Direct Acceleration of SAGA using Sampled Negative Momentum
This work addresses a gap in variance reduction methods for researchers in optimization, though it is incremental as it builds on existing SAGA techniques.
The paper tackles the lack of a directly accelerated variant of SAGA in stochastic optimization by proposing a method using Sampled Negative Momentum, achieving the best known oracle complexity for strongly convex problems.
Variance reduction is a simple and effective technique that accelerates convex (or non-convex) stochastic optimization. Among existing variance reduction methods, SVRG and SAGA adopt unbiased gradient estimators and are the most popular variance reduction methods in recent years. Although various accelerated variants of SVRG (e.g., Katyusha and Acc-Prox-SVRG) have been proposed, the direct acceleration of SAGA still remains unknown. In this paper, we propose a directly accelerated variant of SAGA using a novel Sampled Negative Momentum (SSNM), which achieves the best known oracle complexity for strongly convex problems (with known strong convexity parameter). Consequently, our work fills the void of directly accelerated SAGA.