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
$\varepsilon$-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 $\varepsilon$-greedy
adversarial equilibrium if $y^\star$ is an $\varepsilon$-approximate local
maximum for $f(x^\star,\cdot)$, and $x^\star$ is an $\varepsilon$-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 $\varepsilon$-greedy adversarial
equilibrium in a number of evaluations of the function $f$, the max-player's
gradient $\nabla_y f(x,y)$, and its Hessian $\nabla^2_y f(x,y)$, that is
polynomial in the dimension $d$, $1/\varepsilon$, and the bounds on $f$ and its
Lipschitz constant.
