# Approximate Byzantine Fault-Tolerance in Distributed Optimization

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2021.

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

- [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)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Achieving Byzantine-Resilient Federated Learning via Layer-Adaptive Sparsified Model Aggregation](https://mlsanity.com/paper/2409.01435/) (2024)
- [Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates](https://mlsanity.com/paper/2402.12780/) (2024)
- [Robust Collaborative Learning with Linear Gradient Overhead](https://mlsanity.com/paper/2209.10931/) (2022)
- [Adaptive Gradient Clipping for Robust Federated Learning](https://mlsanity.com/paper/2405.14432/) (2024)
- [Fine-grained Poisoning Attack to Local Differential Privacy Protocols for Mean and Variance Estimation](https://mlsanity.com/paper/2205.11782/) (2022)
- [Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy](https://mlsanity.com/paper/2108.11769/) (2021)
- [Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers](https://mlsanity.com/paper/2312.12835/) (2023)
- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [Identify Backdoored Model in Federated Learning via Individual Unlearning](https://mlsanity.com/paper/2411.01040/) (2024)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [On the Relevance of Byzantine Robust Optimization Against Data Poisoning](https://mlsanity.com/paper/2405.00491/) (2024)
- [Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning](https://mlsanity.com/paper/2506.18020/) (2025)
- [Communication-Efficient {Federated} Learning Using Censored Heavy Ball Descent](https://mlsanity.com/paper/2209.11944/) (2022)
- [Decoupled Vertical Federated Learning for Practical Training on Vertically Partitioned Data](https://mlsanity.com/paper/2403.03871/) (2024)
- [Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filtering](https://mlsanity.com/paper/2409.08640/) (2024)
- [Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2110.10858/) (2021)
- [Impact of Redundancy on Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2211.08622/) (2022)
- [SABLE: Secure And Byzantine robust LEarning](https://mlsanity.com/paper/2309.05395/) (2023)
- [LiD-FL: Towards List-Decodable Federated Learning](https://mlsanity.com/paper/2408.04963/) (2024)
- [GRANITE : a Byzantine-Resilient Dynamic Gossip Learning Framework](https://mlsanity.com/paper/2504.17471/) (2025)
- [Private Aggregation for Byzantine-Resilient Heterogeneous Federated Learning](https://mlsanity.com/paper/2506.09870/) (2025)
- [Trade-off in Estimating the Number of Byzantine Clients in Federated Learning](https://mlsanity.com/paper/2510.04432/) (2025)
- [Practical Validity Conditions for Byzantine-Tolerant Federated Learning](https://mlsanity.com/paper/2605.15887/) (2026)

## Abstract (arXiv)

This paper considers the problem of Byzantine fault-tolerance in distributed multi-agent optimization. In this problem, each agent has a local cost function, and in the fault-free case, the goal is to design a distributed algorithm that allows all the agents to find a minimum point of all the agents' aggregate cost function. We consider a scenario where some agents might be Byzantine faulty that renders the original goal of computing a minimum point of all the agents' aggregate cost vacuous. A more reasonable objective for an algorithm in this scenario is to allow all the non-faulty agents to compute the minimum point of only the non-faulty agents' aggregate cost. Prior work shows that if there are up to f (out of n) Byzantine agents then a minimum point of the non-faulty agents' aggregate cost can be computed exactly if and only if the non-faulty agents' costs satisfy a certain redundancy property called 2f-redundancy. However, 2f-redundancy is an ideal property that can be satisfied only in systems free from noise or uncertainties, which can make the goal of exact fault-tolerance unachievable in some applications. Thus, we introduce the notion of (f,ε)-resilience, a generalization of exact fault-tolerance wherein the objective is to find an approximate minimum point of the non-faulty aggregate cost, with ε accuracy. This approximate fault-tolerance can be achieved under a weaker condition that is easier to satisfy in practice, compared to 2f-redundancy. We obtain necessary and sufficient conditions for achieving (f,ε)-resilience characterizing the correlation between relaxation in redundancy and approximation in resilience. In case when the agents' cost functions are differentiable, we obtain conditions for (f,ε)-resilience of the distributed gradient-descent method when equipped with robust gradient aggregation.