Department of Mathematics Calendar
Roberto Cominetti, Universidad Adolfo Ibáñez, Chile, Convergence rates for Krasnoselskii-Mann fixed-point iterations
A popular method to approximate a fixed point of a non-expansive map is C is the Krasnoselskii-Mann iteration. This covers a wide range of iterative methods in convex minimization, equilibria, and beyond. In the Euclidean setting, a flexible method to obtain convergence rates for this iteration is the PEP methodology introduced by Drori and Teboulle (2012), which is based on semi-definite programming. When the underlying norm is no longer Hilbert, PEP can be substituted by an approach based on recursive estimates obtained by using optimal transport. This approach can be traced back to early work by Baillon and Bruck (1992, 1996). In this talk we describe this optimal transport technique, and we survey some recent progress that settles two conjectures by Baillon and Bruck, and yield the following tight metric estimate for the fixed-point residuals.
The recursive estimates exhibit a very rich structure and induce a very peculiar metric over the integers. The analysis exploits an unexpected connection with discrete probability and combinatorics, related to the Gambler’s ruin for sums of non homogeneous Bernoulli trials. If time allows, we will briefly discuss the extension to inexact iterations, and a connection to Markov chains with rewards.
The talk will be based on joint work with Mario Bravo, Matias Pavez-Signé, José Soto, and José Vaisman.
Zoom meeting: Link