Asynchronous Parallel Computing in Signal Processing and Machine Learning

Wotao Yin, University of California, Los Angeles
February 24th, 2016 at 3:30PM–4:30PM in 939 Evans Hall [Map]

The performance of each CPU core stopped improving around 2005. The Moore's law, however, continues to apply – not to single-thread performance – but the number of cores in each computer. Today, workstations are with 64 cores, graphic cards with thousands of GPU cores, and some cellphones with eight cores are sold at affordable prices. To benefit from this multi-core Moore's law, we must parallelize our algorithms. We study asynchronous parallel computing at a high-level of abstraction: finding a fixed point to a nonexpansive operator. It underlies many models in numerical linear algebra, optimization, and other areas of scientific 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. As special cases of ARock, novel algorithms for linear equation systems, 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. Convergence rates are also given. Very encouraging numerical performance of ARock is observed on sparse logistic regression and other large-scale problems. This is joint work with Zhimin Peng (UCLA), Yangyang Xu (IMA), and Ming Yan (Michigan State).