In classical optimization theory, guaranteeing fast convergence—specifically linear convergence, where the error decreases exponentially—typically requires strict structural assumptions. The most common of these is strong convexity (or strong monotonicity in the context of operators). Strong convexity ensures that the objective function has a strict upward curvature everywhere, meaning that the gradient grows rapidly as you move away from the minimum.
However, many foundational models in machine learning and mathematical programming do not possess this global curvature. Linear Programs, Lasso ($L_1$-regularized regression), and Support Vector Machines (SVMs) all feature flat or piecewise-linear regions where strong convexity fails completely. Yet, in practice, first-order and second-order algorithms often converge to the optimal solution exponentially fast anyway.
This gap between pessimistic theoretical bounds and excellent practical performance is explained by a relaxed geometric condition known as metric subregularity.
The Intuition: Bounding Distance by Residuals
To understand why metric subregularity works, consider what an optimization algorithm actually sees. The algorithm evaluates an operator or a gradient—let's call it the residual—to determine how far it is from equilibrium. If the residual is zero, the algorithm has found a solution.
Under strong convexity, a large distance from the solution guarantees a massive residual, forcing the algorithm to take decisive steps. Metric subregularity relaxes this requirement significantly. Instead of demanding curvature everywhere, it simply requires that the distance to the optimal solution set is bounded by a multiple of the residual.
$$\text{Distance to Solution Set} \le \kappa \times \| \text{Residual} \|$$
Geometrically, this means the optimization landscape cannot become arbitrarily flat as you move away from the solution set. Even if the objective function has a valley of multiple optimal solutions, moving perpendicular to this valley causes the residual to grow at least linearly. As long as this condition holds locally or globally, an algorithm cannot get "stuck" in a flat region far from the optimum. Every step that reduces the residual translates directly into geometric progress toward the solution set.
Unlocking Speed in Primal-Dual and Coordinate Methods
Primal-dual splitting and coordinate descent methods are highly favored for large-scale optimization because their individual iterations are computationally cheap. By exploiting metric subregularity, researchers have shown that these cheap iterations can still achieve exponential convergence rates on non-strongly convex problems.
For instance, Ahmet Alacaoglu et al. demonstrated in Random extrapolation for primal-dual coordinate descent and On the Convergence of Stochastic Primal-Dual Hybrid Gradient that metric subregularity allows primal-dual coordinate methods to achieve linear convergence on problems with piecewise linear-quadratic structures, such as Lasso and Linear Programming. This eliminates the need for users to artificially alter or regularize their objectives to force strong convexity.
Similarly, Daoli Zhu et al. leveraged a global variant of this property in Linear Convergence of Randomized Primal-Dual Coordinate Method for Large-scale Linear Constrained Convex Programming. They proved that randomized coordinate updates achieve linear convergence for linearly constrained convex programs by bounding the distance to the optimal set via the violation of the optimality conditions.
For broader operator splitting frameworks, Puya Latafat and Panagiotis Patrinos proved in Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators that linear convergence is preserved under metric subregularity for complex monotone inclusion problems, bypassing the traditional requirement for strong monotonicity.
Accelerating Decentralized and Networked Optimization
In decentralized optimization, a network of agents collaborates to solve a global problem by communicating only with their immediate neighbors. Here, communication bandwidth is the primary bottleneck, making fast convergence rates critical.
Because global objectives are aggregated across networks, enforcing global strong convexity is often impractical. Metric subregularity serves as a powerful alternative framework to guarantee network efficiency:
- Composite and Non-Smooth Objectives: Luyao Guo et al. established linear convergence for decentralized proximal gradient methods with network-independent stepsizes in Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization. Similarly, Jinrui Huang et al. utilized metric subregularity in Communication-Efficient Decentralized Optimization via Double-Communication Symmetric ADMM to maintain linear convergence rates for non-smooth regularized problems like $L_1$-norm penalties.
- Piecewise Linear-Quadratic Problems: The authors of A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization (TriPD) showed that asynchronous, localized updates achieve linear convergence for piecewise linear-quadratic problems by exploiting subregularity instead of strong convexity.
- Fixed-Point and Quantized Networks: Xiuxian Li and Min Meng extended this principle to multiagent operators under the closely related banner of linear regularity in DOT and DOP: Linearly Convergent Algorithms for Finding Fixed Points of Multiagent Operators. To address hardware constraints, Ziqin Chen et al. demonstrated in Quantized Primal-Dual Algorithms for Network Optimization With Linear Convergence that even when communication is quantized to save bandwidth, metric subregularity preserves exact linear convergence.
Beyond Linear: Superlinear and Higher-Order Convergence
The utility of metric subregularity is not confined to first-order linear convergence; it also underpins fast local convergence in second-order and fixed-point algorithms.
Traditionally, Newton-type methods require the Jacobian of the residual operator to be nonsingular at the solution to achieve superlinear or quadratic convergence. Metric subregularity weakens this assumption. In SuperMann: A Superlinearly Convergent Algorithm for Finding Fixed Points of Nonexpansive Operators, Andreas Themelis and Panagiotis Patrinos showed that fixed-point iterations can achieve superlinear convergence under metric subregularity even when the Jacobian is singular or the problem is highly ill-conditioned.
This robustness is highly practical. For instance, Xudong Li et al. leveraged metric subregularity in A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems to build a semismooth Newton solver that maintains superlinear convergence and numerical stability on degenerate, real-world datasets where solution uniqueness is not guaranteed.
To push the boundaries of convergence theory even further, Boris S. Mordukhovich et al. introduced the concept of metric $q$-subregularity in A globally convergent proximal Newton-type method in nonsmooth convex optimization. By parameterizing the growth of the residual with an exponent $q$, they proved that optimization frameworks can achieve convergence rates that surpass standard quadratic limits when $q > 1$.
Boundaries and Limitations
While metric subregularity provides a powerful framework for relaxing convexity requirements, it is not a universal panacea. The geometric structure of the underlying sets and operators dictates whether subregularity is sufficient for acceleration.
For example, Damek Davis and Wotao Yin demonstrated in Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions that for feasibility problems, the specific regularity of the intersecting sets directly governs whether splitting algorithms like ADMM can beat their worst-case bounds.
Crucially, metric subregularity alone does not always guarantee fast rates. In Scaled relative graphs: nonexpansive operators via 2D Euclidean geometry, Ernest K. Ryu et al. utilized geometric analysis to show that in certain operator configurations, metric subregularity is insufficient by itself to yield linear convergence, meaning that stronger properties like strong monotonicity remain indispensable in specific mathematical contexts.
Key Foundational Work
Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators (2017) — contributed 3 concept elements to this direction.
A Highly Efficient Semismooth Newton Augmented Lagrangian Method for Solving Lasso Problems (2018) — contributed 2 concept elements to this direction.
Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions (2017) — contributed 1 concept elements to this direction.