Computational Complexity of Learning Neural Networks: Smoothness and
  Degeneracy
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.
Amit Daniely, Nathan Srebro, Gal Vardi
# Efficiently Learning Neural Networks:

###### 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.

Collaboration on the Theoretical Foundations of Deep Learning (deepfoundations.ai)

## 1 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. Nevertheless, 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., Klivans and Sherstov (2006); Daniely and Shalev-Shwartz (2016)). Thus, without any assumptions on the input distribution or the network's weights, efficient learning algorithms might not be achievable. Even when assuming that the input distribution is Gaussian, strong hardness results were obtained for depth-\(3\) ReLU networks (Daniely and Vardi, 2021; Chen et al., 2022), suggesting that assumptions merely on the input distribution might not suffice. Also, a hardness result by Daniely and Vardi (2020) 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 a hypothesis that does not belong to the considered hypothesis class. Thus, a combination of assumptions on the input distribution and the network's weights seems to be necessary for obtaining efficient algorithms.
Several polynomial-time algorithms for learning depth-\(2\) neural networks have been obtained, under assumptions on the input distribution and the network's weights (Awasthi et al., 2021; Janzamin et al., 2015; Zhong et al., 2017; Ge et al., 2017; Bakshi et al., 2019; Ge et al., 2018). 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. (2021) gave an efficient algorithm for learning depth-\(2\) (one-hidden-layer) 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. if we add a small random noise to any weight matrix, and hence their result implies efficient learning of depth-\(2\) ReLU networks under the Gaussian distribution in the _smoothed-analysis_ framework.

The positive results on depth-\(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-degenerate, or in the smoothed-analysis framework where the network's parameters are smoothed?_

In this work, we give a negative answer to this question, already for depth-\(3\) networks1. 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 is 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.

Footnote 1: We note that in our results the neural networks have the ReLU activation also in the output neuron.

Motivated by the existing positive results on smoothed-analysis in depth-\(2\) networks, we also study whether learning depth-\(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 parameters and the input distribution are smoothed?_

We give a negative answer to this question, by showing hardness of learning depth-\(2\) ReLU networks where a random noise is added to the network's parameters, and the input distribution on \(\mathbb{R}^{d}\) is obtained by smoothing an i.i.d. Bernoulli distribution on \(\{0,1\}^{d}\). 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 (2006) showed, assuming the hardness of the shortest vector problem, that learning intersections of halfspaces is hard. Hardness of learning DNF formulas is implied by Applebaum et al. (2010) 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 Shalev-Shwartz (2016) showed hardness of learning DNFs under a common assumption, namely, that refuting a random \(K\)-SAT 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 (2016) showed, under an assumption on a specific candidate for Goldreich's PRG (i.e., based on a predicate called \(\mathrm{XOR}\text{-}\mathrm{MAJ}\)), that learning depth-\(3\) Boolean circuits under the uniform distribution on the hypercube is hard. Daniely and Vardi (2021) proved distribution-specific hardness of learning Boolean circuits of depth-\(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 a distribution where each component is drawn i.i.d. from a Bernoulli distribution (which is not 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-specific hardness of learning neural networks. Chen et al. (2022) showed hardness of learning depth-\(2\) neural networks under the uniform distribution on the hypercube, based on an assumption on the hardness of the _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 (2021) established hardness of learning depth-\(3\) networks under this distribution, based on the assumpion on the existence of local PRGs. Chen et al. (2022) 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 Diffie-Hellman 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 is whether assumptions on the network weights may suffice. Daniely and Vardi (2020) showed (under the assumption that refuting a random \(K\)-SAT formula is 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 weights do not suffice for efficient learning.

Several works in recent years have shown hardness of distribution-specific learning shallow neural networks using gradient-methods or statistical query (SQ) algorithms (Shamir, 2018; Song et al., 2017; Vempala and Wilmes, 2019; Goel et al., 2020; Diakonikolas et al., 2020; Chen et al., 2022). Specifically, Goel et al. (2020) and Diakonikolas et al. (2020) gave superpolynomial _correlational SQ_ (CSQ) lower bounds for learning depth-\(2\) networks under the Gaussian distribution. Since there is separation between CSQ and SQ, these results do not imply hardness of general SQ learning. Chen et al. (2022) showed general SQ lower bounds for depth-\(3\) networks under the Gaussian distribution. It is worth noting that while the SQ framework captures some variants of the gradient-descent algorithm, it does not capture, for example, stochastic gradient-descent (SGD), which examines training points individually (see a discussion in Goel et al. (2020)).

We emphasize that none of the above distribution-specific hardness results for neural networks (either for improper learning or SQ learning) holds in the smoothed analysis framework or for non-degenerate weights.

While hardness of proper learning is implied by hardness of improper learning, there are also works that show hardness of properly learning depth-\(2\) networks under more standard assumptions (cf. Goel et al. (2020)). Finally, distribution-specific hardness of learning a single ReLU neuron in the agnostic setting
was shown in Goel et al. (2019, 2020b); Diakonikolas et al. (2020a).

Learning neural networks in polynomial time.Awasthi et al. (2021) gave a polynomial-time algorithm 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-analysis framework. Our work implies that such a result might not be possible in depth-\(3\) networks (with activation in the output neuron). Prior to Awasthi et al. (2021), several works gave polynomial time algorithms for learning depth-\(2\) neural networks where the input distribution is Gaussian and the weight matrix is non-degenerate (Janzamin et al., 2015; Zhong et al., 2017; Ge et al., 2017, 2018; Bakshi et al., 2019), 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 networks with multiple outputs, and allow certain non-Gaussian input distributions.

Provable guarantees for learning neural networks in super-polynomial time were given in Diakonikolas et al. (2020b); Chen et al. (2022b); Diakonikolas and Kane (2020). Distribution-free learning of a single ReLU neuron (in the realizable setting) can be done in polynomial time (Kalai and Sastry, 2009; Kakade et al., 2011).

## 2 Preliminaries

### Notation

We use bold-face letters to denote vectors, e.g., \(\mathbf{x}=(x_{1},\ldots,x_{d})\). For a vector \(\mathbf{x}\) and a sequence \(S=(i_{1},\ldots,i_{k})\) of \(k\) indices, we let \(\mathbf{x}_{S}=(x_{i_{1}},\ldots,x_{i_{k}})\), i.e., the restriction of \(\mathbf{x}\) to the indices \(S\). We denote by \(\mathbbm{1}[\cdot]\) the indicator function, for example \(\mathbbm{1}[t\geq 5]\) equals \(1\) if \(t\geq 5\) and \(0\) otherwise. For an integer \(d\geq 1\) we denote \([d]=\{1,\ldots,d\}\). We denote by \(\mathcal{N}(0,\sigma^{2})\) the normal distribution with mean \(0\) and variance \(\sigma^{2}\), and by \(\mathcal{N}(\mathbf{0},\Sigma)\) the multivariate normal distribution with mean \(\mathbf{0}\) and covariance matrix \(\Sigma\). The identity matrix of size \(d\) is denoted by \(I_{d}\). For \(\mathbf{x}\in\mathbb{R}^{d}\) we denote by \(\|\mathbf{x}\|\) the Euclidean norm. We use \(\mathrm{poly}(a_{1},\ldots,a_{n})\) to denote a polynomial in \(a_{1},\ldots,a_{n}\).

### Local pseudorandom generators

An \((n,m,k)\)-hypergraph is a hypergraph over \(n\) vertices \([n]\) with \(m\) hyperedges \(S_{1},\ldots,S_{m}\), each of cardinality \(k\). Each hyperedge \(S=(i_{1},\ldots,i_{k})\) is ordered, and all the \(k\) members of a hyperedge are distinct. We let \(\mathcal{G}_{n,m,k}\) be the distribution over such hypergraphs in which a hypergraph is chosen by picking each hyperedge uniformly and independently at random among all the possible \(n\cdot(n-1)\cdot\ldots\cdot(n-k+1)\) ordered hyperedges. Let \(P:\{0,1\}^{k}\rightarrow\{0,1\}\) be a predicate, and let \(G\) be a \((n,m,k)\)-hypergraph. We call _Goldreich's pseudorandom generator (PRG)_(Goldreich, 2000) the function \(f_{P,G}:\{0,1\}^{n}\rightarrow\{0,1\}^{m}\) such that for \(\mathbf{x}\in\{0,1\}^{n}\), we have \(f_{P,G}(\mathbf{x})=(P(\mathbf{x}_{S_{1}}),\ldots,P(\mathbf{x}_{S_{m}}))\). The integer \(k\) is called the _locality_ of the PRG. If \(k\) is a constant then the PRG and the predicate \(P\) are called _local_. We say that the PRG has _polynomial stretch_ if \(m=n^{s}\) for some constant \(s>1\). We let \(\mathcal{F}_{P,n,m}\) denote the collection of functions \(f_{P,G}\) where \(G\) is an \((n,m,k)\)-hypergraph. We sample a function from \(\mathcal{F}_{P,n,m}\) by choosing a random hypergraph \(G\) from \(\mathcal{G}_{n,m,k}\).

We denote by \(G\stackrel{{ R}}{{\leftarrow}}\mathcal{G}_{n,m,k}\) the operation of sampling a hypergraph \(G\) from \(\mathcal{G}_{n,m,k}\), and by \(\mathbf{x}\stackrel{{ R}}{{\leftarrow}}\{0,1\}^{n}\) the operation of sampling \(\mathbf{x}\) from the uniform distribution on \(\{0,1\}^{n}\). We say that \(\mathcal{F}_{P,n,m}\) is \(\varepsilon\)-pseudorandom
generator (\(\varepsilon\)-PRG) if for every polynomial-time probabilistic algorithm \(\mathcal{A}\) the _distinguishing advantage_

\[\left|\Pr_{G\xleftarrow{R}\mathcal{G}_{n,m,k}\xleftarrow{R}\{0,1\}^{n}}[ \mathcal{A}(G,f_{P,G}(\mathbf{x}))=1]-\Pr_{G\xleftarrow{R}\mathcal{G}_{n,m,k} \mathbf{y}\xleftarrow{R}\{0,1\}^{m}}[\mathcal{A}(G,\mathbf{y})=1]\right|\]

is at most \(\varepsilon\). Thus, the distinguisher \(\mathcal{A}\) is given a random hypergraph \(G\) and a string \(\mathbf{y}\in\{0,1\}^{m}\), and its goal is to distinguish between the case where \(\mathbf{y}\) is chosen at random, and the case where \(\mathbf{y}\) is a random image of \(f_{P,G}\).

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 \(k\) and a predicate \(P:\{0,1\}^{k}\rightarrow\{0,1\}\), such that \(\mathcal{F}_{P,n,n^{s}}\) is \(\frac{1}{3}\)-PRG._

We remark that the same assumption was used by Daniely and Vardi (2021) to show hardness-of-learning results. Note that we assume constant distinguishing advantage. In the literature, a requirement of negligible distinguishing advantage2 is often considered (cf. Applebaum and Lovett (2016), Applebaum (2016), Couteau et al. (2018)). Thus, our requirement from the PRG is weaker.

Footnote 2: More formally, that for \(1-o_{n}(1)\) fraction of the hypergraphs, the distinguisher has no more than negligible advantage.

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 (Ishai et al., 2008, Applebaum et al., 2017), and general-purpose obfuscation based on constant degree multilinear maps (cf. Lin (2016), Lin and Vaikuntanathan (2016)). Significant evidence for Assumption 2.1 was shown in Applebaum (2013) and Applebaum and Lovett (2016). See Daniely and Vardi (2021) for further discussion on the assumption, and on prior works regarding the relation between Goldreich's PRG and hardness of learning.

### Neural networks

We consider feedforward neural networks, computing functions from \(\mathbb{R}^{d}\) to \(\mathbb{R}\). The network is composed of layers of neurons, such that each neuron computes a function of the form \(\mathbf{x}\mapsto\sigma(\mathbf{w}^{\top}\mathbf{x}+b)\), where \(\mathbf{w}\) is a weight vector, \(b\) is a bias term and \(\sigma:\mathbb{R}\mapsto\mathbb{R}\) is a non-linear activation function. The _input to the neuron_ is defined as \(\mathbf{w}^{\top}\mathbf{x}+b\), i.e., the value before applying the activation function. In this work, we focus on the ReLU activation function, namely, \(\sigma(z)=[z]_{+}=\max\{0,z\}\). For a matrix \(W=(\mathbf{w}_{1},\ldots,\mathbf{w}_{m})\), we let \(\sigma(W^{\top}\mathbf{x}+\mathbf{b})\) be a shorthand for \(\big{(}\sigma(\mathbf{w}_{1}^{\top}\mathbf{x}+b_{1}),\ldots,\sigma(\mathbf{w} _{m}^{\top}\mathbf{x}+b_{m})\big{)}\), and define a layer of \(m\) neurons as \(\mathbf{x}\mapsto\sigma(W^{\top}\mathbf{x}+\mathbf{b})\). By denoting the output of the \(i\)-th layer as \(O_{i}\), we can define a network of arbitrary depth recursively by \(O_{i+1}=\sigma(W_{i+1}^{\top}O_{i}+\mathbf{b}_{i+1})\). The _weights vector_ of the \(j\)-th neuron in the \(i\)-th layer is the \(j\)-th column of \(W_{i}\), and its _outgoing-weights vector_ is the \(j\)-th row of \(W_{i+1}\). We define the _depth_ of the network as the number of layers. Unless stated otherwise, the output neuron also has a ReLU activation function. A neuron which is not an input or output neuron is called a _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 \(\boldsymbol{\theta}\in\mathbb{R}^{p}\) obtained by concatenating these matrices and vectors. For \(B\geq 0\), we 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-analysis framework

We first define learning neural networks under the standard PAC framework:

**Definition 2.1** (Distribution-specific PAC learning).: _Learning depth-\(k\) neural networks under an input distribution \(\mathcal{D}\) on \(\mathbb{R}^{d}\) is defined by the following framework:_

1. _An adversary chooses a set of_ \(B\)_-bounded parameters_ \(\boldsymbol{\theta}\in\mathbb{R}^{p}\) _for a depth-_ \(k\) _neural network_ \(N_{\boldsymbol{\theta}}:\mathbb{R}^{d}\rightarrow\mathbb{R}\)_, as well as some_ \(\epsilon>0\)_._
2. _Consider an examples oracle, such that each example_ \((\mathbf{x},y)\in\mathbb{R}^{d}\times\mathbb{R}\) _is drawn i.i.d. with_ \(\mathbf{x}\sim\mathcal{D}\) _and_ \(y=N_{\boldsymbol{\theta}}(\mathbf{x})\)_. Then, given access to the examples oracle, the goal of the learning algorithm_ \(\mathcal{L}\) _is to return with probability at least_ \(\frac{3}{4}\) _a hypothesis_ \(h:\mathbb{R}^{d}\rightarrow\mathbb{R}\) _such that_ \[\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}}\left[\left(h(\mathbf{x })-N_{\boldsymbol{\theta}}(\mathbf{x})\right)^{2}\right]\leq\epsilon\;.\] _We say that_ \(\mathcal{L}\) _is_ efficient _if it runs in time_ \(\operatorname{poly}(d,p,B,1/\epsilon)\)_._

We consider learning in the _smoothed-analysis_ framework (Spielman and Teng, 2004), which is a popular paradigm for analyzing non-worst-case computational complexity (Roughgarden, 2021). The smoothed-analysis framework has been successfully applied to many learning problems (e.g., Awasthi et al. (2021); Ge et al. (2018); Kalai et al. (2009); Bhaskara et al. (2014, 2019); Haghtalab et al. (2020); Ge et al. (2015); Kalai and Teng (2008); Brutzkus et al. (2020)). In the smoothed-analysis 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 a similar model was considered in Awasthi et al. (2021) and Ge et al. (2018)):

**Definition 2.2** (Learning with smoothed parameters).: _Learning depth-\(k\) neural networks with smoothed parameters under an input distribution \(\mathcal{D}\) is defined as follows:_

1. _An adversary chooses a set of_ \(B\)_-bounded parameters_ \(\boldsymbol{\theta}\in\mathbb{R}^{p}\) _for a depth-_ \(k\) _neural network_ \(N_{\boldsymbol{\theta}}:\mathbb{R}^{d}\rightarrow\mathbb{R}\)_, as well as some_ \(\tau,\epsilon>0\)_._
2. _A perturbed set of parameters_ \(\hat{\boldsymbol{\theta}}\) _is obtained by a random perturbation to_ \(\boldsymbol{\theta}\)_, namely,_ \(\hat{\boldsymbol{\theta}}=\boldsymbol{\theta}+\boldsymbol{\xi}\) _for_ \(\boldsymbol{\xi}\sim\mathcal{N}(\mathbf{0},\tau^{2}I_{p})\)_._
3. _Consider an examples oracle, such that each example_ \((\mathbf{x},y)\in\mathbb{R}^{d}\times\mathbb{R}\) _is drawn i.i.d. with_ \(\mathbf{x}\sim\mathcal{D}\) _and_ \(y=N_{\hat{\boldsymbol{\theta}}}(\mathbf{x})\)_. Then, given access to the examples oracle, the goal of the learning algorithm_ \(\mathcal{L}\) _is to return with probability at least_ \(\frac{3}{4}\) _(over the random perturbation_ \(\boldsymbol{\xi}\) _and the internal randomness of_ \(\mathcal{L}\)_) a hypothesis_ \(h:\mathbb{R}^{d}\rightarrow\mathbb{R}\) _such that_ \[\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\mathcal{D}}\left[\left(h(\mathbf{x })-N_{\hat{\boldsymbol{\theta}}}(\mathbf{x})\right)^{2}\right]\leq\epsilon\;.\] _We say that_ \(\mathcal{L}\) _is_ efficient _if it runs in time_ \(\operatorname{poly}(d,p,B,1/\epsilon,1/\tau)\)_._

Finally, we also consider a 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 \(\mathcal{D}\) is defined as follows:_

1. _An adversary chooses a set of_ \(B\)_-bounded parameters_ \(\boldsymbol{\theta}\in\mathbb{R}^{p}\) _for a depth-_\(k\) _neural network_ \(N_{\boldsymbol{\theta}}:\mathbb{R}^{d}\rightarrow\mathbb{R}\)_, as well as some_ \(\tau,\omega,\epsilon>0\)_._
2. _A perturbed set of parameters_ \(\hat{\boldsymbol{\theta}}\) _is obtained by a random perturbation to_ \(\boldsymbol{\theta}\)_, namely,_ \(\hat{\boldsymbol{\theta}}=\boldsymbol{\theta}+\boldsymbol{\xi}\) _for_ \(\boldsymbol{\xi}\sim\mathcal{N}(\mathbf{0},\tau^{2}I_{p})\)_. Moreover, a smoothed input distribution_ \(\hat{\mathcal{D}}\) _is obtained from_ \(\mathcal{D}\)_, such that_ \(\hat{\mathbf{x}}\sim\hat{\mathcal{D}}\) _is chosen by drawing_ \(\mathbf{x}\sim\mathcal{D}\) _and adding a random perturbation from_ \(\mathcal{N}(\mathbf{0},\omega^{2}I_{d})\)_._
3. _Consider an examples oracle, such that each example_ \((\mathbf{x},y)\in\mathbb{R}^{d}\times\mathbb{R}\) _is drawn i.i.d. with_ \(\mathbf{x}\sim\hat{\mathcal{D}}\) _and_ \(y=N_{\hat{\boldsymbol{\theta}}}(\mathbf{x})\)_. Then, given access to the examples oracle, the goal of the learning algorithm_ \(\mathcal{L}\) _is to return with probability at least_ \(\frac{3}{4}\) _(over the random perturbation_ \(\boldsymbol{\xi}\) _and the internal randomness of_ \(\mathcal{L}\)_) a hypothesis_ \(h:\mathbb{R}^{d}\rightarrow\mathbb{R}\) _such that_ \[\operatorname*{\mathbb{E}}_{\mathbf{x}\sim\hat{\mathcal{D}}}\left[\left(h( \mathbf{x})-N_{\hat{\boldsymbol{\theta}}}(\mathbf{x})\right)^{2}\right]\leq \epsilon\;.\] _We say that_ \(\mathcal{L}\) _is_ efficient _if it runs in time_ \(\operatorname{poly}(d,p,B,1/\epsilon,1/\tau,1/\omega)\)_._

We emphasize that all of the above definitions consider learning in the distribution-specific setting. Thus, the learning algorithm may depend on the specific input distribution \(\mathcal{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.1, there is no efficient algorithm that learns depth-\(3\) neural 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 \(\mathbb{R}^{d}\) 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/\operatorname{poly}(d)\). As we discussed in the introduction, in one-hidden-layer networks with similar assumptions there exist efficient learning algorithms.

**Corollary 3.1**.: _Under Assumption 2.1, there is no efficient algorithm that learns depth-\(3\) neural networks (in the sense of Definition 2.1) under the standard Gaussian distribution on \(\mathbb{R}^{d}\), even if the smallest singular value of each weight matrix is at least \(1/\operatorname{poly}(d)\)._

The proof of the above corollary follows from Theorem 3.1, using the fact that by adding a 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 B for the formal proof.

Theorem 3.1 gives a strong limitation on learning depth-\(3\) networks in the smoothed-analysis framework. Motivated by existing positive results on smoothed-analysis in depth-\(2\) networks, we now study whether learning depth-\(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\) networks may not be possible with smoothed parameters where the input distribution on \(\mathbb{R}^{d}\) is obtained by smoothing an i.i.d. Bernoulli distribution on \(\{0,1\}^{d}\).

**Theorem 3.2**.: _Under Assumption 2.1, there is no efficient algorithm that learns depth-\(2\) neural networks with smoothed parameters and inputs (in the sense of Definition 2.3), under the distribution \(\mathcal{D}\) on \(\{0,1\}^{d}\) where each coordinate is drawn i.i.d. from a Bernoulli distribution which takes the value \(0\) with probability \(\frac{1}{\sqrt{d}}\)._

We prove the theorem in Appendix C. The proof follows from similar ideas to the proof of Theorem 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 (2021). 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 to Daniely and Vardi (2021) is that our reduction must handle the random noise which is added to the parameters. Specifically, Daniely and Vardi (2021) 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 \(\mathbf{x}\in\{0,1\}^{n}\) used by the PRG. Since the network depends on this unknown \(\mathbf{x}\), some of the parameters of the network are unknown, and hence it is not 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 depth.

We now provide the formal proof. The proof relies on several lemmas which we prove in Appendix A. For a sufficiently large \(n\), let \(\mathcal{D}\) be the standard Gaussian distribution on \(\mathbb{R}^{n^{2}}\). Assume that there is a \(\operatorname{poly}(n)\)-time algorithm \(\mathcal{L}\) that learns depth-\(3\) neural networks with at most \(n^{2}\) hidden neurons and parameter magnitudes bounded by \(n^{3}\), with smoothed parameters, under the distribution \(\mathcal{D}\), with \(\epsilon=\frac{1}{n}\), and \(\tau=1/\operatorname{poly}(n)\) that we will specify later. Let \(m(n)\leq\operatorname{poly}(n)\) be the sample complexity of \(\mathcal{L}\), namely, \(\mathcal{L}\) uses a sample of size at most \(m(n)\) and returns with probability at least \(\frac{3}{4}\) a hypothesis \(h\) with \(\mathbb{E}_{\mathbf{z}\sim\mathcal{D}}\left[\left(h(\mathbf{z})-N_{\hat{ \boldsymbol{\theta}}}(\mathbf{z})\right)^{2}\right]\leq\epsilon=\frac{1}{n}\), where \(N_{\hat{\boldsymbol{\theta}}}\) is the perturbed network. Let \(s>1\) be a constant such that \(n^{s}\geq m(n)+n^{3}\) for every sufficiently large \(n\). By Assumption 2.1, there exists a constant \(k\) and a predicate \(P:\{0,1\}^{k}\rightarrow\{0,1\}\), such that \(\mathcal{F}_{P,n,n^{s}}\) is \(\frac{1}{3}\)-PRG. We will show an efficient algorithm \(\mathcal{A}\) with distinguishing advantage greater than \(\frac{1}{3}\) and thus reach a contradiction.

Throughout this proof, we will use the following notations. For a hyperedge \(S=(i_{1},\ldots,i_{k})\) we denote by \(\mathbf{z}^{S}\in\{0,1\}^{kn}\) the following encoding of \(S\): the vector \(\mathbf{z}^{S}\) is a concatenation of \(k\) vectors in \(\{0,1\}^{n}\), such that the \(j\)-th vector has \(0\) in the \(i_{j}\)-th coordinate and \(1\) elsewhere. Thus, \(\mathbf{z}^{S}\) consists of \(k\) size-\(n\) slices, each encoding a member of \(S\). For \(\mathbf{z}\in\{0,1\}^{kn}\), \(i\in[k]\) and \(j\in[n]\), we denote \(z_{i,j}=z_{(i-1)n+j}\). That is, \(z_{i,j}\) is the \(j\)-th component in the \(i\)-th slice in \(\mathbf{z}\). For \(\mathbf{x}\in\{0,1\}^{n}\), let \(P_{\mathbf{x}}:\{0,1\}^{kn}\rightarrow\{0,1\}\) be such that for every hyperedge \(S\) we have \(P_{\mathbf{x}}(\mathbf{z}^{S})=P(\mathbf{x}_{S})\). Let \(c\) be such that \(\Pr_{t\sim\mathcal{N}(0,1)}[t\leq c]=\frac{1}{n}\). Let \(\mu\) be the density of \(\mathcal{N}(0,1)\), let \(\mu_{-}(t)=n\cdot\mathds{1}[t\leq c]\cdot\mu(t)\), and let \(\mu_{+}=\frac{n}{n-1}\cdot\mathds{1}[t\geq c]\cdot\mu(t)\). Note that \(\mu_{-},\mu_{+}\) are the densities of the restriction of \(\mu\) to the intervals \(t\leq c\) and \(t\geq c\) respectively. Let \(\Psi:\mathbb{R}^{kn}\rightarrow\{0,1\}^{kn}\) be a mapping such that for every \(\mathbf{z}^{\prime}\in\mathbb{R}^{kn}\) and \(i\in[kn]\) we have \(\Psi(\mathbf{z}^{\prime})_{i}=\mathds{1}[z^{\prime}_{i}\geq c]\). For \(\tilde{\mathbf{z}}\in\mathbb{R}^{n^{2}}\) we denote \(\tilde{\mathbf{z}}_{[kn]}=(\tilde{z}_{1},\ldots,\tilde{z}_{kn})\), namely, the first \(kn\) components of \(\tilde{\mathbf{z}}\) (assuming \(n^{2}\geq kn\)).
### Defining the target network for \(\mathcal{L}\)

Since our goal is to use the algorithm \(\mathcal{L}\) for breaking PRGs, in this subsection we define a neural network \(\tilde{N}:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}\) that we will later use as a target network for \(\mathcal{L}\). The network \(\tilde{N}\) contains the subnetworks \(N_{1},N_{2},N_{3}\) which we define below.

Let \(N_{1}\) be a depth-\(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^{3}\) (all bounds are for a sufficiently large \(n\)), which satisfies the following. We denote the set of output neurons of \(N_{1}\) by \(\mathcal{E}_{1}\). Let \(\mathbf{z}^{\prime}\in\mathbb{R}^{kn}\) be an input to \(N_{1}\) such that \(\Psi(\mathbf{z}^{\prime})=\mathbf{z}^{S}\) for some hyperedge \(S\), and assume that for every \(i\in[kn]\) we have \(z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)\). Fix some \(\mathbf{x}\in\{0,1\}^{n}\). Then, for \(S\) with \(P_{\mathbf{x}}(\mathbf{z}^{S})=0\) the inputs to all output neurons \(\mathcal{E}_{1}\) are at most \(-1\), and for \(S\) with \(P_{\mathbf{x}}(\mathbf{z}^{S})=1\) there exists a neuron in \(\mathcal{E}_{1}\) with input at least \(2\). Recall that our definition of a neuron's input includes the addition of the bias term. The construction of the network \(N_{1}\) is given in Lemma A.3. Intuitively, the network \(N_{1}\) consists of a layer that transforms w.h.p. the input \(\mathbf{z}^{\prime}\) to \(\Psi(\mathbf{z}^{\prime})=\mathbf{z}^{S}\), followed by a layer that satisfies the following: Building on a lemma from Daniely and Vardi (2021) which shows that \(P_{\mathbf{x}}(\mathbf{z}^{S})\) can be computed by a DNF formula, we define a 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 \(-1\), and otherwise it is at least \(2\). Note that the network \(N_{1}\) depends on \(\mathbf{x}\). However, only the second layer depends on \(\mathbf{x}\), and thus given an input we may compute the first layer even without knowing \(\mathbf{x}\). Let \(N_{1}^{\prime}:\mathbb{R}^{kn}\rightarrow\mathbb{R}\) be a depth-\(3\) neural network with no activation function in the output neuron, obtained from \(N_{1}\) by summing the outputs from all neurons \(\mathcal{E}_{1}\).

Let \(N_{2}\) be a depth-\(2\) neural network with input dimension \(kn\), at most \(n\log(n)\) hidden neurons, at most \(2n\) output neurons, and parameter magnitudes bounded by \(n^{3}\) (for a sufficiently large \(n\)), which satisfies the following. We denote the set of output neurons of \(N_{2}\) by \(\mathcal{E}_{2}\). Let \(\mathbf{z}^{\prime}\in\mathbb{R}^{kn}\) be an input to \(N_{2}\) such that for every \(i\in[kn]\) we have \(z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)\). If \(\Psi(\mathbf{z}^{\prime})\) is an encoding of a hyperedge then the inputs to all output neurons \(\mathcal{E}_{2}\) are at most \(-1\), and otherwise there exists a neuron in \(\mathcal{E}_{2}\) with input at least \(2\). The construction of the network \(N_{2}\) is given in Lemma A.5. Intuitively, each neuron in \(\mathcal{E}_{2}\) is responsible for checking whether \(\Psi(\mathbf{z}^{\prime})\) violates some requirement that must hold in an encoding of a hyperedge. Let \(N_{2}^{\prime}:\mathbb{R}^{kn}\rightarrow\mathbb{R}\) be a depth-\(3\) neural network with no activation function in the output neuron, obtained from \(N_{2}\) by summing the outputs from all neurons \(\mathcal{E}_{2}\).

Let \(N_{3}\) be a depth-\(2\) neural network with input dimension \(kn\), at most \(n\log(n)\) hidden neurons, \(kn\leq n\log(n)\) output neurons, and parameter magnitudes bounded by \(n^{3}\) (for a sufficiently large \(n\)), which satisfies the following. We denote the set of output neurons of \(N_{3}\) by \(\mathcal{E}_{3}\). Let \(\mathbf{z}^{\prime}\in\mathbb{R}^{kn}\) be an input to \(N_{3}\). If there exists \(i\in[kn]\) such that \(z^{\prime}_{i}\in\left(c,c+\frac{1}{n^{2}}\right)\) then there exists a neuron in \(\mathcal{E}_{3}\) with input at least \(2\). Moreover, if for all \(i\in[kn]\) we have \(z^{\prime}_{i}\not\in\left(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}}\right)\) then the inputs to all neurons in \(\mathcal{E}_{3}\) are at most \(-1\). The construction of the network \(N_{3}\) is straightforward and given in Lemma A.6. Let \(N_{3}^{\prime}:\mathbb{R}^{kn}\rightarrow\mathbb{R}\) be a depth-\(3\) neural network with no activation function in the output neuron, obtained from \(N_{3}\) by summing the outputs from all neurons \(\mathcal{E}_{3}\).

Let \(N^{\prime}:\mathbb{R}^{kn}\rightarrow\mathbb{R}\) be a depth-\(3\) network obtained from \(N_{1}^{\prime},N_{2}^{\prime},N_{3}^{\prime}\) as follows. For \(\mathbf{z}^{\prime}\in\mathbb{R}^{kn}\) we have \(N^{\prime}(\mathbf{z}^{\prime})=\left[1-N_{1}^{\prime}(\mathbf{z}^{\prime})-N_{2 }^{\prime}(\mathbf{z}^{\prime})-N_{3}^{\prime}(\mathbf{z}^{\prime})\right]_{+}\). The network \(N^{\prime}\) has at most \(n^{2}\) neurons, and parameter magnitudes bounded by \(n^{3}\) (all bounds are for a sufficiently large \(n\)). Finally, let \(\tilde{N}:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}\) be a depth-\(3\) neural network such that \(\tilde{N}(\tilde{\mathbf{z}})=N^{\prime}\left(\tilde{\mathbf{z}}_{[kn]}\right)\).

### Defining the noise magnitude \(\tau\) and analyzing the perturbed network

In order to use the algorithm \(\mathcal{L}\) w.r.t. some neural network with parameters \(\boldsymbol{\theta}\), we need to implement an examples oracle, such that the examples are labeled according to a neural network with parameters
\(\mathbf{\theta}+\mathbf{\xi}\), where \(\mathbf{\xi}\) is a random perturbation. Specifically, we use \(\mathcal{L}\) with an examples oracle where the labels correspond to a network \(\tilde{N}:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}\), obtained from \(\tilde{N}\) (w.r.t. an appropriate \(\mathbf{x}\in\{0,1\}^{n}\) in the construction of \(N_{1}\)) by adding a small perturbation to the parameters. The perturbation is such that we add i.i.d. noise to each parameter in \(\tilde{N}\), where the noise is distributed according to \(\mathcal{N}(0,\tau^{2})\), and \(\tau=1/\operatorname{poly}(n)\) is small enough such that the following holds. Let \(f_{\mathbf{\theta}}:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}\) be any depth-\(3\) neural network parameterized by \(\mathbf{\theta}\in\mathbb{R}^{r}\) for some \(r>0\) with at most \(n^{2}\) neurons, and parameter magnitudes bounded by \(n^{3}\) (note that \(r\) is polynomial in \(n\)). Then with probability at least \(1-\frac{1}{n}\) over \(\mathbf{\xi}\sim\mathcal{N}(0,\tau^{2}I_{r})\), we have \(|\xi_{i}|\leq\frac{1}{10}\) for all \(i\in[r]\), and the network \(f_{\mathbf{\theta}+\mathbf{\xi}}\) is such that for every input \(\tilde{\mathbf{z}}\in\mathbb{R}^{n^{2}}\) with \(\|\tilde{\mathbf{z}}\|\leq 2n\) and every neuron we have: Let \(a,b\) be the inputs to the neuron in the computations \(f_{\mathbf{\theta}}(\tilde{\mathbf{z}})\) and \(f_{\mathbf{\theta}+\mathbf{\xi}}(\tilde{\mathbf{z}})\) (respectively), then \(|a-b|\leq\frac{1}{2}\). Thus, \(\tau\) is sufficiently small, such that w.h.p. adding i.i.d. noise \(\mathcal{N}(0,\tau^{2})\) to each parameter does not change the inputs to the neurons by more than \(\frac{1}{2}\). Note that such an inverse-polynomial \(\tau\) exists, since when the network size, parameter magnitudes, and input size are bounded by some \(\operatorname{poly}(n)\), then the input to each neuron in \(f_{\mathbf{\theta}}(\tilde{\mathbf{z}})\) is \(\operatorname{poly}(n)\)-Lipschitz as a function of \(\mathbf{\theta}\), and thus it suffices to choose \(\tau\) that implies with probability at least \(1-\frac{1}{n}\) that \(\|\mathbf{\xi}\|\leq\frac{1}{q(n)}\) for a sufficiently large polynomial \(q(n)\) (see Lemma A.7 for details).

Let \(\tilde{\mathbf{\theta}}\in\mathbb{R}^{p}\) be the parameters of the network \(\tilde{N}\). Recall that the parameters vector \(\tilde{\mathbf{\theta}}\) is the concatenation of all weight matrices and bias terms. Let \(\hat{\mathbf{\theta}}\in\mathbb{R}^{p}\) be the parameters of \(\hat{N}\), namely, \(\hat{\mathbf{\theta}}=\tilde{\mathbf{\theta}}+\mathbf{\xi}\) where \(\mathbf{\xi}\sim\mathcal{N}(0,\tau^{2}I_{p})\). By our choice of \(\tau\) and the construction of the networks \(N_{1},N_{2},N_{3}\), with probability at least \(1-\frac{1}{n}\) over \(\mathbf{\xi}\), for every \(\tilde{\mathbf{z}}\) with \(\|\tilde{\mathbf{z}}\|\leq 2n\), the inputs to the neurons \(\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3}\) in the computation \(\hat{N}(\tilde{\mathbf{z}})\) satisfy the following properties, where we denote \(\mathbf{z}^{\prime}=\tilde{\mathbf{z}}_{[kn]}\):

1. If \(\Psi(\mathbf{z}^{\prime})=\mathbf{z}^{S}\) for some hyperedge \(S\), and for every \(i\in[kn]\) we have \(z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)\), then the inputs to \(\mathcal{E}_{1}\) satisfy: * If \(P_{\mathbf{x}}(\mathbf{z}^{S})=0\) the inputs to all neurons in \(\mathcal{E}_{1}\) are at most \(-\frac{1}{2}\). * If \(P_{\mathbf{x}}(\mathbf{z}^{S})=1\) there exists a neuron in \(\mathcal{E}_{1}\) with input at least \(\frac{3}{2}\).
2. If for every \(i\in[kn]\) we have \(z^{\prime}_{i}\not\in\left(c,c+\frac{1}{n^{2}}\right)\), then the inputs to \(\mathcal{E}_{2}\) satisfy: * If \(\Psi(\mathbf{z}^{\prime})\) is an encoding of a hyperedge then the inputs to all neurons \(\mathcal{E}_{2}\) are at most \(-\frac{1}{2}\). * Otherwise, there exists a neuron in \(\mathcal{E}_{2}\) with input at least \(\frac{3}{2}\).
3. The inputs to \(\mathcal{E}_{3}\) satisfy: * If there exists \(i\in[kn]\) such that \(z^{\prime}_{i}\in\left(c,c+\frac{1}{n^{2}}\right)\) then there exists a neuron in \(\mathcal{E}_{3}\) with input at least \(\frac{3}{2}\). * If for all \(i\in[kn]\) we have \(z^{\prime}_{i}\not\in\left(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}}\right)\) then the inputs to all neurons in \(\mathcal{E}_{3}\) are at most \(-\frac{1}{2}\).

### Stating the algorithm \(\mathcal{A}\)

Given a sequence \((S_{1},y_{1}),\ldots,(S_{n^{s}},y_{n^{s}})\), where \(S_{1},\ldots,S_{n^{s}}\) are i.i.d. random hyperedges, the algorithm \(\mathcal{A}\) needs to distinguish whether \(\mathbf{y}=(y_{1},\ldots,y_{n^{s}})\) is random or that \(\mathbf{y}=(P(\mathbf{x}_{S_{1}}),\ldots,P(\mathbf{x}_{S_{n^{s}}}))=(P_{ \mathbf{x}}(\mathbf{z}^{S_{1}}),\ldots,P_{\mathbf{x}}(\mathbf{z}^{S_{n^{s}}}))\) for a random \(\mathbf{x}\in\{0,1\}^{n}\). Let \(\mathcal{S}=((\mathbf{z}^{S_{1}},y_{1}),\ldots,(\mathbf{z}^{S_{n^{s}}},y_{n^{s} }))\).

We use the efficient algorithm \(\mathcal{L}\) in order to obtain distinguishing advantage greater than \(\frac{1}{3}\) as follows. Let \(\mathbf{\xi}\) be a random perturbation, and let \(\hat{N}\) be the perturbed network as defined above, w.r.t. the unknown \(\mathbf{x}\in\{0,1\}^{n}\). Note that given a perturbation \(\mathbf{\xi}\), only the weights in the second layer of the subnetwork
\(N_{1}\) in \(\hat{N}\) are unknown, since all other parameters do not depend on \(\mathbf{x}\). The algorithm \(\mathcal{A}\) runs \(\mathcal{L}\) with the following examples oracle. In the \(i\)-th call, the oracle first draws \(\mathbf{z}\in\{0,1\}^{kn}\) such that each component is drawn i.i.d. from a Bernoulli distribution which takes the value \(0\) with probability \(\frac{1}{n}\). If \(\mathbf{z}\) is an encoding of a hyperedge then the oracle replaces \(\mathbf{z}\) with \(\mathbf{z}^{S_{i}}\). Then, the oracle chooses \(\mathbf{z}^{\prime}\in\mathbb{R}^{kn}\) such that for each component \(j\), if \(z_{j}\geq c\) then \(z^{\prime}_{j}\) is drawn from \(\mu_{+}\), and otherwise \(z^{\prime}_{j}\) is drawn from \(\mu_{-}\). Let \(\tilde{\mathbf{z}}\in\mathbb{R}^{n^{2}}\) be such that \(\tilde{\mathbf{z}}_{[kn]}=\mathbf{z}^{\prime}\), and the other \(n^{2}-kn\) components of \(\tilde{\mathbf{z}}\) are drawn i.i.d. from \(\mathcal{N}(0,1)\). Note that the vector \(\tilde{\mathbf{z}}\) has the distribution \(\mathcal{D}\), due to the definitions of the densities \(\mu_{+}\) and \(\mu_{-}\), and since replacing an encoding of a random hyperedge by an encoding of another random hyperedge does not change the distribution of \(\mathbf{z}\). Let \(\hat{b}\in\mathbb{R}\) be the bias term of the output neuron of \(\hat{N}\). The oracle returns \((\tilde{\mathbf{z}},\tilde{y})\), where the labels \(\tilde{y}\) are chosen as follows:

* If \(\Psi(\mathbf{z}^{\prime})\) is not an encoding of a hyperedge, then \(\tilde{y}=0\).
* If \(\Psi(\mathbf{z}^{\prime})\) is an encoding of a hyperedge:
* If \(\mathbf{z}^{\prime}\) does not have components in the interval \((c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})\), then if \(y_{i}=0\) we set \(\tilde{y}=\hat{b}\), and if \(y_{i}=1\) we set \(\tilde{y}=0\).
* If \(\mathbf{z}^{\prime}\) has a component in the interval \((c,c+\frac{1}{n^{2}})\), then \(\tilde{y}=0\).
* If \(\mathbf{z}^{\prime}\) does not have components in the interval \((c,c+\frac{1}{n^{2}})\), but has a component in the interval \((c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})\), then the label \(\tilde{y}\) is determined as follows:
* If \(y_{i}=1\) then \(\tilde{y}=0\).
* If \(y_{i}=0\): Let \(\hat{N}_{3}\) be the network \(\hat{N}\) after omitting the neurons \(\mathcal{E}_{1},\mathcal{E}_{2}\) and their incoming and outgoing weights. Then, we set \(\tilde{y}=[\hat{b}-\hat{N}_{3}(\tilde{\mathbf{z}})]_{+}\). Note that since only the first layer of \(N_{1}\) depends on \(\mathbf{x}\), then we can compute \(\hat{N}_{3}(\tilde{\mathbf{z}})\) without knowing \(\mathbf{x}\).

Let \(h\) be the hypothesis returned by \(\mathcal{L}\). Recall that \(\mathcal{L}\) uses at most \(m(n)\) examples, and hence \(\mathcal{S}\) contains at least \(n^{3}\) examples that \(\mathcal{L}\) cannot view. We denote the indices of these examples by \(I=\{m(n)+1,\ldots,m(n)+n^{3}\}\), and the examples by \(\mathcal{S}_{I}=\{(\mathbf{z}^{S_{i}},y_{i})\}_{i\in I}\). By \(n^{3}\) additional calls to the oracle, the algorithm \(\mathcal{A}\) obtains the examples \(\tilde{\mathcal{S}}_{I}=\{(\tilde{\mathbf{z}}_{i},\tilde{y}_{i})\}_{i\in I}\) that correspond to \(\mathcal{S}_{I}\). Let \(h^{\prime}\) be a hypothesis such that for all \(\tilde{\mathbf{z}}\in\mathbb{R}^{n^{2}}\) we have \(h^{\prime}(\tilde{\mathbf{z}})=\max\{0,\min\{\hat{b},h(\tilde{\mathbf{z}})\}\}\), thus, for \(\hat{b}\geq 0\) the hypothesis \(h^{\prime}\) is obtained from \(h\) by clipping the output to the interval \([0,\hat{b}]\). Let \(\ell_{I}(h^{\prime})=\frac{1}{|I|}\sum_{i\in I}(h^{\prime}(\tilde{\mathbf{z}}_ {i})-\tilde{y}_{i})^{2}\). Now, if \(\ell_{I}(h^{\prime})\leq\frac{2}{n}\), then \(\mathcal{A}\) returns \(1\), and otherwise it returns \(0\). We remark that the decision of our algorithm is based on \(h^{\prime}\) (rather than \(h\)) 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.

### Analyzing the algorithm \(\mathcal{A}\)

Note that the algorithm \(\mathcal{A}\) runs in \(\mathrm{poly}(n)\) time. We now show that if \(\mathcal{S}\) is pseudorandom then \(\mathcal{A}\) returns \(1\) with probability greater than \(\frac{2}{3}\), and if \(\mathcal{S}\) is random then \(\mathcal{A}\) returns \(1\) with probability less than \(\frac{1}{3}\).

We start with the case where \(\mathcal{S}\) is pseudorandom. In Lemma A.8, we prove that if \(\mathcal{S}\) is pseudorandom then w.h.p. (over \(\boldsymbol{\xi}\sim\mathcal{N}(\mathbf{0},\tau^{2}I_{p})\) and the i.i.d. inputs \(\tilde{\mathbf{z}}_{i}\sim\mathcal{D}\)) the examples \((\tilde{\mathbf{z}}_{1},\tilde{y}_{1}),\ldots,(\tilde{\mathbf{z}}_{m(n)+n^{3}},\tilde{y}_{m(n)+n^{3}})\) returned by the oracle are realized by \(\hat{N}\). Thus, \(\tilde{y}_{i}=\hat{N}(\tilde{\mathbf{z}}_{i})\) for all \(i\). As we show in the lemma, this claim follows by noting that the following hold w.h.p., where we denote \(\mathbf{z}^{\prime}_{i}=(\tilde{\mathbf{z}}_{i})_{[kn]}\):

* If \(\Psi(\mathbf{z}^{\prime}_{i})\) is not an encoding of a hyperedge, then the oracle sets \(\tilde{y}_{i}=0\), and we have:
If \(\mathbf{z}_{i}^{\prime}\) does not have components in \(\left(c,c+\frac{1}{n^{2}}\right)\), then there exists a neuron in \(\mathcal{E}_{2}\) with output at least \(\frac{3}{2}\) (by Property (P2)), which implies \(\hat{N}(\tilde{\mathbf{z}}_{i})=0\). * If \(\mathbf{z}^{\prime}\) has a component in \(\left(c,c+\frac{1}{n}\right)\), then there exists a neuron in \(\mathcal{E}_{3}\) with output at least \(\frac{3}{2}\) (by Property (P3)), which implies \(\hat{N}(\tilde{\mathbf{z}}_{i})=0\).
* If \(\Psi(\mathbf{z}_{i}^{\prime})\) is an encoding of a hyperedge \(S\), then by the definition of the examples oracle we have \(S=S_{i}\). Hence:
* If \(\mathbf{z}_{i}^{\prime}\) does not have components in \(\left(c-\frac{1}{n^{2}},c+\frac{2}{n^{2}}\right)\), then:
* If \(y_{i}=0\) then the oracle sets \(\tilde{y}_{i}=\hat{b}\). Since \(\mathcal{S}\) is pseudorandom, we have \(P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=0\). Hence, in the computation \(\hat{N}(\tilde{\mathbf{z}}_{i})\) the inputs to all neurons in \(\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3}\) are at most \(-\frac{1}{2}\) (by Properties (P1), (P2) and (P3)), and thus their outputs are \(0\). Therefore, \(\hat{N}(\tilde{\mathbf{z}}_{i})=\hat{b}\).
* If \(y_{i}=1\) then the oracle sets \(\tilde{y}_{i}=0\). Since \(\mathcal{S}\) is pseudorandom, we have \(P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=1\). Hence, in the computation \(\hat{N}(\tilde{\mathbf{z}}_{i})\) there exists a neuron in \(\mathcal{E}_{1}\) with output at least \(\frac{3}{2}\) (by Property (P1)), which implies \(\hat{N}(\tilde{\mathbf{z}}_{i})=0\).
* If \(\mathbf{z}_{i}^{\prime}\) has a component in \(\left(c,c+\frac{1}{n^{2}}\right)\), then the oracle sets \(\tilde{y}_{i}=0\). Also, in the computation \(\hat{N}(\tilde{\mathbf{z}}_{i})\) there exists a neuron in \(\mathcal{E}_{3}\) with output at least \(\frac{3}{2}\) (by Property (P3)), which implies \(\hat{N}(\tilde{\mathbf{z}}_{i})=0\).
* If \(\mathbf{z}_{i}^{\prime}\) does not have components in the interval \((c,c+\frac{1}{n^{2}})\), but has a component in the interval \((c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})\), then:
* If \(y_{i}=1\) the oracle sets \(\tilde{y}_{i}=0\). Since \(\mathcal{S}\) is pseudorandom, we have \(P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=1\). Hence, in the computation \(\hat{N}(\tilde{\mathbf{z}}_{i})\) there exists a neuron in \(\mathcal{E}_{1}\) with output at least \(\frac{3}{2}\) (by Property (P1)), which implies \(\hat{N}(\tilde{\mathbf{z}}_{i})=0\).
* If \(y_{i}=0\) the oracle sets \(\tilde{y}_{i}=[\hat{b}-\hat{N}_{3}(\tilde{\mathbf{z}}_{i})]_{+}\). Since \(\mathcal{S}\) is pseudorandom, we have \(P_{\mathbf{x}}(\mathbf{z}^{S})=P_{\mathbf{x}}(\mathbf{z}^{S_{i}})=y_{i}=0\). Therefore, in the computation \(\hat{N}(\tilde{\mathbf{z}}_{i})\) all neurons in \(\mathcal{E}_{1},\mathcal{E}_{2}\) have output \(0\) (by Properties (P1) and (P2)), and hence their contribution to the output of \(\hat{N}\) is \(0\). Thus, by the definition of \(\hat{N}_{3}\), we have \(\hat{N}(\tilde{\mathbf{z}}_{i})=[\hat{b}-\hat{N}_{3}(\tilde{\mathbf{z}}_{i})]_{+}\).

Recall that the algorithm \(\mathcal{L}\) is such that with probability at least \(\frac{3}{4}\) (over \(\boldsymbol{\xi}\sim\mathcal{N}(\mathbf{0},\tau^{2}I_{p})\), the i.i.d. inputs \(\tilde{\mathbf{z}}_{i}\sim\mathcal{D}\), and its internal randomness), given a size-\(m(n)\) dataset labeled by \(\hat{N}\), it returns a hypothesis \(h\) such that \(\mathbb{E}_{\tilde{\mathbf{z}}\sim\mathcal{D}}\left[\left(h(\tilde{\mathbf{z}}) -\hat{N}(\tilde{\mathbf{z}})\right)^{2}\right]\leq\frac{1}{n}\). By the definition of \(h^{\prime}\) and the construction of \(\hat{N}\), if \(h\) has small error then \(h^{\prime}\) also has small error, namely, we have \(\mathbb{E}_{\tilde{\mathbf{z}}\sim\mathcal{D}}\left[(h^{\prime}(\tilde{ \mathbf{z}})-\hat{N}(\tilde{\mathbf{z}}))^{2}\right]\leq\frac{1}{n}\). In Lemma A.9 we use the above arguments and Hoeffding's inequality over \(\tilde{\mathcal{S}}_{I}\), and prove that with probability greater than \(\frac{2}{3}\) we have \(\ell_{I}(h^{\prime})\leq\frac{2}{n}\).

Next, we consider the case where \(\mathcal{S}\) is random. Let \(\tilde{\mathcal{Z}}\subseteq\mathbb{R}^{n^{2}}\) be such that \(\tilde{\mathbf{z}}\in\tilde{\mathcal{Z}}\) iff \(\tilde{\mathbf{z}}_{[kn]}\) does not have components in the interval \((c-\frac{1}{n^{2}},c+\frac{2}{n^{2}})\), and \(\Psi(\tilde{\mathbf{z}}_{[kn]})=\mathbf{z}^{S}\) for a hyperedge \(S\). If \(\mathcal{S}\) is random, then by the definition of our examples oracle, for every \(i\in[m(n)+n^{3}]\) such that \(\tilde{\mathbf{z}}_{i}\in\tilde{\mathcal{Z}}\), we have \(\tilde{y}_{i}=\hat{b}\) with probability \(\frac{1}{2}\) and \(\tilde{y}_{i}=0\) otherwise. Also, by the definition of the oracle, \(\tilde{y}_{i}\) is independent of \(S_{i}\) and independent of the choice of the vector \(\tilde{\mathbf{z}}_{i}\) that corresponds to \(\mathbf{z}^{S_{i}}\). Hence, for such \(\tilde{\mathbf{z}}_{i}\in\tilde{\mathcal{Z}}\) with \(i\in I\), any hypothesis cannot predict the label \(\tilde{y}_{i}\), and the expected loss for the example is at least \(\left(\frac{\hat{b}}{2}\right)^{2}\). Moreover, in Lemma A.11 we show that \(\Pr\left[\tilde{\mathbf{z}}_{i}\in\tilde{\mathcal{Z}}\right]\geq\frac{1}{2\log(n)}\) for a sufficiently large \(n\). In Lemma A.12 we use these
arguments to prove a lower bound on \(\mathbb{E}_{\mathcal{S}_{I}}\left[\ell_{I}(h^{\prime})\right]\), and by Hoeffding's inequality over \(\widehat{\mathcal{S}}_{I}\) we conclude that with probability greater than \(\frac{2}{3}\) we have \(\ell_{I}(h^{\prime})>\frac{2}{n}\).

Overall, if \(\mathcal{S}\) is pseudorandom then with probability greater than \(\frac{2}{3}\) the algorithm \(\mathcal{A}\) returns \(1\), and if \(\mathcal{S}\) is random then with probability greater than \(\frac{2}{3}\) the algorithm \(\mathcal{A}\) returns \(0\). Thus, the distinguishing advantage is greater than \(\frac{1}{3}\).

## 5 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 are smoothed. We hope that our hardness results will help focus on assumptions that may allow for efficient learning. Below we discuss several intriguing open problems.

First, we emphasize that our hardness results are for neural networks that include the ReLU activation also in the output neuron. In 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 is still a 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 in 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 depth-\(2\) networks without activation in the output is not settled.

Moreover, our hardness result for depth-\(3\) networks suggests that adding a small (yet polynomial) noise to the parameters is not sufficient to allow efficient learning under the Gaussian distribution. An intriguing direction is to explore the case where the noise is larger. Intuitively, the case of very large noise corresponds to learning a random network, where the weights are drawn i.i.d. from the Gaussian distribution. Hence, it would be interesting to understand whether there is an efficient algorithm for learning random ReLU networks under the Gaussian input distribution. Likewise, the effect of large noise may also be considered w.r.t. the inputs, namely, we may use large noise for obtaining smoothed input distributions.

### Acknowledgements

This work was done as part of the NSF-Simons Sponsored Collaboration on the Theoretical Foundations of Deep Learning.
