  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.
