Source-linked AI summary
Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
Guoyin Li, Ting Kei Pong
TL;DR
The paper studies how to determine KL exponents, which guide convergence-rate analysis for first-order methods. It develops exponent calculus rules and links Luo-Tseng error bounds to KL exponents, showing exponent 1/2 for many practical models and enabling local linear convergence results for selected algorithms.
Problem
KL exponents are often difficult to determine, while explicit exponents are needed to analyze convergence rates of first-order methods.
Method
The paper develops calculus rules for KL exponents and connects Luo-Tseng error bounds with KL exponent 1/2 under separated stationary values.
Results
Many convex and nonconvex application models, including SCAD- or MCP-regularized least squares and ℓ1-regularized logistic regression, have KL exponent 1/2.
Takeaways & Limitations
The results provide explicit convergence-rate consequences and support local linear convergence of proximal gradient and inertial proximal methods for selected sparse-recovery models.
Takeaways & Limitations
Future work includes deriving exponents for augmented Lagrangian potentials and least-squares models with other nonconvex regularizers.
Abstract
from arXiv · showhide
In this paper, we study the Kurdyka-Łojasiewicz (KL) exponent, an important quantity for analyzing the convergence rate of first-order methods. Specifically, we develop various calculus rules to deduce the KL exponent of new (possibly nonconvex and nonsmooth) functions formed from functions with known KL exponents. In addition, we show that the well-studied Luo-Tseng error bound together with a mild assumption on the separation of stationary values implies that the KL exponent is $\frac12$. The Luo-Tseng error bound is known to hold for a large class of concrete structured optimization problems, and thus we deduce the KL exponent of a large class of functions whose exponents were previously unknown. Building upon this and the calculus rules, we are then able to show that for many convex or nonconvex optimization models for applications such as sparse recovery, their objective function's KL exponent is $\frac12$. This includes the least squares problem with smoothly clipped absolute deviation (SCAD) regularization or minimax concave penalty (MCP) regularization and the logistic regression problem with $\ell_1$ regularization. Since many existing local convergence rate analysis for first-order methods in the nonconvex scenario relies on the KL exponent, our results enable us to obtain explicit convergence rate for various first-order methods when they are applied to a large variety of practical optimization models. Finally, we further illustrate how our results can be applied to establishing local linear convergence of the proximal gradient algorithm and the inertial proximal algorithm with constant step-sizes for some specific models that arise in sparse recovery.
1 Introduction
The paper addresses the difficulty of determining KL exponents, which are important for interpreting first-order-method convergence rates. It develops calculus rules and connects KL exponents with Luo-Tseng error bounds to analyze practical optimization models.
- The KL property relates a potential function’s value to its gradient or subgradient information and helps characterize convergence rates.
- KL exponents are difficult to determine, despite their importance for making first-order-method convergence results informative.Existing explicit estimates can be weak, especially when they grow with problem dimension.
- The paper develops calculus rules for computing KL exponents of functions formed from known KL functions, including minima, Moreau envelopes, and Lagrangian relaxations.
- An applicable Luo-Tseng error bound, together with mild separation of stationary values, implies a KL exponent of 1/2.
- The framework establishes exponent 1/2 for models including SCAD- or MCP-regularized least squares and ℓ1-regularized logistic regression.
- The results support local linear convergence analyses for proximal gradient and inertial proximal algorithms with constant step-sizes on specific sparse-recovery models.
2 Notation and preliminaries
This section introduces the notation, subdifferential and proximal mappings, Luo-Tseng error bounds, and the KL property and exponent used in the paper.
- The paper works in R^n with the standard inner product and induced norm, and defines distances, projections, relative interiors, indicators, and ℓ1 and ℓ0 norms.
- The limiting subdifferential generalizes gradients and classical convex subdifferentials, supporting nonsmooth and nonconvex optimization analysis.
- For f = h + P, stationary points are characterized by the proximal relation x̄ = prox_P(x̄ − ∇h(x̄)).
- The Luo-Tseng error bound is a first-order error bound for specially structured functions and has been used to establish local linear convergence of first-order methods.
- A KL function satisfies the KL property at every point in the domain of its subdifferential, with the exponent specifying a power-form desingularizing function.
- If a proper closed function has a nonzero subdifferential distance from zero at a point, it satisfies the KL property there with any exponent in [0, 1).
3 Calculus of the KL exponent
This section develops calculus rules for transferring KL exponents through operations including minima, compositions, separable sums, Moreau envelopes, Lagrangian relaxations, potential functions, and active-manifold restrictions.
- Applications: These rules are intended for concrete convex and nonconvex optimization models whose KL exponents can then be deduced from known component exponents.The paper explicitly uses the calculus rules in later sections to analyze application-oriented optimization models.
- Other operations: The calculus results also cover Moreau envelopes, convex Lagrangian relaxations, inertial-proximal potential functions, and partly smooth functions restricted to active manifolds.The stated results include an exponent rule for the Moreau envelope, deduction from Lagrangian relaxation, an iPiano potential, and verification along an active manifold.
- Minimum: The KL exponent of the minimum of finitely many KL functions is the maximum exponent among the active functions.Under continuity and proper-closedness assumptions, if f = min_i f_i, then its local exponent at x̄ is max{α_i : i ∈ I(x̄)}.
- Composition: A smooth composition g(F(x)) preserves g’s KL exponent when F is continuously differentiable and its Jacobian at the reference point is surjective.Theorem 3.2 assumes g has exponent α and JF(x̄) is surjective, yielding exponent α for the composition.
- Separable sums: A block-separable sum inherits the maximum KL exponent of its component functions under continuity and proper-closedness assumptions.For f(x)=Σ_i f_i(x_i), the resulting exponent is max{α_i : 1 ≤ i ≤ m}.
- Moreau envelope: For a proper closed convex KL function, the Moreau envelope has an exponent given by the theorem’s transformed expression involving the original exponent.The theorem states that F_λ is a KL function with exponent max{1/2, ...}; the supplied passage truncates the expression after this point.
4 Structured problems: Luo-Tseng error bound and KL property
The section connects the Luo-Tseng error bound and stationary-value separation to KL exponent 1/2, then applies this connection to structured convex models.
- The Luo-Tseng error bound is used to establish local linear convergence for various first-order methods on structured objectives.
- The section develops an auxiliary lemma for proper closed objectives f = h + P, with h smooth on an open domain and P proper closed convex.
- Under Assumption 4.1 and the Luo-Tseng error bound, f is a KL function with exponent 1/2.Assumption 4.1 requires nearby stationary points to have the same function value.
- Convex problems with convex piecewise linear-quadratic regularizers have KL exponent 1/2 when their argmin set is nonempty and compact.
- A second convex model also has KL exponent 1/2 when its infimum is strictly greater than the infimum of its loss term.
5 Applications
The paper applies its calculus rules and Luo-Tseng connection to piecewise and nonconvex regularized models, obtaining KL exponent 1/2 results and local linear convergence guarantees.
- The applications section deduces KL exponents for concrete optimization models and uses them to establish linear convergence of first-order methods.
- Piecewise linear regularizers: Under stated smoothness and polyhedral-regularizer conditions, the functions f_i(x) = l(Ax) + P_i(x) are KL functions with exponent 1/2.
- Piecewise linear regularizers: Many sparse-recovery regularizers represented as minima of finitely many proper closed polyhedral functions yield objectives with KL exponent 1/2.
- Nonconvex regularizers: Least-squares objectives with SCAD or MCP regularizers have KL exponent 1/2 under continuity on dom ∂f.
- Local linear convergence: The proximal gradient method and iPiano are shown to have local linear convergence for several concrete models, including ℓ1-regularized logistic regression.
- Local linear convergence: For coercive objectives with convex piecewise linear-quadratic regularizers, iPiano has guaranteed local linear convergence under the stated model conditions.
6 Concluding remarks
The paper concludes that its KL-exponent calculus and Luo-Tseng connection cover many practical convex and nonconvex models and support local linear convergence analysis.
- Many practical convex or nonconvex optimization models are shown to have KL exponent 1/2.
- The results are applied to establishing local linear convergence of some first-order methods.
- Future work includes deriving exponents for augmented Lagrangians in nonconvex ADMM analysis and for additional nonconvex regularizers.
A An auxiliary lemma
The appendix proves an auxiliary result for objectives combining a smooth proper closed term with a proper closed polyhedral function, using piecewise linearity and strong convexity.
- The appendix proves a version of an existing lemma for f = ℓ + P, where ℓ has an open domain and P is proper closed polyhedral.
- The epigraph set K is introduced as K := {(x, s) : s ≥ P(x)} for the auxiliary construction.
- A lemma establishes a constant C for every x in dom f, with the proof using proximal mapping, projection, and strong convexity.
- Because P is polyhedral and piecewise linear, it is Lipschitz continuous on its domain, yielding bounds involving M∥w − x∥.