Major revision: min neural weight norm asymptotically equals Kolmogorov complexity, one claim retracted
TacoCohen · x · 2026-11-19
Tiberiu Musat's preprint "Minimum Neural Weight Norm = Kolmogorov Complexity" gets a major revision:
- Stronger result: the ratio between minimum weight norm and Kolmogorov complexity (divided by its logarithm) tends to 1 in the limit — true asymptotic equivalence, where v1 only established a logarithmic separation gap. The proof uses two reductions: looped networks encode info via sparsity patterns at logarithmically many bits per non-zero parameter, and any fixed-precision network is describable by enumerating non-zero parameters with logarithmic addressing cost.
- Retraction: the original claim that a Gaussian prior over weights induces a Solomonoff prior over programs had a fundamental proof error and has been fully removed, with the author apologizing.
- Scope: only applies to Turing-complete architectures with constant-precision weights — looped/CoT Transformers, not standard Transformers, CNNs, or finite-state RNNs.
The work links norm minimization to algorithmic simplicity, offering a route toward explaining deep learning generalization and what weight decay really does.
More from Research
- The Little Book of ML Metrics nears launch, pre-order at $60 for data scientists — santiviquez · 2026-11-19
- Schmidhuber publishes annotated AI history tracing deep learning to 1676 — SchmidhuberAI · 2026-11-19
- ICLR debate: cap author rebuttals — and reviewers' 32 AI-generated weaknesses too? — TuhinChakr · 2026-11-19
- Weight-space blend of base and RL checkpoints restores the diversity RL removed: α=0.25 keeps 64-80% of pass@1 gain — Perfect_Power815 · 2026-11-19
- Erik Hoel: consciousness is a great mystery, but its definition isn't — experts largely agree — koltregaskes · 2026-11-19
- ICLR author expands rebuttal from 24 to 40 pages, gets zero reviewer replies — O_Fake_One · 2026-11-19