← All setups

Stochastic Banach Fixed Points

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

A finite-dimensional real Banach space E with its Borel measurable structure; C≥1, R,σ≥0, ε>0. There is a continuous J:E→E∗ with ∥J(x)∥≤∥x∥ and ∥x+y∥2≤∥x∥2+2J(x)[y]+C∥y∥2. The nonexpansive map T:E→E has Tx⋆=x⋆ and ∥x0−x⋆∥≤R. A jointly measurable oracle g satisfies ∫g(x,ξ)dp(ξ)=Tx and ∫∥g(x,ξ)−Tx∥2dp(ξ)≤σ2, with these integrands integrable. Samples are IID with marginal probability measure p under probability measure P. Target: measurable output Z with integrable squared residual and ∫∥TZ−Z∥2dP≤ε2. The construction uses R,C,σ,ε; the setup imposes no algorithm restriction.

Stochastic fixed points in smooth norms: StochasticSmoothBanachFixedPoint.
Result Oracle complexity Novelty Limitations
(1) StochasticSmoothBanachFixedPoint (Ours) (⋆⋆⋆) (review) O((1+R/ε+Cσ2/ε2)ℓ4)
(2) Dual Halpern (Lee 2026, Thm. 3) O(R/ε+(p−1)Rσ2/ε3). Whole-space ℓp, 2≤p<∞, 0<ε≤R; expected residual ≤ε. (1): noise term saves R/(εℓ4); total gain when R/ε≫ℓ4 and (p−1)σ2/ε2≫ℓ4. RMS strengthens expected residual. (1): loses ℓ4 at negligible noise (fixed p); excludes 1<p<2 and p=∞ covered by (2).
(3) Recursive anchoring (Diakonikolas et al. 2026, Thm. 5, Cor. 6) O([Dε+(p−1)Dσ2ε3]
⋅polylog(D/ε)[1+log⁡(1/δ)]). Invariant compact ℓp ball, 2≤p<∞, diameter D, radial retraction, ε≤D/2; HP residual.
(1): on whole-space maps preserving that ball, R≤D, fixed δ, noise term saves D/ε up to logarithms. No invariant compact domain needed. (1) requires whole-space T; excludes nonsmooth type-2 norms and ℓ∞. HP conversion costs O((1+D/(εδ)+Cσ2/(δε2))ℓδ4): polynomial confidence loss.
(4) VR-GHAL (Diakonikolas 2026, Cor. 1) Oκ,log⁡(1/δ)([1+(R+σ)2ε2+(R+σ)6ε5]
⋅polylog(2+(R+σ)/ε)). Variance-only oracle; quadratically smoothable norm; anytime HP residual.
(1): on smooth native norms, fixed positive remaining parameters and constant confidence, ε−5 becomes ε−2 up to logarithms for the shared probability target. (1) gives no anytime HP guarantee; requires the native norm to be smooth, excluding merely equivalent smoothable norms such as ℓ∞.
(5) VR-GHAL (Diakonikolas 2026, Cor. 3) Oκ,log⁡(1/δ)([1+(R+σ)2ε2+(R+σ)4ε]
⋅polylog(2+(R+σ)/ε)). Samplewise nonexpansive oracle with same-seed queries; quadratically smoothable norm; anytime HP residual.
(1): removes samplewise nonexpansiveness while matching the ε−2 exponent up to logarithms at constant confidence. Other parameter factors are not compared. (1) loses anytime HP accuracy and applicability to merely equivalent smoothable norms, including ℓ∞.
(6) RAIN (Chen and Luo 2024, Thm. 4.2 and subsequent remark) O(1+Rε[1+log⁡ℓ]+σ2ε2ℓ3). Hilbert special case C=1, applied to I−T; expected residual ≤ε. (1): matches known polynomial rate in Hilbert space, up to logarithms. (1) pays extra logarithmic factors.

Abbr: R: initial fixed-point distance bound; σ2: oracle variance bound; C: squared-norm smoothness (C=p−1 in ℓp, 2≤p<∞); ℓ=1+log⁡(1+R/ε); D: invariant-domain diameter; ℓδ=1+log⁡(1+D/(εδ)); HP: residual at most ε with probability at least 1−δ, 0<δ<1; RMS: root mean square. Costs count individual oracle evaluations, including batches and paired queries. polylog denotes logarithmic factors left unspecified in the cited bounds. The subscript κ,log⁡(1/δ) retains unspecified smoothability and logarithmic-confidence dependence: κ=Ba2 for an equivalent squared-norm smoothness constant B and norm distortion a (native smooth case: κ=C).

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://jmlr.org/papers/v25/22-1126.html.
Diakonikolas, Jelena. 2026. Solving Stochastic Fixed-Point Equations with High Probability. https://doi.org/10.48550/arXiv.2607.09097.
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.

Lean setup