Abstract
This paper provides a rigorous theoretical foundation for "two-time-scale" Gradient Descent-Ascent (GDA), a popular but often unstable method for solving min-max optimization problems. By analyzing the algorithm in continuous time using singular perturbation theory, we derive improved convergence rates for several complex objective function classes, including those that are nonconvex and nonconcave. Our analysis improves the complexity for Polyak-Lojasiewicz (PL) objectives and provides a unified framework for various structural conditions.
Introduction
Min-max optimization—finding $\min_x \max_y f(x,y)$—is the engine behind modern AI breakthroughs like Generative Adversarial Networks (GANs) and robust machine learning. However, these problems are notoriously difficult to solve. The most common approach, simultaneous GDA, often fails to converge, circling endlessly or diverging even in simple cases like bilinear games.
While researchers often use "two-time-scale" updates (where one variable moves much faster than the other) as a heuristic to stabilize training, theoretical guarantees for these methods have been sparse, especially when the objective function is nonconvex or nonconcave. This paper seeks to close that gap by characterizing exactly how fast these dynamics converge under various mathematical conditions.
Methodology
The analysis shifts from discrete-time steps to continuous-time dynamics modeled by differential equations. This approach allows for the application of powerful tools from control theory and singular perturbation analysis.
Two-Time-Scale Dynamics
The system is modeled with two step-sizes, $\alpha$ and $\beta$, where $\alpha \ll \beta$. This separation of scales ensures that the maximizer ($y$) moves much faster than the minimizer ($x$), effectively allowing the "fast" variable to track the optimal response to the "slow" variable. This time-scale separation is mathematically essential for stability in nonconvex settings, allowing the maximizer to "settle" into a peak before the minimizer makes its next move.
Coupling Lyapunov Functions
To prove convergence, we construct a specialized "energy function" $V(x, y) = V_1(x, y) + \frac{\gamma \alpha}{\beta} V_2(x, y)$. By analyzing how this combined function decays over time, we can prove convergence even when the individual components are highly coupled and non-linear. This singular perturbation approach decouples the interactions between the fast and slow dynamics.
Key Results and Insights
The paper provides a single analytical recipe that works across four distinct problem classes: Two-sided PL, One-sided PL, Nonconvex-Strongly Concave, and Strongly Convex-Nonconcave.
As shown in Figure 1, the main contributions are summarized in improved upper bounds for convergence rates (the time required to reach an $\epsilon$-accurate solution):
- Improved Complexity for PL Functions: For functions satisfying the Polyak-Lojasiewicz (PL) condition, the analysis shows convergence scales with $\kappa^2$ (the condition number) rather than the $\kappa^3$ reported in previous literature. This settles a previous conjecture about whether such an improvement was possible.
- Simplicity in Analysis: By using continuous-time ODEs, we achieve the same convergence rates as complex "nested-loop" algorithms but with a much simpler "single-loop" implementation.
- Stationary Point Convergence: For the Nonconvex-PL case, the algorithm is proven to find a stationary point with a rate of $O(1/\sqrt{T})$, matching the best-known results for simpler minimization problems.
Discussion and Future Work
While this work provides a strong theoretical basis for two-time-scale GDA, several avenues for future research remain:
- Discretization Gap: The results are derived for continuous-time differential equations. While these often translate well to discrete-time algorithms, the errors introduced by finite step sizes require further explicit analysis.
- Stochastic Settings: The current analysis assumes access to exact gradients. In practical machine learning, Stochastic GDA is the norm; investigating the impact of mini-batch noise on these convergence rates is a critical next step.
- Acceleration: Incorporating "acceleration" techniques (such as Nesterov momentum) into this two-time-scale framework could potentially improve convergence rates even further.
Summary updated