ARock: an algorithmic framework for asynchronous parallel coordinate updates

DOI10.1137/15M1024950zbMATH Open1350.49041arXiv1506.02396MaRDI QIDQ2821779FDOQ2821779

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)

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.

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

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

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)

Cites Work

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

Cited In (43)

• Convergence Theorems and Convergence Rates for the General Inertial Krasnosel’skiǐ–Mann Algorithm
• Asynchronous distributed voltage control in active distribution networks
• An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
• Distributed Learning with Sparse Communications by Identification
• Scalable asynchronous domain decomposition solvers
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• A multi-step inertial asynchronous sequential algorithm for common fixed point problems
• Randomized progressive hedging methods for multi-stage stochastic programming
• 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
• 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
• 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
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• Proximal primal-dual best approximation algorithm with memory
• 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
• Sequential inertial linear ADMM algorithm for nonconvex and nonsmooth multiblock problems with nonseparable structure
• Block-proximal methods with spatially adapted acceleration
• On the convergence of asynchronous parallel iteration with unbounded delays
• Asynchronous optimization over weakly coupled renewal systems
• A novel bound on the convergence rate of ADMM for distributed optimization
• 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
• ARock
• 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
• A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates

Uses Software

• TMAC
• HOGWILD

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)