## A2BCD: an Asynchronous Accelerated Block Coordinate Descent Algorithm With Optimal ComplexityRobert Hannah, Fei Feng, and Wotao YinSubmitted ## OverviewWe propose the Asynchronous Accelerated Nonuniform Randomized
Block Coordinate Descent algorithm (A2BCD), the first asynchronous
Nesterov-accelerated algorithm that achieves optimal complexity. This parallel
algorithm solves the unconstrained convex minimization problem, using
We first prove that A2BCD converges linearly to a solution with a fast accelerated rate that matches the recently proposed NU_ACDM, so long as the maximum delay is not too large. Somewhat surprisingly, A2BCD pays no complexity penalty for using outdated information. We then prove lower complexity bounds for randomized coordinate descent methods, which show that A2BCD (and hence NU_ACDM) has optimal complexity to within a constant factor. We confirm with numerical experiments that A2BCD outperforms NU_ACDM, which is the current fastest coordinate descent algorithm, even at small scale. We also derive and analyze a second-order ordinary differential equation, where the time dependent variable has blocks, is the condition number of the objective function , and is a time-delayed copy of . This equation is the continuous-time limit of our accelerated algorithm. converges to zero at an accelerated linear rate of . ## Citation
« Back |