On the Double Descent of Random Features Models Trained with SGD

Abstract

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.

Accepted by NeurIPS22

References in corpus (15)

• Understanding deep learning requires rethinking generalization
• Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• On the Origin of Implicit Regularization in Stochastic Gradient Descent
• Universality Laws for High-Dimensional Learning with Random Features
• Understanding Double Descent Requires a Fine-Grained Bias-Variance Decomposition
• A Precise Performance Analysis of Learning with Random Features
• What causes the test error? Going beyond bias-variance via ANOVA
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression
• Towards an Understanding of Benign Overfitting in Neural Networks
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• Conditioning of Random Feature Matrices: Double Descent and Generalization Error
• On the Role of Optimization in Double Descent: A Least Squares Study
• On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Models
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression