Asynchronous Parallel Computing in Signal Processing and Machine Learning

Monday, January 25, 2016 - 2:00pm - 2:50pm
Keller 3-180
Wotao Yin (University of California, Los Angeles)
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).
MSC Code: