Unverified

Is There a First-Order Method that Only Converges to Local Minimax Optima?

Let $f\in C^2$ and define its saddle-gradient field by

F(x,y)=(\nabla_x f(x,y),-\nabla_y f(x,y)).

Assume $\|DF(z)\|\leq L$ for all relevant $z=(x,y)$ .

Construct a first-order method whose locally attracting stationary points are exactly, or are guaranteed to be, local minimax points in the sense above. In particular, can one remove the step-size and spectral restrictions in the existing two-timescale extragradient analysis and close the gap between its limit points and local minimax optima?

Alternatively, identify and justify a notion of local minimax optimality suitable for first-order methods---possibly the local restricted minimax notion---and give a first-order method that converges only to points satisfying it.

Download

Abstract

For nonconvex--nonconcave minimax optimization, first-order methods may converge to stationary points that are locally optimal for the reverse maximin problem rather than for the intended minimax problem. This motivates the longstanding question of whether a first-order method can converge only to local minimax optima. Two-timescale extragradient gives the first convergence result to refined second-order stationary points, but a gap remains between its limit points and local minimax optima. The appropriate notion of local optimality itself may also require refinement.

Background and progress

For a smooth objective $f(x,y)$ , Jin, Netrapalli, and Jordan define $(x^*,y^*)$ to be a local minimax point if there are $\delta_0>0$ and $h(\delta)\to0$ such that, for every $0<\delta\leq\delta_0$ ,

f(x^*,y)\leq f(x^*,y^*) \leq\max_{\|y'-y^*\|\leq h(\delta)}f(x,y')

whenever $\|x-x^*\|\leq\delta$ and $\|y-y^*\|\leq\delta$ [Jin et al., 2020]. Existing work initially focused on strict local minimax points, characterized by nondegenerate second-order sufficient conditions.

Chae, Kim, and Kim refine the second-order necessary condition using a restricted Schur complement and show that two-timescale extragradient converges locally only to such second-order stationary points under an additional condition [Chae et al., 2023]. Their result excludes some candidate points and depends on the step size, leaving a gap between the method's limit points and local minimax optima.

The source also proposes a local restricted minimax point, restricting the maximization neighborhood to the range of $\nabla^2_{yy}f(x^*,y^*)$ . This variant has a cleaner generalized-Schur-complement condition and excludes a questionable local minimax point of a concave-linear quadratic with no global minimax point. The open problem is posed directly in [Chae et al., 2023].

Reference papers

Open Problem: Is There a First-Order Method that Only Converges to Local Minimax Optima?Jiseok Chae, Kyuwon Kim, Donghwan KimProceedings of Thirty Sixth Conference on Learning Theory · 2023 ↗
Two-Timescale Extragradient for Finding Local Minimax PointsJ. Chae, K. Kim, D. Kim2023
What Is Local Optimality in Nonconvex--Nonconcave Minimax Optimization?C. Jin, P. Netrapalli, M. I. JordanProceedings of the International Conference on Machine Learning · 2020

Is There a First-Order Method that Only Converges to Local Minimax Optima?

Coming soon

Organizer