A2BCD: Asynchronous Acceleration with Optimal Complexity
In this paper, we propose the Asynchronous Accelerated Nonuniform Randomized Block Coordinate Descent algorithm (A2BCD). We prove A2BCD converges linearly to a solution of the convex minimization problem at the same rate as NU_ACDM, so long as the maximum delay is not too large. This is the first asynchronous Nesterov-accelerated algorithm that attains any provable speedup. Moreover, we then prove that these algorithms both have optimal complexity. Asynchronous algorithms complete much faster iterations, and A2BCD has optimal complexity. Hence we observe in experiments that A2BCD is the top-performing coordinate descent algorithm, converging up to 4 − 5× faster than NU_ACDM on some data sets in terms of wall-clock time. To motivate our theory and proof techniques, we also derive and analyze a continuous-time analogue of our algorithm and prove it converges at the same rate.
The authors design an accelerated, asynchronous block coordinate descent algorithm, which, for sufficiently small delays attains the iteration complexity of the current state of the art algorithm (which is not parallel/asynchronous). The authors prove a lower bound on the iteration complexity in order to show that their algorithm is near optimal. They also analyze an ODE which is the continuous time limit of A2BCD, which they use to motivate their approach.
I am a little bit confused about the guarantee of the algorithm, as it does not agree with my intuition. Perhaps I am simply mistaken in my intuition, but I am concerned that there may need to be additional premises to the Theorem.
My main confusion is with Theorem 1, which says that for $\psi < 3/7$ the iteration complexity is approximately the iteration complexity of NU_ACDM times a factor of $(1 + o(1))/(1-\psi)$, i.e. within that factor of the optimal *non-asynchronous/parallel* algorithm. In particular, since $\psi < 3/7$ this means that the algorithm is within a $7/4 + o(1)$ factor. As mentioned in Corollary 3, this applies for instance when $L_i = L$ for all i and $\tau = \Theta( n^{1/2}\kappa^{-1/4} )$. Therefore, in a regime where $n \approx \kappa$, and $n$ very large, this would indicate that the algorithm would be almost as good as the best synchronous algorithm even for delays $\tau \approx n^{1/4}$. Perhaps I am missing something, but this seems very surprising to me, in particular, I would expect more significant slowdown due to $\tau$. 
I am also a little bit surprised that the maximum tolerable delay is proportional to the *minimum* smoothness parameter $\underbar{L}$. It seems like decreasing $\underbar{L}$ should make optimization easier and therefore more delay should be tolerated. Perhaps this is simply an artifact of the analysis.