Theory 061/Information & Computation /Learning theory
Compression Predicts Generalisation
Capacity is counted in parameters. The useful capacity may be the ability to describe the data briefly.
A model's generalisation is predicted by how much it compresses its training data rather than by its parameter count, so a larger model that compresses better generalises better even when it has more capacity to memorise.
01The evidence
Overparameterised models generalise well, which contradicts parameter-count bounds, while compression-based measures track generalisation more reliably in practice.
02The tension
Classical theory bounds generalisation by capacity, and the bounds fail on modern models. The failure is attributed to implicit regularisation without a measurable quantity.
03The mechanism
A model that predicts data well assigns it short code length. The code length is a measurable quantity, and it bounds the gap between training and test performance more tightly than parameter counts do.
That makes compression the criterion, and predicts that among models with equal training error, the one with shorter description length should generalise better.
04What this is not
Count bounds fail on overparameterised models. This uses description length, which is measurable and tracks performance.
05Predictions
- P1Generalisation gap should correlate with description length.
- P2Equal-error models should rank by compression.
- P3Larger compressing models should beat smaller ones.
06Refutation
Generalisation tracking parameter count at controlled compression would restore capacity bounds.
07What it changes
It would change model selection criteria.