Localized Curvature for Fast Convergence in Nonconvex Optimization

31 concepts24 papers1 proposal

In classical optimization theory, the gold standard for fast convergence is global strong convexity. When an objective function is strongly convex, it behaves like a perfectly symmetric quadratic bowl. No matter where you stand on the landscape, the gradient points decisively toward the unique global minimum, and its magnitude is proportional to your distance from the bottom. This geometric guarantee allows simple first-order methods like Gradient Descent to achieve linear convergence—halving the distance to the optimum with every few iterations.

However, modern machine learning routinely breaks this ideal paradigm in two distinct ways:

  1. High-Dimensional Underdetermination ($p > n$): When estimating a parameter vector with more features ($p$) than observations ($n$), the loss function's Hessian matrix is fundamentally rank-deficient. The landscape contains infinitely long, perfectly flat valleys where the global Hessian is singular.
  2. Nonconvex Landscapes: Problems involving neural networks, tensor decompositions, or robust losses are inherently nonconvex, littered with plateaus, saddle points, and multiple local minima.

If global strong convexity is absent, standard theory predicts painfully slow convergence or outright failure. Yet, in practice, simple gradient methods converge remarkably fast. The resolution to this paradox lies in a powerful realization: we do not need global curvature; we only need localized curvature. This insight manifests in two complementary frameworks: Restricted Strong Convexity (curvature along specific directions) and Local Strong Convexity (curvature within specific regions).

Restricted Strong Convexity: Curvature in the Right Directions

In high-dimensional statistical recovery, we often look for structured solutions, such as sparse vectors or low-rank matrices. To find them, we minimize an empirical loss function combined with a regularizer (like the $L_1$ norm or trace norm).

Even though the loss function's landscape is flat in many directions due to data scarcity, the regularizer restricts where the optimization error can actually live. As shown in the unified framework by Negahban et al. 2009, when a regularizer is "decomposable," it forces the estimation error to lie within a highly constrained subspace or "cone" of directions. This motivates the concept of Restricted Strong Convexity (RSC). A function satisfies RSC if it maintains a lower bound on its curvature only when evaluated along these restricted error directions.

Imagine a skateboard ramp that is infinitely long and flat along the horizontal axis, but curved like a U-shape along the transverse axis. Globally, it is not strongly convex. But if a constraint forces you to move only along the transverse axis, you experience a perfect quadratic bowl.

The authors of Agarwal et al. 2010 leveraged this property to prove that first-order gradient methods can achieve geometric convergence rates for high-dimensional recovery, shattering the assumption that rank-deficient Hessians inherently slow down optimization.

This geometric perspective has been generalized widely across high-dimensional statistics:

  • Banerjee et al. 2014 provided a unified geometric framework showing that RSC acts as a universal stability condition across arbitrary norm regularizers and data distributions, ensuring the problem remains well-behaved even when parameters exceed samples.
  • Lee et al. 2013 demonstrated that RSC is essential not just for parameter accuracy, but for model selection consistency—ensuring the algorithm correctly identifies the true underlying sparse structure.
  • Even when the loss function itself is nonconvex, the authors of Liu 2025 proved that RSC ensures stationary points remain tightly bounded around the true parameter value, confining estimation errors to a small, structured set.

RSC provides the bedrock for analyzing greedy, constrained, and distributed algorithms as well. For instance, Yuan et al. 2021 used restricted curvature properties on sparse vectors to establish fast risk bounds for Iterative Hard Thresholding (IHT). In decentralized settings, Bao et al. 2022 utilized RSC and restricted smoothness to guarantee fast composite optimization for federated learning, while Boursier et al. 2022 applied it to trace-norm regularization when data is exceptionally scarce. Furthermore, Fercoq et al. 2019 showed that leveraging RSC allows for accelerated convergence rates in almost surely constrained optimization problems by exploiting local curvature properties to reach optimal solutions more efficiently.

Local Strong Convexity and Sharpness: Curvature in the Right Places

While RSC restricts curvature to specific directions, a parallel line of work focuses on restricting curvature to specific regions—typically a local neighborhood around the optimal solution. This is known as Local Strong Convexity or Sharpness.

In many practical applications, an objective function may be flat or wildly nonconvex globally, but it forms a sharp, well-behaved basin near the optimum. If an optimization algorithm can be initialized inside this basin (a "warm start"), it will converge exponentially fast, completely oblivious to the global non-convexity.

Consider the gap between theory and practice in logistic regression or robust estimation. Globally, these losses may lack strong convexity. However, Qu et al. 2016 proved that as long as the expected loss function is locally strongly convex near the optimum, stochastic algorithms can achieve an accelerated $O(\ln T / T)$ fast rate, bridging the gap between theoretical bounds and practical performance. Similarly, Chen et al. 2016 showed that robust, bounded losses designed to ignore outliers (like the Smooth Ramp loss) retain an optimal $O(1/T)$ convergence rate because they maintain local strong convexity around their local minima.

This concept extends to non-smooth and non-convex landscapes through generalized local growth conditions:

  • Local Growth and Sharpness: The authors of Xu et al. 2017 demonstrated that fast convergence in stochastic optimization depends entirely on how rapidly the objective grows locally around the optimal solution, bypassing the need for global smoothness or convexity. Wang et al. 2023 leveraged this "sharpness" property to prove that mini-batch SGD can robustly learn a single neuron (such as a ReLU) under heavy-tailed noise, because the gradient near the optimum remains sufficiently large to prevent vanishing updates.
  • Relaxed Convexity: When even local strong convexity is absent, Hazan et al. 2015 showed that efficient stochastic optimization is still possible under "local quasi-convexity" by focusing purely on gradient directions rather than magnitudes, successfully navigating plateaus and cliffs.

Applications Across Domains

The realization that local or restricted curvature suffices for global-like convergence has transformed guarantees across diverse engineering and mathematical domains:

  • Tensor and Matrix Factorization: Nonconvex reformulations of Semidefinite Programs (SDPs) via low-rank factorization (the Burer-Monteiro approach) are highly scalable but non-convex. Zeng et al. 2018 proved that combining this factorization with variance reduction yields global linear convergence due to local RSC around the optimum. Similarly, Li et al. 2022 established a local regularity condition for general tensor optimization, proving vanilla gradient descent moves consistently toward the global optimum under a warm start because the landscape behaves convexly within a specific radius.
  • Geometric Estimation and Control: In Time-of-Arrival (TOA) localization, the loss surface is non-convex. So et al. 2022 proved that the loss is locally strongly convex around the true target position, explaining why simple Online Gradient Descent can be more robust and efficient than complex second-order methods. In system identification, Stamouli et al. 2024 utilized a quadratic identifiability constraint to ensure local strong convexity for the Quadratic Prediction Error Method (QPEM).
  • Optimal Transport and Distributed Systems: For semi-discrete optimal transport, Genans et al. 2025 showed that constraining the dual objective to a compact set induces a localized form of strong convexity, enabling SGD to hit minimax optimal convergence rates. In distributed statistical optimization, Duchi et al. 2012 relied on the local strong convexity of the population risk to prove that one-shot communication methods can match centralized performance.

Ultimately, the success of modern optimization on complex, high-dimensional, or non-convex landscapes hinges on a shift from global to localized geometric analysis. Whether by restricting the problem to a subspace of meaningful directions (RSC) or a neighborhood of meaningful solutions (local strong convexity), ensuring curvature where it matters allows simple first-order algorithms to operate with the speed and guarantees of classical convex optimization.

Key Foundational Work

A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009) — contributed 2 concept elements to this direction.
Fast global convergence rates of gradient methods for high-dimensional statistical recovery (2010) — 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_restricted_strong_convexity_4d87669e,
  title = {restricted strong convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/restricted-strong-convexity/rdr_4d87669e779940029b87e4d131562579},
  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_restricted_strong_convexity_4d87669e_v1,
  title = {restricted strong convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/restricted-strong-convexity/rdr_4d87669e779940029b87e4d131562579/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake