mlsanityData to 7 Oct 2026

On the Provable Generalization of Recurrent Neural Networks

arXiv 2109.14142 ↗First posted 29 Sep 2021cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

Recurrent Neural Network (RNN) is a fundamental structure in deep learning. Recently, some works study the training process of over-parameterized neural networks, and show that over-parameterized networks can learn functions in some notable concept classes with a provable generalization error bound. In this paper, we analyze the training and generalization for RNNs with random initialization, and provide the following improvements over recent works: 1) For a RNN with input sequence x=(X1,X2,...,XL), previous works study to learn functions that are summation of f(βTlXl) and require normalized conditions that ||Xl||≤ε with some very small ε depending on the complexity of f. In this paper, using detailed analysis about the neural tangent kernel matrix, we prove a generalization error bound to learn such functions without normalized conditions and show that some notable concept classes are learnable with the numbers of iterations and samples scaling almost-polynomially in the input length L. 2) Moreover, we prove a novel result to learn N-variables functions of input sequence with the form f(βT[Xl1,...,XlN]), which do not belong to the "additive" concept class, i,e., the summation of function f(Xl). And we show that when either N or l0=max(l1,..,lN)-min(l1,..,lN) is small, f(βT[Xl1,...,XlN]) will be learnable with the number iterations and samples scaling almost-polynomially in the input length L.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 31 of its 42 references that are in the map. First posted on arXiv 29 Sep 2021.

Builds on

31 of 42 references.

References · 31

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  6. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  7. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  8. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  9. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  10. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  11. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  12. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
19 more
  1. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  2. 2016Topology and Geometry of Half-Rectified Network Optimizationcited by 102
  3. 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
  4. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  5. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  6. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 83
  7. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  8. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  9. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  10. 2016Gradient Descent Learns Linear Dynamical Systemscited by 78
  11. 2020The Recurrent Neural Tangent Kernelcited by 67
  12. 2020Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspectivecited by 60
  13. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  14. 2019On Generalization Bounds of a Family of Recurrent Neural Networkscited by 42
  15. 2018Stabilizing Gradients for Deep Neural Networks via Efficient SVD Parameterizationcited by 35
  16. 2017When is a Convolutional Filter Easy To Learn?cited by 21
  17. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  18. 2019Can SGD Learn Recurrent Neural Networks with Provable Generalization?cited by 17
  19. 2020Is the Skip Connection Provable to Reform the Neural Network Loss Landscape?cited by 4

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 1; 2024: 1.

6 papers.

  1. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  2. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  3. 2022Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysiscited by 22
  4. 2023A Brief Survey on the Approximation Theory for Sequence Modellingcited by 15
  5. 2022Global Convergence of Over-parameterized Deep Equilibrium Modelscited by 10
  6. 2022Linear RNNs Provably Learn Linear Dynamic Systemscited by 0