Source-linked AI summary
Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
Alexandre Belloni, Victor Chernozhukov, Lie Wang
TL;DR
The paper studies sparse high-dimensional regression with potentially unknown noise scale and non-normal errors. It introduces the pivotal square-root lasso and a conic-programming formulation, showing near-oracle performance comparable to lasso with known σ while imposing growth restrictions for Gaussian-like non-Gaussian results.
Problem
Sparse regression may have p much larger than n, while the unknown noise scale σ makes lasso penalty selection difficult, particularly when p ≫ n.
Method
The square-root lasso modifies lasso to use a σ-independent penalty and formulates the globally convex estimator as a second-order-cone program.
Results
The estimator achieves near-oracle rates and matches lasso performance with unknown σ, with validity extending beyond normality under suitable conditions.
Takeaways & Limitations
Efficient conic-programming algorithms make pivotal sparse estimation computationally attractive without pre-estimating σ.
Takeaways & Limitations
Gaussian-like asymptotic conclusions for non-Gaussian errors require stronger restrictions on the growth of p relative to n.
Abstract
from arXiv · showhide
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 $σ$ or 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\}^{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.
1. Introduction
The paper addresses sparse linear regression when p may exceed n and the significant regressors are unknown, proposing a square-root lasso that avoids estimating σ while retaining near-oracle performance. It also provides a convex conic formulation for efficient computation.
- Problem: Sparse estimation is considered in a high-dimensional regression model where p may exceed n, but β0 has only s significant regressors.The support T of significant regressors is unknown.
- Problem: OLS is inconsistent when p > n, whereas lasso can restore consistency under mild conditions through ℓ1 penalization.The lasso is also computationally attractive because it minimizes a structured convex function.
- Method: The square-root lasso eliminates the need to know or pre-estimate the noise standard deviation σ.Its penalty level is independent of σ, making the estimator pivotal with respect to this parameter.
- Results: Under suitable design and error conditions, the square-root lasso achieves near-oracle rates and matches lasso performance even when σ is unknown.The result extends beyond normal errors under suitable conditions and holds with probability approaching 1 −α.
- Computation: The square-root lasso remains globally convex despite the square-root criterion, enabling a second-order-cone formulation and efficient interior-point or first-order algorithms.Conic programming supplies the computational formulation used for implementation.
2. The choice of penalty level
The penalty level is chosen to dominate a pivotal score, eliminating dependence on the unknown noise scale. Exact, semi-exact, and asymptotic options support Gaussian and suitably moment-controlled non-Gaussian errors.
- General principle and heuristics: The penalty level λ is set above a scaled maximal score, λ ⩾ cΛ, so it dominates estimation noise with high probability.The score summarizes estimation noise, and the smallest dominating penalty is preferred for efficiency.
- General principle and heuristics: The square-root transformation makes the maximal score, and therefore the penalty level, pivotal with respect to σ.Unlike the lasso score, the square-root lasso score does not depend on the unknown standard deviation.
- Formal penalty choices: When the error distribution is known, λ can be set from a conditional quantile of Λ; under an error family, upper quantile bounds provide semi-exact or asymptotic choices.The exact option is simulated from the conditional distribution, while the asymptotic option is easier to compute.
- Gaussian case: Under Gaussian errors, the exact and asymptotic options implement λ ⩾ cΛ with exact or asymptotic probability 1 − α.The asymptotic option uses λ = cn^1/2Φ−1(1 − α/2p) under Condition G.
- Non-Gaussian case: Under moment and growth conditions, the non-Gaussian options implement λ ⩾ cΛ with probability at least 1 − α − o(α).The allowed growth of p depends on the number q of bounded moments; larger q permits faster growth.
- Penalty-level properties: The exact and semi-exact penalty magnitudes satisfy an asymptotic upper bound of {2n log(2p/α)}^1/2{1 + o(1)}.This bound is used to state estimation-error guarantees.
3. Finite-sample and asymptotic bounds on the estimation error
Under restricted-eigenvalue and regularization conditions, square-root lasso has finite-sample error bounds and near-oracle convergence rates without known σ or sub-Gaussian noise. The non-Gaussian results require stronger growth restrictions on p relative to n.
- Error bounds: The analysis bounds estimation error in both Euclidean and prediction norms using restricted eigenvalues of the Gram matrix.The prediction norm directly depends on the Gram matrix, while the error vector is constrained to a restricted set.
- Design conditions: Restricted eigenvalue conditions can remain viable when p ≥ n, despite the full Gram matrix having zero minimum eigenvalue.Restricted eigenvalues may be bounded away from zero for many fixed and random designs with reasonably general regressor correlation.
- Finite-sample results: Theorem 1 gives a finite-sample bound similar to the lasso bound with known σ and yields the same convergence rates.The theorem assumes λ ⩾ cΛ and imposes an additional growth restriction involving λ and s^1/2.
- Finite-sample results: The additional restriction λs^1/2 < nκ̄_c is the price of unknown σ, but it is mild asymptotically when (s/n) log(p/α) → 0.Unlike the analogous pilot-lasso condition, this restriction is independent of σ.
- Asymptotic results: Under Gaussian errors, restricted eigenvalues, and Condition G, exact or asymptotic penalty choices yield the stated asymptotic bounds when (s/n) log(p/α) → 0.Corollary 2 provides the Gaussian asymptotic result.
- Asymptotic results: Under Conditions RE, M, and R, the asymptotic, exact, or semi-exact choices yield analogous non-Gaussian bounds with probability at least 1 − α − o(α).The non-Gaussian case imposes stronger restrictions on p relative to n than the Gaussian case.
4. Computational properties of square-root lasso
The square-root lasso is reformulated as a second-order conic program with a strongly dual problem. This preserves computational tractability and supports interior-point and first-order algorithms.
- Conic formulation: The square-root lasso optimization problem is equivalent to a conic program with second-order cone constraints.The second-order cone is also called the ice-cream cone.
- Duality: The conic program has a strongly dual formulation, meaning the primal and dual optimal values coincide without a duality gap.Strong duality supports the use of interior-point and first-order conic-programming methods.
- Duality: The dual problem maximizes sample correlation between score variables and outcomes subject to approximate-uncorrelation constraints.Optimal scores equal normalized residuals and help derive sparsity bounds on the estimator.
- Algorithms: The conic formulation enables implementation with interior-point, first-order, and coordinatewise methods, with code provided by the authors.The authors report that square-root lasso runs at least as fast as corresponding lasso implementations in the tested methods.
5. Empirical performance of square-root lasso relative to lasso
The experiments compare infeasible and square-root lasso variants across noise levels, evaluating empirical risk and support-selection errors. Square-root lasso performs comparably to infeasible lasso, while post square-root lasso often performs best.
- Experimental design: The experiments compare four estimators using empirical risk and support-selection measures across varying noise levels.The estimators are infeasible lasso, post infeasible lasso, square-root lasso, and post square-root lasso.
- Experimental design: The simulations use Gaussian and t(4) errors, p = 500 regressors, n = 100 observations, and 1000 repetitions per design.The true coefficient vector has five nonzero entries, σ varies from 0.25 to 3, and regressors have Toeplitz correlation.
- Empirical risk: Across a wide range of σ, square-root lasso with unknown σ performs comparably to infeasible lasso with known σ.The empirical-risk comparison is made relative to an oracle estimator that knows the true support.
- Empirical risk: Finite-sample empirical-risk differences arise primarily because square-root lasso has larger shrinkage bias than infeasible lasso.The square-root lasso uses an effectively heavier penalty induced by the residual criterion in place of σ^2.
- Post-estimation performance: Post square-root lasso substantially outperforms both infeasible lasso and square-root lasso, and often outperforms post infeasible lasso.Its advantage is attributed to removing shrinkage bias and having better sparsity properties.
- Non-Gaussian errors: Under t(4) errors, infeasible and square-root lasso performance nearly coincides with performance under Gaussian errors.The authors relate this similarity to their moderate-deviation theoretical results.
- Additional comparisons: Asymmetric noise and highly correlated designs do not change the results qualitatively, while cross-validated lasso performs poorly for model selection.Cross-validated lasso is outperformed by post square-root lasso in empirical risk and by square-root-lasso variants in the reported comparisons.
Supplementary Material
The Supplementary Material extends the paper with complementary penalty analysis, computational discussion, additional simulations, and omitted proof details.
- Supplementary Material: The Supplementary Material analyzes penalty choice using moderate deviations for self-normalizing sums.It also discusses computational aspects and provides additional Monte Carlo experiments.
- Supplementary Material: It includes the omitted part of the proof of Lemma 2 and lists inequalities used in the proofs.
Proofs of Theorems 1 and 2.
The proofs establish error bounds for square-root lasso under prescribed penalty and design conditions, and derive its conic-programming duality. Auxiliary moderate-deviation arguments justify penalty control beyond the Gaussian case.
- Theorem 1: Theorem 1’s proof first places the estimation error in a restricted cone under the prescribed penalty level.The subsequent bounds use convexity, Hölder’s inequality, and the restricted-eigenvalue quantity.
- Theorem 1: Theorem 1’s estimation-error bounds follow by combining the cone relation with restricted-eigenvalue inequalities.The proof concludes once the resulting inequality is solved under the stated penalty condition.
- Theorem 2: The square-root lasso optimization problem is equivalent to a conic-programming formulation, whose dual follows from conic duality.The proof writes the primal in matrix form and derives the dual constraints.
- Theorem 2: The dual constraints imply ||X′a||∞ ≤ λ/n and ||a|| ≤ n^1/2 after using the cone constraint and rescaling.Strong feasibility then yields strong duality.
- Theorem 2: The dual optimality relations identify the dual vector with the normalized residual when the residual norm is positive.
- Auxiliary probability results: The auxiliary arguments control Gaussian and non-Gaussian tail probabilities using union bounds, moment inequalities, moderate deviations, and Chernoff bounds.The non-Gaussian results require moment and growth conditions, while the Gaussian case uses normal tail behavior.
Appendix A. Additional Theoretical Results
The appendix provides complementary penalty-level theory and computational evidence. Under stronger moment and design conditions, asymptotic penalty choices retain theoretical guarantees, while computation remains comparable to lasso.
- Additional theoretical results: The supplementary penalty analysis uses self-normalizing moderate deviations and requires stronger moment assumptions than the main-text analysis.In exchange, these conditions permit weaker growth requirements on p relative to n.
- Penalty choices: The exact and asymptotic penalty choices are λ = cΛF0(1 − α | X) and λ = cn^1/2Φ−1(1 − α/2p), respectively.The exact option uses a conditional quantile of a self-normalized maximum score.
- Penalty guarantees: Under Condition SN, the asymptotic penalty implements λ > cΛ with probability at least 1 − α{1 + o(1)}.Condition SN imposes bounded qth noise moments, bounded design entries, and growth restrictions.
- Penalty guarantees: Combining the supplementary penalty lemma with Theorem 1 yields a high-probability corollary under restricted-eigenvalue, moment, and sparsity-growth conditions.The stated sparsity condition is (s/n) log(p/α) → 0.
- Computational times: Average running times for lasso and square-root lasso are comparable in practical problems across the evaluated computational methods.The appendix reports experiments using the same design, with s = 5 and σ = 1, averaged over 100 simulations.
B.3. Details on Computational Methods.
The section develops computational formulations and algorithms for solving lasso and square-root lasso problems. It emphasizes conic programming, first-order methods, interior-point methods, and componentwise search.
- The lasso and square-root lasso formulations share similarities that support similar computational performance.
- Interior-point methods: Interior-point methods solve the binding conic constraint by barrier regularization and converge through a sequence of interior solutions.
- Both estimators can be formulated as conic programming problems, making several computational methods directly applicable.
- First-order methods: First-order methods exploit structured convex objectives involving a smooth term and a structured, potentially nondifferentiable term.
- Square-root lasso algorithms: For the square-root lasso, conic representations use a second-order cone, while iterative minimization can use soft-thresholding and componentwise updates.
- Computational experiments: The computational experiments compare lasso and square-root lasso across noise distributions and designs, including feasible lasso methods that estimate σ.
C.2. Detailed performance comparison of lasso and square-root lasso.
The experiments compare square-root lasso with infeasible, post, and cross-validated lasso procedures under varied noise and design settings. Results show comparable performance to lasso with known σ, while post square-root lasso performs especially strongly for model selection.
- The experiments use normal, t(4), and asymmetric exponential errors with p = 500, n = 100, five nonzero coefficients, and σ ranging from 0.25 to 3.
- Non-Gaussian errors produce performance very similar to Gaussian errors, while higher covariate correlation increases empirical risk.
- Square-root lasso and post square-root lasso perform relatively close to lasso and post lasso procedures that know σ.
- Cross-validation improves empirical risk by selecting a smaller penalty, but cv-lasso is uniformly dominated by square-root lasso with penalty scaled by 1/2.
- Post cv-lasso performs substantially worse than cv-lasso for model selection, whereas post square-root lasso thoroughly dominates the feasible alternatives considered.
Appendix D. Proofs of Additional Theoretical Results
This appendix supplies technical probability arguments used to control the square-root lasso penalty and establish its asymptotic behavior under moment and design conditions.
- The proofs define slowly varying sequences and Gaussian quantiles to control tail probabilities uniformly over regressors.
- Moderate-deviation and union-bound arguments yield high-probability bounds for the maximal score and related empirical quantities.
- Moment and design conditions control terms involving regressor norms and error moments in the asymptotic bounds.
- The resulting bound is Λ_F0(1 − α | X) ≤ (1 + u_n)(1 + 1/t_n)n^1/2t_n = {1 + o(1)}n^1/2t_n.
Appendix E. Omitted Proofs from the Main Text
This appendix records omitted probability and moment results supporting the paper’s penalty calibration and non-Gaussian theoretical guarantees. The results rely on moderate deviations, moment inequalities, and conditional design bounds.
- Moderate-deviation results provide uniform approximations for normalized empirical scores over regressors under moment restrictions.
- Rosenthal, Von Bahr–Esseen, and related inequalities supply bounds for sums of independent variables across different moment ranges.
- The appendix states assumptions involving finite moments, triangular arrays, and slowly varying sequences for the auxiliary probability results.
- Conditional on the regressors, the technical lemmas establish probability bounds under q-moment conditions and bounded regressor sup norms.