Statistical estimation and testing via the sorted L1 norm

Abstract

We introduce a novel method for sparse regression and variable selection, which is inspired by modern ideas in multiple testing. Imagine we have observations from the linear model y = X beta + z, then we suggest estimating the regression coefficients by means of a new estimator called SLOPE, which is the solution to minimize 0.5 ||y - Xb\|_2^2 + lambda_1 |b|_(1) + lambda_2 |b|_(2) + ... + lambda_p |b|_(p); here, lambda_1 >= λ_2 >= ... >= λ_p >= 0 and |b|_(1) >= |b|_(2) >= ... >= |b|_(p) is the order statistic of the magnitudes of b. The regularizer is a sorted L1 norm which penalizes the regression coefficients according to their rank: the higher the rank, the larger the penalty. This is similar to the famous BHq procedure [Benjamini and Hochberg, 1995], which compares the value of a test statistic taken from a family to a critical threshold that depends on its rank in the family. SLOPE is a convex program and we demonstrate an efficient algorithm for computing the solution. We prove that for orthogonal designs with p variables, taking lambda_i = F^{-1}(1-q_i) (F is the cdf of the errors), q_i = iq/(2p), controls the false discovery rate (FDR) for variable selection. When the design matrix is nonorthogonal there are inherent limitations on the FDR level and the power which can be obtained with model selection methods based on L1-like penalties. However, whenever the columns of the design matrix are not strongly correlated, we demonstrate empirically that it is possible to select the parameters lambda_i as to obtain FDR control at a reasonable level as long as the number of nonzero coefficients is not too large. At the same time, the procedure exhibits increased power over the lasso, which treats all coefficients equally. The paper illustrates further estimation properties of the new selection rule through comprehensive simulation studies.

Cited by in corpus (27)

• SLOPE - Adaptive variable selection via convex optimization
• High-Dimensional Inference: Confidence Intervals, $p$-Values and R-Software hdi
• Sparse Portfolio Selection via the sorted ${\ell }_1$-Norm
• Forward - Backward Greedy Algorithms for Atomic Norm Regularization
• Estimating Structured Vector Autoregressive Model
• Nonconvex Sorted ${\ell }_1$ Minimization for Sparse Approximation
• Sparse Estimation with Strongly Correlated Variables using Ordered Weighted L1 Regularization
• SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax
• Discussion of Big Bayes Stories and BayesBag
• Fast OSCAR and OWL Regression via Safe Screening Rules
• High-dimensional robust regression and outliers detection with SLOPE
• Graph-based regularization for regression problems with alignment and highly-correlated designs
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• The Strong Screening Rule for SLOPE
• Solving L1-regularized SVMs and related linear programs: Revisiting the effectiveness of Column and Constraint Generation
• An $O(n\log (n))$ Algorithm for Projecting Onto the Ordered Weighted ${\ell }_1$ Norm Ball
• Error bounds for sparse classifiers in high-dimensions
• Decreasing Weighted Sorted ${\ell }_1$ Regularization
• Asymptotic behavior of a nonautonomous evolution equation governed by a quasi-nonexpansive operator
• An Exact Solution Path Algorithm for SLOPE and Quasi-Spherical OSCAR
• HALO: Learning to Prune Neural Networks with Shrinkage
• Approximate Cross-validation: Guarantees for Model Assessment and Selection
• Improved error rates for sparse (group) learning with Lipschitz loss functions
• Characterizing the SLOPE Trade-off: A Variational Perspective and the Donoho-Tanner Limit
• Sparse Optimization Problem with s-difference Regularization
• Network Inference by Learned Node-Specific Degree Prior
• Learning Games and Rademacher Observations Losses