Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
This addresses a theoretical bottleneck in nonconvex-nonconcave optimization, providing a method for finding stationary points under specific domain size conditions, which is incremental but offers new algorithmic insights.
The paper tackles the problem of finding approximate first-order stationary points in nonconvex-nonconcave min-max optimization by using Taylor approximations to create a surrogate problem, showing that this approach succeeds when the maximization domain is small (e.g., O(ε^(2/(k+1))) for k≥1) and fails otherwise, with efficient algorithms and convergence guarantees for k≤2.
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.