## ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate UpdatesZhimin Peng, Yangyang Xu, Ming Yan, and Wotao YinPublished in SIAM Journal on Scientific Computing Old C code at GitHub by Zhimin Peng
## OverviewFinding a fixed point to a nonexpansive operator, i.e., , 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 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 based on possibly out-of-date information on . The agents share through either global memory or communication. If writing is atomic, the agents can read and write without memory locks. Theoretically, we show that if the nonexpansive operator has a fixed point, then with probability one, ARock generates a sequence that converges to a fixed points of . Our conditions on 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. ## Related papers- Coordinate friendly structures, algorithms and applications
Z. Peng, T. Wu, Y. Xu, M. Yan, and W. Yin - On unbounded delays in asynchronous parallel fixed-point algorithms
R. Hannah and W. Yin - Decentralized consensus optimization with asynchrony and delay
T. Wu, K. Yuan, Q. Ling, W. Yin, and A.H. Sayed - TMAC: A toolbox of modern async-parallel, coordinate, splitting, and stochastic methods
B. Edmunds, Z. Peng, and W. Yin
## Citation of this paper
« Back |