Asynchronous Coordinate Descent under More Realistic Assumptions

arXiv1705.08494MaRDI QIDQ6287044FDOQ6287044

Authors: Tao Sun, Robert Hannah, Wotao Yin 

Publication date: 19 May 2017

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.

This page was built for publication: Asynchronous Coordinate Descent under More Realistic Assumptions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6287044)