Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima

We consider the problem of learning a one-hidden-layer neural network with\nnon-overlapping convolutional layer and ReLU activation, i.e., $f(\\mathbf{Z},\n\\mathbf{w}, \\mathbf{a}) = \\sum_j a_j\\sigma(\\mathbf{w}^T\\mathbf{Z}_j)$, in which\nboth the convolutional weights $\\mathbf{w}$ and the output weights $\\mathbf{a}$\nare parameters to be learned. When the labels are the outputs from a teacher\nnetwork of the same architecture with fixed weights $(\\mathbf{w}^*,\n\\mathbf{a}^*)$, we prove that with Gaussian input $\\mathbf{Z}$, there is a\nspurious local minimizer. Surprisingly, in the presence of the spurious local\nminimizer, gradient descent with weight normalization from randomly initialized\nweights can still be proven to recover the true parameters with constant\nprobability, which can be boosted to probability $1$ with multiple restarts. We\nalso show that with constant probability, the same procedure could also\nconverge to the spurious local minimum, showing that the local minimum plays a\nnon-trivial role in the dynamics of gradient descent. Furthermore, a\nquantitative analysis shows that the gradient descent dynamics has two phases:\nit starts off slow, but converges much faster after several iterations.\n