Abstract
Halpern iteration is a classical iteration developed by Benjamin Halpern in 1967 as a method for solving fixed point operator equations. Over the past decades, the convergence of Halpern iteration has been studied in both asymptotic and nonasymptotic terms. However, its study was predominantly confined to operator equations. This trend changed a few years ago, when the connection between fixed point equations and monotone inclusion problems was utilized in my work to show that Halpern iteration leads to either optimal or near-optimal convergence guarantees for essentially all standard classes of problems with Lipschitz operators. The setting of monotone inclusion---which corresponds to finding (or approximating) a zero of a monotone operator---is of particular relevance here, as it generalizes variational inequality (equilibria) problems and provides guarantees in terms of both optimality gap and stationarity (norm of the gradient in unconstrained settings) in min-max optimization.
I will discuss recent developments related to the use of Halpern iteration, including in settings where the operator is possibly non-monotone and can be accessed only via stochastic queries. To date, the guarantees that can be obtained with variants of Halpern iteration remain unmatched by any alternative algorithms and are all provided for the last iterate.