Please use this identifier to cite or link to this item:
PIRA download icon_1.1View/Download Full Text
Title: Kurdyka-Lojasiewicz exponent via inf-projection
Authors: Yu, P
Li, G
Pong, TK 
Issue Date: Aug-2022
Source: Foundations of computational mathematics, Aug. 2022, v. 22, no. 4, p. 1171-1217
Abstract: Kurdyka–Łojasiewicz (KL) exponent plays an important role in estimating the convergence rate of many contemporary first-order methods. In particular, a KL exponent of 12 for a suitable potential function is related to local linear convergence. Nevertheless, KL exponent is in general extremely hard to estimate. In this paper, we show under mild assumptions that KL exponent is preserved via inf-projection. Inf-projection is a fundamental operation that is ubiquitous when reformulating optimization problems via the lift-and-project approach. By studying its operation on KL exponent, we show that the KL exponent is 12 for several important convex optimization models, including some semidefinite-programming-representable functions and some functions that involve C2-cone reducible structures, under conditions such as strict complementarity. Our results are applicable to concrete optimization models such as group-fused Lasso and overlapping group Lasso. In addition, for nonconvex models, we show that the KL exponent of many difference-of-convex functions can be derived from that of their natural majorant functions, and the KL exponent of the Bregman envelope of a function is the same as that of the function itself. Finally, we estimate the KL exponent of the sum of the least squares function and the indicator function of the set of matrices of rank at most k.
Keywords: First-order methods
Convergence rate
Kurdyka-Lojasiewicz inequality
Kurdyka-Lojasiewicz exponent
Publisher: Springer
Journal: Foundations of computational mathematics 
ISSN: 1615-3375
DOI: 10.1007/s10208-021-09528-6
Rights: © SFoCM 2021
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use (, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at:
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
Yu_Kurdyka–Łojasiewicz_Exponent_Inf-projection.pdfPre-Published version1.13 MBAdobe PDFView/Open
Open Access Information
Status open access
File Version Final Accepted Manuscript
View full-text via PolyU eLinks SFX Query
Show full item record

Page views

Last Week
Last month
Citations as of May 28, 2023


Citations as of Jun 2, 2023


Citations as of Jun 1, 2023

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.