Katyusha: the first direct acceleration of stochastic gradient methods

By Zeyuan Allen-Zhu. 2016

624 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, methodology): “Katyusha (Allen-Zhu, 2016) (momentum) adaptive O(n+ √ n·β α )”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “Other related work includes algorithms specifically designed to achieve an accelerated rate of convergence in the stochastic setting [1, 19, 10].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “SVRG can be equipped with momentum (and negative momentum), leading to a new accelerated SVRG method known as Katyusha [3].”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, background): “We refer the interested reader to [1,26,35,36,41,95,96] and the references therein.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “SVRG can be equipped with momentum (and negative momentum), leading to a new accelerated SVRG method known as Katyusha [5].”
Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization (2020, methodology): “In case of SGD for ﬁnite sum problems, the momentum method Katyusha (Allen-Zhu, 2017) achieves the optimal rate; for enhancements, see also (Kovalev et al., 2020; Qian et al., 2019; Lan et al., 2019).”
Accelerating Stochastic Training for Over-parametrized Learning (2018, methodology): “There is a large body of work on combining stochastic gradient with momentum in order to achieve an accelerated convergence over SGD including (Jain et al., 2017; Kingma & Ba, 2014; Reddi et al., 2018; Allen-Zhu, 2017).”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “algorithms whose running time is favorable in n and d, but scale at best in √ κ [15, 22, 14, 4].”
Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice (2017, methodology): “Later, other accelerated incremental algorithms were proposed such as Katyusha (Allen-Zhu, 2017), or the method of Lan and Zhou (2017).”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, background): “, 2014) and their accelerated variants (ShalevShwartz and Zhang, 2013a; Frostig et al., 2015a; Lin et al., 2015; Defazio, 2016; Allen-Zhu, 2016) which offer near linear running time in the number of samples and condition number with log(n) passes over the dataset stored in memory.”
Variance Reduction for Matrix Games (2019, methodology): “Optimal variance-reduced finite-sum minimization methods improve the fast gradient method by the same factor [33, 1].”
Lower Bounds and Optimal Algorithms for Personalized Federated Learning (2020, methodology): “We present two different approaches to achieve so: AGD [38] (under the gradient oracle) and Katyusha [3] (under the summand gradient oracle).”