Back
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.
@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} }