← All setups

Regularized Prox Extragradient Cohypomonotone — Stochastic Cohypomonotone Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Cohypomonotone Inclusions · Lean proof

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.

Proved result

⌈253(1−2⋅ρ⋅L)8⋅(1+L⋅Rε+σ2ε2)⋅(1+log⁡(2+L⋅Rε)+log⁡(21−2⋅ρ⋅L))4⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticCohypomonotoneInclusion.spec
  OracleTemplate.StochasticCohypomonotone.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.