We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex optimization, machine learning, distributed and decentralized optimization are introduced. We show that if the operator has a fixed point and is nonexpansive, then with probability one, the sequence of points generated by ARock converges to a fixed point. Stronger convergence properties such as linear convergence are obtained under stronger conditions. Very promising numerical performance of ARock has been observed. Considering the paper length, we present the numerical results of solving linear equations and sparse logistic regression problems.
Article
View ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates