提出新算法解决随机鞍点优化中的步长不稳定问题。
Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities
- 结合递归动量与同批曲率验证，自适应调整步长。
- 理论证明收敛速度达 O(ε⁻³)，为最优阶。
- 适合非凸鲁棒回归等需自动调参的复杂优化任务。
随机非凸非凹优化（即随机变分不等式，SVI）因旋转动力学和缺乏全局目标函数而面临独特挑战。尽管自适应步长方法（如Armijo线搜索）在凸优化中取得成功，但在该场景下受限于‘随机性屏障’：梯度估计噪声掩盖了真实算子曲率，导致步长过大、收敛不稳。本文提出VR-SDA-A算法，融合递归动量（STORM）与严格的同批曲率验证机制。基于李雅普诺夫势能跟踪算子范数，理论证明其在一般Lipschitz连续算子下，求解ε-驻点的预言机复杂度为O(ε⁻³)，达到非凸最小化最优速率，并首次实现鞍点设置下的自动步长调节。在典型旋转基准和非凸鲁棒回归任务上验证，该方法有效抑制极限环，加速收敛，显著降低对人工学习率调度的依赖。
原文摘要 · Abstract (English)
Stochastic non-convex non-concave optimization, formally characterized as Stochastic Variational Inequalities (SVIs), presents unique challenges due to rotational dynamics and the absence of a global merit function. While adaptive step-size methods (like Armijo line-search) have revolutionized convex minimization, their application to this setting is hindered by the Stochasticity Barrier: the noise in gradient estimation masks the true operator curvature, triggering erroneously large steps that destabilize convergence. In this work, we propose VR-SDA-A (Variance-Reduced Stochastic Descent-Ascent with Armijo), a novel algorithm that integrates recursive momentum (STORM) with a rigorous Same-Batch Curvature Verification mechanism. We introduce a theoretical framework based on a Lyapunov potential tracking the Operator Norm, proving that VR- SDA-A achieves an oracle complexity of O(epsilon -3) for finding an epsilon-stationary point in general Lipschitz continuous operators. This matches the optimal rate for non-convex minimization while uniquely enabling automated step-size adaptation in the saddle-point setting. We validate our approach on canonical rotational benchmarks and non-convex robust regression tasks, demonstrating that our method effectively suppresses limit cycles and accelerates convergence with reduced dependence on manual learning rate scheduling.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。