Title: Asynchronous Coordinate Descent under More Realistic Assumptions,
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.