arXiv:1711.06305v2 [] 23 Nov 2017

Neighborhood selection with application to social
networks
Nana Wang ∗
Department of Statistics
University of California, Davis

Wolfgang Polonik †
Department of Statistics
University of California, Davis

Abstract
The topic of this paper is modeling and analyzing dependence in stochastic
social networks. Using a latent variable block model allows the analysis of dependence between blocks via the analysis of a latent graphical model. Our approach
to the analysis of the graphical model then is based on the idea underlying the
neighborhood selection scheme put forward by Meinshausen and Bühlmann (2006).
However, because of the latent nature of our model, estimates have to be used in
lieu of the unobserved variables. This leads to a novel analysis of graphical models
under uncertainty, in the spirit of Rosenbaum et al. (2010), or Belloni et al. (2017).
Lasso-based selectors, and a class of Dantzig-type selectors are studied.

1

Introduction

The study of random networks has been a topic of great interest in recent years, e.g.
see Kolaczyk (2009) and Newman (2010). A network is defined as a structure composed
of nodes and edges connecting nodes in various relationships Tang and Liu (2010). The
observed network can be represented by an N ˆ N adjacency matrix Y “ pYij qi,j“1,...,N ,
where N is the total number of nodes within the network. For a binary relation network,
as considered here, Yij “ 1 if there is an edge from node i to node j, and 0 otherwise. In
the following we identify an adjacency matrix Y with the network itself.
Most relational phenomena are dependent phenomena, and dependence is often of
substantive interest. Frank and Strauss (1986) and Wasserman and Pattison (1996)
introduced exponential random graph models which allow the modelling of a wide range
of dependences of substantive interest, including transitive closure. For such models,
Yij P t0, 1u and the distribution of Y is assumed to follow the exponential
family form
´ř
¯
Pθ pY “ yq “ exp pθ ¨ T pyq ´ φpθqq , y P Y, where φpθq “ ´ log
exppθ
¨
T
pyqq
yPY
and T pyq : Y Ñ Rq , are the sufficient statistics, e. g. the total number of edges. However,
as mentioned in Schweinberger and Handcock (2014), exponential random graph models
∗
†

nnawang@ucdavis.edu
wpolonik@ucdavis.edu

1

are lacking neighborhood structure, and that makes modelling dependencies challenging
for such networks. Neighborhoods (communities, blocks) are in general defined as a
group of individuals (nodes), such that individuals within a group interact with each
other more frequently than with those outside the group. Very recently, Schweinberger
and Handcock (2014) proposed the concept of local dependence in stochastic networks.
This concept allows for dependence within neighborhoods, while different neighborhoods
are independent.
In contrast to that, our work is considering dependence between blocks, while the
connections within blocks are assumed independent. We also assume the blocks to be
known. We then propose to analyze dependencies between blocks by means of graphical
models. To this end, we assume an undirected network so that
`
˘
Yij |pP , zq „ Bernoulli pzris,zrjs ,
(1.1)
s :“ t1, ¨ ¨ ¨ , Ku, i “ 1, . . . , N indicate block memberships in one of K
where zris P K
s govern the intensities of the connectivities within and between
blocks; pk,` , k, ` P K
blocks, 0 ă pk,l ă 1; and P “ ppk,l qk,lPKs is a K ˆ K symmetric matrix. We then put a
Gaussian logistic model on the pk,` . More precisely, for the diagonal elements ppk,k q1ďkďK ,
assume that
˙
ˆ
pk,k
“ xTk β ` k , 1 ď k ď K,
(1.2)
log
1 ´ pk,k
where xk is a pL ˆ 1q vector of given co-variables corresponding to block k, and β is the
pL ˆ 1q parameter vector. Furthermore,  “ p1 , ¨ ¨ ¨ , K qT with
 „ N p0, Σq,

(1.3)

where Σ “ pσkl q1ďk,lďK is an nonsingular covariance matrix. Each off-diagonal element
pk,l (k ‰ l) is assumed to be independent with all the other elements of P . The latter
assumption is made to simplify the exposition. A similar model can be found in Xu and
Hero (2014).
The dependence between the pk,k induces dependence between blocks. We can thus
analyze this induced dependence in our network model, by using methods from Gaussian
graphical models, via selecting the zeros in the precision matrix Σ´1 . Adding dependencies between the pk,` with k ‰ ` would increase the dimension of Σ, and induce ‘second
order dependencies’ to the network structure, namely, dependencies of block connections
between different pairs of blocks.
It is crucial to observe that this Gaussian graphical model is defined in terms of
the pk,k (or, more precisely, in terms of their log-adds ratios), and that these quantities
obviously are not observed. Thus, they need to be estimated from our network data,
and, to this end, we here assume the availability of iid observations of the network. This
estimation, in turn, induces additional randomness to our analysis of the graphical model.
We are therefore facing similar challenges as in the analysis of Gaussian graphical models
under uncertainty. However, our situation is more complex, as will become clear below.
The methods for neighborhood selection considered here, are based on the column2

wise methodology of Meinshausen and Bühlmann (2006). We apply this methodology
(under uncertainty) to some known selection methods from the literature, thereby, adjusting these methods for the additional uncertainty. The selection methods considered
here are (i) the graphical Lasso of Meinshausen and Bühlmann (2006), (ii) a class of
Dantzig-type selectors, that includes the Dantzig selector of Candes and Tao (2007),
and (iii) the matrix uncertainty selector of Rosenbaum et al. (2010). This will lead to
‘graphical’ versions of the respective procedures. The graphical Dantzig selector already
has been studied in Yuan (2010), but without the additional uncertainty we are facing
here. This leads to novel selection methodologies for which we derive statistical guarantees. We also present numerical studies to illustrate their finite sample performance.
The remainder of the manuscript is organized as follows. Section 2 is discussing more
details on our latent variable block model, thereby introducing some basic notation. Section 3 introduces our neighborhood selection methodologies, and presents results on their
large sample performance. We also discuss tuning parameter selection there. Numerical
studies are presented in section 4, and the proofs of our main results are in section 5.

2

Some important preliminary facts

Let η “ pη1 , ¨ ¨ ¨ , ηK qT with ηk “ logppkk {p1´pkk qq be the vector of log odds of the withinblock connection probabilities, and let XKˆL “ px1 , ¨ ¨ ¨ , xK qT be the design matrix.
Our latent variable block model (1.1) - (1.3) says that η „ N pXβ, Σq. The dependence
among the ηk , encoded in Σ, is propagated to the pkk . Let Σ´1 “ D “ pdkl q1ďk,lďK , then
the following fact holds.
Fact 2.1. Under (1.1) - (1.3), we have dkl “ 0, if and only if, pk,k is independent of pl,l
s ˆ Kztpk,
s
given the other variables p´pk,lq “ tpi,j : pi, jq P K
kq, pl, lqu, i ď ju, or just given
s
tpi,i : i P Kztk, luu.
In other words, if
E “ tpk, lq : dkl ‰ 0, k ‰ lu
denotes the edge set of the graph corresponding to η, then, under our latent variable
block model, pk, lq R E if and only if pk,k is conditionally independent with pl,l given the
other variables tpii : 1 ď i ď K, i R tk, luu. Identifying nonzero elements in D thus will
reveal the conditional dependence structure of the blocks in our underlying network.
We will use the relative number of edges ř
within each block, as estimates for the
unobserved values pkk , k “ 1, . . . , K. Let Sk “ zris“zrjs“k Yij , k “ 1, ¨ ¨ ¨ , K, denote the
total number of edges in the K blocks.
Fact 2.2. Under (1.1) - (1.3), we have
signpσkl q “ sign pCovpSk , Sl qq .
For proofs of the two facts see Oliveira (2012) (page 13, Theorem 1.35) and Liu et al.
(2009) (Section 3, Lemma 2), respectively.
3

3

Neighborhood selection

In the following, we mainly focus on identifying nonzero elements in D. We first assume
that (1.1) - (1.3) holds with a known β, and we write µ “ pµ1 , ¨ ¨ ¨ , µK qT “ Xβ. We
s Let Y ptq , t “ 1, . . . , n denote n iid observed
also assume that 0 ă pi,j ă 1 for all i, j P K.
networks with corresponding independent unobserved random vectors pptq , t “ 1, . . . , n
following our model. Let A1 , ¨ ¨ ¨ , AK denote the K blocks of the networks Y ptq and V “
t1,
ŤK¨ ¨ ¨ , N u be the node set. Assume Ak and Al are mutually exclusive for k ‰ l so that
k“1 Ak “ V. The number of possible edges within each block is mk “ |Ak |p|Ak | ´ 1q{2
for k “ 1, ¨ ¨ ¨ , K, and the number of possible edges between block k and block l is then
|Ak ||Al | for 1 ď k ‰ l ď K. We would like to point out again that the block membership
variable z is assumed to be known.

3.1

Controlling the estimation error
ptq

Given a network Y ptq , let Sk “

ptq

ř
zris“zrjs“k

Yij , k “ 1, . . . , K, t “ 1, . . . , n denote the
ptq

ptq

number of edges within block k in network t. Natural estimates of pkk and ηk are given
by
˜ ptq ¸
ptq
prk,k
S
ptq
ptq
prk,k “ k
and ηrk “ log
(3.1)
ptq
mk
1 ´ prk,k
respectively.
ptq
ptq
η1 , ¨ ¨ ¨ , ηrK qT , and let mmin “ min1ďkďK mk be the minimum number of
Let ηrptq “ pr
possible edges within a block, which of course measures the minimum blocksize.
Fact 3.1. Assume that K is fixed. Then, under (1.1) - (1.3), we have for each t “
1, ¨ ¨ ¨ , n,
ηrptq Ñ N pXβ, Σq in distribution as mmin Ñ 8.
This result tells us that, if we base our edge selection on ηrptq , then, for mmin large, we
are close to a Gaussian model, and thus we can hope that our analysis is similar to that
of a Gaussian graphical model. However, the approximation error has to be examined
ptq
ptq
carefully. In order to do that, we first truncate the prkk ’s, or, equivalently, the ηrk . For
T ą 0, let
$
’´T if ηrkptq ă ´T
&
ptq
ptq
ηpk “ ηrkptq if |r
ηk | ď T
’
%
ptq
T
if ηrk ą T .
This truncation corresponds to
$
T ´1
’
&p1 ` e q
ptq
ppk,k “ prptq
k
’
%
p1 ` e´T q´1

ptq

if prk,k ă p1 ` eT q´1
ptq
if p1 ` eT q´1 ď prk,k ď p1 ` e´T q´1
ptq
if prk,k ą p1 ` e´T q´1 .
4

In what follows, we work with these truncated versions. Note that the dependence on T
is not indicated explicitly in this notation.
The magnitude of mmin is important, as it reflects the accuracy of our estimates.
This estimation error will crucially enter the performance of the graphical model based
inverse covariance estimator. Under the latent variable block model, we have the following
concentration result:
Lemma 3.1. Let σ 2 “ maxkPKs σkk and µB “ maxkPKs |µk |. Then, under (1.1) - (1.3),
we have, for minpL, T q ą µB , and mmin ě 16M 2 logpnKqe2L , that
˜
P

d

¸
logpnKq
max
´
ă 8M e
1ďkďK
mmin
1ďtďn
c
ˆ
˙ ´
2
nKσ
pmintL, T u ´ µB q2
1 ¯2M 2 ´1
ě1´
exp ´
´
. (3.2)
π mintL, T u ´ µB
2σ 2
nK
ptq
|p
ηk

ptq
ηk |

L

Remark. Note that the larger µB , the larger we need to choose both T and L. A large
ptq
T will cause problems, because the ppk then might be too close to zero or one, causing
ptq
challenges by definition of ηpk . A large L makes our approximation less tight. Therefore
we will have to control the size of µB (even if µB is known); see assumption A1.6 and
B1.5.
To better understand the bound in (3.2), suppose that the number of blocks, K, grows
with n such that Kpnq “ Opnγ q for some γ ą 0. While K is allowed to grow with n, we
assume that σ 2 is bounded. If we further choose 0 ă mintL, T u ´ µB “ γ log n for some
γ ą 0, then, there exists c ą 0, such that
c
ˆ
˙
`
`
˘˘
pmintL, T u ´ µB q2
2
nKσ
2
exp ´
“
O
exp
´cplog
nq
as n Ñ 8.
π mintL, T u ´ µB
2σ 2
The last
a term on the right-hand side of (3.2) can be controlled similarly, by choosing
M “ p1 ` pc log nq{pγ ` 1qq {2. With these choices, we obtain an approximation error
ptq
ptq
of max1ďkďK,1ďtďn |p
ηk ´ ηk | “ Opn´p q by choosing the minimum blocksize large enough
` ´2p
˘
m´1
plog nq´2 e´2L .
min “ O n

3.2

Edge selection under uncertainty

In order to identify the nonzero elements in D, we consider the graphical model in terms
of the distribution of η. Recall that η P RK , where each component of η belongs to
s “ t1, ¨ ¨ ¨ , Ku are not only the block labels, but also the
one of the K blocks, thus K
node set in the underlying graph corresponding to the joint distribution of the η. Using
s : dab ‰ 0u is the neighborhood of node a P K
s
Gaussianity of η, the set nea “ tb P K
of the associated graph. We follow the idea of Meinshausen and Bühlmann (2006) to

5

s
convert the problem into a series of linear regression problems: for each a P K,
ÿ
ηa ´ µa “
θba pηb ´ µb q ` va
s
bPKztau
a T
with the residual va independent of tηb : 1 ď b ‰ a ď Ku. Let θ a “ pθ1a , ¨ ¨ ¨ , θK
q P RK
s : θa ‰ 0u.
with θaa “ 0, then the neighborhood can also be written as nea “ tb P K
b
Meinshausen and Bühlmann (2006) consider the case of n i.i.d. observations of
η. However, under the assumption of our model, we only have observations of ηp “
pp
η1 , ¨ ¨ ¨ , ηpK qT . Under our assumptions, we have available n independent realizations
x “ pηpp1q , ¨ ¨ ¨ , ηppnq qT be the n ˆ K-dimensional matrix with columns
ηpp1q , ¨ ¨ ¨ , ηppnq . Let H
p1q
pnq T
s Similarly denote by H “ pη p1q , . . . , η pnq qT the n ˆ Kηpa “ pp
ηa , . . . , ηpa q , a P K.
s are
dimensional matrix whose rows are n independent copies of η. Its column ηa , a P K
x
vectors of n independent observations of ηa . That is, we can also write H “ pηp1 , ¨ ¨ ¨ , ηpK q
s
and H “ pη1 , ¨ ¨ ¨ , ηK q. With this notation, for all a P K,
ÿ
ηa ´ µa 1n “
θba pηb ´ µb 1n q ` va .
(3.3)
s
bPK

x ´ H. The new matrix model can be written as
Let R “ H
x ´ 1n µT q “ pH ´ 1n µT q ` R
pH

(3.4)

pη ptq ´ µq „ N p0, Σq i.i.d. for t “ 1, ¨ ¨ ¨ , n.

(3.5)

x´a “ tηpb : b P Kztauu,
s let H´a “ tηb : b P Kztauu,
s
s
Moreover, for each a P K,
H
a
a
a
a
a T
T
θ´a “ pθ1 , ¨ ¨ ¨ , θa´1 , θa`1 , ¨ ¨ ¨ , θK q and µ´a “ pµ1 , ¨ ¨ ¨ , µa´1 , µa`1 , ¨ ¨ ¨ , µK q . We can
write the above model as
a
ηpa ´ µa 1n “ pH´a ´ 1n µT´a qθ´a
` ξa
T
T
x´a ´ 1n µ q “ pH´a ´ 1n µ q ` R´a ,
pH
´a

(3.6)

´a

x´a ´H´a . Note that (3.6) has a similar structure
where ξa “ va `pηpa ´ηa q and R´a “ H
as the model considered by Rosenbaum et al. (2010). The important difference is that
in our situation, we do not have independence of ξa and R´a .

3.3

Edge selection under uncertainty using the Lasso

Similar to Meinshausen and Bühlmann (2006), we define our Lasso estimates θpa,λ,lasso of
θ a (parameterized by λ) as
´
¯
x ´ 1n µT qθ}2 ` λ}θ}1 .
θpa,λ,lasso “ arg min n´1 }pηpa ´ µa 1n q ´ pH
(3.7)
2
θ:θa “0

6

The corresponding neighborhood estimate is
!
)
a,λ,lasso
λ,lasso
p
s
pa
“ b P K : θb
‰0 ;
ne
and the full edge set can be estimated by
!
)
λ,lasso
p λ,^,lasso “ pa, bq : a P ne
p λ,lasso
ne
p
E
and
b
P
a
b
or
!
)
λ,lasso
p λ,_,lasso “ pa, bq : a P ne
p λ,lasso
ne
p
E
or
b
P
.
a
b
In order to formulate statistical guarantees for the behavior of these estimates, we need
the following assumptions. On top of the assumptions from Meinshausen and Bühlmann
(2006), which are assumptions A1.1 - A1.5, we need further assumption on the underlying
network.
A1 Assumptions on the underlying Gaussian graph
1. High-dimensionality: There exists some γ ą 0 so that Kpnq “ Opnγ q for
n Ñ 8.
s and n P N, Varpηa q “ 1 and there exists υ 2 ą 0
2. Nonsigularity: For all a P K
so that
`
˘
Var ηa |ηKztau
ě υ2.
s
3. Sparsity
(a) There exists some 0 ď κ ă 1 so that maxaPKs |nea | “ Opnκ q for n Ñ 8.
s and
(b) There exists some ϑ ă 8 so that for all neighboring nodes a, b P K
all n P N,
}θ a,neb ztau }1 ď ϑ.
4. Magnitude of partial correlations: There exist a constant c ą 0 and some
1 ě ξ ą κ, so that for all pa, bq P E,
|πab | ě cn´p1´ξq{2 ,
where πab is the partial correlation between ηa and ηb .
s with
5. Neighborhood stability: There exists some % ă 1 so that for all a, b P K
b R nea ,
|Sa pbq| ă %

7

where
Sa pbq “

ÿ

sign pθka,nea q θkb,nea .

kPnea

6. Asymptotic upper bound on the mean: µB pnq “ oplog nq for n Ñ 8.
A2 Block size of networks: There exists constants c ą 0 and n0 , such that
mmin pnq ě c ¨ nν

for n ě n0 ,

where ν ą maxt4 ´ 4ξ, 2 ´ 2ξ ` 2κu.
The following theorem shows that, for proper choice of λ “ λn , our selection procedure
finds the correct neighborhoods with high probability, provided n is large enough.
Theorem 3.1. Let assumptions A1 and A2 hold, and assume β to be known. Let  be
such that
(
0 ă max κ, 4´ξ´ν
, 2`2κ´ν
ă  ă ξ.
3
2
If, for some dT , dλ ą 0, we have Tn „ dT log n and λn „ dλ n´p1´q{2 1 , respectively, then
there exists a constant c ą 0, such that
`
`
˘˘
p λ,lasso “ Eq “ 1 ´ O exp ´cplog nq2
P pE
as n Ñ 8.
Remark. Assumption A2 says that the rate of increase of the minimum block size, which
?
behaves like mmin , depends on the neighborhood size in our graphical model, and on the
magnitude of the partial correlations in the graphical model. Roughly speaking, large
neighborhoods (large κ), and small partial correlations (small ξ), both require a large
minimum block size (large ν), which appears reasonable. The choice of a proper penalty
parameter λn also depends on these two parameters.

3.4

Edge selection with a class of Dantzig-type selectors under
uncertainty

In this section, we propose a novel class of Dantzig-type selectors that are iterated over all
s For a linear model as in (3.3), i.e. for fixed a, Candes and Tao (2007) introduced
a P K.
the Dantzig selector as a solution to the convex problem
!
min }θ}1 : θ P RKpnq , θa “ 0 and
ˇ1`
)
˘T `
˘ˇˇ
ˇ
T
T
pηa ´ µa 1n q ´ pH ´ 1n µ qθ ˇ ď λ ,
ˇ H´a ´ 1n µ´a
n
8
1

For two sequence tan u, tbn u of real numbers, we write an „ bn for

8

an
bn

Ñ c for some 0 ă c ă 8.

where λ ě 0 is a tuning parameter, and for a matrix A “ paij q, | ¨ |8 “ maxij |aij |. Under
our model, we define the Dantzig selector as a solution of the minimization problem
!
min }θ}1 : θ P RKpnq , θa “ 0 and
ˇ1`
)
˘T `
˘ˇ
ˇ x
x ´ 1n µT qθ ˇˇ ď λ
pηpa ´ µa 1n q ´ pH
ˇ H´a ´ 1n µT´a
n
8

(3.8)

with λ ě 0. Moreover, when considering (3.6), the idea of matrix uncertainty selector
(MU-selector) comes into our mind. In our setting, we defined an MU-selector, a generalization of the Dantzig selector under matrix uncertainty, as a solution of the minimization
problem
!
min }θ}1 : θ P RKpnq , θa “ 0 and
ˇ1`
)
˘T `
˘ˇ
ˇ x
x ´ 1n µT qθ ˇˇ ď µ}θ}1 ` λ (3.9)
pηpa ´ µa 1n q ´ pH
ˇ H´a ´ 1n µT´a
n
8
with tuning parameters µ ě 0 and λ ě 0. Note that our MU-selector deals with matrix
x in the optimization equations like
uncertainty directly, rather than replacing H by H
the Lasso or the Dantzig selector. What we mean by this is that our MU-selector is
based on the structural equation (3.6), while both Lasso-based estimator and Dantzig
selector are based on the linear model (3.3) with the unknown η’s simply replaced by
their estimators.
Now we consider a class of Dantzig-type selectors, which can be considered as generals let the Dantzig-type
izations of the Dantzig selector and the MU-selector. For each a P K,
a,λ,ds
selector θr
be a solution of the optimization problem
!
min }θ}1 : θ P RKpnq : θa “ 0 and
ˇ1
)
`
˘ˇˇ
ˇ x
T T
T
x
p
p
H
´
1
µ
q
p
η
´
µ
1
q
´
p
H
´
1
µ
qθ
ď
λ
p}θ}
q
, (3.10)
ˇ
ˇ
´a
n ´a
a
a n
n
a,n
1
n
8
s is a set of functions such that
where for each n P N, tλa,n p¨q : a P Ku
s λa,n p¨q is an increasing function.
• For each n P N and a P K,
• For all n P N, minaPKs λa,n p¨q is lower bounded by some constant λn ě 0, i.e, for all
n P N, there exists some λn ą 0 so that
min

min

s θPRK :θa “0
aPK

• maxaPKs λa,n p}θ a }1 q “ opn´
all n ě n0 ,

1´ξ
2

λa,n p}θ}1 q ě λn .

q, i.e, there exist un “ op1q and n0 P N, so that, for

λa,n p}θ a }1 q ď un n´

9

1´ξ
2

s
, for all a P K.

a
The Dantzig-type selector θra,λ,ds always exists, because the LSE θpa defined as θp´a
“
x´a ´ 1n µT q` pη̂a ´ µa 1n q and θpa “ 0 belongs to the feasible set Θa , where
pH
´a
a

!
Θa “ θ P RKpnq : θa “ 0 and
ˇ1`
)
˘T `
˘ˇˇ
ˇ x
T
T
x
pηpa ´ µa 1n q ´ pH ´ 1n µ qθ ˇ ď λa,n p}θ}1 q
ˇ H´a ´ 1n µ´a
n
8
for any λa,n p}θ}1 q ě 0. It may not be unique, however. We will show that, similar to
Candes and Tao (2007) and Rosenbaum et al. (2010), under certain conditions, for large n,
the l8 -norm of the difference between the Dantzig-type selector θra,λ,ds and the population
s with large probability,
quantity θ a , can be bounded by tλa,n p}θra,λ,ds }1 q for all a P K
where t ą 1 is a constant. However, in general, sparseness cannot be guaranteed. This
already has been observed in Rosenbaum et al. (2010). Therefore, we consider penalizing
the Dantzig-type selector via subset selection, which can also significantly improve the
accuracy of the estimation of the sign. Let θpa,λ,ds P RKpnq be defined as
#
0,
b“a
¯
θpba,λ,ds “ ra,λ,ds ´ ra,λ,ds
(3.11)
s
θb
I |θb
| ą tλa,n p}θra,λ,ds }1 q ,
b P Kztau,
where Ip¨q is the indicator function, and t ą 1 is a constant. The corresponding neighs defined as ne
s : θpa,λ,ds ‰ 0u, and the
p λ,ds
borhood selector is, for all a P K,
“ tb P K
a
b
corresponding full edge selector is
!
)
λ,ds
p λ,^,ds “ pa, bq : a P ne
p λ,ds
p
E
and
b
P
ne
a
b
or
!
)
λ,ds
p λ,_,ds “ pa, bq : a P ne
p λ,ds
p
E
or
b
P
ne
.
a
b
Similar to the Section 3.3, in order to derive some consistency properties, we need
assumption about the underlying Gaussian graph (B1), and the minimum block size in
the underlying network (B2).
B1 Underlying Gaussian graph
1. Dimensionality: There exists γ ą 0 such that Kpnq “ Opnγ q as n Ñ 8.
2. Sparsity: There exists 0 ď κ ă 1{2, so that maxaPKs |nea | “ Opnκ q, as n Ñ 8.
3. Magnitude of partial correlations: There exist a constant c ą 0 and 1 ě ξ ą κ,
so that, for all pa, bq P E, |πab | ě cn´p1´ξq{2 .
4. |Σ ´ I|8 “ opn´κ q for n Ñ 8, where | ¨ |8 is the maximum of components
norm.
5. Asymptotic upper bound on the mean: µB pnq “ oplog nq for n Ñ 8.
´ν
B2 Block size of networks: m´1
min pnq “ Opn q with some ν ą 1 ´ ξ ` 2κ for n Ñ 8.

10

Here, the assumption on mmin (assumption B2) is weaker than that assumed for the
Lasso-based estimator (assumption A2). Similar remarks as given for A2 also apply to
B2 (see Remark right below Theorem 3.1).
Assumptions A1 and B1 are similar but not equivalent: A1.1 and B1.1, A1.4 and B1.3
respectively, are exactly the same; B1.2 and B1.4 implies Varpηa |ηKztau
q ě v 2 for some
s
v ą 0, which is almost A1.2 (see Claim 5.4). B1.2 is stronger than A1.3.(a), indicating
the underlying graph should be even sparser than the graph in Section 3.3; assumption
B1 does not have an analog to A1.3.(b) and A1.5.
Theorem 3.2. Let assumptions B1 and B2 hold, and assume β is known. Let  ą 0 be
1´
2 q,
such that ξ ą  ą 1 ` 2κ ´ ν. If Tn „ dT log n with some dT ą 0, and λ´1
n “ Opn
there exists c ą 0, so that
`
`
˘˘
p λ,ds “ Eq “ 1 ´ O exp ´cplog nq2
P pE
as n Ñ 8.
Remark. The choice of proper λa,n p¨q depends on the three parameters
ξ, κ and ν. Howb
ever, even the best scenario does not allow for the order λp „ logn p , which often can be
found in the literature. This stems from the fact that we have to deal with an additional
estimation error (coming in through the estimation of η).

3.5

Extension

In this section, we consider the case of an unknown coefficient vector β, or unknown
ptq
mean µ “ Xβ. Recall that η ptq „ N pµ, Σq, t “ 1, ¨ ¨ ¨ , n are
řn i.i.d.ptq Given tη : t “
1
1, ¨ ¨ ¨ , nu, a natural way to estimate µ is via the MLE ηs “ n t“1 η . Recall, however,
that we only have estimates ηpptq , t “ 1, ¨ ¨ ¨ ř
, n, available. Using the estimates ηpptq , we
s
p “ n1 nt“1 ηpptq . Moreover, we can estimate β via
estimate the underlying mean µ by η
s
p , where X ` is the Moore-Penrose pseudoinverse of X (when rankpXq “ L,
βp “ X ` η
p assumptions on
X ` “ pX T Xq´1 X T ). In order to derive consistency properties for β,
the design matrix are needed. Theorem 3.3 below states asymptotic properties of the
estimators.
Theorem 3.3. Let assumptions A1.1 (or B1.1) and A1.6 (or B1.5) hold. If m´1
min “
´ν
Opn q for some ν ą 0, then, for any b ă mint1, νu, and fixed δ ą 0, there exists some
c ą 0 so that
ˆ
˙
b´γ
`
`
˘˘
s
p ´ µ}2 ą δ “ O exp ´cplog nq2
P n 2 }η
as n Ñ 8.
If, moreover, the design matrix is of full rank and the singular value of X is asymptotically
upper bounded, that is, rankpXq “ L and σmax pXq “ Op1q, then there exists c ą 0, so
that
ˆ
˙
b´γ
`
`
˘˘
p
P n 2 }β ´ β}2 ą δ “ O exp ´cplog nq2
as n Ñ 8.

11

Next we consider the estimation of the edge set E based on D “ Σ´1 . We write
s
p qt“1,¨¨¨ ,n as the observations. We estimate the edge
η ´ µ „ N p0, Σq and consider pηpptq ´ η
pa 1n , and
set in the same way as described in Section 3.3,řbut replace ηpa ´ µa 1n by ηpa ´ ηs
ptq
s
s
x by H
x ´ 1n η
p is as above. The following
p T in (3.7), where ηs
pa “ n1 nt“1 ηpa and η
replace H
consistency result parallels Theorem 3.1 and Theorem 3.2, but stronger assumption are
needed to control the additional estimation error.
Corollary 3.1. Let assumptions A1 - A2 hold with ξ ą 3{4, and let  be such that
maxtκ ` 1{2, 3´ξ
, 4´ξ´ν
, 2`2κ´ν
u ă  ă ξ.
3
3
2
Suppose that Tn „ dT log n, for dT ą 0, and that the penalty parameter satisfies λn „
dλ n´p1´q{2 for some dλ ą 0. Then, there exists c ą 0, so that
`
`
˘˘
p λ,lasso “ Eq “ 1 ´ O exp ´cplog nq2
P pE
as n Ñ 8.
Corollary 3.2. Let assumptions B1 - B2 hold with ξ ą 2κ. Let  be such that ξ ą  ą
1´
2 q, there exists
maxt2κ, 2κ ` 1 ´ νu. If Tn „ dT log n for some dT ą 0, and λ´1
n “ Opn
c ą 0 so that
`
`
˘˘
p λ,ds “ Eq “ 1 ´ O exp ´cplog nq2
P pE
as n Ñ 8.
Example. Let κ “ 0 and ξ “ 1, that is, the number of blocks are finite and the partial
correlations in the graphical model are lower bounded. If, in addition, for some ν ą 0,
ν
m´1
min pnq “ Opn q as n Ñ 8, then Corollaries 3.1 and 3.2, respectively, apply in the
following scenarios:
• The Lasso: If assumption A1 - A2 hold: Choose the tuning parameter λn „
dn´p1´q{2 with any  satisfying 1 ą  ą maxt0, 1 ´ ν{2u in case µ is known, and 
satisfying 1 ą  ą maxt2{3, 1 ´ ν{2u for µ unknown.
• The Dantzig-type selector: If assumptions B1 - B2 hold, whether µ is known
1´
a
2 q with any positive  satisfying 1 ą
or unknown, choose maxaPKs λ´1
a,n pθ q “ Opn
 ą 1 ´ ν. In particular, for
1´

∗ the Dantzig selector: λa,n p}θ}1 q “ dn´ 2 for any d ą 0. Problem (3.10)
1´
becomes (3.8) with tuning parameter λ “ dn´ 2 .
1´

1´

∗ the MU-selector: λa,n p}θ}1 q “ dn´ 2 }θ}1 ` dn´ 2 for any d ą 0. Problem
1´
1´
(3.10) becomes (3.9) with tuning parameter µ “ dn´ 2 and λ “ dn´ 2 .

3.6

Selection of penalty parameters in finite samples

The results above only show that consistent edge selection is possible with the Lasso and
the Dantzig-type selector in a high-dimensional setting. However, we still have not given
a concrete way to choose the penalty parameter for a given data set. In this section, we
discuss the choice of tuning parameter for finite n for the following estimation methods:

12

• The Lasso
• The Dantzig-type selectors:
– the Dantzig selector: λp}θ}1 q “ λ
– the MU-selector: λp}θ}1 q “ λ}θ}1 ` λ
Meinshausen and Bühlmann (2006) proposed a data-driven penalty parameter of the
Lasso for Gaussian random vectors. However, we don’t have Gaussian observations;
moreover, according to our numerical studies, the choice suggested by Meinshausen and
Bühlmann tends to result in a very sparse graph, which goes along with a very small
type I error. Another natural idea is choosing the penalty parameter via cross-validation.
However, Meinshausen and Bühlmann (2006) already state that the choice λoracle gives an
inconsistent estimator, and λcv is an estimate of λoracle . So the cross-validation approach
is also not recommended. Instead we here consider the following two-stage procedure:
s let
for each a P K,
´
¯
#
a,λ
a,λ
a,λ
r
r
r
θb I |θb |{ maxkPKztau
|θb | ą τ
if θra,λ ‰ 0
s
θpba,λ,τ “
(3.12)
0
if θra,λ “ 0 ,
where θra,λ is obtained by solving either (3.7), (3.8) or (3.9) with µ “ λ. Such procedures
have also been used in Rosenbaum et al. (2010) and Zhou et al. (2011). However, the
use of maxkPKztau
|θpba,λ | in the truncation is novel. By using maxkPKztau
|θpba,λ |, we have
s
s
τ P r0, 1s, making the tuning parameter τ more standardized. Note that when θpba,λ is a
Dantzig-type selector, then, under the assumptions in Section 3, and for large n, (3.12)
is equivalent to (3.11).
For the choice of λ and τ , we follow a similar idea as in Zhou et al. (2011), but with
s we select λa via cross-validation to minimize the
some modification: for each a P K,
s are chosen, we
squared error prediction loss for a-th regression. After all λa , a P K,
select τ via BIC based on a Gaussian assumption:
BICpDq “ ´2ln pDq ` logpnq dimpDq,
where ln pDq is the n-sample Gaussian log-likelihood and dimpDq “ number of free
parameters. Note that we do not have a nice form of the likelihood, so we use the
Gaussian likelihood instead.

4

Simulation study

In this section, we mainly study the finite sample behavior of the three estimation methods mentioned in Section 3.6, that is,
• the Lasso;
• the Dantzig selector;
• the MU-selector with µ “ λ.
13

4.1

Finite-sample performance as a function of the penalty parameter

Here we consider the methods proposed in Section 3.3 and 3.4 with an AR(1) type
covariance structure ΣKˆK “ tρ|i´j| ui,jPKs with ρ “ 0.2, 0.5 and 0.8. In this setup,
dij “ 0 if and only if |i ´ j| ą 1. The minimum blocksize in our simulation is set to be
mmin “ 100. We consider the following choices of the sample size and number of blocks:
• n “ 20 with K “ 15;
• n “ 100 with K “ 15, 30, 50, 80, 100 and 150.
We only present the results for n “ 20, K “ 15 and n “ 100, K “ 150. The rest of the
results can be found in the supplementary material (attached to this version). Figures 1
- 2 show ROC-curves; average error rates (total error, type I error and type II error)
as functions of the tuning parameter λ are shown in figures 3 and 4. The shown curves
are color-coded: Lasso: red, Dantzig selector: blue and MU-selector: green. λopt is the
tuning parameter corresponding to the total (overall) minimum error rate.

Figure 1: ROC curves comparing the three proposed methods for K “ 15 and n “ 20

Figure 2: ROC curves comparing the three proposed methods for K “ 150 and n “ 100
We can see that the value of ρ is important. The performance of all the three methods
improves as ρ grows. This can be understood by the fact that it determines the size of
14

the partial correlations (cf. assumption A1.4). Moreover, when n ě K, and for λ “ 0,
all these methods result in estimates with all components being non-zero, which result in
type I error rate equal to 1 and type II error equals 0, that is, p1, 1q in the ROC curves.
However, when n ă K, and λ “ 0, the feasible set Θa is dimension at least pK ´ nq.
The Dantzig-type selectors minimize the L1 -norm of these θ’s, which produces some zero
terms of the solution; thus, the corresponding type I error rate will be less than 1 and the
type II error rate might be greater than 0, that is why the ROC curves of the Dantzig
selector and the MU-selector cannot reach p1, 1q for the case n “ 100 with K “ 150.
However, the solution of the Lasso is not unique, the coordinate decent algorithm could
return a solution with all its elements non-zero, resulting p1, 1q in the ROC curves.

1
2
3
Tuning parameter λ

4

0

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

0.15

total
type I
type II

0.00

0

0.15

0.15

0.05
0.10
Tuning parameter λ

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

0.15

0.15

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

Figure 3: Average error rates as functions of λ for K “ 15 and n “ 20.

15

4

MU selector: ρ = 0.8

total
type I
type II

0.00

1
2
3
Tuning parameter λ

Dantzig selector: ρ = 0.8

MU selector: ρ = 0.5

total
type I
type II

0.05
0.10
Tuning parameter λ

0.05
0.10
Tuning parameter λ

Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

MU selector: ρ = 0.2

0.00

4

Dantzig selector: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Dantzig selector: ρ = 0.2

1
2
3
Tuning parameter λ

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

0

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

total
type I
type II

Lasso: ρ = 0.8
Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.2

0.15

1
2
3
Tuning parameter λ

4

0

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

total
type I
type II

0.00

0.15

0.05
0.10
Tuning parameter λ

4

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

MU selector: ρ = 0.8

total
type I
type II

0.00

1
2
3
Tuning parameter λ

Dantzig selector: ρ = 0.8

MU selector: ρ = 0.5

total
type I
type II

0.05
0.10
Tuning parameter λ

0

0.10
0.20
Tuning parameter λ

Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

MU selector: ρ = 0.2

0.00

4

Dantzig selector: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Dantzig selector: ρ = 0.2

1
2
3
Tuning parameter λ

total
type I
type II

0.15

Average error rates
0.0
0.4
0.8
1.2

0

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

total
type I
type II

Lasso: ρ = 0.8
Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.2

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

0.15

Figure 4: Average error rates as functions of λ for K “ 150 and n “ 100.

4.2

Finite-sample performance with data-driven penalty selection

In this section, we study the three methods for finite-sample setup discussed in Section 3.6. In our simulation study, we consider three different covariance models with
K “ 30, 100, 200, mmin “ 45 and n “ 100, 500, 1000. Below we only present the case
K “ 100. See supplemental material (attached to this version) for the other cases.
• AR(1): ΣKˆK “ tρ|i´j| u1ďi,jďK with ρ “ 0.7.
9 ´ j| “ 1q ` 0.2 ¨ Ip|i ´ j| “ 2q ` 0.2 ¨ Ip|i ´ j| “
• AR(4): dij “ Ip|i ´ j| “ 0q ` 0.4Ip|i
3q ` 0.1 ¨ Ip|i ´ j| “ 4q.
16

• A random precision matrix model (see Rothman et al. (2008)): DK “ B ` δI
with each off-diagonal entry in B is generated independently and equals 0.5 with
probability α or 0 with probability 1 ´ α. B has zeros on the diagonal, and δ is
chosen so that the condition number of D is K.
As mentioned in Section 3.6, we choose λ via cross-validation, and τ based on BICpτ q.
As for the choice of τ , we often encountered the problem of a very flat BIC-function
close to the level of the minimum (some BICpτ q plots are shown in figure 5). To combat
this problem, we use the following strategy in our simulations: if more than half of the
τ P r0, 1s result in the same BIC, then we choice the third quartile of these τ ’s, otherwise,
we choose the one resulting the minimum BIC.

Figure 5: Tuning parameter τ vs BICpτ q plots for the four models with K “ 30: the
red points corresponds to the optimal τ .
Simulation results for AR(1) and AR(4) models are shown in tables 1 and 2, respectively. For the random precision matrix model we consider α “ 0.1 and α “ 0.5 (as in
Zhou et al. (2011)). The simulation results are shown in tables 3 - 4, respectively. The
tables show averages and SEs of classification errors in % over 100 replicates for the three
proposed methods with both “ _ ” (left) and “ ^ ” (right).

17

Table 1: AR(1) model with K “ 100
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
0.90(0.45); 1.16(0.44)
0.84(0.42); 1.26(0.44)
0.93(0.49); 1.22(0.43)

Type I (%)
0.91(0.47); 1.18(0.45)
0.85(0.43); 1.28(0.45)
0.94(0.50); 1.24(0.44)

Type II (%)
0.39(0.68); 0.06(0.28)
0.38(0.68); 0.12(0.36)
0.23(0.53); 0.15(0.44)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
0.566(0.220); 0.716(0.231)
0.601(0.208); 0.700(0.255)
0.574(0.203); 0.676(0.238)

Type I (%)
Type II (%)
0.577(0.224); 0.730(0.236)
0(0)
0.613(0.212); 0.714(0.260)
0(0)
0.586(0.207); 0.690(0.243)
0(0)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (‰)
0.473(0.529); 0.720(0.510)
0.501(0.533); 0.749(0.523)
0.522(0.532); 0.741(0.501)

Type I (%)
Type II (%)
0.483(0.539); 0.735(0.521)
0(0)
0.511(0.544); 0.764(0.534)
0(0)
0.532(0.543); 0.756(0.511)
0(0)

Table 2: AR(4) model with K “ 100
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
8.18(0.45); 8.26(0.37)
8.21(0.39); 8.21(0.33)
8.33(0.44); 8.28(0.37)

Type I (%)
2.37(0.59); 2.27(0.44)
2.38(0.51); 2.21(0.43)
2.57(0.52); 2.33(0.44)

Type II (%)
76.0(2.13); 78.3(1.93)
76.3(1.96); 78.3(2.23)
75.5(1.71); 77.7(1.82)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
4.69(0.28); 4.76(0.27)
4.77(0.28); 4.81(0.27)
4.74(0.24); 4.79(0.25)

Type I (%)
1.22(0.36); 1.30(0.37)
1.21(0.45); 1.30(0.38)
1.18(0.37); 1.30(0.38)

Type II (%)
45.2(3.91); 45.2(3.36)
46.4(3.87); 45.9(3.61)
46.3(3.77); 45.6(3.76)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
2.82(0.31); 2.77(0.29)
2.86(0.25); 2.80(0.29)
2.87(0.28); 2.79(0.28)

Type I (%)
1.37(0.37); 1.34(0.35)
1.35(0.30); 1.34(0.35)
1.37(0.35); 1.31(0.32)

18

Type II (%)
19.8(1.97); 19.5(2.01)
20.5(1.96); 19.8(2.07)
20.4(2.02); 20.1(2.02)

Table 3: The random precision matrix model with α “ 0.1 and K “ 100
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
10.3(0.68); 9.84(0.65)
10.3(0.70); 9.97(0.68)
10.1(0.65); 9.96(0.69)

Type I (%)
4.40(0.59); 3.91(0.61)
4.23(0.74); 4.08(0.56)
4.09(0.58); 4.05(0.57)

Type II (%)
63.9(4.19); 64.3(5.11)
66.0(4.32); 64.0(4.40)
65.6(4.44); 64.0(4.24)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
3.47(0.51); 3.65(0.50)
4.02(0.51); 4.12(0.55)
4.04(0.45); 4.25(0.61)

Type I (%)
2.71(0.50); 2.92(0.52)
3.11(0.50); 3.43(0.58)
3.12(0.50); 3.53(0.64)

Type II (%)
10.4(2.80); 10.2(2.90)
12.2(3.06); 10.2(2.72)
12.2(3.27); 10.5(2.39)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
1.34(0.38); 1.47(0.32)
1.77(0.38); 1.74(0.38)
1.91(0.36); 2.29(0.58)

Type I (%)
1.35(0.43); 1.50(0.36)
1.79(0.43); 1.77(0.42)
1.92(0.40); 2.32(0.65)

Type II (%)
1.27(0.67); 1.32(0.71)
1.74(0.87); 1.42(0.70)
1.78(0.81); 1.79(0.80)

Table 4: The random precision matrix model with α “ 0.5 and K “ 100
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
49.0(0.88); 49.2(0.87)
49.2(0.88); 49.2(0.87)
49.2(0.85); 49.2(0.89)

Type I (%)
7.04(1.16); 6.08(1.04)
6.48(0.92); 6.22(0.90)
6.39(0.88); 6.20(0.86)

Type II (%)
90.9(1.40); 92.1(1.30)
91.9(1.10); 92.1(1.09)
91.9(1.11); 92.1(1.13)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
42.5(1.30); 42.6(1.34)
44.9(1.32); 44.2(1.25)
45.7(1.23); 44.7(1.29)

Type I (%)
12.6(1.44); 12.8(1.66)
13.7(1.73); 14.4(1.72)
13.6(1.53); 14.1(1.52)

Type II (%)
72.2(2.64); 72.3(2.67)
76.1(2.81); 73.8(2.51)
77.6(2.13); 75.2(2.21)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
33.0(1.43); 32.9(1.43)
36.4(1.29); 35.4(1.29)
41.2(1.12); 39.7(1.26)

Type I (%)
13.5(1.58); 13.8(1.58)
16.2(1.47); 15.8(1.82)
17.5(2.05); 17.8(1.69)

19

Type II (%)
52.6(3.17); 52.0(3.00)
56.6(2.93); 55.0(3.24)
64.8(2.28); 61.7(2.25)

5

Appendix: proofs

Recall the notation introduced in Section 3.2,
x“H `R
H
η ptq “ Xβ ` ptq for t “ 1, ¨ ¨ ¨ , n
ptq „ N p0, Σq i.i.d. for t “ 1, ¨ ¨ ¨ , n.
In the proofs we denote by “c” a positive constant that can be different in each formula.

5.1

Proof of Lemma 3.1

We first consider the case β “ 0 and show the following result:
?
Lemma 5.1. Let σ “ maxkPKs σkk . Under the latent block model with β “ 0, for L ą 0,
if mmin ě 16M 2 logpnKqe2L ,
d
¸
˜
c
´ 1 ¯2M 2 ´1
logpnKq
2 nKσ
ptq
ptq
L
ě1´
ηk ´ ηk | ă 8M e
´
.
P max |p
1ďkďK
mmin
π LepL{σq2 {2
nK
1ďtďn
Proof. From Hoeffding’s inequality we have, for any M ą 0, that
ˇ
´?
´ˇ 1
ÿ
ˇ ptq ¯
M ˇˇ ptq ¯
ˇ
ptq
ptq
ptq ˇ
ptq
ˇ
P
mk |r
pk,k ´ pk,k | ą M pk,k “ P ˇ
pY ´ pk,k qˇ ą ?
ˇp
mk zris“k,zrjs“k ij
mk k,k
´
˘2 ¯
`
ď 2 exp ´2mk ?M
mk
`
˘
“ 2 exp ´2M 2 .
Thus, using the fact that, given p “ ppk,k , . . . , pK,K qT , all the Yij are independent, we
obtain
c
ˇ
´
(¯
mk
ˇ
ptq
ptq
|r
pk,k ´ pk,k | ą M ˇ pptq : 1 ď t ď n
P max
1ďkďK
logpnKq
1ďtďn
ˇ
¯
´?
a
ˇ ptq
ptq
ptq
ď nK max P
mk |r
pk,k ´ pk,k | ą M logpnKq ˇ pk,k
1ďkďK
1ďtďn

`
˘
ď nK exp ´2M 2 logpnKq
2

2

“ nKpnKq´2M “ pnKq1´2M ,
By integrating over tpptq : 1 ď t ď nu, we obtain
˜
¸
c
mk
2
ptq
ptq
pk,k ´ pk,k | ą M ď pnKq1´2M .
P max
|r
1ďkďK
logpnKq
1ďtďn

20

(5.1)

ptq

Note that if |ηk | ă T , we have
ptq

ptq

ptq

ptq

|p
ηk ´ ηk | ď |r
ηk ´ ηk |,
and we can write
ptq

ptq

ptq

ptq

prk,k

ptq

ηrk ´ ηk “ log

ptq
1´r
pk,k

ptq

´ log

pk,k
ptq

1´pk,k

ptq

“

ptq

ptq
1
p
ptq
ptq pr
ξk p1´ξk q k,k

ptq

ptq

ptq

´ pk,k q,

ptq

pk,k ´ pk,k |, inequality (5.1) also
where ξk lies between prk,k and pk,k . Since |ξk ´ pk,k | ď |r
ptq

ptq

applies to |ξk ´ pk,k |, so that
˜
P

c
max

1ďkďK
1ďtďn

mk
ptq
ptq
|ξk ´ pk,k | ą M
logpnKq

¸
2

ď pnKq1´2M .

It follows that
´
¯
ptq
ptq
P ξk ă  or ξk ą 1 ´ , for all 1 ď k ď K, 1 ď t ď n
ˆ
˙
?
?
M logpnKq
M logpnKq
ptq
ptq
?
?
ď P pk,k ă  `
or pk,k ě 1 ´  ´
, for all 1 ď k ď K, 1 ď t ď n
mk
mk
˜
¸
c
mk
ptq
ptq
|ξk ´ pk,k | ą M . (5.2)
` P max
1ďkďK
logpnKq
1ďtďn
ptq

As for ηk , since ηk ´ µk „ N p0, σkk q and
ptq

ptq

max |ηk | ď max |ηk ´ µk | ` max |µk |,

1ďkďK
1ďtďn

1ďkďK
1ďtďn

1ďkďK

we have, for C ą 1, that
¸
˜
¸
˜
a
a
?
ptq
ptq
P max |ηk | ą 2 log C ` µB ď P max |pηk ´ µk q{ σkk | ą 2 log C {σ
1ďkďK
1ďtďn

1ďkďK
1ďtďn

a
r 2 log C{σq,
ď 2nK Φp
r “ 1 ´ Φ (Φ is the c.d.f. of N p0, 1q). Note that
where Φ
˜
P

¸
a
ptq
max |ηk | ą 2 log B

1ďkďK
1ďtďn

˜
“P

ptq

max pk,k ą

1ďkďK
1ďtďn

1
1 ` e´

?
2 log B

Now we are using the following:

21

¸

˜
`P

1

ptq

min pk,k ă

1ďkďK
1ďtďn

1`e

?
2 log B

¸
.

2

Fact: For ?each c0 ą 0 we can find x0 “ e1{c0 ą 1 such that for x ě x0 ą 1
we have e´ log x ě x´c0 .
2 {2

Using this fact we get that for any L ą 0 we have that 1`B1´2{L ě 1`e´?12 log B for B ě eL
We obtain that (B ą 1)
¸
˜
¸
˜
1
1
ptq
ptq
?
ě P max pk,k ą
P max pk,k ą
´
2
log
B
1ďkďK
1ďkďK
1 ` B ´2{L
1`e
1ďtďn
1ďtďn
˜
¸
2
1
ptq
ě P max pk,k ą 1 ´ B ´ L .
1ďkďK
2
1ďtďn

.

x

e
1
Further, using that 1`e
x ě 2 for x ą 0, we obtain (by using the above fact again) that
2
for any L ą 0 and B ě eL {2 ,
˜
¸
˜
¸
?
2 log B
?
1
e
ptq
ptq
?
?
P min pk,k ă
“ P min pk,k ă e´ 2 log B
2 log B
1ďkďK
1ďkďK
1
`
e
1 ` e 2 log B
1ďtďn
1ďtďn
˜
¸
2
1
ptq
ě P min pk,k ă B ´ L .
1ďkďK
2
1ďtďn
2

This means that in (5.2) we can choose  “ pLq “ 14 B ´ L . It follows that with this choice
of  (for arbitrarily large L) and assuming that
?
M logpnKq
?
ď ,
(5.3)
max
mk
1ďkďK

we have
˙ ˆ
˙2M 2 ´1
ˆ?
´
¯
1
2
log
B
ptq
ptq
r
`
.
P ξk ă  or ξk ą 1 ´ , 1 ď k ď K, 1 ď t ď n ď 2nK Φ
σ
nK
Finally, this leads to:
2

2 {2

Result: Let  “ pLq “ 41 B ´ L . If (5.3) holds, then for B ě eL
ˆ
P

1
ptq
ptq
ξk p1´ξk q

Then
˜
P

c
max

1ďkďK
1ďtďn

2
ě , 1 ď t ď n, 1 ď k ď K


mk
2M
ptq
ptq
|p
ηk ´ ηk | ă
logpnKq


˙

˙ ˆ
˙2M 2 ´1
ˆ?
2
log
B
1
r
ď 2nK Φ
`
.
σ
nK

¸

´
!a
)¯ ˆ 1 ˙2M 2 ´1
´1
r
,
ě 1 ´ 2nK Φ σ min
2 log B, T
´
nK
22

2 {2

i.e. for L ą 0, if mmin ě 16M 2 logpnKqB 4{L and B ě eL
˜
P

c
max

1ďkďK
1ďtďn

2
mk
ptq
ptq
|p
ηk ´ ηk | ă 8M B L
logpnKq

,

¸

´
!a
)¯ ˆ 1 ˙2M 2 ´1
´1
r σ min
ě 1 ´ 2nK Φ
2 log B, T
´
.
nK
2 {2

Choose B “ eL

, then for L ą 0, if mmin ě 16M 2 logpnKqe2L ,
d
¸
˜
logpnKq
ptq
ptq
P max |p
ηk ´ ηk | ă 8M eL
1ďkďK
mmin
1ďtďn
ˆ
˙2M 2 ´1
` ´1
˘
1
r
ě 1 ´ 2nK Φ σ min tL, T u ´
nK
c
"
* ´
2 nKσ
pmintL, T uq2
1 ¯2M 2 ´1
exp ´
´
.
ě1´
π mintL, T u
2σ 2
nK

The proof of Lemma 3.1 with β ‰ 0 is similar but with
˜
¸
a
nK
ptq
a
P max |ηk | ą 2 log C ` µB ď
,
2
1ďkďK
1{σ
C
π log C 1{σ2
1ďtďn
ptq

which comes from ηk ´ µk „ N p0, σkk q and
ptq

ptq

max |ηk | ď max |ηk ´ µk | ` max |µk |.

1ďkďK
1ďtďn

5.2

1ďkďK
1ďtďn

1ďkďK

Proof of Theorem 3.1

We first introduce the ‘working assumption’
C0. |R|8 ă δ for fixed δ ą 0.
This assumption makes the proofs more transparent. Intermediate results are using this
assumptions. When applying these intermediate results to prove the main results (that
are not using assumption C0 explicitly), we will show that C0 holds with sufficiently
large probability.
The following fact that will be used repeatedly in the proofs, immediately follows from
the definition of R (see section 3.2):
?
Fact 5.1. Under assumption C0, }ηpk ´ ηk }2 ď nδ.

23

We prove a series of results: Theorem 5.1 and 5.2, Corollary 5.1, which will then
imply Theorem 3.1. The asseration of Theorem 3.1 follows from Corollary 5.1 together
with Lemma 3.1.
The proof is an adaptation of Meinshausen and Bühlmann (2006) (proof of Theorem
1) to our more complex situation. Both of the proofs are mainly established with a bound
s
on the tail behavior of the χ2 -distribution and properties of the Lasso. For any A Ă K,
a,A,λ,lasso
a,A
p
let the Lasso estimate θ
of θ
be defined as
´
¯
a,A,λ,lasso
´1
2
p
x
θ
“ arg min n }pηpa ´ µa 1n q ´ pH ´ 1n µqθ}2 ` λ}θ}1 .
(5.4)
θ:θk “0,@kRA

Claim 5.1. For problem (5.4), under assumption C0, for any q ą 1,
˙
ˆ
?
´
¯
2´
2 ´1qn
2q
pq
a,A,λ,lasso
2
´1
.
P }θp
}1 ď pq ` δq λ
ě 1 ´ exp ´
2
Proof. The claim follows directly from the tail bounds of the χ2 -distribution (see Laurent
and Massart (2000)) and the inequality
nλ}θpa,A,λ,lasso }1 ď }ηpa ´ µa 1n }22 ď p}ηpa ´ ηa }2 ` }ηa ´ µa 1n }2 q2 .

Lemma 5.2. Given θ P RK , let Gpθq be a K-dimensional vector with elements
x ´ 1n µT qθ, ηpb ´ µb 1n y.
Gb pθq “ ´2n´1 xpηpa ´ µa 1n q ´ pH
p “
s
A vector θp with θpk “ 0, @k P KzA
is a solution to (5.4) iff for all b P A, Gb pθq
p ď λ in case θpb “ 0. Moreover, if the solution is
´signpθpb qλ in case θpb ‰ 0, and |Gb pθq|
p ă λ for some solution θ,
p then θpb “ 0 for all solutions of (5.4).
not unique, and |Gb pθq|
This Lemma is almost the same as Lemma A.1 in MB (2006) but without normality
x Here and in what follows ‘MB (2006)’ is used as a shortcut for
assumption of H.
Meinshausen and Bühlmann (2006). Since the Gaussian assumption is not needed, the
proof is a straightforward adaptation of the proof of Lemma A.1 in MB (2006).
s let θpa,nea ,λ,lasso be defined as in (5.4). Let the penalty
Lemma 5.3. For every a P K,
parameter satisfy λn „ dn´p1´q{2 with some d ą 0 and κ ă  ă ξ. Suppose that
assumptions A1 and C0 hold with δ “ opn´p4´ξ´3q{2 q. Then there exists c ą 0 so that,
s
for all a P K,
¯
´
P signpθpa,nea ,λ,lasso q “ signpθa q, @b P nea “ 1 ´ Opexpp´cn qq as n Ñ 8.
b

b

Proof. Using similar notation as in MB (2006), we set
´
¯
x ´ 1n µT qθ}2 ` λ}θ}1 ,
θpa,nea ,λ,lasso “ arg min
n´1 }pηpa ´ µa 1n q ´ pH
2
θ:θk “0,@kRnea

24

(5.5)

s with b P nea , we let
and for all a, b P K
¯
´
´1
T
2
a,b,λ
r
x
θ
pωq “ arg min n }pηpa ´ µa 1n q ´ pH ´ 1n µ qθ}2 ` λ}θ}1 ,

(5.6)

θPΘa,b pωq

where
Θa,b pωq “ tθ P RKpnq : θb “ ω; θk “ 0, @k R nea u.
Setting ω “ θpba,nea ,λ,lasso , then θra,b,λ pωq “ θpa,nea ,λ,lasso , and by Claim 5.1 with q “ 2,
´
¯
P |θpba,nea ,λ,lasso | ď p2 ` δq2 λ´1 ě 1 ´ e´n{2 .
Thus, if signpθpba,nea ,λ,lasso q ‰ signpθba q, with probability at least 1 ´ exp t´2´1 nu, there
would exist some ω with |ω| ď p2 ` δq2 λ´1 so that θra,b,λ pωq is a solution to (5.5) but
signpωqsignpθba q ď 0. Without loss of generality, we assume θba ą 0 since signpθba q ‰ 0
for all b P nea . Note that by Lemma 5.2, θra,b,λ pωq can be a solution to (5.5) only if
Gb pθra,b,λ pωqq ě ´λ when ω ď 0. This means
´
¯
´
¯
P signpθpba,nea ,λ,lasso q ‰ signpθba q ď P
sup
Gb pθra,b,λ pωqq ě ´λ ` e´n{2 . (5.7)
2

ďωď0
´ p2`δq
λ

x ´ 1n µT qθra,b,λ pωq and write ηpb , ηb as
Let raλ pωq “ pηpa ´ µa 1n q ´ pH
ÿ
ÿ
b,ne ztbu
b,ne ztbu
θk a pp
θk a pηk ´ µk q ` wb ;
ηpb ´ µb “
ηk ´ µk q ` w
pb and ηb ´ µb “
kPnea ztbu

kPnea ztbu

and ηpa , ηa as
ηpa ´ µa “

ÿ

θka pp
ηk ´ µk q ` vpa

and ηa ´ µa “

kPnea

ÿ

θka pηk ´ µk q ` va ,

kPnea

where va and wb are independent normally distributed random variables with variances
2
2
2
2
σ´a
and σw,b
, respectivley, and 0 ă υ 2 ď σ´a
, σw,b
ď 1 by A1.2. Now we can write
η a ´ µa “

ÿ

b,nea ztbu

pθka ` θba θk

qpηk ´ µk q ` θba wb ` va ,

(5.8)

kPnea ztbu

pb of observations of w
pb , and also the
As in MB (2006), split the n-dimensional vector w
vector wb of observations of wb into the sum of two vectors, respectively,
pb||
pb “ w
pbK ` w
w
||

||

and wb “ wbK ` wb ,

||

pb are contained in the at most p|nea | ´ 1q-dimensional space W|| spanned
where wb and w
pbK are contained in the orthogonal
by the vectors tηk : k P nea ztbuu, while wbK and w
complement WK of W|| in Rn . Following the proof of MB (2006) (Appendix, Lemma
25

A.2.), we have
pb y ` λϑ,
Gb pθra,b,λ pωqq ď ´2n´1 xraλ pωq, w

(5.9)
||

pb y can be written as 2n´1 xraλ pωq, w
pbK y ` 2n´1 xraλ pωq, w
pb y. By defiwhere 2n´1 xraλ pωq, w
λ
K
pb , and (5.8),
nition of ra pωq, the orthogonality property of w
x ´ 1n µT qθra,b,λ pωq, w
pbK y “ 2n´1 xpηpa ´ µa 1n q ´ pH
pbK y
2n´1 xraλ pωq, w
p Ky
“ 2n´1 xpηa ´ µa 1n q ´ pH ´ 1n µT qθra,b,λ pωq, w
b

ra,b,λ

´1

x ´ Hqθ
` 2n xpηpa ´ ηa q ´ pH

pbK y
pωq, w

pbK y
pbK y ` 2n´1 xva , w
“ 2n´1 pθba ´ ωqxwbK , w
x ´ Hqθra,b,λ pωq, w
p Ky
` 2n´1 xpηpa ´ ηa q ´ pH
b

ě 2n

´1

pθba

´

pbK y
ωqxwbK , w

´1

pbK y|
xva , w

´ |2n
x ´ Hqθra,b,λ pωq}2 }w
pbK }2 .
´ 2n´1 }pηpa ´ ηa q ´ pH
?
pb ´ wb }2 ď pϑ ` 1q nδ under assumption C0.
Claim 5.2. }w

(5.10)

Proof. By assumption }θ b,nea ztbu }1 ď ϑ, an application of the triangle inequality and
Claim 5.1 gives the assertion.
pbK y|, we first consider |2n´1 xva , wbK y|,
In order to estimate the second term |2n´1 xva , w
which has already been estimated in MB (2006): for every g ą 0, there exists some
c “ cpg, dq ą 0 so that, as n Ñ 8,
`
˘
`
˘
P |2n´1 xva , wbK y| ě gλ ď P |2n´1 xva , wb y| ě gλ “ Opexpp´cn qq.
(5.11)
pbK y| ´ |xva , wbK y||, we have
Then for the difference ||xva , w
`
˘
n
pbK y| ´ |xva , wbK y|| ď 4pϑ ` 1qδ ě 1 ´ e´ 2 ,
P 2n´1 ||xva , w

(5.12)

which follows from the inequality
ˇ
ˇ
?
ˇ|xva , w
pbK y| ´ |xva , wbK y|ˇ ď }va }2 }w
pbK ´ wbK }2 ď pϑ ` 1q nδ}va }2
a
together with }va }2 „ σ´a χ2n . Thus, by (5.11) and (5.12),
`
˘
pbK y| ě gλ ` 4pϑ ` 1qδ “ Opexpp´cn qq as n Ñ 8.
P |2n´1 xva , w

(5.13)

Similarly, we have
˘
`
˘
`
pbK y ´ xwbK , wbK y| ď 4pϑ ` 1qδ ě 1 ´ exp ´2´1 n .
P 2n´1 |xwbK , w
´2
Note that σw,b
xwbK , wbK y follows a χ2n´|nea |`1 distribution, for n ě |nea |. Using again
the tail bound of the χ2 -distribution from Laurent and Massart (2000), we obtain with

26

2
assumption A.1.3.(a) and σw,b
ě υ 2 , that there exists n0 so that for n ą n0 ,

`
˘
P p2n´1 xwbK , wbK y ą υ 2 q ě 1 ´ exp ´32´1 n .
It follows that,
˘
`
pbK y ą υ 2 ´ 4pϑ ` 1qδ “ Opexpp´cn qq as n Ñ 8.
P 2n´1 xwbK , w

(5.14)

For the third term of (5.10), note that by definition of θra,b,λ pωq,
ÿ a,b,λ
x ´ Hqθra,b,λ pωq}2 ď }ηpa ´ ηa }2 `
}pηpa ´ ηa q ´ pH
|θrk pωq|}ηpk ´ ηk }2
kPnea

¯
? ´
ď nδ 1 ` }θra,b,λ pωq}1
and we also have
}θra,b,λ pωq}1 ´ |ω| ď n´1 }pηpa ´ µa 1n q ´ ωpηpb ´ µb 1n q}22 λ´1
`
˘2
ď n´1{2 }ηa ´ µa 1n }2 ` |ω|n´1{2 }ηb ´ µb 1n }2 ` δp1 ` |ω|q λ´1 .
?
pb }2 ď }wb }2 ` }w
pb ´ wb } ď }wb }2 ` pϑ ` 1q nδ, and the property of
Together with }w
the χ2 -distribution, we have with probability at least 1 ´ 3 exp p´2´1 nq,
x ´ Hqθra,b,λ pωq}2 }w
pb }2
2n´1 }pηpa ´ ηa q ´ pH
`
˘
ď 2 1 ` |ω| ` p1 ` |ω|q2 p2 ` δq2 λ´1 p2 ` pϑ ` 1qδq δ. (5.15)
Using (5.10), (5.13), (5.14) and (5.15), we obatin that with probability 1 ´ Opexpp´cn qq,
as n Ñ 8,
`
˘
pbK y ě pθba ´ ωq υ 2 ´ 4pϑ ` 1qδ ´ gλ ´ 4pϑ ` 1qδ
2n´1 xraλ pωq, w
˘
`
´ 2 1 ` |ω| ` p1 ` |ω|q2 p2 ` δq2 λ´1 p2 ` pϑ ` 1qδq δ.
Moreover, as will be shown in Lemma 5.4, there exists ng “ npgq so that, for all n ě ng ,
ˆ
P

˙
inf t2n

ωď0

´1

pb|| y{p1
xraλ pωq, w

` |ω|qu ě ´2 pgλ ` pϑ ` 1qδq p2 ` δq
`
˘
`
˘
ě 1 ´ 2 exp ´2´1 n ´ exp ´4´1 g 2 nλ2 .

Thus, with probability 1 ´ Opexpp´cn qq, as n Ñ 8,
`
˘
pb y ěpθba ´ ωq σb2 ´ 4pϑ ` 1qδ ´ gλ ´ 4pϑ ` 1qδ
2n´1 xraλ pωq, w
`
˘
´ 2 1 ` |ω| ` p1 ` |ω|q2 p2 ` δq2 λ´1 p2 ` pϑ ` 1qδq δ
´ 2 p1 ` |ω|q pgλ ` pϑ ` 1qδq p2 ` δq.

27

(5.16)

Note that λ „ dn´p1´q{2 with  ă ξ, and by A1.2 and A1.4, we have
d
Varpηb |ηKztbu
q
s
|θba | “ |πab |
ě vπab ě cvn´p1´ξq{2 .
Varpηa |ηKztau
q
s
Together with (5.16), for δ “ opn´p4´ξ´3q{2 q, we have for any l ą 0 that
ˆ
˙
´1
λ
pb yu ą lλ “ 1 ´ Opexpp´cn qq as n Ñ 8.
P
inf
t2n xra pωq, w
2 ´1
´p2`δq λ

ďωď0

Choosing l “ ϑ ` 1 and using (5.9), we have
˜
¸
P
sup
Gb pθra,b,λ pωqq ă ´λ “ 1 ´ Opexpp´cn qq as n Ñ 8.
´p2`δq2 λ´1 ďωď0

Then by Bonferroni’s inequality, assumption A1.3.(a) and (5.7),
´
¯
a,nea ,λ,lasso
a
p
P signpθb
q “ signpθb q, @b P nea “ 1 ´ Opexpp´cn qq as n Ñ 8.

Lemma 5.4. Under assumption C0, for any g ą 0, there exists ng “ npgq so that, for
all n ě ng ,
ˆ
P

inf t2n

ωď0

´1

pb|| y{p1
xraλ pωq, w

˙
` |ω|qu ě ´2 pgλ ` pϑ ` 1qδq p2 ` δq
`
˘
`
˘
ě 1 ´ 2 exp ´2´1 n ´ exp ´4´1 g 2 nλ2 .

Proof. Again following similar arguments as in MB (2006) (Appendix, Lemma A.3), we
have
||

||

pb y|{p1 ` |ω|q ď 2n´1{2 }w
pb }2
|2n´1 xraλ pωq, w

n´1{2 }raλ pωq}2
1 ` |ω|

and
ˆ
˙
`
˘
n´1{2 }raλ pωq}2
P sup
ą 2 ` δ ď P n´1{2 maxt}ηpa ´ µa 1n }2 , }ηpb ´ µb 1n }2 u ą 2 ` δ
1 ` |ω|
ωPR
`
˘
ď 2 exp ´2´1 n .
?
The last inequality uses that }ηk ´ µk 1n }22 „ χ2n and }ηpk ´ ηk }2 ď nδ. Note that
||
||
´2
σw,b
xwb , wb y follows a χ2|nea |´1 distribution for large n and |nea | “ opnλ2 q, and thus for
any g ą 0, there exists ng “ npgq so that for all n ě ng ,
´
¯
`
˘
||
P n´1{2 }wb }2 ą gλ ď exp ´4´1 g 2 nλ2 .
28

Together with Claim 5.2, for any g ą 0, there exists ng “ npgq so that, for all n ě ng ,
´
¯
`
˘
pb|| }2 ą gλ ` pϑ ` 1qδ ď exp ´4´1 g 2 nλ2 ,
P n´1{2 }w
and thus,
ˆ
˙
(
||
´1
λ
pb y|{ p1 ` |ω|q ď 2 pgλ ` pϑ ` 1qδq p2 ` δq
P sup |2n xra pωq, w
ωPR
`
˘
`
˘
ě 1 ´ exp ´4´1 g 2 nλ2 ´ 2 exp ´2´1 n .

Theorem 5.1. Assume that A1 holds and that µ is known. Let the penalty parameter
satisfy λn „ dn´p1´q{2 with d ą 0 and κ ă  ă ξ. If, in addition, C0 holds with
s
δ “ opnmint´p4´ξ´3q{2,´κ´1u q, then for all a P K,
p λ,lasso
P pne
Ď nea q “ 1 ´ Opexpp´cn qq
a

as n Ñ 8.

Proof. Following the proof of Theorem 1, MB (2006), we have
s a : θpa,λ,lasso ‰ 0q,
p λ,lasso
P pne
Ď nea q “ 1 ´ P pDb P Kzcl
a
b
and
˙
ˆ
´
¯
a,λ,lasso
a,nea ,λ,lasso
p
p
s
P Db P Kzcla : θb
q| ě λ ,
‰ 0 ď P max |Gb pθ
s a
bPKzcl

where
x ´ 1n µT qθpa,nea ,λ,lasso , ηpb ´ µb 1n y.
Gb pθpa,nea ,λ,lasso q “ ´2n´1 xpηpa ´ µa 1n q ´ pH
s a , write
For any b P Kzcl
ÿ b,ne
ηpb ´ µb “
θk a pp
ηk ´ µk q ` vpb

and ηb ´ µb “

kPnea

ÿ

θkb,nea pηk ´ µk q ` vrb ,

(5.17)

kPnea

2
2
where vrb „ N p0, σv,b
q with υ 2 ď σv,b
ď 1 and is independent of tηk : k P cla u.

Claim 5.3. Under
assumption C0, for any q ą 1, with probability at least 1 ´ p|nea | `
?
)
!
pq 2 ´ 2q 2 ´1qn
,
2q exp ´
2
ˇ
ˇ
x ´ 1n µT qθpa,nea ,λ,lasso , v
ˇxηpa ´ µa 1n ´ pH
pb y ´ xηa ´ µa 1n ´ pH ´ 1n µT qθpa,nea ,λ,lasso , v
rb yˇ
`
˘`
˘
ď n λ´1 pq ` δq ` 1 1 ` υ ´1 |nea | p2q ` δqδ;
?
!
)
pq 2 ´ 2q 2 ´1qn
and with probability at least 1 ´ p|nea | ` 1q exp ´
,
2

29

ˇ`
˘
x ´ 1n µT qθpa,nea ,λ,lasso }2 ´ }ηpa ´ µa 1n }2 ´
ˇ }pηpa ´ µa 1n q ´ pH
2
2
`
˘ˇ
}pηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso }22 ´ }ηa ´ µa 1n }22 ˇ
`
˘
ď n pλ´1 pq ` δq ` 1q2 ` 1 p2q ` δqδ.
Proof. Using triangle inequality and Cauchy’s inequality,
ˇ
x ´ 1n µT qθpa,nea ,λ,lasso , v
ˇpxηpa ´ µa 1n q ´ pH
pb y
ˇ
rb yˇ
´ xpηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso , v
¯
´ ÿ
vb }2
ď
|θpka,nea ,λ,lasso |}ηpk ´ ηk }2 ` }ηpa ´ ηa }2 }p
kPnea

ď

´` ÿ
kPnea

rb }2
` }ηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso }2 }p
vb ´ v
ÿ
˘
?
|θpka,nea ,λ,lasso |}ηk ´ µk 1n }2
|θpka,nea ,λ,lasso | ` 1 nδ `
kPne

a
¯
´ ÿ
¯?
a,nea ,λ,lasso
p
rb }2 `
` }ηa ´ µa 1n }2 }p
vb ´ v
|θk
| ` 1 nδ}r
vb }2 . (5.18)

kPnea

By definition of vpb and vrb in (5.17), and by using the triangle inequality,
´ ÿ
¯?
rb }2 ď
}p
vb ´ v
|θkb,nea | ` 1 nδ.
kPnea

Moreover, by the definition of partial correlation and assumption A1.4,
d
Varpηb |ηnea q
b,nea
1 ě |πbk
| “ |θkb,nea |
ě v|θkb,nea |,
Varpηk |ηtbuYnea ztku q
and thus

?
rb }2 ď pυ ´1 |nea | ` 1q nδ.
}p
vb ´ v

(5.19)

Using (5.18), (5.19), Claim 5.1 and
of chi-square distribution, with proba? the property
)
!
2
2
pq ´ 2q ´1qn
bility 1 ´ p|nea | ` 2q exp ´
,
2
ˇ
ˇ
x ´1n µT qθpa,nea ,λ,lasso , v
ˇxpηpa ´µa 1n q´pH
pb y´xpηa ´µa 1n q´pH ´1n µT qθpa,nea ,λ,lasso , v
rb yˇ
`
˘`
˘
ď n pq ` δqλ´1 ` 1 1 ` υ ´1 |nea | p2q ` δqδ.
The second part follows similarly.
Lemma 5.2, 5.3 and assumption A1.5 imply that, for any δ “ opn´p4´ξ´3q{2 q, there exists
s and b P Kzcl
s a , for n Ñ 8,
c ą 0 so that for all a P K
´
¯
x ´ 1n µT qθpa,nea ,λ,lasso , v
pb y|
P |Gb pθpa,nea ,λ,lasso q| ď %λ ` |2n´1 xpηpa ´ µa 1n q ´ pH
“ 1 ´ Opexpp´cn qq. (5.20)
30

x ´ 1n µT qθpa,nea ,λ,lasso , v
pb y|. Note that
Now we need to estimate |2n´1 xpηpa ´ µa 1n q ´ pH
by Claim 5.3, for any δ “ Op1q, there exists some constant B ą 0 and c ą 0 so that for
n Ñ 8, with probability 1 ´ Opexpp´cn qq,
x ´1n µT qθpa,nea ,λ,lasso , v
pb y´xpηa ´µa 1n q´pH ´1n µT qθpa,nea ,λ,lasso , v
rb y|
|xpηpa ´µa 1n q´pH
ď Bn3{2´{2`κ δ. (5.21)
ř
rb “ ηb ´ kPnea θkb,nea ηk , we
We already know that vrb KKηcla 2 ; also, ηpcla KKηKzcl
s a |ηcla and v
have vrb KKηpcla |ηcla . Thus, vrb KKtηcla , ηpcla u. Here KK denotes independence. Conditional on
xcla u “ tηk , ηpk : k P cla u, the random variable
tHcla , H
rb y
xpηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso , v
is normally distributed with mean zero and variance
2
σv,b
}pηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso }22 .

By definition of θpa,nea ,λ,lasso ,
x ´ 1n µT qθpa,nea ,λ,lasso }2 ď }ηpa ´ µa 1n }2 ;
}pηpa ´ µa 1n q ´ pH
and by Claim 5.3, for δ “ Op1q, there exists constant c, B ą 0 so that, with probability
1 ´ Opexpp´cn qq, as n Ñ 8, as n Ñ 8,
ˇ`
˘
x ´ 1n µT qθpa,nea ,λ,lasso }2 ´ }ηpa ´ µa 1n }2
ˇ }pηpa ´ µa 1n q ´ pH
2
ˇ
´ p}pηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso }22 ´ }ηa ´ µa 1n }22 qˇ ď Bn2´ δ.
Futhermore, for δ “ Opnmint0,2τ `´2u q, there exists ct ą 0, such that for ta “ ct nτ , as
n Ñ 8,
´
¯
T pa,nea ,λ,lasso 2
2
2
P }pηa ´ µa 1n q ´ pH ´ 1n µ qθ
}2 ď }ηa ´ µa 1n }2 ` ta “ 1 ´ Opexpp´cn qq,
rb y| is stochastically smaller than
thus, |2n´1 xpηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso , v
´1
r
|2n pxηa ´ µa 1n , vb y ` ta zb q| with probability 1 ´ Opexpp´cn qq, as n Ñ 8, where zb „
2
N p0, σv,b
q and is independent of other random variables. Since vrb and ηa are independent,
Epηa vrb q “ 0. Using the Gaussianity and Bernstein’s inequality,
`
˘
`
˘
rb y ` ta zb q| ě p1 ´ %qλ{2 “ O expt´cnmint,1`´2τ u u as n Ñ 8.
P |2n´1 pxηa ´ µa 1n , v
and thus for δ “ Opnmint0,2τ `´2u q, as n Ñ 8,
´
¯
rb y| ě p1 ´ %qλ{2
P |2n´1 xpηa ´ µa 1n q ´ pH ´ 1n µT qθpa,nea ,λ,lasso , v
2

This follows from the Markov properties of the conditional independence graph and the contraction
property of conditional independence.

31

`
˘
“ O expt´cnmint,1`´2τ u u . (5.22)
By (5.20), (5.21) and (5.22), for` δ “ opn´p4´ξ´3q{2 q and
δ “ Opn2τ `´2 q, there exists
˘
c, B ą 0, with probability 1 ´ O expt´cnmint,1`´2τ u u , as n Ñ 8,
|Gb pθpa,nea ,λ,lasso q| ă p1 ` %qλ{2 ` Bn1{2´{2`κ δ,
and we obtain that for δ “ opnmint´p4´ξ´3q{2,´κ´1u q,
ˆ
˙
a,ne
,λ,lasso
a
P max |Gb pθp
q| ě λ “ O pexpp´cn qq

as n Ñ 8.

s
bPKztau

Theorem 5.2. Let assumption A1 hold and assume µ to be known. Let the penalty
parameter satisfy λn „ dn´p1´q{2 with some d ą 0 and κ ă  ă ξ. If, in addition, C0
s
holds with δ “ opnmint´p4´ξ´3q{2,´κ´1u q, for all a P K,
p λ,lasso
P pnea Ď ne
q “ 1 ´ Opexpp´cn qq as n Ñ 8.
a
Proof. Using Theorem 5.1 and Lemma 5.3, the proof is similar to MB (2006), proof of
Theorem 2.
Corollary 5.1. Let assumption A1 hold and assume µ to be known. Let the penalty
parameter satisfy λn „ dn´p1´q{2 with some d ą 0 and κ ă  ă ξ. If, in addition, C0
holds with δ “ opnmint´p4´ξ´3q{2,´κ´1u q, then there exists c ą 0 so that
p λ,lasso “ Eq “ 1 ´ Opexpp´cn qq
P pE

as n Ñ 8.

p λ,lasso ‰ E if and only if there exists a P K
s so that ne
p λ,lasso
Proof. Note that E
‰ nea . The
a
result now follows from Theorem 5.1 and Theorem 5.2 by using Bonferroni’s inequality
and assumption A1.1.

5.3

Proof of Theorem 3.2

We prove a series of results, which will then imply Theorem 3.2. The asseration of
Theorem 3.2 follows from Corollary 5.3 together with Lemma 3.1. First we introduce
some notation. Let
s “ max |nea |
s
aPK

1
pH ´ 1n µT qT pH ´ 1n µT q
n
1
s
Ψa “ pH´a ´ 1n µT´a qT pH´a ´ 1n µT´a q for each a P K.
n

Ψ“

32

s
We also define for each a P K,
¨
κaq psq “ min ˝
J:|J|ďs

min

˛

∆PRp :}∆J c }1 ď}∆J }1
}∆}q “1

|Ψa ∆|8 ‚,

1 ď s ď K, 1 ď q ď 8.

(5.23)

Claim 5.4.
B1.2 and B1.4 imply the existence of n0 ą 0 and υ 2 ą 0 so
` Assumptions
˘
2
s and n ě n0 .
that Var ηa |ηKztau
ě υ , for all a P K
s
Proof. We first note that under our Gaussian assumption, Varpηa |ηKztau
q “ Varpηa |ηnea q.
s
s
Using the formula of Gaussian conditional covariance matrix, we have, for all a P K,
´1
2
Varpηa |ηnea q “ σaa ´ Σa,nea Σ´1
nea ,nea Σnea ,a ě σaa ´ λmin pΣnea ,nea q}Σa,nea }2

By assumption B1.2 and B1.4, we have
max }Σa,nea }22 ď max |nea ||Σ ´ I|28
s
aPK

s
aPK

and all submatrices pΣnea ,nea qaPKs are diagonally dominant both by rows and columns for
large n; using the lower bound for singular values of a diagonally dominant matrix by
Varah (1975), we obtain
¯
´
ř
min λmin pΣnea ,nea q ě min min σkk ´ jPnea ztku |σkj |
s
aPK

s kPnea
aPK

ě 1 ´ |Σ ´ I|8 ´ max |nea ||Σ ´ I|8 .
s
aPK

Thus, for n large enough,
min Varpηa |ηKztau
q ě 1 ´ |Σ ´ I|8 ´ s p1 ´ ps ` 1q|Σ ´ I|8 q´1 |Σ ´ I|28
s
s
aPK

“ 1 ´ opn´κ q as n Ñ 8,
which shows the claim.
`
˘
1
Claim` 5.5.˘ |Ψ ´ I|8 ă 3αs
with probability greater than 1 ´ K 2 exp ´ 600αn2 s2 σ4 ´
n
K exp ´ 32
for n large enough.
´1
Proof. Denote Σ “ pσab qKˆK . For b ‰ a, we have ηb ´ µb 1n “ σba σaa
pηa ´ µa 1n q ` vba ,
where each element of vba is a zero mean normal with variance σb|a ď σbb . Using a tail
bound for the chi-squared distribution from Johnstone (2001) and Bernstein’s inequality,
we have for b P nea , and n large enough,
ˇ
´ˇ 1
1 ¯
ˇ
ˇ
P ˇ pηa ´ µa 1n qT pηb ´ µb 1n q ´ σab ˇ ą
6αs ˙
ˆn ˇ
ˆˇ
˙
ˇ
ˇ
1
1
ˇ pηa ´ µa 1n qT pηa ´ µa 1n q
ˇ
ˇ pηa ´ µa 1n qT vba ˇ
ďP σba ˇ
´ 1ˇ ą
`P ˇ
ˇą
nσaa
12αs
n
12αs
ˆ
˙
ˆ
˙
ˇ
ˇ
ˇ
ˇ
1
1
ďP ˇn´1 χ2n ´ 1ˇ ą ?
` P ˇn´1 pηa ´ µa 1n qT vba ˇ ą
12αs
6

33

ˆ
˙
´ n¯
n
ď exp ´
` 2 exp ´
32
600α2 s2 σaa σbb
and
ˆˇ
˙
ˆ
˙
ˇ
1
1
ˇ1
ˇ
T
´1 2
P ˇ pηa ´ µa 1n q pηa ´ µa 1n q ´ σaa ˇ ą
“ P |n χn ´ 1| ą
n
6αs
6αsσaa
˙
ˆ
n
;
ď exp ´
2
192α2 s2 σaa
Thus, for n large enough, by using Bonferroni’s inequality,
ˆ
˙
´
¯
´ n¯
1
n
P |Ψ ´ Σ|8 ą
ď K 2 exp ´
`
K
exp
´
.
6αs
600α2 s2 σ 4
32
Together with the fact that |Ψ ´ I|8 ď |Ψ ´ Σ|8 ` |Σ ´ I|8 and |Σ ´ I|8 ď
large n, the result follows.

1
6αs

for

Claim 5.6. Under assumption C0, for any q ą 0, we have with probability no less than
2
1 ´ 2K 2 expt´ 4σ4nq
u ´ 2K exp p´2´1 nq,
`2σ 2 q
ˇ
ˇ
ˇ
x´a ´ 1n µT qT ξa ˇˇ ď q ` 4σδ ` δ 2 .
max ˇn´1 pH
´a
s
aPK

8

Proof. By straightforward calculation,
ˇ
ˇ
ˇ
x´a ´ 1n µT qT ξa ˇˇ
max ˇn´1 pH
´a
s
aPK
ˇ
ˇ8
ˇ
ˇ
ˇ ´1 x
ˇ
ˇ
x´a ´ 1n µT qT pηpa ´ ηa qˇˇ
ď max ˇn pH´a ´ 1n µT´a qT va ˇ ` max ˇn´1 pH
´a
s
s
8
8
aPK
aPK
ˆ
˙
ˇ
ˇ
´1 ˇ
T
´1{2
ˇ
ď max max n pηb ´ µb 1n q va ` n
max }ηa ´ µa 1n }2 ` max }va }2 δ ` δ 2 .
s bPKztau
s
aPK

s
aPK

s
aPK

Note that n´1 |pη ´ µa 1n qTb va | can be estimated by Bernstein’s inequality, and both
´1
}ηa ´ µa 1n }22 and σaa
}va }22 are chi-square distributed. Thus, together with Bonferroni’s
inequality, gives
*
ˆ
˙
"
ˇ
ˇ
nq 2
´1 ˇ
T
2
ˇ
P max max n pηb ´ µb 1n q va ě q ď 2K exp ´ 4
s bPKztau
s
4σ ` 2σ 2 q
aPK
and
ˆ
P

˙
n

´1{2

pmax }ηa ´ µa 1n }2 ` max }va }2 q ą 4σ
s
aPK

s
aPK

34

`
˘
ď 2K exp ´2´1 n .

Claim 5.7. For any α ą 1, there exists nα “ npαq so that, for all n ě nα ,
˙
ˆ
˘
` n˘
`
´1
a
ď 1 ´ K 2 exp ´ 150αn2 s2 σ4 ´ K exp ´ 32
.
P max κ8 psq ě 1 ´ α
s
aPK

s
Proof. The result follows from Claim 5.5 and the inequality below: for all a P K,
˜
¸
˜
¸
κa8 psq ě min

J:|J|ďs

min

∆PRp :}∆J c }1 ď}∆J }1
|∆|8 “1

ě 1 ´ max

J:|J|ďs

max

|∆|8

∆PRp :}∆J c }1 ď}∆J }1
|∆|8 “1

´ max

max

∆PRp :}∆J c }1 ď}∆J }1
|∆|8 “1

J:|J|ďs

|pΨa ´ Iq ∆|8

}∆}1 |Ψa ´ I|8

ě 1 ´ 2s |Ψ ´ I|8 .

1´

2 q
Theorem 5.3. Let assumption B1 hold and assume µ to be known. Let λ´1
n “ Opn
with some  ą 0 be such that ξ ą  ą 2κ ´ 2p ` 1. If, in addition, C0 holds with
δ “ Opn´p q for some p ą κ ` p1 ´ ξq{2,

p λ,ds “ Eq “ 1 ´ Opexpp´cnmint,1´2κu qq
P pE

as n Ñ 8.

Proof. Note that by Claim 5.6, the property of chi-square distribution, and
ˇ
`
˘ˇ
ˇ ´1 x
T T
T
a ˇ
x
ˇn pH´a ´ 1n µ´a q pηpa ´ µa 1n q ´ pH ´ 1n µ qθ ˇ
8
ˇ
`
˘ˇˇ
ˇ ´1 x
T T
T
a
a
x
“ ˇn pH´a ´ 1n µ´a q pH´a ´ 1n µ´a qθ´a ` ξa ´ pH´a ´ 1n µT´a qθ´a
ˇ
8
ˇ
ˇ
ˇ
ˇ
ˇ ´1 x
ˇ ´1 x
ˇ
T T
a ˇ
T T
ď ˇn pH´a ´ 1n µ´a q R´a θ´a ˇ ` max ˇn pH´a ´ 1n µ´a q ξa ˇ
s
8
8
ˆ
˙ aPK
ˇ
ˇ
?
ˇ
x´a ´ 1n µ´a qT ξa ˇˇ ,
ďn´1{2 δ
nδ ` max }ηb ´ µb 1n }2 sυ ´1 ` max ˇn´1 pH
s
bPK

s
aPK

8

we have for each q ą 0, that with probability no less than 1 ´ 2K expt´2´1 nu ´
2
2K 2 expt´ 4σ4nq
u,
`2σ 2 q
ˇ
´
¯ˇ
ˇ ´1 x
T T
T
a ˇ
x
max ˇn pH´a ´ 1n µ´a q pηpa ´ µa 1n q ´ pH ´ 1n µ qθ ˇ
s
aPK

8

ď q ` p4σ ` δqδ ` p2σ ` δqυ ´1 sδ
1´

1´

´ 2
2 q, which means there exits b ą 0 so that λ
Note that λ´1
for all
n ě bn
n “ Opn
´ 1´
κ´p
a
2
n large enough. Moreover, sδ “ Opn q “ opλa,n p}θ q}1 q. Choosing q “ bn
{2, we
obtain q ` 2υ ´1 sδ ď λa,n p}θ a }1 q for all large n. Thus

´ˇ
¯
`
˘ˇ
´1 x
T T
T
a ˇ
a
x
s
ˇ
P n pH´a ´ 1n µ´a q pηpa ´ µa 1n q ´ pH ´ 1n µ qθ 8 ď λa,n p}θ }1 q, @a P K
“ 1 ´ Opexpp´cn qq as n Ñ 8,
35

which means that the true parameter θ a falls into the feasible set of problem (3.10) with
probability 1 ´ Opexpp´cn qq as n Ñ 8.
a,λ,ds
a
. By calculation,
Let ∆a “ θr´a
´ θ´a
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ1 T
ˇ
ˇ1
T
T
T
a
T
a
a a
x´a ´ 1n µ q pH´a ´ 1n µ q∆ ˇ ` ˇ R pH´a ´ 1n µ q∆ ˇ
|Ψ ∆ |8 ď ˇˇ pH
´a
´a
´a
´a
ˇ
ˇn
ˇ
n
8
8
ˇ
ˇ
ˇ
ˇ1
a,λ,ds
x´a ´ 1n µT qT ppηpa ´ µa 1n q ´ pH
x´a ´ 1n µT qθr´a qˇ
ď ˇˇ pH
´a
´a
ˇ
n
8
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ1
ˇ
ˇ
1
a,ds ˇ
T T
T T
r
x
x
ˇ
ˇ
ˇ
` ˇ pH´a ´ 1n µ´a q ξa ˇ ` ˇ pH´a ´ 1n µ´a q R´a θ´a ˇ
n
n
8
ˇ 8
ˇ
ˇ1 T
ˇ
` ˇˇ R´a pH´a ´ 1n µT´a q∆a ˇˇ
n
8
ˇ
ˇ
ˇ
ˇ
1 x
T T
2 ra,λ,ds
ˇ
}1
ďλa,n p}θra,λ,ds }1 q ` ˇˇ pH
´a ´ 1n µ´a q ξa ˇ ` δ }θ´a
n
8
¯
1 ´ ra,λ,ds
a
` ? 2}θ´a }1 ` }θ´a }1 δ max }ηb }2 .
s
n
bPK
a,λ,ds
Then, by Claim 5.6, the definition of θr´a
and the property of chi-square distribution,
the following holds. For any constant d ą 0, there exists some c “ cpdq ą 0 so that as
n Ñ 8,
¯
´
1´
s “ 1 ´ O pexpp´cn qq .
P |Ψa ∆a |8 ď λa,n p}θra,λ,ds }1 q ` dn´ 2 ` 4υ ´1 sδ, @a P K

By definition, we have κ8 psq|∆a |8 ď |Ψa ∆a |8 . Using Claim 5.7, there exists some c ą 0
so that for any t ą 1,
´
¯
`
˘
s “ 1 ´ O expp´cnmint1´2κ,u q
P |∆a |8 ď tλa,n p}θra,λ,ds }1 q, @a P K
for n Ñ 8.
The assertion of Theorem 5.3 follows from the fact that |θba | “ Ωpn´p1´ξq{2 q for all b P nea ,
s and maxaPKs λa,n p}θ a }1 q “ opn´ 1´ξ
2 q.
aPK

5.4

Proof for Section 3.5

s under assumption C0,
To verify Theorem 3.3, first observe that for all k P K,
pk ´ µk | ď |ηs
pk ´ ηsk | ` |s
|ηs
ηk ´ µk |
1
“ }1Tn pηpk ´ ηk q}2 ` |s
η k ´ µk |
n
1
ď ? }ηpk ´ ηk }2 ` |s
η k ´ µk |
n
ηk ´ µk |.
ď δ ` |s

36

?
?
?
nps
ηk ´ µk q{ σkk „ N p0, 1q and σ “ maxkPKs σkk , we obtain
c
"
*
´
¯
ÿ ˆ?nδµ ˙
nδµ2
2
Kσ
r ?
?
η k ´ µ k | ě δµ ď 2
ď
exp ´ 2 ,
P max |s
Φ
s
σ
π
nδµ
2σ
kPK
kk
s

Recalling that

(5.24)

kPK

thus,
c
´

¯

pk ´ µk | ě δ ` δµ ď
P max |ηs
s
kPK

"
*
nδµ2
2 Kσ
?
exp ´ 2 .
π nδµ
2σ

?
pk ´ µk |, we have
K maxkPKs |ηs
"
*
´ b´γ
¯ c 2 Kσ
nδµ2
b´γ
1
s
?
p ´ µ}2 ě n 2 K 2 pδ ` δµ q ď
P n 2 }η
exp ´ 2
π nδµ
2σ

s
p ´ µ}2 ď
Using the trivial bound }η

as n Ñ 8.

b

Thus, for δ “ opn´ 2 q with b ă 1, and K “ Opnγ q, we obtain that, for any fixed δ0 ą 0,
´ b´γ
¯
`
˘
s
2
p ´ µ} ě δ0 “ O expp´cn1´b q
P n }η
as n Ñ 8,
which, if combined with Lemma 3.1 (note that the above arguments assume C0) is the
p Using the
first statement of Theorem 3.3. Recall that β “ X ` µ and βp “ X ` η.
assumptions, rankpXq “ L and σmax pXq “ Op1q, we also obtain that, for fixed δ0 ą 0,
¯
´ b´γ
`
˘
as n Ñ 8.
P n 2 }βp ´ β} ě δ0 “ O expp´cn1´b q
Together with Lemma 3.1, we have the results in Theorem 3.3. For Corollary 3.1 and
s
x by H
x ´ 1n η
p T in (3.7). For
Corollary 3.2, recall that, since µ is unknown, we replace H
our model (cf. 3.4), this means that we replace R by
¯
´
ptq
ptq
s
r “ pH
x ´ 1n η
p T q ´ pH ´ 1n µT q “ pp
pk q ´ pηk ´ µk q 1ďtďn .
R
ηk ´ ηs
(5.25)
1ďkďK

s
Note that under assumption C0, for all k P K,
ptq
ptq
ptq
ptq
pk ´ µk | ď 2δ ` |s
pk q ´ pηk ´ µk q| ď |p
ηk ´ µk |,
ηk ´ ηk | ` |ηs
|pp
ηk ´ ηs

which means
r 8 ď 2δ ` max |s
|R|
ηk ´ µk |.

(5.26)

c
"
*
´
¯
nδµ2
2
Kσ
r 8 ď 2δ ` δµ ě 1 ´
?
P |R|
exp ´ 2 .
π nδµ
2σ

(5.27)

s
kPK

Together with (5.24), we have

37

Using (5.27), Corollary 5.1 (or Theorem 5.3) and Lemma 3.1, we have Corollary 3.1 and
Corollary 3.2.

References
Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and variable selection with the lasso. The Annals of Statistics, pages 1436–1462, 2006.
Mathieu Rosenbaum, Alexandre B Tsybakov, et al. Sparse recovery under matrix uncertainty. The Annals of Statistics, 38(5):2620–2651, 2010.
Alexandre Belloni, Mathieu Rosenbaum, and Alexandre Tsybakov. Linear and conic
programming estimators in high-dimensional errors-in-variables models. Journal of
the Royal Statistical Society, Series B, 79:939–956, 2017.
Eric D Kolaczyk. Statistical analysis of network data: methods and models. Springer
Science & Business Media, 2009.
Mark Newman. Networks: An introduction. Oxford University Press, 2010.
Lei Tang and Huan Liu. Community detection and mining in social media. Synthesis
Lectures on Data Mining and Knowledge Discovery, 2(1):1–137, 2010.
Ove Frank and David Strauss. Markov graphs. Journal of the American Statistical
Association, 81(395):832–842, 1986.
Stanley Wasserman and Philippa Pattison. Logit models and logistic regressions for social
networks: I. an introduction to markov graphs and p˚ . Psychometrika, 61(3):401–425,
1996.
Michael Schweinberger and Mark S Handcock. Local dependence in random graph models: characterization, properties and statistical inference. Journal of the Royal Statistical Society: Series B, 2014.
Kevin S Xu and Alfred O Hero. Dynamic stochastic blockmodels for time-evolving social
networks. Journal of Selected Topics in Signal Processing, 8(4):552–562, 2014.
Emmanuel Candes and Terence Tao. The dantzig selector: Statistical estimation when
p is much larger than n. The Annals of Statistics, pages 2313–2351, 2007.
Ming Yuan. High dimensional inverse covariance matrix estimation via linear programming. Journal of Machine Learning Research, 11(Aug):2261–2286, 2010.
Paulo E. Oliveira. Asymptotics for Associated Random Variables. Springer-Verlag Berlin
Heidelberg, 2012.
Han Liu, John Lafferty, and Larry Wasserman. The nonparanormal: Semiparametric
estimation of high dimensional undirected graphs. Journal of Machine Learning Research, 10:2295–2328, 2009.
38

Shuheng Zhou, Philipp Rütimann, Min Xu, and Peter Bühlmann. High-dimensional covariance estimation based on gaussian graphical models. Journal of Machine Learning
Research, 12:2975–3026, 2011.
Adam J Rothman, Peter J Bickel, Elizaveta Levina, and Ji Zhu. Sparse permutation
invariant covariance estimation. Electronic Journal of Statistics, 2:494–515, 2008.
Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by
model selection. The Annals of Statistics, 28(5):1302–1338, 2000.
James M Varah. A lower bound for the smallest singular value of a matrix. Linear
Algebra and its Applications, 11(1):3–5, 1975.
Iain M. Johnstone. Chi-square oracle inequalities. volume 36 of Lecture Notes-Monograph
Series, pages 399–418. Springer, 2001.

39

Supplemental material
Here we present further results of our simulation studies of the three methods introduced
in the manuscript.

5.5

Results: finite-sample performance as a function of the
penalty parameter

ROC curves are shown in figure 6 - 10 for each of the following six cases: n “ 100 and
K “ 15, 30, 50, 80, 100. The ROC curves are color-coded: Lasso: red, Dantzig selector:
blue and MU-selector: green. λopt is the tuning parameter corresponding to the total
(overall) minimum error rate.

Figure 6: ROC curves comparing the three proposed methods for K “ 15 and n “ 100

Figure 7: ROC curves comparing the three proposed methods for K “ 30 and n “ 100

40

Figure 8: ROC curves comparing the three proposed methods for K “ 50 and n “ 100

Figure 9: ROC curves comparing the three proposed methods for K “ 80 and n “ 100

Figure 10: ROC curves comparing the three proposed methods for K “ 100 and n “ 100

41

The average error rates for the three methods are shown in figure 11 - 15 for each of
cases: n “ 100 and K “ 15, 30, 50, 80, 100.

1
2
3
Tuning parameter λ

4

0

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

total
type I
type II

0.00

0.15

0.05
0.10
Tuning parameter λ

0.10
0.20
Tuning parameter λ

MU selector: ρ = 0.8

0.15

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

Figure 11: Average error rates as functions of λ for K “ 15 and n “ 100.

42

4

total
type I
type II

0.00

total
type I
type II

0.00

1
2
3
Tuning parameter λ

Dantzig selector: ρ = 0.8

MU selector: ρ = 0.5

total
type I
type II

0.05
0.10
Tuning parameter λ

0

0.10
0.20
Tuning parameter λ

Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

MU selector: ρ = 0.2

0.00

4

Dantzig selector: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Dantzig selector: ρ = 0.2

1
2
3
Tuning parameter λ

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

0

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

total
type I
type II

Lasso: ρ = 0.8
Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.2

0.15

1
2
3
Tuning parameter λ

4

0

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

total
type I
type II

0.00

0.15

0.05
0.10
Tuning parameter λ

0.10
0.20
Tuning parameter λ

MU selector: ρ = 0.8

0.15

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

Figure 12: Average error rates as functions of λ for K “ 30 and n “ 100.

43

4

total
type I
type II

0.00

total
type I
type II

0.00

1
2
3
Tuning parameter λ

Dantzig selector: ρ = 0.8

MU selector: ρ = 0.5

total
type I
type II

0.05
0.10
Tuning parameter λ

0

0.10
0.20
Tuning parameter λ

Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

MU selector: ρ = 0.2

0.00

4

Dantzig selector: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Dantzig selector: ρ = 0.2

1
2
3
Tuning parameter λ

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

0

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

total
type I
type II

Lasso: ρ = 0.8
Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.2

0.15

1
2
3
Tuning parameter λ

4

0

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

total
type I
type II

0.00

0.15

0.05
0.10
Tuning parameter λ

0.10
0.20
Tuning parameter λ

MU selector: ρ = 0.8

0.15

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

Figure 13: Average error rates as functions of λ for K “ 50 and n “ 100.

44

4

total
type I
type II

0.00

total
type I
type II

0.00

1
2
3
Tuning parameter λ

Dantzig selector: ρ = 0.8

MU selector: ρ = 0.5

total
type I
type II

0.05
0.10
Tuning parameter λ

0

0.10
0.20
Tuning parameter λ

Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

MU selector: ρ = 0.2

0.00

4

Dantzig selector: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Dantzig selector: ρ = 0.2

1
2
3
Tuning parameter λ

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

0

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

total
type I
type II

Lasso: ρ = 0.8
Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.2

0.15

1
2
3
Tuning parameter λ

4

0

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

total
type I
type II

0.00

0.15

0.05
0.10
Tuning parameter λ

0.10
0.20
Tuning parameter λ

MU selector: ρ = 0.8

0.15

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

Figure 14: Average error rates as functions of λ for K “ 80 and n “ 100.

45

4

total
type I
type II

0.00

total
type I
type II

0.00

1
2
3
Tuning parameter λ

Dantzig selector: ρ = 0.8

MU selector: ρ = 0.5

total
type I
type II

0.05
0.10
Tuning parameter λ

0

0.10
0.20
Tuning parameter λ

Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

MU selector: ρ = 0.2

0.00

4

Dantzig selector: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Dantzig selector: ρ = 0.2

1
2
3
Tuning parameter λ

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

0

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

total
type I
type II

Lasso: ρ = 0.8
Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.2

0.15

1
2
3
Tuning parameter λ

4

0

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

total
type I
type II

0.00

0.15

0.05
0.10
Tuning parameter λ

4

total
type I
type II

0.00

0.10
0.20
Tuning parameter λ

MU selector: ρ = 0.8

total
type I
type II

0.00

1
2
3
Tuning parameter λ

Dantzig selector: ρ = 0.8

MU selector: ρ = 0.5

total
type I
type II

0.05
0.10
Tuning parameter λ

0

0.10
0.20
Tuning parameter λ

Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

MU selector: ρ = 0.2

0.00

4

Dantzig selector: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Dantzig selector: ρ = 0.2

1
2
3
Tuning parameter λ

total
type I
type II

0.15

Average error rates
0.0
0.4
0.8
1.2

0

total
type I
type II

Average error rates
0.0
0.4
0.8
1.2

total
type I
type II

Lasso: ρ = 0.8
Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.5
Average error rates
0.0
0.4
0.8
1.2

Average error rates
0.0
0.4
0.8
1.2

Lasso: ρ = 0.2

total
type I
type II

0.00

0.05
0.10
Tuning parameter λ

0.15

Figure 15: Average error rates as functions of λ for K “ 100 and n “ 100.

5.6

Results: finite-sample performance with data-driven penalty
selection

All the following tables show averages and SEs of classification errors in % over 100
replicates for the three proposed methods with both “ _ ” (left) and “ ^ ” (right).

46

Table 5: AR(1) model with K “ 30
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
1.59(1.19); 1.80(1.17)
1.60(1.18); 1.73(1.10)
1.41(1.09); 1.83(1.29)

Type I (%)
1.68(1.26); 1.92(1.25)
1.69(1.25); 1.84(1.18)
1.49(1.17); 1.96(1.38)

Type II (%)
0.43(1.39); 0.13(0.81)
0.43(1.22); 0.13(0.81)
0.30(1.07) 0.07(0.47)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
1.16(1.07); 1.54(1.08)
1.21(1.05); 1.60(1.06)
1.16(1.07); 1.73(1.16)

Type I (%)
Type II (%)
1.25(1.15); 1.65(1.16)
0(0)
1.30(1.12); 1.72(1.13)
0(0)
1.24(1.15); 1.86(1.24)
0(0)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
0.464(1.17); 1.04(1.70)
0.593(1.37); 1.09(1.75)
0.543(1.39); 1.02(1.71)

Type I (%)
0.498(1.26); 1.12(1.83)
0.636(1.47); 1.17(1.88)
0.582(1.49); 1.09(1.83)

Type II (%)
0(0)
0(0)
0(0)

Table 6: AR(1) model with K “ 200
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
0.386(0.250); 0.543(0.143)
0.416(0.237); 0.549(0.148)
0.457(0.210); 0.550(0.174)

Type I (%)
Type II (%)
0.390(0.253); 0.549(0.144)
0(0)
0.420(0.239); 0.555(0.149)
0(0)
0.461(0.212); 0.556(0.176)
0(0)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
0.377(0.104); 0.436(0.119)
0.389(0.119); 0.436(0.129)
0.372(0.107); 0.445(0.124)

Type I (%)
Type II (%)
0.380(0.105); 0.441(0.121)
0(0)
0.393(0.120); 0.440(0.130)
0(0)
0.376(0.108); 0.450(0.126)
0(0)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
0.386(0.250); 0.543(0.143)
0.416(0.237); 0.549(0.148)
0.457(0.210); 0.550(0.174)

Type I (%)
Type II (%)
0.390(0.253); 0.549(0.144)
0(0)
0.420(0.239); 0.555(0.149)
0(0)
0.461(0.212); 0.556(0.176)
0(0)

47

Table 7: AR(4) model with K “ 30
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
20.3(1.21); 20.5(1.15)
20.3(1.14); 20.6(1.29)
20.4(1.27); 20.6(1.24)

Type I (%)
2.72(1.47); 2.89(1.32)
2.51(1.25); 3.10(1.48)
2.93(1.39); 3.03(1.38)

Type II (%)
71.7(4.44); 72.1(4.08)
72.4(4.58); 71.9(4.57)
71.6(4.62); 72.2(4.64)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
10.4(2.03); 10.4(1.78)
10.7(2.09); 10.6(1.87)
10.6(1.94); 10.5(1.85)

Type I (%)
1.21(0.89); 1.24(0.98)
1.41(1.06); 1.36(1.07)
1.31(0.92); 1.38(1.04)

Type II (%)
37.4(9.06) 37.7(8.22)
38.0(9.68); 38.1(8.68)
37.8(8.58); 37.4(8.57)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
5.04(1.02); 5.10(0.98)
5.25(1.04); 5.17(1.00)
5.27(0.95); 5.13(1.04)

Type I (%)
2.02(1.13); 1.94(1.06)
2.03(1.19); 2.05(1.02)
2.10(1.07); 2.23(1.17)

Type II (%)
14.0(3.30); 14.5(3.33)
14.8(3.48); 14.5(3.25)
14.6(3.01); 13.8(3.02)

Table 8: AR(4) model with K “ 200
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
5.13(0.27); 4.81(0.18)
5.07(0.30); 4.80(0.17)
5.16(0.28); 4.84(0.18)

Type I (%)
2.12(0.30); 1.64(0.21)
2.03(0.34); 1.63(0.20)
2.15(0.31); 1.69(0.21)

Type II (%)
78.0(1.27); 81.4(1.36)
78.5(1.41); 81.4(1.36)
77.9(1.17); 81.0(1.29)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
3.01(0.15); 3.09(0.16)
3.03(0.16); 3.09(0.16)
3.02(0.13); 3.09(0.15)

Type I (%)
1.03(0.21); 1.06(0.21)
1.02(0.20); 1.06(0.20)
1.02(0.17); 1.08(0.18)

Type II (%)
50.9(2.31); 52.0(2.09)
51.6(2.10); 52.2(1.97)
51.3(2.13); 51.7(1.74)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
1.99(0.13); 1.98(0.16)
2.03(0.16); 2.02(0.16)
1.98(0.16); 2.00(0.14)

Type I (%)
1.08(0.17); 1.07(0.19)
1.11(0.20); 1.11(0.20)
1.05(0.20); 1.09(0.17)

48

Type II (%)
24.0(1.80); 23.9(1.64)
24.4(1.75); 24.1(1.64)
24.5(1.76); 24.1(1.52)

Table 9: The random precision matrix model with α “ 0.1 and K “ 30
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
6.19(2.24); 6.00(2.02)
6.11(1.99); 6.32(2.06)
6.17(1.91); 6.29(1.92)

Type I (%)
5.01(2.01); 4.78(1.86)
4.80(1.83); 5.04(1.84)
4.87(1.71); 5.08(1.63)

Type II (%)
16.9(8.50); 18.0(8.71)
18.0(8.37); 18.6(8.73)
17.7(9.07); 17.5(8.84)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
1.21(0.87); 1.05(0.77)
1.23(0.91); 1.09(0.89)
1.30(0.94); 1.01(0.73)

Type I (%)
1.33(0.95); 1.19(0.88)
1.37(1.00); 1.23(1.01)
1.44(1.04); 1.13(0.81)

Type II (%)
0.05(0.38); 0.03(0.28)
0.09(0.45); 0.00(0.00)
0.08(0.48); 0.01(0.09)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
1.19(0.92); 0.90(0.74)
1.02(0.94); 0.94(0.82)
1.01(0.92); 0.91(0.72)

Type I (%)
Type II (%)
1.33(1.02); 1.02(0.84)
0(0)
1.15(1.05); 1.06(0.92)
0(0)
1.14(1.04); 1.02(0.81)
0(0)

Table 10: The random precision matrix model with α “ 0.1 and K “ 200
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
11.3(0.36); 10.7(0.29)
11.2(0.31); 10.8(0.28)
11.0(0.29); 10.8(0.28)

Type I (%)
3.57 2.82
3.27(0.34); 2.97(0.33)
3.18(0.32); 2.92(0.29)

Type II (%)
80.8(1.84); 82.3(1.96)
82.3(1.80); 81.9(1.90)
82.1(1.74); 81.9(1.74)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
6.25(0.34); 6.23(0.33)
6.90(0.30); 6.63(0.35)
6.89(0.34); 6.67(0.32)

Type I (%)
3.01(0.34); 3.05(0.31)
3.26(0.36); 3.44(0.36)
3.27(0.39); 3.46(0.35)

Type II (%)
35.5(3.59); 35.0(3.48)
39.7(3.52); 35.3(3.21)
39.5(3.47); 35.3(3.33)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
3.15(0.27); 3.21(0.26)
3.82(0.27); 3.60(0.28)
3.96(0.30); 4.06(0.35)

Type I (%)
2.24(0.27); 2.30(0.26)
2.71(0.30); 2.68(0.30)
2.82(0.35); 3.09(0.38)

49

Type II (%)
11.3(1.95); 11.4(2.05)
13.8(2.14); 11.8(2.03)
13.9(2.03); 12.3(1.71)

Table 11: The random precision matrix model with α “ 0.5 and K “ 30
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
42.0(2.86); 42.0(3.04)
43.7(2.65); 43.3(2.75)
43.6(2.76); 43.4(2.84)

Type I (%)
11.8(3.44); 11.9(3.04)
12.5(3.50); 13.1(3.04)
12.1(3.30); 13.0(3.42)

Type II (%)
72.5(5.76); 72.4(5.37)
75.2(4.90); 73.8(4.77)
75.3(4.77); 74.0(4.79)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
16.7(3.46); 16.7(3.38)
18.7(3.47); 17.8(3.41)
22.8(3.77); 21.5(3.64)

Type I (%)
11.4(3.46); 11.1(3.59)
13.2(3.67); 12.6(3.73)
15.7(3.80); 15.4(3.50)

Type II (%)
22.0(6.49); 22.5(6.01)
24.4(6.18); 23.2(6.07)
29.9(7.03); 27.6(6.60)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
6.27(1.76); 6.42(1.69)
7.89(1.91); 7.41(1.99)
12.3(2.71); 12.0(3.00)

Type I (%)
8.20(2.84); 8.68(2.96)
10.5(3.12); 10.1(3.22)
16.7(4.75); 16.5(5.40)

Type II (%)
4.62(2.32); 4.51(2.48)
5.77(3.00); 5.22(2.48)
8.61(3.38); 8.02(2.90)

Table 12: The random precision matrix model with α “ 0.5 and K “ 200
(a) n “ 100

Ave (SE)
Lasso
Dantzig
MU

Total (%)
49.6(0.41); 49.7(0.42)
49.7(0.43); 49.7(0.41)
49.7(0.42); 49.7(0.41)

Type I (%)
4.53(0.54); 3.43(0.49)
4.19(0.51); 3.53(0.47)
4.17(0.44); 3.48(0.44)

Type II (%)
94.8(0.62); 96.0(0.55)
95.3(0.58); 95.9(0.54)
95.3(0.54); 96.0(0.50)

(b) n “ 500

Ave (SE)
Lasso
Dantzig
MU

Total (%)
47.9(0.45); 47.9(0.46)
48.8(0.45); 48.4(0.42)
48.8(0.44); 48.4(0.43)

Type I (%)
8.96(0.76); 9.10(0.77)
8.63(0.78); 9.41(0.76)
8.57(0.71); 9.31(0.79)

Type II (%)
86.9(0.95); 86.7(0.99)
88.9(0.93); 87.4(0.95)
89.0(0.82); 87.5(0.86)

(c) n “ 1000

Ave (SE)
Lasso
Dantzig
MU

Total (%)
44.6(0.49); 44.6(0.48)
46.8(0.48); 46.0(0.48)
47.4(0.46); 46.5(0.47)

Type I (%)
12.4(1.11); 12.6(1.06)
13.0(1.15); 13.7(1.18)
12.6(1.05); 13.1(0.98)

50

Type II (%)
76.8(1.65); 76.7(1.60)
80.6(1.48); 78.3(1.57)
82.1(1.11); 80.0(1.17)

