|   | 
Author Contreras, J.P.; Cominetti, R.
Title Optimal error bounds for non-expansive fixed-point iterations in normed spaces Type
Year 2022 Publication Mathematical Programming Abbreviated Journal Math. Program.
Volume (down) Early Access Issue Pages
Keywords Non-expansive maps; Fixed-point iterations; Error bounds; Convergence rates
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 parallel to x(n) – Tx(n)parallel to <= 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 approximate to 4/n+4. We also determine the optimal Halpern stepsizes for affine non-expansive maps, for which we get exactly R-n = 1/n+1. Finally, we show that the best rate for the classical Krasnosel'skii-Mann iteration is Si (11 Omega(1/root n), and present numerical evidence suggesting that even extended variants cannot reach a faster rate.
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
Area Expedition Conference
Notes WOS:000805887100002 Approved
Call Number UAI @ alexi.delcanto @ Serial 1577
Permanent link to this record