Title: Conditional Accelerated Lazy Stochastic Gradient Descent,
Abstract: 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)$.