Source-linked AI summary
SLOPE - Adaptive variable selection via convex optimization
Małgorzata Bogdan, Ewout van den Berg, Chiara Sabatti, Weijie Su, Emmanuel J. Candès
TL;DR
The paper addresses variable selection in high-dimensional linear models, especially when false discoveries matter for scientific inference. It introduces SLOPE, a convex estimator using a rank-weighted sorted ℓ1 penalty, and reports FDR control under orthogonal designs with promising behavior more generally. The paper also identifies important limitations and open problems concerning nonorthogonal designs and regularization-sequence adjustments.
Problem
High-dimensional model selection requires identifying relevant predictors while controlling the expected proportion of irrelevant selections, rather than targeting prediction error alone.
Method
SLOPE estimates regression coefficients by minimizing squared residual error plus a sorted ℓ1 penalty whose decreasing weights depend on coefficient rank.
Results
Under orthogonal designs, SLOPE controls FDR at the nominal level, while simulations show FDR close to nominal when p > n and the true model is sparse, with large power and accurate prediction.
Takeaways & Limitations
SLOPE provides a computationally tractable model-selection proposal with robust algorithms and promising FDR-control properties for general designs.
Takeaways & Limitations
The adjustment heuristic has only approximate FDR-control support in simulations, and further research is needed to understand it and develop more efficient alternatives.
Abstract
from arXiv · showhide
We introduce a new estimator for the vector of coefficients $β$ in the linear model $y=Xβ+z$, where $X$ has dimensions $n\times p$ with $p$ possibly larger than $n$. SLOPE, short for Sorted L-One Penalized Estimation, is the solution to \[\min_{b\in\mathbb{R}^p}\frac{1}{2}\Vert y-Xb\Vert _{\ell_2}^2+λ_1\vert b\vert _{(1)}+λ_2\vert b\vert_{(2)}+\cdots+λ_p\vert b\vert_{(p)},\] where $λ_1\geλ_2\ge\cdots\geλ_p\ge0$ and $\vert b\vert_{(1)}\ge\vert b\vert_{(2)}\ge\cdots\ge\vert b\vert_{(p)}$ are the decreasing absolute values of the entries of $b$. This is a convex program and we demonstrate a solution algorithm whose computational complexity is roughly comparable to that of classical $\ell_1$ procedures such as the Lasso. Here, the regularizer is a sorted $\ell_1$ norm, which penalizes the regression coefficients according to their rank: the higher the rank - that is, stronger the signal - the larger the penalty. This is similar to the Benjamini and Hochberg [J. Roy. Statist. Soc. Ser. B 57 (1995) 289-300] procedure (BH) which compares more significant $p$-values with more stringent thresholds. One notable choice of the sequence $\{λ_i\}$ is given by the BH critical values $λ_{\mathrm {BH}}(i)=z(1-i\cdot q/2p)$, where $q\in(0,1)$ and $z(α)$ is the quantile of a standard normal distribution. SLOPE aims to provide finite sample guarantees on the selected model; of special interest is the false discovery rate (FDR), defined as the expected proportion of irrelevant regressors among all selected predictors. Under orthogonal designs, SLOPE with $λ_{\mathrm{BH}}$ provably controls FDR at level $q$. Moreover, it also appears to have appreciable inferential properties under more general designs $X$ while having substantial power, as demonstrated in a series of experiments running on both simulated and real data.
Introduction.
The paper frames variable selection as a high-dimensional scientific inference problem where identifying relevant predictors matters more than prediction alone. It introduces a methodology aimed at selecting important variables with finite-sample confidence statements.
- Scientific studies may prioritize correctly identifying functional variants over minimizing prediction error, because false discoveries can waste substantial verification resources.
- The proposed methodology is intended to privilege correct model selection and support inferential statements about the validity of selected variables.
- The stated goal is to select important variables while controlling the expected proportion of irrelevant variables among those selected.
1. Sorted L-One Penalized Estimation (SLOPE).
SLOPE extends penalized regression with rank-dependent penalties designed to adapt model selection to signal strength while targeting finite-sample FDR control. Under orthogonal designs it connects to BH, remains convex and computationally tractable, and simulations show a favorable FDR–power–prediction trade-off.
- Adaptive penalization and multiple testing in orthogonal designs: SLOPE recasts orthogonal regression as a multiple-testing problem and uses BH-style adaptive thresholds to select variables.The BH threshold depends on the ordered statistics and adapts to the sparsity and magnitude of true signals.
- SLOPE: Unlike Lasso’s uniform penalty, SLOPE assigns different penalties according to the ranked absolute coefficient magnitudes.Its sorted ℓ1 structure is similar to BH but is not exactly equivalent to BH step-up or step-down procedures.
- Adaptive penalization and multiple testing in orthogonal designs: Under orthogonal designs, SLOPE with BH-calibrated penalties provably controls FDR at the target level q.The theorem applies to the procedure that rejects hypotheses corresponding to nonzero SLOPE coefficient estimates.
- SLOPE: SLOPE is a convex, computationally tractable extension of the Lasso whose cost is roughly comparable to classical ℓ1 procedures.Its decaying penalty sequence provides adaptivity while remaining usable for large-dimensional problems and arbitrary design matrices.
- A first illustrative simulation: The method’s detectability depends on signal strength: at the examined value, sparse nonzero means are barely distinguishable from the largest null statistics.This setting is described as lying near the limits of detectability for sparse mixtures.
- A first illustrative simulation: In simulations, SLOPE maintained FDR at 0.1 while power increased from 45% to 70% across the explored sparsity range.Bonferroni-controlled Lasso had power below 45%, whereas cross-validation achieved greater power with FDR averaging 80%; SLOPE also had lower prediction error than Lasso–λCV across considered sparsity levels.
2. Algorithms.
SLOPE is solved with proximal-gradient methods whose key computational step is the prox of the sorted ℓ1 norm. A stack-based FastProxSL1 implementation computes this prox in O(p) time after sorting, yielding an overall cost roughly comparable to the Lasso.
- 2.1. Proximal gradient algorithms.: SLOPE is formulated as minimizing a smooth quadratic residual term plus a nonsmooth sorted ℓ1 penalty.Proximal-gradient methods iteratively approximate the smooth term and apply the prox of the penalty.
- 2.1. Proximal gradient algorithms.: The proximal-gradient update combines a gradient step on the residual objective with the sorted-ℓ1 prox.The update uses step sizes t_k and converges under conditions such as t_k < 2/∥X∥2 or backtracking line search.
- 2.2. Fast prox algorithm.: The sorted-ℓ1 prox can be computed in nearly the time required for soft thresholding: O(p) after an O(p log p) sorting step.The implementation first exploits sign and permutation invariance to sort the input, then applies a linear-time algorithm.
- 2.2. Fast prox algorithm.: FastProxSL1 repeatedly averages violating subsequences until monotonicity holds, at which point the solution is obtained in closed form.The algorithm terminates in at most p steps, and each update preserves the prox value.
- 2.3. Related algorithms.: A stack-based implementation merges each tuple at most once, giving O(p) complexity and practical implementations in C, Matlab, and R.The authors also provide implementations through the SLOPE and TFOCS packages.
- 2.3. Related algorithms.: The prox algorithm is connected to the pool adjacent violators algorithm for isotonic regression.The connection arises because the prox computation enforces monotonic fitted values through averaging adjacent violating blocks.
3. Results.
Across simulations and genetics data, SLOPE generally maintained FDR near its target while providing substantial, often more stable power than competing procedures. Adjusted regularization improved FDR control under Gaussian designs, but performance remained sensitive to signal strength and design assumptions.
- 3. Results.: SLOPE kept FDR at the nominal level for k ≤40 and remained close to it for k ≤80 under known or estimated variance components.The estimation procedure had no influence on SLOPE in these simulations.
- 3. Results.: BH had substantially lower power than SLOPE and more variable false discovery proportions in correlated multiple-testing simulations.For q = 0.1 and k = 50, BH made no rejections in approximately 26% of cases and had mean FDP 0.16 conditional on R > 0.
- 3. Results.: Gaussian designs caused both Lasso–λBonf and SLOPE–λBH to lose targeted error-rate control as k increased, especially when p/n was larger.The authors relate this pattern to stronger shrinkage effects and larger empirical correlations.
- 3. Results.: The proposed scaled-SLOPE algorithm converged quickly, with iterations typically decreasing the estimated noise level and increasing the number of selected variables.At convergence, some signals remained undetected and the noise estimate was slightly overestimated.
- 3. Results.: Under deviations from the assumed regression model, scaled SLOPE kept FDR close to nominal while power was somewhat diminished.Laplace errors produced results almost identical to those under normal errors.
- 3. Results.: In the genetics example, all methods selected a common core of 8 of 14 previously described variants, while total selections ranged from 15 to 119.Cross-validated Lasso selected 90 variables not selected by any other method and offered no FDR control.
4. Discussion.
The discussion presents SLOPE as promising for model selection while identifying unresolved theoretical and practical boundaries. Open questions concern regularization choices, sparsity, covariance structures, and further validation.
- Discussion: SLOPE controls FDR under orthogonal designs and can keep FDR close to nominal levels for sparse models when p > n.The simulations also report large power and accurate prediction.
- Discussion: Heuristics for choosing λ can support FDR control for Gaussian and other random designs, but no definitive sequence is established for general designs.Further theory is needed to identify sequences with provable FDR control.
- Discussion: The paper considers fixed regularizing sequences {λi}; data-driven selection with desirable statistical properties remains an open question.The discussion contrasts this with later work addressing a related Lasso problem when n ≥ p.
- Discussion: SLOPE, like other ℓ1 convex optimization methods, has limits on the signal sparsity it can handle.The paper notes that analogous limitations pertain to the Lasso.
- Discussion: The class of unknown covariance matrices for which SLOPE is effective remains theoretically unresolved.In a simple ANOVA model, SLOPE controls FDR even when unknown variance components are estimated.
- Discussion: The authors conclude that SLOPE is a computationally tractable convex program with promising statistical applications and motivates further research.The conclusion frames the work as an initial contribution rather than a complete resolution of the open problems.
M. Bogdan Department of Mathematics Wroc law University of Technology 50-370 Wroc law Poland
The listed authors are affiliated with Stanford University and IBM’s T.J. Watson Research Center.
- C. Sabatti is affiliated with Stanford University’s Department of Health Research and Policy, Division of Biostatistics, and Department of Statistics.
- The affiliations span academic biostatistics and statistics research at Stanford and human language technologies at IBM.
- E. van den Berg is affiliated with the Human Language Technologies group at IBM T.J. Watson Research Center.