Kurdyka-Łojasiewicz-based convergence analysis with approximate weakly convex subdifferentials: bundle, quadratic penalty, and moving balls approximation methods
Abstract
The Kurdyka-Lojasiewicz (KL) property has been widely used for establishing global sequential convergence and analyzing local convergence rate of optimization algorithms. Most existing analysis frameworks rely on the construction of a suitable KL potential function such that along the sequence generated, it admits sufficient descents and its exact subdifferentials are suitably controlled by successive changes of the iterates. Nevertheless, a handful of important algorithms, such as bundle methods and quadratic penalty methods, are not known to have potential functions verifying the aforementioned properties, rendering their convergence analysis out of the reach of existing KL-based convergence analysis template. In this paper, we develop a new convergence analysis framework to extend the applicability of KL-based analysis. Our framework is built on a weakly convex KL potential function ψ. It allows approximate sufficient descents, the use of diminishing stepsizes, and controls on enlarged subdifferentials of ψ known as the ϱ-weakly-convex-ε-subdifferentials. We illustrate the usefulness of our framework by establishing the global sequential convergence and analyzing the local convergence rate of some recent variants of bundle method, quadratic penalty method and moving balls approximation method. Specifically, we show that these methods fall under our framework by presenting explicit and natural choices of ψ, and derive suitable choices of model parameters, penalty parameters and constraint shrinkage parameters, respectively, for establishing their global sequential convergence and local convergence rate based on the KL property and exponent of ψ.
Related
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Whole-Sequence Convergence of Variable-Smoothing Full-Splitting Methods via a Lifted Kurdyka-Łojasiewicz Framework
- Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing
- Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
- Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs
BibTeX
@misc{xu2026kurdykałojasiewiczbased,
title = {{Kurdyka-Łojasiewicz-based convergence analysis with approximate weakly convex subdifferentials: bundle, quadratic penalty, and moving balls approximation methods}},
author = {Jiefeng Xu and Guoyin Li and Ting Kei Pong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26263},
eprint = {2610.26263},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26263},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Kurdyka-Łojasiewicz-based convergence analysis with approximate weakly convex subdifferentials: bundle, quadratic penalty, and moving balls approximation methods
AU - Jiefeng Xu
AU - Guoyin Li
AU - Ting Kei Pong
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.26263
UR - https://arxiv.org/abs/2610.26263
AB - The Kurdyka-Lojasiewicz (KL) property has been widely used for establishing global sequential convergence and analyzing local convergence rate of optimization algorithms. Most existing analysis frameworks rely on the construction of a suitable KL potential function such that along the sequence generated, it admits sufficient descents and its exact subdifferentials are suitably controlled by successive changes of the iterates. Nevertheless, a handful of important algorithms, such as bundle methods and quadratic penalty methods, are not known to have potential functions verifying the aforementioned properties, rendering their convergence analysis out of the reach of existing KL-based convergence analysis template. In this paper, we develop a new convergence analysis framework to extend the applicability of KL-based analysis. Our framework is built on a weakly convex KL potential function ψ. It allows approximate sufficient descents, the use of diminishing stepsizes, and controls on enlarged subdifferentials of ψ known as the ϱ-weakly-convex-ε-subdifferentials. We illustrate the usefulness of our framework by establishing the global sequential convergence and analyzing the local convergence rate of some recent variants of bundle method, quadratic penalty method and moving balls approximation method. Specifically, we show that these methods fall under our framework by presenting explicit and natural choices of ψ, and derive suitable choices of model parameters, penalty parameters and constraint shrinkage parameters, respectively, for establishing their global sequential convergence and local convergence rate based on the KL property and exponent of ψ.
ER -