论文标题
高阶平滑单调变化不平等的最佳方法
Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities
论文作者
论文摘要
在这项工作中，我们提出了用于解决$ p^{th} $的变异不平等问题（VI）问题的新的简单和最佳算法 - 订购平滑，单调运算符 - 这个问题概括了凸出优化和鞍点问题。最近的作品（Bulins and Lai（2020），Lin and Jordan（2021），Jiang and Mokhtari（2022））提出了实现$ \ tilde {o}（ε^{ - 2/（p+1）$ $ p \ geq 1 $，nemirovski和2004（nemirovski）的$ \ tilde {o}（ε^{ - 2/（p+1））$ （2012）），$ p = 1,2 $。但是，对这些方法的缺点是它们对线路搜索方案的依赖。我们提供了第一个$ p^{\ textrm {th}} $ - 达到$ O（ε^{ - 2/（p+1）}）的订单方法。$我们的方法不依赖行搜索例程，从而通过对数因子来提高先前的速率。在Nemirovski（2004）的Mirror Prox方法的基础上，我们的算法即使在受约束的非欧几里得环境中也起作用。此外，我们通过构建匹配的下限来证明算法的最佳性。这些是对于$ p> 1 $的凸优化的平滑MVIS的第一个下限。这建立了求解光滑的MVI和平滑凸优化之间的分离，并解决了求解$ p^{\ textrm {th}} $ - 订购平滑MVIS的甲骨文复杂性。
In this work, we present new simple and optimal algorithms for solving the variational inequality (VI) problem for $p^{th}$-order smooth, monotone operators -- a problem that generalizes convex optimization and saddle-point problems. Recent works (Bullins and Lai (2020), Lin and Jordan (2021), Jiang and Mokhtari (2022)) present methods that achieve a rate of $\tilde{O}(ε^{-2/(p+1)})$ for $p\geq 1$, extending results by (Nemirovski (2004)) and (Monteiro and Svaiter (2012)) for $p=1,2$. A drawback to these approaches, however, is their reliance on a line search scheme. We provide the first $p^{\textrm{th}}$-order method that achieves a rate of $O(ε^{-2/(p+1)}).$ Our method does not rely on a line search routine, thereby improving upon previous rates by a logarithmic factor. Building on the Mirror Prox method of Nemirovski (2004), our algorithm works even in the constrained, non-Euclidean setting. Furthermore, we prove the optimality of our algorithm by constructing matching lower bounds. These are the first lower bounds for smooth MVIs beyond convex optimization for $p > 1$. This establishes a separation between solving smooth MVIs and smooth convex optimization, and settles the oracle complexity of solving $p^{\textrm{th}}$-order smooth MVIs.
