Yannick Baraud

Christophe Giraud

Sylvie Huet

Estimator selection in the Gaussian setting

Keywords: AMS 2000 subject classifications: Primary 62J05; secondary 62J07, 62G05, 62G08, 62F07 Gaussian linear regression, Estimator selection, Model selection, Variable selection, Linear estimator, Kernel estimator, Ridge regression, Lasso, Elastic net, Random Forest, PLS1 regression

We consider the problem of estimating the mean f of a Gaussian vector Y with independent components of common unknown variance σ 2 . Our estimation procedure is based on estimator selection. More precisely, we start with an arbitrary and possibly infinite collection F of estimators of f based on Y and, with the same data Y , aim at selecting an estimator among F with the smallest Euclidean risk. No assumptions on the estimators are made and their dependencies with respect to Y may be unknown. We establish a non-asymptotic risk bound for the selected estimator. As particular cases, our approach allows to handle the problems of aggregation and model selection as well as those of choosing a window and a kernel for estimating a regression function, or tuning the parameter involved in a penalized criterion. We also derive oracletype inequalities when F consists of linear estimators. For illustration, we carry out two simulation studies. One aims at comparing our procedure to cross-validation for choosing a tuning parameter. The other shows how to implement our approach to solve the problem of variable selection in practice.

Introduction

The setting and the approach

We consider the Gaussian regression framework

Y i = f i + ε i , i = 1, . . . , n
where f = (f 1 , . . . , f n ) is an unknown vector of R n and the ε i are independent centered Gaussian random variables with common variance σ 2 . Throughout the paper, σ 2 is assumed to be unknown which corresponds to the practical case. Our aim is to estimate f from the observation of Y . For specific forms of f , this setting allows to deal simultaneously with the following problems.

Example 1 (Signal denoising). The vector f is of the form f = (F (x 1 ), . . . , F (x n ))

where x 1 , . . . , x n are distinct points of a set X and F is an unknown mapping from X into R.

Example 2 (Linear regression). The vector f is assumed to be of the form

f = Xβ (1)
where X is a n × p matrix, β is an unknown p-dimensional vector and p some integer larger than 1 (and possibly larger than n). The columns of the matrix X are usually called predictors. When p is large, one may assume that the decomposition (1) is sparse in the sense that only few β j are non-zero. Estimating f or finding the predictors associated to the non-zero coordinates of β are classical issues. The latter is called variable selection.

Our estimation strategy is based on estimator selection. More precisely, we start with an arbitrary collection F = { f λ , λ ∈ Λ} of estimators of f based on Y and aim at selecting the one with the smallest Euclidean risk by using the same observation Y . The way the estimators f λ depend on Y may be arbitrary and possibly unknown. For example, the f λ may be obtained from the minimization of a criterion, a Bayesian procedure or the guess of some experts.

The motivation

The problem of choosing some best estimator among a family of candidate ones is central in Statistics. Let us present some examples.

Example 3 (Choosing a tuning parameter). Many statistical procedures depend on a (possibly multi-dimensional) parameter λ that needs to be tuned in view of obtaining an estimator with the best possible performance. For imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 example, in the context of linear regression as described in Example 2, the Lasso estimator (see [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] and [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]) defined by f λ = X β λ with

β λ = argmin β∈R p Y -Xβ 2 + λ p j=1 |β j |
depends on the choice of the parameter λ ≥ 0. Selecting this parameter among a grid Λ ⊂ R + amounts to selecting a (suitable) estimator among the family

F = { f λ , λ ∈ Λ}.
Another dilemma for Statisticians is the choice of a procedure to solve a given problem. In the context of Example 3, there exist many competitors to the Lasso estimator and one may alternatively choose a procedure based on ridge regression (see [START_REF] Hoerl | Ridge regression: bayes estimation for nonorthogonal problems[END_REF]), random forest or PLS (see [START_REF] Tenenhaus | La régression PLS[END_REF], [START_REF] Helland | Some theoretical aspects of partial least squares regression[END_REF] and [START_REF] Helland | Partial least squares regression[END_REF]). Similarly, for the problem of signal denoising as described in Example 1, popular approaches include spline smoothing, wavelet decompositions and kernel estimators. The choice of a kernel may be possibly tricky.

Example 4 (Choosing a kernel). Consider the problem described in Example 1 with X = R. For a kernel K and a bandwidth h > 0, the Nadaraya-Watson estimator (see [START_REF] Nadaraya | On estimating regression[END_REF] and [START_REF] Watson | Smooth regression analysis[END_REF]) f K,h ∈ R n is defined as f K,h = F K,h (x 1 ), . . . , F K,h (x n )

where for x ∈ R

F K,h (x) = n j=1 K x-x j h Y j n j=1 K x-x j h
.

There exist many possible choices for the kernel K, such as the Gaussian kernel K(x) = e -x 2 /2 , the uniform kernel K(x) = 1 |x|<1 , etc. Given a (finite) family K of candidate kernels K and a grid H ⊂ R * + of possible values of h, one may consider the problem of selecting the best kernel estimator among the family F = { f λ , λ = (K, h) ∈ K × H}.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 1.3. A look at the literature A common way to address the above issues is to use some cross-validation scheme such as leave-one-out or V -fold. Even though these resampling techniques are widely used in practice, little is known on their theoretical performances. For more details, we refer to [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF] for a survey on cross-validation technics applied to model selection. Compared to these approaches, as we shall see, the procedure we propose is less time consuming and easier to implement. Moreover, it does not require to know how the estimators depend on the data Y and we can therefore handle the following problem.

Example 5 (Selecting among mute experts). A Statistician is given a collection F = { f λ , λ ∈ Λ} of estimators from a family Λ of experts λ, each of which keeping secret the way his/her estimator f λ depends on the observation Y . The problem is then to find which expert λ is the closest to the truth.

Given a selection rule among F, an important issue is to compare the risk of the selected estimator to those of the candidate ones. Results in this direction are available in the context of model selection, which can be seen as a particular case of estimator selection. More precisely, for the purpose of selecting a suitable model one starts with a collection S of those, typically linear spaces chosen for their approximation properties with respect to f , and one associates to each model S ∈ S a suitable estimator f S with values in S. Selecting a model then amounts to selecting an estimator among the collection F = { f S , S ∈ S}. For this problem, selection rules based on the minimization of a penalized criterion have been proposed in the regression setting by [START_REF] Yang | Model selection for nonparametric regression[END_REF], [START_REF] Baraud | Model selection for regression on a fixed design[END_REF], [START_REF] Birgé | Gaussian model selection[END_REF] and [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF]. Another way, usually called Lepski's method, appears in a series of papers by Lepski (1990;[START_REF] Lepskiȋ | Asymptotically minimax adaptive estimation. I. Upper bounds. Optimally adaptive estimates[END_REF]1992a;[START_REF] Lepskiȋ | On problems of adaptive estimation in white Gaussian noise[END_REF] and was originally designed to perform model selection among collections of nested models. Finally, we mention that other procedures based on resampling have interestingly emerged from the work of [START_REF] Arlot | Rééchantillonnage et Sélection de modèles[END_REF]2009) andCélisse (2008). A common feature of those approaches lies in the fact that the proposed selection rules apply to specific collections of estimators only.

An alternative to estimator selection is aggregation which aims at designing a suitable combination of given estimators in order to outperform each of these separately (and even the best combination of these) up to a remaining term. Aggregation techniques can be found in [START_REF] Catoni | Mixture approach to universal model selection[END_REF][START_REF] Catoni | Statistical learning theory and stochastic optimization[END_REF], [START_REF] Juditsky | Functional aggregation for nonparametric regression[END_REF], [START_REF] Nemirovski | Topics in non-parametric statistics[END_REF], Yang (2000a[START_REF] Yang | Mixing strategies for density estimation[END_REF][START_REF] Yang | Adaptive regression by mixing[END_REF], [START_REF] Tsybakov | Optimal rates of aggregation[END_REF], [START_REF] Wegkamp | Model selection in nonparametric regression[END_REF], [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF], [START_REF] Rigollet | Linear and convex aggregation of density estimators[END_REF], [START_REF] Bunea | Aggregation for Gaussian regression[END_REF] and [START_REF] Goldenshluger | A universal procedure for aggregating estimators[END_REF] for L plosses. Most of the aggregation procedures are based on a sample splitting, one part of the data being used for building the estimators, the remaining part for selecting among these. Such a device requires that the observations be i.i.d. or at least that one has at disposal two independent copies of the data. From this point of view our procedure differs from classical aggregation procedures since we use the whole data Y to build and select. In the Gaussian regression setting that is considered here, we mention the results of [START_REF] Leung | Information theory and mixing leastsquares regressions[END_REF] for the problem of mixing least-squares estimators. Their procedure uses the same data Y to estimate and to aggregate but requires the variance to be known. [START_REF] Giraud | Mixing least-squares estimators when the variance is unknown[END_REF] extends their results to the case where it is unknown.

What is new here?

Our approach for solving the problem of estimator selection is new. We introduce a collection S of linear subspaces of R n for approximating the estimators in F and use a penalized criterion to compare them. As already mentioned and as we shall see, this approach requires no assumption on the family of estimators at hand and is easy to implement, an R-package being available on http://w3.jouy.inra.fr/unites/miaj/public/perso/SylvieHuet_en.html.

A general way of comparing estimators in various statistical settings has been described in [START_REF] Baraud | Estimator selection with respect to Hellinger-type risks[END_REF]. However, the procedure proposed there is mainly abstract and inadequate in the Gaussian framework we consider.

We prove a non-asymptotic risk bound for the estimator we select and show that this bound is optimal in the sense that it essentially cannot be improved (except for numerical constants maybe) by any other selection rule. For the sakes of illustration and comparison, we apply our procedure to various problems among which aggregation, model selection, variable selection and selection among linear estimators. In each of these cases, our approach allows to recover classical results in the areas as well as to establish new imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 ones. In the context of aggregation we compute the aggregation rates for the unknown variance case. These rates turn out to be the same as those for the known variance case. For selecting an estimator among a family of linear ones, we propose a new procedure and establish a risk bound which requires almost no assumption on the considered family. Finally, our approach provides a way of selecting a suitable variable selection procedure among a family of candidate ones. It thus provides an alternative to cross-validation for which little is known.

The paper is organized as follows. In Section 2 we present our selection rule and the theoretical properties of the resulting estimator. For illustration, we show in Sections 3, 4 and 5 respectively, how the procedure can be used to aggregate preliminary estimators, select a linear estimator among a finite collection of candidate ones, or solve the problem of variable selection. Section 6 is devoted to two simulation studies. One aims at comparing the performance of our procedure to the classical V -fold in view of selecting a tuning parameter among a grid. In the other, we evaluate the performance of the variable selection procedure we propose to some classical ones such as the Lasso, random forest, and others based on ridge and PLS regression. Finally, the proofs are postponed to Section 7.

Throughout the paper C denotes a constant that may vary from line to line.

The procedure and the main result

The procedure

Given a collection F = { f λ , λ ∈ Λ} of estimators of f based on Y , the selection rule we propose is based on the choices of a family S of linear subspaces of R n , a collection {S λ , λ ∈ Λ} of (possibly random) subsets of S, a weight function ∆ and a penalty function pen, both from S into R + . We introduce those objects below and refer to Sections 3, 4 and 5 for examples.

The collection of estimators F

The collection F = { f λ , λ ∈ Λ} can be arbitrary. In particular, F need not be finite nor countable and it may consist of a mix of estimators based on the imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 minimization of a criterion, a Bayes procedure or the guess of some experts. The dependency of these estimators with respect to Y need not be known. Nevertheless, we shall see on examples how we can use this information, when available, to improve the performance of our estimation procedure.

The families S and S λ

Let S be a family of linear spaces of R n satisfying the following.

Assumption 1. The family S is finite or countable and for all S ∈ S, dim(S) ≤ n -2.

To each estimator f λ ∈ F, we associate a (possibly random) subset S λ ⊂ S.

Typically, the family S should be chosen to possess good approximation properties with respect to the elements of F and S λ with respect to f λ specifically. One may take S λ = S but for computational reasons it will be convenient to allow S λ to be smaller. The choices of S λ may be made on the basis of the observation f λ . We provide examples of S and S λ in various statistical settings described in Sections 3 to 5. (2)

Whenever S is finite, inequality (2) automatically holds true. However, in practice Σ should be kept to a reasonable size. When Σ = 1, e -∆(.) can be interpreted as a prior distribution on S and gives thus a Bayesian flavor to the procedure we propose. To the weight function ∆, we associate the function pen ∆ mapping S into R + and defined by

E U - pen ∆ (S) n -dim(S) V + = e -∆(S) (3)
where x + denotes the positive part of x ∈ R and U, V are two independent χ 2 random variables with respectively dim(S) + 1 and ndim(S) -1 degrees of freedom. This function can be easily computed from the quantiles of the Fisher distribution as we shall see in Section 8.1. From a more theoretical point of view, it is shown in [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF] that under Assumption 3 below, there exists a positive constant C (depending on κ only) such that pen ∆ (S) ≤ C(dim(S) ∨ ∆(S)).

(

4)

Assumption 3. There exists κ ∈ (0, 1) such that for all S ∈ S,

1 ≤ dim(S) ∨ ∆(S) ≤ κn.

The selection criterion

The selection procedure we propose involves a penalty function pen from S into R + with the following property.

Assumption 4. The penalty function pen satisfies for some K > 1, pen(S) ≥ Kpen ∆ (S) for all S ∈ S.

(5)

Whenever equality holds in (5), it derives from (4) that pen(S) measures the complexity of the model S in terms of dimension and weight.

Denoting Π S the projection operator onto a linear space S ⊂ R n , given the families S λ , the penalty function pen and some positive number α, we define

crit α ( f λ ) = inf S∈S λ Y -Π S f λ 2 + α f λ -Π S f λ 2 + pen(S) σ 2 S , (6)
where

σ 2 S = Y -Π S Y 2 n -dim(S) . (7)

The main result

For all λ ∈ Λ let us set

A( f λ , S λ ) = inf S∈S λ f λ -Π S f λ 2 + pen(S) σ 2 S . (8)
This quantity corresponds to an accuracy index for the estimator f λ with respect to the family S λ . The following result holds.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Theorem 1. Let K > 1, α > 0, δ ≥ 0. Assume that Assumptions 1, 2 and 4 hold. There exists a constant C (given by ( 33)) depending on K and α only such that for any f λ in F satisfying

crit α ( f λ ) ≤ inf λ∈Λ crit α ( f λ ) + δ, (9)
we have the following bounds

CE f -f λ 2 ≤ E inf λ∈Λ f -f λ 2 + A( f λ , S λ ) + Σσ 2 + δ (10) ≤ inf λ∈Λ E f -f λ 2 + E A( f λ , S λ ) + Σσ 2 + δ(11)
(provided that the quantity involved in the expectation in ( 10) is measurable). Furthermore, if equality holds in (5) and Assumption 3 is satisfied, for each λ ∈ Λ

• if the set S λ is non-random,

C ′ E A( f λ , S λ ) ≤ E f -f λ 2 + inf S∈S λ E f λ -Π S f λ 2 + (dim(S) ∨ ∆(S))σ 2 (12)
• if there exists a (possibly random) linear space S λ ∈ S λ such that f λ ∈ S λ with probability 1,

C ′ E A( f λ , S λ ) ≤ E f -f λ 2 + E dim( S λ ) ∨ ∆( S λ ) σ 2 , ( 13
)
where C ′ is a positive constant only depending on κ and K.

Let us now comment Theorem 1.

It turns out that inequality (10) leaves no place for a substantial improvement in the sense that the bound we get is essentially optimal and cannot be improved (apart from constants) by any other selection rule among F. To see this, let us assume for simplicity that F is finite so that a measurable minimizer of crit α always exists and δ can be chosen as 0. Let K = 1.1, α = 1/2 (to fix up the ideas), S a family of linear spaces satisfying the assumptions of Theorem 1 and pen, the penalty function achieving equality in (5). Besides, assume that S contains a linear space S such that 1 ≤ dim(S) ≤ n/2 and associate to S the weight ∆(S) = dim(S). If S λ = S for all λ, we deduce from ( 4) and ( 10) that for some universal constant C ′ , whatever F and

f ∈ R n C ′ E f -f λ 2 ≤ E inf λ∈Λ f -f λ 2 + inf S∈S f λ -Π S f λ 2 + pen(S) σ 2 S ≤ E inf λ∈Λ f -f λ 2 + f λ -Π S f λ 2 + dim(S) σ 2 S . (14)
In the opposite direction, the following result holds.

Proposition 1. There exists a universal constant C, such that for any finite family F = { f λ , λ ∈ Λ} of estimators and any selection rule λ based on Y among Λ, there exists f ∈ S such that

CE f -f λ 2 ≥ E inf λ∈Λ f -f λ 2 + f λ -Π S f λ 2 + dim(S)σ 2 . ( 15
)
We see that, up to the estimator σ 2 S in place of σ 2 and numerical constants, the left-hand sides of ( 14) and (15) coincide.

In view of commenting (11) further, we continue assuming that F is finite so that we can keep δ = 0 in (11). A particular feature of (11) lies in the fact that the risk bound pays no price for considering a large collection F of estimators. In fact, it is actually decreasing with respect to F (or equivalently Λ) for the inclusion. This means that if one adds a new estimator to the collection F (without changing neither S nor the families S λ associated to the former estimators), the risk bound for f λ can only be improved. In contrast, the computation of the estimator f λ is all the more difficult that |F| is large. More precisely, if the cardinalities of the families S λ are not too large, the computation of f λ requires around |F| steps.

The selection rule we use does not require to know how the estimators depend on Y . In fact, as we shall see, a more important piece of information is the ranges of the estimators f λ = f λ (Y ) as Y varies in R n . A situation of special interest occurs when each f λ belongs to some (possibly random) imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 linear space S λ in S with probability one. By taking S λ such that S λ ∈ S λ for all λ, we deduce from Theorem 1 by using ( 11) and ( 13) the following corollary.

Corollary 1. Assume that the Assumptions of Theorem 1 are satisfied, that Assumption 3 holds and that equality holds in (5). If for all λ ∈ Λ there exists a (possibly random) linear space S λ ∈ S λ such that f λ ∈ S λ with probability 1, then

f λ satisfies CE f -f λ 2 ≤ inf λ∈Λ E f -f λ 2 + E dim( S λ ) ∨ ∆( S λ ) σ 2 + δ, (16)
for some C depending on K and κ only.

One may apply this result in the context of model selection. One starts with a collection of models S = {S m , m ∈ M} and associate to each S m an estimator f m with values in S m . By taking

F = { f m , m ∈ M} (here Λ = M) and S m = {S m } for all m ∈ M, our selection procedure leads to an estimator f m which satisfies CE f -f m 2 ≤ inf m∈M E f -f m 2 + (dim(S m ) ∨ ∆(S m )) σ 2 . (17) When f m = Π Sm Y for all m ∈ M, our selection rule becomes m = arg min m∈M Y -f m 2 + pen(S m ) σ 2 Sm (18)
and turns out to coincide with that described in [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF]. Interestingly, Corollary 1 shows that this selection rule can still be used for families F of (non-linear) estimators of the form Π S m Y where the S m are chosen randomly among S on the basis of Y , doing thus as if the linear spaces S m were non-random. An estimator of the form Π S m Y can be interpreted as resulting from a model selection procedures among the family of projection estimators {Π m Y, m ∈ M} and hence, (18) can be used to choose some best model selection rule among a collection of candidate ones.

Aggregation

In this section, we consider the problems of Model Selection Aggregation (MS), Convex Aggregation (Cv) and Linear Aggregation (L) defined below.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Given M ≥ 2 preliminary estimators of f , denoted {φ k , k = 1, . . . , M }, our aim is to build an estimator f based on Y whose risk is as close as possible to inf g∈F Λ fg 2 where

F Λ = f λ = M j=1 λ j φ j , λ ∈ Λ
and, according to the aggregation problem at hand, Λ is one of the three sets

Λ MS = λ ∈ {0, 1} M , M j=1 λ j = 1 , Λ Cv = λ ∈ R M + , M j=1 λ j = 1 , Λ L = R M . When Λ = Λ MS , F Λ is the set {φ 1 , . . . , φ M } consisting of the initial estimators. When Λ = Λ Cv , F Λ is the convex hull of the φ j .
In the literature, one may also find

Λ ′ Cv = λ ∈ [0, 1] M , M j=1 λ j ≤ 1 in place of Λ Cv in which case F Λ is the convex hull of {0, φ 1 , . . . , φ M }.
Finally, when Λ = Λ L , F Λ is the linear span of the φ j .

Each of these three aggregation problems are solved separately if for each Λ ∈ {Λ MS , Λ Cv , Λ L } one can design an estimator f = f (Λ) satisfying

E f -f 2 -C inf g∈F Λ f -g 2 ≤ C ′ ψ n,Λ σ 2 (19) with C = 1, C ′ > 0 free of f, n, M and ψ n,Λ =        M if Λ = Λ L n log(eM/ √ n) if Λ = Λ Cv and √ n ≤ M M if Λ = Λ Cv and √ n ≥ M log M if Λ = Λ MS . (20)
These problems have only been considered when the variance is known. The quantity ψ n,Λ then corresponds to the best possible upper bound in ( 19) over all possible f ∈ R n and preliminary estimators φ j and is called the optimal rate of aggregation. For a more precise definition, we refer the reader to [START_REF] Tsybakov | Optimal rates of aggregation[END_REF]. [START_REF] Bunea | Aggregation for Gaussian regression[END_REF] these three problems simultaneously by building an estimator f which satisfies ( 19) simultaneously for all Λ ∈ {Λ MS , Λ Cv , Λ L } and some constant C > 1. This is an interesting issue since it is impossible to know in practice which aggregation device should be used to achieve the smallest risk bound: as Λ grows (for the inclusion), the bias inf g∈F Λ fg 2 decreases while the rate ψ n,Λ increases.

The aim of this section is to show that our procedure provides a way of solving (or nearly solving) the three aggregation problems both separately and simultaneously when the variance is unknown.

Throughout this section, we consider the family S consisting of the S m defined for each m ⊂ {1, . . . , M} and m = ∅ as the linear span of the φ j for j ∈ m. Along this section, we shall use the weight function ∆ defined on S by

∆(S m ) = |m| + log M |m| ,
take α = 1/2 and pen(.) = 1.1pen ∆ (.) taking thus K = 1.1. The choices of α and K is only to fix up the ideas. Note that ∆ satisfies Assumption 2 with Σ < 1. To avoid trivialities, we assume all along n ≥ 4.

3.1. Solving the three aggregation problems separately

Linear Aggregation

Problem (L) is the easiest to solve. Let us take F = F Λ with Λ = Λ L and

S = S L = S {1,...,M } (21)
and

S λ = S L for all λ ∈ Λ L . Minimizing crit α (f λ ) over f λ ∈ F Λ amounts to minimizing Y -f λ 2 over f λ ∈ S {1,.
..,M } and hence, the resulting estimator

is merely f L = Π S {1,...,M } Y . The risk of f L satisfies E f -f L ≤ inf g∈F Λ f -g 2 + Mσ 2 .
whatever n and M which solves the problem of Linear Aggregation.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Model Selection Aggregation

To tackle Problem (MS), we take

F = F Λ with Λ = Λ MS , that is, F Λ = {φ 1 , . . . , φ M }, S = S MS = {S {1} , . . . , S {M } } (22)
and associate to each f λ = φ j the collection S λ reduced to S {j} . Note that dim(S) ≤ 1 and ∆(S) = log(eM) ≥ dim(S) for all S ∈ S MS , so that under the assumption that log(eM) ≤ n/2 we may apply Corollary 1 with δ = 0 (since F Λ is finite), κ = 1/2 and get that for some constant C > 0 the resulting estimator f MS satisfies

CE f -f MS 2 ≤ inf g∈F Λ f -g 2 + log(M)σ 2 .
This risk bound is of the form ( 19) except for the constant C which is not equal to 1. We do not know whether Problem (MS) can be solved or not with C = 1 when the variance σ 2 is unknown and M is large (possibly larger than n).

Convex aggregation

For this problem, we emphasize the aggregation rate with respect to the quantity

L = sup j=1,...,M φ j σ √ n . ( 23
)
If M < √ nL, take again the estimator f L . Since the convex hull of the φ j is a subset of the linear space S {1,...,M } , for Λ = Λ Cv we have

E f -f L 2 ≤ inf g∈F Λ f -g 2 + Mσ 2 .
Let us now turn to the case M ≥ √ nL. More precisely, assume that

2 ≤ √ nL ≤ M ≤ e -1 min √ nLe nL 2 , e √ n/(2L) (24)
and set d(n, M) = n/(2 log(eM)). We consider the family of estimators F = F Λ with Λ = Λ Cv and

S = S Cv = S λ = S m ∈ S, |m| ≤ d(n, M) , ∀λ ∈ Λ Cv . ( 25
)
imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

The set Λ Cv being compact, λ → crit α (f λ ) admits a minimum λ over Λ Cv and we set f Cv = f λ .

Proposition 2. There exists a universal constant C > 1 such that

E f -f Cv 2 -C inf g∈F Λ f -g 2 ≤ C nL 2 log(eM/ √ nL 2 )σ 2 .
This risk bound is of the form ( 19) except for the constant C which is not equal to 1. Again, we do not know whether Problem (Cv) can be solved or not with C = 1 when the variance σ 2 is unknown and M possibly larger than n.

Solving the three problems simultaneously

Consider now three estimators f L , f MS , f Cv with values respectively in S {1,...,M } , M j=1 S {j} and the convex hull C of the φ j (we use a new notation for this convex hull to avoid ambiguity). One may take the estimators defined in Section 3.1 but any others would suit. The aim of this section is to select the one with the smallest risk to estimate f . To do so, we apply our selection procedure with F = { f L , f MS , f Cv }, taking thus Λ = {L, MS, Cv}, and associate to each of these three estimators the families S L , S MS , S Cv defined by ( 21), ( 22) and ( 25) respectively and choose S = S L ∪ S MS ∪ S Cv .

Proposition 3. Assume that (24) holds and that log(eM) ≤ n/2. There exists a universal constant C > 0 such that whatever f L , f MS and f Cv with values in S {1,...,M } , M j=1 S {j} and C respectively, the selected estimator

f λ satisfies for all f ∈ R n , CE f -f λ 2 ≤ inf λ∈{L,MS,Cv} E f -f λ 2 + B λ ,
where

B L = σ 2 M, B MS = σ 2 log M, B Cv = σ 2 M ∧ nL 2 log(eM/ √ nL 2 ) .
In particular, if f L , f MS and f Cv fulfills (19), then

CE f -f λ 2 ≤ inf λ∈{L,MS,Cv} inf g∈F λ f -g 2 + B λ ,
where F λ stands for F Λ when Λ = Λ λ .

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Selecting among linear estimator

In this section, we consider the situation where the estimators f λ are linear, that is, are of the form f λ = A λ Y for some known and deterministic n×n matrix A λ . As mentioned before, this setting covers many popular estimation procedures including kernel ridge estimators, spline smoothing, Nadaraya estimators, λ-nearest neighbors, projection estimators, low-pass filters, etc. In some cases A λ is symmetric (e.g. kernel ridge, spline smoothing, projection estimators), in some others A λ is non-symmetric and non-singular (as for Nadaraya estimators) and sometimes A λ can be both singular and nonsymmetric (low pass filters, λ-nearest neighbors). A common feature of those procedures lies in the fact that they depend on a tuning parameter (possibly multidimensional) and their practical performances can be quite poor if this parameter is not suitably calibrated. A series of papers have investigated the calibration of some of these procedures. To mention a few of them, [START_REF] Cao | On oracle inequalities related to smoothing splines[END_REF] focus on spline smoothing, [START_REF] Zhang | Learning bounds for kernel regression using effective data dimensionality[END_REF] on kernel ridge regression, [START_REF] Goldenshluger | Structural adaptation via L p -norm oracle inequalities[END_REF] on kernel estimators and [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] propose a procedure to select among symmetric linear estimator with spectrum in [0, 1]. The procedure we present can handle all these cases in an unified framework. Throughout the section, we assume that Λ is finite.

The families S λ

To apply our selection procedure, we need to associate to each A λ a suitable collection of approximation spaces S λ . To do so, we introduce below a linear space S λ which plays a key role in our analysis.

For the sake of simplicity, let us first consider the case where A λ is nonsingular. Then S λ is defined as the linear span of the right-singular vectors of A -1 λ -I associated to singular values smaller than 1. When A λ is symmetric, S λ is merely the linear span of the eigenvectors of A λ associated to eigenvalues not smaller than 1/2. If none of the singular values are smaller than 1, then S λ = {0}.

Let us now extend the definition of S λ to singular operators A λ . Let us recall that R n = ker(A λ ) ⊕ rg(A * λ ) where A * λ stands for the transpose of A λ and rg(A * λ ) for its range. The operator A λ then induces a one to one operator between rg(A * λ ) and rg(A λ ). Write A + λ for the inverse of this operator from rg(A λ ) to rg(A * λ ). The orthogonal projection operator from R n onto rg(A * λ ) induces a linear operator from rg(A λ ) into rg(A * λ ), denoted Π λ . Then S λ is defined as the linear span of the right-singular vectors of A + λ -Π λ associated to singular values smaller than 1. Again if this set is empty, S λ = {0}. When A λ is non-singular or symmetric, we recover the definition of S λ given above.

For each λ ∈ Λ, take S λ such that S λ ⊃ {S λ }. From a theoretical point of view, it is enough to take S λ = {S λ } but practically it may be wise to use a larger set and by doing so, to possibly improve the approximation of f λ by elements of S λ . One may for example take S λ = S 1 λ , . . . , S n-2 λ where S k λ is the linear span of the right-singular vectors associated to the k smallest singular values of A + λ -Π λ .

Choices of S, ∆ and pen

Take S = λ∈Λ S λ and ∆ of the form

∆(S) = a (1 ∨ dim(S)) for all S ∈ S
where a ≥ 1 satisfies Assumption 2 with Σ ≤ 1. One may take a = (log |Λ|)∨1 even though this choice is not necessarily the best. Finally, for some K > 1, take pen(S) = Kpen ∆ (S) for all S ∈ S and select f λ by minimizing the criterion given by ( 6), taking thus δ = 0 in (9).

An oracle-type inequality for linear estimators

The following holds.

Corollary 2. Let K > 1, κ ∈ (0, 1) and α > 0. If Assumption 1 holds and ∆(S) ≤ κn for all S ∈ S, the estimator f λ satisfies

Ca -1 E f -f λ 2 ≤ inf λ E f -f λ 2 + σ 2 ,
for some C depending on K, α and κ only.

The problem of selecting some best linear estimator among a family of those have also been considered in [START_REF] Arlot | Data-driven calibration of linear estimators with minimal penalties[END_REF] framework, and in [START_REF] Goldenshluger | Structural adaptation via L p -norm oracle inequalities[END_REF] in the multidimensional Gaussian white noise model. Arlot and Bach proposed a penalized procedure based on random penalties. Unlike ours, their approach requires that the operators be symmetric with eigenvalues in [0, 1] and that the cardinality of Λ is at most polynomial with respect to n. Goldenshluger and Lepski proposed a selection rule among families of kernel estimators to solve the problem of structural adaptation. Their approach requires suitable assumptions on the kernels while ours requires nothing. Nevertheless, we restrict to the case of the Euclidean loss whereas Goldenshluger and Lepski considered more general L p ones.

Variable selection

Throughout this section, we consider the problem of variable selection introduced in Example 2 and assume that p ≥ 2 in order to avoid trivialities. When p is small enough (say smaller than 20), this problem can be solved by using a suitable variable selection procedure that explores all the subsets of {1, . . . , p}. For example, one may use the penalized criterion introduced in [START_REF] Birgé | Gaussian model selection[END_REF] when the variance is known, and the one in [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF] when it is not. When p is larger, such an approach can no longer be applied since it becomes numerically intractable. To overcome this problem, algorithms based on the minimization of convex criteria have been proposed among which are the Lasso, the Dantzig selector of [START_REF] Candès | The Dantzig selector: statistical estimation when p is much larger than n[END_REF], the elastic net of [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF]. An alternative to those criteria is the forward-backward algorithm described in [START_REF] Zhang | Adaptive forward-backward greedy algorithm for learning sparse representations[END_REF], among others. Since there seems to be no evidence that one of these procedures outperforms all the others, it may be reasonable to mix them all and let the data decide which is the more appropriate to solve the problem at hand. As enlarging F can only improve the risk bound of our estimator, only the CPU resources should limit the number of candidate estimators.

The procedure we propose could not only be used to select among those candidate procedures but also to select the tuning parameters they depend on. From this point of view, it provides an alternative to the cross-validation techniques which are quite popular but offer little theoretical guarantees.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Implementation roadmap

Start by choosing a family L of variable selection procedures. Examples of such procedures are the Lasso, the Dantzig selector, the elastic net, among others. If necessary, associate to each ℓ ∈ L a family of tuning parameters H ℓ . For example, in order to use the Lasso procedure one needs to choose a tuning parameter h > 0 among a grid H Lasso ⊂ R + . If a selection procedure ℓ requires no choice of tuning parameters, then one may take H ℓ = {0}. Let us denote by m(ℓ, h) the subset of {1, . . . , p} corresponding to the predictors selected by the procedure ℓ for the choice of the tuning parameter h. For m ⊂ {1, . . . , p}, let S m be the linear span of the column vectors X .,j for j ∈ m (with the convention S ∅ = {0}). For ℓ ∈ L and h ∈ H ℓ , associate to the subset m(ℓ, h) an estimator f (ℓ,h) of f with values in S m(ℓ,h) (one may for example take the projection of Y onto the random linear space S m(ℓ,h) but any other choice would suit). Finally, consider the family F = { f λ , λ ∈ Λ} of these estimators by taking Λ = ℓ∈L ({ℓ}×H ℓ ) and set M = { m(λ), λ ∈ Λ}. All along we assume that Λ is finite (so that we take δ = 0 in ( 9)).

The approximation spaces and the weight function

Throughout, we shall restrict ourselves to subsets of predictors with cardinality not larger than some D max ≤ n -2. In view of approximating the estimators f λ , we suggest the collection S given by

S = S m m ⊂ {1, . . . , p} , card(m) ≤ D max . (26)
We associate to S the weight function ∆ defined for S ∈ S by

∆(S) = log p D + log(1 + D) with D = dim(S). ( 27
)
Since Assumption 2 is satisfied with Σ = 1 + log(1 + p).

Let us now turn to the choices of the S λ ⊂ S. The criterion given by ( 6) cannot be computed when S λ = S for all λ as soon as p is too large. In such a case, one must consider a smaller subset of S and we suggest for

λ = (ℓ, h) ∈ Λ S (ℓ,h) = S m(ℓ,h ′ ) , h ′ ∈ H ℓ
(where the S m are defined above), or preferably

S (ℓ,h) = S m(ℓ ′ ,h ′ ) , ℓ ′ ∈ L, h ′ ∈ H ℓ
whenever this latter family is not too large. Note that these two families are random.

The results

Our choices of ∆ and S λ ensure that f λ ∈ S m(λ) ∈ S λ for all λ ∈ Λ and that

∆(S m(λ) ) ≤ 2 dim(S m(λ) ) log p.
Hence, by applying Corollary 1 with S λ = S m(λ) , we get the following result.

Corollary 3. Let K > 1, κ ∈ (0, 1) and D max be some positive integer satisfying D max ≤ κn/(2 log p). Let M = { m(λ), λ ∈ Λ} be a (finite) collection of random subsets of {1, . . . , p} with cardinality not larger than D max based on the observation Y and { f λ , λ ∈ Λ} a family of estimators f , also based on Y , such that f λ ∈ S m(λ) . By applying our selection procedure, the resulting estimator

f λ satisfies CE f -f λ 2 ≤ inf λ∈Λ E f -f λ 2 + E dim(S m(λ) ) log(p)σ 2 ,
where C is a constant depending on the choices of K and κ only.

Again, note that the risk bound we get is non-increasing with respect to Λ. This means that if one adds a new variable selection procedure or considers more tuning parameters to increase Λ, the risk bound we get can only be improved.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Without additional information on the estimators

f λ it is difficult to com- pare E dim(S m(λ) ) σ 2 and E f -f λ 2 . If f λ is of the form Π S Y for some deterministic subset S ∈ S it is well-known that E f -Π S Y 2 = f -Π S f 2 + dim(S)σ 2 ≥ dim(S)σ 2 .
Under the assumption that f ∈ S m * and that m * belongs to M with probability close enough to 1, we can compare the risk of the estimator f λ to the cardinality of m * .

Corollary 4. Assume that the assumptions of Corollary 3 hold and that f λ = Π S m(λ) Y for all λ ∈ Λ. If f ∈ S m * for some non-void subset m * ⊂ {1, . . . , p} with cardinality not larger than D max , then

CE f -f λ 2 ≤ log(p)|m * |σ 2 + R n (m * )
where C is a constant depending on K and κ only, and

R n (m * ) = ( f 2 + nσ 2 ) P m * ∈ M 1/2
. Zhao and You (2006) gives sufficient conditions on the design X to ensure that P m * ∈ M is exponentially small with respect to n when the family M is obtained by using the LARS-Lasso algorithm with different values of the tuning parameter.

Simulation study

In the linear regression setting described in Example 2, we carry out a simulation study to evaluate the performances of our procedure to solve the two following problems.

We first consider the problem, described in Example 3, of tuning the smoothing parameter of the Lasso procedure for estimating f . The performances of our procedure are compared with those of the V -fold cross-validation method. Secondly, we consider the problem of variable selection. We solve it by using our criterion in view of selecting among a family L of candidate variable selection procedures.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Our simulation study is based on a large number of examples which have been chosen in view of covering a large variety of situations. Most of these have been found in the literature in the context of Example 2 either for estimation or variable selection purposes when the number p of predictors is large.

The section is organized as follows. The simulation design is given in the following section. Then, we describe how our procedure is applied for tuning the Lasso and performing variable selection. Finally, we give the results of the simulation study.

Simulation design

One example is determined by the number of observations n, the number of variables p, the n × p matrix X, the values of the parameters β, and the ratio signal/noise ρ. It is denoted by ex(n, p, X, β, ρ), and the set of all considered examples is denoted E. For each example, we carry out 400 simulations of Y as a Gaussian random vector with expectation f = Xβ and variance σ 2 I n , where I n is the n × n identity matrix, and

σ 2 = f 2 /nρ.
The collection E is composed of several collections E e for e = 1, . . . , E where each collection E e is characterized by a vector of parameters β e , and a set X e of matrices X: E e = {ex(n, p, X, β, ρ) : (n, p) ∈ I, X ∈ X e , β = β e , ρ ∈ R} where R = {5, 10, 20} and I consists of pairs (n, p) such that p is smaller, equal or greater than n. The examples are described in further details in Section 8.2. They are inspired by examples found in [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF], [START_REF] Zou | The adaptive lasso and its oracle properties[END_REF][START_REF] Huang | Adaptive Lasso for sparse highdimensional regression models[END_REF] for comparing the Lasso method to the ridge, adaptive Lasso and elastic net methods. They make up a large variety of situations. They include cases where

• the covariates are not, moderately or strongly correlated,

• the covariates with zero coefficients are weakly or highly correlated with covariates with non-zero coefficients, • the covariates with non-zero coefficients are grouped and correlated within these groups, • the lasso method is known to be inconsistent, • few or many effects are present.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Tuning a smoothing parameter

We consider here the problem of tuning the smoothing parameter of the Lasso estimator as described in Example 3. Instead of considering the Lasso estimators for a fixed grid Λ of smoothing parameters λ, we rather focus on the sequence { f 1 , . . . , f Dmax } of estimators given by the D max first steps of the LARS-Lasso algorithm proposed by [START_REF] Efron | Least angle regression[END_REF]. Hence, the tuning parameter is here the number h ∈ H = {1, . . . , D max } of steps. In our simulation study, we compare the performance of our criterion to that of the V -fold cross-validation for the problem of selecting the best estimator among the collection F = { f 1 , . . . , f Dmax }.

The estimator of f based on our procedure

We recall that our selection procedure relies on the choices of families S, S h for h ∈ H, a weight function ∆, a penalty function pen and two universal constants K > 1 and α > 0. We choose the family S defined by ( 26). We associate to f h the family S h = {S m(h ′ ) | h ′ ∈ H} ⊂ S where the S m are defined in Section 5.1 and m(h ′ ) ⊂ {1, . . . , p} is the set of indices corresponding to the predictors retuned by the LARS-Lasso algorithm at step h ′ ∈ H. We take pen(S) = Kpen ∆ (S) with ∆(S) defined by ( 27) and K = 1.1. This value of K is consistent with what is suggested in [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF]. The choice of α is based on the following considerations. First, choosing α around one seems reasonable since it weights similarly the term Y -Π S f λ 2 which measures how well the estimator fits the data and the approximation term f λ -Π S f λ 2 involved in our criterion (6). Second, simple calculation shows that the constant C -1 = C -1 (1.1, α) involved in Theorem 1 is minimum for α close to 0.6. We therefore carried out our simulations for α varying from 0.2 to 1.5. The results being very similar for α between 0.5 and 1.2, we choose α = 0.5. We denote by f pen ∆ the resulting estimator of f .

The estimator of f based on V -fold cross-validation

For each h ∈ H, the prediction error is estimated using a V -fold crossvalidation procedure, with V = n/10. The estimator f CV is chosen by minimizing the estimated prediction error.

The results

The simulations were carried out with R (www.r-project.org) using the library elasticnet.

For each example ex ∈ E, we estimate on the basis of 400 simulations the oracle risk

O ex = E min h∈H f -f h 2 , ( 28
)
and the Euclidean risks R ex ( f pen ∆ ) and R ex ( f CV ) of f pen ∆ and f CV respectively.

The results presented in Table 1 show that our procedure tends to choose a better estimator than the CV in the sense that the ratios R ex ( f pen ∆ )/O ex are closer to one than R ex ( f CV )/O ex .

Nevertheless, for a few examples these ratios are larger for our procedure than for the CV. These examples correspond to situations where the Lasso estimators are highly biased.

In practice, it is worth considering several estimation procedures in order to increase the chance to have good estimators of f among the family F. Selecting among candidate procedures is the purpose of the following simulation experiment in the variable selection context.

Variable selection

In this section, we consider the problem of variable selection and use the procedure and notations introduced in Section 5. L × H ℓ } of such random sets, we consider the family

F = { f m(ℓ,h) | (ℓ, h) ∈ L × H ℓ }.
The descriptions of L and H ℓ are postponed to Section 8.3. Let us merely mention that we choose L which gathers variable selection procedures based on the Lasso, ridge regression, Elastic net, PLS1 regression, Adaptive Lasso, Random Forest, and on an exhaustive research among the subsets of {1, . . . , p} with small cardinality. For each procedure ℓ, the parameter set H ℓ corresponds to different choices of tuning parameters. For each λ = (ℓ, h) ∈ L × H ℓ , we take S λ = {S m(ℓ,h) } so that our selection rule over F amounts to minimizing over M

crit(m) = Y -Π Sm Y 2 + K pen ∆ (S m ) σ 2 Sm , (29)
where pen ∆ is given by (3).

Results

The simulations were carried out with R (www.r-project.org) using the libraries elasticnet, randomForest, pls and the program lm.ridge in the library MASS. We first select the tuning parameters associated to the procedures ℓ in L. More precisely, for each ℓ we select an estimator among the collection

F ℓ = { f m(ℓ,h) | h ∈ H ℓ } by minimizing Criterion (29) over M ℓ = { m(ℓ, h)|h ∈ H ℓ }.
We denote by m(ℓ) the selected set and by f m(ℓ) the corresponding projection estimator. For each example ex ∈ E and each method ℓ ∈ L, we estimate the risk

R ex,ℓ = E f -f m(ℓ) 2 of f m(ℓ)
on the basis of 400 simulations and we do the same to calculate that of our estimator

f m , R ex,all = E f -f m 2 .
Let us now define the minimum of these risks over all methods:

R ex,min = min {R ex,all , R ex,ℓ , ℓ ∈ L} .

We compare the ratios R ex,ℓ /R ex,min for ℓ ∈ L ∪ {all} to judge the performances of the candidate procedures on each example ex ∈ E. 3 False dicovery rate (FDR) and true discovery rate (TDR) using our method, for each example with ρ = 10 and n = p = 100.

• none of the procedures ℓ in L outperforms all the others simultaneously over all examples, • our procedure, corresponding to ℓ = all, achieves the smallest mean value. Besides, this value is very close to one. • the variability of our procedure is small compared to the others • for all examples, our procedure selects an estimator the risk of which does not exceed twice that of the oracle.

The false discovery rate (FDR) and the true discovery rate (TDR) are also parameters of interest in the context of variable selection. These quantities are given at Table 3 for each example when ρ = 10 and n = p = 100. Except for one example, the FDR is small, while the TDR is varying a lot among the examples. Throughout this section, we use the following notations. For all λ ∈ Λ and S ∈ S λ , we write

crit α ( f λ , S) = Y -Π S f λ 2 + σ 2 pen(S) + α f λ -Π S f λ 2 ,
where pen(S) = pen(S) σ 2 S /σ 2 , for all S ∈ S.

For all λ ∈ Λ, let S(λ) ∈ S λ be such that

crit α ( f λ , S(λ)) ≤ crit α ( f λ ) + δ.
We also write ε = Yf and S for the linear space generated by S and f . It follows the facts that for all λ ∈ Λ and

S ∈ S λ crit α ( f λ , S( λ)) ≤ crit α ( f λ ) + δ ≤ crit α ( f λ ) + 2δ ≤ crit α ( f λ , S)+2δ
and simple algebra that

f -Π S( λ) f λ 2 + α f λ -Π S( λ) f λ 2 ≤ f -Π S f λ 2 + α f λ -Π S f λ 2 + 2σ 2 pen(S) + 2δ + 2 ε, Π S( λ) f λ -f -σ 2 pen(S( λ)) + 2 ε, f -Π S f λ -σ 2 pen(S).
imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

For λ ∈ Λ and S ∈ S, let us set

u λ,S = Π S f λ -f / Π S f λ -f if Π S f λ = f
and u λ,S = 0 otherwise. For all λ and S, we have u λ,S ∈ S and

f -Π S( λ) f λ 2 + α f λ -Π S( λ) f λ 2 ≤ f -Π S f λ 2 + α f λ -Π S f λ 2 + 2σ 2 pen(S)+2δ + 2 ε, u λ,S( λ) Π S( λ) f λ -f -σ 2 pen(S( λ)) + 2 | ε, u λ,S | Π S f λ -f -σ 2 pen(S) ≤ f -Π S f λ 2 + α f λ -Π S f λ 2 + 2σ 2 pen(S)+2δ + K -1 f -Π S( λ) f λ 2 + K Π S( λ) ε 2 -σ 2 pen(S( λ)) + K -1 f -Π S f λ 2 + K Π S ε 2 -σ 2 pen(S)
Hence, by using ( 5) and (30) we get

(1 -K -1 ) f -Π S( λ) f λ 2 + α f λ -Π S( λ) f λ 2 ≤ (1 + K -1 ) f -Π S f λ 2 + α f λ -Π S f λ 2 + 2σ 2 pen(S) + Σ+2δ ≤ 2(1 + K -1 ) f -f λ 2 +2δ + α + 2(1 + K -1 ) f λ -Π S f λ 2 + 2σ 2 pen(S) + Σ (31)
where

Σ = 2K S∈S Π S ε 2 - pen ∆ (S) n -dim(S) Y -Π S Y 2 + . For each S ∈ S, Y -Π S Y 2 n -dim(S) ≥ Y -Π S Y 2 n -dim(S)
and since the variable Y -Π S Y 2 is independent of Π S ε 2 and is stochastically larger than ε -Π S ε 2 , we deduce from the definition of pen ∆ (S) and (2), that on the one hand E( Σ) ≤ 2Kσ 2 Σ.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

On the other hand, since S is arbitrary among S λ and since

1 α + 1 1 -K -1 -1 f -f λ 2 ≤ (1-K -1 ) f -Π S( λ) f λ 2 +α f λ -Π S( λ) f λ 2 we deduce from (31) that for all λ ∈ Λ, f -f λ 2 ≤ C -1 f -f λ 2 + A( f λ , S λ ) + Σ + δ (32)
with

C -1 = C -1 (K, α) = (1 + α -K -1 ) (α + 2(1 + K -1 )) α(1 -K -1 ) , (33)
and ( 11) follows by taking the expectation on both sides of (32). Note that provided that

inf λ∈Λ f -f λ 2 + A( f λ , S λ )
is measurable, we have actually proved the stronger inequality

CE f -f λ 2 ≤ E inf λ∈Λ f -f λ 2 + A( f λ , S λ ) + σ 2 Σ + δ. (34)
Let us now turn to the second part of the Theorem, fixing some λ ∈ Λ. Since equality holds in (5), under Assumption 3 by ( 4)

pen(S) = Kpen ∆ (S) ≤ C(κ, K)(dim(S) ∨ ∆(S)), ∀S ∈ S.
If S λ is non-random, for some C ′ = C ′ (κ, K) > 0 and all S ∈ S λ , and under Assumption 3, (dim(S) ∨ ∆(S))/(ndim(S)) ≤ κ(1κ) -1 , and hence for all S ∈ S λ

C ′ E A( f λ , S λ ) ≤ E f λ -Π S f λ 2 + (dim(S) ∨ ∆(S))E σ 2 S , = E f λ -Π S f λ 2 + dim(S) ∨ ∆(S) n -dim(S) f -Π S f 2 + (n -dim(S))σ 2 . Since f -Π S f 2 ≤ f -Π S f λ 2 , we have f -Π S f 2 ≤ E f -Π S f λ 2 ≤ 2E f -f λ 2 + 2E f λ -Π S f λ 2 , imsart-
C ′ E A( f λ , S λ ) ≤ 1 + 2κ 1 -κ E f -f λ 2 + 2κ 1 -κ E f λ -Π S f λ 2 + (dim(S) ∨ ∆(S)) σ 2 .
which leads to (12).

Let us turn to the proof of ( 13). We set

σ 2 λ = σ 2 S λ
. Since with probability

one f λ ∈ S λ ∈ S λ , E A( f λ , S λ ) ≤ E pen( S λ ) σ 2 λ
and it suffices thus to bound the right-hand side. Since equality holds in ( 5) and since

f λ ∈ S λ pen( S λ ) σ 2 λ = K pen ∆ ( S λ ) n -dim( S λ ) Y -Π S λ Y 2 ≤ K pen ∆ ( S λ ) n -dim( S λ ) Y -f λ 2 = K pen ∆ ( S λ ) n -dim( S λ ) f + ε -f λ 2 ≤ 2K pen ∆ ( S λ ) n -dim( S λ ) f -f λ 2 + ε 2 ≤ 2K pen ∆ ( S λ ) n -dim( S λ ) f -f λ 2 + ( ε 2 -2nσ 2 ) + + 2nσ 2 .
Under Assumption 3, 1 ≤ ∆( S λ ) ∨ dim( S λ ) ≤ κn and we deduce from (4) that for some constant C depending only on K and κ

C pen( S λ ) σ 2 λ ≤ f -f λ 2 + dim( S λ ) ∨ ∆( S λ ) σ 2 + ( ε 2 -2nσ 2 ) + ,
and the result follows from the fact that E[( ε 2 -2nσ 2 ) + ] ≤ 3σ 2 for all n.

Proof of Proposition 1

For all λ ∈ Λ and f ∈ S, ff λ ≥ Π S f λf λ and hence,

f -f λ 2 ≥ inf λ∈Λ f -f λ 2 ≥ 1 2 inf λ∈Λ f -f λ 2 + Π S f λ -f λ 2 .
imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Besides, since the minimax rate of estimation over S is of order dim(S)σ 2 , for some universal constant C,

C sup f ∈S E f -f λ 2 ≥ dim(S)σ 2 .
Putting these bounds together lead to the result.

Proof of Proposition 2

Under (24), it is not difficult to see that d(n, M) = n/(2 log(eM)) ≥ 2 so that S is not empty and since for all

S m ∈ S Cv (dim(S m ) ∨ 1) ≤ ∆(S m ) = |m| + log M |m| ≤ |m|(1 + log M) ≤ n 2 ,
Assumptions 1 to 4 are satisfied with κ = 1/2. Besides, the set Λ Cv being compact, λ → crit α (f λ ) admits a minimum over Λ Cv (we shall come back the minimization of this criterion at the end of the subsection) and hence we can take δ = 0. By applying Theorem 1 and using ( 12), the resulting estimator f Cv = f λ satisfies for some universal constant C > 0

CE f -f Cv 2 ≤ inf g∈F Λ f -g 2 + A(g, S) , (35)
where

A(g, S) = inf S∈S g -Π S g 2 + (dim(S) ∨ ∆(S)) σ 2 . ( 36
)
We bound A(g, S) from above by using the following approximation result below the proof of which can be found in [START_REF] Makovoz | Random approximants and neural networks[END_REF] (more precisely, we refer to the proof of his Theorem 2).

Lemma 1. For all g in the convex hull F Λ of the φ j and all D ≥ 1, there exists m ⊂ {1, . . . , M} such that |m| = (2D) ∧ M and g -Π Sm g 2 ≤ 4D

A(g, S) ≤ C ′ nL 2 log(eM/ √ nL 2 )σ 2 (37)
for some universal constant C ′ > 0 which together with (35) leads to the risk bound

E f -f Cv 2 -C inf g∈F Λ f -g 2 ≤ C nL 2 log(eM/ √ nL 2 )σ 2 .
Concerning the computation of f Cv , note that inf

λ∈Λ crit α (f λ ) = inf λ∈Λ inf S∈S Cv Y -Π S f λ 2 + α f λ -Π S f λ 2 + pen(S) σ 2 S = inf S∈S Cv inf λ∈Λ Y -Π S f λ 2 + α f λ -Π S f λ 2 + pen(S) σ 2 S ,
and hence, one can solve the problem of minimizing crit α (f λ ) over λ ∈ Λ by proceeding into two steps. First, for each S in the finite set S Cv minimize the convex criterion By applying Theorem 1, we obtain that the selected estimator f λ satisfies

crit α (S, f λ ) = Y -Π S f λ 2 + α f λ -Π S f λ
CE f -f λ 2 ≤ inf λ∈{L,MS,Cv} E f -f λ 2 + E A( f λ , S λ ) .
Let us now bound E A( f λ , S λ ) for each λ ∈ Λ.

If λ = L, by using ( 12) and the fact that f L ∈ S {1,...,M } , we have

C ′ E A( f L , S L ) ≤ E f -f L 2 + Mσ 2 .
If λ = MS, we may use ( 13) since with probability one f MS ∈ S MS and since dim(S) ∨ ∆(S) ≤ 1 + log(M) for all S ∈ S MS , we get

C ′ E A( f MS , S MS ) ≤ E f -f MS 2 + log(M)σ 2 .
Finally, let us turn to the case λ = Cv and denote by g the best approximation of f in C. Since f Cv ∈ C, for all S ∈ S Cv ,

f Cv -Π S f Cv ≤ f Cv -Π S g = f Cv -f + f -g + g -Π S g ≤ 2 f -f Cv + g -Π S g ,
and hence by using ( 12)

C ′ E A( f Cv , S Cv ) ≤ E f -f Cv 2 + A(g, S Cv )
where A(g, S Cv ) is given by (36). By arguing as in Section (3.1.3), we deduce that under (24)

C ′ E A( f Cv , S Cv ) ≤ E f -f Cv 2 + nL 2 log(eM/ √ nL 2 )σ 2 .
By putting these bounds together we get the result.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

Proof of Corollary 2

Since Assumptions 1 to 4 are fulfilled and F is finite, we may apply Theorem 1 and take δ = 0. By using ( 12), we have for some C depending on K, α and κ,

CE f -f λ 2 ≤ inf λ∈Λ E f -f λ 2 + E f λ -Π S λ f λ 2 + a(1 + dim(S λ ))σ 2 .
For all λ ∈ Λ,

E f -f λ 2 = f -A λ f 2 + E A λ ε 2 = f -A λ f 2 + Tr(A * λ A λ )σ 2 ≥ max f -A λ f 2 , Tr(A * λ A λ )σ 2 and E f λ -Π S λ f λ 2 = (I -Π S λ )A λ f 2 + E (I -Π S λ )A λ ε 2 , ≤ 2 max (I -Π S λ )A λ f 2 , E A λ ε 2 = 2 max (I -Π S λ )A λ f 2 , Tr(A *
λ A λ )σ 2 and hence, Corollary 2 follows from the next lemma.

Lemma 2. For all λ ∈ Λ we have

(i) (I -Π S λ )A λ f ≤ f -A λ f , (ii) dim(S λ ) ≤ 4 Tr(A * λ A λ ).
Proof of Lemma 2: Writing f = f 0 + f 1 ∈ ker(A λ ) ⊕ rg(A * λ ) and using the fact that rg(A * λ ) = ker(A λ ) ⊥ and the definition of Π λ , we obtain

f -A λ f 2 = f 0 + f 1 -A λ f 1 2 = f 0 -Π ker(A λ ) A λ f 1 2 + (I -Π λ A λ )f 1 2 ≥ (A + λ -Π λ )A λ f 1 2 ≥ m λ k=1 s 2 k < A λ f, v k > 2 ,
imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

where s 1 ≥ . . . ≥ s m λ are the singular values of A + λ -Π λ counted with their multiplicity and (v 1 , . . . , v m λ ) is an orthonormal family of right-singular vectors associated to (s 1 , . . . , s m λ ). If s 1 < 1, then S λ = R n and we have f -A λ f ≥ (I -Π S λ )A λ f = 0. Otherwise, s 1 ≥ 1, we may consider k λ as the largest k such that s k ≥ 1 and derive that

f -A λ f 2 ≥ k λ k=1 s 2 k < A λ f, v k > 2 ≥ k λ k=1 < A λ f, v k > 2 = (I -Π S λ )A λ f 2 ,
which proves the assertion (i).

For the bound (ii), we set M λ = A + λ -Π λ and note that

(M λ -Π λ )(M λ -Π λ ) * = M λ M * λ + Π λ Π * λ -M λ Π * λ -Π λ M * λ induces a semi-positive quadratic form on rg(A * λ ). As a consequence the quadratic form (M λ + Π λ )(M λ + Π λ ) * is dominated by the quadratic form 2(M λ M * λ + Π λ Π * λ ) on rg(A * λ ). Furthermore (M λ + Π λ )(M λ + Π λ ) * = (A + λ )(A + λ ) * = (A * λ A λ ) +
where (A * λ A λ ) + is the inverse of the linear operator L λ : rg(A * λ ) → rg(A * λ ) induced by A * λ A λ restricted on rg(A * λ ). We then have that the quadratic form induced by (A * λ A λ ) + is dominated by the quadratic form

2(A + λ -Π λ )(A + λ -Π λ ) * + 2Π λ Π * λ on rg(A * λ ).
In particular the sequence of the eigenvalues of (A Along the section, we write S * for S m * and S λ for S m(λ) for short. By using (10) with δ = 0 and since Σ ≤ 1 + log(1 + p), we have

* λ A λ ) + is dom- inated by the sequence (2s 2 k + 2) k=1,m λ so Tr(A * λ A λ ) = Tr(L λ ) ≥ m λ k=1 1 2(1 + s 2 k ) ≥ m λ k=k λ +1 1 2(1 + s 2 k ) ≥ dim(S λ )/4,
CE f -f λ 2 ≤ E inf λ∈Λ f -Π S λ Y 2 + pen( S λ ) σ 2 S λ + (1 + log(p + 1))σ 2 ,
for some constant C > 0 depending on K only. Writing B for the event B = m * / ∈ M , we have

E inf λ∈Λ f -Π S λ Y 2 + pen( S λ ) σ 2 S λ ≤ A n + R ′ n where A n = E f -Π S * Y 2 + pen(S * ) σ 2 S * R ′ n = E inf λ∈Λ f -Π S λ Y 2 + pen( S λ ) σ 2 S λ 1 B .
Let us bound A n from above. Note that f -Π S * Y 2 = Π S * ε 2 and σ 2 S * = (I -Π S * )ε 2 /(ndim(S * )) and since dim(S * ) ≤ D max ≤ κn/(2 log p), by using (4) we get

A n ≤ (dim(S * ) + pen(S * ))σ 2 ≤ C ′ (1 + log(p)) dim(S * )σ 2 ,
for some constant C ′ > 0 depending on K and κ only.

Let us now turn

to R ′ n . For all λ ∈ Λ, f -Π S λ Y 2 ≤ f 2 and σ 2 S λ = Y -Π S λ Y 2 n -dim( S λ ) ≤ 2 f 2 + ε 2 n -dim( S λ ) .
Since for all S ∈ S, dim(S) ≤ D max ≤ κn/(2 log p), by using (4) again, there exists some positive constant c depending on K and κ only such that for all λ ∈ Λ, pen( S λ )/(ndim( S λ )) ≤ c and hence,

inf λ∈Λ f -Π S λ Y 2 + pen( S λ )σ 2 S λ 1 B ≤ (1 + 2c) f 2 + ε 2 1 B . Some calculation shows that E f 2 + ε 2 2 ≤ f 2 + 2nσ
pen ∆ (S) = n -dim(S) n -dim(S) -1
EDkhi dim(S) + 1, ndim(S) -1, e -∆(S) dim(S) + 1 .

Therefore, according to the result given in Section 6.1 in [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF], pen ∆ (S) is the solution in x of the equation

e -∆(S) D + 1 = P F D+3,N -1 ≥ x N -1 N(D + 3) -x N -1 N(D + 1) P F D+1,N +1 ≥ x N + 1 N(D + 1) .

Simulated examples

The collection E is composed of several collections E 1 , . generated as n independent centered Gaussian vectors with covariance matrix C. For each e ∈ {1, . . . , 10}, we define a p ×p matrix C e and a p-vector of parameters β e . We denote by X e the set of 5 matrices X simulated as n-i.i.d N p (0, C e ). The collection E e is then defined as follows: Let us now describe the collections E 1 to E 10 .

Collection E 1 The matrix C equals the p × p identity matrix denoted I p . The parameters β satisfy β j = 0 for j ≥ 16, β j = 2.5 for 1 ≤ j ≤ 5, β j = 1.5 for 6 ≤ j ≤ 10, β j = 0.5 for 11 ≤ j ≤ 15.

Collection E 2 the matrix C is such that C jk = r |j-k| , for 1 ≤ j, k ≤ 15 and 16 ≤ j, k ≤ p with r = 0.5. Otherwise C j,k = 0. The parameters β are as in Collection E 1 .

Collection E 3 The matrix C is as in Collection E 2 with r = 0.95, the parameters β are as in Collection E 1 .

Collection E 4 The matrix C is such that C jk = r |j-k| , for 1 ≤ j, k ≤ p, with r = 0.5, the parameters β are as in Collection E 1 .

Collection E 5 the matrix C is as in Collection E 4 with r = 0.95, the parameters β are as in Collection E 1 .

Collection E 6 The matrix C equals I p . The parameters β satisfy β j = 0 for j ≥ 16, β j = 1.5 for j ≤ 15. Collection E 7 The matrix C satisfies C j,k = (1ρ 1 )1l j=k + ρ 1 for 1 ≤, j, k ≤ 3, C j,k = C k,j = ρ 2 for j = 4, k = 1, 2, 3, C j,k = 1l j=k for j, k ≥ 5, with ρ 1 = .39 and ρ 2 = .23. The parameters β satisfy β j = 0 for j ≥ 4, β j = 5.6 for j ≤ 3.

Collection E 8 The matrix C satisfies C j,k = 0.5 |j-k| for j, k ≤ 8, C j,k = 1l j=k for j, k ≥ 9. The parameters β satisfy β j = 0 for j ∈ {1, 2, 5},

β 1 = 3, β 2 = 1.5, β 5 = 2.
Collection E 9 The matrix C is defined as in Example E 8 . The parameters β satisfy β j = 0 for j ≥ 9, β j = 0.85 for j ≤ 8.

Collection E 10 The matrix C satisfies C j,k = 0.51l j =k + 1l j=k for j, k ≤ 40, C j,k = 1l j=k for j, k ≥ 41. The parameters β satisfy β j = 2 for 11 ≤ j ≤ 20 and 31 ≤ j ≤ 40, β j = 0 otherwise.

Collection E 11 In this last example, we denote by X 11 the set of 5 matrices X simulated as follows. For 1 ≤ j ≤ p, we denote by X j the column j of X.

Let E be generated as n i.i.d. N p (0, 0.01I p ) and let Z 1 , Z 2 , Z 3 be generated as n i.i.d. N 3 (0, I 3 ). Then for j = 1, . . . , 5, X j = Z 1 + E j , for j = 6, . . . , 10, X j = Z 2 + E j , for j = 11, . . . , 15, X j = Z 3 + E j , for j ≥ 16, X j = E j . The parameters β are as in Collection E 6 . The collection E 11 is defined as the set of examples ex(n, p, X, β, ρ) for (n, p) ∈ I, X ∈ X 11 , and ρ ∈ R.

The collection E is thus composed of 660 examples for I chosen as in (39), and 825 for I chosen as in (38). For some of the examples, the Lasso estimators were highly biased leading to high values of the ratio O ex /nσ The Lasso procedure is described in Section 6.2. The collection M Lasso = { m(1), . . . , m(D max )} where m(h) is the set of indices corresponding to the predictors returned by the LARS-Lasso algorithm at step h ∈ {1, . . . , D max } (see Section 6.2).

The ridge procedure is based on the minimization of Y -Xβ 2 +h β 2 with respect to β, for some positive h, see for example [START_REF] Hoerl | Ridge regression[END_REF]. [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] noted that in the case of a large number of small effects, ridge regression gives better results than the lasso for variable selection. For each h ∈ H ridge , the regression coefficients β(h) are calculated and a collection of predictors sets is built as follows. Let j 1 , . . . j p be such that | β j 1 (h)| > . . . > | β jp (h)| and set M h = {{j 1 , . . . , j k }, k = 1, . . . , D max } .

Then, the collection M ridge is defined as M ridge = {M h , h ∈ H ridge }.

The elastic net procedure proposed by [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF] mixes the ℓ 1 and ℓ 2 penalties of the Lasso and the ridge procedures. Let H ridge be a grid of values for the tuning parameter h of the ℓ 2 penalty. We choose M en = {M (en,h) : h ∈ H ridge } where M (en,h) denotes the collection of the active sets of cardinality less than D max , selected by the elastic net procedure when the ℓ 2smoothing parameter equals h. For each h ∈ H ridge the collection M (en,h) can be conveniently computed by first calculating the ridge regression coefficients and then applying the LARS-lasso algorithm, see [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF].

The partial least squares regression (PLSR1) aims to reduce the dimensionality of the regression problem by calculating a small number of components that are usefull for predicting Y . Several applications of this procedure for analysing high-dimensional genomic data have been reviewed by [START_REF] Boulesteix | Partial least squares: a versatile tool for the analysis of high-dimensional genomic data[END_REF]. In particular, it can be used for calculating subsets of covariates as we did for the ridge procedure. The PLSR1 procedure constructs, for a given h, uncorrelated latent components t 1 , . . . , t h that are highly correlated with the response Y , see [START_REF] Helland | Partial least squares regression[END_REF]. Let H pls be a grid a values for the tuning parameter h. For each h ∈ H pls , we write β(h) for the PLS regression coefficients calculated with the first h components. We then imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 set M PLS = {M h : h ∈ H pls }, where M h is build from β(h) as for the ridge procedure.

The adaptive lasso procedure proposed by [START_REF] Zou | The adaptive lasso and its oracle properties[END_REF] starts with a preliminary estimator β. Then one applies the lasso procedure replacing the parameters |β j |, j = 1, . . . , p in the ℓ 1 penalty by the weighted parameters |β j |/| βj | γ , j = 1, . . . , p for some positive γ. The idea is to increase the penalty for coefficients that are close to zero, reducing thus the bias in the estimation of f and improving the variable selection accuracy. Zou showed that, if β is a √ n-consistent estimator of β, then the adaptive lasso procedure is consistent in situations where the lasso is not. A lot of work has been done around this subject, see [START_REF] Huang | Adaptive Lasso for sparse highdimensional regression models[END_REF] for example.

We apply the procedure with γ = 1, and considering two different preliminary estimators:

-using the ridge estimator, β(h) as preliminary estimator. For each h ∈ H ridge , the adaptive lasso procedure is applied for calculating the active sets, M ALridge,h , of cardinality less than D max . The collection M ALridge is thus defined as M ALridge = {M ALridge,h , h ∈ H ridge }.

-using the PLSR1 estimator, β(h), as preliminary estimator. The procedure is the same as described just above. The collection M ALpls is defined as M ALpls = {M ALpls,h , h ∈ H pls }.

The random forest algorithm was proposed by [START_REF] Breiman | Random forests[END_REF] for classification and regression problems. The procedure averages several regression trees calculated on bootstrap samples. The algorithm returns measures of variable importance that may be used for variable selection, see for example Díaz-Uriarte and Alvares de Andrés (2006), [START_REF] Genuer | Variable selection using random forests[END_REF], [START_REF] Strobl | Bias in random forest variable importance measures: Illustrations, sources and a solution[END_REF]2008).

Let us denote by h the number of variables randomly chosen at each split when constructing the trees and H rF = {p/j | j ∈ {3, 2, 1.5, 1}}.

  2.1.3. The weight function ∆ and the associated function pen ∆ We consider a function ∆ from S into R + and assume Assumption 2. Σ = S∈S e -∆(S) < +∞.

e

  -log(1+D) ≤ 1 + log(1 + p), imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

  To solve this problem, we consider estimators of the form f m = Π S m Y where m is a random subset of {1, . . . , p} depending on Y . Given a family M = { m(ℓ, h), m(ℓ, h) ∈ imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

  imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 7. Proofs 7.1. Proof of Theorem 1

2

  over the convex (and compact set) Λ Cv . Denote by f Cv,S the resulting minimizers. Then, minimize the quantity crit α (S, f Cv,S ) + pen(S) σ 2 S for S varying among S Cv . Denoting by S such a minimizer, we have that f Cv = f Cv, S . imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011 7.4. Proof of Proposition 3

E

  e = {ex(n, p, X, β, ρ), (n, p) ∈ I, X ∈ X e , β = β e , ρ ∈ R} where R = {5, 10, 20} and I = {(100, 50), (100, 100), (100, 1000), (200, 100), (200, 200)} (38) in Section 6.2, and I = {(100, 50), (100, 100), (200, 100), (200, 200)} (39) in Section 6.3.

8. 3 .

 3 Procedures for calculating sets of predictorsLet M = ℓ∈L M ℓ where we recall that for ℓ ∈ L, M ℓ = { m(ℓ, h)| h ∈ H ℓ }.

For

  each h ∈ H rF , we consider the set of indicesM h = {{j 1 , . . . , j k }, k = 1, . . . , D max },where {j 1 , . . . , j k } are the ranks of the variable importance measures. Two importance measures are proposed. The first one is based on the decrease in imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

  in the Gaussian regression

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

  Mean, standard-error and quantiles of the ratios R ex /O ex calculated over all ex ∈ E such that O ex < nσ 2 /3. The number of such examples equals 654, see Section 8.2.

						quantiles
	procedure mean std-err	0%	50%	75% 99% 100%
	CV	1.18	0.08 1.05	1.18	1.24 1.36	1.38
	pen ∆ 1.065	0.06 1.01 1.055 1.084 1.18	2.27
				Table 1
	imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

  The mean, standard deviations and quantiles of the sequence {R ex,ℓ /R ex,min , ex ∈ E} are presented in Table2. In particular, the results show that For each ℓ ∈ L ∪ {all}, mean, standard-error and quantiles of the ratios R ex,ℓ /R ex,min calculated over all ex ∈ E. The number of examples in the collection E is equal to 660.

								quantiles
		method	mean std-err 50% 75% 95% 100%
		Lasso	2.82		9.40 1.12 1.33 6.38	127
		ridge	1.76		1.90 1.42 1.82 2.87	36.9
		pls	1.50		1.20 1.22 1.50 2.58	17
		en		1.46		1.90 1.12 1.33 2.57	29
		ALridge	1.20		0.31 1.15 1.26 1.51	5.78
		ALpls	1.29		0.87 1.14 1.29 1.75	12.7
		rFmse	4.13		9.50 1.38 2.04 19.2	118
		rFpurity	3.99		10.00 1.42 2.06 15.1	138
		exhaustive	22.9		45 6.30 24.5 92.9	430
		all		1.16		0.16 1.12 1.25 1.47	1.95
						Table 2
	FDR	E 1 0.045 0.026 0.004 0.026 0.018 0.041 0.012 0.026 0.042 0.15 0.014 E 2 E 3 E 4 E 5 E 6 E 7 E 8 E 9 E 10 E 11
	TDR	0.74	0.63	0.18	0.63	0.17	0.99	1	1	0.98 0.29	0.20
						Table

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

  . . , E 11 that are detailed below. The collections E 1 to E 10 are composed of examples where X is

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

  2 , see Equation(28). We only keep the examples for which the Lasso estimator improves the risk of the naive estimator Y by a factor at least 1/3. This convention leads us to remove 171 examples over 825. These pathological examples are coming from the collections E 1 , E 6 and E 7 for n = 100 and p ≥ 100, and from collections E 2 and E 4 when p = 1000. The examples of collection E 7 were chosen by Zou to illustrate that the Lasso estimators may be highly biased. All the other examples, correspond to matrices X that are nearly orthogonal.

imsart-generic ver. 2010/04/27 file: LinSelect-12-04-2011.tex date: June 21, 2011

the mean square error of prediction after permutation of each of the variables. It leads to the collection M rFmse = {M h , h ∈ H rF }. The second one is based on the decrease in node impurities, and leads similarly to the collection M purity .

The exhaustive procedure considers the collection of all subsets of {1, . . . p} with dimension smaller than D max . We denote this collection M exhaustive .

Choice of tuning parameters

We have to choose D max , the largest number of predictors considered in the collection M. For all methods, except the exhaustive method, D max may be large, say D max ≤ min(n -2, p). Nevertheless, for saving computing time, we chose D max large enough such that the dimension of the estimated subset is always smaller than D max . For the exhaustive method, D max must be chosen in order to make the calculation feasible: D max = 4 for p = 50, D max = 3 for p = 100 and D max = 2 for p = 200.

For the ridge method we choose H ridge = {10 -3 , 10 -2 , 10 -1 , 1, 5}, and for the PLSR1 method, H pls = 1, . . . , 5.