Revisiting EXTRA for Smooth Distributed Optimization

Abstract

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−σ2(W))log1ϵ(1−σ2(W))) 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 O((Lϵ+11−σ2(W))log11−σ2(W)) complexities. Then, we use the Catalyst framework to accelerate EXTRA and obtain the O(Lμ(1−σ2(W))‾‾‾‾‾‾‾‾‾√logLμ(1−σ2(W))log1ϵ) communication and computation complexities for strongly convex and smooth problems and the O(Lϵ(1−σ2(W))‾‾‾‾‾‾‾‾‾√log1ϵ(1−σ2(W))) complexities for non-strongly convex ones. Our communication complexities of the accelerated EXTRA are only worse by the factors of (logLμ(1−σ2(W))) and (log1ϵ(1−σ2(W))) from the lower complexity bounds for strongly convex and non-strongly convex problems, respectively.

Publication
SIAM Journal on Optimization
Next
Previous