← All setups

Stochastic Power-Smooth Fixed Points

Descriptions may be stale. Consult the linked Lean sources.

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

Results

A separable real Banach space satisfies ∥x+y∥s≤∥x∥s+sj(x)y+K∥y∥s for some continuous-linear-functional-valued j, 1<s≤2, K≥1. The whole-space map T is nonexpansive, with Tx⋆=x⋆ and ∥x0−x⋆∥≤D. A jointly measurable IID oracle G(x,ξ) has integrable values, mean Tx, and integrable noise moment ∫∥G(x,ξ)−Tx∥sdμ≤σs. Here D,ε>0, σ≥0. Target: measurable output x^ with integrable residual and ∫∥x^−Tx^∥dP≤ε, where P is the IID sampling law.

Stochastic power-smooth fixed points: StochasticPowerSmoothFixedPoint.
Result Oracle complexity Novelty Limitations
(1) PowerSmoothAnchoring (Ours) (⋆⋆⋆) (review) O([1+D/ε+(216K)1/(s−1)(σ/ε)s/(s−1)]ℓs2+s/(s−1))
(2) Dual Halpern (Lee 2026), Thm. 3 Op(D/ε+Dσq/εq+1). Whole-space ℓpd, 1<p<2, second moment; 0<ε≤D. (1): at fixed p=3/2, D=σ=1, O(ε−3log5⁡(1/ε)) versus O(ε−4). Scope: power-smooth Banach spaces; only s-th moments. (1): logarithmic loss when σ≲ε; larger constants as p↓1. Does not cover ℓ∞.
(3) Recursive anchoring (Diakonikolas et al. 2026), Cor. 6 Op(ε−1[1+(σL/ε)q]L[L+log⁡(1/δ)]). Unit ℓpd ball self-map, 1<p<2, second moment, 0<ε≤1; success 1−δ. (1): on whole-space maps preserving this ball, fixed p,δ and noise-dominated small ε, saves a factor 1/ε up to logs. No invariant-domain assumption. (1) needs whole-space nonexpansiveness; expectation only. Markov conversion has polynomial confidence cost. Excludes weak-type norms such as ℓ∞.
(4) Repository (LongTails, n.d.) O((1+D/ε)ℓ+Kσ2ℓ3/ε2). Restricted to s=2. (1) extends geometry and noise moments to 1<s<2, including infinite-dimensional Lp, 1<p<2. (1) at s=2: initialization uses ℓ4 instead of ℓ; noise uses ℓ4 instead of ℓ3.

Abbr: Costs count individual stochastic oracle samples, including batches. q=p/(p−1); ℓs=3+log2⁡(1+16D/ε); ℓ=1+log⁡(1+D/ε); L=1+log⁡(1/ε); δ∈(0,1) is failure probability. Op permits constants depending on fixed p. On ℓpd, (1) uses s=p, K=4; μ is the sample law.

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://arxiv.org/abs/2610.26484v1.
LongTails: RecursiveAnchorKmSmoothBanach. n.d. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/RecursiveAnchorKmSmoothBanach.lean.

Lean setup