Convergence analysis under consistent error bounds

Abstract

We introduce the notion of consistent error bound functions which provides a unifying framework for error bounds for multiple convex sets. This framework goes beyond the classical Lipschitzian and Hölderian error bounds and includes logarithmic and entropic error bounds found in the exponential cone. It also includes the error bounds obtainable under the theory of amenable cones. Our main result is that the convergence rate of several projection algorithms for feasibility problems can be expressed explicitly in terms of the underlying consistent error bound function. Another feature is the usage of Karamata theory and functions of regular variations which allows us to reason about convergence rates while bypassing certain complicated expressions. Finally, applications to conic feasibility problems are given and we show that a number of algorithms have convergence rates depending explicitly on the singularity degree of the problem.

arXiv comment43 pages, comments welcome. To appear in Foundations of Computational Mathematics

References in corpus (6)

• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity
• Extended Formulations in Mixed-integer Convex Programming
• Amenable cones: error bounds without constraint qualifications
• Facial Reduction and Partial Polyhedrality

Cited by in corpus (4)

• Error bounds, facial residual functions and applications to the exponential cone
• A successive centralized circumcenter reflection method for the convex feasibility problem
• Eigenvalue programming beyond matrices
• Concrete convergence rates for common fixed point problems under Karamata regularity