2018/06/28 by Kaiwen Zhou, Zhou, Kaiwen · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1806.11048
17 pages, 6 figures
openalex publication_date 2018/06/28 · arxiv created 2019/04/22 · arxiv updated 2019/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.