On the Convergence Rate of Training Recurrent Neural Networks

By Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song. 2018

205 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

A Constructive Prediction of the Generalization Error Across Scales (2019, background): “Theoretical error bounds: Much attention has been given to theoretical explanations of the generalization capabilities of deep neural networks (Neyshabur et al., 2017a;b; Allen-Zhu et al., 2018a;b; Arora et al., 2018).”
Wide neural networks of any depth evolve as linear models under gradient descent (2019, background): “[21] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.”
Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “ing" near random initialization, which is related to the study of [34]. Remark. This \lottery ticket winning" process is fundamentally dierent from the neural tangent kernel analysis (e.g. [4, 7, 8, 13, 14, 26{29, 38, 45, 50, 57, 61, 104, 115]). In this phase, although the loss is not suci”
What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, background): “The next proposition at least traces back to [3] and was stated for instance in [4].”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, methodology): “One can also combine this paper with properties of recurrent neural networks (RNNs) [3] to derive PAC-learning results for RNNs [2], or use the existential tools of this paper to derive PAC-learning results for three-layer residual networks (ResNet) [1].”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, neutral): “The dependency on n and the least eigenvalue λ0 is only polynomial, which is the same as previous work on shallow neural networks [Du et al., 2018b, Li and Liang, 2018, Allen-Zhu et al., 2018a].”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…Anthony and Bartlett, 2009), a vast literature have recently studied the connection between the generalization performance of deep neural networks and their architectures (Neyshabur et al., 2015, 2017a,b; Bartlett et al., 2017; Golowich et al., 2017; Arora et al., 2018c; Allen-Zhu et al., 2018a).”
Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks (2019, methodology): “Finally, our proof techniques and intuitions are related to recent literature on global convergence of gradient descent for over-parametrized networks [6, 12, 13, 1, 5, 7, 4, 26, 2].”
Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks (2022, methodology): “3 from Allen-Zhu et al. (2019) assure us that ∥∥∥hW (0) t (z)∥∥∥ = O (t), and finally lemma C.2.a from Allen-Zhu et al. (2019) bounds the deviation from the initialization ∥∥∥hWt (z)− h (0) t (z)∥∥∥ = O (T 6 ∥∥W −W (0)∥∥F ).”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “er network but essentially only the last layer is trained [19, 38], or (3) reducing a multi-layer hierarchical neural network to non-hierarchical models such as kernel methods (a.k.a. neural kernels) [3, 6, 7, 9, 10, 18, 18, 18, 20, 22, 23, 30, 33, 41, 49, 53, 68, 78, 84, 85]. 3For one dimension inp”
Frequency Bias in Neural Networks for Input of Non-Uniform Density (2020, background): “fully connected), residual and convolutional networks (Allen-Zhu et al., 2018; 2019; Arora et al., 2019a; Huang & Yau, 2019; Lee et al., 2019).”
Tensor Programs II: Neural Tangent Kernel for Any Architecture (2020, background): “[5] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.”
Can SGD Learn Recurrent Neural Networks with Provable Generalization? (2019, background): “This is so both in practice (since “memory implies larger spectral radius” [24]) and in theory [2].”
The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies (2019, background): “These papers and others analyze neural networks without an explicit bias term [26, 17, 10, 1].”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “aining to arrive at a good nal solution. On the other hand, unlike in supervised training where the training objective involving a (over-parameterized) deep neural network can be approximately convex [9, 48, 4, 10, 31, 15, 14, 80, 30, 27, 42, 36, 52, 40, 74, 26, 81, 26], to the best of our knowledge”
Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models (2021, methodology): “We build on the great literature of NTK [Li and Liang, 2018, Du et al., 2019, Allen-Zhu et al., 2019b].”
An Improved Analysis of Training Over-parameterized Deep Neural Networks (2019, methodology): “…the assumption that all training data points have unit (cid:96) 2 norm, which is the common assumption made in all these work (Du et al., 2018b; Allen-Zhu et al., 2018b; Du et al., 2018a; Wu et al., 2019; Oymak and Soltanolkotabi, 2019), λ 0 > 0 is equivalent to the fact that all training data…”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “Allen-Zhu et al. (2019a); Bai and Lee (2019) go beyond NTK by studying quadratic approximations of neural networks.”