← All setups

Stochastic Constrained Monotone Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Constrained Monotone Inclusions

We consider a variational inequality for a continuous monotone operator F:E→E on a convex set X in a finite-dimensional real Hilbert space E. The operator satisfies a segmentwise generalized Lipschitz bound with constants L0>0 and L1≥0. A given x0∈X lies within distance R>0 of a solution x⋆ with ∥F(x⋆)∥≤G, where G≥0. Two oracles return independent unbiased estimates of F(x) with variance at most σ2, where σ≥0, and exact projections onto X. For ε>0 and δ∈(0,1), the goal is a feasible output x¯ admitting a normal vector v, meaning ⟨v,w−x¯⟩≤0 for all w∈X, with ∥F(x¯)+v∥≤ε, with probability at least 1−δ.

The variational inequality is to find x⋆∈X such that ⟨F(x⋆),w−x⋆⟩≥0for every w∈X. The norm is induced by the inner product on E. The algorithm receives E, the measurable sample space Ω, x0, and the parameters L0,L1,R,G,σ,ε,δ; it accesses F and X through the two oracles. Both oracles accept queries at any point of E, and their calls are counted separately.

Our assumptions:

Assumption 1 (Constraint set and nearby solution). The set X is convex and contains x0. There exists a solution x⋆ of the variational inequality satisfying ∥x0−x⋆∥≤R,∥F(x⋆)∥≤G. The projection oracle returns ΠX(z) at z∈E, where ΠX(z)∈X,⟨z−ΠX(z),w−ΠX(z)⟩≤0for every w∈X.

Assumption 2 (Monotonicity and generalized Lipschitz continuity). The operator F is continuous on E and satisfies ⟨F(x)−F(y),x−y⟩≥0for all x,y∈E. For all x,y∈E and M∈R, the segment bound ∥F(x+θ(y−x))∥≤Mfor every θ∈[0,1] implies ∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Stochastic operator oracle). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−F(x)∥2 is integrable under ν, with EZ∼ν[g(x,Z)]=F(x),EZ∼ν[∥g(x,Z)−F(x)∥2]≤σ2. Let (Zk)k≥0 be measurable, mutually independent samples with common law ν, independent of the algorithm’s randomness. At the kth call across both oracles, a stochastic operator query at x returns g(x,Zk), while a projection query returns ΠX(x).

The output x¯∈E must be measurable. For x∈X, define the normal cone NX(x)={v∈E:⟨v,w−x⟩≤0 for every w∈X}. The required accuracy is P(x¯∈X and ∃v∈NX(x¯):∥F(x¯)+v∥≤ε)≥1−δ, where P is the joint law of the algorithm’s randomness and the independent sample sequence.

Results

A finite-dimensional real inner-product space; convex X with exact projection and x0∈X; continuous, globally monotone F satisfying ∥F(x)−F(y)∥≤(L0+L1supz∈[x,y]∥F(z)∥)∥x−y∥. A VI solution x⋆∈X satisfies ∥x0−x⋆∥≤R and ∥F(x⋆)∥≤G. Jointly measurable, integrable stochastic evaluations satisfy ∫g(x,ω)dp=F(x) and ∫∥g(x,ω)−F(x)∥2dp≤σ2, with IID samples of law p under P. Public parameters satisfy L0,R,ε>0, L1,G,σ≥0, 0<δ<1. Target: a measurable output Y with P{Y∈X, ∃v∈NX(Y):∥F(Y)+v∥≤ε}≥1−δ. Costs count all operator samples plus projections.

Stochastic constrained generalized-monotone variational inequalities: StochasticConstrainedGeneralizedMonotone.
Result Oracle complexity Novelty Limitations
(1) StochasticConstrainedGeneralizedMonotone (Ours) (⋆⋆⋆) (review) O([(L0+L1G)(1+L1R)2Rε
+(1+L1R)4+σ2ε2]ℓ3(ℓ+log⁡(1/δ)))
(2) AR+SOE (Ji et al. 2026, Thm. 2.2) O(L0Rεh(ε)+σ2ε2j(ε)3h(ε)2)
E[r(Y)2]≤ε; L1=0, ε≤L0R.
(1): Scope extends to L1>0 with polynomial L1R dependence. Matches polynomial accuracy dependence at L1=0, up to logarithms. (1): Extra logarithmic overhead; high-probability accuracy does not supply (2)’s mean-square residual guarantee.
(3) Derived bound: (Ji et al. 2026, Thm. 2.2), Markov conversion O(L0Rεδh(εδ)
+σ2ε2δj(εδ)3h(εδ)2)
P{r(Y)≤ε}≥1−δ; L1=0, εδ≤L0R.
(1): At L1=0, logarithmic confidence dependence replaces δ−1/2 and δ−1 factors in (3) only; no accuracy-exponent gain. (1): At fixed confidence, larger accuracy-logarithm powers: noise term log4 versus log3, apart from iterated logarithms.
(4) Clipped Korpelevich (Vankov et al. 2025, Thm. 4.4) Expected squared distance to the solution set; p-quasi-sharpness with μ>0, p≥2, and 0<α≤12. No comparable residual cost. (1): Scope covers monotone operators without quasi-sharpness at α=1; high-probability residual replaces expected distance. Rates are not comparable. (1): Requires global monotonicity; (4) also covers nonmonotone quasi-sharp operators.
(5) EG (Greenberg and Loizou 2026, Thm. 3.1) O(1+(L0+L1G)(1+L1ReL1R)R2ε)
Exact F (σ=0); averaged restricted gap ≤ε.
(1): Scope allows finite-variance noise; polynomial rather than exponential L1R dependence, for a returned-point residual rather than averaged gap. Rates are not comparable.

Abbr: NX(y)={v:⟨v,w−y⟩≤0 ∀w∈X}; r(y)=infv∈NX(y)∥F(y)+v∥. ℓ=1+log⁡(1+(L0+L1G+L1ε)(1+L1R)R/ε); j(t)=1+log⁡(L0R/t) and h(t)=1+log⁡j(t) for 0<t≤L0R. α is the exponent of ∥F∥ in generalized Lipschitz continuity; p-quasi-sharpness means ⟨F(x),x−z⟩≥μdist(x,X⋆)p for all solutions z. Restricted gap: supz∈B⟨F(z),y−z⟩, where B=X∩{z:∥z−x⋆∥≤cR} for the fixed universal radius factor in (5).

Greenberg, Ezra, and Nicolas Loizou. 2026. Extragradient and Past Extragradient Methods for (L0,L1)-Lipschitz Variational Inequalities. https://doi.org/10.48550/arXiv.2610.16886.
Ji, Yao, Guanghui Lan, and Jason Zhu. 2026. Computation of Strong Solutions to Stochastic Variational Inequalities. https://doi.org/10.48550/arXiv.2609.04188.
Vankov, Daniil, Angelia Nedić, and Lalitha Sankar. 2025. Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates. https://doi.org/10.48550/arXiv.2410.12334.

Lean setup