PAC-Bayesian Inequalities for Martingales

DOI10.1109/TIT.2012.2211334zbMATH Open1364.60030arXiv1110.6886WikidataQ59538561 ScholiaQ59538561MaRDI QIDQ2989669FDOQ2989669

John Shawe-Taylor, Peter Auer, Yevgeny Seldin, Nicolò Cesa-Bianchi, François Laviolette

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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 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 variables. This inequality is applied to derive a tighter analog of Hoeffding-Azuma's inequality.

Full work available at URL: https://arxiv.org/abs/1110.6886

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Martingales with discrete parameter (60G42)

Cited In (12)

• PAC-Bayesian inequalities of some random variables sequences
• 1-bit matrix completion: PAC-Bayesian analysis of a variational approximation
• Exponential inequalities for nonstationary Markov chains
• On some recent advances on high dimensional Bayesian statistics
• Title not available (Why is that?)
• PAC-Bayesian lifelong learning for multi-armed bandits
• Simpler PAC-Bayesian bounds for hostile data
• Stochastic feature mapping for PAC-Bayes classification
• A reduced-rank approach to predicting multiple binary responses through machine learning
• Prediction of time series by statistical learning: general losses and fast rates
• High-dimensional sparse classification using exponential weighting with empirical hinge loss
• User-friendly Introduction to PAC-Bayes Bounds

This page was built for publication: PAC-Bayesian Inequalities for Martingales

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989669)