Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities

Yungi Jeong, Takumi Otsuka · 2026

Read Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities by Yungi Jeong, Takumi Otsuka (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-23034.txt.

Introduction

Yungi Jeong and Takumi Otsuka break a barrier in stochastic optimization for game-like problems. These problems, written as variational inequalities, lack a single score to minimize and can spin in circles. Adaptive step-size methods transformed plain minimization, but noise blocks them here.

Noise in gradient estimates hides the true curvature, triggering steps so large that training destabilizes. Their adaptive, variance-reduced method is designed to see past that noise. Stable methods for these problems support training in economics, games, and adversarial learning. Rotational dynamics are the deep obstacle, making these problems circle rather than descend toward a single best point.

Catalog record

CREATORYungi Jeong, Takumi Otsuka
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-23034

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities Yungi Jeong, Takumi Otsuka Abstract 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 𝒪 ⁡ ( ϵ − 3 ) \mathcal{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. 1 Introduction The frontier of modern machine learning optimization has expanded beyond simple minimization to encompass complex, coupled dynamics. Problems in robust adversarial training, fair machine learning, and multi-agent reinforcement learning are formally characterized as stochastic minimax optimization problems: \min_{\theta\in\mathbb{R}^{d_{1}}}\max_{\phi\in\mathbb{R}^{d_{2}}}f(\theta,\phi)\triangleq\mathbb{E}_{\xi\sim\mathcal{D}}[F(\theta,\phi;\xi)] (1) It is precise to view these problems through the lens of Stochastic Variational Inequalities (SVI). Let z=[\theta^{\top},\phi^{\top}]^{\top} . We define the problem as finding a zero of the operator (vector field) V(z)=[\nabla_{\theta}f(\theta,\phi)^{\top},-\nabla_{\phi}f(\theta,\phi)^{\top}]^{\top} . Unlike minimization, where the negative gradient field -\nabla f constitutes a conservative vector field that naturally guides iterates toward a local optimum, the simultaneous gradient descent-ascent dynamics define a non-conservative vector field V(z) . As noted by 3 , such fields in non-convex non-concave settings often exhibit rotational components (Jacobian eigenvalues with imaginary parts), causing standard first-order methods to orbit the equilibrium rather than converging to it. To stabilize these dynamics, the community has largely relied on manual heuristics or algorithmic lookahead mechanisms (e.g., Extra-Gradient ( 16 ) or Optimistic GDA ( 7 ) ). While theoretically sound, these methods typically depend on fixed, conservative step-sizes to approximate the continuous-time integration of the ODE. This creates a fundamental dilemma: a small step-size is required for stability in rotational fields, but the non-convex landscape of high-dimensional models is replete with flat plateaus. A fixed small step-size results in prohibitively slow traversal, while a fixed large step-size risks divergence. In convex minimization, this dilemma is resolved by Adaptive Line-Search ( 31 ; 30 ) , which dynamically estimates the local Lipschitz constant to maximize the step size. However, no such reliable, parameter-free mechanism exists for stochastic non-monotone variational inequalities. 1.1 The Stochasticity Barrier in Variational Inequalities Transferring adaptive line-search to stochastic operators presents a unique challenge we term the Stochasticity Barrier . In minimization, line-search accepts a step if the objective function value decreases sufficiently. In the general operator setting, f(z) is not a valid merit function (as the maximizer seeks to increase it), and the operator norm \|V(z)\|^{2} is biased by noise. Critically, standard stochastic line-search relies on a ”descent” condition to bound the error. In the stochastic SVI setting, a ”lucky” mini-batch with low variance might erroneously suggest the local operator is smooth (small Lipschitz constant), authorizing a large step \eta_{t} . When applied to the true population dynamics, this large step can catastrophically overshoot, breaking the delicate coupling of the system dynamics. This failure mode implies that in non-monotone operators, variance is not merely noise; it is a structural destabilizer for adaptive methods. We formalize this intuition: without variance reduction, any adaptive method relying on the current batch’s geometry will authorize step sizes \eta_{t}>2/L with constant probability, violating stability conditions in rotational fields. Thus, variance reduction is strictly necessary to enable adaptive step-sizes in non-convex non-concave SVIs. 1.2 Our Contribution: Coupling Variance Reduction with Operator Dynamics In this work, we propose VR-SDA-A (Variance-Reduced Stochastic Descent-Ascent with Armijo). Our central thesis is that Variance Reduction (VR) is strictly necessary to enable adaptive step-sizes in non-convex non-concave SVIs. We utilize Recursive Variance Reduction (specifically the STORM estimator ( 6 ) ) to construct a low-variance estimate of the operator V(z) . Crucially, we introduce a Same-Batch Curvature Verification strategy. Instead of checking for ”descent” on the objective, our line-search estimates the local curvature of the operator using the same batch used for the update. This effectively treats the stochastic step as ”locally deterministic,” satisfying the rigorous stability conditions required for VIs. Our specific contributions are: • Algorithmic Framework: We introduce VR-SDA-A, integrating recursive variance reduction with an adaptive step-size mechanism. Unlike standard VI line-searches (e.g., 19 ) which often assume monotonicity or full gradients, our method handles the fully stochastic non-convex non-concave setting without manual tuning. • Theoretical Guarantee: We provide a convergence analysis based on a Lyapunov potential function \Phi_{t} . We prove that VR-SDA-A converges to an \epsilon -stationary point of the operator ( \mathbb{E}[\|V(z)\|^{2}]\leq\epsilon ) with an oracle complexity of \mathcal{O}(\epsilon^{-3}) . This matches the optimal rate for non-convex minimization while uniquely addressing the rotational instability of saddle-point problems. • Mechanism Analysis: We rigorously derive the ”Same-Batch” condition, showing that it allows us to locally bound the error between the stochastic operator update and the true operator geometry, effectively overcoming the Stochasticity Barrier without requiring the Strong Growth Condition (SGC). 2 Related Work 2.1 Non-Monotone Variational Inequalities The convergence difficulties of Gradient Descent-Ascent (GDA) in solving Variational Inequalities (VIs) are well-documented, particularly when the operator is non-monotone (corresponding to non-convex non-concave games). 3 formalized this using the Hamiltonian decomposition of the Jacobian, showing that the non-conservative (rotational) component of the vector field causes standard first-order methods to cycle rather than converge. To mitigate these rotational dynamics, the literature has focused on ”lookahead” mechanisms that approximate the implicit proximal point method. These include the Extra-Gradient (EG) method ( 16 ) and Optimistic GDA (OGDA) ( 7 ) , unified by 11 under the VI framework. However, theoretical guarantees for these methods typically rely on a fixed step-size \eta<1/L . In practice, the Lipschitz constant L is often unknown or locally variable, rendering fixed step-size strategies fragile and requiring extensive hyperparameter tuning. 2.2 Adaptive Methods for VIs In the deterministic VI setting, adaptive step-size mechanisms are well-established. 29 proposed a modified forward-backward splitting method with a line-search that adapts to the local Lipschitz constant. More recently, 19 introduced the ”Golden Ratio” algorithm, which adapts the step-size based on curvature observed in previous iterations without requiring a backtracking line-search. However, these methods generally assume access to exact operator evaluations. When applied to the stochastic setting, the noise in the operator evaluation \hat{V}(z;\xi) invalidates the monotonicity checks required by Tseng-type line-searches. While 31 successfully applied Armijo line-search to stochastic minimization (SLS), their analysis relies on the Strong Growth Condition (SGC), which implies the noise variance \sigma^{2}\to 0 at the optimum. Crucially, general stochastic VIs (and minimax games) violate SGC because the equilibrium is a saddle point where individual player gradients are non-zero, resulting in persistent variance even at

Read the complete text