Paper deep dive
Sparsity and Out-of-Distribution Generalization
Scott Aaronson, Lin Lin Lee, Jiawei Li
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/13/2026, 12:33:16 AM
Summary
The paper provides a theoretical framework for out-of-distribution (OOD) generalization by leveraging the principle of sparsity (Occam's Razor) and subspace juntas. It proves that if a ground truth hypothesis and a learned hypothesis depend on a small number of features or a low-dimensional subspace, generalization is possible even when training and test distributions diverge on irrelevant features. The authors generalize classic PAC-learning bounds to this OOD context.
Entities (7)
Relation Signals (4)
Scott Aaronson → authored → Sparsity and Out-of-Distribution Generalization
confidence 100% · Paper title and author list
OOD Generalization → addresses → Goodman's grue puzzle
confidence 95% · Explaining out-of-distribution generalization has been a central problem in epistemology since Goodman's grue puzzle
Sparse Hypotheses → formalizes → Occam's Razor
confidence 90% · Sparse hypotheses are one way to formalize the idea of Occam's razor
Subspace Juntas → generalizes → Sparse Hypotheses
confidence 90% · We then generalize sparse classifiers to subspace juntas
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.07388v1
- Canonical: https://arxiv.org/abs/2603.07388v1
Trouble viewing inline? Open PDF directly →
Full Text
54,935 characters extracted from source content.
Expand or collapse full text
Sparsity and Out-of-Distribution Generalization Scott Aaronson UT Austin aaronson@cs.utexas.edu. Supported by Coefficient Giving. Lin Lin Lee UT Austin llee3@utexas.edu. Supported by Coefficient Giving. Jiawei Li UT Austin davidlee@cs.utexas.edu. Supported by Coefficient Giving. 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. (Blumer et al., 1989) 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. 1 Introduction Centuries ago, David Hume asked why we have any rational grounds to expect that the Sun will rise tomorrow—or more generally, why any hypothesis formed to explain past data should generalize to unseen data. Today, the spectacular successes of machine learning, and especially the worries about dangers to humanity as AI grows more powerful, motivate revisiting Hume’s question from a new lens. We are motivated by the following question from the field of AI alignment. Suppose an AI is trained on millions of examples of human moral behavior, and seems to do well at generalizing to further such examples. How do we know that this is not “deceptive alignment”? I.e., how do we know that AI has learned the rule “be moral,” rather than (say) “pretend to be moral while being trained, so that you can pursue your own goals once released into the wild”? Crucially, as long as the AI could tell whether it was in “training” or “deployment” mode (and it seems plausible that it could), the deceptive alignment scenario seems indistinguishable in principle from genuine alignment via any external probe done at training time. In the 1980s, the new field of computational learning theory had notable success at explaining in-distribution generalization — that is, the ability of learning algorithms, given enough sample data drawn from a distribution D, to explain further data also drawn from D. Concretely, Valiant (Valiant, 1984) observed that, if one wishes to “PAC-learn” — that is, find a hypothesis that’s “probably approximately correct,” correct on at least a 1−ϵ1-ε fraction of future data points with probability at least 1−δ1-δ — then it suffices to find a hypothesis that explains m∼1ϵlog|ℋ|δm 1ε |H|δ data points, where ℋH is the class of hypotheses under consideration, and |ℋ||H| is its cardinality. Blumer et al. (Blumer et al., 1989) later sharpened this to show that, even if ℋH is infinite (for example, because the hypotheses involve real parameters), PAC-learning can still be possible with a small number of samples, so long as ℋH is bounded in a key combinatorial parameter called the VC (Vapnik-Chervonenkis) dimension. Alas, conceptually important as they were, these results fall short of explaining the success of modern deep learning in at least two respects. The first is that modern deep learning is typically “overparameterized,” which is to say: the VC-dimension of the hypothesis class is typically far too large, and the sample size is far too small, for the standard theorems to explain the observed successes. More relevant for us, generalization bounds depend essentially on the assumption that the training distribution and test distribution are the same D—i.e., that “the student is tested only on types of problems that were covered in class.” The theorems are powerless to explain even the most trivial instances of OOD generalization, ones where no one seriously expects that practical ML systems will fail. As an example, suppose a neural network is trained to distinguish photos of cats from photos of dogs, until it does extremely well on the training distribution. But suppose that, in the training images, the top-left pixel always happens to be red. Now the neural network is given a new cat or dog image, where the top-left pixel is yellow. A priori, nothing rules out that the network will suddenly start identifying cats as dogs and dogs as cats. Indeed, if we let x be 0 or 1 depending on whether the image is of a cat or dog, and y be 0 or 1 depending on whether the top-left pixel is red or yellow, nothing rules out that the network has learned x⊕yx y, when we wanted it to learn x. The two hypotheses are equally consistent with the training data, and nearly equally easy to represent in a neural network—yet they behave in diametrically opposite ways on the test data. This is simply a modern version of what Nelson Goodman (Goodman, 1955), in 1946, called the “New Riddle of Induction,” or “grue” riddle. Define the word grue to mean “green until January 1, 2030, and blue thereafter”. Likewise, define bleen to mean “blue until January 1, 2030, and green thereafter”. Then Goodman observes that all of our evidence seeming to indicate, for example, that emeralds are green and the sky is blue, could equally well be considered evidence that emeralds are grue and the sky is bleen. A standard response would be that grue and bleen are disfavored by Occam’s Razor: why introduce the gratuitous, unmotivated belief that emeralds and the sky will switch color on a specific date, in the absence of any evidence? Goodman responds that, if we imagined a culture where grue and bleen were basic conceptual categories, then green and blue would seem gratuitous and unmotivated: indeed, one could only express them via complicated phrases like “grue until January 1, 2030, and bleen thereafter”. Likewise with the image classifier, one could imagine a parameterization of the hypothesis class in which hypotheses like x⊕yx y (i.e., cat or dog XOR the color of the top-left pixel) were natural to express, and hypotheses like x (i.e., cat or dog) were complicated. In that case, exposed to images of cats and dogs wherein the top-left pixel always happens to be red, our learner would output an x⊕yx y hypothesis. We conclude that, even in this toy scenario, any explanation for the success of OOD generalization must appeal to some principle beyond those considered in 1980s computational learning theory. For even after we fix the training distribution, test distribution, sample data, and hypothesis class, OOD generalization will sometimes succeed and sometimes fail, depending on which hypotheses the learning algorithm favors as defaults. 1.1 Our Approach In our paper, we consider both sparse hypotheses, which depend only on a few of the input features, and subspace juntas, which generalize this dependency to a low-dimensional subspace of the input space. Sparse hypotheses are one way to formalize the idea of Occam’s razor, under the hypothesis that the world is processed as distinguished features. We now model the grue puzzle to illustrate how sparsity can help. Let S=ℝS=R, n=2n=2, and k=1k=1. There are n=2n=2 input features: the time t and the “emeraldness” e, which takes the value 1 for an emerald and 0 for a sapphire. Given an input of the form (t,e)(t,e), the goal is to learn a function f(t,e)f(t,e), which outputs 1 if the object is green or 0 if it’s blue. The target function, of course, is f(t,e)=ef(t,e)=e: that is, emeralds are green and sapphires are blue, regardless of the time. The difficulty is that, if we’ve only seen examples involving times t<Tt<T, then in principle we could also learn f(t,e)=e,if t<T,1−e,otherwise.f(t,e)= casese,&if t<T,\\ 1-e,&otherwise. cases From our perspective, however, the key is that this “grue” hypothesis is not 1-sparse, depending as it does on both input features. The “green” hypothesis, f(t,e)=ef(t,e)=e, is preferable because of its dependence on only one feature. T011Time ttEmeraldness e Figure 1: Predictions for an emerald’s color over time. The green line represents the 1-sparse hypothesis f(t,e)=ef(t,e)=e, while the blue dashed line represents the grue hypothesis which depends on both e and t. In some instances, however, features may not so clearly represent distinguished concepts. The coordinate basis chosen to represent the data may be arbitrary: the same data may appear different under bases which are rotations of the conventional basis. Indeed, in modern neural nets, the first layer often applies an arbitrary linear transformation of the input data, which would destroy any basis-dependent information. Occam’s Razor intuitively should choose a notion of simplicity which does not change depending on an arbitrary choice of conventional basis. Subspace juntas provide a basis-robust answer: they formalize the idea that only a few degrees of freedom matter, even if the information is distributed across many coordinates. 1.2 Our Results We give a PAC-style explanation for when out-of-distribution (OOD) generalization should succeed. Sparse hypotheses. Let f be the ground truth and h be the learned hypothesis. When f is k-sparse (i.e., depending on at most k out of n features) and we restrict our attention to k-sparse hypotheses, we show that OOD transfer holds to any test distribution ′D that matches (or approximately matches) the training distribution D on the features that f and h actually use, even if ′D differs arbitrarily on all other features. Concretely, after m=O~(d+klognϵ)m= O\! ( d+k nε ) training samples, with high probability every k-sparse hypothesis consistent with the training samples has error at most ϵε, not only on D but on all such distributions ′D (Theorems 3 and 4). Here d is an upper bound on the VC-dimension of the underlying hypothesis family when restricted to any k features, and the additional klognk n term is the “price” of searching over which k features matter. Subspace juntas (basis-robust sparsity). We also develop a basis-invariant analogue of sparsity via subspace juntas. We prove the analogous OOD guarantee: if both f and h depend only on a subspace A, then (approximately) matching the distribution of the projection onto A between training and test distributions is sufficient for transfer (Theorems 5 and 6), even if the distributions differ arbitrarily in directions orthogonal to A. Finally, we discuss when these subspace-junta classes have finite VC-dimension, giving conditions (e.g., semi-algebraicity) under which one obtains explicit polynomial VC bounds. 2 Related Work There has been a great deal of recent technical work on OOD generalization—the vast majority of it experimental, focused on predicting when OOD generalization will or will not succeed in practice, and helping it succeed more often (Wang et al., 2023; Zhou et al., 2022; Gulrajani and Lopez-Paz, 2021; Sagawa et al., 2020). To the best of our knowledge, few papers have sought to identify principles that explain the success of OOD across a wide range of contexts, at a level analogous to the foundational in-distribution generalization principles identified by Valiant (Valiant, 1984) and Blumer et al. (Blumer et al., 1989) in the 1980s. One exception is the field of domain adaptation, which began with the work of Ben-David et al. (Ben-David et al., 2006, 2010a). They show general bounds on the test error using the training error and a discrepancy term, which measures how well a hypothesis class can distinguish the training and test distributions. The result of Ben-David et al. shows that OOD generalization succeeds if no hypothesis class can distinguish the training distribution from the test distribution with large bias. Unfortunately, this condition is overly strong; it seems virtually never to be satisfied in the cases we care about in practice. Similarly, while there have been several follow-up works (e.g. (Blitzer et al., 2007; Mansour et al., 2009; Redko et al., 2017, 2020)) which prove relevant bounds and algorithms incorporating the discrepancy distance term, these bounds can prove too conservative to be useful in settings where the distributions differ greatly on irrelevant coordinates. The discrepancy term can be maximal even when OOD generalization is intuitively straightforward (e.g. in our toy example where a single pixel flips between training and test), rendering the bounds vacuous. Impossibility results such as (Ben-David et al., 2010b) show that we cannot guarantee generalization without some relationship between the training and test distributions. We address this with a different sufficient condition, guaranteeing OOD generalization whenever the train and test distributions approximately overlap on the coordinates or subspace which the learned hypothesis and the ground truth depend on, allowing for arbitrary behavior elsewhere. Another line of work tackles OOD generalization by formalizing notions of invariance across multiple training environments. For instance, invariant risk minimization (Arjovsky et al., 2019) proposes learning a data representation such that the same optimal hypothesis can be shared across all training environments. More recent work, such as that of Ye et al. (Ye et al., 2021), has aimed to provide bounds for domain generalization by quantifying how the invariance of learned features on several training environments translates to test environments via an expansion function. Rather than proposing an invariance learning objective or relying on multiple environments, our results give a PAC-style sufficient condition for OOD generalization. Finally, our sparsity assumptions relate to the classical study of learning a few relevant variables (juntas, see for example (Blum, 1994; Mossel et al., 2004)) and a relevant low dimensional subspace (subspace juntas, see for example (Blum and Kannan, 1997; Vempala and Xiao, 2013; Arriaga and Vempala, 2006)). While these mainly address finding efficient algorithms for learning these functions under distributional assumptions such as uniformity or Gaussianity, we use sparsity and dependence on a low-dimensional subspace primarily to formalize Occam’s Razor style arguments and to cleanly state sufficient conditions for OOD generalization. 3 Preliminaries We introduce some notation and results from PAC learning theory which will be useful. Definition 1. Let S be a sample space, and let ℋH be a class of functions h:S→0,1h:S→\0,1\. We say that ℋH shatters a set X=x1,…,xk⊆SX=\x_1,...,x_k\ S if for all 2k2^k possible choices for h(x1),…,h(xk)h(x_1),...,h(x_k), there exists an h∈ℋh consistent with those choices. Then the VC-dimension of ℋH, or VCdim(ℋ)VCdim(H), is the size k of the largest set shattered by ℋH (or VCdim(ℋ)=∞VCdim(H)=∞ if there is no maximum). Lemma 1 (Sauer’s Lemma). Let S be a set of size n and let ℋH be a class of functions h:S→0,1h:S→\0,1\. Then |ℋ|≤∑i=0VCdim(ℋ)(ni).|H|≤ _i=0^VCdim(H) ni. Using Lemma 1, Blumer et al. proved the following famous result. Theorem 1. Let S be a sample space, let D be a distribution over S, and let ϵε, δ>0δ>0. Let ℋH be a hypothesis class, consisting of hypotheses h:S→0,1h:S→\0,1\ and let f∈ℋf be the “ground truth.” Then there exists a constant C such that, for all m≥CVCdim(ℋ)ϵlog1δϵm≥ CVCdim(H)ε 1δε the following holds. With probability at least 1−δ1-δ over samples x1,…,xmx_1,...,x_m drawn independently from D, any hypothesis h∈ℋh such that h(xi)=f(xi)h(x_i)=f(x_i) for all i∈[m]i∈[m] “generalizes,” in the sense that Prx∼[h(x)=f(x)]≥1−ϵ. _x [h(x)=f(x)]≥ 1-ε. 3.1 Shifting between Distributions We now take a tiny first step towards OOD generalization by introducing a quantity which measures the worst case probability amplification for any event between two distributions. This allows us to understand how much more likely a rare bad event in one distribution might become in another distribution. This notion is also defined in binary hypothesis testing by (Polyanskiy et al., 2010, Eq. 100), but we use it here for the purpose of understanding distribution shift for OOD generalization. Definition 2. Given two distributions D and ′D over the same sample space S, we define α,′(ϵ) _D,D (ε) to be the infimum, over all events E with Pr′[E]≥ϵ _D [E]≥ε, of Pr[E] _D[E]. Note that if S is finite, then α,′(ϵ)>0 _D,D (ε)>0 for all ϵ>0ε>0 if and only if the support of D contains the support of ′D . In general, for any ϵε less than the probability mass contained in the support of ′D but not in the support of D, we will have α,′(ϵ)=0 _D,D (ε)=0. Intuitively, α,′(ϵ) _D,D (ε) is the function that converts small probabilities in ′D to the corresponding small probabilities in D. If we are being trained on samples from D, and will later be tested on samples from ′D and we want to catch bad events with probability at least ϵε in ′D , then we need to catch bad events with probability at least α,′(ϵ) _D,D (ε) in D. This quantity is not necessarily symmetric. To illustrate, let S=ℝ≥0S=R_≥ 0, let D be the uniform distribution over [0,K][0,K], and let ′D be exponentially distributed with mean 1. Then for all ϵ∈[0,1]ε∈[0,1], α,′(ϵ)=0,if ϵ≤e−K1Kln11−ϵ+e−Kotherwise, _D,D (ε)= cases0,&if ε≤ e^-K\\ 1K 11-ε+e^-K&otherwise, cases while α,′(ϵ)=e−(1−ϵ)K−e−K. _D,D (ε)=e^-(1-ε)K-e^-K. We now prove a generalization of Theorem 1 that applies even when the training distribution D and test distribution ′D are different, so long as α,′(ϵ)>0 _D,D (ε)>0 for all ϵ>0ε>0. Theorem 2. Let S be a sample space, let ,′D,D be two distributions over S, and let ϵ,δ>0ε,δ>0. Let ℋH be a hypothesis class, consisting of hypotheses h:S→0,1h:S→\0,1\, and let f∈ℋf be the “ground truth.” Then there exists a constant C such that, for all m≥C⋅VCdim(ℋ)α,′(ϵ)log1δ⋅α,′(ϵ),m≥ C·VCdim(H) _D,D (ε) 1δ· _D,D (ε), the following holds. With probability at least 1−δ1-δ over samples x1,…,xmx_1,...,x_m drawn independently from D, any hypothesis h∈ℋh such that h(xi)=f(xi)h(x_i)=f(x_i) for all i∈[m]i∈[m] “generalizes to ′D ,” in the sense that Prx∼′[h(x)=f(x)]≥1−ϵ. _x [h(x)=f(x)]≥ 1-ε. Proof. Let h∈ℋh be any hypothesis such that Prx∼′[h(x)≠f(x)]≥ϵ. _x [h(x)≠ f(x)]≥ε. Then by definition of α,′(ϵ) _D,D (ε), we have Prx∼[h(x)≠f(x)]≥α,′(ϵ). _x [h(x)≠ f(x)]≥ _D,D (ε). But this is the only “input” that the proof of Theorem 1 needs, and means that we can redo that proof with α,′(ϵ) _D,D (ε) in place of ϵε. ∎ Unfortunately, Theorem 2 does not cover most cases of OOD generalization that we care about in practice, where we really might have α,′(ϵ)=0 _D,D (ε)=0—that is, where the test distribution ′D might include points that never occurred at all in the training distribution D. This motivates us to consider more structured sample spaces, in which each sample point is divisible into n features. We then consider pairs of distributions ,′D,D that overlap on some features but could be arbitrarily far apart on other features. 4 Sparse Hypotheses Formally, our sample space will now have the form SnS^n, where S is the feature space and n is the number of features. We consider hypothesis classes of the form ℋ=(ℋk)k≥1H=(H_k)_k≥ 1, where each ℋkH_k consists of functions h:Sk→0,1h:S^k→\0,1\. We then let ℋ^k H_k, the class of k-sparse hypotheses, consist of all functions h^:Sn→0,1 h:S^n→\0,1\ that have the form h^(x1,…,xn)=h(xi(1),…,xi(k)), h(x_1,...,x_n)=h(x_i(1),...,x_i(k)), for some h∈ℋkh _k and some distinct i(1),…,i(k)∈[n]i(1),...,i(k)∈[n]. And we let ℋ^:=(ℋ^k)k≥1 H:=( H_k)_k≥ 1. To analyze these classes of sparse hypotheses, we first need a technical lemma. The bound on the VC-dimension of a union of hypothesis classes with bounded VC-dimension is standard (e.g. (Shalev-Shwartz and Ben-David, 2014)), but for completeness we provide a proof with explicit constants. Lemma 2. Let S be a sample space, and let ℋ1,…,ℋMH_1,...,H_M be classes of hypotheses h:S→0,1h:S→\0,1\ such that VCdim(ℋi)≤dVCdim(H_i)≤ d for all i∈[M]i∈[M]. Let ℋ:=ℋ1∪…∪ℋMH:=H_1∪... _M. Then VCdim(ℋ)≤4d+10lnM.VCdim(H)≤ 4d+10 M. Proof. Let D=VCdim(ℋ)D=VCdim(H). Set L:=D2−dL:= D2-d, so that D=2(d+L)D=2(d+L), and note that we can assume L≥0L≥ 0, since otherwise we are done. By definition, there exist sample points x1,…,xD∈Sx_1,...,x_D∈ S such that for all 2D2^D possible strings y=y1⋯yD∈0,1Dy=y_1· y_D∈\0,1\^D, there exists a hypothesis hy∈ℋh_y such that hy(x1)=y1,…,hy(xD)=yDh_y(x_1)=y_1,...,h_y(x_D)=y_D. By counting, clearly there exists an i∗i^* such that hy∈ℋi∗h_y _i^* for at least 2D/M2^D/M values of y. So then 2DM≤∑i=0d(Di)≤2Dexp(−L22D) 2^DM≤ _i=0^d Di≤ 2^D (- L^22D ) where the first inequality uses Lemma 1 (Sauer’s Lemma) and the second uses Chernoff. Solving, we get L≤2DlnML≤ 2D M, so D2−d≤2DlnM, D2-d≤ 2D M, or solving the quadratic and using the arithmetic-geometric mean inequality, D≤2d+4lnM+4ln2M+dlnM≤4d+10lnM.D≤ 2d+4 M+4 ^2M+d M≤ 4d+10 M. ∎ Lemma 2 has the following immediate corollary. Corollary 1. Let S be a sample space, and let ℋ=(ℋk)k≥1H=(H_k)_k≥ 1 be a class of sparse hypotheses. Then for all k, VCdim(ℋ^k)≤4⋅VCdim(ℋk)+10klnn.VCdim( H_k)≤ 4·VCdim(H_k)+10k n. Proof. The class ℋ^k H_k is the union of (nk)≤nk nk≤ n^k copies of ℋkH_k, one for each list of k distinct features in [n][n]. The result now follows from Lemma 2. ∎ We introduce two more bits of notation. First, given a hypothesis h:Sn→0,1h:S^n→\0,1\, let Feat(h)⊆[n]Feat(h) [n] be the set of features on which h non-trivially depends. So in particular, if h is k-sparse then |Feat(h)|≤k|Feat(h)|≤ k. Second, given a distribution D over SnS^n as well as a subset A⊆[n]A [n] of features, we let AD_A denote D marginalized to A. We can now prove our first OOD generalization theorem that cares about feature structure. Theorem 3. Let S be a feature space, let n be the number of features, let D be a distribution over SnS^n, and let ϵ,δ>0ε,δ>0. Let ℋ=(ℋk)k≥1H=(H_k)_k≥ 1 be a class of k-sparse hypotheses over S. Let f:Sn→0,1f:S^n→\0,1\ be the “ground truth,” and assume f∈ℋ^kf∈ H_k for some fixed sparsity k. Then there exists a constant C such that, for all m≥CVCdim(ℋk)+klognϵlog1δϵm≥ C VCdim(H_k)+k nε 1δε the following holds. With probability at least 1−δ1-δ over x1,…,xmx_1,...,x_m drawn independently from D, any hypothesis h∈ℋ^kh∈ H_k such that h(xi)=f(xi)h(x_i)=f(x_i) for all i∈[m]i∈[m] “generalizes out of distribution,” in the sense that Prx∼′[h(x)=f(x)]≥1−ϵ, _x [h(x)=f(x)]≥ 1-ε, for all distributions ′D such that A′=AD_A =D_A, where A:=Feat(h)∪Feat(f)A:=Feat(h) (f). Proof. Let B:=[n]−AB:=[n]-A so that we can represent any x∈Snx∈ S^n as (xA,xB)(x_A,x_B), where xA=(xi)i∈Ax_A=(x_i)_i∈ A and xB=(xi)i∈Bx_B=(x_i)_i∈ B. Also, given some xAx_A let B(xA)D_B(x_A) and B′(xA)D_B (x_A) be the probability distributions over xBx_B induced by D and ′D respectively after we condition on xAx_A. Then we have Prx∼′[h(x)=f(x)] _x [h(x)=f(x)] =PrxA∼A′xB∼B′(xA)[h(xA,xB)=f(xA,xB)] = _ subarraycx_A _A \\ x_B _B (x_A) subarray[h(x_A,x_B)=f(x_A,x_B)] =PrxA∼AxB∼B′(xA)[h(xA,xB)=f(xA,xB)] = _ subarraycx_A _A\\ x_B _B (x_A) subarray[h(x_A,x_B)=f(x_A,x_B)] =PrxA∼AxB∼B(xA)[h(xA,xB)=f(xA,xB)] = _ subarraycx_A _A\\ x_B _B(x_A) subarray[h(x_A,x_B)=f(x_A,x_B)] =Prx∼[h(x)=f(x)] = _x [h(x)=f(x)] where the second line follows from A=A′D_A=D_A , and the third line follows because neither h nor f depend on xBx_B. The result now follows from Theorem 1 combined with Corollary 1. ∎ Finally, we combine Theorems 2 and 3 into a single statement. Theorem 4. Let S be a feature space, let n be the number of features, let D be a distribution over SnS^n, and let ϵ,δ,α>0ε,δ,α>0. Let ℋ=(ℋk)k≥1H=(H_k)_k≥ 1 be a class of k-sparse hypotheses over S. Let f:Sn→0,1f:S^n→\0,1\ be the “ground truth,” and assume f∈ℋ^kf∈ H_k for some fixed sparsity k. Then there exists a constant C such that, for all m≥CVCdim(ℋk)+klognαlog1δαm≥ C VCdim(H_k)+k nα 1δα the following holds. With probability at least 1−δ1-δ over x1,…,xmx_1,...,x_m drawn independently from D, any hypothesis h∈ℋ^kh∈ H_k such that h(xi)=f(xi)h(x_i)=f(x_i) for all i∈[m]i∈[m] “generalizes out of distribution,” in the sense that Prx∼′[h(x)=f(x)]≥1−ϵ _x [h(x)=f(x)]≥ 1-ε for all distributions ′D such that αA,A′(ϵ)≥α _D_A,D_A (ε)≥α, where A:=Feat(h)∪Feat(f)A:=Feat(h) (f). 5 Subspace Juntas Explaining out of distribution generalization in terms of sparse hypotheses can only give us basis-dependent explanations, however. To deal with this, we introduce the idea of subspace juntas, which instead of being dependent on a few features, is dependent on a low-dimensional subspace of the input. This is a natural generalization, since we recover sparse hypotheses by choosing the subspace to be the span of the standard basis vectors corresponding to the relevant features of the hypothesis. Subspace juntas are motivated by the idea that while the input space may be high-dimensional, we would like to find a low-dimensional relevant subspace hidden in the input space. For example, we would like to consider a neural network as a function of WxWx after the first layer of weights has been applied, which allows us to project from the higher d-dimensional input space to a k-dimensional subspace. The projection allows the class of these functions to be basis independent. Definition 3 (Subspace Junta). A function f:ℝn→0,1f:R^n→\0,1\ is a k-subspace junta (where k≤nk≤ n) if there exists W∈ℝk×nW ^k× n and a function g:ℝk→0,1g:R^k→\0,1\ such that f(x)=fW(x)=g(Wx)∀x∈ℝn.f(x)=f_W(x)=g(Wx) ∀x ^n. We would like to prove the analogous statements to the theorems for k-sparse hypotheses in the previous section. Instead of taking A to be the union of features of f and h, we let f(x)=g∗(W∗x)f(x)=g^*(W^*x) and h(x)=g(Wx)h(x)=g(Wx), and take A to be the span of the row vectors of W and W∗W^*. Then, we require that for the training distribution D and the test distribution ′D , the projections of D are equal. We replace the VC-dimension in the lower bound on the number of required samples m with the VC-dimension bound for k-subspace juntas instead of k-sparse hypotheses. Theorem 5. Let S=ℝS=R be the feature space, where n is the number of features, D a distribution on ℝnR^n, and let ϵ,δ>0ε,δ>0. Let ℱF be a class of k-subspace juntas over ℝnR^n. Let f:ℝn→0,1f:R^n→\0,1\ be the ground truth function, and assume that f(x)=g∗(W∗x)∈ℋf(x)=g^*(W^*x) . Then there exists a constant C such that for all m≥C⋅VCdim(ℱ)ϵlog1δϵ,m≥ C· VCdim(F)ε 1δε, the following holds. With probability at least 1−δ1-δ over m samples x1,…,xmx_1,…,x_m drawn independently from D, any hypothesis h∈ℋh such that h(xi)=f(xi)h(x_i)=f(x_i) for all i∈[m]i∈[m] has low error on the test distribution, so that Prx∼′[h(x)=f(x)]≥1−ϵ, _x [h(x)=f(x)]≥ 1-ε, for all distributions ′D such that the distribution of PAxP_Ax where x∼x is equal to the distribution of PAx′P_Ax where x′∼′x , where A:=span(w1,…,wk,w1∗,…,wk∗)A:=span(w_1,…,w_k,w_1^*,…,w_k^*), and PAP_A is the projection onto A. Proof. Since A contains the span of the row vectors of W and of the row vectors of W∗W^*, then for any vector x we have Wx=W(PAx)Wx=W(P_Ax) and W∗x=W∗(PAx)W^*x=W^*(P_Ax). Then h(x)h(x) and f(x)f(x) depend only on the projection of x onto A, so that h(x) h(x) =g(Wx)=g(WPAx) =g(Wx)=g(WP_Ax) f(x) f(x) =g∗(W∗x)=g∗(W∗PAx) =g^*(W^*x)=g^*(W^*P_Ax) Then we have Prx∼[h(x)=f(x)] _x [h(x)=f(x)] =Prx∼[g(WPAx)=g∗(W∗PAx)] = _x [g(WP_Ax)=g^*(W^*P_Ax)] =Prx′∼′[g(WPAx′)=g∗(W∗PAx′)] = _x [g(WP_Ax )=g^*(W^*P_Ax )] =Prx′∼′[g(Wx′)=g∗(W∗x′)] = _x [g(Wx )=g^*(W^*x )] =Prx′∼′[h(x′)=f(x′)]. = _x [h(x )=f(x )]. The second line follows from the assumption that the distribution of PAxP_Ax where x∼x is equal to the distribution of PAx′P_Ax where x′∼′x , and the third line follows because W and W∗W^* are each in the span of A. ∎ We can then combine Theorem 5 with Theorem 2 to get a more general statement. Theorem 6. Let S=ℝS=R be the feature space, where n is the number of features, D a distribution on ℝnR^n, and let ϵ,δ,α>0ε,δ,α>0. Let ℱF be a class of k-subspace juntas over ℝnR^n. Let f:ℝn→0,1f:R^n→\0,1\ be the ground truth function, and assume that f(x)=g∗(W∗x)f(x)=g^*(W^*x). Then there exists a constant C such that for all m≥C⋅VCdim(ℱ)αlog1δα,m≥ C· VCdim(F)α 1δα, the following holds. With probability at least 1−δ1-δ over m samples x1,…,xmx_1,…,x_m drawn independently from D, any hypothesis h∈ℋh such that h(xi)=f(xi)h(x_i)=f(x_i) for all i∈[m]i∈[m] has low error on the test distribution, so that Prx∼′[h(x)=f(x)]≥1−ϵ, _x [h(x)=f(x)]≥ 1-ε, for all distributions ′D such that αA,A′≥α _D_A,D_A ≥α, where A:=span(w1,…,wk,w1∗,…,wk∗)A:=span(w_1,…,w_k,w_1^*,…,w_k^*). Examples of k-subspace juntas. If we allow g to come from the class G of all functions from ℝk→0,1R^k→\0,1\, the VC-dimension of the class ℱF of k-subspace juntas would be infinite, rendering Theorem 6 meaningless. Therefore, we would like to give the analogous statement to Corollary 1 by answering the following question: Question 1. Let ℱF be a class of k-subspace juntas such that for each function f:ℝn→0,1f:R^n→\0,1\ in ℱF, the associated function g:ℝk→0,1g:R^k→\0,1\ such that f(x)=g(Wx)f(x)=g(Wx) belongs to a class G with VC-dimension ≤d≤ d. What is an upper bound on the VC-dimension of ℱF in terms of n,k,dn,k,d? Note that we cannot directly apply Lemma 2, as we would be taking an infinite union corresponding to the arbitrary choice for W. There are some instantiations of G where we can get VC-dimension bounds following from those of well known classes. For instance, by taking G to be the class of halfspaces in ℝkR^k, which has VC-dimension k+1k+1, we have a bound on the VC-dimension of ℱF because it is the set of halfspaces in ℝnR^n, which has VC-dimension n+1n+1. We can also consider other classes for G such as polynomial threshold functions (PTFs). We can classically get a VC-dimension bound for PTFs of degree p by considering the monomials of the polynomial as new features (feature expansion), so that we can view it as a halfspace in the new features. Then G would be the class of degree p PTFs in ℝkR^k and would have VC-dimension at most (k+p)+1 k+pp+1, while ℱF would be a subset of degree p PTFs in ℝnR^n and would have VC-dimension at most (n+p)+1 n+pp+1. However, it turns out that there is a counterexample to the general statement of 1 based on a classical construction (see (Anthony and Bartlett, 2009, Chapter 7.2) for a similar example). restatable claimCounterexample Let =gG=\g\ where g:ℝ→0,1g:R→\0,1\ and g(x)=1if ⌊x⌋≡1(mod2)0otherwise.g(x)= cases1&if x ≡ 1 2\\ 0&otherwise. cases Let ℱF be the class consisting of all functions of the form f(x)=g(w⋅x)f(x)=g(w· x) where w∈ℝnw ^n and ‖w‖=1 \|w \|=1. Then the VC-dimension of G is 0, and the VC-dimension of ℱF is ∞. −5-5−4-4−3-3−2-2−1-1112233445511g(x)=1⌊x⌋ is odd0⌊x⌋ is eveng(x)= cases1& x is odd\\ 0& x is even casesxxyy Figure 2: g(x)g(x), the square wave function. Proof. Since G contains a single fixed function, it cannot shatter any points and has VC-dimension 0. Let w vary over the unit circle. Then for any x∈ℝnx ^n, we have w⋅x=‖w‖‖x‖cosθw=‖x‖cosθw· x= \|w \| \|x \| _w= \|x \| _w, where θw _w is the angle between x and w. Consider the following m points in ℝnR^n: xi=(2i,0,…,0),∀i∈1,2,…,m.x_i=(2^i,0,…,0), ∀ i∈\1,2,…,m\. These satisfy ‖xi‖=2i \|x_i \|=2^i. For any given labeling of these points (x1,y1),…,(xm,ym)(x_1,y_1),…,(x_m,y_m) where yi∈0,1y_i∈\0,1\, choose w on the unit circle so that θw=arccos(y12+y222+…+ym2m). _w= ( y_12+ y_22^2+…+ y_m2^m ). 224488wθw _wxxyy Figure 3: For m=3m=3 and n=2n=2, points xix_i along the x-axis and the weight vector w, where the angle θw _w is the angle between the x-axis (since all xix_i lie on it) and w. We choose this θw _w so that cosθw _w encodes the yiy_i labels in binary, given by (0.y1y2…ym)2(0.y_1y_2… y_m)_2. Multiplying by ‖xi‖=2i \|x_i \|=2^i effectively bit shifts so that the last digit in front of the decimal point is yiy_i. That is, for a given point xix_i, w⋅xw· x evaluates to ‖xi‖cosθw \|x_i \| _w =2i⋅(y12+y222+⋯+ym2m) =2^i· ( y_12+ y_22^2+·s+ y_m2^m ) =2i−1⋅y1+⋯+2⋅yi−1+yi+2i(yi+12i+1+⋯+ym2m) =2^i-1· y_1+·s+2· y_i-1+y_i+2^i ( y_i+12^i+1+·s+ y_m2^m ) =(y1y2⋯yi.yi+1⋯ym)2 =(y_1y_2·s y_i.y_i+1·s y_m)_2 The floor of this function is 2i−1⋅y1+…+2⋅yi−1+yi=(y1⋯yi)2,2^i-1· y_1+…+2· y_i-1+y_i=(y_1·s y_i)_2, whose parity only depends on yiy_i. Then by definition of g, we will have g(w⋅xi)=yig(w· x_i)=y_i. The number of points thus shattered can be arbitrarily large, so ℱF has infinite VC-dimension. ∎ The above example demonstrates that subspace juntas may have infinite VC-dimension even if the inner class G has bounded VC-dimension. This is unavoidable: using similar constructions, it is known that there are neural networks whose activation functions are smooth, bounded, and monotonically increasing, which have infinite VC-dimension. Indeed, there are examples where the network only has two layers and two neurons in the first layer, which has activation functions satisfying being convex to the left of zero and concave to the right in addition to the properties listed above which still has infinite VC-dimension (Anthony and Bartlett, 2009, Chapter 7.2). One of the largest classes G that make the corresponding class of subspace juntas ℱF to have finite VC-dimension is the class of (indicators of) semi-algebraic sets. This class includes all neural networks whose activation functions are piecewise polynomial (thus including halfspaces and ReLUs). Definition 4 (Semi-algebraic set, see e.g. (Chernikov, 2017), (Anthony and Bartlett, 2009)). Let t,ℓ,n:=g:ℝn→0,1:g(x)=b(p1(x),…,pt(x)),S_t, ,n:=\g:R^n→\0,1\:g(x)=b(p_1(x),…,p_t(x))\, where b:0,1t→0,1b:\0,1\^t→\0,1\ is an arbitrary boolean function, and pi:ℝn→0,1p_i:R^n→\0,1\ are degree ≤ℓ≤ polynomial threshold functions. That is, pi(x)=sign(qi(x))p_i(x)=sign(q_i(x)) for some real polynomial qi:ℝn→ℝq_i:R^n with degree ≤ℓ≤ . We say t,ℓ,nS_t, ,n is a semi-algebraic subset of ℝnR^n. Theorem 7 (Chernikov (2017), Chapter 1). Let t,ℓ,nS_t, ,n be a semi-algebraic set as defined above. Then, its VC-dimension can be upper bounded as follows: VCdim(t,ℓ,n)≤2t(n+ℓ)log(t(t+1)(n+ℓ)).VCdim(S_t, ,n)≤ 2t n+ (t(t+1) n+ ). Thus, the VC-dimension bound is polynomial in t and n for some fixed ℓ . Now, we consider the definition of subspace juntas with respect to semi-algebraic sets. Definition 5. The class of semi-algebraic subspace juntas is written as ℱn,ℓ,k,t:=f:ℝn→0,1:f(x)=b(p1(Wx),…,pt(Wx))F_n, ,k,t:=\f:R^n→\0,1\:f(x)=b(p_1(Wx),…,p_t(Wx))\ where b:0,1t→0,1b:\0,1\^t→\0,1\ is an arbitrary boolean function, pi:ℝk→0,1p_i:R^k→\0,1\ are degree ≤ℓ≤ polynomial threshold functions, and W∈ℝk×nW ^k× n is an arbitrary real matrix. Note that ℱn,ℓ,k,tF_n, ,k,t is a subset of t,ℓ,nS_t, ,n, because we can consider any degree ℓ polynomial p(Wx)p(Wx) as a degree ℓ polynomial q(x)q(x). Thus ℱn,ℓ,k,tF_n, ,k,t is still a semi-algebraic set, so its VC-dimension is also bounded by Theorem 7. This establishes that ℱn,ℓ,k,tF_n, ,k,t has finite VC dimension, but we can obtain the following tighter bound which has an explicit dependence on k and a linear dependence on n. Theorem 8. Let ℱn,ℓ,k,tF_n, ,k,t be a class of semi-algebraic subspace juntas as defined above. Then, its VC-dimension can be upper bounded as follows: VCdim(ℱn,ℓ,k,t)≤2(kn+t(k+ℓ))log(12t(ℓ+1)).VCdim(F_n, ,k,t)≤ 2 (kn+t k+ ) (12t( +1)). This bound is linear in n rather than scaling like nℓn . Since an upper bound on VC-dimension corresponds to a smaller sample complexity required to learn a class, we see that the case k≪nk n is useful in efficiently learning subspace juntas even in spaces with large input dimension. We note that the linear dependence on n of the VC-dimension bound for ℱn,ℓ,k,tF_n, ,k,t is unavoidable. For example, take ℓ=1,k=1,t=1 =1,k=1,t=1, and b:0,1→0,1b:\0,1\→\0,1\ to be the identity function. Consider the functions f∈ℱn,1,1,1f _n,1,1,1 where p is a degree 11 PTF sign(w⋅x)sign(w· x) for an arbitrary w∈ℝnw ^n. Then these form the class of all halfspaces in ℝnR^n, for which the VC-dimension bound of n+1n+1 is known to be tight. Since this is a subset of ℱn,1,1,1F_n,1,1,1, the overall class has a VC-dimension lower bounded by n+1n+1. 6 Open Problems We have proposed a PAC-style framework for explaining out of distribution generalization through sparsity. This formalizes Occam’s Razor as a natural inductive bias, explaining when we can expect generalization even when the training and test distributions differ entirely on irrelevant coordinates. Are there other natural generalizations of the PAC learning theory or VC-dimension that have explanatory power for OOD generalization? We also note the following directions for future work: Improved VC-dimension bound for semi-algebraic subspace juntas. Our current bound on VC-dimension for semi-algebraic subspace juntas is a specific instantiation of a more general VC bound. Is it possible to obtain a tighter bound for the VC-dimension of semi-algebraic subspace juntas? Can a matching lower bound be obtained? Is the dependence on k optimal? Incorporating max margin into OOD. From the perceptron learning algorithm and the perceptron convergence theorem to SVMs, the concept of maximum margin has been foundational and essential in machine learning. Even in more recent work on the softmax-attention model in transformer architecture shows implicit bias towards a max-margin solution (Tarzanagh et al., 2023). Can we formally determine the role of max-margin in OOD generalization? Explicit algorithms and addressing noise. Our theorems primarily answer statistical learning theory questions, addressing when we have enough samples and under which distributional assumptions we can learn sparse hypotheses and subspace juntas. Natural directions for future work would be to find explicit algorithms for recovering the relevant subspace and consider learning in the agnostic setting, as we have assumed that all examples are perfectly realized by a ground truth function. Acknowledgments This work was begun when one of us (SA) was at OpenAI. We are grateful to Coefficient Giving for supporting this research. We thank Ilya Sutskever, Lionel Levine, Adam Klivans, Eric Price, Harvey Lederman, and Boaz Barak for helpful discussions. References [1] M. Anthony and P. L. Bartlett (2009) Neural network learning: theoretical foundations. Cambridge University Press, Cambridge, UK. Note: Originally published in 1999 External Links: ISBN 978-0-521-11862-0 Cited by: Appendix A, §5, §5, Definition 4, Theorem 9. [2] M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz (2019) Invariant risk minimization. arXiv preprint arXiv:1907.02893. Cited by: §2. [3] R. I. Arriaga and S. Vempala (2006-05) An algorithmic theory of learning: robust concepts and random projection. Mach. Learn. 63 (2), p. 161–182. External Links: ISSN 0885-6125, Link, Document Cited by: §2. [4] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan (2010) A theory of learning from different domains. Machine Learning 79 (1), p. 151–175. External Links: Document, Link Cited by: §2. [5] S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira (2006) Analysis of representations for domain adaptation. In Advances in Neural Information Processing Systems 19 (NIPS 2006), p. 137–144. External Links: Link Cited by: §2. [6] S. Ben-David, T. Lu, T. Luu, and D. Pál (2010) Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS 2010), JMLR Workshop and Conference Proceedings, Vol. 9, p. 129–136. External Links: Link Cited by: §2. [7] J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. Wortman (2007) Learning bounds for domain adaptation. In Advances in Neural Information Processing Systems, J. Platt, D. Koller, Y. Singer, and S. Roweis (Eds.), Vol. 20, p. . External Links: Link Cited by: §2. [8] A. L. Blum and R. Kannan (1997) Learning an intersection of a constant number of halfspaces over a uniform distribution. Journal of Computer and System Sciences 54 (3), p. 371–380. External Links: Document Cited by: §2. [9] A. L. Blum (1994) Relevant examples and relevant features: thoughts from computational learning theory. Technical report Technical Report FS-94-02, AAAI Technical Report, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. Cited by: §2. [10] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth (1989-10) Learnability and the vapnik-chervonenkis dimension. J. ACM 36 (4), p. 929–965. External Links: ISSN 0004-5411, Link, Document Cited by: §1, §2. [11] A. Chernikov (2017) Model theory and combinatorics: chapter 2 (draft). Note: Lecture notes, last updated February 28, 2017 External Links: Link Cited by: Definition 4, Theorem 7. [12] N. Goodman (1955) Fact, fiction, and forecast. Harvard University Press, Cambridge, MA. Cited by: §1. [13] I. Gulrajani and D. Lopez-Paz (2021) In search of lost domain generalization. In International Conference on Learning Representations (ICLR), External Links: Link Cited by: §2. [14] Y. Mansour, M. Mohri, and A. Rostamizadeh (2009) Domain adaptation: learning bounds and algorithms. In Proceedings of The 22nd Annual Conference on Learning Theory (COLT 2009), Montréal, Canada. External Links: Link Cited by: §2. [15] E. Mossel, R. O’Donnell, and R. A. Servedio (2004) Learning functions of k relevant variables. Journal of Computer and System Sciences 69 (3), p. 421–434. Note: Preliminary version in STOC 2003 External Links: Link Cited by: §2. [16] Y. Polyanskiy, H. V. Poor, and S. Verdú (2010-05) Channel coding rate in the finite blocklength regime. IEEE Transactions on Information Theory 56 (5), p. 2307–2359. Cited by: §3.1. [17] I. Redko, A. Habrard, and M. Sebban (2017) Theoretical analysis of domain adaptation with optimal transport. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2017, p. 737–753. External Links: Document Cited by: §2. [18] I. Redko, E. Morvant, A. Habrard, M. Sebban, and Y. Bennani (2020) A survey on domain adaptation theory: learning bounds and theoretical guarantees. arXiv preprint arXiv:2004.11829. External Links: Link Cited by: §2. [19] S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang (2020) Distributionally robust neural networks. In International Conference on Learning Representations, Cited by: §2. [20] S. Shalev-Shwartz and S. Ben-David (2014) Understanding machine learning: from theory to algorithms. Cambridge university press, Cambridge, UK. Cited by: §4. [21] D. A. Tarzanagh, Y. Li, X. Zhang, and S. Oymak (2023) Max-margin token selection in attention mechanism. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Cited by: §6. [22] L. G. Valiant (1984-11) A theory of the learnable. Commun. ACM 27 (11), p. 1134–1142. External Links: ISSN 0001-0782, Link, Document Cited by: §1, §2. [23] S. Vempala and Y. Xiao (2013) Complexity of learning subspace juntas and ica. In 2013 Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, p. 182–186. External Links: Document Cited by: §2. [24] J. Wang, C. Lan, C. Liu, Y. Ouyang, T. Qin, W. Lu, Y. Chen, W. Zeng, and P. S. Yu (2023) Generalizing to unseen domains: a survey on domain generalization. IEEE Transactions on Knowledge and Data Engineering 35 (8), p. 8052–8072. External Links: Document, 2103.03097 Cited by: §2. [25] H. Ye, C. Xie, T. Cai, R. Li, Z. Li, and L. Wang (2021) Towards a theoretical framework of out-of-distribution generalization. In Advances in Neural Information Processing Systems, Vol. 34. External Links: Link Cited by: §2. [26] K. Zhou, Z. Liu, Y. Qiao, T. Xiang, and C. C. Loy (2022) Domain generalization: a survey. IEEE Transactions on Pattern Analysis and Machine Intelligence. External Links: Document, 2103.02503 Cited by: §2. Appendix A Proof of Theorem 8 We derive the VC-dimension bound on semi-algebraic subspace juntas by observing that they are an instantiation of the class considered in Theorem 8.3 of [1]. We first include the theorem statement here for completeness. Theorem 9 ([1], Theorem 8.3). Let H be a class of functions mapping from ℝd×ℝnR^d×R^n to ℝR so that for all x∈ℝn,h∈Hx ^n,h∈ H, the function a↦h(a,x)a h(a,x) is a polynomial on ℝdR^d of degree no more than r. Suppose that F is a t-combination of sign(H)sign(H); that is, for every f∈Ff∈ F, there exists a boolean function b:0,1t→0,1b:\0,1\^t→\0,1\ and functions h1,…,hkh_1,…,h_k in G such that for some parameter vector a∈ℝda ^d, we have f(x)=b(sign(h1(a,x)),…,sign(hk(a,x)))f(x)=b(sign(h_1(a,x)),…,sign(h_k(a,x))) for all x∈ℝnx ^n. Then VCdim(F)≤2dlog2(12tr).VCdim(F)≤ 2d _2(12tr). We now restate Theorem 8 here for convenience. Theorem 10 (Theorem 8, restated). Let ℱn,ℓ,k,tF_n, ,k,t be a class of semi-algebraic subspace juntas. Then, its VC-dimension can be upper bounded as follows: VCdim(ℱn,ℓ,k,t)≤2dlog(12t(ℓ+1)),VCdim(F_n, ,k,t)≤ 2d (12t( +1)), where d=kn+t(k+ℓ).d=kn+t k+ . Proof. First, we parameterize the class. Any f∈ℱn,ℓ,k,tf _n, ,k,t by definition can be written as f(x)=b(sign(q1(Wx)),…,sign(qt(Wx))),f(x)=b(sign(q_1(Wx)),…,sign(q_t(Wx))), where each qiq_i is a polynomial of degree ≤ℓ≤ corresponding to the PTFs in f. It can be parameterized by a vector a∈ℝda ^d, where a contains the knkn entries of W and the (k+ℓ) k+ coefficients of each of the t polynomials q1,…,qtq_1,…,q_t. This makes d=kn+t(k+ℓ)d=kn+t k+ the number of parameters stored in a. More specifically, let H be a class of functions mapping from ℝd×ℝnR^d×R^n to ℝR so that for all x∈ℝn,h∈Hx ^n,h∈ H, the function g(a):=h(a,x)g(a):=h(a,x) is a polynomial on ℝdR^d of degree r≤ℓ+1r≤ +1. Given f∈ℱn,ℓ,k,tf _n, ,k,t, choose the functions in H such that gi(a)=hi(a,x):=qi(Wx)g_i(a)=h_i(a,x):=q_i(Wx). Note that this satisfies the condition that gig_i is a polynomial of degree ≤ℓ+1≤ +1 on ℝdR^d, since qiq_i has degree ≤ℓ≤ and WxWx is linear in the elements of a, and the coefficients of qiq_i appear in a. Then, note that this parameterization of ℱn,ℓ,k,tF_n, ,k,t makes it a t-combination of sign(H)sign(H). Plugging in the appropriate parameters into Theorem 9, we get a bound of 2dlog(12t(ℓ+1))2d (12t( +1)), as above. ∎