Applied Mathematics Seminar

Title: ARock: Asynchronous Parallel Coordinate Updates

Abstract: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) updates a sequence of randomly selected coordinates of the unknown variable in a parallel asynchronous fashion. As special cases of ARock, novel algorithms in linear algebra, convex optimization, machine learning, distributed and decentralized optimization are introduced. We show that if the nonexpansive operator has a fixed point, then with probability one the sequence of points generated by ARock converges to a fixed point. Very encouraging numerical performance of ARock is observed on solving linear equations, sparse logistic regression, and other large-scale problems in recent data sciences. This is joint work with Zhimin Peng, Yangyang Xu, and Wotao Yin.