A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

Authors: ilias  diakonikolas
nikos  zarifis
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:49:53

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.

Main paper: 
 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-valued function h : R d → {±1} of the form h(x) = sign (w • x -θ), where w ∈ R d is the weight vector and θ ∈ R is the threshold. The function sign : R → {±1} is defined as sign(t) = 1 if t ≥ 0 and sign(t) = -1 otherwise. The problem of learning halfspaces with a margin -i.e., under the assumption that no example lies too close to the separating hyperplane -is one of the earliest algorithmic problems studied in machine learning, going back to the Perceptron algorithm [Ros58] .In the realizable PAC model [Val84] (i.e., with clean labels), the sample complexity of learning γ-margin halfspaces on the unit ball in R d is Θ(1/(γ2 ϵ)), where ϵ > 0 is the desired 0-1 error; see, e.g., [SSBD14] 1 . Moreover, the Perceptron algorithm is a computationally efficient learner achieving this sample complexity. That is, without label noise, there is a 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 a distribution over X × {±1}, and let C be a class of Boolean-valued functions over X . We say that D satisfies the η-Massart noise condition with respect to C, for some η < 1/2, if there exists a concept f ∈ C and an unknown noise function η(x) : X → [0, η] such that for (x, y) ∼ D, the label y satisfies: with probability 1 -η(x), y = f (x); and y = -f (x) otherwise. Given i.i.d. samples from D, the goal of the learner is to output a hypothesis h : X → {±1} such that with high probability the 0-1 error err D (h) def = Pr (x,y)∼D [h(x) ̸ = y] is small.The concept class of halfspaces with a margin is defined as follows. Definition 1.2 (γ-Margin Halfspaces). Let D be a distribution over S d-1 × {±1}, where S d-1 is the unit sphere in R d . Let w * ∈ S d-1 and γ ∈ (0, 1). We say that the distribution D satisfies the γ-margin condition with respect the halfspace sign(w * • x)2 , if (i) for (x, y) ∼ D, we have that y = sign(w * • x), and (ii) Pr (x,y)∼D [|w * • x| < γ] = 0. The parameter γ is called the margin of the halfspace sign(w * • x).Information-theoretically, the best possible 0-1 error attainable for learning a concept class with Massart noise is opt := E x∼Dx [η(x)]. Since η(x) is uniformly bounded above by η, it follows that opt ≤ η; also note that it may well be the case that opt ≪ η. Focusing on the class of γmargin halfspaces, it follows from [MN06] that there exists a (computationally inefficient) estimator achieving error opt + ϵ with sample complexity O(1/((1 -2η)γ 2 ϵ)); and moreover that this sample upper bound is nearly best possible (within a 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 η is bounded from 1/2.) Taking computational considerations into account, the feasibility landscape of the problem changes. Prior work [DK22, NT22, DKMR22] has provided strong evidence that achieving error better than η + ϵ is not possible in polynomial time. Consequently, algorithmic research has been focusing on achieving the qualitatively weaker error guarantee of η + ϵ. We note that efficiently obtaining any non-trivial guarantee had remained open since the 80s; see Appendix A.1 for a discussion. The first algorithmic progress for this problem is due to [DGT19] , who gave a polynomial-time algorithm achieving error of η + ϵ with sample complexity poly(1/γ, 1/ϵ). Subsequent work [CKMY20] gave an efficient algorithm with improved sample complexity of Õ(1/(γ 4 ϵ3 )). 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-namely, Ω(1/(γ 4 ϵ 3 ))-than the information-theoretic minimum of Θ η (1/(γ 2 ϵ)). It 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 + 23a] (see also [DDK + 23b]) gave evidence for the existence of inherent information-computation tradeoffs in the Massart noise model-in fact, even in the simpler model of Random Classification Noise (RCN) [AL88] 3 . Specifically, they showed that any efficient Statistical Query (SQ) algorithm or low-degree polynomial tasks requires Ω(1/ϵ 2 ) samples-a near quadratic blow-up compared to the Õ(1/ϵ) information-theoretic upper bound. This discussion serves as the motivation for the following question:What is the optimal computational sample complexity of the problem of learning γ-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 a fine-grained sample complexity versus computational complexity analysis is interesting on its own merits. In this work, we develop a computationally efficient algorithm with sample complexity of Õ(1/(γ 2 ϵ 2 )). Given the aforementioned information-computation tradeoffs, there is evidence that this upper bound is close to 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 a final testing step that slightly increases the runtime.)Our main result is the following:Theorem 1.3 (Main Result, Informal).Let D be a distribution on S d-1 × {±1} that satisfies the η-Massart noise condition with respect to an unknown γ-margin halfspace f (x) = sign(w * • x).There is algorithm that draws n = Õ(1/(ϵ 2 γ 2 )) samples from D, runs in time Õ(dn/ϵ), and with probability at least 9/10 returns a vector ŵ such that err D ( ŵ) ≤ η + ϵ.The sample upper bound of Theorem 1.3 nearly matches the computational sample complexity of the problem (for SQ algorithms and low-degree polynomial tests), which was shown to be Ω(1/(ϵ 2 γ) + 1/(ϵγ 2 )) [MN06, DDK + 23a, DDK + 23b]. That is, Theorem 1.3 comes close to resolving the finegrained complexity of this basic task. Moreover, it matches known algorithmic guarantees for the easier case of Random Classification Noise [DDK + 23a, KIT + 23].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 η + ϵ within the corresponding region. Their approach leverages the LeakyReLU loss (see (1)) as a convex proxy to the 0-1 loss. At a high-level, their approach reweights the samples in order to accurately classify a non-trivial fraction of points. [CKMY20] uses the LeakyReLU loss to efficiently identify a 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 [DKTZ20b, DKK + 21]) to output a linear classifier with 0-1 error at most η + ϵ. Both of these approaches inherently require Ω(1/ϵ 3 ) 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 Θ(ϵ). Thus, even estimating the error of the loss would require at least Ω(1/ϵ 2 ) conditional samples. Beyond the dependence on 1/ϵ, the sample complexity achieved in these prior works is also suboptimal in the margin parameter γ; namely, Ω(1/γ 4 ). This dependence follows from the facts that both of these works require estimating the loss in each iteration within error of at most γϵ, and that their algorithmic approaches require Ω(1/γ 2 ) iterations.To circumvent these issues, novel ideas are required. At a 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 a similar sequence of loss functions was used in the recent work [DKTZ24] in a related, but significantly different, adversarial online setting. Interestingly, a similar reweighting scheme was 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 a detailed comparison.) Via this approach, we obtain an iterative algorithm which uses only O γ (1/ϵ 2 ) samples in order to estimate the loss in each iterative step.In more detail, note that the 0-1 loss can be written in the form -E[y w•x |w•x| ]. We convexify this objective by considering, in each step, the loss ℓ(w, u)= -E[y w•x |u•x| ],where u is independent of w; this loss is convex with respect to w. Observe that ℓ(w, w) is proportional to the zero-one loss of w. Unfortunately, it is possible that no optimal vector w * (under 0-1 loss) minimizes ℓ(w * , w). For this reason, we consider the objectiveℓ η (w, u) = E[(1{y ̸ = sign(w • x)} -η -ϵ)|w • x|/|u • x|]. This new objective satisfies the following: ℓ η (w * , u) < -ϵγ for any vector u and any w * that minimizes the 0-1 objective; and ℓ η (w, w) ≥ ϵ as long as w incurs 0-1 error at least η + ϵ. By the convexity of ℓ η (w, u), this allows us to construct a separation oracle. Namely, we draw enough samples so that ℓ η (w, w) -ℓ η (w * , w) ≥ ϵ/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 O(log(1/ϵ)/γ 2 ) iterations. Overall, this approach leads to an efficient algorithm with sample complexity Õγ (1/ϵ 2 ). To get the desired sample complexity of Õ(1/(ϵ 2 γ 2 )), more ideas are needed.In the previous paragraph, we hid an obstacle that makes the above approach fail. Specifically, it may be possible that, for many points x, the value of |u • x| is arbitrarily small. To fix this issue, we consider a clipped reweighting as follows:ℓ ′ η (w, u) = E[(1{y ̸ = sign(w • x)} -η -ϵ) |w•x| max(|u•x|,γ)]. This clipping step is not a problem for us, because the target halfspace sign(w * • x) was assumed to have margin γ. 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 |u • x| ≤ γ. Indeed, when this is the case, then |w * • x|/|u • x| ≥ 1. Overall, this suffices to guarantee that ℓ ′ η (w, w) -ℓ ′ η (w * , w) ≥ ϵ.For x 2 i ) 1/2 denotes the ℓ 2 -norm of x. We will use x • y for the inner product of x, y ∈ R d . For a subset S ⊆ R d , we define the proj S operator that maps a point x ∈ R d to the closest point in the set S. For a, b ∈ R, we denote W (a, b) def = 1/ max(a, b). We will use 1 A to denote the characteristic function of the set A, i.e., 1{x ∈ A} = 1 if x ∈ A, and 1{x ∈ A} = 0 if x / ∈ A. For A, B ∈ R, we write A ≳ B (resp. A ≲ B) to denote that there exists a universal constant C > 0, such that A ≥ CB (resp. A ≤ CB).We use E x∼D [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 D x for the marginal distribution of x and D y (x) for the distribution of y conditioned on x. We use D N to denote the empirical distribution obtained by drawing N i.i.d. samples from D. We use err D (w) to denote the 0-1 error of the halfspace defined by the weight vector w with respect to the distribution D, i.e., err D (w) , x) = η(x)1{sign(w • x) = sign(w * • x)} + (1 -η(x))1{sign(w • x) ̸ = sign(w * • x)} .2 Our Algorithm and its Analysis: Proof of Theorem 1.3In this section, we prove our main result. Algorithm 1 efficiently learns the class of margin halfspaces on the unit ball, in the presence of Massart noise, with sample complexity nearly matching the information-computation 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, a sequence of convex losses) -serving as a 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 λ (t) = (1 -λ)1{t ≥ 0}t + λ1{t < 0}t, where λ ∈ (0, 1) is the leakage parameter (that needs to be selected carefully). Roughly speaking, the convex function ℓ λ (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 (see, e.g., Claim C.1)EQUATIONObserve that a point x that is classified correctly by the halfspace sign(w • x) will satisfyE y∼Dy(x) [1{sign(w • x) ̸ = y}] -λ |w • x| = (η(x) -λ)|w • x|which is non-positive for λ ≥ η(x). Since the only guarantee we have is that η(x) ≤ η, this suggests that we need to select λ ≥ η. It turns out that λ := η is the optimal choice. We fix the choice of λ := η throughout. On the other hand, if (the halfspace defined by) w misclassifies the point x, this term becomes non-negative.The factor |w•x| in Equation (1) reweights the 0-1 error so that points x for which |w•x| is sufficiently large (i.e., close to 1) have to be classified correctly by a minimizer of E (x,y)∼D [ℓ λ (w, x, y)]. On the other hand, points closer to the separating hyperplane defined by w, or points where η(x) is close to λ = η, 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 so that, to minimize the regret, we need to classify a large fraction of points; this leads to the desired error of η + ϵ 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 functionEQUATIONwith respect to w, we would obtain a 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 issue, instead of reweighting by1/|w • x|, we will reweight by W (v • x, γ) def = 1/ max(|v • x|, γ), where γ is the margin parameter and v is an appropriately chosen vector that is independent of w. The new loss is defined as follows:EQUATIONwhere for technical reasons we use γ/2 instead of γ in the maximum.Since the parameter v is independent of w, the loss L λ,v (w) remains convex in w. At the same time, by carefully choosing v, we can accurately simulate the non-convex 0-1 loss. Note that our reweighting term is a maximum over two terms. The reason for this choice is that, for some points x, the quantity |v • x| can be arbitrarily small; taking the maximum avoids the loss becoming very large.In particular, the loss L λ,v (w) will be guaranteed to remain in a bounded length interval.Our algorithm proceeds in a sequence of iterations. In the (t + 1)-st iteration, it sets v to be w t , where w t is the weight vector of step t. This choice attempts to simulate the 0-1 error at w t , as is suggested by Equation (2). Assume for simplicity that our current hypothesis is the halfspace defined by w and is such thatE x∼Dx [1{|w • x| ≤ γ/2}] = 0. Note this implies that W (w • x, γ/2) = 1/|w • x|.By combining Equations ( 2) and (3), we get that L λ,w (w) = err D (w) -λ; note that as long as err D (w) ≥ λ + ϵ, we have that L λ,w (w) ≥ ϵ. On the other hand, the optimal halfspace w * achieves a non-positive loss; from Equations ( 1) and (2), we have thatL λ,w (w * ) = E (x,y)∼D [(1{sign(w * • x) ̸ = y} -λ)|w * • x|W (w • x, γ/2)] = E x∼Dx [(η(x) -λ)|w * • x|W (w • x, γ/2)] ≤ 0 ,where the inequality follows from the fact that η(x) ≤ η. Recalling that L λ,v (w) is convex, if we run an Online Convex Optimization (OCO) algorithm, after T steps we are guaranteed to find a vector wsuch that L λ,w (w) -L λ,w (w * ) ≤ O(1/ √ T ). For T = O(1/ϵ 2 ), this gives that L λ,w (w) < ϵ/2; and therefore we would have err D (w) < λ + ϵ. We provide an approach using this idea and the cutting planes algorithm in Appendix B that achieves sample complexity O(1/(ϵ 2 γ 4 )).Our algorithm and its analysis work only with the gradient of L λ,v (w). The key novelty is the analysis of the sample complexity. The gradient of ℓ λ (w, x, y)W (v • x, γ) with respect to w has the following explicit form:g λ,γ (w, v, x, y) def = ((1 -2λ)sign(w • x) -y)W (v • x, γ)x = ((1 -2λ)sign(w • x) -y) max(|v • x|, γ) x .Furthermore, we denote byG D (w, v, η, γ) = E (x,y)∼D [g η,γ (w, v, x, y)].Before describing our algorithm and proving Theorem 2.1, we simplify our notation. We will omit the parameters η, γ from the function input (as they are fixed throughout). Therefore, we useG D t N (w, v) ≡ G D t N(w, v, η, γ) and g(w, v, x, y) ≡ g η,γ/2 (w, v, x, y).Our algorithm is described in pseudocode below.Algorithm 1 employs online SGD applied to a sequence of convex loss functions. We show that, after a certain number of iterations, the algorithm will find a weight vector achieving 0-1 error at most η + ϵ. Since the desired vector may not be the last iterate, in the end, our algorithm returns the halfspace that achieves the smallest empirical 0-1 error.We establish the following result, which implies Theorem 1.3. The rest of this section is devoted to the proof of Theorem 2.1.Our algorithm sets v = w t in each round, therefore for the rest of the section we proceed by setting v = w as arguments of g and G.Input: Sample access to a distribution D supported in S d-1 × {±1} corrupted with η-Massart noise with respect to a halfspace sign(w * • x) that satisfies the γ-margin condition; parameters ϵ, δ ∈ (0, 1), and N, T ∈ Z + .Output: Weight vector ŵ such that err D ( ŵ) ≤ η + ϵ with probability at least 1 -δ.1. Let c > 0 be a sufficiently small universal constant. 2. t ← 0, w 0 ← e 1 = (1, 0, . . . , 0), andT = (1/c) log(1/δ)/(ϵ 2 γ 2 ). 3. While t ≤ T do (a) Draw (x (t) , y (t) ) sample from D. (b) Set λ t ← cγ 2 ϵ.(c) Update w t as follows: ▷ Update and project in the unit ball v t+1 ← w t -λ t g(w t , w t , x (t) , y (t) ) w t+1 ← v t+1 max(∥v t+1 ∥ 2 , 1) (d) t ← t + 1.We decompose the stochastic gradient g(w, w, x, y) into two parts: g(w, w, x, y) = g 1 (w, x) + g 2 (w, x, y), whereg 1 (w, x) = (1 -2η)sign(w • x) -E y∼Dy(x) [y] W (w • x, γ/2)x and g 2 (w, x, y) = E y∼Dy(x) [y] -y W (w • x, γ/2)x .We also use G 1D N (w) and G 2 D N(w) for the same decomposition after taking the empirical expectation, i.e., G 1D N (w) = E x∼( Dx) N [g 1 (w, x)] and G 2 D N (w) = E (x,y)∼ D N [g 2 (w, x, y)].This serves to decompose the gradient into two parts: one containing the population expectation over the random variable y, and the other containing the error between the empirical estimation of y and the population version of y. The vector G 1 D N (w) contains the direction that will decrease the distance between w and w * , while G 2 D N (w) contains the estimation error. To see this, observe that if we take the population expectation of g 2 (w, x, y), we will have:E (x,y)∼D [g 2 (w, x, y)] = E x∼Dx (1 -2η(x))sign(w * • x) -E y∼Dy(x) [y] W (w • x, γ/2)x = 0 ,where we used thatE y∼Dy(x) [y] = (1 -2η(x))sign(w * • x).We start by bounding the contribution of G 1 D N (w) in the direction ww * . We show that if instead of the corrupted label y at the point x, we had access to E y∼Dy(x) [y] = (1 -2η(x))sign(w * • x), then the gradient has a large component in the direction of ww * . This effectively implies that G 1 D N (w) can be used as a separation oracle, separating all the halfspaces with 0-1 error more than η + ϵ from the ones with smaller error.Lemma 2.2 (Structural Lemma). Let N ∈ Z + and let D be a distribution on S d-1 × {±1} satisfying the η-Massart condition with respect to the optimal classifier f (x) = sign(w * • x). Let w ∈ R d be such that ∥w∥ 2 ≤ 1 and let {x (i) } N i=1 be a multiset of N i.i.d. samples from D x . Then, it holdsG 1 D N (w) • (w -w * ) ≥ 2(err D N (w) -η), where D N is the corresponding empirical distribution.Proof. We partition R d into two subsets R 1 , R 2 as follows: R 1 contains the points that lie sufficiently far away from the separating hyperplane w • x = 0, i.e., R1 def = {x ∈ R d : |w • x| ≥ γ/2}. R 2 contains the remaining points, i.e., R 2 def = {x ∈ R d : |w • x| < γ/2}.We first show that for any x ∈ R 1 , the vector g 1 (w, x) has a large component parallel to the direction ww * . The proof of the claim below can be found in Appendix C.Claim 2.3. For any x (i) ∈ R 1 , we have that g 1 (w,x (i) ) • (w -w * ) ≥ 2(err(w, x (i) ) -η) .It remains to show that the same holds for all the points in R 2 . The proof of the claim below can be found in Appendix C.Claim 2.4. For any x (i) ∈ R 2 , we have that g 1 (w,x (i) ) • (w -w * ) ≥ 2(err(w, x (i) ) -η) .Applying Claim 2.3 and Claim 2.4 for each sample in the set {x (i) } N i=1 , we get that1 N N i=1 g 1 (w, x (i) ) • (w -w * ) ≥ 2 N N i=1 (err(w, x (i) ) -η) .This completes the proof of Lemma 2.2.By Lemma 2.2, the gradient points towards the direction w tw * , in the t-th iteration. This means that, in fact, the gradient is a subgradient of the potential loss Φ(w) = ∥w -w * ∥ 2 2 . This allows us to show convergence, even though it is generally not possible in a sequence of loss functions in the stochastic setting. We are now ready to prove our main result.Proof of Theorem 2.1. Let T be the maximum number of iterations of Algorithm 1. Denote by Z t := {(x (t) , y (t) )} the i.i.d. sample drawn from D in the t-th iteration, t ∈ [T ]. Furthermore, let F 1 , . . . , F T be the filtration with respect to the σ-algebra generated by Z 1 , . . . , Z T . We denote by H t the event that err D (w t ) ≥ η + ϵ.Recall that Algorithm 1 uses the following update rule (see Step (3c)): w t+1 = proj {w∈R d :∥w∥2≤1} (w t -λ t g(w t , w t , x (t) , y (t) )) , with λ t = cγ 2 ϵ , for some sufficiently small absolute constant c > 0.We begin by bounding from above the distance between w t+1 and w * from the previous distance between w t and w * . We have thatEQUATIONwhere in the first inequality we used the projection inequality, i.e., ∥proj B (v) -proj B (u)∥ 2 ≤ ∥v -u∥ 2 for any set B. We will decouple the mean of the random variable g(w t , w t , x, y) and make it zero-mean.To simplify the notation, we denote by ξ t := g(w t , w t , x (t) , y (t) ) -G 1 D (w t ) • (w tw * ) and note that ξ t is a zero-mean random variable over the sample (x (t) , y (t) ). Adding and subtracting G 1 D (w t ) onto Inequality (4) a we get thatEQUATIONWe now outline the main steps of our analysis. Instead of accurately estimating the gradients in each round, we denote by V t the estimation error from which we bound above their sum. We first add and 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 t is a random variable that corresponds to the estimation error of the gradient. We will argue that with high probability the contribution of T t=1 V t is bounded; therefore, our algorithm will converge to an accurate solution. Lemma 2.2 shows that G 1 D t N (w t ) (and therefore the same holds for G 1 D (w t )) contains substantial contribution towards to the direction w tw * , 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 H t happens, i.e., err D (w t ) ≥ η + ϵ. If λ t ≤ γ 2 ϵ/8, then I ≤ -λ t (err D (w t ) -η).Proof of Claim 2.5.Recall that I = -2λ t G 1 D (w t ) • (w t -w * ) + λ 2 t ∥g(w t , w t , x (t) , y (t) )∥ 2 2 . By Lemma 2.2, we get that G 1 D N (w t ) • (w t -w * ) ≥ 2(err D N (w t ) -η); hence, by taking expectations over the samples, we also haveG 1 D (w t ) • (w t -w * ) ≥ 2(err D (w t ) -η). Furthermore, we have that ∥g(w t , w t , x (t) , y (t) )∥ 2 2 ≤ 8/γ 2 . Hence,I ≤ -2λ t (err D (w t ) -η) + 8(λ 2 t /γ 2 ) .The claim follows by noting that if λ t ≤ γ 2 ϵ/8, then -λ t (err D (w t )-η)+8(λ 2 t /γ 2 ) ≤ 0. Therefore, we obtainI ≤ -λ t (err D (w t ) -η) .This completes the proof of Claim 2.5.Therefore, our choice of parameters guarantees that λ t ≤ γ 2 ϵ/8. Using Claim 2.5 onto Inequality (5), we have thatEQUATIONUsing Claim 2.5 and Inequality (6), we have thatEQUATIONTo complete the proof of Theorem 2.1, we need to bound the estimation error that corresponds to the random variable V t . We show that V t does not increase the error by a lot. Recall that V t = -2λ t ξ t .Before proceeding, we provide some basic background on subgaussian random variables.Definition 2.6 (Subgaussian Random Variable). For σ > 0, a zero-mean random variableX ∈ R is called σ-subgaussian, if for any λ ∈ R it holds log(E[exp(λX)]) ≤ λ 2 σ 2 .Note that any zero-mean bounded random variable is subgaussian. Specifically, we have the following:Fact 2.7 (Hoeffding's lemma, see, e.g., [Ver18] ). Let X ∈ R be a zero-mean random variable such that |X| ≤ σ for some σ > 0. Then X is Cσ-subgaussian, where C > 0 is a universal constant.Equipped with the above context, we show the following:Lemma 2.8. With probability at least 1 -δ over the random samples, it holds that T t=0 V t ≤ Cγ 2 ϵ 2 T + log(1/δ), where C > 0 is an absolute constant.Proof. We first show that ξ t is a subgaussian random variable.Claim 2.9. The random vector ξ t is (16/γ)-subgaussian.Proof of Claim 2.9. Note that ξ t = (g(w t , w t , x (t) , y (t) ) -E (x,y)∼D [g(w t , w t , x, y)]) • (w tw * ) and that by construction ∥g(w t , w t , x, y)∥ 2 ≤ 4/γ. Therefore, it holds that |g(w t , w t , x (t) , y (t) ) • (w tw * )| ≤ 8/γ, where we used that ∥w tw * ∥ 2 ≤ 2 as both of these vectors lie in the unit ball. Hence, by Fact 2.7, we have that ξ t is (16/γ)-subgaussian.Using Claim 2.9 and Definition 2.6 with parameter λ = -2λ t and X = ξ t , we have thatlog E[exp( V t )] = log E[exp(-2λ t ξ t )] ≤ C(λ 2 t /γ 2 ) ,where C > 0 is a universal constant. To bound the contribution of T t=0 V t , we use Markov's inequality with respect to the filtration F 1 , . . . , F T . We have that for any Z ∈ R, it holds thatPr Z 1 ,...,Z T ∼D T t=0 V t ≥ Z = Pr Z 1 ,...,Z T ∼D exp T t=0 V t ≥ exp(Z) ≤ E Z 1 ,...,Z T ∼D exp T t=0 V t exp(-Z) = T t=1 E Z t ∼D exp V t | F t exp(-Z) ≤ exp C T t=0 λ 2 t γ 2 -Z ,where in the second inequality we use the independence of V t with { V k } t-1 k=1 with respect to the filtration F t . Recalling that λ t = cγ 2 ϵ, where c > 0 is a sufficiently small universal constant, we have thatPr Z 1 ,...,Z T ∼D T t=0 V t ≥ Z ≤ exp Cc 2 γ 2 ϵ 2 T -Z ≤ exp Cc 2 γ 2 ϵ 2 T -Z .Setting Z = Cc 2 γ 2 ϵ 2 T + log(1/δ) and taking c to be a sufficiently small absolute constant (as is done in our algorithm), we get that Pr Z 1 ,...,Z T ∼D T t=0 V t ≥ Z ≤ δ. This completes the proof of Lemma 2.8.Assume that until the round T the event H T holds, i.e., for all i ∈ [T ] we have that err D (w i ) ≥ η + ϵ. Using Lemma 2.8 onto Inequality (7), with probability at least 1 -δ, we have that:∥w T +1 -w * ∥ 2 2 ≤ ∥w 0 -w * ∥ 2 2 - T t=0 λ t (err D (w t ) -η) + T t=0 V t ≤ ∥w 0 -w * ∥ 2 2 -cT ϵ 2 γ 2 + log(1/δ) .Running the algorithm for T = Θ(log(1/δ)/(ϵ 2 γ 2 )) iterations guarantees that with probability at least 1 -δ, we will have that ∥w T +1 -w * ∥ 2 2 ≤ 0, which means w T +1 = w * . In that case, i.e., in the case where all the events H i for i ∈ [T ] hold, w T +1 achieves the same error as the optimal halfspace, thus it has 0-1 error of at most η + ϵ. Therefore, at least one vector w t ′ with t ′ ∈ [T + 1] achieves 0-1 error of at most η + ϵ. The algorithm, in Step (5), returns a vector w that has 0-1 error at most err D ( w) ≤ min t∈[T +1] err D (w t ) + ϵ ≤ η + 2ϵ. The algorithm requires N = O(log(T /δ)/(ϵ(1 -2η))) samples for Step (5), due to [MN06] . The algorithm draws a sample in each round and runs for at most T rounds. Therefore, Algorithm 1 draws n = N + T = O(log(1/δ)/(ϵ 2 γ 2 )) samples. The algorithm needs to test each of the T hypotheses with N samples to find the closest one. Therefore, the total runtime is O(dT N ) (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. 
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 is 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 poly(d)/ϵ 2 , 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, DTK23] to effectively reduce to the large margin case.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The work is theoretical.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: In this section, we show how to use the cutting-planes method along with Lemma 2.2 to efficiently learning margin Massart Halfspaces using O(1/(γ 4 ϵ 2 )) samples. Specifically, we establish the following result: Theorem B.1 (Learning Margin Massart Halfspaces with Cutting Planes). Let D be a distribution on S d-1 × {±1} which satisfies the η-Massart noise condition with respect to the γ-margin halfspace f (x) = sign(w * •x). Given N = Θ(log(1/(γδ)/(γ 4 ϵ 2 )) i.i.d. samples from D, there is a poly(d, N ) time algorithm that returns a vector ŵ such that err D ( ŵ) ≤ η + ϵ with probability at least 1 -δ.Remark B.2. We can always assume that d = O(1/γ 2 ). This holds since we can efficiently preprocess the data, using the Johnson-Lindenstrauss transform [JL84] . Similar dimension-reduction 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 S d-1 × {±1} which satisfies the η-Massart noise condition with respect to the γ-margin halfspace f (x) = sign(w * • x). Given N = Θ(d log(1/(γδ)/(γ 2 ϵ 2 )) i.i.d. samples from D, there is a poly(d, N ) time algorithm that returns a vector ŵ such that err D ( ŵ) ≤ η + ϵ with probability at least 1 -δ.The idea of using the cutting plane method is slightly adapted from [CKMY20] . Given access to a separation oracle for a convex set K, we can find a point inside the set 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 to use O(1/ϵ 2 ) samples, instead of O(1/ϵ 3 ) samples, and leads to the optimal sample complexity as a function of ϵ (but not γ).Fact B.4. Suppose that K is an (unknown) convex body in R d which contains a Euclidean ball of radius r > 0 and contained in a Euclidean ball centered at the origin of radius R > 0. There exists an algorithm which, given access to a separation oracle for K, finds a point x * ∈ K, runs in time poly(log(R/r), d), and makes O(d log(Rd/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, we have: Proposition B.5 (Separation Oracle). Let ϵ, δ ∈ (0, 1) and let D be a distribution on S d-1 × {±1} satisfying the η-Massart noise condition with respect to the halfspace f (x) = sign(w * • x). Fix w ∈ R d with ∥w∥ 2 ≤ 1. Let N ≳ log(1/(γδ))/(ϵ 2 γ 2 )) and D N be the corresponding empirical distribution. Then, with probability at least 1 -δ, it holds thatG D N (w, w) • (w -w * ) ≥ 2(err D (w) -η) -ϵ . Proof. By construction, G D N (w, w) = G 1 D N (w) + G 2 D N (w) and by Lemma 2.2 we have that G 1 D N (w) • (w -w * ) ≥ 2(err D N (w) -η).By definition, we haveE (x (1) ,y (1) ),...,(x (N ) ,y (N ) )∼D [G 2 D N (w)] = 0, where the expectation is taken with respect to the sample set. Note that the norm of g 1 (w, x), g 2 (w, x, y), i.e., ∥g 1 (w, x)∥ 2 , ∥g 2 (w, x, y)∥ 2 , is bounded pointwise from above by 4/γ for all w ∈ R d . This can be seen as ∥x∥ 2 ≤ 1, W (•, γ/2) ≤ 2/γ, and (1 -2η), (1 -2η(x)) ≤ 1.We use the following concentration inequality to show that our sample size is enough to guarantee that the estimated gradient is close to its population version.Fact B.6 ([SZ07], Lemma 1). Let Z 1 , . . . , Z n ∈ R d be random vectors such that for each i ∈ [n] it holds ∥Z i ∥ 2 ≤ M < ∞ almost surely and let σ 2 = n i=1 E[∥Z i ∥ 2 2 ]. Then, we have that for any ϵ > 0,Pr 1 n n i=1 (Z i -E[Z i ]) 2 ≥ ϵ ≤ 2 exp - nϵ 2M log 1 + nM ϵ σ 2 .Using Fact B.6, along with the inequality log(1 + z) ≥ z/2, for z ∈ (0, 1), we get that if N ≥ Θ( log(1/δ) (ϵγ) 2 ), with probability at least 1 -δ, we haveEQUATIONandEQUATIONTo complete the proof, recall that by Lemma 2.2 it holds G 1D N (w)•(w-w * ) ≥ 2(err D N (w)-η)-ϵ.Therefore, by taking the expectation over D x , we get thatG 1 D (w) • (w -w * ) ≥ 2(err D (w) -η) . The proof is completed by recalling that ∥G 1 D N (w) -E (x,y)∼D [g 1 (w, x)]∥ 2 ≤ ϵ from Inequality (8)and that E (x,y)∼D [g 2 (w, x, y)] = 0.Equipped with Proposition B.5, we are ready to prove a weaker version of Theorem 2.1 using separation oracles and the cutting plane algorithm. Formally, we show that Proof of Theorem B.3. Our convex set K is a Euclidean ball of radius γ/2 centered at w * . To see that, note that for any v such that ∥w * -v∥ 2 ≤ γ/2, we have that|(w * -v) • x| ≤ γ/2 for any x with ∥x∥ 2 = 1. This implies that γ/2 + w * • x ≥ v • x ≥ w * • x -γ/2. Moreover, by definition we have that w * • x ≥ γ. Hence, if w * • x ≥ 0, we have that v • x ≥ γ/2; and if w * • x ≤ 0, we have that v • x ≤ -γ/2.Therefore, this ball contains all the vectors w with margin γ/2 and separates the points in the same way as w * . Therefore, as long as we are not in the set K or the 0-1 error is more than η + ϵ, we can use ). For any w, x, we have thatℓ λ (w, x, y) = 1{y(w • x) ≤ 0} -λ |w • x| . Proof. Recall that ℓ λ (w, x, y) = LeakyReLU λ (-y(w•x)) = (1-λ)1{y(w•x) ≤ 0}(-yw•x)+λ1{y(w•x) > 0}(-yw•x) .Therefore, we have thatℓ λ (w, x, y) = (1 -λ)1{y(w • x) ≤ 0}|yw • x| -λ1{y(w • x) > 0}|yw • x| = 1{y(w • x) ≤ 0}|w • x| -λ|w • x| = 1{y(w • x) ≤ 0} -λ |w • x| ,where we used that y ∈ {±1}.We restate and prove the following claim: Claim 2.3. For any x (i) ∈ R 1 , we have that g 1 (w,x (i) ) • (w -w * ) ≥ 2(err(w, x (i) ) -η) .Proof of Claim 2.3. For any x (i) ∈ R 1 , we have thatEQUATIONwhere we used that for anyx (i) ∈ R 1 , W (w • x (i) ) = 1/|w • x (i) |, and hence W (w • x (i) , γ/2)w • x (i) = sign(w • x (i) ); and that err(w,x (i) ) = η(x (i) ) if sign(w • x (i) ) = sign(w * • x (i)) and 1 -η(x (i) ) otherwise.We now bound the contribution of w * . Since η(x) ≤ η, we have(1 -2η(x)) -(1 -2η)sign(w • x)sign(w * • x)≥0 .Therefore, we have thatg 1 (w, x (i) ) • w * = (1 -2η)sign(w • x) -(1 -2η(x))sign(w * • x) sign(w * • x)|w * • x|W (w • x (i) ) = -(1 -2η(x)) -(1 -2η)sign(w • x)sign(w * • x) |w * • x|W (w • x (i) ) ≤ 0 ,which gives that -g 1 (w, x (i) ) • w * ≥ 0. This completes the proof of Claim 2.3.We restate and prove the following:Claim 2.4. For any x (i) ∈ R 2 , we have that g 1 (w,x (i) ) • (w -w * ) ≥ 2(err(w, x (i) ) -η) .Proof of Claim 2.4. We have thatg 1 (w, x (i) ) • (w -w * ) = (1 -2η)sign(w • x (i) ) -(1 -2η(x (i) ))sign(w * • x (i) ) w • x (i) -w * • x (i) max(γ/2, |w • x (i) |) = (1 -2η)sign(w • x (i) ) -(1 -2η(x (i) ))sign(w * • x (i) ) w • x (i) -w * • x (i) γ/2 ,where we used that max(γ/2, |w •x (i) |) = γ/2 for any x (i) ∈ R 2 . Since sign(w * • x) has γ- margin, we have that |w * • x (i) | ≥ γ. Since x (i) ∈ R 2 , it holds |w • x (i) | < γ/2. Therefore, -sign(w * • x (i) )(w • x (i) -w * • x (i) ) = |w * • x (i) | -sign(w * • x (i) )w • x (i) ≥ γ/2. This in turn implies that g 1 (w, x (i) ) • (w -w * ) ≥ (1 -2η(x (i) ) -(1 -2η)sign(w • x (i) )sign(w * • x (i) )) = 2(err(w, x (i) ) -η) ,completing the proof of Claim 2.4. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.As is standard, we are assuming that d = Ω(1/γ); otherwise, a sample complexity bound of O(d/ϵ) follows from standard VC-dimension arguments.We will henceforth assume that the threshold is θ = 0, which is well-known to be no loss of generality.The RCN model is the special case of Massart noise, where η(x) = η for all points x in the domain. 


Decision: 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.

Reviews: review: paper_summary: paper_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))$.

They 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.
strength_weakness: strength_weakness: I did not find any significant weaknesses, only minor comments regarding the presentation.

- **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.
questions: 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: limitations: N/A
paper_summary: paper_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].
The 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.
strength_weakness: strength_weakness: Result is specific to a particular noise model and it is not clear if the techniques are more broadly applicable.
questions: questions: In Algorithm 1, $\\lambda_t$ seems to be a constant independent of $t$, so it can be fixed outside the loop.
limitations: limitations: Yes
paper_summary: paper_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).

This 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. 

The 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.
strength_weakness: strength_weakness: I do not see any major weaknesses.
questions: questions: None.
limitations: limitations: This is a theoretical work with no societal impact.
paper_summary: paper_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.

The 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.

The paper is generally well written.
strength_weakness: strength_weakness: I haven't found significant weaknesses in the paper.

Typos:
- Page 2, line 34: “We say that that the distribution” ->  “We say that the distribution” 
- Page 5: Line 195: If I am not mistaken, the function g is twice the gradient.
questions: 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.

- 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: limitations: Since this is a theoretical paper, I can't see any potential negative societal impact.
paper_summary: paper_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.
strength_weakness: strength_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...").
2. The natural agnostic extension of the problem is not discussed.
questions: questions: Questions:
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.
2. Is there a specific reason not to discuss the agnostic case? Is it usualy considered in Massart noise problems?


Suggestions:

Consider writing what is $\eta$ in the abstract.
limitations: limitations: Yes.

Comments: comment: Thank you  for the rebuttal and the clarification. I will keep my rating.
I would like to thank the authors for their response. Since they addressed my minor comments, I'm increasing my score to 7.
Thank you for your response!
Thank you for addressing my comments and questions.