Research map / Learning theory and algorithms / Kernels and regression theory

Does Compression Imply Generalization? A Minimum Description Length Perspective

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: Empirical generalization measures

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes prequential regret (prequential code length minus in-hindsight code length) as a training-trajectory-only MDL complexity measure, proves it upper-bounds parameter description length in the nearly interpolating regime, derives PAC-MDL generalization bounds, and shows it correlates with the generalization gap on CIFAR-10/100 ResNets.

Problem

Explaining why over-parameterized neural networks generalize via a compression measure that is computable from training alone, without held-out data or high-dimensional mutual information estimation, and linking weight-level MDL compression with representation-level information bottleneck compressio

Approach

Use the prequential coding regret (extra bits of the prequential code over the in-hindsight code of the final model) as a model-complexity signal; prove it upper-bounds the expected description length of the trained parameter under the algorithm-induced distribution in the nearly interpolating regime, and that the IB encoder-complexity correction is bounded by parameter description length.

Key results

• On CIFAR-10, prequential regret reaches Pearson 0.9211 with generalization loss gap and 0.9172 with error gap, outperforming all IB-based baselines in Table 1.
• The parameter-information baseline I(S; theta) via SWAG reaches only Pearson 0.2512 (loss gap) and 0.0775 (error gap) on CIFAR-10.
• On CIFAR-100 over 99 configurations, prequential regret tracks the loss and accuracy gaps with Pearson correlations above 0.9 (per the abstract).

Surprising findings

• Three CIFAR-100 configurations with negative empirical regret were severely underfit and fall outside the theory's regime, so the bound does not apply there.

Limitations

• The generalization bound holds only in the transductive PAC-MDL setting with a finite fixed test set, not population risk.
• Assumes nearly interpolating regime and interpolation-genericity condition; fails for underfit models.
• Empirical validation limited to ResNets on CIFAR-10/100; untested on transformers or language/multimodal data.

Experimental setup

Datasets: CIFAR-10 CIFAR-100

Benchmarks: CIFAR-10 CIFAR-100

Metrics: Pearson correlation Spearman correlation Kendall correlation

Baselines: Kawaguchi et al. IB-based generalization measures I(S; theta) parameter information via SWAG fixed-encoder IB mutual information terms

Builds on: PAC-MDL bound (Blum and Langford) prequential coding (Dawid / Rissanen) modern information bottleneck (Kawaguchi et al.) transductive PAC-Bayes (Bégin et al.) Blier and Ollivier prequential MDL for neural networks

Closest papers by meaning

• The Description Length of Deep Learning models (NeurIPS 2018 · similarity 0.90)
• Minimum Description Length and Generalization Guarantees for Representation Learning (NeurIPS 2023 · similarity 0.90)
• Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks (ICML 2025 · similarity 0.88)
• Provable Length Generalization in Sequence Prediction via Spectral Filtering (ICML 2025 · similarity 0.87)
• Length Generalization for Transformers via Compression (NeurIPS 2026 · similarity 0.86)
• Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.86)