2022-06-28-li22a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm	We study the problem of solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms. We devise a novel algorithm, referred to as \emph{Recursive One-Over-T SGD} (ROOT-SGD), based on an easily implementable, recursive averaging of past stochastic gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an asymptotic sense. On the nonasymptotic side, we prove risk bounds on the last iterate of ROOT-SGD with leading-order terms that match the optimal statistical risk with a unity pre-factor, along with a higher-order term that scales at the sharp rate of $O(n^{-3/2})$ under the Lipschitz condition on the Hessian matrix. On the asymptotic side, we show that when a mild, one-point Hessian continuity condition is imposed, the rescaled last iterate of (multi-epoch) ROOT-SGD converges asymptotically to a Gaussian limit with the Cramér-Rao optimal asymptotic covariance, for a broad range of step-size choices.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	li22a	0	ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm	909	981	909-981	909	false	Li, Chris Junchi and Mou, Wenlong and Wainwright, Martin and Jordan, Michael	given family Chris Junchi Li given family Wenlong Mou given family Martin Wainwright given family Michael Jordan	2022-06-28		Proceedings of Thirty Fifth Conference on Learning Theory	178	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v178/li22a/li22a.pdf