Optimal error bounds for non-expansive fixed-point iterations in normed spaces

DOI10.1007/S10107-022-01830-7MaRDI QIDQ6038647zbMATH OpenOpenAlexFDO

Authors Juan Pablo Contreras, Roberto Cominetti

Publication date 2 May 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.10969

zbMATH Keywords

convergence rateserror boundsfixed-point iterationsgeneral Mann iterationsnonexpansive maps

Mathematics Subject Classification ID

Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Fixed-point iterations (47J26) Numerical solutions to equations with nonlinear operators (65J15) Numerical methods for variational inequalities and related problems (65K15)

Abstract: This paper investigates optimal error bounds and convergence rates for general Mann iterations for computing fixed-points of non-expansive maps. We look for iterations that achieve the smallest fixed-point residual after $n$ steps, by minimizing a worst-case bound $|x^n-T{x}^n|le{R}_n$ derived from a nested family of optimal transport problems. We prove that this bound is tight so that minimizing $R_n$ yields optimal iterations. Inspired from numerical results we identify iterations that attain the rate $R_n=O(1/n)$, which we also show to be the best possible. In particular, we prove that the classical Halpern iteration achieves this optimal rate for several alternative stepsizes, and we determine analytically the optimal stepsizes that attain the smallest worst-case residuals at every step $n$, with a tight bound $R_{n}approxfrac4n+4$. We also determine the optimal Halpern stepsizes for affine non-expansive maps, for which we get exactly $R_n=frac1n+1$. Finally, we show that the best rate for the classical Krasnosel'skiu{i}-Mann iteration is $Omega(1/sqrtn)$, and present numerical evidence suggesting that even extended variants cannot reach a faster rate.

Recommendations

• On the convergence rate of the Halpern-iteration
• Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces
• Implicit error bounds for Picard iterations on Hilbert spaces
• On the rate of convergence of Krasnosel'skiĭ-Mann iterations and their connection with sums of Bernoullis
• General iteration algorithm and convergence rate optimal model for common fixed points of nonexpansive mappings

Cites work

• A first order method for solving convex bilevel optimization problems
• Accelerated proximal point method for maximally monotone operators
• Approximation of fixed points of nonexpansive mappings
• Computationally efficient bounds for the Catalan numbers
• Convergence of approximants to fixed points of nonexpansive nonlinear mappings in Banach spaces
• Convex analysis and monotone operator theory in Hilbert spaces
• Extension of uniformly continuous transformations and hyperconvex metric spaces
• Fixed point iterations of nonexpansive mappings
• Fixed points of nonexpanding maps
• scientific article; zbMATH DE number 3615396 (Why is no real title available?)
• scientific article; zbMATH DE number 887498 (Why is no real title available?)
• scientific article; zbMATH DE number 932401 (Why is no real title available?)
• scientific article; zbMATH DE number 3108780 (Why is no real title available?)
• Iterative Algorithms for Nonlinear Operators
• Iterative approximation of fixed points
• Krasnoselski-Mann Iterations in Normed Spaces
• Large-scale convex optimization. Algorithms \& analyses via monotone operators
• Lectures on convex optimization
• Mean Value Methods in Iteration
• On quantitative versions of theorems due to F. E. Browder and R. Wittmann
• On the convergence rate of the Halpern-iteration
• On the convolution of heterogeneous Bernoulli random variables
• On the Distribution of the Number of Successes in Independent Trials
• On the Distribution of the Number of Successes in Independent Trials
• On the logical analysis of proofs based on nonseparable Hilbert space theory
• On the rate of convergence of Halpern iterations
• On the rate of convergence of Krasnosel'skiĭ-Mann iterations and their connection with sums of Bernoullis
• Performance of first-order methods for smooth convex minimization: a novel approach
• Quantitative results for Halpern iterations of nonexpansive mappings
• Rates of asymptotic regularity for Halpern iterations of nonexpansive mappings
• Sharp convergence rates for averaged nonexpansive maps
• Strong convergence theorems for resolvents of accretive operators in Banach spaces
• The solution by iteration of nonlinear functional equations in Banach spaces
• Weak convergence theorems for nonexpansive mappings in Banach spaces

Cited in

(9)

• Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization
• Optimal bounds for round-off errors in the cyclic peaceman-rachford iteration
• [[:Publication:6091103|Fast Krasnosel’skiĭ–Mann Algorithm with a Convergence Rate of the Fixed Point Iteration of \(\boldsymbol{{ o} \left(\frac{1}Template:K \right)}\)]]
• The total variation-Wasserstein problem: a new derivation of the Euler-Lagrange equations
• An accelerated proximal alternating direction method of multipliers for optimal decentralized control of uncertain systems
• Accelerating preconditioned ADMM via degenerate proximal point mappings
• Universal complexity bounds based on value iteration for stochastic mean payoff games and entropy games
• Anderson acceleration of the proximal point method: the exact adaptive minimax, a spectral phase transition, and optimal safeguarding
• Tikhonov regularization of monotone operator flows not only ensures strong convergence of the trajectories but also speeds up the vanishing of the residuals

This page was built for publication: Optimal error bounds for non-expansive fixed-point iterations in normed spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038647)