Seminar Details
2019-03-26 (14:00) : Performance Estimation for Fixed Point Iterations
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Felix Lieder (Universität Düsseldorf)
Abstract :
In recent years exact worst-case performance estimation of first-order methods has gained great attention: It is now well established (especially, but not solely, due to the work of de Klerk, Drori, Glineur, Hendrickx, Taylor and Teboulle) that we can find tight convergence rates for smooth (strongly) convex functions via semidefinite programming. Here the existing approach is transferred to the broader setting of fixed point iterations of non-expansive operators, again ensuring tight rates. Specifically we focus on two fixed point iterations, first the Halpern-Iteration and second the Krasnoselski-Mann-Iteration with constant step-size. In both cases we consider the convergence of the norm of the residuals as our performance criterion of interest. We are able to improve the existing bounds on the convergence rate and, more importantly, show tightness of both bounds. In particular, while the Krasnoselski-Mann-Iteration often performs better in practice, its (tight) rate is an order of magnitude worse than of the Halpern-Iteration, which possesses the fastest proven convergence rate among all fixed step methods.
Finally we discuss applications and possible future extensions, such as different performance criteria and automated algorithm modeling.