Variable selection with Hamming loss
Butucea, C.1,2 , Stepanova, N.A.3 , and Tsybakov, A.B.2

arXiv:1512.01832v4 [] 10 Mar 2017

1

Université Paris-Est Marne-la-Vallée, LAMA(UMR 8050), UPEM, UPEC, CNRS,
F-77454, Marne-la-Vallée, France

2

CREST, ENSAE, Université Paris Saclay, 3, avenue P. Larousse 92245 Malakoff Cedex, France

3

School of Mathematics and Statistics, Carleton University, Ottawa, Ontario, K1S 5B6 Canada

March 13, 2017

Abstract
We derive non-asymptotic bounds for the minimax risk of variable selection under
expected Hamming loss in the Gaussian mean model in Rd for classes of s-sparse vectors
separated from 0 by a constant a > 0. In some cases, we get exact expressions for the nonasymptotic minimax risk as a function of d, s, a and find explicitly the minimax selectors.
These results are extended to dependent or non-Gaussian observations and to the problem
of crowdsourcing. Analogous conclusions are obtained for the probability of wrong recovery of the sparsity pattern. As corollaries, we derive necessary and sufficient conditions
for such asymptotic properties as almost full recovery and exact recovery. Moreover, we
propose data-driven selectors that provide almost full and exact recovery adaptively to the
parameters of the classes.

Keywords:

adaptive variable selection, almost full recovery, exact recovery, Hamming

loss, minimax selectors, nonasymptotic minimax selection bounds, phase transitions.

1

Introduction

In recent years, the problem of variable selection in high-dimensional regression models has
been extensively studied from the theoretical and computational viewpoints. In making effective high-dimensional inference, sparsity plays a key role. With regard to variable selection in
sparse high-dimensional regression, the Lasso, Dantzig selector, other penalized techniques as
well as marginal regression were analyzed in detail; see, for example, [20, 27, 24, 19, 23, 25, 21,
12, 15] and the references cited therein. Several other recent papers deal with sparse variable
selection in nonparametric regression; see, for example, [17, 5, 10, 14, 8].
In this paper, we study the problem of variable selection in the Gaussian sequence model
Xj = θj + σξj ,
1

j = 1, . . . , d,

(1)

where ξ1 , . . . , ξd are i.i.d. standard Gaussian random variables, σ > 0 is the noise level, and
θ = (θ1 , . . . , θd ) is an unknown vector of parameters to be estimated. We assume that θ is
(s, a)-sparse, which is understood in the sense that θ belongs to one of the following sets:
n
Θd (s, a) =
θ ∈ Rd : there exists a set S ⊆ {1, . . . , d} with s elements
such that |θj | ≥ a for all j ∈ S, and θj = 0 for all j 6∈ S}

or
Θ+
d (s, a) =

n

θ ∈ Rd : there exists a set S ⊆ {1, . . . , d} with s elements

such that θj ≥ a for all j ∈ S, and θj = 0 for all j 6∈ S} .

Here, a > 0 and s ∈ {1, . . . , d} are given constants.

We study the problem of selecting the relevant components of θ, that is, of estimating the

vector
η = η(θ) = (I(θj 6= 0))j=1,...,d ,
where I(·) is the indicator function. As estimators of η, we consider any measurable functions
ηb = ηb(X1 , . . . , Xn ) of (X1 , . . . , Xn ) taking values in {0, 1}d . Such estimators will be called

selectors. We characterize the loss of a selector ηb as an estimator of η by the Hamming

distance between ηb and η, that is, by the number of positions at which ηb and η differ:
|b
η − η| ,

d
X
j=1

|b
ηj − ηj | =

d
X
j=1

I(b
ηj 6= ηj ).

Here, ηbj and ηj = ηj (θ) are the jth components of ηb and η = η(θ), respectively. The expected

Hamming loss of a selector ηb is defined as Eθ |b
η − η|, where Eθ denotes the expectation with

respect to the distribution Pθ of (X1 , . . . , Xn ) satisfying (1). Another well-known risk measure
is the probability of wrong recovery Pθ (Sb 6= S(θ)), where Sb = {j : ηbj = 1} and S(θ) = {j :

ηj (θ) = 1}. It can be viewed as the Hamming distance with an indicator loss and is related to
the expected Hamming loss as follows:

Pθ (Sb 6= S(θ)) = Pθ (|b
η − η| ≥ 1) ≤ Eθ |b
η − η|.

(2)

In view of the last inequality, bounding the expected Hamming loss provides a stronger result
than bounding the probability of wrong recovery.
Most of the literature on variable selection in high dimensions focuses on the recovery of the
sparsity pattern, that is, on constructing selectors such that the probability Pθ (Sb 6= S(θ)) is

close to 0 in some asymptotic sense (see, for example, [20, 27, 24, 19, 23, 25, 21]). These papers
consider high-dimensional linear regression settings with deterministic or random covariates.
√
In particular, for the sequence model (1), one gets that if a > Cσ log d for some C > 0 large
2

enough, then there exist selectors such that Pθ (Sb 6= S(θ)) tends to 0, while this is not the case
√
if a < cσ log d for some c > 0 small enough. More insight into variable selection was provided

in [12, 15] by considering a Hamming risk close to the one we have defined above. Assuming
that s ∼ d1−β for some β ∈ (0, 1), the papers [12, 15] establish an asymptotic in d “phase
diagram” that partitions the parameter space into three regions called the exact recovery,

almost full recovery, and no recovery regions. This is done in a Bayesian setup for the linear
regression model with i.i.d. Gaussian covariates and random θ. Note also that in [12, 15] the
knowledge of β is required to construct the selectors, so that in this sense the methods are not
√
adaptive. The selectors are of the form η̂j = I(|Xj | ≥ t) with threshold t = τ (β)σ log d for
some function τ (·) > 0. More recently, these asymptotic results were extended to a combined

minimax - Bayes Hamming risk on a certain class of vectors θ in [16].
The present paper makes further steps in the analysis of variable selection with a Hamming
loss initiated in [12, 15]. Unlike [12, 15], we study the sequence model (1) rather than Gaussian
regression and analyze the behavior of the minimax risk rather than that of the Bayes risk with
a specific prior. Furthermore, we consider not only s ∼ d1−β but general s and derive nonasymptotic results that are valid for any sample size. Remarkably, we get an exact expression
for the non-asymptotic minimax risk and find explicitly the minimax selectors. Finally, we
construct data-driven selectors that are simultaneously adaptive to the parameters a and s.
Specifically, we consider the minimax risk
inf sup
η̃ θ∈Θ

1
Eθ |η̃ − η|
s

(3)

e. In
for Θ = Θd (s, a) and Θ = Θ+
d (s, a), where inf η̃ denotes the infimum over all selectors η
Section 2, for both classes Θ = Θ+
d (s, a) and Θ = Θd (s, a) we find the exact values of the
minimax risks and derive minimax selectors for any fixed d, s, a > 0 such that s < d. For

Θ = Θd (s, a) we also propose another selector attaining the minimax risk up to the factor 2.
Interestingly, the thresholds that correspond to the minimax optimal selectors do not have
√
the classical form Aσ log d for some A > 0; the optimal threshold is a function of a and s.
Analogous minimax results are obtained for the risk measured by the probability of wrong
recovery Pθ (Sb 6= S(θ)). Section 3 considers extensions of the non-asymptotic exact minimax
theorems of Section 2 to settings with non-Gaussian or dependent observations. In Section 4,
as asymptotic corollaries of these results, we establish sharp conditions under which exact

and almost full recovery are achievable. Section 5 is devoted to the construction of adaptive
selectors that achieve almost full and exact recovery without the knowledge of the parameters
a and s. Most of the proofs are given in the Appendix.
Finally, note that quite recently several papers have studied the expected Hamming loss
in other problems of variable selection. Asymptotic behavior of the minimax risk analogous
to (3) for classes Θ different from the sparsity classes that we consider here was analyzed in
3

[8] and without the normalizing factor 1/s in [14]. Oracle inequalities for Hamming risks in
the problem of multiple classification under sparsity constraints are established in [22]. The
paper [26] introduces an asymptotically minimax approach based on the Hamming loss in the
problem of community detection in networks.

2

Non-asymptotic minimax selectors

In what follows, we assume that s < d. We first consider minimax variable selection for the
+
class Θ+
d (s, a). For this class, we will use a selector η̂ with the components

η̂j+ = I(Xj ≥ t),

j = 1, . . . , d,

(4)

where the threshold is defined by
t=

a σ2
+
log
2
a




d
−1 .
s

(5)

Set
Ψ+ (d, s, a) =



 

d

d

a
σ
σ
a
d
−1 Φ −
− log
−1
+ log
−1
+Φ −
,
s
2σ
a
s
2σ
a
s

where Φ(·) denotes the standard Gaussian cumulative distribution function.
Theorem 2.1. For any a > 0 and s < d the selector η̂ + in (4) with the threshold t defined in
(5) satisfies

1
Eθ |η̂ + − η| ≤ Ψ+ (d, s, a).
s
+
θ∈Θ (s,a)
sup

(6)

d

The proof is given in the Appendix.
The next theorem gives a lower bound on the minimax risk showing that the upper bound
in Theorem 2.1 is tight.
Theorem 2.2. For any a > 0 and s < d we have
inf
ηe

1
Eθ |e
η − η| ≥ Ψ+ (d, s, a),
θ∈Θ+ (s,a) s
sup
d

where inf ηe denotes the infimum over all selectors ηe.
The proof is given in the Appendix.

As a straightforward corollary of Theorems 2.1 and 2.2, we obtain that the estimator η̂ +
is minimax in the exact sense for the class Θ+
d (s, a) and the minimax risk satisfies
inf

sup

ηe θ∈Θ+ (s,a)
d

1
1
Eθ |e
η − η| = sup
Eθ |η̂ + − η| = Ψ+ (d, s, a).
s
s
+
θ∈Θ (s,a)
d

4

(7)

Remarkably, this holds under no assumptions on d, s, a except for, of course, some minimal
conditions under which the problem ever makes sense: a > 0 and s < d. Analogous nonasymptotic minimax result is valid for the class
Θ−
d (s, a) =

n

θ ∈ Rd : there exists a set S ⊆ {1, . . . , d} with s elements

such that θj ≤ −a for all j ∈ S, and θj = 0 for all j 6∈ S} .

We omit details here.
Next, consider the class Θd (s, a). A direct analog of η̂ + for Θd (s, a) is a selector η̂ with
the components
η̂j = I(|Xj | ≥ t),

j = 1, . . . , d,

(8)

where the threshold t is defined in (5). Set

 
 
d

d
 
d
a
σ
σ
a
Ψ(d, s, a) =
−1 Φ −
− log
−1
− log
−1
+Φ −
,
s
2σ
a
s
2σ
a
s
+
where x+ = max(x, 0). Note that
Ψ(d, s, a) ≤ Ψ+ (d, s, a).

(9)

We have the following bound.
Theorem 2.3. For any a > 0 and s < d the selector η̂ in (8) with the threshold t defined in
(5) satisfies

1
Eθ |η̂ − η| ≤ 2Ψ(d, s, a).
θ∈Θd (s,a) s
sup

(10)

The proof is given in the Appendix.
For the minimax risk on the class Θd (s, a), we have the following corollary, which is an
immediate consequence of Theorems 2.2, 2.3, and inequality (9).
Corollary 2.1. For any a > 0 and s < d the selector η̂ in (8) with the threshold t defined in
(5) satisfies
sup
θ∈Θd (s,a)

Eθ |η̂ − η| ≤ 2 inf

sup

ηe θ∈Θd (s,a)

Eθ |e
η − η|.

(11)

Thus, the risk of the thresholding estimator (8) cannot be greater than the minimax risk
over the class Θd (s, a) multiplied by 2.
We turn now to exact minimax variable selection over the class Θd (s, a). Consider a selector
η = (η 1 , . . . , η d ) with the components

 
 aX 
j
≥t ,
η j = I log cosh
σ2
5

j = 1, . . . , d,

(12)

where the threshold is defined by
t=

a2
+ log
2σ 2




d
−1 .
s

(13)

Set


 

 aξ  d
2
d
− a2
Ψ(d, s, a) =
≥ −1
− 1 P e 2σ cosh
s
σ
s




2
2
a
d
aξ
− a2
2σ
+ 2 < −1 ,
+P e
cosh
σ
σ
s
where ξ denotes a standard Gaussian random variable. Our aim is to show that Ψ(d, s, a) is
the minimax risk of variable selection under the Hamming loss over the class Θd (s, a) and that
it is achieved by the selector in (12). We first prove that Ψ(d, s, a) is an upper bound on the
maximum risk of the selector (12).
Theorem 2.4. For any a > 0 and s < d the selector η in (12) with the threshold t defined in
(13) satisfies

1
Eθ |η − η| ≤ Ψ(d, s, a).
θ∈Θd (s,a) s
sup

The next theorem establishes the lower bound on the minimax risk showing that the upper
bound in Theorem 2.4 cannot be improved.
Theorem 2.5. For any a > 0 and s < d we have
inf
ηe

1
Eθ |e
η − η| ≥ Ψ(d, s, a),
θ∈Θd (s,a) s
sup

where inf ηe denotes the infimum over all selectors ηe.

Next, we discuss a connection to the Bayesian setting. It is not hard to check that, for

each j, the minimax optimal selector η̂j+ coincides with the Bayes test of the null hypothesis
H0 : θj = 0 against the alternative H0 : θj = a with prior probabilities 1 − s/d and s/d,

respectively. This can be also seen from the proof of Theorem 2.2. Furthermore, the minimax
risk on Θ+
d (s, a) is exactly equal to the risk of the corresponding Bayes selector as shown in
the next proposition. Analogous result holds for the class Θd (s, a) but we do not state it here
for the sake of brevity.
Proposition 2.1. Let µ be the uniform distribution on the set Θ′ of all θ in Θ+
d (s, a) such
that s components θj of θ are equal to a and the remaining d − s components are 0. Then,
Z
inf sup Eθ |e
η − η| = inf Eθ |e
η − η|µ(dθ).
(14)
ηe θ∈Θ+ (s,a)
d

ηe

6

The proof is given in the Appendix.
Finally, we show how the above non-asymptotic minimax results can be extended to the
probability of wrong recovery. For any selector ηe, we denote by Sηe the selected set of indices:
Sηe = {j : ηej = 1}. A selector ηe = (e
η1 , . . . , ηed ) will be called separable if its jth component ηej
depends only on Xj for all j = 1, . . . , d. We denote by T the set of all separable selectors.

Theorem 2.6. For any a > 0 and s < d the selectors η̂ in (8) and η̂ + in (4) with the threshold
t defined in (5), and the selector η in (12) with the threshold t defined in (13) satisfy
sup
θ∈Θ+
d (s,a)

Pθ (Sη̂+ 6= S(θ)) ≤ sΨ+ (d, s, a),

(15)

Pθ (Sη 6= S(θ)) ≤ sΨ(d, s, a)

(16)

Pθ (Sη̂ 6= S(θ)) ≤ 2sΨ(d, s, a).

(17)

sup
θ∈Θd (s,a)

and
sup
θ∈Θd (s,a)

Furthermore,
inf

sup

ηe∈T θ∈Θ+ (s,a)
d

Pθ (Sηe 6= S(θ)) ≥

sΨ+ (d, s, a)
,
1 + sΨ+ (d, s, a)

(18)

Pθ (Sηe 6= S(θ)) ≥

sΨ(d, s, a)
.
1 + sΨ(d, s, a)

(19)

and
inf

sup

ηe∈T θ∈Θd (s,a)

The proof is given in the Appendix.
Although Theorem 2.6 does not provide the exact minimax solution, it implies sharp
minimaxity in asymptotic sense. Indeed, an interesting case is when the minimax risk in
Theorem 2.6 goes to 0 as d → ∞. Assuming that s and a are functions of d, this corresponds

to sΨ+ (d, s, a) → 0 as d → ∞. In this natural asymptotic setup, the upper and lower bounds

of Theorem 2.6 for both classes Θ+
d (s, a) and Θd (s, a) are sharp. We discuss this issue in
Section 4, cf. Theorem 4.5.

Remark 2.1. Papers [12, 15, 16] use a different Hamming loss defined in terms of vectors of signs. In our setting, this would mean considering not |η̂ − η| but the following loss:
Pd
j=1 I(sign(θ̂j ) 6= sign(θj )), where θ̂j is an estimator of θj and sign(x) = I(x > 0) − I(x < 0).

Theorems of this section are easily adapted to such a loss, but in this case the corresponding

expressions for the non-asymptotic risk contain additional terms and we do not obtain exact minimax solutions as above. On the other hand, these additional terms are smaller than
Ψ(d, s, a) and Ψ+ (d, s, a), and in the asymptotic analysis, such as the one performed in Sections 4 and 5, can often be neglected. Thus, in many cases, one gets the same asymptotic
results for both losses. We do not discuss this issue in more detail here.

7

3

Generalizations and extensions

Before proceeding to asymptotic corollaries, we discuss some generalizations and extensions of
the non-asymptotic results of Section 2.

3.1

Dependent observations

It is easy to see that Theorems 2.1 and 2.3 do not use any information on the dependence
between the observations and thus remain valid for dependent Xj . Furthermore, a minimax
optimality property holds under dependence as well. To be specific, denote by Nd (θ, Σ) the

d-dimensional Gaussian distribution with mean θ and covariance matrix Σ. Assume that the

distribution P of (X1 , . . . , Xd ) belongs to the class
2
Pd+ (s, a, σ 2 ) = {Nd (θ, Σ) : θ ∈ Θ+
d (s, a), σii = σ , for all i = 1, . . . , d}

where we denote by σii the diagonal entries of Σ. Note that, for distributions in this class,
Σ can be any covariance matrix with constant diagonal elements.
Theorem 3.1. For any a > 0 and s < d, and for the selector η̂ + in (4) with the threshold t
defined in (5) we have
inf

sup

ηe P∈P + (s,a,σ2 )
d

EP |e
η − η| =

sup
P∈Pd+ (s,a,σ2 )

EP |η̂ + − η| = sΨ+ (d, s, a),

where inf ηe denotes the infimum over all selectors ηe, and EP denotes the expectation with
respect to P.

Proof. The upper bound Ψ+ (d, s, a) on the minimax risk follows from the fact that the proofs
of Theorems 2.1 and 2.3 are not affected by the dependence. Indeed, both the selector and the
Hamming loss proceed coordinate-wisely. The lower bound Ψ+ (d, s, a) on the minimax risk
follows from Theorem 2.2 after observing that the maximum over Pd+ (s, a, σ 2 ) is greater than

the maximum over the subfamily of Gaussian vectors with independent entries {Nd (θ, σ 2 Id ) :
θ ∈ Θ+
d (s, a)}, where Id is the d × d identity matrix.

An interesting consequence of Theorem 3.1 and of (7) is that the model with independent
Xj is the least favorable model, in the exact non-asymptotic sense, for the problem of variable
selection with Hamming loss on the class of vectors Θ+
d (s, a).
This fact was also noticed and discussed in [13] for the detection problem. That paper
considers the Gaussian model with covariance matrix Σ that is not necessarily a diagonal matrix. It is shown that faster detection rates are achieved in the case of dependent observations
(under some assumptions) than in the case of independent data. It would be interesting to
extend these results to the variable selection problem in hand.
8

3.2

Non-Gaussian models

As a building block for extension to non-Gaussian observations, we first consider the following
simple model. We observe independent random variables X1 , . . . , Xd with values in a measurable space (X , U ) such that s among them are distributed according to the probability

distribution P1 and the other d − s are distributed according to the probability distribution
P0 . We assume that P0 6= P1 . Let f0 and f1 be densities of P0 and P1 with respect to some

dominating measure. Denote by η = (η1 , . . . , ηd ) the vector such that ηj = 1 if the distribution
of Xj is P1 and ηj = 0 if it is P0 . Let Θd (s, f0 , f1 ) be the set of all such vectors η. Consider
the selector η̂ = (η̂1 , . . . , η̂d ) where



f1
d
η̂j = I log (Xj ) ≥ log
−1
,
f0
s

j = 1, . . . , d.

(20)

Theorem 3.2. For any s < d, the selector η̂ in (20) satisfies
sup
η∈Θd (s,f0 ,f1 )

E|η̂ − η| = inf

sup

η̃ η∈Θ (s,f0 ,f1 )
d

E|η̃ − η| = sΨ,

(21)

where inf η̃ denotes the infimum over all selectors, and
d
  d
 
d


f1
f1
−1 +
− 1 P0 log (X) ≥ log
−1 .
Ψ = P1 log (X) < log
f0
s
s
f0
s

(22)

Proof. The proof of the upper bound supη∈Θd (s,f0 ,f1 ) E|η̂ − η| ≤ sΨ is obvious. The proof
of the lower bound inf η̃ supη∈Θd (s,f0 ,f1 ) E|η̃ − η| ≥ sΨ follows the same lines as the proof of

Theorem 2.2 with the only difference in the definition of probability measures. We replace
the Gaussian distributions centered at 0 and a by the distributions P0 and P1 , respectively.
With this change, the Bayesian version of the Neyman-Pearson lemma leads to the optimal
test statistic T ∗ of the form
T ∗ (X) = I




(s/d)f1 (X)
>1 ,
(1 − s/d)f0 (X)

and, respectively, to the lower bound (22) on the minimax risk.
Suppose now that instead of two measures P0 and P1 we have a parametric family of
probability measures {Pa , a ∈ U } where U ⊆ R. Let f a be a density of Pa with respect to
some dominating measure. Recall that the family {fa , a ∈ U } is said to have the Monotone

Likelihood Ratio (MLR) property if, for all a0 , a1 in U such that a0 < a1 , the log-likelihood

ratio log(fa1 (X)/fa0 (X)) is an increasing function of X. In particular, this implies, cf. [18,

Lemma 3.4.2] that {fa , a ∈ U } is a stochastically ordered family, i.e.,
Fa (x) ≥ Fa′ (x) for all x

9

if a < a′

(23)

where Fa is the cumulative distribution function corresponding to fa . Using these facts, we
generalize the non-asymptotic results of the previous section in two ways. First, we allow for
not necessarily Gaussian distributions and second, instead of the set of parameters Θ+
d (s, a),
we consider the following set with two restrictions:
n
(s,
a
,
a
)
=
θ ∈ Rd : there exists a set S ⊆ {1, . . . , d} with s elements
Θ+
0
1
d
such that θj ≥ a1 for all j ∈ S, and θj ≤ a0 for all j 6∈ S}

where a0 < a1 . In what follows, we use the notation fj = faj , j = 0, 1.
Theorem 3.3. Let {fa , a ∈ U } be a family with the MLR property, and let a0 , a1 ∈ U be such
that a0 < a1 . Then, for any s < d, the selector η̂ in (20) with f0 = fa0 and f1 = fa1 satisfies
sup
θ∈Θ+
d (s,a0 ,a1 )

Eθ |η̂ − η| = inf
η̃

sup
θ∈Θ+
d (s,a0 ,a1 )

Eθ |η̃ − η| = sΨ,

where inf η̃ denotes the infimum over all selectors and Ψ is given in (22).
Proof. We have

d

f1
sup Pa log (X) < log
−1
f0
s
a≥a1
 
d

d
f1
+ sup
− 1 Pa log (X) ≥ log
− 1 = Ψ,
f0
s
a≤a0 s

1
Eθ |η̂ − η| =
θ∈Θ+ (s,a0 ,a1 ) s
sup

d

where the last equality is due to the monotonicity of log ff10 (X) and to the stochastic order
property (23). The proof of the lower bound
inf
η̃

sup
θ∈Θ+
d (s,a0 ,a1 )

1
Eθ |η̃ − η| ≥ Ψ
s

follows from the fact supθ∈Θ+ (s,a0 ,a1 ) Eθ |η̃ − η| ≥ supη∈Θd (s,f0 ,f1 ) E|η̃ − η| and Theorem 3.2.
d

Example 1. Let fa be the Gaussian N (a, σ 2 ) density with some σ 2 > 0, and let a0 < a1 .

For f1 = fa1 and f0 = fa0 , the log-likelihood ratio
log

a1 − a0 a21 − a20
f1
(X) = X
−
f0
σ2
2σ 2

is increasing in X. By Theorem 3.3, the minimax optimal selector η̂ on the class Θ+
d (s, a0 , a1 )
is a vector with components
η̂j = I (Xj ≥ t(a0 , a1 )) , j = 1, . . . , d,
where
t(a0 , a1 ) =

a1 + a0 σ 2 log(d/s − 1)
+
.
2
a1 − a0
10

(24)

Note that for a0 = 0 it coincides with the selector in (4) with a = a1 , which is minimax optimal
on Θ+
d (s, a1 ). Moreover, the minimax risk only depends on a0 and a1 through the difference
δ = a1 − a0 :

 δ σ 2 log(d/s − 1)   d
  δ σ 2 log(d/s − 1) 
Ψ=Φ − +
+
.
−1 Φ − +
2
δ
s
2
δ

Example 2 Let Pa be the Bernoulli distribution B(a) with parameter a ∈ (0, 1), and

0 < a0 < a1 < 1. Denoting by fa the density of Pa with respect to the counting measure we
have, for f1 = fa1 and f0 = fa0 ,
log

 a
f1
1 − a0 
1 − a1
1
(X) = X log
+ log
f0
1 − a1 a0
1 − a0

which is increasing in X for 0 < a0 < a1 < 1. The minimax optimal selector η̂ on the class
Θ+
d (s, a0 , a1 ) is a vector with components η̂j in (24) where the threshold t(a0 , a1 ) is given by
t(a0 , a1 ) =

log( ds − 1) − log

1−a1
1−a0

a1 1−a0
log( 1−a
)
1 a0

.

Note that the minimax selector η̂j differs from the naive selector η̂jn = Xj . Indeed since
Xj ∈ {0, 1} we have η̂j = 1 if either Xj = 1 or t(a0 , a1 ) ≤ 0, and η̂j = 0 if either Xj = 0 or

t(a0 , a1 ) > 1. The value Ψ in the minimax risk has the form
d
Ψ = Pa1 (X < t(a0 , a1 )) +
s



 d/s − 1,
=
1 − a1 + a0 (d/s − 1),


 1,


− 1 Pa0 (X ≥ t(a0 , a1 ))
t(a0 , a1 ) ≤ 0,

0 < t(a0 , a1 ) < 1,
t(a0 , a1 ) ≥ 1.

In the asymptotic regime when d → ∞ and s → ∞, the minimax risk sΨ can converge to

0 only when the parameters d, s, a0 , a1 are kept such that 0 < t(a0 , a1 ) < 1, and in addition
(1 − a1 )s → 0, a0 (d − s) → 0. Thus, the risk can converge to 0 only when the Bernoulli

probabilities a1 and a0 tend sufficiently fast to 1 and to 0, respectively.

Example 3. Let Pa be the Poisson distribution with parameter a > 0, and let a1 > a0 > 0.
Denoting by fa the density of Pa with respect to the counting measure we have
a 
f1
1
− a1 + a0 ,
log (X) = X log
f0
a0
which is increasing in X. The components of the minimax optimal selector η̂ are given by (24)
with
t(a0 , a1 ) =

log(d/s − 1) + a1 − a0
.
log(a1 /a0 )

Note that t(a0 , a1 ) > 0 as soon as d/s ≥ 2 and a1 > a0 > 0. The minimax risk has the form
Ψ = Pa1 (X < t(a0 , a1 )) + (d/s − 1)Pa0 (X ≥ t(a0 , a1 )).
11

3.3

Crowdsourcing with sparsity constraint

The problem of crowdsourcing with two classes is a clustering problem that can be formalized
as follows, cf. [11]. Assume that m workers provide class assignments for d items. The class
assignment Xij of the ith worker for the jth item is assumed to have a Bernoulli distribution
B(ai0 ) if the jth item belongs to class 0, and a Bernoulli distribution B(ai1 ) if it belongs to class
1. Here, ai0 , ai1 ∈ (0, 1) and ai0 6= ai1 for i = 1, . . . , m. The observations (Xij , i = 1, . . . , m, j =

1, . . . , d) are assumed to be jointly independent. Thus, each vector Xj = (X1j , . . . , Xmj ) is
distributed according to P0 or to P1 where each of these two measures is a product of Bernoulli
measures, and P0 6= P1 . We assume that there are s vectors Xj with distribution P1 , and

d − s vectors Xj with distribution P0 . The aim is to recover the binary vector of class labels

η = (η1 , . . . , ηd ) based on the observations X = (X1 , . . . , Xd ). Here, ηj ∈ {0, 1} satisfies ηj = k

if the jth item belongs to class k ∈ {0, 1}. Thus, we are in the framework of Theorem 3.2 with

a particular form of the log-likelihood ratio

m 
 a
X
f1
1 − ai1
1 − ai0 
i1
log (Xj ) =
+ log
,
Xij log
f0
1 − ai1 ai0
1 − ai0

(25)

i=1

where fk is the density of Pk , k ∈ {0, 1}. The following corollary is an immediate consequence
of Theorem 3.2.

Corollary 3.1. Let s < d, ai0 , ai1 ∈ (0, 1) and ai0 6= ai1 for i = 1, . . . , m. Then, the selector
η̂ in (20) with log

f1
f0 (Xj )

defined in (25) is minimax optimal on the class Θd (s, f0 , f1 ). The

corresponding minimax risk is given in (22).
Thus, a selector which is minimax optimal in the exact non-asymptotic sense is explicitly
given by formula (20). For suitable combinations of parameters d, s, ai0 , ai1 , the exact value of
the minimax risk Ψ can be further analyzed to obtain asymptotics of interest. Gao et al. [11]
have studied a setting of crowdsourcing problem which is different from the one we consider
here. They did not assume sparsity s, and instead of the class Θd (s, f0 , f1 ) of s-sparse binary
sequences, they considered the class of all possible binary sequences {0, 1}d . For this class, Gao
et al. [11] did not derive the exact minimax solution but rather analyzed specific asymptotics
of the minimax risk inf η̃ supη∈{0,1}d d−1 E|η̃ − η| in large deviations perspective.

4

Asymptotic analysis. Phase transitions

In this section, we conduct the asymptotic analysis of the problem of variable selection. The
results are derived as corollaries of the minimax bounds of Section 2. We will assume that
d → ∞ and that parameters a = ad and s = sd depend on d.

The first two asymptotic properties we study here are exact recovery and almost full re-

covery. We use this terminology following [12, 15] but we define these properties in a different
12

way, as asymptotic minimax properties for classes of vectors θ. The papers [12, 15] considered
a Bayesian setup with random θ and studied a linear regression model with i.i.d. Gaussian
regressors rather than the sequence model (1).
The study of exact recovery and almost full recovery will be done here only for the classes
−
Θd (sd , ad ). The corresponding results for the classes Θ+
d (sd , ad ) or Θd (sd , ad ) are completely

analogous. We do not state them here for the sake of brevity.
Definition 4.1. Let (Θd (sd , ad ))d≥1 be a sequence of classes of sparse vectors.
• We say that exact recovery is possible for (Θd (sd , ad ))d≥1 if there exists a selector η̂
such that

lim

sup

d→∞ θ∈Θ (s ,a )
d d d

Eθ |η̂ − η| = 0.

(26)

In this case, we say that η̂ achieves exact recovery.
• We say that almost full recovery is possible for (Θd (sd , ad ))d≥1 if there exists a
selector η̂ such that

1
Eθ |η̂ − η| = 0.
d→∞ θ∈Θd (sd ,ad ) sd
lim

sup

(27)

In this case, we say that η̂ achieves almost full recovery.
It is of interest to characterize the sequences (sd , ad )d≥1 , for which exact recovery and
almost full recovery are possible. To describe the impossibility of exact or almost full recovery,
we need the following definition.
Definition 4.2. Let (Θd (sd , ad ))d≥1 be a sequence of classes of sparse vectors.
• We say that exact recovery is impossible for (Θd (sd , ad ))d≥1 if
lim inf inf
d→∞

sup

η̃ θ∈Θ (s ,a )
d d d

Eθ |η̃ − η| > 0,

(28)

• We say that almost full recovery is impossible for (Θd (sd , ad ))d≥1 if
lim inf inf
d→∞

sup

η̃ θ∈Θ (s ,a )
d d d

1
Eθ |η̃ − η| > 0,
sd

(29)

where inf η̃ denotes the infimum over all selectors.
The following general characterization theorem is a straightforward corollary of the results
of Section 2.

13

Theorem 4.1.

(i) Almost full recovery is possible for (Θd (sd , ad ))d≥1 if and only if
Ψ+ (d, sd , ad ) → 0

as d → ∞.

(30)

In this case, the selector η̂ defined in (8) with threshold (5) achieves almost full recovery.
(ii) Exact recovery is possible for (Θd (sd , ad ))d≥1 if and only if
sd Ψ+ (d, sd , ad ) → 0

as d → ∞.

(31)

In this case, the selector η̂ defined in (8) with threshold (5) achieves exact recovery.
Although this theorem gives a complete solution to the problem, conditions (30) and (31)
are not quite explicit. Intuitively, we would like to get a “phase transition” values a∗d such
that exact (or almost full) recovery is possible for ad greater than a∗d and is impossible for ad
smaller than a∗d . Our aim now is to find such “phase transition” values. We first do it in the
almost full recovery framework.
The following bounds for the tails of Gaussian distribution will be useful:
r
r
Z ∞
2
2
e−y /2
e−y /2
2
1
2
−u2 /2
p
p
,
e
du ≤
<√
π y + y2 + 4
π y + y 2 + 8/π
2π y

(32)

for all y ≥ 0. These bounds are an immediate consequence of formula 7.1.13. in [3] with
√
x = y/ 2.
Furthermore, we will need some non-asymptotic bounds for the expected Hamming loss
that will play a key role in the subsequent asymptotic analysis. They are given in the next
theorem.
Theorem 4.2. Assume that s < d/2.
(i) If



a2 ≥ σ 2 2 log((d − s)/s) + W for some W > 0,

then the selector η̂ defined in (8) with threshold (5) satisfies
√
sup Eθ |η̂ − η| ≤ (2 + 2π)s Φ(−∆),

(33)

(34)

θ∈Θd (s,a)

where ∆ is defined by

(ii) If a > 0 is such that

then

W
∆= p
.
2 2 log((d − s)/s) + W



a2 ≤ σ 2 2 log((d − s)/s) + W for some W > 0,
inf

sup

ηe θ∈Θd (s,a)

Eθ |e
η − η| ≥ s Φ(−∆),

where the infimum is taken over all selectors ηe and ∆ > 0 is defined in (35).
14

(35)

(36)

(37)

The proof is given in the Appendix.
The next theorem is an easy consequence of Theorem 4.2. It describes a “phase transition”
for ad in the problem of almost full recovery.
Theorem 4.3. Assume that lim supd→∞ sd /d < 1/2.
(i) If, for all d large enough,


p
a2d ≥ σ 2 2 log((d − sd )/sd ) + Ad 2 log((d − sd )/sd )

for an arbitrary sequence Ad → ∞, as d → ∞, then the selector η̂ defined by (8) and (5)
achieves almost full recovery:

1
Eθ |η̂ − η| = 0.
d→∞ θ∈Θd (sd ,ad ) sd
lim

sup

(ii) Moreover, if there exists A > 0 such that for all d large enough the reverse inequality
holds:



p
a2d ≤ σ 2 2 log((d − sd )/sd ) + A 2 log((d − sd )/sd )

then almost full recovery is impossible:
lim inf inf
η̃

d→∞

 A
1
> 0.
Eθ |η̃ − η| ≥ Φ −
2
θ∈Θd (sd ,ad ) sd
sup

Here, inf η̃ is the infimum over all selectors ηe.

The proof is given in the Appendix.

Under the natural sparsity assumption that
d/sd → ∞

as

d → ∞,

(38)

Theorem 4.3 shows that the “phase transition” for almost full recovery occurs at the value
ad = a∗d , where
a∗d = σ

p



2 log((d − sd )/sd ) 1 + o(1) .

(39)

Furthermore, Theorem 4.3 details the behavior of the o(1) term here.
We now state a corollary of Theorem 4.3 under simplified assumptions.
Corollary 4.1. Assume that (38) holds and set
ad = σ

p

2(1 + δ) log(d/sd ),

for some δ > 0.

Then the selector η̂ defined by (8) with threshold t = σ
depends only on δ, achieves almost full recovery.
15

p

2(1 + ε(δ)) log(d/sd ) where ε(δ) > 0

In the particular case of sd = d1−β (1 + o(1)) for some β ∈ (0, 1), condition (38) is

satisfied. Then log(d/sd ) = β(1 + o(1)) log d and it follows from Corollary 4.1 that for
p
p

ad = σ 2β(1 + δ) log d the selector with components η̂j = I |Xj | > σ 2β(1 + ε) log d
achieves almost full recovery. This is in agreement with the findings of [12, 15] where an

analogous particular case of sd was considered for a different model and the Bayesian definition of almost full recovery.
We now turn to the problem of exact recovery. First, notice that if
lim sup sd < ∞
d→∞

the properties of exact recovery and almost full recovery are equivalent. Therefore, it suffices
to consider exact recovery only when sd → ∞ as d → ∞. Under this assumption, the “phase

transition” for ad in the problem of exact recovery is described in the next theorem.
Theorem 4.4. Assume that sd → ∞ as d → ∞, and lim supd→∞ sd /d < 1/2.
(i) If



a2d ≥ σ 2 2 log((d − sd )/sd ) + Wd

for all d large enough, where the sequence Wd is such that

Wd
 ≥ 1,
lim inf 
p
d→∞ 4 log(s ) +
log(s
)
log(d
−
s
)
d
d
d

(40)

then the selector η̂ defined by (8) and (5) achieves exact recovery:
lim

sup

d→∞ θ∈Θd (sd ,ad )

Eθ |η̂ − η| = 0.

(41)

(ii) If the complementary condition holds:


a2d ≤ σ 2 2 log((d − sd )/sd ) + Wd
for all d large enough, where the sequence Wd is such that
Wd
 < 1,
lim sup 
p
d→∞ 4 log(sd ) +
log(sd ) log(d − sd )

then exact recovery is impossible, and moreover we have
lim inf

d→∞

sup

ηe θ∈Θd (sd ,ad )

Here, inf ηe is the infimum over all selectors ηe.
16

Eθ |e
η − η| = ∞.

(42)

The proof is given in the Appendix.
Some remarks are in order here. First of all, Theorem 4.4 shows that the “phase transition”


p
for exact recovery occurs at Wd = 4 log(sd ) + log(sd ) log(d − sd ) , which corresponds to

the critical value ad = a∗d of the form
p

p
a∗d = σ
2 log(d − sd ) + 2 log sd .

(43)

This value is greater than the critical value a∗d for almost full recovery, cf. (39), which is

intuitively quite clear. The optimal threshold (5) corresponding to (43) has a simple form:


p
a∗d σ 2
d
∗
td =
+ ∗ log
− 1 = σ 2 log(d − sd ).
2
ad
sd
√
√
For example, if sd = d1−β (1 + o(1)) for some β ∈ (0, 1), then a∗d ∼ σ(1 + 1 − β) 2 log d. In
p
√
this particular case, Theorem 4.4 implies that if ad = σ(1 + 1 − β) 2(1 + δ) log d for some
p
δ > 0, then exact recovery is possible and the selector with threshold t = σ 2(1 + ε) log d for

some ε > 0 achieves exact recovery. This is in agreement with the results of [12, 15] where
an analogous particular case of sd was considered for a different model and the Bayesian

definition of exact recovery. For our model, even a sharper result is true; namely, a simple
√
universal threshold t = σ 2 log d guarantees exact recovery adaptively in the parameters a
and s. Intuitively, this is suggested by the form of t∗d . The precise statement is given in
Theorem 5.1 below.
Finally, we state an asymptotic corollary of Theorem 2.6 showing that the selector η̂ considered above is sharp in the asymptotically minimax sense with respect to the risk defined as
the probability of wrong recovery.
Theorem 4.5. Assume that exact recovery is possible for the classes (Θd (sd , ad ))d≥1 and
+
(Θ+
d (sd , ad ))d≥1 , that is, condition (31) holds. Then, for the selectors η̂ and η̂ defined by (8),

(4) and (5), and for the selector η defined by (12) and (13), we have
Pθ (Sη̂+ 6= S(θ))
= lim inf
d→∞
d→∞ ηe∈T
θ∈Θ+ (sd ,ad ) sd Ψ+ (d, sd , ad )
lim

sup
d

Pθ (Sη 6= S(θ))
= lim inf
d→∞ θ∈Θ (s ,a ) sd Ψ(d, sd , ad )
d→∞ ηe∈T
d d d
lim

sup

Pθ (Sηe 6= S(θ))
= 1,
θ∈Θ+ (sd ,ad ) sd Ψ+ (d, sd , ad )
sup
d

Pθ (Sηe 6= S(θ))
= 1,
θ∈Θd (sd ,ad ) sd Ψ(d, sd , ad )
sup

and
lim sup
d→∞

Pθ (Sη̂ 6= S(θ))
≤ 2.
θ∈Θd (sd ,ad ) sd Ψ+ (d, sd , ad )
sup

Note that the threshold (5) depends on the parameters s and a, so that the selectors
considered in all the results above are not adaptive. In the next section, we propose adaptive
selectors that achieve almost full recovery and exact recovery without the knowledge of s and a.
17

Remark 4.1. Another procedure of variable selection is the exhaustive search estimator of the
support S(θ) defined as
S̃ =

argmax

X

Xj .

C⊆{1,...,d}:|C|=s j∈C

This estimator was studied by Butucea et al. [7]. The selection procedure can be equivalently stated as choosing the indices j corresponding to s largest order statistics of the sample
(X1 , . . . , Xd ). In [7, Theorem 2.5], it was shown that, on the class Θ+
d (sd , ad ), the probability
of wrong recovery Pθ (S̃ 6= S(θ)) tends to 0 as d → ∞ under a stronger condition on (sd , ad )
than (31). The rate of this convergence was not analyzed there. If we denote by ηS̃ the selector

with components I(j ∈ S̃) for j from 1 to d, it can be proved that E|ηS̃ − η| ≤ 2E|η̂ + − η| and

thus the risk of ηS̃ is within the factor 2 of the minimax risk over the class Θ+
d (s, a). Thus,

it does not enjoy the non-asymptotic sharp optimality that we have established for the selector
defined by (4) and (5) over the class Θ+
d (s, a) and for the selector defined by (12) and (13)
over the class Θd (s, a).

5

Adaptive selectors

In this section, we consider the asymptotic setup as in Section 4 and construct the selectors
that provide almost full and exact recovery adaptively, that is, without the knowledge of a
and s.
As discussed in Section 4, the issue of adaptation for exact recovery is almost trivial.
Indeed, the expressions for minimal value a∗d , for which exact recovery is possible (cf. (43)),
and for the corresponding optimal threshold t∗d suggest that taking a selector with the universal
√
threshold t = σ 2 log d is enough to achieve exact recovery simultaneously for all values
(ad , sd ), for which the exact recovery is possible. This point is formalized in the next theorem.
Theorem 5.1. Assume that sd → ∞ as d → ∞ and that lim supd→∞ sd /d < 1/2. Let the

sequence (ad )d≥1 be above the phase transition level for exact recovery, that is, ad ≥ a∗d for all
√
d, where a∗d is defined in (43). Then the selector η̂ defined by (8) with threshold t = σ 2 log d
achieves exact recovery.
The proof of this theorem is given in the Appendix.
We now turn to the problem of adaption for almost full recovery. Ideally, we would like to
construct a selector that achieves almost full recovery for all sequences (sd , ad )d≥1 for which
almost full recovery is possible. We have seen in Section 4 that this includes a much broader
range of values than in case of exact recovery. Thus, using the adaptive selector of Theorem 5.1
for almost full recovery does not give a satisfactory result, and we have to take a different
approach.

18

Following Section 4, we will use the notation

1/2
p
a0 (s, A) , σ 2 log((d − s)/s) + A log((d − s)/s)
.

As shown in Section 4, it makes sense to consider the classes Θd (s, a) only when a ≥ a0 (s, A)

with some A > 0, since for other values of a almost full recovery is impossible. Only such
classes will be studied below.
In the asymptotic setup of Section 4 we have used the assumption that d/sd → ∞ (the

sparsity assumption), which is now transformed into the condition
sd ∈ Sd , {1, 2, . . . , s∗d } where s∗d is an integer such that

d
→ ∞ as d → ∞.
s∗d

(44)

Assuming sd to be known, we have shown in Section 4 that almost full recovery is achievable for
all a ≥ a0 (sd , Ad ), where Ad tends to infinity as d → ∞. The rate of growth of Ad was allowed

to be arbitrarily slow there, cf. Theorem 4.3. However, for adaptive estimation considered in
this section we will need the following mild assumption on the growth of Ad :


Ad ≥ c0 log log



1/2
d
,
−1
s∗d

(45)

where c0 > 0 is an absolute constant. In what follows, we will assume that s∗d ≤ d/4, so that

the right-hand side of (45) is well-defined.

Consider a grid of points {g1 , . . . , gM } on Sd , where gj = 2j−1 and M is the maximal

integer such that gM ≤ s∗d . For each gm , m = 1, . . . , M , we define a selector
η̂(gm ) = (η̂j (gm ))j=1,...,d , (I(|Xj | ≥ w(gm )))j=1,...,d ,
where
w(s) = σ

r

2 log

d
s


−1 .

Note that w(s) is monotonically decreasing. We now choose the “best” index m, for which gm
is near the true (but unknown) value of s, by the following data-driven procedure:
n
m
b = min m ∈ {2, . . . , M } :
d
X
j=1

o

I w(gk ) ≤ |Xj | < w(gk−1 ) ≤ τ gk for all k ≥ m ,

where
τ = log (d/s∗d − 1)

− 1
7

,

and we set m
b = M if the set in (46) is empty. Finally, we define an adaptive selector as
η̂ ad = η̂(gm
b ).
19

(46)

This adaptive procedure is quite natural in the sense that it can be related to the Lepski
method or to wavelet thresholding that are widely used for adaptive estimation. Indeed, as
in wavelet methods, we consider dyadic blocks determined by the grid points gj . The value

Pd
j=1 I w(gk ) ≤ |Xj | < w(gk−1 ) is the number of observations within the kth block. If this

number is too small (below a suitably chosen threshold) we decide that the block corresponds
to pure noise and it is rejected; in other words, this k is not considered as a good candidate
for m.
b This argument is analogous to wavelet thersholding. We start from the largest k

(equivalently, smallest w(gk )) and perform this procedure until we find the first block, which
is not rejected. The corresponding value k determines our choice of m
b as defined in (46).

Theorem 5.2. Let c0 ≥ 16. Then the selector η̂ ad adaptively achieves almost full recovery in
the following sense:

1
Eθ |η̂ ad − η| = 0
d→∞ θ∈Θd (sd ,ad ) sd
lim

sup

(47)

for all sequences (sd , ad )d≥1 such that (44) holds and ad ≥ a0 (sd , Ad ), where Ad satisfies (45).
Remark 5.1. Another family of variable selection methods originates from the theory of multiple testing. These are, for example, the Benjamini-Hochberg, Benjamini-Yekutieli or SLOPE
procedures. We refer to [6] for a recent overview and comparison of these techniques. They
have the same structure as the exhaustive search procedure in that they keep only the largest
order statistics. The difference is that the value s (which is usually not known in practice) is
replaced by an estimator ŝ obtained from comparing the ith order statistic of (|X1 |, . . . , |Xd |)

with a suitable normal quantile depending on i. The analysis of these methods in the literature

is focused on the evaluation of false discovery rate (FDR). Asymptotic power calculations for
the Benjamini-Hochberg procedure are given in [4]. To the best of our knowledge, the behavior
of the risk Pθ (S̃ 6= S(θ)) and of the Hamming risk, even in a simple consistency perspective,
was not studied.

Remark 5.2. In this paper, the variance σ was supposed to be known. Extension to the case
of unknown σ can be treated as described, for example, in [9]. Namely, we replace σ in the
definition of the threshold w(s) by a statistic σ̂ defined in [9, Section 3]. As shown in [9,
Proposition 1], this statistic is such that σ ≤ σ̂ ≤ C ′ σ with high probability provided that
s ≤ d/2, and d ≥ d0 for some absolute constants C ′ > 1, d0 ≥ 1. Then, replacing σ by σ̂

in the expression for w(s), one can show that Theorem 5.2 remains valid with this choice of
w(s) independent of σ, up to a change in numerical constants in the definition of the adaptive
procedure. With this modification, we obtain a procedure which is completely data-driven and
enjoys the property of almost full recovery under the mild conditions given in Theorem 5.2. The
same modification can be done in Theorem 5.1. Namely, under the assumptions of Theorem 5.1

and ad ≥ c′ a∗d , where c′ ≥ 1 is a numerical constant, the selector η̂ defined by (8) with threshold
√
t = σ̂ 2 log d achieves exact recovery when σ is unknown.
20

Remark 5.3. In this section, the problem of adaptive variable selection was considered only
−
for the classes Θd (sd , ad ). The corresponding results for classes Θ+
d (sd , ad ) and Θd (sd , ad ) are

completely analogous. We do not state them here for the sake of brevity.

6

Appendix

Proof of Theorem 2.3. We have, for any t > 0,
|η̂ − η| =

X

η̂j +

j:ηj =0

=

X

j:ηj =0

X

(1 − η̂j )

j:ηj =1

I(|σξj | ≥ t) +

X

j:ηj =1

I(|σξj + θj | < t).

Now, for any θ ∈ Θd (s, a) and any t > 0,
E (I (|σξj + θj | < t)) ≤ P(|θj | − |σξj | < t) ≤ P(|ξ| > (a − t)/σ)
= P(|ξ| > (a − t)+ /σ),
where ξ denotes a standard Gaussian random variable. Thus, for any θ ∈ Θd (s, a),




1
d
t
(a − t)+
Eθ |η̂ − η| ≤
− 1 P(|ξ| ≥ ) + P |ξ| >
= 2Ψ(d, s, a).
s
s
σ
σ

(48)

Note that the inequality here is valid for any t > 0, not necessarily for t defined in (5).
Proof of Theorem 2.1. Arguing as in the proof of Theorem 2.3, we obtain
|η̂ + − η| =

X

j:ηj =0

I(ξj ≥ t) +

X

I(σξj + θj < t),

j:ηj =1

and E (I (σξj + θj < t)) ≤ P(ξ < (t − a)/σ). Thus, for any θ ∈ Θ+
d (s, a),


1
d
+
Eθ |η̂ − η| ≤
− 1 P(ξ ≥ t/σ) + P(ξ < (t − a)/σ) = Ψ+ (d, s, a).
s
s

Proof of Theorem 2.2. An estimator η̄ = (η̄1 , . . . , η̄d ) of η (not necessarily a selector) will
be called separable if η̄j depends only on Xj for all j = 1, . . . , d. First note that instead of
considering all selectors, it suffices to prove the lower bound for the class of separable estimators
η̄ with components η̄j ∈ [0, 1]. Indeed, for any selector ηe, using Jensen’s inequality, we obtain
Eθ |e
η − η| =

d
X
j=1

Eθ |e
ηj − ηj | =

d
X
j=1

Ej,θj E{θi ,i6=j} |e
ηj − ηj | ≥

21

d
X
j=1

Ej,θj |η̄j − ηj |

where η̄j = E{θi ,i6=j} (e
ηj ), and the symbols Ej,θj and E{θi ,i6=j} stand for the expectations over
the distributions of Xj and (X1 , . . . , Xj−1 , Xj+1 , . . . , Xd ), respectively. Clearly, η̄j depends
only on Xj and takes on values in [0, 1]. Thus,
inf
ηe

1
Eθ |e
η − η| ≥ inf
η̄∈T[0,1]
θ∈Θ+ (s,a) s
sup
d

d

1X
Ej,θj |η̄j − ηj |
θ∈Θ+ (s,a) s
sup

(49)

j=1

d

where T[0,1] is the class of all separable estimators η̄ with components η̄j ∈ [0, 1].

Let Θ′ be the set of all θ in Θ+
d (s, a) such that s components θj of θ are equal to a and the

remaining d − s components are 0. Denote by |Θ′ | = ds the cardinality of Θ′ . Then, for any
η̄ ∈ T[0,1] we have

d
d
1 XX
1X
Ej,θj |η̄j − ηj | ≥
Ej,θj |η̄j − ηj |
s|Θ′ |
′
θ∈Θ+ (s,a) s

sup

j=1

d

=

1
s|Θ′ |

d 
X
j=1

X

(50)

θ∈Θ j=1

Ej,0 (η̄j ) +

θ∈Θ′ :θj =0

X

θ∈Θ′ :θj =a


Ej,a (1 − η̄j )

d

s
s
1 X 
Ej,0 (η̄j ) + Ej,a (1 − η̄j )
1−
=
s
d
d
j=1



s
s
d
E0 (T ) + Ea (1 − T ) ,
inf
1−
≥
s T ∈[0,1]
d
d

′
where we have used that |{θ ∈ Θ′ : θj = a}| = d−1
s−1 = s|Θ |/d. In the last line of display (50),

Eu is understood as the expectation with respect to the distribution of X = u + σξ, where

ξ ∼ N (0, 1) and inf T ∈[0,1] denotes the infimum over all [0, 1]-valued statistics T (X). Set


s
s
L∗ = inf
1−
E0 (T ) + Ea (1 − T )
d
d
T ∈[0,1]

By the Bayesian version of the Neyman-Pearson lemma, the infimum here is attained for
T = T ∗ given by
∗

T (X) = I




(s/d)ϕσ (X − a)
>1
(1 − s/d)ϕσ (X)

where ϕσ (·) is the density of an N (0, σ 2 ) distribution. Thus,





s
ϕσ (σξ − a)
ϕσ (σξ)
d
s
d
∗
L =
1−
P
> −1 + P
≤ −1 .
d
ϕσ (σξ)
s
d
ϕσ (σξ + a)
s
Combining this with (49) and (50), we get

1
Eθ |e
η − η|
ηe θ∈Θ+ (s,a) s
d
 




 aξ
 aξ
a2  d
a2  d
d
− 1 P exp
− 2 > − 1 + P exp
+ 2 ≤ −1
≥
s
σ
2σ
s
σ
2σ
s
 







a
σ
σ
d
d
d
a
−1 P ξ >
+ log
−1
+ log
−1
+P ξ ≤−
=
s
2σ
a
s
2σ
a
s
= Ψ+ (d, s, a).
inf

sup

22

Proof of Proposition 2.1. Using (7) it suffices to show that the right hand side of (14) is
bounded from above and from below by sΨ+ (d, s, a). The upper bound is obvious in view of
Theorem 2.1. To prove lower bound, we follow the same lines as in the proof of Theorem 2.2.
The only difference is that, instead of (49), we now use the inequality
inf
ηe

d
1 X
1 XX
E
|e
η
−
η|
≥
inf
Ej,θj |η̄j − ηj |,
θ
η̄∈T[0,1] s|Θ′ |
s|Θ′ |
′
′
θ∈Θ j=1

θ∈Θ

and we do not need the first inequality in (50).
Proof of Theorem 2.4. For any θ ∈ Θd (s, a), we have
X
X
X
Eθ |η − η| =
Pj,0 (η j = 1) +
Pj,θj (η j = 0) +
Pj,θj (η j = 0)
j:θj =0



j:θj ≥a

(51)

j:θj ≤−a


d
= (d − s)P e
cosh
> −1
σ
s
X
X
Pj,θj (η j = 0),
+
Pj,θj (η j = 0) +
−

 aξ 

a2
2σ 2

j:θj ≤−a

j:θj ≥a

where Pj,θj denotes the distribution of Xj , and ξ is a standard Gaussian random variable. We
now bound from above the probabilities Pj,θj (η j = 0). Introduce the notation


(x + σξ)a
, ∀x ∈ R,
g(x) = cosh
σ2
and
u = exp
We have



a2
+ log
2σ 2




d
−1
.
s

Pj,θj (η j = 0) = P(g(θj ) < u) = P (−b − θj < σξ < b − θj ) .
where b = (σ 2 /a)arccosh(u) > 0. It is easy to check that the function x 7→ P (−b − x < σξ < b − x)

is monotonically decreasing on [0, ∞). Therefore, the maximum of P (−b − θj < σξ < b − θj )
over θj ≥ a is attained at θj = a. Thus, for any θj ≥ a we have




a2
(a + σξ)a
d
Pj,θj (η j = 0) ≤ P(g(a) < u) = P e− 2σ2 cosh
−
1
.
<
σ2
s

Analogously, for any θj ≤ −a,



−

a2
2σ 2

Pj,θj (η j = 0) ≤ P e

a2
= P e− 2σ2





(−a + σξ)a
d
cosh
< −1
σ2
s



(a + σξ)a
d
cosh
< −1
σ2
s

(52)

(53)

where the last equality follows from the fact that ξ has the same distribution as −ξ and cosh
is an even function. Combining (51) – (53) proves the theorem.
23

Proof of Theorem 2.5. We follow the lines of the proof of Theorem 2.2 with suitable modifications. The same argument shows that instead of considering all selectors, it suffices to prove
the lower bound for the class of separable estimators η̄ with components η̄j ∈ [0, 1]. Thus,
inf

sup

ηe θ∈Θd (s,a)

Eθ |e
η − η| ≥

inf

sup

d
X

η̄∈T[0,1] θ∈Θ (s,a)
d
j=1

Ej,θj |η̄j − ηj |

(54)

where T[0,1] is the class of all separable estimators η̄ with components η̄j ∈ [0, 1] and Ej,θj

denotes the expectation with respect to Pj,θj .

Let Θ+ and Θ− be the sets of all θ in Θd (s, a) such that d − s components θj of θ are equal

to 0 and the remaining s components are equal to a (for θ ∈ Θ+ ) or to −a (for θ ∈ Θ− ). For
any η̄ ∈ T[0,1] we have
sup

d
X

θ∈Θd (s,a) j=1

Ej,θj |η̄j − ηj | ≥

d
d
o
X
X
1n
Ej,θj |η̄j − ηj | .
Ej,θj |η̄j − ηj | + sup
sup
2 θ∈Θ+
θ∈Θ−
j=1

j=1

As shown in the proof of Theorem 2.2, for any η̄ ∈ T[0,1] ,
d
X

sup

θ∈Θ+ j=1

Ej,θj |η̄j − ηj | ≥

d 

X
s
s
1−
Ej,0 (η̄j ) + Ej,a (1 − η̄j ) .
d
d
j=1

Analogously,
sup

d
X

θ∈Θ− j=1

d 

X
s
s
1−
Ej,θj |η̄j − ηj | ≥
Ej,0 (η̄j ) + Ej,−a(1 − η̄j ) .
d
d
j=1

From the last three displays we obtain
sup

d
X

θ∈Θd (s,a) j=1

Ej,θj |η̄j − ηj | ≥

d 
X
j=1

1−


s
s
Ej,0 (η̄j ) + Ēj (1 − η̄j ) .
d
d

where Ēj is the expectation with respect to the measure P̄j = (Pj,a + Pj,−a)/2. It follows that
sup

d
X

θ∈Θd (s,a) j=1

Ej,θj |η̄j − ηj | ≥

inf

T ∈[0,1]


(d − s)E0 (T ) + s Ē(1 − T ) .

(55)

Here, E0 denotes the expectation with respect to the distribution of X with density ϕσ (·),
Ē is the expectation with respect to the distribution of X with mixture density ϕ̄σ (·) =
(ϕσ (· + a) + ϕσ (· − a))/2, and inf T ∈[0,1] denotes the infimum over all [0, 1]-valued statistics

T (X). Recall that we denote by ϕσ (·) is the density of N (0, σ 2 ) distribution. Set


s
s
E0 (T ) + Ē(1 − T ) .
1−
d
d
T ∈[0,1]

L̃ = inf

24

By the Bayesian version of the Neyman-Pearson lemma, the infimum here is attained for T = T̃
given by
T̃ (X) = I
Thus,




(s/d)ϕ̄σ (X)
>1 .
(1 − s/d)ϕσ (X)






ϕ̄σ (σξ)
d
s
d
ϕ̄σ (X)
s
P
>
−
1
+
P
≤
−
1
L̃ =
1−
a
d
ϕσ (σξ)
s
2d
ϕσ (X)
s


s
d
ϕ̄σ (X)
+ P−a
≤ −1
2d
ϕσ (X)
s




 aξ  d
2
a
s
− 2
2σ
=
1−
P e
> −1
cosh
d
σ
s




s
ϕ̄σ (X)
ϕ̄σ (X)
d
s
d
+ Pa
≤ −1 +
P−a
≤ −1
2d
ϕσ (X)
s
2d
ϕσ (X)
s

(56)

where Pu denotes the probability distribution of X with density ϕσ (· − u). Note that, for all
x ∈ R,

 ax 
a2
ϕ̄σ (x)
= e− 2σ2 cosh
.
ϕσ (x)
σ2

Using this formula with x = σξ + a and x = σξ − a, and the facts that cosh(·) is an even

function and ξ coincides with −ξ in distribution, we obtain




d
d
ϕ̄σ (X)
ϕ̄σ (X)
≤ −1
= P−a
≤ −1
Pa
ϕσ (X)
s
ϕσ (X)
s


 aξ
a2
a2  d
= P e− 2σ2 cosh
+ 2 ≤ −1 .
σ
σ
s

Thus, L̃ = (s/d)Ψ(d, s, a). Combining this equality with (54) and (55) proves the theorem.
Proof of Theorem 2.6. The upper bounds (15), (16) and (17) follow immediately from (2) and
Theorems 2.1, 2.4 and 2.3, respectively. We now prove the lower bound (18). To this end, first
note that for any θ ∈ Θ+
e ∈ T we have
d (s, a) and any η

Pθ (Sηe 6= S(θ)) = Pθ (∪dj=1 {e
ηj 6= ηj }) = 1 −

d
Y

pj (θ),

j=1

where pj (θ) , Pθ (e
ηj = ηj ). Hence, for any ηe ∈ T ,
sup

θ∈Θ+
d (s,a)

Pθ (Sηe 6= S(θ)) ≥ max′ Pθ (Sηe 6= S(θ)) = 1 − p∗ ,

where Θ′ is the subset of Θ+
d (s, a) defined in the proof of Theorem 2.2, and p∗ = minθ∈Θ′
Next, for any selector ηe we have Pθ (Sηe 6= S(θ)) ≥ Pθ (|e
η − η| = 1). Therefore,
sup

θ∈Θ+
d (s,a)

(57)

θ∈Θ

Pθ (Sηe 6= S(θ)) ≥

25

1 X
Pθ (|e
η − η| = 1).
|Θ′ |
′
θ∈Θ

Qd

j=1 pj (θ).

(58)

Here, Pθ (|e
η − η| = 1) = Pθ (∪dj=1 Bj ) with the random events Bj = {|e
ηj − ηj | = 1, and ηei =
ηi , ∀ i 6= j}. Since the events Bj are disjoint, for any ηe ∈ T we get
d
1 XX
1 X
P
(|e
η
−
η|
=
1)
=
Pθ (Bj )
θ
|Θ′ |
|Θ′ |
′
′
θ∈Θ j=1

θ∈Θ

1 X
|Θ′ |
d

=

j=1

p∗ X 
|Θ′ |
j=1

p∗ X 
|Θ′ |
j=1

X

Pj,0 (e
ηj = 1) +

X

Ej,0 (e
ηj ) +

Y

pi (θ) +

i6=j

θ∈Θ′ :θj =0

d

=

Pj,0 (e
ηj = 1)

θ∈Θ′ :θj =0

d

≥

X

Pj,a (e
ηj = 0)

X

X

θ∈Θ′ :θj =a

Y
i6=j

θ∈Θ′ :θj =a

θ∈Θ′ :θj =a

θ∈Θ′ :θj =0

X


Pj,a (e
ηj = 0)


pi (θ)


Ej,a(1 − ηej )

(59)

where Pj,u denotes the distribution of Xj when θj = u. We now bound the right-hand side
of (59) by following the argument from the last three lines of (50) to the end of the proof of
Theorem 2.2. Applying this argument yields that, for any ηe ∈ T ,

1 X
Pθ (|e
η − η| = 1) ≥ p∗ dL̃ ≥ p∗ sΨ+ (d, s, a).
|Θ′ |
′

(60)

θ∈Θ

Combining (57), (58), and (60), we find that, for any ηe ∈ T ,
sup

θ∈Θ+
d (s,a)

Pθ (Sηe 6= S(θ)) ≥ min
max{1 − p∗ , p∗ sΨ+ (d, s, a)} =
∗
0≤p ≤1

sΨ+ (d, s, a)
.
1 + sΨ+ (d, s, a)

We now prove the lower bound (19). Let the sets Θ+ and Θ− and the constants pj (θ) be
the same as in the proof of Theorem 2.5. Then
sup
θ∈Θd (s,a)

where p̄ = minθ∈Θ+ ∪Θ−

Pθ (Sηe 6= S(θ)) ≥

max

θ∈Θ+ ∪Θ−

Pθ (Sηe 6= S(θ)) = 1 − p̄,

Qd

j=1 pj (θ).

For any selector η̃, we use that Pθ (Sηe 6= S(θ)) ≥ Pθ (|e
η − η| = 1) and, therefore,
sup
θ∈Θd (s,a)

Pθ (Sηe 6= S(θ)) ≥

X
X
1
1
Pθ (|e
η − η| = 1) +
Pθ (|e
η − η| = 1).
+
−
2|Θ |
2|Θ |
+
−
θ∈Θ

θ∈Θ

26

We continue along the same lines as in the proof of (59) to get, for any separable selector η̃,


d
X
p̄ X  X
sup Pθ (Sηe 6= S(θ)) ≥
Ej,0 (e
ηj ) +
Ej,a (1 − ηej )
2|Θ+ |
θ∈Θd (s,a)
+
j=1 θ∈Θ+ :θj =0
θ∈Θ :θj =a


d
X
p̄ X  X
Ej,0 (e
ηj ) +
Ej,−a(1 − ηej )
+
2|Θ− |
−
−
j=1

≥

θ∈Θ :θj =0

θ∈Θ :θj =−a

d

s
s
p̄ X 
Ej,0 (e
ηj ) + Ej,a(1 − ηej )
1−
2
d
d
j=1

+

d

s
s
p̄ X 
Ej,0 (e
ηj ) + Ej,−a(1 − ηej )
1−
2
d
d
j=1

= p̄

d 
X

1−

j=1


s
s
Ej,0 (η̄j ) + Ej (1 − ηej ) ,
d
d

where again Ēj denotes the expected value with respect to P̄j = 12 (Pj,a + Pj,−a). Analogously
to the proof of Theorem 2.5, the expression in the last display can be further bounded from
below by p̄dL̃ = p̄sΨ(d, s, a). Thus,
sup
θ∈Θd (s,a)

Pθ (Sηe 6= S(θ)) ≥ min max{1 − p̄, p̄sΨ(d, s, a)} =
0≤p̄≤1

sΨ(d, s, a)
.
1 + sΨ(d, s, a)

Proof of Theorem 4.2. (i) In the proof of Theorem 2.3, we have obtained that


1
d
sup
Eθ |η̂ − η| ≤ 2
− 1 Φ(−t/σ) + 2Φ(−(a − t)+ /σ),
s
θ∈Θd (s,a) s

(61)


− 1 is the threshold (5). Since a2 ≥ 2σ 2 log(d/s − 1) we get that
 2
2
a ≥ t and that t > a/2, which is equivalent to t > a − t. Furthermore, ds − 1 e−t /(2σ ) =
where t =

a
2

2 /(2σ 2 )

e−(a−t)

+

σ2
a

log

d
s

. These remarks and (32) imply that
r


d
exp(−(a − t)2 /(2σ 2 ))
2
p
− 1 Φ(−t/σ) ≤
s
π (a − t)/σ + (a − t)2 /σ 2 + 8/π
exp(−(a − t)2 /(2σ 2 ))
p
(a − t)/σ + (a − t)2 /σ 2 + 4
r


a−t
π
Φ −
≤
.
2
σ
≤

Combining this with (61) we get


√
a−t
1
Eθ |η̂ − η| ≤ (2 + 2π)Φ −
.
σ
θ∈Θd (s,a) s
sup

27

Now, to prove (34) it remains to note that under assumption (33),


a−t
d
a
σ
a2 − 2σ 2 log((d − s)/s)
=
− log
−1 =
≥ ∆.
σ
2σ
a
s
2aσ

1/2
Indeed, assumption (33) states that a ≥ a0 , σ 2 log((d − s)/s) + W
, and the function

2
2
a 7→ a − 2σ log((d − s)/s) /a is monotonically increasing in a > 0. On the other hand,

a20 − 2σ 2 log((d − s)/s) /(2a0 σ) = ∆.

(62)

(ii) We now prove (37). By Theorem 2.2,
inf
ηe


d

1
a
σ
Eθ |e
η − η| ≥ Ψ+ (d, s, a) ≥ Φ −
+ log
−1
.
2σ
a
s
θ∈Θd (s,a) s
sup

Here,

d
 2σ 2 log((d − s)/s) − a2
σ
a
+ log
−1 =
.
2σ
a
s
2σa

Observe that the function a 7→ 2σ 2 log((d − s)/s) − a2 /a is monotonically decreasing in
−

a > 0 and that assumption (36) states that a ≤ a0 . In view of (62), the value of its minimum

for a ≤ a0 is equal to −∆. The bound (37) now follows by the monotonicity of Φ(·).

Proof of Theorem 4.3. Assume without loss of generality that d is large enough to have (d −
p
sd )/sd > 1. We apply Theorem 4.2 with W = A 2 log((d − sd )/sd ). Then,
p
A2 2 log((d − sd )/sd )
2
∆ = p
.
4 2 log((d − sd )/sd ) + A
By assumption, there exists ν > 0 such that (2 + ν)sd ≤ d for all d large enough. Equivalently,

d/sd − 1 ≥ 1 + ν and therefore, using the monotonicity argument, we find
p
A2 2 log(1 + ν)
2
∆ ≥p
→ ∞ as A → ∞.
2 log(1 + ν) + A

This and (34) imply part (i) of the theorem. Part (ii) follows from (37) by noticing that
∆2 ≤ supx>0

A2 x
4(x+A)

= A2 /4 for any fixed A > 0.

Proof of Theorem 4.4. Throughout the proof, we assume without loss of generality that d is


p
large enough to have sd ≥ 2, and (d − sd )/sd > 1. Set W∗ (s) , 4 log s + log s log(d − s) ,
and notice that

p
W∗ (sd )
p
= 2 log sd ,
2 2 log((d − sd )/sd ) + W∗ (sd )
2
p
p
log(d − sd ) + log sd .
2 log((d − sd )/sd ) + W∗ (sd ) = 2
28

(63)
(64)

If (40) holds, we have Wd ≥ W∗ (sd ) for all d large enough. By the monotonicity of the quantity

∆ defined in (35) with respect to W , this implies
Wd
p
∆d ,
2 2 log((d − sd )/sd ) + Wd
p
W∗ (sd )
p
≥
= 2 log sd .
2 2 log((d − sd )/sd ) + W∗ (sd )

(65)

Now, by Theorem 4.2 and using (32) we may write
√
sup
Eθ |η̂ − η| ≤ (2 + 2π)sd Φ (−∆d )
θ∈Θd (sd ,ad )





∆2d
1
exp −
≤ 3sd min 1,
∆d
2




2
∆d − 2 log sd
1
= 3 min 1,
exp −
.
∆d
2

(66)

This and (65) imply that, for all d large enough,



1
.
sup
Eθ |η̂ − η| ≤ 3 min 1, √
2 log sd
θ∈Θd (sd ,ad )

Since sd → ∞, part (i) of the theorem follows.

We now prove part (ii) of the theorem. It suffices to consider Wd > 0 for all d large enough

since for non-positive Wd almost full recovery is impossible and the result follows from part
(ii) of Theorem 4.3. If (42) holds, there exists A < 1 such that Wd ≤ AW∗ (sd ) for all d large

enough. By the monotonicity of the quantity ∆ defined in (35) with respect to W and in view

of equation (63), this implies
∆2d − 2 log sd
A2 W∗2 (sd )
W∗2 (sd )
≤
−
4(2 log((d − sd )/sd ) + AW∗ (sd )) 4(2 log((d − sd )/sd ) + W∗ (sd ))
(A − 1)W∗2 (sd )(AW∗ (sd ) + 2(A + 1) log((d − sd )/sd ))
=
4(2 log((d − sd )/sd ) + AW∗ (sd ))(2 log((d − sd )/sd ) + W∗ (sd ))
≤

(A − 1)AW∗2 (sd )
4(2 log((d − sd )/sd ) + W∗ (sd ))

=

2

p
2(A − 1)A log sd + log sd log(d − sd )
= 2(A − 1)A log sd ,
p
2
√
log(d − sd ) + log sd

(67)

where we have used the fact that A < 1 and equations (63), (64). Next, by Theorem 4.2 and
using (32), we have
inf

sup

ηe θ∈Θd (sd ,ad )





∆2
1 1
sd
min
,
exp − d
4
2 ∆d
2




∆2 − 2 log sd
1
1 1
min
,
exp − d
.
4
2 ∆d
2

Eθ |e
η − η| ≥ sd Φ (−∆d ) ≥
=

29

Combining this inequality with (67), we find that, for all d large enough,


1 1
1
,
inf
sup
Eθ |e
η − η| ≥ min
exp ((1 − A)A log sd ) .
4
2 ∆d
ηe θ∈Θd (sd ,ad )
√
Since A < 1 and ∆d ≤ A 2 log sd by (67), the last expression tends to ∞ as sd → ∞. This
proves part (ii) of the theorem.

Proof of Theorem 5.1. By (48), for any θ ∈ Θd (sd , ad ), and any t > 0 we have
Eθ |η̂ − η| ≤ (d − sd ) P(|ξ| ≥ t/σ) + sd P(|ξ| > (ad − t)+ /σ),
where ξ is a standard normal random variable. It follows that, for any ad ≥ a∗d , any θ ∈

Θd (sd , ad ), and any t > 0,

Eθ |η̂ − η| ≤ d P(|ξ| ≥ t/σ) + sd P(|ξ| > (a∗d − t)+ /σ).
Without loss of generality assume that d ≥ 6 and 2 ≤ sd ≤ d/2. Then, using the inequality
√
√
√
√
x − y ≤ (x − y)/ 2y, ∀x > y > 0, we find that, for t = σ 2 log d,

p
p
√ p
(a∗d − t)+ /σ ≥
2
log(d − sd ) − log d + log(sd )


p
p
d
2 log(sd ) − log
/ log(d − sd )
≥
d − sd
p
p
2 log(sd ) − (log 2)/ log(d/2) > 0.
≥

From this we also easily deduce that, for 2 ≤ sd ≤ d/2, we have ((a∗d − t)+ /σ)2 /2 ≥ log(sd ) −
√
2 log 2. Combining these remarks with (32) and (43), we find
√

sd exp − log(sd ) + 2 log 2
1
p
sup
Eθ |η̂ − η| ≤ √
,
+
2 log d
2 log(sd )
θ∈Θd (sd ,ad )
which immediately implies the theorem by taking the limit as d → ∞.

Proof of Theorem 5.2. Throughout the proof, we will write for brevity sd = s, ad = a, Ad = A,
and set σ = 1. Since Θd (s, a) ⊆ Θd (s, a0 (s, A)) for all a ≥ a0 (s, A), it suffices to prove that
1
Eθ |η̂ ad − η| = 0.
d→∞ θ∈Θd (s,a0 (s,A)) s
lim

sup

(68)

Here s ≤ s∗d and recall that throughout this section we assume that s∗d ≤ d/4; since we deal

with asymptotics as d/s∗d → ∞, the latter assumption is without loss of generality in the
current proof.

If s < gM , let m0 ∈ {2, . . . , M } be the index such that gm0 is the minimal element of

the grid, which is greater than the true underlying s. Thus, gm0 /2 = gm0 −1 ≤ s < gm0 . If

s ∈ [gM , s∗d ], we set m0 = M . In both cases,

s ≥ gm0 /2.
30

(69)

We decompose the risk as follows:
1
Eθ |η̂ ad − η| = I1 + I2 ,
s
where
I1 =
I2 =

1
Eθ (|η̂(gm
b ≤ m0 )) ,
b ) − η|I(m
s
1
Eθ (|η̂(gm
b ≥ m0 + 1)) .
b ) − η|I(m
s

We now evaluate I1 . Using the fact that η̂j (gm ) is monotonically increasing in m and the
definition of m,
b we obtain that, on the event {m
b ≤ m0 },
|η̂(gm
b ) − η̂(gm0 )| ≤

m0
X

m=m+1
b

|η̂(gm ) − η̂(gm−1 )|

m0
d
X
X
(η̂j (gm ) − η̂j (gm−1 ))

=

j=1
m=m+1
b

=

m0
d
X
X

j=1
m=m+1
b
m
0
X

≤ τ

m=m+1
b


I w(gm ) ≤ |Xj | < w(gm−1 )

gm ≤ τ s

m0
X

m=2

2m−m0 +1 ≤ 4τ s,

where we have used the equality gm = 2m and (69). Thus,
1
1
Eθ (|η̂(gm
b ≤ m0 )) + Eθ |η̂(gm0 ) − η|
b ) − η̂(gm0 )|I(m
s
s
1
≤ 4τ + Eθ |η̂(gm0 ) − η|.
s

I1 ≤

By (48), for any θ ∈ Θd (s, a0 (s, A)) we have


d
1
Eθ |η̂(gm0 ) − η| ≤
− 1 P(|ξ| ≥ w(gm0 )) + P(|ξ| > (a0 (s, A) − w(gm0 ))+ )
s
s

(70)

(71)

where ξ is a standard Gaussian random variable. Using the bound on the Gaussian tail
probability and the fact that s ≥ gm0 /2, we get


d
π −1/2
d/s − 1
p
− 1 P(|ξ| ≥ w(gm0 )) ≤
s
d/gm0 − 1
log(d/gm0 − 1)
≤

(72)

2π −1/2
d−s
3π −1/2
p
≤p
.
d − 2s
log(d/s∗d − 1)
log(d/s − 1)

To bound the second probability on the right-hand side of (71), we use the following lemma.
Lemma 6.1. Under the assumptions of Theorem 5.2, for any m ≥ m0 we have
P(|ξ| > (a0 (s, A) − w(gm ))+ ) ≤ log (d/s∗d − 1)
31

− 1

2

.

(73)

Combining (71), (72) and (73) with m = m0 , we find
1
Eθ |η̂(gm0 ) − η| ≤
s

p

which together with (70) leads to the bound
I1 ≤ 4τ + p

3π −1/2 + 1
,
log(d/s∗d − 1)

(74)

3π −1/2 + 1
.
log(d/s∗d − 1)

(75)

We now turn to the evaluation of I2 . It is enough to consider the case m0 ≤ M − 1 since

I2 = 0 when m0 = M . We have
I2 =

M
1 X
Eθ (|η̂(gm̂ ) − η|I(m
b = m))
s m=m +1

(76)

0

≤

1
s

M
X

1/2
1/2
Eθ |η̂(gm ) − η|
Pθ (m
b = m)
.

m=m0 +1

By definition, the event {m
b = m} occurs if and only if there exists some ℓ ≥ m such that
Pd
j=1 I(wℓ ≤ |Xj | < wℓ−1 ) > τ gℓ , vℓ , where we set for brevity wℓ = w(gℓ ). Thus,
Pθ (m
b = m) ≤

M
X

ℓ=m



Pθ 

d
X
j=1



I(wℓ ≤ |Xj | < wℓ−1 ) > vℓ  .

(77)

By Bernstein’s inequality, for any t > 0 we have




d
d
X
X
I(wℓ ≤ |Xj | < wℓ−1 ) > t
I(wℓ ≤ |Xj | < wℓ−1 ) − Eθ 
Pθ 
j=1

j=1

≤ exp − Pd

j=1 Eθ

t2 /2

(I(wℓ ≤ |Xj | < wℓ−1 )) + 2t/3

!

,

(78)

where we have used that, for random variables with values in {0, 1}, the variance is smaller
than the expectation.

Now, similar to (48), for any θ ∈ Θd (s, a0 (s, A)),
Eθ

d
X
j=1


I(wℓ ≤ |Xj | < wℓ−1 )

≤ (d − s)P (wℓ ≤ |ξ| < wℓ−1 ) +

X

P (|θj + ξ| < wℓ−1 )

j:θj 6=0

≤ (d − s)P (|ξ| ≥ wℓ ) + sP(|ξ| > −(a0 (s, A) − wℓ−1 )+ ),
where ξ is a standard Gaussian random variable. Since ℓ ≥ m0 + 1, from Lemma 6.1 we get
P(|ξ| > (a0 (s, A) − wℓ−1 ))+ ) ≤ log (d/s∗d − 1)
32

− 1

2

.

(79)

Next, using the bound on the Gaussian tail probability and the inequalities gℓ ≤ s∗d ≤ d/4, we
find

(d − s)P (|ξ| ≥ wℓ ) ≤

d−s
(4/3)π −1/2 gℓ
π −1/2
p
≤p
.
d/gℓ − 1 log(d/gℓ − 1)
log(d/s∗d − 1)

We now deduce from (79) and (80), and the inequality s ≤ gℓ for ℓ ≥ m0 + 1, that

d
X

(4/3)π −1/2 + 1 gℓ
Eθ
I(wℓ ≤ |Xj | < wℓ−1 ) ≤ p
≤ 2τ gℓ .
log(d/s∗d − 1)
j=1

(80)

(81)

Taking in (78) t = 3τ gℓ = 3vℓ and using (81), we find


d
X
I(wℓ ≤ |Xj | < wℓ−1 ) > vℓ  ≤ exp(−C1 vℓ ) = exp(−C1 2ℓ τ ),
Pθ 
j=1

for all ℓ ≥ m0 + 1 and some absolute constant C1 > 0. This implies
Pθ (m
b = m) ≤

M
X

ℓ=m

exp(−C1 2ℓ τ ) ≤ C2 2−m τ −1 exp(−C1 2m τ )

(82)

for some absolute constant C2 > 0.
On the other hand, notice that the bounds (71), and (72) are valid not only for gm0 but
also for any gm with m ≥ m0 + 1. Using this observation and Lemma 6.1 we get that, for any
θ ∈ Θd (s, a0 (s, A)) and any m ≥ m0 + 1,
#
"
− 1
d/s − 1
π −1/2
∗
p
+ log (d/sd − 1) 2
Eθ |η̂(gm ) − η| ≤ s
d/gm − 1
log(d/gm − 1)

(4/3)π −1/2 + 1 gm
p
≤
, τ ′ gm = τ ′ 2m ,
log(d/s∗d − 1)

(83)

where the last inequality follows from the same argument as in (80).
Now, we plug (82) and (83) in (76) to obtain
1/2

I2 ≤

C2 (τ ′ /τ )1/2
s
τ

exp(−C1 2m−1 τ )

(84)

m=m0 +1

′ 1/2 −3/2

≤ C3 (τ )

M
X

exp(−C1 2m0 τ ) ≤ C3 (τ ′ )1/2 τ −3/2

− 1 
for some absolute constant C3 > 0. Notice that (τ ′ )1/2 = O log (d/s∗d − 1) 4 as d/s∗d → ∞
3
while τ −3/2 = O log (d/s∗d − 1) 14 . Thus, I2 = o(1) as d → ∞. Since from (75) we also get

that I1 = o(1) as d → ∞, the proof is complete.

Proof of Lemma 6.1. Let first s < gM . Then, by definition of m0 , we have s < gm0 . Therefore,
s < gm for m ≥ m0 , and we have w(gm ) < w(s). It follows that
!
√
√
A
A
a0 (s, A) − w(gm ) ≥ a0 (s, A) − w(s) ≥ √ min √ , log1/4 (d/s − 1) ,
2 2
2
33

where we have used the elementary inequalities
√
√ √ 
√
√
√
x + y − y ≥ y/(2 x + y) ≥ (2 2)−1 min y/ x, y
q
p

with x = 2 log (d/s − 1) and y = A log (d/s − 1). By assumption, A ≥ 16 log log d/s∗d − 1 ,

so that we get



a0 (s, A) − w(gm ) ≥ a0 (s, A) − w(s) ≥ 4 log log



1/2
d
.
−1
s∗d

(85)

This and the standard bound on the Gaussian tail probability imply
P(|ξ| > (a0 (s, A) − w(gm ))+ ) ≤ exp(−(a0 (s, A) − w(gm ))2 /2)
− 1
≤
log (d/s∗d − 1) 2 .

(86)
(87)

Let now s ∈ [gM , s∗d ]. Then m0 = M and we need to prove the result only for m = M . By

definition of M we have s∗d ≤ 2gM . This and (85) imply





1/2
d
a0 (s, A)−w(gM ) ≥
≥ 4 log log
−(w(s∗d /2)−w(s∗d )).
−1
s∗d
p
p
p
Now, using the elementary inequality log(x + y) − log(x) ≤ y/(2x log(x)) with x =
a0 (s, A)−w(s)−(w(s∗d /2)−w(s∗d ))

d/s∗d − 1 and y = d/s∗d , and the fact that s∗d ≤ d/4 we find
w(s∗d /2)

−

w(s∗d )

√
1/2


2 2
1
d
d
.
≤ p
−1
≤p
≤ 3 log log
s∗d
2 log(d/s∗d − 1) d − s∗d
3 log(d/s∗d − 1)

The last two displays yield a0 (s, A) − w(gM ) ≥
in (86).



log log



d
s∗d

1/2
−1
, and we conclude as

Acknowledgements. We would like to thank Felix Abramovich for helpful discussion of
the results. The work of N.A. Stepanova was supported by an NSERC grant. The work
of A.B. Tsybakov was supported by GENES and by the French National Research Agency
(ANR) under the grants IPANEMA (ANR-13-BSH1-0004-02), and Labex ECODEC (ANR 11-LABEX-0047). It was also supported by the ”Chaire Economie et Gestion des Nouvelles
Données”, under the auspices of Institut Louis Bachelier, Havas-Media and Paris-Dauphine.

References
[1] F. Abramovich and Y. Benjamini (1995). Thresholding of wavelet coefficients as multiple
hypotheses testing procedure. In Wavelets and Statistics. Lecture Notes in Statistics, 103,
Antoniadis ed., 5-14. Springer, New York.
34

[2] F. Abramovich, Y. Benjamini, D. L. Donoho, and I. M. Johnstone (2006). Adapting to
unknown sparsity by controlling the false discovery rate. Ann. Statist., 34, 584 – 653.
[3] M. Abramowitz, I. A. Stegun (1964). Handbook of Mathematical Functions with Formulas,
Graphs, and Mathematical Tables, volume 55 of National Bureau of Standards Applied
Mathematics Series. Washington, D.C.
[4] E. Arias-Castro and S. Chen (2016). Distribution-free multiple testing.
http://arxiv.org/abs/1604.07520
[5] K. Bertin and G.Lecué (2008). Selection of variables and dimension reduction in highdimensional nonparametric regression. Electronic J. Statist., 2, 1224–1241.
[6] M. Bogdan, E. van den Berg, C. Sabatti, W.Su, and Candès, E. J. (2015). SLOPE –
adaptive variable selection via convex optimization. Ann. Appl. Statist., 9, 1103 – 1140.
[7] C. Butucea, Yu.I. Ingster and I. Suslina (2015). Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix. ESAIM: Probability and Statistics, 19, 115-134.
[8] C. Butucea and N. Stepanova (2015). Adaptive variable selection in nonparametric sparse
additive models. http://arxiv.org/abs/1508.06660
[9] O. Collier, L.Comminges, A.B.Tsybakov and N. Verzelen. (2016). Optimal adaptive estimation of linear functionals under sparsity. http://arxiv.org/abs/1611.09744
[10] L. Comminges and A. S. Dalalyan (2012). Tight conditions for consistency of variable
selection in the context of high dimensionality. Ann. Statist. 40 (5), 2667–2696.
[11] C. Gao, Y. Lu, D. Zhou (2016). Exact exponent in optimal rates for crowdsourcing.
http://arxiv.org/abs/1605.07696
[12] C. R. Genovese, J. Jin, L. Wasserman, and Z. Yao. (2012). A comparison of the Lasso
and Marginal Regression. J. Mach. Learn. Res., 13, 2107–2143.
[13] P. Hall and J. Jin (2010). Innovated higher criticism for detecting sparse signals in correlated noise. Ann. Statist., 38, 1686-1732.
[14] Yu. I. Ingster and N. A. Stepanova (2014). Adaptive variable selection in nonparametric
sparse regression. Journal of Mathematical Sciences, 199, 184–201.
[15] P. Ji, and J. Jin (2012). UPS delivers optimal phase diagram in high-dimensional variable
selection. Ann. Statist., 40 (1), 73–103.

35

[16] J.Jin, C.-H.Zhang, and Q.Zhang (2014). Optimality of graphlet screening in high dimensional variable selection. J. of Machine Learning Research, 15, 2723–2772.
[17] J. Lafferty, and L. Wasserman (2008). Rodeo: sparse, greedy nonparametric regression.
Ann. Statist., 36, 28–63.
[18] E.L. Lehmann, and J.P. Romano (2005). Testing Statistical Hypotheses. Springer, New
York.
[19] K. Lounici (2008). Sup-norm convergence rate and sign concentration property of Lasso
and Dantzig estimators. Electronic J. Statist., 2, 90–102.
[20] N. Meinshausen and P. Bühlmann (2006). High-dimensional graphs and variable selection
with the Lasso. Ann. Statist., 34 (3), 1436–1462.
[21] N. Meinshausen and P. Bühlmann (2010). Stability selection. J. Roy. Stat. Soc. Ser. B,
72 (4), 417–473.
[22] P. Neuvial and E. Roquain (2012). On false discovery rate thresholding for classification
under sparsity. Ann. Statist., 40 (5), 2572–2600.
[23] L. Wasserman and K. Roeder (2009). High-dimensional variable selection. Ann. Statist.,
37 (5A), 2178–2201.
[24] M. Wainwright (2009). Sharp thresholds for high-dimensional and noisy sparsity recovery
using l1 -constrained quadratic programming (Lasso). IEEE Trans. Inf. Theory, 55 (5),
2183–2202.
[25] C.-H. Zhang (2010). Nearly unbiased variable selection under minimax concave penalty.
Ann. Statist., 38 (2), 894–942.
[26] A. Y. Zhang, H. H. Zhou (2015). Minimax rates of community detection in stochastic
block models. http://arxiv.org/abs/1507.05313
[27] P. Zhao and B. Yu (2006). On model selection consistency of Lasso. J. Mach. Learn. Res.,
7, 2541–2563.

36

