Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization

Understand

Min-max optimization of an objective function $f: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$ is an important model for robustness in an adversarial setting, with applications to many areas including optimization, economics, and deep learning.

• In many applications $f$ may be nonconvex-nonconcave, and finding a global min-max point may be computationally intractable.
• There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization model.
• However, many of the alternative models have solution points which are only guaranteed to exist under strong assumptions on $f$, such as convexity, monotonicity, or special properties of the starting point.