Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain

arXiv:2110.03950v2 Announce Type: replace-cross Abstract: 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,dot) 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 arepsilon, namely O(arepsilon^{frac{2}{k+1}}) for k in N and O(arepsilon) for k = 0, with the constant factors controlled by certain regularity parameters of f; then any arepsilon-stationary point in the surrogate problem remains O(arepsilon)-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.

Source: arXiv cs.LG | 2026-06-23