Quantifying Generalization via Information Leakage

296 concepts156 papers1 proposal

Why do machine learning models generalize to unseen data? Traditional statistical learning theory answers this question using combinatorial measures like the Vapnik-Chervonenkis (VC) dimension or Rademacher complexity. However, these classical bounds are algorithm-independent; they evaluate the worst-case scenario across an entire hypothesis space. In modern deep learning, where models possess millions of parameters and can perfectly fit random noise, these worst-case bounds become vacuous.

To understand why specific algorithms generalize well, researchers have turned to information theory. The core intuition is elegant: the learning process can be modeled as a communication channel. The training dataset is the input, and the learned model parameters are the output.

If an algorithm overfits, it acts as a high-capacity channel that memorizes the specific quirks and noise of the training data. If it generalizes, it acts as an information bottleneck, extracting only the essential, distributable patterns. By bounding this "information leakage," we can directly bound the generalization error.

The Core Mutual Information Framework

The foundational approach to this perspective quantifies generalization by measuring the Shannon mutual information $I(W; S)$ between the training dataset $S$ and the learned model weights $W$. As shown by Ankit Pensia et al. in Generalization Error Bounds for Noisy, Iterative Algorithms, the expected generalization gap—the difference between a model's performance on its training set versus the true data distribution—is directly controlled by how much information the weights capture about the dataset. If an algorithm limits this information transfer, it is mathematically prevented from overfitting.

This framework naturally explains why noise injection—such as stochastic gradient Langevin dynamics (SGLD) or dropout—improves performance. Noise acts as a deliberate constraint on the channel capacity, preventing the weights from capturing fine-grained details about individual training samples. Similarly, Hui Li et al. in Learning to Generalize: An Information Perspective on Neural Processes demonstrate that explicitly minimizing the mutual information between parameters and training data via regularization yields tighter generalization bounds and better adaptation to unseen tasks.

The Infinity Problem for High-Dimensional Models

Despite its theoretical elegance, the naive mutual information framework faces a severe technical hurdle when applied to modern deep networks: it often becomes vacuous or infinite.

If a learning algorithm is deterministic (like standard gradient descent) and the weights are continuous, the mutual information $I(W; S)$ can explode to infinity. Furthermore, a high-dimensional model might retain a massive amount of information about the training set even while generalizing perfectly. As noted by Milad Sefidgaran et al. in Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning, lossless information metrics fail to provide meaningful, finite bounds for complex learning algorithms. This mismatch reveals that we do not just need to measure how much information is retained, but how that information is structured.

Solution 1: The Conditional Mutual Information Framework

To circumvent the infinity problem, researchers introduced the supersample framework and Conditional Mutual Information (CMI). Instead of looking at the absolute information the weights $W$ contain about the dataset $S$, we imagine a larger "supersample" $U$ containing $2n$ samples. The actual training set $S$ is formed by choosing $n$ samples from $U$ based on a vector of binary selection variables $V$.

The learning algorithm's information leakage is then measured as the conditional mutual information $I(W; V | U)$—how much the final weights reveal about which specific samples were chosen for training out of the larger pool. As Thomas Steinke et al. argue in Open Problem: Information Complexity of VC Learning, CMI serves as a powerful, algorithm-dependent measure of generalization because it is inherently bounded by the number of training samples (at most $n$ bits), even for deterministic algorithms.

By shifting the focus from high-dimensional weights to the binary membership of data samples, frameworks like the evaluated CMI (e-CMI) developed by Fredrik Hellström et al. in Generalization Bounds via Information Density and Conditional Information Density successfully provide non-vacuous, data-dependent bounds that track real-world performance.

Solution 2: Rate-Distortion and Lossy Compression

Another way to bypass the limitations of lossless mutual information is to treat the model parameters not as an exact description, but as a compressible signal. This perspective brings in rate-distortion theory from lossy data compression.

Instead of requiring the exact weights $W$ to be independent of $S$, we ask: can we compress $W$ into a lower-rate representation $\hat{W}$ such that the performance (distortion) remains acceptable? The authors of Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning demonstrate that by bounding generalization error using lossy compression principles, the resulting bounds remain informative and finite even for continuous parameters and deterministic training procedures. Generalization is guaranteed because a model that can be heavily compressed without losing its predictive power cannot have memorized the fine-grained noise of the training set.

Alternative Divergences and Fine-Grained Perspectives

The evolution of this field has led to a rich toolkit of alternative information-theoretic metrics designed to capture different facets of learning dynamics:

Fundamental Limits of Information Bounds

While information-theoretic bounds offer a powerful lens, they also face intrinsic limits. Roi Livni demonstrates in Information Theoretic Lower Bounds for Information Theoretic Upper Bounds that in certain convex optimization settings, accurate algorithms are fundamentally forced to retain a high degree of correlation with their training data. This implies that mutual information bounds must sometimes scale with the dimension of the problem, even when the algorithm's actual generalization error does not.

Nevertheless, these information-theoretic frameworks successfully shift our understanding of machine learning away from static properties of the hypothesis space and toward the dynamic efficiency with which an algorithm processes and compresses information.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 174 papers
  2. Version 1 · 2026-10-04 · 180 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_information_theoretic_generalization_bou_bbc24be4,
  title = {information-theoretic generalization bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-theoretic-generalization-bounds/rdr_bbc24be433744d16927a74ea5f1d4993},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_information_theoretic_generalization_bou_bbc24be4_v2,
  title = {information-theoretic generalization bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-theoretic-generalization-bounds/rdr_bbc24be433744d16927a74ea5f1d4993/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake