论文标题
在连续和离散的时间内快速乐观的梯度下降（OGDA）方法
Fast Optimistic Gradient Descent Ascent (OGDA) method in continuous and discrete time
论文作者
论文摘要
在真正的希尔伯特空间的框架中，我们在时间动力学上进行了连续研究，以及接近单值单调和连续运算符$ v $的零零的问题的数值算法。起始人Poin是一个二阶动力系统，将消失的阻尼项与沿轨迹的$ V $的时间导数结合在一起。我们的方法表现出$ o \ left的快速收敛速率（\ frac {1} {tβ（t）} \右）$对于$ \ | | v（z（t））\ | $，$β（\ cdot）$是一个积极的非核心功能，可满足生长条件，以及可限制的限制性差异功能。我们还证明了该轨迹较弱的融合到$ v $的零。动力学系统的时间离散化产生了隐式和显式数值算法，这两者都可以看作是乐观梯度下降（OGDA）方法的加速版本，我们证明，我们证明迭代的迭代序列是连续动力学的渐进式特征。 In particular we show for the implicit numerical algorithm convergence rates of order $o \left( \frac{1}{kβ_k} \right)$ for $\|V(z^k)\|$ and the restricted gap function, where $(β_k)_{k \geq 0}$ is a positive nondecreasing sequence satisfying a growth condition.对于明确的数值算法，我们还通过假设运算符$ v $是Lipschitz的连续收敛速率$ o \ left（\ frac {1} {k} {k} \ right）$ for $ \ | v（z^k）\ | $ | $和受限的差距函数。所有收敛速率声明都是最后一次迭代的收敛结果；此外，我们证明了这两种算法的迭代融合至$ v $的零。据我们所知，我们的研究为单调方程式展示了最著名的收敛率结果。数值实验表明，与单调方程的其他方法相比，我们显式数值算法的压倒性优势。
In the framework of real Hilbert spaces we study continuous in time dynamics as well as numerical algorithms for the problem of approaching the set of zeros of a single-valued monotone and continuous operator $V$. The starting poin is a second order dynamical system that combines a vanishing damping term with the time derivative of $V$ along the trajectory. Our method exhibits fast convergence rates of order $o \left( \frac{1}{tβ(t)} \right)$ for $\|V(z(t))\|$, wher $β(\cdot)$ is a positive nondecreasing function satisfying a growth condition, and also for the restricted gap function. We also prove the weak convergence of the trajectory to a zero of $V$. Temporal discretizations of the dynamical system generate implicit and explicit numerical algorithms, which can be both seen as accelerated versions of the Optimistic Gradient Descent Ascent (OGDA) method, for which we prove that the generated sequence of iterates shares the asymptotic features of the continuous dynamics. In particular we show for the implicit numerical algorithm convergence rates of order $o \left( \frac{1}{kβ_k} \right)$ for $\|V(z^k)\|$ and the restricted gap function, where $(β_k)_{k \geq 0}$ is a positive nondecreasing sequence satisfying a growth condition. For the explicit numerical algorithm we show by additionally assuming that the operator $V$ is Lipschitz continuous convergence rates of order $o \left( \frac{1}{k} \right)$ for $\|V(z^k)\|$ and the restricted gap function. All convergence rate statements are last iterate convergence results; in addition we prove for both algorithms the convergence of the iterates to a zero of $V$. To our knowledge, our study exhibits the best known convergence rate results for monotone equations. Numerical experiments indicate the overwhelming superiority of our explicit numerical algorithm over other methods for monotone equations.
