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 O ( (L+11-₂ ({W) }) 1 (1-₂ ({W) ) }) communication and computation complexities for -strongly convex and L-smooth problems, where ₂ (W) is the second largest singular value of the weight matrix W. When the strong convexity is absent, we prove the O ( (L+11-₂ ({W) }) 11-₂ ({W) }) complexities. Then, we use the Catalyst framework to accelerate EXTRA and obtain the O (L{ (1-₂ ({W) ) }} L (1-₂ ({W) ) }1) communication and computation complexities for strongly convex and smooth problems and the O (L{ (1-₂ ({W) ) }}1 (1-₂ (W) ) ) complexities for nonstrongly convex ones. Our communication complexities of the accelerated EXTRA are only worse by the factors of ( (1-₂ (W) ) ) and (1 (1-₂ ({W) ) }) from the lower complexity bounds for strongly convex and nonstrongly convex problems, respectively.