Yu I Ingster

A B † Tsybakov

Detection boundary in sparse regression

Keywords: Mathematics Subject Classifications: Primary 62J05, Secondary 62G10, 62H20, 62G05, 62G08, 62C20, 62G20 High-dimensional regression, detection boundary, sparse vectors, sparsity, minimax hypothesis testing

We study the problem of detection of a p-dimensional sparse vector of parameters in the linear regression model with Gaussian noise. We establish the detection boundary, i.e., the necessary and sufficient conditions for the possibility of successful detection as both the sample size n and the dimension p tend to the infinity. Testing procedures that achieve this boundary are also exhibited. Our results encompass the high-dimensional setting (p ≫ n). The main message is that, under some conditions, the detection boundary phenomenon that has been proved for the Gaussian sequence model, extends to high-dimensional linear regression. Finally, we establish the detection boundaries when the variance of the noise is unknown. Interestingly, the detection boundaries sometimes depend on the knowledge of the variance in a high-dimensional setting.

Introduction

We consider the linear regression model with random design:

Y i = p j=1 θ j X ij + ξ i , i = 1, ..., n, (1.1)
where θ j ∈ IR are unknown coefficients, ξ i are i.i.d. N (0, σ 2 ) random variables, X ij are random variables, which are identically distributed, and (X ij , 1 ≤ i ≤ n) are independent for any fixed j with EX ij = 0, EX 2 ij = 1. We study separately the settings with known σ > 0 (then assuming that σ = 1 without loss of generality) and unknown σ > 0. We also assume that X ij , 1 ≤ j ≤ p, 1 ≤ i ≤ n, are independent of ξ i , 1 ≤ i ≤ n.

Based on the observations Z = (X, Y ) where X = (X ij , 1 ≤ j ≤ p, 1 ≤ i ≤ n), and Y = (Y i , 1 ≤ i ≤ n), we consider the problem of detecting whether the signal θ = (θ 1 , . . . , θ p ) is zero (i.e., we observe the pure noise) or θ is some sparse signal, which is sufficiently well separated from 0. Specifically, we state this as a problem of testing the hypothesis H 0 : θ = 0 against the alternative H k,r : θ ∈ Θ k (r) = {θ ∈ IR p k : θ ≥ r}, where IR p k denotes the ℓ 0 ball in IR p of radius k, • is the Euclidean norm, and r > 0 is a separation constant.

The smaller is r, the harder is to detect the signal. The question that we study here is: What is the detection boundary, i.e., what is the smallest separation constant r such that successful detection is still possible? The problem is formalized in an asymptotic minimax sense, cf. Section 2 below. This question is closely related to the previous work by several authors on detection and classification boundaries for the Gaussian sequence model [START_REF] Cai | Estimation and confidence sets for sparse normal mixtures[END_REF][START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF][START_REF] Donoho | Higher criticism thresholding: Optimal feature selection when useful features are rare and weak[END_REF][START_REF] Donoho | Feature selection by higher criticism thresholding achieves optimal phase diagram[END_REF][START_REF] Hall | Innovated higher criticism for detecting sparse signals in correlated noise[END_REF][START_REF] Haupt | Adaptive discovery of sparse signals in noise[END_REF][START_REF] Haupt | Distilled sensing: Adaptive sampling for sparse detection and estimation[END_REF][START_REF] Ingster | Some problems of hypothesis testing leading to infinitely divisible distributions[END_REF][START_REF] Ingster | Adaptive detection of a signal of growing dimension[END_REF][START_REF] Ingster | Adaptive detection of a signal of growing dimension[END_REF][START_REF] Ingster | Nonparametric goodness-of-fit testing under gaussian models[END_REF][START_REF] Ingster | On a detection of a signal of known shape in multichannel system[END_REF][START_REF] Ingster | Sparse classification boundaries[END_REF][START_REF] Ingster | Classification of sparse high-dimensional vectors[END_REF][START_REF] Jager | Goodness-of-fit tests via phi-divergences[END_REF][START_REF] Jin | Detection boundary for sparse mixtures[END_REF][START_REF] Jin | Detecting a target in very noisy data from multiple looks[END_REF]. These papers considered model (1.1) with p = n and X ij = δ ij , where δ ij is the Kronecker delta, or replications of such a model (in classification setting). The main message of the present work is that, under some conditions, the detection boundary phenomenon similar to the one discussed in those papers, extends to linear regression. Our results cover the high-dimensional p ≫ n setting.

We now give a brief summary of our findings under the simplifying assumption that all the regressors X ij are i.i.d. standard Gaussian. We consider the asymptotic setting where p → ∞, n → ∞ and k = p 1-β for some β ∈ (0, 1). The results are different for moderately sparse alternatives (0 < β < 1/2) and highly sparse alternatives (1/2 < β < 1). We show that for moderately sparse alternatives the detection boundary is of the order of magnitude

r ≍ p 1/4 √ n ∧ 1 n 1/4 , (1.2)
whereas for highly sparse alternatives (1/2 < β < 1) it is of the order

r ≍ k log p n ∧ 1 n 1/4 . (1.3)
This solves the problem of optimal rate in detection boundary for all the range of values (p, n). Furthermore, for highly sparse alternatives under the additional assumption

p 1-β log(p) = o( √ n) (1.4)
we obtain the sharp detection boundary, i.e., not only the rate but also the exact constant. This sharp boundary has the form

r = ϕ(β) k log p n , (1.5)
where

ϕ(β) = √ 2β -1, 1/2 < β ≤ 3/4, √ 2(1 - √ 1 -β), 3/4 < β < 1. (1.6)
The function ϕ(•) here is the same as in the above mentioned detection and classification problems, as first introduced in [START_REF] Ingster | Some problems of hypothesis testing leading to infinitely divisible distributions[END_REF]. We also provide optimal testing procedures. In particular, the sharp boundary (1.5)- (1.6) is attained on the Higher Criticism statistic. One of the applications of this result is related to transmission of signals under compressed sensing, cf. [START_REF] Donoho | Compressed Sensing[END_REF][START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF]. Assume that a sparse high-dimensional signal θ is coded using compressed sensing with i.i.d. Gaussian X ij and then transmitted through a noisy channel. Observing the noisy outputs Y i , we would like to detect whether the signal was indeed transmitted. For example, this is of interest if several signals appear in consecutive time slots but some slots contain no signal. Then the aim is to detect informative slots. Our detection boundary (1.5) specifies the minimal energy of the signal sufficient for detectability. We note that ϕ(•) < √ 2, so that successful detection is possible for rather weak signals whose energy is under the threshold 2k log(p)/n. This can be compared with the asymptotically optimal recovery of sparsity pattern (RSP) by the Lasso in the same Gaussian model as ours [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (Lasso)[END_REF][START_REF] Wainwright | Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting[END_REF]. Observe that the RSP property is stronger than detection (i.e., it implies correct detection) but [START_REF] Wainwright | Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ 1 -constrained quadratic programming (Lasso)[END_REF] defines the alternative by {θ ∈ IR p k : |θ j | ≥ c log(p)/n, ∀j} for some constant c > 2, which is better separated from the null than our alternative Θ k (r). Thresholds that are larger in order of magnitude are required if one would like to perform detection based on estimation of the values of coefficients in the ℓ 2 norm [START_REF] Bickel | Simultaneous analysis of Lasso and Dantzig selector[END_REF][START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF].

In many applications, the variance of the noise ξ is unknown. Does the problem of detection become more difficult in this case? In order to answer this question, we investigate the detection boundaries in the unknown variance setting. Related work [START_REF] Verzelen | Goodness-of-fit tests for high-dimensional Gaussian linear models[END_REF][START_REF] Verzelen | Minimax risks for sparse regressions: Ultra-highdimensional phenomenons[END_REF] develop minimax bounds for detection in model (1.1) under assumptions different from ours and under unknown variance. However, [START_REF] Verzelen | Goodness-of-fit tests for high-dimensional Gaussian linear models[END_REF] does not provide a sharp boundary. Here, we prove that for β ∈ (1/2, 1) and k log(p) ≪ √ n, the detection boundaries are the same for known and unknown variance. In contrast, when k log(p) ≫ √ n, the detection boundary is much larger in the case of unknown variance than for known variance. We also provide an optimal testing procedure for unknown variance.

After we have obtained our results, we became aware of the interesting parallel unpublished work of Arias-Castro et al. [START_REF] Arias-Castro | Global Testing and Sparse Alternatives: ANOVA, Multiple Comparisons and the Higher Criticism[END_REF]. There the authors derive the detection boundary in model (1.1) with known variance of the noise for both fixed and random design. Their approach based on the analysis of the Higher Criticism shares some similarities with our work. When the variables X ij are i.i.d. standard normal and the variance is known, we can directly compare our results with [START_REF] Arias-Castro | Global Testing and Sparse Alternatives: ANOVA, Multiple Comparisons and the Higher Criticism[END_REF]. In [START_REF] Arias-Castro | Global Testing and Sparse Alternatives: ANOVA, Multiple Comparisons and the Higher Criticism[END_REF] the detection boundaries analogous to (1.2) and (1.3) do not contain the minimum with the n -1/4 term, because they are proved in a smaller range of values (p, n) where this term disappears. In particular, the conditions in [START_REF] Arias-Castro | Global Testing and Sparse Alternatives: ANOVA, Multiple Comparisons and the Higher Criticism[END_REF] exclude the high-dimensional case p ≫ n. We also note that, due to the constraints on the classes of matrices X, [START_REF] Arias-Castro | Global Testing and Sparse Alternatives: ANOVA, Multiple Comparisons and the Higher Criticism[END_REF] obtains the sharp boundary (1.5)-(1.6) under the condition p 1-β (log(p)) 2 = o( √ n) which is more restrictive than our condition (1.4).

The other difference is that [START_REF] Arias-Castro | Global Testing and Sparse Alternatives: ANOVA, Multiple Comparisons and the Higher Criticism[END_REF] does not treat the case of unknown variance of the noise.

Below we will use the following notation. We write Z = (X, Y ) where X = (X ij , 1 ≤ j ≤ p, 1 ≤ i ≤ n), and Y = (Y i , 1 ≤ i ≤ n) are the observations satisfying (1.1). Let P θ be the probability measure that corresponds to observations Z, P θ,i be those corresponding to observations Z i = (X i1 , ..., X ip , Y i ) with fixed i = 1, ..., n, and P X , P X,i be the probability measures corresponding to observations X or X (i) = (X i,j , 1 ≤ j ≤ p). We denote by P X θ and P X θ,i the conditional distributions of Y given X and of Y i given X (i) respectively. The corresponding expectations are denoted by E X θ and E X θ,i . Clearly,

P θ (dZ) = P X θ (dY )P X (dX), P θ,i (dZ i ) = P X θ,i (dY )P X,i (dX (i) ), (1.7)
and

P θ (dZ) = n i=1 P θ,i (dZ i ).
We denote by X j ∈ IR n the jth column of matrix X = (X ij ), and set

(X j , X l ) = n i=1 X ij X il , X j 2 = (X j , X j ).

Detection problem

For θ ∈ IR p , we denote by M(θ) = p j=1 1I {θ j =0} the number of non-zero components of θ, where 1I {A} is the indicator function. As above, let IR p k , 1 ≤ k ≤ p, denote the ℓ 0 ball in IR p of radius k, i.e., the subset of IR p that consists of vectors θ with M(θ) ≤ k, or equivalently, θ ∈ IR p k contains no more than k nonzero coordinates. In particular IR p p = IR p . Recall the notation Θ k (r) = {θ ∈ IR p k : θ ≥ r}. We consider the problem of testing the hypothesis H 0 : θ = 0 against the alternative H k,r : θ ∈ Θ k (r). In this paper we study the asymptotic setting where p → ∞, n → ∞ and k = p 1-β . The coefficient β ∈ [0, 1] is called the sparsity index. We assume in this section that σ 2 is known. Modifications for the case of unknown variance are discussed in Section 4.2.1.

We call a test any measurable function ψ(Z) with values in [0, 1]. For a test ψ, let α(ψ) = E 0 (ψ) be the type I error probability and β(ψ, θ) = E θ (1ψ) be the type II error probability for the alternative θ ∈ Θ ⊂ IR p . We set

β(ψ) = β(ψ, Θ) = sup θ∈Θ β(ψ, θ), γ(ψ) = γ(ψ, Θ) = α(ψ) + β(ψ, Θ) .
We denote by β(α) = β n,p,k (α, r) the minimax type II error probability for a given level α ∈ (0, 1),

β(α) = inf ψ:α(ψ)≤α β(ψ, Θ k (r)), 0 ≤ β(α) ≤ 1 -α .
Accordingly, we denote by γ = γ n,p,k (r) the minimax total error probability in the hypothesis testing problem:

γ = inf ψ γ(ψ, Θ k (r)),
where the infimum is taken over all tests ψ. Clearly,

γ = inf α∈(0,1) (α + β(α)), 0 ≤ γ ≤ 1.
The aim of this paper is to establish the asymptotic detection boundary, i.e., the conditions on the separation constant r = r n,p,k , which delimit the zone where γ n,p,k (r) → 1 (indistinguishability) from that where γ n,p,k (r) → 0 (distinguishability). The distinguishability is equivalent to β(α) → 0, ∀ α ∈ (0, 1). We are interested in tests ψ = ψ n,p or ψ α = ψ n,p,α such that either γ(ψ) → 0 or α(ψ α ) ≤ α+o(1), and β(ψ α ) → 0. Here and later the limits are taken as p → ∞, n → ∞ unless otherwise stated.

Assumptions on X

We will use at different instances some of the following conditions on the random variables X ij . A1. The random variables

X ij are uncorrelated, i.e., EX ij X il = 0 for all 1 ≤ j < l ≤ p. A2. The random variables X ij , 1 ≤ j ≤ p, 1 ≤ i ≤ n, are independent. A3. The random variables X ij , 1 ≤ j ≤ p, 1 ≤ i ≤ n, are i.i.d. standard Gaussian: X ij ∼ N (0, 1).
Let U j , 1 ≤ j ≤ p be random variables such that we have equality in distribution L(U j , U l ) = L(X ij , X il ), 1 ≤ j < l ≤ p. We will need the following technical assumptions.

B1

.

max 1≤j<l≤p E((U j U l ) 4 ) = O(1) . (3.1)
B2. There exists h 0 > 0 such that max 1≤j≤l≤p E(exp(hU j U l )) < ∞ for |h| < h 0 , and

log 3 (p) = o(n). (3.2) B3. There exists m ∈ IN such that max 1≤j≤l≤p E(|U j U l | m ) < ∞, and
log 2 (p)p 4/m = o(n). (3.3) Assumption B1 implies that max 1≤j<l≤p E(|U j U l | m ) = O(1), m = 2, 3, 4 . (3.4)
In particular, Assumption B1 holds true under A2 if

max 1≤j≤p E(U 4 j ) = O(1). (3.5)
If (X ij X il , i = 1, . . . , n) are independent zero-mean random variables, we have (cf. [START_REF] Petrov | Limit theorems of probability theory[END_REF], p. 79):

E|(X j , X l )| m ≤ C(m)n m/2-1 n i=1 E(|X ij X il | m ), m > 2 .
This and (3.4)

yield 1≤j<l≤p E(|(X j , X l )| m ) = O(n m/2 p 2 ), m = 2, 3, 4 . (3.6)
Finally, Assumptions B1 and B2 hold true under A3 and (3.2).

4 Main results

Detection boundary under known variance

For this case we suppose σ = 1 without loss of generality.

Lower bounds

We first present the lower bounds on the detection error, i.e., the indistinguishability conditions. We assume that k = p 1-β , β ∈ (0, 1). Indistinguishability conditions consist of two joint conditions on the radius r = r np . The first one is

r 2 np = o(n -1/2 ). (4.1)
The second condition differs according to whether β ≤ 1/2 or β > 1/2. If β ≤ 1/2 (i.e. p = O(k 2 )), which corresponds to moderate sparsity, we require that

r 2 np = o( √ p/n) . (4.2)
The case β > 1/2 (i.e. k 2 = o(p)) corresponds to high sparsity. We define x np by r np = x n,p k log(p)/n. Then, we require that

lim sup(x n,p -ϕ(β)) < 0, (4.3)
where ϕ(β) is defined in (1.6). Clearly, condition (4.3) implies r 2 np = O(k log(p)/n), which is stronger than (4.2) when β > 1/2. Theorem 4.1 Assume A1, B1, k = p 1-β and either B2 or B3. We also require that r np satisfies (4.1) and either (4.2) (for β ∈ (0, 1/2]) or (4.3) (for β ∈ (1/2, 1)). Then, asymptotic distinguishability is impossible, i.e., γ n,p,k (r np ) → 1.

Remark 4.1 This theorem can be extended to non-random design matrix X. Inspection of the proof shows that, instead of B1, we only need the assumption: For some B n,p tending to ∞ slowly enough,

1≤j<l≤p |(X j , X l )| m < B n,p n m/2 p 2 , m = 2, 3, 4. (4.4)
Indeed, B1 is used in the proofs only to assure that (4.4) holds true with P Xprobability tending to 1 (this is deduced from assumption B1 and (3.6)). Also instead of B2 and B3, we can assume that there exists η n,p → 0 such that

r 2 np max 1≤j<l≤p |(X j , X l )| < η n,p k, max 1≤j≤p | X j 2 -n| < η n,p n. (4.5)
Under B2, B3, relations (4.5) hold with P X -probability tending to 1, see Corollary 7.1.

The result of the theorem remains valid for non-random matrices X satisfying (4.4) and (4.5).

Upper bounds

In order to construct a test procedure that achieves the detection boundary, we combine several tests.

First, we study the widest non-sparse case k = p, i.e., we consider Θ p (r) = {θ ∈ IR p : θ ≥ r}. Consider the statistic

t 0 = (2n) -1/2 n i=1 (Y 2 i -1), (4.6)
which is the H 0 -centered and normalized version of the classical χ 2 n -statistic n i=1 Y 2 i . The corresponding tests ψ 0 α and ψ 0 are of the form:

ψ 0 α = 1I t 0 >uα , ψ 0 = 1I t 0 >Tnp
where α ∈ (0, 1), u α is the (1α)-quantile of the standard Gaussian distribution and T np is any sequence satisfying T np → ∞.

Theorem 4.2 For all α ∈ (0, 1), we have: (i) Type I errors satisfy α(ψ 0 α ) = α + o(1) and α(ψ 0 ) = o(1). (ii) Type II errors. Assume A2 and B1 and consider a radius r np such that nr 4 np → ∞. Then, we have

β(ψ 0 α , Θ p (r np )) → 0. If T np is chosen such that lim sup T np n -1/2 r -2 np < 1, then β(ψ 0 , Θ p (r np )) → 0.
Recall that we can replace B1 by (3.5) under A2. If nr 4 np → ∞, then one can take T np such that γ n,p (ψ 0 , Θ p (r np )) → 0 under A2, B1. This upper bound corresponds to the part (4.1) of the detection boundary.

We now introduce a test ψ 1 α that achieves the second boundary (4.2). Consider the following kernel

K(Z i , Z k ) = p -1/2 Y i Y k p j=1 X ij X kj .
The U-statistic t 1 based on the kernel K is defined by

t 1 = N -1/2 1≤i<k≤n K(Z i , Z k ), N = n(n -1)/2.
Note that the U-statistic t 1 can be viewed as the H 0 -centered and normalized version of the statistic χ 2 p = n p j=1 θ2 j based on the estimators θj = n -1 n i=1 Y i X ij :

χ 2 p = 2n -1 p j=1 1≤i<k≤n Y i Y k X ij X kj + n -1 p j=1 n i=1 Y 2 i X 2 ij .
Indeed, up to a normalization, the first sum is the U-statistic t 1 , and moving off the second sum corresponds to centering. Given α ∈ (0, 1), we consider the test ψ 1 α = 1I We can omit the condition p = o(n 2 ) since the test ψ 0 α/2 achieves the optimal rate for p ≥ n. Combining this bound with Theorem 4.1, we conclude that ψ * α simultaneously achieves the optimal detection rate for all β ∈ (0, 1/2].

We now turn to testing in the highly-sparse case β ∈ (1/2, 1). Here we use a version of "Higher Criticism Tests" (HC-tests, cf. [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF]). Set

y i = (Y, X i )/ Y , 1 ≤ i ≤ p.
Let q i = P (|N (0, 1)| > |y i |) be the p-value of the i-th component and let q (i) denote these quantities sorted in increasing order. We define the HC-statistic by simultaneously achieves the optimal detection rate for all β ∈ (1/2, 1).

t HC = max i, q (i) ≤1/2 √ p(i/p -q (i) ) q (i) (1 -q (i) ) . ( 4
In conclusion, under Assumption A3, the test max(ψ 0 α/2 , ψ 1 α/2 , ψ HC ) simultaneously achieves the optimal detection rate for all β ∈ (0, 1). The detection boundary is of the order of magnitude

r ≍ k log p n ∧ 1 n 1/4 . (4.8)
Furthermore, we establish the sharp detection boundary (i.e., with exact asymptotic constant) of the form

r = ϕ(β) k log p n for β > 1/2 and k log(p) = p 1-β log(p) = o( √ n).

Detection boundary under unknown variance 4.2.1 Detection problem

Since the variance of the noise is now assumed to be unknown, the tests ψ under study should not require the knowledge of σ 2 . The type I error probability is now taken uniformly over σ > 0:

α un (ψ) = sup σ>0 E 0,σ (ψ) .
The type II error probability over an alternative Θ ⊂ R p is

β un (ψ, Θ) = sup θ∈Θ,σ>0 β(ψ, θσ, σ) = sup θ∈Θ,σ>0 E θσ,σ (1 -ψ) . (4.9)
Similarly to the setting with known variance, we consider the sum of the two errors:

γ un (ψ, Θ) = α un (ψ) + β un (ψ, θ).
Finally, the minimax total error probability in the hypothesis testing problem with unknown variance is

γ un n,p,k (r) = inf ψ γ un (ψ, Θ k (r))

Lower bounds

Take r np = x n,p k log(p)/n. As in the case of known variance, we consider the condition lim sup(x n,pϕ(β)) < 0 .

(p) = o(n), then distinguishability is impossible, i.e., γ un n,p,k (r np ) → 1 . If k log(p)/n → ∞, then for any radius r > 0, distinguishability is impossible, i.e. γ un n,p,k (r) → 1.
The detection boundary stated in Theorem 4.5 does not depend on the unknown σ 2 . This is due to the definition (4.9) of the type II error probability β un (ψ, Θ k (r)) that considers alternatives of the form σθ with θ ∈ Θ k (r).

Upper bounds

The HC-test ψ HC defined in (4.7) still achieves the optimal detection rate when the variance is unknown as shown by the next proposition. (ii) Type II error. Consider k = p 1-β with β ∈ (1/2, 1) and assume that k log(p) = o(n). Take a radius r np = x np k log(p)/n such that lim inf(x npϕ(β)) > 0. Then, we have β un (ψ HC , Θ k (r np )) → 0.

In conclusion, in the setting with unknown variance we prove that the sharp detection boundary (i.e., with exact asymptotic constant) of the form

ϕ(β) k log p n holds for β > 1/2 and k log(p) = p 1-β log(p) = o(n), i.e.
, for a larger zone of values (p, n) than for the case of known variance. However, this extension corresponds to (p, n) for which the rate itself is strictly slower than under the known variance. Indeed, if the variance σ 2 is known, as shown in Section 4.1, the detection boundary is of the order (4.8). Thus, there is an asymptotic difference in the order of magnitude of the two detection boundaries for k log(p) ≫ √ n.

5 Proofs of the lower bounds

The prior

Take c ∈ (0, 1), h = ck/p, b = r np /c √ k, a = b √ n. Note that the condition r 2 np = o(1/ √ n) is equivalent to b 4 k 2 n = o(1).
Let us consider a random vector θ = (θ j ) with coordinates θ j = bε j , where ε j ∈ (0, +1, -1) iid, such that

P rob(ε j = 0) = 1 -h, P rob(ε j = +1) = P rob(ε j = -1) = h/2.
This introduces a prior probability measure π j on θ j and the product prior measure π = p j=1 π j on θ. The corresponding expectation and variance operators will be denoted by E π and Var π .

Lemma 5.1 Let k → ∞. Then π(θ ∈ IR p k , θ ≥ r) → 1.
Proof. Observe that

θ 2 = b 2 p j=1 ε 2 j , m(θ) = p j=1 |ε j |.
We have

E π ( θ 2 ) = b 2 ph = r 2 /c, E π (m(θ)) = ph = ck, and Var π ( θ 2 ) ≤ phb 4 = r 4 /(kc 3 ), Var π (m(θ)) ≤ ph = ck.
Applying the Chebyshev inequality, we get with

C = c -1 > 1, π( θ 2 < r 2 ) = π(E π ( θ 2 ) -θ 2 > r 2 (C -1)) ≤ Var π ( θ 2 ) r 4 (C -1) 2 → 0,
and similarly, π(m(θ) > k) → 0. 2 Lemma 5.1 implies that, in order to obtain asymptotic lower bounds for the minimax problem, we only have to study the Bayesian problem which corresponds to the prior π, see for instance [START_REF] Ingster | Nonparametric goodness-of-fit testing under gaussian models[END_REF], Proposition 2.9. Consider the mixture

P π (dZ) = E π P θ (dZ) = IR p P θ (dZ)π(dθ)
and the likelihood ratio

L π (Z) = dP π dP 0 (Z).
In order to prove the lower bounds we only need to check that L π (Z) → 1 in P 0probability.

(5.1)

Consider x = lim sup x n,p . If β ≤ 1/2, then x = 0 since nb 2 = O(1)
. For β > 1/2, we take c ∈ (0, 1) such that x c = x/c < ϕ(β), which is possible as x < ϕ(β). We will use the short notation x and a for x c and a c = b

√ n = a/c. We set

a j = b X j , y ′ j = (X j , Y )/ X j , x j = a j / log(p), T j = a j /2 + log(h -1 )/a j ,
which corresponds to he -a 2 j +a j T = 1.

Study of the likelihood ratio L π

First observe that by (1.7)

P π (dZ) = P X (dX)E π P X θ (dY ) , L π (Z) = E π dP X θ dP X 0 (Y ) .
Note that conditional measure P X θ corresponds to observation of the Gaussian vector N (v, I n ) where v = p j=1 θ j X j , I n is the n × n identity matrix, and the likelihood ratio under the expectation is

dP X θ dP X 0 (Y ) = exp(-v 2 /2 + (v, Y )) = g θ (Z)e -∆(X,θ) ,
where

g θ (Z) = p j=1 exp(-θ 2 j X j 2 /2 + θ j (X j , Y )), ∆(X, θ) = 2 1≤j<l≤p θ j θ l (X j , X l ). (5.2) Put Λ(Z) = E π (g θ (Z)) = p j=1 (1 -h + he -b 2 X j 2 /2 cosh(b(X j , Y ))) . We define η j = e -b 2 X j 2 /2 cosh(b(X j , Y )) -1. Take now δ > 0 and introduce the set Σ X = {θ ∈ IR p : |∆(X, θ)| ≤ δ}.
We can write

L π (Z) = IR p g θ (Z)e -∆(X,θ) π(dθ) ≥ e -δ Σ X g θ (Z)π(dθ) = e -δ Λ(Z)π Z (Σ X ),
where π Z = p j=1 π Z,j is the random probability measure on IR p with the density

dπ Z dπ (θ) = g θ (Z) Λ(Z) = p j=1 dπ Z,j dπ j (θ); dπ Z,j dπ j (θ) = e -θ 2 j X j 2 /2+θ j (X j ,Y ) 1 + hη j , θ j ∈ {0, ±b},
i.e., the measure π Z,j is supported at the points {0, b, -b} and

π Z,j (0) = 1 -h 1 + hη j , π Z,j (±b) = h ± Z,j 2 , h ± Z,j = he d j ± 1 + hη j ,
where we set

d ± j = -a 2 j /2 ± a j y ′ j , η j = e d + j 2 + e d - j 2 -1. Proposition 5.1 In P 0 -probability, π Z (Σ X ) → 1. (5.3)
Proof of Proposition 5.1 is given in Section 5.3.

Proposition 5.2 In P 0 -probability,

Λ(Z) → 1.
(5.4)

Proof of Proposition 5.2 is given in Section 5.4.

Propositions 5.1 and 5.2 imply that, for any δ > 0, Let us consider the random measure πZ = p j=1 πZ,j , where πZ,j is supported at the points {0, b, -b} and πZ,j (0

P 0 (Z : L π (Z) > 1 -δ) → 1. Since E 0 L π = 1 and L π (Z) ≥ 0, this yields L π → 1 in P 0 -
) = 1 - q + Z,j 2 - q - Z,j 2 , πZ,j (±b) = q ± Z,j 2
,

where q ± Z,j = (h/2)e d j ± 1I A ± j , A ± j = {he d j ± < 1} = {±y ′ j < T j }
and observe that the event A ± j implies q ± Z,j ≤ 1/2, i.e, the measures πZ,j are correctly defined. We define the event

A = A np = ∩ p j=1 (A + j ∩ A - j ). Lemma 5.2 P 0 (A n,p ) → 1.
Proof. Denote A c the complement of the event A. Since y ′ j ∼ N (0, 1) under P 0 , we have

P X 0 ((A n,p ) c ) ≤ p j=1 P X 0 ((A + j ) c ) + P X 0 ((A - j ) c ) = 2 p j=1 Φ(-T j ).
By Corollary 7.1 we get a j = b X j ∼ b √ n uniformly in 1 ≤ j ≤ p in P Xprobability. By (7.1) this implies p j=1 Φ(-T j ) = o(1) in P X -probability. 2 We can replace the measure π Z by πZ in (5.3). This follows from the following lemma Lemma 5.3 In P 0 -probability,

E πZ |dπ Z /dπ Z -1| → 0.
(5.5)

Proof. Applying the equality E πZ (dπ Z /dπ Z ) = 1 and the inequality 1 + x ≤ e x , we get

(E πZ |dπ Z /dπ Z -1|) 2 ≤ E πZ (dπ Z /dπ Z -1) 2 = E πZ (dπ Z /dπ Z ) 2 -1 = p j=1 E πZ,j (dπ Z,j /dπ Z,j ) 2 -1 = p j=1 (1 + E πZ,j (dπ Z,j /dπ Z,j -1) 2 ) -1 ≤ exp p j=1 E πZ,j (dπ Z,j /dπ Z,j -1) 2 -1.
Consequently, we only have to prove that in P 0 -probability,

H(Z) = p j=1
E πZ,j (dπ Z,j /dπ Z,j -1) 2 → 0.

Since H(Z) ≥ 0, the last relation follows from

E X 0 (H) → 0, in P X -probability by Markov inequality. Observe that E πZ,j (dπ Z,j /dπ Z,j -1) 2 = (h + Z,j -q + Z,j ) 2 2q + Z,j + (h - Z,j -q - Z,j ) 2 2q - Z,j + (h + Z,j + h - Z,j -q + Z,j -q - Z,j ) 2 2(2 -q + Z,j -q - Z,j )
.

By Lemma 5.2, it is sufficient to study these terms under the event A which corresponds to max 1≤j≤p q ± Z,j ≤ 1/2. Under this event, we have h ± Z,j = q ± Z,j /λ j , λ j = 1 + q + Z,j + q - Z,jh, and direct calculation gives

(h + Z,j -q + Z,j ) 2 2q + Z,j + (h - Z,j -q - Z,j ) 2 2q - Z,j + (h + Z,j + h - Z,j -q + Z,j -q - Z,j ) 2 2(2 -q + Z,j -q - Z,j ) = (q + Z,j + q - Z,j )∆ 2 j λ 2 j (2 -q + Z,j -q - Z,j )
, where

∆ j = q + Z,j + q - Z,j -h = h(e d + j 1I A + j + e d - j 1I A - j -2)/2. Since max 1≤j≤p q ± Z,j ≤ 1/2, we only have to control the sum p j=1 ∆ 2 j . E X 0 1I A ∆ 2 j ≤ h 2 2 e a 2 j Φ(T j -2a j ) + e -a 2 j -4Φ(T j -a j ) + 2 . CASE 1: nb 2 = O(1)
. By corollary 7.1, (a j /( √ nb) -1) = o P X (1). Consequently,

Φ(T j -2a j ) = 1 -o P X (p -2 ). E X 0 1I A p j=1 ∆ 2 j ≤ ph 2 2 sinh 2 (nb 2 (1+o p X (1))/2)+o P X (1) = ph 2 nb 2 2 +o P X (1) = o P X (1) , since r 2 n,p = o( √ p/n). CASE 2: lim sup nb 2 = ∞. This implies that k 2 = o(p) and therefore ph 2 = o(1). E X 0 1I A p j=1 ∆ 2 j = ph 2 2 e nb 2 (1+o P X (1)) + o(1) = p -(2β-1)+x 2 +o P X (1) + o(1) . Since x < ϕ(β) ≤ √ 2β -1 for β > 1/2, this allows to conclude. 2 5.3.2 Study of E πZ ∆ 2
By Lemma 5.2, the relation (5.3) follows from π(Σ) → 1, in P 0 -probability. Thus, we only need to check that in P 0 -probability, E πZ ∆ 2 → 0 for ∆ = ∆(X, θ) defined by (5.2). By Markov inequality, the last relation follows from

E X 0 (E πZ ∆ 2 )
)) → 0, in P X -probability. Let us introduce the events X n,p . Taking a positive family η = η n,p → 0, we set

X j = {( X j 2 -n) < ηn}, X ij = {log(p)|(X j , X l )| < ηn}, X n,p = 1≤j<l≤p X j ∩ X ij .
It follows from Corollary 7.1 that, under assumptions B2 or B3 we can take η = η n,p → 0 such that P X (X n,p ) → 1. We have

E πZ ∆ 2 = b 4 E πZ p j 1 ,j 2 ,j 3 ,j 4 =1 θ j 1 θ j 2 θ j 3 θ j 4 (X j 1 , X j 2 )(X j 3 , X j 4 ) = 2A 2 + 6A 3 + 24A 4 ,
where

A 2 = b 4 1≤j 1 <j 2 ≤p E πZ ǫ 2 j 1 ǫ 2 j 2 (X j 1 , X j 2 ) 2 , (5.6)
A 3 = b 4 1≤j 1 <j 2 <j 3 ≤p E πZ ǫ 2 j 1 ǫ j 2 ǫ j 3 (X j 1 , X j 2 )(X j 1 , X j 3 ), (5.7)
A 4 = b 4 1≤j 1 <j 2 <j 3 <j 4 ≤p E πZ (ǫ j 1 ǫ j 2 ǫ j 3 ǫ j 4 ) (X j 1 , X j 2 )(X j 3 , X j 4 ). ( 5
E πZ ǫ 2 j 1 ǫ 2 j 2 = (q + j 1 + q - j 1 )(q + j 2 + q - j 2 ) 4 = 1 4 η 1 ,η 2 2 k=1 q η k j k , (5.9)
E πZ ε 2 j 1 ε j 2 ε j 3 = (q + j 1 + q - j 1 )(q + j 2 -q - j 2 )(q + j 3 -q - j 3 ) 8 = η 1 ,η 2 ,η 3 η 2 η 3 8 3 k=1 q η k j k
(5.10)

E πZ (ε j 1 ε j 2 ε j 3 ε j 4 ) = 1 16 4 k=1 (q + j k -q - j k ) = 1 16 η 1 ,η 2 ,η 3 ,η 4 η 1 η 2 η 3 η 4 4 k=1 q η k j k . (5.11)
Let us take the expectation E X 0 over Y of each of these expressions. We define the vector

V = b m k=1 η k X j k .
Here, E X V refers to the expectation of Y over the Gaussian measure N (V, I n ). We derive that

E X 0 m k=1 q η k j k = h m 2 m E X 0 e -1 2 m k=1 b 2 X j k 2 +b(Y, m k=1 η k X j k ) m k=1 1I {(Y,η k X j k )<T j k X j k } = h m 2 m exp b 2 1≤r<s≤m η r η s (X jr , X js ) E X 0 e -1 2 V 2 +(Y,V ) m k=1 1I {(Y,η k X j k )<T j k X j k } = h m 2 m exp b 2 1≤r<s≤m η r η s (X jr , X js ) E X V m k=1 1I {(Y,η k X j k )<T j k X j k } = h m 2 m exp b 2 1≤r<s≤m
η r η s (X jr , X js ) P j 1 ,...,jm (η), where

P j 1 ,...,jm (η) = E X V m k=1 1I {(Y,η k X j k )<T j k X j k } = E X 0 m k=1 1I {(Y +V,η k X j k )<T j k X j k } = E X 0 m k=1 1I {(Y,η k X j k )<T j k X j k -(V,η k X j k )} = E X 0 m k=1 1I {η k y ′ j k <T j k -(V,η k X j k )/ X j k } .
Let us define

m j k (η) = η k m s=1, s =k η s (X js , X j k )/ X j k , z k = η k y ′ j k .
Then, P j 1 ,...,jm (η) writes as

P j 1 ,...,jm (η) = P X 0 (z 1 < T j 1 -a j 1 -bm j 1 (η) . . . , z m < T jm -a jm -bm jm (η)) .
We have

E X 0 2 k=1 q ε k j k = h 2 4 exp η 1 η 2 b 2 (X j 1 , X j 2 ) P j 1 ,j 2 (η),
(5.12)

E X 0 3 k=1 q ε k j k = h 3 8 exp b 2 1≤s<r≤3
η s η r (X js , X jr ) P j 1 ,j 2 ,j 3 (η), (5.13)

E X 0 4 k=1 q ε k j k = h 4 16 exp b 2 1≤s<r≤4
η s η r (X js , X jr ) P j 1 ,j 2 ,j 3 ,j 4 (η). (5.14)

Evaluation of probabilities

P j 1 ,...,jm (η)
By definition of (z 1 , . . . , z m ) we have

E X 0 z k = 0, E X 0 z 2 k = 1, E X 0 z k z s ∆ = r ks (η) = η k η s (X j k , X js ) X j k X js , 1 ≤ k < s ≤ m. Denote Tj k = T j k -a j k . Observe that P j 1 ,...,jm (η) = 1 - m k=1 Φ(-Tj k -bm j k (η)) + O 1≤k<s≤m P r ks (η) -Tj k -bm j k (η), -Tjs -bm js (η) , (5.15)
where we set, for the Gaussian random vector (z 1 , z 2 ) with Ez k = 0,

Ez 2 k = 1, k = 1, 2, Ez 1 z 2 = r, P r (t 1 , t 2 ) = P (z 1 < t 1 , z 2 < t 2 ) = P (z 1 > -t 1 , z 2 > -t 2 ).
The control of P j 1 ,...,jm (η) then depends on the sequence x np . CASE 1: x = 0. Under the event X n,p , we have max j a j = o( log(p)) and Tj k / log(p) → ∞. Under the event X np , we have

b|m jk (η)| ≤ b s =k |(X js , X j k )|/ X j k ≤ o(b √ n/ log(p)) = o(1/ log(p)) . It follows that max j Φ(-Tj k -bm j k (η)) = o(p -α ), ∀ α > 0.
We conclude

P j 1 ,...,jm (η) = 1 -O m k=1 Φ(-Tj k -bm j k (η)) = 1 -o(p -α ), ∀ α > 0. ( 5
m k=1 Φ(-Tj k -bm j k (η)) = m k=1 Φ(-Tj k ) -b m k=1 m j k (η)Φ(-Tj k ) + b 2 m k=1 O m 2 j k (η) Tj k Φ(-Tj k ) .
Let us define Let us turn to the second term in (5.15). If Tj k ≥ log(p), then

R m ∆ = m k=1 Φ(-Tj k ) = o((ph) -1 ), ( 5
(X js , X j k )Φ(-Tj k )/ X j k = O T j k (X js , X j k )Φ(-Tj k )n -1 = O T j k Φ(-Tj k )|r ks | = o(|r ks |/(ph)) b 2 (X js , X j k ) 2 Tj k Φ(-Tj k )n -1 = O(T 3 j k )Φ(-Tj k )r 2 ks = o(r 2 ks /(ph)). It follows that m k=1 Φ(-Tj k -bm j k (η)) = R m -
P r ks (η) -Tj k -bm j k (η), -Tjs -bm js (η) ≤ Φ(-Tj k -bm j k (η)) = o( (ph) -2
If Tj k ≤ log(p), we have Tj k r ks = o(1) under the event X np . By Lemma 7.3 and previous evaluations, we get

P r ks (η) -Tj k -bm j k (η), -Tjs -bm js (η) = Φ(-Tj k -bm j k (η)) Φ(-Tjs -bm js (η))O 1 + r 2 ks + |r ks | = o (ph) -2
. Finally, we obtain

P j 1 ,...,jm (η) = 1 -R m + o 1≤k<s≤m |r ks |/ph + o((ph) -2 ) (5.18) = 1 + o((ph) -1
).

(5.19)

Evaluation of A 2

We have b 2 max 1≤j 1 <j 2 ≤p |(X j 1 , X j 2 )| = o(1) under the event X n,p . Since P j 1 ,j 2 (η) = O(1), we get from (5.12)

E X 0 2 k=1 q ε k j k = O(h 2 ).
By Assumption B1, we have

sup j 1 =j 2 E X (X j 1 , X j 2 ) 2 = O(n) .
It then follows from (5.6) and (5.9) that A 2 is of the order

b 4 h 2 1≤j 1 <j 2 ≤p (X j 1 , X j 2 ) 2 ≍ p 2 h 2 b 4 n ≍ nk 2 b 4 → 0 ,
in P X -probability.

Evaluation of A 3

Let us turn to A 3 . Consider η k as independent random variables taking values in {-1, 1} with probabilities 1/2. By (5.10) and (5.13), we can write

E πZ θ 2 j 1 θ j 2 θ j 3 = h 3 8 E η η 2 η 3 exp b 2 1≤s<r≤3 η s η r (X js , X jr ) P j 1 ,j 2 ,j 3 (η) .
Under the event X n,p it follows from (5.16), (5.19), and the definition of X n,p that

P j 1 ,j 2 ,j 3 (η) = 1 + o((ph) -1
) and b 2 1≤s<r≤3 η s η r (X js , X jr ) = o(1).

It follows that

E πZ θ 2 j 1 θ j 2 θ j 3 = h 3 8 E η η 2 η 3 exp b 2 1≤s<r≤3 η s η r (X js , X jr ) + o h 2 p -1 .
By Taylor expansion of the exponential function, the expectation over η is of the form, for c sr = b 2 (X js , X jr ),

E η η 2 η 3 1 + η 1 η 2 c 12 + η 1 η 3 c 13 + η 2 η 3 c 23 + O c 2 12 + c 2 13 + c 2 23 = b 2 (X j 2 , X j 3 ) + O b 4 1≤s<r≤3 (X js , X jr ) 2 .
Under the event X n,p , we derive from (5.7) that

A 3 ≤ h 3 b 6 O(H 1 ) + b 8 O(H 2 ) + b 4 o(H 3 h 2 p -1 ),
where

H 1 = 1≤j 1 <j 2 <j 3 ≤p |(X j 1 , X j 2 )||(X j 1 , X j 3 )||(X j 2 , X j 3 )|, H 2 = 1≤j 1 <j 2 <j 3 ≤p 1≤s<r≤3 |(X j 1 , X j 2 )||(X j 1 , X j 3 )|(X js , X jr ) 2 , H 3 = 1≤j 1 <j 2 <j 3 ≤p |(X j 1 , X j 2 )||(X j 1 , X j 3 )|. Since |(X j 1 , X j 2 )||(X j 1 , X j 3 )||(X jr , X js )| ≤ |(X j 1 , X j 2 )| 3 + |(X j 1 , X j 3 )| 3 + |(X jr , X js )| 3 , |(X j 1 , X j 2 )||(X j 1 , X j 3 )|(X j 2 , X j 3 ) 2 ≤ (X j 1 , X j 2 ) 4 + (X j 1 , X j 3 ) 4 + (X j 2 , X j 3 ) 4 , |(X j 1 , X j 2 )||(X j 1 , X j 3 )| ≤ (X j 1 , X j 2 ) 2 + (X j 1 , X j 3 ) 2 ,
we derive from (3.6)

E X H 1 = O(p 3 n 3/2 ), E X H 2 = O(p 3 n 2 ), E X H 1 = O(p 3 n).
Applying Markov's inequality yields

H 1 = O P X (p 3 n 3/2 ), H 2 = O P X (p 3 n 2 ), H 1 = O P X (p 3 n).
Combining these bounds, we obtain

A 3 = O P X ((b 6 h 3 p 3 n 3/2 ) + O P X (b 8 h 3 p 3 n 2 ) + b 4 o P X (b 4 h 2 p 2 n). Since b 4 k 2 n = o(1), hp ≍ k, b = o(1)
, we get A 3 = o P X (1).

Evaluation of A 4

Let us evaluate the item A 4 . Similarly to A 3 , we can write

E πZ (θ j 1 θ j 2 θ j 3 θ j 4 ) = h 4 E η η 1 η 2 η 3 η 4 exp b 2 1≤s<r≤4
η s η r (X js , X jr ) P j 1 ,j 2 ,j 3 ,j 4 (η) .

(5.20)

Under the event X n,p we have

b 2 1≤s<r≤4 η s η r (X js , X jr ) = o(1)
.

CASE 1: x > 0. By (5.18), we have

P j 1 ,j 2 ,j 3 ,j 4 (η) = 1 -R 4 + o 1≤s<r≤4 |r sr |/hp + o((ph) -2 ). 20
Applying a Taylor expansion of the exponential term in (5.20) yields

E η η 1 η 2 η 3 η 4 exp b 2 1≤s<r≤4 η s η r (X js , X jr ) P j 1 ,j 2 ,j 3 ,j 4 (η) = E η η 1 η 2 η 3 η 4 1 + b 2 1≤s<r≤4 η s η r (X js , X jr ) (1 -R 4 ) + O(|δ 1 |) + O(|δ 2 |) = O(|δ 1 |) + O(|δ 2 |),
where

δ 1 = O b 4 1≤s<r≤4 (X js , X jr ) 2 , δ 2 = o 1≤k<s≤4 |r ks |/ph + o((ph) -2 ) .
CASE 2: x = 0. By (5.16), P j 1 ,j 2 ,j 3 ,j 4 (η) = 1o(p -2 ). Arguing as in Case 1, we get

E η η 1 η 2 η 3 η 4 exp b 2 1≤s<r≤4 η s η r (X js , X jr ) P j 1 ,j 2 ,j 3 ,j 4 (η) = O b 4 1≤s<r≤4 (X js , X jr ) 2 + o(p -2 ).
All in all, we obtain that under the event X n,p ,

A 4 ≤ h 4 b 8 O(H 1 ) + o(H 2 b 4 h 4 /p 2 ), x = 0, o(H 3 b 4 h 3 /np + H 2 b 4 h 2 /p 2 ), x > 0,
where

H 1 = 1≤j 1 <j 2 <j 3 <j 4 ≤p |(X j 1 , X j 2 )||(X j 3 , X j 4 )| 1≤s<r≤4 (X js , X jr ) 2 , H 2 = 1≤j 1 <j 2 <j 3 <j 4 ≤p |(X j 1 , X j 2 )||(X j 3 , X j 4 )|, H 3 = 1≤j 1 <j 2 <j 3 <j 4 ≤p |(X j 1 , X j 2 )||(X j 3 , X j 4 )| 1≤s<r≤4 |(X js , X jr )|.
We combine the classical upper bounds,

|(X j 1 , X j 2 )||(X j 3 , X j 4 )|(X js , X jr ) 2 ≤ (X j 1 , X j 2 ) 4 + (X j 3 , X j 4 ) 4 + (X js , X jr ) 4 , |(X j 1 , X j 2 )||(X j 3 , X j 4 )| ≤ (X j 1 , X j 2 ) 2 + (X j 3 , X j 4 ) 2 , |(X j 1 , X j 2 )||(X j 3 , X j 4 )||(X js , X jr )| ≤ |(X j 1 , X j 2 )| 3 + |(X j 3 , X j 4 )| 3 + |(X js , X jr )| 3 .
with (3.6) and obtain

E X (H 1 ) = O(p 4 n 2 ), E X (H 2 ) = O(p 4 n), E X (H 3 ) = O(p 4 n 3/2 ).

Applying Markov's inequality yields

H 1 = O P X (p 4 n 2 ), H 2 = O P X (p 4 n), H 3 = O P X (p 4 n 3/2 ). Since b 4 k 2 n = o(1), hp ≍ k, we get h 4 b 8 H 1 = O(h 4 p 4 b 8 n 2 ) = o P X (1), H 2 b 4 h 2 /p 2 = O P X (b 4 h 2 p 2 n) = o P X (1).
If x > 0, we also have to upper bound the term H 3 . Since r 2 n,p = o(1/ √ n) (cf. (4.1)) and since x > 0, we derive that k = o( √ n). Then, we get

H 3 b 4 h 3 /np = O P X (b 6 p 3 h 3 n 3/2 /nb 2 ) = o P X (1),
Therefore we obtain A 4 = o P X (1). The proposition follows. 2

Proof of Proposition 5.2

We will prove that there exists a family of events Z n,p such that P 0 (Z n,p ) → 1 and

log(Λ(Z)) = p j=1 log 1 + (h/2) e d + j + e d - j -2 → 0, Z ∈ Z n,p .
We take Z n,p = {(X, Y ) : |y ′ j | ≤ T j , 1 ≤ j ≤ p, X ∈ X n,p } where X n,p was defined in Section 5.3.2. It follows from Lemma 5.2 and Section 5.3.2 that P 0 (Z n,p ) → 1.

Under the events Z n,p we can replace the quantities (h/2)e d ± j /2 by q ± j = (h/2)e d ± j 1I ±y ′ j <T j , cf. Section 5.3.1. Let us consider L = p j=1 log(1 + ∆ j ), ∆ j = (q + j + q - jh).

Under the event A = A n,p = p j=1 (A + j + A - j ) defined in Section 5.3.1, we have uniformly in 1 ≤ j ≤ p,

q + j + q - j = h 2 e -a 2 j /2 cosh(a j y ′ j ) ≤ he -a 2 j /2 cosh(a j T j ) = (1 + e -2a j T j )/2 ∼ 1/2,
as h → 0. Consequently, we have

L = p j=1 = A 1 + O(A 2 ), A 1 = p j=1 ∆ j , A 2 = p j=1 ∆ 2 j .
Thus, we need to show that A 1 → 0 and that A 2 → 0 in P 0 -probability. It was stated in the proof of Lemma 5.3 that E X 0 A 2 = o P X (1). Markov's inequality then allows to derive that A 2 = o P X (1). In order to prove the first relation, we shall show that E X 0 A 1 → 0 and that Var X 0 A 1 → 0 in P 0 -probability. Observe that

E X 0 A 1 = h p j=1 (Φ(T j -a j ) -1) = -h p j=1
Φ(-T j + a j ). By (7.1) and ( 7.2) we have

h p j=1 Φ(-T j + a j ) ≍ p j=1 Φ(-T j ) = o(1).
We have Var X 0 A 1 ≤ B + A 2 with B = 1≤j<l≤p ∆j ∆l and ∆j = ∆ j -E X 0 ∆ j . We need to check that, in P X probability,

E X 0 (B) = 1≤j<l≤p E X 0 ( ∆j ∆l ) → 0.
Note that E X 0 ( ∆j ∆l ) = B jl -C jl , where

B jl = E X 0 (q + j + q - j )(q + l + q - l ) , C jl = h 2 Φ(T j -a j )Φ(T l -a l ) .
We consider independent random variables η 1 , η 2 taking values -1 and 1 with probabilities 1/2. We write (compare with (5.12))

B jl = h 2 E η exp η 1 η 2 b 2 (X j , X l ) P j,l (η) , C jl = h 2 P 0 j,l .
Here we set P 0 j,l = Φ( Tj )Φ( Tl ) = 1 -Φ(-Tj ) -Φ(-Tl ) + Φ(-Tj )Φ(-Tl ), Tl = T la l .

We obtain the new decomposition

B jl -C jl = h 2 (U jl + V jl ) , (5.21)
where

U jl = E η exp (η 1 η 2 b 2 (X j , X l ) -1 P j,l (η) , V jl = E η P j,l (η) -P 0 j,l .
Let us recall some notations introduced in Section 5.3.4. r jl (η) = η 1 η 2 r jl ,

r jl = (X j , X l ) X j X l , m jl (η) = η 1 η 2 (X j , X l ) X j , m lj (η) = η 1 η 2 (X j , X l ) X l .
Moreover, z j and z l stand for standard Gaussian variables with Cov(z j , z l ) = r jl (η). Then, P j,l (η) is written as

P j,l (η) = P X 0 (z j < Tj -bm jl (η), z l < Tl -bm lj (η)) = 1 -Φ(-Tj + bm jl (η)) -Φ(-Tl + bm lj (η))
+P X 0 (z j < -Tj + bm jl (η), z l < -Tl + bm lj (η)) .

CASE 1: x = 0. The evaluations of the terms V jl in (5.21) are similar to the ones in Section 5.3.4. We get

P 0 j,l = 1 -o(p -2 ), P j,l (η) = 1 -o(p -2 ), |P j,l (η) -P 0 j,l | = o(p -2 ).
We derive that h 2 1≤j<l≤p V j,l = o(h 2 ).

CASE 2: x > 0. We have (compare with (5.17) and (5.19))

Φ(-Tj )Φ(-Tl ) = o((ph) -2 ), P X 0 (z j < -Tj + bm jl (η), z l < -Tl + bm lj (η)) = o((ph) -2 ), Φ(-Tj + bm jl (η)) = Φ(-Tj ) + η 1 η 2 br jl + o(r 2 jl /(ph)) ,
Taking the expectation over η, we get

E η (P j,l (η)) -P 0 j,l = o(r 2 jl /(hp)) + o((ph) -2 ).
in P X -probability. Therefore

h 2 1≤j<l≤p V jl = O(Hhp -1 ) + o(1), H = 1≤j<l≤p r 2 jl .
Under X n,p we have r 2 jl ∼ n -2 (X j , X l ) 2 . Since E X [(X j , X l ) 2 ] = O(n) for j = l (Assumption B1), we get

H ∼ n -2 1≤j<l≤p (X j , X l ) 2 = O P X (n -1 p 2 ) .
This leads to h 2 1≤j<l≤p V jl = O P X (ph/n) + o(1). Since r 2 n,p = o(1/ √ n) (Eq. 4.1) and since x > 0, we derive that k = o( √ n). Consequently, we have

ph/n = O(k/n) = o(1).
Let us turn to the terms U jl . They are handled as in Section 5.3.2. We have

U jl = E η η 1 η 2 b 2 (X j , X l ) + O b 4 (X j , X l ) 2 1 + o((ph) -1 ) = O b 4 (X j , X l ) 2 + O b 2 |(X j , X l )|/(ph) .
Then, we get

h 2 1≤j<l≤p U jl = O h 2 b 4 H 1 + O hb 2 H 2 /p ,
where

H 1 = 1≤j<l≤p (X j , X l ) 2 , H 2 = 1≤j<l≤p |(X j , X l )| ≤ pH 1/2 1 .
Arguing as for H, we get

H 1 = O P X (p 2 n), H 2 = O P X (p 2 n 1/2 ). It follows that 1≤j<l≤p B jl = O P X (p 2 h 2 b 4 n) + O P X (phb 2 n 1/2 ) = o P X (1), since p 2 h 2 b 4 n ≍ k 2 b 4 n → 0 by (4.1)
. The proposition follows. 2

Proof of Theorem 4.5

An in the proof of Theorem 4.1, we consider x = lim sup x n,p and we take c ∈ (0, 1) such that x c = x/c < ϕ(β). We also define b = x c log(p)/n. We first consider the case where k log(p)/n → 0. We use a different prior π than for Theorem 4.1. Let us note M(k, p) the collection of subsets of {1, . . . , p} of size k. We consider a random vector θ = (θ j ) with coordinates θ j = bǫ j where ǫ j ∈ (0, 1). The set of non-zero coefficient of ǫ is drawn uniformly in M(k, p). This introduces a prior probability π on θ.

Consider the mixture

P π (dZ) = E π P θ, √ 1-bk 2 (dZ) = R p P θ, √ 1-bk 2 (dZ)π(dθ)
and the likelihood ratio

L π (Z) = dP π dP 0,1 (Z) .
As in the proof of Theorem 4.1, we shall prove that L π (Z) converges to 1 in P 0 probability. This will enforce that γ un n,p,k [x c k log(p)/ √ 1kb 2 ] → 1. Since kb 2 converges to 0, this will complete the proof.

The likelihood ratio has the form

L π (Z) = m∈M(k,p) |M(k, p)| -1 L m (Z) and L m (Z) = (1 -kb 2 ) -n/2 exp - kb 2 Y 2 2(1 -kb 2 ) + b(Y, i∈m X i ) 1 -kb 2 × exp - i,j∈m b 2 2(1 -kb 2 ) (X i , X j ) .
(5.22) Definition 5.1 Consider δ ∈ (0, 1), a positive integer s and a n × p matrix A. We say that A satisfies a δ-restricted isometry property of order s if for all θ ∈ R p s ,

(1 -δ) θ ≤ Aθ ≤ (1 + δ) θ .
Let us define the events Ω 1 and Ω 2 by Ω 1 : "X/ √ n satisfies a δ (1) n,p restricted isometry of order 2k"

Ω 2 : "For any 1 ≤ i ≤ p, (Y, X i / X i ) ≤ 2 log(p)(1 + δ (2) n,p )" ,
where δ

n,p = 16 k log(p)/n and δ

(2)

n,p = log -1/2 (p). Applying a deviation inequality due to Davidson and Szarek (Theorem 2.13 in [START_REF] Davidson | Local operator theory, random matrices and Banach spaces[END_REF]), we derive that P X (Ω c 1 ) = o(1). By the Gaussian concentration inequality, we have P 0 (Ω c

2 ) = o(1). Then, we take

Ω = Ω 1 ∩ Ω 2 . Lemma 5.4 We have E 0 [L 2 π (Z)1I Ω ] ≤ 1 + o(1). Lemma 5.5 We have E 0 [L π (Z)1I Ω c ] = o(1)
.

Since E 0 [L π (Z)] = 1, we get the desired result by combining these two lemmas.

Let us turn to the case k log(p)/n → ∞. We consider b > 0 defined by

kb 2 1 -kb 2 = (2β -1) k log(p) n .
Lemma 5. [START_REF] Davidson | Local operator theory, random matrices and Banach spaces[END_REF] We have

E 0 L 2 π (Z) = 1 + o(1) .
This lemma implies that for r = (2β -1)k log(p)/n → ∞, we have γ un n,p,k (r) → 1.

2

In the proof of the following lemmas, o(1) stands for a positive quantity which depends only on (k, p, n) and tends to 0 as (n, p) tend to infinity.

Proof of Lemma 5.4

In order to upper bound

E 0 [L 2 π (Z)1I Ω ], we first upper bound E 0 [L m 1 (Z)L m 2 (Z)1I Ω ] for any m 1 , m 2 ∈ M(k, p). We define W 1 , W 2 , W 3 by , W 1 = i∈m 1 \m 2 X i , W 2 = i∈m 2 \m 1 X i , and W 3 = i∈m 1 ∩m 2 X i . We note S = |m 1 ∩ m 2 |. L m 1 (Z)L m 2 (Z) = (1 -kb 2 ) -n exp - kb 2 Y 2 1 -kb 2 + b(Y, 2W 3 + W 1 + W 2 ) 1 -kb 2 × exp - b 2 2(1 -kb 2 ) ( W 1 + W 3 2 + W 2 + W 3 2 ) .
Let us take the expectation of

L m 1 (Z)L m 2 (Z) with respect to (W 1 , W 2 ). E Y,W 3 0 [L m 1 (Z)L m 2 (Z)] = (1 -Sb 2 ) -n exp - Y 2 Sb 2 1 -Sb 2 + 2b(Y, W 3 ) 1 -Sb 2 - b 2 W 3 2 1 -Sb 2 .
When S = 0, we have

E Y,W 3 0 [L m 1 (Z)L m 2 (Z)] = 1.
Let us now consider the case S > 0. On the event Ω, we have

(Y, W 3 W 3 ) ≤ 2 log(p)(1 + δ (2) n,p ) i∈m 1 ∩m 2 X i i∈m 1 ∩m 2 X i ≤ 2S log(p)(1 + o(1)) , since X/ √ n satisfies a δ (1)
n,p -restricted isometry of order 2k. Then, we can upper bound the expectation with respect to Y .

E W 3 0 [1I Ω L m 1 (Z)L m 2 (Z)] ≤ (1 -S 2 b 4 ) -n/2 exp b 2 W 3 2 1 + Sb 2 × Φ 2S log(p)(1 + o(1)) -2b W 3 (1 -o(1)) .
Moreover on Ω, we have 1δ

(1)

n,p ≤ W 3 / √ nS ≤ 1 + δ (1)
n,p . Since k log(p)/n goes to 0, we get

E 0 [1I Ω L m 1 (Z)L m 2 (Z)] ≤ exp x 2 c S log(p)(1 + o(1)) Φ S log(p) √ 2 -2x c + o(1)
) .

For any x < 0, we have Φ(x) ≤ e -x 2 /2 . Hence, we get Φ(x) ≤ e -x 2 -/2 for any x ∈ R. It follows that

E 0 [1I Ω L m 1 (Z)L m 2 (Z)] ≤ exp S log(p) x 2 c -(1 - √ 2x c ) 2 -+ o(1) .(5.23)
Hence, we get

E 0 [1I Ω L 2 π (Z)] ≤ E S p S{x 2 c -(1- √ 2xc) 2 -+o(1)}
where S follows a hypergeometric distribution with parameters p, k and k/p. We know from Aldous (p.173) [START_REF] Aldous | Exchangeability and Related Topics[END_REF] that S has the same distribution as the random variable E(U|B p ) where U is binomial random variable of parameters k, k/p and B p some suitable σ-algebra. By a convexity argument, we then obtain

E 0 [1I Ω L 2 π (Z)] ≤ 1 + k p p x 2 c -(1- √ 2xc) 2 -+o(1) -1 k ≤ exp k 2 p p x 2 c -(1- √ 2xc) 2 -+o(1) ≤ exp p 1-2β+x 2 c -(1- √ 2xc) 2 -+o(1) Since x c < ϕ(β), one can check that 1 -2β + x 2 c -(1 - √ 2x c ) 2 -is negative and we conclude that E 0 [1I Ω L 2 π (Z)] ≤ 1 + o(1). 2 5.5.2 Proof of Lemma 5.5
By symmetry, it is sufficient to prove that

E 0 (L m (Z)1I Ω c ) = o(1). Let us decom- pose E 0 (L m (Z)1I Ω c ) = E 0 (L m (Z)1I Ω c 2 ) + E 0 (L m (Z)1I Ω c 1 ∪Ω 2 ). Since E X 0 (L m (Z)) = 1, P X almost surely, we have E 0 (L m (Z)1I Ω c 2 ) = P X (Ω c 2 ) = o(1). Let us turn to E 0 (L m (Z)1I Ω c 1 ∪Ω 2 ).
For any 1 ≤ i ≤ p, we define the event Ω (i) by (Y,

X i / X i ) ≥ 2 log(p)(1 + δ (2) n,p ). E 0 (L m (Z)1I Ω c 1 ∪Ω 2 ) ≤ p i=1 E 0 [L m (Z)1I Ω 2 1I Ω (i) ]
The value of these expectations depends on i through the property "i ∈ m" or "i / ∈ m". Let us assume for instance that 1 ∈ m and 2 / ∈ m. Then, we get

E 0 (L m (Z)1I Ω c 1 ∪Ω 2 ) ≤ kE 0 [L m (Z)1I Ω 2 1I Ω (1) ] + pE 0 [L m (Z)1I Ω 2 1I Ω (2)
] .

(5.24)

First, we upper bound

E 0 [L m (Z)1I Ω 2 1I Ω (2) ]. Taking the expectation of L m (Z) with respect to (X i ) i∈m leads to E Y,X 2 0 [L m (Z)] = 1. Hence, we get E 0 [L m (Z)1I Ω 2 1I Ω (2) ] ≤ P 0 (Ω (2) ) ≤ p -1 e - √ log(p) = o(p -1 ) . (5.25) Let turn to E 0 [L m (Z)1I Ω 2 1I Ω (1)
]. We first take the expectation of L m (Z) conditionally to X 1 and Y :

E Y,X 1 0 [L m (Z)] = (1 -b 2 ) -n/2 exp - b 2 Y 2 2(1 -b 2 ) - b 2 X 1 2 2(1 -b 2 ) + (Y, X 1 )b 1 -b 2 .
Then, we take the expectation with respect to Y

E X 1 0 [L m (Z)1I Ω (1) ] ≤ 1 -Φ 2 log(p) 1 -b 2 (1 + δ (2) n,p ) - X 1 b √ 1 -b 2 .
Moreover, on Ω 2 we have Arguing as in the proof of Lemma 5.4, we get

X 1 ≤ √ n(1 + o(1)) E X 1 0 [L m (Z)1I Ω (1) ∪Ω 2 ] ≤ Φ log(p)(x c - √ 2 + o(1)) ≤ C exp -log(p)( √ 2 -x c -o(1)) 2 /2 for (n, p) large enough, since x c < ϕ(β) < √ 2. kE X 1 0 [L m (Z)1I Ω (1) ∪Ω 2 ] ≤ p -( √ 2-xc) 2 /2+1-β+o(1) = o(1) , (5.26)
since x c < √ 2(1- √ 1 -β) ≤ ϕ(β).
E W 3 0 [L m 1 (Z)L m 2 (Z)] = (1 -S 2 b 4 ) -n/2 exp b 2 W 3 2 1 + Sb 2 .
Taking the expectation with respect to W 3 leads to

E 0 [L m 1 (Z)L m 2 (Z)] = (1 -Sb 2 ) -n/2 ≤ exp nSb 2 2(1 -kb 2 )
As in the proof of Lemma 5.4, we upper bound the term E 0 [L 2 π (Z)] by Jensen's inequality.

E 0 [L 2 π (Z)] ≤ 1 + k p exp nb 2 2(1 -kb 2 ) -1 k ≤ exp k 2 p exp nb 2 2(1 -kb 2 ) ≤ exp p 1-2β exp {(β -1/2) log(p)} = 1 + o(1) , since b satisfies kb 2 /(1 -kb 2 ) = (2β -1)k log(p)/n. 2
6 Proofs of the upper bounds 6.1 Tests based on the statistic t 0 Recall that

t 0 = (2n) -1/2 n i=1 (Y 2 i -1).
Under H 0 , the statistics Y i = ξ i ∼ N (0, 1) are i.i.d. This implies E 0 (t 0 ) = 1, Var 0 (t 0 ) = 1. By the Central Limit Theorem, t 0 → ξ ∼ N (0, 1) as n → ∞ in P 0 -probability. This yields Theorem 4.2 (i).

Let us consider the type II errors. We need to show that, if nr 4 → ∞, then sup θ∈Θp(r) P θ (t 0 ≤ u α ) → 0. We will prove that, uniformly over θ ∈ Θ p (r),

E θ t 0 → ∞, Var θ t 0 = o((E θ t 0 ) 2 ). (6.1)
Indeed, if (6.1) is true, we derive that for n, p large enough,

P θ (t 0 ≤ u α ) = P θ (E θ t 0 -t 0 ≥ E θ t 0 -u α ) ≤ P θ (|E θ t 0 -t 0 | ≥ E θ t 0 -u α ) ≤ Var θ (t 0 ) (E θ t 0 -u α ) 2 = o(1) , (6.2)
by Chebychev's inequality. In order to check (6.1), we use the identities

E θ t 0 = E X (E X θ t 0 ), Var θ t 0 = Var X (E X θ t 0 ) + E X (Var X θ t 0 ). Under P X θ , θ ∈ Θ k (r), we have Y ∼ N n (v, I n ), where v = v(θ, X) = p j=1 θ j X j , v 2 = p j=1 θ 2 j X j 2 + 2 1<j<l≤p θ j θ l (X j , X l ).
It follows that

E X θ (t 0 ) = (2n) -1/2 v 2 , Var X θ (t 0 ) = 1 + 2n -1 v 2 .
Since E X ( X j 2 ) = n, E X ((X j , X l )) = 0, j = l, we get the first convergence in (6.1):

E θ t 0 = (2n) -1/2 E X ( v 2 ) = (n/2) 1/2 p j=1 θ 2 j = (n/2) 1/2 θ 2 ≥ (n/2) 1/2 r 2 → ∞.
Let us turn to the variance term

E X (Var X θ t 0 ) = 1 + 2n -1 E X ( v 2 ) = 1 + 2 θ 2 = o(E θ t 0 ), Var X (E X θ (t 0 )) = (2n) -1 Var X ( v 2 ).
By A2, the random variables X ij are independent in (i, j), i = 1, ..., n, j = 1, .., p.

Consequently, the random variables (X j 1 , X l 1 ) with {j 1 , l 1 } = {j 2 , l 2 } are uncorrelated. Moreover, X j 1 2 and (X j , X l ) are uncorrelated as long as (j, l) = (j 1 , j 1 ). We have

Var X X j 2 = Var X (X 2 ij )n, E X (X j , X l ) 2 = n, j = l, where Var X (X 2 ij ) ≤ E X (X 4 ij ) < ∞ by B1. Then, we get n -1 Var X v 2 = n -1 p j=1 θ 4 j Var X X j 2 + 4n -1 1≤j<l≤p θ 2 j θ 2 l E X (X j , X l ) 2 ≤ sup i [E X (X 4 i1 )] p j=1 θ 4 j + 4 θ 4 ≤ (O(1) + 4) θ 4 = o(n θ 4 ) = o (E θ t 0 ) 2 , as n θ 4 ≥ nr 4 → ∞.
Therefore we get the second relation (6.1).

Note that if nr 4 → ∞, then in the inequality (6.2), we can replace u α by a sequence T np → ∞ such that lim sup T np r -2 n -1/2 < 1, for instance by T pn = n 1/2 r 2 /2. Then, the corresponding test ψ 0 satisfies γ(ψ 0 , Θ p (r)) → 0. Theorem 4.2 follows. 2

Tests based on the statistic t 1

First observe that under H 0 , the statistic t 1 is a degenerate U-statistic of the second order, i.e., for Z s = (X (s) , Y s ), s = 1, 2, 3 one has E Z 1 K(Z 1 , Z 2 ) = 0, which yields

E 0 t 1 = 0. By Assumption A1, E 0 t 2 1 = E 0 (K 2 (Z 1 , Z 2 )) = p -1 E 0 (Y 2 1 Y 2 2 ) p j=1 p l=1 E X (X 1j X 2j X 1l X 2l ) = p -1 p j=1 E X X 2 1j X 2 2j = 1. Set G(Z 1 , Z 2 ) = E Z 3 (K(Z 1 , Z 3 )K(Z 2 , Z 3 )) , G 2 = E 0 (G 2 (Z 1 , Z 2 )), G 4 = E 0 (K 4 (Z 1 , Z 2 )),
where E Z 3 denotes the expectation over Z 3 under P 0 . In order to establish the asymptotic normality of t 1 we only need to check the two following conditions, see [START_REF] Ingster | Minimax hypothesis testing on a distribution density for ellipsoids in l p[END_REF] Lemma 3.4,

G 2 = o(1), G 4 = o(n 2 ). (6.3)
We have by Assumption A1,

G(Z 1 , Z 2 ) = p -1 E Z 3 Y 1 Y 2 Y 2 3 p j=1 p l=1 X 1j X 3j X 2l X 3l = p -1 Y 1 Y 2 p j=1 p l=1 X 1j X 2l E X (X 3j X 3l ) = p -1 Y 1 Y 2 p j=1 X 1j X 2j = p -1/2 K(Z 1 , Z 2 ).
Since E 0 (K 2 (Z 1 , Z 2 )) = 1, we get the first convergence in (6.3). Next by A2,

E 0 (K 4 (Z 1 , Z 2 )) = p -2 E 0 (Y 4 1 Y 4 2 ) p j=1 p l=1 p r=1 p s=1 E X (X 1j X 2j X 1l X 2l X 1r X 2r X 1s X 2s ) = 9p -2 p j=1 p l=1 p r=1 p s=1 H 2 jlrs , since E 0 (Y 4 1 Y 4 2 ) = E 2 0 (Y 4 1 ) = 9
, where we set

H jlrs ∆ = E X (X 1j X 1l X 1r X 1s ) =      E X (X 4 1 ), j = l = r = s, 1, j = l = r = s or j = r = l = s or j = s = r = l, 0, otherwise.
As a consequence, we get

E 0 (K 4 (Z 1 , Z 2 )) ≤ 9p -1 b 2 4 + 27 ,
where b 4 ∆ = sup i E(X 4 i1 ). By B1, the second convergence in (6.3) holds true. Thus, Theorem 4.3 (i) follows.

Let us now evaluate the type II errors under P θ . Recall that by (1.1),

Y i = ξ i + v i , v i = p j=1 θ j X ij , ξ i ∼ N (0, 1) iid. Observe that E θ Y i X ij = θ j and set K θ (Z 1 , Z 2 ) = p -1/2 p j=1 (Y 1 X 1j -θ j )(Y 2 X 2j -θ j ).
Consider the representation

K(Z 1 , Z 2 ) = K θ (Z 1 , Z 2 ) + δ(Z 1 ) + δ(Z 2 ) + h(θ) where δ(Z i ) = p -1/2 p j=1 (Y i X ij -θ j )θ j , h(θ) = p -1/2 p j=1 θ 2 j .
Observe that the kernel K θ (Z 1 , Z 2 ) is symmetric and degenerate under P θ , i.e.,

E Z 1 θ K θ (Z 1 , Z 2 ) = E Z 2 θ K θ (Z 1 , Z 2 ) = 0.
The terms K θ (Z 1 , Z 2 ), δ(Z 1 ), and δ(Z 2 ) are centered and uncorrelated under P θ . As a consequence, we derive that

E θ (K(Z 1 , Z 2 )) = p -1/2 θ 2 , (6.4) Var θ (K(Z 1 , Z 2 )) = Var θ (K θ (Z 1 , Z 2 )) + Var θ (δ(Z 1 )) + Var θ (δ(Z 2 )) . (6.5)
Let us compute the variances. Let δ ij be the Kronecker function. Using the representation

K θ (Z 1 , Z 2 ) = p -1/2 p j=1 ξ 1 X 1j + p r=1 θ r (X 1r X 1j -δ rj ) × ξ 2 X 2j + p s=1 θ s (X 2s X 2j -δ sj ) , we derive that E X θ (K θ (Z 1 , Z 2 )) = p -1/2 p j=1 p r=1 p s=1 θ r θ s (X 1r X 1j -δ rj )(X 2s X 2j -δ sj ), Denoting H rsj = (X 1r X 1j -δ rj )(X 2s X 2j -δ sj ) observe that Var X E X θ (K θ (Z 1 , Z 2 )) = p -1 p j=1 p r=1 p s=1 p l=1 p u=1 p v=1 θ r θ s θ u θ v E X (H rsj H uvl ).
Note that

E X (H rsj H uvl ) = D rujl D svjl ,
where (we omit the first index i = 1, 2 in X ij )

D rujl = E X ((X r X j -δ rj )(X u X l -δ ul )) , D svjl = E X ((X s X j -δ sj )(X v X l -δ vl )) .
Observe that

D rujl =      1, r = l = u = j or r = u = j = l, b 4 -1, r = u = j = l, 0, otherwise.
We obtain We now compute

Var X E X θ (K θ (Z 1 , Z 2 )) = p -1
E X [Var X θ (K θ (Z 1 , Z 2 ))]. Var X θ (K θ (Z 1 , Z 2 )) = p -1 1≤j,l≤p X 1j X 2j X 1l X 2l + p -1 p j=1 p l=1 p r=1 p s=1 X 1j X 1l θ r θ s (X 2r X 2j -δ jr )(X 2s X 2l -δ sl ) + p -1 p j=1 p l=1 p r=1 p s=1 X 2j X 2l θ r θ s (X 1r X 1j -δ jr )(X 1s X 1l -δ sl ) .
Let us take the expectation with respect to X. By Assumption A2, we have

E X [Var X θ (K θ (Z 1 , Z 2 ))] = 1 + 2p -1 p j=1 p r=1 p s=1 θ r θ s E X [(X 2r X 2j -δ jr )(X 2s X 2j -δ sj )] ≤ 1 + 2 p r=1 b 4 θ 2 r = 1 + O( θ 2 ) = O(1 + θ 4 ) Since Var θ (K θ (Z 1 , Z 2 )) = E X Var X θ (K θ (Z 1 , Z 2 )) + Var X E X θ (K θ (Z 1 , Z 2 )), we get Var θ (K θ (Z 1 , Z 2 )) = O(1 + θ 4 ).
(6.6)

Similarly for i = 1, 2, we compute the variance of δ(Z i ).

δ(Z i ) = p -1/2 p j=1 θ j ξ i X ij + p l=1 θ l (X ij X il -δ jl ) ,
and we have (we omit the index i = 1, 2)

E X θ (δ(Z)) = p -1/2 p j=1 p l=1 θ j θ l (X j X l -δ jl ), Var X θ (δ(Z)) = p -1 p j=1 p l=1 θ j θ l X j X l , E X Var X θ (δ(Z)) = p -1 θ 2 , Var X E X θ (δ(Z)) = p -1 p j=1 p l=1 p r=1 p s=1 θ j θ l θ r θ s D jrls ,
where D jrls was previously defined and upper bounded. This yields

Var X E X θ (δ(Z)) = p -1 (b 4 -1) p j=1 θ 4 j + 2 θ 4 = O( θ 4 /p). (6.7)
Combining (6.4), (6.5), (6.6), and (6.7) we obtain, for r 2 np -1/2 → ∞ and p = o(n 2 ),

E θ (t 1 ) = √ NE θ (K(Z 1 , Z 2 )) = √ Nh(θ) ∼ n(2p) -1/2 θ 2 ≥ n √ 2p r 2 → ∞, Var θ (t 1 ) = Var θ (K θ (Z 1 , Z 2 )) + n 3 N Var θ (δ(Z 1 )) = O(1 + θ 4 ) + O(n θ 4 /p) = o (E θ (t 1 )) 2 .
Applying Chebyshev's inequality as in the proof of Theorem 4.2 allows to conclude. 2

6.3 Higher Criticism Tests

Type I errors

The variables X 1 , ..., X p , Y are independent under P 0 and (X j , a)/ a ∼ N (0, 1) for any a ∈ IR p , a = 0 under A3. Thus we have

P 0 (y 1 < t 1 , ..., y p < t p ) = E Y (P Y 0 ((X 1 , Y )/ Y < t 1 , ..., (X p , Y )/ Y < t p ) = E Y (Φ(t 1
)....Φ(t p )) = Φ(t 1 )....Φ(t p ) = P 0 (y 1 < t 1 )...P 0 (y p < t p ).

It follows that y j = (X j , Y )/ Y ∼ N (0, 1) and y 1 , . . . , y p are i.i.d. under P 0 . As a consequence, the random variables q i are independent uniformly distributed on (0, 1) under P 0 . We denote by F p (t) the empirical distribution of (q i ) 1≤i≤p :

F p (t) = 1 p p i=1 1I q i ≤t .
Then, the normalized uniform empirical process is defined by

W p (t) = √ p F p (t) -t t(1 -t) .
Arguing as in Donoho and Jin [START_REF] Donoho | Higher criticism for detecting sparse heterogeneous mixtures[END_REF], we observe that t HC = sup t≤1/2 W p (t). It is stated in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF], Chapter 16 that

sup 0≤t≤1/2 W p (t) √ 2 log log p → P 1 , p → ∞ .
This proves the result. 2

Type II errors

We define H np = (1 + a) √ 2 log log p. Consider some β ∈ (1/2, 1) and assume that k log(p)/n → 0. It is sufficient to prove that for any δ 0 > 0 arbitrarily small the radius

r np = (ϕ(β) + δ 0 ) k log(p)/n (6.8)
satisfies β(ψ HC , Θ k (r np )) → 0 . (6.9)

For any θ ∈ Θ k , we set θ ∞ ∆ = sup i |θ i |. In order to prove the convergence (6.9), we consider a partition of Θ k (r np ):

Θ(1) k (r np ) ∆ = Θ k (r np ) ∩ θ ∈ Θ k , θ 2 ≥ 4k log(p) n Θ(2) k (r np ) ∆ = Θ k (r np ) ∩ [ Θ(1) k (r np )] c ∩ θ ∈ Θ k , θ 2 ∞ ≥ 4 log(p) n Θ(3) k (r np ) ∆ = Θ k (r np ) ∩ [ Θ(1) k (r np )] c ∩ [ Θ(2) k (r np )] c .
The sets Θ(1) k (r np ) and Θ(2) k (r np ) contain the parameters θ whose l 2 or l ∞ norms are large, while the set Θ(3) k (r np ) contains the remaining parameters.

Proposition 6.1 Consider the set of parameters Θ(4) k defined by

Θ(4) k ∆ = θ ∈ Θ k , θ 2 ∞ 1 + θ 2 ≥ 3 log(p) n .
Let us introduce the statistic t max and the corresponding test ψ max defined by

t max ∆ = (pq (1) ) -1/2 -(pq (1) )
ψ ′ max = 1I y ∞ ≥ √ 2.5 log(p) (6.11)
If ψ ′ max = 1, it follows that q (1) ≤ 2Φ(-2.5 log(p)) ≤ 2p -5/4 . Hence, we have

t max ≥ p 1/8 / √ 2 - √ 2p -1/8
. For p large enough, this implies that ψ max = 1.

Consequently, we only have to prove that β(ψ ′ max , Θ

k ) → 0. Consider θ ∈ Θ(4) k . (4)
By symmetry, we may assume that θ ∞ = |θ 1 |. We use the following decomposition

Y y 1 = θ 1 X 1 2 + (Y -θ 1 X 1 , X 1 ) .
The random variables Y 2 /(1 + θ 2 ) and X 1 2 have a χ 2 distribution with n degrees of freedom. Since Yθ 1 X 1 is independent of X 1 , the random variable (Yθ 1 X 1 , X 1 / X 1 ) is normal with mean 0 and variance 1 + i =1 θ 2 i . With probability larger than 1 -O(n -1 ∨ log -1 (p)), we obtain

Y 2 /n ≤ (1 + θ 2 )[1 + o(n -1/4 )] (1 -o(n -1/4 )) ≤ X 1 2 /n ≤ (1 + o(n -1/4 )) |(Y -θ 1 X 1 , X 1 )|/ X 1 ≤ (1 + i =1 θ 2 i ) 1/2 2 log(log(p)) .
Thus, we get

|y 1 | ≥ √ n|θ 1 | (1 + θ 2 ) 1/2 [1 -o(n -1/4) ] -O( log log(p)) , with probability larger than 1 -O(n -1 ∨ log -1 (p)). Since θ ∈ Θ(4) k , we have n|θ 1 | 2 /(1 + θ 2 ) ≥ 3 log(p)
L(u) = √ p[ŝ u /p -2Φ(-uT p )] 2Φ(-uT p ) ≤ √ p[ŝ u /p -q (ŝu) ] √ q (ŝu) ≤ t HC .
Power of ψ L . Under P θ , Y 2 /(1 + θ 2 ) has a χ 2 distribution with n degrees of freedom. For any θ ∈

Θ(3) k (r np ), we have θ 2 ≤ 4k log(p)/n = o(1). As a consequence, we have | Y 2 -n| ≤ 4k log(p) + 4 n log(n) = o(n) with probability larger than 1 -O(1/n) uniformly over all θ ∈ Θ(3) k (r np ). Consider the event Z np,1 = {| Y 2 -n| ≤ H n }, where H n = 4k log(p) + 4 n log(n) = o(n). It is sufficient to prove that sup θ∈ Θ(3) k (rnp) P θ (Z np,1 ∩ {L(u) ≤ H np }) → 0. (6.12) Consider θ ∈ Θ(3) k (r np ).
We can assume that θ k+1 = ... = θ p = 0. Then Y = k j=1 θ j X j + ξ does not depend on X k+1 , ..., X p . Arguing as for the type I error, we derive that y k+1 , ..., y p are independent standard Gaussian variables and do not depend on (y 1 , ..., y k ). We can write L(u) = L 1 (u) + L 2 (u), where

L 1 (u) = k j=1 1I {|y j |>uTp} -2Φ(-uT p ) 2pΦ(-uT p ) , L 2 (u) = p j=k+1 1I {|y j |>uTp} -2Φ(-uT p ) 2pΦ(-uT p ) .
We find

E θ (L 2 (u)) = 0, Var θ (L 2 (u)) = 2pΦ(-uT p )(1 -2Φ(-uT p )) 2pΦ(-uT p ) ≤ 1 , which yields, P θ (|L 2 (u)| > H np ) → 0 . (6.13)
In order to study the term L 1 (u), we will find a statistic L1 (u) such that

P θ [ L1 (u) < L 1 (u)] = 1 + o(1) uniformly over Θ (3)
k (r np ). For such a L1 (u), we will have

P θ [L(u) ≤ H np ] ≤ P θ [L 1 (u) ≤ 2H np ] + o(1) ≤ P θ [ L1 (u) ≤ 2H np ] + o(1). (6.14)
Construction of L1 (u). Observe that under P θ ,

y j = (ŷ j ξ + nθ j + ∆ j ) / Y , ∆ j = k l =j θ l (X j , X l ) + X j 2 -n θ j , j = 1, ..., k,
where ŷj = (X j , ξ)/ ξ .

We only need to consider

Z ∈ Z np,2 = { ξ 2 -n| < n 2/3 } since P θ (Z np,2 ) → 1. Set Z np,3 = Z np,1 ∩ Z np,2
. Thus, for δ = δ np → 0 one has

{|y j | > uT p } ∩ Z np,3 ⊃ {|n -1/2 ŷj ξ + n -1/2 ∆ j + n 1/2 θ j )| > uT p (1 + δ)} ∩ Z np,3 ⊃ {sgn(θ j )ŷ j (1 -δ) > uT p (1 + δ) -n 1/2 |θ j | + | Sj |)} ∩ Z np,3 , (6.15)
where Sj = n -1/2 ∆ j .

Lemma 6.1 For any T > 0 going to infinity and such that T = o( √ n), we have

log(P X (| Sj | > T θ )) ≤ - 1 4 T 2 (1 + o(1)) , uniformly over ∈ Θ(3) k (r np ).
Taking T = 4 log(p), we obtain

P X (| Sj | > T θ ) = o(p -1 ).
We recall that θ 2 ≤ 4k log(p)/n = o(1) since θ ∈ Θ(3) k (r np ). Hence, we get

P X max 1≤j≤k | Sj | > o( log(p)) = o(1), uniformly over θ ∈ Θ(3) k (r np ).
Combining this bound with (6.15), we obtain that there exists an event Z np,4 of probability tending to one and a sequence δ = δ np → 0 such that

{|y j | > uT p } ∩ Z np,4 ⊃ {sgn(θ j )ŷ j > uT p (1 + δ) -(1 -δ)n 1/2 |θ j |} ∩ Z np,4 . (6.16)
Observe that the random variables ŷj are independent standard normal.

Setting

ũ = u(1 + δ), ρj = (1 -δ)n 1/2 |θ j | we define L1 (u) = k j=1 1I ŷj >ũTp-ρ j -2Φ(-uT p ) 2pΦ(-uT p ) .
By (6.16), L1 (u) satisfies P θ [ L1 (u) ≤ L 1 (u)] = 1o(1) uniformly over Θ(3) k (r np ). In view of (6.14), in order to complete the proof it suffices to show that

P θ [ L1 (u) ≤ 2H np ] = o(1) uniformly over Θ(3) k (r np ). ( 6
.17)

Control of P θ [ L1 (u) ≤ 2H np ].
In order to evaluate this probability, recall that ŷj ∼ N (0, 1) i.i.d. under P θ . Thus,

E θ ( L1 (u)) = k j=1 Φ(-ũT p + ρj ) -2Φ(-uT p ) 2pΦ(-uT p ) , Var θ ( L1 (u)) ≤ k j=1 Φ(-ũT p + ρj ) 2pΦ(-uT p ) .
By Chebyshev's inequality, we get

P θ ( L1 (u) ≤ 2H np ) = P θ (E θ ( L1 (u)) -L1 (u) ≥ E θ ( L1 (u)) -2H np ) ≤ Var θ ( L1 (u)) (E θ ( L1 (u)) -2H np ) 2 .
Lemma 6.2 There exists η > 0 such that, for n, p large enough,

inf θ∈ Θ(3) k (rnp) k j=1 Φ(-ũT p + ρj ) 2pΦ(-uT p ) ∼ inf θ∈ Θ(3) k (rnp) E θ ( L1 (u)) > p η . (6.18)
In the sequel, we denote by A p a log-sequence, i.e., a sequence such that

A p = (log(p)) cp , |c p | = O(1) as p → ∞. Since u ∈ [0, √ 2
( L1 (u)) = O A p E θ ( L1 (u)) .
Since H np = o(p η ), this implies (6.17) and then (6.12). 2 since for t j = ρj one has

k j=1 t 2 j = (1 -δ) 2 n k j=1 θ 2 j ≥ (1 -δ) 2 nr 2 np = kt 2 0 .
By the choice of u, and v, the relations (7.4) hold true for p large enough (see Remark 7.1). Applying Lemmas 7. In order to obtain (6.18), we have to check that there exists η > 0 such that, for n, p large enough, Let us now consider β ∈ (3/4, 1]. Recalling that ϕ(β) = √ 2(1 -√ 1β) and (6.10), we see that for δ = δ np = 0(1) and δ 0 ∈ (0, √ 2 -2β), one can find η = η(β, δ 0 ) > 0 such that The relation (6.18) follows. 2

G ∆ = 1 2 -β - (ũ -v) 2 + 2 + u 2 4 ≥ η.
G = 1 2 -β - √ 2 - √ 2 1 - √ 1 -β -δ 0 2 2 + 1 2 + o(1) = 1 -β - 1 -β -δ 0 / √ 2 2 + o(1)
6.4 Proof of Proposition 4.6

Under H 0 , the distributions of the variables (y i ) i=1,...,p do not depend on σ 2 . As a consequence, E 0,σ (ψ HC ) = E 0,1 . This last quantity has been shown to converge to 0 in Theorem 4.4. Hence, we get α un (ψ HC ) = o(1).

Let us turn to the type II error probability. We consider the model Y i = p j=1 θ j X ij + ξ i where Var(ξ i ) = σ 2 . Dividing this equation by σ, we obtain the model:

Y ′ i = p j=1 (θ j /σ)X ij + ξ ′ i ,
where Var(ξ ′ i ) = 1. The statistic t HC is exactly the same for the data Z = (Y, X) and Z ′ = (Y ′ , X). Consequently, we obtain E θσ,σ (1ψ HC ) = E θ,1 (1ψ HC ). It remains to use the bound on E θ,1 (1ψ HC ) from Theorem 4.4. 2 7 Appendix: Technical results

Thresholds

Take the thresholds T = T j satisfying T j = a j 2 + log(h -1 ) a j .

Define a j = x j log(p), τ j = T j / log(p), and h = p -β . Then, we have τ j = x j /2 + β/x j .

If for some δ 0 > 0, x j + δ 0 < ϕ 2 (β)

∆ = √ 2(1 - √ 1 -β) ≤ ϕ(β)
, then there exists δ 1 > 0 such that τ j > √ 2 + δ 1 . For such a x j , we derive that pT r j Φ(-T j ) = o(1), ∀ r > 0 .

(7.1)

In particular, if x j = o(1), then τ j → ∞ and (7.1) holds.

For any δ > 0, we have Φ(-T j ) ≍ hΦ(-T j + a j ) for τ j > x j + δ .

This holds if x j < ϕ 2 (β) ≤ √ 2.

7.2 Norms X j and scalar products (X j , X l )

Clearly, E( X j 2 ) = n, E(X j , X l ) = 0 , Var(X j , X l ) = n.

By Assumption B1, there exists D > 0 such that sup j =l Var(X j , X l ) ≤ nD and sup j Var( X j 2 ) ≤ nD.

Lemma 7.1 Let U j be a random variable distributed as X ij .

(1) Assume that there exists h 0 > 0 such that sup 1≤j≤l≤p E(e hU j U l ) < ∞ for any |h| < h 0 . Then, for any sequence t = t n such that t = o( √ n) and t √ n → ∞,

P (| X j 2 -n| > t √ n) ≤ exp[-t 2 /(2D)(1 + o(1))],
and

P (|(X j , X l )|| > t √ n) ≤ exp[-t 2 /(2D)(1 + o(1))],
(2) Assume that E(|X| m ) < ∞, for some m > 2. Then there exists C m < ∞ such that

P (| X j 2 -n| > t √ n) ≤ C m t -m/2 , P (|(X j , X l )| > t √ n) ≤ C m t -m .
Proof follows from the standard arguments based on the moment inequalities and exponential inequalities. If EZ = 0, Var(Z) = 1, E(e h 0 Z ) < ∞, then log(Ee hZ ) = (3) Under assumptions [START_REF] Aldous | Exchangeability and Related Topics[END_REF] or [START_REF] Arias-Castro | Global Testing and Sparse Alternatives: ANOVA, Multiple Comparisons and the Higher Criticism[END_REF] uniformly in 1 ≤ j < l ≤ p in P X -probability, one has a j ∼ a = b √ n, x j ∼ x, i.e., for any δ > 0,

P X ( max 1≤j≤p |(a j /b √ n) -1| > δ) → 0, P X ( max 1≤j≤p
|(x j /x) -1| > δ) → 0.

Expansion of Φ(t)

Let Φ(t) be the standard Gaussian cdf and φ(t) be the standard Gaussian pdf. Let t 1 ≍ t 2 → ∞, rt 1 = o(1). Then P (X > t 1 , Y > t 2 ) = Φ(-t 1 )Φ(-t 2 ) 1 + O(r 2 ) + rφ(t 1 )φ(t 2 ).

Proof. Observe that the conditional distribution L(Y |X = x) is Gaussian N (m(x), σ 2 (x)) with m(x) = rx, σ 2 (x) = 1r 2 . Therefore (f (t)λt 2 ) = f (t 0 )λt 2 0 .

P (X > t 1 , Y > t 2 ) = ∞ t 1 P (Y > t 2 |X = x)dΦ(x) = ∞ t 1 Φ -t 2 + rx √ 1 -
Then F k (t 0 ) = kf (t 0 ).

(4. 10 ) 4 . 5

 1045 Theorem Fix some β > 1/2 and assume A3. If Condition (4.10) holds and if k log

Proposition 4 . 6

 46 Assume A3 (X ij are i.i.d. standard Gaussian). (i) Type I error satisfies α un (ψ HC ) = o(1).

2 5. 3 1 5. 3 . 1

 23131 probability. This yields indistinguishability in the problem. Proof of Proposition 5.Replacing the measure π Z by πZ

. 8 ) 5 . 3 . 3

 8533 Expectation over πZ and over E X 0 Let us define the variables η k in {1, -1}. The expectations over πZ are of the form

. 16 )

 16 CASE 2: x > 0. We have under the event X n,p , b|m jk (η)| = o(b √ n/ log(p)) = o(1) and Tjk b = O(log(p)/ √ n). Hence, Tjk b|m jk (η)| = o(1). Applying Lemma 7.2, we bound the first term in (5.15)

1≤k<s≤moo ( 1 +

 1 (|r ks |/(ph)) + 1≤k<s≤m o r 2 ks /(ph) = 1≤k<s≤m |r ks | + r 2 ks )/(ph) .

2 5. 5 . 3

 253 Combining (5.24),(5.25), and (5.26) completes the proof. Proof ofLemma 5.6

θ= (b 4 - 2 j

 42 r θ s θ u θ v D rujl D svjl ) 2 ] = O( θ 4 ).

  ũT p + ρj ) = kΦ(-ũT p + t 0 ). We recall that A p denotes any log-sequence. Since Φ(-tT p ) = A p p -t 2 /2 for t > 0, we haveinf θ∈ Θk (rnp) E θ ( L1 (u)) = k (Φ(-ũT p + t 0 ) -2Φ(-uT p )) 2pΦ(-uT p ) ∼ kΦ(-ũT p + t 0 ) 2pΦ(-uT p ) = kΦ(-(ũv)T p ) 2pΦ(-uT p ) = A p p 1/2-β-(ũ-v) 2 + /2+u 2 /4 .

Let β ∈ ( 1 / 2 , 3 / 4 ] 1 )

 12341 . Recalling that ϕ 2 (β) = 2β -1 > 0 and (6.10) we see, that for δ = δ np = o(1) and δ 0 ∈ (0, ϕ(β)), one can find η = η(β, δ 0 ) > 0 such that ≥ η + o(1).

= 2 -2β δ 0 - δ 2 0 2 + o( 1 )

 2221 ≥ η + o(1).

h 2 / 2 ( 1

 221 + o(1)) as h → 0. Hence, we take h = t/ √ n = o(1) for the study of the exponential moments of S n = n i=1 Z i . Corollary 7.1 (1) Let log(p) = o(n) and the assumptions Lemma 7.1 (1) hold true. Then, for any B > 2, one has P X ( max 1≤j≤p | X j 2 -n| > BDn log(p) ) = o(1), P X ( max 1≤j<l≤p |(X j , X l )| > 2BDn log(p) ) = o(1).

( 2 )

 2 Let p = o(n m/4 ) and the assumptions Lemma 7.1 (2) hold true. Then, for any sequence v n going to infinity, one hasP X ( max 1≤j≤p | X j 2 -n| > √ np 2/m v n ) = o(1), P X ( max 1≤j<l≤p |(X j , X l )| > √ np 2/m v n ) = o(1).

Lemma 7 . 2

 72 Let δ → 0, tδ = O(1). ThenΦ(t + δ) = Φ(t) + δφ(t) + O δ 2 (|t| + 1)φ(t) .Proof follows from the Taylor expansion and the properties of φ(t). 2Observe that for any b ∈ IR there exists C = C(b) > 0 such that (|t|+1)φ(-t) ≤ C(b)Φ(-t) as t ≤ b. It follows from Lemma 7.2 that as δ → 0, tδ = O(1), t ≤ B for some B ∈ IR, then Φ(-t + δ) = Φ(-t)(1 + O(δ 2 )) + δφ(t).

7. 4

 4 Tails of correlated vectors Lemma 7.3 Let (X, Y ) be the Gaussian random two-dimensional vector, EX = EY = 0, Var(X) = Var(Y ) = 1, Cov(X, Y ) = r.

  t 1 >uα .

	Theorem 4.3 Assume A2 and B1. For all α ∈ (0, 1) we have: (i) Type I error satisfies: α(ψ 1 α ) = α + o(1). (ii) Type II errors. Assume that p = o(n 2 ) and consider a radius r np such that nr 2 np / √ p → ∞. Then, β(ψ 1 α , Θ p (r np )) → 0.
	Remark 4.2 Combining the tests ψ 0 α/2 and ψ 1 α/2 we obtain the test ψ * α =
	max(ψ 0 α/2 , ψ 1 α/2 ) of asymptotic level not more than α. Moreover, it achieves
	β(ψ 1 α , Θ p (r np )) → 0 for any radius r np satisfying r 2 np ≫ √ p n ∧ 1 √ n	.

  1/2 ≤ t HC , ψ max ∆ = 1I tmax>Hnp . Moreover, we have L(u) ≤ t HC , for p large enough. It follows directly from the definition (4.7) that t max ≤ t HC . Consider the test ψ

	We have β(ψ max ,	Θ(4) k ) → 0.
	It follows that β(ψ HC ,	Θ(4) k ) → 0. Observe that
			Θ(1) k (r np ) ⊂ θ ∈ Θ k ,	θ 2 1 + θ 2 ≥	4k log(p)/n 1 + 4k log(p)/n	.
	Since k θ 2 ∞ ≥ θ 2 and since k log(p)/n converges to 0, it follows that Θ(1) k (r np ) ⊂ Θ(4) k for n large enough. Thus, we get β(ψ HC , Θ(1) k (r np )) → 0.
	Let us turn to	Θ(2) k (r np ). For any θ ∈	Θ(2) k (r np ), we have
						θ 2 ∞ 1 + θ 2 ≥	4 log(p)/n 1 + 4k log(p)/n	.
	This quantity is larger than 3 log(p)/n for n large enough.	We get
	β(ψ HC ,	Θ(2) k (r np )) → 0.
	Proposition 6.2 Let us set T p = log(p) and u > 0 such that
						u =	2ϕ(β), β ∈ (1/2, 3/4] , √ 2, β ∈ (3/4, 1) .	(6.10)
	We consider the statistic L(u) and the corresponding test ψ L defined by
		L(u)	∆ =	p j=1	1I |y j |>uTp -2Φ(-uT p ) 2pΦ(-uT p )	,	ψ L = 1I L(u)≥Hnp .
	Then, β(ψ L ,	Θ(3)
	It follows from Proposition 6.2 that β(ψ HC , completes the proof. 2	Θ(3) k (r np )) → 0 converges to 0, which
	6.3.3 Proof of Proposition 6.1

k (r np )) → 0. ′ max defined by

  and the test ψ ′ max rejects with probability going to one. It follows that β(ψ

′ max , Θ(4) k ) → 0. 2 6.3.4 Proof of Proposition 6.2 Connection between t HC and L(u). Set ŝu ∆ = p i=1 1I |y j |>uTp . Observe that q (ŝu) ≤ P (|N (0, 1)| > uT p ) ≤ 1/2 for p large enough. If follows that

  ], we have pΦ(-uT p ) ≥ A p . Combining this bound with Lemma 6.2 yields Var θ

  r 2 dΦ(x). ≤ Φ(-h) = o r 2 Φ(-t 1 )Φ(-t 2 ) .It is sufficient to study the integral over the interval∆ = [t 1 , h]. For x ∈ ∆, we have -t 2 + rx √ 1r 2 = -t 2 + δ(x), δ(x) = rx + O(r 2 t 2 + |r 3 x|)) = O(1).

	Setting h = |r| -1 , observe that
	∞ dΦ(x) Applying Lemma 7.2, we have h Φ -t 2 + rx √ 1 -r 2
	k		k
	j=1	f (t j ) subject to	j=1	t 2 j ≥ kt 2 0 , t j ∈ [0, R].	(7.3)
	Lemma 7.4 Assume that there exists λ > 0 such that
	inf t∈[0,R]

∆ Φ -t 2 + rx √ 1r 2 dΦ(x) = Φ(-t 2 ) (Φ(-t 1 ) -Φ(-h)) 1 + O(r 2 ) + rφ(t 2 ) ∆ xdΦ(x) = Φ(-t 1 )Φ(-t 2 ) 1 + O(r 2 ) + rφ(t 1 )φ(t 2 ), since ∆ xdΦ(x) = φ(t 1 )φ(h) = φ(t 1 ) + o(r 2 Φ(-t 1 )

). 2

7.5 A minimization problem

Let f (t) be a function defined on the interval t ∈ [0, R]. Consider the minimization problem

F k (t 0 ) = inf

Let us bound the deviations of Sj by computing the exponential moments of ∆ j . For any h such that h 2 θ 2 ≤ 1/4, we have

. Using the Taylor expansion of the logarithm

we get

as h 2 θ 2 = o(1). Take some T > 0. Applying a standard technique based on Markov's inequality yields

We get from (6.19) that

Recall that we consider r np = (ϕ(β) + δ 0 ) k log(p)/n with arbitrarily small δ 0 > 0 (see (6.8)). Recalling that T p = log(p), we apply the results of Section 7.5 for δ = δ np > 0, δ np = o(1), and

Proof. We have, for any (t 1 , ..., t k ) such that

We apply Lemma 7.4 to the function f (x) = Φ(-T + x). Let φ(x) = Φ ′ (x) stand for the standard Gaussian pdf.

Lemma 7.5 Let f (t) = Φ(-T + t). Suppose

.4)

Take λ = φ(-T + t 0 )/2t 0 . Then the assumptions of Lemma 7.4 are fulfilled, i.e.,

Proof. Denote g(t) = Φ(-T + t)λt 2 . By the choice of λ we have g ′ (t 0 ) = 0. Let us consider the second derivative,

Observe that the function -xφ(x) is positive for x < 0, increases for x ∈ (-∞, -1) and decreases for x ∈ (-1, 1); lim x→-∞ φ(x) = 0 = 0φ(0),

Consequently, there exist two points t 1 , t 2 such that t 1 < t 0 < t 2 < T , g ′′ (t 1 ) = g ′′ (t 2 ) = 0, g ′′ (t) < 0 as t < t 1 and t > t 2 .

The function g(t) is therefore convex on [t 1 , t 2 ], concave on (-∞, t 1 ] and on [t 2 , ∞), and t 0 is the point of a local minimum of g(t). By the concavity, this yields that the global minimum of g(t) at t ∈ [0, R] is achieved either at t = t 0 or at the ends of the interval [0, R]. Therefore we only need to show that g(0) > g(t 0 ) and g(R) > g(t 0 ).

In order to verify the first inequality, observe that g(0) > 0. Recalling the well known inequality: Φ(-y) < 1 y φ(-y), ∀y > 0 , we get

The second inequality follows from the relation

in view of the assumption on R. 2

Remark 7.1 Observe that if 0 < v < u < b and T = uT p , t 0 = vT p , R = bT p , where T p is large enough, then assumptions (7.4) hold.