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:
- Gradient Descent: Ensuring steady progress and descent in the objective function.
- 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