← All setups

Constrained Monotone Operators with Gap Noise

Descriptions may be stale. Consult the linked Lean sources.

Constrained Monotone Operators with Gap Noise

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 generalized Lipschitz bound, and a given point x0∈X lies near a solution. Two oracles return independent-sample unbiased estimates of F on X, with variance controlled by an operator gap, and exact projections onto X. For ε>0 and δ∈(0,1), the goal is a measurable output x¯∈X admitting u∈E with ⟨u,w−x¯⟩≤0 for every w∈X and ∥F(x¯)+u∥≤ε, with probability at least 1−δ.

The underlying 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 parameters satisfy L0>0,L1≥0,R>0,G,σ,v≥0. The algorithm receives E, a measurable sample space Ω, x0, and all parameters L0,L1,R,G,σ,v,ε,δ; it accesses F and X through the two oracles.

Our assumptions:

Assumption 1 (Feasibility and reference solution). The set X⊆E is convex and contains x0. There exists a solution x⋆ of the variational inequality satisfying ∥x0−x⋆∥≤R,∥F(x⋆)∥≤G. An exact projection map ΠX:E→E is available and satisfies, for every z∈E, ΠX(z)∈X,⟨z−ΠX(z),w−ΠX(z)⟩≤0for every w∈X.

Assumption 2 (Monotonicity and generalized Lipschitz bound). The operator F is continuous on E, and for all x,y∈E, ⟨F(x)−F(y),x−y⟩≥0. For every 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 (Gap-dependent stochastic noise). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈X, the random vector g(x,Z) is Bochner integrable and ∥g(x,Z)−F(x)∥2 is integrable for Z∼ν, with EZ∼ν[g(x,Z)]=F(x),EZ∼ν[∥g(x,Z)−F(x)∥2]≤σ2+v⟨F(x)−F(x⋆),x−x⋆⟩. The reference solution x⋆ is the same as above. The oracle samples (Zk)k≥0 are measurable, mutually independent, and each has law ν. This sequence is independent of the algorithm’s randomness.

Both oracles accept queries in E. At the kth oracle call, a stochastic query at x returns g(x,Zk), whereas a projection query at z returns ΠX(z). The stochastic moment conditions apply to queries in X. Stochastic-operator calls and projection calls are counted separately.

Define the normal cone at x∈X by NX(x)={u∈E:⟨u,w−x⟩≤0 for every w∈X}. After the allotted calls, the output x¯ must be measurable and satisfy P(¬[x¯∈X and ∃u∈NX(x¯):∥F(x¯)+u∥≤ε])≤δ, where P is the joint law of the oracle samples and the independent algorithm randomness.

Results

In a finite-dimensional real inner-product space, X is convex with exact projection, x0∈X, and F is continuous and monotone on the whole space. For every segment [x,y], ∥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. The jointly measurable, integrable IID oracle is unbiased on X, with integrable squared error bounded in expectation by σ2+v⟨F(x)−F(x⋆),x−x⋆⟩. Here L0,R,ε>0, L1,G,σ,v≥0, and 0<δ<1. Target: under the IID sampling law P, with probability at least 1−δ, the measurable output lies in X and admits ξ∈NX(x) with ∥F(x)+ξ∥≤ε.

Gap-dependent noise for constrained generalized-monotone VIs: GapNoiseConstrainedGeneralizedMonotone.
Result Oracle complexity Novelty Limitations
(1) GapNoiseConstrainedGeneralizedMonotone (Ours) (⋆⋆) (review) O([(L0+L1G+v)RQ2ε+Q4
+σ2Qε2]ℓ5)
(2) (Ji et al. 2026), Theorem 3.1 O([L0Rε+(vRε+σ2ε2)h13]j1)
RMS residual ≤ε; L1=0, ε≤L0R.
(1): Scope extends to L1>0 with gap noise, including non-Lipschitz cubic operators and unbounded variance. Matches polynomial accuracy dependence at L1=0. (1): no expected-residual guarantee; larger logarithmic overhead. Requires global monotonicity and smoothness, whereas (2) requires them only on X.
(3) Derived bound from (Ji et al. 2026), Theorem 3.1, Markov conversion O([L0Rεδ+(vRεδ+σ2ε2δ)hδ3]jδ)
L1=0, εδ≤L0R; target probability 1−δ.
(1): at L1=0, confidence dependence is log5⁡(1/δ) instead of δ−1/2,δ−1, under second moments only. (1): global operator assumptions instead of assumptions only on X.
(4) Projected clipped extragradient (Tyurin 2026) O([(L0+L1G)RQ2ε+Q4
+σ2ε2]a3(a+log⁡(1/δ)))
Special case v=0; same probability target.
(1): Scope replaces uniform variance by σ2+vgap, allowing unbounded variance on unbounded X; gap-noise cost is vRQ2/ε before logarithms. (1): at v=0, additive-noise term is larger by Q; greater logarithmic overhead and worse universal constant.

Abbr: Q=1+L1R; ℓ=1+log⁡((2+(L0+L1G)RQ2/ε+Q4)/δ); a=1+log⁡(2+(L0+L1G+L1ε)QR/ε); ht=1+log+⁡(L0R/(εt)); jt=(1+log⁡ht)O(1) denotes the polynomial iterated-log factor in the cited bound; log+⁡u=max{0,log⁡u}. RMS is root mean square. NX(x)={ξ:⟨ξ,w−x⟩≤0 ∀w∈X}; gap=⟨F(x)−F(x⋆),x−x⋆⟩. Costs count stochastic-operator samples and exact projections, including batches; their sum has the displayed order.

Ji, Yao, Guanghui Lan, and Jason Zhu. 2026. Computation of Strong Solutions to Stochastic Variational Inequalities. https://doi.org/10.48550/arXiv.2609.04188.
Tyurin, Alexander. 2026. LongTails: StochasticConstrainedGeneralizedMonotone. Repository theorem, commit cc147db, 24 October 2026. https://github.com/k3nfalt/longtails/blob/cc147db/LongTails/Theorems/StochasticConstrainedGeneralizedMonotone.lean.

Lean setup