← All setups

Cohypomonotone Operator Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Cohypomonotone Operator Inclusions

We seek a zero of F+A on a real inner product space E, where F:E→E is L-Lipschitz and A:E⇉E is monotone. The sum is ρ-cohypomonotone, with L>0, ρ≥0, and ρL<1. A given point x0∈E is within distance R≥0 of a zero. The oracle returns exact values of F and resolvent evaluations of A. For ε>0, the goal is an output x¯∈E admitting ξ∈A(x¯) with ∥F(x¯)+ξ∥≤ε, almost surely under the law of the algorithm’s randomness.

The inclusion problem is to find x∈E such that 0∈F(x)+A(x), where F(x)+A(x)={F(x)+a:a∈A(x)}. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The algorithm receives only E, L, ρ, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

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

Assumption 2 (Cohypomonotonicity). For every x,y∈E, a∈A(x), and b∈A(y), setting u=F(x)+a and v=F(y)+b, we have ⟨u−v,x−y⟩≥−ρ∥u−v∥2.

Assumption 3 (Resolvent access). There is a map J:R×E→E, written Jγ(z), such that, for every γ>0 and z∈E, z−Jγ(z)γ∈A(Jγ(z)). The oracle returns F(x) for a query x∈E, or Jγ(z) for a query (γ,z)∈R×E. These replies are exact. For γ≤0, the map Jγ is unrestricted. Both query types count toward the same oracle-call budget.

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

After the allotted oracle calls, the output must satisfy ∃ξ∈A(x¯)∥F(x¯)+ξ∥≤εP-a.s., where P is the law of the algorithm’s randomness. The required output is x¯; the residual witness ξ need not be returned.

Results

In a real inner-product space, F is L-Lipschitz, H is monotone with exact everywhere-defined resolvents JγH for every γ>0, and F+H satisfies ⟨g−h,x−y⟩≥−ρ∥g−h∥2 for g∈(F+H)(x), h∈(F+H)(y). Assume L>0, 0≤ρL<1, and a zero x⋆ with ∥x0−x⋆∥≤R. Target: ∃ξ∈H(u) with ∥F(u)+ξ∥≤ε, ε>0. Each evaluation of F and each resolvent evaluation counts as one call.

Residual complexity for CohypomonotoneInclusion.
Result Oracle complexity Novelty Limitations
(1) MultiStepAnchoredCohypomonotone (Ours) (⋆⋆) (review) O(1+(LRδ2ε+1{R>0}δ)log⁡eδ)
(2) Inexact Halpern (Alacaoglu et al. 2026), Thm. 2.1, Cor. 2.2, Rem. 2.3 O(1δ+LRδ2εlog(e+LRδε)) (1): At fixed ρL and LR>0, removes log⁡(1/ε) as ε→0. Comparison on Rd with maximal H and maximally cohypomonotone F+H. Scope: arbitrary inner-product spaces; sum maximality unassumed, without established additional Hilbert-space instances. (1): Can lose up to log⁡(e/δ) when LR≲ε.
(3) Composite FEG (Cai et al. 2024), Thm. 4.1; special case ρL<1/2 O(1+LR(1−2ρL)ε) (1): Extends ρL<1/2 to ρL<1. On the Rd, maximal-H overlap, avoids (1−2ρL)−1 blow-up as ρL↑1/2, giving O(1+LR/ε). (1): Double loop instead of single loop; worse leading constants away from ρL=1/2.
(4) Derived bound from AEP (Jiang and Yoon 2026), Thm. 3.2

O(1+(LRδ2ε+1{R>0}δ)log⁡eδ)

Via w=u+ρg, g∈(F+H)(u), and warm-started inner contraction under the shared assumptions.

(1): Matches the derived rate; formalizes the explicit full-range application of the monotone relative-error framework.

Abbr: δ=1−ρL∈(0,1]; R≥0 is the initial-distance bound; 1{R>0} is the indicator of R>0; JγH=(I+γH)−1; log is natural; FEG: fast extragradient; AEP: anchored extra-proximal. Costs sum all inner and outer oracle calls.

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.
Cai, Yang, Argyris Oikonomou, and Weiqiang Zheng. 2024. Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion. https://doi.org/10.48550/arXiv.2206.05248.
Jiang, Ruichen, and TaeHo Yoon. 2026. Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems. https://doi.org/10.48550/arXiv.2609.30212.

Lean setup