← All setups

Stochastic Smooth Banach Fixed Point — Stochastic Banach Fixed Points

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Banach Fixed Points · Lean proof

Stochastic Banach Fixed Points

We consider finding a fixed point of a nonexpansive map T:E→E on a finite-dimensional real Banach space E with a smooth squared norm controlled by C≥1. A given point x0∈E is within distance R≥0 of a fixed point. At x∈E, the oracle returns an unbiased estimate of T(x) using a fresh independent sample, with expected squared error at most σ2, where σ≥0. For ε>0, the goal is a measurable output x¯∈E with EP∥T(x¯)−x¯∥2≤ε2, where P is the joint law of sampling and independent algorithm randomness.

The fixed-point problem is to find x∈E such that T(x)=x. Write ∥⋅∥ for the norm on E and E∗ for its continuous real dual. Operator norms are the induced operator norms. The algorithm receives E, the measurable sample space Ω, x0, C, R, σ, and ε; it accesses T through the stochastic oracle.

Our assumptions:

Assumption 1 (Smooth squared norm). There exists a continuous map J:E→E∗ such that, for every x,y∈E, ∥J(x)∥op≤∥x∥,∥x+y∥2≤∥x∥2+2J(x)[y]+C∥y∥2.

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⋆∥≤R.

Assumption 3 (Stochastic 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,⋅)−T(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=T(x),Eξ∼ν[∥g(x,ξ)−T(x)∥2]≤σ2. At call k≥0, a query x∈E receives the reply g(x,ξk). The measurable random variables (ξk)k≥0 are mutually independent with common law ν, and the entire sample sequence is independent of the algorithm’s randomness.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable, its squared fixed-point residual must be integrable under P, and it must satisfy EP[∥T(x¯)−x¯∥2]≤ε2.

Proved result

⌈220⋅(1+Rε+C⋅σ2ε2)⋅(1+log⁡(1+16⋅Rε))4⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticSmoothBanachFixedPoint.spec
  LongTails.Theorems.StochasticSmoothBanachFixedPoint.budget

Relevant previous results

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