ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

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.

updated the linear convergence proofs

References in corpus (1)

• Coordinate Friendly Structures, Algorithms and Applications

Cited by in corpus (60)

• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Asynchronous Distributed Optimization over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
• VAFL: a Method of Vertical Asynchronous Federated Learning
• Coordinate Friendly Structures, Algorithms and Applications
• AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
• Parallelizable Algorithms for Optimization Problems with Orthogonality Constraints
• A Communication Efficient Collaborative Learning Framework for Distributed Features
• Supervised Learning Under Distributed Features
• Relative Transformation Estimation Based on Fusion of Odometry and UWB Ranging Data
• A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
• CYCLADES: Conflict-free Asynchronous Machine Learning
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems
• A Push-Pull Gradient Method for Distributed Optimization in Networks
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• Randomized Progressive Hedging methods for Multi-stage Stochastic Programming
• Generalized gradient optimization over lossy networks for partition-based estimation
• Distributed Optimization over Lossy Networks via Relaxed Peaceman-Rachford Splitting: a Robust ADMM Approach
• Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
• Block-proximal methods with spatially adapted acceleration
• ADMM-Tracking Gradient for Distributed Optimization over Asynchronous and Unreliable Networks
• Projective Splitting with Forward Steps: Asynchronous and Block-Iterative Operator Splitting
• Robust Online Learning over Networks
• FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
• Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
• On the Convergence of Asynchronous Parallel Iteration with Unbounded Delays
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
• Asynchronous Decentralized Successive Convex Approximation
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• Primal-dual block-proximal splitting for a class of non-convex problems
• An asynchronous, forward-backward, distributed generalized Nash equilibrium seeking algorithm
• Balancing Communication and Computation in Distributed Optimization
• Superlinearly Convergent Asynchronous Distributed Network Newton Method
• Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
• TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods
• A Stochastic Operator Framework for Optimization and Learning with Sub-Weibull Errors
• Learning and Management for Internet-of-Things: Accounting for Adaptivity and Scalability
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Distributed Algorithms for Peak Ramp Minimization Problem in Smart Grid
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• Greedy coordinate descent method on non-negative quadratic programming
• Asynchronous Message-Passing and Zeroth-Order Optimization Based Distributed Learning with a Use-Case in Resource Allocation in Communication Networks
• Setwise Coordinate Descent for Dual Asynchronous Decentralized Optimization
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• A stochastic subspace approach to gradient-free optimization in high dimensions
• Asynchronous Optimization over Weakly Coupled Renewal Systems
• Asynchronous Distributed Power Control of Multi-Microgrid Systems Based on the Operator Splitting Approach
• Dynamic Average Diffusion with randomized Coordinate Updates
• Asynchronous Distributed Voltage Control in Active Distribution Networks
• An Inertial Parallel and Asynchronous Fixed-Point Iteration for Convex Optimization
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
• A Partition-Based Implementation of the Relaxed ADMM for Distributed Convex Optimization over Lossy Networks
• Distributed Prediction-Correction ADMM for Time-Varying Convex Optimization
• Asynchronous Sequential Inertial Iterations for Common Fixed Points Problems with an Application to Linear Systems
• Coordinate-Update Algorithms can Efficiently Detect Infeasible Optimization Problems
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates
• Subdifferentiable functions and partial data communication in a distributed deterministic asynchronous Dykstra's algorithm
• Proximal primal-dual best approximation algorithm with memory
• Asynchronous Parallel Nonconvex Optimization Under the Polyak-Lojasiewicz Condition