PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jérôme Bolte, Trong Phong Nguyen, Juan Peypouquet, Bruce Suter

arXiv:1510.08234v3math.OC

TL;DR

The paper asks how error bounds can support complexity analysis for first-order descent methods in convex minimization. It establishes their connection to KL inequalities and uses a one-dimensional worst-case proximal sequence to obtain complexity bounds, including O(q^k) for ISTA, while noting limitations in error-bound constants and conditioning.

  • Problem

    Existing theory did not provide a solid connection between the paper’s error bounds and complexity analyses for general first-order descent methods.

  • Method

    The paper converts error bounds into KL desingularizing functions and analyzes descent methods through a one-dimensional worst-case proximal sequence.

  • Results

    The approach yields complexity results for projection methods and ISTA, including an O(q^k) bound for least-squares objectives with ℓ1 regularization.

  • Takeaways & Limitations

    The paper provides a systematic workflow linking tractable error bounds to complexity estimates for convex first-order descent methods.

  • Takeaways & Limitations

    The estimate of γ_R is far from optimal, and complexity is sensitive to conditioning because a small γ_R produces worse bounds.

Abstract

from arXiv · show

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 methodology: 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})$ where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with $\ell^1$ regularization.

1 Overview and main results

The paper connects error bounds and KL inequalities for convex functions, then uses KL-based desingularization and a one-dimensional worst-case proximal sequence to derive complexity results for first-order descent methods.

  • The paper addresses the limited theory connecting error bounds with complexity analyses for general first-order descent methods.
  • For convex functions with moderately behaving residual functions, error bounds are equivalent to nonsmooth KL inequalities, including power-type examples.
  • The proposed complexity analysis associates a one-dimensional worst-case proximal method with the original descent method under weak assumptions.
  • The methodology derives an error bound, computes a desingularizing function, identifies essential method constants, and evaluates complexity through the worst-case proximal sequence.
  • For ISTA on least-squares objectives with ℓ1 regularization, the complexity has the form O(q^k), with q ∈ (0, 1).
  • The paper also studies globalization of convex KL inequalities and shows that extremely flat error bounds can break the error-bound/KL equivalence.

2 Preliminaries

The preliminaries define the convex-analytic setting, subdifferential and proximity operators, subgradient curves, KL inequalities, and local-to-global error-bound results for convex functions.

  • The analysis considers proper lower-semicontinuous convex functions on a real Hilbert space that attain their minimum.
  • 2.1 Some convex analysis: The subdifferential collects vectors satisfying the convex supporting inequality, and minimizers are characterized by 0 belonging to the subdifferential.
  • 2.1 Some convex analysis: The least-norm subgradient has norm equal to the distance from zero to the subdifferential, with an infinite value assigned outside the subdifferential domain.
  • 2.1 Some convex analysis: The proximity operator is the unique minimizer of a regularized objective, is characterized by a subdifferential inclusion, and is 1-Lipschitz; for indicator functions, it becomes projection onto the set.
  • 2.2 Subgradient curves: Subgradient curves are absolutely continuous trajectories generated by the differential inclusion ẏ(t) ∈ −∂f(y(t)).
  • 2.3 KL inequalities: A KL inequality uses a concave increasing desingularizing function to reparameterize function values near a point, and semi-algebraic convex functions have the KL property around every domain point.
  • 2.4 Error bounds: With coercivity, semi-algebraic convex functions admit global error bounds, while convexity extends local bounds beyond the initial sublevel set by linear extrapolation.

3 Error bounds with moderate growth are equivalent to Lojasiewicz inequalities

The paper characterizes when convex error bounds and Lojasiewicz/KL inequalities are equivalent, with moderate residual growth as the key condition. It then applies this relationship to obtain explicit desingularizing functions and error bounds for several convex function classes, including piecewise-polynomial and ℓ1-regularized least-squares objectives.

  • Moderate residual growth: Semi-algebraic or subanalytic desingularizing functions automatically have moderate behavior.The paper introduces moderate behavior through a differential condition and notes that the Puiseux lemma establishes it for these function classes.
  • Equivalence results: Global equivalence also holds when the desingularizing function has moderate behavior near the origin.The KL desingularizing function and error-bound residual are essentially identical up to a multiplicative constant; the equivalence can fail for extremely flat functions.
  • Equivalence results: Theorem 5 gives reciprocal local implications between KL inequalities and error bounds for convex functions.A KL inequality yields dist(x, S) ≤ ϕ(f(x)); conversely, an error bound yields a KL inequality after rescaling under moderate behavior.
  • Methodology: The practical procedure is to derive an error bound, compute its desingularizing function, and retain the relevant constants and domain.The paper uses convexity together with Theorem 5 or Corollary 6 to perform this conversion.
  • Applications: For piecewise-polynomial convex functions, the Lojasiewicz exponent is θ = 1 − 1/((deg(f) − 1)n + 1).The result applies on bounded sublevel sets and provides a computable exponent based on the function degree and dimension.
  • Applications: For least squares with ℓ1 regularization, an error bound on an ℓ1 ball yields a KL desingularizing function ϕ(s) = 2γ_R^-1√s.The bound f(x) − f(x∗) ≥ 2γ_R dist²(x, S) holds when ∥x∥1 ≤ R.

4 Complexity for first-order methods with sufficient decrease condition

The paper analyzes convex first-order descent sequences satisfying sufficient decrease and relative error conditions, covering methods such as forward-backward splitting. Its main complexity result reduces the analysis to a one-dimensional worst-case proximal sequence and establishes convergence and rate regimes under KL assumptions.

  • 4.1 Subgradient sequences: The abstract descent framework uses sufficient decrease and relative error conditions for convex objectives.The framework is designed to cover subgradient descent sequences generated by forward-backward, trust-region, alternating, sequential quadratic, and majorization-minimization methods.
  • 4.1 Subgradient sequences: Forward-backward splitting satisfies the framework when its step sizes obey 0 < λ− ≤ λk ≤ λ+ < 2/L.The method includes proximal point and explicit gradient methods as special cases when one component vanishes.
  • 4.1 Subgradient sequences: Under a convex KL property, every subgradient descent sequence converges strongly to a minimizer.Theorem 14 establishes this result in a Hilbert space and provides an associated complexity estimate.
  • 4.2 Complexity for subgradient descent sequences: The paper identifies the desingularizing function, rather than the square root, as the likely source of worst-case complexity.For twice continuously differentiable definable functions, the desingularizing function satisfies ϕ(s) ≥ O(√s) near the origin.
  • 4.2 Complexity for subgradient descent sequences: Theorem 16 uses a one-dimensional worst-case proximal sequence as a Kantorovich-style majorizing sequence for the original descent sequence.The construction gives both strong convergence of the original iterates and complexity control through the scalar sequence.
  • 4.2 Complexity for subgradient descent sequences: KL geometry can produce two complexity regimes when ψ is nonlinear near zero and affine beyond a threshold.Entering the nonlinear region [0, t0] yields a slower and more restrictive regime.
  • 4.2 Complexity for subgradient descent sequences: The sequence-level complexity result remains valid with a continuum of minimizers.Restricting the KL domain to a stable set can improve the desingularizing function and potentially tighten bounds, but maintaining stability is generally difficult.

5 Applications: feasibility problems, uniformly convex problems and compressed sensing

The paper applies its error-bound/KL methodology to convex feasibility, uniformly convex problems, and ℓ1-regularized least squares, deriving complexity results for projection methods and ISTA.

  • Application methodology: The applications use a workflow that derives an error bound, computes a desingularizing function, identifies method constants, and evaluates a one-dimensional worst-case proximal sequence.This methodology is applied to feasibility problems, uniformly convex problems, and compressed sensing.
  • Convex feasibility problems: The barycentric projection sequence converges strongly to a point in the feasible intersection for regular intersections.
  • Convex feasibility problems: The alternating projection sequence converges to a point in the intersection, with iterates remaining in C1 after the first step.
  • Uniformly convex problems: For uniformly convex functions, the complexity is explicit in the quadratic case p = 2 but generally requires numerical estimates.
  • Compressed sensing and ISTA: ISTA is forward-backward splitting for ℓ1-regularized least squares, and the paper derives complexity bounds governed by error-bound constants and conditioning.The method uses soft thresholding and admissible stepsizes satisfying 0 < λ− ≤ λk ≤ λ+ < 2/L.
  • Compressed sensing and ISTA: For constant stepsize d/L, the optimized estimate is obtained at d = 1/2, while the conditioning constant γR is crucial to the complexity bound.

6 Error bounds and KL inequalities for convex functions: additional properties

The paper establishes additional convex-function results linking KL inequalities, subgradient trajectories, and global desingularizing functions, while exhibiting limits of the error-bound/KL connection.

  • KL and subgradient curves: KL inequalities are equivalent to uniform bounds on subgradient-trajectory lengths under the stated convex assumptions, and the trajectories converge strongly to minimizers.
  • Counterexample: A C2 convex function can have a smooth convex error bound without satisfying the KL inequality, showing that error bounds do not always imply KL.
  • Counterexample: For nonconvex functions, Hölderian error bounds likewise need not imply the Łojasiewicz or KL inequalities.
  • Counterexample: The counterexample has a positive sequence converging to zero where f′ vanishes, preventing the KL inequality at zero.
  • Globalization: A local KL inequality for a convex function can be extended globally by continuing its desingularizing function linearly beyond a chosen level r1.
  • Globalization: Every proper lower-semicontinuous definable convex function on Rn with nonempty compact minimizer set has a global KL property and a corresponding global complexity measure.

7 Conclusions

The paper presents error bounds and KL inequalities as a general route to complexity estimates for first-order methods, illustrated on projection algorithms and ISTA.

  • The proposed methodology converts error bounds into desingularizing functions and then into complexity estimates for common convex descent methods.
  • The method yields new complexity results for ISTA in compressed sensing and for barycentric and alternating projection methods in convex feasibility.
  • The authors identify complementary connections with concurrent work on error bounds for parametric polynomial systems and first-order convergence rates.
Loading 1510.08234v3…