ARock: an algorithmic framework for asynchronous parallel coordinate updates

DOI10.1137/15M1024950MaRDI QIDQ2821779zbMATH OpenFDO

Authors Zhimin Peng, Ming Yan, Wotao Yin, Yangyang Xu

Publication date 23 September 2016

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.02396

zbMATH Keywords

optimizationfixed pointnonexpansive operatorasynchronous parallel coordinate updates

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Fixed-point theorems (47H10) Iterative procedures involving nonlinear operators (47J25) Decentralized systems (93A14) Numerical methods based on necessary conditions (49M05) Acceleration of convergence in numerical analysis (65B99)

Abstract: Finding a fixed point to a nonexpansive operator, i.e., $x^{\ast }=T{x}^{\ast }$, abstracts many problems in numerical linear algebra, optimization, and other areas of scientific computing. To solve fixed-point problems, we propose ARock, an algorithmic framework in which multiple agents (machines, processors, or cores) update $x$ in an asynchronous parallel fashion. Asynchrony is crucial to parallel computing since it reduces synchronization wait, relaxes communication bottleneck, and thus speeds up computing significantly. At each step of ARock, an agent updates a randomly selected coordinate $x_i$ based on possibly out-of-date information on $x$. The agents share $x$ through either global memory or communication. If writing $x_i$ is atomic, the agents can read and write $x$ without memory locks. Theoretically, we show that if the nonexpansive operator $T$ has a fixed point, then with probability one, ARock generates a sequence that converges to a fixed points of $T$. Our conditions on $T$ and step sizes are weaker than comparable work. Linear convergence is also obtained. We propose special cases of ARock for linear systems, convex optimization, machine learning, as well as distributed and decentralized consensus problems. Numerical experiments of solving sparse logistic regression problems are presented.

Recommendations

• On unbounded delays in asynchronous parallel fixed-point algorithms
• Asynchronous sequential inertial iterations for common fixed points problems with an application to linear systems
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Asynchronous parallel algorithms for nonconvex optimization

Cites work

• scientific article; zbMATH DE number 3833218 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)
• scientific article; zbMATH DE number 3574917 (Why is no real title available?)
• scientific article; zbMATH DE number 1444680 (Why is no real title available?)
• scientific article; zbMATH DE number 3108780 (Why is no real title available?)
• A case study in programming for parallel-processors
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Asynchronous Iterative Methods for Multiprocessors
• Asynchronous finite-difference schemes for partial differential equations
• Asynchronous multisplitting methods for nonlinear fixed point problems
• Asynchronous stochastic coordinate descent: parallelism and convergence properties
• Asynchronous weighted additive Schwarz methods
• Chaotic relaxation
• Construction of fixed points of demicompact mappings in Hilbert space
• Convergence rate analysis of an asynchronous space decomposition method for convex Minimization
• Convergence rate analysis of several splitting schemes
• Convex analysis and monotone operator theory in Hilbert spaces
• Coordinate descent method for large-scale L2-loss linear support vector machines
• Coordinate-friendly structures, algorithms and applications
• Distributed Subgradient Methods for Multi-Agent Optimization
• Distributed asynchronous computation of fixed points
• Distributed asynchronous incremental subgradient methods
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• Implicit-Explicit Parallel Asynchronous Solver of Parabolic PDEs
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• On asynchronous iterations
• On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
• On the convergence of decentralized gradient descent
• Parallel asynchronous iterations for the solution of a 3D continuous flow electrophoresis problem
• Parallel coordinate descent methods for big data optimization
• Partially Asynchronous, Parallel Algorithms for Network Flow and Other Problems
• Revisiting Asynchronous Linear Solvers
• Self equivalence of the alternating direction method of multipliers
• Some aspects of parallel and distributed iterative algorithms - a survey
• Some convergence results for asynchronous algorithms
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
• Weak convergence of the sequence of successive approximations for nonexpansive mappings

Cited in

(43)

• Asynchronous distributed voltage control in active distribution networks
• A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• Convergence Theorems and Convergence Rates for the General Inertial Krasnosel’skiǐ–Mann Algorithm
• Distributed Learning with Sparse Communications by Identification
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Randomized progressive hedging methods for multi-stage stochastic programming
• Scalable asynchronous domain decomposition solvers
• A multi-step inertial asynchronous sequential algorithm for common fixed point problems
• Primal-dual block-proximal splitting for a class of non-convex problems
• Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
• An asynchronous distributed and scalable generalized Nash equilibrium seeking algorithm for strongly monotone games
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Asynchronous ADMM for nonlinear continuous-time systems
• On unbounded delays in asynchronous parallel fixed-point algorithms
• An asynchronous inertial algorithm for solving convex feasibility problems with strict pseudo-contractions in Hilbert spaces
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
• A distributed flexible delay-tolerant proximal gradient algorithm
• Proximal primal-dual best approximation algorithm with memory
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• Cyclic coordinate-update algorithms for fixed-point problems: analysis and applications
• Asynchronous parallel algorithms for nonconvex optimization
• Risk-averse stochastic programming and distributionally robust optimization via operator splitting
• Partition-based multi-agent optimization in the presence of lossy and asynchronous communication
• Block-proximal methods with spatially adapted acceleration
• Sequential inertial linear ADMM algorithm for nonconvex and nonsmooth multiblock problems with nonseparable structure
• On the convergence of asynchronous parallel iteration with unbounded delays
• ARock
• A novel bound on the convergence rate of ADMM for distributed optimization
• Asynchronous optimization over weakly coupled renewal systems
• Asynchronous sequential inertial iterations for common fixed points problems with an application to linear systems
• A stochastic subspace approach to gradient-free optimization in high dimensions
• Perturbed iterate analysis for asynchronous stochastic optimization
• Redundancy techniques for straggler mitigation in distributed optimization and learning
• Variance reduction for root-finding problems
• A class of smooth exact penalty function methods for optimization problems with orthogonality constraints
• Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays
• Markov chain block coordinate descent
• Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
• Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
• Asynchronous level bundle methods
• Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints

Describes a project that uses

Uses Software

• HOGWILD
• TMAC

This page was built for publication: ARock: an algorithmic framework for asynchronous parallel coordinate updates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2821779)