Source-linked AI summary
Extragradient method with variance reduction for stochastic variational inequalities
Alfredo Iusem, Alejandro Jofré, Roberto I. Oliveira, Philip Thompson
TL;DR
Stochastic variational inequalities require stochastic-oracle methods when the expected operator is unavailable or expensive to compute. This paper studies stochastic approximation with variance reduction, achieving accelerated convergence and near-optimal complexity under weaker variance conditions.
Problem
Stochastic variational inequalities require stochastic-oracle calls when the expected operator is unavailable or expensive to compute.
Method
The paper combines a stochastic approximation extragradient method with iterative variance reduction to preserve convergence with stepsizes bounded away from zero.
Results
O(1/K) convergence and O(ε^-2) oracle complexity up to ln(ε^-1) are achieved, with complexity independent of dimension under unbounded feasible sets and non-uniform variance.
Takeaways & Limitations
The analysis supports stochastic variational inequalities with weaker finite-variance assumptions than uniformly bounded variance, including settings with unbounded feasible sets.
Takeaways & Limitations
The analysis relies on variance assumptions that distinguish finite variance at solution points from uniform variance over the feasible set, with sharper estimates requiring stronger uniformity.
Abstract
from arXiv · showhide
We propose an extragradient method with stepsizes bounded away from zero for stochastic variational inequalities requiring only pseudo-monotonicity. We provide convergence and complexity analysis, allowing for an unbounded feasible set, unbounded operator, non-uniform variance of the oracle and, also, we do not require any regularization. Alongside the stochastic approximation procedure, we iteratively reduce the variance of the stochastic error. Our method attains the optimal oracle complexity $\mathcal{O}(1/ε^2)$ (up to a logarithmic term) and a faster rate $\mathcal{O}(1/K)$ in terms of the mean (quadratic) natural residual and the D-gap function, where $K$ is the number of iterations required for a given tolerance $ε>0$. Such convergence rate represents an acceleration with respect to the stochastic error. The generated sequence also enjoys a new feature: the sequence is bounded in $L^p$ if the stochastic error has finite $p$-moment. Explicit estimates for the convergence rate, the oracle complexity and the $p$-moments are given depending on problem parameters and distance of the initial iterate to the solution set. Moreover, sharper constants are possible if the variance is uniform over the solution set or the feasible set. Our results provide new classes of stochastic variational inequalities for which a convergence rate of $\mathcal{O}(1/K)$ holds in terms of the mean-squared distance to the solution set. Our analysis includes the distributed solution of pseudo-monotone Cartesian variational inequalities under partial coordination of parameters between users of a network.
1. Introduction.
The paper develops a stochastic-approximation extragradient method for pseudo-monotone stochastic variational inequalities, targeting faster residual convergence without regularization. Its analysis covers unbounded feasible sets and operators, non-uniform oracle variance, variance reduction, and distributed Cartesian problems.
- Problem setting: The stochastic variational inequality uses the expected operator T while stochastic-oracle calls substitute sampled values when expectation computation is unavailable or expensive.The paper focuses on stochastic approximation rather than sample average approximation.
- Convergence: The method proves almost-sure and L2 convergence under pseudo-monotonicity without regularization, including bounded iterates, vanishing distance to the solution set, and vanishing natural residual.If the random operator has finite p-moment, the sequence is also bounded in Lp for p = 2 or p ≥4.
- Rates and complexity: O(1/K) convergence holds for the mean-squared natural residual and mean D-gap function with stepsizes bounded away from zero.The paper identifies this as a faster rate under plain pseudo-monotonicity.
- Rates and complexity: O(ε^-2) oracle complexity is preserved up to a first-order logarithmic term while the iteration count is reduced to O(ε^-1).The method reduces projection computations while maintaining near-optimal total sampling cost.
- Unbounded and non-uniform settings: The results remain valid for unbounded feasible sets and unbounded operators, including complementarity problems and systems of equations.The analysis uses natural residual and D-gap measures, which remain finite-valued on broader settings than the standard gap function.
- Unbounded and non-uniform settings: The oracle-complexity analysis accommodates non-uniform variance and selects solution points by trading off variance against distance from the initial iterate.The framework also covers distributed settings, though fully distributed sampling can increase dependence on network dimension.
- Algorithm and extensions: Variance reduction uses growing empirical samples at each iteration to enable bounded-away-from-zero stepsizes and accelerated residual convergence while retaining near-optimal oracle complexity.The method also extends to distributed stochastic Cartesian variational inequalities, allowing agents to share oracle calls or sample independently.
2. Preliminaries.
The preliminaries establish notation for Euclidean geometry, projections, variational-inequality solution sets, stochastic moments, and asymptotic bounds. They also state projection properties and probabilistic convergence tools used in the analysis.
- Notation: The Euclidean norm, distance to a set, projection operator, matrix norm, index sets, expectation, conditional expectation, variance, and conditional Lp norms are defined.The notation also includes positive parts, ceiling values, and the abbreviation RHS.
- Projection properties: For a closed convex set, the Euclidean projection is characterized by an inner-product inequality and is nonexpansive.The projection also satisfies a squared-distance inequality.
- Projection properties: The solution set of VI(H, C) equals the fixed-point set of x = ΠC[x − αH(x)] for any α > 0.This fixed-point characterization connects variational inequalities to projected methods.
- Stochastic tools: The Robbins–Siegmund convergence theorem gives almost-sure convergence of a nonnegative adapted sequence when conditional drift and summability conditions hold.It also implies summability of the associated nonnegative error sequence.
- Stochastic tools: The Burkholder–Davis–Gundy inequality provides moment bounds for vector-valued martingales, with a simplified form obtained through Minkowski’s inequality for q ≥2.These bounds support the paper’s stochastic-moment analysis.
3. An extragradient method with stepsizes bounded away from zero.
The paper develops a stochastic extragradient method with stepsizes bounded away from zero, variance reduction, and assumptions covering unbounded feasible sets, unbounded operators, and non-uniform variance. It establishes convergence, moment bounds, and explicit rate and complexity estimates under pseudo-monotonicity.
- Algorithm: The stochastic extragradient algorithm uses sampled operator values, positive stepsizes, and an increasing sample-rate sequence.The method initializes an iterate, stepsizes, sample rates, and random samples, then updates iteratively using sampled operator evaluations.
- Rates and complexity: The method achieves an O(1/K) rate and O(ε^-2) oracle complexity up to a first-order logarithmic term.The estimates can depend on the variance at a selected solution and the distance of initial iterates, while uniform variance can make the iteration bound solution-independent.
- Assumptions: Variance assumptions range from finite variance at a solution point or across the solution set to uniformly bounded variance over the feasible set.The strongest condition yields sharper estimates, while the weaker conditions accommodate unbounded feasible sets and operators.
- Assumptions: For linear stochastic variational inequalities, oracle variance can grow quadratically with the iterate, so uniform variance fails on unbounded feasible sets.With T(x)=Ax, the variance has quadratic form x^T Bx; positive definiteness gives a lower bound proportional to ||x||^2.
- Variance reduction: The variance-reduction procedure preserves convergence in unbounded settings with stepsizes bounded away from zero and accelerates natural-residual convergence.The stochastic error otherwise destroys the strict Fejér property available in the deterministic setting.
- Convergence: The generated sequence is bounded, approaches the solution set, and has natural residual converging to zero almost surely and in L2.Every cluster point belongs to the solution set; higher-moment recursions provide explicit Lp bounds when the stochastic error has finite p-moment.
Then Theorem 3 holds and there are non-negative constants
The analysis establishes explicit convergence-rate and oracle-complexity estimates for the variance-reduced extragradient method, including unbounded settings, uniform-variance refinements, and distributed Cartesian problems. The bounds expose how variance, initialization distance, sampling rates, and network coordination affect performance.
- Convergence and complexity: The estimates remain applicable when the feasible set and operator are unbounded, with constants depending on problem parameters and initial distance to the solution set.The results use explicit bounds involving d(x0, X∗), variance terms, and recursively controlled moment quantities.
- Uniform variance: Uniform variance over X∗ or X yields sharper convergence-rate and oracle-complexity estimates than general non-uniform variance.For variance uniform over X∗, the estimates depend on σ^4 max0≤k≤k0(σ) E[d(xk, X∗)^2]; for uniform variance over X, they depend only on d(x0, X∗) and sampling-rate scaling.
- Distributed setting: In distributed Cartesian variational inequalities, coordinated sampling exponents and an approximate network dimension make oracle complexity proportional to m up to sampling-rate scaling.The distributed bounds distinguish centralized from decentralized sampling and quantify robustness under changes in sampling parameters.
- Convergence and complexity: O(1/K) convergence is obtained for stochastic terms through iterative variance reduction, while preserving near-optimal oracle complexity.The analysis contrasts the accelerated stochastic rate with O(σ/√K) behavior and retains O(ε^-2) oracle complexity up to a logarithmic factor.
- Comparison of estimates: The method improves bounds based on feasible-set diameter or a fixed solution distance by using d(x0, X∗), and it analyzes non-uniform variance cases.The comparison states that the same merit function applies to compact and unbounded feasible sets, while the estimates use initial distance rather than diam(X) or a fixed ∥x0−x∗∥.
4. Concluding remarks.
The paper presents a variance-reduced extragradient method for pseudo-monotone stochastic variational inequalities and establishes convergence properties under broad oracle and feasible-set conditions. It also identifies extensions and limitations for sharper complexity results.
- Contributions: The method combines stochastic approximation with iterative variance reduction for pseudo-monotone stochastic variational inequalities.It requires only pseudo-monotonicity and Lipschitz continuity, while accommodating unbounded feasible sets and non-uniform oracle variance.
- Contributions: The generated sequence is uniformly bounded in Lp when the stochastic error has finite p-moment.The paper provides explicit estimates for convergence, oracle complexity, and p-moments.
- Contributions: The analysis includes distributed solution of Cartesian stochastic variational inequalities.This extends the scope to distributed settings involving network users.
- Future work: Sharp complexity estimates for exponential convergence remain a direction for future research.Earlier exponential-convergence analyses assume a uniform tail bound that may fail for unbounded feasible sets and can be conservative even on compact sets.
- Error bounds: Natural-residual error bounds hold for several important variational-inequality classes, including semi-stable and certain strongly monotone or linear-cone problems.These bounds relate distance to the solution set to the natural residual near solutions.
Appendix. Proof of lemmas.
The appendix develops technical bounds for the stochastic extragradient analysis. It combines projection identities, martingale moment estimates, and pseudo-monotonicity arguments to control iterates and stochastic errors.
- Extragradient recursion: The proof initializes the stochastic extragradient step by defining an intermediate point from the sampled oracle and projecting it onto X.The construction uses yk := xk − αk bF(εk 2, zk) followed by xk+1 = Π(yk).
- Extragradient recursion: Projection inequalities decompose squared-distance terms into iterate, intermediate-point, and oracle contributions.The derivation applies projection geometry and algebraic identities to obtain recursive bounds.
- Extragradient recursion: Pseudo-monotonicity makes the solution-related inner-product term nonpositive in the key recursion.This sign property is combined with the projection relations to control the distance to a solution.
- Moment estimates: Higher-moment bounds are derived by treating accumulated stochastic errors as vector-valued martingales.The proof uses filtrations, independence assumptions, Minkowski and Cauchy–Schwarz inequalities, and the BDG inequality.
- Moment estimates: The stronger Assumption 8(iii) gives sharper increment bounds, whose proof is omitted because it follows essentially the same argument.This appendix therefore records the sharper result without reproducing its full derivation.