← All setups

Stochastic Lipschitz Monotone Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Lipschitz Monotone Root Finding

We seek a zero of a monotone, L-Lipschitz operator F:E→E on a finite-dimensional real Hilbert space E, where L>0. A given point x0∈E lies within distance R≥0 of a zero x⋆. At each query, the oracle returns an unbiased estimate of F(x) with mean squared error at most σ2, where σ≥0, using independent, identically distributed samples. For ε>0, the goal is a measurable output x¯∈E with integrable squared residual satisfying E∥F(x¯)∥2≤ε2, where expectation includes oracle and independent algorithm randomness.

The root-finding problem is find x∈E such that F(x)=0. Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. Let Ω be the measurable sample space. The algorithm receives E, Ω, x0, L, R, σ, and ε; it accesses F through the oracle.

Our assumptions:

Assumption 1 (Monotonicity and Lipschitz continuity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥0,∥F(x)−F(y)∥≤L∥x−y∥.

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

Assumption 3 (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 under ν, the squared error ∥g(x,⋅)−F(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=F(x),Eξ∼ν[∥g(x,ξ)−F(x)∥2]≤σ2. At call k≥0, a query x∈E receives the reply g(x,ξk). The measurable sample variables (ξk)k≥0 are mutually independent with common law ν under a joint probability law on ΩN. Algorithm randomness is independent of this sample sequence.

Queries may be made at any point of E. Let P denote the joint law of the algorithm randomness and oracle samples. After the allotted oracle calls, the output x¯ must be measurable, its squared residual must be integrable under P, and EP[∥F(x¯)∥2]≤ε2.

Results

In a finite-dimensional real Hilbert space with its Borel structure, F is monotone and globally L-Lipschitz, and F(x⋆)=0 with ∥x0−x⋆∥≤R. Here L,ε>0 and R,σ≥0. The jointly measurable oracle g has integrable values and squared errors, ∫g(x,ω)dp=F(x) and ∫∥g(x,ω)−F(x)∥2dp≤σ2. Samples are IID with marginal probability law p and joint law P. The target is ∫∥F(z(ξ))∥2dP(ξ)≤ε2. Result (1) constructs batched inertial regularized extragradient, tuned using L,R,σ,ε; the setup imposes no algorithm restriction.

Stochastic monotone root finding: StochasticLipschitzMonotone.
Result Oracle complexity Novelty Limitations
(1) InertialMonotoneResidual (Ours) (⋆⋆) (review) O(1+LRε+σ2ε2ℓ2)
(2) RRSEG (Lee and Kim 2026), Cor. 6.2 O(1+LRε+σ2ε2log3⁡(2+LRε+σε)); A=0 specialization. (1) saves at least a factor ℓ when σ2ℓ2/ε2≥LR/ε; otherwise matches the deterministic order. (1) uses growing batches instead of two calls per update; does not cover composite inclusions.
(3) Accumulative regularization (Ji et al. 2026), Thm. 2.2 O(1+LRεh+σ2ε2ℓ3h2); 0<ε≤LR, unconstrained specialization. (1) replaces the statistical factor ℓ3h2 by ℓ2. For fixed L,R,σ>0, the total saving grows as ℓh2 as ε→0. (1) does not cover constrained variational inequalities.
(4) S-Dual-OHM (Yoon and Loizou 2026), Cor. 3.6 O((1+LRε)ℓ+σ2ε2ℓ2); samplewise monotone, uniformly L-Lipschitz maps; same-sample queries. (1) needs only mean regularity and fresh samples. On the overlap, removes the deterministic ℓ factor; total gain when σ2≲εLR/ℓ. Statistical order matches.

Abbr: ℓ=1+log⁡(1+LR/ε); h=1+log⁡ℓ. Costs count individual stochastic operator evaluations, including batches and inner solves; A denotes the additional maximally monotone operator in an inclusion 0∈F(x)+A(x).

Ji, Yao, Guanghui Lan, and Jason Zhu. 2026. Computation of Strong Solutions to Stochastic Variational Inequalities. https://arxiv.org/abs/2609.04188v2.
Lee, Sucheol, and Donghwan Kim. 2026. Accelerated Algorithms for Stochastic Monotone Inclusions with Fixed Queries. https://arxiv.org/abs/2609.35631v1.
Yoon, TaeHo, and Nicolas Loizou. 2026. Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding. https://arxiv.org/abs/2609.36033v1.

Lean setup