Direct Acceleration of SAGA using Sampled Negative Momentum
  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.
