Optimal error bounds for non-expansive fixed-point iterations in normed spaces

Juan Pablo Contreras, Roberto Cominetti

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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≈4n+4. We also determine the optimal Halpern stepsizes for affine non-expansive maps, for which we get exactly Rn=1n+1. Finally, we show that the best rate for the classical Krasnosel’skiĭ–Mann iteration is Ω(1/n), and present numerical evidence suggesting that even extended variants cannot reach a faster rate.

Original languageEnglish
Pages (from-to)343-374
Number of pages32
JournalMathematical Programming
Issue number1-2
StatePublished - May 2023
Externally publishedYes


  • Convergence rates
  • Error bounds
  • Fixed-point iterations
  • Non-expansive maps


Dive into the research topics of 'Optimal error bounds for non-expansive fixed-point iterations in normed spaces'. Together they form a unique fingerprint.

Cite this