Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent

Built on

On tail probabilities for martingales
David A. Freedman · 1975
Earlier work this paper cites.
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method
Original
Simon Lacoste-Julien, Mark W. Schmidt, and Francis R. Bach · 2002
Earlier work this paper cites.
Concentration inequalities and model selection
Pascal Massart · 2007
Earlier work this paper cites.
On the generalization ability of online strongly convex programming algorithms
Sham M. Kakade and Ambuj Tewari · 2008
Earlier work this paper cites.

Making gradient descent optimal for strongly convex stochastic optimization
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan · 2012
Cited alongside, same era.
Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
Elad Hazan and Satyen Kale · 2014
Cited alongside, same era.
On the number of iterations for Dantzig–Wolfe optimization and packing-covering approximation algorithms
Philip Klein and Neal E Young · 2015
Cited alongside, same era.
Quasi-monotone subgradient methods for nonsmooth convex minimization
Yu. Nesterov and V. Shikhman · 2015
Cited alongside, same era.

Tight analyses for non-smooth stochastic gradient descent
Original
Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa · 2018
Later among the works it cites.
High-dimensional probability: An introduction with applications in data science
Roman Vershynin · 2018
Later among the works it cites.
Making the last iterate of SGD information theoretically optimal
Original
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli · 2019
Closest in time.