Tolerant Algorithms for Learning with Arbitrary Covariate Shift

Authors: surbhi  goel
abhishek  shetty
konstantinos  stavropoulos
arsen  vasilyan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:13:37

Abstract: We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially adversarially generated test distribution. We focus on two frameworks: *PQ learning* [GKKM'20], allowing abstention on adversarially generated parts of the test distribution, and *TDS learning* [KSV'23], permitting abstention on the entire test distribution if distribution shift is detected. All prior known algorithms either rely on learning primitives that are computationally hard even for simple function classes, or end up abstaining entirely even in the presence of a tiny amount of distribution shift.
   
   We address both these challenges for natural function classes, including intersections of halfspaces and decision trees, and standard training distributions, including Gaussians. For PQ learning, we give efficient learning algorithms, while for TDS learning, our algorithms can tolerate moderate amounts of distribution shift. At the core of our approach is an improved analysis of spectral outlier-removal techniques from learning with nasty noise. 
   Our analysis can (1) handle arbitrarily large fraction of outliers, which is crucial for handling arbitrary distribution shifts, and (2) obtain stronger bounds on polynomial moments of the distribution after outlier removal, yielding new insights into polynomial regression under distribution shifts. Lastly, our techniques lead to novel results for tolerant *testable learning* [RV'23], and learning with nasty noise.

Main paper: 
 introduction: 
 Despite the tremendous progress of machine learning, real-world deployment and use of machine learning models has proven challenging. A major reason for this is distribution shift, which occurs when the model is trained on one distribution D train over X ×{±1}, while the data during deployment comes from a different distribution D test . In such scenarios, a model can unexpectedly make incorrect predictions, leading to loss of reliability, as well as erosion of trust in the machine learning system itself. Among many other critical applications, distribution shift continues to be a major challenge in healthcare applications [ZBL + 18, SS20, WOD + 21, TCK + 22].Handling distribution shift when D train and D test are allowed to be arbitrary is known to be impossible [DLLP10] . To circumvent this impossibility, recent works [GKKM20, KK21, KSV24b, GHMS24, KSV24a] allow the machine learning model to additionally abstain (not make a prediction) on some or all of the inputs. These frameworks generalize standard PAC learning, requiring the algorithm to abstain from making predictions rather than giving incorrect predictions. In this work, we focus on two such frameworks for binary classification:PQ learning [GKKM20, KK21], requiring the learning algorithm to output a selective classifier f , which is allowed to abstain on some inputs and simultaneously satisfy: (i) ϵ-accuracy: the probability that f does not abstain and incorrectly classifies an input x from the test distribution D test is at most ϵ, and (ii) ϵ-rejection rate: the probability that f abstains on an input x from the original distribution D train is at most ϵ. In particular, this implies that f abstains on D test with probability at most d TV (D train , D test ) + ϵ, i.e. the probability of abstention deteriorates only in proportion to the amount of distribution shift.Testable Distribution Shift (TDS) [KSV24b] , allowing the classifier to abstain on the entire distribution D test if any distribution shift is detected. If there is no distribution shift, then the classifier is ϵ-accurate on D test .Prior known algorithms for both these settings have strong inherent limitations, making them impractical for real-world scenarios. For PQ learning, all known algorithms require access to oracles that are computationally inefficient even for the most basic concept classes and training distributions. For example, even for the most basic class of halfspaces (linear separators) over R d under the Gaussian training distribution, no PQ learning algorithm has run-time better than 2 d Ω (1) . On the other hand, TDS learning algorithms, while being computationally efficient, reject entire test sets even when the test set has a tiny amount of distribution shift. For example, the algorithms of [KSV24b] , use the low-degree moment-matching approach, which can reject distributions D test ̸ = D train even when d TV (D train , D test ) = o(ϵ).In this work, we overcome both these limitations using a unified approach: spectral outlier removal [DKS18] in tandem with strong polynomial approximation results in terms of L 2 -sandwiching [KSV24b] . For PQ learning, we give the first dimension-efficient learning algorithms. For TDS learning, we give the first tolerant TDS learners that accept test sets with moderate amount of distribution shift in TV distance, d TV (D train , D test ) = O(ϵ). We summarize our results in Table 1 .Halfspaces (realizable)N (0, I) d O(log 1/ϵ) d O(log 1/ϵ) Halfspaces N (0, I), U {±1} d d Õ(1/ϵ 4 ) d Õ(1/ϵ 2 ) Intersections of ℓ halfspaces N (0, I), U {±1} d d Õ(ℓ 6 /ϵ 4 ) d Õ(ℓ 6 /ϵ 2 ) Size-s decision trees U {±1} d d O(log(s/ϵ)) d O(log(s/ϵ)) Size-s depth-ℓ formulas U {±1} d d O( √ s(log(s/ϵ)) 5ℓ/2 ) d O( √ s(log(s/ϵ)) 5ℓ/2 )Table 1: Summary of our results for PQ learning and tolerant TDS learning. Except for the first row, all results are for the agnostic noise model.Application: Testable Agnostic Learning. Our techniques give new learning algorithms in the testable agnostic learning framework of [RV23] . Testable learning does not address distribution shift, as it assumes that the training and testing distributions are the same. Similarly to the TDS learning algorithms of [KSV24b] , all known testable agnostic learning algorithms are based either entirely [RV23, GKK23] or partially [GKSV23, DKK + 23, GKSV24] on low-degree moment matching 4 , and are subsequently not tolerant to small amounts of violations of the testing assumption in TV distance.We give the first tolerant testable learning algorithms for a number of function classes, including Halfspaces and low-depth formulas (see Table 2 in Appendix D for details).Application: Learning with Nasty Noise. As a corollary of our tolerant agnostic learning algorithms we obtain algorithms that withstand an Ω(ϵ) amount of nasty noise corruption, and produce classifiers with an error at most ϵ. (In this setting Ω(ϵ) fraction of both labels and examples given to the algorithm are corrupted). The error bound of ϵ compares favorably with the bound of [KKM18] under Ω(ϵ) nasty noise, which is √ ϵ. Compared with the results of [DKS18] in the nasty noise setting, our results are incomparable (see relevant discussion in Section 3, Appendix D.2 for more information).To explain our technical approach, we focus of the PQ learning setting (in TDS learning setting and testable agnostic learning setting, our approach is analogous). If the TV distance between D test and the training distribution D train is at most d TV (D train , D test ), then we think of the dataset as consisting of 1 -d TV (D train , D test ) fraction of inliers and an d TV (D train , D test ) fraction of outliers. In order to accomplish PQ learning, we aim to remove a portion of the test set while (i) ensuring that a learning algorithm based on low-degree polynomial regression [KOS08] works on the remaining data (ii) not removing more than ϵ fraction of the inliers5 .It was known from [KSV24b] that the degree-k polynomial regression performs correctly if the dataset satisfies the degree-k moment-matching test. Despite its power, the low-degree moment test can reject distributions even ϵ/d O(k) -close to the reference distribution. However (i) it is not clear how to efficiently prune the dataset, so the remaining datapoints satisfy the moment-matching condition (ii) even if one could do this efficiently, this can require one remove a constant fraction of inliers. To overcome this issue, we introduce the notion of low-degree spectral boundedness, which requires that for every degree-k polynomial p the expectation E x∼D [p(x) 2 ] does not exceed the analogous expectation with respect to the reference distribution by more than a desired factor. Our first key insight is that by using the notion of L 2 -sandwiching polynomials [KSV24b] , for many settings the low-degree moment matching test can be replaced by this low-degree spectral boundedness test.If our dataset does not satisfy low-degree spectral boundedness, our second key insight is to make it do so by removing outliers. As in many other algorithms based on outlier removal6 (see e.g. [DKK + 19, LRV16, HLZ20, Ste18, DK19, DV04] and references therein), our outlier-removal algorithm repeatedly finds regions in R d , such that at least 1 -ϵ fraction of points in them are outliers. This way, as we remove all the points in such outlier-rich regions, we will not remove too many inliers. Finally, we find such outlier-rich regions efficiently using a spectral approach. Specifically, if the dataset S does not satisfy the low-degree spectral boundedness, then there is some polynomial p for which E x∼S [p(x) 2 ] is much greater than the corresponding expectation over the reference distribution. We infer that, for an appropriate value of τ , at least 1 -ϵ fraction of points in the region {x : p(x) 2 > τ } are outliers.Domain Adaptation. During the last two decades, there has been a long line of works in domain adaptation literature (see, e.g., [BDBCP06, BDBC + 10, MMR09, BCK + 07, DLLP10, RMH + 20, KZZ24] and references therein), aiming to provide generalization bounds for the error on the test distribution, after training using only labeled examples from the training distribution. However, the generalization bounds provided involve distances between the training and test marginals that typically involve enumerations over the whole concept class and no efficient algorithms for estimating or even testing such distances directy are available.PQ Learning. The PQ learning framework was defined by [GKKM20] , which showed that a PQ learner can be efficiently implemented using an oracle to a distribution-free agnostic learner. In follow-up work by [KK21] , it was shown that distribution-free PQ learning is actually equivalent to distribution-free agnostic reliable learning, which is a learning primitive known to be hard even for the fundamental class of halfspaces (exp(Ω( √ d)) time is believed to be necessary). Here, we show how to take advantage of standard assumptions on the training marginal (e.g., Gaussianity) in order to obtain the first dimension-efficient results for PQ learning of several fundamental concept classes.TDS Learning. Testable learning with distribution shift was defined recently by [KSV24b] , where dimension-efficient algorithms for several concept classes including halfspaces, halfspace intersections, decision trees and boolean formulas were provided. In this work, we give similar results for each of these classes in the tolerant TDS learning framework. Further work by [KSV24a] provided improved guarantees for TDS learning halfspace intersections in the realizable case. We believe that our techniques can likely be used to provide similar improvements for tolerant TDS learning, but, for ease of exposition, we do not include such results in this work.Tolerant Distribution Testing: The notion of tolerance in property testing was introduced in [PRR06] and has been the focus of many works including [FF05, VV11, BCE + 19, RV20, CJKL22, CFG + 22, BH18, CP23]. However, over R d all existing tolerant distribution testing algorithms (such as [VV11] ) have run-times and sample complexities of 2 Ω(d) , which greatly exceeds our run-times.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We provide theorems with complete proofs or relevant citations for all claims made in the abstract and introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 Notation. For details on the notation, see Appendix A. We denote with x ⊗k the vector of monomials of degree k of x ∈ R d , i.e., x ⊗k is a vector of length d k with elements of the formx r = d i=1 x ri , where i∈[d] r i ≤ k, r i ∈ N, r = (r 1 , . . . , r d ) and k is the degree of x r . A polynomial p over R d is a function p(x) = r∈N d p r x r = p ⊤ x ⊗d, where we abuse the notation to denote with p the vector of coefficients of the corresponding polynomial. A polynomial p over {±1} d is defined similarly, but all of the coefficients corresponding to monomials x r where r i > 1 for some i are zero.Learning Setting. We consider distribution D over X and D train , D test distributions over X × {±1} such that the marginal on X of D train is D and the marginal of D test is D test X . We also consider some concept class F ⊆ {X → {±1}}. The learner is given access to labeled examples from D train as well as unlabeled examples from D test X and the goal is to produce some hypothesis with low error on D test , but is also allowed to abstain from predicting either on specific points (for PQ learning, Def. 4.1) or even the entire distribution (for TDS learning, Def. 5.1) if distribution shift is detected.In the realizable setting, the labels of both the training distribution and the test distribution are generated according to some concept f * ∈ F and the training examples are of the form (x, f * (x)), where x ∼ D. The target test error is ϵ for some arbitrarily chosen ϵ ∈ (0, 1). In the agnostic setting, the distributions D train and D test can be arbitrary, except from the assumption that the marginal of D train is D train X = D. To quantify the target error, we use parameter λ = λ(F; D train , D test ) = min f ∈F (err(f ; D train ) + err(f ; D test )), where err(f ; D train ) = P (x,y)∼D train [y ̸ = f (x)] (and similarly for err(f ; D test )). The error guarantee we can hope for is some function of λ, because λ encodes the (unknown) relationship between the training and test distributions, in that λ is small when there is a concept in the class F that has low error on both training and test distributions. Error bounds in terms of λ are standard (and necessary) in the domain adaptation literature (see, e.g., [BDBCP06, BDBC + 10]) as well as TDS learning (see [KSV24b] ).Properties of Distributions. We make standard assumptions about training marginal D. We denote with N d the standard Gaussian distribution over R d and with Unif({±1} d ) the uniform distribution over the hypercube {±1} d . A distribution D over X is k-tame if for every degree-k polynomial p over X with E x∼D [(p(x)) 2 ] ≤ 1 and every B greater than e k we have P x∼D (p(x)) 2 > B ≤ e -Ω(B 1/(2k) ) . And note that the Gaussian distribution, all isotropic log-concave distributions over R d , as well as the uniform distribution over {±1} d are k-tame for all k ∈ N (see Appendix A.4).For a concept class F, a distribution D over X , ϵ ∈ (0, 1), we say that F has ϵ-L 2 sandwiching degree k with respect to D if for any f ∈ F, there exist polynomials p up , p low over X with degree at most k such that (1) p low (x) ≤ f (x) ≤ p up (x) for all x ∈ X and (2)E x∼D [(p up (x)-p low (x)) 2 ] ≤ ϵ.If the coefficients of p up , p low are all absolutely bounded by B, we say that F has ϵ-L 2 sandwiching coefficient bound B.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We include a paragraph on the limitations of our work in the end of the main paper.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
outlier removal procedure: 
 The key ingredient of our approach is an outlier removal procedure which is closely related to the corresponding procedure proposed by [DKS18] in the context of learning with nasty noise, but ours enjoys stronger error guarantees and works even when the fraction of outliers is arbitrarily large. The last property is important because we aim to handle arbitrary covariate shifts. Our outlier removal procedure outputs a selector g : X → {0, 1} that satisfies two main guarantees, provided examples drawn independently from some arbitrary, unknown distribution D ′ : (1) for any low-degree polynomial p, the part of the expectation of p 2 (x) under D ′ within the selected subset of X (i.e., E x∼D ′ [p 2 (x)g(x)]), is a bounded multiple of the expectation of p 2 (x) under the reference distribution D and (2) the probability of rejecting a fresh sample drawn from D (i.e., P x∼D [g(x) = 0]) is bounded by a multiple of the statistical distance between D and D ′ . Formally, we prove the following theorem. Theorem 3.1 (Outlier Removal, see Appendix E). There exists an algorithm (Algorithm 1) that, given sample access to an arbitrary distribution D ′ over X ⊆ R d , sample access to a k-tame probability distribution D over X , parameters ϵ, α, δ ∈ (0, 1) and k ∈ N, runs in time poly( 1 ϵ (kd) k log 1 δ ) and outputs a succinct poly( 1 ϵ (kd) k log 1 δ )-time-computable description of a function g : X → {0, 1} that satisfies the following properties with probability at least 1 -δ.(a) E x∼D ′ (p(x)) 2 g(x) ≤ 200 α E x∼D [(p(x)) 2 ], for any polynomial p with deg(p) ≤ k. (b) P x∼D [g(x) = 0] ≤ α d TV (D, D ′ ) + ϵ2 . Remark 3.2. In Theorem 3.1, Condition (b) also implies some bound on the rejection rate over the distribution D ′ and, in particular,P x∼D ′ [g(x) = 0] ≤ (1 + α)d TV (D, D ′ ) + ϵ/2.Remark 3.3. Our algorithm further satisfies a strengthened form of Condition (b) (with probability at least 1 -δ). For σ > α/2 and any distribution D ′′ that is 1/σ-smooth w.r.t. D, (i.e. for any measurable set T ⊂ R d we have P x∼D ′′ [x ∈ T ] ≤ 1 σ P x∼D [x ∈ T ]) it is the case that P x∼D [g(x) = 0] ≤ α σ d TV (D ′′ , D ′ ) + ϵ 2 , which in particular implies that P x∼D [g(x) = 0] ≤ ϵ/2 if D ′ itself is 2/α-smooth w.r.t. D.S 0 ← S D ′ \ {x ∈ S D ′ : there is p ∈ R t with (p ⊤ x ⊗k ) 2 > B and p ⊤ M p ≤ 1} for i = 1, 2, . .Let p i ∈ R t be the solution and µ i and the value of the following quadratic program.max p∈R t 1 N x∈S i-1 (p ⊤ x ⊗k ) 2 s.t.: p ⊤ M p ≤ 1 if µ i ≤ 50 α (1 + ∆) then set i max = i -1and exit the loop; else let τ i be the minimum non-negative real number such that the following is true1 N {x ∈ S i-1 : (p ⊤ i x ⊗k ) 2 > τ i } ≥ 10 α P x∼S D [B ≥ (p ⊤ i x ⊗k ) 2 > τ i ] + ∆ Set S i ← S i-1 \ {x ∈ S i-1 : (p ⊤ i x ⊗k ) 2 > τ i } ; Set g(x) to be 0 if and only if either there is p ∈ R t with (p ⊤ x ⊗k ) 2 > B and p ⊤ M p ≤ 1, or (p ⊤ i x ⊗k ) 2 > τ i for some i ∈ [i max ]. Otherwise, set g(x) = 1.The outlier removal procedure of Theorem 3.1 iteratively solves a quadratic program with quadratic constraints (which can be solved efficiently, see Appendix E.1.1) and increases the rejection region by setting g(x) = 0 on each point x where the corresponding (maximum second moment) polynomial takes large values. The procedure halts when the solution of the quadratic program has value bounded by O(1/α) (which implies condition (a)).Proof overview. The main idea for the analysis is that whenever the stopping criterion does not hold, then there is a polynomial with unreasonably large second moment over the remaining part of D ′ (after the rejections). When such a polynomial p exists, there must be a threshold τ for the squared values of p such that D ′ assigns Ω(1/α) times more mass on non-rejected points x with p 2 (x) > τ compared to the reference distribution D. Such points can be safely rejected, because, in that case, the mass of points under D rejected is multiplicatively smaller (by a factor of O(α)) than the corresponding mass under D ′ (which implies condition (b)). Note that the procedure will have to end eventually, because in each iteration, at least one example is removed.In order to account for errors incurred by sampling (from D and D ′ ), it is important to provide a bound on the number of iterations that is independent from the number of examples drawn, because the complexity of the selector g depends on the number of iterations and we need the desired properties of g to generalize to the actual distributions D and D ′ . To this end, we consider the trace of the matrixM i = 1 N x∈S i (x ⊗k )(x ⊗k) ⊤ as a potential function and we show that it reduces by a multiplicative factor in each iteration (see Claim 6 in the Appendix).Comparison with [DKS18] . Among all outlier removal algorithms, ours is most related to the algorithm of [DKS18] , which also removes elements in regions of the form {x : (p(x)) 2 > τ }. However, there are two differences. First, [DKS18] assume that the fraction of outliers is bounded, while ours provides meaningful guarantees even in the presence of arbitrary fraction of outliers. In particular, we can maintain low rejection rates even in the presence of large fractions of outliers by relaxing the bound on the polynomial moments after outlier removal. This is important for PQ learning, because we need low error guarantees even when the amount of distribution shift is arbitrarily large. Second, even when the fraction of outliers is small, our bound on the second moments of polynomials does not depend on the degree and the degree dependence only appears in the runtime of the outlier removal process. This gives new insights on polynomial regression in the presence of outliers (due to distribution shift or noise). In contrast, the moment bound of [DKS18] scales with the degree of the corresponding polynomial and when the degree bound scales with the target learning error, their results become vacuous. This enables us to combine the outlier removal process with L 2 sandwiching results from TDS learning to obtain, for example, the first dimension-efficient robust learners with nasty noise of rate Ω(ϵ) that achieve error ϵ for the class of intersections of halfspaces. While [DKS18] also provide robust learners for this class, they only achieve error guarantees that scale as Õ(k 1/12 ϵ 1/11 ), for intersections of k halfspaces. The key difference between our analysis and that of [DKS18] is that, to bound the number of iterations, we use an appropriate potential function, while [DKS18] ensure that the number of iterations is bounded by making sure to remove at least some fraction of points in each step. As a result, their stopping criterion scales with the target polynomial degree.0 ← 4d 3k ϵ and ∆ 0 ← 200 d 2k log N N log 1 δ 4. S 0 filtered ← S D ′ \ x : max p: p ⊤ M p≤1 (p(x)) 2 > B 0 . 5. While max p: p ⊤ M p≤1 1 N x∈S i filtered (p(x)) 2 > 50 α (1 + ∆ 0 • B 0 ). (a) p i ← arg max p: p ⊤ M p≤1 1 N x∈S i filtered (p(x)) 2(b) Set τ i to be the smallest value of τ subject to:1 N {x ∈ S i filtered : (p i (x)) 2 > τ } ≥ 10 α P x∼S D [B 0 ≥ (p i (x)) 2 > τ ] + ∆ 0 (c) S i+1 filtered ← S i filtered \ {x : (p i (x)) 2 > τ i } (d) i ← i + 1 6. Output (S accept , S reject ) = (S i filtered , S D ′ \ S i filtered ).Note that the procedure ESTIMATE-MOMENTS produces a good spectral approximation for the degree-k moment matrix of D. Formally, Lemma B.1 says that the matrix M is symmetric positivesemidefinite and with probability at least 1 -δ/10 it is the case that every degree-k polynomial p satisfies.9 10 E x∼D [(p(x)) 2 ] ≤ p ⊤ M p ≤ 11 10 E x∼D [(p(x)) 2 ]. (E.1)We now explain how to execute certain steps of our algorithm in polynomial time:• The quantity max p: p ⊤ M p≤1 (p(x)) 2 equals to the largest eigenvalue of the matrix( M ) -1/2 (x ⊗d )(x ⊗d ) ⊤ ( M ) -1/2 ,which can be computed in polynomial time in the dimension m of the matrix. (Note that if the matrix M is not full-rank, then the above is still true if long as ( M ) -1/2 is replaced by the Moore-Penrose pseudo-inverse of ( M ) 1/2 , which again can be computed efficiently. Also note that we used the fact that the matrix M is symmetric.)• The quantity max p: p ⊤ M p≤11 N x∈S i filtered (p(x)) 2 equals to the largest eigenvalue of the matrix( M ) -1/2   1 N x∈S i filtered (x ⊗d )(x ⊗d ) ⊤   ( M ) -1/2 ,which can be computed in polynomial time in the dimension m of the matrix. (Again, if the matrix M is not full-rank, then the above is still true if long as ( M ) -1/2 is replaced by the Moore-Penrose pseudo-inverse of ( M ) 1/2 . Also note that we again used the fact that the matrix M is symmetric.)• The polynomial p i ← arg max p: p ⊤ M p≤11 N x∈S i filtered (p(x)) 2 can be computed by taking the leading eigenvector of ( M ) -1/2 1N x∈S i filtered (x ⊗d )(x ⊗d ) ⊤ ( M ) -1/2and multiplying this vector by ( M ) -1/2 (again, one takes the Moore-Penrose pseudo-inverse if M is not full-rank). • The value of τ i can be computed in time poly(N ) by considering all the candidate values τ of the form (p i (x)) 2 for all elements x in S i filtered , and setting τ i to be the smallest candidate that satisfies the condition in the algorithm.Note that to prove the run-time bound of poly(N ) for the algorithm as a whole we will need to bound the total number of iterations in the main while loop, which is done in Section E.1.3.We now proceed to proving first the correctness of the algorithm in Section E.1.2. Then, in Section E.1.3 we show the required run-time bound.In this section we show that with probability at least 1-δ the algorithm A satisfies the two correctness guarantees in Theorem E.1. We begin by arguing that with probability at least 1 -δ the sets S D and S clean are well-behaved.Claim 1. Let the set S be formed of N i.i.d. samples from a k-tame distribution D, where N ≥C (kd) k ϵ log 1 δ Cand C is a sufficiently large absolute constant. Also, let B 0 = 4d 3k ϵ . Then with probability at least 1 -δ/10 the set S satisfies the following properties for any polynomial p over R d of degree at most k and any pair of values of τ 1 , τ 2 in R :EQUATIONand if the polynomial p further satisfiesEQUATIONProof. Since (p(x)) 2 is a polynomial of degree at most 2k, the every function of the form {1 τ2≥(p(x)) 2 >τ } is an AND of two degree-2k polynomial threshold functions. Since degree-2k polynomial threshold functions have a VC dimension of at most d 2k + 1, we can use Fact A.5 and Fact A.6 to conclude that property (1) holds with probability at least 1 -δ/30. Now, we show that property (2) is likely to be satisfied. Then there is a collection {r 1 , • • • , r m ′ } of degree-k polynomials that satisfyE x∼D [r j (x)r j ′ (x)] = 1 if j = j ′ 0 otherwise.(Such collection necessarily exists via the Gram-Schmidt process.) We let M denote the matrix E x∼D (x ⊗d )(x ⊗d ) ⊤ . Additionally, we consider a basis {g 1 , • • • , g m-m ′ } for the nullspace of M . Now, for x sampled from D we have:• For a specific index j, we have E x∼D [(r j (x) 2 ] = 1 and therefore by Markov's inequality we haveP x∼D (r j (x)) 2 ≤ 2d k ϵ ≥ 1 - ϵ 2d k • Each g j has E x∼D [(g j (x) 2 ] = 0, and therefore P x∼D [g j (x) = 0] = 1.By union bound, all the events above take place for x sampled from D with probability at least1 -m ϵ 2d k ≥ 1 -ϵ 2 .Via the standard Hoeffding bound, with probability at least 1 -δ the events above take place for at least ϵ 2 + 20 N log 20 δ fraction of elements x in S. Since {r j } are orthonormal with respect to M , every degree-k polynomialp ′ satisfying E x∼D [(p ′ (x)) 2 ] ≤ 1 can be decomposed as p ′ = m ′ i=0 α i r i + m-m ′ i=0 β i g i , where each α i is in [-1, 1].Therefore if the events above take place for a point x, then max p ′ of degree k:E x∼D [(p ′ (x)) 2 ]≤1 (p ′ (x)) 2 = max α1,••• ,α m ′ ∈[-1,1] β1,•••β m-m ′ ∈R       m ′ i=0 α i r i (x) + =0 m-m ′ i=0 β i g i (x)       2 ≤     m ′ i=0 ≤ √ 2d k /ϵ |r i (x)|     2 ≤ 2d k (m ′ ) 2 ϵ ≤ 2d 3k ϵ , (E.2)from which Property (2) follows.Finally, we remark that Property (3) holds with probability at least 1 -δ/30 due to an argument analogous to the proof of Lemma B.2 (where in place of f , we have the function 1 p 2 (x)≤B0 ).We now argue that in each iteration i there is a value of τ i satisfying the condition in step (5b) Claim 2. Suppose the set S D is such that it satisfies property (3) of claim 1, i.e. for every degree-k polynomial p satisfyingE x∼D (p(x)) 2 ≤ 1 we have E x∼S D (p(x)) 2 • 1 (p(x)) 2 ≤B0 ≤ E x∼D [(p(x)) 2 ] + 0.01 and the matrix M satisfies Equation E.1, i.e. for every degree-k polynomial p we have9 10 E x∼D [(p(x)) 2 ] ≤ p ⊤ M p ≤ 11 10 E x∼D [(p(x)) 2 ].Suppose it is the case that 1N x∈S i filtered (p i (x)) 2 > 50 α (1 + ∆ 0 • B 0 ) (i.e. the while loop does not terminate at step i). The there exists some τ for which1 N {x ∈ S i filtered : (p i (x)) 2 > τ } ≥ 10 α P x∼S D [B 0 ≥ (p i (x)) 2 > τ ] + ∆ 0 .Proof of Claim 2. For the sake of contradiction, suppose that for every τ ≥ 0 it is the case that1 N {x ∈ S i filtered : (p i (x)) 2 > τ } ≤ 10 α P x∼S D [B 0 ≥ (p i (x)) 2 > τ ] + ∆ 0 . (E.3)Since every element x of S i filtered satisfies (p i (x)) 2 ≤ B 0 we have1 N x∈S i filtered (p i (x)) 2 = ∞ τ =0 1 N {x ∈ S i filtered : (p i (x)) 2 > τ } dτ = B0 τ =0 1 N {x ∈ S i filtered : (p i (x)) 2 > τ } dτ. (E.4)which combined with Equation E.3 implies1 N x∈S i filtered (p i (x)) 2 ≤ 10 α ∆ 0 B 0 + ∞ τ =0 P x∼S D [B 0 ≥ (p i (x)) 2 > τ ] dτ = 10 α ∆ 0 B 0 + E x∼S D p i (x)) 2 • 1 (pi(x)) 2 ≤B0 (E.5)Additionally, since S D is assumed to satisfy property (3) in Claim 1, and M is assumed to satisfy Equation E.1, we have E x∼S D (p i (x)) 2 • 1 (pi(x)) 2 ≤B0 ≤ E x∼D [(p i (x)) 2 ] + 0.(S i filtered \ S i+1 filtered ) ∩ S uncorrupted ≤ 2α 5 (S i filtered \ S i+1 filtered ) ∩ S adversarial .Proof. Since the set S uncorrupted is a subset of the set S clean , we have(S i filtered \ S i+1 filtered ) ∩ S uncorrupted ≤ (S i filtered \ S i+1 filtered ) ∩ S clean (E.7)Also, based on how the algorithm chooses the set S i+1 filtered and the parameter τ i , we have:|S i filtered \ S i+1 filtered | N = 1 N {x ∈ S i filtered : (p i (x)) 2 > τ i } ≥ 10 α P x∼S D [B 0 ≥ (p i (x)) 2 > τ i ] + 200 d 2k log N N log 1 δ .but since S D and S clean satisfy Property 1 in Claim 1, we also have1 N {x ∈ S clean : B 0 ≥ (p i (x)) 2 > τ i } ≤ P x∼S D [B 0 ≥ (p i (x)) 2 > τ i ] + 200 d 2k log N N log 1 δ .Combining the preceding two inequalities yieldsS i filtered \ S i+1 filtered ≥ 10 α {x ∈ S clean : B 0 ≥ (p i (x)) 2 > τ i } .We argue that every x in (S i filtered \ S i+1 filtered ) ∩ S clean satisfies B 0 ≥ (p i (x)) 2 > τ i . Indeed, if x belongs to S i filtered , it also belongs to S 0 filtered and therefore(p i (x)) 2 ≤ B 0 ((p i ) ⊤ M (p i )) ≤ B 0 .It also has to be that (p i (x)) 2 > τ i because of how S i+1 filtered is defined inside the algorithm. Thus, we haveS i filtered \ S i+1 filtered ≥ 10 α (S i filtered \ S i+1 filtered ) ∩ S clean .Since S i filtered \S i+1 filtered is the disjoint union of (S i filtered \S i+1 filtered )∩S clean and S i filtered \S i+1 filtered )∩S adversarial we further conclude that(S i filtered \ S i+1 filtered ) ∩ S adversarial ≥ 10 α + 1 (S i filtered \ S i+1 filtered ) ∩ S clean .Finally, recalling that S uncorrupted is contained in S clean , we conclude the proposition.Overall, the above claim concludes the proof of (α, ϵ)-validity. Now we proceed to proving the spectral 100 α -boundedness. Claim 4. Suppose the algorithm terminates and produces a partition (S accept , S reject ) and the matrix M satisfies Equation E.1. Also, suppose that C exceeds a certain absolute constant. Then, for every polynomial p of degree at most k satisfyingE x∼D [(p(x)) 2 ] ≤ 1, it is the case that 1 N x∈Saccept p(x) 2 ≤ 100 α . (E.8)Proof. Since the matrix M satisfies Equation E.1, we have p ⊤ M p ≤ 11/10 and since the main while loop of the algorithm has terminated, for the final value i max of i it is the case that1 N x∈S i filtered (p(x)) 2 ≤ 11 10 • 50 α • 1 + 200 d 2k log N N log 1 δ • B 0 . Substituting B 0 = 4d 3k ϵ and N ≥ C (kd) k ϵ log 1 δ C, we see that the inequality above yields Equation E.8 when C exceeds a large enough absolute constant.We now prove the run-time bound of poly(N ). Since each step of the algorithm takes time poly(N d k /ϵ) = poly(N ) (see Section E.1.1), in order to obtain a required run-time bound, it is enough to show that the number of iterations of the main while loop is at most N . We argue this via the following claim: Claim 5. Suppose the sets S D and S clean satisfy the properties in Claim 1 and the matrix M satisfies Equation E.1. Then, for every i < i max , we have 1N x∈S i+1 filtered (p i (x)) 2 ≤ 50 α 1 + 200 d 2k log N N log 1 δ • 4d 3k ϵIndeed, since in i-th loop of the algorithm we have1 N x∈S i filtered (p i (x)) 2 > 50 α 1 + 200 d 2k log N N log 1 δ • 4d 3k ϵ ,the claim above implies that necessarily S i+1 filtered ̸ = S i filtered , which means that |S i+1 filtered | ≤ |S i filtered | -1. Therefore the total number of iterations i max is upper-bounded by N . Now, we prove Claim 5.Proof of Claim 5. Since every element x of S i+1 filtered satisfies (p i (x)) 2 ≤ τ i and the set S i+1 filtered is a subset of S i filtered we have1 N x∈S i+1 filtered (p i (x)) 2 = ∞ τ =0 1 N {x ∈ S i+1 filtered : (p i (x)) 2 > τ } dτ = τi τ =0 1 N {x ∈ S i+1 filtered : (p i (x)) 2 > τ } dτ ≤ τi τ =0 1 N {x ∈ S i filtered : (p i (x)) 2 > τ } dτ. (E.9)Now, recall that τ i is the smallest value of τ subject to:1 N {x ∈ S i filtered : (p i (x)) 2 > τ } ≥ 10 α P x∼S D [B 0 ≥ (p i (x)) 2 > τ ] + 200 d 2k log N N log 1 δ .Therefore, for all values of τ smaller than τ i we have1 N {x ∈ S i filtered : (p i (x)) 2 > τ } < 10 α P x∼S D [B 0 ≥ (p i (x)) 2 > τ ] + 200 d 2k log N N log 1 δ ,which combined with Equation E.9 implies Recall that S i+1 filtered is a subset of S 0 filtered and therefore for every element x of S i+1 filtered it is the case that (p i (x)) 2 ≤ B • (p i ) ⊤ M (p i ) ≤ B, which combinded with the definition of τ i implies that τ i ≤ B = 4d 3k ϵ . Substituting this above allows us to conclude the claim.1 N x∈S i+1 filtered (p i (x)) 2 ≤ 10 α 200 d 2k log N N log 1 δ τ i + ∞ τ =0 P x∼S D [B 0 ≥ (p i (x)) 2 > τ ] dτ = 10 α 200 d 2k log N N log 1 δ τ i + E x∼S D p i (x)) 2 • 1 x≤B0 (E.We restate Theorem 3.1: Theorem E.2. There exists an algorithm that, given sample access to an arbitrary distribution D ′ over R d , sample access to a k-tame probability distribution D over R d , parameters ϵ, α, δ in (0, 1), and a positive integer k, runs in time poly (kd) k ϵ log 1 δ and outputs a succinct poly (kd) k ϵ log 1 δtime-computable description of a function g : R d → {0, 1} that satisfies the following properties with probability at least 1 -δ:• Degree-k spectral 200 α -boundedness: For every polynomial p of degree at most k it is the case thatE x∼D ′ (p(x)) 2 g(x) ≤ 200 α E x∼D [(p(x)) 2 ].• (α, ϵ)-validity: we haveP x∼D [g(x) = 0] ≤ α dist TV (D ′ , D) + ϵ 2 ,which in particular implies thatP x∼D ′ [g(x) = 0] ≤ (1 + α)dist TV (D ′ , D) + ϵ/2.We also restate Algorithm 1 as follows: (p(x)) 2 > B 0 , then g(x) is defined to be 0. (See Section E.1.1 to see how to compute this quantity in time poly(N ).) (b) If for some i it is the case that (p i (x)) 2 is greater than τ i , then g(x) is defined to be 0. (c) Otherwise, g(x) is defined to be 1.It is immediate from Theorem E.1 that the algorithm above runs in time poly (kd) k B ϵ log 1δ with probability at least 1 -δ. Furthermore, we also see that the function g can be described using poly (kd) k B ϵ log 1 δ bits and can be computed using this description on a given input x in timepoly (kd) k B ϵ log 1δ . We need the following claim bounding the number of iterations in the algorithm of Theorem E.1, proof of which is deferred until the end of this section. We remark that for Theorem E.1 we bounded the total number of iterations by N , but in this section we will need a bound that depends only on d, k and ϵ and not on N . Claim 6. If the set S D satisfies the condition of Claim 1, then the number of iterations i max of the main while loop in the algorithm of Theorem E.1 satisfies i max = O kd k log(B 0 d) .We now proceed to use Claim 6 to argue the spectral 200 α -boundedness and (α, ϵ/2)-validity. As the first step, we show the following: Observation E.3. There exists a function class G with a VC dimension of at most O(i max d 2k log(i max )), such that all possible values of the function g belong to G.Proof. The function g is necessarily a logical AND of at most i max + 1 functions, one of which is the function indicator of a ball in R d and the other i max are logical OR-s of pairs of degree-2k polynomial threshold functions. Combining this with Fact A.5 and Fact A.4 yields the observation.We start with arguing the (α, ϵ/2)-validity, as well as the stronger condition of Remark 3.3 (implied by Equation E.13): Claim 7. With probability at least 1 -δ/2 over the choice of the sets S D and S D ′ , we haveP x∼D [g(x) = 0] ≤ α dist TV (D ′ , D) + ϵ 2 . (E.12)Furthermore, for σ > α/2 and any distribution D ′′ that is 1/σ-smooth w.r.t. D, (i.e. for any measurable set T ⊂ R d we haveP x∼D ′′ [x ∈ T ] ≤ 1 σ P x∼D [x ∈ T ]) it is the case that P x∼D [g(x) = 0] ≤ α σ d TV (D ′′ , D ′ ) + ϵ 2 , (E.13)Proof. With probability at least 1 -δ/4 the set S D satisfies the condition of Claim 1. Assuming this, we have:P x∼D [g(x) = 0] ≤ imax i=0 P x∼D (p i (x)) 2 ≥ τ i ≤ imax i=0 P x∼S D (p i (x)) 2 ≥ τ i + i max 200 d 2k log N N log 1 δ , (E.14)where the last step used the premise that S D satisfies the condition of Claim 1. Recalling that by Observation E.3 the function g belongs to a function class with VC dimension of O(i max d O(k) log(i max )), and combining this with Fact A.6, we see that with probability at least 1 -δ/4P x∼D ′ [g(x) = 0] ≥ P x∼S D ′ [g(x) = 0] -O i max d O(k) log(i max ) log N N log 1 δRecalling the definition of g, we see that for x in S D ′ , we have g(x) = 0 when for some iteration i, the point x is in the set {x ∈ S i filtered : (p i (x)) 2 > τ i }, we conclude thatP x∼D ′ [g(x) = 0] ≥ imax i=0 |{x ∈ S i filtered : (p i (x)) 2 > τ i }| N -O i max d O(k) log(i max ) log N N log 1 δ (E.15)Now, we recall that for every iteration i we have:1 N {x ∈ S i filtered : (p i (x)) 2 > τ i } ≥ 10 α P x∼S D [(p i (x)) 2 > τ i ] + 200 d 2k log N N log 1 δ ,and therefore:imax i=0 P x∼S D [(p i (x)) 2 > τ i ] ≤ α 10 imax i=0 1 N {x ∈ S i filtered : (p i (x)) 2 > τ i } + 200i max d 2k log N N log 1 δ . (E.16)Thus, combining Equation E.14, Equation E.15 and Equation E.16 we get: Rearranging the inequality above and recalling that α < 1, we conclude that Equation E.12 holds.EQUATIONFinally, we prodeed to argue Equation E.13. For σ > α/2 suppose that the distribution D ′′ is 1/σsmooth w.r.t. D, (i.e. for any measurable set T ⊂ R d we haveP x∼D ′′ [x ∈ T ] ≤ 1 σ P x∼D [x ∈ T ]). Then, from Equation E.17 we haveP x∼D [g(x) = 0] ≤σ P x∼D ′′ [g(x)=0] by σ-smoothness ≤ α 10 P x∼D ′ [g(x) = 0] ≤distTV(D ′′ ,D)+P x∼D ′′ [g(x)=0] + O i max d O(k) log N N log 1 δ .≤ϵ/10 for constant C sufficiently large.Rearranging the inequality above and recalling that α < 1 and σ > α/2, we conclude that Equation E.13 holds. Now, we argue the spectral 200 α -boundedness. Recall that with probability at least δ/20 the matrix M satisfies Equation E.1, which we will henceforth assume. Also recall that Claim 4 says that for every polynomial p of degree at most k satisfying E x∼D [(p(x)) 2 ] ≤ 1, the set S accept given by the algorithm in Theorem E.1 satisfies 1 N x∈Saccept p(x) 2 ≤ 100 α . By inspecting the definition of the function g, we see that for x in S D ′ we have g(x) = 1 if an only if x is in S accept . Therefore,max p of degree k s.t: E x∼D [(p(x)) 2 ]≤1 E x∼S D ′ [g(x)p(x) 2 ] ≤ 100 α (E.20)In order to conclude the spectral 200 α -boundedness condition we need to be able to conclude that the equation above is likely to generalize, i.e. it approximately holds when one replaces the expectation w.r.t. S D ′ with the expectation w.r.t. the distribution D ′ . To show this, we first recall that via Observation E.3 the function g belongs to a function class G with a VC dimension of at most O(i max d 2k log(i max )). We also see that g(x) = 0 for all x satisfying maxp: E x∼D [(p(x)) 2 )]≤1 (p(x)) 2 >10B 0 , because the matrix M satisfies Equation E.1 and therefore if E x∼D [(p(x)) 2 )] ≤ 1 and (p(x)) 2 > 10B 0 , then also ( √ 0.9p) ⊤ M ( √ 0.9p) ≤ 1 and √ 0.9p(x) > B 0 , which implies that g(x) = 0 by the definition of g. We show in Lemma B.2 that with probability at least 1 -δ/20 such function classes satisfysup g∈G p of degree k s.t: E x∼D (p(x)) 2 ≤1 1 N x∼S D ′ f (x)(p(x)) 2 -E x∼D ′ f (x)(p(x)) 2 ≤ O B 0 i max d 2k log(i max ) d 2k log N N log 1 δ 1/4 ≤ 1 ≤ 1 α , (E.21)where the penultimate inequality above is achieved by substituting the bound i max = O kd k log B 0 d from Claim 6 into the expression above, substituting B 0 = 4d 3k ϵ , recalling thatN = C (kd) k ϵ log 1 δ Cand taking C to be a sufficiently large absolute constant. Combining Equation E.21 with Equation E.20 we conclude that with probability at least 1 -δ/20 it is the case thatmax p of degree k s.t. E x∼D [(p(x)) 2 ] ≤ 1 E x∼D ′ (p(x)) 2 g(x) ≤ 101 α ,Overall, with probability at least 1-δ the function g satisfies spectral 200 α -boundedness, (α, ϵ)-validity, as well as the required run-time bound.Finally, we come back to Claim 6, proving which concludes this section.Proof of Claim 6. Let i be an iteration such that i < i max . Since the while loop did not terminate on step i, we havex∈S i filtered (p i (x)) 2 > 100 α . (E.22)At the same time, Claim 5 implies that1 N x∈S i+1 filtered (p i (x)) 2 ≤ 20 α (E.23)Let m ≤ d k denote the dimension of the vector space of degree-k polynomials. For values of i between 0 and i max and for values of j between 1 and m,let the collection of polynomials {R i j } and non-negative real values {λ i j } be defined asR i j = arg max R of degree k s.t: ∀j ′ <j: (R i j ′ ) ⊤ M R=0 R ⊤ M R≤1 1 N x∈S i filtered (R(x)) 2 λ i j = 1 N x∈S i filtered (R i j (x)) 2 (E.24)In particular7 , we have p i = R i 1 . We will use the quantity φ i := m j=1 λ i j as a potential function, for which we have:φ i -φ i+1 = 1 N m j=1 x∈S i filtered \S i+1 filtered (R i j (x)) 2 ≥ 1 N x∈S i filtered \S i+1 filtered (R i 1 (x)) 2 = 1 N x∈S i filtered \S i+1 filtered (p i (x)) 2 = = x∈S i filtered (p i (x)) 2 - S i+1 filtered (p i (x)) 2 ≥ λ i 1 - 20 α (E.25)Where in the end we substituted Equation E.23. Since λ i 1 equals to 1N x∈S i filtered (p i (x)) 2 and has a value of at least 100/α by Equation E.22, the inequality above allows us to concludeφ i+1 ≤ m j=1 λ i j -0.8λ i 1 ≤ m j=1 λ i j - 0.8 m j λ i j ≤ 1 - 0.9 d k φ i (E.26)We now combine the inequality above with the following two observations:• We have φ imax-1 > 100 α > 1,because the algorithm did not terminate in the (i max -1)-th iteration, and therefore Equation E.22 holds.• We haveφ 0 = 1 N m j=1 x∈S 0 filtered (R i j (x)) 2 ≤ B 0 m,where the last inequality follows from the fact that every element x in S 0 filtered satisfies max p of degree k: p ⊤ M p≤1 (p(x)) 2 ≤ B 0 .Overall, the two bounds above, together with Equation E.26 allow us to conclude that:i max ≤ O d k log(B 0 m) = O kd k log(B 0 d) ,where the last step follows by substituting the definitions of m and ϵ.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Justification: We read the code of ethics in its entirety and strongly believe that our research abides by the stated code. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: We include a discussion on the broader impacts of our work at the end of the main paper. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
selective classification with arbitrary covariate shift: 
 In order to provide provable learning guarantees in the presence of distribution shift, when no test labels are available, one reasonable approach is to enable the model to abstain on certain regions for which the training samples do not provide sufficient information. The model should not be able to abstain frequently on samples from the training distribution, since, otherwise the provided guarantees would be vacuous (e.g., when the model abstains always). A formal definition of this framework was given by [GKKM20] and, in this section, we provide the first end-to-end, dimension-efficient algorithms for learning various fundamental classes (e.g., halfspaces) in this setting. PQ Setting. We first consider the case where the test samples are independently drawn from some (potentially adversarial) distribution D test and the goal of the learner is to achieve low error under D test (on points where the learner does not abstain), without abstaining frequently on fresh training samples, as described formally in the following definition of agnostic PQ learning. Definition 4.1 (PQ Learning [GKKM20] ). Let F be a concept class over X ⊆ R d and D a distribution over X . The algorithm A is a PQ-learner for F with respect to D up to error γ, rejection rate η and probability of failure δ if, upon receiving m train labeled samples from a training distribution D train with X -marginal D and m test unlabeled samples from a test distribution D test , algorithm A outputs, w.p. at least 1 -δ, a hypothesis h : X → {±1} and a selector g : X → {0, 1} such that: (a) (accuracy) The test error is bounded as P (x,y)∼D test [y ̸ = h(x) and g(x) = 1] ≤ γ.(b) (rejection rate) The probability of rejection is bounded as P x∼D [g(x) = 0] ≤ η.The error γ and the rejection rate η are, in general, functions of the parameter λ = λ(F; D train , D test ).Adversarial Setting. Another reasonable scenario from [GKKM20] corresponds to the case where the test examples are not independent, but are chosen adversarially as follows. The adversary receives N independent samples S iid from D and substitutes any number of them adversarially, forming a new unlabeled dataset S test which is given to the learner along with a fresh set of independent samples from D, labeled according to some hypothesis f * ∈ F (realizable setting). The goal is to learn a hypothesis h : X → {±1} and a set S g ⊆ S test such that P x∈Stest [h(x) ̸ = f * (x) and x ∈ S g ] ≤ γ and |S iid ∩ (S test \ S g )| ≤ ηN (only a small fraction of i.i.d. points can be rejected). Note that the adversarial setting is primarily interesting in the realizable case, since there is no underlying test distribution and for any meaningful notion learning to be possible, there needs to be some relationship between the training and test labels. In the rest of this section, we focus on positive results for PQ learning, but, as we argue in Appendix C.2, all of our positive results on (realizable) PQ learning also work analogously in the adversarial setting. This is because our outlier removal process (Theorem 3.1) also works when the examples from the distribution D ′ are in fact generated adversarially (see Theorem E.1).We now give the first dimension-efficient PQ learning algorithms for the fundamental concept class of halfspaces, in the realizable setting and with respect to the Gaussian distribution, i.e., when both the training and the test labels are generated by some unknown halfspace and the training marginal D is the standard Gaussian distribution N d .Warm-Up: Homogeneous Halfspaces. We first focus on the class F of homogeneous halfspaces, i.e., functions f : R d → {±1} with f (x) = sign(w • x) for w ∈ S d-1 . Recent work by [KSV24b] showed that there is a simple fully polynomial-time TDS learner for this problem. In fact, their approach readily implies a PQ learner as well.Proposition 4.2 (Implicit in [KSV24b] ). For any ϵ, δ ∈ (0, 1), there is an algorithm that PQ learns the class of homogeneous halfspaces with respect to N d in the realizable setting, up to error and rejection rate ϵ and probability of failure δ that runs in time poly(d, 1 ϵ ) log(1/δ).The algorithm of [KSV24b, Proposition 5.1] rejects when the probability that a randomly chosen example x from the test marginal falls in some particular region D in R d (for which there is an efficient membership oracle) is greater than Ω(ϵ). Since the training marginal is Gaussian, the ERM, run on sufficiently many labeled training examples, outputs a hypothesis h(x) = sign( w • x) such that ∥ ww * ∥ 2 ≤ ϵ ′ , where w * is the ground truth. Region D consists precisely of the points x for which the ERM hypothesis h is not confident: there are two (potential ground truth) unit vectors v 1 and v 2 that are both ϵ ′ -close to w and sign(v1 • x) ̸ = sign(v 2 • x).Crucially, the Gaussian mass of D is known to be poly(ϵ ′ ) • √ d (see, e.g., [Han14] ). Therefore, for PQ learning, we may return the classifier h along with the selector g(x) = 1{x ̸ ∈ D} and note that access to unlabeled test examples is not neeeded to form h and g.General Halfspaces. For the class of general halfspaces (i.e., functions of the form f (x) = sign(w • x + τ ) where w ∈ S d-1 and τ ∈ R), the labeled training samples do not always provide sufficient information to recover the unknown parameters. This is because the bias τ * of the ground truth could take arbitrarily large positive or negative values, in which case all of the training examples will likely have the same label and (almost) no information about the ground truth w * is revealed. The concern in that case is that the test marginal D ′ assigns a lot of mass far from the origin in the direction of w * . By appropriately applying Theorem 3.1 to select a part of the test marginal D ′ that is sufficiently concentrated in every direction (hence even in the direction of w * ), we obtain the following PQ learning result.Theorem 4.3 (PQ Learning of Halfspaces). For any ϵ, δ ∈ (0, 1), there is an algorithm that PQ learns the class of general halfspaces with respect to N d in the realizable setting, up to error and rejection rate ϵ and probability of failure δ that runs in time poly(d log( 1 ϵ ) , log(1/δ)).The first ingredient for Theorem 4.3 is a result from [KSV24b] regarding recovering the parameters of an unknown general halfspace provided labeled examples from the Gaussian distribution, which was previously used for TDS learning. Proposition 4.4 (Halfspace Parameter Recovery, Proposition 5.5 in [KSV24b] ). For ϵ, δ ∈ (0, 1) and τ ∈ R, suppose that S consists of at least m = poly(d, 1/ϵ)e O(τ 2 ) log(1/δ) i.i.d. samples from N d , labeled by some halfspace of the form f * (x) = sign(w * • x + τ * ), for some w * ∈ S d-1 . Then, with probability at least 1 -δ, for w = (x,y)∈S xy/∥ (x,y)∈S xy∥ 2 and τ = w • x for some x from S such that P (x,y)∈S [y ̸ = sign( w• x + τ )] is minimized, we have ∥ w -w * ∥ 2 ≤ ϵ and | τ -τ * | ≤ ϵ.Therefore, in the case when the bias τ * of the unknown ground truth halfspace is not too large in absolute value, the selector can reject all points x for which there exist two halfspaces with parameters close to w and τ accordingly that disagree on x (similarly to the case of homogeneous halfspaces).Once more, such a selector can be implemented efficiently via a convex program.When the bias is large, in TDS learning, checking whether the first O(log(1/ϵ)) moments of the test marginal D ′ match the corresponding Gaussian moments is sufficient to ensure that the distribution is concentrated in every direction and, therefore, even in the unknown direction of w * . In order to obtain a selective classifier for this case, we instead use Theorem 3.1 with k = O(log(1/ϵ)) and ensure that the selected part of the test marginal is indeed sufficiently concentrated in every direction as required. For more details, see Appendix C.1.1.The outlier removal process of Theorem 3.1 enables one to fully control the ratios between the second moment of any low-degree polynomial under the selected part of the test marginal D ′ and its second moment under the reference distribution D, since the provided bound (see condition (a)) does not depend on the degree of the polynomial, but only on the target rejection rate. Combining our outlier removal process with ideas from TDS learning, we provide a general result on PQ learning classes with low L 2 sandwiching degree. In particular, we require the following properties for the hypothesis class F and the training marginal D. Definition 4.5 (Reasonable Pairs of Classes and Distributions). We say that the pair (D, F), where D is a distribution over X ⊆ R d and F ⊆ {X → {±1}} is (ϵ, δ, k, m)-reasonable if the following properties hold: (1) the ϵ-L 2 sandwiching degree of F under D is at most k with coefficient bound B, (2) the distribution D is k-tame and (3) if S consists of m ′ i.i.d. samples from some distribution D over X × {±1} with marginal D and m ′ ≥ m then, with probability at least 1 -δ we have that for any degree-k polynomial p with coefficient boundB it holds | E D X Y [(y -p(x)) 2 ]-E S [(y -p(x)) 2 ]| ≤ ϵ.Property (1) corresponds to the existence of sandwiching approximators, which is known to be important for learning in the presence of distribution shift by prior work on TDS learning [KSV24b] . Property (2) is the tameness condition Definition A.8, which is important for the outlier removal procedure and was used in the work of [DKS18] for similar purposes. Finally, property (3) ensures generalization for polynomial regression.We obtain the following theorem which gives the first dimension-efficient results on PQ learning several fundamental concept classes with respect to standard training marginals, including intersections of halfspaces, decision trees and boolean formulas. The results work even in the agnostic setting. The algorithm runs the outlier removal process once to form the selector and runs polynomial regression on the training distribution to form the output hypothesis. The rejection rate is bounded due to condition (b) in Theorem 3.1 while the accuracy can be shown by applying condition (a) as follows, where f * ∈ F is the concept achieving λ = min f ∈F (err(f ; D train ) + err(f ; D test )) and p up , p low are the corresponding sandwiching polynomials for f * (as per Definition 4.5). We show thatP (x,y)∼D test [y ̸ = h(x), g(x) = 1] ≤ O( λ η ) + ϵ. P (x,y)∼D test [y ̸ = h(x), g(x) = 1] ≤ P (x,y)∼D test [y ̸ = f * (x)] + P x∼D ′ [f * (x) ̸ = sign( p(x)), g(x) = 1] ≤ λ + E x∼D ′ [(f * (x) -p(x)) 2 g(x)]The termE x∼D ′ [(f * (x) -p(x)) 2 g(x)] can be bounded as E x∼D ′ [(f * (x) -p(x)) 2 g(x)] ≤ 2 E x∼D ′ [(f * (x) -p low (x)) 2 g(x)] + 2 E x∼D ′ [(p low (x) -p(x)) 2 g(x)] and since p up , p low sandwich f * , we bound E x∼D ′ [(f * (x) -p low (x)) 2 g(x)] by E x∼D ′ [(p up (x) -p low (x)) 2 g(x)].By applying condition (a) from Theorem 3.1, since (p low (x) -p(x)) 2 and (p up (x) -p low (x)) 2 are squares of polynomials of degree k, we have the following for some sufficiently large constant C ′ .P D test [y ̸ = h(x), g(x) = 1] ≤ λ + C ′ η (E x∼D [(p low (x) -p(x)) 2 ] + E x∼D [(p up (x) -p low (x)) 2 ])The termC ′ η E x∼D [(p up (x) -p low (x)) 2 ] is at most ϵ 3 and C ′ η E x∼D [(p low (x) -p(x)) 2 ] is bounded by O( λ η ) + 2ϵ/3, as E x∼D [(p low (x) -p(x)) 2 ] ≤ 2 E D train [(p low (x) -y) 2 ] + 2 E D train [(y -p(x)) 2 ]. We have that E D train [(p low (x) -y) 2 ] ≤ 2 E D train [(p low (x) -f * (x)) 2 ] + 2 E D train [(y -f * (x)) 2 ] ≤ ϵη C + O(λ), due to sandwiching and the definition of λ. The term E D train [(y -p(x)) 2 ] is ϵη C -close to E Strain [(y -p(x)) 2 ] (due to Definition 4.5) and, since p is the solution of the least squares program,E Strain [(y -p(x)) 2 ] ≤ E Strain [(y -p low (x)) 2 ] ≤ E D train [(y -p low (x)) 2 ]+ ϵη C = O( ϵη C)+O(λ). Remark 4.7. In a semi-agnostic setting where λ is known, then η can be chosen to balance the error and rejection rates in Theorem 4.6, obtaining bounds of O( √ λ), which is known to be best-possible in the PQ setting, even for contrived concept classes (see [GKKM20] ).By combining Theorem 4.6 with bounds on the L 2 sandwiching degree of fundamental concept classes by [KSV24b] (see Appendix A.5), we obtain the results of Table 2 for PQ learning.Note that when step 3 is activated, then, with high probability, we have that the bias τ * of the ground truth is τ * = O( log(1/ϵ)) and, therefore, the samples required to apply Proposition 4.4 is polynomial in 1/ϵ. From Lemma 5.7 in [KSV24b] , we then have that the selector g has Gaussian rejection rate ϵ, as desired. The accuracy guarantee for the case of step 3 is given by the guarantee of Proposition 4.4 combined with the fact that, with high probability, h agrees with the ground truth anywhere outside the disagreement region (i.e., for all x such that g(x) = 1).When step 2 is activated, then the rejection rate is bounded by Theorem 3.1 and the accuracy guarantee is implied by the fact that τ * ≥ C 2 log(1/ϵ)/C (for some universal constant C ≥ 1) and the following reasoning, where we suppose, without loss of generality that h(x) = 1.P x∼D test X [h(x) ̸ = sign(w * • x + τ * ), g(x) = 1] ≤ P x∼D test X [1 ̸ = sign(w * • x + τ * ), g(x) = 1] ≤ P x∼D test X [|w * • x| > |τ * |, g(x) = 1] ≤ E x∼D test X [(w * • x) 2k g(x)] (τ * ) 2k ≤ 400 ϵ (2C 3 log(1/ϵ)) k (C 2 log(1/ϵ)/C) k ,where we used Markov's inequality and the guarantee from Theorem 3.1. Suppose that C 2 is sufficiently larger than C 3 and C 3 is sufficiently large. Then we have that(2C3 log(1/ϵ)) k (C2 log(1/ϵ)/C) k ≤ (1/2) k ≤ ϵ C3 , which gives that P x∼D test X [h(x) ̸ = sign(w * • x + τ * ), g(x) = 1] ≤ 400ϵ C3 /ϵ ≤ ϵ for sufficiently large C 3 .In the proof of Theorem 4.3, we use Proposition 4.4. However, the original version of Proposition 4.4 worked for constant probability of failure. We show the following general lemma which can be used to amplify the probability of success in logarithmic number of rounds. Lemma C.2 (Parameter Recovery Success Probability Amplification). Let X be a vector space and ∥ • ∥ some norm. For some w * ∈ X and ϵ ∈ (0, 1), suppose that an algorithm A outputs with probability at least 0.9 some w ∈ X with ∥w * -w∥ ≤ ϵ. Then, for any δ ∈ (0, 1), if we run A for T = O(log(1/δ)) independent rounds receiving outputs W = {w 1 , w 2 , . . . , w ⊤ }, and take w = arg min w∈W w ′ ∈W ∥w -w ′ ∥, then we have ∥ ww * ∥ ≤ 5ϵ, with probability at least 1 -δ.Proof. Let W G be the subset of W corresponding to w such that ∥w -w * ∥ ϵ, let W B = W \ W G and note that due to a standard Hoeffding bound, |W G | ≥ 3T 4 , with probability at least 1 -δ, for T = C log(1/δ), where C is a sufficiently large universal constant.Say that ∥ w-w * ∥ = α. Then, by the triangle inequality, ∥ w-w ′ ∥ ≥ ∥ w-w * ∥-∥w * -w ′ ∥ ≥ α-ϵ for any w ′ ∈ W G and we have the followingA := w ′ ∈W ∥ w -w ′ ∥ = w ′ ∈W G ∥ w -w ′ ∥ + w ′ ∈W B ∥ w -w ′ ∥ ≥ |W G |(α -ϵ) + w ′ ∈W B ∥ w -w ′ ∥ Let w ∈ W G . We have ∥w -w ′ ∥ ≤ ∥w -w∥ + ∥ w -w ′ ∥ ≤ ∥w -w * ∥ + ∥w * -w∥ + ∥ w -w ′ ∥ ≤ ϵ + α + ∥ w -w ′ ∥,for any w ∈ W . Therefore, in total, we haveA := w ′ ∈W ∥w -w ′ ∥ = w ′ ∈W G ∥w -w ′ ∥ + w ′ ∈W B ∥w -w ′ ∥ ≤ 2ϵ|W G | + (ϵ + α)|W B | + w ′ ∈W B ∥ w -w ′ ∥By the definition of w, we have that A -A ≤ 0. With probability at least 1 -δ, we have0 ≥ A -A ≥ |W G |(α -3ϵ) -(α + ϵ)(T -|W G |) ≥ 3T 4 (α -3ϵ) -(α + ϵ) T 4 ≥ T ( α 2 - 5ϵ 2 )Therefore, α ≤ 5ϵ, which concludes the proof.Our results on realizable PQ learning extend to the following related model, where the evaluation set is formed by some adversary. In the following definition, we consider each element of the considered sets to be a separate object (even if the corresponding value is the same with some other element of the set).). Let F be a concept class over X ⊆ R d and D a distribution over X . The algorithm A is a transductive learner for F with respect to D, up to error γ, rejection rate η and probability of failure δ if the following hold. If the algorithm A has access to labeled examples from the distribution D labeled by some concept f * ∈ F and receives N unlabeled samples S that are formed by some adversary who first draws N i.i.d. unlabeled samples S iid from D and then corrupts any number of elements of S iid and substitutes them by the same number of arbitrary points of X , then A outputs w.p. at least 1 -δ some set S filt and h : X → {±1} such that:(a) (accuracy) The error after filtering is bounded as (x,y)∈S filt 1{y ̸ = h(x)} ≤ γN . For the proof of Theorem 4.6, we filter the evaluation dataset by using degree k outlier removal (see Theorem E.1) and run polynomial regression on the training distribution to find a hypothesis that has low error on the remaining points of the evaluation dataset. Once more, the analysis is analogous to the one for PQ learning.We now prove Theorem 5.3, which we restate for convenience.Theorem C.4 (Tolerant TDS Learning via Sandwiching). For ϵ, θ, δ ∈ (0, 1), let X ⊆ R d and (D, F) be an ( ϵ C , δ C , k, m)-reasonable pair (Definition 4.5) for some sufficiently large universal constant C > 0. Then, there is an TDS learner F with respect to D up to error O(λ) + 2θ + ϵ, tolerance θ and probability of failure δ with sample complexity m + poly( 1 ϵ (kd) k log(1/δ)) and time complexity poly( m ϵ (kd) k log(1/δ)).Note that the notion of tolerance in property testing was introduced in [PRR06] and has been the focus of many works including [FF05, VV11, BCE + 19, RV20, CJKL22, CFG + 22, BH18, CP23]. However, over R d all existing tolerant distribution testing algorithms (such as [VV11] ) have run-times and sample complexities of 2 Ω(d) , which greatly exceeds our run-times. (x,y)∼D test [y ̸ = h(x)] ≤ P x∼D test X [g(x) = 0] + P (x,y)∼D test [y ̸ = h(x), g(x)= 1] and the properties of g according to Theorem 3.1, via an analysis which is analogous to the one used for Theorem 4.6, but with the difference that, since the parameter α of the outlier removal process was chosen to be 1, the valueP (x,y)∼D test [y ̸ = h(x), g(x) = 1] is bounded by O(λ + ϵ C ) (instead of O( λ η )). The term P x∼D test X [g(x) = 0],when the test has accepted, is bounded by 2θ + ϵ/2.For completeness, we assume that d TV (D, D test X ) ≤ θ and observe that due to condition (b),P x∼D test X [g(x) = 0] ≤ P x∼D [g(x) = 0] + d TV (D, D test X ) ≤ 2d TV (D, D test X ) + ϵ C ≤ 2θ + ϵ C .Therefore, the tester will accept with high probability. Furthermore, via Remark 3.3 our tolerant TDS learning algorithm will also with high probability accept any distribution D ′ that is 1/2-smooth with respect to D.Our techniques provide new results in other classical settings as well. In particular, we discuss applications on tolerant testable learning as well as robust learning. In total, our results for polynomial regression can be summarized in Table 2 .Training Marginal D Run-time1 Intersections of ℓ halfspaces Standard Gaussian Uniform on {±1} d d O(ℓ 6 /σ 2 ) 2 Functions of ℓ halfspaces Standard Gaussian Uniform on {±1} d d O(4 ℓ ℓ 6 /σ 2 )3 Decision trees of size s Uniform on{±1} d d O(log(s/σ))4 Formulas of size s, depth ℓ Uniform on{±1} d d √ s•O(log(s/σ)) 5ℓ 2Table 2: Our learning results parameterized by σ, which captures the required precision of the L 2 -sandwiching approximators in each of the settings: (1) agnostic PQ learning with error O( λ η ) + ϵ and rejection rate η, where σ = ϵη, (2) agnostic θ-tolerant TDS learning with error O(λ) + 2θ + ϵ, where σ = ϵ, (3) θ-tolerant testable learning with excess error 2θ + ϵ, where σ = ϵ 2 and (4) robust learning with nasty noise of rate η up to error 4η + ϵ, where σ = ϵ 2 . The probability of failure in each of the cases is some considered constant and η, θ, ϵ ∈ (0, 1).The following theorem gives the first dimension-efficient algorithms for tolerant testable learning (see Definition A.16) for various important concept classes.Theorem D.1 (Tolerant Testable Learning via Sandwiching). For ϵ, θ, δ ∈ (0, 1), let X ⊆ R d and (D, F) be an ( ϵ 2 C , δ C , k, m)-reasonable pair (Definition 4.5) for some sufficiently large universal constant C > 0. Then, there is a tester-learner for F with respect to D up to error opt + 2θ + ϵ, tolerance θ and probability of failure δ with sample complexity m + poly( 1 ϵ (kd) k log(1/δ)) and time complexity poly( m ϵ (kd) k log(1/δ)), where opt = min f ∈F err(f ).Our plan is to once more make use of the outlier removal Theorem 3.1. In this case, is suffices to run tests on the marginal distribution that certify the existence of a low-degree polynomial approximator for the unknown ground truth concept (achieving optimum error), due to the following classical result from [KKMS08] (which has been used for non-tolerant testable learning in [GKK23] ).Proposition D.2 (L 1 regression guarantee, [KKMS08] ). Let F be a concept class over X where X ⊆ R d and D X Y be any distribution over X × {±1} where the X -marginal of D X Y is D ′ . For ϵ ∈ (0, 1) and k ∈ N, suppose that for any f ∈ F there is some polynomial p over X of degree at most k such thatE x∼D ′ [|f (x) -p(x)|] ≤ ϵ.Then, there is an algorithm (L 1 polynomial regression) that, upon receiving a number of i.i.d. samples from D X Y , outputs with probability at least 1 -δ some hypothesis h :X → {±1} with P (x,y)∼D X Y [y ̸ = h(x)] ≤ opt + O(ϵ), where opt = min f ∈F err(f ; D X Y ). The algorithm uses poly(d k , 1 ϵ ) log(1/δ) time and samples.The tester of Theorem D.1 does the following for some sufficiently large universal constant C ≥ 1.1. Runs the outlier removal of Theorem 3.1 with parameters α ← 1, ϵ ← ϵ/C, δ ← δ/C to receive a selector g with the guarantees specified in Theorem 3.1.2. Estimates, using unlabeled samples form D X Y , the value of P x∼D ′ [g(x) = 0] and rejects if the estimated value is greater than 2θ + 2ϵ/C.Otherwise, the tester accepts and runs the algorithm of Proposition D.2 with fresh samples from the distribution DX Y that corresponds to the conditioning of D X Y to g(x) = 1, with parameters ϵ ← ϵ/C and k ← k.Without loss of generality, we have that 2θ+ϵ ≤ 1/2 (otherwise, we may output a random hypothesis). This implies that the runtime does not change asymptotically by conditioning on g(x) = 1 (which can be done through rejection sampling).For completeness, we observe that, by condition (b),P x∼D [g(x) = 0] ≤ d TV (D, D ′ ) + ϵ C and hence P x∼D ′ [g(x) = 0] ≤ 2d TV (D, D ′ ) + ϵ C. By a standard Hoeffding bound, we have that the estimated value for P x∼D ′ [g(x) = 0] (obtained using unlabeled samples from the marginalD ′ of D X Y ) is at most 2d TV (D, D ′ ) + 2ϵC and the tester will, with high probability accept if d TV (D, D ′ ) ≤ θ. For soundness, we want to show that, upon acceptance, for any f ∈ F, there is a polynomial p of degree k such thatE x∼ D [|f (x) -p(x)|] ≤ O( ϵ C ).Then, by Proposition D.2, we have that the output h satisfies err(h; DX Y ) ≤ min f ∈F err(f ; DX Y ) + O(ϵ/C). Moreover we would also have err(h;D X Y ) ≤ P x∼D ′ [g(x) = 0] + P x∼D ′ [g(x) = 1]err(h; DX Y ), by the law of total probability. The second term of the sum can be bounded asP x∼D ′ [g(x) = 1]err(h; DX Y ) ≤ min f ∈F P x∼D ′ [g(x) = 1] P (x,y)∼D X Y [y ̸ = h(x)|g(x) = 1] + O(ϵ/C) = opt + O(ϵ/C).Overall, the bound on err(h; D X Y ) would then be opt + 2θ + ϵ, because after acceptance, P x∼D ′ [g(x) = 0] is bounded, with high probability, by 2θ + O(ϵ/C).It remains to show the polynomial approximation bound. Let f be some element of F and p up , p low the corresponding ϵ 2 C -L 2 sandwiching polynomials. If D is the X -marginal of DX Y , we have the following, by applying the sandwiching property, Jensen's inequality and the definition of D.(E x∼ D [|f (x) -p low (x)|]) 2 ≤ (E x∼ D [p up (x) -p low (x)]) 2 ≤ E x∼ D [(p up (x) -p low (x)) 2 ] ≤ E x∼D ′ [(p up (x) -p low (x)) 2 g(x)] P x∼D ′ [g(x)= 1] By applying condition (a), as well as the fact that P x∼D ′ [g(x) = 1] ≥ Ω(1) (since P x∼D ′ [g(x) = 0]), we have (E x∼ D [|f (x) -p low (x)|]) 2 ≤ O(1) • E x∼D [(p up (x) -p low (x)) 2 ] ≤ O(ϵ 2 /C) Therefore, indeed, E x∼ D [|f (x) -p low (x)|] ≤ ϵ,We also provide the following result for learning with nasty noise (see Definition A.17). While there are algorithms for learning in the nasty noise model that are more efficient than the one we analyze here (see [DKS18] ), we achieve an error bound that is close to the optimal: we only incur a multiplicative factor of 2 from the information theoretically optimal bound of 2η, where η is the noise rate (see Definition A.17). For intersections of halfspaces, for instance, to the best of our knowledge, all prior known dimension-efficient algorithms incurred an error of Ω( √ η) for learning under nasty noise of rate η (see [KKM18, DKS18] ). Theorem D.3 (Learning with Nasty Noise via Sandwiching). For ϵ, η, δ ∈ (0, 1), let X ⊆ R d and (D, F) be an ( ϵ 2 C , δ C , k, m)-reasonable pair (Definition 4.5) for some sufficiently large universal constant C > 0. Then, there is a robust learner for F under nasty noise of rate η with respect to D up to error 4η + ϵ and probability of failure δ with sample complexity m + poly( 1 ϵ (kd) k log(1/δ)) and time complexity poly( m ϵ (kd) k log(1/δ)).Proof. We follow a very similar approach as the one for Theorem D.1. The main differences are two. First, instead of the outlier removal of Theorem 3.1, we apply the outlier removal of Theorem E.1, which works in the adversarial setting. Second, in the nasty noise setting, we assume that the noise rate is bounded and hence we do not need to run any tests in order to obtain the desired guarantees.Recall that in this setting, the learner receives a sample S of size N with S = S iid ∪S adv \S rem , where S iid is an i. ] for any polynomial p of degree at most k. Then, it runs polynomial regression of degree k with coefficient bound B (given by Definition 4.5) over the set S filt and outputs h(x) = sign( p(x)) where p is the output of the polynomial regression routine (of Proposition D.2).We aim to bound P x∼D [f * (x) ̸ = h(x)]. By uniform convergence, we have a bound of the formP x∼D [f * (x) ̸ = h(x)] ≤ P (x,y)∼S iid [y ̸ = h(x)] + ϵ/C ≤ P (x,y)∼S [y ̸ = h(x)] + η + ϵ/C. We further bound the quantity P (x,y)∼S [y ̸ = h(x)] ≤ P (x,y)∼S [y ̸ = h(x), (x, y) ∈ S filt ] + |S\S filt | N ≤ P (x,y)∼S [y ̸ = h(x), (x, y) ∈ S filt ] + 2η.We may apply Proposition D.2 to show that P (x,y)∼S [y ̸ = h(x), (x, y) ∈ S filt ] ≤ η + O(ϵ/C), as long as the following is true for some polynomial of degree at most k.1 N (x,y)∈S filt |f * (x) -p(x)| ≤ O(ϵ/C)Due to the sandwiching property, this is true for the sandwiching polynomial p low for f * (which exists since f * ∈ F -see Definition 4.5). To show this, we may follow an analogous approach as the one for Theorem D.1.We now give the proofs of our outlier removal theorem in the adversarial, as well as the PQ setting.We present our outlier removal result in the adversarial setting: Theorem E.1. There exists an algorithm that satisfies the following specifications for some sufficiently large absolute constant C. The algorithm A is given parameters ϵ, α, δ in (0, 1], a positive integer k, Let the set S D in R d of size N be sampled i.i.d. from a k-tame probability distribution D, and let S D ′ be generated by: 1. Sampling a size-N i.i.d. set S clean from D.2. Adversary corrupting an arbitrary subset of elements in S clean . Formally, S D ′ = S uncorrupted ∪ S adversarial , where S uncorrupted is an adversarially chosen subset of S clean and S adversarial is a set of adversarially chosen points in R d of size N -|S uncorrupted |.Then, with probability at least 1 -δ, the algorithm A given the sets S D and S D ′ will accept a set S accept ⊆ S D ′ satisfying the following two properties:• Degree-k spectral 200 α -boundedness: For every polynomial p of degree at most k satisfyingE x∼D [(p(x)) 2 ] ≤ 1, it is the case that 1 N x∈Saccept p(x) 2 ≤ 200 α .• (α, ϵ/2)-validity: The set S reject ∩ S uncorrupted has a size of at most α|S adversarial | + ϵ 2 N . We describe our algorithm for Theorem E.1 (restating Algorithm 1):1. Input Sets S D ′ and S D of size N in R d , parameters ϵ, δ in (0, 1).  
tolerant tds learning: 
 Another approach to provide provable learning guarantees with distribution shift is to enable rejecting the whole test distribution. The formal definition of this setting was given by [KSV24b] , but the proposed algorithms were allowed to reject even if a miniscule amount of distribution shift was detected. We provide the first TDS learners that are guaranteed to accept whenever the test marginal D ′ is close to the training marginal D in total variation distance (see Definition A.7). Definition 5.1 (Tolerant TDS Learning, extension of [KSV24b] ). Let F be a concept class over X ⊆ R d and D a distribution over X . The algorithm A is a TDS-learner for F with respect to D up to error γ (which is, in general a function of parameter λ), tolerance θ and probability of failure δ if, upon receiving m train labeled samples from a training distribution D train with X -marginal D and m test unlabeled samples from a test distribution D test , algorithm A either rejects or accepts and outputs a hypothesis h : X → {±1} such that, with probability at least 1 -δ, the following hold:(a) (soundness) Upon acceptance, the test error is bounded asP (x,y)∼D test [y ̸ = h(x)] ≤ γ. (b) (completeness) If d TV (D, D test X )≤ θ, then the algorithm accepts. We first observe that tolerant TDS learning is implied by PQ learning. Proposition 5.2 (PQ implies Tolerant TDS Learning, modification of Proposition 56 in [KSV24b] ). Suppose that there is an algorithm A that PQ learns the class F with respect to D up to error γ, rejection rate η and failure probability δ. Then, for any ϵ, θ ∈ (0, 1) there is an algorithm that TDS learns F with respect to D up to error γ + η + θ + ϵ, with tolerance θ and failure probability δ that calls A once and uses O( 1 ϵ 2 log(1/δ)) additional samples and evaluations of the selector given by A.The above result readily follows by two simple observations about the selector g and the hypothesis h in the output of a PQ learner. In particular, we haveP x∼D test X [g(x) = 0] ≤ P x∼D [g(x) = 0] + d TV (D, D test X ) ≤ η + d TV (D, D test X ) and err(h; D test ) ≤ P x∼D test X [g(x) = 0] + P (x,y)∼D test [y ̸ = h(x), g(x) = 1].The TDS learner will reject if the empirical estimate of P x∼D test X [g(x) = 0] is larger than η + θ + Ω(ϵ); otherwise it will output h. Proposition 5.2 allows us to conclude that the realizable tolerant TDS learning algorithm in Table 1 follows from the PQ learning algorithm of Theorem 4.3.In the agnostic setting, however, the error rate of PQ learning is known to be necessarily high (i.e., Ω( √ λ)) even for very simple classes (see Remark 4.7). Therefore, the corresponding TDS learning results implied by Proposition 5.2 do not achieve the optimum error rate for the case of TDS learning (i.e. Θ(λ)). Nevertheless, we are able to use, once more, our outlier removal process directly and obtain the following analogue of Theorem 4.6 for tolerant TDS learning.Theorem 5.3 (Tolerant TDS Learning via Sandwiching). For ϵ, θ, δ ∈ (0, 1), let X ⊆ R d and (D, F) be an ( ϵ C , δ C , k, m)-reasonable pair (Definition 4.5) for some sufficiently large universal constant C > 0. Then, there is an TDS learner F with respect to D up to error O(λ) + 2θ + ϵ, tolerance θ and probability of failure δ with sample and time complexity poly( m ϵ (kd) k log(1/δ)).Furthermore, (via Remark 3.3) we show that our tolerant TDS learning algorithm will with high probability be guaranteed to accept a distribution D ′ that is 1/2-smooth with respect to D.For the full proof, see Appendix C.3. As a corollary of Theorem 5.3, we obtain the results of Table 2 for tolerant TDS learning.Limitations, Broader Impacts, and Future Work. Our current results hold only for a limited class of training marginal distributions (e.g., standard Gaussian or uniform over the hypercube). We leave it as an interesting open question to relax these distributional assumptions, as well as expand the completeness criterion for our tolerant TDS learning algorithms to accept when the test marginal is close to any distribution among the members of some wide class of well-behaved distributions (i.e., satisfy the universality condition as defined by [GKSV23] ). Additionally, we would like to point out that rejecting to predict on certain distributions may lead to unfair or biased predictions if the distributions overlap significantly with the minority groups.A.1 NotationWe use x, w, v to denote vectors in the d-dimensional Euclidean space R d . For some distribution D and a function f , we denote with E x∼D [f (x)] the expectation of the random variable f (x) when x is drawn from D. For a set of points X, we use a similar notation for the empirical expectations overX, i.e., E x∼X [f (x)] = 1 |X| x∈X f (x).In our paper, X ⊆ R d will either be R d or the hypercube {±1} d . We denote with N the set of natural numbers N = {0, 1, 2, . . . }. The expression x • w or x ⊤ w denotes the inner product between two vectors, i.e., x • w = d i=1 x i w i (where x i is the value of the i-th coordinate of x).Throughout this work, we will refer to polynomials whose degree is at most k as "degree-k polynomials" for brevity. We will identify every degree-k polynomial p with the vector of its coefficients. Furthermore, for a vector x in R d we will denote x ⊗k the vector whose entries correspond to the values of all monomials of degree at most k evaluated on x. Both the vector corresponding to a degree-k polynomial and the vector x ⊗k have dimension m, where m is the number of distinct monomials on R d of degree at most k. Note that m ≤ d k and that with this notation in hand we havep(x) = p • (x ⊗k ) = p ⊤ x ⊗k .We will usually consider function classes over R d taking values in {±1} or in {0, 1}. Consider the following definitions:Definition A.1. A halfspace over R d is a function mapping x in R d to sign(w • x + θ) for some w in S d-1 and θ in R. Definition A.2. A degree-k polynomial threshold function (PTF) over R d is a function mapping x in R d to sign(p(x)) for some degree-k polynomial p. Definition A.3. The OR of a collection of function classes F 1 ∨ • • • ∨ F m , is defined as the collection of functions f defined as f (x) = f 1 (x) ∨ • • • ∨ f m (x)for each f i belonging to F i respectively. Analogously, the AND of the collection of function classesF 1 ∧ • • • ∧ F m , is defined as the collection of functions f defined as f (x) = f 1 (x) ∧ • • • ∧ f m (x) for each f i belonging to F i respectively.The following facts about VC dimensions of various classes are standard: Fact A.4. The VC dimension of halfspaces over R d is at most d + 1, and the VC dimensions of degree-k polynomial threshold functions is at most d k + 1. Fact A.5 (e.g. [VDVW09] and references therein.).Let {F 1 , • • • , F m } be a collection of function classes each of which has a VC dimension of V . Then, the VC dimension of F 1 ∨ • • • ∨ F m and F 1 ∧ • • • ∧ F m are at most O(V m log m).We will also need the standard uniform convergence bound for function classes of bounded VC dimension. Fact A.6. Let F be a function class over R d taking values in {±1} with VC dimension at most V , let D be a distribution over R d × {±1}, and let S ⊂ R d × {±1} be composed of N i.i.d. examples from D. Then, with probability at least 1 -δ we havesup f ∈F   1 N (x,y)∈S [|f (x) -y|] -E (x,y)∼D [|f (x) -y|]   ≤ V log N N log 1 δ .The same statement also true if F is taking values in {0, 1} and D be a distribution over R d × {0, 1}.We denote with D, D ′ distributions over X ⊆ R d . For two distributions D, D ′ , the total variation distance between them is defined as follows.Definition A.7. Let D, D ′ be distributions over X ⊆ R d (for some σ-algebra B ⊆ Pow(R d )). Then, the total variation distance between D and D ′ isd TV (D, D ′ ) = sup A∈B P x∼D [x ∈ A] -P x∼D ′ [x ∈ A]We define the family of tame distributions as follows.Definition A.8. A distribution D over X is k-tame if for every degree-k polynomial p over X withE x∼D [(p(x)) 2] ≤ 1 and every B greater than e 2k we haveP x∼D [(p(x)) 2 > B] ≤ e -Ω(B 1 2k ) .It is known that the standard Gaussian distribution, any log-concave distribution, as well as the uniform distribution over the hypercube {±1} d are tame (see [DKS18] and references therein). Fact A.9. Let D be either the standard Gaussian distribution N or the uniform distribution over {±1} d , then, then D is k-tame for any k ∈ N.Fact A.10. Let D be a log-concave distribution over R d , then D is k-tame for any k ∈ N.We provide a formal definition of the L 2 sandwiching property which is key in order to be able to apply our outlier removal process many of for our main learning applications. Definition A.11 (L 2 Sandwiching). For a concept class F, a distribution D over X , ϵ ∈ (0, 1), we say that F has ϵ-L 2 sandwiching degree k with respect to D if for any f ∈ F, there exist polynomials p up , p low over X with degree at most k such that (1)p low (x) ≤ f (x) ≤ p up (x) for all x ∈ X and (2) E x∼D [(p up (x) -p low (x)) 2 ] ≤ ϵ.If the coefficients of p up , p low are all absolutely bounded by B, we say that F has ϵ-L 2 sandwiching coefficient bound B.In order to obtain our learning results, in addition to L 2 sandwiching, we use some further properties of the marginal distribution (see Definition 4.5). The following proposition from [KSV24b] shows that these properties are true for the Gaussian distribution as well as the uniform distribution over the hypercube {±1} d .Proposition A.12 (Appendix D in [KSV24b] ). Let D be either N d or Unif({±1} d ) and let F be some concept class with ϵ-L 2 sandwiching degree k with respect to D. Then,F ϵ-L 2 sandwiching coefficient bound B = d O(k) and (D, F) is (ϵ, δ, k, m)-reasonable, where m = O( 1 δ )(dk) O(k). Finally, we list a number of fundamental concept classes that are known to admit low-degree L 2 sandwiching approximators. Lemma A.13 (Decision Trees, Lemma 34 in [KSV24b] ). Let D be the uniform distribution over the hypercube X = {±1} d . For s ∈ N, let F be the class of Decision Trees of size s. Then, for any ϵ > 0 the ϵ-L 2 sandwiching degree of F is at most k = O(log(s/ϵ)). Lemma A.14 (Boolean Formulas, Theorem 6 in [OS03] and Lemma 35 in [KSV24b] ). Let D be the uniform distribution over the hypercube X = {±1} d . For s, ℓ ∈ N, let F be the class of Boolean formulas of size at most s, depth at most ℓ. Then, for any ϵ > 0 the ϵ-L 2 sandwiching degree of F is at most k = (C log(s/ϵ)) 5ℓ/2 √ s, for some sufficiently large universal constant C > 0. Lemma A.15 (Intersections and Decision Trees of Halfspaces, Lemma 37 in [KSV24b] ). Let D be either the uniform distribution over the hypercube X = {±1} d or the Gaussian N d over X = R d . For ℓ ∈ N, let also F be the class of intersections of ℓ halfspaces on X . Then, for any ϵ > 0 the ϵ-L 2 sandwiching degree of F is at most k = O( ℓ 6 ϵ 2 ). For Decision Trees of halfspaces of size s and depth ℓ, the bound is k = O( s 2 ℓ 6 ϵ 2 ).Our approach provides new results even for standard learning scenarios (without distribution shift).In particular, we provide the first tolerant testable learning algorithms. In the testable learning setting, there is no distribution shift, but rather, the learner receives labeled examples from some distribution D X Y over X × {±1} and is asked to either reject, or accept and output a hypothesis with low error on D X Y . The target error is opt + ϵ, where opt = min f ∈F err(f ; D X Y ). In order to obtain efficient learners, we allow for the algorithm to reject if it detects that the marginal distribution D ′ of D X Y on X is not equal to some given target distribution D which is known to be well-behaved. The tester is, once more, allowed to reject even when D ′ and D differ by a tiny amount. We are interested in tolerant testable learning, where the tester-learner is required to accept when D ′ is moderately close to D and provide the first upper bounds for the problem. Definition A.16 (Tolerant Testable Learning, extension of [RV23] ). Let F be a concept class over X ⊆ R d and D a distribution over X . The algorithm A is a tester-learner for F with respect to D up to error γ, tolerance θ and probability of failure δ if, upon receiving m labeled samples from a distribution D X Y with X -marginal D ′ , algorithm A either rejects or accepts and outputs a hypothesis h : X → {±1} such that, w.p. at least 1 -δ, the following hold:(a) (soundness) Upon acceptance, the error is bounded asP (x,y)∼D X Y [y ̸ = h(x)] ≤ opt + γ. (b) (completeness) If d TV (D, D ′ ) ≤ θ, then the algorithm accepts.The optimum error opt is defined as opt = minf ∈F P (x,y)∼D X Y [y ̸ = f (x)].Finally, we give a definition for the model of learning with nasty noise (proposed by [BEK02] ). Definition A.17 (Learning with Nasty Noise [BEK02] ). Let F be a concept class over X ⊆ R d and D a distribution over X . The algorithm A is a learner for F with respect to D, robust under nasty noise with rate η ∈ (0, 1), up to error γ and probability of failure δ if the following hold. If the algorithm A receives a set of N labeled samples S that are formed by some adversary who first draws N i.i.d. labeled samples S iid from D, labeled by some concept f * ∈ F and then corrupts at most ηN (arbitrarily chosen) elements of S iid and substitutes them by ηN arbitrary points of X × {±1}, then A outputs w.p. at least 1 -δ some hypothesis h :X → {±1} such that P x∼D [f * (x) ̸ = h(x)] ≤ γ.The error γ is a function of the noise rate η.In this section we present two technical lemmas used for the design and analysis of our filtering algorithm. The following lemma allows one to efficiently estimate the moments of a k-tame distribution and is used for the algorithms of Theorem E.1 and Theorem E.2.Input: Set S of size N , containing points in X ⊆ R d , parameter δ and parameter k ∈ N Output:A matrix M Partition S D into √ N parts (S (i) D ) i∈[ √ N ] , each of size √ N .Compute the matrixM i = E x∼S (i) D [(x ⊗k )(x ⊗k ) ⊤ ] for each i ∈ [ √ N ].Let M = M i for some i such that the number of indices j ∈ [ √ N ] for which the following condition holds0.99 • p ⊤ M j p ≤ p ⊤ M i p ≤ 1.01 • p ⊤ M j p , for all degree k polynomials p is at least 0.8 √ N , if such an index i ∈ [ √ N ] exists. Otherwise, let M = M 1 .Lemma B.1. For some sufficiently large absolute constant C, the following holds. There is an algorithm (Algorithm 2) that takes a parameter δ in (0, 1), a positive integer k and N ≥ C (kd) k log 1/δ C i.i.d. examples from a k-tame distribution D over R d . The algorithm runs in time poly(N ) and with probability at least 1-δ the outputs an m×m symmetric positive-semidefinite matrix M that for every degree-k polynomial p satisfies9 10 E x∼D [(p(x)) 2 ] ≤ p ⊤ M p ≤ 11 10 E x∼D [(p(x)) 2 ].Proof. The run-time bound of poly(N ) is immediate. We now argue that the algorithm succeeds with probability at least 1 -δ when the absolute constant C is large enough. The matrix M is symmetric positive-semidefinite because each matrix M i = E x∼Si (x ⊗k )(x ⊗k ) ⊤ is symmetric positive-semidefinite by construction.Let M denote the matrix E x∼D (x ⊗k )(x ⊗k ) ⊤ . Clearly E Si [M i ] = M , and we will use the second moment method to bound the deviation, but first we observe that with probability 1 for every polynomial p in the nullspace of M we also have p ⊤ E Si [M i ]p = 0. Indeed, this is the case because p ⊤ M p = E x∼D (p(x)) 2 means that p(x) 2 = 0 almost surely for x ∼ D. Thus, with probability 1 this holds for a collection of basis elements for the nullspace of M , and consequently for the entire nullspace of M . Now, we bound the deviation between M and M i for polynomials p for which p ⊤ M p > 0. Let m ′ be such that m -m ′ is the dimension of the nullspace of M . Then there is a collection{r 1 , • • • , r m ′ } of degree-k polynomials that satisfy E x∼D [r j (x)r j ′ (x)] = 1 if j = j ′ 0 otherwise.(Such collection necessarily exists via the Gram-Schmidt process.) Overall, for any polynomial pp ⊤ M p = E x∼D [(p(x)) 2 ] = j E x∼D [p(x)r j (x)] 2 Therefore, denoting {e 1 , • • • , e m } the m basis vectors in R m we have M 1/2 p =           E x∼D [p(x)r 1 (x)] E x∼D [p(x)r 2 (x)] . . . E x∼D [p(x)r m ′ (x)] 0 • • • 0           M -1/2   m ′ i=1 c i e i   = m ′ i=1 c i r i (B.1)(Where M -1/2 p is defined to be the Moore-Penrose pseudo-inverse of M 1/2 if M is singular). We now bound the expected Frobenius norm:E Si I -M -1/2 M i M -1/2 2 F = E Si   j,j ′ ∈{1,••• ,m} e ⊤ j I -M -1/2 M i M -1/2 e j ′ 2   = = E Si   j,j ′ ∈{1,••• ,m} 1 j=j ′ -r ⊤ j M i r j ′ 2   = E Si   j,j ′ ∈{1,••• ,m} E x∼D [r j (x)r j ′ (x)] -r ⊤ j M i r j ′ 2   = = j,j ′ E Si E x∼D [r j (x)r j ′ (x)] -E x∼Si [r j (x)r j ′ (x)] 2 = 1 √ N j1,j2∈{1,••• ,m ′ } Var x∼D (r j (x)r j ′ (x)) (B.2)From the k-tameness of distribution D, and the fact that E x∼D [(r j (x)) 2 ] = 1 we see thatVar x∼D (r j (x)r j ′ (x)) ≤ E x∼D (r j (x)r j ′ (x)) 2 = ∞ 0 P r j (x)r j ′ (x)) 2 > B 2 2B dB ≤ 2e 4k + ∞ e 2k e -Ω(B 1/(2k) ) 2B dB = O(k O(k) ). (B.3)Thus, combining Equation B.2 and Equation B.3 and recalling that M is an m × m matrix with m ≤ d k we get a bound for the expected spectral norm of M -M i :E Si I -M -1/2 M i M -1/2 2 ≤ E Si I -M -1/2 M i M -1/2 F ≤ E Si I -M -1/2 M i M -1/2 2 F ≤ 1 N 1/4 mO(k O(k) ) ≤ 1 N 1/4 (dk) O(k)Recalling that N ≥ C (kd) k log 1/δ C , we see that for a sufficiently large absolute constant C we can use the Chebyshev's inequality to conclude that with probability at least 0.9 we have I -M -1/2 M i M -1/2 2 ≤ 10 -3 , which implies that for any p of degree at most k we havep ⊤ M i p = p ⊤ M p + p ⊤ (M i -M )p = p ⊤ M p + p ⊤ M 1/2 (M -1/2 M i M -1/2 -I)M 1/2 p ∈ [(1 -10 -3 )p ⊤ M p, (1 + 10 -3 )p ⊤ M p] Recalling that i is in {1, • • • , √N } and using the standard Hoeffding's inequality, we see that when C is sufficiently large, with probability at least 1 -δ, the above holds for at least 0.95 fraction of indices i. Call such indices good. For any pair of values i 1 , i 2 of good indices we hence have(1 -10 -2 )p ⊤ M i2 p ≤ p ⊤ M i1 p ≤ (1 + 10 -2 )p ⊤ M i2 p , for all pFor any given indices, the above property can be checked by computing the maximum singular value of the matrixM -1/2 i2 M i1 M -1/2 i2(where we take the Moore-Penrose pseudoinverse) and comparing the nullspaces of M i1 and M i2 . Therefore, the output i 1 = i * satisfies the above property for at least 0.8 fraction of the values of i 2 , according to Algorithm 2. Moreover, i * satisfies the above property for at least one good index i 2 = i g (the fraction of good indices is 0.95 and the property is satisfied for at least a 0.8 fraction). Overall, we have that for all polynomials p0.9p ⊤ M p ≤ 0.99p ⊤ M ig p ≤ p ⊤ M i * p ≤ 1.01p ⊤ M ig p ≤ 1.1p ⊤ M pwhich implies the correctness of the algorithm.The following lemma allows one to show that as long as a distribution D ′ is filtered using a low-VCdimension function f , the moments of the resulting filtered dataset approximate well the moments of the distribution one obtains by filtering the distribution D ′ using f . Lemma B.2. Let D be a probability distribution over R d and let F be a function class over R d taking values in {0, 1} with VC dimension V , such that for every f in F we have f (x) = 0 for all x such that max 1N x∼S f (x)(p(x)) 2 -E x∼D ′ f (x)(p(x)) 2 ≤ O B 1 2 V d 2k log N N log 1 δ 1 4Proof. Let p be a polynomial of degree k s.t: E x∼D (p(x)) 2 ≤ 1 and let f be a function in F. We recall that whenever f (x) ̸ = 0 we have maxp: E x∼D (p(x)) 2 ≤1(p(x)) 2 ≤ B and we let ∆ be a positive real number, to be chosen later. We then have via the triangle inequalityE x∼S f (x)(p(x)) 2 -E x∼D ′ f (x)(p(x)) 2 ≤ B/∆ j=0 E x∼S f (x)(p(x)) 2 1 j∆≤(p(x)) 2 <(j+1)∆ -E x∼D ′ f (x)(p(x)) 2 1 j∆≤(p(x)) 2 <(j+1)∆ ≤ B/∆ j=0 E x∼S f (x)j∆1 j∆≤(p(x)) 2 <(j+1)∆ -E x∼D ′ f (x)j∆1 j∆≤(p(x)) 2 <(j+1)∆ + + ∆   B/∆ j=0 E x∼S f (x)1 j∆≤(p(x)) 2 <(j+1)∆ + E x∼D ′ f (x)1 j∆≤(p(x)) 2 <(j+1)∆   ≤ 2∆ + B B/∆ j=0 P x∼S (f (x) = 1) ∧ p(x) 2 ∈ j∆, (j + 1)∆ - -P x∼D ′ (f (x) = 1) ∧ p(x) 2 ∈ j∆, (j + 1)∆ (B.4)The function that maps x to 1 if and only if f (x) = 1 and p(x) 2 ∈ (j∆, (j + 1)∆] is a logical AND of a function in F and two polynomial threshold functions of degree at most 2k. Thus, by Fact A.5 the VC dimension of these functions is at mostO(d 2k + V ) ≤ O(d 2k • V ). Therefore, we can use Fact A.6 together with the inequality above to conclude that with probability at least 1 -δ sup f ∈F , p of degree k s.t:E x∼D (p(x)) 2 ≤1 E x∼S f (x)(p(x)) 2 -E x∼D ′ f (x)(p(x)) 2 ≤ 2∆+O B ∆ V d 2k log N N log 1 δ .Finally, taking ∆ to minimize the expression above, we recover our proposition.C Certified Learning with Distribution Shift, Omitted Details C.1 PQ SettingWe now prove Theorem 4.3, which is restated here for convenience. Theorem C.1 (PQ Learning of Halfspaces). For any ϵ, δ ∈ (0, 1), there is an algorithm that PQ learns the class of general halfspaces with respect to N d in the realizable setting, up to error and rejection rate ϵ and probability of failure δ that runs in time poly(d log( 1 ϵ ) , log(1/δ)).Proof. The algorithm does the following for sufficiently large universal constants C 1 , C 2 , C 3 ≥ 1.1. Compute the values P (x,y)∼Strain [y = 1] and P (x,y)∼Strain [y = -1].2. If either of these values is at most ϵ C2 /C 1 , then let g be the selector of Theorem 3.1 with inputs ϵ, k = C 3 log(1/ϵ), α = ϵ/2 and access to samples from D and D ′ and h the constant hypothesis for the value in {-1, 1} with which the labels are most frequently consistent.3. Otherwise, let w and τ be as in Proposition 4.4 from some sufficiently large labeled sample from the training distribution. Let h(x) = sign( w • x + τ ) and for W = {(w, τ ) :∥w-w∥ 2 ≤ (ϵ/d) C2 /C 1 , |τ -τ | ≤ (ϵ/d) C2 /C 1 }, let g(x)(where g : R d → {0, 1}) be 0 if and only if there are (w 1 , τ 1 ), (w 2 , τ 2 ) ∈ W such that sign(w 1 • x + τ 1 ) ̸ = sign(w 2 • x + τ 2 ) (which can be implemented via a linear program with quadratic constraints). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not release any data and models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not use any existing code, data, or models.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.In fact,[GKSV24], is partially based on a slightly more general hypercontractivity tester by[KS17]. However, this tester will reject some distributions D test ̸ = D train for which dTV(D train , D test ) = o(ϵ).Precisely, we aim to avoid removing more than ϵN outliers, where N is the size of the test dataset.Our notion of outlier removal is connected to the notion of sampling correctors from[CGR16]. We note that over R d the algorithms of[CGR16] run in time 2 Ω(d) , while ours are dimension-efficient.Speaking precisely, there might be multiple choices for the collection of the polynomials {R ⊤ j }. In this case, still, we can choose these polynomials without loss of generality in such a way that pi = R i 1 . 
 
 Appendix:  


Decision: This is a theory submission about the important problem of learning under covariate shift. The authors consider the two recent frameworks of testable learning [KSV24b] and PQ learning [GKKM20], where both frameworks allow abstentions (but in different ways). The goal is to have a computationally efficient learner than does not make a lot of unnecessary abstentions. The authors achieve this for some classes of hypotheses (e.g., intersection of half spaces) and some distributions (e.g., Gaussians) through the use of a spectral outlier removal. The authors' significant contributions were appreciated by the reviewers. There is room for improvement in terms of the clarity of the proofs, especially in the appendices.

Reviews: review: paper_summary: paper_summary: This work considers learning under distribution shift. Here, a learner receives i.i.d labeled data from $D_{train}$, along with i.i.d unlabled data from $D_{test}$. It then builds a classifier with the goal of achieving high accuracy over $D_{test}$. Under arbitrary conditions, this task is impossible, so in the PQ-learning framework the classifier is allowed to abstain from prediction for points with a frequency close to the total-variation distance between $D_{train}$ and $D_{test}$. This work also considers the TDS setting in which the learner is allowed to completely abstain from prediction if it believes its inputs are drawn from a different data distribution. 

The main technical idea of this work is an outlier detection scheme, which (efficiently) computes an outlier detection function $g$ meant to distinguish the points in the training sample from $D_{test}$ that are "far" from the support of $D_{train}$. Their outlier procedure works by iteratively utilizing a quadratic program to find a polynomial of degree k that strongly distinguishes an outlier set. They then remove points until the outlier set only consists of points where the polynomial solution evaluates to very large amounts. The overall idea here is that similar distributions (i.e. if $D_{train} = D_{test}$) will lead to similar polynomial evaluations over them, and consequently the existence of a "separating" polynomial serves as a means to detecting where the distributions differ. 

This idea is reflected in their first result, which shows that the output of this scheme results in a funtion $g$ such that upon filtering with $g$, polynomial evaluations over the test and training distribution must be bounded within a factor of each other (based on tolerance parameters). They additionally bound the runtime of their algorithm. The only requirement for this theorem to hold is that the training distribution must satisfy regularity conditions based on the degree of polynomials being used, and they subsequently show that these conditions are met by isotropic log-concave distributions.

Utilizing this technical idea, this work proceeds by giving PQ-learning algorithm for half-spaces over Gaussian training distributions. Despite the limited scope of this case, this work neverthless provides the first dimension-efficient solution to this problem. Then, this work continues with a more general result for PQ-learning, which, under a condition of "reasonableness" for a pair $(D, F)$, gives an efficient learning algorithm. Under the same condition, this work concludes by giving results for success in the related TDS setting.
strength_weakness: strength_weakness: The latter half of the paper is fairly burdened with algebra and consequently a bit difficult to follow. I would have appreciated a greater focus on intuition with more of the technical details being left to the appendix.
questions: questions: 1. Could you give some intuition for why you began your PQ-results for Gaussian distributions? The outlier-detection procedure works for a more general set of distributions, so it would be interesting if you could spell out the additional properties of Gaussians that make your first result possible.

2. Could you similarly give more intuition about the $(F, D)$-reasonableness condition? The definition feels rather extensive (given 3 conditions in it) and i consequently feel it could merit a longer discussion. As it is currently written, it feels a bit convoluted to me.
limitations: limitations: Yes.
paper_summary: paper_summary: This paper studies two fundamental learning setups, namely PQ learning and TDS learning (Testable Learning with distribution shift), both motivated by covariate shift. 

In PQ learning, the algorithm is given labeled samples from $\mathcal D^{\text{train}}$ over $\mathbb R^d \times \{0, 1\}$ with marginal distribution $D$, and unlabeled samples from some test distribution $\mathcal D^{\text{test}}$ (also over $\mathbb R^d \times \{0, 1\}$). Assume that there is some common hypothesis $h$ that achieves a small error $\lambda$ under both $\mathcal D^{\text{train}}$ and $\mathcal D^{\text{test}}$, the goal of the learning algorithm is to output a selector $g: \mathbb R^d \mapsto \{0, 1\}$ and a classifier $\hat h$ such that (i) $\hat h$ achieves a small error with respect to $\mathcal D^{\text{test}}$ restricted to the acceptance region of $g$, and (ii) most samples from $D$ will not be rejected by $g$. The main contribution is an algorithm that works when (i) the marginal $D$ of $\mathcal D^{\text{train}}$ satisfies some polynomial concentration properties (including isotropic log-concave) and (ii) the hypothesis class admits $L_2$ sandwiching polynomial under $D$. In particular, it achieves a rejection rate of $\eta$ and an accuracy guarantee of $O( \lambda / \eta )$. The bounds are optimal when one sets $\eta = \sqrt{\lambda}$ to balance the rejection rate and accuracy.

In tolerant TDS learning, the algorithm similarly has labeled sample access to $D^{\text{train}}$ and unlabeled sample access to $D^{\text{test}}$. In addition, the algorithm is allowed to reject $\mathcal D^{\text{test}}$ when it finds that the marginals of $D^{\text{train}}$ and $\mathcal D^{\text{test}}$ are at least $\theta$-far from each other in TV distance.  The name ``tolerance'' follows exactly from the constraint that the algorithm is not allowed to reject when $D^{\text{train}}$ and $\mathcal D^{\text{test}}$ are close but not identical to each other. Their algorithm works in a setup similar to the PQ learning case and achieves a final error of $O(\lambda) + 2 \theta + \epsilon$, where $\lambda$ is the optimal error of some common hypothesis under $\mathcal D^{\text{train}}$ and $\mathcal D^{\text{test}}$ (the sum of the two errors), $\theta$ is the tolerance in TV distance, and $\epsilon$ is the error parameter.

The core technique is a spectral based outlier removal procedure that resembles that from [DKS18] that performs filtering on the dataset until the $L_2$ norm of any polynomial under the empirical distribution becomes at most a constant factor of its $L_2$ norm under the reference distribution (the marginal of $\mathcal D^{\text{train}}$). However, the analysis in the current work is tighter, and in particular exhibits non-trivial guarantees even if $\mathcal D^{\text{test}}$ is very far from $\mathcal D^{\text{train}}$ in total variation distance, which is crucial in the technique's application in PQ learning. After ensuring that the spectral of the dataset is appropriately bounded, the algorithm runs polynomial regression, and its guarantees mainly follow from the existence of $L_2$ sandwiching polynomials.
strength_weakness: strength_weakness: A recent work [CKKSV24] shows that non-tolerant TDS learning can also be accomplished when the hypothesis classes has $L_1$ sandwiching polynomials. This makes TDS learning of some important hypothesis classes such as $AC_0$ circuits and quadratic threshold functions possible. However, the technique of spectral outlier removal in this work seems only applicable when one has $L_2$ sandwiching polynomial as otherwise one cannot easily replace moment-matching with spectral boundedness.
questions: questions: In Definition 4.5, should it be "from some distribution $\mathcal D^{\text{train}}$" instead of "from some distribution $\mathcal D$"?
limitations: limitations: Yes, they have.
paper_summary: paper_summary: This work proposes methods for learning under covariance shifts. In particular, it studies PQ learning and TDS learning models. It provides an algorithm based on filtering technique. Given sample access to two distributions, the algorithm produces a filter that rejects points from the second distribution which attains large values on some degree-k polynomial, and does not reject many values of the first distribution.

This algorithm is then applied to learning some function classes (halfspaces and classes with low sandwiching degree) in PQ learning model and to tolerant TDS learning model. In the former model authors obtain a computationally-efficient algorithm, and in the latter an algorithm which does not reject a distribution even if there exists a small but non-negligible shift.
strength_weakness: strength_weakness: I find the main weakness of the paper is the quality of the proofs in the appendix. They are often inaccurately written and require a lot of time to understand the arguments because of the typos. But it seems that there are some inaccuracies in the proofs of the core results beyond typos, which I highlight in the 'Questions' section.
questions: questions: My main question is about Appendix B, which I believe is crucial for the proof of all technical theorems.
I find this section not carefully written with inconsistent notation and typos, which makes it hard to follow the arguments. 

Next, I focus on the parts which were not merely typos:
1. I do not follow equation (B.2). First of all, it should be square of the Frobenius norm. But still second and third step is unclear. Could the authors explain these steps in more detail?
2. If I understand correctly, equation (B.3) requires $2k$-tameness, instead of $k$-tameness. This is because $r_j(x)r_{j’}(x)$ are of degree $2k$.
3. Equation (B.4): I do not follow first inequality, where does first $\Delta$ come from? Since $f(x)(p(x))^2 = \sum_{j = 0}^{B / \Delta} f(x)(p(x))^2 \mathbb{I}(j\Delta \leq (p(x))^2 < (j+1)\Delta)$, we obtain that $\lvert E_{x\sim S} f(x) (p(x))^2 - E_{x\sim D'} f(x)(p(x))^2\rvert \leq \sum_j \lvert E_{x\sim S} f(x) (p(x))^2 \mathbb{I}_j  - E_D f(x) (p(x))^2 \mathbb{I}_j \rvert$, and there is no additive $\Delta$? $(\mathbb{I}_j := \mathbb{I}(j\Delta \leq p(x)^2 < (j+1)\Delta)$
4. Line 922: Can authors clarify why there exists such $\tau_i$? it seems that if I increase $\tau$, then the value on the left decreases to 0, while the value on the right stays positive?

I will consider changing my score when authors address these questions.
limitations: limitations: There are no ethical limitations in this work.
paper_summary: paper_summary: The authors consider the problem of efficiently learning  a concept class under distribution shift, i.e. in the setting where the training data and testing data are drawn from different distributions. They study two frameworks: PQ learning and TDS learning. In the former, the learner is allowed to abstain from classifying a part of the test samples. In the latter, the learner is allowed to abstain entirely if the test distribution is 'visibly' different from the training distribution.

The paper has two main contributions. First, in the PQ setting, the authors obtain the first dimensionally-efficient learning algorithms, under the assumption that the training data is nicely distributed (Gaussian or uniform on the cube) and the concept class is simple (intersection of halfspaces or low-complexity formulas).
Second, in the TDS setting, under the same assumptions, they provide the first efficient algorithms that tolerate small distribution shift in TV-distance. This generalizes earlier results which only tolerate shift 'in the moments' of the distribution (which is a weaker notion).

The proof of these results consists roughly of two steps. First, the authors adapt/improve an existing spectral technique for outlier-removal to show that the test data can be pruned so that it satisfies a 'low-degree spectral boundedness property', without removing too many samples. Second, they show that this spectral boundedness property suffices to apply low-degree polynomial regression to the PQ/TDS-learning problems (in certain settings). In order to do so, they rely on the notion of 'L2-sandwiching polynomials' of [KSV24b]. The important distinction w.r.t. [KSV24b] is that, there, the authors rely on a 'moment-matching property' (which is stronger than spectral boundedness, and in particular, not always satisfied even if the training and test data are close in TV-distance).
strength_weakness: strength_weakness: - Arguably, much of the technical 'heavy-lifting' to obtain the results of this paper is done by the 'L2-sandwiching' of [KSV24b], and to a lesser extend the outlier removal technique of [DKS18] (which the authors do significantly improve on).

- The results apply only to very simple concept classes. It would have been nice to have guarantees in more complicated settings as well, e.g. for (low-degree) polynomial threshold functions. Similarly, the distributional assumptions on the training data are quite restrictive (although it should be noted that this is not uncommon in the literature).
questions: questions: - l62-63: In testable learning, one does not test whether the underlying distribution is actually Gaussian (which is not possible), but rather whether it shares some important characterics with a Gaussian distributions (e.g. its low-degree moments match). I guess the word 'indirectly' is meant to allude to this distinction, but I think this phrasing could be confusing.

- l111-117: It is not clear to me from this paragraph if any work on *distribution-specific* PQ-learning was done before this paper. In particular, it think it would be good to clarify if  1) this work gives the first *efficient* distribution-specific PQ algorithm (but inefficient *distribution-specific* algorithms had been considered, or 2) this work is the first to consider distribution-specific PQ-learning at all.
limitations: limitations: Adequately addressed
paper_summary: paper_summary: This paper studies the problem of PAC learning with covariate shift. In particular, it examines two specific learning frameworks: one is PQ learning, where a learner is allowed to "absent" from some testing samples but is required to have good accuracy for the retained samples; the other is TDS learning, where one is allowed to completely absent if the testing distribution is detected to be far from the training distribution. From a technical point of view, the paper is restricted to cases when the covariate distribution is Gaussian or uniform and when the concept class is nicely approximated by polynomials of low degree (i.e., the so-called "sandwiching" functions). The main contribution appears to extend prior results to handle arbitrary fractions of outliers and provide tighter bounds.
strength_weakness: strength_weakness: The main weakness of the paper, in my opinion, is the presentation. The paper is very hard to read, especially for those who are not immediately familiar with the relevant literature.

I outline the following specific comments:

1. The main text as written does not provide much technical information. For example, Theorem 3.1 is supposed to be the main technical ingredient of the paper, but the proof overview provides nearly no information. Due to the limited time period of the NeurIPS review, I don't have time to delve into the technical details provided in the appendix. I suggest the authors provide a much more detailed overview in the main text. It does not necessarily need to include all the technical details, but it should provide enough information on the logical flow. Perhaps the "Comparison with [DKS18]" section can be omitted to save space?

2. The theorem statements are sometimes framed very sloppily. For example, the $\lambda$ in Theorem 4.1 was never defined (though it appears in the proof); in Lemma B.2., the sentence "we have f(x) = 0 for all x such that..." does not make sense to me, as the subsequent quantifier has nothing to do with x, referring to f(x)=0 always. Since there are too many sloppy statements like this, I lack the energy to check the details carefully.

3. The authors claim to provide "efficient learning algorithms," but all the computational complexities scale exponentially with respect to the error parameters $\epsilon$. Did I miss something? Can this parameter be selected as a constant and be boosted in some way?

4. Is there a specific reason why Theorem 3.1 is stated for the second moment? Is it due to Lemma B.1?

Given these reasons, although I believe this paper has some interesting technical contributions, it would require substantial revision to be suitable for publication at NeurIPS.
questions: questions: See above.
limitations: limitations: N/A

Comments: title: Response to Rebuttal
comment: I thank the authors for the detailed answers to my and other reviewers questions, and I will increase my score.
Thank you for your response. Overall, I'll maintain my current score but increase my confidence.
I thank the authors for the clarifications. I raise my rating to 6. Since I'm not an expert in this particular field, I will have no objection if the other reviewers lean towards acceptance.