Ilya Sutskever opens this Simons Institute lecture by admitting he almost gave the standard talk and decided against it. Instead he presents a set of results from years earlier at OpenAI, never published, on a question that had bothered him: supervised learning comes with a mathematical guarantee, and unsupervised learning does not. His claim is that it can, if you frame unsupervised learning as compression.
This is the “Classic of the Week” pick, and it earns the label for a specific reason. The argument connects distribution matching, Kolmogorov complexity, and the empirical behavior of next-token prediction in a way that makes the success of large pretrained models feel less like an accident. Sutskever sets expectations modestly — some of it is obvious, he says, and maybe not all of it.
What supervised learning has that unsupervised doesn’t
The PAC-learning result is compact enough to state in a sentence: if your training and test data come from the same distribution, and you find a function from a not-too-large function class that achieves low training error, then low test error is guaranteed. The proof is a few lines. The failure condition is precise — if the training distribution differs from the test distribution, all bets are off.
Sutskever’s point isn’t that the bound is tight. It’s that supervised learning gives you a reason to expect success before you run the experiment. You can be confident models will keep improving as you add data, and know why.
He detours briefly through VC dimension, and his read is deflationary. VC dimension exists mostly to handle parameters with infinite precision. Real computers use floating point, precision shrinks, and the number of functions representable by a computer is finite — at which point the simpler counting bound recovers essentially all the useful results with fewer lines of math.
Unsupervised learning has no equivalent. You optimize one objective — reconstruction, denoising, next-token prediction — and hope for good performance on a different objective you never optimized. Empirically it works. Theoretically, he says, there is no reason to expect it.
Distribution matching: the first crack
Before the main argument, Sutskever presents a setting he ran into years ago that he finds underappreciated. Take two data sources with no correspondence between them — a corpus of English text and a corpus of French text, no sentence pairs. Look for a function f such that the distribution of f(X) matches the distribution of Y.
If X and Y are high-dimensional enough, that constraint alone nearly determines f. This is unsupervised learning that provably works, in the same sense supervised learning provably works, and it covers machine translation and speech recognition as special cases. The setup is artificial and real ML systems are not built this way. But it establishes that a guarantee is possible.
Compression as the frame
Here is the thought experiment that carries the talk. You have two files on a large disk, X and Y, and a good compression algorithm C. You concatenate them and compress the result. What happens?
A good compressor will exploit whatever structure the two files share. The compressed concatenation will be smaller than the sum of the separately compressed files, by exactly the amount of shared structure the compressor manages to extract. Now let X be your unlabeled data and Y be your task data — and the compressor’s job of noticing patterns in X that help predict Y is precisely what you want from unsupervised learning.
Sutskever notes that compression and prediction are equivalent — every compressor is a predictor and vice versa — but argues the compression framing makes this particular argument easier to see. It also subsumes the distribution matching case: a good compressor over a concatenation of English and French will notice the shared structure and use it.
The formalization is in terms of regret. If your algorithm’s regret is low, you have extracted essentially all the value your unlabeled data could offer. Someone with a better compressor could do better, but you have done everything possible with the one you have — as he puts it, you can sleep peacefully.
Kolmogorov complexity as the ceiling
The best possible compressor is the Kolmogorov compressor: compress a string by finding the shortest program that outputs it. It is not computable — that is essentially the halting problem — but it dominates every computable compressor. Give it your favorite compression algorithm as a program and it does at least as well, paying only a constant for the length of that program’s code.
Then the move that makes the whole thing feel less abstract. Running SGD over the parameters of a large neural network is program search over a computer, because neural networks are computing machines with circuits and connections. It’s not the full search, but it’s a real search. Everything here rests on what he calls the SGD miracle: that gradient descent actually finds those circuits.
He extends the observation to architecture design. When you propose adding a connection to an architecture, the simulation argument says the old architecture could have emulated the new one — except when it can’t. An RNN cannot cheaply simulate a transformer given its constrained hidden state; with enough hidden state and the right weights, it could.
For unsupervised learning you want conditional Kolmogorov complexity: the shortest program that outputs Y when allowed to read X. The same domination result holds. This is a good theoretical solution — an algorithm that does better on unsupervised learning than yours is not possible — with one problem: conditioning on a large dataset is awkward. In practice you can fit a dataset but not condition on one.
The resolution is the last technical step. Compressing the concatenation of X and Y with the ordinary unconditional Kolmogorov compressor is just as good as using the conditional one. There are subtleties, which he offers to discuss offline, but the practical statement is clean: take all your data, concatenate it, compress it jointly, and you get the best possible predictions on your supervised task. And this is what pretraining on a large corpus does.
Where this shows up empirically
If the argument holds, better unsupervised objectives should mean better representations in a domain where the connection is not obvious. iGPT was built to test that in vision — not as a practical method but as proof of the idea. Predict the next pixel the way you predict the next word, then fit a linear probe on the best layer. As the models get larger, their unsupervised loss improves and the probe accuracy improves with it.
They scaled to six billion parameters — giant for 2020 — on 64×64 images. The result reached 99% on CIFAR-10 and closed much of the gap to the best contrastive methods of the day on ImageNet, without closing it fully. Sutskever attributes the remaining gap to compute and resolution rather than to the approach, and the honesty is worth noting: the theory predicted the trend, and the trend appeared.
He is explicit about the theory’s limits. It says nothing about why representations should be linearly accessible. Linear probes work everywhere, and the framework offers no account of it. He does flag one empirical curiosity: autoregressive next-pixel models produce better linear representations than BERT-style masked models, and he is not certain why. His speculation is that masking with a moderate fraction of tokens removes the hard prediction problems — much of the reconstruction can be done by looking slightly into the past — whereas the hardest prediction in an autoregressive setting is genuinely harder.
An audience question raises diffusion models, which produce excellent images without an autoregressive objective, as a counterargument. He concedes the tension.
Key takeaways
- Supervised learning has a guarantee that tells you before you run the experiment whether it will work: same distribution, low training error, bounded function class, and low test error follows.
- VC dimension mostly exists to handle infinite-precision parameters. On real hardware the function class is finite and a counting argument recovers the useful bounds with less machinery.
- Distribution matching — finding f such that the distribution of f(X) matches Y, with no paired examples — is unsupervised learning that provably works, and it covers translation and speech as special cases.
- Compressing two files jointly does better than compressing them separately by exactly the shared structure the compressor can extract. Set X to unlabeled data and Y to task data and that is unsupervised learning.
- Framing the goal as low regret means you have extracted everything your unlabeled data can offer with the compressor you have, even if a better compressor exists.
- The Kolmogorov compressor dominates every computable compressor, and SGD over a large network is a real if partial search over programs — resting entirely on the empirical fact that SGD finds the circuits.
- Joint unconditional compression of X and Y is as good as conditional compression of Y given X, which is exactly the theoretical shape of large-corpus pretraining.
- iGPT confirmed the prediction in vision: better next-pixel loss produced better linear probes as scale increased. The theory does not explain why the probes are linear, and Sutskever says so.
Source
An Observation on Generalization — Ilya Sutskever (OpenAI), Large Language Models and Transformers workshop, Simons Institute for the Theory of Computing, UC Berkeley, 14 August 2023. 57m 21s.