← All setups

Full Range Cohypomonotone Mlmc — Full-Range Cohypomonotone Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Full-Range Cohypomonotone Inclusions · Lean proof

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¯∥]≤ε.

Proved result

⌈279⋅(1+L⋅R(1−ρ⋅L)⋅ε+σ2ε2)(1−ρ⋅L)2⋅(1+log⁡(2+L⋅Rε+σ2ε2)+log⁡(21−ρ⋅L))7⌉+

OracleTemplate.Convergence LongTails.Setups.FullRangeCohypomonotoneInclusion.spec
  LongTails.Theorems.FullRangeCohypomonotoneMlmc.budget

Relevant previous results

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