On the Convergence Rate of Training Recurrent Neural Networks

Zeyuan Allen-Zhu; Yuanzhi Li; Zhao Song

Source-linked AI summary

On the Convergence Rate of Training Recurrent Neural Networks

Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song

arXiv:1810.12065v4Oct 29, 2018cs.LGcs.DScs.NEmath.OCstat.ML

TL;DR

The paper addresses the limited theory for SGD training of deep, nonlinear networks, especially RNNs whose repeated recurrent unit can cause exploding or vanishing gradients. It develops convergence and stability analyses for overparameterized ReLU RNNs, showing polynomial-width training convergence and providing evidence that GD/SGD can avoid bad local minima.

Problem
The paper asks how SGD avoids bad local minima in deep, non-convex, non-smooth networks, where existing theory mostly covers shallow networks.
Method
The paper analyzes overparameterized ReLU RNNs using perturbation, stability, and Polyak-Lojasiewicz tools around random initialization.
Results
Overparameterized GD/SGD can converge to global or near-zero training error for multi-layer ReLU networks, with polynomial dependence on sequence length and no exponential gradient explosion or vanishing.
Takeaways & Limitations
The results provide theoretical evidence that SGD can avoid bad local minima in multi-layer networks and that ReLU-based analyses can support RNN memorization.
Takeaways & Limitations
The proofs do not tighten the polynomial dependencies on n, d, and L, and do not analyze correlated randomness generated along the SGD trajectory.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies why SGD can train deep, non-convex, non-smooth networks, focusing on recurrent networks where repeated application of one unit creates additional gradient difficulties. It argues that sufficiently overparameterized ReLU RNNs can reach global or near-zero training error while providing tools for stability and gradient control.

SGD can find global optima on training data in practice despite neural-network objectives being generally non-convex and non-smooth, but the mechanism remains theoretically open.
Existing theory largely studies two-layer networks, Gaussian-like inputs, linear activations, or convex last-layer training, leaving deeper nonlinear networks less understood.
Our Contribution: The work presents convergence evidence for nonlinear networks deeper than two layers, argues that overparameterized GD/SGD avoids bad local minima along training, and develops ReLU stability tools.
Recurrent Neural Networks: RNNs repeatedly apply the same recurrent unit across a sequence, supporting long-term nonlinear interactions but making efficient learning theoretically difficult.
Recurrent Neural Networks: RNN training can suffer gradients that become exponentially small or large in the time horizon, while ReLU activations are proposed as a way to avoid these effects.
Our Result: The paper analyzes Elman RNNs with ReLU activations under δ-separable training sequences and least-squares regression, with feedforward networks treated as special cases.
Our Result: When m ≥ poly(n, d, L, δ^-1, log ε^-1), the theorem guarantees an RNN with ε training error, while the analysis also extends to deep RNNs and other Lipschitz-smooth losses.

2 Notations and Preliminaries

This section establishes the notation, data assumptions, RNN evaluation, random initialization, and the optimization setup used throughout the analysis.

Notation: The paper distinguishes vector, matrix, infinite, sparsity, and Frobenius norms, and defines ReLU coordinatewise as φ(x)=max{x, 0}.It also uses Gaussian-distribution, indicator-function, standard-basis, and Gram–Schmidt orthonormalization notation.
Data assumptions: Each training example is an input sequence of length L with bounded inputs, and distinct first-layer inputs are separated by at least δ.The assumptions require ∥x_i,ℓ∥≤1 and ∥x_i,1−x_j,1∥≥δ for every distinct pair.
RNN evaluation: The RNN is evaluated using weight matrices W, A, and B, with hidden states and outputs indexed by layer or time position.The hidden-state recursion can be written as h_i,ℓ=D_i,ℓW h_i,ℓ−1, where D_i,ℓ is the diagonal activation matrix.
Initialization: Random initialization uses independent Gaussian entries for W, A, and B under the distributions specified in Definition 2.3.The paper also states normalization and bias-related assumptions for the first input layer.
Notation convention: The paper treats the Elman network's recurrent index ℓ as its layer index, while noting that some literature counts it as a three-layer RNN.This convention determines how hidden neurons, inputs, and outputs are labeled throughout the paper.
Objective and gradient: For simplicity, optimization trains only the recurrent weight matrix W while A and B remain at random initialization, using an ℓ2 regression objective.The resulting objective is a function of W, and its (sub-)gradient is derived using the chain rule, including row-wise and full-gradient forms.

3 Our Results

The paper proves that sufficiently overparameterized ReLU RNNs can be trained by GD and SGD toward global minima with essentially linear convergence and polynomial dependence on sequence depth. Its technical framework combines gradient lower bounds, objective semi-smoothness, and perturbation tools to explain why optimization avoids bad local minima and why ReLU prevents exponential gradient instability.

Main results: Both GD and SGD achieve essentially linear convergence, with polynomial rather than exponential dependence on the number of layers L.The result applies even when the RNN processes long input sequences.
Technical theorems: A gradient lower-bound theorem shows that the gradient remains large while the objective value is high, paralleling a Polyak–Łojasiewicz-type condition.This prevents optimization from becoming stationary far from a minimum.
Technical theorems: An objective semi-smoothness theorem shows that sufficiently small moves in the negative-gradient direction decrease the objective.Together with the gradient lower bound, this explains why GD and SGD avoid saddle points and bad local minima along their trajectories.
Open questions: The proof leaves polynomial dependencies on n, d, and L untightened, and does not analyze randomness correlated with the SGD trajectory.The authors suggest such correlated randomness may explain why practical networks need smaller widths than the theorem requires.
Technical tools: The analysis develops first-order and perturbation tools for multi-layer ReLU networks, including stability against adversarial weight perturbations and mechanisms preventing exponential gradient explosion or vanishing.The tools address the dependence of randomness across layers and support the semi-smoothness analysis.

4 Basic Properties at Random Initialization

At random initialization, the analysis uses overparameterization and fresh randomness decompositions to control RNN propagation across recurrent layers. These properties preserve hidden-state norms, data separability, and intermediate-layer bounds without exponential growth in the horizon.

Forward propagation: ReLU and unit-norm incoming signals yield hidden-state norms bounded by O(L), rather than exponential growth or decay.ReLU shuts down roughly half the coordinates, while each layer contributes an additional unit-norm signal.
Forward propagation: Overparameterization makes the rectangular matrix WU_{ℓ−1} spectrally controllable even when hidden states correlate with it.The key condition is m ≫ n^(ℓ−1), which prevents the recurrent reuse of W from causing uncontrolled forward propagation.
Data separability: Data separability degrades by at most a polynomial factor after information propagates through L layers.This follows from the layerwise separability and fresh-randomness properties established in the section.
Intermediate layers and backward propagation: For sparse diagonal ReLU masks, products of recurrent weight matrices satisfy an O(L^3) spectral bound, supporting intermediate-layer and backward-propagation control.A direct spectral argument would grow exponentially because the spectral norm of W is 2; the proof instead uses fixed-vector bounds, ε-net arguments, and sparsity decomposition.
Assumptions and limitations: The stated analysis assumes non-degenerate data, because identical propagated inputs with differing targets prevent the training objective from reaching zero.The authors note that more relaxed assumptions are possible but omit them because they complicate the statements.

5 Stability After Adversarial Perturbation

The perturbation analysis studies RNN behavior after adversarial changes to the recurrent weights. It replaces naive induction with recursive expansion and sparsity-based decomposition to absorb layerwise growth into polynomial-width margins.

Perturbation model: Adversarial perturbations are modeled by writing W = W̃ + W′, where W′ may depend on the random initialization.The same framework later represents optimization updates and a randomness-decomposition construction.
Forward stability: Naive induction fails because the relevant perturbed transition can have spectral norm greater than 1, causing exponential blow-up in L.The adversarially chosen changes prevent directly applying the random-initialization techniques from Section 4.
Forward stability: Recursive expansion produces L terms of each propagation type, allowing the proof to avoid relying on a one-step contraction.The difficult terms are controlled through a two-step decomposition for sparse, small-norm inputs.
Forward stability: A sparse input can be decomposed into y = y1 + y2 with ∥y1∥2 ≤ O(m^-2/3) and ∥y2∥∞ ≤ O(m^-1).This decomposition supplies the margin needed for induction.
Forward stability: Polynomially large width absorbs the blow-up factors between m^-1/2 and m^-2/3, enabling induction without exponential growth.The gap between these scales is the central mechanism used to prove forward stability.
Intermediate and backward stability: Forward stability enables corresponding stability bounds for intermediate layers and backward propagation after perturbation.The derivation uses the sparsity condition from the forward-stability result together with the Section 4 bounds.

6 Proof Sketch of Theorem 3: Polyak- Lojasiewicz Condition

The proof establishes the Polyak–Łojasiewicz lower bound through a fake-gradient argument, then converts it into a true-gradient bound using stability and probabilistic covering techniques.

Fake-gradient construction: The fake gradient is introduced to prove the technically difficult lower bound underlying the Polyak–Łojasiewicz condition.The proof first analyzes fixed loss vectors before recovering the true gradient statement.
From fake to true gradients: Stability lemmas preserve a large fake gradient after adversarial perturbations, while an ε-net and union bound extend fixed-loss control to all losses.Together these steps convert the fake-gradient lower bound into a lower bound on the true gradient.
Theorem completion: The resulting theorem proves the desired gradient lower bound at random initialization rather than only at a perturbed point or on a small coordinate subset.These are the two gaps between the intermediate perturbation result and Theorem 5.
Randomness decomposition: Randomness decomposition separates a small perturbation from the original random initialization, allowing perturbation-based gradient bounds to transfer back to initialization.The decomposition uses correlated Gaussian components while preserving the required marginal distribution.
McDiarmid concentration: Extended McDiarmid concentration handles correlations among neuron coordinates that prevent direct Chernoff or union-bound arguments.The proof applies the inequality over sufficiently large coordinate subsets and then samples enough subsets to cover all coordinates.

7 Proof Sketch of Theorem 4: Objective Semi-Smoothness

The proof establishes objective semi-smoothness by controlling how recurrent hidden states change under adversarial weight perturbations. Its central estimate makes the change proportional to the perturbation norm.

Proof strategy: Theorem 4 relies on basic random-initialization and perturbation-stability properties rather than randomness decomposition or McDiarmid’s inequality.The proof is described as simpler than the Polyak–Łojasiewicz lower-bound proof.
Perturbation setup: The analysis distinguishes quantities at random initialization, at an intermediate adversarial matrix, and after an additional perturbation.These three versions are denoted with separate tilde and un-tilde variables.
Core estimate: The key formula expresses hidden-state differences through diagonal activation matrices and perturbation terms.This algebraic representation enables the subsequent norm bound.
Core estimate: O(L^9)∥W′∥^2 bounds the hidden-state change after perturbation, making the difference proportional to the perturbation norm.This improves on the weaker O(m^-1/2) initialization bound for comparison with the unperturbed state.
Theorem completion: The resulting semi-smoothness theorem supplies the objective decrease control used in the paper’s convergence analysis.The supplied proof sketch states that the final theorem follows by plugging the intermediate estimate into the target inequalities.

B.1 Forward Propagation

The forward-propagation analysis shows that recurrent ReLU states remain controlled across the time horizon with high probability, avoiding exponential vanishing or explosion under sufficiently large width.

Forward-propagation bounds: The section’s goal is to establish upper and lower bounds for forward propagation at random initialization.These bounds are proved recursively across layers.
Forward-propagation bounds: With probability at least 1 − exp(−Ω(m/L^2)), Lemma B.3 provides simultaneous forward-propagation control across the network.The statement is obtained by combining per-layer bounds and a union bound.
Forward-propagation bounds: (1 − 1/(4L))^ℓ ≤ ∥h_i,ℓ+1∥_2 ≤ 2^ℓ + 4 holds for every sample and layer.The lower and upper bounds prevent the forward state from becoming exponentially small or uncontrolled over depth L.
Proof mechanism: The proof applies Gaussian concentration and ε-net arguments first to fixed vectors, then extends the bounds to random recurrent states.The recurrent dependencies are handled by conditioning and uniformization over admissible vector choices.
Supporting properties: Additional lemmas control fresh randomness and state separation across layers, supporting later gradient and perturbation analyses.These properties include lower bounds on projected hidden states and preservation of separability.

C.4 Special Rank-One Perturbation

The special rank-one perturbation analysis studies how a sparse, small perturbation changes recurrent forward and backward quantities while exploiting random initialization to control those changes.

Perturbation setup: The section analyzes a rank-one perturbation W′ = yz⊤ whose direction is tied to a single coordinate and vector.The perturbation is used as a structured probe of the recurrent dynamics.
Perturbation bounds: The perturbation lemmas separately control forward propagation and backward propagation under sparsity, norm, and initialization assumptions.The backward result requires the perturbation not to depend on the random output matrix B.
Forward analysis: The forward analysis bounds changes by decomposing recurrent terms and applying stability estimates to each contribution.The resulting expressions include products of activation derivatives and perturbation-dependent differences.
Quantitative control: O(L^3) bounds the norm of a recurrent product of activation-derivative matrices, while related expressions yield O(L^7) scalar bounds.These polynomial-in-L bounds are used to control perturbation effects across time.
Coordinate selection: The indicator-coordinate lemmas identify many coordinates whose activation behavior differs for the largest-loss sample-layer pair and the remaining cases.This coordinate structure supports the later fake-gradient lower-bound argument.

D.2 Backward Coordinate Bound

This section proves a backward coordinate bound by isolating randomness in subsets of B and controlling the resulting Gaussian coordinates and concentration behavior.

Lemma D.7 studies backward coordinates under random W, A, and B, with a subset N4 that may depend on W and A but not B.The set size is constrained by parameters involving ρ, β−, and L.
Conditioning on events E1 and E2 fixes W and A while retaining B as the only source of randomness.E1 depends on W and A, whereas E2 depends on B.
The proof fixes b−N, varies bN, and analyzes each coordinate through a scalar quantity vk.The resulting vk is Gaussian, with variance bounded below by 1.
McDiarmid’s inequality converts bounded coordinate sensitivity into concentration for the aggregate function g.The argument combines the expected lower bound from Step 1 with concentration over bN.

E Gradient Bound at Random Initialization (Theorem 5)

Theorem 5 establishes a high-probability lower bound on a fake gradient for fixed loss vectors by decomposing initialization randomness and controlling gradient coordinates.

The analysis replaces correlated true loss randomness with fixed loss vectors and studies the corresponding fake gradient.This isolates gradient behavior from the correlation between forward and backward propagation.
Theorem 5 holds with probability at least 1 −e−Ω(ρ2) over W, A, and B for the stated fixed loss vectors.Here ρ = nLd log m.
The proof decomposes randomness, lower-bounds the expected fake gradient, establishes perturbation stability, and applies an extended McDiarmid inequality.These steps are organized across Sections E.1–E.4.
The randomness decomposition writes W as W2 + W′ while preserving i.i.d. Gaussian entries for W2 and controlling its correlation with W′.The construction is parameterized by a selected pair (i∗, ℓ∗) and θ.
The argument uses Gaussian couplings and tail bounds to control auxiliary vectors and support the gradient lower-bound analysis.The coupled vectors are sampled from N(0, 2I_m), with high-probability infinity-norm bounds.

E.2.1 Proof of Lemma E.6

The proof of Lemma E.6 combines coordinate-level backward bounds with a decomposition of W and sign-stability analysis to establish a high-probability lower-bound statement.

The proof fixes W1, A, and B, decomposes W into W1 + W′N, and analyzes the resulting fake-gradient expression coordinatewise.The selected coordinates and loss index are inherited from the maximum-loss construction.
Lemma E.6 holds with probability at least 1 −e−Ω(ρ2) over W1, A, and B under its stated subset-size and decomposition conditions.The proof obtains nested subsets through Lemma D.2 and Lemma D.7, then uses repeated sampling and union bounds.
For the distinguished pair (i∗, ℓ∗), the sign of gi∗,ℓ∗+1 can change with constant probability under W′N randomness.This is the exceptional case in the three-case sign analysis.
For all other index-layer pairs, the proof shows the relevant sign remains fixed or independent of W′N.The cases cover indices after, at, and before the distinguished layer.
Lemma E.7 reformulates the result for t independent random subsets N1, …, Nt and preserves a probability guarantee over the joint randomness.The reformulation is identified as Core Lemma A.

F Gradient Bound After Perturbation (Theorem 3)

This section extends gradient bounds from random initialization to nearby perturbations by comparing the perturbed fake gradient with its initialization value.

Lemma F.1 bounds the fake-gradient behavior uniformly for perturbations W′ whose spectral norm is within the stated radius.The result is first proved for fixed loss vectors.
The proof combines the initialization lower bound with an upper bound on the gradient difference caused by W′.The target difference is ∥b∇f(f W + W′) −b∇f(f W)∥F.
The perturbation analysis expands the gradient difference into multiple terms and controls higher-order contributions.The proof explicitly hides four additional higher-order terms in o(m1/3).
An ε-net argument upgrades the fixed-loss statement to the true losses lossi,ℓ = Bhi,ℓ −y∗ for all loss vectors.This step enables application to the actual network losses.
Theorem 3 holds with probability at least 1 −e−Ω(ρ2) for all sufficiently small spectral-norm perturbations W′ under the stated conditions.The theorem is the perturbed-gradient result obtained from Lemma F.1.

G Objective Semi-Smoothness (Theorem 4)

Theorem 4 establishes objective semi-smoothness near random initialization for the ReLU RNN, using recursive perturbation bounds across recurrent layers.

Objective Semi-Smoothness: Theorem 4 gives a first-order upper bound on the perturbed objective with a higher-order remainder term near initialization.The bound applies to perturbations around weights within radius τ0 and holds with high probability over random initialization.
Recursive Perturbation Analysis: The analysis recursively compares hidden states and pre-activations under perturbed recurrent weights across time steps.The recursive construction tracks h_i,ℓ, its perturbation, and the corresponding ReLU activation patterns.
Proof Assembly: The proof combines recursive hidden-state bounds, activation-pattern control, and norm estimates to obtain the desired semi-smoothness inequality.The final result follows after substituting the intermediate bounds and applying the triangle inequality.
ReLU Perturbations: A diagonal-matrix representation captures ReLU differences coordinate by coordinate, including cases where the two inputs have opposite signs.This representation isolates activation-pattern changes in the perturbation recursion.

H Convergence Rate of Gradient Descent (Theorem 1)

Theorem 1 analyzes gradient descent on the recurrent network under random initialization and sufficient width. It concludes that the training loss reaches ε at a linear convergence speed, while the stated width dependence is not fully tightened.

Theorem 1: Theorem 1 provides conditions under which gradient descent converges from random initialization with high probability.The theorem specifies a width requirement, learning-rate setting, and iteration horizon through parameters involving n, d, L, δ, and ε.
Convergence Result: The training loss of the recurrent neural network drops to ε in a linear convergence speed.The proof controls gradient magnitudes and keeps the iterates within the neighborhood required by the semi-smoothness result.
Scope of Bound: The analysis does not tighten the polynomial dependence on the number of data points, input dimension, and sequence length.The authors state that only the dependencies on δ and ε were tightened in the presented result.

I Convergence Rate of Stochastic Gradient Descent (Theorem 2)

Theorem 2 extends the convergence analysis to stochastic gradient descent under random initialization and sampled gradients. With high probability, SGD achieves the stated convergence behavior while maintaining the required local-neighborhood control.

Theorem 2: Theorem 2 states conditions for stochastic gradient descent to converge from random initialization with high probability.The result uses a width requirement and parameter choices depending on n, d, L, δ, and ε.
Probability Guarantee: The SGD result holds with high probability over the randomness of the sampled stochastic gradients.The theorem separates initialization randomness from the randomness of the samples S1 through ST.
Proof Strategy: The proof uses unbiased stochastic gradients, objective semi-smoothness, gradient bounds, and concentration inequalities to control optimization progress.The argument invokes E_t[∇_t] = ∇f(W^(t)), Jensen’s inequality, and one-sided Azuma concentration.
Neighborhood Control: The analysis verifies that SGD remains in the neighborhood where the auxiliary bounds and semi-smoothness theorem apply.The proof first assumes the neighborhood condition and then verifies it throughout SGD with high probability.