A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
Authors: Ilias Diakonikolas
Nikos Zarifis
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Massart Noise
margin halfspaces
Primary area: learning_theory

Abstract: We study the problem of PAC learning $\gamma$-margin halfspaces in the presence of Massart noise. 
Without computational considerations, the sample complexity of this learning problem is known to be 
$\widetilde{\Theta}(1/(\gamma^2 \epsilon))$. 
Prior computationally efficient algorithms for the problem incur sample complexity 
$\tilde{O}(1/(\gamma^4 \epsilon^3))$ and achieve 0-1 error of $\eta+\epsilon$, 
where $\eta<1/2$ is the upper bound on the noise rate.
Recent work gave evidence of an information-computation tradeoff, 
suggesting that a quadratic dependence on $1/\epsilon$ is required 
for computationally efficient algorithms. 
Our main result is a computationally efficient learner with sample complexity 
$\widetilde{\Theta}(1/(\gamma^2 \epsilon^2))$, nearly matching this lower bound. 
In addition, our algorithm is simple and practical, 
relying on online SGD on a carefully selected sequence of convex losses.

A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
Ilias Diakonikolas Department of Computer Sciences UW-Madison Madison, WI i as@cs wisc. edu
Nikos Zarifis Department of Computer Sciences UW-Madison Madison, WI zari i wesswisscc...m edu
Abstract
We study the problem of PAC learning 7-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem known to be ê(1 (())))) Prior computationally efficient algorithms for the problem incur sample complexity ((1/(r²e)) and achieve 0-1 error of 1) where 7 < 1/2 is the upper bound the noise rate. Recent work gave evidence of an information-computtiion dependence 1/c is required for computationally efficient algorithms. Our main result is computationally efficient learner with sample complexity 5(1/(>2<)) nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.
tradeoff, suggesting that quadratic
Introduction
This work studies the algorithmic task of learning margin halfspaces in the presence of Massart noise (aka bounded label noise) [MN06] with a focus on fine-grained complexity analysis. A halfspace or Linear Threshold Function (LTF) is any Boolean-valus valued function h IRd {+1} of the form h(x) sign (w 9), where E Rd is the weight vector and 0 E R is the threshold. The function sign - 1+ defined as sign(t)
if 2 and sign(!) = -1 otherwise. The i.e., under the assumption that no example lies too close to the separating hyperplane - is one of the earliest algorithmic problems studied machine learning, going back to the Perceptron algorithm [Ros58].
problem of learning halfspaces with margin
In the realizable PAC model [V184] (i.e., with clean labels), the sample complexity of learning 7-margin halfspaces on the unit ball in Rd is O(1 O(1/(?"e)), where > 0 is the desired 0-1 error; see, e.g.. [SSBD14 Moreover, the Perceptron algorithm is computationally efficient learner achieving this sample complexity. That is, without label noise, there is sample-optimal and computationally efficient learner for margin halfspaces.
In this paper, we study the same problem in the Massart noise model that we now define.
Definition 1.1 (PAC Learning with Massart Noise), Let D be distribution over X' x {+1}. and let be a class of Boolcan-valued functions over X. We say that D) satisfies the 17-Massrr noise condition with respect to C, for some 1) < 1/2, if there exists a concept f E C and an unknown noise function 77(x) : X + [0, 7] such that for (x, y) ~ D. the label y satisfies; with probability 1 - (x), = f(x); and
- f(x) otherwise. Given i.i.d, samples from D, the goal of the
As standard, we are assuming that 9(1/?)); otherwise, a sample complexity bound of Ö(d/c) follows from standard VC-dimension arguments.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

learner is to output a hypothesis h X' + {+1} such that with high probability the 0-1 error Pr(x,))-(((()) + v] is small.
(h) def
The concept class of halfspaces with a margin defined as follows.
Definition 1.2 (7-Margin Halfspacess. Let D be a distribution over Sd x {+1}, where Sd-1 is the unit sphere in R Let w E g and y E (0, 1). We say that the distribution D satisfies the 7-margin condition with respect the halfspace sign( ww x if (i) for (x, y) ~ D, we have that 7] 0. The parameter y is called the margin of
y sign(w" x), and (ii) Pr(x)))) [[w* the halfspace sign( w x).
the best possible 0-1 error attainable for learning a concept class with Massart noise is opt := Ex~D2 [x)]]. Since n)(x) is uniformly bounded above by 7, it follows that opt < 77 also note that it may well be the case that opt < v)- Focusing on the class of 7- margin halfspaces, it follows from [MN06] that there exists a (computationally inefficient) estimator achieving error opt + with sample complexity ((1/((1 2c)) and moreover that this sample upper bound is nearly best possible (within logarithmic factor) for any estimator. (That is, the sample complexity of the Massart learning problem is essentially the same as in the realizable case,
as long as 1) is bounded from 1/2.)
Taking computational considerations into account, the feasibility landscape the problem changes. Prior work [DK22] NT22] DKMR22 has provided strong evidence that achieving error better than 1 + is not possible in polynomial time. Consequently, algorithmic research has been focusing on achieving the qualitatively weaker error guarantee of + e. We note that efficiently obtaining any non-trivial guarantee had remained open since the 80s; see Appendix[A.T]fol [ a discussion. The first algorithmic progress for this problem is due to [GTT19] who gave polynomial-time algorithm achieving error of 17 - e with sample complexity poly(1/7, 1/e). Subsequent work [CKMY20] gave an efficient algorithm with improved sample complexity of ((1/(r=e²)) Prior to the current work, this remained the best known sample upper bound for efficient algorithms.
In summary, known computationally efficient algorithms for learning margin halfspaces with Massart noise require significantly more samples camples-nmmely.. ((11(7>22) than the information -tteoretcc minimum of é,, (1) is thus natural to ask whether a polynomial-time algorithm with optimal (or near-optimal, i.e., within logarithmic factors) sample complexity exists. Recall that the answer to this question is affirmative in the realizable setting, where the Perceptron algorithm is optimal. Perhaps surprisingly, recent work (DDK 1Dal+23a| (see also [DDK (tXx+33b) 23b)) gave evidence for the existence of inherent cntormaation-ooppatttiii tradeoffs in the Massart noise model-in fact, even in the simpler Specifically, they showed that any efficient
model of Random Classification Noise (RCN) [AL88] 3
Statistical Query (SQ) algorithm or low-degree polynomial tasks requires ((1/e") samples-a near quadratic blow-up compared to the ((1/c) information-theorett upper bound. This discussion serves as the motivation for the following question:
What is the optimal computational sample complexity of the problem of learning 7-margin halfspaces with Massart noise?
By the term "computational sample complexity" above, we mean the sample complexity of polynomial-time algorithms for the problem. Given the fundamental nature of this learning problem, we believe that fine-grained sample complexity versus computational complexity analysis is inter- esting on its own merits. In this work, we develop computationally efficient algorithm with sample complexity of )(1/(>2²²). Given the aforementioned information-coom compuiionno tradcoffs, there is evidence that this upper bound is close best possible. As a bonus, our algorithm is also simple and practical, relying on online SGD. (In fact, our algorithm runs in sample linear time, excluding final testing step that slightly increases the runtime.)
1.1 Our Result and Techniques
Our main result is the following:
We will henceforth assume that the threshold 0 = 0, which well-known to be no loss of generality.
The RCN model is the special case of Massart noise, where n7xx) ry for all points in the domain.

---

Theorem 1.3 (Main Result, Informal). Let D be distribution on S4-1 x {+1} that satisfies the n-Massart noise condition with respect to an unknown y-maagin halfspace f(x) = sign(w* x). There is algorithm that draws n = ((1((e?())) samples from D, runs in time O(dn/e), and with probability at least 9/10 returns vector w such that errp (w) S 1 +
The sample upper bound of Theorem 1.3 nearly matches the computational sample complexity of the problem (for SQ algorithms and low deereegre polynomial tests), which shown to be ((1/(c²>) 1/(e>²)) [MN06] DDK DDK 23b]. That is, Theorem co3em close to resolving the fine- grained complexity of this basic task. Moreover, it matches known algorithmic guarantees for the easier case of Random Classification Noise DDK+233 KIT+
Independent Work Independent work [CKST24] obtained learning algorithm for y-margin halfspaces with essentially the same sample and computational complexity as ours.
Brief Overview of Techniques Here we provide a brief summary of our approach in tandem with a comparison to prior work. The algorithm of [DGT19] adaptively partitions the space into polyhedral regions and uses a different linear classifier in each region, each achieving error 77 + within the corresponding region. Their approach leverages the LeakyReLU loss (see ( as a convex proxy to the 0-1 loss. At a high-level, their approach reweights the samples in order to accurately classify non-trivial fraction of points. [CKMY20] uses the LeakyRel.U loss to efficiently identify region where the value of the loss conditioned on this region is sub-optimal: they then use this procedure as a separation oracle along with online convex optimization (see also [KKTZ20b] 21K+21) to output a linear classifier with 0-1 error at most 1) + Both of these approaches inherently require (2(/E")) samples for the following reason: they both need to condition on a region where the probability mass of the distribution can be as small as (e). Thus, even estimating the error of the loss would require at least (2(/(²) conditional samples. Beyond the dependence on 1/c, the sample complexity achieved in these prior works is also suboptimal in the margin parameter y,; namely, ((1/'*). This dependence follows from the facts that both of these works require estimating the loss in each iteration within error of at most ye, and that their algorithmic approaches require 22(1 /?²) iterations.
To circumvent these issues, novel ideas are required. At high-level, we design a uniform approach to decrease the "global" error, as opposed to the local error (as was done in prior work). Specifically, we construct a different sequence of convex loss functions, each of which attempts to accurately simulate the 0-1 objective. We note that similar sequence of loss functions work IDKTZ24] in a related, but significantly different, adversarial online setting. Interestingly, a similar reweighting scheme used in [CKMY20] for learning general Massart halfspaces. Beyond this similarity, these works have no implications for the sample complexity of our problem. (See Appendix A.2 for detailed comparison.) Via this approach, we obtain an iterative algorithm which uses only 0, samples in order to estimate the loss in each iterative step.
used in the recent
In more detail, note that the 0-1 loss can be written in the form E(y [ We convexify this w-X
objective by considering, in each step, the loss E(w, u) Ely ju-x where u independent of w; this loss is convex with respect to w. Observe that E(w, w) is proportional to the zero-one loss of w. Unfortunately, is possible that no optimal vector w" (under 0-1 loss) minimizes f(w', w). For this reason, we consider the objective (W, u) = (1 [y & sign(w w x)}
<)|w xx//u xx]. This new objective satisfies the following: É, (w", u) < eyy for any vector u and any w" that minimizes the 0-1 objective; and É, (,, w) 2 E as long as w incurs 0-1 error at least + e. By the convexity of (,(,, u). this allows us to construct separation oracle. Namely, we draw enough samples so that (w, w) (w", w) 2 e/2, where ? is the emprical version of the loss. Due to the nature of these objectives, O, (1/2) samples per iteration suffice for this purpose. This in turn implies that the cutting planes method efficiently finds a near-optimal weight vector after Oloog(L/e) (l/))(())///)))))) iterations. Overall, this approach leads to an efficient algorithm with sample complexity (1/e))) To get the desired sample complexity of ((1)(???))) more ideas are needed.
In the previous paragraph, we hid obstacle that makes the above approach fail. Specifically, it may be possible that, for many points x, the value of uu x| is arbitrarily small. To fix this issue, we [w
consider clipped reweighting as follows: C,(W,, u) E[ (y * sign(w x)} 17 max [ [7)
This clipping step is not a problem for us, because the target halfspace sign(w* x) was assumed to have margin y. This guarantees that the difference between the expected (over y) pointwise losses at (w, w) and (w", w) is at least on the points x where iu- x S 7. Indeed, when this is the case, then ww" x
Iu xx/
x] > 1. Overall, this suffices to guarantee that C (W. w) (w", w) 2
3

---

1.2 Notation
For n Z+, let [n] def [l....,n). We use small boldface characters for vectors. For e R and i E [d], x; denotes the i-th coordinate of x, and ||x|| def ( x/2 denotes the l norm of x. We will use x for the inner product of x, y E Rd. For a subset S S Rd, we define the projs operator that maps a point x E Rd to the closest point in the set S. For a, E I, we denote
W(a, b) def 1/ //aaxaa, b). We will use 1A to denote the characteristic function of the set A, i.e. 1(x E A} = if x E A. and 1 E A} = 0 if x & A. For A, B E R. we write A Z B (resp. A S B) to denote that there exists a universal constant C' > such that A CB (resp. A S.S. CBB).
We use [x= for the expectation of the random variable x with respect to the distribution D and Pr[E] for the probability of event E. For simplicity, we may omit the distribution when it is clear from the context. For (x, y) ~ D, we use Dx for the marginal distribution of x and (x(x) for the distribution of y conditioned on x. We use DN to denote the empirical distribution obtained by drawing N i.i.d. samples from D. We use crTp (TT)(W) to denote the 0-1 error of the
halfspace defined by the weight vector w with respect to the distribution D, i.c., errp(w) def Pr(x.y)~-D(i (sign(w (w- x) & y/. We will use err(w, x) for the 0-1 error of sign(w x) conditioned on x, i.e., err(w, x) == Pry-D,, [sign(w (w- x) * y]. Note that crTn(w) = Ex-D, [err(w,x] If D satisfies the 17- 7-Massart noise condition with respect to the halfspace sign(w (w: - x). then err(w, x) = m(x) (sign(w w x) sign(w" x)} + (1 (xx)) I (sign(w (w x) & sign(w" -x)]
2 Our Algorithm and its Analysis: Proof of Theorem 1.3
In this section, we prove our main result. Algorithm Jefttmientty learns the class of margin halfspaces on the unit ball, in the presence of Massart noise, with sample complexity nearly matching the mnformation-computann
limit. Additionally, its runtime is linear in the sample size, excluding a final testing step to select the best hypothesis.
At a high-level, our algorithm leverages a carefully selected convex loss (or, more precisely, sequence of convex losses) - serving proxy to the 0-1 error. A common loss function, introduced in this context by [DGT19 and leveraged in [DGT19 CKMY20), is the LeakyReLU function. This is the univariate function LeakyReLU, x (1) (1 A) 2 0ft + X1 (1 < 0)/, where À E (0, 1) is the leakage parameter (that needs to be selected carefully). ). Roughly speaking, the convex function (x(w, x. y) LeakyReLU, (-y(w x)) can be viewed as a reasonable proxy to the 0-1 loss of the halfspace sign(w x) on the point (x, y). To see this, note that (sce, c.g., Claim C.I)
(w, x, y) = (1 (sign(w (w x) F y} - \)|w x/
Observe that point x that is classified correctly by the halfspace sign (w- x) will satisfy
E (Ey- [1 (sign(w- x) * yHl >) | x = (17(x) W)|w-2 x
which is non-positive for X 2 v)()). Since the only guarantee we have is that 77() S 1), this suggests that we need to select À 2 77. turns out that X = rj is the optimal choice. We fix the choice of A : v) throughout. On the other hand, if (the halfspace defined by) w misclassifies the point this term becomes non-negative.
The factor || in Equation [1) reweights the 0-1 error so that points x for which [w-x] is sufficiently large (i.e., close 1) have be classified correctly by a minimizer of E(x,y><D[4, (Ex x, v)]. On the other hand, points closer to the separating hyperplane defined by w, or points where r)(x) is close to X = 17, are not guaranteed to be classified correctly by the minimizer of this loss. We leverage this insight to construct a sequence of loss functions that reweight the points that, to minimize
the regret, we need to classify large fraction of points; this leads to the desired error of 1) + e with near-optimal sample complexity.
We now provide some intuition justifying our choice of surrogate loss functions. Observe that if we instead could minimize the function
E (x.y) n [A x, /)/l x||
E (1 (sign(w x) + w} A)] (x:8)~n
with respect to w. we would obtain halfspace with minimum 0-1 error; unfortunately, this reweighted loss is just a shift of the 0-1 loss, hence non-convex. To fix this issuc, instead of reweighting by

---

1//w xl, we will reweight by ((v- x. def 1/ max( -v,
x), where Y the margin parameter and v is an appropriately chosen vector that is independent of w. The new loss is defined as follows:
(x,((w) def
E (x.0)~
(x,,,, x. x.1\2)]
where for technical reasons we use 7/2 instead of in the maximum.
Since the parameter is independent of w, the loss (w) remains convex in At the same time, by carefully choosing V. we can accurately simulate the non-convex 0-1 loss. Note that our reweighting term is maximum over two terms. The reason for this choice is that, for some points x, the quantity vv x| can be arbitrarily small; taking the maximum avoids the loss becoming very large. In partieular, the loss Cx,((w) will be guaranteed remain in bounded length interval.
Our algorithm proceeds in a sequence of iterations. In the (++ 1)-st iteration, it sets v to be w', where w' is the weight vector of step t. This choice attempts to simulate the 0-1 error at w', as is suggested by Equation (2). Assume for simplicity that our current hypothesis is the halfspace defined by w and is such that Ex ([w-
1/|w x|. By combining Equations (2) and (3) we get that L (w) = errp (w) - X; note that as long as err D (w) 2 À + 6, have that Lx, w) On the other hand, the optimal halfspace w achieves
//22]
Note this implies that W(w x, x
a non-positive loss; from Equations and we have that
(xw((w))=
E [11 (11 (sign( w" x) * y) A)/w" x ((W(W (w-22 Now-x,77 x/2)
(x.y)~D
E [()(x) - A) w x|W (w x, x22] 20,
x~Dx
where the inequality follows from the fact that 17(x) 17. Recalling that (x,v(w) (w) is convex. if we an Online Convex Optimization (OCO) algorithm, after T steps we are guaranteed to find a vector w such that (x.w(w) - Lx (w") I O(1/VT). For T = (1)/²), this gives that Lx,w < c/2; and therefore would have err (w)) < c We provide approach using this idea and the cutting planes algorithm in Appendix that achieves sample complexity ((1/(2274)
Our algorithm and its analysis work only with the gradient of (x,v(w). The key novelty is the analysis of the sample complexity. The gradient of lx (w, x, W) x) with respect to has the following explicit form:
gx,7 (w, v, def ((1 22)ssignnn x) w)W((v x,,)x ((1 2Xjsign(w x) - v) max(/v x(,,
Furthermore, we denote by GD(w, v, 17. 7) = Ex.x)) p v.,)),
Before describing our algorithm and proving Theorem 2.1 we simplify our notation. We will omit the parameters 17. y from the function input (as they are fixed throughout). Therefore, we use G By, (w, v) G Gōş, (W, v, 7) and g(w, v, v) Bn.z2 (w, v.).
Our algorithm is described in pseudocode below.
Algorithm I emmloys online SGD applied to a sequence of convex loss functions. We show that, after a certain number of iterations, the algorithm will find weight vector achieving 0-1 error at most 7) + e. Since the desired vector may not be the last iterate, the end, our algorithm returns the halfspace that achieves the smallest empirical 0-1 error.
We establish the following result, which implies Theorem
Theorem 2.1 (Main Result). Let D be distribution on gd-1 {11} satisfying the M-Massart
noise condition with respect to the 7y-margin halfspace f(x) = sign (w" x). Given N (loog(((7)))/466
2n)) and T that e (W) I 17 with probability at least 5. The algorithm draws n = O(N + +T) samples from D and runs in OddTT) time.
([(oo((/))((<>>)) Algorithm 7 returns vector w such
The of this section devoted the proof of Theorem 2.1
Our algorithm sets v w' in each round, therefore for the rest of the section we proceed by setting w arguments of g and G.
5

---

Input:
Sample access to distribution D supported S x {+1} corrupted with 7- 7-Massart noise with respect halfspace sign(w" w" x) that satisfies the 7-margin condition; parameters 6, 8 E (0, 1), and N, T 2
Output: Weight vector w such that errp (w) S r7 + with probability least 1 8.
1. Let > 0 be sufficiently small universal constant.
2. f t 5,0, 0, w. t c = (1,0...., 0), and T = (1/c) log(1/0)/(<27))
3. While t I do
(a) Draw (x(*), sample from D.
(b) Set d t ccfe.
(c) Update w' as follows:
> Update and project in the unit ball
++1
v rl1 t- w >xg(w', w', x', (0))
w
max v
(d) t t+
4. Draw N samples from D and construct the empirical distribution Dx-
5. Return w argmin 6x (w*).
Algorithm 1: Learning Margin Halfspaces with Massart Noise
We decompose the stochastic gradient g(w, w, x, into two parts: g(w, w. y) =g' B'(,,)) g"(w, x, y). where
g" 8'(wxx = (11 -11-21))sig -21)ssign((w x)
E gx
[b]]
W(W W(W-x,7/22x
and
g g2 x, = (x))
- W(w w,,-x,7/21 x,72)
We also G1 (w) and G2 (w) for the same decomposition after taking the empirical expecta- DN (w) (xx)) ig' x)] and G DN (w) E (x..))DD. Ig (w.x, y)].
DN
tion, i.e., G DN
This serves decompose the gradient into two parts: one containing the population expectation over the random variable and the other containing the error between the empirical estimation of and the population version of y. The vector "Dy (w) contains the direction that will decrease the distance between and w*, while G Dy
(w) contains the estimation error. To this, observe that
if we take the population expectation of (,, y), we will have:
[[ (1 (x)ggssi) x)
E 1 x,
v)]
E x~Dr
[w] W (P(wxxx x,7/2)x =0, y-D Dx(x))
E
(x.)~D
where we used that Ey=D,(x) [v] = (1 2n((x))sign(w*.. x).
We start by bounding the contribution of , (w) in the direction w - w" We show that if instead of the corrupted label the point x, had access Eyy-D, [y] (1 2n)(x))sign(w) xx, then the gradient has a large component in the direction of w w". This effectively implies that G1 Dy (w) can be used as a separation oracle, separating all the halfspaces with 0-1 error more than
77 + é from the ones with smaller error.
Lemma 2.2 (Structural Lemma). Let E 2+ and let D be a distribution on gd-1 x (+1} satisfying the 1-- M-Massrrt condition with respect the optimal classifier f(x) = sign(w* x). w R be such that ||wl|| I and let [ i==1 be a multiset of N i.i.d. samples from Dx Then, holds Dy (w) (w w*) 2 2(err Dy (w) - n) where Dr is the corresponding empirical distribution.

---

Proof. We partition Rd into two subsets R1, R2 as follows: Ri contains the points that lie sufficiently
far away from the separating hyperplane w x = 0, i.e., R1
def
{x E
IR
|w
x 2 7/2 R2
contains the remaining points, i.e., R2 def fx R w x < 7/2).
We first show that for any X E R4 the vector g+ (w, x) has a large component parallel to the direction w'. The proof of the claim below be found in Appendix C
Claim 2.3. For any x(0 E R1, we have that g' (w, x(1)) (W -w") 2 ((err(w,x()) 17)
remains to show that the same holds for all the points in R2. The proof of the claim below can be found in Appendix
Claim 2.4. For any x(0 E R2, we have that g' (w, x(1) (w -w") 2 2(crr(w, (w)))) - 1))
Applying Claim 2.3 and Claim 2.4 for each sample in the set {x(1)) NN 1i=1. we get that
N
2
Σ
g w, x (1) (w --o)-w))--
w")
(err(w, x -1)
N i=1
N
This completes the proof of Lemma 2.2
By Lemma 2.2 the gradient points towards the direction w ww", in the f-th iteration. This means that, in fact, the gradient is subgradient of the potential loss ((w) ||w w 11.2 This allows us to show convergence, even though generally not possible in sequence of loss functions the stochastic setting. We
ready prove our main result.
Proof of T'heorem 2.7 Let 7 be the maximum number of iterations of Algorithm
I Denote by Z' = {xx(*), (x((")y()))) ())) the i.i.d. sample drawn from D the f-th iteration, t E [T]. Furthermore, let Fi..... Fr be the filtration with respect to the o-algebra generated by Z ...., 2². We denote by H, the event that D (w") 2 +
Recall that Algorithm D Jsses the following update rule (see Step (3c
w : (w' >eg(w' w", w (*))
with A = c for some sufficiently small absolute constant c >> 0.
We begin by bounding from above the distance between w and w from the previous distance between w' and w We have that
| w 11
(wRr (w' >rg(w' w ,x(x))))) g0)) w
ww" >ug(w' w/, x(1, (00)) -w"13
I w0 2)rg(w' w x(1), (()) (w' - ww) + A3 llg((" w", (()) (/)
where in the first inequality used the projection inequality, i.e., ((proje(v) projo (oooi(())l 1
||v - u//2 for any set B. We will decouple the mean of the random variable g(w", w', x, y) and make it zero-mean.
To simplify the notation, we denote by & == g(w', w xx00, - Gb(w")) (w' - w") and
note that & is zero-mean random variable over the sample (x(1)), ((t)). Adding and subtracting (w(")) onto Inequality (4) we get that
1 < I|w w w -22.Gb(w') (w" -w") w²) Xi lills(w' w (1) ( 27
(5)
We now outline the main steps of our analysis. Instead of accurately estimating the gradients in each round, we denote by Vn the estimation error from which we bound above their sum. We first add and
7

---

subtract the population gradient to obtain the I term, which is the decreasing direction. In this way. we decouple the expected decrease and the error of the approximation (see Claim 2.5). After that, we bound the contribution of the estimation error in Lemma 2.8 Observe that V is a random variable that corresponds to the estimation error of the gradient. We will argue that with high probability the contribution of Σ V, is bounded; therefore, algorithm will converge an accurate solution.
Lemma 2.2 shows that G (w") (and therefore the same holds for G (w")) contains substantial
contribution towards to the direction w' - -w', . depending of the current error. We show that our choice of step size guarantees a decreasing direction. To this end, we prove the following:
Claim 2.5, Assume that the event He happens, ie., errD(w") 2 n + e. 1 S 72e/8 then S - (Oer -n)-
Proof of Claim 2.5 Recall that 1= = - (w"). -(w' w*) + X3 lgw',,'' w xx("), ( By Lemma 2.2 we get that G) (w"). ) (w' w") 2 2(err (w") )- 71) hence, by taking expectations over the samples, we also have G (ww)). :(w' ww) 2 2(errD (w") - -17). Furthermore, we have that llg(",, w', ((0 y 10) < 88/7". Hence, S -22e(eer - + +8(A)/n²) The claim follows
by noting that if d S 79//8, then ->e(errn(w)) - 11) +8A(//7
S 0. Therefore, we obtain
IS - (wrr - 1))
This completes the proof of Claim 2.5
Therefore, our choice of parameters guarantees that d S 2/²8/8. Using Claim 2.5 onto Incquality (5) we have that
w 1+1
w 113 l|w
1| Ae(erro(w9)- - -n) + Dz
(6)
Using Claim 2.5 and Inequality (6)
we have that
1| T T+1
w
<
w
112
Ar (wor (w") -1) + Vir
T
w
Σ Aelerp(ww)) - -n) + 1=0
V
t=0
To complete the proof of Theorem 2.1 we need to bound the estimation error that corresponds to the random variable Vú. We show that V, does not increase the error by lot. Recall that V. -2
Before proceeding, we provide some basic background on subgaussian random variables.
Definition 2.6 (Subgaussian Random Variable). For 0, zero-mean random variable X E R called r-subgaussian, if for any À E R holds log(Elexx (E(exp(AX)) S X262.
Note that any zero-mean bounded random variable is subgaussian. Specifically, we have the following:
Fact 2.7 (Hoeffding's 's lemma, see, e.g., [Ver18)) Let X E R be zero-mean random variable such that X < a for some a > O. Then X is Co-subganssian, where >>> 0 universal constant.
Equipped with the above context, we show the following:
Lemma 2.8. With probability at least 1 - 8 over the random samples, it holds that Et= Vi s
C 1og(1/8), where C > 0 is an absolute constant.
Proof. We first show that & is a subgaussian random variable.
Claim 2.9. The random vector & is -ubgaussian.
Proof of Claim 2.9 Note that & = (g(w", w', (1) ()) Ex w x, v)) (w' - ww*
and that by construction lig( w w x))ll | < 4/7. Therefore, it holds that (g(w", w² x(t), (1))
(w' w=] S 8/2, where we used that || w 2|2 S as both of these vectors lie in the unit ball.
Hence, by Fact 2.7 we have that & is ((ton)))subauusiian
8

---

with Using Claim 2.9 and Definition 2.6 with parameter À = -2 and X = &., we have that
log E exp Vi] = log E
S /(2)/>²),
where C
0 is a universal constant. To bound the contribution of Σ V. we use Markov's
inequality with respect to the filtration FI,..., Fr. We have that for any Z E R, it holds that
T
Pr 2 2 2
Σ v Z
Pr 2 2',..,ZNND
exp
Σ
V1
exp(2)
T
5 2 2T..,,TNND
exp
Σ
V/
exp(-2)
1=0
T
T Z
E 2'D
exp
V
Fi
exp( (-2) exp(-2)
exp
t=1
1=0
where in the second inequality we use the independence of 8ú with (W with respect to the filtration Ft. Recalling that X = c, where > 0 is a sufficiently small universal constant, we have that
Pr
Σ
V 2 Z
< exp (CoP)2 Z) exp (C - Z)
Setting Z = C + log(1/6) and taking c to be a sufficiently small absolute constant (as is done in our algorithm), we get that Prz Prgi....,Taa. 2nD Σ V 2 Z 5. This completes the proof of Lemma 2.8
Assume that until the round T the event Hy holds, i.e., for all i E [T] we have that errp (w*) 2 1) t.
Using Lemma 2.8 onto Inequality (7) with probability at least 1 - 6, we have that:
T
T
|| |W
S || wo11 1
Xe (err (w") n) +
I || - w11 - cTe2 log(1/8).
Running the algorithm for T = ((log(1/))/C) 1/6)/(E272)) iterations guarantees that with probability at least 1 1-6 8, we will have that ||w"* ie., in the case where all the events H; for i [T] hold, TT+ achieves the same error as the optimal halfspace, thus it has 0-1 error of at most 7) + Therefore, at least
w 113 < O, which means 7'++1 w In that case,
vector w with
t' E [T' + 1] achieves 0-1 еттоr of at most + The algorithm, in Step (5), returns a vector w that has 0-1 error most erT (W) I min err (w") + E S 7 + 2e. The algorithm requires N = O(log(T (8/)/(((111 2n))) samples for Step ( due to [MN06]. The algorithm draws a sample in each round and runs for at most 7' rounds. Therefore, Algorithm [ draws samples. The algorithm needs to test each of the T hypotheses with N samples to find the closest one. Therefore, the total runtime OdT (as in the other subroutines the algorithm uses the samples only to estimate the gradients g, which requires O(1) additions of d-dimenional vectors). This completes the proof of Theorem 2.1
= N + T = (loggL/8))((22))
3 Conclusions and Open Problems
In this paper, we give the first sample near-optimal and computationally efficient algorithm for learning margin halfspaces in the presence of Massart noise. Specifically, the sample complexity of our algorithm nearly matches the computational sample complexity of the problem and its computational complexity polynomial in the sample size. An interesting direction for future work is to develop a sample near-optimal and computationally efficient learner for general halfspaces (i.e., without the margin assumption). While our approach can likely be leveraged to obtain an efficient algorithm with sample complexity (d) , the sample dependence on the dimension d would be suboptimal. Obtaining the right dependence on the dimension seems to require novel ideas, as prior works rely on fairly sophisticated methods [DV04 DKT21 2T3 to effectively reduce to the large margin case.

---

Acknowledgments
ID was supported in part by NSF Medium Award CCF-2107079 and H.I. Romnes Faculty Fellowship. NZ was supported in part by NSF Medium Award CCF-2107079.
References
[ABHU15] P. Awasthi, M. F. Balcan, N. Haghtalab, and R. Urner. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, pages 167-190, 2015.
[ABHZ16] P. Awasthi, M. Balcan, N. Haghtalab, and Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, pages 152-192, 2016.
[AL88] D. Angluin and P. Laird. Learning from noisy examples. Machine Learning, 2(4):343- 370, 1988.
[Blu03] A. Blum. Machine learning: My favorite results, directions, and open problems. In 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 1 11-14, 2003.
[CKMY20] S. Chen, F. Koehler, A. Moitra, and M. Yau. Classification under misspecification: Halfspaces, generalized linear models, and connections to evolvability. In Advances in Neural Information Processing Systems, NewrIPS, 2020.
[CKMY21] S. Chen, F. Koehler, A. Moitra, and M. Yau. Online and distribution- robustness: Regression and contextual bandits with huber contamination. In FOCS, 2021.
[CKST24) G. Chandrasekaran, V. Kontonis, K. Stavropoulos, and K. Tian. Learning noisy halfs- paces with margin: Massart is no harder than random. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[DDK + 23a] I. Diakonikolas, J. Diakonikolas. D. M. Kane, P. Wang, and N. Zarifis. Information computation tradcoffs for learning margin halfspaces with random classification noise. In COLT, 2023.
[DDK 23b] I. Diakonikolas, J. Diakonikolas, D. M. Kane, P. Wang, and N. Zarifis. Near-optimal bounds for learning gaussian halfspaces with random classification noise. In NeurlPS, 2023.
[DGT19] I. Diakonikolas, T. Gouleakis, and C. Tzamos. Distribution- PAC learning of halfspaces with Massart noise. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 4751-4762 Curran Associates, Inc., 2019.
[2] I. Diakonikolas, Impagliazzo, D. M. Kane, R. Lei, J. Sorrell, and C. Tzamos. Boosting in the presence of Massart noise. In Proceedings of The 34th Conference on Learning Theory, COLT, 2021.
[DK22] I. Diakonikolas and D. Kane. Near-optimal Statistical Query hardness of learning halfspaces with Massart noise. In Conference on Learning Theory, volume 178 of Pro- ceedings of Machine Learning Research, pages Version 2021: Arxiv eprint: 2012.09720.
PMLR, 2022. Preliminary
[DKK + +20 I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. A polynomial time algorithm for learning halfspaces with Tsybakov noise. arXiv, 2020.
[DKK T 21] I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Efficiently learning halfspaces with Tsybakov noise. STOC, 2021.
[2KK+22] I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with general Massart noise under the gaussian distribution. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pages 874-885. ACM, 2022.
10

---

[DKMR22] I. Diakonikolas, D. Kane, P. Manurangsi, and L. Ren. Cryptographic hardness of learning halfspaces with Massart noise. Advances in Neural Information Processing Systems, 2022.
[DKRS22] I. Diakonikolas, D. Kane, L. Ren, and Y. Sun. SQ lower bounds for learning single neurons with Massart noise. In Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurIPS 2022, 2022.
[DKT21] I. Diakonikolas, D. Kane, and C. Tzamos. Forster decomposition and learning halfs- paces with noise. In Advances Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurIPS 2021, pages 7732-7744, 2021.
[DKTZ20a] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with Massart noise under structured distributions. Conference on Learning Theory, COLT, 2020.
[DKTZ20b] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with Tsybakov noise. arXiv, 2020.
[DKTZ24] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Online Linear Classification with Massart Noise, 2024. Arxiv eprint: 2405.12958.
[DPT21] I.
Diakonikolas, J. Park, and C. Tzamos. Relu regression with Massart noise. In Advances in Neural Information Processing Systems, 2021.
[DTK23] I. Diakonikolas, C. Tzamos, and D. M. Kane. A strongly polynomial algorithm for approximate forster transforms and its application to halfspace learning. In Proceedings of the 55th Anmual ACM Symposium on Theory of Computing, STOC 2023, pages 1741-1754. ACM, 2023.
[DV04] J. Dunagan and Vempala. Optimal outlier removal in high-dimensional spaces. Computer & System Sciences, 68(2):335-373 2004.
[JL84] W. Johnson and Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. Contemporary Mathematics, 26: 1892206, 1984.
[3]] V. Kontonis, F. Iliopoulos, K. Trinh, C. Baykal, G. Menghani, and E. Vee. Slam: Student-label mixing for distillation with unlabeled examples. In Advances in Neu- ral Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, 2023.
[MN06] P. Massart and E. Nedelec. Risk bounds for statistical learning. Ann. Statist,, 3445):336- 2366, 10 2006.
[NT22] R. Nasser and S. Tiegel. Optimal SQ lower bounds for learning halfspaces with Massart noise. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1047-1074, PMLR, 2022.
[Ros58] F. Rosenblatt. The Perceptron: probabilistic model for information storage and organization in the brain. Psychological Review, 65:386-407, 1958.
[Slo88] R. H. Sloan. Types of noise in data for concept learning. In Proceedings of the First Annual Workshop on Computational Learning Theory, COLT '88, pages 91-96, San Francisco, CA, USA, 1988. Morgan Kaufmann Publishers Inc.
[Slo92] R. H. Sloan. Corrigendum types of noise in data for concept learning. In Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, COLT 1992, page 450, 1992.
[SSBD14] S. Shalev-Shwart and Ben-David. Understanding machine learning: From theory algorithms. Cambridge university press, 2014.

---

[S207] S. Smale and D. Zhou. Learning theory estimates via integral operators and their approximations. Constructive approximation, 26(2):153-17,, 2007.
[Va184] G. Valiant. A theory the learnable. In Proc. 16th Annual ACM Symposium on Theory of Computing (STOC), pages 436-445, ACM Press, 1984.
[Ver18] R. Vershynin. High- High-Diiensiooal Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cam- bridge University Press, 2018
[YZ17] S. Yan and Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pages 1056-1066, 2017.
[ZI.C17] Zhang, P. Liang, and M. Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 20/7, pages 1980-2022, 2017.
12

---

Supplementary Material
Organization The structure of this appendix is as follows: In Appendix A we provide additional summary and comparison with related and prior work. In Appendix cutting-planes based algorithm with sample complexity ((1/(E"7")) Finally, in Appendix C we provide the proof's omitted from Section 2
B we provide a polynomial time
A Related and Prior Work
A.1 Additional Related Work
The computational problem of learning halfspaces with Massart noise has been extensively studied, both in the distribution-spedd specific and the distribution-fre settings.
In the distributionnsseccieee setting, the first efficient algorithm for homogeneous Massart halfspaces was given in [ABHU15]. Subsequent work generalized this result in various directions [ABHZ16
ZLCI7 YZ17 DK22200 DKT2206
DKK 20 DKK* + 21 DKK+22 22].
The first algorithmic progress in the distribution-free setting was made by [DGT199, answering a longstanding open problem [SS088] Slo92] Blu03). Subsequent work gave an algorithm with improved sample complexity [CKMY20) and provided strong evidence that an error of rn + e is the best to hope for in polynomial time [D222 NT22, DKMR22] (in both the Statistical Query model and under plausible cryptographic assumptions). In a related direction, [DIK 21 gave the first efficient boosting algorithm in the presence of Massart noise, which can boost weak learner to with error 7) + Finally, we note that natural generalizations of the Massart model to learning real-valued functions (in an essentially distribution- freee setting) have also been studied [CKMY21 DPT21 DKRS22).
Very recent work 223l+ gave SQ (and low-degree polynomial testing) lower bounds for learning 7-margin halfspaces with RCN [AL88] which is special case of Massart noise. Specifi- cally, [DDK 23al showed that any efficient SQ algorithm for the problem requires sample complexity ((2/()212222) Subsequently, [DDK + 23b) showed related SQ lower bound under the Gaussian distribution, which can be adapted to obtain lower bound of [2 ((11(r)e²)) for the margin setting.
A.2 Comparison with [KTZ244]
The work [DKTZ24] uses similar sequence of loss functions for the problem of "online learning" Massart margin halfspaces. Intuitively, their goal is to minimize regret in an adversarial online setting. In their online setting, the adversary in each round commits to covariates x' x² E Rd and distribution D' over R, x R.. Then the algorithm observes the covariates, chooses an action E 21, and observes a reward r, E R.. It is only guaranteed that there exists unit vector w so that (r (ssig>)ss(((((((/ [sign( w x w" x²) rb)] 2 A for some A >> 0.
Despite this superficial similarity, the work of [DK1724] has no new implications on the sample complexity of PAC learning Massart halfspaces with margin. Specifically, they achieve a regret bound of OTT3/4/2) /7). If one translates this bound to a sample complexity upper bound for PAC learning, one would obtain a bound of ((1/(c(77)) which is quantitatively worse than prior work of [DGT19 CKMY20)
At a technical level, our work leverages this sequence of loss functions as subgradients of the potential function ((w) = ||w w'113. Via a novel analysis, we show that these subgradients ((c)-corellate with the direction of w w This in turn means that we can expect a decrease of order ((Ae) in each iteration, where the corresponding step-size, as long as we get 0-1 error more than 7) + e. This structural understanding suffices for obtaining an algorithm, based on separation oracle, that achieves sample complexity of Ō(1/ In order to obtain an algorithm with near-optimal sample complexity (and runtime), we required additional new ideas as elaborated in the body of the paper.
13

---

B Learning Margin Massart Halfspaces via Cutting Planes
In this section, we show how to use the botting-planes method along with Lemma 2.2 to efficiently learning margin Massart Halfspacce using ((1((7Ae)) samples. Specifically, we establish the following result:
Theorem B.1 (Learning Margin Massart Halfspaces with Cutting Planes). Let D be a distribution on gd-1 x {=1} which satisfies the M-Massart noise condition with respect to the "i-marin halfspace f(x) = sign(w"-x] Given N = (Llo(11((7))/( ((rr))/((()))))))) (x)))) i..dd samples D, there is a poly(d, N) time algorithm that returns vector w such that err (w) S 1 + with probability least 1 6.
Remark B.2. We can always assume that d (LL/2²). This holds since can efficiently preprocess the data, using the Johnson-Lindenstrauss transform [L84]. Similar dimension-reductin
steps have been use in prior work, e.g.. [CKMY20] DDK 23a].
Given the above remark, it suffices to establish the following:
Theorem B.3. Let D be a distribution on gd-1 x [+1} which satisfies the 17-Mssaar noise condition with respect to the y-margin halfspace [(x) = (ing x). Given N = (d (1)(1
i.i.d. samples from D, there a poly(d, N) time algorithm that returns vector such that erI S 17 + with probability at least 6.
The idea of using the cutting plane method is slightly adapted from [CKMY20]. Given access to separation oracle for convex K, we can find point inside the K. by querying the separation oracle O(d log d) times. The difference with [CKMY20) is that we are using a more sophisticated (and sample efficient) separation oracle. This allows us use (1)c²) samples, instead of ((1/²²) samples, and leads to the optimal sample complexity as function of (but not 7).
Fact B.4. Suppose that K. is (unknown) convex body in Rd which contains a Euclidean ball of radius r > O and contained in a Euclidean ball centered at the origin of radius R >> 0. There exists an algorithm which, given access separation oracle for K. finds point x" K. runs in time poly R/r), d), and makes (d (ddoog(dd/r) calls to the separation oracle.
We first show that if we get enough samples, we can efficiently approximate the gradients G(w, w). Formally, have:
Proposition B.5 (Separation Oracle). Let c, 10, and let D be a distribution on Sd-1 x {+1} satisfying the M-Massart noise condition with respect to the halfspace f(x) sign(w" x). Fix
E & with ||w]|2 I 1. Let N 2 log(1/(75)) (E22)) and Dy be the corresponding empirical distribution. Then, with probability at least 6, it holds that
G Dx (w, w) (w (w" 2 2(errD(w) 1) 66
Proof. By construction, G Gp (w, (W,w) w)
Dx (w) G (w) and by Lemma 2.2 Dy have that G. D, (w) (w w") 2 2(eIT DN (w) - m) By definition, we have
(()".))))... (x()), (x))) G2 (w)] = O, where the expectation is taken with respect to the sam- Dy
ple set. Note that the norm of g" (w, x), g² g.(,,,, x, y). i.c., (w, x)112, llg((w, x, y)1.2. is bounded pointwise from above by 4/y for all w E Rdd This can be seen as ||x||2 S (W37/2) S 2/7, and (1 - 2n), (1 21)(x)) < 1.
We the following concentration inequality show that our sample size is enough guarantee that the estimated gradient is close to its population version.
Fact B.6 ([S707, Lemma 1). Let Zi.... Zn E R2d be random vectors such that for each i E [n]] it holds |Z < M < oo almost surely and let o² -E= E 11).. Then, we have that for any
e > 0,
(-
1 nMe)
))
Pr
n Σ
(Z,
E|Z.)
20
< 2 exp
log
2M
o²
14

---

Using Fact B.6. along with the inequality log(1 + 2) 2 2/2, for (0, 1), we get that if N 2
( (0)) with probability least 1 8, we have
(e7)*
G G (w)
E (x.1)
g (w, (w. x)
ce.
(8)
and
G (w)
E (x,y)-
x, w) [g 1 (w,
66.
(9)
To complete proof, recall that by Lemma it holds G DN (w)-(w-w) 2 2(err (w) -c. Therefore, by taking the expectation over Dx, we get that
(w) (w w> 2 2(errn(w) -n)
The proof is completed by recalling that G Dx (w) ((x.)) (w, S c from Inequality (8) and that E (x.a)= (gggg,wwww
(w, (w,,,,) y) 0.
we are ready to prove a weaker version of Theorem 2.1 using separation oracles and the cutting plane algorithm. Formally, we show that
Equipped with Proposition B.5
Proof of Theorem B.3 Our convex set K. is Euclidean ball of radius 7/2 centered at w To see that, note that for any such that ||w" vll2 7/2, we have that [w* v) x| 7/2 for any with ||x||a = 1. This implies that 7/2 + w - 2 v w X 15--1 7/2. Moreover, by definition we have that w
7. Hence, if w 2 that v x < -7/2. Therefore, this ball contains all the vectors w with margin 7/2 and separates the points in the same way as w
have that x 2 7/2; and if w x S
have
Therefore, as long as we are not in the set K or the 0-1 eπтоr more than + e, we can use separation oracle. By Fact B.4] the maximum number of calls
Proposition B.5 to construct = O(d By Proposition B35 in each round we need n =
to the separation oracle (log(T/5))/((2) samples from D construct separation oracle. Therefore, the maximum number samples is O(TT) = O(dlog(T/8)/((e) This completes the proof.
C Omitted Proofs from Section 2
C.1 Proof of Claim
Claim C.1 (Claim 2.1 DGT19 For any w, x, have that
8 (x(w,x,y) (1 x) S 0] A)/w x
Proof. Recall that (x(w, x, v) BeakyReLU, = =0 (/(p 03(-xwxxx.
Therefore, we have that
Ex (w (1 A)1(3(w x) S 0}lyw x -A1fy(W x) > 0//yw x/
= 1 03/w x/ A/w. = [1yy(w 50} - 2) w w.xl x/,
where we used that E {+1).
C.2 Proof of Claim 2.3
We restate and prove the following claim:
w. -1) Claim 2.3. For any (9) Rí, have that g¹ (w, (w- w") > (x,
15

---

Proof of Claim
2.3 For any x E R1, we have that
g' (w, B'(w,x(1) (0) w (1 2n))sign(ww x))) - (1- (1-21)(x(0) )sign((" (w" (xx"))))))))))))))))))))))))(( w x W(W (w. x(1)
(1 2n)ssgg((w . x))) - (1 - -21((x()) )sigg((" (w''x(')) sign w . x)))
2(err(w, x(1)) 11)
(10)
where we used that for any x0) E R1, W(w . x(0) = 1//w x00 and hence W(w (()),//)w
x()) = sign(w x and that crr(w, x() = n7(x(1) if sign(w x()) = sign(w" x(1) and
1 - (x)))) otherwise.
We now bound the contribution of w". Since n7(x) S 17, we have
(1- (n))) - (1 (11))sigg((w) (w- x)sign("""x))
Therefore, we have that
((,,((1) w- = (11 ((1-21)ssgni 21))sign(ww x) (1 22{(x))signnw x) sigu(w".xx -x)] xx)]=*xx(100 xx(W(w (w x(())
(11 21)(x)) - (1 21)ssinn( (w- x)sign(w* .x)
x) /w- .x[W x()) s 5O,
which gives that -g (w, x()) w 2 0. This completes the proof of Claim 2.3
C.3 Proof of Claim
We restate and prove the following:
Claim 2.4.
For any ( E R2, we have that g (w,, (w - w*) 2 2(err(w, x(1)) 11)
Proof of Claim 2.4 We have that
g' (w, x9) (w - ww)= = (1 (1-2))sig((w w- x x()) (1-27(x' ))sig() xx()) x(1) w x(1) 1max(1/22 | x(11
w x() -w x()
(1 2n)sign w x (1) (1 - 227(x(()) )s)gg(( x(())
7/2
where we used that max(?//2 |w x 7/2 for any x(6) E R2. Since sign(w" (w" x) has 7- margin, we have that |w" x((1 2 y. Since x(1) E R2, it holds |W x(0) 7/2. Therefore, -sign(w" x()) x()) w x) (lw* x(0 sign(w* x(0) x()) 2 7/2. This in
turn implies that
g s'(w, (0) (w w*) 2 (1 217(x(()) (1 1--20 2n)sign(w x(1) ssign(w" xx(x)))))) x())))
= 2 w, x1) - 17)
completing the proof of Claim 2.4
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract summarizes the result provided in Theorem 1.3 (and Theorem 2.1].
The introduction describes how this contribution resolves open problem in the literature by summarizing the motivation for the model and describing prior work's 's contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations are clearly stated in the statements of each theorem and are discussed in the introduction of the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
17

---

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

---

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

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper is theoretical in nature and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttp:://eeurjpp: httpa/awwww.....pppapccccccccaaa
Answer: [Yes]
Justification: Our research conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is theoretical and we do not see any major or immediate implications society.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work is theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This work does not use any assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

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


Reviews:
[{"review_id": "kMLsiDHzLk", "reviewer": "Reviewer_g5LR", "summary": "This paper essentially resolves the *computational sample complexity* of learning $\\gamma$-margin halfspaces under the Massart noise model. Here, computational sample complexity refers to the number of samples required for polynomial-time algorithms, as opposed to general statistical estimators which may be computationally intractable. Previous works have given rigorous evidence, in the form of lower bounds against large classes of algorithms such as SQ algorithms, of an *information-computation* gap for learning $\\gamma$-margin halfspaces. Without restrictions on computation, the sample complexity is $\\Theta(1/(\\gamma^2 \\epsilon))$ for achieving zero-one loss of $\\eta + \\epsilon$, where $\\eta$ is the uniform bound on the Massart noise. For a large class of efficient algorithms, however, the required sample complexity is at least $\\Omega(1/(\\gamma^2 \\epsilon^2))$.\n\nThey show that the $1/(\\gamma^2 \\epsilon^2)$ sample complexity is essentially tight by designing a polynomial-time algorithm for learning $\\gamma$-margin halfspaces. Their algorithm is based on a novel and technically insightful choice of the loss sequence for online SGD, which results in a surprisingly simple and efficient algorithm with near-optimal sample complexity.", "questions": "- Does the near-optimal online SGD algorithm fall within the class of SQ algorithms? If not, could there still exist non-SQ algorithms that achieve sample complexity with subquadratic dependence on $1/\\epsilon$?", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is a well-written paper that stands out for being both technically insightful and simple. A simple and efficient algorithm (online SGD with a specific choice of loss sequence) achieves optimal sample complexity and lends itself to a clean analysis. It's hard to ask for more than this. \n\nThe core idea behind the algorithm is a clever choice of the loss sequence $(\\ell_t)$ with respect to which one runs online SGD. Previous works have already employed the LeakyReLU loss as a convex surrogate for the zero-one loss and achieved suboptimal upper bounds on the sample complexity. LeakyReLU with parameter $\\lambda > 0$ is defined by $\\ell_\\lambda(a) = (1-\\lambda) \\mathbb{1}[a \\ge 0] + \\lambda \\mathbb{1}[a < 0]$. Applying this to the halfspace learning setting, a straightforward calculation shows that $\\ell_\\lambda(-y (w \\cdot x)) = (\\mathbb{1}[\\mathrm{sign}(w\\cdot x) \\neq y] - \\lambda)|w \\cdot x|$, where $(x, y) \\in \\mathbb{S}^{d-1} \\times \\\\{\\pm 1\\\\}$ is a sample from the $\\gamma$-margin halfspace distribution and $w \\in \\mathbb{R}^d$ is a candidate halfspace. Note the resemblance to the *shifted* zero-one loss $L(w) = \\mathbb{E}_{(x,y)} \\mathbb{1}[\\mathrm{sign}(w\\cdot x) \\neq y] - \\eta$ (when $\\lambda = \\eta$ in LeakyReLU). By the $\\eta$-Massart noise assumption, $L(w^{\\*}) \\le 0$ for the optimal halfspace $w^{\\*} \\in \\mathbb{R}^d$ and $L(w) \\ge \\epsilon$ for any halfspace $w$ with zero-one loss at least $\\eta + \\epsilon$. \n\nThe key difference between this shifted zero-one loss and the LeakyReLU is the $|w \\cdot x|$ term. In particular, if we reweight each sample LeakyReLU loss by $1/|w \\cdot x|$, we recover the shifted zero-one loss which is unfortunately non-convex. The authors overcome this issue by considering a *family* of bounded and convex loss functions $(\\ell_u)$ indexed by $u \\in \\mathbb{R}^{d}$. Each $\\ell_u$ is simply the LeakyReLU loss reweighted by $1/|u \\cdot x|$. It is precisely this decoupling of the halfspace parameter $w$ and the reweighting parameter $u$ that leads to the guarantees of the algorithm. The *sequence* of reweighting parameters $(u_t)$, each of which leads to a different loss $\\ell_t$, is chosen adaptively by online SGD.", "weaknesses": "I did not find any significant weaknesses, only minor comments regarding the presentation.\n\n- **The expression \"(vector) v is independent of w\" (line 174, 176) is confusing.** I think it's easy to confuse \"independence\" with statistical independence. It would be helpful to clarify this by adding that the reweighting term is *constant* with respect to the parameter $w \\in \\mathbb{R}^d$, and the reweighting term $W(v \\cdot x, \\gamma)$ remains the same when taking the gradient of $L_{v}(w)$. This is already implicit in the mathematical expressions, but providing additional explanation would benefit readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper and for the positive feedback. Below we provide specific responses to the points and questions raised by the reviewer.\n\n> (Weaknesses 1): The expression \"(vector) v is independent of w\" (line 174, 176) is confusing. I think it's easy to confuse \"independence\" with statistical independence. It would be helpful to clarify this by adding that the reweighting term is constant with respect to the parameter $w \\in \\mathbb{R}^d$, and the reweighting term $W(v \\cdot x, \\gamma)$ remains the same when taking the gradient of $L_{v}(w)$. This is already implicit in the mathematical expressions, but providing additional explanation would benefit readers.\n\n*Response:*  We thank the reviewer for this suggestion. We will clarify this point in the final version of the paper.\n\n> (Question 1) Does the near-optimal online SGD algorithm fall within the class of SQ algorithms? If not, could there still exist non-SQ algorithms that achieve sample complexity with subquadratic dependence on $1/\\epsilon$?\n\n*Response:* The online GD algorithm (using a batch size) can indeed be efficiently implemented as an SQ algorithm. As we explain below, our algorithm can be formulated in this way. Therefore, the previously known SQ lower bound covers the algorithm developed in our paper. In more detail, this can be seen as follows: in each iteration of our algorithm, the update rule calculates the gradient -- which is of the form $g=\\mathbf{E}[f(x,y)]$ --  where $f$ can be viewed as the query function in the SQ model. \n\nWe also note that prior work established the same information-computation tradeoff for the class of low-degree polynomial tests (in addition to SQ algorithms). Historically, lower bounds against SQ algorithms and low-degree polynomials have been viewed as strong evidence of hardness. That said, these are restricted models of computation and it is in principle possible that an algorithm can surpass them.", "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": "nmroPY0272", "reviewer": "Reviewer_SyXT", "summary": "The paper studies the problem of learning a $\\\\gamma$-margin halfspace with $\\\\eta$ Massart noise and provides the first computationally efficient algorithm having 0-1 error $<= \\\\eta + \\\\varepsilon$ with sample complexity $O(1/\\\\gamma^2\\\\varepsilon^2)$ which nearly matches the information theoretic bound of $O(1/\\\\gamma^2\\\\varepsilon^)$ improving upon the previous $O(1/\\\\gamma^4\\\\varepsilon^3)$ sample complexity by [Chen et al. ‘20].\nThe main contributions of the paper are a novel “global” (as opposed to previous conditioning based) optimization to solve this problem directly using gradient descent. Towards this, a novel convex loss is defined using an independent vector as a parameter, and using the margin as a bound on the scaling parameter. The gradient w.r.t. the solution vector is used in an SGD loop, while the independent vector is updated by the gradient step, and its projection on the unit ball is the updated solution. This clever formulation leads to the gradient being composed of the “correct” direction of optimization along with an estimation error. The former minimizes the distance to the true solution, while the latter is bounded using standard concentration arguments.", "questions": "In Algorithm 1, $\\\\lambda_t$ seems to be a constant independent of $t$, so it can be fixed outside the loop.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Novel loss formulation and gradient update step which can be directly used via SGD.\n2. Simple algorithm and analysis.\n3. Near optimal computational bound on an important problem.", "weaknesses": "Result is specific to a particular noise model and it is not clear if the techniques are more broadly applicable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and the provided questions. We respond to each point raised by the reviewer below. \n\n> (Weaknesses 1):Result is specific to a particular noise model and it is not clear if the techniques are more broadly applicable.\n\n*Response:* We would like to point out that the Massart (or bounded noise) model is essentially the strongest label noise model that allows for polynomial-time algorithms in the distribution-free PAC setting. In particular, if the label noise is fully adversarial (agnostic model), it is computationally hard to achieve any non-trivial error guarantees for the class of margin halfspaces (aka to achieve \"weak learning\"); see [1,2,3]. Moreover, we believe that the problem we study and the results themselves are interesting in their own right (the algorithmic complexity of the problem has been a longstanding open question; the NeurIPS'19 paper on the topic received the best paper award at that conference and has subsequently had a significant impact). That said, while our focus has been on this particular problem, we believe that the technical analysis of our algorithm could be of broader interest. Specifically, we feel that our white-box analysis of online SGD is novel and could be useful elsewhere. Moreover, the reweighting scheme that we employ may be useful in other problems, as it provides a method to *convexify* the 0-1 loss.\n\n> (Question): In Algorithm 1, $\\lambda_t$ seems to be a constant independent of $t$, so it can be fixed outside the loop.\n\n*Response:*  Thank you for pointing this out. We will move $\\lambda_t$ outside the main loop.\n\n\n\n[1] Hardness of Learning Halfspaces with Noise, Venkatesan Guruswami, Prasad Raghavendra, FOCS 2006\n\n[2] Complexity Theoretic Limitations on Learning Halfspaces, Amit Daniely, STOC 2016\n\n[3] Hardness of agnostically learning halfspaces from worst-case lattice problems, Stefan Tiegel, COLT 2023", "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": "TJgQ9h8XSg", "reviewer": "Reviewer_JiXV", "summary": "This paper studies the problem of PAC learning $\\gamma$-margin halfspaces under Massart noise: to PAC learn any distribution $D$ such that there exists $w^*$ with the bounded norm of $1$ that has a margin of at least $\\gamma$, i.e. $\\mathbb{P}_{(x,y)\\sim D}( |\\langle w^*,x \\rangle| \\geq \\gamma)=1$ and for every $x$, we have $\\mathbb{P}(\\text{sign}(\\langle w^*,x \\rangle) \\neq y )=\\eta(x)$, where a function $\\eta$ is bounded in $[0,\\eta]$ (with overload of notation).\n\nThis is a classical problem in learning theory. Information theoretically, one needs $\\tilde{\\Theta}(1/\\gamma^2 \\epsilon)$ samples, while for computationally efficient algorithms, it is widely believed that inverse quadratic dependence in $\\epsilon$ (e.g. $1/\\epsilon^2$) is necessary. \n\nThe main result of this paper is to present an efficient algorithm with nearly optimal sample complexity $\\tilde{O}(1/\\gamma^2 \\epsilon^2)$, essentially closing the question.", "questions": "None.", "limitations": "This is a theoretical work with no societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper studies a problem that is important to the learning theory community and provides a state-of-the-art result. The previous best algorithm required $O(1/\\gamma^4 \\epsilon^3)$ samples.\n2. The paper is well-written.", "weaknesses": "I do not see any major weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing our paper and the positive feedback.", "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": "afwRJni69d", "reviewer": "Reviewer_Sz9S", "summary": "The paper considers the problem of PAC-learning $\\gamma$-margin halfspaces under $\\eta$-Massart noise. The paper provides an efficient algorithm achieving error $\\eta+\\epsilon$ with sample complexity $\\tilde{O}(1/(\\epsilon^2\\gamma^2))$. Since previous work provided evidence that an inverse-quadratic dependence on $\\epsilon$ is necessary for efficient algorithms, the algorithm appears to be near-optimal in terms of sample-complexity up to logarithmic factors.\n\nThe algorithm relies on an iterative stochastic-gradient descent approach, where at each iteration a new loss function is defined which determines the gradient descent of the next iteration. The paper proves that if $T$ iterations are performed (where $T$ is a sufficiently large multiple of $\\log(1/\\delta)/(\\epsilon^2\\gamma^2)$), then with probability at least $1-\\delta$, one of the halfspaces obtained in $T$ iterations have error at most $\\eta+\\epsilon$. By drawing some extra independent samples and computing the empirical error for each of these halfspaces, one can find a good halfspace.\n\nThe paper is generally well written.", "questions": "- The authors claim that the computational complexity of the algorithm is linear in the samples. However, it seems to me that the complexity of step (5) is $O(T\\cdot N\\cdot d)$. It does not seem to be trivial to implement step (5) in $O((T + N)\\cdot d)$ time.\n\n- While previous work show that $\\Omega(1/(\\gamma^2\\epsilon))$ and $\\Omega(1/\\epsilon^2)$ are lower bounds, it doesn't necessarily follow that  $\\Omega(1/(\\epsilon^2\\gamma^2))$ is a lower bound as well.", "limitations": "Since this is a theoretical paper, I can't see any potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a near-optimal algorithm (in terms of sample complexity) for learning $\\gamma$-margin halfspaces under Massart noise.", "weaknesses": "I haven't found significant weaknesses in the paper.\n\nTypos:\n- Page 2, line 34: “We say that that the distribution” ->  “We say that the distribution” \n- Page 5: Line 195: If I am not mistaken, the function g is twice the gradient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reading our paper and the positive assessment. We respond to each point raised by the reviewer below.\n\n>(Question 1): The authors claim that the computational complexity of the algorithm is linear in the samples. However, it seems to me that the complexity of step (5) is $O(T\\cdot N\\cdot d)$. It does not seem to be trivial to implement step (5) in $O((T + N)\\cdot d)$ time.\n\n\n*Response:* Yes, the reviewer is correct. We will fix the statement about the runtime where appropriate. As the reviewer notes, the running time incurs an extra $1/\\epsilon$ multiplicative term (up to logarithmic factors). That is because $N$ is set to $\\tilde{O}(\\log(1/(\\delta\\gamma))/(\\epsilon (1-2\\eta)))$ and we need to evaluate each of the $T$ hypotheses to return the best one.\n\n>(Question 2):  While previous work show that $\\Omega(1/(\\gamma^2\\epsilon))$ and $\\Omega(1/\\epsilon^2)$ are lower bounds, it doesn't necessarily follow that $\\Omega(1/(\\epsilon^2\\gamma^2))$ is a lower bound as well.\n\n\n*Response:* We agree with the reviewer about prior work on hardness, and we will adjust our phrasing. In more detail, the best known lower bound for the computational sample complexity of this problem is $\\tilde{\\Omega}( 1/(\\epsilon \\gamma^2)+1/(\\gamma\\epsilon^2) )$, and applies to SQ algorithms and low-degree polynomial tests. The first term is the information-theoretic sample complexity [MN06] and the second term follows from [DDK+23a,DDK+23b]. \n\nWhile we have good reason to believe that these hardness results can be improved to give a lower bound of $\\Omega(1/(\\epsilon^2\\gamma^2))$, this remains an open problem.", "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": "V8wJa7tRW5", "reviewer": "Reviewer_2xNf", "summary": "The paper considers the problem of PAC learning halfspaces with margin in the presence of Massart noise. The paper provides an algorithm that well-balances sample and computational efficiency. Specifically, the dependence of the algorithm on both $\\epsilon$ and $\\gamma$ is near-optimal.", "questions": "Questions:\n1. I'm not sure about the statement \"...we essentially settle this question...\"  in line 71. As far as I understand, the optimal computational sample complexity might be $\\tilde{O}(1/\\epsilon^2 + 1/\\epsilon \\gamma^2)$ and not $\\tilde{\\Omega}(1/\\epsilon^2 \\gamma^2)$. Either way, the provided upper bound is impressive enough to recommend for acceptance.\n2. Is there a specific reason not to discuss the agnostic case? Is it usualy considered in Massart noise problems?\n\n\nSuggestions:\n\nConsider writing what is $\\eta$ in the abstract.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is fundamental in the area of PAC learning, and the paper provides a significant progress on it.\n2. The paper is well written, and the main techniques are well explained.", "weaknesses": "1. Results might be somewhat weaker than presented (see questions), and some phrasings in this context are too vague (for example \"there is evidence that...\").\n2. The natural agnostic extension of the problem is not discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reading our paper and the positive assessment.  We respond to each point raised by the reviewer below. \n\n>(Weakness 1): Results might be somewhat weaker than presented (see questions), and some phrasings in this context are too vague (for example \"there is evidence that...\").\n\n*Response:*  We thank the reviewer for this feedback. We will make our statements of prior information-computation tradeoffs precise. In the submitted version, we did not discuss these results in detail due to space limitations. Please see response below for more details.\n\n>(Weakness 2): The natural agnostic extension of the problem is not discussed.\n\n*Response:*   For distribution-free agnostic PAC learning, the learning problem we study is known to be computationally intractable (even for weak learning). Specifically, it is is NP-Hard [1] for proper learning and cryptographically/SQ-hard for improper learning [2,3]. These hardness results have historically been one of the motivations for studying the Massart model.\n\n>(Question 1): I'm not sure about the statement \"...we essentially settle this question...\"  in line 71. As far as I understand, the optimal computational sample complexity might be $\\tilde{O}(1/\\epsilon^2 + 1/\\epsilon \\gamma^2)$ and not $\\tilde{\\Omega}(1/\\epsilon^2 \\gamma^2)$. Either way, the provided upper bound is impressive enough to recommend for acceptance.\n\n*Response:* As the reviewer points out, the best known lower bound on the computational sample complexity of the problem is  $\\tilde{\\Omega}(1/(\\gamma\\epsilon^2) + 1/(\\epsilon \\gamma^2))$. This lower bound is quadratic in both parameters of interest but does not quite match our upper bound. While we believe that a lower bound of order $\\tilde{\\Omega}(1/(\\gamma^2\\epsilon^2))$ exists, this remains an open problem. Finally, we note that even for the easier model of Random Classification Noise (RCN), the best known efficient algorithm has sample complexity $\\tilde{O}(1/(\\gamma^2\\epsilon^2))$ (established recently in [DDK+23a]). \n\n>(Question 2): Is there a specific reason not to discuss the agnostic case? Is it usually considered in Massart noise problems?\n\n\n*Response:* See Response to  Weakness 2 above.\n\n\n\n> Suggestions: Consider writing what is $\\eta$ in the abstract.\n\n*Response:* Thank you. We will add this in the final version. \n\n[1] Hardness of Learning Halfspaces with Noise, Venkatesan Guruswami, Prasad Raghavendra, FOCS 2006\n\n[2] Complexity Theoretic Limitations on Learning Halfspaces, Amit Daniely, STOC 2016\n\n[3] Hardness of agnostically learning halfspaces from worst-case lattice problems, Stefan Tiegel, COLT 2023", "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:
We thank the reviewers for their time, effort, and feedback. We are  encouraged by the positive comments of reviewers, and that our paper was appreciated for the: (i) **significant contribution** (SyXT, JiXV, 2xNf); (ii) **technically novel** (g5LR,SyXT) and (iii) **writing quality** (g5LR, JiXV,  2xNf). We respond to specific comments below.

Meta-review: This paper advances state of the art results on efficient learning large-margin halfspaces with eta-Massart noise, with target error eta+epsilon; specifically its upper bound's quadratic dependences on 1/gamma and 1/epsilon are essentially not improvable in view of existing lower bounds. The reviewers also deemed the paper's technique of using online learning and convexifying the losses interesting. 

The authors are encouraged to incorporate the discussion with the reviewers to clarify the running time analysis and the sense of optimality of the sample complexity bounds in the final version.
Decision: Accept (spotlight)