PAC-Bayesian Inequalities for Martingales

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

137 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Statistical Learning Theory

Citations in the corpus

PAC-Bayesian Theory Meets Bayesian Inference (2016, neutral): “However, despite the amount of work dedicated to this statistical learning theory—many authors improved the initial results [9, 29, 33, 43, 48] and/or generalized them for various machine learning setups [4, 14, 20, 28, 38, 44, 45, 46]—it is mostly used as a frequentist method.”
Counterfactual reasoning and learning systems: the example of computational advertising (2012, background): “In order to maximize the accumulated rewards, the player must construct policies π that balance the exploration of the action space with the exploitation of the best action identified so far (Auer et al., 2002; Audibert et al., 2007; Seldin et al., 2012).”
Curriculum learning of multiple tasks (2014, methodology): “ by Abased on Q i 1 and S i, m = 1 n P n i=1 1 m i 1 is the harmonic mean of the sample sizes and KL denotes Kullback-Leibler divergence. Proof. First we use Donsker-Varadhan’s variational formula [33] to change the expectation over posteriors (Q 1;:::;Q n) to the expectation over priors (Q 0;Q 1;:”
Lifelong Learning with Non-i.i.d. Tasks (2015, methodology): “We use techniques from [17] in combination of those from [13], resulting in the following lemma: Lemma 1.”
PAC-Bayesian Bounds based on the Rényi Divergence (2016, methodology): “Note that the same result is derived from Fenchel’s inequality [Banerjee, 2006] and Donsker-Varadhan’s variational formula for relative entropy [Seldin et al., 2012, Tolstikhin and Seldin, 2013].”
PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits (2011, methodology): “In Seldin et al. (2011c) we handled this dependence by combining PAC-Bayesian analysis with Hoeffding-Azuma-type inequalities for martingales.”
PAC-Bayes-Empirical-Bernstein Inequality (2013, methodology): “We start with providing the problem setting and then give some background on PAC-Bayesian analysis.”
Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm (2015, background): “, 2014), Co-clustering (Seldin and Tishby, 2009, 2010), Martingales (Seldin et al., 2012), UStatistics of higher order (Lever et al.”
PAC-Bayesian Collective Stability (2014, methodology): “Our PACBayes proofs are based on a martingale technique due to Lever et al. (2010) and Seldin et al. (2012).”
Stability and Generalization in Structured Prediction (2016, methodology): “PAC-Bayesian analysis is often accredited to McAllester (1998, 1999), and has been refined by a number of authors (e.g., Herbrich and Graepel, 2001; Langford and Shawe-Taylor, 2002; Seeger, 2002; Ambroladze et al., 2006; Catoni, 2007; Germain et al., 2009; Lever et al., 2010; Seldin et al., 2012).”
Bayesian Counterfactual Risk Minimization (2018, methodology): “To achieve a similar rate, we could perhaps use a PACBayesian Bernstein inequality [29, 34].”
User-friendly introduction to PAC-Bayes bounds (2021, methodology): “Other time series models where PAC-Bayes bounds were used include martingales [176], Markov chains [21], continuous dynamical systems [93], LTI systems [72].”