Lost in Latent Space

The bounds are vacuous and I’ve stopped feeling bad about it

I got into statistical learning theory the way a lot of people do: I trained a neural network, watched it generalize better than it had any business doing, and wanted to know why. Someone pointed me at VC dimension. I learned what it was, did the exercises, and worked out the bound for my model. The bound said the test error could be as high as several million percent. The actual test error was 3.2%.

This was puzzling, then funny, then embarrassing — embarrassing for the theory, not for me. Eventually I stopped looking at bounds at all when I wanted to predict whether a model would generalize, and that has worked out better than I expected. I want to write down why, partly because I keep meeting people who are where I was five years ago, and partly because I’m still not entirely at peace with it.

The bounds aren’t wrong, they’re just answering a different question

This took me a while to internalize. A VC bound (or a Rademacher bound, or PAC-Bayes, or really any classical bound) is a worst-case statement over a hypothesis class. It says: there exists some distribution and some sample where, if you got unlucky, your test error could be this bad. That’s not a prediction about your model. It’s a prediction about the class of models you’re drawing from, assuming an adversary is choosing both the data and the hypothesis.

Modern networks have hypothesis classes so large that the worst case is catastrophically bad. The actual case isn’t, because (1) SGD doesn’t draw uniformly from the class, and (2) natural data isn’t adversarial. Both facts are outside the bound’s scope. So the bound delivers what it promises — it just promises something I don’t care about.

What predicts generalization better than bounds

In rough order of how often I actually use them:

  1. Training-set size relative to dataset complexity. Crude, but the single biggest lever.
  2. A held-out set. Yes, this is a tautology, but specifically: a small held-out set, checked often during training tells me when the gap opens. The number it produces is more useful than any bound.
  3. Sharpness of the minimum (loss landscape curvature, or proxies like gradient noise scale at the end of training). Models that converged to flatter minima generalize better. This isn’t proven, but it replicates and I trust it.
  4. Effective number of parameters that moved. Many of the parameters in a fine-tuned network barely change. Counting only the ones that did has, in my experience, been a better proxy for “capacity actually used” than counting all of them.
  5. Distribution shift between train and test. A bound assumes IID. In real life it’s only approximately IID. The shift matters more than any other single factor when generalization fails surprisingly.

None of these come with a formal guarantee. All of them are more useful than the formal guarantees I have access to.

So does the theory matter?

Here’s where I’m still unsettled. Part of me says no: the theory has had forty years and still cannot produce a non-vacuous bound for a modern network. That’s a long time to be wrong about the thing you said you’d explain. Part of me says yes: PAC-Bayes-flavored bounds with data-dependent priors are creeping toward non-vacuity, and the work on implicit regularization (SGD as a stochastic differential equation, the neural tangent kernel, etc.) is producing theory that touches the actual training procedure rather than the worst case over the class.

What I’ve actually settled on is this: the bounds I learned aren’t predictive tools, they’re limits on what a worst-case argument can buy you. Once I stopped expecting predictions out of them, I stopped being disappointed, and the parts of the theory that are predictive (PAC-Bayes with the right prior, NTK in the right regime) became visible to me as a separate, more useful thread.

What I’m still puzzling over

Why do flat minima generalize better, mechanistically? I don’t believe “flatness ≈ MDL” all the way down. Something about the loss-landscape geometry is doing real work and I don’t yet have a satisfying picture of what.