A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates

Abstract

Recent years have witnessed exciting progress in the study of stochastic variance reduced gradient methods (e.g., SVRG, SAGA), their accelerated variants (e.g, Katyusha) and their extensions in many different settings (e.g., online, sparse, asynchronous, distributed). Among them, accelerated methods enjoy improved convergence rates but have complex coupling structures, which makes them hard to be extended to more settings (e.g., sparse and asynchronous) due to the existence of perturbation. In this paper, we introduce a simple stochastic variance reduced algorithm (MiG), which enjoys the best-known convergence rates for both strongly convex and non-strongly convex problems. Moreover, we also present its efficient sparse and asynchronous variants, and theoretically analyze its convergence rates in these settings. Finally, extensive experiments for various machine learning problems such as logistic regression are given to illustrate the practical improvement in both serial and asynchronous settings.

arXiv commentICML2018

References in corpus (4)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• Online Variance Reduction for Stochastic Optimization

Cited by in corpus (19)

• Lower Bounds and Optimal Algorithms for Personalized Federated Learning
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Recent theoretical advances in decentralized distributed convex optimization
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• A Generic Acceleration Framework for Stochastic Composite Optimization
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• On Biased Stochastic Gradient Estimation
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
• Numerical methods for the resource allocation problem in networks
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays
• Asynchronous Distributed Optimization with Stochastic Delays
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• Adaptive Weight Decay for Deep Neural Networks