Parallel stochastic asynchronous coordinate descent: Tight bounds on the possible parallelism

Yun Kuen Cheung; Richard J. Cole; Yixin Tao

doi:10.1137/19M129574X

Parallel stochastic asynchronous coordinate descent: Tight bounds on the possible parallelism

Yun Kuen Cheung, Richard J. Cole, Yixin Tao

Computer Science

Research output: Contribution to journal › Article › peer-review

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/L_res) processors, where Lmax and L_res are suitable Lipschitz parameters. This paper shows the bound is tight for almost all possible values of these parameters.

Original language	English (US)
Pages (from-to)	448-460
Number of pages	13
Journal	SIAM Journal on Optimization
Volume	31
Issue number	1
DOIs	https://doi.org/10.1137/19M129574X
State	Published - Feb 2021

Keywords

Parallelism bound
Stochastic asynchronous coordinate descent

ASJC Scopus subject areas

Software
Theoretical Computer Science

Access to Document

10.1137/19M129574X

Cite this

@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 = "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",

}

TY - JOUR

T1 - Parallel stochastic asynchronous coordinate descent

T2 - Tight bounds on the possible parallelism

AU - Cheung, Yun Kuen

AU - Cole, Richard J.

AU - Tao, Yixin

PY - 2021/2

Y1 - 2021/2

N2 - 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.

AB - 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.

KW - Parallelism bound

KW - Stochastic asynchronous coordinate descent

UR - http://www.scopus.com/inward/record.url?scp=85103224716&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85103224716&partnerID=8YFLogxK

U2 - 10.1137/19M129574X

DO - 10.1137/19M129574X

M3 - Article

AN - SCOPUS:85103224716

SN - 1052-6234

VL - 31

SP - 448

EP - 460

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 1

ER -

Parallel stochastic asynchronous coordinate descent: Tight bounds on the possible parallelism

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this