From error bounds to the complexity of first-order descent methods for convex functions

By Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, Bruce Wilsey Suter. 2015

391 citations recorded by the source corpus.

This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-Łojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Hölderian growth). A counterexample shows that the equivalence is no longer true for extremely flat functions. This fact reveals the relevance of an approach based on KL inequality. In a second stage, we show how KL inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence in the spirit of the famous majorant method of Kantorovich. Our result applies to a very simple abstract scheme that covers a wide class of descent methods. As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple method: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form $$O(q^{k})$$O(qk) where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with $$\ell ^1$$ℓ1 regularization.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “The equivalence of the KL condition and the proximal-gradient variant of the Luo-Tseng EB condition is known for convex f , see [Drusvyatskiy and Lewis, 2016, Corollary 3.6] and the proof of [Bolte et al., 2015, Theorem 5].”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, background): “For example, when functions are semi-algebraic and “regular” (for instance, continuous), the above inequality is known to hold on any compact set (c.f. (Bolte et al., 2017) and references therein).”
Boosting Frank-Wolfe by Chasing Gradients (2020, background): “See also the Kurdyka-Łojasiewicz inequality (Kurdyka, 1998; Łojasiewicz, 1963) for a generalization to nonsmooth optimization (Bolte et al., 2017).”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, background): “We note that the error bound condition in (11) is well-studied in the optimization literature (see (Pang, 1997; Bolte et al., 2017; Roulet and d’Aspremont, 2020) and the references therein) and is known to hold generally when the function g is analytic and the set Z is bounded (Łojasiewicz, 1959;…”
The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth (2015, background): “At the time of writing this paper, the authors of [4] showed the equivalence between the error bound (corresponding to our growth property) and the Kurdyka-Lojasiewicz inequality for convex functions having a moderately ﬂat proﬁle near the set of minimizers.”
SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm (2016, background): “This deep, difficult to characterize property is related to the Hoffman bound [18], the linear regularity assumption, and the KurdykaLojasiewicz property [7].”
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods (2016, methodology): “There have been a number of closely related works that appeared on arXiv shortly before or concurrently with the initial version of this manuscript, notably [8, 30, 39, 54, 55].”
Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity (2017, methodology): “We refer to [BNPS16] for the following function that do not satisfy the KL inequality for any r ≥ 2: Strongly convex situation.”