提出RAMPAGE算法，解决变分不等式求解中的离散化偏差问题。
RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation
- 引入随机中点法消除梯度外推的离散误差
- 理论证明收敛速度达O(1/k)，适用于多种非线性场景
- 适合研究博弈、优化等领域的学者，尤其关注稳定性与收敛性
变分不等式（VIs）的经典方法是外梯度法（EG），可视为离散时间积分。本文指出，当应用于非线性向量场时，EG存在离散化偏差。为此，我们提出无偏的随机中点外推法RAMPAGE及其方差缩减版本RAMPAGE+，利用反向采样实现负相关性。相比EG，两者均无偏差。RAMPAGE+作为无偏几何路径积分器，完全消除了内部一阶项方差，理论性能优于RAMPAGE。我们在共协强制、共拟单调和广义Lipschitz等条件下证明了二者均具有$/mathcal{O}(1/k)$的收敛性。进一步引入对称缩放变体，拓展至约束型VIs。此外，针对随机与确定性平滑凸-凹博弈，也给出了收敛保证。值得注意的是，尽管是随机方法，RAMPAGE+在若干设置下仍达到纯确定性界。
原文摘要 · Abstract (English)
A celebrated method for Variational Inequalities (VIs) is Extragradient (EG), which can be viewed as a standard discrete-time integration scheme. With this view in mind, in this paper we show that EG may suffer from discretization bias when applied to non-linear vector fields, conservative or otherwise. To resolve this discretization shortcoming, we introduce RAndomized Mid-Point for debiAsed Gradient Extrapolation (RAMPAGE) and its variance-reduced counterpart, RAMPAGE+, which leverages antithetic sampling. In contrast with EG, both methods are unbiased. Furthermore, leveraging negative correlation, RAMPAGE+ acts as an unbiased, geometric path-integrator that completely removes internal first-order terms from the variance, provably improving upon RAMPAGE. We further demonstrate that both methods enjoy provable $\mathcal{O}(1/k)$ convergence guarantees for a range of problems including root finding under co-coercive, co-hypomonotone, and generalized Lipschitzness regimes. Furthermore, we introduce symmetrically scaled variants to extend our results to constrained VIs. Finally, we provide convergence guarantees of both methods for stochastic and deterministic smooth convex-concave games. Somewhat interestingly, despite being a randomized method, RAMPAGE+ attains purely deterministic bounds for a number of the studied settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。