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
The fixed-point problem is to find
Our assumptions:
Assumption 1 (Uniform smoothness of the norm). There
exists a map
Assumption 2 (Nonexpansiveness and initial
distance). The map
Assumption 3 (Unbiased stochastic oracle). The map
Queries may be made at any point of
Results
A separable real Banach space
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RecursiveAnchorKmSmoothBanach
(Ours) |
|||
| (2) Dual Halpern (Lee 2026, Thm. 3) | (1): faster if |
(1): extra factor |
|
| (3) Recursive anchoring (Diakonikolas et al. 2026, Thm. 5) | Expected-residual conversion on compact convex self-maps of diameter
|
(1): on global maps
preserving such a set with |
(1): requires |
| (4) Batched Halpern (Shehu 2026, Thm. 4.3, Rem. 4.4) | (1): noise term smaller
by |
(1): extra factor |
|
| (5) RAIN, derived bound (Chen and Luo 2024, Thm. 4.2); reduction (Shehu 2026, Thm. 4.8) | Hilbert special case, |
(1): extends Hilbert
scope to |
(1): deterministic term
worse by |
Abbr: