Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy
Authors: Amit Daniely
Nathan Srebro
Gal Vardi
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning neural networks
Computational complexity
Hardness of learning
Smoothed analysis
Degenerate weights
TL;DR: We show new hardness results for learning shallow neural networks in highly non-degenerate cases

Abstract: Understanding when neural networks can be learned efficiently	is a fundamental question in learning theory.	Existing hardness results suggest that assumptions on both the input distribution and the network's weights are necessary for obtaining efficient algorithms. Moreover, it was previously shown that depth-$2$ networks can be efficiently learned under the assumptions that the input distribution is Gaussian, and the weight matrix is non-degenerate. In this work, we study whether such assumptions may suffice for learning deeper networks and prove negative results. We show that learning depth-$3$ ReLU networks under the Gaussian input distribution is hard even in the smoothed-analysis framework, where a random noise is added to the network's parameters. It implies that learning depth-$3$ ReLU networks under the Gaussian distribution is hard even if the weight matrices are non-degenerate. Moreover, we consider depth-$2$ networks, and show hardness of learning in the smoothed-analysis framework, where both the network parameters and the input distribution are smoothed. Our hardness results are under a well-studied assumption on the existence of local pseudorandom generators.

Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy
Amit Daniely
Nathan Srebro TTI-Chicago nati@ttic. edu
Hebrew University and Google
amit dan.elylmaiillii.. i1
Gal Vardi
TTI-Chicago and Hebrew University galvardi@ttic.com
Abstract
Understanding when neural networks can learned efficiently a fundamental question in learning theory. Existing hardness results suggest that assumptions both the input distribution and the network's 's weights are necessary for obtaining efficient algorithms. Moreover, it previously shown that depth-2 networks can be efficiently learned under the assumptions that the input distribution is Gaussian, and the weight matrix is non-degenerate. In this work, study whether such assumptions may suffice for learning deeper networks and prove negative results. We show that learning depth-3 ReLU networks under the Gaussian input distribution is hard even in the smoothed-analysie framework, where a random noise added the network's parameters. implies that learning depth-3 ReLU networks under the Gaussian distribution is hard even if the weight matrices are non-degenerate. Moreover, we consider depth-2 networks, and show hardness of learning in the smoothed-analee and the input distribution are smoothed. Our hardness results are under a well- studied assumption on the existence of local pseudorandom generators.
framework, where both the network parameters
Introduction
The computational complexity of learning neural networks has been extensively studied in recent years, and there has been much effort in obtaining both upper bounds and hardness results. Neverthe- less, it is still unclear when neural networks can be learned in polynomial time, namely, under what assumptions provably efficient algorithms exist.
Existing results imply hardness already for learning depth-2 ReLU networks in the standard PAC learning framework (e.g.. [4]) Thus, without any assumptions the input distribution the network's weights, efficient learning algorithms might not be achievable. Even when assuming that the input distribution is Gaussian, strong hardness results
obtained for depth-3 ReLUU networks [6] [I] suggesting that assumptions merely on the input distribution might not suffice. Also, a hardness result by Daniely and Vardi (15) shows that strong assumptions merely on the network's weights (without restricting the input distribution) might not suffice even for efficiently learning depth-2 networks. The aforementioned hardness results hold already for improper learning, namely, where the learning algorithm is allowed to return hypothesis that does not belong to the considered hypothesis class, Thus, combination of assumptions on the input distribution and the network's weights seems to be necessary for obtaining efficient algorithms.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Several polynomial-time algorithms for learning depth-2 neural networks have been obtained, under assumptions on the input distribution and the network's weights 66 |8 + 20 2T). In these works, it is assumed that the weight matrices are non-degenerate. That is, they either assume that the condition number of the weight matrix is bounded, or some similar non-degeneracy assumption. Specifically, Awasthi et al. [6] gave an efficient algorithm for learning depth-2 cone-hidden-layee ReLU networks, that may include bias terms in the hidden neurons, under the assumption that the input distribution is Gaussian, and the weight matrix is non-degenerate. The non-degeneracy assumption holds w.h.p. we add a small random noise to any weight matrix, and hence their result implies efficient learning of 2epth-2 ReLU networks under the Gaussian distribution in the smoothed -aoolhhd-analysis framework.
The positive results on 2 networks suggest the following question:
Is there an efficient algorithm for learning ReLU networks of depth larger than 2 under the Gaussian distribution, where the weight matrices are non non-degenerate, or in the smoothed mmoothed-annlysis framework where the network's 's parameters are smoothed?
In this work, we give a negative answer to this question, already for depth-3 networks]] We show that learning depth-3 ReLU networks under the Gaussian distribution is hard even in the smoothed- analysis framework, where a random noise is added to the network's parameters. As a corollary, we show that learning depth-3 ReLU networks under the Gaussian distribution hard even if the weight matrices are non-degenerate. Our hardness results are under a well-studied cryptographic assumption on the existence of local pseudorandom generators (PRG) with polynomial stretch.
Motivated by the existing positive results on amoothed-analyste in 2epth-2 networks, we also study whether learning 22pth-2 networks with smoothed parameters can be done under weak assumptions on the input distribution. Specifically, we consider the following question:
Is there an efficient algorithm for learning depth-2 ReLU networks in the smoothed- analysis framework, where both the network's 's parameters and the input distribution are smoothed?
We give a negative answer to this question, by showing hardness learning depth-2 ReLU networks where a random noise is added to the network's 's parameters, and the input distribution on I& is obtained by smoothing an i.idd Bernoulli distribution on {0, 1]a. This hardness result is also under the assumption on the existence of local PRGs.
Related work
Hardness of learning neural networks. Hardness of improperly learning depth-2 neural networks follows from hardness of improperly learning DNFs or intersections of halfspaces, since these classes can be expressed by depth-2 networks. Klivans and Sherstov (11 showed, assuming the hardness of the shortest vector problem, that learning intersections of halfspaces is hard. Hardness of learning DNF formulas implied by Applebaum et al. under a combination of two assumptions: the first is related to the planted dense subgraph problem in hypergraphs, and the second is related to local PRGs. Daniely and Shwary-Shwrrz [14 showed hardness of learning DNFs under a common assumption, namely, that refuting random K -ST formula is hard. All of the above results are distribution free, namely, they do not imply hardness of learning neural networks under some specific distribution.
Applebaum and Raykov 33 showed, under an assumption on specific candidate for Goldreich's PRG (i.e.. based on a predicate called XOR-MAJ), that learning depth-3 Boolean circuits under the uniform distribution on the hypercube is hard. Daniely and Vardi [16] proved distribution-speciin hardness of learning Boolean circuits of depth-2 2 (namely, DNFs) and depth-3, under the assumpion on the existence of local PRGs that we also use in this work. For DNF formulas, they showed hardness of learning under distribution where each component is drawn i.i.d. from a Bernoulli distribution (which is non-uniform). For depth-3 Boolean circuits, they showed hardness of learning under the uniform distribution on the hypercube. Since the Boolean circuits can be expressed by ReLU networks of the same depth, these results readily translate to distribution-ssecifee hardness of learning neural networks. Chen et al. II showed hardness of learning depth-2 neural networks under the uniform distribution on the hypercube, based on assumption the hardness of the
We note that in results the neural networks have the ReLU activation also in the output neuron.

---

Learning with Rounding (LWR) problem. Note that the input distributions in the above results are supported on the hypercube, and they do not immediately imply hardness of learning neural networks under continuous distributions.
When considering the computational complexity of learning neural networks, perhaps the most natural choice of an input distribution is the standard Gaussian distribution. Daniely and Vardi [16] established hardness of learning depth-3 networks under this distribution, based on the assumpion on the existence of local PRGs. Chen et al. [ also showed hardness of learning depth-3 networks under the Gaussian distribution, but their result holds already for networks that do not have an activation function in the output neuron, and it is based on the LWR assumption. They also showed hardness of learning constant depth ReLU networks from label queries (i.e., where the learner has the ability to query the value of the target network at any desired input) under the Gaussian distribution, based either on the decisional Hellie or the Learning with Errors assumptions
The above results suggest that assumptions on the input distribution might not suffice for achieving an efficient algorithm for learning depth-3 neural networks. A natural question whether assumptions on the network weights may suffice. Daniely and Vardi [15) showed (under the assumption that refuting a random K K-SAT formula hard) that distribution-free learning of depth-2 neural networks is hard already if the weights are drawn from some "natural" distribution or satisfy some "natural" properties. Thus, if we do not impose any assumptions on the input distribution, then even very strong assumptions on the network's 's weights do not suffice for efficient learning.
Several works in recent years have shown hardness of cistribution-speecffi learning shallow neural networks using gradient-method or statistical query (SQ) algorithms [38
11. It is worth noting that while the SQ framework captures some variants of the gradient-descen algorithm, it does not capture, for example, stochastic gradient-descent (SGD), which examines training points individually (see discussion in (24]).
39
41
24
18
We emphasize that none of the above distribution-speciffe hardness results for neural networks (either for improper learning SQ learning) holds in the smoothed analysis framework or for non-degene weights.
Learning neural networks in polynomial time. Awasthi et al. 6 gave a polynomial-time al- gorithm for learning depth-2 (one-hidden-layer) ReLU networks, under the assumption that the input distribution is Gaussian, and the weight matrix of the target network is non-degenerate. Their algorithm is based on tensor decomposition, and it can handle bias terms in the hidden layer. Their result also implies that depth-2 ReLU networks with Gaussian inputs can be learned efficiently under the smoothed -nnalyss framework. Our work implics that such a result might not be possible in d networks (with activation in the output neuron). Prior to 3.. several works gave polynomial time algorithms for learning depth-2 neural networks where the imput distribution is Gaussian and the
21 7 but these works either do not handle the presence of bias terms or do not handle the ReLU activation. Some of the aforementioned works consider net- works with multiple outputs, and allow certain non-Gaussian input distributions. Provable guarantees
weight matrix is non-degenerate 28 43 20
for learning neural networks in super-polynomial time were given in [18 12 17
22
42 23
2 Preliminaries
Notations. We use bold-face letters to denote vectors, c.g., x (#)...... zx). For a vector x and a sequence S= (i....., ) of k indices, we let X5 = (Ii,....,, 2i, ). i.c., the restriction of x to the indices S. We denote by 1 the indicator function, for example 1| 2 5] equals if 2 and 0 otherwise. For integer d 2 1 we denote [d] = {1, f1.....d d}. We denote by AO o²) the normal distribution with mean 0 and variance o², and by \ Σ) the multivariate normal distribution with mean and covariance matrix Σ. The identity matrix of size d is denoted by la. For x E Rdd we denote by ||x|| the Euclidean norm. We use poly(a....... o.)) to denote polynomial in 01,...,
Local pseudorandom generators. An (n. m. k) hyppergraph is a hypergraph over n vertices [n] with m hyperedges Si,..., .., S.. each of cardinality k. Each hyperedge S = (fi...., is) is ordered, and all the & members of hyperedge are distinct. We let Gn.m,k be the distribution over such hypergraphs in which a hypergraph chosen by picking each hyperedge uniformly and independently at random among all the possible n (n 1re-1. 1). ..... (n k+ 1) ordered hyperedges. Let P. {0, 1)*h -
3

---

{0, 1} be predicate, and let G be a (n, m, k) hypeerraa..... We call Goldreich's 's pseudorandom generator (PRG) [5] the function fP.G: [0, + {0, 1m such that for x E {0. 1)", we have P(xs...) 1). The integer lo is called the locality of the PRG. If l is constant then the PRG and the predicate P are called local. We say that the PRG has polynomial stretch
[x) = (P((ss)..-
m n² for some constant & > 1. We let Fp denote the collection of functions fP.G where G is an (n, m, hyypergapp We sample a function from Fpmm. by choosing a random hypergraph G from m..
Rt We denote by G _ In.m, the operation of sampling a hypergraph G from Gn.m.k. and by x f {0, 13"h the operation of sampling x from the uniform distribution on {0, 13"". We say that Fp... is e-pseudorandom generator (s-PRG) if for every polynomial-time probabilistic algorithm A the distinguishing advantage
Pr
SPa(x)) = =1]-
Pr
[A(G,y) - 1]
G Gm [0,1}*
G Gm (u,1)m
is at most E. Thus, the distinguisher A is given random hypergraph G and string E {0, 10.1) and its goal is to distinguish between the case where y is chosen at random, and the case where y is a random image of JP...
Our assumption is that local PRGs with polynomial stretch and constant distinguishing advantage exist:
Assumption 2.1. For every constant s > 1. there exists a constant i and a predicate P {00, 1]. {0, 1). such that F is 2 JPRG.
We remark that the same assumption was used by Daniely and Vardi [6 to show hardness-of-learning results. Local PRGs have been extensively studied in the last two decades. In particular, local PRGs with polynomial stretch have shown to have remarkable applications, such as secure-computation with constant computational overhead [27 (5 and general-purpose obfuscation based on constant degree
multilinear maps (ef. 33 34 D. Significant evidence for Assumption [ was shown in Applebaum
(1 Moreover, concrete candidate for local PRG, based on the XOR-MAJ predicate, was shown to be secure against all known attacks 13 35 3) See [16] for further discussion on the assumption, and on prior work regarding the relation between Goldreich's PRG and hardness of learning.
Neural networks. We consider feedforward ReLU networks. Starting from an input x E R4 each layer in the network of the form z a (W,z z + b,),, where (a) [a]= max (0, a} is the ReLU activation which applies to vectors entry-wise, W; is the weight matrix, and b; are the bias terms. The weights vector of the j-th neuron in the i-th layer is the j-th row of W,, and its outgoing- vector is the j-th column of W++1. We define the depth of the network as the number of layers. Unless stated otherwise, the output neuron also has ReLU activation function. Note that a depth-k network with activation in the output neuron has k non-linear layers. A neuron which is not input or output neuron is called hidden neuron. We sometimes consider neural networks with multiple outputs. The parameters of the neural network is the set of its weight matrices and bias vectors. We often view the parameters as a vector O E R& obtained by concatenating these matrices and vectors. For B 2 O, say that the parameters are B-bounded if the absolute values of all weights and biases are at most B.
Learning neural networks and the smoothed-analee framework. We first define neural net- works learning under the standard PAC framework:
Definition 2.1 ceerribution-sppeeife PAC learning). Learning depth-k neural networks under an input distribution 'D on IR is defined by the following framework:
1. An adversary chooses a set of B-bounded parameters O TRP for depth-k neural network No : Rdd - Tk, as well as some >> O.
2. Consider an examples oracle, such that each example (x, E Rd x IR is drawn i.i.d. with x ~ D and y = No(x). Then, given access to the examples oracle, the goal of the learn- ing algorithm C is to return with probability at least 3 a hypothesis h Bd - R such that
Ex~D [l((x) - No(x))²] S.e. We say that C is efficient if runs in time poly (d. p, B, 1/e).

---

We consider learning in the smoothed-andle -nallssis framework [40] which is popular paradigm for analyzing non-worst-cass computational complexity [36]. The smoothed-analysis framework has
10) ). In the amoothed-annlysii setting, the target network is not purely controlled by an adversary. Instead, the adversary can first generate an arbitrary network, and the parameters for this network (i.e., the weight matrices and bias terms) will be randomly perturbed to yield a perturbed network. The algorithm only needs to work with high probability on the perturbed network. This limits the power of the adversary and prevents it from creating highly degenerate cases, Formally, we consider the following framework (we note that similar model was considered in 66 21)::
been successfully applied to many learning problems (e.g.. 6 21 30 8 26
19 29
Definition 2.2 (Learning with smoothed parameters). Learning depth-k neural networks with smoothed parameters under an input distribution 'D is defined as follows:
1. An adversary chooses a set of B-bounded parameters 0 E EP for depth-k neural network Ng E + R. as well as some T > O.
2. A perturbed set of parameters θ obtained by a random perturbation to 9, namely. 0 -= + for & I=)
3. Consider an examples oracle, such that each example (x,u) E R.d x TR is drawn ii.d with x 'D and y Ng (x). Then, given access the examples oracle, the goal of the learning algorithm to return with probability at least 3. (over the random perturbation & and the
internal randomness of L) a hypothesis h : Rdd - R. such that Rx [Mx(x) - N S We say that C is efficient if runs in time poly(d, d. p, B, 1/,1////T))
Finally, we also consider setting where both the parameters and the input distribution are smoothed:
Definition 2.3 (Learning with smoothed parameters and inputs). Learning depth-k neural networks with smoothed parameters and inputs under an input distribution D is defined as follows:
1. An adversary chooses a set of B-bounded parameters O EP for depth-k neural network No Rdd - IR, as well as some T, T, O.
2. A perturbed set of parameters Ô obtuined by a rundom perturbation to namely, 0 0=0 0 & for & E~ *~N(0, I2)). Moreover, a smoothed input distribution DD is obtained from D, such that x ~ D is chosen by drawing x ~ 'D and adding random perturbation from (N,, Ia).
3. Consider an examples oracle, such that each example (x, u) TRd x TR. drawn i.i.d. with x ~ D and y = (x).). Then, given access to the examples oracle, the goal of the learning algorithm f. is to retrrn with probability at least 3
3 (over the random perturbation & and the
internal randomness of C) hypothesis h : Fd - IR such that W xx [h(x)) No(x)) "] S
We say that L is efficient if it runs in time poly(d. d. p. 1/c, 1/T, /T,11/1 1/w)-
We emphasize that all of the above definitions consider learning in the catriiuttionsspecife setting. Thus, the learning algorithm may depend on the specific input distribution D.
3 Results
As we discussed in the introduction, there exist efficient algorithms for learning depth-2 (one-hidden- layer) ReLU networks with smoothed parameters under the Gaussian distribution. We now show that such a result may not be achieved for depth-3 networks:
Theorem 3.1. Under Assumption 2. there is no efficient algorithm that learns depth-3 networks with smoothed parameters (in the sense of Definition 2.2) under the standard Gaussian distribution.
We prove the theorem in Section 4 Next, we conclude that learning depth-3 neural networks under the Gaussian distribution on Rd is hard in the standard PAC framework even if all weight matrices are non-degenerate, namely, when the minimal singular values of the weight matrices are lower bounded by 1/ (d). As we discussed in the introduction, in lne networks with similar assumptions there exist efficient learning algorithms.
5

---

there is no efficient algorithm that learns depth-3 networks (in the sense of Definition 2 under the standard Gaussian distribution on IR,,, even if the smallest singular value of each weight matrix is at least 1/ poly(d).
Corollary 3.1. Under Assumption 2.7
The proof of the above corollary follows from Theorem 3.1 using the fact that by adding small random perturbation to the weight matrices, we get w.h.p. non-degenerate matrices. Hence, an efficient algorithm that learns non-degenerate networks suffices for obtaining an efficient algorithm that learns under the smoothed analysis framework. See Appendix [ for the formal proof.
The above hardness results consider depth-3 networks that include activation in the output neuron. Thus, the networks have three non- non-linear layers. We remark that these results readily imply hardness also for depth-4 networks without activation in the output, and hardness for depth-k networks for any k > 3. We also note that the hardness results hold already for networks where all hidden layers are of the same width, e.g., where all layers are of width d.
Theorem 3.1 gives a strong limitation on learning depth-3 networks in the smoothed-analyst frame- work. Motivated by existing positive results smoothed-analyse in depth-2 networks, we now study whether learning 2 networks with smoothed parameters can be done under weak assumptions on the input distribution. Specifically, we consider the case where both the parameters and the input distribution are smoothed. We show that efficiently learning depth-2 2 networks may not be possible with smoothed parameters where the input distribution on IR is obtained by smoothing i.i.d. Bernoulli distribution on 1)..
Theorem 3.2. Under Assumption 2.1 there is efficient algorithom that learns depth-2 networks with smoothed parameters and inputs (in the sense of Definition 2.3), under the distribution 'D on {0, 13dh where each coordinate is drawn i.i.d. from Bernoulli distribution which takes the value 0 with probability Vi
We prove the theorem in Appendix C The proof follows from similar ideas to the proof of Theo- rem 3.1 which we discuss in the next section.
4 Proof of Theorem 3.1
The proof builds on a technique from Daniely and Vardi [16]. It follows by showing that an efficient algorithm for learning depth-3 neural networks with smoothed parameters under the Gaussian distribution can be used for breaking a local PRG. Intuitively, the main challenge in our proof in comparison [16] is that our reduction must handle the random noise which is added to the parameters. Specifically, [16) define a certain examples oracle, and show that the examples returned by the oracle are realizable by some neural network which depends on the unknown x E {0, 1}" used by the PRG. Since the network depends on this unknown some of the parameters of the network are unknown, and hence it is non-trivial how to define an examples oracle which is realizable by a perturbed network. Moreover, we need to handle this random perturbation without increasing the network's 's depth. For these reasons, our reduction is significantly different from [16]
We now provide the formal proof. The proof relies on several lemmas which we prove in Appendix A For sufficiently large let 'D be the standard Gaussian distribution on IR= Assume that there is a poly(n)-time algorithm L that learns depth-3 neural networks with at most n² hidden neurons and parameter magnitudes bounded by n²3, with smoothed parameters, under the distribution D, with e = f., and - = 1/ poly(n) that we will specify later. Let Let mn))) S poly(n) be the sample complexity of L. namely, L uses a sample of size at most m(n) and returns w.p. at least 3 a hypothesis h with
En-D (h(z) No (z))² < E = 1. where No is the perturbed network. Let > be a constant such that n² 2 m(n) + n for every sufficiently large n. By Assumption 2.1 there exists a constant k and a predicate P : {0, 13* + fo, 1). such that Fp, is 1 -PRG We will show an efficient 3 algorithm A with distinguishing ad advantage greater than and thus reach contradiction.
Throughout this proof, we will use the following notations. For a hyperedge S (f.....,44) (x) we denote by z E {0, 1 the following encoding of S: the vector z is a concatenation of k vectors in {0, 1)3h, such that the j-th vector has in the -t coordinate and elsewhere. Thus, S consists of k size-n slices, each encoding a member of S. For z E (0, 1) }An, i E [k] and j E [m)) we denote zij 2((1))+ That is, 2i is the j-th component in the i-th slice in z. For x E {0, 1)", let

---

Px: {0, 1m + {0.1) be such that for every hyperedge S we have )x(z²)= = P(xs). Let be such that P I d Let μ be the density of N 1). let μ (t n 1[t S p(t). and let μ+ --I 1lt 2 c| (t). Note that μ., + are the densities of the restriction of f to the intervals / S e and I 2 e respectively. Let v : IR + +0, 1 be a mapping such that for every
z' E 1 and E [km] we have (z'), 1[ 2 cl. For Ž E RT we denote [(km]] (21 ................................ knn). namely, the first kn components of z (assuming n² 2 kn).
4.1 Defining the target network for
Since our goal is to use the algorithm & for breaking PRGs, in this subsection we define neural network N : g=² + I that we will later use as target network for C. The network N contains the subnetworks N2, .gg which we define below.
Let N1 be 2 neural network with input dimension kn, at most n log(n) hidden neurons, at most log(n) output neurons (with activations in the output neurons), and parameter magnitudes bounded by n² (all bounds are for sufficiently large n), which satisfies the following. We denote the set of output neurons of N1 by E7. Let z' E kn be an input to N1 such that V (z') = z for some hyperedge S, and assume that for every i E [kn] we have 2/ & (c,c+ ) Fix some x E {0, 1)" Then, for S with Px (x = 0 the inputs to all output neurons E are at most 11, and for 5 with (x(25) = there exists neuron in & with input least 2. Recall that our definition of neuron's 's input includes the addition of the bias term. The construction of the network N1 is given in Lemma A.3] Intuitively, the network N₁ consists of layer that transforms w.h.p. the input z' to (zz)) = z², followed by layer that satisfies the following; Building on a lemma from [T6] which shows that (x(z)) can be computed by DNF formula, we define layer where each output neuron corresponds to a term in the DNF formula, such that if the term evaluates to 0 then the input to the neuron is at most only the second layer depends on x, and thus given an input we may compute the first layer even without knowing x. Let Ní= RRn -> be a depth-3 network with no activation in the output neuron, obtained from N1 by summing the outputs from all neurons &
and otherwise it is at least 2. Note that the network N2 depends on x. However,
Let N₂ be 22pth-2 neural network with input dimension kn, at most log(n) hidden neurons, most 2n output neurons, and parameter magnitudes bounded by n² (for a sufficiently large nt), which satisfies the following. We denote the set of output neurons of N2 by Eg. Let z' E 1 be an input to N2 such that for every E [Km]] we have 2! & (c, c ) If (zz) is an encoding of a hyperedge then the inputs to all output neurons &g are at most 11, and otherwise there exists a neuron in & with input at least 2. The construction of the network N₂ is given in Lemma (.5) Intuitively, each neuron in & is responsible for checking whether L (z') violates some requirement that must hold in encoding of a hyperedge. Let N₂- Rahn - RR. be depth-3 network with no activation in the output neuron, obtained from N2 by summing the outputs from all neurons &g.
Let N3 be depth-2 2 neural network with input dimension kn, at most n log(n) hidden neurons, kn S n log(n) output neurons, and parameter magnitudes bounded by n (for a sufficiently large n), which satisfies the following. We denote the set of output neurons of N₃ by Eg. Let z' E AR be an input to N3. If there exists i E [km] such that z/ E (c,c+ + (/) then there exists neuron in &g with input least 2. Moreover, if for all i [km] we have 2/ & (c , 33) then the inputs to all neurons in Eg are at most - 1. The construction of the network N3 is straightforward and given in Lemma A.6 Let N₂= : R + IR be a depth-3 neural network with no activation function in the output neuron, obtained from N3 by summing the outputs from all neurons Eg.
Let N' Rkn + R be depth-3 network obtained from Ni. No N2 as follows. For z' R we have (z') = (z') - N2(2²') - N2(22')4__ The network N' has at most n² neurons, and parameter magnitudes bounded by n² (all bounds are for a sufficiently large n), Finally, let Ñ R + R be a depth-3 neural network such that (2) = N' (2/mm).
4.2 Defining the noise magnitude and analyzing the perturbed network
In order to use the algorithm L w.r.t. some neural network with parameters 0, we need to implement an examples oracle, such that the examples are labeled according to a neural network with parameters
0 + E. where& & is random perturbation. Specifically, we use L with an examples oracle where the
7

---

labels correspond to network N: R²² - RR obtained from N (w.r.. an appropriate x E {0. 1)." in the construction of Ni) by adding a small perturbation to the parameters. The perturbation such that we add i.i.d. noise to each parameter in N, where the noise is distributed according to NN(,, and T = 1/ poly(n) is small enough such that the following holds. Let fo IR" + R be any depth-3 neural network parameterized by 0 R' for some 0 with at most n² neurons, and parameter magnitudes bounded by n (note that r is polynomial in n). Then w.p. at least 1/2 over & ~ NV 1,),, we have |&il S TO for all i E [r]. and the network so+e is such that for every input ă E TR." with ||||| I 2n and every neuron we have: Let a, be the inputs to the neuron in the computations fol (2) and fo+e(2) (respectively), then |a bj - 2- Thus, T is sufficiently small, such that w.h.p. adding i.i.d. noise (N0, r²) to each parameter does not change the inputs to the neurons by more than 2.
-. Note that such an mnverse-polyoomial T exists, since when the network size, parameter magnitudes, and input size are bounded by some poly(n), then the input to each neuron in fz) is poly (1) Lipschitz as a function of 0, and thus it suffices to choose T that implies w.p. at for sufficiently large polynomial g(n) (see Lemma A.7 for details).
least 1 1 that | q(m) "
Let 0 E Rº be the parameters of the network N. Recall that the parameters vector 0 is the concatenation of all weight matrices and bias terms. Let O E I' be the parameters of N, namely, @ = 0 + E where & ~ _N 12) By our choice of and the construction of the networks Ni, N2. N3. w.p. at least n over &. for every 2 with ||ž||| S 2n, the inputs to the neurons E2 &g in the computation Ñ (?) satisfy the following properties, where we denote z' 2 jmn]
(PI) If ((z') = S for some hyperedge S, and for every E [kv] we have z/ É (c,c+ + ) then the inputs to & satisfy: If (z(2)) = O then the inputs to all neurons in & are at most 2. and if (z)) ) = 1 then there exists a neuron in &1 with input at least 5
(P2) If for every i E [km] we have 2 & (c. (c.c+ ) then the inputs to &g satisfy: If (zz) is an encoding of a hyperedge then the inputs to all neurons & are at most 2. and otherwise there exists a neuron in &g with input at least 3
(P3) The inputs to Eg satisfy: If there exists i E [Am] such that 2 E c + then there exists a neuron in & with input at least 3. and if for all i E [ke]] we have of & (c n + . then the inputs to all neurons in Eg are at most - 1
4.3 Stating the algorithm A
are i.i.d. random hyperedges, Given sequence (1),,)....., (S.., (Sn,,,n=), where SI,...,S, Sn the algorithm A needs to distinguish whether = (yi.... Vn-) is random or that we have y (P(xs, )..., )(xs,,))
" for random x E 10. We let
S ([z 11 (2... ,Vn=)).
We use the efficient algorithm L in order to obtain distinguishing advantage greater than 1 as follows. Let & be a random perturbation, and let Ñ be the perturbed network as defined above, w.r.t. the unknown x E {0, 1J". Note that given a perturbation &, only the weights in the second layer of the subnetwork N, in N are unknown, since all other parameters do not depend on x. The algorithm A runs L with the following examples oracle. In the i-th call, the oracle first draws z E {0, 1 such that each component drawn i.i.d. from Bernoulli distribution which takes the value 0 w.p. A. If z is an encoding of a hyperedge then the oracle replaces z with z Then, the oracle chooses z' E Rm such that for each component j. if zj
then z/J is drawn from μ4, and otherwise 2/ is drawn from _... Let 2 E R be such that km] z', and the other n²² kn components of & are drawn i.i.d. from (0, 1). Note that the vector ž has the distribution D, due to the definitions of the densities μ++ and p_, and since replacing an encoding of a random hyperedge by an encoding of another random hyperedge does not change the distribution of z. Let E R be the bias term of the output neuron of N. The oracle returns (z, ÿ). where the labels ğ are chosen as follows:
If (2') is not an encoding of a hyperedge, then 0 = 0. If (z') is an encoding of hyperedge:
8

---

If z' does not have components in the interval (c- n c + n2 then if ys = 0 we set i = b. and y/ 1 we set O.
If z has component in the interval (c,c ): then O.
If z' does not have components in the interval (c, c + ).)) ). but has a component in the interval (c- + c+ 2.) ). then the label y is determined as follows: If yı - 1 then i = 0. If yi 0, we have: Let N3 be the network N after omitting the neurons & and their incoming and outgoing weights. Then, we set y [B Nz( Note that since only the second layer of N1 depends on x, then we can compute N' (ž) without knowing x.
Let h be the hypothesis returned by L. Recall that L uses at most m(n) examples, and hence S contains at least n examples that L cannot view. We denote the indices of these examples by I = {m(() + 1...., m(n) + n n²), and the examples by S₁ { 94) By n² additional calls to the oracle, the algorithm A obtains the examples S₁ { ūe) that correspond to S₁- Let / be hypothesis such that for all E IR= have h'(2) max (0, min h()))), thus, for b 2 the hypothesis h' is obtained from by clipping the output to the interval [0, 6j. Let (7hh)) पे Eie
3.)2. Now, if (y(h') S 3. then returns 1, and otherwise it returns O. We remark that the decision of our algorithm is based on 1 (rather than h) since we need the outputs to be bounded, in order to allow using Hoeffding's 's inequality in our analysis, which we discuss in the next subsection.
4.4 Analyzing the algorithm A
Note that the algorithm A runs in poly(n) time. We now show that if S is pseudorandom then A returns 1 w.p. greater than 3. and if S is random then A returns w.p. less than 1.
3.
We start with the case where S is pseudorandom. In Lemma A.8 we prove that if S is pseudoran- dom then w.h.p. (over & _N( (p) and the i.i.d. inputs 2; D) the examples (2), W1),..., (Zm(n)+na (m(n))+n)) returned by the oracle are realized by Ñ. Thus, Dr (2,) for all i. As we show in the lemma, this claim follows by considering the definition of the oracle for the different
cases of (z.) [kn]. and using Properties (P1) (P3) to show that Ñ behaves similarly.
Recall that the algorithm L is such that w.p. least & (over & ~ (O ((0,7²I,) r2Lp), the i.id. inputs ž D, and its internal randomness), given a size-m(()) dataset labeled by Ñ, returns a hypothesis h such that E2~D (h(z) ( S 1 By the definition of h' and the construction of N, if has small
error then also has small error, namely, we have EgLD (h'(2) - N()))2 < 1.- Lemma A.9
we use the above arguments and Hoeffding's inequality over S,, and prove that w.p. greater than we have (h') <
Next, we consider the case where S is random. Let Z C R be such that ă E 2 iff 2 [km] does not have components the interval (c - 2 c )), and (2(km) = z for a hyperedge S. If S is random, then by the definition of our examples oracle, for every i E [m(n) n²] such that 2, E 2, we have T; b w.p. 1 and ūe otherwise. Also, by the definition of the oracle, ÿi is independent of S; and independent of the choice of the vector ž, that corresponds to St Hence, for such 2; e Ž with i E T, any hypothesis cannot predict the label fi. and the expected loss for the example is at least
Moreover, in Lemma A. we show that Pr 2 E E [log(n] for a sufficiently large n. In Lemma A.12 we use these arguments to prove a lower bound on EEg, [h)),, and by Hoeffding's inequality over S, we conclude that w.p. greater than 3 we have (y(h)) > 2
Overall, if S is pseudorandom then w.p. greater than 3/2 the algorithm A returns 1, and if S is random then w.p. greater than o it returns 0. Thus, the distinguishing advantage is greater than $

---

Discussion
Understanding the computational complexity of learning neural networks is a central question in learning theory. Our results imply that the assumptions which allow for efficient learning in one- hidden-layer networks might not suffice in deeper networks. Also, in depth-2 networks we show that it is not sufficient to assume that both the parameters and the inputs smoothed. We hope that our hardness results will help focus on assumptions that may allow for efficient learning.
We emphasize that our hardness results are for neural networks that include the ReLU activation also in the output neuron. contrast, the positive results on learning depth-2 networks that we discussed in the introduction do not include activation in the output neuron. Therefore, as far as we are aware, there still small gap between the upper bounds and our hardness results: (1) Under the assumption that the input is Gaussian and the weights are non-degenerate, the cases of depth-2 networks with activation the output neuron and of depth-3 networks without activation in the output are not settled; (2) In the setting where both the parameters and the input distribution are smoothed, the case of 22pth-2 networks without activation the output is not settled. These gaps are an intriguing subject for further research.
Acknowledgments and Disclosure of Funding
This work done part of the NSF-Simons Sponsored Collaboration on the Theoretical Founda- tions of Deep Learning.
References
[1] B. Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM Journal on Computing, 42(5):2008 2037, 2013.
[2] B. Applebaum and S. Lovett. Algebraic attacks against random local functions and their countermeasures. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1087-1100, 2016.
[3] B. Applebaum and Raykov. Fast pseudorandom functions based on expander graphs. In Theory of Cryptography Conference, pages 27-56. Springer, 2016.
[4] B. Applebaum, B. Barak, and A. Wigderson. Public-key cryptography from different assump- tions. In Proceedings of the forty-second ACM symposium Theory of computing, pages 171-180, 2010.
[5] B. Applebaum, I. Damgård, Y. Ishai, M. Nielsen, and L. Zichron. Secure arithmetic computation with constant computational overhead. In Anmual International Cryptology Conference, pages 223-254. Springer, 2017.
[6] P. Awasthi, A. Tang, and A. Vijayaraghavan. Efficient algorithms for learning depth-2 neural networks with general relu activations. Advances in Neural Information Processing Systems, 34:1 34:13485-13466, 2021.
[7] A. Bakshi, R. Jayaram, and D. Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195-268. PMLR, 2019.
[8] A. Bhaskara, M. Charikar, A. Moitra, and Vijayaraghavan. Smoothed analysis of tensor decompositions. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 594-603, 2014.
[9] A. Bhaskara, A. Chen, A. Perreault, and A. Vijayaraghavan. Smoothed analysis in unsupervised learning via decoupling. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 582-610. IEEF, 2019.
[10] A. Brutzkus, A. Daniely, and F. Malach. Id3 learns juntas for smoothed product distributions. In Conference on Learning Theory, pages 902-915, PMLR, 2020.
10

---

[11] S. Chen, A. Gollakota, A. R. Klivans, and R. Meka. Hardness of noise-free learning for two-hidden-aae neural networks. arXiv preprint arXiv:2202.05255, 2022.
[12] Chen, R. Klivans, and R. Meka. Learning deep relu networks fixed-parane axed-parameter tractable. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707. IEEE, 2022.
[13] G. Couteau, A. Dupin, P. Méaux, M. Rossi, and Y. Rotella. On the concrete security of goldreich's pseudorandom generator. In International Conference on the Theory and Application of Cryptology and Information Security, pages 96-124, Springer, 2018.
[14] A. Daniely and S. Shalev-Shwartz. Complexity theoretic limitations on learning dnf's. In Conference Learning Theory, pages 815-830, 2016.
[15] A. Daniely and G. Vardi. Hardness of learning neural networks with natural weights. arXiv preprint arXiv:2006.03 177.0,37777.7 2020.
[16] A. Daniely and G. Vardi. From local pseudorandom generators to hardness of learning. In Conference Learning Theory, pages 1358-1394. PMLR, 2021.
[17] I. Diakonikolas and D. M. Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In 2020 IEEE st Annual Symposium on Foundations of Computer Science (FOCS), pages 184-195, IEEE, 2020.
[18] I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-laye relu networks. arXiv preprint arXiv:2006. 12476, 2020.
[19] R. Ge, Q. Huang, and S. M. Kakade. Learning mixtures of gaussians in high dimensions. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 761-770 2015.
[20] R. Ge, J. D. Lee, and T. Ma. Learning one one-hidden-layer neural networks with landscape design. arXiv preprint arXiv: 1711.0050,, 2017.
[21] R. Ge, R. Kuditipudi, Z. Li, and X. Wang. Learning two-layer neural networks with symmetric inputs. arXiv preprint arXiv: 2018.
[22] S. Goel and A. R. Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference on Learning Theory, pages 1470-1499. PMLR, 2019.
[23] S. Goel, V. Kanade, A. Klivans, and J. Thaler. Reliably learning the relu in polynomial time. In Conference Learning Theory, pages 1004-1042. PMLR, 2017.
[24] S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. arXiv preprint arXiv:2006. 1201 2020.
[25] O. Goldreich. Candidate one-way functions based on expander graphs. IACR Cryptol. ePrint Arch., 2000:63, 2000.
[26] N. Haghtalab, T. Roughgarden, and A. Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33:9203-9215. 2020.
[27] Y. Ishai, E. Kushilevitz, Ostrovsky, and A. Sahai. Cryptography with constant computational overhead. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 433 433-442, 2008
[28] M. Janzamin, H. Sedghi, and Anandkumar. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint 1rXiv:1506.08477. 2015.
[29] A. T. Kalai and S.-H. Teng. Decision trees are pac-learnable from most product distributions: smoothed analysis. arXiv preprint wxXiv:08/2.09: 2008
[30] A. Kalai, A. Samorodnitsky, and S.-H. Teng. Learning and smoothed analysis. 2009 50th Annual IEEE Symposium Foundations of Computer Science, pages 395-404. IEEE, 2009.
11

---

[31] A. R. Klivans and A. A. Sherstov. Cryptographic hardness for learning intersections of halfs- paces. In FOCS, 2006.
[32] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
[33] H. Lin. Indistinguishabiiity obfuscation from constant-degree graded encoding schemes. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 28 57. Springer, 2016.
[34] H. Lin and Vaikuntanathan. Indistigguishabiiiy obfuscation from ddh-like assumptions on constant-degree graded encodings, In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 1-200. IEEE, 2016.
[35] Méaux, C. Carlet, A. Journault, and F.-. Standaert. Improved filter permutators: Combining symmetric encryption design, boolean functions, low complexity cryptography, and homomor- phic encryption, for private delegation of computations. IACR Cryptol. ePrint Arch., 2019:483, 2019.
[36] T. Roughgarden. Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021.
[37] A. Sankar, D. A. Spielman, and S.-H. Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications, 28(2):446-476. 2006.
[38] O. Shamir. Distribution- -speiiff hardness of learning neural networks. The Journal of Machine Learning Research, ([11::1135-166) 2018.
[39] L. Song, S. Vempala, J. Wilmes, and B. Xie. On the complexity of learning neural networks. In Advances in neural information processing systems, pages 5514-5522, 2017.
[40] D. A. Spielman and S.-H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 5163)3385555 2004.
[41] S. Vempala and J. Wilmes. Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds. In Conference Learning Theory, pages 3115-3117. PMLR, 2019.
[42] Y. Zhang, J. D. Lee, and M. I. Jordan. 11-regularized neural networks are improperly learnable in polynomial time. In International Conference on Machine Learning, pages 993-1001. PMLR, 2016.
[43] K. Zhong, Z. Song, Jain, P. L. Bartlett, and I. S. Dhillon. Recovery guarantees for one-hidden- layer neural networks. In International conference on machine learning, pages 4140-4149 4149. PMLR, 2017.
12

---

A Missing lemmas for the proof of Theorem 3.1
Lemma A.1 (Daniely and Vardi [16]). For every predicate P: 10,11 - (0,1) and x {0, 1) there is DNF formula io over {0, 1 km with at most 2 terms, such that for every hyperedge S we have (x ) = (2²)). Moreover, each term in tb is a conjunction of positive literals.
Proof. The following proof is from Daniely and Vardi [6], and we give it here for completeness. We denote by B _ [O, 13 the set of satisfying assignments of P. Note that the size of B is at most 2 Consider the following DNF formula over {0, 1 kmm
(iz)
V A
A 23,1-
bEB jE(M] (l=r)s/b;)
For hyperedge 5 (h....., ;4,,, we have
21x5) = -
d B E [k] Vn, + bj, 25,1 =
b Byj E [k] Vn + by, in #1
3b B Vj E [K], Ii, bj
3b E B, =b
P(xs)= =1
Lemma A.2. Let 13". There exists an affine layer with at most 2 outputs, weights bounded by a constant and bias terms bounded by n log(n) (for sufficiently large n),, such that given an input z E {0,1] km for some hyperedge S, it satisfies the following: For with Px(z²) = 0 all outputs are most -1, and for S with Px(25)
there exists an outpul greater or equal 2.
Proof. By Lemma A.1 there exists DNF formula 9x over {0, 1) 1 with at most 2 terms, such that spx (z = Px 2 Thus, if (z5)) = 0 then all terms in fx are not satisfied for the input S and if Px (x )- then there is at least one term in Sx which is satisfied for the input 2 Therefore, it suffices to construct an affine layer such that for an input z5, the j-th output will be at most - the j-th term of yox is not satisfied, and at least 2 otherwise. Each term Cj in 9x is conjunction of positive literals. Let I S [kn]] be the indices of these literals. The j-th output of the affine layer will
be
32 Iel
3
3/4 +
Note that if the conjunction C2 holds, then this expression is exactly 3/4 - 314, + 2 = 2, and otherwise it is at most 3(1T - 1) I + 2 -1. Finally, note that all weights are bounded by 3 and all bias terms are bounded by n log(n) (for large enough nt).
Lemma A.3. Let E {0, 13". There exists depth-2 neural network N1 with input dimension knn 2kn hidden neurons, at most 2 output neurons, and parameter magnitudes bounded by n² (for sufficiently large n., which satisfies the following. We denote the set of output neurons of N₂ by E Let z' E Bek be such that (zz)) = 2 for some hyperedge S, and assume that for every i [kn] we have 2 of (c,c+ 1.). Then,for S with (z(=S) 0 the inputs all neurons Er are most -,, and there exists a neuron in Er with input least 2. Moreover, only the second layer of N₁ depends on x.
for S with (z(z))
Proof. First, we construct 22pth-2 neural network No km [0, 1] AAm with single layer of non- linearity, such that for every z' E & with a & (c, + + for every i E [kn], we have No (z') (z'). The network Ny has 2kn hidden neurons, and computes (z') (f(e))....,ff where ʃ RR. > [0, 1] is such that
f(t) = n -tt ( - { - c+ n? 11
13

---

Note that i I then f(t) = 00 c+ na then f(t) = 1, and and < << c+ da then f(t E (0, 1). Also, note that all weights and bias terms can be bounded by n² (for large enough n). Moreover, the network Ny does not depend on x.
Let E RR such that V'zz)= = z for some hyperedge S, and assume that for every i E [km] we have 2/ & (c.c+ )²) For such z', we have (z') = (z') z Hence, it suffices to show that we can construct an affine layer with at most 2 outputs, weights bounded by a constant and bias terms bounded by n², such that given an input 2 it satisfies the following: For S with Px(x*)
all outputs are at most -1, and for S with (z(2)) ) = there exists an output greater or equal to 2.
We construct such an affine layer in Lemma A.2
Lemma A.A. There exists an affine layer with 2k + outputs weights bounded by a constant and
bias terms bounded by n log(n) (for sufficiently large n), such that given an input z E {0, 1 if it is encoding of hyperedge then all outputs are most 11, and otherwise there exists an output greater or equal to 2.
Proof. Note that z E {0, 13 is not an encoding of a hyperedge iff least one of the following holds:
1. At least one of the le size-n slices in z contains 0 more than once.
2. At least one of the l size-n slices in z does not contain 0.
3. There are two size-n slices in z that encode the same index.
We define the outputs of our affine layer as follows. First, we have k outputs that correspond
to (1). order to check whether slice E [A] contains 0 more than once, the output will be
3n 4- ( jEn] 32,).. Second, we have i outputs that correspond to (2): in order to check whether slice i E [k] does not contain 0, the output will be (EjEjn) 3zz,) - 3n + 2. Finally, we have n outputs that correspond to (3): in order to check whether there are two slices that encode the same index j E [n], the output will be 3k - 4 (Eie(s) 324,)). Note that all weights are bounded by 3 and all bias terms are bounded by n log(n) for large enought n.
Lemma A.5. There exists a depth-2 neural network N₂ with input dimension kn, at most 2kn hidden neurons, 2k + output neurons, and parameter magnitudes bounded by n² (for a sufficiently large n), which satisfies the following. We denote the set of output neurons of N₂ by Ez. Let z' E TR kn be
such that for every E [kn] we have 2 & (c, c+ 1.). If (zz' ) is an encoding of a hyperedge then the inputs to all neurons Eg are at most 1, and otherwise there exists neuron in Eg with input at least? 2.
Proof. Let Ny I - [0, 1 be the 2epth-2 2 neural network from the proof of Lemma A.3 with a single layer of non- non-linearity with 2kn hidden neurons, and parameter magnitudes bounded by n²? such that for every z' E R with 2 & (c, + 1 for every [kn]], we have NN = (z').
Let z' E R be such that for every E [km] we have z/ & (c, #.) For such z' we have No (z')= (z'). Hence, it suffices to show that we can construct an affine layer with 2k - n outputs, weights bounded by constant and bias terms bounded by n², such that given an input z E {0. 1 if it is an encoding of a hyperedge then all outputs are at most 11, and otherwise there exists an output greater or equal to 2. We construct such an affine layer in Lemma A.4
Lemma A.6. There exists a 2 neural network N3 with input dimension kn, at most n log(n) hidden neurons, kn < log(n) output neurons, and parameter magnitudes bounded by n² (for sufficiently large rt), which satisfies the following. We denote the set of output neurons of Na by Eg. Let z' E Ritn If there exists E [kn] such that z E (c. + 222) then there exists neuron in Es with
input at least 2. If for all i [km] we have 2 & (c 22, c [ then the inputs to all neurons in Eg are at most- -1.
Proof. It suffices to construct univariate depth-2 network f R R. a constant number of hidden neurons, such that for every input 2, E (c ,12 we have f(el) = 2. and for every 2 & (c- L,, + 32) we have f(2)) -1.
+ R with one non non-linear layer and
14

---

We construct f as follows:
(c- c- n² +
1 )
- -1z - 004
11/1-c1,
(1t ( c+
1 n22
) - 2 (ct ne )1.)
2
(3n²)
- 1.
Note that all weights and bias terms are bounded by Tē (for large enough rt).
Lemma A.7. Let = poly(n) and r poly(n). Then, there exists T poly(n) such that for a sufficiently large n, with probability at least - cxp((-n/2) vector (0, 7 I,) satisfies
|E& 9
Proof. Let gy2rm Every component & in & has the distribution (N00, 7?). By standard tail bound of the Gaussian distribution, we have for every i [r] and t 2 that Pris, 2 s 1a (-2rz)
2 exp
Hence, for t qVF' we get
2r2
272 (~Z2(pp)
2rng 2
Pr /
I 2exp
= 2 exp
= 2 exp (-n)
By the union bound, with probability at least r n we have
|K Sr. rg² q2
Thus, for sufficiently large n, with probability at least - exp(-n/2) we have ||E|| - 1.
Lemma A.8. If is pseudorandom then with probability at least i.i.d. imputs 2; DD the examples (Z,, (2),...,. (2m(n)+ (m(n)+n3)) returned by the oracle are realized by N.
26
39
(over & ~20,+²1p) and the
Proof. By our choice of r, with probability least 1 1 over & NNO, r21)), we have |k,1 S 1 for all [p], and for every ž with || < 2n the inputs to the neurons E,, Eg in the computation
n
Ñ (2) satisfy Properties (P1) through (P3) We first show that with probability at least 1 - 1 all
examples ă ....... (m) + satisfy ||2.] 2n. Henee, with probability least 1 - Properties (P1)
through (P3) hold for the computations (2,) for all E [m(n) + n3].
Note that || 12 has the Chi-squared distribution. Since 2; is of dimension n a concentration bound by Laurent and Massart (32 Lemma 1] implies that for all f we have
Pr
|
n² 2 2n + 2t S er
Plugging-in /. a² we get
Pr
||,
2 Pr
| 11 n² > 3n
3n'
Pr
1 2 n² >
2
n2
n²
Pr
| 2 n > 2n
2
4
n²
S exp
4
Thus, we have Pr [|] 2 2m] S exp (-a²) -
By the union bound, with probability at least
n²
(m(n) + n
exp
4
15

---

(for sufficiently large n), all examples (Z,, Ms) satisfy ||ž,|| - 2n.
Thus, we showed that with probability at least 1 2 > 39 (for sufficiently large ni), have 15 I 1 for all j E [p]. and Properties (P1) through (P3) hold for the computations ((,)) for all E (m(n) + n²]. It remains to show that if these properties hold, then the examples (21, Ui)................... .......(m((mu) (2m(n)+n3, Bm(x))4n)) are realized by N.
10
Let i E (m(n) + nn'.. For brevity, we denote ž = 2, U = U. and z' [akn] Since | S j E [p], and all incoming weights to the output neuron in N are -1, then in Ñ all incoming weights To -m and the bias term in the output neuron, denoted by b, is in 9 U1] Consider the following cases:
. for all TO
to the output neuron are in -
10 To.
If (z') is not an encoding of a hyperedge then y - 0, and (() satisfies:
1. If z' does not have components in (c,c #). then there exists a neuron in & with
output at least 3 (by Property (P2)..
2. If z' has component in (c, H) then there exists neuron in Eg with output least
2 (by Property (P3)
In both cases, since all incoming weights to the output neuron in N are in [- [-
10 - -
and b E
9 10 101 then the input to the output neuron (including the bias term) is at most and thus its output is O.
10 10
If v (z') is an encoding of a hyperedge S, then by the definition of the examples oracle we
have S = S,. Hence:
If x does not have components in (c n², 3,3), then:
* If y 0 then the oracle sets y b. Since S is pseudorandom, we have Px(25)
(x ) 1/2 0. Hence, in the computation (Z) the inputs to all neurons in &, &2, &g are at most 1/4 (by Properties (P1). (P2) and (P3)), and thus their outputs are O. Therefore, Ñ (2) 6. * If y = 1 then the oracle sets 0. Since S is pseudorandom, we have Px(z*) (x S.) y: L. Hence, in the computation Ñ (2) there exists neuron in E with output at least (by Property (PI) Since all incoming weights to the output
neuron in Ñ are in 10 1 and
1
10J then the input output neuron
10
(including the bias term) is at most 11
3
9 < 0, and thus its output is 0.
TO
10
If z' has component in (c. ) then 5 = O. Also, in the computation (z) there
exists a neuron in &g with output at least 3
2 (by Property (P3) b. Since all incoming
weights the output neuron in Ñ are in 11 [ and b Ioo 11]. then the input
to output neuron (including the bias term) at most TO 10 < 0, and thus its output is O.
z' does not have components in the interval (c.c+ ) but has component in the interval (c , c })) then:
* If y: = 1 the oracle sets ÿ = 0. Since S is pseudorandom, we have Px(z²) (z 9; 1. Hence, in the computation (2) there exists neuron in Er with output at least (by Property (PI) Since all incoming weights to the output neuron in Ñ are in [- T0 1 and b (including the bias term) is at most
9 [ then the input to output neuron 2 TO < 0, and thus its output is 0.
* If y: 0 the oracle sets ÿ 16 Na(2)) Since S is pseudorandom, we have Px(zS)= Px (z yA = O. Therefore, in the computation Ñ (2) all neurons in E,, &g have output (by Properties (roperties(PP]Jaann) (PI))and (P2)). and hence their contribution to
the output of Ñ' is O. Thus, by the definition of Ng. we have (z) = 1b- N2(2))+.
16

---

Lemma A.9. S is pseudorandom, then for sufficiently large n, with probability greater than Gan we have
E1(h)) 2
Proof. By Lemma A.8 if S is pseudorandom then with probability at least 39 (over ~ NO, 7² 4p) and the i.i.d. inputs 2; D) the examples (11.9)).-- (.),.... (Zm())) Vm(n)) returned by the oracle are realized by Ñ. Recall that the algorithm & such that with probability at least 1 (over & ~ N/ 7² I)), the i.i.d. inputs 2; ~ D, and possibly its internal randomness), given a size-m(n) dataset labeled by Ñ, returns hypothesis such that EgzD (h(2) - N(2)) S 1 Hence, with probability at least - In labeled by our examples oracle. Indeed, note that L can return bad hypothesis only if the random choices are either bad for & (when used with realizable examples) or bad for the realizability of the examples returned by our oracle. By the definition of h and the construction of N, if h has small error then h also has small error, namely,
40
- the algorithm L returns such good hypothesis h, given vn(n) examples
(M(2)) - N(2)) 2nD
(1 N())) s
1
E
IR 2ND
Let (1h)'= [7] Eie ( - 2² Recall that by our choice of T we have Pr[b > 10
11 S //-
Since, (h'(z) - -2( [0, for all ă R= by Hoeffding's incquality, we have for a sufficiently large n that
Pr
(1((h)) E (1h))
5
2
- n
= Pr
(1(K))) E (h)) 5,
IV
3
6
18
Pr
10
+ Pr
(((h') - E ((((h))
IV
5
1F
Pr
2n
< 2exp
.111
214
1
40
Moreover, by Lemma A.8
Pr # + s Pr Pr Us [(z))
40
Overall, by the union bound we have with probability at least sufficiently large n that:
(1
+
for
40
10
10
Es, (h')) = ELND (N'(2) - N(z)) 2
(e((10) - Es, &,(10) t.
((N) - (,4)
Combining the above, we get that if S is pscudorandom, then with probability greater than & we have
E ())) + B. (,(h') (1()() (E,(0)) - -E(0)) + (R/(N)
1 2 n
5
+
St
Si
n n
Lemma A.10. Let z {0, 1 be random vector whose components are drawn i.i.d. from Bernoulli distribution, which takes the value O with probability L. Then, for a sufficiently large n, the vector z is an encoding of hyperedge with probability at least Tog
17

---

Proof. The vector z represents hyperedge iff in each of the & size-n slices in z there is exactly one O-bit and each two of the k slices in z encode different indices. Hence.
A:
nk-k
1 m2
1
Pr [z represents hyperedge] = n (n - 1) (n k+
1)
71
k(n-1)
k
n
n
k
k
1
k(n-1)
n
Since for every (0, have e < 1
2
then for sufficiently large the above is at least
(-
2k
2k(n 1)
exp
exp
exp (-1) eexp (-2k) 2 log(n)
n
n
Lemma A.11. Let E Bn² be the vector returned by the oracle, We have
Pr ZE 2 2 2 log(nn)
Proof.
Let z'
[[ke] We have
1 2 n n 7j [km] s.t. z/j E (c- ( ++
Pr
2 E
2
S Pr
Pr (z') does not represent hyperedge]
(1)
We now bound the terms the above RHS. First, since z' has the Gaussian distribution, then its components drawn i.d. from density function bounded by L. Hence, for sufficiently large we have
1 2T
3
3k 2mn
log(n)
Pr Fj E [km]] s.t. z/ E
c+ c- n c
S kn
n²
n
n
Let (z'). Note that is random vector whose components are drawn i.i.d. from Bernoulli distribution, where the probability to get 1. with probability at least log(n) Combining with Eq. 11 and 2 we get for sufficiently large n
n. By Lemma A.10 z an encoding hyperedge
that
Pr 2
log(n) + (1 log(n)
1
<
2 log(n)
as required.
Lemma A.12. If S is random, then for sufficiently large n with probability larger than 2 we have
2
(x(h')
Proof. Let 2 C TR² such that ž E 2 iff [[m)] does not have components the interval (c- 1, 23, and (()))))) = x for a hyperedge S. If S is random, then by the definition of our examples oracle, for every E [m(n) + n²] such that 2; E 2, we have f, d with probability and 0 = 0 otherwise. Also, by the definition of the oracle, 0 is independent of S; and independent of the choice of the vector 2, that corresponds to S. If > 16 then for sufficiently large the
18

---

hypothesis h' satisfies for each random example (2,, E St the following
Pr (Rg.3))
(Z.) :i:)² 2 5]
Pr (2,thh)
(h'(z,) - -0 N
2; E 2
Pr
2 E Σ
2,
2
b
Pr
(z,) - - >
2 E 2
Pr 2 E 2
(2:)91)
2
Pr
2i
2
2i
In Lemma A.11
show that Prz
i E
2
2
llg(n) Hence,
1
1 4lg((n)
Pr
(M((2))
-ū:)²²
(R.:5:)
5
2
2 llgg(n)
Thus, 6 2 1O
then we have
1
[ 2
5 llo((n)
20 log(n)
Therefore, for large n we have
7
Pr
E [er(h')]
2
20 log(n)
n1
Since, (h'(2) - 7)² E [0, 62) for all 2, y returned by the examples oracle, and the examples ž, for i I are ii.d., then by Hoeffding's incquality, we have for sufficiently large that
Pr (1hh')
E (hh)) 5,
2 = Pr
(1())
- E (hh) 3,
IV
2 21
6-
5 14
Pr
8
10
+ Pr
(T(1') - E (7(h') S
IV
112
111
1F
Pr
(-m2 2n
< 2eex
(n>(11/1oj4)
-111
n
V
Hence, for large enough n, with probability at least 1 -
2 we have both Eg, [e)(1')) 2
20 [0gg and (h') Es, (h)) $ n. and thus
2 > n
(((h)) Z 20log(n)
B Proof of Corollary 3.1
By the proof of Theorem 3.1 under Assumption 2.1 there is no poly(d)-time algorithm L, that satisfies the following: Let 0 < R2 be B-bounded parameters of a depth-3 network No IR + R. and let T, e > O. Assume that B, 1/e, 1/7 S (oly(d), and that the widths of the hidden layers in No are d (i.e., the weight matrices are square). Let & E (0, and let Ô = 0 &. Then, with probability at least 3 4 1000 given access to an examples oracle for Ng. the algorithm L, returns hypothesis h with Ex [(h(x) N {) <c
Note that in the above, the requirements from L. are somewhat weaker than our original definition of learning with smoothed parameters. Indeed, we assume that the widths of the hidden layers are d and the required success probability only 3 I (rather than }). We now explain why the hardness result holds already under these conditions:
1oo0
19

---

Note that if we change the assumption on the learning algorithm in proof of Theorem 3.1 such that it succeeds with probability at least 3 To0o (rather than }). then in the case where S is pseudorandom we get that the algorithm A returns with probability at least
1- + 1000 40 + 40 + a0 (see the proof of Lemma A.9), which is still greater than 3" Also, the analysis of the case where S is random does not change, and thus in this case A returns with probability greater than? 3. Consequently, we still get distinguishing advantage
greater tham? 3.
Regarding the requirement on the widths, note that in the proof of Theorem 3.1 the layers satisfy the following. The input dimension is d = =n² the width of the first hidden layer is most 3n ln)(n) S d, and the width of the second hidden layer is most lng(n) + 2n + n log(n) S d (all bounds are for a sufficiently large d). In order to get a network where all layers are of width d, we add new neurons to the hidden layers, with incoming weights O, outgoing weights 0, and bias terms -1. Then, for an appropriate choice of = 1/ poly(n), even in the perturbed network the outputs of these new neurons will be 0 w.h.p. for every input ....... zm² and thus they will not affect the network's 's output. Thus, using the same argument as in the proof of Theorem 3.1] we conclude that the hardness results holds already for network with square weight matrices.
Suppose that there exists an efficient algorithm Ep that learns in the standard PAC framework depth-3 neural networks where the minimal singular value of each weight matrix is lower bounded by l/g(d) for any polynomial g(d). We will use Lp to obtain an efficient algorithm L, that learns depth-3 networks with smoothed parameters as described above, and thus reach a contradiction.
Let E RR be B-bounded parameters of a depth-3 network No I2 + R. and let T, e > O. Assume that p. 1/, / V poly(d), and that the widths of the hidden layers in No are d. For random E O. 12 pp) and = 0 E. the algorithm L. has access to examples labeled by Ng- Using Lemma B. below with t- = _ and the union bound over the two weight matrices in No. we get that
with probability at least - 22.33
- 1000 (for large enough d), the minimal singular values of all for some sufficiently large polynomial (cd). Our algorithm L. will simply run Lp. Given that the minimal singular values of the weight matrices are at least क(क) the algorithm Cp runs in time poly(d) and returns with probability at least a hypothesis h with Ex [(hxx) N (x) < e. Overall, the algorithm L, runs in poly(d) time, and with probability at least? 1 TOU0 (over both & and the internal randomness) returns a hypothesis i with loss at most
vd
weight matrices in i are at least
q(d]
Lemma B.1 (Sankar et al. 377. Theorem 3.3). Let W be an arbitrary square matrix in Rddd, and let P E Bddd be a random matrix, where each entry is drawn i.i.d. from (0, 7²) for some 7 >> O. Let oa be the minimal singular value of the matrix W + P. Then, for every t >> 0 we have
tVd
Pr S [| 2.35 2.35
p
C Proof of Theorem 3.2
The proof follows similar ideas to the proof of Theorem 3.1 handle here a smoothed discrete input distribution rather than the standard Gaussian distribution.
The main difference is that we need to
For sufficiently large n. let D be distribution f0, 1)=², where each component is drawn i.i.d. from a Bernoulli distribution which takes the value 0 with probability A. Assume that there is a poly(n) ttimee algorithm & that learns depth-3 neural networks with at most n² hidden neurons and parameter magnitudes bounded by n²², with smoothed parameters and inputs, under the distribution D. with = 7 and 7, w = 1/ (nly(n) that we will specify later. Let m(n) S poly(n) be the sample complexity of L, namely, L uses a sample of size at most m(n) and returns with probability least
hypothesis h with E [(((2) Nz(z)) < 1. Note that D is the distribution D after
smoothing with parameter w, and the vector is the parameters of the target network after smoothing with parameter 7. Let > 1 be constant such that n² m(n) + n² for every sufficiently large By Assumption 2.1 there exists a constant & and predicate P {0, 13 {0, 1}. such that F
20

---

is 3 .PRG We will show an efficient algorithm A with distinguishing advantage greater than 3 and thus reach a contradiction.
Throughout this proof, we will use some notations from the proof of Theorem
We repeat the following encoding of S: the vector z is a concatenation of k vectors in {0. 1]",, such that the j-th vector has in the i- coordinate and elsewhere. Thus, 2 consists of k size-n slices, each encoding member of S. For E {0, 1)Am, E [k] and j E [n]] we denote Zi.j
here for convenience. For hyperedge S = (A1,-...44 ..k) denote by 2 E (0. Rm
F)i-1) That is, 2a,j is the j-th component in the i-th slice in z. For x E {0, 1)", let Px {00, 1] + {0. 13 be such that for every hyperedge S we have Px (2 P(xs). For 2 E RTn we denote [(xx]] = (#1,-... San), namely, the first kn components of 2 (assuming n² 2 kn).
C.1 Defining the target network for L
Since our goal is to use the algorithm L for breaking PRGs, in this subsection we define neural target network for L. The network N contains the
network N: Rn² -> R that will later subnetworks N1, N2 that we define below.
Let Ni be depth-1 neural network (i.e., one layer, with activations in the output neurons) with input dimension kn, at most log(n) output neurons, and parameter magnitudes bounded by n² (all bounds are for sufficiently large n), which satisfies the following. We denote the set of output neurons of N1 by & Let E {0, 1 be an input to N1 such that z = = for some hyperedge S. Thus, even though N1 takes inputs in R&m, we consider now its behavior for an input z' with discrete components in {0, 1}. Fix some x E {0, )). Then, for S with (2) = 0 the inputs to all output neurons E are most 1, and for S with Px (zx)
there exists a neuron in & with input at least 2. Recall that our definition of neuron's 's input includes the addition of the bias term. The construction of the network N1 is given in Lemma A.2 Note that the network N1 depends on x. Let Ní. 4 - I be a 2 neural network with no activation function in the output neuron, obtained from Ni by summing the outputs from all neurons &
Let N2 be depth-1 neural network (i.e., one layer, with activations in the output neurons) with input dimension kn, most 2n output neurons, and parameter magnitudes bounded by n² (for sufficiently large n), which satisfies the following. We denote the set of output neurons of N₂ by &g. Zet E (0. 1 be an input to N2 (note that it has components only in {0. 1)). If z' is an encoding of a hyperedge then the inputs to all output neurons & are at most 11, and otherwise there exists a neuron in &g with input at least The construction of the network N₂ is given in Lemma [A.4] Let N₂-- : R + R be depth-2 neural network with no activation function in the output neuron, obtained from N₂ by summing the outputs from all neurons E2.
Let N' p + R be depth-2 network obtained from Ni.N% as follows. For z' E R we have N'(z') = [1 (z(2z) (2 The network N' has at most n² neurons, and parameter magnitudes bounded by n² (all bounds are for a sufficiently large n). Finally, let Ñ: R=n R be depth-2 neural network such that (2) N' (ā)m)))
C.2 Defining the noise magnitudes T, and analyzing the perturbed network under perturbed inputs
In order to use the algorithm w.r.t. some neural network with parameters θ and a certain input distribution, we need implement an examples oracle, such that the examples are drawn from smoothed input distribution, and labeled according to a neural network with parameters 0 where g is a random perturbation. Specifically,
use L with an examples oracle where the input distribution D is obtained from D by smoothing, and the labels correspond to network Ñ R=² + IR obtained from Ñ (w.r.t. an appropriate x E (0, 1)" the construction of N1) by adding small perturbation to the parameters. The smoothing magnitudes w. of the inputs and the network's 's parameters (respectively) are such that the following hold.
We first choose the parameter т = 1/ poly(n) as follows. Let So R=² + R be any depth-2 neural network parameterized by 0 E R² for some >> 0 with at most n² neurons, and parameter magnitudes bounded by n² (note that r is polynomial n). Then, is such that with probability at least 1 1 over (0 - I.). we have [al < 1 for all e [r]. and the network fe-g is such that 10
21

---

for every imput 2 E R"² with ||||| S n and every neuron we have: Let a, be the inputs to the neuron in the computations fz) and f (Z) (respectively), then |a - bl < 7. Thus, 7 is sufficiently small, such that w.h.p. adding i.i.d. noise (0 r²) to each parameter does not change the inputs to the neurons by more than z. Note that such an inverse-oolynomial exists, since when the network size, parameter magnitudes, and input size are bounded by some poly(n), then the input to each neuron in fz( is poly(n)-Lipschitt as function of O, and thus it suffices to choose that implies with n
for a sufficiently large polynomial ((2) (see Lemma A.7 probability at least 1 1 that ||||| S q(n)
for details).
Next, we choose the parameter w = 1/ poly(n) as follows. Let fo : RT - R be any depth-2 neural network parameterized by 0 with at most n² neurons, and parameter magnitudes bounded by n² + To. Then, w is such that for every z {0, 10.1 with probability least 1 exp(-n/ over C <~ (~, IIn)) the following holds for every neuron the fe: Let a, be the inputs to the neuron in the computations fe and fe(z + <) (respectively), then la bl S 3.- Thus, w is sufficiently small, such that w.h.p. adding noise N(0 - I,2) to the input z does not change the inputs to the neurons by more than 1. Note that such an inverse-polye pverse-polynomial i exists, since when the network size and parameter magnitudes are bounded by some poly(n), then the input to each neuron in fz) is polyshi)-ipschhitz as a function of z, and thus it suffices to choose w that implies with probability at least 1 - exp(-n/22 that ||$|| S I for sufficiently large polynomial g(n) (see Lemma A.7 for details).
q(n)
Let 0 E R' be the parameters of the network N. Recall that the parameters vector θ is the concatenation of all weight matrices and bias terms. Let 0 E TRP be the parameters of N, namely, i 0 + & where & ~ (N( 7 Ip)) By our choice of and the construction of the networks N1, N2. with probability at least
1 over &, for every z E {0, 13m" the following holds: Let Ç ~ ((0,w²),e) and let 2 = z + Ç. Then with probability at least exp(-n/2) over Ç the differences between inputs to all neurons in the computations (2) and (z) are at most 1. Indeed, w.h.p. for all z E {0,1)* 13"" the computations (zz) and Ñ (z) are roughly similar (up to change of 1/4 in the input to each neuron), and w.h.p. the computations (z) and (2) are roughly similar (up to change of 1/4 in the input to each neuron). Thus, with probability at least 1 over &, the network Ñ is such that for every z E {0, 1}"", we have with probability at least - exp( (n/2) over { that the computation (2) satisfies the following properties, where z' := [kkm]
n
(QI) If z' = =z for some hyperedge S, then the inputs to E satisfy:
If Px(2)) 0 the inputs to all neurons in & are at most 2
If Px = 1 there exists a neuron in E with input at least 2
(Q2) The inputs to Eg satisfy:
If z' is an encoding of hyperedge then the inputs to all neurons Eg are at most -1.
Otherwise, there exists neuron in & with input at least 3
C,3 Stating the algorithm A
Given a sequence (51,)),.... (Sar, where St,..., Su are i.i.d. random hyperedges, the algorithm A needs to distinguish whether y = (U1,..., .ur) is random or that y = (P(xs)),.... P(xs,..) = (22 (((Sm)) for a random x E 10.1)". Let S ((z)) ..))...... (z )).
We use the efficient algorithm L in order to obtain distinguishing advantage greater than 3 as follows.
Let & be random perturbation, and let Ñ be the perturbed network as defined above, w.r.t. the unknown x E {0, 1l. Note that given a perturbation &, only the weights in the second layer of the subnetwork N1 in N are unknown, since all other parameters do not depend on x. The algorithm A runs L with the following examples oracle. In the i-th call, the oracle first draws z' e {0, km such that each component is drawn i.i.d. from a Bernoulli distribution which takes the value 0 with probability 1. If z is an encoding of hyperedge then the oracle replaces z' with z Let x E {0, 13" 1 be such that Z[kn] z', and the other n² - kn components of are drawn i.i.d. from
22

---

a Bernoulli distribution which takes the value 0 with probability 1. Note that the vector has the distribution D. since replacing an encoding of random hyperedge by an encoding of another random hyperedge does not change the distribution of z'. Let 2 = z + S. where Ç ~ N(,, " T,a). Note that 2 has the distribution D. Let b IR be the bias term of the output neuron of N. The oracle returns (2, f), where the labels 9 are chosen as follows:
If zz' is not an encoding of a hyperedge, then 9 O.
* If zz' is an encoding of a hyperedge:
If yi we set 9 b.
- If y/ = 1 we set 9 = 0.
Let h be the hypothesis returned by L. Recall that L uses at most m(n) examples, and hence S contains at least n examples that L cannot view. We denote the indices of these examples by I- == {m(() + 1,..., m(n) + n²), and the examples by S {(z y:)ee By n² additional calls the oracle, the algorithm A obtains the examples Š; [ Di))eer that correspond Sr. Let h/ be a hypothesis such that for all ă E IR"" we have h'(z) = max(0, min (()))), thus, for b 2 0 the hypothesis h' is obtained from h by clipping the output to the interval [o, 6j. Let (h') J Cher(h((z,, - 9.)². Now, if ( S 3, then A returns 1, and otherwise it returns O. We remark that the decision of our algorithm is based on h (rather than /)) since we need the outputs to be bounded, in order to allow using Hoeffding's inequality in our analysis, which we discuss in the next subsection.
C.4 Analyzing the algorithm A
Note that the algorithm A runs in poly(n) time. We now show that if S is pseudorandom then A returns 1 with probability greater than 2 and if S is random then A returns 1 with probability less than 3. To that end, we use similar arguments to the proof of Theorem 3.1
3.
In Lemma C.I. we show that if S is pseudorandom then with probability at least 39 (over & ~ TU (O TT and C2 ~ NN wT)))))))) for all i E [m(n)]) the examples (&1:91).-.. (2m(n): Pmmt)) returned by the oracle are realized by Ñ. Recall that the algorithm L is such that with probability at least 1/2 (over & ~ NN 12), the i.i.d. inputs é; D. and possibly its internal randomness), given size-m(n) dataset labeled by Ñ, it returns a hypothesis such that T (1(2)) - N())) S 1.
Hence, with probability at least examples labeled by our examples oracle. Indeed, note that L can return a bad hypothesis only if the random choices are either bad for L (when used with realizable examples) or bad for the realizability of the examples returned by our oracle. By the definition of h and the construction of Ñ, if h has small error then / also has small error, namely,
1 the algorithm C returns such a good hypothesis h, given m(n) 40
(h((2) - N(2)) 2nD
E
S E. 2ND
[1(2)-
- N(2)) $
Let (r(h') 1/ (h - (2.))) Recall that by our choice of r we have Pr(l >
To. S +.
Since, (h'(z) - (())) 60 for all 2 R by Hoeffding's inequality, we have for a sufficiently
large n that
Pr
((((h)) 5
E (r(('')
>
1
= Pr
[2(()) E (h() 51
1V
31 21
5
1A
alF
P
5
n
+ Pr
(y(h') - E ((()'))
IV
11-
V
11
Pr
S
10
2n
< 2exp
In2(11110z²
-111
21-
< 1
40
23

---

Moreover, by Lemma C.I
Pr (((()))((00)) = Pr Ds + N(.)
40
Overall, by the union bound we have with probability at least sufficiently large that:
(1
40 >
for
40
40
(s,,i((h) EnND (M(()) ((())-N(Z))? =
[((K) - Es, (1() 1.
(000 (0)))
Combining the above, we get that if is pseudorandom, then with probability greater than 3 we have
(1hh) = (+(00)-&((0)) + (1(0)) E S, (((( + (h) 50+
+ n
S,
We now consider the case where random. For an example 2; = 2, + C; returned by the oracle, we denote z/ = (2.) E (0, Jkmn Thus, z is the input that the oracle used before adding the n kn additional components and adding noise ç, Let Z' C (0, 13 be such that z' Z' iff = z for some hyperedge S. If S is random, then by the definition of our examples oracle, for every i [m(n) + n²] such that z E Z', we have J = with probability and ÿ: = 0 otherwise. Also, by the definition of the oracle, Ú; is independent of S, independent of the n² kn additional components that where added, and independent of the noise C; NO w² I,,)) that corresponds to 2,
2
9. then for sufficiently large n the hypothesis / satisfies for each random example
10
(2,, 91) Sy the following:
1
Pr (2..9.)
(N())) 01)2²²
5
1
2 Pr (2.))))
(h'(2,) 02)²
2 Z'
Pr 1z! z'|
b
Pr (R..0s)
(h'(2,) 0.)3
z Z'
Priz E 2'
2
2 2
Pr (2' E 2"
In Lemma A.10 we show that for sufficiently large we have Pr [Z] E Z'|
Hence,
log(n)
Pr (#.))))
(N((2) 01)
2
1 2
5
2 log(n)
2 2log(n)
Thus, i
then we have
1O
1
[h()]
2
S
2 log(nn)
10 10
Therefore, large n we have
1
7
Pr E [er(h')]
>
1
10 log
n
8
24

---

Since, (h'(2) 0) E 62) for all 2, 9 returned by the examples oracle, and the examples 2; for i I are ii.d., then by Hoeffding's inequality, we have for sufficiently large n that
Pr (((h))
(()) S,
1 1 = Pr 2
(1(1)
E. (1()) 5,
IV
3 31
5
Pr
8
-
11
n
10
+Pr
(T(N)) - E Ei(h') 5
IV
21
3
7
10
Pr
10
(-m2 2n
$
2exp
'n2(11/10)**
-1+1
n
V1
Hence, for large enough n, with probability at least 1 8
3
3
2
we have both Es, [er(N()) 2
[1] and [e(hh)) Es, (x())) s # and thus
2 >
(((N) 10 10log(n)
n
n
Overall, if S is pseudorandom then with probability greater than 3 the algorithm A returns 1, and S is random then with probability greater than the algorithm A returns O. Thus, the distinguishing advantage is greater than 3/2 This concludes the proof of the theorem. It remains to prove the deffered lemma on the realizability of the examples returned by the examples oracle:
Lemma C.I. I is pseudorandom then with probubility al least 30 over & N(O0,²;pp) and S; ~ ~~ w² Ln2) for i E [m(n) + n²*), the examples (21, (2.91)...... (2m(n)+)) (ma(n)+a3) returned by the oracle are realized by N.
Proof. By our choice of T and w and the construction of N1, with probability at least 1 -
over & ~ "=(00,77 T2)), we have |tyl S 1
To for all j E [p]. and for every z E {0, 13m² the following
holds: Let Ç ~ NN(0, NN(O," and let 2 = z + Ç. Then with probability at least 1 - exp( n/
over Ç the inputs to the neurons & & in the computation (2(2) satisfy Properties (Q1) and (Q2)
Hence, with probability at least
=/- (m(n) + n²3 exp( -n/2) 2 1 2 (for a sufficiently large
n m). [5,] S To for all j E [p], and Properties (Q1) and (Q2) hold for the computations (2,) for all
i E [m(n) + n²).. It remains to show that if T S TO for all j E [p] and Properties (Q1) and (Q2)
hold, then the examples (21, f1), (2m(()) +n (m(n)) are realized by N.
Let E [m(n) + n3]. We denote é, = 2, + C,, namely, the i-th example returned by the oracle was obtained by adding noise S, to z, E {0, 10."""" We also denote z = (2:)(Rm) E (0, 1) )dm Since kgyl S to for all j E [p). and all incoming weights to the output neuron in N are 1,, then in N all incoming weights to the output neuron are in - 10: ] and the bias term in the output neuron,
11
denoted by i, is in 1 Wd] Consider the following cases:
If z is not an encoding of hyperedge then ús 0. Moreover, in the computation (2.).
there exists neuron in & with output at least (by Property (Q2) Since all incoming
weights to the output neuron in N are in |- 11 Io ) and i
E I0 10.
111 then the input to
the output neuron (including the bias term) is at most 10 2 10 0.
3 9
< 0, and thus its output is
If zz' is encoding of hyperedge S. then by the definition of the examples oracle we have S S.. Hence:
- If y/4 0 then the oracle sets ú = b. Since S is pseudorandom, we have (x(2
Px = yi = 0. Hence, in the computation (2.) the inputs to all neurons in E,. & and and (2)). and thus their outputs are 0. Therefore,
are at most - 2 (by Properties ( (Q1)
Ñ (2.) = b.
25

---

If y then the oracle sets Ds = 0. Since S is pseudorandom, we have (x ) y/ 1. Hence, in the computation N (2.) there exists a neuron in E with
output at least 3 (by Property (Q1) Since all incoming weights to the output neuron
in N are in | 11 ]. and b 10 10. then the input to output neuron (including the bias term is at most
9.
10
and thus its output is O.
26


Reviews:
[{"review_id": "q6B6n96Jwn", "reviewer": "Reviewer_Hkzt", "summary": "  This paper addresses the complexity of learning neural networks, a\nvery fundamental problem in learning theory. Previously, some \ncomplexity and efficient solvability results were known for networks \nof depth 2.  The paper shows that when the depth is increased to\n3, the learning problem becomes computationally intractable (under\na hypothesis on the existence of local pseudorandom generators) \neven when one uses the assumptions (e.g., Gaussian input distribution,\nnon-degeneracy of the weight matrix) that lead to efficient algorithms\nfor the depth-2 case.  The paper also shows that the learning problem\nfor depth-2 networks is hard under a smoothed analysis framework\n(where both the input distribution and the network parameters are\nperturbed).", "questions": "(1) You prove hardness results for depth-3 neural nets. Can the proofs\n  be extended (in a simple way) to show that the hardness results also hold for\n  depth-k neural nets for any k >= 3?\n\n  (2) Assumption 2.1 (on the existence of local PRGs with certain properties)\n  is used in your proofs. You cite references that provide evidence for the\n  assumption. It will be useful to the readers if you can include a short discussion\n  on the evidence in the paper itself. Are there any consequences if\n  Assumption 2.1 does not hold?", "limitations": "None", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(a) Understanding the boundary between hard and easy cases of learning\n    neural networks is an important problem in learning theory. This is a \n    very nice contribution to that area.\n  \n   (b) The paper provides a nice summary of previous work which makes\n   it easier to understand the context for the contributions.\n\n   (c) The technical results are presented very well.", "weaknesses": " This reviewer can't see any weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review.\n\nRegarding the questions:\n1. Yes, the result can be easily extended to any $k \\geq 3$ by appending to our construction additional layers. We will add a remark about it in the camera-ready version. \n2. Indeed, we referred the reader to papers where this assumption is discussed. One notable evidence for our assumption was shown by Applebaum [1]. He showed that our assumption follows from a variant of Goldreich’s one-wayness assumption (Goldreich, 2000). In addition, there is a concrete candidate for a local PRG, which is based on the XOR-MAJ predicate, and was shown to be secure against all known attacks. A more detailed discussion of our assumption can be found in [15, Section 2.2]. We will add some details on this subject in the camera-ready version. \n"}, {"review_id": "tBmrYKA95i", "reviewer": "Reviewer_nyVW", "summary": "The submission studies the classical problem of constructing ReLU-activated neural networks, specifically from the learning point of view. Previous work has established the existence of an efficient learning learning algorithm for learning depth-2 ReLU networks under the Gaussian distribution assuming a non-degenerate weight matrix. The authors provide a lower bound that rules out an extension of this result to depth-3 ReLU networks even under the \"smoothed analysis\" framework, where one assumes the presence of random noise to avoid the use of \"degenerate\" instances in the hardness reduction. As a second result, the authors provide a lower bound that rules out the extension of the aforementioned algorithm on the Gaussian distribution to general smoothed distributions.", "questions": "N/A; however, the authors are of course welcome to respond to the individual points raised in the review.", "limitations": "The limitations have been adequately addressed.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The construction of ReLU-activated neural networks is a central topic at NeurIPS, and other lower-bound results on the problem have also appeared at the proceedings. The article is well-written and the results are non-trivial. ", "weaknesses": "My main issue with the submission is that the newly obtained lower bounds seem to only shift the boundaries of intractability by a very small step compared to what was known previously. In particular, previous results of Daniely and Vardi [15] already ruled out (under the same complexity-theoretic assumptions) an efficient learning algorithm for the setting studied in this submission, with the distinction being that their lower bound does not operate in the \"smoothed analysis\" framework. The same work of Daniely and Vardi [15] also established a lower bound that matches the second result in this submission, but once again without the use of the \"smoothed analysis\" framework. In this sense, it seems to me that the main contribution of the submission is showing that previously established lower bounds do not require the use of purely degenerate cases. In combination with the fact that the lower-bound proof itself builds on the approach introduced by Daniely and Vardi [15], I cannot help but feel that the present submission is somewhat incremental in nature. \n\nAlso, a clearer and more to-the-point comparison of the submission's results to those obtained in the previous work(s) of Daniely and Vardi would have been appreciated... but that is only a minor (and perhaps subjective) point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their efforts.\n\nOur hardness results show that learning neural networks under the Gaussian distribution is hard already for non-degenerate instances. This is in contrast to all previously known hardness results for learning neural networks. Since for depth-2 networks the non-degeneracy assumption makes the problem solvable in polynomial time, we think that our hardness result for depth-3 is surprising. Also, from the technical point of view, the required construction is highly non-trivial, and differs significantly from [15]. Thus, we believe that the contribution of the current paper is significant both at the conceptual and technical levels. \n"}, {"review_id": "dw55NjiwH7", "reviewer": "Reviewer_fAAD", "summary": "This paper studies the computational complexity of learning 3-layer neural networks under the standard Gaussian distribution. Specifically, under a standard cryptographic assumption on the existence of local pseudorandom generators, the authors show that there is no poly-time algorithm that can learn 3-layer networks under the smoothed analysis framework. As a corollary, they show learning 3-layer networks is hard even with assuming a lower bound on the smallest singular values of the weight matrices.", "questions": "- I find the main text of the paper, in particular section 4, to be quite difficult to understand. The proof of the main theorem is written in a lengthy paragraph format, and as such I think the paper could be improved by organizing the exposition in section 4. Some concrete suggestions are the following:\n    - The authors could add a high-level proof sketch at the beginning of section 4 before diving into the details of the argument. This could be particularly helpful to readers who are not familiar with the argument of [15], and complexity theory more generally (and may make the paper more suitable for a NeurIPS audience).\n    - Key lemmas (such as Lemmas A.4 - A.6) could be stated explicitly in the main text, to make more clear what the various steps in the proof are.\n    - Both the examples oracle and algorithm $\\mathcal{A}$ could be written in algorithm format, to make more clear what exactly they are computing.\n- I am a bit confused about what the point of the examples oracle is in Section 4.3, and how this is being used by the algorithm. Could you please clarify this further?\n- As mentioned in the weaknesses section, the paper would benefit from additional comparison to [11], in particular the novelty and a comparison between the LWR and PRG cryptographic assumptions.\n\n[15] A. Daniely and G. Vardi. From local pseudorandom generators to hardness of learning. In Conference on Learning Theory, pages 1358–1394. PMLR, 2021.", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- It is an interesting question to understand the worst-case hardness of learning neural networks, and under what assumptions learning is possible. Prior work has shown 2-layer networks can be learned under the smoothed analysis framework. The current paper, however, shows that learning 3-layer networks in the smoothed setting is hard, which is quite an interesting result.\n- At a high level the proof appears to be sound, however I admit that I do not work on complexity theory and am unable to verify the proofs fully.", "weaknesses": "The novelty of the paper seems limited, particularly in light of the related work [11]. [11] shows that learning three-layer networks is hard, under the Learning With Rounding (LWR) assumption. [11] considers three-layer networks with no activation in the last layer, while the current paper considers networks with an activation in the last layer, but this last-layer activation seems like a very minor difference. Can the authors please comment further on the novelty of the current paper in comparison to this prior work?\n\n[11]  S. Chen, A. Gollakota, A. R. Klivans, and R. Meka. Hardness of noise-free learning for two-hidden-layer neural networks. arXiv preprint arXiv:2202.05258, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions.\n\nRegarding the comparison to [11]: \nIn [11], the authors showed hardness of learning depth-3 networks under the Gaussian input distribution, but the neural network in their construction is degenerate. Hence, their result does not imply hardness of learning non-degenerate networks, and does not imply hardness under the smoothed-analysis framework. Moreover, despite some efforts that we made in this direction, we do not see a way to extend their technique to these settings. The novelty in the current paper is that we establish hardness results for non-degenerate networks and hardness under the smoothed-analysis framework. We view this contribution as significant and surprising, as for depth-2 networks the non-degeneracy assumption makes the problem solvable in poly time. As the reviewer mentioned, there are additional distinctions between our results and [11], which we view as more minor, such as different cryptographic assumptions and the existence of activation in the output neuron. As we discuss in the paper, our cryptographic assumption is considered established, but we do not think that there is a formal way to make a comparison to their LWR assumption (it is essentially a matter of taste). \n\nRegarding the readability of the proof in Section 4: We will try to apply the reviewer's suggestions to make the proof a bit easier to follow.\n\nRegarding the examples oracle in Section 4.3: As we define in Definition 2.2, a learning algorithm has access to an examples oracle, and returns w.h.p. a hypothesis that performs well on fresh examples from the examples oracle. In our proof, we assume that we have an efficient learning algorithm for smoothed depth-3 neural networks, and we run it with the examples oracle defined in Section 4.3 in order to break the PRG as follows. If the hypothesis returned by the learning algorithm performs well on fresh examples from the examples oracle then the data is pseudorandom, and otherwise it is random. If the reviewer has further questions on this issue we will be happy to elaborate more.\n"}, {"review_id": "xIaWkpXdaU", "reviewer": "Reviewer_fpWr", "summary": "The paper presents results on the nonexistence of efficient learning algorithms for $3$-depth ReLU networks with smoothed parameters and Gaussian input. It also proves that in general, there is no efficient learning algorithm for $2$-depth ReLU networks with smoothed parameters and smoothed inputs (the smoothness is applied to a specially constructed input, which is Bernoulli). The neural networks they analyze, unlike previous works, have a ReLU unit at the single output.", "questions": "Please, see above, in the section \"Weaknesses\" of this review.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is theoretical in nature and so it is good that it is rigorous in its analysis and seeks to provide enough detail to understand its proofs. The paper presents its results in a logical order.", "weaknesses": "I will first introduce my main concerns, and then other important observations to address. (I must say that I haven’t followed Section 4 with enough detail, though I do have some observations based on what I read.)\n\n1) I am trying to understand the relevance of the learning problem studied by the paper. When talking about learning, from what I can recall, I have basically seen two approaches in the literature: \n\nCase a) When training a neural network, e.g. using SGD, one of the things we are concerned about is the testing performance of the network after being trained for some number of iterations or number of epochs.\n\nCase b) I have seen other works that are concerned on generalization issues in terms of how close is the empirical loss (with respect to samples of the input data) from the population loss (defined by the expected value with respect to the input data distribution), which such closeness depending on different parameters such as the number of samples being used, the width of the network, the depth of the network, etc. \n\nBoth of these cases tackle the issue of how well a neural network learns and generalizes. However, the paper seems to tackle the problem of actually learning a given neural network (see Definitions 2.1 and 2.2), where the true parameter of the neural network is chosen adversarially (and sometimes smoothed afterwards). In the paper, essentially, the learning is done by some algorithm that outputs some hypothesis that seeks to approximate the adversarial neural network. However, how is this relevant in the context of training neural networks and their testing/generalization performance? The type of works in Case a) and  Case b), though theoretical, are trying to understand some practical issues in neural network learning that is relevant to the general ML community, but I don’t see such immediate connection in this paper. In which situations do we care about “learning a neural network” instead of “training a neural network so it learns”? This needs more motivation and clarification. \nAlso, the hypothesis $h$ that is supposed to learn the neural network in Definitions 2.1 and 2.2 seems to belong to any arbitrary class of functions. Is this right? If so, why isn’t this intractable to compute? In my mind, it would make sense for $h$ to belong to the same class of neural networks as defined by $N_\\theta$ --- maybe it is the case in Section 4, but I just don’t know; all I know is that in Section 2 and 3, this is not clear to me.\nCuriously, thinking about Case a) above, the paragraph that starts at line 102 mentions stochastic gradient descent (SGD), which makes me think that previous works have addressed the question of learning in a more practically motivated way, since SGD is used in practice. Can the authors also comment on this? How does it relate to your paper?\n\n2) The paper addresses computational complexity, and from reading the paper it seems that such computation is linked to the algorithm $\\mathcal{L}$. The computation by $\\mathcal{L}$ seems to be related to how many times the algorithm needs to access the oracle in order to compute the final hypothesis $h$. This number of times is, I believe, the sample complexity of the algorithm. So, are we talking about computational complexity or sample complexity in the paper? Is the paper concerned about sample complexity at all? This must be clear on the paper, probably since the beginning of it. As far as I can see, the concept of sample complexity was only referenced in line 251 of Section 4 without much more detail about its relevance. Please, address this, since sample complexity is very important in ML and learning in general.\n\n3) The first part of Section 4 explains how the proof used by the authors is related to [15] and what is the additional challenge that the authors present, i.e., the handling of smoothing. However, besides the first paragraph of Section 4, there is no more indication of whether some of the constructions being used throughout the proof correspond to ones in [15] or not. It would be nice to know which parts of the proof were taken from previous papers that also study learning of neural networks, and which parts weren’t.\n\n4) This comment applies to networks of $k$-depth where $k>2$. When considering the neural network in definition 2.1 and 2.2, as well as in the statement of Theorems 3.1, there is no mention on how the neurons are distributed in the feedforward network. Do all hidden layers have the same width? Are the number of neurons per width irrelevant in terms of learning? Since the paper is concerned with presenting negative results, I guess they consider specific constructions of the networks in order to prove their results. Is that correct? If so, could this be mentioned? In general, could there be some mention about the specific topology of the networks in terms of the widths per layer?\n\n5) Naturally, the paper recognizes that it might be possible to obtain results of efficient learning for different assumptions and topologies, such as not including an activation function at the output. I believe the authors should investigate this case for $3$-depth networks because this will strengthen their paper’s contribution. For example, if efficient learning is demonstrated for $3$-depth networks without activation function at the output, this will be very interesting because it elucidates more the role of the extra activation in efficient learning! I know that theoretical works are hard to do because proofs can be very non-trivial; however, since there is at least one previous work showing the efficiency of learning $2$-depth networks [6], how difficult would it be to adapt their proof to the case of $3$-depth networks?\n\nOther observations:\n\n1) The paper mentions that the neural network architecture they focus on have a ReLU at the single output layer. Previous works seem to focus on linear output, i.e. regression. Is having a ReLU at the output layer closer to real world applications? What is the motivation for it?\n\n2) Definition 2.1 and 2.2 says that $(x,y)$ is drawn iid; however, it seems that only $x$ must be drawn iid, since $y$ is a deterministic function of $x$. Please check.\n\n3) I think a proof outline is needed in Section 4, probably right before subsection 4.1 to better understand how the rest of the proof is built. Though the subsection titles in section 4 indicate what is being done, how they are pieced together in order to better understand the overall proof is not clear to me.\n\nMinor:\n\n1) In the abstract, line 9 mentions the word “hard”. It would be better to instead use expressions in terms of efficiency of the computation, etc.\n\n2) Line 35, it seems that it should say “bounded from below”.\n\n3) In line 86 it says that considering standard Gaussian distributions is “perhaps the most natural choice of an input distribution”, why is that? In real world applications, practitioners don’t care about this type of input. It may be good to insert a better motivation for it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their efforts.\n\nRegarding the weaknesses:\n1. The paper studies PAC learning, as defined in Definitions 2.1, 2.2 and 2.3. Thus, we study whether there exists an efficient algorithm that returns w.h.p. a hypothesis with a small population loss. In this common notion of learning, the learning algorithm can be any efficient algorithm, and it is not restricted to standard algorithms such as SGD. Also, the returned hypothesis is not restricted. Therefore, our hardness results imply that (under Assumption 2.1) there is no efficient algorithm that returns w.h.p. a hypothesis with a small population loss. As a special case, it implies that SGD cannot learn neural networks efficiently (even under the smoothed analysis framework, Gaussian inputs, depth-3, etc.). In other words, the fact that our definitions do not have any restrictions on the algorithm and the returned hypothesis only makes our hardness results stronger. In this sense, our results are stronger than the hardness results that are specific to gradient methods, which are mentioned in the paragraph that starts at line 102.\n2. Our results consider computational complexity. That is, we show (under Assumption 2.1) that there is no poly-time algorithm that learns the considered networks under the smoothed analysis framework. In the proof, we assume that such a poly-time learning algorithm exists, and therefore this algorithm must also have a polynomial sample complexity, and we use it to obtain a poly-time algorithm that breaks the PRG given a polynomial number of examples. Thus, we refer to the sample complexity of the algorithm in the proof for technical reasons, but the theorems proved in the paper consider computational complexity. Our results do not rule out the existence of learning algorithms with a polynomial sample complexity but super-polynomial time.\n3. Indeed, in the first paragraph of Section 4 we compare our proof to [15]. While we build on the technique from [15], none of the parts in the proof is taken directly from [15], except for Lemma A.1 in the appendix.\n4. The construction considers a specific architecture, but by a simple argument (which we use in the proof of Corollary 3.1 in Appendix B) we can see that the hardness results hold even if all layers are of the same width (e.g., when all layers are of width d, where d is the input dimension). We will add a remark about this issue in the camera-ready version.\n5. Indeed, it is not clear whether learning depth-3 networks without activation in the output in the smoothed-analysis framework is hard. Despite efforts by the community, the existing algorithms for learning non-degenerate depth-2 networks were not extended to depth 3, and it is unknown whether such an extension is possible. Intuitively, we feel that obtaining such an extension will be challenging. We agree that it is an important direction for future research.\n\nRegarding the other observations:\n1. In real-world applications, practitioners can choose whether to include activation in the output or not. We note that our hardness results can be easily shown to apply also in the case of depth-4 networks without activation in the output neuron (by adding a linear layer to the depth-3 network from our construction).\n2. Sure, we can just draw $x$ i.i.d. and then $y$ is a deterministic function of $x$.\n3. We will try to clarify this.\n"}]

Author rebuttal:

Meta-review: The paper studies the computational complexity of training neural networks. In particular, the authors show that learning depth-3 NNs (technically their network is depth-4) is hard even under the smoothed analysis setting compared to previous known lower bounds that depended on degenerate cases. They use a cleverer variant of the so-called Daniely-Vardi lift that is resistant to smoothing at the cost of an extra layer (technically two non-linear layers) which allows them to embed depth-$L$ hard boolean functions as depth-$(L+2)$ ReLU networks.

The main concern raised by most reviewers was about the technical significance of extending the known hardness results to the "smoothed analysis" setting. Reviewer fpWr had additional concerns about the motivation of studying computational complexity in the PAC learning setting. Since the work is built on a long line of prior work studying this setting, and the setting is very classically studied in learning theory, I do not think the latter concern is well-founded. Additionally, I think that the "smoothed analysis" setting is technically significant in light of the brittleness of existing lower bounds to even slight perturbations. Therefore, I vote to accept the paper. I encourage the authors to add more discussion about the importance of the setting and comparison to prior work, and also clarify depth-4 vs depth-3 in their notation.
Decision: Accept (poster)