Direct Acceleration of SAGA using Sampled Negative Momentum

Abstract

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.

17 pages, 6 figures

Cited by in corpus (12)

• Lower Bounds and Optimal Algorithms for Personalized Federated Learning
• Recent theoretical advances in decentralized distributed convex optimization
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• A Generic Acceleration Framework for Stochastic Composite Optimization
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters