← All setups

Stochastic Generalized Monotone Equations

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Generalized Monotone Equations

We seek a zero of a continuous monotone operator F:E→E on a finite-dimensional real Hilbert space E. For L0,L1≥0, its Lipschitz constant along each segment is bounded by L0+L1M whenever M bounds the operator norm values on that segment. A given point x0∈E lies within distance R≥0 of a zero. The oracle returns unbiased estimates of F(x) with variance at most σ2, where σ≥0, using independent, identically distributed samples. Given ε>0 and δ∈(0,1), the goal is a measurable output x¯∈E with ∥F(x¯)∥≤ε with probability at least 1−δ over oracle and independent algorithm randomness.

The operator equation is F(x)=0,x∈E. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. Let Ω be the measurable sample space. The algorithm receives E, Ω, L0, L1, x0, R, σ, ε, and δ; it accesses F through the oracle.

Our assumptions:

Assumption 1 (Continuity and monotonicity). The operator F is continuous, and for every x,y∈E, ⟨F(x)−F(y),x−y⟩≥0.

Assumption 2 (Generalized Lipschitz condition). For every x,y∈E and M∈R, the following implication holds: ∥F(x+θ(y−x))∥≤Mfor all θ∈[0,1]⟹∥F(x)−F(y)∥≤(L0+L1M)∥x−y∥.

Assumption 3 (Nearby zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R.

Assumption 4 (Stochastic operator oracle). There exist 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 Eξ∼ν[g(x,ξ)]=F(x),Eξ∼ν[∥g(x,ξ)−F(x)∥2]≤σ2. At call k≥0, a query x∈E receives g(x,ξk). The sample variables (ξk)k≥0 are measurable, mutually independent, and each has law ν. The algorithm’s randomness is independent of the entire sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable and satisfy PP(∥F(x¯)∥>ε)≤δ, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Results

On a finite-dimensional real Hilbert space, F is continuous and monotone, F(x⋆)=0, ∥x0−x⋆∥≤R, and ∥F(x)−F(y)∥≤(L0+L1supz∈[x,y]∥F(z)∥)∥x−y∥. The jointly measurable oracle satisfies ∫g(x,ω)dp=F(x) and ∫∥g(x,ω)−F(x)∥2dp≤σ2, with integrable values and squared errors, and IID samples of law p under P. Here L0,L1,R,σ≥0, ε>0, 0<δ<1. Target: measurable output X with P{∥F(X)∥>ε}≤δ.

Stochastic generalized monotone root finding: StochasticGeneralizedMonotone.
Result Oracle complexity Novelty Limitations
(1) StochasticGeneralizedMonotone (Ours) (⋆⋆⋆) (review) O([1+L0Rε+(L1R)2+σ2ε2]
⋅log3⁡Qlog⁡(Q/δ)) stochastic calls, including batches and repetitions.
(2) (Ji et al. 2026), Thm. 2.2; globally Lipschitz special case L1=0, L0>0 O(L0Rεh+σ2ε2ℓ3h2) stochastic calls; ε≤L0R; (E∥F(X)∥2)1/2≤ε on the unconstrained restriction. (1): Scope extends to L1>0 with polynomial dependence and additive variance cost. At L1=0, matches polynomial accuracy dependence; gives high-probability accuracy under finite variance. (1): Extra logarithmic overhead at L1=0, including confidence dependence; no constrained-VI guarantee.
(3) (Vankov et al. 2025), Thm. 4.4, p=2; quasi-sharp, 0<α≤12 O(1+dRaτ+σ2+K1σ2αa2τ) stochastic calls for Edist2(X,X⋆)≤τ; two calls per iteration. (1): No quasi-sharpness assumption; permits α=1, including monotone operators with ⟨F(x),x−x⋆⟩=0 near roots. Residual and distance rates are not comparable. (1): Does not cover constrained or structured non-monotone problems covered by (3).
(4) Anchored extragradient (LongTails, n.d.); exact-oracle special case σ=0, L0>0 O(1+L0Rε+(1+L1R)
⋅log(1+(L0+L1G)Rε)) exact calls; deterministic residual accuracy.
(1): Scope extends to noisy finite-variance oracles; no initial-residual bound G needed for its budget. (1): At σ=0, quadratic rather than linear L1R term, with additional logarithms; loses anytime last-iterate guarantee.

Abbr: Q=2+L0R/ε+L1R, ℓ=1+log⁡(L0R/ε) and h=1+log⁡ℓ in (2); G≥∥F(x0)∥ in (4). In (3), X⋆ is the solution set, τ>0 is squared-distance accuracy, R2≥Edist2(x0,X⋆), and quasi-sharpness means ⟨F(x),x−x⋆⟩≥μdist2(x,X⋆), μ>0. The exponent α replaces 1 on the segment operator norm in generalized Lipschitz continuity; its constants are denoted L¯0,L¯1. Set cα=2α2/(1−α), K0=L¯0(cα+1), K1=L¯1cα3α, K2=L¯11/(1−α)cα3α(1−α)α/(1−α), a=μmin{1,[2(CF+σ)]−1}, d=max{4μ,23(K0+K1+K2)}, where CF≥supkE∥F(xk)∥.

Ji, Yao, Guanghui Lan, and Jason Zhu. 2026. Computation of Strong Solutions to Stochastic Variational Inequalities. https://doi.org/10.48550/arXiv.2609.04188.
LongTails: AnchoredGeneralizedMonotone.lean. n.d. Lean theorem in the LongTails repository. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AnchoredGeneralizedMonotone.lean.
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