Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization
Milad Sefidgaran, Kimia Nadjahi, Abdellatif Zaidi · 2025
Read Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization by Milad Sefidgaran, Kimia Nadjahi, Abdellatif Zaidi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-23485.txt.
Introduction
Milad Sefidgaran, Kimia Nadjahi, and Abdellatif Zaidi tighten the theory that bounds how badly a learning algorithm can fail on new data. Their bounds use conditional mutual information, which measures how much the trained model reveals about its training set. Recent work showed older information-based bounds can go empty or misdescribe behavior on certain problems, leaving a gap in the theory.
The new ingredient is to project the model's output randomly and compress it with loss, before measuring the information. On the very problem cases where older bounds failed, the new ones give guarantees that shrink like one over the square root of the sample size, the healthy rate. The authors also revisit claims that good learning forces an algorithm to memorize much of its data. They show any algorithm has a twin that does not memorize yet generalizes about as well, for every data distribution.
Catalog record
| CREATOR | Milad Sefidgaran, Kimia Nadjahi, Abdellatif Zaidi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 215 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-23485