nucleation

LIT-238: Minimum Description Length Revisited

3 min read

Properties5
StatusActive — read 2026-10-14 (NOTE-760) in full; worth reading as the current map of MDL. A model is replaced by one universal distribution with small worst-case regret, NML is the minimax one with complexity (k/2) log(n/2π) + log ∫ v√|I| + o(1), estimation is penalised ML with a luckiness function, and the decade's results are collected: the switch distribution, RIPr tests, convergence of general MDL estimators, and inconsistency under misspecification. Read it knowing that it is a review whose results are cited rather than proved, that it sets aside Kolmogorov-complexity MDL, and that its "unification" of AIC with BIC and of cross-validation with Bayes is, in its own words, partial.
Version2
Tagslearning-theory, model-comparison, probabilistic-modeling, information-theory
Cited as “paper” byNOTE-198 — Minimum Description Length Revisited, NOTE-760 — Grünwald & Roos — Minimum Description Length Revisited
Cited as “source” byTHEORY-087 — The Bayesian complexity penalty grows as (d/2) log n in a regular model, where the curvature at the optimum sets the Occam factor, and as λ log n in a singular one, where λ is the real log canonical threshold; with the prior positive on the optimal set, λ falls below d/2 when that set is infinite or has a point of degenerate curvature, and equals d/2 when it is finitely many points of non-degenerate curvature

Graph View

Peter Grünwald, Teemu Roos (2019), International Journal of Mathematics for Industry 11(1):1930001 (2019) — ARXIV-1908.08484

Key takeaways

From the reading, NOTE-760.

  • One distribution per model. MDL scores a model by a single universal distribution p̄. Because it sums to one, p̄ cannot fit every sample well, and that is the guard against overfitting. The kinds are Bayes, NML, two-part, prequential plug-in, switch and RIPr.
  • NML is the minimax choice. p̄_nml,v(zⁿ) ∝ max_θ p_θ(zⁿ)v(θ) uniquely maximises the worst-case fitness ratio. With v ≡ 1 it is the minimax-regret predictor, and comp(M; v) is the minimax regret. NML is undefined with v ≡ 1 for most models on unbounded outcome spaces.
  • The penalty. comp(M; v) = (k/2) log(n/2π) + log ∫ v(θ)√|I(θ)| dθ + o(1) for exponential families (Suzuki & Yamanishi 2018). Bayes with the generalised Jeffreys prior matches it asymptotically. Every standard universal code pays (k/2) log n + O(1) on regular data.
  • Estimation is penalised ML. θ̂_v = argmax p_θ(zⁿ)v(θ). Joint MDL over model and parameter selects the same model as meta-NML. Two-part codes have no special status (Grünwald & Mehta 2019).
  • Recent universal codes.
    • The switch distribution is strongly consistent and prediction-optimal within O(log log n). It “almost” resolves the AIC–BIC dilemma, which Yang (2005) shows cannot be resolved exactly.
    • The RIPr makes likelihood-ratio tests of composite nulls safe under optional continuation.
  • Frequentist guarantees and their limit. General MDL estimators are consistent when a generalised complexity comp_η, η < 1, grows as o(n). Under misspecification, MDL and Bayes can be inconsistent, or choose arbitrarily bad models for fairly large n. Tempering the likelihood (η < 1) repairs this.
  • Deep learning (§6.4). Flat minima need fewer bits, and PAC-Bayes bounds give that a precise frequentist form. The review cites this and calls it one of several explanations.

Standing in the record

Filed on 2026-09-26 at the owner’s request, from a list they grouped under the heading Relating K-complexity to minimum sufficient statistics. Read on 2026-10-14 in NOTE-760. It is the record’s reference for statistical MDL. LIT-623 named it as such while it was unread. It does not serve the heading it was filed under. It sets Kolmogorov-complexity MDL aside, and it mentions the structure function only in pointing to Rissanen’s later programme.

No THEORY is filed. The review cites its results and proves none. Its (k/2) log n penalty with the Fisher-volume constant adds a second, description-length source for the regular half of THEORY-087. Its singular-model formula (31) quotes the same λ log n leading term from Watanabe (LIT-616). Its §6.3, on inconsistency under misspecification, is a ground for caution about Bayes-factor thresholds that CLAIM-188 does not yet name (NOTE-760, Bearing on the record). The companion readings on Kolmogorov-complexity MDL are LIT-225 and LIT-239.

Access when seeded: arXiv abs page (v1 2019-08-21 submitted by Roos, v2 2019-12-18) and v2 PDF read for §1 (pp. 1–3), section heads, §6.4 and §7 (pp. 28–30). Crossref for the journal record (article 1930001, issue dated 2019-12, online 2020-03-12). The journal version was not read.

Backlinks