Tight analyses of first-order methods with error feedback
Not on the map. Why?
Abstract (arXiv)
Communication between agents often constitutes a major computational bottleneck in distributed learning. One of the most common mitigation strategies is to compress the information exchanged, thereby reducing communication overhead. To counteract the degradation in convergence associated with compressed communication, error feedback schemes -- most notably EF and EF21 -- were introduced. In this work, we provide a tight analysis of both of these methods. Specifically, we find the Lyapunov function that yields the best possible convergence rate for each method -- with matching lower bounds. This principled approach yields sharp performance guarantees and enables a rigorous, apples-to-apples comparison between EF, EF21, and compressed gradient descent. Our analysis is carried out in the simplified single-agent setting, which allows for clean theoretical insights and fair comparison of the underlying mechanisms.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 48 of its 68 references that are in the map. First posted on arXiv 5 Jun 2025.
Builds on
48 of 68 references.
References · 48
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
- 2019Advances and Open Problems in Federated Learningcited by 3,046
- 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
- 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 419
- 2018Sparsified SGD with Memorycited by 376
- 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 356
- 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 310
- 2018The Convergence of Sparsified Gradient Methodscited by 229
- 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 221
- 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 160
- 2020On Biased Compression for Distributed Learningcited by 140
- 2017Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradientscited by 139
36 more
- 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
- 2020Dynamic Model Pruning with Feedbackcited by 125
- 2019Distributed Learning with Compressed Gradient Differencescited by 112
- 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 99
- 2019Natural Compression for Distributed Deep Learningcited by 90
- 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
- 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
- 2019Communication-efficient distributed SGD with Sketchingcited by 81
- 2018Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimizationcited by 76
- 2020Linearly Converging Error Compensated SGDcited by 61
- 2018Distributed learning with compressed gradientscited by 55
- 2019Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedbackcited by 50
- 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 46
- 2022BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compressioncited by 41
- 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 37
- 2019A Double Residual Compression Algorithm for Efficient Distributed Learningcited by 31
- 2023Momentum Provably Improves Error Feedback!cited by 31
- 2022EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compressioncited by 28
- 2023DoCoFL: Downlink Compression for Cross-Device Federated Learningcited by 28
- 20223PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregationcited by 27
- 2021CANITA: Faster Rates for Distributed Convex Optimization with Communication Compressioncited by 23
- 2021Preserved central model for faster bidirectional compression in distributed settingscited by 21
- 2021Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networkscited by 19
- 2015Exact Worst-case Performance of First-order Methods for Composite Convex Optimizationcited by 16
- 2022Adaptive Compression for Communication-Efficient Distributed Trainingcited by 16
- 2019Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functionscited by 12
- 2021Communication-Compressed Adaptive Gradient Method for Distributed Nonconvex Optimizationcited by 12
- 2018Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guaranteescited by 11
- 2019Distributed Fixed Point Methods with Compressed Iteratescited by 11
- 2022PEPit: computer-assisted worst-case analyses of first-order optimization methods in Pythoncited by 11
- 2016On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functionscited by 9
- 2019A frequency-domain analysis of inexact gradient methodscited by 7
- 2023Automated tight Lyapunov analysis for first-order methodscited by 6
- 2023On Fundamental Proof Structures in First-Order Optimizationcited by 4
- 2017On reducing the communication cost of the diffusion LMS algorithmcited by 3
- 2023Counter-examples in first-order optimization: a constructive approachcited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.