论文标题
对于受约束的单调变异性不平等的，外部外部和乐观梯度下降算法的紧密近期收敛
Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities
论文作者
论文摘要
单调变化不平等是数学编程中的一个核心问题，它统一并概括了许多重要的设置，例如平滑的凸优化，零和零游戏，凸孔 - 连接点问题问题等。解决单调变化不平等的方法。尽管历史悠久，但以下主要问题仍然开放。对于单调和Lipschitz的变化不等式的，外部外算法的最后近期收敛速率或乐观的梯度下降算法是什么？我们通过证明外部算法和乐观的梯度下降算法都具有紧密的$ o \ left（\ frac {1} {\ sqrt {\ sqrt {t}} \ right）$ term-Ilter-Inter-Inter-Inter-Inter-Inter-Inter-Inter-Inter-clement fations pobsence cobsible bects and and golich，我们可以解决这个开放的问题。 [2020a，b]。我们的速率是根据标准差距函数来衡量的。我们的结果的核心是一个非标准的性能度量 - 切线残差，可以看作是考虑到局部约束的操作员规范的适应。我们使用切线残差（或切线残差的轻微变化）作为我们对外部外算法分析（或乐观的梯度下降算法）的潜在函数，并证明它在两个连续的迭代之间不侵入。
The monotone variational inequality is a central problem in mathematical programming that unifies and generalizes many important settings such as smooth convex optimization, two-player zero-sum games, convex-concave saddle point problems, etc. The extragradient algorithm by Korpelevich [1976] and the optimistic gradient descent-ascent algorithm by Popov [1980] are arguably the two most classical and popular methods for solving monotone variational inequalities. Despite their long histories, the following major problem remains open. What is the last-iterate convergence rate of the extragradient algorithm or the optimistic gradient descent-ascent algorithm for monotone and Lipschitz variational inequalities with constraints? We resolve this open problem by showing that both the extragradient algorithm and the optimistic gradient descent-ascent algorithm have a tight $O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergence rate for arbitrary convex feasible sets, which matches the lower bound by Golowich et al. [2020a,b]. Our rate is measured in terms of the standard gap function. At the core of our results lies a non-standard performance measure -- the tangent residual, which can be viewed as an adaptation of the norm of the operator that takes the local constraints into account. We use the tangent residual (or a slight variation of the tangent residual) as the the potential function in our analysis of the extragradient algorithm (or the optimistic gradient descent-ascent algorithm) and prove that it is non-increasing between two consecutive iterates.
