对比两种随机外梯度法，揭示其收敛性差异与局限
On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities
- 区分同一样本与独立样本的随机外梯度法，分析其收敛机制
- 证明同一样本方法在无界域上仍可高概率收敛，但改进受限
- 发现经典步长策略对同一样本法失效，可能引发几乎必然发散
本文研究求解可行集上单调变分不等式问题（VIP）的随机外梯度（SEG）方法。尽管确定性外梯度算法理论成熟，其随机版本仍缺乏充分理解。现有分析多集中于独立样本SEG（I-SEG），并假设定义域有界或随机算子方差一致有界。同一样本SEG（S-SEG）这一自然变体因性质迥异，研究甚少。本文填补空白：首先证明S-SEG对样本局部利普希茨参数敏感，仅均值利普希茨和有界方差不足以保证收敛，即使在紧集上亦然；其次，在可能无界的域上，基于较弱假设建立了两类SEG的高概率受限间隙收敛性，并证明此类改进在一般情形下不可行；最后，指出已知能保证I-SEG几乎必然末点收敛的非对称双步长策略在S-SEG上可能失效：存在一个随机单调VIP，使得即便采用该步长规则，S-SEG仍几乎必然发散。
原文摘要 · Abstract (English)
We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood. Most existing analyses focus on independent-sample SEG (I-SEG) and assume either that the domain is compact or that the variance of the stochastic operator is uniformly bounded. The behavior of same-sample SEG (S-SEG), a natural variant with materially different properties, has received far less attention. In this work, we address these gaps in the literature. We first show that S-SEG is sensitive to samplewise Lipschitz parameters: mean Lipschitzness and bounded variance alone do not ensure convergence, even on a compact set. Then, for possibly unbounded domains, we establish a high-probability restricted-gap convergence for each SEG variant under a relaxed set of assumptions, and show that certain fundamental improvements to these results are impossible in general. Finally, we show that a known asymmetric double step-size selection that guarantees almost sure last-iterate convergence for I-SEG can fail for S-SEG: there exists a stochastic monotone VIP for which S-SEG diverges almost surely even under the modified step-sizes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。