Concrete convergence rates for common fixed point problems under Karamata regularity

Abstract

We introduce the notion of Karamata regular operators, which is a notion of regularity that is suitable for obtaining concrete convergence rates for common fixed point problems. This provides a broad framework that includes, but goes beyond, Hölderian error bounds and Hölder regular operators. By concrete, we mean that the rates we obtain are explicitly expressed in terms of a function of the iteration number $k$ instead, of say, a function of the iterate $x^k$. While it is well-known that under Hölderian-like assumptions many algorithms converge linearly/sublinearly (depending on the exponent), little it is known when the underlying problem data does not satisfy Hölderian assumptions, which may happen if a problem involves exponentials and logarithms. Our main innovation is the usage of the theory of regularly varying functions which we showcase by obtaining concrete convergence rates for quasi-cylic algorithms in non-Hölderian settings. This includes certain rates that are neither sublinear nor linear but sit somewhere in-between, including a case where the rate is expressed via the Lambert W function. Finally, we connect our discussion to o-minimal geometry and show that, under mild assumptions, definable operators in any o-minimal structure are always Karamata regular.

arXiv comment52 pages. Minor fixes. To appear in Mathematical Programming

References in corpus (6)

• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Quantitative convergence analysis of iterated expansive, set-valued mappings
• Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity
• Error bounds, facial residual functions and applications to the exponential cone
• Convergence analysis under consistent error bounds
• Łojasiewicz-type inequalities and global error bounds for nonsmooth definable functions in o-minimal structures