Dogukan Tuna

Compression is how I think about learning. The tighter a model can compress its inputs, the more structure it has actually found. Kolmogorov complexity makes this precise. It measures the length of the shortest program that produces a given output, which turns out to be the theoretical floor for any compressor.

The Ultimate Compressor

K(X) = length of the shortest program that outputs X. For any computable compressor C and all strings X:

K(X) ≤ |C(X)| + K(C) + O(1)

via the simulation argument: run C inside a universal machine

The Catch

K(X) is uncomputable. You can never know the true shortest program. But a deep network is a finite parallel computer that approximates it with bounded resources.

Why Neural Nets are Compressors

1. Neural nets can simulate arbitrary programs.
2. They are small computers, circuits wired by data.
3. SGD searches over the space of programs they can express.

Micro-Kolmogorov Complexity

Fix an architecture, then fit a network with SGD. The bit-length of the resulting weights is a practical proxy for description length:

min_{f ∈ F} [ loss(f) + λ · micro-K(f) ]

micro-K(f) ≈ bit-length of weights in a fixed architecture

Shorter description length → better generalization.

I'm deeply invested in methods that make learning systems compress harder and generalize further.