Abstract
We present a new family of information-theoretic generalization bounds, in which the training loss and the population loss are compared through a jointly convex function. This function is upper-bounded in terms of the disintegrated, samplewise, evaluated conditional mutual information (CMI), an information measure that depends on the losses incurred by the selected hypothesis, rather than on the hypothesis itself, as is common in probably approximately correct (PAC)-Bayesian results. We demonstrate the generality of this framework by recovering and extending previously known information-theoretic bounds. Furthermore, using the evaluated CMI, we derive a samplewise, average version of Seeger's PAC-Bayesian bound, where the convex function is the binary KL divergence. In some scenarios, this novel bound results in a tighter characterization of the population loss of deep neural networks than previous bounds. Finally, we derive high-probability versions of some of these average bounds. We demonstrate the unifying nature of the evaluated CMI bounds by using them to recover average and high-probability generalization bounds for multiclass classification with finite Natarajan dimension.
Introduction
In machine learning, a generalization bound provides a mathematical guarantee on how a model's performance on unseen data (population loss) relates to its performance on training data (training loss). Traditional information-theoretic bounds typically analyze the mutual information between the training data and the model's weights. However, for modern deep neural networks (DNNs) with millions of parameters, these weight-based bounds often become "vacuous"—they technically hold but are so loose (e.g., predicting an error rate of over 100%) that they provide no practical utility.
This paper introduces a versatile framework for deriving generalization bounds based on "evaluated Conditional Mutual Information" (e-CMI). By shifting the focus from high-dimensional model weights to the specific losses a model incurs, the authors provide a tighter and more stable characterization of generalization in deep learning.
The Shift to Evaluated CMI
The core problem with traditional bounds is that the information content in model weights often explodes as training progresses, even when the model generalizes well. To address this, the authors build on the Conditional Mutual Information (CMI) framework. In this setup, we consider a "supersample" of $2n$ data points, from which $n$ points are randomly selected for training. The goal is to bound the information the learning algorithm "memorizes" about which specific points were chosen.
Instead of measuring the information between the training set and the hypothesis (the weights), the authors measure the information between the training set and the losses the model produces on the supersample. Because the generalization gap depends only on these losses, measuring the information in the losses (e-CMI) is inherently tighter than measuring the information in the weights, a principle supported by the data-processing inequality.
Theoretical Framework: The Generic Main Lemma
The paper's methodological foundation is a "Generic Main Lemma." This lemma uses jointly convex functions to compare training and population losses, acting as a skeleton for creating various types of bounds.
Using this framework, the authors derive a samplewise version of Seeger’s PAC-Bayesian bound. This "Binary KL bound" utilizes the binary Kullback-Leibler (KL) divergence—a measure of discrepancy between two Bernoulli distributions. This approach is particularly powerful in the "interpolating regime" common in deep learning, where training error is near zero. By using convex functions, the framework can "squeeze" the bound tighter than standard square-root or linear bounds.
Empirical Results and Stability
The authors evaluated their bounds using standard benchmarks, including binarized MNIST, CIFAR-10, and a ResNet-50 model fine-tuned on CIFAR-10. Their findings highlight several key advantages of the e-CMI approach:
- Superior Tightness: The Binary KL bound consistently outperformed previous square-root and linear bounds in numerical experiments, providing a much more accurate estimate of actual test error.
- Stability Over Time: While weight-based bounds often increase as a model trains, e-CMI bounds remain remarkably stable. This suggests that while a model's weights may change significantly, the information it holds about its specific training errors does not necessarily grow.
- Handling Overfitting: The bounds remained non-vacuous even in scenarios with label corruption (randomized training labels), where many other theoretical guarantees fail.
Conclusion and Future Work
The e-CMI framework serves as a unifying language for generalization theory, capable of recovering classical results like those based on the Natarajan dimension. While the current work assumes independent and identically distributed (i.i.d.) data and bounded loss functions, it opens new avenues for understanding why deep networks generalize. Future research may extend these bounds to non-i.i.d. data or unbounded losses, further bridging the gap between theoretical guarantees and practical deep learning performance.
Summary updated