mlsanityData to 14 Oct 2026

A Tight Theory of Error Feedback Algorithms in Distributed Optimization

arXiv 2605.31594 ↗First posted 29 May 2026cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Communication costs are a major bottleneck in distributed learning and first-order optimization. A common approach to alleviate this issue is to compress the gradient information exchanged between agents. However, such compression typically degrades the convergence guarantees of gradient-based methods. Error feedback mechanisms provide a simple and computationally cheap remedy for this issue, but numerous variants have been proposed, and their relative performance remains poorly understood. This paper provides tight convergence analyses for two of the main error-feedback algorithms from the literature, the classic Error Feedback method (EF) and Error Feedback 21 (EF21), by identifying optimal step-size choices and constructing optimal Lyapunov functions tailored to each method. The results hold independently of the number of agents and recover the known best guarantees possible in the single-agent regime.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 32 of its 49 references that are in the map. First posted on arXiv 29 May 2026.

Builds on

32 of 49 references.

References · 32

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2018Sparsified SGD with Memorycited by 376
  4. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 310
  5. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 221
  6. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  7. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  8. 2020On Biased Compression for Distributed Learningcited by 140
  9. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  10. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  11. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 101
  12. 2019Communication-efficient distributed SGD with Sketchingcited by 81
20 more
  1. 2018Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimizationcited by 76
  2. 2020Linearly Converging Error Compensated SGDcited by 61
  3. 2019Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedbackcited by 50
  4. 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 46
  5. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
  6. 2023Momentum Provably Improves Error Feedback!cited by 31
  7. 2021Preserved central model for faster bidirectional compression in distributed settingscited by 21
  8. 2022EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimizationcited by 17
  9. 2023EControl: Fast Distributed Optimization with Compression and Error Controlcited by 15
  10. 2018Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guaranteescited by 11
  11. 2022PEPit: computer-assisted worst-case analyses of first-order optimization methods in Pythoncited by 11
  12. 2025Error Feedback for Muon and Friendscited by 11
  13. 2021EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedbackcited by 8
  14. 2019Analysis and Design of First-Order Distributed Optimization Algorithms over Time-Varying Graphscited by 7
  15. 2023Automated tight Lyapunov analysis for first-order methodscited by 6
  16. 2021ErrorCompensatedX: error compensation for variance reduced algorithmscited by 5
  17. 2017On reducing the communication cost of the diffusion LMS algorithmcited by 3
  18. 2022Analysis of Error Feedback in Federated Non-Convex Optimization with Biased Compressioncited by 3
  19. 2018A Canonical Form for First-Order Distributed Optimization Algorithmscited by 2
  20. 2025Tight analyses of first-order methods with error feedbackcited by 1

Built on by

Not cited yet.