Title: Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements Show Chinese title

Title: 随机方法在变分不等式中的应用：遍历性、偏差与改进

Abstract: For min-max optimization and variational inequalities problems (VIP) encountered in diverse machine learning tasks, Stochastic Extragradient (SEG) and Stochastic Gradient Descent Ascent (SGDA) have emerged as preeminent algorithms. Constant step-size variants of SEG/SGDA have gained popularity, with appealing benefits such as easy tuning and rapid forgiveness of initial conditions, but their convergence behaviors are more complicated even in rudimentary bilinear models. Our work endeavors to elucidate and quantify the probabilistic structures intrinsic to these algorithms. By recasting the constant step-size SEG/SGDA as time-homogeneous Markov Chains, we establish a first-of-its-kind Law of Large Numbers and a Central Limit Theorem, demonstrating that the average iterate is asymptotically normal with a unique invariant distribution for an extensive range of monotone and non-monotone VIPs. Specializing to convex-concave min-max optimization, we characterize the relationship between the step-size and the induced bias with respect to the Von-Neumann's value. Finally, we establish that Richardson-Romberg extrapolation can improve proximity of the average iterate to the global solution for VIPs. Our probabilistic analysis, underpinned by experiments corroborating our theoretical discoveries, harnesses techniques from optimization, Markov chains, and operator theory. Show Chinese abstract

Abstract: 对于在各种机器学习任务中遇到的极小极大优化和变分不等式问题（VIP），随机外梯度（SEG）和随机梯度下降上升（SGDA）已成为领先的算法。 SEG/SGDA的固定步长变体已广受欢迎，具有易于调整和对初始条件快速宽容等优点，但即使在基本的双线性模型中，它们的收敛行为也更为复杂。 我们的工作旨在阐明并量化这些算法内在的概率结构。 通过将固定步长的SEG/SGDA重新表述为时间齐次马尔可夫链，我们建立了首个此类大数定律和中心极限定理，证明了平均迭代值在广泛的单调和非单调VIP范围内渐近服从正态分布，并具有唯一的不变分布。 专门针对凸凹极小极大优化，我们描述了步长与相对于冯·诺依曼值的诱导偏差之间的关系。 最后，我们证明Richardson-Romberg外推可以提高平均迭代值与VIP全局解的接近程度。 我们的概率分析得到了实验验证，支持我们的理论发现，并利用了优化、马尔可夫链和算子理论的技术。