# Communication-Efficient and Byzantine-Robust Distributed Learning with Error Feedback

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2019.

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

- [BROADCAST: Reducing Both Stochastic and Compression Noise to Robustify Communication-Efficient Federated Learning](https://mlsanity.com/paper/2104.06685/) (2021)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [Byzantine-Resilient Federated Learning at Edge](https://mlsanity.com/paper/2303.10434/) (2023)
- [FedREP: A Byzantine-Robust, Communication-Efficient and Privacy-Preserving Framework for Federated Learning](https://mlsanity.com/paper/2303.05206/) (2023)
- [Analysis of Error Feedback in Federated Non-Convex Optimization with Biased Compression](https://mlsanity.com/paper/2211.14292/) (2022)
- [Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top](https://mlsanity.com/paper/2206.00529/) (2022)
- [Stochastic Alternating Direction Method of Multipliers for Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/2106.06891/) (2021)
- [Optimal Compression of Unit Norm Vectors in the High Distortion Regime](https://mlsanity.com/paper/2307.07941/) (2023)
- [Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filtering](https://mlsanity.com/paper/2409.08640/) (2024)
- [Incentivize Contribution and Learn Parameters Too: Federated Learning with Strategic Data Owners](https://mlsanity.com/paper/2505.12010/) (2025)
- [Reconciling Communication Compression and Byzantine-Robustness in Distributed Learning](https://mlsanity.com/paper/2508.17129/) (2025)
- [Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget](https://mlsanity.com/paper/2601.18950/) (2026)
- [Robust Distributed Learning Against Both Distributional Shifts and Byzantine Attacks](https://mlsanity.com/paper/2210.16682/) (2022)
- [Byzantine-Robust and Communication-Efficient Distributed Training: Compressive and Cyclic Gradient Coding](https://mlsanity.com/paper/2603.28780/) (2026)
- [Expectation Maximization (EM) Converges for General Agnostic Mixtures](https://mlsanity.com/paper/2604.05842/) (2026)

## Abstract (arXiv)

We develop a communication-efficient distributed learning algorithm that is robust against Byzantine worker machines. We propose and analyze a distributed gradient-descent algorithm that performs a simple thresholding based on gradient norms to mitigate Byzantine failures. We show the (statistical) error-rate of our algorithm matches that of Yin et al.~citedong, which uses more complicated schemes (coordinate-wise median, trimmed mean). Furthermore, for communication efficiency, we consider a generic class of δ-approximate compressors from Karimireddi et al.~citeerrorfeed that encompasses sign-based compressors and top-k sparsification. Our algorithm uses compressed gradients and gradient norms for aggregation and Byzantine removal respectively. We establish the statistical error rate for non-convex smooth loss functions. We show that, in certain range of the compression factor δ, the (order-wise) rate of convergence is not affected by the compression operation. Moreover, we analyze the compressed gradient descent algorithm with error feedback (proposed in citeerrorfeed) in a distributed setting and in the presence of Byzantine worker machines. We show that exploiting error feedback improves the statistical error rate. Finally, we experimentally validate our results and show good performance in convergence for convex (least-square regression) and non-convex (neural network training) problems.