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

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.

Strengths

Originality: The 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. Quality: The 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. Clarity: The paper is very well written and explains very well the ideas behind the proof. Significance: The improvement in sample complexity is a polynomial improvement in $(\gamma\varepsilon)^{-1}$ so I would say significant.

Weaknesses

Weaknesses: Not anything significant - related to the question below do the other papers also use $\eta$ in the error bound instead of $E[\eta(x)]\leq \eta$? If yes why not use $E[\eta(x)]$?

Questions

\section*{Questions} Line 18-20: I really like how it was $Pr_{x\sim D_{x}}$ was used as it made the randomness explicit - I didn't at first get that the randomness in the $Pr$ (line 20) was over $y\sim D_{y}(x)$ I don't know if other readers would have the same experience. Line 72 : what error does previous work in massart noise setting use? If other- why not use the same? Line 102 $\eta(x)$? Not consistent whether it is $Pr_{\cdot}$ or just $Pr$ Table: Good table. Is the running time not interesting? The real numbers $R$ and natural numbers $N$ didn't look like I'm used to seeing them - I don't know if this is on purpose if it is don't mind changing it - I just wanted to let you know in case that something has complied weirdly. Line 221: should it be $B^d\times \{-1,1\}$? Line 229: why isn't it a vector? Can you give the derivation of this expression? Line 238: $h_{w'}=sign((w..$ shouldnt it be $h_{w'}=sign((w'..$ Line 261: what does the $l_\eta(w*,x,h)$ mean? Happens more places in this proof. Line 263: Please show fact (1), or should it be $l_\eta(-yw*x)$. If facts 1) and 2) follow from the fact stated at the beginning of the proof from [DGT19b] maybe consider moving these together. Line 276: it says $w^{\star}$ instead of $w^*$ Line 298-299: The third line in the equation missing $x^t$ Line 289 algorithm line 7: this makes $w^t$ and $x^t$ independent right? Which is used in the proof of lemma 3 last inequality of the large equation combined with lemma 2? Line 307: why say anything about contradiction - doesn't it just follow from the inequality afterward? Line 313-316: I guess It doesn't matter that the last badge isn't necessarily of size $T$? Or is it necessarily of size $T$? Line 329: what is $B$? Would it be interesting to make the computational cost independent of d with the cost of polynomial factors in $1/\gamma\varepsilon$?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

They address the limitations of the work.

Summary

The paper considers the problem of PAC-learning $\gamma$-margin halfspaces under $\eta$-Massart noise. The paper provides an efficient algorithm achieving error $\eta+\epsilon$ with sample complexity $\tilde{O}(1/(\epsilon^2\gamma^2))$. The individual dependence of the sample complexity on $\epsilon$ and $\gamma$ appears to be optimal for efficient algorithms in the light of lower bounds provided in previous work. The algorithm is a form of stochastic-gradient descent where the loss function is the LeakyReLu loss. The gradient is carefully weighted with an appropriate weight in order to yield the desired results. The paper also provides an algorithm for a more general model, the generalized linear model (GLM), under Massart-noise. The paper is generally very-well written.

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. The paper also provides generalizations to the GLM models.

Weaknesses

I haven't found any significant weaknesses. Typos: - Page 3, line 97: “observe that that if” -> “observe that if”

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$?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

4

Limitations

Since this is a theoretical paper, I do not see any potential negative societal impact.

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

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$. On 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. [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. ## Technical Overview I like the structure of the technical overview and that it tries to highlight differences with previous works (this also shows expertise of the authors). Unfortunately however, in several places the writing is unclear (see below). I find it nice that the proof for the halfspace result is so short that it fits in the main body. Nevertheless, I would find a more extensive technical overview with commentary much more illustrative then including the full proof (the many formulas make this hard to read and understand what is going on). Here are some specific comments about the technical overview: - lines 129-136: It is not clear from the discussion why this approach incurs a too high sample complexity on a quantitative level. - lines 153-162: It is not at all clear from the discussion why the proposed update rule improves the dependence on $\gamma$ - lines 172-174: You say that this approach also works for the case of massart halfsapces. Why did you not follow this approach? From the discussion it seems it would significantly simplify a part of the analysis. Is there anything else that breaks? ## Introduction - lines 46-58: Before diving into the details of the fine-grained aspects and to set the stage, it would be helpful to briefly explicitly recall what is known in the general Massart model (without margin assumption) -- e.g., error $\eta$ is possible and this is likely optimal - when you say "learn up to error $\varepsilon$" in the above paragraph, do you mean error $\eta + \varepsilon$? - I believe the work [DKMR22] is not mentioned at all, this should be added - Similarly, when talking about impossibility results in the agnostic model, the work [Tie23] (see also [DKMR22]) should be mentioned - for some of the citations, the arxiv version is cited. Why not cite the conference version? [DKMR22]: I. Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren, Cryptographic Hardness of Learning Halfspaces with Massart Noise [Tie23]: S. Tiegel, Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems

Questions

See last part of above section.

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

yes

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.

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. For example line 263 should be $w^*$, there should be an $x$ in the end of line 270, etc.

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?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors have addressed the limitations adequately.

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.

Strengths

- The paper makes a concrete improvement to the sample complexity of learning halfspaces under Massart Noise, a classic problem in learning theory. - 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.

Questions

NA

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes