A Note on the PAC Bayesian Theorem

By Andreas Maurer. 2004

229 citations recorded by the source corpus.

We prove general exponential moment inequalities for averages of [0,1]-valued iid random variables and use them to tighten the PAC Bayesian Theorem. The logarithmic dependence on the sample count in the enumerator of the PAC Bayesian bound is halved.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

In Statistical Learning Theory

Citations in the corpus

PAC-Bayesian Theory Meets Bayesian Inference (2016, methodology): “We thank Gabriel Dubé and Maxime Tremblay for having proofread the paper and supplemental.”
A PAC-Bayesian Tutorial with A Dropout Bound (2013, background): “PAC-Bayesian generalization bounds [11, 12, 10, 7, 4, 6] govern the performance (loss) when stochastically selecting rules from a “posterior” distribution.”
Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm (2015, background): “The proof of Lemma 51 (below) follows the key steps of the proof of Lemma 50 by Maurer (2004), but we include a few more mathematical details for completeness.”
PAC-Bayesian Inequalities for Martingales (2011, result): “The lemma generalizes a previous result by Maurer for independent random variables [19].”
User-friendly introduction to PAC-Bayes bounds (2021, background): “1 McAllester’s bound [134] and Maurer’s improved bound [133] As the original paper by McAllester [134] focused on finite or denumerable sets Θ, let us start with the first bound for a general Θ, in [135].”
Supplementary Material to A PAC-Bayesian Approach for Domain Adaptation with Specialization to Linear Classiﬁers (2013, background): “Denote X (cid:48) = ( X 1 , . . . , X m ) , where X i is the unique Bernoulli ( { 0 , 1 } -valued) random variable with Lemma 4 (from Inequalities (1) and (2) of Maurer (2004)) .”
Fairness in Machine Learning (2020, result): “This condition is quite natural, empirically veriﬁable, and it has been exploited in previous work [44, 124].”
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions (2013, methodology): “This proof follows Seeger’s PAC-Bayesian approach [19], and extended to the structured label case [13].”
Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory (2017, background): “Consider the following single-task bound by (Seeger, 2002; Maurer, 2004).”
PAC-Bayesian Analysis of Co-clustering and Beyond (2010, background): “Maurer (2004) showed that due to convexity of the KL-divergence, inequality (1) is valid for all loss functions bounded in the [0,1] interval, and not only for the zero-one loss.”