Tolerant Algorithms for Learning with Arbitrary Covariate Shift
Authors: Surbhi Goel
Abhishek Shetty
Konstantinos Stavropoulos
Arsen Vasilyan
Venue: NeurIPS 2024 spotlight (2024)
Keywords: pac learning
distribution shift
distribution testing
outlier removal
testable learning
Primary area: learning_theory

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.

Tolerant Algorithms for Learning with Arbitrary Covariate Shift
Surbhi Goel
Abhishek Shetty' Department of EECS UC Berkeley shetty@berkeley. edu
Department of Computer Science University of Pennsylvania surbhig@seas. upenn edu
Konstantinos Stavropoulos Department of Computer Science UT Austin kstavrop@utexas.comm edu
Arsen Vasilyan Department of EECS
UC Berkeley arsenvasilyand@maii.. com
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 [GKKM20], allowing abstention on adversarially generated parts of the test distribution, and TDS learning KSV24b), 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 tiny amount distribution shift.
We address both these challenges for natural function classes, including intersec- tions of halfspaces and decision trees, and standard training distributions, including Gaussians. For PQ learning, we give efficient learning algorithms, while for TDS learning, algorithms can tolerate moderate amounts of distribution shift. At the core of our approach an improved analysis of spectral outlier-removal tech- niques from learning with nasty noise. Our analysis (1) handle arbitrarily large fraction of outliers, which 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 (RV23), and learning with nasty noise.
1 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 Dirain over x (+1), while the data during deployment comes from different distribution Diest, In such scenarios, model can unexpectedly make incorrect
'Supported by an Apple AI/M PhD Fellowship t SSupported the NSF Institute for Foundations of Machine Learning (IFML) and by scholarships from Bodossaki Foundation and Leventis Foundation.
*Supported by NSF awards CCF-2006664, DMS- DMS-2022448, CCF- CCF-1565235, CCF- (CF-1955217, Big George
Fellowship and Fintech CSAIL. Part of this work was conducted while the author was visiting the Simons Institute for the Theory of Computing.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 be a major challenge in healthcare applications [ZBL_ 18 SS20 WOD+21
TCK+
Handling distribution shift when Dirain and Drest are allowed be arbitrary is known be impossible [DLLPIO] To circumvent this impossibility, recent works [GKKM20 KK21 KSV24b GHMS24 KSV24a| allow the machine learning model to additionally abstain (not make 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 abstain on some inputs and simultaneously satisfy: (i) e-accuracy: the probability that I does not abstain and incorrectly classifies an input x from the test distribution Diest is at most c, and (ii) c-rejection rate: the probability that f abstains on an input x from the original distribution Dirain is at most In particular, this implies that J abstains on Diest with probability at most ( (Diraln, Ditest + e, 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 distri- bution Diest if any distribution shift is detected. If there is no distribution shift, then the classifier is
e-accurate on Diest
Prior known algorithms for both these settings have strong inherent limitations, making them imprac- tical for real-world scenarios. For PQ learning, all known algorithms require access 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 IR under the Gaussian training distribution, no PQ learning algorithm has run-time better than 2d 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 [KS224b,, use the low-degree moment-matching approach, which reject distributions Diest * Dirain even when drv (Dirain Diest) = o(c).
1.1 Our results
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 Cz-sandwiching KSV24b) For PQ learning, we give the first cimension-efficeee
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, drv (Dirain Diest) = O(e). We summarize our results in Table
Concept class FF
Digain
PQ runtime
TDS runtime
Halfspaces (realizable) Halfspaces
(00,
d 1/4) (o(1/e))
Olo 1/e)
N(0, 2) ((+1)))
jo11/e)
Intersections of & halfspaces
1),, ({+1))
10())e))
(0
Size-s decision trees
21 ({=199)
(lgg(ss/)
(llgg(s/() oo (log
Size-s depth-& formulas
u ({=1)
d ((
Table 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 RRV23 GKK23 or partially [GKSV23 DKK 23, G3SS2K)) on low-degree moment matching / and
'In fact, (GKSV24, is partially based on slightly more general hypercontractivity tester by KS17 However, this tester will reject some distributions eest o Dtrain for which drv (Dr DDtet) = o(c).

---

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 in Appendix [ for details).
Learning with Nasty Noise, As corollary of our tolerant agnostic learning algorithms we obtain algorithms that withstand an S2(e) amount of nasty noise corruption, and produce classifiers with an error at most e. (In this setting Qe(e) fraction of both labels and examples given to the algorithm are corrupted). The error bound of e compares favorably with the bound of [KMM88] under ((()) nasty noise, which is VE. Compared with the results of [DKS18] in the nasty noise setting, our Appendix D.2 for more information).
Application:
results are incomparable (see relevant discussion in Section
1.2 Our Techniques
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 Drest and the training distribution Dirain is at most (Tviaaiaia DDiest), ), then we think of the dataset as consisting of 1 -drv (Dirsin, Diest) fraction of inliers and an dry Diest) 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 e fraction of the inlier [5]
It was known from KSV24b that the degree-k k polynomial regression performs correctly if the dataset satisfies the degree-k mooment-matching test. Despite its power, the low-degree moment test can reject distributions even e/ e/d0(k) -close to the reference distribution. However (i) it is not clear how to efficiently prune the dataset, the remaining datapoints satisfy the moment-matchiin 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 Ex~z Ex~z[p(x))
[p(x)]] ) does not exceed the analogous expectation with respect to the reference distribution by more than desired factor. Our first key insight is that by using the notion of Ly-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 algorithmss based outlier remova f (see e.g. [DKK 19, LRVI6 HLZ20 Ste 18 DK19 DV04] and references therein), our outlier-removal algo- rithm repeatedly finds regions in R. such that at least This way, as we remove all the points in such outlier-rich regions, we will not remove too many inliers. Finally,
fraction of points in them outliers.
find such outlier-rich regions efficiently using spectral approach. Specifically, if the dataset S does not satisfy the low-degree spectral boundedness, then there is some polynomial p for which [=<s(p(x)? is much greater than the corresponding expectation over the reference distribution. We infer that, for an appropriate value of t, at least 1 fraction of points in the region {x: p(x)²= > 7 are outliers.
1.3 Related work
Domain Adaptation. During the last two decades, there has been long line of works in domain adaptation literature (see, e.g., [BDECP06] BDBC* 10 MMR09 BCK 07 DLLPIO RMH 20
KZZ24] and references therein), aiming to provide generalization bounds for the error 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 [KKM220, which showed that a PQ learner can be efficiently implemented using oracle to distribution- free agnostic learner. In follow-up work by [K22]] 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
PPrecisely, we aim to avoid removing more than eN outliers, where N is the size of the test dataset. "Our notion outlier removal is connected to the notion of sampling correctors from (CGR16). We note that over ded the algorithms of (CGRI6) run in time 20(d) while ours dimenssonneffficient.
3

---

the fundamental class of halfspaces (exp((((Vd)) 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-efficien results for PQ learning of several fundamental concept classes.
TDS Learning. Testable learning with distribution shift defined recently by (KSV24b), where cumension-efficienn algorithms for several concept classes including halfspaces, halfspace intersec- tions, 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 [PR006] and has been the focus of many works including [FFO5 VIII BCE + 19 RV20 CJ
CFG 22 BHIS CP23 However, over I& all existing tolerant distribution testing algorithms (such as [V have run-times and sample complexities of 201d), which greatly exceeds our run-times.
2 Preliminaries
Notation. For details the notation, see Appendix A We denote with x** the vector of monomials of degree i x Fd i.c., x8 is vector of length dt with elements of the form x" II== x", where Σie(q r - k, r, E N. r = .i......ra ra) and is the degree of x". A polynomial p over Rd is a function p(x) = Σ EEN P,x' = pT xp xd where we abuse the notation to denote with p the vector of coefficients of the corresponding polynomial. A polynomial p over [=1]" is defined similarly, but all of the coefficients corresponding to monomials x" where ri > for some i are zero
Learning Setting. We consider distribution D over X' and Dirsin Diest distributions over X' x {+11 such that the marginal on X' of Dirain is DD and the marginal of Diest is x We also consider some concept class F S {X - {- The learner is given access to labeled examples from Dirain as well as unlabeled examples from Diest and the goal is to produce some hypothesis with low error on D but also allowed to abstain from predicting either on specific points (for PQ learning, Def. 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 E F and the training examples are of the form (x. fx)).. where x ~ D. The target test error E for some arbitrarily chosen e E (0, 1). In the agnostic setting. the distributions Dirain and Diest can be arbitrary, except from the assumption that the marginal of Dtrain is D
D. To quantify the target error, we use parameter X X(F; Dirain DDestt
(x..))DDrnii [y * [(x) (and similarly for err(f: f: D)tsst). )). The error guarantee we can hope for is some function of X, 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 X are standard (and necessary) in the domain adaptation literature (see, e.g.. BDBCP06 10) as well as TDS learning (see KSV2446).
minyer(err([; (J; Dirain) + err(f; Deest))) where err(f: Diraiu)
Properties of Distributions, We make standard assumptions about training marginal D. We denote with Wia the standard Gaussian distribution over Rd and with Unif({=114 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 Ex-D (p(x)) < 1 and every B greater than ct we have PX-D [(p(x))² > B] <
-0(BA/(20)) And note that the Gaussian distribution, all isotropic log-concave distributions over Rd, as well as the uniform distribution over {=1)2 are k-tame for all
(see Appendix A.4
For a concept class F. a distribution D over X, e E (0, 1). we say that F has e-Le sandwiching degree i with respect to D if for any f F, there exist polynomials Pup: Plow over X' with degree at
(x) PPww (x)) If the coefficients of Pups Plow are all absolutely bounded by B, we say that F has C- sandwiching coefficient bound B.
most & such that (1) plow (x) < f(x) S (x) for E X and (2) Ex-D [pppp

---

3 Outlier Removal Procedure
The key ingredient of our approach an outlier removal procedure which is closely related the corresponding procedure proposed by [DKSIS] 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 y²(x under D'' within the selected subset of (i.e.,
Ex [p²(x)gt (x)g(x))] (x)]). is bounded multiple of the expectation of n p²(x)) under the reference distribution D and (2) the probability of rejecting a fresh sample drawn from D (i.c., by multiple of the statistical distance between D) and D'. Formally, we prove the following theorem.
= 0)) is bounded
Theorem 3.1 (Outlier Removal, see Appendix D. There exists an algorithm (Algoritim 7 that, given sample access to an arbitrary distribution D over X Rd, sample access k-tame probability distribution 'D over X. parameters c,a, E (0.1) and l E N, runs in time poly(? (kel)* log })) and outputs succinct poly(? 1 (kd)* log })) compp-computable description of function g : X + {0, 1} that satisfies the following properties with probability at least 1-
(a) ExWD [(p(x)) = 200 Ex~D([p(x)) for any polynomial p with deg(p) s k.
(b) Px~Dlg(x) = 0] S a (D, +
Remark 3.2. In Theorem 3.1 Condition (b) also implies some bound on the rejection rate over the distribution D' and, in particular, Px~D' g(x 0J S (1 + (D)rr(D,,D)) + e/2.
Remark 3.3. Our algorithm further satisfies strengthened form of Condition (b) (with probability least 5). For a > a/2 and any distribution D that 1/a-smooth w.r.t. D, (i.e. for any measurable set T C Rd have Px~DD<Xx [x E T _ Fx~D[x E 27) it the case that
P L = 0] S drv D')
which in particular implies that P Px~pll(x) = 0] s 2/ if D' itself is 2/ 2/a-shooth w.r.t. D.
Algorithm 1: Outlier Removal Procedure
Input: Sets Sp, Spy, each of size N, containing points in X' C Rd and parameters k. e, 6, Output: A succinct description a selector function g X {0, 1}
Let t ( B = f3k and = 2d0 log log(1/5)) (//
Compute monomial correlations estimate M by running Algorithm on inputs Sp, and 6/10. S + Sp \ (x E Sp there is E 'R' with (p x0k22 > B and p Mp < 1}
for i 1,2,.... .2,..... N do
Let p. E R' be the solution and μ and the value of the following quadratic program.
max
1
Σ
(p
s.t: p TT Mp $
PER'
N
XESI-
if 14, 50 (1 A) then set imax ii- and exit the loop: a else let Ti be the minimum non-negative real number such that the following is true
1 I (p) x x To)
10
P [
(p) 8 77 +2)
a
XNSD
Set Sr + -i Si (0) @k2 n
Set g(x) to be 0 if and only if either there is E R' with (p xx > B and p Mp < 1, or (p. 0R 2 > Ti for some E [imax]] Otherwise, set g(x) = 1.
The outlier removal procedure of Theorem 3.1 jiteratiely solves a quadratic program with quadratic constraints (which can be solved efficiently, see Appendix [E. and increases the rejection region by setting g(x) = 0 on each point x where the corresponding (maximum second moment) polynomial
5

---

takes large values. The procedure halts when the solution of the quadratic program has value bounded by O(1/a) (which implies condition
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 T for the squared values of p such that D' assigns (2(1/a) times more mass on non-rejected points x with (x() > T compared to the reference distribution D. Such points can be safely rejected, because, in that case, the mass of points under DD rejected is multiplicatively smaller (by factor of O(a)) 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 depends on the number of iterations and we need the desired properties of g to generalize the actual distributions D and D', To this end, we consider the trace of the matrix M;- = NV Exss (x xx**((x (x0k) skyT as a potential function and we show that it reduces by multiplicative factor in each iteration (see Claim 6 in the Appendix).
[x
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))² > 7}. However, there are two differences. First, [DKSI8] 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 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 [DKSI8] 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 L2 sandwiching results from TDS learning to obtain, for example, the first dimension-efficient robust learners with nasty noise of rate s2(c) that achieve error for the class of intersections of halfspaces. While [KST8) also provide robust learners for this class, they only achieve error guarantees that scale as ((K1/12 for intersections of 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 (KKI& ensure that the number of iterations bounded by making sure to remove at least some fraction of points in each step. As result, their stopping criterion scales with the target polynomial degree.
4 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-efficien 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 Deest and the goal of the learner is to achieve low error under Drest (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 concept class over X' C IRd and D distribution over X. The algorithm A is a PQ-learner for JF with respect to D up to error 7, rejection rate v) and probability of failure 6 if, upon receiving Mtrain labeled samples from training distribution Dirain with mmrainaaall D and meett unlabeled samples from a test distribution Diest, algorithm A outputs, w.p. at least 1 - 6, a hypothesis h X + {+1} and selector g : X + {0, 1) such that:

---

(a) (accuracy) The test error is bounded as ((x.)))D [y * h(x) and g(x) = 1| S 7
(b) (rejection rate) The probability of rejection is bounded as Px~ = 0] S 1/.
The error y and the rejection rate v) are, in general, functions of the parameter À = X(F: Dirain Dieet).
Ad Adversarial Setting. Another reasonable scenario from GKKM20 corresponds to the case where the test examples are not independent, but are chosen ad vvvesarially as follows. The adversary receives N independent samples Sid from D and substitutes any number of them adversarially, forming a new unlabeled dataset Stett which is given to the learner along with a fresh set of independent samples from D, labeled according to some hypothesis f E (realizable setting). The goal is to learn a hypothesis h X' + } and set Sg S Steaa such that P w [4(x)= A f*(x) and x E Sy] and [Saa n (Stest \ s I nnN (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 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.
4.1 PQ Learning of Halfspaces
We now give the first dimension-efficiee efficcient 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 Na.
We first focus on the class F of homogeneous halfspaces, i.e. functions f : Rd - {+1} with f(x) sign(w w x) for w E gd-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.
Warm-Up: Homogeneous Halfspaces.
Proposition 4.2 (Implicit in (KSV24b). For any c, E (0, 1), there is algorithm that PQ learns the class of homogeneous halfspaces with respect to Na in the realizable setting, up to error and rejection rale and probability of failure ō that runs in time poly(d, 1) (og(1/)).
The algorithm of KSV24b Proposition 5.1] rejects when the probability that randomly chosen example x from the test marginal falls in some particular region D in Rd (for which there is an efficient membership oracle) is greater than ((c).. 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 || w ||2 I é', 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 and V2 that are both e'-close to w and sign(v x) A sign(v2 x). Crucially, the Gaussian mass of D is known to poly(e')- vid (see, e.g., Han 14)). Therefore, for PQ learning, we may return the classifier h along with the selector 9 = [ & D) and note that access to unlabeled test examples not neeeded to form i and g.
General Halfspaces. For the class of general halfspaces (i.e., functions of the form fxx sign(w x + T) where w E s and 7 E R), the labeled training samples do not always provide sufficient information to recover the unknown parameters. This is because the bias 7" 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 select 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 c,8 E (0, 1), there is an algorithm that PQ learns the class of general halfspaces with respect to Na in the realizable setting, up to error and rejection rate and probability failure ó that runs in time poly poly(dlog(.
(, ,log(1/8)).
7

---

The first ingredient for Theorem 4.3 is 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 e, E (0, 1) and T E R. suppose that S consists of at least m poly(d, 1/c)c log(1/6) /6) i.i.d. samples from Na. labeled by some halfspace of the form (x) = sign(w* x x*),,, J, for some w E Egd-1. Then, with Σ (xx))s xy/ll Σ ((x,))s xyll2 and 7 = W -wxforr ffrr some x from
probability at least 1 8, for w
S such that F(x.))esly + sign W x + F)] is minimized, we have || - wwlla S E and | - S
Therefore, in the case when the bias r² 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 F accordingly that disagree on x (similarly to the case of homogeneous halfspaces). Once more, such selector can be implemented efficiently via a convex program.
When the bias large, in TDS learning, checking whether the first (log((/<e) moments of the test marginal D' match the corresponding Gaussian moments is sufficient to ensure that the distribution concentrated in every direction and, therefore, even in the unknown direction of w*. In order to obtain selective classifier for this case, we instead use Theorem 3.1 with k = (1log(1/e) 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.I.I
4.2 PQ for Classes with Low Sandwiching Degree
The outlier removal process of Theorem 3.J 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 L2 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 distribution over X' C Rd and F C (X' + { is (e, 6, k m))reasonable if the following properties hold: (1) the e-L2 sandwiching degree of F under D is at most & with coefficient bound B, (2) the distribution D is k-tame and (3) if S consists of mn i.i.d. samples from some distribution D over X' x {+1} with marginal D and m' 2 m then, with probability at least 1 5 we have that for any degree-k polynomial p with coefficient bound B it holds EBxxy [(V ( p1 Es((y - S e.
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 Limension-efficien results on PQ learning sev- eral 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.
Theorem 4.6 (PQ Learning via Sandwiching). For E, E (0, let X C Rd and (D,F) be an (eD & C ks m) rrasooable pair (Definition 4.5) for some sufficiently large universal constant C > O. Then, there is an algorithm that PQ learns F with respect to D up to error ( e, rejection rate n and probability of failure 8 with sample complexity m + poly () (kd)+ log(1/0) and time complexity poly(m (kd)* log(1/8)).
The algorithm forms the selector g by applying the outlier removal process of Theorem 3.1 with parameters a, e + 2. 5 < 5/C and k < k. Then, we run the following box-constrained least squares problem, using at least m labeled examples Sursin from Dirsin, where
Proof of Theorem 4.6
8

---

t= dh and B is the value specified in Definition 4.5
min (x..)) 1yy - p(x))) s.t. p has degree at most & and coefficient bound B
p Let P be the solution. The algorithm returns the selector 9 and the classifier h(x) sign (f)))
The rejection rate is bounded due to condition (b) in Theorem 3.I while the accuracy can be
shown by applying condition (a) follows, where f FF is the concept achieving A =
minzex(crr((f Diraim) + err f: Diest) and Pup. Plow are the corresponding sandwiching polynomi-
als for f (as per Definition 4.5)
We show that PP ((xx))DDoa [y & lxx), g(x) = 1] s O(2)) +c.
P Iv + h(x), (x)) (x.g)>
1]
P 1 l [x)]+ P (x) # sign()())). = 1]
(x,))~Dten
x-D
( - "(x)))
The term Bx - 2(x))² can be bounded as Ex (xx "(x))) <
2 [f Plow [zz) + 2 Ex [(Piow (x) - )(x))) and since Pup. Plow sandwich
f", we bound Ex-D' [xx Plow (x))² (x)] by Ex [Pup (x) - Piow (x)))
By applying condition (a) from Theorem 3.1 since (plow (x) - )(x))² and (Pup - Plow (x) are squares of polynomials of degree k. we have the following for some sufficiently large constant C".
C"
Iu + h(x), g(x)= = =] P Dime:
[Fxlo/( - ((x)) + Ex (appoe/((PPpPPPP (xx - -Poo (x))
The term C ExxD (Pup(x)) - Piow (x))² is at most and S. Ex~ [(Poow (x) - p( [(x is bounded
77 by 0(²) + 23, as Fx ((Piow (x) - f())) S 2 R.prrrm (FPtow (x) - y)² + 2 Eprrain [(v ((
77
We have that Eprrain [Plow (x) 2 S 2 2 (Plow (x) - f )1 + Exrrain [ly f (x)) <
~ + O()), due to sandwiching and the definition of X. The term Eprrain ((y - f(x)) )=] is E -coose to
EStrain
(v p(x))² 2] (due to Definition 4.5) and. since P is the solution of the least squares program.
Es E. ( S Es....m [V Plow (x) S EDusin [(V- -iu--PPoww- [x)) +((). O
Remark 4.7. In semi-agnostic setting where À is known, then v) can be chosen to balance the error and rejection rates in Theorem 4.6) obtaining bounds of O (V))). which is known to be post-pos in the PQ setting, even for contrived concept classes (see [GKKM20).
By combining Theorem 4.6 with bounds the L2 sandwiching degree of fundamental concept classes by [SV24 (see Appendix we obtain the results of Table 2 for PQ learning.
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 KSV24bb). Let F be concept class over X C Rdd and 'D a distribution over X. The algorithm A is a TDS-learner for F with respect to 'D up to error 7 (which is, in general a function of parameter X), tolerance @ and probability of failure o if, upon receiving Marain labeled samples from training distribution Dirain with X'mmrginna D and Mest unlabeled samples from a test distribution Diest algorithm A either rejects or accepts and outputs hypothesis h X + [+1} such that, with probability at least 1 - 6, the following hold:
(a) (soundness) Upon acceptance, the test error is bounded as P(x.))) Iy + h(x)) S 7.
(b) (completeness) If dry (D, Diest) S 6, 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 (KS224b])
Suppose that there is an algorithm A that PQ learns the class F with respect to D up to error Y. rejection rate and failure probubility 8. Then, for any e,0 E (0,1) there is an algorithm that TDS learns F with respect to 'D up to error 7 + 1 + + e, with tolerance O and failure probubility 5 that calls A once and uses O 2 log( (18) 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 PQ learner. In particular, we have IP x- [g(x) = 0] S P [g = 0] +
drv (D, xxx ) I 7 + drv (r,(DDD) ") and crr(h; Dieat) - P x [x(x) = 0] + IP (xxa))DDaa [U of
h(x),g(x) = 1]. The TDS learner will reject if the empirical estimate of P D (x()) = 0] is
larger than 1j + 0 - S)))); otherwise it will output h.
Proposition 5.2 allows to conclude that the realizable tolerant TDS learning algorithm in Table T 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., (VVx)) even for very simple classes (see Remark 4.7 Therefore, the corresponding TDS learning results implied by Proposition [.2] do not achieve the optimum error rate for the case of TDS learning more, our outlier removal process directly and
(i.e. (A)). Nevertheless, we are able to use, obtain the following analogue of Theorem 4.6 for tolerant TDS learning.
Theorem 5.3 (Tolerant TDS Learning via Sandwiching). For e, B, 8 E (0,1), let X S R and (D,F) be an ( (E. &. k. m) reasonable pair (Definition 4.5) for some sufficiently large universal constant C > O. Then, there is an TDS learner F with respect to 'D up to error O(2) 20 + c, tolerance 0 and probability of failure ö with sample and time complexity poly( th (kd)² log(1/6)).
Furthermore, (via Remark 3.3)
we show that our tolerant TDS learning algorithm will with high probability be guaranteed 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 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 the distributions overlap significantly with the minority groups.
Acknowledgements. We thank the anonymous reviewers of NeurIPS 2024 for their constructive feedback. We thank Adam Klivans for insightful conversations and helpful references. K.S. thanks Aravind Gollakota for useful discussions regarding PQ learning of homogeneous halfspaces and the observation that no unlabeled test examples are needed in this case. A. V. thanks Shyam Narayanan for helpful conversations about robust mean estimation and outlier removal.
References
[BCE+19] Eric Blais, Clément I. Canonne, Talya Eden, Amit Levi, and Dana Ron. Tolerant junta testing and the connection to submodular optimization and function isomorphism. ACM Transactions on Computation Theory (TOCT), 114):1133, 2019.
[BCK+07] John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman. Learning bounds for domain adaptation. Advances in neural information processing systems, 20, 2007.
[BDBC 10] Shai Ben- David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 19:151-175, 2010.
[BDBCP06] Shai Bev-ia John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19, 2006.
[BEK02] Nader H Bshouty, Nadav Firon, and Eyal Kushilevitz. Pac learning with nasty noise. Theoretical Computer Science, 288(2):255-277 2002.
10

---

[BH18] Avrim Blum and Lunjia Hu. Active tolerant testing. In Conference On Learning Theory, pages 474-497. PMLR, 2018.
[CFG*22] Sourav Chakraborty. Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Exploring the gap between tolerant and non-tolerant distribution testing. Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), 245:1-23, 2022.
[CGR16] Clément L Canonne, Themis Gouleakis, and Ronitt Rubinfeld. Sampling correctors. In Proceedings of the 2016 ACM Conference Innovations in Theoretical Computer Science, pages 93-102, 2016.
[CJKL22] Clément L Canonne, Ayush Jain, Gautam Kamath, and Jerry Li. The price of tolerance in distribution testing. In Conference Learning Theory, pages 573-624, PMLR, 2022.
[CP23] Xi Chen and Shyamal Patel. New lower bounds for adaptive tolerant junta testing. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1778-1786. IEEE, 2023.
[DK19] Ilias Diakonikolas and Daniel M. Kane. Recent advances in algorithmic high- dimensional robust statistics, 2019.
[DKK 19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-864, 2019.
[DKK Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Effi- cient testable learning of half'spaces with adversarial label noise. Advances in Neural Information Processing Systems, 36, 2023.
[DS188] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1061-1073 2018
[DLLPI0] Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pages 29-1336 JMLR Workshop and Conference Proceedings, 2010.
[DV04] John Dunagan and Santosh Vempala. Optimal outlier removal in high-dimensional spaces. Journal of Computer and System Sciences, 68(2):335-373, 2004. Special Issue on STOC 2001.
[FFO5] Eldar Fischer and Lance Fortnow. Tolerant versus intolerant testing for boolean properties. In 20th Annual IEEE Conference on Computational Complexity (CCC pages 135-140. IEEE, 2005.
[GHMS24] Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty. Adversarial resilience in sequential prediction via abstention. Advances in Neural Information Processing Systems, 36, 2024.
[GKK23] Aravind Gollakota, Adam Klivans, and Pravesh Kothari. A moment- approach to testable learning and a new characterization of rademacher complexity. Proceedings of the fift--ffth annual ACM Symposium on Theory of Computing, 2023.
[GKKM20] Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. Advances in Neural Information Processing Systems, 33: 13559191155870 2020.
[GKSV23] Aravind Gollakota, Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Tester-learners for halfspaces: Universal algorithms. Advances in Neural Information Processing Systems, 36, 2023.

---

[GKSV24] Aravind Gollakota, Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. An efficient tester-leamer for halfspaces. The Twelfth International Conference on Learning Representations, 2024.
[Han14] Steve Hanneke. Theory of disugreement-based active learning. Foundations and Trends in Machine Learning, 7(2-3):131330, 2014.
[HLZ20] Samuel B. Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estima- tion made simple, via regret minimization. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc.
[KK21] Adam Tauman Kalai and Varun Kanade. Efficient learning with arbitrary covariate shift. In Algorithmic Learning Theory, pages 350-864. PMLR, 2021.
[KMМ88] Adam Klivans. Pravesh K Kothari, and Raghu Meka. Efficient algorithms for outlier- robust regression. In Conference On Learning Theory, pages 1420-1430. PMLR, 2018.
[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6) 2008.
[KOS08] Adam Klivans, Ryan O'Donnell, and Rocco A Servedio. Learning geometric concepts via gaussian surface area. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 541 541-550. IEEE, 2008
[KS17] Pravesh K Kothari and Jacob Steinhardt. Better agnostic clustering via relaxed tensor norms. arXiv preprint arXiv: 171.v0171 2017.
[KSV24a] Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning intersections of halfspaces with distribution shift: Improved algorithms and sq lower bounds. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2944-2978. PMLR, 30 Jun-03 Jul 2024.
[KSV24b] Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2887-2943. PMLR, 30 Jun-03 Jul 2024.
[KZZ24] Alkis Kalavasis, Ilias Zadik, and Manolis Zampetakis, Transfer learning beyond bounded density ratios. arXiv preprint arXiv:2403.11965 2024.
[LRV16] Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 665-6744 2016
[MMR09] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Proceedings of The 22nd Annual Conference on Learning Theory (COL.T 2009), Montréal, Canada, 2009.
[OS03] Ryan O'Donnell and Rocco A Servedio. New degree bounds for polynomial threshold functions. In Proceedings of the thirty-fitth annual ACM symposium on Theory of computing, pages 325-334, 2003.
[PRR06] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 1012-1012 2006.
[RMH+20] levgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younès Bennani. survey on domain adaptation theory: learning bounds and theoretical guarantees. arXiv preprint arXiv:2004.11829 2020.
12

---

[RV20] Ronitt Rubinfeld and Arsen Vasilyan. Monotone probability distributions over the boolean cube can be learned with sublinear samples. arXiv preprint NXXv:20022.33155. 2020.
[RV23] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learn- ing algorithms. Proceedings of the fifty-fifth annual ACM Symposium on Theory of Computing, 2023.
[SS20] Adarsh Subbaswamy and Suchi Saria. From development to deployment: dataset shift, causality, and shift-stable models in health ai. Biostatistics. 21(2):345-352, 2020.
[Ste18] Jacob Steinhardt. Robust learning: Information theory and algorithms. Stanford University, 2018.
[TCK+ Niels K Ternov, Anders N Christensen, Peter JT Kampen, Gustav Als, Tine Vestergaard, Lars Konge, Martin Tolsgaard, Lisbet R Hölmich, Pascale Guitera, Annette H Chakera, al. Generalizability and usefulness of artificial intelligence for skin cancer diagnosties: An algorithm validation study. JEADV Clinical Practice, 1(4):344-354, 2022.
[VDVW09] Aad Van Der Vaart and Jon A Wellner. A note bounds for ve dimensions. Institute of Mathematical Statistics collections, 5:103, 2009.
[VV11] Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via clts. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 685-694, 2011.
[WOD+21] 21] Andrew Wong, Erkin Otles, John P Donnelly, Andrew Krumm, Jeffrey McCullough, Tooolyy Justin Pestrue, Marie Phillips, Judy Konye, Carleen Penoza, al. External validation of a widely implemented proprietary sepsis prediction model hospitalized patients. JAMA Internal Medicine, 181(8):1065-1070 2021.
Olivia DeTroyer- Cooley,
[ZBL+18] John Zech, Marcus Badgeley, Manway Liu, Anthony Costa, Joseph J Titano, and Eric Karl Oermann. Variable generalization performance of a deep learning model to detect pneumonia in chest radiographs: a cross sectional study. PLoS medicine, 15(11))e100268) 2018.
13

---

A Extended Preliminaries
A.1 Notation
We use x, W, V to denote vectors in the d-dimensional Euclidean space Rd. For some distribution D and function
denote with [x=D[f(x)) the expectation of the random variable (x) when is drawn from D. For a set of points X, we use a similar notation for the empirical expectations over X, i... Ex=xi = [XT Exex fxx. In our paper, X' S _ will either be R2 or the hypercube {+1]d. We denote with N the set of natural numbers N (0, 1,........ The expression x or w denotes the inner product between two vectors, i.e., X Σ J.W;; (where x; is the value
of the i-th coordinate of x).
A.2 Polynomials
Throughout this work, we will refer to polynomials whose degree is at most k as "degree-k polyno- mials" for brevity. We will identify every degree-k polynomial p with the vector of its coefficients. Furthermore, for vector in I we will denote x the vector whose entries correspond to the values of all monomials of degree at most & evaluated on x. Both the vector corresponding to a degree-k k polynomial and the vector x 8* have dimension m, where m is the number of distinet monomials on IRd of degree at most k. Note that m S d and that with this notation in hand we have
p(x) p (x @k) p x 8k
A.3
Learning theory
We will usually consider function classes over Rdd taking values in {+1} or in (0, 1}. Consider the following definitions:
Definition A.1. A halfspace over Rd a function mapping x in IRd to sign(w x + 0) for some w in g and in IR.
Definition A.2. A degree-k polynomial threshold function (PTF) over IRd is function mapping x in Rd to sign( for some degree-k polynomial p.
Definition A.3. The OR of collection of function classes Fi V ........... V.n is defined the collection of functions f defined as f(x) = fi (x) V v... fm (x) for each fa belonging to F; respectively. Analogously, the AND of the collection of function classes F, A A.... is defined as the collection of functions f defined as fxx = f1 (x) A ... fm (x) for each f; belonging to F, respectively.
The following facts about VC dimensions of various classes are standard:
Fact A.4. The VC dimension of halfspaces over TRd is at most + 1, and the VC dimensions of degree-k polynomial threshold functions is at most dt 1. Fact A.5 (c.g. [VDVW99] and references therein.). Let [Fi..... FFm be a collection of function
classes each of which has VC dimension of V. Then, the VC dimension Fi ... V. Fm and F1 A A... F. 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 function class over R& taking values in {+1) with VC dimension most V, let D be distribution over Idd x {+1), and let S c. Rd x {+1} be composed of N i.i.d. examples from D. Then, with probability at least 1 we have
Σ l1f(x) - vll
[lf(x) wll
V log N N
sup fEF
log
N
(x.1)D
(X.U)ES
The same statement also true F is taking values in {0, 1} and D be distribution over IRd 10, 1}.
A.4 Properties of Distributions
We denote with D, D' distributions over C RRd. For two distributions D, D', the total variation distance between them is defined as follows.
14

---

Definition A.7. Let D, D' be distributions over A' _ R (for some o-algebra B _ ))w(RR)). the total variation distance between D and D is
Then,
drv D')
sup P A AEB
P x- xwDi
X
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' with Ex~D(<((x)) S 1 and every greater than e we have Px--D((((x))² > B] B -0(
It is known that the standard Gaussian distribution, any log-concave distribution, well as the uniform distribution over the hypercube {=1]² 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}", , then, then D is k-tame for any k E N.
Fact A.10. Let D be a log-con log-concave distribution over R4, then D is k-tame for any k E N.
A.5
Sandwiching Polynomials
We provide a formal definition of the L2 sandwiching property which is key in order be able to apply our outlier removal process many of for our main learning applications.
Definition A.11 (L2 Sandwiching). For concept class a distribution over X, E (0, 1), we say that FF has ca sandwiching degree k with respect to D if for any f E FF, there exist polynomials Plow (2) (eopD((Pp(()
Pup- Plow over X' with degree most i such that (1) Plow (x) S fxx I Pup for all x E X and
(x) Plow (x)) $ e. If the coefficients of Pup. Plow are all absolutely bounded by B, we say that F has 22C2 sand windwiching coefficient bound B.
In order obtain our learning results, in addition to L2 sandwiching, we use some further properties of the marginal distribution (see Definition 4.5). The following proposition from [KS224b] shows that these properties are true for the Gaussian distribution as well as the uniform distribution over the hypercube [=1]a.
Proposition A.12 (Appendix D in (KSV24b).. Let 'D be either Na or Unif( and let F be some concept class with c- L2 sandwiching degree with respect to Then, F e- L- sandwiching coefficient bound B = O(k) and (D,F) is (e, Ó, k. re-reaabbal,,, where 0 ((k))
Finally, we list a number of fundamental concept classes that are known admit low-degree Lz sandwiching approximators.
Lemma A.13 (Decision Trees, Lemma 34 in KSV24b) ). Let D be the uniform distribution over the hypercube X' = {=1)".
a For N, let F be the class of Decision Trees of size s. Then, for any e > 0 the e- L2 sandwiching degree of F is most i O(log(s/e).
Lemma A.14 (Boolean Formulas, Theorem 6 in [OS03] and Lemma 35 in KSV24bl). Let D be the the hypercube X = {+1]². For 8, E N, let F be the class of Boolean formulas of size at most 8, depth at most f. Then, for any >> O the 6-L2 sandwiching degree of F is most (C log(s/ //))///) //s for some sufficiently large universal constant C O.
uniform distribution
Lemma A.15 (Intersections and Decision Trees of Halfspaces, Lemma 37 in KSV24b)) Let DD be either the uniform distribution over the hypercube X = {=1}² the Gaussian Na over X = Rd. For E N, let also F be the class of intersections of l halfspaces on X. Then, for any > 0 the E-L2 sandwiching degree of F is at most k = O.E) For Decision Trees of halfspaces of size and depth
the bound is l Ō 2g6
A.6 Other Learning Settings
Our approach provides new results even for standard learning scenarios (without distribution shift). 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 Dxy over X x [+1} and is asked to either reject, or accept and output a hypothesis with low error on Dxy. The target error is opt + e, where opt minser err(f: Dxy). In order to obtain efficient
15

---

learners, we allow for the algorithm to reject if it detects that the marginal distribution D' of xxy on X' is not equal to some given target distribution D which is known to well-behaved. The tester is, once more, allowed to reject even when 'D' and D differ by tiny amount. We are interested in tolerant testable learning. where the tester-learner is required accept when DD' moderately close to DD 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 Ed and D a distribution over X. The algorithm AA is tester-learner for with respect D up to error tolerance & and probability of failure if, upon receiving m labeled samples from distribution Dxy with X--marginal D', algorithm A either rejects or accepts and outputs hypothesis h: X + {+1} such that, w.p. at least 1 - 8, the following hold:
(a) (soundness) Upon acceptance, the error is bounded as P ((xx))DXx (y # h(x)) S opt + y-
(b) (completeness) If drv (D, D') _ 0, then the algorithm accepts.
The optimum error opt is defined opt minjer P(x.))>Dxylu ly # [(x)].
Finally, we give definition for the model of learning with nasty noise (proposed by [EK02
Definition A.17 (Learning with Nasty Noise [EK02]). Let F concept class over C Rdd and D distribution over X. The algorithm A is a learner for JF with respect to D, robust under nasty noise with rate 77 E (o, 1). up to error and probability of failure algorithm A receives set of N labeled samples S that are formed by some adversary who first draws N i.i.d. labeled samples Säa from D, labeled by some concept f E F and then corrupts at most N (arbitrarily chosen) elements of Snd and substitutes them by n,N arbitrary points of X' x
the following hold. the
{+1}. then A outputs w.p. at least 1 some hypothesis h X' - {=1} such that PxxDDf" (x) + h(x)] S 7-
The error y is function of the noise rate 1).
B Additional Tools
B.1 Miscellancous lemmas
In this section we present two technical lemmas used for the design and analysis of our filtering algo- rithm. The following lemma allows one to efficiently estimate the moments a k-tame distribution and is used for the algorithms of Theorem E.T and Theorem
Algorithm 2: Monomial Correlations Matrix Estimation
Input: Set S size N, containing points in X' C Rd, parameter and parameter & E N Output: A matrix M Partition Sp into VN parts (Sh) )SElVN- each of size VN.
Compute the matrix M, Ex (xx*))xx (x**)T for each E [VN].
Let M = M, for some i such that the number of indices j E [VN] for which the following condition holds
0.99 P My S p Ma S 1.01 p MMp, for all degree k polynomials p
is at least 0.8vN, if such an index é E [VN] exists.
Otherwise, let M Mi.
Lemma B.1. For some sufficiently large absolute constant C, the following holds. There is an algorithm (Algorithm 2) that takes a parameter 8 in (0, 1), positive integer k and N Z C' ((kd)+ log 1/8) ii.dd examples from a k-tame distribution over Rd. The algorithm runs in time poly(N) and with probubility at least 1 the outputs an m x m symmetric sexidive-eeiddefiite matrix M that for every degree-k polynomial satisfies
9
11
E 10 X>D
[((()))²
Mp
E [((x)))
10
16

---

Proof. The run- uu-timee 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 eesitiee-emideffiitt because each matrix M; = Ex-s, [xx (x ] is symmetric positive-semidefniite by construction.
Let M denote the matrix Ex~D (xx**)( Clearly Eg, [M,] = M, and we will use the second moment method to bound the deviation, but first observe that with probability for every polynomial p in the nullspace M we also have p Es, [M,]p = O. Indeed, this is the case because p _ Mp = Ex~pl (p(x))² means that p(x)² = 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; for polynomials p for which p Mp > 0. Let m' be such that m'' is the dimension of the nullspace of M. Then there collection {ri,-" .'mm 3 of degree-k polynomials that satisfy
{0
ifj=
E Iry (x)r3) (x)]
otherwise.
(Such collection necessarily exists via the Gram-Schmidt process.) Overall, for any polynomial p
p' MP
E x~D 1x(((()) = Σ E
(())))()))
Therefore, denoting fei, em the basis vectors in I we have
Ex (p(x)r (x)
Ex (x)))2(x)
m'
m
1
Ex D (p(x)) rm (x)
M M-2
Σ
Cee;
=
cri
(B.1)
(Where M 1 is defined to be the Moore- Perroee pseudo-invers of 1/2 if M is singular). We now bound the expected Frobenius norm:
E
I -
M 101MM11100
M/ 1/2
E
Σ
1M-M-1122 M.-M-MMMMMMPP es))
S.
J. mm]
E (xx())x) -13 (.]Mirr)) {
)²
E
Σ
- 11 M:rr)
E
Σ
x
Aid's (dd' m)
[dN''(,,... m)
E (XDD
(x,(((r)
(r,(x)))x(())
Var Varx~D(T,
S;
xm.;
3.3'
(B.2)
From the k-tameness of distribution D, and the fact that
= 1 we see that
/ P P(rs(x)ry (x))² B 2B dB <
Var Varx- S x (x))
2k -
2B dB (K))) (B.3)
E22
Thus, combining Equation B.2 and Equation B.3 and recalling that M is an m x m matrix with m S dt we get bound for the expected spectral norm of M M;:
E |||T 1-2
M, 1/2
E [|| 5
M 1/2 1/2
E
21
N1/4 mO( <
N1/4 (dk)
17

---

p: (x Recalling that N 2 C ((kd)* log
we that for sufficiently large absolute constant C. we can use the Chebyshev's 's inequality to conclude that with probability at least 0.9 we have
1/6) log
|| - M- 1/2 1./2M,-- 1/22 S 10-3, which implies that for any p of degree at most & we have
p M.p=p' Mp p (M; M)p pp Mp + M (M 1/2 /) E [(1-10 "pp Mp. + 10 Mpl
Recalling that i is in {1...., vN) and using the standard Hoeffding's inequality, we see that when C' is sufficiently large, with probability at least indices i. Call such indices good. For any pair of values i1, i2 of good indices we hence have
the above holds for at least 0.95 fraction of
- -1-00->pp M S M, < (1 + 10- Mi,P, for all
For any given indices, the above property can be checked by computing the maximum singular value of the matrix M M, Mr, M, 1/2 (where we take the Moore-Penrose pseudoinverse) and comparing the nullspaces of Mr, and My Therefore, the output é i' satisfies the above property for at least 0.8 fraction of the values of 22 according to Algorithm 2 Moreover, i' satisfies the above property for at least one good index iz ig (the fraction of good indices 0.95 and the property is satisfied for at least 0.8 fraction). Overall, we have that for all polynomials p
0.9p' Mp & 0.99p p M. S 1.01p' M., S 1.1p Mp
which implies the correctness of the algorithm.
The following lemma allows one to show that as long as distribution D' is filtered using a low-VC: dimension 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 DD be a probability distribution over R2 and let F be a function class over IRd taking values in {0, 1} with VC dimension V, such that for every f in F have f(x) 0 for all such that max
p: Bx-=((((x))²31 (p(x))2 B. Let DD' be probability distribution over Rd and S be collection of N i.i.d. samples from DD' then with probability at least - 5 we huve
log N 1 #
sup JEF, p&t Sk, Ex
Σ [(x))(()))]] x
EE [[())(((() < <0 (vd X~D
N log 5))
N
Proof. Let p be polynomial of degree k s.t: Ex~D(p(x)) < 1 and let f be function in F. We (p(x))² < B and we let A be positive real recall that whenever f(x) + 0 we have max
number, to be chosen later. We then have via the triangle inequality
E [xxx))(x))
E. [(())((())]]
x
XND
B/A
E x~S
(()))((())211/30000))))))))))) s xND
E
B/A
E [
E [[ +
x
x-Di
B/A
+ A
Σ
Exns [(x))) + EXWDD | [[()))))5((0)))))))H)))) 5
/=0
B/A
(f(x)= 1) (p(x)2 E (jS. (14.0++))a)]
2A + B
p
x
f=
(f(x) = 1) (xx)pE (14.+1144) 1)]
p
(B.4)
XaDD
18

---

The function that maps to 1 if and only if f(x) = and p(x)² E (jA, (j 1) is logical AND of function in FF and two polynomial threshold functions of degree at most 2k. Thus, by F.ct the VC dimension of these functions is at most O(dak + V) I O V). Therefore, we can use Fact A.6 together with the inequality above to conclude that with probability at least
sup FEF, p degree & s.t: Ex (p(x))" $1
E [Fxx))(x))] x
E [[())(((x))]] x-D
- 2
B A
Vd log N
log 8
N
Finally, taking A to minimize the expression above, we recover our proposition.
C Certified Learning with Distribution Shift, Omitted Details
C.1 PQ Setting
C.1.1 General Halfspaces
We now prove Theorem 4.3 which is restated here for convenience.
Theorem C.1 (PQ Learning of Halfspaces). For any c, 6 E (0, there is an algorithm that PQ learns the class of general halfspaces with respect to Na in the realizable setting, up to error and rejection rate and probability of failure ó that runs in time poly poly(dlo((t), (doos(t))oog(/8)))
Proof. The algorithm does the following for sufficiently large universal constants C1 C2, C3 2
1. Compute the values IP (xx.))SSeain /y 1] and (xx.)) (v = -1].
2. If either of these values is at most e² CC, then let g be the selector of Theorem 3.1 with inputs k = C3 (og()/)), a e/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 7 be as in Proposition 4.4 from some sufficiently large labeled sample from the training distribution. Let h(x) sign ( x x++ F) and for W = {(w, T) (C1))//Ci,17 - S (e/d))=/CC
let g(x) (where Rd + {0, be be Of and only if there are (W1, T1), (W2.7e) T2) E W such that sign +1+ & sign (w2 x
||w- - w ||2 S
(which can be implemented via a linear program with quadratic constraints).
4. Return (g, h).
Note that when step activated, then, with high probability, we have that the bias T" of the ground truth is n" = O (O(T/oo((1// (oe(1 and, therefore, the samples required to apply Proposition 4.4 is polynomial in 1/c. From Lemma 5.7 in [KSV24b). rejection rate e, 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, agrees with the ground truth anywhere outside the disagreement region (i.e., for all x such that g(x) 1).
then have that the selector g has Gaussian
When step 2 is activated, then the rejection rate is bounded by Theorem 3.1 and the accuracy guarantee
implied by the fact that r* > /C2 log(1/e)/C (for some universal constant C 2 1) and the following reasoning, where we suppose, without loss of generality that (xx)
x Draat (xxx A (wn x + ++)"), = 1]
F x-
[1 * sign( w-
x + 7-) gxx)) 1]
P ||w" x | (x)))
x D
E Dian
[(w" ( [x))
(r*)2k
400 (2Ca log(1/e))*
(C2 (oloo/1//)//0 (1/))/C***
where used Markov's inequality and the guarantee from Theorem 3.1
Suppose that C2 is (2C, log(1/e))*
sufficiently larger than C3 and C3 is sufficiently large. Then we have that
(Ca loxT/e//C
<
19

---

(1/2) S C which gives that Px D [1(x) o sign(w" "x+T"))) = 1] - 400 fe S e for sufficiently large C3.
In the proof Theorem 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 logarithmic number of rounds.
Lemma C.2 (Parameter Recovery Success Probability Amplification), Ler be a vector space and || some norm. For some w E X and E (0, 1), suppose that an algorithm A outputs with probability at least 0.9 some E X with Iw" w|l S E. Then, for any E (0, 1), if we run A for T ((log(//o)) independent rounds receiving outputs W {w', w2 ...., w }. and take - ||wwwl|, then we have | - w-| S. 5e, with probability at least 1- -
w arg minwew Ew'ew I
|| 1 with probability at least 6, for T == C' log(1/5), where C is sufficiently large universal constant.
Proof. Let Wa be the subset of W corresponding to w such that ||w - -w"l| S c, let WB = W \ We and note that due to a standard Hoeffding bound, |Wal 2 32'
Say that || w- w" = a. Then, by the triangle inequality, ||w- 2 || w w-1l-//" |||w" -w'l- 2 a- for any w/ E We and we have the following
Ā =
Σ W'EW
w w'l
= Σ
1 - w/ll +
w w'll
W'EWe
w'EWs
2 Wo e) + Σ
lw - w'
w'EWn
Let W E WG. have ||w- wwll S | +| -
w/ll S
w' || -
w w w/l
c+ a + | w'll, for any w E W. Therefore, in total, we have
A Σ
w|
Σ w'EWo
||
w'll +
Σ
||w w'll
W'EW
w'EW's
s Wc[Wal + (c+a) WB +
Σ
W - -www
w'EWB
w
By the definition of w, we have that Ā A O. With probability at least 8, we have
0 2 Ā- A
Wal(a - 3c) (a + -WWla)
3T
2
(a - 3c) - (a + c)
4
2 T a 5c
2
2
Therefore, a S 5e, which concludes the proof.
C.2 Adversarial Setting
Our results on realizable PQ learning extend to the following related model, where the evaluation set 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).
Definition C.3 (Tranductive Learning (KKKM20). Let J. be a concept class over X RRd and D distribution over X. The algorithm A is a transductive learner for F with respect to D, up to error rejection rate 17 and probability failure 5 if the following hold. If the algorithm AA has access to labeled examples from the distribution 'D labeled by some concept f" E F and receives N unlabeled samples S that are formed by some adversary who first draws N i.i.d. unlabeled samples Sna from D and then corrupts any number of elements of Sna and substitutes them by the same number of arbitrary points of X, then A outputs w.p. at least 8 some set San and h X - {+1) such that:
(a) (accuracy) The error after filtering is bounded E(x,)e L(v * h(x)) S N.
20

---

(b) (rejection rate) The rejection rate of ii.. examples is #(x x E Snd (S') Smi) S n.V.
In particular, we have # #xx E S Smn) s 2n.N.
Our proofs of Theorems 4.3 and 4.6 generalize in this setting exactly analogously, with the only difference being the use of Theorem E.1 in place of Theorem 33. for the outlier removal process. The learning phase is not different, since the learner has sample access to clean examples from the labeled training distribution.
For the proof of Theorem 4.3 we either run the outlier removal process to filter the evaluation dataset in order to ensure that it concentrated in every direction (in the case when almost all the training examples have the same label) or, if the training examples are indeed informative, we reject only the examples that fall inside the disagreement region. The arguments hold analogously.
For the proof of Theorem 4.6 we filter the evaluation dataset by using degree outlier removal (see Theorem [.T] and run polynomial regression on the training distribution to find 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.
C.3 Tolerant TDS Learning
We now prove Theorem 5.3 which we restate for convenience.
Theorem C.4 (Tolerant TDS Learning via Sandwiching). For c, c,0,8 10, S R and (D,F)
be an ( ( Ø k. reasooabl pair (Definition 4.5) for some sufficiently large universal constant C > O. Then, there is an TDS learner F with respect to 'D up to error O(x) 20 c, tolerance and probability of failure 8 with sample complexity m + poly (kd)* log(1 (1))) po (kd))* 1og(1/8))
and time complexity
Note that the notion of tolerance in property testing was introduced in [RR006] and has been the
focus of many works including [FFO5] VVil BCE 19 RV20 CJKL22
CFG $2 BH18 CP23).
However, over Rd all existing tolerant distribution testing algorithms (such as [VI1l have run-times and sample complexities of 20((), which greatly exceeds our run-times.
Proof of Theorem 5.3 The algorithm first runs the outlier removal process of Theorem 3.1 with c/C, 8 8/C and k Using a large enough sample from the test marginal Dixst, the algorithm estimates the quantity Fx (x) = 0) and rejects if the estimated value is larger than 20 + g. Otherwise, it runs the following box-constrained least squares problem, using at least m labeled examples Seraān from Dirain where d and B is the value specified in Definition 4.5
parameters a +
receive the selector g X - 10. 1}.
min ((xx)) [(v p(x))²]
p has degree most l: and coefficient bound B
Let ② be the minimizer the above program. The algorithm accepts and returns classifier h(x) = (fgn(
Soundness follows from the observation that ((x.a))DD== ly * h(x)] S P PxnDi [g(x) 0]
P ((x.))>Diess [y * f(x),, gx) = 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
a of the outlier removal process was chosen to be 1, the value P P(x.a)>Dean [y * h (xx,, g(x) = 1] is
bounded by O() + &) (instead of ((²)) The term P FxwDi (Ø(x) = 0), when the test has accepted, bounded by 20 c/2.
For completeness, we assume that dDv Diest) < 0 and observe that due to condition (b) P. Px~De=" [g(x) 0] < (x)Dll(x) = 0] + (Dv (Tv(D,Dtest)
2dTV (D. Diest) + G <
20
+ 7
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 /22-smooth with respect to D.
D
21

---

D Applications to Other Learning Settings
Our techniques provide new results in other classical settings as well. In particular, we discuss applications on tolerant testable learning as well robust learning. In total, our results for polynomial regression can be summarized in Table
Concept class
Training Marginal D
Run-time
Standard Gaussian Uniform on [+1]a
1016
Intersections of & halfspaces
Standard Gaussian Uniform on [+1]4
2 Functions of & halfspaces
3 Decision trees of size
Uniform on {=1]2
(log((s/))
4 Formulas of size s, depth
Uniform on [+1]2
dv=-((lo((s/o))
Table 2: Our learning results parameterized by a, which captures the required precision of the L2-sandwiching approximators in each of the settings: (1) agnostic PQ learning with error O ( + and rejection rate y). where e?): (2) agnostic 0-tolerant TDS learning with error O(A) 20 + e, where a = 6, (3) f-tolerant testable learning with excess error 20 + e, where o = e² and (4) robust learning with nasty noise of rate y) up error 4n where e2. The probability of failure in each of the cases is some considered constant and 0, e E (0, 1).
D.1 Classical Testable learning
The following theorem gives the first comension-efffcicen algorithms for tolerant testable learning (see Definition 16 for various important concept classes.
Theorem D.1 (Tolerant Testable Learning via Sandwiching). For e, 0,0, E (0, 1), let X' C Rdd and (D.F) be an ( 5 reasooabll pair (Definition 4.5 for some sufficiently large universal constant C >> O. Then, there is a tester-learner for F with respect to D up to enror opt 20 + tolerance 0 and probability of failure with sample complexity i + +polyy (kdy* log(1/8)) and time complexity poly( m (kd)* log(1/6)), where opt = minjer efr(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 low-degree polynomial approximator for the unknown ground truth concept (achieving optimum error), due to the following classical result from [KMS08] (which has been used for non-tolerant testable learning in [GKK23).
Proposition D.2 (L1 regression guarantee, (KMS08)) ). Let F be a concept class over X where X C. Id and Dxy be any distribution over X x {=1} where the X-marginal of Dxy is D'. For E (0,1) and E N. suppose that for any f E F there is some polynomial p over X' of degree at most i such that Ex-D'' (1f()) p(x)]] S Then, there is an algorithu (La polynomial regression) that, upon receiving a number of i.idd samples from DD Dxy, outputs with probability at least some hypothesis h : X + {+1} with P ((xx)>>xxy [V + h(x)) I opt + Oc),, where opt minjer err(f; Dxy). The algorithm uses poly(d", (olg(" (1g 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, e + e/C, 8 - 6/C'to receive a selector g with the guarantees specified in Thcorem
2. Estimates, using unlabeled samples form Dxy, the value of P (x>D<(((x)) 0] and rejects the estimated value is greater than 20 + 2c/C.
3. Otherwise, the tester accepts and runs the algorithm of Proposition D.2 with fresh samples from the distribution Dxy that corresponds to the conditioning of Dxy to g(x) = 1, with parameters t- e/C and k < k.
22

---

Without loss of generality, we have that 28 I 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,
observe that, by condition (b)
P Px~Dlg(x) 0] S (D, D') & and hence
Px [x( 0] z 2drv (D, + &. By standard Hoeffding bound, we have that the estimated value for x (x) = 0] (obtained using unlabeled samples from the marginal DD' of Dxy) is at
most 20lv (D, D') + с
2c and the tester will, with high probability accept d (D, D') S 0.
For soundness, we want to show that, upon acceptance, for any E there is a polynomial P of degree k such that [x~Dllf(x) p(x)]] I O Then, by Proposition D.2 we have that the output h satisfies err(h; (xy) I minser err(f:Dx) + +(e/C). Moreover we would also have (h; Dxy) I Px~D [x(x) = +
[x(x) = 1]err(h; Dxy), by the law of to- Fx~D'' +
tal probability. The second term of the sum can be bounded as Px-DD [x(x) = Terrr(h; Dxy) < min P [x(x = 1] (x))))x> yV # h(x)lg(()) = 1] + O(e/C) = opt + Ó(e/C). Overall, the bound on err(h; Dxy) would then be opt 20 + e, because after acceptance, P Px-DY [g(x) = 0j is bounded, with high probability, by 20 + O(e/C).
It remains show the polynomial approximation bound. Let be some element of F and Pup+ Plow the corresponding &f sandwiching polynomials. If D is the X'-marginal of Dxy, we have the following, by applying the sandwiching property, Jensen's 's inequality and the definition of D.
(B (Bx~oll((x- Plow (x)1)² < (B (xxDDPuppxx Plow (x)))
s E ExxDDllo ExnDD(Pupp (x) Plow )x)
Ex (Pupl (x) Plow (x) 9xx]
Px [g(x) = 1]
By applying condition (a) as well as the fact that Px Px [g(x) = 1| 2 52(1) (since Px [g(x) 0),
we have
(l) Plow (x)l)² < 0(1) (Pxp((pupx)) Plow (x)) S ((2/C)
Therefore, indeed, LE (x) Plow (x)l] S e, which concludes the proof of Theorem D.I
D.2 Robust Learning
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 (DKSI8), we achieve error bound that is close to the optimal: multiplicative factor of 2 from the information theoretically optimal bound of 2n), where 1j is the noise rate (see Definition 7.17 For intersections of halfspaces, for instance, to the best of our knowledge, all prior known cimension-effician noise of rate 7 (see [KKMI& DKS18).
only incur
algorithms incurred an error of 2 ()(V)) for learning under nasty
Theorem D.3 (Learning with Nasty Noise via Sandwiching). For c. f, E (0, 1), let X C Rdd and FD. be an ( 5 m)) reasonable pair (Definition 4.5 for some sufficiently large universal G. k. k.
constant > 0. Then, there is a robust learner for F under nasty noise of rate 17 with respect to D up to error 4n + and probability of failure ė with sample complexity m + poly( (kdy log(1/8)) and time complexity poly(? Th (kdy* log(1/6)).
Proof. We follow a very similar approach as the one for Theorem D.I The main differences are two. First, instead of the outlier removal of Theorem (.1] we apply the outlier removal of Theorem E.I 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 run any tests in order obtain the desired guarantees.
Recall that in this setting, the learner receives a sample S of size N with S = Saa Sremm where Sna is an i..dd labeled sample drawn from D and labeled by some f F, |Sadvl = |Sreml S n/V where Stom is an arbitrary subset of Sna and Saav is an arbitrary sample of size Srom (i.e., the adversary removes the samples in Srem and substitutes them with adversarial samples Sndv).
The algorithm runs the outlier removal of Theorem E. on with parameters a <- 1, 6 t- E/C. 8 + 6/C and & +- i to receive a filtered set of samples Spit such that SSta' /Sauel I "Saal+eN//C.
23

---

nN + eN/C and also N Exx (p(x))² I 200 [x) for any polynomial p of degree at most Then, runs polynomial regression of degree k with coefficient bound B (given by Definition 4.5) over the set Silt and oulputs h((x) sign(f(x)) where p is the output of the polynomial regression routine (of Proposition D.2).
We aim to bound Px= # h(x)]- By uniform convergence, have bound of the form Fx~xlf*(x) # h(x)] I ((x,))~Sia y + h(x)) + c/C s ((xa)=sVV & h(x) + + c/C. We further bound the quantity P ((x.))-sly + h(x)] S P(x,))~sl + h(x), (x, 3) Sau] + Sa S
((x.))~sl + h(x); (x, v) E Shin] 2m..
We may apply Proposition D.2 to show that IP (xx.)) y # h(x), (x, v) E Smul S O(eCC) as long as the following true for some polynomial of degree at most k.
Σ (f"(x) - p(x) p(x) O(e/C)
E
Due to the sandwiching property. this is true for the sandwiching polynomial Plow for f (which exists since f E see Definition 4.5). To show this, we may follow an analogous approach as the one for Theorem D.I
E
Outlier Removal Procedure
We now give the proofs of our outlier removal theorem in the adversarial, as well as the PQ setting.
E.1
Outlier Removal in the Adversarial Setting
We present our outlier removal result in the adversarial setting:
Theorem E.1. There exists an algorithu that satisfies the following specifications for some sufficiently large absolute constant C. The algorithm A is given parameters
in (0, 1], positive integer k.
and a pair of size-N sets So and STy of points in TRd, where 2 C (Jad)* log The algorithm
A then accepts subset Succeps Spr rejects a subset Syeject S Saccept and runs in time (Nly(N).
the set Sp in TRd. of size N sampled i..dd from a k-tame probability distribution DD and let STy be generated by:
1. Sampling a size-N i..dd set Seleom from D.
2. Adversary corrupting an arbitrary subset of elements in Selean- Formally, ST Sudversarial, where Suncorupted is an adversarially chosen subset of Selean and Sudversarial is set of adversarially chosen points in RR of size N - 1Sunooruped).
S uncorrapped
Then, with probability least the algorithm A given the sets Sp and Spy will accept a set Succept C Sp satisfying the following two properties:
Degree-k spectral 200 -boundedness: For every polynomial of degree at most satisfying
I x
[[((())))
it is the case that
1
Σ pxx)²
200
N
XESu
(a, e/ vaaliityy The set Sreject C Suncorrupped has a size of at most a S + N.N.
We describe our algorithm for Theorem E.
(restating Algorithm
Input Sets Sp and Sp size N Rd parameters e, 8 in (0,
2. M < ESTIMATE-MOMENTS' Sp, k. 8/10). (See Lemma B. for further info).
24

---

3. Bo + 1d8k and Do t y d2k Nog
N No log
4. S0 filtered f SDi \ fxx maxp p MoSi (p(x)) > Bo)
5. While max, p: p' Mpsi Exest (p(x)))) 30 (1 + Do Bo).
(a) ps f- arg max p Mp51 (N Ex EXEST (f(x))
(b) Set to be the smallest value of t subject to:
{x Shitered : (p:(x))) 7} 2 a
10
P [Bo (Di(x))² > ( 20)
x~S5
(c) Si+1
nltered f Siterrdd \ fx: (p)(x))2 > TzF
(d) i f i+1
6. Output (Saccept, Sreject) = (Shinrod SD \ Siteered)
Note that the procedure -IOMANTT-MOENTS produces good spectral approximation for the degree-k moment matrix of D. Formally, Lemma B. says that the matrix M is symmetric positive- semidefinite and with probability at least 6/ [0 the case that every degree-k polynomial satisfies.
9
11
E (p(x))
Mp S
E (p(x))
(E.1)
10 X
10 xDxDD
E.1.1 Efficient implementation
We now explain how to exccute certain steps of our algorithm in polynomial time:
The quantity max p: p MrSi (p(x)) equals to the largest eigenvalue of the matrix
(M) - 1/22 ((x 0d (x (d)
T) (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 long as (M)-11/ 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: pT Mys1 (N
ExE Sinmes (p(x))² equals to the largest eigenvalue of the
matrix
(M)-112 11/2 1/2
Σ (xxd (x
(M) 11/2 1/2
XE
which be computed in polynomial time in the dimension m of the matrix. (Again, if the matrix M full-rank, then the above is still true if long as (M) is replaced by the Moore- Penrose useudo-inverse of 1/2, Also note that we again used the fact that the matrix M is symmetric.)
The polynomial pi arg max, p: p Mp51 N
inooed (p(x)))) can be computed by tak- ing the leading eigenvector of 112 N Exe (x) (M) and multi-
(1 ExEs:
plying this vector by (M) 1/2 (again, one takes the Moore-Penros pseudo-inverse if M is not full-rank).
The value of 7, can be computed in time poly(N) by considering all the candidate values of the form (p, (x))² for all elements x in St Siitered and setting T, to be the smallest candidate that satisfics the condition in the algorithm.
Note that to prove the run-time bound of poly(N) for the algorithm as whole we will need bound the total number of iterations in the main while loop, which is done in Section E.1.3
25

---

4d% Then with E.1.2 Correctness analysis
now proceed to proving first the correctness of the algorithm in Section E.1.2 Then, Section we show the required run-time bound.
In this section we show that with probability least 1 1 the algorithm satisfies the two correctness guarantees in Theorem E.I We begin by arguing that with probability at least - 8 the sets Sp and Selemn are well-behaved.
Claim 1. Let the set S be formed of N i..dd samples from k-tame distribution D, where N Z C. C( (kat)² log log&) and C is sufficiently large absolute constant. Also, let Bo c probability least 1 1- 8/10 the set satisfies the following properties for any polynomial p over IR. of degree at most k and any pair of values of in TR:
{x E S::: T2 2 (p(x))) > n1
d log N
122 2 (f(x))2 2 71) S $100
log
(1)
N
XND
N
(p'(x) (x))² 2d3
30
max x XES: o of degree ke Bx ((v (x))
(2)
N
and if the polynomial further satisfies Ex (p(x)) I then also
[(xlx)) (p(0))) x~Sp
E
E [x(x)))) 0.01
(3)
xxD
Proof. Since (p(x)) is a polynomial of degree at most 2k, the every function of the form {1==2(((x))>>+} is an AND of two 2egree-2k polynomial threshold functions. Since degree-2h 2 polynomial threshold functions have a VC dimension of at most dak + 1, we can use Fact A.5 and Fact A.6 conclude that property (I) holds with probability least 8/30.
Now, we show that property (2) is likely to be satisfied. Then there a collection fri," "Tmm of degree-k polynomials that satisfy
E (x)(s) = {0 if x
otherwise.
(Such collection necessarily exists via the Gram-Schmidt process.) We let M denote the matrix Ex-D (x (x Additionally, we consider basis {gr,--. 9m } for the nullspace of M. Now, for sampled from D have:
For a specific index j. we have (ir; = 1 and therefore by Markov's inequality we have
2d
P
(r5(x))
xnD
2n
Each øj has [xx= = 0, and therefore P. Px-D(g,(x)) =0] =
By union bound, all the events above take place for x sampled from D with probability at least 2 1 1- Via the standard Hoeffding bound, with probability at least 1 the events
1 2z
above take place for at least & + V22 log 20 fraction of elements x S. Since {r,} are orthonormal with respect to M, every degree-k polynomial p' satisfying Ex<D (p' (px))( < 1 can be decomposed as p' = Σm' auT, Eme" 3igs. where each as is in [-1, 1]. Therefore if the events above take
26

---

place for a point x, then
2
(v'(x))²=
max on on - E[-1111
Σ (x)
Begi(x) (x)
p of degree k
3 X ((' (x))
B1 m ER
2220// le
ml' Σ [xx(x)
2d (ml)²
20
(E.2)
from which Property (2) follows.
Finally, we remark that Property (3) holds with probability least 1- 6/30 due argument analogous to the proof of Lemma B.2 (where in place of f, we have the function ()))
We now argue that in each iteration there is value of T; satisfying the condition in step (5b)
Claim 2. Suppose the set Sp is such that it satisfies property (3) of claim 7 i.e. for every degree-k polynomial p satisfying Ex-xxp(x))² s 1 we have Ex-Sp [((()))² (10x))))-1(()))222)0 (xx))))BB)) S
Ex (xx())) + 0.01 and the matrix M satisfies Equation E.1 i.e. for every degree-k polynomial p we have
9 X-D
11
[p(()))
Mp
Mp
S
E [(((x))
10 x
Suppose it is the case that N ExEs
jems (px(x))² >
50
(1 + Do - Bo) (i.e. the while loop does not
terminate at step i). The there exists some J for which
10
Bo 2 (pi(x))² r] [] Ao)
[x E Sittered: (p:(x))>>>})
N
x~Sp
Proof of Claim
2 For the sake of contradiction, suppose that for every T 2 0 is the case that
10
[Bo 2 (pi(x))² T] Ao)
{x E Iimeeed : (p:(x))² 7}
S a x
(E.3)
Since every element x of Sittered satisfies (pi(x))² S Bo we have
Σ (xx(x))²=
1
{x E Sittered (pi(x))² 7} 7 dr=
N
N
9t aliaal
frB. N fxE Shhened : (pi(x))² > 7} dr. (E.4)
which combined with Equation
F.3 implies
10 (f.(x))²
Σ
A By
P X~SD
BB 2 (p((x))2 > r] :1
NV
a
T=
x St
10
Ao Bp
E [x)( ((0))))))B))) x~Sp
(E.5)
a
Additionally, since Sp is assumed to satisfy property (3) in Claim and M is assumed to satisfy Equation E.T we have
111
E [(x(x))) x~Sp
E x-D (p,(()))
0.01 < 0.01
(p:) ( (M())) + 0.01 < 100"
(E.6)
10
27

---

Combining Equation E.5 and Equation E.6
we get
10 (pi(x)))
111
Ao Bn
N
a
100
This contradicts the premise that N Exe innee (px(x))² (1 + Do Bo). finishing the proof.
Now, we proceed to argue that if all the properties in Claim and Equation E.1 hold then the algorithm A will satisty the (a, e.2)e property. In other words, show that the set Snccept O Suncorupeed has a size of at most or Sddversanial + 5N. The set Saccept O Suncorupted consists of two components:
The elements in x E Suncorrpted maxp
p of degree & <p(xx)) > Bp whose number is upper-
Mp
bounded by 2e N for the following reason. Equation E.1 implies that whenever M
holds, we also have [xxdl(p(x)){ < 10/9 and since Suncorppeed is assumed to satisfy Claim
for at least
2c/3 fraction of elements x in Suncorupted have (p(x))² < 2
which is less than Bo-
The elements in U. ((Shereed \ (iitered) n Suncorrupted). the number of which is bounded by
2a Sadversarial by the following claim.
5.
Claim 3. Suppose the sets Sp and Selcon satisfy the properties in Claim 7 Then, for each iteration i of the main loop of the algorithm, is the case that
(Sittered
(iteered Sumcorrupted
2x
(5)
[Sitered
S1+1 fiterrdd O Sndversarial
5
Proof. Since the set Suncormpted is subset of the set Solean we have
(Sitered
Si+1 fiteered n
Suncorrupted S (SShneeeed \ Shiterod n Setean
(E.7)
gd+1 Also, based on how the algorithm chooses the set littered and the parameter Tr, we have:
fittered
\
81+1
(x E Siinered (px(x))² > Tz) 2
N
N
10
log N
1
Bo 2 (pi(x))² > Ti] + 200 dak
log
X~
but since Sp and Setean satisfy Property Claim I we also have
log N N
{x E Seleam : Bo 2 (p:(x))² mi
<
P. Bo 2 (p:(x))² > no. + 200 x~
d2k
log
N
Combining the preceding two inequalities yields
10
Silnered \
gr++1 Altered
(x E Selean Bo 2 (p:(x))2 Ti
We argue that every x in (hhree \ (Sittted) S.Seeam satisfies Bo 2 (p,(x))2 > Indeed, if x belongs fitered: it also belongs fiteredd and therefore (px(x))² s (p. (M(p)) S Bo. It also has to be that (x))x) > Ti because of how gi+1 is defined inside the algorithm. Thus, we have
50
10
Saitered
s1+11 filtered
(Shitered \\
illtredd n Selean
Since Sitteeed \ Shitt is the disjoint union of (S) further conclude that
S SSteea and St
gi+1 Filtered) 0 Satverrsaial
( \
1
n
Sadversarial
10 >
(2)))
+1)
(S fiterre
S
1 (ithered)
n Selean
Finally, recalling that Suncormpted contained in Selean conclude the proposition.
28

---

Overall, the above claim concludes the proof of (a, e)-validity. Now we proceed to proving the spectral 100. -boundedness..
Claim 4. Suppose the algorithm terminates and produces a partition (Sacceps Stejes) and the matrix M satisfies Equation E.I Also, suppose that C' exceeds certain absolute constant. Then, for every potynomial p of degree at most k satisfying
E X~D
(p(x))
S
it is the case that
Σ
p(x)²
100
(E.8)
N
XESaopp
Proof. Since the matrix M satisfies Equation E.1 we have pT MM I. 11/10 and since the main while loop of the algorithm has terminated, for the hinal value êmax of it is the case that
Σ (p(x)) (eered
11 50
( [1+ 1402001/1
d2k
log N
1 log
BB
N
10 a
N
8
log we see that the inequality above yields Equation E.8 when C exceeds large enough absolute constant.
Substituting Bn
t and N 2 C
[kd)'*
E.1.3 Run-time analysis
We now prove the run-time bound of poly(N). Since each step of the algorithm takes time poly(Nd /e) = Poly(N) (see Section E.1.1). in order to obtain a required run-time bound, enough to show that the number of iterations of the main while loop at most N. We argue this via the following claim:
Claim 5. Suppose the sets SD and Seleon satisfy the properties in Claim D and the matrix M satisfies Equation E.1 Then, for every i imax, we have N Ex1 Stord (p:(x))² s
50
+ 200
(2h log N
log
Indeed, since in i-th loop of the algorithm we have
50
log N
1 g
4d
Σ (p:(x))²
1 + 2 d2k
log
N
N
X
the claim above implies that necessarily filtered Siiterett which means that ffteered < Therefore the total number of iterations max 18 upper-bounded by N. Now, we prove Claim
S Siteer 1.
Proof of Claim 5 Since every element x of gi+1 satisfies (p,(x))) s Ta and the set sr+1 is subset of Aiterrd we have
1
Σ
(px(x))²
{x E
gi+1 fitterd
(px(x))² > -]] dr
N
N
11
E fitered
(p:(x))² T} dr <
1 N
{x E Sineea (px(x))² TB dr. (E.9)
Now, recall that T, is the smallest value of r subject to:
10
log N N
{xE Sitterad (px(x))) > 7}
P X~Sp
Bo 2 (pi(x))² > 200/
d2k
log
N
29

---

Therefore, for all values of smaller than T we have
10
log N
N {x E Siterred (p)(2)) > 7}
Bo 2 (pi(x))² > 7] 200/
daR
log
x~S0
N
which combined with Equation E.9 implies
Σ
(pi(x))
N
stunal
10
log N N
1
700
[Bo 2 (pi(x))² > r] (tr)=
|
d2n
log
+
P
T=
X~SD
10
200g
d2
log N
log
1
+
R S
[p:(x))2 lo5mol)
(E.
N
8
Additionally, since So is assumed to satisfy property (3) in Claim Equation E.I we have
and M is assumed to satisfy
11
111
E x>SPp
((i(())) (
< E (px(())))) + 0.01 - x~D
(p:) MMpp + 0.01 N 100"
(E.11)
10
Combining Equation E.10 and Equation E.1l we get
1
Σ (p.(x))) - 200
daR
log N
log
Ts +
111
N
N
100
XES
Recall that fittered is a subset of SO filtered and therefore for every element x of Si+1 fitered it is the case (p.) (P.) s B, which combinded with the definition of т; implies that a Substituting this above allows us to conclude the claim.
Si+1
that (p: (x))))) B
E.2 Outlier Removal in the PQ setting
We restate Theorem
Theorem E.2. There exists an algorithm that, given sample access to an arbitrary distribution 'D' over Rd, sample access to a k-tame probability distribution over Rd, parameters c, az, 8 in (0, 1), and positive integer k, runs in time poly [kd))* log 1/ and outputs succincl poly (Skd)* log 1/
computale description of function g Rd > {0, 1) that satisfies the following properties with probability at least 1 1-8: 8:
Degree-k spectral 200 boundedness: For every polynomial p of degree at most l the case that
200 E [p(()))
E [[p(x)) < a x
x-DD
* ((a, c)-vaiiiity: we have
P [x(x 0] S a distiv (D', c
x
2'
which in particular implies that IPx 0] s (1 + disstry DD + e/2.
We also restate Algorithm ass follows:
Draw sets Sp and Sp of N= C C ((ka)) log 8 samples from distributions D and D respectively, where C is sufficiently large absolute constant.
30

---

2. Run the algorithm of Theorem E.1 on the input Spr. Set 4max to be the number of iterations of the main loop the algorithm of Theorem E.I and store the polynomials {p:}. values
{ri} J computed at each iteration of the main loop, as well as the matrix M.
3. Output the function g R + {0, 1 that does the following given an input x in R4:
(a) If maxp of degree k (p(x))² > Bo, then g(x) is defined to be O. (See Section E.1.1 p' My51
how to compute this quantity in time poly(N).)
(b) If for some i it is the case that (p:(x))² is greater than T3 then g(x) is defined to be 0.
(c) Otherwise, ((x is defined to be 1.
It is immediate from Theorem E.1 that the algorithm above runs in time poly (kd)) B log 8 with probability at least - 8. Furthermore, we also see that the function can be described using log bits and can be computed using this description on a given input x in time (Rd))*
(Kad)* R
poly
poly
log
We need the following claim bounding the number of iterations in the algorithm of Theorem E.1 proof which is deferred until the end this section. We remark that for Theorem E.I we bounded the total number of iterations by N, but in this section we will need bound that depends only on d, and and not on N.
Claim 6. If the set Sp satisfies the condition of Claim 7 then the number of iterations imnx of the main while loop in the algorithm of Theorem E satisfies imax O (kdd log( (Bgd)
We now proceed to use Claim to argue the spectral 200 -boundedness and (a, vaaliiyy As the first step, we show the following:
Observation F.3. There exists function class G with a VC dimension of at most Ofmax d log(Imax }), such that all possible values of the function g belong to G.
Proof. The function is necessarily logical AND of at most maxx +1 functions, one of which is the function indicator of ball in Fd and the other imax are logical OR-s pairs of degree-21 2k polynomial threshold functions. Combining this with Fact A.5 and Fact A.4 yields the observation.
We start with arguing the (a, (a,e/2)-validee v/a)dvalidity, well as the stronger condition of Remark 3.3 by Equation E.13): Claim 7. With probability least 8/2 over the choice of the SD and Sp', we have
(implied
IP [x()) = 0] s a distrv (D',
(E.12)
x
Furthermore, for >> cx/2 and any distribution "D" that is 1/a-smooth w.r.t D, (i.e. for any measurable set T C. _dd we have PX-D" [x E T < 1 Px~DD xx E TJ) it is the case that
P x-D l = 0] < drv ('"."''')) 2
a
D')
c
(E.13)
Proof. With probability at least 1 - 6/4 the set Sp satisfies the condition of Claim we have:
Assuming this,
fmax
[x(x)= = 0] x
IP
(x)(
2 T/ S
xND
0=0
log N
1
P S
(x)(
To] + imax
200 dek
log 8
(E.
N
1=0
where the last step used the premise that Sp satisfies the condition of Claim [ Recalling that by Obser-
vation E.3 the function g belongs to a function class with VC dimension of O (imax (1k) log(Emax ))-
and combining this with Fact A.6 we see that with probability at least 1 - 6/4
F.c
Finx d0(k) log |max log N
I [g(x) = 0] 2 x~Di
P S
[g(x) = 0] -
log
N
31

---

Recalling the definition of we see that for x in Six,, we have g(x) = when for some iteration i, the point the set {x S Siitered (p:(x))² Te). we conclude that
[g((x = =0] 2
X~
fmax
(x
Sinered
(pi(x))²
Ti)l -o
-o(( Ammax (O(k) log log(Emax/ log N
log 8
(E.15)
N
N
Now, we recall that for every iteration we have:
10
log
N {x Sitered (D:(x))² > Ti)
2
> T, + 2200/ P [x)(
da
log
x~SD
N
8
and therefore:
(()(()))
X
imax
d2h log N
{x Sittered (px(x))² n.
+ 200
log
(E.16)
10
N
N
Thus, combining Equation E.14 Equation E.15 and Equation E.16 get:
(O(k) log
P X l = 0] 5
a
[x() 0l XnDDi
P
+0 imax
log 3
(E.17)
10
N
Edistiv pl(px=
[kdd* log Overall, we see
We now the bound on imax from Claim 6 and recall that = that for sufficiently large absolute constant the error term above upper-bounded by e e/10, so
[x(x) 0] S ddistryD'' (D), X~D
P
P x~p [g(xx) _ 01
(E.
10
Rearranging the inequality above and recalling that a < 1, we conclude that Equation E. 12 holds.
Finally, we prodeed to argue Equation E.13 For >> ax/2 suppose that the distribution D is 1/0- smooth w.r.t. D, (i.e. for any measurable set I" C Id we have FX~D" |x E 2] & Px~D [x E T'). Then, from Equation E.17 we have
[g(x)
0
P lox) -1) X
=0)
+0
imax
(o(k) log N
log
(E.
10
N
Sa SoPP-Di PPx-D"(((x)== a-smoothnnss
ddistyy(D" PA [0(
Sc/10
for constant C sulliciently large.
Rearranging the inequality above and recalling that < 1 and o a/2, we conclude that Equation holds.
Now, we argue the spectral 200 -boundedness.. Recall that with probability at least 8/20 the matrix M satisfies Equation E. which we will henceforth assume. Also recall that Claim that for every polynomial p of degree at most & satisfying (x<<((((())
&
< 1, the set Saccept given by the algorithm Theorem satisfics 1 ExeSumn p(x)2 2 < 100 By inspecting the definition of the
function g, we see that for x in STy we have g(x) if an only if x is in Succepe Therefore,
100
max p degree S.E. Exwr [
E X [x(x)p(x)
(E.20)
32

---

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. approximately holds when one replaces the expectation w.r.t Spr with the expectation w.r.t. the distribution D' To show this, we first recall that via Observation F.3 the function 9 belongs to function class G with a VC dimension of most (Fmaax d² (og((max)) )). We also see that g(x) = 0 for all x satisfying
pi Ex-r((((x)) (p(x))²
max
10Bo, because the matrix M satisfies Equation E.1 and therefore Txx ((x(((((())))) Σ and (p(x))² > 10 then also (v (.0.)) (v0.9p))
< and v0.9p(x) > Ba. which implies that B.2 that with probability at least 8/20 such
g(x) by the definition of g. We show in Lemma function classes satisfy
sup gE9
Σ
(Fxx)((()))]]
[fxx)(((x))
$
N
X
Xr-Spr
p of degree Ex
(p(x)) o
((VBo
Bu /mxx d log( da log N 1/1
N log !)
1
< 1 a² (E.21)
where the penultimate inequality above achieved by substituting the bound Amax O (kd log Byd) from Claim into the expression above, substituting Bo 4
recalling that
N C (hd)) log and taking C' to be sufficiently large absolute constant. Combining Equa-
tion E.2 with Equation E.20 we conclude that with probability at least 1 - 6/20 it is the case that
101
E
(((()))(g(x)) 1 a
p degree
x
Ex-D [((())
Overall, with probability least 1-8 the function g satisfies spectral 200 -bbudddddsssss, (a, e)-validity, as well as the required run-time bound.
Finally, come back to Claim 6 proving which concludes this section.
Proof of Claim Let i be an iteration such that < mmax- Since the while loop did terminate on step i, we have
100
Σ (pi(x))²
(E.22)
XESS
At the same time, Claim 1aamm5mmmp implies that
20
(p:(x))²
(E.23)
N XESÉ 11
Let m < d denote the dimension of the vector space of degree-k polynomials. For values of i between and imax and for values of j between and m.let the collection of polynomials {Rt} and non-negative real values {사j} be defined as
RC
arg max R degree & s.t VJ' L:j: (R))) J M.==0
Σ [(R(x))]]
= N
Σ [(R(()))
(E.24)
N
XE Stiree
SE S Hitsel
MRS1
33

---

In particular we have = Ri. We will use the quantity (i = :==]=
Aj as potential function, for
which we have:
P/: - Pi+1=
=
Σ (R)
N Σ (Ri(
Σ
(Di(x))²=
=
N
N
xE SESuanaa Sallo
x Sharea 1- Shhrred
x Shared 1-9
20
(pi(x))²
(x:(x))
(E.25)
Ck
X
Where in the end we substituted Equation
E.23
Since Xf equals to NV2 Exes (x)) and has
a value of at least 100/a by Equation E.22 the inequality above allows us to conclude
Fi+ Σ
-
0.8
<
Σ
0.8
Σ
2
0.9
si
(E.26)
m
d
j=1
We now combine the inequality above with the following two observations:
We have
100
Pinax
> 1,
a
because the algorithm did not terminate the (imax - 1) iteration, and therefore Equation E,22 holds.
We have
Σ Σ (R)( < Bom,
P0
N
j=1
$0 Eitered
where the last inequality follows from the fact that every element in SO
fitered satisfies
(p(x))² < By-
max p degres p Mp51
Overall, the two bounds above, together with Equation E.26 allow us to conclude that: mmx I (d log( BBm) O (kd* log(B))))
where the last step follows by substituting the definitions of m and e.
"Speaking precisely, there might be multiple choices for the collection of the polynomials (R,) ). In this still, choose these polynomials without loss of generality in such way that ps R).
34

---

NeurIPS Paper Checklist
1. Claims
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 proof's 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 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We include paragraph on the limitations of our work in the end of the main
paper.
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-specfiiaatinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
35

---

Answer: [Yes]
Justification: Our theorem statements clearly state the assumptions and we provide full proofs in the main paper appendix. Wherever possible, provide proof sketches in the main paper.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
36

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our paper does not have any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /oti:///gu.deeeoooouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
37

---

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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 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 eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not have any experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We read the code of ethics its entirety and strongly helieve 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 deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration 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 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.
38

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data and models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: Our paper does not use any existing code, data, models.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
39

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowd-sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "8Tt6XmaTsI", "reviewer": "Reviewer_wKf2", "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. \n\nThe 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. \n\nThis 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.\n\nUtilizing 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.", "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.\n\n2. 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": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This paper offers a solution to well-known theoretical problem that achieves the best known bounds. I particularly like that their algorithms are computationally efficient (in addition to enjoying the typical performance guarantees). Their technical idea for outlier detection (which forms the core of the paper) is relatively well explained and seems to me an innovative way to approach outlier detection.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We wish to thank the anonymous reviewer for their constructive feedback and suggestions.\n\n**Gaussian assumption:** The reviewer is correct that the outlier removal procedure works under weaker assumptions than Gaussianity. In particular, it will work for any tame distribution (see lines 155–158 for a definition). However,  in order to obtain our PQ learning results, we also make use of the existence of low degree $\\mathcal{L}_2$-sandwiching approximators. The existence of such approximators has been proven in prior work for the Gaussian distribution as well as for the uniform distribution over the hypercube. Nonetheless, we believe that simple classes like halfspaces and halfspace intersections admit low-degree sandwiching approximators with respect to other distributions as well and establishing appropriate bounds is an interesting direction for future work. The important relevant properties are, in general, both concentration and the anti-concentration of the Gaussian distribution, which are, for example, also satisfied by strongly log-concave distributions.\n\n**Reasonable pairs:** Definition 4.5 indeed consists of 3 properties. The first one is 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]. The second one is the tameness condition, which is important for the outlier removal procedure and was introduced in the work of [DKS18] for similar purposes. The third one ensures generalization for polynomial regression. We will add an appropriate discussion in future revisions.\n\n*[DKS18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061–1073, 2018.*\n\n*[KSV24b] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. 37th Annual Conference on Learning Theory, 2024.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jtnJsVWFw8", "reviewer": "Reviewer_JMSW", "summary": "This paper studies two fundamental learning setups, namely PQ learning and TDS learning (Testable Learning with distribution shift), both motivated by covariate shift. \n\nIn 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.\n\nIn 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.\n\nThe 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.", "questions": "In Definition 4.5, should it be \"from some distribution $\\mathcal D^{\\text{train}}$\" instead of \"from some distribution $\\mathcal D$\"?", "limitations": "Yes, they have.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The application of spectral outlier removal in the context of distribution shift is natural and turns out to b quite powerful. The most surprising part is that the procedure works even when the TV distance between the test and the training distributions is more than $1/2$. A naive application of spectral outlier removal will not work in this case as the filter may end up removing all points from the dataset (since the standard guarantee only says that the filter remove more \"bad\" points than \"good\" points). The analysis of this work circumvents the issue, and characterizes a tradeoff between the rejection rate $\\alpha$ and the final bound on the $L_2$ norm of polynomials. This makes PQ learning possible even when the TV distance between $\\mathcal D^{\\text{train}}$ and $\\mathcal D^{\\text{test}}$ approaches $1$ (albeit with a cost of having larger learning error in the end).", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and for appreciating our work. In Definition 4.5, the distribution $\\mathcal{D}$ represents some distribution over the features, which is unlabeled. We instead typically use $\\mathcal{D}^{\\mathrm{train}}$ to denote the labeled training distribution (see lines 136–137 and also Definition 4.1).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iRzDQpJHgp", "reviewer": "Reviewer_tKBR", "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.\n\nThis 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.", "questions": "My main question is about Appendix B, which I believe is crucial for the proof of all technical theorems.\nI find this section not carefully written with inconsistent notation and typos, which makes it hard to follow the arguments. \n\nNext, I focus on the parts which were not merely typos:\n1. 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?\n2. 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$.\n3. 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)$\n4. 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?\n\nI will consider changing my score when authors address these questions.", "limitations": "There are no ethical limitations in this work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. Paper provides novel results in the PQ learning and TDS learning. Solving these learning models is important, since in practice algorithms need to perform well under covariate shifts.\n2. Core algorithm of the paper is versatile, as the authors show how to apply it to multiple other learning settings (e.g. learning with nasty noise).\n3. For TDS learning, prior works rejected distribution with a very small distributional shift. This work provides an algorithm which gives non-trivial results even if the distance between distributions is larger.\n4. This work suggests a novel technique to bound number of iterations of their algorithm through the use of potential function.\n5. The main text of the paper is well-written.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback. We will carefully go through our proofs in the appendix to fix all typos for future revisions. Regarding the specific questions of the reviewer:\n\n**Question 1.** You are correct that Equation (B.2) should have the square of Frobenius norm on the left side. Thank you for pointing out that typo. This will in turn slightly change the bound of the equation between lines 677 and 678, where we will instead use the fact that $\\mathbb{E}_{S_i}[||I-M^{-1/2}M_iM^{-1/2}||_2] \\le \\sqrt{ \\mathbb{E} _{S_i}[||I-M^{-1/2}M_iM^{-1/2}||_F^2]} \\le \\frac{(dk)^{O(k)}}{N^{1/4}}$. The statement of line 678 is still true for some sufficiently large constant $C$.\n\nWe now give the omitted details for Equation (B.2). We start with the second equality. We have $\\mathbb{E}_ {x\\sim D}[ r_{j}(x) r_{j'}(x) ] = e_{j}^{T} e_{j'}$, which is zero if $j=j’$ and 1 otherwise (by the equation starting directly after line 669). We also have $e_j^T M^{-1/2}=r_j^T$ and $M^{-1/2} e_{j’}= r_{j’}$ and therefore $e_j^T M^{-1/2} M_i M^{-1/2} e_{j’}= r_j^T M_i  r_{j’}$ which equals to $\\mathbb{E}_ {x \\sim S_i}[r_{j}(x) r_{j'}(x)]$. \n\nNow we explain the third equality, after adding $\\mathbb{E}_ {S_i}$ (the expectation over the random selection of the elements of $S_i$) in the beginning of the second line, which is missing due to a typo. Since the set $S_i$ is composed from i.i.d. samples from $D$, the quantity $\\mathbb{E}_ {S_i}(\\mathbb{E}_ {x \\sim D}[r_{j}(x) r_{j'}(x)]-\\mathbb{E}_ {x \\sim S_i}[r_{j}(x) r_{j'}(x)])^2$ equals to the variance of the random variable $\\mathbb{E}_ {x \\sim S_i}[r_{j}(x) r_{j'}(x)] = \\frac{1}{|S_i|}\\sum_{x\\in S_i}r_{j}(x) r_{j'}(x)$ (the randomness is over the choice of $S_i$). Since the choice of elements of $S_i$ is i.i.d. from $D$, we can use the fact that the variance of a sum of i.i.d. variables  equals to the sum of their variances. Overall, we have that the variance of $\\mathbb{E}_ {x \\sim S_i}[r_{j}(x) r_{j'}(x)]$ equals to $\\frac{1}{|S_i|}\\mathrm{Var}_ {x \\sim D}[r_{j}(x) r_{j'}(x)]$. Finally, we substitute $|S_i|=\\sqrt{N}$.\n\n**Question 2.** Even though the polynomial $r_j r_{j’}$ is of degree $2k$, it has the extra property of being a product of two degree-k polynomials. If $(r_j(x) r_{j’}(x))^2>B^2$ it has to either be the case that $(r_j(x))^2>B$ or $(r_{j’}(x))^2>B$. The probability of either of those events can be bounded by referring to the definition of $k$-tameness. \n\n**Question 3.** We confirm that the additive term $\\Delta$ is indeed not necessary in the second line of Equation (B.4). We will correct this typo in the revision. We however note that the third line of Equation (B.4) should still have an additive term of $2\\Delta$ (replacing the current value $\\Delta$ with the value $2\\Delta$ entails changing $\\Delta$ to $\\Delta/2$ in the line after line 701 and does not change the conclusion on line 702). The third line of Equation (B.4) follows from the second line of Equation (B.4) (with $\\Delta$ removed) as follows. By triangle inequality, the second line of Equation (B.4) can be upper-bounded by a sum of terms if we let $u_j$ denote $\\mathbb{E}_ {x \\sim S} [f(x) \\mathbf{1}_ {j\\Delta \\leq (p(x))^2 < (j+1)\\Delta } ]$ and $v_j$ denote $\\mathbb{E}_ {x \\sim D’} [f(x) \\mathbf{1}_ {j\\Delta \\leq (p(x))^2 < (j+1)\\Delta } ]$, then by the triangle inequality we see that the second line of Equation (B.4) is at most $\\sum_{j=0}^{B/\\Delta}( (j \\Delta) |u_j - v_j| + \\Delta u_j + \\Delta v_j)$. We also observe that $j \\Delta \\leq B$, and $\\sum_{j=0}^{B/\\Delta} u_j \\leq 1$ and $\\sum_{j=0}^{B/\\Delta} v_j \\leq 1$ which bounds the whole expression by $2\\Delta+B\\sum_{j=0}^{B/\\Delta}( |u_j - v_j|).$\n\n**Question 4.** Thank you for pointing this out, we added a short claim that proves that there indeed exists a value of $\\tau_i$ satisfying the condition, assuming certain high-probability events take place. The proof is based on a simple averaging argument. In particular, $\\tau_i$ is defined as the threshold such that the current set $S_i ^{\\text{filtered}}$ contains unreasonably many points $x$ such that $(p_i(x))^2 >\\tau_i$. If such a threshold $\\tau_i$ did not exist, then $S_i ^{\\text{filtered}}$ would not satisfy line 919 (which is a contradiction).\n\nMore formally, for the sake of contradiction, suppose that for every $\\tau \\ge 0$ it is the case that\n$$\n\\frac{1}{N} | \\{ x \\in S_i^ {\\text{filtered}} : (p_ i(x))^2 > \\tau \\} | \\le \\frac{10}{\\alpha} ( \\mathbb{P}_ {x \\sim S_D} [B_0 \\ge (p_ i(x))^2 > \\tau] + \\Delta_0 ). \\tag{1}\n$$\nSince every element $x$ of $S_i^ {\\text{filtered}}$ satisfies $(p_i(x))^2 \\le B_0$ we have\n$$\n\\frac{1}{N} \\sum_{x \\in S_i^{\\text{filtered}}} (p_i(x))^2 = \\int_{\\tau = 0}^{B_0} \\frac{1}{N} | \\{ x \\in S_i^{\\text{filtered}} : (p_i(x))^2 > \\tau \\} | d\\tau. \\tag{2}\n$$\nCombining Equations (1) and (2) gives\n$$\n\\frac{1}{N} \\sum_{x \\in S_i^ {\\text{filtered}}} (p_i(x))^2 \\le \\frac{10}{\\alpha} \\left( \\Delta_0 B_0 + \\int_{0}^{B_0} \\mathbb{P}_ {x \\sim S_D} [B_0 \\ge (p_i(x))^2 > \\tau] d\\tau \\right),\n$$\nwhich in turn is bounded by $\\frac{10}{\\alpha} ( \\Delta_0 B_0 + \\mathbb{E}_ {x \\sim S_D} [ (p_i(x))^2 \\cdot 1_{x \\le B_0} ] )$. Additionally, since $S_D$ is assumed to satisfy property (3) in Claim 1, and $\\hat{M}$ is assumed to satisfy Equation (E.1) (see line 929), we have\n$\\mathbb{E}_ {x \\sim S_D} \\left[ (p_i(x))^2 \\cdot 1_ {(p_i(x))^2 \\le B_0} \\right] \\le 2\\mathbb{E}_ {x \\sim D}[(p_i(x))^2] \\le \\frac{11}{5} (p_i)^T \\hat{M} (p_i)  \\le \\frac{11}{5} \\le 5$. Overall, we have bounded $\\frac{1}{N} \\sum_{x \\in S_i^ {\\text{filtered}}} (p_i(x))^2$ by $\\frac{10}{\\alpha} \\left( \\Delta_0 B_0 + 5 \\right)$, which contradicts the premise that $\\frac{1}{N} \\sum_{x \\in S_i^ {\\text{filtered}}} (p_i(x))^2 > \\frac{50}{\\alpha} (1 + \\Delta_0 B_0)$, finishing the proof.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LNbEPZPbKV", "reviewer": "Reviewer_wPZr", "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.\n\nThe 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).\nSecond, 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).\n\nThe 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).", "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.\n\n- 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": "Adequately addressed", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper achieves strong and novel results in an area which I believe to be of interest to the Neurips community. It falls in a line of research focussing on relaxing (or testing) distributional assumptions in algorithmic learning theory, which has recently received a lot of interest. In particular, I like that the paper goes beyond the 'moment-matching' approach of earlier works.\n\n- I find the combination of ideas from [KSV24b] and outlier removal to obtain the main results very insightful.\n\n- The paper is very well written: the key technical ideas are exposed clearly, and it is easy even for the non-expert to graps the main concepts. Furthermore, the results and some of their consequences are positioned clearly in the existing literature. Lastly, the technical background (on learning models, previous algorithms etc.) is well presented.\n\n- The work leaves open some directions for future research, and I think it is likely that its ideas will be applied to obtain future results in this area.", "weaknesses": "- 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).\n\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and appreciation of our work.\n\n- Lines 62-63: We will clarify this point, thank you for pointing out.\n\n- Lines 111-117: Our work is indeed the first to consider distribution-specific PQ-learning at all. Prior work involved reductions to other learning primitives like agnostic or reliable agnostic learning, but the reductions did not preserve the marginal distributions and, hence, the resulting algorithms were inherently distribution-free.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RsfmXuSAa5", "reviewer": "Reviewer_QNbu", "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.", "questions": "See above.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "While I'm not an expert in PAC learning using polynomial regression, this paper appears to provide some interesting technical results. The outlier removal algorithm introduced in Theorem 3.1 seems to be an interesting technical primitive for handling outliers in low-degree polynomial regressions. Although the settings considered in this paper are fairly restrictive, the results seem to provide a valuable step toward understanding learning with abstention in covariate shift.", "weaknesses": "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.\n\nI outline the following specific comments:\n\n1. 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?\n\n2. 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.\n\n3. 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?\n\n4. Is there a specific reason why Theorem 3.1 is stated for the second moment? Is it due to Lemma B.1?\n\nGiven these reasons, although I believe this paper has some interesting technical contributions, it would require substantial revision to be suitable for publication at NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort.\n\n**Question 1.** We note that, while we provide most of the technical details of our proofs in the appendix, we do provide a high-level explanation of our results in the main part, including Theorem 3.1 (see lines 189–223). In fact, the comparison with [DKS18] partly explains the technical differences between Theorem 3.1 and results on outlier removal from prior work. Given the reviewer’s feedback, however, we will add some further technical details in the main paper.\n\n**Question 2.** We respectfully disagree with the reviewer’s comment that our statements lack precision. Note that the parameter $\\lambda$ is defined in the preliminaries (lines 146–148). Moreover, in Lemma B.2, the premise regarding $f$ is that $f(x) = 0$ for any $x$ that satisfies some property (the one described in line 693, i.e., that $p(x)^2$ is more than $B$ for some polynomial $p$ with low second moment) and not all $x$. We will clarify these points in the main paper and we are happy to address any further specific concerns that the reviewer may have.\n\n**Question 3.** The algorithms we propose are efficient in the dimension of the input, which is a standard goal in learning theory (see, for example, the classical work of [KKMS08]). In the presence of label noise, the exponential dependence on the parameter $\\epsilon$ cannot be removed, even if one assumes that there is no distribution shift (see [DKPZ21]). Additionally, when there is no label noise, the algorithm of Theorem 4.3 for PQ learning of halfspaces is quasi-polynomial in all parameters and is optimal in the SQ framework (see [KSV24a]).\n\n**Question 4.** Theorem 3.1 is stated for the second moment for two reasons. First, using the second moment enables the use of spectral methods for the outlier removal procedure and is a common approach for prior results on outlier removal. Second, it is sufficient for our purposes, since the difference of the upper and lower $\\mathcal{L}_2$ sandwiching approximators is itself a polynomial with low second moment under the target distribution. Subsequently, we can use the outlier removal procedure to find a subset of the input set over which the bound on the squared difference of the sandwiching approximators is preserved.\n\n*[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777–1805, 2008.*\n\n*[DKPZ21] Diakonikolas, Ilias, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. \"The optimality of polynomial regression for agnostic learning under gaussian marginals in the SQ model.\" In Conference on Learning Theory, pp. 1552-1584. PMLR, 2021.*\n\n*[KSV24a] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning intersections of halfspaces with distribution shift: Improved algorithms and sq lower bounds. 37th Annual Conference on Learning Theory, COLT, 2024.*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (spotlight)