← All setups

Stochastic Weak Minty Extragradient — Stochastic Weak Minty Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Weak Minty Root Finding · Lean proof

Stochastic Weak Minty Root Finding

We seek a zero of a Lipschitz operator F:E→E on a separable real Hilbert space E. A zero within a prescribed distance of the given starting point satisfies the weak Minty condition. At each query x∈E, the oracle uses a fresh independent sample to return an unbiased estimate of F(x) with uniformly bounded variance. For a tolerance ε>0, the goal is an output x¯∈E with integrable residual norm satisfying E∥F(x¯)∥≤ε, where the expectation includes both oracle and algorithm randomness.

The root-finding problem is find x∈E such that F(x)=0. The algorithm receives E with its Borel σ-algebra, the measurable sample space Ω, the starting point x0∈E, and the parameters L,ρ,σ,R,ε, whose ranges are L>0,0≤ρ≤120L,σ≥0,R≥0,ε>0.

Our assumptions:

Assumption 1 (Lipschitz continuity). For every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥.

Assumption 2 (Weak Minty condition). There exists x⋆∈E with F(x⋆)=0 and ∥x0−x⋆∥≤R such that ⟨F(x),x−x⋆⟩≥−ρ∥F(x)∥2for every x∈E.

Assumption 3 (Stochastic operator oracle). On call k, a query at any 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.

After the allotted oracle calls, the output x¯ must satisfy ∥F(x¯)∥∈L1(P),EP[∥F(x¯)∥]≤ε, where P is the joint law of the algorithm’s randomness and the oracle samples.

Proved result

⌈219⋅(1+L2⋅R2ε2)⋅(1+σ2ε2)⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticWeakMinty.spec
  LongTails.Theorems.StochasticWeakMintyExtragradient.budget

Relevant previous results