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.
Introduction
Saddle-point problems, where one agent seeks to minimize a function while another seeks to maximize it, are fundamental to modern artificial intelligence. These min-max frameworks are the backbone of Generative Adversarial Networks (GANs), robust optimization, and Reinforcement Learning (RL). Despite their prevalence, solving these problems using standard stochastic first-order methods remains a significant challenge due to inherent instabilities.
In many real-world scenarios, the optimization domain is unconstrained, and gradients can grow arbitrarily large as iterates move away from the origin. This often triggers a "divergence cascade": a large iterate from one player generates a massive gradient for the opponent, pushing their iterate even further out, eventually causing the system to blow up. This paper introduces a "stabilization" technique to provide a safety net for these processes without requiring restrictive prior knowledge of the solution's scale.
The Challenge of Unbounded Domains
The traditional remedy for instability in Stochastic Gradient Descent-Ascent (SGDA) is to project iterates back into a bounded set, such as a ball of radius $R$. However, this introduces a "Goldilocks dilemma":
- If $R$ is too small, the optimal solution may lie outside the feasible set.
- If $R$ is too large, the algorithm's convergence rate slows significantly.
This research addresses a critical question: Can we achieve the stability of projections without committing to a fixed, pre-defined radius?
Proposed Method: Stabilization via Regularization
The authors propose a framework called COGDA (Composite Objective Gradient Descent-Ascent) and its generalized version, COMIDA (Composite Mirror Descent). Instead of utilizing hard projections, the method augments the objective function with a regularization term that penalizes the distance from the initial starting point $(x_1, y_1)$. Specifically, terms such as $\frac{ ho}{2}\|x - x_1\|^2$ are added to the objective.
While regularization is a standard tool in optimization, the novelty here lies in the tuning of the regularization parameter $ ho$. By setting $ ho$ based on the problem's "sub-bilinear" growth constants, the negative terms introduced by the regularization in the mathematical analysis perfectly cancel out the potentially exploding gradient terms of the opposing player. This creates a cross-player stabilization effect where each player's regularization acts as a safety net for the other's instability.
Technical Innovations
The paper introduces several key analytical components to handle the complexities of unbounded gradients:
- Composite Mirror Descent: The COMID framework is used to handle the regularization term analytically, ensuring the iterates remain well-behaved.
- Ghost-Iterate Trick: A sophisticated analysis technique used to handle "adaptive" comparators—solutions that might depend on the specific history of the optimization path.
- Sub-Bilinear Generalization: The analysis moves beyond simple linear games to a broader class of functions where gradients grow at most linearly with the size of the iterates, accommodating multiplicative noise that typically causes standard algorithms to fail.
Application: Average-Reward Reinforcement Learning
The authors apply their algorithm to a specific challenge in Reinforcement Learning: finding optimal policies in an Average-Reward Markov Decision Process (MDP) using a generative model.
A major hurdle in average-reward RL is the "bias span" ($B$), which represents the maximum difference in the value function. Most existing algorithms require prior knowledge of $B$ to set their hyperparameters. The stabilization method proposed here is effectively parameter-free in this regard, as it adapts to the unknown bias span automatically.
Key Results
The theoretical analysis yields several significant findings:
- Convergence Rates: The method achieves a duality gap convergence rate of $O(1/\sqrt{T})$, matching the best known rates for projection-based methods but within an unconstrained setting.
- Initialization-Dependent Bounds: Unlike methods that depend on a fixed radius $R$, these bounds scale with the distance from the starting point to the optimum. Starting closer to the solution results in faster convergence.
- RL Complexity: For the average-reward MDP problem, the algorithm achieves an iteration complexity of $\tilde{O}(B^4 SA / \epsilon^2)$, where $S$ is the number of states and $A$ is the number of actions. This is a landmark result as it removes the requirement for prior knowledge of the bias span $B$.
Discussion and Future Work
While the stabilization technique provides a robust solution for unbounded gradients, some limitations remain. The current error bounds scale quadratically with the distance to the optimum (|x^* - x_1|^2), whereas some convex minimization problems allow for linear scaling. Achieving linear scaling in a min-max setting without prior knowledge remains an open challenge. Additionally, while the method removes the need for a projection radius, it still requires knowledge of the gradient "growth constant" ($L$). Future research may focus on making the algorithm fully adaptive to this constant as well, further reducing the need for manual parameter tuning.
Summary updated