Krasnosel'skii-Mann iterations beyond asymptotics: a combinatorial analysis

We revisit the classical Krasnosel'skii-Mann fixed point iteration for contractions and nonexpansive maps in general normed spaces.

This iteration is ubiquitous across a wide range of areas, including convex optimization, monotone inclusions, Markov decision processes, under-relaxed methods for nonlinear PDEs, and more.

Drawing on a remarkable connection with a Markov chain on $\mathbb{Z}^2$, and using counting arguments from enumerative combinatorics of lattice paths, we derive explicit estimates for the distance between iterates, as well as non-asymptotic error bounds for the fixed point residuals.

As the contraction parameter approaches one, these bounds smoothly recover the known estimates for nonexpansive maps.

Building upon these estimates, we further derive error bounds for inexact Krasnosel'skii-Mann iterations.