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

Min-max optimization of a function f from ${\mathrm{ℝ}}^d\times {\mathrm{ℝ}}^d$ to $\mathrm{ℝ}$ is an important framework for modeling robustness in adversarial settings with applications to optimization, economics, and deep learning. Oftentimes, f is nonconvex–nonconcave, and finding a global min-max point is computationally intractable. There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization formulation. However, many of these alternative solution concepts guarantee the existence of solution points only under strong assumptions on f, such as convexity or monotonicity of its gradient. We propose a new solution concept, the $\epsilon$-greedy adversarial equilibrium, and show that it can serve as a computationally tractable alternative to min-max optimization. We prove the existence of such a point for any smooth bounded function with Lipschitz Hessian and give an algorithm that converges to an $\epsilon$-greedy adversarial equilibrium in a number of evaluations of f, ${\nabla }_{y}f(x,y)$, and ${\nabla }_y^{2}f(x,y)$ that is polynomial in d, $1/\epsilon$, and the bounds of f and its Lipschitz constant.

Funding: This work was supported by the National Science Foundation [Grant CCF-1908347].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2023.0262.