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

Juan Pablo Contreras, Roberto Cominetti

TL;DR

This paper identifies the fundamental limits of how fast we can find fixed points for non-expansive maps in general normed spaces. The authors prove that Halpern-type iterations are theoretically superior to the widely used Krasnosel’skiĭ-Mann iterations, achieving an $O(1/n)$ convergence rate compared to $O(1/\sqrt{n})$, and they derive the exact "perfect" stepsizes to reach these optimal bounds.

What Problem Does This Paper Address?

Many problems in science and engineering—from convex optimization and signal processing to solving differential equations—boil down to finding a "fixed point" of a mapping $T$, where $Tx = x$. A common class of these mappings is non-expansive maps, where the distance between two points doesn't increase after applying the map ($||Tx - Ty|| \le ||x - y||$).

While several iterative algorithms (collectively known as Mann iterations) exist to find these points, researchers have long debated:

  1. What is the best possible "worst-case" error bound after $n$ steps?
  2. Which specific algorithm and stepsizes achieve this limit?
  3. Is there a fundamental gap between different styles of iteration?

Methods

The authors employ a sophisticated mathematical framework based on Optimal Transport. They model the error bound of an iteration as a nested family of optimal transport problems.

Key technical steps include:

  • Tightness Proofs: They prove that the theoretical bounds derived from optimal transport are "tight," meaning there actually exists a worst-case map $T$ that hits that error exactly.
  • Sequential Optimization: Because finding the best coefficients for all $n$ steps at once is computationally "hard" (non-convex), they propose a sequential optimization approach to find the best averaging parameters step-by-step.
  • Analytical Derivation: For the specific case of Halpern iterations, they move beyond numerical simulations to derive a closed-form recursive formula for the optimal stepsizes.

Datasets

As a theoretical mathematics paper, no external datasets were used. The authors performed numerical experiments by simulating the iterations themselves to observe the behavior of the error bounds ($R_n$) across different algorithmic variants.

Key Insights and Ideas

  • The Power of the Anchor: The "Halpern iteration" differs from the "Krasnosel’skiĭ-Mann" iteration because it always keeps a "link" to the starting point $y^0$. The paper shows this "anchor" is crucial; it allows the algorithm to escape the $O(1/\sqrt{n})$ speed trap that limits other methods.
  • Optimal Stepsize Recursion: For Halpern iterations, the authors found that the optimal stepsizes $\beta_n$ follow a beautiful, simple quadratic recursion: $\beta_{n+1} = \frac{1}{2}(1 + \beta_n^2)$.
  • Linear vs. Nonlinear: A surprising "aha moment" is that for linear (affine) maps, the optimal stepsizes for Halpern's method are exactly $\beta_n = n/(n+1)$, which yields an even tighter error bound of $1/(n+1)$.
  • The $O(1/n)$ Limit: The paper establishes that $O(1/n)$ is the "speed limit" for any general Mann iteration in a normed space. You simply cannot go faster without assuming more structure about the space (like it being a Hilbert space).

Key Results

  • Halpern is King: The authors prove Halpern’s iteration achieves the optimal rate of $R_n \approx \frac{4}{n+4}$.
  • KM is Slower: The classical Krasnosel’skiĭ-Mann iteration is proven to be stuck at a rate of $\Omega(1/\sqrt{n})$, and even adding "extra terms" or inertial effects doesn't seem to break this barrier in general normed spaces.
  • Linear Efficiency: For affine maps, the bound improves to exactly $R_n = \frac{1}{n+1}$.
  • Tightness: They provide a simple "right-shift" operator example that proves no Mann iteration can ever beat the $1/(n+1)$ residual bound, providing a definitive lower bound for the field.

Limitations and Future Work

The primary limitation is that these bounds are for general normed spaces. In specific environments, like Hilbert spaces, the geometry is "nicer" (thanks to the parallelogram identity), and some iterations might behave differently or allow for even tighter constants.

The authors also note that while they've optimized the residual ($||x^n - Tx^n||$), this doesn't always guarantee fast convergence to the fixed point itself ($||x^n - x^*||$) in spaces that aren't "uniformly smooth." Future research could look at bridging the gap between residual reduction and actual distance-to-solution in more restrictive settings.

Summary updated

Abstract

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 $\|x^n-Tx^n\|\le R_n$ derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing $R_n$ yields optimal iterations. Inspired from numerical results we identify iterations that attain the rate $R_n=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 $R_n\approx\frac{4}{n+4}$. We also determine the optimal Halpern stepsizes for affine non-expansive maps, for which we get exactly $R_n=\frac{1}{n+1}$. Finally, we show that the best rate for the classical Krasnosel'ski\uı-Mann iteration is $Ω(1/\sqrt{n})$, and present numerical evidence suggesting that even extended variants cannot reach a faster rate.
BibTeX
@article{contreras2023optimal,
  author = {Juan Pablo Contreras and Roberto Cominetti},
  title = {{Optimal error bounds for nonexpansive fixed-point iterations in normed spaces}},
  journal = {Math. Program.},
  year = {2023},
  doi = {10.1007/s10107-022-01830-7},
}

Loading related content...

Figure