Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Abstract

Motivated by the recent successes of neural networks that have the ability to fit the data perfectly and generalize well, we study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $⟨{\theta }_{\ast },\varphi (X)⟩=Y$, where $\varphi (X)$ stands for a possibly infinite dimensional non-linear feature map. To solve this problem, we consider the estimator given by the last iterate of stochastic gradient descent (SGD) with constant step-size. In this context, our contribution is two fold: (i) from a (stochastic) optimization perspective, we exhibit an archetypal problem where we can show explicitly the convergence of SGD final iterate for a non-strongly convex problem with constant step-size whereas usual results use some form of average and (ii) from a statistical perspective, we give explicit non-asymptotic convergence rates in the over-parameterized setting and leverage a fine-grained parameterization of the problem to exhibit polynomial rates that can be faster than $O(1/T)$. The link with reproducing kernel Hilbert spaces is established.

arXiv comment23 pages, 1 figure, 1 Appendix

References in corpus (8)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• On exponential convergence of SGD in non-convex over-parametrized learning
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Stochastic Composite Least-Squares Regression with convergence rate O(1/n)
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping

Cited by in corpus (3)

• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• On the Double Descent of Random Features Models Trained with SGD
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression