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

Abstract

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