On the Convergence Rate of Training Recurrent Neural Networks

Abstract

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 $\text{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.

V2/V3/V4 polish writing

References in corpus (14)

• Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling
• A Convergence Theory for Deep Learning via Over-Parameterization
• Recent Advances in Recurrent Neural Networks
• Deep Neural Networks as Gaussian Processes
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Qualitatively characterizing neural network optimization problems
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Dynamical Isometry and a Mean Field Theory of RNNs: Gating Enables Signal Propagation in Recurrent Neural Networks
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels

Cited by in corpus (47)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• The Global Landscape of Neural Networks: An Overview
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Machine Learning for Prediction with Missing Dynamics
• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• A Constructive Prediction of the Generalization Error Across Scales
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• A Fine-Grained Spectral Perspective on Neural Networks
• Frequency Bias in Neural Networks for Input of Non-Uniform Density
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Tensor Programs III: Neural Matrix Laws
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks
• Distributionally Robust Deep Learning using Hardness Weighted Sampling
• The Recurrent Neural Tangent Kernel
• On the Curse of Memory in Recurrent Neural Networks: Approximation and Optimization Analysis
• Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization
• Enhancing Adversarial Defense by k-Winners-Take-All
• The Discovery of Dynamics via Linear Multistep Methods and Deep Learning: Error Estimation
• FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Which Minimizer Does My Neural Network Converge To?
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Global Convergence of SGD On Two Layer Neural Nets
• Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
• Making Method of Moments Great Again? -- How can GANs learn distributions
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• Theoretical Exploration of Flexible Transmitter Model
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• On the Provable Generalization of Recurrent Neural Networks
• Quantifying Epistemic Uncertainty in Deep Learning
• RNN-based Online Learning: An Efficient First-Order Optimization Algorithm with a Convergence Guarantee
• A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
• One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks
• Learning in Gated Neural Networks
• RNN Training along Locally Optimal Trajectories via Frank-Wolfe Algorithm