Beyond the Golden Ratio for Variational Inequality Algorithms
This work provides incremental improvements to optimization algorithms for researchers in machine learning and optimization, addressing hyperparameter tuning and performance in constrained and nonmonotone problems.
The paper tackles the problem of improving the golden ratio algorithm for solving monotone variational inequalities and convex-concave min-max problems by establishing its equivalence with existing methods, enabling larger step sizes, and enhancing its adaptive version for better complexity and performance in nonmonotone settings, resulting in superior empirical outcomes.
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.