Two-timescale Extragradient for Finding Local Minimax Points
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization
Gradient descent-ascent (GDA) is a widely used algorithm for minimax optimization. However, GDA has been proved to converge to stationary points for nonconvex minimax optimization, which are suboptimal compared with loca…
Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm
Deciding whether saddle points exist or are approximable for nonconvex-nonconcave problems is usually intractable. This paper takes a step towards understanding a broad class of nonconvex-nonconcave minimax problems that…
Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems
This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax problems is computationally intractable. T…
Extragradient Type Methods for Riemannian Variational Inequality Problems
Riemannian convex optimization and minimax optimization have recently drawn considerable attention. Their appeal lies in their capacity to adeptly manage the non-convexity of the objective function as well as constraints…
Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization
Large scale convex-concave minimax problems arise in numerous applications, including game theory, robust training, and training of generative adversarial networks. Despite their wide applicability, solving such problems…
Generative Adversarial NetworkVocal Bursts Type Prediction