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

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.

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.

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

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.

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.

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.

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.