In classical optimization theory, Global Strong Convexity (GSC) is the gold standard for ensuring fast convergence. If an objective function is globally strongly convex, it possesses a strict quadratic lower bound across its entire domain. This guarantees that the gradient always points reliably toward the unique global minimum, allowing first-order methods to achieve a geometric (linear) convergence rate.
However, modern machine learning frequently operates in high-dimensional regimes ($p \gg n$) where the number of features significantly exceeds the number of observations. In these settings, the sample covariance matrix is inherently rank-deficient, creating a null space where the objective function is completely flat. As highlighted by Lin Xiao et al. in A Proximal-Gradient Homotopy Method for the L1-Regularized Least-Squares Problem, this lack of global curvature invalidates standard fast-convergence proofs.
Traditional worst-case analysis predicts that optimization algorithms should slow down to a sluggish sublinear rate ($O(1/T)$ or $O(1/\sqrt{T})$) on such landscapes. Yet, in practice, these algorithms converge rapidly. A major research direction has emerged to resolve this paradox by showing that global strong convexity is not a necessity for fast convergence; instead, algorithms can exploit localized or restricted forms of curvature.
The Core Intuition: Curvature Where It Matters
An optimization algorithm does not visit every point in a landscape; it traverses a specific trajectory. Therefore, fast convergence does not require a function to be strongly convex everywhere—it only requires the function to have curvature along the path the algorithm travels or locally around the optimum.
This insight manifests through several theoretical frameworks:
- Restricted Strong Convexity (RSC): The objective function behaves as if it were strongly convex when restricted to specific low-dimensional subspaces, such as the space of sparse vectors.
- Local Growth Conditions and Error Bounds: The function grows at a sufficient rate as iterates move away from the optimal solution set, even if it contains flat valleys elsewhere.
As demonstrated by Yi Xu et al. in Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence, a stronger local growth condition directly accelerates global convergence rates for non-smooth problems. Similarly, Zirui Zhou et al. in $\ell_{1, p}$-Norm Regularization: Error Bounds and Convergence Rate Analysis of First-Order Methods utilize structural error bounds to prove that first-order methods can maintain fast linear convergence for specific regularizers without relying on global strong convexity.
Homotopy Paths and Effective Strong Convexity
One of the most powerful mechanisms for exploiting localized curvature is the homotopy continuation method. In high-dimensional sparse recovery (like the Lasso), the global loss function lacks strong convexity due to the underdetermined nature of the system. However, if the optimization iterates can be kept strictly sparse, they remain within a low-complexity subspace where the data matrix behaves like a well-conditioned operator.
[Large Regularization (λ)] ---> Iterates are highly sparse (High Local Curvature)
|
v (Warm Start)
[Medium Regularization (λ)] --> Iterates remain sparse (Effective Curvature)
|
v (Warm Start)
[Target Regularization (λ)] ---> Fast Convergence to Global Minimum
Lin Xiao et al. and Tong Zhang et al. in A Proximal-Gradient Homotopy Method for the Sparse Least-Squares Problem formalize this using a Proximal-Gradient Homotopy (PGH) framework. Instead of optimizing the target ill-conditioned objective directly, the algorithm solves a sequence of problems defined by a gradually decreasing regularization parameter $\lambda$:
- High Regularization: The algorithm starts with a large $\lambda$, forcing the initial solution to be highly sparse. In this sparse subspace, the objective exhibits strong local curvature.
- Continuation & Warm Starts: The parameter $\lambda$ is systematically reduced. The solution from the previous step serves as a "warm start" for the next.
- Restricted Trajectory: Because of the warm start, the algorithm's trajectory is confined to a region where the iterates remain sparse, bypassing the non-strongly convex zones of the global landscape entirely.
This strategy allows the algorithm to achieve a global geometric convergence rate. Reza Eghbali et al. in Decomposable norm minimization with proximal-gradient homotopy algorithm extended this principle beyond vector sparsity, proving that homotopy methods can exploit "effective" strong convexity for any decomposable norm by keeping the optimization path restricted to low-complexity structures.
Adaptive Restarting Schemes
Standard accelerated first-order methods (such as Nesterov’s acceleration) typically require explicit knowledge of the global strong convexity parameter to properly tune their momentum steps. When this parameter is zero or unknown, standard acceleration can fail or oscillate wildly in high-dimensional settings, a challenge noted by Marie Maros et al. in Acceleration in Distributed Sparse Regression.
To capture local curvature without global knowledge, researchers employ scheduled restart schemes. The core idea is to run an accelerated algorithm for a fixed window of iterations, halt it, reset the momentum, and restart the algorithm using the current iterate as the new initial state.
Qihang Lin et al. in An Adaptive Accelerated Proximal Gradient Method and its Homotopy Continuation for Sparse Optimization demonstrate that an adaptive restarting scheme can automatically estimate the local strong convexity parameters along the path. This achieves a "square-root" speedup in iteration complexity—moving from $O(\kappa_s)$ to $O(\sqrt{\kappa_s})$, where $\kappa_s$ is the restricted condition number.
Similarly, Junqi Tang et al. developed Rest-Katyusha: Exploiting the Solution's Structure via Scheduled Restart Schemes, which applies scheduled restarts to stochastic accelerated methods. By leveraging the solution's inherent low-dimensional structure, they achieve accelerated linear convergence under Restricted Strong Convexity, proving that explicit global curvature is unnecessary for state-of-the-art stochastic acceleration.
Fast Rates in Stochastic and Online Settings
The absence of global strong convexity is particularly problematic in stochastic optimization, where gradient noise can trap algorithms in flat regions. Traditional Stochastic Gradient Descent (SGD) yields a slow $O(1/\sqrt{T})$ convergence rate on general convex functions, and standard theory requires global strong convexity to unlock the optimal $O(1/T)$ or $O(1/n)$ "fast rate."
However, local properties are sufficient to achieve these fast rates in stochastic environments:
- Local Convexity Around the Optimum: Chao Qu et al. show in Fast Rate Analysis of Some Stochastic Optimization Algorithms that popular stochastic algorithms achieve an $O(\ln T / T)$ rate as long as the expectation of the loss function is locally strongly convex around the optimal solution.
- Iterate Averaging: For composite least-squares problems, Nicolas Flammarion et al. demonstrate in Stochastic Composite Least-Squares Regression with Convergence Rate $O(1/n)$ that Stochastic Dual Averaging combined with a constant step-size and iterate averaging achieves the optimal $O(1/n)$ rate without requiring the objective to be strongly convex anywhere.
- The Interpolation Regime: In overparameterized or kernel settings where models fit the data perfectly, the smallest eigenvalue of the covariance matrix often approaches zero. Aditya Vardhan Varre et al. prove in Last iterate convergence of SGD for Least-Squares in the Interpolation regime that the final iterate of SGD achieves fast polynomial convergence rates without needing iterate averaging or decaying step sizes, defying conventional pessimistic bounds.
Unifying Structural Optimization
Shifting the analytical focus from global geometric properties to localized structural properties provides a unified explanation for why diverse optimization algorithms perform well in high-dimensional statistics.
For example, Ryan Tibshirani in Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions establishes deep theoretical connections between Dykstra's algorithm, ADMM, and coordinate descent, clarifying how their rapid convergence in $\ell_1$-regularized problems stems from shared underlying geometric structures rather than global curvature.
When these local conditions are fundamentally violated—such as in non-convex landscapes induced by weakly convex regularizers (Xinyue Shen et al., Nonconvex Sparse Logistic Regression With Weakly Convex Regularization)—standard first-order methods can stall in local minima. To bypass this limitation entirely when local strong convexity fails, Hongcheng Liu in Global solutions to folded concave penalized nonconvex learning introduces a mixed-integer programming framework (MIPGO) to guarantee global optimality.
Ultimately, this body of research demonstrates that the optimization landscape of high-dimensional machine learning is far more forgiving than global metrics suggest. By designing algorithms that remain within highly curved subspaces or adaptively respond to local growth, fast convergence can be reliably achieved.
Key Foundational Work
On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems (2013) — contributed 1 concept elements to this direction.
A Proximal-Gradient Homotopy Method for the L1-Regularized Least-Squares Problem (2012) — contributed 1 concept elements to this direction.
Constrained stochastic gradient descent for large-scale least squares problem (2013) — contributed 1 concept elements to this direction.