A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method

Built on

Smooth minimization of non-smooth functions
Y. Nesterov · 2005
Earlier work this paper cites.
Large margin methods for structured and interdependent output variables
I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun · 2006
Earlier work this paper cites.
Pegasos: Primal estimated sub-gradient solver for SVM
S. Shalev-Shwartz, Y. Singer, and N. Srebro · 2007
Earlier work this paper cites.
(Online) subgradient methods for structured prediction
N. Ratliff, J. A. Bagnell, and M. Zinkevich · 2007
Earlier work this paper cites.

Robust stochastic approximation approach to stochastic programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2009
Cited alongside, same era.
Pegasos: primal estimated sub-gradient solver for SVM
S. Shalev-Shwartz, Y. Singer, N. Srebro, and A. Cotter · 2010
Cited alongside, same era.
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization
E. Hazan and S. Kale · 2011
Cited alongside, same era.

Non-asymptotic analysis of stochastic approximation algorithms for machine learning
Original
F. Bach and E. Moulines · 2011
Later among the works it cites.
Making gradient descent optimal for strongly convex stochastic optimization
A. Rakhlin, O. Shamir, and K. Sridharan · 2012
Closest in time.
Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes
Original
O. Shamir and T. Zhang · 2012
Closest in time.