ARock

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.


References in zbMATH (referenced in 20 articles , 1 standard article )

Showing results 1 to 20 of 20.
Sorted by year (citations)

  1. Mishchenko, Konstantin; Iutzeler, Franck; Malick, Jérôme: A distributed flexible delay-tolerant proximal gradient algorithm (2020)
  2. Sun, Tao; Sun, Yuejiao; Xu, Yangyang; Yin, Wotao: Markov chain block coordinate descent (2020)
  3. Todescato, Marco; Bof, Nicoletta; Cavraro, Guido; Carli, Ruggero; Schenato, Luca: Partition-based multi-agent optimization in the presence of lossy and asynchronous communication (2020)
  4. Gao, Bin; Liu, Xin; Yuan, Ya-Xiang: Parallelizable algorithms for optimization problems with orthogonality constraints (2019)
  5. Heaton, Howard; Censor, Yair: Asynchronous sequential inertial iterations for common fixed points problems with an application to linear systems (2019)
  6. Pang, C. H. Jeffrey: Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting (2019)
  7. Peng, Zhimin; Xu, Yangyang; Yan, Ming; Yin, Wotao: On the convergence of asynchronous parallel iteration with unbounded delays (2019)
  8. Stathopoulos, Giorgos; Jones, Colin N.: An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization (2019)
  9. Valkonen, Tuomo: Block-proximal methods with spatially adapted acceleration (2019)
  10. Wang, Yu; Yin, Wotao; Zeng, Jinshan: Global convergence of ADMM in nonconvex nonsmooth optimization (2019)
  11. Xiao, Lin; Yu, Adams Wei; Lin, Qihang; Chen, Weizhu: DSCOVR: randomized primal-dual block coordinate algorithms for asynchronous distributed optimization (2019)
  12. Xu, Yangyang: Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs (2019)
  13. Bednarczuk, E. M.; Jezierska, A.; Rutkowski, K. E.: Proximal primal-dual best approximation algorithm with memory (2018)
  14. Hannah, Robert; Yin, Wotao: On unbounded delays in asynchronous parallel fixed-point algorithms (2018)
  15. Wei, Xiaohan; Neely, Michael J.: Asynchronous optimization over weakly coupled renewal systems (2018)
  16. Xu, Yangyang: Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming (2018)
  17. Xu, Yangyang; Zhang, Shuzhong: Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization (2018)
  18. Chow, Yat Tin; Wu, Tianyu; Yin, Wotao: Cyclic coordinate-update algorithms for fixed-point problems: analysis and applications (2017)
  19. Mania, Horia; Pan, Xinghao; Papailiopoulos, Dimitris; Recht, Benjamin; Ramchandran, Kannan; Jordan, Michael I.: Perturbed iterate analysis for asynchronous stochastic optimization (2017)
  20. Peng, Zhimin; Xu, Yangyang; Yan, Ming; Yin, Wotao: ARock: an algorithmic framework for asynchronous parallel coordinate updates (2016)