Learners that Use Little Information

Abstract

We study learning algorithms that are restricted to using a small amount of information from their input sample. We introduce a category of learning algorithms we term $d$-bit information learners, which are algorithms whose output conveys at most $d$ bits of information of their input. A central theme in this work is that such algorithms generalize. We focus on the learning capacity of these algorithms, and prove sample complexity bounds with tight dependencies on the confidence and error parameters. We also observe connections with well studied notions such as sample compression schemes, Occam's razor, PAC-Bayes and differential privacy. We discuss an approach that allows us to prove upper bounds on the amount of information that algorithms reveal about their inputs, and also provide a lower bound by showing a simple concept class for which every (possibly randomized) empirical risk minimizer must reveal a lot of information. On the other hand, we show that in the distribution-dependent setting every VC class has empirical risk minimizers that do not reveal a lot of information.

Cited by in corpus (26)

• The Conditional Entropy Bottleneck
• User-friendly introduction to PAC-Bayes bounds
• Generalization Bounds via Information Density and Conditional Information Density
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• Predictive Information Accelerates Learning in RL
• Reasoning About Generalization via Conditional Mutual Information
• Information Complexity and Generalization Bounds
• Information-theoretic generalization bounds for black-box learning algorithms
• Generalization Error Bounds Via Rényi-, $f$-Divergences and Maximal Leakage
• Bounding Information Leakage in Machine Learning
• Robust Predictable Control
• Information Bottleneck and its Applications in Deep Learning
• Variational Predictive Information Bottleneck
• A New Approach to Adaptive Data Analysis and Learning via Maximal Leakage
• PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
• Calibrating Noise to Variance in Adaptive Data Analysis
• A Limitation of the PAC-Bayes Framework
• An Optimal Transport View on Generalization
• A necessary and sufficient stability notion for adaptive generalization
• Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
• Average-Case Information Complexity of Learning
• A Direct Sum Result for the Information Complexity of Learning
• Guess First to Enable Better Compression and Adversarial Robustness
• Whitening and second order optimization both make information in the dataset unusable during training, and can reduce or prevent generalization