The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
Authors: Adam Klivans
Konstantinos Stavropoulos
Kevin Tian
Arsen Vasilyan
Venue: NeurIPS 2025 spotlight ()
Keywords: robust learning
malicious noise
contamination
outlier removal
Primary area: theory
TL;DR: We provide a wide range of nearly optimal guarantees for several fundamental problems in robust supervised learning based on a single iterative polynomial filtering algorithm.

Abstract: Inspired by recent work on learning with distribution shift, we give a
general outlier removal algorithm called *iterative polynomial
filtering* and show a number of striking applications for supervised
learning with contamination:
(1) We show that any function class that can be approximated by
low-degree polynomials with respect to a hypercontractive distribution
can be efficiently learned under bounded contamination (also
known as *nasty noise*).  This is a surprising resolution to a
longstanding gap between the complexity of agnostic learning and
learning with contamination, as it was widely believed that low-degree
approximators only implied tolerance to label noise.
(2) For any function class that admits the (stronger) notion of
sandwiching approximators, we obtain near-optimal learning guarantees
even with respect to heavy additive contamination, where far more than
$1/2$ of the training set may be added adversarially. Prior
related work held only for regression and in a list-decodable setting.
(3) We obtain the first efficient algorithms for tolerant testable
learning of functions of halfspaces with respect to any fixed
log-concave distribution.  Even the non-tolerant case for a single
halfspace in this setting had remained open.
These results significantly advance our understanding of efficient
supervised learning under contamination, a setting that has been much
less studied than its unsupervised counterpart.

The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
Adam R. Klivans"
Konstantinos Stavropoulos UT Austin
Kevin Tian UT Austin
Arsen Vasilyan UT Austin
UT Austin
Abstract
Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial filtering and show number striking applications for supervised learning with contamination: (1) We show that any function class that be approximated by low-degree polynomials with respect to a hypercontractive distribution can be efficiently learned under bounded contamination (also known nasty noise). This is surprising resolution a longstanding gap between the complexity of agnostic learning and learning was widely believed that low-degree approximators only
with contamination, implied tolerance to label noise. (2) For any function class that admits the (stronger) notion of sandwiching approximators, even with respect to heavy additive contamination, where far more than 1/2 of the training set may be added adversarially. Prior related work held only for regression and in a list-deoodable setting. (3) We obtain the first efficient algorithms for tolerant testable learning of functions of halfspaces with respect to any fixed log- concave distribution. Even the non-tolerant case for a single halfspace in this setting had remained open. These results significantly advance our understanding of efficient supervised learning under contamination, setting that has been much less studied than unsupervised counterpart.
obtain near-optimal learning guarantees
Introduction
Dataset curation fundamental part of the training pipeline of modern machine learning models and often appears to be the bottleneck in obtaining models with improved performance [SKL17, LRB 21, BGMMS21, GIF++33 One way to theoretically model this problem is assume that the learner has access to potentially heavily- contymmintt dataset and the goal is to learn model that performs well on some clean underlying target distribution. While there has been tremendous recent progress for unsupervised learning with contamination [HM13, CSV17, 17, KS17a, KS17b, BDLS17, DKSI 18b, HI.18, CDG199 RY20, BDH+20, CMY20, BK21, IK22, 7S22, DKK+ +2a, DHPT24], relatively little is known for supervised learning with contamination, especially for binary classification.
Many efficient algorithms with strong error guarantees have been developed for agnostic learning, special case of contamination where only the labels are adversarially corrupted [KKMS08, KOS08, BOWIO, ABL17, DKSI8t 8a, DKTZ20b, DKK OKK+)2b), Most of these guarantees, however, had seemed difficult to extend to the more challenging setting of contamination, where both labels and covariates can be adversarially corrupted. In this paper-buildin on recent work on robust learning and learning with distribution shift [DKS Sa, GSSVG V24, KSV24c]-wy ww give a general iterative polynomial filtering procedure that greatly expands the set of known positive results for learning binary classifiers from
'klivans&ce, utexas. edu. 'kstavrop@utexas. edu. 'kjtianccs. utexas edu. larsenvaiilyangmaiil. com.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

contaminated datasets (see Tables 1, 2. and 4). In particular, we obtain the surprising conclusion that all known near-optimal error guarantees for agnostic learning (that can be achieved efficiently) can indeed be extended to the setting of contamination.
Learning with Bounded Contamination. The earliest works that explored learnability beyond label noise date back more than 30 years ago [Va185, KL93J. Since then, the problem has been studied in the context of learning with malicious [Va185, KL93, KLS09, She25] and nasty [BEK02, ABL17, DKS GSSV24, KSV24c] noise. Here we focus on the harshest among these noise models, nasty noise, which we call bounded contamination (defined below). in line with recent work in robust learning (see [DK23, KSV24cJ). In this model, the adversary is allowed to replace an arbitrarily chosen but bounded fraction of a clean dataset with arbitrary labeled datapoints.
Definition 1.1 (Bounded Contamination (BC)). Let 'D be some distribution over X. n (0. 1) and f: X + {+1}. We say that a set of samples Supp is generated by (D,f) with bounded contamination rate n if is generated as follows for some M 2 1.a
1. First, set Senn of M i..dd. examples of the form (x, fx)), where x D, is drawn.
2. Then, adversary receives Sehn. chooses at most nM labeled examples in Sein and substitutes them with an equal number of arbitrary labeled examples Sadv to form Simp-
The learner receives a dataset with bounded contamination, and the goal is to output classifier that enjoys information- taatttoiointh optimal error guarantees on the clean underlying target distribution. Achieving an error better than twice the contamination rate is, in general, impossible [BEK02].
Definition 1.2 (BC-Learning). An algorithm A is BC-leamer for C S {X' - {+1}} if on input (c, 6, Smm)), where e, (0,1), and Supp is generated by (D. with bounded contamination n for some distribution D over X, some f C and E [0, 1), the algorithm A outputs some hypothesis h: X + [ such that with probability at least 1 over the clean examples in Simps and the randomness of A:
P [f() + Mxxx S +
X
The sample complexity of A is the minimum number of examples required to achieve the above guarantee. Moreover, distribution-spe speciffcc BC-learner with respect some distribution D' over X is a BC-learner that is guaranteed to work only when D = D*
Most of the computationally efficient algorithms for learning with bounded contamination provide suboptimal error guarantees and apply only to special concept classes [KLS09, ABL17, DKS I 8a]. Nevertheless, recent line of works inspired by advances in learning with distribution shift [GKKM20, KSV24b, GSSV24) has given efficient algorithms with near-optimal guarantees for concept classes that admit sandwiching polynomial approximators [GSSV24, KSV24c]. In contrast, for agnostic learning (i.e., adversarial label noise), it is well known that the weaker notion of (non-sandwiching) approximating polynomials is sufficient [KKMS08], and there is strong evidence of its necessity 14, DKPZ21J.
Therefore, the following question naturally arises: does the existence of low-degree approximating polynomials imply efficient learnability even with respect to bounded contamination?
In Theorem 4.2, we give positive answer to this question, thereby resolving a longstanding gap between the complexity of learning with bounded contamination and with adversarial label noise. This is particularly important as it implies exponential improvements for BC-learning of fundamental concept classes like intersections of halfspaces, monotone functions, and convex sets (see Table 2).
Learning with Heavy Contamination. Perhaps surprisingly, to our knowledge, binary classification beyond bounded contamination is completely unexplored. In contrast, there is substantial body of work for learning from datasets where only a small proportion comes from the clean distribution in unsupervised settings [CSV17. DKS RY20, BK21, IK22, ZS22, DHPT24] and linear regression [RY20, KKK19, DHPT24]. These works typically provide list-decodable guarantees (i.c.. multiple candidate hypotheses) or require access a small trusted clean sample. Here, we define a new model for learning binary classifiers with heavy additive contamination that outputs a single hypothesis with a strong error guarantee under the clean distribution. Our model is inspired by recent work on regression (a basic supervised learning task) in additive semi-randon models [JLM+23 23, KLL* KLL+23].
We use the notation S to denote labeled dataset and distinguish it from its unlabeled counterpart S.

---

Definition 1.3 (Heavily Contaminated (HC) Datasets). Let 'D be some distribution over X' x { (we think of as the clean or uncorrupted distribution). We say that a set of samples Smp is generated by D with Q-heavy contamination if it is generated as follows for some m S M with M/m S Q
1. First, a set Senn of m i.i.d. labeled examples from D is drawn.
2. Then, an adversary receives Seln and adds M- - m arbitrary labeled examples to form Smp-
The heavy contamination model only allows the adversan to add points, since removing an arbitrary fraction of the clean samples would correspond to learning with truncation [DGTZ18, DGTZ19, KZZ24], which is beyond the scope of this work (see also Remark G.2). Another difference between Definition 1.1 and Definition 1.3 that in the HC model, clean labels need not be realized by some function in the given concept class. We instead consider the following quantity
opt
= min FEC [Smpl
Σ
1 f(x)),
(1.1)
(x.))ESmmp
which is the minimum error achievable by the concept class C the whole (contaminated) input dataset Simp (including the misclassification errors on the clean samples). The error benchmark we consider is a rescaling of opttotal, proportional to the heavy contamination ratio Q.
Definition 1.4 (HC-Learning). An algorithm A is an HC-learner for C S {t + } if on imput (e, 8, Q, Sip)), where e, E (0, 1), Q Z and Simp is a Q-heavily contaminated set of labeled examples generated by distribution 'D (as described in Definition 1.3), the algorithm A oulputs some hypothesis h X + {+13 such that with probability at least 1 - 5 over the clean examples in Simp. and the randomness A:
P (x.9)~D h(x)] S SQ- optiotal c,, where pota is given by Eq. (1.1)
The (clean) sample complexity of is the minimum number of clean examples Sup needs to contain in order to achieve the above guarantee. Moreover, a distribution-speciie HC-learner with respect to D* an HC-learner that is guaranteed to work only when the marginal of DD on X is D
We show that the dependence on NQQ opta) is, in fact, necessary, even if the clean labels are realized by the learned class C. The quantity Q -optooal equals the number of errors |Simpl opt of the optimal classifier the input set Simp divided by the size of the clean dataset. Our lower bound essentially shows the existence of a contamination strategy that forces any HC learner to pay for all the mistakes of the optimal classifier on Simp: even if these
not made the clean dataset. let
This is possible the learner does not know which subset of Simp is clean. In the following, opt == minfec IP, (x.))>DlV # f(x) be the optimum error under the clean distribution.
Proposition 1.5 (Informal, see Propositions B.2 and B.3). Let C be any non-trivial class. Then, no HC-learner for C can guarantee error better than 2 opt even when the clean distribution is realizable, i.e., opt.lean O. Moreover, if X oc, then no HC-learner for Call {=1]** can guarantee error better than Q opt even when opt,lean = 0.
Naturally, one might wonder whether the existence of approximating polynomials is sufficient for HC- learning. In Theorem E.2 we give a negative answer to this question, by providing a lower bound on the sample complexity of HC-learning of monotone functions, which admits low-degree approximators. A recent line of works has used the stronger notion of sandwiching approximators to provide efficient algorithms for various challenging learning tasks [GKK23, KSV24b, GSSV24, CKK 24b, KSS KSV24c). Here, we expand on this paradigm and show that the existence of low-degree sandwiching polynomials implies efficient HC-learning well (Theorem 4.4).
1.1 Our Results
Learning from Contaminated Datasets. In Table we present an overview of the upper bounds we obtain applications of our main theorems on learning with contamination (Theorems 4.2 and 4.4). For comparison, we also provide the corresponding results on learning with label noise from prior work. For the case of bounded contamination, and for constant error and confidence parameters (e, 8), our results match the best known bounds for learning with label noise, since both cases, the existence of lew-ee polynomial approximators is sufficient. See Tables 2 and for further details.
3

---

Adversarial Label Noise (Prior work)
Bounded Contamin. (This work)
2- HeHav
Target Marginal
Concept Class
Contamin.
(This work)
Intersections of I Halfspaces
(O Ia)
klogk)))
( k)
do(k))
Depth-f, Size-d Boolean Circuits
Unif(#1}"
dO
d'(logd)
dOoog
Degree-k PTFs
Aa)
do(A2)
do(k2)
dox(1)
Monotone
Unif{#13d
20(va)
20(va)
2
Functions
Table 1: Bounds on the time complexity of learning under different noise models up to excess error é 0.1 and failure probability 6 = 0.01. Except for the lower bound for monotone functions under heavy contamination, all remaining entries correspond to upper bounds. See Appendix D for more details on the complexity of learning with adversarial label noise.
All of our results work in the distribution-speciff setting. Distributional assumptions are unavoidable, as there is strong evidence that distribution-free learning of even the simplest classes (c.g.. linear classifiers) in the presence of noise computationally hard [FGKP06, Danl6]. Although we present our results for specific standard target marginal distributions, our results hold for any hypercontractive (Definition 3.1) marginal D* that can be sampled efficiently, as long as the degree of approxima- tion (resp. sandwiching for HC-learning) of the learned class is low under D Hypercontractive distributions are an extremely wide class of probability distributions, which includes Gaussians, all log-concave distributions over Rd. as well product distributions over {+1 )d. See Appendix C for an overview of relevant results in approximation theory.
On the lower bound side, we show that learning monotone functions with heavy contamination requires exponentially many samples, thereby separating bounded and heavy contamination. For more thorough discussion on lower bounds for learning with contamination, see Appendix E,6
Testable Learning. A recent line of works in learning theory has focused providing learning algorithms that can verify their distributional assumptions [RV23, GKK23, GKSV23, O3,+23, GKSV24, STW24, GSSV24). These algorithms with certified optimal performance, or detect a violation of their target distributional assumptions and reject. Here, we provide improved results for tolerant version of this problem where the algorithm has to accept even if the input distribution is close to the target distribution. Tolerant testable learning was first studied in [GSSV24] (see Definition H.I).
allowed either accept and output classifier
In Theorem H.2, we show that the existence of low-degree sandwiching polynomials implies efficient tolerant testable learning. Previously, [GSSV24] required the existence of low-degree Cy-sandwiching polynomials, which is a stronger assumption. Moreover, all of the previous results in testable learning- even the non-tolerant variants-requin required that the sandwiching polynomials have bounded coefficients. Here, we do not impose such a requirement and obtain the first testable learning results for functions of halfspaces with respect any fixed log-concave distribution. All prior work either gave worse error guarantees [GKSV24, GKSV23), or required target marginals with strictly sub-exponential tails [GKK23]. See Appendix H for more details.
1.2 Our Techniques
Iterative Polynomial Filtering. All of our results use the same iterative polynomial filtering algorithm of Theorem 3.2 with appropriate hyperparameter choices. The algorithm receives a set Sma of data points and filters it, outputting a subset San of Smap that satisfies the following two conditions. First, any low-degree polynomial p whose absolute expectation E| p(x)] over the pre-specified target
'We note that although learning with bounded contamination is clearly more challenging than learning with adversarial label noise, many of the known lower bounds for agnostic learning do not transfer directly to BC- formalized in Definition 1.1 for technical reasons. See Appendix E for way to eircumvent this.

---

distribution D is small, will also have bounded average over Smn, i.c. [Smi ExeSm p(x) is small. Second, if Smp contains set of points S that were initially generated independently by D*, then only a limited number of points from S can be removed by the filtering (the allowed number of removed points is controlled by appropriate hyperparameter).
Our algorithm is a refined version of bounded-degree outlier removal procedures from robust learning and learning with distribution shift [DKS18a, DKK 19, GSSV24, KSV24c]. The general principle behind these algorithms is that one can iteratively find polynomials that violate the desired condition over the input set and use them to filter the input points. In particular, the algorithm removes the points that give such polynomials values larger than a threshold. By choosing this threshold appropriately, one can control the proportion of removed points that lie in the clean set S in each step.
Prior work only gave guarantees for squared polynomials [DKS18a, GSSV24] and for non- oon-negative polynomials [KSV24c]. Here, we give filtering algorithm that preserves the expectation of any polynomial, as long as its absolute expectation is small with respect to the target distribution. This is crucial for our application in BC-learning, Moreover, our filtering procedure works for any hypercontractive target distribution Dr, which is also true for [DKS] 8a, GSSV24) but not for [KSV24c), which only works for the uniform distribution over the hypercube.
Learning with Bounded Contamination. Our algorithm follows two-phase approach: (1) Run our outlier-removal algorithm, and obtain a filtered subset Shte (2) Following an approach similar to [KKMS08], construct a predictor based on the polynomial P with smallest Li error on Sint- We now give sketch of the analysis of this algorithm and explain how an error of O + e) can be guaranteed. (The optimal dependence of 2n + c is obtained by carefully refining the analysis below.)
What would happen if we ran the phase (2) without filtering the dataset beforehand? As shown in [KKMS08], this approach works in the agnostic setting, i.e. when adversary can corrupt only the labels but not the examples. A key observation in [KKMS08] is that if p* is an e-approximating polynomial for the ground truth f", then after fraction of data labels are corrupted, the polynomial p" will have an Li-error of only at most + e. However, in the more challenging setting of learning with contamination over Rd even a single corrupted data-point can cause the L1-error of p* to be arbitrarily large. The reason is that any non-zero polynomial over Rd will be arbitrarily large in absolute value when evaluated at inputs x far enough from the origin.
Hence, the first phase of our algorithm aims to filter out such bad input datapoints. The following basic observation is key to approach: if p" is an ea-approximttor in L2 norm for a (+1 (-t1)-valuee J-valued function ʃ", then the average Ex-D- [] (x))² - 1|] is at most O(e2). This observation, together with our filtering guarantee, ensures that the average Ex [p""[[["'X0"n (x))² -1] is likewise bounded by O()) while removing almost exclusively outliers.
Yet, the set San might still contain many outliers. We show that the condition Ex~ (I= (x))²-1} < O(e) implies that the remaining outliers are not dangerous when it comes to phase (2) of our algorithm. Indeed, this condition tells us that the number of remaining outliers x in Sate with [p" (x) > is at
most O(ISaule/ lc/²)) Taking T = 2, we see that the total contribution to the Cn error of p" on San
of outliers with p0 (xx) > 2 is O(c). The remaining outliers contribute at most O(1) to this error, since there are at most (n) of such outliers and each satisfies (xx) S 2.
Overall, we see that the Li error of p' on Sint is at most O(n + c), and therefore the polynomial p found in phase 2 of our algorithm will also have an Lı error of at most O(1 + e) on San- Since phase (1) only removed at most Oc)) clean datapoints, we conclude that the L1 error of p on the clean dataset Sein is likewise O(n + e), which we use to bound the out-of-distributio error of p.
Learning with Heavy Contamination. Our heavy contamination algorithm follows the same structure as the one for bounded contamination: we first run the iterative filtering algorithm and then run L1 polynomial regression on the filtered dataset. This time, however, we choose the hyperparameters of the iterative filtering algorithm so that the proportion of removed points that are clean is inversely proportional to the heavy contamination ratio Q. In this way, we make sure to remove only a small fraction of the clean points. To conclude the proof, we use the notion of sandwiching polynomials. In particular, if f" E C is the optimum classifier on the input dataset, and Pup: Pdown are two low-degree polynomials such that (1) (x) Z f" Z Pdown(x) (x) for all x and (2) Ex [Pup - Pdoow [x)] < O(²/Q), then the filtering process guarantees that Exc-Seis [Pup (x) - Pdown (x)] scales proportionally to c. Overall, this implies that Pdowa has low Ci-error under Sau and that -o-polynomial regression achieves near-optimal error guarantees.
5

---

1.3 Related Work
Supervised Learning with Noise. The majority of existing works on robust supervised learning focus on label noise. In order to obtain efficient algorithms, it is standard and often necessary to make assumptions
the marginal distribution [Dan16, DK22, DKMR22], although there have been recent attempts to relax those assumptions [CKK* Even under common distributional assumptions, the best possible error guarantees often require exponential dependence on the excess error parameter e [DSFT* 14, DKPZ2IJ. A line of works was focused on providing faster learning algorithms for some classes at the expense of relaxed error guarantees [ABL17, DKS18a, 8a,, DKTZ20b] or under restricted noise models [DKTZ20a, DKK 22b]. We consider the more challenging scenario of learning with contamination, where there is noise on both the input examples and their labels. Before this work, efficient algorithms for learning with bounded contamination up to optimal error were known only for classes with low sandwiching degree [GSSV24, KSV24c], and nothing was known about classification under heavy contamination.
Models. Our Definition 1.3 is inspired by semi-random models, which lie between the average and worst case settings [BS95, FKOIJ. In particular, it resembles an instantiation of the semi- random model framework known monotone adversary, which breaks a statistical assumption used by a learning algorithm (e.g., i.idd draws from known distribution) by providing additional data. Our approach is inspired by recent algorithms for supervised regression problems, e.g., solving linear systems, sparse recovery, or matrix completion (G, KLL*23, JLM 23, KLL* 24]. that are tolerant to monotone adversaries. These algorithms also use reweightings that come with certificates of success. However, major qualitative difference between the aforementioned works and ours that our Definition 1.3 does not require that the adversary uses labels consistent with a "clean hypothesis." Instead, our algorithms can tolerate label noise (alongside covariate noise) and achieve the information- thcoreiccal optimal clean error under such a contamination model (Proposition 1.5).
Semi-Random
Testable Learning. In recent years, a number of works has focused on verifying the assumptions of learning algorithms. Testable learning was introduced by [RV23] in the context of verifying the distributional assumptions of agnostic learners and there are several subsequent works on this setting [GKK23, GKSV24, DKK 23, GKSV23, DKLZ24, STW24J. This paradigm has since been expanded to testing for distribution shifts that may harm the performance of supervised learning algorithms [KSV24b, KSV24a, CKK+ CKIS25), or even testing noise assumptions [GKSV25]. Here, we study a tolerant version of testable agnostic learning that was first studied by [GSSV24), and provide the first guarantees for halfspaces with respect to any fixed log-concave measure.
Learning with heavy contamination can be thought of as a finding version of the testable learning problem. More specifically, in testable learning the goal is to decide whether the input dataset is structured enough so that a near-optimal hypothesis can be found efficiently, while in HC-learning the goal is to find a subset of the input that is structured enough. An analogous connection was observed in [GSSV24] between TDS learning [KSV24b] and PQ learning [GKKM20] in the context of learning under distribution shift. There, the goal was to either decide whether the (unlabeled) test examples come from distribution that is similar to the one the learner has trained on (TDS), or find a subset of the test examples where the learner is confident in its predictions (PQ). See Remark G.
2 Notation
We consider a d-dimensional feature space X' which will either be IRd or the hypercube {=1]d. polynomial p over I2 of the form p(x) = Eacn' sp(a)x", where x" = [Iiejd] x/" is monomial of degree ||a]|2. The degree of p is equal to the maximum ||a|]/ such that (,(a) * 0. Over {=1}" we use the multilinear expansion p(x) = EzzIa (p) where x = I Zy. In both cases, we call cp the vector of coefficients. We consider sets of points S to contain examples that are separate instances of the correponding elements of X. We denote with 5 the corresponding labeled set of examples. We use x ~ S to say that is drawn uniformly from S. For a labeled distribution D over X' x [=1}. D is the marginal on X. In the following the distribution-speciff algorithms have sample access to the unlabeled target distribution D We use Na = (O. Ls) to denote the standard d-dimensional Gaussian and Unif, Unif for the uniform over the d-dimensional hypercube.

---

Iterative Polynomial Filtering
We first define hypercontracttvity,. which a crucial assumption for our filtering procedure. Definition 3.1 (Hypeecoonrracivvtty).. We say that distribution D over X' is A-hypercontractive with respect to polynomials for some A 2 1 if for any polynomial over X' and any 2 we have
1. Ex [xx=xlp((x)] & (At)*
(A (lxxxllx()]
where & = deg(p)
2. The absolute value of any degree-1 monomial has finite expectation under D.
Our main algorithmic tool is the following theorem, which gives a way to filter an arbitrary set of examples in order to preserve the expectations of polynomials whose expected absolute value under some hypercontractive target distribution is small. For the proof, see Appendix F.
Theorem 3.2 (Iterative Filtering). Let "D" be A-hypercontractive distribution
d-dimensional space X. Consider parameters c, E (0, 1) and R f, m 2 1, and let Simp be an arbitrary set of examples in X and Sret of Myef i..dd. examples from D For sufficiently large universal constant C 2 1, myet 2 RR (CA) (log 2)ae+1, then Algorithm I on input (Smp: Syet, m, E, R, e) runs in time poly( Mref, (d+ 1)t and outputs Sitt S Simp such that the following hold:
1. Let Seln be any set of m i.i.d examples from DD' where m 2 CR (2A(d+1)) log 8. Suppose that Simp is formed by first removing an arbitrary fraction of points Scha and then adding any number of arbitrary points. Then, the algorithm removes relatively small number of the examples Sein that appear in Stop:
(Satn (Spp)) \
1-1Smp
SSuul
em
with probability at least 1-8 over Selns Seef
R
2
2. For any polynomial of degree at most E, and Ex-D- [[((x)] IR we have:
Σ
p(x) S Em, with probability at least 1 over Syet
XE Stie
Algorithm 1: Iterative Polynomial Filtering
Input: Simp set of M points, Spef set of m,et points, m, f N, R 1. (0,
Output: Set Spic S Sipp.
Let B < 2(2.))2; B: 4dd TB'
Let P denote the family of polynomials p of degree most for which we have:
Ex Sx [|](x)]] < and Ex-- [[p(x)) 3;
3 S (x E Stup 1p(x) & B for all E P);
for i Compute p" and X as follows.
1, M do
Σp(x) and PEP
x Ex((x
p" = arg max
m XES
XES
if X* <
then return Set. +- S;
else
Let T 2 0 be the smallest value such that
S P Px~slpp((x)) > r*] 2 R R Px.-S. [Ip* (x) > r*] +A;
S- S fxeS S: (xx) > +*};
10
end
end
The algorithm iteratively removes the points that give large values to polynomials that do not satisfy the stopping criterion of line 6. The hyperparameter R determines how selective the filtering is: larger

---

values of R imply that less points will be removed in each iteration, and the proportion of removed points that are clean is smaller. The price one has to pay for larger choices of R is that the guarantee of part 2 holds for polynomials with smaller absolute expectation under the target distribution.
Our algorithm requires access to set of reference samples from the target distribution DD' and uses them to restrict its attention to polynomials with the desired properties under D The stopping criterion ensures that upon completion all of these polynomials will have bounded expectations under the empirical distribution over the filtered set. The bound depends on the hyperparameters- (target error) and m (effective size), but not on the degree l of the polynomials considered.
Applications
4.1 Learning with Bounded Contamination
We give results for BC-learning of any concept class that can be approximated by low-degree polynomials in La distance.
Definition 4.1 (Polynomial Approximators). For (0,1), 1), we say that a class C S {X' - {+1)}
has e-approximate degree & = f(e) with respect to some distribution D' over X' if for any s E C there is polynomial p of degree at most E(e) such that Dx [([(x) p(x))² S e.
Our main result additionally requires that the target marginal distribution is hypercontractive. This assumption is inherited by Theorem 3.2.
Theorem 4.2 (Polynomial Approximation implies BC-Learning). Let e, (0, 1) and A 1. Let D' be some A-hypercontractive distribution over d-dimensional space and let C be a concept class whose E -approximate degree w.r.. DD is l for some large enough universal constant C 2 1. Then, there is an algorithu that (c, 8)-learss under bounded contamination with respect to D in time poly(A (log })² (d + 1)', 2), and has (clean) sample complexity at most 2 0 (Ad log(1 (1/8)) 16+1.
In Table 2, summarize some of the new results we obtain corollaries of Theorem 4.2, combined with appropriate known bounds on the approximate degree (see Appendix C.I). We also present the previous state-of-the-art results for comparison. For monotone functions and convex sets, no non-trivial results were known before this work. For halfspace intersections, we obtain exponential improvements over prior work, and for polynomial threshold functions, we obtain the first near- optimal error bounds. For small-depth circuits, we obtain an improved dependence on the depth.
Concept Class
Target Marginal
Runtime
Error
Reference
Intersections of Halfspaces
Na Unifa Na or Unifa
(log(())/e))
2m +
This work [GSSV24]
(0(1//et)
4n + e
Na
dk (k)0 + (5)0())
O +
[DKS18a]
Na Na
21 +
This work
Degree-k PTFs
poly(dt 1/e) ((loR1//))00t)11
(( +e
[DKS18a]
Unifa
2m +
This work
Monotone Functions
Unifa
(o(va;e))
2n +
This work
Convex Sets
Na
(olva/e))
21j + c
This work
Depth-t, Size-s
Unifa
((ngg))) 1 1og1/e 1/0
21j + e
This work [KSV24c]
Circuits
Unifa
dOllog 200 log 1/c
2m +
Table Bounds on the time complexity of learning with bounded contamination of (unknown) rate E (0, 1) up to failure probability å = 0.01.
Our results nearly match the best known upper bounds for agnostic learning, albeit with a worse dependence the excess error parameter In particular, to achieve excess error e, we require
8

---

aapproxixii polynomials, while for agnostic learning an aapproximmao suffices. Therefore, our results imply, for example, a runtime of dO(log(k)/e for BC-learning of k-halfspace intersections with respect to Ná. but agnostic learning can be done in d'(log(k)/e [KOS08].
The proof of Theorem 4.2 is based on a delicate analysis of the error on the filtered dataset obtained by applying Theorem 3.2 and can be found in Appendix G.I. The filtering algorithm is used preserve the following important property of any polynomial p" that approximates a boolean function:
[[[p" (x))² < 1++0
(4.1)
We show that obtaining a filtered set that preserves this property is sufficient for learning with bounded contamination. To prove this, we crucially use the fact that the noise is bounded and that the right hand side of Eq. (4.1) is approximately equal to (rather than some larger constant). On the other hand, by applying part 2 of Theorem 3.2 on the polynomial q(x) (p" (x))² 1, we are able to ensure the desired property for p" on the filtered set.
4.2 Learning with Heavy Contamination
For heavy contamination, our results are based on the stronger notion of sandwiching approximators from pseudorandomness [Baz09].
Definition 4.3 (Sandwiching Approximators). For c E (0, 1), we say that a class C S {X - {+1)} has e-sandwiching degree& e = E(e) with respect to some distribution D over X if for any f E C there are two polynomials Pup: Pdown of degree at most E(e) such that:
1. Pdown (x) S f(x)= S Pup for all x E X and
2. E Ex [Pup (x) Pdown [x)] Sc
Once more, our main result requires hypercontractivity of the marginal distribution.
Theorem 4.4 (Sandwiching implies HC-Learming) Let e, E (0.1) 1) and A, Q 2 1. Let D' be some A-hypercontractive distribution over a d-dimensional space and let C be concept class whose 2 cQ sandwiching degree w.r.t DD" f for some large enough constant C 2 1. Then, there is an algorithm that (c, 8, Q)-HC learns C with respect D* in time (Aly (log(1/8))), (d+ Q/e). and has (clean) sample complexity at most O O(Ad)) -log }.
The proof of Theorem 4.4 uses once more Algorithm 1 to filter the input set, but this time we set the hyperparameter R to value that scales with the heavy contamination ratio Q. This ensures that keep most of the clean points, because the filtering process is highly selective. Due to the choice of R, the required sandwiching degree scales with Q as well. As consequence, for many classes, our bounds are exponential in Q. After filtering, the approximation property of the sandwiching polynomials is preserved under the empirical distribution over the filtered set, and this sufficient for efficient learnability of the optimum hypothesis on the filtered set, due to Theorem A.3 by [KKMS08]. For complete proof of Theorem 4.4 and quantitative bounds for HC-learning of various classes, see Appendix G.2 and Table 4.
Limitations and Future Work. We lay the groundwork for principled study of efficient learning algorithms in the presence of contamination. There are several interesting directions for future work: (1) Universality: All of our algorithms require sample access to the target unlabeled distribution D* Relaxing this requirement and obtaining algorithms that work universally with respect to broad classes of distributions is an important question. This is known to be possible for several problems in learning with label noise [BOW10, 10, 1,,17, DKTZ20b), robust unsupervised learning [KS17a, KS 17b, DHPT24], as well as testable learning [GKSV23, CKK + 24b]. (2) Improved Error Guarantees: Our algorithms obtain error guarantees that are proven to be optimal in general. However, it is an open question whether one can achieve error 1) + for BC-Iearning or error (Q opt + optclean) for HC-learning for special classes, perhaps by allowing the learner to output randomized hypotheses (also known as probabilistic concepts). (3) Characterization of Efficient Learnability under Contamination: We show that L2 polynomial approximation suffices for efficient BC-learning and Li sandwiching suffices for efficient HC-learning. However, it is not clear whether efficient learnability in these models is completely characterized by these notions of approximation. For agnostic learning, Li polynomial approximation is known to characterize efficient learnability for algorithms in the statistical query framework [DSFT+ 14, DKPZ21]. See also Appendix E.

---

Acknowledgments and Disclosure of Funding
Adam Klivans was supported by NSF award AF-1909204 and the NSF AI Institute for Foundations of Machine Learning (IFML). Konstantinos Stavropoulos was supported by the NSF Al Institute for Foundations of Machine Learning (IFML), by scholarships from Bodossaki foundation and Leventis foundation, and by the Apple Scholars in AI/ML PhD fellowship. Arsen Vasilyan was supported by the NSF Al Institute for Foundations of Machine Learning (IFML).
References
[ABL17] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM). 63(6):1-27, 2017.
[Ba193] Keith Ball. The reverse isoperimetric problem for gaussian measure. Discrete Comput. Geom., 10(4):411-42) dec 1993.
[Baz09] Louay MJ Bazzi, Polylogarithmic independence can fool dnf formulas. SIAM Journal on Computing, 38(6):220--272,, 2009.
[BCO+15] Eric Blais, Clément I. Canonne, Igor C Oliveira, Rocco A Servedio, and Li- Yang Tan. Learning circuits with few negations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), pages 512-527. Schloss Dagstuhl-LeibbizzZzeen
für Informatik, 2015.
[BDH+20] Ainesh Bakshi, Ilias Diakonikolas, Samuel Hopkins, Daniel Kane, Sushrut Kar- malkar, and Pravesh K Kothari. Outlier-robust clustering of gaussians and other non-spherical mixtures. In 2020 ieee 61st annual symposium on foundations of computer science (focs), pages 159-159. IEEE, 2020.
[DLS17]] Sivaraman Balakrishnan, Simon Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Conference Learning Theory, pages 169-212. PMLR, 2017.
[BEO02] Nader H. Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. Theoretical Computer Science, 288(2):255-27) 2002. Algorithmic Learning Theory.
[BGMMS21] Emily M Bender, Timnit Gebru, Angelina McMillan
and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM conference on fairness, accountability, and Iransparency, pages 610-623, 2021.
[BK21] Ainesh Bakshi and Pravesh K Kothari. List-decodable subspace recovery: Dimen- sion independent error in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1279-1297. SIAM, 2021.
[Bob01] Sergey G Bobkov. Some generalizations of prokhorov's results on khinchin-type inequalities for polynomials. Theory of Probability & Its Applications, 45(4):644-647, 2001.
[BOW10] Eric Blais, Ryan O' D'Donelll, and Karl Wimmer, Polynomial regression under arbitrary product distributions. Machine learning, 80(2):273-29) 2010.
[Bra08] Mark Braverman. Polylogarithmic independence fools ac circuits. Journal of the ACM (JACM), 57(5:1 2008.
[BS95] Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. Journal of Algorithms, 19(2):204 2234, 1995.
[BT96] Nader H Bshouty and Christino Tamon. the fourier spectrum of monotone functions. Journal of the ACM (JACM), 43(4):747-770, 1996.
10

---

[CDG19] Yu Cheng, Haa Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the thirtieth annual ACM-SIANE symposium on discrete algorithms, pages 2 SIAM, 2019.
[CG18] Yu Cheng and Rong Ge. Non-convex matrix completion against a semi-random adversary. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1362-1394. PMLR, 2018.
[CKK 224] Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, and Kon- stantinos Stavropoulos. Smoothed analysis for learning concepts with low intrinsic dimension. In The Thirty Seventh Annual Conference on Learning Theory, pages 876-92 976-922. PMLR, 2024.
[CKK 24b] Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis. Konstantinos Stavropoulos, and Arsen Vasilyan. Efficient discrepancy testing for learning with distribution shift. Advances in Neural Information Processing Systems, 37:137263-137308, 2024.
[CKLS25] Gautam Chandrasckaran, Adam Klivans, Lin Lin Lee, and Konstantinos Stavropoulos, Learning neural networks with distribution shift: Efficiently certifiable guarantees, In The Thirteenth International Conference on Learning Representations, 2025.
[CMY20) Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation in nearly linear time. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 14 1-18. IEEE, 2020.
[CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, pages 47-60, 2017.
[Dan16] Amit Daniely. Complexity theoretic limitations on learning halfspaces. In Proceedings of the fight- annual ACM symposium on Theory of Computing, pages 105-117, 2016.
[DGTZ18] Constantinos
Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zam- petakis. Efficient statistics, in high dimensions, from truncated samples. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages -39-649. IEEE, 2018
[DGTZ19] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zam- petakis. Computationally and statistically efficient truncated regression. In Conference on learning theory, pages 955-960. PMLR, 2019.
[DHK+10] Ilias Diakonikolas, Prahladh Harsha, Adam Klivans, Raghu Meka, Prasad Raghaven- dra, Rocco A. Servedio, and Li- Yang Tan. Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. In Proceedings of the Forty-Second ACM Symposium Theory of Computing, STOC 10. page 533-542, New York, NY, USA, 2010. Association for Computing Machinery.
[DHPT24] Ilias Diakonikolas, Samuel B Hopkins, Ankit Pensia, and Stefan Tiegel. Sos certifi- ability of subgaussian distributions and its algorithmic applications. arXiv preprint arXiv:2410.21194, 2024.
[DK22] Ilias Diakonikolas and Daniel Kane. Near-optimal statistical query hardness of learning halfspaccs with massart noise. In Conference on Learning Theory, pages 4258-4282.
PMLR, 2022.
[DK23] Ilias Diakonikolas and Daniel M. Kane. Algorithmic High--Diensionul Robust Statistics. Cambridge University Press, 2023.
[DKK*19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-88) 864, 2019.

---

[DKK 22a] Ila Diakonikolas, Daniel Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas. List-decodable sparse mean estimation via difference-of-puin filtering, Advances in Neural Information Processing Systems, 35:13947-13366 2022.
[DKK 22b] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 874-885, 2022.
[DKK*23] 23] Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Efficient testable learning of halfspaces with ad adversarial label noise. Advances in Neural Information Processing Systems, 36, 2023.
[DKLZ24] Ilias Diakonikolas, Daniel Kane, Sihan Liu, and Nikos Zarifis. Testable learning of general halfspaces with adversarial label noise. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1308- 1335. PMLR, 30 Jun-03 Jul 2024.
[DKMR22] Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren. Cryptographic hardness of learning halfspaces with massart noise. In Advances in Neural Information Processing Systems, 2022.
[DKN10] Ilias Diakonikolas, Daniel M Kane, and Jelani Nelson. Bounded independence fools degree-2 threshold functions. In 2010 IEEE 51 Annual Symposium on Foundations of Computer Science, pages 11-20. IEEE, 2010.
[DKPZ21] Ilias Diakonikolas, 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, pages 1552-1584. PMLR, 2021.
[DKS18a] Ilias Diakonikolas, Daniel 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.
[DKS18b] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1047-1060, 2018.
[DKTZ20a] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learn- ing halfspaces with massart noise under structured distributions. In Conference Learning Theory, pages 1486-1513. PMLR, 2020.
[DKTZ20b] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Non-convex sgd learns halfspaces with adversarial label noise. Advances in Neural Information Processing Systems, 11118854-18444 2020.
[DSFT 14] Dana Dachman-Solle Vitaly Feldman, Li- Yang Tan, Andrew Wan, and Karl Wimmer. Approximate resilience, monotonicity, and the complexity of agnostic learning. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 911. SIAM, 2014.
[Fer14] Dietmar Ferger. Optimal constants in the marcinkiewicz-zygmmuee incqualities. Statis- tics & Probability Letters, 84:96-101, 2014.
[FGKP06] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New results for learning noisy parities and halfspaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 563-574. IEEE, 2006.
[FK01] Uriel Feige and Joe Kilian. Heuristies for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639-671, 2001.
12

---

[FKV20] Vitaly Feldman, Pravesh Kothari, and Jan Vondrák. Tight bounds on 11 approximation and learning of self- boffdbounding functions. Theoretical Computer Science, 808:86-98, 2020.
[3] Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang. Jonathan Hayase, Georgios Smyrnis, Thao Nguyen, Ryan Marten, Mitchell Wortsman, Dhruba Ghosh, Jieyu Zhang, et al. Datacomp: In search of the next generation of multimodal datasets. Advances in Neural Information Processing Systems, 36:27092-271 2023.
[GKK23] Aravind Gollakota, Adam Klivans, and Pravesh K Kothari. A moment-matchnn approach testable learning and new characterization of rademacher complexity. Proceedings of the fifty-fifth 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: 53:15859-15870 2020.
[GKSV23] Aravind Gollakota, Adam Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Tester-learners for halfspaces: Universal algorithms. Advances Neural Information Processing Systems, 36, 2023.
[GKSV24] Aravind Gollakota, Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. An efficient tester-learner for halfspaces. The Twelfth International Conference on Learning Representations, 2024.
[GKSV25] Surbhi Goel, Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testing noise assumptions of learning algorithms. arXiv preprint arXiv:2501.0918) 2025.
[GOWZ10] Parikshit Gopalan, Ryan O' Donnell, Yi Wu, and David Zuckerman. Fooling functions of halfspaces under product distributions. In 2010 JEEE 25th Annual Conference Computational Complexity, pages 223-234. IEEE, 2010.
[GSSV24] Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos, and Arsen Vasilyan. Toler- ant algorithms for learning with arbitrary covariate shift. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 124979-125018. 8. Curran Associates, Inc., 2024.
[HL18] Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1021-1034 2018.
[HM13] Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Conference on Learning Theory, pages 354-375. PMLR, 2013.
[HS19] Prahladh Harsha and Srikanth Srinivasan. On polynomial approximations to AC Random Structures & Algorithmss 54(2):289-303, 2019.
[IK22] Misha Ivkov and Pravesh K Kothari. List-decodable covariance estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. pages 1276-1283. 2022.
[JLM+23] Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, and Kevin Tian. Structured semidefinite programming for recovering structured preconditioners. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural information Processing Systems 2023, 2023.
1a] Daniel M Kane. The gaussian surface area and noise sensitivity of degree-d polynomial threshold functions. computational complexity. 20(2):389 412, 2011.
[Kan11b] Daniel M. Kane. k-independent gaussians fool polynomial threshold functions, 2011.
[Kan13] Daniel M Kane. The correct exponent for the gotsman-linia conjecture. 2013 IEEE Conference Computational Complexity, pages 56-64. IEEE, 2013.
13

---

[Kan14] Daniel M Kane. The average sensitivity of an intersection of half spaces. In Pro- ceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 437-440, 2014.
[Kea98] Michael Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6))983-1066, November 1998.
[Kha93] Michael Kharitonov. Cryptographic hardness of distribution-speciii learning. In Proceedings of the Twenty-Füff Annual ACM Symposium on Theory of Computing. STOC '93, page 372-381, New York, NY, USA, 1993. Association for Computing Machinery.
[KKK19] Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. List-decodable linear regres- sion. Advances in neural information processing systems, 32, 2019.
[KKM13] Daniel M. Kane, Adam R. Klivans, and Raghu Meka. Learning halfspaces under log-concave densities: Polynomial approximations and moment matching. In Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 The 26th Anmual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pages 522-545. JMLR.org. 2013.
[KKMS08] Adam Tauman Kalai, Adam Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6)11777-1805, 2008.
[KL93] Michael Kearns and Ming Li. Learning in the presence of malicious emrors. SIAM J. Comput., 2074))807-837, 1993.
(KLL+33) Jonathan Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, and Kevin Tian. Semi- random sparse recovery in nearly-linear time. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2023.
PMLR, 12-15 Jul
[KLL+24] Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Semi- random matrix completion via flow-based adaptive reweighting. In Adyances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024.
[KLS09) Adam R Klivans, Philip M Long, and Rocco A Servedio. Learning halfspaces with malicious noise. Journal of Machine Learning Research, 10(12) 2009.
[KM13] Adam Klivans and Raghu Meka. Moment-matching polynomials. arXiv preprint 13Xiv:1301.0823 2013.
[KOS08] Adam R Klivans, Ryan O' D'Donelll, and Rocco Servedio. Learning geometric con- cepts via gaussian surface area. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 541-550. IEEE, 2008
[KS17a] Pravesh K Kothari and Jacob Steinhardt. Better agnostic clustering via relaxed tensor norms. arXiv preprint arXiv:1711.07465 2017.
[KS17b] Pravesh Kothari and David Steurer. Outlier-robust moment-estimation via sum-of- squares. arXiv preprint arXiv:1711.1158/ 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 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.
14

---

[KSV24c] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning constant- depth circuits in malicious noise models. arXiv preprint arXiv:2411.03570, 2024.
[KZZ24] Alkis Kalavasis, Ilias Zadik, and Manolis Zampetakis. Transfer learning beyond bounded density ratios. arXiv preprint arXiv:2403.11963 2024.
[LMN93] Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. Journal of the ACM (JACM), 40(3):607-62, 1993.
[LRB+21] Peng Li, Xi Rao, Jennifer Blase, Yue Zhang, Xu Chu, and Ce Zhang. Cleanml: A study for evaluating the impact of data cleaning on ml classification tasks. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 13-24. IEEE, 2021.
[RV23] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learning algorithms. Proceedings of the fifty-fifth annual ACM Symposium on Theory of Computing. 2023.
[RY20] Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares. In Proceedings of the Fourteenth Annual ACM- Symposium Discrete Algorithmss, pages 161-180. SIAM, 2020.
[She25] Jie Shen. Efficient pac learning of halfspaces with constant malicious noise rate, In 36th International Conference Algorithmic Learning Theory, 2025.
[SKL17] Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. Advances in neural information processing systems, 30, 2017.
[STW24] Lucas Slot, Stefan Tiegel, and Manuel Wiedmer. Testably learning polynomial thresh- old functions. 38th Annual Conference on Neural Information Processing Systems (NeurIPS 2024), 2024.
[Tal17] Avishay Tal. Tight bounds the Fourier spectrum of AC In 32nd Computa- tional Complexity Conference (CCC 2017). Schloss Bagsuuhl-Leibniz-ZZetuu fuer Informatik, 2017.
[Va185] Leslie G. Valiant. Learning disjunction of conjunctions. In Aravind K. Joshi, editor, Proceedings of the 9th International Joint Conference on Artificial Intelligence. Los Angeles, CA, USA, August 1985, pages 560-566. Morgan Kaufmann, 1985.
[ZS22] Shiwei Zeng and Jie Shen. List-decodable sparse mean estimation. Advances in Neural Information Processing Systems, 35:24031-24045, 2022.
15

---

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 justify all of our claims through appropriate proofs in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation 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 included a dedicated discussion on the limitations of our work in the last paragraph of the main part.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Our assumptions are made clear in Definitions 3.1, 4.1 and 4.3 and we provide complete proofs for all our results in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not 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 proof's 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 properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 is a specific model and empirical evaluation, it may be necessary to either make 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 can also be provided via detailed 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, or other means that are appropriate to the research performed.
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 reproduce that algorithm. (b) If the contribution is primarily
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 be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ httpc//guides//ooeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips. wttpccccpppccccceeececceccccccct httpa///ggiieee/eeeuuuuiiiiiiiii /CodeSubmic ssionnollll onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include 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 be 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: This paper does not include 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, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
18

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful 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 in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs 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 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 https: : /ttp///eerrp/.///ee cc Caabblic/Ethissoeee httbbiiicc/hhiccccceeeeeeee.e
Answer: [Yes]
Justification:
Our work fully complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have 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 sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is of theoretical nature and we do not identify any direct potential negative societal impact.
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 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.
19

---

The conference expects that many papers will be foundational research and not tied 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: Our paper does not pose any such risks.
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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not any existing assets.
Guidelines:
The answer NA means that the paper does 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/dataseta 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.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset'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:
We do release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing 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: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 the main paper.
According the NeurIPS Code of Ethics, 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:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 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 the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We used LLMs only for minor editing suggestions.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https : //taarrpp..c//oofeeeenee////222 for what should or should not be described.
22

---

A Additional Tools
In our proofs, we make use of the following results for hypercontractive distributions.
Lemma A.1 (Loewner Concentration, Lemma 3.8 in [CKLS25], Lemma B.1 in [GSSV24]). Let D be some h-hypercontractive distribution in d dimensions and let S be set of m i.i.d. examples from DD where m 2 (CAdd (log $ ))*R+1 for some sufficiently large universal constant C 2 1, 8 E (0,1) and A, e d 1. Then, with probability least ô over S the following condition holds.
1 E [((()))
E (p(x)))) x
2 E Ix((()))) for any p of degree at most E x-D
2 x~D
Lemma A.2. Let 'D be some A-hopercontractive distribution in d dimensions for some A 2 1. Let S be a of m i... samples from DD and Pa(S) be the family of polynomials of degree most E such that Ex~s((p(x)) and B 2 22//e. (d + 1) / the following holds with probability at least 1 - 8 over S:
S B, where f, 2 1. Then, for any c, E (0, 1), if m (C.) (log 4 4)+++1
P [p(x)] s B, for all E
21-6 1
Proof of Lemma A.2. We first apply Lemma A.1 to show that, with probability at least 1 - 8 over S, for any p E PS)(S) we have Ex-D (p(x)) v 2 [<xxs(((( < 2.3
Consider now the moment matrix M Ex pal (x) T], where (x)(x) is the vector whose coordinates correspond monomials of of degree at most f. Let M UDUT be the concise SVD of M, i.e., D is diagonal with dimension equal to the rank of M, U and UU is the orthogonal projection on the column (or row) space of M. Let (o(x) = D--DD-1/200 1/2 (>)(x) and observe that (xx=D(p(xx))(( ] = I and the dimension yp is equal to the rank of M, which at most (d + 1).. Here, we use the fact that all the entries of M are finite, due to hypereontraccivitty.
We may express any polynomial p in (S)(S) as a linear combination of the elements of yo, i.e., p(x) = o pxx), where ||č,113 = Ex~D (p(x)) 2 < 28. Moreover, we have the following due to Markov's inequality and the fact that [B[] (x) [ < (d+11)
B²
23 1)
P
(x)(
S
S
D
23
B
In the event that [|x(x)]13 $
8²a 20 we have |p(x) S ||ااممa||6(x)ا|| S 22 /23 B.
We will also use the following theorem which is implicit in [KKMS08] and shows that polynomial approximation is sufficient to find simple hypothesis with near-optimum error on a given dataset.
Theorem A.3 (C) polynomial regression [KKMS08]). Let Š be a set of labeled examples and be concept class such that for each ff C there is some polynomial p of degree at most E such that Ex~s(lf(x)
p(x)]] I e. Then, the degree-l Ln polynomial regression algorithm of [KKMS08] outputs, in time poly([S)d*/e /e), a degree-E polynomial threshold function such that ((xw))_ly # h(x)) S min P (xx))~Sl # [(x)) +
We also give the definition of L1 approximating polynomials, which are sufficient for agnostic learning, but it is not clear whether they suffice for BC-learning. We instead use the notion of Ca approximating polynomials (Definition 4)..
Definition A.4 (Cn Polynomial Approximators). For E 10, we say that class C C {X
{+1}} has c-approximate degree é = E(c) with respect to some distribution D' over X' if for any C there is a polynomial p of degree most E(c) such that Ex [[((x) - p(x)] < c.
The difference between L1 and Le approximators is that the former enjoy the approximation property with respect to the L, norm, while the latter with respect to the La norm. Achieving La approximation is, in general, a stronger assumption, because the Li norm is upper bounded by the La norm, but not vice versa. Nevertheless, for most interesting classes that L1 approximators are known, we also have Ce approximators. This is because of analytic advantages of the Le norm.
23

---

B Error Lower Bounds for HC-Learning
In order to prove our lower bounds, we provide definition for the adversary the context of heavy contamination.
Definition B.1 (Contamination Strategy), An algorithm M is called (randomized) Q-HC strategy if, upon receiving labeled set Sclu. outputs set Smp of size 15mppl I Q|Setal such that Smp Seln- For m N and labeled distribution D, we denote with M(D")) the distribution of the output Simp of M on of m i.i.d. samples Sehn from D. Note that mpp depends the random choice of Seln- as well as the randomness of M.
We first prove the following lower bound, which holds for any non-trivial concept class.
Proposition B.2. Let C be any concept class such that there is some f E C for which -f E C. For any Q E 32.3.... }. any unlabeled distribution D* any E [0. 1/2), c, 8 > and any m 2 log(2/5) there is a Q-HC strategy M and distribution 'D whose marginal is DD such that, if we let D' be the distribution of (x, -y), where (x,y) D. then the following hold.
2c
1. M(D") =
M(D"))=((D')))) M((D')m)
2. sin P. ((xx))-VV # [(x)] = minsee IP ((xx)) # [(x)] =
3. With probubility least over Sinp ~ M(D we have Q opptooal S 1 - + e, where optiotal minsec (x.,))~u.,, [(x)].
Hence, no HC-leamer for C with respect to D* can achieve error less than (Q (Q +opt -E) with probability more than 8, even when opt
Proof of Proposition B.2. Let D D Consider the following labeled distributions. First, Dj is a distribution over X' x { whose marginal on X' is D and the labels are generated as follows:
fxx,, with probability P
V1
(xx), with probability p
Consider also distribution D2 whose marginal is also D but the labels are generated as follows:
[x((),, with probability 1 1-2
1/2 = (x(x), with probability
The adversary receives set Seln of i.i.d. samples from D (Di, D2) and does the following.
1. First, the adversary computes the value my E (x.))e8..... Hy f(x)). well as the
value m2 = E(x.)es.., = = fxx)).
2. If m. m2, then the adversary adds M m examples drawn by D and labeled by -f(x).
3. If m, m2, then the adversary adds m2 m, examples drawn by D and labeled by fxx). as well as M 2m2 examples drawn by D and labeled by (x()).
Part 1. Let m, where E {1,2] such that D D,. We have that & follows the binomial distribution with parameters (m, 1 - p), and is independent from the value of i.
Given any realization m, of & with m, > m/2, by drawing M i.i.d. samples from D and labeling & of them according to f(x) and M E of them according to (x)). We have that M(DIT) ((DT"))eem/2
equivalently form the input examples Siap
M(D 1/>m/2-
Given any realization m, of & with m, < m/2, we can equivalently form the input examples Smmp by drawing M i.idd samples from D and labeling m - { of them according to f(x) and M m + g of them according (x). We, therefore, have M(D )l M(D ((DD))lem//)) 1lesm/2
Overall, since & does not depend on i, we have M(D M(D
24

---

Part 2. Follows immediately from the fact that f- E C and the definition of D = D1, D'= D2.
Part 3. Regarding the error benchmark, we have Q opt = max(E,m- m < - p-p whenever
- (1 p)ml I em, which happens with probability at least 1 - 6, according to the following inequality.
10
Pl[s - (1 - p)ml > em] I 2 2exp( 1eop(-2e2110 2m)mm < á
The bound follows from application of Hoeffding's inequality, since & is binomial of mean (1 - p)m. It follows that with probability at least 1 - 8, the algorithm outputs a hypothesis with error least (Q optao
opteiman
c).
Implication to HC Learning. We have M MM Let A be any, potentially randomized algorithm, and let h :- A(M(DT)) = A(M( be the random variable corresponding to its output, where h X' + {+1]. Consider the event that h is such that: P ((x,))),, (1(x) o < 1/2. Then, we have:
P (x.g)>>2
(x(x) # y]
IP (x.y)~D,
[h(x) + y]
[h(x) *
1/2
(x,g)>D,
Note that the same is true even h is a randomized classifier. Overall, the error of A on either D1 or Do is 1/2 with probability at least 1/2. Finally, due to part 3, with probability at least 1 - 8, we have 1/2 2 (Q- opttotal opt - E). which implies the desired result.
For finite feature spaces and the particular choice of the class of all functions, obtain sharper information -theoreticct lower bound on the error. Note that this lower bound captures the problem of HC-learning halfspaces over (+1) in one dimension.
Proposition B.3. Suppose that |x| < oo and C is any concept class from X to {=1}. Then, on any value of Q in 32.3... 3....... any cittrriuuiionsspcciff HC-learner will output hypothesis with error 1 with probability least 2 on some instance where Q optiotal = Moreover, if (+)
then the instance satisfies opt O.
Proof of Proposition B.3. The adversary receives the clean dataset Sehn and creates duplicate S'in where all the labels are flipped but the feature vectors are unchanged. Then, the adversary draws (Q - 2) m i.i.d. examples S' from the marginal distribution D on X' of the clean distribution D and labels them according to fi. The input dataset is Senn U S U..
Note that the input dataset is completely independent from the clean labels, since Sein U U.S. can be constructed equivalently by choosing an arbitrary function : X + {+1) to label the points in Sein and then label the points in Sttn according to -g.
Therefore, we may assume that the ground truth labels are generated by the function f*, where -f" is the most likely output of the HC-learner on a dataset of the form Seta U 8% U.. Since there are at most X1 possible functions, A must output -f" with probability at least 2 2-1211 When A outputs -f", the error 1.
Finally, note that f1 achieves error on Simp equal to 1/Q, so opt = 1/Q and Q opteoaal 1.
When = {+1]*, we have f* E C and, hence, opt == minsec IP (x(x)))=(l # f(x) 0.
C Approximation Theory Results
C.1 Low-Degree Approximators
Our structural Theorem 4.2 can be combined with results from polynomial approximation theory in order to obtain end-to-end results on learning with nasty noise, including the results of Table 2.
Intersections Halfspaces. For the class of k-halfspace intersections, [KOS08] showed that the e-approximate degree with respect to the standard Gaussian distribution N₂ (see Definition 4.1) is t(e) & log(k)/e and [Kan] 4] obtains the same result with respect the uniform distribution Unif over the hypercube.
25

---

Monotone Functions and Convex Sets. For monotone functions, the e-approximate degree with respect to Unifa was bounded by {(c) v vd/c in [BT96]. For convex sets, [KOS08] showed that the c-approximate degree with respect to the Gaussian distribution can be bounded via the Gaussian Surface Area (GSA). Combined with the result of [Ba193] on the GSA of convex sets, the corresponding bound is {(c) S vd/c.
Polynomial Threshold Functions. For the class of degree-k PTFs, the e-approximate degree with respect to the standard Gaussian was bounded by f(e) I k2/e in [Kanlla]. In [Kan13], it was shown that {(c) xlog) (log 1/c)0 with respect to the uniform over [=1]d.
Low-depth Circuits. For the class of AC circuits of size and depth t, the c-approximate degree is known to be at most E(c) (llog()))*~logg log(1/c) due to the seminal work of [LMN933 and subsequent improvements [Tal17].
C.2 Sandwiching Approximators
For the more challenging problem of learning with heavy contamination, we require the existence of sandwiching approximators (see Theorem 4.4), and show that arbitrary moon-sandwiching) approxi- mators do not suffice (see Theorem E.2).
Decision Trees of Halfspaces. For the class of depth-l, size-s decision trees of halfspaces, [GOWZI0] showed that the e-sandwiching degree with respect to either the standard Gaussian or the uniform the hypercube is E(e) < (
Low-Depth Circuits. The e-sandwiching degree of AC circuits of depth and size s known to be most E(e) < O(log(s)) log(1/e), due the celebrated results of [Bra08, Tal17, HS19].
Polynomial Threshold Functions. The c-sandwiching degree of degree-k PTFs over the Gaussian was bounded by É(c) I
in [STW24], based on the pseudorandom generator of [Kan 1b]. Here, O&() (:) hiding multiplicative factor that scales as an arbitrary function of k. For h: = 2, the sandwiching degree with respect to the uniform distribution over the hypercube is known to be at most E(c) I ((1/e²) due [DKN10].
Functions of Halfspaces over Log-Concave Measures. For arbitrary functions of l halfspaces, the e-sandwiching degree with respect to any log-concave distribution was shown to be at most t(e) < exp (oo((log(oog())// (())) /e+) by [KM13, KKM13].
D
Complexity of Learning with Adversarial Label Noise
The computational complexity of agnostic learning (or equivalently learning with adversarial label noise) is much better understood than the complexity of learning with contamination. In this setting, the learner receives i.i.d. examples from some labeled distribution D whose marginal on the feature space X' is well-behaved (i.e., Gaussian or uniform) and is, otherwise, arbitrary. The goal is to output, with high probability, a hypothesis whose error is at most opt + e, where opt = minyec IP ((xx))=D11 [y + [x)], for some target concept class C.
Upper Bounds. On the upper bound side, [KKMS08] showed that any class with bounded C approximation degree admits dimension-eefficient agnostic learners via low-degree Li polynomial regression. Several prior and subsequent works provided such bounds for many fundamental classes, based on Fourier or Hermite analysis [LMN93, BT96, DHK* 10, Kan la, Kan13, 3, Kan14], as well as geometric properties of Gaussian spaces [KOS08]. Note that the usual way to bound the Cn approximation degree, is to first bound the L2 approximation degree and then use Cauchy-Schwee inequality. This is because bounding the La approximation usually more analytically convenient. However, this approach does not always give tight results for the degree in terms of the approximation error. In [FKV V20, it was shown that L, approximation bounds over the hypereube can be obtained directly for any function class with bounded noise sensitivity.
26

---

Concept Class
Target Marginal
Upper Bounds
Lower Bounds
Intersections of 1 Halfspaces
(ollog())ee))
Depth-t, Size-d
Unif{#13d
dOllogy)'
logg1/
dilog o)
(E 0(1))
Boolean Circuits
Degree-k PTFs
Ia)
d0(216))
(0(212)
Monotone
Uni
20(va/(3)
20(2//))
Functions
Table 3: Upper and lower bounds on the time complexity of agnostic learning up to excess error and failure probability 8 0.01. The lower bounds either hold for algorithms the Statistical Query model [Kea98] or for any algorithm under appropriate cryptographic assumptions.
Lower Bounds. The complexity of agnostic learning with respect to Gaussian marginals was shown to be characterized in terms of the Li approximation degree for algorithms that fall in the statistical query (SQ) framework by [DKPZ21]. implying the lower bounds of Table for intersections of halfspaces and polynomial threshold functions. For the uniform distribution on the hypercube, similar characterization was given by [DSFT* Moreover, [BCO* 15] showed an information- theoretic lower bound for learning monotone functions even in the realizable setting, implying the lower bound of Table 3 for monotone functions. For AC circuits, [Kha93] provided cryptographic lower bound.
E Lower Bounds for Learning with Contamination
Bounded Contamination. Although the problem of learning from contaminated datasets is, in principle, more challenging than learning with label noise, it is not clear whether the common formulations of the former are formally stronger than those of the latter. particular, the problem of learning with label noise is usually formalized in terms of agnostic learning, where the goal is to achieve error opt c on the inpur distribution DD for opt = min fec PP ((xx))>D(V (VV * f(x), where is the learned class. In contrast, learning with contamination is usually formulated learning with nasty noise, where the goal is to achieve error 27 + c on the targer distribution ff") where f" E C and y is the noise rate. Therefore, given an algorithm for learning with contamination, one may obtain an agnostic learner with error guarantee 3opt + e, but it is not clear whether the guarantee of opt + can be achieved in black-box way. This is because in one formulation the error measured with respect to the input distribution and in the other it is measured with respect to the clean target distribution.
Furthermore, many of the lower bounds for agnostic learning seem to exclusively rule out algorithms with error guarantees of opt + [DKPZ21]. Therefore, these lower bounds do not transfer directly to learning with bounded contamination as defined in Definition 1.1. One natural way go around this, to observe that our result Theorem 4.2 would also hold for the following stronger version of Definition 1.1.
Definition E.1 (Agnostic BC-Learning). An algorithm A is agnostic BC-learner for C C {X {+1}} if on imput (c, 5, Stmp). where e,6 E 1). and Sma is generated by with bounded contamination n) for some labeled distribution D, and n [0. 1), the algorithm A outputs some hypothesis h : X + {+1} such that with probability at least 1 - 5 over the clean examples in Sim and the randomness of A:
+ 1(x)) S 21j opt +G, where opt (x.I)~D
P
min P JEC (x.y)=
P
I(x)
The sample complexity of A is the minimum number of examples required to achieve the above guarantee. Moreover, distribution-speciff BC-learner with respect some distribution D' over X is a BC-learner that is guaranteed to work only when D = D*
Note that Definition E. is a generalization of agnostic learning, since we can set = 0. Our Theorem 4.2 holds even under this definition, and all the lower bounds for agnostic learning (Table 3)
27

---

are inherited as well. However, agnostic learning is known to be characterized by the L1 -paaproxi degree [KKMS08, DSFT 14, DKPZ21], whereas we require the stronger assumption of low L2- approximate degree. Therefore, while for most interesting classes our results are essentially tight, complete characterization of efficient learnability in the setting of Definition E.1 remains open.
Heavy Contamination. We give the following, information-thhoree lower bound for learning monotone functions with heavy contamination. Our lower bound highlights separation between bounded and heavy contamination and justifies the need for a stronger notion of approximation than standard polynomial approximators.
Theorem E.2 (Lower Bound for HC-Learning of Monotone Functions). Let C be the class of monotone functions over {+1}". Any HC-learner for C with respect to the uniform distribution over the hypercube Unif({=1}() requires sample complexity 20(4), even when = 1/4. Q = 2 and
6 == 1/3.
Proof of Theorem E.2. Suppose that the ground truth is constant function, i.e., either s* = 1 or f = -1, and that m I 2d/10/10, Then, the adversary receives the m clean examples Simp and draws m additional i..d, examples S' from Unif({+1)d) labeling them according to -f. The input dataset is Smp Senn U..
Note, first, that no algorithm can achieve error better than 1/2 with probability at least 1/2, since guessing f randomly is optimal strategy because the distribution of the input dataset mp is exactly the same in the two cases corresponding to f* = -1 and f = We will show that
Q optt
with high probability over the choice of Simp-
We say that x and x' are comparable if x S x' or S x, i.e., if x(i I x(ii for all i or x1( S x(i) for i. Since coordinates are independent, we have
Let x, x, x' be two independent samples from Unif([#1])
P X.X
S x(),, for all i [d]]
II
P
x (1) (3/4)a
x.X'
<E(cd]
Similarly, for the other direction we have that xxx (x(i) 2 (i), for all i E [d] S (3/4)a and, overall, that Px x' are comparable] < 2 (3/4)².
We have set Simp of 2m examples. It suffices to show that no pair of examples in Sinp is comparable, because, then, any labeling of these examples is consistent with some monotone function and, hence, opt = 0. We overall have at most 4m pairs and each of them is comparable with probability at most 2 (3/4).. Therefore, by union bound, the probability that there a pair that is comparable is at most Sm 3 (3/4)/ 1/10.
F Omitted Proofs for Iterative Polynomial Filtering
We now give the proof of our main technical tool, Theorem 3.2. The proof follows the approach of [KSV24c], but has a number technical differences. In particular, the algorithm of [KSV24c] only gives guarantees for non-negative polynomials and works with respect to the uniform distribution on the hypereube. Here, we preserve the expectation of any polynomial, with respect to any target hypercontractive distribution that can be sampled efficiently.
Proof of Theorem 3.2. We first observe that the family P of polynomials p of degree at most & for which Ex- [Ip(x)]] I y and Ex~SS.. [[] < 3 can be described by O(mret) linear constraints plus one convex quadratic constraint over the coefficient vectors whose dimension is (d + 1). Therefore, lines 3 and can be implemented convex programs in time poly([Smml mrefs (d - 1)
Lines 8 and 9 can implemented with single pass the input points.
We first prove the following claim, which ensures that lines and 9 are well defined.
Claim. When x > e, there exists -* that satisfies the guarantees of line 8.
28

---

Proof. Suppose, for contradiction, that for any 7 2 0 we have
I
P ([llll((x))
RR R. P (x)
m. x
x
We may now integrate both sides of the inequality over E [0, B), since it holds for all 2 0. Note that Io" (x) for all x and, therefore, the following are true
(x)l = f E
> 7] dr /
PP
(x)
Ilpe (x)
> 7] dr
(F.1)
x~s
==
==0X~5
E 1P (x)l] XeoStar
P lb" 7| dr
P 11 (x) 7| dr
(F:2)
T= T=OX
The second equality in Eq. (F.I) follows from the fact that for any p" E P, S contains only points such that p² (x) [-B. due to line 3. The inequality in Eq. (F.2) follows from the fact that the integrated function non-negative. Overall, we obtain the following inequality
S
|S|
E X
(x)]
E E. (x)] (x)]l m x-5
< R E IPpp (x) + AB x-SSee
222 and where the last inequality follows from the fact that p* E P and, hence, Ex-Sm.n (x)"(xx]]== S A
We have reached contradiction, because we showed that X" S.
Note that due to the claim above, we have {x E S (x"(x) > > + 0. This means that at each iteration remove least one point from the input dataset and, therefore, do not need more than M Smmpl iterations. The following claim ensures that we only remove a small fraction of clean points from Smp-
Claim. With probability at least 1 - over Sein and Seet, we have
[(SeIn n (Spp)) \ SSull -
em
+
-SSp \ Satel
2
Proof. We will show that with high probability over the clean and reference datasets, the number of removed points from Senn is small. First, we account for the initial filtering of line 3. In this step, we remove points x from Simp that give large absolute values to polynomials
P, i.e., polynomials who, in particular, have bounded second norms over Sret- Due to Lemma A.2 and since Mref 2 (d) (log ) the probability that some x drawn from D gives [p(x)] > B for some p E P is at most e/4. Therefore, the total number of points removed from Setn in this step follows the binomial distribution with m number trials and probability of success at most e/4. By a standard Chernoff bound, and since m 2 C (1/8), with probability at least 1 - 8/2 we have
Hx E Sen |p(x)] > B for some p E PP) < cm/2 remains to account for the points removed line 9. The removed points are always of the form (x S: [x*(x) > }"} for some p² P. Moreover, according to line 8, we have
(F.3)
1
Σ
11p
(x) > r") 2 R
P X
Ip (x))
+
m
XES
Since m, Myef 2 C (oo1))+ for some sufficiently large universal constant C" 2 and the VC
(A/R)*
dimension of the class of polynomial threshold functions of degree E is most (d+1); 1)5, we have that
with probability at least 1 8/2 over Sehn Seef the following holds for all polynomials p of degree at most and all T 2 0
R P [l(x)]
P [[(()) > r] + A,
X~SSan
X
since Sehn and Sret are both i.i.d. samples from the distribution DD and {(p(x)) > r is equal the sum of two degree- polynomial threshold functions, 1 (p(x) > r) + (p(x) < - Therefore:
x[x E 5 1p" (x)l 7"]l 2 R R- E Sem 1p'(x)) >>>,,
for any update we make. Summing over all the updates, we obtain that the total number of points removed from San by the updates line 9 is at most
(1/R) |mmmp \ Sttel
(F.4)
By combining Eq. (F.3) and (F.4), we obtain the desired result, where the probability of failure is at most 8 due union bound.
D
29

---

So far, we have proven the first part of Theorem 3.2. We will now prove the second part, by showing the following claim.
Claim. Any polynomial of degree at most i and Bx<<(lp(x)) 3 e/(4R), lies within P with probability least ô over Sret.
Proof. Let D = = D" Fix any polynomial p with (xw-D[p((x S </(4)). Due to the hypercontrac-
tivity of DD (Definition 3. 1), we have xx (p(()) S (2A)² = 3/2, since Ex-D (lx(())((]]]))))))) S 1. By 6 2 over Stet, we have Ex-s,.. [((())) & B.
Lemma 1. since Mref is large enough, w.p. at least
It remains to show that with probability at least 1 - 8822, we have (xx-s...ll(x)) < e/ The following bound can be obtained for any by applying the Marcinkiewicz Zygmuun inequality (see [Fer14] 14)), due to the fact that Stef consists of myet i.i.d. examples.
32R²t 2
|D(x)] x 11(x2))))) 22
[1
18 Seef Df
E X
[[p(x)]]
x E [n(x')]]
2
E X
4R
To conclude the proof the claim, we use the simple inequality (a + b)20 I maxfa" b20) for all b, 2 0 as well as hypercontractivity bound the expectation on the right-hand side by (8.Af) 28t EX Ex~<plpt [lp()]])) Due to the choice of Myef. we choose = (0)( we obtain a bound of 6/2, desired.
This concludes the proof Theorem 3.2.
G Omitted Details for Learning with Contamination
G.1 Bounded Contamination
We give the proof our main result on learning with bounded contamination (Theorem 4.2) below.
Proof of Theorem 4.2. The algorithm receives a dataset Smp generated by (D*,f*) with bounded contamination of rate 1) E (0, 1). where f" E C and n are unknown, draws a set Seef of Myef Ad) (log 5 1)641 i.i.d. unlabeled examples from D", where C" > is sufficiently large universal constant and does the following.
1. First, the algorithm runs the filtering procedure of Theorem 3.2 (that is, Algorithm 1) on input (Smp. Syet, m = |mmpl 26, R = 2, 24c / /C) to form the filtered dataset Spn. where the labels are consistent with Simp-
2. Then, the algorithm finds a polynomial ñ of degree at most & that minimizes the following convex objective.
p arg min
E My
p(x)]
Sx
s.t. p has degree at most
3. The algorithm outputs hxx)= sign(((x)++)) where f e R minimizes the one-dimensional objective PP (x. [y * sign (x(x) T]] over T E IR.
We will now bound the error of on the clean dataset Sen according to which Simp was formed (see Definition 1.1). This suffices because, due standard VC theory, and since h is a polynomial threshold function of degree at most f, as long as 1Saml > C (d+1))= å. for some sufficiently large universal constant C" 2 1, we have that IP Ix=x(f((x) * h(x)] is approximately equal to its empirical counterpart (xx.)) [y # h(x)).
Consider p" to polynomial of degree at most such that Ex [ (x) p" (x)) S Se' where é él //C. Since p" approximates Boolean-values function fr, the values of p should, in
30

---

expectation, be close to either or -1. In particular, we obtain the following bound using the Cauchy-Schward inequality:
x~D 11 (x))2
-1]] 11] E (le ( (/*()))
x
E (x))xx)) - fx)) lo (x) + fx))]]
X-Di
$ E 1100 (x) (x)) V (x)
XWDD
$ é + V2e' S 36 /2//VC
(G.1)
Note that g(x) (x*(x))² -1 1 is polynomial of degree at most 2C. Therefore, Algorithm can be used filter out the points x such that (x) is too large and, in particular, due to Theorem 3.2, the following holds with probability at least 8/4 over the random choice of Sref and Setu as long as m 2 C² (2A(d+1))*
log 2 and myaf 2
(C' Ad) (log 1 188411
8
em
Σ
[(x) S
(G.2)
C"
XESnis
where C" VV/24. We will now show that this bound is sufficient for our purposes.
Consider the quantity p |Saal ((x.))~Smm. ly + h(x)]. We first bound the quantity P P S
[Saae 2m E(x.y)~Bnn bly - px) where the factor 1/2 appears due to the fact that the choice of f is optimal (and random choice would yield the factor 1/2 with positive probability, see (KKMS08)).
Furthermore, we have the following, due the fact that p is optimal among low-degree polynomials for San with respect to the absolute error.
P
Σ
x(x) I 2m
Σ
ly - px((((x)]
2m
(x.
Σ
(x) -x(xx)
1
Σ
--)"(xx)
2m
2m
(x.9)) S
(X.)) /Bet
Σ
18nit
1
Σ
lx((x)
(G.3)
2m
2m
2m
(x.y)E
( Sat
15emm and therefore have I E(x,)) [x) px() Exwsaan [lf (ff=sx)lll((xx p" (x))]. In order to bound this quan- tity, use the fact that Seh is set of m i.i.d. samples from hypercontractive distribution, combining the Marcinkiewicz-Zygmmnn equality to higher moments), hypercontractivity and boundedness of f" to obtain that, long as m 2 (C' (log(1/5) 2i+1" 2 with probability at least 1 - 5/4 over the choice of Senn we have:
For the first term, observe that choose m 1mmpl
inequality (which is a generalization of Chebyshev's in-
E (x) (x)11 S E 11 (x) - (x) +e/6 xnD
SeeSela
$ E (f (x))) + e/6
2 <e/vo + e/6 S E/3
(G.4)
For the last term in Eq. (G.3), first the basic fact that the variance of any random variable is neganegetive and hence Exx- SSe (x))] < (Ex~ / [(p' (x)) Then, observe that Sm Se 1( (x) E Exwssn
Stil's Se [g(x)) + Overall, we have:
1
Σ
(x(x))
Sai \. Setml (1+ +
E X~ (atn
(2(x))) 1/2
(G.5)
2m
2m
XE Sat
31

---

We will now bound the quantity P' = Ex- Sta /Sau [Ø(x)]
Sate /Sein Exesane 18tt ((x).
1
p'
1
g(x)
Σ
q(x)
San
\
Selal
Stilt \ Selul
XE
XE Seate nSein
(G22
émm
E
1x(x)
C" SAi SSanl
SAn Setnl
xe XESm SSete
e
m
E X--Sel
[[((x)]
(G.6)
CM1 Smk \ Sennl
SSitt
\
Setn
The first inequality in the expression above follows from the guarantee Eq. (G.2), which provided by the filtering algorithm. We may now use the Marcinkiewiez--Yy Zymgund inequality once more to obtain that, as long as m 2 (C" (lo((1/))) with probability at least 8/4, 4, we have:
E X--Sel
[[((x)]
S
E (a(x))+++1/0 S 2//"
x-D
where the last inequality follows from Eq. (G.1), the fact that q(x) (p" (xx)x)) 1, and recall that 2.am
C" = VC. Overall, we obtain the bound p" S (HIShi /Saal Note that since for any 2 0 we have
vI+asl4 Vo, by substituting the bound for Pr in Eq. (G.5), we obtain
Shh \ SStnl
Σ
lx*(x)) S
2m
2m
V2"
XE Smn Sa
where we used the fact that |Smut \ (Setal s m to bound the factor v Shit \ Seml/m m in the second term of the above bound by 1. In total, by choosing appropriately large, we have the following bound, where combine Eq. (G.3), (G.4), and (G.5).
< |Sitt Sotal 2e
Σ (mu
1 + M(x))
with probability at least 36/4 4 over the random choice of Simp and Syet- We will now bound I ((x.)))Smmp ly * h(xx) by 2n + 5e/6. We have the following:
1
P Seln
+ hxx))(]
Σ
1 h(x)}
m
SStt
Σ
{v + h(x)} +
Σ
1 + h(x))
(x.
(xty)e \,S
1lv h(x)) + Seln \ S
EStt)
San \ Sanl + 1(Sem n Bmmp)) \ Saul + 1Sen \ Simpl
+ 22/3
m
In order to complete the proof, we use the guarantee of Algorithm that with probability at least 1 - 8/4, we have
[(Sein Simp) Saull
S
_ Simp \ S +
1
12
1
1 2[Sinp \, \San)) \ Smell + em/12.
(Seln n Simp) \. Satel +
2
Therefore, we have 1(5atn n Simp) Smiel S 1(5mp \ Senn \ Saul + em/6. Note that the union of the sets (Simp Soln) \ Sait and SMI \ 1. is disjoint and equals the set of adversarial examples Sadv Simp Soln- By the definition the noise model (Definition I.1), we have that [SSav] S 17m and 1Semn \ Smmpl = |Savvl S mm. Therefore, we overall obtain the desired bound of
IN * h(x)) < 2n + 5c
IP (x.n)~Seen
This concludes the proof of Theorem 4.2.
32

---

G.2 Heavy Contamination
In Table 4, we provide a number of end-to-eun results for learning with heavy contamination, which are obtained by combining Theorem 4.4 with appropriate known bounds on the sandwiching degree (see Appendix C.2). The first row of Table 4 gives the bound @0(Q"*"/e") for learning intersections of k halfspaces with Q-heavy contamination by choosing
k, as well as the bound d0102k44 (ct) for arbitrary functions of k halfspaces, with the choice s = 2 1 k.
Concept Class
Target Marginal
Runtime
Depth-l, Size-s
Na Unif,
Decision Trees of Halfspaces
Depth-t, Size-s
Unifø
d x) log(Q/c)
Boolean Cireuits
Degree-k PTFs
Na
D PTFs
Unifa
Table 4: Bounds on the time complexity of learning with Q-heavy contamination up error Q rotao + e and failure probability 5 0.01.
We now give the proof of our main result learning with heavy contamination (Theorem 4.4).
Proof of Theorem 4.4. The algorithm receives a Q-heavily contaminated dataset Simp. draws a set Sret of mzef QCC' (log 3 ) i.idd unlabeled examples from D = DD, where C' 2 is sufficiently large universal constant and does the following.
2b
1. First, the algorithm runs the filtering procedure of Theorem 3.2 (that is, Algorithm 1) on input (Smp: Sect, m (C' Ad)" log
e,, R
2Q e/3) form the filtered dataset Shn-
2. Then, the algorithm finds polynomial f of degree at most E that minimizes the following convex objective.
f == arg min
E [Iv p(x)l]
(x.
s.t. p has degree at most l
3. The algorithm outputs hxx)= = (fgn(((x)++7 7), where + E R minimizes the one-dimensional objective P (xx.))~.Sm.. [v * sign (p(x) + +]] over 7 E IR.
We will now bound the error of on the clean distribution D. To this end, we first note that the empirical error of h on the clean samples Setn is, with high probability. close to the error D, since |Scn is large enough and is polynomial threshold function of degree at most It therefore, suffices to bound the error of h Sein We have the following.
P Iy + h(x)]
1
Σ
1 + h(x)) +
Σ
1 + h(x))
(xe1))-Bet
m
(x.1)~BBla Sra.
1
Σ
1 h(x))
SSen \ Saul
(G.7)
(x.I)
Sale
The second term the bound above can bounded by e/3, due to part of Theorem 3.2. remains to bound the first term.
Consider f* C be the concept in class C with minimum error on Salt i.c. we have that f = arg sec I' (x..)) [y * fx)].. Note that there is some f' E that makes at most M optootll errors the whole input dataset Smp- due to the definition of opt (see Definition 1.4). We have that P (a. [y * f (x)) < (x. [y # f(()) < M opt SSntl
33

---

Moreover, let Pup- Prown be the sandwiching polynomials for for and p- Pup -down which is
720
non-negative polynomial with [lx()] T2Q Due to part of Theorem 3.2, the expectation of p under San is at most em i.e., Ex i PPup (x) Pdown xx) 3/Smar
e²
em Since Pup 2 f 2 Pdown 3|Snte]
we also have that
E (x) Pdown (x)]] X-
cm
3|Smm|
We now observe that / is the output of the & polynomial regression algorithm on Sätt and, therefore, according to Theorem A.3 by [KKMS08], overall have the following bound
M
P
wy
h(x))
optiotal
(x.))~Sa
San
3 3
which implies the desired bound:
Σ
1 h(x)) S
M
cotal + em
S optlooall + t
(G.8)
2
(xm
The result follows by combining Eq. (G.7) and (G.8).
Remark G.1. Our result on HC-learning highlights the following analogy:
Learning with heavy contamination can be thought of as a version of testable agnostic learning (Definition H.1), where the algorithm is asked to find subset of the input that is structured enough, instead of merely verifying whether the whole input structured.
Similarly, in the context of learning with distribution shift, PQ learning [GKKM20] requires finding subset of unlabeled test dataset where the learner is confident in its predictions, while TDS learning [KSV24b] aims to verify whether the whole unlabeled test dataset is drawn from some distribution that similar the one the learner has trained on.
In [GSSV24], shown that by using a spectral iterative filtering algorithm, TDS learning results can be extended to PQ learning. Here, we complete the analogy by showing that our iterative filtering algorithm can extend known results from testable learning (i.e., that sandwiching is sufficient, see [GKK23]) to HC-leaming.
Remark G.2. One could define hybrid model where bounded fraction of clean points are replaced adversarially and proportionally large number of adversarial points are then added. Our results should apply to this setting as well, but we focus on BC and HC learning separately for simplicity of presentation.
H Applications to Tolerant Testable Learning
We give new results for testable learning [RV23] and tolerant testable learning [GSSV24).
Definition H.1 (Tolerant Testable Learning [GSSV24[). An algorithm A is tolerant tester-learner for C C (X' + {+1}} with respect some target distribution D* over X' if on input (c. T, Simp), where C, T, 8 E 10, and Simp is of i.i.d. examples from some arbitrary distribution D, the algorithm A outpuls either oulputs Reject or oulputs ( (Accept, h), where h h: X - {+1} such that with probability al least ô over Simp, and the randomness of A, the following conditions hold.
1. (Soundness) Upon acceptance, the error of h is bounded as follows:
P [y # h(x)) < min
P IV + + (x.I)~D
(x.I)>~D
FEC
2. (Completeness) dry (D, & where D is the marginal of DD on X, then A accepts.
The sample complexity of A is the minimum number of examples required to achieve the above guarantee.
34

---

Previous work by [GSSV24] showed that the existence of L2 sandwiching polynomials with bounded coefficients, i.e., polynomials Pup- Pdown such that Ex-D-1(Ppp (x) Paown Paown(x))3 (x))²] S eimplies toler- ant testable learning. Here, we relax this condition to L1 sandwiching polynomials (Definition 4.3), without requiring any bound on the coefficients. Note that even for non-tolerant testable learn- ing, where L1 sandwiching is known to suffice [GKK23], all prior work required bounds on the coefficients.
Theorem H.2 (Sandwiching implies Tolerant Testable Learning). Let c, E (0. 1) and Q 2 1. Let D' be some A-hypercontructive distribution over d-dimensional space and let be a concepl class whose cil+t/e; -sandwiching degree w.r.t. 'D" is & for some large enough constand C 2 1. Then, there is an (e, - rester--llrr for C w.r.t. "D* with runtime poly(A (1o((1/0)) (d+ 1/ee, and sample complexity at most 2 O(Ad)a l. 3.
The following corollary follows from Theorem H.2, combined with the fact that log-concav dis- tributions are hypercontractive (see [Bob01]). as well the results of [KM13, KKM13] the sandwiching degree of functions of halfspaces (see Appendix C.2). This is the first result for testably learning even single halfspace with respect to log- log-concave distributions up optimal error.
Corollary H.3. Let C be the class of arbilrary functions of k halfspaces over I& and let DD be any log- (og-concave distribution. There is an (e, 8, r)-tteter--leame for C with respect to D* that runs in time (dlog((/8)) where i cxp((log(log(H) (k) (E²)
We will now prove Theorem H.2, using once more the iterative polynomial filtering algorithm of Theorem 3.2.
Proof of Theorem H.2. The algorithm receives dataset Simp. draws reference set Sref of m (C' Ad) (log 1) 4 i.idd. unlabeled examples from D, where C' 2 1 is sufficiently large universal eb constant and does the following.
1. First, the algorithm runs the filtering procedure of Theorem 3.2 (that is, Algorithm 1) on input (Smp: Stef, m = [Smpl dr
2, c/8) to form the filtered dataset Sate-
2. Then, the algorithm checks if m |Stte] < (r + e/2)mm and rejects if the inequality does not hold.
3. Otherwise, the algorithm finds polynomial p of degree at most l that minimizes the following convex objective.
p arg min (xtt)~Stt
E ll p(x)]]
s.t. p has degree at most f
4. The algorithm outputs hxx) = sign(p(x)+ where f E R minimizes the miedimmnsional objective PP (x..)))mm [y (f() + +]] over E RR
Soundness. Suppose, first, that the algorithm accepts. Observe that [.mpp \ SStel |Sinp - |5mt since Smn. C Smp-- Since the algorithm has accepted, we know the following.
Smpl - 1mmil = m - Satel I m(( + e/2)
Recall that Simp of m i.i.d. examples from the input distribution D. Since large enough, due to standard VC dimension arguments (and the fact that is a polynomial threshold function of degree at most f), we have that with high probability:
P (x
wV * h(x))
P
IV + h(x)) 6/4
(H.1)
(x. (x.
35

---

Therefore, it suffices to show bound on the empirical error of h on Smp- We have the following:
P 1 + h(x))
Σ
1 h(x)} +
Σ
1/ + h(x))
(x.
(x.y) Suu Snii
(x.))E8mi
< Stap
&Satel
+
P (x,2)>-SEi
w h(x)]
S
P -aa))-an
ly + h(x)]
m
suffices to show that (x.,)>~Biie [y X [(x)
(minsec P ((x))~D' + 1((x)] + t/4). Let
Saa
I be the function that minimizes the error on D and let Pup: Proon be its 128r sandwiching polynomials, Then according to part 2 of Theorem 3.2, and since for Pup Pdown we have Ex~D[p(x)] S 128r+646' we obtain:
SSadl E X--Smit
[xup(x) Pelowu (x)
Σ (Pup - Pdowa (x)) - XESaI.
cm 8
Therefore, we also have Ex [1f Pdown(x)) S Ex [Pup(X) Pdown (x)] S cm
8|Sas
Observe, now that is the output of the low-degree polynomial regression algorithm and, hence, according to Theorem A.3 by [KKMS08], we have the following.
Iv + h(x)] (x.
P
IU [x)) +
em
(x,y) (Sn
Sanl
To conclude the argument, observe IP (x..))~San. (v (x)) SSatel
(x.,) # (x)), since
Sate S Simp and, due to Hoeffding bound, with high probability we have (x.w) ly + [*)x s P(x.))~D ly # (x)) c/8. Note that due the choice of f", we have P. (xx # [x))
minfec P (xa))>bl # [xx] =: opt. Overall, we have the following bound:
[y # h(x)] S opt + r + 3E/4,
(x.y)>~Smmp
which, together with the generalization bound of Eq. (H.1) implies the soundness of the algorithm.
Completeness. We will now show that the algorithm accepts with high probability whenever dDv (D, < r. It suffices to show that [Smp Saul S (r + e/2)m with high probability, since [Siup \ Smul = m - [Sauel which exactly the quantity based upon which the algorithm decides whether to reject not.
Let Sai = (x(1) x(() xx.,))..,x(m)) xmm)
set of m i.i.d. examples drawn from D. Let Simp be drawn as
follows:
For each i [m]. draw an independent Bernoulli random variable & with probability of success 1 - 7.
If & 1, then let z x
If E: = 0, then draw (6) independently from the residual distribution D' in the maximal coupling between and D* (i.e., the joint distribution (x, x*) that has marginals D and D respectively and maximizes the likelihood that x = x").
Let San (z( )i(m))-
Note that the distribution of each ( is DD' and they drawn independently. Due Chernoff bound, since m is large enough, we have that, with high probability, |Smp \ "Smml & m(( + c/8). According to Theorem 3.2, we have the following, with high probability:
[(Suup n Sem) \ Saul < R |Siu \ Smul + cm
8
36

---

Observe, now, that |Siup \ Smul = mSSmp n Sela)) \ Smn + |Smpp) \ Sclal- Therefore, if we solve for
[Sip \ Satl we have the following
(1 R- -1Supp \ Saul
1Smp Selal
em
8 m(T c/4)
Due to the choice of R, we have the desired bound |Stmp \\ Saul - m( + e/2).
37


Reviews:
[{"review_id": "GnMsalk113", "reviewer": "Reviewer_E9uM", "summary": "They propose efficient supervised learning algorithms under contamination where both labels and covariates are adversarialy corrupted. Here, a learner has access to a potentially heavy contaminated dataset and the goal is to learn a model that performs well on some clean underlying distribution.\n\nThey propose an outlier removal algorithm called iterative polynomial filtering in the supervised setting.\n\t-  They show any function that can be approximated by low-degree polynomials can be efficiently learned under bounded noise contamination. Here, the learner receives a dataset with bounded contamination and the goal is to output a classifier that enjoys approximately optimal error guarantees on the clean underlying target distribution. \n\t\n\tThis solves a long-standing gap between the complexity of agnostic learning and learning w contamination.\n\t\n\t- If a function class admits stronger notion of sandwiching approximators, they obtain near-optimal learning guarantees even in the heavy-contamination case in the case of supervised learning binary classifiers.\n\n\n\nFor learning with bounded contamination (BC-learning), their algorithm runs in two phases: 1- run an outlier removal algorithm. 2. construct a predictor based on the polynomial \\hat{p} with smallest \\ell_1 error on the filtered set from step 1.\n\nThe main idea of their alg is the outlier removal algorithm and it comes from bounded-degree outlier removal procedures from robust learning and learning with distribution shift. The idea is that one can iteratively find polynomials that violate the desired condition over the input set and use them to filter the input points. More specifically, the algorithm removes the points that give such polynomials values larger than a threshold. After this step, they can ensure the outliers remaining are not dangerous when moving to step 2.", "questions": "Table 1, is the caption as intended? I am confused which one is the lower bound and which one is the upper bound?\n\nIn Alg 1, what is the size of \\cal{P}? In line 5, how can you compute p* efficiently?\n\nTheir algorithms require sample access to the target distribution D^*. What is the main challenge in order to relax this assumption?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: I am mostly familiar with robust learning (when the features do not change) and outlier detection in unsupervised learning and not very familiar with this line of work. Their problem is challenging since both labels and covariates can be adversarially corrupted. Furthermore, the heavy-contamination results are also interesting and they also build-up on their filtering algorithm. They propose a new model for learning binary classifiers with heavy additive contamination that outputs a single hypothesis with a strong error guarantee under the clean distribution.\n\nIn terms of weaknesses, the runtime of their algorithm is pretty huge, but the gap between lower and upper bound is not too large (table 3).", "was_revised": true, "final_justification": "After going through the rebuttal and other responses, I agree that this is a strong set of results and would be happy to see it gets accepted.", "rebuttal": "We thank the reviewer for their constructive feedback and for appreciating our work. \n\nIn table 1, we present the upper bounds using big-$O$ and the lower bound for monotone functions (last row, last column) using $\\Omega$. We will modify the caption to make this clear in future revisions.\n\nComputing $p^*$ corresponds to a convex program over the space of coefficients of degree-$\\ell$ polynomials. In particular, the objective function is linear, and $\\cal{P}$ is a convex set defined by a polynomial number of linear constraints plus one quadratic constraint. See lines 869–873 in the submission (proof of Theorem 3.2) for a relevant discussion on the algorithmic implementation.\n\nWe believe that obtaining an outlier-removal algorithm that works universally over a wide family of distributions is an important direction for future work (see lines 356–360). There are several challenges towards achieving this:\n1. First, the problem is non-trivial even from an information-theoretic perspective. Barring any computational considerations, one needs to be able to control the number of clean points that are removed by the filtering algorithm. However, it is unclear when this is possible for infinite-sized families of target distributions (e.g., the family of all isotropic log-concave distributions). \nOne special case where this issue can be resolved is for concept classes with the following universal approximation property: for each function in the class, there is a low-degree approximator that works with respect to all distributions within a wide family.\n\n\n2. Second, even if one could show such a universal approximation property, it is not clear how to express the universal approximation (or an appropriate relaxation thereof) as a convex constraint. To this end, the sum-of-squares framework could be useful, but none of the known results from the sum-of-squares literature seems to directly apply to our setting."}, {"review_id": "tqfT58n9h7", "reviewer": "Reviewer_Pive", "summary": "The paper presents an outlier removal algorithm called iterative polynomial filtering and its applications to learning under contamination. Specifically, the authors address the nasty noise setting and the heavy contamination setting.", "questions": "1. In Table 1, it says that the table has upper and lower bounds, but it is not clear which numbers are which. I suppose that all are upper bounds except for the 2-Heavy contamination result for monotone functions?\n2. In practice, how does one select a class of polynomials P? I understand that this is a theoretical paper. However, the algorithm is interesting and it would be nice if there were some discussion on practical implementation.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper is well-written and the mathematics appears to be rigorous. The authors have discussed a good amount of related work.\n2. The problem that the paper tries to solve (learning with nasty noise and learning with heavy contamination) is a problem with significant interest in the field. There are many past works on this problem and it is hard, so solving it is meaningful.\n3. The approach is applicable to various settings, leading to matching bounds to prior results or extending to novel settings.\n\n**Weaknesses:**\n\n1. The introduction and related work sections are fairly long, going up to page 6. The paper uses terms such as \"polynomial p\" and \"polynomial approximator\" early on, but the definitions for these concepts appear quite late in the paper (page 8). It would be helpful for readers if the paper could briefly describe these definitions in the introduction, or at least point to where the definitions can be found.\n\n2. As discussed in the future work section, the filtering algorithm requires access to the clean unlabeled data distribution D*, and the number of samples we need could be large. I am not sure if this is feasible in practical settings. If we have labeled data with some contamination, usually the unlabeled dataset could be contaminated as well. To clean the dataset, one has to know whether a sample is drawn from the target D* or not. If there is an algorithm to do that, then we can also use it to clean the labeled dataset. Otherwise, we may need humans to clean up the dataset, which may not be possible, especially in high-dimensional settings, or it could be expensive. However, as a first step toward solving this problem, this is a minor point.", "was_revised": true, "final_justification": "I thank the authors for their rebuttal, which has addressed the questions raised in my initial review. After consideration, I will keep my score as is.", "rebuttal": "Thank you for your time and appreciation of our work! We are happy to incorporate your suggestions in future revisions of our paper.\n\n**Access to unlabeled examples:** We would like to point out that one does not always need to know whether the clean distribution corresponds to the target $D^* $, at least in the bounded contamination case. In particular, we may first fix a target distribution of interest $D^* $ of our own choosing, and form an algorithm that is guaranteed to either produce a low-error hypothesis under the clean distribution, or certify that the clean distribution is far from $D^* $. In other words, this algorithm would work in the testable setting, meaning that it does not require any assumptions on the clean distribution, at the cost of potentially refusing to provide a solution, but only if the clean distribution happens to be far from $D^* $.\n\nTo achieve this type of guarantee, it suffices to raise a flag if the outlier removal with respect to $D^* $ removes more than an $O(\\eta)$ fraction of the input examples. Since $D^* $ is chosen by the learner, we can generate our own samples, for example by using random coin flips. \n\nThe proof of correctness for this method follows the approach of Section H, where we show that our iterative polynomial filtering can be used to solve the tolerant testable agnostic learning problem. We did not define the testable version of BC-learning for clarity of presentation, but the proofs of Section H can be generalized to the BC setting as well.\n\nNevertheless, we agree that designing algorithms that work universally with respect to wide families of distributions (and, hence, lead to testable algorithms that accept more often) is a concrete and important direction for future work.\n\n\n**Answers to questions:**\n\n**Q1.** You are correct that the only lower bound in Table 1 is in the cell of the last row and last column. We will make this clear in future revisions.\n\n**Q2.** The choice of the class of polynomials is characterized by two hyperparameters, the degree $\\ell$ and the excess error rate $\\epsilon$. If one is interested in achieving information-theoretically optimal guarantees (e.g., error $2\\eta$ in the BC case), then the choice of $\\ell$ should be as high as possible, depending on the computational budget of the learner. The hope would be that $\\ell$ is large enough so that the ground truth can be approximated by degree-$\\ell/2$ polynomials. \n\nMoreover, the error of the output hypothesis on the filtered set is an accurate proxy for its error on the clean distribution, as long as the number of removed points during filtering is small. Both of these quantities can be estimated efficiently, and, therefore, one can verify whether the choice of $\\ell$ is large enough.\n\nOn the other hand, if the learner can only afford small values for $\\ell$ (e.g., $\\ell=1$ or $2$), then it would be preferable to follow approaches of prior work on BC learning (see, e.g., [DKS18a], citation in lines 481–483). These works give guarantees for BC learning of geometric classes (like halfspaces or intersections thereof), through constant-degree polynomial filtering. For a comparison between our filtering algorithm and the one used in [DKS18a], see our response to Reviewer b2ov. \n\nThe caveats are that (1) these methods can be significantly less robust to contamination compared to ours and (2) they only seem to work for special classes. Therefore, their methods would only provide meaningful results if the contamination rate is small enough, and the ground truth lies within a structured concept class. One interesting direction for future work is extending these methods to the case of heavy contamination, when $\\mathrm{opt}_{\\mathrm{total}}$ takes small values."}, {"review_id": "CO1P2QicVn", "reviewer": "Reviewer_b2ov", "summary": "This paper introduces a outlier removal algorithm called Interactive Polynomial Filtering and showcases its application in supervised learning with contamination.\n\nThe paper also provides guarantees for learning whenever the distributional assumptions are met (hypercontractivity) and: (a) under bounded contamination (BC), guarantee error at most $2\\eta + \\epsilon$. [Theorem 4.2] (b). under heavy contamination (HC), guarantee error at most  $Q \\cdot opt_{total}+\\epsilon$. [Theorem 4.4]", "questions": "Would the authors mind sharing a quick comparison of their algorithm with the iterative filtering method from [DKS18a]? In particular, what are the main similarities and differences?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The paper has some very interesting results and contributions to the field of tolerant testable learning and robust learning with contamination.\n2. The paper is well-written and the authors did a great job discussing previous works as well as how this paper fits with related literature.\n3. Overall the presentation of the paper is good and the paper was very enjoyable to read :)\n\nWeakness:\n\nI think there is no obvious weakness in general.", "was_revised": true, "final_justification": "I thank the authors for thoroughly addressing my questions. Overall, I think this is a well-written paper and hoping to see it at the conference.", "rebuttal": "We wish to thank the reviewer for their positive feedback and comments!\n\nThe main differences between our outlier removal algorithm and the one of [DKS18a] are twofold: \n\n1. First, their algorithm only preserves the expectations of squared polynomials, whereas ours preserves the expectations of arbitrary polynomials with small absolute expectations under the target distribution. Note that a bound on the absolute expectation of a polynomial does imply a bound on its squared expectation via hypercontractivity (see Definition 3.1); however, the resulting bound incurs a multiplicative factor that is exponential in the degree of the polynomial. \n\n2. Second, our bounds on the polynomial expectations over the filtered set are independent of the degree of the polynomials, while the bounds of [DKS18a] scale exponentially with the degree $\\ell$ of the polynomials. \n\nBoth of these improvements are crucial in our setting, because the polynomials we are interested in have degrees that are tied to their approximation properties. In particular, applying the results of [DKS18a] directly would introduce a race condition between the approximation quality $\\epsilon$ and the degree $\\ell$.\n\nSee also lines 167–178 in the submission."}, {"review_id": "CYCQ5D2J0p", "reviewer": "Reviewer_bEh6", "summary": "The paper studies the efficient learnability of families of concept classes and distributions when the training data is adversarially contaminated.\nSpecifically, in the bounded contamination setting (the \"nasty noise\" model), a fraction of the training set is removed and replaced by an adversarially chosen set of labeled examples. Notably, the noise affects not only the labels but also the examples (i.e., the covariates).\nIn this model, the authors present an algorithm that significantly improves the running time for natural concept classes (such as intersections of halfspaces, circuits, etc.) and distributions (such as uniform and Gaussian).\nIn many cases, the running time matches the best-known results for settings where the contamination affects only the labels.\n\nMoreover, the authors introduce a more challenging contamination model (\"heavy contamination\"), in which the adversary is allowed to add corrupted points to the training set. As in the previous model, the algorithm achieves non-trivial results, although with increased running time.\n\nBeyond the results themselves, a notable contribution is the algorithmic technique of iteratively removing outliers, applied to concept classes that can be approximated by low-degree polynomials with respect to a hypercontractive distribution.", "questions": "For the bounded contamination (BC) setting, you assume that the clean distribution is realizable, whereas in the heavy contamination setting, it can be agnostic. Is there a specific reason why the BC model would not work similarly if the clean distribution were not realizable?\n\nAre the parameters $\\eta$ and $Q$ assumed to be known in advance? I couldn't find a clear statement.\n\nLines 36–37: \"all known near-optimal error guarantees for agnostic learning (that can be achieved efficiently) can indeed be extended to the setting of contamination.\"\nIn the agnostic model, the results are typically stated with respect to OPT, while in the contamination model the bounds are with respect to 2OPT (i.e., \"semi-agnostic\"). Is the quoted statement accurate, or did I miss a nuance?\n\nLines 52–53: \"It is known that achieving an error better than twice the contamination rate is, in general, impossible.\"\nIs this impossibility result referring to any algorithm (including inefficient ones)? It might be helpful to clarify.\n\nTable 1: What does the notation $O_k(1)$ mean? Do you mean that the bound hides constants depending on $k$?", "limitations": "Limitations are discussed in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper makes strong contributions to efficient supervised learning under contamination, both by improving many known results and by introducing an interesting algorithmic idea.\nI believe the paper is a good fit for the conference, and I would be happy to see it accepted.\n\nI did not identify any specific weaknesses.\nI am not fully familiar with recent techniques in learning under distribution shifts and unsupervised contamination. If there are similarities with those approaches, it might be helpful for the authors to highlight and discuss them.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments, and for appreciating our work! We will incorporate your feedback in future revisions.\n\nFor a comparison to previous outlier removal techniques, see lines 167–178 in the submission, as well as our response to Reviewer b2ov.\n\n**Answers to questions:**\n- The reason we consider the clean distribution to be realizable in the BC setting is to be in line with the classical definition of learning with nasty noise. However, our approach generalizes to agnostic BC learning. See also Definition E.1 in Appendix E, for a formal definition.\n- For BC learning, we do not need to know $\\eta$. For HC learning, we do require an upper bound on the contamination ratio $Q$, in order to tune the hyperparameters of the iterative polynomial filtering algorithm. See also Definitions 1.2 and 1.4, where we describe the input of a BC learner (which does not include $\\eta$), and the input of an HC learner (which does include $Q$).\n- In lines 36–37, we use the term “optimal” to refer to the information-theoretically optimal guarantee, which, in the BC case, is $2\\eta$. Thank you for pointing out this ambiguity. Note that no algorithm (even an inefficient one) can achieve error better than $2\\eta$ under bounded contamination in the general case.\n- The notation $O_k(1)$ hides an arbitrary function of $k$, which is a constant when $k$ is considered constant. See also line 775."}]

Author rebuttal:

Meta-review: The authors consider the problem of efficient supervised learning with nasty noise. This problem is less studied in the literature (unlike supervised learning under label noise or unsupervised learning with adversarial contamination) but is quite important and interesting. Under distributional assumptions (such as Gaussian marginal, etc) and for certain interesting concept classes related to polynomials, the authors propose algorithms for learning under bounded contamination. These results match those of the easier model of label noise. The authors also go beyond this, and leverage the testable learning framework to make sure that the distributional assumptions are actually met.

This work is inspired by recent line of work on testable learning under distribution shift where the authors propose an iterative filtering approach to learning with contamination. They use this algorithm to show multiple results including (i) the first efficient algorithms for tolerant testable learning of halfspaces with respect to a log-concave distribution and (ii) an efficient method to learn any function class that can be approximated by low-degree polynomials with respect to a hypercontractive distribution under nasty noise. 

This work offers a fresh view on the important problem of robust supervised learning, offering algorithmic and theoretical contributions on this important problem. The work would likely have significant impact on the theoretical ML community.
Decision: Accept (spotlight)