An Asynchronous Parallel Stochastic Coordinate Descent Algorithm

MaRDI QIDQ5502117zbMATH OpenFDO

Authors Ji Liu, Stephen J. Wright, Christopher Re, Victor Bittorf, Srikrishna Sridhar

Publication date 17 August 2015

Full work available at URL https://arxiv.org/abs/1311.1873, http://jmlr.csail.mit.edu/papers/v16/liu15a.html

zbMATH Keywords

asynchronous parallel optimizationstochastic coordinate descent

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Convex programming (90C25)

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

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

(62)

• 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
• Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training
• A distributed quantile estimation algorithm of heavy-tailed distribution with massive datasets
• Resolving learning rates adaptively by locating stochastic non-negative associated gradient projection points using line searches
• Asynchronous parallel algorithms for nonconvex optimization
• Worst-case complexity of cyclic coordinate descent: O(n^2) gap with randomized version
• Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
• Asynchronous Lagrangian scenario decomposition
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Coordinate descent algorithms
• Parallel stochastic gradient algorithms for large-scale matrix completion
• Linear convergence of first order methods for non-strongly convex optimization
• A framework for parallel second order incremental optimization algorithms for solving partially separable problems
• On the convergence of asynchronous parallel iteration with unbounded delays
• A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
• Parallel coordinate descent methods for big data optimization
• Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
• Variance reduction for root-finding problems
• On the parallelization upper bound for asynchronous stochastic gradients descent in non-convex optimization
• ARock: an algorithmic framework for asynchronous parallel coordinate updates
• Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
• A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
• A parallel bundle framework for asynchronous subspace optimization of nonsmooth convex functions
• Accelerated, parallel, and proximal coordinate descent
• An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
• Distributed block coordinate descent for minimizing partially separable functions
• Perturbed iterate analysis for asynchronous stochastic optimization
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Delay and cooperation in nonstochastic bandits
• Decentralized consensus algorithm with delayed and stochastic gradients
• Optimization methods for large-scale machine learning
• Parallel stochastic Newton method
• Distributed Learning with Sparse Communications by Identification
• A class of parallel doubly stochastic algorithms for large-scale learning
• Convergence rates for the stochastic gradient descent method for non-convex objective functions
• A class of smooth exact penalty function methods for optimization problems with orthogonality constraints
• An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces
• On the rates of convergence of parallelized averaged stochastic gradient algorithms
• Parallel stochastic asynchronous coordinate descent: tight bounds on the possible parallelism
• Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints
• Coordinatewise descent methods for leading eigenvalue problem
• Accelerate stochastic subgradient method by leveraging local growth condition
• An Uncertainty-Weighted Asynchronous ADMM Method for Parallel PDE Parameter Estimation
• Randomized block proximal damped Newton method for composite self-concordant minimization
• Redundancy techniques for straggler mitigation in distributed optimization and learning
• Asynchronous Gradient Push
• A generic coordinate descent solver for non-smooth convex optimisation
• Asynchronous fully-decentralized SGD in the cluster-based model
• Cyclic Coordinate Dual Averaging with Extrapolation
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• 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
• 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
• Random descent steps in a probability maximization scheme
• A simulation-based approach to estimate joint model of longitudinal and event–time data with many missing longitudinal observations

Describes a project that uses

Uses Software

• LIBSVM
• HOGWILD

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)