Didier Chauveau
email: didier.chauveau@univ-orleans.fr

Vy Thuy

Lynh Hoang

Nonparametric mixture models with conditionally independent multivariate component densities

Keywords: EM algorithm, multivariate kernel density estimation, multivariate mixture, nonparametric mixture

Recent works in the literature have proposed models and algorithms for nonparametric estimation of finite multivariate mixtures. In these works, independent coordinates conditional on the subpopulation from which each observation is drawn is assumed, so that the dependence structure comes only from the mixture. Here this assumption is relaxed, allowing for independent multivariate blocks of coordinates, conditional on the subpopulation from which each observation is drawn. Otherwise the blocks density functions are completely multivariate and nonparametric. We propose an EM-like algorithm for this model, and derive some strategies for selecting the bandwidth matrix involved in the nonparametric estimation step of it. The performance of this algorithm is evaluated through several numerical simulations. We also experiment this new model and algorithm on an actual dataset from the model based, unsupervised clustering perspective, to illustrate its potential.

Introduction

Populations of individuals may often be divided into subgroups. The task in examining a sample of measurements to discern and describe subgroups of individuals, even when there is no observable variable that readily indexes into which subgroup an individual properly belongs, is sometimes referred to as "unsupervised clustering" in the literature, and in fact mixture models may be generally thought of as comprising the subset of clustering methods known as model-based clustering.

Finite mixture models may also be used in situations beyond those for which clustering of individuals is of interest. For one thing, finite mixture models give descriptions of entire subgroups (called components), rather than assignments of individuals to those subgroups. Indeed, even the subgroups may not necessarily be of interest; sometimes finite mixture models merely provide a means for adequately describing a particular distribution, such as the distribution of residuals in a linear regression model where outliers are present. Much of the theory of these models involves the assumption that the subgroups are distributed according to a particular parametric form and quite often this form is univariate or multivariate normal.

The most general model for nonparametric multivariate mixtures is as follows: suppose the vectors X 1 , . . . , X n are a simple random sample from a finite mixture of m > 1 arbitrary distributions. The density of each X i may be written

g θ (x i ) = m j=1 λ j f j (x i ), (1)
where x i ∈ R r , and θ = (λ, f ) = (λ 1 , . . . , λ m , f 1 , . . . , f m ) denotes the parameters of the statistical model. In this model λ j denotes the proportion (weight) of component j in the population; the λ j 's are thus positive and m j=1 λ j = 1. The f j 's are the component densities, drawn from some family of multivariate density functions F absolutely continuous with respect to Lebesgue measure. Note that the univariate (r = 1) case will only be briefly considered, since this paper focus on multivariate extensions.

Model (1) is not identifiable if no restrictions are placed on F, where "identifiable" means that g θ has a unique representation of the form (1) and also that we do not consider that "label-switching" -i.e., reordering the m pairs (λ 1 , f 1 ), . . . , (λ m , f m ) -produces a distinct representation. The most common restriction in the mixture literature is to assume that the family F is parametric, i.e. that any f ∈ F is completely specified by a finite-dimensional parameter. The most used and studied parametric mixture model is the Gaussian mixture, where f j is the density of a (eventually multidimensional) Gaussian distribution with mean µ j and variance (matrix) Σ j . Section 1.2 presents various ways of relaxing this parametric assumption while preserving some sort of identifiability property.

The EM algorithm

Mixture models are deeply connected to the EM algorithm. This algorithm, as defined in the seminal article [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], is more properly understood to be a class of algorithms, a number of which predate even [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] in the literature. These algorithms are designed for maximum likelihood estimation in missing data problems, of which finite mixture problems are canonical examples because the unobserved labels of the individuals (as in unsupervised clustering) give an easy interpretation of missing data. A recent account of EM principle, properties and generalizations can be found in [START_REF] Mclachlan | The EM Algorithm and Extensions[END_REF], and mixture models are deeply detailed in [START_REF] Mclachlan | Finite mixture models[END_REF].

In a missing data setup, the n-fold product of the pdf of the observations g θ corresponds to the incomplete data pdf, associated to the log-likelihood x (θ) = n i=1 log g θ (x i ). In mixture models and many other missing data situations, maximizing x (θ) leads to a difficult problem. Intuitively, EM algorithms replace this unfeasible maximization by the maximization of a pseudo-likelihood that resembles the likelihood for some complete data y that is defined from the model, so that this pseudo-likelihood is easy to maximize. Assuming y comes from a complete data pdf g c θ , the EM algorithm iteratively maximizes the operator Q(θ|θ (t) ) := E[log g c θ (y)|x, θ (t) ],

the expectation being taken relatively to the conditional distribution of (y|x), for the value θ (t) of the parameter at iteration t. Given an arbitrary starting value θ (0) , the EM algorithm generates a sequence (θ (t) ) t≥1 by iterating the following steps:

1. E-step: compute Q(θ|θ (t) ) 2 2. M-step: set θ (t+1) = argmax θ∈Θ Q(θ|θ (t) ).

In finite mixture models, the complete data associated with the actually observed sample x is y = (x, Z), where to each individual (multivariate) observation x i is associated an indicator variable Z i denoting its component of origin. Notationally, it is common to define Z i = (Z i1 , . . . , Z im ) with the indicator variables

Z ij = I{observation i comes from component j}, m j=1 Z ij = 1.
From (1), this means that P θ (Z ij = 1) = λ j , and (X i |Z ij = 1) ∼ f j , j = 1, ..., m. In this case, the expectation is w.r.t. the conditional distribution of the Z ij 's,

Q(θ|θ (t) ) := E[ n i=1 m j=1 Z ij log λ j f j (x i )|x, θ (t) ].
Conveniently, the M-step for finite mixture models always looks partly the same: No matter what form the f j 's take, the updates to the mixing proportions are given by

λ (t+1) j = 1 n n i=1 p (t) ij , for j = 1, . . . , m,
where p

(t) ij := P θ (t) (Z ij = 1|x i )
is the posterior probability that the individual i comes from component j. The updates for the f j 's depend on the particular form of the component densities. In parametric mixtures (i.e. when the family F is completely specified by a finitedimensional parameter), the updates of these parameters is often easy, and can be looked like weighted MLE estimates. This is the case for, e.g., Gaussian mixtures.

Previous work on semi-and non-parametric mixtures

In this work, the term "nonparametric" means that no assumptions are made about the form of the f j 's, even though the weights λ are scalar parameters. Note that other authors as, e.g., [START_REF] Lindsay | Mixture Models: Theory, Geometry, and Applications[END_REF], speak of "nonparametric mixture modeling" in a different sense: The family F is fully specified up to a finite-dimensional parameter, but the mixing distribution, rather than having finite support of known cardinality m like here, is assumed to be completely unspecified.

As said above, nonparametric mixture models are not identifiable if no restrictions are placed on the family F to which the f j 's belong. The classical definition of identifiability requires that any two different values θ = θ correspond to two different distributions g θ and g θ . Weaker notions of identifiability can be considered, and in the particular case of mixtures, the fact that there always exists m! permutations of the labels in θ = (λ 1 , . . . , λ m , f 1 , . . . , f m ) that result in the same distribution g θ is one of those. Sometimes, the essentially nonparametric density functions in F may be partially specified by scalar parameters, a case often called semi-parametric. For instance, in the univariate (r = 1) case, [START_REF] Bordes | Semiparametric estimation of a two-component mixture model[END_REF] and [START_REF] Hunter | Inference for mixtures of symmetric distributions[END_REF] proved that when f j (x) = f (x -µ j ) for some density f (•) that is symmetric about zero, the mixture (1) admits a unique representation whenever m ≤ 3, except in very special cases. In the multivariate situation, Benaglia et al. (2009a), and recently [START_REF] Chauveau | Semi-parametric estimation for conditional independence multivariate finite mixture models[END_REF] propose some semiparametric mixture models as well.

On the multivariate situation, the common restriction placed on F in a number of recent theoretical and algorithmic developments in the statistical literature is that each joint density f j (•) is equal to the product of its marginal densities. In other words, the coordinates of the X i vector are independent, conditional on the subpopulation or component (f 1 through f m ) from which X i is drawn. Therefore, model (1) becomes

g θ (x i ) = m j=1 λ j r k=1 f jk (x ik ).
(2)

This conditional independence assumption has been introduced by [START_REF] Hall | Nonparametric estimation of component distributions in a multivariate mixture[END_REF], who established that when m = 2, identifiability of parameters generally follows in r ≥ 3 dimensions but not in fewer than three. [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] extended this result, suggesting that the condition on m gets less restrictive as r increases; intuitively, dimensionality together with conditional independence help for identifiability. This results, nowadays known as the "curse of dimensionality in the reverse", says that for a given number of components m, there is a lower bound r m that the dimensionality of observations must exceed for the model to be identifiable. [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF] finally established the fundamental result of identifiability for model (2) if r ≥ 3, regardless of m.

Several authors addressed the problem of estimating the parameters of these semi-or nonparametric mixture models. In the univariate case, [START_REF] Bordes | Semiparametric estimation of a two-component mixture model[END_REF] and [START_REF] Hunter | Inference for mixtures of symmetric distributions[END_REF] both propose estimators based on a minimum contrast approach, a method impossible to extend beyond m = 2 components. For the multivariate model (2), [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] give estimators based on inversion of the mixture, that apply only in the case when m = 2 and r = 3, due to analytical difficulties appearing beyond this case.

The difficulties associated to these theoretically well grounded approaches encourage the development of estimation strategies based on the EM principle. In the univariate case, [START_REF] Bordes | A stochastic EM algorithm for a semiparametric mixture model[END_REF] first propose a univariate semiparametric (and stochastic) "EM-like" algorithm for a location-shift semiparametric mixture model

g θ (x) = m j=1 λ j f (x -µ j ), x ∈ R, θ = (λ, µ, f ).
The novelty that is hidden behind the term EM-like is that the M step is not a genuine maximization step. It is a hybrid algorithm that introduces a nonparametric, Weighted Kernel Density Estimation (WKDE) step. This algorithm hence gives kernel-density-like estimates for f . It is also a stochastic algorithm since, at each iteration, each observation in the dataset is randomly assigned to one of the mixture components. This assignment is based on the posterior probabilities of component membership. This algorithm is simple to program and is applicable practically for any number m of components, even beyond the cases for which identifiability has been proved.

For the multivariate model (2), an empirical "EM-like" algorithm for statistical estimation of its parameter has been introduced in Benaglia et al. (2009a). This algorithm called npEM (non-parametric EM) eliminates the stochasticity of the univariate algorithm from [START_REF] Bordes | A stochastic EM algorithm for a semiparametric mixture model[END_REF], but also relies on a WKDE step for the updates of the f jk 's. The corresponding npEM function for this algorithm is publicly available in the mixtools package [START_REF] Benaglia | mixtools: An R package for analyzing finite mixture models[END_REF] for the R statistical software R Development Core Team (2010), and is designed to estimate θ in model (2), and in some refinements of it. However, despite its empirical success, this algorithm lacks any sort of theoretical justification; indeed, it can only be called "EM-like" because it resembles an EM algorithm in certain aspects of its formulation. [START_REF] Levine | Maximum smoothed likelihood for multivariate mixtures[END_REF] corrects this shortcoming by introducing a smoothed loglikelihood function and formulating an iterative algorithm with a provable monotonicity property that happens to produce results that are similar to those of [START_REF] Benaglia | mixtools: An R package for analyzing finite mixture models[END_REF] in practice.

This article describes a new nonparametric mixture models that extends model (2) in the sense that it allows for conditionally independent multivariate and nonparametric component densities. Importantly, this extensions allows for dependence structures within multivariate subsets of coordinates, apart from the dependence induced by the mixture that is the unique dependence allowed in model (2). Note that the idea of using conditionally independent multivariate subsets of variables itself is not new in the world of usual parametric mixtures; see, e.g., [START_REF] Hunt | Mixture model clustering for mixed data with missing information[END_REF]. But the idea there is usually motivated by specific modelling needs, or for reducing the number of parameters in the covariance matrices of the component distributions. Our objective here is motivated by the need to extend the currently available nonparametric mixture models from the recent literature.

We present this model in Section 2, and verify that its parameters are identifiable using results from [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF] that go beyond the conditionally independent univariate case. We then focus on statistical estimation of these parameters in Section 3. We propose a new "EM-like" algorithm called mvnpEM since it relies -and is a multivariate (mv) per block extension of -the npEM algorithm introduced by Benaglia et al. (2009a). Like the EM-like algorithms presented in this introduction, our algorithm requires a weighted kernel density estimation step, which turns out here to be a multivariate WKDE. We thus describe possible bandwidth selection strategies for this WKDE in Section 3.2. Section 4 is devoted to implementation considerations and a study of the algorithm through large scale Monte-Carlo simulations. Section 5 describes an analysis, using our model, of an actual dataset from the machine learning community. The perspective there is unsupervised model-based clustering, illustrating the potential usefulness of our new mixture model approach relaxing the conditional independence assumption.

Nonparametric mixture with multivariate blocks

We assume now that each joint density f j is equal to the product of B multivariate densities that will correspond to conditionally independent multivariate blocks in the mixture model. Let the set of indices {1, ..., r} be partitioned into B disjoint subsets s l , i.e. {1, ..., r} = B l=1 s l , where 2 ≤ B < r is the total number of such blocks, and d l is the number of coordinates in lth block, i.e. lth block dimension. Actually, we will impose B ≥ 3 in practice in view of [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF] result implying that there is little hope to have an identifiable model for less than 3 independent blocks (see Section 2.1 below).

Here, the indices i, j, k and l denote a generic individual, component, coordinate, and block, 1

≤ i ≤ n, 1 ≤ j ≤ m, 1 ≤ k ≤ r and 1 ≤ l ≤ B (m,
r, B and n stand for the number of mixture components, repeated measurements, blocks, and the sample size). Suppose f j is equal to the product of f jl -the multivariate density function of jth component and lth block.

Then model (1) becomes

g θ (x i ) = m j=1 λ j B l=1 f jl (x is l ), ( 3
)
where x is l = {x ik , k ∈ s l } is the multivariate variable which have its coordinates in lth block. Hence this model assumes independence of blocks of multivariate densities, conditional on the subpopulation from which each observation is drawn. This is a main difference in comparison with the model of conditional independence (2) introduced by [START_REF] Hall | Nonparametric estimation of component distributions in a multivariate mixture[END_REF]: here the dependence structure does not come only from the mixture structure, since some additional within-block dependence is allowed. This model thus brings more flexibility with respect to the conditional independence assumption, that is in some applications a shortcoming of model ( 2) (see, for instance, our actual data application Section 5).

When all blocks are of size 1 (univariate blocks), then B = r and the model is the conditional independence assumption model (2). Thus, to have at least 1 multivariate block of size ≥ 2, we assume B < r in the sequel. Note that "block" have a different meaning in Benaglia et al. (2009a) and successive works on smoothed versions like [START_REF] Chauveau | Semi-parametric estimation for conditional independence multivariate finite mixture models[END_REF]. There, block means a group of coordinates sharing a same univariate density f j for component j, allowing for more parsimonious models motivated by some actual applications from psychometrics.

Identifiability considerations

As reviewed briefly in Section 1.2, [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] explored the identifiability question related to model (2) with univariate conditionally independent marginals. They also suggest that a similar result could be achievable for conditionally independent blocks of multivariate densities, that is precisely our model (3). Then [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF] proved a collection of identifiability results, based on a representation of some latent variable model in terms of 3-way contingency tables. Their results are based on an algebraic result of [START_REF] Kruskal | More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling[END_REF][START_REF] Kruskal | Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF], who describes a 3-way contingency table that cross-classifies a sample of n individuals with respect to three categorical variables, say X k , k = 1, 2, 3, each X k taking value in a state space {1, . . . , κ k } with κ k possible categories. This model assumes existence of a latent (unobservable) variable Z with values in {1, . . . , m} that is just an alternative coding of our binary variables Z ij 's. It is also assumed that conditionally on knowing the exact class {Z = j}, the 3 observed variables are mutually independent. This model is thus precisely a version of model ( 2) for per-components and coordinate finite measures. [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF] denote this m-class, r = 3-features model M(m; κ 1 , κ 2 , κ 3 ). The full details are in their article, and a survey-like shorter description for application to model (2) can be found in [START_REF] Chauveau | Semi-parametric estimation for conditional independence multivariate finite mixture models[END_REF]. We only summarize briefly this technique here, focusing on results concerning our model (3).

The representation of the r = 3 conditionally independent finite measures is done by defining matrices A k of size m×κ k , k = 1, 2, 3, where each A k 's row j describes the probability distribution of (X k |Z = j). Defining λ j : def = P (Z = j), and Ã1 = diag(λ)A 1 , the probability distribution of the latent class model (the finite mixture) is associated to the κ 1 ×κ 2 ×κ 3 tensor [ Ã1 , A 2 , A 3 ], that is the three-dimensional array whose element with coordinates (u 1 , u 2 , u 3 ) is a sum of products of elements of these three matrices, with column numbers u 1 , u 2 , u 3 respectively, added up over the m rows:

Ã1 , A 2 , A 3 u 1 ,u 2 ,u 3 = m j=1 λ j 3 k=1 P(X k = u k |Z = j).
Define the Kruskal rank of a matrix A, rank K (A), as the largest number I of rows such that every set of I rows of A is independent, and let

I k = rank K (A k ). Kruskal established that, if I 1 + I 2 + I 3 ≥ 2m + 2, then [A 1 , A 2 , A 3 ]
uniquely determines the A k 's, up to simultaneous permutation and rescaling of rows. Kruskal's result is a cornerstone of several subsequent results establishing identifiability criteria for various latent structure models. [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF] first reformulate it, proving identifiability of model M(m; κ 1 , κ 2 , κ 3 ) (up to label switching), providing that all entries of λ are positive. Then they extend that to the r-variate model M(m; κ 1 , ..., κ r ) with r ≥ 3, under the condition that there exists a tripartition of {1, ..., r} into three disjoint nonempty subsets S 1 , S 2 , S 3 , such that 3 l=1 min(m, τ l ) ≥ 2m + 2, where

τ l = k∈S l κ k .
Extension of Kruskal's work to finite mixtures of conditionally independent univariate nonparametric measures, that is model (2), is based on a judicious use of cut points to discretize the distributions associated to the f jk 's (Theorem 8). Considering 3 random variables at a time only, each X k is associated to

Y k = {1 {X k ∈I 1 k } , ..., 1 {X k ∈I κ k k } }, where R is parti- tionned into κ k consecutive intervals (I l k , 1 ≤ l ≤ κ k ).
Stochastic matrices are built from this construction, using the f jk 's associated c.d.f.s. It is possible to build these partitions general enough and well-chosen so that Kruskal's result applies to these matrices, and that identifiability for the continuous model can be linked to identifiability of the discrete one. This requires equivalence between linear independence of probability distributions and their corresponding c.d.f.s.

Finally, the case of multidimensional blocks of conditionally independent measures, model (3), is covered using a similar but more cumbersome construction (Theorem 9 in [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF]. Discrete random variables Y k 's are defined based on indicator functions of d l -product intervals, where d l is the lth block dimension. The equivalence between linear independence of the probability distributions and corresponding multidimensional c.d.f.'s remains valid, so that model (3) is identifiable in general.

Estimating the parameters

The algorithm we propose is an extension of the original npEM algorithm that was designed for estimation in the multivariate mixture model (2). The EM principle is first applied in the E-step, i.e. computation of the posterior probabilities given the current value θ (t) of the whole parameter. The EM machinery is also applied straightforwardly for the M-step of the scalar parameters that are only the weights λ. Then a nonparametric WKDE is applied to update the component densities per blocks. The main difference is that in this model, we need multivariate density estimates. This is also where this algorithm becomes "EM-like", since kernel density estimation is not a genuine maximization step.

A multivariate npEM algorithm (mvnpEM)

Given initial values θ (0) = (λ (0) , f (0) ), the mvnpEM algorithm consists in iterating the following steps:

1. E-step: Calculate the posterior probabilities (conditional on the data and θ (t) ), for each i = 1, . . . , n and j = 1, . . . , m:

p (t) ij := P θ (t) (Z ij = 1|x i ) = λ (t) j f (t) j (x i ) m j =1 λ (t) j f (t) j (x i ) , (4)
where

f (t) j (x i ) = B l=1 f (t) jl (x is l ).
2. M-step for λ:

λ (t+1) j = 1 n n i=1 p (t) ij , j = 1, . . . , m. (5)
3. Nonparametric kernel density estimation step: For any u in R d l , define for each component j ∈ {1, . . . , m} and block l ∈ {1, . . . , B},

f (t+1) jl (u) = 1 nλ (t+1) j n i=1 p (t) ij K H jl (u -x is l ), (6)
where K H jl is a multivariate kernel density function, typically Gaussian, and H jl is a symmetric positive definite d l × d l matrix known as the bandwidth matrix. This matrix may depend on the lth block and jth component, and even on the tth iteration, as it will be precised in the next Section.

Bandwidth selection in multivariate KDE

The central decision in the nonparametric density estimation step of both the npEM and mvnpEM algorithm is the selection of an appropriate value for the (scalar or matrix) bandwidth or smoothing parameter. Firstly, as in Benaglia et al. (2009a) it is possible to simply use a single fixed bandwidth for all components per coordinate within each block, selected by default according to a rule of thumb from [START_REF] Silverman | Density estimation for statistics and data analysis[END_REF]. Secondly, we investigate a often more appropriate strategy defining iterative and per component and coordinate bandwidths by adapting Silverman's rule of thumb as in [START_REF] Benaglia | Bandwidth Selection in an EM-like algorithm for nonparametric multivariate mixtures[END_REF].

Multivariate Kernel Density Estimation (KDE) has been used since a long time in multivariate data analysis (see, e.g., [START_REF] Scott | Multivariate density estimation[END_REF]. Forgetting for now about blocks and components, and considering a single sample (x 1 , . . . , x n ) iid from a pdf f over R r , the general form of a multivariate KDE is fH

(u) = 1 n n i=1 K H (u -x i ),
where, for u = (u 1 , u 2 , . . . , u r ) t ∈ R r ,

K H (u) = |H| -1/2 K(H -1/2 .u),
K is a multivariate kernel function, H is a symmetric positive definite r × r "bandwidth matrix", and H -1/2 .u is the usual matrix product.

With a full bandwidth matrix, the corresponding kernel smoothing is equivalent to prerotating the data by an optimal amount and then using a diagonal bandwidth matrix. The bandwidth matrix can be restricted to a class of positive definite diagonal matrices, and then the corresponding kernel function is often a product kernel (e.g. Gaussian). In this case, H = diag(h 2 1 , h 2 2 , . . . , h 2 r ) where h k denotes the kth coordinate bandwidth. Then |H| 1/2 = h 1 • • • h r so that (denoting informally by K both the multivariate and univariate kernels)

K H (u) = 1 h 1 • • • h r K u 1 h 1 , . . . , u r h r = r k=1 1 h k K u k h k .
In the simplest case H = diag(h 2 , . . . , h 2 ) we have

K H (u) = 1 h r K 1 h u .
In our mixture model with multivariate blocks, we propose to consider two cases for the d l ×d l diagonal bandwidth matrix associated to the lth block.

Case (i) Same bandwidth per block for all components The bandwidth matrix for block l is diagonal with scalar bandwidths for each coordinates in the block:

H l = diagonal(h 2 s l ), where h s l = (h k ) k∈s l .
The multivariate kernel for block l becomes

K H l (u) = 1 k∈s l h k K(H -1/2 l .u), u ∈ R d l ,
where h k is fixed and selected by default according to a rule of thumb from [START_REF] Silverman | Density estimation for statistics and data analysis[END_REF], page 48:

h k = 0.9 min{SD k , IQR k 1.34 }(n) -1/5 , (7)
and SD k and IQR k are respectively the standard deviation and interquartile range of the n univariate observations from the kth coordinate.

Case (ii) Adaptive bandwidth per block and component In this case the bandwidth matrix for block l is diagonal with scalar bandwidths for each coordinates in the block, but it depends also on component j and current algorithm iteration t:

H (t) jl = diagonal((h (t)
js l ) 2 ), where h (t)

js l = (h (t)
jk ) k∈s l .

The multivariate Kernel for block l, component j and iteration t is

K H (t) jl (u) = 1 k∈s l h (t) jk K (H (t) jl ) -1/2 .u , u ∈ R d l .
The values of the per-block and component bandwidths are computed following the adaptive bandwidth strategy from [START_REF] Benaglia | Bandwidth Selection in an EM-like algorithm for nonparametric multivariate mixtures[END_REF], except that in the present definition of our model there are no i.i.d. coordinates for which the n data can be pooled; as said previously, blocks in our model has a different meaning than in Benaglia et al. (2009a). Each scalar bandwidth is hence determined from the corresponding n scalar observations of coordinate k, using a Silverman's like rule weighted by the posterior probabilities at each iterations of the mvnpEM algorithm:

h (t+1) jk = 0.9min{σ (t+1) jk , IQR (t+1) jk 1.34 }(nλ (t+1) j ) -1/5 , (8)
where nλ (t+1) j

estimates the sample size in the jth component, and

µ (t+1) jk = n i=1 p (t) ij x ik n i=1 p (t) ij = n i=1 p (t) ij x ik nλ (t+1) j
, and

σ (t+1) jk = 1 nλ (t+1) j n i=1 p (t) ij (x ik -µ (t+1) jk ) 2 1/2
, are the weighted empirical means and variances.

To define the iterative interquartile range IQR (t+1) jk appearing in (8), we introduce a weighted quantile estimate as in [START_REF] Benaglia | Bandwidth Selection in an EM-like algorithm for nonparametric multivariate mixtures[END_REF]. Let a 1 , . . . , a ν be real numbers and w 1 , . . . , w ν be associated (nonnegative) weights, with

W = w 1 + • • • + w ν . Denote τ (•) the permutation sorting the a i 's in non-decreasing order, a τ (1) ≤ • • • ≤ a τ (ν)
. For α ∈ (0, 1), define the weighted α quantile estimate to be α τ (iα) , where i α = min{s :

s i=1 w τ (i) ≥ αW },
is the smallest integer that gives at least a proportion α of the total sum of weights W . We compute IQR (t+1) jk as the difference between the estimated 0.75 and 0.25 quantiles of the ν = n observations from the kth coordinate, using weights w i = p (t+1) ij for the jth component. Note that functions for computing these quantiles are provided in the mixtools package [START_REF] Benaglia | mixtools: An R package for analyzing finite mixture models[END_REF].

Implementation and simulated examples

We propose in this section some examples illustrating the performances of our algorithm, on two synthetic multivariate models, after some details about implementation and experiment settings. The mvnpEM algorithm defined in Section 3.1 has been implemented in the development version of the mixtools package [START_REF] Benaglia | mixtools: An R package for analyzing finite mixture models[END_REF] for the R statistical software R Development Core Team (2010), and will be made publicly available in a future version of it. In particular, the step requiring nonparametric multivariate WKDE's has been coded in C to speed up the CPU time.

Initialization of the mvnpEM algorithm.

As it is typically the case for EM algorithms, the choice of the starting parameter value θ (0) is important. In parametric settings, a simple manner consists in starting the algorithm from a parameter value "reasonably close" to the true value, that may be given by a priori knowledge obtained from some expert on the model and data. When this sort of information is not available, the usual practice consists in starting the algorithm from several values randomly drawn from a uniform distribution on the parameter space (or a subset of it), and retaining the EM estimate achieving the maximum of the observed likelihood among all the trials. If this exhaustive exploration of the parameter support is done with enough precision (enough random draws), then at least some of these randomly chosen θ (0) 's fall close enough to the global maximum so that the final estimate corresponds to the location of the global maximum.

In our nonparametric setup, we can see that the first E-step of mvnpEM requires initial values for the f (0) j 's (and λ (0) j 's) that themselves only require an initial n × m matrix of posteriors P (0) := (p (0) ij , i = 1, . . . , n, j = 1, . . . , m). To obtain this matrix, the most appealing method consists in using a prior clustering of the data using any unsupervised algorithm such as k-means, that assign each observation to one initial components as, e.g., in Benaglia et al. (2009a). At this point, the parallel of the parametric initialization method based on some prior knowledge on the model and data consists in providing k-means with meaningful cluster centers instead of letting it randomly choose m centers. These "weakly informative" centers, even vaguely related to the true component means, usually help k-means finding an initial clustering good enough for an EM algorithm to start with. If such even crude prior information is not available, one can just provide k-means with the number of clusters m, so that m data points are randomly chosen as the initial centers. To be fair in our experiments, this completely blind, automatic and data-driven initialization is actually what we did in all our simulated and real data situations hereafter. We never experienced any difficulties (such as, e.g., the algorithm emptying one component after few iterations due to a very poor initialization). Note also that this k-means based initialization is also often used in standard EM algorithms for, e.g., multivariate Gaussian mixtures, where clusters means and (co)-variances are used as initialization means and variances for the component Gaussian distributions.

In even more complex situations where the above initialization strategies fail we can proceed by analogy with the parametric space exploration: drawing P (0) posterior matrices randomly (uniformly) several times, and run several mvnpEM algorithm initialized with these P (0) 's. Then retain the θ corresponding to the largest "observed loglikelihood" n i=1 log g θ(x i ) which is not in the nonparametric case a true likelihood but merely an empirical criterion. The uniform simulation of P (0) can be done in several ways, e.g. simply by choosing, for each row the j for which p (0) ij = 1 uniformly in {1, . . . , m}. One can also use uniform Dirichlet if non 0/1 weights are desired. There is also always the possibility to run a first parametric Gaussian EM to get a first matrix of posteriors to start mvnpEM. We tried the initialization strategy using uniform Dirichlet for ModelsA and B, and obtained the same results as with the k-means initialization.

Handling the label-switching problem Not surprisingly, the data-driven initialization without specifying centers to the k-means procedure generates more label-switching than when proper centers are provided. As explained in Section 1, label-switching refers to the fact that arbitrary re-orderings of the component indices (1, . . . , m) correspond to the same mixture model. In a single real data study, label switching is not important since component index does not change interpretation. But these re-orderings are possible when numerous instances of the same mixture problem are solved. Hence label-switching becomes problematic in Monte-Carlo simulation studies and bootstrap estimation involving mixture models. For detailed explanation, see discussion in [START_REF] Mclachlan | Finite mixture models[END_REF] (section 4.9), and for an illustrative stochastic EM example see [START_REF] Celeux | Stochastic versions of the EM algorithm: An experimental study in the mixture case[END_REF]. In their study, [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] dealt with label-switching in the same context by enforcing the constraint λ1 < λ2 . Here, we choose to detect and "switch-back" the estimates (the final matrix of posteriors here, from which the other estimates are computed) to be in accordance with the initial representation. Since in all our experiments we set λ 1 < λ 2 , we decide that a switching occured after a replication if λ1 > λ2 , in which case we switch the parameters from 1 st component to 2 nd component and inversely.

In our Monte-Carlo experiments, we computed the errors in terms of the square root of the Mean Integrated Squared Error (MISE) for the densities as in [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] and Benaglia et al. (2009a):

M ISE jl = 1 S S s=1 ( f (s) jl (u) -f jl (u)) 2 du,
where the integral over R d l is computed numerically and f (s) jl is the density estimate at replication s, computed from (6) but using the final values of the p (t) ij 's, i.e. the posterior probabilities after convergence of the algorithm that we denote pij 's.

A difference with both [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] and Benaglia et al. (2009a) results is that in their work the Integrated Squared Errors ISE jl = ( fjl -f jl ) 2 were evaluated using numerical integrations of univariate densities (since the f jl 's were univariate only). Here, it appears that estimating f jl for multivariate densities with strong dependence structure using a kernel density estimate (KDE) with diagonal bandwidth matrix is more difficult, and this difficulty may results in overestimated MISE values, not necessarily implying a poor fitting of the mixture by the algorithm. To illustrate that in a simple case, we ran S = 300 replications of n = 300 observations of a single bivariate sample (i.e. no mixture, no posteriors, usage of standard unweighted KDE) from a centered bivariate Gaussian density f with unit variances and varying correlation ρ. We then computed M ISE f = 1 S S s=1 ( f (s) -f ) 2 using a bandwidth matrix following [START_REF] Silverman | Density estimation for statistics and data analysis[END_REF] as in (7). Results are in Table 1 This shows that estimation of the MISE deteriorates as correlation increases. Using a non-diagonal bandwidth matrix is thus an interesting perspective for future work, to better recover multivariate and strongly correlated component and block densities. In our present setup and experiment, in order to get results not too biased by this KDE problem i.e. to obtain comparable M ISE jl 's between univariate and multivariate blocks, we selected variances matrices Σ j 's with not too strong correlations (up to 50%).

We also computed the mean squared error (MSE) for the proportions that are the only scalar parameters in these models. In our models with just m = 2 components, we have for

λ 1 : M SE λ 1 = 1 S S s=1 ( λ(s) 1 -λ 1 ) 2 ,
where, at replication s, λ(s) 1 is computed using ( 5) with the final values of the posterior probabilities, pij 's. Note that we computed and displayed as well MSE's for other scalar empirical moments like means and variances, but these are not genuine parameters of the model, i.e. they are provided only as additional criteria. At each replication, these scalar measures are weighted versions of the empirical estimates; for instance, the mean for component j and coordinate k is given by μjk

= n i=1 pij x ik n i=1 pij = n i=1 pij x ik n λj .

Model A: simple Gaussian data

We first introduce this simple model with two univariate blocks and one bivariate block, chosen intentionally as close as possible to model (2) (with conditionally independent univariate marginals) used first by [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] to illustrate the performance of their estimation technique based on inverting the mixture. Their example was considering r = 3 conditionally independent univariate Gaussian, all N (0, 1) for component 1, and N (3, 1), N (4, 1) and N (5, 1) for component 2. This model has being used later in Benaglia et al. (2009a) for comparison with the npEM algorithm.

We consider a r = 4 variables, m = 2 components Gaussian mixture which have 1 multivariate block, i.e. B = 3 blocks of coordinates with s 1 = {1}, s 2 = {2}, s 3 = {3, 4}. Densities f jl are univariate normals for l = 1, 2, and bivariate Gaussian for block l = 3, where the means are given in Table 2, and the common covariance matrix of the bivariate block is

Σ = 1 1/2 1/2 1 . Model A Block 1 Block 2 Block 3 Coordinate(s) 1 2 {3, 4} Component 1 N (0, 1) N (0, 1) N 2 0 0 , Σ Component 2 N (3, 1) N (4, 1) N 2 3 3 , Σ Table 2: Parameters for Model A.
Hence to allow comparison with the original npEM and both [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] and Benaglia et al. (2009a) results for the univariate coordinates, we kept individual densities as in their examples for the first and the second block. We also kept their experiment settings: S = 300 replications of n = 500 observations each, where λ 1 is varying from 0.1 to 0.4. Results for model A ran with the adaptive bandwidth strategy are given in Fig. 1. We obtained similar results with the same bandwidth setting; these results are omitted here for brevity. For this model with similar ranges across components and blocks, the bandwidth strategy does not make a noticeable difference. These results were obtained, as said in Section 4.1, using k-means initialization with randomly chosen initial centers and checking for label switching.

The stable behavior of the MSE's for λ 1 and for the other scalar measures (means, covariances) estimates show that the algorithm behaves well. In particular, density and scalar estimates associated to component 1 (black curves) decrease when λ 1 increases, as expected since the proportion of data actually coming from this component increases with λ 1 . Simultaneously, the estimates associated with component 2 increase (red curves). Moreover, the results for the √ M ISE f jl 's are close to the results we can see on the plots on page 517, figure 2 of Benaglia et al. (2009a) and outperform the plots on page 675, figure 2 of [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] for univariate blocks.

Model B: Gaussian, heavy-tailed and skewed data

We also experiment our method on a second model, with three bivariate blocks using the full potential of our approach. We wanted here to show that our algorithm can compete to some extent with fitting Gaussian mixtures where mixture components are indeed Gaussian, and do better when they are non Gaussian, all this using a single model for brevity. Model B thus has one bivariate Gaussian block, one bivariate block with heavy-tailed (Student) distributions, and one bivariate block with heavy-tailed and severely skewed distributions. Precisely, it has r = 6 variables, m = 2 components, where λ 1 is kept fixed to 30 %, and B = 3 blocks. Block 1 involves bivariate Gaussian densities N 2 (µ j1 , Σ)'s with some correlation structure; block 2 involves bivariate non-central Student densities t 2 (µ j2 , Σ)'s with same correlation structure. The component densities of block 3 are themselves mixtures of bivariate Gaussian contaminated by bivariate Student's, thus generating skewed densities. This model involves two covariance matrices,

Σ = 1 1/4 1/4 1 and Σ = 1 1/2 1/2 4 ,
where Σ is used only in block 3, component 2. The other parameters are given in Table 3.

Model B Block 1 Block 2 Block 3 s l {1, 2} {3, 4} {5, 6} j = 1 N 2 0 0 , Σ t 2 0 0 , Σ, df = 4 87%t 2 0 0 , Σ, df = 4 + 13%N 2 4 6 , Σ j = 2 N 2 1 5 , Σ t 2 2 5 , Σ, df = 4 87%t 2 2 8 , Σ, df = 4 + 13%N 2 5 14 , Σ Table 3: Parameters for Model B.
Before presenting a full Monte-Carlo experiment as for model A, we display in Figure 2 the true marginal densities of this model, together with a result from a single run of the mvnpEM algorithm and a result given by a standard Gaussian EM algorithm, the mvnormalmixEM function from the mixtools package [START_REF] Benaglia | mixtools: An R package for analyzing finite mixture models[END_REF] The estimate for the proportion in this run has been λ1 = 0.284 for our nonparametric method, and 0.282 for the Gaussian EM. We also computed the estimates of the covariances for block 1 (the one for which the true values are given in Σ). Both mvnpEM and the Gaussian EM gave estimates of about 0.236 in both components.

We then ran S = 300 replications of samples of sizes n = 400, 600, 800, 1000. As for model A, we computed the M ISE of the densities and the mean squared error (MSE) of the scalar parameter (λ 1 ) and some other descriptive scalar measures (for the Gaussian block 1 only). q q q q q q q q q q q q q q q q q q q q q q q q 400 500 600 700 800 900 1000 0.00 0.02 0.04 0.06 0.08 0.10 0.12 0.14 mvnpEM -same bandwidth n sqMISE or sqMSE q q q q q q q q q q q q q q q q q q q q q q q q q q q f j1 f j2 f j3 Gaussian EM n sqMISE or sqMSE q q q q q q q q q q q q q q q q q q q q q q q q Figure 3: Square roots of MISE's for the densities as a function of the sample size n, S = 300 replications, for the two algorithm settings for Model B: mvnpEM adaptive bandwidth (left), mvnpEM same bandwidth (middle) and Gaussian EM (right). MISE for Densities are plotted in circles and solid lines (block 1), dashed lines (block 2) and dot-dashed (block 3).

Our purpose was also to build a model illustrating the performance of the adaptive bandwidth strategy (Section 3.2), which is appropriate typically for models with different ranges of observations per components and coordinates. Figure 3 confirm this behavior, with a slight advantage for the adaptive bandwidth, particularly in block 3, as expected. Figure 3 also shows that the MISE's decrease when the sample size n increases, which can be understood as numerical evidence of "convergence" (see the Discussion about these convergence-related questions). Finally we can see, by comparing marginal densities in the single example Fig. 2 and MISE's Fig. 3 across the nonparametric and parametric solutions block per block, that our method performs slightly less better than the Gaussian method for the Gaussian block 1, but better than it for the heavy-tailed block 2, and even better for the heavy-tailed and skewed block 3. In blocks 2 and 3, the parametric estimates even show no convergence at all as n increases.

An example on actual data

We consider in this section a real dataset from an experiment involving n = 569 instances about Wisconsin Diagnostic Breast Cancer (WDBC). This database is available through the UW CS ftp server. The attributes in the WDBC dataset are the Diagnosis (M = malignant, B = benign) and ten real-valued features computed for each cell nucleus: Radius, Texture, Perimeter, Area, Smoothness, Compactness, Concavity, Concave points, Symmetry and Fractal dimension. These features are computed from a digitized image of a breast mass. The mean, standard error, and "worst" (mean of the three largest values) of these features are computed for each image, resulting in a total of 30 features.

This actual dataset has already been used as an illustration for comparing supervised and unsupervised clustering methods. The principle of such a study from the unsupervised clustering perspective consists in clustering the population based on the quantitative variables, and after that compare these estimates with the observed classes. For model-based clustering using mixture models, the clustering is done using the Maximum A Posteriori (MAP) strategy deduced from the parameter estimate θ given by any EM-like algorithm. The MAP consists in setting Ẑij 0 = 1, where j 0 = arg max j=1,...,m {p ij } , and Ẑij = 0 for j = j 0 ,

where the pij 's are as before the posterior probabilities after convergence of the algorithm. The MAP classifier is compared here with the classes given by Diagnosis variable (62.74% B and 37.26% M).

Our motivation in using this dataset is not to find a scientific definitive answer or the best clustering algorithm. We have choosen this dataset because: (i) it illustrates the potential and feasibility of our estimation algorithm for models involving blocks and data of moderate to large dimensions; (ii) there are obvious dependence structures across some coordinates that prevent the usage of the previous nonparametric npEM approach from Benaglia et al. (2009a) since the conditional independence of coordinates is obviously violated (see Fig. 4 below); (iii) it has been used recently in [START_REF] Hennig | Methods for merging gaussian mixture components[END_REF], who propose a competitive alternative modelbased parametric but not simply Gaussian clustering: their method amounts to build clusters by merging components obtained from a Gaussian mixture model fit. Hence their cluster distributions are not Gaussian, they can e.g., be multimodal.

In their merging Gaussian method, Hennig (2010) just used the ten first features (means) of the WDBC dataset. Hence we first tried our approach on this r = 10 dimensional dataset. We had to define multivariate conditionally independent blocks prior to apply our mvnpEM algorithm. A simple exploration of the data shows that there are some obvious correlations across coordinates, not due to a mixture. Fig. 4 displays the most obvious such dependences among the ten mean features. It is for instance clear that radius, perimeter and area must be grouped in one block. Similarly, compactness, concavity and number of concave points can be grouped in another block. Proceeding like this, we are able to design some plausible models. One of the best ones in terms of clustering precision is made of B = 5 blocks: the two trivariate blocks from Fig. 4, a block of size 2 (symmetry and fractal dimension), and two remaining blocks of size 1. The results are given in Table 4, together with the basic k-means that we tried as well (and that is used in our initialization of the mvnpEM, see Section 4.1). In experimenting some alternative block designs we somehow proceed like Hennig (2010) who try several (heuristical) merging criterions and reports the best result they obtained. However, in our case, these alternative models (e.g., merging smoothness with the block in Fig. 4, right) always showed results between 92.5 and 93.67% i.e. better than [START_REF] Hennig | Methods for merging gaussian mixture components[END_REF].

We also tried more complex models by adding the other groups of available features, the 10 standard errors (se), or the 10 "worst" variables keeping the same block structure (also supported by the exploration of the scatterplots) but merging together corresponding features. We found that adding the se's where not bringing better results, whereas a r = 20 dimensional model made of the means and worst features with B = 5 blocks as before but of double dimensions (e.g., s 1 = 6 and block 1 made of radius, perimeter and area means and se's) gave a slightly better 94% of correct classification. Finally, we tried the full r = 30 model with B = 5 blocks of sizes up to s 1 = s 2 = 9 with no better results. However, this showed us that running the algorithm on these large dimensional model and n = 569 individuals only took a couple of minute on a common laptop computer.

Discussion

We have proposed in this paper a nonparametric mixture model with conditionally independent multivariate blocks of nonparametric components. The conditional independence assumption has been introduced in several works in the literature, as e.g. in [START_REF] Hunt | Mixture model clustering for mixed data with missing information[END_REF] in the context of parametric mixtures, but was limited so far in nonparametric mixture models to conditionally independent univariate coordinates. The crucial novelty of our model from a statistical modelling perspective is that it allows the dependence to be due not only to the mixture but also to the internal (covariance) structure of the multivariate distributions within each block.

The identifiability of the parameters of our new model regardless the number of components m comes directly using a results from [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF]: actually we have merely pointed out that our model corresponds exactly to one of the theoretical setup developed in [START_REF] Allman | Identifiability of parameters in latent structure models with many observed variables[END_REF].

We then proposed a multivariate EM-like algorithm for this model, called mvnpEM since it extends the npEM algorithm from Benaglia et al. (2009a). We have also introduced and described two strategies to select the bandwidth involved in kernel density estimation step of this algorithm. The performance of this model have been evaluated through numerical simulations with two perspectives. First we experimented it focusing on parameter estimation (including the nonparametric multivariate densities), on two synthetic models: one allowing for comparison with the original npEM algorithm and results from [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] based on an inversion method (both designed for univariate blocks only); the other showing how our algorithm behaves on Gaussian, non-Gaussian with heavy tails, and non-Gaussian with both heavy tails and severely skewed data. We also showed there that some better estimates can result from the adaptive bandwidth strategy we have introduced, compared to the more immediate fixed bandwidth approach.

Second, we have experimented these new model and algorithm on an actual dataset, from the perspective of model-based unsupervised clustering in dimensions from 10 to 30. We compared our approach with the simple k-means algorithm, but also against a recent parametric but non-Gaussian model-based clustering alternative [START_REF] Hennig | Methods for merging gaussian mixture components[END_REF]. This example allows us to illustrate, from a modelling perspective, the way to choose the conditionally independent blocks from the structure of the data. By simple exploratory analysis of the data, one can recognize dependences between variables not obviously due to any mixture structure and group these variables in blocks. We showed that, for several possible blocks design, a clustering based on the Maximum A Posteriori (MAP) strategy using final posterior matrix produced by our algorithm outperformed the two other approaches. The purpose of this example was also to illustrate the applicability of our algorithm in real-size datasets and actual multi-dimensional models.

Both strategies about bandwidth selection for the kernel density estimation step of our algorithm use diagonal bandwidth matrices whose elements are computed from a fixed or adaptive weighted Silverman's rule. This rule is known to be somehow motivated by estimation of Gaussian-shaped distributions, which is too restrictive. Other strategies for the smoothing parameter, i.e. non diagonal bandwidth matrices, or cross-validation strategies are interesting perspectives for future investigations (see, e.g., [START_REF] Hyndman | Bandwidth Selection for Multivariate Kernel Density Estimation Using MCMC[END_REF] for recent research on multivariate bandwidth selection).

Our algorithm, like the original npEM algorithm for univariate blocks from Benaglia et al. (2009a) has not yet theoretical justification, since it is not proved to maximize any objective function, and since its weighted KDE step is not a genuine M-step. Like its predecessors in recent literature, it however provides numerical evidence of consistency in the sense that the scalar and density estimates "numerically converge" to the true values for MSE or MISE criterion, when we let n increase, for all the models we tried. An ongoing work that is beyond the scope of the present paper is precisely to show some type of convergence, extending the ideas from [START_REF] Levine | Maximum smoothed likelihood for multivariate mixtures[END_REF] introducing a non-linearly smoothed log-likelihood objective function and developping an iterative algorithm with a monotony property as for a genuine EM.

Finally, we reiterate that the mvnpEM algorithm introduced in this work will be publicly available in a future version of the mixtools package [START_REF] Benaglia | mixtools: An R package for analyzing finite mixture models[END_REF] for the R statistical software R Development Core Team (2010).

Figure 1 :

 1 Figure 1: Square roots of MISE for the densities and square roots of MSE for the scalar parameter λ 1 , and other scalar measures that are not parameters in the model (means and covariances), as a function of the proportion of the first component λ 1 , for Model A, n = 500 and S = 300 replications, adaptive bandwidth. The gray line types in the legend are identifying densities and scalar criterions, that are plotted colored by component.

Figure 2 :

 2 Figure 2: Marginal density estimates for Model B, where column l corresponds to the two marginals of the lth bivariate block, l = 1, 2, 3. Each plot shows the true marginals (solid lines), mvnpEM with adaptive bandwidth estimates (dashed lines), Gaussian EM estimates (dotted lines). Estimates are based on a sample of size n = 1000. The final values of the adaptive bandwidths are also given under each plot.

Figure 4 :

 4 Figure4: Pairs plots for selected "mean" features from the WDBC database; s 1 = {1, 3, 4} for block 1 (left), and s 2 = {6, 7, 8} for block 2 (right).

Table 1 :

 1 The effect of correlation ρ on MISE of the estimation of a centered bivariate Gaussian density f with unit variances.

	:

  ).

				block 1, k=1					block 2, k=3				block 3, k=5
		0.35						0.35		component 1			0.35
		0.30						0.30		component 2			0.30
		0.25						0.25						0.25
	Density	0.15 0.20					Density	0.15 0.20					Density	0.15 0.20
		0.10						0.10						0.10
		0.05						0.05						0.05
		0.00						0.00						0.00
		-2		0	2		4	-5		0	5		10	-5	0		5
			adapt bw: 0.261 0.238 adapt bw: 0.261 0.238			adapt bw: 0.308 0.255 adapt bw: 0.308 0.255				adapt bw: 0.366 0.322 adapt bw: 0.366 0.322
				block 1, k=2					block 2, k=4				block 3, k=6
		0.35						0.35						0.35	true density
		0.30						0.30						0.30	mvnpEM adaptive bw Gaussian EM
		0.25						0.25						0.25
	Density	0.15 0.20					Density	0.15 0.20					Density	0.15 0.20
		0.10						0.10						0.10
		0.05						0.05						0.05
		0.00						0.00						0.00
		-2	0	2	4	6	8	-10	-5	0	5	10	15	-5	0	5	10	15	20
			adapt bw: 0.299 0.239 adapt bw: 0.299 0.239			adapt bw: 0.307 0.271 adapt bw: 0.307 0.271				adapt bw: 0.386 0.323 adapt bw: 0.386 0.323

Table 4 :

 4 The % of correct classification of the WDBC data using mvnpEM and the MAP strategy, compared with the k-means clustering strategy and the merging Gaussian method of[START_REF] Hennig | Methods for merging gaussian mixture components[END_REF].

	Method	B (over 357) M (over 212) (%) correctly-classified
	k-means	355	122	83.831
	merging Gaussian	344	178	91.740
	mvnpEM & MAP	350	183	93.673

Acknowledgements We thank the Associate Editor and a Reviewer for pointing us to references Hennig (2010) and Hunt and Jorgensen (2003), and for their valuable comments helping us improving the original manuscript and the simulation and real data sections.


Yael Tauman Kalai

Ilan Komargodski
email: ilan.komargodski@weizmann.ac.il

Compressing Communication in Distributed Protocols

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of rounds, the same communication pattern, the same output distribution, and the same resilience to error. Assuming that the output lies in some universe of size M , in our resulting protocol each message consists of only polylog(M, n, d) many bits, where n is the number of parties and d is the number of rounds. Our transformation works in the full information model, in the presence of either static or adaptive Byzantine faults. In particular, our result implies that for any such poly(n)-round distributed protocol which generates outputs in a universe of size poly(n), long messages are not needed, and messages of length polylog(n) suffice. In other words, in this regime, any distributed task that can be solved in the LOCAL model, can also be solved in the CON GEST model with the same round complexity and security guarantees. As a corollary, we conclude that for any poly(n)-round collective coinflipping protocol, leader election protocol, or selection protocols, messages of length polylog(n) suffice (in the presence of either static or adaptive Byzantine faults).

Introduction

In classical algorithmic design the goal is to design efficient algorithms, where the common complexity measures are time and space. In distributed algorithms, where a set of parties tries to perform a predefined task, there are more parameters of interest, such as round complexity, message complexity, fault-tolerance, and more. These measures have been studied in the literature under two main models: LOCAL and CON GEST [START_REF] Peleg | Distributed Computing: A Locality-sensitive Approach[END_REF]. The LOCAL model is aimed at studying "localized" executions of distributed protocols, and thus, messages of unlimited size are allowed. The CON GEST model is geared towards understanding the effect of congestion in the network, and thus, messages of poly-logarithmic size (in the number of parties) are allowed. 3Most of the work in distributed computing assumes one of the models above and focuses on optimizing resources such as round complexity, message complexity and fault-tolerance. We initiate the study of the following question:

Is there a generic way to transform protocols in the LOCAL model to protocols in the CON GEST model, without negatively affecting the round complexity, fault-tolerance and other resources?

We give a positive answer to this question for protocols in which parties do not have private inputs, without incurring any cost to the round complexity or the resilience to errors. More details follow.

Our model. In this work, our focus is on the synchronous, full information model. Namely, we consider a distributed model in which n parties are trying to perform a predefined task. Each party is equipped with a source of private randomness and a unique ID. We assume the existence of a global counter which synchronizes parties in between rounds, but the parties are asynchronous within each round. The goal is to fulfill the task even in the presence of Byzantine faults. In the full information model no restrictions are made on the computational power of the faulty parties or the information available to them. Namely, the faulty parties may be infinitely powerful, and we do not assume the existence of private channels connecting pairs of honest parties. We model faulty parties by a computationally unbounded adversary who controls a subset of parties and whose aim is to bias the output of the protocol. We assume that the adversary has access to the entire transcript of the protocol, and once a party is corrupted, the adversary gains complete control over the party and can send any messages on its behalf, and the messages can depend on the entire transcript so far. In addition, we allow our adversary to be "rushing", i.e., it can schedule the delivery of the messages within each round. We consider two classes of adversaries: static and adaptive. A static adversary is an adversary that chooses which parties to corrupt ahead of time, before the protocol begins. An adaptive adversary, on the other hand, is allowed to choose which parties to corrupt adaptively in the course of the protocol as a function of the messages seen so far.

The focus of this work, is on protocols in which parties do not have private inputs. Many classical distributed tasks fall in this category, including collective coin-flipping, leader election, selection and more.

A concrete motivation: adaptively-secure coin-flipping. An important distributed task that was extensively studied in the full information model, is that of collective coin-flipping. In this problem, a set of n parties use private randomness and are required to generate a common random bit. The goal of the parties is to jointly output a somewhat uniform bit even in the case that some of the parties are faulty and controlled by a static (resp. adaptive) adversary whose goal is to bias the output of the protocol in some direction.

This problem was first formulated and studied by Ben-Or and Linial [START_REF] Ben-Or | Collective coin flipping, robust voting schemes and minima of banzhaf values[END_REF]. In the case of static adversaries, collective coin-flipping is well studied and almost matching upper and lower bounds are known [START_REF] Feige | Noncryptographic selection protocols[END_REF][START_REF] Russell | Lower bounds for leader election and collective coin-flipping in the perfect information model[END_REF], whereas the case of adaptive adversaries has received much less attention. Ben-Or and Linial [START_REF] Ben-Or | Collective coin flipping, robust voting schemes and minima of banzhaf values[END_REF] showed that the majority protocol (in which each party sends a uniformly random bit and the output of the protocol is the majority of the bits sent) is resilient to Θ( √ n) adaptive corruptions. Furthermore, they conjectured that this protocol is optimal, that is, they conjectured that any coin-flipping protocol is resilient to at most O( √ n) adaptive corruptions. Shortly afterwards, Lichtenstein, Linial and Saks [START_REF] Lichtenstein | Some extremal problems arising form discrete control processes[END_REF] proved the conjecture for protocols in which each party is allowed to send only one bit. Very recently, Goldwasser, Kalai and Park [START_REF] Goldwasser | Adaptively secure coin-flipping, revisited[END_REF] proved a different special-case of the aforementioned conjecture: any symmetric (many-bit) one-round collective coin-flipping protocol 4 is resilient to at most O( √ n) adaptive corruptions. Despite all this effort, proving a general lower bound, or constructing a collective coin-flipping protocol that is resilient to at least ω( √ n) adaptive corruptions, remains an intriguing open problem.

The result of [START_REF] Lichtenstein | Some extremal problems arising form discrete control processes[END_REF] suggests that when seeking for a collective coinflipping protocol that is resilient to at least ω( √ n) adaptive corruptions, to focus on protocols that consist of many communication rounds, or protocols in which parties send long messages. Our main result (Theorem 1) is that long messages are not needed in adaptively secure coin-flipping protocols with poly(n) rounds, and messages of length polylog(n) suffice. This is true more generally for leader election protocols, and for selection protocols where the output comes from a universe of size at most quasi-polynomial in n.

Our Results

Our main result is that "long" messages are not needed for distributed tasks in which parties do not have private inputs. More specifically, we show how to convert any n-party d-round protocol, where parties do not have private inputs, and whose output comes from a universe of size M , into a d-round protocol, with the same communication pattern, the same output distribution, the same security guarantees, and where each message is of length polylog(M, n, d). Note that for many well studied distributed tasks, such as coin-flipping, leader election, and more, the output is from a universe of size at most poly(n), in which case our result says that if we consider poly(n)-round protocols, then messages of length polylog(n) suffice.

Our results in more detail. Formally, we say that a protocol Π, in which parties do not have private inputs, is (t, δ, s)-statically (resp., adaptively) secure if for any adversary A that statically (resp., adaptively) corrupts at most t = t(n) parties, and any subset S of the output universe such that |S| = s, it holds that

Pr [Output of A(Π) ∈ S] -Pr [Output of Π ∈ S] ≤ δ,
where "Output of A(Π)" means the output of the protocol when executed in the presence of the adversary A, "Output of Π" means the output of the protocol when executed honestly, and the probabilities are taken over the internal randomness of the parties. In addition, we say that a protocol Π simulates a protocol Π if the outcomes of the protocols are statistically close (when executed honestly) and their communication patterns are the same.

Our main result is a generic communication compression theorem which, roughly speaking, states that (t, δ, s)-statically (resp., adaptively) secure protocols in the above model do not need "long" messages. Namely, we show that any secure protocol which sends arbitrary long messages can be simulated by a protocol which is almost as secure and sends short messages.

Theorem 1 (Main theorem -informal). Any (t, δ, s)-statically (resp., adaptively) secure d-round protocol that outputs m bits (or more generally, has an output universe of size 2 m ), can be simulated by a d-round (t, δ , s)statically (resp., adaptively) secure protocol, where δ = δ + negl(n), and in which parties send random messages of length at most m•polylog(n, d).

Our results can also be seen as a transformation of protocols (in which parties do not have private inputs) in the LOCAL model to protocols in the CON GEST model, as discussed above. Our main theorem (Theorem 1) implies that any task, whose output consists of at most polylog(n) bits, and in which parties do not have private inputs, that can be solved in the LOCAL model with d ≤ poly(n) rounds, can also be solved in the CON GEST model with d rounds.

Corollary 1. Any n-party (t, δ, s)-statically (resp., adaptively) secure poly(n)-round protocol that outputs polylog(n) bits in the LOCAL model, can be simulated by a (t, δ , s)-statically (resp., adaptively) secure protocol in the CON GEST model, where δ = δ + negl(n).

We emphasize that our results holds for any underlying communication pattern including the broadcast channel or the message-passing model with any underlying communication graph.

Finally, we note that the transformation in Theorem 1 preserves the computational efficiency of the honest parties, but the resulting protocol is non-uniform, even if the protocol we started with is uniform. We elaborate on this in Section 1.3.

Related Work

The resource of communication is central in several fields of computer science. The field of communication complexity is devoted to the study of which problems can be solved with as little communication as possible. We refer to the book of Kushilevitz and Nisan [START_REF] Kushilevitz | Communication complexity[END_REF] for an introduction to the field. In cryptography, minimizing communication has been the focus of several works in several contexts, including private information retrieval [START_REF] Kushilevitz | Replication is NOT needed: SINGLE database, computationally-private information retrieval[END_REF], random access memory machines [START_REF] Naor | Communication preserving protocols for secure function evaluation[END_REF], and more.

Interestingly, in the setting of distributed computing most of the work focuses on optimizing other resources such as round complexity, faulttolerance, and the quality of the outcome. Very few works focus on optimizing the maximal message length being sent during the protocols.

Moreover, most of the work in the literature focuses on static adversaries, and very few papers study distributed protocols with respect to adaptive adversaries. Our results hold in both settings.

Finally, we mention that separations between the LOCAL and CON G-EST models are known for general tasks. For example, for network graphs of diameter D = Ω(log n), computing the minimum spanning tree (MST) in the LOCAL model requires Θ(D) rounds, whereas in the CON GEST model every distributed MST algorithm has round complexity Ω(D + √ n/ log 2 n) [START_REF] Peleg | A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction[END_REF].

Overview of Our Techniques

In this section we provide a high-level overview of our main ideas and techniques. First, we observe that one can assume, without loss of generality, that any protocol in which parties do not have private inputs, can be transformed into a public-coin protocol, in which honest parties' messages consist only of random bits. This fact is a folklore, and for the sake of completeness we include a proof sketch of it in Section 4.

Our main result is a generic transformation that converts any publiccoin protocol, in which parties send arbitrarily long messages, into a protocol in which parties send messages of length m • polylog(n • d), where m is the number of bits the protocol outputs, n is the number of parties participating in the protocol, and d is the number of communication rounds. The resulting protocol simulates the original protocol, has the same round complexity and satisfies the same security guarantees. Next, we elaborate on how this transformation works.

Suppose for simplicity that in our underlying protocol each message sent is of length L = L(n) (and thus the messages come from a universe of size 2 L ), and think of L as being very large. We convert any such protocol into a new protocol where each message consists of only bits, where think of as being significantly smaller than L. This is done by a priori choosing 2 messages within the 2 L -size universe, and restricting the parties to send messages from this restricted universe. Thus, now each message is of length , which is supposedly significantly smaller than L. We note that a similar approach was taken in [START_REF] Newman | Private vs. common random bits in communication complexity[END_REF] in the context of transforming public randomness into private randomness in communication complexity, in [START_REF] Goldreich | On the randomness complexity of property testing[END_REF] to reduce the number of random bits needed for property testers, and most recently in [START_REF] Goldwasser | Adaptively secure coin-flipping, revisited[END_REF] to prove a lower bound for coin-flipping protocols in the setting of strong adaptive adversaries.

A priori, it may seem that such an approach is doomed to fail, since by restricting the honest parties to send messages from a small universe within the large 2 L -size universe, we give the adversary a significant amount of information about future messages (especially in the multiround case). Intuitively, the reason security is not compromised is that there are many possible restrictions, and it suffices to prove that a few (or only one) of these restrictions is secure. In other words, very loosely speaking, since we believe that most of the bits sent by honest parties are not "sensitive", we believe that it is safe to post some information about each message ahead of time.

For the sake of simplicity, in this overview we focus on static adversaries, and to simplify matters even further, we assume the adversary always corrupts the first t parties. This simplified setting already captures the high-level intuition behind our security proof in Section 3.

Let us first consider one-round protocols. Note that for one-round protocols restricting the message space of honest parties does not affect security at all since we consider rushing adversaries, who may choose which messages to send based on the content of the messages sent by all honest parties in that round. Thus, reducing the length of messages is trivial in this case, assuming the set of parties that the adversary corrupts is predetermined. We mention that even in this extremely simplified setting, we need to be linear in m for correctness ("simulation"), i.e., in order to ensure that the output is distributed correctly.

Next, consider a multi-round protocol Π. We denote by H the restricted message space, i.e., H is a subset of the message universe of size 2 , and denote by Π H the protocol Π, where the messages are restricted to the set H. Suppose that for any set H there exists an adversary A H that biases the outcome of Π H , say towards 0. 5 We show that in this case there exists an adversary A in the underlying protocol that biases the outcome towards 0. Loosely speaking, at each step the adversary A will simulate one of the adversaries A H . More specifically, at any point in the underlying protocol, the adversary will randomly choose a set H such that the transcript so far is consistent with a run of protocol Π H with the adversary A H , and will simulate the adversary A H . The main difficulty is to show that with high probability there exists such H (i.e., the remaining set of consistent H's is non-empty). This follows from a counting argument and basic probability analysis.

In our actual construction, we have a distinct set H of size 2 corresponding to each message of the protocol. Thus, if the underlying pro-tocol Π has d rounds, and all the parties send a message in each round, then the resulting (short-message) protocol is associated with d • n sets H 1 , . . . , H d•n each of size 2 , where the message of the j th party in the i th round is restricted to be in the set H i,j . We denote all these sets by a matrix H ∈ {0, 1} L d•n×2 , where the row (i, j) of H corresponds to the set of messages that the j th party can send during the i th round.

Note that there are 2 L•2 •d•n such matrices. Each time an honest party sends a uniformly random message in Π it reduces the set of consistent matrices by approximately a 2 L -factor (with high probability). Any time the adversary A sends a message, it also reduces the set of consistent matrices H, since his message is consistent only with some of the adversaries A H , but again a probabilistic argument can be used to claim that it does not reduce the set of matrices by too much, and hence, with high probability there always exist matrices H that are consistent with the transcript so far.

We briefly mention that the analysis in the case of adaptive corruptions follows the same outline presented above. One complication is that the mere decision of whether to corrupt or not reduces the set of consistent matrices H. Nevertheless, we argue that many consistent matrices remain.

We emphasize that the above is an over-simplification of our ideas, and the actual proof is more complex. We refer to Section 3 for more details.

Preliminaries

In this section we present the notation and basic definitions that are used in this work. For an integer n ∈ N we denote by [n] the set {1, . . . , n}. For a distribution X we denote by x ← X the process of sampling a value x from the distribution X. Similarly, for a set X we denote by x ← X the process of sampling a value x from the uniform distribution over X. Unless explicitly stated, we assume that the underlying probability distribution in our equations is the uniform distribution over the appropriate set. We let U L denote the uniform distribution over {0, 1} L . We use log x to denote a logarithm in base 2.

A function negl : N → R is said to be negligible if for every constant c > 0 there exists an integer N c such that negl(n) < n -c for all n > N c .

The statistical distance between two random variables X and Y over a finite domain Ω is defined as

SD(X, Y ) 1 2 ω∈Ω |Pr[X = ω] -Pr[Y = ω]| . ( 1
)
The Model

The communication model and distributed tasks. We consider the synchronous model where a set of n parties P 1 , . . . , P n run protocols. Each protocol consists of rounds in which parties send messages. We assume the existence of a global counter which synchronizes parties in between rounds (but they are asynchronous within a round). The focus of this work is on tasks where parties do not have any private inputs. Examples of such tasks are coin-flipping protocols, leader election protocols, Byzantine agreement protocols, etc.

Throughout this paper, we restrict ourselves to public-coin protocols.

Definition 1 (Public-coin protocols).

A protocol is public-coin if all honest parties' messages consist only of uniform random bits.

Jumping ahead, we consider adversaries in the full information model. In Section 4 we argue that the restriction to public-coin protocols is without loss of generality since in the full information model any protocol (in which parties do not have private inputs) can be converted into a public-coin one, without increasing the round complexity and without degrading security (though this transformation may significantly increase the communication complexity).

The adversarial model. We consider the full information model where it is assumed the adversary is all powerful, and may see the entire transcript of the protocol. The most common adversarial model considered in the literature is the Byzantine model, where a bound t = t(n) ≤ n is specified, and the adversary is allowed to corrupt up to t parties. The adversary can see the entire transcript, has full control over all the corrupted parties, and can send any messages on their behalf. Moreover, the adversary has control over the order of the messages sent within each round of the protocol. 6 We focus on the Byzantine model throughout this work. Within this model, two types of adversaries were considered in the literature: static adversaries, who need to specify the parties they corrupt before the protocol begins, and adaptive adversaries, who can corrupt the parties adaptively based on the transcript so far. Our results hold for both types of adversaries. Throughout this work, we focus on the adaptive setting, since the proof is more complicated in this setting. In Subsection 3.1 we mention how to modify (and simplify) the proof for the static setting.

Correctness and security. For any protocol Π and any adversary A, we denote by

out(A Π | r 1 , . . . , r n )
the output of the protocol Π when executed with the adversary A, and where each honest party P i uses randomness r i .

Let Π be a protocol whose output is a string in {0, 1} m for some m ∈ N. Loosely speaking, we say that an adversary is "successful" if he manages to bias the output of the protocol to his advantage. More specifically, we say that an adversary is "successful" if he chooses a predetermined subset M ⊆ {0, 1} m of some size s, and succeeds in biasing the outcome towards the set M . To this end, for any set size s, we define

succ s (A Π ) def = max M ⊆{0,1} m s.t. |M |=s succ M (A Π ) def = max M ⊆{0,1} m s.t. |M |=s Pr r 1 ,...,rn [out(A Π | r 1 , . . . , r n ) ∈ M ] - Pr r 1 ,...,rn [out Π (r 1 , . . . , r n ) ∈ M ] ,
where out Π (r 1 , . . . , r n ) denotes the outcome of the protocol Π if all the parties are honest, and use randomness r 1 , . . . , r n .

Intuitively, the reason we parameterize over the set size s is that we may hope for different values of succ M (A Π ) for sets M of different sizes, since for a large set M it is often the case that Pr r 1 ,...,rn [out Π (r 1 , . . . , r n ) ∈ M ] is large, and hence succ M (A Π ) is inevitably small, whereas for small sets M the value succ M (A Π ) may be large.

For example, for coin-flipping protocols (where m = 1 and the outcome is a uniformly random bit in the case that all parties are honest), often an adversary is considered successful if it biases the outcome to his preferred bit with probability close to 1, and hence an adversary is consid-

ered successful if succ M (A Π ) ≥ 1 2 -o(1)
for either M = {0} or M = {1}, whereas for general selection protocols (where m is a parameter) one often considers subsets M ⊆ {0, 1} m of size γ • 2 m for some constant γ > 0, and an adversary is considered successful if there exists a constant δ > 0 such that succ M (A Π ) ≥ δ.

Definition 2 (Security). Fix any constant δ > 0, any t = t(n) ≤ n, and any n-party protocol Π whose output is an element in {0, 1} m . Fix any s = s(m). We say that Π is (t, δ, s)-adaptively secure if for any adversary A that adaptively corrupts up to t = t(n) parties, it holds that

succ s (A Π ) ≤ δ.
We note that this definition generalizes the standard security definition for coin-flipping protocols and selection protocols. We emphasize that our results are quite robust to the specific security definition that we consider, and we could have used alternative definitions as well. Intuitively, the reason is that we show how to transform any d-round protocol Π into another d-round protocol with short messages, that simulates Π (see Definition 3 below), where this transformation is independent of the security definition. Then, in order to prove that the resulting protocol is as secure as the original protocol Π, we show that if there exists an adversary for the short protocol that manages to break security according to some definition, then there exists an adversary for Π that "simulates" the adversary of the short protocol and breaches security in the same way. (See Section 1.3 for more details, and Section 3 for the formal argument).

Finally, we mention that an analogous definition to Definition 2 can be given for static adversaries. Our results hold for the static definition as well.

Definition 3 (Simulation). Let Π be an n-party protocol with outputs in {0, 1} m . We say that an n-party protocol Π simulates Π if

SD (out Π , out Π ) = negl(n),
where out Π is a random variable that corresponds to the output of protocol Π assuming all parties are honest, and out Π is a random variable that corresponds to the output of protocol Π assuming all parties are honest.

Compressing Communication in Distributed Protocols

In this section we show how to transform any n-party d-round t-adaptively secure public-coin protocol, that outputs messages of length m and sends messages of length L, into an n-party d-round t-adaptively secure publiccoin protocol in which every party sends messages of length = m • polylog(n, d).

Throughout this section, we fix µ * to be the negligible function defined by

µ * = µ * (n, d) = √ ε + 1 -(1 -ε) dn • 2dn, (2)
and where ε = 2 -log 2 (dn) . Proof. Fix any m = m(n), d = d(n), L = L(n), and any n-party d-round public-coin protocol Π that outputs messages in {0, 1} m and in which all parties send messages of length L = L(n). Fix any constant δ > 0, any t = t(n) < n, and any s = s(m) such that Π is (t, δ, s)-adaptively secure. We start by describing the construction of the (short message) protocol.

Let N = 2 = 2 m•log 4 (n•d) . (3)
H(i, j, r) H((i -1)n + j, r).
As a convention, we denote by R a message from {0, 1} L and by r and a message from {0, 1} .

From now on, we assume for the sake of simplicity of notation, that in protocol Π, in each round, all the parties send a message. Recall that we also assume for the sake of simplicity (and without loss of generality) that Π is a public-coin protocol (see Definition 1). For any H ∈ H we define a protocol Π H that simulates the execution of the protocol Π, as follows.

The Protocol Π H . In the protocol Π H , for every i ∈ [d] and j ∈ [n], in the i th round, party P j sends a random string r i,j ← {0, 1} . We denote the resulting transcript in round i by We abuse notation, and define for every round i ∈

Trans H,i = (r i,1 , . . . , r i,n ) ∈ {0, 1}
[d], H(Trans H,i ) = (H(i, 1, r i,1 ), . . . , H(i, n, r i,n )).
Similarly, we define H(Trans H ) = (H(Trans H,1 ) . . . , H(Trans H,d )).

The outcome of protocol Π H with transcript Trans H is defined to be the outcome of protocol Π with transcript H(Trans H ).

It is easy to see that the round complexity of Π H (for every H ∈ H) is the same as that of Π. Moreover, we note that with some complication in notation we could have also preserved the exact communication pattern (instead of assuming that in each round all parties send a message).

In order to prove Theorem 1 it suffices to prove the following two lemmas.

Lemma 1. There exists a subset H 0 ⊆ H of size |H| 2 , such that for every matrix H ∈ H 0 it holds that Π H is (t, δ , s)-adaptively secure for δ = δ + µ * , where µ * is the negligible function defined in Equation (2). Indeed, given Lemmas 1 and 2, we obtain that there exists an H ∈ H such that Π H is (t, δ , s)-adaptively secure and it simulates Π.

The proofs of Lemmas 1 and 2 can be found in the full version [START_REF] Kalai | Compressing communication in distributed protocols[END_REF].

Static Adversaries

We note that Theorem 2 holds also for static adversary. For completeness, we restate the theorem for static adversaries. The proof of Theorem 3 is almost identical to the proof of Theorem 2. An outline is given in the full version [START_REF] Kalai | Compressing communication in distributed protocols[END_REF].

Public-Coin Protocols

In this section we show how to convert any distributed protocol in which parties do not have private inputs into a public-coin protocol.

Theorem 4. Every protocol Π in which parties do not have private inputs can be transformed into a protocol Π which simulates Π and such that the messages sent in Π are uniformly random. Moreover, the protocol Π preserves the security of Π and its round complexity.

The proof sketch of this theorem can be found in the full version [START_REF] Kalai | Compressing communication in distributed protocols[END_REF].

Theorem 2 .

 2 Fix any m = m(n), d = d(n), L = L(n), and any nparty d-round public-coin protocol Π that outputs messages in {0, 1} m and in which all parties send messages of length L = L(n). Then, for any constant δ > 0, any t = t(n) < n, and any s = s(m), if Π is (t, δ, s)-adaptively secure then there exists an n-party d-round (t, δ , s)adaptively secure public-coin protocol, that simulates Π, where all parties send messages of length = m • log 4 (n • d), and where δ ≤ δ + µ * (and µ * = µ * (n, d) is the negligible function defined in Equation (2)).

Let H =

 = {H : [d • n] × {0, 1} → {0, 1} L } be the set all possible [d • n] × {0, 1} ≡ [d • n] × [N ] matrices, whose elements are from {0, 1} L . Note that |H| = 2 d•n•N •L . We often interpret H : [d • n] × {0, 1} → {0, 1} L as a function H : [d] × [n] × {0, 1} → {0, 1} L ,or as a matrix where each row is described by a pair from [d] × [n]. We abuse notation and denote by

  entire transcript by Trans H = (Trans H,1 . . . , Trans H,d ).

Lemma 2 .

 2 There exists a negligible function µ = µ(n, d) such that,Pr H←H [SD(out Π H , out Π ) ≤ µ] ≥2 3 .

Theorem 3 .

 3 Fix any m = m(n), d = d(n), L = L(n), and any nparty d-round public-coin protocol Π that outputs messages in {0, 1} m and in which all parties send messages of length L = L(n). Then, for any constant δ > 0, any t = t(n) < n, and any s = s(m), if Π is (t, δ, s)statically secure then there exists an n-party d-round (t, δ , s)-statically secure public-coin protocol that simulates Π, where all parties send messages of length = m • log4 (n • d), and where δ ≤ δ + µ * (where µ * = µ * (n, d) is the negligible function defined in Equation (2)).

Part of this work done while an intern at MSR New England. Supported in part by a grant from the I-CORE Program of the Planning and Budgeting Committee, the Israel Science Foundation, BSF and the Israeli Ministry of Science and Technology.

We note that often the term CON GEST is a short-hand writing for CON GEST (B), where B is a bandwidth constraint. In many cases, the convention is to set B to be bounded by O(log n), where n is the number of parties. Here, we take a more liberal interpretation, which allows for messages of size bounded by polylog(n) (see e.g.,[START_REF] Sarma | Fast distributed pagerank computation[END_REF]).

A symmetric protocol Π is one that is oblivious to the order of its inputs: namely, for any permutation π : [n] → [n] of the parties, it holds that Π(r1, . . . , rn) = Π(r π(1) , . . . , r π(n) ).

Of course, it may be that for different sets H, the adversary A H biases the outcome to a different value. For simplicity we assume here that all the adversaries bias the outcome towards a fixed message, which we denote by 0.

Such an adversary is often referred to as "rushing".

Acknowledgments We thank Nancy Lynch, Merav Parter and David Peleg for helpful remarks and pointers. The second author thanks his advisor Moni Naor for his continuous support.