Revisiting EXTRA for Smooth Distributed Optimization

EXTRA is a popular method for dencentralized distributed optimization and has broad applications. This paper revisits EXTRA. First, we give a sharp complexity analysis for EXTRA with the improved Oleft(left(fracLμ+frac11-σ2(W)right)logfrac1ε(1-σ2(W))right) communication and computation complexities for μ-strongly convex and L-smooth problems, where σ2(W) is the second largest singular value of the weight matrix W. When the strong convexity is absent, we prove the Oleft(left(fracLε+frac11-σ2(W)right)logfrac11-σ2(W)right) complexities. Then, we use the Catalyst framework to accelerate EXTRA and obtain the Oleft(√fracLμ(1-σ2(W))logfrac Lμ(1-σ2(W))logfrac1εright) communication and computation complexities for strongly convex and smooth problems and the Oleft(√fracLε(1-σ2(W))logfrac1ε(1-σ2(W))right) complexities for non-strongly convex ones. Our communication complexities of the accelerated EXTRA are only worse by the factors of left(logfracLμ(1-σ2(W))right) and left(logfrac1ε(1-σ2(W))right) from the lower complexity bounds for strongly convex and non-strongly convex problems, respectively.