# Distributed Statistical Min-Max Learning in the Presence of Byzantine Agents

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 34 references that are in the map.
- First posted on arXiv 7 Apr 2022.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Robust Federated Learning: The Case of Affine Distribution Shifts](https://mlsanity.com/paper/2006.08907/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [DRACO: Byzantine-resilient Distributed Training via Redundant Gradients](https://mlsanity.com/paper/1803.09877/) (2018)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent](https://mlsanity.com/paper/1705.05491/) (2017)
- [On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient](https://mlsanity.com/paper/1803.06573/) (2018)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Distributed Optimization Under Adversarial Nodes](https://mlsanity.com/paper/1606.08939/) (2016)
- [Convergence Rate of O(1/k) for Optimistic Gradient and Extra-gradient Methods in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/1906.01115/) (2019)

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

- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Min-Max Optimization under Delays](https://mlsanity.com/paper/2307.06886/) (2023)

## Abstract (arXiv)

Recent years have witnessed a growing interest in the topic of min-max optimization, owing to its relevance in the context of generative adversarial networks (GANs), robust control and optimization, and reinforcement learning. Motivated by this line of work, we consider a multi-agent min-max learning problem, and focus on the emerging challenge of contending with worst-case Byzantine adversarial agents in such a setup. By drawing on recent results from robust statistics, we design a robust distributed variant of the extra-gradient algorithm - a popular algorithmic approach for min-max optimization. Our main contribution is to provide a crisp analysis of the proposed robust extra-gradient algorithm for smooth convex-concave and smooth strongly convex-strongly concave functions. Specifically, we establish statistical rates of convergence to approximate saddle points. Our rates are near-optimal, and reveal both the effect of adversarial corruption and the benefit of collaboration among the non-faulty agents. Notably, this is the first paper to provide formal theoretical guarantees for large-scale distributed min-max learning in the presence of adversarial agents.