# Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2025.

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

- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneity](https://mlsanity.com/paper/2506.09438/) (2025)
- [mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environments](https://mlsanity.com/paper/2605.07841/) (2026)
- [A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling](https://mlsanity.com/paper/2606.01720/) (2026)
- [Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds](https://mlsanity.com/paper/2604.10179/) (2026)
- [Robustifying Asynchronous SGD via Soft Throttling](https://mlsanity.com/paper/2609.39357/) (2026)

## Abstract (arXiv)

In this paper, we establish tight lower bounds for Byzantine-robust distributed first-order stochastic optimization methods in both strongly convex and non-convex stochastic optimization. We reveal that when the distributed nodes have heterogeneous data, the convergence error comprises two components: a non-vanishing Byzantine error and a vanishing optimization error. We establish the lower bounds on the Byzantine error and on the minimum number of queries to a stochastic gradient oracle required to achieve an arbitrarily small optimization error. Nevertheless, we identify significant discrepancies between our established lower bounds and the existing upper bounds. To fill this gap, we leverage the techniques of Nesterov's acceleration and variance reduction to develop novel Byzantine-robust distributed stochastic optimization methods that provably match these lower bounds, up to logarithmic factors, implying that our established lower bounds are tight.