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 minx ∈ X maxy ∈ 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,·) 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^frac2k+1) for k ∈ mathbbN 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 ≤ k ≤ 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.