mlsanityData to 7 Oct 2026

On the Double Descent of Random Features Models Trained with SGD

arXiv 2110.06910 ↗First posted 13 Oct 2021stat.ML cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We study generalization properties of random features (RF) regression in high dimensions optimized by stochastic gradient descent (SGD) in under-/over-parameterized regime. In this work, we derive precise non-asymptotic error bounds of RF regression under both constant and polynomial-decay step-size SGD setting, and observe the double descent phenomenon both theoretically and empirically. Our analysis shows how to cope with multiple randomness sources of initialization, label noise, and data sampling (as well as stochastic gradients) with no closed-form solution, and also goes beyond the commonly-used Gaussian/spherical data assumption. Our theoretical results demonstrate that, with SGD training, RF regression still generalizes well for interpolation learning, and is able to characterize the double descent behavior by the unimodality of variance and monotonic decrease of bias. Besides, we also prove that the constant step-size SGD setting incurs no loss in convergence rate when compared to the exact minimum-norm interpolator, as a theoretical justification of using SGD in practice.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 50 of its 77 references that are in the map. First posted on arXiv 13 Oct 2021.

Builds on

50 of 77 references.

References · 50

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  3. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  5. 2018On Lazy Training in Differentiable Programmingcited by 671
  6. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  8. 2019Benign Overfitting in Linear Regressioncited by 544
  9. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  10. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  11. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  12. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
38 more
  1. 2019Two models of double descent for weak featurescited by 194
  2. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  3. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  4. 2021On the Origin of Implicit Regularization in Stochastic Gradient Descentcited by 183
  5. 2016Generalization Properties of Learning with Random Featurescited by 163
  6. 2019Linearized two-layers neural networks in high dimensioncited by 155
  7. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  8. 2020Generalisation error in learning with random features and the hidden manifold modelcited by 126
  9. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  10. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  11. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  12. 2020Rethinking Bias-Variance Trade-off for Generalization of Neural Networkscited by 107
  13. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 107
  14. 2020On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regressioncited by 97
  15. 2020Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regimecited by 95
  16. 2017A Random Matrix Approach to Neural Networkscited by 80
  17. 2020Understanding Double Descent Requires a Fine-Grained Bias-Variance Decompositioncited by 75
  18. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  19. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 69
  20. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  21. 2020Multiple Descent: Design Your Own Generalization Curvecited by 44
  22. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
  23. 2017Geometry of Optimization and Implicit Regularization in Deep Learningcited by 39
  24. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  25. 2020Kernel regression in high dimensions: Refined analysis beyond double descentcited by 39
  26. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  27. 2019Exact expressions for double descent and implicit regularization via surrogate random designcited by 35
  28. 2020Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regimecited by 35
  29. 2018Learning with SGD and Random Featurescited by 33
  30. 2021How rotational invariance of common kernels prevents generalization in high dimensionscited by 32
  31. 2019Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizescited by 29
  32. 2021Towards an Understanding of Benign Overfitting in Neural Networkscited by 29
  33. 2020What causes the test error? Going beyond bias-variance via ANOVAcited by 28
  34. 2020Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized modelscited by 26
  35. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 25
  36. 2019Double descent in the condition numbercited by 14
  37. 2021On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Modelscited by 13
  38. 2021On the Role of Optimization in Double Descent: A Least Squares Studycited by 7

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 3.

5 papers.

  1. 2024MUSO: Achieving Exact Machine Unlearning in Over-Parameterized Regimescited by 3
  2. 2024Learning Analysis of Kernel Ridgeless Regression with Asymmetric Kernel Learningcited by 2
  3. 2023Orthogonal Random Features: Explicit Forms and Sharp Inequalitiescited by 1
  4. 2024Probability Distribution Learning and Its Application in Deep Learningcited by 1
  5. 2023Gibbs-Based Information Criteria and the Over-Parameterized Regimecited by 0