Neural Weight Norm = Kolmogorov Complexity: Why Weight Decay is Optimal Induction

TL;DR

Why does $L_2$ regularization (weight decay) work so well? A new paper from ETH Zürich provides a profound answer: in any fixed-precision system, the weight norm of a network is essentially the Kolmogorov complexity of the data it generates. This means every time you use weight decay, you are performing a computable version of Solomonoff Induction—the theoretical "gold standard" for Bayesian prediction.

Background: The Mystery of Regularization

For decades, deep learning has relied on weight decay to prevent overfitting. Yet, our standard toolkit of learning theory (VC dimension, Rademacher complexity) is remarkably bad at explaining why. These theories focus on the "size" of the function class, but the same network architecture can generalize on real data while perfectly memorizing random labels.

The author, Tiberiu Musat, argues that we should stop looking at function classes and start looking at Description Length.

The "Insight": The Fixed-Precision Collapse

The paper's breakthrough rests on one key observation: Fixed Precision. While theoretical AI often assumes infinite precision (real numbers), actual hardware uses fp16, int8, or bf16.

In this discrete world, all $L_p$ norms (whether $L_1$ or $L_2$) collapse into the same thing: a count of non-zero parameters. ${\delta }^p\cdot \Vert heta{\Vert }_0\le \Vert heta{\Vert }_p^p\le M^p\cdot \Vert heta{\Vert }_0$ This "collapse" allows the author to bridge the gap between continuous math (calculus/GD) and discrete math (Turing machines).

Methodology: The Sandwich Bound

The core of the paper is the Main Theorem, which "sandwiches" Kolmogorov complexity $K(s)$ between two bounds of neural complexity $\mathcal{N}(s)$:

1. Lower Bound (Programs → Networks): Any computer program of length $|p|$ can be embedded into a neural network using roughly $|p|$ weights.
2. Upper Bound (Networks → Programs): Any network with $W$ non-zero weights can be described as a program of length $O(W\log W)$.

The fundamental relationship: Neural Complexity effectively tracks Algorithmic Complexity.

The Logarithmic Factor is Real

The $O(\log W)$ factor isn't just a mathematical artifact. The author proves it is tight using the "Permutation Example." If a network encodes a permutation, it uses $N$ parameters to identify one out of $N!$ possibilities. Since $\log N!\approx N\log N$, the network is "using" that log factor to store structural information in the positions of its weights.

Experiments & Theoretical Implications

By bridging these worlds, the paper derives several heavy-hitting conclusions:

• Solomonoff Matching: The prior induced by weight decay is a polynomial-factor approximation of Solomonoff’s Universal Prior.
• Quantization strengthens the bias: Deeply quantized networks (like 4-bit) implement this "Universal Induction" more directly than full-precision models.
• Generalization Bounds: The author derives a new MDL-style generalization bound where the penalty is $\Vert heta{\Vert }_2^2\log \Vert heta{\Vert }_2^2$.

How this work compares to legends like Schmidhuber and Hinton. This paper is unique in providing a two-sided bound for any $L_p$ norm in fixed-precision.

Critical Analysis & Takeaways

Limitations

• Asymptotic Constants: The proof works for large $N$, but the "constants" involved in building a Universal Turing Machine inside a Transformer are likely huge.
• No Empirical Validation: This is a pure theory paper. While it makes testable predictions (e.g., "simple data benefits more from weight decay"), it doesn't run them on ImageNet.

Conclusion

This work elevates weight decay from a "trick to keep weights small" to a fundamental law of information. It suggests that the success of modern Transformers is due to the fact that their training dynamics are implicitly searching for the shortest possible program to explain the data.

If you are training a model today with $L_2$ regularization, you aren't just doing "optimization"—you are performing algorithmic induction.