mlsanityData to 14 Oct 2026

On the Role of Noise in the Sample Complexity of Learning Recurrent Neural Networks: Exponential Gaps for Long Sequences

arXiv 2305.18423 ↗First posted 28 May 2023stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider the class of noisy multi-layered sigmoid recurrent neural networks with w (unbounded) weights for classification of sequences of length T, where independent noise distributed according to N(0,σ2) is added to the output of each neuron in the network. Our main result shows that the sample complexity of PAC learning this class can be bounded by O (wlog(T/σ)). For the non-noisy version of the same class (i.e., σ=0), we prove a lower bound of Omega (wT) for the sample complexity. Our results indicate an exponential gap in the dependence of sample complexity on T for noisy versus non-noisy networks. Moreover, given the mild logarithmic dependence of the upper bound on 1/σ, this gap still holds even for numerically negligible values of σ.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 37 of its 65 references that are in the map. First posted on arXiv 28 May 2023.

Builds on

37 of 65 references.

References · 37

  1. 2014Sequence to Sequence Learning with Neural Networkscited by 2,986
  2. 2014Deep Visual-Semantic Alignments for Generating Image Descriptionscited by 968
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  4. 2013Speech Recognition with Deep Recurrent Neural Networkscited by 669
  5. 2019Benign Overfitting in Linear Regressioncited by 549
  6. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  7. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  8. 2017Implicit Regularization in Matrix Factorizationcited by 322
  9. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  10. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
  11. 2018Stronger generalization bounds for deep nets via a compression approachcited by 307
  12. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
25 more
  1. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  2. 2017Size-Independent Sample Complexity of Neural Networkscited by 290
  3. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  4. 2017A Dual-Stage Attention-Based Recurrent Neural Network for Time Series Predictioncited by 245
  5. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
  6. 2021Deep learning: a statistical viewpointcited by 240
  7. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 224
  8. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  9. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 126
  10. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  11. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  12. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  13. 2018Does data interpolation contradict statistical optimality?cited by 95
  14. 2020Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithmscited by 89
  15. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  16. 2016Gradient Descent Learns Linear Dynamical Systemscited by 79
  17. 2020Gradient descent follows the regularization path for general lossescited by 59
  18. 2019Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resiliencecited by 51
  19. 2020Do RNN and LSTM have Long Memory?cited by 47
  20. 2019On Generalization Bounds of a Family of Recurrent Neural Networkscited by 42
  21. 2021Noisy Recurrent Neural Networkscited by 42
  22. 2018Stabilizing Gradients for Deep Neural Networks via Efficient SVD Parameterizationcited by 35
  23. 2019Can SGD Learn Recurrent Neural Networks with Provable Generalization?cited by 17
  24. 2014Dropout Rademacher Complexity of Deep Neural Networkscited by 14
  25. 2022Benefits of Additive Noise in Composing Classes with Bounded Capacitycited by 4

Built on by

Not cited yet.