Constant Nullspace Strong Convexity and Fast Convergence of Proximal Methods under High-Dimensional Settings

Ian En-Hsu Yen, Cho-Jui Hsieh, Pradeep Ravikumar, Inderjit S. DhillonNeurIPS 2014 · OpenReview

This paper bridges the gap between optimization theory and the practical performance of high-dimensional statistical models.

TL;DR

High-dimensional optimization problems (where features outnumber samples) often lack the "strong convexity" needed for fast convergence, yet algorithms like Proximal Gradient work surprisingly well in practice. This paper introduces Constant Nullspace Strong Convexity (CNSC) to explain this phenomenon, proving that standard proximal methods achieve linear or even quadratic convergence rates under this realistic condition.

In modern machine learning, we often deal with high-dimensional settings where the number of parameters ($d$) is much larger than the number of samples ($n$). When solving these problems (e.g., Lasso or sparse logistic regression), the underlying math gets tricky.

Specifically, the Hessian matrix—which describes the curvature of the loss function—becomes rank-deficient. In optimization terms, the function is no longer strongly convex because it has "flat" directions. Standard theory suggests that without strong convexity, optimization algorithms should be sluggish, converging at a slow "sublinear" rate. However, practitioners consistently observe much faster performance. The authors set out to find the missing theoretical link that explains why these algorithms are so efficient in high-dimensional regimes.

Introducing Constant Nullspace Strong Convexity (CNSC)

The authors introduce a new condition called Constant Nullspace Strong Convexity (CNSC) to bridge this gap.

  1. The CNSC Condition: Instead of requiring the function to be strictly curved in every direction, CNSC only requires it to be strongly convex over a specific constant subspace (typically the range of the data matrix) while allowing it to be flat in the nullspace. They show that almost all standard $M$-estimators (like those used in linear and logistic regression) naturally satisfy this property.
  2. Proximal Gradient (Prox-GD) Analysis: By combining the CNSC property with Hoffman’s Bound (a geometric tool relating the distance to a solution set to the violation of constraints), they prove that Prox-GD achieves global linear convergence. This means the error decreases exponentially, rather than at a sublinear crawl.
  3. Proximal Newton Analysis: They further show that for second-order methods, CNSC guarantees local quadratic convergence. This explains why Proximal Newton methods can find highly accurate solutions in just a few iterations once they get close to the optimum.

Key Insights

  • Algebraic vs. Statistical Assumptions: Unlike previous work that relied on statistical assumptions (like the Restricted Isometry Property), CNSC is a purely algebraic property. It depends on the form of the loss function and the data matrix, making it more broadly applicable and easier to verify.
  • The Role of Decomposability: The fast convergence of Prox-GD relies on the regularization term (like the $\ell_1$ norm) being "decomposable." This structure allows the algorithm to navigate the "flat" directions of the loss function effectively.
  • Explaining the "Gap": The paper identifies that the "flatness" in high-dimensional problems isn't random; it is confined to a constant nullspace. Because the nullspace doesn't change as the algorithm steps, the optimizer can effectively "ignore" it and converge quickly on the important subspace.

Empirical Results

The authors validated their theory using the rcv1.1k dataset (a subset of the Reuters Corpus Volume 1) in a high-dimensional configuration ($d = 10,192$ and $n = 1,000$). This setup specifically triggers the rank-deficient regime where standard strong convexity fails.

  • Theoretical Bounds: For Prox-GD, the paper provides a finite-iteration bound showing that the distance to the optimal set shrinks by a constant factor $(1 - \alpha)$ at each step. For Prox-Newton, the distance to the optimal $z$ satisfies $\|z_{t+1} - \bar{z}\| \leq \frac{L_H}{2m} \|z_t - \bar{z}\|^2$.
  • Empirical Confirmation: The authors compared Logistic loss (which satisfies CNSC) against $\ell_2$-hinge loss (which does not satisfy the strictness required for CNSC in the same way).
Convergence comparison of Prox-GD and Prox-Newton on logistic vs. L2-hinge loss.

The results showed a stark qualitative difference: the Logistic loss curves formed straight lines on a log-scale (indicating linear convergence), while the hinge loss convergence was significantly slower.

Limitations and Future Work

  • Local vs. Global: While the Prox-GD result is global, the Proximal Newton quadratic convergence is local, meaning the algorithm must already be somewhat close to the solution for the "super-fast" phase to kick in.
  • Norm Constraints: The linear convergence proof for Prox-GD specifically targets decomposable norms. Extending this to more general non-smooth penalties remains an open area.
  • Step Size: The analysis assumes certain properties of the step size and Lipschitz constants which, in practice, are often estimated via line search. The impact of inexact line searches on these specific rates could be explored further.

Summary updated

Abstract

State of the art statistical estimators for high-dimensional problems take the form of regularized, and hence non-smooth, convex programs. A key facet of thesestatistical estimation problems is that these are typically not strongly convex under a high-dimensional sampling regime when the Hessian matrix becomes rank-deficient. Under vanilla convexity however, proximal optimization methods attain only a sublinear rate. In this paper, we investigate a novel variant of strong convexity, which we call Constant Nullspace Strong Convexity (CNSC), where we require that the objective function be strongly convex only over a constant subspace. As we show, the CNSC condition is naturally satisfied by high-dimensional statistical estimators. We then analyze the behavior of proximal methods under this CNSC condition: we show global linear convergence of Proximal Gradient and local quadratic convergence of Proximal Newton Method, when the regularization function comprising the statistical estimator is decomposable. We corroborate our theory via numerical experiments, and show a qualitative difference in the convergence rates of the proximal algorithms when the loss function does satisfy the CNSC condition.
BibTeX
@inproceedings{yen2014constant,
  author = {Ian En-Hsu Yen and Cho-Jui Hsieh and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{Constant Nullspace Strong Convexity and Fast Convergence of Proximal Methods under High-Dimensional Settings}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=Sy-EwubuWr},
}
Figure