Information Complexity and Generalization Bounds

Abstract

We present a unifying picture of PAC-Bayesian and mutual information-based upper bounds on the generalization error of randomized learning algorithms. As we show, Tong Zhang's information exponential inequality (IEI) gives a general recipe for constructing bounds of both flavors. We show that several important results in the literature can be obtained as simple corollaries of the IEI under different assumptions on the loss function. Moreover, we obtain new bounds for data-dependent priors and unbounded loss functions. Optimizing the bounds gives rise to variants of the Gibbs algorithm, for which we discuss two practical examples for learning with neural networks, namely, Entropy- and PAC-Bayes- SGD. Further, we use an Occam's factor argument to show a PAC-Bayesian bound that incorporates second-order curvature information of the training loss.

arXiv commentTo appear in 2021 IEEE International Symposium on Information Theory (ISIT); 23 pages

References in corpus (11)

• Weight Uncertainty in Neural Networks
• Information-theoretic analysis of generalization capability of learning algorithms
• From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation
• Generalization in Adaptive Data Analysis and Holdout Reuse
• A Note on the PAC Bayesian Theorem
• A PAC-Bayesian Tutorial with A Dropout Bound
• Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learning
• Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes
• Generalization Bounds via Information Density and Conditional Information Density
• Learners that Use Little Information
• PAC-Bayes Mini-tutorial: A Continuous Union Bound

Cited by in corpus (2)

• User-friendly introduction to PAC-Bayes bounds
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics