User-friendly introduction to PAC-Bayes bounds

Abstract

Aggregated predictors are obtained by making a set of basic predictors vote according to some weights, that is, to some probability distribution. Randomized predictors are obtained by sampling in a set of basic predictors, according to some prescribed probability distribution. Thus, aggregated and randomized predictors have in common that they are not defined by a minimization problem, but by a probability distribution on the set of predictors. In statistical learning theory, there is a set of tools designed to understand the generalization ability of such procedures: PAC-Bayesian or PAC-Bayes bounds. Since the original PAC-Bayes bounds of D. McAllester, these tools have been considerably improved in many directions (we will for example describe a simplified version of the localization technique of O. Catoni that was missed by the community, and later rediscovered as "mutual information bounds"). Very recently, PAC-Bayes bounds received a considerable attention: for example there was workshop on PAC-Bayes at NIPS 2017, "(Almost) 50 Shades of Bayesian Learning: PAC-Bayesian trends and insights", organized by B. Guedj, F. Bach and P. Germain. One of the reason of this recent success is the successful application of these bounds to neural networks by G. Dziugaite and D. Roy. An elementary introduction to PAC-Bayes theory is still missing. This is an attempt to provide such an introduction.

References in corpus (21)

• Gibbs posterior for variable selection in high-dimensional classification and data mining
• A Note on the PAC Bayesian Theorem
• Fast learning rates in statistical inference through aggregation
• On the properties of variational approximations of Gibbs posteriors
• Optimal rates and adaptation in the single-index model using aggregation
• PAC-Bayesian Bounds for Randomized Empirical Risk Minimizers
• On the Generalization Gap in Reparameterizable Reinforcement Learning
• PAC-Bayes Mini-tutorial: A Continuous Union Bound
• Information Complexity and Generalization Bounds
• PAC-Bayesian AUC classification and scoring
• PAC-Bayes Information Bottleneck
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• The Bayesian Learning Rule
• PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
• PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior
• On the Robustness to Misspecification of $\alpha$-Posteriors and Their Variational Approximations
• PAC-Bayes Analysis of Sentence Representation
• PAC-Bayesian Generalization Bounds for MultiLayer Perceptrons
• How Tight Can PAC-Bayes be in the Small Data Regime?
• Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL information
• New bounds for $k$-means and information $k$-means

Cited by in corpus (8)

• Generalization Bounds for Neural Belief Propagation Decoders
• High-dimensional sparse classification using exponential weighting with empirical hinge loss
• Misclassification bounds for PAC-Bayesian sparse deep learning
• Progress in Self-Certified Neural Networks
• A PAC-Bayesian Framework for Optimal Control with Stability Guarantees
• Comparing Comparators in Generalization Bounds
• PAC-Bayes Bounds for High-Dimensional Multi-Index Models with Unknown Active Dimension
• A PAC-Bayes oracle inequality for sparse neural networks