Cryptographic Hardness of Learning Halfspaces with Massart Noise
Authors: Ilias Diakonikolas
Daniel Kane
Pasin Manurangsi
Lisheng Ren
Venue: NeurIPS 2022 Accept (2022)
Keywords: learning theory
hardness of learning
halfspaces
Massart noise
Learning with Errors (LWE)

Abstract: We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i.i.d. labeled examples $(\mathbf{x}, y) \in \mathbb{R}^N \times \{ \pm 1\}$, where the distribution of $\mathbf{x}$ is arbitrary and the label $y$ is a Massart corruption of $f(\mathbf{x})$, for an unknown halfspace $f: \mathbb{R}^N \to \{ \pm 1\}$, with flipping probability $\eta(\mathbf{x}) \leq \eta < 1/2$. The goal of the learner is to compute a hypothesis with small 0-1 error. Our main result is the first computational hardness result for this learning problem. Specifically, assuming the (widely believed) subexponential-time hardness of the Learning with Errors (LWE) problem, we show that no polynomial-time Massart halfspace learner can achieve error better than $\Omega(\eta)$, even if the optimal 0-1 error is small, namely $\mathrm{OPT}  =  2^{-\log^{c} (N)}$ for any universal constant $c \in (0, 1)$. Prior work had provided qualitatively similar evidence of hardness in the Statistical Query model. Our computational hardness result essentially resolves the polynomial PAC learnability of Massart halfspaces, by showing that known efficient learning algorithms for the problem are nearly best possible.

Cryptographic Hardness of Learning Halfspaces with Massart Noise
Dlias Diakonikolas UW Madison iliasOcs. wisc. edu
Daniel M. Kane UC San-Diego dakanelucsd.c edu
Pasin Manurangsi Google Research pasinggoogle. com
Lisheng Ren UW Madison 1ren290visc, edu
Abstract
We study the complexity of PAC learning halfspaces the presence of Massart noise. In this problem, we are given i.i.d. labeled examples (x, E R x {+1}, where the distribution of x is arbitrary and the label y is a Massart corruption of fxx), for unknown halfspace
RN {+1}, with flipping probability n((x) S 7 < 1/2. The goal of the learner is to compute a hypothesis with small 0-1 error. Our main result is the first computational hardness result for this learning problem. Specifically, assuming the (widely believed) subexponential-in hardness of the Learning with Errors (LWE) problem, show that polynomial- time Massart halfspace learner can achieve error better than 2(1)), even if the optimal 0-1 error is small, namely OPT = 2 log" for any universal constant c E (0, 1). Prior work had provided qualitatively similar evidence of hardness in the Statistical Query model. Our computational hardness result essentially resolves the polynomial PAC learnability of Massart halfspaces, by showing that known efficient learning algorithms for the problem are nearly best possible.
Introduction
halfspace or linear threshold function (LTF) any function Aw.: RN - {+1} the form lxw.(x) : sign( (w, x) - 1), where the vector w R& is called the weight vector, / E R is called the threshold, and sign R - {+1} is defined by sign(() otherwise. Halfspaces are a central concept class machine learning, extensively investigated since the 1950s [Ros58 Nov62 MP68]. Here we study the computational complexity of learning halfspaces in Valiant's 's (distribution independent) PAC model [Va144, when the labels have been corrupted by Massart noise [MN06]. We define the Massart noise model below.
if / 2 O and sign(!) = -1
Definition 1.1 (Massart Noise). We say that joint distribution D of labeled examples (x, y). supported on R x {=1]. satisfies the Massart noise condition with noise parameter vi E [0, 1/2) with respect to concept class of Boolean--vlll valued functions on R if there is concept C such
that for all X E N we have that (x())
def Pr(xx))D(((()) + x = xo] < 1
The Massart PAC learning problem for the concept class is the following: Given i.i.d. samples from Massart distribution D, as in Definition [.I. the goal is to output a hypothesis with small 0-1 error. In this work, we study the computational complexity of the Massart PAC learning problem, when the underlying concept class C' is the class of halfspaces on N.
In its above form, the Massart noise model was defined in [MN66] An essentially equivalent noise model had been defined in the 80s by Sloan and Rivest [Slo88 RS94 Slo96), and a very similar definition had been considered even earlier by Vapnik [Vap82).
The Massart model a classical semi-random noise model that is more realistic than Random Classification Noise (RCN) In contrast RCN, Massart noise allows for variations misclassification
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

rates (without a priori knowledge of which inputs are more likely to be misclassified). Asymmetric misclassification rates arise in number of upplications, including human annotation noise [BK09] Consequently, learning algorithms that can tolerate Massart noise are less brittle than those that depend on the uniformity of RCN. The agnostic model [Hau92] KSS94), where the noise can be fully adversarial, is of course even more robust; unfortunately, it is computationally hard to obtain agnostic learners with any non-trivial guarantees, even for basic settings.
We now return to the class of halfspacce,, which is the focus of this work. We recall that PAC learning halfspaces with RCN is known to solvable in polynomial time (to any desired accuracy) [FFKV%) V96]. On the other hand, agnostic PAC learning of halfspaces is known to computationally hard (even for weak learning) [GR06 FGKP06 Da
The computational task of PAC learning halfspaces corrupted by Massart noise is a classi- cal problem in machine learning theory that has been posed by several authors since the 1980s [Sl088] Coh97 [lu03]. Until recently, no progress had been made on the efficient PAC learn- ability of Massart halfspaces. (DGTI9) made the first algorithmic progress on this problem: they gave a poly(N, 1/e)-time learning algorithm with error guarantee of 1j +.. Subsequent work made a num- ber of refinements to this algorithmic result, including giving an efficient proper learner [CMM220 and developing an efficient learner with strongly polynomial sample complexity [KT21 In a related direction, [DIK* + 21] gave an efficient boosting algorithm achieving error rj + for any concept class, assuming the existence of a weak learner for the class.
The error bound of 7) can be very far from the information-theorriialll -heoretically optimum error of OPT, where OPT = RLTF(D) (D) S v). Indeed, known polynomial-timg -time algorithms only guarantee error x even if OPT is very small, i.e., OPT < n.. This prompts the following question:
Question 1.1. Is there efficient learning algorithm for Massart halfspaces with relative error guarantee? Specifically, if OPT < &1 is it possible to achieve error significantly better than n??
Our main result (Theorem 1.2p
answers this question in the negative, assuming the subexponential- time hardness of the classical Learning with Errors (LWE) problem (sssumption2..4 In other words, we essentially resolve the efficient PAC learnability of Massart halfspaces, under a widely-believed cryptographic assumption.
1.1
Our Results
Before we state our main result, we recall the setup of the Learning with Errors (LWE) problem. In the LWE problem, we are given samples (x1, 8/1 ,.... (xm= Dm) and the goal is to distinguish between the following two cases: (i) Each x; drawn uniformly at random (u.a.r.) from Zū. and there a hidden secret vector s E Z such that y/: (x, s) + 22, where 2; E Zy is discrete Gaussian noise (independent of x,); (ii) Each x; and each y/1 are independent and are sampled u.a.r. from ž and Zn respectively. Formal definitions of LWE (Definition 2.3) and related distributions together with the precise computational hardness assumption (Assumption 2.4h we rely on are given in Section 2
Our main result can now be stated follows:
Theorem 1.2 (Informal Main Theorem). Assume that LWE cannot be solved in 2n 220))() time. Then, for any constant Ç > 0, there is no polynomial-time learning algorithm for Massart halfspaces on RN that can output hypothesis with 0-1 error smaller than M(1)), even when OPT 2 log'-5 N and the Massart noise parameter 1j a small positive constant.
The reader is also referred to Theorem D.I in the Appendix for more detailed formal statement. Theorem 1.2 is the first computational hardness result for PAC learning halfspaces (and, in fact, any triviaivial concept class) in the presence of Massart noise. Our result rules out even improper PAC learning, where the learner is allowed to output any polynomially evaluatable hypothesis. As a corollary, it follows that the algorithm given in [DGT19] is essentially the best possible, even when assuming that OPT is almost inverse polynomially small (in the dimension N). We also remark that this latter assumption is also nearly the best possible: if OPT is o(c/N), then we can just draw ((N/c) samples and output any halfspace that agrees with these samples.
We note that line of work has established qualitatively similar hardness in the Statistical Query (SQ) model [Kea98] - a natural, yet restricted, model of computation. Specifically, [CKMY20) established super-polynomial SQ lower bound for learning within error of OPT + o(1). Subse-

---

quently, [DK22 gave near- mear-optimal super- Soper-polynomialS SQ lower bound: their result rules out the existence of efficient SQ algorithms that achieve error better than (2))), even if OPT = 2 N Building on the techniques of [K22], more recent work [NT22 established an SQ lower bound for learning to error better than 7) even if OPT = 2log' N matching the guarantees of known algorithms exactly. While the SQ model is quite broad, it also restricted. That is, the aforemen- tioned prior results do not have any implications for the class of all polynomial-time algorithms. Interestingly, as we will explain in the proceeding discussion, our computational hardness reduction is inspired by the SQ-hard instances constructed in [K22]]
1.2 Brief Technical Overview
Here give high-level overview of our approach. Our reduction proceeds in two steps. The first is to reduce the standard LWE problem (as described above) to a different "continuous" LWE problem more suitable for our purposes. In particular, we consider the problem where the x samples are taken is either taken to be an independent random element of R/Z or is taken
uniformly from IR" IR"/"" /2", , to be (x, s) mod plus a small amount of (continuous) Gaussian noise, where s is some unknown vector in {=1 This reduction follows from existing techniques [Mie 18a GVV22).
The second step which is the main technical contribution of our work - is reducing this continuous LWE problem to that of learning halfspaces with Massart noise. The basic idea is to perform a rejection sampling procedure that allows us to take LWE samples (x, y) and produce some new samples (x, 7). We will do this so that if y is independent of x, then ÿ is (nearly) independent of x; but if y (x, s) + noise, then ÿ is halfspace of x with a small amount of Massart noise. An algorithm capable of learning halfspaces with Massart noise (with appropriate parameters) would be able to distinguish these cases by learning hypothesis h and then looking at the probability that ((x) f y. In the case where ý was a halfspace with noise, this would necessarily be small; but in the case where and ğ were independent, it could not be.
In order to manage this reduction, we will attempt to produce a distribution (x, 5) similar to the SQ-hard instances of Massart halfspaces constructed in (KK22. These instances can best be thought of as instances of a random variable (x', y') in R" X {+1}, where y' is given by a low-degree polynomial threshold function (PTF) of x' with small amount of Massart noise. Then, letting x be the Veronese map applicd to x', we see that any low-degree polynomial in x' is a linear function of x, and y/ is LTF of x plus small amount of Massart noise.
As for how the distribution over (x', v/) is constructed in [K22]] essentially the conditional dis- tribution of x' on y' and on y' = -1 are carefully chosen mixtures of discrete Gaussians in the v-direction (for some randomly chosen unit vector v), and independent standard Gaussians in the orthogonal directions. O Our goal will be to find a way to perform rejection sampling on the distribution (x,y) to produce a distribution of this form.
In pursuit of this, for some small real number b and some a E [0, b), we let x' be random Gaussian subject x' = bx (mod 6) (in the coordinate-wise sense) conditioned on by = a (mod 6). We note that if we ignore the noise in the definition of y. this implies that (x', .) = (bx, s) = b (x. s) = by = (mod b) (recalling that E {=1)") In fact, it is not hard to see that the resulting distribution on x' is close to a standard Gaussian conditioned on (x' s) a discrete Gaussian with spacing b/||s||2 and offset a/ l||s||| in the s-direction, and an independent standard Gaussian in orthogonal directions. Furthermore, this x' can be obtained from (x, v) samples by rejection sampling: taking many samples until one is found with by = a (mod b), and then returning random x' with x' = bx (mod b). By taking an appropriate mixture of these distributions, we can manufacture a distribution close to the hard instances in [DK22]. This intuition is explained in detail in Section 3.1. see Lemma 3.3 (We note that Lemma 3.3 is included only for the purposes of intuition; it is a simpler version of Lemma 3.5 which is one of the main lemmas used to prove our main theorem.)
(mod b). In other words, x' is close to
Unfortunately, as will be discussed in Section 3.2 applying this construction directly does not quite work. This is because the small noise in the definition of y leads to a small amount of noise in the final values of s). This gives us distributions that are fairly similar to the hard instances of [DK22), but leads to small regions of values for u, where the following condition holds:
Pr(y' = +1 x' u) = -1 x' = u). Unfortunately, the latter condition cannot hold y' is function of x' with Massart noise. In order to fix this issue, we need to modify the construction
3

---

by carving intervals out of the support of x' conditioned on 3 -1, in order to eliminate these mixed regions. This procedure is discussed in detail in Section 3.3.2
1.3 Additional Related Work
There have also been several recent works showing reductions from LWE or lattice problems to other learning problems. Concurrent and independent work ours (Tie22] showed hardness of weakly agnostically learning halfspaces, based on a worst-case lattice problem (via a reduction from "continuous" LWE). Two recent works obtained hardness for the unsupervised problem of learning mixtures of Gaussians (GMMs), assuming hardness of (variants of) the LWE problem. Specifically, [BRST2I] defined a continuous version of LWE (whose hardness they established) and reduced it to the problem of learning GMMs. More recently, [GVV22] obtained a direct reduction from LWE to a (different) continuous version of LWE; and leveraged this connection to obtain quantitatively stronger hardness for learning GMMs. It is worth noting that for the purposes of our reduction, we require as a starting point continuous version of LWE that differs from the one defined in [BRST2I] Specifically, we require that the distribution on is uniform on [0, 1Jmh (instead of Gaussian, as in (BRST2() and the secret vector is binary. The hardness of this continuous version essentially follows from [Mie 18h GVV22
2 Preliminaries
For x, E IR with s + xet def (x, s)/[|||[2 be the length of the projection of x in the direction, and x E RR-1 be the projection of the orthogonal complement of For f.g U - R, we write f(uu) x g(u) if there is c E IR such that f(u) = cg(u) for all u E U. We use X ~ D to denote random variable X with distribution D. We use PD Px for the corresponding probability mass function (pmf) or density function (pdf), and Pro or Prx for the measure function of the distribution. We use Dx denote the distribution of the random variable X. For S C R", we will use X(S) to denote the n--dimensional volume of S. Let US) denote the uniform distribution on S. For distribution D on R" and S S. R". we denote by D S the conditional distribution of X D given X S. Let D (resp. D-1S) be the distribution of x (resp. x-*), where D. For distributions D1. D2, we use D1 + D2 to denote the prruuddddisributtion with measure function +rD (A) Pr (A) + PrD, (A). For
IR let D denote the pseudo-distribution with measure function aPrp. On the other hand, let a o D denote the distribution of axx, where X ~ D.
We use D1 * D2 to denote the convolution of distributions D1, D2.
We will use LTFN N for the class of halfspaces on RN; when N is clear from the context, we may discard it and simply write LTF. For q E N. we use Z, def {0, 1..... :9 - 1} and I., def [0, q). We use mody: R² + Ry to denote the function that applies mody(x) on each coordinate of x.
We use DV to denote the n-dimensional Gaussian distribution with mean 0 and covariance matrix o² d2/(27) I, and use DAY as short hand for DAY In some cases, will use (O In) for the standard (i.e., zero mean and identity covariance) multivariate Gaussian,
Definition 2.1 (Partially Supported Gaussian Distribution). For a E R4 and x E R", let (x( def o o""eep (~>((x[|2/o))). For any countable set S C I","" we let (S) def Exes Po (x), and let Dy, be the distribution supported on S with pmf Ppy. (x) = Po (S)
y E IR and E R4, we define the "T-spaced, Definition 2.2 (Discrete Gaussian). For T E R4,y
g-offset discrete Gaussian distribution with a scale" to be the distribution of Diz
We use the following definition of LWE, which allows for flexible distributions of samples, secrets, and noises. Here is the number of samples, is the dimension, and is the ring size.
Learning with Errors (LWE)
Definition 2.3 (Generic LWE). Let m. n, E N. and let Deample: Descret. Dnoise be distributions on (noise,mo,,) mod,) problem, we are given m independent samples (x, y) and want to distinguish between the following two cases: (i) Alternative
R" R", R. respectively. In the LWE(m, D Dsample: Dsperet Dnoise,
Mooe precisely, let B1s E (=)(n-)) for the matrix whose columns form an (arbitrary) orthonormal basis for the orthogonal complement sf's and Ls def
(B1+)*x x.

---

hypothesis: s is drawn from D Deecret. Then, each sample is generated by taking x ~ Dauplee 2 ~o D Dosise and letting y = mod, s) + 2): and (ii) Null hypothesis: x, y are independent and each has the same marginal distribution as above.
When a distribution in LWE is uniform over some set S. we may abbreviate U(S) merely as S. Note that LWE(m, Zn 2n D modg) to the classical LWE problem.
Computational Hardness Assumption for LWE As alluded to earlier, the assumption for our hardness result the hardness of the (classic) LWE problem, with the parameters stated below.
Assumption 2.4 (Standard LWE Assumption (see, e.g., (PII)). Let 0 be sufficiently large constant. For any constant (0, 1). x E N. LWE(20(n") Bn 2g. DW. mod,) with q S n² and cvn cannot be solved in 20(nP) time with 2 -(n²) advantage.
We recall that [Reg09] Pei0g
gave a polynomial-ting quantum reduction from approximating (the decision version of) the Shortest Vector Problem (GapSVP) to LWE (with similar n. q. a parameters). Our hardness assumption is the widely believed sub-exponential hardness of LWE. We note that the fastest known algorithm for GapSVP takes 20(x) time [ALNS20], Thus, refuting the conjecture would be major breakthrough. A similar assumption was also used in [GVV22] establish computational hardness of learning Gaussian mixtures. Our use of a sub-exponential hardness of LWE is not coincidence; see Section
As mentioned earlier, we will use a different variant of LWE, where the sample is from RE, the secret from [+1]", and the noise is drawn from continuous Gaussian distribution. The hardness of this variant is stated below. The proof, which follows from [Mic MicI8al GVV22), is deferred to Appendix B
Lemma 2.5. Under Assumption
2.4 for any 3 (0,1) and y E R4, there is no 20(n²) time algorithm to solve LWE (2((n)) RT. [=1]", Do(n->> modd with 2-0(m²) advantage.
Decisional Massart Halfspace Problem For distribution D on labeled examples and concept
class C, we let Re(DD def minsec (r(x.))-. (h(x) * y] be the error of the best classifier C with respect D. We will prove hardness for the following decision version of learning Massart halfspaces. This will directly imply hardness for the corresponding learning (search) problem.
Definition 2.6 (Testing Halfspaces with Massart Noise). For n, N E N. 7,, OPT E (0, 12) let Massart(m, NN r7, OPT) denote the problem of distinguishing, given i.i.d. samples from D on RN x x [=1]. 1. between the following two cases: (i) Alternative hypothesis: D satisfies the Massart halfspace condition with noise parameter and RETF (D) < OPT; and (ii) Null hypothesis: the Bayes optimal classifier has on error, where e > 0 a sufficiently small universal constant.
3 Reduction from LWE to Learning Massart Halfspaces
In this section, we establish Theorem 1.2
Some intermediate technical lemmas have been deferred
to the Appendix C Our starting point is the problem LWE(m, RT. ( . modd). Note that, by Lemma 2.5 Assumption 2.4mimplies the hardness of LWE(m, RT, [#1}", D. modz). , We will
DD
reduce this variant of LWE to the decision/testing version of Massart halfspaces (Definition 2.6p.
Our reduction will employ multiple underlying parameters, which are required to satisfy set of conditions. For convenience, we list these conditions below.
Condition 3.1. Let n, m. m' E N, I,e, R 8 E (0, 1), satisfy: (i) l/e is a sufficiently large even integer, (ii) σ S Vū, (ii) 1 (iv) de log(m'/0)) where c' > 0 is sufficentlly small universal constant and c" 0 is sufficiently large universal constant.
Wa 2 Vclog(n/8), where is sufficiently large universal constant,
The main theorem of this work is stated below.
Theorem 3.2. Let n. m. m' N, t, o R., 6,6 8 E (0, satisfy Condition 3.1 and 1/2. Moreover, assume that m' = c(e/t)m, where c > 0 is sufficiently small universal constant and m/</t)" sufficiently large, and N = (n + 1)d, where d/(t/e) is sufficiently large. Suppose that there is no T (m N, (log(1)))--tin)) algorithm for solving LWE(m, R2 [+1}". D. modj)
5

---

with c' - 0() advantage. Then there is no T time algorithm for solving Massart(m', ,N, NN,,, OPT) with 2e' advantage, where OPT = e )e2)).
Note that Theorem 3.2, combined with Lemma 2.5 can be easily used to prove Theorem 1.2 (, by plugging in t n (00) , O( 155) in the above statement); see Appendix D As such, we devote the remainder of the body of this paper to give an overview to the proof of T Theorem 3.2
High-level Overview The starting point of our computational hardness reduction is the family of SQ-hard instances obtained in [DK22]. At high-level, these instances are constructed using mixtures of "hidden direction" " discrete Gaussian distributions, i.e., distributions that are discrete Gaussians in hidden direction and continuous Gaussians on the orthogonal directions.
we note that by using an appropriate rejection sampling procedure on the LWE samples (drawn from the alternative hypothesis), we obtain a distribution very similar to the "hidden direction discrete Gaussian". A crucial difference in our setting is the existence of a small amount of additional "noise". A natural attempt is to replace the discrete Gaussians in [DK22] with the noisy ones obtained from our rejection sampling procedure. This produces problems similar to the hard instances from [D22 Unfortunately, the extra noise in our construction means that the naive version of this construction will not work; even with small amounts of noise, the resulting distributions will nor satisfy the assumptions of PTF with Massart noise. In Section 3.2, we elaborate on this issue and the modifications we need to make to our construction in order to overcome it. In Section 3.3 we provide the complete construction of our Massart PTF hard instance.
In Section 3.1
Overview of the [DK22] SQ-hard Construction [DK22] showed SQ-hardness for the following
hypothesis testing version of the problem (which implies hardness for the learning problem): For an input distribution D on TR" x {+1), distiguussh between the cases where D is a specific distribution Daull in which x and y are independent or where D) belongs to class of alternative hypothesis distributions Dalternative- In particular, for D E Dalternative. y will be given by a low-degree PTF in with small amount of Massart noise. As we will be trying reproduce it, it is important for us to understand this alternative hypothesis distribution. Each distribution in Dalternative is parameterized by hidden direction s S We will denote the corresponding distribution by Dz. D3 is constructed so that x x ~ DV - is independent of x and y. This means that we can specify D. by describing the simpler distribution of (x*, y) E R x [+.]. For (x*, we have that y = +1 with probability 77. The distributions of x conditioned on y = =1 are defined to be mixtures of discrete Gaussians as follows:
Dx (x=((==1) - 1/-
1 D.V Di- du and Dx*( c x/22
1/24c
DW ut(l+u-1/222,1 du
(1)
As we noted, both x" (y= +1) and x* | (y -1) are mixtures of discrete Gaussians. Combining
this with the fact that x-s NN,,,,, In),,, this indicates that x (y = +1) and (y = 1)
mixtures of "hidden direction discrete Gaussians" support on the hidden direction. These conditional distributions were carefully selected to ensure that y is Massart PTF of with small error. To see why this is, notice that the support of x* (y +1) is lit, it + (i +i++1) 1)e), while the support of x* (y = 11) is [iit= + t/2, it + 1/2 + (i + 1)e]: both iEZ
with different spacing and offiset for their
iE?
supports are unions of intervals. Consider the implications of this for three different ranges of x5:
1. For x* [- /2 (2e)]. the intervals have lengths in [0, t/2]: thus, the +1 intervals and the -1 intervals do not overlap at all.
2. For x E [- - / (2c)) U (22((2), t2/c], the intervals have lengths in It/2,t]: thus, the +1 intervals and the -1 intervals overlap, that their union covers the space. We note that in this
case there are gaps between the +1 intervals; specifically, there are at most (tt/c) such gaps.
3. For E (- -22 u ((feee,,e 20), the intervals have lengths in [t, 20), the +1 intervals cover the space by themselves.
Consider the degree-O PTF sign((()) such that (ign(p(x)) = +1 x e lit, it (i+ 1)c].
3E?
In particular, sign(p(x)) = 1 for x in the support of the conditional distribution on y = 1. Note that the PTF sign(p(x)) has zero error the first case; thus, its total 0-1 error is at most exp (()))))))))))) Moreover, since the probability of y 1 is substantially larger than the probability of y = -1, it not hard to see that for any x with (ign((()) = that Prly = 1 | x = x) > 0(r). This implies that y is given by sign(p(z)) with Massart noise On)).

---

3.1 Basic Rejection Sampling Procedure
In this subsection, we show that by performing rejection sampling on LWE samples, one can obtain a distribution similar the "hidden direction discrete Gaussian". For the sake of intuition, we start with the following simple lemma. The lemma essentially states that, doing rejection sampling on LWE samples, gives distribution with the following properties: On the hidden direction s, the distribution is pointwise close to the convolutional sum of a discrete Gaussian and a continuous Gaussian noise. Moreover, on all the other directions 1 S, the distribution nearly independent of its value on s, in the sense that conditioning on any value on 8, the distribution on 1 s stays pointwise close to Gaussian. Note that this distribution closely resembles the "hidden direction discrete Gaussian" in [DK22].
Lemma 3.3. Let (x.y) be a sample of the LWE(m, Ri, [+1)", D. .mod,) ) from the alternativ hypothesis case, let letyy be any constant in [0,1), and let ~ (1/Oscale) Dx+
x+32 Jssale (y = y') Then we have the following: (i) For x"x, we have that for any u E IR it holds that Px (u) =
(1=
PD Duoise (u) where D' = =D (w'+22)
and = SR/(n' (12 Osignal = VR,
T Juoise = vI SR, and SR- Faaso +027n (ii) x < is "nearly independent" of x"" namely for any 1 E and u E R=-1 we have that Px xxxxx== xx)xx=((1)) = (1 + ((5)) pp..,,, (n)
Lemma 3.3 is a special case of Lemma 3.5 which is one of the main lemmas required for our proof. We note that the distribution of x' obtained from the above rejection sampling is very similar to the "hidden direction discrete Gaussian" used in [DK22). The key differences are as follows: (i) on the hidden direction, x is close to a discrete Gaussian plus extra Gaussian noise (instead of simply being discrete Gaussian), (ii) x and x are not perfectly independent. More importantly, by taking different values for y' and Tscale. we can obtain distributions with the same hidden direction, but their discrete Gaussian on the hidden direction has different spacing (T) and offset (y').
To obtain a computational hardness reduction, our goal will be to simulate the instances from [DK22 by replacing the hidden direction discrete Gaussians with the noisy versions that we obtain from this rejection sampling. We next discuss this procedure and see why naive implementation of it does not produce a PTF with Massart noise.
3.2 Intuition for the Hard Instance
The natural thing try is simulate the conditional distributions from (DK22) by replacing the hidden direction discrete Gaussian terms in ① with similar distributions obtained from rejection sampling. In particular, Lemma 3.3 says that we can obtain a distribution which is close this hidden direction Gaussian plus a small amount of Gaussian noise. Unfortumately, this extra noise will cause problems for our construction.
Recall that the support of x (y=+1) was U it + (i + (1c)) and the support of x | (y = 1)
1E2
was U + 4/2, 4/2 - (i + 1)c] for DK22
With the extra noise, there is a decaying density
.EZ" tail in both sides of each jtt, it + (i + D) interval in the support of x (y = +1). The same holds for each interval in the support of x* (y = (1). Recalling the three cases of these intervals
discussed earlier, this leads to the following issue. In the second case, the intervals have length within [1/2, I): thus, the intervals (it, il + (i + 1)e] and (it + +/22, il + 1/2 + (i 4
1)e] overlap, i.e.,
il + (i + 1)e 2 il + 1/2. On the right side of [i1, il + (i + 1)c]. in the support of x (y -1), there is a small region of values for u, where Priy/ = +1| x* = u] = Priy' = = x = u].
This causes the labels y +1 and y -1 to be equally likely over that small region, violating the Massart condition. (We note that for the first case, there is also this kind of small region that
Prly' = +1 x* u| Prly'" -1 x* = uj caused by the noise tail. However, the probability density of this region is negligibly small, as we will later see in Lemma 3.9
We can address this by carving out empty spaces in the |it + t/2, it + t/2 + (i 1)c] intervals for x3 (1 - 1), so that these decaying parts can fit into. Since this only needs to be done for intervals of Case 2 at most O(1/e) many such slots are needed. It should be noted that no finite slot will totally prevent this from occurring. However, we only need the slot to be wide enough so that the decay of the error implies that there is negligible mass in the overlap (which can be treated an error).
7

---

We also need to discuss another technical detail. In the last section, we defined the rejection sampling process taking (1/Oscale) DV
(y 1/', where we can control the offiet by y and spacing by sscale (Lemma 3.3) This distribution is effectively noisy version of discrete Gaussian. Therefore, we can produce a noisy version of the hard instances of [DK22 by taking a mixture of these noisy discrete Gaussians. Unfortunately the noise rate of one of these instances will be noise- This quantity depends on the spacing of the discrete Gaussian, which varies across the mixture we would like to take. This inconsistent noise rate is inconvenient for our analysis. However, we can fix the issue by adding extra noise artificially to each of the discrete Gaussians in our mixture, so that they will all have uniform noise rate noise: Algorithm [ and Lemma 3.5
x+22 deople
The last bit of technical detail that instead of doing the rejection for y v/. which has 0 acceptance probability, we will only reject if is not corresponding to any discrete Gaussian we need. Then we do another rejection to make sure that the magnitude discrete Gaussians the mixture correct. In the next subsection, we introduce the complete rejection sampling method.
3.3 The Full Hard Instance Construction
We first introduce the complete rejection algorithm, and then explain how the hard instance is produced using it. Below we provide proof overviews; omitted proofs can be found in Appendix C
3.3.1 The Complete Rejection Algorithm
The rejection sampling algorithm is the following. The sampling process produces the noisy variant of the distribution which, for some carefully selected set B S [0.1]. has PDF function 2
X(B SB D.N k+(t+k-0)z,1 dk in the hidden direction, we will see in Lemma 3.5
Algorithm 1 Rejection Sampling Algorithm
Inputs: A sample (x, y) RT R and the input parameters L, e, R2 where th + I B S [.. ab + ec. 8 E (0, 1). In addition, the parameters satisfy items (i)-(ii) of Condition 3.1 Output: REJECT or a sample x' E=.
1. Reject unless there is a k E B such that y 24
2. Furthermore, reject with probability
(++k-v)²
3. Let SR = 1 - 4(l + e)2o², Oscale
SR [e+k (1+k-v)vn and aadd V D2",aw Faad and output x' ~ (1/Oscate) o D.N' x+ xadd + 2n Facale"
[1 (1-SR)o2
Sit/a/ vny Then, SR
sample independent noise Xadd ~ D
Notice that the parameter SR does not depend on y, whereas Oscales andd do depend on y- For convenience, let us use the following notation for the output distributions.
Dalternative be the distributions of Definition 3.4 (Output Distribution of Rejection Sampling). Let Delter B,S
x' produced by Algorithm 1 (conditioned that the algorithm accepts) given that (x, y) are sampled follows: let x (RRT.. ) D.Y. and then let y modı ((x, s) + 2). where secret. Furthermore, let Dmull B,, be similar distribution, but when x ~ U (RR)), y (RR) are independent.
[=1]" 3 is the
Note that Dalteruative depends on s, but we do not explicitly denote this in our notation.
Alternative Hypothesis Analysis The main properties of Dalternative are summarized in the following lemma. Essentially, the lemma states that for this distribution Dt,,,t,,,5 B,,6 the marginal distribution the hidden direction is pointwise close to the convolution sum of D' and Gaussian noise, where D' is a linear combination of discrete Gaussians. Moreover, on all the other directions 1 s. the distribution is nearly independent of its value s, in the sense that conditioning any value on s. the distribution on 1 always stays pointwise close to a Gaussian.
Lemma 3.5. Let x'
Dalternative
L. Then we have the following: (i) For x!5, we have that for
any u E R. (x) = (1 PD Enoise
(2) where D' A[B JB DN (tt(t*k-))2.0ngu dk
8

---

dsignal V and noise -R = 2(t + e)o. (SR is defined in Algorithm 1 (ii) x' is "nearly independent" of x²; namely, for any I E IR and u E IR--1, we have that Px "|x'==((u) (1 P DN uu)
Null Hypothesis Analysis For D B.8. we can show that it is pointwise close to DR Lemma 3.6. For any u E R", have that P
(u) (1 ((6)) (u).
3.3.2 The Reduction Algorithm
With the rejection sampling algorithm (Algorithm T at our disposal, we can now give the full construction of the hard instance. We use Dr.c. 1,,,,,,,111 for y = +1, Dt,aa , for x -] (with a carefully chosen pair of 1B+.14+ and (B_, w))), as we discussed in Section 3.2 and take a proper marginal distribution of to build a joint distribution of (x, y)- We introduce reduction algorithm that, given samples from our LWE problem (either from the null or the alternative hypothesis), produces i.idd. samples (x, y) from joint distribution with the following properties:
If the input LWE problem the null hypothesis, then x y +1 and x y = -1 are close in total variation distance. Therefore, no hypothesis for predicting in terms of x can do much better than the best constant hypothesis.
2. If the input LWE problem is the alternative hypothesis, then the joint distribution of (x, build close to a distribution D) that satisfies O(1) Massart condition with respect to (etree-O(t/e) PTF, and there is a detree-O(t/e) PTF with small error on D.
We formalize the idea from Section 3.2 here. For x y +1, we will use t/4 def 0 and B+ def 60,
For x = 11 we take v!_ def t/2, which is also the same as [K22]: : but instead of taking
1t/2,t/2+ c). we will need to carve out the slots on B_. First, we define the mapping g R- [-1.5%, 0.5(] + [0.5l, 4J as follows: for i E Z and b E R,, we have that
B
def
g(il + (122+1/2+0 +2) def
t/2
if 2
t/2
if <.
This function maps a location it + t/2 + b to the corresponding place need carve out on B_, which is defined in Algorithm These intervals are chosen so that the decaying density part of +1
can fit in, we discussed in Section 3.2 Now we introduce the algorithm that reduces LWE to learning Massart PTFs.
We similarly define the output distributions of the algorithms in the two cases as follows: Definition 3.7. Let DPTF Dalternative be mixture Dalternative 2.e,0 ,B,6 and Dalternative with +1 and -1 labels
and weights 1 and 1) respectively. Similarly, let Dpull be mixture of D L... and D D,r,0i B
with 11 and -1 labels and weights 17 and v respectively.
The following observation is immediate from the algorithm.
Observation 3.8. In the alternative (resp. null) hypothesis case, the output distribution of Algorithm conditioned on not failing, the same as m' ii.d. samples drawn from Drre
Dalternative (resp. D
Alternative Hypothesis Analysis We prove that there exists a (tgree-O(t/e) PTF such that Delternative is close to (in total variation distance) satisfying the (1)) Massart noise condition with respect to this PTF, and this PTF has small error with respect to Daltermative
Lemma 3.9. D is O(5/m') close in total variation distance to a distribution Dtruncated such that there is d(gree-O(t/e) PTF sign(p(xx) that: (i) E( (xx) # y] < (ap(-(((9)))) (ii) Diruncated satisfies the O(1) Massart noise condition with respect sign(p(x)).
Null Hypothesis Analysis The reader referred to Lemma C.8 in Appendix for the null hypothesis analysis.

---

Algorithm/ 2 Reducing LWE to Learning PTFs with Massart Noise
Inputs: mn samples from an instance of LWE(m, R7, (=1)", ,No,, modi). The input parameters
m' E N, f. E Ryg. 8 E (0, 1), and > 0 sufficiently small value. In addition, the parameters satisfy Condition 3.1
Output: m' many samples in R } or FAIL.
1. We take // = 0, B+ = [0, 1/ 1/2 and
1-1
B_ = t/2,t/2
U
g(lit 2de,
U -=
g + (i + 1), (i+ 1)e 2c'e))
-
glit + (i+ 1)c 2d', (i ( 1)c)
g(itt it 2ccc)
2. Repeat the following m' times. If at any point the algorithm attempts to use than LWE samples from the input, then output FAIL.
(a) With probability 1 - 7/ repeat the following until Algorithm accepts and output x': run Algorithm D with the next unused LWE sample from the input and parameters t, 4 B B+, 5. Add (x',+1) to the output samples.
(b) With probability y, repeat the following until Algorithm accepts and output x': run
Algorithm| [ with the next unused LWE sample from the input and parameters e,
B. B = ò_, -B, Add (x', to the output samples.
Putting Everything Together Having reduced LWE to learning Massart PTFs, we can apply Veronese mapping on the samples; this PTF becomes an LTF on the Veronese mapping. Since use degree-O(t/e) Veronese mapping, the dimension for the Massart LTF problem is N (n + 1)0())))
4
Discussion
Our result rules out the existence of polynomial time algorithms achieving error smaller than P(1)). where 77 the upper bound on the noise rate, even of the optimal error is very small, assuming the subexponential time hardness of LWE. A technical open question is whether the constant factor in the (2(r)-temm of our lower bound can be improved the value C' 1; this would match known algorithms exactly. (As mentioned in the introduction, such sharp lower bound has been recently established in the SQ model [NT22), improving on (DK22.)
It is also worth noting that our reduction rules out polynomial-time algorithms, but does not rule out, e.g., subexponential even quasipolynomial time algorithms with improved error guarantees. We believe that obtaining stronger hardness for these problems would require substantially new ideas, our runtime lower bounds essentially the same the best time lower bounds for learning in the (much stronger) agnostic noise model or in restricted models of computation (like SQ). This seems related the requirement that our bounds require subexponential hardness of LWE in our assumption. As the strongest possible assumptions only allow us to prove quasi-polynomin lower bounds, any substantially weaker assumption will likely fail to prove super-po aoper-polynomial ones.
Acknowledgments
Ilias Diakonikolas was supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CAREER), Sloan Research Fellowship, and a DARPA Learning with Less Labels (LwLL) grant. Daniel M. Kane was supported by NSF Medium Award CCF-2107547, NSF Award CCF- (CAREER), a Sloan Research Fellowship. and a grant from Casperl Labs. Lisheng Ren was supported by NSF Award CCF- CCF-1652862 (CAREER) and DARPA Learning with Less Labels (LwLL) grant.
10

---

References
[ALNS20]
Aggarwal, Li, Q. Nguyen, and N. Heephess-avidowwe Slide reduction, revisited filling the gaps in SVP approximation. In Advances in Cryptology CRYPTO 2020- 40th Annual International Cryptology Conference, CRYPTO 2020, volume 12171 of Lecture Notes in Computer Science, pages 274-295. Springer, 2020.
[BFKV96]
A. Blum, A. M. Frieze, R. Kannan, and S. Vempala. A polynomial soaynomial-iimeeeeee algorithm for learning noisy linear threshold functions. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, pages 330-338, 1996.
[BK09]
E. Beigman and B. B. Klebanov. Learning with annotation noise. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 280-287, 2009.
[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.
[BRST21] J. Bruna, O. Regev, J. Song, and Y. Tang. Continuous LWE. In S7OC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 694-707. ACM, 2021.
[CKMY20] S. Chen, F. Koehler, A. Moitra, and M. Yau. Classification under misspecifica- tion: Halfspaces, generalized linear models, and connections to evolvability. CoRR, abs/2006.04787, 2020. Appeared in NeurlPS'20 20.
[Coh97] E. Cohen. Learning noisy perceptrons by perceptron polynomial time. Pro- ceedings of the Thirty-Eighth Symposium on Foundations of Computer Science, pages 514-521, 1997.
[Dan16]
A. Daniely. Complexity theoretic limitations on learning halfspaces. In Proceedings of the 48th Annual Symposium Theory of Computing, STOC 2016, pages 105-117, 2016.
[DGTI9]
I. Diakonikolas, T. Gouleakis, and C. Tzamos. Distributior-indeeenden PAC learning of halfspaces with massart noise. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Bue, Emily Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pages 4751 4751-4762, 2019.
[DIK+21] I. Diakonikolas, R. Impagliazzo, D. M. Kane, R. Lei, Sorrell, and C. T7amo. Boosting in the presence of massart noise. In Conference on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Research, pages 1585-1644. PMLR, 2021.
[DK22]
I. Diakonikolas and D. M. Kane. Near-optimal statistical query hardness of learning halfspaces with massart noise. In Conference on Learning Theory, COLT 2022, volume 178 of Proceedings of Machine Learning Research, pages 4258 4258-4282, PMLR, 2022. Full version available at
[DKT21]
I. Diakonikolas, D. Kane, and C. Tzamos. Forster decomposition and learning halfs- paces with noise, In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pages 7732-7744, 2021.
[FGKP06]
V. Feldman, Gopalan, Khot, and A. Ponnuswami. New results for learning noisy parities and halfspaces. In Proc. FOCS, pages 563-576, 2006.
[GR06]
V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise. In FOCS 2006, pages 543-552, IEEE Computer Society, 2006.
[GVV22]
A. Gupte, N. Vafa, and V. Vaikuntanathan. Continuous Iwe is hard as Iwe & applica- tions to learning gaussian mixtures. arXiv preprini arXiv:2204.00 02550, 2022.
[Hau92]
D. Haussler. Decision theoretic generalizations of the PAC model for neural net and
other learning applications. Information and Computation, 100:78-150, 1992.
[Kaa98]
M. J. Kearns. Efficient noisc-tolerant learning from statistical queries. Journal of the ACM, 45(6):983-1006, 1998.
[KSS94]
M. Kearns, R. Schapire, and I.. Sellie. Toward Efficient Agnostic Learning. Machine Learning, 1752/)) 1994.

---

[LP11]
R. Lindner and C. Peikert. Better key sizes (and attacks) for lwe-based encryption. In Cryptographers' Track the RSA Conference, pages 319-339. Springer, 2011.
[MG02]
D. Micciancio and S. Goldwasser. Complexity of lattice problems: a cryptographic perspective, volume 671. Springer Science & Business Media, 2002.
[8]]
D. Micciancio. On the hardness of learning with errors with binary secrets. Theory Comput., 14(1):1-17, 2018.
[Mic18b]
D. Micciancio. On the hardness of learning with errors with binary secrets. Theory of Computing, 14(1):1-17 2018.
[MN06]
P. Massart and E. Nedelec. Risk bounds for statistical learning. Ann. Statist,, 34(5):2326- 2366, 10 2006.
[MP68]
M. Minsky and S. Papert. Perceptrons: an introduction to computational geometry. MIT Press, Cambridge, MA, 1968.
[MR07]
D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. SIAM Journal on Computing, 37(1):267-302, 2007.
[Nov62]
A. Novikoff. On convergence proofs perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata, volume XII, pages 615-622, 1962.
[NT22]
R. Nasser and S. Tiegel. Optimal SQ lower bounds for learning halfspaces with massart noise. In Conference Learning Theory, COLT 2022, volume 178 of Proceedings of Machine Learning Research, pages 1047-1074. PMLR, 2022.
[Pei09]
Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, 2009, pages 333-342. ACM, 2009.
[Reg09]
O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6): 16(6),1-40, 2009.
[Ros58]
F. Rosenblatt. The Perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65:386-407, 1958.
[RS94]
R. Rivest and R. Sloan. A formal model of hierarchical concept learning. Information and Computation, (4(1))88-1144 1994.
[Slo88]
Sloan. Types of noise in data for concept learning. Proceedings of the First Annual Workshop on Computational Learning Theory, COLT '88, pages 91-96, San Francisco, CA. USA, 1988. Morgan Kaufmann Publishers Inc.
[Slo96]
R. H. Sloan. Pac Learning, Noise, and Geometry, pages 21-41. Birkhäuser Boston, Boston, MA, 1996.
[Tie22]
S. Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems. Personal communication, July 2022.
[Va184]
L. G. Valiant. A theory of the learnable. In STOC, pages 436-445. acm, 1984.
[Vap82]
Vapnik. Estimation of Dependences Based on Empirical Data: Springer Series in Statistics. Peringer-Verllgg Berlin, Heidelberg, 1982.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? (Yes) See Assumption
2.4
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "mfZVHy6y5mD", "reviewer": "Reviewer_yBUh", "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.\n\nThe 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.\n\n", "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.)\n- 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.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis 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.\n\nWeaknesses:\n\nOne 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.\n\nOverall, I think this is a very good paper that makes a significant contribution to the area.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WEkB6H9pCN3", "reviewer": "Reviewer_k4Eo", "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.", "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.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.\n\nI am in general positive towards acceptance; however, I would like to understand the importance of this hardness result, given the existing SQ lower bounds. ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VjHRib5UyW", "reviewer": "Reviewer_UuxY", "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.\n", "questions": "Can the authors address the essentialness of the subexponential hardness of LWE, and to what extent it holds?\n", "limitations": "There are no negative social impact concerns for this paper.\n", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OMITsLwc7QP", "reviewer": "Reviewer_EeJy", "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.\n\nThere 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).", "questions": "line 54: should be 2^{-log^{1-zeta}(n)}?\nline 224: why is this exp(-Omega(t^2/epsilon)^2)? Should it be exp(-Omega(t/epsilon)^2)?\nline 312: D^{expand} is only defined in the appendix\nline 313: there is no Fact A.5, I guess this should be Fact A.4?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept