Empirical Inference Article 2012

PAC-Bayesian Inequalities for Martingales

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}
}