In classical optimization theory, the "gold standard" for achieving fast, linear convergence is strong convexity. If a function is strongly convex, its landscape has a reliable curvature that pushes every gradient step decisively toward the unique optimum. However, many of the most important problems in modern machine learning and signal processing—such as Lasso, Support Vector Machines, and Linear Programming—are not strongly convex. They often possess "flat" regions or non-unique solutions where traditional theory predicts slow, sub-linear progress.
A growing body of research has identified metric subregularity as the fundamental geometric property that explains why many algorithms actually achieve linear convergence in practice, even when strong convexity is absent.
The Intuition: Beyond Curvature
The core idea of metric subregularity is to shift focus from the curvature of the objective function to the stability of the solution set. An operator is metrically subregular if the distance from a point to the solution set is locally bounded by the "residual" (the error or step size) at that point.
Think of it as a "sharpness" condition: as long as the algorithm's progress doesn't "stall" too much as it approaches the solution, it can maintain a high speed. Jingwei Liang and Jalal Fadili show in Convergence Rates with Inexact Non-expansive Operators that this property allows iterative methods to transition from slow global convergence to a much faster linear regime once they enter a neighborhood of the solution.
Bridging Theory and Practice
Metric subregularity is significantly less restrictive than strong convexity. It accommodates functions with flat regions and problems with multiple solutions, which are common in high-dimensional settings where the number of features exceeds the number of samples.
- Splitting Methods: Shaohua Pan demonstrates in Linear convergence of the generalized PPA and several splitting methods that popular algorithms like Douglas-Rachford and Forward-Backward splitting achieve linear rates under metric subregularity.
- Primal-Dual Algorithms: Work by Ahmet Alacaoglu and Volkan Cevher on Stochastic Primal-Dual Hybrid Gradient proves that these methods are robust and fast without needing manual tuning for strong convexity, provided the problem is metrically subregular.
- Decentralized Systems: In distributed networks, Xiuxian Li and Min Meng use a related concept called "linear regularity" to guarantee fast convergence for multi-agent operators in DOT and DOP.
Structural Sufficient Conditions
While metric subregularity is a powerful theoretical tool, it can be difficult to verify directly. Researchers have identified "structural" properties that automatically guarantee it. For instance, piecewise linear-quadratic functions—which include the objectives for Lasso and L1-regularized problems—naturally satisfy metric subregularity.
Xudong Li, Defeng Sun, and Kim-Chuan Toh leverage this in their Semismooth Newton Augmented Lagrangian Method, showing that exploiting the underlying geometry (or "second-order sparsity") allows for superlinear convergence even on ill-conditioned, real-world datasets.
A Unified View of Convergence
Recent theoretical work has sought to unify these concepts with other frameworks. Shaohua Pan and Yulan Liu established in Metric Subregularity of Subdifferential and KL Property of Exponent 1/2 that for convex functions, metric subregularity is equivalent to the Kurdyka-Łojasiewicz (KL) property with an exponent of 1/2. This equivalence provides a rigorous mathematical bridge between variational analysis and the practical observation of fast convergence in non-smooth optimization.