提出改进的随机外梯度算法，解决无约束极小极大问题的收敛难题。
Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
- 采用翻转打乱与锚点技巧，提升随机外梯度法稳定性
- 在强凸强凹设定下，收敛速度优于其他打乱方法
- 适用于需要稳定求解极小极大问题的研究者
在极小极大优化中，外梯度（EG）方法因在凸-凹（C-C）问题中表现优于梯度下降-上升法而受到广泛关注。然而，随机外梯度（SEG）在无约束的C-C问题中进展有限。受近期基于打乱的随机方法进展启发，我们研究了基于打乱的SEG在无约束有限求和极小极大问题中的收敛性，旨在找到可收敛的打乱型SEG。分析表明，仅使用随机重排或最近提出的翻转打乱均可能导致C-C问题发散。但通过引入一种简单技巧——锚点，我们提出了翻转打乱锚点随机外梯度（SEG-FFA），成功实现C-C问题的收敛。此外，在强凸-强凹设定下，我们给出了上界与下界，证明SEG-FFA相比其他打乱方法具有可证明更快的收敛速率。
原文摘要 · Abstract (English)
In minimax optimization, the extragradient (EG) method has been extensively studied because it outperforms the gradient descent-ascent method in convex-concave (C-C) problems. Yet, stochastic EG (SEG) has seen limited success in C-C problems, especially for unconstrained cases. Motivated by the recent progress of shuffling-based stochastic methods, we investigate the convergence of shuffling-based SEG in unconstrained finite-sum minimax problems, in search of convergent shuffling-based SEG. Our analysis reveals that both random reshuffling and the recently proposed flip-flop shuffling alone can suffer divergence in C-C problems. However, with an additional simple trick called anchoring, we develop the SEG with flip-flop anchoring (SEG-FFA) method which successfully converges in C-C problems. We also show upper and lower bounds in the strongly-convex-strongly-concave setting, demonstrating that SEG-FFA has a provably faster convergence rate compared to other shuffling-based methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。