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.
Introduction
The Krasnosel'skii-Mann (KM) iteration is a cornerstone of convex optimization, serving as the underlying mechanism for algorithms like the Proximal Point Method, ADMM, and various splitting schemes. It aims to find a fixed point of a nonexpansive map $T$ in a Banach space through the update rule $x_{n+1} = (1-\alpha)x_n + \alpha Tx_n$. While the convergence properties of the exact KM iteration are well-understood, practical implementations often involve "inexact" steps due to numerical noise, approximate sub-problem solutions, or infeasible iterates.
Analyzing these inexact iterations in Banach spaces is significantly more challenging than in Hilbert spaces, as the lack of an inner product prevents the use of standard geometric tools like the parallelogram law. This paper addresses this gap by establishing tight convergence rates for Inexact Krasnosel'skii-Mann (IKM) iterations.
The Probabilistic Proof Technique
The authors analyze the IKM scheme defined by: $$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.
To overcome the geometric limitations of Banach spaces, the paper introduces a novel probabilistic proof technique. The convergence analysis is reduced to studying a Markov reward process on a 2D grid. This process is conceptualized as a "fox and hare" race, where the fox (representing the current iterate) pursues the hare (the target fixed point).
By calculating the expected rewards in this stochastic model, the authors derive a deterministic "master inequality" for the fixed-point residual $\|x_n - Tx_n\|$. This approach not only simplifies the analysis in Banach spaces but also preserves the tightness of the convergence constants, such as the $1/\sqrt{\pi}$ factor known from the exact case.
Key Convergence Results
The paper provides explicit rates of convergence based on the decay of the error sequence $\|e_n\|$:
- Optimal Rate: If errors decay as $O(1/n^a)$ for $a > 1$, the residual $\|x_n - Tx_n\|$ converges at the optimal rate of $O(1/\sqrt{n})$.
- Sub-optimal Decay: For slower error decay ($1/2 \le a < 1$), the residual converges at a rate of $O(1/n^{a-1/2})$.
- Robustness: One surprising finding is that the algorithm can tolerate "nonsummable" errors. Even if errors do not 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 and Extensions
The theoretical framework is highly versatile. The authors demonstrate its application to several variants of the basic iteration:
- Ishikawa Iterations: A two-step fixed-point iteration scheme.
- Diagonal KM Schemes: Where the operator $T$ varies at each step, allowing for dynamic optimization scenarios.
- Continuous-Time Systems: The results extend to nonautonomous evolution equations, proving that the system velocity $u'(t)$ vanishes at a rate of $O(1/\sqrt{t})$ even in the presence of external forcing terms.
Limitations and Future Outlook
While the results represent a significant step forward, they rely on certain theoretical constraints. The main results require that the iterates remain in a bounded region or that the operator $T$ has a bounded range. Additionally, the analysis is strictly for nonexpansive maps; extending these probabilistic techniques to "quasi-nonexpansive" or "$\alpha$-averaged" operators in Banach spaces remains an open direction for future research. Nevertheless, by bridging the gap between Hilbert and Banach spaces through a unique probabilistic lens, this work offers a powerful unified framework for analyzing a wide class of optimization algorithms.
Summary updated