English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  (Near) Optimal Parallelism Bound for Fully Asynchronous Coordinate Descent with Linear Speedup

Cheung, Y. K., Cole, R., & Tao, Y. (2018). (Near) Optimal Parallelism Bound for Fully Asynchronous Coordinate Descent with Linear Speedup. Retrieved from http://arxiv.org/abs/1811.03254.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0002-AAF5-A Version Permalink: http://hdl.handle.net/21.11116/0000-0002-AAF6-9
Genre: Paper

Files

show Files
hide Files
:
arXiv:1811.03254.pdf (Preprint), 475KB
Name:
arXiv:1811.03254.pdf
Description:
File downloaded from arXiv at 2018-12-13 12:45
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Cheung, Yun Kuen1, Author              
Cole, Richard2, Author
Tao, Yixin2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Mathematics, Optimization and Control, math.OC,Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
 Abstract: When solving massive optimization problems in areas such as machine learning, it is a common practice to seek speedup via massive parallelism. However, especially in an asynchronous environment, there are limits on the possible parallelism. Accordingly, we seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent. We focus on asynchronous coordinate descent (ACD) algorithms on convex functions $F:\mathbb{R}^n \rightarrow \mathbb{R}$ of the form $$F(x) = f(x) ~+~ \sum_{k=1}^n \Psi_k(x_k),$$ where $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a smooth convex function, and each $\Psi_k:\mathbb{R} \rightarrow \mathbb{R}$ is a univariate and possibly non-smooth convex function. Our approach is to quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a truly simple yet optimal analysis of the standard stochastic ACD in a partially asynchronous environment, which already generalizes and improves on the bounds in prior work. We also give a considerably more involved analysis for general asynchronous environments in which the only constraint is that each update can overlap with at most $q$ others, where $q$ is at most the number of processors times the ratio in the lengths of the longest and shortest updates. The main technical challenge is to demonstrate linear speedup in the latter environment. This stems from the subtle interplay of asynchrony and randomization. This improves Liu and Wright's (SIOPT'15) lower bound on the maximum degree of parallelism almost quadratically, and we show that our new bound is almost optimal.

Details

show
hide
Language(s): eng - English
 Dates: 2018-11-072018
 Publication Status: Published online
 Pages: 48 p.
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: arXiv: 1811.03254
URI: http://arxiv.org/abs/1811.03254
BibTex Citekey: corr/abs-1811-03254
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show