  One of the mysteries in the success of neural networks is randomly
initialized first order methods like gradient descent can achieve zero training
loss even though the objective function is non-convex and non-smooth. This
paper demystifies this surprising phenomenon for two-layer fully connected ReLU
activated neural networks. For an $m$ hidden node shallow neural network with
ReLU activation and $n$ training data, we show as long as $m$ is large enough
and no two inputs are parallel, randomly initialized gradient descent converges
to a globally optimal solution at a linear convergence rate for the quadratic
loss function.
  Our analysis relies on the following observation: over-parameterization and
random initialization jointly restrict every weight vector to be close to its
initialization for all iterations, which allows us to exploit a strong
convexity-like property to show that gradient descent converges at a global
linear rate to the global optimum. We believe these insights are also useful in
analyzing deep models and other first order methods.
