Katyusha: the first direct acceleration of stochastic gradient methods
Author:
Top Cited Papers
Open Access
- 19 June 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 18, 1200-1205
Abstract
Nesterov's momentum trick is famously known for accelerating gradient descent, and has been proven useful in building fast iterative algorithms. However, in the stochastic setting, counterexamples exist and prevent Nesterov's momentum from providing similar acceleration, even if the underlying problem is convex. We introduce Katyusha, a direct, primal-only stochastic gradient method to fix this issue. It has a provably accelerated convergence rate in convex (off-line) stochastic optimization. The main ingredient is Katyusha momentum, a novel "negative momentum" on top of Nesterov's momentum that can be incorporated into a variance-reduction based algorithm and speed it up. Since variance reduction has been successfully applied to a growing list of practical problems, our paper suggests that in each of such cases, one could potentially give Katyusha a hug.Keywords
All Related Versions
Funding Information
- Microsoft (0518584)
- NSF (CCF-1412958)
This publication has 13 references indexed in Scilit:
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal SettingIEEE Journal of Selected Topics in Signal Processing, 2015
- Nearly-Linear Time Positive LP Solver with Faster Convergence Rate2015
- Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine LearningSIAM Journal on Optimization, 2015
- Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel2014
- On the complexity analysis of randomized block-coordinate descent methodsMathematical Programming, 2014
- A Proximal Stochastic Gradient Method with Progressive Variance ReductionSIAM Journal on Optimization, 2014
- Efficiency of Coordinate Descent Methods on Huge-Scale Optimization ProblemsSIAM Journal on Optimization, 2012
- An optimal method for stochastic composite optimizationMathematical Programming, 2011
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Solving large scale linear prediction problems using stochastic gradient descent algorithms2004