← All setups

Power Smooth Anchoring — Stochastic Power-Smooth Fixed Points

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Power-Smooth Fixed Points · Lean proof

Stochastic Power-Smooth Fixed Points

We seek a fixed point of a nonexpansive map T:E→E on a separable real Banach space E whose norm is power-smooth with exponent s∈(1,2] and constant K≥1. A given point x0∈E lies within distance D>0 of a fixed point x⋆. At any query x∈E, the oracle returns an unbiased estimate of T(x) using an independent sample, with error sth moment at most σs, where σ≥0; this permits heavy-tailed noise. For ε>0, the goal is a measurable output x¯∈E with integrable residual satisfying EP∥x¯−T(x¯)∥≤ε, where P is the joint law of algorithm and oracle randomness.

The fixed-point problem is to find x∈E such that T(x)=x. Equip E with its Borel sigma-algebra, and let Ξ be the measurable sample space. The algorithm receives E, Ξ, x0, s, K, D, σ, and ε; it accesses T through the stochastic oracle described below.

Our assumptions:

Assumption 1 (Power-smooth norm). There exists a map j:E→E∗, where E∗ is the continuous real dual of E, such that ∥x+y∥s≤∥x∥s+sj(x)(y)+K∥y∥s,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 oracle with bounded moment). Let ν be a probability measure on Ξ, and let G:Ξ×E→E be jointly measurable. For every x∈E, the random vector G(ξ,x) is Bochner integrable under ξ∼ν, the scalar ∥G(ξ,x)−T(x)∥s is integrable, and Eξ∼ν[G(ξ,x)]=T(x),Eξ∼ν[∥G(ξ,x)−T(x)∥s]≤σs. At call k∈{0,1,…}, a query x∈E receives G(ξk,x). The measurable samples (ξ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 anywhere in E. After the allotted oracle calls, the output x¯ must be measurable, its residual ∥x¯−T(x¯)∥ must be integrable under P, and the accuracy requirement is EP[∥x¯−T(x¯)∥]≤ε.

Proved result

⌈512⋅(1+Dε+(65536⋅K⋅(σε)exponent)1exponent−1)⋅(3+log2⁡(1+16⋅Dε))2+exponentexponent−1⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticPowerSmoothFixedPoint.spec
  LongTails.Theorems.PowerSmoothAnchoring.budget

Relevant previous results

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