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

Abstract

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.

Disclosure

“timately led us to Krattenthaler’s work on lattice paths [25], which paved the way for the precise formulation and proof of Theorem 1. The connection with binomial distributions presented in §3.1 was identified later with the assistance of ChatGPT. The proof of Proposition 7, however, as well as all subsequent analysis, is entirely our own. We take full responsibility for the content of the manuscript. References [1] Baillon, J.-B. and”

PDF page 24

Classification

Brainstorming or outlining

Multiplier

2

Verified

2026-08-23T18:59:01.088508Z

Structural counts