On the efficiency of the de-biased Lasso
Sara van de Geer


On the asymptotic variance of the debiased Lasso

.1in
Sara van de Geer

Seminar for Statistics, ETH Zürich

.1in
August 21, 2018 

MSC 2010 subject classifications: Primary 62J07; secondary 62E20.

Keywords and phrases: asymptotic efficiency, asymptotic variance, Cramér Rao lower bound, 
debiasing, Lasso, sparsity. 

Abstract. We consider the high-dimensional linear regression model
Y = X β^0 + ϵ
with Gaussian noise ϵ and Gaussian random design X.
We assume that Σ:=  X^T X / n is non-singular and write its inverse
as Θ := Σ^-1. The parameter of interest is
the first component β_1^0 of β^0. 
We show that in the high-dimensional case the asymptotic variance of a debiased Lasso
estimator can be smaller than Θ_1,1.  For some special such cases we establish
asymptotic efficiency. The conditions include
β^0 being  sparse 
and the first column Θ_1 of Θ being not sparse.
These conditions depend on whether Σ is known or not.





§ INTRODUCTION
 

Let Y be an n-vector of observations and X ∈^n × p an input matrix.
The linear model is

    Y = X β^0 + ϵ ,

where β^0 ∈^p is a vector of unknown coefficients and ϵ∈^n
is unobservable noise.  
We examine the high-dimensional case with
p ≫ n. The parameter of interest in this paper is a component of β^0, say the first 
component β_1^0. We consider the asymptotic properties of debiased
estimators of the one-dimensional
parameter β_1^0 under scenarios
where certain sparsity assumptions fail to hold. 

The paper shows that the asymptotic variance of the debiased estimator
can be smaller than the “usual" value for the low-dimensional case. For simplicity we examine Gaussian
data: the rows of (X,Y) ∈^n× (p+1) are i.i.d. copies
of a zero-mean Gaussian row vector ( x,  y ) ∈^p+1, where x= ( x_1 , … ,
 x_p) has covariance matrix Σ :=  x^T  x. We assume the inverse
of Σ exists and write it as
Θ:= Σ^-1. The vector β^0 of regression coefficients is 
β^0 = Θ x^T  y.
We denote the first column of Θ by  Θ_1 ∈^p and the first
element of this vector by Θ_1,1. Our main aim is to present
examples where lack of sparsity in Θ_1 can result in a small asymptotic
variance of a suitably debiased estimator. In particular, the asymptotic
variance can be smaller than Θ_1,1. For the case Σ known, this means applying for instance
a (noiseless) node-wise Lasso, instead of an exact orthogonalization of the first variable with respect to the others,
may reduce the asymptotic variance (as follows from combining Theorem <ref> with Lemma <ref>).
If Σ is unknown, the high dimensionality of the problem
already excludes exact empirical projections for orthogonalization. The (noisy) Lasso is designed 
to deal with approximate orthogonalization in the high-dimensional case.
Using the node-wise Lasso, we find that
one may again profit from non-sparsity of the (now unknown) vector Θ_1
(see Theorem <ref>). 


We look at specific examples or constructions of
covariance matrices Σ. 
The results illustrate that 
  asymptotic efficiency claims require some caution.
  The high-dimensional situation exhibits new phenomena
that do not occur in low dimensions. 

Throughout, the minimal
eigenvalue of Σ, denoted by Λ_ min^2, is required to
stay away from zero, i.e. 1/Λ_ min^2 = 𝒪 (1).
We further consider only Σ's with all 1's on the diagonal and
assume for simplicity that σ_ϵ^2 := 
(  y -  xβ^0 )^2 is known and that its value is σ_ϵ^2=1. 
   
Let a given subset
B of ^p be
the model class for β^0. An interesting research goal is to construct for the model B a regular 
estimator of β_1^0 with asymptotic variance that achieves the asymptotic Cramér Rao lower bound
(given here in Proposition <ref>). One then needs to decide which model class B 
one considers as relevant.
In high-dimensional
statistics it is commonly assumed that β^0 is sparse in some sense. 
Let 0< r ≤ 1, define  for a vector b ∈^p its ℓ_r-“norm"
b _r by b _r^r := ∑_j=1^p | b_j |^r and let b _0^0 be its number
of non-zero entries.
A sparse model  is for example

    B := { b ∈^p :   b _0^0 ≤ s }

 for some (“small") s ∈.
 Alternatively one may believe only in ℓ_1-sparsity. Then
 
    B = { b ∈^p :   b _1 ≤√(s)}

 for some s >0.
These are the two extremes of weakly sparse models of the form

    B = { b ∈^p :  b _r^r ≤ s^2-r  2} ,

 for some s>0 and 0≤ r ≤1. Throughout, the value of s is allowed to depend on n, but
 r is fixed for all n. 
  
 Constructing estimators that achieve the asymptotic Cramér Rao lower bound for model (<ref>), (<ref>), (<ref>) or some other sparse model
 is to our understanding
 quite ambitious, especially if one wants to do this for all possible covariance matrices Σ.
 See e.g. Example <ref> for some details concerning model (<ref>).
 However, for special cases of Σ's the problem can be solved.
  One such special case is where the first row of Θ_1 of Θ is sparse in an appropriate sense. 
 This is the situation considered in previous work such as  <cit.> and <cit.>
 where Σ is unknown. In this paper we consider known
 and unknown Σ and in both cases do not require sparsity of Θ_1. 
 The paper <cit.> also does not require sparsity of Θ_1
 when Σ is known and 
it turns out that for certain non-sparse vectors Θ_1 their estimator
is not asymptotically efficient (see Theorem <ref> or Remark <ref>
following this theorem).







 The debiased Lasso defined in this paper in equation (<ref>) below is based on
  a direction Θ̃_1 ∈^p where typically Θ̃_1 is thought of as some estimate of Θ_1. 
 As we do not
 assume sparsity of Θ_1 a reliable estimator of Θ_1 may not be available.
 Nevertheless, we show that this does not rule out good theoretical performance. 
 We present a class of covariance matrices Σ for which a debiased
 Lasso has asymptotic variance smaller than Θ_1,1. 
 This phenomenon is tied to the high-dimensional situation, see Remark <ref>.
 For special cases,
we establish that
 an asymptotic Cramér Rao bound smaller than Θ_1,1 can  be achieved.
 In other words,  there exist cases where a
 debiased Lasso profits from sparsity of β^0 combined with non-sparsity of
Θ_1. This is good news: the asymptotic variance can be small for two reasons:
either Θ_1 is sparse in which case the asymptotic variance Θ_1,1 is typically small
(as it is the inverse of the residuals of regressing the first variable  on
only a few of the other variables), or Θ_1 is not sparse
 but then the asymptotic variance can be smaller than Θ_1,1. This paper presents
 cases where the latter situation indeed occurs.  
   
 

 §.§ The Lasso, debiased Lasso and sparsity assumptions


The Lasso (<cit.>) is
defined as 

    β̂:= min_b ∈^p{ Y - X b _2^2/n + 2 λ b _1 }

with λ>0 a tuning parameter. (We will throughout take of order √(log p / n ) but not too
small.)



A debiased Lasso is
given by

    b̂_1 = β̂_1 + Θ̃_1^T X^T (Y- X β̂)/n .

The p-dimensional vector Θ̃_1 is typically some estimate of the first column 
Θ_1 of 
the precision matrix Θ, but in our case it will rather be estimating a sparse approximation. 
We refer to Θ̃_1 as a direction. The estimator β̂ is commonly taken to be the Lasso given
in (<ref>) although this is not a must. 



 
 The debiased Lasso (<ref>) was introduced in
<cit.> and further developed in <cit.> and 
<cit.> for example.  Related work is <cit.>  and <cit.>.

The theory for the Lasso (<ref>) and debiased Lasso (<ref>) 
requires some form of sparsity of β^0.
Consider for some s ∈ one of the sparsity models (<ref>),
(<ref>) or, more generally, model (<ref>). 
 Two prevalent sparsity assumptions are:

(i) s = o ( n / log p ),

(ii) s = o ( √(n) / log p ).

 
 
 Sparsity variant (i) is for example invoked to establish ℓ_2-consistency of the Lasso β̂
(see <cit.> or the monographs <cit.>, <cit.> and <cit.>,
and their references). 

Which sparsity variant
is needed to establish asymptotic normality of the debiased Lasso  (<ref>) depends to a large extent
on whether Σ is known or not. In <cit.>, <cit.>, <cit.>. 
<cit.> one can find
refined results on this issue. 


This case  Σ known is treated in Section <ref>. We introduce and apply there the concept of an eligible pair, see Definition <ref>. An eligible pair is a sparse approximation
of Θ_1 together with a parameter describing the order of approximation and sparsity. 
We allow for sparsity variant (i) in model (<ref>) as in <cit.>, see Example
<ref>. Sparsity variant (i) will also be allowed for the models
(<ref>) and (<ref>), see Examples <ref> and
<ref>.



 
 
 
 
 Eligible pairs will also play a crucial role in Section <ref>
 where Σ is unknown.  Let us discuss some of the literature for this case
 and for the sparsity model
(<ref>).
 From the papers
<cit.> and <cit.>  we know that for the minimax bias of an
estimator of β_1^0 to be of order 1/ √(n), the assumption s=  O( √(n / log p) ) is necessary.
 Thus, up to log-terms  this needs 
 the second sparsity  variant.
 When considering asymptotic Cramér Rao lower bounds,
 one also needs to restrict oneself to a certain class of estimators,
 for instance estimators with bias of small order 1/√(n) or asymptotically linear 
 estimators. In <cit.> such restrictions are studied.
  One can show asymptotic linearity of the debiased Lasso under model (<ref>) with sparsity variant
  (ii)  and in addition Θ_1 _0 = o (√(n) / log p ). 
   If Θ_1 is not sparse
  nor can be approximated by a sparse vector, then 
 it is unclear whether an asymptotically linear estimator exists. 
 We refer to Remark <ref> for more details.
 In summary, modulo log-terms, sparsity variant (ii) cannot be relaxed as far as minimax rates
 for the bias are concerned, and sparsity variant (ii) with in addition sparsity
 of order o (√(n) / log p )  for Θ_1 or its sparse approximation 
appears to be needed
for establishing asymptotic linearity.
We note that  the paper <cit.>
  establishes asymptotic normality under (among others) the assumption
  
    min ( s, Θ_1 _0^0) = o( √(n) / log p ).

 Bias and asymptotic linearity
 are not considered (these issues are not within the scope of that paper).
 In our setup however, Θ_1 is not sparse at all, so
 variant (ii) is in line with (<ref>). 
 










Tables <ref> and <ref> presented in Subsection <ref>
summarizes the sparsity conditions applied in this paper. One sees that models
(<ref>) and (<ref>) are special cases of model
(<ref>), with r=0 and r=1 respectively. However, when r=0 the
asymptotic efficiency depends on β^0 and also quite severely on the value of s.
For the case Σ unknown, model (<ref>) is too large. 






 §.§ The asymptotic Cramér Rao lower bound

We briefly review the Cramér Rao lower bound and refer to <cit.> for details.
Let the model be β^0 ∈ B, where B is a given class of
regression coefficients. Let  H_β^0 := { h ∈^p:  β^0 + h/√(n)∈ B}.
We call H_β^0 the set of model directions. 


An estimator T (or actually: sequence of estimators) is called regular at β^0 if for all fixed ρ>0
and R >0 and all sequences h  ∈ H_β^0 with | h_1 | ≥ρ and
h^T Σ h ≤ R^2,
it holds that

    √(n) ( T- (β_1^0+ h_1/√(n))    V_β^0 ) D_β^0 + h/√(n)⟶ N (0,1)

where V_β^0^2 = 𝒪 (1) is some constant (depending on n and possibly on β^0, but not depending
on ρ, R or h), called the asymptotic variance
(it is defined up to smaller order terms). Regularity is important in practice. It means that the
asymptotics is not just pointwise but remains valid in neighbourhoods.

 Typically, the class B is not a cone. This is the reason why
we do not restrict ourselves to model directions h ∈ H_β^0 with h_1=1 (say).


 One may also opt for defining the set of possible directions 
H_β^0 differently,
say  H_β^0 :=  B.
Then regularity concerns parameter values that fall outside the parameter space. 
For example under model (<ref>) one then has to
deal with sparsity 2s instead of s. With our choice of H_β^0 we stay inside the parameter space
but the set of possible directions then depends on β^0. In model (<ref>) or
(<ref>) one can move away from this dependence when β^0 is
a proper “interior point" of B (see Examples <ref> and
<ref>). 



Suppose T is asymptotically linear at β^0 with influence function
i_β^0: ^p+1→:

    T- β_1^0 = 1  n∑_i=1^n  i_β^0 (X_i , Y_i) + o__β^0  (1/ √(n) )

where _β^0 i_β^0( x ,  y ) = 0 and
V_β^0^2 := _β^0  i_β^0^2 ( x ,  y )= 𝒪 (1).
Assume the Lindeberg condition

    lim_n →∞_β^0 i_β^0^2 ( x ,  y )  l{ i_β^0^2 ( x ,  y )> ηn V_β^0^2} =0   ∀ η >0 .

Assume further that T is regular at β^0. Then for all fixed ρ>0 and R>0

    V_β^0^2 + o(1) ≥max_h ∈ H_β^0:  |h_1| ≥ρ, 
    h^T Σ h ≤ R^2 h_1^2 
    h^T Σ h  .



This proposition is as Theorem 9 in  <cit.> but tailored for the particular situation.
A proof is given in Section <ref>.
We remark that such results are not a direct consequence of the Le Cam theory, as
we are dealing with triangular arrays. 

 Assume the conditions of Proposition <ref> and
that for some fixed ρ>0 and R >0 and some sequence h ∈ H_β^0, with
|h_1| ≥ρ and h^T Σ h ≤ R^2,  it is true that

    V_β^0^2 =  h_1^2  h^T Σ h  + o(1) .

Then T is asymptotically efficient. This is our main tool to arrive at asymptotic efficiency
for some special Σ's. 


The restriction to directions in H_β^0 means that the Cramér Rao lower bound for
the asymptotic variance V_β^0^2 can be orders of magnitude smaller than Θ_1,1.


  Under the sparse model (<ref>)[A more natural model in this context might be B := { b ∈^p :   b_-1_0^0 ≤ s-1 } where,
for b ∈^p, b_-1 := ( b_2 , … , b_p)^T.]
 we have

    H_β^0⊆ H_β^0 ,

where

    H_β^0  := { h _0^0 ≤ s- s_0 }

and s_0 = |S_0| with 
S_0 := {β_j^0 ≠ 0 } being the set of active coefficients of β^0.


Some special cases

a) If Θ_1  ∈ H_β^0, then V_β^0^2 + o(1)= Θ_1,1.
Note that the condition on Θ_1 depends on β^0 (via s_0).

b)  Suppose { 1 }∈ S_0, s=s_0 and that the following “betamin" condition
holds: | β_j^0 | > m_n/√(n) for all j ∈ S_0, where m_n is some sequence
satisfying 
m_n →∞. Then we see that 

    H_β^0∩{ h^T Σ h ≤ R^2  } ={ h_-S_0 _0 = 0 }∩{ h^T Σ h ≤ R^2  }.

The lower bound is then

    V_β^0^2+ o(1) ≥ ( Σ_S_0  , S_0 ^-1)_1,1 ,

where Σ_S_0 , S_0 is the matrix of covariances of the variables in S_0.
This lower bound corresponds to the case S_0 is known.
The bound could be achieved if one has a consistent estimate Ŝ of S_0.
For this one needs betamin conditions in order to have no false negatives.
Estimation of β_1^0 using some estimator Ŝ of S_0 typically means that the estimator 
of β_1^0 is not regular.
Imposing further conditions beyond model (<ref>)
to make it regular
may diminish the lower bound.

c) More generally, if  { 1 }∈ S_0 and | β_j^0 | > m_n /√(n) for all j ∈ S_0 and some
sequence m_n →∞ then the lower bound corresponds to knowing
the set S_0 up to s-s_0 additional variables. 

d) Suppose that β^0 is an interior point in the sense that it stays away from the boundary:
for some fixed 0 < η< 1 it holds that s_0 ≤ (1- η) s
(so that 1- s_0 / s stays away from zero). Then 

    { h :   h _0^0 ≤η s }⊂ H_β^0   .

The lower bound can then still depend on η.
A rescaling argument as applied in the next examples, Example <ref> and
more generally Example <ref>,
 does not work here.
This signifies that
model (<ref>) less suitable in our context: the exact value of s plays a too
prominent role. 



Consider model (<ref>). The situation is then more like a classical one.
Suppose β^0 stays away from the boundary of the parameter space, i.e., for a fixed 0<η < 1
it holds that
β^0 _1 ≤ (1-η )√(s). Then

    { h _1 ≤η√(ns)}⊂ H_β^0   .

By a rescaling argument the dependence on η in the left hand side plays no role in the lower bound:
for all M>0 fixed

    V_β^0^2 +o(1) ≥ ( min_c ∈^p-1:   c _1 ≤ M√(ns) (  x_1 -  x_-1 c )^2  )^-1 ,

where x_1 is the first entry of x and x_-1 := ( x_2 , … ,  x_p ). 
In other words, unlike in model (<ref>), the exact value of s does not play a prominent role.
We thus see that in order to be able to improve over Θ_1,1 we must have that
Θ_1 is rather non-sparse: Θ_1 _1 should be of larger order
than √(ns). 
For example if
s = o(n /log p), say s= n/(m_n log p ) for some sequence m_n →∞ slowly,
the model directions have ℓ_1-norm of order n / √(m_n log p).
To improve over Θ_1,1 one thus must have Θ_1_1 of larger
order, say Θ_1_1= n / √(log p ). We get back to this
in Example <ref>. 

 

 
We now turn to model (<ref>). Using the same arguments as
in Example <ref> one sees that if β^0 stays away from the boundary,
one may use model directions  with ·_r^r of order √(n^r s^2-r).
The lower bound is then

    V_β^0^2 +o(1) ≥ ( min_c ∈^p-1:   c _r^r ≤ M√(n^r s^2-r) (  x_1 -  x_-1 c )^2  )^-1

where M >0 is any fixed constant. 



It is clear, and illustrated by Examples <ref> , <ref> and
<ref>, that the
lower bound of Proposition <ref> depends on the model B. 
The sparse model (<ref>) is perhaps too
stringent. One may want to take the model B as the largest set for which a regular estimators exist.
This points in the direction  of  model (<ref>). We 
will see that when Σ is known this model is indeed useful but when Σ is unknown it is
too large. 









 §.§ Notations and definitions



We consider an asymptotic framework with triangular arrays of observations.
Thus, unless explicitly stated otherwise, all quantities depend on n although we do not (always) express this in our notation.


Let x_1 be the first entry of x and x_-1:= ( x_2 , …,  x_p) be this vector with the first entry excluded,
so that x = (  x_1 ,  x_-1 ). Write Σ_-1,-1:=  x_-1^T  x_-1∈^(p-1)× (p-1). 
For vectors b ∈^p be use a similar
notation: b_1∈ is the first coefficient and b_-1∈^p-1 forms the rest of
the coefficients.
Apart from the regression (projection) xβ^0 of y on x, we consider the
  regression x_-1γ^0 of x_1 on x_-1, and an approximation
  γ^♯ of γ^0 which is accompanied by a parameter λ^♯
  to form an “eligible pair" (γ^♯, λ^♯) as given in Definition <ref>.
  When Σ is known we can invoke the noiseless Lasso γ_ Lasso with tuning parameter
  λ_ Lasso 
  (an approximate projection of x_1 on
  x_-1) to approximate γ^0. See (<ref>) for its definition.
    For the case Σ is unknown we apply the notation Σ̂:= X^T X / n. We let
  X_1∈^n be the first column of X, and
the matrix X_-1∈^n × (p-1) be the remaining columns and we write Σ̂_-1,-1:=
X_-1^T X_-1 / n. 
We
do a approximate regression of X_1 on X_-1
 invoking the noisy Lasso γ̂ with tuning parameter
  λ^ Lasso as given in (<ref>). The various vectors of coefficients
  and their “lambda parameter" are summarized in Table <ref>.
  Here we also add  the Lasso β̂  for the estimation of β^0, as
  defined in (<ref>) with
  tuning parameter λ. 
      
  





We write for S ∈{1 , … , p }, x_S :={ x_j}_j ∈ S and
x_-S :={ x_j}_j ∉ S,  j ≠ 1. 



We further let for S ⊂{ 1 , … , p}
with cardinality s, the matrix Σ_S,S:=  x_S^T  x_S ∈^ s× s be the 
covariance sub-matrix formed
by the variables in S and
Σ_-S,-S:=  x_-S^T  x_-S∈^(p-1- s) ×( p-1- s) and 
Σ_S,-S :=  x_S^T x_-S  =: Σ_-S, S^T ∈^ s× (p-1- s).


Note that the vector of coefficients γ^0 of the
regression of x_1 on x_-1 is a vector in ^p-1.
We will index its entries by { 2 , … , p }: γ^0 = (γ_2^0 , … , γ_p^0 )^T.
Also the various other “gamma" parameters" γ will be indexed by { 2, … , p }.
It should be clear from the context when this indexing applies. 
For c=(c_2, … , c_p)
and S ⊂{ 2 , … , p } we write
c_S := {γ_j :  j ∈ S } and γ_-S := { c_j : j ∉ S,   j ≠ 1  }.
We use the same notation for the (p-1)-dimensional vector c_S which has
the entries not in S set to zero, and we then let c_-S= c- c_S. 




For a positive semi-definite matrix A we let
Λ_ min^2 (A) be its smallest eigenvalue and
Λ_ max^2 (A) be its largest eigenvalue. 
The smallest eigenvalue of Σ is written shorthand as Λ_ min^2:= Λ_ min^2 (Σ).
Recall we assume throughout that 
Λ_ min^2 stays away from zero: 1/ Λ_ min^2 = 𝒪 (1).
We use the shorthand notation ≫ 0 for “strictly positive and staying away from zero". Thus
throughout we assume Λ_ min^2 ≫ 0. 

In order to be able to construct confidence intervals one needs some uniformity in 
unknown parameters. We introduce the following definition. 

 Let B be the model for β^0. 
Let { Z_n } be a sequence of real-valued random variables depending on (X,Y)
and { r_n } a sequence of positive numbers.
We say that { Z_n } is 𝒪__β^0 ( r_n) uniformly in β^0 ∈ B if

    lim_M →∞lim sup_n →∞sup_β^0 ∈ B_β^0 ( |  Z_n|  > M r_n  ) = 0 .

We say that Z_n= o__β^0(r_n) uniformly in β^0 ∈ B if 
  
    lim_n →∞sup_β_0 ∈ B_β^0 (| Z_n| > η r_n  ) = 0 ,  ∀ η  >0 .

  
  
  
 




 §.§ Organization of the rest of the paper










Section <ref> contains the results for the case Σ
known and applying a debiased Lasso using
sample splitting. Here we also introduce the concept of an
eligible pair (γ^♯ , λ^♯) in Definition <ref>. 
Section <ref> contains results and constructions for eligible pairs.
Section <ref> considers the case Σ unknown and a debiased Lasso
(without sample splitting). Section <ref> concludes and Section <ref>
collects the proofs. Section <ref> (included for completeness)
contains some elementary probability inequalities for products of
Gaussians, which are applied in Section <ref>.

In Tables <ref> and <ref> we summarize the (sparsity) conditions  we use, see Examples
<ref>, <ref> and <ref> for the case Σ known and
 Examples
<ref> and <ref> for the case Σ unknown. The
particular cases r=0 and r=1 follow from the general case 0 ≤ r ≤ 1 when Σ is known.
When Σ is unknown the case r=0 also follows from the general case 0≤ r < 1. With r=1 the model
is then too large. We have displayed the extreme cases separately so that the conditions
for these can be read off directly . In particular for r=0 one sees
the standard sparsity conditions known from the literature. For r=1 (Σ known) one sees that
unlike in the other cases there is no logarithmic gap between conditions for asymptotic normality and
asymptotic efficiency. 

 





§ THE CASE Σ KNOWN


Before presenting “eligible pairs" in Definition <ref>, we provide the motivation that
led us to this concept.

Recall the  debiased Lasso given in (<ref>).
If Σ is known we choose the direction Θ̃_1=: Θ_1^♯ non-random,
 depending on Σ. 
We invoke the decomposition

    b̂_1 - β_1^0 =Θ_1^♯ T X^T ϵ / n +  ( e_1 -
     Σ̂Θ^♯ )^T ( β̂- β^0 )_ remainder .

The remainder  is

    ( e_1- Σ̂Θ^♯)^T ( β̂- β^0 )=
     Θ_1^♯ T ( Σ - Σ̂)(β̂- β^0 )_:=(i) + 
    (  e_1  -  ΣΘ^♯)^T (β̂- β^0 )_:=(ii) .

 
 The first term (i) can be handled assuming Θ_1^♯ TΣΘ_1^♯ = 𝒪 (1) and
 Σ^1/2 (β̂- β^0)_2 = o_ (1). This goes along the lines of
 techniques as in <cit.>, applying the conditions
 used there. One then arrives at (i)= o_ (1/√(n) ).
 (We will however alternatively use a sample splitting technique later on in 
 Theorem <ref> to simplify the derivations.)
  
 The second term (ii) is additional bias and will be our major concern. If Θ_1^♯= Θ_1 this
 term vanishes. However, as we will see it is useful to apply  instead of Θ_1
 some sparse approximation of Θ_1. In fact, we
 aim at a sparse approximation Θ_1^♯ with  Θ_1,1^♯ being smaller than Θ_1,1 and their
 difference not vanishing.  
 
 We will assume conditions
 that ensure the additional bias is negligible and
invoke that
 
    |(  e_1  -  ΣΘ_1^♯)^T (β̂- β^0 ) | ≤Σ ( Θ_1^♯ - Θ_1) _∞β̂- β^0 _1

   (recall that by the definition of Θ_1 it is true that e_1 = ΣΘ_1). 
   
   
 One may think of applying instead  the Cauchy-Schwarz inequality
 
    |(  e_1  -  ΣΘ_1^♯)^T (β̂- β^0 ) |≤Σ^1/2 ( Θ_1^♯- Θ_1) _2Σ^1/2 (β̂- β^0) _2  .

 This
 leads to requiring that  Σ^1/2 ( Θ_1^♯- Θ_1) _2→ 0 fast enough. But we actually want
 Σ^1/2 ( Θ_1^♯- Θ_1) _2↛0 in order to be able to arrive
 at an improvement over the asymptotic variance. 
 
 
 
 Consider now for some p≥ 1 the general
 dual norm inequality
 
    |(  e_1  -  ΣΘ^♯)^T (β̂- β^0 ) |≤Σ ( Θ_1^♯ - Θ_1) _ pβ̂- β^0 _ q

where 1/  p + 1/  q =1. Choosing p≤ 2 here again works against our aim
to improve the asymptotic variance. Thus we need to choose p>2 (and therefore
q < 2). This certifies the choice p=∞ as being quite natural.
 
 
 
    We note that
 Σ^1/2 ( Θ_1^♯ - Θ_1) _2 ≤Σ (Θ_1^♯ - Θ_1) _2 / 
 Λ_ min. This means we want Σ (Θ_1^♯ - Θ_1) _2 ↛0 as we
 assume that Λ_ min stays away from zero. Now it is clear that if for some vector
 v ∈^p, it holds that v _∞≤λ_0^♯, then
 v _2 ≤√(p)λ_0^♯. So v _2 ↛0 implies
 pλ^♯ 2↛0. In other words, we can only improve the asymptotic variance
 in the high-dimensional case. 
 

Taking the dual norm inequality (<ref>) as starting point we now need
   
    Σ (Θ_1^♯  - Θ_1)_∞≤λ_0^♯

 for some constant λ_0^♯ small enough, such that uniformly in β^0 ∈ B
 
    λ_0^♯β̂- β^0 _1 = o__β^0 (1/√(n)  ) .

  

 
With the above considerations as motivation, we
 now concentrate on 
 an ℓ_∞-condition as given in  inequality (<ref>). 
 We fix some λ^♯ and construct vectors Θ_1^♯
 for which inequality (<ref>) holds. 
 It is based on replacing the vector of coefficients γ^0 of the regression
 of x_1 on x_-1 by a sparse approximation γ^♯.
 
 
 Let γ^♯∈^p-1 and λ^♯ >0.
 We say that the pair (γ^♯ , λ^♯ ) is eligible if 
 
    Σ_-1,-1 (γ^♯- γ^0) _∞≤λ^♯

 and
 
    λ^♯γ^♯_1 → 0 .

   
 
 The two conditions in Definition <ref> will allow us to arrive at
 (<ref>) as is shown in the next lemma.
  
   
 Suppose (γ^♯, λ^♯) is an eligible pair.
    Then
  
    1- γ^0TΣ_-1,-1γ^♯≥Λ_ min^2 -o(1)

  i.e., 1- γ^0TΣ_-1,-1γ^♯≫ 0 eventually. 
  Let (for n sufficiently large)
  
    Θ_1^♯ := [ 1  - γ^♯ ]/ (1- γ^0TΣ_-1, -1γ^♯ ).
 
 Then we have
 
    Σ( Θ_1^♯ - Θ_1)  _∞≤λ_0^♯

 where 
 
    λ_0^♯:= λ^♯ /  (1- γ^0TΣ_-1, -1γ^♯) =
     𝒪 (λ^♯ ).

 Moreover,
  
    Θ_1^♯ T ΣΘ_1^♯   =   Θ_1,1^♯ +o(1)
       ≤   Θ_1,1 + o(1).

Finally, in order to have a non-vanishing  improvement  of
Θ_1,1^♯ over Θ_1,1 it must be true that
 γ^0 is not sparse, in the sense that
 
    λ^♯γ^0 _1≫ 0 .

   
  
  
  The first condition (<ref>) of Definition 
  <ref> can be rewritten as
 
    x_-1γ^0 =  x_-1γ^♯ + ξ^0,  |  x_j ξ^0 | ≤λ^♯ ∀ j ∈{2 , … , p } .

 The second condition (<ref>) in this definition can be thought of as a sparsity condition on γ^♯. 
 The two conditions together require that the regression of
x_1 on x_-1 is sparse when one relaxes the orthogonality condition
of residuals to approximate orthogonality.[Condition (<ref>) is of the same nature
as the condition λβ^0 _1 = o(1) (which follows from
the classical condition λ^2 β^0 _0^0 =o(1) if
β^0 _2 = 𝒪 (1)) when applying the Lasso (<ref>)
with tuning parameter λ.]  One may think of γ^0 as a “least squares estimate"
of γ^♯ in a noisy regression model. We refer to Subsection <ref>
which gives a very natural interpretation of eligible pairs. 
 Further, for Θ_1^♯ defined in (<ref>)
 one has the equivalence
 
    Θ_1,1 - Θ_1,1^♯≫ 0  ⇔  ( ξ^0)^2 ≫ 0 .

  


  
  To have Θ_1,1^♯ improving over Θ_1,1 we see from the above lemma that we aim at a situation where γ^0, and hence Θ_1,  is not sparse,
  but where γ^0 can be replaced by a sparse vector γ^♯. 





  For some special Σ's, we give examples of eligible pairs in Section <ref>.
  That section also discusses for a given λ^♯ uniqueness of the vectors γ^♯
  for which the pair (γ^♯, λ^♯) is eligible. Moreover, we show cases where
  x_-1γ^♯ is an approximation of the projection of x_1 on a subset of
  x_S of the other variables for some S ⊂{ 2 , … , p }, see Lemma <ref>.
  This may help to understand why the Cramér Rao lower bound can be achieved in those
  cases. 
      
  Lemma <ref> essentially has all the ingredients to prove asymptotic normality
  of the debiased Lasso (<ref>) with direction Θ̃_1= Θ_1^♯ and
  Θ_1^♯ given in (<ref>) in this lemma. 


It can be done along the lines of Theorem 3.8 in <cit.>, assuming the conditions
stated there. However, as the authors point out, 
when using instead the sample splitting approach their Assumption (iii) is not needed. 
Sampling splitting it is also mathematically less involved. We present it here.

Assume the sample size n is even.
Define the matrices

    (X_I, Y_I)    :=    {X_i,1, … , X_i,p, Y_i  }_1 ≤ i ≤ n/2∈^n/2 × (p+1), 
    
     (X_II, Y_I)    :=   {X_i,1, … , X_i,p, Y_i  }_n/2 < i ≤ n∈^n/2 × (p+1).

Let β̂_I be an estimator of β^0 based on the
first half (X_I, Y_I) of the sample, for instance the Lasso estimator
min{ Y_I - X_I b_2^2 /n+  λ b _1 }. 
Similarly, let β̂_II be an estimator of β^0 based on the second half (X_II, Y_II) of the sample.

Let (γ^♯, λ^♯) be an eligible pair.
We then define the two debiased estimators

    b̂_I,1^♯   :=   β̂_II,1 + 2Θ_1^♯ T X_I^T (Y_I - X_I β̂_II )/n
    b̂_II,1^♯   :=   β̂_I,1 + 2Θ_1^♯ T X_II^T (Y_II - X_IIβ̂_I  )/n

where Θ_1^♯ is given in (<ref>) in Lemma <ref>.
The final estimator b̂_1^♯ is obtained  by averaging these two:

    b̂_1^♯ := b̂_I,1^♯+b̂_II,1^♯ 2 .


Let now B be a given model class for the unknown vector of regression
coefficients β^0. 



 
Let (γ^♯, λ^♯) be an eligible pair,
Θ_1^♯ be given in (<ref>) and 
b̂_1^♯ be given in 
(<ref>) with b̂_I,1^♯ and b̂_II,1^♯ the debiased estimators
based on Θ_1^♯ using the splitted sample.
Suppose that uniformly in β^0 ∈ B

    Σ^1/2 (β̂_I - β^0) _2 = o__β^0 (1) , Σ^1/2 (β̂_II - β^0 )_2 = o__β^0 (1)

and

    √(n)λ^♯β̂_I - β^0 _1 = o__β^0 (1) , √(n)λ^♯β̂_II - β^0 _1 = o__β^0 (1) .

Then, uniformly in β^0 ∈ B,

    b̂_1^♯ - β_1^0 = Θ_1^♯ T  X^T ϵ /n + o__β^0 (1/ √(n) ) ,

and 

    lim_n →∞sup_β_0 ∈ B_β^0 (
    √(n) ( b̂_1^♯ - β_1^0 ) Θ_1,1^♯≤ z  )= Φ(z) ,  ∀ z ∈.

 

  
Theorem <ref> shows that under its conditions
the estimator b̂_1^♯
is uniformly asymptotically linear and regular.
It means that for this estimator the Cramér Rao lower bound as
given in Subsection <ref> is relevant.
Depending among other things on B and Σ it does or does not reach the Cramér Rao lower bound,
see Remark <ref>.




  Lemmas <ref>, <ref> and
<ref> in Subsection <ref> present examples of eligible pairs
(γ^♯, λ^♯) where Θ_1,1 - Θ_1,1^♯ 
(with Θ_1,1^♯ given in (<ref>)) is
non-vanishing:  Θ_1,1 - Θ_1,1^♯≫ 0.Thus for those cases
Theorem <ref> shows an asymptotic variance remaining strictly
smaller than Θ_1,1. Moreover, the constructions 
of Lemmas <ref>, <ref> and
<ref> allow for directions Θ_1^♯ 
(depending on β^0 _0^0∈ H_β^0
in model (<ref>). In models
(<ref>) and (<ref>) the direction
Θ_1^♯ lies in H_β^0 after scaling where only
the scaling depends on β^0.
For these cases (special constructions of Σ) the Cramér Rao lower bound is therefore achieved.
 

We now discuss the requirements (<ref>) and
(<ref>) for the models (<ref>),
(<ref>) and (<ref>). The overall picture
is summarized in Table <ref>. 


Consider model 
model (<ref>) with s= o( n / log p ) (sparsity variant (i)).
For the 
Lasso estimator 
β̂ given in (<ref>),
with appropriate choice of the tuning parameter λ≍√(log p / n ), one has
uniformly in β^0 ∈ B

    Σ^1/2 (β̂- β^0 )_2^2 = 𝒪__β^0 ( s log p / n  ) , β̂- β^0 _1 = O__β^0 ( s √(log p / n)  ).

This follows from e.g. Theorem 6.1 in <cit.>,  together with results for Gaussian
quadratic forms as given in (<ref>). 
So for β̂_I and β̂_II Lasso's based on the splitted sample
with suitable tuning parameter λ, the requirement on λ^♯ becomes

    λ^♯ s √(log p)= o( 1).

This is guaranteed  when λ^♯= 𝒪 ( √(log p) /n ).
The smaller the sparsity s, the more room there is for improvement (i.e., the larger
the collection
of covariance matrices Σ that allow for improvement over Θ_1,1).
For example, if in fact
s= o( √(n ) / log p )
we can take
λ^♯= 𝒪 ( √(log p /n) ).
Finally, if γ^♯_0^0 = s_♯ with s_♯≤ s- s_0 -1 the estimator
b̂_1^♯ is asymptotically efficient. 


  
In view of Theorem <ref> and the statements of Example <ref> and Remark
<ref>, we see that for model
(<ref>) the debiased
estimator of Theorem 3.8 in <cit.>, which uses
Θ̃_1= Θ_1, is in certain cases asymptotically  inefficient as
a choice Θ̃_1 = Θ_1^♯≠Θ_1 can give
an improvement in the asymptotic variance (and is then efficient for certain
cases).




In this example we take the model (<ref>) with 0< s = o( n / log p ). 
Let β̂ be again the Lasso estimator 
given in (<ref>)
with appropriate choice of the tuning parameter λ≍√(log p / n ).
One may use a “slow rates" result: uniformly in β^0 ∈ B it is true that

    Σ^1/2 ( β̂- β^0 ) _2 = o__β^0 (1) ,  β̂- β^0 _1 = 𝒪__β^0  (√(s)) ,

see for example
<cit.>, Theorem 6.3, and combine this with results for quadratic forms as
given in (<ref>). 
(The arguments for establishing these “slow rates" are in fact as in Lemma <ref> for the node-wise Lasso.) Taking β̂_I and β̂_II again as appropriate Lasso's, condition (<ref>) 
of Theorem <ref> holds if

    λ^♯√(ns)= 
    o(1) .

Then for γ^♯_1 = 𝒪 (√(ns)) we get an eligible
pair ( γ^♯, λ^♯). Since when β^0 stays away from the 
boundary, such γ^♯ form a model direction
after scaling, we see that the Cramér Rao lower bound is achieved.
Recall now that in Example <ref> we concluded that, in view
of Corollary <ref>,
in order to be able to improve over Θ_1,1 we must have γ^0 _1
of order larger than √(ns). 
As pointed out in Remark <ref> 
one may apply one of
the  Lemmas <ref>, <ref> or
<ref> to create vectors γ^0 and eligible pairs
(γ^♯, λ^♯) where λ^♯√(ns)→ 0, γ^♯_1 can take any value of order √(ns) and 
Θ_1,1 - Θ_1,1^♯≫ 0.
























  
The results for model (<ref>)
are a special case of those for model (<ref>).
One needs again s= o( n / log p) and one may for example apply
Corollary 2.4 in <cit.>, again together with (<ref>). For the Lasso
β̂ in (<ref>) with λ≍√(log p / n) appropriately chosen one gets
uniformly in β^0 ∈ B

    Σ^1/2 ( β̂- β^0 ) _2^2 = 𝒪__β^0 
    ( s log p / n   )^2-r  2 ,  β̂- β^0 _1 =
    𝒪__β^0  ( ( log p / n)^1-r  2  s^2-r  2 ).

The requirement (<ref>) on λ^♯ is thus

    λ^♯ ( log p)^1- r  2√(n^r  s^2-r )= o(1) .

If γ^♯_r^r = 𝒪 ( √( n^r s^2-r) )
then (γ^♯, λ^♯) is an eligible pair and the Cramér Rao
lower bound is achieved whenever β^0 stays away from the boundary. 
In order to be able to improve over Θ_1,1 we now
need γ^0 _r^r of larger order √( n^r s^2-r)
by Corollary <ref>. 
Remark <ref> can be taken into the considerations here too.








§ FINDING ELIGIBLE PAIRS
 
The main results of this section can be found in Subsection
<ref> where for any λ^♯ we construct eligible pairs
(γ^♯, λ^♯) by choosing γ^0 appropriately.
The results can be seen as existence proofs. Before doing these
constructions we discuss uniqueness in Subsection
<ref>, in Subsection <ref> the noiseless Lasso as a practical method
for improving over Θ_1,1 and in Subsection <ref> we examine
whether or not projections on a subset
of the variables can lead to eligible pairs. For the latter we impose rather string conditions.
We show in Subsection <ref> that eligible pairs are more flexible than projections.
Nevertheless in the final part of this section we return to projections as they come
up naturally when imposing non-sparsity constraints on γ^0





 §.§ Uniqueness


 Fix λ^♯ and let
(γ^♯, λ^♯) and (γ^♭, λ^♯)
be two eligible pairs. Then

    Σ_-1,-1^1/2  (γ^♯ - γ^♭ )_2^2 → 0 .



This lemma tells us that asymptotically it makes no difference to debias using
(γ^♯, λ^♯) or (γ^♭, λ^♯). 




















  




 §.§ Using the Lasso

Fix some tuning parameter λ_ Lasso and consider the noiseless Lasso

    γ_ Lasso:= min_c ∈^p-1{ (  x_1 -  x_-1 c )^2 + 2  λ_ Lasso c _1 } .

One may verify that  (γ_ Lasso, λ_ Lasso) is an eligible pair if
λ_ Lassoγ^0 _1 → 0. But the latter is exactly
what we want to avoid. 
If ( γ^♯ , λ^♯) is an eligible pair
then the noiseless Lasso can find it if one chooses λ_ Lasso= 𝒪 ( λ^♯) larger
than λ^♯, as follows from the next lemma. It says that given λ^♯ one
may use the noiseless Lasso for constructing a direction, Θ_1,  Lasso say,
with which one has same improvement over Θ_1,1 as with Θ_1^♯.

 Suppose ( γ^♯, λ^♯) is an eligible pair.
Let λ_ Lasso > λ^♯ 
and λ_ Lassoγ^♯_1 → 0.
Let γ_ Lasso be the noiseless Lasso defined in (<ref>).
Then

    Σ_-1,-1^1/2  (γ_ Lasso - γ^♯ )_2^2 → 0 
     .

In addition, if λ_ Lasso≥ 2 λ^♯ (say)
then
( γ_ Lasso , λ_ Lasso) is an eligible pair.


  

  



 §.§ Using projections


In this subsection we investigate (rather straightforwardly) conditions such that the coefficients of
a projection of x_-1γ^0 
can be joined with a λ^♯ to form an eligible pair.

Fix some set S⊂{ 2, … , p } with cardinality s. 
The value of s need not be s, where s is the sparsity
used in the model class B.
Let x_S γ_S^S be the projection
of x_-1γ^0 on x_S. 


Let γ^S ∈^p-1 be the vector γ_S^S
∈^ s completed with zeroes. 
Then γ^S _1 ≤√( s)γ^S _2 = 𝒪 (√( s) )
so that when 

    λ^♯√( s)→ 0

we have for γ^S the sparsity condition (<ref>)
of Definition <ref>:
λ^♯γ^S _1 → 0. 
Note that γ^0TΣ_-1,-1γ^S = γ^STΣ_-1,-1γ^S(=  (  x_S γ_S^S )^2) exactly in this case.
Furthermore

    v^S := Σ_-1,-1 ( γ^0 - γ^S) = [ 0   v_-S^S ]

where

    v_-S^S =  x_-S x_-1γ^-S ,

with

    x_-1γ^-S = ( x_-Sγ_-S)  A x_S =:
     (  x_-S -  x_S^T Σ_S,S^-1Σ_S,-S ) γ_-S^0

being the anti-projection of x_-Sγ_-S^0 on x_S. 
We check whether
the pair (γ^S , λ^♯) is an eligible
pair, which is the case if  λ^♯√( s) = o(1) and v_-S^S _∞≤λ^♯.  
We briefly discuss some conditions that may help ensuring the latter.

Let A _1 := max_j ∑_k |a_j,k |
be the ℓ_1-operator norm of the matrix  A. 

  It holds that

    v_-S^S _∞≤Σ_-S, -S - Σ_-S, SΣ_S,S^-1Σ_S,-S_1   γ_-S^0 _∞  .





To arrive at a sparse approximation of γ^0 one may consider putting its
p- s-1 smallest-in-absolute-value coefficients to zero.
To this end, consider the ordered sequence | γ^0 |_(1)≥⋯≥ |γ^0|_(p-1), 
write |γ^0|_(j) =: |γ_r_j ^0 |, j= 1, … , p-1, and let
S= { r_1 , … r_ s}. Then clearly γ_-S^0 _∞≤γ^0 _2 / √( s)
= 𝒪 (1/ √(s)).
The condition (<ref>) excludes 1/ √( s) = 𝒪 ( λ^♯).
We therefore examine situations where the coefficients in γ^0 decrease at a rate quicker than 1/ √( s)


 Let N be some integer and 0 ≠ v ∈^N be a vector.  We call

    κ (v) :=  v _1  v _∞ v _2

the sparsity index of v.
We say that v is asymptotically sparse if κ (v)→ 0.


A vector v with v _2=𝒪 (1) can have some 
relatively large coefficients, but it cannot have too many of these. If 
in addition v _1 is large it cannot have many zeroes either.
Asymptotic non-sparseness of the vector v with the large
coefficients removed means that there are many very small
non-zero coefficients. 

 Let v_j = 1/ √(N) for all j. Then 
v _1 = 1/  v_∞ = √(N). Thus κ (v)=1 
and v is not (asymptotically) sparse.


 Let s≤ N and v_j=0 for j ≤ s and v_j = 1/ √(j log N ) for j> s. Then 
κ(v)  ≍√( N /( slog^2 N) ).
The vector v is not asymptotically sparse if s= 𝒪  (N/ (log^2 N) ). 


 
Suppose that γ_-S^0 is not asymptotically sparse.
Let

    λ^S = κ (γ_-S^0)  C  γ_-S^0 _1  ,
 where

    C:= Σ_-S, -S - Σ_-S, SΣ_S,S^-1Σ_S,-S_1  .

Assume that λ^S √( s)→ 0. Then
( γ^S , λ^S) is an eligible pair and
λ^S γ^0 _1 ↛0.




 §.§ Approximate projections

Recall that the first condition (<ref>) of Definition <ref> can be written as
  
    x_-1γ^0 =  x_-1γ^♯ + ξ^0

  where ξ^0 is “noise" satisfying x_-1^T ξ^0 _∞≤λ^♯. 
  Denote the active set of γ^♯ 
  by S = { j∈{ 2 , … , p }: γ_j^♯≠ 0 } and its cardinality by s := |S|.
   Then λ^♯√( s)→ 0 implies that 1/ Θ_1,1^♯ is asymptotically
  the squared residual of the projection of x_1 on x_S as is shown in the next lemma.
  In that sense, eligible pairs are more flexible than projections. 

   If s is small enough, then for model (<ref>),
   (<ref>) or (<ref>) 
  one has that Θ_1^♯ is a model direction (after rescaling). The estimator
  b̂_1^♯ in Theorem <ref> then reaches the Cramér Rao lower bound.
  
  
    Suppose for some set S 
  with cardinality s that γ^♯ = γ_S^♯
  and assume
 the first condition (<ref>) of Definition <ref>. If λ^♯√( s)→ 0
 then the second condition (<ref>) holds too so that (γ^♯, λ^♯) is an eligible pair. Moreover,
 
    1/ Θ_1,1^♯ = ( x_1 -  x_S γ_S^S )^2 + o(1)

 where 
 
    γ_S^S = Σ_S,S^-1 x_S^T  x_1 .

   





 §.§ Reverse engineering

In this subsection we fix λ^♯ and then construct vectors γ^0 ∈^p-1 such that there is an eligible pair
(γ^♯, λ^♯ ). These constructions are in a sense equivalent
but approach the problem from different angles.
In these constructions the vector γ^♯
is having active set S= {γ_j^♯≠ 0 } with cardinality s:= |S|.
The sparsity of γ^♯ is then measured in terms of 
the value of s. More general constructions are possible, but in this
way we can apply the results to any of the models
(<ref>), (<ref>) or (<ref>).
In view of Lemma <ref> is means that the constructions correspond
to an approximate projection on x_S. 

Throughout this subsection, the matrix Σ_-1, -1 is
is assumed to have 1's one the diagonal and smallest eigenvalue Λ_ min^2 (Σ_-1, -1)≫ 0.



  §.§.§ Which γ^0's are allowed?

We let for γ^0 ∈^p

    Σ (γ^0):= [                      1 γ^0TΣ_-1,-1Σ_-1, -1γ^0               Σ_-1, -1 ] .


  We say that the vector γ^0 is allowed if
Σ (γ^0) is positive definite, with
Λ_ min^2 (Σ (γ^0)) ≫ 0
and  Σ_-1, -1γ^0 _∞≤ 1. 


 
Suppose that 

    1- Σ_-1,-1^1/2γ^0 _2^2  ≫ 0 .

Then
γ^0 is allowed. 




  §.§.§ Regression: γ^0 as least squares estimate of γ^♯

In this subsection we create γ^0 using random noise. We then arrive at an eligible
pair “with high probability". Let N∈ be a given sequence with N > p. Take a matrix
Z_-1∈^N × (p-1) which has Z_-1^T Z_-1 / N = Σ_-1,-1. 
Let ξ∈^N have i.i.d. standard Gaussian entries, let
γ^♯∈^p-1 be a vector satisfying γ^♯_1= o ( √(log p / N ) ) 
 and define 
 
    Z_1 := Z_-1γ^♯ + ξ .

 Let
 
    γ^0 := (Z_-1^T Z_-1 )^-1 Z_-1^T Z_1

 be the least  squares estimator of γ^♯. Finally let λ^♯≍√(log p / N).
 be appropriately chosen. 
 Then ( γ^♯ , λ^♯) is with high probability an eligible pair. Indeed
 the first condition (<ref>) of Definition <ref> follows from
 
    Σ_-1,-1 (γ^0- γ^♯ ) _∞= 
      Z_-1^T ξ/N _∞ = 𝒪_ ( √(log p / N) )

 so that for appropriate λ^♯≍√(log p / N), with high probability
  
    Σ_-1,-1 (γ^0- γ^♯ ) _∞≤λ^♯ .

 The second condition (<ref>) of Definition <ref> follows from the condition
 γ^♯_1= o ( √(log p / N ) ) so λ^♯γ^♯_1 = o(1). 
 We also see that if p/N ≫ 0 then with high probability Θ_1,1^♯ as given
 in (<ref>) is an improvement over Θ_1,1, since
 
    Σ_-1,-1 ^1/2 ( γ^0 - γ^♯ )_2^2 = χ_p-1^2 / N

 where χ_p-1^2 has the chi-squared distribution with p-1 degrees of freedom. 
 It follows that

    Σ_-1,-1 ^1/2 ( γ^0 - γ^♯ )_2^2= p + 𝒪 (√(p) )  N .

With high probability this stays away from zero so that also

    Θ_1,1 - Θ_1,1^♯≫ 0 .

For appropriate N with 1- p/N ≫ 0 the vector γ^0 is with high probability also allowed by
Lemma <ref>. 
With this choice of N we have λ_♯≍√(log p / p ). Recall that
according to Remark <ref> it must be true that p ≥ 1/ λ^♯ 2.
In the present context we in fact have p ≍log p / λ^♯ 2.



  §.§.§ Creating γ^0 directly


We first recall that 

    Θ_1,1 - Θ_1,1^♯≫ 0 ⇔Σ_-1,-1^1/2 (γ^0 - γ^♯) _2^2 ≫ 0

with Θ_1^♯ given in (<ref>).
It will be the case in the constructions of this subsection. 

Fix some set S⊂{ 2 , … , p } with cardinality s and fix some λ^♯. We will assume 
λ^♯√( s)→ 0. 


 
Suppose there exists a vector z ∈^p-1 with 

    z _∞≤ 1 ,

and 

    1 - λ^♯2Σ_-1,-1^-1/2 z _2^2 ≫ 0  , λ^♯ 2Σ_-1,-1^-1/2 z _2^2 ≫ 0  .

Let γ^♯ be a vector in ^p-1 with 
γ_-S^♯=0 (i.e. γ^♯ = γ_S^♯) and

    1-  λ^♯2Σ_-1,-1^-1/2 z _2^2 -Σ_-1,-1^1/2γ_S^♯_2^2  ≫ 0
     .

Define

    γ^0 :=γ^♯+ λ^♯Σ_-1,-1^-1 z .

Then, if λ^♯√( s)→ 0, the pair (γ^♯, λ^♯) is an
eligible pair. Moreover, γ^0 is eventually allowed, λ^♯γ^0 _1 ↛0
and in fact

    Σ_-1,-1^1/2 (γ^0 - γ^♯) _2^2 ≫ 0.

 



Recall that Λ_ min^2 (Σ_-1,-1 ) ≫ 0. To check condition (<ref>) for
some z _∞≤ 1 one may want to impose in addition that
Λ_ max (Σ_-1,-1 ) = 𝒪 (1).  Then the condition is true
if z _2  ≍ 1/λ^♯ which is true for instance if
 1/ λ^♯2 of the coefficients of z stay away from zero.  This is only possible
 if p > 1/ λ^♯ 2 i.e., in high-dimensional situations (see also
 Remark <ref>). 
 
 
   One may also consider taking
 z= Z_-1^T ξ/(N λ^♯) where Z_-1, ξ and λ^♯ are
 is in Subsection <ref>. Then
 
    λ^♯ 2Σ_-1,-1^1/2 z _2^2 = χ_p-1^2 / N

 as there and one arrives at eligible pairs “with high probability". 
 
 
We now examine the following question: can one choose γ_S^♯ in Lemma
<ref> equal to γ_S^0?
As we will see this will only be possible if a form of the irrepresentable condition
 holds.
The “usual" irrepresentable condition (that implies
the absence of false positives of the Lasso, see <cit.>) involves the coefficients of the 
projection of the “large" collection x_-S on the “small" collection x_S.
In our case, we reverse the roles of S and -S.

 Fix a vector z_-S∈^p- s-1 with z_-S_∞≤ 1. We say that the
reversed irrepresentable condition holds for (S, z_-S) if

    Σ_S, -SΣ_-S, -S^-1 z_-S_∞≤ 1 .




 

a) Assume the reversed irrepresentable condition holds for (S , z_-S), 
and that in addition

    1-   λ^♯ 2Σ_-1,-1^-1/2  z_-S_2^2 ≫ 0  ,  λ^♯2Σ_-1,-1^-1/2  z_-S_2^2 ≫ 0  .

Let γ_S^0 satisfy

    1- λ^♯2Σ_-1,-1^-1/2  z_-S_2^2-
    Σ_-1,-1^1/2γ_S^0 _2^2 
    ≫ 0  .

Define γ_-S^0 :=  λ^♯Σ_-S,-S^-1 z_-S and 
γ^♯:= γ_S^0
Then, if λ^♯√( s)→ 0, the pair (γ^♯, λ^♯)
is an eligible pair, γ^0 is eventually allowed and 
λ^♯γ^0 _1 ↛0. In fact

    Σ_-1,-1^1/2 (γ^0 - γ^♯) _2^2 ≫ 0.

b) Conversely, if for some γ^0 and for γ^♯ := γ_S^0 
the pair (γ^♯, λ^♯)
is an eligible pair, then the reversed irrepresentable condition holds for (S , z_-S) with appropriate
z_-S satisfying z_-S_∞≤ 1. 
 





  §.§.§ Creating γ^0 using a non-sparsity restriction
 

Fix some set S⊂{2 , … , p } with cardinality s and some λ^♯>0.
Let w ∈^p-1 be a vector of strictly positive weights with w _∞≤ 1 and define
the matrix W as the diagonal matrix with w on its diagonal.
 Let

    c^0 ∈min{Σ_-1,-1^1/2c_2^2 : λ^♯ ( W c )_-S_1 = 1 }

and

    ζ_S := 0,  ζ_j  :=  sign (c_j^0 ),  j ∉ S .



The random variable
x_-1 c^0 is orthogonal to (i.e. independent of) x_S.
Moreover

    Σ_-1,-1 c^0 _∞ =  w_-S_∞λ^♯Σ_-1,-1^-1/2 W ζ_2^2

and

    Σ_-1,-1^1/2 c^0 _2^2 =   1 λ^♯2Σ_-1,-1 ^-1/2 W ζ_2^2





  Suppose that

    1-  (λ^♯2Σ_-1,-1^-1/2 W ζ_2^2)^-1≫ 0   
     ,  λ^♯2Σ_-1,-1^-1/2 W ζ_2^2 = 𝒪 (1) .

Let γ^♯ be a vector satisfying γ_-S^♯=0 and

    0<1-   (λ^♯2Σ_-1,-1^-1/2W  ζ_2^2)^-1-
    Σ_-1,-1^1/2γ_S^♯_2^2 ≫ 0.

Define γ_-S^0 = c_-S^0 and x_-1γ^0 :=
 x_S γ_S^♯  + ( x_-S A x_S ) γ_-S^0. 
Then x_S γ_S^♯ is the projection of x_-1γ^0 on
x_S. Moreover, if λ^♯√( s)→ 0, the pair
(γ^♯, λ^♯) is eligible, γ^0 is allowed
and λ^♯γ^0 _1 ↛0.
In fact

    Σ_-1,-1^1/2 (γ^0 - γ^♯) _2^2 ≫ 0.





As in  Remark <ref>, 
to deal with the requirement  (<ref>) one may want to impose the condition 
Λ_ max^2 ( Σ_-1,-1 )=𝒪 (1).
 



§ THE CASE Σ UNKNOWN


As we will see
the concept of an eligible pair will also play a crucial role when
Σ is unknown.

We use in this section the noisy Lasso

    γ̂∈min_c ∈^p-1{ X_-1 - X_-1 c _2^2 / n + 2  λ^ Lasso c _1 } .

We require the the tuning
parameter λ^ Lasso to be 
of order √(log p / n).
Then in the debiased Lasso given in (<ref>) we apply

    Θ̃_1 := Θ̂_1
 where

    Θ̂_1 := [ 1  - γ̂ ]/ ( X_1 - X_-1γ̂_2^2 / n +
     λ^ Lassoγ̂_1  ).





Let (γ^♯, λ^♯) be an
eligible pair, with λ^♯ = 𝒪 ( √(log p / n) ). 
In Lemma <ref>, we in fact need λ^ Lasso to be at least as large as λ^♯. The
latter is allowed to be of small order √(log p / n), yet we will assume
λ^ Lassoγ^♯_1 → 0.

Let η_n → 0 be a sequence 
such that 

    ( 
    inf_c:  λ^ Lasso c _1 ≤ 4η_n^2  ,  Σ_-1,-1^1/2 c_2  = 1  X_-1 c _2^2/n  ≥1  2 ) → 1 .

Such a sequence exists, see for example Chapter 16 in <cit.> and its references.

Define
 ε := X_1- X_-1γ^0 and
ε^♯ := X_1- X_-1γ^♯= ε + X_-1
(γ^0 - γ^♯ ).  Choose λ_ε^♯≍√(log p / n) in such a way that

    (  X^T ϵ^♯_∞/n≥λ_ε^♯ ) → 0

(see Lemma <ref>). This implies λ_ϵ^♯≥λ^♯. 

The following lemma establishes the so-called “slow rate". The proof is standard (see for example
<cit.>, Theorem 6.3), up to the replacement of ε by
ε^♯. The result is the noisy counterpart of Lemma <ref>


 Let λ^ Lasso≍√(log p / n ) satisfy
λ^ Lasso≥ 2 λ_ε^♯ and suppose
λ^ Lasso γ^♯_1 ≤η_n^2. Then
we have

    λ^ Lasso γ̂_1 = o_(1) ,   X_-1  ( γ̂- γ^♯) _2^2/n= o_ (1) ,  Σ_-1,-1^1/2  ( γ̂- γ^♯) _2^2 = o_ (1) .










 
Let b̂_1 be the debaised Lasso given in (<ref>)  with Θ̃_1 equal to
Θ̂_1 given in
(<ref>):

    b̂_1 := β̂_1 + Θ̂_1 X^T (Y- X β̂)/n .

Assume that λ^♯ = 𝒪 (√(log p / n)), that
√(log p / n)γ^♯_1 = o(1) and 
λ^ Lasso≍√(log p / n) is sufficiently large 
(depending only on λ^♯).
Suppose that uniformly in β^0 ∈ B

    √(log p )β̂- β^0 _1= o__β^0 (1).

 Then uniformly in β^0 ∈ B
 
    b̂_1 - β_1^0 = Θ̂_1^T X^T ϵ / n + o__β^0 (1/√(n)) .

 Moreover,

    lim_n →∞sup_β^0 ∈ B ( √(n)  (b̂_1 - β_1^0 )√(Θ̂_1^T Σ̂Θ̂_1 )≤ z  )=  Φ (z)  ∀ z ∈ ,

and for Θ_1^♯ given in (<ref>)

    Θ̂_1^T Σ̂Θ̂_1= Θ_1,1^♯ + o_ (1) .




 Recall that Lemmas <ref>, <ref> and
<ref> present examples of eligible pairs
(γ^♯, λ^♯) where Θ_1,1^♯ 
remains strictly smaller than Θ_1,1. 
 


 By Slutsky's Theorem we conclude that the asymptotic variance of b̂_1
is (up to smaller order terms) equal to Θ_1,1^♯. 



 Note that Theorem <ref> only requires sparsity of γ^♯ in ℓ_1-sense:
it requires γ^♯_1= o( √(n / log p)). Indeed, we in fact base
the result on “slow rates" for the Lasso γ̂ given in Lemma <ref>


 Assume the conditions of Theorem <ref>.
and that in fact

    √(log p)γ̂- γ^♯_1 = o_ (1) .

Then also √(log p)Θ̂_1  - Θ_1^♯_1 = o_ (1), which implies

    Θ̂_1 X^T ϵ /n = Θ_1^♯ X^T ϵ / n + o_ (1/ √(n)) .

Thus, then the estimator b̂_1 is asymptotically linear, uniformly in β^0 ∈ B. 
The uniform asymptotic linearity of b̂_1 implies in turn that the Cramér Rao lower bound of Subsection
<ref> applies. 


The results of the following two examples are summarized in Table <ref>.

 
Assume the sparse model (<ref>) with
s = o ( √(n) / log p ). As stated in Example <ref>, for the 
Lasso estimator 
β̂ given in (<ref>),
with appropriate choice of the tuning parameter λ≍√(log p / n ), one has
uniformly in β^0 ∈ B

    β̂- β^0 _1 = O__β^0 ( s √(log p / n) )=
    o__β^0 (1/√(log p) ) .

Suppose now as in Theorem <ref> that λ^♯ = 𝒪
(√(log p / n )) and √(log p / n )γ^♯_1 = o(1). 
In fact, assume that γ^♯_0^0 is small enough so that
Θ_1^♯ is a model direction.
Then one obtains
by the same arguments  if λ^ Lasso≍√(log p /n ) is suitably chosen

    γ̂- γ^♯_1 = O_ ( s √(log p / n)  )= o__β^0
    (1/ √(log p) ).

Thus then (<ref>) is met so that we have asymptotic linearity.
It means that the Cramér Rao lower bound applies and is achieved.


The model (<ref>) is too large for us to be able to apply when Σ is unknown.
We now turn to the model (<ref>).


For the model (<ref>) the rates for the Lasso β̂ are given in Example
<ref>. One sees that for 0 ≤ r < 1 the requirement on s becomes

    s = o(n^1-r  2-r / log p ) .

By the same arguments, if for a fixed 0 ≤ r≤ 1

    γ^♯_ r^ r= o(n^1- r 2 / log^2-  r 2 p )

one finds

    γ̂- γ^♯_1 =  o_ (1/ √(log p) )

which yields asymptotic linearity so that the Cramér Rao lower bound applies. If such γ^♯ is in
addition a model direction after scaling, i.e. if
γ^♯_r^r = 𝒪 ( n^r  2 s^2-r  2 ), then
the Cramer Rao lower bound is achieved whenever β^0 stays away from the boundary. 




§ CONCLUSION

This paper illustrates that Θ_1,1 can be larger than the asymptotic Cramér
Rao lower bound, that for certain Σ the
asymptotic variance of a debiased Lasso is smaller than Θ_1,1 and that in special such cases the asymptotic Cramér Rao lower bound
is achieved. 
In Examples <ref> and <ref> we showed that if β^0 stays
away from the boundary, then the asymptotic Cramér Rao lower bound is

    (  min_ c _r^r ≤ M n^r  2 s^2-r  2 (  x_1 -  x_-1 c )^2  )^-1

where M is any fixed value. When Σ is known, Theorem <ref> shows
that up to log-terms this lower bound is achieved as soon as there exists an eligible pair (γ^♯, λ^♯).
with γ^♯_r^r = 𝒪 (n^r  2 s^2-r  2 ).
When Σ is unknown the situation is more involved and in particular for model (<ref>)
sparsity variant (i) is replaced by the stronger variant (ii). Model (<ref>) is too large for the case Σ unknown and model (<ref>) requires more sparsity then
model (<ref>): the larger r the smaller s is required to be. 
Model (<ref>) however appears for both known and unknown Σ too
stringent as results depend on the exact value of s, not only on its order.
Model (<ref>) (with Σ known) or more generally model (<ref>)
(with 0<r<1 if Σ is unknown)
do not suffer from such a dependence as long as β^0
stays away from the boundary.  



§ PROOFS
 



 §.§ Proof for Section <ref>
 

The proof of Proposition  <ref>
relies on the results in <cit.>, which allow the arguments to
follow those of the
low-dimensional case. These arguments are then rather standard.

Proof of Proposition <ref>.  Let h ∈ H_β^0, |h_1 | ≥ρ and
h^T Σ h ≤ R^2.
The log-likelihood ratio L (h) for  β^0+ h / √(n)
with respect to β^0 is

    L (h)    =    h^T X^T ϵ / √(n) + h^T Σ̂h / 2
        =     h^T X^T ϵ / √(n) + h^T Σ h / 2+ o_ (1)

since h^T Σ h = 𝒪 (1). 
Let for (x , y) ∈^p+1

    l_β_0 (x,y):= [ i_β^0 (x,y)  x^T (y- xβ^0) ]

and define

    Ω_β^0 := _β^0 l_β^0 ( x,  y ) l_β^0 ( x,  y )^T.
 
By the Lindeberg condition, we can apply Lindeberg's central limit theorem to conclude that
for any sequence a:= (1, c^T  )^T ∈^p+1 with c^T Σ c  = 𝒪 (1) it holds
that

    a^T∑_i=1^n  l_β^0 (X_i, Y_i) √( n a^T  Ω_β^0 
    a) ) D_β^0    ⟶ N (0,1)  .

Therefore, by Wold's device

    (  [    1 0  0  h^T ]Ω_β^0[    1 0  0    h ] )^-1/2[    1 0  0  h^T ]∑_i=1^n l_β^0  (X_i, Y_i) / 
     √(n)   D_β^0    ⟶  N (0,
     [    1 0  0    1 ] ) .

 We now apply  a slight modification of Lemmas 16 and 23 in <cit.>, where we
 drop the assumption of bounded eigenvalues of Σ 
 (which is possible because we have h^T Σ h ≤ R^2 = 𝒪 (1)). The asymptotic linearity of T 
 and the 2-dimensional central limit theorem just obtained imply that
 at the alternative β^0 + h / √(n) it holds that 
 
    T - (β_1^0 + h_1 / √(n)) +h_1  - h^T_β^0 i_β^0  ( x,  y )
       x^T ( y  -  xβ^0 ) √(n V_β^0^2 )   D_β^0  + h / √(n)⟶ N (0 ,1) .

 As T is assumed to be regular at β^0 we conclude that
 
    h^T _β^0 i_β^0  ( x,  y )
       x^T ( y  -  xβ^0 ) = h_1 + o(1) .

  But by the Cauchy-Schwarz inequality
 
    (  h^T _β^0 i_β^0  ( x,  y )
       x^T ( y  -  xβ^0 )  )^2 ≤ V_β^0^2 h^T Σ h .

  Moreover, 
    
    (h_1 +o(1) )^2= h_1^2 + o(1) .

  so that we obtain
  
    V_β^0^2  ≥ h_1^2 +o(1)  h^T Σ h  =  h_1^2  h^T Σ h + o(1)

  where in the last step we used h^T Σ h ≥ h_2^2 / Λ_ min^2 ≥ρ^2
  so that  1/h^T Σ h= 𝒪 (1). 
   Since the result is true for all h ∈ H_β^0, |h_1 | ≥ρ and
h^T Σ h ≤ R^2, we may maximize the right hand side of
(<ref>) over all such h.
 ⊔ -12mu ⊓
  




 §.§ Proofs for Section <ref>
 

 Proof of Lemma <ref>. 
  Because x_-1γ^0 is the projection of x_1 on
  x_-1 we know that
  
    (  x_1 -  x_-1γ^♯ )^2 ≥ (  x_1 -  x_-1γ^0 )^2 = 1/ Θ_1,1 .

  Moreover
  
    Θ_1,1 =  e_1^T Θ e_1 ≤Λ_ max^2 (Θ ) =
      1/ Λ_ min^2 .

  Thus
  
    (  x_1 -  x_-1γ^♯ )^2  ≥Λ_ min^2 .

  We now rewrite
  
    (  x_1 -  x_-1γ^♯ )^2    =    1+
      γ^♯ TΣ_-1,-1γ^♯ - 2  x_1^T  x_-1γ^♯
       =    1+  γ^♯ TΣ_-1,-1γ^♯ - 2 γ^0TΣ_-1,-1γ^♯

  where in the second equality we
  used that x_1 -  x_-1γ^0 is the anti-projection
  of x_1 on x_-1  and hence orthogonal to x_-1γ^♯. 
  For the cross-product we have by the two conditions on the pair (γ^♯, λ^♯)
  
    γ^0TΣ_-1,-1γ^♯   =    γ^♯ TΣ_-1, -1γ^♯ +
      ( γ^0 - γ^♯ )^T Σ_-1, -1γ^♯_ | · | ≤Σ_-1, -1( γ^0 - γ^♯ ) _∞γ^♯_1 ≤λ^♯γ^♯_1= o(1) 
       =   γ^♯ TΣ_-1, -1γ^♯ + o(1) .

  Thus
  
    (  x_1 -  x_-1γ^♯ )^2 = 1- γ^0 TΣ_-1, -1γ^♯  +o(1) .

  Combining this with inequality (<ref>) proves the first result of the lemma. 
  The second result:
  
    Σ( Θ_1^♯- Θ_1 )_∞≤λ_0^♯

  follows trivially from this. 
  For the third result, we compute and re-use the already obtained results:
    
    Θ_1^♯ΣΘ_1^♯    =   1 - γ^0 TΣ_-1,-1γ^♯ - γ^♯ TΣ_-1,-1 (γ^0 - γ^♯ )
      (1 - γ^0 TΣ_-1,-1γ^♯)^2
        =   1  
      1 - γ^0 TΣ_-1,-1γ^♯_= Θ_1,1^♯  +o(1) 
       =    1/  ( x_1-  x_-1γ^♯ )^2 + o(1) 
       ≤   1/  ( x_1-  x_-1γ^0 )^2 _= Θ_1,1 +o(1) .
 
   To show the final statement of the lemma, assume on the contrary
   that γ^0 is sparse:
   
    λ^♯γ^0 _1 → 0 .

   Then
   
    Θ_1,1^♯   =    1  1- γ^0TΣ_-1,-1γ^♯
        =    1  1- γ^0TΣ_-1,-1γ^0 + γ^0TΣ_-1,-1(γ^0 -
       γ^♯_|· | ≤λ^♯γ^0 _1 = o(1) )
       =   Θ_1,1 + o(1) .

   ⊔ -12mu ⊓
   
   Proof of Theorem <ref>. We use the decomposition
of the beginning of this section applied to b̂_I,1^♯

    b̂_I,1^♯ - β_1^0 =2 Θ_1^♯ T X_I^T ϵ_I / n +  ( e_1^T -
    Θ_1^♯ TΣ̂_I) ( β̂_II - β_1^0 )_ remainder_I

where remainder_I  is

    ( e_1^T-Θ_1^♯ TΣ̂_I ) ( β̂_II - β^0 )=
     Θ_1^♯ T ( Σ - Σ̂_I )(β̂_II - β^0 )_:=(i) + 
    (  e_1^T  -  Θ_1^♯ TΣ) (β̂_II - β^0 )_:=(ii) .

 Here, ϵ_I := Y_I - X_I β^0 and Σ̂_I:= 2X_I^T X_I /n.
 But, given (X_II , Y_II),
 
    Θ̂_1^♯ TΣ̂_I (β̂_II - β^0) =
     2 Θ_1^♯ T X_I^T X_I(β̂_II - β^0) /n

 is the average of n/2 i.i.d. random variables which are the product of a random variable with the
 N (0, Θ_1^♯ TΣΘ_1^♯)-distribution 
 and a N (0, Σ_1/2 ( β̂_II - β^0) _2^2)-distributed random variable. 
 Since the variances satisfy Θ_1^♯ TΣΘ_1^♯= Θ_1,1^♯ +
 o(1) = 𝒪 (1) and Σ_1/2 ( β̂_II - β^0) _2^2=o__β^0 (1) uniformly in β^0 ∈ B we see that
 
    (i) = o__β^0 (1/ √(n) )

 uniformly in β^0 ∈ B.  For the term (ii) we use that
 
    ΣΘ_1^♯ -  e_1_∞ = 𝒪 (λ^♯ )

 and the assumption
 λ^♯β̂_II - β^0 _1 =o__β^0  (1/ √(n) ) uniformly
 in β^0 ∈ B. 
 This gives that uniformly
 in β^0 ∈ B

    b̂_I,1^♯ - β_1^0 = 2 Θ_1^♯ TX_I^T ϵ_I /n +
     o__β^0 (1/ √(n)).

 In the same way one derives that
 uniformly
 in β^0 ∈ B

    b̂_II,1^♯ - β_1^0 = 2 Θ_1^♯ T X_II^T ϵ_II/n +
     o__β^0 (1/ √(n))

 with ϵ_II := Y_II - X_IIβ^0. Since
 b̂_1^♯ = (b_I,1^♯ + b_II,1^♯ )/2 is the average of the
 two, this proves the asymptotic linearity. Further
 var ( Θ_1^♯ X^T ϵ / √(n)) = Θ_1^♯ TΣΘ_1^♯=
 Θ_1,1^♯+o(1) by Lemma <ref>. The central limit theorem completes the proof. 
 ⊔ -12mu ⊓
 
 

 §.§ Proofs for Section <ref>

 
 Proof of Lemma <ref>. We have

    (γ^♯ - γ^♭ )^TΣ_-1,-1 (γ^♯ - γ^♭ )
       ≤   γ^♯ - γ^♭_1 Σ_-1,-1 (γ^♯ - γ^♭ )_∞
       ≤   λ^♯γ^♯ - γ^♭_1 
       ≤   λ^♯γ^♯_1 +  λ^♯γ^♭_1 → 0

⊔ -12mu ⊓




Proof of Lemma <ref>.  By the KKT conditions

    (γ_ Lasso - γ^♯)^T Σ_-1, -1 ( γ_ Lasso - γ^0) ≤λ_ Lassoγ^♯_1-  λ_ Lassoγ_ Lasso_1 .

Therefore,

    (γ_ Lasso - γ^♯ )^T Σ_-1,-1 (γ_ Lasso - γ^♯ ) 
        =    
     (  γ_ Lasso - γ^♯)^T Σ_-1, -1 (  γ_ Lasso - γ^0)+
     (  γ_ Lasso - γ^♯)^T Σ_-1, -1 ( γ^0 - γ^♯)
       ≤   λ_ Lassoγ^♯_1-  λ_ Lassoγ_ Lasso_1 +
      γ_ Lasso - γ^♯_1 Σ_-1, -1 ( γ^0 - γ^♯)_∞
       ≤   λ_ Lassoγ^♯_1-  λ_ Lassoγ_ Lasso_1 +
      λ^♯γ_ Lasso - γ^♯_1  
       ≤    ( λ_ Lasso + λ^♯ )γ^♯_1 -
      ( λ_ Lasso - λ^♯ ) γ_ Lasso_1 .

  Thus
  
    (γ_ Lasso - γ^♯ )^TΣ_-1,-1(γ_ Lasso - γ^♯ ) +
       ( λ_ Lasso - λ^♯ ) γ_ Lasso_1≤  ( λ_ Lasso + λ^♯ )γ^♯_1 → 0

   where we used that λ_ Lasso > λ^♯ and λ_ Lassoγ^♯_1 → 0.
      We also know that by the KKT conditions
   
    Σ_-1, -1 ( γ_ Lasso- γ^0) _∞≤λ_ Lasso .

   If
   λ_ Lasso≥ 2 λ^♯, we obtain from the above
   
    λ_ Lassoγ_ Lasso_1 ≤ 
       3 λ_ Lassoγ^♯_1  /2  → 0 .

   So ( γ_ Lasso, λ_ Lasso) is an eligible pair.
   ⊔ -12mu ⊓
   
   .1in
   Proof of Lemma <ref>. 
Note that

    x_-S^T  x_-1γ^-S   =    x_-S^T  [ (  x_-Sγ_-S^0 )  A x_S  ]
       =    x_-S^T  [  x_-S -  x_S Σ_S,S^-1Σ_S,-S ] γ_-S^0 
        =     [ Σ_-S, -S - Σ_-S, SΣ_S,S^-1Σ_S,-S ] γ_-S^0 .
 
We therefore have

    v_-S^S _∞   =    [ Σ_-S, -S - Σ_-S, SΣ_S,S^-1Σ_S,-S ] 
    γ_-S^0 _∞
       ≤   Σ_-S, -S - Σ_-S, SΣ_S,S^-1Σ_S,-S_1 
    γ_-S^0 _∞ .

⊔ -12mu ⊓

Proof of Lemma <ref>. 
We have 

    γ_-S^0 _∞ = λ^S/C ,

so that by Lemma <ref>

    Σ_-1,-1γ^S _∞≤λ^S .

Moreover

    λ^S γ^S _1 ≤λ^S √( s)→ 0 .

Thus ( γ^S , λ^S) is an eligible pair.
Finally

    λ^S γ^0 _1 ≥λ^S γ_-S^0 _1 = κ (γ_-S^0)  C   ↛0 .

⊔ -12mu ⊓

Proof of Lemma <ref>.
  Write
  
    x_-1γ^0 =  x_-1γ^♯ + ξ^0 ,   x_-1^T ξ^0 _∞≤λ^♯.

  It holds that
  
    γ_S^S = Σ_S,S^-1 x_S^T  x_-1γ^0 .

  So
  
    Σ_-1,-1^1/2 ( γ_S^S - γ^♯ ) _2^2    =   
      ( x_S^T ξ^0  )^TΣ_S,S^-1 (  x_S^T ξ^0)  
       ≤    x_S ^Tξ^0 _2 / Λ_ min^2 
       ≤    s x_S^Tξ^0  _∞^2 / Λ_ min^2 → 0 .

  ⊔ -12mu ⊓ 

Proof of Lemma <ref>.

For a ∈ and c ∈^p-1 satisfying a^2 + Σ_-1,-1^1/2 c _2^2=1,

    [ a c ]^T Σ (γ^0) [ a c ]    =     a^2+ 2 a γ^0TΣ_-1,-1 c + c^T Σ_-1,-1 c 
        =    1+ 2 a γ^0TΣ_-1,-1 c 
       ≥    1- 2|a|Σ_-1, -1^1/2γ^0 _2   Σ_-1,-1^1/2 c _2 
       =    1- 2 |a| √(1- a^2)Σ_-1,-1^1/2γ^0 _2 
       ≥    1- Σ_-1,-1^1/2γ^0 _2.
 

But then

    1  a^2 +  c _2^2 [ a c ]^T Σ (γ^0) [ a c ]
       =   a^2 +  Σ_-1,-1^1/2 c _2^2  a^2 +  c _2^2 [ a c ]^T Σ (γ^0) [ a c ]
       ≥    a^2 + Λ_ min^2 (Σ_-1,-1 )  c _2  
     a^2 +  c _2  (1- Σ_-1,-1^1/2γ^0 _2) 
       ≥    (1- Σ_-1,-1^1/2γ^0 _2) Λ_ min^2 (Σ_-1,-1 ) .


Hence Λ_ min^2 (Σ (γ^0)) is positive definite and 

    Λ_ min^2 (Σ (γ^0)) ≥ (1- Σ_-1,-1^1/2γ^0 _2 ) Λ_ min^2  
    (Σ_-1,-1 ) .

It further holds for all j∈{ 2 , … , p } that

    |  x_j^T  x_-1γ^0 |≤√( ( x_-1γ^0 )^2) < 1 .


⊔ -12mu ⊓

Proof of Lemma <ref>.
By definition

    Σ_-1,-1 ( γ^0 - γ^♯ ) = λ^♯ z ,

so that

    Σ_-1,-1 ( γ^0 - γ^♯ ) _∞≤λ^♯ .

Moreover, λ^♯γ^♯_1 ≤λ√( s)γ^♯_2 → 0,
since 

    γ^♯_2 ≤Σ_-1,-1^1/2γ^♯_2 / Λ_ min
    (Σ_-1,-1 ) = 𝒪 (1) .

So ( γ^♯, λ^♯) is an eligible pair.
We further have

    (γ^0 - γ^♯)^T Σ_-1,-1 (γ^0 - γ^♯) = λ^♯2 z^T Σ_-1, -1^-1 z .

Thus

    γ^0TΣ_-1,-1γ^0    =   γ^♯ TΣ_-1-1γ^♯+
    2 ( γ^0 - γ^♯)^T Σ_-1,-1γ^♯ +
    λ^♯2 z^T Σ_-1,-1^-1 z 
       <    1+ o(1)

and 

    1- Σ_-1, -1^1/2γ^0 _2^2 ≫ 0

where the positivity is true for large enough n. 
Therefore, by Lemma <ref>,  γ^0 is eventually allowed.
Finally, 

    λ^♯γ^0 - γ^♯_1 ≥λ^♯ z^T ( γ^0 - γ^♯)
    = λ^♯2 z^T Σ_-1,-1^-1 z ≫ 0 .

So, since λ^♯γ^♯_1 → 0, it must be true that
λ^♯γ^0 _1 ≫ 0.
We in fact have

    γ^0TΣ_-1,-1γ^0 -
    γ^♯ TΣ_-1,-1γ^♯ = λ^♯2 z^T Σ_-1, -1^-1 z + o(1)

 so that

    γ^0TΣ_-1,-1γ^0 -
    γ^♯ TΣ_-1,-1γ^♯≫ 0 .

 
⊔ -12mu ⊓

Proof of Lemma <ref>. 

((a) ⇒) 
For
z_S :=  Σ_S,-SΣ_-S,-S^-1 z_-S
the equality 

    Σ_-1,-1 (γ^0 - γ^♯) = λ^♯ z

holds. By assumption z_-S_∞≤ 1 and by the 
reversed irrepresentable condition also
z_S _∞≤ 1. Thus

    Σ_-1,-1(γ^0 - γ^♯)   _∞≤λ^♯ .


Moreover, 

    λ^♯γ^♯_1 = 
    λ^♯γ_S^0 _1 ≤λ^♯√( s)γ_S^0 _2 → 0 .

 So ( γ^♯ , λ^♯) is eligible.

To see make sure that γ^0 is allowed we bound γ^0TΣ_-1, -1γ^0:

    γ^0TΣ_-1,-1γ^0 ≤γ_S^0TΣ_S,Sγ_S^0 + 2 λ^♯γ_S^0 _1 +
    λ^♯ 2 z_-S^T  Σ_-1,-1^-1 z_-S.

Therefore, since λ^♯γ_S^0 _1→ 0,
and in view of 
Lemma <ref>, the vector γ^0 is for large enough n allowed. 
Finally, we have

    λ^♯γ_0 _1   ≥   λ^♯γ_-S^0 _1
       ≥   λ^♯  z_-S^T γ_-S^0
        =    λ^♯ 2 z_-S^T Σ_-S, -S^-1 z_-S≫ 0.

In fact

    γ^0TΣ_-1,-1γ^0 -
    γ^♯ TΣ_-1,-1γ^♯ = 
     λ^♯ 2 z_-S^T Σ_-S, -S^-1 z_-S+ o(1) ≫ 0 
     .



((b)⇐)
If (γ^♯, λ^♯) is an eligible pair we have

    Σ_-1,-1 ( γ^♯ - γ^0 ) _∞≤λ^♯.

Define now c =  γ^0 - γ^♯ and
z=  Σ_-1,-1^-1 c / λ^♯. 
Then 

    Σ_-1,-1 c = λ^♯ z

 and z _∞≤ 1, c_S=0.
It follows that

    Σ_S,-SΣ_-S,-S^-1 z_-S = z_S

so that

    Σ_S,-SΣ_-S,-S^-1 z_-S_∞≤ 1.

⊔ -12mu ⊓

Proof of Lemma <ref>. 
One readily verifies that
all c_j^0 with j ∉ S are non-zero.  One thus has
the Lagrangrian

    Σ_-1, -1  c^0 = λ̃W ζ

where λ̃ is the Lagrangian parameter.
Since ζ_S =0 this says that

    (Σ_-1,-1 c^0)_S = 0

so we know that x_-1 c^0 is orthogonal to x_S. 

The restriction gives

    Σ_-1,-1^1/2 c^0 _2^2 = λ̃ (W c^0)_-S_∞ = λ̃/ λ^♯ ,

so

    λ̃= λ^♯Σ_-1,-1^1/2 c^0 _2^2  ,

and inserting this back yields

    Σ_-1,-1 c^0 =  λ^♯Σ_-1,-1^1/2 c^0 _2^2 W ζ.

It follows that

    c^0 =λ^♯Σ_-1,-1^1/2 c^0_2^2 Σ_-1,-1^-1 Wζ .

But then

    Σ_-1,-1^1/2 c^0 _2 =λ^♯Σ_-1,-1^1/2 c^0 _2^2 Σ_-1,-1^-1/2 W ζ_2

or

    Σ_-1,-1^1/2 c^0_2 = 1 λ^♯Σ_-1,-1^-1/2 W ζ_2  .

So now we have

    Σ_-1,-1 c^0=  1 λ^♯Σ_-1,-1^-1/2ζ_2^2 W ζ

and hence

    Σ_-1,-1 c^0_∞ =  w_-S_∞λ^♯Σ_-1,-1^-1/2ζ_2^2 .

⊔ -12mu ⊓

Proof of Lemma <ref>.
It holds that

    Σ_-1,-1 (γ^0 - γ^♯ ) =
     x_-1^T  x_-1 (γ^0 - γ^♯) =
     x_-1^T ( x_-S A x_S ) γ_-S^0 = Σ_-1,-1 c^0 .

So 

    Σ_-1,-1 (γ^0 - γ^♯ ) _∞ =  w_-S_∞λ^♯Σ_-1,-1^1/2 Wζ_2^2  =λ^♯ w_-S_∞λ^♯2Σ_-1,-1^1/2W  ζ_2^2 ≤λ^♯
     .

Moreover

    λ^♯γ^♯_1 ≤√( s)γ^♯_2 → 0 .

Thus (γ^♯, λ^♯) is an eligible pair. 
Furthermore

    γ^0TΣ_-1, -1γ^0 =
    γ^♯ TΣ_-1,-1γ^♯ + c^0TΣ_-1,-1 c^0


    = γ^♯ TΣ_-1,-1γ^♯ +
     1 λ^♯2Σ_-1,-1 ^-1/2 W ζ_2^2  .

So by Lemma <ref> γ^0 is allowed. 
Finally, λ^♯γ^0 _1 ≥λ^♯ (W γ^0 )_-S_1 = 1
and in fact

    γ^0TΣ_-1, -1γ^0 -
    γ^♯ TΣ_-1,-1γ^♯ =1 λ^♯2Σ_-1,-1 ^-1/2 W ζ_2^2 ≫ 0  .


⊔ -12mu ⊓



 §.§ Proofs for Section <ref>
 

Proof of Lemma <ref>. 
We recall the notation Σ̂_-1,-1 := X_-1^T X_-1 / n.
The event

    { X_-1^T ϵ^♯_∞ /n ≤λ_ε^♯}∩{inf_c:  λ^ Lasso c _1 ≤ 4 η_n^2  ,  c^T Σ_-1,-1 c = 1  c^T Σ̂_-1,-1 c  ≥1  2}

has probability converging to one so in the rest of the proof we may assume that
we are on this event. 
By the KKT conditions

    Σ̂_-1,-1 ( γ̂- γ^0) = X_-1^T ε / n - λ^ Lassoζ̂

where ζ̂∈∂γ̂_1, with ∂ c _1 the sub-differential of the map
c ↦ c _1. 
Thus

    Σ̂_-1,-1 ( γ̂- γ^♯) = X_-1^T ε^♯ / n - 
    λ^ Lassoζ̂.

Therefore

    ( γ̂- γ^♯)^T Σ̂_-1,-1 ( γ̂- γ^♯)    =    
    ( γ̂- γ^♯)^T X_-1^T ε^♯ / n - λ^ Lasso( γ̂- γ^♯)^Tζ̂
       ≤   λ_ε^♯γ̂- γ^♯_1+ λ^ Lassoγ^♯_1 - λ^ Lassoγ̂_1 
       ≤    ( λ^ Lasso + λ_ε^♯ )
    γ^♯_1- (λ^ Lasso - λ_ε^♯ )γ̂_1 
       ≤    ( λ^ Lasso + λ_ε^♯ )
    γ^♯_1
       ≤    3 λ^ Lassoγ^♯_1 /2 ≤ 3 η_n^2 /2 .

It moreover follows from the above that

    γ̂_1 ≤ ( λ^ Lasso  + λ_ε^♯λ^ Lasso - λ_ε^♯ )  γ^♯_1

 and so 
 
    λ^ Lassoγ̂_1≤λ^ Lasso ( λ^ Lasso + λ_ελ^ Lasso - 
    λ_ε^♯ ) ≤ 3 η_n^2 ,

and also 

    λ^ Lassoγ̂- γ^♯_1 ≤λ^ Lasso (   2λ^ Lassoλ^ Lasso - 
    λ_ε^♯ )  γ^♯_1 ≤ 4 η_n^2   .
 
If Σ^1/2 ( γ̂- γ^♯ )_2 ≤ 2 η_n we are done. 
Otherwise, if Σ^1/2 ( γ̂- γ^♯ )_2 ≥ 2 η_n
it holds that 4 η_n^2 ≤ 2 η_n Σ^1/2 ( γ̂- γ^♯ )_2.
But then

    1  2  ( γ̂- γ^♯)^T  Σ_-1,-1 ( γ̂- γ^♯)    ≤   
    ( γ̂- γ^♯)^T  Σ̂_-1,-1 ( γ̂- γ^♯) 
       ≤    (λ^ Lasso + λ_ε^♯ )
    γ^♯_1 
       ≤    2 λ^ Lassoγ^♯_1  ≤ 2 η_n^2 .

⊔ -12mu ⊓

Proof of Theorem <ref>.
We rewrite

    β̂_1 - β_1^0 = Θ̂_1 X^T ϵ / n +
    ( e_1^T - Θ̂_1^T Σ̂) ( β̂- β^0) _ remainder .

By the KKT conditions

    e_1^T - Θ̂_1^T Σ̂_∞≤λ^ Lasso/( X_1 - X_-1γ̂_2^2 / n +
     λ^ Lassoγ̂_1  ).

 But by Lemma <ref>
 
    X_1 - X_-1γ̂_2^2 / n +
     λ^ Lassoγ̂_1 =
     (  x_1 -  x_-1γ^♯ )^2 + o(1)

 which stays away from zero.
 Moreover, by assumption, √(n)λ^ Lassoβ̂- β_0 _1 = o__β^0 (1)
 uniformly in β^0 ∈ B. 
 Thus, for the remainder we find

    |  ( e_1^T - Θ̂_1^T Σ̂) ( β̂- β^0) |≤ e_1^T - Θ̂_1^T Σ̂_∞β̂- β^0 _1 = o__β^0 ( 1/ √(n) )

uniformly in β^0 ∈ B.
For the main term, we have after standardization

    Θ̂_1^T X^T ϵ /√(n)√(Θ̂_1^T Σ̂Θ̂_1)∼ N (0,1) .

It further holds that  Θ̂_1^T Σ̂Θ̂_1 = Θ_1,1^♯ + o_ (1)
by Lemma <ref>.
which stays away from zero.
Therefore, for  the standardized remainder term

    √(n)  |  ( e_1^T - Θ̂_1^T Σ̂) ( β̂- β^0) | √(Θ̂_1^T Σ̂Θ̂_1) = o__β^0 (1 )

uniformly in β^0 ∈ B. 
The final result thus follows from Slutsky's Theorem.
⊔ -12mu ⊓





§ PROBABILITY INEQUALITIES


In this section we present some probability inequalities for products of Gaussians.
Such results are known (for example as Hanson-Wright inequalities for sub-Gaussians, see 
<cit.>) and only presented here for completeness. 

  Let U and W be two independent N (0,1)-distributed random variables.
   Then for all L > 1
   
    exp [ UW  L ] ≤exp [ 1  2 L^2 - 2L  ] .

   
   
   Proof. We have for L>1
   
    exp [ UW  L  ]    ≤   exp [ (U + W)^2 -(U-W)^2   4L  ]
        =    exp [ (U+W)^2-2  4L ] exp [  2- (U-W)^2   4L ] 
       =    exp [ (U+W)^2-2  4L ] exp [ 2-(U-W)^2   4L ] 
       ≤   exp [ 1  4L^2 - 4L ]  exp [ 2-(U-W)^2   4L ] .

 (see Lemma 1 and its proof in <cit.>) or  Section  8.4 in <cit.>).
  But
  
    exp [ 2-(U-W)^2   4L ]    =    1 √(2 π)∫exp [ 1-v^2  2L ] exp [ 
       -  v^2  2  ]  dv 
        =    exp [  1  2L ] 1 √(2 π)∫exp [ - 1  2 ( 1+ 1  L ) v^2 
        ]  dv 
        =    exp [  1  2L ]  ( 1+ 1  L )^-1/2
       =    exp [ 1  2L - 1  2log (1+ 1/L )   ] .

   Since
   
    log (1+ 1/L) ≥  1/L -   12   (1/L^2 )

   we obtain
   
    exp [ 2-(U+W)^2   4L ]    ≤   exp [ 1  4 L^2  ] 
       ≤   exp [  1  4L^2 - 4L  ] .

 It follows that
 
    exp [ UW   L  ]  ≤exp [ 2  4L^2 - 4L ]  
     =  exp [ 1  2L^2 - 2L ] .

 ⊔ -12mu ⊓ 
  
   Let U= (U_1 , … , U_n)^T and W= (W_1 , … , W_n)^T be two independent
standard Gaussian n-dimensional random vectors.
Then for all t >0

    ( U^T W /n ≥√(2t/n) +  t/n  ) ≤exp [-t] .

 
 
 Proof. By Lemma <ref> and using the independence
 
    exp [  U^T W    L ] ≤exp [ n  2L^2 - 2L ].

 This gives for all t>0
 
    ( U^T W ≥√(2nt) +  t  ) ≤exp [-t]

 (see e.g.  Lemma 8.3 in <cit.>).
 ⊔ -12mu ⊓ 
   
    Let { (U_i, V_i) }_i=1^n be i.i.d. two-dimensional Gaussians with mean zero.
    Suppose var (U_1) =1. Define λ^♯ :=  U_1V_1 and
   σ^♯ 2=  V_1^2.  Then for all t >0
   
    ( U^T V / n ≥λ^♯ + ( √(2)σ^♯ + 2λ^♯) √(t/n) +
       ( σ^♯ + 2 λ^♯) t/n  ) ≤ 2 exp[-t] .


   
   
   
   Proof. For all i the projection of V_i on U_i is [ U_iV_i /  var  (U_i) ] U_i = λ^♯ U_i. Hence
   we may write for all i
   
    V_i = λ^♯ U_i + W_i ,

   where W_i is a zero-mean Gaussian random variable independent of U_i. It follows
   that
   
    U^T V/n  = λ^♯ U _2^2 /n + U^T W/n .

   Since var ( W_i ) ≤σ^♯2 for all i we see from Lemma <ref>
   that
   
    ( U^T W / n ≥√(2)σ^♯√( t/n) + σ^♯ t/n  ) ≤exp [-t] .

   Moreover (see Lemma in <cit.>, also given in <cit.> as Lemma 8.6)
   
    (  U _2^2/n  -1 ≥ 2 √(t/n) + 2 t/n  ) ≤exp[-t] .

   Thus
   
    ( U^T V / n ≥λ^♯ + (  √(2)σ^♯ + 2 λ^♯) √(t/n) +
       ( σ^♯ + 2 λ^♯) t/n  ) ≤ 2 exp[-t] .

   ⊔ -12mu ⊓ 


   
   


















plainnat




