Stationary Points of Shallow Neural Networks with Quadratic Activation
  Function
  We consider the teacher-student setting of learning shallow neural networks
with quadratic activations and planted weight matrix $W^*\in\mathbb{R}^{m\times
d}$, where $m$ is the width of the hidden layer and $d\le m$ is the data
dimension. We study the optimization landscape associated with the empirical
and the population squared risk of the problem. Under the assumption the
planted weights are full-rank we obtain the following results. First, we
establish that the landscape of the empirical risk admits an "energy barrier"
separating rank-deficient $W$ from $W^*$: if $W$ is rank deficient, then its
risk is bounded away from zero by an amount we quantify. We then couple this
result by showing that, assuming number $N$ of samples grows at least like a
polynomial function of $d$, all full-rank approximate stationary points of the
empirical risk are nearly global optimum. These two results allow us to prove
that gradient descent, when initialized below the energy barrier, approximately
minimizes the empirical risk and recovers the planted weights in
polynomial-time. Next, we show that initializing below this barrier is in fact
easily achieved when the weights are randomly generated under relatively weak
assumptions. We show that provided the network is sufficiently
overparametrized, initializing with an appropriate multiple of the identity
suffices to obtain a risk below the energy barrier. At a technical level, the
last result is a consequence of the semicircle law for the Wishart ensemble and
could be of independent interest. Finally, we study the minimizers of the
empirical risk and identify a simple necessary and sufficient geometric
condition on the training data under which any minimizer has necessarily zero
generalization error. We show that as soon as $N\ge N^*=d(d+1)/2$, randomly
generated data enjoys this geometric condition almost surely, while that ceases
to be true if $N<N^*$.
