mlsanityData to 7 Oct 2026

Acceleration in Distributed Optimization under Similarity

arXiv 2110.12347 ↗First posted 24 Oct 2021math.OC cs.LGcited by 17

Not on the map. Why?

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.

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

Builds on

25 of 38 references.

References · 25

  1. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  2. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  3. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  4. 2019SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentumcited by 121
  5. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  6. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
  7. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  8. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  9. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  10. 2021Acceleration Methodscited by 48
  11. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  12. 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 42
13 more
  1. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  2. 2019Communication-Efficient Accurate Statistical Estimationcited by 32
  3. 2020Statistically Preconditioned Accelerated Gradient Method for Distributed Optimizationcited by 29
  4. 2018A Dual Approach for Optimal Algorithms in Distributed Optimization over Networkscited by 27
  5. 2020Multi-consensus Decentralized Accelerated Gradient Descentcited by 20
  6. 2019On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyondcited by 18
  7. 2019Optimal Complexity and Certification of Bregman First-Order Methodscited by 16
  8. 2018Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterationscited by 15
  9. 2020Revisiting EXTRA for Smooth Distributed Optimizationcited by 12
  10. 2020Dual-Free Stochastic Decentralized Optimization with Variance Reductioncited by 12
  11. 2020Towards accelerated rates for distributed optimization over time-varying networkscited by 10
  12. 2018Decentralized Accelerated Gradient Methods With Increasing Penalty Parameterscited by 8
  13. 2020Recent theoretical advances in decentralized distributed convex optimizationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 3; 2024: 6; 2025: 3; 2026: 2.

17 papers.

Sort:

  1. 2022Faster federated optimization under second-order similaritycited by 18
  2. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  3. 2024Federated Optimization with Doubly Regularized Drift Correctioncited by 10
  4. 2022Optimal Gradient Sliding and its Application to Distributed Optimization Under Similaritycited by 9
  5. 2022Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalitiescited by 8
  6. 2024Stabilized Proximal-Point Methods for Federated Optimizationcited by 6
  7. 2023On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approachcited by 4
  8. 2024Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learningcited by 2
  9. 2024Optimal Data Splitting in Distributed Optimization for Machine Learningcited by 1
  10. 2025Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimizationcited by 1
  11. 2023On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequalitycited by 0
  12. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
5 more
  1. 2024Distributed Optimization via Energy Conservation Laws in Dilated Coordinatescited by 0
  2. 2025Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimizationcited by 0
  3. 2025Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Trackingcited by 0
  4. 2026Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problemscited by 0
  5. 2026Improved Convergence Analysis of Topology Dependence in Decentralized SGDcited by 0