# Byzantine-Robust Decentralized Stochastic Optimization with Stochastic Gradient Noise-Independent Learning Error

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 10 Aug 2023.

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

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [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)
- [Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks](https://mlsanity.com/paper/1912.12716/) (2019)
- [Federated Learning for Edge Networks: Resource Optimization and Incentive Mechanism](https://mlsanity.com/paper/1911.05642/) (2019)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [BRIDGE: Byzantine-resilient Decentralized Gradient Descent](https://mlsanity.com/paper/1908.08098/) (2019)
- [ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning](https://mlsanity.com/paper/1708.08155/) (2017)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [Byzantine-Resilient Decentralized Stochastic Optimization with Robust Aggregation Rules](https://mlsanity.com/paper/2206.04568/) (2022)
- [Distributed Optimization Under Adversarial Nodes](https://mlsanity.com/paper/1606.08939/) (2016)
- [DSA: Decentralized Double Stochastic Averaging Gradient Algorithm](https://mlsanity.com/paper/1506.04216/) (2015)
- [Distributed Momentum for Byzantine-resilient Learning](https://mlsanity.com/paper/2003.00010/) (2020)
- [Decentralized learning for wireless communications and networking](https://mlsanity.com/paper/1503.08855/) (2015)
- [Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning](https://mlsanity.com/paper/1906.12345/) (2019)
- [Byzantine Resilient Non-Convex SVRG with Distributed Batch Gradient Computations](https://mlsanity.com/paper/1912.04531/) (2019)
- [Byzantine Fault-Tolerance in Peer-to-Peer Distributed Gradient-Descent](https://mlsanity.com/paper/2101.12316/) (2021)
- [On the Geometric Convergence of Byzantine-Resilient Distributed Optimization Algorithms](https://mlsanity.com/paper/2305.10810/) (2023)
- [Consensus based Detection in the Presence of Data Falsification Attacks](https://mlsanity.com/paper/1504.03413/) (2015)
- [Byzantine-Resilient Locally Optimum Detection Using Collaborative Autonomous Networks](https://mlsanity.com/paper/1803.01221/) (2018)

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

- [Adaptive Decentralized Federated Learning for Robust Optimization](https://mlsanity.com/paper/2512.02852/) (2025)
- [Topology-Independent Robustness of the Weighted Mean under Label Poisoning Attacks in Heterogeneous Decentralized Learning](https://mlsanity.com/paper/2601.02682/) (2026)

## Abstract (arXiv)

This paper studies Byzantine-robust stochastic optimization over a decentralized network, where every agent periodically communicates with its neighbors to exchange local models, and then updates its own local model by stochastic gradient descent (SGD). The performance of such a method is affected by an unknown number of Byzantine agents, which conduct adversarially during the optimization process. To the best of our knowledge, there is no existing work that simultaneously achieves a linear convergence speed and a small learning error. We observe that the learning error is largely dependent on the intrinsic stochastic gradient noise. Motivated by this observation, we introduce two variance reduction methods, stochastic average gradient algorithm (SAGA) and loopless stochastic variance-reduced gradient (LSVRG), to Byzantine-robust decentralized stochastic optimization for eliminating the negative effect of the stochastic gradient noise. The two resulting methods, BRAVO-SAGA and BRAVO-LSVRG, enjoy both linear convergence speeds and stochastic gradient noise-independent learning errors. Such learning errors are optimal for a class of methods based on total variation (TV)-norm regularization and stochastic subgradient update. We conduct extensive numerical experiments to demonstrate their effectiveness under various Byzantine attacks.