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
- 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 Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- 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
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- 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 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
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- Parallel coordinate descent methods for big data optimization
- Parallel Gradient Distribution in Unconstrained Optimization
- Parallel Selective Algorithms for Nonconvex Big Data Optimization
- Parallel Variable Distribution
- 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
(59)- On unbounded delays in asynchronous parallel fixed-point algorithms
- Stochastic block-coordinate gradient projection algorithms for submodular maximization
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- Synchronous parallel block coordinate descent method for nonsmooth convex function minimization
- Asynchronous parallel algorithms for nonconvex optimization
- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- New analysis of linear convergence of gradient-type methods via unifying error bound conditions
- Markov chain block coordinate descent
- An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
- Coordinate descent algorithms
- Parallel block coordinate minimization with application to group regularized regression
- Parallel stochastic gradient algorithms for large-scale matrix completion
- Random block coordinate descent methods for linearly constrained optimization over networks
- On the convergence of asynchronous parallel iteration with unbounded delays
- Zeroth-order feedback optimization for cooperative multi-agent systems
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
- Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
- Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters
- scientific article; zbMATH DE number 6982318 (Why is no real title available?)
- Perturbed iterate analysis for asynchronous stochastic optimization
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- DSCOVR: randomized primal-dual block coordinate algorithms for asynchronous distributed optimization
- Accelerating Stochastic Composition Optimization
- A class of parallel doubly stochastic algorithms for large-scale learning
- Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes
- Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays
- An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces
- A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer
- Sample complexity of sample average approximation for conditional stochastic optimization
- Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
- scientific article; zbMATH DE number 7307474 (Why is no real title available?)
- The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
- Coordinatewise descent methods for leading eigenvalue problem
- The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth
- Accelerate stochastic subgradient method by leveraging local growth condition
- Iteration complexity of a block coordinate gradient descent method for convex optimization
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- An accelerated communication-efficient primal-dual optimization framework for structured machine learning
- Distributed stochastic optimization with large delays
- Asynchronous fully-decentralized SGD in the cluster-based model
- Parameter estimation in a 3‐parameter p‐star random graph model
- A new large-scale learning algorithm for generalized additive models
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
- The geometry of monotone operator splitting methods
- Decentralized stochastic subgradient projection optimization algorithms over random networks
- Fast convergence to non-isolated minima: four equivalent conditions for \({\mathrm{C}^2}\) functions
- Review of mathematical optimization in federated learning
- Coordinate-update algorithms can efficiently detect infeasible optimization problems
- Using filter methods to guide convergence for ADMM, with applications to nonnegative matrix factorization problems
- Parallel block coordinate descent methods with identification strategies
- Asynchronous distributed generalized Nash equilibrium computation for aggregative games with coupling constraint
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)
