Minimum Neural Weight Norm = Kolmogorov Complexity
summary
The gist
Neural Weight Norm = Kolmogorov Complexity is proven to establish that in any fixed-precision regime, the smallest weight norm of a looped neural network outputting a binary string equals the…
In short
The paper proves that for a fixed-precision neural network outputting a binary string, the smallest weight norm equals its Kolmogorov complexity up to a logarithmic factor. This means weight decay acts as an optimal prior matching Solomonoff’s universal prior over computable functions, linking regularization directly to the inherent randomness of information.
Key concepts
- Kolmogorov Complexity (K(s))
- This measures the shortest possible description length for a string s using a fixed programming language. It quantifies the inherent incompressibility or randomness of that specific output string.
- Weight Norm and Fixed Precision
- In fixed-precision regimes, the Lp weight norm of a network's weights is essentially equal to the count of non-zero parameters. This equivalence is crucial because it allows the network's magnitude to be treated as an O(1)-bit object, linking its size directly to its description length.
- Solomonoff’s Universal Prior
- This is the optimal prior distribution over all computable functions, representing the most unbiased guess about what a program will output. The paper shows that L2 weight decay induces a prior that matches this universal prior in the exponent.
Terminology used across episodes
This episode discusses
- Minimum Neural Weight Norm = Kolmogorov Complexity · Paper Radio
- Universal Transformers
- Learning Universal Predictors
- Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
- Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers
The paper
Minimum Neural Weight Norm = Kolmogorov Complexity · Read on arXiv
Tiberiu Musat
ETH Zurich
Transcript
Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Minimum Neural Weight Norm = Kolmogorov Complexity".
Paper summary: Tom: So to recap, this paper by Tiberiu Musat proves that for any computable string s, the smallest weight norm of a looped neural network outputting s equals its Kolmogorov complexity up to a logarithmic factor.
Jane: That’s really dense. So the main thing is that we can use weight decay as a prior matching Solomonoff’s universal prior when you're working in fixed precision.
Lu: The paper establishes that the minimum number of non-zero parameters, N(s), is bounded by K(s) and K(s) is bounded by N(s) times the logarithm of N(s).
Meng: If we translate that to what I care about, it means the regularization penalty you add to your loss function isn't just some arbitrary tuning; it’s actually matching the optimal prior for any computable hypothesis.
Lalam: The paper says the induced prior on the network’s output under L2 weight decay matches Solomonoff’s universal prior in the exponent up to that logarithmic factor, which is a pretty strong connection.
Tom: But there are caveats about what this means practically, right? The authors point out that while it holds for fixed precision, real-valued networks can compute non-recursive functions with finite norms even though their Kolmogorov complexity is infinite.
Jane: Right, so the fixed precision condition is the key restriction here because it’s what locks the result into the world of computable functions, not everything that runs on actual hardware.
Lu: The paper also mentions two ways they prove this: one way shows any program for a universal Turing machine can be encoded into neural weights at unit cost per program bit, and another shows how to describe any fixed-precision network by just enumerating its non-zero parameters with some logarithmic overhead.
Meng: I wonder what the practical cost of that enumeration overhead is when you’re trying to deploy these models at scale. If every parameter needs that extra log factor for description, it could add up fast.
Lalam: The paper suggests this correspondence is tight because the network can exploit that log factor, using things like permutation encodings where a network with theta parameters can produce a string whose complexity scales as the non-zero parameter count times its logarithm.
Conclusion: Tom: So we’ve been looking at "Minimum Neural Weight Norm = Kolmogorov Complexity" and the authors' claim that weight decay matches Solomonoff's universal prior in this fixed-precision setup.
Jane: The big implication is that simple data benefits more from weight decay than what you might get from just using random targets or some other regularization method.
Lu: It suggests that flat minima you see downstream are actually a consequence of this weight norm matching the description length, not some separate phenomenon we have to explain.
Meng: From an engineering standpoint, it means the most reliable regularizer in modern deep learning is actually a tractable proxy for what an ideal computational agent would choose as its optimal prior.
Lalam: The paper establishes a quantitative two-sided link between the L2 weight decay used in practice and that universal prior up to a polynomial factor in something related to K(s).
Tom: It’s less about inventing a new loss function and more about understanding *why* the regularization we use actually works so well for learning patterns.
Jane: It really ties together complexity theory, which sounds super high-level, with the actual mechanics of how neural networks learn representations.
More episodes
- 2603.28595-Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes
- 2603.29765-Training-Free Dynamic Upcycling of Expert Language Models
- 2605.00778-Observable Performance Does Not Fully Reflect Adaptive System Organization: A Multi-Level Analysis of Gait Dynamics Under Occlusal Constraint
- 2605.06906-TraXion: Rethinking Pre-training Frameworks for Mobility and Beyond
- 2605.09165-Sparse Layers are Critical to Scaling Looped Language Models
- 2605.09439-Inverse Design for Conditional Distribution Matching
- 2605.10313-Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewards: Regret Bound and Statistical Inference
- 2605.11617-MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound
- 2605.15085-From Data to Action: Accelerating Refinery Optimization with AI
- 2605.23500-GRTO: Bootstrapped Group Relative Tool Optimization for Referring Segmentation