Header logo is ei

PAC-Bayesian Inequalities for Martingales

2012

Article

ei


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

Department(s): Empirical Inference
Research Project(s): Reinforcement Learning
Bibtex Type: Article (article)

DOI: 10.1109/TIT.2012.2211334
State: Published

Links: PDF
Web

BibTex

@article{SeldinLCS2012,
  title = {PAC-Bayesian Inequalities for Martingales },
  author = {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 = {12},
  pages = {7086-7093},
  month = jun,
  year = {2012},
  month_numeric = {6}
}