# Min-Max Optimization under Delays

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 13 Jul 2023.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [On the Convergence Rate of Incremental Aggregated Gradient Algorithms](https://mlsanity.com/paper/1506.02081/) (2015)
- [An Optimal Multistage Stochastic Gradient Method for Minimax Problems](https://mlsanity.com/paper/2002.05683/) (2020)
- [Distributed Statistical Min-Max Learning in the Presence of Byzantine Agents](https://mlsanity.com/paper/2204.03187/) (2022)

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

- [DASA: Delay-Adaptive Multi-Agent Stochastic Approximation](https://mlsanity.com/paper/2403.17247/) (2024)

## Abstract (arXiv)

Delays and asynchrony are inevitable in large-scale machine-learning problems where communication plays a key role. As such, several works have extensively analyzed stochastic optimization with delayed gradients. However, as far as we are aware, no analogous theory is available for min-max optimization, a topic that has gained recent popularity due to applications in adversarial robustness, game theory, and reinforcement learning. Motivated by this gap, we examine the performance of standard min-max optimization algorithms with delayed gradient updates. First, we show (empirically) that even small delays can cause prominent algorithms like Extra-gradient (textttEG) to diverge on simple instances for which textttEG guarantees convergence in the absence of delays. Our empirical study thus suggests the need for a careful analysis of delayed versions of min-max optimization algorithms. Accordingly, under suitable technical assumptions, we prove that Gradient Descent-Ascent (textttGDA) and textttEG with delayed updates continue to guarantee convergence to saddle points for convex-concave and strongly convex-strongly concave settings. Our complexity bounds reveal, in a transparent manner, the slow-down in convergence caused by delays.