PaperlayerView exact revision on arXiv

Source-linked AI summary

Does Compression Imply Generalization? A Minimum Description Length Perspective

Lincen Yang, Jiayang Shi, Nan Pu, Daniël M. Pelt, Matthijs van Leeuwen, Zhong Li, Shujian Yu

arXiv:2610.21376v1cs.LG

TL;DR

Why over-parameterized neural networks generalize despite their capacity to memorize remains a central question, while existing compression measures characterize different aspects of learned models. This paper uses MDL to propose prequential regret as a training-trajectory signal, and reports that it bounds parameter description length and tracks generalization gaps on CIFAR-10 and CIFAR-100.

  • Problem

    Why over-parameterized models generalize despite having enough capacity to memorize their training sets remains a central question, and existing approaches characterize complexity at different levels.

    Source: §1 · p. 1

  • Method

    The paper uses the MDL principle to propose prequential coding regret as an operational complexity signal computable from the training trajectory alone.

    Source: §1 · p. 2, §7 · p. 10

  • Results

    Expected prequential regret upper-bounds trained-parameter description length, yields a PAC-MDL generalization bound, and tracks CIFAR-10 and CIFAR-100 generalization gaps with Pearson correlations exceeding 0.9.

    Source: §4 · p. 7, §5 · p. 7, §7 · p. 10

  • Takeaways & Limitations

    The encoder-complexity correction in algorithm-level IB is upper-bounded by an MDL parameter description length, connecting the two compression views.

    Source: §7 · p. 10

    The generalization bound is transductive, with a finite fixed test set; extending it to a population-risk statement remains open.

    Source: §7 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The section asks how to measure the complexity of over-parameterized models that generalize despite their capacity to memorize, while existing measures differ in what they compress and can be difficult to estimate. It proposes prequential regret through MDL as a training-based signal and summarizes theoretical and empirical links to generalization.

1 Introduction

  • Existing compression measures target weights or representations, while their estimation can require held-out data, high-dimensional mutual information estimates, or complex priors.The section also notes debate over whether Occam-style reasoning applies to over-parameterized networks.Source: §1 · p. 2
  • The paper proposes prequential coding regret as an MDL-based operational complexity signal computable from the training trajectory alone.MDL measures model complexity through the bits needed to encode the model itself in a lossless manner.Source: §1 · p. 2
  • In the nearly interpolating regime, expected prequential regret upper-bounds the trained parameter's description length under the algorithm-induced distribution.The paper further states that this description length yields a generalization bound in the PAC-MDL setting.Source: §1 · p. 2
  • The encoder-complexity correction in algorithm-level IB is upper-bounded by an MDL parameter description length, linking the two compression views.On CIFAR-10 and CIFAR-100, regret tracks the generalization gap with Pearson correlations of 0.9 or higher.Source: §1 · p. 2

2 Preliminary: The MDL Principle

The section introduces MDL as a coding view of learning, then contrasts a two-part code with a prequential code. The latter encodes labels using successive models trained on earlier blocks, implicitly communicating the learned model.

2 Preliminary: The MDL Principle

  • MDL evaluates a model by the combined cost of encoding the model and the data given it, with the best model achieving the highest compression.A family of distributions alone does not determine a code; a universal code induces one distribution over outcomes.Source: §2 · p. 3

2.1 The two-part encoding scheme

  • The two-part code transmits a parameter and then encodes labels under its predictive distribution, minimizing their combined description cost.For high-dimensional neural networks, choosing the discretization precision affects the trade-off, and the two-part code is generally suboptimal among universal codes.Source: §2.1 · p. 3

2.2 The prequential encoding scheme

  • The prequential code encodes each block's labels under a model trained on preceding blocks, implicitly transmitting the learned model without sending parameters.The receiver can reproduce each model from the shared protocol and decoded labels, then reconstruct the model trained on the full set.Source: §2.2 · pp. 3–4
  • Prequential regret is the excess prequential code length over the in-hindsight code length and acts as a model-complexity penalty.The analysis assumes nonnegative regret, motivated by the final model fitting the labels at least as well as intermediate models.Source: §2.2 · p. 4

3 Compression of Parameters and the Modern Information Bottleneck

The section connects parameter-level MDL compression with representation-level information bottleneck compression. It shows that the encoder-complexity correction for a learned encoder is bounded by a parameter description length.

Compression of Parameters and the Modern Information Bottleneck

  • IB defines compression at the representation level, while MDL defines it at the parameter level through whether the weights admit a short code.The encoder maps inputs to layer-l representations, and its learned form depends on the training sample.Source: §3 · p. 4
  • For a learned encoder, in-sample I(Xm; Zm) decomposes into fixed-encoder IB and encoder-complexity terms, with the latter measuring how the encoder varies with training data.The correction vanishes when the algorithm returns the same encoder on every sample.Source: §3 · p. 5
  • The encoder-complexity correction required for a learned encoder is upper-bounded by a parameter description length, connecting the MDL and IB views of compression.The bound applies to I(ϕl; S), where S is the training set and ϕl is learned from it.Source: §3 · pp. 4–5

4 Prequential Regret Bounds the Description Length of Neural Networks

The section formalizes how prequential regret can contain a description of trained parameters by distinguishing predictive likelihoods from the algorithm-induced distribution over parameters. Under the stated condition, regret upper-bounds parameter description length, including in expectation and for stochastic training.

Prequential Regret Bounds the Description Length of Neural Networks

  • In expectation, prequential regret minus the trained-model code length upper-bounds the expected description length of the trained parameter under the algorithm-induced distribution.The bound is the entropy difference H_T(θ | Xm) − H_T(θ | Xm, Ym).Source: §4 · p. 6
  • For deterministic training, expected regret is at least the conditional self-information of trained parameters under their marginal distribution given the inputs.The conditional entropy of parameters given inputs and labels is zero in this setting.Source: §4 · p. 6
  • For stochastic training, the expected parameter description-length term becomes I_T(Ym; θ | Xm), accounting for randomness in the trained parameters given the data.The paper interprets this as a bits-back description length.Source: §4 · pp. 6–7
  • The theorem’s condition requires the trained model’s likelihood of the training labels to be at least their posterior probability given the inputs and trained parameter.The paper calls this the interpolation-genericity condition; it can fail under underfitting or strong memorization.Source: §4 · pp. 6–7
  • The formal bound identifies the description length under T(θ | Xm), rather than predictive code length under Qθ, as the parameter quantity contained in prequential regret.T is induced jointly by the data-generating process and training algorithm; Xm is shared side information in this coding setup.Source: §4 · pp. 6–7

5 From Prequential Regret to Generalization

This section converts expected prequential regret into generalization guarantees through PAC-MDL for deterministic algorithms and a transductive PAC-Bayes argument for stochastic algorithms. The guarantees rely on the interpolation-genericity condition, with stochastic algorithms requiring a Gibbs-error bound.

5 From Prequential Regret to Generalization

  • The PAC-MDL setup converts description length into a high-probability test-error guarantee, using a partition-invariant prior that encodes the training partition and trained parameter.The prior over description methods may depend on the unlabeled pooled sample fixed before the random partition.Source: §5 · p. 7

5.1 Deterministic algorithms

  • For deterministic algorithms, under interpolation-genericity and finite-precision parameters, the generalization bound uses expected prequential regret to control description length.The proof combines a PAC-MDL bound with Markov's inequality; the algorithm-dependent term is computable from the training set.Source: §5.1 · p. 8

5.2 Stochastic algorithms

  • For stochastic algorithms, realized-parameter description length can exceed expected regret by up to the algorithm's intrinsic conditional entropy.PAC-MDL's pointwise code charge does not account for the bits-back term extracted by prequential coding.Source: §5.2 · p. 8
  • Replacing PAC-MDL with transductive PAC-Bayes recovers the bits-back-tight expected complexity, but bounds Gibbs test error rather than one sampled parameter's error.The posterior is T(θ | Xm, Ym), the prior is T(θ | Xm), and the bound reduces to point error in the deterministic limit.Source: §5.2 · p. 8

6 Experiments

The experiments compare prequential regret with generalization gaps across network configurations on CIFAR-10 and CIFAR-100. Regret outperforms the reported CIFAR-10 baselines and tracks the CIFAR-100 gaps in the configurations where the bound applies.

Setup

  • Prequential regret is computed from 40 geometrically growing trajectory blocks, subtracting the final model's training cross-entropy from the sequential code length.The study evaluates 540 CIFAR-10 and 99 CIFAR-100 ResNet configurations across batch size, weight decay, dropout, and seed.Source: §6 · p. 9

Results on CIFAR-10

  • Pearson 0.92 versus 0.25 on the loss gap, and 0.92 versus 0.08 on the error gap, for prequential regret versus ˇI(S; θS D+1).Prequential regret outperforms all baselines across the six rank and linear correlation columns; the table reports correlations for loss and classification-error gaps.Source: Table 1 · p. 9, §6 · p. 10

Results on CIFAR-100

  • On CIFAR-100, regret tracks loss and accuracy gaps closely on the remaining configurations, while three negative-regret outliers are severely underfit and violate interpolation-genericity.The outliers have training accuracy below 0.25; Figure 1 plots empirical prequential regret against the generalization gaps.Source: §6 · p. 10, Figure 1 · p. 10
  • CIFAR-100 evaluation is limited to 99 network configurations, and the study omits Kawaguchi et al.'s IB baselines because their post-training estimation exceeded the 48-hour compute budget.The reported CIFAR-10 IB baseline numbers come from the earlier work's matching hyperparameter and seed grid.Source: §6 · pp. 9–10

7 Conclusion

The paper presents prequential regret as a training-trajectory-only complexity measure that upper-bounds trained-parameter description length and tracks generalization gaps on CIFAR-10 and CIFAR-100. Its generalization bound is transductive, and extending it to population risk remains open.

7 Conclusion

  • Expected prequential regret upper-bounds trained-parameter description length, yields a PAC-MDL generalization bound, and tracks empirical gaps on CIFAR-10 and CIFAR-100 with Pearson correlations exceeding 0.9.The regret is computable from the training trajectory alone, and the paper relates MDL parameter compression to the algorithm-level information bottleneck correction.Source: §7 · p. 10
  • The generalization bound applies in the transductive PAC-MDL setting with a fixed finite test set; extending it to population risk remains an open problem.The authors also identify transformers and language or multimodal data as future directions, particularly where nearly-interpolating assumptions are stressed.Source: §7 · p. 10

A.1 Proof of Proposition 3.1

The appendix proves the information identity by applying the chain rule in two ways and derives the regret bound through a pointwise inequality and an expectation argument.

A.1 Proof of Proposition 3.1

  • Applying the chain rule to I(Xm; Zm, ϕl) in two orders and rearranging yields the identity in equation (3).Dropping the nonnegative conditional mutual-information term gives equation (4).Source: §A.1 · p. 13

A.2 Proof of Theorem 4.1

  • The pointwise proof of Theorem 4.1 starts by taking logarithms of inequality (6) and subtracting the prequential log probability.The supplied proof passages then identify the left-hand side with Lpreq − L̂ and rewrite the right-hand side using the algorithm-induced joint distribution.Source: §A.2 · p. 13
  • Taking expectations yields the bound by expressing expected negative log probabilities as conditional entropies and using nonnegativity of KL divergence.This establishes the expectation step of the proof from the pointwise inequality.Source: §A.2 · p. 13

A.3 Proof of Theorem 5.3

The proof combines a PAC-MDL bound under a partition-invariant prior with a Markov bound on expected description length, then uses a union bound to obtain the result with probability at least 1 − δ.

A.3 Proof of Theorem 5.3

  • The proof applies PAC-MDL to a description method that pairs a training partition π with a parameter θ, whose labeling is determined by θ.The prior is fixed before the random partition and sums to one.Source: §A.3 · pp. 13–14
  • Markov’s inequality converts the expected description-length bound into a high-probability bound on −log T(θ | Xm), under the stated deterministic assumption.The expectation is bounded by E[Lpreq − ˆL].Source: §A.3 · p. 14
  • A union bound combines the PAC-MDL and Markov events, each holding with probability at least 1 − δ/2, to give simultaneous probability at least 1 − δ.The resulting lower bound on T(θ∗ | Xm) is substituted into the PAC-MDL bound.Source: §A.3 · p. 14

A.4 Proof of Theorem 5.5

For stochastic algorithms, the proof replaces PAC-MDL with transductive PAC-Bayes, applies Markov’s inequality to a KL divergence, and combines the resulting events with a union bound.

A.4 Proof of Theorem 5.5

  • The proof parallels Theorem 5.3, but uses transductive PAC-Bayes and applies Markov’s inequality to a KL divergence rather than description length.Source: §A.4 · p. 14
  • The proof lifts each hypothesis to a pair (π, θ) and applies transductive PAC-Bayes using a prior fixed before the partition is drawn.The prior is a probability distribution; concentrating the posterior on the realized partition reduces the lifted Gibbs errors.Source: §A.4 · p. 14
  • Markov’s inequality bounds the KL divergence with high probability because its expectation, I_T(θ; Y^m | X_m), is at most E[Lpreq − ˆL].This expectation bound follows from the bits-back extension of Theorem 4.1(ii).Source: §A.4 · p. 14
  • A union bound combines the transductive PAC-Bayes and Markov events to obtain the stated result with probability at least 1 − δ.The KL decomposition lets the Markov bound be substituted into the PAC-Bayes bound.Source: §A.4 · p. 14

B.1 CIFAR-10 Experiment Details

The CIFAR-10 experiments reproduce a 540-cell protocol and add prequential coding across geometrically growing training prefixes, using the resulting regret as a predictor of generalization gaps.

B.1 CIFAR-10 Experiment Details

  • The protocol uses 15,000-image CIFAR-10 subsamples, three PreResNet architectures, and SGD with the specified schedule, weight-decay values, and batch sizes.Subsamples match the original Kawaguchi et al. RNG order bit-for-bit.Source: §B.1 · p. 15
  • Prequential coding divides each subsample into at most 40 geometrically growing blocks, coding later blocks with models trained on preceding prefixes.The first block uses a uniform class prior; subsequent blocks use tiered epoch budgets and warm-starting.Source: §B.1 · p. 15
  • The predictor is R/m = (Lpreq − ˆL)/m, evaluated against loss and error generalization gaps.Source: §B.1 · p. 15
  • The experiment uses a 540-cell grid spanning three architectures, three weight decays, three batch sizes, four seeds, and five instances; correlations include cells with training accuracy above 0.85.Source: §B.1 · p. 15

B.2 CIFAR-100 Experiment Details

These passages document the CIFAR-100 experiment’s data, training and prequential-coding setup, experiment grid, compute resources, and research-code release, alongside checklist disclosures about study scope, correlation confidence intervals, human-subject research, and LLM use.

B.2 CIFAR-100 Experiment Details

  • CIFAR-100 experiments use all 50,000 training examples and 10,000 test examples, with five ResNet depths and a prequential coding procedure.The first block uses a uniform 100-class prior; later blocks are evaluated by cross-entropy, and R/m is compared with generalization-loss and generalization-error targets. Training uses SGD with batch size 256, label smoothing 0.1, and warm-starts across blocks.Source: §B.2 · p. 15
  • The architecture, weight-decay, and dropout sweeps plus a shared anchor yield 99 CIFAR-100 experiment cells.The architecture sweep covers four additional depths; the weight-decay sweep tests nine nonzero values, and the dropout sweep uses 19 values in (0, 0.5], each with three repeats.Source: §B.2 · pp. 15–16

B.3 Computation Resources

  • CIFAR-100 runs used NVIDIA A100 GPUs, with 24-hour limits for weight-decay and dropout sweeps and 48-hour limits for the architecture sweep.Runs typically took 8–16 hours; each run was allocated four CPU cores and 16 GB host memory.Source: §B.3 · p. 16

NeurIPS Paper Checklist

  • The checklist limits empirical validation to ResNets on CIFAR-10/100 in the nearly-interpolating regime and notes that correlation values have no confidence intervals.It also states that Appendix B documents training and coding details for reproduction; the generalization bound is transductive, with a population-risk statement left open.Source: NeurIPS Paper Checklist · pp. 17–20

B.2 CIFAR-100 Experiment Details

  • The authors release code for prequential coding and the experimental pipeline, with algorithm and configuration documentation in Section 6 and Appendix B; no new datasets or pretrained models are released.The code is linked through an anonymized URL.Source: NeurIPS Paper Checklist · p. 22
  • The experiments use standard public image-classification benchmarks and do not involve crowdsourcing, human subjects, or applicable IRB review.Source: NeurIPS Paper Checklist · p. 23
  • LLMs are not part of the core methodology; any use was limited to writing or editing assistance and did not affect the scientific content.Source: NeurIPS Paper Checklist · p. 23

Related papers

Loading 2610.21376v1…