  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.
