Information-theoretic analysis of generalization capability of learning algorithms

By Aolin Xu, Maxim Raginsky. 2017

562 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Theoretical Guarantees for Model Auditing with Finite Adversaries (2019, background): “More contemporary developments in this topic can be found in [27–32] and references therein.”
Empirical Bayes Transductive Meta-Learning with Synthetic Gradients (2020, methodology): “Next, we extend the result from Xu & Raginsky (2017) and derive a data-dependent upper bound for gen(q) using mutual information.”
User-friendly introduction to PAC-Bayes bounds (2021, background): “Russo and Zou’s result were improved and extended Raginsky, Rakhlin, Tsao, Wu and Xu [159, 200].”
Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, methodology): “It is important to note that the mutual information between learned parameter and a single data point is used to produce generalization bounds in work by Bu, Zou, and Veeravalli [6], Raginsky et al. [26], and Wang, Lei, and Fienberg [32].”
Explaining Knowledge Distillation by Quantifying the Knowledge (2020, methodology): “The information-bottleneck theory [41, 36] used the mutual information to evaluate the representation capacity of DNNs [13, 43].”
An Information-Theoretic View for Deep Learning (2018, background): “The advantage of using the mutual information between the input and output to bound the expected generalization error [15, 19] is that it depends on almost every aspects of the learning algorithm, including the data distribution, the complexity of the hypothesis class, and the property of the learni”
Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting (2020, methodology): “Lemma B.1 ((Xu and Raginsky, 2017)).”
Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints (2017, background): “(2018) proposed another algorithm-dependent generalization bounds for non-convex learning, based on the method of mutual information (Xu and Raginsky, 2017).”
Calibrating Noise to Variance in Adaptive Data Analysis (2017, methodology): “(We note that (Russo and Zou, 2016; Xu and Raginsky, 2017) use the same technique as that used in PAC-Bayes bounds and appear to have overlooked the direct connection between their results and the PAC-Bayes line of work.”
Generalization Error Bounds for Noisy, Iterative Algorithms (2018, methodology): “Our approach leverages recent results that bound the generalization error using the mutual information between the input data set and the output parameter estimates [4], [5].”
Chaining Mutual Information and Tightening Generalization Bounds (2018, background): “This was originally proposed in the key paper of Russo and Zou [8] and then generalized in [16], [17], and in [18] for infinite number of hypotheses: Theorem 2.”
On the Robustness of Information-Theoretic Privacy Measures and Mechanisms (2018, methodology): “This problem has been studied in computer science [41] and, recently, has been analyzed using tools from information theory by Xu and Raginsky [42] and Russo and Zou [43].”
Improving Generalization by Controlling Label-Noise Information in Neural Network Weights (2020, methodology): “Xu & Raginsky (2017) derive generalization bounds that involve this latter quantity.”