Models, Networks and Algorithmic Complexity

Models, functions, invariance groups, and datasets are all the same thing viewed through different lenses — and Kolmogorov complexity is the unifying language.

The central move is simple but powerful: an optimal model of a dataset is just the shortest program that generates it. That's it. Once you accept this, a classifier, a generative function, and a compressed dataset become interchangeable descriptions of the same underlying computational object. You can walk from one to another without losing information. This equivalence isn't just philosophical tidiness — it means every tool from algorithmic information theory (Kolmogorov complexity, the Solomonoff prior, compression ratios) can be applied directly to neural networks and learning.

The most concrete result is about invariance groups. When a classifier labels some inputs as "hand" and others as "not hand," the set of transformations that shuffle hands among hands (rotations, translations, deformations) forms a mathematical group. The paper proves that this group uniquely determines the classifier up to relabeling. This matters because it reframes what learning actually is: you're not memorizing examples, you're discovering a group structure. If you know the group, you need only a short program to specify the generative function — exponentially fewer bits than a lookup table. The group is the compression.

Building on this, the paper introduces implementation efficiency — the ratio of a function's algorithmic complexity to the program length needed to specify a network that computes it. A perfectly efficient network would have ratio 1; a bloated one wastes bits. The paper then conjectures (and this part is explicitly unproven) a strict ordering: recurrent networks are more efficient than deep feedforward networks, which beat shallow ones, with the gap widening as the function becomes more compressible relative to its raw entropy. The intuition is clean: shallow networks can't reuse intermediate computations, so they expand every combination explicitly. Deep networks exploit compositionality the way a for-loop exploits repetition. Recurrent networks add while-loops and become Turing-complete.

There's also a neuroscience thread. The paper connects perturbation propagation in well-trained networks to the algorithmic depth of what they encode — and links this to the perturbational complexity index (PCI), an empirical measure derived from TMS stimulation of human cortex. The claim is that circuits encoding deep, compressible functions should show rich, propagating perturbation signatures, while shallow or random circuits should not. This is a testable bridge between abstract complexity theory and brain measurement, though the paper doesn't validate it experimentally.

The honest caveat: the two central conjectures about deep versus shallow efficiency remain unproven, Kolmogorov complexity is uncomputable in general (the paper relies on LZW compression as a practical proxy), and the framework is entirely theoretical with no empirical section. What it does deliver is a coherent vocabulary — models as compression, learning as group discovery, architecture as programming language — that subsequent work in this corpus builds on directly.