An asynchronous parallel stochastic coordinate descent algorithm

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 (1/K) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is O(n1/2) in unconstrained optimization and O(n1/4) in the separable-constrained case, where n is the number of variables. We describe results from implementation on 40-core processors.

• Publication year

  2013

• Venue

  Journal of machine learning research

• Publication date

  2013-11-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.5555/2789272.2789282arXiv 1311.1873
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties

  2014cited by this paper
• DimmWitted: A Study of Main-Memory Statistical Analytics

  2014cited by this paper
• Introductory Lectures on Convex Optimization - A Basic Course

  2014cited by this paper
• Iteration complexity of feasible descent methods for convex optimization

  2014cited by this paper
• Stochastic Approximation approach to Stochastic Programming

  2013influential reference
• Parallel and distributed sparse optimization

  2013cited by this paper
• On the complexity analysis of randomized block-coordinate descent methods

  2013cited by this paper
• Revisiting Asynchronous Linear Solvers: Provable Convergence Rate through Randomization

  2013cited by this paper
• A Randomized Asynchronous Linear Solver with Provable Convergence Rate

  2013cited by this paper
• Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

  2013cited by this paper
• On the Convergence of Block Coordinate Descent Type Methods

  2013cited by this paper
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent

  2013cited by this paper
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes

  2012cited by this paper
• Accelerated Block-coordinate Relaxation for Regularized Optimization

  2012cited by this paper
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems

  2012cited by this paper
• Feature Clustering for Accelerating Parallel Coordinate Descent

  2012cited by this paper
• Parallel coordinate descent methods for big data optimization

  2012cited by this paper
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

  2011cited by this paper
• Distributed delayed stochastic optimization

  2011influential reference
• LIBSVM: A library for support vector machines

  2011influential reference
• Better Mini-Batch Algorithms via Accelerated Gradient Methods

  2011cited by this paper
• Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

  2011influential reference
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers

  2011cited by this paper
• A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training

  2010cited by this paper
• Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

  2010cited by this paper
• Fast Multiple-Splitting Algorithms for Convex Optimization

  2009cited by this paper
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems

  2009cited by this paper
• A coordinate gradient descent method for nonsmooth separable minimization

  2008cited by this paper
• Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization

  2001cited by this paper
• Partial Solutions Manual Parallel and Distributed Computation : Numerical Methods

  1997influential reference
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Parallel Gradient Distribution in Unconstrained Optimization

  1995cited by this paper
• Support-Vector Networks

  1995cited by this paper
• Parallel Variable Distribution

  1994cited by this paper
• On the convergence of the coordinate descent method for convex differentiable minimization

  1992cited by this paper

• Global Convergence to Nash Equilibrium in Nonconvex General-Sum Games under the $n$-Sided PL Condition

  2026cites this paper
• Asynchronous Stochastic Gradient Descent with Model Quantization

  2025cites this paper
• Random Descent Steps in a Probability Maximization Scheme

  2025cites this paper
• CAC: An asynchronous non-blocking consistency model with bounded staleness for distributed machine learning

  2025cites this paper
• A simulation-based approach to estimate joint model of longitudinal and event–time data with many missing longitudinal observations

  2025cites this paper
• Toward whole-genome inference of polygenic scores with fast and memory-efficient algorithms

  2025cites this paper
• Randomized coordinate gradient descent almost surely escapes strict saddle points

  2025cites this paper
• A Fast Algorithm for the Finite Expression Method in Learning Dynamics on Complex Networks

  2024cites this paper
• Asynchronous Block Parallel Policy Optimization for the Linear Quadratic Regulator*

  2024influential citation
• Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients

  2024cites this paper
• Difference Between Cyclic and Distributed Approach in Stochastic Optimization for Multi-agent System

  2024cites this paper
• Shuffling-type gradient method with bandwidth-based step sizes for finite-sum optimization

  2024cites this paper
• Tree Network Design for Faster Distributed Machine Learning Process with Distributed Dual Coordinate Ascent

  2024cites this paper
• Loss Landscape Characterization of Neural Networks without Over-Parametrization

  2024cites this paper
• Block Coordinate Descent Methods for Structured Nonconvex Optimization with Nonseparable Constraints: Optimality Conditions and Global Convergence

  2024cites this paper
• Asynchronous Parallel Large-Scale Gaussian Process Regression

  2024cites this paper
• Distributed Functional Compression for Independent Component Analysis in Wireless Networks

  2024cites this paper
• Convex and Bilevel Optimization for Neuro-Symbolic Inference and Learning

  2024cites this paper
• Natural Light Can Also be Dangerous: Traffic Sign Misinterpretation Under Adversarial Natural Light Attacks

  2024cites this paper
• Accelerated Markov Chain Monte Carlo Using Adaptive Weighting Scheme

  2024cites this paper
• Parallelization Strategies for the Randomized Kaczmarz Algorithm on Large-Scale Dense Systems

  2024cites this paper
• Distributed Dual Coordinate Ascent With Imbalanced Data on a General Tree Network

  2023cites this paper
• On the Lower Bound of Minimizing Polyak-Łojasiewicz functions

  2023cites this paper
• An Adaptive Load Balancing Strategy for Distributed Machine Learning

  2023cites this paper
• Coordinate-Update Algorithms can Efficiently Detect Infeasible Optimization Problems

  2023cites this paper
• FedDec: Peer-to-peer Aided Federated Learning

  2023cites this paper
• A New Machine-Learning Extracting Approach to Construct a Knowledge Base: A Case Study on Global Stromatolites over Geological Time

  2023influential citation
• Theoretical Analysis of Impact of Delayed Updates on Decentralized Federated Learning

  2023cites this paper
• Delay-agnostic Asynchronous Coordinate Update Algorithm

  2023influential citation
• Non-ergodic linear convergence property of the delayed gradient descent under the strongly convexity and the Polyak-Łojasiewicz condition

  2023cites this paper
• Open-Ended Online Learning for Autonomous Visual Perception

  2023cites this paper
• Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization

  2023cites this paper
• Distributed Adaptive Greedy Quasi-Newton Methods with Explicit Non-asymptotic Convergence Bounds

  2023cites this paper
• Block-Coordinate Methods and Restarting for Solving Extensive-Form Games

  2023cites this paper
• Stochastic Optimization under Hidden Convexity

  2023cites this paper
• Momentum-driven adaptive synchronization model for distributed DNN training on HPC clusters

  2022cites this paper
• Variance reduction for root-finding problems

  2022influential citation
• Flexible Vertical Federated Learning With Heterogeneous Parties

  2022cites this paper
• Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning

  2022cites this paper
• Convergence analysis of asynchronous stochastic recursive gradient algorithms

  2022cites this paper
• Democratizing Machine Learning: Resilient Distributed Learning with Heterogeneous Participants

  2022cites this paper
• On Generalization Bounds for Deep Networks Based on Loss Surface Implicit Regularization

  2022cites this paper
• Optimizing the Performative Risk under Weak Convexity Assumptions

  2022cites this paper
• An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces

  2022cites this paper
• Optimal convergence rates of totally asynchronous optimization

  2022cites this paper
• A dual approach for federated learning

  2022cites this paper
• Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functions

  2022cites this paper
• A Machine Learning Framework for Distributed Functional Compression over Wireless Channels in IoT

  2022cites this paper
• Convergence of gradient descent for deep neural networks

  2022cites this paper
• Spread: Decentralized Model Aggregation for Scalable Federated Learning

  2022cites this paper
• Stochastic Second-Order Methods Provably Beat SGD For Gradient-Dominated Functions

  2022cites this paper
• Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization

  2022cites this paper
• Gradient Descent: Robustness to Adversarial Corruption

  2022cites this paper
• A Unifying Framework for Variance-Reduced Algorithms for Findings Zeroes of Monotone operators

  2022cites this paper
• Escaping From Saddle Points Using Asynchronous Coordinate Gradient Descent

  2022influential citation
• Asynchronous Gradient Play in Zero-Sum Multi-agent Games

  2022influential citation
• Communication-efficient Distributed Learning for Large Batch Optimization

  2022cites this paper
• On the Lower Bound of Minimizing Polyak-{\L}ojasiewicz Functions

  2022cites this paper
• Delay-adaptive step-sizes for asynchronous learning

  2022influential citation
• Follow the flow: Proximal flow inspired multi-step methods

  2022cites this paper
• Efficient and Light-Weight Federated Learning via Asynchronous Distributed Dropout

  2022influential citation
• On the Parallelization Upper Bound for Asynchronous Stochastic Gradients Descent in Non-convex Optimization

  2022cites this paper
• Staleness and Stagglers in Distibuted Deep Image Analytics

  2021cites this paper
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees

  2021cites this paper
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback

  2021cites this paper
• Efficient greedy coordinate descent via variable partitioning

  2021cites this paper
• Learning Linear Models Using Distributed Iterative Hessian Sketching

  2021cites this paper
• Efficient Asynchronous Semi-Stochastic Block Coordinate Descent Methods for Large-Scale SVD

  2021cites this paper
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent

  2021cites this paper
• ASYNC-RED: A PROVABLY CONVERGENT ASYN-

  2021cites this paper
• Sample Contribution Pattern Based Big Data Mining Optimization Algorithms

  2021cites this paper
• Online Learning with Optimism and Delay

  2021cites this paper
• Cyclic Coordinate Dual Averaging with Extrapolation

  2021cites this paper
• Optimal No-Regret Learning in Strongly Monotone Games with Bandit Feedback

  2021cites this paper
• Coordinate Descent Methods for DC Minimization

  2021cites this paper
• Solving large-scale support vector ordinal regression with asynchronous parallel coordinate descent algorithms

  2021cites this paper
• On the global convergence of randomized coordinate gradient descent for non-convex optimization

  2021cites this paper
• Totally Asynchronous Primal-Dual Convex Optimization in Blocks

  2021cites this paper
• Effective and Efficient Learning at Scale

  2020cites this paper
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization

  2020cites this paper
• A Black-Box Fork-Join Latency Prediction Model for Data-Intensive Applications

  2020cites this paper
• Asynchronous Lagrangian scenario decomposition

  2020cites this paper
• Context-aware, preference-based vehicle routing

  2020cites this paper
• Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglers

  2020cites this paper
• A class of smooth exact penalty function methods for optimization problems with orthogonality constraints

  2020cites this paper
• Asynchronous and Parallel Distributed Pose Graph Optimization

  2020cites this paper
• Asynchronous parallel adaptive stochastic gradient methods

  2020cites this paper
• Anytime Minibatch: Exploiting Stragglers in Online Distributed Optimization

  2020cites this paper
• An asynchronous distributed and scalable generalized Nash equilibrium seeking algorithm for strongly monotone games

  2020cites this paper
• Parallel and distributed asynchronous adaptive stochastic gradient methods

  2020cites this paper
• Resolving learning rates adaptively by locating stochastic non-negative associated gradient projection points using line searches

  2020cites this paper
• A parameter-level parallel optimization algorithm for large-scale spatio-temporal data mining

  2020cites this paper
• Tera-scale coordinate descent on GPUs

  2020cites this paper
• Building a Personally Identifiable Information Recognizer in a Privacy Preserved Manner Using Automated Annotation and Federated Learning

  2020cites this paper
• Carath\'eodory Sampling for Stochastic Gradient Descent

  2020cites this paper
• High-Dimensional Nonconvex Stochastic Optimization by Doubly Stochastic Successive Convex Approximation

  2020cites this paper
• Asynchronous Stochastic Gradient Descent over Decentralized Datasets

  2020cites this paper
• Asynchronous Parallel Stochastic Quasi-Newton Methods

  2020cites this paper
• DONE: Distributed Newton-type Method for Federated Edge Learning

  2020cites this paper
• Async-RED: A Provably Convergent Asynchronous Block Parallel Stochastic Method using Deep Denoising Priors

  2020cites this paper