Can SGD Learn Recurrent Neural Networks with Provable Generalization?

By Zeyuan Allen-Zhu, Yuanzhi Li. 2019

61 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, neutral): “[4, 7, 8, 13, 14, 26–29, 38, 45, 50, 57, 61, 104, 115]).”
What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, methodology): “ete the proof. The second inequality follows from sub-exponential concentration bounds. The next proposition at least traces back to [5] and was stated for instance in [6]. Proposition B.4. Suppose 2[0;1] and g(0) 2Rm is a random vector g(0) ˘N(0;I m ). With probability at least 1 e (m2=3), for all ”
Generalization and Representational Limits of Graph Neural Networks (2020, background): “Several works have established generalization guarantees for FFNs (Bartlett et al., 2017; Golowich et al., 2018; Neyshabur et al., 2018; Zhang et al., 2018a) and RNNs (Chen et al., 2019a; Allen-Zhu and Li, 2019).”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, methodology): “[23], [15], [3], [9], [2], [1]) also use the method of "coupling" and the popular ReLU activation.”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “2 With huge non-convexity obstacles, existing theoretical works, to the best of our knowledge, have only been able to demonstrate that multi-layer neural networks can efficiently perform learning tasks that are already known solvable by non-hierarchical methods, such as kernel methods [3, 6, 7, 9, 1”
Understanding Generalization in Recurrent Neural Networks (2020, background): “There are also some works about the generalization of recurrent neural networks (Zhang et al., 2018; Chen et al., 2019; Allen-Zhu & Li, 2019).”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, unknown): “(2018); Arora et al. (2019b); Cao and Gu (2019); Du et al. (2018c); Arora et al. (2019a); Allen-Zhu and Li (2019b); Allen-Zhu et al.”
Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations (2019, background): “…can be regarded as a linear model with infinite dimensional feature (Jacot et al., 2018; Li & Liang, 2018; Du et al., 2019a; Arora et al., 2019; Du et al., 2019b; Allen-Zhu et al., 2018; Allen-Zhu & Li, 2019; Allen-Zhu et al., 2019; Du et al., 2019a; Zou et al., 2018; Oymak & Soltanolkotabi, 2018).”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “On the other hand, unlike in supervised training where the training objective involving a (over-parameterized) deep neural network can be approximately convex [9, 48, 4, 10, 31, 15, 14, 80, 30, 27, 42, 36, 52, 40, 74, 26, 81, 26], to the best of our knowledge, there are also no theoretical result sh”