Prediction Under Imperfect Compression: A Theory of Approximate MDL

Guangxu Yang; Qian Li; Shang-Hua Teng; Xinyu Mao

arxiv: 2606.04834 · v1 · pith:IK4QGLH6new · submitted 2026-06-03 · 💻 cs.LG

Prediction Under Imperfect Compression: A Theory of Approximate MDL

Qian Li , Xinyu Mao , Shang-Hua Teng , Guangxu Yang This is my paper

Pith reviewed 2026-06-28 06:56 UTC · model grok-4.3

classification 💻 cs.LG

keywords approximate MDLsequential predictioncumulative squared erroradditive approximationregularization parameter lambdaminimum description lengthmodel selection failure

0 comments

The pith

Approximate MDL with any fixed additive slack C still yields finite cumulative expected squared prediction error for all regularization parameters λ at least 1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies whether imperfect optimization of the minimum description length criterion can preserve reliable sequential prediction. It establishes that an additive approximation error bounded by a constant C, rather than a multiplicative factor, keeps the total expected squared error finite whenever the balance parameter λ satisfies λ ≥ 1. The argument splits into an affinity-telescoping sum for λ > 1 and a likelihood-ratio stopping time for the boundary λ = 1, both relying on exact MDL bounds. The characterization is shown to be tight because weaker regularization or multiplicative approximations permit divergence of the error even over the class of estimable measures.

Core claim

The paper proves that for any approximation with additive slack C of the balanced MDL objective λ·L(model)+L(data | model), the cumulative expected squared prediction error is finite for all λ≥1. The case λ>1 is proved by an affinity-telescoping argument, while λ=1 uses a likelihood-ratio stopping argument based on exact static MDL bounds. The results establish that classical MDL regularization remains robust to any fixed additive optimization error, while showing that model selection may fail for every λ>0 under multiplicative approximation and that overfits producing infinite error occur when 0<λ<1.

What carries the argument

The balanced MDL objective λ·L(model)+L(data | model) minimized under additive approximation slack C to select the next model in sequential prediction.

If this is right

Any fixed additive optimization error leaves cumulative squared prediction error finite when λ ≥ 1.
For 0 < λ < 1 overfits can produce infinite cumulative expected error in the class of estimable measures.
Multiplicative approximations allow model selection to fail for every positive λ.
Strong model-complexity regularization is necessary even when optimization is imperfect.
Additive approximation is both sufficient and essential for the positive guarantee.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practical MDL-based predictors may tolerate constant optimization inaccuracies without losing finite-error guarantees.
The distinction between additive and multiplicative error could apply to other online model-selection criteria that trade description length against fit.
Testing the boundary λ=1 case with controlled additive noise in simulated data streams would directly probe the stopping-time argument.
The result suggests examining whether similar additive-error robustness holds for non-squared loss functions in sequential settings.

Load-bearing premise

The approximation error must be a fixed additive constant independent of the model chosen.

What would settle it

A concrete construction of an additive approximation with slack C for which the cumulative expected squared error diverges at λ=1 over a universal class of estimable measures would falsify the claim.

read the original abstract

Minimum Description Length (MDL) formalizes the principle of Occam's razor by optimizing the total description length: $L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$. For sequential prediction, the MDL method repeatedly selects a model with a minimum objective score of the observed prefix for the next step prediction. Classical MDL prediction theory shows that exact optimization of the MDL objective indeed provides a strong compression guarantee that supports reliable prediction. However, practical machine learning usually can only find models by approximately optimizing the objective function. To bridge this gap, this paper addresses the following fundamental question: Under what forms of approximation and regularization does approximate MDL still guarantee reliable sequential prediction? This work offers a principled characterization. We prove that for any approximation with additive slack $C$ of the more general form of the balanced MDL objective: $\lambda\cdot L(\mathrm{model})+L(\mathrm{data} \ | \ \mathrm{model})$, the cumulative expected squared prediction error is finite for all $\lambda\ge1$. The case $\lambda>1$ is proved by an affinity-telescoping argument, while the boundary case $\lambda=1$ is proved by a likelihood-ratio stopping argument based on exact static MDL bounds. Our results establish that classical MDL regularization remains robust to any fixed additive optimization error. Furthermore, we establish that our characterization of the approximate MDL framework is sharp: When $0<\lambda<1$, overfits can happen to incur infinite cumulative expected error in the universal class of estimable measures, and hence a strong form of model-complexity regularization is necessary. In addition, model selection may fail in every regularized regime $\lambda >0$, under multiplicative approximation, and thus, additive approximation is both sufficient and essential.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows additive slack in approximate MDL keeps cumulative squared prediction error finite for λ ≥ 1, with clean necessity results for the boundaries.

read the letter

The main result is that any fixed additive slack C in the objective λ L(model) + L(data|model) still yields finite cumulative expected squared prediction error when λ ≥ 1. They handle λ > 1 via affinity-telescoping and λ = 1 via a likelihood-ratio stopping argument that leans on exact static MDL bounds.

This is new. Prior MDL prediction theory required exact minimization; the paper isolates the exact conditions on the approximation form and the regularization strength that preserve the guarantee, and demonstrates both are necessary.

The work does a few things cleanly. The positive claims rest on classical tools (telescoping sums, stopping times) without circularity or new parameters. The counterexamples for multiplicative slack and for λ < 1 are stated explicitly in the universal class of estimable measures, so the characterization is sharp rather than one-sided.

The soft spot is that only the abstract is available here, so the concrete steps in the affinity-telescoping argument and the precise invocation of static bounds at λ = 1 cannot be checked for hidden restrictions on the model class. Nothing in the high-level structure suggests a load-bearing gap, but that remains to be verified.

This is for people working on sequential prediction, online learning, and compression-based methods who want to know how much optimization error they can tolerate. A reader who needs precise conditions on approximate MDL will find the separation between additive and multiplicative cases useful.

I would send it to peer review. The claim is concrete, the necessity results are stated, and the result directly addresses a practical gap between theory and implementation.

Referee Report

0 major / 2 minor

Summary. The paper develops a theory for approximate MDL in sequential prediction. It proves that any additive approximation with fixed slack C to the balanced objective λ·L(model) + L(data|model) yields finite cumulative expected squared prediction error for all λ ≥ 1, using an affinity-telescoping argument for λ > 1 and a likelihood-ratio stopping argument based on exact static MDL bounds for λ = 1. The characterization is shown to be sharp: λ < 1 permits overfitting with infinite error in the universal class of estimable measures, and multiplicative approximations cause model selection to fail for every λ > 0.

Significance. If the results hold, the work provides a principled bridge between classical exact MDL theory and practical approximate optimization, showing that fixed additive slack preserves the compression-based prediction guarantees while multiplicative slack does not. The explicit counterexamples establishing necessity of both the additive form and λ ≥ 1, together with the use of standard telescoping and stopping-time arguments, constitute a clean and falsifiable contribution to the literature on Occam's razor in learning.

minor comments (2)

[Abstract] Abstract and §1: the phrase 'balanced MDL objective' is used before its formal definition; a forward reference or one-sentence gloss would improve readability for readers outside the MDL community.
[Introduction] The statement that the approximation error is 'model-independent' (additive slack C) is load-bearing; a brief remark in the introduction on why this is the natural model of 'imperfect compression' (as opposed to, e.g., model-dependent slack) would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The referee's description of the results accurately captures the contributions regarding additive approximations to the balanced MDL objective and the necessity of λ ≥ 1.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's central results establish finite cumulative expected squared prediction error under additive slack C for λ ≥ 1, using an affinity-telescoping argument for λ > 1 and a likelihood-ratio stopping argument based on exact static MDL bounds for λ = 1. These rest on classical MDL prediction theory and standard probabilistic tools (telescoping sums, stopping times) that are independent of the approximation result itself. The paper separately demonstrates necessity by counterexamples for λ < 1 and for multiplicative approximations, but these are external falsifications rather than self-referential definitions. No fitted parameters are renamed as predictions, no self-citation chains bear the load of the uniqueness or core bounds, and no ansatz is smuggled in. The derivation chain does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on the standard definition of description length, the existence of a universal class of estimable measures for the negative result, and classical properties of likelihood ratios and stopping times; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

standard math Description length functions satisfy the usual Kraft inequality and prefix-free properties
Invoked when defining the MDL objective and when applying exact static MDL bounds.
domain assumption There exists a universal class of estimable probability measures in which over-fitting can produce infinite cumulative error
Used to establish sharpness for λ<1.

pith-pipeline@v0.9.1-grok · 5867 in / 1496 out tokens · 27427 ms · 2026-06-28T06:56:17.477730+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 10 canonical work pages

[1]

Léonard Blier and Yann Ollivier

doi: 10.1109/TIT.2008.2008152. Léonard Blier and Yann Ollivier. The description length of deep learning models. InAdvances in Neural Information Processing Systems 31, pages 2220–2230,

work page doi:10.1109/tit.2008.2008152 2008
[2]

Gustavo L Gilardoni

doi: 10.1109/18.945257. Gustavo L Gilardoni. On pinsker’s and vajda’s type inequalities for csiszár’sf-divergences.IEEE Transactions on Information Theory, 56(11):5377–5386,

work page doi:10.1109/18.945257
[3]

ISBN 9780262529631. Peter D. Grünwald and Steven de Rooij. Asymptotic log-loss of prequential maximum likelihood codes. InLearning Theory: 18th Annual Conference on Learning Theory, COLT 2005, volume 3559 ofLecture Notes in Computer Science, pages 652–667. Springer,

2005
[4]

Geoffrey E

doi: 10.1007/11503415_44. Geoffrey E. Hinton and Drew van Camp. Keeping the neural networks simple by minimizing the description length of the weights. InProceedings of the Sixth Annual Conference on Computational Learning Theory, pages 5–13,

work page doi:10.1007/11503415_44
[5]

Marcus Hutter

doi: 10.1145/168304.168306. Marcus Hutter. Sequence prediction based on monotone complexity. InLearning Theory and Kernel Machines, volume 2777 ofLecture Notes in Computer Science, pages 506–521. Springer,

work page doi:10.1145/168304.168306
[6]

Marcus Hutter

doi: 10.1007/978-3-540-45167-9_37. Marcus Hutter. Discrete MDL predicts in total variation. InAdvances in Neural Information Processing Systems 22, pages 817–825,

work page doi:10.1007/978-3-540-45167-9_37
[7]

Marvin Minsky

doi: 10.1007/s00224-024-10180-0. Marvin Minsky. Remarks in panel discussion: The Limits of Understanding. World Science Festival, New York City, June

work page doi:10.1007/s00224-024-10180-0
[8]

URLhttps://www.worldsciencefestival.com/videos/ the-limits-of-understanding/. Video. Accessed: 2026-05-02. Jan Poland and Marcus Hutter. Asymptotics of discrete MDL for online prediction.IEEE Transactions on Information Theory, 51(11):3780–3795,

2026
[9]

Jorma Rissanen

doi: 10.1109/TIT.2005.856956. Jorma Rissanen. Modeling by shortest data description.Automatica, 14(5):465–471,

work page doi:10.1109/tit.2005.856956 2005
[10]

Rissanen , keywords =

doi: 10.1016/0005-1098(78)90005-5. Jorma Rissanen.Stochastic complexity in statistical inquiry, volume

work page doi:10.1016/0005-1098(78)90005-5
[11]

Yuzhou Cao, Hussein Mozannar, Lei Feng, Hongxin Wei, and Bo An

doi: 10.1109/TIT. 2004.838346. Paul M. B. Vitányi and Ming Li. Minimum description length induction, bayesianism, and kolmogorov complexity.IEEE Transactions on Information Theory, 46(2):446–464,

work page doi:10.1109/tit 2004
[12]

12 A Full proofs for additive Approx-MDL Proof of Lemma 2.3.Fix α∈(0, 1)

doi: 10.1109/18.825807. 12 A Full proofs for additive Approx-MDL Proof of Lemma 2.3.Fix α∈(0, 1). We first prove the following scalar inequality: for every x,y∈[0,1], (1−α)x+αy−x1−αyα≥α(1−α) 2 (x−y)2.(5) Ifx=y= 0, the claim is immediate. Otherwise set M:= max{x,y}∈(0,1], x=Ma, y=Mb. Thena,b∈[0,1]andmax{a,b}=

work page doi:10.1109/18.825807
[13]

LettingT→∞and using monotone convergence gives ∑ t≥1 EP [Rtdα t (P,Q)]≤1

Thus, T∑ t=1 EP [Rtdα t (P,Q)]≤1. LettingT→∞and using monotone convergence gives ∑ t≥1 EP [Rtdα t (P,Q)]≤1. Next, on the event{Lt≥c}, 1{Lt≥c}≤c−αLα t =c−αRt. By Lemma 2.3, for every historyX<t, ∑ a∈X (pa−qa)2≤ 2 α(1−α)dα t (P,Q). Therefore, EP ∑ t≥1 1{Lt≥c} ∑ a∈X ( P(a|X<t)−Q(a|X<t) )2 ≤ 2 α(1−α)EP ∑ t≥1 1{Lt≥c}dα t (P,Q) ≤ 2 α(1−α)c−α∑ t≥1 EP [Rtdα t (P,...

2005
[14]

Let τ:= inf{t≥1 :Lt≥c}be the first threshold-crossing time

15 Proof. Let τ:= inf{t≥1 :Lt≥c}be the first threshold-crossing time. Ifτ=∞, the thresholded loss is zero. Condition on{τ <∞}and on X<τ= x. Let Px and Qx be the conditional continuation measures after historyx. For a future stringy, Qx(y) Px(y) = Q(xy)/Q(x) P(xy)/P(x) = Lτ+ℓ(y) Lτ . Therefore the rule that usesQ exactly whenLτ+ℓ(y)≥cis equivalent to exact...

2005

[1] [1]

Léonard Blier and Yann Ollivier

doi: 10.1109/TIT.2008.2008152. Léonard Blier and Yann Ollivier. The description length of deep learning models. InAdvances in Neural Information Processing Systems 31, pages 2220–2230,

work page doi:10.1109/tit.2008.2008152 2008

[2] [2]

Gustavo L Gilardoni

doi: 10.1109/18.945257. Gustavo L Gilardoni. On pinsker’s and vajda’s type inequalities for csiszár’sf-divergences.IEEE Transactions on Information Theory, 56(11):5377–5386,

work page doi:10.1109/18.945257

[3] [3]

ISBN 9780262529631. Peter D. Grünwald and Steven de Rooij. Asymptotic log-loss of prequential maximum likelihood codes. InLearning Theory: 18th Annual Conference on Learning Theory, COLT 2005, volume 3559 ofLecture Notes in Computer Science, pages 652–667. Springer,

2005

[4] [4]

Geoffrey E

doi: 10.1007/11503415_44. Geoffrey E. Hinton and Drew van Camp. Keeping the neural networks simple by minimizing the description length of the weights. InProceedings of the Sixth Annual Conference on Computational Learning Theory, pages 5–13,

work page doi:10.1007/11503415_44

[5] [5]

Marcus Hutter

doi: 10.1145/168304.168306. Marcus Hutter. Sequence prediction based on monotone complexity. InLearning Theory and Kernel Machines, volume 2777 ofLecture Notes in Computer Science, pages 506–521. Springer,

work page doi:10.1145/168304.168306

[6] [6]

Marcus Hutter

doi: 10.1007/978-3-540-45167-9_37. Marcus Hutter. Discrete MDL predicts in total variation. InAdvances in Neural Information Processing Systems 22, pages 817–825,

work page doi:10.1007/978-3-540-45167-9_37

[7] [7]

Marvin Minsky

doi: 10.1007/s00224-024-10180-0. Marvin Minsky. Remarks in panel discussion: The Limits of Understanding. World Science Festival, New York City, June

work page doi:10.1007/s00224-024-10180-0

[8] [8]

URLhttps://www.worldsciencefestival.com/videos/ the-limits-of-understanding/. Video. Accessed: 2026-05-02. Jan Poland and Marcus Hutter. Asymptotics of discrete MDL for online prediction.IEEE Transactions on Information Theory, 51(11):3780–3795,

2026

[9] [9]

Jorma Rissanen

doi: 10.1109/TIT.2005.856956. Jorma Rissanen. Modeling by shortest data description.Automatica, 14(5):465–471,

work page doi:10.1109/tit.2005.856956 2005

[10] [10]

Rissanen , keywords =

doi: 10.1016/0005-1098(78)90005-5. Jorma Rissanen.Stochastic complexity in statistical inquiry, volume

work page doi:10.1016/0005-1098(78)90005-5

[11] [11]

Yuzhou Cao, Hussein Mozannar, Lei Feng, Hongxin Wei, and Bo An

doi: 10.1109/TIT. 2004.838346. Paul M. B. Vitányi and Ming Li. Minimum description length induction, bayesianism, and kolmogorov complexity.IEEE Transactions on Information Theory, 46(2):446–464,

work page doi:10.1109/tit 2004

[12] [12]

12 A Full proofs for additive Approx-MDL Proof of Lemma 2.3.Fix α∈(0, 1)

doi: 10.1109/18.825807. 12 A Full proofs for additive Approx-MDL Proof of Lemma 2.3.Fix α∈(0, 1). We first prove the following scalar inequality: for every x,y∈[0,1], (1−α)x+αy−x1−αyα≥α(1−α) 2 (x−y)2.(5) Ifx=y= 0, the claim is immediate. Otherwise set M:= max{x,y}∈(0,1], x=Ma, y=Mb. Thena,b∈[0,1]andmax{a,b}=

work page doi:10.1109/18.825807

[13] [13]

LettingT→∞and using monotone convergence gives ∑ t≥1 EP [Rtdα t (P,Q)]≤1

Thus, T∑ t=1 EP [Rtdα t (P,Q)]≤1. LettingT→∞and using monotone convergence gives ∑ t≥1 EP [Rtdα t (P,Q)]≤1. Next, on the event{Lt≥c}, 1{Lt≥c}≤c−αLα t =c−αRt. By Lemma 2.3, for every historyX<t, ∑ a∈X (pa−qa)2≤ 2 α(1−α)dα t (P,Q). Therefore, EP ∑ t≥1 1{Lt≥c} ∑ a∈X ( P(a|X<t)−Q(a|X<t) )2 ≤ 2 α(1−α)EP ∑ t≥1 1{Lt≥c}dα t (P,Q) ≤ 2 α(1−α)c−α∑ t≥1 EP [Rtdα t (P,...

2005

[14] [14]

Let τ:= inf{t≥1 :Lt≥c}be the first threshold-crossing time

15 Proof. Let τ:= inf{t≥1 :Lt≥c}be the first threshold-crossing time. Ifτ=∞, the thresholded loss is zero. Condition on{τ <∞}and on X<τ= x. Let Px and Qx be the conditional continuation measures after historyx. For a future stringy, Qx(y) Px(y) = Q(xy)/Q(x) P(xy)/P(x) = Lτ+ℓ(y) Lτ . Therefore the rule that usesQ exactly whenLτ+ℓ(y)≥cis equivalent to exact...

2005