Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random

Authors: gautam  chandrasekaran
u t austin
kevin  tian
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 17:34:28

Abstract: We study the problem of PAC learning $\gamma$-margin halfspaces with Massart noise. We propose a simple  proper learning algorithm, the Perspectron, that has sample complexity $\widetilde{O}((\epsilon\gamma)^{-2})$ and achieves classification error at most $\eta+\epsilon$ where $\eta$ is the Massart noise rate. 
 Prior works (DGT19, CKMY20)  came with worse sample complexity
 guarantees (in both $\epsilon$ and $\gamma$) or could only
 handle random classification noise (DDKWZ23,KITBMV23)--- a much milder noise assumption. 
We also show that our results extend to the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving a similar sample complexity to the halfspace case. This significantly improves upon the prior state-of-the-art in this setting due to CKMY20, who introduced this model.

Main paper: 
 introduction: 
 We study the problem of learning halfspaces with a margin, one of the oldest problems in the field of machine learning dating to work of Rosenblatt [Ros58] . Specifically, we consider the following formulation of this problem, where the label distribution is corrupted by Massart noise [MN06] , where we use the following notation for halfspace hypotheses h w : R d → {±1}: h w (x) := sign (w • x) , for w ∈ R d .(1)Definition 1 (Massart halfspace model). Let η ∈ [0, 1 2 ] and γ ∈ (0, 1). We say that a distribution D on B d × {±1} is an instance of the η-Massart halfspace model with margin γ if the following hold.• There exists w ⋆ ∈ R d such that ∥w ⋆ ∥ = 1, 4 and D x has margin γ with respect to w ⋆ , 5 i.e.,Pr x∼Dx [|w * • x| < γ] = 0.• For all x ∈ supp(D x ), there is an η(x) ∈ [0, η] such that Pr [y ̸ = h w ⋆ (x) | x] = η(x).We note that Definition 1 extends straightforwardly to general halfspaces up to rescaling (i.e., with larger domain size bounds and constant shift terms), as discussed in Remark 2.The Massart noise model of Definition 1 for halfspaces (and more generally, binary classification problems) has garnered interest from the statistics, machine learning, and algorithms communities for a variety of reasons. This noise model was originally introduced as an intermediate noise model, between the simpler (from an algorithmic design standpoint) random classification noise (RCN) model [AL88] , and the more challenging agnostic model [Hau92b, KSS94] . In the RCN model, η(x) in Definition 1 is restricted to be η pointwise, i.e., the noise level is uniform; polynomial-time PAC learning has long since known to be tractable under RCN [Byl94, BFKV98] . On the other hand, in the agnostic model (where learning is computationally intractable under well-studied conjectures [GR06, FGKP06, Dan16] ), an adversary is allowed to arbitrarily modify an η fraction of labels. As observed by [Slo88] , the Massart noise model of Definition 1 is equivalent to allowing an oblivious adversary control an η fraction of labels, where the η fraction is crucially sampled independently at random. It was stated as a longstanding open question [Coh97, Blu03] whether this obliviousness of the adversary impacts the polynomial-time tractability of learning halfspaces, even with a margin.For additional motivation, it is reasonable to consider Massart noise to be a more realistic model of real-life noise (even when benign) when compared to the RCN model, as it allows for some amount of non-uniformity. This made Definition 1 a possibly tractable way to relax the noise assumption, without running into the aforementioned computational barriers for agnostic learning.In a series of recent exciting developments, in large part spurred by the breakthrough work of [DGT19b] who gave an (improper) polynomial-time PAC learning algorithm in the Massart halfspace model, significant algorithmic advances have been made towards understanding the polynomialtime tractability of learning under Massart noise [ABHU15, DGT19b, DKTZ20a, CKMY20, ZL21, DKK + 22]. However, less is understood about the fine-grained sample and computational complexity of these problems, which is potentially of greater interest from a practical perspective.We investigate this question of fine-grained complexity for the Massart halfspace model, inspired by a line of recent work on semi-random models [BS95] , a popular framework for understanding the overfitting of algorithms to their modeling assumptions. To motivate semi-random models, observe that from a purely information-theoretic standpoint, one might suspect that learning under Massart noise is actually easier than RCN; the noise level η(x) is only allowed to decrease, giving more "signal" with respect to w ⋆ . However, this modification poses challenges when designing algorithms, e.g., because it breaks independence between y and x beyond the value sign(w ⋆ • x). Indeed, this is reflected in our current knowledge of halfspace learning algorithms. While it is known that one can learn halfspaces with margin γ under the RCN model to ϵ error (in the zero-one loss) using O((ϵγ) -2 ) samples [DDK + 23, KIT + 23], state-of-the-art learners under Massart noise use O(γ -4 ϵ -3 ) samples (if required to be proper) [CKMY20] or O(min(γ -4 ϵ -3 , γ -3 ϵ -5 )) samples (otherwise) [DGT19b] .The semi-random model framework posits that this discrepancy reflects a lack of robustness in the current algorithmic theory for learning halfspaces, due to their overfitting to the RCN assumption.For many statistical learning problems, new algorithms have been developed under semi-random modeling assumptions, with guarantees matching, or nearly-matching, classical algorithms under the corresponding fully random models [CG18, KLL + 23, JLM + 23, GC23, BGL + 24]. This leads us to our motivating problem, which aims to accomplish this goal for learning halfspaces.Is it possible to design algorithms for learning in the Massart halfspace model with sample complexities matching the state-of-the-art for learning in the RCN model?(2)As our main contribution, we resolve (2) in the affirmative in the setting of Definition 1. We also extend our results a substantial generalization of this model in Definition 2.Massart halfspace model. We begin with our basic result in the setting of the Massart halfspace model, Definition 1. Our goal in this setting is to find a proper hypothesis halfspace h w (x) = sign(w • x) for w ∈ B d , achieving good zero-one loss ℓ 0-1 (see Section 2 for a definition) over examples (x, y) drawn from the distribution D. Our main result to this end is the following.Theorem 1 (Informal, see Theorem 3). Let D be an instance of the η-Massart halfspace model with margin γ, and let ϵ ∈ (0, 1). Then, Perspectron (Algorithm 1) returns w ∈ B d such that ℓ 0-1 (w) ≤ η + ϵ with probability 0.99,6 using O(γ -2 ϵ -2 ) samples and O(dγ -2 ϵ -4 ) time.We pause to comment on Theorem 1. First, our error guarantee is of the form η + ϵ rather than the more stringent goal of ℓ 0-1 (w⋆ ) + ϵ = E x∼Dx [η(x)] + ϵ.There is strong evidence that this distinction is necessary for polynomial-time algorithms in the statistical query (SQ) framework of [Kea98] , which our algorithm is an instance of, due to [CKMY20, DK20, NT22]. Next, the sample complexity bound of Theorem 1 matches the results of [DDK + 23, KIT + 23], the state-of-the-art under the milder RCN model. There is evidence that the dependences in Theorem 1 on both ϵ -1 and γ -1 are individually tight. In particular, [MN06] shows the sample complexity of the problem is Ω(γ -2 ϵ -1 ), and [DDK + 23] shows any efficient algorithm in the SQ framework must use Ω(γ -1/2 ϵ -2 ) samples.We also remark that we can assume without loss of generality that η is known (see Appendix B.1).Finally, as mentioned, prior to our work, the best-known polynomial-time learners under Definition 1 had sample complexities O(min(γ -4 ϵ -3 , γ -3 ϵ -5 )) [CKMY20, DGT19b] . In Table 1 , we summarize relevant sample complexity bounds for learning variants of halfspace models with noise. 1 : Sample complexities of learning halfspaces with γ margin, omitting logarithmic factors and failure probabilities for brevity. All the algorithms above run in polynomial time.Source RCN Massart Proper Sample Complexity [DGT19b] ✓ ✗ ✓ γ -4 ϵ -2 [DDK + 23, KIT + 23] ✓ ✗ ✓ γ -2 ϵ -2 [DGT19b] ✓ ✓ ✗ γ -3 ϵ -5 [CKMY20] ✓ ✓ ✓ γ -4 ϵ -3 Theorem 1 ✓ ✓ ✓ γ -2 ϵ -2 TableMassart generalized linear models. Our second result is an extension of Theorem 1 to the more challenging setting of learning generalized linear models (GLMs) with a known link function σ under Massart noise. As before, we only consider distributions that have a margin with respect to the optimal halfspace. We now formally define the setting we study.Definition 2 (Massart GLM). Let σ : [-1, 1] → [-1, 1] be an odd, non-decreasing function. We say that a distribution D on B d × {±1} is an instance of the σ-Massart generalized linear model (GLM) with margin γ if the following conditions hold.⋆ ∈ R d such that ∥w ⋆ ∥ = 1 and Pr[|w * • x| < γ] = 0. 2. For all x ∈ supp(D x ), it holds that η(x) := Pr[y ̸ = h w ⋆ (x) | x] ≤ 1-|σ(w ⋆ •x)| 2 .Remark 1. We remark that the assumption that σ is odd is also commonly used in prior works (see, e.g., [CN08, DKTZ20a, CKMY20] ). We further show that our result extends to σ with bounded asymmetry, albeit with a weaker error guarantee (see Definition 3 and Theorem 4).To provide intuition for Definition 2, observe that that if η(x) = 1-|σ(w ⋆ •x)| 2 for some x ∈ supp(D x ), then E [y | x] = |σ(w ⋆ • x)|sign(w ⋆ • x) = σ(w ⋆ • x), i.e., Definition 2 corresponds to the standard GLM definition. In Definition 2 (compared to Definition 1), we replace the fixed noise rate upper bound η with a data-dependent upper bound which is monotone (i.e., decreases as |w ⋆ • x| grows more confident). That is, Definition 2 generalizes the problem of learning Massart halfspaces, which follows by taking σ(t) = (1 -2η)sign(t) for all t ∈ [-1, 1].When working with a Massart GLM D, we define opt RCN := E (x,y)∼D [ 1-|σ(w ⋆ •x)| 2 spaces, known SQ lower bounds make competing with opt := ℓ 0-1 (w ⋆ ) := Pr (x,y)∼D [y ̸ = h w ⋆ (x)] an intractable target, so our focus is again on attaining ℓ 0-1 (w) ≈ opt RCN .To our knowledge, the model in Definition 2 was first studied in [CKMY20] , though we note that similar models have been considered in prior works [ZLC17, HKLM20, DKTZ20a], which we describe and compare to Definition 2 in Section 1.3. In [CKMY20] , the parameterization of this model is slightly different; they assume σ is L-Lipschitz and that Pr x∼Dx [|σ(w * • x)| ≥ γ] = 1, i.e., they impose a margin on σ(w * • x) rather than w * • x. This implies our margin assumption (with γ ← γ L in Definition 2), but not vice versa. Under their slightly more restrictive assumptions, [CKMY20] claims a runtime which is an unspecified polynomial in Lγ -1 ϵ -1 , that is at least Ω(L 4 γ -4 ϵ -6 ) when specialized to the halfspace case (see their Theorems 5.2 and 6.14). On the other hand, we achieve improved rates extending our simple algorithmic approach for the Massart halfspace case in this more challenging setting.Theorem 2 (Informal, see Theorem 4). Let D be an instance of the σ-Massart GLM with margin γ, and let ϵ ∈ (0, 1). There is an algorithm returning w ∈ B d so that ℓ 0-1 (w) ≤ opt RCN + ϵ with probability 0.99, using O(γ -2 ϵ -4 ) samples and O(dγ -2 ϵ -6 ) time.In particular, parameterizing our problem using the margin and Lipschitz assumptions in [CKMY20] (with γ ← γ L ), we obtain an improved sample complexity of O(L 2 γ -2 ϵ -4 ).Learning Massart halfspaces. Our learning algorithms are inspired by the certificate framework for learning with semi-random noise developed in [DKTZ20d, CKMY20] . In that framework, given a sub-optimal hypothesis w, i.e., with error Pr (x,y)∼D [sign(w • x) ̸ = y] ≥ η + ϵ, the goal is to construct a certificate of sub-optimality in the form of a separating hyperplane between w and the target w * , i.e., a vector g such that g• w ≥ g • w ⋆ ⇐⇒ g • (w -w ⋆ ) ≥ 0.Given such a separating hyperplane, prior works rely on cutting-plane methods (e.g., [Vai96] ) or on first-order regret minimization methods to learn a hypothesis achieving the target error.We first describe our algorithm in the halfspace setting, by motivating our choice of a certificate. Prior work [CKMY20] achieving a proper Massart halfspace learner uses the gradient of the Leaky-ReLU objective ℓ η (t) := (1 -η) max(0, t) -η max(0, -t) conditioned on a band around the current hypothesis w as a separating hyperplane. That is, they argue that for some appropriate interval I, it holds that E[∇ℓ η (-yw• x) | x • w ∈ I] • (w -w * ) ≥ 0.This yields a sample complexity scaling as Õ(ϵ -3 ) because one has to sample condionally from the band I and estimate the gradient of the Leaky-ReLU on these samples up to error ϵ, as well as additional overhead in γ -1 due to use of expensive outer loops taking advantage of these certificates, such as cutting-plane methods.To avoid the sample complexity overhead of this conditioning (implemented via rejection sampling), we use a simple reweighting scheme pointwise, which puts a larger weight of |w • x| -1 (an inverse margin) on points closer to the boundary of our current hypothesis h w . Intuitively, this reweighting is a soft implementation of the hard conditioning done in [CKMY20] . This is motivated by our first important observation: any significantly sub-optimal hypothesis w with ℓ 0-1 (w) ≥ η + ϵ satisfiesE ∇ℓ η (-yw • x) |w • x| • (w -w ⋆ ) ≥ ϵ,proven in Lemma 1. This suggests using g= E[∇ℓ η (-yw • x)|w • x| -1 ] (rather than E[∇ℓ η (-yw • x) | x • w ∈ I] as in [CKMY20]) as our certificate, which we can estimate via a single sample.While reweighting by the inverse margin |w • x| -1 gives a separating hyperplane certificate, it may be impossible to estimate this certificate from few samples, e.g., if the weight |w•x| -1 is often very large, which introduces significant variance. For instance, even if D x has margin with respect to a target w ⋆ , this is not necessarily true with respect to the current hypothesis w (without further distributional assumptions on D x ). To overcome this, we change our pointwise reweighting to be less aggressive and instead use (|w •x|+γ) -1 . In Lemma 2, we exploit the margin assumption about D x to show that whenℓ 0-1 (w) ≥ η+ϵ, it is still the case that E[∇ℓ η (-yw•x)(|w•x|+γ) -1 ]•(w-w * ) ≥ ϵ.Moreover, we still have an unbiased estimator for this separating hyperplaneE[∇ℓ η (-yw • x)(|w • x| + γ) -1 ],and the estimator is bounded in Euclidean norm by γ -1 with probability 1 by our margin assumption.Standard concentration inequalities now show O(γ -2 ϵ -2 ) samples suffice to obtain a separation oracle with high probability. Plugging this certificate into oracle-efficient cutting-plane methods (e.g., [Vai96] ) implies an algorithm with sample complexity O(γ -4 ϵ -2 ) (after a random projection process [AV99] to reduce to O(γ -2 ) dimensions). This already improves upon the prior best-known O(γ -4 ϵ -3 ) sample complexity. We further improve our dependence on γ by using it in a perceptronlike regret minimization scheme, where at every step we update the current hypothesis w using the aforementioned bounded unbiased estimator of our certificate, see Lemma 3 and Algorithm 1. Overall, our algorithm iterates the following very simple update for a step-size λ > 0 and β := 1 -2η:EQUATIONSince at every step we perform an (approximate) perspective projection (|w ). Using a similar iterative method as the Perspectron defined in (3), we obtain our sample complexity of O(γ -2 ϵ -4 ) for learning Massart GLMs.• x| + γ) -1 onWe briefly survey some additional related works here. First, a common worst-case assumption used in statistical learning is that the label noise is adversarial (a.k.a. agnostic) [Hau92a] . In that setting, a lot of progress has been made for learning halfspaces when the underlying distribution satisfies structural assumptions (e.g., it is Gaussian or log-concave) [KKMS05, KOS08, ABHU15, DKS18, DKTZ20c, DKTZ22]. For learning halfspaces with a margin, the best-known agnostic results have runtime and sample complexity that depend exponentially on the margin γ and/or the accuracy parameter ϵ [SSS09, LS11, DKM19]. Another important line of work [DKTZ20d, DKK + 20, ZL21] has focused on learning halfspaces under Tsybakov noise: a semi-random noise model that extends Massart noise, but is still easier than the agnostic setting. We also note that variants of Definition 2 have appeared before: the generalized Tsybakov low noise condition of [HKLM20] is a close relative which imposes different noise rates within and outside a margin, and the strong Massart noise of [ZLC17, DKTZ20a] is an instance of Definition 2 without the margin restriction.Our algorithms rely on the certificate framework developed in [DKTZ20b, CKMY20] and the Leaky-ReLU loss that has been extensively used in prior works on learning with random classification and Massart label noise [Byl98, DGT19a, CKMY20, DKT21]. Our main technical contribution is a new certificate that relies on an inverse-margin reweighting scheme and can be estimated using a single sample at every iteration. Similar, "inverse-margin" reweighting schemes have been used for learning general halfspaces [CKMY20] and online linear classification [DKTZ24] . Those results have no implications for the sample complexity of the problem studied here. Finally, we mention that a local reweighting scheme that is somewhat similar in spirit to ours (but very different in its implementation) was previously employed by [KLL + 23], for a different semi-random statistical learning problem.One interesting open direction is providing improved sample complexity guarantees for more general noise models. For example, the misspecified GLM framework (Definition 3.2, [CKMY20] ) generalizes Definition 2 to include an additional misspecification parameter ζ such that η(x) ≤1-|σ(w * •x)| 2 + ζ.Our approach does not directly apply in this setting, since ζ = 0 is important for our separation oracle result of Lemma 6. A different interesting generalization of the noise model corresponds to the case where the link function σ is unknown, which the [CKMY20] algorithm can handle (at a much higher sample complexity). While our algorithms require knowledge of σ, it would be interesting to explore whether techniques from learning single-index models (e.g., [KS09, GGKS23, ZWDD24] ) can be used to extend our algorithms in this setting.A clear next step is to design efficient algorithms with sample complexities independent of the margin but still linear in the dimension d.7 , e.g., with an ≈ dϵ -2 sample complexity. In prior work [DKT21] such an algorithm is given, albeit with a significantly worse poly(dϵ -1 ) sample complexity. 
preliminaries: 
 We denote vectors in lower-case boldface, and ∥x∥ is the Euclidean norm of x ∈ R d . We use B d to denote the unit ball in R d , i.e.B d := {x ∈ R d | ∥x∥ ≤ 1}. We use Π B d (w) := min{1, 1∥w∥ }w to denote the Euclidean projection of a vector w ∈ R d onto B d . We let 0 d be the all-zeroes vector in dimension d. We reserve the overline notation x to denote the unit vector in the direction of x, i.e.x := x ∥x∥ . We let sign : R → {±1} be defined so sign(t) = 1 iff t ≥ 0. We use 1{E} to denote the 0-1 indicator of a random event E, Pr[E] to denote its probability, and E to denote the expectation operator. The support of a distribution D is denoted supp(D), and[N ] := {i ∈ N | i ≤ N }.Throughout the paper we study the problem of learning a binary classifier, given labeled examples from a distribution D over labeled examples (x, y) ∈ R d × {0, 1}, under various models on the distribution to be discussed. We refer to the x-marginal of D by D x , and the conditional distribution of the label y | x by D y (x). We will primarily be interested in learning halfspace hypotheses, which for w ∈ R d are the corresponding functions h w : R d → {±1} defined by h w (x) := sign (w • x). We also denote the zero-one loss of a halfspace hypothesis h w corresponding to w ∈ R d as follows, when the distribution D over labeled examples is clear from context:ℓ 0-1 (w) := Pr (x,y)∼D [h w (x) ̸ = y].We define the Leaky-ReLU function with parameter λ > 0 as ℓ λ (t) := (1 -λ) max(0, t)λ max(0, -t). Given vectors w, x and y ∈ {±1}, it holds that the (sub) gradient of ℓ λ (-yw• x) with respect to w is ∇ w ℓ λ (-yw • x) = 1 2 ((1 -2λ)sign(w • x) -y) • x.We also provide some brief remarks on how to extend Definition 1 to more general settings here.Remark 2. Definition 1 extends straightforwardly to the case where D x has margin γ and is supported on a subset of R • B d for R ̸ = 1, by rescaling so R ← 1 and γ ← γ R , as halfspace hypotheses and our label noise assumptions only depend on signs. Other than these margin and support assumptions, we make no additional distributional assumptions about the x-marginal D x . Further, due to working in the distributional assumption-free setting, we can assume with up to constant factor loss(in margin) that the halfspace is homogeneous, i.e., has no constant shift term. That is, given a halfspace sign(w • x + b) with ∥w∥ , |b| ≤ 1, after a feature expansion (e : x → 1 √ 2 (x, 1)) the halfspace h w ′ (z) = sign((w, b) • z) is homogeneous while still having a margin ≥ γ 2 with respect to w ′ = 1 √ 1+b 2 (w, b). Finally, the Massart noise model of [MN06] is defined for any hypothesis class and is not tied to halfspaces. Since we focus on learning halfspaces with a margin, we combined the hypothesis class {h w } w∈R d with the noise model in Definition 1 for simplicity.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We thoroughly discuss the assumptions under which our results hold, as well as their scope and comparison with related work, in an explicit limitations and future work section.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. 
massart halfspaces: 
 In this section, we give our result on learning Massart halfspaces with margin. Our proof is surprisingly short, and we separate it into its two main components: a structural lemma in Section 3.1 which shows how to estimate a separating hyperplane given a sub-optimal w, and a perceptron-like analysis of a stochastic iterative method in Section 3.2.We prove our main structural lemma here, used to argue the progress of our iterative method. As highlighted in Section 1.2, we show that when the current ℓ 0-1 (w) ≥ η + ϵ, we can construct an unbiased estimator for a separating hyperplane between w and the target vector w ⋆ .Warmup: an "unbounded" separating hyperplane. Before presenting the full proof, we first give a separating hyperplane that works for any feature distribution -even without margin assumptions. The proposed separating hyperplane works due to the fact that we can express the zero-one in terms of the Leaky-ReLU which is a convex function, as was previously observed by [DGT19b] .Lemma 1 (Separating hyperplane for Massart halfspaces). Let D be an instance of the η-Massart halfspace model, and w ∈ R d has classification error ℓ 0-1 (w) ≥ η + ϵ. It holds thatE (x,y)∼D ∇wℓη(-yw•x) |w•x| • (w -w * ) ≥ ϵ .Proof. We recall Claim 2.1 from [DGT19b] : for all w, x, it holds thatE y∼Dy(x) [ℓ λ (-yw • x)] = (Pr y∼Dy(x) [sign(w • x) ̸ = y]-λ)•|w•x|.In particular, we have E (x,y)∼Dℓη(-yw•x) |w•x| = ℓ 0-1 (w)- η. From the convexity of ℓ η (-yw • x), we obtain that ∇ w ℓ η (-yw • x) • (w -w * ) ≥ ℓ η (-yw • x) - ℓ η (-yw * • x). By dividing both sides by |w • x| and taking expectation over x and y, we obtainE x,y ∇ w (ℓ η (-yw • x) |w • x| • (w -w * ) ≥ E x,y ℓ η (-yw • x) |w • x| -E x,y ℓ η (-yw * • x) |w • x| ≥ ϵ ,where the last inequality follows from the following facts: (1) for all x, it holds thatE y∼Dy(x) [ℓ η (-yw * • x)] = (Pr y∼Dy(x) [sign(w * • x) ̸ = y]-η)•|w * •x| = (η(x)-η)•|w * •x| ≤ 0, and (2) E x,y ℓη(-yw•x) |w•x| = ℓ 0-1 (w) -η ≥ ϵ.This completes the proof.A "bounded" separating hyperplane for γ-margin Massart halfspaces. Our claim in the previous lemma was very general: it works for any marginal distribution. However, as discussed in Section 1.2, the unbounded nature of this separating hyperplane may make it impossible to estimate from samples.To overcome this, we propose a new candidate hyperplane:E x,y ∇wℓη(-yw•x) |w•x|+γ. We prove that this candidate is indeed a separating hyperplane by leveraging the fact that we have margin γ with respect to the optimal halfspace w * . Recall from Section 2 that ∇ w ℓ η (-yw•x) = 1 2 ((1-2η)sign(w•x)-y).Lemma 2 (Bounded separating hyperplane for Massart halfspaces). Let D be an instance of the η-Massart halfspace model with margin γ (with respect to w ⋆ ) and defineβ = 1 -2η. If w ∈ R d has ℓ 0-1 (w) ≥ η + ϵ, it holds that E (x,y)∼D (βsign(w • x) -y) x |w • x| + γ • (w -w * ) ≥ 2ϵ .Proof. We first observe that by the definition of the Massart halfspace model,E y∼Dy(x) [y] = (1 -2η(x))sign(w * • x) = β(x)sign(w ⋆ • x), where β(x) := 1 -2η(x). Therefore, we have thatI := E (x,y)∼D (βsign(w • x) -y) (w • x -w * • x) |w • x| + γ = E x∼Dx (βsign(w • x) -β(x)sign(w * • x)) (w • x -w * • x) |w • x| + γ .We denote by g(x) := (βsign(w• x) -β(x)sign(w * • x)) (w•x-w * •x) |w•x|+γ, which we bound differently based on whether x falls in the agreement regionA := x ∈ B d | h w ⋆ (x) = h w (x) . For x ∈ A, g(x) = βsign(w • x) -β(x)sign(w * • x) (w • x -w * • x) |w • x| + γ = β -β(x) |w • x| -|w * • x| |w • x| + γ ≥ β -β(x) .The second equality follows from the fact that sign(w * EQUATIONWe will now use our lower bound on ℓ 0-1 (w), which we relate to Equation (4). We haveℓ 0-1 (w) = E x∼Dx [1 {x ∈ A} η(x)] + E x∼Dx [1 {x ̸ ∈ A} (1 -η(x))] = E x∼Dx [1 {x ̸ ∈ A} β(x)] + E x∼Dx [η(x)].Next, by our definition β(x) = 1 -2η(x), rearranging and expanding we have:EQUATIONWe finish the proof by combining Equation (4), Equation (5), and ℓ 0-1 (w) -η ≥ ϵ.We now present and analyze Perspectron, our algorithm for learning Massart halfspaces.Algorithm 1: Perspectron1 Input: {x i , y i } i∈[T1+T2] ⊂ R d × {±1} drawn i.i.d. from D in the η-Massart halfspace model with margin γ, step size λ > 0, failure probability δ ∈ (0, 1 2 ) 2 β ← 1 -2η, N ← ⌈log 2 ( 2 δ )⌉, T ← ⌈ T1 N ⌉ 3 H ← ∅ 4 for j ∈ [N ] do 5 w 1,j ← 0 d 6 for t ∈ [min(T, T 1 -(j -1)T )] do 7 i ← (j -1)T + t 8 w t+1,j ← w t,j -λ βsign(w t,j •x i )-y i |w t,j •x i |+γ x i 9 end 10H ← H ∪ {w t,j } t∈[min(T,T1-(j-1)T )] 11 end 12 S ← {x i , y i } T1+T2 i=T1+1 13 w ← arg min w∈H Pr (x,y)∼unif.S [h w (x) ̸ = y] 14 Return: h w We begin by giving a self-contained analysis of a single loop j ∈ [N ] of Line 6 to Line 9, showing that for sufficiently large T , at least one iterate achieves small ℓ 0-1 with constant probability.Lemma 3. Let {x i , y i } i∈[T ] ∼ i.i.d. D, where D is an instance of the η-Massart halfspace model with margin γ with respect to w ⋆ . Consider iterating, from w 1 := 0 d ,EQUATIONfor β := 1 -2η, λ := γ 2 √ T . Then if T ≥ 16 ϵ 2 γ 2 , Pr[min t∈[T ] ℓ 0-1 (w t ) ≥ η + ϵ 2 ] ≤ 1 2 .Proof. Throughout the proof, say w ∈ R d is bad iff ℓ 0-1 (w) ≥ η + ϵ 2 , and let E t denote the event that all of the iterates {w s } s∈[t] updated according to (6) are bad. Define the potential functionΦ t := E[1 {E t } • ∥w ⋆ -w t ∥2 ] for all t ∈ [T ]. On expanding the expression for the squared norm and using the fact that 1 {E t+1 } ≤ 1 {E t },Φ t+1 ≤ E 1 {E t } • w ⋆ -w t+1 2 ≤ Φ t + λ 2 E βsign(w t • x t ) -y t |w t • x t | + γ x t 2 -2λ E 1 {E t } • βsign(w t • x t ) -y t |w t • x t | + γ x t • (w t -w ⋆ ) ≤ Φ t + 4λ 2 γ 2 -2λ Pr [E t ] E βsign(w t • x t ) -y t |w t • x t | + γ x t • (w t -w ⋆ ) | E t ≤ Φ t + 4λ 2 γ 2 -2λϵ Pr [E t ] .Here, the third inequality used x t ∈ B d and |βsign(w t • x t ) -y t | ≤ 2, and the fourth applied Lemma 2. Now using thatΦ 1 ≤ ∥w ⋆ ∥ 2 = 1, Φ T +1 ≥ 0, and Pr[E t ] ≥ Pr[E T ] for t ∈ [T ], we have 2λϵT Pr [E T ] ≤ 1 + 4λ 2 T γ 2 .The conclusion Pr [E T ] ≤ 1 2 follows from our choices of λ, T .We next analyze the hypothesis selection step in Line 13.Lemma 4 (Hypothesis selection). Suppose there exists ŵ ∈ H with ℓ 0-1 (w)≤ η + ϵ 2 . Then if T 2 ≥ 8 ϵ 2 log( 2|H| δ ), with probability ≥ 1 -δ the w returned by Line 13 satisfies ℓ 0-1 (w) ≤ η + ϵ.Proof. Because S is independent of H, Hoeffding's inequality and a union bound implies that Pr (x,y)∼unif.S [h w (x) ̸ = y] -ℓ 0-1 (w) ≤ ϵ 4 with probability ≥ 1 -δ, for all w ∈ H. Conditioning on this event, ℓ 0-1 (w) > η + ϵ yields a contradiction:ℓ 0-1 (w) - ϵ 4 ≤ Pr (x,y)∼unif.S [h w (x) ̸ = y] ≤ Pr (x,y)∼unif.S [h ŵ(x) ̸ = y] ≤ ℓ 0-1 ( ŵ) + ϵ 4 ≤ η + 3ϵ 4 .We are now ready to state and prove our main theorem.Theorem 3 (Learning γ-margin Massart halfspaces). Let D be an instance of the η-Massart halfspace model with margin γ, and let ϵ, δ ∈ (0, 1). Algorithm 1 withT 1 ≥ 16 ϵ 2 γ 2 ⌈log 2 ( 2 δ )⌉, T 2 ≥ 8 ϵ 2 log( 4|T1| δ) returns w such that ℓ 0-1 (w) ≤ η + ϵ with probability ≥ 1 -δ, using O((ϵγ) -2 log(δ -1 ) + ϵ -2 log((ϵγδ) -1 )) samples and O(dϵ -4 γ -2 log(δ -1 ) log((ϵγδ) -1 ) time.Proof. First, applying Lemma 3 to each of the N independent runs of Line 6 to Line 9 shows that the premise of Lemma 4 is met except with probability δ 2 . The correctness claim then follows from Lemma 4. The sample complexity is immediate, and the runtime bound follows because the bottleneck operation is computing the value of h w (x) for all (x, y) ∈ S and w ∈ H.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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: [Yes] Justification: Our work is of theoretical nature, focusing on improving the reliability of a basic learning algorithm. We do not foresee any direct path to any negative applications. 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). 
massart generalized linear models: 
 In this section, we present a key piece of intuition motivating our extension to the Massart GLM noise model (see Definition 2), deferring a full proof to Appendix A. In this setting, instead of being upper bounded by a fixed constant η, the noise rate is data-dependent and upper bounded by 1-σ(w ⋆ •x)2where σ is odd non-decreasing and w ⋆ is the optimal halfspace. Inspired by our approach in Section 3, we propose a novel separating hyperplane based on the previously described reweighting scheme. We argue in this section that E x,y(σ(w•x)-y) |w•x|x is a valid separating hyperplane, generalizing Lemma 1.Lemma 5 (Separating hyperplane for Massart GLMs). Let D be an instance of the σ-Massart GLM model with margin γ (with respect to halfspace w ⋆ ), and w ∈ R d has ℓ 0-1 (w) ≥ opt RCN + ϵ. We have that E (x,y)∼D(σ(w•x)-y) |w•x| x • (w -w * ) ≥ 2ϵ .Proof Sketch. We use the definition of sets A, β(x) from Lemma 2. By expanding out the expression for ℓ 0-1 (w) similarly to Lemma 2, we obtain that 1 2• E (x,y)∼D [(|σ(w * • x)| -β(x))1{x ∈ A}] + 1 2 • E (x,y)∼D [(|σ(w * • x)| + β(x))1{x / ∈ A}] ≥ ϵ. Let g(x) = (σ(w•x)-y) |w•x|• (w -w * ). Now, we argue that E x∼Dx [g(x)] is greater than the left hand side of the previous inequality. We do a case analysis. For x ∈ A, we observe that g(x)≥ (|σ(w * • x)| -β(x)) |w•x|-|w * •x| |w•x| ≥ (|σ(w * • x)| -β(x)).Here, we obtained the first inequality by adding and subtracting the corresponding term with σ(w * • x) and then using monotonicity. The final inequality follows from the fact that β(x) ≥ |σ(w * • x)|. For x / ∈ A, we obtain that g(x) = (|σ(w However, we are met with the same obstacle as before: |w • x| can be arbitrarily small. The previous approach of adding γ to the denominator does not work immediately. Instead, we add the rescaled term ϵ 2-ϵ • γ. Adding a smaller term in the denominator increases the bound on the norm of the increments in each step, resulting to a larger bound on the number of iterations (and, therefore, sample complexity) by a factor of ϵ -2 . However, this rescaling is useful to obtain an analogue of Lemma 2 for the case of Massart GLMs (Lemma 6). The rescaling essentially accounts for the part of the distribution where |w • x| is smaller than |w * • x| and the signs disagree. This is important because the size of |w • x| is quantitatively more significant in the Massart GLM case.• x)| + β(x)) |w•x|+|w * •x| |w•x| ≥ (|σ(w * • x)| + β(x))Combining this with a modified version of the Perspectron algorithm and analysis (see Algorithm 2), we obtain our final result with sample complexity O(γ -2 ϵ -4 ) (see Theorem 4).In this section, we prove our result regarding learning in the Massart generalized linear model with a margin. Our analysis is similar to that of Section 3 but requires a modified version of Lemma 2, which gives a "bounded" separating hyperplane in the case of Massart GLM (Lemma 6). We first state the definition of our model again (slightly generalized to relax the assumption that σ is odd).Definition 3 (Massart GLM). Let σ : [-1, 1] → [-1, 1] be a non-decreasing function. We say that a distribution D on B d × {±1} is an instance of the σ-Massart generalized linear model (GLM) with constant shift τ and margin γ with respect to w ⋆ if the following conditions hold.• |σ(t)| -|σ(-t)| ≤ τ for all t ∈ [0, 1]. • There exists w ⋆ ∈ R d such that ∥w ⋆ ∥ = 1 and Pr[|w ⋆ • x| < γ] = 0. • For all x ∈ supp(D x ), there is an η(x) ∈ [0, 1-|σ(w ⋆ •x)| 2 ] such that Pr y∼Dy(x) [y ̸ = h w ⋆ (x)] = η(x).We state and prove the following lemma which provides a separating hyperplane in this setting.Lemma 6 (Separating Hyperplane). Let D be a distribution on R d ×{±1} such satisfying Definition 3. Let w ∈ R d be such that Pr (x,y)∼D [sign(w• x) ̸ = y] ≥ E x∼Dx 1-|σ(w * •x)|+τ 2 + ϵ. Then, we have E (x,y)∼D (σ(w.x) -y) x |w • x| + αγ • (w -w * ) ≥ ϵ , for α = ϵ/(2 -ϵ). Proof. Let A = {x ∈ R d | sign(w • x) = sign(w * • x)} and B = {x ∈ R d | sign(w • x ̸ = sign(w * • x)}.We have thatI = E (x,y)∼D (σ(w • x) -y) x |w • x| + αγ • (w -w * ) = E x∼Dx (σ(w • x) -β(x)sign(w * • x)) • (w • x -w * • x) |w • x| + αγ Define g(x) = (σ(w • x) -β(x)sign(w * • x)) • (w•x-w * •x) |w•x|+αγ .We analyze g(x) separately for x ∈ A and x ∈ B .First consider points x in A. For any x ∈ A, we have thatg(x) = σ(w • x) -σ(w * • x) + σ(w * • x) -β(x)sign(w * • x) • (w • x -w * • x) |w • x| + αγ ≥ |σ(w * • x)|sign(w * • x) -β(x)sign(w * • x) • (w • x -w * • x) |w • x| + αγ ≥ |σ(w * • x)| -β(x) • |w • x| -|w * • x| |w • x| + αγ ≥ |σ(w * • x)| -β(x) .The second inequality follows from the fact that (σ(w We now consider the case where x ∈ B. Since sign(w• x) -σ(w * • x)) • (w • x -w * • x) ≥ 0 since σ is• x) ̸ = sign(w * • x), we have that g(x) = |σ(w • x)| + β(x) • |w•x|+|w * •x| |w•x|+αγ . We split B into two finer regions. Define B 1 = {x ∈ B | |w • x| ≥ |w * • x|} and B 2 = {x ∈ B | |w • x| < |w * • x|}. First, consider x ∈ B 1 . We have that |σ(w • x)| ≥ max(0, |σ(-w • x)| -τ ). We also have that |σ(-w • x|) ≥ |σ(w * • x)| since |w • x| ≥ |w * • x| and σ is monotone non-decreasing. Also, observe that |w•x|+|w * •x| |w•x|+αγ ≥ 1 since |w * • x| ≥ γ. Thus, we obtain that g(x) ≥ max(0, |σ(w * • x)| -τ ) + β(x). Finally, we consider x ∈ B 2 . Let c(x) = |w * •x| |w•x| . We have that g(x) ≥ β(x) |w * • x| + |w • x| |w • x| + αγ ≥ β(x) 1 + |w * •x| |w•x| 1 + α γ |w * •x| |w * •x| |w•x| ≥ β(x) 1 + c(x) 1 + αc(x) ≥ (2 -ϵ)β(x) .The third inequality follows from the fact that |w * • x| ≥ γ and the last inequality is true because1+c 1+αc ≥ 2 -ϵ for any c ≥ 1 when α = ϵ 2-ϵ . Since 1 ≥ β(x) ≥ |σ(w * • x)|, we have that g(x) ≥ β(x) + |σ(w * • x)| -ϵ.Thus, we obtain thatEQUATIONWe now use our assumption on the error of w. We have thatϵ ≤ Pr (x,y)∼D [sign(w • x) ̸ = y] -E x∼Dx 1 -|σ(w * • x)| 2 = E (x,y)∼D 1{x ∈ A} 1 -β(x) 2 + E (x,y)∼D 1{x ∈ B} 1 + β(x) 2 -E x∼Dx 1 -|σ(w * • x)| 2 = 1 2 • E (x,y)∼D |σ(w * • x)| -β(x) 1{x ∈ A} + 1 2 • E (x,y)∼D max(0, |σ(w * • x)| -τ )β(x) 1{x ∈ B}Plugging into Equation (7), we obtain that I ≥ 2ϵ -ϵ ≥ ϵ. This completes the proof.We can now prove our main theorem about Massart GLMs. The algorithm we use, Algorithm 2, is a modified version of the Perspectron algorithm (Algorithm 1), where we subsitute the value of the parameter γ with γ • ϵ 2-ϵ and the updates involve the function σ. Theorem 4. Let D be an instance of the σ-Massart GLM with constant shift τ and margin γ with respect to w ⋆ , and let ϵ, δ ∈ (0, 1). Algorithm 2 with ,T 1 ≥ 32 ϵ 4 γ 2 ⌈log 2 ( 2 δ )⌉, T 2 ≥ 8 ϵ 2 log( 4|T1| δ ) returns w such that ℓ 0-1 (w) ≤ E x∼Dx 1-|σ(w * •x|+τ 2 + ϵ with probability ≥ 1 -δ, using O log( 1 δ ) ϵ 4 γ 2 + log( 1 ϵγδ ) ϵ 2 samples and O d log( 1 δ ) log( 1 ϵδ ) ϵ 6 γ 2 time.Algorithm 2: GLMPerspectron1 Input: {x i , y i } i∈[T1+T2] ⊂ R d × {±1} drawn i.i.d. from D in the σ-Massart GLM model with margin γ, parameter α ∈ (0, 1), step size λ > 0, failure probability δ ∈ (0, 1 2 ) 2 β ← 1 -2η, N ← ⌈log 2 ( 2 δ )⌉, T ← ⌈ T1 N ⌉ 3 H ← ∅ 4 for j ∈ [N ] do 5 w 1,j ← 0 d 6 for t ∈ [min(T, T 1 -(j -1)T )] do 7 i ← (j -1)T + t 8 w t+1,j ← w t,j -λ σ(w t,j •x i )-y i |w t,j •x i |+γ•α x i 9 end 10 H ← H ∪ {w t,j } t∈[min(T,T1-(j-1)T )] 11 end 12 S ← {x i , y i } T1+T2 i=T1+113 w ← arg min w∈H Pr (x,y)∼unif.S [h w (x) ̸ = y] 14 Return: h w Proof. Given Lemma 6, the first step of the proof is exactly analogous to the proof of Lemma 3, i.e., we can show the following claim.Claim 1. Let {x i , y i } i∈[T ] ∼ i.i.d. D, where D satisfies Definition 3. Consider iterating, from w 1 := 0 d ,EQUATIONfor λ := γϵ (2-ϵ) √ 2T . Then if T ≥ 32 ϵ 4 γ 2 , Pr[min t∈[T ] ℓ 0-1 (w t ) ≥ E x∼Dx 1-|σ(w * •x|+τ 2 + ϵ 2 ] ≤ 1 2 .The proof is analogous to the proof of Lemma 3, but we use γϵ/(2 -ϵ) in the place of γ. To amplify the success probability and finish the proof, we once more use Lemma 4.In this section, we can obtain the same sample complexity (upto logarithmic factors) as Theorem 3 even when the noise rate η is unknown to the learner. The argument is the following: we argue that our separating hyperplane (Lemma 2) is tolerant to O(ϵ) noise in the parameter η. We can then discretize the interval [0, 1/2] into intervals of size ϵ and run the training algorithm multiple times for these different choices. Then, we can output the hypothesis with lowest validation error among the classifiers output by these different runs of the algorithm. We now argue that this idea indeed works.Lemma 7. If D is an instance of the η-Massart halfspace model with margin γ with respect to w ⋆ , andEQUATION• x) -y) x |w • x| + γ • (w -w * ) ≥ 2ϵ, for β ∈ ((1 -2η) -ϵ, (1 -2η)] .Proof. The proof is almost identical to the proof of Lemma 2 except for a few steps. We highlight the differences. We reuse the notation from the previous proof.First consider x / ∈ A, we observe that using the same argument as before, we now obtaing(x) ≥ β + β(x) ≥ β + β(x) -ϵ.In the case of x ∈ A, since β(x) ≥ β ≥ β, we obtaing(x) ≥ ( β -β(x)) ≥ β -β(x) -ϵ.Using this, we can can complete the proof by repeating the steps of the previous proof.Having proved this, our algorithm is simple, run over the (1/(2ϵ)) choices of β in [0, 1/2] and run the algorithm from Theorem 3 for each choice, reusing the same samples in the different run's of the algorithm. The correctness follows Lemma 7 and the proof of Theorem 3 since one of the the choices of parameters must lie in the interval((1 -2η) -ϵ, (1 -2η)].NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: We provide proofs and/or references for all claims made in the abstract and introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 paper does not release data or models.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: The paper does not use existing 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.The formal variant, Theorem 3, gives high-probability bounds at a mild polylogarithmic overhead in sample and runtime complexities.By standard random-projection procedures[AV99], the dimension d is comparable to γ -2 under a γ-margin assumption, and therefore our sample complexity is nearly-linear in the "dimension." 
 
 Appendix:  


Decision: This paper improves the state of the art sample complexity for learning halfspaces with massart noise, where the noise in each example is upper bounded by \eta. They match the \eta + \epsilon learning guarantee established in previous works [DGT19,CKMY20] with an improved sample complexity, and also give some extensions of their result to the more challenging GLM + massart noise setting studied by prior work. All of the reviewers agreed this advances the start of the art in this area with a simple and clean approach.

Reviews: review: paper_summary: paper_summary: The paper considers the problem of learning halfspaces with a margin, under the Massart noise model. The Massart noise model generalizes the Random Classification Noise (RCN) Model: while in the RCN model, each label is flipped with fixed probability \eta, in the Massart noise model the the probability of flipping the label can be a function of the covariates bounded above by \eta.  The paper asks the question of whether one can design learning algorithms under the Massart noise model, matching the sample complexity under the RCN model, and answers it positively. Specifically, the paper proposes a proper learning algorithm, with sample complexity 1/(\epsilon^2 \gamma^2), matching the state of the art under the RCN model  (\epsilon is the error of the algorithm, \gamma is the margin). The results are also extended to the case of generalized linear models.
strength_weakness: strength_weakness: The set of people interested in the fine-grained complexity of learning under Massart Noise might not be very broad. So the significance of the results seems moderate.
questions: questions: NA
limitations: limitations: Yes
paper_summary: paper_summary: This paper focused on the fine-grained analysis of learning $\gamma$-margin halfspace with massart noise. The authors designed a new certificate vector $g$ by dividing the gradient vector of leaky ReLU by $|w^\top x| + \gamma$, and showed that when the hyperplane $h_w(x)$ has large 0-1 loss $\ell_{0,1}(w)\geq \eta + \epsilon$, the certificate vector aligns well with the direction of $w - w^*$, i.e., $g^\top(w. - w^*)\geq \epsilon$, hence a perceptron-like algorithm enjoys fast convergence to the optimal hyperplane $h_{w^*}(x)$. In the end, the authors showed that the proposed Perspectron algorithm requires only $O((\gamma\epsilon)^{-2})$ samples, matching with the sample complexity of learning margin halfspaces with RCN. The authors also extended the technique to massart GLM problem and achieved a similar $O((\gamma\epsilon)^{-2})$ sample complexity.
strength_weakness: strength_weakness: No serious weakness of this paper, but there are several typos here and there. 
For example line 263 should be $w^*$, there should be an $x$ in the end of line 270, etc.
questions: questions: I am not very familiar with massart GLMs. If I understand correctly, it seems the goal of massart GLM is still trying to find a classification hyperplane, but under this massart GLM model, the massart noise $\eta(x)$ is bounded by a function of $w^*\cdot x$. If so, isn't massart GLM a sub-class of massart model, as we have further constraints on $\eta(x)$ (in addition to simply restricting $\eta(x)\leq \eta$), hence perhaps implying that massart GLM is simpler than massart model?
limitations: limitations: The authors have addressed the limitations adequately.
paper_summary: paper_summary: This submission studies the problem of learning halfspaces and generalized linear model in the Massart model under a margin assumption. In particular, for the case of halfspaces, the submission gives an efficient algorithm achieving (conjecturally optimal) error $\eta + \varepsilon$ using only $\tilde{O}(\gamma^{-2} \varepsilon^{-2})$ samples, where $\gamma$ is the margin parameter, and $\eta$ the upper bound on the noise rate. This matches what is known in the more benign RCN model. All previously known efficient algorithms in the Massart model require a number of samples that is polynomially worse in $\varepsilon$ and $\gamma$.
strength_weakness: strength_weakness: The presentation of the submission is generally solid but can be improved in several aspects. Below are comments aiming at this. Especially the comments related to the technical overview are important in order to understand why the submission is able to improve over previous work. I'm willing to increase my score to 6 or 7 if the authors agree to address the comments below and in particular, explain in their rebuttal how they would address the comments for the technical overview.


## Technical Overview

I like the structure of the technical overview and that it tries to highlight differences with previous works (this also shows expertise of the authors). Unfortunately however, in several places the writing is unclear (see below). I find it nice that the proof for the halfspace result is so short that it fits in the main body. Nevertheless, I would find a more extensive technical overview with commentary much more illustrative then including the full proof (the many formulas make this hard to read and understand what is going on).

Here are some specific comments about the technical overview:

- lines 129-136: It is not clear from the discussion why this approach incurs a too high sample complexity on a quantitative level.
- lines 153-162: It is not at all clear from the discussion why the proposed update rule improves the dependence on $\gamma$
- lines 172-174: You say that this approach also works for the case of massart halfsapces. Why did you not follow this approach? From the discussion it seems it would significantly simplify a part of the analysis. Is there anything else that breaks?


## Introduction

- lines 46-58: Before diving into the details of the fine-grained aspects and to set the stage, it would be helpful to briefly explicitly recall what is known in the general Massart model (without margin assumption) -- e.g., error $\eta$ is possible and this is likely optimal
- when you say "learn up to error $\varepsilon$" in the above paragraph, do you mean error $\eta + \varepsilon$?
- I believe the work [DKMR22] is not mentioned at all, this should be added
- Similarly, when talking about impossibility results in the agnostic model, the work [Tie23] (see also [DKMR22]) should be mentioned
- for some of the citations, the arxiv version is cited. Why not cite the conference version?


[DKMR22]: I. Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren, Cryptographic Hardness of Learning Halfspaces with Massart Noise

[Tie23]: S. Tiegel, Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems
questions: questions: See last part of above section.
limitations: limitations: yes
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))$. The individual dependence  of the sample complexity on $\epsilon$ and $\gamma$ appears to be optimal for efficient algorithms in the light of lower bounds provided in previous work.

The algorithm is a form of stochastic-gradient descent where the loss function is the LeakyReLu loss. The gradient is carefully weighted with an appropriate weight in order to yield the desired results.

The paper also provides an algorithm for a more general model, the generalized linear model (GLM), under Massart-noise.

The paper is generally very-well written.
strength_weakness: strength_weakness: I haven't found any significant weaknesses.

Typos:
- Page 3, line 97: “observe that that if” ->  “observe that if”
questions: questions: - In Lemma 3, the parameters $\lambda$ and $T$ were chosen so that $\mathbb{P}[\mathcal{E}_T]\leq 1/2$, which necessitated the outer loop $j\in[N]=[\log_2(2/\delta)]$ to get success probability at least $1-\delta$. Wouldn't it be possible to choose the constant factors in $\lambda$ and $T$ differently to directly get  $\mathbb{P}[\mathcal{E}_T]\leq \delta$?
limitations: limitations: Since this is a theoretical paper, I do not see any potential negative societal impact.
paper_summary: paper_summary: The paper studies learning half-spaces in the Massart noise setting. That is for $\gamma\eta >0$ and $\eta(x)\leq \eta $ for all $x\in supp(D_{x})$,  half space $w^*$ and such that $P( | w^* x  | \geq \gamma)$ and $P ( sign( w^* x ) \not= y)=\eta(x)$ for all $x\in supp(D_{x})$ - given such an instance and $\varepsilon>0$ the paper now states the problem of finding a half spaces $w$ such that $P[sign(wx)\not=y]\leq \eta+\varepsilon]$ using as few samples and computations as possible. The paper achieves a new bound on the number of samples needed to solve this problem of $\tilde{O}(\gamma\varepsilon)^{-2}$ (suppressing factors of  $\log(1/\delta)$). This is an improvement over previous results which uses $\gamma^{-3}\varepsilon^{-5}$, $\gamma^{-4}\varepsilon^{-3}$. They also show it in a more general setting for $\sigma$ odd and non decreasing where $P[sign(w*x)\not= y]=\frac{1-\sigma(wx)}{2}$ for all $x\in supp(D_{x})$. They obtain a sample complexity bound of $(\tilde{O})((\gamma\varepsilon)^{-2})$ here.
strength_weakness: strength_weakness: Weaknesses:
Not anything significant - related to the question below do the other papers also use $\eta$ in the error bound instead of $E[\eta(x)]\leq \eta$? If yes why not use $E[\eta(x)]$?
questions: questions: \section*{Questions}

Line 18-20: I really like how it was $Pr_{x\sim D_{x}}$ was used as it made the randomness explicit - I didn't at first get that the randomness in the $Pr$ (line 20) was over $y\sim D_{y}(x)$ I don't know if other readers would have the same experience.

Line 72 : what error does previous work in massart noise setting use? If other- why not use the same?
 

Line 102 $\eta(x)$?

Not consistent whether it is $Pr_{\cdot}$ or just $Pr$

Table: Good table. Is the running time not interesting?

The real numbers $R$ and natural numbers $N$ didn't look like I'm used to seeing them - I don't know if this is on purpose if it is don't mind changing it - I just wanted to let you know in case that something has complied weirdly.

Line 221: should it be $B^d\times \{-1,1\}$?

Line 229: why isn't it a vector? Can you give the derivation of this expression?

Line 238: $h_{w'}=sign((w..$ shouldnt it be $h_{w'}=sign((w'..$ 

Line 261: what does the $l_\eta(w*,x,h)$ mean? Happens more places in this proof.

Line 263: Please show fact (1), or should it be $l_\eta(-yw*x)$. If facts 1) and 2) follow from the fact stated at the beginning of the proof from [DGT19b] maybe consider moving these together.

Line 276: it says $w^{\star}$ instead of $w^*$

Line 298-299: The third line in the equation missing $x^t$

Line 289 algorithm line 7: this makes $w^t$ and $x^t$ independent right? Which is used in the proof of lemma 3  last inequality of the large equation combined with lemma 2?

Line 307: why say anything about contradiction - doesn't it just follow from the inequality afterward?

Line 313-316: I guess It doesn't matter that the last badge isn't necessarily of size $T$? Or is it necessarily of size $T$?

Line 329: what is $B$?

Would it be interesting to make the computational cost independent of d with the cost of polynomial factors in $1/\gamma\varepsilon$?
limitations: limitations: They address the limitations of the work.

Comments: title: Reply to reviewer x3Ci
comment: Thank you for the detailed response! I think the above discussion makes the technical contribution of the submission over previous work much clearer. I have increased my score accordingly. I also appreciate (and acknowledge) the authors official rebuttal regarding the error and fix in the Massart GLM case.
I thank the authors for their response and corrections. I would like to remain my evaluation.
I thank the authors for their response. After reading the response as well as other reviews, I am inclined to keep my original score.
Thank you for the clarification. I remain my score.
Thanks for answering my questions and clearing up my misunderstandings - good luck!
Yes, that was a mistake in our description -- Line 113 should say the sample complexity of [CKMY20] is $\Omega(L^4 \gamma^{-4} \epsilon^{-6})$, not its runtime. This is directly comparable to our updated sample complexity of $\widetilde{O}(L^2 \gamma^{-2} \epsilon^{-4})$. Both runtimes pay an overhead in the dimension $d$ compared to the sample complexity, since they perform vector operations. Thank you for this catch.
Arrh good -  to this end, so [CKMY20] achieves sample complexity and runtime of $\Omega(L^4\gamma^{-4}\varepsilon^{-6})$ - I think line 113 only says something about runtime?(sorry if im mistaking).
Table 1 in our paper is currently only about Massart Halfspaces. We are happy to add one more column with the sample complexity of Massart GLM. This column will have the sample complexity of $\gamma^{-2}\epsilon^{-4}$ in our row, as the reviewer notes.

### In regards to the bounds obtained by prior work:
1) [DGT19b] do not study this model.
2) [CKMY20] consider this model with an additional restriction on $\sigma$ being $L$-Lipschitz and $|\sigma(\mathbf{w}^*\cdot\mathbf{x})|\geq \gamma$ for all $\mathbf{x}$. In this regime, they obtain a sample complexity of at least $L^4\gamma^{-4}\epsilon^{-6}$. In this regime, our result translates to a bound of $L^2\gamma^{-2}\epsilon^{-4}$ which is a strict improvement. 

### Comparison between $\epsilon$ and $\gamma$: 

In general, these parameters are incomparable depending on situation (one is about a suboptimality guarantee, and one is a geometric assumption about the distribution). However, there are natural scenarios where one would prefer a worse $\epsilon$ dependence (as in our updated result) compared to a worse $\gamma$ dependence: 

1) $\gamma$ is a high-dimensional parameter, so it is natural to have it depend on the dimension $d$. In particular, for natural models (e.g. $D$ is TV-close to the uniform distribution over the unit sphere) we really do have margin about $1/\sqrt{d}$.
2)  $\epsilon$ measures error in the 0-1 output space, so it is natural to have it not depend on $d$ (i.e. treat it as a constant / free parameter).

Concretely, in the margin-free setting, state-of-the-art algorithms all apply pre-processing techniques [BFKV96,DV04,DKT21] that transform an underlying distribution to one with margin effectively equal to $\Omega(\text{poly}(1/d))$. In these cases, a worse dependence on $1/\epsilon$ may be preferred over a bad dependence on $1/\gamma$.

*[BFKV96] 	Avrim Blum, Alan M. Frieze, Ravi Kannan and Santosh S. Vempala. A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS 1996*

*[DV04] John Dunagan and Santosh Vempala. A simple polynomial-time rescaling algorithm for solving linear programs. STOC 2004*

*[DKT21] Ilias Diakonikolas, Daniel M. Kane and Christos Tzamos. Forster decomposition and learning halfspaces with noise. NeurIPS 2021*
Thanks for your response. My understanding of the change due to the technical issue in terms of Table 1: the Massart noise column is now two columns: Massart with sample complexity $(\gamma\varepsilon)^{-2}$ and Massart GLM with sample complexity $\gamma^{-2}\varepsilon^{-4}$ for your row. If this is correct please “fill in” the sample complexity that [DGT19b] and [CKMY20] get for Massart and Massart GLM (or other relevant references). To this end please remind me if $\varepsilon$ is always less than $\gamma$.