@article{ea9abdc141e549a0b65ec62021dc83d2,
title = "Parallel stochastic asynchronous coordinate descent: Tight bounds on the possible parallelism",
abstract = "Several works have shown linear speedup is achieved by an asynchronous parallel implementation of stochastic coordinate descent so long as there is not too much parallelism. More specifically, it is known that if all updates are of similar duration, then linear speedup is possible with up to \Theta (Lmax\surd n/Lres) processors, where Lmax and Lres are suitable Lipschitz parameters. This paper shows the bound is tight for almost all possible values of these parameters.",
keywords = "Parallelism bound, Stochastic asynchronous coordinate descent",
author = "Cheung, {Yun Kuen} and Cole, {Richard J.} and Yixin Tao",
note = "Funding Information: \ast Received by the editors October 28, 2019; accepted for publication (in revised form) November 18, 2020; published electronically February 1, 2021. https://doi.org/10.1137/19M129574X Funding: The first author would like to acknowledge Singapore NRF 2018 Fellowship NRF-NRFF2018-07 and MOE AcRF Tier 2 grant 2016-T2-1-170. The work of the second and third authors was supported in part by NSF grants CCF-1527568 and CCF-1909538. \dagger Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK (yunkuen.cheung@rhul. ac.uk, http://cs.rhul.ac.uk/\sim cheung/). \ddagger Courant Institute of Mathematical Sciences, New York University, New York, NY 10012-1185 USA (cole@cs.nyu.edu, yt851@nyu.edu). 1In optimization, we compare the times of two executions that achieve a given level of accuracy. 2We chose the notation q to emphasize its likely similarity to p, the number of processors. \sum 3Many of these results hold for composite functions, i.e., functions of the form f(x) = g(x) + k=1n\Psi k(xk), where g : n \rightarrow is a convex function with a continuous gradient, and each \Psi k : \rightarrow is a univariate convex function, but may be nonsmooth. Publisher Copyright: {\textcopyright} 2021 Society for Industrial and Applied Mathematics",
year = "2021",
month = feb,
doi = "10.1137/19M129574X",
language = "English (US)",
volume = "31",
pages = "448--460",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",
}