Scott Aaronson, Lin Lin Lee, Jiawei Li
5 min
Abstract
Explaining out-of-distribution generalization has been a central problem in epistemology since Goodman's "grue" puzzle in 1946. Today it's a central problem in machine learning, including AI alignment. Here we propose a principled account of OOD generalization with three main ingredients. First, the world is always presented to experience not as an amorphous mass, but via distinguished features (for example, visual and auditory channels). Second, Occam's Razor favors hypotheses that are "sparse," meaning that they depend on as few features as possible. Third, sparse hypotheses will generalize from a training to a test distribution, provided the two distributions sufficiently overlap on their restrictions to the features that are either actually relevant or hypothesized to be. The two distributions could diverge arbitrarily on other features. We prove a simple theorem that formalizes the above intuitions, generalizing the classic sample complexity bound of Blumer et al. to an OOD context. We then generalize sparse classifiers to subspace juntas, where the ground truth classifier depends solely on a low-dimensional linear subspace of the features.
Sam: They use VC-dimension from learning theory—a measure of rule flexibility. Simple sparse rules have low VC-dimension, so examples scale manageably, like k times log of total features. This gives a PAC-style bound for shifted data.
Alex: So overlap plus simplicity controls sample needs?
Sam: Exactly. It shows why ignoring noise works when cores align.
Alex: Makes the philosophy puzzle feel concrete.
Sam: Classic PAC learning says: for rules with low VC-dimension, enough training examples from one setup mean a perfect fit works on new ones from the same setup. But tests often shift, so they add a shift measure called alpha: for test events happening at least alpha often, they must hit alpha in training too. If alpha is zero for new test events, guarantees fail.
Alex: They fix that with sparsity?
Sam: Yes. They focus on k-sparse rules—depending on k chosen features out of n, union over all choices. VC-dimension stays low, like k log n. Theorem 3 proves: if true and learned rules share key features A, and train-test match exactly on A combos, test error matches training error—near zero after enough examples.
Alex: Irrelevant parts can change wildly, as long as A lines up?
Sam: Exactly. Rules ignore outside A, so test averages over matching A first, making other noise irrelevant.
Alex: What if overlap isn't perfect?
Sam: Theorem 4 adds alpha tolerance on A: samples scale with 1/alpha if shifts aren't too wild there.
Alex: Like Occam's Razor: simple rules generalize when essentials match.
Sam: Right. They extend to subspace versions—rules depending on projections onto k directions, like neural nets viewing low-dim shadows. Theorem 5: if train-test match on combined shadow space A, generalization holds, with low VC. Theorem 6 adds alpha tolerance.
Alex: Does that fit real neural nets?
Sam: For some, like halfspaces or polynomial thresholds—VC stays polynomial. But Question 1 notes counterexamples: some inner functions make overall VC infinite despite low dimension. Care needed for broad classes.
Alex: So projections strengthen it, but limits exist. Explains why nets sometimes handle rotations.
Sam: These are existence proofs: clean examples guarantee generalization under overlap. But they assume perfect data matching a true sparse rule—no noise—and no efficient ways to find keys.
Alex: Limits real use?
Sam: It guides next steps, like noisy algorithms or checking alignments. Test if train-deploy data match on key features to predict success—or spot risks.
Alex: A formal reason sparsity plus overlap handles shifts, with paths ahead.
Sam: Yes—a meaningful bridge from philosophy to AI safety, why simple rules ignore distractions when essentials align.
Alex: Well put. Thanks for joining ResearchPod.