Distribution shift continues to be a major barrier for deploying AI models, especially in the health and bioscience domains. By far the most common approach to modeling distribution shift (or domain adaptation) is to bound the performance of a classifier in terms of some notion of distance between the training and test distributions (Ben-David et al., 2006;Mansour et al., 2009). These distances, however, are computationally intractable to estimate, as they are defined in terms of an enumeration over all classifiers from some class. As such, learners constrained to run in polynomialtime obtain no guarantees on the performance of a classifier (without making strong assumptions on the test distribution).
A recent work of Klivans, Stavropoulos, and Vasilyan (Klivans et al., 2023) departs from this paradigm and defines a model of testable learning with distribution shift (TDS learning). In this model, a learner first runs a test on labeled samples drawn from training distribution D and unlabeled samples drawn from test distribution D ′ . No assumptions are made on D ′ . If the test accepts, the learner outputs a classifier that is guaranteed to have low error with respect to D ′ . Further, the test must accept (with high probability) whenever the marginal of D equals the marginal of D ′ . It is clear that this model generalizes the traditional PAC model of learning (where D always equals D ′ ), and, as described in Klivans et al. (2023), obtaining efficient algorithms seems considerably more challenging. Giving positive results for TDS learning with running times that match known results in the traditional PAC model is therefore a best-case scenario.
Here we focus on the intensely studied problem of learning intersections of halfspaces (or halfspace intersections) with respect to Gaussian distributions, where large gaps exist between the best known algorithms for TDS learning versus ordinary PAC learning. Our main contribution is a set of new positive results all of which greatly improve on prior work in TDS learning and in some cases match the best known bounds for PAC learning (see Tables 1 and 2 for precise statements of bounds). Our algorithm assumes that the training distribution contains at least an ϵ fraction of both positive and negative examples (ϵ-balanced), which turns out to be necessary, as we describe below.
Indeed, we provide the first set of SQ lower bounds for any problem in TDS learning (that was not already known in the traditional PAC model of learning). We show that no polynomialtime SQ algorithm can TDS learn a single halfspace unless the training distribution is ϵ-balanced. Further, we prove that no polynomial-time SQ algorithm can TDS learn the intersection of two general halfspaces, even if we assume the training distribution is ϵ-balanced. Taken together, these results considerably narrow the gap between efficient TDS learnability and PAC learnability for halfspace-based learning.
TDS Learning through Covering the Solution Space. Our upper bounds are based on the idea of constructing a set of candidate output hypotheses that has three properties: (1) it has small size, (2) it contains one hypothesis with low test error and (3) all of the hypotheses in the set have low training error. Once such a cover is constructed, a small set of unlabeled data from the test distribution is sufficient to ensure that all of the members of the cover have low training error. This is possible by estimating the discrepancy distance between the test marginal and the Gaussian, but only with respect to the members of the cover, i.e., estimating the maximum probability of disagreement between pairs of elements of the cover under the test marginal. Since the cover is small (by (1)), this can be done efficiently and since all of the hypotheses have low training error (by (3)), the test should accept in the absence of distribution shift. If the test accepts, then all of the members have low disagreement with one hypothesis with low test error (by (2)) and they, hence, have low test error as well. The learner may then output any member of the cover.
Constructing Covers for Halfspace Intersections. Our method for covering the solution space for TDS learning halfspace intersections is based on two main ingredients. The first ingredient is access to an algorithm that uses training data and retrieves a low-dimensional subspace that is O(k) (Vempala, 2010b) and is the best known bound for small k. We nearly match this bound in row two above and provide an incomparable result in row four. In row five, we improve on all of these bounds under a non-degeneracy assumption on the intersection of halfspaces; see the Related Work section for a discussion. Table 2: Statistical Query complexity (upper and lower) bounds for TDS Learning k-Halfspace Intersections under N d . No prior SQ lower bounds for any TDS learning problem were known. For the balance assumption, see Definition 17. For the non-degeneracy assumption, see Definition 26. Row 1 and the upper bound of row 4 are from Klivans et al. (2023).
All other results are from this work: Theorem 12 (row 2), Corollary 30 (row 3), Theorem 8 (row 4), Theorem 15 (row 5, lower bound), Corollary 32 (row 5, upper bound). The lower bounds of rows 4, 5 hold for d = O(ϵ -1/4 ).
guaranteed to approximately contain (in terms of angular distance) each of the normal vectors that define the ground truth intersection. See the Related Work section for a more detailed discussion on subspace recovery algorithms. The second ingredient is a local halfspace disagreement tester, namely, a tester that takes as input a vector (and unlabelled test data) and certifies that all of the vectors that are geometrically close to the input define halfspaces with low disagreement to the one defined by the input under the test distribution. Such testers have been proposed in the literature of testable learning Gollakota et al. (2023a,b) and TDS learning Klivans et al. (2023), but, we provide an additional one for the case of general halfspaces. Equipped with both of these ingredients, we use a Euclidean cover for the sphere in the low-dimensional subspace retrieved and run the disagreement tester on each vector in the cover. We form a cover of the solution space with the desired properties by forming all possible intersections of halfspaces with normals in the Euclidean cover and keeping only those with low training error.
For general halfspaces, we also use an additional moment-matching tester which ensures that halfspaces with very high bias can be safely omitted from the output hypothesis, because the test distribution is certified to be sufficiently concentrated in every direction. This is important, because the training data does not reveal enough information for such halfspaces and, hence, it is not guaranteed that their normals will be approximately contained in the retrieved subspace.
SQ Lower Bounds for TDS Learning from Lower Bounds for NGCA. We prove our statistical query (SQ) lower bounds by reducing appropriate distribution testing problems to TDS learning. The distribution testing problems we consider fall in the category of Non-Gaussian Component Analysis (NGCA) where a distinguisher has access to an unknown distribution and is asked to distringuish whether the distribution is Gaussian or it is Gaussian in all but one hidden direction where the marginal satisfies certain problem-specific conditions. Diakonikolas et al. (2023a) provide SQ lower bounds for various instantiations of the problem.
We show that a TDS learner for general halfspaces can distinguish the Gaussian from any distribution that has some non-negligible mass far from the origin along some hidden direction. We then construct a distribution that is Gaussian in all but one direction along which the marginal (1) exactly matches moments with the standard Gaussian up to some degree and (2) assigns non-negligible mass far from the origin. To show approximate moment matching, we use a mass transportation argument and for exact moment matching, we use an argument based on the theory of Linear Programming from Diakonikolas et al. (2023b). Under these conditions, a generic tool from Diakonikolas et al. (2023a) implies an SQ lower bound for the distinguishing problem we constructed and hence an SQ lower bound for TDS learning. A similar construction gives a lower bound for intersections of two general halfspaces. For intersections of two homogeneous halfspaces, we reduce the problem of anti-concentration detection (whose SQ lower bound is given in Diakonikolas et al. (2023a)) to the corresponding TDS learning problem.
Intersections of Halfspaces Learning intersections of halfspaces continues to be an important benchmark for algorithm design in learning theory with a long history of prior work (Long and Warmuth, 1994;Blum and Kannan, 1997;Klivans et al., 2004;Klivans and Sherstov, 2009;Klivans et al., 2009Klivans et al., , 2008;;Vempala, 2010b,a;Gopalan et al., 2012;Kane et al., 2013;Diakonikolas et al., 2018). Finding a fully polynomial-time algorithm for learning the intersection of k halfspaces in d dimensions to accuracy ϵ remains a notorious open problem, even in the case of noise-free PAC learning with respect to Gaussian marginals.
The most relevant works here are Vempala (2010b) and Vempala (2010a) which both attempt to recover the subspace spanned by the k normals of the relevant halfspaces. This type of subspace recovery is a crucial ingredient for our work here, as we describe in the Techniques subsection above. In Vempala (2010b), an algorithm with running time and sample complexity (dk/ϵ) O(k) is given for noise-free PAC learning with respect to log-concave marginals. In a follow-up work Vempala (2010a) claims an improved bound of (k/ϵ) O(k) poly(d). Unfortunately, this proof has a gap. In Appendix C.1 we provide a complete proof of a weaker result using the approach of Vempala (2010a), namely we obtain a 2 O(k 2 /ϵ 2 ) poly(d, k) time algorithm for intersections of homogeneous halfspaces. If we take a non-degeneracy assumption on the ground truth intersection (see Appendix C.2), we prove that the gap can be fixed and we recover the
For large values of k, the best known bound of d Õ(log k/ϵ 2 ) for PAC or agnostic learning is due to Klivans et al. (2008), obtained using the Gaussian surface area/Hermite analysis approach. For TDS learning, Klivans et al. (2023) gave an algorithm with running time d Õ(k 6 /ϵ 2 ) that is improper and outputs a polynomial threshold function as the final hypothesis. In addition to improving their bounds on run-time (as described in Table 1), the algorithm we present here is proper: our learner gives an intersection of k halfspaces as its output hypothesis.
Distribution Shift/Domain Adaptation The field of domain adaptation considers problems very similar to the model introduced here. A learner is presented with labeled training samples, unlabeled test samples, and is required to output a classifier with low test error. The learner in traditional domain adaptation, however, is not allowed to reject. The area is too broad for us to survey here, and we refer the reader to Redko et al. (2020) and references therein. We highlight the works of Ben-David et al. (2006) and Mansour et al. (2009), which provide sample complexity upper bounds for domain adaptation in terms of discrepancy distance. It is proved in Klivans et al. (2023) that the notion of discrepancy distance also provides sample complexity guarantees for TDS learning. The first set of efficient algorithms for domain adaptation without taking strong assumptions on the test distribution were given by Klivans et al. (2023). We also note related work due to Goldwasser et al. (2020); Kalai and Kanade (2021); Goel et al. (2023) on PQ learning, a model formally shown to be harder than TDS learning in Klivans et al. (2023).
Testable Learning Although both the Testable Learning framework due to Rubinfeld and Vasilyan (2023) and TDS learning allow a learner to reject unless a training set passes a test, the models address very different issues and are formally incomparable. In testable learning, the goal is to certify that an agnostic learner has succeeded (or reject). In particular, (1) testable learning is trivial in the realizable (noise-free) framework (recall in this paper we work exclusively in a noise-free setting) and (2) testable learning does not allow for distribution shift. For a further comparison of the models see Klivans et al. (2023). We do make use of some general techniques from testable learning, as we describe in the Techniques section.
For v ∈ R d , τ ∈ R, we call a function of the form x → sign(v • x) a homogeneous halfspace and a function of the form x → sign(v
, where w i are called the normals of the intersection and τ i the corresponding thresholds. Let N d be the standard Gaussian in d dimensions. For a subspace U , let proj U (w) be the orthogonal projection of a vector w on the subspace U .
Learning Setup. We focus on the framework of testable learning with distribution shift (TDS learning) defined by Klivans et al. (2023). In particular, for a concept class C ⊆ {R d → {±1}}, the learner A is given ϵ, δ ∈ (0, 1), a set S train of labelled examples of the form (x, f * (x)), where x ∼ D = N d and f * ∈ C, as well a set X test of unlabelled examples from an arbitrary test distribution D ′ and is asked to output a hypothesis h : R d → {±1} with the following guarantees.
(a) (Soundness.) With probability at least 1 -δ over the samples S train , X test we have:
If the learner A enjoys the above guarantees, then A is called an (ϵ, δ)-TDS learner for C w.r.t. N d . Since the probability of success can be amplified through repetition (see (Klivans et al., 2023, Proposition C.1)), in what follows, we will provide algorithms with constant failure probability.
Our first main result concerns the problem of TDS learning intersections of homogeneous halfspaces with respect to the Gaussian distribution. For a single homogeneous halfspace Klivans et al. (2023) showed that there is a fully polynomial-time TDS learner under Gaussian marginals. The learner crucially relied on the approximate recovery of the normal vector corresponding to the ground truth halfspace in terms of angular distance using training data. After obtaining a vector that is geometrically close to the ground truth, the learner used unlabelled test data to certify that any halfspace near the recovered one (and, hence, also the ground truth) does not significantly disagree with the recovered halfspace on the test distribution. Such a certificate can be obtained through appropriate localized testers that rely on low-degree moment estimation (introduced in the testable learning literature, see Gollakota et al. (2023a,b)).
We significantly generalize this approach beyond the case of a single halfspace and obtain improved TDS learners for intersections of any number of homogeneous halfspaces (as well as general halfspaces in Section 2.2). Our approach is once more to recover some information about the ground truth that can be measured in geometric terms. In particular, the appropriate notion of geometric recovery for the case of halfspace intersections is approximate subspace retrieval, namely, recovering a subspace that approximately contains all of the normals to the ground truth intersection, as defined below.
Definition 1 (Approximate Subspace Retrieval for Homogeneous Halfspaces) We say that algorithm A (ϵ, δ)-retrieves the relevant subspace for C (whose elements are homogeneous halfspace intersections) under N d if A, upon receiving at least m A examples of the form (x, f * (x)), where x ∼ N d and f * ∈ C, outputs, w.p. at least 1 -δ a subspace U such that for any normal w of f * we have ∥ proj U w∥ 2 ≥ 1 -ϵ.
It turns out that the idea of approximate subspace retrieval has been explored in the literature of standard PAC learning, as it can be used to provide strong PAC learning guarantees and proper algorithms. We may, therefore, use existing results on approximate subspace retrieval (see Appendix C) as a first step of our TDS learning algorithm. Once we have obtained a low-dimensional subspace that approximately contains all the normals, we (1) generate a small cover of the candidate solution space, (2) acquire (using unlabeled test examples) a certificate that the cover contains a hypothesis with low test error and (3) bound the discrepancy distance (notion from domain adaptation) of the test marginal with the Gaussian, but only with respect to the candidate solution space. We obtain the following result, whose full proof can be found in Section D.1.
Theorem 2 (TDS Learning Intersections of Homogeneous Halfspaces) Let C be a class whose elements are intersections of k homogeneous halfspaces on R d , ϵ ∈ (0, 1) and C ≥ 1 a sufficiently large constant. Assume that A ( ϵ 3 Ck 3 , 0.01)-retrieves the relevant subspace for C under N d with sample complexity m A . Then, there is an algorithm (Algorithm 3) that (ϵ, δ = 0.02)-TDS learns the class C, using m A + Õ(
dk 2 ϵ 2 ) labeled training examples and Õ( dk 2 ϵ 2 ) unlabelled test examples, calls A once, and uses additional time
Algorithm 1: Proper TDS Learner for Homogeneous Halfspace Intersections
Ck 3/2 and ϵ ′′ = ϵ 6 Ck 7 for some sufficiently large universal constant C ≥ 1. Run algorithm A on the set S train and let (v 1 , . . . , v k ) be its output. Let U be the subspace spanned by (v 1 , . . . , v k ) and consider the following sparse cover of U :
Before proving Theorem 2, we first describe how we can obtain the above algorithm A.
Approximate Subspace Retrieval. To approximately recover the relevant subspace, we apply results from PAC learning (see Vempala (2010a,b)), which we state in Appendix C. For example, Vempala (2010a) uses a Gaussian variance reduction lemma (see Lemma 18) which states that if we truncate the Gaussian distribution on the positive region of some intersection of homogeneous halfspaces, then the variance of the resulting distribution along the directions that define the normals of the intersection is bounded away below 1 (for directions orthogonal to the span of the normals, the variance is 1). Unfortunately, in the original proof of Vempala (2010a), a (crucial) approximate version of the variance reduction lemma (similar to the last part of Lemma 18) is missing and hence it is not clear whether the claimed approximate subspace retrieval result is true. We provide in Sections C.1 and C.2 a full proof of the subspace retrieval lemma, but with the following caveat: we either (1) incur complexity that is exponential in poly(k/ϵ) (see Section C.1) or (2) require some non-degeneracy assumption (see Section C.2).
We now give an overview of the proof of Theorem 2.
Stage I: Acquiring a Good Cover. A good cover is a list F of candidate hypotheses (i.e., halfspace intersections) that is guaranteed to contain some intersection with low test error and only contains intersections with low training error. We construct such a cover as follows.
1. Once we have obtained a(n orthonormal basis for a) subspace U such that every normal to the ground truth intersection is geometrically close to some vector in U , we exhaustively cover the unit sphere in U (see Lemma 20) to obtain a list U ′ of (( k ϵ ) O(k) ) candidate unit vectors that is guaranteed to contain, for each normal w of the ground truth intersection, some element u, such that the angle between w and u is small. 2. We then certify that for each element u of U ′ , all of the halfspaces whose normals are geometrically close to u have low disagreement with the halfspace defined by u on the test distribution. Such a certificate can be obtained by using tools (Lemma 21) from the literature of testable learning (see Gollakota et al. (2023a,b)); in fact we may use, here, the same tools that Klivans et al. (2023) utilized to obtain TDS learners for single homogeneous halfspaces.
3. We construct F by including all possible intersections, of at most k elements from U ′ , that have low training error. Note that there is one element f in F such that its normals are (one-by-one) geometrically close to the normals of the ground truth. The previous test has ensured that f has low test error, since the probability that any halfspace in f disagrees with the corresponding true one is small.
Stage II: Estimating Discrepancy Distance. It remains to pick an element from F with low test error. However, we have only shown that there is one (unknown) element f in F with low test error.
Note that since all of the elements of F have low training error, then the disagreement between each pair of elements in F should be small under the training marginal (and the test marginal as well if there was no distribution shift). Therefore, as a last step, we test that the disagreement between any pair of hypotheses in F is small under test data; otherwise, it is safe to reject. If the test accepts, all of the elements in F should also have low test error (since they mostly agree with f under test data). We stress that this last test corresponds to estimating the discrepancy distance between the test marginal D ′ and the Gaussian with respect to F , i.e., the quantity
The discrepancy distance is a standard notion in domain adaptation (see, e.g., Mansour et al. (2009)), but involves an enumeration and it can be hard to compute. Since we only compute it with respect to a small set of candidate hypotheses, we can afford to brute force search over all pairs of functions. Combining our Theorem 2 with tools for approximate subspace retrieval (see Appendix C), we obtain the following upper bounds. For a more detailed version of the bounds, see Corollary 30.
Corollary 3 The class of ϵ-balanced intersections of k homogeneous halfspaces on R d can be ϵ-TDS learned in time poly(d)2 poly(k/ϵ) using poly(d)2 poly(k/ϵ) training examples and poly(dk/ϵ) test examples. Moreover, it can be ϵ-TDS learned in time
training examples and poly(dk/ϵ) test examples.
In the case of intersections of general halfspaces, we use a similar approach. However, the notion of approximate subspace retrieval of Definition 1 is too strong in this case, as there might be halfspaces that have very high bias and, therefore, it is not possible to obtain enough information about them unless we use a vast amount of training data. We, therefore, define the following relaxed version of approximate subspace retrieval, also used for PAC learning (see Vempala (2010a)).
Definition 4 (Approximate Subspace Retrieval for General Halfspaces) We say that the algorithm A (ϵ, δ, T )-retrieves the relevant subspace for C (whose elements are halfspace intersections) under N d if A, upon receiving at least m A examples of the form (x, f * (x)), where x ∼ N d and f * ∈ C, outputs, w.p. at least 1 -δ a subspace U such that for any normal w corresponding to a halfspace {x : w
The notion of approximate subspace retrieval of Definition 4 is sufficient to design efficient PAC learners, since the halfspaces with large thresholds can be omitted without incurring a significant increase on the error under the training distribution (which, for PAC learning, is the same as the test distribution). In TDS learning, however, the test marginal is allowed to assign non-negligible mass to the unseen region of a hidden halfspace. In fact, this is a source of lower bounds for TDS learning as we show in Theorems 8 and 15.
Prior work on TDS learning (Klivans et al., 2023) focusing on the case of a single general halfspace, used a moment matching tester to ensure that the test marginal does not assign considerable mass to the unseen region of significantly biased halfspaces (as is the case under the Gaussian). Such tests incur a complexity of d Θ(log( 1 ϵ )) , which is essentially unavoidable (see Theorem 8). Note that by assuming that the ground truth is balanced (Definition 17), one can bypass the lower bound of Theorem 8 for TDS learning a single general halfspace. This is not the case, however, for intersections of even 2 general halfspaces (see Theorem 15), where the lower bound of d Ω(log(1/ϵ)) persists even under the balanced concepts assumption.
For TDS learning general halfspaces, we adopt a similar moment matching approach as the one used for a single general halfspace (see Klivans et al. (2023)) to ensure that the normals of the ground truth that are not represented by any element of the retrieved subspace (due to high bias) are not important even under the test distribution. Moreover, in order to acquire a certificate that we have a good cover (as per the previous section), we design a local halfspace disagreement tester that works even for general halfspaces (see Lemma 22). We obtain the following result (see Section D.2).
Theorem 5 (TDS Learning Intersections of General Halfspaces) Let C be a class whose elements are intersections of k general halfspaces on R d , ϵ ∈ (0, 1) and C ≥ 1 a sufficiently large constant. Assume that A ( ϵ 3 Ck 3 , 0.01, 3 log 1/2 ( 10k ϵ ))-retrieves the relevant subspace for C under N d with sample complexity m A . Then, there is an algorithm (Algorithm 4) that (ϵ, δ = 0.02)-TDS learns the class C, using m A + Õ(
We once more combine our Theorem 5 with results on approximate subspace retrieval (see Appendix C), to obtain the following upper bounds (see also Corollary 32).
Corollary 6 The class of ϵ-balanced intersections of k general halfspaces on R d can be ϵ-TDS learned in time
We will now provide a number of lower bounds for TDS learning in the statistical query model originally defined by Kearns (1998), which has been a standard framework for proving computational lower bounds in machine learning, and is known to capture most commonly used algorithmic techniques like gradient descent, moment methods, etc. (see, for example, Feldman et al. (2017a,b).
Definition 7 (Statistical Query Model) Let φ > 0 and D be a distribution over R d . We say that an algorithm A is a statistical query algorithm (SQ algorithm) with tolerance φ if A only has access to D through making a number of (adaptive) bounded queries of the form q :
Our approach is to reduce appropriate distribution testing problems to TDS learning and then show that these problems cannot be efficiently solved in the SQ framework, by applying recent results from Diakonikolas et al. (2023a) on Non-Gaussian Component Analysis.
We prove the following theorem which gives a tight lower bound for TDS learning general halfspaces with respect to the Gaussian distribution in the SQ framework, since the lower bound matches the recent corresponding upper bound of Klivans et al. (2023).
Theorem 8 (SQ Lower Bound for TDS Learning a Single Halfspace) For ϵ > 0, set d = ϵ -1/4 . Then, for all sufficiently small ϵ, the following is true. Let A be a TDS learning algorithm for general halfspaces over R d w.r.t. N d , with accuracy parameter ϵ and success probability at least 0.95. Further, suppose that A obtains at most d log 1/ϵ log log 1/ϵ samples from the training distribution and accesses the testing distribution via 2 d o(1) SQ queries of precision φ > 0 (the SQ queries are allowed to depend on the training samples). Then, the tolerance φ has to be at most d
We first define an appropriate distribution testing problem which can be reduced to TDS learning general halfspaces. In particular, the distribution testing problem we define amounts to testing whether a distribution to which we have sample access assigns too much mass to some halfspace compare to the mass assigned by the Gaussian.
Definition 9 (Biased Halfspace Detection Problem) Let 0 ≤ α ≤ β ≤ 1 The (α, β)-biased halfspace detection problem is the task of distinguishing the d-dimensional standard Gaussian distribution from any distribution D over R d for which there exist v in R d and τ in R satisfying
The idea is that if one has a TDS learner for general halfspaces, then the TDS learner must also work when the training examples are drawn from a Gaussian and labelled by the constant hypothesis -1. In this case, the learner cannot extract any information about the training data, except from the fact that they correspond to a halfspace with very high bias (but the direction remains completely unspecified). If the test distribution assigns a lot of mass on the positive region of the halfspace, then the error would be large and the TDS learner will reject. On the other hand, if the test distribution is the Gaussian, the TDS learner will accept. Hence, the TDS learner would solve the biased halfspace detection problem. We obtain the following quantitative result, whose formal proof can be found in Section E.1.
Proposition 10 (Biased Halfspace Detection via TDS Learning) Let A be a TDS learning algorithm for general halfspaces over R d w.r.t. N d with accuracy parameter ϵ and success probability at least 0.95. Suppose A obtains at most m samples from the training distribution and accesses the test distribution via N SQ queries of tolerance φ (the SQ queries are allowed to depend on the training samples). Then, there exists an algorithm ( 1 100m , 10ϵ)-biased halfspace detection that uses N + 1 SQ queries of tolerance min (φ, ϵ) and has success probability at least 0.8.
In order to complete the proof of Theorem 8, it remains to show that the biased halfspace detection problem is hard in the SQ framework. To this end, we use a powerful tool from recent work on Non-Gaussian Component Analysis by Diakonikolas et al. (2023a), which states that distinguishing the Gaussian from a distribution which is Gaussian in all but one hidden direction is hard for SQ algorithms, whenever the marginal in this direction is guaranteed to match the low degree moments of the Gaussian (see Theorem 37). For our purposes, it is sufficient to construct a one-dimensional distribution that matches low degree moments with the standard Gaussian, but assigns non negligible mass far from the origin. We obtain the following result whose proof can be found in Section E.1.
Proposition 11 (SQ Lower Bound for Biased Halfspace Detection) For ϵ > 0, set d = 1 ϵ 1/4 . Then, for all sufficiently small ϵ, the following is true. Suppose that A is an SQ algorithm for (d -ln(1/ϵ) , 10ϵ)-biased halfspace detection problem over R d , and A has a success probability of at least 2/3. Then, A either has to use SQ tolerance of d -Ω( log 1/ϵ log log 1/ϵ ) , or make 2 d Ω(1) SQ queries.
The following theorem demonstrates that, although TDS learning a single homogeneous halfspace with respect to the Gaussian distribution admits fully polynomial time algorithms (see Klivans et al. (2023)), for intersections of two homogeneous halfspaces, there is no polynomial-time SQ algorithm. Notably, the construction corresponds to a highly unbalanced intersection, so the lower bound does not hold for the problem of TDS learning balanced intersections.
Theorem 12 (SQ Lower Bound for TDS Learning Two Homogeneous Halfspaces) Let ϵ > 0 with ϵ ∈ (0, 1/10) and let A be a TDS learning algorithm for learning intersections of 2 homogeneous halfspaces over R d w.r.t. N d with accuracy ϵ and success probability at least 0.95. Then A either makes some query of tolerance φ = d -ωϵ(1) to the test distribution or runs in time d ωϵ(1) .
To prove our result, we use an SQ lower bound for detecting anti-concentration (AC) from Diakonikolas et al. (2023a).
Theorem 13 (SQ Lower Bound for Detecting AC, Theorem 1.10 in Diakonikolas et al. (2023a)) Let ϵ ∈ (0, 1/2). Any SQ algorithm with SQ access to either (1) N d or (2) some distribution D ′ that assigns mass at least ϵ on some subspace of dimension d -1 and distinguishes the two cases w.p. at least 2/3, either uses 2 d Ω(1) queries, or uses a query with tolerance at most d -ωϵ (1) .
It remains to reduce the AC detection problem to the problem of TDS learning intersections of two homogeneous halfspaces. The idea is to use an intersection of two almost opposite halfspaces, whose positive region effectively coincides with half of the subspace where D ′ has non negligible mass. Therefore, upon acceptance, the output function should take the value 1 with non-negligible probability only if the unknown distribution is D ′ , which implies that we have solved the distinguishing problem. See Section E.2 for a proof.
Remark 14 Under the balance assumption, our algorithms achieve polynomial-time performance for learning intersections of k = O(1) homogeneous halfspaces (see Corollary 30). This demonstrates the importance of the balance condition on the training data.
We now provide an SQ lower bound for TDS learning balanced (see Definition 17) intersections of two general halfspaces. The lower bound demonstrates that the balance condition cannot always mitigate the obstacles of TDS learning due to hard examples that are trivial for PAC learning. In particular, the hard example here is an intersection of two halfspaces, where one of them is known and the other one is orthogonal to the first and is effectively irrelevant for the intersection under the Gaussian measure. For PAC learning, this implies that the second halfspace can be safely ignored, but for TDS learning, the hidden halfspace is a source of SQ lower bounds as demonstrated below.
Theorem 15 (SQ Lower bound for TDS Learning Halfspace Intersections) For ϵ > 0, set d = ϵ -1/4 . Then, for all sufficiently small ϵ, the following is true. Let A be a TDS learning algorithm for 1 3 -balanced intersections of 2 general halfspaces over R d w.r.t. N d , with accuracy parameter ϵ and success probability at least 0.95. Further, suppose that A obtains at most d log 1/ϵ log log 1/ϵ samples from the training distribution and accesses the testing distribution via 2 d o(1) SQ queries of precision φ > 0 (the SQ queries are allowed to depend on the training samples). Then, the tolerance φ has to be at most d
The idea is similar to the one used for the proof of Theorem 8. We once more prove a general reduction of the biased halfspace detection problem to TDS learning. The hard instance corresponds once more (as for the proof of Theorem 8) to the detection problem where the unknown distribution is either (1) the standard Gaussian or (2) some distribution D ′ that assigns non-trivial mass in the negative region of a halfspace H 1 = {x : v • x + τ ≥ 0} for some appropriately large τ .
The reduction of the hard instance to TDS learning follows closely the proof of Proposition 10 (see Appendix E.1.1), but we run the TDS algorithm twice, once using training data of the form (x, sign(u • x)) with x ∼ N d and u some random vector in S d-1 and another one with training data of the form (x, sign(-u • x)), x ∼ N d .
For each of the executions of the TDS algorithm, the training data are consistent (w.h.p.) with the unknown intersection defined by the halfspaces
If the TDS algorithm rejects, then we have a certificate that the marginal was not the Gaussian. If the TDS algorithm accepts, then we may use one SQ query for the probability that the output function is positive. If D ′ was the Gaussian, then this probability should be very close to 1/2. Otherwise, it should be bounded away from 1/2 for at least one of the executions (D ′ assigns non-trivial mass in the negative region of H 1 , so it must assign non-trivial mass to either H 2 \ H 1 or H2 \ H 1 ). Hence, the pair of our SQ queries (one for each execution) will indicate the answer to the biased halfspace detection problem.
Remark 16 Note that the lower bound of Theorem 15 holds even for the problem of TDS learning 2-non-degenerate intersections of two halfspaces (according to Definition 26). Under the nondegeneracy assumption, our algorithms achieve improved performance (see Corollary 32) and, in particular, the lower bound of Theorem 15 is essentially tight (d Θ(log(1/ϵ)) ) for TDS learning Θ(1)non-degenerate, poly(ϵ)-balanced intersections of k = O(1) halfspaces.
We let R d be the d-dimensional Euclidean space. For a distribution D over R d , we use E D (or E x∼D ) to refer to the expectation over distribution D and for a given (multi)set X, we use E X (or E x∼X ) to refer to the expectation over the uniform distribution on X (i.e., E x∼X [g(x)] = 1 |X| x∈X g(x), counting possible duplicates separately). For x ∈ R d where x = (x 1 , x 2 , . . . , x d ) and for α ∈ N d , we denote with x α the product i∈ [d] x α i i . We denote with S d-1 the d -1 dimensional sphere on R d . For any v 1 , v 2 ∈ R d , we denote with v 1 • v 2 the inner product between v 1 and v 2 and we let ∡(v 1 , v 2 ) be the angle between the two vectors, i.e., the quantity θ ∈
, where w i are called the normals of the intersection and τ i the corresponding thresholds.
Learning Setup. We focus on the framework of testable learning with distribution shift (TDS learning) defined by Klivans et al. (2023). In particular, for a concept class C ⊆ {R d → {±1}}, the learner A is given ϵ, δ ∈ (0, 1), a set If the learner A enjoys the above guarantees, then A is called an (ϵ, δ)-TDS learner for C w.r.t. N d . Since the probability of success can be amplified through repetition (see (Klivans et al., 2023, Proposition C.1)), in what follows, we will provide algorithms with constant failure probability.
For our upper bounds, we will make use of a balanced concepts condition, whose importance we justify through appropriate lower bounds (see Sections 3.1 and 3.2). In particular, we will assume that the ground truth (D, f * ) is sufficiently balanced, meaning that positive and negative examples from the training data both have sufficiently large frequency.
Definition 17 (Balance Condition) Let D be a distribution over R d and f : R d → {±1}. For η ∈ (0, 1/2], we say that f is η-balanced with respect to D if
For a concept class C ⊆ {R d → {±1}}, we denote with C η the η-balanced version of C, i.e., the subset of C that contains the elements that are η-balanced.
Note that the algorithm can check whether the ground truth is balanced using training data and, therefore, detect possible failure due to imbalance (i.e., the condition is testable).
Our positive results build on the dimension reduction technique of Vempala (2010a) for PAC learning intersections of halfspaces and low-dimensional convex sets through principal component analysis (PCA), which is based on the following Gaussian variance reduction lemma. Note that although the first two parts of the lemma were known (see e.g., Vempala (2010a)), the last part (which gives variance reduction for any vector that has some correlation with a normal) is proven here. In fact, this more general form of the lemma is important even for the results in Vempala (2010a) (although it is missing from the original paper).
Lemma 18 (Variance Reduction, variant of Lemma 4.7 in Vempala (2010a)) Let K ⊆ R d be an intersection of halfspaces and let N d | K be the truncation of the standard Gaussian distribution in d dimensions N d to K. For any u ∈ S d-foot_0 , we have Var
is one of the defining halfspaces of the intersection then, we have variance reduction along u, i.e., Var
for a sufficiently large universal constant C > 0. Furthermore, for any ϵ ∈ (0, 1 4 ) and any
Proof The first two parts follow from Cafarelli's theorem, see e.g. Theorem 3.1 in Funaki and Toukairin (2007) where one may set the function ψ to be a quadratic function within the interval (-T, ∞) and either 0 outside it when T < 0 or a linear function tangent to the graph of y = x 2 at the point x = T if T ≥ 0 1 .
For the last part, we will introduce an artificial halfspace in the direction of u ′ and we will link the variance in the direction of u ′ under the truncation of the Gaussian on the initial intersection to the variance under the new (artificial) truncation. In particular, let K ′ be the set K ∩ {u ′ • x + θ ≥ 0}, where θ > 0 is a parameter of our choice. We then have Var
, by the previous part of the lemma. However, we are interested in the quantity Var x∼N d | K (x). We have the following
For the first term s 1 , we have s
For the second term s 2 , we have
where the inequality follows from the fact that for any x ∈ K we have u • x + T ≥ 0 and for any
Hence, by bounding the Gaussian integral of the above inequality (note that u ′ ⊥ v), we obtain that for some large constant C ′ > 0 we have s 2 ≤ 1
. For the term µ 1 we have
. The term 2µ 1 µ 2 can be bounded similarly (observe that µ 2 ≤ s 1/2 2 ). Hence, overall, we have
and hence by picking θ = C ′′ T +log 1/2 (1/η) ϵ
, where η = P N d [x ∈ K] and C ′′ ≥ 1 some sufficiently large constant, we have Var
. This concludes the proof of Lemma 18.
We will also make use of the following lemma regarding the sample complexity of estimating the expectation and covariance matrix of a log-concave distribution. Note that the truncation of the standard Gaussian on any convex set is log-concave and has variance at most 1 in every direction.
Lemma 19 (Mean and Covariance Estimation, see Lemma 4.2 in Vempala (2010a)) Let C > 0 be a sufficiently large universal constant, let γ > 0, δ ∈ (0, 1), let D be some log-concave distribution over R d such that the variance in every direction is bounded by 1 and let X be a set of i.i.d. samples from D of size |X| ≥ C • d γ 2 log 2 (d/δ). Then, with probability at least 1 -δ, we have
The following lemma is a standard argument that provides a sparse cover of the k-dimensional sphere and will be useful in order to exhaustively search in the low-dimensional subspace.
Lemma 20 (Sparse Cover w.r.t. Angular Distance) Let U be a linear subspace spanned by the vectors
Proof of Lemma 20, see Vempala (2010b). Let v ∈ U , which we assume w.l.o.g. to have unit norm (since we only focus on angular distance). We have
We will need the following result from Gollakota et al. (2023a) which provides a tester which ensures that any homogeneous halfspace with normal that is geometrically close to some given vector w has low disagreement with the halfspace corresponding to w under the tested marginal.
Lemma 21 (Tester for Local Halfspace Disagreement, see Gollakota et al. (2023a)) Let C > 0 be a sufficiently large universal constant. There is a tester that for any ϵ, δ ∈ (0, 1 2 ), any w ∈ S d-1 and any (multi)set X of points in R d , runs in time O(d 3 + d 2 |X|) and satisfies the following.
(a) (Soundness.) If the tester accepts, then for any w ∈ S d-1 , with ∡(w, w) ≤ ϵ we have
)) independent samples from N d , the tester accepts w.p. at least 1 -δ.
Proof of Lemma 21, combination of Propositions 3.2, 3.3 and 4.5 in Gollakota et al. (2023a). The tester does the following.
] and reject if its value is greater than 5ϵ 2/3 . 2. Compute the largest eigenvalue of the covariance matrix Var x∼X (x) and reject if its value is greater than 2.
3. Otherwise, accept.
Soundness. If the tester accepts, then we have the following. Suppose that w ̸ = w (otherwise, the proof is trivial). Let v = w-(w• w) w ∥w-(w• w) w∥ 2 (so v orthogonal to w). Observe that for any x with sign(w
∥w-(w• w) w∥ 2 , where w • x ≥ 0, w • w ≥ cos ϵ and ∥w -(w • w) w∥ 2 ≤ sin ϵ. Therefore, we obtain the following by additionally using Chebyshev's inequality.
Completeness. For completeness, assume that X consists of m i.i.d. Gaussian examples. We have that E
By using a standard Hoeffding bound, we have that the first test will accept with probability at least 1-2δ as long as m ≥ C ϵ 4/3 log(1/δ) and C is sufficiently large. Moreover, by Lemma 19, as long as m ≥ C • d • log 2 (d/δ), we have that the largest eigenvalue of Var x∼X (x) is at most 2 (since ∥ Var x∼N d (x)∥ 2 = 1).
We also prove the following generalization of Lemma 21 for general halfspaces.
)) independent samples from N d , the tester accepts w.p. at least 1 -δ.
Proof of Lemma 22. The tester does the following for γ = 10(ϵT + ϵ 2/3 ).
and reject if its value is greater than 5γ.
2. Compute the largest eigenvalue of the covariance matrix Var x∼X (x) and reject if its value is greater than 2.
3. Otherwise, accept.
Soundness. If the tester accepts, then we have the following. Suppose that w ̸ = w (otherwise, the proof is trivial). Let v = w-(w• w) w ∥w-(w• w) w∥ 2 (so v orthogonal to w). Observe that for any x with sign(w
where for the first equality we add and subtract the terms τ and τ (w • w) and for the inequality we use the fact that the signs of the halfspaces are opposite. Moreover, since we have |w
Therefore, we obtain the following by additionally using Chebyshev's inequality.
for a sufficiently large constant C ′ > 0, due to the choice of γ.
Completeness. For completeness, assume that X consists of m i.i.d. Gaussian examples. We have that
By using a standard Hoeffding bound, we have that the first test will accept with probability at least 1 -2δ as long as m ≥ C γ 2 log(1/δ) and C is sufficiently large. Moreover, by Lemma 19, as long as m ≥ C • d • log 2 (d/δ), we have that the largest eigenvalue of Var x∼X (x) is at most 2 (since ∥ Var x∼N d (x)∥ 2 = 1).
Finally, we state the following result from Klivans et al. (2023), which demonstrates that any high bias halfspace behaves as a constant function with respect to any distribution that matches sufficiently many moments up to sufficiently small accuracy with the Gaussian distribution. Lemma 24 (Subspace Retrieval, modification from Vempala (2010a)) Let C ≥ 1 be a sufficiently large universal constant. Let C be the class of intersections of k general halfspaces on R d , ϵ ∈ (0, 1), T > 0 and η ∈ (0, 1/2]. Let S be a set of at least dk 4 (1/η) C/ϵ 2 2 CT 2 /ϵ 2 log 2 (d/δ) labelled examples of the form (x, f * (x)), where x ∼ N d and f * ∈ C η is an η-unbiased intersection which is defined by the normal vectors (w 1 , . . . , w k ) and the corresponding thresholds (τ 1 , . . . , τ k ). Then, with probability at least 1 -δ, the subspace U spanned by the k-smallest variance orthogonal components of the positive examples S + = {x : (x, 1) ∈ S} approximately includes all of the normal vectors corresponding to bounded thresholds, i.e., for any i ∈ For the proof, we will use the following strong theorem which ensures that the subspace retrieved by PCA on the empirical distribution will be geometrically close to the true corresponding subspace, as long as there is a spectral gap in the covariance matrix of the true distribution.
Proposition 25 (Davis-Kahan, modification of Theorem 2 in Yu et al. (2015)) Let M ∈ R d×d and M ∈ R d×d be symmetric matrices such that for some k ∈ [d], the gap between the k-th smallest eigenvalue of M and the (k + 1)-th smallest eigenvalue of M is positive, i.e., λ k+1 -λ k > 0. Let v 1 , . . . , v k be the eigenvectors of M corresponding to the k smallest eigenvalues and, similarly, u 1 , . . . , u k the k smallest eigenvectors of M . Then we have that
Let W be the span of (w 1 , . . . , w k ) and note that every direction orthogonal to W has variance
and let W γ be the subspace of W such that for every direction u orthogonal to W γ , we have
In other words, W γ is the span of the eigenvectors of the covariance matrix M of N d | K whose corresponding eigenvalues are at most
Since there is a γ gap between λ ℓ and λ k+1 , there is some j ∈ [ℓ, k] such that λ j+1 -λ j > γ k . Let U be the subspace corresponding to the k smallest eigenvectors of the empirical covariance matrix M of the set of positive examples S + . Since |S| ≥ 1 η 2 log(1/δ), due to a Hoeffding bound, we have that with probability at least 1-δ/10,
We can therefore apply Lemma 19 to N d | K (which is log-concave) to obtain that ∥M -M ∥ 2 ≤ γϵ 2C ′ k 2 . Let U ℓ be the subspace of U corresponding to the ℓ smallest eigenvalues of M , and let (v 1 , . . . , v ℓ ) be the corresponding eigenvectors. By Proposition 25, we have that
We analyze w i in two orthogonal components, w and w ′ , where w is the normalized projection of w i on W γ and w ′ is therefore orthogonal to W γ . Since w ′ is orthogonal to W γ , by the definition of W γ , we have
. Moreover, by Equation (1), we have that ∡(w, proj
≤ ϵ/10 by the choice of γ, we obtain the desired result.
In the previous subsection we provided a detailed proof of the subspace retrieval lemma which was originally proven in Vempala (2010a), incurring, however, an exponential dependence on 1/ϵ 2 . Here, we define a technical assumption on the concept class considered which is sufficient to provide a fully polynomial result for subspace retrieval. Despite its technicality, the non-degeneracy condition is satisfied by the constructions we use for our lower bounds, which implies that under the non-degeneracy condition, our upper and lower bounds are directly comparable (and tight in some regimes).
Definition 26 (Non-Degeneracy Condition) Let K be an intersection of halfspaces in R d and N d | K be the truncation of the standard Gaussian to K. For β ≥ 1, we say that K is β-nondegenerate if the following is true. For every subspace W spanned by some of the normals of K and for every vector w ∈ S d-1 that is a normal to K with non-zero projection w ′ ∈ R d \ {0} onto the subspace orthogonal to W we have
For any class C of halfspace intersections on R d , we denote with C β the β-non-degenerate version of C, i.e., the subset of C that contains the elements that are β-non-degenerate.
The condition defined above states that each normal w of the intersection has either zero or nontrivial relative influence on subspaces orthogonal to the span W ′ of any subset of the normals. The influence is measured in terms of the variance reduction along the residual direction w-proj W ′ (w). In particular, in light of the third part of Lemma 18, for intersections of two halfspaces, the nondegeneracy condition is satisfied whenever the two halfspaces of the intersection have normals either pointing to the exact same direction or have sufficiently large angular distance (but nothing in between). This enables one to circumvent the need for a strong quantitative statement relating (1) the angle between some vector u and a normal with (2) the variance reduction along u, which is the source of the exponential dependence of 2 1/ϵ 2 . With an analysis similar to the one of Section C.1, we obtain the following subspace retrieval result.
Algorithm 3: Proper TDS Learner for Homogeneous Halfspace Intersections Input: Labelled set S train , unlabelled set X test , parameter ϵ Set ϵ ′ = ϵ 3/2 Ck 3/2 and ϵ ′′ = ϵ 6 Ck 7 for some sufficiently large universal constant C ≥ 1. Run algorithm A on the set S train and let (v 1 , . . . , v k ) be its output. Let U be the subspace spanned by (v 1 , . . . , v k ) and consider the following sparse cover of U :
Proof of Theorem 2. Let S train be a set of m train samples from the training distribution, i.e., of the form (x, f * (x)), where x ∼ D = N d and let X test be a set of m test samples from the test distribution D ′ . Let C > 0 be a sufficiently large universal constant. Let f * : R d → {±1} denote the ground truth, i.e., the intersection of k homogeneous halfspaces
In the following, we will say that an event holds with high probability if it holds with probability sufficiently close to 1 so that union bounding over all the bad events gives a probability of failure of at most 0.01. This is possible by choosing C to be a sufficiently large constant.
Soundness. To prove soundness, suppose that the tests have accepted. We first use the approach of Vempala (2010a) to show that using training data, we can retrieve a subspace that is geometrically close to the normal subspace of the ground truth. Let C ′ , C ′′ be sufficiently large universal constants.
In particular, the guarantee for algorithm A implies that the retrieved subspace U has the property that for any i ∈
) k . Therefore, for any i ∈ [k] we have some vector u i in the cover U ϵ ′′ that is close to the normal w i , i.e., ∡(u i , w
If suffices to show that f belongs in the set F of candidate concepts and that f has small test error
, because then for any other candidate concept f ′ ∈ F , we know that it disagrees with f only on a small fraction of test points and, hence, we will have
. By standard VC dimension arguments, this would imply that, whenever m test ≥ C dk log k ϵ 2 , with high probability, the test error of any element of
We appeal to the tester for local halfspace disagreement of Lemma 21 in order to demonstrate that P x∼Xtest [f (x) ̸ = f * (x)] ≤ ϵ/4. In particular, we have that
Finally, we show that the hypothesis f lies within F . In particular,
, which is bounded by ϵ/10 by choosing the constant C ′ appropriately. By standard VC dimension arguments, we therefore have that
Completeness. To prove completeness, suppose that D ′ = N d . Since U ϵ ′′ , F do not depend on X test , we can use Hoeffding bounds to bound the probability of rejection, as well as union bounds over F × F accordingly. In particular, the tester of Lemma 21 will accept with high probability as long as
) and the tester of the disagreement probabilities of pairs in F will accept (due to standard Hoeffding and union bounds) with high probability whenever
By combining Theorem 29 with Lemmas 24, 27 and 28 we obtain the following bounds for TDS learning homogeneous halfspace intersections. (b) There is an (ϵ, δ = 0.02)-TDS learner for the class C β η of η-balanced and β-non-degenerate intersections that uses Õ(d)
(c) There is an (ϵ, δ = 0.02)-TDS learner for the class C η of η-balanced intersections that uses
unlabelled test examples and runs in time
We now prove our positive results on learning intersections of general halfspaces.
Theorem 31 (TDS Learning Intersections of General Halfspaces) Let C be a class whose elements are intersections of k general halfspaces on R d , ϵ, T ∈ (0, 1) and C ≥ 1 a sufficiently large constant.
• Assume that there is an algorithm A that upon receiving at least m A examples of the form (x, f * (x)), where x ∼ N d and f * ∈ C, outputs, with probability at least 0.99 an orthonormal basis for a subspace U such that for any normal w ∈ S d-1 that corresponds to some halfspace {x : w
Then, there is an algorithm (Algorithm 4) that (ϵ, δ = 0.02)-TDS learns the class C, using m A + Õ(
Ck 3/2 and ϵ ′′ = ϵ 6 Ck 3/2 , where C ≥ 1 is a sufficiently large constant. Reject and terminate if for some α ∈ N d with ∥α∥ 1 ≤ r it holds
Run algorithm A on set S train and let (v 1 , . . . , v k ) be its output.
Let U be the subspace spanned by (v 1 , . . . , v k ) and consider the following sparse cover of U :
where (u 1 , θ 1 ), . . . , (u k , θ k ) ∈ U ϵ ′′ × T ϵ ′ and P (x,y)∼S train [y ̸ = f (x)] ≤ ϵ/5. Reject and terminate if max
Otherwise, output f : R d → {±1} for some f ∈ F .
Proof of Theorem 5. The proof is similar to the one of Theorem 2, but since the intersections are general, there are some additional complications. Let once more S train be a set of m train samples from the training distribution, i.e., of the form (x, f * (x)), where x ∼ D = N d and let X test be a set of m test samples from the test distribution D ′ . Let C > 0 be a sufficiently large universal constant. Let f * : R d → {±1} denote the ground truth, i.e., the intersection of k halfspaces
In the following, we will say that an event holds with high probability if it holds with probability sufficiently close to 1 so that union bounding over all the bad events gives a probability of failure of at most 0.01. This is possible by choosing C to be a sufficiently large constant.
Soundness. Suppose that the tests have accepted. We will once more use the subspace retrieval lemma from Vempala (2010a), but this time we will use a version (Lemma 24) that works for arbitrary halfspace intersections. We pick T = 3 log(10k/ϵ), r ≥ log(10k/ϵ) and C ′ , C ′′ > 0 sufficiently large universal constants.
Due to Lemma 24, the retrieved subspace U has the property that, with high probability, for any
) k ). Therefore, for any i ∈ [k] that corresponds to a halfspace with bounded bias τ i ≤ T , we have ∡(u i , w i ) ≤ ( 5ϵ C ′ k ) 3/2 . Moreover, for any such i, there is some θ i ∈ T ϵ ′ that is either close to the i-th threshold (|θ i -τ i | ≤ ϵ ′ ) or they are both large enough (τ i ≤ -T and θ i = -T ). Assume without loss of generality that {i ∈ [k] :
Once more, it suffices to show that f belongs in the set F of candidate concepts and that f has small test error P x∼Xtest [f (x) ̸ = f * (x)] ≤ ϵ/4, because then for any other candidate concept f ′ ∈ F , we know that it disagrees with f only on a small fraction of test points and, hence, we will have
. By standard VC dimension arguments, this would imply that, whenever m test ≥ C dk log k ϵ 2 , with high probability, the test error of any element of F satisfies
As a first step, we will show that the ground truth is close to the intersection corresponding to the bounded bias halfspaces with respect to both the training and the test examples, i.e., that
This is important, because we can then relate f , f * through f * . Since the moment-matching test has accepted, by Lemma 23, as long as r ≥ log(10k/ϵ) and T ≥ 3 log(10k/ϵ), for any i > ℓ, we have that P x∼Xtest [sign(w
, due to a union bound (and the fact that the only possibility that f * and f * differ is if some of the omitted halfspaces in f * becomes negative). Similarly, for S train , the claim follows with high probability by a standard Hoeffding bound (f * and f * do not depend on S train ), as long as |S train | ≥ C k 2 ϵ 2 . We will now bound the quantity P x∼Xtest [f (x) ̸ = f * (x)] by ϵ/8. Observe that in the case that |τ i | ≥ T , then, by Lemma 23 (as argued above), the corresponding halfspace is constant with probability at least 1 -ϵ/(10k) and the same is true for θ i = T . Therefore, we may safely omit these terms from f and f * by only incurring an error of at most ϵ/10. For the remaining terms, we appeal to the tester for local (general) halfspace disagreement of Lemma 22 in order to show that P x∼Xtest [f (x) ̸ = f * (x)] ≤ ϵ/8. In particular, we have that
Finally, we show that the hypothesis f lies within F . In particular, P
, which is bounded by ϵ/20 by choosing the constant C ′ appropriately. By standard VC dimension arguments, we therefore have that
Completeness. To prove completeness, suppose that D ′ = N d . Since U ϵ ′′ , F do not depend on X test , we can use Hoeffding bounds to bound the probability of rejection, as well as union bounds over F × F accordingly. In particular, the tester of Lemma 22 will accept with high probability 1. Generate S train ⊂ R d × {±1}, of pairs (x i ,-1), where each x i is sampled from N d .
2. Run the TDS learning algorithm A on the training set S train . Every time A makes an SQ query to the test distribution, make the same SQ query to D, and return A the result.
3. If A returns "Reject", then our algorithm also returns "Reject" and terminates.
4. Otherwise, A outputs "Accept" and a classifier f : R d → {±1}.
5. Using an SQ query, let λ be an estimate up to additive error min (φ, ϵ) of P x∼D f (x) = 1 .
6. If λ > 4ϵ, then output "Reject" and terminate.
7. Otherwise, output "Accept" and terminate.
First, we argue that if D is N d , then the algorithm above will output "Accept" with probability at least 0.8. For arbitrarily chosen unit vector w, as a parameter τ grows to infinity, the statistical distance between S train = (x i , -1) and the set S ′ train = (x i , sign w • x i -τ ) goes to zero. If A is given S ′ train and D = N d , then the definition of TDS learning requires A with probability at least 0.95 to accept and output a hypothesis f satisfying
Taking the parameter τ to be sufficiently large, we see that if A is given S train = (x i , -1) and D = N d , then with probability at least 0.94 the algorithm A accepts and outputs a hypothesis f satisfying P x∼N d f (x) ̸ = -1 ≤ 2ϵ. Therefore, the estimate λ will be at most 3ϵ, and we will thus output "Accept". Now, suppose D is such that for some unit vector v and τ ∈ R we have
100m . Besed on the set S train = (x i , -1) , define the set S ′′ train as S ′′ train = (x i , sign v • x i -τ ) . If the algorithm A were given the set S ′′ train instead of S train as the training set, then the definition of TDS learning would require A with probability at least 0.95 either to output "Reject" or give a hypothesis f satisfying
we see via a union bound that that the statistical distance between S train and S ′′ train is at most 0.01. Thus, in the algorithm above, the algorithm A with probability at least 0.94 indeed either outputs "Reject" or gives a hypothesis f satisfying P x∼D f (x) ̸ = sign (v • x -τ ) ≤ ϵ. In the former case, our algorithm will also output "Reject". In the latter case we will have λ > 9ϵ, since D is such that P
Therefore, in this case too our algoirthm outputs "Reject", which completes the proof.
We now provide a proof for the second ingredient, namely, that no efficient SQ algorithm can solve the problem of detecting biased halfspaces, i.e., the following proposition (restated here for convenience).
Proposition 34 (SQ Lower Bounds for Biased Halfspace Detection) For ϵ > 0, set d = 1 ϵ 1/4 . Then, for all sufficiently small ϵ, the following is true. Suppose A is an SQ algorithm for (d -ln(1/ϵ) , 10ϵ)biased halfspace detection problem over R d , and A has a success probability of at least 2/3. Then, A either has to use SQ tolerance of d -Ω( log 1/ϵ log log 1/ϵ ) , or make 2 d Ω(1) SQ queries.
To prove the above claim, we first construct a one-dimensional distribution D 1 that approximately matches the low-degree moments of N d , while having a lot of probability mass above a certain threshold.
Proposition 35 For ϵ > 0, let k 0 be defined as k 0 = ln 1/ϵ 100 ln ln 1/ϵ . If ϵ is sufficiently small, then there exists a distribution D 1 supported on a finite subset of R, satisfying
, for some t for which
Proof We will first construct a distribution D ′ 1 that satisfies the conditions above, but does not have finite support. Afterwards, we will discretize D ′ 1 . We take t := ln 1/ϵ and observe that
For ϵ sufficiently small.
.
Let τ be the real number for which
From Equation 2, we see that for all sufficiently small ϵ it is the case that τ < ϵ. We define D ′ 1 the following way: to sample z
ln 1/ϵ 100 ln ln 1/ϵ = = 12ϵ 0.99 ≤ 1 2 • 100 ln ln 1/ϵ ln 1/ϵ ln 1/ϵ 10 ln ln 1/ϵ For ϵ sufficiently small. = 1 2k 10k 0 0
.
Overall, we have so far shown that
1 is not supported on a finite subset of R. We will now construct a finitely-supported distribution D 1 via the probabilistic method. Obtain D 1 as the empirical distribution over K i.i.d. samples from D ′ 1 . Since all moments of D ′ 1 are bounded, as K grows to infinity, for all i ∈ {0, • • • , 10k 0 } the quantity E x∼D 1 x i converges in probability to E x∼D ′ 1 x i , and the quantity
Thus, for a sufficiently large K, we have
, with non-zero probability over the choice of D 1 , which completes the proof.
We now apply the following theorem which is implicit in Diakonikolas et al. (2023b) to obtain a distribution D over R that has a lot of probability mass above a certain threshold and whose moments match N 1 exactly.
Theorem 36 (Implicit in Diakonikolas et al. (2023b)) Let k be a sufficiently large positive integer and let D 0 be a distribution supported on a finite subset of R, and suppose that for every i ∈ {0, • • • , 10k} we have
then there exists a distribution D 1 with the same support as D 0 with E x∼D 0 x i = E x∼N 1 x i for every i ∈ {0, • • • , k}, and also satisfying
for every x 0 in the support of D 0 .
The proof is equivalent to the proof given by Diakonikolas et al. (2023b), but is provided here with slight modifications for completeness. We will need the following fact.
Fact 1 Let p be a polynomial over R of degree at most k, and let E x∼N 1 p(x)
foot_1 ≤ 1. Then, each coefficient of p has absolute value of at most 2 k+1 .
Proof We will use the Hermite polynomials. Recall that for i = 0, 1, 2, • Hermite polynomials {H i } are the unique collection of polynomials over R that are orthogonal with respect to Gaussian distribution. In other words E x∈N 1 [H i (x)H j (x)] = 0 whenever i ̸ = j. In this work, we normalize the Hermite polynomials to further satisfy E x∈N 1 [H i (x)H i (x)] = 1. It is a standard fact from theory of orthogonal polynomials that H 0 (x) = 1, H 1 (x) = x and for i ≥ 2 Hermite polynomials satisfy the following recursive identity:
It follows immediately from the recursion relation that Each coefficient of H i is bounded by 2 i in absolute value. We expand P (x) as a sum of Hermite polynomials 2 :
Due to orthogonality of Hermite polynomials, we have:
In particular, this implies that each coefficient α i is bounded by 1 in absolute value. Combining this with Equation 4, the fact that each coefficient of H i is bounded by 2 i in absolute value, we see that each coefficient of p is bounded by k i=0 2 i < 2 k+1 in absolute value.
Proof of Theorem 36, implicit in Diakonikolas et al. (2023b). Provided here for completeness.
We first restate the setting of the theorem. Let k be a sufficiently large positive integer and let D 0 be a distribution supported on a finite subset of R, and suppose that for every i ∈ {0, • • • , 10k} we have
then we would like to show that there exists a distribution D 1 with the same support as D 0 satisfying E x∼D 0 x i = E x∼N 1 x i for every i ∈ {0, • • • , k}, and also satisfying Pr It is now shown that the above is indeed infeasible if D 0 is such that for every i ∈ {0, • • • , 10k}
we have E x∼D 0 x i -E x∼N 1 x i ≤ 1 k 10k . For the sake of contradiction, suppose that the linear program above is feasible and is satisfied by some polynomial p. Without loss of generality, assume that E x∼N 1 (p(x)) 2 = 1, because otherwise one could rescale p while still satisfying the dual linear program above. By Fact 1 each coefficient of p has absolute value of at most 2 k+1 . This implies that each coefficient of p 2 has an absolute value of at most 8 k+1 and each coefficient of p 4 has an absolute value of at most 32 k+1 . Combining these coefficient bounds with Equation 5, and applying the triangle inequality, we see that (11) where the prior to last inequality follows form the fact that E x∼N 1 (p(x)) 4 ≤ (4k + 1)32 k+1 k!!, as each coefficient of p 4 is at most 32 k+1 in absolute value. Overall, we see that Equations 11 and 10 cannot hold simultaneously for a sufficiently large k , contradiction.
In order to conclude the proof of Proposition 34, we a tool from Diakonikolas et al. (2023a). Recall that in the setting of Theorem 8 for ϵ > 0, we let d be chosen as d = 1 ϵ 1/4 . Suppose Theorem 8 is false. Then for a sequence of ϵ approaching 0 there is a TDS learning algorithm A for general halfspaces over R d with accuracy parameter ϵ and success probability at least 0.95. ) and has success probability at least 0.8. However, for sufficiently small values of ϵ, this directly contradicts Proposition 11. This finishes the proof of Theorem 8.
This choice of ψ is due to Raghu Meka(Meka, 2010).
Note that the expansion below is always possible for a degree k polynomial because polynomials of the form Hi have degree at most k and are linearly independent, because they are orthonormal with respect to the standard Gaussian distribution.