An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
arXiv:1311.1873
Abstract
We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential strong convexity property and a sublinear rate () on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is in unconstrained optimization and in the separable-constrained case, where is the number of variables. We describe results from implementation on 40-core processors.
References in corpus (7)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Better Mini-Batch Algorithms via Accelerated Gradient Methods
- Parallel Coordinate Descent Methods for Big Data Optimization
- Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
- DimmWitted: A Study of Main-Memory Statistical Analytics
- Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
Cited by in corpus (35)
- Staleness-aware Async-SGD for Distributed Deep Learning
- On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
- Coordinate Friendly Structures, Algorithms and Applications
- Adding vs. Averaging in Distributed Primal-Dual Optimization
- Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
- Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
- Asynchronous and Parallel Distributed Pose Graph Optimization
- A Cost-based Optimizer for Gradient Descent Optimization
- PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
- An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
- Asynchronous stochastic convex optimization
- Factorized Q-Learning for Large-Scale Multi-Agent Systems
- A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
- An Asynchronous, Decentralized Solution Framework for the Large Scale Unit Commitment Problem
- A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
- Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
- Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers
- DimmWitted: A Study of Main-Memory Statistical Analytics
- Matrix Exponential Learning Schemes with Low Informational Exchange
- Asynchronous Complex Analytics in a Distributed Dataflow Architecture
- On Data Dependence in Distributed Stochastic Optimization
- Stochastic Gradient Descent on Highly-Parallel Architectures
- Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
- A machine-compiled macroevolutionary history of Phanerozoic life
- SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
- On generalization bounds for deep networks based on loss surface implicit regularization
- SCOPE: Scalable Composite Optimization for Learning on Spark
- Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
- Parallel and distributed asynchronous adaptive stochastic gradient methods
- A Survey on Large-scale Machine Learning
- Randomized block proximal damped Newton method for composite self-concordant minimization
- A Linearly Convergent Doubly Stochastic Gauss-Seidel Algorithm for Solving Linear Equations and A Certain Class of Over-Parameterized Optimization Problems
- On the global convergence of randomized coordinate gradient descent for non-convex optimization
- Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
- Online Learning with Optimism and Delay