Katyusha: The First Direct Acceleration of Stochastic Gradient Methods

Understand

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 and finite-sum.
• We introduce $\mathtt{Katyusha}$, a direct, primal-only stochastic gradient method to fix this issue.
• In convex finite-sum stochastic optimization, $\mathtt{Katyusha}$ has an optimal accelerated convergence rate, and enjoys an optimal parallel linear speedup in the mini-batch setting.