On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants

Abstract

We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD). Remarkable recent progress has been made in this direction through development of algorithms like SAG, SVRG, SAGA. These algorithms have been shown to outperform SGD, both theoretically and empirically. However, asynchronous versions of these algorithms---a crucial requirement for modern large-scale applications---have not been studied. We bridge this gap by presenting a unifying framework for many variance reduction techniques. Subsequently, we propose an asynchronous algorithm grounded in our framework, and prove its fast convergence. An important consequence of our general approach is that it yields asynchronous versions of variance reduction algorithms such as SVRG and SAGA as a byproduct. Our method achieves near linear speedup in sparse settings common to machine learning. We demonstrate the empirical performance of our method through a concrete realization of asynchronous SVRG.

References in corpus (3)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems

Cited by in corpus (40)

• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Revisiting Distributed Synchronous SGD
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• AIDE: Fast and Communication Efficient Distributed Optimization
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Big Batch SGD: Automated Inference using Adaptive Batch Sizes
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Stochastic, Distributed and Federated Optimization for Machine Learning
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Communication trade-offs for synchronized distributed SGD with large step size
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
• Variance-Reduced Stochastic Learning under Random Reshuffling
• Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction
• Asynchronous Stochastic Proximal Optimization Algorithms with Variance Reduction
• Trading-off variance and complexity in stochastic gradient descent
• Asynchronous Stochastic Block Coordinate Descent with Variance Reduction
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Variance Reduction for Distributed Stochastic Gradient Descent
• Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction
• Stochastic Variance Reduced Riemannian Eigensolver
• k-SVRG: Variance Reduction for Large Scale Optimization
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Proximal SCOPE for Distributed Sparse Learning: Better Data Partition Implies Faster Convergence Rate
• Accelerated Variance Reduced Block Coordinate Descent
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
• High Throughput Synchronous Distributed Stochastic Gradient Descent
• Backpropagation with N-D Vector-Valued Neurons Using Arbitrary Bilinear Products
• IS-ASGD: Accelerating Asynchronous SGD using Importance Sampling
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Aggregated Gradient Langevin Dynamics
• Stochastic Doubly Robust Gradient