Beyond the Golden Ratio for Variational Inequality Algorithms
Beyond the Golden Ratio for Variational Inequality Algorithms
复制标题
DOI：
10.48550/arxiv.2212.13955
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Ahmet Alacaoglu;A. Böhm;Yura Malitsky
中科院分区：
文献类型：
--
作者：
Ahmet Alacaoglu;A. Böhm;Yura Malitsky
我们提高了理解的$\textit{黄金比例算法}$，解决单调变分不等式（VI）和凹凸极小极大问题，通过适应当地Lipschitz常数的步长的显着特点。自适应步长不仅消除了选择超参数的需要，而且还消除了全局Lipschitz连续性的必要性，并且可以从一次迭代到下一次迭代增加。我们首先建立了该算法与流行的VI方法，如反射梯度，波波夫或乐观的梯度下降上升在无约束的情况下，恒定的步长的等价性。然后，我们移动到约束设置，并引入一个新的分析，允许使用更大的步长，完成黄金比例算法和文献中现有的算法之间的桥梁。这样做，我们实际上消除了黄金分割率$\frac{1+\sqrt{5}}{2}$和算法之间的联系。此外，我们改进了自适应版本的算法，首先通过删除最大步长超参数（从分析的工件），以提高复杂度的限制，其次通过调整它的非单调问题与弱明蒂解决方案，具有上级经验性能。
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.