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

Aditya Varre, Loucas Pillaud-Vivien, Nicolas Flammarion

Type: Preprint

Publication Date: 2021-01-01

Citations: 5

DOI: https://doi.org/10.48550/arxiv.2102.03183

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Last iterate convergence of SGD for Least-Squares in the Interpolation regime	2021	Aditya Varre Loucas Pillaud-Vivien Nicolas Flammarion
+	Minimum $\ell_{1}$-norm interpolators: Precise asymptotics and multiple descent	2021	Yue Li Yuting Wei
+	Benign Overfitting of Constant-Stepsize SGD for Linear Regression	2021	Difan Zou Jingfeng Wu Vladimir Braverman Quanquan Gu Sham M. Kakade
+	A finite sample analysis of the benign overfitting phenomenon for ridge function estimation	2020	Emmanuel Caron Stéphane Chrétien
+	On the Double Descent of Random Features Models Trained with SGD	2021	Fanghui Liu Johan A. K. Suykens Volkan Cevher
+	A finite sample analysis of the double descent phenomenon for ridge function estimation.	2020	Emmanuel Caron Stéphane Chrétien
+	Aiming towards the minimizers: fast convergence of SGD for overparametrized problems	2023	Chaoyue Liu Dmitriy Drusvyatskiy Mikhail Belkin Damek Davis Yi-An Ma
+	ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm	2020	Chris Junchi Li Wenlong Mou Martin J. Wainwright Michael I. Jordan
+	Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model	2020	Raphaël Berthier Francis Bach Pierre Gaillard
+ PDF Chat	Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model	2020	Raphaël Berthier Francis Bach Pierre Gaillard
+	A Continuous-Time View of Early Stopping for Least Squares	2018	Alnur Ali J. Zico Kolter Ryan J. Tibshirani
+ PDF Chat	A finite sample analysis of the benign overfitting phenomenon for ridge function estimation	2021	Emmanuel Caron Stéphane Chrétien
+	A Continuous-Time View of Early Stopping for Least Squares Regression	2019	Alnur Ali J. Zico Kolter Ryan J. Tibshirani
+	A Continuous-Time View of Early Stopping for Least Squares Regression	2018	Alnur Ali J. Zico Kolter Ryan J. Tibshirani
+	Surprises in high-dimensional ridgeless least squares interpolation	2022	Trevor Hastie Andrea Montanari Saharon Rosset Ryan J. Tibshirani
+	On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels	2019	Tengyuan Liang Alexander Rakhlin Xiyu Zhai
+	The distribution of Ridgeless least squares interpolators	2023	Qiyang Han Xiaocong Xu
+	On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels	2019	Tengyuan Liang Alexander Rakhlin Xiyu Zhai
+	Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime	2022	Difan Zou Jingfeng Wu Vladimir Braverman Quanquan Gu Sham M. Kakade
+	Non-parametric Stochastic Approximation with Large Step sizes	2014	Aymeric Dieuleveut Francis Bach

Works That Cite This (5)

Action	Title	Year	Authors
+	On the Double Descent of Random Features Models Trained with SGD	2021	Fanghui Liu Johan A. K. Suykens Volkan Cevher
+	Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime	2021	Hugo Cui Bruno Loureiro Florent Krząkała Lenka Zdeborová
+ PDF Chat	Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime*	2022	Hugo Cui Bruno Loureiro Florent Krząkała Lenka Zdeborová
+	Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting, and Regularization	2022	Ke Wang Christos Thrampoulidis
+	Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression	2021	Jingfeng Wu Difan Zou Vladimir Braverman Quanquan Gu Sham M. Kakade

Works Cited by This (13)

Action	Title	Year	Authors
+ PDF Chat	A lecture on the averaging process	2012	David Aldous Daniel Lanoue
+ PDF Chat	Optimal Rates for the Regularized Least-Squares Algorithm	2006	Andrea Caponnetto Ernesto De Vito
+	On exponential convergence of SGD in non-convex over-parametrized learning	2018	Raef Bassily Mikhail Belkin Siyuan Ma
+	Nonparametric stochastic approximation with large step-sizes	2016	Aymeric Dieuleveut Francis Bach
+	Tight analyses for non-smooth stochastic gradient descent	2019	Nicholas J. A. Harvey Christopher Liaw Yaniv Plan Sikander Randhawa
+	The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares	2019	Rong Ge Sham M. Kakade Rahul Kidambi Praneeth Netrapalli
+	Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping.	2020	Nicole Mücke Enrico Reiss
+	Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation	2019	Si Yi Meng Sharan Vaswani Issam Laradji Mark Schmidt Simon Lacoste-Julien
+	Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition	2013	Mark Schmidt Nicolas Le Roux
+	Online Learning as Stochastic Approximation of Regularization Paths: Optimality and Almost-Sure Convergence	2014	Pierre Tarrès Yuan Yao