Dealing with unbounded gradients in stochastic saddle-point optimization

Gergely Neu, Nneka Okolo

TL;DR

This paper introduces a simple yet powerful regularization technique to stabilize stochastic gradient descent-ascent in min-max optimization problems where gradients can grow uncontrollably. By adding a specific "stabilizing" term to the objective, the authors achieve convergence guarantees that depend only on the initial starting point, effectively solving the "projection radius dilemma" and enabling new performance bounds for average-reward Reinforcement Learning.

What Problem Does This Paper Address?

Many machine learning problems, from Generative Adversarial Networks (GANs) to Reinforcement Learning (RL), are framed as saddle-point problems: one player tries to minimize a function while another tries to maximize it ($\min_x \max_y f(x, y)$).

A major headache in these "games" is instability. In standard optimization, we often assume gradients are bounded. However, in saddle-point problems—especially bilinear ones like $f(x, y) = x^TMy$—the gradient for one player depends on the magnitude of the other player's variables. If one player's iterates start to grow, the other player sees massive gradients, which pushes their iterates even further away. This creates a feedback loop leading to divergence.

The traditional fix is to project iterates onto a bounded set (a "ball"). But this creates a catch-22: if you pick a radius that's too small, you might exclude the actual solution; if you pick one that's too large, the optimization becomes incredibly slow and unstable.

Methods

The authors propose Composite Objective Gradient Descent-Ascent (COGDA) and its generalized version, COMIDA (Composite-Objective Mirror Descent-Ascent).

The core innovation is a stabilization technique that replaces hard projections with a specific regularization term. Instead of just following the gradient, the algorithm adds a penalty based on the distance from the initial point:

  • Regularization: They add terms $H_x(x) = \frac{1}{2}\|x - x_1\|^2$ and $H_y(y) = \frac{1}{2}\|y - y_1\|^2$ to the objective.
  • Closed-form Updates: For bilinear games, this results in an update rule that is a convex combination of a standard stochastic gradient step and the initial starting point. It essentially "anchors" the iterates to prevent them from flying off to infinity.
  • Adaptive Comparators: They employ a "ghost-iterate" trick to handle cases where the optimal solution (the comparator) might change based on the history of the optimization, which is crucial for applications like Reinforcement Learning.

Datasets

This is a theoretical paper focused on algorithmic analysis and convergence proofs. As such, no empirical datasets were used for training or evaluation. The "application" section uses a mathematical model of an average-reward Markov Decision Process (MDP) to demonstrate the algorithm's utility.

Key Insights and Ideas

  • Eliminating the Gradient Norm: In standard analysis, the error bound depends on the maximum norm of the gradients encountered. If gradients are unbounded, the bound is useless. The authors show that their regularization "cancels out" these large terms in the regret analysis, replacing them with the gradient norm evaluated at the starting point ($x_1, y_1$), which is always finite.
  • Sub-Bilinear Growth: The method works not just for bilinear functions, but for a broader class called "sub-bilinear" functions, where gradients grow at most linearly with the size of the iterates.
  • Solving the RL Bias Span Dilemma: In average-reward RL, the scale of the "value function" (the bias span) is usually unknown. Previous methods required knowing this span to set projection radii. COMIDA-MDP finds near-optimal policies without any prior knowledge of this scale, representing a significant step forward in parameter-free RL.

Key Results

  • Convergence Rate: The algorithm achieves a duality gap of $O(1/\sqrt{T})$, matching the best-known rates for projection-based methods but without needing to know the projection radius in advance.
  • Initialization Dependence: The error bounds scale with the distance from the initial point to the optimum ($\|x^* - x_1\|^2$). If you start close to the solution, you converge faster.
  • RL Complexity: For average-reward MDPs, the algorithm reaches an $\epsilon$-optimal policy with an iteration complexity of $O\left(\frac{B^4 SA \log(SA)}{\epsilon^2}\right)$, where $B$ is the (unknown) bias span, $S$ is the number of states, and $A$ is the number of actions.

Limitations and Future Work

  • Quadratic Scaling: A current limitation is that the error scales quadratically with the initialization error ($\|x^* - x_1\|^2$). In some convex minimization settings, linear scaling is possible; the authors note that recent work suggests quadratic scaling might be unavoidable for this specific min-max setting, but it remains an open question.
  • RL Efficiency: While the RL results are theoretically significant for being "parameter-free," the dependence on the state-action space ($SA$) is currently suboptimal compared to methods that do know the bias span.
  • General Geometries: While the paper extends the idea to Bregman divergences, the authors suggest that further exploring how this "anchoring" trick applies to more diverse game-theoretic settings could be a fruitful area for future research.

Summary updated

Abstract

We study the performance of stochastic first-order methods for finding saddle points of convex-concave functions. A notorious challenge faced by such methods is that the gradients can grow arbitrarily large during optimization, which may result in instability and divergence. In this paper, we propose a simple and effective regularization technique that stabilizes the iterates and yields meaningful performance guarantees even if the domain and the gradient noise scales linearly with the size of the iterates (and is thus potentially unbounded). Besides providing a set of general results, we also apply our algorithm to a specific problem in reinforcement learning, where it leads to performance guarantees for finding near-optimal policies in an average-reward MDP without prior knowledge of the bias span.
BibTeX
@inproceedings{neu2024dealing,
  author = {Gergely Neu and Nneka Okolo},
  title = {{Dealing with unbounded gradients in stochastic saddle-point optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=RPMTNGMq0O},
}
Figure