# ARock: Asynchronous Parallel Coordinate Update

Monday, December 7, 2015 - 2:25pm - 3:25pm

Lind 305

Yangyang Xu (University of Minnesota, Twin Cities)

The problem of ﬁnding a ﬁxed point to a nonexpansive operator is an abstraction of many models in numerical linear algebra, optimization, and other areas of scientiﬁc computing. To solve this problem, we propose ARock, an asynchronous parallel algorithmic framework, in which a set of agents (machines, processors, or cores) update randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. The resulting algorithms are not aﬀected by load imbalance. When the coordinate updates are atomic, the algorithms are free of memory locks.

We show that if the nonexpansive operator has a ﬁxed point, then with probability one, the sequence of points generated by ARock converges to a ﬁxed point of the operator. Stronger convergence properties such as linear convergence are obtained under stronger conditions. As special cases of ARock, novel algorithms for linear systems, convex optimization, machine learning, distributed and decentralized optimization are introduced with provable convergence. Very promising numerical performance of ARock has been observed. We present the numerical results of solving sparse logistic

regression problems.

We show that if the nonexpansive operator has a ﬁxed point, then with probability one, the sequence of points generated by ARock converges to a ﬁxed point of the operator. Stronger convergence properties such as linear convergence are obtained under stronger conditions. As special cases of ARock, novel algorithms for linear systems, convex optimization, machine learning, distributed and decentralized optimization are introduced with provable convergence. Very promising numerical performance of ARock has been observed. We present the numerical results of solving sparse logistic

regression problems.