Concrete convergence rates for common fixed point problems under Karamata regularity
<|reference_start|>Concrete convergence rates for common fixed point problems under Karamata regularity: 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\"olderian error bounds and H\"older 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\"olderian-like assumptions many algorithms converge linearly/sublinearly (depending on the exponent), little it is known when the underlying problem data does not satisfy H\"olderian 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\"olderian 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 definable operators in any o-minimal structure are always Karamata regular.<|reference_end|>
@article{liu2024concrete,
    title={Concrete convergence rates for common fixed point problems under
  Karamata regularity},
    author={Tianxiang Liu and Bruno F. Lourenc{c}o},
    journal={arXiv preprint arXiv:2407.13234},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.13234},
    primaryClass={math.OC cs.NA math.FA math.MG math.NA}
}