# Robust Distributed Optimization With Randomly Corrupted Gradients

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 58 references that are in the map.
- First posted on arXiv 28 Jun 2021.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [How To Backdoor Federated Learning](https://mlsanity.com/paper/1807.00459/) (2018)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Large Batch Training of Convolutional Networks](https://mlsanity.com/paper/1708.03888/) (2017)
- [Attack of the Tails: Yes, You Really Can Backdoor Federated Learning](https://mlsanity.com/paper/2007.05084/) (2020)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Can You Really Backdoor Federated Learning?](https://mlsanity.com/paper/1911.07963/) (2019)
- [Adversarial Training and Robustness for Multiple Perturbations](https://mlsanity.com/paper/1904.13000/) (2019)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks](https://mlsanity.com/paper/1912.12716/) (2019)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning](https://mlsanity.com/paper/1708.08155/) (2017)
- [Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/1806.05358/) (2018)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [The Power of Normalization: Faster Evasion of Saddle Points](https://mlsanity.com/paper/1611.04831/) (2016)
- [On the Convergence Rate of Incremental Aggregated Gradient Algorithms](https://mlsanity.com/paper/1506.02081/) (2015)
- [On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond](https://mlsanity.com/paper/1908.02246/) (2019)
- [The Internet of Things: Secure Distributed Inference](https://mlsanity.com/paper/1806.09199/) (2018)
- [Distributed stochastic optimization via matrix exponential learning](https://mlsanity.com/paper/1606.01190/) (2016)
- [Distributed Learning for Stochastic Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/1608.00039/) (2016)
- [Distributed Online Learning via Cooperative Contextual Bandits](https://mlsanity.com/paper/1308.4568/) (2013)
- [Hyperfast Second-Order Local Solvers for Efficient Statistically Preconditioned Distributed Optimization](https://mlsanity.com/paper/2102.08246/) (2021)
- [Resilient Primal-Dual Optimization Algorithms for Distributed Resource Allocation](https://mlsanity.com/paper/2001.00612/) (2020)
- [Gradient Methods for Problems with Inexact Model of the Objective](https://mlsanity.com/paper/1902.09001/) (2019)
- [Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games](https://mlsanity.com/paper/1304.4577/) (2013)
- [On Robustness of the Normalized Subgradient Method with Randomly Corrupted Subgradients](https://mlsanity.com/paper/2009.13725/) (2020)

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

- [AFLGuard: Byzantine-robust Asynchronous Federated Learning](https://mlsanity.com/paper/2212.06325/) (2022)
- [Federated Learning Resilient to Byzantine Attacks and Data Heterogeneity](https://mlsanity.com/paper/2403.13374/) (2024)
- [SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning](https://mlsanity.com/paper/2310.04918/) (2023)
- [Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients](https://mlsanity.com/paper/2408.09539/) (2024)
- [Communication-Efficient {Federated} Learning Using Censored Heavy Ball Descent](https://mlsanity.com/paper/2209.11944/) (2022)
- [Federated Learning Robust to Byzantine Attacks: Achieving Zero Optimality Gap](https://mlsanity.com/paper/2308.10427/) (2023)

## Abstract (arXiv)

In this paper, we propose a first-order distributed optimization algorithm that is provably robust to Byzantine failures-arbitrary and potentially adversarial behavior, where all the participating agents are prone to failure. We model each agent's state over time as a two-state Markov chain that indicates Byzantine or trustworthy behaviors at different time instants. We set no restrictions on the maximum number of Byzantine agents at any given time. We design our method based on three layers of defense: 1) temporal robust aggregation, 2) spatial robust aggregation, and 3) gradient normalization. We study two settings for stochastic optimization, namely Sample Average Approximation and Stochastic Approximation. We provide convergence guarantees of our method for strongly convex and smooth non-convex cost functions.