ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

Zhimin Peng UCLA Yangyang Xu University of Alabama Ming Yan Michigan State University Wotao Yin UCLA

Numerical Analysis and Scientific Computing Optimization and Control Machine Learning mathscidoc:1703.25022

SIAM Journal on Scientific Computing, 38, (5), A2851-A2879, 2016
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 sciences. To solve xed- 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. 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 comparable work. Linear convergence is obtained under suitable assumptions. 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.
asynchronous, parallel, coordinate update, nonexpansive operator, ADMM
[ Download ] [ 2017-03-14 09:40:35 uploaded by yangyangxu ] [ 99 downloads ] [ 0 comments ]
@inproceedings{zhimin2016arock:,
  title={ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates},
  author={Zhimin Peng, Yangyang Xu, Ming Yan, and Wotao Yin},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170314094035571023691},
  booktitle={SIAM Journal on Scientific Computing},
  volume={38},
  number={5},
  pages={A2851-A2879},
  year={2016},
}
Zhimin Peng, Yangyang Xu, Ming Yan, and Wotao Yin. ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates. 2016. Vol. 38. In SIAM Journal on Scientific Computing. pp.A2851-A2879. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170314094035571023691.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved