# Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 24 Sep 2023.

## Builds on (most cited first, 27 of 27)

- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Differentially Private Federated Learning on Heterogeneous Data](https://mlsanity.com/paper/2111.09278/) (2021)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent](https://mlsanity.com/paper/1705.05491/) (2017)
- [Byzantine-Resilient Non-Convex Stochastic Gradient Descent](https://mlsanity.com/paper/2012.14368/) (2020)
- [Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)](https://mlsanity.com/paper/2008.00742/) (2020)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [On the linear convergence of the stochastic gradient method with constant step-size](https://mlsanity.com/paper/1712.01906/) (2017)

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

- [The Utility and Complexity of in- and out-of-Distribution Machine Unlearning](https://mlsanity.com/paper/2412.09119/) (2024)
- [Achieving Byzantine-Resilient Federated Learning via Layer-Adaptive Sparsified Model Aggregation](https://mlsanity.com/paper/2409.01435/) (2024)
- [Detecting Backdoor Attacks in Federated Learning via Direction Alignment Inspection](https://mlsanity.com/paper/2503.07978/) (2025)
- [Adaptive Gradient Clipping for Robust Federated Learning](https://mlsanity.com/paper/2405.14432/) (2024)
- [Unified Breakdown Analysis for Byzantine Robust Gossip](https://mlsanity.com/paper/2410.10418/) (2024)
- [Towards Trustworthy Federated Learning with Untrusted Participants](https://mlsanity.com/paper/2505.01874/) (2025)
- [SoK: Blockchain-Based Decentralized AI (DeAI)](https://mlsanity.com/paper/2411.17461/) (2024)
- [Fine-Tuning Personalization in Federated Learning to Mitigate Adversarial Clients](https://mlsanity.com/paper/2409.20329/) (2024)
- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [ByzFL: Research Framework for Robust Federated Learning](https://mlsanity.com/paper/2505.24802/) (2025)
- [The poison of dimensionality](https://mlsanity.com/paper/2409.17328/) (2024)
- [Bant: Byzantine Antidote via Trial Function and Trust Scores](https://mlsanity.com/paper/2505.07614/) (2025)
- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [Reconciling Communication Compression and Byzantine-Robustness in Distributed Learning](https://mlsanity.com/paper/2508.17129/) (2025)
- [Byzantine Machine Learning: MultiKrum and an optimal notion of robustness](https://mlsanity.com/paper/2602.03899/) (2026)
- [mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environments](https://mlsanity.com/paper/2605.07841/) (2026)
- [On the Gradient Heterogeneity Dynamics of Adversarially Robust Federated Regression](https://mlsanity.com/paper/2609.25705/) (2026)
- [LiD-FL: Towards List-Decodable Federated Learning](https://mlsanity.com/paper/2408.04963/) (2024)
- [FL-CLEANER: byzantine and backdoor defense by CLustering Errors of Activation maps in Non-iid fedErated leaRning](https://mlsanity.com/paper/2501.12123/) (2025)
- [GRANITE : a Byzantine-Resilient Dynamic Gossip Learning Framework](https://mlsanity.com/paper/2504.17471/) (2025)
- [From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity](https://mlsanity.com/paper/2602.03329/) (2026)
- [Byzantine-Robust Optimization under (L0, L1)-Smoothness](https://mlsanity.com/paper/2603.12512/) (2026)
- [Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds](https://mlsanity.com/paper/2604.10179/) (2026)
- [Defending Against Backdoor Attacks via Alignment Checking in Model-Contrastive Federated Learning](https://mlsanity.com/paper/2607.26933/) (2026)
- [Robustifying Asynchronous SGD via Soft Throttling](https://mlsanity.com/paper/2609.39357/) (2026)
- [FUSE: Fairness-aware Update Screening against Byzantine Exploitation in q-Fair Federated Learning](https://mlsanity.com/paper/2610.20264/) (2026)

## Abstract (arXiv)

The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, established lower bounds on the learning error are essentially vacuous and greatly mismatch empirical observations. This is because the heterogeneity model considered is too restrictive and does not cover basic learning tasks such as least-squares regression. We consider in this paper a more realistic heterogeneity model, namely (G,B)-gradient dissimilarity, and show that it covers a larger class of learning problems than existing theory. Notably, we show that the breakdown point under heterogeneity is lower than the classical fraction 1/2. We also prove a new lower bound on the learning error of any distributed learning algorithm. We derive a matching upper bound for a robust variant of distributed gradient descent, and empirically show that our analysis reduces the gap between theory and practice.