Recursive Anchor Km Smooth Banach — Stochastic Fixed Points in Banach Spaces
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Fixed Points in Banach Spaces · Lean proof
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
Proved result
OracleTemplate.Convergence LongTails.Setups.StochasticFixedPointSmoothBanach.spec
OracleTemplate.RecursiveAnchorKm.budgetRelevant previous results
- Lesi Chen and Luo Luo. Near-Optimal
Algorithms for Making the Gradient Small in Stochastic Minimax
Optimization. 2024 (preprint 2022; published version used).
Complexity:
stochastic operator calls using RAIN for in Euclidean space, with and ; fixed total cost including initialization. - Yekini Shehu. Adaptivity, Anchoring, and
the Exact Oracle Complexity of Stochastic Fixed-Point Iterations.
2026 (preprint v1). Complexity:
stochastic map calls using the RAIN reduction in Hilbert space for , where ; fixed total cost including initialization.