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((\frac{L}{\mu }+\frac{1}{1-{\sigma }_2(W)})\log \frac{1}{ϵ(1-{\sigma }_2(W))})$ communication and computation complexities for $\mu$-strongly convex and $L$-smooth problems, where ${\sigma }_2(W)$ is the second largest singular value of the weight matrix $W$. When the strong convexity is absent, we prove the $O((\frac{L}{ϵ}+\frac{1}{1-{\sigma }_2(W)})\log \frac{1}{1-{\sigma }_2(W)})$ complexities. Then, we use the Catalyst framework to accelerate EXTRA and obtain the $O\left(\sqrt{\frac{L}{\mu(1-\sigma_2(W))}}\log\frac{ L}{\mu(1-\sigma_2(W))}\log\frac{1}{\epsilon}\right)$ communication and computation complexities for strongly convex and smooth problems and the $O(\sqrt{\frac{L}{ϵ(1-{\sigma }_2(W))}}\log \frac{1}{ϵ(1-{\sigma }_2(W))})$ complexities for non-strongly convex ones. Our communication complexities of the accelerated EXTRA are only worse by the factors of $(\log \frac{L}{\mu (1-{\sigma }_2(W))})$ and $(\log \frac{1}{ϵ(1-{\sigma }_2(W))})$ from the lower complexity bounds for strongly convex and non-strongly convex problems, respectively.