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

CREATORMilad Sefidgaran, Kimia Nadjahi, Abdellatif Zaidi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE215 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-23485

Browse the full library · About the Tower of Babel