PaperlayerView exact revision on arXiv

Source-linked AI summary

SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax

Weijie Su, Emmanuel Candes

arXiv:1503.08393v3math.STcs.IT

TL;DR

High-dimensional regression raises how testing-based procedures can support estimation under correlated designs. This paper extends the estimation–testing link to linear models and shows that FDR-based procedures can achieve asymptotically optimal estimation while adapting to unknown sparsity.

  • Problem

    In correlated linear models, applying the BHq procedure to least-squares estimates is not known to control FDR and suffers from highly variable false discovery proportions.

  • Method

    The paper extends the link between estimation and testing by studying a procedure originally designed for FDR control in variable selection within a linear model.

  • Results

    FDR estimation is asymptotically minimax over k-sparse signals across a broad sparsity range without knowing k, achieving the best possible mean-square error.

  • Takeaways & Limitations

    The FDR criterion provides a fundamentally correct approach to squared-loss estimation rather than only a multiple-testing problem.

  • Takeaways & Limitations

    The paper does not address how to choose or tune the weight sequence for correlated Gaussian designs or fixed designs.

Abstract

from arXiv · show

We consider high-dimensional sparse regression problems in which we observe $y = X β+ z$, where $X$ is an $n \times p$ design matrix and $z$ is an $n$-dimensional vector of independent Gaussian errors, each with variance $σ^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} λ_i |\hat β|_{(i)}$, where $|\hat β|_{(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 $λ_i$ just about equal to $σ\cdot Φ^{-1}(1-iq/(2p))$ ($Φ^{-1}(α)$ is the $α$th quantile of a standard normal and $q$ is a fixed number in $(0,1)$) achieves a squared error of estimation obeying \[ \sup_{\| β\|_0 \le k} \,\, \mathbb{P} \left(\| \hatβ_{\text{SLOPE}} - β\|^2 > (1+ε) \, 2σ^2 k \log(p/k) \right) \longrightarrow 0 \] as the dimension $p$ increases to $\infty$, and where $ε> 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.

1. Introduction.

SLOPE connects adaptive false-discovery-rate thresholding with sparse regression, using rank-dependent penalties to adapt to unknown sparsity. Under orthogonal and Gaussian designs, it achieves asymptotically minimax squared error under broad sparsity conditions.

  • 1. Introduction.: SLOPE extends the estimation–testing link from orthogonal sequence models to the more general linear regression model.The paper studies SLOPE in sparse regression with Gaussian random designs, beyond the earlier orthogonal setting.
  • 1.1. SLOPE.: SLOPE uses rank-dependent penalization that adapts its threshold to the unknown number of strong signals.Unlike the Lasso’s common threshold, SLOPE penalizes larger estimated coefficients more heavily and lowers the effective threshold when more strong signals are present.
  • 1.3. Random designs.: Under Gaussian designs, SLOPE’s squared loss is at most (1 + o(1)) 2σ^2k log(p/k) with high probability.This matches the minimax lower bound, establishing sharp asymptotic minimaxity over k-sparse signals.
  • 1.2. Orthogonal designs.: 2σ^2k log(p/k) is the fundamental asymptotic squared-loss limit, and SLOPE achieves it without knowing k.The orthogonal-design result holds for every fixed q in (0,1), while the Gaussian-design result uses k/p → 0 and (k log p)/n → 0.
  • 1.3. Random designs.: With BH weights, SLOPE also yields the best possible prediction in the stated asymptotic setting.The paper further connects the estimator’s coefficient-estimation error with its mean-response prediction error.

2. Alternatives to SLOPE?.

The alternatives discussed include non-adaptive Lasso tuning, data-dependent procedures such as SURE, and FDR-thresholding variants. These methods face accuracy, continuity, or generalization limitations relative to SLOPE in the supported settings.

  • 2.1. Other ℓ1 penalized methods.: Non-adaptive Lasso tuning can inflate risk because avoiding false discoveries requires λ at least σ√(2 log p), causing excessive shrinkage bias.The resulting risk inflation does not decrease with increasing sparsity in the discussed regime.
  • 2.1. Other ℓ1 penalized methods.: SLOPE is more accurate than Lasso for strong and moderate signals, with its advantage increasing as sparsity grows.The comparison uses Gaussian design and reports that the pattern is consistent with SLOPE having lower bias at larger k.
  • 2.1. Other ℓ1 penalized methods.: The paper leaves SLOPE behavior unclear when both k/p and n/p converge to positive constants, including what weight sequence would be appropriate.This is presented as an open comparison regime rather than an established failure result.
  • 2.2. Data-driven procedures.: SURE thresholding has larger mean squared error and variability than SLOPE, especially for sparser signals, with particularly dispersed error when k = 1.The cited discussion reports that SURE's risk is infinitely larger than SLOPE's under the global null.
  • 2.3. Variations on FDR thresholding.: FDR hard-thresholding is discontinuous and does not extend well to linear models, whereas SLOPE depends continuously on observations and is designed for regression.The paper links FDR discontinuities to technical difficulties and restrictions on the effective sparsity range.

3. Orthogonal designs.

For orthogonal designs, the paper proves SLOPE's optimality by decomposing its error into on-support and off-support contributions and controlling each probabilistically. The resulting bound matches the asymptotic minimax rate without requiring the sparsity level.

  • 3. Orthogonal designs.: The proof is simpler than the corresponding FDR-thresholding analysis because SLOPE continuously depends on the observations.The paper associates FDR hard-thresholding discontinuities with technical difficulties and narrower sparsity-range effectiveness.
  • 3. Orthogonal designs.: The orthogonal-design analysis develops majorization and prox facts that support the later Gaussian-design proof.The section introduces majorization, decomposes the loss by support, and establishes lemmas used in Theorem 1.1.
  • 3. Orthogonal designs.: The on-support error is bounded through majorization and the sorted penalty weights, while the off-support error is shown negligible relative to 2k log(p/k).The argument uses properties of the prox to the sorted ℓ1 norm and Gaussian control of the residual coordinates.
  • 3. Orthogonal designs.: With λ = (1 + ϵ)λBH(q), the off-support error remains controlled uniformly over ϵ for k/p → 0.The proposition supplies a high-probability bound for every k-sparse β and any fixed q in the stated range.

4. Gaussian random designs.

For Gaussian random designs, the paper compares SLOPE with an analyzable oracle estimator and localizes both supports to a small resolvent set. Under restricted eigenvalue and sparsity conditions, this transfers asymptotic optimality to the actual SLOPE solution.

  • 4. Gaussian random designs.: The Gaussian-design argument must address both column correlations and high dimensionality, which prevent simply treating X′y as an orthogonal-design observation.The proof therefore combines support localization, random-matrix control, and comparison of reduced optimization problems.
  • 4.1. Architecture of the proof.: The proof constructs an oracle estimator from one proximal-gradient step at the ground truth, then shows it is close to SLOPE.The oracle and SLOPE estimates coincide under orthogonal designs, while the oracle is easier to analyze statistically.
  • 4.2. Comparing SLOPE and the oracle.: On a localized set whose Gram eigenvalues are near one, the squared distance between SLOPE and the oracle is bounded by a multiple of the oracle's estimation error.The relevant comparison factor is 3δ/(1 − 2δ) under δ < 1/2.
  • 4.4. Support localization.: A resolvent set augments the true support with the largest off-support values of |X′z| and is shown to contain the supports of β, the oracle, and SLOPE with high probability.Its size can be chosen small relative to p and n/log p while retaining the required support-localization property.

5. Lower bounds.

The lower-bound analysis constructs one-sparse and block-sparse Gaussian regression problems to show that no estimator can uniformly beat the 2σ²k log(p/k) squared-loss scale. This matches SLOPE's upper bound in the stated asymptotic regime.

  • 5. Lower bounds.: The one-sparse base case establishes a lower bound of 2 log p for estimating sparse Gaussian means.This result is then used to construct harder k-sparse problems.
  • 5. Lower bounds.: For the k-sparse lower bound, the prior partitions coordinates into k blocks and randomly places one signal of amplitude near √(2 log(p/k)) in each block.The total loss is decomposed across independent blocks, allowing the one-sparse result to be aggregated.
  • 5.2. Random designs.: The random-design lower bound handles correlations by decomposing the model into one block and the remaining columns before applying the one-sparse argument.The assumptions ensure the relevant signal scaling remains compatible with n/log(p/k) → ∞.

6. Discussion.

The discussion identifies unresolved questions about extending SLOPE beyond the paper’s setting, especially correlated designs and rigorous FDR control.

  • 6. Discussion.: The paper acknowledges broader design classes as an important direction for extending its results.
  • 6. Discussion.: Correlated designs remain outside the paper’s scope, including weight selection for random covariance designs and tuning for fixed designs.These questions are left for future research.
  • 6. Discussion.: Whether SLOPE rigorously controls the FDR in sparse settings remains an open question.

APPENDIX A: PROOFS OF TECHNICAL RESULTS

The appendix establishes notation and notes that the technical proofs rely on lemmas stated later in the appendix.

  • APPENDIX A: PROOFS OF TECHNICAL RESULTS: The appendix defines ≍ as two-sided bounded equivalence and ∼ as convergence of the ratio to one.
  • APPENDIX A: PROOFS OF TECHNICAL RESULTS: The proofs in this subsection depend on lemmas presented later in the appendix.

A.1. Proofs for Section 2.

These proofs develop technical bounds for SLOPE-related regression quantities, including reduced Lasso arguments, support and off-support losses, and Gaussian-design probability control.

  • A.1. Proofs for Section 2.: The proof establishes the stated result by combining reduced Lasso KKT conditions, support-restricted bounds, and Gaussian-design singular-value control.The argument uses k log p/n → 0 and k/p → 0 to transfer properties from the reduced problem to the full problem.
  • A.1. Proofs for Section 2.: The total loss is decomposed into on-support and off-support components for bounding the SLOPE sequence estimator.
  • A.1. Proofs for Section 2.: 2k log(p/k) dominates the secondary terms because the first contribution is (1 + o(1)) 2k log(p/k) while the remaining terms are lower order.The proof explicitly uses log(p/k) →∞.
  • A.1. Proofs for Section 2.: The analysis accounts for dependence between the random noise order statistics and rank-indexed SLOPE weights.
  • A.1. Proofs for Section 2.: A dual formulation of the SLOPE program is introduced as part of the technical proof strategy.

A.2. Proofs for Section 3.

These proofs analyze the SLOPE proximal and dual formulations and control Gaussian order-statistic terms needed for the technical results.

  • A.2. Proofs for Section 3.: The dual solution is characterized geometrically as the projection of y onto the polytope Cλ,X.
  • A.2. Proofs for Section 3.: The proximal map is monotone, so enlarging selected coordinates cannot decrease the norm of the corresponding fitted coordinates.
  • A.2. Proofs for Section 3.: The proof controls variance and bias-related terms separately, showing their contributions are lower order than 2k log(p/k).
  • A.2. Proofs for Section 3.: The Gaussian bounds rely on order-statistic representations through uniform Beta variables and normal quantile approximations.
  • A.2. Proofs for Section 3.: The auxiliary tail bound assumes q(1 + A)/A < 1 and controls Gaussian order statistics using Chernoff bounds.

A.3. Proofs for Section 4.

The appendix establishes technical lemmas controlling Gaussian order statistics, design singular values, and reduced SLOPE solutions, then uses duality to connect reduced and full programs.

  • Primal-dual completion: Strong duality for the reduced SLOPE program yields optimality of the lifted primal solution and its associated full-program dual vector.The reduced problem has linear equality constraints and is feasible, so its primal and dual optimal values agree.
  • Gaussian order statistics: Gaussian order-statistic lemmas show that BHq critical values majorize the relevant Gaussian sequences with probability approaching one.The lemmas assume fixed 0 < q < 1 and impose conditions on k⋆ relative to k and p.
  • Gaussian decomposition: An orthogonal transformation measurable with respect to z preserves Gaussian structure while separating one transformed row from the remaining design.Independence between the transformation and X makes the resulting matrices suitable for the singular-value and reduced-problem arguments.
  • Gaussian design control: The proof controls the smallest and largest singular values of the Gaussian subdesign indexed by S⋆.Lemma A.11 applies when k < k⋆ < min{n,p} and provides probability bounds for these singular values.
  • Reduced SLOPE control: The reduced SLOPE solution is bounded with probability tending to one when k⋆/min{n,p} tends to zero.The argument combines KKT-based control with Gaussian tail and order-statistic bounds.

A.4. Proofs for Section 5.

The appendix proves Section 5 results by analyzing Gaussian threshold exceedances and showing that sufficiently many coordinates exceed the relevant threshold with high probability.

  • Gaussian exceedances: The number of Gaussian coordinates exceeding the threshold diverges in probability when the threshold is below the extreme-value scale by a diverging gap.The exceedance count is binomial, and its expected value diverges under the stated threshold condition.
  • Error-event reduction: The proof reduces the target error event to whether a randomly selected signal coordinate appears among the largest observed coordinates.The set A is defined through fitted-coefficient thresholds, and the relevant coordinate belongs to A exactly under the target error condition.
  • Random-design extension: The argument extends the coordinatewise analysis to Gaussian random designs by exploiting independence and controlling many columns with bounded norms.The proof uses independence between a selected column and the remaining transformed noise-design vector, together with a high-probability event affecting at least 0.49p columns.
  • Uniform control: The resulting probability bound is negligible uniformly over estimators when log p/n is sufficiently small.The appendix explicitly invokes sufficiently large p so that (log p)/n is small before applying the chosen threshold.
  • Corollary argument: A dimension-reduction argument applies the Section 5 theorem after restricting to p⋆=min{⌊cn⌋,p}, with c chosen sufficiently small.This yields the required sparsity and sample-size relationships for the reduced problem and transfers the bound back to the original setting.
Loading 1503.08393v3…