Source-linked AI summary
Splitting methods with variable metric for KL functions
Pierre Frankel, Guillaume Garrigos, Juan Peypouquet
TL;DR
The paper studies convergence of nonsmooth, nonconvex descent methods governed by the Kurdyka–Łojasiewicz inequality. It develops an abstract inexact and variable-metric framework, then applies it to alternating Forward–Backward and Newton-like methods, obtaining convergence results and general rates.
Problem
Existing descent methods have limited parameter flexibility, while their convergence rates appear to depend mainly on the Kurdyka–Łojasiewicz inequality rather than algorithmic structure.
Method
The paper develops an abstract inexact descent method with variable metrics, then analyzes variable-metric Alternating Forward–Backward and generalized Newton-like methods.
Results
The framework proves strong convergence to critical points with finite-length trajectories and derives general convergence rates for values and iterates.
Takeaways & Limitations
The unified Kurdyka–Łojasiewicz analysis applies to various descent algorithms and supports a novel projected Newton-like method.
Takeaways & Limitations
Applying the approach to an infinite-dimensional sparse-control functional remains challenging because the Kurdyka–Łojasiewicz inequality has not been established there.
Abstract
from arXiv · showhide
We study the convergence of general abstract descent methods applied to a lower semicontinuous nonconvex function f that satisfies the Kurdyka-Lojasiewicz inequality in a Hilbert space. We prove that any precompact sequence converges to a critical point of f and obtain new convergence rates both for the values and the iterates. The analysis covers alternating versions of the forward-backward method with variable metric and relative errors. As an example, a nonsmooth and nonconvex version of the Levenberg-Marquardt algorithm is detailled.
1. Introduction
The paper develops an abstract convergence-rate framework for nonsmooth, nonconvex descent methods under the Kurdyka–Łojasiewicz inequality, extending it to errors and flexible parameters. It applies this framework to variable-metric alternating Forward–Backward methods and related Newton-like algorithms.
- The analysis targets critical-point methods for nonsmooth, nonconvex functions on Hilbert spaces using the Kurdyka–Łojasiewicz inequality.
- Existing descent methods commonly require compactness, bounded step sizes or metric eigenvalues, and converge strongly with finite-length trajectories.
- Convergence rates for several methods depend primarily on the Kurdyka–Łojasiewicz inequality rather than the specific algorithm.
- The paper introduces an inexact abstract descent method allowing additive computational errors and more flexible parameter choices.
- The framework derives general convergence rates for values and iterates, with finite-iteration termination occurring in several cases.
- Applications include inexact variable-metric Alternating Forward–Backward methods, generalized Levenberg–Marquardt algorithms, and sparse low-rank matrix decomposition.
2. Preliminaries
The preliminaries define the Hilbert-space setting, subdifferential-based criticality, the Kurdyka–Łojasiewicz property, variable metrics, and metric proximal operators. These concepts support convergence analysis for lower-semicontinuous nonsmooth functions.
- The paper works in a real Hilbert space and distinguishes strong, weak, f-, precompact, and f-precompact convergence for sequences.
- The limiting Fréchet subdifferential is defined through f-convergent points and weakly convergent Fréchet-subgradient sequences.
- A critical point satisfies 0 ∈ ∂f(x), while the lazy slope measures the smallest norm of an element of the subdifferential.
- A Kurdyka–Łojasiewicz function has the stated property at every point in the domain of its subdifferential.
- The growth of the desingularizing function directly affects optimization convergence rates by reparameterizing function values near critical points.
- A positive self-adjoint uniformly elliptic operator induces the variable metric and its associated norm on the Hilbert space.
- The metric proximal operator is set-valued in general and becomes nearest-point mapping in the operator-induced metric for indicator functions.
3. Convergence of an abstract inexact descent method
The paper develops an abstract inexact descent framework for KL functions, proving convergence, finite trajectory length, capture properties, and convergence-rate results under stated hypotheses. The framework accommodates computational errors and variable parameters, and supports sharper finite-time conclusions for certain gradient-related methods.
- Algorithmic scope: The framework is complemented by implementable examples, including gradient-related methods and alternating Forward-Backward schemes with inexact iterates and dynamically chosen metrics.The practical setting also includes a generalized Levenberg-Marquardt method.
- Abstract descent framework: Under H1, H2, and H3, an f-precompact sequence generated for a KL function converges strongly to a critical point, with finite-length piecewise-linear interpolation.The framework is stated for proper strongly lower-semicontinuous functions and includes sufficient decrease and parameter conditions.
- Abstract descent framework: The abstract inexact descent method extends earlier settings to additive computational errors and more flexible parameter choices, while proving strong convergence, finite length, and a capture property.The capture result can remove the f-precompactness assumption near a global minimum under suitable initialization conditions.
- Sharper gradient-related rates: A modified hypothesis H′2 gives sharper rate estimates for certain explicit schemes, including gradient-related methods, with finite-step convergence when the associated primitive has a finite limit at zero.Theorem 5 states this finite-step conclusion under m := inf_k a_k b_k+1 > 0.
4. Descent methods with errors and variable metric
The paper extends abstract descent analysis to variable metrics, relative errors, and alternating forward-backward schemes, establishing convergence of precompact iterates to critical points under KL assumptions. It also develops a Hessian-informed variable metric method related to generalized Levenberg-Marquardt algorithms.
- Variable metric: Variable-metric forward-backward methods allow changing metrics, including vanishing step sizes and unbounded metric eigenvalues.The framework is designed to accommodate broader parameter choices than earlier treatments.
- Alternating forward-backward: Alternating forward-backward methods exploit both nonsmooth separability and the smooth structure of the coupling term while updating variables cyclically.The method extends alternating schemes through variable metrics and inexact computation.
- Errors: Relative errors model inexact computation of explicit gradient steps and proximal updates through error sequences.The resulting convergence analysis is stated for the method with errors.
- Convergence: The framework links computational and theoretical sequences, showing shared limit points and equivalent precompactness under the stated lower-boundedness condition.Finite length transfers from the auxiliary sequence to the actual iterates.
- Convergence: Under KL, parameter, error, and precompactness conditions, the AFB iterates have finite length and converge to a critical point.The result also covers cases where step sizes can tend to zero or the nonsmooth terms need not be continuous on their domains.
- Generalized Newton methods: A positive-definite metric approximating the Hessian yields a nonsmooth nonconvex Levenberg-Marquardt-type method whose iterates converge strongly to critical points.The method remains within the abstract convergence framework, while interpolation has finite length and strong convergence extends a convex-setting result.
5. Applications
The paper applies its KL-based framework to structured nonconvex problems, including sparse and low-rank matrix decomposition, using alternating projections suited to separated variables.
- Image-processing and data-compression problems are generally semi-algebraic and can involve the counting norm with an easily implementable hard-shrinkage proximal operator.The counting norm is defined as the number of nonzero coefficients.
- Sparse and low-rank matrix decomposition: Sparse and low-rank matrix decomposition seeks X and Y satisfying A = X + Y, rank(X) ≤ r, and ∥Y∥0 ≤ s.
- Sparse and low-rank matrix decomposition: The KL framework provides convergent numerical methods for the original nonconvex semialgebraic decomposition problem.
- Sparse and low-rank matrix decomposition: The alternating forward-backward method updates X and Y through projections onto rank and sparsity constraint sets.Rank projection uses the singular value decomposition, while sparsity projection retains the s largest-magnitude coefficients.
- Sparse and low-rank matrix decomposition: Using the relevant smooth-term constant gives L = 1, whereas the gradient Lipschitz constant would give L = 2 and a smaller parameter upper bound.
6. Concluding Remarks
The paper unifies several descent algorithms under the KL framework and derives general convergence rates, while identifying extensions beyond its sufficient-decrease setting.
- The paper gives a unified treatment of recent descent algorithms and derives general convergence-rate results in the KL framework.
- The framework is intended to apply to potential future numerical methods.
- The paper explores improvements and proposes a novel projected Newton-like method.
- Extending the analysis to algorithms without sufficient decrease condition H1 remains challenging, including acceleration schemes and primal-dual methods.
- An infinite-dimensional counting-norm extension is proposed as an application direction, but verifying its KL inequality has not been established.
- The Section 3 results also remain valid in the more general setting of a normed space after adapting the subdifferential and lazy slope.
A.1. Proofs of Theorems 1 and 2.
The proofs establish capture, convergence, and finite length for the abstract descent sequence by combining the stated hypotheses with KL-based arguments and lower semicontinuity.
- Under H1, H2, H3, and the stability property S(x∗, δ, ρ), Proposition 5 provides the basic asymptotic properties of the sequence.
- The proof uses capture, convergence, and finite length from Lemma 3 and H3, together with summability and subgradient estimates.
- The objective values decrease and converge to f(x∗), with lower semicontinuity supplying the needed comparison at the limit.
- The KL inequality rules out a limiting value strictly above f(x∗) because it would contradict the vanishing lower limit of the subgradient norm.
- The convergence proof is localized in a strict upper level set where the KL inequality holds, and initialization is required sufficiently close to the target point.
A.2. Proof of Proposition 1.
The proof of Proposition 1 verifies the abstract descent hypotheses for an alternating forward-backward construction using proximal updates, descent estimates, error bounds, and parameter conditions.
- The alternating scheme is rewritten in a form suitable for verifying the abstract method’s hypotheses.
- H1 is established by expanding proximal definitions, applying the descent lemma, and combining the resulting inequalities across variables.
- Coercivity is retained when ραk > L, enabling the estimates based on Cauchy-Schwarz, Lipschitz continuity, and the error hypotheses.
- H2 follows from Fermat’s first-order condition applied to each proximal subproblem.
- The proof uses the error estimates and pL-Lipschitz continuity of the partial gradients to control the inexact updates.
- The remaining H3 conditions are checked from the assumed bounds, nonsummability, and summability requirements on αk, βk, and µk.