Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming

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$ or 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.

References in corpus (5)

• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• Asymptotic properties of bridge estimators in sparse high-dimensional regression models
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• High-dimensional generalized linear models and the lasso
• Aggregation for Gaussian regression

Cited by in corpus (156)

• On asymptotically optimal confidence regions and tests for high-dimensional models
• On Gridless Sparse Methods for Line Spectral Estimation From Complete and Incomplete Data
• Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors
• Robust Wasserstein Profile Inference and Applications to Machine Learning
• Asymptotic normality and optimalities in estimation of large Gaussian graphical models
• Robust subspace clustering
• High-Dimensional Inference: Confidence Intervals, $p$-Values and R-Software hdi
• Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
• Valid Post-Selection and Post-Regularization Inference: An Elementary, General Approach
• Weighted SPICE: A Unifying Approach for Hyperparameter-Free Sparse Estimation
• Pivotal estimation via square-root Lasso in nonparametric regression
• High-dimensional instrumental variables regression and confidence sets
• Noisy low-rank matrix completion with general sampling distribution
• Confidence intervals for high-dimensional inverse covariance estimation
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression
• Beyond Low Rank + Sparse: Multi-scale Low Rank Matrix Decomposition
• Robust Subjective Visual Property Prediction from Crowdsourced Pairwise Labels
• A Note on the SPICE Method
• High-dimensional inference in misspecified linear models
• A Practical Scheme and Fast Algorithm to Tune the Lasso With Optimality Guarantees
• Sparse CCA: Adaptive Estimation and Computational Barriers
• Linear Hypothesis Testing in Dense High-Dimensional Linear Models
• Double/Debiased Machine Learning for Treatment and Causal Parameters
• Goodness of fit tests for high-dimensional linear models
• Ridge regression and asymptotic minimax estimation over spheres of growing dimension
• Spike-and-Slab Meets LASSO: A Review of the Spike-and-Slab LASSO
• Online Hyperparameter-Free Sparse Estimation Method
• Successive Concave Sparsity Approximation for Compressed Sensing
• Prediction error of cross-validated Lasso
• Significance testing in non-sparse high-dimensional linear models
• A General Theory of Hypothesis Tests and Confidence Regions for Sparse High Dimensional Models
• Limitations of Deep Learning for Inverse Problems on Digital Hardware
• Estimating the error variance in a high-dimensional linear model
• Selective inference with a randomized response
• Sparse HP Filter: Finding Kinks in the COVID-19 Contact Rate
• Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression
• Trust, but verify: benefits and pitfalls of least-squares refitting in high dimensions
• Contact Tracing Enhances the Efficiency of COVID-19 Group Testing
• The Gaussian min-max theorem in the Presence of Convexity
• Scaled Sparse Linear Regression
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• Confidence regions for high-dimensional generalized linear models under sparsity
• DOA Estimation in Partially Correlated Noise Using Low-Rank/Sparse Matrix Decomposition
• Sparse structures with LASSO through Principal Components: forecasting GDP components in the short-run
• Pivotal Estimation via Self-Normalization for High-Dimensional Linear Models with Error in Variables
• Solution Paths of Variational Regularization Methods for Inverse Problems
• Non-convex Global Minimization and False Discovery Rate Control for the TREX
• Uniformly Valid Post-Regularization Confidence Regions for Many Functional Parameters in Z-Estimation Framework
• Confidence Intervals for Low-Dimensional Parameters in High-Dimensional Linear Models
• Learning Heteroscedastic Models by Convex Programming under Group Sparsity
• Asymptotically Exact Error Analysis for the Generalized ${\ell }_2^2$-LASSO
• Reluctant Interaction Modeling
• On estimation of the diagonal elements of a sparse precision matrix
• Multivariate Distributionally Robust Convex Regression under Absolute Error Loss
• An Overview on the Estimation of Large Covariance and Precision Matrices
• Double Machine Learning for Partially Linear Mixed-Effects Models with Repeated Measurements
• Learning High-dimensional Gaussian Graphical Models under Total Positivity without Adjustment of Tuning Parameters
• A Projection Based Conditional Dependence Measure with Applications to High-dimensional Undirected Graphical Models
• Proximal Alternating Penalty Algorithms for Constrained Convex Optimization
• A study on tuning parameter selection for the high-dimensional lasso
• Dual Extrapolation for Sparse Generalized Linear Models
• The Geometry of Adversarial Training in Binary Classification
• Doubly Robust Data-Driven Distributionally Robust Optimization
• Sharp Oracle Inequalities for Square Root Regularization
• A Survey of Tuning Parameter Selection for High-dimensional Regression
• The Noise Collector for sparse recovery in high dimensions
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• A sparse semismooth Newton based proximal majorization-minimization algorithm for nonconvex square-root-loss regression problems
• Confidence Intervals for High-Dimensional Linear Regression: Minimax Rates and Adaptivity
• Quantile universal threshold for model selection
• Correcting for unknown errors in sparse high-dimensional function approximation
• Convex programming approach to robust estimation of a multivariate Gaussian model
• Gaussian Graphical Model Estimation with False Discovery Rate Control
• Optimal tuning-free convex relaxation for noisy matrix completion
• Bias-Aware Inference in Regularized Regression Models
• High-dimensional semi-supervised learning: in search for optimal inference of the mean
• PANDA: AdaPtive Noisy Data Augmentation for Regularization of Undirected Graphical Models
• Fast signal recovery from quadratic measurements
• Robust sketching for multiple square-root LASSO problems
• Tuned Regularized Estimators for Linear Regression via Covariance Fitting
• Sparse Poisson Regression with Penalized Weighted Score Function
• A Survey of Estimation Methods for Sparse High-dimensional Time Series Models
• On Fast Convergence of Proximal Algorithms for SQRT-Lasso Optimization: Don't Worry About Its Nonsmooth Loss Function
• Testing High Dimensional Mean Under Sparsity
• High dimensional regression and matrix estimation without tuning parameters
• Nonparametric Heterogeneous Treatment Effect Estimation in Repeated Cross Sectional Designs
• Minimax density estimation for growing dimension
• Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing
• Support recovery and sup-norm convergence rates for sparse pivotal estimation
• The Benefit of Group Sparsity in Group Inference with De-biased Scaled Group Lasso
• Ultra high dimensional generalized additive model: Unified Theory and Methods
• Tuning Free Orthogonal Matching Pursuit
• High-Dimensional Screening Using Multiple Grouping of Variables
• Treatment Effect Estimation with Observational Network Data using Machine Learning
• Optimal Statistical Inference for Individualized Treatment Effects in High-dimensional Models
• Sequential scaled sparse factor regression
• Online Learning for Distribution-Free Prediction
• Detection and estimation of parameters in high dimensional multiple change point regression models via ${\ell }_1/{\ell }_0$ regularization and discrete optimization
• Scaled minimax optimality in high-dimensional linear regression: A non-convex algorithmic regularization approach
• The flare Package for High Dimensional Linear Regression and Precision Matrix Estimation in R
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
• Chi-square and normal inference in high-dimensional multi-task regression
• Pivotal Auto-Encoder via Self-Normalizing ReLU
• Approximation of Functions: Optimal Sampling and Complexity
• The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit
• Inference on the Change Point for High Dimensional Dynamic Graphical Models
• Oracle inequalities for square root analysis estimators with application to total variation penalties
• Graph Estimation for Matrix-variate Gaussian Data
• Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery
• Tuning-Free Heterogeneity Pursuit in Massive Networks
• On Quadratic Convergence of DC Proximal Newton Algorithm for Nonconvex Sparse Learning in High Dimensions
• Signal Recovery in Perturbed Fourier Compressed Sensing
• New insights for the multivariate square-root lasso
• Structural Change in Sparsity
• An Inexact Augmented Lagrangian Method for Second-order Cone Programming with Applications
• On Regularized Square-root Regression Problems: Distributionally Robust Interpretation and Fast Computations
• Wilcoxon-type Multivariate Cluster Elastic Net
• Asymptotic normality in linear regression with approximately sparse structure
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
• Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees
• Robust Inference for High-Dimensional Linear Models via Residual Randomization
• A Simple Correction Procedure for High-Dimensional Generalized Linear Models with Measurement Error
• A proximal MM method for the zero-norm regularized PLQ composite optimization problem
• L1 penalized LAD estimator for high dimensional linear
• Imputation for High-Dimensional Linear Regression
• The False Positive Control Lasso
• Signal and Noise Statistics Oblivious Sparse Reconstruction using OMP/OLS
• Oracle inequalities for sign constrained generalized linear models
• High-Dimensional Semiparametric Selection Models: Estimation Theory with an Application to the Retail Gasoline Market
• Constraints and Conditions: the Lasso Oracle-inequalities
• yaglm: a Python package for fitting and tuning generalized linear models that supports structured, adaptive and non-convex penalties
• High-dimensional inference robust to outliers with l1-norm penalization
• Adaptive posterior convergence in sparse high dimensional clipped generalized linear models
• PAC-Bayesian aggregation of affine estimators
• Thresholding Greedy Pursuit for Sparse Recovery Problems
• Testing Endogeneity with High Dimensional Covariates
• Improved bounds for Square-Root Lasso and Square-Root Slope
• Robust-to-outliers square-root LASSO, simultaneous inference with a MOM approach
• What needles do sparse neural networks find in nonlinear haystacks
• Learning Gaussian DAGs from Network Data
• A proximal dual semismooth Newton method for computing zero-norm penalized QR estimator
• Iteratively Reweighted ${\ell }_1$-Penalized Robust Regression
• Inference on the change point in high dimensional time series models via plug in least squares
• Approximate Representer Theorems in Non-reflexive Banach Spaces
• Learning sparse linear dynamic networks in a hyper-parameter free setting
• Contact Tracing Information Improves the Performance of Group Testing Algorithms
• Worst possible sub-directions in high-dimensional models
• Fast and Accurate Graph Learning for Huge Data via Minipatch Ensembles
• A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
• Adaptive Discrete Smoothing for High-Dimensional and Nonlinear Panel Data
• Inference robust to outliers with l1-norm penalization
• High-dimensional regression with unknown variance
• High Dimensional Tests for Functional Networks of Brain Anatomic Regions
• Estimating the Penalty Level of ${\ell }_1$-minimization via Two Gaussian Approximation Methods
• A proximal-proximal majorization-minimization algorithm for nonconvex tuning-free robust regression problems