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
The fixed-point problem is to find
Our assumptions:
Assumption 1 (Power-smooth norm). There exists a map
Assumption 2 (Nonexpansiveness and initial
distance). The map
Assumption 3 (Unbiased oracle with bounded moment).
Let
Queries may be made anywhere in
Results
A separable real Banach space satisfies
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) PowerSmoothAnchoring
(Ours) |
|||
| (2) Dual Halpern (Lee 2026), Thm. 3 | (1): at fixed |
(1): logarithmic loss
when |
|
| (3) Recursive anchoring (Diakonikolas et al. 2026), Cor. 6 | (1): on whole-space maps
preserving this ball, fixed |
(1) needs whole-space
nonexpansiveness; expectation only. Markov conversion has polynomial
confidence cost. Excludes weak-type norms such as |
|
| (4) Repository (LongTails, n.d.) | (1) extends geometry and
noise moments to |
(1) at |
Abbr: Costs count individual stochastic oracle
samples, including batches.