Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconcave min-max optimization

Min-max optimization of an objective function f ∶ R d ×R d → 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 ε-greedy adversarial equilibrium, and show that it can serve as a computationally tractable alternative to the minmax optimization model. Roughly, we say that a point (x ⋆ , y ⋆ ) is an ε-greedy adversarial equilibrium if y ⋆ is an ε-approximate local maximum for f (x ⋆ , ⋅), and x ⋆ is an ε-approximate local minimum for a "greedy approximation" to the function max z f (x, z) which can be efficiently estimated using secondorder 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 ε-greedy adversarial equilibrium in a number of evaluations of the function f , the max-player's gradient ∇ y f (x, y), and its Hessian ∇ 2 y f (x, y), that is polynomial in the dimension d, 1 ε, and the bounds on f and its Lipschitz constant.