Before revision:  However, the classes of local min-max solutions which prior algorithms seek are only guaranteed to exist under very strong assumptions on f, such as convexity or monotonicity. We propose a notion of a greedy equilibrium pointfor min-max optimization and prove the existence of such a point for any function such that it and its first three derivatives are bounded. Informally , we say that a point (x^\star, y^\star) is an \varepsilon-greedy min-max equilibrium point of a function f: \mathbb{R^d \times \mathbb{R}^d \rightarrow \mathbb{R} }  if y^\star is a second-order local maximum for f(x^\star,\cdot) and, roughly, x^\star is a local minimum for a greedy optimization version of the function \max _y f(x, y ) which can be efficiently estimated using greedy algorithms.
After revision:  However, the classes of local min-max solutions which prior algorithms seek are only guaranteed to exist under very strong assumptions on f, such as convexity , monotonicity, or special properties of the starting point. In this paper, we propose an optimization model, the \varepsilon-greedy adversarial equilibrium, which 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 min-max equilibrium point of a function f: \mathbb{R^d \times \mathbb{R}^d \rightarrow \mathbb{R} } if y^\star is a second-order local maximum for f(x^\star,\cdot) and, roughly, x^\star is a local minimum for a greedy optimization version of the function \max _y f(x, y ) which can be efficiently estimated using greedy algorithms.