SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax

By E.J. Candes, Weijie Su. 2015

150 citations recorded by the source corpus.

We consider high-dimensional sparse regression problems in which we observe $y = X \beta + z$, where $X$ is an $n \times p$ design matrix and $z$ is an $n$-dimensional vector of independent Gaussian errors, each with variance $\sigma^2$. Our focus is on the recently introduced SLOPE estimator ((Bogdan et al., 2014)), which regularizes the least-squares estimates with the rank-dependent penalty $\sum_{1 \le i \le p} \lambda_i |\hat \beta|_{(i)}$, where $|\hat \beta|_{(i)}$ is the $i$th largest magnitude of the fitted coefficients. Under Gaussian designs, where the entries of $X$ are i.i.d.~$\mathcal{N}(0, 1/n)$, we show that SLOPE, with weights $\lambda_i$ just about equal to $\sigma \cdot \Phi^{-1}(1-iq/(2p))$ ($\Phi^{-1}(\alpha)$ is the $\alpha$th quantile of a standard normal and $q$ is a fixed number in $(0,1)$) achieves a squared error of estimation obeying \[ \sup_{\| \beta\|_0 \le k} \,\, \mathbb{P} \left(\| \hat{\beta}_{\text{SLOPE}} - \beta \|^2 > (1+\epsilon) \, 2\sigma^2 k \log(p/k) \right) \longrightarrow 0 \] as the dimension $p$ increases to $\infty$, and where $\epsilon > 0$ is an arbitrary small constant. This holds under a weak assumption on the $\ell_0$-sparsity level, namely, $k/p \rightarrow 0$ and $(k\log p)/n \rightarrow 0$, and is sharp in the sense that this is the best possible error any estimator can achieve. A remarkable feature is that SLOPE does not require any knowledge of the degree of sparsity, and yet automatically adapts to yield optimal total squared errors over a wide range of $\ell_0$-sparsity classes. We are not aware of any other estimator with this property.

Subfields: Computational Mechanics, Numerical Analysis, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Numerical Analysis

In Statistics and Probability

Citations in the corpus

Regularization, sparse recovery, and median-of-means tournaments (2017, result): “rnament procedure and the technical machinery we require, let us describe in more detail the two applications mentioned previously, both of which originating in sparse recovery: lasso, and slope(see, [1, 3, 14, 15]). The two are regularized empirical risk minimization procedures in Rd, and we would ”
Learning Games and Rademacher Observations Losses (2015, methodology): “(40) (Proof in Appendix, Subsection 9.14) Constraint (ii) onq is interesting in the light of the properties of SLOPE (Bogdan et al., 2015; Su & Candès, 2015).”
Debiasing the lasso: Optimal sample size for Gaussian designs (2015, methodology): “ularly interesting. In particular, we construct a thresholded Lasso estimator that is minimax optimal up to a factor (1 + o n(1)) (an alternative approach to the same problem was recently proposed in [SC15]). 6 Section2discusses relations with earlier work in this area. Outlines of the proofs of the”
Familywise error rate control via knockoffs (2015, background): “, 2004) and sorted-`1-penalized estimation (Bogdan et al., 2015; Su and Candès, 2015), can be used instead as long as they obey the sufficiency and antisymmetry properties defined therein.”
On Regularizing Rademacher Observation Losses (2016, methodology): “Modulo some assumptions, SLOPE yields a control the false discovery rate (FDR) — i.e., negligible coefficients in the "true” linear model θ∗ that are found significant in the learned θ —.”
Robust machine learning by median-of-means: Theory and practice (2017, methodology): “SLOPE is an extension of the LASSO that was introduced in [16, 84].”