← All setups

Recursive Anchor Km Smooth Banach — Stochastic Fixed Points in Banach Spaces

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Fixed Points in Banach Spaces · Lean proof

Stochastic Fixed Points in Banach Spaces

We seek a fixed point of a nonexpansive map T:E→E on a separable real Banach space E with a 2-uniformly smooth norm ∥⋅∥. A given point x0∈E lies within distance D>0 of a fixed point x⋆. At x∈E, the oracle returns an unbiased estimate of T(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 residual satisfying E[∥x¯−T(x¯)∥]≤ε, averaging over oracle and independent algorithm randomness.

The fixed-point problem is to find x∈E such that T(x)=x. Equip E with its Borel sigma-algebra. Let Ξ be a measurable sample space, let ν be a probability measure on Ξ, and write G:Ξ×E→E for the sampled map. The algorithm receives E, Ξ, x0, and the parameters K≥0, D>0, σ≥0, and ε>0; the map T, the sampled map G, and the distribution ν are accessed through the oracle.

Our assumptions:

Assumption 1 (Uniform smoothness of the norm). There exists a map j:E→E∗, where E∗ is the continuous real dual of E, such that ∥x+y∥2≤∥x∥2+2j(x)(y)+K∥y∥2,x,y∈E.

Assumption 2 (Nonexpansiveness and initial distance). The map T satisfies ∥T(x)−T(y)∥≤∥x−y∥,x,y∈E. There exists x⋆∈E such that T(x⋆)=x⋆,∥x0−x⋆∥≤D.

Assumption 3 (Unbiased stochastic oracle). The map G is jointly measurable. For every x∈E, the random vector G(ξ,x) is Bochner integrable under ξ∼ν, and ∥G(ξ,x)−T(x)∥2 is integrable, with Eξ∼ν[G(ξ,x)]=T(x),Eξ∼ν[∥G(ξ,x)−T(x)∥2]≤σ2. At call k≥0, a query x∈E receives G(ξk,x). The measurable samples (ξk)k≥0 are mutually independent with common law ν under their joint probability law on ΞN. The algorithm’s randomness is independent of this sample sequence.

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

Proved result

⌈(log2⁡(1+Dε)+4)⋅(16+20⋅Dε+2048⋅K⋅σ2⋅(log2⁡(1+Dε)+4)2ε2)⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticFixedPointSmoothBanach.spec
  OracleTemplate.RecursiveAnchorKm.budget

Relevant previous results