Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
Authors: Gautam Chandrasekaran
Vasilis Kontonis
Konstantinos Stavropoulos
Kevin Tian
Venue: NeurIPS 2024 spotlight (2024)
Keywords: pac learning
learning halfspaces
massart noise
sgd
robust learning
Primary area: learning_theory
TL;DR: We give a simple efficient algorithm for learning halfspaces with Massart noise.

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.

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
Gautam Chandrasekaran' gautamc@cs. utexas. edu UT Austin
Vasilis Kontonis vasilis@cs utexas. edu UT Austin
Konstantinos Stavropoulos' kstavropecs utexas. edu UT Austin
Kevin Tian kjtian&cs. utexas. edu UT Austin
Abstract
We study the problem of PAC learning 7-margin halfspaces with Massart noise. We propose simple proper learning algorithm, the Perspectron, that has sample complexity O((ey)- -?) and achieves classification error most 7) + where r) is the Massart noise rate. Prior works [DGT19b, CKMY20) came with worse sample complexity guarantees (in both and 7) could only handle random classification noise [DDK+22 KIT+23] - a much milder noise assumption. We also show that results extend the more challenging setting of learning generalized linear models with a known link function under Massart noise, achieving similar sample complexity the halfspace case. This significantly improves upon the prior state-of- thetre in this setting due to [CKMY20J, who introduced this model.
Introduction
We study the problem of learning halfspaces with margin, one of the oldest problems in the field of machine learning dating work 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 /tw Rd - (+1):
how (x) := sign (w x) for w E Rdd.
Definition (Massart halfspacc model). Let ry E [0, 1 and y E (0, 1). We say that distribution D on Bd x {+1} is an instance of the n- n-Massart halfspace model with margin 7 if the following hold.
There exists w E Rd such that ||w" 1, and Dx has margin y with respect to w", i.e.
Prx !| x| < <>==1 O.
For all x supp Dx), there is an r7(x) E [0, ry] such that Pr ly * hw (x) x] = 77(x).
We note that Definition extends straightforwardly to general halfspaces up to rescaling (i.e., with larger domain size bounds and constant shift terms), as discussed in Remark 2.
"Supported by the NSF AT Institute for Foundations of Machine Learning (IFML.).
'Supported by NSF Institute for Foundations Machine Learning (IFML).
'Supported by the NSF Al Institute for Foundations of Machine Learning (IFML) and by scholarships from Bodossaki Foundation and Leventis Foundation.
"This normalization is made for convenience, as the noise assumption of Definition is invarinna. "See Section for our notation; Dy is the x-marginal of D, and D, (x(x) the conditional marginal of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The Massart noise model of Definition 1 for halfspaces (and more generally, binary classification problems) has garnered interest from the statisties, 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, n7(x) in Definition is restricted to be 1) pointwise, i.c., the noise level is uniform; polynomial learning has long since known to be tractable under RCN [By194, BFKV98]. On the other hand, in the agnostic model (where learning is computationally intractable under well-studied conjectures [GR06, FGKP06, Danl6]). an adversary is allowed to arbitrarily modify an 1 fraction of labels. As observed by [SIo88], the Massart noise model of Definition is equivalent to allowing an oblivious adversary control an 7j fraction of labels, where the 77 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-tine tractability of learning halfspaccs, even with a margin.
PAC
For additional motivation, it 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 halfippace model, significant algorithmic advances have been made towards understanding the polynomial- time tractability of learning under Massart noise [ABHUI5, DGT19b, DKTZ20a, CKMY20, 1L21, DKK+ However, less is understood about the fine-grained sample and computational complexity of these problems, which is potentially of greater interest from 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]. popular framework for understanding the overfitting of algorithms to their modeling assumptions. To motivate semi-random models, observe that from a purely infformation-thhorree noise is actually easier than RCN; the noise level 17( is only allowed to decrease, giving more "signal" with respect to w". However, this modification poses challenges when designing algorithmss 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 7 under the RCN model to error (in the zero-one loss) using (((e))
standpoint, one might suspect that learning under Massart
samples [DDK* SDDK+23, 23, KIT KIT+23J, state-of-the-art learners under Massart noise use Ö(7 ' 9) samples (if required to be proper) [CKMY20] or O(min(y (iminn y 7 8c) samples (otherwise) [DGT19b].
The semi-randoor 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 mearly-matching, classical algorithms under the corresponding fully random models [CG18, * JLM 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 saate-of-the-ar for learning in the RCN model?
1.1
Our results
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 Aw (x) = sign(w x) for w E Bd, achieving good zero-one loss &o (see Section for a definition) over examples (x, y) drawn from the distribution D. Our main result to this end is the following.
2

---

Theorem 1 (Informal, see Theorem 3). Let D be an instance of the n-Massart halfspace model with margin ", and let E (0,1). Then, Perspectron (Algorithm 1) returns w E B such that (o-(w) $ 7 + c with probability 0.99, using
samples and Od time.
We pause to comment on Theorem 1. First, our error guarantee of the form 1) + ratherr than the more stringent goal of fg-1(w)) + c Ex=D, [n(x + c. There is strong evidence that this distinction is necessary for polynomial-ting [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+ the state-of-the-ar under the milder RCN model. There is evidence that the dependences in Theorem on both 6 and 7 are individually tight. In particular, [MN06] shows the sample complexity of the problem is ( and [DDK + 23] shows any efficient algorithm in the SQ framework must use 51(71122 122 samples. We also remark that we can assume without loss of generality that 7) is known (see Appendix B.1).
algorithms in the statistical query (SQ) framework of
Finally, mentioned, prior our work, the best-known polynomial-time learners under Defini- tion had sample complexities (mmin(y=4e"" y ()) [CKMY20, DGT19b]. In Table we summarize relevant sample complexity bounds for learning variants of halfspace models with noise.
Source
RCN
Massart
Proper
Sample Complexity
[DGT19b]
y 4-26-2
[DDK+23, KIT+23)
/
X
V
2-26-2
[DGT19b]
/
X
7 36-5
[CKMY20]
γ 46-
Theorem
Y c2-
Table Sample complexities of learning halfspaces with y margin, omitting logarithmic factors and failure probabilities for brevity. All the algorithms above run in polynomial time.
Massart generalized linear models. Our second result an extension of Theorem 1 to the more challenging setting of learning generalized linear models (GLMs) with known link function o under Massart noise. As before, we only consider distributions that have a margin with respect the optimal halfspace. We now formally define the setting we study.
Definition (Massart GLM). Let a: [-1,1] be an odd, non non-decreasing function. We say that a distribution on BB x {+1] is an instance of the a-Massart generalized linear model (GLM) with margin if the following conditions hold.
1. There exists w E Rd such that ||w*|| and Prl[w" x/ < 7/ = 0.
2. For all x E supp(Dx)) ). it holds that 17(x) = Prly o hw (x) x] < (x))
Remark 1. We remark that the assumption that a is odd is also commonly used prior works (see, e.g. [CN08, DKTZ20a, CKMY20J). We further show that our result extends to a with bounded asymmetry, albeit with a weaker error guarantee (see Definition and Theorem 4).
To provide intuition for Definition 2, observe that that if 7xx) = 1-la(w"sx) for some X E supp( 2
then E [y x] = aww" xx xsggss (w" x) o(w" x), i..., Definition 2 corresponds to the standard GLM definition. In Definition 2 (compared to Definition 1), we replace the fixed noise rate upper bound v) with data-dependent upper bound which 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 2r))sign(t) for all E [-1,
When working with a Massart GLM D. we define optRCN := E(x.))=D E [1-1o(""x)) special case of a Massart halfspace model, we simply have optRCN n. As in the case of Massart half-
Note that in the
2
'The formal variant, Theorem 3, gives high bigbbbrobbbility bounds at mild polylogarithmic overhead in sample and runtime complexities.
3

---

spaces, known SQ lower bounds make competing with opt := (o-1(==))))) := Pr(x..)~D Iv # hw (x) an intractable target, so our focus is again on attaining fo-1 = OPERCN-
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, HKLMO0, DKTZ20a], which we describe and compare Definition 2 in Section 1.3. In [CKMY20], the parameterization of this model is slightly different; they assume a is L-Lipschitz and that Prx~D, [lo . x)] 2 = 1, i... they impose margin on oww" x) rather than w This implies margin assumption (with y in Definition 2), but not vice versa. Under their slightly more restrictive assumptions, [CKMY20] claims a runtime which is an unspecified polynomial in - that is at least 4 when specialized to the halfspace case (see their Theorems 5.2 and 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 o-Massart GLM with margin y, and let é E (0, 1). There is an algoritiu returning w E B so that fo.(w) S opTRCN + c with probability 0.99, using O samples and O time.
In particular, parameterizing our problem using the margin and Lipschitz assumptions in [CKMY20] (with y + 7), we obtain an improved sample complexity of Ö(L² -)) +)
1.2 Technical overview
Learning Massart halfspaces. Our learning algorithms are inspired by the certificate framework for learning with semi-random noise developed in [DKTZ20d, CKMY20J. In that framework, given a sub-optimal hypothesis w, i.e., with error Pr(x.))> D ssign(w x) * yl 2 7 c, the goal is to construct a certificate of sub-optimality in the form of separating hyperplane between w and the target w', i.e., a vector g such that g w 2 g w - g (w w*) 2 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 proper Massart halfspace learner uses the gradient of the Leaky-ReLU objective (t) ;= (1 17) m0 t) - 7 max(0, -t) conditioned on band around the current hypothesis w as a separating hyperplane. That is, they argue that for some appropriate interval x) x w E 1]- (w w") 2 O. This yields a sample complexity scaling as Ō(E=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 e, as well as additional overhead in ? due to use of expensive outer loops taking advantage of these certificates, such as cutting -plane methods.
holds that E
To avoid the sample complexity overhead of this conditioning (implemented via rejection sampling), we use a simple reweighting scheme pointwise, which puts larger weight of |W- x (an inverse margin) on points closer to the boundary of our current hypothesis hw. Intuitively, this reweighting is soft implementation of the hard conditioning done in [CKMY20]. This is motivated by our first important observation: any significantly sub-optimal hypothesis w with ( 2 17 + e satisfies
V (
yw x) W
(w w²) 2E
x
-1 (rather than E x) x w E 7] as in [CKMY20]) as our certificate, which we can estimate via single sample.
proven in Lemma 1. This suggests using g ( x) [o]/wx/-
While reweighting by the inverse margin w x| gives a separating hyperplane certificate, it may be impossible to estimate this certificate from few samples, e.g., if the weight |w - is often very large, which introduces significant variance. For instance, even if Dxx has margin with respect w', this is not necessarily true with respect to the current hypothesis w (without further distributional assumptions on Dx). To overcome this, change our pointwise reweighting to be less aggressive and instead use (|W-x/ [[W-x++>)-> In Lemma 2, we exploit the margin assumption about Dx to show that when fo.1 (w) 2 7,,, is still the case that E (-yw-(yy))) x) w x/++++>> -1----------------- "[-(w-w") 2 e. Moreover, we still have unbiased estimator for this separating hyperplane E yyw x)) x| +)))"1
target
and the estimator is bounded in Euclidean norm by y with probability by our margin assumption.

---

Standard concentration inequalities now show 3 samples suffice to obtain a separation oracle with high probability. Plugging this certificate into oracle-efficient autting-plane methods (e.g., [Vai96]) implies an algorithm with sample complexity O (after a random projection process [AV99] to reduce to Ö dimensions). This already improves upon the prior best-known O(y=tc sample complexity. We further improve
dependence on y by using it in perceptron- like 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 3 == 1 1 22
x!0
w t- (1)) M(Bsignww') (w (0) ()0))
with w()) c- 0.
(3)
w(())
x(0
+
Since at every step perform an (approximate) perspective projection (/w on our sample, we call Algorithm which iterates the update in Equation (3) the Perspectron.
Learning Massart GLMs. For learning Massart GLMs (Definition 2), we use a similar certificate- based approach. While it is simple to show reweighting with the inverse margin ww- x x|= still works in this case (see Lemma 5), using the bounded reweighting (Iw - x + >--) does not. Instead we use new reweighting of of the form (/w x| an) where O(e) (see Lemma 6). Using similar iterative method the Perspectron defined in (3), we obtain our sample complexity of Ö(y 2e) for learning Massart GLMs.
1.3 Related work
We 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, 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, DKTZ20e, DKTZ22]. For learning halfspaces with margin, the best-known agnostic results have runtime and sample complexity that depend exponentially on the margin y and/or the accuracy parameter e [SSS09, LS1 DKM19). Another important line of work (DKT720d, 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 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, CKMY20J and the Leaky- ReLU loss that has been extensively used in prior works on learning with random classification and Massart label noise [By198, DGT19a, CKMY20, DKT21J. Our main technical contribution is new certificate that relies on an inverne-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 [DKT722). Those results have no implications for the sample complexity of the problem studied here. Finally, mention that local reweighting scheme that is somewhat similar in spirit to ours (but very different in its implementation) was previously employed by [KLL* 23], for different semi-random statistical learning problem.
1.4 Limitations and open problems
One interesting open direction is providing improved sample complexity guarantees for more gen- eral noise models. For example, the misspecified GLM framework (Definition 3.2, [CKMY20J) generalizes Definition 2 to include an additional misspecification parameter such that 7)(x) S
1-la(w" xx] + Ç. Our approach does not directly apply in this setting, since ( = 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 a is unknown, which the [CKMY20] algorithm can handle (at much higher sample complexity). While our algorithms require knowledge of a, it would be interesting to explore whether techniques from learning single-index models (e.g..
2
[KS09, GGKS23, ZWDD24]) can be used to extend our algorithms in this setting.
5

---

A clear next step is to design efficient algorithms with sample complexities independent of the margin but still linear in the dimension d. e.g., with an de sample complexity. In prior work [DKT21] such an algorithm is given, albeit with a significantly worse poly(de -1 sample complexity.
2 Preliminaries
We denote vectors in lower-case boldface, and ||x] is the Euclidean norm of x E Rd. We use B to denote the unit ball in RR i.c. B := {x E Rd || I 1}. We use (g) == min [[]] /w to vector w R onto Bd, We let Oa 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.c. 1 iff t 2 O. We use
denote the Euclidean projection
== | We let sign R + { be defined so sign(t)
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 distribution D is denoted supp(D) and [N] (i E IN S N).
Throughout the paper we study the problem of learning a binary classifier, given labeled examples from distribution D over labeled examples (x. y) Rd x {0. under various models the distribution to be discussed. We refer to the x-marginal of D by Dx. and the conditional distribution of the label x by (x). We will primarily be interested in learning halfspace hypotheses, which for w Rd are the corresponding functions hw Rd + } defined by hw (x) sign (w (.x)). We also denote the zero-one loss of halfspace hypothesis ww corresponding to w E Rd as follows, when the distribution D over labeled examples is clear from context: fa-1 (w) == (r(x)))> (l (x) o y)- We define the Leaky-RelL function with parameter À
as (x(t) == (1 A) max(0, t) À max(0, -t). Given vectors w, and y E {=1}. it holds that the (sub) gradient of Ex f-(-ww with respect w is V xww / ((1 2X 2X)sign(W x) y)- x. We also provide some brief remarks on how to extend Definition to more general settings here.
Remark 2. Definition I extends straighiforwardly to the case where Dx has margin Y and is supported on a subset of R BBd for R * 1, by rescaling so R + and r + 7. as halfspace hypotheses and our label noise assumptions only depend signs. Other than these margin and support assumptions, we make no additional distributional assumptions about the x-marginal Dx- Further, due to working in the distributional assumption-ffre setting, constant factor loss( in margin) that the halfspace is homogeneous, i.e., has no constant shift term. That is, given halfspace sign(w -x+ +b) with | |b| 1, after a feeatue expansion (E x x /2
assume with up to
(x(, the halfspace how (z) = sign((w, b))z) is homogeneous while still having a margin 2 with respect to w' === - (w,,), b). Finally, the Massari noise model of [MN06] is defined for any hypothesis class and is not tied to halfspaces. Since focus on learning halfspaces with margin, combined the hypothesis class [hw]wer with the noise model in Definition 1 for simplicity.
3 Massart halfspaces
In this section, we give our result on learning Massart halfspaces with margin. Our proof is surpris- ingly short, and we separate into its two main components: a structural lemma in Section 3.1 which shows how to estimate separating hyperplane given a sub-optimal w, and perceptron- like analysis of a stochastic iterative method Section 3.2.
3.1 Separating hyperplanes for Massart halfspaces
We prove our main structural lemma here, used to argue the progress of our iterative method. As highlighted in Section 1.2, show that when the current fo-1 (w) n + e, 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 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-Rell which is convex function,
previously observed by [DGT19b).
"B standard random- projection procedures [AV99], the dimension is comparable -3 under a m-rginn assumption, and therefore our sample complexity is nearly- -inear in the "dimension."

---

Lemma (Separating hyperplane for Massart halfspaces). Let D be an instance of the ry
Massart halfspace model, and w Rd has classification error to (w) 2 1 q+ c. It holds that
(xx,))D Vwlal ywxx
(w w*)
wx
Proof. We recall Claim 2.1 from [DGT19b]: for all w, x, it holds that E D (x) [Bx(-10 1/W x)]
(Dry)D,(x) [sign(w x) A y) -)- In particular, we have ((x,))
En( yw-x)
ln (w)
[w-x]
77. From the convexity of (-(- x), we obtain that W x) (w w") f-
b, (-yww- x). By dividing both sides by [w - and taking expectation over x and y, we obtain
V (ep( x)
yw x) L
( x
E N.y
(w w
E x.
E x.9
e,
ww x
x
w x
where the last inequality follows from the following facts: (1) for all x, it holds that By--Dy(x)) (en(-yw" x)] = (Pry>D,(x)) [sign(w" x) + n)) ----///w>>>>>>
|w" -x| (v(()) w/ w S 0.
and (2) Ex.y
[w lai(w) 2 This completes the proof.
"bounded" separating hyperplane for 7-margin Massart halfspaces. Our claim in the previous lemma very general: it works for any marginal distribution. However, discussed in Section 1.2, the unbounded nature of this separating hyperplane may make impossible to estimate from samples. Vulz(-pwxx
To overcome this, we propose a new candidate hyperplane: Ex.y |w-x +7
We prove that this candidate is indeed separating hyperplane by leveraging the fact that we have margin with respect the optimal halfspace w". Recall from Section 2 that V (- (
= ((1 2n sign(( -)))
Lemma 2 (Bounded separating hyperplane for Massart halfspaces). Let D be an instance of the M-Massart halfspace model with margin y (with respect w*) and define B 1 2n, w E Rd has fo 2 + it holds that
E (x.g)>D
[Asign(w x) - 9) w x +
+
(w w") 2c.
Proof. We first observe that by the definition of the Massart halfspace model, Ey (1 - 2n(())sign((' x) = ((x)sign(w" x), where 3(x) == 1 - 21)(x). Therefore, we have that
[Bsign(w x) (w x w" xx)
T: E (x,9)~D
w x + +
(Ssign(w x) B(x)sign(w (w" x)) (w x w xx)]
E x~
x +
We denote by g(x) == (Bsign(w x) ((x)sign( (w" xx) (w xx which we bound differently
|wxlt>
based on whether falls in the agreement region A == fx E Bd ltw- (x) lw lx)x For E A,
g(x) = (Bsign(w (w x) - -3(x)siggn( x)) (w-x xx)
w x +
x / x 3 3(x)
= (3-3(x)) |w
x
+
The second equality follows from the fact that sign(w" x) sign(w (w x). The final incquality holds since | (x) < O and
1. Similarly, for x & A, an analogous calculation yields g(x)= = (8 + [(x) w | 3+ [(x). . The first equality holds because sign(w"... "x" * sign(w (w x) and the final inequality follows since |w". x 2 y from the margin assumption. Thus
| ww'
w
[w-x|+ +
1 E [1(x A}(B 3(x)) xxDx
E x~
[1(x & A}(3 + 8(x))
7

---

We will now use our lower bound on (w), which we relate to Equation (4), We have (a-(ww)
Ex--x [1 fx A} r7(x] Ex-r= [1 (x & A] (1 - 7(x)]]
Ex- [1 fx & A} [(x)]
Ey-Dx [x[]]] Next, by our definition 3(x) = 1 - 2n)(x), rearranging and expanding we have:
1
(0.(w) -1
E [1 A}3(x))
E
|3 [(x)]
x-Dxx
2 xx~Dx
(1 & A}3(x))
E [1 E A} + 1[x & A))(B - 3(x)
x>
1
2 2x~Dx [1 & A)(3(x) + 8) + xx~Dx
[1 A)(B 3(x))
(5)
We finish the proof by combining Equation (4), Equation (5), and la.1 (w) - 17 1724 E.
3.2 Perspectron
We now present and analyze Perspectron, our algorithm for learning Massart halfspaces.
Algorithm 1: Perspectron
Input: {x', (x',y') /e.yy'/eeee veeeezz C Rdd x {+1} drawn i..d. from D the 77-Massart halfspace model with margin y, step size X > 0, failure probability 5 E (0, !
2 3 1-1- 1-1-20 2n, N + [log )1 T +- N
3 H <- 0
4 for N do
w +- 0a
6
for t E [min (T, Ti (j- 1)7) do
it (j 1)T
w w >
Asign( (w" /xxx
w xx
end
10
H + H U U he 11-1)
11
end
S + (x
T2 Jim Ti
arg min Pr Pr(x.))mmmn S how (x) # v]
Return: ho
We begin by giving a self-contained analysis of single loop j E [N] of Line Line 9, showing that for sufficiently large T. at least one iterate achieves small fo.1 with constant probability.
Let fx', , TiemT misdd. D, where D is an instance of the M-Massart halfspace model Lemma 3.
with margin with respect to w*. Consider iterating, from w == Oa.
w+1 w 3sign ww x²) yr
w. x + x'
(6)
2 for 3 1- 21, = 2/T
Then isT ट52., Pr[minem lai(w') 2 + $
Proof. Throughout the proof, say w E Rd is bad iff (w-(w) 2 17 5. and let & denote the event that all of the iterates (w*)eelt] updated according (6) are bad. Define the potential function
& = E[L (Ee)- ||w" [|w"=""["] for all t [T]. On expanding the expression for the squared norm

---

and using the fact that 1 {Ett1} I 1 {Er).
1 (EE) - 119]
D(+1 S E
Bsign(w' (w' xx)) y¹ x²
12
I 1, X²E
(w' x²1 +
[ssig(w' (ogn xx²)= -1²
2A E
(&
x² (w' ww))
|w' x²| +
4x2
Bsign (w' x²) ye x (w' - -w) E
$ 2 +
22 Pr
[ E
72
|wp x!| +
4X2
I 0 + 72
2Ac Pr [E]]-
Here, the third inequality used x' E Bd and [ssign(w' x²) - y01 2, and the fourth applied
Lemma 2. Now using that $1 S | || 1, Pr+1 2 0, and Pr[e,] 2 Pr(Er] for E [T], we have
2x [T]] < 1 + T The conclusion Pr [E]] S / follows from our choices of X, T.
We next analyze the hypothesis selection step in Line 13.
Lemma 4 (Hypothesis selection). Suppose there exists W E H with fo-1 S 1j + 5. Then if ). with probability 2 8 the w returned by Line 13 satisfies los (w) S 51 +
Ta 2 log( 2 log(2!()) à
Proof. Because S is independent of H1 Hoeffding's 's inequality and union bound implies that (r( [/w(xx + yl fa.1 (w)] < 1 with probability 2 11-6 8, for all w E H. Conditioning
on this event, fa.1 (w) > 17 + yields a contradiction:
(oi(w)
<
Pr
(x)
+ vl
S
Pr (x.
(x) + y) (ln((w)) + 4
I 4
4
(x.y)
We are now ready to state and prove our main theorem.
Theorem 3 (Learning y-margin Massart halfspaces). Let be an instance of the 1-Massart halfspace model with margin %, and let e, E (0,1). Algorithm 1 with Ti Z टम loga (3)1
16
Ta 2 o0 log( I returns such that fo-(w) 17 + with probability (((e)) loog( (0g(0-1))) +> log(((e)))))) samples and
6, using 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 5. 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 A (x) for all (x, y) E S and w E H.
4 Massart generalized linear models
In this section, we present key piece of intuition motivating our extension to the Massart GLM noise model (see Definition 2), deferring full proof to Appendix A. In this setting, instead of being upper bounded by fixed constant 17, the noise rate data-dependent and upper bounded by 1-o(w' x) where is odd non non-decreasing and w* is the optimal halfspace. Inspired by our approach in Section 3, we propose novel separating hyperplane based on the previously described reweighting scheme. We (a(ww))
argue in this section that Ex.y
x] is a valid separating hyperplane, generalizing Lemma 1.
Lemma 5 (Separating hyperplane for Massart GLMs). Let D be instance of the o-Massart GLM model with margin y (with respect to halfspace w*), and w E Rd has fo-(ww) 2 optEcN + e. We
have that E (xx))=D
(a(w x) v) x] (w w*) > 2c.
w.x

---

Proof Sketch. We use the definition of sets A, (x) from Lemma 2. By expanding out the expression for fa.1 (w) similarly Lemma 2, we obtain that 2 (xx.))> [[ xx] {xx) E A]|+ 2
(xx [[]o(w* x)I
АH {x
Let g(x) (alwx))-) (w- w"). Now, argue [w-x|
that Ex=D,[l(x)) is greater than the left hand side the previous incquality. We do a case analysis. For x E A, we observe that g(x) 2 (la(w*... x)1
3(x)) ww 2 (la(w" x)1 [())). Here,
wwx/-|w">x
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) 2 lo(w" x) For
E A, obtain that g(x) (lo(w- x)] + [()) /w-x--ww -x
[w-x] 2 (lo(w* x) + 3(x)) where
obtain the inequality by doing a case analysis: (1) [ x| S [w" x/, in this case w
w
and 2x(x) 2 (la(w* x)] + (x)) and (2), |w x 2 |w" x|, in this case (a x)] 2 (w" x)]
and hence we are done. Now, taking the expectation of gx) completes the proof the claim.
However, we are met with the same obstacle as before: |w x can be arbitrarily small. The previous approach of adding y to the denominator does not work immediately. Instead, we add the rescaled term 2-6 y. 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 factor of -2, However, this rescaling useful to obtain an analogue of Lemma for the case of Massart GLMs (Lemma 6). The rescaling essentially accounts for the part of the distribution where ww x| smaller than |w" x and the signs disagree. This is important because the size of ww x| is quantitatively more significant in the Massart GLM case.
Combining this with a modified version of the Perspectron algorithm and analysis (see Algorithm 2). we obtain our final result with sample complexity Ö(y -2 44 (see Theorem 4).
10

---

References
[ABHU15]
Pranjal Awasthi Maria-Florina Balcan, Nika Haghtalab, and Ruth Umer. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Confer- ence on Learning Theory, COLT 20/5, volume 40 of JMLR Workshop and Conference Proceedings, pages 167-190. JMLR.org, 2015.
[AL88] D. Angluin and Laird. Learning from noisy examples. Mach. Learn., 2(4):343-370, 1988.
[AV99] R. Arriaga and S. Vempala. An algorithmic theory of learning: Robust concepts and random projection. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 616-623, New York, NY, 1999.
[BFKV98] Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1/2):35-52. 1998.
IBGL*241 Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj. Aadirupa Saha, and Yuanyuan Yang. Dueling optimization with a monotone adversary. In International Conference on Algorithmic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pages 223. PMLR, 2024.
[Blu03] A. Blum. Machine learning: My favorite results, directions, and open problems. In 44th Symposium on Foundations of Computer Science (FOCS 2003), pages 11-14, 2003.
[BS95] Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs.
J. Algorithms, 19(2):204 234,, 1995.
[By194] Tom Bylander. Learning linear threshold functions in the presence of classification noise. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 1994, pages 340-347. ACM, 1994.
[By198] T. Bylander. Worst-case analysis of the Perceptron and exponentiated update algorithms. Artificial Intelligence, 106, 1998.
[CG18] Yu Cheng and Rong Ge. Non-convex matrix completion against semi-random adver- sary. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1362-1394) PMLR, 2018.
[CKMY20] Sitan Chen, Frederic Kochler, Ankur Moitra, and Morris Yau. Classification under mis- specification: Halfspaces, generalized linear models, and evolvability. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020.
[CN08] R. M. Castro and R. D. Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, (1S:):333-23533 2008
[Coh97] Edith Cohen. Learning noisy perceptrons by perceptron in polynomial time. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, pages 514-523. IEEE Computer Society, 1997.
[Dan16] Amit Daniely. Complexity theoretic limitations learning halfspaces. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 105-117. ACM, 2016.
[DDK+23] Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, and Nikos Zarifis. Information-computttiie tradcoffs for learning margin halfspaces with random classification noise. In The Thirty Sixth Annual Conference Learning Theory, COLT 2023, volume 195 Proceedings of Machine Learning Research, pages 2211-2239. PMLR 2023.
[DGT19a] I. Diakonikolas, T. Gouleakis, and C. Tzamos. Distribution-iddepeneett pac learning of halfspaces with massart noise. In Advances Neural Information Processing Systems 32, NeurlPS. 2019.

---

[DGTI9b] Iliss Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution intrriinenddeeedeenntt PAC learning of halfspaces with massart noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, pages 4751-47622 2019.
[DK20] 1. Diakonikolas and D. M. Kane. Hardness of learning halfspaces with massart noise. CoRR, abs/2012.09720, 2020.
[DKK+20] I. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. A polynomial time algorithm for learning halfspaces with tsybakov noise. arXiv, 2020.
[DKK 22| Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning general halfspacess with general massart noise under the gaussian distribution. In Symposium on Theory of Computation, volume 54, 2022.
[DKM19] Ilias Diakonikolas, Daniel Kane, and Pasin Manurangsi. Nearly tight bounds for robust proper learning of halfspaces with a margin. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.. 2019.
[DKS18] Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50 Annual ACM SIGACT Symposium Theory of Computing, STOC 2018, pages 1061-1073, 2018.
[DKT21] Ilias Diakonikolas, Daniel Kane, and Christos Tzamos. Forster decomposition and learning halfspaces with noise. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 7732-7744. Curran Associates, Inc., 2021.
[DKTZ20a] Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with massart noise under structured distributions. In Conference on Learning Theory, COLT, 2020.
[DKTZ20b] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaces with tsybakov noise. arXiv, 2020.
[DKTZ20c] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Non-convex SGD learns halfspaces with adversarial label noise. In Advances Neural Information Processing Systems, NeurlPS, 2020.
[DKTZ20d] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with tsybakov noise. arXiv e-prints, pages arXiv-2006. 2020.
[DKTZ22] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning gen- eral halfspaces with adversarial label noise via online gradient descent. In International Conference on Machine Learning, pages 5118-5141. PMLR, 2022.
[DKTZ24] I. Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Online Linear Classification with Massart Noise, 2024. Arxiv eprint: 12958..
[FGKP06] V. Feldman. P. Gopalan, S. Khot, and A. K. Ponnuswami. New results for learning noisy parities and halfspaces. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 563-574 IEEE Computer Society, 2006.
[GC23] Xing Gao and Yu Cheng. Robust matrix sensing in the semi-random model. In Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, 2023.
[GGKS23] A. Gollakota, P. Gopalan, A. R. Klivans, and K. Stavropoulos. Agnostically learning single-index models using omnipredictors. arXiv preprint arXiv:2306. 0...:2336..0.... 2023.
[GR06] Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 543-552. IEEE Computer Society, 2006.
[Hau92a] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100:78-150, 1992.
12

---

[Hau92b] David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput.. 100(():78-150, 1992.
[HKLM20] M. Hopkins, D. M. Kane, Lovett, and G. Mahajan. Noise-tolerant, reliable active classification with comparison queries. In COLT, 2020.
[JLM+233 Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sid- ford, and Kevin Tian, Structured semidefinite programming for recovering structured preconditioners. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023.
[Kaa98] M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 1566),983- 1998.
[3] Vasilis Kontonis, Fotis Iliopoulos, Khoa Trinh, Cenk Baykal, Gaurav Menghani, and Erik Vee. Slam: Student-label mixing for distillation with unlabeled examples. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023.
[KKMS05] A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. In Proceedings of the 46 IEEE Symposium on Foundations of Computer Science (FOCS), pages 11 11-20, 2005.
[KLL+2] Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly-linear time. In The Thirty Sixth Annual Conference on Learn- ing Theory, COLT 2023, volume 195 of Proceedings of Machine Learning Research, pages 2352-2338. PMLR, 2023.
[KOS08] A. Klivans, R. O'Donnell, and R. Servedio. Learning geometric concepts via Gaussian surface area. Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pages 541-550, Philadelphia, Pennsylvania, 2008
[KS09] A. T. Kalai and R. Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT. Citeseer, 2009.
[KSS94] Michael J. Kearns, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. Mach. Learn., 17(2-3):115-141, 1994.
[LS11] Long and R. Servedio. Learning large-margin halfspaces with more malicious noise. NIPS, 2011.
[MN06] P. Massart and E. Nedelec. Risk bounds for statistical learning. Ann. Statist., 34(5):2326- 2366, October 2006.
[NT22] R. Nasser and S. Tiegel. Optimal SQ lower bounds for learning halfspaces with massart noise. In Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1047-1074. PMLR, 2022.
[Ros58] F. Rosenblatt. The perceptron: probabilistic model for information storage and organization in the brain. Psychological Review, 65:386 043866407, 1958.
[Slo88] R. H. Sloan. Types of noise in data for concept learning. Proceedings of the First Annual Workshop Computational Learning Theory, COLT '88, pages 91-96, San Francisco, CA, USA, 1988. Morgan Kaufmann Publishers Inc.
[SSS09] S. Shalev Shwartz, O. Shamir, and K. Sridharan. Agnostically learning halfspaces with margin errors. TTI Technical Report, 2009.
[Vai96] M. Vaidya. new algorithm for minimizing convex functions over convex sets. Math. Prog., 13(3):291-341, 1996.
[ZL22]] Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. Conference on Learning Theory, pages 4526-4527. PMLR, 2021.
13

---

[ZLCI7] Y. Zhang, P. Liang, and M. Charikar. A bitting time analysis of stochastic gradient langevin dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages 1980-2022, 2017.
[WWDD24] Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, and Jelena Diakonikolas. Robustly learning single-index models via alignment sharpness. CoRR, 17752402.11756, 2024.
14

---

A Massart GLMs
In this section, we prove our result regarding learning in the Massart generalized linear model with margin. Our analysis is similar that of Section but requires modified version of Lemma 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 relax the assumption that odd).
Definition 3 (Massart GLM), Let |-1,1| [-1, be non-decreasing function. We say that distribution D on B x } is an instance of the a o-Massart generalized linear model (GLM) with constant shift and margin y with respect to w* if the following conditions hold.
-o(t)--oo(-))
for all [0, 1].
There exists w E IR such that ||w*|l = and Pr([w* x < 7| = O.
For all x E supp(Dx) Dx), there is an nf(x) E [0, (_lo((">x)) [ such that
Pr (x)
[y o lww (x)) = n(x).
We state and prove the following lemma which provides a separating hyperplane in this setting.
Lemma 6 (Separating Hyperplane). Let D be distribution on RR x {+1} such satisfying Definition 3. Let w E Rd be such that Pr Pr(x.e)~D (sign(w x) # y) 2 Ex-Dx 11 la(w" +)]++] + Then, we have
2
E (x,w)>D
(a(w..)) y) w x + an
(w (w- w²) 2 e, for a 6/(2-a)
Proof. Let A (x Idd sign(w x) sign(w" xx) and B {x Rd sign(w" x)). We have that
sign(w +
1 = E (x,0)>D
(a(w. x) //wwww x + az
x
- (w-w")
(w x w xx)
E x>
(o(W. -x(xssign(W x))
x az
Define g(x) (a(w- x) B(x)sign(w** x)) and x E B.
(wx-w'xx)
We analyze g(x) separately for E A
First consider points x in A. For any x E A, we have that
g(x) (o(w x) (ww x) + ooww" x) - 3(x)sign(w" -x)) (w x w x) [w x + ary
2 (lo(w" - xx]ssign(w" (w" x) ((x)ssiggn(" "w" x)) (w -x w= w
w x + ar
z (lo(w" - W x
|w" xx|
> la(w" x)1 - 3(xx).
w x ar
The second inequality follows from the fact that (a(w x) - oww x)) (w . x - w x) 2 0 since
is monotonically increasing. The third inequality holds because sign ww x) = sign(w x). The final inequality is true because [w-x]] maxx///w""xx" < and (xx) 2 la(w" x)|.
[
We now consider the case where X E B. Since sign(w x) * sign(w* x), we have that g(x) (la(w. x) + [(x)) |w +|xx+//">x
We split B into finer regions. Define B₁ {x E B
w +ay
lw x 2 |w" >x} and Bg = {x E B w x| < |w" x/)- First, consider x E B, We have
that la (ww -x] > max (0, [ w x) r). We also have that (a(-w x|) > lo(w" x) since
w x N. |w" -x] and a is monotone non-decreasing. Also, observe that [w x| |wx|-00 2 1 since
w" x N Thus, we obtain that g(x) 2 max(0, la(w" xx] 7) 3(x). Finally, consider
15

---

E B2. Let c(x)
|w'xx [w
We have that
Iw
g(x) 3(x) |w" x W [ x
1 + c(x) + (c((x)
2 B(x)
W-x
[(x)
2 (2 e))(x)
+ ary
1 (w
x
w-
The third inequality follows from the fact that /w"
x
2 and the last inequality is true because
Itee 2 2 for any Itac
when z-c- Since
2 (xx) 2 lo(w"* x)], we have that
g(x) 2 (x) lo(w" x)] 6.
Thus, we obtain that
I
E (x.y)~
[lloow' x)] B(x)) 1 (xEn)]
E (x
max(0,, lo(w" x)] -) + 3(x)) [xEB]]-
(7)
We now our assumption on the error of We have that
lo(w" x)
< Pr(xx))>n(signl x) # y)
x=Dx
2
1xX A} 1 3(x)
1 B(x)
(oww" (w". x)
=
E (x.)>DD
+ E
1(X B}
E
2
(x.))>D
2
x D2
2
E
[[[o(w" x)1 3(x)) 1fx E A}]
2 (x
1
E [[ (iaxx(,|/a(w)) x)1 -1)())) E B)] (x,y)~
Plugging this into Equation (7), we obtain that 7 2 2c 2 This completes the proof.
L
We can now prove our main theorem about Massart GLMs. The algorithm we use, Algorithm 2, is modified version of the Perspectron algorithm (Algorithm 1), where we subsitute the value of the parameter y with 7 zーe and the updates involve the function a.
Theorem 4. Let D be an instance of the o-Massarl GLM with constant shift and margin 7 with respect to w*, and let e, E (0, 1). Algorithm 2 with, Ti 2
32
[log(( T3 2 log( 4/21)
returns w such that (w-( S. Ex
la(w" +X
+ with probability 2 1 - 8, using
2
log(?)
log( 1 Agg
samples and O (
log((s) (olog()))og(d))
(
O
+
time.
22
Algorithm 2: GLMPerspectron
Input: {x', heee +nal Rdd {+1} drawn i..d. from D in the o-Massart GLM model with margin 7, parameter a E (0, 1), step size >> 0, failure probability E (0,
2 3 1-1-- 2n, N + [log2 (2) 1)1.7 T + N
3 H + Q
for j []] do
lid +- 0a
for E [Tin(T,1] Ti (j 1)T)] do
i it (j 1)T +
w11 &- wis > (o (0 x-) x!
/ H
end
H H ( /
end
12 t {xt, yx"
T2+ T T1+1
13 W <- arg min WEH Pr Px.x)) now (x) # y]
14 Return: hw
16

---

Proof. Given Lemma 6, the first step of the proof is exactly analogous to the proof of Lemma 3, i... we can show the following claim.
Claim 1. Let {x', (eeT misd D, where D satisfies Definition 3. Consider iterating, from w = Oa.
w w o(w' x²) 3¹
W x²1 + 70/(2 x',
88)
for A = (2-c) Then if
32 cty2
Pr(minee|r la-(ww) 2 Ex
x ooww"
+.
+
2
The proof is analogous the proof of Lemma 3, but ye/ e) in the place of To amplify the success probability and finish the proof, we once more use Lemma 4.
B Omitted proofs
B.1 Learning with unknown noise rate
In this section, we can obtain the same sample complexity (upto logarithmic factors) as Theorem even when the noise rate 1) is unknown to the learner. The argument is the following: we argue that our separating hyperplane (Lemma 2) is tolerant to Oce) noise in the parameter 7). 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 argue that this idea indeed works.
Lemma 7. If D is an instance of the M-Massart halfspace model with margin with respect to w and Rd has (w-( 2 17 +,
E (x.8)~D
(āsign(w w x) y)
(w w') 2e, for 3 E ((1 2n) e, 27)]
W x +
Proof. The proof is almost identical to the proof of Lemma 2 except for a few steps. We highlight differences. We reuse the notation from the previous proof.
First consider x & A, we observe that using the same argument as before, we now obtain
g(x) > 3 - (xx) 3 + B(x) e.
In the of x A, since (xx)
B, obtain
g(x) 3 (x)) 2 3 3(x) -.
Using this, we can complete the proof by repeating the steps of the previous proof.
Having proved this, our algorithm is simple,
the (1/(2c)) choices of 3 in [0. 1/2] and run
the algorithm from Theorem for each choice, reusing the same samples in the different run's of the algorithm. The correctness follows Lemma and the proof of Theorem 3 since of the the choices
of parameters must lie in the interval ((1 (2n) e, 22n)]
17

---

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]
We provide proofs and/or references for all claims made in the abstract and introduction.
Justification:
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We thoroughly discuss the assumptions under which our results hold, as well their scope and comparison with related work, in explicit limitations and future work section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create 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 few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
18

---

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

---

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

---

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

---

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

---

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


Reviews:
[{"review_id": "mXkWXKKTgt", "reviewer": "Reviewer_LLF4", "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.", "questions": "NA", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper makes a concrete improvement to the sample complexity of learning halfspaces under Massart Noise, a classic problem in learning theory.\n\n- The proposed algorithm is natural and simple, and the main ideas of the paper are explained well.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your reviewing efforts; we are glad you found our algorithm natural and simple, and that it was explained well. We mention that beyond our main technical result, from a conceptual standpoint, our paper advances a line of work giving faster learning algorithms under realistic noise models, likely to be of broad general interest.\nWe are optimistic that the insights of our paper may lead to follow-up developments, of simpler and more noise-robust algorithms in more general settings, e.g., learning noisy multi-index models (which includes fine-tuning a neural network as a case).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1x5b09mWQl", "reviewer": "Reviewer_TiaP", "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.", "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": "The authors have addressed the limitations adequately.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "I enjoyed reading this paper due to its clarity and fluency in presentation. The authors did a good job explaining the intuitions and ideas. The result of this paper is very interesting to me, as I have always thought learning halfspaces with massart noises is much harder than with RCN, and this paper provided a surprising result that shows learning with massart noise can be achieved with similar sample complexity. The method (new certificate vector) that the authors proposed is also interesting, and can be informative for future research.", "weaknesses": "No serious weakness of this paper, but there are several typos here and there. \nFor example line 263 should be $w^*$, there should be an $x$ in the end of line 270, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review, and we will make sure to address your typo catches. Re: your question about Massart GLMs, we will definitely provide more clarifying discussion on this point, as it is somewhat confusing. In particular, in a Massart GLM (following Definition 2), the optimal decision rule (evaluated by zero-one loss) is given by a halfspace, because the error rate is always $\\le \\frac 1 2$. However, the model is more general than Definition 1, because it allows a non-uniform maximum noise rate depending on $\\mathbf{w} \\cdot \\mathbf{x}$ (in the halfspace model, the maximum noise rate is uniformly $\\eta$). In summary, both of the following are true: Definition 1 is a special case of Definition 2, but the Bayes optimal prediction rule under Definition 2 is a halfspace (our algorithm also returns a halfspace).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zP4yNwp7rI", "reviewer": "Reviewer_kyaH", "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$.", "questions": "See last part of above section.", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The Massart model is a semi-random noise model motivated by the question whether known (efficient) algorithmic approaches for the fully random model, in this case random classification noise (RCN), are overfitting to the specific aspects of the model. The work of [DGT19] designed the first efficient algorithm to non-trivially learn halfspaces in this harsher noise model (without margin assumption). The current work shows that under a margin assumption, this is possible with as few samples as known efficient algorithms for the more benign RCN model needs. All prior works were loose by polynomial factors in $\\gamma$ and $\\varepsilon$.\n\nOn a technical level the submission combines previous algorithmic approaches with a regret-minimization scheme leading to an elegant analysis and ultimately a better sample complexity.\n\n\n\n\n[DGT19]: I. Diakonikolas, T. Gouleakis, and C. Tzamos. Distribution-independent PAC learning of halfspaces with massart noise", "weaknesses": "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.\n\n\n## Technical Overview\n\nI 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).\n\nHere are some specific comments about the technical overview:\n\n- lines 129-136: It is not clear from the discussion why this approach incurs a too high sample complexity on a quantitative level.\n- lines 153-162: It is not at all clear from the discussion why the proposed update rule improves the dependence on $\\gamma$\n- 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?\n\n\n## Introduction\n\n- 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\n- when you say \"learn up to error $\\varepsilon$\" in the above paragraph, do you mean error $\\eta + \\varepsilon$?\n- I believe the work [DKMR22] is not mentioned at all, this should be added\n- Similarly, when talking about impossibility results in the agnostic model, the work [Tie23] (see also [DKMR22]) should be mentioned\n- for some of the citations, the arxiv version is cited. Why not cite the conference version?\n\n\n[DKMR22]: I. Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren, Cryptographic Hardness of Learning Halfspaces with Massart Noise\n\n[Tie23]: S. Tiegel, Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your many helpful comments, and suggested references. We agree with all of your suggestions regarding the introduction and citations, and will fix them in a revision.\n\nWe agree additional care can be taken to clarify the technical overview, emphasizing conceptual points and quantitative gains over formulas and full proofs.\n\nLines 129-136: Re: the $\\epsilon$ dependence, the number of iterations of both of our methods scales as $\\frac 1 {\\epsilon^2}$, but to implement each iteration of [CKMY20], they need to rejection sample from a region. The [CKMY20] termination condition only guarantees this region has at least $\\epsilon$ probability mass, yielding a $\\frac 1 \\epsilon$ overhead. Re: the $\\gamma$ dependence, this is similar to the following comment on cutting plane methods, which require certificates with much smaller failure probabilities than the first-order regret minimization approach we use. The [CKMY20] method is cutting plane-based, so their certificates are less sample efficient.\n\nLines 153-162: The key difference is that cutting plane methods require high-probability guarantees on separating oracles being valid (as they are not robust to occasional errors); standard probability boosting techniques require $\\gtrsim \\frac 1 {\\gamma^2}$ samples for sub-Gaussian concentration to kick in. On the other hand, the projected gradient regret minimization method we use is tolerant to any unbiased estimator with a second moment bound, so it only needs one sample per iteration, leading to a better $\\frac 1 \\gamma$ dependence.\n\nLines 172-174: At the time of submission, we made the presentation decision to use a reweighting which adds $\\gamma$ to the denominator rather than implementing the push-away operation (in the halfspace case), as it is conceptually simpler and adds less overhead to the proof. In light of the error we noted in the meta-comment, this distinction is no longer relevant, and in our revision we will include our new corrected proof for Massart GLMs.\n\nWe plan to add discussion of these important points to the technical overview, and more generally include more comparisons to previous approaches, mentioning in greater detail why they incurred suboptimal sample complexities. In particular, we will spell out the bottlenecks to improving cutting plane methods (such as [CKMY20]'s approach) in more detail, as well as other previous approaches in the literature. We hope that this response was clarifying, and that our revision plan elevates our paper in your viewpoint.\n\n*[CKMY20] Sitan Chen, Frederic Koehler, Ankur Moitra and Morris Yau. Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability. NeurIPS 2020*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vpmmvUmgVl", "reviewer": "Reviewer_vx3q", "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.\n\nThe 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.\n\nThe paper also provides an algorithm for a more general model, the generalized linear model (GLM), under Massart-noise.\n\nThe paper is generally very-well written.", "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": "Since this is a theoretical paper, I do not see any potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The problem of learning half-spaces under Massart noise is a fundamental problem that has received a lot of attention recently. This paper provides a simple algorithm with a low sample-complexity that is probably optimal.\n\nThe paper also provides generalizations to the GLM models.", "weaknesses": "I haven't found any significant weaknesses.\n\nTypos:\n- Page 3, line 97: “observe that that if” ->  “observe that if”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate that you found our paper well-written. Thank you for your typo suggestions; we will fix these in a revision. Re: your question in Lemma 3, we chose this parameter tradeoff because it yields a $\\log(\\frac 1 \\delta)$ overhead in our runtime. As you suggest, it is also possible to directly obtain a failure probability of $\\delta$ in one shot. However, this would require taking a number of steps polynomial in $\\frac 1 \\delta$, which is a worse overall tradeoff.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nZf5G40MoP", "reviewer": "Reviewer_x3Ci", "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.", "questions": "\\section*{Questions}\n\nLine 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.\n\nLine 72 : what error does previous work in massart noise setting use? If other- why not use the same?\n \n\nLine 102 $\\eta(x)$?\n\nNot consistent whether it is $Pr_{\\cdot}$ or just $Pr$\n\nTable: Good table. Is the running time not interesting?\n\nThe 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.\n\nLine 221: should it be $B^d\\times \\{-1,1\\}$?\n\nLine 229: why isn't it a vector? Can you give the derivation of this expression?\n\nLine 238: $h_{w'}=sign((w..$ shouldnt it be $h_{w'}=sign((w'..$ \n\nLine 261: what does the $l_\\eta(w*,x,h)$ mean? Happens more places in this proof.\n\nLine 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.\n\nLine 276: it says $w^{\\star}$ instead of $w^*$\n\nLine 298-299: The third line in the equation missing $x^t$\n\nLine 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?\n\nLine 307: why say anything about contradiction - doesn't it just follow from the inequality afterward?\n\nLine 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$?\n\nLine 329: what is $B$?\n\nWould it be interesting to make the computational cost independent of d with the cost of polynomial factors in $1/\\gamma\\varepsilon$?", "limitations": "They address the limitations of the work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\nThe paper seems to combine many ideas from different papers and in this way get a novel result and improvement over previous results. Related work is well cited. \n\nQuality: \nThe main of the paper includes a full proof of the Massart noise and a proof sketch of the general setting. The proof of the Massart noise case on a first quick read seems ok. The proof sketch is ok - I have not read the appendix with the full proof so I will not comment on the technically soundness of the proof. The authors also address the limits of their work and state interesting future work.\n\nClarity:\nThe paper is very well written and explains very well the ideas behind the proof.\n\nSignificance: \nThe improvement in sample complexity is a polynomial improvement in $(\\gamma\\varepsilon)^{-1}$ so I would say significant.", "weaknesses": "Weaknesses:\nNot 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)]$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading, and all of your detailed feedback. We are glad that you found our explanations clear. Regarding improved dependences on $\\mathbb{E}[\\eta(\\mathbf{x})]$, prior work has shown that such guarantees are likely computationally intractable for statistical query based algorithms (such as ours, and all previous Massart learners) under standard complexity assumptions: see, for example, the citations [CKMY20, DK22, DKMR22, NT22]. Therefore, to give a polynomial-time algorithm, we focus on achieving error $\\eta + \\epsilon$. We discuss this point in Lines 73-76 of our submission. This is consistent with previous works in the Massart model, re: your question about Line 72.\n\nWe now address the reviewer's other more specific questions.\n\nLine 102: This should be $\\eta$, as stated, as it is about the noise rate upper bound.\nTable: All runtimes are nearly-linear in the input size, but we will add such a remark.\n\nLine 229: This was a typo, and there should be an extra factor of $\\mathbf{x}$ due to chain rule, so it is a vector. Thank you for noticing this.\n\nLine 261: This was a typo, it should say $\\ell_\\eta(-y\\mathbf{w}^\\star \\cdot \\mathbf{x})$, and we will fix this.\n\nLine 263: Yes, as you point out, the expression should be about $\\mathbf{w}^\\star$.\n\nLine 289: This is correct, and we will note this for clarity.\n\nLine 307: Good catch, we will make this simplification.\n\nLine 313-316: In our application of Algorithm 1 (Theorem 3), we ensured even divisibility.\n\nLine 329: $B$ was intended to be the complement of $A$ (as in Lemma 2); we will clarify this.\n\nComputational cost: We expect that achieving independence of $d$ is unachievable, as one needs to at least read in the samples. However, we do agree that it is interesting to see if fast dimensionality reduction techniques could be used to speed up the low-order terms of our algorithm's runtime; thank you for this suggestion.\n\n*[CKMY20] Sitan Chen, Frederic Koehler, Ankur Moitra and Morris Yau. Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability. NeurIPS 2020*\n\n*[DK22] Ilias Diakonikolas, Daniel Kane. Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise. Conference on Learning Theory, 2022*\n\n*[DKMR22] Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren, Cryptographic Hardness of Learning Halfspaces with Massart Noise. NeurIPS 2022*\n\n*[NT22] Rajai Nasser, Stefan Tiegel. Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise. Conference on Learning Theory, 2022*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their positive feedback on our paper! 

We would like to point out a technical issue in the current proof of Theorem 4 for learning **Massart GLMs**, which we found after the submission of our paper. The issue can be resolved through a concise extension of the proof of Theorem 3 (which we provide below), albeit with a worse sample and runtime complexity scaling as $\tilde{O}(1/(\epsilon^4 \gamma^2))$. This sample complexity is still an improvement to the comparable prior work [CKMY20] on Massart GLMs across all parameters, see discussion in Lines 107-115.

 **Our main statement and proof on Massart halfspaces (Theorem 3) is correct and remains unchanged.**

Despite the additional factor of $1/\epsilon^2$ in the sample complexity of learning Massart GLMs, the qualitative value of our result remains: a simple SGD-based algorithm simplifies and improves the best known algorithms for Massart GLMs with known activations. 

Our revised approach for Massart GLMs is in line with our overall message, by showing that the Perspectron algorithm (Algorithm 1), after a slight parameter modification, achieves state-of-the-art guarantees for a more general noise model, in addition to halfspaces (Definition 1). This emphasizes the value of our simple algorithmic approach.


### Technical issue with current proof 

Lemma 6, Part 2 is incorrect. It is only true when $\mathbf{w}$ is a unit vector. The issue stems from the fact that the added "Push-away" term is potentially unbounded when $\|\mathbf{w}\|$ is small. Intuitively, it is impossible to induce a large margin in an unnormalized small direction.

### Working Fix

As a consequence of this error, our analysis for Massart GLMs using the Push-away operation fails to go through. We propose a simple fix achieving a sample complexity of $\tilde{O}(1/(\gamma^2\epsilon^4))$. This still improves over prior work, but does not match our halfspace result.

We now present the details of our fix. Instead of the push-away operator, we use $|\mathbf{w}\cdot\mathbf{x}| \to |\mathbf{w}\cdot\mathbf{x}|+\frac{\gamma\epsilon}{2-\epsilon}$ as the modified denominator of the separating hyperplane in Lemma 5, thus bounding the norm of the step in our iterative method by $O(1/\epsilon \gamma)$. Combining this with the iterative method leads to the new sample complexity bound. We will add the complete proof in the final version and can also attach a pdf containing it if requested by the reviewers. We now present the proof of correctness for the new separating hyperplane, by highlighting the changes to the steps in the proof of Lemma 5. 

*Lemma.* Let $D$ be an instance of $\sigma$-Massart GLM model with margin $\gamma$ and $\ell_{\text{0-1}}(\mathbf{w})\geq \text{opt}_{\text{RCN}}+\epsilon$. Then, we have that

 $\mathbf{E}_{(\mathbf{x},y)\sim D}[\frac{(\sigma(\mathbf{w}\cdot\mathbf{x})-y)}{|\mathbf{w}\cdot \mathbf{x}|+\alpha\gamma}\mathbf{x}]\cdot (\mathbf{w}-\mathbf{w}^*)\geq \epsilon$, where $\alpha=\frac{\epsilon}{2-\epsilon}$.

*Proof*. We borrow notation from the proof of Lemma 5. The only change from Lemma 5 is in how we lower bound $g(\mathbf{x})$. The analysis for the case $\mathbf{x}\in A$ is identical as it does not depend on the normalization used in the denominator of the separating hyperplane. We now analyse the case $\mathbf{x}\notin A$. There are two subcases. 

First, suppose $|\mathbf{w}\cdot\mathbf{x}|\leq |\mathbf{w}^*\cdot \mathbf{x}|$. Let $c(\mathbf{x}):=\frac{|\mathbf{w}^*\cdot\mathbf{x}|}{|\mathbf{w}\cdot\mathbf{x}|}$. In this case, we have that $g(\mathbf{x})\geq\beta(\mathbf{x})\cdot\frac{|\mathbf{w}\cdot \mathbf{x}|+|\mathbf{w}^*\cdot\mathbf{x}|}{|\mathbf{w}\cdot\mathbf{x}|+\alpha\gamma}=\beta(\mathbf{x}) \cdot \frac{1+c(\mathbf{x})}{1+\alpha\frac{\gamma}{|\mathbf{w}^*\cdot\mathbf{x}|}c(\mathbf{x})}\geq \beta(\mathbf{x})\cdot\frac{1+c(\mathbf{x})}{1+\alpha c(\mathbf{x})}\geq \beta(\mathbf{x})(2-\epsilon)$, where the third inequality follows from $|\mathbf{w}^*\cdot\mathbf{x}|\geq \gamma$, and the final inequality follows from $\frac{1+c}{1+c\alpha}\geq 2-\epsilon$ for any $c\geq 1$ and $\alpha=\frac{\epsilon}{2-\epsilon}$. Thus, $g(\mathbf{x})\geq |\sigma(\mathbf{w}^*\cdot\mathbf{x})|+\beta(\mathbf{x})-\epsilon$. 

Finally, consider the case where $|\mathbf{w}\cdot\mathbf{x}|\geq |\mathbf{w}^*\cdot \mathbf{x}|$. Here, we have that $g(\mathbf{x})=(|\sigma(\mathbf{w}\cdot\mathbf{x})|+\beta(\mathbf{x}))\cdot\frac{|\mathbf{w}\cdot\mathbf{x}|+|\mathbf{w}^*\cdot\mathbf{x}|}{|\mathbf{w}\cdot\mathbf{x}|+\epsilon\gamma}\geq |\sigma(\mathbf{w}^*\cdot\mathbf{x})|+\beta(\mathbf{x})$ as $|\mathbf{w}^{*}\cdot \mathbf{x}|\geq \gamma$.

Thus, we have proven that $g(\mathbf{x}) \ge |\sigma(\mathbf{w}^*\cdot\mathbf{x})|\pm \beta(\mathbf{x}) - \epsilon$ pointwise, where the $\pm$ depends on whether $x \in A$. We now repeat the steps from Lemma 5 to complete the proof, by comparing $g(\mathbf{x})$ to the zero-one error at $\mathbf{x}$, as done in Lemmas 1 and     2.

Meta-review: 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.
Decision: Accept (spotlight)