← All setups

Full-Range Cohypomonotone Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Full-Range Cohypomonotone Inclusions

We seek a zero of F+A on a finite-dimensional real inner product space E. The map F:E→E is L-Lipschitz with L>0, the set-valued operator A:E⇉E is monotone, and F+A is ρ-cohypomonotone with 0≤ρ<1/L. A given point x0∈E lies within distance R≥0 of a solution. The oracle provides unbiased estimates of F with bounded variance using independent, identically distributed samples, or exact resolvent values of A at positive step sizes. For ε>0, the goal is a measurable pair (x¯,a¯) with a¯∈A(x¯) for every realization and E∥F(x¯)+a¯∥≤ε, averaging over oracle and algorithm randomness.

In terms of a point x⋆ and a vector a⋆, the inclusion is to find x⋆∈E,a⋆∈A(x⋆),F(x⋆)+a⋆=0. The algorithm receives E, the measurable sample space Ω, the starting point x0, and the parameters L,ρ,R,σ,ε, where σ≥0 bounds the root mean squared oracle error.

Our assumptions:

Assumption 1 (Operator inequalities). For all x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥. For every a∈A(x) and b∈A(y), write u=F(x)+a and v=F(y)+b. Monotonicity of A and cohypomonotonicity of F+A mean that ⟨a−b,x−y⟩≥0,⟨u−v,x−y⟩≥−ρ∥u−v∥2.

Assumption 2 (Initial distance). There exists a solution x⋆ of the inclusion such that ∥x0−x⋆∥≤R.

Assumption 3 (Stochastic evaluations and resolvent access). At call k, a query x∈E returns g(x,ξk), where g:E×Ω→E is jointly measurable. The samples (ξk)k≥0 are independent random variables with common law ν on Ω, and the sequence is independent of the algorithm’s randomness. For each x∈E and ξ∼ν, the vector g(x,ξ) is Bochner integrable, the squared error ∥g(x,ξ)−F(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=F(x),Eξ∼ν[∥g(x,ξ)−F(x)∥2]≤σ2. Alternatively, a query (γ,z)∈R×E returns Jγ(z)∈E. For every γ>0 and z∈E, this reply satisfies the resolvent identity z−Jγ(z)γ∈A(Jγ(z)). Both query types draw on the same call budget.

After the allotted calls, the output (x¯,a¯)∈E×E must be measurable and satisfy a¯∈A(x¯) for every realization. Under the joint law P of the samples and the algorithm’s randomness, the residual norm must be integrable and satisfy EP[∥F(x¯)+a¯∥]≤ε.

Results

In a finite-dimensional real inner-product space, F is L-Lipschitz (L>0), G is maximal monotone, and F+G is ρ-cohypomonotone with 0≤ρL<1. Some zero x⋆ of F+G satisfies ∥x0−x⋆∥≤R. Each call gives an exact resolvent of G or a jointly measurable, unbiased sample of F with variance at most σ2 using IID randomness. The target is a measurable pair (x,u) with u∈G(x) for every seed and E∥F(x)+u∥≤ε, ε>0.

Sufficient oracle budgets for full-range stochastic cohypomonotone inclusions.
Result Oracle complexity Novelty Limitations
(1) FullRangeCohypomonotoneMlmc (Ours) (⋆⋆⋆) (review) O(1+a/τ+bτ2ℓ7(1+a+bτ)) deterministic calls
(2) Inexact Halpern (Alacaoglu et al. 2026, Cor. 4.1) O(K4ℓ2(K)/τ2) for the last-iterate resolvent residual ∥z−Jη(F+G)z∥/η in root mean square. (1): For fixed L,R,ρ and σ>0, the cost drops from fourth to second order in 1/ε, up to logarithms as ε↓0, with an explicit graph certificate throughout ρL<1. (1) bounds the mean norm. (2) controls the second moment of its resolvent residual for maximally ρ-cohypomonotone F+G.
(3) RAIN++ (Chen and Luo 2025, Thm. 5.4 and Prop. 5.3) O~(1+a+b) expected samples, including conversion from saddle-envelope to original gradient accuracy. (1) extends (3) from unconstrained saddle-gradient operators (G=0, ρL≤1/2) to composite inclusions with ρL<1. On the overlap, polynomial rates match and (1) fixes the budget per seed.
(4) Regularized prox-extragradient (LongTails 2026b) O(1+a+bδ8ℓ4(1+aδ)) (1) extends ρL<1/2 to ρL<1. As ρL↑1/2, its condition factors stay bounded while (4) grows at least as δ−8. (1) has a seventh-power logarithm involving noise. (4) has a fourth-power logarithm independent of noise.
(5) Multistep anchored method (LongTails 2026a) O(1+⌈a/τ⌉ℓ(1/τ)/τ) exact calls. (1) allows finite-variance samples where (5) requires exact F. With exact F and a≥1, (1) pays a/τ3 times a seventh-power logarithm. (5) pays aℓ(1/τ)/τ2.

Abbr: a=LR/ε, b=σ2/ε2, τ=1−ρL, δ=1−2ρL, ℓ(t)=1+log⁡t for t≥1. In (2), JηH=(I+ηH)−1, η=(ρ+1/L)/2, K=1+L(R+σ)/(τε). In (3), O~ suppresses polylogarithmic factors.

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. 2025. Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization. https://doi.org/10.48550/arXiv.2208.05925.
LongTails. 2026a. LongTails: MultiStepAnchoredCohypomonotone. Lean theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/MultiStepAnchoredCohypomonotone.lean.
LongTails. 2026b. LongTails: RegularizedProxExtragradientCohypomonotone. Lean theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/RegularizedProxExtragradientCohypomonotone.lean.

Lean setup