Asynchronous Coordinate Descent under More Realistic Assumption *
Asynchronous-parallel algorithms have the potential to vastly speed up algorithms by eliminating costly synchronization. However, our understanding of these algorithms is limited because the current convergence theory of asynchronous block coordinate descent algorithms is based on somewhat unrealistic assumptions. In particular, the age of the shared optimization variables being used to update blocks is assumed to be independent of the block being updated. Additionally, 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. The convergence theory involves a Lyapunov function that directly incorporates both objective progress and delays. A continuous-time ODE is provided to motivate the construction at a high level.
The paper studies coordinate descent with asynchronous updates. The key contributions include a relaxation of the assumptions on how the block coordinates are chosen and how large could the delays be. Descent lemma and convergence rates are obtained for a variety of settings using the ode analysis and discretization.
I think the paper is well-grounded because existing assumptions in the asynchronous analyses of coordinate descents are highly unsatisfactory; and this work explained the problem well and proposed a somewhat more satisfactory solution. For this reason I vote for accept.
Detailed evaluation:
1. I did not have time to check the proof, but I think the results are believable based on the steps that the authors outlined in the main paper. 
2. The conditions for cyclic choice of coordinates and unbounded delays could be used in other settings.
3. In a related problem of asynchronous block coordinate frank wolfe, it was established under weaker tail bound assumptions of the delay random variable that there could be unbounded stochastic delay. The delay random variable also are not required to be independent. Establishing deterministic sequence in AP-BCFW or more heavy-tailed stochastic delay for AP-BCD could both be useful. 
- Wang, Y. X., Sadhanala, V., Dai, W., Neiswanger, W., Sra, S., & Xing, E. (2016, June). Parallel and distributed block-coordinate Frank-Wolfe algorithms. In International Conference on Machine Learning (pp. 1548-1557).