Can SGD Learn Recurrent Neural Networks with Provable Generalization?

Abstract

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.

V2 polishes writing

References in corpus (14)

• Sequence to Sequence Learning with Neural Networks
• On the difficulty of training Recurrent Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Recent Advances in Recurrent Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Machine Learning on Sequential Data Using a Recurrent Weighted Average
• Theoretical properties of the global optimizer of two layer neural network
• On Generalization Bounds of a Family of Recurrent Neural Networks
• Stabilizing Gradients for Deep Neural Networks via Efficient SVD Parameterization

Cited by in corpus (5)

• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Constructing Gradient Controllable Recurrent Neural Networks Using Hamiltonian Dynamics