-

 

 

 




Optimization Online





 

Asynchronous Coordinate Descent under More Realistic Assumptions

Tao Sun (nudtsuntao***at***163.com;nudttaosun)
Robert Hannah (roberthannah89***at***math.ucla.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: Asynchronous-parallel algorithms have the potential to vastly speed up algorithms by eliminating costly synchronization. However, our understanding to these algorithms is limited because the current convergence of asynchronous (block) coordinate descent algorithms are based on somewhat unrealistic assumptions. In particular, the age of the shared optimization variables being used to update a block is assumed to be independent of the block being updated. Also, it is assumed that the updates are applied to randomly chosen blocks. In this paper, we argue that these assumptions either fail to hold or will imply less efficient implementations. We then prove the convergence of asynchronous-parallel block coordinate descent under more realistic assumptions, in particular, always without the independence assumption. The analysis permits both the deterministic (essentially) cyclic and random rules for block choices. Because a bound on the asynchronous delays may or may not be available, we establish convergence for both bounded delays and unbounded delays. The analysis also covers nonconvex, weakly convex, and strongly convex functions. We construct Lyapunov functions that directly model both objective progress and delays, so delays are not treated errors or noise. A continuous-time ODE is provided to explain the construction at a high level.

Keywords: asynchronous; parallel; coordinate descent; convergence

Category 1: Nonlinear Optimization

Citation:

Download: [PDF]

Entry Submitted: 05/19/2017
Entry Accepted: 05/19/2017
Entry Last Modified: 07/24/2017

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society