在强单调条件下，数据驱动求解变分不等式可实现更快收敛速度。
Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity
- 利用稳定性分析将凸优化的快速学习方法拓展至变分不等式
- 在强单调假设下，达到Θ(1/ε)的最优率，优于传统Θ(1/ε²)
- 适用于多玩家博弈均衡求解等复杂场景，适合优化与博弈研究者
变分不等式（VIs）是一类涵盖从标准凸最小化到极小极大优化及多玩家博弈均衡计算的广泛优化问题。在凸优化中，强凸性可使统计学习速率加快至仅需Θ(1/ε)次随机一阶预言机调用即可获得ε-最优解，远优于标准的Θ(1/ε²)。本文简要说明：当变分不等式满足强单调性（强凸性的推广）时，同样可获得Θ(1/ε)的快速学习率。具体而言，我们证明了凸最小化中的标准稳定性泛化论证，在定义域具有小覆盖或算子可积且次优性以势函数衡量时，可直接推广至变分不等式情形；例如在求解多玩家博弈均衡时。
原文摘要 · Abstract (English)
Variational inequalities (VIs) are a broad class of optimization problems encompassing machine learning problems ranging from standard convex minimization to more complex scenarios like min-max optimization and computing the equilibria of multi-player games. In convex optimization, strong convexity allows for fast statistical learning rates requiring only $Θ(1/ε)$ stochastic first-order oracle calls to find an $ε$-optimal solution, rather than the standard $Θ(1/ε^2)$ calls. This note provides a simple overview of how one can similarly obtain fast $Θ(1/ε)$ rates for learning VIs that satisfy strong monotonicity, a generalization of strong convexity. Specifically, we demonstrate that standard stability-based generalization arguments for convex minimization extend directly to VIs when the domain admits a small covering, or when the operator is integrable and suboptimality is measured by potential functions; such as when finding equilibria in multi-player games.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。