Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization
Lin, Tianyi Jin, Chi Jordan, Michael I.
Lin, Tianyi
Jin, Chi
Jordan, Michael I.
Supervisor
Department
Machine Learning
Embargo End Date
Type
Journal article
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
We provide a unified analysis of two-timescale gradient descent ascent (TTGDA) for solving structured nonconvex minimax optimization problems in the form of minx maxy?Y f(x, y), where the objective function f(x, y) is nonconvex in x and concave in y, and the constraint set Y ? R n is convex and bounded. In the convex-concave setting, the single-timescale gradient descent ascent (GDA) algorithm is widely used in applications and has been shown to have strong convergence guarantees. In more general settings, however, it can fail to converge. Our contribution is to design TTGDA algorithms that are effective beyond the convex-concave setting, efficiently finding a stationary point of the function ?(·) := maxy?Y f(·, y). We also establish theoretical bounds on the complexity of solving both smooth and nonsmooth nonconvex-concave minimax optimization problems. To the best of our knowledge, this is the first systematic analysis of TTGDA for nonconvex minimax optimization, shedding light on its superior performance in training generative adversarial networks (GANs) and in other real-world application problems.
Citation
T. Lin, C. Jin, and M. I. Jordan, “Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization,” Journal of Machine Learning Research, vol. 26, pp. 1–45, 2025, Accessed: Mar. 10, 2025. [Online]. Available: http://jmlr.org/papers/v26/22-0863.html.
Source
Journal of Machine Learning Research
Conference
Keywords
Structured nonconvex minimax optimization, two-timescale gradient descent
ascent, iteration complexity analysis
Subjects
Source
Publisher
Microtome Publishing