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}{{\epsilon }^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}{{\epsilon }^4}\right)$.

37 pages, 9 figures

References in corpus (2)

• On the Equivalence between Herding and Conditional Gradient Algorithms
• Lazifying Conditional Gradient Algorithms

Cited by in corpus (10)

• Blended Conditional Gradients: the unconditioning of conditional gradients
• Stochastic Conditional Gradient++
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
• Deep Neural Network Training with Frank-Wolfe
• Zeroth-Order Stochastic Block Coordinate Type Methods for Nonconvex Optimization
• Efficient Projection-Free Online Convex Optimization with Membership Oracle
• Locally Accelerated Conditional Gradients
• Backtracking linesearch for conditional gradient sliding
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
• Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization