Universal bounds for fixed point iterations via optimal transport metrics

Thierry Champion, Mario Bravo, Roberto Cominetti

Abstract

We present a self-contained analysis of a particular family of metrics over the set of non-negative integers. We show that these metrics, which are defined through a nested sequence of optimal transport problems, provide tight estimates for general Krasnosel'skii-Mann fixed point iterations for non-expansive maps. We also describe some of their very special properties, including their monotonicity and the so-called "convex quadrangle inequality" that yields a greedy algorithm to compute them efficiently.

Introduction

Many fundamental problems in optimization and signal processing are framed as finding a "fixed point"—a value $x$ such that $Tx = x$ for a non-expansive map $T$. The most general approach to solving these problems is the Krasnosel’skii-Mann (KM) iteration, which computes successive approximations as weighted averages of previous iterates.

While convergence is well-established, obtaining tight, universal error bounds—bounds that depend solely on the algorithm's weights rather than the specific function $T$—has historically been a significant challenge. This paper establishes a unified framework that treats the distance between iteration steps as a recursive optimal transport problem on integers, providing the sharpest possible theoretical bounds for a wide class of fixed-point algorithms.

Methodology

The core of the proposed framework is a family of metrics $d_{m,n}$ defined over non-negative integers. The weights used in the KM iteration are treated as probability distributions, denoted as $\pi^n$. The distance between iteration $m$ and $n$ is then defined as the cost of an optimal transport problem between these distributions.

Weight distributions $\pi^m$ and $\pi^n$ treated as probability masses for optimal transport.

Key technical components of this approach include:

  • Recursive Definition: The distance $d_{m,n}$ is built using distances from previous steps, creating a nested optimization structure.
  • Kantorovich-Rubinstein Duality: This duality provides an alternative characterization of the metric, which is essential for proving the "tightness" of the bounds.
  • The Inside-Out Algorithm: Under a "drifting mass" assumption (where the algorithm prioritizes more recent iterates), the authors demonstrate that the metric satisfies a convex quadrangle inequality. This property allows complex optimization to be replaced by a simple, efficient greedy algorithm.

As a theoretical work, the framework was evaluated by applying it to well-known iteration schemes such as the standard Krasnosel’skii iteration, Halpern’s method, and the Ishikawa iteration.

Theoretical Insights

Universal Tightness

The most significant finding is that the distance $\|x^m - x^n\|$ is universally bounded by $d_{m,n}$. This bound is independent of the map $T$ or the underlying space; as long as $T$ is non-expansive, this bound is the best achievable. The authors prove this by showing that for any sequence of weights, there exists a "worst-case" map $T$ where the error exactly equals their bound.

Geometry and Combinatorics

By viewing algorithm weights as probability mass, the research reveals that moving from one iteration to another is equivalent to moving mass efficiently across time steps. The discovery of the "Inside-Out" property—where optimal transport flows are nested and do not cross—simplifies the mathematics significantly.

Visualization of the convex quadrangle inequality for distances $d_{i,j}$, which enables efficient greedy computation.

Furthermore, a surprising connection was found between the polynomials describing these bounds and the "postage stamp problem" in number theory, suggesting a deep combinatorial structure underlying fixed-point theory.

Key Results and Convergence Rates

The framework provides explicit rates for several methods. For Halpern's method, the authors show the residual $\|x^n - Tx^n\|$ scales as $O(\frac{\ln n}{n})$ or $O(\frac{1}{n})$ depending on weight settings, refining previous literature. They also formally prove that under standard conditions, the distance from the starting point increases monotonically as the algorithm progresses, matching the intuitive "drift" observed in these methods.

Limitations and Future Work

While these bounds are universally tight, they may not be tight for specific geometric spaces. For instance, in Hilbert spaces, which possess more "rounded" geometry than the $\ell^\infty$ spaces used for the tightness proof, faster convergence rates may be possible. Additionally, while the paper provides a way to evaluate bounds for given weights, the "inverse problem" of determining the absolute optimal weights for the fastest possible convergence remains an open area for future research. Finally, the efficient greedy algorithm relies on the assumption that mass gradually drifts toward larger integers, which, while common, does not cover every possible iterative scheme.

Summary updated

Abstract

We present a self-contained analysis of a particular family of metrics over the set of non-negative integers. We show that these metrics, which are defined through a nested sequence of optimal transport problems, provide tight estimates for general Krasnosel'skii-Mann fixed point iterations for non-expansive maps. We also describe some of their very special properties, including their monotonicity and the so-called "convex quadrangle inequality" that yields a greedy algorithm to compute them efficiently.
BibTeX
@inproceedings{champion2022universal,
  author = {Thierry Champion and Mario Bravo and Roberto Cominetti},
  title = {{Universal bounds for fixed point iterations via optimal transport metrics}},
  booktitle = {Applied Set-Valued Analysis and Optimization},
  year = {2022},
  doi = {10.23952/asvao.4.2022.3.04},
}

Loading related content...

Figure