新算法无需调参即可高效求解一类变分不等式问题。
Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities
- 利用延迟一个周期的算子信息，实现无参数自适应更新。
- 在目标误差ε下，复杂度达到1/ε（单调）或log²(1/ε)（强单调）。
- 适合需要低同步要求的并行与分布式计算场景。
循环块坐标方法是一类基础的一阶算法，因其简洁性和优异的实证表现被广泛应用。然而其理论行为仍难以解释，步长设置除经典坐标下降外通常需精细调参或线搜索。本文提出 exttt{ADUCA}（自适应延迟更新循环算法），用于求解具有单调Lipschitz算子的广义Minty变分不等式。该算法完全无参数：无需全局或块级Lipschitz常数，且仅在初始化时需一次线搜索。核心机制是使用延迟一个完整周期的算子信息，使算法兼容并行与分布式实现，降低跨块同步要求。我们证明 exttt{ADUCA}在目标误差ε>0下的全局预言机复杂度为近最优：对单调算子为1/ε，对强单调算子为log²(1/ε)。
原文摘要 · Abstract (English)
Cyclic block coordinate methods are a fundamental class of first-order algorithms, widely used in practice for their simplicity and strong empirical performance. Yet, their theoretical behavior remains challenging to explain, and setting their step sizes -- beyond classical coordinate descent for minimization -- typically requires careful tuning or line-search machinery. In this work, we develop $\texttt{ADUCA}$ (Adaptive Delayed-Update Cyclic Algorithm), a cyclic algorithm addressing a broad class of Minty variational inequalities with monotone Lipschitz operators. $\texttt{ADUCA}$ is parameter-free: it requires no global or block-wise Lipschitz constants and uses no per-epoch line search, except at initialization. A key feature of the algorithm is using operator information delayed by a full cycle, which makes the algorithm compatible with parallel and distributed implementations, and attractive due to weakened synchronization requirements across blocks. We prove that $\texttt{ADUCA}$ attains (near) optimal global oracle complexity as a function of target error $ε>0,$ scaling with $1/ε$ for monotone operators, or with $\log^2(1/ε)$ for operators that are strongly monotone.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。