In classical optimization, we often rely on the comfort of convexity. If a function is convex, any local minimum is a global one, and gradient descent is virtually guaranteed to find it. However, modern machine learning—from deep neural networks to sparse dictionary learning—operates in a "wild" territory of non-convex and non-smooth functions. In these landscapes, traditional proofs fail. An algorithm might see its objective value decrease, yet its parameters could oscillate indefinitely or wander through flat regions without ever settling at a single solution.
To solve this, researchers have converged on a powerful mathematical tool: the Kurdyka-Łojasiewicz (KL) property. This property provides the "rigidity" necessary to prove that iterative algorithms actually settle down—achieving global convergence of the entire sequence of iterates to a single stationary point.
The Problem of Wandering Iterates
In non-convex optimization, the primary fear is not just failing to find the global optimum, but failing to converge at all. As noted by Yangyang Xu and Wotao Yin in A globally convergent algorithm for nonconvex optimization based on block coordinate update, standard convergence proofs often only guarantee that the objective value stabilizes or that some subsequence of the parameters converges. This is insufficient for practical machine learning, where we need the actual model weights to stop changing.
Without a property like KL, an algorithm could theoretically orbit a set of critical points forever. This is a known risk in algorithms like Lloyd’s algorithm for quantization or Mean Field inference. Léo Portales and Elsa Cazelles recently addressed this for Lloyd's algorithm, using the KL inequality to ensure that iterates settle on a specific configuration rather than oscillating between multiple accumulation points [On the Sequential Convergence of Lloyd’s Algorithms].
The Intuition: Avoiding the Flatness Trap
The KL property essentially dictates that a function cannot be "too flat" near its critical points. Mathematically, it relates the value of the function to the magnitude of its gradient (or subgradient). If a function satisfies the KL property, then as long as you are not at a stationary point, the gradient is large enough to push you toward one.
This property is surprisingly universal. It holds for "tame" functions—those definable in o-minimal structures, which include most functions used in deep learning, such as polynomials, exponentials, and even ReLU activations. Arnulf Jentzen and colleagues leverage this in Mathematical Introduction to Deep Learning to provide a rigorous foundation for neural network training, moving beyond "black box" heuristics to prove convergence to critical points.
A Safety Net for Inexact and Stochastic Solvers
One of the most practical applications of the KL framework is that it allows for "imprecise" math. In large-scale problems, calculating exact gradients or solving sub-problems perfectly is often too expensive.
The Inexact Proximal Alternating Direction (IPAD) method and the Task Embedded Coordinate Update (TECU) framework, developed by researchers like Risheng Liu, use the KL property as a theoretical safety net. In Task Embedded Coordinate Update, the authors show that you can plug in "imprecise" task-specific solvers—even deep learning models—into an optimization loop. As long as the errors are controlled and the underlying objective satisfies the KL property, the entire system is guaranteed to reach a stable equilibrium.
Similarly, in the realm of stochastic optimization, the SPRING algorithm [SPRING: A fast stochastic proximal alternating method] by Derek Driggs and others combines variance-reduced gradients with the KL framework. This ensures that even with the randomness of mini-batch sampling, the algorithm reliably reaches a stable critical point in non-smooth, non-convex landscapes.
Broadening the Reach: From Tensors to Control
The reach of KL-based convergence analysis extends across diverse domains:
- Tensor Completion: Bin Gao et al. use KL to ensure that alternating minimization for graph-regularized tensors doesn't stall, even with extremely sparse data [Alternating minimization algorithms for graph regularized tensor completion].
- Predictive Control: Jean-Hubert Hours and Colin Jones applied the property to Nonlinear Model Predictive Control (NMPC), proving that tracking errors remain bounded even when only a few iterations are performed per time step [A Parametric Non-Convex Decomposition Algorithm].
- Biological Data: In single-cell RNA sequencing, Wenwen Min demonstrated that the non-convex $\ell_{2,0}$-norm used for feature selection satisfies the KL property, justifying the use of fast proximal algorithms for clustering cell types [Structured Sparse Non-negative Matrix Factorization].
By shifting the focus from the global geometry of the landscape (convexity) to the local growth properties near critical points (KL), this research direction has provided the mathematical "glue" that holds modern, non-convex optimization together. It ensures that our most complex models don't just work by accident, but by geometric necessity.