Beyond the Golden Ratio for Variational Inequality Algorithms

Ahmet Alacaoglu, Axel Böhm, Yura Malitsky

TL;DR

This paper uncovers a deeper theoretical unity in variational inequality algorithms by proving that the Golden Ratio Algorithm (GRAAL) doesn't actually need the golden ratio. By extending the algorithm's key parameter $\phi$ from $\approx 1.618$ to $2$, the authors bridge GRAAL with classical methods like Optimistic Gradient Descent-Ascent (OGDA) and eliminate a restrictive hyperparameter to achieve a superior, linear complexity bound ($O(L/k)$) for its adaptive variant.

What Problem Does This Paper Address?

Many important machine learning paradigms—most notably Generative Adversarial Networks (GANs) and adversarial training—are formulated as min-max optimization problems. These are often solved using Variational Inequality (VI) algorithms. Unlike standard minimization, naive gradient descent-ascent frequently fails to converge here, even on simple bilinear problems, often spinning out into infinite loops.

To fix this, researchers use sophisticated splitting methods. Among them, the Golden Ratio Algorithm (GRAAL) stands out because its adaptive variant (aGRAAL) automatically tunes its step sizes to the local Lipschitz constants of the problem. This eliminates the need to guess global hyperparameters. However, GRAAL had two major drawbacks:

  1. Its mathematical analysis strictly tied its step-size parameter $\phi$ to the golden ratio ($\frac{1+\sqrt{5}}{2} \approx 1.618$), causing it to underperform compared to competitors like OGDA when using constant step sizes.
  2. Its adaptive version required an artificial maximum step-size cap ($\bar{\alpha}$) to make the proof work, which severely degraded its theoretical worst-case complexity.

The authors set out to determine if the golden ratio is truly fundamental to the algorithm, or merely an artifact of a conservative analysis.

Methods

The authors re-examine GRAAL under both constant and adaptive step-size regimes:

  • Unconstrained Equivalence: They prove that in the unconstrained setting with constant step sizes, setting $\phi = 2$ makes GRAAL mathematically equivalent to popular VI methods like Popov's algorithm, reflected gradient, and OGDA.
  • Constrained Induction Proof: For constrained problems, standard energy (Lyapunov) functions fail when $\phi = 2$. To overcome this, the authors introduce a novel mathematical induction technique directly on the algorithm's tightest error inequalities to prove that the iterates remain bounded.
  • Streamlined Adaptivity: They remove the problematic hyperparameter $\bar{\alpha}$ from the adaptive step-size rule, simplifying it to: $$\alpha_k = \min \left( \gamma\alpha_{k-1}, \frac{\phi^2 \|z^k - z^{k-1}\|^2}{4\alpha_{k-2}\|F(z^k) - F(z^{k-1})\|^2} \right)$$
  • Extension to Nonmonotone Problems: They extend the analysis to nonmonotone problems that satisfy the Weak Minty (WM) solution condition, providing the first adaptive algorithm for this setting that avoids costly line searches at every single iteration.

Datasets

Because this is a fundamental optimization paper, evaluation is conducted on synthetic and classic game-theoretic optimization benchmarks rather than image or text datasets:

  • Policeman & Burglar matrix game: A classic matrix game setup from Nemirovski (2013).
  • Linearly Constrained Quadratic Program (QP): A challenging constrained optimization problem setup from Yoon & Ryu (2021).
  • The "Forsaken" Problem: A notoriously difficult nonmonotone min-max problem containing two limit cycles that trap standard algorithms.
  • The Polar Game: A nonmonotone problem featuring a limit cycle that attracts solutions away from the true central equilibrium.

Key Insights and Ideas

  • The Golden Ratio is an Artifact: The namesake restriction ($\phi \le 1.618$) was not an intrinsic property of the algorithm, but a limitation of previous proof techniques. Allowing $\phi = 2$ unlocks optimal step sizes.
  • Adaptivity is Free: By eliminating the artificial step-size cap ($\bar{\alpha}$), the authors improve the theoretical complexity bound from a quadratic dependence on the Lipschitz constant ($O(L^2/k)$) to a linear one ($O(L/k)$). This means you get all the practical benefits of local step-size adaptivity with zero theoretical penalty.
  • Slowing Down to Converge: For nonmonotone problems (like the Polar Game), the authors found that decreasing $\phi$ (making the algorithm more conservative by anchoring it to older iterates) actually helps the algorithm escape deceptive limit cycles.

Key Results

  • Massive Speedups via Adaptivity: As illustrated in the Policeman & Burglar matrix game, the adaptive version (aGRAAL) converges orders of magnitude faster than constant step-size alternatives like standard EG or OGDA.
Figure 1: Policeman&Burglar matrix game example from (Nemirovski, 2013).
  • Parity with OGDA: With $\phi=2$ and constant step sizes, GRAAL performs identically to OGDA on constrained QPs and matrix games, erasing its previous performance deficit.
  • Conquering the "Forsaken" Game: In nonmonotone settings, choosing a small $\phi$ allowed aGRAAL to rapidly converge to the true solution, whereas larger values got permanently trapped in a limit cycle.

Limitations and Future Work

  • Parameter Dependency in Nonmonotone Settings: For nonmonotone problems with Weak Minty solutions, safely choosing the optimal $\phi$ still requires knowing the theoretical Weak Minty parameter $\rho$. Designing a fully automated, adaptive way to estimate $\rho$ on the fly remains an open challenge.
  • Step-Size Lower Bounds: While the adaptive algorithm performs exceptionally well empirically, providing a tight theoretical lower bound for individual step sizes in the nonmonotone regime is still an open problem.

Summary updated

Abstract

We improve the understanding of the $\textit{golden ratio algorithm}$, which solves monotone variational inequalities (VI) and convex-concave min-max problems via the distinctive feature of adapting the step sizes to the local Lipschitz constants. Adaptive step sizes not only eliminate the need to pick hyperparameters, but they also remove the necessity of global Lipschitz continuity and can increase from one iteration to the next. We first establish the equivalence of this algorithm with popular VI methods such as reflected gradient, Popov or optimistic gradient descent-ascent in the unconstrained case with constant step sizes. We then move on to the constrained setting and introduce a new analysis that allows to use larger step sizes, to complete the bridge between the golden ratio algorithm and the existing algorithms in the literature. Doing so, we actually eliminate the link between the golden ratio $\frac{1+\sqrt{5}}{2}$ and the algorithm. Moreover, we improve the adaptive version of the algorithm, first by removing the maximum step size hyperparameter (an artifact from the analysis) to improve the complexity bound, and second by adjusting it to nonmonotone problems with weak Minty solutions, with superior empirical performance.
BibTeX
@article{alacaoglu2023beyond,
  author = {Ahmet Alacaoglu and Axel Böhm and Yura Malitsky},
  title = {{Beyond the Golden Ratio for Variational Inequality Algorithms}},
  journal = {J. Mach. Learn. Res.},
  year = {2023},
  url = {https://openreview.net/forum?id=RMpDxzeQ9O},
}
Figure