Does Compression Imply Generalization? A Minimum Description Length Perspective

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, and estimating the associated quantities either requires held-out data in principle or relies on mutual-information estimation in ultra-high dimensions. We approach the question through the minimum description length (MDL) principle and 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 is upper-bounded by an MDL parameter description length, bringing the two views of compression onto a shared footing. Empirically, the prequential regret tracks the generalization error on CIFAR-10 and CIFAR-100, with Pearson correlations exceeding 0.9.