# Acceleration in Distributed Optimization under Similarity

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 38 references that are in the map.
- First posted on arXiv 24 Oct 2021.

## Builds on (most cited first, 25 of 25)

- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum](https://mlsanity.com/paper/1910.00643/) (2019)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Communication-Efficient Accurate Statistical Estimation](https://mlsanity.com/paper/1906.04870/) (2019)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks](https://mlsanity.com/paper/1809.00710/) (2018)
- [Multi-consensus Decentralized Accelerated Gradient Descent](https://mlsanity.com/paper/2005.00797/) (2020)
- [On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond](https://mlsanity.com/paper/1908.02246/) (2019)
- [Optimal Complexity and Certification of Bregman First-Order Methods](https://mlsanity.com/paper/1911.08510/) (2019)
- [Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations](https://mlsanity.com/paper/1805.08531/) (2018)
- [Revisiting EXTRA for Smooth Distributed Optimization](https://mlsanity.com/paper/2002.10110/) (2020)
- [Dual-Free Stochastic Decentralized Optimization with Variance Reduction](https://mlsanity.com/paper/2006.14384/) (2020)
- [Towards accelerated rates for distributed optimization over time-varying networks](https://mlsanity.com/paper/2009.11069/) (2020)
- [Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters](https://mlsanity.com/paper/1810.01053/) (2018)
- [Recent theoretical advances in decentralized distributed convex optimization](https://mlsanity.com/paper/2011.13259/) (2020)

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

- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [Federated Optimization with Doubly Regularized Drift Correction](https://mlsanity.com/paper/2404.08447/) (2024)
- [Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities](https://mlsanity.com/paper/2206.09446/) (2022)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approach](https://mlsanity.com/paper/2306.07159/) (2023)
- [Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning](https://mlsanity.com/paper/2409.14280/) (2024)
- [Optimal Data Splitting in Distributed Optimization for Machine Learning](https://mlsanity.com/paper/2401.07809/) (2024)
- [Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimization](https://mlsanity.com/paper/2506.05791/) (2025)
- [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026)
- [On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality](https://mlsanity.com/paper/2310.00419/) (2023)
- [Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity](https://mlsanity.com/paper/2405.16126/) (2024)
- [Distributed Optimization via Energy Conservation Laws in Dilated Coordinates](https://mlsanity.com/paper/2409.19279/) (2024)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking](https://mlsanity.com/paper/2509.18129/) (2025)
- [Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems](https://mlsanity.com/paper/2601.08614/) (2026)

## Abstract (arXiv)

We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. The loss functions of the agents are assumed to be textitsimilar, due to statistical data similarity or otherwise. In order to reduce the number of communications to reach a solution accuracy, we proposed a it preconditioned, accelerated distributed method. An varepsilon-solution is achieved in tildeObig(√fracβ/μ1-ρlog1/varepsilonbig) number of communications steps, where β/μ is the relative condition number between the global and local loss functions, and ρ characterizes the connectivity of the network. This rate matches (up to poly-log factors) lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest. Numerical results show significant communication savings with respect to existing accelerated distributed schemes, especially when solving ill-conditioned problems.