# Conditional Accelerated Lazy Stochastic Gradient Descent

In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate $O\left(\frac{1}{\varepsilon^2}\right)$ improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan and Kale [2012] with convergence rate $O\left(\frac{1}{\varepsilon^4}\right)$.
Submitted 16 Mar 2017 to Learning [cs.LG]
Published 20 Mar 2017
Updated 24 Mar 2017
Subjects: cs.LG stat.ML
Author comments: 33 pages, 9 figures
Msc class: 90C25
http://arxiv.org/abs/1703.05840
http://arxiv.org/pdf/1703.05840.pdf
Scited by: Daniel Suess