Fast Convergence in High-Dimensional Non-Strongly Convex Optimization

This direction is split into other directions: global strong convexity deficiency. Its last version stays readable and citable here.

Version 1 of 146 papers46 conceptsfrozen 2026-10-04

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.

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fast_convergence_in_high_dimensional_non_f4d2949f,
  title = {Fast Convergence in High-Dimensional Non-Strongly Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-convergence-in-high-dimensional-non-strongly-convex-optimization/rdr_f4d2949f52414018a8dfea5dda20b14c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_fast_convergence_in_high_dimensional_non_f4d2949f_v1,
  title = {Fast Convergence in High-Dimensional Non-Strongly Convex Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-convergence-in-high-dimensional-non-strongly-convex-optimization/rdr_f4d2949f52414018a8dfea5dda20b14c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}