# Minimax Optimization with Smooth Algorithmic Adversaries

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 73 references that are in the map.
- First posted on arXiv 2 Jun 2021.

## Builds on (most cited first, 30 of 42)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Which Training Methods for GANs do actually Converge?](https://mlsanity.com/paper/1801.04406/) (2018)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Unrolled Generative Adversarial Networks](https://mlsanity.com/paper/1611.02163/) (2016)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Generalized Inner Loop Meta-Learning](https://mlsanity.com/paper/1910.01727/) (2019)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Gradient descent GAN optimization is locally stable](https://mlsanity.com/paper/1706.04156/) (2017)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications](https://mlsanity.com/paper/1902.08294/) (2019)
- [Torchmeta: A Meta-Learning library for PyTorch](https://mlsanity.com/paper/1909.06576/) (2019)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [Stable Opponent Shaping in Differentiable Games](https://mlsanity.com/paper/1811.08469/) (2018)
- [On Gradient-Based Learning in Continuous Games](https://mlsanity.com/paper/1804.05464/) (2018)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games](https://mlsanity.com/paper/1901.00838/) (2019)

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

- [Proximal Learning With Opponent-Learning Awareness](https://mlsanity.com/paper/2210.10125/) (2022)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [SAN: Inducing Metrizability of GAN with Discriminative Normalized Linear Layer](https://mlsanity.com/paper/2301.12811/) (2023)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [On adversarial robustness and the use of Wasserstein ascent-descent dynamics to enforce it](https://mlsanity.com/paper/2301.03662/) (2023)
- [Convergence of GANs Training: A Game and Stochastic Control Methodology](https://mlsanity.com/paper/2112.00222/) (2021)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Iterative Minimax Games with Coupled Linear Constraints](https://mlsanity.com/paper/2212.04672/) (2022)

## Abstract (arXiv)

This paper considers minimax optimization minx maxy f(x, y) in the challenging setting where f can be both nonconvex in x and nonconcave in y. Though such optimization problems arise in many machine learning paradigms including training generative adversarial networks (GANs) and adversarially robust models, many fundamental issues remain in theory, such as the absence of efficiently computable optimality notions, and cyclic or diverging behavior of existing algorithms. Our framework sprouts from the practical consideration that under a computational budget, the max-player can not fully maximize f(x,·) since nonconcave maximization is NP-hard in general. So, we propose a new algorithm for the min-player to play against smooth algorithms deployed by the adversary (i.e., the max-player) instead of against full maximization. Our algorithm is guaranteed to make monotonic progress (thus having no limit cycles), and to find an appropriate "stationary point" in a polynomial number of iterations. Our framework covers practical settings where the smooth algorithms deployed by the adversary are multi-step stochastic gradient ascent, and its accelerated version. We further provide complementing experiments that confirm our theoretical findings and demonstrate the effectiveness of the proposed approach in practice.