Introduction
Many modern machine learning challenges—most notably Generative Adversarial Networks (GANs) and adversarial training—are formulated as minimax problems rather than simple minimization tasks. These are frequently solved using Variational Inequalities (VIs). While standard algorithms often converge on average (the average of all previous guesses), practitioners strongly prefer last-iterate convergence, where the very last point calculated is the best one. Last-iterate behavior is typically more stable and easier to implement, but proving it mathematically is notoriously difficult.
This paper resolves a long-standing open question in optimization by proving that the Optimistic Gradient (OG) method (also known as Past Extragradient or PEG) achieves an $O(1/N)$ last-iterate convergence rate for monotone variational inequalities. Crucially, the authors remove the previously required "Lipschitz Jacobian" assumption and extend the proof to constrained problems, providing a much more general and robust theoretical foundation for minimax optimization.
The Challenge of Last-Iterate Convergence
For the Past Extragradient (PEG) method, previous proofs of $O(1/N)$ last-iterate convergence relied on a highly restrictive assumption: that the Jacobian of the operator is Lipschitz continuous. Furthermore, these earlier proofs failed to cover constrained cases, where the solution must lie within a specific set. This paper fills those critical gaps, proving the rate under standard assumptions for both unconstrained and constrained settings.
Methodology: A Computer-Aided Approach
To tackle this theoretical hurdle, the authors employ a sophisticated "computer-aided" approach to proof discovery:
- Performance Estimation Problems (PEPs): Instead of relying solely on manual derivation, the authors formulated the search for a convergence bound as a semidefinite program (SDP). This allowed them to numerically "observe" the worst-case behavior of the algorithm across different iteration counts ($N$) and stepsizes ($\gamma$).
- Potential Function Discovery: By analyzing the dual solutions of these SDPs, they identified novel Lyapunov (potential) functions—mathematical expressions guaranteed to decrease at every step of the algorithm.
- Analytical Proofs: Once the potential functions were "discovered" via computer, the authors wrote traditional analytical proofs to confirm that these functions indeed imply the $O(1/N)$ rate for any problem size.
Key Insights and Results
The study focuses on PEG, which uses a "past" gradient to approximate an extra-gradient step. In the unconstrained case, this is equivalent to the Optimistic Gradient (OG) method.
- Simpler Assumptions: The authors proved that the "Lipschitz Jacobian" assumption was merely an artifact of previous proof techniques, not a fundamental requirement of the algorithm itself.
- Unconstrained Rate: For an operator $F$, the squared norm $\|F(x^N)\|^2$ converges at a rate of $O(1/N)$. Specifically, they provide the bound: $$\|F(x^N)\|^2 \leq \frac{123L^2\|x^0 - x^*\|^2}{N + 32}$$
- Constrained Generality: The extension to the constrained case is significant because many real-world ML problems have constraints (e.g., weights must be within a certain range). In the constrained case, the squared residual $\|x^N - x^{N-1}\|^2$ also achieves an $O(1/N)$ rate, and the restricted gap function achieves $O(1/\sqrt{N})$.
- Monotonicity of the Potential: While the norm of the operator itself might not decrease at every single step, the authors found a specific combination of the norm and the distance between iterates that does decrease monotonically, providing the "anchor" for the $O(1/N)$ proof.
- Tightness: These results match the known lower bounds for this class of first-order methods, meaning the analysis is essentially as tight as possible for this algorithm.
Limitations and Future Directions
While a significant theoretical leap, the paper notes a few limitations. The authors acknowledge that their analytical constants (like the "123" in the bound above) are larger than what they observed numerically, as they prioritized a "simple" proof over the tightest possible constants. Additionally, the theoretical proof requires a slightly more conservative stepsize ($\gamma \leq 1/3L$ or $1/4L$) than what might work in practice.
Future work will need to address stochastic settings. This work focuses on deterministic gradients, and extending these last-iterate results to stochastic optimistic methods (where gradients are noisy) remains an important open challenge. Finally, while this covers monotone VIs, many deep learning landscapes are non-monotone; understanding why these methods work so well in those "messier" settings is a key direction for future research.
Summary updated