← All setups

Stochastic Cohypomonotone Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Cohypomonotone Inclusions

We consider solving 0∈F(x)+A(x) in a finite-dimensional real inner product space E, where F:E→E is L-Lipschitz and A:E⇉E is monotone. The sum F+A is ρ-cohypomonotone, with L>0, ρ≥0, and 2ρL<1. A given point x0∈E lies within distance R≥0 of a solution. The oracle returns unbiased estimates of F with independent sampling and variance at most σ2, where σ≥0, or exact resolvent evaluations of A. For ε>0, the goal is a measurable pair (x¯,a¯) with a¯∈A(x¯) for every realization and E∥F(x¯)+a¯∥≤ε, averaging over sampling and algorithm randomness.

The inclusion problem is to find x∈E such that 0∈F(x)+A(x). Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The algorithm receives E, the measurable sample space Ω, L, ρ, R, σ, ε, and x0.

Our assumptions:

Assumption 1 (Lipschitz continuity and cohypomonotonicity). For every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥. For every a∈A(x) and b∈A(y), monotonicity of A and cohypomonotonicity of F+A mean ⟨a−b,x−y⟩≥0,⟨F(x)+a−F(y)−b,x−y⟩≥−ρ∥F(x)+a−F(y)−b∥2.

Assumption 2 (Initial distance). There exists x⋆∈E satisfying −F(x⋆)∈A(x⋆),∥x0−x⋆∥≤R.

Assumption 3 (Stochastic operator access). There is a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For each 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. The samples (ξk)k≥0 are measurable, mutually independent, and each has law ν. They are independent of the algorithm’s randomness. A stochastic query at x∈E on call k returns g(x,ξk).

Assumption 4 (Exact resolvent access). There is a map J:R×E→E such that, for every γ>0 and z∈E, z−J(γ,z)γ∈A(J(γ,z)). A resolvent query (γ,z)∈R×E returns J(γ,z) exactly. The stated resolvent condition applies to positive γ.

Each call chooses either a stochastic query or a resolvent query; both count toward the same total oracle-call budget. The index k counts calls of either kind.

The output (x¯,a¯)∈E×E must be measurable and satisfy a¯∈A(x¯) for every realization. Its residual norm must be integrable and obey EP[∥F(x¯)+a¯∥]≤ε, where P is the joint law of the oracle samples and the independent algorithm randomness.

Results

In a finite-dimensional real inner-product space, F is L-Lipschitz and G is monotone with an everywhere-defined exact resolvent JγG for every γ>0. For v∈(F+G)(x) and w∈(F+G)(y), ⟨v−w,x−y⟩≥−ρ∥v−w∥2, with L>0 and 0≤2ρL<1. A zero x⋆ satisfies ∥x0−x⋆∥≤R. The jointly measurable oracle g has integrable samples and squared errors, ∫g(x,ω)dp=F(x) and ∫∥g(x,ω)−F(x)∥2dp≤σ2; samples are IID with law p under P. Target: a measurable pair (x¯,u) with u∈G(x¯) on every path and ∫∥F(x¯)+u∥dP≤ε. Parameters L,ρ,R,σ,ε are supplied; R,σ≥0, ε>0. Costs count every F sample and every resolvent evaluation.

Stochastic cohypomonotone inclusions: StochasticCohypomonotoneInclusion.
Result Oracle complexity Novelty Limitations
(1) RegularizedProxExtragradientCohypomonotone (Ours) (⋆⋆⋆) (review) O(τ−8(1+LRε+σ2ε2)
⋅[ℓ+log⁡(1/τ)]4)
(2) (Alacaoglu et al. 2026, Cor. 4.1, Rem. C.7); stochastic, ρ<1/L O(L2R2σ2d4ε4
⋅polylog(LRdε,σε,1d)), for LR,σ≥ε. Resolvent residual; conversion to the target adds O(1+σ2/ε2) calls, absorbed here.
(1): ε−4→ε−2 up to logs for fixed L,R,σ>0, ρL<1/2, and small ε. Strong residual with an explicit certificate. (1) requires ρ<1/(2L) instead of 1/L; τ−8 diverges at 1/(2L) while d−4 remains bounded.
(3) RAIN++ (Chen and Luo 2024, Thm. 5.4, Prop. 5.3); G=0, saddle-gradient F, ρ≤1/(2L) O((1+LRε+σ2ε2)
⋅polylog(L,R,σ,ε−1)) expected F samples, including conversion to the original residual.
(1): Scope extends to composite inclusions. On the unconstrained overlap, matches polynomial parameter dependence, with a fixed budget instead of expected random cost. (1) incurs τ−8 and excludes ρ=1/(2L).
(4) AR (Ji et al. 2026, Thm. 2.2); monotone F, G=NX, closed convex X, 0<ε≤LR O(1+LRεh+σ2ε2ℓ3h2) samples and projections; E[resF(x¯)2]≤ε. (1): Scope extends from monotone constrained VIs to nonmonotone cohypomonotone inclusions with general resolvents; matches polynomial accuracy dependence on the overlap. (1) has larger logarithmic overhead at ρ=0 and proves expected norm, rather than root-mean-square residual accuracy.
(5) (Alacaoglu et al. 2026, Thm. 2.1, Cor. 2.2); deterministic, σ=0, ρ<1/L O((1+LRd2ε)
⋅[1+log(1+LRdε)]) exact F and resolvent calls.
(1): Scope extends to noisy oracles; no established improvement when σ=0. (1) has larger logarithmic and ρ dependence, and requires ρ<1/(2L) instead of 1/L.

Abbr: τ=1−2ρL; d=1−ρL; ℓ=1+log⁡(1+LR/ε); h=1+log⁡ℓ; JγG=(I+γG)−1; NX is the normal cone; resF(x)=dist(0,F(x)+NX(x)); E is expectation under the sampling law; polylog denotes the cited guarantee’s unspecified logarithmic factors in the displayed parameters, with logarithms bounded below by one.

Alacaoglu, Ahmet, Donghwan Kim, and Stephen J. Wright. 2026. Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity. https://doi.org/10.48550/arXiv.2402.05071.
Chen, Lesi, and Luo Luo. 2024. “Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization.” Journal of Machine Learning Research 25 (387): 1–44. https://jmlr.org/papers/v25/22-1126.html.
Ji, Yao, Guanghui Lan, and Jason Zhu. 2026. Computation of Strong Solutions to Stochastic Variational Inequalities. https://doi.org/10.48550/arXiv.2609.04188.

Lean setup