Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
  Domain
  We study the problem of finding approximate first-order stationary points in
optimization problems of the form $\min_{x \in X} \max_{y \in Y} f(x,y)$, where
the sets $X,Y$ are convex and $Y$ is compact. The objective function $f$ is
smooth, but assumed neither convex in $x$ nor concave in $y$. Our approach
relies upon replacing the function $f(x,\cdot)$ with its $k$th order Taylor
approximation (in $y$) and finding a near-stationary point in the resulting
surrogate problem. To guarantee its success, we establish the following result:
let the Euclidean diameter of $Y$ be small in terms of the target accuracy
$\varepsilon$, namely $O(\varepsilon^{\frac{2}{k+1}})$ for $k \in \mathbb{N}$
and $O(\varepsilon)$ for $k = 0$, with the constant factors controlled by
certain regularity parameters of $f$; then any $\varepsilon$-stationary point
in the surrogate problem remains $O(\varepsilon)$-stationary for the initial
problem. Moreover, we show that these upper bounds are nearly optimal: the
aforementioned reduction provably fails when the diameter of $Y$ is larger. For
$0 \le k \le 2$ the surrogate function can be efficiently maximized in $y$; our
general approximation result then leads to efficient algorithms for finding a
near-stationary point in nonconvex-nonconcave min-max problems, for which we
also provide convergence guarantees.
