Journal of Machine Learning Research 17 (2016) 1-17

Submitted 11/2015; Revised 10/2016; Published 10/2016

A Practical Scheme and Fast Algorithm to
Tune the Lasso With Optimality Guarantees
Michaël Chichignoud

michael.chichignoud@gmail.com

arXiv:1410.0247v2 [stat.ME] 8 Nov 2016

Seminar for Statistics
ETH Zürich

Johannes Lederer∗

ledererj@uw.edu

Department of Statistics
and Department of Biostatistics
University of Washington

Martin J. Wainwright

wainwrig@berkeley.edu

Department of Statistics
and Department of Electrical Engineering and Computer Sciences
University of California at Berkeley

Editor: Francis Bach

Abstract
We introduce a novel scheme for choosing the regularization parameter in high-dimensional
linear regression with Lasso. This scheme, inspired by Lepski’s method for bandwidth selection in non-parametric regression, is equipped with both optimal finite-sample guarantees
and a fast algorithm. In particular, for any design matrix such that the Lasso has low
sup-norm error under an “oracle choice” of the regularization parameter, we show that our
method matches the oracle performance up to a small constant factor, and show that it
can be implemented by performing simple tests along a single Lasso path. By applying the
Lasso to simulated and real data, we find that our novel scheme can be faster and more
accurate than standard schemes such as Cross-Validation.
Keywords: Lasso, regularization parameter, tuning parameter, high-dimensional regression, oracle inequalities

1. Introduction
Regularized estimators—among them the Lasso (Tibshirani, 1996), the Square-Root and
the Scaled Lasso (Antoniadis, 2010; Belloni et al., 2011; Städler et al., 2010; Sun and Zhang,
2012), as well as estimators based on nonconvex penalties such as MCP (Zhang, 2010) and
SCAD (Fan and Li, 2001)—all hinge on finding a “suitable” choice of tuning parameters.
There are many possible methods for solving this so-called calibration problem, but for
high-dimensional regression problems, there is a not a single method that is computationally
tractable and for which the non-asymptotic theory is well understood.
The focus of this paper is the calibration of the Lasso for sparse linear regression,
where the tuning parameter needs to be adjusted to both the noise distribution and the
∗. Corresponding author. Postal address:
Box 354322, Seattle, WA 98195

Department of Statistics at University of Washington,

©2016 Michaël Chichignoud, Johannes Lederer, Martin J. Wainwright.

Chichignoud, Lederer, and Wainwright

design matrix (van de Geer and Lederer, 2013; Hebiri and Lederer, 2013; Dalalyan et al.,
2014). Calibration schemes for this setting are typically based on Cross-Validation (CV)
or BIC-type criteria. However, CV-based procedures can be computationally intensive
and are currently lacking in non-asymptotic theory for high-dimensional problems. BICtype criteria, on the other hand, are computationally simpler but also lacking in nonasymptotic guarantees. Another approach is to replace the Lasso with Square-Root Lasso
or TREX (Lederer and Müller, 2015); however, Square-Root Lasso still contains a tuning
parameter that needs to be calibrated to certain aspects of the model, and the theory for
TREX is currently fragmentary. For these reasons and given the extensive use of the Lasso
in practice, understanding the calibration of Lasso is important.
In this paper, we introduce a new scheme for calibrating the Lasso in the supremum
norm (ℓ∞ )-loss, which we refer to as Adaptive Validation for ℓ∞ (AV∞ ). This method is
based on tests that are inspired by Lepski’s method for non-parametric regression (Lepski,
1990; Lepski et al., 1997), see also Chichignoud and Lederer (2014). In contrast to current
schemes for the Lasso, our method is equipped with both optimal theoretical guarantees
and a fast computational routine.
The remainder of this paper is organized as follows. In Section 2, we introduce the
AV∞ method. Our main theoretical results show that this method enjoys finite sample
guarantees for the calibration of Lasso with respect to sup-norm loss (Theorem 3) and
variable selection (Remark 4). In addition, we provide a simple and fast algorithm (Algorithm 1). In Section 3, we illustrate these features with applications to simulated data and
to biological data. We conclude with a discussion in Section 4.
Notation: The indicator of events is denoted by 1l{·} ∈ {0, 1}, the cardinality of sets by
| · |, the sup-norm or maximum norm of vectors in Rp vectors k · k∞ , the number of non-zero
entries by k·k0 , the ℓ1 - and ℓ2 -norms by k·k1 and k·k2 , respectively, and [p] : = {1, . . . , p}. For
c
given vector β ∈ Rp and subset A of [p], βA ∈ R|A| and βAc ∈ R|A | denote the components
in A and in its complement Ac , respectively.

2. Background and Methodology
In this section, we introduce some background and then move onto a description of the
AV∞ method.
2.1 Framework
We study the calibration of the Lasso tuning parameter in high-dimensional linear regression
models that can contain many predictors and allow for the possibility of correlated and
heavy-tailed noise. More specifically, we assume that the data (Y, X) with outcome Y ∈ Rn
and design matrix X ∈ Rn×p is distributed according to a linear regression model
Y = Xβ ∗ + ε,

(Model)

where β ∗ ∈ Rp is the regression vector and ε ∈ Rn is a random noise vector. Our framework
allows for p larger than n and requires that the noise variables ε satisfy only the second
moment condition
max E[ε2i ] < ∞.

i∈{1,...,n}

2

(1)

Lasso Tuning

A standard approach for estimating β ∗ in such a model is by computing the ℓ1 -regularized
least-squares estimate, known as the Lasso, and given by


kY − Xβk22
b
βλ ∈ arg min
+ λkβk1 .
(Lasso)
n
β∈Rp

Note that this equation actually defines a family of estimators indexed by the tuning parameter λ > 0, which determines the level of regularization.
Intuitively, the optimal choice of λ is dictated by a trade-off between bias and some
form of variance control. Bias is induced by the shrinkage effect of the ℓ1 -regularizer, which
acts even on non-zero coordinates of the regression vector. Thus, the bias grows as λ is
increased. On the other hand, ℓ1 -regularization is useful in canceling out fluctuations in the
score function, which for the linear regression model is given by X ⊤ ε/n. Thus, an optimal
choice of λ is the smallest one that is large enough to control these fluctuations.
A large body of theoretical work (e.g., van de Geer and Bühlmann (2009); Bickel et al.
(2009); Bühlmann and van de Geer (2011); Negahban et al. (2012)) has shown that an
appropriate formalization of this intuition is based on the event
Tλ : =

n kX ⊤ εk

∞

n

≤

λo
.
4

(2)

When this event holds, then as long as the design matrix X is “well-behaved”, it is possible
to obtain bounds on the sup-norm error of the Lasso estimate. There are various ways of
characterizing well-behaved design matrices; of most relevance for sup-norm error control
are mutual incoherence conditions (Bunea, 2008; Lounici, 2008) as well as ℓ∞ -restricted
eigenvalues (Ye and Zhang, 2010). See van de Geer and Bühlmann (2009) and Section 2.3
for further discussion of these design conditions.
In order to bring sharp focus to the calibration problem, rather than focusing on any
particular design condition, it is useful to instead work under the generic assumption that
the Lasso sup-norm error is controlled under the event Tλ defined in equation (2). More
formally, we state:
Assumption 1 (ℓ∞ (C)) There is a numerical constant C such that conditioned on Tλ , the
Lasso ℓ∞ -error is upper bounded as kβbλ − β ∗ k∞ ≤ Cλ.

As mentioned above, there are many conditions on the design matrix X under which Assumption ℓ∞ (C) is valid, and we consider a number of them in the sequel.
With this set-up in place, we can now focus specifically on how to choose the regularization parameter. Since we can handle only finitely many tuning parameters in practice,
we restrict ourselves to the selection of a tuning parameter among a finite but arbitrarily
large number of choices. It is easy to see that λmax : = 2kX ⊤ Y k∞ /n is the smallest tuning
parameter for which βbλ equals zero. Accordingly, for a given positive integer N ∈ N, let us
form the grid
0 < λ1 < · · · < λN = λmax ,

denoted by Λ : = {λ1 , . . . , λN } for short. Assumption ℓ∞ (C) guarantees that the sup-norm
error is proportional to λ whenever the event Tλ holds; consequently, for a given probability
3

Chichignoud, Lederer, and Wainwright

of error δ ∈ (0, 1), it is natural to choose the smallest λ for which event Tλ holds with
probability at least 1 − δ, assuming that it is finite. This criterion can be formalized as
follows:
Definition 1 (Oracle tuning parameter) For any constant δ ∈ (0, 1), the oracle tuning
parameter is given by
λ∗δ : = arg min {P (Tλ ) ≥ 1 − δ} .
λ∈Λ

(3)

Note that by construction, if we solve the Lasso using the oracle choice λ∗δ , and if the
design matrix X fulfills Assumption ℓ∞ (C), then the resulting estimate satisfies the bound
kβbλ∗δ − β ∗ k∞ ≤ Cλ∗δ with probability at least 1 − δ. Unfortunately, the oracle choice is
inaccessible to us, since we cannot compute the probability of the event Tλ based on the
observed data. However, as we now describe, we can mimic this performance, up to a factor
of three, using a simple data-dependent procedure.
2.2 Adaptive Calibration Scheme
Let us now describe a data-dependent scheme for choosing the regularization parameter,
referred to as Adaptive Calibration for ℓ∞ (AV∞ ):
Definition 2 (AV∞ ) Under Assumption ℓ∞ (C) and for a given constant C ≥ C, Adaptive
Calibration for ℓ∞ (AV∞ ) selects the tuning parameter
#
)
"
(
kβbλ′ − βbλ′′ k∞
(4)
−C ≤0 .
λ̂ : = min λ ∈ Λ ′max
λ′ + λ′′
λ ,λ′′ ∈Λ
λ′ ,λ′′ ≥λ

The definition is based on tests for sup-norm differences of Lasso estimates with different
tuning parameters. We stress that Definition 2 requires neither prior knowledge about the
regression vector nor about the noise.
The tests in Definition 2 can be formulated in terms of the binary random variables
(
)
N
Y
kβbλj − βbλk k∞
b
1l
tλj : =
for j ∈ [N ],
−C ≤0
λj + λk
k=j

from the AV∞ tuning parameter λ̂ can be computed as follows:
Data: βbλ1 , . . . , βbλN , C
Result: λ̂ ∈ Λ
Set initial index: j ← N
while b
tλj−1 6= 0 and j > 1 do
Update index: j ← j − 1
end
Set output: λ̂ ← λj

Algorithm 1: Algorithm for AV∞ in Definition 2.
4

Lasso Tuning

This algorithm can be readily implemented and only requires the computation of one Lasso
solution path. In strong contrast, k-fold Cross-Validation requires the computation of k
solution paths. Consequently, the Lasso with AV∞ can be computed about k times faster
than Lasso with k-fold Cross-Validation.
The following result guarantees that the Lasso with AV∞ method achieves the sup-norm
error up to a constant pre-factor:
Theorem 3 (Optimality of AV∞ ) Suppose that condition ℓ∞ (C) holds and the AV∞ method
is implemented with parameter C ≥ C. Then for any δ ∈ (0, 1), the AV∞ output pair (λ̂, βbλ̂ )
given by the rule (4) satisfies the bounds
λ̂ ≤ λ∗δ

with probability at least 1 − δ.

and

kβbλ̂ − β ∗ k∞ ≤ 3Cλ∗δ

(5)

Remark 4 (Relevance for estimation and variable selection) The ℓ∞ -bound from equation (5) directly implies that the AV∞ scheme is adaptively optimal for the estimation of
the regression vector β ∗ in ℓ∞ -loss. As another important feature, Theorem 3 entails strong
variable selection guarantees. First, the ℓ∞ -bound implies that AV∞ recovers all non-zero
entries of the regression vector β ∗ that are larger than 3Cλ∗δ in absolute value. Additionally,
by virtue of the bound λ̂ ≤ λ∗δ , thresholding βbλ̂ by 3C λ̂ leads to exact support recovery if
all non-zero entries of β ∗ are larger than 6Cλ∗δ in absolute value. In strong contrast, standard calibration schemes are not equipped with comparable variable selection guarantees, and
there is no theoretically sound guidance for how to threshold standard schemes.
We prove Theorem 3 in Appendix A; here let us make a few remarks about its consequences. First, if we knew the oracle value λ∗δ defined in equation (3), then under Assumption ℓ∞ (C), the Lasso estimate βb would satisfy the ℓ∞ -bound kβb − β ∗ k∞ ≤ Cλ∗δ .
Consequently, when the AV∞ method is implemented with parameter C, then its sup-norm
error is optimal up to a factor of three. For standard calibration schemes, among them
Cross-Validation, no comparable guarantees are available in the literature. In fact, we are
not aware of any finite sample guarantees for standard calibration schemes.
We point out that Theorem 3—in contrast to asymptotic results or results with unspecified constants—provides explicit guarantees for arbitrary sample sizes. Moreover, Theorem 3 does not presume prior knowledge about the regression vector or the noise distribution
and allows, in particular, for correlated, heavy-tailed noise. From the perspective of theoretical sharpness, the best choice for C is C = C. However, Theorem 3 shows that it also
suffices to know an upper bound for C. We provide more details on choices of C and C
below.
We finally observe that the specific choice of the grid enters Theorem 3 only via the
oracle. Indeed, for any choice of the grid, Theorem 3 ensures that λ̂ performs as well as the
oracle tuning parameter λ∗δ , which is the “best” tuning parameter on the grid.
2.3 Conditions on the Design Matrix for ℓ∞ -guarantees
Let us now describe some conditions on the design matrix X that are sufficient for Assumption ℓ∞ (C). We stress that these are conditions to ensure that the Lasso satisfies
5

Chichignoud, Lederer, and Wainwright

ℓ∞ -bounds; importantly, our method itself does not impose any additional restrictions.
We defer all proofs of the results stated here to Appendix B and, for simplicity, we assume
b : = X ⊤ X/n has been normalized such that
in the following that the sample covariance Σ
b
Σjj = 1 for all j ∈ [p].
The significance of the event Tλ lies in the following implication: when Tλ holds, then it
can be shown (e.g.,Bickel et al. (2009); Bühlmann and van de Geer (2011); Negahban et al.
b : = βbλ − β ∗ must belong to the cone
(2012)) that the Lasso error ∆

C(S) : = ∆ ∈ Rp | k∆S c k1 ≤ 2k∆S k1 ,
(6)

where S denotes the support of β ∗ , and S c its complement. Accordingly, all known condib for vectors lying
tions involve controlling the behavior of the sample covariance matrix Σ
within this cone.
The most directly stated sufficient condition is based on lower bounding the ℓ∞ -restricted
eigenvalue: there exists some γ > 0 such that
b ∞ ≥ γk∆k∞
kΣ∆k

for all ∆ ∈ C(S).

(7)

See van de Geer and Bühlmann (2009) for an overview of various conditions for the Lasso,
and their relations. Based on (7), we prove in Appendix B.1 the following result:
b satisfies the γ-RE condition (7)
Lemma 5 (ℓ∞ -restricted eigenvalue) Suppose that Σ
5
.
and that Tλ holds. Then Assumption ℓ∞ (C) is valid with C = 4γ

Although this result is cleanly stated, the RE condition cannot be verified in practice,
since it involves the unknown support set S. Accordingly, let us now state some sufficient
and verifiable conditions for obtaining bounds on the restricted eigenvalues, and hence for
verifying Assumption ℓ∞ (C).
b
For a given integer s̃ ∈ [2, p] and scalar ν > 0, let us say that the sample covariance Σ
is diagonally dominant with parameters (s̃, ν) if
X
b jk | < ν
max
|Σ
for all j ∈ [p].
(8)
|T |=s̃
T ⊂[p]\{j} k∈T

b jj = 1
In the context of this definition, the reader should recall that we have assumed that Σ
for all j ∈ [p]. Note that this condition can be verified in polynomial-time, since the
subset T achieving the maximum in row j can be obtained simply by sorting the entries
b jk |, k ∈ [p]\j}. The significance of this condition lies in the following result:
{|Σ
b is s̃-order
Lemma 6 (Diagonal dominance of order s̃) Suppose that s̃ ≥ 9|S| and Σ
diagonally dominant with parameter ν ∈ [0, 1). Then under the event Tλ , Assumption
5
.
ℓ∞ (C) is valid with C = 4(1−ν)

See Appendix B.2 for the proof.
It is worth noting that the diagonal dominance condition is weaker than the pairwise
incoherence conditions that have been used in past work on sup-norm error (Lounici, 2008).
b = maxj6=k |Σ
b jk |. If the
The pairwise incoherence of the sample covariance is given by ρ(Σ)
b ≤ ν/s̃, then it follows that Σ
b is diagonally
pairwise incoherence satisfies the bound ρ(Σ)
dominant with parameters (s̃, ν).
By combining Lemma 6 with Theorem 3, we obtain the following corollary:
6

Lasso Tuning

b is s̃-order diagonally dominant with parameter
Corollary 7 Suppose that s̃ ≥ 9|S| and Σ
5
returns an estimate
ν ∈ [0, 1). Then for any δ ∈ (0, 1), the AV∞ method with C = 4 (1−ν)
βb such that
λ̂

with probability at least 1 − δ.

kβbλ̂ − β ∗ k∞ ≤

15
λ∗
4 (1 − ν) δ

(9)

Another sufficient condition for the sup-norm optimality of AV∞ is a design compatibility
condition due to van de Geer (2007). For each index j ∈ [p], suppose that we define the
deterministic vector
(
)
r
2
log(p)
kXβk
2
η j ∈ arg minp
+
kβk1 .
β∈R
n
n
βj =−1

Note that this optimization problem defining the vector regression of the jth column of the
design matrix
on the set of all other columns, where we have imposed an ℓ1 -penalty with
q
weight

log(p)
n .

We can then derive the following sup-norm bound for the Lasso.

Lemma 8 (Lasso bound under compatibility) Assume that X fulfills the compatibility condition
(p
)
|S|kXβk2
√
min
≥t
(Compatibility)
nkβS k1
kβS c k1 ≤3kβS k1
for a constant t > 0. Additionally, assume that
1
|S|
sup 2 j ≤
log n
j∈[p] t kη k1

r

n
.
log p

Then under the event Tλ , Assumption ℓ∞ (C) is valid with
C :=



1
3
+
4 log(n)



max
j∈[p]

kη j k
p 1
.
kXη j k22 /n + log(p)/nkη j k−j /2

This bound is a consequence of results in (van de Geer, 2014); the proof is deferred to
Section B.3. We are now ready to state the optimality of AV∞ with respect to this bound.
Corollary 9 (Optimality of AV∞ ) Assume that the assumptions in Lemma 8 are met.
Then for any constant δ > 0, the following bound for Lasso AV∞ with C = C, and C as
above, holds with probability at least 1 − δ:
kβbλ̂ − β ∗ k∞ ≤ 3Cλ∗δ .

(10)

This result demonstrates the optimality of AV∞ for sup-norm loss under the compatibility
condition.
7

Chichignoud, Lederer, and Wainwright

Remark 10 (Constant C in practice) The optimal choice is C = C in view of our
theoretical results. The constant C (or an upper bound of it) can be readily computed,
because it depends only on X (cf. Lemma 8) or on X and an upper bound on s (cf.
Lemma 6). However, we propose the universal choice C = 0.75 for all practical purposes.
Note that accurate support recovery and ℓ∞ -estimation is possible only if the design is near
orthogonal. A direct computation yields the bound kβbλ − β ∗ k∞ ≤ Cλ with C = 0.75 for
orthogonal design. Letting α → ∞ in Theorem 1 due to Lounici (2008) yields the same
bound with C ≈ 0.75 for near orthogonal designs. This provides strong theoretical support
for the choice C = 0.75. The empirical evidence in Section 3 indicates that a further
calibration is indeed not necessary.

3. Simulations
In this section, we perform experiments on both simulated and real data to demonstrate
the practical performance of AV∞ .
3.1 Simulated Data
We simulate data from linear regression models as in equation (Model) with n = 200
observations and p ∈ {300, 900} parameters. More specifically, we sample each row of
the design matrix X ∈ Rn×p from a p-dimensional normal distribution with mean 0 and
covariance matrix (1 − κ) I +κ1l, where I is the identity matrix, 1l : = (1, . . . , 1)⊤ (1, . . . , 1) is
the matrix of ones, and κ ∈ {0, 0.2, 0.4} is the magnitude of the mutual correlations. For
the entries of the noise ε ∈ Rn , we take the one-dimensional normal distribution with mean
0 and variance 1. The entries of β ∗ are first set to 0 except for 6 uniformly at random
chosen entries that are each set to 1 or −1 with equal probability. The entire vector β ∗
is then rescaled such that the signal-to-noise ratio kXβ ∗ k22 /n is equal to 5. We finally
consider a grid of 100 tuning parameters Λ := {λmax /1.30 , λmax /1.31 , . . . , λmax /1.399 } with
λmax : = 2kX ⊤ Y k∞ /n. We run 100 experiments for each set of parameters and report
the corresponding means (thick, colored bars) and standard deviations (thin, black lines).
All computations are conducted with the software R (R Core Team, 2013) and the glmnet
package (Friedman et al., 2010). While we restrict the presentation to the parameter settings
described, we found similar results over a wide range of settings.
We compare the sup-norm and variable selection performance of the following three
procedures:
- Oracle: Lasso with the tuning parameter that minimizes the ℓ∞ loss (this tuning
parameter is unknown in practice);
- AV∞ : Lasso with AV∞ and C = 0.75;
- Cross-Validation: Lasso with 10-fold Cross-Validation.
Our choice C = 0.75 is motivated by a theorem due to Lounici (2008) in the regime α → ∞;
see Remark 10 for details.
8

Lasso Tuning

p = 300
κ=0

Oracle
AV∞
Cross-Validation

p = 300
κ = 0.2

Oracle
AV∞
Cross-Validation

p = 300
κ = 0.4

Oracle
AV∞
Cross-Validation

0

0.1

0.2

0.3

ℓ∞ error

Figure 1: Sup-norm error kβbλ − β ∗ k∞ of the Lasso with three different calibration schemes
for the tuning parameter λ. Depicted are the results for three simulation settings
that differ in the correlation level κ. The simulation settings and the calibration
schemes are specified in the body of the text.

9

Chichignoud, Lederer, and Wainwright

p = 900
κ=0

Oracle
AV∞
Cross-Validation

p = 900
κ = 0.2

Oracle
AV∞
Cross-Validation

p = 900
κ = 0.4

Oracle
AV∞
Cross-Validation

0

0.1

0.2

0.3

ℓ∞ error

Figure 2: Sup-norm error kβbλ − β ∗ k∞ of the Lasso with three different calibration schemes
for the tuning parameter λ. Depicted are the results for three simulation settings
that differ in the correlation level κ. The simulation settings and the calibration
schemes are specified in the body of the text.

10

Lasso Tuning

AV∞ false positives
Cross-Validation false positives

p = 300
κ=0

AV∞ false negatives
Cross-Validation false negatives

AV∞ false positives
Cross-Validation false positives

p = 300
κ = 0.2

AV∞ false negatives
Cross-Validation false negatives

AV∞ false positives
Cross-Validation false positives

p = 300
κ = 0.4

AV∞ false negatives
Cross-Validation false negatives

0

20

40

60 Variable selection
error

Figure 3: Number of false positives |{j : βj∗ = 0, (βbλ )j 6= 0}| and false negatives |{j :
βj∗ 6= 0, (βbλ )j = 0}| of the Lasso with AV∞ and Cross-Validation as calibration
schemes for the tuning parameter λ. For AV∞ , the safe threshold described after
Theorem 3 is applied. The simulations settings correspond to those in Figure 1.

11

Chichignoud, Lederer, and Wainwright

AV∞ false positives
Cross-Validation false positives

p = 900
κ=0

AV∞ false negatives
Cross-Validation false negatives

AV∞ false positives
Cross-Validation false positives

p = 900
κ = 0.2

AV∞ false negatives
Cross-Validation false negatives

AV∞ false positives
Cross-Validation false positives

p = 900
κ = 0.4

AV∞ false negatives
Cross-Validation false negatives

0

20

40

60 Variable selection
error

Figure 4: Number of false positives |{j : βj∗ = 0, (βbλ )j 6= 0}| and false negatives |{j :
βj∗ 6= 0, (βbλ )j = 0}| of the Lasso with AV∞ and Cross-Validation as calibration
schemes for the tuning parameter λ. For AV∞ , the safe threshold described after
Theorem 3 is applied. The simulations settings correspond to those in Figure 2.

12

Lasso Tuning

Sup-norm error: In Figures 1 and 2, we compare the ℓ∞ error of the four procedures.
We observe that AV∞ outperforms Cross-Validation for most settings under consideration.
We also mention that the same conclusions can be drawn if the normal distribution for the
noise is replaced by other, possibly heavy-tailed distributions (for conciseness, we do not
show the outputs).
Variable selection: In Figures 3 and 4, we compare the variable selection performance
of AV∞ and Cross-Validation. More specifically, we compare the number of false positives
|{j : βj∗ = 0, (βbλ )j 6= 0}| and the number of false negatives |{j : βj∗ 6= 0, (βbλ )j = 0}|.
In contrast to Cross-Validation, AV∞ allows for a safe threshold of size 3C λ̂ (recall the
discussion after Theorem 3). Therefore, we report the results of Lasso with AV∞ and
an additional threshold of size 3C λ̂ applied to each component (that is, we consider the
vector with entries (βbλ )j 1l{|(βbλ )j | ≥ 3C λ̂} ), and we report the results of Lasso with CrossValidation (without threshold). We observe that, as compared to Cross-Validation, AV∞
with subsequent thresholding can lead to a considerably smaller number of false positives,
while keeping the number of false negatives on a low level. Note that one could perform a
similar thresholding of the Cross-Validation solution, but unlike for AV∞ , there is no theory
to guide the choice of the threshold. This problem also applies to other standard calibration
schemes.
Computational complexity: Cross-Validation with 10 folds requires the computation 10
Lasso paths, while AV∞ requires the computation of only one Lasso path - or even less.
AV∞ is therefore about 10 times more efficient than 10-fold Cross-Validation.
Let us conclude with remarks on the scope of the simulations. First, many methods have been proposed for tuning the regularization parameter in the Lasso, including Cross-Validation, BIC and AIC-type criteria, Stability Selection (Meinshausen and
Bühlmann, 2010), LinSelect (Baraud et al., 2014; Giraud et al., 2012), permutation approaches (Sabourin et al., 2015), and many more. On top of that, there are many modifications and extensions of the Lasso itself, including BoLasso (Bach, 2008), Square-Root/Scaled
Lasso (Antoniadis, 2010; Belloni et al., 2011; Städler et al., 2010; Sun and Zhang, 2012),
SCAD (Fan and Li, 2001), MCP (Zhang, 2010), and others. Detailed comparisons among
the selection schemes and the methods can be found in the cited papers. We also refer to
Leeb and Pötscher (2008) for theoretical insights about limitations of the methods.
In our simulations, we instead focus on the Lasso and, since we are not aware of guarantees similar to ours for any selection scheme, we compare to the most popular and most
extensively studied selection scheme, Cross-Validation. This comparison shows that, beyond its theoretical properties and the easy and efficient implementation, AV∞ is also a
competitor in numerical experiments.
3.2 Riboflavin Production in B. subtilis
We now consider variable selection for a data set that describes the production of riboflavin
(vitamin B2 ) in B. subtilis (Bacillus subtilis), see (Bühlmann et al., 2014). The data set
comprises the expressions of p = 4088 genes and the corresponding riboflavin production
rates for n = 71 strains of B. subtilis. We apply AV∞ and then impose the threshold 3C λ̂.
The resulting genes and the corresponding parameter values are given in the first column of Table 1. We see that these results commensurate with the results from previous
13

Chichignoud, Lederer, and Wainwright

AV∞
YXLD at
YOAB at
YEBC at
ARGF at
XHLB at

-0.405
-0.420
-0.146
-0.313
0.278

Stability Selection

B-TREX

YXLD at
YOAB at
LYSC at

YXLD at
YOAB at
YXLE at

Table 1: Variable selection results for the riboflavin data set. The first column depicts the
genes and the corresponding parameter values yielded by AV∞ . The second and
third column depict the genes returned by approaches based on Stability Selection
and TREX.

approaches based on Stability Selection (Bühlmann et al., 2014) and TREX (Lederer and
Müller, 2015), which are given in the third and fourth column.

4. Conclusions
We have introduced a novel method for sup-norm calibration, known as AV∞ , that is
equipped with finite sample guarantees for estimation in ℓ∞ -loss and for variable selection.
Moreover, we have shown that AV∞ allows for simple and fast implementations. These properties make AV∞ a competitive algorithm, as standard methods such as Cross-Validation
are computationally more demanding and lack non-asymptotic guarantees.
In order to bring sharp focus to the issue, we have focused this paper exclusively on the
calibration of the Lasso. However, we suspect that the methods and techniques developed
here could be more generally applicable, for instance to problems with nonconvex penalties
(e.g., SCAD, MCP). In particular, the paper (Loh and Wainwright, 2014) provides guarantees for ℓ∞ -recovery using such nonconvex methods, which could be combined with our
results. Another interesting direction for future work is the use of our methods for more
general decomposable penalty functions (Negahban et al., 2012), including the nuclear norm
that is often used in matrix estimation.
We also stress that our goals are ℓ∞ -estimation and variable selection, which are feasible
only under strict conditions on the design matrix. Other objectives, including prediction
and ℓ2 -estimation, can typically be achieved under less stringent conditions. However, the
corresponding oracle inequalities contain quantities (such as the sparsity level) that are
typically unknown in practice. Adaptations of our method to objectives beyond the ones
considered here thus need further investigation. We refer to (Chételat et al., 2014) for ideas
in this direction. However, there might be no approach that is uniformly optimal for all
objectives, see also the papers (Yang, 2005; Zhao and Yu, 2006).
Finally, as pointed out by one of the reviewers, another field for further study is model
misspecification. It would be interesting to see how robust the Lasso with the AV∞ scheme
is with respect to, for example, non-linearities in the model.

14

Lasso Tuning

Acknowledgments
We thank Sara van de Geer and Sébastien Loustau for the inspiring discussions. We also
thank the reviewers for the careful reading of the manuscript and the insightful comments.
This work was partially supported by NSF Grant DMS-1107000, and Air Force Office of
Scientific Research AFOSR-FA9550-14-1-0016 to MJW.

Appendix A. Proof of Theorem 1
o
n ⊤
λ∗
Define the event Tδ∗ : = kX nεk∞ ≤ 4δ and note that P[Tδ∗ ] ≥ 1 − δ by our definition
of the oracle tuning parameter in (3). Thus, it suffices to show that the two bounds hold
conditioned on the event Tδ∗ .
Bound on λ̂: To show that λ̂ ≤ λ∗δ , we proceed by proof by contradiction. If λ̂ > λ∗δ ,
then the definition of the AV∞ method implies that there must exist two tuning parameters
λ′ , λ′′ ≥ λ∗δ such that
kβbλ′ − βbλ′′ k∞ > C (λ′ + λ′′ ).

(11)

However, since Tλ′ and Tλ′′ are both subsets of Tδ∗ , Assumption ℓ∞ (C) implies that we must
have the simultaneous inequalities kβbλ′ − β ∗ k∞ ≤ Cλ′ and kβbλ′′ − β ∗ k∞ ≤ Cλ′′ . Combined
with the triangle inequality, we find that
kβbλ′ − βbλ′′ k∞ ≤ kβbλ′ − β ∗ k∞ + kβ ∗ − βbλ′′ k∞ ≤ C (λ′ + λ′′ ).

Since C ≥ C, this upper bound contradicts our earlier conclusion (11) and, therefore, yields
the desired claim.
Bound on the sup-norm error:
inition implies that

On the event Tδ∗ , we have λ̂ ≤ λ∗δ , and so the AV∞ def-


kβbλ̂ − βbλ∗δ k∞ ≤ C λ̂ + λ∗δ ≤ 2Cλ∗δ .

Combined with the triangle inequality, we find that

kβbλ̂ − β ∗ k∞ ≤ kβbλ̂ − βbλ∗δ k∞ + kβbλ∗δ − β ∗ k∞ ≤ 2Cλ∗δ + kβbλ∗δ − β ∗ k∞ .

Finally, under Tδ∗ and C ≥ C, Assumption ℓ∞ (C) implies that kβbλ∗δ − β ∗ k∞ ≤ Cλ∗δ ≤ Cλ∗δ ,
and combining the pieces completes the proof.


Appendix B. Remaining Proofs for Section 2
In this appendix, we provide the proofs of Lemmas 5, 6, and 8.
15

Chichignoud, Lederer, and Wainwright

B.1 Proof of Lemma 5
By the first-order stationarity conditions for
βbλ must satisfy
 an optimum, the Lasso solution
1 ⊤
p
the stationary condition n X X βbλ − Y + λb
z = 0, where zb ∈ R belongs to the subb
differential of the ℓ1 -norm at βλ . Since Y = Xβ ∗ + ε, we find that

X ⊤ε
b βbλ − β ∗ = −λb
.
Σ
z+
n

Taking the ℓ∞ -norm of both sides and applying the triangle inequality yields

X ⊤ε
b βbλ − β ∗ k∞ ≤ λkb
kΣ
z k∞ +
n

∞

≤λ+

λ
5
= λ,
4
4

using the bound from event Tλ , and the fact that kb
z k∞ ≤ 1, by definition of the ℓ1 -subb = βbλ − β ∗ belongs
differential. As noted previously, under the event Tλ , the error vector ∆
to the cone C(S) in (6), so that the γ-RE condition can be applied so as to obtain the lower
b βbλ − β ∗ )k∞ ≥ γkβbλ − β ∗ k∞ . Combining the pieces concludes the proof.
bou kΣ(

B.2 Proof of Lemma 6
Since ∆ ∈ C(S), we have
k∆k21 ≤ 9k∆S k21 ≤ 9|S|k∆S k22 ≤ 9|S|k∆k22 ≤ 9|S|k∆k1 k∆k∞ ,
which implies k∆k1 ≤ 9|S|k∆k∞ . In view of Lemma 5, it thus suffices to prove the lower
bound
b ∞ ≥ (1 − ν)k∆k∞
kΣ∆k

for all ∆ ∈ A : = B1 (9|S|) ∩ B∞ (1),

(12)

where we set Bd (r) : = {β ∈ Rp : kβkd ≤ r} for d ∈ [0, ∞] and r ≥ 0. We claim that

B1 (9|S|) ∩ B∞ (1) ⊆ 2 cl conv B0 (9|S|) ∩ B∞ (1)},
{z
} |
|
{z
}
A

(13)

B

where cl conv denotes the closed convex hull. Taking this as given for the moment, let us
use it to prove the desired claim. We have
max
∆∈A

X
b − I)∆k∞
b − I)∆k∞
b − I)∆k∞
k(Σ
k(Σ
k(Σ
b jk | ≤ ν
= max
≤ max
≤ max max
|Σ
∆∈B
k∆k∞
k∆k∞
k∆k∞
∆∈A/2
j∈[p] |T |=9|S|
T ⊂[p]\j k∈T

(14)

using the diagonal dominance (8). Combined with the triangle inequality, the lower bound (12)
follows.
It remains to prove the inclusion (13). Since both A and B are closed and convex,
it suffices to prove that φA (θ) ≤ φB (θ) for all θ ∈ Rp , where φA (θ) : = supz∈A hz, θi and
φB (θ) : = supz∈B hz, θi are the support functions. For a given vector θ ∈ Rp , let T be the
16

Lasso Tuning

subset indexing its top 9|S| values in absolute value. By construction, we are guaranteed
to have the bound 9|S|kθT c k∞ ≤ kθT k1 , and consequently
sup (hzT , θT i + hzT C , θT C i) φA (θ) ≤ sup (kzT k∞ kθT k1 + kzT C k1 kθT C k∞ )
z∈A

z∈A

≤ kθT k1 + 9|S| kθT c k∞

≤ 2kθT k1 .

On the other hand, for this same subset T , we have φB (θ) ≥ supz∈B hzT , θT i = 2kθT k1 ,
which completes the proof.

B.3 Proof of Lemma 8
In order to prove Lemma 8, we use a somewhat simplified version of a recent result due
to van de GeerP(2014). So as to simplify notation, we first define the norms kakj : = |aj |
and kak−j : = i6=j |ai | for any vector a. We then have:
Lemma 11 (van de Geer (2014), Lemma 2.1) Given any tuning parameter λ > 0, it
holds that
kβbλ − β ∗ kj ≤ Dj

kX ⊤ εk∞
+
n

p

log(p)kβbλ − β ∗ k−j
λ
√
+
j
2 nkη k1
2

!

for all j = 1, . . . , p,

where for each j ∈ [p],
Dj : =

kη j k
p 1
.
kXη j k22 /n + log(p)/nkη j k−j /2

This result provides a specific bound for each coordinate of Lasso. Lemma 8 can then
readily be proven using this result together with Theorem 6.1 from Bühlmann and van de
Geer (2011).


Appendix C. Strong Correlations
In this paper, we assume that the correlations in design matrix are small, which is needed
for precise ℓ∞ -estimation and variable selection. In the interest of completeness, however,
we add here two simulations where the correlations are large. Overall, we use the same
settings as described in the main part of the paper, but we set κ = 0.9. The results are
summarized in Figure 5 (note that the x-scale in the upper part of the figure is different
from the scales of the corresponding plots in the main part of the paper). We find that
AV∞ misses about half of the pertinent variables but has almost no false positives. CrossValidation, on the other hand, has less false negatives but selects many irrelevant variables.
As expected, none of the methods, including the oracle, provide accurate ℓ∞ -estimation.
17

Chichignoud, Lederer, and Wainwright

p = 300
κ = 0.9

Oracle
AV∞
Cross-Validation

p = 900
κ = 0.9

Oracle
AV∞
Cross-Validation

0

1

ℓ∞ error

2

3

40

60 Variable selection
error

AV∞ false positives
Cross-Validation false positives

p = 300
κ = 0.9

AV∞ false negatives
Cross-Validation false negatives

AV∞ false positives
Cross-Validation false positives

p = 900
κ = 0.9

AV∞ false negatives
Cross-Validation false negatives

0

6

20

Figure 5: Sup-norm and variable selection errors of the Lasso with three/two different calibration schemes for the tuning parameter λ. Depicted are the results for two
simulation settings that differ in the number of parameters p. The simulation
settings and the calibration schemes are specified in the main part of the paper.

References
A. Antoniadis. Comments on: ℓ1 -penalization for mixture regression models. Test, 19(2):
257–258, 2010.
18

Lasso Tuning

F. Bach. Bolasso: model consistent lasso estimation through the bootstrap. In Proceedings
of the 25th International Conference on Machine Learning, pages 33–40, 2008.
Y. Baraud, C. Giraud, and S. Huet. Estimator selection in the gaussian setting. In Ann.
Inst. H. Poincaré Probab. Statist., volume 50, pages 1092–1119, 2014.
A. Belloni, V. Chernozhukov, and L. Wang. Square-root lasso: pivotal recovery of sparse
signals via conic programming. Biometrika, 98(4):791–806, 2011.
P. Bickel, Y. Ritov, and A. Tsybakov. Simultaneous analysis of the Lasso and Dantzig
selector. Ann. Statist., 37(4):1705–1732, 2009.
P. Bühlmann and S. van de Geer. Statistics for high-dimensional data: Methods, theory and
applications. Springer Series in Statistics. Springer, 2011.
P. Bühlmann, M. Kalisch, and L. Meier. High-dimensional statistics with a view toward
applications in biology. Annual Review of Statistics and Its Application, 1(1):255–278,
2014.
F. Bunea. Honest variable selection in linear and logistic regression models via ℓ1 and ℓ1 +ℓ2
penalization. Electron. J. Stat., 2:1153–1194, 2008.
D. Chételat, J. Lederer, and J. Salmon.
arXiv:1410.5014, 2014.

Optimal two-step prediction in regression.

M. Chichignoud and J. Lederer. A robust, adaptive M-estimator for pointwise estimation
in heteroscedastic regression. Bernoulli, 20(3):1560–1599, 2014.
A. Dalalyan, M. Hebiri, and J. Lederer. On the Prediction Performance of the Lasso.
Bernoulli, in press, 2014.
J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle
properties. J. Amer. Statist. Assoc., 96(456):1348–1360, 2001.
J. Friedman, T. Hastie, and R. Tibshirani. Regularization paths for generalized linear
models via coordinate descent. Journal of Statistical Software, 33(1):1–22, 2010.
C. Giraud, S. Huet, and N. Verzelen. High-dimensional regression with unknown variance.
Statistical Science, 27(4):500–518, 2012.
M. Hebiri and J. Lederer. How correlations influence Lasso prediction. IEEE Trans. Inform.
Theory, 59(3):1846–1854, 2013.
J. Lederer and C. Müller. Don’t fall for tuning parameters: Tuning-free variable selection
in high dimensions with the trex. In Proceedings of the Twenty-Ninth AAAI Conference
on Artificial Intelligence, 2015.
H. Leeb and B. Pötscher. Sparse estimators and the oracle property, or the return of Hodges’
estimator. J. Econometrics, 142(1):201–211, 2008.
19

Chichignoud, Lederer, and Wainwright

O. Lepski. A problem of adaptive estimation in Gaussian white noise. Teor. Veroyatnost. i
Primenen., 35(3):459–470, 1990. ISSN 0040-361X.
O. Lepski, E. Mammen, and V. Spokoiny. Optimal spatial adaptation to inhomogeneous
smoothness: an approach based on kernel estimates with variable bandwidth selectors.
Ann. Statist., 25(3):929–947, 1997.
P.-L. Loh and M. Wainwright. Support recovery without incoherence: A case for nonconvex
regularization. arXiv:1412.5632, 2014.
K. Lounici. Sup-norm convergence rate and sign concentration property of Lasso and
Dantzig estimators. Electron. J. Stat., 2:90–102, 2008.
N. Meinshausen and P. Bühlmann. Stability selection. J. R. Stat. Soc. Ser. B. Stat.
Methodol., 72(4):417–473, 2010.
S. Negahban, P. Ravikumar, M. J. Wainwright, and B. Yu. A unified framework for highdimensional analysis of M -estimators with decomposable regularizers. Statistical Science,
27(4):538–557, December 2012.
R Core Team. R: A Language and Environment for Statistical Computing. R Foundation
for Statistical Computing, Vienna, Austria, 2013. http://www.R-project.org/.
J. Sabourin, W. Valdar, and A. Nobel. A permutation approach for selecting the penalty
parameter in penalized model selection. Biometrics, 71(4):1185–1194, 2015.
N. Städler, P. Bühlmann, and S. van de Geer. ℓ1 -penalization for mixture regression models.
Test, 19(2):209–256, 2010.
T. Sun and C.-H. Zhang. Scaled sparse linear regression. Biometrika, 99(4):879–898, 2012.
R. Tibshirani. Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser.
B, 58(1):267–288, 1996.
S. van de Geer.
The deterministic Lasso.
2007 Proc. Amer. Math. Soc. [CDROM], see also www.stat.math.ethz.ch/˜geer/lasso.pdf, 2007.
S. van de Geer. Worst possible sub-directions in high-dimensional models. J. Multivariate
Anal., in press, 2014.
S. van de Geer and P. Bühlmann. On the conditions used to prove oracle results for the
Lasso. Electron. J. Stat., 3:1360–1392, 2009.
S. van de Geer and J. Lederer. The Lasso, correlated design, and improved oracle inequalities. IMS Collections, 9:303–316, 2013.
Y. Yang. Can the strengths of aic and bic be shared? A conflict between model indentification and regression estimation. Biometrika, 92(4):937–950, 2005.
F. Ye and C.-H. Zhang. Rate minimaxity of the lasso and dantzig selector for the lq loss in
lr balls. J. Mach. Learn. Res., 11:3519–3540, 2010.
20

Lasso Tuning

C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. Ann.
Statist., pages 894–942, 2010.
P. Zhao and B. Yu. On model selection consistency of Lasso. J. Mach. Learn. Res., 7:
2541–2563, 2006.

21

