# Revisiting EXTRA for Smooth Distributed Optimization

arXiv: https://arxiv.org/abs/2002.10110 · HTML: https://mlsanity.com/paper/2002.10110/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2020.

## Built on by (most cited first, 12 of 12)

- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Push--Pull with Device Sampling](https://mlsanity.com/paper/2206.04113/) (2022)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality](https://mlsanity.com/paper/2310.00419/) (2023)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [Fast networked data selection via distributed smoothed quantile estimation](https://mlsanity.com/paper/2406.01929/) (2024)
- [Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps](https://mlsanity.com/paper/2407.02689/) (2024)
- [Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking](https://mlsanity.com/paper/2509.18129/) (2025)
- [Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothness](https://mlsanity.com/paper/2601.03566/) (2026)

## Abstract (arXiv)

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.