  How can local-search methods such as stochastic gradient descent (SGD) avoid
bad local minima in training multi-layer neural networks? Why can they fit
random labels even given non-convex and non-smooth architectures? Most existing
theory only covers networks with one hidden layer, so can we go deeper?
  In this paper, we focus on recurrent neural networks (RNNs) which are
multi-layer networks widely used in natural language processing. They are
harder to analyze than feedforward neural networks, because the $\textit{same}$
recurrent unit is repeatedly applied across the entire time horizon of length
$L$, which is analogous to feedforward networks of depth $L$. We show when the
number of neurons is sufficiently large, meaning polynomial in the training
data size and in $L$, then SGD is capable of minimizing the regression loss in
the linear convergence rate. This gives theoretical evidence of how RNNs can
memorize data.
  More importantly, in this paper we build general toolkits to analyze
multi-layer networks with ReLU activations. For instance, we prove why ReLU
activations can prevent exponential gradient explosion or vanishing, and build
a perturbation theory to analyze first-order approximation of multi-layer
networks.
