← All setups

Inertial Monotone Residual — Stochastic Lipschitz Monotone Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Lipschitz Monotone Root Finding · Lean proof

Stochastic Lipschitz Monotone Root Finding

We seek a zero of a monotone, L-Lipschitz operator F:E→E on a finite-dimensional real Hilbert space E, where L>0. A given point x0∈E lies within distance R≥0 of a zero x⋆. At each query, the oracle returns an unbiased estimate of F(x) with mean squared error at most σ2, where σ≥0, using independent, identically distributed samples. For ε>0, the goal is a measurable output x¯∈E with integrable squared residual satisfying E∥F(x¯)∥2≤ε2, where expectation includes oracle and independent algorithm randomness.

The root-finding problem is find x∈E such that F(x)=0. Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. Let Ω be the measurable sample space. The algorithm receives E, Ω, x0, L, R, σ, and ε; it accesses F through the oracle.

Our assumptions:

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

Assumption 2 (Nearby zero). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R.

Assumption 3 (Stochastic operator oracle). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable under ν, the squared error ∥g(x,⋅)−F(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=F(x),Eξ∼ν[∥g(x,ξ)−F(x)∥2]≤σ2. At call k≥0, a query x∈E receives the reply g(x,ξk). The measurable sample variables (ξk)k≥0 are mutually independent with common law ν under a joint probability law on ΩN. Algorithm randomness is independent of this sample sequence.

Queries may be made at any point of E. Let P denote the joint law of the algorithm randomness and oracle samples. After the allotted oracle calls, the output x¯ must be measurable, its squared residual must be integrable under P, and EP[∥F(x¯)∥2]≤ε2.

Proved result

⌈222⋅(1+L⋅Rε+(σε)2⋅(log⁡(2+L⋅Rε))2)⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticLipschitzMonotone.spec
  LongTails.Theorems.InertialMonotoneResidual.budget

Relevant previous results

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