Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization

Abstract

We provide the first theoretical analysis on the convergence rate of the asynchronous stochastic variance reduced gradient (SVRG) descent algorithm on non-convex optimization. Recent studies have shown that the asynchronous stochastic gradient descent (SGD) based algorithms with variance reduction converge with a linear convergent rate on convex problems. However, there is no work to analyze asynchronous SGD with variance reduction technique on non-convex problem. In this paper, we study two asynchronous parallel implementations of SVRG: one is on a distributed memory system and the other is on a shared memory system. We provide the theoretical analysis that both algorithms can obtain a convergence rate of $O(1/T)$, and linear speed up is achievable if the number of workers is upper bounded. V1,v2,v3 have been withdrawn due to reference issue, please refer the newest version v4.

V1,v2,v3 have been withdrawn due to reference issue, because arXiv policy, we can't delete them. Please refer the newest version v4

References in corpus (12)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• 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
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Stochastic Variance Reduction for Nonconvex Optimization
• Slow Learners are Fast
• Variance Reduction for Faster Non-Convex Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• Asynchronous Stochastic Block Coordinate Descent with Variance Reduction
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction

Cited by in corpus (9)

• Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction
• Asynchronous Stochastic Block Coordinate Descent with Variance Reduction
• Distributed Deep Learning with Event-Triggered Communication
• Accelerating Asynchronous Algorithms for Convex Optimization by Momentum Compensation
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
• Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction
• An Asynchronous Distributed Framework for Large-scale Learning Based on Parameter Exchanges