The Analysis of Asynchronous Coordinate Descent

7^th December 2017, 14:00 Ashton Lecture Theater
Professor Richard Cole
Computer Science Department
Courant Institute of Mathematical Sciences
New York University

Abstract

The Analysis of Asynchronous Coordinate Descent

Finding an approximate minimum of high-dimensional convex functions is both a fundamental problem and one of considerable practical interest in machine learning and elsewhere. A method of choice is (sequential) stochastic coordinate descent. Given the high dimensions that arise in practice, asynchronous parallel implementations have received a lot of attention.

We show how to analyze the standard implementation in which coordinates are partitioned among processors and each processor repeatedly selects a coordinate to update uniformly at random from among its assigned coordinates. This analysis has a possibly unexpected connection to the analysis of (sequential) cyclic coordinate descent, for which we provide the best currently-known bounds, and we provide evidence that these bounds may be tight. We also give the first analysis of an asynchronous accelerated coordinate descent. The main question we are answering is for how many processors does one achieve linear speedup compared to the sequential versions of these algorithms.

This talk is intended to be self-contained. Our goal is to indicate the challenges that these analyses face and how we approach them.

This is joint work with Yun Kuen Cheung, Yixin Tao, and Ojas Deshpande.