arXiv:2604.07662math.OCcs.LG2026-04被引 3

提出无需调参的非遍历外梯度算法,实现单调变分不等式求解的强收敛性。

Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities

  • 设计无参数外梯度方法,直接控制最后一轮迭代结果
  • 在全局Lipschitz条件下达到o(1/√T)的最后迭代收敛率
  • 适用于真实问题中常不满足全局光滑性的场景,适合实际应用

单调变分不等式(VIs)统一了凸优化、均衡计算和鞍点问题。外梯度类方法是求解此类问题最有效的首阶算法之一,但其性能高度依赖步长选择。现有理论多关注迭代平均值的渐近行为,而实际性能往往由最后迭代表现决定。然而,已有最后迭代保证通常依赖于需精确估计的问题特定全局光滑性信息的固定步长,这在实践中难以实现甚至不适用。本文提出适用于约束单调VI的无参数外梯度算法,并给出非渐近的最后迭代保证。对于全局Lipschitz算子,该算法达到o(1/√T)的最后迭代收敛率。通过回溯线搜索将框架扩展至局部Lipschitz算子,仍保持无参数性,从而适用于全局光滑性不成立的重要问题类别。在双线性矩阵博弈、LASSO、极小极大群体公平性及最大熵采样松弛等实验中,验证了方法的广泛适用性以及显著优于现有方法的最后迭代性能。

原文摘要 · Abstract (English)

Monotone variational inequalities (VIs) provide a unifying framework for convex minimization, equilibrium computation, and convex-concave saddle-point problems. Extragradient-type methods are among the most effective first-order algorithms for such problems, but their performance hinges critically on stepsize selection. While most existing theory focuses on ergodic averages of the iterates, practical performance is often driven by the significantly stronger behavior of the last iterate. Moreover, available last-iterate guarantees typically rely on fixed stepsizes chosen using problem-specific global smoothness information, which is often difficult to estimate accurately and may not even be applicable. In this paper, we develop parameter-free extragradient methods with non-asymptotic last-iterate guarantees for constrained monotone VIs. For globally Lipschitz operators, our algorithm achieves an $o(1/\sqrt{T})$ last-iterate rate. We then extend the framework to locally Lipschitz operators via backtracking line search and obtain the same rate while preserving parameter-freeness, thereby making parameter-free last-iterate methods applicable to important problem classes for which global smoothness is unrealistic. Our numerical experiments on bilinear matrix games, LASSO, minimax group fairness, and state-of-the-art maximum entropy sampling relaxations demonstrate wide applicability of our results as well as strong last-iterate performance and significant improvements over existing methods.

变分不等式外梯度无参数收敛率

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。