In classical optimization theory, "strong convexity" is the gold standard. It guarantees that an objective function has enough curvature everywhere to allow algorithms like gradient descent to converge at a lightning-fast linear rate. Without it, we are typically told to expect much slower, sub-linear progress.
However, modern machine learning lives in a high-dimensional world where the number of features ($p$) often exceeds the number of observations ($n$). In this $p > n$ regime, global strong convexity is mathematically impossible—the objective function is "flat" along many directions. Yet, practitioners consistently observe that algorithms like Coordinate Descent and Proximal Gradient methods converge rapidly anyway.
This research direction explains this paradox by showing that we don't need global strong convexity. Instead, we can rely on "restricted" or "local" properties that emerge from the structure of the data and the sparsity of the solution.
The Geometry of the Null Space
To understand why high-dimensional problems lack strong convexity, imagine a least-squares objective. The curvature is determined by the eigenvalues of the data matrix. When $p > n$, the matrix is rank-deficient, meaning it has a "null space"—a set of directions where the function is perfectly flat. If your optimization path wanders into this null space, the gradient provides no information on how to reach the unique minimum, because a unique minimum might not even exist.
Standard theory, as noted by Haibin Zhang, Jiaojiao Jiang, and Zhi-Quan Luo in On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems, fails here because it assumes the function curves upward in every direction.
Restricted Strong Convexity
The breakthrough intuition is that we only need the function to be strongly convex in the directions that actually matter. In sparse recovery (like the Lasso), we are looking for a solution where most coefficients are zero.
Lin Xiao and Tong Zhang demonstrate this in their work on A Proximal-Gradient Homotopy Method for the L1-Regularized Least-Squares Problem. They show that if the data satisfies a "Restricted Strong Convexity" (RSC) condition, the function behaves as if it were strongly convex on the subset of sparse vectors. By using a homotopy method—solving a sequence of problems with decreasing regularization—the algorithm stays within these "well-curved" regions, achieving geometric convergence despite the global flatness.
Beyond Curvature: The Error Bound Property
While RSC is a property of the data, researchers have found a more general geometric condition called the Luo-Tseng Error Bound. This property doesn't require the function to be curved; instead, it requires that the distance from any point to the set of optimal solutions is bounded by the magnitude of the gradient (or the proximal gradient).
Man-Chung Yue, Anthony Man-Cho So, and Zirui Zhou leveraged this in Inexact Regularized Proximal Newton Method: Provable Convergence Guarantees for Non-Smooth Convex Minimization without Strong Convexity. They proved that second-order methods can achieve superlinear or even quadratic convergence on degenerate, high-dimensional datasets as long as this error bound holds. This explains why "proximal Newton" methods remain efficient even when the Hessian is singular.
Exploiting Structure and Sparsity
Another facet of this direction is structure-adaptivity. If a solution is sparse, the algorithm eventually "identifies" the correct support (the non-zero features). Once the support is identified, the problem effectively collapses from a high-dimensional flat space to a low-dimensional space where the function is strongly convex.
- Coordinate Descent: Quentin Klopfenstein, Samuel Vaiter, and colleagues showed in Model identification and local linear convergence of coordinate descent that cyclic coordinate descent identifies the sparsity pattern in finite steps, after which it converges linearly.
- Adaptive Acceleration: Junqi Tang and Mohammad Golbabaee proposed structure-adaptive algorithms in Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization that estimate these local stability parameters on the fly to accelerate convergence.
Stochastic and Decentralized Settings
The shift away from global strong convexity has also transformed stochastic optimization. Francis Bach and Eric Moulines showed in Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) that with proper averaging, one can achieve $O(1/n)$ rates even without strong convexity, a significant improvement over the standard $O(1/\sqrt{n})$.
In decentralized systems, where data is spread across a network, Gesualdo Scutari and Ying Sun demonstrated in Decentralized Sparse Linear Regression via Gradient-Tracking that gradient tracking allows a network to collectively exploit local structure, achieving linear convergence to the statistical optimum even when the global objective is not strongly convex.
Summary of Intuition
The reason these algorithms work so well in high dimensions is that optimization paths are not random. They are guided by regularizers (like $L_1$) and algorithmic structures (like coordinate updates) that force the iterates to stay in regions where the function has "effective" curvature. Whether through Restricted Strong Convexity, Error Bounds, or Manifold Identification, the field has moved from requiring global curvature to proving that local structure is enough.