SLOPE IS ADAPTIVE TO UNKNOWN SPARSITY AND ASYMPTOTICALLY MINIMAX

• Published in: The Annals of statistics 2016-06, Vol.44 (3), p.1038-1068
• Main Authors: Su, Weijie, Candès, Emmanuel
• Format: Article
• Language: English
• Subjects: Asymptotic methods; Mathematical problems; Measurement errors; Normal distribution; Regression analysis; Sparsity; Studies
• ISSN: 0090-5364; 2168-8966
• DOI: 10.1214/15-aos1397

We consider high-dimensional sparse regression problems in which we observe y = Xβ + z, where X is an n × p design matrix and z is an n-dimensional vector of independent Gaussian errors, each with variance σ². Our focus is on the recently introduced SLOPE estimator [Ann. Appl. Stat. 9 (2015) 1103-1140], which regularizes the least-squares estimates with the rank-dependent penalty${\Sigma _{1 \leqslant i \leqslant {p^{{\lambda _i}}}|\hat \beta {|_{(i)}}$, |β̂|(i) is the ith largest magnitude of the fitted coefficients. Under Gaussian designs, where the entries of X are i.i.d. N(0,1/n), we show that SLOPE, with weights λi just about equal to σ· Φ⁻¹ (1 — iq/(2p)) [Φ⁻¹(α) is the orth quantile of a standard normal and q is a fixed number in (0,1)] achieves a squared error of estimation obeying sup ℙ(||β̂SLOPE - β||² > (1 + ε)2σ²klog(p/k))→0 ||β||₀≤k as the dimension p increases to ∞, and where ε > 0 is an arbitrary small constant. This holds under a weak assumption on the l₀-sparsity level, namely, k/p → 0 and (k log p)/n → 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 l₀-sparsity classes. We are not aware of any other estimator with this property.