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 open question of how SGD avoids bad local minima in non-convex, non-smooth multi-layer networks, focusing on recurrent neural networks. It proves that overparameterized GD/SGD can reach global minima in polynomial time and develops tools for analyzing ReLU networks.

Problem
Existing theory had not explained how SGD avoids bad local minima or gradient explosion and vanishing when training multi-layer RNNs.
Source: §1 · p. 2
Method
The paper analyzes overparameterized ReLU RNNs using random-initialization bounds, perturbation stability, and a Polyak–Łojasiewicz fake-gradient argument.
Source: §3.1 · p. 8, §4 · p. 9, §6 · p. 11
Results
Overparameterized GD/SGD reaches global minima on non-degenerate data in time polynomial in network depth and sample count.
Source: §1 · p. 2
Takeaways & Limitations
The results provide theoretical evidence that RNNs can memorize mappings while ReLU networks avoid exponential gradient explosion, vanishing, and perturbation instability.
Source: §3.1 · p. 8
The proofs do not tighten polynomial dependencies and do not analyze randomness correlated with the SGD trajectory.
Source: §3 · p. 7

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 introduction frames SGD training of non-convex, non-smooth multi-layer networks—especially recurrent networks—as theoretically unresolved despite practical success. It presents polynomial-width convergence results for ReLU RNNs and technical tools addressing gradient stability and deeper architectures.

1 Introduction

SGD often finds training-data global optima despite non-convex, non-smooth objectives, but how it avoids bad local minima remains theoretically open [21] [69].Source: §1 · p. 2

1.2 Other Related Works

Prior theory largely studied two-layer networks, linear activations, last-layer training, or infinite-width initialization, whereas finite-width training convergence remained unaddressed.Source: §1 · p. 2, §1.2 · p. 4

1 Introduction

RNNs repeatedly apply one unit across sequences, creating vanishing or exploding gradients over the time horizon; ReLU activations can help avoid this instability [52].Source: §1 · pp. 2–3

1.1 Our Question

The paper asks whether ReLU can stabilize training and whether RNNs can efficiently reach near-zero training error under mild assumptions.Source: §1.1 · p. 3
With m ≥ poly(n, d, L, δ^-1, log ε^-1) neurons, the ReLU RNN can achieve ε training error from random Gaussian initialization.Source: §1.1 · p. 4
The work claims the first convergence proof for GD/SGD training hidden layers in recurrent, and more generally multi-layer, networks with activation functions.Source: §1.1 · p. 4
The results extend to deep RNNs and other Lipschitz-smooth, possibly nonconvex losses, while introducing ReLU analysis tools used for further RNN generalization guarantees [1] [2] [3] [10].Source: §1.1 · p. 4

2 Notations and Preliminaries

This section fixes notation for norms, distributions, ReLU, and Gram–Schmidt orthonormalization, then defines the Elman RNN, its data assumptions, initialization, regression objective, and gradient formulas.

2 Notations and Preliminaries

The paper defines vector and matrix norms, Gaussian and indicator notation, coordinatewise ReLU, standard basis vectors, and Gram–Schmidt orthonormalization.It includes Euclidean, spectral, infinity, sparsity, Frobenius, and row ℓp norms, with a zero-vector convention in Gram–Schmidt.Source: §2 · p. 5

2.1 Elman Recurrent Neural Network

The Elman RNN processes length-L input sequences under bounded-input and δ-separated first-input assumptions, using recurrent activation-diagonal matrices, random Gaussian initialization, and layer-indexed notation.The model uses weight matrices W, A, and B; hidden states satisfy h_i,ℓ = D_i,ℓ W h_i,ℓ−1, while A and B are initialized randomly under the stated distributions.Source: §2.1 · p. 5

2.2 Objective and Gradient

Training optimizes only the recurrent matrix W while keeping A and B at random initialization, with the regression objective and its coordinatewise and full gradients derived by the chain rule.The gradient expressions account for indices across the sequence horizon and are stated for each row W_k and for the full matrix.Source: §2.2 · p. 6

3 Our Results

The paper proves that sufficiently wide RNNs can be trained by GD and SGD at essentially linear convergence, while avoiding exponential gradient explosion or vanishing. It develops technical tools explaining this behavior and extends convergence theory to nonlinear networks deeper than two layers.

3 Our Results

Sufficient overparameterization yields essentially linear convergence for both GD and SGD, with polynomial dependence on sequence length L and no exponential gradient explosion or vanishing.The guarantees hold with high probability from random initialization when the width is polynomial in the training parameters and L.Source: §3 · pp. 6–7
Theorem 3 provides a Polyak–Łojasiewicz-like gradient lower bound, while Theorem 4 establishes objective semi-smoothness near random initialization.Together, these first-order properties show that gradient steps reduce the objective whenever it is high.Source: §3 · p. 7
These technical theorems ensure GD and SGD avoid saddle points and bad local minima throughout their training trajectories.The argument combines large gradients at high objective values with sufficient decrease along negative-gradient directions.Source: §3 · p. 7
The proofs leave the polynomial dependencies on n, d, and L untightened, partly because initialization randomness may correlate with the SGD trajectory.The authors suggest that analyzing this correlated randomness could explain why practical width requirements are smaller.Source: §3 · p. 7

3.1 Conclusion

The work gives the first convergence proof for overparameterized nonlinear neural networks deeper than two layers and shows RNNs can map different input tokens to different outputs using one recurrent unit.The RNN formulation also provides an independent memorization result.Source: §3.1 · pp. 7–8
The paper develops general ReLU-network tools explaining resistance to exponential exploding or vanishing and stability under adversarial weight perturbations.The perturbation theory supports the semi-smoothness theorem and has been used by follow-up works [1] [2] [3] [10].Source: §3.1 · p. 8

Proof Sketch

The proof sketch focuses on preventing exponential dependence on L and handling randomness dependence across layers.These issues motivate the detailed discussions in Sections 4–7.Source: Proof Sketch · p. 8

4 Basic Properties at Random Initialization

At random initialization, the RNN’s forward propagation remains controlled across depth, while fresh randomness preserves data separability. Overparameterization and related random-matrix arguments also yield polynomial bounds for intermediate and backward propagation.

Forward propagation

Forward propagation neither explodes nor vanishes, with hidden-state norms bounded by O(L) across layers.ReLU suppresses roughly half the coordinates, while recurrent weight reuse requires controlling correlated directions rather than assuming fresh randomness.Source: §4 · pp. 8–9
Overparameterization controls reused-weight directions through spectral bounds, preventing the exponential depth blowup that square-matrix bounds would cause.The rectangular matrix WU_{ℓ−1}, enabled by m ≫ n(ℓ−1), limits correlated components of recurrent propagation.Source: §4 · p. 9

Data separability

Each layer has a non-negligible amount of fresh new randomness, while separability information does not diminish by more than a polynomial factor when propagated through L layers.Source: §4 · p. 9

Intermediate layers

Intermediate-layer products satisfy the polynomial spectral bound ||W D_{i,ℓ1} ··· D_{i,ℓ2} W||₂ ≤ O(L^3).The analysis avoids exponential accumulation by combining fixed-vector concentration, ε-net arguments, and sparse-vector decompositions; tightening O(L^3) to O(1) is left open.Source: §4 · pp. 9–10

Backward propagation

The same random-matrix strategy extends to backward propagation for sparse diagonal activation patterns, with the output-weight matrix B contributing a spectral scale around √(m/d).The backward result is stated for ℓ1 ≥ ℓ2 and sparsity s ∈ [ρ², m^0.49].Source: §4 · p. 10

5 Stability After Adversarial Perturbation

This section analyzes RNN stability when the random initialization is subjected to an adversarially chosen perturbation. It develops forward, intermediate-layer, backward, and special rank-1 stability results used later for optimization updates and randomness decomposition.

Setup

The perturbation analysis allows W′ to depend on the random initialization, covering adversarial algorithmic updates and the later randomness-decomposition technique.The decomposition writes W = fW + W′, where fW is identically distributed as the true random initialization.Source: §5 · p. 10

Forward Stability

Forward stability is proved without exponential blow-up in the time horizon, despite adversarial changes that prevent naive induction.The proof recursively expands the recurrence and exploits a gap between norm bounds, with polynomially large width absorbing the resulting factors.Source: §5 · pp. 10–11

Intermediate Layers and Backward Stability

Using forward stability and sparsity, the analysis derives O(L^7) stability bounds for intermediate-layer products and backward propagation.These bounds compare perturbed products with their random-initialization counterparts.Source: §5 · p. 11

Special Rank-1 Perturbation

For rank-1 perturbations W′ = yz^T with unit z and sparse y, the paper establishes two additional bounds for every k ∈ [m].These special bounds are required for technical reasons in the subsequent analysis.Source: §5 · p. 11

6 Proof Sketch of Theorem 3: Polyak- Lojasiewicz Condition

The proof establishes the Polyak–Łojasiewicz lower bound by introducing a fake gradient and proving it remains large under perturbations. It then converts fixed-loss and coordinate-level arguments into a high-probability lower bound for the full true gradient.

6 Proof Sketch of Theorem 3: Polyak- Lojasiewicz Condition

Theorem 5 yields the key high-probability fake-gradient lower bound at random initialization, which implies Theorem 3 through stability and an ε-net union bound.The proof first transfers the bound through adversarial perturbations, then extends it from fixed losses to all losses and from fake to true gradients.Source: §6 · p. 12

6.1 Indicator and Backward Coordinate Bounds

The fake gradient factors into backward coordinates, forward vectors, and ReLU indicators; random initialization bounds these factors using concentration, coordinate-correlation control, and fresh randomness.McDiarmid’s inequality handles correlations caused by the shared matrix B, while ε-net arguments and independence between WU_ℓ* and A establish indicator-coordinate bounds.Source: §6.1 · pp. 12–13

6.2 Thought Experiment: Adding Small Rank-One Perturbation

A small rank-one perturbation can flip a selected ReLU indicator with constant probability while changing the forward vector and backward coordinate only slightly, preserving a large fake-gradient contribution.The construction uses a specially chosen coordinate satisfying the backward and indicator bounds, with perturbation scale controlled by the parameter θ.Source: §6.2 · p. 13

6.3 Real Proof: Randomness Decomposition and McDiarmid’s Inequality

The full proof decomposes Gaussian initialization into an unchanged component and a small perturbation, then uses an extended McDiarmid inequality to aggregate correlated good coordinates and prove Theorem 5.Randomness decomposition resolves the mismatch between perturbed and initial weights, while simultaneous small perturbations over coordinate sets overcome dependence and constant-probability events.Source: §6.3 · pp. 13–14

7 Proof Sketch of Theorem 4: Objective Semi-Smoothness … B Basic Properties at Random Initialization

This section develops the perturbation, concentration, and bounded-difference tools needed to establish objective semi-smoothness and the paper’s main proofs. It also analyzes random initialization, showing controlled forward and backward propagation in the RNN.

7 Proof Sketch of Theorem 4: Objective Semi-Smoothness

Objective semi-smoothness follows from Sections 4–5 without randomness decomposition or McDiarmid’s inequality, using a perturbation formula for hidden states.The proof considers random initialization, an adversarial perturbation, and a further perturbation, then substitutes the resulting bounds into Theorem 4.Source: §7 · p. 15
∥h_i,ℓ−ȟ_i,ℓ∥≤O(L^9)∥W′∥^2, showing the hidden-state difference is quadratic in the perturbation rather than bounded only by O(m^-1/2).The stronger bound is obtained through careful linear-algebraic manipulation and relies on the earlier bound in (4.1).Source: §7 · p. 15

8 Appendix Roadmap

The appendix roadmap assigns Appendix B to random initialization, Appendix C to adversarial stability, Appendices D–F to Theorem 3, Appendix G to Theorem 4, and Appendices H–I to GD and SGD convergence.The roadmap also introduces parameters controlling indicator thresholds, randomness decomposition, and the set used for McDiarmid’s inequality.Source: §8 · pp. 15–16

A Preliminaries on Probability Theory

The probability preliminaries cover randomness swapping, chi-square concentration, ReLU-of-Gaussian square sums, Gaussian-vector properties, and a generalized McDiarmid inequality.These tools are organized across Sections A.1–A.6 for use in later proofs.Source: A Preliminaries on Probability Theory · p. 18

A.2 Concentration of Chi-Square Distribution / A.3 Concentration of Sum of Squares of ReLU of Gaussians

Two-sided concentration bounds control sums of squared ReLU Gaussian variables and extend from single Gaussian matrices to multiple concatenated matrices.The appendix also characterizes the resulting random variables using chi-square and binomial structure.Source: §A.3 · pp. 20–21

A.4 Gaussian Vector Percentile: Center / A.5 Gaussian Vector Percentile: Tail / A.6 McDiarmid’s Inequality and An Extension

Gaussian-vector tools establish central percentiles and tail decompositions, while the McDiarmid extension provides concentration under high-probability bounded-difference conditions.For Gaussian vectors, the center results define (α,σ)-goodness and the tail result decomposes y=Wx into components with bounded infinity and Euclidean norms.Source: §A.4 · p. 22, §A.5 · pp. 22–23, §A.6 · p. 23

A.6 McDiarmid’s Inequality and An Extension

The McDiarmid-inequality extension establishes the desired theorem with probability at least 1 − N√p.The construction yields X_N = f(w_1, ..., w_N) with the stated high probability, while X_N = N otherwise.Source: §A.6 · p. 24

B Basic Properties at Random Initialization

At random initialization, forward propagation norms ∥h_i,ℓ∥_2 neither vanish nor explode.The section assumes Gaussian random initialization for W, A, and B and represents the recurrent update using diagonal activation matrices D_i,ℓ.Source: B Basic Properties at Random… · p. 25
The analysis lower-bounds projected forward propagation and characterizes projected propagation between two data points.These projections use the orthonormal basis U_ℓ constructed from the hidden states.Source: B Basic Properties at Random… · p. 25
Consecutive intermediate layers do not explode in spectral norm for either full or sparse vectors.The proof framework also defines the vectors v_i,ℓ used in the random-initialization analysis.Source: B Basic Properties at Random… · p. 25
Backward propagation does not explode at random initialization.This complements the forward-propagation and intermediate-layer spectral-norm controls.Source: B Basic Properties at Random… · p. 25

B.1 Forward Propagation … C.3 Backward

This section develops high-probability tools for forward and backward propagation in deep ReLU recurrent networks, including norm, separateness, spectral, sparse-vector, and perturbation-stability bounds. It establishes stability across intermediate layers and under small adversarial recurrent-weight perturbations using specified width, depth, and norm conditions.

B.1 Forward Propagation

With probability at least 1 −exp(−Ω(m/L2)), hidden-state norms satisfy (1 −1/(4L))^ℓ ≤∥hi,ℓ+1∥2 ≤2^ℓ + 4 across all samples and layers.The proof derives matching upper and lower bounds inductively over layers, using Gaussian concentration and ε-net arguments, then unions over the L layers.Source: §B.1 · p. 25

B.2 Forward Correlation

The forward-correlation analysis bounds the component of each hidden representation orthogonal to the previously generated subspace, quantifying how much fresh randomness remains after propagation.Lemma B.6 provides this high-probability projection bound, with the displayed bound involving 106L2 log3 m.Source: §B.2 · p. 28

B.2.1 Tools

The auxiliary tool analyzes random Gaussian vectors by splitting coordinates into large, intermediate, and small blocks, then combining support-size and chi-square concentration bounds.This establishes the projection-control ingredient used in the forward-correlation proof.Source: §B.2.1 · pp. 29–30

B.3 Forward δ-Separateness

With high probability, pairwise δ-separateness of the input representations is preserved across every layer for all distinct sample pairs.The proof proceeds inductively, decomposing one representation into components parallel and orthogonal to the other and exploiting independent Gaussian randomness.Source: §B.3 · p. 31
With probability at least 1−exp(−Ω(α^2m)), the forward δ-separateness argument establishes that w is (α, σ/4)-good and extends this guarantee uniformly via an ε-net.The argument then applies Lemma B.7 using independence between v and U,w to propagate the guarantee.Source: §B.3 · p. 32

B.4 Intermediate Layers: Spectral Norm

With probability at least 1−exp(−Ω(m/L^2)), intermediate layers preserve spectral norms uniformly across layer intervals and examples, with ∥z^ℓ∥2 ≤ (1+1/L)^(ℓ−b+1)∥z^(b−1)∥2.The proof partitions arbitrary vectors into L^3 coordinate trunks to avoid an infeasible union bound over all m-dimensional inputs.Source: §B.4 · pp. 33–34

B.4.1 Tools

For fixed vectors and Gaussian matrices, Claim B.13 supplies the concentration inequality needed to control intermediate-layer norms with failure probability exp(−Ω(m/L^2)).Its proof decomposes Gaussian products into independent components and combines binomial and chi-square concentration bounds.Source: §B.4.1 · p. 34

B.5 Intermediate Layers: Sparse Spectral Norm

For k-sparse vectors, intermediate-layer propagation is bounded by 3 with probability at least 1−e^{O(k log m)}e^{−Ω(m/L^2)}, yielding the stated sparse spectral-norm corollaries.The corollaries specialize this control to s^2m^(2/3)-sparse and 1-sparse vectors with failure probabilities exp(−Ω(s^2m^(2/3)log^2m)) and exp(−Ω(ρ^2)).Source: §B.5 · pp. 35–36

B.6 Backward Propagation

Backward propagation satisfies analogous high-probability bounds for sparse vectors, including corollaries for s^2m^(2/3)-sparse and 1-sparse inputs.Lemma B.17 combines intermediate-layer control with Gaussian bounds involving B, then applies ε-net and union-bound arguments over sparse vectors, layers, and examples.Source: §B.6 · pp. 36–37

C Stability After Adversarial Perturbation

Under an adversarial perturbation W′, Section C establishes separate stability results for forward propagation, intermediate layers, backward propagation, and rank-one perturbations.The forward, intermediate, and backward results are used in final training updates and randomness decomposition, whereas the rank-one result is used only in randomness decomposition.Source: C Stability After Adversarial… · p. 38

C.1 Forward

For ∥W′∥2 ≤ τ0/m^(1/3), forward perturbations satisfy ∥g′i,ℓ∥2,∥h′i,ℓ∥2 ≤ O(L^6τ0)/m^(1/2) and ∥D′i,ℓgi,ℓ∥2 ≤ O(L^5τ0)/m^(1/2).The same lemma also bounds the support size of D′i,ℓ and proves these inequalities with high probability over the random initialization.Source: §C.1 · pp. 38, 40
Forward analysis establishes high-probability goodness properties and decompositions for propagated vectors through products of ReLU-weight matrices.The tools use Gaussian-weight assumptions, fixed-vector arguments, and sparse-vector ε-net reasoning to control forward propagation.Source: §C.1.1 · pp. 41–42

C.1.1 Tools

The forward claims combine to control vectors of the form f_W eD_ℓ f_W ··· eD_b f_W x across recurrent layers.Claim C.5 provides a decomposition for these propagated vectors, which is then combined with Claim C.4.Source: §C.1.1 · p. 42

C.2 Intermediate Layers

Intermediate-layer stability bounds the effect of replacing f_W by f_W + W′ when ∥W′∥2 is sufficiently small, with the resulting operator bound at most O(L7).The bound applies across examples and layer intervals, under sparse diagonal perturbations and the stated high-probability conditions.Source: §C.2 · p. 43

C.3 Backward

Backward stability controls four forward/backward product differences under small W′ perturbations, for all layer ranges and training examples.The proof bounds representative products using factors such as (s · m^1/3 log m) × (s · m^-1/6 log m)^ℓ−1 × O(L3), together with intermediate-layer and output-matrix norm bounds.Source: §C.3 · p. 44

C.4 Special Rank-One Perturbation · D Indicator and Backward Coordinate Bounds · D.1 Indicator Coordinate Bound

The section establishes high-probability forward and backward bounds for special rank-one perturbations, then develops indicator-coordinate bounds that isolate one loss-maximizing sample-layer pair from the others. These results rely on Gaussian initialization, sparsity and independence conditions, concentration inequalities, and union bounds.

C.4 Special Rank-One Perturbation

Under Gaussian random initialization, special rank-one perturbations admit uniform forward-propagation bounds with high probability.The perturbation has the form W′ = yz^⊤, with ∥z∥ = 1, sparse y, and bounded ∥y∥∞.Source: §C.4 · pp. 45–47
The corresponding backward-propagation lemma gives high-probability bounds across samples, layers, and coordinates when the perturbation does not depend on B.The proof controls products of recurrent derivative factors and uses independence from B to obtain concentration.Source: §C.4 · p. 47
The backward analysis bounds derivative-product terms by polynomial powers of L, including O(L^3) and O(L^7), rather than leaving them uncontrolled.These bounds are applied to both perturbation-dependent and coordinate-vector terms.Source: §C.4 · pp. 47, 49

D Indicator and Backward Coordinate Bounds

The indicator-coordinate framework seeks many coordinates where the preactivation is small for the loss-maximizing pair (i*, ℓ*) but large for selected other sample-layer pairs.The surrounding section separates this indicator-coordinate result from a subsequent backward-coordinate result.Source: D Indicator and Backward Coordinate… · p. 50

D.1 Indicator Coordinate Bound

The indicator-coordinate lemmas construct sufficiently large coordinate sets using Gaussian anti-concentration, Chernoff bounds, ε-net arguments, and union bounds.The argument first handles fixed vectors, then extends to the random recurrent representation using norm control and discretization.Source: §D.1 · pp. 50–51
The construction refines an initial coordinate set N2 by exploiting independence from Wz for vectors orthogonal to the relevant recurrent subspaces.This independence permits concentration while conditioning on the randomness used to define N2.Source: §D.1 · p. 51
For non-target samples and later layers, successive coordinate sets N3 and N4 are obtained through Gaussian concentration and union bounds over samples and layers.The refinement covers i ≠ i* at ℓ = ℓ* and then ℓ > ℓ* through recursively defined sets.Source: §D.1 · p. 52

D.2 Backward Coordinate Bound

This section proves a backward coordinate bound for recurrent-network quantities under specified random-matrix and subset-size conditions. The proof combines Gaussian-coordinate analysis, Lipschitz sensitivity, and McDiarmid concentration.

D.2 Backward Coordinate Bound

Lemma D.7 establishes a backward coordinate bound when W, A, and B are random and N4 has the prescribed size and independence conditions.N4 may depend on W and A but not on B; the lemma uses the maximally large loss coordinate pair (i*, ℓ*).Source: §D.2 · p. 53
The argument bounds coordinate perturbations using the Lipschitz surrogate h and then applies McDiarmid’s inequality to a function of the B columns.The proof controls changes under coordinate replacement before concentrating the aggregate quantity.Source: §D.2 · pp. 53, 55, 56
Conditioning on events E1 and E2 separates randomness from W, A, and B before analyzing coordinates indexed by N4.The proof fixes W and A satisfying E1 and conditions on B satisfying E2.Source: §D.2 · pp. 53–54
For each coordinate in N4, the proof shows the relevant quantity is Gaussian in the randomized B columns, with variance bounded below by 1.This lower variance bound follows from norm inequalities and the earlier bound (D.1).Source: §D.2 · pp. 54–55
Combining the Step 1 estimate with the stated concentration argument yields the claimed result with probability at least 1 − e^−Ω(|N|/(nL)2) over the randomness of bN.Step 1 provides the expectation estimate used in the final combination.Source: §D.2 · p. 56

E Gradient Bound at Random Initialization (Theorem 5) … E.3.2 Core Lemma B

This section analyzes gradient bounds and stability at random initialization for recurrent activations. It develops the required upper and lower bounds using Gaussian randomness decompositions, sign-stability arguments, high-probability estimates, ε-net constructions, and union bounds.

E Gradient Bound at Random Initialization (Theorem 5)

The analysis replaces correlated true losses with fixed “fake losses” and defines a corresponding fake gradient for tractable gradient-bound arguments.The true loss vectors depend on network randomness, whereas the fake losses are fixed throughout this section.Source: E Gradient Bound at Random… · p. 56
Theorem 5 establishes high-probability lower bounds for the fake gradient at random initialization, while Lemma E.2 supplies corresponding upper bounds.The analysis uses ρ = nLd log m; Theorem 5 holds with probability at least 1 −e^−Ω(ρ^2), while Lemma E.2 uses 1 −e^−Ω(m/L^2).Source: E Gradient Bound at Random… · p. 57

E.1 Randomness Decomposition

Randomness decomposition writes W = W2 + W′, preserving W2’s initialization distribution while representing W′ as a correlated rank-one perturbation.The decomposition is constructed for fixed indices and a parameter θ, with W2 having i.i.d. Gaussian entries like W.Source: §E.1 · pp. 57–58

E.2 Gradient Lower Bound in Expectation

The expected-gradient lower bound isolates a loss vector of minimum norm and proves a high-probability bound under random initialization and structured coordinate subsets.Lemma E.6 fixes (i*, ℓ*) by minimizing the loss-vector norm and uses N within a specified size range.Source: §E.2 · p. 59

E.2.1 Proof of Lemma E.6

The proof obtains a nontrivial contribution by showing only the selected preactivation’s sign can change under the perturbation, while all other signs remain fixed.The argument treats three cases according to the sample and time index, then combines the resulting bounds across selected coordinates.Source: §E.2.1 · pp. 61–62

E.2.2 Core Lemma A

Core Lemma A reformulates the expectation bound using multiple random coordinate subsets, yielding simultaneous high-probability guarantees over W2, A, B, and the subsets.The construction splits W into W2, W′_N, and W′_−N, with t = m/|N| independent subsets of fixed cardinality.Source: §E.2.2 · p. 63
Core Lemma A is extended from one random subset to t samples by repeating the choice of N and applying a union bound.The resulting statement uses nested high-probability guarantees over initialization, sampled subsets, and the remaining randomness.Source: §E.2.2 · p. 63

E.3 Gradient Stability

Lemma E.8 provides the gradient-stability statement that Core Lemma B rewrites under the decomposition W = W2 + W′−N.The subsection fixes ρ, loss vectors, a random subset N containing j, and a rank-one perturbation W′′j while preserving random initialization.Source: §E.3 · p. 64, §E.3.2 · p. 65

E.3.1 Proof of Lemma E.8

Gradient stability is proved by controlling ReLU sign changes and combining these bounds with gradient-norm estimates at random initialization.The proof bounds the contribution of sign-changing indices and invokes ∥b∇kf(f W)∥2 ≤ O(ρ4) and ∥(eui,ℓ)k · ehi,ℓ∥2 ≤ O(ρ2L).Source: §E.3.1 · pp. 64–65

E.3.2 Core Lemma B

Core Lemma B holds with probability at least 1 −e−Ω(ρ2) simultaneously over initialization and t independent random subsets, for every sampled subset and admissible perturbation.Here ρ = nLd log m, t = m/|N|, and |N| ∈ [1, ̺ 100].Source: §E.3.2 · p. 66

E.4 Main Theorem: Proof of Theorem 5

The proof of Theorem 5 combines Core Lemmas A and B with an extended McDiarmid inequality to establish the required high-probability statement. It then controls the overlap of random subsets to complete the argument.

Proof of Theorem 5

Core Lemmas A and B yield the boxed high-probability statement when the network size |N| is appropriately chosen.The probability is at least 1 − e^−Ω(ρ^2) over the initialization randomness, including W2, A, B, and N1, · · · , Nt.Source: §E.4 · pp. 66–67
The proof applies extended McDiarmid’s inequality after conditioning on fixed quantities and scaling the random vector u_N so the relevant function lies in [0, 1].The argument conditions on the event ∥u_N∥∞ ≤ 3θρ^m and uses the bound 0 ≤ (u_N) ≤ O(Nρ^8).Source: §E.4 · p. 67
With probability at least 1 − e^−Ω(ρ^2), each index k ∈ [m] is covered by at most ρ^2 of the t random subsets N1, · · · , Nt.This random-subset overlap bound is used in the final step of the proof.Source: §E.4 · p. 68

F Gradient Bound After Perturbation (Theorem 3)

Theorem 3 establishes a high-probability gradient bound after perturbing the recurrent weight matrix, extending a fixed-loss result to the true loss through an ε-net argument.

Fixed-loss perturbation bound

Lemma F.1 first proves the corresponding bound for fixed loss vectors under a high-probability event and bounded perturbations.The fixed-loss statement assumes ∥W ′∥2 ≤ τ0 m with τ0 ≤ 100.Source: F Gradient Bound After Perturbation… · p. 69

Perturbation analysis

The proof controls gradient change by upper bounding ∥b∇f(f W + W ′) −b∇f(f W)∥F and combining this with the lower bound from Theorem 5.The argument separates several terms, including higher-order terms hidden in o(m1/3).Source: F Gradient Bound After Perturbation… · pp. 69–70

Extension to the true loss

An ε-net argument upgrades Lemma F.1 from fixed loss vectors to all loss vectors, enabling substitution of the true loss lossi,ℓ = Bhi,ℓ − y∗.This produces the loss-dependent gradient statement required by Theorem 3.Source: F Gradient Bound After Perturbation… · p. 70

Theorem 3 (restated)

Theorem 3 holds with probability at least 1 −e−Ω(ρ2) for all perturbations W ′ satisfying the stated spectral-norm bound.Here ρ = nLd log m, and the theorem is over the random matrices W, A, and B.Source: F Gradient Bound After Perturbation… · p. 70

G Objective Semi-Smoothness (Theorem 4) · G.1 Tool

The section establishes objective semi-smoothness near random initialization for the RNN objective, using recursive perturbation bounds for hidden states and ReLU activations. It also introduces a coordinatewise ReLU tool represented by diagonal correction matrices.

G Objective Semi-Smoothness (Theorem 4)

With probability at least 1 − e^−Ω(ρ^2), the objective admits a first-order upper approximation around any nearby weight matrix.The theorem applies to every W̌ satisfying ∥W̌ − W̃∥ ≤ τ_0, under the stated parameter definitions and initialization conditions.Source: G Objective Semi-Smoothness (Theorem 4) · p. 71
The proof controls the perturbed hidden-state difference recursively by introducing baseline, nearby, and additionally perturbed recurrent trajectories.These trajectories track the effects of W̃ and W̃ + W′ through the recurrent ReLU updates and loss quantities.Source: G Objective Semi-Smoothness (Theorem 4) · p. 71
The hidden-state recursion relies on diagonal activation matrices and bounds the coordinates where the ReLU signs differ between trajectories.Sign-disagreement coordinates are linked to mismatches among the corresponding diagonal activation matrices, enabling probabilistic control of their number.Source: G Objective Semi-Smoothness (Theorem 4) · pp. 71–72
Norm bounds on hidden states and recurrent matrix products control the higher-order remainder after expanding the objective around W̌.The proof combines recursive perturbation estimates, operator-norm bounds, and triangle inequality to obtain the theorem’s remainder term.Source: G Objective Semi-Smoothness (Theorem 4) · pp. 71–73

G.1 Tool

Proposition G.3 provides a coordinatewise diagonal representation for differences of ReLU outputs under arbitrary input vectors and a diagonal sign matrix.The proof checks the four possible sign combinations of the two coordinates, including both cases where the inputs have opposite signs.Source: §G.1 · p. 73
The coordinatewise ReLU argument distinguishes jointly active, jointly inactive, and sign-changing coordinates to construct the correction matrix.This elementary tool supplies the activation-difference identity used in the hidden-state perturbation recursion.Source: §G.1 · p. 73

H Convergence Rate of Gradient Descent (Theorem 1)

Theorem 1 shows that, under sufficiently large width and random initialization, gradient descent trains the RNN to loss ε at a linear convergence rate with high probability.

Theorem 1

The result requires polynomially large width m, with dependencies on the training parameters, network dimensions, depth L, confidence δ, and target loss ε.The analysis tightens the dependencies on δ and ε, while noting that a more involved analysis can remove the log(1/ε) dependency in m [3].Source: H Convergence Rate of Gradient Descent… · p. 74
The training loss of the recurrent neural network drops to ε at a linear convergence speed.The theorem establishes this convergence from random initialization with probability at least 1 − e^−Ω(ρ^2).Source: H Convergence Rate of Gradient Descent… · p. 74

Proof of Theorem 1

The proof maintains a small deviation from initialization throughout gradient descent, ensuring the assumptions needed to apply the auxiliary convergence and gradient bounds.It first assumes the stability condition (H.1), proves convergence under that condition, and then verifies it for every iteration.Source: H Convergence Rate of Gradient Descent… · p. 74

I Convergence Rate of Stochastic Gradient Descent (Theorem 2)

Theorem 2 establishes high-probability convergence of stochastic gradient descent for sufficiently wide recurrent networks under random initialization. Its proof combines gradient estimates, martingale concentration, and parameter-drift control, while leaving polynomial width dependencies untightened.

Theorem 2

With sufficiently large width and random initialization, SGD satisfies Theorem 2 with probability at least 1 − e^−Ω(ρ^2).The theorem defines ρ and imposes a width condition polynomial in the stated parameters, though the extracted statement omits parts of the displayed formulas.Source: I Convergence Rate of Stochastic… · p. 75
The theorem presents a simplified width requirement, tightening dependencies on δ and ε while not optimizing polynomial factors in n, d, and L.The authors note that a more involved analysis can remove the log(1/ε) dependence in m.Source: I Convergence Rate of Stochastic… · p. 75

Proof of Theorem 2

The analysis verifies that SGD remains in a small neighborhood of initialization, allowing the assumed conditions to hold throughout optimization.The proof bounds f(W^(t)) by O(nρ^2L^3) and then uses Theorem 3 to control ||W^(t) − W^(0)||_F.Source: I Convergence Rate of Stochastic… · pp. 75–76
The proof establishes convergence by combining unbiased stochastic gradients, gradient-norm bounds, and one-sided Azuma martingale concentration.The argument invokes Theorems 3 and 4, Jensen’s inequality, and Cauchy–Schwarz to control the stochastic update process.Source: I Convergence Rate of Stochastic… · pp. 75–76