Nicolas Verzelen

Fanny Villers

Goodness-of-fit Tests for high-dimensional Gaussian linear models

Keywords: Linear regression, Gaussian graphical models, multiple testing, adaptive testing, minimax hypothesis testing, minimax separation rate, ellipsoid, goodness-of-fit

Let (Y, (X i ) 1≤i≤p ) be a real zero mean Gaussian vector and V be a subset of {1, . . . , p}. Suppose we are given n i.i.d. replications of this vector. We propose a new test for testing that Y is independent of (X i ) i∈{1,...p}\V conditionally to (X i ) i∈V against the general alternative that it is not. This procedure does not depend on any prior information on the covariance of X or the variance of Y and applies in a high-dimensional setting. It straightforwardly extends to test the neighbourhood of a Gaussian graphical model. The procedure is based on a model of Gaussian regression with random Gaussian covariates. We give non asymptotic properties of the test and we prove that it is rate optimal (up to a possible log(n) factor) over various classes of alternatives under some additional assumptions. Besides, it allows us to derive non asymptotic minimax rates of testing in this random design setting. Finally, we carry out a simulation study in order to evaluate the performance of our procedure.

Tests d'hypothèses linéaires pour des modèles de régression gaussienne en grande dimension

Résumé : On considére (Y, (X i ) i∈I ) un vecteur gaussien de moyenne nulle et V un sous-ensemble de I. Supposons que l'on observe n réplications indépendantes du vecteur (Y, X). Dans ce rapport, nous proposons une procédure pour tester l'hypothèse Y est indépendant de (X i ) i∈I\V conditionellement à (X i ) i∈V . Ce test ne nécessite aucune connaissance sur la matrice de covariance de X ou la variance de Y et peut s'appliquer dans un contexte de grande dimension. De plus, on peut facilement en déduire un test de voisinage de modèle graphique gaussien. Nous calculons la puissance du test d'un point de vue non asymptotique et prouvons qu'il atteint la vitesse optimale de séparation (à un facteur log n prés) pour différentes classes d'alternatives. Nous en déduisons ainsi des vitesse minimax de séparation d'hypothèses pour ce modèle de régression. Enfin, nous évaluons la performance de notre procédure sur des données simulées.

Mots-clés : Régression linéaire, modèles graphiques gaussiens, test multiple, test adaptatif, test minimax, vitesse de séparation minimax, ellipsoïde, test d'adéquation

Introduction

We consider the following regression model

Y = p i=1 θ i X i + ǫ ( 1
)
where θ is an unknown vector of R p . In the sequel, we note I := {1, . . . , p}. The vector X := (X i ) 1≤i≤p follows a real zero mean Gaussian distribution with non singular covariance matrix Σ and ǫ is a real zero mean Gaussian random variable independent of X. Straightforwardly, the variance of ǫ corresponds to the conditional variance of Y given X, var(Y |X).

The variable selection problem for this model in a high-dimensional setting has recently attracted a lot of attention. A large number of papers are now devoted to the design of new algorithms and estimators which are computationally feasible and are proven to converge; see for instance the works of [START_REF] Meinshausen | High-dimensional graphs and variable selection with the Lasso[END_REF], [START_REF] Candès | The dantzig selector: statistical estimation when p is much larger than n[END_REF], [START_REF] Zhao | On model selection consistency of Lasso[END_REF], [START_REF] Zou | Regularization and variable selection via the Elastic Net[END_REF], [START_REF] Bühlmann | Variable selection for high-dimensional models: partial faithful distributions, strong assocations and the PC-algorithm[END_REF], or Zhao and Huang Zhang and Huang (2008). A common drawback of the previously mentioned estimation procedures is that they require restrictive conditions on the covariance matrix Σ in order to behave well. Our issue is the natural testing counterpart of this variable selection problem: we aim at defining a computationally feasible testing procedure that achieves an optimal rate for any covariance matrix Σ.

Presentation of the main results

We are given n i.i.d. replications of the vector (Y, X). Let us respectively note Y and X i the vectors of the n observations of Y and X i for any i ∈ I. Let V be a subset of I, then X V refers to the set {X i , i ∈ V } and θ V stands for the sequence (θ i ) i∈V . We first propose a collection of testing procedures T α of the null hypothesis "θ I\V = 0" against the general alternative "θ I\V = 0". These procedures are based on the ideas of [START_REF] Baraud | Adaptative tests of linear hypotheses by model selection[END_REF] in a random design. Their definition are very flexible as they require no prior knowledge of the covariance of X, the variance of ǫ, nor the variance of Y . Note that the property "θ I\V = 0" is equivalent to "Y is independent of X I\V conditionally to X V ". Hence, it also permits to test conditional independences and applies for testing the graph of Gaussian graphical model (see below). Contrary to most approaches in this setting (e.g. Drton and Pearlman Drton and Perlman (2007)), we are able to consider the difficult case of tests in a high-dimensional setting: the number of covariates p is possibly much larger than the number of observations n. Such situations arise in many statistical applications like in genomics or biomedical imaging. To our knowledge, the only testing procedures (e.g. [START_REF] Schäfer | An empirical bayes approach to inferring large-scale gene association network[END_REF]) that could handle high-dimensional alternatives lack of theoretical justifications. In this paper, we exhibit some tests T α that are both computationally amenable and optimal in the minimax sense.

From a theoretical perspective, we are able to control the Family Wise Error Rate (FWER) of our testing procedures T α . Besides, we derive a general non asymptotic upper bound for their power. Contrary to the various rates of convergence obtained in the estimation setting (e.g. [START_REF] Meinshausen | High-dimensional graphs and variable selection with the Lasso[END_REF] or [START_REF] Candès | The dantzig selector: statistical estimation when p is much larger than n[END_REF]), our upper bound holds for any covariance matrix Σ. Then, we derive from it non-asymptotic minimax rates of testing in the Gaussian random design framework. If the minimax rates are known for a long time in the fixed design Gaussian regression framework (e.g. [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF]), they were unknown in our setting. For instance, if at most k components of θ are non-zero and if k is much smaller than p, we prove that the minimax rates of testing is of order k log(p) n when the covariates X i are independent. If the covariates are dependent, we derive faster minimax rates. To our knowledge, these are the first results for testing or estimation issues that illustrate minimax rates for dependent covariates. Afterwards, we show analogous results when k is large, or when the vector θ belongs to some ellipsoid or some collection of ellipsoids. For any of these alternatives, we exhibit some procedure T α that achieves the optimal rate (at a possible log(n) factor). Finally, we illustrate the performance of the procedure on simulated examples.

Application to Gaussian Graphical Models (GGM)

Our work was originally motivated by the following question: let (Z j ) j∈J be a random vector which follows a zero mean Gaussian distribution whose covariance matrix Σ ′ is non singular. We observe n i.i.d. replications of this vector Z and we are given a graph G = (Γ, E) where Γ = {1, . . . |J |} and E is a set of edges in Γ × Γ. How can we test that Z is an undirected Gaussian graphical model (GGM) with respect to the graph G?

The random vector Z is a GGM with respect to the graph G = (Γ, E) if for any couple (i, j) which is not contained in the edge set E, Z i and Z j are independent, given the remaining variables. See Lauritzen [START_REF] Lauritzen | Graphical Models[END_REF] for definitions and main properties of GGM. Interest in these models has grown as they allow the description of dependence structure in high-dimensional data. As such, they are widely used in spatial statistics [START_REF] Cressie | Statistics for Spatial Data[END_REF][START_REF] Rue | Gaussian Markov Random Fields: Theory and Applications[END_REF] or probabilistic expert systems [START_REF] Cowell | Probabilistic Networks and Expert Systems[END_REF]. More recently, they have been applied to the analysis of microarray data. The challenge is to infer the network regulating the expression of the genes using only a small sample of data, see for instance [START_REF] Schäfer | An empirical bayes approach to inferring large-scale gene association network[END_REF], [START_REF] Kishino | Correspondence analysis of genes and tissue types and finding genetic links from microarray data[END_REF], or Wille et al. [START_REF] Wille | Sparse graphical Gaussian modelling of the isoprenoid gene network in arabidopsis thaliana[END_REF]. This issue has motivated the research for new estimation procedures to handle GGM in a high-dimensional setting.

It is beyond the scope of this paper to give an exhaustive review of these. Many of these graph estimation methods are based on multiple testing procedures, see for instance [START_REF] Schäfer | An empirical bayes approach to inferring large-scale gene association network[END_REF] or Wille and Bühlmann [START_REF] Wille | Low-order conditional independence graphs for inferring genetic networks[END_REF]. Other methods are based on variable selection for high-dimensional data we previously mentioned. For instance, [START_REF] Meinshausen | High-dimensional graphs and variable selection with the Lasso[END_REF] proposed a computationally feasible model selection algorithm using Lasso penalization. [START_REF] Huang | Covariance matrix selection and estimation via penalised normal likehood[END_REF] and Yuan and Lin [START_REF] Yuan | Model selection and estimation in the Gaussian graphical model[END_REF] extend this method to infer directly the inverse covariance matrix Σ ′-1 by minimizing the log-likehood penalized by the l 1 norm.

While the issue of graph and covariance estimation is extensively studied, few theoretical results are proved for the problem of hypothesis testing of GGM in a high-dimensional setting. We believe that this issue is significant for two reasons: first, when considering a gene regulation network, the biologists often have a previous knowledge of the graph and may want to test if the microarray data match with their model. Second, when applying an estimation method in a high-dimensional setting, it could be useful to test the estimated graph as some of these methods reveal too conservative.

Admittedly, some of the previously mentioned estimation methods are based on multiple testing. However, as they are constructed for an estimation purpose, most of them do not take into account some previous knowledge about the graph. This is for instance the case for the approaches of Drton and Perlman [START_REF] Drton | Mutiple testing and error control in Gaussian graphical model selection[END_REF] and [START_REF] Schäfer | An empirical bayes approach to inferring large-scale gene association network[END_REF].

INRIA

Some of the other existing procedures cannot be applied in a high-dimensional setting (|J | ≥ n). Finally, most of them lack theoretical justification in a non asymptotic way.

In a subsequent paper [START_REF] Verzelen | Tests for Gaussian graphical models[END_REF] we define a test of graph based on the present work. It benefits the ability of handling high dimensional GGM and has minimax properties. Besides we show numerical evidence of its efficiency; see [START_REF] Verzelen | Tests for Gaussian graphical models[END_REF] for more details. In this article, we shall only present the idea underlying our approach.

For any j ∈ J , we note N (j) the set of neighbours of j in the graph G. Testing that Z is a GGM with respect to G is equivalent to testing that the random variable Z j conditionally to (Z l ) l∈N (j) is independent of (Z l ) l∈J \(N (j)∪{j}) for any j ∈ J . As Z follows a Gaussian distribution, the distribution of Z j conditionally to the other variables decomposes as follows:

Z j = k∈J \{j} θ k Z k + ǫ j ,
where ǫ j is normal and independent of (Z k ) k∈J \{j} . Then, the statement of conditional independency is equivalent to θ J \{j}∪N (j) = 0. This approach based on conditional regression is also used for estimation by [START_REF] Meinshausen | High-dimensional graphs and variable selection with the Lasso[END_REF].

Organization of the Paper

In Section 2, we present the approach of our procedure and connect it with the fixed design framework. Besides, we define the notion of minimax rates of testing in this setting and gather the main notations. We define the testing procedures T α in Section 3 and we non asymptotically characterise the set of vectors θ over which the test T α is powerful. In Section 4 and 5, we apply our procedure to define tests and study their optimality for two different classes of alternatives. More precisely, in Section 4 we test θ = 0 against the class of θ whose components equal 0, except at most k of them (k is supposed small). We define a test which under mild conditions achieves the minimax rate of testing. When the covariates are independent, it is interesting to note that the minimax rates exhibits the same ranges in our statistical model [START_REF] Wille | Sparse graphical Gaussian modelling of the isoprenoid gene network in arabidopsis thaliana[END_REF] and in fixed design regression model (2). In Section 5, we define two procedures that achieve the simultaneous minimax rates of testing over large classes of ellipsoids (to sometimes the price of a log(p) factor). Besides, we show that the problem of adaptation over classes of ellipsoids is impossible without a loss in efficiency. This was previously pointed out in [START_REF] Spokoiny | Adaptative hypothesis testing using wavelets[END_REF] in fixed design regression framework. The simulation studies are presented in Section 6. Finally, Sections 7, 8 and Appendix contain the proofs.

Description of the approach 2.1 Connection with tests in fixed design regression

Our work is directly inspired by the testing procedure of [START_REF] Baraud | Adaptative tests of linear hypotheses by model selection[END_REF] in fixed design regression framework. Contrary to model [START_REF] Wille | Sparse graphical Gaussian modelling of the isoprenoid gene network in arabidopsis thaliana[END_REF], the problem of hypothesis testing in fixed design regression has been extensively studied. This is why we will use the results in this framework as a benchmark for the theoretical bounds in our model [START_REF] Wille | Sparse graphical Gaussian modelling of the isoprenoid gene network in arabidopsis thaliana[END_REF]. Let us define this second regression model:

Y i = f i + σǫ i , i ∈ {1, . . . , N }, ( 2
)
where f is an unknown vector of R N , σ some unknown positive number, and the ǫ i 's a sequence of i.i.d. standard Gaussian random variables. The problem at hand is testing that f belongs to a linear subspace of R N against the alternative that it does not. We refer to [START_REF] Baraud | Adaptative tests of linear hypotheses by model selection[END_REF] for a short review of non parametric tests in this framework. Besides, we are interested in the performance of the procedures from a minimax perspective. To our knowledge, there has been no results in model [START_REF] Wille | Sparse graphical Gaussian modelling of the isoprenoid gene network in arabidopsis thaliana[END_REF]. However, there are numerous papers on this issue in the fixed design regression model. First, we refer to the seminal work of Ingster (Ingster, 1993a,b,c) who gives asymptotic minimax rates over non parametric alternatives. Our work is closely related to the results of [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF] where he gives non asymptotic minimax rates of testing over ellipsoids or sparse signals.

Throughout the paper, we highlight the link between the minimax rates in fixed and in random design.

Principle of our testing procedure

Let us briefly describe the idea underlying our testing procedure. A formal definition will follow in Section 3.1.Let m be a subset of I \ V . We respectively define S V and S V ∪m as the linear subspaces of R p such that θ I\V = 0, respectively θ I\(V ∪m) = 0. We note d and D m for the cardinalities of V and m and N m refers to

N m = n -d -D m . If N m > 0, we define the Fisher statistic φ m by φ m (Y, X) := N m Π V ∪m Y -Π V Y 2 n D m Y -Π V ∪m Y 2 n , (3)
where Π V refers to the orthogonal projection onto the space generated by the vectors (X i ) i∈V and . n is the canonical norm in R n . We define the test statistic φ m,α (Y, X) as

φ m,α (Y, X) = φ m (Y, X) -F -1 Dm,Nm (α) , (4)
where FDm,Nm (u) denotes the probability for a Fisher variable with D and N degrees of freedom to be larger than u. Let us consider a finite collection M of non empty subsets of I \ V such that for each m ∈ M, N m > 0. Our testing procedure consists of doing a Fisher test for each m ∈ M.

We define {α m , m ∈ M} a suitable collection of numbers in ]0, 1[ (which possibly depends on X).

For each m ∈ M, we do the Fisher test φ m of level α m of:

H 0 : θ ∈ S V against the alternative H 1,m : θ ∈ S V ∪m \ S V
and we decide to reject the null hypothesis if one of those Fisher tests does.

The main advantage of our procedure is that it is very flexible in the choices of the model m ∈ M and in the choices of the weights {α m }. Consequently, if we choose a suitable collection M, the test is powerful over a large class of alternatives as shown in Sections 3.3, 4, and 5.

Finally, let us mention that our procedure easily extends to the case where the expectation of the random vector (Y, X) is unknown. Let X and Y denote the projections of X and Y onto the unit vector 1. Then, one only has to apply the procedure to (Y -Y, X -X) and to replace d by d + 1. The properties of the test remain unchanged and one can adapt all the proofs to the price of more technicalities.

INRIA

Minimax rates of testing

In order to examine the quality of our tests, we will compare their performance with the minimax rates of testing. That is why we now define precisely what we mean by the (α, δ)-minimax rate of testing over a set Θ. We endow R p with the Euclidean norm

θ 2 := θ t Σθ = var p i=1 θ i X i .
(5)

As ǫ and X are independent, we derive from the definition of . 2 that var(Y ) = θ 2 +var(Y |X). Let us remark that var(Y |X) does not depend on X. If we have θ vary, either the quantity var(Y ) or var(Y |X) has to vary. In the sequel, we suppose that var(Y ) is fixed. We briefly justify this choice in Section 4.2. Consequently, if θ 2 is increasing, then var(Y |X) has to decrease so that the sum remains constant. Let α be a number in ]0; 1[ and let δ be a number in ]0; 1 -α[ (typically small). For a given vector θ, matrix Σ and var(Y ), we denote P θ the joint distribution of (Y, X). For the sake of simplicity, we do not emphasize the dependence of P θ on var(Y ) or Σ. Let ψ α be a test of level α of the hypothesis "θ = 0" against the hypothesis "θ ∈ Θ \ 0". In our framework, it is natural to measure the performance of ψ α using the quantity ρ (ψ α , Θ, δ, var(Y ), Σ) defined by:

ρ (ψ α , Θ, δ, var(Y ), Σ) := inf ρ > 0, inf P θ (ψ α = 1), θ ∈ Θ and θ 2 var(Y ) -θ 2 ≥ ρ 2 ≥ 1 -δ ,
where the quantity

r s/n (θ) := θ 2 var(Y ) -θ 2 (6)
appears naturally as it corresponds to the ratio θ 2 /var(Y |X) which is the quantity of information brought by X (i.e. the signal) over the conditional variance of Y (i.e. the noise). We aim at describing the quantity inf ψα ρ (ψ α , Θ, δ, var(Y ), Σ) := ρ (Θ, α, δ, var(Y ), Σ) ,

where the infimum is taken over all the level-α tests ψ α . We call this quantity the (α, δ)-minimax rate of testing over Θ.

A dual notion of this ρ function is the function β Σ . For any Θ ⊂ R p and α ∈]0, 1[, we denote β Σ (Θ) the quantity

β Σ (Θ) := inf ψα sup θ∈Θ P θ [ψ α = 0] ,
where the infimum is taken over all level-α tests ψ α and where we recall that Σ refers to the covariance matrix of X.

Notations

Let recall the main notations that we shall use throughout the paper. In the sequel, n stands for the number of independent observations, p is the number of covariates. Besides, X V stands for the collection (X i ) i∈V of the covariates that correspond to the null hypothesis and d is the cardinality of the set V . The models m are subsets of I ⊂ V and we note D m their cardinality. T α stands for our testing procedure of level α. The statistics φ m and the test φ m,α are respectively defined in (3) and (4). Finally, the norm . is introduced in 5.

For x, y ∈ R, we set x ∧ y := inf{x, y}, x ∨ y := sup{x, y}.

For any u ∈ R, FD,N (u) denotes the probability for a Fisher variable with D and N degrees of freedom to be larger than u. In the sequel, L, L 1 , L 2 ,. . . denote constants that may vary from line to line. The notation L(.) specifies the dependency on some quantities. For the sake of simplicity, we only give the orders of magnitude in the results and we refer to the proofs for explicit constants.

3 The Testing procedure

I \ V such that for all m ∈ M, 1 ≤ D m ≤ n -d -1.
We introduce the following test of level α. We reject H 0 : "θ ∈ S V " when the statistic

T α := sup m∈M φ m (Y, X) -F -1 Dm,Nm (α m (X)) (8)
is positive, where the collection of weights {α m (X), m ∈ M} is chosen according to one of the two following procedures:

P 1 :
The α m 's do not depend on X and satisfy the equality :

m∈M α m = α . (9)
P 2 : For all m ∈ M, α m (X) = q X,α , the α-quantile of the distribution of the random variable

inf m∈M FDm,Nm Π V ∪m (ǫ) -Π V (ǫ) 2 n /D m ǫ -Π V ∪m (ǫ) 2 n /N m (10) conditionally to X.
Note that it is easy to compute the quantity q X,α . Let Z be a standard Gaussian random vector of size n independent of X. As ǫ is independent of X, the distribution of (10) conditionally to X is the same as the distribution of

inf m∈M FDm,Nm Π V ∪m (Z) -Π V (Z) 2 /D m Z -Π V ∪m (Z) 2 /N m
conditionally to X. Hence, we can easily work out its quantile using Monte-Carlo method.

Clearly, the computational complexity of the procedure is linear with respect to the size of the collection of models M even when using Procedure P 2 . Consequently, when we apply our procedure to high-dimensional data as in Section 6 or in [START_REF] Verzelen | Tests for Gaussian graphical models[END_REF], we favour collections M whose size is linear with respect to the number of covariates p. We respectively refer to T 1 α and T 2 α for the tests (8) associated with Procedure P 1 and P 2 . First, we are able to control the behavior of the test under the null hypothesis.

Proposition 1. The test T 1 α corresponds to a Bonferroni procedure and therefore satisfies

P θ (T α > 0) ≤ m∈M α m ≤ α,
whereas the test T 2 α has the property to be of size exactly α:

P θ (T α > 0) = α.
The proof is given in Appendix. Besides, the test T 2 α is more powerful than the corresponding test T 1 α defined with weights α m = α/|M|. Proposition 2. For any parameter θ that does not belong to S V , the procedure T 1 α with weights α m = α/|M| and the procedure T 2 α satisfy

P θ T 2 α (X, Y) > 0 X ≥ P θ T 1 α (X, Y) > 0 | X X a.s. . (11)
Again, the proof is given in Appendix. On the one hand, the choice of Procedure P 1 allows to avoid the computation of the quantile q X,α and possibly permits to give a Bayesian flavor to the choice of the weights. On the other hand, Procedure P 2 is more powerful than the corresponding test with Procedure P 1 . We will illustrate these considerations in Section 6. In sections 3.3, 4, and 5 we study the power and rates of testing of T α with Procedure P 1 .

Power of the Test

We aim at describing a set of vectors θ in R p over which the test defined in Section 3 with Procedure P 1 is powerful. Since Procedure P 2 is more powerful than Procedure P 1 with α m = α/|M|, the test with Procedure P 2 will also be powerful on this set of θ.

Let α and δ be two numbers in ]0, 1[, and let {α m , m ∈ M} be weights such that m∈M α m ≤ α. Let define Hypothesis (H M ) as follows:

(H M )
For all m ∈ M, α m ≥ exp(-N m /10) and δ ≥ exp 2(-N m /21).

For typical choices of the collections M and {α m , m ∈ M}, these conditions are fulfilled as discussed in Sections 4 and 5. Let us now turn to the main result.

Theorem 3. Let T α be the test procedure defined by (8). We assume that n > d + 2 and that Assumption (H M ) holds. Then, P θ (T α > 0) ≥ 1 -δ for all θ belonging to the set

F M (δ) := θ ∈ R p , ∃m ∈ M : var(Y |X V ) -var(Y |X V ∪m ) var(Y |X V ∪m ) ≥ ∆(m) ,
where

∆(m) := L 1 D m log 2 αmδ 1 + Dm Nm + L 2 1 + 2 Dm Nm log 2 αmδ n -d . ( 12
)
This result is similar to Theorem 1 in [START_REF] Baraud | Adaptative tests of linear hypotheses by model selection[END_REF] in fixed design regression framework and the same comment also holds: the test T α under procedure P 1 has a power comparable to the best of the tests among the family {φ m,α , m ∈ M}. Indeed, let us assume for instance that V = {0} and that the α m are chosen to be equal to α/|M|. The test T α defined by ( 8) is equivalent to doing several tests of θ = 0 against θ ∈ S m at level α m for m ∈ M and it rejects the null hypothesis if one of those tests does. From Theorem 3, we know that under the hypothesis H M this test has a power greater than 1 -δ over the set of vectors θ belonging to m∈M F ′ m (δ, α m ) where

F ′ m (δ, α m ) is the set of vectors θ ∈ R p such that var(Y ) -var(Y |X m ) var(Y |X m ) ≥ L(D m , N m ) n D m log 2 α m δ + log 2 α m δ . ( 13
)
Besides, L(D m , N m ) behaves like a constant if the ratio D m /N m is bounded. Let us compare this result with the set of θ over which the Fisher test φ m,α at level α has a power greater than 1 -δ.

Applying Theorem 3, we know that it contains F ′ m (δ, α). Moreover, the following Proposition shows that it is not much larger than F ′ m (δ, α):

Proposition 4. Let δ ∈]0, 1 -α[. If var(Y ) -var(Y |X m ) var(Y |X m ) ≤ L(α, δ) √ D m n , then P θ (φ m,α > 0) ≤ 1 -δ
The proof is postponed to Section 8 and is based on a lower bound of the minimax rate of testing.

F ′ m (δ, α) and F ′ m (δ, α m ) defined in (13) differ from the fact that log(1/α) is replaced by log(1/α m ). For the main applications that we will study in Section 4, 5, and 6, the ratio log (1/α m ) / log (1/α) is of order log(n), log log n, or k log(ep/k) where k is a "small" integer. Thus, for each δ ∈]0, 1 -α[, the test based on T α has a power greater than 1 -δ over a class of vectors which is close to m∈M F ′ m (δ, α). It follows that for each θ = 0 the power of this test under P θ is comparable to the best of the tests among the family {φ m,α , m ∈ M}.

In the next two sections, we use this theorem to establish rates of testing against different types of alternatives. First, we give an upper bound for the rate of testing θ = 0 against a class of θ for which a lot of components are equal to 0. In Section 5, we study the rates of testing and simultaneous rates of testing θ = 0 against classes of ellipsoids. For the sake of simplicity, we will only consider the case V = {0}. Nevertheless, the procedure T α defined in (8) applies in the same way when one considers more complex null hypothesis and the rates of testing are unchanged except that we have to replace n by n -d and var(Y ) by var(Y |X V ).

Detecting non-zero coordinates

Let us fix an integer k between 1 and p. In this section, we are interested in testing θ = 0 against the class of θ with a most k non-zero components. This typically corresponds to the situation encountered when considering tests of neighborhood for large sparse graphs. As the graph is assumed to be sparse, only a small number of neighbors are missing under the alternative hypothesis.

INRIA

For each pair of integers (k, p) with k ≤ p, let M(k, p) be the class of all subsets of I = {1, . . . , p} of cardinality k. The set Θ[k, p] stands for the subset of vectors θ ∈ R p , such that at most k coordinates of θ are non-zero.

First, we define a test T α of the form (8) with Procedure P 1 , and we derive an upper bound for the rate of testing of T α against the alternative θ ∈ Θ[k, p]. Then, we show that this procedure is rate optimal when all the covariates are independent. Finally, we study the optimality of the test when k = 1 for some examples of covariance matrix Σ.

Rate of testing of T α

Proposition 5. We consider the set of models M = M(k, p). We use the test T α under Procedure P 1 and we take the weights α m all equal to α/|M|. Let us suppose that n satisfies:

n ≥ L log 2 αδ + k log ep k . ( 14
)
Let us set the quantity

ρ ′2 k,p,n := L(α, δ) k log ep k n . ( 15
) For any θ in Θ[k, p], such that θ 2 var(Y )-θ 2 ≥ ρ ′2 k,p,n , P θ (T α > 0) ≥ 1 -δ.
We recall that the norm . is defined in ( 5) and equals var(Y ) -var(Y |X). This proposition easily follows from Theorem 3 and its proof is given in Section 7. Note that the upper bound does not directly depend on the covariance matrix of the vector X. Besides, Hypothesis ( 14) corresponds to the minimal assumption needed for consistency and type-oracle inequalities in the estimation setting as pointed out by [START_REF] Wainwright | Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting[END_REF] Th. 2) and Giraud [START_REF] Giraud | Estimation of Gaussian graphs by model selection[END_REF] Sect. 3.1). Hence, we conjecture that Hypothesis ( 14) is minimal so that Proposition 5 holds. We will further discuss the bound (15) after deriving lower bounds for the minimax rate of testing.

Minimax lower bounds for independent covariates

In the statistical framework considered here, the problem of giving minimax rates of testing under no prior knowledge of the covariance of X and of var(Y ) is open. This is why we shall only derive lower bounds when var(Y ) and the covariance matrix of X are known. In this section, we give non asymptotic lower bounds for the (α, δ)-minimax rate of testing over the set Θ[k, p] when the covariance matrix of X is the identity matrix (except Proposition 6). As these bounds coincide with the upper bound obtained in Section 4.1, this will show that our test T α is rate optimal.

We first give a lower bound for the (α, δ)-minimax rate of detection of all p non-zero coordinates for any covariance matrix Σ. Proposition 6. Let us suppose that var(Y ) is known. Let us set ρ 2 p,n such that:

ρ 2 p,n := L(α, δ) √ p n . ( 16
)
Then for all ρ < ρ p,n ,

β Σ θ ∈ Θ[p, p], θ 2 var(Y ) -θ 2 = ρ 2 ≥ δ,
where we recall that Σ is the covariance matrix of X.

If n ≥ (1 + γ)p for some γ > 0, Theorem 3 shows that the test φ I,α defined in (4) has power greater than δ over the vectors θ that satisfy

θ 2 var(Y ) -θ 2 ≥ L(γ, α, δ) √ p n .
Hence, √ p/n is the minimax rate of testing Θ[p, p] at least when the number of observations is larger than the number of covariates. This is coherent with the minimax rate obtained in the fixed design framework (e.g. [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF]). When p becomes larger we do not think that the lower bound given in Proposition 6 is still sharp. Note that this minimax rate of testing holds for any covariance matrix Σ contrary to Theorem 7.

We now turn to the lower bound for the (α, δ)-minimax rate of testing against θ ∈ Θ[k, p].

Theorem 7. Let us set ρ 2 k,p,n such that ρ 2 k,p,n := L(α, δ) k n log 1 + p k 2 + 2 p k 2 . ( 17
)
We suppose that the covariance of X is the identity matrix I. Then, for all ρ < ρ k,p,n ,

β I θ ∈ Θ[k, p], θ 2 var(Y ) -θ 2 = ρ 2 > δ.
where the quantity var(Y ) is known.

If α + δ ≤ 53%, then one has

ρ 2 k,p,n ≥ k 2n log 1 + p k 2 ∨ p k 2 .
This result implies the following lower bound for the minimax rate of testing

ρ (Θ[k, p], α, δ, var(Y ), I)) ≥ ρ 2 k,p,n .
The proof is given in Section 8. To the price of more technicalities, it is possible to prove that the lower bound still holds if the variables (X i ) are independent with known variances possibly different. Theorem 7 recovers approximately the lower bounds for the minimax rates of testing in signal detection framework obtained by [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF]. The main difference lies in the fact that we suppose var(Y ) known which in the signal detection framework translates in the fact that we would know the quantity f 2 + σ 2 . We are now in position to compare the results of Proposition 5 and Theorem 7. Let distinguish between the values of k.

INRIA

When k ≤ p γ for some γ < 1/2, if n is large enough to satisfy the assumption of Proposition 5, the quantities ρ 2 k,p,n and ρ ′2 k,p,n are both of the order k log(p) n times a constant (which depends on γ, α, and δ). This shows that the lower bound given in Theorem 7 is sharp. Additionally, in this case, the procedure T α defined in Proposition 5 follows approximately the minimax rate of testing. We recall that our procedure T α does not depend on the knowledge of var(Y ) and corr(X). In applications, a small k typically corresponds to testing a Gaussian graphical model with respect to a graph G, when the number of nodes is large and the graph is supposed to be sparse. When n does not satisfy the assumption of Proposition 5, we believe that our lower bound is not sharp anymore.

When

√ p ≤ k ≤ p, the lower bound and the upper bound do not coincide anymore. Nevertheless, if n ≥ (1 + γ)p for some γ > 0, Theorem 3 shows that the test φ I,α defined in (4) has power greater than δ over the vectors θ that satisfy

θ 2 var(Y ) -θ 2 ≥ L(γ, α, δ) √ p n . ( 18
)
This upper bound and the lower bound do not depend on k. Here again, the lower bound obtained in Theorem 7 is sharp and the test φ I,α defined previously is rate optimal. The fact that the rate of testing stabilizes around √ p/n for k > √ p also appears in signal detection and there is a discussion of this phenomenon in [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF].

When k < √ p and k is close to √ p, the lower bound and the upper bound given by Proposition 5 differ from at most a log(p) factor. For instance, if k is of order √ p/ log p, the lower bound in Theorem 7 is of order √ p log log p/ log p and the upper bound is of order √ p. We do not know if any of this bound is sharp and if the minimax rates of testing coincide when var(Y ) is fixed and when it is not fixed.

All in all, the minimax rates of testing exhibit the same range of rates in our framework as in signal detection [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF] when the covariates are independent. Moreover, this implies that the minimax rate of testing is slower when the (X i ) i∈I are independent than for any other form of dependence. Indeed, the upper bounds obtained in Proposition 5 and in (18) do not depend on the covariance of X. Then, a natural question arises: is the test statistic T α rate optimal for other correlation of X? We will partially answer this question when testing against the alternative θ ∈ Θ [1, p].

Minimax rates for dependent covariates

In this section, we look for the minimax rate of testing θ = 0 against θ ∈ Θ[1, p] when the covariates X i are no longer independent. We know that this rate is between the orders 1 n , which is the minimax rate of testing when we know which coordinate is non-zero, and log(p) n , the minimax rate of testing for independent covariates. Proposition 8. Let us suppose that there exists a positive number c such that for any i = j, |corr(X i , X j )| ≤ c and that α + δ ≤ 53%. We define ρ 2 1,p,n,c as

ρ 2 1,p,n,c := L n log(p) ∧ 1 c . ( 19
)
Then for any ρ < ρ 1,p,n,c ,

β Σ θ ∈ Θ[1, p], θ 2 var(Y ) -θ 2 = ρ 2 ≥ δ,
where Σ refers to the covariance matrix of X.

Remark: If the correlation between the covariates is smaller than 1/ log(p), then the minimax rate of testing is of the same order as in the independent case. If the correlation between the covariates is larger, we show in the following Proposition that under some additional assumption, the rate is faster. Proposition 9. Let us suppose that the correlation between X i and X j is exactly c > 0 for any i = j. Moreover, we assume that n satisfies the following condition:

n ≥ L 1 + log p αδ (20)
Let introduce the random variable X p+1 :=

T α = sup 1≤i≤p φ {i},α/(2p) ∨ φ {p+1},α/2 satisfies P 0 (T α > 0) ≤ α and P θ (T α > 0) ≥ 1 -δ, for any θ in Θ[1, p] such that θ 2 var(Y ) -θ 2 ≥ L(α, δ) n log p 1 c .
Consequently, when the correlation between X i and X j is a positive constant c, the minimax rate of testing is of order log(p)∧(1/c) n . When the correlation coefficient c is small, the minimax rate of testing coincides with the independent case, and when c is larger those rates differ. Therefore, the test T α defined in Proposition 5 is not rate optimal when the correlation is known and is large. Indeed, when the correlation between the covariates is large, the tests statistics φ {m},αm defining T α are highly correlated. The choice of the weights α m in Procedure P 1 corresponds to a Bonferroni procedure, which is precisely known to behave bad when the tests are positively correlated.

This example illustrates the limits of Procedure P 1 . However, it is not very realistic to suppose that the covariates have a constant correlation, for instance when one considers a GGM. Indeed, we expect that the correlation between two covariates is large if they are neighbors in the graph and smaller if they are far (w.r.t. the graph distance). This is why we derive lower bounds of the rate of testing for other kind of correlation matrices often used to model stationary processes.

Proposition 10. Let X 1 , . . . , X p form a stationary process on the one dimensional torus. More precisely, the correlation between X i and X j is a function of |i -j| p where |.| p refers to the toroidal distance defined by: |i -j| p := (|i -j|) ∧ (p -|i -j|) .

INRIA Σ 1 (w) and Σ 2 (t) respectively refer to the correlation matrix of X such that corr(X i , X j ) = exp(-w|i -j| p ) where w > 0 , corr(X i , X j ) = (1 + |i -j| p ) -t where t > 0 .

Let us set ρ 2 1,p,n,Σ1 (w) and ρ 2 1,p,n,Σ2 (t) such that:

ρ 2 1,p,n,Σ1 (w) := 1 n log 1 + L(α, δ)p 1 -e -w 1 + e -w ρ 2 1,p,n,Σ2 (t) :=        1 n log 1 + L(α, δ) p(t-1) t+1 if t > 1 1 n log 1 + L(α, δ) p 1+2 log(p-1) if t = 1 1 n log (1 + L(α, δ)p t 2 -t (1 -t)) if 0 < t < 1.
Then, for any ρ 2 < ρ 2 1,p,n,Σ1 (w),

β Σ1(w) θ ∈ Θ[1, p], θ 2 var(Y ) -θ 2 = ρ 2 ≥ δ,
and for any ρ 2 < ρ 2 1,p,n,Σ2 (t),

β Σ2(t) θ ∈ Θ[1, p], θ 2 var(Y ) -θ 2 = ρ 2 ≥ δ.
If the range ω is larger than 1/p γ or if the range t is larger than γ for some γ < 1, these lower bounds are of order log p n . As a consequence, for any of these correlation models the minimax rate of testing is of the same order as the minimax rate of testing for independent covariates. This means that our test T α defined in Proposition 5 is rate-optimal for these correlations matrices. However, if ω is smaller than 1/p or if t is smaller than 1/ log(p), we recover the parametric rates 1/n, which is achieved by the test φ {p+1},α . This comes from the fact that the correlation corr(X 1 , X i ) does not converge to zero for such choices of ω or t. We omit the details since the arguments are similar to the proof of Proposition 9.

To conclude, when k ≤ p γ (for γ ≤ 1/2), the test T α defined in Proposition 5 is approximately (α, δ)-minimax against the alternative θ ∈ Θ[k, p], when neither var(Y ) nor the covariance matrix of X is fixed. Indeed, the rate of testing of T α coincide (up to a constant) with the supremum of the minimax rates of testing on Θ[k, p] over all possible covariance matrices Σ:

ρ (Θ[k, p], α, δ) := sup var(Y )>0,Σ>0 ρ (Θ[k, p], α, δ, var(Y ), Σ) ,
where the supremum is taken over all positive var(Y ) and every positive definite matrix Σ. When k ≥ √ p and when n ≥ (1 + γ)p (for γ > 0), the test defined in (18) has the same behavior. However, our procedure does not adapt to Σ: for some correlation matrices (as shown for instance in Proposition 9), T α with Procedure P 1 is not rate optimal. Nevertheless, we believe and this will be illustrated in Section 6 that Procedure P 2 slightly improves the power of the test when the covariates are correlated.

Rates of testing on "ellipsoids" and adaptation

In this section, we define tests T α of the form (8) in order to test simultaneously θ = 0 against θ belongs to some classes of ellipsoids. We will study their rates and show that they are optimal at sometimes the price of a log p factor.

For any non increasing sequence (a i ) 1≤i≤p+1 such that a 1 = 1 and a p+1 = 0 and any R > 0, we define the ellipsoid E a (R) by

E a (R) := θ ∈ R p , p i=1 var(Y |X mi-1 ) -var(Y |X mi ) a 2 i ≤ R 2 var(Y |X) , (21)
where m i refers to the set {1, . . . , i} and m 0 = ∅.

Let us explain why we call this set an ellipsoid. Assume for instance that the (X i ) are independent identically distributed with variance one. In this case, the difference var

(Y |X mi-1 ) - var(Y |X mi ) equals |θ i | 2 and the definition of E a (R) translates in E a (R) = θ ∈ R p , p i=1 |θ i | 2 a 2 i ≤ R 2 var(Y |X) .
The main difference between this definition and the classical definition of an ellipsoid in the fixed design regression framework (as for instance in [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF]) is the presence of the term var(Y |X). We added this quantity in order to be able to derive lower bounds of the minimax rate. If the X i are not i.i.d. with unit variance, it is always possible to create a sequence X ′ i of i.i.d. standard gaussian variables by orthogonalizing the X i using Gram-Schmidt process. If we call θ ′ the vector in

R p such that Xθ = X ′ θ ′ , it is straightforward to show that var(Y |X mi-1 ) -var(Y |X mi ) = |θ ′ i | 2
. We can then express E a (R) using the coordinates of θ ′ as previously:

E a (R) = θ ∈ R p , p i=1 |θ ′ i | 2 a 2 i ≤ R 2 var(Y |X) .
The main advantage of Definition 21 is that it does not directly depend on the covariance of X. In the sequel we also consider the special case of ellipsoids with polynomial decay,

E ′ s (R) := θ ∈ R p , p i=1 var(Y |X mi-1 ) -var(Y |X mi ) i -2s var(Y |X) ≤ R 2 , ( 22
)
where s > 0 and R > 0. First, we define two tests procedures of the form (8) and evaluate their power respectively on the ellipsoids E a (R) and on the ellipsoids E ′ s (R). Then, we give some lower bounds for the (α, δ)-simultaneous minimax rates of testing. Extensions to more general l p balls with 0 < p < 2 are possible to the price of more technicalities by adapting the results of Section 4 in [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF].

These alternatives correspond to the situation where we are given an order of relevance on the covariates that are not in the null hypothesis. This order could either be provided by a previous knowledge of the model or by a model selection algorithm such as LARS (least angle regression) introduced by Efron et al. [START_REF] Efron | Least angle regression[END_REF]. We apply this last method to build a collection of models for our testing procedure (8) in [START_REF] Verzelen | Tests for Gaussian graphical models[END_REF].

INRIA

Simultaneous Rates of testing of T α over classes of ellipsoids

First, we define a procedure of the form (8) in order to test θ = 0 against θ belongs to any of the ellipsoids E a (R). For any x > 0, [x] denotes the integer part of x.

We choose the class of models M and the weights α m as follows:

If n < 2p, we take the set M to be ∪ 1≤k≤[n/2] m k and all the weights α m are equal to α/|M|.

If n ≥ 2p, we take the set M to be ∪ 1≤k≤p m k . α mp equals α/2 and for any k between 1 and p -1, α m k is chosen to be α/(2(p -1)).

As previously, we bound the power of the tests T α from a non-asymptotic point of view.

Proposition 11. Let us assume that

n ≥ L 1 + log 1 αδ . ( 23
)
For any ellipsoid E a (R), the test T α defined by ( 8) with Procedure P 1 and with the class of models given just above satisfies

P 0 (T α ≤ 0) ≥ 1 -α,
and

P θ (T α > 0) ≥ 1 -δ for all θ ∈ E a (R) such that θ 2 var(Y ) -θ 2 ≥ L(α, δ) log n inf 1≤i≤[n/2] a 2 i+1 R 2 + √ i n (24)
if n < 2p, or

θ 2 var(Y ) -θ 2 ≥ L(α, δ) log p inf 1≤i≤p-1 a 2 i+1 R 2 + √ i n √ p n (25) if n ≥ 2p.
All in all, for large values of n, the rate of testing is of order sup 1≤i≤p a

2 i R 2 ∧ √ i log(p) n
. We

show in the next subsection that the minimax rate of testing for an ellipsoid is of order:

sup 1≤i≤p a 2 i R 2 ∧ √ i n .
Besides, we prove in Proposition 16 that a loss in √ log log p is unavoidable if one considers the simultaneous minimax rates of testing over a family of nested ellipsoids. Nevertheless, we do not know if the term log(p) is optimal for testing simultaneously against all the ellipsoids E a (R) for all sequences (a i ) and all R > 0. When n is smaller than 2p, we obtain comparable results except that we are unable to consider alternatives in large dimensions in the infimum (25).

We now turn to define a procedure of the form (8) in order to test simultaneously that θ = 0 against θ belongs to any of the E ′ s (R). For this, we introduce the following collection of models M and weights α m :

If n < 2p, we take the set M to be ∪m k where k belongs to 2 j , j ≥ 0 ∩ {1, . . . , [n/2]} and all the weights α m are chosen to be α/|M|.

If n ≥ 2p, we take the set M to be ∪m k where k belongs to 2 j , j ≥ 0 ∩ {1, . . . , p} ∪ {p}, α mp equals α/2 and for any k in the model between 1 and p -1, α m k is chosen to be α/(2(|M| -1)).

Proposition 12. Let us assume that

n ≥ L 1 + log 1 αδ ( 26
)
and that R 2 ≥ √ log log n/n. For any s > 0, the test procedure T α defined by ( 8) with Procedure P 1 and with a class of models given just above satisfies:

P 0 (T α > 0) ≥ 1 -α, and P θ (T α > 0) ≥ 1 -δ for any θ ∈ E ′ s (R) such that θ 2 var(Y ) -θ 2 ≥ L (α, δ) R 2/(1+4s) √ log log n n 4s/(1+4s) + R 2 (n/2) -2s + log log n n (27) if n < 2p or θ 2 var(Y ) -θ 2 ≥ L (α, δ) R 2/(1+4s) √ log log p n 4s/(1+4s) + log log p n √ p n (28)
if n ≥ 2p.

Again, we retrieve similar results to those of Corollary 2 in [START_REF] Baraud | Adaptative tests of linear hypotheses by model selection[END_REF] in the fixed design regression framework. For s > 1/4 and n < 2p, the rate of testing is of order

√ log log n n 4s/(1+4s)
. We show in the next subsection that the logarithmic factor is due to the adaptive property of the test.

If s ≤ 1/4, the rate is of order n -2s . When n ≥ 2p, the rate is of order

√ log log p n 4s/(1+4s) ∧ √ p
n , and we mention at the end of the next subsection that it is optimal.

Here again, it is possible to define these tests with Procedure P 2 in order to improve the power of the test (see Section 6 for numerical results).

Minimax lower bounds

We first establish the (α, δ)-minimax rate of testing over an ellipsoid when the variance of Y and the covariance matrix of X are known.

Proposition 13. Let us set the sequence (a i ) 1≤i≤p+1 and the positive number R. We introduce

ρ 2 a,n (R) := sup 1≤i≤p ρ 2 i,n ∧ a 2 i R 2 , ( 29
)
where ρ 2 i,n is defined by ( 16), then for any non singular covariance matrix Σ we have

β Σ θ ∈ E a (R), θ 2 var(Y ) -θ 2 ≥ ρ 2 a,n (R) ≥ δ, INRIA where the quantity var(Y ) is fixed. If α + δ ≤ 47% then ρ 2 a,n (R) ≥ sup 1≤i≤p √ i n ∧ a 2 i R 2 .
This lower bound is once more analogous to the one in the fixed design regression framework. Contrary to the lower bounds obtained in the previous section, it does not depend on the covariance of the covariates. We now look for an upper bound of the minimax rate of testing over a given ellipsoid. First, we need to define the quantity D * as:

D * := inf 1 ≤ i ≤ p, a 2 i R 2 ≤ √ i n
with the convention that inf ∅ = p.

Proposition 14. Let us assume that n ≥ L log 1 + log 1 αδ . If R 2 > 1 n and D * ≤ n/2, the test φ m D * ,α defined by (4) satisfies

P 0 [φ m D * ,α = 1] ≤ α and P θ [φ m D * ,α = 0] ≤ δ for all θ ∈ E a (R) such that θ 2 var(Y ) -θ 2 ≥ L(α, δ) sup 1≤i≤p √ i n ∧ a 2 i R .
If n ≥ 2D * , the rates of testing on an ellipsoid are analogous to the rates on an ellipsoid in fixed design regression framework (see for instance [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF]). If D * is large and n is small, the bounds in Proposition 13 and 14 do not coincide. In this case, we do not know if this comes from the fact that the test in Proposition 14 does not depend on the knowledge of var(Y ) or if one of the bounds in Proposition 13 and 14 is not sharp.

We are now interested in computing lower bounds for rates of testing simultaneously over a family of ellipsoids, in order to compare them with rates obtained in Section 5.1. First, we need a lower bound for the minimax simultaneous rate of testing over nested linear spaces. We recall that for any D ∈ {1, . . . , p}, S mD stands for the linear spaces of vectors θ such that only their D first coordinates are possibly non-zero.

Proposition 15. For D ≥ 2, let us set ρ2 D,n := L(α, δ) log log(D + 1) √ D n . ( 30
)
Then, the following lower bound holds

β I   1≤D≤p θ ∈ S mD , θ 2 var(Y ) -θ 2 = r 2 D   ≥ δ,
if for all D between 1 and p, r D ≤ ρD,n Using this Proposition, it is possible to get a lower bound for the simultaneous rate of testing over a family of nested ellipsoids.

Proposition 16. We fix a sequence (a i ) 1≤i≤p+1 . For each R > 0, let us set

ρ2 a,R,n := sup 1≤D≤p ρ2 D,n ∧ (R 2 a 2 D ) . ( 31
)
where ρD,n is given by (30). Then, for any non singular covariance matrix Σ of the vector X,

β Σ R>0 θ ∈ E a (R), θ 2 var(Y ) -θ 2 ≤ ρ2 a,R,n ≥ δ.
This Proposition shows that the problem of adaptation is impossible in this setting: it is impossible to define a test which is simultaneously minimax over a class of nested ellipsoids (for R > 0). This is also the case in fixed design as proved by [START_REF] Spokoiny | Adaptative hypothesis testing using wavelets[END_REF] for the case of Besov bodies. The loss of a term of the order √ log log p/n is unavoidable. As a special case of Proposition 16, it is possible to compute a lower bound for the simultaneous minimax rate over E ′ s (R) where R describes the positive numbers. After some calculation, we find a lower bound of order:

√ log log p n 4s 1+4s √ p log log p n .
This shows that the power of the test T α obtained in (28) for n ≥ 2p is optimal when R 2 ≥ √ log log n/n. However, when n < 2p and s ≤ 1/4, we do not know if the rate n -2s is optimal or not.

To conclude, when n ≥ 2p the test T α defined in Proposition 12 achieves the simultaneous minimax rate over the classes of ellipsoids E ′ s (R). On the other hand, the test T α defined in Proposition 11 is not rate optimal simultaneously over all the ellipsoids E a (R) and suffers a loss of a √ log p factor even when n ≥ 2p.

Simulations studies

The purpose of this simulation study is threefold. First, we illustrate the theoretical results established in previous sections. Second, we show that our procedure is easy to implement for different choices of collections M and is computationally feasible even when p is large. Our third purpose is to compare the efficiency of Procedures P 1 and P 2 . Indeed, for a given collection M, we know from Section 3.2 that the test (8) based on Procedure P 2 is more powerful than the corresponding test based on P 1 . However, the computation of the quantity q X,α is possibly time consuming and we therefore want to know if the benefit in power is worth the computational burden.

To our knowledge, when the number of covariates p is larger than the number of observations n there is no test with which we can compare our procedure.

Simulation experiments

We consider the regression model ( 1) with I = {1, . . . , p} and test the null hypothesis "θ = 0", which is equivalent to "Y is independent of X", at level α = 5%. Let (X i ) 1 i p be a collection of p INRIA Gaussian variables with unit variance. The random variable is defined as follows: Y = p i=1 θ i X i +ε where ε is a zero mean gaussian variable with variance 1 -θ 2 independent of X.

We consider two simulation experiments described below.

1. First simulation experiment: The correlation between X i and X j is a constant c for any i = j. Besides, in this experiment the parameter θ is chosen such that only one of its components is possibly non-zero. This corresponds to the situation considered in Section 4. First, the number of covariates p is fixed equal to 30 and the number of observations n is taken equal to 10 and 15. We choose for c three different values 0, 0.1, and 0.8, allowing thus to compare the procedure for independent, weakly and highly correlated covariates. We estimate the size of the test by taking θ 1 = 0 and the power by taking for θ 1 the values 0.8 and 0.9. Theses choices of θ lead to a small and a large signal/noise ratio r s/n defined in ( 6) and equal in this experiment to θ 2 1 /(1 -θ 2 1 ). Second, we examine the behavior of the tests when p increases and when the covariates are highly correlated: p equals 100 and 500, n equals 10 and 15, θ 1 is set to 0 and 0.8, and c is chosen to be 0.8.

Second simulation experiment:

The covariates (X i ) 1 i p are independent. The number of covariates p equals 500 and the number of observations n equals 50 and 100. We set for any i ∈ {1, . . . , p}, θ i = Ri -s . We estimate the size of the test by taking R = 0 and the power by taking for (R, s) the value (0.2, 0.5), which corresponds to a slow decrease of the (θ i ) 1 i p . It was pointed out in the beginning of Section 5 that |θ i | 2 equals var(Y |X mi-1 ) -var(Y |X mi ). Thus, |θ i | 2 represents the benefit in term of conditional variance brought by the variable X i .

We use our testing procedure defined in (8) with different collections M and different choices for the weights {α m , m ∈ M}.

The collections M: we define three classes. Let us set J n,p = p ∧ [ n 2 ], where [x] denotes the integer part of x and let us define:

M 1 := {{i}, 1 i p} M 2 := {m k = {1, 2, . . . , k}, 1 k J n,p }} M 3 := {m k = {1, 2, . . . , k}, k ∈ {2 j , j ≥ 0} ∩ {1, . . . , J n,p }}
We evaluate the performance of our testing procedure with M = M 1 in the first simulation experiment, and M = M 2 and M 3 in the second simulation experiment. The cardinality of these three collections is smaller than p, and the computational complexity of the testing procedures is at most linear in p.

The collections {α m , m ∈ M}: We consider Procedures P 1 and P 2 defined in Section 3. When we are using the procedure P 1 , the α m 's equal α/|M| where |M| denotes the cardinality of the collection M . The quantity q X,α that occurs in the procedure P 2 is computed by simulation. We use 1000 simulations for the estimation of q X,α . In the sequel we note T M i ,Pj the test (8) with collection M i and Procedure P j .

In the first experiment, when p is large we also consider two other tests:

1. The test φ {1},α (4) of the hypothesis θ 1 = 0 against the alternative θ 1 = 0. This test corresponds to the single test when we know which coordinate is non-zero.

2. The test φ {p+1},α where X p+1 := 1 p p i=1 X i . Adapting the proof of Proposition 9, we know that this test is approximately minimax on Θ [1, p] if the correlation between the covariates is constant and large. Contrary to our procedures, these two tests are based on the knowledge of var(X) (and eventually θ). We only use them as a benchmark to evaluate the performance of our procedure. We aim at showing that our test with Procedure P 2 is as powerful than φ {p+1},α and is close to the test φ {1},α .

We estimate the size and the power of the testing procedures with 1000 simulations. For each simulation, we simulate the gaussian vector (X 1 , . . . , X p ) and then simulate the variable Y as described in the two simulation experiments.

Results of the simulation

Null hypothesis is true, The results of the first simulation experiment for c = 0 are given in Table 1. As expected, the power of the tests increases with the number of observations n and with the signal/noise ratio r s/n . If the signal/noise ratio is large enough, we obtain powerful tests even if the number of covariates p is larger than the number of observations.

θ 1 = 0 n T M 1 ,P1 T M 1 ,P2 10
In Table 2 we present results of the first simulation experiment for θ 1 = 0.8 when c varies. Let us first compare the results for independent, weakly and highly correlated covariates when using Procedure P 1 . The size and the power of the test for weakly correlated covariates are similar to the size and the power obtained in the independent case. Hence, we recover the remark following Proposition 8: when the correlation coefficient between the covariates is small, the minimax rate is of the same order as in the independent case. The test for highly correlated covariates is more powerful than the test for independent covariates, recovering thus the remark following Theorem 7: the worst case from a minimax rate perspective is the case where the covariates are independent. Let us now compare Procedures P 1 and P 2 . In the case of independent or weakly correlated covariates, they give similar results. For highly correlated covariates, the power of T M 1 ,P2 is much larger than the one of T M 1 ,P1 .

In Table 3 we present results of the multiple testing procedure and of the two tests φ {1},α and φ {p+1},α when c = 0.8 and the number of covariates p is large. For p = 500 and n = 15, one test takes less than one second with Procedure P 1 and less than 30 seconds with Procedure P 2 . As expected, Procedure P 1 is too conservative when p increases. For p = 100, the power of the test based on Procedure P 1 is smaller than the power of the test φ {p+1},α and this difference increases when p is larger. The test based on Procedure P 2 is as powerful as φ {p+1},α , and its power is close to the one of φ {1},α . We recall that this last test is based on the knowledge of the non-zero component of θ contrary to ours. Besides, the test φ {p+1},α was shown in Proposition 9 to be optimal for this particular correlation setting. Hence, Procedure P 2 seems to achieve the optimal rate in this situation. Thus, we advise to use in practice Procedure P 2 if the number of covariates p is large, because Procedure P 1 becomes too conservative, especially if the covariates are correlated.

INRIA Null hypothesis is true, θ 1 = 0 c = 0 n T M 1 ,P1 T M 1 ,P2 10
Null hypothesis is true, R = 0 The results of the second simulation experiment are given in Table 4. As expected, Procedure P 2 improves the power of the test and the test T M 3 ,P2 has the greatest power. In this setting, one should prefer the collection M 3 to M 2 . This was previously pointed out in Section 5 from a theoretical point of view. Although T M 3 ,P1 is conservative, it is a good compromise for practical issues: it is very easy and fast to implement and its performances are good.

n T M 2 ,P1 T M 2 ,P2 T M 3 ,P1 T M 3 ,P2 50
7 Proofs of Theorem 3,Propositions 5,9,11,12,and 14 Proof of Theorem 3. In a nutshell, we shall prove that conditionally to the design X the distribution of the test T α is the same as the test introduced by Baraud et al. [START_REF] Baraud | Adaptative tests of linear hypotheses by model selection[END_REF]. Hence, we may apply their non asymptotic upper bound for the power.

Distribution of φ m (Y, X) . First, we derive the distribution of the test statistic φ m (Y, X) under P θ . The distribution of Y conditionally to the set of variables (X V ∪m ) is of the form

Y = i∈V ∪m θ V ∪m i X i + ǫ V ∪m , ( 32
)
where the vector θ V ∪m is constant and ǫ V ∪m is a zero mean Gaussian variable independent of

X V ∪m , whose variance is var(Y |X V ∪m ). As a consequence, Y -Π V ∪m Y 2 n is exactly Π (V ∪m) ⊥ ǫ V ∪m 2
n , where Π (V ∪m) ⊥ denotes the orthogonal projection along the space generated by (X i ) i∈V ∪m .

INRIA

Using the same decomposition of Y one simplifies the numerator of φ m (Y, X):

Π V ∪m Y -Π V Y 2 n = i∈V ∪m θ V ∪m i (X i -Π V X i ) + Π V ⊥ ∩(V ∪m) ǫ V ∪m 2 n ,
where Π V ⊥ ∩(V ∪m) is the orthogonal projection onto the intersection between the space generated by (X i ) i∈V ∪m and the orthogonal of the space generated by (X i ) i∈V .

For any i ∈ m, let us consider the conditional distribution of X i with respect to X V ,

X i = j∈V θ V,i j X j + ǫ V i . ( 33
)
where θ V,i j are constants and ǫ V i is a zero-mean normal gaussian random variable whose variance is var(X i |X V ) and which is independent of X V . This enables us to express

X i -Π V X i = Π V ⊥ ∩(V ∪m) ǫ V i , for all i ∈ m . Therefore, we decompose φ m (Y, X) in φ m (Y, X) = N m Π V ⊥ ∩(V ∪m) i∈m θ V ∪m i ǫ V i + ǫ V ∪m 2 n D m Π (V ∪m) ⊥ ǫ V ∪m 2 n . ( 34
)
Let us define the random variable Z

m and Z

(2) m where Z

m refers to the numerator of ( 34) divided by N m and Z

(2) m to the denominator divided by D m . We now prove that Z The variables (ǫ V j ) j∈m are σ (X V ∪m )-measurable as linear combinations of elements in X V ∪m . Moreover, ǫ V ∪m follows a zero mean normal distribution with covariance matrix var(Y |X V ∪m )I n and is independent of X V ∪m . As a consequence, conditionally to X V ∪m , Z

m and Z

(2) m are independent by Cochran's Theorem as they correspond to projections onto two sets orthogonal from each other.

As ǫ V j is a linear combination of the columns of X V ∪m , Z

m follows a non-central χ 2 distribution conditionally to X V ∪m :

(Z (1) m

|X V ∪m ) ∼ var(Y |X V ∪m )χ 2    j∈m θ V ∪m j Π (V ∪m)∩V ⊥ ǫ V j 2 n var(Y |X V ∪m ) , D m    . We denote a 2 m (X V ∪m ) := j∈m θ V ∪m j Π (V ∪m)∩V ⊥ ǫ V j 2 n var(Y |XV ∪m )
this non-centrality parameter.

Power of T α conditionally to X V ∪m . Conditionally to X V ∪m our test statistic φ m (Y, X) is the same as that proposed by [START_REF] Baraud | Adaptative tests of linear hypotheses by model selection[END_REF] with n -d data and σ 2 = var(Y |X V ∪m ). Arguing as in their proof of Theorem 1, there exists some quantity ∆m (δ) such that the procedure accepts the hypothesis with probability not larger than δ/2 if a 2 m (X V ∪m ) > ∆m (δ):

∆m (δ) := 2.5 1 + K 2 m (U ) D m log 4 α m δ 1 + D m N m + (35) 2.5 [k m K m (U ) ∨ 5] log 4 α m δ 1 + 2D m N m ,
where U m := log(1/α m ), U := log(2/δ), k m := 2 exp (4U m /N m ), and

K m (u) := 1 + 2 u N m + 2k m u N m .
Consequently, we have

P θ (T α ≤ 0|X V ∪m ) 1 a 2 m (X V ∪m ) ≥ ∆m (δ) ≤ δ/2. ( 36
)
Let derive the distribution of the non-central parameter a m (X V ∪m ). First, we simplify the projection term as ǫ V j is a linear combinations of elements of X V ∪m .

Π (V ∪m)∩V ⊥ ǫ V j = Π V ∪m ǫ V j -Π V ǫ V j = Π V ⊥ ǫ V j . Let us define κ 2 m as κ 2 m := var j∈m θ V ∪m j ǫ V j var(Y |X V ∪m ) .
As the variable j∈m θ V ∪m j ǫ V j is independent of X V , and as almost surely the dimension of the vector space generated by X V is d, we get

j∈m θ V ∪m j Π V ⊥ ǫ V j 2 n var(Y |X V ∪m ) ∼ κ 2 m χ 2 (n -d).
Hence, applying for instance Lemma 1 in [START_REF] Laurent | Adaptive estimation of a quadratic function by model selection[END_REF], we get

P θ a 2 m (X V ∪m ) κ 2 m ≥ (n -d) -2 (n -d)U ≤ δ/2.
Let gather (36) with this last bound. If

κ 2 m ≥ ∆ ′ m (δ) := ∆m (δ) (n -d) 1 -2 U n-d , ( 37
)
then it holds that

P θ (T α ≤ 0) ≤ P θ T α ≤ 0, a 2 m (X V ∪m ) > ∆m (δ) + P θ a 2 m (X V ∪m ) ≤ ∆m (δ) ≤ E θ P θ T α ≤ 0, a 2 m (X V ∪m ) > ∆m (δ)|X V ∪m + P θ a 2 m (X V ∪m ) κ 2 m ≥ (n -d) -2 (n -d)U ≤ δ. INRIA Computation of κ 2 m .
Let us now compute the quantity κ 2 m in order to simplify Condition (37). Let first express var(Y |X V ) in terms of var(Y |X m∪V ) using the decomposition (32) of Y .

var(Y |X V ) = var   j∈V ∪m θ V ∪m j X j + ǫ V ∪m |X V   = var   j∈V ∪m θ V ∪m j X j |X V   + var ǫ V ∪m |X V = var   j∈V ∪m θ V ∪m j X j |X V   + var (Y |X V ∪m ) , (38)
as ǫ V ∪m is independent of X V ∪m . Now using the definition of ǫ V j in (33), it turns out that var

  j∈V ∪m θ V ∪m j X j |X V   = var   j∈m θ V ∪m j X j |X V   = var   j∈m θ V ∪m j ǫ V j |X V   = var   j∈m θ V ∪m j ǫ V j   , (39)
as the (ǫ V j ) j∈m are independent of X V . Gathering formulae ( 38) and (39), we get

κ 2 m = var(Y |X V ) -var(Y |X V ∪m ) var(Y |X V ∪m ) . (40)
Under Assumption H M , U m ≤ N m /10 for all m ∈ M and U ≤ N m /21. Hence, the terms U/N m , U m /N m , k m , and K m (U ) behave like constants and it follows from (37) that ∆ ′ (m) ≤ ∆(m), which concludes the proof.

Proof of Proposition 5. We first recall the classical upper bound for the binomial coefficient (see for instance (2.9) in [START_REF] Massart | Concentration Inequalities and Model Selection, École d'été de probabilités de Saint Flour[END_REF]

). log |M(k, p)| = log ( p k ) ≤ k log ep k .
As a consequence, log(1/α m ) ≤ log(1/α) + k log ep k . Assumption ( 14) with L = 21 therefore implies Hypothesis H M . Hence, we are in position to apply the second result of Theorem 3. Moreover, the assumption on n implies that n ≥ 21k and D m /N m is thus smaller than 1/20 for any model m in M(k, p). Formula (12) in Theorem 3 then translates into

△(m) ≤ (1 + √ 0.05)L 1 k 2 log ep k + k log 2 αδ + 1.1L 2 k log ep k + log 2 αδ n ,
and it follows that Proposition 5 holds.

Proof of Proposition 9. We fix the constant L in Hypothesis (20) to be 21 log(4e) ∨ C 2 log(4) where the universal constant C 2 is defined later in the proof. This choice of constants allows the procedure sup 1≤i≤p φ {i},α/(2p) to satisfy Hypothesis H M . An argument similar to the proof of Proposition 5 allows to show easily that there exists a universal constant C such that if we set

ρ ′2 1 := C log(p) + log 4 αδ n = C n log 4p αδ , (41)
then

θ 2 var(Y )-θ 2 ≥ ρ ′2 1 implies that P θ (T α > 0) ≥ 1 -δ.
Here, the factor 4 in the logarithm comes from the fact that some weights α m equal α/(2p).

Let ρ 2 and λ 2 be two positive numbers such that

λ 2 var(Y )-λ 2 = ρ 2 and let θ ∈ Θ[1, p] such that θ 2 = λ 2 . As corr(X i , X j ) = c for any i = j, it follows that var(X p+1 ) = c + 1-c p and cov(Y, X p+1 ) 2 = θ 2 c + 1-c p 2 . var(Y ) -var(Y |X p+1 ) var(Y |X p+1 ) = (c + (1 -c)/p) λ 2 var(Y ) -(c + (1 -c)/p) λ 2 .
We now apply Theorem 3 to φ {p+1},α/2 under H M . There exists a universal constant C 2 such that

P θ φ {p+1},α/2 > 0 ≥ 1 -δ if (c + (1 -c)/p) λ 2 var(Y ) -(c + (1 -c)/p) λ 2 ≥ C 2 n log 4 αδ .
This last condition is implied by

cλ 2 var(Y ) -cλ 2 ≥ C 2 n log 4 αδ ,
which is equivalent to

λ 2 var(Y ) ≥ C 2 cn + cC 2 log 4 αδ log 4 αδ . (42)
Let us assume that c ≥ log 4 αδ / log 4p αδ . As n ≥ 2C 2 log 4p αδ (Hypothesis (20) and definition of L), nc ≥ 2C 2 log 4 αδ . As a consequence, Condition ( 42) is implied by:

ρ 2 ≥ 2C 2 nc log 4 αδ . (43)
Combining ( 41) and ( 43) allows to conclude that Let first consider the case n < 2p and let apply Theorem 3 under Hypothesis

P θ (T α > 0) ≥ 1 -δ if ρ 2 ≥ L n log
H M to T α . P θ (T α > 0) ≥ 1 -δ for all θ ∈ R p such that ∃i ∈ {1, . . . , [n/2]}, var(Y ) -var (Y |X mi ) var (Y |X mi ) ≥ C i log 2[n/2] αδ + log 2[n/2] αδ n , (46)
where C is an universal constant. Let θ be an element of E a (R) that satisfies

θ 2 ≥ (1 + C) (var(Y |X mi ) -var(Y |X)) + (1 + C)var(Y |X) i log n αδ + log n αδ n ,
for some 1

≤ i ≤ [n/2].
(R), var(Y |X mi ) -var(Y |X) = a 2 i+1 var(Y |X) p j=i+1 var(Y |X mj-1 ) -var(Y |X mj ) a 2 i+1 var(Y |X) ≤ a 2 i+1 var(Y |X)R 2 .
Hence, if θ belongs to E a (R) and satisfies

θ 2 ≥ (1 + C)var(Y |X)     a 2 i+1 R 2 + i log n αδ n   + 1 n log n αδ   , then P θ (T α ≤ 0) ≤ δ.
Gathering this condition for any i between 1 and [n/2] allows to conclude that if θ satisfies

θ 2 var(Y ) -θ 2 ≥ (1 + C)   inf 1≤i≤[n/2]   a 2 i+1 R 2 + i log n αδ n   + 1 n log n αδ   , then P θ (T α ≤ 0) ≤ δ.
Let us now turn to the case n ≥ 2p. Let us consider T α as the supremum of p -1 tests of level α/2(p -1) and one test of level α/2. By considering the p -1 firsts tests, we obtain as in the previous case that

P θ (T α ≤ 0) ≤ δ if θ 2 var(Y ) -θ 2 ≥ (1 + C)   inf 1≤i≤(p-1)   a 2 i+1 R 2 + i log p αδ n   + 1 n log p αδ   .
On the other hand, using the last test statistic φ

I,α/2 , P θ (T α ≤ 0) ≤ δ if θ 2 var(Y ) -θ 2 ≥ C p log 2 αδ + log 2 αδ n .
Gathering these two conditions allows to prove (25).

Proof of Proposition 12. The approach behind this proof is similar to the one for Proposition 11. We fix the constant L in Assumption 26, as in the previous proof. Hence, the collection of models M and the weights α m satisfy hypothesis H M as in the previous proof.

Let us give a sharper upper bound on |M|:

|M| ≤ 1 + log(n/2 ∧ p)/ log(2) ≤ log(n ∧ 2p)/ log(2). ( 47
)
We deduce from (47) that there exists a constant L(α, δ) only depending on α and δ such that for all m ∈ M,

log 1 α m δ ≤ L(α, δ) log log(n ∧ p).
First, let us consider the case n < 2p. We apply Theorem 3 under Assumption H M . As in the proof of Proposition 11, we obtain that

P θ (T α > 0) ≥ 1 -δ if θ 2 var(Y ) -θ 2 ≥ L(α, δ) inf i∈{2 j ,j≥0}∩{1,...,[n/2]} R 2 (i + 1) -2s + √ i log log n n + log log n n . It is worth noting that R 2 i -2s ≤ √ i log log n n if and only if i ≥ i * = R 2 n √ log log n 2/(1+4s)
.

INRIA

Under the assumption on R, i * is larger than one. Let us distinguish between two cases. If there exists i ′ in {2 j , j ≥ 0} ∩ {1, . . . , [n/2]} such that i * ≤ i ′ , one can take i ′ ≤ 2i * and then inf

i∈{2 j ,j≥0}∩{1,...,[n/2]} R 2 i -2s + √ i log log n n ≤ 2 √ i ′ log log n n ≤ 2 √ 2R 2/(1+4s) √ log log n n 4s/(1+4s)
.

Else, we take i

′ ∈ {2 j , j ≥ 0} ∩ {1, . . . , [n/2]} such that n/4 ≤ i ′ ≤ n/2. Since i ′ ≤ (i * ∧ n/2) we obtain that inf i∈{2 j ,j≥0}∩{1,...,[n/2]} R 2 i -2s + √ i log log n n ≤ 2R 2 i ′-2s ≤ 2R 2 n 2 -2s . ( 49
)
Gathering inequalities ( 48) and ( 49) allows to prove (27).

We now turn to the case n ≥ 2p. As in the proof of Proposition 11, we divide the proof into two parts: first we give an upper bound of the power for the |M| -1 first tests which define T α and then we give an upper bound for the last test φ I,α/2 . Combining these two inequalities allows us to prove (28).

Proof of Proposition 14. We fix the constant L in the assumption as in the two previous proofs. We first note that the assumption on R 2 implies that D * ≥ 2. As N m is larger than n/2, the φ m D * test clearly satisfies Condition H M . As a consequence, we may apply Theorem 3. Hence,

P θ (T * α ≤ 0) ≤ δ for any θ such that var(Y ) -var(Y |X m D * ) var(Y |X m D * ) ≥ L(α, δ) √ D * n . (50)
Now, we use the same sketch as in the proof of Proposition 11. For any θ ∈ E a (R), Condition ( 50) is equivalent to:

θ 2 ≥ (var(Y |X m D * ) -var(Y |X)) 1 + L(α, δ) √ D * n + var(Y |X)L(α, δ) √ D * n . (51)
Moreover, as θ belongs to E a (R),

var(Y |X m D * ) -var(Y |X) ≤ a 2 D * +1 R 2 var(Y |X) ≤ a 2 D * var(Y |X)R 2 . As √ D * /n is smaller than one, Condition (51) is implied by θ 2 var(Y ) -θ 2 ≥ (1 + L(α, δ)) a 2 D * R 2 + √ D * n .
As a 2 D * R 2 is smaller than

√ D * n which is smaller sup 1≤i≤p √ i n ∧ a 2 i R 2 , it turns out that P θ (T * α = 0) ≤ δ for any θ belonging to E a (R) such that θ 2 var(Y ) -θ 2 ≥ 2(1 + L(α, δ)) sup 1≤i≤p √ i n ∧ a 2 i R 2 .
8 Proofs of Theorem 7,Propositions 4,6,8,10,13,15,and 16 Throughout this section, we shall use the notations η := 2(1 -α -δ) and L(η) := log(1+2η 2 ) 2 .

Proof of Theorem 7. This proof follows the general method for obtaining lower bounds described in Section 7.1 in [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF]. We first remind the reader of the main arguments of the approach applied to our model. Let ρ be some positive number and µ ρ be some probability measure on

Θ[k, p, ρ] := θ ∈ Θ[k, p], θ 2 var(Y ) -θ 2 = ρ .
We define P µρ = P θ dµ ρ (θ) and Φ α the set of level-α tests of the hypothesis "θ = 0". Then,

β I (Θ[k, p, ρ]) ≥ inf φα∈Φα P µρ [φ α = 0] ≥ 1 -α - sup A, P0(A)≤α |P µρ (A) -P 0 (A)| ≥ 1 -α - 1 2 P µρ -P 0 T V , (52)
where P µρ -P 0 T V denotes the total variation norm between the probabilities P µρ and P 0 . If we suppose that P µρ is absolutely continuous with respect to P 0 , we can upper bound the norm in total variation between these two probabilities as follows. We define

L µρ (Y, X) := dP µρ dP 0 (Y, X).
Then, we get the upper bound

P µρ -P 0 T V = |L µρ (Y, X) -1|dP 0 (Y, X) ≤ E 0 L 2 µρ (Y, X) -1 1/2
. Thus, we deduce from (52) that

β I (Θ[k, p, ρ]) ≥ 1 -α - 1 2 E 0 L 2 µρ (Y, X) -1 1/2 . If we find a number ρ * = ρ * (η) such that log E 0 L 2 µ ρ * (Y, X) ≤ L(η), (53)
then for any ρ ≤ ρ * ,

β I (Θ[k, p, ρ]) ≥ 1 -α - η 2 = δ.
To apply this method, we first have to define a suitable prior µ ρ on Θ [k, p, ρ]. Let m be some random variable uniformly distributed over M(k, p) and for each m ∈ M(k, p), let ǫ m = (ǫ m j ) j∈m

INRIA

be a sequence of independent Rademacher random variables. We assume that for all m ∈ M(k, p), ǫ m and m are independent. Let ρ be given and µ ρ be the distribution of the random variable θ = j∈ m λǫ m j e j where

λ 2 := var(Y )ρ 2 k(1 + ρ 2 ) ,
and where (e j ) j∈I is the orthonormal family of vectors of R p defined by (e j ) i = 1 if i = j and (e i ) j = 0 otherwise.

Straightforwardly, µ ρ is supported by Θ[k, p, ρ]. For any m in M(k, p) and any vector (ζ m j ) j∈m with values in {-1; 1}, let µ m,ζ m ,ρ be the Dirac measure on j∈m λζ m j e j . For any m in M(k, p), µ m,ρ denotes the distribution of the random variable j∈m λζ m j e j where (ζ m j ) is a sequence of independent Rademacher random variables. These definitions easily imply

L µρ (Y, X) = 1 ( p k ) m∈M(k,p) L µm,ρ (Y, X) = 1 2 k ( p k ) m∈M(k,p) ζ m ∈{-1,1} k L µ m,ζ m ρ (Y, X).
We aim at bounding the quantity E 0 (L 2 µρ ) and obtaining an inequality of the form (53). First, we work out L µ m,ζ m ,ρ :

L µ m,ζ m ,ρ (Y, X) =   1 1 -λ 2 k var(Y ) n/2 exp - Y 2 n 2 λ 2 k var(Y )(var(Y ) -λ 2 k) + λ j∈m ζ m j < Y, X j > n var(Y ) -λ 2 k -λ 2 j,j ′ ∈m ζ m j ζ m j ′ < X j , X j ′ > n 2(var(Y ) -λ 2 k)     , (54)
where < . > n refers to the canonical inner product in R n . Let us fix m 1 and m 2 in M(k, p) and two vectors ζ 1 and ζ 2 respectively associated to m 1 and m 2 . We aim at computing the quantity

E 0 L µ m 1 ,ζ 1 ,ρ (Y, X)L µ m 2 ,ζ 2 ,ρ (Y, X) .
m 3 := j ∈ m 1 ∩ m 2 |ζ 1 j = ζ 2 j m 4 := j ∈ m 1 ∩ m 2 |ζ 1 j = -ζ 2 j .
For the sake of simplicity, we reorder the elements of m 1 ∪ m 2 from 1 to |m 1 ∪ m 2 | such that the first elements belong to m 1 \ m 2 , then to m 2 \ m 1 and so on. Moreover, we define the vector

ζ ∈ R |m1∪m2| such that ζ j = ζ 1 j if j ∈ m 1 and ζ j = ζ 2 j if j ∈ m 2 \ m 1 . Using these notations, we compute the expectation of L m1,ζ 1 ,ρ (Y, X)L m2,ζ 2 ,ρ (Y, X). E 0 L µ m 1 ,ζ 1 ,ρ (Y, X)L µ m 2 ,ζ 2 ,ρ (Y, X) = 1 var(Y )(1 -λ 2 k var(Y ) ) 2 n/2 |A| -n/2 , ( 55
)
where |.| refers to the determinant and A is a symmetric square matrix of size |m 1 ∪ m 2 | + 1 such that:

A[1, j] :=          var(Y )+λ 2 k var(Y )(var(Y )-λ 2 k) if j = 1 - λζj-1 var(Y )-λ 2 k if (j -1) ∈ m 1 △m 2 -2 λζj-1 var(Y )-λ 2 k if (j -1) ∈ m 3 0 if (j -1) ∈ m 4 ,
where m 1 △m 2 refers to (m 1 ∪ m 2 ) \ (m 1 ∩ m 2 ). For any i > 1 and j > 1, A satisfies

A[i, j] :=                λ 2 ζi-1ζj-1 var(Y )-λ 2 k + δ i,j if (i -1, j -1) ∈ (m 1 \ m 2 ) × m 1 λ 2 ζi-1ζj-1 var(Y )-λ 2 k + δ i,j if (i -1, j -1) ∈ (m 2 \ m 1 ) × (m 2 \ m 1 ∪ m 3 ) -λ 2 ζi-1ζj-1 var(Y )-λ 2 k if (i -1, j -1) ∈ (m 2 \ m 1 ) × m 4 2λ 2 ζi-1ζj-1 var(Y )-λ 2 k + δ i,j if (i -1, j -1) ∈ [m 3 × m 3 ] ∪ [m 4 × m 4 ] 0 else,
, where δ i,j is the indicator function of i = j.

After some linear transformation on the lines of the matrix A, it is possible to express its determinant into

|A| = var(Y ) + λ 2 k var(Y )(var(Y ) -λ 2 k) I |m1∪m2| + C ,
where I |m1∪m2| is the identity matrix of size

|m 1 ∪ m 2 |. C is a symmetric matrix of size |m 1 ∪ m 2 | such that for any (i, j), C[i, j] = ζ i ζ j D[i, j]
and D is a block symmetric matrix defined by

D :=       λ 4 k var 2 (Y )-λ 4 k 2 -λ 2 var(Y ) var 2 (Y )-λ 4 k 2 -λ 2 var(Y )+λ 2 k λ 2 var(Y )-λ 2 k -λ 2 var(Y ) var 2 (Y )-λ 4 k 2 λ 4 k var 2 (Y )-λ 4 k 2 -λ 2 var(Y )+λ 2 k -λ 2 var(Y )-λ 2 k -λ 2 var(Y )+λ 2 k -λ 2 var(Y )+λ 2 k -2λ 2 var(Y )+λ 2 k 0 λ 2 var(Y )-λ 2 k -λ 2 var(Y )-λ 2 k 0 2λ 2 var(Y )-λ 2 k      
.

Each block corresponds to one of the four previously defined subsets of m 1 ∪ m 2 (i.e. m 1 \ m 2 , m 2 \m 1 , m 3 , and m 4 ). The matrix D is of rank at most four. By computing its non-zero eigenvalues, it is then straightforward to derive the determinant of

A |A| = var(Y ) -λ 2 (2|m 3 | -|m 1 ∩ m 2 |) 2 var(Y )(var(Y ) -λ 2 k) 2 .
Gathering this equality with (55) yields

E 0 L µ m 1 ,ζ 1 ,ρ (Y, X)L µ m 2 ,ζ 2 ,ρ (Y, X) =   1 1 -λ 2 (2|m3|-|m1∩m2|) var(Y )   n . ( 56
E 0 (L µm 1 ,ρ (Y, X)L µm 2 ,ρ (Y, X)) = E 0 1 1 -λ 2 Z var(Y ) n . ( 57
)
When Z is non-positive, this expression is smaller than one. Alternatively, when Z is nonnegative:

1 1 -λ 2 Z var(Y ) n = exp n log 1 1 -λ 2 Z var(Y ) ≤ exp   n λ 2 Z var(Y ) 1 -λ 2 Z var(Y )   ≤ exp   n λ 2 Z var(Y ) 1 -λ 2 k var(Y )   ,
as log(1+x) ≤ x and as Z is smaller than k. We define an event A such that {Z 0} ⊂ A ⊂ {Z ≥ 0} and P(A) = 1 2 . This is always possible as the random variable Z is symmetric. As a consequence, on the event A c , the quantity ( 57) is smaller or equal to one. All in all, we bound (57) by:

E 0 (L µm 1 ,ρ (Y, X)L µm 2 ,ρ (Y, X)) ≤ 1 2 + E 0   1 A exp   n λ 2 Z var(Y ) 1 -λ 2 k var(Y )     , (58)
where 1 A is the indicator function of the event A. We now apply Hölder's inequality with a parameter v ∈]0; 1], which will be fixed later.

E 0   1 A exp   n λ 2 Z var(Y ) 1 -λ 2 k var(Y )     ≤ P(A) 1-v   E 0 exp   n v λ 2 Z var(Y ) 1 -λ 2 k var(Y )     v ≤ 1 2 1-v cosh nλ 2 v(var(Y ) -λ 2 k) |m1∩m2|v . (59)
Gathering inequalities ( 58) and ( 59) yields

E 0 L 2 µρ (Y, X) ≤ 1 2 + 1 2 1-v 1 ( p k ) 2 m1,m2∈M(k,p) cosh nλ 2 v(var(Y ) -λ 2 k) |m1∩m2|v .
Following the approach of [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF] in Section 7.2, we note that if m 1 and m 2 are taken uniformly and independently in M(k, p), then |m 1 ∩ m 2 | is distributed as a Hypergeometric distribution with parameters p, k, and k/p. Thus, we derive that

E 0 L 2 µρ (Y, X) ≤ 1 2 + 1 2 1-v E cosh nλ 2 v(var(Y ) -λ 2 k) vT (60)
where T is a random variable distributed according to a Hypergeometric distribution with parameters p, k and k/p. We know from Aldous (p.173) [START_REF] Aldous | Exchangeability and related topics, École d'été de probabilités de Saint Flour[END_REF] that T has the same distribution as the random variable E(W |B p ) where W is binomial random variable of parameters k, k/p and B p some suitable σ-algebra. By a convexity argument, we then upper bound (60).

E 0 L 2 µρ (Y, X) ≤ 1 2 + 1 2 1-v E cosh nλ 2 v(var(Y ) -λ 2 k) vW = 1 2 + 1 2 1-v 1 + k p cosh nλ 2 v(var(Y ) -λ 2 k) v -1 k = 1 2 + 1 2 1-v exp k log 1 + k p cosh nλ 2 v(var(Y ) -λ 2 k) v -1 .
To get the upper bound on the total variation distance appearing in (52), we aim at constraining this last expression to be smaller than 1 + η 2 . This is equivalent to the following inequality:

2 v exp k log 1 + k p cosh nλ 2 k vk(var(Y ) -λ 2 k) v -1 ≤ 1 + 2η 2 . (61)
We now choose v = L(η) log(2) ∧ 1. If v is strictly smaller than one, then ( 61) is equivalent to:

k log 1 + k p cosh nλ 2 k vk(var(Y ) -λ 2 k) v -1 ≤ log(1 + 2η 2 ) 2 . ( 62
)
It is straightforward to show that this last inequality also implies (61) if v equals one. We now suppose that

nλ 2 v(var(Y ) -λ 2 k) ≤ log (1 + u) 1 v + (1 + u) 2 v -1 , (63)
where u = pL(η) k 2 . Using the classical equality cosh log(1

+ x + √ 2x + x 2 ) = 1 + x with x = (1 + u) 1 v -1, we deduce that inequality (63) implies (62) because k log 1 + k p cosh nλ 2 k vk(var(Y ) -λ 2 k) v -1 ≤ k log 1 + k p u ≤ k 2 p u ≤ L(η) .
For any β ≥ 1 and any x > 0, it holds that

(1 + x) β ≥ 1 + βx. As 1 v ≥ 1, Condition (63) is implied by: λ 2 k var(Y ) -λ 2 k ≤ kv n log 1 + u v + 2u v .

INRIA

One then combines the previous inequality with the definitions of u and v to obtain the upper bound

λ 2 k var(Y ) -λ 2 k ≤ k n L(η) log(2) ∧ 1 log 1 + p(log(2) ∨ L(η)) k 2 + 2p(log(2) ∨ L(η)) k 2 .
For any x positive and any u between 0 and 1, log(1 + ux) ≥ u log(1 + x). As a consequence, the previous inequality is implied by:

λ 2 k var(Y ) -λ 2 k ≤ k n L(η) log(2) ∧ 1 ([L(η) ∨ log(2)] ∧ 1) log 1 + p k 2 + 2p k 2 = k n (L(η) ∧ 1) log 1 + p k 2 + 2p k 2 .
To resume, if we take ρ 2 smaller than (17), then

β I (Θ[k, p, ρ]) ≥ δ .
Besides, the lower bound is strict if ρ 2 is strictly smaller than (17). To prove the second part of the theorem, one has to observe that α + δ ≤ 53% implies that L(η) ≥ 1 2 . Proof of Proposition 6. Let us first assume that the covariance matrix of X is the identity. We argue as in the proof of Theorem 7 taking k = p. The sketch of the proof remains unchanged except that we slightly modify the last part. Inequality (62) becomes

pv log cosh nλ 2 p vp(var(Y ) -λ 2 p) ≤ L(η),
where we recall that v = L(η) log 2 ∧ 1. For all x ∈ R, cosh(x) ≤ exp(x 2 /2). Consequently, the previous inequality is implied by

λ 2 p var(Y ) -λ 2 p ≤ 2vL(η) √ p n ,
and the result follows easily.

If we no longer assume that the covariance matrix Σ is the identity, we orthogonalize the sequence X i thanks to Gram-Schmidt process. Applying the previous argument to this new sequence of covariates allows to conclude.

Proof of Proposition 4. Let define the constant L(α, δ) involved in the condition:

L(α, δ) := log (1 + 8(1 -α -δ) 2 ) 1 ∧ log (1 + 8(1 -α -δ) 2 ) /(2 log 2)
Let us apply proposition 6. For any ρ ≤ L(α, δ) . Let θ ′ be an element of S m such that κ 2 m = ρ 2 . The distribution of φ m under P θ ′ is the same as its distribution under P θ , and therefore

P θ ′ (φ m,α ≤ 0) ≥ δ -ς.
Letting ς go to 0 enables to conclude.

Proof of Proposition 8. This lower bound for dependent gaussian covariates is proved through the same approach as Theorem 7. We define the measure µ ρ as in that proof. Under the hypothesis H 0 , Y is independent of X. We note Σ the covariance matrix of X and E 0,Σ stands for the distribution of (Y, X) under H 0 in order to emphasize the dependence on Σ.

First, one has to upper bound the quantity E 0,Σ L 2 µρ (Y, X) . For the sake of simplicity, we make the hypothesis that every covariate X j has variance 1. If this is not the case, we only have to rescale these variables. The quantity corr(i, j) refers to the correlation between X i and X j . As we only consider the case k = 1, the set of models m in M(1, p) is in correspondence with the set {1, . . . , p}.

E 0,Σ L µ i,ζ 1 ,ρ (Y, X)L µ j,ζ 2 ,ρ (Y, X) = var(Y ) var(Y ) -corr(i, j)λ 2 ζ 1 ζ 2 n .
When i and j are fixed, we upper bound the expectation of this quantity with respect to ζ 1 and ζ 2 by

E 0,Σ L µi,ρ (Y, X)L µj,ρ (Y, X) ≤ 1 2 + 1 2 var(Y ) var(Y ) -|corr(i, j)|λ 2 n . (64)
If i = j, |corr(i, j)| is smaller than c and if i = j, corr(i, j) is exactly one. As a consequence, taking the expectation of (64) with respect to i and j yields the upper bound

E 0,Σ L 2 µρ (Y, X) ≤ 1 2 + 1 2 1 p var(Y ) var(Y ) -λ 2 n + p -1 p var(Y ) var(Y ) -cλ 2 n . (65)
Recall that we want to constrain this quantity (65) to be smaller than 1 + η 2 . In particular, this holds if the two following inequalities hold:

1 p var(Y ) var(Y ) -λ 2 n ≤ 1 p + η 2 (66) p -1 p var(Y ) var(Y ) -cλ 2 n ≤ p -1 p + η 2 . ( 67
)
One then uses the inequality log( 1 1-x ) ≤ x 1-x which holds for any positive x smaller than one. Condition (66) holds if

λ 2 var(Y ) -λ 2 ≤ 1 n log(1 + pη 2 ) , (68)
INRIA whereas Condition (67) is implied by

cλ 2 var(Y ) -cλ 2 ≤ 1 n log 1 + p p -1 η 2 .
As c is smaller than one and p p-1 is larger than 1, this last inequality holds if

λ 2 var(Y ) -λ 2 ≤ 1 nc log(1 + η 2 ) . (69)
Gathering conditions ( 68) and ( 69) allows to conclude and to obtain the desired lower bound (19).

Proof of Proposition 10. The sketch of the proof and the notations are analogous to the one in Proposition 8. The upper bound (64) still holds:

E 0,Σ L µi,ρ (Y, X)L µj,ρ (Y, X) ≤ 1 2 + 1 2 var(Y ) var(Y ) -|corr(i, j)|λ 2 n .
Using the stationarity of the covariance function, we derive from (64) the following upper bound:

E 0,Σ L 2 µρ (Y, X) ≤ 1 2 + 1 2p p-1 i=0 var(Y ) var(Y ) -λ 2 |corr(0, i)| n ,
where corr(0, i) equals corr(X 1 , X i+1 ). As previously, we want to constrain this quantity to be smaller than 1 + η 2 . In particular, this is implied if for any i between 0 and p -1: 1. For corr(i, j) = exp(-w|i -j| p ), the sum is clearly bounded by 1 + 2

β Σ θ ∈ E a (R), θ 2 var(Y ) -θ 2 ≥ r 2 D ≥ δ .
The first result of Proposition 13 follows by gathering these lower bounds for all D between 1 and p.

Moreover, ρ 2 i,n is defined in Proposition 6 as

ρ 2 i,n = √ 2 L(η) ∧ L(η) √ log 2 √ i n . If α + δ ≤ 47%, it is straightforward to show that ρ 2 i,n ≥ √ i n .

INRIA

Proof of Proposition 15. We first need the following Lemma.

Lemma 17. We consider (I j ) j∈J a partition of I. For each j ∈ J let p(j) = |I j |. For any j ∈ J , we define Θ j as the set of θ ∈ R p such that their support is included in I j . For any sequence of positive weights k j such that j∈J k j = 1, it holds that

β I   j∈J θ ∈ Θ j , θ 2 var(Y ) -θ 2 = r 2 j   ≥ δ ,
if for all j ∈ J , r j ≤ ρ p(j),n (η/ k j ), where the function ρ p(j),n is defined by ( 16).

For all j ≥ 0 such that 2 j+1 -1 ∈ I (i.e. for all j ≤ J where J = log(p + 1)/ log(2) -1 ), let Sj be the linear span of the e k 's for k ∈ {2 j , . . . , 2 j+1 -1}. Then, dim( Sj ) = 2 j and Sj ⊂ S mD for D = D(j) = 2 j+1 -1. It is straightforward to show that It remains to check that (71) is larger than ρD(j),n . Using j + 1 = log(D + 1)/ log(2) ≥ log(D + 1), we get 2 j/2 ≥ D/2. Thanks to the convexity inequality log(1 + ux) ≥ u log(1 + x), which holds for any x > 0 and any u ∈]0, 1], we obtain log(1 + 2η 2 (j + 1)R(p))2

β I p D=1 θ ∈ S mD , θ 2 var(Y ) -θ 2 = r 2 D ≥ δ .
Proof of Lemma 17. Using a similar approach to the proof of Theorem 7, we know that for each r j ≤ ρj (η/ k j ) there exists some measure µ j over Θ j [r j ] := θ ∈ Θ j , θ 2 var(Y ) -θ 2 = r 2 j such that

E 0 L 2 µj (Y, X) ≤ 1 + η 2 /k j . (72)
We now define a probability measure µ = j∈J k j µ j over j∈J Θ j [r j ]. L µj refers to the density of P µj with respect to P 0 . Thus,

L µ (Y ) = dP µ dP 0 (Y, X) = j∈J k j L µj (Y, X) , and
E 0 L 2 µ (Y, X) = j,j ′ ∈J k j k j ′ E 0 L µj (Y, X)L µ j ′ (Y, X) .
Using expression (56), it is straightforward to show that if j = j ′ , then

E 0 L µj (Y, X)L µ j ′ (Y, X) = 1.

INRIA

This follows from the fact that the sets Θ j and Θ j ′ are orthogonal with respect to the inner product (5). Thus,

E 0 [L µ (Y, X)] = 1 + j∈J k 2 j E 0 L 2 µj (Y, X) -1 ≤ 1 + η 2
thanks to (72). Using the argument (53) as in the proof of Theorem 7 allows to conclude.

Proof of Proposition 16. First of all, we only have to consider the case where the covariance matrix of X is the identity. If this is not the case, one only has to apply Gram-Schmidt process to X and thus obtain a vector X ′ and a new basis for R p which is orthonormal. We refer to the beginning of Section 5 for more details.

Like the previous bounds for ellipsoids, we adapt the approach of Section 6 in [START_REF] Baraud | Non-asymptotic rates of testing in signal detection[END_REF]. We use the same notations as in proof of Proposition 13. Let D * (R) ∈ {1, . . . , p} an integer which achieves the supremum of ρ2 D ∧ (R 2 a 2 D ) = r2 D . As in proof of Proposition 13, for any R > 0,

θ ∈ S m D * (R) , θ 2 var(Y ) -θ 2 = r 2 D * (R) ⊂ θ ∈ E a (R), θ 2 var(Y ) -θ 2 ≥ r 2 D * (R)
The test associated with Procedure P 2 has the property to be of size exactly α. More precisely, for any θ ∈ S V , we have that P θ (T α > 0|X) = α X a.s. .

The result follows from the fact that q X,α satisfies

P θ sup m∈M N m Π V ∪m (ǫ) -Π V (ǫ) 2 n D m ǫ -Π V ∪m (ǫ) 2 n -F -1
Dm,Nm (q X,α ) > 0 X = α, and that for any

θ ∈ S V , Π V ∪m Y -Π V Y = Π V ∪m ǫ -Π V ǫ and Y -Π V ∪m Y = ǫ -Π V ∪m ǫ.
Proof of Proposition 2. Let come back to the definitions of T 1 α and T 2 α :

T 1 α (X, Y) = sup m∈M φ m (Y, X) -F -1 Dm,Nm (α/|M|) T 2 α (X, Y) = sup m∈M φ m (Y, X) -F -1 Dm,Nm (q X,α )
Conditionally on X, the size of T 1 α is smaller than α, whereas the size T 2 α is exactly α. As a consequence q X,α ≥ α/|M| as the statistics T 1 α and T 2 α differ only through these quantities. Thus, T 2 α (X, Y) ≥ T 1 α (X, Y), (X, Y) almost surely and the result (11) follows.

INRIA 3 . 2

 32 Comparison of Procedures P 1 and P 2

  First, we decompose the set m 1 ∪ m 2 into four sets (which possibly are empty): m 1 \ m 2 , m 2 \ m 1 , m 3 , and m 4 , where m 3 and m 4 are defined by:

  ) INRIA Then, we take the expectation with respect to ζ 1 , ζ 2 , m 1 and m 2 . When m 1 and m 2 are fixed the expression (56) depends on ζ 1 and ζ 2 only towards the cardinality of m 3 . As ζ 1 and ζ 2 correspond to independent Rademacher variables, the random variable 2|m 3 | -|m 1 ∩ m 2 | follows the distribution of Z, a sum of |m 1 ∩ m 2 | independent Rademacher variables and

  )-θ 2 = ρ 2 and P θ (φ m,α ≤ 0) ≥ δ -ς. In the proof of Theorem 3, we have shown in (34) and following equalities that the distribution of the test statistic φ m only depends on the quantity κ 2 m = var(Y )-var(Y |Xm) var(Y |Xm)

...

  Using the inequality log(1 + u) ≤ u, it is straightforward to show that this previous inequality holds ifλ 2 var(Y ) -λ 2 |corr(i,As |corr(i, 0)| is smaller than one for any i between 0 and p-1, it follows that E 0,Σ L 2 µρ (Y, X) is smaller than 1 + η 2 if We now apply the convexity inequality log(1 + ux) ≥ u log(1 + x) which holds for any positive x and any u between 0 and 1 to obtain the condition we only have to upper bound the sum of |corr(i, 0)| for the different types of correlation:

.

  For each dimension D between 1 and p, we define r 2 D = ρ 2 D,n ∧ a 2 D R 2 . Let us fix some D ∈ {1, . . . , p}. Since r 2 D ≤ a 2 D and since the a j 's are non increasing, D j=1 var(Y |X mj-1 ) -var(Y |X mj ) a 2 j ≤ var(Y |X)R 2 ,for all θ ∈ S mD such thatθ 2 var(Y )-θ 2 = r 2 D . Indeed, θ 2 = D j=1 var(Y |X mj-1 ) -var(Y |X mj ) and var(Y ) -θ 2 = var(Y |X). As a consequence, θ ∈ S mD , θ 2 var(Y ) -θ 2 = r 2 D ⊂ θ ∈ E a (R), θ 2 var(Y ) -θ 2 ≥ r 2 D Since r D ≤ ρ D,n , we deduce from Proposition 6 that

SFor

  m D(j) [r D(j) ] ⊂ p D=1 S mD [r D ] ,where Sj [r D (j)] := θ ∈ Sj ,θ 2 var(Y )-θ 2 = r 2 D(j) and S mD [r D ] := θ ∈ S mD , θ 2 var(Y )-θ 2 = r 2 D .Let choose J = {1, . . . , J}. For any j ∈ J , we define I j = 2 j , 2 j + 1, . . . , 2 j+1 -1 . Applying Lemma 17 with k j := [(j + 1)R(p)]-1 where R(p)if for all those D = D(j)r 2 D ≤ log(1 + 2η 2 /k j ) 1 ∧ log(1 + 2η 2 /k j ) D = D(j), this last quantity is lower bounded by log(1 + 2η 2 /k j ) 1 ∧ log(1 + 2η 2 /k j )

Table 1 :

 1

				0.043	0.045
			15	0.044	0.049
			Null hypothesis is false
	θ 1 = 0.8, r s/n = 1.78		θ 1 = 0.9, r s/n = 4.26
	n 10	T M 1 ,P1 T M 1 ,P2 0.48 0.48		n 10	T M 1 ,P1 T M 1 ,P2 0.86 0.86
	15	0.81	0.81		15	0.99	0.99

First simulation study, independent case: p = 30, c = 0. Percentages of rejection and value of the signal/noise ratio r s/n .

Table 2 :

 2 First simulation study, independent and dependent case. p = 30 Frequencies of rejection.

								c = 0.1
		0.043	0.045				n 10	T M 1 ,P1 T M 1 ,P2 0.042 0.04
	15	0.044	0.049				15	0.058	0.06
		c = 0.8
	n 10	T M 1 ,P1 T M 1 ,P2 0.018 0.045
	15	0.019	0.052
				Null hypothesis is false, θ 1 = 0.8
		c = 0						c = 0.1
	n 10	T M 1 ,P1 T M 1 ,P2 0.48 0.48				n 10	T M 1 ,P1 T M 1 ,P2 0.49 0.49
	15	0.81	0.81				15	0.81	0.82
		c = 0.8
	n 10	T M 1 ,P1 T M 1 ,P2 0.64 0.77
	15	0.89	0.94
				Null hypothesis is true, θ 1 = 0
			p = 100					p = 500
	n 10	T M 1 ,P1 T M 1 ,P2 φ {1},α φ {p+1},α 0.01 0.056 0.051 0.045	n 10	T M 1 ,P1 T M 1 ,P2 φ {1},α φ {p+1},α 0.009 0.044 0.040 0.040
	15	0.016	0.053	0.047	0.053	15	0.011	0.040	0.042	0.034
				Null hypothesis is false, θ 1 = 0.8
			p = 100					p = 500
	n 10	T M 1 ,P1 T M 1 ,P2 φ {1},α φ {p+1},α 0.60 0.77 0.91 0.79	n 10	T M 1 ,P1 T M 1 ,P2 φ {1},α φ {p+1},α 0.52 0.76 0.91 0.77
	15	0.85	0.92	0.99	0.92	15	0.77	0.94	0.99	0.94

Table 3 :

 3 First simulation study, dependent case: c = 0.8. Frequencies of rejection.

Table 4 :

 4 Second simulation study. Frequencies of rejection.

		0.013	0.052	0.036	0.059
	100	0.009	0.059	0.042	0.059
	Null hypothesis is false, R = 0.2, s = 0.5
	n 50	T M 2 ,P1 T M 2 ,P2 T M 3 ,P1 T M 3 ,P2 0.17 0.33 0.31 0.38
	100	0.42	0.66	0.62	0.69

  We fix the constant L to 42 log(80) in Hypothesis(23).First, we check that the test T α satisfies Condition H M . As the dimension of each model is smaller than n/2, for any model m in M, N m is larger than n/2. Moreover, for any model m in M, α m is larger than α/(2|M|) and |M| is smaller than n/2. As a consequence, the first condition of H M is implied by the inequality ≥ 20 log 40 α . Besides, for any n > 0 it holds that n/2 ≥ 20 log n 40 . Combining these two lower bounds enables to obtain (45). The second condition of H M holds if n ≥ 42 log 2 δ which is a consequence of hypothesis (44).

							It follows that
	(23) implies
	n ≥ 42 log	40 α	∨ log	2 δ	.	(44)
	n ≥ 20 log	n α	.			(45)
	Hypothesis (44) implies that n/2
		4p αδ	1 c	log	4 αδ	.

INRIA

Proof of Proposition 11.

  e -w 1-e -w and Condition (70) simplifies asρ 2 ≤ 1 n log 1 + 2pη 2 1 -e -w 1 + e -w .2. if corr(i, j) = (1 + |i -j| p ) -t for t strictly larger than one, then

	and Condition (70) simplifies as								p-1 i=0 |corr(i, 0)| ≤ 1 + 2 t-1
		ρ 2 ≤	1 n	log 1 +	2p(t -1)η 2 t + 1	.
	3. if corr(i, j) = (1 + |i -j| p ) -1 then simplifies as ρ 2 ≤ 1 n	p-1 i=0 |corr(i, 0)| ≤ 1 + 2 log(p -1) and Condition (70) log 1 + 2pη 2 1 + 2 log(p -1) .
	4. if corr(i, j) = (1 + |i -j| p ) -t for 0 < t < 1, then
	p-1 i=0	|corr(i, 0)| ≤ 1 +	2 1 -t	p 2	1-t	-1 ≤	1 -t 2	2 p	1-t
	and Condition (70) simplifies as
		ρ 2 ≤	1 n	log 1 + p

t 2 1-t (1 -t)η 2 .

Proof of Proposition 13.

  Thus, if for all 1 ≤ D ≤ p, r 2 D is smaller than ρ2 D,n , it holds that

	j/2 ≥ ≥ ≥	log [1 + log(D + 1)] log log(D + 1) D/2, D/2 η 2R(p) ∧ 1 (η √ 2) ∧ 1 1 √ 2 1 ∧ log(1 + 2η 2 ) log log(D + 1) √ D ,
	as R(p) is larger than one for any p ≥ 1. All in all, we get the lower bound
	log(1 + 2η 2 (j + 1) 2 R(p))	1 ∧	log(1 + 2η 2 ) √ 2 log 2	2 j/2 n
	≥	1 2 log(2)	1 ∧ log(1 + 2η 2 )	log log(D + 1)	√ D n	= ρ2 D,n .

RR n 6354

Verzelen & Villers

Acknowledgements

We gratefully thank Sylvie Huet and Pascal Massart for many fruitful discussions.

Appendix

Proof of Proposition 1. The test associated with Procedure P 1 corresponds to a Bonferroni procedure. Hence, we prove that its size is less than α by arguing as follows: let θ be an element of S V (defined in Section 2.2),

Because ǫ is independent of X, the distribution of φ m (Y, X) conditionally to X is a Fisher distribution with D m and N m degrees of freedom. As a consequence, φ m,αm (Y, X) is a Fisher test with D m and N m degrees of freedom. It follows that:

RR n 6354