Accelerating variance-reduced stochastic gradient methods

Derek Driggs, Matthias J. Ehrhardt, Carola-Bibiane SchönliebMath. Program 2022 · DOI · OpenReview

Stochastic Gradient Descent (SGD) is a cornerstone of large-scale optimization, favored for its low per-iteration cost. However, its convergence is often hampered by the variance of gradient estimates. While variance-reduction (VR) techniques like SVRG and SAGA have addressed this noise, achieving "acceleration"—the faster convergence rates characteristic of Nesterov’s methods—has remained complex. This paper introduces a universal framework that achieves optimal acceleration for a wide range of VR methods without the need for the "negative momentum" trick used in previous state-of-the-art algorithms like Katyusha.

The Challenge of Acceleration in Stochastic Optimization

The primary hurdle in combining variance reduction with acceleration is maintaining stability. Previous successful attempts relied on "negative momentum," which periodically anchors the algorithm to a point where the full gradient is known. While effective, this approach is algorithm-specific and difficult to generalize to methods like SAGA, which lack a natural anchor point. Furthermore, the theoretical analysis of negative momentum is notoriously intricate.

This research asks a fundamental question: Is negative momentum a necessary component for stochastic acceleration? By demonstrating that it is not, the authors simplify both the implementation and the theoretical understanding of accelerated stochastic methods.

A Universal Framework for Acceleration

The proposed framework is built upon the principle of Linear Coupling. This approach conceptualizes acceleration as a synergistic blend of two distinct optimization trajectories:

  1. Gradient Descent: Ensuring steady progress and descent in the objective function.
  2. Mirror Descent: Minimizing a "regret" term to maintain global convergence properties.

The MSEB Property: A Unified Interface

Central to this framework is the introduction of the Mean-Squared-Error and Bias (MSEB) property. This mathematical abstraction serves as a standardized interface for gradient estimators. It characterizes how the error and bias of an estimator evolve over time. Any stochastic gradient estimator—whether unbiased (like SAGA and SVRG) or biased and recursive (like SARAH and SARGE)—that satisfies the MSEB property can be integrated into the framework to achieve automatic acceleration.

This unified language allows for the first "direct" acceleration of SAGA that does not require doubling storage or computation per iteration, making it exceptionally efficient for problems with a large number of component functions ($n$).

Key Theoretical and Empirical Results

The framework provides rigorous convergence guarantees across different problem classes:

  • Non-Strongly Convex Problems: Achieves an optimal convergence rate of $O(n/T^2)$.
  • Strongly Convex Problems: Achieves a linear convergence rate of $O((1 + \sqrt{\mu/Ln})^{-T})$.

In the strongly convex setting, using a batch size of $b = n^{2/3}$, the accelerated SAGA and SVRG methods match the convergence rates of full-gradient accelerated methods while requiring significantly fewer gradient evaluations.

Empirical evaluations on ridge regression and LASSO tasks using datasets from the LIBSVM database (including australian, mushrooms, phishing, and ijcnn1) confirm the theoretical findings. The accelerated variants consistently outperformed their non-accelerated counterparts and performed comparably to Katyusha, despite the latter's more complex architecture.

Discussion and Future Directions

The paper demonstrates that negative momentum is essentially a specific form of variance control. By managing the mean-squared error and bias directly through the framework's parameters, acceleration emerges naturally.

While the framework is highly effective, some challenges remain. For biased methods like SARAH, the theoretical constants still show a less favorable dependence on $n$ compared to unbiased methods, likely due to the inherent difficulty of analyzing bias. Additionally, like most accelerated methods, performance is sensitive to parameter tuning. Future research may focus on identifying new gradient estimators with even smaller MSEB constants to further push the boundaries of stochastic optimization speed.

Summary updated

Abstract

Variance reduction is a crucial tool for improving the slow convergence of stochastic gradient descent. Only a few variance-reduced methods, however, have yet been shown to directly benefit from Nesterov’s acceleration techniques to match the convergence rates of accelerated gradient methods. Such approaches rely on “negative momentum”, a technique for further variance reduction that is generally specific to the SVRG gradient estimator. In this work, we show for the first time that negative momentum is unnecessary for acceleration and develop a universal acceleration framework that allows all popular variance-reduced methods to achieve accelerated convergence rates. The constants appearing in these rates, including their dependence on the number of functions n, scale with the mean-squared-error and bias of the gradient estimator. In a series of numerical experiments, we demonstrate that versions of SAGA, SVRG, SARAH, and SARGE using our framework significantly outperform non-accelerated versions and compare favourably with algorithms using negative momentum.
BibTeX
@article{driggs2022accelerating,
  author = {Derek Driggs and Matthias J. Ehrhardt and Carola-Bibiane Schönlieb},
  title = {{Accelerating variance-reduced stochastic gradient methods}},
  journal = {Math. Program.},
  year = {2022},
  doi = {10.1007/s10107-020-01566-2},
}
Figure