ASVRG: Accelerated Proximal SVRG

Abstract

This paper proposes an accelerated proximal stochastic variance reduced gradient (ASVRG) method, in which we design a simple and effective momentum acceleration trick. Unlike most existing accelerated stochastic variance reduction methods such as Katyusha, ASVRG has only one additional variable and one momentum parameter. Thus, ASVRG is much simpler than those methods, and has much lower per-iteration complexity. We prove that ASVRG achieves the best known oracle complexities for both strongly convex and non-strongly convex objectives. In addition, we extend ASVRG to mini-batch and non-smooth settings. We also empirically verify our theoretical results and show that the performance of ASVRG is comparable with, and sometimes even better than that of the state-of-the-art stochastic methods.

arXiv comment32 pages, 3 figures

Cited by in corpus (10)

• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
• On Biased Stochastic Gradient Estimation
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization
• Proximal and Federated Random Reshuffling
• A Primal-Dual Framework for Decentralized Stochastic Optimization
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters