To appear in the Annals of Statistics
arXiv: arXiv:1511.01957

FALSE DISCOVERIES OCCUR EARLY ON THE LASSO
PATH

arXiv:1511.01957v4 [] 15 Sep 2016

By Weijie Su∗ and Malgorzata Bogdan† and Emmanuel Candès‡
University of Pennsylvania, University of Wroclaw, and Stanford
University
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. Almost all data scientists know about and routinely
use the Lasso [31, 32] to fit regression models. In the big data era, where
the number p of explanatory variables often exceeds the number n of observational units, it may even supersede the method of least-squares. One
appealing feature of the Lasso over earlier techniques such as ridge regression is that it automatically performs variable reduction, since it produces
∗

Supported in part by NSF under grant CCF-0963835.
Supported in part by the European Union’s 7th Framework Programme for research,
technological development and demonstration under Grant Agreement No. 602552 and cofinanced by the Polish Ministry of Science and Higher Education under Grant Agreement
2932/7.PR/2013/2
‡
Supported in part by NSF under grant CCF-0963835 and by the Math + X Award
from the Simons Foundation.
MSC 2010 subject classifications: Primary 62F03; secondary 62J07, 62J05.
Keywords and phrases: Lasso, Lasso path, false discovery rate, false negative rate,
power, approximate message passing (AMP), adaptive selection of parameters
†

1

2

W. SU, M. BOGDAN, AND E. CANDÈS

models where lots of—if not most—regression coefficients are estimated to
be exactly zero. In high-dimensional problems where p is either comparable
to n or even much larger, the Lasso is believed to select those important
variables out of a sea of potentially many irrelevant features.
Imagine we have an n×p design matrix X of features, and an n-dimensional
response y obeying the standard linear model
y = Xβ + z,
where z is a noise term. The Lasso is the solution to
(1.1)

b
β(λ)
= argmin
b∈Rp

1
2 ky

− Xbk2 + λ kbk1 ;

if we think of the noise term as being Gaussian, we interpret it as a penalized
maximum likelihood estimate, in which the fitted coefficients are penalized
in an `1 sense, thereby encouraging sparsity. (There are nowadays many
variants on this idea including `1 -penalized logistic regression [32], elastic
nets [43], graphical Lasso [39], adaptive Lasso [42], and many others.) As is
clear from (1.1), the Lasso depends upon a regularizing parameter λ, which
must be chosen in some fashion: in a great number of applications this is
typically done via adaptive or data-driven methods; for instance, by crossvalidation [16, 24, 40, 28]. Below, we will refer to the Lasso path as the family
b
of solutions β(λ)
as λ varies between 0 and ∞. We say that a variable j is
b
selected at λ if βj (λ) 6= 0.1
The Lasso is, of course, mostly used in situations where the true regression coefficient sequence is suspected to be sparse or nearly sparse. In such
settings, researchers often believe—or, at least, wish—that as long as the
true signals (the nonzero regression coefficients) are sufficiently strong compared to the noise level and the regressor variables weakly correlated, the
Lasso with a carefully tuned value of λ will select most of the true signals
while picking out very few, if any, noise variables. This belief is supported by
theoretical asymptotic results discussed below, which provide conditions for
perfect support recovery, i.e. for perfectly identifying which variables have
a non-zero effect, see [38, 37, 30] for instance. Since these results guarantee
that the Lasso works well in an extreme asymptotic regime, it is tempting to
over-interpret what they actually say, and think that the Lasso will behave
correctly in regimes of practical interest and offer some guarantees there as
well. However, some recent works such as [19] have observed that the Lasso
1

We also say that a variable j enters the Lasso path at λ0 if there is there is ε > 0 such
that βbj (λ) = 0 for λ ∈ [λ0 − ε, λ0 ] and βbj (λ) 6= 0 for λ ∈ (λ0 , λ0 + ε]. Similarly a variable
is dropped at λ0 if βbj (λ) 6= 0 for λ ∈ [λ0 − ε, λ0 ) and βbj (λ) = 0 for λ ∈ [λ0 , λ0 + ε].

FALSE DISCOVERIES ON LASSO PATH

3

has problems in selecting the proper model in practical applications, and
that false discoveries may appear very early on the Lasso path. This is the
reason why [8, 7, 29] suggest that the Lasso should merely be considered as
a variable screener rather than a model selector.
While the problems with the Lasso ordering of predictor variables are
recognized, they are often attributed to (1) correlations between predictor
variables, and (2) small effect sizes. In contrast, the novelty and message
of our paper is that the selection problem also occurs when the signal-tonoise ratio is infinitely large (no noise) and the regressors are stochastically
independent; we consider a random design X with independent columns, and
as a result, all population correlations vanish (so the sample correlations are
small). We also explain that this phenomenon is mainly due to the shrinkage
of regression coefficients, and does not occur when using other methods,
e.g. an `0 penalty in (1.1) rather than the `1 norm, compare Theorem 3.1
below.
Formally, we study the value of the false discovery proportion (FDP),
the ratio between the number of false discoveries and the total number of
discoveries, along the Lasso path.2 This requires notions of true/false discoveries, and we pause to discuss this important point. In high dimensions,
it is not a trivial task to define what are true and false discoveries, see
e.g. [4, 21, 35, 20, 23]; these works are concerned with a large number of
correlated regressors, where it is not clear which of these should be selected
in a model. In response, we have selected to work in the very special case
of independent regressors precisely to analyze a context where such complications do not arise and it is, instead, quite clear what true and false
discoveries are. We classify a selected regressor Xj to be a false discovery
if it is stochastically independent from the response, which in our setting is
equivalent to βj = 0. Indeed, under no circumstance can we say that that
such a variable, which has zero explanatory power, is a true discovery.
Having clarified this point and as a setup for our theoretical findings,
Figure 1 studies the performance of the Lasso under a 1010 × 1000 a random
Gaussian design, where the entries of X are independent draws from N (0, 1).
Set β1 = · · · = β200 = 4, β201 = · · · = β1000 = 0 and the errors to be
independent standard normals. Hence, we have 200 nonzero coefficients out
of 1000 (a relatively sparse setting), and a very large signal-to-noise ratio
(SNR). For instance, if we order the variables by the magnitude of the leastsquares estimate, which we can run since n = 1010 > 1000 = p, then with
probability practically equal to one, all the top 200 least-squares discoveries
2

Similarly, the TPP is defined as the ratio between the number of true discoveries and
that of potential true discoveries to be made.

4

W. SU, M. BOGDAN, AND E. CANDÈS

0.20

correspond to true discoveries, i.e. variables for which βj = 4. This is in
sharp contrast with the Lasso, which selects null variables rather early. To
be sure, when the Lasso includes half of the true predictors so that the
false negative proportion falls below 50% or true positive proportion (TPP)
passes the 50% mark, the FDP has already passed 8% meaning that we have
already made 9 false discoveries. The FDP further increases to 19% the first
time the Lasso model includes all true predictors, i.e. achieves full power
(false negative proportion vanishes).

Least−squares
Lasso

0.00

0.05

FDP
0.10

0.15

●

●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●
● ●
●
●
●
●●
●
●
●
●●
●●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
● ●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

0.0

0.2

0.4

0.6

0.8

1.0

TPP

Fig 1: True positive and false positive rates along the Lasso path as
compared to the ordering provided by the least-squares estimate.

Figure 2 provides a closer look at this phenomenon, and summarizes the
outcomes from 100 independent experiments under the same Gaussian random design setting. In all the simulations, the first noise variable enters the
Lasso model before 44% of the true signals are detected, and the last true
signal is preceded by at least 22 and, sometimes, even 54 false discoveries.
On average, the Lasso detects about 32 signals before the first false variable
enters; to put it differently, the TPP is only 16% at the time the first false
discovery is made. The average FDP evaluated the first time all signals are
detected is 15%. For related empirical results, see e.g. [19].
The main contribution of this paper is to provide a quantitative description of this phenomenon in the asymptotic framework of linear sparsity
defined below and previously studied e.g. in [3]. Assuming a random design
with independent Gaussian predictors as above, we derive a fundamental
Lasso trade-off between power (the ability to detect signals) and type I er-

5

FALSE DISCOVERIES ON LASSO PATH
20

30

15

Frequency

20

10

10
5

0

0
0.0

0.1

0.2

0.3

0.4

0.5

TPP at time of first false selection

0.00

0.05

0.10

0.15

0.20

0.25

FDP at time of last true selection

Fig 2: Left: power when the first false variable enters the Lasso model.
Right: false discovery proportion the first time power reaches one
(false negative proportion vanishes).

rors or, said differently, between the true positive and the false positive rates.
This trade-off says that it is impossible to achieve high power and a low false
positive rate simultaneously. Formally, we compute the formula for an exact
boundary curve separating achievable (TPP, FDP) pairs from pairs that are
impossible to achieve no matter the value of the signal-to-noise ratio (SNR).
Hence, we prove that there is a whole favorable region in the (TPP, FDP)
plane that cannot be reached, see Figure 3 for an illustration.
2. The Lasso Trade-off Diagram.
2.1. Linear sparsity and the working model. We mostly work in the setting of [3], which specifies the design X ∈ Rn×p , the parameter sequence
β ∈ Rp and the errors z ∈ Rn . The design matrix X has i.i.d. N (0, 1/n)
entries so that the columns are approximately normalized, and the errors
zi are i.i.d. N (0, σ 2 ), where σ is fixed but otherwise arbitrary. Note that
we do not exclude the value σ = 0 corresponding to noiseless observations.
The regression coefficients β1 , . . . , βp are independent copies of a random
variable Π obeying E Π2 < ∞ and P(Π 6= 0) =  ∈ (0, 1) for some constant
. For completeness, X, β, and z are all independent from each other. As in
[3], we are interested in the limiting case where p, n → ∞ with n/p → δ for
some positive constant δ. A few comments are in order.
Linear sparsity. The first concerns the degree of sparsity. In our model, the
expected number of nonzero regression coefficients is linear in p and equal
to  · p for some  > 0. Hence, this model excludes a form of asymptotics
discussed in [38, 37, 30], for instance, where the fraction of nonzero coeffi-

6

W. SU, M. BOGDAN, AND E. CANDÈS

cients vanishes in the limit of large problem sizes. Specifically, our results
do not contradict asymptotic results from [38] predicting perfect support
recovery in an asymptotic regime, where the number of k of variables in the
model
√ obeys k/p ≤ δ/(2 log p) · (1 + o(1)) and the effect sizes all grow like
c · σ 2 log p, where c is an unknown numerical constant. The merit of the
linear sparsity regime lies in the fact that our theory makes accurate predictions when describing the performance of the Lasso in practical settings with
moderately large dimensions and reasonable values of the degree of sparsity,
including rather sparse signals. The precision of these predictions is illustrated in Figure 5 and in Section 4. In the latter case, n = 250, p = 1000
and the number of k of signals is very small, i.e. k = 18.
Gaussian designs. Second, Gaussian designs with independent columns are
believed to be “easy” or favorable for model selection due to weak correlations between distinct features. (Such designs happen to obey restricted
isometry properties [9] or restricted eigenvalue conditions [5] with high probability, which have been shown to be useful in settings sparser than those
considered in this paper.) Hence, negative results under the working hypothesis are likely to extend more generally.
Regression coefficients. Third, the assumption concerning the distribution
of the regression coefficients can be slightly weakened: all we need is that
the sequence β1 , . . . , βp has a convergent empirical distribution with bounded
second moment. We shall not pursue this generalization here.
2.2. Main result. Throughout the paper, V (resp. T ) denotes the number
of Lasso false (resp. true) discoveries while k = |{j : βj 6= 0}| denotes the
number of true signals; formally, V (λ) = |{j : βbj (λ) 6= 0 and βj = 0}|
whereas T (λ) = |{j : βbj (λ) 6= 0 and βj 6= 0}|. With this, we define the FDP
as usual,
(2.1)

FDP(λ) =

V (λ)
|{j : βbj (λ) 6= 0}| ∨ 1

and, similarly, the TPP is defined as
(2.2)

TPP(λ) =

T (λ)
k∨1

(above, a ∨ b = max{a, b}). The dependency on λ shall often be suppressed
when clear from the context. Our main result provides an explicit trade-off
between FDP and TPP.

FALSE DISCOVERIES ON LASSO PATH

7

Theorem 2.1. Fix δ ∈ (0, ∞) and  ∈ (0, 1), and consider the function
q ? (·) = q ? (·; δ, ) > 0 given in (2.4). Then under the working hypothesis and
for any arbitrary small constants λ0 > 0 and η > 0, the following conclusions
hold:
(a) In the noiseless case (σ = 0), the event
o
\ n
(2.3)
FDP(λ) ≥ q ? (TPP(λ)) − η
λ≥λ0

holds with probability tending to one. (The lower bound on λ in (2.3)
does not impede interpretability since we are not interested in variables
entering the path last.)
(b) With noisy data (σ > 0) the conclusion is exactly the same as in (a).
(c) Therefore, in both the noiseless and noisy cases, no matter how we
b X) ≥ c1 adaptively by looking at the response y and
choose λ(y,
b <
design X, with probability tending to one we will never have FDP(λ)
?
b
q (TPP(λ)) − c2 .
(d) The boundary curve q ? is tight: any continuous curve q(u) ≥ q ? (u)
with strict inequality for some u will fail (a) and (b) for some prior
distribution Π on the regression coefficients.
A different way to phrase the trade-off is via false discovery and false negative rates. Here, the FDP is a natural measure of type I error while 1−TPP
(often called the false negative proportion) is the fraction of missed signals, a
natural notion of type II error. In this language, our results simply say that
nowhere on the Lasso path can both types of error rates be simultaneously
low.
Remark 1. We would like to emphasize that the boundary is derived
from a best-case point of view. For a fixed prior Π, we also provide in Theorem D.2 from Appendix D a trade-off curve q Π between TPP and FDP,
which always lies above the boundary q ? . Hence, the trade-off is of course
less favorable when we deal with a specific Lasso problem. In fact, q ? is
nothing else but the lower envelope of all the instance-specific curves q Π
with P(Π 6= 0) = .
Figure 3 presents two instances of the Lasso trade-off diagram, where
the curve q ? (·) separates the red region, where both type I and type II
errors are small, from the rest (the white region). Looking at this picture,
Theorem 2.1 says that nowhere on the Lasso path we will find ourselves in
the red region, and that this statement continues to hold true even when

8

W. SU, M. BOGDAN, AND E. CANDÈS

there is no noise. Our theorem also says that we cannot move the boundary
upward. As we shall see, we can come arbitrarily close to any point on the
curve by specifying a prior Π and a value of λ. Note that the right plot is
vertically truncated at 0.6791, implying that TPP cannot even approach 1
in the regime of δ = 0.3,  = 0.15. This upper limit is where the DonohoTanner phase transition occurs [15], see the discussion in Section 2.6 and
Appendix C.
1.0

0.8

0.8

0.6

0.6

0.4

0.4

FDP

1.0

0.2

Unachievable

0.0

Unachievable

0.2

0.0
0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

TPP

0.6

0.8

1.0

TPP

Fig 3: The Lasso trade-off diagram: left is with δ = 0.5 and  = 0.15,
and right is with δ = 0.3 and  = 0.15 (the vertical truncation occurs
at 0.6791).

Support recovery from noiseless data is presumably the most ideal scenario. Yet, the trade-off remains the same as seen in the first claim of the
theorem. As explained in Section 3, this can be understood by considering
that the root cause underlying the trade-off in both the noiseless and noisy
cases come from the pseudo-noise introduced by shrinkage.
2.3. The boundary curve q ? . We now turn to specify q ? . For a fixed u,
let t? (u) be the largest positive root3 of the equation in t,


2(1 − ) (1 + t2 )Φ(−t) − tφ(t) + (1 + t2 ) − δ
1−u
=
.
 [(1 + t2 )(1 − 2Φ(−t)) + 2tφ(t)]
1 − 2Φ(−t)
Then
(2.4)

q ? (u; δ, ) =

2(1 − )Φ(−t? (u))
.
2(1 − )Φ(−t? (u)) + u

3
If u = 0, treat +∞ as a root of the equation, and in (2.4) conventionally set 0/0 = 0.
In the case where δ ≥ 1, or δ < 1 and  is no larger than a threshold determined only by
δ, the range of u is the unit interval [0, 1]. Otherwise, the range of u is the interval with
endpoints 0 and some number strictly smaller than 1, see the discussion in Appendix C.

9

FALSE DISCOVERIES ON LASSO PATH

0.7

0.30

It can be shown that this function is infinitely many times differentiable over
its domain, always strictly increasing, and vanishes at u = 0. Matlab code
to calculate q ? is available at https://github.com/wjsu/fdrlasso.
Figure 4 displays examples of the function q ? for different values of 
(sparsity), and δ (dimensionality). It can be observed that the issue of FDR
control becomes more severe when the sparsity ratio  = k/p increases and
the dimensionality 1/δ = p/n increases.

0.5

0.6

δ=0.4
δ=0.8
δ=1

0.4
0.3

0.15

0.0

0.00

0.1

0.05

0.2

0.10

FDP

0.20

0.25

ε=0.4
ε=0.2
ε=0.1

0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

0.8

1.0

0.6

0.8

δ=0.05
δ=0.1
δ=0.25

0.4

0.6
0.4

0.0

0.0

0.2

ε=0.07
ε=0.05
ε=0.03

0.2

FDP

0.6

TPP

0.8

TPP

0.0

0.2

0.4

0.6

TPP

0.8

1.0

0.0

0.2

0.4

0.6

0.8

1.0

TPP

Fig 4: Top-left is with δ = 1; top-right is with  = 0.2; bottom-left
is with δ = 0.1; and bottom-right is with  = 0.05.

2.4. Numerical illustration. Figure 5 provides the outcomes of numerical
simulations for finite values of n and p in the noiseless setup where σ = 0.
For each of n = p = 1000 and n = p = 5000, we compute 10 independent
Lasso paths and plot all pairs (TPP, FDP) along the way. In Figure 5a we
can see that when TPP < 0.8, then the large majority of pairs (TPP, FDP)
along these 10 paths are above the boundary. When TPP approaches one,
the average FDP becomes closer to the boundary and a fraction of the paths

10

W. SU, M. BOGDAN, AND E. CANDÈS

0.25

0.25

fall below the line. As expected this proportion is substantially smaller for
the larger problem size.
●

●
●

boundary
n=p=1000
n=p=5000

●●
●
●
●●
●●●
●
●●●
●●
● ●●
●●
●●●●●
●●●●●●● ●●●●●●●●●●
●
●●●
●●
●●● ● ●● ●●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ● ●
●
●
●
●
●
●
●
●
●
●
● ● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●● ●●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●●● ● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
●
●
●
●
●●
●
●●
●●●
●
●
●
●
●
●●
●●●
●
●
●
●
●
●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●●●● ●●●●●●●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ● ●●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●● ● ●● ●● ●●●● ●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ● ●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●● ●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●●●●
●
●
●
●●
●
●
●
●
●
●
●
●
● ●●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●● ●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●●● ● ●●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●●
● ●
●
●
●●
●
●
●
●● ●
●
●●
●
●
●
●
● ●●
●●
●
●
●● ● ● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●●●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
● ●●●●● ●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●● ●●●●
●● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
● ●●●
●
●●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●●● ●●●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●● ●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●● ●●●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
● ●●●●
●
●
●
●
●
●
●●●● ●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●●●●●● ●●●●●● ●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●●● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ● ●●
●
●
●
●●●●●●●●● ●●●●●● ●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●● ● ●●● ●● ●● ● ●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●● ●● ●●● ●●● ●●● ●●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●●
●
●
●
●
●
●●●● ●●
●
●
●
●
●
●
●
●
●
●● ●●
●● ●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●●●● ●●●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●
●
●
●●●● ●●●● ●
●
●
●
●
●●
●
●
●●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●●● ● ●●
●
●
●
●
●
●●●● ●●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
● ●●
●
●
●
●●
●
●
●
●
●
●
●
●
●●●●●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●●●●●●
●
●
●
●●●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●● ●●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●●●●
●
●
●
●
●
●
●
●
●●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
● ●●●●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●●
● ●●
●●
●● ●
●
●●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●●●●
●●
●
●
● ●●
●●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●
●
●
●
●
●
●●●●●
●
●
●
●
●
●●
●
●●●
●●●●
●●
●
●
●●
●●
●● ●
●●
● ●●●●
●
●
●
●
●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●●
●
●
●●
●
●
●●●●
●
●●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●●
●
●
●
●
●
●
●
●●
●●●●●● ●
●
●
●●●●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●●●
●●
●
●●
●
●
●
●
●
●
●●●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●●●●● ●
●
●
●
●
●
●
●
●
●
●●●●●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●
●
●●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●●●●●●●●●●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●
●
●●
●●●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●●
●
●●●●● ●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●●
●
● ●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●
●
●
●●
●
●
●
●
●
●●●
●
●
●●
●●●●
●
●●
●
●
●
●
●●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●●●●●
●
●
●
●
●
●
●
●
●
●
●●●●●●●●●●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●●●●●●
●
●
●
●
●
●
●●
●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
● ●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●●●●●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
● ●●●●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●●●●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●●
●●●●●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●●●●●●●●●●●●●●●●●●●

boundary
ε'=0.3
ε'=0.5
ε'=0.7
ε'=0.9

0.20

0.20

●

0.0

0.2

0.4

0.6

0.8

TPP

1.0

0.15

Mean FDP

0.10
0.05
0.00

0.00

0.05

0.10

FDP

0.15

●

0.0

0.2

0.4

0.6

0.8

1.0

TPP

(a) Realized (TPP, FDP) pairs

(b) Sharpness of the boundary

Fig 5: In both (a) and (b), n/p = δ = 1,  = 0.2, and the noise level is
σ = 0 (noiseless). (a) FDP vs. TPP along 10 independent Lasso paths
with P(Π = 50) = 1 − P(Π = 0) = . (b) Mean FDP vs. mean TPP
averaged at different values of λ over 100 replicates for n = p = 1000,
P(Π = 0) = 1 −  as before, and P(Π = 50|Π 6= 0) = 1 − P(Π =
0.1|Π 6= 0) = 0 .

2.5. Sharpness. The last conclusion from the theorem stems from the
following fact: take any point (u, q ? (u)) on the boundary curve; then we can
approach this point by fixing 0 ∈ (0, 1) and setting the prior to be


w.p.  · 0 ,
M,
Π = M −1 , w.p.  · (1 − 0 ),


0,
w.p. 1 − .
We think of M as being very large so that the (nonzero) signals are either
very strong or very weak. In Appendix C, we prove that for any u between
0 and 1 there is some fixed 0 = 0 (u) > 0 such that4
(2.5)
4

lim

lim (TPP(λ), FDP(λ)) → (u, q ? (u)),

M →∞ n,p→∞

In some cases u should be bounded above by some constant strictly smaller than 1.
See the previous footnote for details.

FALSE DISCOVERIES ON LASSO PATH

11

where convergence occurs in probability. This
√ holds provided that λ → ∞
in such a way that M/λ → ∞; e.g. λ = M . Hence, the most favorable
configuration is when the signal is a mixture of very strong and very weak
effect sizes because weak effects cannot be counted as false positives, thus
reducing the FDP.
Figure 5b provides an illustration of (2.5). The setting is as in Figure 5a
with n = p = 1000 and P(Π = 0) = 1 −  except that, here, conditionally
on being nonzero the prior takes on the values 50 and 0.1 with probability
0 ∈ {0.3, 0.5, 0.7, 0.9} and 1 − 0 , respectively, so that we have a mixture of
strong and weak signals. We observe that the true/false positive rate curve
nicely touches only one point on the boundary depending on the proportion
0 of strong signals .
2.6. Technical novelties and comparisons with other works. The proof
of Theorem 2.1 is built on top of the approximate message passing (AMP)
theory developed in [12, 2, 1], and requires nontrivial extensions. AMP was
originally designed as an algorithmic solution to compressive sensing problems under random Gaussian designs. In recent years, AMP has also found
applications in robust statistics [13, 14], structured principal component
analysis [11, 26], and the analysis of the stochastic block model [10]. Having
said this, AMP theory is of crucial importance to us because it turns out to
be a very useful technique to rigorously study various statistical properties
of the Lasso solution whenever we employ a fixed value of the regularizing
parameter λ [3, 25, 27].
There are, however, major differences between our work and AMP research. First and foremost, our paper is concerned with situations where λ
is selected adaptively, i.e. from the data; this is clearly outside of the envelope of current AMP results. Second, we are also concerned with situations
where the noise variance can be zero. Likewise, this is outside of current
knowledge. These differences are significant and as far as we know, our main
result cannot be seen as a straightforward extension of AMP theory. In particular, we introduce a host of novel elements to deal, for instance, with the
irregularity of the Lasso path. The irregularity means that a variable can
enter and leave the model multiple times along the Lasso path [17, 34] so
that natural sequences of Lasso models are not nested. This implies that
a naive application of sandwiching inequalities does not give the type of
statements holding uniformly over all λ’s that we are looking for.
Instead, we develop new tools to understand the “continuity” of the supb
port of β(λ)
as a function of λ. Since the support can be characterized by
the Karush-Kuhn-Tucker (KKT) conditions, this requires establishing some

12

W. SU, M. BOGDAN, AND E. CANDÈS

sort of continuity of the KKT conditions. Ultimately, we shall see that this
comes down to understanding the maximum distance—uniformly over λ and
b
b 0 ) at close values of the regularizλ0 —between Lasso estimates β(λ)
and β(λ
ing parameter. A complete statement of this important intermediate result
is provided in Lemma B.2 from Appendix B.
Our results can also be compared to the phase-transition curve from [15],
which was obtained under the same asymptotic regime and describes conditions for perfect signal recovery in the noiseless case. The solution algorithm
there is the linear program, which minimizes the `1 norm of the fitted coefficients under equality constraints, and corresponds to the Lasso solution in
the limit of λ → 0 (the end or bottom of the Lasso path). The conditions for
perfect signal recovery by the Lasso turn out to be far more restrictive than
those related to this linear program. For example, our FDP-TPP trade-off
curves show that perfect recovery of an infinitely large signal by Lasso is
often practically impossible even when n ≥ p (see Figure 4). Interestingly,
the phase-transition curve also plays a role in describing the performance
of the Lasso, since it turns out that for signals dense enough not to be recovered by the linear program, not only does the Lasso face the problem of
early false discoveries, it also hits a power limit for arbitrary small values of
λ (see the discussion in Appendix C).
Finally, we would like also to point out that some existing works have
investigated support recovery in regimes including linear sparsity under random designs (see e.g. [37, 30]). These interesting results were, however, obtained by taking an information-theoretic point of view and do not apply to
computationally feasible methods such as the Lasso.
3. What’s Wrong with Shrinkage?.
3.1. Performance of `0 methods. We wrote earlier that not all methods
share the same difficulties in identifying those variables in the model. If the
signals are sufficiently strong, some other methods, perhaps with exponential computational cost, can achieve good model selection performance, see
e.g. [30]. As an example, consider the simple `0 -penalized maximum likelihood estimate,
(3.1)

βb0 = argmin ky − Xbk2 + λ kbk0 .
b∈Rp

Methods known as AIC, BIC and RIC (short for risk inflation criterion)
are all of this type and correspond to distinct values of the regularizing
parameter λ. It turns out that such fitting strategies can achieve perfect
separation in some cases.

FALSE DISCOVERIES ON LASSO PATH

13

Theorem 3.1. Under our working hypothesis, take  < δ for identifiability, and consider the two-point prior
(
M,
w.p. ,
Π=
0,
w.p. 1 − .
Then we can find λ(M ) such that in probability, the discoveries of the `0
estimator (3.1) obey
lim

lim FDP = 0

M →∞ n,p→∞

and

lim

lim TPP = 1.

M →∞ n,p→∞

The proof of the theorem is in Appendix E. Similar conclusions will certainly hold for many other non-convex methods, including SCAD and MC+
with properly tuned parameters [18, 41].
3.2. Some heuristic explanation. In light of Theorem 3.1, we pause to
discuss the cause underlying the limitations of the Lasso for variable selection, which comes from the pseudo-noise introduced by shrinkage. As is
well-known, the Lasso applies some form of soft-thresholding. This means
that when the regularization parameter λ is large, the Lasso estimates are
seriously biased downwards. Another way to put this is that the residuals
still contain much of the effects associated with the selected variables. This
can be thought of as extra noise that we may want to call shrinkage noise.
Now as many strong variables get picked up, the shrinkage noise gets inflated
and its projection along the directions of some of the null variables may actually dwarf the signals coming from the strong regression coefficients; this
is why null variables get picked up. Although our exposition below dramatically lacks in rigor, it nevertheless formalizes this point in some qualitative
fashion. It is important to note, however, that this phenomenon occurs in
the linear sparsity regime considered in this paper so that we have sufficiently many variables for the shrinkage noise to build up and have a fold on
other variables that becomes competitive with the signal. In contrast, under
extreme sparsity and high SNR, both type I and II errors can be controlled
at low levels, see e.g. [22].
For simplicity, we fix the true support T to be a deterministic subset of size
 · p, each nonzero coefficient in T taking on a constant value M > 0. Also,
assume δ > . Finally, since the noiseless case z = 0 is conceptually perhaps
the most difficult, suppose σ = 0. Consider the reduced Lasso problem first:
βbT (λ) = argmin
bT

∈Rp

1
2 ky

− XT bT k2 + λ kbT k1 .

14

W. SU, M. BOGDAN, AND E. CANDÈS

This (reduced) solution βbT (λ) is independent from the other columns XT
(here and below T is the complement of T ). Now take λ to be of the same
magnitude as M so that roughly half of the signal variables are selected.
The KKT conditions state that
−λ1 ≤ XT> (y − XT βbT ) ≤ λ1,
where 1 is the vectors of all ones. Note that if |Xj> (y − XT βbT )| ≤ λ for all
j ∈ T , then extending βbT (λ) with zeros would be the solution to the full
Lasso problem—with all variables included as potential predictors—since it
would obey the KKT conditions for the full problem. A first simple fact is
this: for j ∈ T , if
(3.2)

|Xj> (y − XT βbT )| > λ,

then Xj must be selected by the incremental Lasso with design variables
indexed by T ∪ {j}. Now we make an assumption which is heuristically
reasonable: any j obeying (3.2) has a reasonable chance to be selected in the
full Lasso problem with the same λ (by this, we mean with some probability
bounded away from zero). We argue in favor of this heuristic later.
Following our heuristic, we would need to argue that (3.2) holds for a
number of variables in T linear in p. Write
XT> (y − XT βbT ) = XT> (XT βT − XT βbT ) = λgT ,
where gT is a subgradient of the `1 norm at βbT . Hence, βT −βbT = λ(XT> XT )−1 gT
and
XT (βT − βbT ) = λXT (XT> XT )−1 gT .
Since δ > , XT (XT> XT )−1 has a smallest singular value bounded away from
zero (since XT is a fixed random matrix with more rows than columns). Now
because we make about half discoveries, the subgradient takes on the value
one (in magnitude) at about  · p/2 times. Hence, with high probability,
kXT (βT − βbT )k ≥ λ · c0 · kgT k ≥ λ · c1 · p
for some constants c0 , c1 depending on  and δ.
Now we use the fact that βbT (λ) is independent of XT . For any j ∈
/ T , it
follows that
Xj> (y − XT βbT ) = Xj> XT (βT − βbT )
is conditionally normally distributed with mean zero and variance
kXT (βT − βbT )k2
c1 λ2 p
≥
= c2 · λ2 .
n
n

FALSE DISCOVERIES ON LASSO PATH

15

In conclusion, the probability that Xj> (y −XT βbT ) has absolute value larger
than λ is bounded away from 0. Since there are (1 − )p such j’s, their
expected number is linear in p. This implies that by the time half of the true
variables are selected, we already have a non-vanishing FDP. Note that when
|T | is not linear in p but smaller, e.g. |T | ≤ c0 n/ log p for some sufficiently
small constant c0 , the variance is much smaller because the estimation error
kXT (βT − βbT )k2 is much lower, and this phenomenon does not occur.
Returning to our heuristic, we make things simpler by considering alternatives: (a) if very few extra variables in T were selected by the full Lasso,
then the value of the prediction X βb would presumably be close to that obtained from the reduced model. In other words, the residuals y − X βb from
the full problem should not differ much from those in the reduced problem. Hence, for any j obeying (3.2), Xj would have a high correlation with
b Thus this correlation has a good chance to be close to λ, or actually
y −X β.
be equal to λ. Equivalently, Xj would likely be selected by the full Lasso
problem. (b) If on the other hand, the number of variables selected from T
by the full Lasso were a sizeable proportion of |T |, we would have lots of
false discoveries, which is our claim.
In a more rigorous way, AMP claims that under our working hypothesis,
the Lasso estimates βbj (λ) are, in a certain sense, asymptotically distributed
as ηατ (βj +τ Wj ) for most j and Wj ’s independently drawn from N (0, 1). The
positive constants α and τ are uniquely determined by a pair of nonlinear
equations parameterized by , δ, Π, σ 2 , and λ. Suppose as before that all the
nonzero coefficients of β are large in magnitude, say they are all equal to M .
When about half of them appear on the path, we have that λ is just about
equal to M . A consequence of the AMP equations is that τ is also of this
order of magnitude. Hence, under the null we have that (βj + τ Wj )/M ∼
N (0, (τ /M )2 ) while under the alternative, it is distributed as N (1, (τ /M )2 ).
Because, τ /M is bounded away from zero, we see that false discoveries are
bound to happen.
Variants of the Lasso and other `1 -penalized methods, including `1 -penalized
logistic regression and the Dantzig selector, also suffer from this “shrinkage
to noise” issue.
4. Discussion. We have evidenced a clear trade-off between false and
true positive rates under the assumption that the design matrix has i.i.d. Gaussian entries. It is likely that there would be extensions of this result to designs
with general i.i.d. sub-Gaussian entries as strong evidence suggests that the
AMP theory may be valid for such larger classes, see [1]. It might also be
of interest to study the Lasso trade-off diagram under correlated random

16

W. SU, M. BOGDAN, AND E. CANDÈS

designs.
As we previously mentioned in the introduction, a copious body of literature considers the Lasso support recovery under Gaussian random designs,
where the sparsity of the signal is often assumed to be sub-linear in the ambient dimension p. Recall
that if all the nonzero signal components have mag√
nitudes at least cσ 2 log p for some unspecified numerical constant c (which
would have to exceed one), the results from [38] conclude that, asymptotically, a sample size of n ≥ (2 + o(1))k log p is both necessary and sufficient
for the Lasso to obtain perfect support recovery. What does these results say
for finite values of n and p? Figure 6 demonstrates the performance of the
Lasso under a moderately large 250 × 1000 random Gaussian design. Here,
we consider a very sparse signal, √
where only k = 18 regression coefficients
are nonzero, β1 = · · · = β18 = 2.5 2 log p ≈ 9.3, β19 = · · · = β1000 = 0, and
the noise variance is σ 2 =√1. Since k = 18 is smaller than n/2 log p and β is
substantially larger than 2 log p one might expect that Lasso would recover
the signal support. However, Figure 1 (left) shows that this might not be
the case. We see that the Lasso includes five false discoveries before all true
predictors are included, which leads to an FDP of 21.7% by the time the
power (TPP) reaches 1. Figure 6 (right) summarizes the outcomes from 500
independent experiments, and shows that the average FDP reaches 13.4%
when TPP = 1. With these dimensions, perfect recovery is not guaranteed
even in the case of ‘infinitely’ large signals (no noise). In this case, perfect
recovery occurs in only 75% of all replicates and the averaged FDP at the
point of full power is equal to 1.7%, which almost perfectly agrees with the
boundary FDP provided in Theorem 2.1. Thus, quite surprisingly, our results obtained under a linear sparsity regime apply to sparser regimes, and
might prove useful across a wide range of sparsity levels.
Of concern in this paper are statistical properties regarding the number
of true and false discoveries along the Lasso path but it would also be interesting to study perhaps finer questions such as this: when does the first
noise variable get selected? Consider Figure 7: there, n = p = 1000, σ 2 = 1,
β1 = · · · = βk = 50 (very large SNR) and k varies from 5 to 150. In the very
low sparsity regime, all the signal variables are selected before any noise
variable. When the number k of signals increases we observe early false discoveries, which may occur for values of k smaller than n/(2 log p). However,
the average rank of the first false discovery is substantially smaller than k
only after k exceeds n/(2 log p). Then it keeps on decreasing as k continues
to increase, a phenomenon not explained by any result we are aware of. In
the linear sparsity regime, it would be interesting to derive a prediction for
the average time of the first false entry, at least in the noiseless case.

17

0.15
●

●

●

●

●

0.10

●
●

●

●

● ●

● ● ● ● ● ● ● ● ● ● ●

0.0

0.2

0.4

mean FDP, with noise
mean FDP, no noise
boundary

●

0.05

●

Least Squares
Lasso

0.00

0.00 0.05 0.10 0.15 0.20 0.25

FDP

FALSE DISCOVERIES ON LASSO PATH

0.6

TPP

0.8

1.0

0.2

0.4

0.6

0.8

TPP

Fig√ 6: Simulation setup: n = 250, p = 1000, β1 = · · · = β18 =
2.5 2 log p ≈ 9.3 (the other coefficients all vanish), σ 2 = 1 (with
noise) and σ 2 = 0 (no noise). Left: noisy case. True positive and false
positive rates along a single realization of the Lasso path. The least
squares path is obtained by ordering least squares estimates from a
model including the first 50 variables selected by the Lasso. Right:
mean FDP as a function of TPP. The mean FDP was obtained by
averaging over 500 independent trials.

Methods that are computationally efficient and also enjoy good model
performance in the linear sparsity regime would be highly desirable. (The
Lasso and the `0 method each enjoys one property but not the other.) While
it is beyond our scope to address this problem, we conclude the discussion
by considering marginal regression, a technique widely used in practice and
not computationally demanding. A simple analysis shows that marginal regression suffers from the same issue as the Lasso under our working hypothesis. To show this, examine the noiseless case (σ = 0) and assume
β1 = · · · = βk = M for some constant M > 0. It is easy to see that the
marginal statistic Xj> y for the jth variable is asymptotically distributed as
p
N (0, σ̃ 2 ), where σ̃ = M (k − 1)/n, if j is a true null and N (M, σ̃ 2 ) otherwise. In the linear sparsity regime, where k/n tends to a constant, the mean
shift M and standard deviation σ̃ have comparable magnitudes. As a result,
nulls and non-nulls are also interspersed on the marginal regression path, so
that we would have either high FDR or low power.
Acknowledgements. W. S. would like to thank Andrea Montanari for
helpful discussions. We thank Yuxin Chen for helpful comments about an
early version of the manuscript. Most of this research was performed while
W. S. was at Stanford University.

18

100
50

Rank of first false discovery

150

W. SU, M. BOGDAN, AND E. CANDÈS

●

●

●

●

●

● ● ● ● ● ●
●

●

●

●
● ●
●

●

● ● ●

●

0

●

●

●

●

●

●

●

0

50

100

150

Sparsity

Fig 7: Rank of the first false discovery. Here, n = p = 1000 and
β1 = · · · = βk = 50 for k ranging from 5 to 150 (βi = 0 for i > k). We
plot averages from 100 independent replicates and display the range
between minimal and maximal realized values. The vertical line is
placed at k = n/(2 log p) and the 45◦ line passing through the origin
is shown for convenience.

References.
[1] M. Bayati, M. Lelarge, and A. Montanari. Universality in polytope phase transitions
and message passing algorithms. The Annals of Applied Probability, 25(2):753–822,
2015.
[2] M. Bayati and A. Montanari. The dynamics of message passing on dense graphs,
with applications to compressed sensing. IEEE Trans. Inform. Theory, 57(2):764–
785, 2011.
[3] M. Bayati and A. Montanari. The Lasso risk for Gaussian matrices. IEEE Trans.
Inform. Theory, 58(4):1997–2017, 2012.
[4] R. Berk, B. Lawrence, A. Buja, K. Zhang, and L. Zhao. Valid post-selection inference.
Ann. Statist., 41(2):802–837, 2013.
[5] P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of Lasso and
Dantzig selector. The Annals of Statistics, pages 1705–1732, 2009.
[6] M. Bogdan, E. v. d. Berg, W. Su, and E. J. Candès. Supplementary material to
“Statistical estimation and testing via the ordered `1 norm”. Available at http:
//statweb.stanford.edu/~candes/papers/SortedL1_SM.pdf, 2013.
[7] P. Bühlmann. Invited discussion on ”regression shrinkage and selection via the lasso:
a retrospective (r. tibshirani)”. Journal of the Royal Statistical Society: Series B,
73:277–279, 2011.
[8] P. Bühlmann and van de Geer. Statistics for High-dimensional Data. Springer, New

FALSE DISCOVERIES ON LASSO PATH

19

York, 2011.
[9] E. J. Candès and T. Tao. Decoding by linear programming. IEEE Transactions on
Information Theory, 51(12):4203–4215, Dec. 2005.
[10] Y. Deshpande, E. Abbe, and A. Montanari. Asymptotic mutual information for the
two-groups stochastic block model. arXiv preprint arXiv:1507.08685, 2015.
[11] Y. Deshpande and A. Montanari. Information-theoretically optimal sparse PCA.
In IEEE International Symposium on Information Theory (ISIT), pages 2197–2201,
2014.
[12] D. L. Donoho, A. Maleki, and A. Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914–
18919, 2009.
[13] D. L. Donoho and A. Montanari. High dimensional robust M-estimation: Asymptotic
variance via approximate message passing. arXiv preprint arXiv:1310.7320, 2013.
[14] D. L. Donoho and A. Montanari. Variance breakdown of Huber (M)-estimators:
n/p → m ∈ (1, ∞). arXiv preprint arXiv:1503.02106, 2015.
[15] D. L. Donoho and J. Tanner. Observed universality of phase transitions in highdimensional geometry, with implications for modern data analysis and signal processing. Philosophical Trans. R. Soc. A, 367(1906):4273–4293, 2009.
[16] L. S. Eberlin et al. Molecular assessment of surgical-resection margins of gastric cancer by mass-spectrometric imaging. Proceedings of the National Academy of Sciences,
111(7):2436–2441, 2014.
[17] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. The
Annals of Statistics, 32(2):407–499, 2004.
[18] J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle
properties. Journal of the American Statistical Association, 96(456):1348–1360, 2001.
[19] J. Fan and R. Song. Sure independence screening in generalized linear models with
NP-dimensionality. The Annals of Statistics, 38(6):3567–3604, 2010.
[20] R. Foygel Barber and E. J. Candes. A knockoff filter for high-dimensional selective
inference. ArXiv e-prints, Feb. 2016.
[21] M. G’Sell, T. Hastie, and R. Tibshirani. False variable selection rates in regression.
ArXiv e-prints, 2013.
[22] P. Ji and Z. Zhao. Rate optimal multiple testing procedure in high-dimensional
regression. arXiv preprint arXiv:1404.2961, 2014.
[23] J. D. Lee, D. L. Sun, S. Y., and T. J. E. Exact post-selection inference, with application to the Lasso. Annals of Statistics, 44(2):802–837, 2016.
[24] W. Lee et al. A high-resolution atlas of nucleosome occupancy in yeast. Nature
genetics, 39(10):1235–1244, 2007.
[25] A. Maleki, L. Anitori, Z. Yang, and R. Baraniuk. Asymptotic analysis of complex
LASSO via complex approximate message passing (CAMP). IEEE Trans. Inform.
Theory, 59(7):4290–4308, 2013.
[26] A. Montanari and E. Richard. Non-negative principal component analysis: Message
passing algorithms and sharp asymptotics. arXiv preprint arXiv:1406.4775, 2014.
[27] A. Mousavi, A. Maleki, and R. G. Baraniuk. Asymptotic analysis of LASSO’s
solution path with implications for approximate message passing. arXiv preprint
arXiv:1309.5979, 2013.
[28] F. S. Paolo, H. A. Fricker, and L. Padman. Volume loss from Antarctic ice shelves is
accelerating. Science, 348(6232):327–331, 2015.
[29] P. Pokarowski and J. Mielniczuk. Combined `1 and greedy `0 penalized least squares
for linear model selection. Journal of Machine Learning Research, 16:991–992, 2015.
[30] G. Reeves and M. C. Gastpar. Approximate sparsity pattern recovery: Information-

20

W. SU, M. BOGDAN, AND E. CANDÈS

theoretic lower bounds. IEEE Trans. Inform. Theory, 59(6):3451–3465, 2013.
[31] F. Santosa and W. W. Symes. Linear inversion of band-limited reflection seismograms. SIAM Journal on Scientific and Statistical Computing, 7(4):1307–1330, 1986.
[32] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal
Statistical Society, Series B, 58(1):267–288, Feb. 1994.
[33] R. J. Tibshirani. The lasso problem and uniqueness. Electronic Journal of Statistics,
7:1456–1490, 2013.
[34] R. J. Tibshirani and J. Taylor. The solution path of the generalized lasso. The Annals
of Statistics, 39(3):1335–1371, 2011.
[35] R. J. Tibshirani, J. Taylor, R. Lockhart, and R. Tibshirani. Exact post-selection
inference for sequential regression procedures. ArXiv e-prints, 2014.
[36] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In
Compressed Sensing, Theory and Applications, 2012.
[37] M. J. Wainwright. Information-theoretic limits on sparsity recovery in the highdimensional and noisy setting. IEEE Trans. Inform. Theory, 55(12), 2009.
[38] M. J. Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using-constrained quadratic programming (lasso). IEEE Trans. Inform. Theory,
55(5):2183–2202, 2009.
[39] M. Yuan and Y. Lin. Model selection and estimation in regression with grouped
variables. Journal of the Royal Statistical Society, Series B, 68:49–67, 2006.
[40] Y. Yuan et al. Assessing the clinical utility of cancer genomic and proteomic data
across tumor types. Nature biotechnology, 32(7):644–652, 2014.
[41] C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. The
Annals of Statistics, 38(2):894–942, 2010.
[42] H. Zou. The adaptive lasso and its oracle properties. Journal of the American
Statistical Association, 101(476):1418–1429, 2006.
[43] H. Zou and T. Hastie. Regularization and variable selection via the elastic net.
Journal of the Royal Statistical Society, Series B, 67:301–320, 2005.

APPENDIX A: ROAD MAP TO THE PROOFS
In this section, we provide an overview of the proof of Theorem 2.1, presenting all the key steps and ingredients. Detailed proofs are distributed in
Appendices B–D. At a high level, the proof structure has the following three
elements:
1. Characterize the Lasso solution at a fixed λ asymptotically, predicting the (non-random) asymptotic values of the FDP and of the TPP
denoted by fdp∞ (λ) and tpp∞ (λ), respectively. These limits depend
depend on Π, δ,  and σ.
2. Exhibit uniform convergence over λ in the sense that
sup

P

|FDP(λ) − fdp∞ (λ)| −−→ 0,

λmin ≤λ≤λmax

and similarly for TPP(λ). A consequence is that in the limit, the
asymptotic trade-off between true and false positive rates is given by
the λ-parameterized curve (tpp∞ (λ), fdp∞ (λ)).

21

FALSE DISCOVERIES ON LASSO PATH

3. The trade-off curve from the last step depends on the prior Π. The
last step optimizes it by varying λ and Π.
Whereas the last two steps are new and present some technical challenges,
the first step is accomplished largely by resorting to off-the-shelf AMP theory. We now present each step in turn. Throughout this section we work
under our working hypothesis and take the noise level σ to be positive.
Step 1. First, Lemma A.1 below accurately predicts the asymptotic limits
of FDP and TPP at a fixed λ . This lemma is borrowed from [6], which
follows from Theorem 1.5 in [3] in a natural way, albeit with some effort
spent in resolving a continuity issue near the origin. Recall that ηt (·) is the
soft-thresholding operator defined as ηt (x) = sgn(x)(|x| − t)+ , and Π? is the
distribution of Π conditionally on being nonzero;
(
Π? ,
w.p. ,
Π=
0,
w.p. 1 − .
Denote by α0 the unique root of (1 + t2 )Φ(−t) − tφ(t) = δ/2.
Lemma A.1 (Theorem 1 in [6]; see also Theorem 1.5 in [3]).
solution with a fixed λ > 0 obeys
V (λ) P
−−→ 2(1 − )Φ(−α),
p

The Lasso

T (λ) P
−−→  · P(|Π? + τ W | > ατ ),
p

where W is N (0, 1) independent of Π, and τ > 0, α > max{α0 , 0} is the
unique solution to

(A.1)

1
τ 2 = σ 2 + E (ηατ (Π + τ W ) − Π)2
δ


1
λ = 1 − P(|Π + τ W | > ατ ) ατ.
δ

Note that both τ and α depend on λ.
We pause to briefly discuss how Lemma A.1 follows from Theorem 1.5
b is,
in [3]. There, it is rigorously proven that the joint distribution of (β, β)
in some sense, asymptotically the same as that of (β, ηατ (β + τ W )), where
W is a p-dimensional vector of i.i.d. standard normals independent of β,
and where the soft-thresholding operation acts in a componentwise fashion.
Roughly speaking, the Lasso estimate βbj looks like ηατ (βj + τ Wj ), so that

22

W. SU, M. BOGDAN, AND E. CANDÈS

we are applying soft thresholding at level ατ rather than λ and the noise
level is τ rather than σ. With these results in place, we informally obtain
V (λ)/p = #{j : βbj 6= 0, βj = 0}/p ≈ P(ηατ (Π + τ W ) 6= 0, Π = 0)
= (1 − ) P(|τ W | > ατ )
= 2(1 − ) Φ(−α).
Similarly, T (λ)/p ≈  P(|Π? + τ W | > ατ ). For details, we refer the reader
to Theorem 1 in [6].
Step 2. Our interest is to extend this convergence result uniformly over a
range of λ’s. The proof of this step is the subject of Section B.
Lemma A.2. For any fixed 0 < λmin < λmax , the convergence of V (λ)/p
and T (λ)/p in Lemma A.1 is uniform over λ ∈ [λmin , λmax ].
Hence, setting
td∞ (λ) :=  P(|Π? + τ W | > ατ )

fd∞ (λ) := 2(1 − )Φ(−α),

(A.2)
we have

sup
λmin ≤λ≤λmax

and
sup
λmin ≤λ≤λmax

V (λ)
P
− fd∞ (λ) −−→ 0,
p
T (λ)
P
− td∞ (λ) −−→ 0.
p

To exhibit the trade-off between FDP and TPP, we can therefore focus on the
far more amenable quantities fd∞ (λ) and td∞ (λ) instead of V (λ) and T (λ).
Since FDP(λ) = V (λ)/(V (λ) + T (λ)) and TPP(λ) = T (λ)/|{j : βj 6= 0}|,
this gives
P

|FDP(λ) − fdp∞ (λ)| −−→ 0,

sup

fdp∞ (λ) =

λmin ≤λ≤λmax

fd∞ (λ)
,
fd∞ (λ) + td∞ (λ)

and
sup
λmin ≤λ≤λmax

P

|TPP(λ) − tpp∞ (λ)| −−→ 0,

tpp∞ (λ) =

td∞ (λ)
,


so that fdp∞ (λ) and tpp∞ (λ) are the predicted FDP and TPP. (We shall
often hide the dependence on λ.)

FALSE DISCOVERIES ON LASSO PATH

23

Step 3. As remarked earlier, both tpp∞ (λ) and fdp∞ (λ) depend on Π, δ, 
and σ. In Appendix C, we will see that we can parameterize the tradeoff curve (tpp∞ (λ), fdp∞ (λ)) by the true positive rate so that there is a
function q Π obeying q Π (tpp∞ ) = fdp∞ ; furthermore, this function depends
on Π and σ only through Π/σ. Therefore, realizations of the FDP-TPP pair
fall asymptotically arbitrarily close to q Π . It remains to optimize the curve
q Π over Π/σ. Specifically, the last step in Appendix C characterizes the
envelope q ? formally given as
q ? (u; δ, ) = inf q Π (u; δ, ),
where the infimum is taken over all feasible priors Π. The key ingredient in
optimizing the trade-off is given by Lemma C.1.
Taken together, these three steps sketch the basic strategy for proving
Theorem 2.1, and the remainder of the proof is finally carried out in Appendix D. In particular, we also establish the noiseless result (σ = 0) by
using a sequence of approximating problems with noise levels approaching
zero.
APPENDIX B: FOR ALL VALUES OF λ SIMULTANEOUSY
In this section we aim to prove Lemma A.2 and, for the moment, take σ >
0. Also, we shall frequently use results in [3], notably, Theorem 1.5, Lemma
3.1, Lemma 3.2, and Proposition 3.6 therein. Having said this, most of our
proofs are rather self-contained, and the strategies accessible to readers who
have not yet read [3]. We start by stating two auxiliary lemmas below, whose
proofs are deferred to Section B.1.
Lemma B.1. For any c > 0, there exists a constant rc > 0 such that for
any arbitrary r > rc ,


r
sup # 1 ≤ j ≤ p : |Xj> u| > √
≤ cp
n
kuk=1
holds with probability tending to one.
A key ingredient in the proof of Lemma A.2 is, in a certain sense, the unib
form continuity of the support of β(λ).
This step is justified by the auxiliary
lemma below which demonstrates that the Lasso estimates are uniformly
continuous in `2 norm.

24

W. SU, M. BOGDAN, AND E. CANDÈS

Lemma B.2. Fixe 0 < λmin < λmax . Then there is a constant c such for
any λ− < λ+ in [λmin , λmax ],
sup
λ− ≤λ≤λ+

p
b
b − ) ≤ c (λ+ − λ− )p
β(λ)
− β(λ

holds with probability tending to one.
Proof of Lemma A.2. We prove the uniform convergence of V (λ)/p
and similar arguments apply to T (λ)/p. To begin with, let λmin = λ0 <
λ1 < · · · < λm = λmax be equally spaced points and set ∆ := λi+1 − λi =
(λmax − λmin )/m; the number of knots m shall be specified later. It follows
from Lemma A.1 that
(B.1)

P

max |V (λi )/p − fd∞ (λi )| −−→ 0

0≤i≤m

by a union bound. Now, according to Corollary 1.7 from [3], the solution α
to equation (A.1) is continuous in λ and, therefore, fd∞ (λ) is also continuous
on [λmin , λmax ] . Thus, for any constant ω > 0, the equation
|fd∞ (λ) − fd∞ (λ0 )| ≤ ω

(B.2)

holds for all λmin ≤ λ, λ0 ≤ λmax satisfying |λ − λ0 | ≤ 1/m provided m is
sufficiently large. We now aim to show that if m is sufficiently large (but
fixed), then
(B.3)

max

sup

0≤i<m λi ≤λ≤λi+1

|V (λ)/p − V (λi )/p| ≤ ω

holds with probability approaching one as p → ∞. Since ω is arbitrary small,
combining (B.1), (B.2), and (B.3) gives uniform convergence by applying the
triangle inequality.
b
Let S(λ) be a short-hand for supp(β(λ)).
Fix 0 ≤ i < m and put λ− = λi
+
−
+
and λ = λi+1 . For any λ ∈ [λ , λ ],
(B.4)

|V (λ) − V (λ− )| ≤ |S(λ) \ S(λ− )| + |S(λ− ) \ S(λ)|.

Hence, it suffices to give upper bound about the sizes of S(λ) \ S(λ− ) and
S(λ− ) \ S(λ). We start with |S(λ) \ S(λ− )|.
The KKT optimality conditions for the Lasso solution state that there
b
exists a subgradient g(λ) ∈ ∂kβ(λ)k
1 obeying
b
X > (y − X β(λ))
= λg(λ)

FALSE DISCOVERIES ON LASSO PATH

25

for each λ. Note that gj (λ) = ±1 if j ∈ S(λ). As mentioned earlier, our
strategy is to establish some sort of continuity of the KKT conditions with
respect to λ. To this end, let


b
b −)
X β(λ)
− β(λ


u=
b
b −)
X β(λ)
− β(λ
be a point in Rn with unit `2 norm. Then for each j ∈ S(λ) \ S(λ− ), we have
|Xj> u| =

b
b − ))
Xj> X(β(λ)
− β(λ
b
b − ))k
kX(β(λ)
− β(λ

=

|λgj (λ) − λ− gj (λ− )|
λ − λ− |gj (λ− )|
≥
.
b
b − ))k
b
b − ))k
kX(β(λ)
− β(λ
kX(β(λ)
− β(λ

Now, given an arbitrary constant a > 0 to be determined later, either
|gj (λ− )| ∈ [1 − a, 1) or |gj (λ− )| ∈ [0, 1 − a). In the first case ((a) below) note
that we exclude |gj (λ− )| = 1 because for random designs, when j ∈
/ S(λ)
>
−
−
b
the equality |Xj (y − X β(λ ))| = λ can only hold with zero probability
(see e.g. [33]). Hence, at least one of the following statements hold:
b − ))| = λ− |gj (λ− )| ∈ [(1 − a)λ− , λ− );
(a) |Xj> (y − X β(λ
(b) |Xj> u| ≥

λ−(1−a)λ−
b
b − ))k
kX(β(λ)−
β(λ

>

aλ−
b
b − ))k .
kX(β(λ)−
β(λ

In the second case, since the spectral norm σmax (X) is bounded in probability (see e.g. [36]), we make use of Lemma B.2 to conclude that
aλ−

aλ−
aλ−
p
≥ c0 a
≥
≥
+
−
−
−
b
b
b
b
cσmax (X) (λ − λ )p
kX(β(λ) − β(λ ))k
σmax (X)kβ(λ) − β(λ )k
holds for all λ− ≤ λ ≤ λ+ with probability tending to one. Above, the
constant c0 only depends on λmin , λmax , δ and Π. Consequently, we see that
sup
λ− ≤λ≤λ+

o
n
b − ))| < λ−
S(λ) \ S(λ− ) ≤ # j : (1 − a)λ− ≤ |Xj> (y − X β(λ
o
n
p
+ # j : |Xj> u| > c0 a m/n .

Equality (3.21) of [3] guarantees the existence of a constant a such that the
event5
n
o
b − ))| < λ− ≤ ωp
(B.5)
# j : (1 − a)λ− ≤ |Xj> (y − X β(λ
4
5

Apply Theorem 1.8 to carry over the results for AMP iterates to Lasso solution.

r

m
n

26

W. SU, M. BOGDAN, AND E. CANDÈS

happens with probability approaching one. Since λ− = λi is always in the
interval [λmin , λmax ], the constant a can be made to be independent of the
index i. For the second term, it follows from Lemma B.1 that for sufficiently
large m, the event
n
o ωp
p
>
0
(B.6)
# j : |Xj u| > c a m/n ≤
4
also holds with probability approaching one. Combining (B.5) and (B.6), we
get
(B.7)

sup

S(λ) \ S(λ− ) ≤

λ− ≤λ≤λ+

ωp
2

holds with probability tending to one.
Next, we bound |S(λ− ) \ S(λ)|. Applying Theorem 1.5 in [3], we can find
a constant ν > 0 independent of λ− ∈ [λmin , λmax ] such that
n
o ωp
(B.8)
# j : 0 < |βbj (λ− )| < ν ≤
4
happens with probability approaching one. Furthermore, the simple inequality
n
o
b
b − )k2 ≥ ν 2 # j : j ∈ S(λ− ) \ S(λ), |βbj (λ− )| ≥ ν ,
kβ(λ)
− β(λ
together with Lemma B.2, give
(B.9)
n
o kβ(λ)
b
b − )k2
− β(λ
c2 (λ+ − λ− )p
# j : j ∈ S(λ− ) \ S(λ), |βbj (λ− )| ≥ ν ≤
≤
ν2
ν2
for all λ ∈ [λmin , λmax ] with probability converging to one. Taking m sufficiently large such that λ+ − λ− = (λmax − λmin )/m ≤ ων 2 /4c2 in (B.9) and
combining this with (B.8) gives that
(B.10)

sup
λ− ≤λ≤λ+

S(λ− ) \ S(λ) ≤

ωp
2

holds with probability tending to one.
To conclude the proof, note that both (B.7) and (B.10) hold for a large
but fixed m. Substituting these two inequalities into (B.4) confirms (B.3) by
taking a union bound.
As far as the true discovery number T (λ) is concerned, all the arguments
seamlessly apply and we do not repeat them. This terminates the proof.

FALSE DISCOVERIES ON LASSO PATH

27

B.1. Proofs of auxiliary lemmas. In this section, we prove Lemmas B.1 and B.2. While the proof of the first is straightforward, the second
crucially relies on Lemma B.5, whose proof makes use of Lemmas B.3 and
B.4. Hereafter, we denote by oP (1) any random variable which tends to zero
in probability.
Proof of Lemma B.1. Since


r2
r
>
2
>
ku Xk ≥ # 1 ≤ j ≤ p : |Xj u| > √
,
n
n
we have


r
nσmax (X)2 kuk2
n
>
# 1 ≤ j ≤ p : |Xj u| > √
≤ 2 ku> Xk2 ≤
r
r2
n
√ 2
(1 + δ) p
,
= (1 + oP (1))
r2
−1/2
where we make use of lim n/p = δ and σmax (X) =
√ 1 + δ √ + oP (1). To
complete the proof, take any rc > 0 such that (1 + δ)/rc < c.

Lemma B.3. Take a sequence a1 ≥ a2 ≥ · · · ≥ ap ≥ 0 with at least one
strict inequality, and suppose that
P
p pi=1 a2i
P
2 ≥M
( pi=1 ai )
for some M > 1. Then for any 1 ≤ s ≤ p,
Ps
a2i
p3
Pi=1
≥
1
−
.
p
2
M s3
i=1 ai
Proof of Lemma B.3. By the monotonicity of a,
Pp
Ps
2
a2
i=1 ai
≥ i=1 i ,
s
p
which implies
(B.11)

P
P
s pi=1 a2i
p si=1 a2i
sM
Ps
2 ≥ Pp
2 ≥ p .
( i=1 ai )
( i=1 ai )

28

W. SU, M. BOGDAN, AND E. CANDÈS

Similarly,
p
X

(B.12)

a2i

 Ps

i=1 ai

≤ (p − s)

2

s

i=s+1

and it follows from (B.11) and (B.12) that
Ps
a2i
Pi=1
p
2 ≥ P
s
i=1 ai

sM
p2

Ps

2
i=1 ai

2
i=1 ai

+ (p − s)

 Ps

i=1

ai

2 ≥

s

sM
p2

+

p−s
s2

≥1−

p3
.
M s3

Lemma B.4. Assume n/p → 1, i.e. δ = 1. Suppose s obeys s/p → 0.01.
Then with probability tending to one, the smallest singular value obeys
1
min σmin (XS ) ≥ ,
2
|S|=s
where the minimization is over all subsets of {1, . . . , p} of cardinality s.
Proof of Lemma B.4. For a fixed S, we have


p
2
P σmin (XS ) < 1 − s/n − t ≤ e−nt /2
for all t ≥ 0, please see[36]. The claim follows from plugging t = 0.399 and
a union bound over ps ≤ exp(pH(s/p)) subsets, where H(q) = −q log q −
(1 − q) log(1 − q). We omit the details.
The next lemma bounds the Lasso solution in `2 norm uniformly over λ.
We use some ideas from the proof of Lemma 3.2 in [3].
Lemma B.5. Given any positive constants λmin < λmax , there exists a
constant C such that
!
√
b
P
sup
kβ(λ)k
≤ C p → 1.
λmin ≤λ≤λmax

Proof of Lemma B.5. For simplicity, we omit the dependency of βb on
λ when clear from context. We first consider the case where δ < 1. Write
b + P2 (β),
b where P1 (β)
b is the projection of βb onto the null space
βb = P1 (β)
b is the projection of βb onto the row space of X. By the
of X and P2 (β)

FALSE DISCOVERIES ON LASSO PATH

29

rotational invariance of i.i.d. Gaussian vectors, the null space of X is a random subspace of dimension p − n = (1 − δ + o(1))p with uniform orientation.
b belongs to the null space, Kashin’s Theorem (see Theorem F.1
Since P1 (β)
in [3]) gives that with probability at least 1 − 2−p ,

(B.13)

b 2 = kP1 (β)k
b 2 + kP2 (β)k
b 2
kβk
b 2
kP1 (β)k
1
b 2
≤ c1
+ kP2 (β)k
p
b 2 + kP2 (β)k
b 2
kβk
1
1
b 2
≤ 2c1
+ kP2 (β)k
p
b 2
2c1 kβk
1
b 2
≤
+ (1 + 2c1 )kP2 (β)k
p

for some constant c1 depending only on δ; the first step uses Kashin’s theorem, the second the triangle inequality, and the third Cauchy-Schwarz inequality. The smallest√nonzero singular value of the Wishart matrix X > X
is concentrated at (1/ δ −1)2 with probability tending to one (see e.g. [36]).
b belongs to the row space of X, we have
In addition, since P2 (β)
b 2 ≤ c2 kXP2 (β)k
b 2
kP2 (β)k
√
with probability approaching one. Above, c2 can be chosen to be (1/ δ −
1)−2 + o(1). Set c3 = c2 (1 + 2c1 ). Continuing (B.13) yields
b 2≤
kβk
=
≤

≤
≤

b 2
2c1 kβk
1
b 2
+ c2 (1 + 2c1 )kXP2 (β)k
p
b 2
2c1 kβk
1
b 2
+ c3 kX βk
p
b 2
2c1 kβk
1
b 2 + 2c3 kyk2
+ 2c3 ky − X βk
p

2
1


2
b
b
2c1 2 ky − X βk + λkβk1
1
2
b + λkβk
b 1 + 2c3 kyk2
+ 4c3
ky − X βk
λ2 p
2
c1 kyk4
+ 4c3 kyk2 ,
2λ2 p

b 2 + λkβk
b 1 ≤ 1 kyk2 .
where in the last inequality we use the fact 12 ky − X βk
2
2
Thus, it suffices to bound
kyk . The largest singular value of X > X is
√
bounded above by (1/ δ + 1)2 + oP (1). Therefore,
kyk2 = kXβ + zk2 ≤ 2kXβk2 + 2kzk2 ≤ c4 kβk2 + 2kzk2 .

30

W. SU, M. BOGDAN, AND E. CANDÈS

Since both βi and zi have bounded second moments, the law of large numbers
claims that there exists a constant c5 such that c4 kβk2 + 2kzk2 ≤ c5 p with
probability approaching one. Combining all the inequalities above gives


c1 c25 p
c1 c25
2
b
sup
kβ(λ)k ≤
+ 2c3 c5 p
+ 2c3 c5 p ≤
2λ2
2λ2min
λmin ≤λ≤λmax
with probability converging to one.
b = 0.
In the case where δ > 1, the null space of X reduces to 0, hence P1 (β)
Therefore, this reduces to a special case of the above argument.
Now, we turn to work on the case where δ = 1. We start with
b 2 ≤ 2kyk2 + 2ky − X βk
b 2
kX βk
and

1
b 2 + λkβk
b 1 ≤ 1 kyk2 .
ky − X βk
2
2
These two inequalities give that simultaneously over all λ,
2
b
kX β(λ)k
≤ 4kyk2 ≤ 4c5 p
1
c5 p
b
kβ(λ)k
kyk2 ≤
1 ≤
2λmin
2λmin

(B.14a)
(B.14b)

with probability converging to one. Let M be any constant larger than 1.7 ×
b 2 /kβk
b 2 < M , by (B.14b), we get
107 . If pkβk
1
√
b ≤ M c5 √p.
(B.15)
kβk
2λmin
Otherwise, denoting by T the set of indices 1 ≤ i ≤ p that correspond to
b i , from Lemma B.3 we have
the s := dp/100e largest |β|
p3
kβbT k2
106
≥1−
≥
1
−
.
b 2
M s3
M
kβk

(B.16)
To proceed, note that

b = kXT βbT + X βb k
kX βk
T T
b
≥ kXT βT k − kXT βbT k
≥ kXT βbT k − σmax (X)kβbT k.

FALSE DISCOVERIES ON LASSO PATH

31

By Lemma B.4, we get kXT βbT k ≥ 12 kβT k, and it is also clear that σmax (X) =
2 + oP (1). Thus, by (B.16) we obtain
b ≥ kXT βbT k − σmax (X)kβb k ≥ 1 kβbT k − (2 + oP (1))kβb k
kX βk
T
T
2r
r
1
106 b
106 b
≥
1−
kβk − (2 + oP (1))
kβk
2
M
M
b
= (c + oP (1))kβk,
where c =

1
2

p
p
1 − 106 /M − 2 106 /M > 0. Hence, owing to (B.14a),
√
(2 + oP (1)) c5 √
b
kβk ≤
p
c

(B.17)

In summary, with probability tending to one, in either case, namely, (B.15)
or (B.17),
b ≤ C √p
kβk
for come constant C. This holds uniformly for all λ ∈ [λmin , λmax ], and thus
completes the proof.

Now, we conclude this section by proving our main lemma.
Proof of Lemma B.2. The proof extensively applies Lemma 3.16 in [3]
b
b − ) be the notations in the
and Lemma B.5. Let x + r = β(λ)
and x = β(λ
statement of Lemma 3.1 in [3]. Among the fives assumptions needed in that
lemma, it suffices to verify the first, third and fourth. Lemma B.5 asserts
that
b
b − )k ≤ 2A√p
sup kr(λ)k = sup kβ(λ)
− β(λ
λ− ≤λ≤λ+

λ− ≤λ≤λ+

with probability approaching one. This fulfills the first assumption by taking
b − )k1 obey
c1 = 2A. Next, let g(λ− ) ∈ ∂kβ(λ
b − )) = λ− g(λ− ).
X > (y − X β(λ
Hence,
b − )) + λg(λ− ) = (λ − λ− )kg(λ− )k ≤ (λ+ − λ− )√p
−X > (y − X β(λ
√
The conclusion of this lemma, krk ≤ pξ(, c1 , . . . , c5 ) in our notation, can be effort√
√
lessly strengthened to krk ≤ (  + /λ)ξ(c1 , . . . , c5 ) p.
6

32

W. SU, M. BOGDAN, AND E. CANDÈS

which certifies the third assumption. To verify the fourth assumption, taking
t → ∞ in Proposition 3.6 of [3] ensures the existence of constants c2 , c3
and c4 such that, with probability tending to one, σmin (XT ∪T 0 ) ≥ c4 for
T = {j : |gj (λ− )| ≥ 1 − c2 } and arbitrary T 0 ⊂ {1, . . . , p} with |T 0 | ≤ c3 p.
Further, these constants can be independent of λ− since λ− ∈ [λmin , λmax ]
belongs to a compact interval. Therefore, this lemma concludes that, with
probability approaching one,

p
λ − λ−
√
−
−
b
b
ξ p
λ−λ +
sup kβ(λ) − β(λ )k ≤ sup
λ
−
+
−
+
λ ≤λ≤λ
λ ≤λ≤λ

p
λ+ − λ−
√
+
−
ξ p
≤
λ −λ +
λmin
p

=O
(λ+ − λ− )p .
This finishes the proof.
APPENDIX C: OPTIMIZING THE TRADE-OFF
In this section, we still work under our working hypothesis and σ > 0.
Fixing δ and , we aim to show that no pairs below the boundary curve can
be realized. Owing to the uniform convergence established in Appendix B, it
is sufficient to study the range of (tpp∞ (λ), fdp∞ (λ)) introduced in Appendix
A by varying Π? and λ. To this end, we introduce a useful trick based on
the following lemma.
Lemma C.1. For any fixed α > 0, define a function y = f (x) in the
parametric form:
x(t) = P(|t + W | > α)
y(t) = E (ηα (t + W ) − t)2
for t ≥ 0, where W is a standard normal. Then f is strictly concave.
We use this to simplify the problem of detecting feasible pairs (tpp∞ , fdp∞ ).
Denote by π ? := Π? /τ . Then (A.1) implies
(C.1)

(1 − ) E ηα (W )2 +  E(ηα (π ? + W ) − π ? )2 < δ,
(1 − ) P(|W | > α) +  P(|π ? + W | > α) < min{δ, 1}.

We emphasize that (C.1) is not only necessary, but also sufficient in the
following sense: given 0 < δ1 < δ, 0 < δ2 < min{δ, 1} and π ? , we can solve
for τ by setting
(1 − ) E ηα (W )2 +  E(ηα (π ? + W ) − π ? )2 = δ1

FALSE DISCOVERIES ON LASSO PATH

33

and making use of the first line of (A.1), which can be alternatively written
as

τ2 
(1 − ) E ηα (W )2 +  E(ηα (π ? + W ) − π ? )2 .
τ 2 = σ2 +
δ
(Π? = τ π ? is also determined, so does Π),7 and along with
(1 − ) P(|W | > α) +  P(|π ? + W | > α) = δ2 ,
λ is also uniquely determined.
Since (C.1) is invariant if π ? is replaced by |π ? |, we assume π ? ≥ 0 without
loss of generality. As a function of t, P(|t + W | > α) attains the minimum
P(|W | > α) = 2Φ(−α) at t = 0, and the supremum equal to one at t = ∞.
Hence, there must exist 0 ∈ (0, 1) obeying
(C.2)

P(|π ? + W | > α) = (1 − 0 ) P(|W | > α) + 0 .

As a consequence, the predicted TPP and FDP can be alternatively expressed as
(C.3)

tpp∞ = 2(1 − 0 )Φ(−α) + 0 ,

fdp∞ =

2(1 − )Φ(−α)
.
2(1 − 0 )Φ(−α) + 0

Compared to the original formulation, this expression is preferred since it
only involves scalars.
Now, we seek equations that govern 0 and α, given δ and . Since both
E(ηα (t + W ) − t)2 and P(|t + W | > α) are monotonically increasing with
respect to t ≥ 0, there exists a function f obeying
E(ηα (t + W ) − t)2 = f (P(|t + W | > α)) .
Lemma C.1 states that f is concave. Then
E(ηα (π ? + W ) − π ? )2 = f (P(|π ? + W | > α)
and (C.2) allows us to view the argument of f in the right-hand side as an
average of a random variable taking value P(|W | > α) with probability 1−0
and value one with probability 0 . Therefore, Jensen’s inequality states that
E(ηα (π ? +W )−π ? )2 ≥ (1−0 )f (P(|W | > α))+0 f (1) = (1−0 ) E ηα (W )2 +0 (α2 +1).
7

Not every pair (δ1 , δ2 ) ∈ (0, δ) × (0, min{δ, 1}) is feasible below the Donoho-Tanner
phase transition. Nevertheless, this does not affect our discussion.

34

W. SU, M. BOGDAN, AND E. CANDÈS

Combining this with (C.1) gives
(C.4a)

(1 − 0 ) E ηα (W )2 + 0 (α2 + 1) < δ,

(C.4b)

(1 − 0 ) P(|W | > α) + 0 < min{δ, 1}.

Similar to (C.1), (C.4) is also sufficient in the same sense, and (C.4b) is
automatically satisfied if δ > 1.
The remaining part of this section studies the range of (tpp∞ , fdp∞ ) given
by (C.3) under the constraints (C.4). Before delving into the details, we
remark that this reduction of π ? to a two-point prior is realized by setting
π ? = ∞ (equivalently Π? = ∞) with probability 0 and otherwise +0, where
+0 is considered to be nonzero. Though this prior is not valid since the
working hypothesis requires a finite second moment, it can nevertheless be
approximated by a sequence of instances, please see the example given in
Section 2.
The lemma below recognizes that for certain (δ, ) pairs, the TPP is
asymptotically bounded above away from 1.
Lemma C.2.
?

Put

u (δ, ) :=

(
1−

(1−δ)(−? )
(1−? ) ,

1,

δ < 1 and  > ? (δ),
otherwise.

Then
tpp∞ < u? (δ, ).
Moreover, tpp∞ can be arbitrarily close to u? .
This lemma directly implies that above the Donoho-Tanner phase transition (i.e. δ < 1 and  > ? (δ)), there is a fundamental limit on the TPP for
arbitrarily strong signals. Consider


(C.5)
2(1 − ) (1 + t2 )Φ(−t) − tφ(t) + (1 + t2 ) = δ.
For δ < 1, ? is the only positive constant in (0, 1) such that (C.5) with
 = ? has a unique positive root. Alternatively, the function ? = ? (δ) is
implicitly given in the following parametric form:
2φ(t)
2φ(t) + t(2Φ(t) − 1)
2φ(t) − 2tΦ(−t)
? =
2φ(t) + t(2Φ(t) − 1)
δ=

FALSE DISCOVERIES ON LASSO PATH

35

for t > 0, from which we see that ? < δ < 1. Take the sparsity level k such
as ? p < k < δp = n, from which we have u? < 1. As a result, the Lasso
is unable to select all the k true signals even when the signal strength is
arbitrarily high. This is happening even though the Lasso has the chance to
select up to n > k variables.
Any u between 0 and u? (non-inclusive) can be realized as tpp∞ . Recall
that we denote by t? (u) the unique root in (α0 , ∞) (α0 is the root of (1 +
t2 )Φ(−t) − tφ(t) = δ/2) to the equation


2(1 − ) (1 + t2 )Φ(−t) − tφ(t) + (1 + t2 ) − δ
1−u
(C.6)
=
.
 [(1 + t2 )(1 − 2Φ(−t)) + 2tφ(t)]
1 − 2Φ(−t)
For a proof of this fact, we refer to Lemma C.4. Last, recall that
q ? (u; δ, ) =

2(1 − )Φ(−t? (u))
.
2(1 − )Φ(−t? (u)) + u

We can now state the fundamental trade-off between fdp∞ and tpp∞ .
Lemma C.3.

If tpp∞ ≥ u for u ∈ (0, u? ), then
fdp∞ > q ? (u).

In addition, fdp∞ can be arbitrarily close to q ? (u).
C.1. Proofs of Lemmas C.1, C.2 and C.3.
Proof of Lemma C.1. First of all, f is well-defined since both x(t) and
y(t) are strictly increasing functions of t. Note that
dx
= φ(α − t) − φ(−α − t),
dt

dy
= 2t [Φ(α − t) − Φ(−α − t)] .
dt

Applying the chain rule gives
dy . dx
2t [Φ(α − t) − Φ(−α − t)]
=
dt dt
φ(α − t) − φ(−α − t)
R α−t − u2
Rα
(u−t)2
2t −α−t e 2 du
2t −α e− 2 du
=
=
(α−t)2
(−α−t)2
α2 +t2 −2αt
α2 +t2 +2αt
− 2
−
2
2
2
e−
− e−
e
−e
2
2
R
α2 R α
u2
α
u
α
2te 2 −α e− 2 etu du
2e 2 0 e− 2 (etu + e−tu )du
R
=
=
.
α tu
−tu du
eαt − e−αt
0 e +e

f 0 (t) =

36

W. SU, M. BOGDAN, AND E. CANDÈS

Since x(t) is strictly increasing in t, we see that f 00 (t) ≤ 0 is equivalent to
saying that the function
Rα
g(t) :=

0

u2

e− 2 (etu + e−tu )du
Rα
≡
tu
−tu du
0 e +e

R α − u2
2 cosh(tu)du
0 Re
α
0 cosh(tu)du

is decreasing in t. Hence, it suffices to show that
0

g (t) =

Rα
0

e−

u2
2

u sinh(tu)du

Rα
0

R α u2
Rα
cosh(tv)dv − 0 e− 2 cosh(tu)du 0 v sinh(tv)dv
≤ 0.
2
Rα
cosh(tv)dv
0

Observe that the numerator is equal to
Z αZ α
Z αZ α
2
u2
− u2
u sinh(tu) cosh(tv)dudv −
e− 2 v cosh(tu) sinh(tv)dudv
e
0
0
0
0
Z αZ α
2
− u2
(u sinh(tu) cosh(tv) − v cosh(tu) sinh(tv)) dudv
=
e
0
0
Z αZ α
v2
u↔v
=
e− 2 (v sinh(tv) cosh(tu) − u cosh(tv) sinh(tu)) dvdu
Z0 Z0
v2
1 α α − u2
(e 2 − e− 2 ) (u sinh(tu) cosh(tv) − v cosh(tu) sinh(tv)) dudv.
=
2 0 0
Then it is sufficient to show that
(e−

u2
2

− e−

v2
2

) (u sinh(tu) cosh(tv) − v cosh(tu) sinh(tv)) ≤ 0

for all u, v, t ≥ 0. To see this, suppose u ≥ v without loss of generality so
that e−

u2
2

− e−

v2
2

≤ 0 and

u sinh(tu) cosh(tv) − v cosh(tu) sinh(tv) ≥ v(sinh(tu) cosh(tv) − cosh(tu) sinh(tv))
= v sinh(tu − tv) ≥ 0.
This analysis further reveals that f 00 (t) < 0 for t > 0. Hence, f is strictly
concave.
To prove the other two lemmas, we collect some useful facts about (C.5).
This equation has (a) one positive root for δ ≥ 1 or δ < 1,  = ? , (b)
two positive roots for δ < 1 and  < ? , and (c) no positive root if δ <
1 and  > ? . In the case of (a) and (b), call t(, δ) the positive root
of (C.5) (choose the larger one if there are two). Then t(, δ) is a decreasing function of . In particular,
t(, δ) → ∞ as  → 0. In addition,

2(1 − ) (1 + t2 )Φ(−t) − tφ(t) + (1 + t2 ) > δ if t > t(, δ).

FALSE DISCOVERIES ON LASSO PATH

37

Lemma C.4. For any 0 < u < u? , (C.6) has a unique root, denoted by
in (α0 , ∞). In addition, t? (u) strictly decreases as u increases, and it
further obeys 0 < (1 − u)/(1 − 2Φ(−t? (u))) < 1.
t? (u),

Lemma C.5.

As a function of u,
q ? (u) =

2(1 − )Φ(−t? (u))
2(1 − )Φ(−t? (u)) + u

is strictly increasing on (0, u? ).
Proof of Lemma C.2. We first consider the regime: δ < 1,  > ? . By
(C.3), it is sufficient to show that tpp∞ = 2(1 − 0 )Φ(−α) + 0 < u? under
the constraints (C.4). From (C.4b) it follows that
Φ(−α) =

1
δ − 0
P(|W | > α) <
,
2
2(1 − 0 )

which can be rearranged as
2(1 − 0 )Φ(−α) + 0 <

(1 − 0 )(δ − 0 )
+ 0 .
1 − 0

The right-hand side is an increasing function of 0 because its derivative is
equal to (1 − )(1 − δ)/(1 − 0 )2 and is positive. Since the range of 0 is
(0, ? /), we get
2(1 − 0 )Φ(−α) + 0 <

(1 − ? /)(δ −  · ? /)
+ ? / = u? .
1 −  · ? /

This bound u? can be arbitrarily √
approached: let 0 = ? / in the example
given in Section 2.5; then set λ = M and take M → ∞.
We turn our attention to the easier case where δ ≥ 1, or δ < 1 and  ≤ ? .
By definition, the upper limit u? = 1 trivially holds. It remains to argue that
tpp∞ can be arbitrarily close to 1. To see this, set Π? = M almost surely,
and take the same limits as before: then tpp∞ → 1.

Proof of Lemma C.3. We begin by first considering the boundary case:
tpp∞ = u.

(C.7)
In view of (C.3), we can write
fdp∞ =

2(1 − )Φ(−α)
2(1 − )Φ(−α)
=
.
∞
2(1 − )Φ(−α) + tpp
2(1 − )Φ(−α) + u

38

W. SU, M. BOGDAN, AND E. CANDÈS

Therefore, a lower bound on fdp∞ is equivalent to maximizing α under the
constraints (C.4) and (C.7).
Recall E ηα (W )2 = 2(1+α2 )Φ(−α)−2αφ(α). Then from (C.7) and (C.4a)
we obtain a sandwiching expression for 1 − 0 :


(1 − ) 2(1 + α2 )Φ(−α) − 2αφ(α) + (1 + α2 ) − δ
1−u
< 1 − 0 =
,
 [(1 + α2 )(1 − 2Φ(−α)) + 2αφ(α)]
1 − 2Φ(−α)
which implies


(1 − ) 2(1 + α2 )Φ(−α) − 2αφ(α) + (1 + α2 ) − δ
1−u
−
< 0.
2
 [(1 + α )(1 − 2Φ(−α)) + 2αφ(α)]
1 − 2Φ(−α)
The left-hand side of this display tends to 1 − (1 − u) = u > 0 as α → ∞,
and takes on the value 0 if α = t? (u). Hence, by the uniqueness of t? (u)
provided by Lemma C.4, we get α < t? (u). In conclusion,
(C.8)

fdp∞ =

2(1 − )Φ(−t? (u))
2(1 − )Φ(−α)
>
= q ? (u).
2(1 − )Φ(−α) + u
2(1 − )Φ(−t? (u)) + u

It is easy to see that fdp∞ can be arbitrarily close to q ? (u).
To finish the proof, we proceed to consider the general case tpp∞ = u0 > u.
The previous discussion clearly remains valid, and hence (C.8) holds if u is
replaced by u0 ; that is, we have
fdp∞ > q ? (u0 ).
By Lemma C.5, it follows from the monotonicity of q ? (·) that q ? (u0 ) > q ? (u).
Hence, fdp∞ > q ? (u), as desired.

C.2. Proofs of auxiliary lemmas.
Proof of Lemma C.4. Set


2(1 − ) (1 + t2 )Φ(−t) − tφ(t) + (1 + t2 ) − δ
ζ := 1 −
 [(1 + t2 )(1 − 2Φ(−t)) + 2tφ(t)]
or, equivalently,
(C.9)



2(1 − ζ) (1 + t2 )Φ(−t) − tφ(t) + ζ(1 + t2 ) = δ.

As in Section C.1, we abuse notation a little and let t(ζ) = t(ζ, δ) denote
the (larger) positive root of (C.9). Then the discussion about (C.5) in Section C.1 shows that t(ζ) decreases as ζ increases. Note that in the case where

FALSE DISCOVERIES ON LASSO PATH

39

δ < 1 and  > ? (δ), the range of ζ in (C.9) is assumed to be (0, ? /), since
otherwise (C.9) does not have a positive root (by convention, set ? (δ) = 1
if δ > 1).
Note that (C.6) is equivalent to


2(1 − ) (1 + t2 )Φ(−t) − tφ(t) + (1 + t2 ) − δ
(C.10)
u=1−
.
 [(1 + t2 )(1 − 2Φ(−t)) + 2tφ(t)] /(1 − 2Φ(−t))
Define


2(1 − ) (1 + t(ζ)2 )Φ(−t(ζ)) − t(ζ)φ(t(ζ)) + (1 + t(ζ)2 ) − δ
h(ζ) = 1 −
.
 [(1 + t(ζ)2 )(1 − 2Φ(−t(ζ))) + 2t(ζ)φ(t(ζ))] /(1 − 2Φ(−t(ζ)))
In view of (C.9) and (C.10), the proof of this lemma would be completed
once we show the existence of ζ such that h(ζ) = u. Now we prove this fact.
On the one hand, as ζ & 0, we see t(ζ) % ∞. This leads to
h(ζ) → 0.
On the other hand, if ζ % min{1, ? /} , then t(ζ) converges to t? (u? ) > α0 ,
which satisfies


2(1 − min{, ? }) (1 + t?2 )Φ(−t? ) − t? φ(t? ) + min{, ? }(1 + t?2 ) = δ.
Consequently, we get
h(ζ) → u? .
Therefore, by the continuity of h(ζ), for any u ∈ (0, u? ) we can find 0 < 0 <
min{1, ? /} such that h(0 ) = u. Put t? (u) = t(0 ). We have
1−u
= 1 − 0 < 1.
1 − 2Φ(−t? (u))
Last, to prove the uniqueness of t? (u) and its monotonically decreasing
dependence on u, it suffices to ensure that (a) t(ζ) is a decreasing function of
ζ, and (b) h(ζ) is an increasing function of ζ. As seen above, (a) is true, and
(b) is also true as can be seen from writing h as h(ζ) = 2(1 − ζ)Φ(−t(ζ)) + ζ,
which is an increasing function of ζ.

Proof of Lemma C.5. Write
q ? (u) =

2(1 − )
.
2(1 − ) + u/Φ(−t? (u))

40

W. SU, M. BOGDAN, AND E. CANDÈS

This suggests that the lemma amounts to saying that u/Φ(−t? (u)) is a
decreasing function of u. From (C.10), we see that this function is equal to



(1 − 2Φ(−t? (u))) 2(1 − ) (1 + (t? (u))2 )Φ(−t? (u)) − t? (u)φ(t? (u)) + (1 + (t? (u))2 ) − δ
1
−
Φ(−t? (u))
Φ(−t? (u)) [(1 + (t? (u))2 )(1 − 2Φ(−t? (u))) + 2t? (u)φ(t? (u))]
With the proviso that t? (u) is decreasing in u, it suffices to show that



(1 − 2Φ(−t)) 2(1 − ) (1 + t2 )Φ(−t) − tφ(t) + (1 + t2 ) − δ
1
−
Φ(−t)
Φ(−t) [(1 + t2 )(1 − 2Φ(−t)) + 2tφ(t)]


δ
1 − 2Φ(−t)
2 (1 − 2Φ(−t)) (1 + t2 )Φ(−t) − tφ(t)
= ·
− ·
+2
 Φ(−t) [(1 + t2 )(1 − 2Φ(−t)) + 2tφ(t)]  Φ(−t) [(1 + t2 )(1 − 2Φ(−t)) + 2tφ(t)]
|
|
{z
}
{z
}
f1 (t)

f2 (t)

is an increasing function of t > 0. Simple calculations show that f1 is increasing while f2 is decreasing over (0, ∞). This finishes the proof.
APPENDIX D: PROOF OF THEOREM 2.1
With the results given in Appendices B and C in place, we are ready
to characterize the optimal false/true positive rate trade-off. Up until now,
the results hold for bounded λ, and we thus need to extend the results to
arbitrarily large λ. It is intuitively easy to conceive that the support size of
βb will be small with a very large λ, resulting in low power. The following
lemma, whose proof constitutes the subject of Section D.1, formalizes this
point. In this section, σ ≥ 0 may take on the value zero. Also, we work with
λ0 = 0.01 and η = 0.001 to carry fewer mathematical symbols; any other
numerical values would clearly work.
Lemma D.1.

For any c > 0, there exists λ0 such that
sup
λ>λ0

#{j : βbj (λ) 6= 0}
≤c
p

holds with probability converging to one.
Assuming the conclusion of Lemma D.1, we prove claim (b) in Theorem
1 (noisy case), and then (a) (noiseless case). (c) is a simple consequence of
(a) and (b), and (d) follows from Appendix C.

FALSE DISCOVERIES ON LASSO PATH

41

Case σ > 0. Let c be sufficiently small such that q ? (c/) < 0.001. Pick a
large enough λ0 such that Lemma D.1 holds. Then with probability tending
to one, for all λ > λ0 , we have
TPP(λ) =

#{j : βbj (λ) 6= 0}
T (λ)
c
≤ (1 + oP (1))
≤ (1 + oP (1)) .
k∨1
p


On this event, we get
q ? (TPP(λ)) − 0.001 ≤ q ? (c/ + oP (1)) − 0.001 ≤ 0,
which implies that
(D.1)

o
\ n
?
FDP(λ) ≥ q (TPP(λ)) − 0.001
λ>λ0

holds with probability approaching one.
Now we turn to work on the range [0.01, λ0 ]. By Lemma A.2, we get that
V (λ)/p (resp. T (λ)/p) converges in probability to fd∞ (λ) (resp. td∞ (λ))
uniformly over [0.01, λ0 ]. As a consequence,
(D.2) FDP(λ) =

fd∞ (λ)
V (λ)
P
= fdp∞ (λ)
−−→ ∞
max {V (λ) + T (λ), 1}
fd (λ) + td∞ (λ)

uniformly over λ ∈ [0.01, λ0 ]. The same reasoning also justifies that
(D.3)

P

TPP(λ) −−→ tpp∞ (λ)

uniformly over λ ∈ [0.01, λ0 ]. From Lemma C.3 it follows that
fdp∞ (λ) > q ? (tpp∞ (λ)).
Hence, by the continuity of q ? (·), combining (D.2) with (D.3) gives that
FDP(λ) ≥ q ? (TPP(λ)) − 0.001
holds simultaneously for all λ ∈ [0.01, λ0 ] with probability tending to one.
This concludes the proof.
Case σ = 0. Fix λ and let σ > 0 be sufficiently small. We first prove that
Lemma A.1 still holds for σ = 0 if α and τ are taken to be the limiting
solution to (A.1) with σ → 0, denoted by α0 and τ 0 . Introduce βbσ to be the
Lasso solution with data y σ := Xβ + z = y + z, where z ∼ N (0, σ 2 In ) is
independent of X and β. Our proof strategy is based on the approximate
equivalence between βb and βbσ .

42

W. SU, M. BOGDAN, AND E. CANDÈS

It is well known that the Lasso residuals y−X βb are obtained by projecting
the response y onto the polytope {r : kX > rk∞ ≤ λ}. The non-expansive
property of projections onto convex sets gives
b ≤ ky σ − yk = kzk.
(y σ − X βbσ ) − (y − X β)
If P (·) is the projection onto the polytope, then I − P is also non-expansive
and, therefore,
(D.4)

X βbσ − X βb ≤ kzk.

√
Hence, from Lemma B.1 and kzk = (1 + oP (1))σ n it follows that, for
any c > 0 and rc depending on c,
(D.5)

b > 2rc σ} ≤ cp
#{1 ≤ j ≤ p : |Xj> (y σ − X βbσ − y + X β)|

holds with probability converging to one. Let g and g σ be subgradients
certifying the KKT conditions for βb and βbσ . From
b = λgj ,
Xj> (y − X β)
X > (y σ − X βbσ ) = λg σ ,
j

j

we get a simple relationship:
b > 2rc σ}.
{j : |gj | ≥ 1−a/2}\{j : |gjσ | ≥ 1−a/2−2rc σ/λ} ⊆ {j : |Xj> (y σ −X βbσ −y+X β)|
Choose σ sufficiently small such that 2rc σ/λ < a/2, that is, σ < aλ/(4rc ).
Then
(D.6)
b > 2rc σ}.
{j : |gj | ≥ 1−a/2}\{j : |gjσ | ≥ 1−a} ⊆ {j : |Xj> (y σ −X βbσ −y+X β)|
b and S σ = supp(βbσ ). In addition, let
As earlier, denote by S = supp(β)
Sv = {j : |gj | ≥ 1 − v} and similarly Svσ = {j : |gjσ | ≥ 1 − v}. Notice that
we have dropped the dependence on λ since λ is fixed. Continuing, since
S ⊆ S a2 , from (D.6) we obtain
(D.7)

b > 2rc σ}.
S \ Saσ ⊆ {j : |Xj> (y σ − X βbσ − y + X β)|

This suggests that we apply Proposition 3.6 of [3] that claims8 the existence of positive constants a1 ∈ (0, 1), a2 , and a3 such that with probability
tending to one,
(D.8)
8

∞.

σmin (XSaσ

1

∪S 0 )

≥ a3

Use a continuity argument to carry over the result of this proposition for finite t to

FALSE DISCOVERIES ON LASSO PATH

43

for all |S 0 | ≤ a2 p. These constants also have positive limits a01 , a02 , a03 , respectively, as σ → 0. We take a < a01 , c < a02 (we will specify a, c later) and suffib > 2rc σ}.
ciently small σ in (D.7), and S 0 = {j : |Xj> (y σ − X βbσ − y + X β)|
Hence, on this event, (D.5), (D.7), and (D.8) together give
kX βb − X βbσ k = XSaσ ∪S 0 (βbSaσ ∪S 0 − βbSσaσ ∪S 0 ) ≥ a3 kβb − βbσ k
for sufficiently small σ, which together with (D.4) yields
√
(1 + oP (1))σ n
σ
b
b
.
(D.9)
kβ − β k ≤
a3
b 0 is the number of nonzero entries in the vector β.
b From
Recall that the kβk
(D.9), using the same argument outlined in (B.8), (B.9), and (B.10), we have
(D.10)

b 0 ≥ kβbσ k0 − c0 p + oP (p)
kβk

for some constant c0 > 0 that decreases to 0 as σ/a3 → 0.
b 0 . Making use of (D.7) gives
We now develop a tight upper bound on kβk
b 0 ≤ kβbσ k0 + #{j : 1 − a ≤ |g σ | < 1} + cp.
kβk
j
As in (B.5), (3.21) of [3] implies that

P
# j : (1 − a) ≤ |gjσ | < 1 /p −−→ P ((1 − a)ατ ≤ |Π + τ W | < ατ ) .
Note that both α and τ depend on σ, and as σ → 0, α and τ converge to,
respectively, α0 > 0 and τ 0 > 0. Hence, we get
(D.11)

b 0 ≤ kβbσ k0 + c00 p + oP (p)
kβk

for some constant c00 > 0 that can be made arbitrarily small if σ → 0 by
first taking a and c sufficiently small.
With some obvious notation, a combination of (D.10) and (D.11) gives
(D.12)

|V − V σ | ≤ c000 p,

|T − T σ | ≤ c000 p,

for some constant c000 = c000
σ → 0 as σ → 0. As σ → 0, observe the convergence,
fd∞,σ = 2(1 − )Φ(−α) → 2(1 − )Φ(−α0 ) = fd∞,0 ,
and
td∞,σ =  P(|Π? + τ W | > ατ ) →  P(|Π? + τ 0 W | > α0 τ 0 ) = td∞,0 .

44

W. SU, M. BOGDAN, AND E. CANDÈS

By applying Lemma A.1 to V σ and T σ and making use of (D.12), the
conclusions
V P
T P
−−→ fd∞,0 and
−−→ td∞,0
p
p
follow.
Finally, the results for some fixed λ can be carried over to a bounded
interval [0.01, λ0 ] in exactly the same way as in the case where σ > 0. Indeed,
the key ingredients, namely, Lemmas A.2 and B.2 still hold. To extend the
results to λ > λ0 , we resort to Lemma D.1.
For a fixed a prior Π, our arguments immediately give an instance-specific
trade-off. Let q Π (·; δ, σ) be the function defined as
q Π (tpp∞,σ (λ); δ, σ) = fdp∞,σ (λ)
for all λ > 0. It is worth pointing out that the sparsity parameter  is implied
by Π and that q Π depends on Π and σ only through Π/σ (if σ = 0, q Π is
invariant by rescaling). By definition, we always have
q Π (u; δ, σ) > q ? (u)
for any u in the domain of q Π . As is implied by the proof, it is impossible
to have a series of instances Π such that q Π (u) converges to q ? (u) at two
different points. Now, we state the instance-specific version of Theorem 2.1.
Theorem D.2. Fix δ ∈ (0, ∞) and assume the working hypothesis. In
either the noiseless or noisy case and for any arbitrary small constants λ0 >
0 and η > 0, the event
o
\ n
FDP(λ) ≥ q Π (TPP(λ)) − η
λ≥λ0

holds with probability tending to one.
D.1. Proof of Lemma D.1. Consider the KKT conditions restricted
to S(λ):


>
b
XS(λ)
y − XS(λ) β(λ)
= λg(λ).
b
Here we abuse the notation a bit by identifying both β(λ)
and g(λ) as
|S(λ)|-dimensional vectors. As a consequence, we get
(D.13)

>
>
b
β(λ)
= (XS(λ)
XS(λ) )−1 (XS(λ)
y − λg(λ)).

FALSE DISCOVERIES ON LASSO PATH

45

> X
Notice that XS(λ)
S(λ) is invertible almost surely since the Lasso solution
has at most n nonzero components for generic problems (see e.g. [33]). By
b
definition, β(λ)
obeys
(D.14)
1
1
1
2
2
2
b
b
ky − XS(λ) β(λ)k
+ λkβ(λ)k
1 ≤ ky − XS(λ) · 0k + λk0k1 = kyk .
2
2
2

Substituting (D.13) into (D.14) and applying the triangle inequality give
2
1
1
>
>
>
2
b
kλXS(λ) (XS(λ)
XS(λ) )−1 g(λ)k − ky − XS(λ) (XS(λ)
XS(λ) )−1 XS(λ)
yk +λkβ(λ)k
1 ≤ kyk .
2
2
> X
−1 >
Since I|S(λ)| − XS(λ) (XS(λ)
S(λ) ) XS(λ) is simply a projection, we get
>
>
ky − XS(λ) (XS(λ)
XS(λ) )−1 XS(λ)
yk ≤ kyk.

Combining the last displays gives
>
λkXS(λ) (XS(λ)
XS(λ) )−1 g(λ)k ≤ 2kyk,

(D.15)

which is our key estimate.
√
Since σmax (X) = (1 + oP (1))(1 + 1/ δ),
(D.16)
>
λkXS(λ) (XS(λ)
XS(λ) )−1 g(λ)k

p
λ |S(λ)|
λkg(λ)k
√ = (1+oP (1))
√ .
≥ (1+oP (1))
1 + 1/ δ
1 + 1/ δ

As for the right-hand side of (D.15), the law of large numbers reveals that
p
p
2kyk = 2kXβ+zk = (2+oP (1)) n(kβk2 /n + σ 2 ) = (2+oP (1)) p E Π2 + nσ 2 .
Combining the last two displays, it follows from (D.15) and (D.16) that
√
2 + nσ 2 )(1 + 1/ δ)2
(p
E
Π
Cp
b
kβ(λ)k
= (1+oP (1)) 2
0 ≡ |S(λ)λ | ≤ (4+oP (1))
2
λ
λ
for some constant C. It is worth emphasizing that the term oP (1) is indepenp
dent of any λ > 0. Hence, we finish the proof by choosing any λ0 > C/c.
APPENDIX E: PROOF OF THEOREM 3.1
We propose two preparatory lemmas regarding the χ2 -distribution, which
will be used in the proof of the theorem.
Lemma E.1.

For any positive integer d and t ≥ 0, we have
√
2
P(χd ≥ d + t) ≤ e−t /2 .

46

W. SU, M. BOGDAN, AND E. CANDÈS

Lemma E.2.

For any positive integer d and t ≥ 0, we have
d

P(χ2d ≤ td) ≤ (et) 2 .
The first lemma can be derived by the Gaussian concentration inequality,
also known as the Borell’s inequality. The second lemma has a simple proof:
Z td
d
x
1
2
P(χd ≤ td) =
x 2 −1 e− 2 dx
d
0 2 2 Γ( d )
2
d
Z td
d
1
2(td) 2
−1
2
≤
x
dx
=
.
d
d
d
2 Γ( )
0 2 2 Γ( d )
d2
2
2
Next, Stirling’s formula gives
d

P(χ2d ≤ td) ≤

2(td) 2
d

d2 2 Γ( d2 )

d

≤

d
2(td) 2
2
d ≤ (et) .
d√
d
−
d
d2 2 πd( 2 ) 2 e 2

Now, we turn to present the proof of Theorem 3.1. Denote by S a subset
of {1, 2, . . . , p}, and let m0 = |S ∩ {j : βj = 0}| and m1 = |S ∩ {j : βj 6= 0}|.
Certainly, both m0 and m1 depend on S, but the dependency is often omitted
for the sake of simplicity. As earlier, denote by k = #{j : βj 6= 0}, which
obeys k = ( + oP (1))p. Write βbSLS for the least-squares estimate obtained
by regressing y onto XS . Observe that (3.1) is equivalent to solving
(E.1)

argmin ky − XS βbSLS k2 + λ|S|.

S⊂{1,...,p}

As is clear from (3.1), we only need to focus on S with cardinality no more
than min{n, p}. Denote by Sb the solution to (E.1), and define m
b 0 and m
b 1 as
before. To prove Theorem 3.1 it suffices to show the following: for arbitrary
small c > 0, we can find λ and M sufficiently large such that (3.1) gives
(E.2)

P(m
b 0 > 2ck or m
b 1 ≤ (1 − c)k) → 0.

Assume this is true. Then from (E.2) we see that m
b 0 ≤ 2ck and m
b 1 > (1−c)k
hold with probability tending to one. On this event, the TPP is
m
b1
> 1 − c,
k
and the FDP is
m
b0
2ck
2c
≤
=
.
m
b0 + m
b1
2ck + (1 − c)k
1+c

FALSE DISCOVERIES ON LASSO PATH

47

Hence, we can have arbitrarily small FDP and almost full power by setting
c arbitrarily small.
It remains to prove (E.2) with proper choices of λ and M . Since
{m
b 0 > 2ck or m
b 1 ≤ (1 − c)k} ⊂ {m
b0 + m
b 1 > (1 + c)k} ∪ {m
b 1 ≤ (1 − c)k},
we only need to prove
P(m
b 1 ≤ (1 − c)k) → 0

(E.3)
and

P(m
b0 + m
b 1 > (1 + c)k) → 0.

(E.4)

We first work on (E.3). Write
X
y=
M Xj +
j∈S,βj =M

X

M Xj + z.

j∈S,βj =M

P

M Xj is already in the span
of XS . This fact implies
that the residual vector y − XS βbSLS is the same as
P
the projection of j∈S,βj =M M Xj + z onto the orthogonal complement of
XS . Thanks to the independence among β, X and z, our discussion proceeds
by conditioning on the random support set of β. A crucial but simple observation is that the orthogonal complement P
of XS of dimension n − m0 − m1
has uniform orientation, independent of
j∈S,βj =M M Xj + z. From this
fact it follows that
(E.5)

d
L(S) := ky−XS βbLS k2 +λ|S| = σ 2 + M 2 (k − m1 )/n χ2
+λ(m0 +m1 ).
In this decomposition, the summand

S

j∈S,βj =M

n−m0 −m1

Call ES,u the event on which
√
L(S) ≤ σ 2 (n − k + 2u n − k + u2 ) + λk
holds; here, u > 0 is a constant to be specified later. In the special case
where S = T and T ≡ {j : βj 6= 0} is the true support, Lemma E.1 says
that this event has probability bounded as


√
P(ET ,u ) = P σ 2 χ2n−k + λk ≤ σ 2 (n − k + 2u n − k + u2 ) + λk


√
(E.6)
= P χ2n−k ≤ n − k + 2u n − k + u2
≥ 1 − e−

u2
2

.

48

W. SU, M. BOGDAN, AND E. CANDÈS

By definition, ES,u
b1
b is implied by ET ,u . Using this fact, we will show that m
is very close to k, thus validating (E.3). By making use of
{m
b 1 ≤ (1−c)k} ⊂ {m
b 0 +m
b 1 ≥ (k+n)/2}∪{m
b 1 ≤ (1−c)k, m
b 0 +m
b 1 < (k+n)/2},
we see that it suffices to establish that
(E.7)

P(m
b0 + m
b 1 ≥ (k + n)/2) → 0

and
(E.8)

P(m
b 1 ≤ (1 − c)k, m
b0 + m
b 1 < (k + n)/2) → 0

for some λ and sufficient large M . For (E.7), we have
(E.9)
b0 + m
b 1 ≥ (k + n)/2})
P(m
b0 + m
b 1 ≥ (k + n)/2) ≤ P(E T ,u ) + P(ET ,u ∩ {m
≤ P(E T ,u ) + P(ES,u
b0 + m
b 1 ≥ (k + n)/2})
b ∩ {m
X
P(ES,u )
≤ P(E T ,u ) +
m0 +m1 ≥(k+n)/2
2
− u2

≤e

X

+

P(ES,u ),

m0 +m1 ≥(k+n)/2

where the last step makes use of (E.6), and the summation is over all S such
that m0 (S) + m1 (S) ≥ (k + n)/2. Due to (E.5), the event ES,u has the same
probability as
(E.10)
√

σ 2 + M 2 (k − m1 )/n χ2n−m0 −m1 + λ(m0 + m1 ) ≤ σ 2 (n − k + 2u n − k + u2 ) + λk
√
σ 2 (n − k + 2u n − k + u2 ) + λk − λ(m0 + m1 )
2
⇐⇒ χn−m0 −m1 ≤
.
σ 2 + M 2 (k − m1 )/n
Since m0 + m1 ≥ (k + n)/2, we get
√
√
σ 2 (n−k+2u n − k+u2 )+λk−λ(m0 +m1 ) ≤ σ 2 (n−k+2u n − k+u2 )−λ(n−k)/2.
Requiring
(E.11)

λ > 2σ 2 ,

√
would yield σ 2 (n − k + 2u n − k + u2 ) − λ(n − k)/2 < 0 for sufficiently
large n (depending on u) as n − k → ∞. In this case, we have P(ES,u ) = 0
whenever m0 + m1 ≥ (k + n)/2. Thus, taking u → ∞ in (E.9) establishes
(E.7).

FALSE DISCOVERIES ON LASSO PATH

49

Now we turn to (E.8). Observe that
(E.12)
P (m
b 1 ≤ (1 − c)k and m
b0 + m
b 1 < (k + n)/2)
≤ P(E T ,u ) + P(ET ,u ∩ {m
b 1 ≤ (1 − c)k and m
b0 + m
b 1 < (k + n)/2})
≤ e−

u2
2

≤ e−

u2
2

+ P(ES,u
b 1 ≤ (1 − c)k and m
b0 + m
b 1 < (k + n)/2})
b ∩ {m
X
+
P(ES,u ).
m0 +m1 < k+n
,m1 ≤(1−c)k
2

For m0 + m1 < (k + n)/2 and m1 ≤ (1 − c)k, notice that n − m0 − m1 > (n −
k)/2 = (δ −+oP (1))p/2, and M 2 (k−m1 )/n ≥ cM 2 k/n ∼ (c/δ +oP (1))M 2 .
Let t0 > 0 be a constant obeying
δ−
(1 + log t0 ) + log 2 < −1,
5
then choose M sufficiently large such that
2σ 2 (δ − ) + 2λ
< t0 .
(σ 2 + cM 2 /δ)(δ − )

(E.13)
This gives

√
σ 2 (n − k + 2u n − k + u2 ) + λk − λ(m0 + m1 )
< t0
(σ 2 + M 2 (k − m1 )/n)(n − m0 − m1 )
for sufficiently large n. Continuing (E.12) and applying Lemma E.2, we get
(E.14)
P (m
b 1 ≤ (1 − c)k and m
b0 + m
b 1 < (k + n)/2)
X
u2
≤ e− 2 +
P(χ2n−m0 −m1 ≤ t0 (n − m0 − m1 ))
m0 +m1 < k+n
,m1 ≤(1−c)k
2

≤ e−

u2
2

X

+

(et0 )

n−m0 −m1
2

,m1 ≤(1−c)k
m0 +m1 < k+n
2

X

≤

(et0 )

m0 +m1 <(k+n)/2,m1 ≤(1−c)k

≤ e−

u2
2

≤ e−

u2
2

+ 2p (et0 )
+ e−p .

Taking u → ∞ proves (E.8).

(δ−)p
5

(δ−)p
5

50

W. SU, M. BOGDAN, AND E. CANDÈS

Having established (E.3), we proceed to prove (E.4). By definition,
b 2 + λkβk
b 0 = ky − X bβbLS k2 + λkβ LS k0
ky − X βk
S Sb
Sb
≤ ky − Xβk2 + λkβk0
= kzk2 + λk.
If
(E.15)

λ>

σ2δ
,
c

then

σ2n
kzk2
+ k = (1 + oP (1))
+ k ≤ (1 + c)k
λ
λ
holds with probability tending to one, whence (E.4).
To recapitulate, selecting λ obeying (E.11) and (E.15), and M sufficiently
large such that (E.13) holds, imply that (E.2) holds. The proof of the theorem is complete.
m
b0 + m
b1 ≤

Departments of Statistics
The Wharton School
University of Pennsylvania
Philadelphia, PA 19104
USA
E-mail: suw@wharton.upenn.edu

Institute of Mathematics
University of Wroclaw
50-137, Wroclaw
Poland
E-mail: malgorzata.bogdan@pwr.edu.pl

Departments of Statistics and Mathematics
Stanford University
Stanford, CA 94305
USA
E-mail: candes@stanford.edu

