Convergence analysis of the Halpern iteration with adaptive anchoring parameters

He, Songnian; Xu, Hong-Kun; Dong, Qiao-Li; Mei, Na

doi:10.1090/mcom/3851

Convergence analysis of the Halpern iteration with adaptive anchoring parameters
HTML articles powered by AMS MathViewer

by Songnian He, Hong-Kun Xu, Qiao-Li Dong and Na Mei

Math. Comp. 93 (2024), 327-345

DOI: https://doi.org/10.1090/mcom/3851

Published electronically: May 17, 2023

HTML | PDF | Request permission

Abstract:

We propose an adaptive way to choose the anchoring parameters for the Halpern iteration to find a fixed point of a nonexpansive mapping in a real Hilbert space. We prove strong convergence of this adaptive Halpern iteration and obtain the rate of asymptotic regularity at least $O(1/k)$, where $k$ is the number of iterations. Numerical experiments are also provided to show advantages and outperformance of our adaptive Halpern algorithm over the standard Halpern algorithm.

References

Radu Ioan Boţ, Ernö Robert Csetnek, and Dennis Meier, Inducing strong convergence into the asymptotic behaviour of proximal splitting algorithms in Hilbert spaces, Optim. Methods Softw. 34 (2019), no. 3, 489–514. MR 3937043, DOI 10.1080/10556788.2018.1457151
H. Cheval, U. Kohlenbach, and L. Leuştean, On modifined Halpern and Tikhonov-Mann iterations, arXiv:2203.11003v3[math.OC], 11 Apr 2022.
Benjamin Halpern, Fixed points of nonexpanding maps, Bull. Amer. Math. Soc. 73 (1967), 957–961. MR 218938, DOI 10.1090/S0002-9904-1967-11864-0
J. Diakonikolas, Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities, arXiv:2002.08872v3. Proceedings of Thirty Third Conference on Learning Theory, PMLR 125, pp. 1428–1451, 2020.
Kazimierz Goebel and W. A. Kirk, Topics in metric fixed point theory, Cambridge Studies in Advanced Mathematics, vol. 28, Cambridge University Press, Cambridge, 1990. MR 1074005, DOI 10.1017/CBO9780511526152
Kazimierz Goebel and Simeon Reich, Uniform convexity, hyperbolic geometry, and nonexpansive mappings, Monographs and Textbooks in Pure and Applied Mathematics, vol. 83, Marcel Dekker, Inc., New York, 1984. MR 744194
Songnian He, Qiao-Li Dong, Hanlin Tian, and Xiao-Huan Li, On the optimal relaxation parameters of Krasnosel’skiĭ-Mann iteration, Optimization 70 (2021), no. 9, 1959–1986. MR 4307803, DOI 10.1080/02331934.2020.1767101
Songnian He, Tao Wu, Yeol Je Cho, and Themistocles M. Rassias, Optimal parameter selections for a general Halpern iteration, Numer. Algorithms 82 (2019), no. 4, 1171–1188. MR 4032910, DOI 10.1007/s11075-018-00650-1
Tae-Hwa Kim and Hong-Kun Xu, Strong convergence of modified Mann iterations, Nonlinear Anal. 61 (2005), no. 1-2, 51–60. MR 2122242, DOI 10.1016/j.na.2004.11.011
Ulrich Kohlenbach, On quantitative versions of theorems due to F. E. Browder and R. Wittmann, Adv. Math. 226 (2011), no. 3, 2764–2795. MR 2739793, DOI 10.1016/j.aim.2010.10.002
U. Kohlenbach and L. Leuştean, Effective metastability of Halpern iterates in CAT(0) spaces, Adv. Math. 231 (2012), no. 5, 2526–2556. MR 2970458, DOI 10.1016/j.aim.2012.06.028
Laurenţiu Leuştean, Rates of asymptotic regularity for Halpern iterations of nonexpansive mappings, J.UCS 13 (2007), no. 11, 1680–1691. MR 2390244
Felix Lieder, On the convergence rate of the Halpern-iteration, Optim. Lett. 15 (2021), no. 2, 405–418. MR 4218746, DOI 10.1007/s11590-020-01617-9
Pierre-Louis Lions, Approximation de points fixes de contractions, C. R. Acad. Sci. Paris Sér. A-B 284 (1977), no. 21, A1357–A1359 (French, with English summary). MR 470770
Genaro López, Victoria Martín-Márquez, and Hong-Kun Xu, Halpern’s iteration for nonexpansive mappings, Nonlinear analysis and optimization I. Nonlinear analysis, Contemp. Math., vol. 513, Amer. Math. Soc., Providence, RI, 2010, pp. 211–231. MR 2668248, DOI 10.1090/conm/513/10085
Genaro Lopez Acedo and Hong-Kun Xu, Iterative methods for strict pseudo-contractions in Hilbert spaces, Nonlinear Anal. 67 (2007), no. 7, 2258–2271. MR 2331876, DOI 10.1016/j.na.2006.08.036
Boris T. Polyak, Introduction to optimization, Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York, 1987. Translated from the Russian; With a foreword by Dimitri P. Bertsekas. MR 1099605
Huiqiang Qi and Hong-Kun Xu, Convergence of Halpern’s iteration method with applications in optimization, Numer. Funct. Anal. Optim. 42 (2021), no. 15, 1839–1854. MR 4396371, DOI 10.1080/01630563.2021.2001826
Simeon Reich, Approximating fixed points of nonexpansive mappings, Panamer. Math. J. 4 (1994), no. 2, 23–28. MR 1274185
Shoham Sabach and Shimrit Shtern, A first order method for solving convex bilevel optimization problems, SIAM J. Optim. 27 (2017), no. 2, 640–660. MR 3634996, DOI 10.1137/16M105592X
Robert Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B 58 (1996), no. 1, 267–288. MR 1379242, DOI 10.1111/j.2517-6161.1996.tb02080.x
Rainer Wittmann, Approximation of fixed points of nonexpansive mappings, Arch. Math. (Basel) 58 (1992), no. 5, 486–491. MR 1156581, DOI 10.1007/BF01190119
Hong-Kun Xu, Iterative algorithms for nonlinear operators, J. London Math. Soc. (2) 66 (2002), no. 1, 240–256. MR 1911872, DOI 10.1112/S0024610702003332
Hong-Kun Xu, Averaged mappings and the gradient-projection algorithm, J. Optim. Theory Appl. 150 (2011), no. 2, 360–378. MR 2818926, DOI 10.1007/s10957-011-9837-z
T. Yoon and E. K. Ryu, Accelerated algorithms for smooth convex-concave minimax problems with $\mathcal {O}(1/k^2)$ rate on squared gradient norm, Proceedings of the 38th International Conference on Machine Learning, PMLR 139, pp. 12098–12109, 2021.
Per Christian Hansen, James G. Nagy, and Dianne P. O’Leary, Deblurring images, Fundamentals of Algorithms, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006. Matrices, spectra, and filtering. MR 2271138, DOI 10.1137/1.9780898718874
Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183–202. MR 2486527, DOI 10.1137/080716542