PAC-Bayesian Inequalities for Martingales
- 2 August 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 58 (12) , 7086-7093
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. 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's inequality.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Entropy and Information Theory2011
- Distribution-Dependent PAC-Bayes PriorsLecture Notes in Computer Science, 2010
- PAC-Bayesian learning of linear classifiers2009
- PAC-Bayesian Stochastic Model SelectionMachine Learning, 2003
- Elements of Information Theory2001
- Structural risk minimization over data-dependent hierarchiesIEEE Transactions on Information Theory, 1998
- Some PAC-Bayesian theorems1998
- A Weak Convergence Approach to the Theory of Large Deviations1997
- A theory of the learnableCommunications of the ACM, 1984
- Asymptotic evaluation of certain markov process expectations for large time, ICommunications on Pure and Applied Mathematics, 1975