An Efficient Tester-Learner for Halfspaces
Authors: Aravind Gollakota
Adam Klivans
Konstantinos Stavropoulos
Arsen Vasilyan
Venue: ICLR 2024 poster (2024)
Keywords: testable learning
pac learning
agnostic learning
Massart label noise
adversarial label noise
distribution testing
Primary area: learning theory

Abstract: We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan [2022]. In this model, a learner certifies that the accuracy of its output hypothesis is near optimal whenever the training set passes an associated test, and training sets drawn from some target distribution must pass the test. This model is more challenging than distribution-specific agnostic or Massart noise models where the learner is allowed to fail arbitrarily if the distributional assumption does not hold. We consider the setting where the target distribution is the standard Gaussian in $d$ dimensions and the label noise is either Massart or adversarial (agnostic). For Massart noise, our tester-learner runs in polynomial time and outputs a hypothesis with (information-theoretically optimal) error $\mathrm{opt}+\epsilon$ (and extends to any fixed strongly log-concave target distribution). For adversarial noise, our tester-learner obtains error $O(\mathrm{opt})+\epsilon$ in polynomial time. Prior work on testable learning ignores the labels in the training set and checks that the empirical moments of the covariates are close to the moments of the base distribution. Here we develop new tests of independent interest that make critical use of the labels and combine them with the moment-matching approach of Gollakota et al. [2022]. This enables us to implement a testable variant of the algorithm of Diakonikolas et al. [2020a, 2020b] for learning noisy halfspaces using nonconvex SGD.

Published as a conference paper at ICLR 2024
AN EFFICIENT TESTER-LEARNER FOR HALFSPACES
Aravind Gollakota" Apple
Adam R. Klivans UT Austin
Konstantinos Stavropoulos
Arsen Vasilyan MIT
UT Austin
ABSTRACT
We give the first efficient algorithm for learning halfspaces in the testable learn- ing model recently defined by Rubinfeld and Vasilyan (RV23). In this model, learner certifies that the accuracy of its output hypothesis is near optimal when- ever the training set passes associated test, and training sets drawn from some target distribution must pass the test. This model is more challenging than distribution-specine agnostic Massart noise models where the learner is al- lowed to fail arbitrarily if the distributional assumption does not hold. We con- sider the setting where the target distribution is the standard Gaussian in d dimen- sions and the label noise is either Massart or adversarial (agnostic). For Massart noise, our tester-learner runs in polynomial time and outputs hypothesis with cenffommtiion-theoretttn
optimal) error opt (and extends to any fixed strongly log-concave target distribution). For adversarial noise, our tester-learner obtains error (optt) + in polynomial time. Prior work on testable learning ignores the labels in the training set and checks that the empirical moments of the covariates are close to the moments of the base distribution. Here we develop new tests of independent interest that make critical use of the labels and combine them with the moment- mathhnng approach of (GKK23). This enables us to implement testable variant of the algorithm of (KT7/20a DKTZ20b) for learning noisy halfspaces using nonconvex SGD.
INTRODUCTION
Learning halfspaces in the presence of noise is one of the most basic and well-studied problems in computational learning theory. A large body of work has obtained results for this problem under variety of different noise models and distributional assumptions (see e.g. (BH2I) for survey). A major issue with common distributional assumptions such as Gaussianity, however, is that they can be hard or impossible to verify in the absence of any prior information.
The recently defined model of testable learning (VV2)) addresses this issue by replacing such as- sumptions with efficiently testable ones. this model, the learner is required to work with an arbitrary input distribution Dxy and verify any assumptions it needs to succeed. It may choose to reject a given training set, but if it accepts, it is required to output a hypothesis with error close to opt(C, >xy),, the optimal error achievable over Dxy by any function in concept class C. Further, whenever the training set is drawn from a distribution Dxy whose marginal is truly a well-behaved target distribution D (such as the standard Gaussian), the algorithm is required to accept with high probability. Such an algorithm, or tester-learner, is then said to testably learn C with respect to target marginal D (See Definition (.11ttooonnn)))..) Note that unlike ordinary iistribution-speeiffe agnostic learners, a tester-learner must take some nontrivial action regardless of the input distribution.
The work of (V223 GKK23) established foundational algorithmic and statistical results for this model and showed that testable learning is in general provably harder than ordinary distribution- specific agnostic learning. As one of their main algorithmic results, they showed leareer for the class of halfspaces over Rd that succeed whenever the target marginal is Gaussian (or one of a more general class of distributions), achieving error opt + e in time and sample complexity
"aravindgécs . wtw.as.e........................ reaassedh. edu 'kli "klivans@cs utexas. edu Ikstavrop@cs. www.aaarppccsseeeaeseee utexss. edu Evasi yannmi edu

---

Published as a conference paper at ICLR 2024
dō(1/e"), This matches the running time of ordinary distribution-specifi agnostic learning of half- spaces over the Gaussian using the standard approach of (KKMS08). Their testers are simple and label-oblivious, and are based on checking whether the low-degree empirical moments of the un- known marginal match those of the target D
These works essentially resolve the question of designing tester-learners achieving error opt + e for halfspaces, matching known hardness results for (ordinary) agnostic learning (GGK20, DKZ20 DKPZ2I). Their running time, however, necessarily scales exponentially in 1/c.
A long line of research has sought to obtain more efficient algorithms at the cost of relaxing the optimality guarantee (ABLI7 DKSI8 DKT/20a DKT/20b). These works give polynomial-time algorithms achieving bounds of the form opt + and (Opt +e for the Massart and agnostic setting respectively under structured distributions (see Section 1.I for more discussion). The main question we consider here is whether such guarantees can be obtained in the testable learning framework.
Our contributions. In this work we design the first tester-learners for halfspaces that run in fully polynomial time in all parameters. We match the optimality guarantees of fully polynomial-time learning algorithms under Gaussian marginals for the Massart noise model (where the labels arise from a halfispace but are flipped by adversary with probability at most 7)) as well as for the agnostic model (where the labels can be completely arbitrary). In fact, for the Massart setting our guarantee holds with respect to any chosen target marginal D' that is isotropic and strongly log-concave, and the same is true of the agnostic setting albeit with a slightly weaker guarantee.
Theorem 1.1 (Formally stated as Theorem 4.1. Let C be the class of origin-centered halfspaces over TRd, and let D be any isotropic strongly log-concave distribution.
the setting where the labels are corrupted with Massart noise rate at most 1j <. 2.2 C can be testably learned w.r.. D up error opt + using poly(d, :,- 1-27) time and sample complexity.
Theorem 1.2 (Formally stated as Theorem 5.1). Let C be as above. In the adversarial noise or agnostic setting where the labels are completely arbitrary, C can be testably learned w.r.t (O, La) up to error (opt + using poly(d, }) time and sample complexity.
Our techniques. The tester-learners we develop are significantly more involved than prior work on testable learning. We build on the nonconvex optimization approach to learning noisy halfspaces due to (DKTZ20al DKTZ20b) as well as the structural results on fooling functions of halfspaces using moment matching due to (GKK23). Unlike the label-oblivious, global moment tests of (RV23) GKK23), our tests make crucial use of the labels and check local properties of the distribution in regions described by certain candidate vectors. These candidates are approximate stationary points of a natural nonconvex surrogate of the 0-1 loss, obtained by running gradient descent. When the distribution is known to be well-hehaved, (DKT7200) DKT220b) showed that any such stationary point is in fact a good solution (for technical reasons we must use a slightly different surrogate loss). Their proof relies crucially structural geometric properties that hold for these well-behaved distributions, an important one being that the probability mass of any region close to the origin is proportional to its geometrie measure.
In the testable learning setting, we must efficiently check this property for candidate solutions. Since these regions may be described intersections of halfspaces, we may hope apply the moment- matching framework of (GKK23). Naively, however, they only allow us to check in polynomial time that the probability masses of such regions are within an additive constant of what they should be under the target marginal. But we can view these regions as sub-regions of a known band described by our candidate vector. By running moment tests on the distribution conditioned on this band and exploiting the full strength of the matching framework, we are able to effectively convert our weak additive approximations to good multiplicative ones. This allows us argue that our stationary points are indeed good solutions.
Independent and Subsequent Works. In this paper we provide the first efficient tester-learners for halfspaces when the noise is either adversarial or Massart. In independent and concurrent work by OOKK+23) an efficient tester-learner for homogeneous halfspaces achieving error (opt) + e for Gaussian target marginals is also provided, but they do not provide any results for arbitrary strongly log-concave target marginals (see Theorem 5.1) or a guarantee of opt + e for Massart noise. In techniques were used to provide tester-learners that are not
subsequent work by (GKSV23), tailored to a single target distribution, but are guaranteed to accept any member of a large family of distributions. Although their main results are more general, their approach crucially extends our
2

---

Published as a conference paper at ICLR 2024
approach here. Moreover, on the technical side, the proof we give here shows how to make use of the moment- approach of (GKK23) to provide fully polynomial efficient lester-leamers, which might be of independent interest.
1.1 RELATED WORK
We provide a partial summary of some of the most relevant prior and related work on efficient algorithms for learning halfspaces in the presence of adversarial label Massart noise, and refer the reader to (BH21) for a survey.
In the distributionnspeccfic agnostic setting where the marginal is assumed to be isotropic and log- concave, (KLS09) showed algorithm achieving error (s) for the class of origin-centered halfspaces. (ABL17) later obtained (opp) + e using an approach that introduced the principle of it- erative localization, where the learner focuses attention on band around candidate halfspace in der to produce an improved candidate. (Dan15) used this principle to obtain a PTAS for agnostically learning halfspaces under the uniform distribution on the sphere, and (BZ17) extended it more general s-concave distributions. Further works in this line include (YZ17) Zhal8 88 ZSA20) (ZL21). (DKTZ20b) introduced the simplest approach yet, based entirely on nonconvex SGD, and showed that it achieves +e for origin-centern centered halfspaces over a wide class of structured distributions. Other related works include (DKS18) DK2222).
In the Massart noise setting with noise rate bounded by 17. work of (GTT19) gave the first effi- cient distribution-free algorithm achieving error 7) + c; further improvements and followups include (DKT21 DTK22). However, the optimal error opt achievable by a halfspace may be much smaller than 7,, and it has been shown that there are distributions where achieving error competitive with opt as opposed to 77 is computationally hard (DK22) DKMR22). As a result, the distribution-speciie setting remains well nell-motivated for Massart noise. Early distributionnsseciine algorithms were given the nonconvex SGD approach introduced by
by (ABHUI5 (AHHZ16), but a key breakthrough (KKT720a), which achieved error opt + for origin-centered halfspaces efficiently over a wide range of distributions. This was later generalized by (DKK -2)).
1.2 TECHNICAL OVERVIEW
Our starting point is the nonconvex optimization approach to learning noisy halfspaces due to (DKTZ20a DKTZ20b). The algorithms in these works consist of running SGD on a natural non- convex surrogate L. for the 0-1 loss, namely a smooth version of the ramp loss. The key structural property shown that the marginal distribution is structured (e.g. log-concave) and the slope of the ramp is picked appropriately, then any w that has large angle with an optimal w cannot be an approximate stationary point of the surrogate loss L,, i.e. that [VL,(w)) must be large. This proven by carefully analyzing the contributions to the gradient norm from certain critical regions of span(w, (w, w*), and crucially using the distributional assumption that the probability masses of these regions are proportional to their geometric measures. (See Fig. 3 In the testable learning setting, the main challenge we face in adapting this approach checking such a property for the unknown distribution we have access to.
A preliminary observation is that the critical regions of span(w, w*) that we need to analyze are rectangles, and are hence functions of small number of halfspaces. Encouragingly, structural results of the prior work of (GKK23) pertains to "fooling" such functions. Concretely, they
of the key
show that whenever the true marginal Dx matches moments of degree at most Õ(1/7²) with target D' that satisfies suitable concentration and anticoncentration properties, then EDx [efl-E--I [f] < for any / that is a function of a small number of halfspaces. If we could run such a test and ensure that the probabilities of the critical regions over our empirical marginal are also related their areas, then would have similar stationary point property. However, the difficulty is that since wish to run in fully polynomial time, we can only hope to fool such functions up to T that a constant. Unfortunately, this is not sufficient analyze the probability masses of the critical regions care about as they may be very small.
The chief insight that lets get around this issue is that each critical region R in fact of very spe- cific form, namely a rectangle that axis- axis-aligned with w: R = (x: (w,x) E [-o, oj and (v.x) e (a, 38} for some values a, 3, and some v orthogonal w. Moreover, know w, meaning
3

---

Published as a conference paper at ICLR 2024
can efficiently estimate the probability PDy E I-o, a]l up to constant multiplicative factors without needing moment tests. Denoting the band {x (w,x) E =I-o,o]] o]} by T and E Pp [T], PDxl(v.x) ((v.)) E [o.33] x E = (11), as this is what would occur under the structured target distri- bution D (Such a "localization" property is also at the heart of the algorithms for approximately learning halfspaces of, c.g., (ABL17 Dan To check this, it suffices to run tests that ensure that PDx x) [a, 3]
writing P PDx [R] PD x) E [a,
it turns out that we should expect
'] is within an additive constant of this probability under D
We can now describe the core of our algorithm (omitting some details such as the selection of the slope of the ramp). First, we run SGD on the surrogate loss L arrive at an approximate stationary point and candidate vector w (technically list of such candidates). Then, we define the band T based on w, and run tests on the empirical distribution conditioned on T. Specifically, we check that the low-degree empirical moments conditioned on T match those of D conditioned on T, and then apply the structural result of (GKK23) to ensure conditional probabilities of the form FD [(v, x) [ax, 3] E T"] match I' [(vx)) E [ax x E 7] up to suitable additive constant. This suffices to ensure that even over our empirical marginal, the particular stationary point w we have is indeed close in angular distance to an optimal w".
A final hurdle that remains, often taken for granted under structured distributions, is that closeness in angular distance Z(w, w*) does not immediately translate to closeness in terms of agreement, P(sign((w
# sign( (w"" x)]], over our unknown marginal. Nevertheless, we show that when the target distribution is Gaussian, we can run polynomial-time tests that ensure that an angle of 0 = Z(w, w*) translates to disagreement of at most O(0). When the target distribution is a general strongly log-concave distribution, we show slightly weaker relationship: for any k E N, we can run tests requiring time d((k) that ensure that an angle of A translates to disagreement of at most O(Vk g1-1 In the Massart noise setting, we can make L(w, w") arbitrarily small, and so obtain our opt + guarantee for any target strongly log-concave distribution in polynomial time. In the adversarial noise setting, we face a more delicate tradeoff and can only make <(w, w*) as small as (optt.. When the target distribution Gaussian, this enough to obtain final error (opt) + e in polynomial time. When the target distribution is a general strongly log-concave distribution, we instead obtain Ö(pt)) + in quasipolynomial time.
2 PRELIMINARIES
Notation and setup Throughout, the domain will be X = Rd, and labels will lie in ) = {+ The unknown joint distribution over X' x y that we have access to will be denoted by Dxy, and its marginal on X' will be denoted by Dx The target marginal on X will be denoted by D*. We use the following convention for monomials: for a multi-index a = (ai....,ad)
ad) E Z x" denotes II oF', and |al = Σ, a; denotes its total degree. We use C to denote a concept class mapping Rd to [+1], which throughout this paper will be the class of halfspaces or functions of halfspaces over Rd. We use pot(C,Dx>) to denote the optimal error inf F(x.)))Dxy If(x) # v). just opt when C and Dxy are clear from context. We recall the definitions of the noise models we consider. In the Massart noise model, the labels satisfy Py>-Dxyllly # sign( (w" x)) x] = n(x), where rx(x) S 1 < 1/ for all x. In the adversarial label noise or agnostic model, the labels may be completely arbitrary. In both cases, the learner's goal is to produce a hypothesis with error competitive with opt. We now formally define testable learning. The following definition is an equivalent reframing of the original definition (RV23 Def 4), folding the (label-awarg tester and learner into a single tester-learner.
Definition 2.1 (Testable learning, (RV2))). Let C be a concept class mapping Rd {=1}. Let D* be a certain target marginal on Iidd. Let 6,6 > O be parameters, and let và : [0. 1] - [0 be some function. We say C can be testably learned w.r.t. D" up to error ('ppt) + e with failure probability 6 if there exists tester-learner A meeting the following specification. For any distribution Dxy on Rd x 1+11.44 A takes in a large sample S drawn from Dxy, and either rejects S or accepts and produces hypothesis h. gd + [+1}. Further, the following conditions must be met:
(a) (Soundness.) Whenever A accepts and produces a hypothesis h, with probability at least 1- 8 (over the randomness of S and A), h must satisfy P P(x.a) [h(x) # y] S (opt((C, Dxy)) +c.
4

---

Published as a conference paper at ICLR 2024
(b) (Completeness.) Whenever Dxy truly has marginal D", A must accept with probability least 8 (over the randomness S and A).
TESTING PROPERTIES OF STRONGLY LOG-CONCAVE DISTRIBUTIONS
In this section we define the testers that we will need for our algorithm. All the proofs from this section can be found in Appendix B We begin with a structural lemma that strengthens the key structural result of (KK23),, stated here as Proposition A.3 It states that even when we restrict an isotropic strongly log- log-concave D to band around the origin, moment matching suffices to fool functions of halfspaces whose weights are orthogonal the normal of the band.
Proposition 3.1. Let D be isotropic strongly log-concave distribution. Let w E &Sd-1 be any a function of halfspaces of the form in for all i.
fixed direction. Let p be a constant. Let f IR'' + R be Eq. (A.2). with the additional restriction that its weights v* E gd-1 satisfy (v', (v',w) For some a E [0, 11, let T denote the band {x [(w, S 5.) Let D be any distribution such that Dir matches moments of degree most l ((1/7) with Dir up to additive slack of d (-0)) Then [E>~ [ T - En T] ST.
We now describe some of the testers that we use. First, we need a tester that ensures that the distribution concentrated in every single direction. More formally, the tester checks that the moments of the distribution along any direction are small.
Proposition 3.2. For any isotropic strongly log-concave D", there exists some constants C₁ and a tester T1 that takes set S S Rd {=1}, even k N, parameter ö E (0, and runs and in time poly (dh [8], }). Let D denote the uniform distribution over S. IfT, accepts, then for any gd-1
E (x,y)~
{ (C11)//22.
(3.1)
Moreover, if is obtained by taking at least (dog (1og)) )) C1
i.i.d. samples from distribution whose -a-miinnaal is D", the test T1 passes with probubility at least 1 8.
Secondly, we will use a tester that makes sure the distribution is not concentrated too close to spe- cific hyperplane. This is one of the properties we will need to use order to employ the localization technique of (ABL17).
Proposition 3.3. For any isotropic strongly log- og-coocavee D", there exist some constants C2. Cs and tester T3 that takes set S C Rd x {+1} vector w gi--) parameters ö E (0, 1) and runs in time poly (d. [S], log }). Let D denote the uniform distribution over S. If accepts, then
P (x,))~
IK,. x) S d) (C2a,Cza)
(3.2)
Moreover, if S is obtained by taking least 100 K,o² log (3) i.i.d. samples from distribution whose Rd -arainnaall is D*, the test T2 passes with probability at least 6.
Finally, in order to use the localization idea of (BL17)) in manner similar to (DKTZ20b) need to make sure that the distribution is well-behaved also within a band around to a certain hyper- plane. The main property of the distribution that establish is that functions of constantly many halfspaces have expectations very close to what they would be under our distributional assumption. As we show later in this work, having the aforementioned property allows us derive many other properties that strongly log-concave distributions have, including many of the key properties that make the localization technique successful.
Proposition 3.4. For any isotropic strongly log-concave D and a constant C₁ there exists constant CG and a tester T3 that takes a set S Rd {+1} a vector
gi-1, parameters O (0, 1) and runs in time poly 0 (2), 3. 18), 4) Let D denote the uniform distribution over S, lei T denote the band {x ((w,x) x) So} and let Fo denote the set {+1)
functions functtoon of C₁ halfspaces whose weight vectors are orthogonal to w. If accepts, then
max JEFu
E X
[f(x)
E (x,)) (f(x) x (X ST,
(3.3)
5

---

Published as a conference paper at ICLR 2024
max VEB4-1; (V,W)=0 X
E [((v
X
[((v, x)) x ETT ST.
(3.4)
(x.0)
Moreover, if S is obtained by taking at least ( d log (+) (log 2) log logg Co.
iidd
samples from a distribution whose Hd -marginnal is D the test T's passes w.p. at least 1 6.
4 TESTABLY LEARNING HALFSPACES WITH MASSART NOISE
In this section we prove that we can testably learn halfspaces with Massart noise with respect to isotropic strongly log-concave distributions (see Definition [.T].
Theorem 4.1 (Tester-Learner for Halfspaces with Massart Noise). Let Dxy be a distribution over R x { and let D be an isotropic strongly log-concave distribution over IR4, Let be the class of origin centered halfspaces in R. Then, for any 1) < 1/2, > O and ê E (0, 1), there exists an algorithm [Algorithm]] 7 that testably learns w.r.t. D up to excess error e and ervor probability most in the Massart noise model with rate most 17, using time and mumber of samples from Dxy that are polynomial in d, 1/c, 1- and 1og(1/5)
Algorithm 1: Tester-learner for halfspaces
Input: Training sets S1, S2, parameters ar, 8,
Output: A near-optimal weight vector w. or rejection
Run PSGD on the empirical loss La over S1 to get list L of candidate vectors. Test whether L contains an a-approximate stationary point w of the empirical loss C, over S2. Reject if such w exists.
for each candidate w' in [w,-w] do
Let Bw)(o) denote the band {x : (ww,x)] S.j.
Let Fw denote the class of functions of at most two halfspaces with weights orthogonal w'.
Let 8' (6))
Run (S2, k = 2,8) to verify that the empirical marginal is approximately isotropic.
Reject if Ti rejects.
Run (2( w',a,5') to verify that Bw = ((r). Reject if T2 rejects. o o/6, T, 8') and Ts(S, w', a 0/2, r, 8') for suitable constant to verify that the empirical distribution conditioned on B (a/6) and Bw (a/2) fools Fw
Run (S2, w',
up to r. Reject if T3 rejects.
Estimate the empirical eтror of w' on S.
If all tests have accepted, output w' (w, w with the best empirical error.
To show our result, revisit the approach of (DKTZ20a) for learning halfspaces with Massart noise under well-behaved distributions. Their result based on the idea of minimizing a surrogate loss that is non convex, but whose stationary points correspond to halfspaces with low error. They also require that their surrogate loss is sufficiently smooth, so that one can find stationary point efficiently. While the distributional assumptions that are used demonstrate that stationary points of the surrogate loss can be discovered efficiently are mild, the main technical lemma, which de- mostrates that any stationary point suffices, requires assumptions that are not necessarily testable. We establish label-dependent approach for testing, making use of tests that are applied during the course of our algorithm.
We consider slightly different surrogate loss than the one used in (DKTZ20a). In particular, for o O, we let
E lo (c(- (w, x |w||2
C. (w)
(4.1)
(xxy)>Dxy>
where lo : - 10, is smooth approximation to the ramp function with the properties described in Proposition C. (see Appendix C). obtained using a piecewise polynomial of degree 3. Unlike the standard logistic function, It] > o/2). This makes the analysis of the gradient of C, casier, since the contribution from points lying outside certain band is exactly 0.
loss function has derivative exactly 0 away from the origin (for

---

so that Published as a conference paper at ICLR 2024
The smoothness allows to run PSGD to obtain stationary points efficiently, and we now state the convergence lemma we need.
Proposition 4.2 (PSGD Convergence, Lemmas 4.2 and B.2 in DKTZ220)). Let Lar be as Equa-
lion equation 4.7 with E 10. ta as described in Proposition C.I and Dxy such that the marginal Dx on Ted satisfies Property equation for
2. Then, Jor any e > and E (0, 1), there is an algorithm whose time and sample complexity is O( + eto which, having access to samples from Dxy, outputs a list L of vectors w E g with | =($ + 1og(1/0)) there exists w L with
Who (w))l2 S e, with probability at least 1 6.
In particular, the algorithm performs Stochastic Gradient Descent on Co Projected on Sd-1 (PSGD).
It now suffices to show that, upon performing PSGD on La, for some appropriate choice of we acquire a list of vectors that testably contain a vector which is approximately optimal. We first prove the following lemma, whose distributional assumptions are relaxed compared to the corresponding structural Lemma 3.2 of (DKT/20a). In particular, instead of requiring the marginal distribution to be "well-behavedf, expected values under the true marginal distribution that are close, up to multiplicative factors, their expected values under some "well-behaved" (in fact, strongly log-concave) distribution. While some of the quantities of interest have values that are miniscule and estimating them up to multiplicative factors could be too costly, turns out that the source of their vanishing scaling can be completely attributed to factors of the form (l x)| I a) (where o is small), which, due to standard concentration arguments, can be approximated up to multiplicative factors, given w E gd-1 and > O (see Proposition 3.3). As result, we may estimate the remaining factors up to sufficiently small additive constants (see Proposition 3.4b to get multiplicative overall closeness to the "well behaved" bascline. We defer the proof of the following Lemma to Appendix C.1
assume that the quantities of interest (for the purposes of our proof) have
Lemma 4.3. Let L.r be as in Equation equation 4. with E (0, 1). la described in Proposition C.I. let w E S and consider Dxy such that the marginal Dx on Rd satisfies Properties equa- tion 3.2 and equation for C4 = 2 and accuracy Let * E Sd-1 define optimum halfspace and let < 1/2 be an upper bound on the rate of the Massart noise. Then, there are constants
C1, C2 C3 > 0 such that if Wo (o)((())l
(w)ll2 c1(1 2n) and I C2 then
(w,
C3
ww)
C3
2n
21
Combining Proposition 4.2 and Lemma 4.3 we get that for any choice of the parameter E (0, 1], by running PSGD on Lg. we can construct a list of vectors of polynomial size (in all relevant parameters) that testably contains a vector that is close to the optimum weight vector. In order to link the zero-one loss to the angular similarity between a weight vector and the optinum vector, we use the following Proposition (for the proof, see Appendix C.2).
Proposition 4.4. Let Dxy be a distribution over Rd x {+1,, w" E arg migg Pxy ly of sign((w (w, and w E gd-1, Then, for any 0 > L(w, w ). 0 E 7/4,, if the marginal Dx on Rd satisfies Property equation 3.7 for C1 > and some even k E N and Property equation 3.2 with
set to (Cik)acéts)
2c2t1) (tan 0 then, there exists constant >> 0 such that the following is true.
IP ly + sign (w, x)) I opt + c 41/2 + Dxy
Throughout the proof we consider 8' to be sufficiently small polynomial in all the relevant parameters. Each of the failure events will have probability at least 8 and their number will be polynomial in all the relevant parameters, so by the union bound, we may pick 8' so that the probability of failure is most 6.
Proof of Theorem 4.7
The algorithm we run is Algorithm| [] with appropriate selection of parameters and given samples sufficiently large sets of independent samples from the true unknown
S1, S2, each of which distribution Dxy. For some a e (0, to be defined later, we run PSGD on the empirical loss E, over Si described in Proposition 4.2 with c1(1 - 22)) /4/, where e is given by Lemma 4.3
7

---

Published as a conference paper at ICLR 2024
G
G
A
42
A
tan
G
We analyze the contributions of the regions labeled A1, A2 to the quantities AI,A2 in the proofs. Specifically, the regions A₁ (which have height a //3 so that the value of é (xw) for any x in these regions is exactly 1/a, by Proposition C.1 form subset of the region g, and their probability mass under Dx (up to a multiplicative factor) a lower bound on the quantity A1 (see Eq equation C.3). Similarly, the region A2 is subset of the intersection of G with the band of height 0, and has probability mass that is (up to a multiplicative factor) an upper bound on the quantity A2 (see Eq equation C.4
Figure 1: Critical regions in the proofs of main structural lemmas (Lemmas 4.3 5.2)
By Proposition 4.2 we get list I. of vectors w E Sd-1 with [T] poly (d, 1/a) such that there is W L with Co (w)ll2 3c 2n) under the true distribution, if the marginal isotropic.
Having acquired the list L using sample Si, we use the independent samples in S2 to test whether L contains an approximately stationary point of the empirical loss on S2. If this not the case, then we may safely reject: for large enough |S1] if the distribution is indeed isotropic strongly logconcave. there an approximate stationary of the population loss L and if [St] is large enough, the gradient of the empirical loss on S2 will be close to the gradient of the population loss on each of the elements of T., due to appropriate concentration bounds for log-concave distributions as well as the fact that the elements of I. are independent from Sz. For the following, let w be point such that W/ (w) < c1 2n)) under the empirical distribution over S2
In Lemma 4.3 and Proposition 4.4 we have identified certain properties of the marginal distribution that are sufficient for our purposes, given that contains an approximately stationary point of empirical (surrogate) loss on S2. Our testers Ti, T2, T3 verify that these properties hold for the empirical marginal over our sample S2, and it will be convenient to analyze the optimality of our algorithm purely over S2. In particular, that when the true marginal indeed the target D" our testers succeed with high probability (for the corresponding sample complexity, see Propositions 3.2 3.3 and 3.4h. Moreover, by standard generalization theory, since the VC dimension of halfspaces is only O(d) and for us SS2] is large (d, 1/e), both the error of final output and the optimal error over S2 will be close that over Dxy. So in what follows, we will abuse notation and refer to the uniform distribution over S as Dxy and the optimal error over S₂ simply as opt.
will need require that [Sa] is sufficiently large, so
We proceed with some basic tests. Throughout the rest of the algorithm, whenever a tester fails, we reject, otherwise we proceed. First, we run testers T2 with inputs (w, 0//2, 5') and (w, a /6, 8') (Proposition 3.3) and T3 with inputs (w, 0/2, c22 8') and with (w, a/, c2, 5') (Proposition 3.4 02 as defined Lemma 4.3). This ensures that for the approximate stationary point w of the L., the probability within the band (a (a/2) (x ([w, x) < a/2) is ((a) (and similarly for Bw (a (a/6)) and moreover that our marginal conditioned on each the bands fools (up to an additive constant) functions of halfspaces with weights orthogonal to As a result, may apply Lemma 4.3 to 2n)
and form a list of vectors {w, - w which contains some w' with L(w', w*) < C20
(where cg is as defined in Lemma 4.3
8

---

Published as a conference paper at ICLR 2024
We run Ti (Proposition 3.2) with A 2 to verify that the marginals approximately isotropic and we use T3 once again, with appropriate parameters for each w and its negation, to apply Proposition 4.4 and get that {w.- - contains vector w' with
Iu + sign((w', x\)] opt c 0 where L(w', w*) S 0 c20/ V1 2n Dxy
P
By picking ((23/2(1- 21)) we have P. Iy + sign((w', xx)] S opt E.
Dxy
However, we do not know which of the weight vectors in {w. -w) is the guaranteed to achieve small error. In order to discover this vector, we estimate the probability of error of each of the corresponding halfspaces (which can be done efficiently, due to Hoeffding's bound) and pick the one with the smallest error. This final step does not require any distributional assumptions and we do not need perform any further tests.
5 TESTABLY LEARNING HALFSPACES THE AGNOSTIC SETTING
In this section, we provide our result on efficiently and testably learning halfspaces in the agnostic setting with respect to isotropic strongly log-concave target marginals. We defer the proofs to Ap- pendix D The algorithm we use is once more Algorithm[]] but we call it multiple times for different choices of the parameter a, reject if any call rejects and output the vector that achieved the mini- mum empirical error overall, otherwise. Also, the tester Ti is called for a general (not necessarily k 2).
Theorem 5.1 (Efficient Tester-Learner for Halfspaces in the Agnostic Setting). Let Dxy be a dis- tribution over Rd x {=1} and let D be strongly log-concav distribution over RR (Definition A.7) Let C be the class of origin centered halfspaces in R.. Then, for any even k E N, any and 5 E 1), there exists an algorithm that agnostically testably learns C w.r.t. D up to error 02. ボ4f) cc, where opt = min P Dxy ly + sign((w: (w, x)), and error probability at most 6, using time and a number of samples from Dxy that are polynomial in d d0()) (1/c))(()) and (log(1/5) ((k)) In particular, by picking some appropriate k < logg d, we obtain error Ö(opt) + quasipolynomial time and sample complexity, i.e. poly poly(2polylog (2polylog ( (o)yoyyoo..).
To prove Theorem 5.1 we may follow a similar approach as the one we used for the case of Massart noise. However, in this case, the main structural lemma regarding the quality of the stationary points involves an additional requirement about the parameter a. In particular, o cannot be arbitrarily small with respect the error of the optimum halfspace, because, in this case, there is upper bound on the amount of noise that any specific point x might be associated with. As a result, picking o to be arbitrarily small would imply that algorithm only considers points that lie within region that has arbitrarily small probability and can hence be completely corrupted with the adversarial opt budget. On the other hand, the polynomial slackness that the testability requirement introduces (through Proposition 4.4) between the error we achieve and the angular distance guarantee we can get via finding stationary point of L. (which is now coupled with opt), appears the exponent of the guarantee we achieve in Theorem 5.1
Lemma 5.2. Let Lo be in Equation equation 4.1 with E (0, 1]. la described in Proposition C.1 let w E gd-1 and consider Dxy such that the marginal Dx on Rd satisfies Properties equa- lion equation 3.33 and equation 3.4 3.4for with C4 = and accuracy parameler T. Let opt be the minimum error achieved by some origin centered halfspace and let w E &dd-1 be a corresponding vector. Then, there are constants C12 C2, C32 C4 > O such that opt S C1O, Wo (w)ll2 < C2 and
T S C3 then either L(w, S C1σ or 2( W ww") S C4O.
We obtain our main result for Gaussian target marginals by refining Proposition 4.4 for the specific case when the target marginal distribution D* is the standard multivariate Gaussian distribution. The algorithm for the Gaussian case is similar to the one of Theorem 5.1 but it runs different tests for the improved version (see Proposition D.I) of Proposition 4.4
Theorem 5.3. In Theorem 5.7 if D* is the standard Gaussian in dimensions, we obtain error (opt) + in polynomial time and sample complexity, i.e. poly(d, 1 1/e, log(1/8))-

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We wish to thank the anonymous reviewers of ICLR 2024 for their constructive feedback. Aravind Gollakota was at UT Austin while this work was done, supported by NSF award AF-1909204 and the NSF Institute for Foundations Machine Learning (IFML). Adam R. Klivans was sup- ported by NSF award AF-1909204 and the NSF AI Institute for Foundations of Machine Learning (IFML). Konstantinos Stavropoulos was supported by NSF award AF-1909204, the NSF AI Insti- tute for Foundations of Machine Learning (IFML), and by scholarships from Bodossaki Foundation and Leventis Foundation. Arsen Vasilyan was supported in part by NSF awards CCF-2006664, DMS-2022448, CCF-1565235, CCF-1955217, CCF-2310818 18, Big George Fellowship and Fin- lech@CSAIL. Part of this work was done while Arsen Vasilyan was visiting UT Austin.
REFERENCES
[ABHU15] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Umer. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory, pages 167-190. PMLR, 2015.
[ABHZ16] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learn- ing and 1-bit compressed sensing under asymmetric noise. In Conference on Learning Theory, pages 152-192. PMLR, 2016.
[ABL17] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localiza- tion for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
[BH21] Maria-Florina Balcan and Nika Haghtalab. Noise in classification, Beyond the Worst- Case Analysis of Algorithms, page 361, 2021.
[BZ17] Maria-Florina F Balean and Hongyang Zhang. Sample and computationally efficient learning algorithms under s-concave distributions. Advances in Neural Information Processing Systems, 30, 2017.
[Dan15] Amit Daniely. A ptas for agnostically learning halfspaces. In Conference Learning Theory, pages 484-502. PMLR, 2015.
[DGT19] Iliss Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indeeenden pac learning of halfspaces with massart noise. Advances in Neural Information Pro- cessing Systems, 32, 2019.
[DK22] Ilias Diakonikolas and Daniel Kane. Near-optimal statistical query hardness of learn- ing halfspaces with massart noise. In Conference on Learning Theory, pages 4258- 4282. PMLR, 2022.
[DKK+22] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. In Proceedings the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 874-885, 2022.
[DKK+23] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Sihan Liu, and Nikos Zarifis. Efficient testable learning of halfspaces with adversarial label noise. arXiv preprint arXiv:2303.05485 2023.
[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.
[DKPZ21] Ilias Diakonikolas, Daniel M Kane, Thanasis Pittas, and Nikos Zarifis. The optimal- ity of polynomial regression for agnostic learning under gaussian marginals in the sq model. In Conference Learning Theory, pages 1552-1584. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2024
[DKS18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061-1073, 2018.
[KT221] Ilias Diakonikolas, Daniel Kane, and Christos Tzamos. Forster decomposition and learning halfspaces with noise. Advances in Neural Information Processing Systems, 34:7732-7744, 2021.
[DKTZ20a] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learn- ing 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 Neural Information Processing Systems, 11185500-85499 2020.
[DKTZ22] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspaces with adversarial label noise via online gradient descent. In Interna- tional Conference on Machine Learning, pages 5118-5141. PMLR, 2022.
[DKZ20] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems, 33: 15:16-1861555 13596, 2020.
[DTK22] Ilias Diakonikolas, Christos Tzamos, and Daniel M Kane. A strongly polynomial algorithm for approximate forster transforms and its application to halfspace learning. arXiv preprint arXiv:2212.03008. 2022.
[GGK20] Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33:2147- 2158, 2020.
[GKK23] Aravind Gollakota, Adam R Klivans, and Pravesh K Kothari. moment- matteng approach testable learning and new characterization of rademacher complexity. Proceedings of the fifty-fifth annual ACM Symposium on Theory of Computing, 2023.
To appear.
[GKSV23] Aravind Gollakota, Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Tester-learners for halfspaces: Universal algorithms. arXiv preprint 1765,, 2023.
[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Ag- nostically learning halfspaces. SIAM Journal on Computing, 37 2008.
[KLS09] Adam R Klivans, Philip M Long, and Rocco A Servedio. Learning halfspaces with malicious noise. Journal of Machine Learning Research, 10(12), 2009.
[RV23] Ronitt Rubinfeld and Arsen Vasilyan. Testing distributional assumptions of learning algorithms. Proceedings of the fifty-fifth annual ACM Symposium on Theory of Com- puting, 2023. To appear.
[SW14] Adrien Saumard and Jon A Wellner, Log-concavity and strong log-concavity: a review. Statistics surveys, 8:45, 2014.
[YZ17] Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. Advances in Neural Information Processing Systems, 30, 2017.
[Zha18] Chicheng Zhang. Efficient active learning of sparse halfspaces. In Conference on Learning Theory, pages 1856-1880. PMLR, 2018.
[ZL21] Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning half- spaces with massart and tsybakov noise. Conference on Learning Theory, pages 4526 4527. PMLR, 2021.
11

---

Published as a conference paper at ICLR 2024
[ZSA20] Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspacces with arbitrary bounded noise. Advances in Neural Information Processing Systems, 33:7184-7197, 2020.
12

---

Published as a conference paper at ICLR 2024
A STRONGLY LOG-CONCAVE DISTRIBUTIONS
We also formally define the class of strongly log-concave distributions, which is the class that our larget marginal D is allowed to belong to, and collect some useful properties of such distributions. We will state the definition for isotropic D* (i.e. with mean and covariance Z) for simplicity.
Definition A.1 (Strongly log-concave distribution, see e.g. (SW14) Def 2.8)). We say an isotropic distribution D R4 is strongly log-coneave if the logarithm of its density q a strongly concave function. Equivalently, can be written as
g(x) = 7(2))
(A.1)
some log-concave function r and some constant k > O, where 7,21 denotes the density of spherical Gaussian (0, x²1).
Proposition A.2 (see e.g. (SW14). Let D be an isotropic strongly log-concave distribution on R with density q.
(a) Any orthogonal projection of D onlo subspace is also strongly log-concave.
(b) There exist constants U, R such that q(x) S U for all and g(x) 2 1/U for all ||x|| s R.
(c) There exist constants U' and i. such that q(x) S (')xar( for all x.
(d) There exist constants K1, K2 such that for any a E [0, 1] and any v E gd P S
a) E (K1a, K20)..
(e) There exists a constant K3 such that for any E N. BII( x) x (Kzk)&/2
(f) Let a (a1,...,.al) E Z be multi-index with total degree |o|| = Σ, aj = k, and let
II, x. There exists a constant K4 such that for any such a, xx1 S (K,
For (a), see e.g. (SW14 Thm 3.7). The other properties follow readily from Eq. A. which allows us to treat the density as subgaussian.
A key structural fact that will need about strongly log- log-coneave distributions is that approximately matching moments of degree at most ((1/²2) with such a 1 sufficient fool any function of constant number of halfspaces up to an additive т.
Proposition A.3 (Variant (GKK23) Thm 5.6)). Let p be a fixed constant, and let F be the class of all functions of p halfspaces mapping IRd {+1} of the form
f(x) = g (sign((v), x) + 01)..... sign (v": + 0p))
(A.2)
for some g {+1]2 + {+1) and weights v E Sd-1 Let D be any target marginal such that for every i, the projection (v', vxxx x) has subgaussian tails and anticoncentrated: (a) Pll(vv, ,x) > t) S exp(=O((t)), and (b) for any interval (a,b), Pl((",, xx) [a, < 0(16 -a)). Let D be any distribution such that for all monomials x = =II. x of total degree |ax] = E, as S k,
c/ar|
lal
|x - - < D
E
dvw
for some sufficiently small constant (in particular, it suffices to have d O(k) moment closeness for every a). Then
max
EIAI < FEF
Note that this is a variant of the original statement of (GKK23 Thm 5.6), which requires that the 1D projection of D along any direction satisfy suitable concentration and anticoncentration. Indeed, an inspection of their proof reveals that it suffices to verify these properties for projections only along the directions {v' Jeeppi as opposed to all directions. This is because to fool function f of the form above, their proof only analyzes the projected distribution .x)..., (v", x)) on RP, and requires only concentration and anticoncentration for each individual projection (v x).
13

---

Published as a conference paper at ICLR 2024
B PROOFS FOR SECTION 3
B. PROOF OF PROPOSITION 3.1
Our plan is to apply Proposition A.3 To do so, we must verify that Dr satisfies the assumptions required. particular, suffices to verify that the ID projection along any direction orthogonal to w has subgaussian tails and is anticoncentrated. Let v Sd-1 be any direction that is orthogonal to w. By Proposition A.2 d), we may assume that Pp- [T] 2 (2(0).
To verify subgaussian tails, we must show that for any D., (1, x)) t S exp(-Ct²) for some constant C. The main fact we pointwise upper bounded by Gaussian density times constant. Write
Proposition A.2 c). i.e. that any strongly log-concave density is
(I x)| > Pp- PD-l(vv x) > and (w, x) E [[-0,0]] P/r
P
PD (w,x) [-0,
The claim now follows from the fact that the numerator upper bounded by a constant times the corresponding probability under a Gaussian density, which is at most constant C", and that the denominator is (((r).
for some PP [v,x) E [a, Pn- [v, x) E [a, bj and (w, x) E [ Di
To check anticoncentration, for any interval (a, b), write
PD- ( x) E T- o]]
After projecting onto span(v, w) (an operation that preserves logconcavity), the numerator is the probability mass under rectangle with side lengths b al and 20, which is at most O al) as by Proposition (b. the density is pointwise upper bounded by a constant. The claim follows since the denominator is (l()).
Now we are ready to apply Proposition
A.3 We see that if Djr matches moments of degree at
most with ir up to an additive slack of O(k), then |EpIf [f T] Eplf T S Ō(1//k). Rewriting in terms of gives the theorem.
B.2 PROOF OF PROPOSITION 3.2
The tester Ti does the following:
1. For all a 2 with |a| =
(a) Compute the corresponding moment E(x,)) x =
ExES x
1
(b) If [Bxx.)) [x*] Ex-r- [x*]| _ then reject.
2. If all the checks above passed, accept.
First, we claim that for some absolute constant C1, if the tester above accepts, we have ((x,y) ( (Vvx))) < (C/A)&/2 for any E gd-1, To show this, we first recall that by Propo- sition A.2 e) it the case that E(x ((v,x))) $1 (Kyk)*/2, But we have
[((v,))) x))
(x.g)DD [((v,x))*
Σ
E
x
E
[xm]
(x.)>D
(x.g)D
xnDi
a:|a|=/
< dk
[2) [x0]
max ad/a|=k
(x.I)DD x-D-
Together with the bound B(x,))~ -
(Kah) the above implies that
((v, (C1k)&/2 for some constant C1.
Now, need to show that if the elements of are chosen i..d from D* and |S| > C, then the tester above accepts with probability at least - 6. Consider any specific
(dh (log #))
14

---

Published as a conference paper at ICLR 2024
multi-index Σ
with |a|
k. Now, by Proposition A.2
f have the following:
E (x0 x=D
(x
E znD
(2n))
E
(x9)))
(1 E [2n1]
2 2log(1/6)-
x
2
(K,tk) 0k/ (Ka (K ((20)
$ 2 2lgg log (og((/))) 10
This, together with Markov's inequality implies that
(3Kak log(1 ())(1 20g((18)
I
1 S
Σ XES
x
E
x
dk
Since S is obtained by taking least |S| > d (log (1ogg) for sufficiently large Ci we see that
the above is upper-bounded by 5. Taking union bound over all Z with |a| k, that with probability at least 1 - 8 the tester T₁ accepts, finishing the proof.
B.3 PROOF OF PROPOSITION 3.3
Let K₁ be as in part (d) of Proposition A.2 that are in T. If this fraction is K10/2-close to IP P [[(w, x) S o). the algorithm accepts. The algorithm rejects otherwise.
The tester T/ computes the fraction of elements in S
Now, from (d) of Proposition A.2 we have that Px~D- xw) I ol [K10, K20). Therefore, if the fraction of elements in that belong in T is Kia/ /100/00-loos to Px=-D-IKw x) S o]. then this quantity is in | (K2 + K1/2)o as required.
Finally, if [S| 2
Kio log ($) by standard Hoeffding bound, with probability least 1 8 indeed have that the fraction of elements in S that are in T is /1o/2-close to P PX-D- [[w,,)) x)| a).
100
B.4 PROOF OF PROPOSITION 3.4
The tester T3 does the following:
1. Runs the tester T2 from Proposition 3.3 If T2 rejects, T3 rejects as well.
2. Let S be the set of elements in S for which T.
3. Let k = Ö(1/72) be chosen as in Proposition 3.1
4. For all a E 2 with |al =
(a) Compute the corresponding moment E(x,)) xx x E ETT] Sizl Exes, x²
(b) If ((xa)=D(x* x E T] Ex-Di [x" x T]
js d Ō(k) then reject, where the polylogarithmic in d Ö(k) is chosen to satisfy the additive slack condition in Proposi- tion 3.
5. If all the checks above passed, accept.
First, we argue that the checks above pass, then Equations 3.3 and 3.4/ hold, the tester passes, Equation 3.3 follows immediately from the guarantees in step (4b) of Ta together with Proposition Equation 3.4 in turn, is proven as follows:
E (xa)~D
[(VV, x)]]
E (xa))
[((v. x\)
< Σ
E x
[x*]
(x:1))_1)
df
E
[x
E
[xa]
ST
0:/o==2
(x,y)~
x-
15

---

Published as a conference paper at ICLR 2024
Now, need to show that if the elements of S are chosen i..d. from D", and |S| 2 ... then the tester above accepts with probability at least 1 - 8. Consider any specifie mult-index a E 2 with |o|| = k. Now, by Proposition A.2 we have for any positive integer & the following:
E x-
(x
- (Katk)&/2
But by Proposition A.2 d) we have that IP PX- [x E T = IP xD (|xx, w o] 2 Kia. Therefore, the density of the distribution P/r (which is defined as the distribution one obtains by taking D and conditioning
T) is upper bounded by the product of the density of the distribution D This allows us to bound
and Kio
E x-D-
|XET]
E K10 x-D"
1
|(
(Kalk)a/2
K10
This implies that
210x(1/6)
E
xx"
[2"
z ETT)
iXET)
x
2n13
E
(xa))
(xE E 1(x" |xE
2log(1/6)-
X-D-
2 l0g(1/8)
(KGEk) 0k/2 (KaN)))))))
(Ki0)2 (lg((1/6)
t=
llg((1 (2K, log(1 (0)(1)))))02(1110) (olg111)
This, together with Markov's inequality implies that
- (o 2log(1/6)
di d o(k) d-O(k)
P
xx9
S
x-D-
K10
XES
Now, recall that the tester T2 in step (1) accepted, we have |Str| 2 2ha Since S is obtained
Co
d log (t). (log 2)) # 18 (4)
by taking at least |S| 2
for sufficiently large C3 we
see that the expression above is upper-bounded by 5 Taking a union bound over all a E Zd with |a| = k, we see that with probability at least 1 5 the tester T3 accepts, finishing the proof.
C PROOFS FROM SECTION
We first present the following Proposition, which ensures that we can form loss function with certain desired properties.
Proposition C.1. There are constants c, d' > such that for any a > 0, there exists a continuously differentiable function E, IR [0, 1] with the following properties.
1. For any E [-a/6, a /6), (t) + f.
2. For any 1 0/2, Eo (1) = and for any - 02, La(1)= =0.
3. For any E R, (t) [0,c/a] (t) = (-(-)) -)) and (t) s c/
Proof. We define e, as follows.
if
ift &
(a(1)
ifi =
(t(),LE
(0),tE(-5 -))
16

---

Published as a conference paper at ICLR 2024
Et(t)
20
20
Figure 2: The function & used to smoothly approximate the ramp.
for some appropriate functions et, e+ is sufficient that we pick e+ satisfying the following conditions (then & would be defined symmetrically, i.e., (1) = -1-)+(-()).
(a/2) = 1 and (+' = 0.
(6/6)) = 2/3 and (a/66/ = 1/0.
g+ is defined and bounded, except, possibly on a/6 and/or a o/2.
We therefore need to satisfy four equations for e+ So set e+ to be degree 3 polynomial: (t) = aa, + azt² + agt + 94. Whenever a > 0, the system has a unique solution that satis- fies the desired inequalities. In particular, we may solve the equation to get a -1--9//9 02 15/(2o²), 4g = -3/(4r) and a4 5/8. For the resulting function (see Figure 2 below and Fig- ure in the appendix) we have that there are constants c, such that (t) c//c/o] and jet (()()))= < d'/o² for any t E [a/6, o/2].
C.1 PROOF OF LEMMA 4.3
We will prove the contrapositive of the claim, namely, that there are constants C1 C22 C3 such that if <(w, w*), <(- w, w") > -T-27 a, and
then Vw (w)llz 2 ei (1 2ny)
Consider the case where Z(W, w*) < 5/2 (otherwise, perform the same argument for w). Let be a unit vector orthogonal to w that can be expressed as a linear combination of w and w and for which (v, w*) O. Then {v, w) is an orthonormal basis for V span w, w*). For any vector E Rdd we will use the following notation:
Xw = (w, x), X (v,x), It follows that projy = Xw + x,V, where projy is the operator that orthogonally projects vectors on V.
Using the fact that Vw((w, x)/l|w|]2) interchangeability of the gradient and expectation operators and the fact that & is an even function get that
(w, x)w
Xw for any E gd-1, the
VwC E E. (I(w,))l)
- Xw
Since the projection operator projy is a contraction, we have V (w) lpprovy VwCo (w) and we can therefore restrict our attention problem. In particular, since (xojv(x) = Xw w X, we get
simpler, two dimensional
|rooj V Cwoo(w)l
E
l ([xw)))
X
1, - -|E{ l' ((xxl)) y y.xu
E
l (|xw)) |) sign((w" xx) (1 2 1 yy * sign((w" xx))) x.
17

---

Published as a conference paper at ICLR 2024
W
G
W
0
A
A
0
tan
G
G
Figure 3: Critical regions in the proofs main structural lemmas (Lemmas 4.3
We analyze the contributions of the regions labeled A1, A2 the quantities A1, A2 in the proofs. Specifically, the regions A₁ (which have height o/3 so that the value of & (Xw) for any x in these regions is exactly 1/a, by Proposition C.1) form subset of the region G. and their probability mass under Dx is (up to multiplicative factor) a lower bound on the quantity A (see Eq equation C.3 Similarly, the region A₂ subset of the intersection of G with the band of height a, and has probability mass that is (up to multiplicative factor) an upper bound on the quantity Ag (see Eq equation C.4
5.2).
Let Fly, x) denote 21 {y * sign((w* x))). We may write x, as [xv] sign(x.) and let G C I² such that (xg) sign( x)) -1 iff x G. Then, sign(x.) (w",x)
l(x $ 9} 1(x E G}. We get
projy V Co (w) 112
to ((xwl)
(1fx Eg) 1 & g)) Fly, x) |xv|| 2
2 E Eo (|xwl) )) 1(x E 9) Fly, x) |xv|] EE lo (wl) 11 1 $ 9) F0 x). [xv]]
Let A, Ele" (1 [[xw]] 1) 11x 9} FFy x) x and A₂ E(L'- [[w) 1(x & G} F(y, |xv
(See Figure Note that Ey,x | (y, x) = 1 (x)(x) E [1 - 2n,, 1]. where 2n > 0. Therefore,
we have that A 2 (1 - (n) E[C Xw|
9)- and Ag S [[x'((xxw]] 1) 1(x & 9} [xv]]:
Note that due to Proposition C.I l [xwl) _ c/oo for some constant and ly ([xwl) 0 whenever [xw] 0/2. Therefore, 2g is the band Bw = (x: |xw| S a/2} we have
A < - [ (xx E U2) |xv|]
(C.1)
Moreover, for each individual x, have e ((xw)) |) 1(x G} [xv] e (Proposition C.Ip. Hence, for any set set C Rd we have that
0, due to the properties of
A 2 (1 2n) E[C ((xwl) 1(x E 9) 1(x E U1} |x,|] Setting Un = Bw (a/6) = {x |xw| - e/).. by Proposition C.1 we get l ((xwl) 1(x E (1) = 1 U.
1- 2m E[1(x e 9) 1[x U1 |xv]]
A
(C.2)
We now observe that by the definitions G, for any constant R > 0, there exist some constants c', cd > 0 such that if a tan 0 < d R (the points in R² where ag intersects either Old or
18

---

Published as a conference paper at ICLR 2024
D(o/tan6)) 0U2 have projections on that are O tan 0)) have that
1 (x E 9} 1xx e 3 2 1 x
[c' R, 26 22 R]} 1 E 41} and 1 x E 9) X E (2) - Xv| S c / tan 0) [x E U2]
By equations equation C.1 and equation sentations can be found in Figure 3
we get the following bounds whose graphical repre-
A 2 [(( - 2m)
[ E [e R, 2d' R) 1(x
(C.3)
c. c"
A2 S tan
B[A[[x] S c/o/ tan ta 1 UzH
(C.4)
So far, we have used no distributional assumptions. Now, consider the corresponding expectations under the target marginal D (which we assumed to be strongly log-concave).
1 E [1([vvl E (e 22 R 1(x E Ui D
1 [ S c'a// /an 1(x 42)
Any strongly log-concave distribution enjoys the "well-behaved" properties defined by (DKTZ20a) and therefore, if R is picked to be small enough, then I and I2 are of order (())) (due to upper and lower bounds on the two dimensional marginal density over V within constant radius balls aka anti-anticoncentrationn and anticoncentration) Moreover, by Proposition A.2 we have P[x E [4] and IP[x E U4] are both of order ((r). Hence we have that there exist constants c1, cg > such that for the conditional expectations we have
1(x E 41) 2 & E 1 E (CR, 26 2C) E
[1[xx] S d'o//tnn))
1fx U2]] s cc
By assumption, Property equation 3.3 holds and, therefore, if s /d/2,c//2 62. we get that
[xxx E [eR, 2d R|}
1(x E UnH 2//2
Dx
E Dx
1[ / lan 1(x E Ub} S dd/2
Moreover, by Property equation are both (cr). Hence, total, we get that for some constants č₁ 622 we have
3.2 we have that (under the true marginal) P(x E Ui) and IP[x E U22
A č (1 2n) and A ट2 Lan
Hence, if we pick a O((1 27) tan f), we get the desired result.
C.2 PROOF OF PROPOSITION
For the following all the probabilities and expectations over Dxy. First observe that
Ply # sign( (w, x)) )1 < Ply # sign((w (w),)) Ny y = sign( (w", x))] + Ply * sign( (w", [ww",))] < IP siin(((; x)) A sign (enn.,w.... x))] + opt.
Then, we observe that by assumption that Dxy satisfies Property equation 3.2 we have
Pl x) S ol & Cáo
and that
Pfssgn((ww (w, A sign( (gg"",.... x)) n (w. x) > of < Pl [ x() tan 0
where v is some vector perpendicular to w. Using Markov's inequality, we get
(tan 0)
P [(v) tan 0 <
E (v. x) #1.
g
19

---

Published as a conference paper at ICLR 2024
But, by assumption that Dxy satisfies Property equation 3.1 that [[([v,, x)1* - (C) Thus
there is some constant C1 0 Ouch
P|signn( (ww, x)) A sign((w" x\)] - Pll (w, x) S o]
Pllsign( (w, x)) + ()) øl
C30 + (Cik)
By picking appropriately in order to balance the two terms (note that this is a different than the one in Lemma 4.3 we get the desired result.
D PROOFS FROM SECTION 5
D. PROOF OF THEOREM 5.1
We will follow the same steps for proving Theorem 4.1 Once more, draw sufficiently large sample so that our testers are ensured to accept with high probability when the true marginal is indeed the target marginal D and that we have generalization, i.e. the guarantee that any approximate minimizer of the empirical error (error on the uniform empirical distribution over the sample drawn) is also an approximate minimizer of the true error. The algorithm we use is once more Algorithm| | but this time we make multiple calls for different parameters (and we run Zi with higher k, as we will see shortly) and reject any of these calls rejects. we accept, we output the output of the execution of Algorithm | with the minimum empirical error.
The main difference between the Massart noise case and the agnostic case is that in the former we were able to pick a arbitrarily small, while in the latter we face a more delicate tradeoff. To balance competing contributions to the gradient norm, we must ensure that ensuring that it is not too large. And since we do not know the value of opt, will need to search over a space of possible values for a that is only polynomially large in relevant parameters (similar to the approach of (DKTZ20b)) In our case, may sparsify the space (0, 1] of possible values for up to accuracy @(( & ) +++// and form a list of poly(k/e) possible values for σ, one of which will Vk
at least ((opt) while also
satisfy c @(( (5( for each of the possible values of and get list of candidate vectors which is still of polynomial size.
)+1//k) ) < opt S Cia. hence, we perform the same (testing-learning) process
The final step is, again, to Proposition 4.4 after running tester Ti with parameter i (Proposition 3.2 and tester T2 with appropriate parameters for each of the candidate weight vectors. We get that our list contains vector w with
ly & sign((w, < opt + c. 12/2, 01-1/(k+1), Dxy
P
where <(w, w*) S 0 = C2a for such that 0 0(( (0((())+1111 S opt S cιa.
IP [ sign( (w. x)) < opt to ( opt + 0 Dxy
1+ ((((()))))***
- S O(Vi opt -- सो)) tc.
C1
However, we do not know which of the weight vectors in our list the one guaranteed achieve small error. In order to discover this vector, we estimate the probability of error of each of the corresponding halfspaces (which can be done efficiently, due to Hoeffding's 's bound) and pick the one with the smallest error. This final step does not require any distributional assumptions and we do not need to perform any further tests.
In order to obtain our Ö(opt) quasipolynomial time guarantee, observe first that we may assume without loss of generality that opt > 1/dd for some C: if instead opt o(1/d"), say, then sample of (d) points will with high probability be noiseless, and so simple linear programming will recover consistent halfspacc that will generalize. Moreover, since otherwise achieving ((opt) is trivial (we may output an arbitrary halfspace). Let us adapt our algorithm so that we run tester Ti (see Proposition 3.2) multiple times for all lo = 1, ...,... [log² (this only changes our time and sample complexity by a polylog(d) factor). Then Proposition 4.4
may assume that opt < 1/10,
20

---

Published as a conference paper at ICLR 2024
holds for some k* such that k- [log(1/opt), 2 log(p// since the interval has length at least (and therefore it contains some integer) and 2 1log(1/opt) I 2C' log d I log" d (for large enough d). Therefore, by picking the best candidate we get a guarantee of order
k opt opt1-1/k" vk* opt-1/k opt
vk 2 log at opt
< 22 (og(1/opt)) 2 opt
(since log(1/opt) S k* s <2log(1/opt)
= (optt)
This concludes the proof of Theorem 5.1
D.2 PROOF OF LEMMA 5.2
However, in this case, 21 * sign (w", x))} (w",)))} does not have conditional expectation on x that lower bounded by constant. Instead, we need consider an additional term A3 correcponding to the part { & sign(("",x) x))} and the term Ai will not be
In the agnostic case, the proof analogous the proof of Lemma 4.3 the difference is that the random variable x))
scaled by the factor (1 2n) as in Lemma 4.3 Hence, with similar arguments we have that
w)ll 2 A1 A2 As,
where A 2 č1 A2 inequality)
82 tan
and (using properties of in Lemma 4.3 and the
A3 = 2B E xwl) 1(x E 9} 1yy # sign((w, x))} xvll
2c B[1[x E U2) 1 # sign( (w, x))) [xv]] S
2c
[E| E U2} (xx
B + sign( (W,x)
/c/
E
x E [b]
IP E U2}
Similarly to our approach in the proof of Lemma 4.3 and equation 3.4 to get that
we can use the assumed properties equation 3.2
opt Vo
Aa 03
which gives that in order for the gradient loss to be small, we require opt S ((o).
D.3 PROOF OF THBOREM 5.3
Before presenting the proof of Theorem tially, a stronger version of Proposition 4.4 for the specific case when the target marginal distribution D' is the standard multivariate Gaussian distribution. Proposition D. important to get O(opt) guarantee for the case where the target distribution the standard Gaussian.
prove the following Proposition, which is, essen-
Proposition D.1. Let Dxy be distribution over Rdd {+1), w E arg minlweg--1 PD (y + sign((w, [))] and w E Sd-1, Let 0 Z L(w, w*) and suppose that E [0, x/4] Then, for sufficiently large constant C, there is a tester that given 8 (0, 1), 0, w and set S of samples from
Dx with size at least ($ log 1)² rruss in time poly (b. d, log t) and with probability 1 - 8 satisfies the following specifications:
If the distribution Dx is N Ia), the tester accepts.
If the tester accepts, then we have:
Pr [sign((w", x)) + (w,n((w,x))) S O(0)
Proof. The testing algorithm does the following:
21

---

Published as a conference paper at ICLR 2024
1. Given: Integer d, set S C R 1d-1, (0, T/4] and 8 E (0.
2. Let projiw Rdd RR-11 denote the operator that projects vector IRd to it's projection into the (d - 1)-dimensional subspace of R² that is orthogonal to w.
3. For i in { 0,
22 $
(a) S - {x E (w, x) E |00, (i + 1)0}
(b) [8]
29, then reject.
(c) If [..] Exes. (proj ( (p)o wwppii/wxxxx)) (x)) Ta-1) > 0.1, reject.
4. If
ExES 4 (w.x))> 2l0g 50, then reject.
ST
5. If reached this step, accept.
If the tester accepts, then we have the following properties for some sufficiently large constant C" > O. For the following, consider the vector v E IRd to be the vector that is perpendicular to w, lies within the plane defined by w and w* and (v, w*)
1. P P (w.x)
E 1ii + 1)]l S C²O, for any E 0, +1, + v 2 log $
2. Px
[v,x)|
8 tan
S / for any i =l........ # 2 log
3. Px~5 ((w,)) 2 V 2 2oog b
S C"0.
Then, for k = 1/2 / 2 20ogg and Strip: = fx Rd: (w, x)] E [0i, 0(i + 1)]}, we have that 0(i
Pr [sign(( ((,, # (eeu((w",ao (w",x))] x
P xx E Strip,] P
[[v,x)]
0 i x E Strip,
P
[( x) 2 V
2log 1 s
x
x
tan
xm.
S [S]
P x-S,
[kvxx)|
i + C'O s (C")20
1
2
+
+C'
tan 0
7z
i
Now, suppose the distribution Dx is indeed the standard Gaussian. (N I2). We would like to show that our tester accepts with probability least 1 6. Since D =O(0, Ia), we see that for x D we have that x w is distributed as (0, 1). This implies that
For all i E 0. + log
we have
PIx~ I(, x) E [10, (i + 1)01 < <2* 0
- Pr E |i0, (i + 1 1)01 > 0-min
V25 e 4 >
26 / 2log
8,
$ +8
ga
10
Pix (W, E [20, (i 1)01] <
10
V2n
Prx (w, x) > 2 log = 12/108
e # dx
<
00.00
1 e 4 dr 9
72=
V
22

---

Published as a conference paper at ICLR 2024
Therefore, via the standard Hoeffding, bound, we that for sufficiently large absolute constant C we have with probability at least 1 over the choice of that
For all i E 11 2 log
we have
Prxws (w, x) [10, (i 1)0] S 0
Prxws ((W,)) [10, (i 1)0 2 @2
Prxws (W.)) > 2 log 0
. Prx-s (W.x) < 2 log $
0
Finally, we would like to show that conditioned on the above, the probability of rejection in step (3b) is small.
Fact D.2.
Given set C Rdd-1 of ii.d samples from NO0 Ia), with probability least 1
[8 (
poly
we have
1 S
Σ XES
((d-1) S 0.1
op
Now, since each sample x; drawn i.dd. from (O, Ia), we have that (w, xw) and proj w (x,) are all independent from each other for all i. Since all the events we conditioned on depend on ((w, x;)} we see that {proj_w(x;) (x:)) are still distributed as i.i.d. samples from (O (da-1)).
Recall
that
one of the events
already conditioned on is that This allows us 20 for all E -0. ... 2 2og
we
have
Prx-s (w, x) E [10. 1)01 N
to lower bound by /2/20 the ratio |S://IS). And since, as we described, for all these elements x; the vectors рroj (x,) distributed i.i.d. samples from A/0, (dd-1)),
Fact D.2 conclude that for sufficiently large absolute constant C, when |S| ( log ) have with
probability 1- & for all i 0. #1.... 2 that
(proj w (x)) w (x)) [(a-1)
$ 0.1
S
xES;
op
Overall, this allows us to conclude that with probability at least 8 the tester accepts.
We now present the proof of Theorem 5.3
In the proof of Theorem 5. when the target distribution is the standard Gaussian in d dimensions, may apply Proposition D.I (and run the corresponding tester), instead Proposition 4.4 in order to ensure that our list will contain a vector w with
P ly + sign((w x)) < Dxy
[y * sign((w", (w",))) + TP [sign(("" x)) * sign((w,x)) Dxy
Dxy
< opt + O(0)
where L(w, w") A == C2 and is such that 61 - O(c) opt CıO, which gives the desired (opt) + e bound. To get the value of a with the desired property, we once again sparsified the space (0, 1] of possible values for this time up to accuracy (cc).
23

---

Published as a conference paper at ICLR 2024
lo(t) (t(t)
(g(t)
Figure 4: Figure illustrating the (normalized) first derivatives of the function f, used define the non convex surrogate loss L.. The normalization is appropriate since f' and f" are homoge- neous in 1/a and L/o² respectively. particular, we that l' S @(1or) and |e O(1/o²) everywhere.
24


Reviews:
[{"review_id": "nFqXDW0idh", "reviewer": "Reviewer_sjRf", "summary": "This paper is a further exploration of the testable learning framework proposed by Rubinfeld and Vasilyan. The main feature of this framework is that it requires learning algorithms that learn near-optimal predictors whenever the input training sample passes a test (soundness), and also training samples pass the test whenever the distributional assumptions are met (completeness). \n\nThe paper gives polynomial-time testable learning algorithms for halfspaces when the marginal distribution is isotropic log-concave and:\n(a) under Massart noise, guarantee error at most OPT + \\epsilon. [Theorem 4.1]\n(b). under adversarial noise, guarantee error at most O(OPT) + \\epsilon. [Theorem 5.1]", "questions": "It would be great if the authors could discuss further the contributions of this paper in light of subsequent work (Gollakota, Klivans, Stavropoulos, Vasilyan, NeurIPS 2023). In particular, can the authors make a case for why the contributions in this paper are beneficial/useful given that more general results have already been published.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is a good paper that significantly extends what is known to be achievable in the testable-learning framework. To establish these results, the paper contributes new testing procedures that go beyond the limitations of prior work (Gollakota, Klivans, Kothari, 2023). Additionally, the techniques of this paper have also led to more general results in testable-learning (Gollakota, Klivans, Stavropoulos, Vasilyan, 2023). \n\nThe paper is well-written and easy to read. The authors do a great job discussing prior work, and how the paper fits with related literature.", "weaknesses": "The results may be a little limited in retrospect. In particular, the paper (Gollakota, Klivans, Stavropoulos, Vasilyan, NeurIPS 2023) already has more general results, including the results of this paper. If I understood correctly (based on page 2, subsequent work paragraph), there is some non-overlap in the techniques used in both papers, and so this paper may still be beneficial to the community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xXFC2eQoxU", "reviewer": "Reviewer_HBcm", "summary": "This paper worked on the problem of learning Gaussian Halfspace (with extension to more general stongly logconcave distributions) with Massart noise and agnostic noise, under the Tester-Learner models. The authors provided the first tester-learner algorithm with polynomial iteration and sample complexity, that achieves $\\mathrm{OPT} + \\epsilon$ error for the Massart noise and $O(\\mathrm{OPT}) + \\epsilon$ error for the agnostic noise (under Gaussian marginal). The technical contriutions of this paper are mainly the following: the authors devised more efficient testers using information of labels and exploiting the local geometric structure of the distribution (the condition probability on a band $P[v\\cdot x \\in [\\alpha, \\beta] | w\\cdot x\\in[-\\sigma,\\sigma]]$); they also showed that for some carefully designed loss function $\\mathcal{L}_\\sigma$, its stationary points $w$ are also vectors that are close (in angle) to the optimal solution $w^*$, under some distributions that are efficiently testable.", "questions": "1. I am confused why the algorithm needs two $T_3$ testers with different accuracies, $\\sigma/6$ and $\\sigma/2$?\n2. I am not very familiar with tester-learner models. Are there lower bounds on learning gaussian halfspaces under massart/agnostic noise for tester-learner algorithms? Are tester-learner algorithms SQ algorithms?\n3. In algorithm 1, what exactly is the function class $\\mathcal{F}_{w'}$? How to choose the weights that are orthogonal to $w'$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper contributes rigorously to the field of robustly learning halfspaces, and has some very interesting results. \n1. Based on the results from DKTZ20a and GKK23, the authors devised new algorithms that are more efficient comparing to prior works. This includes a new loss function that work better for the specific task, and some new structrual results linking the gradient norm of this loss to the angle between the parameter $w$ and the optimal halfspace $w^*$.\n2. The authors used some local property of the distribution that enables them to get desired result using testers that achieves only constant error rather than $\\epsilon$ error.\n3. These results can further extend from Gaussian distribution to strongly logconcave distribution, and get simialr results (at least for Massart noise).\n4. The authors finally get the first polynomial tester-learner algorithm for learning Gaussian halfspaces under massart and agnostic noise.\n5. The paper is clear and contains useful explanation on the intuiation of the algorithm.", "weaknesses": "I think there is no obvious weakness in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xjPQBVr8T6", "reviewer": "Reviewer_CcgF", "summary": "This paper proposed a polynomial-time algorithm for learning halfspaces on testable fixed well-behaved distributions under Massart and adversarial noise. Unlike its prior works, it takes the labels into account and checks local properties of the distribution by testing the moments of the conditional distributions around the stationary points.", "questions": "Can you justify the unique value of this paper given the subsequent work has shown strictly stronger guarantees?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The framework of testable testing was recently proposed and has drawn great attention in the research community. This paper proposes a polynomial time algorithm for learning halfspaces under noisy settings, while the distributional assumptions are replaced by a tester on a fixed distribution. The paper is well-written. The technical parts look sound.", "weaknesses": "As mentioned in the paper, its subsequent work, “Tester-learners for halfspaces: Universal algorithms” has shown a more general tester-learner with stronger guarantees. This largely weakened the merit of publishing the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Vocn2g91vU", "reviewer": "Reviewer_9fsR", "summary": "In this paper, the authors give the first computationally efficient tester-learner for learning halfspaces where the target distribution is the d-variate Gaussian and the label noise is Massart or adversarial. The tester-learner framework was recently proposed as a generation to the distribution-specific learning setting where the algorithm needs to accept a dataset whenever it comes from a target distribution and needs to achieve the agnostic learning guarantee (error = $opt + \\varepsilon$) whenever it accepts. Previous work only gave a sample-optimal tester learner for the same problem which was not computationally efficient. The main technical novelty in this work is tester that looks at the labels as opposed to the label-oblivious testers previously designed. For the adversarial noise setting, the authors achieve the suboptimal risk $O(opt) + \\varepsilon$.\n\nThe authors build on the non-convex optimization approach of [DKTZ] which uses the a smoothed version of the ramp loss as a surrogate to the zero one loss. Although this is a non-convex function, it was shown that the stationary points are good solution which can be recovered by projected SGD as the first step under the Gaussianity assumption. In the testing-learning framework, we need to additionally check the following assumption: the probability masses of certain regions are proportional to their geometric measures. The tester checks local properties of the distribution in regions described by the stationary points using moment matching techniques. Naively, such a check could only guarantee the empirical mass is additively close to the true mass. However, using a refined moment test conditioned on a band based on the stationary vector (similar to the existing localization-based refinement techniques of Awasti et al. 2017) they could get the stronger multiplicative guarantee. This allows them to argue that if the test passes, the stationary points will indeed be close to the true weight vector in angular distance. This in turn means the returned vectors are good solutions using properties of Gaussian. The later step results in a larger error for the adversarial noise setting as opposed to the Massart noise setting.", "questions": "- Are the constants involved in the complexity very big? Given that ICLR accepts experiments and the dataset is easy to synthesize, how hard is it to implement and test the claimed efficient algorithm? This may be a general question targeted to even some of the prior works as well.\n- I believe the results easily extend to non-homogeneous halfspaces where there is a constant offset term?\n- I believe only the tester T3 uses the labels to check the fooling and T1 and T2 does not in Algo 1? Small typo: the Run T2 step has $\\sigma$ missing in $B'_W(\\sigma)$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The proposed work is an interesting combination of several technical ingredients that have been developed in learning theory for learning halfspaces and testing distributions such as non-convex optimization, fooling functions of halfspaces, and moment-matching tests. Moreover, they achieve the desired polynomial runtime for halfspaces in the newly proposed testing-learning framework.", "weaknesses": "The presentation could have been better. The paper has several forward references, that too from the main body to the appendix, which makes it slightly hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)