Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Evaluating Stochasticity in Deep Research Agents
Deep Research Agents (DRAs) are promising agentic systems that gather and synthesize information to support research across domains such as financial decision-making, medical analysis, and scientific discovery. Despite r…
Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning. In these works, the cumulative variance of the noise $Λ= \sum_{t=1}^T σ_t^2$, where $σ_t^2$ is the…
Reinforcement LearningData-Driven Time-Varying Control Barrier Functions for Adaptive Safe-Set Learning with Online Decremental Support Vector Machines
Mission-critical intelligent systems often operate under time-varying limitations that reduce control authority and change the admissible safe operating envelope. In such settings, a safety certificate learned under nomi…
Unmatched Control Barrier Functions: Certainty Equivalence Adaptive Safety
This work applies universal adaptive control to control barrier functions to achieve forward invariance of a safe set despite the presence of unmatched parametric uncertainties. The approach combines two ideas. The first…
Wasserstein Distributionally Robust Control Barrier Function using Conditional Value-at-Risk with Differentiable Convex Programming
Control Barrier functions (CBFs) have attracted extensive attention for designing safe controllers for their deployment in real-world safety-critical systems. However, the perception of the surrounding environment is oft…