# Optimal error bounds for nonexpansive fixed-point iterations in normed spaces

arXiv: https://arxiv.org/abs/2108.10969 · HTML: https://mlsanity.com/paper/2108.10969/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Aug 2021.

## Built on by (most cited first, 12 of 12)

- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [Faster Fixed-Point Methods for Multichain MDPs](https://mlsanity.com/paper/2506.20910/) (2025)
- [Finite-Time Bounds for Average-Reward Fitted Q-Iteration](https://mlsanity.com/paper/2510.17391/) (2025)
- [A Unifying View of Anchoring via Operator-Side Tikhonov Regularization](https://mlsanity.com/paper/2605.30905/) (2026)
- [Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps](https://mlsanity.com/paper/2609.09524/) (2026)
- [Polyak-Type Extragradient Methods for Monotone Root-Finding Problems](https://mlsanity.com/paper/2609.26581/) (2026)
- [Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity](https://mlsanity.com/paper/2609.28543/) (2026)
- [Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding](https://mlsanity.com/paper/2609.36033/) (2026)

## Abstract (arXiv)

This paper investigates optimal error bounds and convergence rates for general Mann iterations for computing fixed-points of non-expansive maps. We look for iterations that achieve the smallest fixed-point residual after n steps, by minimizing a worst-case bound |xn-Txn|≤ Rn derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing Rn yields optimal iterations. Inspired from numerical results we identify iterations that attain the rate Rn=O(1/n), which we also show to be the best possible. In particular, we prove that the classical Halpern iteration achieves this optimal rate for several alternative stepsizes, and we determine analytically the optimal stepsizes that attain the smallest worst-case residuals at every step n, with a tight bound Rn≈frac4n+4. We also determine the optimal Halpern stepsizes for affine non-expansive maps, for which we get exactly Rn=frac1n+1. Finally, we show that the best rate for the classical Krasnosel'skiui-Mann iteration is Omega(1/√n), and present numerical evidence suggesting that even extended variants cannot reach a faster rate.