Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry

Ziyi Chen, Yi Zhou, Tengyu Xu, Yingbin Liang

Minimax optimization—the "battle" between two players where one minimizes and the other maximizes—is the engine behind some of modern artificial intelligence's most exciting frontiers, from Generative Adversarial Networks (GANs) to robust reinforcement learning. However, while we often observe these models "converge" empirically in terms of loss values, proving that the actual model parameters (the variables) settle down to a specific, stable point in a complex, nonconvex landscape has remained a theoretical holy grail.

A recent paper, "Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry," provides a rigorous mathematical map for this territory. The authors prove that a generalized version of the Gradient Descent-Ascent (GDA) algorithm is guaranteed to converge to a specific critical point in nonconvex-strongly-concave minimax problems. By introducing a novel Lyapunov function and leveraging Kurdyka-Łojasiewicz (KŁ) geometry, they establish the first theoretical variable convergence results and rates for this broad class of problems.

The Challenge of Variable Convergence

In standard minimization, the goal is for parameters to reach a valley. In minimax optimization, the objective is to find a "saddle point." The most common tool for this is Gradient Descent-Ascent (GDA), where one variable ($x$) takes a step down the gradient while the other ($y$) takes a step up.

The primary challenge in this dynamic is stability. Because the algorithm is simultaneously pushing and pulling, the trajectory of the variables can oscillate wildly or even enter infinite loops, even if the "loss" value appears to stabilize. Most existing theory only guarantees value convergence (the loss stops changing) or gradient convergence (the slope becomes flat).

But for machine learning applications, we need variable convergence: we need absolute certainty that our model weights actually stop at a specific optimal policy. Until now, this was only well-understood for simple "convex-concave" landscapes, which fail to reflect the highly complex, nonconvex nature of modern neural networks.

Methodology: Proximal-GDA and KŁ Geometry

To bridge this gap, the authors study Proximal-GDA, a version of the algorithm equipped to handle "regularizers"—extra terms like $L_1$ or $L_2$ penalties that might be non-smooth. Their theoretical analysis rests on two foundational pillars:

  1. A Novel Lyapunov Function: To track progress in an oscillating system, one needs an "energy function" that strictly decreases over time. The authors designed a clever Lyapunov function $H(x, y)$ that combines the minimax objective with a term measuring how far the current $y$ is from its "best response" to the current $x$. They prove this function decreases monotonically at every step of the algorithm, effectively "taming" the oscillations inherent in GDA.
  2. KŁ Geometry: The Kurdyka-Łojasiewicz (KŁ) property is a mathematical framework used to describe the "sharpness" or "flatness" of a function's local geometry. By assuming the landscape follows KŁ geometry (a property shared by almost all practical ML functions), the authors can translate the steady decrease in their Lyapunov function into actual, measurable movement toward a limit point.

Note: This is a purely theoretical work focused on mathematical proofs of convergence and complexity analysis. No empirical experiments on specific datasets were conducted.

Key Insights and Results

The most significant breakthrough of the paper is the formal establishment that the entire sequence of iterates $(x_t, y_t)$ converges to a unique critical point $(x^*, y^*)$. The authors highlight that while gradient norms might vanish at a rate of $1/\sqrt{t}$, that alone does not guarantee the path taken by the variables is finite. Their Lyapunov framework ensures the "tail" of the trajectory is short enough that the variables actually come to a halt.

Furthermore, the paper provides a complete characterization of convergence rates for both function values and variables across the "KŁ Spectrum." They categorize convergence into four distinct regimes based on the KŁ parameter $\theta$:

Convergence rates of Proximal-GDA under different KŁ parameters

Depending on the local shape of the function, the algorithm achieves:

  • Finite-step convergence: The algorithm reaches the exact point in a limited number of steps ($\theta = 1$).
  • Super-linear convergence: Faster than any exponential rate ($\theta \in (1/2, 1)$).
  • Linear convergence: The standard "fast" convergence expected in well-behaved problems ($\theta = 1/2$).
  • Sub-linear convergence: A slower, polynomial rate typical of flatter regions ($\theta \in (0, 1/2)$).

This marks the first time such a "full spectrum" of rates has been established for nonconvex minimax optimization.

Limitations and Future Directions

While a major step forward, the theoretical framework has boundaries that invite future research:

  • Strong Concavity Requirement: The proofs currently require the function to be "strongly concave" in the $y$ variable. While common in minimax theory, many real-world GANs might only be "concave" or even "non-concave," presenting an open challenge.
  • Deterministic Focus: The paper focuses on deterministic GDA. In practice, machine learning relies heavily on Stochastic GDA (using mini-batches). Extending this Lyapunov framework to the stochastic setting is a primary direction for future work.
  • Hyperparameter Sensitivity: The guaranteed convergence relies on specific choices for learning rates ($\eta_x, \eta_y$) that depend on the smoothness of the function, which can be difficult to estimate accurately in practice.

Summary updated

Abstract

The gradient descent-ascent (GDA) algorithm has been widely applied to solve minimax optimization problems. In order to achieve convergent policy parameters for minimax optimization, it is important that GDA generates convergent variable sequences rather than convergent sequences of function value or gradient norm. However, the variable convergence of GDA has been proved only under convexity geometries, and it is lack of understanding in general nonconvex minimax optimization. This paper fills such a gap by studying the convergence of a more general proximal-GDA for regularized nonconvex-strongly-concave minimax optimization. Specifically, we show that proximal-GDA admits a novel Lyapunov function, which monotonically decreases in the minimax optimization process and drives the variable sequences to a critical point. By leveraging this Lyapunov function and the KL geometry that parameterizes the local geometries of general nonconvex functions, we formally establish the variable convergence of proximal-GDA to a certain critical point $x^*$, i.e., $x_t\to x^*, y_t\to y^*(x^*)$. Furthermore, over the full spectrum of the KL-parameterized geometry, we show that proximal-GDA achieves different types of convergence rates ranging from sublinear convergence up to finite-step convergence, depending on the geometry associated with the KL parameter. This is the first theoretical result on the variable convergence for nonconvex minimax optimization.
BibTeX
@inproceedings{chen2021proximal,
  author = {Ziyi Chen and Yi Zhou and Tengyu Xu and Yingbin Liang},
  title = {{Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=zMBvZBOiJB},
}
Figure