ARock: an algorithmic framework for asynchronous parallel coordinate updates. Finding a fixed point to a nonexpansive operator, i.e., x * =Tx * , abstracts many problems in numerical linear algebra, optimization, and other areas of data science. 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. We prove that if the nonexpansive operator T has a fixed point, then with probability one, ARock generates a sequence that converges to a fixed point of T. Our conditions on T and step sizes are weaker than those in comparable work. Linear convergence is obtained under suitable assumptions. We propose special cases of ARock for linear systems, convex optimization, and machine learning, as well as distributed and decentralized consensus problems. Numerical experiments solving sparse logistic regression problems are presented.
Keywords for this software
References in zbMATH (referenced in 4 articles , 1 standard article )
Showing results 1 to 4 of 4.
- Xu, Yangyang: Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming (2018)
- Chow, Yat Tin; Wu, Tianyu; Yin, Wotao: Cyclic coordinate-update algorithms for fixed-point problems: analysis and applications (2017)
- Mania, Horia; Pan, Xinghao; Papailiopoulos, Dimitris; Recht, Benjamin; Ramchandran, Kannan; Jordan, Michael I.: Perturbed iterate analysis for asynchronous stochastic optimization (2017)
- Peng, Zhimin; Xu, Yangyang; Yan, Ming; Yin, Wotao: ARock: an algorithmic framework for asynchronous parallel coordinate updates (2016)