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

Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, Bruce W. SuterMath. Program 2017 · DOI · OpenReview

In the landscape of large-scale optimization, first-order methods like gradient descent and proximal splitting are the workhorses of modern machine learning. Despite their ubiquity, a significant gap has historically existed between the theoretical "worst-case" complexity bounds and the actual performance observed in practice. This research, published in 2016, provides a rigorous theoretical bridge between error bounds—which describe the geometry of a function near its minimizers—and complexity analysis, which dictates the convergence speed of an algorithm.

By demonstrating that these two concepts are often two sides of the same coin, the authors provide a framework to derive significantly tighter convergence rates for practical convex problems, most notably proving that algorithms like ISTA achieve linear convergence for LASSO problems.

The Convergence Gap

In big-data optimization, first-order methods are preferred due to their low per-iteration computational cost. However, standard complexity analysis often yields pessimistic results. For instance, the Iterative Shrinkage-Thresholding Algorithm (ISTA), a staple in compressed sensing and sparse recovery, is traditionally cited as having an $O(1/k)$ convergence rate.

While "error bound" theory (studying how the distance to a solution set relates to the objective function value) has existed for decades, it was rarely used to systematically compute the actual complexity of an algorithm. Conversely, the Kurdyka-Łojasiewicz (KL) inequality has emerged as a powerful tool for proving convergence, but identifying the specific "desingularizing function" ($\phi$) required for KL analysis is notoriously difficult. This paper addresses this disconnect by showing how to translate easily derived error bounds into explicit complexity results via the KL framework.

Methodology: The 1D Majorant Approach

The authors introduce a systematic three-step methodology to bridge this gap:

  1. Derive an Error Bound: Leverage the geometric properties of the specific problem (e.g., Hoffman’s linear error bounds for polyhedral sets) to establish a relationship between the function value and the distance to the set of minimizers.
  2. Compute the Desingularizing Function: The authors prove that for convex functions with "moderate behavior" (covering the vast majority of practical cases), the error bound directly provides the KL desingularizing function $\phi$.
  3. The 1D Majorant Method: Inspired by Kantorovich’s majorant method for Newton’s method, the authors reduce the high-dimensional descent process to a simple one-dimensional "worst-case" proximal sequence. This 1D sequence acts as a "master" that governs the complexity of the original high-dimensional algorithm.

This approach is applied to an abstract descent scheme that encompasses forward-backward splitting, projection methods, and trust-region methods.

Key Theoretical Insights

The Equivalence Breakthrough

The paper establishes that for convex functions, possessing an error bound is essentially equivalent to satisfying a KL inequality, provided the function does not exhibit extreme flatness (such as $e^{-1/x^2}$). This equivalence simplifies the toolkit for researchers, merging two previously distinct areas of optimization theory.

Robustness of KL

Through a clever counterexample in $\mathbb{R}^2$, the authors demonstrate that for extremely flat functions, the KL inequality remains a viable tool for proving convergence even when standard error bounds fail. This reinforces the KL inequality as the more fundamental and robust tool for complexity analysis.

Linear Convergence of ISTA

A standout practical insight is the application of this theory to the LASSO problem ($\ell^1$-regularized least squares). Because the objective function is piecewise polynomial, it satisfies a specific error bound that leads to a global linear convergence rate ($O(q^k)$). This explains why ISTA frequently outperforms its theoretical $O(1/k)$ projection in real-world applications.

Results and Implications

The research culminates in several key results:

  • Universal Complexity Bound: Theorem 16 provides a general bound for descent methods: $f(x_k) - \min f \leq \psi(\alpha_k)$, where $\alpha_k$ is the 1D proxy sequence.
  • Explicit Rates for LASSO: The authors derive an explicit linear rate for $\ell^1$-regularized least squares, where the decay factor $q$ depends on the conditioning of the data matrix and the regularization parameter.
  • Feasibility Methods: The framework provides new, explicit complexity bounds for the Barycentric Projection Algorithm and the Alternating Projection Method used to find points in the intersection of convex sets.

Limitations and Future Directions

While the paper offers a powerful new framework, several challenges remain. Estimating the specific constants (such as the Hoffman constant $\nu$) for a given data matrix remains difficult, and current estimates are likely non-optimal. Furthermore, the equivalence between error bounds and KL inequalities relies heavily on convexity; extending this systematic pipeline to non-convex problems is a significant hurdle. Finally, the current abstract scheme does not yet cover "accelerated" methods (like Nesterov’s acceleration), which require different Lyapunov functions for analysis.

Summary updated

Abstract

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 ( q k ) where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with $$\ell ^1$$ ℓ 1 regularization.
BibTeX
@article{bolte2017from,
  author = {Jérôme Bolte and Trong Phong Nguyen and Juan Peypouquet and Bruce W. Suter},
  title = {{From error bounds to the complexity of first-order descent methods for convex functions}},
  journal = {Math. Program.},
  year = {2017},
  doi = {10.1007/s10107-016-1091-6},
}
Figure