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 kth 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.