Efficient Testable Learning of Halfspaces with Adversarial Label Noise
Authors: Ilias Diakonikolas
Daniel Kane
Vasilis Kontonis
Sihan Liu
Nikos Zarifis
Venue: NeurIPS 2023 poster (2023)
Keywords: Machine Learning
TL;DR: We give an efficient active tester-learner pair for halfspaces in the testable learning framework defined by Rubinfeld and Vasilyan (2022).

Abstract: We give the first polynomial-time algorithm for the testable learning 
of halfspaces in the presence of adversarial label noise under the Gaussian distribution. In the recently introduced testable learning 
model, one is required to produce a tester-learner such that if the data passes the tester, then one can trust the output of the robust learner on the data. Our tester-learner runs in time $\text{poly}(d/\epsilon)$ and outputs a halfspace with misclassification error $O(\text{opt})+\epsilon$, where $\text{opt}$ is the 0-1 error of the best fitting halfspace. At a technical level, our algorithm employs an iterative soft localization technique enhanced with appropriate testers to ensure that the data distribution is sufficiently similar to a Gaussian. Finally, our algorithm can be readily adapted to yield an efficient and testable active learner requiring only $d ~ \text{polylog}(1/\epsilon)$ labeled examples.

Efficient Testable Learning of Halfspaces with Adversarial Label Noise
Ilias Diakonikolas
Daniel M. Kane University of California, San Diego dakane@ucsd.
University of Wisconsin, Madison iliasOcs. wisc.
Vasilis Kontonis
Sihan Liu
University of Texas, Austin mailto:vasilisn utexas.
University of California, San Diego
i10460ucsd.
Nikos Zarifis
University of Wisconsin, Madison zarif earifis@visc.edu
Abstract
We give the first polynomial-time algorithm for testable learning halfspaces in the presence of adversarial label noise under the Gaussian distribution. In the recently introduced testable learning model, one is required to produce tester- learner such that if the data passes the tester, then one trust the output of the robust learner on the data. Our tester-learner runs in time poly(d/e) and outputs halfspace with misclassification error (oopt) + c, where opt is the 0-1 error of the best fitting halfspace. At a technical level, our algorithm employs an iterative soft localization technique enhanced with appropriate testers to ensure that the data distribution is sufficiently similar to Gaussian. Finally, our algorithm can be readily adapted yield efficient and testable active learner requiring only d poly /e) labeled examples.
Introduction
A (homogeneous) halfspacc is a Boolean function h RR + [+:1} of the form (x((x) = sign (w x).
where w E IRd the corresponding weight vector and the function sign IR - {=1} is defined as sign(t) 1 i 2 ( and sign(t) = -1 otherwise. Learning halfspaces from random labeled examples a classical task machine learning, with history going back to the Perceptron algorithm [Ros58]. In the realizable PAC model [Va184] (i.e., with consistent labels), the class of halfspaces is known be efficiently learnable without distributional assumptions. On the other hand, the agnostic (or adversarial label noise) model [Hau92, KSS94) even weak learning is computationally intractable in the distribution- setting [Dan16, DKMR22, Tie22].
These intractability results have served as motivation for the study of agnostic learning in the distribution-specifi, setting, i.c., when the marginal distribution on examples is assumed be well- behaved. In this context, number of algorithmic results are known. The L₃ regresssio algorithm of [KKMS08] agnostically learns halfspaces within near-optimal 0-1 error opt + e, where opt is the 0-1 error of the best-fitting halfspace. The running time of the L2 Le-rgression algorithm is (((1/e)) under the assumption that the marginal distribution on examples the standard Gaussian (and for a few other structured distributions) [DGJ+ 10, DKN10J. While the L1 regression method leads to improper learners, a proper agnostic learner with qualitatively similar complexity was recently given
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in [DKK 21]. The exponential dependence on 1/c in the running time of these algorithms is known be inherent, in both the Statistical Query model [DKZ20, GGK20, DKPZ21] and under standard cryptographic assumptions [DKR23].
Interestingly, it is possible to circumvent the super-polynomial dependence on 1/c by relaxing the final error guarantee namely, by obtaining a hypothesis with 0-1 error f(opt) +e, for some function f(t) that goes when - 0. (Vanilla agnostic learning corresponds the case that f(t) = t.) A number of algorithmic works, starting with [KLS09], developed efficient algorithms with relaxed error guarantees; see, e.g., [ABL17, Dan DKS18, DKTZ20b). The most relevant results in the context of the current paper are the works TABL17, DKS18) which gave poly(d/c) time algorithms with error Copt + c, for some universal constant C 1, for learning halfspaces with adversarial label noise under the Gaussian distribution. Given the aforementioned computational hardness results, these constant- factor approximations are best possible within the class of polynomial-time algorithms.
drawback of distribution-speciffi agnostic learning is that it provides no guarantees if the assumption on the marginal distribution on examples is not satisfied. Ideally, one would additionally like an efficient method to test these distributional assumptions, so that: (1) if our tester accepts, then we can trust the output of the learner, and (2) it is unlikely that the tester rejects if the data satisfies the distributional assumptions. This state-of-affairs motivated the definition of a new model - introduced
in [RV23] and termed testable learning formally defined below:
Definition 1.1 (Testable Learning with Adversarial Label Noise [RV23]). Fix E (0, 1] and let f: (0, 10,1] B4. A tester-learner A (approximately) testably learns a concept class C with respect to the distribution Dx on R with N samples, and failure probability if the following holds. For any distribution D on R x {=1]. the tester-leamner A draws a set S of N i.i.d. samples from D. In the end, either rejects S or accepts and produces hypothesis h Rd >> (+1}. Moreover, the following conditions must be met:
(Completeness) If D truly has marginal Dx. A accepts with probability at least 1-
* (Soundness) The probability that A accepts and outputs hypothesis h for which Pr(xai>D + yl f(opt) +c, where opt == mingec Pr(xa))Dlg((x) # yl is at most T.
The probability in the above statements is over the randomness of the sample S and the internal randomness of the tester-learner A.
The initial work [RV23] and the followup paper [GKK22] focused on the setting where S(1) (i.e., achieving optimal error of opt + <). These works developed general moment-matching based algorithms that yield testable learners for range of concept classes, including halfspacces. For the class of halfspaces in particular, they gave testable agnostic learner under the Gaussian distribution with sample complexity and runtime d((1/c²) essentially matching the complexity of the problem in the standard agnostic PAC setting (without the testable requirement). Since the testable lcarning setting is at least as hard as the standard PAC setting, the aforementioned hardness results imply that the exponential complexity dependence in 1/c cannot be improved.
In this work, we continue this line of investigation. We ask whether we can obtain fully polynomial time testable learning algorithms with relaxed error guarantees ideally matching the standard (non-testable) learning setting, Concretely, we study the following question:
Is there poly(d/e) time tester-learner for halfspaces with error (optt + e?
Specifically, is there a constant-factor approximation?
As our main result, we provide an affirmative answer to this question in the strongest possible sense by providing an efficient constant-face approximate tester-learner.
Labeling examples often requires hiring expert annotators, paying for query access to powerful language models, etc. On the other hand unlabeled examples are usually easy to obtain in practice. This has motivated the design of active learning algorithms that, given a large dataset of unlabeled examples, carefully choose small subset to ask for their labels. A long line of research has studied active learning of halfspaces under structured distributions either with clean labels or in the presence of noise [BBL06, BBZ07, 1L1 ABL17, She21].
In principle, testable learners could only rely on unlabeled examples during their "testing phase" in order to verify that the x-marginal satisfies the required properties; and, assuming that it does so,
2

---

proceed to rum an active learning algorithm. However, as the testing process is often coupled with the downstream learning task that depends on labeled examples - is an interesting question to investigate the design of testable learners in the active learning setting.
Definition 1.2 (Testable Active Learning). A tester-leamnr has sample complexity N and label complexity q in the active learning model if it draws N unlabeled samples from Dx. i.e., the x- marginal of D over TR.,, and queries the labels of at most q samples throughout its computation.
Main Result Our main result is the first polynomial-time tester-learner for homogeneous halfspaces with respect the Gaussian distribution in the presence of adversarial label noise. Formally, we establish the following theorem:
Theorem 1.3 (Testable Active Learning Halfspaces under Gaussian Marginals). Let 6, T E (0,1) and C be the class of homogeneous halfspaces on RR. There exists a tester-learner with sample complexity N = poly (d, 1/e) log(1/T) and runtime poly(d N) for C with respect to (0, 1) up to 0-1 error (opt)) + e, where opt is the 0-1 error of the best fitting function in C. that that fails with probability at most In addition, in the active learning model, the algorithm has sample complexity N and label complexity q = Ö((d log(1/e) + log" log(L/T))
Before we provide an overview of our technical approach, some remarks are in order. Theorem 1.3 gives the first algorithm for testable learning of halfspaces that runs in poly(d/c) time and achieves comeensioninndpendern error (i.e., error of the form f(ppt + e, where f satisfies lim;-0 f(t) 0.) Moreover, the constant-factur approximation achieved is best possible, matching the known guarantees without the testable requirement and complexity lower bounds. Prior known result in the testable setting, due to [RV23, GKK22], achieves error opt + e with complexity d A novel (and seemingly necessary) feature of our approach that the testing components of our algorithm depend on the labels (as opposed to the label-oblivious testers of [RV23, GKK22J). As will be explained in the proceeding discussion, to prove Theorem 1.3 we develop a testable version of the well- localization technique that may be of broader interest.
work, the only
Independent Work In concurrent and independent work, [GKSV23] gave an efficient tester- learner for homogeneous halfspaces under the Gaussian distribution (and strongly log-concave distributions) achieving cimension-indepeneee concave distributions, their algorithm achieves error O O(k2/2opt111/4 with sample complexity and running time of (d) (1/)))())). That is, they obtain error O(opt)), where < is a universal constant, in poly. (d/e)) time; and error (opt)) in quasi-polynomial (d//))ooylog(() time. For the Gaussian distribution, they achieve error O(opt) with complexity poly(d, 1/e). We remark that since the learner in [GKSV23] corresponds to the stochastic gradient descent algorithm from [DKTZ20b], which requires labeled sample in every iteration, it is not clear whether their approach can be made label-efficient.
error guarantees. Specifically, for strongly log-
1.1 Overview of Techniques
Our tester-learner is based on the well-known localization technique that has been used in the context of learning halfspaces with noise; see, e.g., [ABL17, DKS18J. At a high-level, the idea of localization hinges on updating given hypothesis by using "the most informative" examples, specifically examples that have very small margin with respect to the current hypothesis. Naturally, the correctness of this geometric technique leverages structural properties of the underlying distribution over examples, namely concentration, anti-concentration, and iii-anti-conneetratiinn properties (see, e.g., [DKTZ20a]). While the Gaussian distribution satisfies these properties, they are unfortunately hard to test. In this work, show that localization can be effectively combined with appropriate efficient testing routines to provide an efficient tester-learner.
Localization and a (Weak) Proper Testable Learner Assume that we are given a halfspace defined by the unit vector w with small 0-1 error, namely Prx-D, (ww..dssssiivvv>>> xx) * big(w-xx). < 5, for some small 8 > O, where v² is the unit vector defining an optimal halfspace. The localization approach improves the current hypothesis, defined by w, by considering the conditional distribution D' on the points that fall in thin slice around w, i.e., the set of points x satisfying |W x S 06)). The goal is to compute new (unit) weight vector w' that is close an optimal halfspace, defined by v", with
3

---

W
(8)
(ii
Figure The disagreement region between halfspace with normal vector w and the target v is shown in green. The unit direction u corresponds to the projection of v* on the orthogonal complement w. We assume that the &g distance of the two halfspaces is (and thus their angle is (6))) Since the slabs S; = {id s xx w| s (i+ 1)63 have width 6, the z-coordinate of the start of the i-th box (i).
respect to D', i.e., Pr [sign(v* x') A sign(w'. -x'] S for an appropriate a > O. We can then show that the halfspace defined by w' will be closer to the target halfspacc (defined by v²) with respect to the original distribution, i.e., we have that Prx-D, [sign(v" x) & sign(w' w'.x x)] I ((8)). By repeating the above step, we iteratively reduce the disagreement with v* until we reach our target error of (opt). Similarly to [DKS18] instead of "hard" conditioning on a thin slice, we perform "soft" localization step where (by rejection sampling) we transform the x-marginal to Gaussian whose covariance is (88)) in the direction of w and identity the orthogonal directions, i... Σ = (1 8²) ww see Fact 3.2.
A crucial ingredient of our approach is proper testable, weak agnostic learner with respect to the Gaussian distribution. More precisely, our tester-learner runs in polynomial time and either reports that the X-marginal is not (0, or outputs a unit vector w with small constant distance to the target v", i.c. ||w- v"lla S 1/100; see Proposition 2. Our weak proper tester-learner first verifies that the given x-marginal approximately matches constantly many low-degree moments with the standard Gaussian; and if it does, it returns the vector defined by the degree-1 Chow parameters, i.e., c c= Exxx))) [yx]]. Our main structural result in this context shows that if Dx approximately matches its low-degree moments with the standard Gaussian, then the Chow parameters of any homogeneous LTF with respect to Dx are close to its Chow parameters with respect to (O, I). i... for any homogeneous LTF fxx, we have that Ex~Dx Lemma 2.3. Since the Chow vector of homogeneous LTF with respect to the Gaussian distribution parallel to its normal vector v (see Fact 2.2), it is not hard to show that the Chow vector of the LTF with respect to Dx will not be very far from v and will satisfy the (weak) learning guarantee of ||c - v212 < 1/100. Finally, to deal with label noise, we show that if x' has bounded second moments (a condition that we can efficiently test), we can robustly estimate Ex-D, [f (x)x] with samples from D up to error Optopt (see Lemma 2.4), which suffices for our purpose of weak learning. The detailed description of our weak, proper tester-learner can be found in Section 2.
[y
== Ex- [f (x" )x*]: see
From Parameter Distance Zero-One Error Having (weak) testable proper learner, we can now use it on the localized (conditional) distribution D' and obtain a vector w' that is closer to v in & distance; see Lemma 3.3. However, our goal is to obtain a vector that has small zero-one disagreement with the target halfspace v". Assuming that the underlying x-marginal is standard normal distribution, and that ||w - v*112 = holds that Prx~D, [sign(w w x) of sign(v" x)] = O6)) which implies that achieving fg-distance O(opt) + suffices. We give algorithm that can efficiently either certify that small l-2 fd-distance implies small zero-one disagreement with respect to the given marginal Dx or declare that Dx is not the standard normal.
The disagreement region of v and w a union of two "wedges" (intersection of two halfspaces); see Figure 1. In order for our algorithm to work, we need to verify that these wedges do not contain too much probability mass. Similarly to our approach for the weak tester-leaner, one could try a moment-matching approach and argue that if Dx matches its "low" "lowe-degree moments with N I), then small fgddittnnce translates to small zero-one disagreement. However, we will need to use this result for vectors that are very close to the target (but still not close enough), namely ||w v 8.

---

where 5 = ( this would require matching (1ly(1/6) many moments (as we essentially need to approximate the wedge of Figure I with polynomial) and would thus lead an exponential runtime of d
Instead of trying to approximate the disagreement region with a polynomial, we will make use of the fact that algorithm knows (but not v²) and approximate the disagreement region by union of cylindrical slabs. We consider slabs of the form S. = fx i0 If the target distribution is Gaussian, we know that the set |w . x > Aog(1/e has mass O()) and we can essentially ignore it. Therefore, we can cover the whole space by considering roughly
< w . < (i + 1)6).
M O( (oylog(1) (1/))//)///1/ /8) slabs of width d and split the disagreement region into the disagreement region inside each slab S.. We have that
M Σ
Pr [sign(w ww x) sign(v' x) x~Dx
Pr|ju- x /
x S. Pr[S.],
where u is the unit direction parallel to the projection of the target v onto the orthogonal complement of w. see Figure 1. By the anti-concentration of the Gaussian distribution we know that each slab should have mass at most (6)) Note that this is easy to test by sampling and computing empirical estimates of the mass of each slab. Moreover, assuming that underlying distribution is N (O, I), have that, conditional on S, the orthogonal direction u
(N, 1) (see Figure 1) and in particular u x has bounded second moment. We do not know the orthogonal direction u as it depends on the unknown V but we can check that, conditional on the slab S,, the projection of Dx onto the orthogonal complement of w is (approximately) mean-zero and has bounded covariance (i.e., bounded above by 21). Note that both these conditions hold when x ~ ~N(0, I) and can be efficiently tested with samples in time poly(d, (d. 1/5). Under those conditions we have that that Pr[s;] = O for all i. Moreover, when the conditional distribution on St (projected on the orthogonal complement of w) has bounded second moment, we have that Pr[[u x| 2 i S.] S ((1/f)) Combining the above, we obtain that under those assumptions the total probability of disagreement is at most (6). The detailed analysis is given in Section 3.1.
Obtaining an Active Learner. Our localization- based algorithm can be readily adapted to yield an efficient active learner-tester. We first observe that the tester that verifies that the parameter distance proportional to 0/1 error does not require any labels, as it relies on verifying moments of the x- x-marginal of the underlying distribution. During each iteration of localization, since the learner is only trying to find a constant approximation of the defining vector of the unknown halfspace, the learner only needs roughly (d) samples that fall in the slice we localize to. Since we can selectively query only the labels of samples that fall in the right region and the total number of iterations is In
at most ((log(1/<)) the labels needed to learn the defining vectors is roughly the end, the learner needs to find the best halfspace among the ones from Ollo(11/ /c)) localization iterations. We remark this can also be done with polylog (L/e) many label queries (see Lemma 3.6).
1.2 Preliminaries
We small boldface characters for vectors and capital bold characters for matrices. We use [d] to denote the set 21, .., d}. For vector x E Rd and E [d]. x4 denotes the i-th coordinate of x, and ||x||| = VId i= x² the &g norm of x. We use x y := Σm_ x,y; as the inner product between them. We use }{E} to denote the indicator function of some event E.
We use Ex=D[x] for the expectation of the random variable according to the distribution D and Pr[F]] for the probability of event F. For simplicity of notation, we may omit the distribution when it is clear from the context. For μ E Rdd Σ E Rddd we denote by [(,,, Σ) the d-dimensional Gaussian distribution with mean μ and covariance Σ. For (x, y) E X distributed according to D, we denote Dx to be the marginal distribution of x. Let f Rd + [+1] be a boolean function and D a distribution over Rdd, The degree-1 Chow parameter vector of f with respect to D is defined as Ex-D [x)x]. For a halfspace h(x) sign(v x). we say that is the defining vector of h.
Moment- Matching In what follows, we use the phrase "A distribution D on Red matches k moments with a distribution Q up to error A ". -iimilarly to [GKK22], we formally define approximate moment- matching as follows.
5

---

Definition 1.4 (Approximate Moment-Matching Let k E N be degree parameter and let M d)
be the set of d-variate monomials of degree up k. Moreover, let A E RlM((k,)) be a slack parameter (indexed by the monomials of M(k, d)), satisfying A = O. We say that two distributions D.Q match moments up to envor A if Ex-n [m(]]] - Ex-ol Ex=o(m(x]]] - Am for every monomial m(x) E _M(k, d). When the error bound A is the same for all monomials overload notation and simply use & instead of the parameter A.
2
Weak Testable Proper Agnostic Learning
As our starting point, we give an algorithm that performs testable proper learning of homogeneous halfspaces in the presence of adversarial label noise with respect to the Gaussian distribution. The main result of this section given below and its proof can be found in Appendix A.
Proposition 2.1 (Proper Testable Learner with Adversarial Label Noise). Let D be a distribution on labeled examples (x, 3) E Rd x {=1} with x- x-marginal Dx. Suppose that there exists a unit vector v E TRd such that Pr(xa))DD isign(v" x) # yl I opt. There exists an algorithm (Algorithm 2) that given 1] (0, 1), N d01/a²) log(L/T) i.idd. unlabeled samples from Dx. queries the labels of them, and runs in time poly (d, N) and does one of the following:
of ofdd//)))og((e
The algorithm reports that the x-marginal of D is not (O.II)
The algorithm oulputs a unit vector w E RR..
With probability at least 1 T the following holds: (1) if the algorithm reports anything, the report correct, and (2) if the algorithm returns a vector w, it holds ||v* - wll2 S Cx + 1, where CA > 0 is an absolute constant.
couple of remarks are in order. First, notice that if the algorithm outputs a vector w. we only have the guarantee that ||v* wll, is small instead of that the hypothesis halfspace l>))) = sign( w achieves small 0-1 error. Nonetheless, as we will show in the next section, conditioned on 17 passing some test, the error of the halfspace hew will be at most opt plus constant multiple of ||v* w (see Lemma 3.1). Second, unlike the testable improper learners in [RV23, GKK22] - which achieve our testable proper learner
error of opt + 7) with similar running time and sample complexity achieves the weaker error guarantee O( /opt + T7) This suffices for our purposes for the following reason: in the context of our localization based approach, we only need an efficient proper weak learner that achieves sufficiently small constant error. This holds for our proper testable learner, as long both opt and 1) are bounded above by some other sufficiently small constant.
To obtain a proper learner, we proceed to directly estimate the defining vector v* of the target halfspace ht (x) sign(v" x)), where we assume without loss of generality that v* is a unit vector. The following simple fact relating the degree-1 Chow-parameter of homogeneous halfspace and its defining vector will be useful for us.
Fact 2.2 (see, e.g., Lemma 4.3 of [DKS18]). Let v be a unit vector and h(x) = sign(v x) be the corresponding halfspace. If x is from N(0, I), then we have that Ex~N((.)) [x(x)x] / 2/T v.
To apply Fact 2.2 in our context, we need to overcome two hurdles: (i) the x marginal of D is not necessarily the standard Gaussian, and (ii) the labels are not always consistent with h 1((x)) (x). The second issue can be circumvented by following the approach of [DKS18]. In particular, if the marginal of D is indeed Gaussian, we can just treat D as a corrupted version of (x, h" (x)). where x (O, I) and estimate the Chow parameters robustly.
To deal with the first issue, we borrow tools from [GKK22]. At a high level, we certify that the low-degree moments of Dx the marginal of D approximately match the corresponding moments of (0, before estimating the Chow parameters. Importantly, this testing procedure uses only unlabeled samples. To establish the correctness of our algorithm, we show that, for any distribution B that passes the moment test, the Chow parameters of a halfspace under B will still be close to its defining vector. We state the lemma formally below. Its proof can be found in Appendix A.
Lemma 2.3 (From ComeettMatcchng to Chow Distance). Fix > O. Let k k+1
Colog(1 (l)g(1/)///
and A =
where C > is a sufficiently large absolute constant. Let B be
CVK)

---

distribution whose moments up to degree i match with those of o0, I) up to additive error A. Let
lxxx = sign(v x) be hulfspuce. Then we have that Ex-n [x(xxx]
sO(V))
With Lemma 2.3 in hand, we know suffices to estimate the Chow parameters of h" with respect to Dx. This would then give us good approximation to v" conditioned on Dx indeed having its low-degree moments approximately match those of M I). We use the following lemma, which estimates the Chow parameters robustly under adversarial label noise.
Lemma 2.4. Let 17, E (0,1) and G be distribution over IRd {=1} such that Ex-G, [xx x 21. Let V E I2 be a unit vector such that Pr (sign(v (V- x) X y] S 11. Then there exists an algorithm that takes N- Odd/n²) log(d/T) labeled samples from G. runs in time poly(N), and oupput vector w such that [xx-Gx (sign(v x)x] w S (())) with probability at least
The proof follows from standard arguments in robust mean estimation and the details can be found in Appendix C. We remark that the number of labeled samples required by this procedure is (nearly) linear with respect to d for constant 77, which is important for to obtain (nearly) optimal label complexity overall.
We are now ready to describe our testable proper learner. In particular, it first certifies that the moments of the underlying distribution match with the standard Gaussian and then draws i.i.d. samples to estimate the Chow parameter. It then follows from Fact 2.2, Lemmas 2.3 and 2.4 that the resulting Chow vector, conditioned on that the moment test pass, is closed to the defining vector of the optimal halfspace. We given the pseudo-code of the algorith and its analysis, which also serves as the proof of Propostion 2.1, in the end of Appendix A.
3 Efficient Testable Learning of Halfspaces
In this section, give our tester-learner for homogeneous halfspaces under the Gaussian distribution, thereby proving Theorem 1.3. Throughout this section, we will fix an optimal halfspace It" lt((x) (x) sign(v" x), i.e., a halfspace with optimal 0-1 error.
The structure of this section as follows: Section 3.1, we present tester which certifies that the probability of the disagreement region between two halfspaces whose defining vectors are close to each other is small under Dx. In Section 3.2, we present and analyze our localization step and combine it with the tester from Section 3.1 to obtain our final algorithm.
3.1 From Parameter Distance to 0-1 Error
For two homogeneous halfspaces (x) sign(u . x) and (x) sign(v x), where u, are unit vectors, if Dx is the standard Gaussian, I). we can express the probability mass of their disagreement region as follows (see, e.g., Lemma 4.2 of [DKS18]):
Pr [Au(x) * hy (x)) S O (Ilu ([uu)v12)) x-
(I)
Hence, learning homogeneous halfspaces under Gaussian marginals can often be reduced to approxi- mately learning the defining vector of some optimal halfspace h². This is no longer the case if Dx is an arbitrary distribution, which may well happen in our regime. We show in this section that it is still possible to "certify" whether some relationship similar to the one in Equation (1) holds.
In particular, given a known vector v. we want to make sure that for any other vector w that is close to v. the mass of the disagreement region between the halfspaces defined by by v, respectively is small. To do so, we will decompose the space into many thin "slabs" that are stacked on top of each other in the direction of v. Then, we will certify the mass of disagreement restricted to each of the slab is not too large. For slabs that are close to the halfspace sign(v x), we can check these slabs must not themselves be too heavy. For slabs that are far away from the halfspace, we use the observation that the points in the disagreement region must then have large components in the subspace perpendicular to v. Hence, long as D has its second moment bounded, we can bound the mass of the disagreement region in these far-away slabs using standard concentration inequality. Formally, we have the following lemma, whose proof can be found in Appendix B.
Lemma 3.1 (Wedge Bound), Let Dy be distribution over Rdd. Given a unit vector v and parameters 7. T (0, 1/2), there exists algorithm (Algorithm 1) that draws i...d. samples from Dx runs in
7

---

Input: Sample access to a distribution Dx over R tolerance parameter 1) > 0; unit vector R4; failure probability E (0,
Output: Certifies that for unit vectors w such that ||w - vll S ?) holds that
Pr (sign(v x) * sign(w w xi] Cn,, for some absolute constant C' > 1, or reports that Dx is not (0,
1. Set B (o//n//)//
2. Let D be the empirical distribution obtained by drawing poly(d, 1/n) log(1/T) samples from Dx-
3. For integers B - 1 S - B, define E, to be the event that vv-x x E [ön, (i + 1)m] and
EB-1 to be the event that {|v x 2 v /log(1/n)).
4. Verify that - B-1 B- Prw((.)) [AA]] Pro [Bi]] S 17.
5. Let Sy the distribution of D conditioned Eg and S be S. projected on the subspace orthogonal to v.
6. For each i, verify that S has bounded covariance, i.c., check that Ex [xx 1 x 21.
Algorithm 1: Wedge- Bound
time poly(d, 1/1) log(1/T), and reports either one of the following: (i) For all unit vectors w such that [|w V1l2 S y it holds Prx-D, [sign(v -x) sign(w x)] S Cn for absolute constant C> (ii Dx is not the standard Gaussian N (O. I). Moreover, with probability at least т, the report is accurate.
3.2 Algorithm and Analysis: Proof of Theorem 1.3
We employ the idea of "soft" localization used in [DKS18]. In particular, given vector v and parameter a, we use rejection sampling to define new distribution Dv.o that "focuses" on the region near the halfspace sign(v x).
Fact 3.2 (Rejection Sampling, Lemma 4.7 of [DKS18]). Let D be a distribution on labeled examples (x, y) IRd {+1]. Let E TRd be unit vector and a E (0,1). We define the distribution Dv. as follows: draw sample (x, y) from D and accept it with probability e (vxx)²((a- 22--)) Then, D the distribution of (x. y) conditional on acceptance, If the x-marginal of D is (O,, then the x-marginals of Dv, is (0, E). where E = =1 (1-1-=)) Moreover, the acceptance probability of point a.
We now briefly discuss the sample and label complexities of this rejection sampling procedure. Since the acceptance probability is a, we need roughly 1/a samples from to simulate one sample from Dv... On the other hand, to simulate one labeled sample from D, only need label query in addition to the unlabeled samples as one can query only the points that are accepted by the procedure. This makes
that rejection sampling is efficient in terms of its label complexity.
The main idea of localization is the following. Let v be a vector such that ||v-v*|,, S. Suppose that we use localization to the distribution Dv,ā- If we can learn halfspace with defining vector w that achieves sufficiently small constant error with respect to the new distribution Dv,5, we can then combine our knowledge of w and to produce a new halfspace with significantly improved error guarantees under D. The following lemma formalizes this geometric intuition.
Lemma 3.3. Let v", v be two unit vectors in R.d such that ||v
112 I 8 s 1/100. Let Σ
I (1-82)) -v and be unit vector such that
1//2
<C 5 1/100. Then it holds
E 1/1/2 1/2w
< 5(82 8C).
We defer the proof to Appendix C. Below, we provide few useful remarks regarding the relevant parameters.

---

Remark 3.4. Observe that in Lemma 3.3 we require that the distance of v and v* is smaller than 1/100. While this constant is not the best possible, we remark that some non-trivial error is indeed necessary so that the localization step works. For example, assume that V and v* are orthogonal, i... v. v = O, and that Σ = I - (1 2²)vv" for some E [0. 1]. Observe that Σ1/² scales vectors by a factor of & in the direction of v and leaves orthogonal directions unchanged. Similarly, its inverse --1/2 scales vectors by a factor of 1/E in the direction of v and leaves orthogonal directions unchanged. Without loss of generality, assume that v = e1, V = -e where e1, 62 are the two standard basis vectors. Then E1/²v" = v", Moreover, assume that w = aej + be (with a² + 6² = 1). We observe that ||W E1/2v" / ////////" = |w v v'1l2 = 2 - 2b. However, we have that s Σ- 1211/2 (a/E)e) + be2. Therefore, [s/||s|/2 v*1 = 2 2b/ ab/V(a// (a//E2 IP. Notice that for all & E [0, 1] it holds that s/ //|s||2 is further away from v than w, i.c., rescaling by
E- 1/2 worsens the error.
We are now ready to present an iterative testing/learning procedure that will serve as the main component of our algorithm. At high level, we first use Algorithm 2 from Proposition 2.1 to learn a vector v that close to v* in &g fy-distance up to some sufficiently small constant. Then we localize to the learned halfspace and re-apply Algorithm 2 to iteratively improve v. In particular, we will argue that, whenever the learned halfspace still significantly suboptimal, the algorithm either detects that the underlying distribution is not Gaussian or keeps making improvements such that v gets closer to v" conditioned on v still being sub-optimal. The pscudocode and analysis of the algorithm can be found in Appendix C.
S S 1/100. There is an algorithm (Algorithm 3) that with probability at least - T, either (i) correctly reports that the x-marginal of D is not N 1) or (ii) computes unit vector v(t+1) so that either ||v - v(t+1)|| 1|2 S 5/2 || v(0) 1|2 S Copt, where C > is an absolute constant. Furthermore, the algorithm draws N- = poly 1/0) log(1/T) many unlabeled samples and uses O (d log(d/T)) label queries.
Lemma 3.5. Suppose [|1''--v
After running Algorithm for at most a logarithmic number of iterations, we know v must be close to v². Then, we can use Algorithm from Lemma 3.1 to certify that the disagreement between the learned halfspace and h (x) small. One technical difficulty is that we do not know precisely when to terminate the update and each update does not necessarily monotonically bring v closer to v". As a result, the process only yields a list of vectors v(1) (t) with the guarantee that at least one of them is sufficiently closed v A natural idea to estimate the 0-1 errors of the halfspaces defined by the vectors in the list and simply pick the one with the smallest empirical error. Naively, we need to estimate the errors up an additive e and this may take up to 201/e²) labeled samples, which is exponentially worse than our goal in terms of the dependency on Nonetheless, we remark that comparing the errors of two halfspaces which differ by some multiplicative factors can be done much more efficiently in terms of its label complexity. In particular, it suffices for us to compare the errors of the two halfspaces restricted to the area in which the predictions made by them differ. Under this conditioning, the difference between the errors then gets magnified to some constant, making comparisons much easier. Hence, we can run a tournament among the the halfspaces, which reduces to perform pairwise comparisons among the lists, to obtain our final winner hypothesis. The result is summarized in the following lemma.
Lemma 3.6 (Tournament). Let E, E (0,1) and D distribution over IRd {+1). Given list of halfspaces yL there is an algorithm that draws N = (R.2 log(k/ ((T)///)))))))))))))))() i.i.d. unlabeled samples from Dx uses θ (k22 log(k/T)) label queries, runs in time poly (d, N) and outputs a halfspace h satisfying that Pr(x.)>D(h(a + y] < 10 min, Pr(x.)) (x) + y] +
We provide the pseudocode of the algorithm and its analysis in Appendix C. The proof of Theorem 1.3 then follows.
Our final algorithm (Algorithm 5) simply iteratively applies the localized update routine (Algorithm 3) and then runs a tournament (Algorithm 4) among the (logg(1/)) (1/)) candidate halfspaces obtained from the iterations. The pseudocode and its analysis, which serves as proof of our main theorem, can be found at the end of Appendix C.
9

---

4 Acknowledgements
ID was supported by NSF Medium Award CCF-2107079, NSF Award CCF-165288 (CAREER). and DARPA Learning with Less Labels (LwLL) grant. DK was supported by NSF Medium Award CCF-2107547 and NSF Award CCF-1553288 (CAREER). NZ was supported in part by NSF award 2023239, NSF Medium Award CCF-2107079, and DARPA Learning with Less Labels (LwLL) grant.
References
[ABL17] P. Awasthi, M. F. Balcan, and P. M. Long. The power of localization for efficiently learning linear separators with noise. J. ACM, 63(6):50:1-50:27,, 2017. 2017.
[BBL06] M. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. In Proceedings of the 23rd international conference on Muchine learning, pages 65-72, 2006.
[BBZ07] M. Balcan, A. Broder, and T. Zhang. Margin based active learning. Learning Theory: 20th Annual Conference on Learning Theory, COLT' 2007, San Diego, CA, USA; June 13-15, 2007. Proceedings 20, pages 35-50. Springer, 2007.
[BL13] M. Balcan and P. Long. Active and passive learning of linear separators under log- concave distributions. In Conference on Learning Theory, pages 288-316. PMLR, 2013.
[Dan15] A. Daniely, A PTAS for agnostically learning halfspaces. In Proceedings of The 28 Conference on Learning Theory, COLT 2015, pages 484-502, 2015.
[6a A. Daniely. Complexity theoretic limitations on learning halfspaces. In Proceedings of the 48 Annual Symposium on Theory of Computing, STOC 2016, pages 105-117, 2016.
[DG 10] I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, and E. Viola. Bounded indepen- dence fools halfspaces. SIAM Journal on Computing, 39(8):344133422 2010.
[DKK+21] Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamms, and N. Zarifis. Agnostic proper learning of halfspaces under gaussian marginals. In Proceedings of The 34th Conference Learning Theory, COLT, 2021.
[DKMR22] Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren. Cryptographic hardness of learning halfspaces with massart noise. CoRR, abs/2207. 14266, 2022.
[DKN10] Diakonikolas, D. M. Kane, and J. Nelson. Bounded independence fools degree-2 threshold functions. In FOCS, pages 11 11-20, 2010.
[DKPZ21] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polynomial re- gression for agnostic learning under gaussian marginals in the SQ model. In Proceedings of The t4th Conference Learning Theory, COLT, 2021.
[DKR23] I. Diakonikolas, D. M. Kane, and L. Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. CoRR, abs/2302.06512, 2023.
[DKS18] Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1061-1073, 2018.
[DKT7200] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learning Theory, COLT, 2020.
[DKT720b] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Non-convex SGD lears halfspaces with adversarial label noise. In Advances Neural Information Processing Systems, NeurlPS, 2020.
10

---

[DKZ20] I. Diakonikolas, D. M. Kane, and N. Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginals. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[GGK20] S. Goel, A. Gollakota, and A. R. Klivans. Statistical-query lower bounds via functional gradients. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[GKK22] A. Gollakota, A. Klivans, and P. Kothari. A moment-matching approach to testable learning and a new characterization of rademacher complexity. arXiv preprint arXiv:2211.33312, 2022. To appear in STOC'23.
[GKSV23] A. Gollakota, A. R. Klivans. K. Stavropoulos, and A. Vasilyan. An efficient tester-learner for halfspaces. CoRR, abs/2302.14853, 2023.
[Hau92] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100:78-150, 1992.
[KKMS08] A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777-1855, 2008. Special issue for FOCS 2005.
[KLS09] A. Klivans, P. Long, and R. Servedio. Learning Halfspaces with Malicious Noise. Journal Machine Learning Research, 10:2715-2740, 2009.
[KSS94] M. Kearns, R. Schapire, and Sellie. Toward Efficient Agnostic Learning. Machine Learning, 17(2/3):115-141, 1994.
[Ros58] F. Rosenblatt. The Perceptron: probabilistic model for information storage and organization the brain. Psychological Review, 65:386-407, 1958.
[RV23] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learning al- gorithms. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pages 1643-1656, 2023.
[She21] Shen. On the power of localized perceptron for label-optimal learning of halfspaces with adversarial noise. In International Conference Machine Learning, pages 9503- 9514. PMLR, 2021.
[Tie22] S. Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems. CoRR, abs/2207. 14030, 2022.
[Va184] L. G. Valiant. theory of the learnable. In Proc. 16th Annual ACM Symposium on Theory of Computing (STOC), pages 436-445, ACM Press, 1984.

---

Supplementary Material
A Omitted Proofs for Weak Testable Proper Agnostic Learning
Proof of Lemma 2.3. It suffices to show that for any unit vector E R&, the following holds:
E x--
[xxx)x u]
[M(x)x u] s O(VT)
(
The following fact expresses a real number as an integral of the sign function.
Fact A.1. For any a IR, it holds 1 So (sign(a sign(a + t))
We apply Fact A.I the term u x, which gives
/ (sign(u x + si + d)
E [1(x)x u]
E [x(x)x-ux uu
E
h(x)
x~B
x-N(0.1)
2
x~B
1120
E
h(xx)
(sign(u-x--a + sign(u x x t)) dt
(0.)
120
[h(x) (sign(u- x + sign t)) x
E
2 120
E (0.1
[h(x) (sign(u t) sign(u + t))] dt
where in the last line we switch the order of the integral of and x by Fubini's theorem. We then split above integral over into two parts based on the magnitude of (1 > 1/ /T versus 1 s 1/VT) and apply the triangle inequality:
E x~B
[x(x)x-u]
u]
E [x(xxx1 u]
E
| (x)signnu ( x-() [)] x=N((o,1)
E
[M(x)sign(uxx x x-t)] t]] )at
2
JSSISIVV
x~B
E (xxxssign(u-xxx -u--uuu-+)) x+]
E
[xx)ssin( (u-sggn(u-20) x t)] de
2
x-
I
+
E [h(x) (sign(u- x - t) + sign x + t))]
121//0
x~B
E x-.(
(x( (sign(u . x- + sign(u x x xx
(2)
We start by bounding the integral for t > 1/v7.
Lemma A.2 (Chow-Distance Tail). Let Q be distribution over IRd with Ex [xx] 1 x 21. Moreover, let g(x): Rdd + R be a bounded function, i.e., Ig(x)] S 1 for all E IRd, It holds
E V x [x(x) (sign(u x 1) sign(u (u x + 1))] de S 20(7))
Proof. We split the expectation into two parts based on the relative sizes of [u x/ and Specifically, can write:
12

---

1/21 1/23/ vo x-Q (x(x) (sign(u. x- + sign(u x + ())
E [g(x) (sign(u- 1221//1 x-
sign(u x f)) 1f/u x 2 f]]dr
E 121/v0 x-"
(g(x) (sign(u- x x-t) sign(u x x+ 1{[u x [t
(3)
For the second term in Equation (3), we rely on the following observation: when x I t, the quantities u x- and u- u-x-t x-+ have opposite signs. Hence, we conclude the integrand is 0 everywhere and therefore the second term also For the first term, we have
Ve
E [x(x) (sign(u- t) sign(u x x))) 1f[u x 2 2|H x-Q
/ 1121//7 x-_Q
[(xx (sign(u- x x- t) + sign(u x t)) 1flu x 21)
[21([u x 2 tHl $
1/21//M t <o(T))
1121//7 x
where the first inequality follows from the triangle inequality, the second inequality uses the fact that the sign(-) function is at most and the third inequality follows from Chebyshev's inequality using the fact that the E[xx] x 21. Combining our analysis for the two terms in Equation (3), we can then conclude the proof of Lemma A.2.
Using the triangle inequality and applying Lemma A.2 on the distributions B and N/ I), we have that
1
/
E x-B
[h(x) (sign(u x t) + sign(u x t))]
2
121/4
E
[x(x) (sign(u x - 1) sign(u x + 1)]1 )ad < O((T)
(4)
xo.(
We then turn our attention to the terms
JosIsUv
E [b(x)sign(u= x -1]]] di
E (xx))sgg(uuxxx x 0)]-
(5)
x
xxN((.))
JoS [h(x)sign(u x x x
E xo.)
[hx))sign(( x t)] dt
(6)
x-B
To bound Equations (5) and (6), we need the following fact from [GKK22].
Fact A.3 (Theorem 5.6 of [GKK221). Let Rd + {+1} be a function of halfspaces, i.e. h(x) = (x), ... (x))) where h4 are halfspaces and g {=1}" + {1] For any k E N, let A
k+1
for some sufficiently large absolute constant C' 0. Then, for any distribution whose moments up to order l match those of NO,, up to A, we have
vp
2k de C'vk)
E
[x(x)]
E [x(x]] x~B
S VD (Clog (Vpk)
1
Vk
for some constant C C>0 0.
13

---

For fixed t, note that h(x)sign(u t) is a function of two halfspaces. Moreover, from the assumptions of Lemma 2.3, the distributions B and N I) match C'log(1/n///) moments k+1
where C' > 0 is sufficiently large absolute constant. Therefore, applying Fact A.3 and the triangle inequality gives
up to enror A =
kdt CVk
2 I
E [h()ssign((u x x- -)1- x-N(0.1) x-B
[h(x)sign(u- x x-1]] ddt
+)] )at
50(1) [
ndt =dt= O(v
JoSISI/V
Similarly, we can show that Equation (6) is bounded by O(vr)- Substituting the bounds from Equations (4) and (7) into Equation (2) then gives
[x(x)x u] x-B
E
[xxxx ul SO(vT).
x=N110,1)
Since is chosen arbitrary unit vector, this implies that
E
[x(x)x]
E
[x(x)x]
$ 5O(vT).
x~B
(
Combining this with Fact 2.2 concludes the proof of Lemma 2.3.
Proof of Lemma 2.4. We first show that Ex [sign(v V x) x] (xx.)) x - O(vr). For any unit vector u, we have that
E xxGx
[sign(v x) x]
E (x.y)~
wy u u-
E (x.I)~
[signn(v x) yyu
E [(sign(v x) x) -)? E x)²]
V (x.9)~
XNGG
4
where we used the Cauchy-Schwarz inequality and the fact that Pr(x,)) bsignssssvvvvv x) * 8] S n. Therefore, we have that |Ex-Gx [sign(v x)x] Ex [yx]] 1l I 4V7. Let (x(1), (x()),(())) ()))) (x(....,((([[))) (x(N)), ((Nii,yy(,)) y(N)) be samples drawn from G, where Ni = Od/1)²). Then, let W (1/N)) (0)x6), From Chebyshev's inequality, we know the i-th coordinate of w should satisfy Pr[lw; E [yx]]] 2 /d] < 4d/(N17²) < 1/4. Therefore, using the standard me- dian technique, we can find w!median, that Pr[[w]eedia
(wmmedian Ex [yx]] n/vd r/d, w w w-median), then we have that [xxx))> [yx] w|| S O()) with probability at least 1-7. T. Then, using the triangle inequality, we have that Ex-G, (sign(v x)x] w/l2 S O(vn), which concludes the proof of Lemma 2.4. Ll
using N₂ O(N, log(d/r)) samples. Let
Proof of Proposition 2.1. Let A, N be defined in Algorithm If Dx is (0, the moments up to degree the x-marginal the empirical distribution D (obtained after drawing N i.idd. samples from Dx) are close to those of (O, up additive error A with probability at least 1 1-1110
If Algorithm 2 did not terminate on Line 3, we then have that the moments up to degree of D are close to those of (N I) up to additive error A with probability at least 1 7/10. Then, applying Lemma 2.3 with B D' and h(x) = sign(v' (v" x), we get that
ssign(v* x)x] 22/TV' 20(v).
(8)
Now, suppose we were to query the labels of all points in D We could then construct another empirical distribution LN over labeled samples. By our assumption, the error of sign(v" x) under
14

---

Input:
Sample access to distribution Dx over unlabeled samples and query access to the labels of the drawn samples according to D; certification range 7j failure probability т. Output: Either reports that the Dx is not (0, I); or returns unit vector E R4 such that ||v" w w 12 S CA Vovopl+ +/-
k+1
1. Set k = C log((/n)) and A
where C > 0 is a sufficiently large
CVk
absolute constant.
2. Draw N= d loglog log(1/r) samples from Dx and construct the empirical distribution DN.
3. Certify that the moments of D up to degree match with those of (o up to error A.
4. If the above does not hold; report that Dx is not (0, I) and terminate.
5. Draw N' = (d/nn")) (d/n) samples from D and query their labels. Denote the resulting labeled samples as S.
6. Use algorithm from Lemma 2.4 on S and obtain w. Return w/llw/l2-
Algorithm 2: Proper Testable Learner
D is at most opt. Hence, the error of sign(v" x) under Ln is at most opt + 17 with probability at least 1 - T/10. Next, notice that the set of samples S in Line are exactly i.i.d. samples from Lv- Hence, applying Lemma 2.4 on L then gives that, with probability at least 1 1/10, the vector w. computed on Line of Algorithm satisfies
[sign(v" x)x] w
5 (Vopt (ooppt++)) +
(Lx)
2
Notice that the x- x-marginal of LN is exactly Dy. Hence, combining Equations (8) and (9), we get that /2/Tv" O + t?) as desired.
B Proof of Wedge Bound Lemma 3.1
Proof of Lemma 3.1. Recall that D is the empirical distribution made up of N i..dd samples from Dx where N (dly 1/r) log(1/r). We consider D restricted set of thin "slabs" stacked on each other in the direction of More formally, we define S, to be the distribution of D conditioned on v E [( - 1)1,, in)) for E [-vlog(1 (1/n)//,, (1oog(1/)/// /n), and S be the distribution S, projected into the subspace orthogonal to v.
Suppose that Dx is indeed (O,,I), I). Then the distribution D is the empirical distribution formed by samples taken from AO I). In this case, is easy to see that both Line 4 and of Algorithm pass with high probability.
Claim B.1. Assume that Dx (0, Then the tests at Line and 6 of Algorithmm pass with probability at least - T 7/10.
(). If we concatenate the values of Pr [E,] into vector, it be viewed as the discretization of (N(0, 1) into 2B many buckets. On the other hand, Pr [ is an empirical version of this discrete distribution composed of N i.i.d. samples where N poly(d (d, 1/n) log(1/7). Since can learn any discrete distribution with support n to error in total variation distance with (nn77²) log(1/7) samples with probability least - T, it follows that Line 4 will pass with high probability long as we take more than & poly(d. (d,y 1/n) log(1/T) many samples.
Proof. If NN(O,) I), then
For Line 6, we remark that S is the empirical version of (d 1) dimensiionaa standard Gaussian. Since the empirical mean and the empirical covariance concentrates around the true mean and
15

---

covariance with probability at least 1 1-17 7 if one takes more than (og(/)) many samples, it follows that Line 4 will pass with high probability as long as we take more than (dd² /n/²) log(1/T) -
poly(d, 1/n) log(1/r) many samples.
Suppose that both lines pass. We claim that this implies the following: for all unit vectors w such that l|w 2 S it holds
Pr [sign(v x) & sign(w x)] - Cn. x~
(10)
for some absolute constant C'> 1. Given this, we can deduce that the same equation must also hold for Dx with high probability - albeit with larger constant C". To see this, we remark that the left hand side of the equation can be treated as the error of the halfspace sign( - x) if the true labels are generated by sign(v x). Since the VC-dimension of the class of homogeneous halfspaces is d, we have that the error for all w under Dx well -pproxpppo by that under D up to an additive 7 with probability at least - T given N = poly(d, 1/n) log(1/r) many samples. Hence, conditioned on Equation (10), it holds with probability at least т that
Pr [sign(v x) + sign(w x)] S (C + +1m, x>
for all w.
We now proceed to show Equation (10) holds if the Algorithm 1 did not terminate on Lines 4 and 6. Conditioned on Line 6, for any unit vector u E IRd that is orthogonal to v, we have | I x|| S (())
and Var [u x] < 2. Using Chebyshev's 's inequality, for any a > O, it holds
+1 (1+
Pr [| x a| S 8
(11)
a
We can now bound Pr (sign(v x) 7 sign(w x)] for an arbitrary unit vector w satisfying
||w vll2 S v.. We proceed to rewrite w as (1 - 22)1/2 + yu for some unit vector u E IRd that is orthogonal to v and y E (0, m). Denote 7 = 7/(1 - -2))1/2, then the event that sign(v x) + sign(w (w.. x) implies that 7 u x 2 vlv x|. Therefore, we have that
1 + n7²
Pr [sign(v x) & sign(w - x)] < Pr b Iu x 2 x.
x|| < Pr x
x
2 in) S
SOL
S
12
(12)
where in the second inequality we use the definition of S; and in the third inequality we use that 7 S 17 and Equation (11). We now bound from above the total disagreement probability between w and v under D. We have that
Pr [sign(v x) + (i x)] s Pr D
v x| 2 vlo((1/n)
+
Pr x
||v x s
x~D
Mog(1/ni// Σ
Pr X
[sign(v x) + sign(w x]] Pr [(i 1)n S S inj xnD
H1
Viogi//n/n
1 1"2
I 6n + (n)
Σ HSI
S 50())
12
where we used that Pr Prx-olIx v/ > Vlo((1/) I 3n and Pr Pix-Bllx v| < 7] S 31,, since in Line 4 verified that the probabilities Pr pI [( 1)7, in] are close the probabilities under (/OO,) I) and hence bounded by O(n), Equation (12), and the fact that the series Σ, is convergent and less than n²² n²/6.
C Omitted Proofs of localization and main theorem
Proof of Lemma 3.3. Since ||v v*ll2 S 5, we can write
v² 1
(v + ku)
(13)
v1 + x
16

---

for some R. E [0, 6] and some unit vector u perpendicular to v. By definition, E shrinks in the direction of v by factor of á and leaves other orthogonal directions unchanged. Hence, holds
g1/2"
(ōv + ku)
R2
Then, using the triangle inequality, obtain
26
// S V1+1" (6 (óllvl12 + N 11ul1)) 3
S 26,
V1 n²
since k. upper bounded by 5. Since
x/1/8v" w |2//2v11 11g
S. we can write
11/2v"
+ av bu',
|1/22'1 2
for some |a|.b [0, and u' perpendicular v. We can multiply both sides by y and get
yw = -/222" + ayv + byu',
which implies that
3 1/2 //11/3 w = v a0//vv+ byu'.
Using Equation (13), we then have
1/2 (v x² +02)
byu'.
(14)
VI+
Let = - VITK² a7/8 be the coefficient before v. We next identify the range of X.
Claim C.1. It holds that X E [1 - 5 - 2ç, 1 2c].
Proof. Recall that 6. E [0, |a|
[0, [] and y E [0, 26.. If we view À as function of K, is minimized when K = 8, a 5. = 28, which then gives
1
V 2 8 26,
where in the second inequality use the fact that / 2 1 - for x 2 0. On the other hand, X
maximized when λ a 7, 28, which gives < 2Ç. Hence, we can conclude that A E [1 - 2Ç, 1 + 2c).
We multiply both sides of Equation (14) by AvI+K which gives
E
1/2
K u
b
u'
Xv1 + 2
VI+
x(1+x2)
AV
+ x
K
-v++
u
u'
A(L
VI+
Av
+ R
where in the second equality Equation (13). We then bound from above and below the norm, and we get that
by
E
1/2
1
XV1+K 1
R
AVI R²
where we used triangle inequality. Note that
(1/A) / k2 < /1/A +|
V1 + x2
S (6 16+221 2() 5 2(() + K
and that < 8. Therefore, we obtain that
7
1/2 w
s 4(8 +()
A +
R
2
17

---

Input: Sample access to distribution D over labeled examples; unit vector R4; parameters T, 8, > 0.
Output: Either reports that Dx is not (O, I) or computes unit vector v' such that: either Iv" v'll2 S 6/2 or liv* - - I ((opt)
1. Let Dv.s be the distribution obtained by running Rejection Sampling with parameters and 6.
2. Check the acceptance probability within (6/2,36/2) Otherwise, report x-marginals of is not (0,
1/2 3. Let G' be the distribution obtained by applying the transformation - on the marginals of Dv.s where Σ = I - (1 v²)vv'
4. Run Algorithm 2 on G with accuracy 1/(20000C)) to obtain unit vector w.
5. If the algorithm reports the marginal of G' is not n (O, I), terminate and report it.
6. Set
/
Σ w || and return v'.
Algorithm 3: Testable Localized- Update
Let A
E 1/2 w
We have that
AV++R?
Σ- 1/2 w
S l|vv 1-11 11/ 1| 5(5² 100++00 +
1
|/-1/2
This concludes the proof.
Proof of Lemma 3.5. For simplicity, we denote (1) v. We apply the Rejection Sampling procedure from Fact 3.2 in the direction v with o 5. the x-marginal of D is (0, I), the acceptance probability of Dv,5 5 is exactly 8. We then estimate the acceptance probability with accuracy e; if is not lying inside the interval 2 36/ /2] (see Line Algorithm 3), we report that the x-marginal of D is not standard normal and terminate.
Conditioned on the event that the algorithm did not terminate, we can get an (unlabeled) sample from the x-marginal of Dv.5. using (11/8) unlabeled samples from Dx- To get a labeled sample from Dv.s, we only need additional label query. Note that, under the distribution Dv.5, the error of the v" is
Pr [sign(v" x) + v (x..)
Pr [sigu(v" xx) # y (x, y) is accepted] (x.8)~
< Pr siign(v xx) # v\/ Pr [xx, y) is accepted] (x,y)~
(x.0)~D
< 2opt/8
(15)
where we used that the probability of the acceptance is at least 8/2. Denote by G the distribution of (2-1/2x, y), where (x, y) Dv,s and Σ = I- (1 v²) We note that the x-marginal of D were the standard normal, then x-marginal of is the standard normal. Hence, we can apply the algorithm Algorithm 2 from Proposition 2.1. Under the transformed distribution, we have that the new optimal vector (v+Y== : 11/2"" E 1/2
From Proposition 2.1, running Algorithm on the normalized distribution with error parameter < 1/(2000C)) and failure probability 7 consumes poly(d) log(1/T) unlabeled samples and (og(/)/))) (d/r)) labeled samples from G. Since the rejection sampling procedure for accepts points with probability at least S2 (e) Therefore, it consumes poly(d, (d, 1/e) (1g(1/r) samples from D and uses (d (olog(d/))) additional label queries. Conditioned on the event that succeeds (which happens with probability at least 1 7), it either (i) reports that the --magiaal of G is not standard Gaussian (ii) returns a unit vector w such that
w (v'\ll2 $ CA.
Pr (x.y)~G
(sign((v+) x) # # +
(16)
18

---

In case (i), we can directly report that x-marginal of D is not (0, since the x- x-marginal of G ought to be NV.O.))
In case (ii), we claim that at least one of the following hold (a) v before the localized update
already good enough, ie. ||v - vllg I 40000C; opt: (b) it holds || (vvy' - w|l, I 1/100. Suppose that (a) does not hold; will show that it then must hold II(v*) wl12 - 1/100. Since ||v -v"=vllp S 6 and ||v* vll, > 40000CA* 2opt, have that opt. 8//(0000))). Furthermore, from Equation (15) we have that Pr(x.y)~Du. (sign(v" x) # yl S 2opt/ó, it then follows that ()))) [sign((v") x) + vl S 2opt/6 & 1/(200002)) Substituting this into Equation (16) then gives
1/w (v*) - 1/100.
Using our assumption that 1|v v- S 5 < 1/100, we can apply Lemma 3.3, which gives that
E E-1/2w
6/2
10-1//w|] 112
Hence, we set ((+1) =
E /-//w ww
and this completes the proof.
L
E w
Input: Sample access to Dx over unlabeled examples and query access to the labels of the samples drawn; a list of k halfspaces (h()) parameters T, >> O.
Output: finds halfspace h whose error is nearly optimal among the list.
1. Let C' be sufficiently large constant.
2. For i k
(a) Take N1 == C log(k/T)/c samples Dx.
(b) Skip the iteration if there are fewer than N2 = 0.1 C log(k/T) samples such that
(60 (x) & (x). Denote the samples satisfying the condition as St. (c) Query the labels of random subset of samples from S1 of size N2. Denote the set of labeled samples as S2
(d) Compute the empirical errors of (0) hD) using S2.
(e) If the empirical errors differ by more than 1/4, mark the one with larger error as sub-optimal.
3. Return any halfspace among the list that has not been marked as sub-optimal or declare failure if there is any.
Algorithm 4: Tournament
Proof of Lemma 3.6. Fix halfspace (1) Suppose there another halfspace h0) such that
Pr [h (1) (x) + > 10
Pr (x.9)>>
(1 (z) * yl +
(x,y)>
We argue the halfspace will be marked as sub-optimal with probability at least T/ log(1/e). For convenience, denote == (r(x.y)>D(hh (hh (x) + y A (100)) + h(0 6 Pr(x.))>((hh) (1()) * y A (x) * hx)))) and m Prx~Dx Dz (1()) (x) o h63 Notice that a, b are the errors of the two halfspaces from the area in which their predictions differ and m is the mass of the area. Then, it holds
+ b (x:1)>~D)
Pr (1) (x)
X 1100
A
h0 (x)]
Pr (1(0 (x) # G
A Ag (1 (x) = m,
(x.9))~
Pr 1 (x) マ (x,))~D
Pr (x.y)~
[x) + 29
Pr (x
O (x)
+ v) + 9b.
This further implies that a/m - b/m 4/5. Notice that a/ m, b/m are precisely the errors of (1)
() under the conditional distribution of D restricted to the area in which (00) * hO) Hence,
19

---

with (log(k/T)) many samples, the corresponding empirical errors will differ by at least 1/4 with probability least 7/k.
On the other hand, suppose
Pr (x) (x.g)=
Pr (x) + v). (x,y)>D
This implies that a/m < b/m m. As a result, the algorithm either skips the iteration if there are fewer than (log((//T) many labeled samples from the conditional distribution or the empirical error of h())) will be less than that of h,55) by more than 1/4 with probability least r/k² if there are enough samples.
The correctness of the lemma then follows from union bound. Finally, we remark m, the mass of the area we condition to, should be at least e if the errors of the two halfspaces differ by at least e. In that case, it takes on average (1/c) unlabeled samples and additional label query to simulate one labeled sample from the conditional distribution. Therefore, it suffices if the algorithm takes O(k² (og(k/T)/e many unlabeled samples from Dx and use + (k2 log(k/r)) many additional label queries. This concludes the proof of Lemma 3.6.
Input:
Sample access to a distribution Dx over unlabeled examples and query access to the labels of the samples drawn; >> unit vector E Rdd Output: Either reports that Dx is not IO, or computes hypothesis h such that Pr(x,))=((((x) # y] = (opt).
1. Set T = (Cl))()/)) for sufficiently large constant C > 0. Set 1 1/(20000CA) where CA is the constant from Proposition 2.1.
Run Algorithm on D with accuracy to obtain unit vector (0))
3. If Algorithm reports that Dx is not (0, I). then report it and terminate.
set = (1/100)2 and run Algorithm 3 with parameters (((), 6, to 4. For = 0 lo...
obtain (1+1)
5. For i 0 log(//):
(a) Run Algorithm with v() and je for j E [1/c] on the x-marginals of D.
(b) Set (x) sign(v(1) x).
6. Return the hypothesis obtained from rumning Algorithm 4 the list of hypothesis
(h()) Net log(1/e) on D with accuracy and failure probability 7/10.
Algorithm 5: Testable Localization
Proof of Theorem 1.3. Denote by v", a unit vector with error at most opt, i.e., Pr(x.))> jsign(v*. x) * yl Σ opt. We start by analyzing Algorithm 5. In Line 2, Algorithm uses Algorithm with parameter 77 = 1/(20000C3) to get hypothesis (0) with small distance with v*. From Proposition 2.1, Algorithm 2 either reports that x-marginal of D is not // (0, outputs vector (0) small distance with v*. If Algorithm reports that the x-marginal of D is not (/ I), terminate the algorithm. Conditioned on the event that the algorithm did not terminate, then we have
(0) -''1, S CA + t
(17)
We consider two cases depending on how large the value of opt is. If opt > 1/(20000C)) then any unit vector achieves constant eтror; therefore, conditioned that the algorithm did terminate on any proceeding test, any vector we output will satisfy the guarantees of Theorem 1.3. For the rest of the proof, we consider the case where opt < 1/ 1/(20000 In this case, ||v - -vll < 1/100, this means that Algorithm 5 on Lines 4-4 will decrease the distance between the current v".
currenthypothest hypothesis and
Conditioned on the event that the algorithm did not terminate at Lines 4-4 of Algorithm 5, claim that there must have some 0 < t" < log([//)) such that [|v((*) v*] < O (opt + e). Let t' N be
20

---

the maximum value so that 2- /1000 2 40000opt, then, for all t S min(t', (og(1/e) it holds that 2- 2-1/100 2 40000opt. From Lemma 3.5, we have that for S log holds that
v" - - 52-
From the above, note that if > log(1/c) then || v* c/100. If llg[(//c), have that ((()) v* S O(ppt), which proves our claim. remains show that Algorithm 5 will return vector v' so that Pr(x.y)~D(sipg (v'. x) + y| Oopt + e). From Lemma 3.1, conditioned that Algorithm did not terminate on Lines 5-5b, we have that for all vectors v ..... (logg(//e) generated on Lines 4-4 of Algorithm 5, have that
(sign(v()) (x.y)~
Pr
x) + vl
-v/))-
Hence, we can conclude that Pr(x.y)>D(sigg (v(*)) x) * v) S O (opt + +e). Then, applying Lemma 3.6 gives that the returned halfspace will have error most 10 (isaguiolssiuuv" x) o v] + +==00 (opt + c).
To conclude the proof, note that each invocation of Algorithms 1, 2 and con- sumes 1/l log(1/r) unlabeled samples and Od (log(d/r) + log log(1/c))) label queries. Moreover, the total number of invocations upper bounded by @(log(I/e)). For algorithm Algorithm 4, it draws poly(1/e) many unlabeled samples and use e (loge(1/e) (log log(1/e) + log(1/r))) label queries. Therefore the total unlabeled samples con- sumed by Algorithm 5 is N (oly(d, 1/<) and the total label quereis used is most
1 = 0 (d log(1/e (/e) (log(d/r) + log log(1/<)) + (1/e(1 (log log(1/e) + log(1/r)))
All the procedures run in time that scales polynomially with the number of samples drawn. This concludes the proof.
21


Reviews:
[{"review_id": "EMarWdq3Af", "reviewer": "Reviewer_fkEL", "summary": "The paper studies the problem of efficient testable learning of half spaces under Gaussian marginals and adversarial noise. The setting of testable learning addresses the issue of restrictive assumptions on the marginal distributions (such as Gaussianity) under learning algorithms are designed. Traditionally, a learning algorithm has no guarantee when the marginal distribution is not the prescribed one. In tester-learner setting, a learning algorithm consists of a tester and a learner. The tester \"certifies\" that the marginal distribution satisfies certain conditions (ideally this test would be a test of whether the marginal distribution is \"close\" to the original distribution). Conditioned on the tester passing, the learning algorithm has the desired correctness guarantee. The main idea is that tester does not need to test for distributional closeness but rather just closeness sufficient to \"fool\" the learning algorithm.\n\nA recent line of work has considered the learning of half spaces in this setting. Previous work show that the halfspaces can be agnostically learnt under Gaussian marginals in time $d^{1/\\eps^2}$ which is optimal if one insists on algorithms that return hypotheses that have error $OPT + \\eps$. The present paper relaxes this notion to require that the hypothesis returned only has error $O(OPT) + \\eps$. The paper presents a polynomial (in $d$ and $1/\\eps$) time tester-learner algorithm under Gaussian marginals. ", "questions": "- It would be nice to address which parts of the paper can be generalized to more general distributions? For example, what notions of testable concentration and anti concentrations would suffice for these algorithms to work. For example, would having sufficient moment decay suffice for the Chow parameter recovery? ", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a natural and interesting adaptation of the localization technique for learning half spaces in the testable learning setting. The main idea is that learning algorithms designed to work under Gaussian marginals require significantly less information (for example only rely on moments and anti concentration). The paper analyses a robust version of Chow parameter recovery under the condition that the marginals match Gaussian marginals (this can be tested efficiently). Using this as a weak learner, the paper uses a localization technique to convert a weak learner (from Chow parameter recovery) to a strong learner. Again the paper uses the fact that closeness of parameter and loss for halfspaces can be efficiently tested. In summary, the paper presents a nice analysis of learning algorithm ", "weaknesses": "As presented the paper is too specific to Gaussian marginals.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nRegarding the concern that our tester-learner may only work under Gaussian marginals, we refer the reviewer to our General Response.\n\nThe reviewer brought up the question of which part of the algorithm can be generalized to work under a broader family of distributions. Just as the reviewer guessed, the Chow parameter estimation part can indeed be relaxed to work with distributions whose second moments are bounded. The main challenge in generalizing our approach to other distributions is the localization step: while the conditional distribution of Gaussian restricted to a thin slice is still a Gaussian, this need not be the case for other family of distributions. \n"}, {"review_id": "8EkznTMuKg", "reviewer": "Reviewer_8SDJ", "summary": "This paper considers computationally efficient learning of halfspaces with adversarial noise in a recently proposed \"testable\" task: with high probability either reports the example distribution is not standard Guaissian, or outputs a halfspace with error of at most O(opt)+epsilon. There are existing works in a similar setting but targets the error of opt+epsilon, so their time and sample complexity is unavoidably $d^{O(1/\\epsilon^2)}$. This paper relaxed the error target to O(opt)+epsilon as in previous non-testable works, and shows that the testable task can be achieved with time and sample complexity of around poly(d, 1/epsilon) and label complexity of around d log(1/epsilon).\n\nTechnically, the results are obtained by (non-trivially) combining known ideas, like moment matching to assist testing, the Chow parameter (roughly speaking, E[yx]), robust mean estimation, and soft localization for learning in a label-efficient way.\n\n--\n\nI've read the author's response and I remain positive for this paper.", "questions": "I don't really have any questions, but one minor comment is that since this is a relatively new setting, it might help readers understand the difficulty of the problem by explaining that one cannot simply first test if the distribution is Gaussian and then proceed with standard learning algorithms.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This paper considers a recently proposed task of efficient testable learning of halfspaces with Gaussian distribution, and shows that, similar to the results in classical non-testable setting, it can be done with poly(d/epsilon) when considering constant-factor approximation. In my opinion, this result is not very surprising, but it is still interesting to know.\n\n- Most of the individual ideas used for the proof and algorithm are known to the community. On the other hand, the careful analysis to combine them in this new testable learning setting is still novel and nontrivial.\n\n- I briefly checked the proofs and they looked sound to me.\n\n- The paper is written very clearly: it clearly explains the problem and how it relates to existing work, and it organizes its technical part well so that one could follow both the high level steps and details.", "weaknesses": "There are some weakensses (and I mentioned some of them above already), but I don't think they're really major:\n\n- The results are not very surprising to me, and the individual ideas used are mostly known.\n\n- It only considers standard Gaussian distributions and adversarial noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The reviewer mentions the result is itself not surprising. While we respect this opinion, we want to point out that there are known hypotheses classes where there are separations between testable learning and standard agnostic learning. In particular, as shown in the initial work of [RV23], there are agnostic learning algorithms of monotone boolean functions under the uniform distribution in time $2^{\\tilde O(\\sqrt n)}$, but their lower bound construction suggest that achieving the same under the testable learning setting requires a runtime of $2^{\\Omega(n)}$.\n\nThe reviewer also pointed out “Most of the individual ideas used for the proof and algorithm are known to the community”. While we indeed use many standard tools appearing in prior works, the wedge bound algorithm (Algorithm 2) and its analysis, to the best of our knowledge, is a novel technical contribution. Quite differently from the tester that exists in prior literature, this testing routine no longer blindly compares global low-degree moments but rather uses “local’’ information restricted to areas defined by the output of the learner. In our opinion, this is one of the most important pieces in achieving efficient testable learning of halfspaces. \n\nFinally, we thank the reviewer for bringing up the discussion of the difficulty of testable learning. The insufficiency of the naive combination of testing distributional closeness and the standard learning algorithm has already been discussed in the initial paper of [RV23]. We will include this in our paper and explain in detail why testable learning is a non-trivial task.\n\n[RV23] Rubinfeld, R., & Vasilyan, A. (2023, June). Testing distributional assumptions of learning algorithms. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1643-1656)."}, {"review_id": "4EHh9sxyFw", "reviewer": "Reviewer_1kSW", "summary": "Learning halfspaces is a very well studied problem in machine learning. In the agnostic (adversarial label noise) and distribution free setting, this problem has been known to be computationally intractable. As a result, there have been several works of agnostic learning in distribution specific settings (where the marginal distribution belongs to a particular family of distributions, say Gaussian or log-concave). In this scenario, the learner has an error of the form $OPT + \\epsilon$, where OPT denotes the optimal 0-1 error. This however has complexity $d^{1/\\epsilon^2}$, and the exponential dependency on $1/\\eps$ is tight. This motivates the designing of learning algorithms that have better sample complexity with respect to $1/\\epsilon$, whereas the error becomes $f(OPT) + \\eps$ for some function f.\n\nIn this work, the authors studied this problem in the newly introduced Testable learning framework  by Rubinfeld and Vasilyan (STOC 23). Here the goal is if the tester accepts, then with high probability the output of the learning is close to some function of OPT, and if the data satisfies the distributional assumptions, the algorithm accepts.\n\nIn this paper, the authors study the class of homogeneous halfspaces over $R^d$ with Gaussian marginals. This work designs a tester-learner with sample complexity $N=poly(d, 1/\\epsilon)$ and runtime $poly(dN)$. Additionally, their algorithm also works in the active learning framework where the algorithm only queries the labels of a subset of the samples.\n\nThe authors first design a weak agnostic learner with respect to Gaussian distribution which checks if the low degree moments of the marginal distribution approximately matches with that of Gaussian distribution (Section 2). The idea is if the moments are close, then the vector corresponding to the degree-1 chow parameters will not be far from v^* (the true vector of the half-space), see Lemma 2.3. They also design an algorithm that either reports if the marginal distribution is not Gaussian or it outputs a unit vector w (Algorithm 2 corresponding to Proposition 2.1)  Once they have the weak learner, the authors will try to find a vector that has small 0-1 error with v^* by calling Algorithm 2 (Lemma 2.1) in an iterative manner. After logarithmic many iterations, they show that the probability mass of the disagreement region is bounded (Lemma 3.1). However, this process gives a collection of vectors such that one of them is close to the optimal vector v^*.The authors finally run a tournament among these candidate halfspaces corresponding to these vectors and outputs the winner hypothesis (Lemma 3.6).\n\n\n", "questions": "Can this approach be used to design tester-learners for function classes other than halfspaces.\n", "limitations": "It is a pure theoretical work in the paradigm of testable learning - a relatively new concept whose importance is not yet fully confirmed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper gives the first algorithm for testable learning of halfspaces that runs in poly(d, epsilon). The algorithm is very nice.\nWith the complexity pulled down drastically, a proper implementation and experimental results for this algorithm would be possible and it would be nice to see the relevance of the concept of testable learning in various applications. ", "weaknesses": "The usefulness of the testable learning model in real life applications is yet to be understood.  The paper can only handle adversarial noise.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nRegarding practicality: The testable learning framework is a new learning paradigm whose definition (in a paper that appeared in STOC’23) was motivated by practical considerations (namely, the fact that one cannot verify the output of known distribution-specific agnostic learners). Since its introduction, the ML theory community has been intensely studying the algorithmic possibilities and limitations in this learning model. Ours is the first work that gives fully-polynomial time algorithms with near-optimal error guarantees for learning Gaussian halfspaces in this model. Since the testable learning model was defined only recently, it has not yet been picked up by more practical ML researchers. Related to this, we note that prior to our work no known efficient implementation of testable learners was possible (because prior algorithms had complexity scaling exponential in $1/\\epsilon$). As pointed out by the reviewer, our work drastically pulls down the complexity and hence makes experimental investigation of the model in practical settings a viable option.\n\nFinally, we would like to note that learning theory results such as ours are within the scope of NeurIPS (as stated in the call for papers). Consequently, we request that our work is judged on its merits based on the appropriate criteria.\n\nRegarding generalizing our results to other hypothesis classes: even without the testable requirement, halfspaces are the only class for which it is known how to achieve O(OPT)+eps error in polynomial time in the distribution-specific agnostic model. In fact, most known efficient learners (with distribution-independent error guarantees) tolerant to label noise focus on the class of halfspaces and their generalizations [KKMS08, KLS09, ABL17, DKS18, DKKTZ21, DKPTZ21, DKTZ22].\n\n\n[ABL17] Awasthi, P., Balcan, M. F., & Long, P. M. (2017). The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6), 1-27.\n\n[DKS18] Diakonikolas, I., Kane, D. M., & Stewart, A. (2018, June). Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1061-1073).\n\n[DKKTZ21] Diakonikolas, I., Kane, D. M., Kontonis, V., Tzamos, C., & Zarifis, N. (2021, July). Agnostic proper learning of halfspaces under gaussian marginals. In Conference on Learning Theory (pp. 1522-1551). PMLR.\n\n[DKPZ21] Diakonikolas, I., Kane, D. M., Pittas, T., & Zarifis, N. (2021, July). The optimality of polynomial regression for agnostic learning under gaussian marginals in the SQ model. In Conference on Learning Theory (pp. 1552-1584). PMLR.\n\n[KKMS08] Kalai, A. T., Klivans, A. R., Mansour, Y., & Servedio, R. A. (2008). Agnostically learning halfspaces. SIAM Journal on Computing, 37(6), 1777-1805.\n\n[KLS09] Klivans, A. R., Long, P. M., & Servedio, R. A. (2009). Learning Halfspaces with Malicious Noise. Journal of Machine Learning Research, 10(12).\n\n[DKTZ22] Diakonikolas, I., Kontonis, V., Tzamos, C., & Zarifis, N. (2022, June). Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning (pp. 5118-5141). PMLR.\n"}, {"review_id": "JGXtGNMcgl", "reviewer": "Reviewer_XEN1", "summary": "This paper studies the problem of learning halfspaces under Gaussian distribution and adversarial label noise in the testable learning framework of Rubinfeld and Vasilyan (STOC'23). In this setup, the learning algorithm, given a few training examples drawn i.i.d. from some unknown distribution $\\mathcal{D}$, may either *accept* and returns a hypothesis or *reject*. The goal is to satisfy the following two natural constraints:\n- Completeness: If the marginal of $\\mathcal{D}$ is indeed Gaussian, the algorithm should accept w.h.p.\n- Soundness: The probability that the learning algorithm accepts and returns an inaccurate hypothesis is small.\n\nThe main result is a poly-time algorithm that works for the Gaussian distribution against adversarial label noise. In particular, if $\\mathsf{opt}$ is the smallest possible testing error achieved by the best halfspace on $\\mathcal{D}$, the algorithm guarantees $O(\\mathsf{opt}) + \\epsilon$ error in time $\\mathrm{poly}(d/\\epsilon)$. Prior work achieves $\\mathsf{opt} + \\epsilon$ error but requires $d^{\\mathrm{poly}(1/\\epsilon)}$ time.\n\nA first building block is a weak learner (given in Proposition 2.1) that outputs a weight vector $v$ that is $O(\\sqrt{\\mathsf{opt} + \\eta})$-close in time $d^{\\tilde O(1/\\eta^2)}$. (This is not sufficient due to the extra square root as well as the exponential dependence on $1/\\eta$.) This baseline learner is then boosted by localizing to the decision boundary of $\\mathrm{sgn}(v\\cdot x)$. In particular, each iteration either makes progress in improving the accuracy of $v$, or obtains a proof of non-Gaussianity in terms of moments.", "questions": "Following up on the weakness part, some discussion on whether/how the current technique could handle non-homogeneous halfspaces and/or the stronger agnostic learning guarantee would be helpful.", "limitations": "This work is purely theoretical and its limitations are in the assumptions (e.g., the concept class is the class of homogeneous halfspaces, and the \"reference distribution\" is a spherical Gaussian). This has been properly addressed in the paper (clearly stated in the abstract and the main paper).", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper studies a well-motivated and fundamental learning theory problem in the recently proposed model of testable learning. The results are strong, and the solution involves several novel and non-trivial ideas. Despite this complexity, the main paper is nicely written and achieves a great balance between intuition and technical details. I vote for accepting this paper.", "weaknesses": "The algorithm only handles the homogeneous halfspaces without a bias term, and cannot achieve the $\\mathsf{opt} + \\epsilon$ error guarantee as in the prior work of [RV22, GKK22].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the positive assessment of our work. \n\nFirst, regarding the limitation on the error guarantees (does not achieve OPT but only O(OPT)), we remark there is strong evidence that achieving error $OPT + \\epsilon$ in fully polynomial time under agnostic learning, even without the testable requirement, is hard. In particular, as shown in [DKPZ21], no statistical query algorithm can learn halfspaces under Gaussian marginal up to error $OPT +\\epsilon$ in time less than $d^{O(1/\\epsilon^2)}$. Moreover, the same result is shown to hold for general algorithms under standard cryptographic assumptions in [DKR23]. Given the aforementioned hardness results, the best one can hope to do with a polynomial time algorithm is to learn up to error $O(OPT)$. Our result is optimal in a sense that it achieves essentially the same error guarantee efficiently as in the absence of the testable requirements.\n\nSecondly, the reviewer raises the question whether our approach can be made to work with non-homogeneous halfspaces. We remark that, to the best of our knowledge, almost all prior literature for learning LTFs under adversarial noise is for homogeneous cases with only two exceptions [DKS18, DKTZ22]. We believe our approach can be extended for general LTFs but would give a bit worse error. We leave this as an interesting question for future work.\n\n[DKS18] Diakonikolas, I., Kane, D. M., & Stewart, A. (2018, June). Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1061-1073).\n\n[DKPZ21] Diakonikolas, I., Kane, D. M., Pittas, T., & Zarifis, N. (2021, July). The optimality of polynomial regression for agnostic learning under gaussian marginals in the SQ model. In Conference on Learning Theory (pp. 1552-1584). PMLR.\n\n[DKTZ22] Diakonikolas, I., Kontonis, V., Tzamos, C., & Zarifis, N. (2022, June). Learning general halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning (pp. 5118-5141). PMLR.\n\n[DKR23] Diakonikolas, I., Kane, D., & Ren, L. (2023, July). Near-optimal cryptographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. In International Conference on Machine Learning (pp. 7922-7938). PMLR.\n"}]

Author rebuttal:
## General Response 

We thank the reviewers for their time and effort in providing feedback. We are encouraged by the positive comments from reviewers for the following: (i) the **improved running time for testable learning halfspaces** from $d^{ \text{poly}(1/\epsilon) }$ to fully polynomial in all parameters (ii) the **optimality of the error guarantees** (Reviewers fkEL, 8SDJ, XEN1) and (iii) **the writing quality and the clarity of the presentation of the ideas** (Reviewers 8SDJ, XEN1). Additionally, as mentioned by reviewer 1kSW, we emphasize that another major strength of our algorithm is that it **works under the active learning setting requiring only $d \text{ } \text{poly} \log(1/\epsilon)$ labeled examples.** 

Below, we first address some common concerns and then provide responses to each individual reviewer in order.

**Learning under Gaussian Marginals**

 Two reviewers pointed out that our result is specific for Gaussian marginals. While generalizing our results to broader families of distributions is an interesting future direction, we remark that Gaussianity here is a natural assumption that has been commonly made in many prior works studying agnostic learning of halfspaces (see [DKKTZ21], [DKPTZ21], [DKZ20], etc.). Analogous to situations in the standard agnostic learning setting, understanding polynomial time testable learners in the Gaussian case can be seen as an important first step in achieving a universal theory of efficient testable learning under a variety of different distributions. We emphasize that our work is the first polynomial-time algorithm for testable learning halfspaces with near-optimal error guarantees that matches that without the testable requirement. Therefore, we view this is a natural and important first step in understanding efficient testable learning under more general marginal distributions.

Some reviewers also questioned the choice of our noise model. We remark that the adversarial noise model is theoretically well motivated, extensively studied, and also one of the strongest noise models in the literature. Hence, the error guarantees and runtime hold for all other weaker families of noise models as well. Whether the error guarantees can be improved under these weaker noise conditions is a direction we did not pursue but is a potential interesting future direction.

**Adversarial Noise Model**

Some reviewers also questioned the choice of our noise model. We remark that the adversarial noise model is theoretically well motivated, extensively studied, and also one of the strongest noise models in the literature. Hence, the error guarantees and runtime hold for all other weaker families of noise models as well. Whether the error guarantees can be improved under these weaker noise conditions is a direction we did not pursue but is a potential interesting future direction.


Meta-review: This paper studies the recently introduced testable learning model and studies the problem of robustly learning a halfspace. The paper presents a polynomial time algorithm that achieves the near optimal $O(OPT) + \epsilon$ guarantee. The reviewers liked the paper and concluded that the result is a solid theoretical contribution. One reviewer questioned the applicability of the testable learning model in real world settings and wondered whether the paper would be more suitable for a TCS venue. In my assessment, the paper fits well into the scope of NeurIPS. The authors are however encouraged to improve the writing and discuss more practical applications (both current and forward looking) of the model.
Decision: Accept (poster)