PAC-Bayesian Inequalities for Martingales

作者：Seldin Yevgeny^*; Laviolette Francois; Cesa Bianchi Nicolo; Shawe Taylor John; Auer Peter

来源：IEEE Transactions on Information Theory, 2012, 58(12): 7086-7093.

DOI：10.1109/TIT.2012.2211334

• Bernstein%26apos
• s inequality
• Hoeffding-Azuma%26apos
• s inequality
• martingales
• PAC-Bayesian bounds

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. Our results extend the PAC-Bayesian (probably approximately correct) analysis in learning theory from the i.i.d. setting to martingales opening the way for its application to importance weighted sampling, reinforcement learning, and other interactive learning domains, as well as many other domains in probability theory and statistics, where martingales are encountered. We also present a comparison inequality that bounds the expectation of a convex function of a martingale difference sequence shifted to the [0, 1] interval by the expectation of the same function of independent Bernoulli random variables. This inequality is applied to derive a tighter analog of Hoeffding-Azuma%26apos;s inequality.

• 出版日期2012-12