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
The fixed-point problem is to find
Our assumptions:
Assumption 1 (Smooth squared norm). There exists a
continuous map
Assumption 2 (Nonexpansiveness and initial
distance). The map
Assumption 3 (Stochastic oracle). There exist a
probability measure
Queries may be made at any point of
Results
A finite-dimensional real Banach space
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticSmoothBanachFixedPoint
(Ours) |
|||
| (2) Dual Halpern (Lee 2026, Thm. 3) | (1): noise term saves
|
(1): loses |
|
| (3) Recursive anchoring (Diakonikolas et al. 2026, Thm. 5, Cor. 6) | (1): on whole-space maps
preserving that ball, |
(1) requires whole-space
|
|
| (4) VR-GHAL (Diakonikolas 2026, Cor. 1) | (1): on smooth native
norms, fixed positive remaining parameters and constant confidence,
|
(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) | (1): removes samplewise
nonexpansiveness while matching the |
(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) | (1): matches known polynomial rate in Hilbert space, up to logarithms. | (1) pays extra logarithmic factors. |
Abbr: