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

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. We propose an optimization model, the $\epsilon$-greedy adversarial equilibrium, and show that it can serve as a computationally tractable alternative to the min-max optimization model. Roughly, we say that a point $(x^{\star },y^{\star })$ is an $\epsilon$-greedy adversarial equilibrium if $y^{\star }$ is an $\epsilon$-approximate local maximum for $f(x^{\star },\cdot )$, and $x^{\star }$ is an $\epsilon$-approximate local minimum for a “greedy approximation” to the function ${\max }_{z}f(x,z)$ which can be efficiently estimated using second-order optimization algorithms. We prove the existence of such a point for any smooth function which is bounded and has Lipschitz Hessian. To prove existence, we introduce an algorithm that converges from any starting point to an $\epsilon$-greedy adversarial equilibrium in a number of evaluations of the function $f$, the max-player’s gradient ${\mathrm{\nabla }}_{y}f(x,y)$, and its Hessian ${\mathrm{\nabla }}_y^{2}f(x,y)$, that is polynomial in the dimension $d$, $1\mathrm{/}\epsilon$, and the bounds on $f$ and its Lipschitz constant.