Conditional Accelerated Lazy Stochastic Gradient Descent
This work provides a faster optimization method for machine learning practitioners dealing with large-scale convex problems, though it appears incremental as it builds on existing stochastic gradient descent frameworks.
The paper tackles the problem of stochastic gradient descent for convex optimization by introducing a conditional accelerated lazy algorithm that achieves an optimal convergence rate of O(1/ε²), improving over the previous O(1/ε⁴) rate from Hazan and Kale [2012].
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)$.