突破传统假设，解决无界约束下的随机变分不等式问题
Solving Stochastic Variational Inequalities without the Bounded Variance Assumption
- 放宽方差与定义域有界假设，适用于无界约束的极小极大优化
- 在两类问题上均实现最优的$ ilde{O}(ε^{-4})$查询复杂度
- 适合研究非凸-非凹极小极大问题的算法设计者
我们分析了在不假设方差有界或定义域有界的情况下求解随机变分不等式（VI）的算法，重点聚焦于可能无界的约束集上的极小极大优化。研究两类问题：单调VI；以及满足弱Minty VI解的结构化非单调VI，后者使我们能够求解结构化的非凸-非凹极小极大问题。对于这两类问题，为使期望残差范数小于$\varepsilon$，我们证明了最优的$ ilde{O}(ε^{-4})$查询复杂度，这是目前已知约束VI的最佳结果。以往该复杂度仅在方差有界假设下成立，而该假设甚至不适用于无界域上的双线性极小极大问题。本工作首次在方差可随优化变量平方范数快速增长的随机算子下实现此复杂度。
原文摘要 · Abstract (English)
We analyze algorithms for solving stochastic variational inequalities (VI) without the bounded variance or bounded domain assumptions, where our main focus is min-max optimization with possibly unbounded constraint sets. We focus on two classes of problems: monotone VIs; and structured nonmonotone VIs that admit a solution to the weak Minty VI. The latter assumption allows us to solve structured nonconvex-nonconcave min-max problems. For both classes of VIs, to make the expected residual norm less than $\varepsilon$, we show an oracle complexity of $\widetilde{O}(\varepsilon^{-4})$, which is the best-known for constrained VIs. In our setting, this complexity had been obtained with the bounded variance assumption in the literature, which is not even satisfied for bilinear min-max problems with an unbounded domain. We obtain this complexity for stochastic oracles whose variance can grow as fast as the squared norm of the optimization variable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。