Linear Convergence under Metric Subregularity

30 concepts17 papers1 proposal

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:


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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_metric_subregularity_6bc6d6b0,
  title = {metric subregularity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/metric-subregularity/rdr_6bc6d6b0947c43b9a1a9be8d427490f9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_metric_subregularity_6bc6d6b0_v1,
  title = {metric subregularity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/metric-subregularity/rdr_6bc6d6b0947c43b9a1a9be8d427490f9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake