An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
From MaRDI portal
Publication:5502117
zbMATH Open1337.68286arXiv1311.1873MaRDI QIDQ5502117FDOQ5502117
Authors: Ji Liu, Stephen J. Wright, Christopher Re, Victor Bittorf, Srikrishna Sridhar 
Publication date: 17 August 2015
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.
Full work available at URL: https://arxiv.org/abs/1311.1873
Recommendations
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- Parallel and distributed asynchronous adaptive stochastic gradient methods
- Asynchronous parallel algorithms for nonconvex optimization
- On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
- On the complexity of parallel coordinate descent
- Accelerated, parallel, and proximal coordinate descent
Cited In (60)
- Distributed adaptive greedy quasi-Newton methods with explicit non-asymptotic convergence bounds
- Non-ergodic linear convergence property of the delayed gradient descent under the strongly convexity and the Polyak-Łojasiewicz condition
- Asynchronous fully-decentralized SGD in the cluster-based model
- Cyclic Coordinate Dual Averaging with Extrapolation
- Accelerate stochastic subgradient method by leveraging local growth condition
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- Distributed Learning with Sparse Communications by Identification
- Stochastic block-coordinate gradient projection algorithms for submodular maximization
- Parallel coordinate descent methods for big data optimization
- On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
- A class of parallel doubly stochastic algorithms for large-scale learning
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- On the rates of convergence of parallelized averaged stochastic gradient algorithms
- A generic coordinate descent solver for non-smooth convex optimisation
- Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- Optimization methods for large-scale machine learning
- An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces
- On unbounded delays in asynchronous parallel fixed-point algorithms
- The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- Parallel stochastic gradient algorithms for large-scale matrix completion
- Decentralized consensus algorithm with delayed and stochastic gradients
- Parallel and distributed asynchronous adaptive stochastic gradient methods
- Resolving learning rates adaptively by locating stochastic non-negative associated gradient projection points using line searches
- Coordinatewise descent methods for leading eigenvalue problem
- Parallel stochastic Newton method
- Asynchronous parallel algorithms for nonconvex optimization
- Accelerated, parallel, and proximal coordinate descent
- Convergence rates for the stochastic gradient descent method for non-convex objective functions
- Linear convergence of first order methods for non-strongly convex optimization
- Asynchronous Gradient Push
- On the convergence of asynchronous parallel iteration with unbounded delays
- Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
- Asynchronous Lagrangian scenario decomposition
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
- Perturbed iterate analysis for asynchronous stochastic optimization
- A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
- Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training
- Redundancy techniques for straggler mitigation in distributed optimization and learning
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- Coordinate descent algorithms
- Variance reduction for root-finding problems
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- A class of smooth exact penalty function methods for optimization problems with orthogonality constraints
- A parallel bundle framework for asynchronous subspace optimization of nonsmooth convex functions
- Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
- Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version
- A framework for parallel second order incremental optimization algorithms for solving partially separable problems
- Delay and cooperation in nonstochastic bandits
- A distributed quantile estimation algorithm of heavy-tailed distribution with massive datasets
- Distributed block coordinate descent for minimizing partially separable functions
- Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints
- An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation
- Randomized block proximal damped Newton method for composite self-concordant minimization
Uses Software
This page was built for publication: An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502117)
