Convergence Rates for Krasnoselskii-Mann Fixed-Point Iterations

Abstract: A popular method to approximate a fixed point of a non-expansive map $T : C \to C$ is the Krasnoselskii-Mann iteration

$$(KM)\ \ \ \hspace{3cm} x_{n+1} = (1 − \alpha_{n+1}) x_n + \alpha_{n+1} T xn.$$

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 yields the following tight metric estimate for the fixed-point residuals

$$x_n – T x_n = \frac{diam (C)}{\pi \sum_(k=1)^n \alpha_k (1-\alpha_k)}.$$

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.

Note: The talk will be based on joint work with Mario Bravo, Matías Pavez-Signé, José Soto, and José Vaisman. Papers are available at sites.google.com/site/cominettiroberto/.

optimization and control

Audience: advanced learners

Comments: The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk.

---

One World Optimization seminar

Series comments: Description: Online seminar on optimization and related areas

The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk

---