Does Compression Imply Generalization? A Minimum Description Length Perspective
Abstract
A central question in modern learning theory is what notion of compression, if any, explains why over-parameterized neural networks generalize. Existing answers measure complexity at different levels, ranging from weights to representations; however, estimating the associated quantities either requires held-out data in principle or relies on the challenging (ultra) high-dimensional mutual information estimation. To overcome these challenges, we approach the question through the minimum description length (MDL) principle, and specifically, we propose the prequential regret as a complementary signal that is computable from the training trajectory alone. We establish that, in the (nearly) interpolating regime, the expected prequential regret upper-bounds the description length of the trained parameter under the algorithm-induced distribution, and that this description length translates into a high-probability generalization bound in the PAC-MDL setting. Along the way, we show that the encoder-complexity correction recently added to the algorithm-level information bottleneck (IB) is upper-bounded by an MDL parameter description length, \new{bringing together} the two views of compression from MDL and IB. Empirically, the prequential regret tracks the generalization error on CIFAR-10 and CIFAR-100, with Pearson correlations exceeding 0.9.
Authors 7
-
Affiliation as printed
Leiden Institute of Advanced Computer Science , Leiden University , The Netherlands
-
Leiden University · Centrum Wiskunde & Informatica
Affiliation as printed
Centrum Wiskunde & Informatica (CWI) , Amsterdam , The Netherlands
Leiden Institute of Advanced Computer Science , Leiden University , The Netherlands
-
Leiden University · Hefei University of Technology
Affiliation as printed
Hefei University of Technology , Hefei , China
Leiden Institute of Advanced Computer Science , Leiden University , The Netherlands
-
Affiliation as printed
Leiden Institute of Advanced Computer Science , Leiden University , The Netherlands
-
Affiliation as printed
Leiden Institute of Advanced Computer Science , Leiden University , The Netherlands
-
Leiden University · Dongguan University of Technology
Affiliation as printed
Great Bay University , Dongguan , China
Leiden Institute of Advanced Computer Science , Leiden University , The Netherlands
-
UiT The Arctic University of Norway · Vrije Universiteit Amsterdam
Affiliation as printed
Department of Computer Science , Vrije Universiteit Amsterdam , The Netherlands
Department of Physics and Technology , UiT The Arctic University of Norway