# Exactly Tight Information-Theoretic Generalization Error Bound for the Quadratic Gaussian Problem

arXiv: https://arxiv.org/abs/2305.00876 · HTML: https://mlsanity.com/paper/2305.00876/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 39 references that are in the map.
- First posted on arXiv 1 May 2023.

## Builds on (most cited first, 26 of 26)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Generalization Bounds via Information Density and Conditional Information Density](https://mlsanity.com/paper/2005.08044/) (2020)
- [Information-Theoretic Generalization Bounds for Meta-Learning and Applications](https://mlsanity.com/paper/2005.04372/) (2020)
- [Individually Conditional Individual Mutual Information Bound on Generalization Error](https://mlsanity.com/paper/2012.09922/) (2020)
- [On Random Subset Generalization Error Bounds and the Stochastic Gradient Langevin Dynamics Algorithm](https://mlsanity.com/paper/2010.10994/) (2020)
- [Generalization Bounds via Convex Analysis](https://mlsanity.com/paper/2202.04985/) (2022)
- [Information-theoretic analysis for transfer learning](https://mlsanity.com/paper/2005.08697/) (2020)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Tighter Expected Generalization Error Bounds via Convexity of Information Measures](https://mlsanity.com/paper/2202.12150/) (2022)
- [Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness](https://mlsanity.com/paper/2210.06511/) (2022)
- [Improved Information Theoretic Generalization Bounds for Distributed and Federated Learning](https://mlsanity.com/paper/2202.02423/) (2022)
- [From Generalisation Error to Transportation-cost Inequalities and Back](https://mlsanity.com/paper/2202.03956/) (2022)
- [Fast Rate Generalization Error Bounds: Variations on a Theme](https://mlsanity.com/paper/2205.03131/) (2022)

## Built on by (most cited first, 4 of 4)

- [Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Bounds](https://mlsanity.com/paper/2310.20102/) (2023)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces](https://mlsanity.com/paper/2402.05576/) (2024)
- [Block-Sample MAC-Bayes Generalization Bounds](https://mlsanity.com/paper/2602.12605/) (2026)

## Abstract (arXiv)

We provide a new information-theoretic generalization error bound that is exactly tight (i.e., matching even the constant) for the canonical quadratic Gaussian (location) problem. Most existing bounds are order-wise loose in this setting, which has raised concerns about the fundamental capability of information-theoretic bounds in reasoning the generalization behavior for machine learning. The proposed new bound adopts the individual-sample-based approach proposed by Bu et al., but also has several key new ingredients. Firstly, instead of applying the change of measure inequality on the loss function, we apply it to the generalization error function itself; secondly, the bound is derived in a conditional manner; lastly, a reference distribution is introduced. The combination of these components produces a KL-divergence-based generalization error bound. We show that although the latter two new ingredients can help make the bound exactly tight, removing them does not significantly degrade the bound, leading to an asymptotically tight mutual-information-based bound. We further consider the vector Gaussian setting, where a direct application of the proposed bound again does not lead to tight bounds except in special cases. A refined bound is then proposed for decomposable loss functions, leading to a tight bound for the vector setting.