Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction

Abstract

In the era of big data, optimizing large scale machine learning problems becomes a challenging task and draws significant attention. Asynchronous optimization algorithms come out as a promising solution. Recently, decoupled asynchronous proximal stochastic gradient descent (DAP-SGD) is proposed to minimize a composite function. It is claimed to be able to off-loads the computation bottleneck from server to workers by allowing workers to evaluate the proximal operators, therefore, server just need to do element-wise operations. However, it still suffers from slow convergence rate because of the variance of stochastic gradient is nonzero. In this paper, we propose a faster method, decoupled asynchronous proximal stochastic variance reduced gradient descent method (DAP-SVRG). We prove that our method has linear convergence for strongly convex problem. Large-scale experiments are also conducted in this paper, and results demonstrate our theoretical analysis.

References in corpus (10)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Slow Learners are Fast
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• An Asynchronous Parallel Randomized Kaczmarz Algorithm
• Distributed Mini-Batch SDCA
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Faster Asynchronous SGD
• Make Workers Work Harder: Decoupled Asynchronous Proximal Stochastic Gradient Descent

Cited by in corpus (3)

• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Asynchronous Stochastic Block Coordinate Descent with Variance Reduction
• Proximal SCOPE for Distributed Sparse Learning: Better Data Partition Implies Faster Convergence Rate