Asynchronous Analysis of Asynchronous Coordinate Descent and Tatonnement

We analyze a rather general asynchronous coordinate descent on convex functions of the form F(x) = f(x) + sum_k gk(xk) where f is a smooth convex function on (x1, ..., xn), and each gk is univariate and convex, but possibly non-smooth.

Our formulation of asynchrony captures cyclic (i.e. round robin) coordinate descent, and the version of stochastic coordinate descent with no-replacement sampling, a version which has not previously been analyzed to the best of our knowledge, although it is used in practice, as well as many other asynchronous interleavings. Our analysis is amortized and the resulting bounds are worst case, even for stochastic coordinate descent! We extend the analysis to show that an asynchronous version of tatonnement converges toward a market equilibrium for Fisher markets with CES or Leontief utilities, settings in which tatonnement is equivalent to coordinate descent.

This is joint work with Yun Kuen Cheung.