# Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2020.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning](https://mlsanity.com/paper/2108.10241/) (2021)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [Robust Collaborative Learning with Linear Gradient Overhead](https://mlsanity.com/paper/2209.10931/) (2022)
- [Over-the-Air Federated Edge Learning with Hierarchical Clustering](https://mlsanity.com/paper/2207.09232/) (2022)
- [Byzantine-Resilient Federated Learning at Edge](https://mlsanity.com/paper/2303.10434/) (2023)
- [Temporal Gradient Inversion Attacks with Robust Optimization](https://mlsanity.com/paper/2306.07883/) (2023)
- [A simplified convergence theory for Byzantine resilient stochastic gradient descent](https://mlsanity.com/paper/2208.11879/) (2022)
- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [Communication-efficient distributed eigenspace estimation with arbitrary node failures](https://mlsanity.com/paper/2206.00127/) (2022)
- [Byzantine-Resilient Federated PCA and Low Rank Column-wise Sensing](https://mlsanity.com/paper/2309.14512/) (2023)
- [Beyond Trade-offs: A Unified Framework for Privacy, Robustness, and Communication Efficiency in Federated Learning](https://mlsanity.com/paper/2508.12978/) (2025)
- [Robust and Efficient Collaborative Learning](https://mlsanity.com/paper/2510.08311/) (2025)
- [Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements](https://mlsanity.com/paper/2604.06282/) (2026)
- [Adversary-Robust Learning from Fully Asynchronous Directional Derivative Estimates](https://mlsanity.com/paper/2605.09337/) (2026)

## Abstract (arXiv)

We study distributed stochastic gradient descent (SGD) in the master-worker architecture under Byzantine attacks. We consider the heterogeneous data model, where different workers may have different local datasets, and we do not make any probabilistic assumptions on data generation. At the core of our algorithm, we use the polynomial-time outlier-filtering procedure for robust mean estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt gradients. In order to be able to apply their filtering procedure in our em heterogeneous data setting where workers compute em stochastic gradients, we derive a new matrix concentration result, which may be of independent interest. We provide convergence analyses for smooth strongly-convex and non-convex objectives. We derive our results under the bounded variance assumption on local stochastic gradients and a em deterministic condition on datasets, namely, gradient dissimilarity; and for both these quantities, we provide concrete bounds in the statistical heterogeneous data model. We give a trade-off between the mini-batch size for stochastic gradients and the approximation error. Our algorithm can tolerate up to frac14 fraction Byzantine workers. It can find approximate optimal parameters in the strongly-convex setting exponentially fast and reach to an approximate stationary point in the non-convex setting with a linear speed, thus, matching the convergence rates of vanilla SGD in the Byzantine-free setting. We also propose and analyze a Byzantine-resilient SGD algorithm with gradient compression, where workers send k random coordinates of their gradients. Under mild conditions, we show a fracdk-factor saving in communication bits as well as decoding complexity over our compression-free algorithm without affecting its convergence rate (order-wise) and the approximation error.