Two-timescale Extragradient for Finding Local Minimax Points
This work addresses a fundamental bottleneck in minimax optimization for machine learning and AI applications, offering a provable advancement over existing methods.
The paper tackles the challenge of optimizing minimax problems by proposing a two-timescale extragradient method, which converges to local minimax points under mild conditions and eliminates the need for a nondegenerate Hessian assumption, improving upon previous results.
Minimax problems are notoriously challenging to optimize. However, we present that the two-timescale extragradient method can be a viable solution. By utilizing dynamical systems theory, we show that it converges to points that satisfy the second-order necessary condition of local minimax points, under mild conditions that the two-timescale gradient descent ascent fails to work. This work provably improves upon all previous results on finding local minimax points, by eliminating a crucial assumption that the Hessian with respect to the maximization variable is nondegenerate.