Asynchronous Stochastic Block Coordinate Descent with Variance Reduction

Abstract

Asynchronous parallel implementations for stochastic optimization have received huge successes in theory and practice recently. Asynchronous implementations with lock-free are more efficient than the one with writing or reading lock. In this paper, we focus on a composite objective function consisting of a smooth convex function $f$ and a block separable convex function, which widely exists in machine learning and computer vision. We propose an asynchronous stochastic block coordinate descent algorithm with the accelerated technology of variance reduction (AsySBCDVR), which are with lock-free in the implementation and analysis. AsySBCDVR is particularly important because it can scale well with the sample size and dimension simultaneously. We prove that AsySBCDVR achieves a linear convergence rate when the function $f$ is with the optimal strong convexity property, and a sublinear rate when $f$ is with the general convexity. More importantly, a near-linear speedup on a parallel system with shared memory can be obtained.

References in corpus (8)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Asynchronous Stochastic Proximal Optimization Algorithms with Variance Reduction
• Distributed Asynchronous Dual Free Stochastic Dual Coordinate Ascent
• Decoupled Asynchronous Proximal Stochastic Gradient Descent with Variance Reduction

Cited by in corpus (5)

• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
• Privacy-Preserving Asynchronous Federated Learning Algorithms for Multi-Party Vertically Collaborative Learning
• Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Quadruply Stochastic Gradients for Large Scale Nonlinear Semi-Supervised AUC Optimization