Asynchronous stochastic coordinate descent: parallelism and convergence properties
From MaRDI portal
Abstract: We describe an asynchronous parallel stochastic proximal coordinate descent algorithm for minimizing a composite objective function, which consists of a smooth convex function plus a separable convex function. In contrast to previous analyses, our model of asynchronous computation accounts for the fact that components of the unknown vector may be written by some cores simultaneously with being read by others. Despite the complications arising from this possibility, the method achieves a linear convergence rate on functions that satisfy an optimal 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 . We describe results from implementation on ten cores of a multicore processor.
Recommendations
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
- Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
- Accelerated, parallel, and proximal coordinate descent
Cites work
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training
- A coordinate gradient descent method for nonsmooth separable minimization
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- Accelerated, parallel, and proximal coordinate descent
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Augmented _1 and nuclear-norm models with a globally linearly convergent algorithm
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Convergence of sequential and asynchronous nonlinear paracontractions
- Degenerate Nonlinear Programming with a Quadratic Growth Condition
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Fast multiple-splitting algorithms for convex optimization
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- On asynchronous iterations
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- On the complexity analysis of randomized block-coordinate descent methods
- On the convergence of block coordinate descent type methods
- On the convergence of the coordinate descent method for convex differentiable minimization
- Parallel Gradient Distribution in Unconstrained Optimization
- Parallel Selective Algorithms for Nonconvex Big Data Optimization
- Parallel Variable Distribution
- Parallel coordinate descent methods for big data optimization
- Revisiting Asynchronous Linear Solvers
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Sparse Reconstruction by Separable Approximation
- Support-vector networks
Cited in
(58)- Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes
- Review of mathematical optimization in federated learning
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
- Stochastic block-coordinate gradient projection algorithms for submodular maximization
- scientific article; zbMATH DE number 6982318 (Why is no real title available?)
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- A class of parallel doubly stochastic algorithms for large-scale learning
- Accelerating Stochastic Composition Optimization
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- On unbounded delays in asynchronous parallel fixed-point algorithms
- An accelerated communication-efficient primal-dual optimization framework for structured machine learning
- An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces
- Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
- The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
- Parallel stochastic gradient algorithms for large-scale matrix completion
- The geometry of monotone operator splitting methods
- Asynchronous parallel algorithms for nonconvex optimization
- Coordinatewise descent methods for leading eigenvalue problem
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Coordinate-update algorithms can efficiently detect infeasible optimization problems
- Asynchronous fully-decentralized SGD in the cluster-based model
- On the convergence of asynchronous parallel iteration with unbounded delays
- scientific article; zbMATH DE number 7307474 (Why is no real title available?)
- Iteration complexity of a block coordinate gradient descent method for convex optimization
- Parallel block coordinate minimization with application to group regularized regression
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- Perturbed iterate analysis for asynchronous stochastic optimization
- Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters
- Sample complexity of sample average approximation for conditional stochastic optimization
- Decentralized stochastic subgradient projection optimization algorithms over random networks
- Using filter methods to guide convergence for ADMM, with applications to nonnegative matrix factorization problems
- Parameter estimation in a 3‐parameter p‐star random graph model
- Coordinate descent algorithms
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
- Distributed stochastic optimization with large delays
- Parallel block coordinate descent methods with identification strategies
- Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Markov chain block coordinate descent
- Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
- Zeroth-order feedback optimization for cooperative multi-agent systems
- A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer
- A new large-scale learning algorithm for generalized additive models
- Random block coordinate descent methods for linearly constrained optimization over networks
- Synchronous parallel block coordinate descent method for nonsmooth convex function minimization
- Fast convergence to non-isolated minima: four equivalent conditions for \({\mathrm{C}^2}\) functions
- Accelerate stochastic subgradient method by leveraging local growth condition
- DSCOVR: randomized primal-dual block coordinate algorithms for asynchronous distributed optimization
- The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth
This page was built for publication: Asynchronous stochastic coordinate descent: parallelism and convergence properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954387)
