Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper establishes the cryptographic hardness of learning halfspaces with Massart noise by reducing the Learning with Errors problem to it, which as claimed is widely believed to be subexponential-time hard. This improves the precious statistical-query hardness by [DK21], which only holds for a restricted class of SQ models. The key technique is establishing some hard instances for Massart halfspaces and then performing rejection sampling to produce them from the LWE samples. As a result, the hardness of LWE problem implies the hardness of learning LTFs with Massart noise.

strengths_and_weaknesses: The result shows that no polynomial-time algorithm can achieve o(\eta) error even though the optimal rate OPT is very small, implying the optimality of the existing Massart halfspaces algorithms ([DGT19,CKMY20,DKT21]). The established lower bound helps to understand the hardness of an interesting and important problem of learning Halfspaces with Massart noise, a noise type that is considered to be between the random classification noise model and agnostic model, which makes it an important progress in the theory of learning. No concerns on the clarity.

questions: Can the authors address the essentialness of the subexponential hardness of LWE, and to what extent it holds?

limitations: There are no negative social impact concerns for this paper.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proves a new cryptographic hardness result for the fundamental problem of learning halfspaces with Massart noise in the distribution-free setting. Specifically, they assume subexponential hardness of the Learning with Errors (LWE) problem and show the following: given a distribution consistent with a halfspace except with $\eta$-bounded Massart noise (think of $\eta = 1/3$), and for which the true OPT is almost polynomially small, no polynomial-time algorithm can achieve 0-1 loss better than $\Omega(\eta)$. Technically, they show that even a natural decision version of this learning problem is hard.

The approach taken is a careful reduction from continuous LWE (itself as hard as LWE) to the problem of learning polynomial threshold functions (PTFs) with Massart noise; by the natural monomials feature map, PTFs are just LTFs over a higher-dimensional space. The reduction builds closely on prior work that showed a superpolynomial SQ lower bound for the same problem. At a high level, the final hard Massart distribution that one wishes to generate is roughly similar in both: one wants a distribution of $(x', y')$ that is consistent with a Massart PTF, and such that the two conditional distributions $x' | y' = +1$ and $x' | y' = -1$ are "pancake distributions", i.e. Gaussian in all directions except one, in which it is instead a mixture of _discrete_ Gaussians that matches many moments with a standard Gaussian. One does this using a very careful kind of rejection sampling; the technical work required is very delicate and nontrivial. Overall, this approach falls into a major line of work on lower bounds for non-Gaussian component analysis and other problems using reductions arising from it, with one of the key foundational works being DKS17.


strengths_and_weaknesses: Strengths:

This is an important hardness result for a fundamental problem in learning theory, perhaps one of the most basic ones in robust PAC learning. The SQ lower bound was already quite convincing, but a cryptographic lower bound has the benefit of not being restricted to a certain model. And while the approach in this paper closely follows the SQ proof, the additional technical work required is still considerable and showcases great mastery of the ideas and techniques involved. The paper is very well-written and clear; the figures in the supplement are particularly helpful. Considering the proofs are quite technical, I do not claim to have verified them in complete detail, but they seem correct to me.

Weaknesses:

One small weakness of this work is that it assumes _subexponential_ hardness of LWE. This is still widely-believed, but it is natural to wonder if a weaker assumption would suffice. The authors do point out how this assumption is consistent with the known SQ lower bounds, though. In terms of novelty, it definitely borrows heavily from the SQ lower bound of DK21, but again it does require significant extra work and ideas.

Overall, I think this is a very good paper that makes a significant contribution to the area.
questions: - It would be helpful to understand why in the overall proof we end up _needing_ subexponential hardness of LWE. That is, why must the parameters in appendix D be set that way? What would fail if we tried to make do with say quasipolynomial hardness? My guess is that if we tried to set the PTF degree $d = O(t/\epsilon)$ to be say logarithmic in $n$, then OPT would be too large (something like $1/\mathrm{polylog}(N)$ maybe?), but I wonder if it would still at least be nontrivial. The reduction itself seems to only take $\mathrm{poly}(m, N)$ time, so that can't be the bottleneck. Some remarks on this would be useful right in the introduction. (Note that the comparison with known SQ bounds is a slightly different matter; the question is why the _proof in this paper_ requires the strong assumption.)
- A small typo in the statement of Thm 1.2: I think it should be $OPT \leq 2^{-\log^{1-\zeta}N}$.
limitations: The authors generally do a good job contextualizing their result and its limitations. A few further remarks on how the proof crucially uses subexponential hardness of LWE would not be out of place. I am not aware of any potential negative societal impact of this work.
review_title: null

final_score: 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.
review_content: summary: Learning halfspaces from samples with noisy labels is a classical problem in learning theory. In the Massart noise model with parameter eta, for some unknown halfspace f_w(x) = sign(<x,w>), the samples (x,y) are drawn as x ~ D (for some arbitrary unknown D) and y in {-1,1} such that Pr_{x ~ D}[f_w(x) = y] >= 1-eta. A recent sequence of works has shown how to learn (with polynomial time and sample complexity) a halfspace with error at most eta + eps. But in polynomial samples (with no time complexity restriction) it's possible to learn a halfspace with error at most OPT + eps, where OPT is the error of the best halfspace (it could be that OPT << eta). It remains open whether it's possible to do in polynomial time.

There is evidence via statistical query lower bounds suggesting that this goal is impossible. The current paper presents additional evidence, in the form of a conditional (but unrestricted) lower bound under the Learning With Errors assumption. Specifically, the main result of this paper is that if LWE cannot be solved in strongly subexponential time 2^{n^{1-Omega(1)}}, then no polynomial time learning algorithm can learn halfspaces with eta-Massart noise in polynomial time with error better than Omega(eta), even under the promise that OPT << eta (concretely, eta is constant and OPT < 2^{-log^{1-zeta}(n)} for constant zeta>0).
strengths_and_weaknesses: The contribution of this paper is original and of interest to the learning theory community. The paper is for the most part cleanly written, although there are a large number of parameters in the construction and perhaps more intuition could be given about them (e.g. Condition 3.1 and the main theorem). The overview of the prior SQ lower bound construction was particularly helpful, although a few parts were tricky to follow (specifically, the claims in lines 223-227). Lemma 3.3 also could use a bit more explanation (e.g. explaining in plaintext the sampling procedure for x'). The proofs are rather technical and I wasn't able to check them all, but the overview of the various obstacles and how they are overcome makes sense.

The only potential weakness is that this paper is strictly of interest to the learning theory segment of the NeurIPS community; also, while technical and certainly non-trivial I am not sure whether the proof techniques are of broader interest. Nonetheless, within learning theory the problem solved by this paper is of sufficient interest that I would recommend acceptance.
questions: line 54: should be 2^{-log^{1-zeta}(n)}?
line 224: why is this exp(-Omega(t^2/epsilon)^2)? Should it be exp(-Omega(t/epsilon)^2)?
line 312: D^{expand} is only defined in the appendix
line 313: there is no Fact A.5, I guess this should be Fact A.4?
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper provides cryptographic hardness results for the problem of learning halfspaces with Massart noise. The authors give a reduction of LWE to Massart halfspace learning and show that no polynomial time algorithm for Massart halfspaces can achieve error better than the one achieved by the existing algorithms. Prior to this work, there were only SQ lower bounds for this task.
strengths_and_weaknesses: The paper provides a cryptographic hardness result for the problem of learning Massart halfspaces. Such cryptographic hardness results have been recently obtained for various other learning tasks. Also, recent work has established hardness results for Massart halfspaces in the SQ model. The main result of this work is that, assuming the sub-exponential hardness of the LWE problem, there is no efficient learning algorithm for Massart halfspaces with error better than $\eta$ even if the optimal classifier can achieve much smaller error.

The paper is well-written and the result is quite clear. The technical contribution of the paper is a reduction from continuous LWE to Massart halfspaces. In general, this result is an interesting addition to the literature of robust supervised statistics.

I am in general positive towards acceptance; however, I would like to understand the importance of this hardness result, given the existing SQ lower bounds. 
questions: While I find the contribution nice, it is not clear to me how significant is such a hardness result given the existing SQ hardness results for the Massart halfspaces problem. Which algorithmic approaches that bypass the SQ lower bounds could be potentially used to efficiently tackle this task? Is it only Gaussian elimination and some LLL based algorithms?  
limitations: The authors address the limitations and propose future directions.
review_title: null

Meta-review: metareview: The paper studies the hardness of PAC learning halfspaces in the presence of Massart noise. Recent work showed that the problem is hard for all algorithms using only statistical queries (the SQ model). While this class contains most learning algorithms, it does not include powerful algorithmic techniques such as Gaussian elimination or certain lattice algorithms. The present work shows similar hardness result for all algorithms under the assumption that learning with errors (LWE) is hard for subexponential-time algorithms. All reviewers appreciate the hardness result on a central problem in learning theory. Some reviewers are slightly concerned that the subexponential-time hard assumption is quite strong but there are evidences linking the problem with other problems at the foundation of lattice-based cryptography and the assumption has also been used in several other previous works.
confidence: Certain
Decision: Accept