Information-theoretic analysis of generalization capability of learning algorithms

Abstract

We derive upper bounds on the generalization error of a learning algorithm in terms of the mutual information between its input and output. The bounds provide an information-theoretic understanding of generalization in learning problems, and give theoretical guidelines for striking the right balance between data fit and generalization by controlling the input-output mutual information. We propose a number of methods for this purpose, among which are algorithms that regularize the ERM algorithm with relative entropy or with random noise. Our work extends and leads to nontrivial improvements on the recent results of Russo and Zou.

Final version, accepted to NIPS 2017

References in corpus (1)

• On-Average KL-Privacy and its equivalence to Generalization for Max-Entropy Mechanisms

Cited by in corpus (56)

• On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views
• User-friendly introduction to PAC-Bayes bounds
• Where is the Information in a Deep Neural Network?
• Generalization Bounds via Information Density and Conditional Information Density
• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• Enforcing constraints for interpolation and extrapolation in Generative Adversarial Networks
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Information-Theoretic Generalization Bounds for Meta-Learning and Applications
• The Convex Information Bottleneck Lagrangian
• An Information-Theoretic View for Deep Learning
• On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm
• Tighter expected generalization error bounds via Wasserstein distance
• Knowledge Consistency between Neural Networks and Beyond
• Reasoning About Generalization via Conditional Mutual Information
• Explaining Knowledge Distillation by Quantifying the Knowledge
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Generalization Error Bounds Via Rényi-, $f$-Divergences and Maximal Leakage
• Empirical Risk Minimization with Relative Entropy Regularization
• Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis
• Information Complexity and Generalization Bounds
• Chaining Mutual Information and Tightening Generalization Bounds
• PAC-Bayes Information Bottleneck
• Improved Information Theoretic Generalization Bounds for Distributed and Federated Learning
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• A New Approach to Adaptive Data Analysis and Learning via Maximal Leakage
• DECONET: an Unfolding Network for Analysis-based Compressed Sensing with Generalization Error Bounds
• Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting
• The Role of Information Complexity and Randomization in Representation Learning
• Improving Generalization by Controlling Label-Noise Information in Neural Network Weights
• On generalization bounds for deep networks based on loss surface implicit regularization
• Calibrating Noise to Variance in Adaptive Data Analysis
• PAC-Bayes Analysis Beyond the Usual Bounds
• Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning
• A necessary and sufficient stability notion for adaptive generalization
• An Optimal Transport View on Generalization
• Upper Bounds on the Generalization Error of Private Algorithms for Discrete Data
• Rate-Distortion Analysis of Minimum Excess Risk in Bayesian Learning
• Channels, Remote Estimation and Queueing Systems With A Utilization-Dependent Component: A Unifying Survey Of Recent Results
• Formal limitations of sample-wise information-theoretic generalization bounds
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• Trap of Feature Diversity in the Learning of MLPs
• Information-Theoretic Odometry Learning
• Learning via Wasserstein-Based High Probability Generalisation Bounds
• Interpreting and Disentangling Feature Components of Various Complexity from DNNs
• Double Descent Risk and Volume Saturation Effects: A Geometric Perspective
• Gaussian Mean Field Regularizes by Limiting Learned Information
• Comparing Comparators in Generalization Bounds
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD
• REVE: Regularizing Deep Learning with Variational Entropy Bound
• Think Global, Act Local: Relating DNN generalisation and node-level SNR
• Distribution-Dependent Analysis of Gibbs-ERM Principle
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Quantization-Based Regularization for Autoencoders
• Label-Based Diversity Measure Among Hidden Units of Deep Neural Networks: A Regularization Method