Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise

Summary

The paper considers the problem of learning $d$-dimensional halfspaces $h(x) = \mathrm{sign}(w \cdot x + t)$ over Gaussian marginals under random classification noise (where with probability $\eta$, a sample is given the incorrect label). While the homogeneous case (where $t = 0$ and the bias $p = \frac12$) by prior works, the paper focuses on the in-homogenous case where $t$ is unknown. The results give a nearly tight characterization of this regime: * Theorem 1.3 shows that there exists a polynomial-time algorithm for learning in-homogeneous halfspaces that uses $N = \tilde{O}(d / ((1 - \eta)\epsilon) + d / \max(p(1 - 2\eta), \epsilon)^2) \log \frac1\delta$ samples. The algorithm (given and analyzed in Section 2 and Appendix B) works as follows: * The Initialization procedure chooses a weight vector $w_0$ and predicts the bias $\hat{p}$ by iteratively averaging together signed samples until the norm of their average is sufficiently large. * The Optimization procedure locally updates $w_0$ by running Riemannian subgradient descent on a band of inputs on unit sphere of width $\hat{t}$, for each $\hat{t}$ belonging in an $\epsilon$-net over all thresholds $t$. * The Testing procedure identifies which threshold gives the lowest error on a new sample and outputs such a classifier. * Theorem 1.5 shows the near-optimality of the upper bound by showing that SQ-learning $p$-biased halfspaces under constant RCN requires either an exponential number of queries or at queries to an oracle of accuracy $d^{1/2 - c} / p^2$, whose dependence on $p$ matches the upper bounds.

Strengths

The paper is well-written, the bounds are mathematically interesting and have clear proofs, and the matching dependence on $1 / p^2$ in the upper and lower bounds is a strong argument that these bounds are nearly optimal. While I did not review all of the details of the proofs in the appendices, I didn't find any technical red flags. Theorems and lemmas are well-stated and easy to follow.

Weaknesses

A minor note: The pseudocode for Algorithm 1 could be written in way that makes it more easily digestible for readers. Some helpful details (like the sample complexity for Initialization and Testing) could be included, while terms like $M$ could probably be given asymptotically for simplicity.

Questions

The upper and lower bounds have a substantial gap in $d$. Do the authors believe that this gap could be closed by a future work? And does a similar gap exist in the literature for learning homogeneous halfspaces? Likewise, do you expect it to be possible to prove a lower bound with a more sensitive dependence on the classification noise $\eta$? It would be interesting to see if the problem gets much harder as the noise level approaches $\frac12$. I don't exactly see why the Optimization procedure is subgradient descent on a leaky ReLU rather than just a scaled ReLU; if it were leaky, shouldn't there be another additive term in the gradient computation multiplied by $\eta$, rather than just one term in the band multiplied by $(1 - \eta)$?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

All limitations are well-documented in the assumptions underlying the theoretical results.

Summary

This paper studies the problem of learning Gaussian half-spaces with random classification noise. Given labeled data $(x,y)\sim D$ where $x$ follows the standard Gaussian distribution, a halfspace function $f$ such that $y=f(x)$ with probability $1-\eta$ and $y=-f(x)$ with probability $\eta$ and a precision parameter $\epsilon$. The goal is to construct a halfspace function $h$ such that for $(x,y)\sim D$, $h(x)=y$ with probability at least $1-\eta-\epsilon$. This paper provides lower and upper bounds on the sample/time complexity in the general case where $f$ can be biased: $p=\min(Pr[f(x)=1], Pr[f(x)=-1])\neq 1/2 $. An efficient algorithm is proposed with a sample complexity $\tilde{O}(d/\epsilon + d/\max^2(p,\epsilon) )$. A lower bound on the sample complexity of $\Omega(\sqrt{d}/ \max^2(p,\epsilon) )$ is proved for SQ efficient algorithms.

Strengths

Generalizing the problem of learning Gaussian halfspaces with RCN to not necessarily homogeneous halfspaces is a good contribution. Moreover, the bad term of the sample complexity $\tilde{O}( d/\max^2(p,\epsilon) )$ could not be improved in terms of the dependency in $\max(p,\epsilon)$ thanks to the lower bound proved. The algorithm is not a trivial generalization of the one for homogeneous halfspaces with RCN.

Weaknesses

One weakness is that the lower bound has does not match the upper bound in terms of the dependency in $d$.

Questions

Do you think your results could be generalized to (some) distributions $D$ with non Gaussian marginal $D_x$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

The authors provide an algorithm to learn d-dimensional halfspaces under random classification noise upto error \eps. The algorithm has time complexity O(dN/\eps^2), where N is the number of samples; and sample complexity ~ \tilde{O}(d/\eps + d/\eps^2). They also prove a lower bound, in the statistical query model, that requires \Omega(\sqrt{d}/\eps^2) samples, unless the model makes high accuracy queries.

Strengths

- The problem of learning half spaces under noise is an important and fundamental problem in machine learning. - The results are tight in the statistical query model up to a factor \sqrt{d}. - Clear and lucid technical overview..

Weaknesses

No significant weaknesses.

Questions

Some of the writing in the proofs can be simplified, constants like 0.000098 can be jarring.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes, adequately discussed.

Summary

This paper studies the PAC learning complexity of half spaces (or linear threshold functions), when the labels are flipped randomly with some probability $\eta$. For realizable hypothesis classes, it is known that $O(d/\epsilon)$ samples are enough to learn a halfspace with $\epsilon$ 0-1 error. Under random classification error, the problem becomes much more challenging. This paper makes two contributions to this problem: - First, it presents an efficient algorithm with comparable scaling to $\tilde O_{\eta}(d/\epsilon + d / (\max(p, \epsilon))^2 )$. - Second, it proves statistical query lower bounds that match the above upper bound under certain regimes of $\eta$. The upper bound involves three subroutines, including a warm start initialization that returns a vector close enough to the target. Second, it issues queries near the threshold, akin to learning a leaky ReLU loss. Lastly, it uses a simple hypothesis testing procedure, which draws a fresh sample and selects a hypothesis with the lowest test error. Ther SQ lowe bound establishes the existence of a large set of distributions whose pariwise correlations are small. The construction builds on prior work of Diakonikolas, Kane and Steward (FOCS'17).

Strengths

S1) The paper makes two contributions to learning halfspaces with random classification noise--this would be a nice contribution to this literature. The results seem solid and technically challenging. S2) The authors make an effort to explain their results at a high level, which is helpful.

Weaknesses

W1) My main concern with this paper is the presentation of their technical results; in particular, there is a large number of notations, many of which are not clearly explained or are difficult to follow. This would limit the potential audience of their work within the broader NeurIPS community. W2) There are some inconsistencies between the statements, in particular, line 10 and line 46, which should be fixed or better explained.

Questions

- Is the assumption of $p$-biasedness necessary for showing the sample complexity guarantee? - The comparison with a concurrent work of Diakonikolas et al. (2023) needs to be stated more clearly. - How critical are the results inherent to Gaussian inputs?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors have not discussed the limitations of their work in the main text. The paper is of a highly technical nature, so potential negative societal impacts of their work would be limited.

Summary

This paper gives new positive and negative results for the problem of learning general (nonhomogenous) Gaussian halfspaces under the random classification noise (RCN) model. The motivating question is whether there exists a polynomial time algorithm nearly achieving the (known) minimal sample complexity required for solving the problem. Positive result -- The authors give an efficient algorithm that solves this problem; this algorithm works with a sample complexity that is only off of the known optimal sample complexity by logarithmic factors. Specifically, the runtime of the algorithm is roughly $O(dN/\varepsilon^2)$, where $N$ (sample complexity) is roughly $O(d/\varepsilon^2 \cdot \log(1/\delta))$ and $\varepsilon$ is the target suboptimality. (note that I have omitted the dependences on the noise rate $\eta$ and the bias $p$ of the target function -- both are probably optimal) To obtain the positive result, there are three main algorithmic contributions. The first is an initialization step, which returns a vector whose correlation with the true weight vector is pretty high. The second is an optimization procedure that takes as input a guess for the threshold of the target halfspace and returns a halfspace of low error with that fixed threshold. The third is a procedure that tests several hypotheses and selects the one with the lowest error. Negative result -- The authors give a Statistical Query (SQ) model lower bound on the sample complexity of any algorithm solving the above problem -- either the statistical queries have to be very accurate, or there need to be an exponential number of queries made in order to recover a linear separator with nontrivial suboptimality. The authors also use a recent result almost equating SQ algorithms and low-degree tests to give a lower bound in the low-degree testing model. The exact statement is a bit technical, so I'll omit it here. It can easily be found in Theorem 1.5. EDIT 2023-09-01 -- As mentioned in my response, my review stands. Thank you for answering the questions!

Strengths

The paper almost (up to pesky logarithmic factors) resolves the motivating question of whether the optimal sample complexity can be achieved by an efficient algorithm for this problem. The algorithmic primitives are natural and easy to understand. The problem is pretty fundamental. Finally, the paper is clearly presented.

Weaknesses

There are minor typographic issues that can be cleaned up (e.g. spelling mistakes, long math strings, etc.) -- of course this is very minor. Although the optimality of the sample complexity is discussed, there appears to not be as much emphasis on the optimality of the runtime (in particular, the worst case dependence on $\varepsilon$ in the runtime is $\varepsilon^{-4}$ -- is this unavoidable?)

Questions

What do you think are interesting future directions? e.g. do you think it is possible to obtain an even faster algorithm for this problem? If so, do you think extensions of the ideas you presented are likely to work, or do you think a totally different algorithmic approach is necessary? I probably missed this in the paper, but what is known about this problem when the input distribution is uniform over the vertices of the hypercube (i.e., $\mathsf{Unif}(\{\pm 1\})^d$? Do the techniques you give in this work readily transfer to this setting? It feels to me as though the Boolean setting is a more basic variant of the problem you study, but I would believe that the two are morally very similar.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Yes

Summary

This paper studies the problem of learning non-homogeneous halfspaces in the presence of Random Classification Noise, where the marginal distribution is standard Gaussian in $d$ dimensions. On the upper bound side, this work provides an efficient algorithm that achieves learning an $\epsilon$-optimal halfspace with sample complexity $\tilde{O} (\frac{d}{\epsilon} + \frac{d}{\max (p,\epsilon)^2})$ where $p$ is the bias of the target halfspace. The algorithmic idea involves Initialization, Optimization, and final Testing subroutines. The algorithm runs for $O(1/\epsilon^2)$ guesses of the threshold $t$ and selects the best output halfspace. On the lower bound side, this work establishes a nearly matching lower bound that no efficient SQ algorithm can learn a Gaussian halfspace with $\eta = 1/3$ with less than $\Omega( \frac{\sqrt d}{\max (p,\epsilon)^2} )$ samples.

Strengths

1. This work studies learning halfspace with RCN, which is a fundamental problem in machine learning theory. Although it has been known that halfspaces are efficiently PAC learnable with RCN, this work refines the sample complexity of the previous works in the Gaussian marginal distribution setting. Moreover, it provides formal evidence that the quadratic dependence on $ \frac{1}{\max (p,\epsilon)}$ is the best one can hope for an efficient algorithm. 2. This paper is technically strong. 3. Along with the formal technical statements and proofs, this work exhibits some valuable informal explanations and implications of the results, which makes it easier for the readers to understand and appreciate the significance of the results in this paper. 4. The main algorithm consists of several subroutines, each coming with a nice explanation and theoretical performance guarantees.

Weaknesses

1. It could be nice to have a more comprehensive review of the related works. E.g., how is the sample complexity in this work related to the other papers on learning halfspaces with RCN with comparable settings? 2. It could be good to include in the main algorithm the case where the threshold $t$ is significant.

Questions

1. Could the main algorithm be modified a bit so that it could directly tell if the true threshold $t$ is significant enough and a constant hypothesis suffices? 2. In Algorithm 1, the Optimization procedure is invoked for $M = O(1/\epsilon^2)$ times, and $N_2 = \tilde{O} (\frac{d}{\epsilon} )$ samples are drawn in each iteration. Could you please explain a bit more about why the total sample complexity (the dependence on $\epsilon$) is less than $ \tilde{O} (\frac{1}{\epsilon^3} )$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

There are no obvious limitations to be addressed in my opinion. One question that might be interesting to study is if it is possible to attain matching bounds in $d$.