Lucien Birgé

Model selection for density estimation with L 2 -loss

Keywords: AMS 1991 subject classifications. Primary 62G07; secondary 62G10 Density estimation, L2-loss, model selection, estimator selection, histograms

Model selection for density estimation with L2-loss

Introduction 1.Histograms and partition selection

Suppose we have at hand n i.i.d. observations X 1 , . . . , X n with values in the measurable space (X , W) and they have an unknown density s with respect to some probability measure µ on X . The simplest method for finding an estimator of s is to build an histogram. Given a finite partition I = {I 1 , . . . , I k } of X with µ(I j ) = l j > 0 for 1 ≤ j ≤ k, the histogram ŝI based on this partition is defined by ŝI (X 1 , . . . , X n ) = 1 nl j k j=1

N j 1l I j , with N j = n i=1 1l I j (X i ).

β j 1l I j β j ∈ R for 1 ≤ j ≤ k    .
If s ∈ L 2 (µ), then s I is the orthogonal projection of s onto the k-dimensional linear space S I spanned by the functions 1l I j . Choosing the squared L 2 -distance induced by the norm • of L 2 (µ) as our loss function leads to the following quadratic risk for the estimator ŝI :

E ŝI -s 2 = s I -s 2 + 1 n k j=1 p j (1 -p j ) l j .
(1.2) Hence, if s ∈ L ∞ (µ), with norm s ∞ , the quadratic risk of ŝI can be bounded by

E ŝI -s 2 ≤ s I -s 2 + (k -1) s ∞ n , (1.3)
and, as we shall see below, this bound is essentially unimprovable without additional assumptions.

The histogram estimator ŝI is probably the simplest example of a model-based estimator with model S I , i.e. an estimator of s with values in S I . It may acually be viewed as the empirical counterpart of the projection s I of s onto S I .

Suppose now that we are given a finite (although possibly very large) family {I m , m ∈ M} of finite partitions of X with respective cardinalities |I m |, hence the corresponding families of models {S Im , m ∈ M} and histogram estimators {ŝ Im , m ∈ M}. It is natural to try to find one estimator in the family which leads, at least approximately, to the minimal risk inf m∈M E ŝIms 2 . But one cannot select such an estimator from (1.2) or (1.3) since the risk depends on the unknown density s via s Im . Methods of model or estimator selection base the choice of a suitable partition I m with m = m(X 1 , . . . , X n ) on the observations. When s ∈ L ∞ (µ) one would like to know whether it is possible to design a selection procedure m(X 1 , . . . , X n ) leading (at least approximately), in view of (1.3), to a risk bound of the form

E ŝI m -s 2 ≤ C inf m∈M s Im -s 2 + n -1 s ∞ |I m | ,
for some universal constant C, even when s ∞ is unknown.

What is presently known

There exists a considerable amount of litterature dealing with problems of model or estimator selection. Most of it is actually devoted to the analysis of Gaussian problems, or regression problems, or density estimation with either Hellinger or Kullback loss and it is not our aim here to review this litterature. Only a few papers are actually devoted to our subject, namely model or estimator selection for estimating densities with L 2 -loss, and we shall therefore concentrate on these only. These papers can roughly be divided into three groups: the ones dealing with penalized projection estimators, the ones that study aggregation by selection of preliminary estimators and the ones which use methods based on the thresholding of empirical coefficients within a given basis. The last ones are typically not advertised as dealing with model selection but, as explained for instance in Section 5.1.2 of Birgé and [START_REF] Birg É | Gaussian model selection[END_REF], they can be viewed as special instances of model selection methods for models that are spanned by some finite subsets of an orthonormal basis. All these papers have in common the fact that they require more or less severe restrictions on the families of models and, apart from some special cases, typically assume that s ∈ L ∞ (µ) with a known or estimated bound for s ∞ .

In order to see how such methods apply to our problem of partition selection, let us be more specific and assume that X = [0, 1], µ is the Lebesgue measure and N = {j/(N + 1), 1 ≤ j ≤ N } for some (possibly very large) positive integer N . For any subset m of N , we denote by I m the partition of X generated by the intervals with set of endpoints m ∪ {0, 1} and we set S m = S Im and ŝm = ŝIm . This leads to a set M with cardinality 2 N and the corresponding families of linear models S m , m ∈ M and related histogram estimators {ŝ m , m ∈ M}. Then all models S m are linear subspaces of the largest one S N . Of particular interest is the dyadic case with N = 2 K -1 for which S N is the linear span of the 2 K first coefficients of the Haar basis. There is, nevertheless, a difference between expansions in the Haar basis and projections on our family of models. Let us, for instance, consider the function 1l [0,2 -K ) . It belongs to the two-dimensional model S {1} but its expansion in the Haar basis has K non-zero coefficients.

Given a sample X 1 , . . . , X n with unknown density s, which partition I m should we choose to estimate s and what bound could we derive for the resulting estimator? Penalized projection estimators have been considered by Birgé and Massart (1997) and an improved version is to be found in Chapter 7 of [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF]. The method either deals with polynomial collections of models (which does not apply to our case) or with subset selection within a given basis which applies here only when N = 2 K -1 and we use the Haar basis. Moreover, it requires that N < n/ log n and a bound on s I N ∞ be known or estimated, as in Section 4.4.4 of Birgé and [START_REF] Birg É | From model selection to adaptive estimation[END_REF], since the penalty depends on it.

Methods based on wavelet thresholding, as described in Donoho, Johnstone, [START_REF] Donoho | Density estimation by wavelet thresholding Ann[END_REF] or [START_REF] Kerkyacharian | Thresholding algorithms, maxisets and well-concentrated bases[END_REF] (see also the numerous references therein) require the same type of restrictions and, in particular, a control on s ∞ in order to properly calibrate the threshold. Also, as mentioned above, restricting to subsets of the Haar basis may result in expansions that use many more coefficients (K instead of 2, for instance) than needed with the partition selection approach.

Aggregation of estimators by selection assumes that preliminary estimators (one for each model in our case) are given in advance (we should here use the histograms) and typically leads to a risk bound including a term of the form n -1 s ∞ log |M| = n -1 N s ∞ log 2 so that all such results are useless for N ≥ n. Moreover, most of them also require that an upper bound for s ∞ be known since it enters the construction of the aggregate estimator. This is the case in [START_REF] Rigollet | Linear and convex aggregation of density estimators[END_REF] (see for instance his Corollary 2.7) and Juditsky, Rigollet and Tsybakov (2007, Corollary 5.7) since the parameter β that governs their mirror averaging method depends crucially on an upper bound for s ∞ . As to Samarov and Tsybakov (2005), their Assumption 1 requires that N be not larger than C log n. Similar restrictions are to be found in [START_REF] Yang | Mixing strategies for density estimation[END_REF] in his developments for mixing strategies and in [START_REF] Rigollet | Linear and convex aggregation of density estimators[END_REF] for linear aggregation of estimators. [START_REF] Lounici | Aggregation of density estimators for the L π risk with 1 ≤ π < ∞[END_REF] does not assume that s ∈ L ∞ but, instead, that all preliminary estimators are uniformly bounded. One can always truncate the estimators to get this, but to be efficient, the truncation should be adapted to the unknown parameter s, and therefore chosen from the data in a suitable way. We do not know of any paper that allows such a data driven choice.

Consequently, none of these results can solve our partition selection problem in a satisfactory way when N is at least of size n and s ∞ is unknown. This fact was one motivation for our study of model selection for density estimation with L 2 -loss. Results about partition selection will be a consequence of our general treatment of model selection. This treatment allows to consider arbitrary countable families of finite-dimensional models (possibly nonlinear) and does not put any assumption on the density s, apart from the fact that it belongs to L 2 (µ); it may, in particular, be unbounded. We do not know of any result that applies to such a situation. There is a counterpart to this level of generality: our procedure is of a purely abstract nature and not constructive, only indicating what is theoretically feasible. Unfortunately, we are unable to design a practical procedure with similar properties.

Model based estimation and model selection

To begin with, let us fix our framework and notations. We want to estimate an unknown density s, with respect to some probability measure µ on the measurable space (X , W), from an i.i.d. sample X = (X 1 , . . . , X n ) of random variables X i ∈ X with distribution P s = s • µ. Throughout the paper we denote by P s the probability that gives X the distribution P ⊗n s , by E s the corresponding expectation operator and by • q the norm in L q (µ), omitting the subscript when q = 2 for simplicity. We denote by d 2 the distance in L 2 (µ): d 2 (t, u) = tu . For 1 ≤ q ≤ +∞ and Γ > 1, we set

L q = t ∈ L q (µ) t ≥ 0 and t dµ = 1 ; L Γ ∞ = t ∈ L ∞ t ∞ ≤ Γ . (2.1)
We measure the performance at s ∈ L 2 of an estimator ŝ(X) ∈ L 2 by its quadratic risk E s d 2 2 (ŝ(X), s) . More generally, if (M, d) is a metric space of measurable functions on X such that M ∩L 1 = ∅, the quadratic risk of some estimator ŝ ∈ M at s ∈ M ∩L 1 is defined as E s d 2 (ŝ(X), s) . We denote by |I| the cardinality of the set I and set a∨b and a∧b for the maximum and the minimum of a and b, respectively. Throughout the paper C (or C ′ , . . . ) will denote a universal (numerical) constant and C(a, b, . . .) or C q a fonction of the parameters a, b, . . . or q. Both may vary from line to line. Finally, from now on, countable will always mean "finite or countable".

Model based estimation

A common method for estimating s consists in choosing a particular subset S of (M, d) that we shall call a model for s and design an estimator with values in S. Of this type are the maximum likelihood estimator over S or the projection estimator onto S. Let us set M = L 1 and choose for d either the Hellinger distance h or the variation distance v given respectively by

h 2 (t, u) = 1 2 √ t - √ u 2 dµ and v(t, u) = 1 2 |t -u| dµ.
It follows from Le Cam (1973[START_REF] Le | On local and global properties in the theory of asymptotic normality of experiments[END_REF][START_REF] Le | Asymptotic Methods in Statistical Decision Theory[END_REF] and subsequent results by Birgé (1983Birgé ( , 2006a) ) that the risk of suitably designed estimators with values in S is the sum of two terms, an approximation term depending on the distance from s to S and an estimation term depending on the dimension of the model S which can be defined as follows.

Definition 1 Let S be a subset of some metric space (M, d) and let B d (t, r) denote the open ball of center t and radius r with respect to the metric d.

Given η > 0, a subset S η of M is called an η-net for S if, for each t ∈ S, one can find t ′ ∈ S η with d(t, t ′ ) ≤ η.
We say that S has a metric dimension bounded by D ≥ 0 if, for every η > 0, there exists an η-net S η for S such that

|S η ∩ B d (t, xη)| ≤ exp Dx 2
for all x ≥ 2 and t ∈ M.

(2.2)

Remark: One can always assume that S η ⊂ S at the price of replacing D by 25D/4 according to Proposition 7 of Birgé (2006a).

Typical examples of sets with metric dimension bounded by D when (M, d) is a normed linear space are subsets of 2D-dimensional linear subspaces of M as shown in Birgé (2006a). If d is either h or v and S ⊂ L 1 has a metric dimension bounded by D ≥ 1/2, there exists a universal constant C and an estimator ŝ(X) with values in S such that, for any s ∈ L 1 ,

E s d 2 (ŝ(X), s) ≤ C inf t∈S d 2 (s, t) + n -1 D . (2.3)
In particular, sup s∈S E s d 2 (ŝ(X), s) ≤ Cn -1 D. This results from the following theorem about model selection of Birgé (2006a) by setting M = {0}, S 0 = S, D 0 = D and ∆ 0 = 1/2.

Theorem 1 Let X 1 , . . . , X n be an i.i.d. sample with unknown density s belonging to L 1 and S m , m ∈ M a finite or countable family of subsets of L 1 with metric dimensions bounded by D m ≥ 1/2 respectively. Let the nonegative weights

∆ m , m ∈ M satisfy m∈M exp[-∆ m ] = Σ < +∞. (2.4)
Then there exists a universal constant C and an estimator s(X 1 , . . . , X n ) such that, for any s ∈ L 1 ,

E s d 2 (s, s) ≤ C(1 + Σ) inf m∈M inf t∈Sm d 2 (s, t) + n -1 (D m ∨ ∆ m ) .
(2.5)

Unfortunately, as we shall see below, (2.3) does not hold in general when (M, d) = (L 2 (µ), d 2 ). In particular, whatever the estimator ŝ, sup s∈S E s d 2 (ŝ(X), s) may be infinite even if S ⊂ L 2 (µ) has a bounded metric dimension. This difference is due to the following fact: h and v are actually distances defined on the set of all probabilities on (X , W) and h(s, t) = h(P s , P t ) is independent of the choice of the underlying dominating measure, the same property holding for the variation distance v. This is not the case for d 2 which is a distance in L 2 (µ) depending on the choice of µ and definitely not a distance between probabilities. Even the fact that s = dP s /dµ belong or not to L 2 (µ) depends on µ. Further remarks on this subject can be found in Devroye and Györfi (1985) and [START_REF] Devroye | A Course in Density Estimation[END_REF].

Nevertheless, the L 2 -distance has been much more popular in the past than either the Hellinger or variation distances, mainly because of its simplicity due to the classical "squared bias plus variance" decomposition of the risk. Although hundreds of papers have been devoted to the derivation of risk bounds for various specific estimators, we do not know of any general bound for the risk similar to (2.3) based on purely metric considerations for the distance d 2 .

Projection and histogram estimators

To illustrate the specificity of the L 2 -risk, let us turn to a quite classical family of model-based estimators for densities, the projection estimators of [START_REF] Cencov | Evaluation of an unknown distribution density from observations[END_REF]. To estimate a density s ∈ L 2 from an i.i.d. sample X 1 , . . . , X n , we chose some kdimensional linear subspace S of L 2 (µ) together with an orthonormal basis (ϕ 1 , . . . , ϕ k ) so that the projection s of s onto S can be written s = k j=1 β j ϕ j . Then we estimate each coefficient β j = ϕ j s dµ in this expansion by its empirical version βj = n -1 n i=1 ϕ j (X i ). This results in the projection estimator ŝ = k j=1 βj ϕ j (which in general does not belong to L 1 ) with risk

E s ŝ -s 2 = s -s 2 + n -1 k j=1 Var s ϕ j (X 1 ) ≤ s -s 2 + n -1   k j=1 ϕ 2 j (x)   s(x) dµ(x) ≤ s -s 2 + n -1 min    k j=1 ϕ 2 j ∞ ; k s ∞    .
(2.6)

A particular case occurs with the histogram ŝI given by (1.1) which corresponds to choosing ϕ j = l -1/2 j 1l I j , S = S I and s = s I . If l j = k -1 for all j, we get a regular histogram and derive from (1.2) and a convexity argument that

E s s -ŝI 2 ≤ s -s I 2 + (k -1)/n.
But, for general partitions, the bound (1.3) clearly emphasizes the difference with the risk bound of the form (2.3) obtained in Birgé and Rozenholc (2006) for the Hellinger loss:

E s h 2 (s, ŝI ) ≤ h 2 (s, s I ) + (k -1)/(2n).
Moreover, (1.3) is essentially unimprovable without further assumptions on s if the partition I is arbitrary, as shown by the following example. Define the partition I on X = [0, 1] by I j = [(j -1)α, jα) for 1 ≤ j < k and

I k = [(k -1)α, 1] with 0 < α < (k -1) -1 . Set s = s I = [(k -1)α] -1 [1 -1l I k ]. Then p j = (k -1) -1 for 1 ≤ j < k, s = s I and it follows from (1.2) that E s s -ŝI 2 = k -2 (k -1)αn = (k -2) s ∞ n ,
which shows that there is little space for improvement in (1.3).

Some negative results

The fact that the L ∞ -norm of s comes into the risk is not due to the use of histograms or projection estimators as shown by another negative result provided by Proposition 4 of Birgé (2006b) that we recall below for the sake of completeness.

Proposition 1 For each L > 0 and each integer D with 1 ≤ D ≤ 3n, one can find a finite set S of densities with the following properties: i) it is a subset of some D-dimensional affine subspace of L 2 ([0, 1], dx) with a metric dimension bounded by D/2;

ii) sup s∈S s ∞ ≤ L + 1; iii) for any estimator ŝ(X 1 , . . . , X n ) belonging to L 2 ([0, 1], dx) and based on an i.i.d. sample with density s ∈ S,

sup s∈S E s ŝ -s 2 > 0.0139DLn -1 .
(2.7)

It follows that there is no hope to get an analogue of (2.3), under the same assumptions, when d = d 2 and the best one can expect in full generality, when S is a model with metric dimension bounded by D and s ∈ L ∞ , is to design an estimator ŝ with a risk bounded by

E s d 2 2 (ŝ, s) ≤ C inf t∈S d 2 2 (s, t) + n -1 D s ∞ .
(2.8)

The situation becomes worse when s ∈ L ∞ (µ) or if sup s∈S s ∞ = +∞ as shown by the following lower bound to be proved in Section 7.1.

Proposition 2 Let S = {s θ , 0 < θ ≤ 1/3} be the set of densities with respect to Lebesgue measure on [0, 1] given by

s θ = θ -2 1l [0,θ 3 ] + θ 2 + θ + 1 -1 1l (θ 3 ,1] .
If we have at disposal n i.i.d. observations with density s θ ∈ S, we can build an estimator ŝn such that sup 0<θ≤1/3 E s θ nh 2 (s θ , ŝn ) ≤ C for some C independent of n. On the other hand, although the metric dimension of S with respect to the distance d 2 is bounded by 2, sup 0<θ≤1/3 E s θ s θsn 2 = +∞, whatever n and the estimator sn .

About this paper

Our purpose here is twofold. We first want to derive estimators achieving a risk bound which generalizes (2.8) in the sense that it could also apply to the case of s ∈ L ∞ . We know from (2.6) that projection estimators do satisfy (2.8) when S is a D-dimensional linear space, but do not have any result for non-linear models. Our second goal is to handle many models simultaneously and design an estimator which performs as well (or almost as well) as the estimator based on the "best model", i.e. one leading to the smallest risk bound (up to some universal constant). This is possible when the distance d is either the Hellinger distance h or the variation distance v, as shown by Theorem 1. As compared to the bound (2.3), we simply pay the price of replacing D m by ∆ m when ∆ m > D m . This price is due to the complexity of the family of models we use (there is nothing to pay in the simplest case of one model per dimension) and this price is essentially unavoidable, as shown in a specific case by Birgé and Massart (2006).

It follows from the previous section that it is impossible to get an analogue of Theorem 1 when d = d 2 . We shall explain what kind of (necessarily weaker) results can be obtained in this context and to what extent Theorem 1 can be rescued. For this, we shall proceed in several steps. In the next section we shall explain how to build estimators based on families of special models S m , following the method explained in Birgé (2006a). These models need to be discrete subsets of L Γ ∞ (for some given Γ) with bounded metric dimension while there is no reason that our initial models S m be of this type (think of linear models). Section 4 will therefore be devoted to the construction of such special models S m from ordinary ones. This construction will finally lead to an estimator ŝΓ belonging to L Γ ∞ , the performance of which strongly depends on our choice of Γ. In Section 5, we shall explain how, given a geometrically increasing sequence (Γ i ) i≥1 of values of Γ and the corresponding sequence of estimators ŝΓ i , we can use the observations to choose a suitable value for Γ. Since we have a single sample X to build the estimators ŝΓ i and to choose Γ, we shall proceed by sample splitting using one half of the sample for the construction of the estimators and the second half to select a value of Γ. In particular, for the case of a single model, this will lead to a generalized version of (2.8) that can also handle the case of s ∈ L ∞ . When s ∈ L ∞ (with an unknown value of s ∞ ), the risk bounds we get completely parallel (apart from some constants depending on s ∞ ) those obtained for estimating s in the white noise model. We shall give a few applications of these results, in particular to aggregation of preliminary estimators, in Section 6, while the last section will be devoted to the most technical proofs.

T-estimators for L 2 -loss

In order to define estimators based on families of models with bounded metric dimensions, we shall follow the approach of Birgé (2006a) based on what we have called T-estimators. We refer to this paper for the definition of these estimators, recalling that it relies on the existence of suitable tests between balls of the underlying metric space L 2 , d 2 . To derive such tests, we need a few specific technical tools to deal with the L 2 -distance.

Tests between L 2 -balls

Randomizing our sample

In the sequel we shall make use of randomized tests based on a randomization trick due to Yang and Barron (1998, page 106) which has the effect of replacing all densities involved in our problem by new ones which are uniformly bounded away from zero. For this, we choose some number λ ∈ (0, 1) and consider the mapping τ from L 2 to L 2 given by τ (u) = λu + 1λ. Note that τ is one-to-one and isometric, up to a factor λ, i.e.

d 2 (τ (u), τ (v)) = λd 2 (u, v). If u ∈ L Γ ∞ , then τ (u) ∈ L Γ ′ ∞ with Γ ′ = λΓ + 1 -λ.
Let s ′ = τ (s). Given our initial i.i.d. sample X, we want to build new i.i.d. variables X ′ 1 , . . . , X ′ n with density s ′ . For this, we consider two independent n-samples, Z 1 , . . . , Z n and ε 1 , . . . , ε n with respective distributions µ and Bernoulli with parameter λ. Both samples are independent of X. We then set

X ′ i = ε i X i + (1 -ε i )Z i for 1 ≤ i ≤ n. It follows that X ′
i has density s ′ as required. We shall still denote by P s the probability on Ω that gives X ′ = (X ′ 1 , . . . , X ′ n ) the distribution P ⊗n s ′ . Given two distinct points t, u ∈ L 2 we define a (randomized) test function ψ(X ′ ) between t and u as a measurable function with values in {t, u}, ψ(X ′ ) = t meaning deciding t and ψ(X ′ ) = u meaning deciding u.

Once we have used the randomization trick of Yang and Barron, for instance with λ = 1/2, we deal with an i.i.d. sample X ′ with a density s ′ which is bounded from below by 1/2 and we may therefore work within the set of densities that satisfy this property.

Some minimax results

The main tool for the design of tests between L 2 -balls of densities is the following proposition which derives from the results of Birgé (1984) (keeping here the notations of that paper) and in particular from Corollary 3.2, specialized to the case of I = {t} and c = 0.

Proposition 3 Let M be some linear space of finite measures on some measurable space (Ω, A) with a topology of a locally convex separated linear space. Let P, Q be two disjoint sets of probabilities in M and F a set of positive measurable functions on Ω with the following properties (with respect to the given topology on M):

i) P and Q are convex and compact; ii) for any f ∈ F and 0 < z < 1 the function P → f z dP is well-defined and upper semi-continuous on P ∪ Q;

iii) for any P ∈ P, Q ∈ Q, t ∈ (0, 1) and ε > 0, there exists an f ∈ F such that

(1 -t) f t dP + t f 1-t dQ < (dP ) 1-t (dQ) t + ε;
iv) all probabilities in P (respectively in Q) are mutually absolutely continuous. Then one can find P ∈ P and Q ∈ Q such that

sup P ∈P Q P t dP = sup Q∈Q P Q 1-t dQ = sup P ∈P,Q∈Q (dP ) 1-t (dQ) t = dP 1-t dQ t .
In Birgé (1984) we assumed that M was the set of all finite measures on (Ω, A) but the proof actually only uses the fact that P and Q are subsets of M. Recalling that the Hellinger affinity between two densities u and v is defined by ρ(u, v) = √ uv dµ = 1h 2 (u, v), we get the following corollary.

Corollary 1 Let µ be a probability measure on (X , W) and, for 1 ≤ i ≤ n, let (P i , Q i ) be a pair of disjoint convex and weakly compact subsets of L 2 (µ) such that s > 0 µ-a.s. and s dµ = 1 for all s ∈ n i=1

(P i ∪ Q i ) . (3.1)
For each i, one can find p i ∈ P i and q i ∈ Q i such that

sup u∈P i q i /p i u dµ = sup v∈Q i p i /q i v dµ = sup u∈P i ,v∈Q i ρ(u, v) = ρ(p i , q i ). Let X = (X 1 , . . . , X n ) be a random vector on X n with distribution n i=1 (s i • µ) with s i ∈ P i for 1 ≤ i ≤ n and let x ∈ R. Then P n i=1 log(q i /p i )(X i ) ≥ 2x ≤ e -x n i=1 ρ(p i , q i ) ≤ exp -x - n i=1 h 2 (p i , q i ) . If X has distribution n i=1 (u i • µ) with u i ∈ Q i for 1 ≤ i ≤ n, then P n i=1 log(q i /p i )(X i ) ≤ 2x ≤ e x n i=1 ρ(p i , q i ) ≤ exp x - n i=1 h 2 (p i , q i ) .
Proof: We apply the previous proposition with t = 1/2, (X , W) = (Ω, A) and M the set of measures of the form u • µ, u ∈ L 2 (µ) endowed with the weak L 2 -topology.

In view of (3.1), P i and Q i can be identified with two sets of probabilities and we can take for F the set of all positive functions such that log f is bounded. As a consequence, all four assumptions of Proposition 3 are satisfied. In order to get iii) we simply take for f a suitably truncated version of s/u when P = s • µ and Q = u • µ.

As to the probability bounds they derive from classical exponential inequalities, as for Lemma 7 of Birgé (2006a).

Abstract tests between L 2 -balls

The purpose of this section is to prove the following result.

Theorem 2 Let t, u ∈ L Γ ∞ for some Γ < +∞. For any x ∈ R, there exists a test ψ t,u,x between t and u, based on the randomized sample X ′ defined in Section 3.1.1 with a suitable value of λ, which satisfies

sup {s∈L2 | d 2 (s,t)≤d 2 (t,u)/4} P s [ψ t,u,x (X ′ ) = u] ≤ exp - n t -u 2 + x 65Γ , (3.2) sup {s∈L2 | d 2 (s,u)≤d 2 (t,u)/4} P s [ψ t,u,x (X ′ ) = t] ≤ exp - n t -u 2 -x 65Γ . (3.3)
Proof: It requires several steps. To begin with, we use the randomization trick of Yang and Barron described in Section 3.1.1, replacing our original sample X by the randomized sample X ′ = (X ′ 1 , . . . , X ′ n ) for some convenient value of λ to be chosen later. Each X ′ i has density s ′ ≥ 1λ when X i has density s. Then we build a test between t ′ = τ (t) and u ′ = τ (u) based on X ′ and Corollary 1. To do this, we set ∆ = tu ,

P = τ B d 2 (t, ∆/4) ∩ L 2 and Q = τ B d 2 (u, ∆/4) ∩ L 2 .
Then P is the subset of the ball B d 2 (t ′ , λ∆/4) of those densities bounded from below by 1λ, hence d 2 (P, Q) ≥ λ∆/2 and P is convex and weakly closed since any indicator function belongs to L 2 (µ) because µ is a probability. Since B d 2 (t ′ , λ∆/4) is weakly compact, it is also the case for P and the same argument shows that Q is also convex and weakly compact. It then follows from Corollary 1 that one can find t ∈ P and ū ∈ Q such that

P s n i=1 log ū(X ′ i )/ t(X ′ i ) ≥ 2y ≤ exp -nh 2 ( t, ū) -y if s ∈ P, (3.4) while P s n log ū(X ′ i )/ t(X ′ i ) ≤ 2y ≤ exp -nh 2 ( t, ū) + y if s ∈ Q. (3.5) Fixing y = nx/(65Γ), we finally define ψ t,u,x (X ′ ) by setting ψ t,u,x (X ′ ) = u if and only if n i=1 log (ū(X ′ i )/ t(X ′ i )) ≥ 2y. Since s ′ ∈ P is equivalent to s ∈ B d 2 (t, ∆/4
) or d 2 (s, t) ≤ ∆/4 and similarily s ∈ Q is equivalent to d 2 (s, u) ≤ ∆/4, to derive (3.2) and (3.3) from (3.4) and (3.5), we just have to show that h 2 ( t, ū) ≥ (65Γ) -1 ∆ 2 . We start from the fact, to be proved below, that t ∨ ū ∞ ≤ 2(λΓ + 1λ).

(3.6)

It implies that h 2 ( t, ū) = 1 2 √ t - √ ū 2 dµ = 1 2 ( t -ū) 2 √ t + √ ū 2 dµ ≥ t -ū 2 16(λΓ + 1 -λ) ≥ (λ∆) 2 64(λΓ + 1 -λ)
.

Choosing λ close enough to one leads to the required bound h 2 ( t, ū) ≥ (65Γ) -1 ∆ 2 . As to (3.6), it is a consequence of the next lemma to be proved in Section 7.2. We apply this lemma to the pair t ′ , u ′ which satisfies

t ′ ∨ u ′ ∞ ≤ λΓ + 1 -λ. If (3.6)
were wrong, we could find t′ ∈ P and ū′ ∈ Q with h ( t′ , ū′ ) < h ( t, ū), which, by Corollary 1, is impossible.

Lemma 1 Let us consider four elements t, u, v 1 , v 2 in L 2 with t = u, v 1 = v 2 and t ∨ u ∞ = B. If v 1 ∨ v 2 ∞ > 2B, there exists v ′ 1 , v ′ 2 ∈ L 2 with d 2 (v ′ 1 , t) ≤ d 2 (v 1 , t), d 2 (v ′ 2 , u) ≤ d 2 (v 2 , u) and h(v ′ 1 , v ′ 2 ) < h(v 1 , v 2 ).

The performance of T-estimators

We are now in a position to prove an analogue of Corollary 6 of Birgé (2006a).

Theorem 3 Assume that we observe n i.i.d. random variables with unknown density s ∈ L 2 , d 2 and that we have at disposal a countable family of discrete subsets

{S m } m∈M of L Γ ∞ for some given Γ > 1. Let each set S m satisfy |S m ∩ B d 2 (t, xη m )| ≤ exp D m x 2 for all x ≥ 2 and t ∈ L 2 , (3.7) with η m > 0, D m ≥ 1/2, η 2 m ≥ 273ΓD m n for all m ∈ M, m∈M exp - nη 2 m 1365Γ = Σ < +∞. (3.8)
Then one can build a T-estimator ŝ such that, for all s ∈ L 2 ,

E s d q 2 (s, ŝ) ≤ C q (Σ + 1) inf m∈M d 2 (s, S m ) ∨ η m q
, for all q ≥ 1.

(3.9)

Proof: Since (3.9) is merely a version of (7. for some given Γ > 1. One can build a T-estimator ŝ such that, for all s ∈ L 2 ,

E s s -ŝ 2 ≤ C inf t∈S d 2 2 (s, t) + n -1 DΓ .
Proof: By Definition 1 and the remark following it, for each η 0 > 0, one can find an η 0 -net S 0 ⊂ S for S, hence S 0 ⊂ L Γ ∞ , satisfying (3.7) with D 0 = 25D/4. Moreover d(s, S 0 ) ≤ η 0 + d s, S . Choosing η 2 0 = 273 × 25ΓD/4, we may apply Theorem 3. The result then follows from (3.9) with q = 2.

Theorem 3 applies in particular to the special situation of each model S m being reduced to a single point {t m } so that we can take D m = 1/2 for each m. We then get the following useful corollary.

Corollary 3 Assume that we observe n i.i.d. random variables with unknown distribution P s , s ∈ L 2 , d 2 and that we have at disposal a countable subset S = {t m } m∈M of L Γ ∞ for some given Γ > 1. Let {∆ m } m∈M be a family of weights such that ∆ m ≥ 1/10 for all m ∈ M and

1 ≤ m∈M exp[-∆ m ] = Σ < +∞.
(3.10)

We can build a T-estimator ŝ such that, for all s ∈ L 2 ,

E s d q 2 (s, ŝ) ≤ C q Σ inf m∈M d 2 (s, t m ) ∨ Γ∆ m /n
q for all q ≥ 1.

Proof: Let us set here S m = {t m }, D m = 1/2 and η m = 37 Γ∆ m /n for m ∈ M. One can then check that (3.7) and (3.8) are satified so that (3.9) holds. Our risk bound follows.

At this stage, there are two main difficulties to apply Theorem 3 or Corollary 3. The first problem is to build suitable subsets S m (or S) of L Γ ∞ from classical approximating sets (models), finite dimensional linear spaces for instance, that belong to L 2 (µ). We shall address this problem in the next section while we shall solve the second problem, namely choosing a convenient value for Γ from the data, in Section 5.

4 Model selection with uniformly bounded models 4.1 The projection operator onto L Γ ∞ Our first task is to define a projection operator π Γ from L 2 (µ) onto L Γ ∞ (Γ > 1) and to study its properties. In the sequel, we systematically identify a real number a with the function a1l X for the sake of simplicity. The following proposition is the corrected version, by Yannick Baraud, of the initial mistaken result of the author.

Proposition 4 For t ∈ L 2 (µ) and 1 < Γ < +∞ we set π Γ (t) = [(t + γ) ∨ 0] ∧ Γ where γ is defined by [(t + γ) ∨ 0] ∧ Γ dµ = 1. Then π Γ is the projection operator from L 2 (µ) onto the convex set L Γ ∞ . Moreover, if s ∈ L 2 and Γ > 2, then s -π Γ (s) 2 ≤ Γ 2 -Γ -1 Γ(Γ -2) Q s (Γ) with Q s (z) = s>z (s -z) 2 dµ. ( 4
t -π(t), u -π(t) ≤ 0 for all u ∈ L Γ ∞ . (4.2) Since [u -π(t)] dµ = 0 for u ∈ L Γ ∞ , (4.2) implies that t + z -π(t), u -π(t) ≤ 0 for z ∈ R, hence π(t) = π(t + z). Since π Γ (t) = π Γ (t + z) as well, we may assume that [t ∨ 0] ∧ Γ dµ = 1, hence π Γ (t) = [t ∨ 0] ∧ Γ and π Γ (t) = t on the set 0 ≤ t ≤ Γ. Then, for u ∈ L Γ ∞ , t -π Γ (t), u -π Γ (t) = t<0 tu dµ + t>Γ (t -Γ)(u -Γ) dµ ≤ 0, since 0 ≤ u ≤ Γ. This concludes the proof that π = π Γ .
Let us now bound sπ Γ (s) when s ∈ L 2 , setting s = s ∧ Γ + v with v = (s -Γ)1l s>Γ . Since there is nothing to prove when s ∞ ≤ Γ, we assume that v dµ > 0. By Cauchy-Schwarz Inequality,

v dµ 2 ≤ µ({s > Γ}) v 2 dµ ≤ Γ -1 v 2 . (4.3) Moreover, since s ∧ Γ dµ < 1, π Γ (s) = (s + γ) ∧ Γ with 0 < γ ≤ 1. Hence 1 = [(s + γ) ∧ Γ] dµ ≥ (s ∧ Γ) dµ + γµ({s ≤ Γ -γ}) ≥ 1 -v dµ + γ 1 - 1 Γ -γ > 1 -v dµ + γ Γ -2 Γ -1 and γ < (Γ -1)/(Γ -2) v dµ. Now, since 0 ≤ π Γ (s) -s ≤ γ for s ≤ Γ, s -π Γ (s) 2 = s≤Γ [π Γ (s) -s] 2 dµ + v 2 ≤ γ s≤Γ [π Γ (s) -s] dµ + v 2 < Γ -1 Γ -2 v dµ s>Γ [s -π Γ (s)] dµ + v 2 ≤ Γ -1 Γ -2 v dµ 2 + v 2 ≤ 1 + Γ -1 Γ(Γ -2) v 2 ,
where we used (4.3). This concludes our proof.

Selection for uniformly bounded countable sets

We consider here the situation mentioned in Corollary 3 but without the assumption that S ⊂ L Γ ∞ . For S = {t m } m∈M an arbitrary countable subset of L 2 (µ) we may always replace it by its projection π Γ (S) onto L Γ ∞ and apply Corollary 3. The resulting risk bound involves

d 2 s, π Γ (t m ) ≤ d 2 s, π Γ (s) + d 2 π Γ (s), π Γ (t m ) ≤ Γ 2 -Γ -1 Γ(Γ -2) Q s (Γ) 1/2 + d 2 (s, t m )
by Proposition 4. We finally get:

Corollary 4 Assume that we observe n i.i.d. random variables with unknown density s ∈ L 2 , d 2 and that we have at disposal a countable subset S = {t m } m∈M of L 2 (µ) and a family of weights {∆ m } m∈M such that ∆ m ≥ 1/10 for all m ∈ M and (3.10) holds. Given Γ ≥ 3 we can build a T-estimator ŝΓ with values in π Γ (S) such that, for all s ∈ L 2 ,

E s s -ŝΓ q ≤ C q Σ inf m∈M d 2 (s, t m ) + Q s (Γ) ∨ Γ∆ m /n q for q ≥ 1.

Selection with uniformly bounded models

Typical models S for density estimation in L 2 (µ) are finite-dimensional linear spaces which are not subsets of L Γ ∞ but merely spaces of functions with nice approximation properties. To apply Theorem 3 we have to replace them by discrete subsets of L Γ ∞ Proposition 5 Let S be a subset of L 2 (µ) with metric dimension bounded by D. For Γ > 2 and η > 0, one can find a discrete subset S ′ of L Γ ∞ with the following properties:

|S ′ ∩ B d 2 (t, xη)| ≤ exp 9Dx 2
for all x ≥ 2 and t ∈ L 2 (µ); (4.4)

for any s ∈ L 2 , one can find some s ′ ∈ S ′ such that

s -s ′ ≤ 3.1 η + inf t∈S s -t + 4.1 Γ 2 -Γ -1 Γ(Γ -2) Q s (Γ) 1/2 . (4.5)
Proof: According to Definition 1, we choose some η-net S η for S such that (2.2) holds for all t ∈ L 2 (µ). Since, by Proposition 4, the operator

π Γ from L 2 (µ) to L Γ ∞ satisfies u -π Γ (t) ≤ u -t for all u ∈ L Γ ∞ , we may apply Proposition 12 of Birgé (2006a) with M ′ = L 2 (µ), d = d 2 , M 0 = L Γ ∞ , T = S η , π = π Γ and λ = 1. It shows that one can find a subset S ′ of π Γ (S η ) such that (4.4) holds and d 2 (u, S ′ ) ≤ 3.1d 2 (u, S η ) for all u ∈ L Γ ∞ . If s is an arbitrary element of L 2 , then d 2 π Γ (s), S ′ ≤ 3.1d 2 (π Γ (s), S η ) ≤ 3.1 d 2 (π Γ (s), s) + d 2 s, S + η , hence d 2 s, S ′ ≤ 3.1 d 2 s, S + η + 4.1d 2 (π Γ (s), s) . (4.6)
The conclusion follows from Proposition 4.

We are now in a position to derive our main result about bounded model selection.

We start with a countable collection {S m , m ∈ M} of models in L 2 (µ) with metric dimensions bounded respectively by D m ≥ 1/2 and a family of weights ∆ m satisfying (3.10). We fix some Γ ≥ 3 and, for each m ∈ M, we set

η m = 50 D m ∨ 37 ∆ m Γ/n.
By Proposition 5 (with η = η m ), each S m gives rise to a subset S Γ m which satisfies (3.7) with D m = 9D m . It follows from our choice of η m that (3.8) is also satisfied so that we may apply Theorem 3 to the family of sets S Γ m , m ∈ M . This results in a T-estimator ŝΓ such that, for all s ∈ L 2 ,

E s d q 2 s, ŝΓ ≤ C q Σ inf m∈M d 2 s, S Γ m ∨ η m q for q ≥ 1.
We also derive from Proposition 5 that

d 2 s, S Γ m ≤ 3.1 η m + inf t∈Sm s -t + 4.1 (5/3)Q s (Γ).
Putting the bounds together and rearranging the terms leads to the following theorem.

Theorem 4 Given a countable collection {S m , m ∈ M} of models in L 2 (µ) with metric dimensions bounded respectively by D m ≥ 1/2 and a family of weights ∆ m satisfying (3.10), one can build, for each Γ ≥ 3, a T-estimator ŝΓ which satisfies, for all s ∈ L 2 and q ≥ 1,

E s s -ŝΓ q ≤ C q Σ   inf m∈M    d 2 s, S m + Γ D m ∨ ∆ m n    + Q s (Γ)   q , (4.7)
with Q s given by (4.1) and C q some constant depending only on q. If s ∞ ≤ Γ, then

E s s -ŝΓ 2 ≤ CΣ inf m∈M d 2 2 s, S m + n -1 Γ D m ∨ ∆ m .
(4.8)

A selection theorem

Now that we are able to build models which are bounded by Γ for each Γ ≥ 3 and to select one of these models, which results in an estimator ŝΓ , we need a way to choose Γ from the data in order to optimize the bound in (4.7). The idea is to use one half of our sample to build a sequence of estimators ŝ2 i and select a convenient value of i from the other half of our sample. This requires to select an element from a sequence of densities which is not uniformly bounded.

A preliminary selection result

We start with a general selection result, to be proved in Section 7.3, that we state for an arbitrary statistical framework since it may apply to other situations than density estimation from an i.i.d. sample. We observe some random object X with distribution P s on X where s belongs to a metric space M (carrying a distance d) which indexes a family P = {P t , t ∈ M } of probabilities on X .

Theorem 5 Let (t p ) p≥1 be a sequence in M such that the following assumption holds: for all pairs (n, p) with 1 ≤ n < p and all x ∈ R, one can find a test ψ tn,tp,x based on the observation X and satisfying

sup {s∈M | d(s,tn)≤d(tn,tp)/4} P s [ψ tn,tp,x (X) = t p ] ≤ B exp -a2 -p d 2 (t n , t p ) -x ; (5.1) sup {s∈M | d(s,tp)≤d(tn,tp)/4} P s [ψ tn,tp,x (X) = t n ] ≤ B exp -a2 -p d 2 (t n , t p ) + x ; (5.2)
with positive constants a and B independent of n, p and x. For each A ≥ 1, one can design an estimator ŝA such that, for all s ∈ M ,

E s [d q (ŝ A , s)] ≤ BC(A, q) inf p≥1 d(s, t p ) ∨ a -1 p2 p q for 1 ≤ q < 2A/ log 2. (5.3)
This general result applies to our specific framework of density estimation based on an observation X with distribution P s , s ∈ L 2 , provided that the sequence (t p ) p≥1 be suitably chosen. We shall simply assume here that t p ∈ L 2 with t p ∞ ≤ 2 p+1

for each p ≥ 1. This implies that, for 1 ≤ i < j, t i and t j belong to L so that Theorem 2 applies with X replaced by the randomized sample X ′ and the assumption of Theorem 5 is therefore satisfied with d = d 2 , B = 1 and a = n/65, leading to the following corollary.

Corollary 5 Let (t i ) i≥1 be a sequence of densities such that t i ∈ L 2 i+1 ∞ for each i, A ≥ 1 and X be an n-sample with density s ∈ L 2 . One can design an estimator ŝA such that

E s [d q 2 (ŝ A , s)] ≤ C(A, q) inf i≥1 d 2 (s, t i ) ∨ √ n -1 i2 i q
for 1 ≤ q < 2A/ log 2.

General model selection in L 2

We now consider the general situation where we observe n = 2n ′ i.i.d. random variables X 1 , . . . , X n with an unknown density s ∈ L 2 , not necessarily bounded, and have at disposal a countable collection {S m , m ∈ M} of models in L 2 (µ) with metric dimensions bounded respectively by D m ≥ 1/2 and a family of weights ∆ m which satisfy (3.10). We split our sample X = (X 1 , . . . , X n ) into two subsamples X 1 and X 2 of size n ′ . With the sample X 1 we build the T-estimators ŝi (X 1 ) = ŝ2 i+1 (X 1 ), i ≥ 1 which are provided by Theorem 3. It then follows from (4.7) that each such estimator satisfies, for q ≥ 1,

E s [ s -ŝi (X 1 ) q ] ≤ C q Σ    inf m∈M   d 2 s, S m + 2 i D m ∨ ∆ m n 1/2   + Q s (2 i+1 )    q ,
with Q s given by (4.1). We now work conditionally on X 1 , fix a convenient value of A ≥ 1 (for instance A = 1 if we just want to bound the quadratic risk) and use the second half of the sample X 2 to select one estimator among the previous family according to the procedure described in Section 5.1. By Corollary 5 this results in a new estimator sA (X) which satisfies

E s d q 2 (s A (X), s) X 1 ≤ C(A, q) inf i≥1 d 2 (s, ŝi (X 1 )) ∨ √ n -1 i2 i q ,
provided that q < 2A/ log 2. Integrating with respect to X 1 and using our previous risk bound gives

E s [ s -sA (X) q ] ≤ C(A, q) inf i≥1 E s [ s -ŝi (X 1 ) q ] + n -1 i2 i q/2 ≤ C ′ (A, q)Σ inf i≥1    inf m∈M   d q 2 s, S m + 2 i D m ∨ ∆ m ∨ i n q/2   + [Q s (2 i+1 )] q/2    . For 2 i ≤ z < 2 i+1 , log z ≥ i log 2 and Q s (z) ≥ Q s (2 i+1 ) since Q s is nonincreasing.
Modifying accordingly the constants in our bounds, we get the main result of this paper which provides adaptation to both the models and the truncation constant.

Theorem 6 Let X = (X 1 , . . . , X n ) with n ≥ 2 be an i.i.d. sample with unknown density s ∈ L 2 and {S m , m ∈ M} be a countable collection of models in L 2 (µ) with metric dimensions bounded respectively by D m ≥ 1/2. Let {∆ m , m ∈ M} be a family of weights which satisfy (3.10) and Q s (z) be given by (4.1). For each A ≥ 1, there exists an estimator sA (X) such that, whatever s ∈ L 2 and 1 ≤ q < (2A/ log 2),

E s [ s -sA (X) q ] ≤ C(A, q)Σ inf z≥2 inf m∈M   d q 2 s, S m + z D m ∨ ∆ m ∨ log z n q/2 + [Q s (z)] q/2   . (5.4)
In particular, for s = s1 and s ∈ L ∞ (µ),

E s s -s(X) 2 ≤ CΣ inf m∈M d 2 2 s, S m + n -1 s ∞ D m ∨ ∆ m ∨ log s ∞ .
(5.5)

Some remarks

We see that (5.4) is a generalization of (4.7) and (5.5) of (4.8) at the modest price of the extra log z (or log s ∞ ). We do not know whether this log z is necessary or not but, in a typical model selection problem, when s belongs to L ∞ (µ) but not to ∪ m∈M S m , the optimal value of D m goes to +∞ with n, so that, for this optimal value, asymptotically

D m ∨ ∆ m ∨ log s ∞ = D m ∨ ∆ m .
Up to constants depending on s ∞ , (5.5) is the exact analogue of (2.5) which shows that, when s ∈ L ∞ (µ), all the results about model selection obtained for the Hellinger distance can be translated in terms of the L 2 -distance.

Note that Theorem 6 applies to a single model S with metric dimension bounded by D, in which case one can use a weight ∆ = 1/2 ≤ D which results, if A = 1, in the risk bound

E s s -s(X) 2 ≤ C d 2 2 s, S + inf z≥2 z D ∨ log z n + Q s (z) , (5.6) and, if s ∈ L ∞ (µ), E s s -s(X) 2 ≤ C d 2 2 s, S + n -1 s ∞ D ∨ log s ∞ . (5.7)
Apart from the extra log s ∞ , which is harmless when it is smaller than D, we recover what we expected, namely the bound (2.8).

Even if s ∈ L ∞ (µ) the bound (5.4) may be much better than (5.5). This is actually already visible with one single model, comparing (5.6) with (5.7). It is indeed easy to find an example of a very spiky density s for which (5.6) is much better than (5.7) or the classical bound (2.6) obtained for projection estimators. Of course, this is just a comparison of universal bounds, not of the real risk of estimators for a given s.

More surprising is the fact that our estimator can actually dominate a histogram based on the same model, although our counter-example is rather caricatural and more an advertising against the use of the L 2 -loss than against the use of histogram estimators. Let us consider a partition I of [0, 1] into 2D intervals I j , 1 ≤ j ≤ 2D with the integer D satisfying 2 ≤ D ≤ n and fix some γ ≥ 10. We then set α = γ 2 n -1 .

For 1 ≤ j ≤ D, the intervals I 2j-1 have length α while the intervals I 2j have length β with D(α + β) = 1. We denote by S the 2D-dimensional linear space spanned by the indicator functions of the I j . It is a model with metric dimension bounded by D.

We assume that the underlying density s with respect to Lebesgue measure belongs to S and is defined as

s = pα -1 D j=1 1l I 2j-1 + qβ -1 D j=1
1l I 2j with p = γα and D(p + q) = 1, so that β > q since α < p. We consider two estimators of s derived from the same model S: the histogram ŝI based on the partition I and the estimator s based on S and provided by Theorem 6. According to (1.2) the risk of ŝI is

Dn -1 α -1 p(1 -p) + β -1 q(1 -q) ≥ 0.9Dn -1 α -1 p = 0.9Dγn -1 ,
since p ≤ 1/10. The risk of s can be bounded by (5.4) with z = 4 which gives

E s s -s(X) 2 ≤ C 4Dn -1 + D I 1 (p/α) 2 dµ = CD 4n -1 + p 2 α -1 = 5CDn -1 .
For large enough values of γ our estimator is better than the histogram. The problem actually comes from the observations falling in some of the intervals I 2j-1 which will lead to a very bad estimation of s on those intervals. Note that this fact will happen with a small probability since Dp = D(γn) -1 ≤ γ -1 . Nevertheless, this event of small probability is important enough to lead to a large risk when we use the L 2 -loss.

6 Some applications

Aggregation of preliminary estimators

Theorem 6 applies in particular to the problem of aggregating preliminary estimators, built from an independent sample, either by selecting one of them or by combining them linearily.

Aggregation by selection

Let us begin with the problem, that we already considered in Section 4.2, of selecting a point among a countable family {t m , m ∈ M}. Typically, as in [START_REF] Rigollet | Linear and convex aggregation of density estimators[END_REF], the t m are preliminary estimators based on an independent sample (derived by sample splitting if necessary) and we want to choose the best one in the family. This is a situation for which one can choose D m = 1/2 and A = 1 which leads to the following corollary Corollary 6 Let X = (X 1 , . . . , X n ) with n ≥ 2 be an i.i.d. sample with unknown density s ∈ L 2 and {t m , m ∈ M} be a countable collection of points in L 2 (µ). Let {∆ m , m ∈ M} be a family of weights which satisfy (3.10) and Q s (z) be given by (4.1).

There exists an estimator s(X) such that, whatever s ∈ L 2 ,

E s s -s(X) 2 ≤ CΣ inf z≥2 inf m∈M d 2 2 (s, t m ) + z(∆ m ∨ log z) n + Q s (z) .

Linear aggregation

Rigollet and Tsybakov ( 2007) have considered the problem of linear aggregation. Given a finite set {t 1 , . . . , t N } of preliminary estimators of s, they use the observations to build a linear combination of the t j in order to get a new and potentially better estimator of s. For λ = (λ 1 , . . . , λ N ) ∈ R N , let us set t λ = N j=1 λ j t j . Rigollet and Tsybakov build a selector λ(X 1 , . . . , X n ) such that the corresponding estimator s

(X) = t b λ satisfies, for all s ∈ L ∞ , E s s -s(X) 2 ≤ inf λ∈R N d 2 2 s, t λ + n -1 s ∞ N. (6.1)
Unfortunately, this bound, which is shown to be sharp for such an estimator, can be really poor, as compared to the minimal risk inf 1≤j≤N d 2 2 (s, t j ) of the preliminary estimators when one of those is already quite good and n -1 s ∞ N is large, which is likely to happen when N is quite large. Moreover, this result tells nothing when s ∈ L ∞ . In Birgé (2006a, Section 9.3) we proposed an alternative way of selecting a linear combination of the t j based on T-estimators. In the particular situation of densities belonging to L 2 , we proceed as follows: we choose for M the collection of all nonvoid subsets m of {1, . . . , N } and, for m ∈ M, we take for S m the linear span of the t j with j ∈ m so that the dimension of S m is bounded by |m| and its metric dimension D m by |m|/2. Since the number of elements of M with cardinality j is N j < (eN/j) j , we may set ∆ m = |m|[2 + log(N/|m|)] so that (3.10) is satisfied with Σ < 1. An application of Theorem 6 leads to the following corollary.

Corollary 7 Let X = (X 1 , . . . , X n ) with n ≥ 2 be an i.i.d. sample with unknown density s ∈ L 2 and {t 1 , . . . , t N } be a finite set of points in L 2 (µ). Let M be the collection of all nonvoid subsets m of {1, . . . , N } and, for m ∈ M,

Λ m = λ ∈ R N λ j = 0 for j ∈ m .
For each A ≥ 1, there exists an estimator sA (X) such that, whatever s ∈ L 2 and 1 ≤ q < (2A/ log 2),

E s [ s -sA (X) q ] ≤ C(A, q) inf z≥2 inf m∈M R(q, s, z, m), where R(q, s, z, m) = inf λ∈Λm d q 2 s, t λ + z |m| 1 + log(N/|m|) ∨ log z n q/2 + [Q s (z)] q/2
and Q s (z) is given by (4.1).

There are many differences between this bound and (6.1), apart from the nasty constant C(A, q). Firstly, it applies to densities s that do not belong to L ∞ and handles the case of q > 2 for a convenient choice of A. Also, when s ∈ L ∞ and one of the preliminary estimators is already close to s, it may very well happen, when N is large, that

R (2, s, s ∞ , m) ≤ inf λ∈Λm d 2 2 s, t λ + n -1 s ∞ |m| 1 + log(N/|m|) ∨ log s ∞
be much smaller than the right-hand side of (6.1) for some m of small cardinality.

Selection of projection estimators

In this section, we assume that s ∈ L ∞ (µ). This assumption is not needed for the design of the estimator but only to derive suitable risk bounds. We have at hand a countable family S m , m ∈ M of linear subspaces of L 2 (µ) with respective dimensions D m and we choose corresponding weights ∆ m satisfying (3.10). For each m, we consider the projection estimator ŝm defined in Section 2.2. Each such estimator has a risk bounded by (2.6), i.e.

E s ŝm -s 2 ≤ s m -s 2 + n -1 D m s ∞ ,
where s m denotes the orthogonal projection of s onto S m . If we apply Corollary 6 to this family of estimators, we get an estimator s(X) satisfying, for all s ∈ L ∞ ,

E s s -s(X) 2 ≤ CΣ inf m∈M s m -s 2 + n -1 s ∞ (D m ∨ ∆ m ∨ log s ∞ ) .
With this bound at hand, we can now return to the problem we considered in Section 1.1, starting with an arbitrary countable family {I m , m ∈ M} of finite partitions of X and weights ∆ m satisfying (3.10). To each partition I m we associate the linear space S m of piecewise constant fonctions of the form I∈Im β I 1l I . The dimension of this linear space is the cardinality of I m and its metric dimension is bounded by

|I m |/2. If we know that s ∈ L ∞ (µ)
, we can proceed as we just explained, building the family of histograms ŝIm (X 1 ) corresponding to our partitions and using Corollary 6 to get In the general case of s ∈ L 2 (µ), we may apply Theorem 6 to the family of linear models S m , m ∈ M derived from these partitions, getting an estimator s with a risk satisfying

E s s -s(X) 2 ≤ CΣ inf m∈M s Im -s 2 + n -1 s ∞ (|I m | ∨ ∆ m ∨ log s ∞ ) , (6.2
E s s -s(X) 2 ≤ CΣ inf z≥2 inf m∈M s Im -s 2 + z(|I m | ∨ ∆ m ∨ log z) n + Q s (z) .

A comparison with Gaussian model selection

A benchmark for model selection in general is the particular (simpler) situation of model selection for the so-called white noise framework in which we observe a Gaussian process

X = {X z , z ∈ [0, 1]} with X z = z 0 s(x) dx + σW z ,
where s is an unknown element of L 2 ([0, 1], dx), σ > 0 a known parameter and W z a Wiener process. For such a problem, an analogue of Theorem 1 has been proved in Birgé (2006a), namely Theorem 7 Let X be the Gaussian process given by

X z = z 0 s(x) dx + n -1/2 W z , 0 ≤ z ≤ 1,
where s is an unknown element of L 2 ([0, 1], dx) to be estimated and W z a Wiener process. Let {S m , m ∈ M} be a countable collection of models in L 2 (µ) with metric dimensions bounded respectively by D m ≥ 1/2. Let {∆ m , m ∈ M} be a family of weights which satisfy (3.10). There exists an estimator s(X) such that, whatever s ∈ L 2 ([0, 1], dx),

E s s -s(X) 2 ≤ C inf m∈M d 2 2 s, S m + n -1 D m ∨ ∆ m .
Comparing this bound with (5.5) shows that, when s ∈ L ∞ (µ), we get a similar risk bound for estimating the density s from n i.i.d. random variables, apart from an additional factor depending on s ∞ . Similar analogies are valid with bounds obtained for estimating densities with squared Hellinger loss or for estimating the intensity of a Poisson process as shown in Birgé (2006a and2007). Therefore, all the many examples that have been treated in these papers could be transferred to the case of density estimation with L 2 -loss with minor modifications due to the appearence of s ∞ in the bounds. We leave all these translations as exercices for the concerned reader.

Estimation in Besov spaces

The Besov space B α p,∞ ([0, 1]) with α, p > 0 is defined in DeVore and Lorentz (1993) and it is known that a necessary and sufficient condition for B α p,∞ ([0, 1]) ⊂ L 2 ([0, 1], dx) is δ = α+1/2-1/p > 0, which we shall assume in the sequel. The problem of estimating adaptively densities that belong to some Besov space B α p,∞ ([0, 1]) with unknown values of α and p has been solved for a long time when α > 1/p which is a necessary and sufficient condition for B α p,∞ ([0, 1]) ⊂ L ∞ ([0, 1], dx). See for instance Donoho, Johnstone, [START_REF] Donoho | Density estimation by wavelet thresholding Ann[END_REF], [START_REF] Delyon | On minimax wavelet estimators[END_REF] or Birgé and [START_REF] Birg É | From model selection to adaptive estimation[END_REF]. It can be treated in the usual way (with an estimation of s ∞ ) leading to the minimax rate of convergence n -2α/(2α+1) for the quadratic risk.

Wavelet expansions

It is known from analysis that functions s ∈ L 2 ([0, 1], dx) can be represented by their expansion with respect to some orthonormal wavelet basis {ϕ j,k , j ≥ -1, k ∈ Λ(j)} with |Λ(-1)| ≤ K and 2 j ≤ |Λ(j)| ≤ K2 j for all j ≥ 0. Such a wavelet basis satisfies

k∈Λ(j) ϕ j,k ∞ ≤ K ′ 2 j/2 for j ≥ -1, (6.3)
and we can write

s = ∞ j=-1 k∈Λ(j) β j,k ϕ j,k , with β j,k = ϕ j,k (x)s(x) dx. (6.4)
Moreover, for a convenient choice of the wavelet basis (depending on α), the fact that s belongs to the Besov space (6.5) where |s| α,p,∞ < +∞ is equivalent to the Besov semi-norm |s| α p . Moreover, it follows from Birgé and [START_REF] Birg É | From model selection to adaptive estimation[END_REF][START_REF] Yang | Mixing strategies for density estimation[END_REF], as summarized in Birgé (2006a, Proposition 13), that, given the integer r, one can find a wavelet basis (depending on r) and a universal family of linear models {S m , m ∈ M = ∪ J≥0 M J } with respective dimensions D m , and weights {∆ m , m ∈ M} satisfying (3.10), with the following properties. Each S m is the linear span of {ϕ -1,k , k ∈ Λ(-1)}∪{ϕ j,k , (j, k) ∈ m} with m ⊂ ∪ j≥0 Λ(j);

B α p,∞ ([0, 1]) is equivalent to sup j≥0 2 j(α+1/2-1/p)   k∈Λ(j) |β j,k | p   1/p = |s| α,p,∞ < +∞,
D m ∨ ∆ m ≤ c2 J for m ∈ M J and inf m∈M J inf t∈Sm s -t ≤ C(α, p)2 -Jα |s| α,p,∞ for s ∈ B α p,∞ ([0, 1]), α < r.
(6.6)

The bounded case

Actually, only the assumption that s ∈ B α p,∞ ([0, 1]) ∩ L ∞ (µ), rather than α > 1/p, is needed to get the optimal rate of convergence n -2α/(2α+1) . Indeed, we may apply the results of Section 6.2 to the family of models which satisfies (6.6) and derive an estimator s with a risk bounded by

E s s -s(X) 2 ≤ C(α, p) inf J≥0 2 -2Jα (|s| α,p,∞ ) 2 + n -1 s ∞ 2 J ∨ log s ∞ .
Choosing 2 J of the order of n 1/(2α+1) leads to the bound

E s s -s(X) 2 ≤ C (α, p, |s| α,p,∞ , s ∞ ) n -2α/(2α+1) , which is valid for all s ∈ B α p,∞ ([0, 1]) ∩ L ∞ (µ)
, whatever α < r and p and although α, p, |s| α p and s ∞ are unknown.

Further upper bounds for the risk

When α ≤ 1/p, i.e. 0 < δ ≤ 1/2, s may be unbounded and the classical theory does not apply any more. As a consequence the minimax risk over balls in B α p,∞ ([0, 1]) is presently unknown. Our study will not, unfortunely, solve this problem but, at least, provide some partial information. In this section we assume that α ≤ 1/p and, as usual, restrict ourselves to the case p ≤ 2 so that δ ≤ α. We consider the wavelet expansion of s which has been described in Section 6.4.1 and, to avoid unnecessary complications, we also assume that |s| α,p,∞ ≥ 1. In what follows, the generic constant C (changing from line to line) depends on the choice of the basis and δ.

Since p ≤ 2,

  k∈Λ(j) β 2 j,k   1/2 ≤   k∈Λ(j) |β j,k | p   1/p ≤ |s| α,p,∞ 2 -j(α+1/2-1/p) = |s| α,p,∞ 2 -jδ ,
hence, for q ≥ -1 an integer, j>q k∈Λ(j)

β j,k ϕ j,k ≤ C2 -qδ |s| α,p,∞ . (6.7)
The simplest estimators of s are the projection estimators ŝq over the linear spaces S ′ q where S ′ q is spanned by {ϕ

j,k , -1 ≤ j ≤ q, k ∈ Λ(j)} ŝq (X) = q j=-1 k∈Λ(j) βj,k (X)ϕ j,k , with βj,k (X) = n -1 n i=1 ϕ j,k (X i ),
The risk of these estimators can be bounded using (2.6) and (6.7) by

E s s -ŝq (X) 2 ≤ d 2 2 s, S ′ q + C2 q /n ≤ C ′ 2 -2qδ |s| 2 α,p,∞ + 2 q /n .
A convenient choice of q, depending on δ, then leads to 2δ+1) .

E s s -ŝq (X) 2 ≤ C|s| 2 α,p,∞ n -2δ/(
One can actually choose q from the data using a penalized least squares estimator and get a similar risk bound without knowing δ as shown by Theorem 7.5 of [START_REF] Massart | Concentration Inequalities and Model Selection[END_REF]. This is the only adaptation result we know for the case α ≤ 1/p without the restriction s ∈ L ∞ ([0, 1]).

Let us now see what our method can do. Since s is a density, it follows from (6.4) and ( 6.

3) that |β -1,k | ≤ ϕ -1,k ∞ ≤ K ′ / √ 2, hence k∈Λ(-1) β -1,k ϕ -1,k ∞ ≤ K ′ / √ 2 k∈Λ(-1) ϕ -1,k ∞ ≤ K ′2 /2.
Moreover, for j ≥ 0, (6.5) implies that sup k∈Λ(j) |β j,k | ≤ 2 -jδ |s| α,p,∞ . Therefore, by (6.3), k∈Λ(j)

β j,k ϕ j,k ∞ ≤ C2 -j(α-1/p) |s| α,p,∞ ,
and, for J ≥ 0, J j=0 k∈Λ(j)

β j,k ϕ j,k ∞ ≤    C|s| α,p,∞ if α > 1/p; C(J + 1)|s| α,p,∞ if α = 1/p; C2 J(1/p-α) |s| α,p,∞ if α < 1/p. Finally, J j=-1 k∈Λ(j) β j,k ϕ j,k ∞ ≤ C 0 L J |s| α,p,∞ with L J =    1 if α > 1/p; (J + 1) if α = 1/p; 2 J(1/p-α) if α < 1/p. Observing that if s = u + v with u ∞ ≤ z, then Q s (z) ≤ v 2 , we can conclude from (6.7) that Q s (C 0 L J |s| α,p,∞ ) ≤ C ′ 2 -2Jδ |s| 2 α,p,∞ .
Let us now turn back to the family of linear models described in Section 6.4.1 that satisfy (6.6). Theorem 6 asserts the existence of an estimator s(X) based on this family of models and satisfying

E s s -s(X) 2 ≤ C inf z≥2 inf m∈M d 2 2 s, S m + z D m ∨ ∆ m ∨ log z n + Q s (z) .
Given the integers J, J ′ , we may set z = z J ′ = C 0 L J ′ |s| α,p,∞ and restrict the minimization to m ∈ M J which leads to

E s s -s(X) 2 ≤ C |s| 2 α,p,∞ 2 -2Jα + 2 -2J ′ δ + n -1 L J ′ |s| α,p,∞ 2 J ∨ log z J ′ .
Since L J ′ 2 J ∨ log z J ′ is a nondecreasing function of both J and J ′ , this last bound is optimized when Jα and J ′ δ are approximately equal which leads to choosing the integer J ′ so that Jα/δ ≤ J ′ < Jα/δ + 1, hence 2 -2J ′ δ ≤ 2 -2Jα . Assuming, moreover, that 2 J ≥ log |s| α,p,∞ , which implies that 2 J ≥ C ′ log z J ′ , we get

E s s -s(X) 2 ≤ C|s| 2 α,p,∞ 2 -2Jα + 2 J (n|s| α,p,∞ ) -1 L J ′ .
We finally fix J so that 2 J ≥ G > 2 J-1 , where G is defined below. This choice ensures that G ≥ log |s| α,p,∞ for n large enough (depending on |s| α,p,∞ ), which we assume here.

-If α > 1/p we set G = (n|s| α,p,∞ ) 1/(2α+1) which leads to a risk bound of the form 2α+1) .

Cn -2α/(2α+1) (|s| α,p,∞ ) (2α+2)/(
-If α = 1/p, L ′ J < Jα/δ + 2 and we take G = (n|s| α,p,∞ / log n) 1/(2α+1) which leads to the risk bound 2δ)] which leads to the bound

C(n/ log n) -2α/(2α+1) (|s| α,p,∞ ) (2α+2)/(2α+1) . -Finally, for α < 1/p, L J ′ < √ 2 2 (Jα/δ)(1/p-α) and we set G = (n|s| α,p,∞ ) 1/[α+1+α/(
Cn -2α/[α+1+α/(2δ)] (|s| α,p,∞ ) (2+(α/δ)/[α+1+α/(2δ)] .

Some lower bounds

Lower bounds of the form n -2α/(1+2α) for the minimax risk on Besov balls are wellknown (deriving from lower bounds for Hölder spaces) and they are sharp for α > 1/p, as shown in Donoho, Johnstone, [START_REF] Donoho | Density estimation by wavelet thresholding Ann[END_REF]. To derive new lower bounds for the case α < 1/p we introduce some probability density f ∈ B α p,∞ ([0, 1]) with compact support included in (0, 1) and Besov semi-norm |f | α p . Then we set g(x) = af (2anx) for some a > (2n) -1 to be fixed later. Then g(x) = 0 for x ∈ 0, (2an) -1 , g q = a(2an) -1/q f q and |g| α p = a(2an) α-1/p |f | α p .

Let us now set

t = g+ 1 -(2n) -1 1l [0,1] , so that t is a density belonging to B α p,∞ ([0, 1]) with Besov semi-norm |t| α p = |g| α p = Ka 1+α-1/p n α-1/p with K = 2 α-1/p |f | α p .
For a given value of the constant K ′ > 0, the choice a = K ′ n 1/p-α 1/(1+α-1/p) > (2n) -1 (at least for n large) leads to |t| α p = KK ′ so that K ′ determines |t| α p . We also consider the density u(x) = t(1x) which has the same Besov semi-norm. Then

h 2 (t, u) = (2an) -1 0 g + [1 -(2n) -1 ] -1 -(2n) -1 2 < (2an) -1 0 g = (2n) -1 ,
and it follows from Le Cam (1973) that any estimator ŝ based on n i.i.d. observations satisfies

max E t t -ŝ 2 , E u u -ŝ 2 ≥ C t -u 2 = 2C g 2 = Can -1 f 2 .
Since an -1 = K ′1/(δ+1/2) n -2δ/(δ+1/2) , we finally get

max E t t -ŝ 2 , E u u -ŝ 2 ≥ C |t| α p 2/(2δ+1) n -4δ/(2δ+1) ,
where C depends on K ′ , f , |f | α p and δ. One can check that this rate is slower than n -2α/(1+2α) , when 0 < δ < α[2(α+1)] -1 or, equivalently, when α+[2(α+1)] -1 < 1/p.

Conclusion

In the case α > 1/p, the estimator that we built in Section 6.4.3 has the usual rate of convergence with respect to n, namely n -2α/(2α+1) , which is known to be optimal, and we can extend the result to the borderline case α = 1/p with only a logarithmic loss. The situation is different when α < 1/p for which, to our knowledge, the value of the minimax risk is still unknown. The rate n -2α/[α+1+α/(2δ)] that we get is worse than the one valid for α > 1/p and also than the lower bound n -4δ/(2δ+1) that we derived in the previous section. It can be compared with the risk of the penalized least squares estimators based on the nested models S ′ q , which is, as we have seen, bounded by Cn -2δ/(2δ+1) . Our rate is better when α > 2δ/(2δ + 1), which is always true for α ≥ 1/2 since δ < 1/2. When α < 1/2, hence p > 2/(2α + 1) > 1, it also holds for p < 2(1α)/ 1 -2α 2 < α -1 . We are convinced that our rate is always suboptimal in the range α ≤ 1/p but are presently unable to derive the correct minimax rate.

Proofs

Proof of Proposition 2

For simplicity, we shall write h(θ, λ) for h(s θ , s λ ) and analogously d 2 (θ, λ) for d 2 (s θ , s λ ). Let us first evaluate h 2 (θ, λ) for 0 < θ < λ ≤ 1/3. Setting

β θ = θ 2 + θ + 1 -1 ∈ [9/13, 1), we get 2h 2 (θ, λ) = and 0 < β θ -β λ = (λ -θ)(λ + θ + 1) (θ 2 + θ + 1)(λ 2 + λ + 1) < λ -θ. (7.1) It follows that 0 < β θ -β λ 2 = (β θ -β λ ) 2 √ β θ + √ β λ 2 < 13
Since 8/9 < 1λ 2 β θ < 1 and, by (7.1),

0 < θλ 2 1 -λ 3 β θ -β λ λ -θ 2 < 1 27 , we conclude that G = θ -1 -λ -1 -1 d 2 2 (θ, λ) = (1 -z)(1 + z) 2 + c 1 (θ, λ) z + z 2 + z 3 + c 2 (θ, λ)(1 -z), with z = θ/λ ∈ (0, 1), 8/9 < c 1 (θ, λ) < 1 and 0 < c 2 (θ, λ) < 1/27. It follows that 1 < 1 + z -z 2 -z 3 + (8/9) z + z 2 + z 3 < G < 1 + 2z + (1/27)(1 -z) < 3,
which finally implies that, for all θ and λ in (0, 1/3], d 2 2 (θ, λ) = C(θ, λ) θ -1λ -1 with 1 < C(θ, λ) < 3. Now setting S η = {s λ j , j ≥ 0} with λ j = 3 + 2jη 2 /3 -1 we deduce as before that S η is an η-net for S. In order that s λ j ∈ B(s λ , xη), it is required that d 2 2 (λ j , λ) = C(θ, λ)|λ -1 jλ -1 | < x 2 η 2 , which implies that |λ -1 jλ -1 | < x 2 η 2 . It follows that the number of elements of S η contained in the ball is bounded by 3x 2 /2 + 1 ≤ exp x 2 /2 for x ≥ 2. Hence the metric dimension of S with respect to the L 2 -distance is bounded by 2. It nevertheless follows from the fact that h(θ, λ) → 0 while d 2 (θ, λ) → +∞ when θ and λ tend to zero and classical arguments [START_REF] Le | Convergence of estimates under dimensionality restrictions[END_REF] -see also [START_REF] Donoho | Geometrizing rates of convergence I[END_REF] or [START_REF] Yu | Assouad, Fano and Le Cam[END_REF] -that the minimax risk over S is infinite when we use the L 2 -loss.

Proof of Lemma 1

Let us begin with a preliminary lemma.

Lemma 2 Let F and G be two disjoint sets with positive measures α = µ(F ) and β = µ(G) and g ∈ L 2 such that inf x∈F g(x) > 0. Set g ε = g + ε(α1l G -β1l F ) for ε > 0. Then g ε is a density for ε small enough and for any f ∈ L 2 , with the convention that G f g -1 dλ = +∞ if either µ(G ∩ {g = 0} ∩ {f > 0}) > 0 or the integral diverges.

Proof: Since g ε dµ = 1 and g ε ≥ 0 for ε small enough g ε is a density. Moreover, setting k = α1l G -β1l F , we get

d 2 2 (g ε , f ) = (g + εk -f ) 2 dµ = d 2 2 (g, f ) + ε 2 k 2 + 2ε k(g -f ) dµ
and (7.2) follows. Let ∆(ε) = ε -1 h 2 (g ε , f )h 2 (g, f ) and fix η > 0. Then

∆(ε) = ε -1 gf dµ - (g + εk)f dµ = ε -1 F gf -(g -εβ)f dµ + G gf -(g + εα)f dµ = F β √ f √ g -εβ + √ g dµ - G∩{g>0} α √ f √ g + εα + √ g dµ - G∩{g=0}∩{f >0}
αf /ε dµ.

When ε tends to 0, the first integral converges to (β/2) F f g -1 dµ and the second one converges to (α/2) G∩{g>0} f g -1 dµ, by monotone convergence. The last one converges to +∞ if µ(G ∩ {g = 0} ∩ {f > 0}) > 0 and 0 otherwise, which achieves the proof of (7.3).

If v 1 ∨ v 2 ∞ > 2B, we may assume, exchanging the roles of v 1 and v 2 if necessary, that µ(A) > 0 with A = {v 1 ≥ v 2 and v 1 > 2B}. Let C = {v 1 < B ∧ v 2 }. If µ(C) > 0, we may apply Lemma 2 with F = A, G = C, g = v 1 and v ′ 1 = g ε . We first set f = t. Since v 1t < B on C while v 1t > B on A, it follows from (7.2) that d 2 (v ′ 1 , t) < d 2 (v 1 , t) for ε small enough. If we now set f = v 2 and use (7.3), we see that h(v ′ 1 , v 2 ) < h(v 1 , v 2 ) since v 2 ≤ v 1 on A and v 2 > v 1 on C. We conclude by setting v ′ 2 = v 2 . If µ(C) = 0, then µ({B ≤ v 1 < v 2 }) + µ({v 2 ≤ v 1 < B}) = 1 and both sets have positive µ-measure since v 1 = v 2 . In this case we set F = {B ≤ v 1 < v 2 }, G = {v 2 ≤ v 1 ∧ u} and g = v 2 . Then µ(F ) > 0 and µ(G) > 0 since u ≤ B < v 2 on F and they are densities. If we use (7.2) with f = u, we derive that d 2 (v ′ 2 , u) < d 2 (v 2 , u) for ε small enough and if we use (7.3) with f = v 1 , we derive that h(v ′ 2 , v 1 ) < h(v 2 , v 1 ), in which case we set v ′ 1 = v 1 .

Proof of Theorem 5

We consider the family of tests ψ(t n , t p , X) = ψ tn,tp,x (X) provided by the assumption with x = A|p-n|. Given this family of tests and S = {t i , i ≥ 1}, we define the random function D X on S as in Birgé (2006a), i.e. we set R i = {t j ∈ S, j = i | ψ(t i , t j , X) = t j } and

D X (t i ) =    sup t j ∈R i d(t i , t j ) if R i = ∅; 0 if R i = ∅.
(7.4) Given some t i ∈ S, we want to bound P s D X (t i ) > xy i for x ≥ 1 and y i = 4d(s, t i ) ∨ √ Aa -1 i2 i .

Let us define the integer K by x 2 < 2 K ≤ 2x 2 . Then K ≥ 1, a2 -i-K (xy i ) 2 ≥ a2 -i-1 y 2 i ≥ Ai/2 and e -AK ≤ x

29

≤ B e -A 1e -A exp -Ai x 2 -1 ≤ B e -A 1e -A exp -A x 2 -1 ≤ B 1e -A -1 exp -Ax 2 ≤ B 1e -A -1 x -2A/ log 2 , where we used (7.5), i ≥ 1 and x ≥ 1. Also, by (5.1), Σ 2 ≤ B j>i 1l d(t i ,t j )>y exp -a2 -j d 2 (t i , t j ) -A|i -j| exp -2 j-1j < 3e -AK .

We finally get, putting all the bounds together and using (7.5) again, In view of the definition of D X , d(t i , t j ) ≤ D X (t i ) ∨ D X (t j ), hence, for all t i ∈ S, d (ŝ A , t i ) ≤ D X (t i ) + √ Aa -1 and d (ŝ A , s) ≤ D X (t i ) + √ Aa -1 + d(s, t i ) < D X (t i ) + y i .

It then follows from (7.6) that P s [d (ŝ A , s) > zy i ] ≤ BC(A)(z -1) -2A/ log 2 for z ≥ 2.

Integrating with respect to z leads to E s [(d (ŝ A , s) /y i ) q ] ≤ BC(A, q) for 1 ≤ q < 2A/ log 2, and, since t i is arbitrary in S, E s [d q (ŝ A , s)] ≤ BC(A, q) inf i≥1 d q (s, t i ) ∨ a -1 i2 i q/2 for 1 ≤ q < 2A/ log 2.

  6) ofBirgé (2006a) with d = d 2 , we just have to show that Theorem 5 of this paper applies to our situation. It relies on Assumptions 1 and 3 of the paper. Assumption 3 follows from (3.7). As to Assumption 1 (with a = n/(65Γ), B = B ′ = 1 and δ = 4d 2 , hence κ = 4), it is a consequence of our Theorem 2. The conditions (7.2) and (7.4) of Birgé (2006a) on η m and D m follow from (3.8).In the case of a single D-dimensional model S ⊂ L Γ ∞ we get the following corollary:Corollary 2 Assume that we observe n i.i.d. random variables with unknown distribution P s , s ∈ L 2 , d 2 and that we have at disposal a D-dimensional model S ⊂ L Γ ∞

  First note that the existence of γ follows from the continuity and monotonicity of the mapping z → [(t + z) ∨ 0] ∧ Γ dµ and that π Γ (t) ∈ L Γ ∞ . Since L Γ ∞ is a closed convex subset of a Hilbert space, the projection operator π onto L Γ ∞ exists and is characterized by the fact that

  ) which should be compared with (1.3). Apart from the unavoidable complexity term ∆ m due to model selection, we have only lost (up to the universal constant C) the replacement of |I m | by |I m | ∨ log s ∞ . Examples of families of partitions that satisfy (3.10) are given in Section 9 of Birgé (2006a).

F

  g ε , f )h 2 (g, f ) = β

  -j y 2 -A(ji) = B +∞ k=1 exp -a2 -i-k y 2 -Ak ≤ B K k=1 exp -a2 -i-k y 2 -Ak + k>K exp[-Ak] = B(Σ 3 + Σ 4 ), with Σ 4 = e -AK e A -1-1 and, by (7.5),Σ 3 = e -AK K-1 j=0 exp -a2 -i-K+j y 2 + Aj ≤ e -AK K-1 j=0 exp -A(i2 j-1j) ≤ e -AK j≥0

P

  s D X (t i ) > xy i ≤ BC(A)x -2A/ log 2 for x ≥ 1. (7.6)As a consequence D X (t i ) < +∞ a.s. and we can define ŝA = t p with p = min j D X (t j ) < inf i D X (t i ) + √ Aa -1 .

  -2A/ log 2 . (7.5) Now, setting y = xy i , observe thatP s D X (t i ) > y = P s [ ∃j with d(t i , t j ) > y and ψ(t i , t j , X) = t j ] ≤ Σ 1 + Σ 2 , ,t j )>y P s [ψ(t i , t j , X) = t j ] ; Σ 2 = j>i 1l d(t i ,t j )>y P s [ψ(t i , t j , X) = t j ] .If i = 1, then Σ 1 = 0 and if i ≥ 2, we can use (5.2) and y ≥ 4d(s, t i ) to derive thatΣ 1 ≤ B j<i 1l d(t i ,t j )>y exp -a2 -i d 2 (t i , t j ) + A|i -j| ≤ B exp -a2 -i y 2 i x 2 + Ai

	with
	Σ 1 =

j<i 1l d(t i j≥1 e -Aj

that satisfy (3.7). Unfortunately, they cannot simply be derived by a discretization of S followed by a projection π Γ or a discretization of π Γ S . A more complicated construction is required to preserve both the metric and approximation properties of S. It is provided by the following preliminary result.

j+1 ∞

< 1, β θ + β λ > 2 β 1/3 = 6/ √ 13