PaperlayerView exact revision on arXiv

Source-linked AI summary

Can SGD Learn Recurrent Neural Networks with Provable Generalization?

Zeyuan Allen-Zhu, Yuanzhi Li

arXiv:1902.01028v2cs.LGcs.DScs.NEmath.OCstat.ML

TL;DR

The paper addresses the limited understanding of what RNNs can learn with generalization guarantees, especially when existing bounds grow exponentially with sequence length. It analyzes vanilla SGD for a concept class that includes smooth functions mapping earlier tokens to later outputs. The results establish polynomial or almost-polynomial complexity in input length for specified function families, while the target functions adapt to token positions rather than past-token values.

  • Problem

    RNN learning theory has limited answers about learnable concept classes and generalization, while existing bounds can grow exponentially with input length.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes vanilla SGD on a ReLU RNN for targets approximately realizable by a smooth function in a specified concept class.

    Source: §1 · p. 2

  • Results

    For constant-degree polynomial φ, C = poly(L, log ε^-1); for functions with good Taylor truncation, C = L^O(log(1/ε)).

    Source: §4.1 · p. 6

  • Takeaways & Limitations

    The concept class includes per-token outputs generated from earlier inputs by two-layer neural networks, and the recurrent unit can learn different functions across token positions.

    Source: §4.1 · p. 6

    The target function adapts to input-token positions but not to the values of past tokens.

    Source: §4.1 · p. 6

Abstract

from arXiv · show

Recurrent Neural Networks (RNNs) are among the most popular models in sequential data analysis. Yet, in the foundational PAC learning language, what concept class can it learn? Moreover, how can the same recurrent unit simultaneously learn functions from different input tokens to different output tokens, without affecting each other? Existing generalization bounds for RNN scale exponentially with the input length, significantly limiting their practical implications. In this paper, we show using the vanilla stochastic gradient descent (SGD), RNN can actually learn some notable concept class efficiently, meaning that both time and sample complexity scale polynomially in the input length (or almost polynomially, depending on the concept). This concept class at least includes functions where each output token is generated from inputs of earlier tokens using a smooth two-layer neural network.

1 Introduction

The introduction frames RNNs as difficult to analyze jointly for optimization and generalization, especially because existing bounds may grow exponentially with sequence length. The paper presents an SGD guarantee for a concept class with efficient learning and explains how one recurrent unit can handle different token-position functions.

1 Introduction

  • The introduction identifies optimization and generalization as open questions, with vanishing or exploding gradients and non-convex training among the optimization challenges.It also asks how a shared recurrent operation can implement different rules for the same token at different positions.Source: §1 · pp. 1–2
  • Prior optimization results show benefits from over-parameterization in linear dynamic systems and ReLU RNNs, but the latter result gives no generalization guarantee.The paper frames bridging optimization and generalization as especially challenging for RNNs because input length can cause exponential blowup.Source: §1 · p. 2
  • Existing RNN generalization bounds can grow exponentially with input length when the recurrent-unit operator norm β exceeds 1.The introduction notes that applications may allow β > 1 for greater expressibility.Source: §1 · p. 2
  • Strong regularization or small networks may aid generalization, but the introduction says it is unclear whether SGD can find such networks with low training loss.Without regularization, the number of parameters may be large and β may exceed 1, where known bounds fail to apply.Source: §1 · p. 2
  • The paper proves that vanilla SGD on a ReLU RNN can achieve small training and generalization error when outputs are approximately realizable by a smooth function in the stated concept class.The guarantee allows β to exceed 1 by a constant and has iteration, sample, and time complexities polynomial or almost polynomial in input length.Source: §1 · p. 2

2 Notations

The notation section establishes conventions for norms, smoothness, and function complexity used in the analysis.

2 Notations

  • The paper uses Euclidean and spectral norms, as well as infinity, sparsity, and Frobenius norms, with row norms introduced for matrices.It also defines Gram–Schmidt orthonormalization for a collection of vectors.Source: §2 · pp. 2–3
  • A function is L-Lipschitz when its value changes by at most L times the Euclidean distance, and L-smooth when its gradient is L-Lipschitz.The section also defines ReLU and its coordinate-wise application to vectors.Source: §2 · p. 3
  • The section defines complexity measures for infinite-order differentiable functions using their Taylor-series behavior.For constant-degree polynomials, the stated bounds are O(R^d) for C_s and O(R^d polylog(1/ε)) for C_ε.Source: §2 · p. 3

3 Problem Formulation

The problem formulation specifies an i.i.d. sequence-learning setting, an Elman RNN learner, and a bounded-complexity target class evaluated by population risk.

3 Problem Formulation

  • The data are modeled as i.i.d. samples from an unknown distribution over true input and label sequences.The training set contains N such samples.Source: §3 · p. 3
  • Each true input is transformed into an actual sequence for the RNN, with the resulting sequence normalized so its first token has norm 1 and later tokens have norm ε_x.The transformation uses a parameter ε_x in (0, 1).Source: §3 · pp. 3–4

3.1 Our Learner Network: Elman RNN

  • The learner is a classical Elman RNN with ReLU activation and recurrent matrix W.The network also has input and output matrices A and B.Source: §3.1 · p. 4
  • Training updates W while keeping A and B at random initialization, and fits the output sequence to the true labels using a convex, 1-Lipschitz loss.The stated loss examples include cross-entropy and ℓ2 regression for bounded labels.Source: §3.1 · p. 4

3.2 Concept Class

  • The target functions combine smooth functions of inputs at earlier positions to produce outputs at each later token.The concept class includes functions whose per-token outputs are generated from earlier inputs by a two-layer neural network.Source: §3.2 · pp. 4–5
  • The agnostic PAC objective is to learn targets in the stated class, bounded by complexity C and parameter p_0, with population risk OPT + ε.The stated sample and time complexities are polynomial in C, p_0, and 1/ε.Source: §3.2 · pp. 4–5

4 Our Result: RNN Provably Learns the Concept Class

The paper analyzes vanilla SGD for learning a bounded-complexity RNN concept class, then interprets the guarantee and its scope. Its proof combines a linear approximation, a constructed target representation, an SGD descent argument, and a Rademacher complexity bound.

4 Our Result: RNN Provably Learns the Concept Class

  • The theorem assumes a target in the concept class and states sufficient width and sample-size conditions for an SGD guarantee, with probability at least 1 − e^−Ω(ρ^2) over initialization.The supplied theorem passage specifies m ≥ poly(C, ε^-1), N ≥ poly(C, ε^-1, log m), and that sample complexity is also bounded by the number of SGD iterations.Source: §4 · pp. 5–6

4.1 Our Contribution, Interpretation, and Discussion

  • For constant-degree polynomial φ, the paper gives C = poly(L, log ε^-1), and for functions with good Taylor truncation it gives C = L^O(log(1/ε)).The latter category includes exp(z) − 1, sin z, sigmoid, and tanh.Source: §4.1 · p. 6
  • The learnable functions include weighted averages of nonlinear measurements and at least per-token outputs generated from earlier inputs by two-layer neural networks.The paper notes these averages are used in sentence embedding and as a basis for attention mechanisms in RNNs.Source: §4.1 · p. 6
  • The target functions can vary with input-token positions even though positions are not directly fed into the network.The paper attributes this ability to differences among hidden layers at different positions.Source: §4.1 · p. 6
  • The target functions adapt to input positions, not to the values of past tokens, and the complexity parameter worsens with sequence length.The paper attributes the length dependence to increasing noise in hidden neurons that makes new input signals less significant over time.Source: §4.1 · p. 6

4.2 Conclusion

  • The conclusion presents efficient SGD learning for a nontrivial concept class, with sample complexity almost independent of network width.It also identifies explaining how a shared recurrent unit learns different functions across input and output tokens as a contribution.Source: §4.2 · p. 7

Proof Sketch

  • The proof sketch linearizes output changes around initialization, constructs a matrix approximating the target, and argues SGD moves in a nearly as-good direction.It then uses the linear approximation for a Rademacher complexity bound that does not grow exponentially in L.Source: Proof Sketch · p. 7

5 Existence of Good Network Through Backward

Section 5 constructs a bounded linear perturbation of the recurrent weights that can represent target functions across different input-token/output-token pairs. Its construction uses an indicator-to-function lemma and a single-function fitting result.

5 Existence of Good Network Through Backward

  • A bounded-Frobenius-norm matrix can simultaneously represent functions from different input tokens to different output tokens, and SGD descends in a comparable direction.The section frames the construction as a linear function over the recurrent weight matrix that captures first-order output changes.Source: §5 · p. 8

5.1 Indicator to Function

  • Lemma 5.1 uses a bounded indicator function to fit a smooth target, while its new noise property makes the function nearly constant when the noise magnitude is large.The fitting property comes from prior work [1]; the nearly-constant property is presented as new.Source: §5.1 · p. 8

5.2 Fitting a Single Function

  • For a single input-token/output-token function, the recurrent-state inner product acts as noise: it is small for the matching token and remains large for different, somewhat uncorrelated states.The construction also uses a null sequence independent of the true input that stays close enough to the true hidden state.Source: §5.2 · p. 9

5.3 Fitting the Target Function

  • The constructed matrix approximates the target across output positions and coordinates with high probability, while its Frobenius norm scales as m^-1/2, making sample complexity independent of m up to logarithmic factors.The stated guarantee applies to normalized input sequences generated from inputs in the support of the distribution.Source: §5.3 · pp. 10–11

6 Coupling and First-Order Approximation

Section 6 relates changes in the RNN output after a small weight perturbation to a linear function of that perturbation. It also shows that the constructed target-representing matrix retains its property after such perturbations.

6 Coupling and First-Order Approximation

  • The first-order approximation is stated uniformly over small perturbations, allowing the perturbation to depend on the random initialization.The section motivates this uniformity as a way to untangle correlations between the perturbation and initialization.Source: §6 · p. 11
  • For perturbations within the stated spectral-norm bound, the output difference is approximated by a linear function of the weight change.The linear expression uses hidden states, derivatives, and backward terms from the unperturbed network.Source: §6 · p. 11
  • The matrix constructed in Section 5 retains its target-representation property after any perturbation within the stated spectral-norm bound, with high probability.The result follows by combining the existence result with the first-order coupling lemma.Source: §6 · pp. 11–12

7 Optimization and Convergence

Section 7 presents the main convergence lemma for SGD on the training objective. Its proof sketch uses a linearized objective whose value and gradient match those of the original objective at the current iterate, then argues via descent.

7 Optimization and Convergence

  • The section states a main convergence lemma for SGD on the training objective.The supplied proof sketch explains convergence through a gradient-descent argument when the objective exceeds OPT by more than the stated tolerance.Source: §7 · pp. 12–13
  • The proof sketch defines a convex surrogate objective over the linear perturbation, with the original objective and gradient matching its value and gradient at zero.The matching is stated for the current weight iterate.Source: §7 · p. 13
  • The descent argument says the objective decreases while it remains above OPT plus the stated tolerance, so this cannot persist for too many iterations.The sketch first presents this argument for gradient descent rather than SGD.Source: §7 · p. 13

8 Rademacher Complexity Through Coupling

Section 8 bounds Rademacher complexity by first using coupling to reduce the RNN to a linear function class, then analyzing that class. The supplied passages do not state the bound's formula.

8 Rademacher Complexity Through Coupling

  • The proof uses the coupling lemma to reduce the RNN analysis to the complexity of a linear function class.The section describes this as the two-step complexity argument.Source: §8 · pp. 13–14
  • The section gives a Rademacher-complexity lemma for RNN outputs at each coordinate and layer.The passage introducing the lemma does not provide its bound formula.Source: §8 · p. 14
  • After coupling, the relevant function is written as linear in the weight perturbation.The proof then applies a proposition to bound the complexity of that linear function.Source: §8 · p. 14

9 Proof of Theorem 1

The proof combines an SGD guarantee with generalization analysis and properties of the RNN at random initialization. Its argument also addresses a bounded-loss technical issue through truncation.

9 Proof of Theorem 1

  • With at least 1 − e^−Ω(ρ^2) probability over random initialization, the theorem’s SGD guarantee uses polynomial width and sample-size requirements in C, p, L, d, and ε^−1.The supplied theorem fragments also specify a learning-rate choice, but do not provide its complete expression.Source: §9 · p. 14
  • Because the loss is not absolutely bounded on all samples, the proof truncates it for analysis, applies the bounded-loss argument, then removes truncation using a rare-event bound.The empirical risk remains unchanged by truncation, while the population risk is initially bounded only in truncated form.Source: §9 · p. 15

A Rademacher Complexity Review

  • The generalization argument invokes Rademacher complexity bounds for bounded function classes and Lipschitz loss composition.The review also recalls a linear-class complexity bound for unit-norm inputs.Source: A Rademacher Complexity Review · p. 16

B Random Initialization: Basic Properties

  • The random-initialization properties are stated for normalized sequences with a first input of unit norm and later inputs of small norm.The appendix contrasts this setting with prior work studying multiple fixed sequences and later inputs of norm up to one.Source: B Random Initialization: Basic… · p. 16

B.1 Proof for Lemma B.1

This proof section establishes several initialization properties used for recurrent-network analysis, including bounds on hidden-state behavior and forward correlations.

B.1 Proof for Lemma B.1

  • The proof uses a low-dimensional column-span representation and a net argument to extend bounds over candidate hidden-state vectors.For the forward-propagation bound, it substitutes the hidden state into the uniform bound over vectors of controlled norm.Source: §B.1 · p. 18

C Random Initialization: Backward Correlation

The section states a backward-correlation property for RNNs at random initialization and introduces a stability analysis comparing two input-sequence executions.

C Random Initialization: Backward Correlation

  • At random initialization, backward-propagated vectors associated with distinct output positions are very uncorrelated with high probability.The lemma states this for every fixed normalized input sequence and indices satisfying j < j′.Source: C Random Initialization: Backward… · p. 19
  • The authors note that the correlation result can be extended to pairs with unequal differences j − i and j′ − i′, but do not need that stronger form.Source: C Random Initialization: Backward… · p. 19

D Stability: After Dropping x⋆

  • The next section compares two RNN executions: one on a baseline sequence and another on a sequence formed from an arbitrary supported input sequence.The supplied lemma fragment states a high-probability property for these executions but does not include the property’s full expression.Source: D Stability: After Dropping x⋆ · pp. 21–22

D.1 Proof of Lemma D.1a

These appendix sections analyze stability under input changes, row re-randomization, and adversarial weight perturbations, alongside a Gaussian-ReLU tool and a restatement of a prior approximation lemma.

D.1 Proof of Lemma D.1a

  • A change of size τ to a pre-activation vector yields at most O(τ^2/3 m + ρ^2) sign changes with the stated high probability.Source: §D.1 · p. 24

D.3 Mathematical Tools

  • The Gaussian-ReLU tool established in this section is 0.5-Lipschitz continuous over x.Source: §D.3 · p. 25

E Stability: After Re-Randomization

  • For row re-randomization affecting at most m/ρ^23 rows, the backward-vector difference is bounded by O(ρ^7(N/m)^1/6) times the test-vector norm.The lemma states this with probability at least 1 − e^−Ω(ρ^2).Source: E Stability: After Re-Randomization · p. 26

F Stability: After Adversarial Perturbation

  • The adversarial-perturbation section considers recurrent-weight shifts W′ with spectral norm at most Δ, uniformly over such perturbations.The passage frames this stability setting as capturing possible SGD movement from initialization.Source: F Stability: After Adversarial… · p. 29

G.1 Missing Proof of Lemma 5.1

  • The proof restates an indicator-to-function lemma for smooth functions and notes that its approximation constant is unchanged under the stated rescaling.Source: §G.1 · pp. 29–30

G.2 Missing Proof of Lemma 5.2

The appendix gives proof steps for Lemmas 5.2, 5.4, 6.1, 6.2, and 7.1, along with a norm-bound claim for W ⋇.

G.2 Missing Proof of Lemma 5.2

  • The proof distinguishes “On Target” and “Off Layer” parts; a step is justified using Lemma 5.1, and the off-target part is finished by combining the preceding result with (G.11) and the chosen εc.Source: §G.2 · pp. 32–34

G.3 Missing Proof of Lemma 5.4

  • The proof of Lemma 5.4 replaces a random subset of rows with fresh i.i.d. samples and bounds hidden-state perturbations and resulting sums.The proof uses concentration bounds for the sums.Source: §G.3 · pp. 34–36

G.4 Norm Bound on W ⋇

  • Claim G.1 states that a norm bound on W ⋇ holds with high probability over random initialization of W, A, and B.Source: §G.4 · p. 37

H.1 Proof of Lemma 6.1

  • The proof of Lemma 6.1 derives a semi-smoothness bound using ReLU's 1-Lipschitz continuity, paralleling [2].Source: §H.1 · p. 38

H.2 Proof of Lemma 6.2

  • The proof of Lemma 6.2 analyzes three error terms separately.Source: §H.2 · p. 39

I Proof for Lemma 7.1

  • The proof of Lemma 7.1 uses the convexity of surrogate eG and relates Obj(Wt) and its gradient to eG at zero.It also notes that SGD uses a stochastic gradient.Source: I Proof for Lemma 7.1 · pp. 40–41

Related papers

Loading 1902.01028v2…