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 15 Feb 2018
Subjects: cs.LG stat.ML
Author comments: 37 pages, 9 figures
Msc class: 90C25
Scited by: Daniel Suess