Symptom

You fit a model. It scores 94% on training data and 71% on held-out data.

So you simplify: fewer parameters, more regularization. Training drops to 88%, held-out rises to 84%. You simplify further and both drop. Somewhere in there was an optimum, and you found it by trial and error, with a validation set and patience.

Everyone tells you to prefer the simpler model. Occam’s razor, they say, as if citing a medieval friar settles a question about polynomial degree. But nobody tells you what “simpler” means quantitatively, and without that the advice is unfalsifiable. Simpler in parameters? In description? In computation? A degree-9 polynomial with small coefficients and a degree-3 polynomial with huge ones — which is simpler, and why should the answer have anything to do with predicting new data?

MDL answers this. Simplicity is compression, the units are bits, and the tradeoff stops being a matter of taste.

Statement

Minimum description length principle. The best model for a dataset is the one minimizing the total description length of model plus data given model:

$$\min_{M} \; \left[ L(M) + L(D \mid M) \right]$$

$L(M)$ is the bits to describe the model; $L(D \mid M)$ is the bits to describe the data using that model as a codebook. Learning is compression, and the best hypothesis is the one that makes the shortest total message.

The two terms pull against each other and that is the point. A complex model fits tightly and costs little to encode residuals — small $L(D \mid M)$, large $L(M)$. The empty model costs nothing to state and forces you to transmit the data raw. Neither extreme wins, and overfitting is exactly the case where the model costs more bits than it saves.

Two connections make this more than a slogan. Via Kolmogorov complexity (T023), $L(M) + L(D \mid M)$ approximates $K(D)$, so MDL is a computable stand-in for “the shortest program generating this data.” Via Shannon (T018), the optimal code length for data under a probabilistic model is $-\log_2 P(D \mid M)$ bits, so minimizing description length is minimizing

$$-\log_2 P(D \mid M) - \log_2 P(M)$$

which is exactly maximum a posteriori estimation. MDL and Bayesian model selection are the same computation in different units: a prior is a code, and a code is a prior.

Argument

Why the code-length view is forced. Shannon’s source coding theorem says that for a distribution $P$, the optimal codeword for outcome $x$ has length $-\log_2 P(x)$ bits, achievable to within one bit (T018, T020). Probabilities and code lengths are interchangeable. Any probabilistic model is a compression scheme and any compression scheme is a probabilistic model, so the question “which model” and the question “which encoding” are one question.

The two-part code, worked. Suppose you have 1000 points and are choosing a polynomial degree.

  • Model cost. A degree-$d$ polynomial has $d+1$ coefficients. At $b$ bits each, $L(M) = (d+1)b$. There is a classical result that the right precision is about $\frac{1}{2}\log_2 n$ bits per parameter — finer precision costs more than it saves, since the estimation error already swamps it. At $n = 1000$ that is about 5 bits per parameter.
  • Data cost. With Gaussian residuals of standard deviation $\sigma$, encoding $n$ residuals costs about $\frac{n}{2}\log_2(2\pi e \sigma^2)$ bits. Halving $\sigma$ saves exactly $n$ bits — one bit per point.

So each added parameter costs $\frac{1}{2}\log_2 n$ bits and is worth it only if it reduces residual entropy by more. That is the whole tradeoff in one sentence, and it is quantitative.

Now the numbers. Adding a parameter at $n = 1000$ costs about 5 bits. To pay for itself it must shrink $\sigma$ by a factor of $2^{5/1000} = 1.0035$ — a 0.35% reduction in residual scale. That is a small bar, which is correct: with a thousand points you can afford parameters. At $n = 20$, the cost is $\frac{1}{2}\log_2 20 = 2.16$ bits, and the required shrinkage is $2^{2.16/20} = 1.078$, nearly 8%. The same parameter must earn twenty times as much on small data. MDL derives the folk rule that small datasets demand simple models, rather than asserting it.

Where AIC and BIC come from. Take the two-part code with $\frac{1}{2}\log_2 n$ bits per parameter, convert from bits to nats, and multiply by two:

$$-2\ln P(D \mid \hat\theta) + k \ln n$$

That is BIC exactly. The Bayesian Information Criterion is the two-part MDL code in different clothing, which is why BIC’s $\ln n$ penalty grows with sample size while AIC’s constant $2k$ does not. AIC estimates prediction error, BIC and MDL estimate description length, and they disagree because they are answering different questions — AIC does not assume the true model is in your candidate set, BIC does. Knowing which you want stops the endless AIC-versus-BIC argument.

The crude code’s weakness, and the fix. $L(M)$ depends on how you choose to encode models, and different encodings give different winners. That arbitrariness is real, and it is why naive MDL is unsatisfying. Modern refined MDL removes the choice using the normalized maximum likelihood distribution: encode the data with the code that minimizes worst-case regret against the best model in the class. The resulting complexity term — the parametric complexity — depends on the model class’s geometry rather than on your arbitrary parameterization. That is the version worth learning, and Grünwald’s tutorial is where.

Why compression predicts. Compression is only possible by finding regularity; regularity is what persists in new data. A model compressing your data has found structure, and structure generalizes while noise does not. This is the intuition behind Solomonoff induction, and MDL is its computable approximation.

Forbids

Model selection by training fit alone. Training likelihood always improves with parameters, so it cannot select. Something must price complexity, and MDL says the price is in bits.

Free lunch from complexity. Every parameter costs. A model must earn its bits through improved data compression or it loses, and this is not a heuristic but an accounting identity.

The idea that “simplicity” is subjective here. Once you fix a description language, simplicity is a number. Language choice still matters, but it shifts everything by a constant (T023), not arbitrarily.

Comparing models across different data encodings. Both terms must be in the same units on the same data, or the comparison is meaningless. This is the commonest way MDL is misapplied.

Does not forbid

It does not say big models cannot generalize, and modern deep learning is the loud counterexample. GPT-scale networks have hundreds of billions of parameters and generalize well past the point classical complexity penalties predict disaster. The resolution is that parameter count is a terrible proxy for description length: trained networks are massively compressible — pruning and 8-bit or 4-bit quantization routinely shrink them by an order of magnitude with little loss — and implicit regularization from SGD keeps the effective description short. Double descent, where test error falls again past the interpolation threshold, is the empirical shape of this. MDL is not refuted; the naive counting proxy is.

It does not make cross-validation obsolete. CV is the workhorse and usually the right default, since it needs no coding scheme and directly estimates what you care about. MDL is most valuable where CV is awkward: tiny datasets, time series where splitting breaks dependence, and online settings with no held-out set.

It does not force the simplest model always. MDL selects the model with the best total, and on large data that is often a large model. “Prefer simplicity” is a consequence of the accounting under scarce data, not an axiom.

It does not mean regularization is just MDL in disguise, though the correspondence is exact where it holds. L2 regularization is a Gaussian prior and hence a code; L1 is Laplace and induces sparsity because zeros are cheap to encode. Dropout and batch normalization have no such clean description-length reading, and pretending otherwise is retrofitting.

It does not require your model class to contain the truth. Refined MDL is explicitly a worst-case-regret criterion relative to the class you brought, which makes it usable when you know your model is wrong — which is always.

Boundary

  • The coding scheme is a modelling choice. Crude two-part MDL is only as good as your encoding of models. Refined MDL and NML remove the arbitrariness at real computational cost, since the parametric complexity integral is often intractable.
  • Bayes is the same thing in probability units. $-\log P(M)$ is $L(M)$. Choosing a prior is choosing a code, and people who find priors philosophically troubling but code lengths obvious should notice they have committed to the same object.
  • Solomonoff induction is the ideal limit. Weight hypotheses by $2^{-K}$ and you dominate every computable predictor, uncomputably. MDL is what you do instead, and the gap is exactly T023’s uncomputability.
  • Compression as a benchmark. The Hutter Prize pays for compressing a Wikipedia snapshot, on the thesis that better compression is better understanding. Large language models are now evaluated by bits-per-byte, which is the same measurement — this connection is not metaphorical.
  • Where it feeds forward. PAC learning (T096) prices hypothesis-class complexity by VC dimension instead of description length. Both bound generalization by a complexity term; MDL’s is in bits and VC’s is combinatorial, and the two agree qualitatively about what makes a class safe.