Research map / Learning theory and algorithms / Prediction and decision losses

Prediction Under Imperfect Compression: A Theory of Approximate MDL

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Consistency of surrogate losses · 0 citations (OpenAlex)

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.

Shows that approximate MDL prediction with additive slack C remains reliable (finite cumulative squared error) for regularization λ≥1 but fails for λ<1, and that multiplicative approximation fails for all λ>0.

Problem

When does approximately minimizing the (regularized) MDL objective still yield reliable sequential prediction? Exact MDL prediction guarantees are known, but practical optimization only yields approximate minimizers.

Approach

Treats approximate MDL selection with additive slack C as a likelihood-ratio threshold event problem; an affinity-telescoping argument (lambda>1) and a likelihood-ratio stopping argument based on exact static MDL (lambda=1) bound cumulative expected squared error, with sharp counterexamples for lambda<1 and for multiplicative approximation.

Key results

• For additive slack C and lambda>=1, every additive-C Approx-MDL predictor has cumulative expected squared error at most 16 K_PH lambda 2^{C/lambda} w_mu^{-1} (K_PH=21 from static MDL bound).
• For lambda in (0,1), there is an additive-C selector on the fair-coin true environment with cumulative expected squared error +infinity (constant per-step loss 1/2).
• For multiplicative (1+eps) approximation, there is a valid selector with infinite cumulative error for every lambda>0 and eps>0.

Surprising findings

• Additive slack is safe at lambda=1 while small regularization (lambda<1) allows pointwise overfitting that yields constant per-step error forever.
• Multiplicative approximation can fail for any lambda>0 because its tolerance grows with the optimal score, admitting systematically wrong models.

Limitations

• Results are worst-case over selectors; they do not show typical behavior of practical optimizers.
• Positive results assume realizability (true measure in the countable class) and the universal class is uncomputable, so not directly implementable.
• No empirical experiments on practical ML models.

Experimental setup

Metrics: cumulative expected squared prediction error

Baselines: exact MDL predictor multiplicative approximate MDL

Builds on: exact MDL prediction theory (Poland-Hutter static MDL bounds) Solomonoff-style universal induction Milovanov best-explanation predictor Hutter monotone-complexity prediction

Closest papers by meaning

• Does Compression Imply Generalization? A Minimum Description Length Perspective (NeurIPS 2026 · similarity 0.85)
• Unified Scaling Laws for Compressed Representations (NeurIPS 2025 · similarity 0.83)
• Length Optimization in Conformal Prediction (NeurIPS 2024 · similarity 0.83)
• Agnostic Sample Compression Schemes for Regression (ICML 2024 · similarity 0.82)
• Symbolic regression via MDLformer-guided search: from minimizing prediction error to minimizing description length (ICLR 2025 · similarity 0.82)
• CBMA: Improving Conformal Prediction through Bayesian Model Averaging (ICLR 2025 · similarity 0.82)