← All setups

Stochastic Fixed Points in Banach Spaces

Descriptions may be stale. Consult the linked Lean sources.

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¯)∥]≤ε.

Results

A separable real Banach space E with its Borel structure admits j:E→E∗ satisfying ∥x+y∥2≤∥x∥2+2j(x)(y)+K∥y∥2. The map T:E→E is nonexpansive, Tx∗=x∗, and ∥x0−x∗∥≤D. A jointly measurable oracle G(x,ξ) uses IID samples of law p, with integrable replies, ∫G(x,ξ)dp(ξ)=Tx, and integrable squared error ∫∥G(x,ξ)−Tx∥2dp(ξ)≤σ2. Here K,σ≥0 and D,ε>0. Target: a measurable output x^ with integrable residual and ∫∥x^(ω)−Tx^(ω)∥dP(ω)≤ε, where P is the IID execution law.

Stochastic fixed-point residual complexity under StochasticFixedPointSmoothBanach.
Result Oracle complexity Novelty Limitations
(1) RecursiveAnchorKmSmoothBanach (Ours) (⋆⋆⋆) (review) O((1+D/ε)ℓ+Kσ2ℓ3/ε2)
(2) Dual Halpern (Lee 2026, Thm. 3)

O(D/ε+(p−1)Dσ2/ε3)

E=ℓpd, 2≤p<∞, 0<ε≤D.

(1): faster if (p−1)σ2≫ε2ℓ and D/ε≫ℓ3. For ℓ4, D=σ=1: O(ε−2ℓ3) versus O(ε−3). Scope extends to infinite-dimensional 2-smooth spaces. (1): extra factor ℓ in deterministic term; factor-ℓ loss when (p−1)σ2≲ε2.
(3) Recursive anchoring (Diakonikolas et al. 2026, Thm. 5)

O((B/ε+KBσ2/ε3)polylog(2+B/ε))

Expected-residual conversion on compact convex self-maps of diameter B, 0<ε≤B/2, 2-smooth norm, bounded retraction constant. Target ε/2, failure probability ε/(2B); logarithmic powers unspecified.

(1): on global maps preserving such a set with B≍D, noise dependence improves ε−3 to ε−2 up to logs; total gain requires Kσ2≫ε2polylog(2+D/ε) and D/ε≫ℓ3. (1): requires 2-smoothness rather than weak type 2, and a global map; loses high-probability residual guarantee.
(4) Batched Halpern (Shehu 2026, Thm. 4.3, Rem. 4.4)

O(D/ε+KD2σ2/ε4)

K≥1, 0<ε<D.

(1): noise term smaller by (D/ε)2/ℓ3 when this ratio exceeds one; no uniform total-cost dominance. (1): extra factor ℓ in deterministic term.
(5) RAIN, derived bound (Chen and Luo 2024, Thm. 4.2); reduction (Shehu 2026, Thm. 4.8)

O((1+D/ε)(1+log⁡ℓ)+σ2ℓ3/ε2)

Hilbert special case, K=1, via F=I−T.

(1): extends Hilbert scope to 2-smooth Banach spaces; matches the Hilbert noise term. (1): deterministic term worse by ℓ/(1+log⁡ℓ) on the Hilbert overlap.

Abbr: ℓ=1+log⁡(1+D/ε); K is the squared-norm smoothness constant (K=p−1 for ℓp, p≥2); B is a compact domain’s diameter. Costs count individual oracle samples, including batches. polylog denotes unspecified polynomial logarithmic factors. ≍ means equality up to universal factors; ≫ denotes asymptotic domination.

Chen, Lesi, and Luo Luo. 2024. “Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization.” Journal of Machine Learning Research 25 (387): 1–44. https://www.jmlr.org/papers/v25/22-1126.html.
Diakonikolas, Jelena, Cristóbal Guzmán, and David Martínez-Rubio. 2026. Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps. https://doi.org/10.48550/arXiv.2609.09524.
Lee, Jongmin. 2026. Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces. https://doi.org/10.48550/arXiv.2610.26484.
Shehu, Yekini. 2026. Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations. https://doi.org/10.48550/arXiv.2610.00295.

Lean setup