Tutte Colloquium - Ting Kei Pong

Title: Deducing Kurdyka-Łojasiewicz exponent of optimization models

Abstract:

Kurdyka-Łojasiewicz (KL) exponent is an important quantity for determining the qualitative convergence behavior of many first-order methods. In this talk, we review some known connections between the KL exponent and other important error bound concepts, and discuss some calculus rules that allow us to determine the KL exponent of new functions from functions with known KL exponent. Specifically, we will show that KL exponents are preserved via inf-projections and can be deduced from Lagrangians, under mild assumptions. This allows us to obtain, under suitable assumptions, the KL exponent of many important convex or nonconvex optimization models, such as group fused LASSO, least squares with MCP or SCAD regularization, least squares with rank constraint, and envelope functions such as the Moreau envelope and the forward-backward envelope.

This is a joint work with Guoyin Li and Peiran Yu.