提出新迭代方法，显著提升单调变分不等式求解速度。
Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities
- 用大步长近似Halpern迭代结合高阶方法，加速收敛。
- 对p阶情形实现最优复杂度$ ilde{ m O}(T^{-p})$，优于此前所有结果。
- 适合研究优化算法收敛性或高阶方法的学者参考。
本文研究光滑单调变分不等式（MVI）的二阶及以上阶方法。Monteiro和Svaiter（SIAM J. Optim., 2012）证明二阶方法NPE的收敛率为$ m O(T^{-1.5})$。对于凸-凹极小极大优化（一类MVI），Chen等（COLT 2025）将复杂度提升至$ ilde{ m O}(T^{-1.75})$。然而，关于MVI的最优复杂度是否可进一步改进仍为开放问题。本文通过引入大步长的不精确Halpern迭代，提出新型的Halpern-NPE方法，实现$ ilde{ m O}(T^{-2})$的更快收敛率。我们还推广该方法至$ p $阶情形：首先设计锚定张量法（ATM），达到$ m O(T^{-(p-1)})$速率；再与Halpern迭代结合，最终实现$ ilde{ m O}(T^{-p})$速率。该结果对所有$ p \geq 2 $均优于先前工作，并在$ p=1 $时退化为经典外梯度法的复杂度。
原文摘要 · Abstract (English)
We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at the rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to $\tilde{\mathcal{O}}( T^{-1.75})$ . However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of $\tilde{\mathcal{O}}(T^{-2})$ for solving MVIs. We also provide the $p$th-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of $\mathcal{O}(T^{-(p-1)})$, and then combine it with the Halpern iteration to achieve a faster convergence rate of $\tilde{\mathcal{O}}(T^{-p})$. This improves all prior results for $p \ge 2$ and matches the classical extragradient method for $p=1$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。