PaperlayerView exact revision on arXiv

Source-linked AI summary

False Discoveries Occur Early on the Lasso Path

Weijie Su, Malgorzata Bogdan, Emmanuel Candes

arXiv:1511.01957v4math.STcs.ITstat.ML

TL;DR

The paper asks whether strong signals and independent, weakly correlated predictors suffice for accurate Lasso variable selection under linear sparsity. Using asymptotic analysis based on approximate message passing and adaptive-parameter arguments, it derives a sharp power–false-positive boundary. The results show that high power necessarily comes with a nontrivial false-positive burden along the Lasso path, even with arbitrarily strong signals.

  • Problem

    The paper examines whether the Lasso can achieve few false discoveries when signals are strong and regressors are independent, in the linear-sparsity regime.

  • Method

    The paper analyzes the Lasso path asymptotically under independent Gaussian designs using approximate message passing and arguments allowing adaptive selection of the regularization parameter.

  • Results

    The paper derives an exact boundary for achievable (TPP, FDP) pairs, showing that high power and a low false-positive rate cannot occur simultaneously regardless of signal-to-noise ratio.

  • Takeaways & Limitations

    True and null features can remain interspersed on the Lasso path, so the Lasso may require a false-positive trade-off even with independent predictors and very strong effects.

  • Takeaways & Limitations

    The analysis uses linear sparsity and independent regressors; it does not contradict perfect-support-recovery results in substantially sparser asymptotic regimes.

Abstract

from arXiv · show

In regression settings where explanatory variables have very low correlations and there are relatively few effects, each of large magnitude, we expect the Lasso to find the important variables with few errors, if any. This paper shows that in a regime of linear sparsity---meaning that the fraction of variables with a non-vanishing effect tends to a constant, however small---this cannot really be the case, even when the design variables are stochastically independent. We demonstrate that true features and null features are always interspersed on the Lasso path, and that this phenomenon occurs no matter how strong the effect sizes are. We derive a sharp asymptotic trade-off between false and true positive rates or, equivalently, between measures of type I and type II errors along the Lasso path. This trade-off states that if we ever want to achieve a type II error (false negative rate) under a critical value, then anywhere on the Lasso path the type I error (false positive rate) will need to exceed a given threshold so that we can never have both errors at a low level at the same time. Our analysis uses tools from approximate message passing (AMP) theory as well as novel elements to deal with a possibly adaptive selection of the Lasso regularizing parameter.

1. Introduction.

The paper challenges the belief that strong signals and weakly correlated predictors let the Lasso identify important variables with few false discoveries. Under linear sparsity, it shows that false discoveries can appear early and derives a sharp trade-off between power and false-positive rates.

  • Motivation: The Lasso is widely used for sparse variable selection, especially when p is comparable to or larger than n.Its appeal is automatic variable reduction through coefficients estimated as exactly zero.
  • Motivation: Perfect support recovery is often expected when signals are strong relative to noise and predictors are weakly correlated, but practical results show early false discoveries.This motivates treating the Lasso primarily as a variable screener rather than a model selector.
  • Setup: The paper studies false discovery proportion (FDP) along the Lasso path, defining null predictors with β_j = 0 as false discoveries in the independent-regressor setting.The independent-design assumption makes the distinction between true and false discoveries unambiguous.
  • Empirical illustration: In a Gaussian design with 200 nonzero coefficients out of 1000 and high signal-to-noise ratio, the Lasso selects null variables relatively early.When TPP passes 50%, FDP already exceeds 8%; when all true predictors enter, FDP reaches 19%.
  • Empirical illustration: Across 100 experiments, the first false variable entered before 44% of true signals were detected, while the last true signal was preceded by at least 22 false discoveries.On average, the first false discovery occurred after about 32 detected signals, corresponding to only 16% TPP.
  • Main contribution: The main contribution is an asymptotic power–false-positive trade-off under linear sparsity, expressed as an exact boundary separating achievable from impossible (TPP, FDP) pairs.The boundary implies that high power and a low false-positive rate cannot be achieved simultaneously, regardless of signal-to-noise ratio.

2. The Lasso Trade-off Diagram.

Under linear sparsity with independent Gaussian designs, the paper derives a sharp FDP–TPP boundary showing that the Lasso cannot simultaneously achieve high power and low false-discovery rates. The boundary remains relevant in noiseless settings, under adaptive regularization, and across signal distributions, while its severity depends on sparsity and dimensionality.

  • Linear sparsity: Linear sparsity assumes an expected ϵ · p nonzero coefficients, excluding regimes where the nonzero fraction vanishes as p grows.The paper notes that this distinction avoids contradiction with asymptotic perfect-support-recovery results for much sparser models.
  • Main result: The main result gives an explicit boundary q⋆ separating achievable from impossible (TPP, FDP) pairs along the Lasso path.The boundary is tight and remains valid when the regularization parameter is selected adaptively from the data.
  • Main result: Nowhere on the Lasso path can false-discovery and false-negative rates both be simultaneously low.Here FDP represents a type I error measure, while 1−TPP measures missed signals and serves as a type II error measure.
  • Main result: The best-case boundary q⋆ is an envelope: for any fixed coefficient prior Π, the instance-specific trade-off curve qΠ lies above it.Thus, the universal boundary is optimistic relative to any particular Lasso problem.
  • Trade-off diagrams: For δ = 0.3 and ϵ = 0.15, TPP cannot approach 1 because the diagram is vertically truncated at 0.6791.This upper limit is associated with the Donoho–Tanner phase transition.
  • Technical novelties: The trade-off persists with noiseless observations because shrinkage introduces pseudo-noise, the stated common root of the noiseless and noisy cases.The analysis also accommodates irregular Lasso paths, where variables may enter and leave repeatedly, using tools based on KKT support characterization.
  • Trade-off diagrams: FDR control becomes more difficult as the sparsity ratio ϵ = k/p or dimensionality 1/δ = p/n increases.The paper illustrates this dependence through examples of q⋆ for varying ϵ and δ.
  • Numerical illustration: A mixture of very strong and very weak effects is the most favorable configuration because weak effects are not counted as false positives, reducing FDP.Finite-dimensional noiseless simulations are used to illustrate the resulting boundary behavior.

3. What’s Wrong with Shrinkage?.

The Lasso’s shrinkage creates pseudo-noise in residuals, causing false discoveries even with strong signals. In contrast, suitably tuned non-convex methods can achieve perfect separation in some settings.

  • ℓ1 shrinkage biases selected coefficients downward, leaving their effects in the residuals as additional “shrinkage noise.”
  • The heuristic links strong residual correlations for null variables to their possible selection by the full Lasso through the KKT conditions.
  • When the signal support is linear in p, this residual error makes null predictors exceed the selection threshold for a non-vanishing fraction of variables.
  • If the support is sufficiently smaller, such as |T| ≤ c0n/log p, the reduced estimation error is much lower and the phenomenon does not occur.
  • Other ℓ1-penalized methods, including logistic Lasso and the Dantzig selector, also suffer from shrinkage to noise.

4. Discussion.

Discussion of simulations and related regimes shows that false discoveries can arise even with very strong signals and few nonzero coefficients. The paper also identifies open questions about first false entry times and extensions beyond Gaussian designs.

  • Earlier support-recovery results for sub-linear sparsity require n ≥ (2 + o(1))k log p for asymptotically perfect recovery, but Figure 6 shows finite-sample errors under strong signals.
  • 13.4% mean FDP occurs when TPP = 1 across 500 experiments, while noiseless perfect recovery occurs in only 75% of replicates.
  • The timing of the first false selection remains an open question, especially for predicting its average occurrence in the noiseless linear-sparsity regime.
  • Figure 6 uses n = 250, p = 1000, 18 nonzero coefficients of magnitude ≈9.3, and both noisy and noiseless settings.
  • In linear sparsity, marginal-regression nulls and signals are interspersed because their mean shift and standard deviation have comparable magnitudes, implying either high FDR or low power.

APPENDIX A: ROAD MAP TO THE PROOFS

The proof roadmap combines fixed-λ AMP limits, uniform convergence over λ, and optimization over signal priors to derive the asymptotic FDP–TPP trade-off.

  • Proof roadmap: Step 1 uses AMP theory to characterize asymptotic FDP and TPP for the Lasso at fixed λ.
  • Proof roadmap: AMP represents most Lasso estimates asymptotically through componentwise soft-thresholding of βj + τWj at level ατ.
  • Proof roadmap: The limiting false and true discovery rates are expressed through fd∞(λ) and td∞(λ), replacing random finite-dimensional counts asymptotically.
  • Proof roadmap: Step 2 extends convergence of false and true discovery proportions uniformly over λ in a fixed interval.
  • Proof roadmap: Step 3 parameterizes the limiting trade-off by TPP and optimizes the resulting curve over feasible priors.
  • Proof roadmap: The proof also establishes the noiseless case by approximating it with problems whose noise levels approach zero.

APPENDIX B: FOR ALL VALUES OF λ SIMULTANEOUSY

The appendix proves convergence simultaneously across regularization parameters by combining a λ-grid, continuity of limiting quantities, and uniform continuity of Lasso supports and estimates.

  • Uniform convergence: Uniform continuity of the Lasso estimates in ℓ2 norm controls changes in the solution as λ varies.
  • Uniform convergence: The proof partitions [λmin, λmax] into an equally spaced grid and first controls convergence at the grid points.
  • Uniform convergence: Continuity of the limiting solution parameter and fd∞(λ) transfers grid-point control to nearby λ values.
  • Uniform convergence: KKT optimality conditions and subgradient behavior bound variables entering or leaving the support between neighboring grid points.
  • Uniform convergence: The argument relies on auxiliary lemmas, AMP results, bounded spectral norms, and a union bound over the fixed grid.
  • Uniform convergence: The resulting bounds hold with probability tending to one, yielding uniform convergence for false and true discovery proportions.

B.1. Proofs of auxiliary lemmas.

The appendix proves auxiliary bounds needed for the Lasso analysis, including uniform control of the solution and conditions supporting pathwise arguments. The proofs treat underdetermined, overdetermined, and square designs separately.

  • Pathwise auxiliary control: The remaining auxiliary lemmas use monotonicity and concentration arguments to complete the stated high-probability bounds.
  • Uniform solution bounds: Lemma B.5 establishes a high-probability ℓ2 bound for the Lasso solution uniformly over λ ∈ [λmin, λmax].The proof decomposes the solution into null-space and row-space projections and uses Gaussian rotational invariance, Kashin’s theorem, singular-value concentration, and norm inequalities.
  • Uniform solution bounds: For δ > 1, the design matrix has a trivial null space, reducing the solution-bound argument to the preceding case.
  • Uniform solution bounds: At δ = 1, the proof separately controls either the ratio p∥bβ∥2/∥bβ∥1 or the largest coordinates of bβ.The argument uses Lemma B.3 and a subset singular-value bound with s/p → 0.01.
  • Pathwise auxiliary control: Lemma B.2 verifies assumptions required by an earlier pathwise lemma using Lemma B.5, subgradient conditions, and restricted singular-value bounds.

APPENDIX C: OPTIMIZING THE TRADE-OFF

This appendix reduces the feasible asymptotic true-positive and false-discovery rates to a scalar parameterization, then derives the optimal trade-off and its phase-transition boundary.

  • Scalar reduction: Uniform convergence reduces feasibility to studying (tpp∞(λ), fdp∞(λ)) while varying the prior Π⋆ and regularization parameter λ.
  • Scope: The construction is sufficient in the stated sense, but not every pair (δ1, δ2) is feasible below the Donoho–Tanner phase transition.
  • Scalar reduction: A two-point-prior representation expresses the predicted rates through scalar quantities ϵ′ and α.The resulting formulas are tpp∞ = 2(1 − ϵ′)Φ(−α) + ϵ′ and the corresponding scalar FDP expression.
  • Scalar reduction: The function governing the scalar parameterization is concave, enabling Jensen’s inequality to constrain feasible rate pairs.
  • Optimal trade-off: Above the Donoho–Tanner phase transition, asymptotic TPP is bounded away from 1 even for arbitrarily strong signals.
  • Optimal trade-off: For achievable TPP u, the asymptotic FDP obeys fdp∞ > q⋆(u), and q⋆ is strictly increasing in u.The bound is obtained through the unique root t⋆(u) and its monotonicity properties.

C.2. Proofs of auxiliary lemmas.

The auxiliary proofs establish existence, uniqueness, and monotonicity properties for the scalar roots and trade-off functions used in the optimal boundary characterization.

  • Root properties: The positive-root structure changes across regimes: there are two roots below ϵ⋆, one at the boundary or when δ ≥ 1, and none above ϵ⋆ when δ < 1.
  • Root properties: For 0 < u < u⋆, equation (C.6) has a unique root t⋆(u), which strictly decreases as u increases.
  • Proof strategy: The construction of t⋆(u) follows from continuity of h(ζ), while uniqueness follows from the monotonicity of t(ζ) and h(ζ).
  • Trade-off monotonicity: The function q⋆(u) is strictly increasing on (0, u⋆).

APPENDIX D: PROOF OF THEOREM 2.1

The appendix extends the trade-off results across regularization parameters and noise levels, including large λ and the noiseless limit, to prove the main theorem.

  • Extension across λ: The proof extends bounded-λ results to arbitrarily large λ, where the Lasso solution becomes small and power decreases.
  • Extension across λ: Lemma D.1 provides the upper bound needed to control the support size for sufficiently large λ.
  • Main theorem: The theorem’s proof combines the large-λ support bound, uniform convergence on bounded intervals, and KKT-based arguments for noisy and noiseless settings.
  • Noiseless limit: The noiseless case is handled by adding vanishing Gaussian noise and using non-expansiveness of projections onto the Lasso residual polytope.
  • Noiseless limit: As σ → 0, the noisy true-discovery rate converges to its noiseless counterpart, allowing the noisy analysis to transfer to σ = 0.
  • Extension across λ: Uniform convergence over bounded λ intervals combines with the large-λ argument to establish the theorem’s statements with probability tending to one.

D.1. Proof of Lemma D.1.

The proof derives a key estimate for the Lasso solution using optimality, norm inequalities, concentration, and a choice of λ that works uniformly over λ > 0.

  • D.1. Proof of Lemma D.1.: The argument starts from the Lasso objective inequality comparing the fitted solution with the zero vector.This bounds the residual-plus-ℓ1 objective by 1/2∥y∥2.
  • D.1. Proof of Lemma D.1.: Substitution and the triangle inequality produce successive bounds on the relevant quantities.The proof then combines these bounds into its key estimate.
  • D.1. Proof of Lemma D.1.: The law of large numbers controls the right-hand side of the estimate asymptotically.This converts the preceding deterministic inequalities into a probabilistic bound.
  • D.1. Proof of Lemma D.1.: The resulting oP(1) term is independent of any λ > 0, enabling the proof to select a suitable positive λ.The argument concludes by choosing λ′ > 0 after establishing this uniformity.

APPENDIX E: PROOF OF THEOREM 3.1

The appendix proves Theorem 3.1 by controlling selected null and signal variables under linear sparsity. It combines Gaussian concentration and χ2 lemmas with carefully chosen λ and sufficiently large signal magnitude M.

  • APPENDIX E: PROOF OF THEOREM 3.1: Gaussian concentration and χ2-distribution lemmas control the probabilities of the relevant selection events.The first lemma uses Borell’s inequality, while the appendix introduces two χ2 lemmas for the proof.
  • APPENDIX E: PROOF OF THEOREM 3.1: The proof fixes a support subset S and tracks m0 null and m1 nonzero coefficients among its selected variables.The true-support size satisfies k = (ϵ + oP(1))p.
  • APPENDIX E: PROOF OF THEOREM 3.1: It suffices to find λ and sufficiently large M so that the Lasso solution satisfies the desired bounds on false and true selections.This reduction is stated as the target condition for proving Theorem 3.1.
  • APPENDIX E: PROOF OF THEOREM 3.1: With suitable λ and large M, the proof establishes the required event bounds by decomposing them into cases involving m0 + m1 and m1.The final steps invoke the preceding probability estimates to complete the theorem.
  • APPENDIX E: PROOF OF THEOREM 3.1: The argument conditions on the random true support and exploits the uniform orientation of the orthogonal complement of the selected design.Independence among β, X, and z supports this conditioning argument.
  • APPENDIX E: PROOF OF THEOREM 3.1: The appendix chooses λ according to the stated inequalities and takes M sufficiently large so that the central bound holds, completing the proof.The conclusion follows after verifying the two target probability limits.
Loading 1511.01957v4…