Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces

Mario Bravo, Roberto Cominetti, Matías Pavez-Signé

This paper, titled "Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces," provides a rigorous theoretical foundation for understanding how errors affect one of the most fundamental algorithms in optimization.

TL;DR

The authors establish a new, tight metric bound for the convergence rate of "inexact" Krasnosel'skii-Mann (KM) iterations in general Banach spaces. By employing a novel probabilistic proof technique—modeling the algorithm as a "fox and hare" Markov process—they show how residuals converge even when computations are noisy or projections are only approximate.

What Problem Does This Paper Address?

In the world of convex optimization, many popular algorithms (like the Proximal Point Method, ADMM, and Forward-Backward splitting) are actually specific instances of the Krasnosel'skii-Mann (KM) iteration. This iteration is used to find a "fixed point" of a nonexpansive map $T$ (a function that doesn't move points further apart).

The standard KM iteration is a simple weighted average: $x_{n+1} = (1-\alpha)x_n + \alpha Tx_n$. While we have known the convergence rates for the "exact" version for years, real-world applications are rarely exact. We deal with:

  1. Numerical noise or precision limits.
  2. Approximate sub-problems where $Tx_n$ is only estimated.
  3. Infeasible iterates where we must project back onto a constraint set approximately.

Previous research often restricted these "inexact" analyses to Hilbert spaces (which have a "nice" geometry). This paper tackles the much harder case of Banach spaces, which lack an inner product, making standard geometric proofs impossible.

Methods

The authors introduce the Inexact Krasnosel'skii-Mann (IKM) scheme: $$x_{n+1} = (1-\alpha_{n+1})x_n + \alpha_{n+1}(Tx_n + e_{n+1})$$ where $e_{n+1}$ represents the error at each step.

The core innovation is the Probabilistic Proof Technique. Instead of relying on traditional functional analysis, the authors reduce the recursive error bounds to a Markov reward process. They visualize the iteration as a race on a 2D grid between a "fox" (the current iterate) and a "hare" (the target fixed point).

  • The fox tries to catch the hare.
  • The "rewards" collected during this process correspond to the accumulated errors ($e_n$).
  • By calculating the expected reward in this stochastic game, they derive a deterministic bound for the algorithm's residual $\|x_n - Tx_n\|$.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, the results are proven via rigorous deduction rather than empirical testing on specific datasets.

Key Insights and Ideas

  • The Fox and the Hare: The use of a Markov chain to prove convergence in Banach spaces is a brilliant "aha moment." It bypasses the need for the parallelogram law (which only holds in Hilbert spaces) by using the properties of random walks instead.
  • Preserving Tightness: The paper maintains the constant $1/\sqrt{\pi}$ in its bounds. This constant is known to be "tight" (the best possible) for the exact case, and the authors show it carries over to the inexact setting.
  • Mild Error Requirements: One surprising finding is that the algorithm can tolerate "nonsummable" errors. Even if the errors don't vanish extremely quickly, the residual can still converge to zero at a predictable rate, provided the step sizes ($\alpha_n$) are chosen appropriately.
  • Unified Framework: The authors show their main result (Theorem 1.1) is a "master inequality" that can be used to derive rates for several other algorithms, including the Ishikawa iteration and diagonal schemes where the operator $T$ changes over time.

Key Results

The paper provides explicit convergence rates for the residual $\|x_n - Tx_n\|$ based on the decay rate of the errors $\|e_n\|$:

  • Standard Rate: If errors decay as $O(1/n^a)$ with $a > 1$, the residual converges at the optimal rate of $O(1/\sqrt{n})$.
  • Slower Decay: If errors decay more slowly (e.g., $1/2 \le a < 1$), the residual converges at a rate of $O(1/n^{a-1/2})$.
  • Continuous Time: The authors successfully extend these discrete results to continuous-time evolution equations, proving that the velocity of the system $u'(t)$ vanishes at a rate of $O(1/\sqrt{t})$ even in the presence of external forcing terms.

Limitations and Future Work

  • Boundedness Assumption: The main results rely on assumption $(H_0)$, which requires that the iterates remain in a bounded region or that the operator $T$ has a bounded range. While often true in practice, it is a theoretical constraint.
  • Step Size Constraints: Most specific rates assume the step sizes $\alpha_n$ are bounded away from 0 and 1. Exploring "vanishing" step sizes (like $1/n$) leads to logarithmic rates, which are significantly slower.
  • Nonexpansivity: The work is strictly for nonexpansive maps. Extending these probabilistic techniques to "quasi-nonexpansive" or "$\alpha$-averaged" operators in Banach spaces remains an open direction.

Summary updated

Abstract

We study the convergence of an inexact version of the classical Krasnosel’skii–Mann iteration for computing fixed points of nonexpansive maps. Our main result establishes a new metric bound for the fixed-point residuals, from which we derive their rate of convergence as well as the convergence of the iterates towards a fixed point. The results are applied to three variants of the basic iteration: infeasible iterations with approximate projections, the Ishikawa iteration, and diagonal Krasnosels’kii–Mann schemes. The results are also extended to continuous time in order to study the asymptotics of nonautonomous evolution equations governed by nonexpansive operators.
BibTeX
@article{bravo2019rates,
  author = {Mario Bravo and Roberto Cominetti and Matías Pavez-Signé},
  title = {{Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces}},
  journal = {Math. Program.},
  year = {2019},
  doi = {10.1007/s10107-018-1240-1},
}

Loading related content...

Figure