提出新步长策略，让外梯度法在更宽松条件下更快求解根问题。
Extragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems
- 基于新型$(L_0, L_1)$-Lipschitz条件设计自适应步长。
- 证明单调算子下亚线性收敛，强单调时线性收敛。
- 适用于现代机器学习中的复杂优化问题，尤其适合研究者参考。
外梯度法（EG）自1976年由Korpelevich提出以来，已成为解决极小极大优化、根求解问题和变分不等式（VIs）的核心方法。尽管该方法历史悠久且备受关注，但大多数关于其收敛性分析的文献均依赖于强L-Lipschitz条件。本文在Zhang等[2024b]针对最小化问题和Vankov等[2024]针对变分不等式所提出的假设基础上，聚焦于更宽松的α-对称$(L_0, L_1)$-Lipschitz条件。该条件通过允许Lipschitz常数随算子范数缩放，对现代机器学习中问题结构提供了更精细的刻画。在此条件下，我们为EG提出一种新颖的步长策略，用于求解根求解问题，并建立了单调算子的亚线性收敛率与强单调算子的线性收敛率。此外，我们还证明了弱Minty算子的局部收敛性。通过实验验证了理论分析，展示了所提步长策略在有效性和鲁棒性方面的优越表现。
原文摘要 · Abstract (English)
Introduced by Korpelevich in 1976, the extragradient method (EG) has become a cornerstone technique for solving min-max optimization, root-finding problems, and variational inequalities (VIs). Despite its longstanding presence and significant attention within the optimization community, most works focusing on understanding its convergence guarantees assume the strong L-Lipschitz condition. In this work, building on the proposed assumptions by Zhang et al. [2024b] for minimization and Vankov et al.[2024] for VIs, we focus on the more relaxed $α$-symmetric $(L_0, L_1)$-Lipschitz condition. This condition generalizes the standard Lipschitz assumption by allowing the Lipschitz constant to scale with the operator norm, providing a more refined characterization of problem structures in modern machine learning. Under the $α$-symmetric $(L_0, L_1)$-Lipschitz condition, we propose a novel step size strategy for EG to solve root-finding problems and establish sublinear convergence rates for monotone operators and linear convergence rates for strongly monotone operators. Additionally, we prove local convergence guarantees for weak Minty operators. We supplement our analysis with experiments validating our theory and demonstrating the effectiveness and robustness of the proposed step sizes for EG.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。