# Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methods

arXiv: https://arxiv.org/abs/1602.02915 · HTML: https://mlsanity.com/paper/1602.02915/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2016.

## Built on by (most cited first, 30 of 35)

- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022)
- [Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimization](https://mlsanity.com/paper/2212.12978/) (2022)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)
- [Convergence Analysis of Mean Shift](https://mlsanity.com/paper/2305.08463/) (2023)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties](https://mlsanity.com/paper/2305.05828/) (2023)
- [Convergence Rates of Training Deep Neural Networks via Alternating Minimization Methods](https://mlsanity.com/paper/2208.14318/) (2022)
- [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023)
- [Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimization](https://mlsanity.com/paper/2410.14054/) (2024)
- [SG-PALM: a Fast Physically Interpretable Tensor Graphical Model](https://mlsanity.com/paper/2105.12271/) (2021)
- [Joint reconstruction-segmentation on graphs](https://mlsanity.com/paper/2208.05834/) (2022)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [Convergence Rates of Stochastic Zeroth-order Gradient Descent for L ojasiewicz Functions](https://mlsanity.com/paper/2210.16997/) (2022)
- [Tensor Factorization via Transformed Tensor-Tensor Product for Image Alignment](https://mlsanity.com/paper/2212.05719/) (2022)
- [Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning](https://mlsanity.com/paper/2303.15866/) (2023)
- [Low-Rank Tensor Learning by Generalized Nonconvex Regularization](https://mlsanity.com/paper/2410.18402/) (2024)
- [Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks](https://mlsanity.com/paper/2502.11152/) (2025)
- [A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz condition](https://mlsanity.com/paper/2507.01932/) (2025)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [Coordinate Descent for MCP/SCAD Penalized Least Squares Converges Linearly](https://mlsanity.com/paper/2109.08850/) (2021)
- [An inexact LPA for DC composite optimization and application to matrix completions with outliers](https://mlsanity.com/paper/2303.16822/) (2023)
- [ADMM Algorithms for Residual Network Training: Convergence Analysis and Parallel Implementation](https://mlsanity.com/paper/2310.15334/) (2023)
- [Alternating Iteratively Reweighted ℓ1 and Subspace Newton Algorithms for Nonconvex Sparse Optimization](https://mlsanity.com/paper/2407.17216/) (2024)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)
- [Super-fast Rates of Convergence for Neural Network Classifiers under the Hard Margin Condition](https://mlsanity.com/paper/2505.08262/) (2025)
- [SplInterp: Improving our Understanding and Training of Sparse Autoencoders](https://mlsanity.com/paper/2505.11836/) (2025)
- [Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learning](https://mlsanity.com/paper/2507.04247/) (2025)
- [Dynamic Proximal Gradient Algorithms for Schatten-p Quasi-Norm Regularized Problems](https://mlsanity.com/paper/2603.00333/) (2026)

## Abstract (arXiv)

In this paper, we study the Kurdyka-Lojasiewicz (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 ℓ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.