Orves Honoré D'estienne D'

Alan Bâtiment

Turing

Lucie Montuelle

Erwan Le Pennec

Serge X Cohen

Gaussian Mixture Regression model with logistic weights, a penalized maximum likelihood approach

Keywords: Conditional density estimation, Gaussian Mixture Regression, Model selection

We wish to estimate conditional density using Gaussian Mixture Regression model with logistic weights and means depending on the covariate. We aim at selecting the number of components of this model as well as the other parameters by a penalized maximum likelihood approach. We provide a lower bound on penalty, proportional up to a logarithmic term to the dimension of each model, that ensures an oracle inequality for our estimator. Our theoretical analysis is supported by some numerical experiments.

Gaussian Mixture Regression model with logistic weights, a penalized maximum likelihood approach Résumé : Nous souhaitons estimer une densité conditionelle à l'aide d'un modèle de mélange de régression gaussienne à poids logistiques et moyennes dépendant d'une covariable. L'objectif est de sélectionner le nombre de composantes dans le modèle ainsi que d'estimer les autres paramètres par une approche de type maximum de vraisemblance pénalisé. Nous proposons une borne inférieur sur la pénalité, proportionelle à un facteur logarithmique près, à la dimension de chaque modèle, qui assure l'existence d'une inégalité oracle pour notre estimateur. Notre analyse théorique est confirmée par des expériences numériques.

Mots-clés : Estimation de densité conditionnelle, Mélange de régression gaussienne, Sélection de modèles

Gaussian Mixture Regression model with logistic weights, a penalized maximum likelihood approach L. Montuelle, E. Le Pennec and S. X. Cohen April 9, 2013

1 Framework

In classical Gaussian mixture models, density is modeled by

s K,υ,Σ,w (y) = K k=1 π w,k Φ υ k ,Σ k (y),
where K ∈ N * is the number of mixture components, Φ υ,Σ is the density of a Gaussian of mean υ and covariance matrix Σ, Φ υ,Σ (y) = 1

(2π) p |Σ| e - 1
2 (y-υ) ′ Σ -1 (y-υ)

and mixture weights can always be defined from a K-tuple (w 1 , . . . , w K ) with a logistic scheme:

π w,k = e w k K k ′ =1 e w k ′
.

In this article, we consider such a model in which mixture weights as well as means can depend on a covariate. More precisely, we observe n pairs of random variables ((X i , Y i )) 1≤i≤n where covariates X i s are independent and Y i s are independent conditionally to the X i s. We want to estimate the conditional density s 0 (•|x) with respect to the Lebesgue measure of Y given X. We model this conditional density by a mixture of Gaussian regression with varying logistic weights

s K,υ,Σ,w (y|x) = K k=1 π w(x),k Φ υ k (x),Σ k (y),
where (υ 1 , . . . , υ K ) and (w 1 , . . . , w K ) are now K-tuples of functions chosen, respectively, in a set Υ K and W K . Our aim is then to estimate those functions υ k and w k , the covariance matrices Σ k as well as the number of classes K so that the error between the estimated conditional density and the true conditional density is as small as possible.

The classical Gaussian mixture case has been much studied [START_REF] Mclachlan | Finite Mixture Models[END_REF]. Nevertheless, theoretical properties of such model have been less considered. In a Bayesian framework, asymptotic properties of posterior distribution are obtained by Choi [START_REF] Choi | Convergence of posterior distribution in the mixture of regressions[END_REF], Genovese and Wasserman [START_REF] Genovese | Rates of convergence for the gaussian mixture sieve[END_REF], Van der Vaart and Wellner [START_REF] Van Der Vaart | Weak convergence and empirical processes[END_REF] when the true density is assumed to be a Gaussian mixture. AIC/BIC penalization scheme are often used to select a number of cluster (see Burnham and Anderson [4] for instance). Non asymptotic bounds are obtained by Maugis and Michel [START_REF] Maugis | A non asymptotic penalized criterion for gaussian mixture model selection[END_REF] even when the true density is not a Gaussian mixture. All these works rely heavily on a bracketing entropy analysis of the models, that will also be central in our analysis.

When there is a covariate, the most classical extension of this model is the Gaussian mixture regression, in which the means υ k are now functions, is well studied as described inMcLachlan and Peel [START_REF] Mclachlan | Finite Mixture Models[END_REF]. Models in which the proportions vary have been considered by Antoniadis et al. [START_REF] Antoniadis | A multiscale approach for statistical characterization of functional images[END_REF]. Using idea of Kolaczyk et al. [START_REF] Kolaczyk | Multiscale, multigranular statistical image segmentation[END_REF], they have considered a model in which only proportion depend in a piecewise constant manner from the covariate. Their theoretical results are nevertheless obtained under the strong assumption they exactly know the Gaussian components. This assumption can be removed as shown by Cohen and Le Pennec [START_REF] Cohen | Partition-based conditional density estimation[END_REF]. Models in which both mixture weights and means depend on the covariate are considered by Ge and Jiang [START_REF] Ge | On consistency of bayesian inference with mixtures of logistic regression[END_REF], but in a logistic regression mixture framework. They give conditions on the number of experts to obtain consistency of the posterior with logistic weights. Note that similar properties are studied by Lee [START_REF] Lee | Consistency of posterior distributions for neural networks[END_REF] for neural networks.

Although natural, Gaussian mixture regression with varying logistic weights seems to be mentioned first by Jordan and Jacobs [START_REF] Jordan | Hierarchical Mixtures of Experts and the EM Algorithm[END_REF]. They provide an algorithm similar to ours, based on EM and IRLS, for hierarchical mixtures of experts but no theoretical analysis. Chamroukhi et al. [START_REF] Chamroukhi | A hidden process regression model for functional data description. application to curve discrimination[END_REF] consider the case of piecewise polynomial regression model with affine logistic weights. In our setting, this corresponds to a specific choice for Υ K and W K : a collection of piecewise polynomial and a set of affine functions. They use a variation of the EM algorithm and a BIC criterion and provide numerical experiments to support the efficiency of their scheme. In this paper, we propose a slightly different penalty choice and prove non asymptotic bounds for the risk under very mild assumptions on Υ K and W K that hold in their case.

A model selection approach

We will use a model selection approach and define some conditional density models S m by specifying sets of Gaussian regression mixture conditional densities through their number of classes K, a structure on the covariance matrices Σ k and two function sets Υ K and W K to which belong respectively the K-tuple of means (υ 1 , . . . , υ K ) and the K-tuple of logistic weights (w 1 , . . . , w K ). Typically those sets are compact subsets of polynomial of low degree. Within such a conditional density set S m , we estimate s by the maximizer s m of the likelihood

s m = argmax sK,υ,Σ,w ∈Sm n i=1 ln s K,υ,Σ,w (Y i |X i ),
or more precisely, to avoid any existence issue, by any η-minimizer of the -log-likelihood:

n i=1 -ln s m (Y i |X i ) ≤ min sK,υ,Σ,w ∈Sm n i=1 -ln s K,υ,Σ,w (Y i |X i ) + η.
Assume now we have a collection {S m } m∈M of models, for instance with different number of classes K or different maximum degree for the polynomials defining Υ K and W K , we should choose the best model within this collection. Using only the log-likelihood is not sufficient since

RR n°8281

this favors models with large complexity. To balance this issue, we will define a penalty pen(m) and select the model m that minimizes (or rather η ′ -almost minimizes) the sum of the opposite of the log-likelihood and this penalty:

K k=1 -ln s m (Y i |X i ) + pen( m) ≤ min m∈M K k=1 -ln s m (Y i |X i ) + pen(m) + η ′ .
Our goal is now to define a penalty pen(m) which ensures that the maximum likelihood estimate in the selected model performs almost as well as the maximum likelihood estimate in the best model. More precisely, we will prove that

E JKL ⊗n ρ (s 0 , s m ) ≤ C 1 inf m∈M inf sm∈Sm KL ⊗n (s 0 , s m ) + pen(m) n + η + η ′ n + C 2 n
where KL ⊗n is a tensorized Kullback-Leibler divergence, JKL ⊗n ρ a lower bound of this divergence with a pen(m) chosen of the same order as the variance of the corresponding single model maximum likelihood estimate. In the next section, we specify all those divergences and explain the general framework proposed by Cohen and Pennec [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF] for conditional density estimation. We will then explain how to use those results in our specific setting. The last section is dedicated to some numerical experiments conducted for sake of simplicity in the case where X ∈ [0, 1] and Y ∈ R.

A general conditional density model selection theorem

We summarize in this section the main result of Cohen and Pennec [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF] that will be our main tool to obtain the previous oracle inequality. In this work, the estimator loss is measured with a divergence JKL ⊗n defined as a tensorized Kullback-Leibler divergence between the true density and a convex combination of the true density and the estimated one. Contrary to the true Kullback-Leibler divergence, to which it is closely related, it is bounded. This boundedness turns out to be crucial to control the loss of the penalized maximum likelihood estimate under mild assumptions on the complexity of the model and their collection.

Let KL be the classical Kullback-Leibler divergence, which measures a distance between two density functions. Since we work in a conditional density framework, we use a tensorized version of it. We define by KL ⊗n the Kullback-Leibler tensorized divergence,

KL ⊗n (s, t) = E 1 n n i=1 KL(s(.|X i ), t(.|X i ))
which appears naturally in this setting. Replacing t by a convex combination between s and t yields the so-called Jensen-Kullback-Leibler tensorized divergence, denoted JKL ⊗n ρ ,

JKL ⊗n ρ (s, t) = E 1 n n i=1 1 ρ KL(s(.|X i ), (1 -ρ)s(.|X i ) + ρt(.|X i ))
with ρ ∈]0; 1[. This loss is always bounded by 1 ρ ln 1 1-ρ but behaves as KL when t is close to s. Furthermore JKL ⊗n ρ (s, t) ≤ KL ⊗n ρ (s, t). If we let d 2⊗n be the tensorized extension of the squared Hellinger distance d 2 , Cohen and Pennec [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF] prove that there is a constant C ρ such that C ρ d 2⊗n (s, t) ≤ JKL ⊗n ρ (s, t).

To any model S m , a set of conditional densities, we associate a complexity defined in term of a specific entropy, the bracketing entropy with respect to the root of d 2⊗n . Recall that a bracket [t -, t + ] is a pair of real functions such that ∀(x, y) ∈ X × Y, t -(x, y) ≤ t + (x, y) and a function s is said to belong to the bracket

[t -, t + ] if ∀(x, y) ∈ X × Y, t -(x, y) ≤ s(x, y) ≤ t + (x, y).
The bracketing entropy H [],d (δ, S) of a set S is defined as the logarithm of the minimal number N [],d (δ, S) of brackets [t -, t + ] covering S, such that d(t -, t + ) ≤ δ. Our main assumption on models is an upper bound of a Dudley type integral of these bracketing entropies:

Assumption (H) For every model S m in the collection S, there is a non-decreasing function

φ m such that δ → 1 δ φ m (δ) is non-increasing on ]0,+∞[ and for every σ ∈ R + , σ 0 H [.],d ⊗n (δ, S m )dδ ≤ φ m (σ).
One need further to control the complexity of the collection as a whole through a coding type (Kraft) assumption.

Assumption (K)

There is a family (x m ) m∈M of non-negative numbers such that m∈M e -xm ≤ Ξ < +∞.

For technical reason, a separability assumption, always satisfied in the setting of this paper, is also required.

Assumption (Sep)

For every model S m in the collection S, there exists some countable subset S ′ m of S m and a set Y ′ m with λ(Y\Y ′ m ) = 0 such that for every t in S m , it exists some sequence (t k ) k≥1 of elements of S ′ m such that for every x and every y ∈ Y ′ m , ln(t k (y|x)) -----→ k→+∞ ln(t(y|x)).

The main result of Cohen and Pennec [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF] is a condition on the penalty pen(m) which ensures an oracle type inequality:

Theorem 1. Assume we observe (X i , Y i ) with unknown conditional density s 0 . Let S = (S m ) m∈M an at most countable conditional density model collection. Assume assumptions (H), (Sep) and (K) hold. Let s m be a η -log-likelihood minimizer in

S m n i=1 -ln( s m (Y i |X i )) ≤ inf sm∈Sm n i=1 -ln(s m (Y i |X i )) + η
Then for any ρ ∈ (0, 1) and any C 1 > 1, there is a constant κ 0 depending only on ρ and C 1 such that, as soon as for every index m ∈ M,

pen(m) ≥ κ(nσ 2 m + x m )
with κ > κ 0 and σ m the unique root of 1 σ φ m (σ) = √ nσ, the penalized likelihood estimate s m with

m such that n i=1 -ln( s m (Y i |X i )) + pen( m) ≤ inf m∈M n i=1 -ln( s m (Y i |X i )) + pen(m) + η ′ RR n°8281 satisfies E JKL ⊗n ρ (s 0 , s m ) ≤ C 1 inf m∈M inf sm∈Sm KL ⊗n λ (s 0 , s m ) + pen(m) n + C 1 κ 0 Ξ + η + η ′ n .
The name oracle type inequality means that the right-hand side is a proxy for the estimation risk of the best model within the collection. The term inf sm∈Sm KL ⊗n λ (s 0 , s m ) is a typical bias term while pen(m) n plays the role of the variance term. We have three sources of loss here: the constant C 1 can not be taken equal to 1, we use a different divergence on the left and on the right and pen(m) n is not directly related to the variance. The first issue is often considered as minor while the second one turns out to be classical in density estimation results. Whenever pen(m) can be chosen approximately proportional to the dimension D m of the model, which will be the case in our setting, pen(m) n is approximately proportional to D m /n, which is the asymptotic variance in the parametric case. The right-hand side matches nevertheless the best known bound obtained for a single model within such a general framework.

In the next section, we show how to apply this result in our Gaussian mixture setting and prove that the penalty can be chosen roughly proportional to the intrinsic dimension of the model, and thus of the order of the variance.

Spatial Gaussian regression mixture estimation theorem

As explained in introduction, we are looking for conditional densities of type

s K,υ,Σ,w (y|x) = K k=1 π w,k (x)Φ υ k (x),Σ k (y),
where K ∈ N * is the number of mixture components, Φ υ,Σ is the density of a Gaussian of mean υ and covariance matrix Σ, υ k is a function specifying the mean given x of the k-th component while Σ k is its covariance matrix and the mixture weights π w,k are defined from a collection of K functions w 1 , . . . , w K by a logistic scheme:

π w,k (x) = e w k (x) K k ′ =1 e w k ′ (x)
.

For sake of simplicity, we will assume that the covariate X belongs to an hypercube so that X = [0; 1] d . We will estimate those conditional densities by conditional densities belonging to some model S m defined by

S m = (x, y) → K k=1 π w,k (x)Φ υ k (x),Σ k (y) (w 1 , . . . , w K ) ∈ W K , (υ 1 , . . . , υ K ) ∈ Υ K , (Σ 1 , . . . , Σ K ) ∈ V K
where W K is a compact set of K-tuples of functions from X to R, Υ K a compact set of K-tuples of functions from X to R p and V K a compact set of K-tuples of covariance matrix of size p × p. Before describing more precisely those sets, we recall that S m will be taken in a model collection RR n°8281 S = (S m ) m , where m specifies a choice for each of those parameters. The number of components K can be chosen arbitrarily in N * , but will in practice and in our theoretical example be chosen smaller than an arbitrary K max , which may depend on the sample size n. The sets W K and Υ K will be typically chosen as a tensor product of a same compact set of moderate dimension, for instance a set of polynomial of degree smaller than respectively d W and d Υ whose coefficients are smaller in absolute values than respectively T W and T Υ . The structure of the set V K depends on the noise model chosen: we can assume, for instance, it is common to all regressions, that they share a similar volume or diagonalization matrix or they are all different. More precisely, we decompose any covariance matrix Σ into LDAD ′ , where L = |Σ| 1/p is a positive scalar corresponding to the volume, D is the matrix of eigenvectors of Σ and A the diagonal matrix of normalized eigenvalues of Σ. Let L -, L + be positive values and λ -, λ + real values. We define the set A(λ -, λ + ) of diagonal matrices A such that |A| = 1 and ∀i ∈ {1, . . . , p}, λ -≤ A i,i ≤ λ + . A set V K is defined by

V K = {(L 1 D 1 A 1 D ′ 1 , . . . , L K D K A K D ′ K )|∀k, L -≤ L k ≤ L + , D k ∈ SO(p), A k ∈ A(λ -, λ + )}
Those sets V K correspond to the classical covariance matrix sets described by Celeux and Govaert [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF].

We will bound the complexity term nσ 2 m in term of the dimension of S m : we prove that those two terms are roughly proportional. The set V K is a parametric set and thus dim(V K ) is easily defined as the dimension of its parameter set. Defining the dimension of W K and Υ K is more interesting. We rely on an entropy type definition of the dimension. For any K-tuples of functions (s 1 , . . . , s K ) and (t 1 , . . . , t K ), we let

d sup ∞ ((s 1 , . . . , s K ), (t 1 , . . . , t K )) = sup x∈X sup 1≤k≤K |s k (x) -t k (x)|
and define the dimension dim(F K ) of a set F K of such K-tuples as the smallest D such that there is a C satisfying

H d sup ∞ (σ, F K ) ≤ D C + ln 1 σ .
Using the following proposition of Cohen and Pennec [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF], we can easily verify that Assumption (H) is satisfied.

Proposition 1. If for any δ ∈ [0; √ 2], H [.],d ⊗n (δ, S m ) ≤ D m (C m + ln( 1 δ )), then the function φ m (σ) = σ √ D m √ C m + √ π + ln( 1 σ∧1 ) satisfies assumption (H). Furthermore, the unique root σ m of 1 σ φ m (σ) = √ nσ satisfies nσ 2 m ≤ D m 2( C m + √ π) 2 + ln n ( √ C m + √ π) 2 D m + .
We show in Appendix that if

H d sup ∞ (σ, W K ) ≤ dim(W K ) C WK + ln 1 σ
and

H max k sup x 2 (σ, Υ K ) ≤ dim(Υ K ) C ΥK + ln 1 σ RR n°8281 then, if n ≥ 1, the complexity of the corresponding model S m satisfies nσ 2 m ≤ D m 2( C m + √ π) 2 + ln n ( √ C m + √ π) 2 D m + ≤ D m 2( C m + √ π) 2 + ln(n) ≤ D m (C ′ m + ln(n))
with C ′ m that depends only on the constants defining V K and the constants C WK and C ΥK . In order to obtain the same constant C ′ m for all models, we impose that the dimension bound holds with the same constants for all models: Assumption (DIM) There exist two constants C W and C Υ such that, for every model S m in the collection S,

H max k ∞ (σ, W K ) ≤ dim(W K ) C W + ln 1 σ .
and

H max k sup x 2 (σ, Υ K ) ≤ dim(Υ K ) C Υ + ln 1 σ
We can now state our main result:

Theorem 2. For any collection of Gaussian regression mixtures satisfying (K) and (DIM), there is a constant C such that for any ρ ∈ (0, 1) and any C 1 > 1, there is a constant κ 0 depending only on ρ and C 1 such that, as soon as for every index m ∈ M, pen(m) = κ((C + ln n) dim(S m ) + x m ) with κ > κ 0 , the penalized likelihood estimate s m with m such that

n i=1 -ln( s m (Y i |X i )) + pen( m) ≤ inf m∈M n i=1 -ln( s m (Y i |X i )) + pen(m) + η ′ satisfies E JKL ⊗n ρ (s 0 , s m ) ≤ C 1 inf m∈M inf sm∈Sm KL ⊗n λ (s 0 , s m ) + pen(m) n + κ 0 Ξ + η + η ′ n .
In the previous theorem, the assumption on pen(m) could be replaced by the milder one

pen(m) ≥ κ 2D m C 2 + D m ln n C 2 D m + + x m .
To minimize arbitrariness, x m should be chosen such that 2κxm pen(m) is as small as possible. Notice that the constant C only depends on the model collection parameters, for instance on the maximal number of components K max . As often in model selection, the collection may be chosen according to to the sample size n. If the constant C ′ grows no faster than ln(n), the penalty shape can be kept intact and a similar result holds uniformly in n up to a slightly larger κ 0 . For instance, as K max only appears in C through a logarithmic term, K max may grow as a power of the sample size.

We postpone the proof of this theorem to the Appendix and focus on Assumption (DIM). This assumption can often be verified when the functions sets W K and Υ K are defined as images of a finite dimensional compact subset of parameters when X ∈ [0, 1] d . For example, those sets can be defined as linear combination of a finite set of bounded functions whose coefficients belong to a compact set. We study here the case of linear combination of the first elements of a polynomial basis but similar results hold, up to some modification on the coefficient sets, for many other choices (first elements of a Fourier, spline or wavelet basis, elements of an arbitrary bounded dictionary...)

Let d W and d Υ be two integers and T W and T Υ some positive numbers. We define

W =    w : [0; 1] d → R|w(x) = dW |r|=0 α r x r and α ∞ ≤ T W    Υ =    υ : [0; 1] d → R p ∀j ∈ {1, . . . , p}, ∀x, υ j (x) = dΥ |r|=0 α (j) r x r and α ∞ ≤ T Υ    Let W K = {0} × W K-1 and Υ K = Υ K . We prove in Appendix that Lemma 1. W K and Υ K satisfy assumption (DIM), with C W = ln √ 2 + T W dW +d d and C Υ = ln √ 2 + √ p dΥ+d d T Υ , not depending on K.
To apply Theorem 2, it remains to describe a collection (S m ) and a suitable choice for (x m ). Assume, for instance, that the models in our collection are defined by an arbitrary maximal number of components K max , a common free structure for the covariance matrix K-tuple and a common maximal degree for the sets W K and Υ K , then one can verify that dim(S m ) = (K -1 + Kp) dW +d d + Kp p+1 2 and that the weight family (x m = K) satisfy Assumption (K) with Ξ ≤ 1/(e -1). Theorem 2 yields then an oracle inequality with pen(m) = κ ((C + ln(n)) dim(S m ) + x m ). Note that as x m ≪ (C + ln(n)) dim(S m ), one can obtain a similar oracle inequality with pen(m) = κ(C + ln(n)) dim(S m ) for a slightly larger κ. Finally, as explained in the proof, choosing a covariance structure from the finite collection of Celeux and Govaert [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF] or choosing the maximal degree for the sets W K and Υ K among a finite family can be obtained with the same penalty but with a larger constant Ξ in Assumption (K).

Numerical scheme and numerical experiment

We illustrate our theoretical result in a setting similar to the one considered by Chamroukhi et al. [START_REF] Chamroukhi | A hidden process regression model for functional data description. application to curve discrimination[END_REF]. We observe n pairs (X i , Y i ) with X i ∈ [0, 1] and Y i ∈ R and look for the best estimate of the conditional density s 0 (y|x) that can be written

s K,υ,Σ,w (y|x) = K k=1 π w,k (x)Φ υ k (x),Σ k (y),
with w ∈ W K and υ ∈ Υ K . We consider the simple case where W K and Υ K comprise linear functions. We do not impose any structure on the covariance matrices. Our aim is to estimate the best number of components K, as well as the model parameters. As described with more details later, we use an EM type algorithm to estimate the model parameters for each K and select one using the penalized approach described previously. In our numerical experiment, we consider two different examples: one in which true conditional density belongs to one of our models, a parametric case, and one in which this is not true, a non parametric case. In the first situation, we expect to perform almost as well as the maximum likelihood estimation in the true model. In the second situation, we expect our algorithm to automatically balance the model bias and its variance. More precisely, we let

s 0 (y|x) = 1 1 + exp(15x -7) Φ -15x+8,0.3 (y) + exp(15x -7) 1 + exp(15x -7) Φ 0.4x+0.6,0.4 (y)
in the first example, denoted example P, and

s 0 (y|x) = 1 1 + exp(15x -7) Φ 15x 2 -22x+7.4,0.3 (y) + exp(15x -7) 1 + exp(15x -7) Φ -0.4x 2 ,0.4 (y)
in the second example, denoted example NP. For both experiments, we let X be uniformly distributed over [0, 1]. Figure 1 shows a typical realization for both examples.

As often in model selection approach, the first step is to compute the maximum likelihood estimate for each number of components K. To this purpose, we use a numerical scheme based on the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] similar to the one used by Chamroukhi et al. [START_REF] Chamroukhi | A hidden process regression model for functional data description. application to curve discrimination[END_REF]. The only difference with a classical EM is in the Maximization step since there is no closed formula for the weights optimization. We use instead a Newton type algorithm. Note that we only perform a few Newton steps (5 at most) and ensures that the likelihood does not decrease. We have noticed that there is no need to fully optimize at each step: we did not observe a better convergence and the algorithmic cost is high. We denote from now on this algorithm Newton-EM. Figure 2 illustrates the fast convergence of this algorithm towards a local maximum of the likelihood. Notice that the lower bound on the variance required in our theorem appears to be necessary in practice. It avoids the spurious local maximizer issue of EM algorithm, in which a class degenerates to a minimal number of points allowing a perfect Gaussian regression fit. We use a lower bound of 10 n . Biernacki and Castellan [START_REF] Biernacki | A data-driven bound on variances for avoiding degeneracy in univariate gaussian mixtures[END_REF] provide a more precise data-driven bound:

min 1≤i<j≤n (Yi-Yj ) 2 2χ 2 n-2K+1 ((1-α) 1/K ) , with χ 2
n-2K+1 the chi-squared quantile function, which is of the same order as 1 n in our case. In practice, the constant 10 gave good results. An even more important issue with EM algorithms is initialization, since the local minimizer obtained depends heavily on it. We observe that, while the weights w do not require a special care and can be simply initialized uniformly equal to 0, the means require much more attention in order to obtain a good minimizer. We propose an initialization strategy which can be seen as an extension of a Quick-EM scheme with random initialization.

RR n°8281

We draw randomly K lines, each defined as the line going through two points (X i , Y i ) drawn at random among the observations. We perform then a K-means clustering using the distance along the Y axis. Our Newton-EM algorithm is initialized by the regression parameters as well as the empirical variance on each of the K clusters. We perform then 3 steps of our minimization algorithm and keep among 50 trials the one with the largest likelihood. This winner is used as the initialization of a final Newton-EM algorithm using 10 steps.

We consider two other strategies: a naive one in which the initial lines chosen at random and a common variance are used directly to initialize the Newton-EM algorithm and a clever one in which observations are first normalized in order to have a similar variance along both the X and the Y axis, a K-means on both X and Y with 5 times the number of components is then performed and the initial lines are drawn among the regression lines of the resulting cluster comprising more than 2 points.

The complexity of those procedures differs and as stressed by Celeux and Govaert [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF] the fairest comparison is to perform them for the same amount of time (5 seconds, 30 seconds, 1 minute...) and compare the obtained likelihoods. The difference between the 3 strategies is not dramatic: they yield very similar likelihoods. We nevertheless observe that the naive strategy has an important dispersion and fails sometime to give a satisfactory answer. Comparison between the clever strategy and the regular one is more complex since the difference is much smaller. Following Celeux and Govaert [START_REF] Celeux | Gaussian parsimonious clustering models[END_REF], we have chosen the regular one which corresponds to more random initializations and thus may explores more local maxima.

Once the parameters' estimates have been computed for each K, we select the model that minimizes which the estimate has good properties, but does not give an explicit value for κ. In practice, κ has to be chosen. The two most classical choices are κ = 1 and κ = ln n 2 which correspond to the AIC and BIC approach, motivated by asymptotic arguments. We have used here the slope heuristic proposed by Birgé and Massart and described for instance in Baudry et al. [START_REF] Baudry | Slope heuristics: Overview and implementation[END_REF]. It consists in representing the dimension of the selected model according to κ (fig 3), and finding κ such that if κ < κ, the dimension of the selected model is large, and reasonable otherwise. The slope heuristic prescribes then the use of κ = 2κ. In both examples, we have noticed that the sample's size had no significant influence on the choice of κ, and that very often 1 was in the range of possible values indicated by the slope heuristic. According to this observation, we have chosen in both examples κ = 1.

We measure performances in term of tensorized Kullback-Leibler distance. Since there is no known formula for tensorized Kullback-Leibler distance in the case of Gaussian mixtures, and since we know the true density, we evaluate the distance using Monte Carlo method. The variability of this randomized evaluation has been verified to be negligible in practice.

For several numbers of mixture components and for the selected K, we draw in figure 4 the box plots and the mean of tensorized Kullback-Leibler distance over 55 trials. The first observation is that the mean of tensorized Kullback-Leibler distance between the penalized estimator ŝ K and s 0 is smaller than the mean of tensorized Kullback-Leibler distance between ŝK ans s 0 over K ∈ {1, . . . , 20}. This is in line with the oracle type inequality of Theorem 2. Our numerical results hint that our theoretical analysis may be pessimistic. A close inspection show that the bias-variance trade-off differs between the two examples. Indeed, since in the first one the true density belongs to the model, the best choice is K = 2 even for small n. As shown on the histogram of Figure 5, this is almost always the model chosen by our algorithm. Observe also that the mean of Kullback-Leibler distance seems to behave like dim(Sm) 2n (shown by a dotted line). This is indeed the expected behavior when the true model belongs to a nested collection and corresponds to the classical AIC heuristic. In the second example, the true model does not belong to the collection. The best choice for K should thus balance a model approximation error and a variance one. We observe in Figure 5 such a behavior: the larger n the more complex the model and thus K. Note that the slope of the mean error seems also to grow like dim(Sm) 2n even though there is no theoretical guarantee of such a behavior.

Figure 6 shows the error decay when the sample size n grows. As expected in the parametric

RR n°8281

Gaussian Mixture Regression model with logistic weights, a penalized maximum likelihood approach14 Figure 6: Kullback-Leibler distance between the true density and the computed density using (X i , Y i ) i≤N with respect to the sample size, represented in a log-log scale. For each graph, we added a free linear least-square regression and one with slope -1 to stress the two different behavior.

case, example P, we observe the decay in t/n predicted in the theory, with t some constant. The rate in the second case appears to be slower. Indeed, as the true conditional density does not belong to any model, the selected models are more and more complex when n grows which slows the error decay. In our theoretical analysis, this can already be seen in the decay of the variance term of the oracle inequality. Indeed, if we let m 0 (n) be the optimal oracle model, the one minimizing the right-hand side of the oracle inequality, the variance term is of order

D m 0 (n) n
which is larger than 1 n as soon as D m0(n) → +∞. It is well known that the decay depends on the regularity of the true conditional density. Providing a minimax analysis of the proposed estimator, as have done Maugis and Michel [START_REF] Maugis | Adaptive density estimation using finite gaussian mixtures[END_REF], would be interesting but is beyond the scope of this paper.

A Proof of Theorem 2

In this section, an overview of the proof of the model selection theorem, applied to our Gaussian regression mixture, is given. B is dedicated to the example with polynomial means and weights. The constants in the Assumption (DIM) and the theorem are specified. Then, in C, we provide more details on the proofs and lemmas used in the first section.

We will show that Assumption (DIM) ensures that for all δ ∈ [0;

√ 2], H [.],d ⊗n (δ, S m ) ≤ D m (C m + ln( 1 δ )
) with a common C m . If this happens, Proposition 1 yields the results. In other words, if we can control models' bracketing entropy with a uniform constant C, we get a suitable bound on the complexity. This result will be obtain by first decomposing the entropy term between the weights and the Gaussian mixtures. Therefore we use the following distance over conditional densities:

sup x d y (s, t) = sup x∈X y s(y|x) -t(y|x) 2 dy 1 2
.

RR n°8281

Notice that d 2⊗n (s, t) ≤ sup x d 2 y (s, t). For all weights π and π ′ , we define

sup x d k (π, π ′ ) = sup x∈X K k=1 π k (x) -π ′ k (x) 2 1 2
.

Finally, for all densities s and t over Y, depending on x, we set

sup x max k d y (s, t) = sup x∈X max 1≤k≤K d y (s k (x, .), t k (x, .)) = sup x∈X max 1≤k≤K y s k (x, y) -t k (x, y) 2 dy 1 2 . Lemma 2. Let P = (π w,k ) 1≤k≤K /w ∈ W K , and ∀(k, x), π w,k (x) = e w k (x) K l=1 e w l (x)
and

G = (Φ υ k ,Σ k ) 1≤k≤K /υ ∈ Υ K , Σ ∈ V K . Then for all δ in [0; √ 2]
, for all m in M,

H [.],sup x dy (δ, S m ) ≤ H [.],sup x d k δ 5 , P + H [.],sup x max k dy δ 5 , G .
One can then relate the bracketing entropy of P to the entropy of

W K Lemma 3. For all δ ∈ [0; √ 2], H [.],sup x d k δ 5 , P ≤ H max k ∞ 3 √ 3δ 20 √ K , W K Since P is a set of weights, 3 √ 3δ 20 √
K could be replaced by 3 √ 3δ 20 √ K-1 with an identifiability condition. For example, W ′ K = {(0, w 2w 1 , . . . , w Kw 1 )|w ∈ W K } can be covered using brackets of null size on the first coordinate, lowering squared Hellinger distance between the brackets' bounds to a sum of K -1 terms. Therefore,

H [.],sup x d k δ 5 , P ≤ H max k ∞ 3 √ 3δ 20 √ K-1 , W ′ K . Since we have assumed that ∃D WK , C W s.t ∀δ ∈ [0; √ 2], H max k ∞ (δ, W K ) ≤ D WK C W + ln 1 δ Then H [.],sup x d k δ 5 , P ≤ D WK C W + ln 20 √ K 3 √ 3δ
To tackle the Gaussian regression part, we rely heavily on the following proposition,

Proposition 2. Let κ ≥ 17 29 , γ κ = 25(κ -1 2 ) 49(1 + 2κ 5 )
. For any 0 < δ ≤ √ 2 and any δ Σ ≤

1 5 √ κ 2 cosh( 2κ 5 )+ 1 2 δ p , (υ, L, A, D) ∈ Υ × [L -, L + ] × A(λ -, λ + ) × SO(p) and (υ, L, Ã, D) ∈ Υ × [L -, L + ] × A(λ -, +∞) × SO(p), Σ = LDAD ′ and Σ = L D Ã D′ , assume that t -(x, y) = (1 + κδ Σ ) -p Φ υ(x),(1+δΣ) -1 Σ(y) and t + (x, y) = (1 + κδ Σ ) p Φ υ(x),(1+δΣ) Σ(y). If            ∀x ∈ R d , υ(x) -υ(x) 2 ≤ pγ κ L -λ - λ- λ+ δ Σ 2 (1 + 2 25 δ Σ ) -1 L ≤ L ≤ L ∀1 ≤ i ≤ p, |A -1 i,i -Ã-1 i,i | ≤ 1 10 δΣ λ+ ∀y ∈ R p , Dy -Dy ≤ 1 10 λ- λ+ δ Σ y then [t -, t + ] is a δ 5 Hellinger bracket such that t -(x, y) ≤ Φ υ(x),Σ (
y) ≤ t + (x, y). We consider three cases: the parameter (mean, volume, matrix) is known (⋆ = 0), unknown but common to all classes (⋆ = c), unknown and possibly different for every class (⋆ = K). For example, [ν K , L 0 , D c , A 0 ] denotes a model in which only means are free and eigenvector matrices are assumed to be equal and unknown. Under our assumption that D ΥK , C Υ s.t ∀δ ∈ [0;

√ 2],

H max k sup x . 2 (δ, Υ K ) ≤ D ΥK C Υ + ln 1 δ
we deduce:

H [.],max k sup x dy δ 5 , G ≤ D C + ln 1 δ (1)
where

D = Z υ,⋆ + Z L,⋆ + p(p -1) 2 Z D,⋆ + (p -1)Z A,⋆ and C = ln 5p κ 2 cosh 2κ 5 + 1 2 + Z υ,⋆ C Υ D + Z υ,⋆ 2D ln λ + pγ κ L -λ 2 - + Z L,⋆ D ln   4 + 129 ln L+ L- 10   + Z D,⋆ D ln(c U ) + p(p -1) 2 ln 10λ + λ - + Z A,⋆ (p -1) D ln 4 5 + 52λ + 5λ - ln λ + λ - . Z υ,K = D ΥK , Z υ,c = D Υ1 , Z υ,0 = 0 Z L,0 = Z D,0 = Z A,0 = 0, Z L,c = Z D,c = Z A,c = 1, Z L,K = Z D,K = Z A,K = K
We notice that the following upper-bound of C is independent from the model of the collection, because we have made this hypothesis on C Υ .

C ≤ ln 5p κ 2 cosh 2κ 5 + 1 2 + C Υ + 1 2 ln λ + pγ κ L -λ 2 - + ln   4 + 129 ln L+ L- 10   + 2 p(p -1) ln(c U ) + ln 10λ + λ - + ln 4 5 + 52λ + 5λ - ln λ + λ - := C 1 .
We conclude that H

[.],sup x dy (δ, S m ) ≤ D m C m + ln 1 δ
, with

D m = D WK + D C m = D WK D m C W + ln 20 √ K 3 √ 3 + DC 1 D m ≤ C W + ln 20 √ K max 3 √ 3 + C 1 := C
Note that the constant C does not depend on the dimension D m of the model, thanks to the hypothesis that C W is common for every model S m in the collection. Using Proposition 1, we deduce thus that

nσ 2 m ≤ D m   2 √ C + √ π 2 +   ln n √ C + √ π 2 D m    +    .
Theorem 1 yields then, for a collection S = (S m ) m∈M , with

M = {(K, W K , Υ K , V K )|K ∈ N * , W K , Υ K , V K
as previously defined } for which Assumption (K) holds, the oracle inequality of Theorem 2 as soon as

pen(m) ≥ κ   Dm   2 √ C + √ π 2 +   ln n √ C + √ π 2 D m    +    + x m    .

B Proof of Theorem for polynomial

We focus here on the example in which W K and Υ K are polynomials of degree respectively at most d W and d Υ .

By applying lemmas 1, 3 and 1, we get:

Corollary 1. H [.],sup x d k δ 5 , P ≤ (K -1) d W + d d × ln √ 2 + 20 3 √ 3 T W √ K -1 d W + d d + ln 1 δ . ≤ (K -1) d W + d d × C W + ln 20 3 √ 3 √ K -1 + ln 1 δ . H [.],sup x max k dy δ 5 , G ≤ D C + ln 1 δ RR n°8281
with

D = D Υ K + K p(p + 1) 2 , D Υ K = pK d Υ + d d C = 2 2D Υ K + Kp(p + 1) D Υ K C Υ + D Υ K 2 ln 25pλ + κ 2 cosh 2κ 5 + 1 2 γ κ L -λ 2 - +K   ln(c U ) + ln   4 + 129 ln L+ L- 10   + p(p + 1) 2 ln 5p κ 2 cosh 2κ 5 + 1 2 + p(p -1) 2 ln 10λ + λ - + (p -1) ln 4 5 + 52λ + 5λ - ln λ + λ - .
Just like in the general case, we define C 1 by:

C 1 = C Υ + 1 2 ln 25pλ + κ 2 cosh 2κ 5 + 1 2 γ κ L -λ 2 - + ln 5p κ 2 cosh 2κ 5 + 1 2 + 2 p(p + 1)   ln(c U ) + ln   4 + 129 ln L+ L- 10   + (p -1) ln 4 5 + 52λ + 5λ - ln λ + λ -   + p -1 p + 1 ln 10λ + λ - and remind that C = C W + ln 20 √ Kmax-1 3 √ 3
+ C 1 is an upper-bound for C m . We recall that

C W = ln √ 2 + T W dW +d d and C Υ = ln √ 2 + √ pT Υ dΥ+d d
, and observe that C does not depend on the model S m in the collection since C only depends on K max , T W , d W , T Υ , d Υ , p, d, κ and the parameters defining V K . Then we can apply the result in the general case to the collection (S m ) in which each model is defined by a number of components K, a common free structure on the covariance matrix K-tuple and a common maximal degree for the sets W K and Υ K . (x m = K) m∈M satisfies Kraft inequality, since m∈M e -xm ≤ 1 e-1 . We obtain an oracle inequality with pen(m

) = κ ((C + ln(n)) dim(S m ) + x m ), where C = 2( √ C + √ π) 2 , dim(S m ) = (K -1 + Kp) dW +d d + Kp p+1 2
and x m = K for the selection of the number of components in the mixture. If we change the structure V K over the covariance matrices, it only changes the constant Ξ in Kraft inequality, since there a finite number of possible structures for a fixed K and the sum m∈M e -xm can be rewritten K∈N * m∈M|m(1)=K e -xm .

C Lemma Proofs

In this section, we provide the proofs of the main lemmas used in the first appendix, to prove Theorem 2. It begins with bracketing entropy's decomposition, then we focus on the bracketing entropy of the weight's families in the general case and in our example, followed by the analysis of the bracketing entropy of Gaussian families.

C.1 Bracketing entropy's decomposition

Lemma 4. Let

P = π = (π k ) 1≤k≤K /∀k, π k : X → R + and ∀x ∈ X , K k=1 π k (x) = 1 , Ψ = (ψ 1 , . . . , ψ K )/∀k, ψ k : X × Y → R + , and ∀x, ∀k, ψ k (x, y)dy = 1 , C = (x, y) → K k=1 π k (x)ψ k (x, y)/π ∈ P, ψ ∈ Ψ .
Then for all δ in [0;

√ 2],

H [.],sup x dy (δ, C) ≤ H [.],sup x d k δ 5 , P + H [.],sup x max k dy δ 5 , Ψ .
The proof mimics the one of Lemma 7 from [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF].

Proof. First we will exhibit a covering of bracket of C.

Let ([π i,-, π i,+ ]) 1≤i≤NP be a minimal covering of δ bracket for sup

x d k of P: ∀i ∈ {1, . . . , N P }, ∀x ∈ X , d k (π i,-(x), π i,+ (x)) ≤ δ.
Let ([ψ i,-, ψ i,+ ]) 1≤i≤NΨ be a minimal covering of δ bracket for sup

x max k d y of Ψ: ∀i ∈ {1, . . . , N Ψ }, ∀x ∈ X , ∀k ∈ {1, . . . , K}, d y (ψ i,- k (x, .), ψ i,+ k (x, .)) ≤ δ.
Let s be a density in C. By definition, there is π in P and ψ in Ψ such that for all

(x, y) in X × Y, s(y|x) = K k=1 π k (x)ψ k (x, y).
Due to the covering, there is i in {1, . . . , N P } such that ∀x ∈ X , ∀k ∈ {1, . . . , K}, π i,- k (x) ≤ π k (x) ≤ π i,+ k (x). There is also j in {1, . . . , N Ψ } such that ∀x ∈ X , ∀k ∈ {1, . . . , K}, ∀y ∈ Y, ψ j,- k (x, y) ≤ ψ k (x, y) ≤ ψ j,+ k (x, y). Since for all x, for all k and for all y, π k (x) and ψ k (x, y) are non-negatives, we may multiply term-by-term and sum these inequalities over k to obtain:

∀x ∈ X , ∀y ∈ Y, K k=1 π i,- k (x) + ψ j,- k (x, y) + ≤ s(y|x) ≤ K k=1 π i,+ k (x)ψ j,+ k (x, y). K k=1 π i,- k + ψ j,- k + , K k=1 π i,+ k ψ j,+ k 1≤i≤NP 1≤j≤NΨ
is thus a bracket covering of C. Now, we focus on brackets' size using lemmas from [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF] (namely Lemma 11,[START_REF] Genovese | Rates of convergence for the gaussian mixture sieve[END_REF][START_REF] Jordan | Hierarchical Mixtures of Experts and the EM Algorithm[END_REF], To lighten the notations, π - k and ψ - k are supposed non-negatives for all k. Following their Lemma 12, only using Cauchy-Schwarz inequality, we prove that

sup x d 2 y K k=1 π - k (x)ψ - k (x, .), K k=1 π + k (x)ψ + k (x, .) ≤ sup x d 2 y,k (π -(x)ψ -(x, .), π + (x)ψ + (x, .)) RR n°8281
Then, using Cauchy-Schwarz inequality again, we get by their Lemma 11:

sup x d 2 y,k (π -(x)ψ -(x, .), π + (x)ψ + (x, .)) ≤ sup x   max k d y (ψ + k (x, .), ψ - k (x, .)) K k=1 π + k (x) +d k (π + (x), π -(x)) max k ψ - k (x, y)dy 2
According to their Lemma 13, ∀x,

K k=1 π + k (x) ≤ 1 + 2( √ 2 + √ 3)δ. sup x   max k d y (ψ + k (x, .), ψ - k (x, .)) K k=1 π + k (x) +d k (π + (x), π -(x)) max k ψ - k (x, y)dy 2 ≤ 1 + 2( √ 2 + √ 3)δ + 1 2 δ 2 ≤ (5δ) 2
The result follows from the fact we exhibited a 5δ covering of brackets of C, with cardinality

N P N Ψ .
C.2 Bracketing entropy of weight's families

C.2.1 When W K is a compact
We demonstrate that for any δ ∈ [0; √ 2],

H [.],sup x d k δ 5 , P ≤ H max k ∞ 3 √ 3δ 20 √ K , W K Proof. We show that ∀(w, z) ∈ (W K ) 2 , ∀k ∈ {1, . . . , K}, ∀x ∈ X , | π w,k (x) -π z,k (x)| ≤ F (k, x)d(w, z), with F a function and d some distance. We define ∀k, ∀u ∈ R K , A k (u) = exp(u k ) K k=1 exp(u k ) , so π w,k (x) = A k (w(x)). ∀(u, v) ∈ (R K ) 2 , A k (v) -A k (u) = 1 0 ∇ A k (u + t(v -u)).(v -u)dt Besides, ∇ A k (u) = 1 2 A k (u) ∂ ∂u l (ln(A k (u))) 1≤l≤K = 1 2 A k (u) (δ k,l -A l (u)) 1≤l≤K RR n°8281 A k (v) -A k (u) = 1 2 1 0 A k (u + t(v -u)) K l=1 (δ k,l -A l (u + t(v -u))) (v l -u l )dt ≤ 1 2 1 0 A k (u + t(v -u)) K l=1 |δ k,l -A l (u + t(v -u))| |(v l -u l )| dt ≤ v -u ∞ 2 1 0 A k (u + t(v -u)) K l=1 |δ k,l -A l (u + t(v -u))| dt Since ∀u ∈ R K , K k=1 A k (u) = 1, K l=1 |δ k,l -A l (u)| = 2(1 -A k (u)) A k (v) -A k (u) ≤ v -u ∞ 1 0 A k (u + t(v -u)) (1 -A k (u + t(v -u))) dt ≤ 2 3 √ 3 v -u ∞ since x → √ x(1 -x) is maximal over [0;1] for x = 1 3 . We deduce that for any (w, z) in (W K ) 2 , for all k in {1, . . . , K}, for any x in X , | π w,k (x) -π z,k (x)| ≤ 2 3 √ 3 max l w l -z l ∞ .
By hypothesis, for any positive ǫ, an ǫ-net N of W K may be exhibited. Let w be an element of W K . There is a z belonging to the ǫ-net N such that max l z lw l ∞ ≤ ǫ. Since for all k in {1, . . . , K}, for any x in X ,

| π w,k (x) -π z,k (x)| ≤ 2 3 √ 3 max l w l -z l ∞ ≤ 2 3 √ 3 ǫ,
and

K k=1 π z,k (x) + 2 3 √ 3 ǫ -π z,k (x) + 2 3 √ 3 ǫ 2 = K 4ǫ 3 √ 3 2 , √ π z -2 3 √ 3 ǫ 2 ; √ π z + 2 3 √ 3 ǫ 2 z∈N is a 4ǫ √ K 3 √ 3 -bracketing cover of P. As a result, H [],sup x d k δ 5 , P ≤ H maxk ∞ 3 √ 3 20 √ K δ, W K . C.2.2 When W K = {0} ⊗ W K-1 with W a set of polynomials
We remind that

W =    w : [0; 1] d → R/w(x) = dW |r|=0 α r x r and α ∞ ≤ T W    Proposition 3. For all δ ∈ [0; √ 2], H [.],sup x d k δ 5 , P ≤ (K -1) d W + d d × ln √ 2 + 20 3 √ 3 T W √ K -1 d W + d d + ln 1 δ .
Proof. W K is a finite dimensional compact set. Thanks to the result in the general case, we get

H [.],sup x d k δ 5 , P ≤ H max k ∞ 3 √ 3δ 20 √ K -1 , W K ≤ H . ∞ 3 √ 3δ 20 √ K -1 dW +d d , α ∈ R (K-1)( d W +d d ) / α ∞ ≤ T W ≤ (K -1) d W + d d ln 1 + 20 √ K -1T W dW +d d 3 √ 3δ ≤ (K -1) d W + d d × ln √ 2 + 20 3 √ 3 T W √ K -1 d W + d d + ln 1 δ
The second inequality comes from: for all w, v in

W K , max k w k -v k ∞ ≤ max k dW |r|=0 |α k,r -β k,r | ≤ dW +d d max k,r |α k,r -β k,r |.

C.3 Bracketing entropy of Gaussian families

C.3.1 General case

We rely on a general construction of Gaussian brackets:

Proposition 4. Let κ ≥ 17 29 , γ κ = 25(κ -1 2 ) 49(1 + 2κ 5 )
. For any 0 < δ ≤ √ 2, any p ≥ 1 and any

δ Σ ≤ 1 5 √ κ 2 cosh( 2κ 5 )+ 1 2 δ p , let (υ, L, A, D) ∈ Υ × [L -, L + ] × A(λ -, λ + ) × SO(p) and (υ, L, Ã, D) ∈ Υ × [L -, L + ] × A(λ -, +∞) × SO(p), define Σ = LDAD ′ and Σ = L D Ã D′ , t -(x, y) = (1 + κδ Σ ) -p Φ υ(x),(1+δΣ) -1 Σ(y) and t + (x, y) = (1 + κδ Σ ) p Φ υ(x),(1+δΣ) Σ(y). If            ∀x ∈ X , υ(x) -υ(x) 2 ≤ pγ κ L -λ - λ- λ+ δ 2 Σ 1 + 2 25 δ Σ -1 L ≤ L ≤ L ∀1 ≤ i ≤ p, |A -1 i,i -Ã-1 i,i | ≤ 1 10 δΣ λ+ ∀y ∈ R p , Dy -Dy ≤ 1 10 λ- λ+ δ Σ y then [t -, t + ] is a δ/5 Hellinger bracket such that t -(x, y) ≤ Φ υ(x),Σ (y) ≤ t + (x, y).
Admitting this proposition, we are brought to construct nets over the spaces of the means, the volumes, the eigenvector matrices and the normalized eigenvalue matrices. We consider three cases: the parameter (mean, volume, matrix) is known (⋆ = 0), unknown but common to all classes (⋆ = c), unknown and possibly different for every class (⋆ = K). For example, [ν K , L 0 , D c , A 0 ] denotes a model in which only means are free and eigenvector matrices are assumed to be equal and unknown.

If the means are free (⋆ = K), we construct a grid G ΥK over Υ K , which is compact. Since

H max k sup x . 2 pγ κ L -λ - λ - λ + δ Σ , Υ K ≤ D ΥK   C Υ + ln   1 pγ κ L -λ - λ- λ+ δ Σ     , G ΥK pγ κ L -λ - λ - λ + δ Σ ≤   C Υ + ln   1 pγ κ L -λ - λ- λ+ δ Σ     DΥ K .
If the means are common and unknown (⋆ = c), belonging to Υ 1 , we construct a grid

G Υc pγ κ L -λ - λ- λ+ δ Σ over Υ 1 with cardinality at most   C Υ + ln   1 pγ κ L -λ - λ- λ+ δ Σ     DΥ 1 .
Finally, if the means are known (⋆ = 0), we do not need to construct a grid. In the end,

G Υ⋆ pγ κ L -λ - λ- λ+ δ Σ ≤   C Υ + ln   1 pγκL-λ- λ - λ + δΣ     Zυ,⋆ , with Z υ,K = D ΥK , Z υ,c = D Υ1 and Z υ,0 = 0.
Then, we consider the grid G L over [L -, L + ]: . For the grid G A , we look at the condition on the p -1 first diagonal values and obtain:

G L 2 25 δ Σ = L -1 + 2 25 δ Σ g /g ∈ N, L -1 + 2 25 δ Σ g ≤ L + G L 2 25 δ Σ ≤ 1 + ln L+ L- ln 1 + 2 25 δ Σ Since δ Σ ≤ 2
G A 1 10 λ - λ + δ Σ ≤   2 + ln λ+ λ- ln 1 + 1 10 λ- λ+ δ Σ   p-1 Since δ Σ ≤ 2 5 , ln 1 + 1 10 λ- λ+ δ Σ ≥ 5 52 λ- λ+ δ Σ , then G A 1 10 λ - λ + δ Σ ≤ 2 + 52 5δ Σ λ + λ - ln λ + λ - p-1 ≤ 4 + 52 λ + λ - ln λ + λ - p-1 1 5δ Σ p-1 RR n°8281 Let Z L,0 = Z D,0 = Z A,0 = 0, Z L,c = Z D,c = Z A,c = 1, Z L,K = Z D,K = Z A,K = K. We define f υ,⋆ from Υ ⋆ to Υ K by      0 → (υ 0,1 , . . . , υ 0,1 ) if ⋆ = 0 υ → (υ, . . . , υ) if ⋆ = c (υ 1 , . . . , υ K ) → (υ 1 , . . . , υ K ) if ⋆ = K and similarly f L,⋆ , f D,⋆
and f A,⋆ , respectively from (R + )

ZL,⋆ into (R + ) K , from (SO(p)) ZD,⋆ into (SO(p)) K and from A(λ -, λ + ) ZA,⋆ into A(λ -, λ + ) K .

We define

Γ : (υ 1 , . . . , υ K , L 1 , . . . , L K , D 1 , . . . , D K , A 1 , . . . , A K ) → (υ k , L k D k A k D ′ k ) 1≤k≤K and Ψ : (υ k , Σ k ) 1≤k≤K → (Φ υ k ,Σ k ) 1≤k≤K . The image of Υ ⋆ × [L -, L + ] ZL,⋆ × SO(p) ZD,⋆ × A(λ -, λ + ) ZA,⋆ by Ψ • Γ • (f υ,⋆ ⊗ f L,⋆ ⊗ f D,⋆ ⊗ f A,⋆ ) is the set G of all K-tuples of Gaussian densities of type [υ ⋆ , L ⋆ , D ⋆ , A ⋆ ].
Now, we define B:

(υ k , Σ k ) 1≤k≤K → (1 + κδ Σ ) -p Φ υ k ,(1+δΣ) -1 Σ k , (1 + κδ Σ ) p Φ υ k ,(1+δΣ)Σ k 1≤k≤K . The image of G Υ⋆ × G ZL,⋆ L × G ZD,⋆ D × G ZA,⋆ A by B • Γ • (f υ,⋆ ⊗ f L,⋆ ⊗ f D,⋆ ⊗ f A,⋆ ) is a δ/5-bracket covering of G, with cardinality bounded by   λ + exp (C Υ ) pγ κ L -λ 2 -δ Σ   ZΥ,⋆ ×   4 + 129 ln L+ L- 10δ Σ   ZL,⋆ × c ZD,⋆ U 10λ + λ -δ Σ p(p-1) 2 ZD,⋆ × 4 + 52 λ + λ - ln λ + λ - (p-1)ZA,⋆ 1
C = ln 5p κ 2 cosh 2κ 5 + 1 2 + Z υ,⋆ C Υ D + Z υ,⋆ 2D ln λ + pγ κ L -λ 2 - + Z L,⋆ D ln   4 + 129 ln L+ L- 10   + Z D,⋆ D ln(c U ) + p(p -1) 2 ln 10λ + λ - + Z A,⋆ (p -1) D ln 4 5 + 52λ + 5λ - ln λ + λ - C.3.

With polynomial means

Using previous work, we only have to handle Υ K 's bracketing entropy. Just like for W K , we aim at bounding the bracketing entropy by the entropy of the parameters' space. We focus on the example where Υ K = Υ K and

Υ =    υ : [0; 1] d → R p ∀j ∈ {1, . . . , p}, ∀x, υ j (x) = dΥ |r|=0 α (j) r x r and α ∞ ≤ T Υ   
We consider for any υ, ν in Υ and any x in

[0; 1] d , υ(x) -ν(x) 2 2 = p j=1   dΥ |r|=0 α (j) r -β (j) r x r   2 ≤ p j=1   dΥ |r|=0 α (j) r -β (j) r 2     dΥ |r|=0 x 2r   ≤ d Υ + d d p j=1 dΥ |r|=0 α (j) r -β (j) r 2 ≤ p d Υ + d d 2 max j,r α (j) r -β (j) r 2
So,

H [.],max k sup x 2 (δ, Υ K ) ≤ H max k,j,r |.|   δ √ p dΥ+d d ,    α (j,k) r 1≤j≤p |r|≤dΥ 1≤k≤K α ∞ ≤ T Υ      ≤ pK d Υ + d d ln 1 + √ p dΥ+d d T Υ δ ≤ pK d Υ + d d ln √ 2 + √ p d Υ + d d T Υ + ln 1 δ ≤ D ΥK C Υ + ln 1 δ with D ΥK = pK dΥ+d d and C Υ = ln √ 2 + √ p dΥ+d d T Υ .
C.4 Proof of the key proposition to handle bracketing entropy of Gaussian families

C.4.1 Proof of Proposition 4 Proof. [t -, t + ] is a δ/5 bracket. Since (1 + δ Σ ) Σ-1 -(1 + δ Σ ) -1 Σ-1 = ((1 + δ Σ ) -(1 + δ Σ ) -1
) Σ-1 is a positive-definite matrix, Maugis and Michel's lemma can be applied.

Lemma 5. ( [START_REF] Maugis | A non asymptotic penalized criterion for gaussian mixture model selection[END_REF]) Let Φ υ1,Σ1 and Φ υ2,Σ2 be two Gaussian densities with full rank covariance matrix in dimension p such that Σ -1 1 -Σ -1 2 is a positive definite matrix. For any y ∈ R p ,

Φ υ1,Σ1 (y) Φ υ2,Σ2 (y) ≤ |Σ 2 | |Σ 1 | exp 1 2 (υ 1 -υ 2 ) ′ (Σ 2 -Σ 1 ) -1 (υ 1 -υ 2 ) . RR n°8281 Thus, ∀x ∈ X , ∀y ∈ R p , t -(x, y) t + (x, y) = (1 + κδ Σ ) -p (1 + κδ Σ ) p Φ υ(x),(1+δΣ) -1 Σ(y) Φ υ(x),(1+δΣ) Σ(y) ≤ 1 (1 + κδ Σ ) 2p (1 + δ Σ ) p (1 + δ Σ ) -p = 1 + δ Σ (1 + κδ Σ ) 2 p = 1 + δ Σ 1 + 2κδ Σ + κ 2 δ 2 Σ p ≤ 1 For all x in X , d 2 y (t -, t + ) = t -(x, y)dy + t + (x, y) dy -2 t -(x, y) t + (x, y)dy = (1 + κδ Σ ) -p + (1 + κδ Σ ) p -2(1 + κδ Σ ) -p/2 (1 + κδ Σ ) p/2 × Φ υ(x),(1+δΣ) -1 Σ(y) Φ υ(x),(1+δΣ) Σ(y) dy = (1 + κδ Σ ) -p + (1 + κδ Σ ) p -(2 -d 2 y Φ υ(x),(1+δΣ) -1 Σ(y), Φ υ(x),(1+δΣ) Σ(y) .
Using the following lemma, Lemma 6. Let Φ υ1,Σ1 and Φ υ2,Σ2 be two Gaussian densities with full rank covariance matrix in dimension p, then

d 2 (Φ υ1,Σ1 , Φ υ2,Σ2 ) = 2 1 -2 p/2 |Σ 1 Σ 2 | -1/4 |Σ -1 1 + Σ -1 2 | -1/2 × exp - 1 4 (υ 1 -υ 2 ) ′ (Σ 1 + Σ 2 ) -1 (υ 1 -υ 2 ) .
we obtain

d 2 y (t -, t + ) = (1 + κδ Σ ) -p + (1 + κδ Σ ) p -2 2 p/2 (1 + δ Σ ) + (1 + δ Σ ) -1 -p/2 = 2 -2 2 p/2 (1 + δ Σ ) + (1 + δ Σ ) -1 -p/2 + (1 + κδ Σ ) -p -2 + (1 + κδ Σ ) p Applying Lemma 7 Lemma 7. For any 0 < δ ≤ √ 2 and any p ≥ 1, let κ ≥ 1 2 and δ Σ ≤ 1 5 √ κ 2 cosh( 2κ 5 )+ 1 2 δ p , then δ Σ ≤ 2 5p ≤ 2 5 .
and Lemma 8. For any p ∈ N * , for any δ Σ > 0,

2 -2 p/2+1 (1 + δ Σ ) + (1 + δ Σ ) -1 -p/2 ≤ pδ Σ 2 2 ≤ p 2 δ Σ 2 2
Furthermore, if pδ Σ ≤ c, then

(1 + κδ Σ ) p + (1 + κδ Σ ) -p -2 ≤ κ 2 cosh(κc)p 2 δ Σ 2 .
with c = 2 5 , it comes out that:

sup x d 2 y (t -(x, y), t + (x, y)) ≤ δ 5 2 .
Now, we show that for all x in X , for all y in R p , t -(x, y) ≤ Φ υ(x),Σ (y) ≤ t + (x, y). We use therefore Lemma 9, thanks to the hypothesis made on covariance matrices.

Lemma 9. Let (L, A, D) ∈ [L -, L + ]×A(λ -, λ + )×SO(p) and ( L, Ã, D) ∈ [L -, L + ]×A(λ -, ∞)× SO(p), define Σ = LDAD ′ and Σ = L D Ã D′ . If      (1 + δ L ) -1 L ≤ L ≤ L ∀1 ≤ i ≤ p, |A -1 i,i -Ã-1 i,i | ≤ δ A λ -1 - ∀y ∈ R p , Dy -Dy ≤ δ D y then (1 + δ Σ ) Σ-1 -Σ -1 and Σ -1 -(1 + δ Σ ) -1 Σ-1 satisfy ∀y ∈ R p ,y ′ (1 + δ Σ ) Σ-1 -Σ -1 y ≥ L-1 (δ Σ -δ L )λ -1 + -(1 + δ Σ )λ -1 -(2δ D + δ A ) y 2 ∀y ∈ R p ,y ′ Σ -1 -(1 + δ Σ ) -1 Σ-1 y ≥ L-1 1 + δ Σ δ Σ λ -1 + -λ -1 -(2δ D + δ A ) y 2 Using δ L = 2 25 δ Σ δ D = δ A = 1 10 λ- λ+ δ Σ
we get lower bounds of the same order:

∀y ∈ R p ,y ′ (1 + δ Σ ) Σ-1 -Σ -1 y ≥ L-1 2λ + δ Σ y 2 ∀y ∈ R p ,y ′ Σ -1 -(1 + δ Σ ) -1 Σ-1 y ≥ L-1 1 + δ Σ 7 10λ + δ Σ y 2
Let's compare Φ υ,Σ and t + .

Φ υ(x),Σ (y) (1 + κδ Σ ) p Φ υ(x),(1+δΣ) Σ(y) ≤ (1 + κδ Σ ) -p   |(1 + δ Σ ) Σ| |Σ| exp 1 2 (υ(x) -υ(x)) ′ (1 + δ Σ ) Σ -Σ -1 (υ(x) -υ(x))   ≤ (1 + δ Σ ) p/2 (1 + κδ Σ ) p   | Σ| |Σ| exp 1 2 (υ(x) -υ(x)) ′ (1 + δ Σ ) Σ -Σ -1 (υ(x) -υ(x))   .
But,

(1 + δ Σ ) Σ -Σ -1 = (1 + δ Σ ) Σ(Σ -1 -(1 + δ Σ ) -1 Σ-1 )Σ -1 = (1 + δ Σ ) -1 Σ -1 (Σ -1 -(1 + δ Σ ) -1 Σ-1 ) -1 Σ-1 RR n°8281
Thus by Lemma 9,

(υ(x) -υ(x)) ′ (1 + δ Σ ) Σ -Σ -1 (υ(x) -υ(x)) ≤ (1 + δ Σ ) -1 L -1 -λ -1 -(1 + δ Σ ) L 10 7 λ + δ -1 Σ L-1 λ -1 -υ(x) -υ(x) 2 ≤ 10 7 L -1 -λ -2 -λ + δ -1 Σ υ(x) -υ(x) 2 ≤ 10 7 L -1 -λ -2 -λ + δ -1 Σ pγ κ L -λ 2 -λ -1 + δ 2 Σ ≤ 10 7 pγ κ δ Σ Since | Σ| |Σ| = L L p 2 ≤ 1 + 2 25 δ Σ p/2 , Φ υ(x),Σ (y) (1 + κδ Σ ) p Φ υ(x),(1+δΣ) Σ(y) ≤ (1 + δ Σ ) p/2 (1 + 2 25 δ Σ ) p/2 (1 + κδ Σ ) p exp 5γ κ 7 pδ Σ . It suffices that 5γ κ 7 δ Σ ≤ ln   1 + κδ Σ √ 1 + δ Σ 1 + 2 25 δ Σ   Now let f (δ Σ ) = ln(1 + κδ Σ ) - 1 2 ln(1 + δ Σ ) - 1 2 ln 1 + 2 25 δ Σ f ′ (δ Σ ) = κ 1 + κδ Σ - 1 2(1 + δ Σ ) - 1 25 1 + 2 25 δ Σ = (27k -4)δ Σ + 50k -27 2(1 + κδ Σ )(1 + δ Σ )(25 + 2δ Σ ) Since κ > 17 29 , f ′ (δ Σ ) > k -27 50 (1 + κδ Σ )(1 + δ Σ ) 1 + 2 25 δ Σ Finally, since f (0) = 0 and δ Σ ≤ 2 5 , one deduces f (δ Σ ) > k -27 50 (1 + κδ Σ )(1 + δ Σ ) 1 + 2 25 δ Σ δ Σ ≥ k -27 50 1 + 2 5 κ 1 + 2 5 1 + 2 25 2 5 δ Σ = 5 7 125(k -27 50 ) 129 1 + 2 5 κ δ Σ ≥ 5 7 γ κ δ Σ RR n°8281
So Φ υ,Σ ≤ t + . t - Φυ,Σ is handled the same way.

(

+ κδ Σ ) -p Φ υ(x),(1+δΣ) -1 Σ(y) Φ υ(x),Σ 1
≤ (1 + κδ Σ ) -p |Σ| |(1 + δ Σ ) -1 Σ| exp 1 2 (υ(x) -υ(x)) ′ Σ -(1 + δ Σ ) -1 Σ -1 (υ(x) -υ(x)) ≤ (1 + δ Σ ) p/2 (1 + κδ Σ ) p exp 1 2 (υ(x) -υ(x)) ′ Σ -(1 + δ Σ ) -1 Σ -1 (υ(x) -υ(x)) Now Σ -(1 + δ Σ ) -1 Σ -1 = Σ (1 + δ Σ ) Σ-1 -Σ -1 (1 + δ Σ ) -1 Σ -1 = (1 + δ Σ ) Σ-1 (1 + δ Σ ) Σ-1 -Σ -1 -1 Σ -1 and (υ(x) -υ(x)) ′ Σ -(1 + δ Σ ) -1 Σ -1 (υ(x) -υ(x)) ≤ (1 + δ Σ ) L-1 λ -1 -2 Lλ + δ -1 Σ L -1 -λ -1 -pγ κ L -λ 2 -λ -1 + δ 2 Σ ≤ 2pγ κ (1 + δ Σ )δ Σ (y)
We only need to prove that

γ κ (1 + δ Σ )δ Σ ≤ ln 1 + κδ Σ √ 1 + δ Σ Let g(δ Σ ) = ln 1 + κδ Σ √ 1 + δ Σ g ′ (δ Σ ) = κ 1 + κδ Σ - 1 2(1 + δ Σ ) = κδ Σ + 2κ -1 2(1 + δ Σ )(1 + κδ Σ ) Provided that κ ≥ 1 2 and δ Σ ≤ 2 5 , g ′ (δ Σ ) > 2κ -1 2(1 + 2 5 )(1 + 2 5 κ)
.

Finally, since g(0) = 0,

g(δ Σ ) > 2κ -1 2(1 + 2 5 )(1 + 2 5 κ) δ Σ = 5(2κ -1) 14(1 + 2κ 5 ) δ Σ ≥ 7 5 γ κ δ Σ ≥ (1 + δ Σ ) γ κ δ Σ .
One deduces (1 + κδ Σ ) -p Φ υ(x),(1+δΣ) -1 Σ(y) ≤ Φ υ(x),Σ (y).

C.5 Proof of inequalities used for bracketing entropy's decomposition

For sake of completeness, we prove here the inequalities of Lemma 11 and 12 of [START_REF] Cohen | Conditional density estimation by penalized likelihood model selection and applications[END_REF] used in the proof of Lemma 4. RR n°8281

as cosh(x) ≥ 1, we have thus

f ′′ (x) ≤ d 2 .
Now since f (0) = 0 and f ′ (0) = 0, this implies for any x ≥ 0

f (x) ≤ d 2 x 2 2 ≤ d 2 2
x 2 2 .

We deduce thus that

2 -2 2 d/2 (1 + δ Σ ) + (1 + δ Σ ) -1 -d/2 ≤ 1 2 d 2 (ln(1 + δ Σ ))

C.6.3 Proof of Lemma9

Proof. By definition,

x ′ (1 + δ Σ ) Σ-1 -Σ -1 x = (1 + δ Σ ) L-1 p i=1 Ã-1 i,i | D′ i x| 2 -L -1 p i=1 A -1 i,i |D ′ i x| 2 = (1 + δ Σ ) L-1 p i=1 Ã-1 i,i | D′ i x| 2 -(1 + δ Σ ) L-1 p i=1 Ã-1 i,i |D ′ i x| 2 + (1 + δ Σ ) L-1 p i=1 Ã-1 i,i |D ′ i x| 2 -(1 + δ Σ ) L-1 p i=1 A -1 i,i |D ′ i x| 2 + (1 + δ Σ ) L-1 p i=1 A -1 i,i |D ′ i x| 2 -L -1 p i=1 A -1 i,i |D ′ i x| 2
Along the same lines,

x ′ Σ -1 -(1 + δ Σ ) -1 Σ-1 x = L -1 p i=1 A -1 i,i |D ′ i x| 2 -(1 + δ Σ ) -1 L-1 p i=1 Ã-1 i,i | D′ i x| 2 = L -1 p i=1 A -1 i,i |D ′ i x| 2 -(1 + δ Σ ) -1 L-1 p i=1 A -1 i,i |D ′ i x| 2 + (1 + δ Σ ) -1 L-1 p i=1 A -1 i,i |D ′ i x| 2 -(1 + δ Σ ) -1 L-1 p i=1 Ã-1 i,i |D ′ i x| 2 + (1 + δ Σ ) -1 L-1 p i=1 Ã-1 i,i |D ′ i x| 2 -(1 + δ Σ ) -1 L-1 p i=1 Ã-1 i,i |D ′ i x| 2 Now p i=1 Ã-1 i,i | D′ i x| 2 - p i=1 Ã-1 i,i |D ′ i x| 2 ≤ p i=1 Ã-1 i,i | D′ i x| 2 -|D ′ i x| 2 ≤ λ -1 - p i=1 | D′ i x| 2 -|D ′ i x| 2 ≤ λ -1 - p i=1 | D′ i x| -|D ′ i x| | D′ i x| + |D ′ i x| ≤ λ -1 - p i=1 ( Di -D i ) ′ x 2 1/2 p i=1 ( Di + D i ) ′ x 2 1/2 ≤ λ -1 -δ D x 2 x = λ -1 -2δ D x 2 .
Furthermore,

p i=1 Ã-1 i,i |D ′ i x| 2 - p i=1 A -1 i,i |D ′ i x| 2 ≤ p i=1 Ã-1 i,i -A -1 i,i |D ′ i x| 2 ≤ δ A λ -1 - p i=1 |D ′ i x| 2 = δ A λ -1 -x 2 .
We notice then that

(1 + δ Σ ) L-1 p i=1 A -1 i,i |D ′ i x| 2 -L -1 p i=1 A -1 i,i |D ′ i x| 2 = (1 + δ Σ ) L-1 -L -1 p i=1 A -1 i,i |D ′ i x| 2 ≥ (δ Σ -δ L ) L-1 λ -1 + x 2 while L -1 p i=1 A -1 i,i |D ′ i x| 2 -(1 + δ Σ ) -1 L-1 p i=1 A -1 i,i |D ′ i x| 2 = L -1 -(1 + δ Σ ) -1 L-1 p i=1 A -1 i,i |D ′ i x| 2 ≥ 1 -(1 + δ Σ ) -1 L-1 λ -1 + x 2 ≥ δ Σ 1 + δ Σ λ -1 + L-1 x 2 RR n°8281

  2 000 data points of example NP

Figure 1 :

 1 Figure 1: Typical realizations

  of steps of the algorithm Log-likelihood of the density estimate

Figure 2 :

 2 Figure2: Increase of the Log-likelihood of the estimated density at each step of our iterative Newton-EM algorithm in the example NP with 3 components and 2 000 data points.

-κ

  ln( s m (Y i |X i )) + pen(m) with pen(m) = κ dim(S m ). Note that our theorem ensures that there exists a κ large enough for Number of mixture components of the selected model (b) Example NP with 2 000 points

Figure 3 :

 3 Figure 3: Slope heuristic: plot of the selected model dimension with respect to the penalty coefficient κ. In both examples, κ is of order 1/2.

Figure 4 :

 4 Figure 4: Box-plot of the Kullback-Leibler distance according to the number of mixture components. On each graph, the right-most box-plot shows this Kullback-Leibler distance for the penalized estimator ŝ K

Figure 5 :

 5 Figure 5: Histograms of the selected K

5 ,

 5 ln 1 + 2 25 δ Σ ≥ 10 129 δ Σ . By definition of a net, for any D ∈ SO(p) there is a D ∈ G D 1 10 λ-λ+ δ Σ such that ∀y ∈ R p , Dy -Dy ≤ 1 10 λ-λ+ δ Σ y . There exists a universal constant c U such that G D

5 ,

 5 obtainH [.],sup x max k dy δ G ≤ D C + ln 1 δ with D = Z υ,⋆ + Z L,⋆ + p(p -1) 2 Z D,⋆ + (p -1)Z A,⋆ and

d 2 y 2 y 2 d 2 - 2 -d/ 2 = 2 1 --d/ 2 = 1 f

 222222121 ,k (π -(x)ψ -(x, .), π + (x)ψ + (x, .)) π + k (x)π - k (x) ψ - k (x, y) ψ + k (x, y)ψ - k (x, y) dy ≤ K k=1 π + k (x) max k d 2 y (ψ + k (x, .), ψ - k (x, .)) + d 2 k (π + (x), π -(x)) max k ψ - k (x, y)dy +2 K k=1 π + k (x) π + k (x)π - k (x) d y (ψ + k (x, .), ψ - k (x, (ψ + k (x, .), ψ - k (x, .)) + d 2 k (π + (x), π -(x)) max k ψ - k (x, y)dy +2 max k ψ - k (x, y)dy max k d y (ψ + k (x, .), ψ - k (x, .)) k (π + (x), π -(x)) +d k (π + (x), π -(x)) max k ψ - k (x, y)dy 2 RR n°8281Proof of Lemma 12. For all x in X ,ψ + k (x, y) π - k (x)ψ - k (x, y)dy ≤ d 2 y,k (π -(x)ψ -(x, .), π + (x)ψ + (x, .))C.6 Proof of lemmas used for Gaussian's bracketing entropy2 2 d/2 (1 + δ Σ ) + (1 + δ Σ ) -1 -d/2 = 2 1 -e ln(1+δΣ) + e -ln(1+δΣ) (cosh (ln(1 + δ Σ ))) 2f (ln(1 + δ Σ ))where f (x) = 1cosh(x) -d/2 . Studying this function yieldsf ′ (x) = d 2 sinh(x) cosh(x) -d/2-′′

2( 1 + 2 .

 12 and using ln(1+ δ Σ ) ≤ δ Σ 2 -2 2 d/2 (1 + δ Σ ) + (1 + δ Σ ) -1 -d/2 ≤ κδ Σ ) d + (1 + κδ Σ ) -d -2 = 2 (cosh (d ln(1 + κδ Σ )) -1) = 2g (d ln(1 + κδ Σ ))with g(x) = cosh(x) -1. Studying this function yieldsg ′ (x) = sinh(x) and g ′′ (x) = cosh(x)and thus, since g(0) = 0 and g ′ (0) = 0, for any 0 ≤ x ≤ c g(x) ≤ cosh(c) x 2Since ln(1 + κδ Σ ) ≤ κδ Σ , dδ Σ ≤ c implies d ln(1 + κδ Σ ) ≤ κc, we obtain thus(1 + κδ Σ ) d + (1 + κδ Σ ) -d -2 ≤ cosh(κc)d 2 (ln(1 + κδ Σ )) 2 ≤ κ 2 cosh(κc)d 2 δ 2 Σ .

RR n°8281

rue Honoré d'Estienne d'Orves Bâtiment Alan Turing Campus de l'École Polytechnique 91120 Palaiseau Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

We deduce thus that