Yannick Baraud

Lucien Birgé

Estimating composite functions by model selection Revised version

Keywords: classifications. Primary 62G05 Curve estimation, model selection, composite functions

We consider the problem of estimating a function s on [-1, 1] k for large values of k by looking for some best approximation of s by composite functions of the form g • u. Our solution is based on model selection and leads to a very general approach to solve this problem with respect to many different types of functions g, u and statistical frameworks. In particular, we handle the problems of approximating s by additive functions, single and multiple index models, neural networks, mixtures of Gaussian densities (when s is a density) among other examples. We also investigate the situation where s = g • u for functions g and u belonging to possibly anisotropic smoothness classes. In this case, our approach leads to a completely adaptive estimator with respect to the regularity of s.

0 AMS 1991 subject

Introduction

In various statistical problems, we have at hand a random mapping X from a measurable space (Ω, A) to (X, X ) with an unknown distribution P s on X depending on some parameter s ∈ S which is a function from [-1, 1] k to R. For instance, s may be the density of an i.i.d. sample or the intensity of a Poisson process on [-1, 1] k or a regression function. The statistical problem amounts to estimating s by some estimator s = s(X) the performance of which is measured by its quadratic risk, R(s, s) = E s d 2 (s, s) , where d denotes a given distance on S. To be more specific, we shall assume in this introduction that X = (X 1 , . . . , X n ) is a sample of density s 2 (with s ≥ 0) with respect to some measure µ and d is the Hellinger distance. We recall that, given two probabilities P, Q dominated by µ with respective densities f = dP/dµ and g = dQ/dµ, the Hellinger distance h between P and Q or, equivalently, between f and g (since it is independant of the choice of µ) is given by

h 2 (P, Q) = h 2 (f, g) = 1 2 f - √ g 2 dµ.
(1.1)

It follows that √ 2d(s, t) is merely the L 2 -distance between s and t. A general method for constructing estimators s is to choose a model S for s, i.e. do as if s belonged to S, and to build s as an element of S. Sometimes the statistician really assumes that s belongs to S and that S is the true parameter set, sometimes he does not and rather considers S as an approximate model. This latter approach is somewhat more reasonable since it is in general impossible to be sure that s does belong to S. Given S and a suitable estimator s, as those built in [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF] for example, one can achieve a risk bound of the form

R(s, s) ≤ C inf t∈S d 2 (s, t) + τ D(S) , (1.2)
where C is a universal constant (independent of s and S), D(S) the dimension of the model S (with a proper definition of the dimension) and τ , which is equal to 1/n in the specific context of density estimation, characterizes the amount of information provided by the observation X.

It is well-known that many classical estimation procedures suffer from the so-called "curse of dimensionality", which means that the risk bound (1.2) deteriorates when k increases and actually becomes very loose for even moderate values of k. This phenomenon is easy to explain and actually connected with the most classical way of choosing models for s. Typically, and although there is no way to check that such an assumption is true, one assumes that s belongs to some smoothness class (Hölder, Sobolev or Besov) of index α and such an assumption can be translated in terms of approximation properties with respect to the target function s of a suitable collection of linear spaces (generated by piecewise polynomials, splines, or wavelets for example). More precisely, there exists a collection S of models with the following property: for all D ≥ 1, there exists a model S ∈ S with dimension D which approximates s with an error bounded by cD -α/k for some c independent of D (but depending on s, α and k). With such a collection at hand, we deduce from (1.2) that whatever D ≥ 1 one can choose a model S = S(D) ∈ S for which the estimator s ∈ S achieves a risk bounded from above by C c 2 D -2α/k + τ D . Besides, by using the elementary Lemma 1 below to be proved in Section 5.6, one can optimize the choice of D, and hence of the model S in S, to build an estimator whose risk satisfies R(s, s) ≤ C max 3c 2k/(2α+k) τ 2α/(2α+k) ; 2τ .

(1.3)

Lemma 1 For all positive numbers a, b and θ and N ⋆ the set of positive integers, inf D∈N ⋆ {aD -θ + bD} ≤ b + min 2a 1/(θ+1) b θ/(θ+1) ; a ≤ max 3a 1/(θ+1) b θ/(θ+1) ; 2b .

Since the risk bound (1.3) is achieved for D of order τ -k/(2α+k) , as τ tends to 0, the deterioration of the rate τ 2α/(2α+k) when k increases comes from the fact that we use models of larger dimension to approximate s when k is large. Nevertheless, this phenomenon is only due to the previous approach based on smoothness assumptions for s. An alternative approach, assuming that s can be closely approximated by suitable parametric models the dimensions of which do not depend on k would not suffer from the same weaknesses. More generally, a structural assumption on s associated to a collection of models S ′ , the approximation properties of which improve on those of S, can only lead to a better risk bound and it is not clear at all that assuming that s belongs to a smoothness class is more realistic than directly assuming approximation bounds with respect to the models of S ′ . Such structural assumptions that would amount to replacing the large models involved in the approximation of smooth functions by simpler ones have been used for many years, especially in the context of regression. Examples of such structural assumptions are provided by additive models, the single index model, the projection pursuit algorithm introduced by [START_REF] Friedman | A projection pursuit algorithm for exploratory data analysis[END_REF], (an overview of the procedure is available in [START_REF] Huber | Projection pursuit[END_REF]) and artificial neural networks as in [START_REF] Barron | Universal approximation bounds for superpositions of a sigmoidal function[END_REF][START_REF] Barron | Approximation and estimation bounds for artificial neural networks[END_REF], among other examples. It actually appears that a large number of these alternative approaches (in particular those we just cited) can be viewed as examples of approximation by composite functions.

In any case, an unattractive feature of the previous approach based on an a priori choice of a model S ∈ S is that it requires to know suitable upper bounds on the distances between s and the models S in S. Such a requirement is much too strong and an essential improvement can be brought by the modern theory of model selection. More precisely, given some prior probability π on S, model selection allows to build an estimator s with a risk bound CR(s, s) ≤ inf S∈S inf t∈S d 2 (s, t) + τ D(S) + log 1/π(S) , (1.4) for some universal constant C > 0. If we neglect the influence of log (1/π(S)), which is connected to the complexity of the family S of models we use, the comparison between (1.2) and (1.4) indicates that the method selects a model in S leading approximately to the smallest risk bound.

With such a tool at hand that allows us to play with many models simultaneously and let the estimator choose a suitable one, we may freely introduce various models corresponding to various sorts of structural assumptions on s that avoid the "curse of dimensionality". We can, moreover, mix them with models which are based on pure smoothness assumptions that do suffer from this dimensional effect or even with simple parametric models. This means that we can so cumulate the advantages of the various models we introduce in the family S.

The main purpose of this paper is to provide a method for building various sorts of models that may be used, in conjonction with other ones, to approximate functions on [-1, 1] k for large values of k. The idea, which is not new, is to approximate the unknown s by a composite function g • u where g and u have different approximation properties. If, for instance, the true s can be closely approximated by a function g • u where u goes from [-1, 1] k to [-1, 1] and is very smooth and g, from [-1, 1] to R, is rough, the overall smoothness of g • u is that of g but the curse of dimensionality only applies to the smooth part u, resulting in a much better rate of estimation than what would be obtained by only considering g • u as a rough function from [-1, 1] k to R. This is an example of the substantial improvement that might be brought by the use of models of composite functions.

Recent works in this direction can be found in [START_REF] Horowitz | Rate-optimal estimation for a general class of nonparametric regression models with unknown link functions[END_REF] or [START_REF] Juditsky | Nonparametric estimation of composite functions[END_REF]. Actually, our initial motivation for this research was a series of lectures given at CIRM in 2005 by Oleg Lepski about a former version of this last paper. There are, nevertheless, major differences between their approach and ours. They deal with estimation in the white noise model, kernel methods and the L ∞ -loss. They also assume that the true unknown density s to be estimated can be written as s = g • u where g and u have given smoothness properties and use these properties to build a kernel estimator which is better than those based on the overall smoothness of s. The use of the L ∞ -loss indeed involves additional difficulties and the minimax rates of convergence happen to be substantially slower (not only by logarithmic terms) than the rates one gets for the L 2 -loss, as the authors mention on page 1369, comparing their results with those of [START_REF] Horowitz | Rate-optimal estimation for a general class of nonparametric regression models with unknown link functions[END_REF].

Our approach is radically different from the one of Juditsky, Lepski and Tsybakov and considerably more general as we shall see, but this level of generality has a price. While they provide a constructive estimator that can be computed in a reasonable amount of time, although based on supposedly known smoothness properties of g and u, we offer a general but abstract method that applies to many situations but does not provide practical estimators, only abstract ones. As a consequence, our results about the performance of these estimators are of a theoretical nature, to serve as benchmarks about what can be expected from good estimators in various situations.

We actually consider "curve estimation" with an unknown functional parameter s and measure the loss by L 2 -type distances. Our construction applies to various statistical frameworks (not only the Gaussian white noise but also all these for which a suitable model selection theorem is available). Besides, we do not assume that s = g • u but rather approximate s by functions of the form g • u and do not fix in advance the smoothness properties of g and u but rather let our estimator adapt to it. In order to give a simple account of our result, let us focus on pairs (u, g) with

u mapping [-1, 1] k into [-1, 1] and g [-1, 1] into R.
In this case, our main theorem says the following: consider two (at most) countable collections of models T and F, endowed with the probabilities λ and γ respectively, in order to approximate such functions u and g respectively. There exists an estimator s such that, whatever the choices of u and g with g at least L-Lipschitz for some L > 0,

C ′ (L)R(s, s) ≤ d 2 (s, g • u) + inf F ∈F inf f ∈F d 2 ∞ (g, f ) + τ [D(F ) + log(1/γ(F ))] + inf T ∈T inf t∈T d 2 (u, t) + τ D(T ) log τ -1 + log(1/λ(T )) , (1.5)
where d ∞ denotes the distance based on the supremum norm. Compared to (1.4), this result says that, apart from the extra logarithmic terms and the constant C ′ depending on L, if s were of the form g • u the risk bound we get for estimating s is the maximum of those we would get for estimating g and u separately from a model selection procedure based on (F, γ) and (T, λ) respectively. A more general version of (1.5) allowing to handle less regular functions g and multivariate functions u = (u 1 , . . . , u l ) with values in [-1, 1] l is available in Section 3. As a consequence, our approach leads to a completely adaptive method with many different possibilities to approximate s. It allows, in particular, to play with the smoothness properties of g and u or to mix purely parametric models with others based on smooth functions. Since methods and theorems about model selection are already available, our main task here will be to build suitable models for various forms of composite functions g • u and check that they do satisfy the assumptions required for applying previous model selection results.

Our statistical framework

We observe a random element X from the probability space (Ω, A, P s ) to (X, X ) with distribution P s on X depending on an unknown parameter s. The set S of possible values of s is a subset of some space L q (E, µ) where µ is a given probability on the measurable space (E, E). We shall mainly consider the case q = 2 even though one can also take q = 1 in the context of density estimation. We denote by d the distance on L q (E, µ) corresponding to the L q (E, µ)-norm • q (omitting the dependency of d with respect to q) and by E s the expectation with respect to P s so that the quadratic risk of an estimator s is E s d 2 (s, s) . The main objective of this paper, in order to estimate s by model selection, is to build special models S that consist of functions of the form f • t where t = (t 1 . . . , t l ) is a mapping from E to I ⊂ R l , f is a continuous function on I and I = l j=1 I j is a product of compact intervals of R. Without loss of generality, we may assume that I = [-1, 1] l . Indeed, if l = 1, t takes its values in I 1 = [βα, β + α], α > 0 and f is defined on I 1 , we can replace the pair (f, t) by ( f , t) where t(x) = α -1 [t(x)β] and f (y) = f (αy + β) so that t takes its values in [-1, 1] and f • t = f • t. The argument easily extends to the multidimensional case.

Notations and conventions

To perform our construction based on composite functions f • t, we introduce the following spaces of functions :

T ⊂ L q (E, µ) is the set of measurable mappings from E to [-1, 1], F l,∞ is the set of bounded functions on [-1, 1] l endowed with the distance d ∞ given by d ∞ (f, g) = sup x∈[-1,1] l |f (x) -g(x)
| and F l,c is the subset of F l,∞ which consists of continuous functions on [-1, 1] l . We denote by N ⋆ (respectively, R ⋆ + ) the set of positive integers (respectively positive numbers) and set

⌊z⌋ = sup{j ∈ Z | j ≤ z} and ⌈z⌉ = inf{j ∈ N ⋆ | j ≥ z}, for all z ∈ R.
The numbers x ∧ y and x ∨ y stand for min{x, y} and max {x, y} respectively and log + (x) stands for (log x) ∨ 0. The cardinality of a set A is denoted by |A| and, by convention, "countable" means "finite or countable". We call subprobability on some countable set A any positive measure π on A with π(A) ≤ 1 and, given π and a ∈ A, we set π(a) = π({a}) and ∆ π (a) =log(π(a)) with the convention ∆ π (a) = +∞ if π(a) = 0. The dimension of the linear space V is denoted by D(V ). Given a compact subset K of R k with • K = ∅, we define the Lebesgue probability µ on K by µ(A) = λ(A)/λ(K) for A ⊂ K, where λ denotes the Lebesgue measure on R k .

For x ∈ R m , x j denotes the j th coordinate of x (1 ≤ j ≤ m) and, similarly, x i,j denotes the j th coordinate of x i if the vectors x i are already indexed. We set |x| 2 = m j=1 x 2 j for the squared Euclidean norm of x ∈ R m , without reference to the dimension m, and denote by B m the corresponding closed unit ball in R m . Similarly, |x| ∞ = max{|x 1 |, . . . , |x m |} for all x ∈ R m . For x in some metric space (M, d) and r > 0, B(x, r) denotes the closed ball of center x and radius r in M and for A ⊂ M , d(x, A) = inf y∈A d(x, y). Finally, C stands for a universal constant while C ′ is a constant that depends on some parameters of the problem. We may make this dependence explicit by writing C ′ (a, b) for instance. Both C and C ′ are generic notations for constants that may change from line to line.

A general model selection result

General model selection results apply to models which possess a finite dimension in a suitable sense. Throughout the paper, we assume that in the statistical framework we consider the following theorem holds.

Theorem 1 Let S be a countable family of finite dimensional linear subspaces S of L q (E, µ) and let π be some subprobability measure on S. There exists an estimator s = s(X) with values in ∪ S∈S S satisfying, for all s ∈ S,

E s d 2 (s, s) ≤ C inf S∈S d 2 (s, S) + τ (D(S) ∨ 1) + ∆ π (S) , (2.1)
where the positive constant C and parameter τ only depend on the specific statistical framework at hand.

Similar results often hold also for the loss function d r (s, s) (r ≥ 1) replacing d 2 (s, s).

In such a case, the results we prove below for the quadratic risk easily extend to the risk E s [d r (s, s)]. For simplicity, we shall only focus on the case r = 2.

Some illustrations

The previous theorem actually holds for various statistical frameworks. Let us provide a partial list.

Gaussian frameworks A prototype for Gaussian frameworks is provided by some Gaussian isonormal linear process as described in Section 2 of [START_REF] Birgé | Gaussian model selection[END_REF]. In such a case, X is a Gaussian linear process with a known variance τ , indexed by a subset S of some Hilbert space L 2 (E, µ). This means that s ∈ S determines the distribution P s . Regression with Gaussian errors and Gaussian sequences can both be seen as particular cases of this framework. Then Theorem 1 is a consequence of Theorem 2 of [START_REF] Birgé | Gaussian model selection[END_REF]. In the regression setting, [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF] considered the practical case of an unknown variance and proved that (2.1) holds under the assumption that D(S) ∨ ∆ π (S) ≤ n/2 for all S ∈ S.

Density estimation Here X = (X 1 , . . . , X n ) is an n-sample with density s 2 with respect to µ and S is the set of nonnegative elements of norm 1 in L 2 (E, µ). Then d(s, t) = √ 2h s 2 , t 2 where h denotes the Hellinger distance between densities defined by (1.1), τ = n -1 and Theorem 1 follows from Theorem 6 of [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF] or Corollary 8 of [START_REF] Baraud | Estimator selection with respect to Hellinger-type risks[END_REF]. Alternatively, one can take for s the density itself, for S the set of nonnegative elements of norm 1 in L 1 (E, µ) and set q = 1. The result then follows from Theorem 8 of [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF]. Under the additional assumption that s ∈ L 2 (E, µ) ∩ L ∞ (E, µ), the case q = 2 follows from Theorem 6 of [START_REF] Birgé | Model selection for density estimation with L 2 -loss[END_REF] with

τ = n -1 s ∞ (1 ∨ log s ∞ ).
Regression with fixed design We observe

X = {(x 1 , Y 1 ), . . . , (x n , Y n )} with E[Y i ] = s(x i ) where s is a function from E = {x 1 , . . . , x n } to R and the errors ε i = Y i -s(x i ) are i.i.d. Here µ is the uniform distribution on E, hence d 2 (s, t) = n -1 n i=1 [s(x i )-t(x i )]
2 and τ = 1/n. When the errors ε i are subgaussian, Theorem 1 follows from Theorem 3.1 in [START_REF] Baraud | Model selection for (auto-)regression with dependent data[END_REF]. For more heavytailed distributions (Laplace, Cauchy, etc.) we refer to Theorem 6 of [START_REF] Baraud | Estimator selection with respect to Hellinger-type risks[END_REF] when s takes its values in [-1, 1].

Bounded regression with random design Let (X, Y ) be a pair of random variables with values in E × [-1, 1] where X has distribution µ and

E[Y |X = x] = s(x) is a function from E to [-1, 1].
Our aim here is to estimate s from the observation of n independent copies X = {(X 1 , Y 1 ), . . . , (X n , Y n )} of (X, Y ). Here the distance d corresponds to the L 2 (E, µ)-distance and Theorem 1 follows from Corollary 8 in [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF] with τ = n -1 .

Poisson processes In this case, X is a Poisson process on E with mean measure s 2 • µ, where s is a nonnegative element of L 2 (E, µ). Then τ = 1 and Theorem 1 follows from [START_REF] Birgé | Model selection for Poisson processes[END_REF] or Corollary 8 of [START_REF] Baraud | Estimator selection with respect to Hellinger-type risks[END_REF].

3 The basic theorems

Models and their dimensions

If we assume that the unknown parameter s to be estimated is equal or close to some composite function of the form g•u with u ∈ T l and g ∈ F l,c and if we wish to estimate g • u by model selection we need to have at disposal a family F of models for approximating g and families T j , 1 ≤ j ≤ l, to approximate the components u j of u. Typical sets that are used for approximating elements of F l,c or T l are finite-dimensional linear spaces or subsets of them. Many examples of such spaces are described in books on Approximation Theory, like the one by DeVore and Lorentz (1993) and we need a theorem which applies to such classical approximation sets for which it will be convenient to choose the following definition of their dimension.

Definition 1 Let H be a linear space and S ⊂ H. The dimension D(S) ∈ N ∪ {∞} of S is 0 if |S| = 1 and is, otherwise, the dimension (in the usual sense) of the linear span of S.

Some smoothness assumptions

In order to transfer the approximation properties of g by f and u by t into approximation of g • u by f • t, we shall also require that g be somewhat smooth. The smoothness assumptions we need can be expressed in terms of moduli of continuity. We start with the definition of the modulus of continuity of a function g in F l,c .

Definition 2 We say that w from [0, 2] l to R l + is a modulus of continuity for a continuous function g on [-1, 1] l if, for all z ∈ [0, 2] l , w(z) is of the form w(z) = (w 1 (z 1 ), . . . , w l (z l )) where each function w j with j = 1, . . . , l is continuous, nondecreasing and concave from [0, 2] to R + , satisfies w j (0) = 0, and

|g(x) -g(y)| ≤ l j=1 w j (|x j -y j |) for all x, y ∈ [-1, 1] l .
For α ∈ (0, 1] l and L ∈ (0, +∞) l , we say that g is (α, L)-Hölderian if one can take

w j (z) = L j z α j for all z ∈ [0, 2] and j = 1, . . . , l. It is said to be L-Lipschitz if it is (α, L)-Hölderian with α = (1, . . . , 1).
Note that our definition of a modulus of continuity implies that the w j are subadditive, a property which we shall often use in the sequel and that, given g, one can always choose for w j the least concave majorant of w j where

w j (z) = sup x∈[-1,1] l ; x j ≤1-z |g(x) -g(x 1 , . . . , x j-1 , x j + z, x j+1 , . . . , x l )|.
Then w j (z) ≤ 2w j (z) according to Lemma 6.1 p. 43 of DeVore and Lorentz (1993).

The main theorem

Our construction of estimators s of g • u will be based on some set S of the following form:

S = {l, F, γ, T 1 , . . . , T l , λ 1 , . . . , λ l }, l ∈ N ⋆ , (3.1)
where F, T 1 , . . . , T l denote families of models and γ, λ j are measures on F and T j respectively. In the sequel, we shall assume that S satisfies the following requirements.

Assumption 1 The set S is such that i) the family F is a countable set and consists of finite-dimensional linear subspaces

F of F l,∞ with respective dimensions D(F ) ≥ 1, ii) for j = 1, . . . , l, T j is a countable set of subsets of L q (E, µ) with finite dimen- sions,
iii) the measure γ is a subprobability on F, iv) for j = 1, . . . , l, λ j is a subprobability on T j .

Given S, one can design an estimator s with the following properties.

Theorem 2 Assume that Theorem 1 holds and that S satisfies Assumption 1. One can build an estimator s = s(X) satisfying, for all u ∈ T l and g ∈ F l,c with modulus of continuity w g ,

CE s d 2 (s, s)) ≤ l j=1 inf T ∈T j lw 2 g,j d(u j , T ) + τ ∆ λ j (T ) + i(g, j, T )D(T ) + d 2 (s, g • u) + inf F ∈F d 2 ∞ (g, F ) + τ [∆ γ (F ) + D(F )] , (3.2) where i(g, j, T ) = 1 if D(T ) = 0 and otherwise, i(g, j, T ) = inf i ∈ N ⋆ | lw 2 g,j e -i ≤ τ iD(T ) < +∞. (3.3)
Note that, since the risk bound (3.2) is valid for all g ∈ F l,c and u ∈ T l , we can minimize the right-hand side of (3.2) with respect to g and u in order to optimize the bound. The proof of this theorem is postponed to Section 5.4. Of special interest is the case where g is L-Lipschitz. If one is mainly interested by the dependence of the risk bound with respect to τ as it tends to 0, one can check that i(g, j, T ) ≤ log τ -1 for τ small enough (depending on l and L) so that (3.2) becomes for such a small τ

C ′ E s d 2 (s, s) ≤ l j=1 inf T ∈T j d 2 (u j , T ) + τ ∆ λ j (T ) + D(T ) log τ -1 +d 2 (s, g • u) + inf F ∈F d 2 ∞ (g, F ) + τ [D(F ) + ∆ γ (F )] .
If it were possible to apply Theorem 1 to the models F with the distance d ∞ and the models T with the distance d for each j separately, we would get risk bounds of this form, apart from the value of C ′ and the extra log τ -1 factor. This means that, apart from this extra logarithmic factor, our procedure amounts to performing l + 1 separate model selection procedures, one with the collection F for estimating g and the other ones with the collections T j for the components u j , finally getting the sum of the l + 1 resulting risk bounds. The result is however slightly different when g is no longer Lipschitz. When g is (α,L)-Hölderian then one can check that i(g, j, T ) ≤ L j,T where L

j,T = 1 if D(T ) = 0 and, if D(T ) ≥ 1, L j,T = α -1 j log lL 2 j [τ D(T )] -1 1 (3.4) ≤ C ′ (l, α j ) log(τ -1 ) ∨ log(L 2 j /D(T )) ∨ 1 . (3.5)
In this case, Theorem 2 leads to the following result.

Corollary 1 Assume that the assumptions of Theorem 2 holds. For all (α, L)-Hölderian function g with α ∈ (0, 1] l and L ∈ (R ⋆ + ) l , the estimator s of Theorem 2 satisfies

CE s d 2 (s, s) ≤ l j=1 inf T ∈T j lL 2 j d 2α j (u j , T ) + τ ∆ λ j (T ) + D(T )L j,T + d 2 (s, g • u) + inf F ∈F d 2 ∞ (g, F ) + τ [∆ γ (F ) + D(F )] , (3.6)
where L j,T is defined by (3.4) and bounded by (3.5).

Mixing collections corresponding to different values of l

If it is known that s takes the special form g • u for some unknown values of g ∈ F l,c and u ∈ T l , or if s is very close to some function of this form, the previous approach is quite satisfactory. If we do not have such an information, we may apply the previous construction with several values of l simultaneously, approximating s by different combinations g l • u l with u l taking its values in [-1, 1] l , g l a function on [-1, 1] l and l varying among some subset I of N ⋆ . To each value of l we associate, as before, l + 1 collections of models and the corresponding subprobabilities, each l then leading to an estimator s l the risk of which is bounded by R( s l , g l , u l ) given by the right-hand side of (3.2). The model selection approach allows us to use all the previous collections of models for all values of l simultaneously in order to build a new estimator the risk of which is approximately as good as the risk of the best of the s l . More generally, let us assume that we have at hand a countable family {S ℓ , ℓ ∈ I} of sets S ℓ of the form (3.1) satisfying Assumption 1 for some l = l(ℓ) ≥ 1. To each such set, Theorem 2 associates an estimator s ℓ with a risk bounded by

E s d 2 (s, s ℓ ) ≤ inf (g,u) R( s ℓ , g, u),
where R( s ℓ , g, u) denotes the right-hand side of (3.2) when S = S ℓ and the infimum runs among all pairs (g, u) with g ∈ F l(ℓ),c and u ∈ T l(ℓ) . We can then prove (in Section 5.5 below) the following result.

Theorem 3 Assume that Theorem 1 holds and let I be a countable set and ν a subprobability on I. For each ℓ ∈ I we are given a set S ℓ of the form (3.1) that satisfies Assumption 1 with l = l(ℓ) and a corresponding estimator s ℓ provided by Theorem 2. One can then design a new estimator s = s(X) satisfying

CE s d 2 (s, s) ≤ inf ℓ∈I inf (g,u) {R( s ℓ , g, u) + τ ∆ ν (ℓ)} ,
where R( s ℓ , g, u) denotes the right-hand side of (3.2) when S = S ℓ and the second infimum runs among all pairs (g, u) with g ∈ F l(ℓ),c and u ∈ T l(ℓ) .

The main ideas underlying our construction

Let us assume here that p = q = 2 and E = [-1, 1] k with k > l ≥ 1. Our approach is based on the construction of a family of linear spaces with good approximation properties with respect to composite functions g • u. More precisely, if one considers a finite dimensional linear space F ⊂ F l,∞ for approximating g and compact sets T j ⊂ T for approximating the u j , we shall show (see Proposition 4 in Section 5.1 below) that there exists some t in T = l j=1 T j such that the linear space

S t = {f • t | f ∈ F } approximates the composite function g • u with an error bound d(g • u, S t ) ≤ d ∞ (g, F ) + √ 2 l j=1 w g,j (d(u j , T j )) . (3.7)
The case where the function g is Lipschitz, i.e. w g,j (x) = Lx for all j, is of particular interest since, up to constants, the error bound we get is the sum of those for approximating separately g by F (with respect to the L ∞ -distance) and the u j by T j . In particular, if s were exactly of the form s = g • u for some known functions u j , we could use a linear space F of piecewise constant functions with dimension of order D to approximate g, and take T j = {u j } for all j. In this case the linear space S u whose dimension is also of order D would approximate s = g • u with an error bounded by D -1/l . Note that if the u j were all (β, L)-Hölderian with β ∈ (0, 1] k , the overall regularity of the function s = g • u could not be expected to be better than β-Hölderian, since this regularity is already achieved by taking g(y 1 , . . . , y l ) = y 1 . In comparison, an approach based on the overall smoothness of s, which would completely ignore the fact that s = g • u and the knowledge of the u j , would lead to an approximation bound of order

D -β/k with β = k k j=1 β -1 j -1
. The former bound, D -1/l , based on the structural assumption that s = g • u therefore improves on the latter since β ≤ 1 and k > l. Of course, one could argue that the former approach uses the knowledge of the u j , which is quite a strong assumption. Actually, a more reasonable approach would be to assume that u is unknown but close to a parametric set T, in which case, it would be natural to replace the single model S u used for approximating s, by the family of models S T (F ) = {S t | t ∈ T} and, ideally, let the usual model selection techniques select some best linear space among it. Unfortunately, results such as Theorem 1 do not apply to this case, since the family S T (F ) has the same cardinality as T and is therefore typically not countable. The main idea of our approach is to take advantage of the fact that the u j take their values in [-1, 1] so that we can embed T into a compact subset of T l . We may then introduce a suitably discretized version T of T (more precisely, of its embedding) and replace the ideal collection S T (F ) by S T (F ), for which similar approximation properties can be proved. The details of this discretization device will be given in the proofs of our main results. Finally, we shall let both T and F vary into some collections of models and use all the models of the various resulting collections S T (F ) together in order to estimate s at best.

Applications

The aim of this section is to provide various applications of Theorem 2 and its corollaries. We start with a brief overview of more or less classical collections of models commonly used for approximating smooth (and less smooth) functions on [-1, 1] k .

Classical models for approximating smooth functions

Along this section,

d denotes the L 2 -distance in L 2 ([-1, 1] k , 2 -k dx), thus taking q = 2, E = [-1, 1
] k and µ the Lebesgue probability on E. Collections of models with the following property will be of special interest throughout this paper.

Assumption 2 For each D ∈ N the number of elements with dimension D belonging to the collection S is bounded by exp[c(S)(D + 1)] for some nonnegative constant c(S) depending on S only.

Approximating functions in Hölder spaces on [-1, 1] k

When k = 1, a typical smoothness condition for a function s on [-1, 1] is that it belongs to some Hölder space H α ([-1, 1]) with α = r + α ′ , r ∈ N and 0 < α ′ ≤ 1 which is the set of all functions f on [-1, 1] with a continuous derivative of order r satisfying, for some constant L(f ) > 0,

f (r) (x) -f (r) (y) ≤ L(f )|x -y| α ′ for all x, y ∈ [-1, 1].
This notion of smoothness extends to functions

f (x 1 , . . . , x k ) defined on [-1, 1] k , by saying that f belongs to H α ([-1, 1] k ) with α = (α 1 , . . . , α k ) ∈ (0, +∞) k if, viewed as a function of x i only, it belongs to H α i ([-1, 1]) for 1 ≤ i ≤ k with some constant L(f )
independent of both i and the variables x j for j = i. The smoothness of a function s in H α ([-1, 1] k ) is said to be isotropic if the α i are all equal and anisotropic otherwise, in which case the quantity α given by

1 α = 1 k k i=1 1 α i
corresponds to the average smoothness of s. It follows from results in Approximation Theory that functions in the Hölder space H α ([-1, 1] k ) can be well approximated by piecewise polynomials on k-dimensional hyperrectangles. More precisely, our next proposition follows from results in [START_REF] Dahmen | Multidimensional spline approximation[END_REF].

Proposition 1 Let (k, r) ∈ N ⋆ × N.
d(s, S) ≤ inf S∈H k,r (D) d ∞ (s, S) ≤ C ′ 2 (k, r)L(s)D -α/k , for all s ∈ H α ([-1, 1] k ) with sup 1≤i≤k α i ≤ r + 1.

Approximating functions in anisotropic Besov spaces

Anisotropic Besov spaces generalize anisotropic Hölder spaces and are defined in a similar way by using directional moduli of smoothness, just as Hölder spaces are defined using directional derivatives. To be short, a function belongs to an anisotropic Besov space on [-1, 1] k if, when all coordinates are fixed apart from one, it belongs to a Besov space on [-1, 1]. A precise definition (restricted to k = 2 but which can be generalized easily) can be found in [START_REF] Hochmuth | Wavelet characterizations for anisotropic Besov spaces[END_REF]. The general definition together with useful approximation properties by piecewise polynomials can be found in [START_REF] Akakpo | Adaptation to anisotropy and inhomogeneity via dyadic piecewise polynomial selection[END_REF]. For 0 < p ≤ +∞, k > 1 and β ∈ (0, +∞) k , let us de- [START_REF] Akakpo | Adaptation to anisotropy and inhomogeneity via dyadic piecewise polynomial selection[END_REF] that Proposition 1 can be generalized to Besov spaces in the following way.

note by B β p,p ([-1, 1] k ) the anisotropic Besov spaces. In particular, B β ∞,∞ ([-1, 1] k ) = H β ([-1, 1] k ). It follows from
Proposition 2 Let p > 0, k ∈ N ⋆ and r ∈ N. There exists a collection of models B k,r = D≥1 B k,r (D) satisfying Assumption 2 such that for each positive integer D, B k,r (D) consists of linear spaces S with dimensions D(S) ≤ C ′ 1 (k, r)D spanned by piecewise polynomials of degree at most r on k-dimensional hyperrectangles and for which inf

S∈B k,r (D) d(s, S) ≤ C ′ 2 (k, r, p) |s| β,p,p D -β/k for all s ∈ B β p,p ([-1, 1] k ) with semi-norm |s| β,p,p and β satisfying sup 1≤i≤k β i < r + 1 and β > k p -1 -2 -1 ∨ 0 . (4.1)

Estimation of smooth functions on [-1, 1] k

In this section, our aim is to establish risk bounds for our estimator s when s = g • u for some smooth functions g and u. We shall discuss the improvement, in terms of rates of convergence as τ tends to 0, when assuming such a structural hypothesis, as compared to a pure smoothness assumption on s. Throughout this section, we take

q = 2, E = [-1, 1] k and d as the L 2 -distance on L 2 (E, 2 -k dx).
It follows from Section 4.1 that, for all r ≥ 0, H k,r satisfies Assumption 2 for some constant c(H k,r ). Therefore the measure γ on H k,r defined by

∆ γ (S) = (c(H k,r ) + 1)(D + 1) for all S ∈ H k,r (D) \ 1≤D ′ <D H k,r (D ′ ) (4.2) is a subprobability since S∈H k,r e -∆γ (S) ≤ D≥1 e -D H k,r (D) e -c(H k,r )(D+1) ≤ D≥1 e -D < 1.
We shall similarly consider the subprobability λ defined on B k,r by

∆ λ (S) = (c(B k,r ) + 1)(D + 1) for all S ∈ B k,r (D) \ 1≤D ′ <D B k,r (D ′ ). (4.3) Finally, for g ∈ H α ([-1, 1] l ) = B α ∞,∞ ([-1, 1] l ) with α ∈ (R ⋆ + ) l , we set g α,∞ = |g| α,∞,∞ + inf L ′
where the infimum runs among all numbers L ′ for which w g,j (z) ≤ L ′ z α j ∧1 for all z ∈ [0, 2] and j = 1, . . . , l.

Convergence rates using composite functions

Let us consider here the set S k,l (α, β, p, L, R) gathering the composite functions

g • u with g ∈ H α ([-1, 1] l ) satisfying g α,∞ ≤ L and u j ∈ B
β j p j ,p j with semi-norms |u j | β j ,p j ,p j ≤ R j for all j = 1, . . . , l. The following result holds.

Theorem 4 Assume that Theorem 1 holds with q = 2. There exists an estimator s such that, for all l ≥ 1, α, R

∈ (R ⋆ + ) l , L > 0, β 1 , . . . , β l ∈ (R ⋆ + ) k and p ∈ (0, +∞] l with β j > k p -1 j -2 -1 ∨ 0 for 1 ≤ j ≤ l, sup s∈S k,l (α,β,p,L,R) C ′ E s d 2 (s, s) ≤ l j=1 LR α j ∧1 j 2k 2β j (α j ∧1)+k [τ L] 2β j (α j ∧1) 2β j (α j ∧1)+k + L 2l l+2α τ 2α l+2α + τ L,
where L = log(τ -1 ) ∨ log(L 2 ) ∨ 1 and C ′ depends on k, l, α, β and p.

Let us recall that we need not assume that s is exactly of the form g • u but rather, as we did before, that s can be approximated by a function

s = g•u ∈ S k,l (α, β, p, L, R).
In such a case we simply get an additional bias term of the form d 2 (s, s) in our risk bounds.

Proof: Let us fix some value of l ≥ 1 and take s = g • u ∈ S k,l (α, β, p, L, R) and define

r = r(α, β) = 1 + max i=1,...,l α i max j=1,...,l,ℓ=1,...,k β j,ℓ .
The regularity properties of g and the u j together with Propositions 1 and 2 imply that for all D ≥ 1, there exist F ∈ H l,r (D) and sets

T j ∈ B k,r (D) for j = 1, . . . , l such that D(F ) ≤ C ′ 1 (l, α, β) D; d ∞ (g, F ) ≤ C ′ 2 (l, α, β) LD -α/l ; and, for 1 ≤ j ≤ l, D(T j ) ≤ C ′ 3 k, α, β j , p j D; d(u j , T j ) ≤ C ′ 4 k, α, β j , p j R j D -β j /k .
Since the collections H l,r and B k,r satisfy Assumption 2 and w g,j (z) ≤ Lz α j ∧1 for all j and z ∈ [0, 2], we may apply Corollary 1 with S l,r = (l, H l,r , γ r , B k,r , . . . , B k,r , λ r , . . . , λ r ) the subprobabilities γ l,r and λ l,r being given by (4.2) and (4.3) respectively. Besides, it follows from (3.5) that L j,T ≤ C ′ (l, α)L for all j, so that (3.6) implies that the risk of the resulting estimator s l,r is bounded from above by

C ′ R( s l,r , g, u) = l j=1 inf D≥1 L 2 R 2(α j ∧1) j D -2(α j ∧1)β j /k + Dτ L + inf D≥1 L 2 D -2α/l + Dτ ,
for some constant C ′ depending on l, k, α, β 1 , . . . , β l . We obtain the result by optimizing each term of the sum with respect to D by means of Lemma 1, and by using Theorem 3 with ν defined for ℓ = (l, r) l+r+1) for which ∆ ν (l, r)τ ≤ (l + r + 1)R( s l,r , g, u) for all l, r.

∈ N ⋆ × N by ν(l, r) = e -(

Structural assumption versus smoothness assumption

In view of discussing the interest of the risk bounds provided by Theorem 4, let us focus here, for simplicity, on the case where g ∈ H α ([-1, 1]) with α > 0 (hence l = 1) and u is a function from

E = [-1, 1] k to [-1, 1] that belongs to H β ([-1, 1] k ) with β ∈ (R ⋆ + ) k .
The following proposition is to be proved in Section 5.7.

Proposition 3 Let φ be the function defined on

(R ⋆ + ) 2 by φ(x, y) = xy if x ∨ y ≤ 1; x ∧ y otherwise. For all k ≥ 1, α > 0, β ∈ (R ⋆ + ) k , g ∈ H α ([-1, 1]) and u ∈ H β ([-1, 1] k ), g • u ∈ H θ ([-1, 1] k ) with θ i = φ(β i , α) for 1 ≤ i ≤ k. (4.4)
Moreover, θ is the largest possible value for which (4.4) holds for all g ∈ H α ([-1, 1])

and u ∈ H β ([-1, 1] k ) since, whatever θ ′ ∈ (R ⋆ + ) k such that θ ′ i > θ i for some i ∈ {1, . . . , k}, there exists some g ∈ H α ([-1, 1]) and u ∈ H β ([-1, 1] k ) such that g • u ∈ H θ ′ ([-1, 1] k ).
Using the information that s belongs to H θ ([-1, 1] k ) with θ given by (4.4) and that we cannot assume that s belongs to some smoother class (although this may happen in special cases) since θ is minimal, but ignoring the fact that s = g • u, we can estimate s at rate τ 2θ/(2θ+k) (as τ tends to 0) while, on the other hand, by using Theorem 4 and the structural information that s = g • u, we can achieve the rate

τ 2α/(2α+1) + τ log τ -1 2β(α∧1)/(2β(α∧1)+k) .
Let us now compare these two rates. First note that it follows from (4.4) that θ i ≤ α for all i, hence θ ≤ α and, since k > 1, 2α/(2α + 1) > 2θ/ 2θ + k . Therefore the term τ 2α/(2α+1) always improves over τ 2θ/(2θ+k) when τ is small and, to compare the two rates, it is enough to compare θ with β(α ∧ 1). To do so, we use the following lemma (to be proved in Section 5.8).

Lemma 2 For all α > 0 and β ∈ (R ⋆ + ) k , the smoothness index θ = φ(α, β 1 ), . . . , φ(α, β k ) satisfies θ ≤ β(α ∧ 1) and equality holds if and only if sup 1≤i≤k β i ≤ α ∨ 1.

When sup 1≤i≤k β i ≤ α ∨ 1, our special strategy does not bring any improvement as compared to the standard one, it even slightly deteriorates the risk bound because of the extra log τ -1 factor. On the opposite, if sup 1≤i≤k β i > α ∨ 1, our new strategy improves over the classical one and this improvement can be substantial if β is much larger than α ∨ 1. If, for instance, α = 1 and β = k = β j for all j, we get a bound of order τ log τ -1 2/3 which, apart from the extra log τ -1 factor, corresponds to the minimax rate of estimation of a Lipschitz function on [-1, 1], instead of the risk bound τ 2/(2+k) that we would get if we estimated s as a Lipschitz function on [-1, 1] k . When our strategy does not improve over the classical one, i.e. when sup 1≤i≤k β i ≤ α∨1, the additional loss due to the extra logarithmic factor in our risk bound can be avoided by mixing the models used for the classical strategy with the models used for designing our estimator, following the recipe of Section 3.4.

Generalized additive models

In this section, we assume that E = [-1, 1] k , µ is the Lebesgue probability on E and q = 2. A special structure that has often been considered in regression corresponds to functions s = g • u with

u(x 1 , . . . , x k ) = u 1 (x 1 ) + . . . + u k (x k ); s(x) = g u 1 (x 1 ) + . . . + u k (x k ) , (4.5)
where the u j take their values in [-1/k, 1/k] for all j = 1, . . . , k. Such a model has been considered in [START_REF] Horowitz | Rate-optimal estimation for a general class of nonparametric regression models with unknown link functions[END_REF] and while their approach is non-adaptive, ours, based on Theorem 2 and a suitable choice of the collections of models, allows to derive a fully adaptive estimator with respect to the regularities of g and the u j . More precisely, for r ∈ N, let T r be the collection of all models of the form T = T 1 + . . . + T k where for j = 1, . . . , k, T j is the set of functions of the form x → t j (x j ) with x ∈ E and t j in B 1,r . Using λ r = λ as defined by (4.3), we endow T r with the subprobability λ

(k)
r defined for T ∈ T r by the infimum of the quantities k i=1 λ r (T i ) when (T 1 , . . . , T k ) runs among all the k-uplets of B k 1,r satisfying

T = T 1 + . . . + T k . Finally, for α, L > 0, β, R ∈ (R ⋆ + ) k and p = (p 1 , . . . , p k ) ∈ (R ⋆ + ) k , let S Add k (α, β, p, L, R) be the set of functions of the form (4.5) with g ∈ H α ([-1, 1]) satisfying g α,∞ ≤ L and u j ∈ B β j p j ,p j ([-1, 1]) with |u j | β j ,p j ,p j ≤ R j k -1 for all j = 1, . . . , k. Using the sets S r = (1, H 1,r , γ r , T r , λ (k)
r ) with r ∈ N we can build an estimator with the following property.

Theorem 5 Assume that Theorem 1 holds with q = 2. There exists an estimator s which satisfies for all α, L > 0, p, R ∈

(R ⋆ + ) k and β ∈ (R ⋆ + ) k with β j > (1/p j -1/2) + for all j = 1, . . . , k, sup s∈S Add k (α,β,p,L,R) C ′ E s d 2 (s, s) ≤ L 2 2α+1 τ 2α 2α+1 + k j=1 L(R j k -1/2 ) α∧1 2 2(α∧1)β j +1 (τ L) 2(α∧1)β j 2(α∧1)β j +1 + τ L,
where L = log τ -1 ∨ log L 2 ∨ 1 and C ′ is a constant that depends on α, β, p and k only.

If one is mainly interested in the rate of convergence as τ tends to 0, the bound we get is of order max{τ 2α/(2α+1) , [τ log(τ -1 )] 2(α∧1)β/(2(α∧1)β+1) } where β = min{β 1 , . . . , β k }. In particular, if α ≥ 1, this rate is the same (up to a logarithmic factor) as that we would obtain for estimating a function on [-1, 1] with the smallest regularity among α, β 1 , . . . , β k .

Proof: Let us consider some s = g • u ∈ S Add k (α, β, p, L, R) and r = 1 + ⌈α ∨ β 1 ∨ . . . ∨ β k ⌉. For all D, D 1 , . . . , D k ≥ 1, there exist F ∈ H 1,r (D) and T j ∈ B 1,r (D j ) for all j = 1, . . . , k such that D(F ) ≤ C ′ 1 (r)D; d ∞ (g, F ) ≤ C ′ 2 (r)LD -α ;
and, for 1 ≤ j ≤ k,

D(T j ) ≤ C ′ 3 (k, r, p) D j ; d(u j , T j ) ≤ C ′ 4 (k, r, p) R j k -1 D -β j j . If T = T 1 +. . .+T k , then D(T ) ≤ k j=1 D(T j ), ∆ λ (k) r (T ) ≤ k j=1 ∆ λr (T j ) ≤ (c(B 1,r )+ 1) k j=1 (D j + 1). Moreover, d(u, T ) ≤ k j=1 d(u j , T k ) ≤ C ′ 4 k -1 k j=1 R j D -β j j
, hence,

d 2 (u, T ) ≤ (C ′ 4 ) 2 k -1 k j=1 R 2 j D -2β j j
and finally,

d 2(α∧1) (u, T ) ≤ (C ′ 4 ) 2(α∧1) k j=1 (R j k -1/2 ) 2(α∧1) D -2(α∧1)β j j
.

For all T , L 1,T ≤ C ′ (α)L and since w g (z) ≤ Lz α for all z ∈ [0, 2], we may apply Corollary 1 with l = 1 and get that the risk of the resulting estimator s r satisfies

C ′ R( s r , g, u) = k j=1 inf D≥1 L 2 (R j k -1/2 ) 2(α∧1) D -2(α∧1)β j + Dτ L + inf D≥1 L 2 D -2α + Dτ .
We conclude by arguing as in the proof of Theorem 4.

Multiple index models and artificial neural networks

In this section, we assume that E = [-1, 1] k , q = 2 and d is the distance in L 2 (E, µ) where µ is the Lebesgue probability on E. We denote by | • | 1 and | • | ∞ respectively the ℓ 1 -and ℓ ∞ -norms in R k and C k the unit ball for the ℓ 1 -norm. As we noticed earlier, when s is an arbitrary function on E and k is large, there is no hope to get a nice estimator for s without some additional assumptions. A very simple one is that s(x) can be written as g( θ, x ) for some θ ∈ C k , which corresponds to the so-called single index model. More generally, we may pretend that s can be well approximated by some function s of the form s(x) = g θ 1 , x , . . . , θ l , x

where θ 1 , . . . , θ l are l elements of C k and g maps [-1, 1] l to R, l being possibly unknown and larger than k. When s = g • u is of this form, the coordinate functions u j (•) = θ j , • , for 1 ≤ j ≤ l, belong to the set T 0 ⊂ T of functions on E of the form x → θ, x with θ ∈ C k , which is a subset of a k-dimensional linear subspace of L 2 (E, µ), hence D(T 0 ) ≤ k. A slight generalization of this situation leads to the following result.

Theorem 6 Assume that Theorem 1 holds with q = 2. For j ≥ 1, let T j be a subset of T with finite dimension k j and for I ⊂ N * and l ∈ I, let F l be a collection of models satisfying Assumptions 1-(i and iii) for some subprobability γ l . There exists an estimator s which satisfies

CE s d 2 (s, s) ≤ inf l∈I inf g∈F l,c , u∈T l   d 2 (s, g • u) + A(g, F l , γ l ) + τ l j=1 k j i(g, j, T j )   , (4.6)
where T l = T 1 × . . . × T l , i(g, j, T j ) is defined by (3.3) and

A(g, F l , γ l ) = inf F ∈F l d 2 ∞ (g, F ) + τ [D(F ) + ∆ γ l (F )] .
In particular, for all l ∈ I and (α, L)-Hölderian functions g with α ∈ (0, 1] l and L

∈ (R ⋆ + ) l CE s d 2 (s, s)) ≤ inf u∈T l   d 2 (s, g • u) + A(g, F l , γ l ) + τ l j=1 k j 1 α j log lL 2 j (k j τ ) -1 1   . (4.7)
Let us comment on this result, fixing some value l ∈ I. The term d(s, g•u) corresponds to the approximation of s by functions of the form g(u 1 (.), . . . , u l (.)) with g in F l,c and u 1 , . . . , u l in T 1 , . . . , T l respectively. As to the quantity A(g, F l , γ l ), it corresponds to the estimation bound for estimating the function g alone if s were really of the previous form. Finally, the quantity τ l j=1 k j i(g, j, T j ) corresponds to the sum of the statistical errors for estimating the u j . If for all j, the dimensions of the T j remain bounded by some integer k independent of τ , which amounts to making a parametric assumption on the u j , and if g is smooth enough the quantity τ l j=1 k j i(g, j, T j ) is then of order τ log τ -1 for small values of τ as seen in (4.7).

Proof of Theorem 6: For all j, we choose λ j to be the Dirac mass at T j so that ∆ λ j (T j ) = 0 = d(u j , T j ). The result follows by applying Theorem 2 (for a fixed value of l ∈ I) and then Theorem 3 with ν defined by ν(l) = e -l for all l ∈ I.

The multiple index model

As already mentioned, the multiple index model amounts to assuming that s is of the form s(x) = g θ 1 , x , . . . , θ l , x whatever x ∈ E, for some known l ≥ 1 and k j = k for all j. For L > 0 and α ∈ (R ⋆ + ) l , let us denote by S α l (L) the set of functions s of this form with g ∈ H α ([-1, 1] l ) satisfying g α,∞ ≤ L. Applying Theorem 6 to this special case, we obtain the following result.

Corollary 2 Assume that Theorem 1 holds with q = 2 and let I ⊂ N ⋆ . There exists an estimator s such that for all l ∈ I, α ∈ (R ⋆ + ) l and L > 0,

sup s∈S α l (L) C ′ E s d 2 (s, s) ≤ L 2 2α+1 τ 2α 2α+1 + kτ L,
where L = log(τ -1 ) ∨ log(L 2 k -1 ) ∨ 1 and C ′ is a constant depending on l and α only.

The effect of the dimension k only appears in the remaining term. The latter is essentially proportional de kτ (log(τ -1 ) ∨ 1), at least for k ≥ L 2 . It is not difficult to see that there is no hope to get a faster rate than kτ over S α l (L). Indeed, by taking l = L = 1 for simplicity and g the identity function, we see that S α 1 (1) contains the unit ball of a k-dimensional linear space and this is enough to assert that, at least in the regression setting, the minimax rate is of order kτ . As to the extra logarithmic factor log(τ -1 ), we do not know whether it is necessary or not.

Proof: Fix s = g • u ∈ S α
l (L) and apply Theorem 6 with T j = T 0 for all j ≥ 1, I = {l}, F l = H l,r and γ l defined by (4.2) with k = l and r = ⌈α 1 ∨ . . . ∨ α l ⌉. Arguing as in the proof of Theorem 4, we obtain an estimator s (l,r) the risk of which satisfies

R( s (l,r) , g, u) = C ′ inf D≥1 L 2 D -2α/l + Dτ + τ kL ≤ C ′′ L 2 2α+1 τ 2α 2α+1 + kτ L ,
for constants C ′ and C ′′ depending on l and α only. Finally, we conclude as in the proof of Theorem 4.

Case of an additive function g

In the multiple index model, when the value of l is allowed to become large (typically not smaller than k) it is often assumed that g is additive, i.e. of the form g(y 1 , . . . , y l ) = g 1 (y 1 ) + . . . + g l (y l ) for all y ∈ [-1, 1] l , (4.8)

where the g j are smooth functions from [-1, 1] to R. Hereafter, we shall denote by F Add l,c the set of such additive functions g. The functions s = g • u with g ∈ F Add l,c and u ∈ T l 0 hence take the form

s(x) = l j=1
g j ( θ j , x ) for all x ∈ E. (4.9)

For each j = 1, . . . , l, let F j be a countable family of finite dimensional linear subspaces of F 1,∞ designed to approximate g j and γ j some subprobability measure on F j . Given (F 1 , . . . , F l ) ∈ l j=1 F j , we define the subspace F of F l,∞ as

F = f (y 1 , . . . , y l ) = f 1 (y 1 ) + . . . + f l (y l ) f j ∈ F j for 1 ≤ j ≤ l (4.10)
and denote by F the set of all such F when (F 1 , . . . , F l ) varies among l j=1 F j . Then, we define a subprobability measure γ on F by setting

γ(F ) = l j=1 γ j (F j ) or ∆ γ (F ) = l j=1 ∆ γ j (F j ),
when F is given by (4.10). For such an

F , d ∞ (g, F ) ≤ l j=1 d ∞ (g j , F j ), hence d 2 ∞ (g, F ) ≤ l l j=1 d 2 ∞ (g j , F j ) and D(F ) ≤ l j=1 D(F j ).
We deduce from Theorem 6 the following result.

Corollary 3 Assume that Theorem 1 holds with q = 2 and let I ⊂ N ⋆ and for j ≥ 1, let F j be a collection of finite dimensional linear subspaces of F 1,∞ satisfying Assumption 1-i) and-iii) for some subprobability γ j . There exists an estimator s such that

CE d 2 (s, s) ≤ inf l∈I inf g∈F Add l,c ,u∈T l 0   d 2 (s, g • u) + l j=1 R j (g, F j , ∆ γ j ) + τ ki(g, j, T 0 )   , where R j (g, F j , ∆ γ j ) = inf F j ∈F j d 2 ∞ (g j , F j ) + τ D(F j ) + ∆ γ j (F j ) for 1 ≤ j ≤ l.
Moreover, if s of the form (4.9) for some l ∈ I and functions g j ∈ H α j ([-1, 1]) satisfying g j α j ,∞ ≤ L j for α j , L j > 0 and all j = 1, . . . , l, one can choose the F j and γ j in such a way that (4.11) where

E s d 2 (s, s) ≤ C ′   l j=1 L 2 2α j +1 j τ 2α j 2α j +1 + kτ L   ,
L = log τ -1 ∨ 1 ∨ l j=1 log L 2 j k -1
and C ′ is a constant depending on l and α 1 , . . . , α l only.

For j ≥ 1, R j = R j (g, F j , ∆ γ j ) corresponds to the risk bound for the estimation of the function g j alone when we use the family of models F j , i.e. what we would get if we knew θ j and that g i = 0 for all i = j. In short, l j=1 R j corresponds to the estimation rate of the additive function g. If each g j belongs to some smoothness class, this rate is similar to that of a real-valued function defined on the line with smoothness given by the worst component of g, as seen in (4.11).

Proof of Corollary 3:

The first part is a straightforward consequence of Theorem 6. For the second part, fix s = g • u and r = ⌊α 1 ∨ . . . ∨ α l ⌋. Since the g j are (α j ∧ 1, L j )-Hölderian, i(g, j, T 0 ) ≤ C ′ L for some C ′ depending on the α j only. By using Proposition 1, Lemma 1 and the collection F j,r = H 1,r with γ j,r defined by (4.2), for all j = 1, . . . , l, R j ≤ C ′ inf D≥1 {L 2 j D -2α j + Dτ } ≤ C ′′ (L 2/(2α j +1) j τ 2α j /(2α j +1) + τ ) for some constants C ′ , C ′′ depending on the α j only. Putting these bounds together, we end up with an estimator s r the risk of which is bounded from above by the righthand side of (4.11). We get the result for all values of r by using Theorem 3 and arguing as in the proof of Theorem 4.

Artificial neural networks

In this section, we consider approximations of s on E = [-1, 1] k by functions of the form

s(x) = l j=1 R j ψ ( a j , x + b j ) with |b j | + |a j | 1 ≤ 2 r , (4.12)
for given values of (l, r)

∈ I = (N ⋆ ) 2 . Here, R = (R 1 , . . . , R l ) ∈ R l , a j ∈ R k , b j ∈ R for j = 1, .
. . , l and ψ is a given uniformly continuous function on R with modulus of continuity w ψ . We denote by S l,r the set of all functions s of the form (4.12).

Let us now set ψ r (y) = ψ (2 r y) for y ∈ R and, for x ∈ E, u j (x) = 2 -r ( a j , x + b j ), so that u j ∈ T belongs to the (k + 1)-dimensional spaces of functions of the form x → a, x + b. We can then rewrite s in the form g • u with g(y 1 , . . . , y l ) = l j=1 R j ψ r (y j ). Since g belongs to the l-dimensional linear space F spanned by the functions ψ r (y j ), we may set F = {F }, ∆ γ (F ) = 0 and apply Theorem 6. With w g,j (y) = |R j |w ψ (2 r y), (4.6) becomes,

CE s d 2 (s, s l,r ) ≤ d 2 (s, s) + τ (k + 1) l j=1 inf i ∈ N ⋆ lR 2 j w 2 ψ 2 r e -i ≤ (k + 1)τ i .
If w ψ (y) ≤ Ly α for some L > 0, 0 < α ≤ 1 and all y ∈ R + , then, according to (3.4),

CE s d 2 (s, s l,r ) ≤ d 2 (s, s) + kτ   l j=1 α -1 log lR 2 j L 2 2 2rα [kτ ] -1 1   ≤ d 2 (s, s) + lkτ r log 4 + α -1 log + l |R| 2 ∞ L 2 [kτ ] -1 . (4.13)
These bounds being valid for all (l, r) ∈ I and s ∈ S l,r , we may apply Theorem 3 to the family of all estimators s l,r , (l, r) ∈ I, with ν given by ν(l, r) = e -l-r . We then get the following result.

Theorem 7 Assume that Theorem 1 holds with q = 2 and that ψ is a continuous function with modulus of continuity w ψ (y) bounded by Ly α for some L > 0, 0 < α ≤ 1 and all y ∈ R + . Then one can build an estimator s = s(X) such that

CE s d 2 (s, s)) ≤ inf (l,r)∈I inf s∈S l,r d 2 (s, s) + lkτ r 1 + (rα) -1 log + l |R| 2 ∞ L 2 [kτ ] -1 . (4.14)
Approximation by functions of the form (4.12). Various authors have provided conditions on the function s so that it can be approximated within η by functions s of the form (4.12) for a given function ψ. An extensive list of authors and results is provided in Section 4.2.2 of [START_REF] Barron | Risk bounds for model selection via penalization[END_REF] and some proofs are provided in Section 8.2 of that paper. The starting point of such approximations is the assumed existence of a Fourier representation of s of the form

s(x) = K s R k cos a, x + δ(a) dF s (a), K s ∈ R, |δ(a)| ≤ π,
for some probability measure F s on R k . To each given function ψ that can be used for the approximation of s is associated a positive number β = β(ψ) > 0 and one has to assume that (4.15) in order to control the approximation of s by functions of the form (4.12). A careful inspection of the proof of Proposition 6 in [START_REF] Barron | Risk bounds for model selection via penalization[END_REF] shows that, when (4.15) holds, one can derive the following approximation result for s.

c s,β = |a| β 1 dF s (a) < +∞,
There exist constants r ψ ≥ 1, γ ψ > 0 and C ψ > 0 depending on ψ only, a number R s,β ≥ 1 depending on c s,β only and some s ∈ S l,r with |R| 1 ≤ R s,β such that

d (s, s) ≤ K s C ψ 2 -rγ ψ + R s,β l -1/2 for r ≥ r ψ . (4.16)
Putting this bound into (4.14) and omitting the various indices for simplicity, we get a risk bound of the form

R(l, r) = CK 2 2 -2rγ + R 2 l -1 + K -2 lkτ r 1 + (rα) -1 log + lR 2 L 2 [kτ ] -1 ,
to be optimized with respect to l ≥ 1 and r ≥ r ψ . We shall actually perform the optimization with respect to the first three terms, omitting the logarithmic one.

Let us first note that, if RK ≤ r ψ kτ , one should set r = r ψ and l = 1, which leads to

R(1, r ψ ) ≤ Ckτ r ψ 1 + (r ψ α) -1 log + R 2 L 2 [kτ ] -1 .
Otherwise r ψ kτ < RK and we set

r = r * = inf r ≥ r ψ 2 -2rγ ≤ (R/K) √ rkτ and l = l * = RK √ r * kτ . If l * > 1, then RK(r * kτ ) -1/2 ≤ l * < 2RK(r * kτ ) -1/2 hence R(l * , r * ) ≤ CRK √ r * kτ 1 + 1 r * α log + 2R 3 L 2 K (kτ ) 3/2 √ r * . (4.17) If l * = 1, then R 2 ≤ K -2 r * kτ and r ψ kτ < RK ≤ √ r * kτ , hence r * > r ψ and r * -1 ≥ r * /2. Then, from the definition of r * , RK -1 (r * /2)kτ ≤ RK -1 (r * -1)kτ < 2 -2(r * -1)γ ≤ 2 -2γ , hence √ r * kτ < (K/R)2 -2γ+(1/2) < √
2K and (4.17) still holds. To conclude, we observe that either -2γr ψ log 2 ≤ log RK -1 r ψ kτ and r * = r ψ or the solution z 0 of the equation 2zγ log 2 = log K/ R √ kτ -(1/2) log z satisfies r ψ < z 0 ≤ r * . Since log z 0 ≤ z 0 /e, it follows that

r * ≥ log K/ R √ kτ / 2γ log 2 + e -1
and, by monotonicity, that

1 r * log + 2R 3 L 2 K (kτ ) 3/2 √ r * ≤ L = 2γ log 2 + e -1 log + 2R 3 L 2 K (kτ ) 3/2 √ r ψ log K R √ kτ -1
where L is a bounded function of kτ . One can also check that

r * ≤ r = log K/ R r ψ kτ 2γ log 2
and (4.17) finally leads, when r * > r ψ , to

R(l * , r * ) ≤ CRK kτ log K/ R r ψ kτ 2γ log 2 1/2 1 + α -1 L . (4.18)
In the asymptotic situation where τ converges to zero, (4.18) prevails and we get a risk bound of order [-kτ log(kτ )] 1/2 .

Estimation of a regression function and PCA

We consider here the regression framework

Y i = s(X i ) + ε i , i = 1, . . . , n,
where the X i are random variables with values in some known compact subset K of R k (with k > 1 to avoid trivialities) the ε i are i.i.d. centered random variables of common variance 1 for simplicity and s is an unknown function from R k to R. By a proper origin and scale change on the X i , mapping K into the unit ball B k of R k , one may assume that the X i belong to B k , hence that E = B k , which we shall do from now on. We also assume that the X i are either i.i.d. with common distribution µ on E (random design) or deterministic (X i = x i , fixed design), in which case µ = n -1 n i=1 δ x i , where δ x denotes the Dirac measure at x. In both cases, we choose for d the distance in L 2 (E, µ). As already mentioned in Section 2.3, Theorem 1 with τ = n -1 applies to this framework, at least in the two cases when the design is fixed and the errors Gaussian (or subgaussian) or when the design is random and the Y i are bounded, say with values in [-1, 1].

Introducing PCA

Our aim is to estimate s from the observation of the pairs (X i , Y i ) for i = 1, . . . , n, assuming that s belongs to some smoothness class. More precisely, given A ⊂ R k and some concave modulus of continuity w on R + , we define H w (A) to be the class of functions h on A such that |h(x)h(y)| ≤ w (|x -y|) for all x, y ∈ A.

Here we assume that s is defined on B k and belongs to H w (B k ), in which case it can be extended to an element of H w R k , which we shall use when needed. Typically, if w(z) = Lz α with α ∈ (0, 1] and the X i are i.i.d. with uniform distribution µ on E, the minimax risk bound over H w (B k ) with respect to the L 2 (E, µ)-loss is C ′ L 2k/(k+2α) n -2α/(k+2α) (where C ′ depends on k and the distribution of the ε i ). It can be quite slow if k is large (see [START_REF] Stone | Optimal global rates of convergence for nonparametric regression[END_REF]), although no improvement is possible from the minimax point of view if the distribution of the X i is uniform on B k . Nevertheless, if the data X i were known to belong to an affine subspace V of R k the dimension l of which is small as compared to k, so that µ(V ) = 1, estimating the function s with L 2 (E, µ)-loss would amount to estimating s • Π V (where Π V denotes the orthogonal projector onto V ) and one would get the much better rate n -2α/(l+2α) with respect to n for the quadratic risk. Such a situation is seldom encountered in practice but we may assume that it is approximately satisfied for some well-chosen V . It therefore becomes natural to look for an affine space V with dimension l < k such that s and s • Π V are close with respect to the L 2 (E, µ)-distance. For s ∈ H w R k , it follows from Lemma 3 below that,

E |s(x) -s • Π V (x)| 2 dµ(x) ≤ E w 2 (|x -Π V x|) dµ(x) ≤ 2w 2 E |x -Π V x| 2 dµ(x) 1/2
, and minimizing the right-hand side amounts to finding an affine space V with dimension l for which E |x -Π V x| 2 dµ(x) is minimum. This way of reducing the dimension is usually known as PCA (for Principal Components Analysis). When the X i are deterministic and µ = n -1 n i=1 δ X i , the solution to this minimization problem is given by the affine space V l = a + W l where the origin a = X n = n -1 n i=1 X i ∈ B k and W l is the linear space generated by the eigenvectors associated to the l largest eigenvalues (counted with their multiplicity) of XX * (where X is the k × n matrix with columns X i -X n and X * is the transpose of X). In the general case, it suffices to set a = E xdµ (so that a ∈ E) and replace XX * by the matrix

Γ = E (x -a)(x -a) * dµ(x). If λ 1 ≥ λ 2 ≥ . . . ≥ λ k ≥ 0 are the eigenvalues of Γ in nonincreasing order, then inf {V | dim(V )=l} E |x -Π V x| 2 dµ(x) = k j=l+1 λ j (4.19)
(with the convention ∅ = 0) and therefore inf

{V | dim(V )=l} s -s • Π V 2 2 ≤ s -s • Π V l 2 2 ≤ 2w 2   k j=l+1 λ j   .
(4.20)

PCA and composite functions

In order to put the problem at hand into our framework, we have to express s • Π V l in the form g • u. To do so we consider an orthonormal basis u 1 , . . . , u k of eigenvectors of XX * or Γ (according to the situation) corresponding to the ordered eigenvalues λ 1 ≥ λ 2 ≥ . . . ≥ λ k ≥ 0. For a given value of l < k we denote by a ⊥ the component of a which is orthogonal to the linear span W l of u 1 , . . . , u l and for x ∈ B k , we define u j (x) = x, u j for j = 1, . . . , l. This results in an element u = (u 1 , . . . , u l ) of T l and a ⊥ + l j=1 u j (x)u j = Π V l (x) is the projection of x onto the affine space V l = a ⊥ + W l . Setting

g(z) = s   a ⊥ + l j=1 z j u j   for z ∈ [-1, 1] l ,
leads to a function g • u with u ∈ T l and g ∈ F l,c which coincides with s • Π V l on B k as required. Consequently, the right-hand side of (4.20) provides a bound on the distance between s and g

• u. Moreover, since s ∈ H w R k , g(z) -g(z ′ ) ≤ w   l j=1 z j u j - l j=1 z ′ j u j   = w   l j=1 (z j -z ′ j )u j   = w(|z -z ′ |),
(4.21) so that we may set w g,j = w for all j ∈ {1, . . . , l}.

In the following sections we shall use this preliminary result in order to establish risk bounds for estimators s l of s, distinguishing between the two situations where µ is known and µ is unknown.

Case of a known µ

For D ∈ N ⋆ , we consider the partition P l,D of [-1, 1] l into D l cubes with edge length 2/D and denote by F l,D the linear space of functions which are piecewise constant on each element of P l,D so that D(F l,D ) = D l for all D ∈ N ⋆ . This leads to the family F = {F l,D , D ∈ N ⋆ } and we set γ(F l,D ) = e -D for all D ≥ 1. We define u j as in the previous section and take for T j the family reduced to the single model T j = {u j } for j = 1, . . . , l. Then D(T j ) = 0 for all j and we take for λ j the Dirac measure on T j . This leads to a set S which satisfies Assumption 1 and we may therefore apply Theorem 2 which leads to an estimator s l with a risk bounded by

CE s s -s l 2 2 ≤ d 2 (s, g • u) + inf D≥1 d 2 ∞ (g, F l,D ) + D l + D n .
Since s • Π V l and g • u coincide on B k , it follows from (4.20) that

s -g • u 2 2 = s -s • Π V l 2 2 ≤ 2w 2   k j=l+1 λ j   .
Moreover, for all cubes I ∈ P l,D and x ∈ I, the Euclidean distance between x and the center of I is at most √ lD -1 , hence by (4.21), d ∞ (g, F l,D ) ≤ w √ lD -1 for all D ≥ 1. Putting these inequalities together we see that the risk of s l is bounded by

CE s s -s l 2 2 ≤ w 2   k j=l λ j   + inf D≥1 w 2 √ lD -1 + D l n . (4.22)

Case of an unknown µ

When µ corresponds to an unknown distribution of the X i , the matrix Γ is unknown, its eigenvectors u 1 , . . . , u k and the vector a as well and therefore also the elements u 1 , . . . , u l of T . In order to cope with this problem, we have to approximate the unknown u j which requires to modify the definition of T j given in the previous section, keeping all other things unchanged. For each v ∈ R k with |v| ≤ 1, we denote by t v the linear map, element of T , given by t v (x) = x, v . Denoting by B • k the unit sphere in R k we then set, for all j, T j = T = {t v , v ∈ B • k } which is a subset of a k-dimensional linear subspace of L 2 (µ). It follows that Assumption 1 remains satisfied but now with D(T j ) = k. Since u j ∈ T j for all j, an application of Theorem 2 leads to

CE s d 2 (s, s) ≤ k n l j=1 i(g, j, T ) + d 2 (s, g • u) + inf D≥1 d 2 ∞ (g, F l,D ) + D l + D n ,
where i(g, j, T ) is given by (3.3). Since, by (4.21), w g,j = w for all j ∈ {1, . . . , l}, i(g, j, T

) = i = inf i ∈ N ⋆ | lw 2 e -i ≤ ik n .
Arguing as in the case of a known µ, we get

CE s s -s l 2 2 ≤ kli n + w 2   k j=l+1 λ j   + inf D≥1 w 2 √ lD -1 + D l n . Let i D = log D/ √ l . If i ≤ i D , then kli/n ≤ klD/n since i D ≤ D. Otherwise, i ≥ i D + 1 ≥ 2 and l 2 w 2 e -i D ≥ l 2 w 2 e -i+1 > kl(i -1) n ≥ kli 2n ,
which shows that kli/n < 2l 2 w 2 √ lD -1 + klD/n. Finally

CE s s -s l 2 2 ≤ w 2   k j=l+1 λ j   + inf D≥1 l 2 w 2 √ lD -1 + D l + klD n ≤ w 2   k j=l+1 λ j   + lk inf D≥1 w 2 √ lD -1 + 2D l n ,
which is, up to constants, the same as (4.22). We do not know whether the multiplicative factor lk arising here and missing in (4.22) can be improved or not.

Varying l

The previous bounds are valid for all values of l ∈ I = {1, . . . , k} but we do not know which value of l will lead to the best estimator. We may therefore apply Theorem 3 with ν(l) = l -2 /2 for l ∈ I which leads to the following risk bound for the new estimator s in the case of a known µ:

CE s s -s 2 2 ≤ inf l∈{1,...,k} inf D≥1   w 2   k j=l+1 λ j   + w 2 √ lD -1 + D l + log l n   .
Apart from multiplicative constants depending only on k, the same result holds when µ is unknown. If w(z) = Lz α for some L > 0 and α ∈ (0, 1], we get, since k j=l+1 λ j ≤ (kl)λ l+1 (with the convention λ k+1 = 0),

CE s s -s 2 2 ≤ inf l∈{1,...,k} inf D≥1 L 2 [(k -l)λ l+1 ] α + L 2 l α D -2α + D l + log l n .
Assuming that n ≥ L -2 to avoid trivialities and choosing D = nL 2 l α 1/(l+2α) , we finally get l+2α) .

CE s s -s 2 2 ≤ inf l∈{1,...,k} L 2 [(k -l)λ l+1 ] α + log l n + L 2l/(l+2α) n 2α/(
For l = k, we recover (up to constants) the minimax risk bound over H w (B k ), namely C ′ (k)L 2k/(k+2α) n -2α/(k+2α) . Therefore our procedure can only improve the risk as compared to the minimax approach.

Introducing parametric models

In this section, we approximate s by functions of the form s = g •u where g belongs to F l,c and the components u j of u to parametric models T j = {u j (θ, .), θ ∈ Θ j } ⊂ T indexed by subsets Θ j of R k j with k j ≥ 1. Besides, we assume that the following holds.

Assumption 3 For each j = 1, . . . , l, Θ j ⊂ B k j (0, M j ) for some positive number M j and the mapping θ → u j (θ, .) from Θ j to (T , d) is (β j , R j )-Hölderian for β j ∈ (0, 1] and R j > 0 which means that d(u j (θ, .), u j (θ ′ , .)) ≤ R j θθ ′ β j for all θ, θ ′ ∈ Θ j .

(4.23)

Under such an assumption, the following result holds.

Theorem 8 Assume that Theorem 1 holds and let l ≥ 1, T 1 , . . . , T l be parametric sets satisfying Assumption 3, F be a collection of models satisfying Assumption 1-i) and γ be a subprobability on F. There exists an estimator s such that

CE s d 2 (s, s) ≤ d 2 (s, g • u) + inf F ∈F d 2 ∞ (g, F ) + τ (∆ γ (F ) + D(F )) + τ   l j=1 k j log(1 + 2M j R 1/β j j )   + l j=1 inf i≥1 lw 2 g,j e -i + iτ 1 + k j β -1 j ,
for all g ∈ F l,c and u j ∈ T j , j = 1, . . . , l.

In particular, for all (α, L)-Hölderian functions g with α ∈ (0, 1] l and L ∈

(R ⋆ + ) l , CE s d 2 (s, s) ≤ d 2 (s, g • u) + inf F ∈F d 2 ∞ (g, F ) + τ (∆ γ (F ) + D(F )) + τ l j=1 k j log(1 + 2M j R 1/β j j ) + (L j ∨ 1) 1 + k j β -1 j , (4.24)
where

L j = 1 2α j log lL 2 j (1 + k j β -1 j )τ for j = 1, . . . , l. (4.25)
Although this theorem is stated for a given value of l, we may, arguing as before, let l vary and design a new estimator which achieves the same risk bounds (apart for the constant C) whatever the value of l.

As usual, the quantity inf F ∈F d 2 ∞ (g, F ) + τ (∆ γ (F ) + D(F )) corresponds to the estimation rate for the function g alone by using the collection F. In particular, if g ∈ H α ([-1, 1] l ) with α ∈ (R ⋆ + ) l , this bound is of order τ 2α/(2α+l) as τ tends to 0 for a classical choice of F (see Section 4.1). Since for all j, g is also (α j ∧ 1)-Hölderian as a function of x j alone, the last term in the right-hand side of (4.24), which is of order -τ log τ , becomes negligible as compared to τ 2α/(2α+l) and therefore, when s is really of the form g • u with g ∈ H α ([-1, 1] l ) the rate we get for estimating s is the same as that for estimating g.

Proof of Theorem 8: For η > 0 and j = 1, . . . , l, let Θ j [η] be a maximal subset of Θ j satisfying |tt ′ | > η for all t, t ′ in Θ j [η]. Since Θ j is a subset of the Euclidean ball in R k j centered at 0 with radius M j , it follows from classical entropy computations (see Lemma 4 in [START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF]) that log |Θ j [η]| ≤ k j log(1 + 2M j η -1 ). For all i ∈ N ⋆ , let T j,i be the image of Θ j,i = Θ j [(R j e i ) -1/β j ] by the mapping θ → u j (θ, .). Clearly,

log |T j,i | ≤ log |Θ j,i | ≤ k j log 1 + 2M j R 1/β j j e i/β j ≤ k j log(1 + 2M j R 1/β j j ) + iβ -1 j
and because of the maximality of Θ j,i and (4.23), for all θ ∈ Θ j there exists θ ∈ Θ j,i such that d(u j (θ, .), u j (θ, .)) ≤ R j θθ β j ≤ e -i so that T j,i is an e -i -net for T j . For j = 1, . . . , l, we set T j = i≥1 T j,i so that the models in T j are merely the elements of the sets T j,i . For a model T that belongs to T j,i \ 1≤i ′ <i T j [e -i ′ ] (with the convention

∅ = ∅) we set ∆ λ j (T ) = log |T j,i | + i ≤ k j log 1 + 2M j R 1/β j j + i 1 + k j β -1 j which defines a measure λ j on T j satisfying T ∈T j λ j (T ) ≤ i≥1 t∈T j,i λ j ({t}) ≤ i≥1 e -i < 1.
Since for all j and T ∈ T j , D(T ) = 0, we get the first risk bound by applying Theorem 2 to the corresponding set S. To prove (4.24), let us set i(j) = ⌊L j ⌋ ∨ 1 for j = 1, . . . , l with L j given by (4.25), so that 1 ≤ i(j) ≤ L j ∨ 1 and notice that, if

z ≥ L j ∨ 1, then lL 2 j e -2α j z ≤ zτ 1 + k j β -1 j . If L j ≥ 1, then L j ≤ i(j) + 1 ≤ 2L j , hence lL 2 j e -2α j (i(j)+1) ≤ (i(j) + 1)τ 1 + k j β -1 j ≤ 2L j τ 1 + k j β -1 j and lw 2 g,j (e -i(j) ) ≤ lL 2 j e -2α j i(j) ≤ 2e 2α j L j τ 1 + k j β -1 j ≤ 2e 2 L j τ 1 + k j β -1 j . Otherwise, L j < 1, i(j) = 1 ≥ L j ∨ 1 and lw 2 g,j (e -i(j) ) ≤ lL 2 j e -2α j ≤ τ 1 + k j β -1 j , so that in both cases lw 2 g,j (e -i(j) ) ≤ 2e 2 (L j ∨ 1)τ 1 + k j β -1 j
, which leads to the conclusion.

Estimating a density by a mixture of Gaussian densities

In this section, we consider the problem of estimating a bounded density s with respect to some probability µ (to be specified later) on E = R k , d denoting, as before, the L 2 -distance on L 2 (E, µ). We recall from Section 2.3 that Theorem 1 applies to this situation with τ = n -1 s ∞ (1 ∨ log s ∞ ). A common way of modeling a density on E = R k is to assume that it is a mixture of Gaussian densities (or close enough to it). More precisely, we wish to approximate s by functions s of the form s(x) = l j=1 q j p(m j , Σ j , x) for all x ∈ R k , (4.26)

where l ≥ 1, q = (q 1 , . . . , q l ) ∈ [0, 1] l satisfies l j=1 q j = 1 and for j = 1, . . . , l, p(m j , Σ j , .) = dN (m j , Σ 2 j )/dµ denotes the density (with respect to µ) of the Gaussian distribution N (m j , Σ 2 j ) centered at m j ∈ R k with covariance matrix Σ 2 j for some symmetric positive definite matrix Σ j . Throughout this section, we shall restrict to means m j with Euclidean norms not larger than some positive number r and to matrices Σ j with eigenvalues ρ satisfying ρ ≤ ρ ≤ ρ for positive numbers ρ < ρ. In order to parametrize the corresponding densities, we introduce the set Θ gathering the elements θ of the form θ = (m, Σ) where Σ is a positive symmetric matrix with eigenvalues in [ρ, ρ] and m ∈ B k (0, r). We shall consider Θ as a subset of R k(k+1) endowed with the Euclidean distance. In particular, the set M k of square k × k matrices of dimension k is identified to R k 2 and endowed with the Euclidean distance and the corresponding norm N defined by For parameters θ 1 = (m 1 , Σ 1 ), . . . , θ l = (m l , Σ l ) in Θ, the density s can be viewed as a composite function g • u with g(y 1 , . . . , y l ) = e b q 1 y 2 1 + . . . + e b q l y 2 l (4.27) and u = (u 1 , . . . , u l ) with u j (.) = u(θ j , .) for j = 1, . . . , l. With our choices of b and µ, u(θ, .) ∈ T for all θ = (m, Σ) ∈ Θ as required, since for all

N 2 (A) = k i=1 k j=1 A 2 i,j if A = A i,j 1≤i≤k
x ∈ E p(θ, x) = (2ρ 2 ) k/2 det Σ exp |x| 2 4ρ 2 - Σ -1 (x -m) 2 2 ≤ (2ρ 2 ρ -2 ) k/2 exp |x -m| 2 2ρ 2 + |m| 2 2ρ 2 - Σ -1 (x -m) 2 2 ≤ (2ρ 2 ρ -2 ) k/2 e r 2 /(2ρ 2 ) ≤ e b .
An application of Theorem 8 leads to the following result.

Proof: It relies on the following lemma the proof of which is postponed to the end of the section.

Lemma 3 Let (E, E, µ) be some probability space and w some nondecreasing and nonnegative concave function on R + such that w(0) = 0. For all p ∈ [1, +∞] and h ∈ L p (µ), w(|h|) p ≤ 2 1/p w( h p ), with the convention 2 1/∞ = 1.

We argue as follows. For all y, y ′ ∈ [-1, 1] l , |g(y)g(y ′ )| ≤ l j=1 w g,j (|y jy ′ j |) and, since µ is a probability on E,

g • u -f • t p ≤ g • u -g • t p + g • t -f • t p ≤ l j=1 w g,j (|u j -t j |) p + g • t -f • t p ≤ l j=1
w g,j (|u jt j |) p + sup

Basic theorem

We shall first prove a general theorem of independent interest that applies to finite models T for functions in T l and is at the core of all our further developments.

Theorem 9 Let I be a countable set and ν a subprobability on I. Assume that, for each ℓ ∈ I, we are given two countable families T ℓ and F ℓ of subsets of T l and F l,∞ respectively such that each element T of T ℓ is finite and each F ∈ F ℓ is a linear subspace of dimension D(F ) ≥ 1 of F l,∞ . Let λ ℓ and γ ℓ be subprobabilities on T ℓ and F ℓ respectively. One can design an estimator s = s(X) satisfying, for all ℓ ∈ I, all u ∈ T l and g ∈ F l,c with modulus of continuity w g , CE s d 2 (s, s) ≤ inf Proof: For each t ∈ T∈T ℓ T and F ∈ F ℓ we consider the set F t = {f • t, f ∈ F } ⊂ L q (E, µ), which is a D(F )-dimensional linear space. This leads to a new countable family of models S ℓ together with a subprobability π ℓ on S ℓ given by

S ℓ =    F t , t ∈ T∈T ℓ T, F ∈ F ℓ    ; π ℓ (F t ) = γ ℓ (F ) inf T∈T ℓ , T∋t
|T| -1 λ ℓ (T).

(5.1)

We then set S = ℓ∈I S ℓ and π(F t ) = ν(ℓ)π ℓ (F t ) for F t ∈ S ℓ .

It follows that ∆ π (F t ) = ∆ γ ℓ (F ) + inf We now use Proposition 4 which implies that, for each f • t ∈ F t ,

d 2 (s, f • t) ≤ ( s -g • u q + g • u -f • t q ) 2 ≤   s -g • u q + d ∞ (g, f ) + 2 1/q l j=1 w g,j ( u j -t j q )   2 ≤ 3   s -g • u 2 q + d 2 ∞ (g, f ) + 4l l j=1
w 2 g,j ( u jt j q )   , for some universal constant C since 2 1/q ≤ 2. The conclusion follows from a minimization over all possible choices for f and t.

Building new models

In order to use Theorem 9, which applies to finite sets T, starting from the models T which satisfy Assumption 1, we need to derive new models from the original ones.

Let us first observe that, since u j takes its values in [-1, 1] and µ is a probability on E, d(0, u j ) ≤ 1. It is consequently useless to try to approximate u j by elements of L q (E, µ) that do not belong to B(0, 2) since 0 always does better. We may therefore replace T ⊂ L q (E, µ) by T ∩ B(0, 2) ∪ {0}, denoting again the resulting set, which remains a subset of some D(T )-dimensional linear space, by T . Moreover, this modification can only decrease the value of d(T, u j ). Since now T ⊂ B(0, 2), we can use the discretization argument described by the following lemma.

Lemma 4 Let T ⊂ B(0, 2) be either a singleton (in which case D(T ) = 0) or a subset of some D(T )-dimensional linear subspace of L q (E, µ) with D(T ) ≥ 1. For each η ∈ (0, 1], one can find a subset T [η] of T with cardinality bounded by (5/η) D(T ) such that inf We are now in a position to build discrete models for approximating the elements of T l . Given j ∈ {1, . . . , l}, T j in T j and some i ∈ N ⋆ , the previous lemma provides a set T j e -i satisfying T j e -i ≤ exp [D(T j ) (i + log 5)]. Moreover, d u j , T j e -i ≤ d (u j , T j ) + e -i ∧ D(T j ) for all u ∈ T l and i ∈ N ⋆ .

(5.3)

We then define the family T of models by

T =    T = l j=1
T j e -i j with (i j , T j ) ∈ N ⋆ × T j for j = 1, . . . , l    .

(5.4)

Then each T = T 1 e -i 1 × . . . × T l e -i l in T has a finite cardinality bounded by log |T| ≤ l j=1 D(T j ) (i j + log 5) .

(5.5)

Proof of Theorem 2

Starting from the families T j , 1 ≤ j ≤ l, we build the set T given by (5.4) as indicated in the previous section and we apply Theorem 9 to F and T. This requires to define a suitable subprobability λ on T, which can be done by setting, for each T = T 1 e -i 1 × . . . × T l e -i l in T, λ(T) = ∆ λ j (T j ) + i j D(T j ) .

Applying Theorem 9 to F and T with I reduced to a single element and ν the Dirac measure and using (5.5) and (5.3) which implies that inf t j ∈T j [e -i j ] w g,j ( u jt j p ) ≤ w g,j e -i j ∧ D(T j ) + d (u j , T j ) ≤ w g,j e -i j ∧ D(T j ) + w g,j d(u j , T j ) take g(x) = |x| α and u(y) = |y| β for all x, y ∈ [-1, 1], if 1 < β and α ≤ β, take g = h α and u(y) = y for all y ∈ [-1, 1], finally, if α > 1 and α > β, take g(x) = x for all x ∈ [-1, 1] and u = h β .

Proof of Lemma 2

For all α > 0, the map defined for y in (0, +∞) by φ α (y) = 1 φ(α, 1/y) = y(α ∧ 1) -1 if y ≥ (α ∨ 1) -1 ; α -1 otherwise, is positive, piecewise linear and convex. Hence,

1 θ = 1 k k i=1 φ α 1 β i ≥ φ α 1 β = 1 φ(α, β)
and equality holds if and only if β i ≤ (α ∨ 1) for all i or if for all i, β i ≥ (α ∨ 1). We conclude by using the fact that φ(α, z) ≤ z(α ∧ 1) for all positive number z and that equality holds if and only if z ≤ α ∨ 1.

  There exists a collection of models H k,r = D≥1 H k,r (D) satisfying Assumption 2 such that for each positive integer D, the family H k,r (D) consists of linear spaces S with dimensions D(S) ≤ C ′ 1 (k, r)D spanned by piecewise polynomials of degree at most r on k-dimensional hyperrectangles and for which inf S∈H k,r (D)

1≤j≤k .

 1≤j≤k This norm derives from the inner product [A, B] = tr(AB * ) (where B * denotes the transpose of B) on M k and satisfies N (AB) ≤ N (A)N (B) (by Cauchy-Schwarz inequality) and N (A) = N (U AU -1 ) for all orthogonal matrices U . In particular, if A is symmetric and positive with eigenvalues bounded from above by c, N (A) ≤ √ kc. We shall use these properties later on. For b = r 2 /(2ρ 2 ) + k log( √ 2ρ/ρ) and µ the Gaussian distribution N (0, 2ρ 2 I k ) on R k (where I k denotes the identity matrix) we define the parametric set T by T = u(θ, .) = e -b/2 p(θ, .), θ ∈ Θ .

  j ( u jt j p ) + d ∞ (g, f ), which proves the proposition.Proof of Lemma 3: Since there is nothing to prove if h p = 0, we shall assume that h p > 0. The assumptions on w imply that, for all 0 < a < b, b -1 w(b) ≤ a -1 w(a) and w(a) ≤ w(b). Consequently, for p ∈ [1, +∞[, E w p (|h|) dµ = E w p (|h|)1l |h|≤b dµ + E w p (|h|)1l |h|>b dµ ≤ w p (b) + E w p (|h|) |h| p |h| p 1l |h|>b dµ ≤ w p (b) + w p (b) b p E |h| p dµ, and the result follows by choosing b = h p . The case p = ∞ can be deduced by letting p go to +∞.

  ( u jt j p ) + τ [∆ λ ℓ (T) + log |T| + ∆ ν (ℓ)]    + d 2 (s, g • u) + inf F ∈F ℓ d 2 ∞ (g, F ) + τ [D(F ) + ∆ γ ℓ (F )] .

F

  T∈T ℓ , T∋t [∆ λ ℓ (T) + log(|T|)] + ∆ ν (ℓ) for F t ∈ S ℓ .Applying Theorem 1 to S and π leads to an estimator s satisfying, for each ℓ ∈ I, CE s d 2 (s, s)≤ inf ∈F ℓ , T∈T ℓ , t∈T d 2 (s, F t ) + τ [D(F ) + ∆ γ ℓ (F ) + ∆ λ ℓ (T) + log |T| + ∆ ν (ℓ)] .

  v) + [η ∧ D(T )] for all v ∈ T .(5.2)Proof: If D(T ) = 0, then T = {t}, we set T [η] = {(-1 ∨ t) ∧ 1} and the result is immediate since v takes its values in [-1, 1].Otherwise, let T ′ be a maximal subset of T such that d(t, t ′ ) > η for each pair (t, t ′ ) of distinct points in T ′ . Then, for each t ∈ T there exists t ′ ∈ T ′ such that d(t, t ′ ) ≤ η and it follows from Lemma 4 in[START_REF] Birgé | Model selection via testing: an alternative to (penalized) maximum likelihood estimators[END_REF] that |T ′ | ≤ (5/η) D(T ) . Now set T [η] = {(-1 ∨ t) ∧ 1, t ∈ T ′ }.Then (5.2) holds since D(T ) ≥ 1.

  T j ) exp [-i j D(T j )] or ∆ λ (T) = l j=1

Corollary 4 Let s be a bounded density in L 2 (E, µ), d(., .) be the L 2 -distance, τ = n -1 s ∞ (1∨log s ∞ ), M = √ kρ+r, b = r 2 /(2ρ 2 )+k log( √ 2ρ/ρ), R = k/2e -b/2 ρ -1 and

.

There exists an estimator s satisfying for some universal constant C > 0 CE s d 2 (s, s) ≤ inf d 2 (s, g • u) + lk(k + 1)τ [log(1 + 2M R) + (L(τ ) ∨ 1)] , (4.28)

where the infimum runs among all functions u = (u 1 , . . . , u l ) ∈ T l and g of the form (4.27).

The second term in the right-hand side of (4.28) does not depend on g nor u and is of order -τ log τ as τ tends to 0. As already mentioned, one can also consider many values of l simultaneously and find the best one by using Theorem 3. Up to a possibly different constant C, the risk of the resulting estimator then satisfies (4.28) for all l ≥ 1 simultaneously. The problem of estimating the parameters involved in a mixture of Gaussian densities in R k has also been considered by [START_REF] Maugis | A non asymptotic penalized criterion for Gaussian mixture model selection ESAIM Probab[END_REF].

Their approach is based on model selection among a family of parametric models consisting of densities of the form (4.26). Nevertheless, they restrict to Gaussian densities with specific forms of covariance matrices only.

Proof of Corollary 4: First note that for all θ ∈ Θ,

Assumption 3 will be satisfied with

We shall therefore be able to apply Theorem 8 with T j = T for all j, τ = n -1 s ∞ (1∨ log s ∞ ), F = {F } where F is the linear span of dimension D(F ) = l of functions g of the form (4.27) and γ the Dirac mass at F . Since the functions g of the form (4.27) are L-Lipschitz with L j = 2q j e b ≤ 2e b for all j, we shall finally deduce (4.28) from (4.24). We therefore only have to prove (4.29). Let us first note that

where h denotes the Hellinger distance defined by (1.1). Some classical calculations show that

and from the inequalities, 1e -z ≤ z and log(det A) ≤ tr(A -I k ) which hold for all z ∈ R and all matrices A such that det A > 0, by setting

with

It remains to bound U 1 and U 2 from above. For U 1 , taking A = (Σ 0 -Σ 1 )Σ -1 0 and B = Σ -1 1 (Σ 0 -Σ 1 ) and using the fact that the eigenvalues of Σ -1 0 and Σ -1 1 are not larger than ρ -1 , we get

Let us now turn to U 2 . It follows from the same arguments that the symmetric matrix

Putting these bounds together, we obtain that

which, together with (4.30), leads to (4.29).

Proofs of the main results

Let us recall that, in this section, d denotes the distance associated to the q norm of L q (E, µ) and d ∞ the distance associated to the supnorm on F l,∞ .

Preliminary approximation results

The purpose of this section is to see how well f • t approximates g • u when we know how well f approximates g and t = (t 1 , . . . , t l ) approximates u.

with the convention 2 1/∞ = 1. by the subadditivity property of the modulus of continuity w g,j , we get the risk bound

where the first infimum runs among all T j ∈ T j and all i j ∈ N ⋆ for j = 1, . . . , l.

Setting i j = i(g, j, T j ) implies that lw 2 g,j e -i j ∧ D(T j ) ≤ τ i j D(T j ), which proves (3.2). As to (3.6), it simply derives from the fact that, if

Proof of Theorem 3

It follows exactly the line of proof of Theorem 2 via Theorem 9 with an additional step in order to mix the different families of models corresponding to the various sets S ℓ . To each S ℓ corresponds a family of models S ℓ and a subprobability π ℓ on S ℓ given by (5.1). We again apply Theorem 9 with I and ν as given in Theorem 3.

Proof of Lemma 1

If D = 1, we get the bound a + b. When a > b, we can choose D such that (a/b) 1/(θ+1) ≤ D < (a/b) 1/(θ+1) + 1, so that

and the bound b + 2a 1/(θ+1) b θ/(θ+1) ∧ a follows. If b ≥ a, the bound 2b holds, otherwise b < a 1/(θ+1) b θ/(θ+1) and the conclusion follows.

Proof of Proposition 3

It suffices to show that for all i ∈ {1, . . . , k} and x ∈

If at least α or β i are not larger than 1, the result is clear. Otherwise both are larger than 1 and we can write

. Both functions g and u x are b i ∧ a times differentiable and the derivatives g (ℓ) • u x and u

Since the derivative of order b i ∧ a of g • u x is a polynomial with respect to these functions, we derive (4.4) from the fact that the set (H ρ ([-1, 1] k ), +, .) is an algebra on R.

We shall prove the second part of the proposition for the case k = 1 only since the general case can be proved by similar arguments. For ρ > 0, let h ρ ∈ H ρ ([-1, 1]) \ ρ ′ >ρ H ρ ′ ([-1, 1]). Given α, β > 0, we distinguish between the cases below and the reader can check that for each of these g ∈ H α ([-1, 1]), u ∈ H β ([-1, 1]), g • u ∈ H θ ([-1, 1]) with θ = φ(α, β) but g • u ∈ H θ ′ ([-1, 1]) whatever θ ′ > θ. If α, β ≤ 1,