Can SGD Learn Recurrent Neural Networks with Provable Generalization?

Zeyuan Allen-Zhu, Yuanzhi Li

Introduction

Recurrent Neural Networks (RNNs) are fundamental to sequential data analysis, yet their theoretical properties remain poorly understood. Historically, two major obstacles have hindered a rigorous theory for RNNs: the optimization challenge, characterized by vanishing or exploding gradients, and the generalization challenge, where existing bounds often grow exponentially with the input sequence length $L$. This exponential dependence suggests that learning long sequences would require an impractical amount of data.

This work provides the first theoretical guarantee that vanilla Stochastic Gradient Descent (SGD) can efficiently train over-parameterized RNNs to achieve both low training and generalization error. Crucially, the authors demonstrate that for a specific class of smooth functions, the time and sample complexity scale polynomially with $L$, effectively breaking the "exponential barrier" that has long plagued RNN theory.

Methodology

The study focuses on a vanilla Elman RNN architecture utilizing ReLU activation functions. The analysis is built upon several technical pillars:

Over-parameterization

The hidden layer is assumed to be sufficiently "wide," with a large number of neurons $m$. In this over-parameterized regime, the network's behavior remains stable near its random initialization, facilitating a more tractable analysis.

Algorithm and Optimization

The training process follows standard Stochastic Gradient Descent. The authors prove that during training, the RNN's output can be closely approximated by a linear function of the weight changes—a phenomenon known as first-order coupling. This allows the application of linear optimization tools to a highly non-linear system.

Algorithm 1: Stochastic Gradient Descent (SGD) for Recurrent Neural Networks.

Concept Class Learning

Rather than attempting to learn arbitrary functions, the researchers define a "concept class" of target functions. This class consists of functions where each output token is generated from previous inputs via a smooth two-layer neural network. The goal is to prove Agnostic PAC-learning: the learner can match the performance of the best function within this class.

Theoretical Insights

A key insight of this paper is that inhomogeneity is a feature. While the same weight matrix is applied at every step, the hidden states $h_\ell$ naturally evolve and accumulate "noise" or signal as the sequence progresses. This inherent inhomogeneity allows the RNN to distinguish between different positions in a sequence despite weight sharing.

Furthermore, the authors derive a new bound for the Rademacher complexity of RNNs. Unlike previous bounds that explode exponentially with sequence length, this new bound scales polynomially by leveraging the smoothness of the target concept class. This bridges the gap between worst-case theory and average-case practice.

Key Results

The paper establishes several significant results:

  • Efficiency Guarantee: If the number of neurons $m$ and samples $N$ are polynomial in $L$ and other parameters, SGD will converge to a solution with population risk $OPT + \epsilon$ in polynomial time.
  • Polynomial Generalization: The generalization bound depends on the smoothness of the target function rather than the raw norm of the weights, preventing exponential blow-up.
  • Spectral Radius Stability: The results remain valid even when the spectral radius of the recurrent weights is slightly greater than 1, a regime typically associated with exploding gradients.

Discussion and Limitations

While this work represents a major step forward, it has limitations. The proofs are tied to a specific class of smooth target functions; whether RNNs can provably learn discrete or combinatorial logic remains an open question. Additionally, the over-parameterization requirement involves a high-degree polynomial for $m$, whereas practical RNNs often succeed with much smaller hidden layers. Future work may explore how architectures like LSTMs or GRUs might handle even longer-term dependencies more efficiently than the vanilla RNNs studied here.

Summary updated

BibTeX
@inproceedings{allenzhu2019can,
  author = {Zeyuan Allen-Zhu and Yuanzhi Li},
  title = {{Can SGD Learn Recurrent Neural Networks with Provable Generalization?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure