We present a set of high-probability inequalities that control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. We also present a comparison inequality that bounds expectation of a convex function of martingale difference type variables by expectation of the same function of independent Bernoulli variables. This inequality is applied to derive a tighter analog of Hoeffding-Azuma inequality.
| Author(s): | Seldin, Y. and Laviolette, F. and Cesa-Bianchi, N. and Shawe-Taylor, J. and Auer, P. |
| Journal: | IEEE Transactions on Information Theory |
| Volume: | 58 |
| Number (issue): | 12 |
| Pages: | 7086-7093 |
| Year: | 2012 |
| Month: | June |
| Day: | 0 |
| Bibtex Type: | Article (article) |
| DOI: | 10.1109/TIT.2012.2211334 |
| State: | Published |
| Electronic Archiving: | grant_archive |
| Links: | |
BibTex
@article{SeldinLCS2012,
title = {PAC-Bayesian Inequalities for Martingales },
journal = {IEEE Transactions on Information Theory},
abstract = {We present a set of high-probability inequalities
that control the concentration of weighted averages of multiple (possibly uncountably many) simultaneously evolving and interdependent martingales. We also present a comparison inequality that bounds expectation of a convex function of martingale difference type variables by expectation of the same function of independent Bernoulli variables. This inequality is applied to derive a tighter analog of Hoeffding-Azuma inequality.},
volume = {58},
number = {12},
pages = {7086-7093},
month = jun,
year = {2012},
slug = {seldinlcs2012},
author = {Seldin, Y. and Laviolette, F. and Cesa-Bianchi, N. and Shawe-Taylor, J. and Auer, P.},
month_numeric = {6}
}