# ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

arXiv: https://arxiv.org/abs/1506.02396 · HTML: https://mlsanity.com/paper/1506.02396/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2015.

## Built on by (most cited first, 21 of 21)

- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Robust Online Learning over Networks](https://mlsanity.com/paper/2309.00520/) (2023)
- [Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delays](https://mlsanity.com/paper/2405.10123/) (2024)
- [SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient Method for Distributed Learning in Computing Clusters](https://mlsanity.com/paper/2208.08425/) (2022)
- [Hyperion -- A fast, versatile symbolic Gaussian Belief Propagation framework for Continuous-Time SLAM](https://mlsanity.com/paper/2407.07074/) (2024)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization](https://mlsanity.com/paper/2207.07543/) (2022)
- [On Parallel or Distributed Asynchronous Iterations with Unbounded Delays and Possible Out of Order Messages or Flexible Communication for Convex Optimization Problems and Machine Learning](https://mlsanity.com/paper/2210.04626/) (2022)
- [Asynchronous Message-Passing and Zeroth-Order Optimization Based Distributed Learning with a Use-Case in Resource Allocation in Communication Networks](https://mlsanity.com/paper/2311.04604/) (2023)
- [DVM-SLAM: Decentralized Visual Monocular Simultaneous Localization and Mapping for Multi-Agent Systems](https://mlsanity.com/paper/2503.04126/) (2025)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Scalable Asynchronous Federated Modeling for Spatial Data](https://mlsanity.com/paper/2510.01771/) (2025)
- [Distributed Perceptron under Bounded Staleness, Partial Participation, and Noisy Communication](https://mlsanity.com/paper/2601.10705/) (2026)
- [Stochastic convergence of parallel asynchronous adaptive first-order methods](https://mlsanity.com/paper/2606.01787/) (2026)

## Abstract (arXiv)

Finding a fixed point to a nonexpansive operator, i.e., x^*=Tx^*, 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 xi based on possibly out-of-date information on x. The agents share x through either global memory or communication. If writing xi 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.