Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
share
We study the problem of finding approximate first-order stationary points in optimization problems of the form min_x ∈ Xmax_y ∈ 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 ε, namely O(ε^2/k+1) for k ∈ℕ and O(ε) for k = 0, with the constant factors controlled by certain regularity parameters of f; then any ε-stationary point in the surrogate problem remains O(ε)-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.
READ FULL TEXT