A Flexible Framework for Hypothesis Testing in High-dimensions
Adel Javanmard∗ and Jason D. Lee†

arXiv:1704.07971v1 [math.ST] 26 Apr 2017

April 27, 2017

Abstract
Hypothesis testing in the linear regression model is a fundamental statistical problem. We
consider linear regression in the high-dimensional regime where the number of parameters exceeds the number of samples (p > n) and assume that the high-dimensional parameters vector
is s0 sparse. We develop a general and flexible `∞ projection statistic for hypothesis testing in
this model. Our framework encompasses testing whether the parameter lies in a convex cone,
testing the signal strength, testing arbitrary functionals of the parameter, and testing adaptive
hypothesis. We show that
√ the proposed procedure controls the type I error under the standard
assumption of s0 (log p)/ n → 0, and also analyze the power of the procedure. Our numerical
experiments confirms our theoretical findings and demonstrate that we control false positive
rate (type I error) near the nominal level, and have high power.

1

Introduction

Consider the high-dimensional regression model where we are given n i.i.d. pairs (y1 , x1 ), (y2 , x2 ),
· · · , (yn , xn ) with yi ∈ R, and xi ∈ Rp , denoting the response values and the feature vectors,
respectively. The linear regression model posits that response values are generated as
wi ∼ N(0, σ 2 ) .

yi = hθ0 , xi i + wi ,

(1)

Here θ0 ∈ Rp is a vector of parameters to be estimated and h · , · i is the standard scalar product.
In addition, noise wi is independent of xi . In matrix form, letting y = (y1 , . . . , yn )T and denoting
T
by X the matrix with rows xT
1 ,· · · , xn we have
y = X θ0 + w ,

w ∼ N(0, σ 2 In×n ) .

(2)

We are interested in high-dimensional models where the number of parameters p may far exceed
the sample size n. Our goal in this paper is to understand various parameter structures of the highdimensional model. Specifically, we develop a flexible framework for testing null hypothesis of the
form
H0 : θ0 ∈ Ω0

versus

HA : θ0 ∈
/ Ω0 , ,

(3)

for a general set Ω0 ⊂ Rp . We make no restricting assumption (such as convexity or connectedness)
on Ω0 . We also allow for adaptive tests where the set Ω0 depends on the observed samples (yi , xi ),
1 ≤ i ≤ n.
∗
†

Data Sciences and Operations Department, University of Southern California. Email: ajavanma@usc.edu
Data Sciences and Operations Department, University of Southern California. Email: jasonlee@marshall.usc.

edu

1

1.1

Motivation

High-dimensional models are ubiquitous in many areas of applications. Examples range from signal
processing (e.g. compressed sensing), to recommendation systems (collaborative filtering), to statistical network analysis, to predictive analytics. The widespread interest in these applications has
spurred remarkable progress in the area of high-dimensional data analysis [CT07, BRT09, BvdG11].
Given that the number of parameters goes beyond the sample size, there is no hope to obtain reasonable estimate without making further assumption on the structure of model parameters. A
natural such assumption is sparsity, which posits that only s0 of the parameters θ0,i are nonzero,
and s0 ≤ n.
A prominent approach in this setting is the Lasso estimator [Tib96, CD95] defined by


1
n
2
b
θ (y, X; λ) ≡ arg maxp
(4)
ky − Xθk2 + λkθk1 .
θ∈R
2n
(We will omit the arguments of θbn (y, X; λ) whenever clear from the context.)
To date, the majority of work on high-dimensional parametric models has focused on point
estimation such as consistency for prediction [GR04], oracle inequalities and estimation of parameter vector [CT07, BRT09, RWY09], model selection [MB06, ZY06, Wai09], and variable screening [FL08]. However, the fundamental problem of statistical significance is far less understood in
the high-dimensional setting. Uncertainty assessment is particularly important when one seeks
subtle statistical patterns about the model parameters θ0 .
Below, we discuss some important examples of high-dimensional inference that can be performed
provided a methodology for testing hypothesis of form (3).
Example 1 (Testing θmin condition) Support recovery in high-dimension concerns the problem of finding a set Ŝ ⊆ {1, 2, . . . , p}, such that P(Ŝ = S) is large, where S ≡ {i : θ0,i 6= 0, 1 ≤
i ≤ p}. Work on support recovery requires the nonzero parameters be large enough to be detected. Specifically,
p for exact support recovery meaning that P(Ŝ 6= S) → 1, it is assumed that
mini∈S |θ0,i | = Ω( (log p)/n). This assumption is often referred to as θmin condition and is shown
to be necessary for exact support recovery [MY09, ZY06, FL01, ZY06, Wai09, MB06].
Relaxing the task of exact support recovery, let α and β be the type I and type II error rates in
detecting nonzero (active) parameters of the model. In [JM14b], it is shown that even for gaussian
design matrices, any hypothesis testing method that achieve nontrivial power 1 − β > α requires
√
mini∈S |θ0,i | = Ω(1/ n). Despite θmin assumption is commonplace, it is not verifiable in practice
and hence it calls for developing methodologies that can test whether such condition holds true.
For a vector θ ∈ Rp , define support of θ as supp(θ) = {1 ≤ i ≤ p : θi 6= 0}. In (3), letting
Ω0 = {θ ∈ Rp : mini∈supp(θ) |θi | ≥ c}, we can test θmin condition for any given c ≥ 0 and at a
pre-assigned significance level α.
Example 2 (Confidence intervals for quadratic forms) We can apply our method to test
hypothesis of form
H0 : kQθ0 k2 ∈ Ω0 ,

(5)

for some given set Ω0 ⊆ [0, ∞) and a given matrix Q ∈ Rp×p . By duality between hypothesis testing
and confidence interval, we can also construct confidence intervals for quadratic forms kQθ0 k.
2

In the case of Q = I, this yields inference on the signal strength kθk22 . As noted in [JBC16],
armed with such testing method one can also provide confidence intervals for the estimation error,
b 0 k. Specifically, we split the collected samples into two independent groups (y (0) , X (0) )
namely kθ−θ
(1)
b
and (y , X (1) ), and construct an estimate θb just by using the first group. Letting ỹ ≡ y (1) − X (1) θ,
(1)
b
b
we obtain a linear regression model ỹ = X (θ0 − θ) + w. Further, if θ is a sparse estimate, then
θ0 − θb is also sparse. Therefore, inference on the signal strength on the obtained model is similar
b
to inference on the error size kθ0 − θk.
Inference on quadratic forms turns out to be closely related to a number of well-studied problems, such as estimate of the noise level σ 2 and the proportion of explained variation [FGH12,
BEM13, D+ 14, JBC16, VG16]. To expand on this point, suppose that attributes xi are drawn
i.i.d. from a gaussian distribution with covariance Σ, and the noise level σ 2 is unknown. Then,
Var(yi ) = σ 2 + kΣ1/2 θ0 k22 . Since kyk22 /Var(yi ) follows a χ2 distribution with n degrees of freedom,
we have kyk22 /n = Var(yi )[1+OP (n−1/2 )]. Hence, task of inference on the quadratic form kΣ1/2 θ0 k22
and the noise level σ 2 are intimately related. This is also related to the proportion of explained
variation defined as
η(θ0 , σ) =

E(hxi , θ0 i2 )
µ
=
,
Var(yi )
1+µ

(6)

with µ = (1/σ 2 )kΣ1/2 θ0 k2 the signal-to-noise ratio. This quantity is of crucial importance in genetic
variability [VHW08] as it somewhat quantifies the proportion of variance in a trait (response) that
is explained by genes (design matrix) rather than environment (noise part).
Example 3 (Testing individual parameters θ0,i ) Recently, there has been a significant
interest in testing individual hypothesis H0,i : θi = 0, in high-dimensional regime. This is a
challenging problem because obtaining an exact characterization of the probability distribution of
the parameter estimates in high-dimensional regime is notoriously hard.
A successful approach is based on debiasing the regularized estimators. The obtained debiased estimator is amenable to distributional characterization which can be used for inference on
individual parameters [JM14a, JM14b, ZZ14, VdGBRD14, JM13]. Our methodology for testing
hypothesis of form (3) is built upon the debiasing idea. It also recovers the debiasing approach for
Ω0 = {θ ∈ Rp : θi = 0}.
Example 4 (Confidence intervals for predictions) For a new sample xnew , we can perform
inference on the response value hxnew , θ0 i by letting Ω0 = {θ : hxnew , θ0 i = η} for a given value η.
Further, by duality between hypothesis testing and confidence intervals, we can construct confidence
interval for hxnew , θ0 i. We refer to Section 5.2 for further details.
Example 5 (Confidence intervals for f (θ0 )) Let f : Rp → R be an arbitrary function.
By letting Ω0 = {θ : f (θ0 ) = η} we can test different values of f (θ0 ). Further, by employing
the duality relationship between hypothesis testing and confidence intervals, we can construct
confidence intervals for f (θ0 ). Note that Example 3, 4 are special cases of f (θ0 ) = hei , θ0 i and
f (θ0 ) = hxnew , θ0 i. Here ei is the i-th standard basis element with one at the i-th entry and zero
everywhere else.
Example 6 (Testing over convex cones) For a given cone C, our framework allows us to
test whether θ0 belongs to C. Some examples that naturally arise in studying treatment effects are
3

nonnegative cone C≥0 = {θ ∈ Rp : θi ≥ 0 for all 1 ≤ i ≤ p}, and monotone cone CM = {θ ∈ Rp :
θ1 ≤ θ2 ≤ . . . ≤ θp }. Letting θi denote the mean of treatment i, by testing θ0 ∈ C≥0 , one can test
whether all the treatments in the study are harmless. Another case is when treatments correspond
to an ordered set of dosages of the same drug. Then, one might reason that if the drug is of any
effect, its effect should follow a monotone relationship with its dosage. This hypothesis can be cast
as θ0 ∈ CM . Such testing problems over cones have been studied for gaussian sequence models
by [Kud63, RW78, RCLN86], and very recently by [WWG17].

1.2

Summary of main results

Our methodology is built upon the fundamental ida of debiasing developed in [JM14a, JM14b,
ZZ14, VdGBRD14]. In this approach, a debiased (or desparsified) estimator is constructed that
takes the form
1
θbd = θbn + M X T (y − X θbn ) .
n

(7)

The de-correlating matrix M is a function of design X but not the response y. There are several
proposals for constructing M , but the underlying idea behind all of them is that M Σ − I should
b = (X T X)/n denotes the sample covariance.
small where Σ
√
Under some technical assumptions, and assuming that s0 = o( n/ log p), it is shown that θbd is
asymptotically unbiased and admits a gaussian distribution. (We refer to [JM14a, Theorems 2.3,
2.5] for formal results.) In addition, it was shown that for gaussian designs, a similar result can be
obtained under weaker assumption that s0 = o(n/(log p)2 ) [JM15].
In order to test hypothesis (3), we compute an `∞ projection pursuit using the debiased estimator. Specifically, let
θbp =

kD(θbd − θ)k∞

argmin
θ∈Rp

(8)

subject to θ ∈ Ω0
Here D is a diagonal matrix of size p, whose choice will be discussed shortly.
Our test statistics is then the optimal value of the above optimization:
Tn = kD(θbd − θp )k∞ .

(9)

We then reject null hypothesis H0 only if Tn > tc , for a critical value tc .
We consider two cases: (i) nonadaptive hypothesis, where the set Ω0 is fixed a priori and
statistically is independent of collected samples (yi , xi ), 1 ≤ i ≤ n; (ii) adaptive hypothesis, where
the set Ω0 can be chosen after observing the samples.
The contributions of this paper are organized as follows:
1. We provide a testing methodology under both cases that controls false positive rate under a
pre-assigned α level.
In case of adaptive hypothesis, we set Dii as the reciprocal of the standard deviation of θbid ,
(n)
b T . We propose an analytical form for the
namely diag({Qii }−1/2 ), where Q ≡ (σ 2 /n)M ΣM
critical value tc in this case.
√
In case of non-adaptive hypothesis, we set D = nI. Here, we improve the power of the test
by using Monte Carlo simulations in determining the critical value tc .
4

2. We derive an analytical lower bound for the statistical power of our test. In case of Ω0 =
{θ ∈ Rd : θ0,i = 0} (Example 3), it matches the bound proposed in [JM14a, Theorem 3.5],
which is also shown to be minimax optimal.
3. We use duality between hypothesis testing and confidence intervals to derive confidence intervals for function value f (θ0 ) for an arbitrary f . In case of linear functions, we show that
the length of proposed interval achieves the optimal rate established in [CG15].
4. We discuss examples in the introduction in further details and provide several numerical
experiments to validate our testing methodology.

1.3

Other Related work

Testing in the high-dimensional linear model has experienced a resurgence in the past few years.
Most closely related to us is the line of work on debiasing/desparsifying pioneered by [ZZ14,
VdGBRD14, JM14a]. These papers propose a debiased estimator θbd such that every coordinate θbid
is approximately Gaussian under the condition that s20 (log p)/n → 0, which is in turn used to test
single coordinates of θ0 , H0 : θ0,i = 0, and construct confidence intervals for θ0,i . In a parallel line
of work, [BCH11b, BCFVH13, BCH11a, BCH14] have also designed an asymptotically Gaussian
pivot via the post-double-selection lasso, under the same sample size condition of s20 (log p)/n → 0.
[CG15] established that the sample size conditions required by debiasing and post-double-selection
√
are minimax optimal meaning to construct a confidence interval of length O(1/ n) for a coordinate
of θ0 requires s20 (log p)/n → 0.
The debiasing and post-double-selection approaches have also been applied to a wide variety of
other models for testing θ0,i including missing data linear regression [WWBS17], quantile regression
[ZKL14], and graphical models [RSZ+ 15, CRZZ16, WK16, BK15].
In the multiple testing realm, the FDR-thresholding and SLOPE procedures controls the false
discovery rate (FDR) when the design matrix X is orthogonal [SC16, BvdBS+ 15, ABDJ06]. In
the non-orthogonal setting, the knockoff procedure [BC14] controls FDR whenever n ≥ 2p, and
the noise is isotropic; In [JS15], knockoff was generalized to also control for the family-wise error
rate. More recently, [CFJL16] developed the model-free knockoff which allows for p > n when the
distribution of X is known.
In parallel, there have been developments in selective inference, namely inference for the variables that the lasso selects. [LSS+ 16, TTLT16] developed exact tests for the regression coefficients
corresponding to variables that lasso selects. This was further generalized to a wide variety of
polyhedral model selection procedures including marginal screening and orthogonal matching pursuit in [LT14]. [TT15, FST14, HPM+ 16] developed more powerful and general selective inference
procedures by introducing noise in the selection procedure. To allow for selective inference in the
high-dimensional setting, [LSS+ 16, Lee15] combined the polyhedral selection procedure with the
√
debiased lasso to construct selectively valid confidence intervals for θ0,i when s0 (log p)/ n → 0.
Much of the previous work has focused on testing coordinates or 1-dimensional projections of θ0 .
Our work increases the applicability of the debiasing approach by allowing for general hypothesis,
θ0 ∈ Ω0 . The set Ω0 can be adaptive (meaning that it depends on the collected samples (yi , xi )),
con-convex or even disconnected. Our setup encompasses a broad range of testing problems. Of
course, we do not expect our methodology to be optimal in all of these problems but its applicability
is very broad.

5

1.4

Organization of the paper

Section 2 is devoted to notations and preliminary lemmas. We also provide a self-contained overview
on the debiasing approach. In Section 3, we explain our testing methodology and discuss the case
of adaptive and non-adaptive hypothesis separately. Our testing method for the two cases are quite
similar. For non-adaptive hypothesis we use Monte Carlo calibration to improve the statistical
power. We present our main results in Section 4. Some applications of our framework are discussed
in Section 5. We provide numerical experiments in Section 6 to corroborate our findings and
evaluate type I error and statistical power of our test under various settings. Proof of Theorems
are given in Section 7, while the proof of technical lemmas are deferred to appendices.

2

Preliminaries and notations

We start by adapting some simple notations that will be used throuoght the paper, along with
some basic definitions from the literature on high-dimensional regression.
We use ei to refer to the i-th standard basis element, e.g., e1 = (1, 0, . . . , 0). For a vector v,
supp(v) represents the positions of nonzero entries of v. For a vector θ and a subset S, θS is the
restriction of θ to indices in S. For an integer p ≥ 1, we usePthe notation [p] = {1, · · · , p}. We
write kvkp for the standard `p norm of a vector v, i.e., kvkp = ( i |vi |p )1/p and kvk0 for the number
of nonzero entries of v. Whenever the subscript p is not mentioned it should be read as `2 norm.
For a matrix A, we denote by |A|∞ ≡ maxi≤m,j≤n |Aij |, the maximum absolute value of entries of
A. Further, its maximum and minimum
values
are respectively indicated by by σmax (A)
√
R x singular
2
and σmin (A). Throughout, Φ(x) ≡ −∞ e−t /2 dt/ 2π denotes the CDF of the standard normal
distribution. Finally, with high probability (w.h.p) means with probability converging to one as
n → ∞ and for two functions f (n) and g(n), the notation f (n) = o(g(n)) means that g ‘dominates’
f asymptotically, namely, for every fixed positive C, there exists n(C) such that f (n) ≤ Cg(n) for
n > n(C). We use oP ( · ) to indicate asymptotic behavior in probability as the sample size n tends
to infinity.
b = (X T X)/n ∈ Rp×p be the sample covariance of the design X ∈ Rn×p . In the highLet Σ
b is singular. As common in high-dimensional statistics,
dimensional setting, where p exceeds n, Σ
b to be nonsingular in a restricted set of directions.
we assume compatibility condition which requires Σ
We use the notation k · kψ2 to refer to the subgaussian norm. Specifically, for a random variable
X, we let
kXkψ2 = sup q −1/2 (E|X|q )1/q .
q≥1

For a random vector X ∈

Rm ,

its subgaussian norm is defined as
kXkψ2 = sup khX, xikψ2 .
kxk≤1

Definition 2.1. For a symmetric matrix J ∈ Rp×p and a set S ⊆ [p], the compatibility condition
is defined as
φ2 (J, S) ≡ minp
θ∈R

n |S|hθ, Jθi
kθS k21

o
θ ∈ Rp , kθS c k1 ≤ 3kθS k1 .

:

(10)

Matrix J is said to satisfy compatibility condition for a set S ⊆ [p], with constant φ0 if φ(J, S) ≥ φ0 .
6

2.1

Debiased estimator

Characterizing the distribution of Lasso estimator for general design matrix is notoriously hard.
Further, due to the `1 penalization, Lasso estimator is biased towards small `1 norm. The fundamental idea of de-biasing developed in [JM14a, JM14b, ZZ14, VdGBRD14, JM13] is to start with
Lasso and remove its bias, approximately. This results in debiased (or de-sparsified) estimator that
takes the form
1
θbd = θbn + M X T (y − X θbn ) .
(11)
n
Here M ∈ Rp×p is a matrix that is a function of X, but not of y. Various constructions of M
have been offered by different works, but the basic insight is that M should act as a de-correlating
matrix. In other words, it should be a good estimate of the precision matrix Ω = Σ−1 , where
Σ = E{x1 xT
1 } is the population covariance.
In this paper, we follow the recipe of [JM14a] for the choice of M . For 1 ≤ i ≤ p, let mi be a
solution of the convex program:
b
mT Σm
b − ei k∞ ≤ µ
subject to kΣm

minimize

(12)

Then, set M = (m1 , m2 , . . . , mp )T .
The parameter µ controls the trade-off between the bias and the variance of each coordinate
of θbd . It should be chosen large enough such that optimization (12) is feasible. In this regard, we
recall the definition of generalized coherence, provided in [JM14a].
b = (X T X)/n be the sample
Definition 2.2. Given the pair X ∈ Rn×p and M ∈ Rp×p , let Σ
covariance of X. The generalized coherence parameter of X, M denoted by µ∗ (X; M ) is given by
b − I|∞ .
µ∗ (X; M ) ≡ |M Σ

(13)

The minimum generalized coherence of X is µmin (X) = minM ∈Rp×p µ∗ (X; M ).
By choosing µ ≥ µmin (X), optimization (12) becomes feasible.
For random designs, defined below, there is an explicit upper bound for the minimum generalized
coherence that holds with high probability with respect to the randomness in the design.
Proposition 2.3 ( [JM14a]). Let Σ ∈ Rp×p be such that σmin (Σ) ≥ Cmin > 0 and σmax (Σ) ≤
Cmax < ∞ and maxi∈[p] Σii ≤ 1. Suppose that XΣ−1/2 has independent subgaussian rows, with
mean zero and subgaussian norm kΣ−1/2 x1 kψ2 = κ, for some constant κ > 0. For constant a > 0,
define
r
n
log p o
n×p
Gn (a) ≡ X ∈ R
: µmin (X) < a
.
(14)
n
p
In other words, Gn (a) is the event that problem (12) is feasible for µ = a (log p)/n. Then, for
n ≥ a2 Cmin log p/(4e2 Cmax κ4 ), the following holds true with high probability
a2 Cmin
− 2.
(15)
24e2 κ4 Cmax
p
By Proposition 2.3, for subgaussian design we set µ = a (log p)/n for an arbitrary but fixed
constant a > 0.
P(X ∈ Gn (a)) ≥ 1 − 2p−c2 ,

7

c2 =

3
3.1

Projection statistic
Adaptive hypotheses

Let Ω0 be an arbitrary set in Rp that can be constructed after observing the collected samples.
Without loss of generality, we assume that Ω0 = Π(S × Rp−k ), for some S ⊂ Rk , an integer
1 ≤ k ≤ p and a permutation Π. For notational convenience, we will omit the permutation, since
the arguments do not change.
In order to obtain an estimate of the measurement noise level σ 2 , we use the scaled Lasso [SZ12]
given by


1
σ
n
2
b
{θ (λ), σ
b(λ)} = arg min
(16)
ky − Xθk2 + + λkθk1 .
2
θ∈Rp ,σ>0 2σn
This optimization
simultaneously gives an estimate of θ0 and σ. We use regularization parameter
p
λ = 10 (2 log p)/n.
We compute the debiased estimator given by (11), with M is chosen by solving optimization (12).
We define
Q(n) ≡

σ
b2
b T) ,
(M ΣM
n

(17)

(n)

and let D(n) ≡ diag({Qii }−1/2 ). To ease the notation, we hereafter drop the superscript (n). We
next construct a test statistic Tn so that the large values of Tn provide evidence against the null
hypothesis. Our test statistic is defined based on an `∞ projection estimator given by the following
optimization problem.
θbp =

argmin
θ∈Rp

kD(θbd − θ)k∞
(18)

subject to θ ∈ Ω0 and θS c

= θbSd c .

We then define the test statistic to be the optimal value of (18), i.e.,
Tn = kD(θbd − θbp )k∞
The decision rule is then based on the test statistic:



−1 1 − α

1
if
T
≥
t
≡
Φ
(reject H0 )

n
c

2k
RX (y) =


0 otherwise
(fail to reject H0 ).

(19)

(20)

The above procedure generalizes the debiasing approach of [JM14a]. Define Ω0 = {θ : θ1 = 0} =
{0} × Rp−1 . We see that Tn = kθbd − θbp k∞ = |θb1d |. Thus the test RX (y) rejects if Tn ≥ φ−1 (1 − α2 ),
which is precisely the same rejection rule as in [JM14a].
In Section 7.1, we prove that decision rule (20) controls false positive rate below the target level
α. However, it might be conservative for some settings in that it controls false positive rate at a
smaller level than α. In next section, we consider a broad class of non-adaptive hypothesis and
argue how to modify the decision rule to make it less conservative and improve its power.
8

3.2

Non-adaptive hypotheses

Suppose that Ω0 is fixed a priori and is statistically independent of the samples. Further, assume
that the set Ω0 is closed under addition, meaning if θ1 , θ2 ∈ Ω0 , then θ1 + θ2 ∈ Ω0 . For instance,
all convex cones are closed under addition.
In this section, we design a Monte Carlo calibration scheme to set the critical value tc .
Let D = I, so that our test statistic simplifies to
θbp =

argmin
θ∈Rp

kθbd − θk∞
(21)

subject to θ ∈ Ω0 and θS c = θbSd c .
We then construct the test statistic as following
√
Tn = n kθbd − θbp k∞

(22)

For a vector v ∈ Rp , we denote by PΩ∞0 (v), with a slight abuse of notation, the `∞ projection of
b T ), we let
v onto Ω0 ∩ {θ : θS c = θbSd c }. For t ≥ 0 and Z ∼ N(0, σ
bM ΣM

ΦZ,Ω0 (t) = P kZ − PΩ∞0 (Z)k∞ > t ,
for t ≥ 0 .
The quantity ΦZ,Ω0 (t) does not admit an analytical form but be computed via Monte Carlo
calibration. The rejection rule is

−1

(reject H0 )
1 if Tn ≥ tc ≡ ΦZ,Ω0 (α) + 0.001
RX (y) =
(23)


0 otherwise
(fail to reject H0 ).
The steps of our testing framework are summarized in Algorithm 1.

4

Main results

We take a minimax perspective and require that the probability of type I error (false positive) to
be controlled uniformly over s0 -sparse vectors.
For a test R : Rn → {0, 1} and a set Ω0 , we define
n
o
αn (R) ≡ sup Pθ0 (R = 1) : θ0 ∈ Ω0 , kθ0 k0 ≤ s0 (n) .
(28)
Our first result shows validity of our test for general adaptive set Ω0 under deterministic designs.
Theorem 4.1. Consider a sequence of design matrices X ∈ Rn×p , with dimensions n → ∞, p =
b = (X T X)/n
p(n) → ∞ satisfying the following assumptions. For each n, the sample covariance Σ
satisfies compatibility condition for the set S0 = supp(θ0 ), with a constant φ0 > 0. Also, assume
b ii for some constant K > 0.
that K ≥ maxi∈[p] Σ
Consider
linear model (2), and let θbn and σ
b be obtained by scaled Lasso, given by (16), with
p
λ = c (log p)/n. Further, form a debiased estimator as in (11) using µ ≥ µmin (X), where µmin (X)
is the minimum generalized
coherence parameter as per Definition 2.2. Choose c > 32K and suppose
√
that s0 = o(1/(µ log p), n/log p).
For the test RX defined in Equation (20), and for any α ∈ [0, 1], we have
lim sup αn (RX ) ≤ α .
n→∞

9

(29)

Algorithm 1 Testing algorithm for closed sets with Monte Carlo calibration.
Input: Measurement vector y, design matrix X, null set Ω0 , tuning parameter µ.
Output: Validptesting framework.
1: Set λ = 10 (2 log p)/n.
bn = θbn (Y, X; λ) and σ
2: Let θ
b be obtained by scale Lasso as per Eq. (16).
T
b
3: Set Σ ≡ (X X)/n.
4: for i = 1, 2, . . . , p do
5:
Let mi be a solution of the convex program:
b
mT Σm
b − e i k∞ ≤ µ ,
subject to kΣm
minimize

(24)

where ei ∈ Rp is the vector with one at the i-th position and zero everywhere else.
6: Set M = (m1 , . . . , mp )T . If any of the above problems is not feasible, then set M = Ip×p .
bd as follows:
7: Define the estimator θ
1
θbd = θbn (λ) + M X T (Y − X θbn (λ))
n
8:

(25)

Compute `∞ projection of θbd onto set Ω0 :
θbp =

argmin
θ∈Rp

kθbd − θk∞
(26)

subject to θ ∈ Ω0 and θS c = θbSd c .
√
Compute the test statistic Tn = nkθbd − θbp k∞ .
b T ), and let Z̄b = Zb − P ∞ (Zb ).
10: Draw B samples Zb ∼ N (0, σ
bM ΣM
Ω0
−1
11: Approximate ΦZ,Ω (α) as the 1 − α quantile of the sample {Z̄b }B
b=1
0
12: return The rejection rule is

−1

(reject H0 )
1 if Tn ≥ tc ≡ ΦZ,Ω0 (α) + 0.001
RX (y) =


0 otherwise
(fail to reject H0 ).
9:

10

(27)

We next prove validity of our test for general adaptive set Ω0 underrandom designs.
Theorem 4.2. Let Σ ∈ Rp×p such that σmin (Σ) ≥ Cmin > 0 and σmax (Σ) ≤ Cmax < ∞ and
maxi∈[p] Σii ≤ 1. Suppose that XΣ−1/2 has independent subgaussian rows, with mean zero and
subgaussian norm kΣ−1/2 x1 kψ2 = κ, for some constant κ > 0. Consider linear model (2), and let
p
θbn and σ
b be obtained by scaled Lasso,
given
by
(16),
with
λ
=
c
(log p)/n. Further, form a debiased
p
√
estimator as in (11) with µ = a (log p)/n. Choose c > 32K and suppose that s0 = o( n/log p).
For the test RX defined in Equation (20), and for any α ∈ [0, 1], we have
lim sup αn (RX ) ≤ α .

(30)

n→∞

Theorem 4.2 follows readily by putting together Proposition 2.3 and Theorem 4.1. We give its
proof in Section 7.2.
Our next result is about validity of Algorithm 1 for non-adaptive null hypothesis.
Theorem 4.3. Let Ω0 ⊂ Rp be a non-adaptive set. Under the assumptions of Theorem 4.1 for
deterministic designs (or assumptions of Theorem 4.2 for random designs), for the testing method
given by Algorithm 1 we have
lim sup αn (RX ) ≤ α .

(31)

n→∞

Proof of Theorem 4.3 is given in Section 7.3.

4.1

Statistical Power

We next analyze the statistical power of our test. Before proceeding, note that without further
assumption, we cannot achieve any non-trivial power, namely, power of α which is obtained by a
rule that randomly reject null hypothesis with probability α). Indeed, by choosing θ0 ∈
/ Ω0 but
arbitrarily close to Ω0 , once can make H0 essentially indistinguishable from HA . Another point to
note is that we can in general construct the project pursuit test statistics using other norms than
`∞ in (19). The choice of norm should naturally depend on the alternative hypothesis to achieve
statistical power. For instance if the alternative hypothesis is in `2 norm, θ0 can have a large `2
distance to Ω0 , but the corresponding test statistic is not large enough because it is `∞ norm.
Taking the above points into account, for a set Ω ⊆ Rp and θ ∈ Rp , we define the distance
d(θ, Ω) as
d(θ, Ω) = inf kθ − vk∞ .
v∈Ω

We will assume that, under alternative hypothesis, d(θ0 , Ω0 ) ≥ γ as well. Define
n
o
βn (R) ≡ sup Pθ0 (R = 0) : kθ0 k0 ≤ s0 (n), d(θ0 , Ω0 ) ≥ γ

(32)

(33)

Quantity βn is the probability of type II error (false negative) and 1 − βn is the statistical power
of the test.

11

Theorem 4.4. Let RX be the test defined in Equation (20). Under the conditions of Theorem 4.1,
for all α ∈ [0, 1]:
lim inf
n→∞

1 − βn (RX )
≥ 1,
G(α/k, mQ γ, k)

(34)

−1/2

where mQ = mini∈S Qii , with Q given by (17). Further, for α ∈ [0, 1], u ∈ R+ , and integer
k ≥ 1, the function G(α, u, k) is defined as follows:
n

o
G(α, u, k) = 1 − k Φ u + Φ−1 (1 − α/(2k)) − Φ u − Φ−1 (1 − α/(2k)) .
(35)
Note that for any integer k ≥ 1 and α ∈ [0, 1], G(α, 0, k) = α confirming the observation that
if θ0 is arbitrarily close to Ω, one cannot outperform random guessing. Further, for any k ≥ 1,
α > 0, the function u 7→ G(α, u, k) is continuous and monotone increasing, i.e., the larger d(θ0 , Ω0 )
the higher power is achieved. Also, in order to achieve a specific power β > α, our scheme requires
√
b T )1/2 , for some constant cβ that depends on the desired power β.
γ > cβ (σ/ n) maxi∈S (M ΣM
ii
It is worth noting that in case of testing individual parameters H0,i : θ0,i = 0 (corresponding
to Ω0 = {θ ∈ Rp : θ0,i = 0}), k = 1 and we recover the power lower bound established in [JM14a],
which by comparing to the minimax trade-off studied in [JM14b], is optimal up to a constant.

5

Discussion

In this section, we discuss some of the applications of our testing methodology.

5.1

Confidence interval for f (θ0 )

Let f : Rp → R be an arbitrary function. We can always write f (θ) = g(θS ) for some subset
S ⊆ [p] of size k, with 1 ≤ k ≤ p, and for a function g : Rk → R. We refer to S as the effective
domain of f because the value f (θ) does not depend on the coordinates θi , for i ∈
/ S. We apply
our testing framework to test H0 : f (θ0 ) = η by defining Ω0 = f −1 (η), and then use the duality
between confidence intervals and statistical tests to obtain a confidence interval for f (θ0 ).
Proposition 5.1. Let f : Rp → R be any arbitrary fixed function with effective domain S ⊆ [p],
with |S| = k for some 1 ≤ k ≤ p. Define C(α) = [η− , η+ ], where η− and η+ are given as follows:

α
, vS c = 0
(36)
η− = min f (θbd − D−1 v)
subject to kvk∞ ≤ Φ−1 1 −
v
2k 

α
η+ = max f (θbd + D−1 v)
subject to kvk∞ ≤ Φ−1 1 −
, vS c = 0
(37)
v
2k
Under the conditions of Theorem 4.1,
lim P (f (θ0 ) ∈ C(α)) ≥ 1 − α .

n→∞

Proof of Proposition 5.1 is given in Section 7.5.

12

(38)

5.2

Confidence interval for predictions

One special but important case is f (θ) = hxnew , θi, where xnew is a new feature data, and hence
f (θ) corresponds to the noiseless unobserved response on xnew .
Proposition 5.2. Consider a sequence of design matrices X ∈ Rn×p , with dimensions n, p → ∞,
p = p(n) → ∞ satisfying the assumptions of Theorem 4.1. Then, an asymptotic two-sided confidence interval for hxnew , θ0 i, with significance α is given by C(α) = [hxnew , θbd i−δ(α, n), hxnew , θbd i+
δ(α, n)] where in case of non-adaptive xnew

α  kxnew k1 kxnew k∞ new
δ(α, n) = Φ−1 1 −
hx , Qxnew i1/2 .
2
kxnew k2

(39)

In case of adaptive xnew , we have
p

−1

δ(α, n) = Φ



α  X 1/2 new
Qii |xi | ,
1−
2k

(40)

i=1

where k = |supp(xnew )| and Q is given by (17).

5.3

Testing beta-min condition

For a given c > 0, define the set Ω0 = {θ ∈ Rp : minj∈supp(θ) |θj | ≥ c}. Note that Ω0 is non-convex
and indeed disconnected. Further, the `∞ projection pursuit given by (18) is not unique. However,
there exists a closed-form solution to this optimization problem.
Lemma 5.3. Let v ∈ Rp and define θ ∈ Rp with


x



c
S(x, c) =
0



−c

θi = S(vi , c), where
|x| ≥ c ,
x ∈ (c/2, c)
x ∈ [−c/2, c/2]
x ∈ (−c, −c/2)

(41)

Then θ is a solution to minθ∈Rp kD(θ − v)k∞ , subject to θ ∈ Ω0 , for any diagonal matrix D.
Proof of Lemma 5.3 is straightforward and is omitted.
Therefore, test statistic in this case becomes
Tn = kD(θbd − S(θbd , c))k∞ .
The decision rule also reads as



−1 1 − α

1
if
T
≥
Φ
n


2p
RX (y) =



0 otherwise

13

(42)

(reject H0 )
(43)
(fail to reject H0 ).

(a) Type I error

c\ρ
0.6
0.7
0.8
0.9
1

0.2
0
0
0.02
0.04
0.04

0.4
0.02
0.04
0.05
0.05
0.05

0.6
0.02
0.02
0.04
0.05
0.05

(b) Statistical power

0.8
0
0.02
0.02
0.02
0.04

c\ρ
1.1
1.2
1.3
1.4
1.5

0.2
0.06
0.54
0.96
1
1

0.4
0.14
0.82
1
1
1

0.6
0.20
0.94
1
1
1

0.8
0.18
0.74
1
1
1

Table 1: Type I error and statistical power for H0 : minj∈supp(θ0 ) |θ0,j | ≥ c, for significance level α = 0.05.

5.4

Testing membership in the non-negative cone

Let Ω0 = {θ ∈ Rp : θi ≥ 0}. Clearly, Ω0 is closed under addition. Therefore, we can use Algorithm 1
to test H0 : θ0 ∈ Ω0 . For a vector v, let v+ and v− respectively denote the positive (negative) parts
of v, i.e., v+,i = vi I(vi ≥ 0) and v−,i = vi I(vi ≤ 0). Then, the projection pursuit θp , given by (26),
d and the test statistics becomes T = √nkθ
bd k∞ . We then use the rule (26) in
works out at θp = θb+
n
−
rejecting the null hypothesis.

6

Numerical illustration

In this section, we examine the performance of our inference framework in terms of coverage rate,
confidence interval length, type I error and statistical power under different setups. We consider
linear model (2) where the design matrix X ∈ Rn×p has i.i.d rows generated from N(0, Σ), with
Σ ∈ Rp×p being the Toeplitz matrix Σi,j = ρ|i−j| . For coefficient parameter θ0 , we consider a
uniformly random support S ⊆ [p], with |S| = s0 , and let θ0,i = b for i ∈ S and θ0,i = 0, otherwise.
The measurement errors are Wi ∼ N(0, 1).

6.1

Testing beta-min condition

We consider null hypothesis H0 : minj∈supp(θ0 ) |θ0,j | ≥ c. For Lasso estimator θbn , we set the
p
e =
regularization
parameter λ = 4b
σ (2 log p)/n, with σ
b given by the scaled Lasso (16), with λ
p
10 (2 log p)/n. Further, p
the parameter µ in constructing the debiased estimator (see Optimization (12)) is set to µ = 2 (log p)/n. We set p = 1000, n = 600, b = 1, s0 = 10 and compute the
rejection probabilities based on 100 random samples.
We set α = 0.05 and vary the values of c and ρ. When c < 1, H0 holds and thus the rejection
probability corresponds to the type I error. When c > 1, the rejection probability corresponds to
the power of the test. The results are reported in Table 1. As we see in Table 1(a), type I error is
controlled below the desired level α = 0.05. Also, as evident in Table 1(b), the power of our test
increases at a very fast rate as c increases. (Its power gets close to one for different values of ρ at
c = 1.3)

6.2

Confidence intervals for linear functions

We use our methodology to construct 95% confidence intervals for functions of form hξ, θ0 i. We set
p = 3000, s0 = 30 and choose the correlation parameter ρ = 0.5. The value of nonzero parameters
14

1

0
ξ1

0.95

ξ2

−0.5

ξ3
ξ4

log(CI width)

95% CI Coverage

0.9
0.85
0.8
ξ1

0.75

ξ2

−0.5 log(n)

−1.5
−2

ξ3

0.7

ξ4

0.65
0.6

ξ5

−1

−2.5

ξ5
1000

1500

2000

−3
6.8

2500

7

7.2

n

7.4

7.6

7.8

8

log(n)

(a) Coverage of confidence intervals

(b) Confidence interval widths

Figure 1: (a) Coverage of 95% confidence intervals (39) for linear functions hξ, θ0 i versus sample size n. (b)
Confidence interval widths versus sample size n. Here p = 3000, s0 = 30, b = 0.5, ρ = 0.5.
(a) Type I error

b\ρ
1
0.75
.5
.25
0

0.2
.06
.06
0.07
0.05
0.05

0.4
0.05
0.04
0.04
0.04
0.04

0.6
0.05
0.06
0.04
0.05
0.05

(b) Statistical power

0.8
0.03
0.03
0.03
0.03
0.04

b\ρ
−0.25
−0.5
−0.75
−1

0.2
.70
1
1
1

0.4
0.97
1
1
1

0.6
1
1
1
1

0.8
.71
1
1
1

Table 2: Testing in the non-negative cone, (n, s, p) = (600, 10, 1000). The non-zero entries have magnitude
b, and the covariance Σij = ρ|i−j| .

is set as b = 0.5.
We construct confidence intervals according to (39). We choose fives vectors ξ1 , ξ2 , . . . , ξ5 as
eigenvectors of Q with well-separated eigenvalues. For each ξi , we vary n in {1000, 1200, 1400, . . . , 2600}.
For each configuration (ξi , n), we consider N = 500 independent realizations of measurement noise
and on each realization, we construct 95% confidence interval for hξi , θ0 i based on Equation (39).
In Figure 1(a), we plot the average coverage probability of constructed confidence intervals
for each configuration. Each curve corresponds to one of the vectors ξi . As we see, the coverage
probability for all of them and across different values of n is close to the nominal value.
In Figure 1(b), we plot the average length of confidence intervals as we vary the sample size n
√
in the log-log scale. As evident from the figure, the length of confidence intervals scales as 1/ n.
In Figure 2, we plot the constructed 95%-confidence intervals for hξ1 , θ0 i, and n = 1600. For
sake of clarity, we plot the confidence intervals for only 50 realizations of the measurement noise.

6.3

Testing for the non-negative cone

Define Ω0 = {θ : θi ≥ 0 for all i} as the non-negative cone. In this section, we test whether θ0 ∈ Ω0
versus θ0 ∈
/ Ω0 . The null model is generated as θ0,i = b for i ∈ S and zero, otherwise. Likewise,
15

1
0.8

hξ1 , θ0 i
hξ1 , θbd i

0.6
0.4
0.2
0
−0.2
−0.4
−0.6
−0.8
−1

0

100

200

300

400

500

n
Figure 2: 95% confidence intervals (39) for linear function hξ1 , θ0 i and for 50 independent realizations of
measurement noise. Here p = 3000, n = 1600. Values hξ1 , θ0 i are in red and values hξ1 , θbd i are in black.
Note that the CI are centered around hξ1 , θ0 i.

the alternative model is generated as θ0,i = −b, for i ∈ S and zero, otherwise. As in the previous
sections, the design matrix X ∈ Rn×p has i.i.d rows generated from N(0, Σ), with Σ ∈ Rp×p
being the Toeplitz matrix Σi,j = ρ|i−j| , and measurement errors Wi ∼ N(0, 1), with parameters
(n, s, p) = (600, 10, 1000) with 300 repetitions. The Monte Carlo simulation in Algorithm 1 is done
with B = 104 . We vary the values of b and ρ.
The simulation shows that the type I error is controlled at nearly α = 0.05, and is not overly
conservative, due to the Monte Carlo calibration. For statistical power when |b| ≥ 0.5, the power is
1. In the most difficult case of b = −0.25, the power is still above 0.7. We would like to note that
this is a very difficult alternative in the sense that only a small fraction of the coordinates, s0 /d,
are negative, so it is a very mild violation of the null, yet our algorithm still has high power.

7
7.1

Proof of Theorems
Proof of Theorem 4.1

√
Let σ ∗ = kW k/ n. We first prove a lemma to bound the estimation error of σ
b returned by the
scaled Lasso. The following lemma uses the analysis of [SZ12] and its proof is given in Appendix A
for reader’s convenience.
Lemma 7.1. Under the assumptions
of Theorem 4.1, let σ
b=σ
b(λ) be the scaled Lasso estimator
p
of the noise level, with λ = c (log p)/n. Then, σ
b satisfies
!
r
σ
b
2c
s0 log p
c2
−c0
−n/16
P
−
1
≥
+
2e
,
c
=
− 1.
(44)
≤
2p
0
σ∗
φ0 σ ∗
n
32K

16

Our next proposition bounded the bias of θbd . Its analysis is similar to [JM14a, Theorem 2.3]
but it differs in that it uses scaled Lasso as the initial estimator, while [JM14a, Theorem 2.3] uses
Lasso. We refer to Appendix B for its proof.
Proposition 7.2. Let X ∈ Rn×p be any (deterministic) design matrix, and θbd = θbd (λ) be a
b
general debiased estimator as per Eq (11), with θb = θ(λ)
the scaled Lasso estimator. Then, setting
√
T
Z = M X W/ n, we have
√
√ d
b .
b T ) , ∆ = n(M Σ
b − I)(θ0 − θ)
n(θb − θ0 ) = Z + ∆ , Z ∼ N(0, σ 2 M ΣM
(45)
p
Further, choosing λ = c (log p)/n, we have


c2
cµσ ∗ s0 p
−c0
−n/16
log
p
≤
2p
+
2e
,
c
=
P k∆k∞ ≥
− 1.
(46)
0
32K
φ20
We next recall the following lemma from [JM14a] that will be used later in the proof.
Lemma 7.3. ([JM14a, Lemma 3.1]) Let M = (m1 , . . . , mp )T be the matrix with rows mT
i obtained
by solving optimzation (12). Then, for all i ∈ [p],
b T ]i,i ≥
[M ΣM

(1 − µ)2
.
b ii
Σ

(47)

Under H0 , we have θ0 ∈ Ω0 and hence
Tn = kD(θbd − θbp )k∞ ≤ kD(θbd − θ0 )k∞
1
1
≤ √ kDZk∞ + √ kD∆k∞
n
n

(48)

√
Note that for Z̃ = σ
bDZ/(σ n), we have Z̃i ∼ N(0, 1). The entries of Z̃ are correlated though.
Fix  > 0 and using Equation (48),


1
σ
kZ̃k∞ + √ kD∆k∞ ≥ x
P(Tn ≥ x) ≤ P
σ
b
n


σ

1
≤P
kZ̃k∞ ≥ x −  + P √ kD∆k∞ ≥ 
σ
b
n






σ
b
1
≤ P kZ̃k∞ ≥ (1 − )(x − ) + P
− 1 ≥  + P √ kD∆k∞ ≥ 
(49)
σ
n
For the second term, we proceed as follows






σ
b

σ
b

σ
b
σ
b
≥
≥
P
−1 ≥ ≤P
−
1
+
P
−
σ
σ∗
2
σ∗ σ
2

(50)

Now, note that σ ∗ → σ, in probability, as n tends to infinity. Moreover, by applying Lemma (7.1)
and using the assumption s0 = o(n/ log p), we can write


lim sup P(Tn ≥ x) ≤ lim sup P kZ̃k∞ ≥ (1 − )(x − )
(51)
n→∞
n→∞


1
+lim sup P √ kD∆k∞ ≥ 
(52)
n
n→∞
17

b T ]i,i ≥ (1 − µ)2 /Σ
b ii . Therefore,
By Lemma 7.3, for large enough n, we have [M ΣM




1
1
1/2
b ii ) k∆k∞ ≥ 
(max Σ
P √ kD∆k∞ ≥  ≤ P
σ
b(1 − µ) i∈S
n
!
√
 ∗

σ
2 K
b ii ≥ K)
k∆k∞ >  + P
≤P
≥ 2 + P(max Σ
i∈S
(1 − µ)σ ∗
σ
b

(53)
(54)

b ii , we clearly
By Lemma (7.1), we have P((σ ∗ /b
σ ) ≥ 2) → 0 and by definition K ≥ maxi∈[p] Σ
b ii > K) = 0.
have P(maxi∈S Σ
√
√
√
Since s0 = o(1/(µ log p)), for n and p large enough, we have cµs0 log p/φ20 ≤ (1 − µ)/(2 K).
Hence by (46),
!
√


1
2 K
lim sup P √ kD∆k∞ ≥  ≤ lim sup P
k∆k∞ > 
(55)
(1 − µ)σ ∗
n
n→∞
n→∞
≤ lim sup (2p−c0 + 2e−n/16 ) = 0 .

(56)

n→∞

By substituting (56) in (49), we get
lim sup P(Tn ≥ x) ≤ lim sup P(kZ̃k∞ ≥ x − x + 2 ).
n→∞

(57)

n→∞

By union bounding over the first k entries,
P(kZ̃k∞ ≥ x − x + 2 ) ≤ 2k(1 − Φ(x − x + 2 )).

(58)

The above holds for any  > 0, and since the right-hand side is continuous in ,
P(kZ̃k∞ ≥ x) ≤ 2k(1 − Φ(x)).
The result follows from the above and (67) by choosing x = Φ−1 (1 − α/(2k)).

7.2

Proof of Theorem 4.2

For φ0 , s0 , K ≥ 0, let En = En (φ0 , s0 , K) be the event that the compatibility condition holds for
b = (X T X/n), for all sets S ⊆ [p], |S| ≤ s0 with constant φ0 > 0, and that maxi∈[p] Σ
b i,i ≤ K.
Σ
Explicitly
n
o
b S) ≥ φ0 , max Σ
b i,i ≤ K, Σ
b = (X T X/n) .
En (φ0 , s0 , K) ≡ X ∈ Rn×p :
min φ(Σ,
(59)
S: |S|≤s0

i∈[p]

Then, by result of [RZ13, Theorem 6] (see also [JM14a,
Theorem 2.4(a)]), random designs satisfy
√
the compatibility condition with constant φ0 = Cmin /2, provided that n ≥ νs0 log(p/s0 ), where
ν = cκ4 (Cmax /Cmin ), for a constant c > 0. More precisely,
4

P(X ∈ En (φ0 , s0 , K)) ≥ 1 − 4e−c1 n/κ ,

(60)

where c1 = c1 (c) > 0 is a constant.
p
Further, by Proposition 2.3, we can take µ = a (log p)/n, with probability at least 1 − 2p−c2 .
Putting these two bounds together in Theorem 4.1, we obtain that for random designs with
√
s0 = o( n/(log p)), we have lim sup αn (RX ) ≤ α.
n→∞

18

7.3

Proof of Theorem 4.3

First consider deterministic designs. Under the assumption of Theorem 4.1, for an arbitrary fixed
 > 0, we have
lim sup P(k∆k∞ ≥ ) = 0 .

(61)

n→∞

√
Equation 61 follows from Proposition 7.2 and using the assumption s0 = o(1/(µ log p)).
Similarly, Equation 61 under the assumptions of Theorem 4.2 for random designs.
We fix  = 0.001 and define θ̄ = θ0 + √1n PΩ∞0 (Z). Under the null, θ̄ ∈ Ω0 , and since Ω0 is closed
under addition, θ̄ ∈ Ω0 . Then,
√
√
Tn = nkθbd − θbp k∞ ≤ nkθbd − θ̄k∞
√
1
Z
≤ n θ0 + √ − θ0 − √ PΩ∞0 (Z)
+ k∆k∞
n
n
∞
≤ Z − PΩ∞0 (Z)

∞

+ k∆k∞ .

Hence,
lim sup αn (RX )
n→∞

lim sup P(Tn ≥ Φ−1
Z,Ω0 (1 − α) + 0.001)
n→∞


≤ lim sup P Z − PΩ∞0 (Z) ∞ + k∆k∞ ≥ Φ−1
(α)
+
0.001
Z,Ω0
n→∞


≤ lim sup P Z − PΩ∞0 (Z) ∞ ≥ Φ−1
Z,Ω0 (α) + lim sup P(k∆k∞ > 0.001)
n→∞

n→∞

≤ α.

(62)

Here, the last step follows from 61 and definition of ΦZ,Ω0 .

7.4

Proof of Theorem 4.4

Let z∗ ≡ Φ−1 (1 − α/(2k)). Write
1 − βn (RX )
G(α/k, γ, k)
n
o
1
= lim inf
inf Pθ0 (RX = 1) : kθ0 k0 ≤ s0 , d(θ0 , Ω0 ) ≥ γ
n→∞ G(α/k, γ, k) θ0
n 

o
1
= lim inf
inf P kD(θbd − θbp )k∞ ≥ z∗ : kθ0 k0 ≤ s0 , d(θ0 , Ω0 ) ≥ γ
n→∞ G(α/k, γ, k) θ0

lim inf
n→∞

(63)

We further note that
kD(θbd − θbp )k∞ ≥ kD(θbp − θ0 )k∞ − kD(θbd − θ0 )k∞

(64)

To ease the notation, let T̃ = kD(θbp − θ0 )k∞ and T = kD(θbd − θ0 )k∞ . We then have
P(kD(θbd − θbp )k∞ ≥ z∗ ) ≥ P(|T̃ − T | ≥ z∗ )
n
o
= 1 − P(T ≥ T̃ − z∗ ) − P(T ≥ T̃ + z∗ ) = 1 − P(T̃ − z∗ ≤ T ≤ T̃ + z∗ )
19

(65)
(66)

As proved in Equation (67), we have
lim sup P(T ≥ x) ≤ lim sup P(kZ̃k∞ ≥ x)
n→∞

(67)

n→∞

where Z̃ has standard normal entries. A matching lower bound can be derived by a similar argument. Hence,
lim sup
n→∞

P(T ≥ x) − P(kZ̃k∞ ≥ x) = 0 .

(68)

Further, since θbp ∈ Ω0 , we have
T̃ ≥ min(Dii ) kθbp − θ0 k∞ ≥ mQ d(θ0 , Ω0 ) ≥ mQ γ .
i∈S

Using (66) and (68) in (63), we get
1 − βn (RX )
G(α/k, mQ γ, k)

n 

o
1
= lim inf
1 − sup P T̃ − z∗ ≤ kZ̃k∞ ≤ T̃ + z∗ : T̃ ≥ γ
n→∞ G(α/k, mQ γ, k)
θ0

n 

o
1
1 − k sup P T̃ − z∗ ≤ |Z̃1 | ≤ T̃ + z∗ : T̃ ≥ γ
≥ lim inf
n→∞ G(α/k, mQ γ, k)
θ0



1
= lim inf
1 − k P mQ γ − z∗ ≤ |Z̃1 | ≤ mQ γ + z∗
n→∞ G(α/k, mQ γ, k)

n
o
1
= lim inf
1 − k Φ(mQ γ + z∗ ) − Φ(mQ γ − z∗ )
n→∞ G(α/k, mQ γ, k)
1
= lim inf
G(α/k, mQ γ, k) = 1 ,
n→∞ G(α/k, mQ γ, k)

lim inf
n→∞

(69)

where in the last step we substitute for z∗ .

7.5

Proof of Proposition 5.1

For η ∈ R, define the null hypothesis H0 (η) : f (θ0 ) = η and the alternative HA (η) : f (θ0 ) 6= η.
Define Ω0 = f −1 (η) = S × Rp−k , since f (θ) = g(θS ).
Recalling our test statistic (19), which was based on the following optimization
kD(θbd − θ)k∞
subject to θ ∈ Ω0 and θbSd c = θS c
minimizeθ

(70)

By the change of variables v = Dn (θbd − θ), this can be recast as
kvk∞
subject to f (θbd − D−1 v) ∈ η and vS c = 0
minimizev

(71)

We now invert the hypothesis test to construct a confidence interval. By detection rule (20), we
fail to reject H0 (η) if the optimal value of optimization (26) is smaller than Φ−1 (1 − α/(2k)). We
20

see that these values of η that are accepted is the range of f (θbd − D−1 v) subject to the constraints
kvk∞ ≤ Φ−1 (1−α/(2k)), and vS c = 0. We can find the endpoints of the smallest interval containing
this range by computing

α
max / min f (θbd − D−1 v) subject to kvk∞ ≤ Φ−1 1 −
and vS c = 0.
2k
The coverage of the interval C(α) = [η − , η + ] follows from 4.1 and the duality between confidence
intervals and hypothesis testing.

7.6

Proof of Proposition 5.2

We start by the case of non-adaptive xnew . Let Ω0 = {θ ∈ Rp : hxnew , θi = η}. The set Ω0 is not
closed under addition and hence we cannot directly apply the result of Theorem 4.3. Instead we
follow a similar proof. Define
Ω = {θ ∈ Rd : hxnew , θi = 0} .

(72)

Consider test statistic (22). Let θ̄ = θ0 + √1n PΩ∞ (Z). Since Ω is close under addition, similar to
Equation (62), under null hypothesis H0 : θ0 ∈ Ω0 , we have
Tn ≤ kZ − PΩ∞ (Z)k∞ + k∆k∞ .
−1
Therefore, in the decision rule (23), we can replace Φ−1
Z,Ω0 (α) by ΦZ,Ω (α).
Similar to the proof of Proposition 5.1, by duality between hypothesis testing and confidence
intervals, we can construct (1 − α) confidence interval C(α) = [η− , η+ ] for hxnew , θ0 i as follows:
new
k1
η− = hxnew , θbd i − Φ−1
Z,Ω (α)kx
new
k1
η+ = hxnew , θbd i + Φ−1
Z,Ω (α)kx

(73)

We next bound Φ−1
Z,Ω (α).
ΦZ,Ω (t) = P(kZ − PΩ∞ (Z)k∞ > t) ≤ P(kZ − PΩ (Z)k∞ > t) = P(kPΩ⊥ (Z)k∞ > t) ,

(74)

where PΩ denotes the `2 projection onto Ω and the first inequality follows from definition of `∞ projection. Let x̃new = xnew /kxnew k be the normalized vector. We have PΩ⊥ (Z) = hx̃new , Zix̃new . Since
xnew is non-adaptive, it is independent of Z. Hence, hx̃new , Zi ∼ N(0, σ02 ), with σ02 = hx̃new , Qx̃new i.
Therefore,

t 
ΦZ,Ω (t) ≤ P(kPΩ⊥ (Z)k∞ > t) ≤ P |hx̃new , Zi| >
kx̃k∞



t
=2 1−Φ
(75)
σ0 kx̃k∞
By inverting above equation, we get

α
−1
Φ−1
(α)
≤
σ
kx̃k
Φ
1
−
0
∞
Z,Ω
2
new
d
new
b
By recalling (73), we have C(α) = [hx , θ i − δ(α, n), hx , θbd i + δ(α, n)], with

α
kxnew k1 kxnew k∞ new
new 1/2 −1
1
−
δ(α, n) ≤
hx
,
Qx
i
Φ
.
kxnew k2
2

(76)

(77)

In case of adaptive xnew , the result follows by applying Proposition 5.1 to f (θ) = hxnew , θi.
21

A

Proof of Lemma 7.1

We apply [SZ12, Theorem 1], where using their notation with their λ0 replaced by λ, ξ = 3,
T = supp(θ0 ), κ(ξ, T ) ≥ φ0 , η∗ (σ ∗ λ, ξ) ≤ 4s0 λ2 /φ20 . By a straightforward manipulation of Eq. (13)
in [SZ12], we have for kX T W/(nσ ∗ )k∞ ≤ λ/2,
r
√
2 s0 λ
σ
b
2c
log p
−1 ≤
=
.
(78)
∗
∗
∗
σ
φ0 σ
φ0 σ
n
Note that

P

kX T W k∞
λ
>
∗
nσ
2

√
We define vj = W T Xej /( nσ).
supremum of p gaussian random

kX T W k∞
P
>
nσ




≤P

kX T W k∞
λ
>
nσ
4


+P

σ

>
2
σ∗

(79)

b jj ) by applying a standard tail bound on the
Since vj ∼ N(0, Σ
variables, we get

λ
c2
2
2
≤ 2pe−λ n/(32K ) = 2p−c0
c0 =
− 1.
(80)
4
32K

For the second term, note that

n

σ ∗2
kW k2
1X 2
=
=
Zj ,
σ2
nσ 2
n
j=1

with Zj ∼ N(0, 1) independent. By a standard tail bound for χ2 random variables we have
 σ∗
P

σ

≤

n
 1X
1
3
≤P
Zj2 − 1 >
≤ 2e−n/16 .
2
n
4

(81)

j=1

Combining (80), (81) in (79), we get that


kX T W k∞
λ
P
>
≤ 2p−c0 + 2e−n/16 ,
nσ
4
which yields the desired result.

B

Proof of Proposition 7.2

The proof follows the same lines as [JM14a, Theorem 2.3]. We plug in for y = Xθ0 + W in the
definition of debiased estimator.
1
b + 1 M X TW
θbd = θb + M X T X(θ0 − θ)
n
n
1
1
= θ0 + √ Z + √ ∆ ,
n
n
where ∆ and Z are defined in the theorem statement. Also, given W ∼ N(0, σ 2 I), we have Z ∼
b T ).
N(0, σ 2 M ΣM
22

In order to bound k∆k∞ , we use duality of `1 and `∞ to write
√
√
b − I|∞ kθb − θ0 k1 ≤ nµkθb − θ0 k1 .
k∆k∞ ≤ n|M Σ
Employing [SZ12, Corollary 1], with ξ = 3, for kX T W/(nσ ∗ )k∞ ≤ λ/2, we have kθb − θ0 k1 ≤
As we showed in the proof of Lemma 7.1,


λ
kX T W k∞
≤ 2p−c0 + 2e−n/16 ,
>
P
nσ
4
p
Therefore, invoking Equation (82), and substituting for λ = c (log p)/n, we have


cµσ ∗ s0 p
P k∆k∞ ≥
log p ≤ 2p−c0 + 2e−n/16 .
2
φ0

(82)
σ ∗ λs0
.
φ20

(83)

References
[ABDJ06]

Felix Abramovich, Yoav Benjamini, David L Donoho, and Iain M Johnstone, Special
invited lecture: adapting to unknown sparsity by controlling the false discovery rate,
The Annals of Statistics (2006), 584–653. 5

[BC14]

Rina Foygel Barber and Emmanuel Candes, Controlling the false discovery rate via
knockoffs, arXiv:1404.5609 (2014). 5

[BCFVH13]

Alexandre Belloni, Victor Chernozhukov, Ivan Fernández-Val, and Chris Hansen,
Program evaluation and causal inference with high-dimensional data, arXiv preprint
arXiv:1311.2645 (2013). 5

[BCH11a]

Alexandre Belloni, Victor Chernozhukov, and Christian Hansen, Inference for highdimensional sparse econometric models, arXiv preprint arXiv:1201.0220 (2011). 5

[BCH11b]

, Lasso methods for gaussian instrumental variables models. 5

[BCH14]

, Inference on treatment effects after selection among high-dimensional controls, The Review of Economic Studies 81 (2014), no. 2, 608–650. 5

[BEM13]

Mohsen Bayati, Murat A Erdogdu, and Andrea Montanari, Estimating lasso risk and
noise level, Advances in Neural Information Processing Systems, 2013, pp. 944–952.
3

[BK15]

Rina Foygel Barber and Mladen Kolar, Rocket: Robust confidence intervals via
kendall’s tau for transelliptical graphical models, arXiv preprint arXiv:1502.07641
(2015). 5

[BRT09]

P. J. Bickel, Y. Ritov, and A. B. Tsybakov, Simultaneous analysis of Lasso and
Dantzig selector, Amer. J. of Mathematics 37 (2009), 1705–1732. 2

23

[BvdBS+ 15]

Malgorzata Bogdan, Ewout van den Berg, Chiara Sabatti, Weijie Su, and Emmanuel J Candès, Slopeadaptive variable selection via convex optimization, The annals of applied statistics 9 (2015), no. 3, 1103. 5

[BvdG11]

Peter Bühlmann and Sara van de Geer, Statistics for high-dimensional data,
Springer-Verlag, 2011. 2

[CD95]

S.S. Chen and D.L. Donoho, Examples of basis pursuit, Proceedings of Wavelet
Applications in Signal and Image Processing III (San Diego, CA), 1995. 2

[CFJL16]

E. J. Candès, Y. Fan, L. Janson, and J. Lv, Panning for gold: Model-free knockoffs
for high-dimensional controlled variable selection, Manuscript (2016). 5

[CG15]

T Tony Cai and Zijian Guo, Confidence intervals for high-dimensional linear regression: Minimax rates and adaptivity, arXiv:1506.05539 (2015). 5

[CRZZ16]

Mengjie Chen, Zhao Ren, Hongyu Zhao, and Harrison Zhou, Asymptotically normal
and efficient estimation of covariate-adjusted gaussian graphical model, Journal of
the American Statistical Association 111 (2016), no. 513, 394–406. 5

[CT07]

E. Candés and T. Tao, The Dantzig selector: statistical estimation when p is much
larger than n, Annals of Statistics 35 (2007), 2313–2351. 2

[D+ 14]

Lee H Dicker et al., Variance estimation in high-dimensional linear models,
Biometrika 101 (2014), no. 2, 269–284. 3

[FGH12]

Jianqing Fan, Shaojun Guo, and Ning Hao, Variance estimation using refitted crossvalidation in ultrahigh dimensional regression, Journal of the Royal Statistical Society: Series B (Statistical Methodology) 74 (2012), no. 1, 37–65. 3

[FL01]

Jianqing Fan and Runze Li, Variable selection via nonconcave penalized likelihood
and its oracle properties, Journal of the American statistical Association 96 (2001),
no. 456, 1348–1360. 2

[FL08]

Jianqing Fan and Jinchi Lv, Sure independence screening for ultrahigh dimensional
feature space, Journal of the Royal Statistical Society: Series B (Statistical Methodology) 70 (2008), no. 5, 849–911. 2

[FST14]

William Fithian, Dennis Sun, and Jonathan Taylor, Optimal inference after model
selection, arXiv preprint arXiv:1410.2597 (2014). 5

[GR04]

E. Greenshtein and Y. Ritov, Persistence in high-dimensional predictor selection and
the virtue of over-parametrization, Bernoulli 10 (2004), 971–988. 2

[HPM+ 16]

Xiaoying Tian Harris, Snigdha Panigrahi, Jelena Markovic, Nan Bi, and
Jonathan Taylor, Selective sampling after solving a convex problem, arXiv preprint
arXiv:1609.05609 (2016). 5

[JBC16]

Lucas Janson, Rina Foygel Barber, and Emmanuel Candes, Eigenprism: inference
for high dimensional signal-to-noise ratios, Journal of the Royal Statistical Society:
Series B (Statistical Methodology) (2016). 2, 3
24

[JM13]

Adel Javanmard and Andrea Montanari, Nearly optimal sample size in hypothesis
testing for high-dimensional regression, 51st Annual Allerton Conference (Monticello,
IL), June 2013, pp. 1427–1434. 3, 6

[JM14a]

, Confidence intervals and hypothesis testing for high-dimensional regression,
The Journal of Machine Learning Research 15 (2014), no. 1, 2869–2909. 3, 4, 5, 6,
7, 8, 12, 17, 18, 22

[JM14b]

, Hypothesis Testing in High-Dimensional Regression under the Gaussian
Random Design Model: Asymptotic Theory, IEEE Trans. on Inform. Theory 60
(2014), no. 10, 6522–6554. 2, 3, 4, 6, 12

[JM15]

, De-biasing the lasso: Optimal sample size for gaussian designs, arXiv
preprint arXiv:1508.02757 (2015). 4

[JS15]

Lucas Janson and Weijie Su, Familywise error rate control via knockoffs,
arXiv:1505.06549 (2015). 5

[Kud63]

Akio Kudo, A multivariate analogue of the one-sided test, Biometrika 50 (1963),
no. 3/4, 403–418. 4

[Lee15]

Jason D Lee, Selective inference and learning mixed graphical models, arXiv preprint
arXiv:1507.00039 (2015). 5

[LSS+ 16]

Jason D Lee, Dennis L Sun, Yuekai Sun, Jonathan E Taylor, et al., Exact postselection inference, with application to the lasso, The Annals of Statistics 44 (2016),
no. 3, 907–927. 5

[LT14]

Jason D Lee and Jonathan E Taylor, Exact post model selection inference for
marginal screening, Advances in Neural Information Processing Systems, 2014,
pp. 136–144. 5

[MB06]

N. Meinshausen and P. Bühlmann, High-dimensional graphs and variable selection
with the lasso, The Annals of Statistics 34 (2006), 1436–1462. 2

[MY09]

N. Meinshausen and B. Yu, Lasso-type recovery of sparse representations for highdimensional data, The Annals of Statistics 37 (2009), no. 1, 246–270. 2

[RCLN86]

Richard F Raubertas, Chu-In Charles Lee, and Erik V Nordheim, Hypothesis tests
for normal means constrained by linear inequalities, Communications in StatisticsTheory and Methods 15 (1986), no. 9, 2809–2833. 4

[RSZ+ 15]

Zhao Ren, Tingni Sun, Cun-Hui Zhang, Harrison H Zhou, et al., Asymptotic normality and optimalities in estimation of large gaussian graphical models, The Annals
of Statistics 43 (2015), no. 3, 991–1026. 5

[RW78]

Tim Robertson and Edward J Wegman, Likelihood ratio tests for order restrictions
in exponential families, The Annals of Statistics (1978), 485–505. 4

25

[RWY09]

G. Raskutti, M. J. Wainwright, and B. Yu, Minimax rates of estimation for highdimensional linear regression over `q -balls, 47th Annual Allerton Conf. (Monticello,
IL), September 2009. 2

[RZ13]

Mark Rudelson and Shuheng Zhou, Reconstruction from anisotropic random measurements, IEEE Trans. on Inform. Theory 59 (2013), no. 6, 3434–3447. 18

[SC16]

Weijie Su and Emmanuel Candes, Slope is adaptive to unknown sparsity and asymptotically minimax, The Annals of Statistics 44 (2016), no. 3, 1038–1068. 5

[SZ12]

Tingni Sun and Cun-Hui Zhang, Scaled sparse linear regression, Biometrika 99
(2012), no. 4, 879–898. 8, 16, 22, 23

[Tib96]

R. Tibshirani, Regression shrinkage and selection with the Lasso, Journal of the
Royal Statistical Society: Series B (Statistical Methodology) 58 (1996), 267–288. 2

[TT15]

Xiaoying Tian and Jonathan E Taylor, Selective inference with a randomized response, arXiv preprint arXiv:1507.06739 (2015). 5

[TTLT16]

Ryan J Tibshirani, Jonathan Taylor, Richard Lockhart, and Robert Tibshirani, Exact post-selection inference for sequential regression procedures, Journal of the American Statistical Association 111 (2016), no. 514, 600–620. 5

[VdGBRD14] Sara Van de Geer, Peter Bühlmann, Yaacov Ritov, and Ruben Dezeure, On asymptotically optimal confidence regions and tests for high-dimensional models, The Annals of Statistics 42 (2014), no. 3, 1166–1202. 3, 4, 5, 6
[VG16]

Nicolas Verzelen and Elisabeth Gassiat, Adaptive estimation of high-dimensional
signal-to-noise ratios, arXiv preprint arXiv:1602.08006 (2016). 3

[VHW08]

Peter M Visscher, William G Hill, and Naomi R Wray, Heritability in the genomics
era?concepts and misconceptions, Nature Reviews Genetics 9 (2008), no. 4, 255–266.
3

[Wai09]

M.J. Wainwright, Sharp thresholds for high-dimensional and noisy sparsity recovery
using `1 -constrained quadratic programming, IEEE Trans. on Inform. Theory 55
(2009), 2183–2202. 2

[WK16]

Jialei Wang and Mladen Kolar, Inference for high-dimensional exponential family
graphical models, Proc. of AISTATS, vol. 51, 2016, pp. 751–760. 5

[WWBS17]

Yining Wang, Jialei Wang, Sivaraman Balakrishnan, and Aarti Singh, Rate optimal
estimation and confidence intervals for high-dimensional regression with missing covariates, arXiv preprint arXiv:1702.02686 (2017). 5

[WWG17]

Yuting Wei, Martin J Wainwright, and Adityanand Guntuboyina, The geometry of
hypothesis testing over convex cones: Generalized likelihood tests and minimax radii,
arXiv preprint arXiv:1703.06810 (2017). 4

26

[ZKL14]

Tianqi Zhao, Mladen Kolar, and Han Liu, A general framework for robust testing and confidence regions in high-dimensional quantile regression, arXiv preprint
arXiv:1412.8724 (2014). 5

[ZY06]

P. Zhao and B. Yu, On model selection consistency of Lasso, The Journal of Machine
Learning Research 7 (2006), 2541–2563. 2

[ZZ14]

Cun-Hui Zhang and Stephanie S Zhang, Confidence intervals for low dimensional parameters in high dimensional linear models, Journal of the Royal Statistical Society:
Series B (Statistical Methodology) 76 (2014), no. 1, 217–242. 3, 4, 5, 6

27

