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\left(\left(\frac{L}{\mu }+\frac{1}{1-{\sigma }_2(W)}\right)\log \frac{1}{\epsilon (1-{\sigma }_2(W))}\right)$ 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\left(\left(\frac{L}{\epsilon }+\frac{1}{1-{\sigma }_2(W)}\right)\log \frac{1}{1-{\sigma }_2(W)}\right)$ 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\left(\sqrt{\frac{L}{\epsilon (1-{\sigma }_2(W))}}\log \frac{1}{\epsilon (1-{\sigma }_2(W))}\right)$ complexities for non-strongly convex ones. Our communication complexities of the accelerated EXTRA are only worse by the factors of $\left(\log \frac{L}{\mu (1-{\sigma }_2(W))}\right)$ and $\left(\log \frac{1}{\epsilon (1-{\sigma }_2(W))}\right)$ from the lower complexity bounds for strongly convex and non-strongly convex problems, respectively.

References in corpus (6)

• Optimal Distributed Online Prediction using Mini-Batches
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
• A Unification and Generalization of Exact Distributed First Order Methods

Cited by in corpus (4)

• Recent theoretical advances in decentralized distributed convex optimization
• Dual-Free Stochastic Decentralized Optimization with Variance Reduction
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization
• PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction