A network generalizes only when its weights are cheaper to describe than the data they explain.
Before “regularization” meant dropout or grid-searched weight decay, this 1993 paper reframed overfitting as a coding problem. Imagine a sender who must transmit a trained network plus the training data to a receiver. The total bill has two parts: the bits to describe the weights, and the bits to describe the mistakes the network still makes. The Minimum Description Length principle says: pick the network that makes that total bill smallest.
The surprising move is to make the weights noisy on purpose. A weight that is allowed to wobble carries less information, so it is cheaper to send. The paper's “bits-back” argument then shows that the apparent waste of sending random, wobbly weights is partly refunded — and the true cost works out to exactly a variational bound, the same identity that variational autoencoders would lean on two decades later.
Don't ask how accurate the weights are. Ask how many bits it takes to describe them — and let the data pay only for what it truly needs.
The coding view
Why overfitting is really a problem about bits
Step 1 · A sender, a receiver, a bill
To learn well is to transmit the data using as few bits as possible.
Here is the whole idea in one picture. Imagine a sender who has seen both the training inputs and their correct outputs, and a receiver who has seen only the inputs. The sender's job: make the receiver able to reproduce the correct outputs exactly. To do that she trains a network, ships its weights, and then — because the network is never perfect — also ships the leftover mistakes (the gap between the network's output and the true answer on each case).
The Minimum Description Length (MDL) principle (Rissanen, 1986) names the winner: the best model is the one that minimizes the combined cost of describing the model and describing the data's misfit to it. Fancier networks fit the training data better, shrinking message 2 — but they take more bits to describe, swelling message 1. Generalization is whatever balances the two.
That reframing is the quiet payload of this paper. It is not a benchmark win; it is a way of thinking. A network generalizes, the abstract says, exactly when there is much less information in the weights than in the outputs they explain.
One bill, two messages: bits for the weights plus bits for the misfits. Every later trick in this paper is a cleverer way to make that total smaller — and that, not accuracy alone, is what controls overfitting.
From the abstract: “Supervised neural networks generalize well if there is much less information in the weights than there is in the output vectors of the training cases.”
Step 2 · The cost of the mistakes
Squared error isn't an arbitrary choice — it's the bit-cost of the mistakes.
You've met the two-message bill. Take message 2 first — the mistakes — because pricing it reveals something familiar hiding inside MDL.
How many bits does it cost to send one mistake? Coding theory gives a
clean rule: if sender and receiver have agreed on a probability
distribution over possible mistakes, a mistake with probability
p costs −log p bits. Rare mistakes are
expensive; likely ones are cheap. So we just need a distribution over the
misfits. The natural pick is a zero-mean Gaussian — small errors
are likely, large ones rare — narrow tube of width t for the
fine quantization:
Read the bell literally. A misfit out in the tail has tiny probability,
so −log p is large — it costs a lot of bits. The log of a
Gaussian's height is proportional to the square of how far you are
from the mean. Sum that bit-cost over all training cases and the
distance-dependent part is exactly the sum of squared
errors you already minimize:
Cmisfit=kN+N2log[mean (d − y)²]
k depends only on the quantization width t · so minimizing description length = minimizing squared error (Eq. 3)
The everyday squared-error loss isn't a modelling whim — it's the MDL bit cost of the mistakes under a Gaussian assumption. This same Gaussian-as-a-code idea, applied next to the weights, is the whole engine of the paper.
The coding theorem: a misfit with assumed probability p costs
−log p bits (nats here — units of log e). For a
zero-mean Gaussian of width σ, that is a constant plus
(d − y)² / 2σ² per case (Eqs. 1–3).
Step 3 · The crude fix is plain weight-decay
Code the weights the same way, and out pops ordinary weight-decay.
Squared error already prices the mistakes. Now apply the exact same Gaussian-as-a-code trick to the other message — the weights — and something you already know falls out for free.
Assume the trained weights are drawn from a zero-mean Gaussian of width
σw. By the same argument as the misfits, the bits
to describe a weight are proportional to its square. Add the two
messages and you get one cost to minimize:
C=Σ (d − y)²2σj²+Σ w²2σw²
left term = squared error (message 2) · right term = squared weights (message 1) · Eq. 4
Look at the right-hand term: it penalizes the sum of squared weights.
That is weight-decay — the standard trick of
shrinking weights toward zero. So weight-decay isn't a hack; it is the
crudest possible MDL code, with both Gaussian widths
fixed in advance. The ratio σj² / σw²
is precisely the weight-decay coefficient you'd otherwise tune by hand.
But this code has a serious flaw. It assumes every weight is described to the same precision, set tight by σw. That charges full price for the exact value of every weight — even weights the network barely cares about. A network is far cheaper to describe if the don't-care weights can be left imprecise. Fixing that is the heart of the paper.
Plain weight-decay pays for the height of each weight's probability but ignores its precision (how tightly it's pinned down). Spending bits to nail down a weight that doesn't matter is waste. Part B buys that precision back.
“The fact that weight-decay improves generalization can be viewed as a vindication of this crude MDL approach in which the standard deviations of the data-misfits and the weights are both fixed in advance.” (§4)
Noisy weights
Make each weight wobble · price the wobble · then refund it
Step 4 · A weight that's allowed to wobble
Let a weight be a fuzzy cloud, not a sharp number — and watch two costs trade off.
Plain weight-decay nailed every weight down to the same precision. The
paper's key move: stop nailing them down. Replace each precise weight with
a noisy one — a little Gaussian cloud Q with its own
width σQ.
Why would fuzziness help? Because a wide, wobbly cloud carries less information, so it is cheap to describe (message 1 shrinks). But a wobbly weight also makes the network's outputs wobble, so the mistakes get larger and more expensive (message 2 grows). There is a sweet spot. Drag the noise level and watch the two bit-costs trade off:
Drag the noise width σ — watch description bits fall while data bits rise
More noise → cheaper to describe, costlier to fit. The minimum of the total sits where one more bit of fuzziness would cost as much in extra error as it saves in description. Gradient descent finds that point for every weight automatically.
Watch the U-shaped total. Slide toward “fuzzy” and the teal curve drops while the coral one climbs; their sum bottoms out in between. Curve values are illustrative of the trade-off the paper optimizes.
Crucially, the noise width itself is learned, one per weight. A weight the network leans on stays sharp (small σ, expensive but worth it); a weight it can ignore goes fuzzy (large σ, nearly free). That is precisely the precision-per-weight that plain weight-decay couldn't express.
Because the noise width is a continuous number, the “information content” of a weight becomes a differentiable quantity. So the whole trade-off — squared error versus weight information — can be optimized by gradient descent, not guesswork.
“Adding adaptive Gaussian noise to each weight makes information content a differentiable quantity, so the trade-off between squared error and weight information can be optimized by gradient descent.” (§5)
Step 5 · Pricing the wobble exactly
The cost of a noisy weight is the gap between the cloud you keep and the prior you'd code it under.
You felt the trade-off on the slider. Now let's price the “describe the weight” bits exactly — and the answer turns out to be a famous quantity.
Sender and receiver agree in advance on a prior Gaussian
P for each weight. After training, the sender holds a learned
posterior cloud Q — a different mean and a different
width. The number of bits to send Q, given that you must code it under P,
is the KL divergence from P to Q (also called
the asymmetric divergence): a measure of how far the cloud you keep has
drifted from the prior you code under.
For two Gaussians this has a tidy closed form — and you can read each term
as a bit-cost. Drift the mean away from the prior, pay
(μQ − μP)²; make the cloud narrower than
the prior, pay for the extra precision; make it wider, get a refund:
KL(Q‖P)=logσPσQ+σQ² − σP² + (μQ − μP)²2σP²
narrower Q (smaller σQ) → more bits · wider Q → fewer bits · drifted mean → more bits · Eq. 9
This formula is the teal “describe-weight” curve from Step 4. Slide
σQ up (fuzzier) and the log(σP/σQ)
term goes negative — bits refunded. That's why a don't-care weight, left
fuzzy, costs almost nothing to send.
The communication cost of a posterior weight equals the asymmetric
divergence (Kullback-Leibler distance) from P to Q,
G(P,Q) = ∫ Q(w) log[Q(w)/P(w)] dw (Eqs. 5, 9).
Step 6 · The “bits-back” refund
Sending random weights looks wasteful — until the receiver hands the randomness back.
Step 5 priced one noisy weight at KL(Q‖P). But that hides a puzzle: to send a fuzzy weight the sender first has to pick a precise value from the cloud, using random bits. Doesn't paying for those random bits make noise more expensive, not less? The bits-back argument is the resolution.
Follow the ledger one transaction at a time. The sender uses random bits to collapse the cloud Q to a precise weight, then codes that weight under the prior P — a real, large up-front cost. But after the receiver also gets the data-misfits, he can re-run the same learning algorithm, reconstruct the very cloud Q the sender started from, and therefore recover the exact random bits that were used. Those recovered bits are free information — so the sender subtracts them back out. Step the transaction:
Step through the transaction — watch the bill, then the refund, settle to KL
Step 0 — nothing sent yet. Press “Next step” to begin the transaction.
The refund is the whole trick. The charged bits are big, but the recovered random bits cancel most of them — leaving exactly KL(Q‖P), the tidy cost from Step 5. Numbers are illustrative; the identity charged − refund = KL is exact.
Written as bits: the sender is charged
C(w) = −log t − log P(w) to pin down a precise weight, and
later refunded R(w) = −log t − log Q(w) for the
recovered random bits. Subtract, take the expectation under Q, and the
awkward −log t terms cancel exactly — leaving
KL(Q‖P). The apparent waste of noise is fully refunded.
charged − bits back = KL(Q‖P). This is the exact same identity a variational autoencoder uses two decades later, where the “bits back” are the encoder's entropy. Same algebra, different name.
“Once he has the correct outputs he can run whatever learning algorithm was
used by the sender and recover that same posterior distribution Q … he can
recover all the random bits that the sender used.” The true expected cost is
⟨C(w) − R(w)⟩ = KL(Q‖P) (Eqs. 6–8).
Step 7 · Making it actually trainable
Keep the output units linear and the whole thing has exact, cheap derivatives.
The bits-back argument settled the why. Two engineering choices make the method actually run — and they're the reason this stayed exact rather than slow and noisy.
First, exact gradients. Noisy weights would normally force slow Monte-Carlo sampling to estimate the expected error. But with one layer of non-linear hidden units and linear output units, the expected squared error has a closed form. The mean and variance of each output flow straight from the means and variances of the weights — so the derivatives compute exactly, no sampling:
⟨Ej⟩=(dj − μyj)²+Vyj
expected error = squared bias + output variance · both computed exactly from per-weight means & variances (Eqs. 10–12)
Second, a smarter prior. A single Gaussian prior P is a blunt code: if some weights cluster near 0 and a few near 1, no single bell fits both. So the paper lets the prior be an adaptive mixture of Gaussians (after Nowlan & Hinton, 1992), whose means, widths and mixing weights are learned alongside the network. Weights get pulled toward whichever cluster is cheapest to join.
Exact derivatives keep it fast; the mixture prior keeps it flexible. Together they make “minimize the bits in the weights” a practical training objective — not just a thought experiment.
“Provided the output units are linear, the exact derivatives can be computed efficiently without time-consuming Monte Carlo simulations.” The mixture uses a statistical-mechanics lemma (free energy) to keep the cost tractable (§7).
The payoff
Does it work · and what did it start
Step 8 · The one experiment
On a tiny, hard dataset, noisy weights beat noise-free weights three-to-one.
The theory is elegant — but does compressing the weights actually generalize better? The paper ran one deliberately brutal test: far more inputs than training examples, the regime where overfitting is fatal.
The task: predict the effectiveness of a peptide molecule, each described by 128 inputs, from only 105 training cases (420 held out for test). The network had just 4 hidden units — yet 521 weights, five times the number of training cases. Without limiting the information in the weights, it overfits disastrously. The score is relative error: 1.0 means “no better than guessing the mean”, lower is better.
Report card · relative error on held-out peptides (lower is better)
Noisy weights (this paper) · MDL + bits-back
Best simple weight-decay · carefully tuned
Weight-decay tuned on the test set · cheating
noise-free weights · no info penalty
The win is real but modest, on one small task. The paper says so plainly. Its lasting importance was never the 0.286 — it was the framework that produced it, which is what Part C's legacy is about.
Coding-prior: an adaptive mixture of 5 Gaussians, means initialized uniformly between −0.24 and +0.24. Optimized with conjugate gradient; the penalty coefficient was ramped from 0.05 up to 1.0 on a schedule to avoid a trivial all-equal-weights solution (§9).
Step 9 · Recap — can you explain it?
Five questions. Answer them out loud and you've got the paper.
You've followed one weight from a sharp number, to a noisy cloud, to a bits-back ledger, to a real experiment. Final check: can you re-explain each move without the page in front of you?
Answer each out loud before opening it. If all five come easily, you can genuinely re-teach this paper to someone else.
Why is overfitting a “coding problem”?
A sender must transmit the network plus the leftover mistakes. The total bill is bits-for-weights plus bits-for-misfits. MDL says pick the network that makes that total smallest — so generalization means the weights carry less information than the outputs they explain.
Why does making a weight noisy ever help?
A wide, wobbly cloud carries less information, so it is cheaper to describe (message 1 shrinks). The wobble does add error (message 2 grows), so each weight settles at the noise level where the two bit-costs balance — sharp where it matters, fuzzy where it doesn't.
What exactly does a noisy weight cost?
The KL divergence from the agreed prior P to the learned cloud Q. Drift the mean from P, pay; make Q narrower than P, pay for the precision; make Q wider, get a refund. A Q that stays near P is nearly free.
What is the “bits-back” refund?
Sending a fuzzy weight needs random bits to pick a precise value — a big charge. But after the receiver also gets the misfits, he re-runs learning, reconstructs Q, and recovers those random bits. Subtract them: charged − refund = KL(Q‖P), exactly.
Did it actually work?
On the 128-input peptide task with 105 training cases, noisy weights hit 0.286 relative error versus 0.967 for noise-free weights and 0.317 for the best honest weight-decay. A real but modest win on one small task — the authors call it preliminary.
What happened next — the bits-back identity, charged − refund = KL(Q‖P), is the exact bound a variational autoencoder optimizes. The idea of a distribution over weights, trained by gradient descent, became “Bayes by Backprop” and modern variational inference. The 0.286 faded; the framework did not.
“The idea of minimizing the amount of information that is required to communicate the weights of a neural network leads to a number of interesting schemes for encoding the weights.” — Hinton & van Camp, 1993
The quiet seed of variational deep learning.
Judged on its 0.286, this is a minor 1993 result. Judged on its idea — that a network is a message, and the bits-back refund makes a distribution over weights cheap to send — it is one of the roots of how modern generative models are trained.
Variational autoencoders
The VAE's training objective is the same bits-back identity: reconstruction cost plus KL(Q‖P), with the encoder's randomness refunded. This paper stated that bound twenty years early.
Bayes by Backprop
“Weight uncertainty in neural networks” (Blundell et al.) trains a Gaussian over every weight by gradient descent — exactly this method, scaled up to deep nets.
MDL & compression
“Generalization is compression” — keep the model cheaper to describe than the data it explains — remains a guiding lens on why over-parameterized networks still generalize.
Don't ask how accurate the weights are; ask how many bits they cost — a question the field is still answering.