Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
Authors: Sitan Chen
Aravind Gollakota
Adam Klivans
Raghu Meka
Venue: NeurIPS 2022 Accept (2022)
Keywords: PAC learning
neural networks
SQ lower bounds

Abstract: We give superpolynomial statistical query (SQ) lower bounds for learning two-hidden-layer ReLU networks with respect to Gaussian inputs in the standard (noise-free) model. No general SQ lower bounds were known for learning ReLU networks of any depth in this setting: previous SQ lower bounds held only for adversarial noise models (agnostic learning) (Kothari and Klivans 2014, Goel et al. 2020a, Diakonikolas et al. 2020a) or restricted models such as correlational SQ (Goel et al. 2020b, Diakonikolas et al. 2020b). Prior work hinted at the impossibility of our result: Vempala and Wilmes (2019) showed that general SQ lower bounds cannot apply to any real-valued family of functions that satisfies a simple non-degeneracy condition. To circumvent their result, we refine a lifting procedure due to Daniely and Vardi (2021) that reduces Boolean PAC learning problems to Gaussian ones. We show how to extend their technique to other learning models and, in many well-studied cases, obtain a more efficient reduction. As such, we also prove new cryptographic hardness results for PAC learning two-hidden-layer ReLU networks, as well as new lower bounds for learning constant-depth ReLU networks from membership queries.

Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
Sitan Chen UC Berkeley
Aravind Gollakota UT Austin
Adam R. Klivans UT Austin
si sitanoberreeey.comm edu
aravindgocs. utexas. edu
klivans@cs, utexas. edu
Raghu Meka UCLA raghum@cs. ucla.
Abstract
We give superpolynonial statistical query (SQ) lower bounds for learning two- hidden-layer ReLU networks with respect to Gaussian inputs in the standard (noise-free) model. No general SQ lower bounds were known for learning ReLU networks of any depth in this setting: previous SQ lower bounds held only for ad- versarial noise models (agnostic learning) 14,14, GGK20, DKZ20] or restricted models such as correlational SQ [GGJ 20, DKKZ20J. Prior work hinted at the impossibility of our result: Vempala and Wilmes [VW19] showed that general SQ lower bounds cannot apply to any real-valued family of functions that satisfies a simple non-degeneracy condition. To circumvent their result, we refine lifting procedure due to Daniely and Vardi [DV21] that reduces Boolean PAC learning problems to Gaussian ones. We show how to extend their technique to other learn- ing models and, in many well-studied cases, obtain a more efficient reduction. As such, we also prove new cryptographic hardness results for PAC learning two- hidden-layer ReLU networks, well new lower bounds for learning constant- depth ReLU networks from label queries.
Introduction
In this paper we extend a central line of research proving cetrrseettttioinnepeeedeeee hardness results for learning classes of neural networks. We will consider arguably the simplest possible setting: given samples (æ1, y1)..... (In, yn) where for every i [n]. x, sampled independently from some distribution D over IRd and y; fx;) for unknown neural network Rd RR the goal to output any function / for which [z-D([((x)) {())) ) small. This model is often referred to as the realizable or noise-free setting.
This problem has long been known be computationally hard for discrete input distributions. For example, if 'D is supported over a discrete domain like the Boolean hypercube, then we have a vari- ety of hardness results based on cryptorrahhicaavrrgge.om assumptions [KS09, DLSS14, DSS16, DV20, DV21].
Over the last few years there has been a very active line of research the complexity of learning with respect to continuous distributions, the most widely studied case being the assumption that D is standard Gaussian in dimensions. A rich algorithmic toolbox has been developed for the Gaus- sian setting [JSA15, ZSJ+ 17, BG17, LY17, Tia17, GKM18, GLMI8, BJW19, ZYWG19, DGK 20, LMZ20, DK20, ATV21, CKM20, SZB21, VSS+22), but all known efficient algorithms can only handle networks with a single hidden layer, that is, functions of the form f f(x) E ) x)).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

This motivates the following well-studied question:
Are there Sundamenial burriers to learning neural networks with two hidden layers?
(1)
Two distinct lines of research, one using cryptography and one using the statistical query (SQ)
model, have made progress towards solving this question.
In the cryptographic setting, [DV21] showed that the existence of a certain class of pseudorandom generators, specifically local pscudorandom generators with polynomial stretch, implies superpoly- nomial lower bounds for learning ReLU networks with three hidden layers.
For SQ learning, work of [GGJ 20] and [DKKZ20] gave the first superpolynomial correlational SQ (CSQ) lower bounds for learning even one-hidden-layer neural networks. Notably, however, there are strong separations between SQ and CSQ [APVZ14, ADHV19, CKM20), and the question of whether general SQ algorithm exists remained an interesting open problem. In fact, Vempala and Wilmes [VW19] showed that general SQ lower bounds might be impossible to achieve for learn- ing real-valued neural networks. For any family of networks satisfying simple non-degeneracy condition (see Section 1.1), they gave algorithm that succeeded using only polynomially many statistical queries. As such, the prevailing conventional wisdom was that noise was required in the model obtain full SQ lower bounds.
The main contribution of this paper answer Question by giving both general SQ lower bounds and cryptographic hardness results (based on the Learning with Rounding or LWR assumption) for learning ReLU networks with two hidden layers and polynomially bounded weights. We note that our SQ lower bound is the first of its kind for learning ReLU networks of any depth. We also show how to extend our results to the setting where the learner has label query access to the unknown network.
Reference
Num. hidden layers
Model of hardness
[DKKZ20, GGJ+20]
Correlational SQ
Cryptographic
[DV21]
3
(assuming existence of local PRGs)
This work
2
Full SQ
Cryptographic
This work
2
(assuming hardness of LWR)
Table Summary of known and new superpolynomial lower bounds for learning noise-free shallow ReLU networks over Gaussian inputs up to sufficiently small (but non-negligible) error. (Definitions and terminology may be found in Appendix A.)
SQ Lower Bound We state an informal version of our main SQ lower bound:
Theorem 1.1 (Full SQ lower bound for two hidden layers (informal), see Theorem 3.1). Any SQ al- gorithm for learning
two-hidden-layy layer ReLU networks over (0, Ida) up to squared loss 1/ poly(d) d) must use at least d=(1) queries, or have query tolerance that is negligible in d.
We stress that this bound holds unconditionally, independent of any cryptographic assumptions. This simultaneously closes the gap between the hardness result of [DV21] and the positive results on one- hidden-layer networks [JSA 15, ZSJ+ 17, GLM18, ATV21, DK20] and goes against the conventional wisdom that one cannot hope to prove full SQ lower bounds for learning real-valued functions in the realizable setting.
We also note that unlike previous CSQ lower bounds which are based on orthogonal function fam- ilies and crucially exploit cancellations specific to the Gaussian distribution, our Theorem 1.1 and other hardness results in this paper extend to any reasonably anticoncentrated product distribution over Rd; see Remark C.5.
Cryptographic Lower Bound While Theorem 1.1 rules out most known approaches for prov- ably learning neural networks (c.g. method of moments/tensor decomposition [JSA15, ZSJ* 17,

---

GLMI8, BJW19, DGK 20, DK20, ATV2IJ, noisy gradient descent [BG17, LY17, Tia17, GKMI8, ZYWG19, LMZ20], and filtered PCA [CKM20]), it does not preclude the existence of non-SQ algorithm for doing so. Indeed, a number of recent works [BRST21, SZB21, ZSWB22, DK21] have ported algorithmic techniques like lattice basis reduction [LLLL82], traditionally studied in the context discrete settings like cryptanalysis, to learning problems over continuous domains for which there is no corresponding SQ algorithm.
Our next result shows however that under a certain cryptographic assumption, namely hardness of Learning with Rounding (LWR) with polynomial modulus [BPR12, AKPW13, BGM+16], no polynomial-tine algorithm can learn two-hidden-laye The LWR problem close cousin of the well-known Learning with Errors (LWE) problem [Reg09], except with deterministic rounding in place of random additive errors.
neural networks from Gaussian examples.
Definition 1.2. Fix moduli p. q E N. where < q. and let n be the security parameter. For any w E zy. define Jw : 2 - p by [w)( = 1
p [ x ælp = 3 (w x mod 4)}, where [t] is the closest integer to t. In the LWR.....g problem, the secret w is drawn randomly from Zy. and we must distinguish between labeled examples (z, y) where x ~ Σ and either y = fx( or y is drawn independently from Unif(Zp/p) LWE is similar, except that E Z,/9 / is either ((w-2 mod q) for some E B. sampled from a carefully chosen noise distribution, is drawn from (zg/(Zzg)))
Theorem 1.3 (Cryptographic hardness result (informal), see Theorem 4.1). Suppose there exists poly(d) (lydd)-time time algorithm for learning poly (d) -izeed two woo-iddeenllaerr ReLU networks over N(0, Ida) up to squared loss 1/ poly(d). Then there exists quasipolynonial-tine algorithm for LWR with polynomial modulus (i.e., in the regime where n = d. p, q = poly(n), and q/p po)y(n)).
Note that here we may actually improve the LWR hardness assumption required from quasipolyno- mial to any mildly superpolynomial function of the security parameter (see Remark 4.2).
Under LWR with polynomial modulus, we also show the first hardness result for learning one hidden layer ReLU networks over the uniform distribution on {0, 1}² (see Theorem 4.3).
We discuss existing hardness evidence for LWR well as its relation to more standard assump- tions like LWE in Appendix A.3. From a negative perspective, Theorem 1.3 suggests that the aforementioned lattice-based algorithms for continuous domains ing algorithms for two-hidden-layer networks, because even their more widely studied discrete counterparts have yet to break LWR. From a positive perspective, in light of the prominent role LWR and its variants have played in a number of practical proposals for post-quantum cryptography [CKLS18, BGML+ 18, JZ16, DKRVI8), Theorem 1.3 offers new avenue for stress-testing these schemes.
unlikely yield new learn-
Query Learning Lower Bound One additional benefit of our techniques is that they are flexible enough to accommodate other learning models beyond traditional PAC learning. To illustrate this, for our final result we show hardness of learning neural networks from label queries. In this setting, the learner is much more powerful: rather than sample or SQ access, they are given the ability to query the value (xx of the unknown function I at any desired point x in IRd and the goal is still to output function f for which [x( f()))²] is small. The expectation here is with respect to some specified distribution, which we will take to be (N00 Ida).
In recent years, this question has received renewed interest from the security and privacy communi- ties in light of model extraction attacks, which attempt to reverse-engineer neural networks found in publicly deployed systems [T]+ 16, MSDH19, PMG+ 17, JCB+20, RK20, JW720, DG21]. Recent work [CKM21] has shown that in this model, there is an efficient algorithm for learning arbitrary one-hidden--lyer ReLU networks that is truly polynomial in all relevant parameters. We show that under plausible cryptographic assumptions about the existence of simple pseudorandom function (PRF) families (see Section 5) which may themselves be based standard number theoretic or lattice-based cryptographic assumptions, such guarantee is impossible for general constant-depth ReLU networks.
Theorem 144 (Label query hardness (informal), see Theorem 5.1). If either the decisional Diffie- Hellman or the Learning with Errors assumption holds, then the class of poly(d)-sizer constant- depth ReLU networks from R2d to R is not learnable up to small constant squared loss e over N (0, Ida) even using label queries over all of Rd..
3

---

Note that the connection between PRFs and hardness of learning from label queries over discrete domains well-known connection dating back to Valiant [Val84]. To our knowledge, however, Theorem 1.4 is the first hardness result for query learning over continuous domains.
1.1 Discussion and Related Work
Hardness for learning neural networks. There are a number of works [BR89, Vu06, KS09, LSSS14, GKKT17, DV20] showing hardness for distribution-free learning of various classes of neural networks.
As for hardness of distribution-speccfic learning, several works have established lower bounds with respect to the Gaussian distribution. Apart from the works [GGJ+ 20, DKKZ20, DV21J from the introduction which are most closely related to the present work, we also mention the works of [KK14, GKK19, GGK20, DKZ20] which showed hardness for agnostically learning halfspaces and ReLUs, [Sha18] which showed hardness for learning periodic activations with gradient-base based meth- ods, [SVWX17] which showed lower bounds against SQ algorithms for learning me--hddeenllaer networks using Lipschitz statistical queries and large tolerance, and [SZB21] which showed lattice- based hardness of learning one- mee-idden-llyee networks when the labels y have been perturbed by bounded adversarially chosen noise. Our approach has similarities to the "Gaussian lift" as studied by Klivans and Kothari [KK14] Their approach, however, required noise in the labels, whereas we interested in hardness in the strictly realizable setting. We also remark that (DGKP20, AAK21] showed correlational SQ lower bounds for learning random depth-w(log n) neural networks over Boolean inputs which are uniform over halfspace.
There have also been works on hardness of learning from label queries over discrete domains and for more "classical" concept classes like Boolean circuits [Fe109, CGVI5, Val84, Kha95, AK95].
SQ lower bounds for real-valued functions. A recurring conundrum in the literature on SQ lower bounds for supervised learning has been whether one can show SQ hardness for learning real-valued functions, SQ lower bounds for Boolean functions are typically shown by lower bounding the sta- ristical dimension of the function class, which essentially corresponds to the largest possible set of functions in the class which are all approximately pairwise orthogonal. Indeed, the content of the hardness results of [GGJ 20, DKKZ20] of -aeeedddee-llyer networks. Unfortunately, for real-valued functions, statistical dimension lower bounds only imply CSQ lower bounds. As discussed in [GGJ+20], the class of d-variate Hermite polynomials of degree-l is pairwise orthogonal and of size d0((), which translates to CSQ lower bound of (f)) Yet there exist SQ algorithms for learning Hermite polynomials in far fewer queries [APVZ14, ADHV19].
prove lower bounds the statistical dimension
Further justification for the difficulty of proving SQ lower bounds for real-valued functions came from [VW19]. which observed that for any real-valued learning problem satisfying a seemingly in- coampptionnnmelle that for any pair of functions f. g in the class, the
nocuous non-degeneracy probability under the input distribution that f(x) g(x) zero-there an efficient "cheating" SQ algorithm (see Proposition 4.1 therein). The SQ lower bound shown in the present work circum-
vents this proof barrier by exhibiting a family of neural networks for which any pair of networks agrees on a set of inputs with Gaussian measure bounded away from zero.
Open question. All known positive results for one hidden layer that run in time polynomial in all parameters require various assumptions on the underlying network. This leaves open the tantalizing possibility of strengthening our results to apply to worst-case one hidden layer networks.
1.2 Technical Overview
Our work will build recent approach of Daniely and Vardi [DV21], who developed simple and clever technique for lifting discrete functions to the Gaussian domain entirely in the realizable setting. Our main contributions are (1) make their lifting procedure more efficient that two hidden layers suffice and (2) show how to apply the lift in a variety of models beyond PAC. For the purposes of this overview we will take the domain of our discrete functions to be {0, 1) but our techniques extend to こ with (oly(d).

---

Daniely-Vardi (DV) lift. At high level, the DV lift is transformation mapping a Boolean ex- ample (z. y) labeled by hard-to-learn Boolean function f to a Gaussian example (z, y) labeled by a (real-valued) ReLU network fov that behaves similarly to f in that (z) approximates (sign(z)), where for us sign(t) denotes 1 > 0] and is applied elementwise. The key idea is to use continuous approximation sign of the sign function, and pair it with "soft indicator" function bad R - R. that is large whenever sign(z) * sign(2), and that can be implemented as a one- hiyden-layer network independent of the target function. One can show that whenever ff is realizable as L-hidden-lay layer network over {0, 1]d, the function fou ReLU(((sign(())) - bad( 2)) can be implemented as an (L + 2)-hidden-layer network satisfying
jDv (z) (eii((()) bad(z)).
This property allows us to generate synthetic Gaussian labeled examples (z, fDV (2)) from Boolean labeled examples (x, (z)). and thereby reduce the problem of learning that of learning fou.
Improving the DV lift. Our first technical contribution is to introduce more efficient lift which only requires one extra hidden layer. Our starting point is to observe that a variety of hard-to-lear Boolean functions/ ʃ like parity and LWR take the form (x) a(((x=) for some ReLU network whose range T over Boolean inputs is discrete subset of [0, poly(d) of polynomially bounded size, and for some function a T + [0, For such compressible functions (see Definition 2.1), one can write f(x) = (h(()) = Er ((t)
= t*. Again, we would like to implement lifted function få Rdd T using sign and bad that it approximates f(sign(z)) except when bad indicates that sign + sign. To this end, we might hope to implement, say,
0²( - Σ (((ggi((s))))()) ["j bad(z;) < 1].
EET
Here we now view bad as a univariate function, and whenever small, we can be sure sign sign. Suppose that we could build a one-hidden-layer network N.
S8; () that behaves like 1 = 0] : 8j & 1]. Then we could realize f as an (I. + 1)-hidden-layer network:
(=)) = Σ (bad))( (2.).... bad(za); h(sign(=) - 1*).
EE
While many natural attempts to build such an N run into difficulties, we construct a suitably relaxed version of N that turns out to suffice for the reduction. To gain some intuition for our construction, the starting observation is that the following mnclsion--xcllsion type formula vanishes identically whenever any of the sy is 1:
(i 82, 83) (1, (11, 1, (2,1, + (81, 1, + (11, 82, 1) + (81, - (1,1,,
For a suitable choice of ei, one might hope to build N out of such a formula by taking sy = bad 22y) for every j. But the natural generalization of this expression to d inputs would have size 2d, which runs the risk of rendering the resulting SQ lower bounds vacuous. Our final construction (Lemma 2.6) instead resembles a truncated inclusion-exclusin mial size, which may be of independent interest. Since the SQ lower bounds for Boolean functions that we build on are exponential, by a simple padding argument we still obtain a superpolynomial SQ lower bound for our lifted functions.
type formula of only quasipolyno-
Hard one-hidden-layer Boolean functions and LWR. To use this lift for Theorems 1.1 and 1.3, we need one- miedeidde-- networks that are compressible and hard to learn over uniform Boolean inputs. For SQ lower bounds, we can simply start from parities, for which there are exponential SQ lower bounds, and which turn out be easily implementable by compressible hid-hidden-llyer networks. For cryptographic hardness, Daniely and Vardi [DV2i] used certain one-hidden-layee Boolean networks that arise from the cryptographic assumption that local PRGs exist (see Section 1.4.1 therein). Unfortunately, these functions are not compressible. For this reason, we work instead with LWR: turns out that the LWR functions are compressible and, conveniently, the hardness assumption directly involves uniform discrete inputs.
5

---

Hardness beyond PAC. While the DV lift is priori only for showing hardness of example-bate based PAC learning, we can extend to the SQ and label query models by simple simulation arguments.
2 Compressing the Daniely-Vardi Lift
In this section we show how to refine the lifting procedure of Daniely and Vardy [DV21] such that whenever the underlying discrete functions satisfy property we term compressibility, we obtain hardness under the Gaussian for networks with just one extra hidden layer.
Definition 2.1. g > 0 be a modulus." We call an L-hidden-layer ReLU network f 2 - [0, 1]
compressible if it is expressible in the form f(x) = (h((2)), where
h Z + T is (L- 1)-hidden-layer network such that [h(=)) - poly(d) for all æ;; h has range T (ZØ) such that T C Z and [T] S poly(d); and
a [0, 1] is a mapping from h's possible output values to [0, 1].
Remark 2.2. To see why such an is L-hidden- -laee network in 2, consider the function o T + R. Because T C E and [T' S poly(d), a is expressible as (the restriction to T of) a piecewise linear function R whose size and maximum slope are poly(d), and hence as poly(d)-sized mme-hidden-layer ReLU network from I to R. By composition, x + (h(x)) can be represented by an l-yidden-layer network.
We now formally state theorem which captures our "compressed" version of the DV lift. The version of this theorem for L + layers is implicit in [DV21]. In technical terms, our improvement consists of removing the single outer ReLU present in their construction. Thus, while our construc- tion still has three linear layers, it has only two non-linear layers. By a standard padding argument, we also obtain Corollary C.6, which lets work with polynomial-sized neural networks.
Theorem 2.3 (Compressed DV lift). Letq= poly(() be a modulus. Let C be a class of compressible L-hidden-layer layer poly(d)-sizee ReLU networks mapping 2ÿ to [0, 1]. Let m = m(d) = wa(1) be a size parameter that grows slowly with d. There exists a class C (L 1--hidden-layer (m)) sized ReLU networks mapping R2 to [0. 1] such that the following holds:
Suppose there is an efficient algorithm A capable of learning Ca over N ( Ida) up to squared loss d- -((m), Then there is efficient algorithm B capable of weakly predicting C over (nif with advantage d' d0)(m) over guessing the constant 1/2 in the following sense: given access to labeled examples (xx, f(x)) for x Uni and an unknown f E C, B satisfies E [B((z) f(x)) E =()=)(x)) 2 d dmm(),,, where the probability is taken over both x and the internal randomness of B. We refer to C as the lifted class corresponding to C.
The proof of Theorem 2.3 leverages certain -lehiddeenllyyer gadgets. The first two gadgets are inherent to the original DV lift (extended to work with general 2, as opposed to just {0, 1}), while the third is one of our main technical contributions and essential to obtaining an improvement in depth. Proofs are deferred to Appendix C.
Start by letting To, J,,..., : T- be partition of IR. into q consecutive intervals each of mass 1/9 under No 1) (e.g.. when q = 2, To = (-o0, 0) and J = (0, oo)). Note that these intervals will have differing lengths, which we denote by |Ty]. and the shortest ones will be the ones closest to the origin. Still, by Gaussian
connncnntntttion, we know that each [T,] 2 0(1 Let thres, : R- -2, be the piecewise constant function that takes on value k on I.. Clearly, when ~ NN 1). thres,()) ~ Unif((Z,). ). Let RI,..., Ri be intervals such that R& C 1 U In and Rg contains the boundary point between TR-1 and It. and such that each Rs has mass 8/g for some 5 < 1 to be picked later. Let Si...., Sy be slightly larger intervals such that R₂ C S₁ for each k E [q 11, and each Sg has mass 25/q. By Gaussian anti- coneentrennnnn again, each Sy 2 (88/q). Notice that by construction, P==A(0.1)]2 E Rx = and P=~N(o,1) E S+ = 26.
Lemma 2.4. Lei > 0, g > O, and intervals Is, Re, Sp. for k E Zn be as above. There exists a one-hidden--ayer ReLU network N1 IR - TR with O(g) unity and weights of magnitude O(g/d)
such that (t) = thress, (t) if & Ug
Our results are stronger when is taken to be a large polynomial in the dimension, but the Boolean g = 2 case is illustrative of all the main ideas.

---

Lemma 2.5. Let ò > 0, > O, and intervals Is. Rg. Sk for k Zg be as above. There exists eme-hidden-laye ReLU network N₂ : [0, 1] with O(q) units and weights of magnitude O(q/ such that
ifte U.R
N2(1) is
= VTER\URS,
20 otherwise
Note that when q = 2, N2 and N2 play the role of "sign" and "bad" from the technical overview. To motivate the third gadget, recall from the technical overview that one might hope to build Nz($1..... 8d; t) that behaves like [[ [jj : 8j < Slightly more generally, one can show that it would suffice to build one- one-hidden-laye network N3 with the following properties:
0 if s)
N5(11. ... ips
0
if E 2 {0}
if :8 =
and = 0
Unfortunately, most natural attempts to construct N3 with such ideal properties run into difficulties and appear require two hidden layers (see Appendix D for discussion).
The key idea that lets us make progress is to restrict attention to those possibilities for ($1,..., sd) (NV(21),.... N2(22) (za)) that are the most likely. Specifically, if m wa(1) is the size parameter from Theorem 2.3, then by setting in Lemmas 2.4 and 2.5 appropriately, we can ensure that with overwhelming probability
-N(0,, Id), more than m of the N2)z are simultaneously 1. Accordingly, we focus on constructing N3 such that
0
if between 1 and m of the 8; are
................................ sa: Nu($1....,,$a
0
if Z {0}
otherwise
Our construction for N3 has size d9(m), and satisfies the first and second properties exactly. It also "approximately" satisfies the third in the sense that it takes on a nonzero value with nonnegligible probability over its inputs. As we will see, this turns out to be enough for the reduction to go through. And even though the size of N3 is slightly superpolynomial in the dimension, because the SQ lower bounds for Boolean functions that we build on are exponential, by a simple padding argument we will still obtain superpolynomial SQ lower bound for our lifted functions.
Lemma 2.6 (Main lemma). Let m m(d) = wa(1) be a size parameter. There exists a one-hidden- layer neural network Ng Rd R IR. such that
(a) N3 Sdi t) = for any E IR if between I and m of the s, are
(b) N8(81,..., Sa;
t) for any "1....,88
8a E [0, 11d ift Z {0}
(c) Na has size at most d2m
(d) N3(O....,,00 8; = 8 for any E [0, 1l (there are d zerves in front s).
Proof sketch of Theorem 2.3. For each f E given by f = o let fa E EC be given by
(² Σ ((N)))(N Na(aa) ((N((z)) - t*), eEr
where N1 and N2 are from Lemmas 2.4 and 2.5, with the å parameter set to d-10m, and N3 is from Lemma 2.6. This is an (L+1) (L+1)-hidden layer network since No and N2 each have at most L hidden layers, and N₂ adds additional layer. By Lemma 2.6(c), the size of this network is S (mm). Note that for such that (2)2)).... Na(za) < 1, we have N1(2) = thres,(2), and the only t" for which one of the summands in Eq. (4) is potentially nonzero is the one given by t" h(thres,(2)) So in this case fā simplifies to
(5) Further, for a such that between and m of the N2(2,) are 1, we know that (NN2(=))..... .... (z(2)); t) = 0 identically (for all E IR), so in this case (2 0. And finally, for
(2) = (thrre, (N( No(za): : 0).
7

---

such that more than m of the (2,),) are I, we have guarantees on the behavior of fo, but as we now show, we have set parameters such that this case occurs only with negligible probability, and we can pretend that 0 is still valid label in this case. Indeed, by standard Gaussian anti-concentration, for each coordinate 2j we have ss [N(2z) =
d-10mm The number of coordinates j for which N2(zz) = thus follows a binomial distribution B(d, d-10mm), which has decreasing pdf with unique mode at [[d + 1)d 10m 0. Thus the probability of having at least m 1s is at most
IP=, [2g E U2 RR]
Σ ( (a-10mm 10m-10mppe - d-10mmd-+ I (d m + 1) (d) d 1-10m²
d
S ddd d- d=10m²
I dmmm
(6)
for sufficiently large d. This negligibly small not only but also in == (9())
We now describe the reduction. For each labeled example (a; y) that the discrete learner B receives,
where x ~ (z)) and f(x) for an unknown f E C. B forms a labeled example (2. y) for the Gaussian learner A as follows. For each coordinate j E [d]] 2j is drawn from / (0, 1) conditioned on 2j Izy- Notice that this way thres,(2) z, and the marginal distribution is exactly Na-
The modified label is given by
O
if more than m of the N2(2,) are if between and m of the N2(2;) are 1 otherwise
5 - -v,
No. N2(a)) 0)
Note that in the bottom two cases, T = (z) exactly; in the top case ÿ in general inconsistent with f but as we have seen, this case occurs with negl(S) probability. In particular, with overwhelming probabilityy, pS (S-)time algorithm will ever see non-realizable samples.
So B can feed these new labeled examples (z, 7/ to A. Suppose A outputs hypothesis f R R such that Eg [[{()) (=))²] < e. We need to show can convert this hypothesis into nontrivial one for its discrete problem. We first define "good region" G C Idd where fc is guaranteed to be nonzero and nontrivially related to the original f by saying 2 E G iff N2(2)).... ..., (2a-11)) Lemma 2.6(d) we have
and N2(za) E 2) Observe that when E G. by Eq. (5) and
(z) = (( (zaa):
yNNzza),
(8)
where we use the fact that (2ros,(2)
that f(thros,(2)) f(x)= = y.
One can show that G has non-negligible probability mass. The discrete learner B can now adapt as follows. Given a fresh test point x ~ (z the learner forms = 2(x) such that for each coordinate j E [d], is drawn from N/00 1) conditioned on 2j E Ing. If E G, then B predicts y = (2(=a) (recall that when & E 2, N2(za) > 2d), and otherwise simply predicts ÿ = } By exploiting the fact that this is a good prediction at least on the region G, it is not hard to show that H's overall square loss is non-negligibly better than random.
f(z)
3 Statistical Query Lower Bound
We prove a superpolynomial SQ lower bound (for general queries as opposed only correlational or Lipschitz queries) for weakly learning two-hidden-Le layer ReLU networks under the standard Gaus- sian. We obtain this by lifting the problem of learning parities under Ua, which well-known to require exponentially many queries.
Theorem 3.1. Fix any a E (0. 1). Any SQ learner capable of learning poly(d) siszed) sized two-hidden- layer ReLU networks under (0, Ida) up to squared loss E (for some sufficiently small & =
1/ (oly(d)) using bounded queries of tolerance 2 2 2 d)2-a must use at least (222 do(1), 7 such queries.
72)
8

---

This theorem is proven using the following key reduction, which adapts the compressed DV lift (Theorem 2.3) to the SQ setting. The proof is deferred Appendix E.
Theorem 3.2. Let q = poly(d) be modulus, and let m m(d) = wa(1) be a size parameter Let C. be class of compressible I--hidden-aaye -laeer poly(d)-sized ReLU networks mapping 2ig to [0. 1). and let Ca be the lifted class of (L + 1)-hidden-laye dized sized ReLU networks corresponding to C. mapping TR.d R (as in Theorem 2.3). Suppose there an SQ learner A capable of learning C over ((0 Ida) up to squared loss d d using queries of tolerance т, where T Z d d=0(m²)
Then there is SQ learner B that, using the same number of queries of tolerance r/2, produces weak predictor B for C over (n) with advantage d (mmm over guessing the constant 1/2 (in expectation over both the data and the internal randomness of B).
Proof of Theorem 3.1. Let m = m(d)= = log" d c 1, and let d' = d = 2 ++ d, so
that d = 2/0g (0++) d'. It is easy to see that the class of parities on {0, 10 can be implemented by compressible one-hidden-layer poly(d)-sized ReLU networks. Indeed, for any S C [d] recall that xx)x) = 1{ Ti is odd), which is a compressible one-hidden-layer network with the inner depth-O network being x + Eses I.y and ott) = 1[t is odd]. Thus the lifted class C can be implemented by two-hidden-lag layer d0(m) ReLU networks over Rdd padding argument lets us embed these classes into dimension d'. By using the predictor from Theorem 3.2 (with 2). we obtain an SQ algorithm capable of distinguishing parities from random labels using queries of
2=13
tolerance T 7/2, assuming T 2 d (mm) 2 log log2 d 2 log ott d' It is well-known [Kea98,
BF]+94] that the lower bound for learning parities is (2)2 which becomes 9(22 2 1(1+)) of Substituting a = Itc gives the result.
By way of an alternative construction that arguably remains hard even for non-SQ algorithms, in Appendix F we provide a different proof of this SQ lower bound using the LWR functions in place of the parities. We stress that this alternative proof remains unconditional and relies only on the LWR function family, not on the LWR hardness assumption itself.
4 Cryptographic Hardness Based on LWR
In this section we show hardness of learning two-hidden- layer ReLU networks over Gaussian inputs based on LWR. This is a direct application of the compressed DV lift (Theorem 2.3) to the LWR problem, which by definition a hard learning problem over (n))
Theorem 4.1. Let be the security parameter, and fix moduli q 2 1 such that p, q poly(n) and p/q = poly(n). Let d n. Let c. > O, m = m(d) = log" d and d' d Suppose there exists a poly(d") algorithm capable of learning (o'y -iized depth-2 ReLU networks under (O, Idar) up to squared loss 1/ poly(d'). Then there exists a poly(d') 20 time algorithm for LWR..p..
Proof. We claim that the class CLWR is implementable by compressible poly(d)-sized one-hidden- layer ReLU networks over zz. or, after padding, over zi² Indeed, by definition we have f.) = [((w=z) mod qlp- which is compressible one-hidden- layer ReLU network with the inner depth-0 network (i.e., affine function) being w + w x and (t)) = !
n [ mod 41p Let CLwR denote the corresponding lifted class of poly poly(d") (d')-sized two-hidden-layer ReLU networks, padded to have do- main Rd Applying Corollary C.6 the assumed learnrr for CiWR, we obtain poly(d')- -timm weak predictor predictor for CLWR, which readily yields a corresponding distinguisher for the LWR..p.4 problem. Using the facts that d' T 2log' and d n, we may translate (dly into 20(log" +o **n), yielding the result.
Remark 4.2. Note that the choice of m = m(d) = log" d in Theorem 4.1 is purely for simplicity. By picking m(d)- wa(1) (1) to be suitably woowing function of d, such as log" d, we can obtain running time for the final LWR algorithm that is as mildly superpolynomial as we like.

---

In addition, we also obtain hardness result for one-hidden- networks under Unif (0, 1 im- proving on the hardness result of [DV21] (see Theorem 3.4 therein) for hwo-hidden-layer networks under Unif (0, 1]a For this application, we let d = n log q = Ö(n). so that we may identify the do- main Z with {0, 13d via the binary representation. This also identifies Uni with Uni 1)". Corollary 4.3. Let n. P.q be such that p.q = poly(n) and p/q = poly(n), and let d = n log q = (n)) Suppose there exists an efficient algorithm for learning poly(d) one-hidden-layer ReLU networks under Ua up to squared loss 1 1/4. Then there exists efficient algorithm for LWRm.
5 Hardness of Learning using Label Queries
Here we show hardness of learning constant-depth ReLU networks over Gaussians from label queries by lifting pseudorandom function (PRF) families. For preliminaries PRFs and their con- nection to hardness of learning, see Appendix A.4. Since PRFs are not necessarily compressibile, will simply the original DV lift (Theorem B.1).
Theorem 5.1. Assume there exists a family of PRFss mapping {0, 1] to {0,1} implemented by poly(d)-sizee (didd L-hidden-layer ReLU networks. Then there does not exist an efficient learner that, given query access to unknown poly(d)-sizer) (L + 2) -2iddeedd---ayy layer ReLU network f RR - R, is able to output a hypothesis h. Rd - IR such that Ee,~A((,,aa) (()()) [(=))²] < 1/16.
Proof. Let f. 10. - {0, 1} be unknown L-hidden-layer ReLU network obtained from the PRF family by picking the key s at random. Consider the lifted (L+ ---d)--iddennllyyr ReLU network fov Rd + I from Eq. (10), given by (2) = ReLU(fa (x)) - [z))),, where N1 and N₂ are from Lemmas 2.4 and 2.5, and (2(22) = / N2(2z). Suppose there were efficient learner A capable of learning functions of the form foV using queries. By the DV lift (Theorem B.I,, A yields efficient predictor В achieving small constant error w.r.t. the unknown fs, contradicting Lemma A.3. We only need to verify that A's query access to fov can be simulated by B. Indeed, suppose A makes a query to /DV at a point = E Rdd Then B can make a query to fe at the point sign(z) and return ReLU (()ign(()) N²)) fDV. This completes the reduction and proves the theorem.
(P)()), as this was the key property satisfied by
Acknowledgments and Disclosure of Funding
We would like to thank our anonymous reviewers for pointing out an issue in the first version of our proof. Part of this work was completed while the authors were visiting the Simons Institute for the Theory of Computing. SC is supported in part by NSF Award 2103300. AG and ARK are supported by NSF awards AF- 1909204, 1F-1717896, and the NSF AI Institute for Foundations of Machine Learning (IFML). RM is supported by NSF CAREER Award CCF-1553605.
References
[AAK2I] Naman Agarwal, Pranjal Awasthi, and Satyen Kale. A deep conditioning treatment of neural networks. In Algorithmic Learning Theory, pages 249-305. PMLR, 2021. 1.1
[ADHV19] Alexandr Andoni, Rishabh Dudeja, Daniel Hsu, and Kiran Vodraballi. Attribute- efficient learning of monomials over highly-coreelatdd variables. In Algorithmic Learning Theory, pages 127-161. PMLR, 2019. 1, 1.1
[AK95] Dana Angluin and Michael Kharitonov. When won't 't membership queries help? Jour- nal of Computer and System Sciences, 50(2):336-355, 1995. 1.1
[AKPW13] Joël Alwen, Stephan Krenn, Krzysztof Pietzzak, and Daniel Wichs. Learning with rounding, revisited. In Annual Cryptology Conference, pages 57-74. Springer, 2013.
A.3
[APVZ14] Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning sparse polynomial functions. In Proceedings of the twenty-fitth annual ACM-SIAM sympo- sium Discrete algorithms, pages 500-510. SIAM, 2014. 1, 1.1
10

---

[ATV21] Pranjal Awasthi, Alex Tang, and Aravindan Vijayaraghavan. Efficient algorithms for learning 2 neural networks with general relu activations. Advances in Neural Information Processing Systems, 34, 2021. 1, 1,
[BF]+94] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning us- ing fourier analysis. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 253-262, 1994.
[BG17] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine crarning-Volume 70, pages 605-614, 2017. 1,
[BGM 16] Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen. On the hardness of learning with rounding over small modulus. In Theory of Cryptogra- phy Conference, pages 209-224. Springer, 2016. A.3, A.2, A.3
[BGML+ 18] Sauvik Bhattacharya, Oscar Garcia-Morchon, Thijs Laarhoven, Ronald Rietman, Markku-Juhani Saarinen, Ludo Tolhuizen, and Zhenfei Zhang. Round5: Compact and fast post-quantum public-key encryption. IACR Cryptol. ePrint Arch., 2018:725, 2018. A.3
[BIP 18] Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J Wu. Exploring crypto dark matter. In Theory of Cryptography Conference, pages 699-729. Springer, 2018. A.4
[BJW19] Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195- 268. PMLR, 2019. 1,
[Bog21] Andrej Bogdanov. Personal communication. 2021. F
[BP14] Abhishek Banerjee and Chris Peikert. New and improved key-homomorphic pseudo- random functions. Annual Cryptology Conference, pages 353-370. Springer, 2014.
A.4
[BPR12] Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In Annual International Conference on the Theory and Applications of Cryp- tographic Techniques, pages 719-737. Springer, 2012. 1, A.3, A.4
[BR89] Avrim Blum and Ronald I. Rivest. Training a 3-node neural network is np-complete. In Advances in neural information processing systems, pages 494-501, 1989. 1.1
[BR17] Andrej Bogdanov and Alon Rosen. Pseudorandom functions: Three decades later. In Tutorials on the Foundations of Cryptography, pages 79-158. Springer, 2017. A.4, F
[BRST21] Joan Bruna, Oded Regev, Min Jae Song, and Tang. Continuous lwe. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 694 707, 2021.
[CGV15] Aloni Cohen, Shafi Goldwasser, and Vinod Vaikuntanathan. Aggregate pseudoran- dom functions and connections to learning. In Theory of Cryptography Conference, pages 61-89. Springer, 2015. 1.1
[CKLS18] Jung Hee Cheon, Duhyeong Kim, Joohee Lee, and Yongsoo Song. Lizard: Cut off the tail! a practical post-quantum public-key encryption from Iwe and lwr. In In- ternational Conference on Security and Cryptography for Networks, pages 160-177. Springer, 2018. 1, A.3
[CKM20] Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep relu networks is fixed- parameter tractable. arXiv preprint MxXiv:2009.335/4 2020. 1,
[CKM21] Sitan Chen, Adam Klivans, and Raghu Meka. Efficiently learning one hidden layer relu networks from queries. Advances in Neural Information Processing Systems, 2021. 1
11

---

[DG21] Amit Daniely and Elad Granot. An exact poly-time membership-queries algorithm for extraction a three-layer relu network. arXiv preprint arXiv:2105.09673, 2021.
[DGK*20] Iliss Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. In Conference on Learn- ing Theory, 2020. 1,
[DGKP20] Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, and Rina Panigrahy. On the learn- ability of random deep networks. In Proceedings of the Fourteenth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 398 410. SIAM, 2020. 1.1
[DK20] Ilias Diakonikolas and Daniel M. Kane. Small covers for near-zero sets of polyno- mials and learning latent variable models. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 184-195, 2020. 1,
[DK21] Ilias Diakonikolas and Daniel M. Kane. Non-gaussian component analysis via lattice basis reduction, 2021.
[DKK720] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning onc-hidden-layer relu networks. In Conference on Learning Theory, pages 1514-1539, PMLR, 2020. (document), 1, ??, 1.1, 1.1
[DKRV18] Jan-Pieter D' Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Ver- cauteren. Saber: Module-Iwr based key exchange, cpa-secure encryption and cca- secure kem. In International Conference on Cryptology Africa, pages 282-305.
Springer, 2018. A.3
[DKZ20] Ilias Diakonikolas, Daniel M Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. arXiv preprint arXiv:2006. 16200, 2020. (document), 1.1
[DLSS14] Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complex- ity to improper learning complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 441-448, 2014.
[DSS16] Amit Daniely and Shai Shalev-Shwarzz. Complexity theoretic limitations on learning dnf's. In Conference on Learning Theory, pages 815-830. PMLR, 2016.
[DV20] Amit Daniely and Gal Vardi. Hardness learning neural networks with natural weights. Advances in Neural Information Processing Systems, 33, 2020. 1.1
[DV21] Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning. In Conference on Learning Theory, pages 1358-1394. PMLR, 2021. (doc- ument), 1, 1, ??, 1, 1.1, 1.2, 1.2, 2, B.1,
[Far19] Mike Farnest. Proving an identity involving the alternating sum of products of bi- nomial coefficients. Mathematics Stack Exchange, 2019. URL: https://math.
stackexchange.com.. wwt.co//////c////// (version: 2019-02-11), C.2
[Fe109] Vitaly Feldman. On the power of membership queries in agnostic learning. The Journal of Machine Learning Research, 10:163-182, 2009. 1.1
[GGJ+20) Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradi- ent descent. In International Conference Machine Learning, pages 3587-3596 PMLR, 2020. (document), 1, ??, 1.1, 1.1
[GGK20] Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33, 2020. (document), 1.1
[GKK19] Surbhi Goel, Sushrut Karmalkar, and Adam Klivans. Time/accuracy tradeoffs for learning a relu with respect to gaussian marginals. In Proceedings of the 33rd Inter- national Conference on Neural Information Processing Systems, pages 8584-8593, 2019. 1.1
12

---

[GKKT17] Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the relu in polynomial time. In Conference on Learning Theory, pages 1004-1042. PMLR, 2017. 1.1
[GKM18] Surbhi Goel, Adam R. Klivans, and Raghu Meka. Learning one convolutional layer with overlapping patches. In ICML, volume 80, pages 1778-1786. PMLR, 2018. I,
[GLMI8] Rong Ge, Jason Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. In 6th International Conference on Learning Representations, ICLR 2018, 2018. 1,
[3MP**3] András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits of bounded depth. Journal of Computer and System Sciences, 46(2):129-154, 1993. A.4
UCB+20) Matthew Jagielski, Nicholas Carlini, David Berthelot, Alex Kurakin, and Nicolas Pa- pernot. High accuracy and high fidelity extraction of neural networks. In Srdjan Capkun and Franziska Roesner, editors, 29th USENIX Security Symposium, USENIX Security 2020, August 12-14, 2020, pages 1345-1362. USENIX Association, 2020.
[JSA15] Majid Janzamin, Hamie Sedghi, and Anima Anandkumar. Beating the perils of non- convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv: /50.. 08473, 2015. 1, 1,
JWZ20] Rajesh Jayaram, David Woodruff, and Qiuyi Zhang. Span recovery for deep neural networks with applications to input obfuscation. In ICLR. OpenReview.net, 2020. 1
[JZ16] Zhengzhong Jin and Yunlei Zhao. Optimal key consensus in presence of noise. arXiv preprint 1r1.0:1611.061000 2016. A.3
[Kea98] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), (5(6):883-100) 1006, 1998. 3, A.2
[Kha95] Michael Kharitonov. Cryptographic lower bounds for learnability of boolean func- tions on the uniform distribution. Journal of Computer and System Sciences, 50(3):600-610, 1995. 1.1
[KK14] Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaus- sian space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANOOM 2014). Schloss Dagstuhl-Leibmn Zentrum fuer Informatik, 2014. (document), 1.1,
[KL01] Matthias Krause and Stefan Lucks. Pseudorandom functions in in tcO and crypto- graphic limitations to proving lower bounds. computational complexity, 10(4):297- 313, 2001. A.4
[KS09] Adam R Klivans and Alexander A Sherstov. Cryptographic hardness for learning intersections halfspaces. Journal of Computer and System Sciences, 75(1)2--1, 2009. 1.1
[LLL82] Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische annalen, 261:515-534, 1982. I
[LMZ20] Yuanzhi Li, Tengyu Ma, and Hongyang R. Zhang. Learning over-parametrized two- layer neural networks beyond ntk. In Conference on Learning Theory 2020, volume 125, pages 2613-2682. PMLR, 2020. 1,
[LSSS14] Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. Advances in Neural Information Processing Systems, 27:855-863. 2014. 1.1
[LY17] Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances Neural Information Processing Systems 30, pages 597-607, 2017. 1,
13

---

[MSDH19] Smitha Milli, Ludwig Schmidt, Anca D. Dragan, and Moritz Hardt. Model recon- struction from model explanations. In FAT. pages 1-9. ACM, 2019. 1
[NR97] Moni Naor and Omer Reingold. Number-theereetc constructions of efficient pseudo- random functions. In Proceedings 38th Annual Symposium on Foundations of Com- puter Science, pages 458 467. IEEE, 1997. A.4
[Pei16] Chris Peikert. A decade of lattice cryptography. Found. Trends Theor. Comput. Sci., 10(4):283-424, mar 2016. A.3
[PMG 17] Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning- In Ramesh Karri, Ozgur Sinanoglu, Ahmad-Reza Sadeghi, and Xun Yi, editors, Pro- ceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS 2017, Abu Dhabi, United Arab Emirates, April 2-6, 2017, pages 506-519, ACM, 2017.
[PSP17] PSPACEhard. Alternating of binomial coefficients identity. Mathematics Stack Exchange, 2017. URL: https://mathh: httpa//tcctcccaaaceee//a//////2/ com/q/2183223 (ver-
htap:://mtth.ssaakkrchagggg
sion: 2017-03-12). C.2
[Raz92] Alexander A Razborov. On small depth threshold circuits. In Scandinavian Workshop on Algorithm Theory, pages 42-52. Springer, 1992. A.4
[Reg09] Oded Regev, On lattices, learning with errors, random linear codes, and cryptography.
Journal of the ACM (JACM), 56(6):1 1-10, 2009. 1
[Reg10] Oded Regev. The learning with errors problem. Invited survey in CCC, 7(30)11,, 2010. A.3
[Rey20] Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applica- tions. arXiv preprint arXiv:2004.0055 2020. A.2
[RK20] David Rolnick and Konrad P. Kording. Reverse-engineering deep relu networks. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 8178-8187 PMLR, 2020.
[RR97] Alexander A Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. A.4
[Sha18] Ohad Shamir. Distribution-specife hardness of learning neural networks. The Journal of Machine Learning Research, 19(1): 135-116,, 2018. 1.1
[SVWX17] Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learn- ing neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5520-5528, 2017. 1.1
[SZB21] Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. arXiv preprint arXiv:2 10744, 2021. 1, 1, 1.1
[Tia17] Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. Proceedings of the 34th International Conference on Machine Learning, ICML 2017, volume 70, pages 3404-3413. PMLR, 2017. 1,
[T) 16] Florian Tramèr, Fan Zhang 0022, Ari Juels, Michael K. Reiter, and Thomas Risten- part. Stealing machine learning models via prediction apis. CoRR, abs/1609.0294. 2016. 1
[Va184] Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-111 1984. 1, 1.1,
[VRPS21] Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. Size and depth separation in approximating natural functions with neural networks. arXiv preprint arXiv:2 102.0311 2021. A.4
14

---

[VSS*22] Kiran Vodrahalli. Rakesh Shivanna, Mahesh Sathiamoorthy, Sagar Jain, and Ed Chi. Algorithms for efficiently learning low-rank neural networks. 2022.
[Vu06] VH Vu. the infeasibility training neural networks with small mean-squared error. IEEE Transactions on Information Theory, 44(7):2822-2000, 2006. 1.1
[VW19] Santosh Vempala and John Wilmes. Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds. In COLT, volume 99, 2019. (document), 1.1
[ZS] + 17] Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit Dhillon. Recov- ery guarantees for one-hidden-layer neural networks. In International conference on machine learning, pages 4140-4149, PMLR, 2017. 1,
[ZSWB22] llias Zadik, Min Jae Song, Alexander S. Wein, and Joan Bruna. nattice-based methods surpass sum-of-squares in clustering, 2022.
[YWG119] Xiao Zhang. Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden- layer relu networks via gradient descent. The 22nd International Conference on Artificial Intelligence and Statistics, pages 1524-1534. PMLR, 2019. 1, 1
15

---

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 open question in Section 1.1.
(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]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are present
in either the main body or the forthcoming supplement.
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 using existing assets (e.g., code, data, models) 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 or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 'r using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able 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]
16


Reviews:
[{"review_id": "lb-HvYr3wdC", "reviewer": "Reviewer_uQ7v", "summary": "The authors prove statistical query lower bounds for learning polynomial-sized neural networks with two hidden layers. The bound is superpolynomial in the input dimension $d$ (or the query tolerance is negligible in $d$). No cryptographic assumptions are needed for these bounds to hold. The authors also show that, under the learning with rounding with polynomial modulus cryptographic assumption, no polynomial-time algorithm can learn neural networks with two hidden layers from Gaussian examples. The result is extended to neural networks with one hidden layer over the uniform distribution on the boolean hypercube. ", "questions": "### Suggestions\n\nA conclusion should be included in the main body were the paper to be accepted. If there is room, a table comparing different lower bounds setting and contrasting the current paper with related work would be a great addition. ", "limitations": "Limitations: yes\n\nImpact: N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and the review of the related work is thorough. A great deal of effort has been put into making sure that the paper is clear and accessible for a wide audience, particularly in the technical overview. This paper is a bit outside my expertise, but the results and techniques used are interesting and could be of independent interest. I believe this paper is relevant to the learning theory community.", "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": "imJuS5SAwXs", "reviewer": "Reviewer_ZuTs", "summary": "The paper establishes hardness of learning neural networks with Gaussian inputs under various assumptions:\n- statistical query learning, two hidden layers;\n- cryptographic hardness of learning with rounding, two hidden layers;\n- label query learning, existence of a family of pseudo-random functions, any fixed number of hidden layers.\n\nThe main tool for obtaining these results is a modified Danieli-Vardy transform (2021) that maps a Boolean example (x, y) to a Gaussian example (z, y') while remaining in the realizability setup.", "questions": "No questions", "limitations": "See weaknesses above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- A solid theoretical work that establishes new hardness results for the now ubiquitous neural networks.\n\n**Weaknesses**\n- The paper does not explicitly indicate the limitations of the results. For example, lines 67-68 say that \"Theorem 1.1 rules out almost all known approaches for provably learning neural networks\", but the most well-known approach to learn neural networks---SGD---is not ruled out by Thm 1.1.", "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": "_kDzubyhJm3", "reviewer": "Reviewer_PSRf", "summary": "This work provides lower bounds in the noise free setting for learning two hidden layer networks in the Gaussian space. Basically, the whole concept is to embed hard problems over the uniform in hypercube to the Gaussian space. This is not something new, this has been done before in [1] for proving lower bound in the agnostic learning halfspaces over the Gaussian distribution. In contrast, this work provides noise-free lower bounds. They provide a super-polynomial SQ lower bound, a cryptographic lower bound under the LWR assumption. Moreover, they also provide lower bounds for the query model which is more powerful than the PAC learning model. \n\nThe whole concept is the following: To embed hard problems from the hypercube to the Gaussian space, we can use a similar idea like in [1], i.e., using the sign function. The DV lift basically does that by adding 2 more hidden layers (with ReLU components). So, a hard problem with L-Layers can provide lower bounds for L+2 layers in Gaussian space.\n\nThe authors decrease the number of layers from +2 Layers to +1. To do that, first they show a way to do it using a very large network, basically, they start from an exponential construction Eq.(11) and then they decrease it to $d^m$ by make the network more sparse, using the distributional properties of the Gaussian. They introduce some error in the construction but they show that this is indeed very small. After that the hardness proofs follow from a reduction.\n\n\n\n[1] Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaussian space.", "questions": "Some presentation suggestions:\nI would suggest the authors to add after section 1.2 lines 197 some more intuition about the construction and the idea that they use to decrease the size of the network. \nSome fullstops and commas in equations are missing, i.e., eq. 2.", "limitations": "everything is good.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Pros\n1. This is good result. The authors provide lower bounds under several assumptions/models. \n2. This work is very well-written. Checked almost all the proofs and the claims are sound.\n\n# Cons\nNot really a con just a comment. The lower bounds are for 2-hidden layer networks where there are results for 1-hidden layer networks for the CSQ model. [GGJ+20],[DKKZ20] Basically, the trade-off is stronger model and 2-hidden layer instead of 1. In general, I would expect stronger lower bounds for 2-hidden layer network. \n\n\nOverall, I recommend for 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