Finite Generalization Bounds via Bounded Information Measures

This direction is merged into another direction: information-theoretic generalization bounds. Its last version stays readable and citable here.

Version 1 of 19 papers17 conceptsfrozen 2026-10-04

In machine learning theory, we often want to bound the "generalization gap"—the difference between how a model performs on its training data versus how it performs on unseen data. For years, the gold standard for this analysis has been information theory, specifically using Mutual Information (MI) to quantify how much a model "memorizes" its training set.

However, traditional information-theoretic bounds face a fatal flaw: in modern deep learning, they often become infinite. When a learning algorithm is deterministic or the model capacity is high, the mutual information between the input data and the resulting hypothesis can blow up, rendering the bound "vacuous" (useless). Recent research has pivoted toward a new strategy: replacing unbounded measures like Kullback-Leibler (KL) divergence with bounded, symmetric alternatives that remain informative even in complex, high-dimensional regimes.

The Problem of Infinite Information

The core intuition behind information-theoretic generalization is that if a model $W$ depends too heavily on the specific training set $S$, it is likely to overfit. We quantify this dependence using the mutual information $I(S; W)$.

As Gholamali Aminian, Laura Toni, and Miguel R. D. Rodrigues point out in Jensen-Shannon Information Based Characterization of the Generalization Error of Learning Algorithms, this approach breaks down when the relationship between data and hypothesis is deterministic. In such cases, the KL divergence (which underlies MI) can become infinite. If your mathematical "speed limit" for error is infinity, you haven't actually learned anything about the model's performance.

Smoothing the Divergence with Jensen-Shannon

To solve this, Aminian et al. propose using Jensen-Shannon (JS) information. Unlike KL divergence, JS divergence is:

  1. Symmetric: It treats the two distributions equally.
  2. Bounded: It never exceeds a finite value (typically $\log 2$).

By using a smoothed, symmetric information measure derived from the average of the joint and marginal distributions, the researchers ensure that the generalization bound remains finite regardless of model complexity. This allows theorists to provide stable upper limits on expected generalization error even for high-capacity models that would otherwise "break" traditional MI bounds.

Turning Entropy into a Metric

A parallel challenge is that traditional relative entropy isn't a true mathematical "distance"—it doesn't satisfy the triangle inequality. This makes it difficult to use in optimization or clustering where consistent normalization is required.

In A Novel Distance Matric: Generalized Relative Entropy, Shuai Liu and colleagues introduce Generalized Relative Entropy (GRE). By structurally modifying the divergence formula, they transform entropy into a true metric that possesses a finite upper bound. This prevents the "gradient explosions" often seen in high-dimensional optimization. When a measure is bounded, it becomes numerically stable, allowing for consistent comparisons across different datasets and model architectures.

Geometry over Probability: The Wasserstein Shift

While JS divergence solves the infinity problem through smoothing, another approach looks at the geometry of the space. In Tighter Expected Generalization Error Bounds via Wasserstein Distance, Borja Rodríguez Gálvez, Mikael Skoglund, and their co-authors argue that Wasserstein distance (derived from optimal transport) is a superior tool for modern deep learning.

The intuition here is that Wasserstein distance measures the "work" required to transform one distribution into another. Unlike MI, which only cares about whether two distributions overlap, Wasserstein distance cares about how far apart they are. This makes it particularly robust for deterministic learning algorithms. Even if the model's weights are a direct, non-stochastic function of the data, the Wasserstein distance remains finite and informative, providing a much tighter "gap" estimate than traditional information theory.

Why It Works: Stability through Boundedness

The shared insight across these papers is that unboundedness is the enemy of generalization theory.

  • Numerical Stability: Bounded measures like GRE prevent the instability associated with infinite values in high-dimensional spaces.
  • Deterministic Compatibility: Measures like JS information and Wasserstein distance don't "blow up" just because a model lacks stochasticity.
  • Tightness: By using measures that respect the geometry or the finite range of the hypothesis space, researchers can produce bounds that actually track with empirical performance.

By shifting from KL-based mutual information to these more robust, bounded measures, the field is moving toward a framework that can finally explain why massive, deterministic neural networks generalize as well as they do.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_finite_generalization_bounds_via_bounded_7be6c57e,
  title = {Finite Generalization Bounds via Bounded Information Measures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-generalization-bounds-via-bounded-information-measures/rdr_7be6c57e525f434e80855fa971e17a51},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_finite_generalization_bounds_via_bounded_7be6c57e_v1,
  title = {Finite Generalization Bounds via Bounded Information Measures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/finite-generalization-bounds-via-bounded-information-measures/rdr_7be6c57e525f434e80855fa971e17a51/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}