Reasoning About Generalization via Conditional Mutual Information

Abstract

We provide an information-theoretic framework for studying the generalization properties of machine learning algorithms. Our framework ties together existing approaches, including uniform convergence bounds and recent methods for adaptive data analysis. Specifically, we use Conditional Mutual Information (CMI) to quantify how well the input (i.e., the training data) can be recognized given the output (i.e., the trained model) of the learning algorithm. We show that bounds on CMI can be obtained from VC dimension, compression schemes, differential privacy, and other methods. We then show that bounded CMI implies various forms of generalization.

arXiv comment58 pages. Changes from previous version: Added discussion on related work and updated references. Simplified part of the proof of Theorem 4.10

References in corpus (16)

• The information bottleneck method
• Rényi Divergence and Kullback-Leibler Divergence
• Information-theoretic analysis of generalization capability of learning algorithms
• Generalization in Adaptive Data Analysis and Holdout Reuse
• Generalization Bounds via Information Density and Conditional Information Density
• Learners that Use Little Information
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• Generalization Bounds for Uniformly Stable Algorithms
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• Limits of Private Learning with Access to Public Data
• A New Approach to Adaptive Data Analysis and Learning via Maximal Leakage
• PAC learning with stable and private predictions
• Information, Privacy and Stability in Adaptive Data Analysis
• Average-Case Information Complexity of Learning
• Uniform Generalization, Concentration, and Adaptive Learning

Cited by in corpus (6)

• Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis
• For self-supervised learning, Rationality implies generalization, provably
• Information-Theoretic Analysis of Epistemic Uncertainty in Bayesian Meta-learning
• Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning
• Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL information
• A Probabilistic Representation of DNNs: Bridging Mutual Information and Generalization