Sparsity and Out-of-Distribution Generalization
This work addresses the fundamental problem of out-of-distribution generalization for machine learning, including AI alignment, by providing a theoretical framework.
This paper proposes a principled account of out-of-distribution (OOD) generalization, building on the ideas that the world is presented via distinguished features, Occam's Razor favors sparse hypotheses, and these sparse hypotheses generalize if training and test distributions sufficiently overlap on relevant features. The authors formalize these intuitions with a theorem that generalizes the Blumer et al. sample complexity bound to an OOD context and extend sparse classifiers to subspace juntas.
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.