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

Abstract

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 $\frac{1}{2}$. 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 $\frac{1}{2}$. 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.

The paper has been published in Foundations of Computational Mathematics: https://link.springer.com/article/10.1007/s10208-017-9366-8. In this update, we added the domain and range of g and h in Theorem 3.5 to remove ambiguity. See also the notes under the previous two updates for changes after the journal version is published

References in corpus (1)

• Nearly unbiased variable selection under minimax concave penalty

Cited by in corpus (20)

• Acceleration Methods
• Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs
• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• A structured L-BFGS method and its application to inverse problems
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• Error bounds, facial residual functions and applications to the exponential cone
• Inertial Proximal Block Coordinate Method for a Class of Nonsmooth Sum-of-Ratios Optimization Problems
• Convergence analysis under consistent error bounds
• Generalized subdifferentials of spectral functions over Euclidean Jordan algebras
• A proximal subgradient algorithm with extrapolation for structured nonconvex nonsmooth problems
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• Approximate Bregman Proximal Gradient Algorithm for Relatively Smooth Nonconvex Optimization
• Global convergence of the gradient method for functions definable in o-minimal structures
• Joint reconstruction-segmentation on graphs
• Majorization-minimization Bregman proximal gradient algorithms for NMF with the Kullback--Leibler divergence
• Eigenvalue programming beyond matrices
• Fast Gradient Algorithm with Dry-like Friction and Nonmonotone Line Search for Nonconvex Optimization Problems
• Proximal Algorithms for Smoothed Online Convex Optimization with Predictions
• Proximal Dogleg Opportunistic Majorization for Nonconvex and Nonsmooth Optimization
• Concrete convergence rates for common fixed point problems under Karamata regularity