SQ Lower Bounds for Learning Single Neurons with Massart Noise
Authors: Ilias Diakonikolas
Daniel Kane
Lisheng Ren
Yuxin Sun
Venue: NeurIPS 2022 Accept (2022)
Keywords: learning theory
Statistical Query (SQ) model
Massart noise
single neuron
ReLU activation

Abstract: We study the problem of PAC learning a single neuron in the presence of Massart noise. Specifically, for a known activation function $f: \mathbb{R}\to \mathbb{R}$, the learner is given access to labeled examples $(\mathbf{x}, y) \in \mathbb{R}^d \times \mathbb{R}$, where the marginal distribution of $\mathbf{x}$ is arbitrary and the corresponding label $y$ is a Massart corruption of $f(\langle \mathbf{w}, \mathbf{x} \rangle)$. The goal of the learner is to output a hypothesis $h: \mathbb{R}^d \to \mathbb{R}$ with small squared loss. For a range of activation functions, including ReLUs, we establish super-polynomial Statistical Query (SQ) lower bounds for this learning problem. In more detail, we prove that no efficient SQ algorithm can approximate the optimal error within any constant factor. Our main technical contribution is a novel SQ-hard construction for learning $\{ \pm 1\}$-weight Massart halfspaces on the Boolean hypercube that is interesting on its own right.


SQ Lower Bounds for Learning Single Neurons with Massart Noise
Maias Diakonikolas University of Wisconsin-Madde Madison iliasOcs. wisc. edu
Daniel M. Kane
University of California, San Diego dakane@cs, ucsd. edu
Lisheng Ren
Yuxin Sun University of Wisconsin-Madison yxsunêcs wis.. edu
University of Wisconsin-Madison 1ren290wisc. edu
Abstract
We study the problem PAC learning a single neuron in the presence Massart noise. Specifically, for known activation function f : R R, the learner is given access to labeled examples (x, y) E Rd x R, where the marginal distribution is arbitrary and the corresponding label is Massart corruption of s((w, x)). The goal of the learner is to output a hypothesis h R E with small squared loss. For a range of activation functions. including ReLUs, we establish super- polynomial Statistical Query (SQ) lower bounds for this learning problem. In more detail, we prove that no efficient SQ algorithm can approximate the optimal error within any constant factor. Our main technical contribution is novel SQ- hard construction for learning {=1] J-weight Massart halfspaces on the Boolean hypercube that is interesting on its own right.
Introduction
The success of deep learning has served as motivation for understanding the complexity of learning simple classes of neural networks. Here we study arguably the simplest possible setting of learning a single neuron, i.e., real-valued function of the form f((w, ()), where is the weight vector of parameters and f R -> a non-linear and monotone activation. The underlying learning problem the following: Given i.i.d. samples from distribution D on (x, y). where x gd is the example and E IR is the corresponding label, the goal is to learn the target function in L3-loss. That is, the objective of the learner is to output a hypothesis h Rd + such that B(x.))~[(h((x
y) is as small as possible, compared to the optimal loss value OPT == min ((x,,)~ ([[((,,)) x)]} A learning algorithm in this context is called proper if the hypothesis h is restricted to be of the form hww (x) = f((w, x)), for some w E Rd One of the most popular activations is the ReLU
function, corresponding to f(u = ReLU(u) def max(0, w.J. In this work, we study the complexity of improperly learning single neurons, where the marginal distribution examples is fixed but arbitrary and the hypothesis h is allowed to be any efficiently computable function.
In the realizable case, i.e., when the labels are consistent with function in the target concept class, the above learning problem known to be efficiently solvable various activation functions. line of work, see, e.g., [KS09] [Sol17] [S20] and references therein, has shown that simple algorithms like gradient-descee
efficiently converge to an optimal solution (in some cases under assumptions on the marginal distribution examples). On the other hand, in the adversarial label noise (aka agnostic) model, known hardness results [Dan16] DKMR22al rule out efficient constant factor approximations to the optimal loss for range of activations including ReLUs. The aforementioned negative results
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

for label agnostic learning motivate the study of weaker corruption models, where non non-trivial efficient learning algorithms may still be possible. A natural class of such models that may be more realistic in some practical applications are semi-random noise models, involving combination of adversarial choices and random choices.
Here we focus on the Massart (or bounded) noise model [MN06], a classical semi-random model first defined in the context of binary classification (see [Slo88] for an equivalent noise model). Intuitively, in the Massart model, an adversary has control over a (uniformly) random < 1/2 fraction of the labels (see Definition I.I). In the context of binary classification, [DGT19 gave the first non-trivial learning algorithm for halfspaccs in this model (see also [CKMM20 DKT2I)..
Subsequent work [DK22, [N22]] provided evidence that the error guarantee of the latter algorithm is essentially best possible in the Statistical Query (SQ) model Kea98]; and, more recently, under standard cryptographic assumptions [KMR22b]
To state our results, we formally define the following natural generalization of the Massart model for real-valued functions (see, e.g., [CKMY21| DPT21).
Definition 1.1 (Massart Noise Model). Let G be a concept class of
functions over Rd Dx be a fixed distribution over IR",, and 0 < < 1/2. Fix an unknown function E G. The noiseless distribution DD (corresponding to g) is the distribution on labeled examples (X, Y), supported on distribution on labeled examples (X, Y"), supported on F x R, such that for (X, Y') ~ D Mass we have that (i)
E R. where X Dx and Y = =XX).. An n-Massart distribution, DMsss
X ~ xx, and (ii) for all x E Rd it holds that Pr (")x,," [Y' + x X x 1n
Given sample access the 17- MaMssart distribution DMass, corresponding an unknown g E G, the goal is to output a hypothesis h RRd + R such that (2;;; DMsss) == E(X,Y")>DX'"" [XX)) is small. Let OPT Mass == inl E(X,Y")DDaa (YY (x)) denote the optimal squared error. We will say that a learning algorithm is a- a-approximate it outputs an h I2 + R that with high probability satisfies (2; DyTass) I a(d)- OPTMass- We say that a learner is constant factor approximation if O(1.. We focus on the concept class of single neurons: for an activation
f: IR + R. we will denote by C, def {ow IRd + RR Cw (x) = S((w, x)), w E Rd).
In Definition 1.1 the Massart adversary corrupts each label independently with probability at most n. Even though this noise model might appear innocuous, the fact that the corruption probability unknown the learner makes the design of efficient Massart learners challenging. The Massart model has been extensively studied in the context of binary classification [Slo88] RS94 Slo%
ABHCI3 ABHZI6 DGT19 DKTZ20 CKMY20 DKT21 and, more recently, for learning real- valued functions [CKMY21 DPT21].
For the task of PAC learning halfspaces with Massart noise (i.e., neurons corresponding to the sign activation), there is compelling evidence that even approximate learning is computationally
hard [D222 NT22 DKMR226) In sharp contrast, our understanding of the possibilities and limitations of Massart learning well-behaved real-valued functions (including ReLUs and other Lipschitz monotone activations) remains limited. On the positive side, recent work developed the first efficient learners for linear regression [CKMY21] DPT21] and ReLU regression [DPT21] with Massart noise. We note that the ReLU regression algorithm of [DPT21] requires a certain anti- concentration condition on the distribution Dx of examples, which is crucial for its performance guarantees. In fact, without such an assumption, no non-trivial upper bound is known for ReLUs (or other non-linear activations). This discussion prompts the following question:
Is there an efficient O(1) Japproximatee learner for distribution-free learning of single neuron with Massart noise?
For the important case of ReLU activations, [PP22] conjectured that the distribution-ine -intbuiiionn-ddeeeeenntt PAC learning problem is intractable. As the main contribution of this paper, we provide strong evidence towards this conjecture, by establishing super-polynomial lower bounds the Statistical Query (SQ) model - restricted but powerful family of algorithms. Specifically, we show that no efficient SQ algorithm can achieve any constant factor approximation. Moreover, our SQ-hardness result is not specific to ReLUs, but generalizes to broad class of non-linear activation functions.

---

1.1 Our Results
In this work, we give strong evidence that the problem of learning single neurons with Massart noise does not admit any constant factor approximation. Specifically, we show that any efficient SQ algorithm cannot achieve a constant factor approximation. In fact, the hardness gap that we establish is super-constant, scaling with the dimensionality of the problem.
Instead of directly accessing samples, SQ algorithms (Kea98] only to adaptively query expectations of bounded functions of the underlying distribution up to some tolerance (see Section 2 The class of SQ algorithms fairly broad: a wide range of known algorithmic techniques in machine learning are known to be implementable in the SQ model [FGR+1]
For the important class of ReLU activations, our main result is the following:
Theorem 1.2 (SQ Hardness of Massart Learning ReLUs), Any SQ algorithm that learns a single neuron with ReLU activation on Rd, the presence of Massart noise with Lj = 1/3,, to squared error better than (poly(log(d)) requires either queries of accuracy belter than 2 2-0oggd)* or at least 2 20og statistical queries, for some constant C₁ 1. This holds even if the optimal squared error is at most 2 (log dy for some 0 < C2 < i, and the total weight of the neuron is poly (d).
Theorem 1.2 rules out the existence of efficient SQ algorithms (i.e., using polynomially many queries of inverse polynomial accuracy) with approximation ratio 2 dy for some 0 < c < 1. It therefore a fortiori rules out any constant factor approximate SQ learner.
We note that the SQ-hardness result of Theorem 1.2 does not require the linearity of the ReLU (on positive inputs); a similar result can be shown for broader class of activation functions. Specifically, we can generalize our SQ-hardness result to any activation f of the form f(u) 0, u < 0, and
Bug 2 0. (wo)) * 0.
Theorem 1.2 establishes SQ-hardness of learning single neurons under the Massart noise notion of Definition
We note that for learning real-valued functions, one can consider other natural definitions of Massart noise". Specifically, Definition I.] considers an Lu-perturbation (the adversary allowed to arbitrarily corrupt a random 17- f-fraction of the labels). Another natural definition considers L2 te-perturbations as stated below (note that in the definition below, the parameter 17 does not need to be bounded above by 1/2).
Definition 1.3 (Ly-Massart Noise Model). Let G be concept class of real-valued functions
over RR, Dx be a fixed distribution over Rd, and 17 > O. Fix an unknown function 9 E g. An 1--L-Maasar distribution, DMasss 1.2 is distribution on labeled examples (X, Y), sup- ported on IRd IR such that for (X Dasss we have that (i) X Dx. and (ii) for all x E Rd it holds that (MR.))-aMw--allll
?
g())² X = x] < 4n.. We will use OPT Mass L2 == infgeg E ()x.Y)> La [Y [] to denote the optimal squared error.
Note that for [+1} labels, with noise rate < 1/2, the above model generalizes the standard Massart model (for binary classification) with the same noise rate 77. For this noise model, establish SQ-hardness for the following general family of non-linear activations (including ReL.ss):
Definition 1.4 (Fast Convergent Activation). We say that function f R + a fast-convergent activation if either g(t) == (t) or g(t) == f(-t) satisfies the following: (i) lim, g(t) exists. (ii) For t < with absolute value sufficiently large, (g(() g(-o))| 1 1/poly((t))
Intuitively, the second condition above requires that the function converges to its limit inverse polynomial rate. Without loss of generality, we consider activation which converge on the negative side. For such an activation f. let f- f(-o0) and c4 be constant such that f(c_) + f-.
Our proof technique establishing Theorem 1.2 is quite robust and can be adapted La-Massart noise under fast convergent activations. Our main result in this context is the following:
Theorem 1.5 (SQ Hardness of MasMarstt Learning). Let f R + I be a fast convergent activation. Any SQ algorithum that learns single neuron with activation on Idd, in the presence of n- Massart noise with 17 2[(c+)---1 to squared error better than 1 1/poly(log(d) requires either queries of accuracy better than 2 2 d)=1 or at least 20oggd d statisticul queries, for some constant e 1. This holds even if the optimal squared error is at most 2 21llog -loggd)² for some 0 < e2 <, 1, and
the total weight of the neuron is poly(d).
3

---

Interestingly, the key ingredient for our aforementioned SQ-hardness results for real-valued functions a new SQ-hardness construction for low-weight halfspaces (i.e., neurons with a sign activation) on the Boolean hypercube. In this context, we prove:
Theorem 1.6 (SQ Hardness for Low-weight Massart Halfspaces on 10.1)%) Any SQ algorithm that learns {=li-weight halfspaces on {0, 1J", in the presence of Massart noise with = 1/3, to 0-1 error better than 1/poly(log(d))
requires either queries of accuracy better than 2 -log dy or at least 2 2(logd) statistical queries. for some constant e1 > 1. This holds even if the optimal 0-1 error at most 2- -log "0 for some c2 < 1.
Theorem rules any efficient polynomial (relative) approximation for [=1)-t halfspaces on the hypereube. This is the first hardness result for approximate learning of Boolean Massart halfspaces. Prior work either obtained -Q-hardness of exact learning [CKMY20 was inherently applicable to halfspaces on I [D222 NT22
A number of learning problems involving halfspaces are computationally easy when the weights are small integers (aka the "large margin" case) and computationally hard for arbitrary weights. The conceptual message of Theorem [.6]is that the Massart halfspace learning problem is SQ-hard due to the combinatorial nature of the problem (and not due to the magnitude of the weights). This addresses an open problem of [Blu03] regarding the complexity of Massart learning simple halfspaccs.
1.2 Technical Overview
We start by describing the proof of Theorem 1.6 Our SQ lower bound for learning Boolean Massart halfspaces requires a number of novel ideas. Our starting point is the construction of DK22 that proves similar lower bound in the continuous setting. They begin by producing construction of a Massart PTF whose distributions conditional on y = 1 and y = 1 approximately match many moments. Using techniques from [DKS17] they show that by embedding this one- dimensional construction into higher dimensions, they can produce d-dimensional instances of Massart polynomial threshold functions (PTFs) that are SQ-hard to learn. They then further embed these instances via the Veronese embedding to produce SQ-hard LTF instances (essentially using the fact that a PTF in x is an LTF in the low-degree monomials of z))
oie-dimensional
Our proof adapts this general idea to the discrete setting, The first obstacle is developing an appropriate analogue of the one-dimensional construction. The construction from [DK22] uses the fact that discrete Gaussian nearly matches moments with a standard Gaussian; thus, making the conditional distributions of mixtures of discrete Gaussians ensures that the moment matching condition is satisfied. By carefully picking this mixture, they ensure that the conditional distributions have no overlap for |ar] small (thus ensuring a small value of OPT), but that the y = I case is always more likely for |ar] sufficiently large. This construction does not work in our case, as we need our one-dimensional construction to be discrete.
Our basic idea is to begin by noting that the binomial distribution conditioned on x being 0 mod approximately matches many moments with the full binomial. As first attempt, we let = -1 if = 0 mod s and y = 1 otherwise. This matches many moments with the binomial, but alternates between y = and y = 1 many times, and thus cannot be considered to be a low-degree PTF with Massart noise. To fix this, we need to modify our distributions so that: (i) Conditioned on any 2 far from n2/2. y more likely to be than -1, (ii) the two distributions conditioning
on y = and y = -1 have little overlap, and (iii) each conditional distribution approximately matches moments with the full binomial. We can fix (i) at the cost of (ii) by replacing the conditional distribution on y
with the full binomial distribution. As long as the prior probability of y = exceeds that of y = -1 by enough, even for x = O mod s, y/ = 1 will be more likely than y = -1. Unfortunately, the conditional distributions now have too much overlap. We can address this by moving the mass in the y = 1 conditional off of the points with r = O mod s and |x - n/2 small. Importantly, we must find a way to do this without destroying property (iii). To that end, we show that there is a way to move mass from each of these points x and redistribute it to nearby points in such way so to not affect any of the low-order moments (see Lemma 3.8). By doing this each x = mod s with |x - n/22 small, we get our final construction.
We also need to modify the method by which we embed the one-dimensional construction into higher dimensions order to obtain the family of SQ-hard PTF instances. This construction must differ from previous constructions, as our family of distributions will be discrete and not Gaussian-

---

like as in [DK177] Fortunately, we can leverage the recent technique of [DKS22], embedding our low-dimensional construction as a junta. In particular, a significant difference with the Gaussian case is in the way we embed the low-dimensional distribution as higher-dimensional one. In the Gaussian case, we simply take the distribution to be Gaussian independent directions. discrete setting, we begin by embedding into moderate dimensional hypercube by taking the unique symmetric distribution, where our one-dimensional distribution over some subset is the distribution igs over Zies X, We note that this distribution will approximately match low-degree moments with the uniform distribution over the hypercube. We then embed this distribution into a higher-dimensional hypercube as random junta.
our
As an application of the above general recipe obtain SQ lower bounds for discrete distributions, we note that the hard instances we construct for learning Boolean halfspaces with Massart noise, also (with a slight change of variables) produce hard instances for ReLUS (and other activations). In particular, in our hard instance for PTFs, the optimal classifier f is given by f(x) = -1 if x5 = 0 mod and Xs n/2| ds/2, and 1 otherwise, where Xş is the sum over the coordinates of x in some particular subset S. We note that the function (1 f(x))/2 /2, which is equal to 1 if x5ş 0 mod and |xs - n/2 < ds/2 and otherwise, can be written as ReLU(p(x)) for some degree O(d) polynomial p, where p(x) = 1 for xs = 0 mod s and |Xs n/2] < ds/2,, and p(x) s 0 otherwise. By replacing x by its Vernonese embedding as before, we can produce hard instances of ReLU functions with Massart noise.
2 Preliminaries
Notation For n E Z+, we denote [n] def {l.....M. n). For two distributions p. q over probability space Ω let drv (p.
supsça (p(S) - q(S) denote the total variation distance between p and g. We use Pr[E] and I[E] for the probability and the indicator of event E. For real random variable X, we use E [], Var [X] denote the expectation and variance of X, respectively. For n Z+ and 0 S p S 1, we use Bin(n, p) to denote the Binomial distribution with parameters and p. Throughout this article, we will use capital letters (e.g., X) to denote random variables and random vectors, and small letters (e.g, x, x) to denote corresponding values.
Statistical Query Algorithms We will use the framework of Statistical Query (SQ) algorithms for problems over distributions [FG We require the following standard definition.
Definition 2.1 DDecision/Testing Problem over Distributions). Let D be a distribution and D be a family of distributions over R We denote by B(D, D) the decision (or hypothesis testing) problem in which the input distribution D' is promised to satisfy either (a) D' = D or (b) D' E D, and the goal of the algorithm is to distinguish between these two cases.
We define SQ algorithms as algorithms that do not have direct access to samples from the distribution, but instead have access to an SQ oracle. We will consider the following standard oracle.
Definition 2.2 (STAT Oracle). Let D be a distribution on M A Statistical Query (SQ) is a bounded function f IR. - [-1, 1]. For > 0, the STAT(T) oracle responds to the query with a value Ex=Dif(X)) I r. We call r the tolerance of the statistical query. A Statistical Query (SQ) algorithm is an algorithm whose objective is to learn some information about an unknown distribution D by making adaptive calls to the corresponding STAT(T) oracle.
such that |V Ex
3 SQ Hardness Construction for Supervised Learning
3.1 Generie SQ Lower Bound Construction
We start with some basic definitions. Let UM be the uniform distribution over {0, 1)M For a subset T C MM and {0, 1)M M, denote xr (-1)E.er=1, s. For distribution P over {0, 1) M, let We will require the orthogonal polynomials under the binomial distribution. Definition 3.1 (Kravchuk Polynomial
P(T) = Ex-PlXx(3
[Sze89). For k. m. Z, with 0 < k, S m. the Kravchuk polynomial K4; m) is the univariate degree-k polynomial in x defined by K,((;;)) ==
-rgin,,71+446655 (-10 (f) (M=3), where y has x I's and m O's.
The following distribution family that is the basis of our discrete SQ lower bound construction.
5

---

Definition 3.2 High--Dimensionl Hidden Junta Distribution). Let m, M E Σμ with m < M. For a distribution A on im] U {0} with probability mass function (pmf) A(z) and a subset S S [M]] with |S] = m, consider the probability distribution over (0, 1 1 denoted by Pg. such that for X ~ P the distribution (X;)igs is the uniform distribution on its support and the distribution (Xi)ie is symmetric with Eies X; distributed according to A. Specifically, P is given by the pmf
(x) = 2 + m A (Eies zi) (EvES
The following condition describes the approximate moment-matching property of the desired distri- bution A with the Binomial distribution.
Condition 3.3. Let k, m E 2+ with k < m and v > 0. The distribution A on [m]] U {0} is such that
(KX m)]l S v. for all < t < k.
We now define the hypothesis testing and learning problem which will be used throughout this paper:
Definition 3.4 (Hidden Junta Binary Testing Problem). Fix + b E R. Let A and B be distributions on [mm] U {0} satisfying Condition 3.3 with parameters & E Z+ and v E R2,, and let E (0, 1). For M E Z+, M > m, and a subset S S [M] with |S| = m, define the distribution S.a.b on {0, 10. {a, b) that returns a sample from (Pá) a) with probability p and a sample from (P b) with probability 1 - p. In the (A, B, a, b. - Junta Testing Problem, one is given access to a distribution D so that either Hy: D = URr where for (X, Y) ~ US we have that X a uniform random element of {0, 1) JMM, and Y is independently a with probability p and b with probability 1-p.
H1: D is given by PA...p for some subset S _ [M] with [S] = m. One is then asked to distinguish between Hg and H1.
S,a,b
Note that this is just the hypothesis testing problem B(D, D) with = Uhr and D = (PS.a. }.
Proposition 3.5 (Generic Discrete SQ Lower Bound), Let m, M E Z, with M > Let A, B be distributions on [m]] U {0} satisfying Condition 3.3 Let T 2 kv² - 2 (x"(xx, Bin(m.112) (B, Bin(m, 1/2)))- Any SQ algorishm that solves the testing problem of Definition 3.4 with probability at least 2/3 must either make queries of accuracy better than v2T must make at least 20 7 (A, Bin 1/2)) + x² x²(B, Bin(m, 1/2))) statistical queries.
We give proof sketch here and defer the full proof to Appendix B We first pick a collection C of 20(mm) subsets S C [M] of size m. whose pairwise intersections small. For any S, E C. we write the correlation between P P..B.p. P P.A.B.p as linear combination of the correlation between S.a.b s P.J. and the correlation between P Pg.. Since we can directly obtain an upper bound for the correlation between the hidden junta distributions, applying existing techniques will yield our result.
PAA.
3.2 Construction of Univariate Moment-Matching Distributions
Here give the construction of our approximate moment-matching distributions. For convenience, we use the "expectation" and "moments" for the unnormalized measure without clarification. The main result of this section captured in the following proposition.
Proposition 3.6. Let d, k, s, m E4 and Ç E (0, 1/2) such that: (i) s 2 wokk), (ii) k < m/2, (iii) ds 2 22 m log(1/()), and (iv) s²d S o(m). There exist measures D+ and D_ over [m] (0) and union J of d points in [m]] U {0} such that: 1. (a) D.,. = 0 on J, and (b) D. > 2D_
on J = [m]] U [0) \ J. 2. All but Ç-fraction of the measure of D__ lies in J. 3. The distributions D+/1[D+11 1 and D_ -/DD_1 11 satisfy Condition 3.3 with parameters k and v < (T) exp(- (m) 4. (a) D+ is at most ((1 (1),in,mm, 1/2) and (b) TD+111 = ((1) 5. DD_ = (11ss).
Proof. We start by constructing each measure in turn.
Definition of the Measure D__ We define the measure D_ as follows: D__ P_xx)) Bin 1 1/2) (x)
i = 0 (mod s); otherwise D_ (x) = O. We claim that this satisfies Condition 3.3 This is shown
in the following lemma.
Lemma 3.7. D_(x) satisfies Condition 3.3 with parameters i and v = s(() exp( (op(-((mms)))

---

Proof. We need to bound Bz-D_ (X)[2m)) for 1 S I k. By definition, we have that
m
Bz-D_IKi(2;;n)) - Σ E (Y)] Ti(m),TT=
Ex (xx)xxxx(xx
where Y has Z I's and m - 0's, and R E (0, 11th is the unique symmetric measure with Ei=1 X; having measure D_, and To [ [m] is some subset with [To] = t. Let w be a primitive s th root of unity. We note that the pmf Rxx of the measure satisfies
t 1
1 E :
R(x) 2m
2
Therefore, we can write
R(x)xT((x) ((1)) lie
(w((-))lierr)) "
2 2
1=0 f=
2 1=ر
Since the expectation is the sum of the above over all x {0, 1 and since this separates product, we get that
Ex~R Ex~RIxI, (x)] = 2ms s
1
E
Il m
(w((-1)lieral)* 21 = 2 y=0
s-1 m
Σ
II
(1+ w0 (-1Jliii)))
xE
(0.0))
j=
1=1
Note that the terms with 2j = 0 (mod s) have indices i such that w (-1) (-1) = 11 and do not
contribute to the sum. Other terms will have each value of |1 + w (-1) at most 2 - S2(1/s²). Therefore, Ex~R (XT, (X) = exp(-s(mm/s²). This completes our proof.
We also note that D_ is clearly bounded above by Bin(m, 1/2). We define J to be the union of the d elements of m {0) congruent to 0 modulo s that are closest to m/2. We note that the measure of D__ outside J is clearly at most the probability that Bin(m, 1/2) is more than ds/2 from m/2, which is at most Ç by standard tail bounds.
Definition of the Measure D+- Intuitively, we would like to define D+ to be equal to some suitable multiple (say. 3) of the standard Binomial measure Bin Bin(m, 1/2). Such a definition would satisfy the desired moment- moment-matching conditions (property 3 of Proposition (.6) with zero error and would also guarantee that D+ > 2D on J, as desired (property 1(b)). However, this candidate definition does not satisfy property (a)), i..., that D+ be equal to 0 on J. To satisfy the latter property, we will need to carefully modify this measure. The key lemma is the following (see Appendix B for the proof):
Lemma 3.8. Let s 2 wk*). There exists a signed measure μ on {-s 1, 2, ........................ .., s 1} such that: (i) For any integer S t S k Ei=l-, =0, 0, (ii) p(0)= -1, (ii) (u(1)] 1/10, i + O.
We are now ready construct the measure D4. We begin with the measure 3Bin 1/2). We then for each element x E J take the measure j from Lemma (.8 translate it to center around x and add appropriate multiple of it to D4 in order to make D (z) = O. It is clear that the first k moments of D. agree with those moments of 3Bin(m, 1/2), and from there it follows that D..
satisfies Condition 3.3 with 0, since for any 0 1 < is and any point & E J, we have that
Σ p( m0) 11--
Σ 10
Σ ((0)(())))))) i=l-s
MO)= 00 =
Σ
have D.,. which means that never change the moments by making (x) = O. Therefore, is O on J by our construction. We also claim that D4 is bounded between 2Bin(m, 1/2) and 4Bin(m, 1/2) on J. For this, we note that for any x & J, there are most two integers, x' and x". that are in J and within distance s of æ. It is clear that
(x) - 3Bnn(m, 1=)) < (Bmm)) 1/2)(z²) + Bin(m, 1/2)(²"))
It suffices to show that Bim(m.1/21(z') 1/2(m,
< 3/22 along with the analogous statement for x². However,
the log of the ratio is easily seen to be O(sdd/m) o(1), which suffices. This completes the proof of Proposition 3.6
D
7

---

3.3 Parameter Setting for the SQ-hard Distributions
We will consider the following family of hardness distributions which will be used in the proof of all SQ hardness results throughout this article. Let C' > 0 be a sufficiently large universal constant. Let m be a positive integer and m' be an integer on the order of Cm. Let d be an integer on the order of m!/10, s an integer on the order of m4/9, and an integer on the order of m2/19. Observe that (2 m'' I (ml))d = exp(O(Cm) /11 log(m))). Select m as large as possible so that the above less than M. Decreasing M if necessary, we can assume that M = (2dtm') ). We
consider the Veronese mapping Vo(d) : 1RTh' - IRM, such that the coordinate functions of Vo(a) are exactly the monomials in m variables of degree at most O(d). We define measures D. and D_ on [m]] U {0), as given by Proposition 3.6, with k; and d as above, and taking log(1/C) sufficiently small multiple of (ds)²/m,
that <= exp(-S((m
exxp(S2(11e)) )))
It is easily verified that these parameters satisfy the assumptions of Proposition 3.6 For a subset
S C [mm'] of size and labels + E R, define the distribution P S.a.b P...D-.. as in Definition 3.4. with
p- |1D+ 111 /(I + I1D_1l1). We will consider the distribution (X'Y"") "") on 10, {a, b)
by drawing (x, Y) from P P0 PD. and letting X' Vora (X) and Y' = =Y. It is easy to see that finding hypothesis that predicts y' given x' is equivalent to finding a hypothesis for given (since y = y' and there D+ and D_ imply that x²(D+/ (D= ||,, (in(m,112)) + (D DD1 11. Bin(m, 1/2)) = O(s²). The parameter v in Proposition 3.5 is at most smx exp(-5((m/=)) = (Sp(-(((=/))) Note
known 1-1 mapping between x and x'). The pointwise bounds on
As I is also ((log(M))1.5)) we have M) ())) < 1/poly(M). In the remaining part of this article, we will use x', X' y Y' without clarification to denote the results of x, X. y, after the Veronese mapping Vo(d) IRm" R
that as M exp(O(m22/1)) this is exp(=(((og((M)-))
that T = exp(-9t(
4 Concrete SQ Hardness Results
In this section, we prove our SQ hardness results for Massart learning low-weight half-spaces and ReLUs. We provide additional SQ hardness results for learning fast convergent activations with respect to Massarstr noise in Appendix
4.1 SQ Hardness of Learning Low- Weight Boolean Halfspaces with Massart Noise
In this subsection, we prove the following theorem.
Theorem 4.1 (SQ Hardness for Low-weight Massart Halfspaces on {0. M) Any SQ algorithm that learns {+1] J-eeight halfspaces on (0, 1), in the presence of Massart noise with = 1/3. to 0-1 error better than 1/poly(log(MM))
requires either queries of accuracy better than == at least 1/T statistical queries. This holds even if the optimal classifier has 0-1 error exp( exlo- My8/9).
(
Our proof will make use of the SQ framework of Section 3.1 and will crucially rely on the mie-dimeniional construction of Proposition 3.6, In this subsection, we fix the labels a = 1. = -1, and apply the construction in Section 3.3 to obtain the joint distributions (X, Y) and (X'Y') Note that y = y and there is a known 1-1 mapping between x and x', therefore finding hypothesis that predicts yf given x' equivalent to finding hypothesis for y given x.
Proof.
Claim 4.2. The distribution (X', Y') over {0, x {+1} is Massart LTF distribution with and Massart noise rate upper
optimal misclassification error OPT < bound of 1 1/3.
We defer the proof of the above claim Appendix C We now show that the (D+, D,, 1,-, m')- Hidden Junta Testing Problem efficiently reduces to our learning task. In more detail, we show that any SQ algorithm that computes hypothesis h satisfying Pr ( (X'))') # Y'I < min(p,
p) 2 27 can be used as black-box to distinguish between P DD_.D_. for some unknown subset S C [m]] with |S| m, and UP Since there is a 1-1 mapping between x E (0.1) 13 and x' E {0, M, we denote h {0, 13m + {+1} to be h(x) n((x)). We note that
8

---

can (with one additional query to estimate the Pr(h'(X') * Y within error V2T) distinguish between (i) the distribution P D.DD- D-.P and (ii) the distribution UT" This is because for any h we S,a. have that Pr(x.y)~uz, [h(X) * Y] 2 min(p, 1 - p). Applying Proposition 3.5 we determine that any SQ algorithm which, given access to distribution P so that either P U or P is given by PDD,D .P- for some unknown subset 5 _ [m''] with |S] = m, correctly distinguishes S.a.b
between these two cases with probability at least 2/3 must either make queries of accuracy better than /2T or must make at least 20(m) ( Bin(m, 1/2)) + x2 Bin(m, 1/2))) statistical queries. Therefore, it is impossible for an SQ algorithm to learn hypothesis with error better than min(p, 1 p) 2/2r (11/s) ((vF) 1/polyyog(MM (M) without either using queries of accuracy better than making at least 2 ( (Mollylog(M) 1/T many queries. This completes the proof of the SQ-hardness.
It remains to argue that the underlying halfspaces in the hard instance can be assumed to have {+1} weights. To deal with the weights, we note that g is degree-2d PTF that can be defined as the product of 2d linear polynomials L;, so that each L; has integer coefficients and the sum of the absolute values of these coefficients is O(m). This means that g can be defined by degree-2d polynomial with integer coefficients and the sum of whose absolute values is at most (m))2 = poly(M). By doubling these coefficients, we can assume that they are all even. Therefore, the linear threshold function L can be defined by linear polynomial with even integer weights each of which has absolute value at most W. If we replace our distribution over {0, 1} by distribution over {0, 1 by duplicating each coordinate W times (i.e., creating new distribution with coordinates ž1,j for i E [M] and j E [W] with 2i.j = I; for all i, we can rewrite L(x) as LTF [z),,, where L' has [=ei-wss This is done by replacing term 0:2; by (0c+ W2/2
1==1
21,J
W))(0. 2.3- This completes the proof of Theorem 4.1
ΣW
4.2 SQ Hardness of Learning Single Neuron with Massart Noise
In this subsection, we prove our SQ hardness result of learning single neuron with ReLU activation and Massart noise. The standard ReLU function is defined by Re max(t, 0), Vt E R. For technical convenience, we will consider the following linear transformation of the standard ReLU, ReI.U(() 1 if L < 0, and ReI.U(() -1 + 2/ otherwise. We note that our SQ hardness result for the ReLU function applies to the standard ReLU function as well.
Theorem 4.3 (SQ Hardness of Massart Learning ReLUs). Any SQ algorithu that learns a single neuron with ReLU activation R. M, in the presence of Massart noise with 17 1/3, within squared error belter than (ipoly([og[M))
requires either queries of accuracy better than T == (xp(-S((lg(MM)) (Mfooo((M)05))) or at least 1/7 statistical queries. This holds even (i) the optimal neuron has squared error exp(-S2(log M )/9),, (ii) The X values are supported on {0, 1)M, and (iii) the total weight of the neuron is pol((M)
Throughout this subsection, we need the following technical lemma.
Lemma 4.4. Let J be a union of d points in [m] U (0) for some odd integer d. Then there exists real univariate polynomial p(x) of degree (d) such that p(z) = 1, Vx E J, and p(x) S O, Vx E J. In addition, the absolute value of the coefficients of p(z) is at most m (id) = (M)
"en....,.a,, Define ((x) = - - (x (z, 1/2)) - (x; + 1/2)). By definition, we have that g(x)= O, Vx J, and ((x) < 0. Vr E J. Then, by polynomial interpolation. < i < d.
Proof. Let
there exists a real univariate polynomial r of degree d - 1 such that r(z,) = 1
Vo(a,)
Consider the real univariate polynomial p(z) = (2)))(x)) For any 1 1 S d, we have that p(z,) = (x;))((;)) I and for any E J. we have that p(z) < 0 since q(x) < 0, Vx E J. Finally by polynomial interpolation, we know that the absolute value of every coefficient of rxx), p(x) is at most m ((d) = PM)y(M).
Proof of Theorem 4.3
Our proof will make use of the SQ framework of Section 3.1 and will crucially
rely on the dim-dimell construction of Proposition (.6) In this section, we fix the labels - 1, and apply the construction in Section 3.3 to obtain the joint distributions (X, Y) and

---

XXYY', Note that y y/ and there is known 1-1 mapping between x and x', therefore finding hypothesis that predicts y/ given x' is equivalent to finding hypothesis for y given x.
Claim 4.5. The distribution (X) over {0, x {+1} is Massart single neuron distribution with ReLU activation and with optimal squared error OPT L2 S exp(-S((log()) M ))) and Massart noise rate upper bound 1) 1/3.
- (D,,D_,-1, m')- Hidden Junta Testing Problem efficiently reduces to our learning task. more detail, we show that any SQ algorithm that computes a hypothesis h' satisfying S.a.b D-.DD-1" for some unknown subset S S [mm'] with |S| = m, and U m/ Since there is 1-1 mapping between x E {0, 1)m² and x' E (0,1) we denote h {0, 1) R to be h(x) h' f'(x'.. We note that we can (with one additional query to estimate the E[(N((X) - ) within error v 22) distinguish between (i) the distribution P S,a.b
We defer the proof of the above claim to Appendix We now show that the (D+,
Y < 4p- 4p² 2/
can be used as a black-box to distinguish between P
P..D-..P
and (ii) the distribution UP This is because for any h we have that
E EX [(h )) 1 2(1 2p) (X,Y [x(X]] + E E(X,Y) [h(X)²]
2 2(1 - 2p) Ex) [M(X] + E E ml [x) 4p -pp
Applying Proposition 3.5 we determine that any SQ algorithm which, given access to a distribution P so that either P = U .. or P is given by S.a.b PD..D-.P for some unknown subset S C [m/'] with |S| = m. correctly distinguishes between these two cases with probability at least 2/3 must either make queries of accuracy better than V2T or must make at least /0 T/xxx(AA, Bin(m. 1/2)) +
(B, Bin(m, 1/2))) statistical queries. Therefore, it is impossible for an SQ algorithm learn a hypothesis with error better than 4p- 4p² 2/22 = (11/8) @(vF) = 1/polylog( (M) without either using queries of accuracy better than r or making at least 20(m) / /pooyllo(MM) (M) > 1/T many
queries. This completes the proof of Theorem 4.3
5 Conclusion and Future Directions
In this work, we showed that no efficient SQ algorithm can approximate the optimal error within any constant factor for learning single neurons with Massart noise. In the process, constructed new moment- matching distributions corresponding to Boolean halfspacce with Massart noise, which is result of independent interest. Importantly. our construction has some additional desirable properties which allows us to establish hardness for learning low-weight LTFs, strengthening the result of [D222] In addition, provide a simple technique for transforming our binary construction into hardness of learning real-valued single neurons with Massart noise.
A number of avenues for future work remain, some of which we briefly discuss below. Recent work [DKK (2) studied the problem of learning halfspaces under the Gaussian distribution with Massart noise for 1/2. It is plausible that the 1/2 case in our distribution-independde is much harder than the 77 = 0.49 case. Establishing such a statement is left as an interesting open question. Another direction concerns the iestribution-speciine
setting
setting. Are there efficient algorithms with non-trivin trivial error guarantees (c.g., achieving a constant factor approximation) for learning single neurons under simple discrete distributions (e.g., under the uniform distribution on the hypercube)?
10

---

References
[ABHU15] P. Awasthi, M. F. Balcan, N. Haghtalab, and R. Urner. Efficient learning of linear separators under bounded noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, pages 167-190, 2015.
[ABHZ16] P. Awasthi, M. F. Balcan, N. Haghtalab, and H. Zhang. Learning and 1-bit compressed sensing under asymmetric noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016, pages 152-192, 2016.
[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.
[CKMY20] S. Chen, F. Koehler, A. Moitra, and M. Yau. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. In Advances in Neural Infor- mation Processing Systems 33: Annual Conference on Neurul Information Processing Systems 2020, NeurlPS 2020, 2020.
[CKMY21] S. Chen, F. Koehler, A. Moitra, and M. Yau. Online and distribution-free robustness: Regression and contextual bandits with huber contamination. In 62nd IEEE Annual Symposium Foundations of Computer Science, FOCS 2021, pages 684-695, IEEE, 2021.
[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.
[DGT19] Diakonikolas, T. Gouleakis, and Tzamos. Distribution-indeeenden PAC learning of halfspaces with massart noise. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pages 4751-4762, 2019.
[DK22] Diakonikolas and D. Kane. Near-optimal statistical query hardness of learning halfspaces with massart noise. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages -2822 PMLR, 2022. Full version available at http:://ariivorg/bbb//11...
[DKK+22] I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. Learning general halfspaces with general massart noise under the gaussian distribution. Symposium on Theory Of Computation (STOC), 2022.
[DKMR22a] I. Diakonikolas, D. Kane, P. Manurangsi, and L. Ren. Hardness of learning single neu- ron with adversarial label noise. In Proceedings of the 25th International Conference on Artificial Inielligence and Statistics (AISTATS 2022), 2022.
[DKMR226] I. Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren. Cryptographic hardness of learning halfspaces with massart noise. CoRR, abs/2207. 1426/2207.1266,, 2022. Conference version in NeurlPS'22 22.
[DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 58th IEFE Annual Symposium Foundations of Computer Science, FOCS 2017, pages 73-84, 2017. Full version at http://arxiv.or//as//1/
[DKS22] Diakonikolas, D. Kane, and Y. Sun. Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models. In Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022), 2022.
[DKT21] 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, I, NeurIPS 2021, pages 7732-7744, 2021.
11

---

[DKTZ20] Diakonikolas, V. Kontonis, C. Tzamos, and N. Zarifis. Learning halfspaccs with mas- sart noise under structured distributions. Jacob D. Abernethy and Shivani Agarwal, editors, Conference Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 1486-1513, PMLR, 2020.
[DP221] Diakonikolas, H. Park, and C. Tzamos. Relu regression with massart noise. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, pages 25891-25903, 2021.
[FGR 17] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and lower bound for detecting planted cliques. ACM, 64(2):8:1-8:37, 2017.
[Kea98] M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983-1006, 1998.
[KS09] A. Kalai and R. Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT 2009, 2009.
[MN06] P. Massart and E. Nedelec. Risk bounds for statistical learning. Ann. Statist., 34(5):2326-2366 10 2006.
[NT22] R. Nasser and S. Tiegel. Optimal SQ lower bounds for learning halfspaces with massart noise. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1047-1074. PMLR, 2022. Full version available https///arivv.rrgabs//20) 200.//22000.118....
[RS94] R. Rivest and R. Sloan. A formal model of hierarchical concept learning. Information and Computation, 1 114(1):88- 18--114, 114, 1994.
[Slo88] R. H. Sloan. Types of noise in data for concept learning. In 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.
[So117] M. Soltanolkotabi. Learning relus via gradient descent. In Advances in neural informa- tion processing systems, pages 2007-2017, 2017.
[Sze89] G. Szegö. Orthogonal Polynomials, volume XXIII of American Mathematical Society Colloquium Publications. A.M.S, Providence. 1989.
[YS20] G. Yehudai and O. Shamir. Learning a single neuron with gradient methods. In Conference on Learning Theory, pages 3756-3786. PMLR, 2020.
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 descrihe the limitations of your work? [N/A]
(c) Did you discuss any potential negative societal impacts of your work [N/A] Our work pure theoretical nature.
(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] Each theoretical result explicitly accompanied with the assumptions required.
(b) Did you include complete proofs of all theoretical results? [Yes] The main body of the paper contains all essential and significant proofs and the remaining technical proofs are the supplementary.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as 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 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 (e.g., type of GPUs, internal cluster, or 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 eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing 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": "z11ULl_wIhh", "reviewer": "Reviewer_8CnK", "summary": "This work deals with the problem of PAC learning a single neuron with Massart noise. For this task for various activation functions, the authors provide super-polynomial SQ lower bounds. In particular, it is proved that no efficient SQ algorithm can approximate the optimal error within any constant factor.", "questions": "Theorem 1.2 captures the ReLU activation function and other functions with a \"threshold\" behavior. Is there some intuition on why the result holds only for these activations? Do we expect similar hardness results for other activations? ", "limitations": "This is a theoretical work. The authors describe the limitations of this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main question of the paper is whether there exists an efficient constant approximate learning algorithm for distribution-independent learning of a single neuron with Massart noise for various activation functions. The authors rule out the existence of efficient SQ algorithms with constant factor approximation for the above problem for the ReLU activation.\n\nNext the authors introduce a second variant of the Massart noise model for real-valued functions and give another SQ lower bound for this model and a general family of activations (including ReLUs).\n\nI believe that the most interesting result is Theorem 1.6 which gives an SQ hardness result for low-weight Massart halfspaces on the Boolean hypercube. The fact that this problem remains SQ-hard is quite nice and justifies the difficulties when dealing with the Massart noise model.\n\nIn general, the paper is clear and the results are well presented.\n\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": "xrmxNPePL_5", "reviewer": "Reviewer_DKp1", "summary": "The authors consider the problem of (distribution-free) PAC learning of single neuron neural nets in the presence of Massart noise, with the aim off finding a constant factor approximation error. They prove a super polynomial lower bound in the statistical query model (a restricted family of algorithms). This is proved for ReLU and also a broader class of activation function: those that output zero for negative parts and any injective function for the positive part. They establish a hardness gap that is super-constant and scales with the dimensionality of the problem. This lower bound shows a barrier to improve the existing upper bounds (i.e., one cannot hope to use algorithms based on statistical queries to get an efficient method with constant approximation guarantee) \n\nTechnical overview:\n•\tThe proof starts by finding a SQ hard instance for the Boolean case based on recent results for continuous case.\n•\tThe recent result is for continuous case and finds instances for one-dimensional Gaussian like distributions and extend it to high dimensions.\n•\tThey need the case for discrete and it is not easy to extend that Gaussian like results to this case\n•\tThey start by constructing the binomial distribution conditioned on X being 0 mod s and then change the distributions so that (1) conditioned on X being far from n/2 the probability of Y=1 is larger than Y=-1 (2) conditioned on Y=1 and Y=-1, the distributions have less overlap and (3) the conditional distributions have moments close to binomial.\n•\tUse recent result to extend this to high dimensions.\n•\tConstruct an instance of ReLU that produces the desired classifier for the Boolean case\n", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ The authors offer a SQ lower bound for learning neural nets with 1 neurons under Massart noise. This is a solid technical contribution and an important step towards understanding the barriers for improving regression algorithms under noise conditions.\n\nWeaknesses:\n\n+ The generalization of the Massart noise model to the real-valued case (Definition 1) seems somewhat unnatural. In the real valued extension the y-values are kept \"exactly the same\" with some probability and changed otherwise. Yes, this coincides with Massart noise for binary case, but in the continuous case is rather odd. Some more motivations can help.\n\n+ The paper does not provide enough background and motivations, has missing/vague notations, missing explanations that can glue different technical results, and sometimes not rigorous in the statements of the results. Overall, the paper is hard to read or assess, and in my opinion is not ready for publication. The presentation can be greatly improved. Some concrete points:\n\n+ Many notations are unclear, vague, or even undefined. Here are some examples:\n+  Definition 3.2. The notation (X_i )_(i∈S) is confusing and has not been properly defined or explained. Also, what is a symmetric distribution in this case? Parsing this definition with these notations \n+  Definition 3.4. What does sampling from (P_S^A,a) mean? Does it mean that we sample a point x from P_S^A   and return (x,a)? The notation is quite confusing.\n+ Proposition 3.5. although rather standard, it would help to define the X^2 distribution and its notation.\n+ When you use a measure as a function, do you assume it has some kind of (unnormalized) density?\n+ Related to the previous point, the notations D_+ and D_- are not consistently used. Sometimes they refer to the function as used D_+=0 on J and sometimes they are used with reference to the input as D_+ (x). Also, it would help to define the ell_1 norm of D in this context.\n+ would help to explicitly define (±1)-weight half-space\n\n+ The introduction of the paper does not motivate the setting. Adding some more motivations such as explaining why a statistical query lower bound is important can help the non-expert reader. The structure of the literature review and the background does not help the non-expert reader either.\n+ Some lemmas and propositions appear in the main paper without enough context or explanations about where they are going to be used. \n+ The technical proofs are quite hard to follow. The different parts of the proofs are not introduced with intuitive introductions and explanations. It is difficult for the reader to obtain a general understanding of the problem without diving into the technical proofs of theorems, which are also hard to understand considering the missing notations and definitions.\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": "tYRWreTQ7O", "reviewer": "Reviewer_J7z6", "summary": "This paper studies the question of distribution-free, improper learning of single neurons when a random fraction of the labels in the training data have been corrupted. The objective is to output a predictor whose squared loss over the clean data is as close to that achieved by the optimal neuron. They show that no statistical query algorithm with polynomial query complexity or inverse polynomial tolerance can always achieve a constant factor approximation to the optimal squared loss in the worst case. They additionally show hardness in a different setting that they call \"L_2-Massart noise\" in which the labels are given by perturbing the true label by heterogeneous noise of bounded variance.\n\nThey also show a new SQ lower bound for distribution-free learning of halfspaces in the presence of Massart noise. Unlike the previous lower bounds of Chen et al. '20 and Diakonikolas and Kane '20, their bound applies to halfspaces over the hypercube whose coefficients are from {1, -1}. \n\nThe hard instance they construct to prove these lower bounds closely follows the approach of Diakonikolas and Kane '20, with the main technical twist that they need to handle discrete rather than Gaussian inputs. They design a joint distribution over $(x,y)$ such that 1) conditioned on $y = -1$ or on $y = 1$, the distribution over $x$ is iid random bits outside of a hidden subset of $m$ coordinates over which it is symmetric and such that the 1D distribution of the sum of these $m$ coordinates approximately moment-matches $\\text{Bin}(m,1/2)$, 2) these 1D distributions for $y = 1$ and $y = -1$ don't overlap by much, and 3) the joint distribution can be realized as an instance of whatever learning problem their lower bound applies to.", "questions": "*Questions*:\n- A priori isn't it possible that ReLU regression under Massart noise isn't constant-factor-approximable even when the covariates are *uniform* over the hypercube?\n- Can one hope for a common generalization of this work together with Diakonikolas and Kane '20 to show hardness for a more general family of activations than just {sign} + {\"relu-like\" functions that are injective over the positive part}? Perhaps any activation that is far from the identity function?\n\n*Minor comments*:\n- Technical overview is quite hard to read for a general audience as it assumes close familiarity with [DK20]. Also it uses notation that is not defined previously in the paper (see below)\n- P. 2 Line 58-60: While this is true for binary classification, this point doesn't seem very relevant for the real-valued regression problems studied in this submission.\n- P. 4 Line 147: The relevant document doesn't appear to be available, though the associated talk slides which are available online don't seem to mention this as an open problem\n- P. 4 Line 168: s not defined\n- P. 4 Line 171: n not defined\n- P. 4 Line 152: LTF and PTF should be defined\n- P. 9: would be helpful to include a sentence on why it's more convenient to work with $\\widehat{\\text{ReLU}}$ rather than $\\text{ReLU}$\n- Lemma 3.7: confusing as Condition 3.3 is phrased in terms of distributions, whereas Lemma 3.7 is about an unnormalized measure, and this is exacerbated by the expectation notation used in the proof. also, isn't $\\mathcal{R}$ also unnormalized? if so, the use of the word \"pmf\" is similarly confusing.\n- Some of the technical writing is rather hard to read, e.g. the block of text in Section 3.3, though this might be due to space constraints.\n- It seems more accurate to call Definition 1.1 Huber contamination rather than Massart noise.", "limitations": "The authors give a pretty comprehensive answer to the question they set out to solve, so I don't see any limitations per se. I also don't see any potential negative societal impact, as they are proving a hardness result for a theoretical problem.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic of this paper feels a bit like smashing a bunch of well-studied topics together. Arguably the main reason to be interested in extending existing lower bounds for learning halfspaces under Massart noise to learning ReLUs would be that real-valued regression problems tend to require new techniques for showing hardness. But the architecture of the proof in this work builds heavily on Diakonikolas and Kane '20, and the hard joint distribution exhibited ultimately has binary labels as before (they've gone from the PTFs of Diakonikolas and Kane '20 to certain ReLUs of polynomials which take on binary values over the hypercube). The main technical difference is that it's important that the x's are over the hypercube instead of $\\mathbb{R}^d$, so one needs some discrete analogue of the usual non-Gaussian component analysis setup. But this discrete analogue is precisely the one developed in Diakonikolas, Kane, and Sun '22. That being said, the actual moment-matching construction is new and requires a number of clever moves, in particular Lemma 3.8, that are specific to the setting at hand.", "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": "s7TWkbuB3lN", "reviewer": "Reviewer_yXsm", "summary": "The paper addresses the problem of PAC learning a single neuron under the Massart noise model. For various activation functions, including ReLUs, the authors show that no efficient Statistical Query (SQ) algorithm can approximate the optimal error within any constant factor. The key technical innovation is a new SQ-hardness construction for learning neurons with a sign activation on the Boolean hypercube.\n", "questions": "Can the case $\\eta=1/2$ in the noise model be addressed within this framework?", "limitations": "I do not foresee any potential negative societal impact of this work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and the results coherently presented. The paper can benefit from a separate conclusion / potential open problems section.\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": {}}]

Author rebuttal:

Decision: Accept