Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms

Abstract

The information-theoretic framework of Russo and J. Zou (2016) and Xu and Raginsky (2017) provides bounds on the generalization error of a learning algorithm in terms of the mutual information between the algorithm's output and the training sample. In this work, we study the proposal, by Steinke and Zakynthinou (2020), to reason about the generalization error of a learning algorithm by introducing a super sample that contains the training sample as a random subset and computing mutual information conditional on the super sample. We first show that these new bounds based on the conditional mutual information are tighter than those based on the unconditional mutual information. We then introduce yet tighter bounds, building on the "individual sample" idea of Bu, S. Zou, and Veeravalli (2019) and the "data dependent" ideas of Negrea et al. (2019), using disintegrated mutual information. Finally, we apply these bounds to the study of Langevin dynamics algorithm, showing that conditioning on the super sample allows us to exploit information in the optimization trajectory to obtain tighter bounds based on hypothesis tests.

arXiv comment23 Pages, 3 Figures. To appear in, Advances in Neural Information Processing Systems (34), 2020

References in corpus (7)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Information-theoretic analysis of generalization capability of learning algorithms
• Learners that Use Little Information
• Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates
• How much does your data exploration overfit? Controlling bias via information usage
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets

Cited by in corpus (13)

• Generalization Bounds via Information Density and Conditional Information Density
• Recent advances in deep learning theory
• On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm
• Reasoning About Generalization via Conditional Mutual Information
• Empirical Risk Minimization with Relative Entropy Regularization
• PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
• Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning
• Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• Formal limitations of sample-wise information-theoretic generalization bounds
• Comparing Comparators in Generalization Bounds
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics