Square-root lasso: pivotal recovery of sparse signals via conic programming

Alexandre Belloni, Victor Chernozhukov, Lei WangBiometrika 2011 · DOI · arXiv

Abstract

We propose a pivotal method for estimating high-dimensional sparse linear regression models, where the overall number of regressors $p$ is large, possibly much larger than $n$, but only $s$ regressors are significant. The method is a modification of the lasso, called the square-root lasso. The method is pivotal in that it neither relies on the knowledge of the standard deviation $\sigma$ nor does it need to pre-estimate $\sigma$. Moreover, the method does not rely on normality or sub-Gaussianity of noise. It achieves near-oracle performance, attaining the convergence rate $\sigma\{(s/n) \log p\}^{1/2}$ in the prediction norm, and thus matching the performance of the lasso with known $\sigma$. These performance results are valid for both Gaussian and non-Gaussian errors, under some mild moment restrictions. We formulate the square-root lasso as a solution to a convex conic programming problem, which allows us to implement the estimator using efficient algorithmic methods, such as interior-point and first-order methods.

Introduction

In modern statistical learning, researchers frequently encounter high-dimensional datasets where the number of features ($p$) exceeds the number of observations ($n$). The standard approach to this problem is the Lasso (Least Absolute Shrinkage and Selection Operator), which relies on the assumption of sparsity—that only a small subset ($s$) of features truly influence the outcome.

However, the standard Lasso faces a significant practical hurdle: the optimal choice of its regularization parameter, $\lambda$, is intrinsically linked to the unknown standard deviation of the noise, $\sigma$. In practice, $\sigma$ is rarely known, and estimating it in high-dimensional settings is a complex, often circular problem. If $\sigma$ is poorly estimated, the resulting model may suffer from either excessive noise inclusion or the omission of critical signals. This paper introduces the Square-root Lasso, a "pivotal" estimator that eliminates the need for prior knowledge or pre-estimation of the noise level.

The Square-root Lasso Estimator

The Square-root Lasso modifies the traditional Lasso objective function by replacing the Mean Squared Error (MSE) with its square root. The optimization problem is defined as:

$$\min_{\beta \in \mathbb{R}^p} \sqrt{\frac{1}{n}\sum_{i=1}^n (y_i - x_i'\beta)^2} + \frac{\lambda}{n}\|\beta\|_1$$

This transformation is mathematically profound because it alters the scaling of the loss function. In the standard Lasso, the gradient of the loss function (the "score") scales linearly with $\sigma$. By taking the square root, the scale of the noise cancels out in the first-order optimality conditions. This makes the choice of the tuning parameter $\lambda$ independent of $\sigma$, a property referred to as "pivotality."

Theoretical Performance and Pivotality

The authors demonstrate that the Square-root Lasso achieves near-oracle performance. Specifically, it attains a convergence rate of $\sigma \sqrt{(s/n) \log p}$ in the prediction norm. This matches the theoretical performance of the "infeasible Lasso"—a theoretical benchmark where the researcher is assumed to know the true value of $\sigma$ perfectly.

Beyond pivotality, the Square-root Lasso offers enhanced robustness. While many high-dimensional estimators require the noise to be Gaussian or sub-Gaussian, the Square-root Lasso remains effective under much milder moment restrictions. This makes it suitable for datasets with heavy-tailed or asymmetric noise distributions, provided they have finite variance.

Computational Implementation via Conic Programming

Despite the square-root transformation, the objective function remains globally convex, ensuring that the global optimum can be found reliably. The authors show that the Square-root Lasso can be formulated as a Second-Order Cone Program (SOCP), a well-understood class of convex optimization problems.

This formulation allows the use of efficient, scalable algorithms:

  1. Interior-Point Methods: Reliable for small to medium-sized problems.
  2. First-Order Methods: Such as Template for First-Order Conic Solvers (TFOCS), which are better suited for very large-scale applications.
  3. Coordinate-wise Search: Specialized algorithms that can further reduce computational overhead.

Simulation Evidence

The methodology was validated through extensive Monte Carlo simulations. The authors tested the estimator against various noise distributions, including standard Gaussian, Student’s $t(4)$ (representing heavy-tailed noise), and asymmetric exponential noise. They also utilized different design matrices, such as Toeplitz correlation structures, to simulate realistic feature dependencies.

Key findings from these simulations include:

  • Performance Parity: The Square-root Lasso performed nearly identically to the infeasible Lasso across all tested noise levels.
  • Post-Lasso Refinement: The authors explored a "Post Square-root Lasso" approach, where the estimator is used for feature selection, followed by Ordinary Least Squares (OLS) on the selected features. This two-stage process was found to be highly effective at removing the shrinkage bias inherent in $\ell_1$ methods.
  • Efficiency: The conic programming approach proved to be computationally competitive with standard Lasso implementations, maintaining performance as the dimensionality $p$ increased.

Conclusion

The Square-root Lasso represents a significant advancement in sparse recovery. By providing a pivotal method that does not require knowledge of the noise scale, it simplifies the tuning process and increases the reliability of high-dimensional regressions in real-world scenarios where $\sigma$ is unknown. Its robustness to non-Gaussian noise and its formulation as a tractable conic program make it a versatile tool for modern data science. Future work may extend this pivotal framework to more complex models, including nonparametric regression and instrumental variable analysis.

Summary updated

Abstract

We propose a pivotal method for estimating high-dimensional sparse linear regression models, where the overall number of regressors p is large, possibly much larger than n, but only s regressors are significant. The method is a modification of the lasso, called the square-root lasso. The method is pivotal in that it neither relies on the knowledge of the standard deviation σ nor does it need to pre-estimate σ. Moreover, the method does not rely on normality or sub-Gaussianity of noise. It achieves near-oracle performance, attaining the convergence rate σ{(s/n) log p}-super-1/2 in the prediction norm, and thus matching the performance of the lasso with known σ. These performance results are valid for both Gaussian and non-Gaussian errors, under some mild moment restrictions. We formulate the square-root lasso as a solution to a convex conic programming problem, which allows us to implement the estimator using efficient algorithmic methods, such as interior-point and first-order methods. Copyright 2011, Oxford University Press.
BibTeX
@inproceedings{belloni2011square,
  author = {Alexandre Belloni and Victor Chernozhukov and Lei Wang},
  title = {{Square-root lasso: pivotal recovery of sparse signals via conic programming}},
  booktitle = {Biometrika},
  year = {2011},
  doi = {10.1093/biomet/asr043},
}
Figure