Ariane Marandon

Tabea Rebafka

Etienne Roquain

Nataliya Sokolovska

False

False clustering rate control in mixture models

published or not. The documents may come

Introduction

Background

Clustering is a standard statistical task that aims at grouping together individuals with similar features. However, it is common that data sets include ambiguous individuals that are inherently difficult to classify, which makes the clustering result potentially unreliable. To illustrate this point, consider a Gaussian mixture model with overlapping mixture components. Then it is difficult, or even impossible, to assign the correct cluster label to data points that fall in the overlap of those clusters, see Figure 1. Hence, when the overlap is large (Figure 1 panel (b)), the misclassification rate of a standard clustering method is inevitably elevated.

This issue is critical in applications where misclassifications come with a high cost for the user and should be avoided. This is for example the case for medical diagnosis, where an error can have severe consequences on the individual's health. When there is too much uncertainty, a solution is to avoid classification for such individuals, and to adopt a wiser "abstention decision", that leaves the door open for further medical exams.

In a supervised setting, classification with a reject (or abstention) option is a long-standing statistical paradigm, that can be traced back to [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF], with more recent works including [START_REF] Herbei | Classification with reject option[END_REF]; [START_REF] Bartlett | Classification with a reject option using a hinge loss[END_REF]; [START_REF] Wegkamp | Support vector machines with a reject option[END_REF], among others. In this line of research, rejection is accounted for by adding a term to the risk that penalizes any rejection (i.e., non classification). However, this approach does not provide a prescribed control of the classification error among the classified items (those that are not rejected).

More confidence in the labelling can be brought via conformal prediction, [START_REF] Vovk | Machine-learning applications of algorithmic randomness[END_REF][START_REF] Vovk | Algorithmic learning in a random world[END_REF], see also [START_REF] Nikolas | Uncertainty sets for image classifiers using conformal prediction[END_REF] for a review. This generic technique can be applied to supervised classification for producing confidence sets for the label vector. However, such inference does not incorporate the abstention rule. Very recently, [START_REF] Denis | Consistency of plug-in confidence sets for classification in semi-supervised learning[END_REF] proposed a conformal approach with a rejection option. The method consists in minimizing the probability of misclassification conditionally on the fact that it has been classified, while controlling the probability of being classified. This brings a safety guarantee on the label assigned to the classified items.

Aim and approach

The goal of the present work is to propose a labelling guarantee on the classified items in the vein of [START_REF] Denis | Consistency of plug-in confidence sets for classification in semi-supervised learning[END_REF], but in the more challenging unsupervised setting, where no training set is available and data are assumed to be generated from a finite mixture model. This is achieved by the possibility to refuse to cluster ambiguous individuals and by using the false clustering rate (FCR), which is defined as the average proportion of misclassifications among the classified objects. Our procedures are devised to keep the FCR below some nominal level α, while classifying a maximum number of items.

It is important to understand the role of the nominal level α in our approach. It is chosen by the user and depends on their acceptance or tolerance for misclassified objects. Since the FCR is the misclassification risk that is allowed on the classified objects, the final interpretation of FCR control at level α is clear: if for instance α is chosen to be 5% and 100 items are finally chosen to be classified by the method, then the number of misclassified items is expected to be at most 5. This high interpretability is similar to the one of the false discovery rate (FDR) in multiple testing, which has known a great success in applications since its introduction by [START_REF] Benjamini | Controlling the false discovery rate: a practical and powerful approach to multiple testing[END_REF]. This is a clear advantage of our approach for practical use compared to the methods with a rejection option that are based on a penalized risk.

In our framework, a procedure is composed of two intertwined decisions:

• a selection rule deciding which of the items are labelled;

• a clustering method inferring the labels for the selected items.

Both decisions heavily rely on the appropriate quantification of the uncertainty of the cluster labels. As such, our approach is model-based, and can be viewed as a method that thresholds the posterior probabilities of the cluster labels with a data-driven choice of the threshold. The performance of the method will depend on the quality of the estimates of these posterior probabilities in the mixture model. The adaptive character of our method is illustrated in Figure 1: when the clusters are well separated (panel (a)), the new procedure only discards few items and provides a clustering close to the correct one. However, when the clusters are overlapping (panel (b)), to avoid a high misclassification error, the procedure discards most of the items and only provides few labels, for which the uncertainty is low. In both cases, the proportion of misclassified items among the selected ones is small and in particular close to the target level α (here 10%). Hence, by adapting the amount of labeled or discarded items, our method always delivers a reliable clustering result, inspite of the varying intrinsic difficulty of the clustering task.

Presentation of the results

Let us now describe in more details the main contributions of the paper.

• We introduce three new data-driven procedures that perform simultaneously selection and clustering: the plug-in procedure (illustrated in Figure 1) and two bootstrap procedures (parametric and non-parametric), see Section 3.2. In each panel, the left part displays the true clustering, while the right part illustrates the new procedure (plug-in procedure at level α = 10%), that does not cluster all items. The points not classified are depicted by grey crosses. Points circled in red correspond to erroneous labels.

• We prove that the plug-in procedure controls the FCR at the desired level α, up to a reminder term which becomes small when the sample size grows. In addition, this procedure is shown to satisfy the following optimality property: any other procedure that provides an FCR control necessarily classifies equal or less items than the plug-in procedure, up to a small remainder term. All results are non-asymptotic in the sample size (Theorem 6), and it is shown that the reminder terms tend to zero when the sample size tends to infinity (Corollary 7). We also put forward specific convergence rates depending on the parameter estimation accuracy (Corollary 8).

• Numerical experiments establish that the bootstrap procedures improve the plug-in procedure in terms of non-asymptotic FCR control, and thus are more reliable for practical use, where the sample size may be moderate, see Section 5.1.

• Our analysis also shows that the fixed threshold procedure that only labels items with a maximum posterior probability larger than 1 -α is generally suboptimal for an FCR control at level α, see Section 5.1. To this extent, our procedures can be seen as more refined algorithms that classify more individuals while maintaining the FCR control.

• The practical impact of our approach is demonstrated on a real data set, see Section 5.2.

Relation to previous work

Other clustering guarantees in unsupervised learning While we provide a specific FCR control guarantee on the clustering, other criteria, not particularly linked to a rejection option, have been previously proposed in an unsupervised setting. Considering the cluster labels as fixed parameters, minimizing the misclassification risk has been proposed in [START_REF] Lei | Consistency of spectral clustering in stochastic block models[END_REF]; [START_REF] Lu | Statistical and computational guarantees of lloyd's algorithm and its variants[END_REF], among others. When clusters are rather considered as latent variables generated concomitantly with the observations (as we do here), other criteria have been investigated: the probability to make a different decision than the Bayes rule [START_REF] Azizyan | Minimax theory for high-dimensional gaussian mixtures with sparse mean separation[END_REF], the probability of exact recovery [START_REF] Arora | Learning mixtures of separated nonspherical Gaussians[END_REF][START_REF] Bickel | A nonparametric view of network models and newman-girvan and other modularities[END_REF], or the fact that all clusters are mostly homogeneous with high probability [START_REF] Najafi | Reliable clustering of Bernoulli mixture models[END_REF]. All these works provide a guarantee only if the setting is favorable enough. By contrast, providing a rejection option is the key to obtain a guarantee in any setting (in the worst situation, the procedure will not classify any item).

Comparison to [START_REF] Denis | Consistency of plug-in confidence sets for classification in semi-supervised learning[END_REF] and [START_REF] Mary-Huard | Error rate control for classification rules in multiclass mixture models[END_REF] We describe here two recent studies that are related to ours, because they also use a FCR-like criterion. The first one is the work of [START_REF] Denis | Consistency of plug-in confidence sets for classification in semi-supervised learning[END_REF], which also relies on a thresholding of the (estimated) posterior probabilities. However, the control is different, because it does not provide an FCR control, but rather a type-II error control concerning the probability of classifying an item. Also, the proposed procedure therein uses an additional labeled sample (semi-supervised setting), which is forbidden in our case.

The work of [START_REF] Mary-Huard | Error rate control for classification rules in multiclass mixture models[END_REF] also proposes a control of the FCR. However, the analysis therein is solely based on the case where the model parameters are known (thus corresponding to the oracle case developed in Section 3.1 here). Compared to [START_REF] Mary-Huard | Error rate control for classification rules in multiclass mixture models[END_REF], the present work provides number of new contributions, which are all given in Section 1.3. Let us also emphasize that we handle the label switching problem in the FCR, which seems to be overlooked in [START_REF] Mary-Huard | Error rate control for classification rules in multiclass mixture models[END_REF].

Relation to false discovery rate The FCR is closely related to the false discovery rate (FDR), defined as the average proportion of errors among the discoveries, in a multiple testing context. In fact, we can roughly view the problem of designing an abstention rule as testing, for each item i, whether the clustering rule correctly classifies item i or not. With this analogy, our selection rule is based on quantities similar to the local FDR values [START_REF] Efron | Empirical bayes analysis of a microarray experiment[END_REF], a key quantity to build optimal FDR controlling procedure in multiple testing mixture models, see, e.g., [START_REF] Storey | The positive false discovery rate: a bayesian interpretation and the q-value[END_REF]; [START_REF] Sun | Oracle and adaptive compound decision rules for false discovery rate control[END_REF]; [START_REF] Cai | Covariate-assisted ranking and screening for largescale two-sample inference[END_REF]; [START_REF] Rebafka | Graph inference with clustering and false discovery rate control[END_REF]. In particular, our final selection procedure shares similarities with the procedure introduced in [START_REF] Sun | Oracle and adaptive compound decision rules for false discovery rate control[END_REF], also named cumulative -value procedure [START_REF] Abraham | Empirical bayes cumulative -value multiple testing procedure for sparse sequences[END_REF]. In addition, our theoretical analysis is related to the work of [START_REF] Rebafka | Graph inference with clustering and false discovery rate control[END_REF], although the nature of the algorithm developed therein is different from here: they use the q-value procedure of [START_REF] Storey | The positive false discovery rate: a bayesian interpretation and the q-value[END_REF], while our method rather relies on the cumulative -value procedure.

Organization of the paper

The paper is organized as follows: Section 2 introduces the model and relevant notation, namely the FCR criterion, with a particular care of the label switching problem. Section 3 presents the methods: the oracle, plug-in and the bootstrap approaches. Our main theoretical results are provided in Section 4, after introducing the appropriate assumptions. Section 5 presents numerical experiments and an application to a real data set, while a conclusion is given in Section 6. Proofs of the results and other technical details are deferred to appendices.

Setting

This section presents the notation, model, procedures and criteria that will be used throughout the manuscript.

Model

Let X = (X 1 , . . . , X n ) be an observed random sample of size n. Each X i is an i.i.d. copy of a d-dimensional real random vector, which is assumed to follow the standard mixture model:

Z ∼ M(π 1 , . . . , π Q ), X|Z = q ∼ F φq , 1 ≤ q ≤ Q,
where M(π 1 , . . . , π Q ) denotes the multinomial distribution of parameter π (equivalently, π q = P(Z = q) for each q). The model parameters are given by • the probability distribution π on {1, . . . , Q} that is assumed to satisfy π q > 0 for all q.

Hence, π q corresponds to the probability of being in class q;

• the parameter φ = (φ 1 , . . . , φ Q ) ∈ U Q , where {F u , u ∈ U} is a collection of distributions on R d . We moreover assume that each distribution F u has a density with respect to the Lebesgue measure on R d , that we denote by f u . Also, we assume that the φ q 's are all distinct.

The parameter Q, coding for the number of classes, is assumed to be known and fixed throughout the manuscript (see Section 6 for a discussion). The overall parameter is thus θ = (π, φ), the parameter set is denoted by Θ, and the distribution of (Z, X) is denoted by P θ . The distribution family {P θ , θ ∈ Θ} is the considered statistical model. We also assume that Θ is an open subset of R K for some K ≥ 1 with the corresponding topology.

In this mixture model, the latent vector Z = (Z 1 , . . . , Z n ) encodes a partition of the n observations into Q classes given by {1 ≤ i ≤ n : Z i = q}, 1 ≤ q ≤ Q. We refer to this model-based, random partition as the true latent clustering in the sequel.

In what follows, the "true" parameter that generates (Z, X) is assumed to be fixed and is denoted by θ * ∈ Θ.

Procedure and criteria

Our approach starts with a given clustering rule, that aims at recovering the true latent clustering. In general, a clustering rule is defined as a (measurable) function of the observation X returning a vector label Z = ( Ẑi ) 1≤i≤n ∈ {1, . . . , Q} n for which the label q is given to individual i if and only if Ẑi = q.

The classification error of Ẑ is thus given by ε(

Z, Z) = n i=1 1{Z i = Ẑi }. Obviously,
since switching the labels in Z does not change the true latent partition, we should allow for switching the labels when making the decision Z from the data. The clustering risk of Z is thus defined by

R( Z) = E θ * min σ∈[Q] E θ * n -1 ε(σ( Z), Z) | X , (1)
where [Q] denotes the set of all permutations on {1, . . . , Q}. Above, the minimum over σ is added to handle the aforementioned label switching problem.

Remark 1. Note that the position of the minimum w.r.t. σ matters in the risk (1): σ is allowed to depend on X but not on Z. Hence, this risk has to be understood as being computed up to a data dependent label switching. This definition coincides with the usual definition of misclassification risk in the situation where the true clustering is deterministic, see [START_REF] Lei | Consistency of spectral clustering in stochastic block models[END_REF]; [START_REF] Lu | Statistical and computational guarantees of lloyd's algorithm and its variants[END_REF]. Hence, it can be seen as a natural extension of the latter to a mixture model where the true clustering is random.

Classically, we aim to find a clustering rule Z such that the clustering risk is "small". However, as mentioned above, whether this is possible or not depends on the intrinsic difficulty of the clustering problem and thus of the true parameter θ * (see Figure 1). Therefore, the idea is to provide a selection rule, that is, a (measurable) function of the observation X returning a subset S ⊂ {1, . . . , n}, such that the clustering risk with restriction to S is small. Throughout the paper, a procedure refers to a couple C = ( Z, S), where Z is a clustering rule and S is a selection rule.

Definition 1 (False clustering rate). The false clustering rate (FCR) of a procedure C = ( Z, S) is given by

FCR θ * (C) = E θ * min σ∈[Q] E θ * ε S (σ( Z), Z) max(|S|, 1) X , (2)
where ε S ( Z, Z) = i∈S 1{Z i = Ẑi } denotes the misclassification error restricted to the subset S.

In this work, the aim is to find a procedure C such that the false clustering rate is controlled at a nominal level α, that is, FCR θ * (C) ≤ α. Obviously, choosing S empty implies ε S (σ( Z), Z) = 0 a.s. for any permutation σ and thus satisfies this control. Hence, while maintaining the control FCR θ * (C) ≤ α, we aim to classify as much individuals as possible, that is, to make E θ * |S| as large as possible.

The FCR (2) involves an expectation of a ratio, which is more difficult to handle that a ratio of expectations. Hence, the following simpler alternative criterion will also be useful in our analysis.

Definition 2 (Marginal false clustering rate). The marginal false clustering rate (mFCR) of a procedure C = ( Z, S) is given by

mFCR θ * (C) = E θ * min σ∈[Q] E θ * ε S (σ( Z), Z) X E θ * (|S|) , (3)
with the convention 0/0 = 0.

Note that the mFCR is similar to the criterion introduced in Denis and Hebiri (2020) in the supervised setting.

Notation

We will extensively use the following notation: for all q ∈ {1, . . . , Q} and θ = (π, φ) ∈ Θ, we let

q (X, θ) = P θ (Z = q|X) = π q f φq (X) Q =1 π f φ (X) ; (4) T (X, θ) = 1 -max q∈{1,...,Q} q (X, θ) ∈ [0, 1 -1/Q]. (5)
Hence, q (X, θ) is the posterior probability of being in class q given the measurement X under the distribution P θ . The quantity T (X, θ) is a measure of the risk when classifying X: it is close to 0 when there exists a class q such that q (X, θ) is close to 1, that is, when X can be classified with a large confidence.

Methods

In this section, we introduce new methods for controlling the FCR. We start by identifying an oracle method, in the sense that it uses the true value of the parameter θ * . Substituting in that oracle the unknown parameter θ * by an estimator provides our first method, called the plug-in procedure. We then define a refined version of the plug-in procedure, that accounts for the variability of the estimator and is based on a bootstrap approach.

Oracle procedures

MAP clustering Here, we proceed as if an oracle had given us the true value of θ * and we introduce an oracle procedure C * = ( Z * , S * ) based on this value. As the following lemma shows, the best clustering rule is well-known and given by the Bayes clustering Z * = ( Z * 1 , . . . , Z * n ) which can be written as

Z * i ∈ argmax q∈{1,...,Q} q (X i , θ * ), i ∈ {1, . . . , n}, (6)
where q (•) is the posterior probability given by (4).

Lemma 1. We have

min Z R( Z) = R( Z * ) = n -1 n i=1 E θ * (T * i ),
for the Bayes clustering Z * defined by (6) and for

T * i = T (X i , θ * ) = P θ * (Z i = Ẑ * i |X i ), i ∈ {1, . . . , n}, (7)
where T (•) is given by (5).

In words, Lemma 1 establishes that the oracle statistics T * i corresponds to the posterior misclassification probabilities of the Bayes clustering. To decrease the overall misclassification risk, it is natural to avoid classification for points with a high value of the test statistic T * i .

Thresholding selection rules In this section, we introduce the selection rule, which assesses which items have to be classified. From the above paragraph, it is natural to consider a thresholding based selection rule S = {i ∈ {1, . . . , n} : T * i ≤ t}, for some threshold t to be suitably chosen. The following result gives insights for choosing such a threshold t.

Lemma 2. For a procedure C = ( Z * , S) with Bayes clustering and an arbitrary selection S,

FCR θ * (C) = E θ * i∈S T * i max(|S|, 1) . ( 8
)
As a consequence, a first way to build an (oracle) selection is to set

S = {i ∈ {1, . . . , n} : T * i ≤ α}.
Since an average of numbers smaller than α is also smaller than α, the corresponding procedure controls the FCR at level α. This procedure is referred to as the procedure with fixed threshold in the sequel. It corresponds to the following naive approach: to get a clustering with a risk of α, we only keep the items that are in their corresponding class with a posterior probability at least 1 -α. By contrast, the selection rule considered here is rather

S = {i ∈ {1, . . . , n} : T * i ≤ t(α)},
for a threshold t(α) ≥ α maximizing |S| under the constraint i∈S T * i ≤ α|S|. It uniformly improves the procedure with fixed threshold and will in general lead to a (much) broader selection. This gives rise to the oracle procedure, that can be easily implemented by ordering the T * i 's, see Algorithm 1.

Algorithm 1 Oracle procedure Input: Parameter θ * , sample (X 1 , . . . , X n ), level α.

1. Compute the posterior probabilities

P θ * (Z i = q|X i ), 1 ≤ i ≤ n, 1 ≤ q ≤ Q; 2. Compute the Bayes clustering Z * i , 1 ≤ i ≤ n,
given by ( 6); 3. Compute the probabilities T * i , 1 ≤ i ≤ n, given by ( 7); 4. Order these probabilities in increasing order T *

(1) ≤ • • • ≤ T * (n) ; 5. Choose k * the maximum of k ∈ {0, . . . , n} such that max(k, 1) -1 k j=1 T * (j) (X) ≤ α; 6. Select S *
α , the index corresponding to the k * smallest elements among the

T * i 's. Output: Oracle procedure C α = ( Z * , S * α ).
Algorithm 2 Plug-in procedure Input: Sample (X 1 , . . . , X n ), level α.

1. Compute an estimator θ of θ; 2. Run the oracle procedure given in Algorithm 1 with θ in place of θ * . Output: Plug-in procedure

C PI α = ( Z PI , S PI α ).

Empirical procedures

Plug-in procedure The oracle procedure cannot be used in practice since θ * is generally unknown. A natural idea is then to approach θ * by an estimator θ and then to plug this estimate into the oracle procedure. The resulting procedure, denoted

C PI = ( Z PI , S PI α ), is called the plug-in procedure and is implemented in Algorithm 2.
Obviously, the quality of the plug-in procedure relies on the chosen estimator θ. In a mixture model, the maximum likelihood estimator (MLE) is not computable in general. A standard way to approach the MLE is to use an Expectation Maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF]. The property of the EM estimator θ in the current framework has been extensively studied both empirically and theoretically in the literature, see [START_REF] Balakrishnan | Statistical guarantees for the EM algorithm: From population to sample-based analysis[END_REF] and references therein.

In Section 4, we establish that the plug-in procedure has suitable properties: when n tends to infinity, provided that the chosen estimator θ behaves well and under mild regularity assumptions on the model, the FCR of the plug-in procedure is close to the level α while it is nearly optimal in terms of average selection number.

Bootstrap procedure Despite the favorable theoretical properties shown in Section 4, the plug-in procedure achieves an FCR that can exceed α in some situations, as we will see in our numerical experiments (Section 5). This is in particular the case when the estimator θ is too rough. Indeed, the uncertainty of θ near θ * is ignored by the plug-in procedure.

To take into account this effect, we propose to use a bootstrap approach. It is based on the following result.

Lemma 3. For a given level α ∈ (0, 1), the FCR of the plug-in procedure C PI α is given by

FCR( C PI α ) = E X∼P θ *   min σ∈[Q] n i=1 {1 -σ( ẐPI i (X)) (X i , θ * )}1{i ∈ ŜPI α (X)} max(| ŜPI α (X)|, 1)   . (9)
The general idea is as follows: since FCR( C PI α ) can exceed α, we choose α as large as possible such that FCR α ≤ α, for which FCR α is a bootstrap approximation of FCR(

C PI α ) based on (9). Algorithm 3 Bootstrap procedure Input: Sample (X 1 , . . . , X n ), level α, number B of bootstrap runs. 1. Choose a grid of increasing level (α(k)) 1≤k≤K ; 2. Compute FCR B α(k) , 1 ≤ k ≤ K, according to (10); 3. Choose k according to (11). Output: Bootstrap procedure C boot α = C PI α( k) .
The bootstrap approximation reads as follows: in the RHS of ( 9), we replace the true parameter θ * by θ and X ∼ P θ * by X ∼ P , where P is an empirical substitute of P θ * . This empirical distribution P is P θ for the parametric bootstrap and the uniform distribution over the X i 's for the non-parametric bootstrap. This yields the bootstrap approximation of FCR( C PI α ) given by

FCR α = E X ∼ P   min σ∈[Q] n i=1 {1 -σ( ẐPI i (X )) (X i , θ(X))}1{i ∈ ŜPI α (X )} max(| ŜPI α (X )|, 1) X   .
Classically, the latter is itself approximated by a Monte Carlo scheme:

FCR B α = 1 B B b=1 min σ∈[Q] n i=1 {1 -σ( ẐPI i (X b )) (X b i , θ(X))}1{i ∈ ŜPI α (X b )} max(| ŜPI α (X b )|, 1) , (10)
with X 1 , . . . , X B i.i.d. ∼ P corresponding to the bootstrap samples of X. Let (α(k)) 1≤k≤K ∈ (0, 1) K a grid of increasing nominal levels (possibly in restriction to values slightly below the targeted level α). Then, the bootstrap procedure at level α is defined as

C boot α = C PI α( k) where k = max k ∈ {1, . . . , K} : FCR B α(k) ≤ α . ( 11
)
This procedure is implemented in Algorithm 3.

Remark 2 (Parametric versus non parametric bootstrap). The usual difference between parametric and non parametric bootstrap also holds in our context: the parametric bootstrap is fully based on P θ, while the non parametric bootstrap builds an artificial sample (with replacement) from the original sample, which does not come from a P θ -type distribution. This gives rise to different behaviors in practice: when θ is too optimistic (which will be typically the case here when the estimation error is large), the correction brought by the parametric bootstrap (based on P θ) is often weaker than that of the non parametric one. By contrast, when θ is close to the true parameter, the parametric bootstrap approximation is more faithful because it uses the model, see Section 5.

4 Theoretical guarantees for the plug-in procedure

In this section, we derive theoretical properties for the plug-in procedure: we show that its FCR and mFCR is close to α while its expected selection number is close to be optimal under some conditions.

Additional notation and assumptions

We make use of an optimality theory for mFCR control, that will be developed in detail in Section A.1. This approach extensively relies on the following quantities (recall the definition of T (X, θ) in ( 5)):

mFCR * t = E θ * (T (X, θ * ) | T (X, θ * ) < t) ; (12) t * (α) = sup {t ∈ [0, 1] : mFCR * t ≤ α} (13) α c = inf{mFCR * t : t ∈ (0, 1], mFCR * t > 0}; (14) ᾱ = mFCR * 1 . (15)
In words, mFCR * t is the mFCR of an oracle procedure that selects the T * i smaller than a threshold t (Lemma 11). Then, t * (α) is the optimal threshold such that this procedure has a mFCR controlled at level α. Next, α c and ᾱ are the lower and upper bounds for the level α, respectively, for which the optimality theory can be applied. Now, we introduce our main assumption, which will be ubiquitous in our analysis.

Assumption 1. For all θ ∈ Θ, under P θ * , the r.v. T (X, θ) given by ( 5) is continuous, that is,

t → P θ * (T (X, θ) < t) is continuous on [0, 1]. In addition, it is increasing on (α c , ᾱ).
Assumption 1 is useful to several regards: first, it prohibits ties in the T (X i , θ)'s, 1 ≤ i ≤ m, so that the selection rule (see Algorithm 1) can be truly formulated as a thresholding rule. Second, it entails interesting properties for function t → mFCR * t , see Lemma 11 (this in particular ensures that the supremum in ( 13) is a maximum). Also note that the inequality

0 ≤ α c < ᾱ < 1 -1/Q holds under Assumption 1.
The next assumption ensures that the density family {f u , u ∈ U } is smooth, and will be useful to establish consistency results.

Assumption 2. For P θ * -almost all x ∈ R d , u ∈ U → f u (x) is continuous.
Let us now introduce some additional quantities measuring the regularity of the model and that will appear in our remainder terms (recall definition (4), ( 5) and (13) of q (X, θ), T (X, θ) and t * (α), respectively): for , δ, v > 0,

W ( ) = sup E θ * max 1≤q≤Q | q (X, θ * ) -q (X, θ)| , θ -θ * 2 ≤ , θ ∈ Θ ; (16) W T (δ) = sup{| P θ * (T (X, θ * ) < t ) -P θ * (T (X, θ * ) < t)| , t, t ∈ [0, 1], |t -t| ≤ δ}; (17) Ψ( ) = inf δ∈(0,1) {W T (δ) + W ( )/δ} ; (18) W t * ,α (v) = sup {|t * (α + β) -t * (α)| , |β| ≤ v} . ( 19
)
Note that Ψ( ) ≤ W T (W ( ) 1/2 ) + W ( ) 1/2 for small enough. The following lemma is straightforward.

Lemma 4. Under Assumption 1, we have lim δ→0 W T (δ) = 0, lim v→0 W t * ,α (v) = 0. Under Assumption 2, we have lim →0 W ( ) = 0. Under both assumptions, we have lim →0 Ψ( ) = 0.

We can derive rates for the convergences in Lemma 4 under the following additional regularity condition.

Assumption 3. There exists positive constants r = r(θ * ),

C 1 = C 1 (θ * ), C 2 = C 2 (θ * , α), C 3 = C 3 (θ * , α) such that (i) for P θ * -almost all x, u ∈ U → f u (x) is continuously differentiable, and 1≤q≤Q E θ *    sup θ∈Θ θ-θ * ≤r ∇ θ q (X, θ)    ≤ C 1 ; (ii) for all t, t ∈ [0, 1], | P θ * (T (X, θ * ) < t) -P θ * (T (X, θ * ) < t )| ≤ C 2 |t -t |; (iii) for all β ∈ [(α c + α)/2, (α + ᾱ)/2], |t * (β) -t * (α)| ≤ C 3 |β -α|. Lemma 5. Under Assumption 3, we have W ( ) ≤ C 1 , W T (δ) ≤ C 2 δ, W t * ,α (v) ≤ C 3 v and Ψ( ) ≤ (1 + C 2 )C 1/2 1 1/2 for , δ, v small enough.
In Appendix D, it is proved that Assumptions 1, 2 and 3 hold true in the homoscedastic two-component multivariate Gaussian model, see Lemma 18.

Let us now discuss conditions on the estimator θ on which the plug-in procedure is based. We start by introducing the following assumption (used in the concentration part of the proof, see Lemma 14).

Assumption 4. The estimator θ is assumed to be valued in a countable subset D of Θ.

This assumption is a minor restriction, because we can always choose D ⊂ Q K (recall Θ ⊂ R K ). Next, we additionally define a quantity measuring the quality of the estimator: for all > 0,

η( , θ * ) = P θ * min σ∈[Q] θσ -θ * 2 ≥ . (20)
In the Gaussian case, the quantity η( , θ * ) is provided to be small for a constrained MLE, see Proposition 16.

A general result

The following theorem is our main theoretical result: it provides non-asymptotical bounds on the mFCR/FCR of the plug-in procedure and on its average selection number.

Theorem 6. Let Assumption 1 be true. For any α ∈ (α c , ᾱ), for s * = s * (α, θ * ) ∈ (0, 1) and e * = e(α, θ * ) > 0 two constants only depending on α and θ * , the following holds. Consider the plug-in procedure C PI α = ( Z PI , S PI α ) introduced in Algorithm 2 and based on an estimator θ satisfying Assumption 4, with η( , θ * ) defined by (20). Then for ≤ e * and n ≥ 4, letting

∆ n ( ) = 2 (W T (W t * ,α (2δ n + 8Ψ( )/s * )) + 4Ψ( ) + 2δ n ) + 50/n + 10η( , θ * ),
for δ n = (2/s * ) (log n)/n and with the quantities W T , W , Ψ, W t * ,α defined by (17), ( 16), ( 18), ( 19), respectively, it holds:

• C PI α controls both the FCR and mFCR at level close to α in the following sense:

max mFCR( C PI α ), FCR( C PI α ) ≤ α + ∆ n ( )/s * ;
• C PI α is nearly optimal in the following sense: for any other procedure C = ( Z, S) that controls the mFCR at level α, that is, with mFCR(C) ≤ α, we have

n -1 E θ * (| S PI α |) ≥ n -1 E θ * (|S|) -∆ n ( ).
The proof employs techniques that share similarities with the work of [START_REF] Rebafka | Graph inference with clustering and false discovery rate control[END_REF] developed in a different context, see Appendix A. Here, a difficulty is to handle the new statistics T (X i , θ) which is defined as an extremum, see (5).

Corollaries

In this section, we present two straightforward consequences of the main result. By Lemma 4, assuming Assumptions 1 and 2, we have that for all small enough, the limit of the remainder term lim sup n ∆ n ( ) can be bounded by a function of that vanishes when tends to 0. This yields the following consistency result.

Corollary 7 (Asymptotic optimality of the plug-in procedure). Consider the setting of Theorem 6 where, in addition, Assumption 2 is supposed to hold. Then, we have

lim sup n FCR( C PI α ) ≤ α, lim sup n mFCR( C PI α ) ≤ α,
and for any procedure C = ( Z, S) that controls the mFCR at level α, we have

lim inf n {n -1 E θ * (| S PI α |) -n -1 E θ * (|S|)} ≥ 0.
As shown by Lemma 5, by strengthening the assumptions, Theorem 6 delivers in addition convergence rates.

Corollary 8 (Optimality of the plug-in procedure with rates). Consider the setting of Theorem 6, where in addition Assumption 3 holds. Then, with constants C 1 = C 1 (α, θ * ) > 0 and C 2 = C 2 (α, θ * ) > 0, we have for any sequence n > 0 tending to zero, for n larger than a constant only depending on α and θ * , max((FCR(

C PI α ), mFCR( C PI α )) ≤ α + C 1 1/2 n + (log n)/n + η( n , θ * ) (21) n -1 E θ * (| S PI α |) -n -1 E θ * (|S|) ≥ -C 2 1/2 n + (log n)/n + η( n , θ * ) , (22)
for any procedure C = ( Z, S) that controls (non asymptotically) the mFCR at level α.

The assumptions of Corollary 8 are all satisfied in the homoscedastic two-component multivariate Gaussian model. Applying this result in this case with n = c (log n)/n (for some constant c > 0 not depending on n) and with θ being a constrained MLE, Proposition 16 ensures that η( n , θ * ) is smaller than 1/n. This indicates that the convergence rates in ( 21) and ( 22) are of order ((log n)/n) 1/4 in this case.

Experiments

In this section, we evaluate the behavior of the new procedures: plug-in (Algorithm 2), parametric bootstrap and non parametric bootstrap (Algorithm 3). For this, we use both synthetic and real data.

Synthetic data set

The performance of our procedures is studied via simulations in different settings with various difficulties. All of them are gaussian mixture models, with possible restrictions on the parameter space. For parameter estimation, the classical EM algorithm is applied with 100 iterations and 10 starting points chosen with Kmeans++ [START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF]. In the bootstrap procedures B = 1000 bootstrap samples are generated. The performance of all procedures is assessed via the sample FCR and the proportion of classified data points, which is referred to as the selection frequency. For every setting and every set of parameters, depicted results display the mean over 100 simulated datasets. As a baseline, we consider the fixed threshold procedure in which one selects data points that have a maximum posterior group membership probability that exceeds 1 -α. The oracle procedure (Algorithm 1) is also considered in our experiments for comparison.

Finally note that some figures are postponed in Appendix E for space reasons.

Known proportions and covariances

In the first setting, the true mixture proportions and covariance matrices are known and used in the EM algorithm. We consider the case

Q = 2, π 1 = π 2 = 1/2 and Σ 1 = Σ 2 = I d with I d the (d × d)-identity matrix.
For the mean vectors, we set µ 1 = 0 and µ 2 = ( / √ d, . . . , / √ d). The quantity corresponds to the mean separation, that is, µ 1 -µ 2 2 = and accounts for the difficulty of the clustering problem.

Figure 2 displays the FCR for nominal level α = 0.1, sample size n = 100, dimension d = 2 and varying mean separation ∈ {1, √ 2, 2, 4}. Globally, our procedures all have an FCR close to the target level α (excepted for the very well separated case = 4 for which the FCR is much smaller because a large part of the items can be trivially classified). In addition, the selection rate is always close to the one of the oracle procedure. On the other hand, the baseline procedure is too conservative: its FCR can be well below the nominal level and it selects up to 50% less than the other procedures. This is well expected, because unlike our procedures, the baseline has a fixed threshold and thus does not adapt to the difficulty of the problem.

We also note that the FCR of the plug-in approach is slightly inflated for a weak separation ( = 1). This comes from the parameter estimation, which is difficult in that case. This also illustrates the interest of the bootstrap methods, that allow to recover the correct level in that case, by appropriately correcting the plug-in approach. Diagonal covariances In this setting, the true parameters are the same as in previous paragraph, but the true mixture proportions and covariance matrices are unknown and not used in the EM algorithm. However, to help the estimation, the diagonal structure of Σ 1 and Σ 2 is used in this algorithm. Figure 3 displays the FCR and the selection frequency in function of the separation for this case. The conclusion is qualitatively the same as in the previous case, but with larger FCR values for a weak separation. Overall, it shows that the plug-in procedure is anti-conservative and that the bootstrap corrections are able to recover an FCR/selection frequency close to the one of the oracle. However, for a weak separation = 1, note that the parametric bootstrap correction is not enough and that the latter procedure still overshoots the level α. Indeed, in our simulations, it appears that P θ is typically a distribution that is more favorable than P θ * from a statistical point of view (for instance, with more separated clusters). Note that these conclusions also hold when making the FCR/selection frequency vary with n, see Figure 4.

Figure 5 displays the FCR and the selection frequency for varying nominal level α, with = √ 2 and n ∈ {200, 1000}. The plug-in is still anti-conservative while the bootstrap procedures have an FCR that is close to α for both sample sizes and uniformly on the considered α range. Moreover, we note that for all our procedures (including the plug-in), the gap between the FCR and the nominal level is roughly constant with α: this illustrates the adaptive aspect of our procedures. This is in contrast with the baseline procedure, for which this gap highly depends on α, and which may be either anti-conservative or sub-optimal depending on the α value. Other settings We also consider the following settings:

• Larger dimension (Figure 9). Same as in the previous paragraph but for d = 20.

• Three components (Figure 10): Same as in the previous paragraph but for Q = 3,

π 1 = π 2 = π 3 = 1/3, Σ 1 = Σ 2 = Σ 3 = I 2 , µ 1 = 0, µ 2 = ( / √ 2, / √
2), µ 3 = (0, √ ) (so that µ 3 is at equal L2-distances from µ 1 and µ 2 ).

• Unconstrained model (Figure 11): In this case, the EM algorithm is agnostic in the sense that does not use any knowledge, whatsoever, of the structure or values of the parameters. The true parameters are the same as the previous paragraph.

• An additional "typical" setting (Figure 6): an unconstrained model with three components Q = 3, dimension d = 4 and a separation = 2.

In the three first settings, the difficulty of the estimation problem is increased with respect to the previous section. Hence, the behaviors the aforementioned procedures is deteriorated. In particular, it puts forward that the non parametric bootstrap can be anti-conservative (resp. over-conservative) in some cases when n is too large (resp. small). Finally, the last setting is intended to be a faithful summary of the procedure behaviors in a "typical" situation. For a fairly large sample size n = 1000, the new bootstrap procedures are correctly mimicking the oracle. The more challenging case of a small sample size n = 100 is handled differently by these two corrections: the parametric one is anti-conservative while the non-parametric is very conservative.

In conclusion, in our experiments, the parametric bootstrap procedure shows overall the more "stable" behavior: it uniformly improves the plug-in procedure across all the explored parameter ranges. In addition, it gets an FCR and a selection frequency close to the one of the oracle when the sample size n is fairly large. For more challenging cases where the sample size is small and we seek for a stricter FCR control, the non-parametric bootstrap is an interesting alternative.

Real data set

We consider the Wisconsin Breast Cancer Diagnosis (WCBD) dataset from the UCI ML repository. The data consists of features computed from a digitalized image of a fine needle aspirate (FNA) of a breast mass, on a total of 569 patients (each corresponds to one FNA sample) of which 212 are diagnosed as Benign and 357 as Malignant. Ten real-valued measures were computed for each cell nucleus present in any one image (e.g. radius, perimeter, texture, etc.). Then, the mean, standard error and mean of the three largest values of these measures were computed for each image, resulting in a total of 30 features. Here, we restrict the analysis to the variables that correspond to the mean of these measures.

We choose to model the data as a mixture of Students as proposed in [START_REF] Peel | Robust mixture modelling using the t distribution[END_REF]. Student mixtures are appropriate for data containing observations with longer than normal tails or atypical observations leading to overlapping clusters. Compared to Gaussian mixtures, Students are less concentrated and thus produce estimates of the posterior probabilities of class memberships that are less extreme, which is favorable for our selection procedures. In our study, the degree of freedom of each component is set to 4, and no constraints are put on the rest of the parameters. The t-mixture is fit via the EM algorithm provided by the Python package studenttmixture [START_REF] Peel | Robust mixture modelling using the t distribution[END_REF].

For illustration, Figure 7 (panel (a)) displays the first two variables of the dataset, the mean radius and the mean texture of the images. Different colors indicate the ground truth labels (this information is not used in the clustering). One can see that the Student approximation is fairly good for each of the groups, and there is some overlap between them. Figure 7 (panel (b)) displays the MAP clustering result for the t-mixture model without any selection. The FCR is computed with respect to the ground truth labels and amounts to 14 %. Finally, Figure 7 (panel (c)) provides the result of our parametric bootstrap procedure with nominal level α = 5%. The procedure does not classify points that are at the intersection of the clusters and the FCR equals 3%, which is below the targeted level. Figure 8 (panel (a)) provides a comparison of all our procedures and the baseline for varying nominal level α. The new procedures yield quite similar results. In particular, we see that the false clustering rate is always close to the nominal level, which illustrates once again the adaptive behavior of our procedures. By contrast, the false clustering rate of the baseline procedure is significantly below the nominal level and selects far less data points than our procedures, especially for large values of α. In addition, Figure 8 (panel (b)) displays results for the dataset where seven variables (d = 7) are analyzed and the conclusions are qualitatively the same.

Conclusion and discussion

We have presented new data-driven methods providing both clustering and selection that ensure an FCR control guarantee in a mixture model. The plug-in approach was shown to be theoretically valid both when the parameter estimation is accurate and the sample size is large enough. When this is not necessarily the case, we proposed two second-order bootstrap corrections that have been shown to increase the FCR control ability on numerical experiments. Finally, applying our unsupervised methods to a supervised data set, our approach has been qualitatively validated by considering the attached labels as revealing the true clusters: our approach produces a selection/clustering close to what one would have done by observing the labels with some misclassification error range.

We would like to underline that the cluster number Q is assumed to be fixed and known throughout the study. In practice, it can be fitted from the data by using the standard AIC or BIC criteria. In addition, if several values of Q make sense from a practical viewpoint, we recommend to provide to the practitioner the collection of the corresponding outputs.

Concerning the pure task of controlling the FCR in the mixture model, our methods provide a correct FCR control in some area of the parameter space, leaving other less favorable parameter configurations with a slight inflation in the FCR level. This phenomenon is well known for FDR control in the two group mixture multiple testing model [START_REF] Sun | Oracle and adaptive compound decision rules for false discovery rate control[END_REF][START_REF] Roquain | False discovery rate control with unknown null distribution: is it possible to mimic the oracle?[END_REF], and facing a similar problem in our framework is well expected. On the one hand, in some cases, this problem can certainly be solved by improving on parameter estimation: here the EM algorithm seems to over-estimate the extreme posterior probabilities, which makes the plug-in procedure too anti-conservative. On the other hand, it could be hopeless to expect a robust FCR control uniformly valid over all configurations, while being optimal in the favorable cases. To illustrate that point, we refer to the work [START_REF] Roquain | False discovery rate control with unknown null distribution: is it possible to mimic the oracle?[END_REF] that shows that such a procedure does not exist in the FDR controlling case, when the null distribution is Gaussian with an unknown scaling parameter (which is a framework sharing similarities with the one considered here). Investigating such a "lower bound" result in the current setting would provide better guidelines for the practitioner and is therefore an interesting direction for future research. In addition, in these unfavorable cases, adding labeled samples and considering a semi-supervised framework can be an appropriate alternative for practical use. This new sample is likely to considerably improve the inference. Studying the FCR control in that setting is another promising avenue.

Note that the optimal procedure is not the same as the oracle procedure defined in Section 3.1, although these two procedures are expected to behave roughly in the same way (at least for a large n).

Under Assumption 1, Lemma 11 entails that, for α > α c , mFCR(C * t * (α) ) ≤ α. Hence, C * t * (α) controls the mFCR at level α. In addition, it is optimal in the following sense: any other mFCR controlling procedure should select less items than C * t * (α) .

Lemma 9 (Optimality of C * t * (α) ). Let Assumption 1 be true and choose α ∈ (α c , ᾱ]. Then the oracle procedure C * t * (α) = ( Z * , S * t * (α) ) satisfies the following:

(i) mFCR(C * t * (α) ) = α;
(ii) for any procedure C = ( Z, S) such that mFCR(C) ≤ α, we have

E θ * (|S|) ≤ E θ * (|S * t * (α) |).

A.2 Preliminary steps for proving Theorem 6

To keep the main proof concise, we need to define several additional notation. Let for t ∈ [0, 1] and θ ∈ Θ (recall ( 5))

L 0 (θ, t) = 1 n n i=1 T (X i , θ)1 T (X i ,θ)<t ; L 1 (θ, t) = 1 n n i=1 1 T (X i ,θ)<t . Denote L = L 0 / L 1 , L 0 = E θ * L 0 , L 1 = E θ * L 1 , L = L 0 /L 1 (with the convention 0/0 = 0).
Note that for any α > α c , the mFCR of the optimal procedure C * t * (α) defined in Section A.1 is given by mFCR(C * t * (α) ) = L(θ * , t * (α)) = α. Also, we denote from now on * i,q = P θ * (Z i = q|X i ) for short and introduce for any parameter θ ∈ Θ (recall (4) and (5))

q(X i , θ) ∈ argmax q∈{1,...,Q} q (X i , θ), 1 ≤ i ≤ n; (23) U (X i , θ) = 1 - * i,q(X i ,θ) , 1 ≤ i ≤ n; (24) M 0 (θ, t) = 1 n n i=1 U (X i , θ)1 T (X i ,θ)<t , t ∈ [0, 1], (25)
Note that M 0 (θ 14) and ( 15)), we also let

* , t) = L 0 (θ * , t) but in general M 0 (θ, t) is different from L 0 (θ, t). We denote M = M 0 / L 1 , M 0 = E θ * M 0 and M = M 0 /L 1 (with the convention 0/0 = 0). When α ∈ (α c , ᾱ] (recall (
s * = s * (α, θ * ) = n -1 E θ * |S * t * ( α+αc 2 ) | = L 1 (θ * , t * ((α + α c )/2)) > 0. ( 26
)
We easily see that the latter is positive: if it was zero then S * t * ((α+αc)/2)) would be empty which would entails that mFCR(C * t * ((α+αc)/2) ) is zero. This is excluded by definition ( 14) of

α c because (α + α c )/2 > α c .
Also, we are going to extensively use the event

Ω = min σ∈[Q] θσ -θ * 2 < .
On this event, we fix any permutation σ ∈ [Q] (possibly depending on X) such that θσθ * 2 < . Now using Lemma 12, the plug-in selection rule can be rewritten as S PI α = {i ∈ {1, . . . , n} : Ti < t(α)} (denoted by S in the sequel for short), where Lemma 10. For the permutation σ in Ω realizing θσ -θ * 2 < , we have on the event Ω the following relations:

t(α) = sup{t ∈ [0, 1] : L( θ, t) ≤ α}. ( 27
| S| = L 1 ( θσ , t(α)); min σ ∈[Q] E θ * ε S (σ ( Z), Z) X ≤ M 0 ( θσ , t(α)); min σ ∈[Q] E θ * ε S (σ ( Z), Z) max(| S|, 1) X ≤ M( θσ , t(α)).
Finally, we make use of the concentration of the empirical processes L 0 (θ, t), L 1 (θ, t), and M 0 (θ, t), uniformly with respect to θ ∈ D (where D is defined in Assumption 4). Thus, we define the following events, for δ, > 0 (recall s * defined by ( 26)):

Γ 0,δ,t = sup θ∈D L 0 (θ, t) -L 0 (θ, t) ≤ δ ; Γ 1,δ,t = sup θ∈D L 1 (θ, t) -L 1 (θ, t) ≤ δ ; Γ δ,t =      sup θ∈D, L 1 (θ,t)≥s * L(θ, t) -L(θ, t) ≤ δ      ; Υ 0,δ,t = sup θ∈D M 0 (θ, t) -M 0 (θ, t) ≤ δ .
Note that the following holds:

Γ 0,δs * /2,t ∩ Γ 1,δs * /2,t ⊂ Γ δ,t . (28)
Indeed, on the event Γ 0,δs * /2,t ∩ Γ 1,δs * /2,t , provided that L 1 (θ, t) ≥ s * , we have θ, t). This proves the desired inclusion.

L 0 (θ, t) L 1 (θ, t) - L 0 (θ, t) L 1 (θ, t) ≤ L 0 (θ, t) -L 0 (θ, t) L 1 (θ, t) + L 0 (θ, t) 1 L 1 (θ, t) - 1 L 1 (θ, t) ≤ (δs * /2)/s * + (δs * /2)/s * = δ, because L 0 (θ, t) ≤ L 1 (

A.3 Proof of Theorem 6

Let us now provide a proof for Theorem 6.

Step 1: bounding t(α) w.r.t. t * (α) Recall ( 13), ( 27) and ( 26). In this part, we only consider realizations on the event

Ω . Let β ∈ [ 2α+αc 3 , α+ ᾱ 2 ]
. By Lemma 13, we have

L 1 ( θσ , t * (β)) ≥ L 1 (θ * , t * (β)) -Ψ( θσ -θ * 2 ) ≥ L 1 (θ * , t * ((2α + α c )/3)) -Ψ( ), because t * (β) ≥ t * ( 2α+αc 3 ) since t * (•)
is non decreasing by Lemma 11. Hence L 1 ( θσ , t * (β)) ≥ s * for smaller than a threshold only depending on θ * and α. Hence, we have on Γ δ,t * (β) that

L( θσ , t * (β)) -δ ≤ L( θσ , t * (β)) ≤ δ + L( θσ , t * (β)).
By using again Lemma 13, we have

L(θ * , t * (β)) -3Ψ( )/s * ≤ L( θσ , t * (β)) ≤ L(θ * , t * (β)) + 3Ψ( )/s * . Given that L(θ * , t * (β)) = mFCR(C * t * (β) ) = β (see Lemma 9 (i)), it follows that for γ = γ( , δ) = δ + 4Ψ( )/s * , on the event Γ δ,t * (α-γ) ∩ Γ δ,t * (α+γ) , L( θσ , t * (α -γ)) ≤ α, L( θσ , t * (α + γ)) > α,
where we indeed check that α -γ ≥ 2α+αc 3 and α + γ ≤ α+ ᾱ 2 for δ and smaller than some threshold only depending on θ * and α. In a nutshell, we have established

Γ δ,t * (α-γ) ∩ Γ δ,t * (α+γ) ∩ Ω ⊂ t * (α -γ) ≤ t(α) ≤ t * (α + γ) . (29)
Step 2: upper-bounding the FCR Let us consider the event

Λ α,δ, := Γ 0,δs * /2,t * (α-γ) ∩ Γ 1,δs * /2,t * (α-γ) ∩ Γ 0,δs * /2,t * (α+γ) ∩ Γ 1,δs * /2,t * (α+γ) ∩ Υ 0,δ,t * (α+γ) ∩ Ω ,
where the different events have been defined in the previous section. Let us prove (21). By using Lemma 10 and (29),

FCR( Ĉ) ≤ E θ * [ M( θσ , t(α))1 Λ α,δ, ] + P((Λ α,δ, ) c ) ≤ E θ * M 0 ( θσ , t * (α + γ)) L 1 ( θσ , t * (α -γ))
1 Λ α,δ, + P((Λ α,δ, ) c ).

Now using a concentration argument on the event Λ α,δ, ⊂ Γ 1,δ,t * (α-γ) ∩ Υ 0,δ,t * (α+γ) , we have

FCR( Ĉ) ≤ E θ * M 0 ( θσ , t * (α + γ)) + δ L 1 ( θσ , t * (α -γ)) -δ 1 Λ α,δ, + P((Λ α,δ, ) c ) ≤ M 0 (θ * , t * (α + γ)) + 3Ψ( ) + δ L 1 (θ * , t * (α -γ)) -Ψ( ) -δ + P((Λ α,δ, ) c ) = L 0 (θ * , t * (α + γ)) + 3Ψ( ) + δ L 1 (θ * , t * (α -γ)) -Ψ( ) -δ + P((Λ α,δ, ) c ), (30)
by using Lemma 13 and that M 0 (θ * , t) = L 0 (θ * , t) for all t by definition. Now, using again Lemma 13, we have

L 0 (θ * , t * (α + γ)) ≤ L 0 (θ * , t * (α -γ)) + W T (t * (α + γ) -t * (α -γ)) ≤ L 0 (θ * , t * (α -γ)) + W T (W t * ,α (2γ))
This entails

FCR( Ĉ) ≤ L 0 (θ * , t * (α -γ)) + W T (W t * ,α (2γ)) + 3Ψ( ) + δ L 1 (θ * , t * (α -γ)) -Ψ( ) -δ + P((Λ α,δ, ) c ) ≤ L 0 (θ * , t * (α -γ)) L 1 (θ * , t * (α -γ)) -Ψ( ) -δ + (s * /2) -1 (W T (W t * ,α (2γ)) + 3Ψ( ) + δ) + P((Λ α,δ, ) c ),
by choosing , δ smaller than a threshold (only depending on θ * and α) so that

L 1 (θ * , t * (α - γ)) -Ψ( ) -δ ≥ s * /2. Now using L 0 (θ * , t * (α -γ)) = (α -γ)L 1 (θ * , t * (α -γ)), we have L 0 (θ * , t * (α -γ)) L 1 (θ * , t * (α -γ)) -Ψ( ) -δ = (α -γ) 1 + Ψ( ) + δ L 1 (θ * , t * (α -γ)) -Ψ( ) -δ ≤ α 1 + (s * /2) -1 (Ψ( ) + δ) .
This leads to

FCR( Ĉ) ≤ α + (2/s * ) (W T (W t * ,α (2δ + 8Ψ( )/s * )) + 4Ψ( ) + 2δ) + P((Λ α,δ, ) c ),
which holds true for δ, smaller than a threshold only depending on θ * and α.

Step 3: upper-bounding the mFCR We apply a similar technique as for step 2. By using Lemma 10 and (29),

mFCR( Ĉ) ≤ E θ * [ M 0 ( θσ , t(α))1 Λ α,δ, ] + P((Λ α,δ, ) c ) E θ * [ L 1 ( θσ , t(α))1 Λ α,δ, ] ≤ E θ * [ M 0 ( θσ , t * (α + γ))1 Λ α,δ, ] + P((Λ α,δ, ) c ) E θ * [ L 1 ( θσ , t * (α -γ))1 Λ α,δ, ]
. Now using a concentration argument on Λ α,δ, ⊂ Γ 1,δ,t * (α-γ) ∩ Υ 0,δ,t * (α+γ) , we have

mFCR( Ĉ) ≤ E θ * [(M 0 ( θσ , t * (α + γ)) + δ)1 Λ α,δ, ] + P((Λ α,δ, ) c ) E θ * [(L 1 ( θσ , t * (α -γ)) -δ)1 Λ α,δ, ] ≤ M 0 (θ * , t * (α + γ)) + 3Ψ( ) + δ + P((Λ α,δ, ) c ) L 1 (θ * , t * (α -γ)) -Ψ( ) -δ -P((Λ α,δ, ) c ) = L 0 (θ * , t * (α + γ)) + 3Ψ( ) + δ + P((Λ α,δ, ) c ) L 1 (θ * , t * (α -γ)) -Ψ( ) -δ -P((Λ α,δ, ) c ) ,
by using Lemma 13 and that M 0 (θ

* , t) = L 0 (θ * , t) by definition. Letting x = L 0 (θ * , t * (α + γ)) + 3Ψ( ) + δ, y = L 1 (θ * , t * (α -γ)) -Ψ( ) -δ and u = P((Λ α,δ, ) c
), we have obtained the bound (x + u)/(y -u), which has to be compared with the FCR bound (30), which reads x/y + u. Now, when y ∈ [0, 1], x ≥ 0, x/y ≤ 2, u/y ≤ 1/2, y -u ≥ s * /2, we have

(x + u)/(y -u) ≤ x/y 1 -u/y + (2/s * )u ≤ x/y(1 + 2u/y) + (2/s * )u ≤ x/y + (10/s * )u.
As a result, for , δ small enough, and P((Λ α,δ, ) c ) ≤ s * /4, we obtain the same bound as for the FCR, with P((Λ α,δ, ) c ) replaced by (10/s * )P((Λ α,δ, ) c ).

Step 4: lower-bounding the selection rate In Step 3, when bounding the mFCR, we derived a lower bound for the denominator of the mFCR, that is, E θ * (| Ŝ|). It reads

n -1 E θ * (| Ŝ|) ≥ L 1 (θ * , t * (α -γ)) -Ψ( ) -δ -P((Λ α,δ, ) c ) ≥ L 1 (θ * , t * (α)) -W T (t * (α) -t * (α -γ)) -Ψ( ) -δ -P((Λ α,δ, ) c ) ≥ n -1 E θ * (|S * t * (α) |) -W T (W t * ,α (γ)) -Ψ( ) -δ -P((Λ α,δ, ) c ),
by using ( 17) and ( 19). Now consider another procedure C = ( Z, S) that controls the mFCR at level α, that is, mFCR(C) ≤ α. By Lemma 9, we then have

E θ * (|S * t * (α) |) ≥ E θ * (|S|).
Step 5: concentration Finally, we bound P((Λ α,δ, ) c ) by using Lemma 14 with u = (log n)/n and x = 2 (log n)/n. This gives for δ = 2x/s * , and n such that log(n) ≥ 1,

P((Λ α,δ, ) c ) ≤ 5/n + P(Ω c ).

B Proofs of lemmas

Proof of Lemma 1 The clustering risk of Z is given by

R( Z) = E θ * min σ∈[Q] E θ * n -1 n i=1 1{Z i = σ( Ẑi )} X = E θ * min σ∈[Q] n -1 n i=1 P θ * (Z i = σ( Ẑi ) | X) ≥ E θ * min Z n -1 n i=1 P θ * (Z i = Ẑi | X) ,
where, by independence, the minimum in the lower bound is achieved for the Bayes clustering. Thus, R(

Z) ≥ n -1 n i=1 E θ * (T * i ). Moreover, n -1 n i=1 E θ * (T * i ) ≥ R( Z * ), since R( Z * ) = E θ * min σ∈[Q] n -1 n i=1 P θ * (Z i = σ( Ẑ * i ) | X) ≤ E θ * n -1 n i=1 P θ * (Z i = Ẑ * i | X) .
Thus, min Z R( Z) = R( Z * ) and the proof is completed.

Proof of Lemma 2 Following the reasoning of the proof of Lemma 1 that, we have

FCR θ * (C) = E θ * min σ∈[Q] E θ * i∈S 1{Z i = σ( Ẑ * i )} max(|S|, 1) X = E θ * i∈S T * i max(|S|, 1
) .

Proof of Lemma 3 By definition, we have

FCR( C PI α ) = E θ *   min σ∈[Q] E θ *   n i=1 1 Z i =σ( ẐPI i (X)) 1{i ∈ ŜPI (X)} max(| ŜPI (X)|, 1) X    
so that (9) follows by a direct integration w.r.t. the latent variable Z.

Proof of Lemma 4

The only non-trivial fact is for W t * ,α (v). Assumption 1 and Lemma 11 provide that t → mFCR * t is a one-to-one continuous increasing map from (t * (α c ), t * ( ᾱ)) to (α c , ᾱ). Hence, for α ∈ (α c , ᾱ), β → t * (α + β) is continuous in 0 and lim v→0 W t * ,α (v) = 0.

Proof of Lemma 9 By Lemma 11, we have that mFCR(C * t ) is monotonous in t and continuous w.r.t. t on (t * (α c ), 1], thus for α ∈ (α c , ᾱ], mFCR(C * t * (α) ) = α which gives (i). For (ii), let C = ( Z, S) be a procedure such that mFCR(C) ≤ α. Let us consider the procedure C with the Bayes clustering Z * and the same selection rule S. Since C is based on a Bayes clustering, by the same reasoning leading to R( Z * ) ≤ R( Z) in Section 3.1, we have that mFCR(C ) ≤ mFCR(C) ≤ α with

mFCR(C ) = E θ * i∈S T * i E θ * (|S|)
.

Hence,

E θ * i∈S T * i ≤ α E θ * (|S|). (31)
Now we use an argument similar to the proof of Theorem 1 in [START_REF] Cai | Covariate-assisted ranking and screening for largescale two-sample inference[END_REF]. By definition of S * t * (α) , we have that

n i=1 1 i∈S * t * (α) (X) -1 i∈S(X) (T * i -t * (α)) ≤ 0
which we can rewrite as

n i=1 1 i∈S * t * (α) (X) -1 i∈S(X) (T * i -t * (α) + α -α) ≤ 0
and so

E θ * n i=1 1 i∈S * t * (α) (X) -1 i∈S(X) (T * i -α) ≤ (t * (α) -α) E θ * n i=1 1 i∈S * t * (α) (X) -1 i∈S(X) = (t * (α) -α)(E θ * (|S * t * (α) |) -E θ * (|S|)).
On the other hand, mFCR(C * t * (α) ) = α together with (31) implies that

E θ * n i=1 1 i∈S * t * (α) (X) -1 i∈S(X) (T * i -α) = E θ *    i∈S * t * (α) T * i -α|S * t * (α) | - i∈S T * i + α|S|    ≥ 0.
Combining, the relations above provides

(t * (α) -α)(E θ * (|S * t * (α) |) -E θ * (|S|)) ≥ 0.
Finally, noting that t * (α) -α > 0 since α = mFCR(C * t * (α) ) < t * (α) by (ii) Lemma 11, this gives E θ * (|S * t * (α) |) -E θ * (|S|) ≥ 0 and concludes the proof.

Proof of Lemma 10 First, we have by definition q (X i , θ σ ) = σ(q) (X i , θ) and thus T (X i , θ) = T (X i , θσ ) by taking the maximum over q. This gives S σ = S and yields the first equality.

Next, we have on Ω ,

min σ ∈[Q] E θ * ε S (σ ( Z), Z) X ≤ E θ * ε S (σ( Z), Z) X ≤ E θ * ε S σ (σ( Z), Z) X ,
still because S σ = S. Now observe that,

E θ * ε S σ (σ( Z), Z) X = 1 n n i=1 P θ * (Z i = σ(q(X i , θ)) X)1 T (X i , θσ )< t(α) = 1 n n i=1 (1 - * i,σ(q(X i , θ)) )1 T (X i , θσ )< t(α) = M 0 ( θσ , t(α)),
because σ(q(X i , θ)) = q(X i , θσ ). This proves the result.

C Auxiliary results

Lemma 11. Let us consider the procedure C * t defined in Section A.1 and the functional mFCR * t defined by (12). Then we have

mFCR(C * t ) = E θ * n i=1 T * i 1 T * i <t E θ * n i=1 1 T * i <t = mFCR * t , t ∈ [0, 1]. (32)
Moreover, the following properties for the function t ∈ [0, 1] → mFCR(C * t ): (i) mFCR(C * t ) is non-decreasing in t ∈ [0, 1] and, under Assumption 1, it is increasing in t ∈ (t * (α c ), t * ( ᾱ));

(ii) mFCR(C * t ) < t for t ∈ (0, 1];

(iii) Under Assumption 1, mFCR(C * t ) is continuous w.r.t. t on (t * (α c ), 1], where t * (α c ) is given by (14).

Proof. First, (32) is obtained similarly than (8). For proving (i), let t 1 , t 2 ∈ [0, 1] such that t 1 < t 2 . We show that mFCR(C * t 1 ) ≤ mFCR(C * t 2 ). Remember here the convention 0/0 = 0 and that mFCR(

C * t ) = E θ * (T (X, θ * ) | T (X, θ * ) < t). First, if P θ * (T (X, θ * ) < t 1 ) = 0 then the result is immediate. Otherwise, we have that mFCR(C * t 1 ) -mFCR(C * t 2 ) = (P θ * (T (X, θ * ) < t 1 )) -1 E θ * T (X, θ * ) 1 T (X,θ * )<t 1 - P θ * (T (X, θ * ) < t 1 ) P θ * (T (X, θ * ) < t 2 ) 1 T (X,θ * )<t 2
where, given that t 1 < t 2 , the quantity in the brackets is positive when T (X, θ * ) < t 1 and is negative or zero otherwise. Hence,

T (X, θ * ) 1 T (X,θ * )<t 1 - P θ * (T (X, θ * ) < t 1 ) P θ * (T (X, θ * ) < t 2 ) 1 T (X,θ * )<t 2 ≤ t 1 1 T (X,θ * )<t 1 - P θ * (T (X, θ * ) < t 1 ) P θ * (T (X, θ * ) < t 2 ) 1 T (X,θ * )<t 2 .
Taking the expectation makes the right-hand-side equal to zero, from which the result follows. Now, to show the increasingness, if mFCR(C * t 1 ) = mFCR(C * t 2 ) for t * (α c ) < t 1 < t 2 < t * (ᾱ), then the above reasoning shows that (T (X, θ * ) -t 1 ) 1 T (X,θ * )<t 1 -

P θ * (T (X, θ * ) < t 1 ) P θ * (T (X, θ * ) < t 2 )
1 T (X,θ * )<t 2 ≤ 0 and has an expectation equal to 0. Hence, given that T (X, θ * ) is continuous, we derive that almost surely

P θ * (T (X, θ * ) < t 2 ) 1 T (X,θ * )<t 1 = P θ * (T (X, θ * ) < t 1 ) 1 T (X,θ * )<t 2 , that is, P θ * (t 1 ≤ T * i < t 2 ) = 0
, which is excluded by Assumption 1. This entails mFCR(C * t 1 ) < mFCR(C * t 2 ). For proving (ii), let t > 0. If P θ * (T (X, θ * ) < t) = 0 then the result is immediate. Otherwise, we have that mFCR(C * t )-t = (P θ * (T (X, θ * ) < t)) -1 E θ * ((T (X, θ * )-t)1{T (X, θ * ) < t}). The latter is clearly not positive, and is moreover negative because (T (X, θ * )-t)1{T (X, θ * ) < t} ≤ 0 and P θ * (T (X, θ * ) = t) = 0 by Assumption 1.

For proving (iii), let ψ 0 (t) = E θ * (T (X, θ * )1{T (X, θ * ) < t}) and ψ 1 (t) = P θ * (T (X, θ * ) < t), the numerator and denominator of mFCR(C * t ) = mFCR * t , respectively. ψ 1 (t) is non-decreasing in t, with ψ 1 (0) = 0 and ψ 1 (1) > 0. Moreover, ψ 0 and ψ 1 are both continuous under Assumption 1. Then denote by t c the largest t s.t. ψ 1 (t) = 0. ψ 1 is zero on [0, t c ] then strictly positive and non-decreasing on (t c , 1], and we have that t c = t * (α c ). Hence, mFCR(C * t ) is zero on [0, t c ] then strictly positive and continuous on (t c , 1].

Remark 3. With the notation of the above proof, t → mFCR(C * t ) may have a discontinuity point at t c since for t n → tn>tc t c , as ψ 1 (t n ) → 0, one does not necessarily have that mFCR(C * t ) → 0.

Lemma 12 (Expression of plug-in procedure as a thresholding rule). For any α ∈ (0, 1), let us consider the plug-in procedure C PI α = ( Z PI , S PI α ) defined by Algorithm 2 and denote K = | S PI α | the maximum of the k ∈ {0, . . . , n} such that max(k, 1) -1 k j=1 T(j) ≤ α for Ti = 1 -max q q (X i , θ), 1 ≤ i ≤ n. Consider also t(α) defined by (27). Let Assumption 1 be true and consider an estimator θ satisfying Assumption 4. Then it holds that t(α) = T(K+1) and S PI α = {i ∈ {1, . . . , n} : Ti < t(α)}.

Proof. If T(K) < T(K+1) then the result is immediate. Thus it suffices to show that T(K) = T(K+1) occurs with probability 0. From Assumption 4 (with the countable set D defined therein), we have

P θ * ( T(K) = T(K+1) ) ≤ P θ *   i =j { Ti = Tj }   ≤ P θ *   θ∈D i =j {T (X i , θ) = T (X j , θ)}   .
Now, the right term is a countable union of events which are all of null probability under Assumption 1. The result follows.

Lemma 13. We have for all θ ∈ Θ,

sup t∈[0,1] |L 1 (θ, t) -L 1 (θ * , t)| ≤ Ψ( θ * -θ ); (33) sup t∈[0,1] |L 0 (θ, t) -L 0 (θ * , t)| ≤ 2Ψ( θ * -θ ); (34) sup t∈[t * ((α+αc)/2),1] |L(θ, t) -L(θ * , t)| ≤ 3Ψ( θ * -θ )/s * ; (35) sup t∈[0,1] |M 0 (θ, t) -M 0 (θ * , t)| ≤ 3Ψ( θ * -θ ); (36) sup t∈[t * ((α+αc)/2),1] |M(θ, t) -M(θ * , t)| ≤ 4Ψ( θ * -θ )/s * ; (37)
where α ∈ (α c , ᾱ] and s * > 0 is given by (26). In addition, for all θ ∈ Θ and t, t ∈ [0, 1],

|L 0 (θ, t) -L 0 (θ, t )| ≤ 4Ψ( θ * -θ ) + W T (|t -t |). (38)
Proof. Fix θ ∈ Θ and t ∈ [0, 1]. We have for any δ > 0,

|P θ * (T (X, θ) < t) -P θ * (T (X, θ * ) < t)| ≤ (P θ * (T (X, θ * ) < t + δ) -P θ * (T (X, θ * ) < t)) ∨ (P θ * (T (X, θ * ) < t) -P θ * (T (X, θ * ) < t -δ)) + P θ * (|T (X, θ * ) -T (X, θ)| > δ) ≤ W T (δ) + E θ * (|T (X, θ * ) -T (X, θ)|)/δ.
In addition, by definition (5),

|T (X, θ * ) -T (X, θ)| ≤ | max 1≤q≤Q q (X, θ * ) -max 1≤q≤Q q (X, θ)| ≤ max 1≤q≤Q | q (X, θ * ) -q (X, θ)|.
Hence,

|P θ * (T (X, θ) < t) -P θ * (T (X, θ * ) < t)| ≤ inf δ∈(0,1) {W T (δ) + W ( θ * -θ )/δ} = Ψ( θ * -θ ),
which establishes (33). Next, we have

L 0 (θ, t) -L 0 (θ * , t) = E θ * [T (X, θ)(1 T (X,θ)<t -1 T (X,θ * )<t ) + 1 T (X,θ * )<t (T (X, θ) -T (X, θ * ))] ≤ t| P θ * (T (X, θ) < t) -P θ * (T (X, θ * ) < t)| + | E θ * [1 T (X,θ * )<t (T (X, θ) -T (X, θ * ))]| ≤ | P θ * (T (X, θ) < t) -P θ * (T (X, θ * ) < t)| + E θ * |T (X, θ) -T (X, θ * )| ≤ 2Ψ( θ * -θ )
By exchanging the role of θ and θ * in the above reasoning, the same bound holds for L 0 (θ * , t)-L 0 (θ, t), which gives (34). To prove (35), we use for any

t ∈ [t * ( α+αc 2 ), 1], L 0 (θ, t) L 1 (θ, t) - L 0 (θ * , t) L 1 (θ * , t) ≤ L 0 (θ, t) -L 0 (θ * , t) L 1 (θ * , t) + L 0 (θ, t) 1 L 1 (θ * , t) - 1 L 1 (θ, t) ≤ 2Ψ( θ * -θ )/s * + 1 L 1 (θ * , t) L 0 (θ, t) L 1 (θ, t) |P θ * (T (X, θ * ) < t) -P θ * (T (X, θ) < t)| ≤ 3Ψ( θ * -θ )/s * , because L 0 (θ, t) ≤ L 1 (θ, t)
and L 1 (θ * , t) ≥ s * by monotonicity. Similarly to the bound on L 0 , we derive

|M 0 (θ, t) -M 0 (θ * , t)| ≤ | P θ * (T (X, θ) < t) -P θ * (T (X, θ * ) < t)| + E θ * |U (X, θ) -U (X, θ * )|.
Define q(X, θ) ∈ argmax q∈{1,...,Q} q (X, θ). Now, since U (X, θ * ) ≤ U (X, θ) by definition (24), we have

E θ * |U (X, θ) -U (X, θ * )| = E θ * [U (X, θ) -U (X, θ * )] = E θ * [ q(X,θ) (X, θ * ) -q(X,θ * ) (X, θ * )] = E θ * [ q(X,θ) (X, θ * ) -q(X,θ) (X, θ) + q(X,θ) (X, θ) -q(X,θ * ) (X, θ * )] ≤ E θ * [ max 1≤q≤Q | q (X, θ * ) -q (X, θ)|] + E θ * [ max 1≤q≤Q q (X, θ) -max 1≤q≤Q q (X, θ * )] ≤ 2 E θ * [ max 1≤q≤Q | q (X, θ * ) -q (X, θ)|] ≤ 2Ψ( θ * -θ ).
This proves (36) and leads to (37) by following the reasoning that provided (35).

Next, we have for 0 ≤ t ≤ t ≤ 1, by (34),

|L 0 (θ, t) -L 0 (θ, t )| ≤ |L 0 (θ * , t) -L 0 (θ * , t )| + 4Ψ( θ * -θ ).
Moreover,

|L 0 (θ * , t) -L 0 (θ * , t )| = L 0 (θ * , t) -L 0 (θ * , t ) = E θ * [T (X, θ * )1 t ≤T (X,θ * )<t ] ≤ E θ * [1 t ≤T (X,θ * )<t ] = P θ * (T (X, θ * ) < t) -P θ * (T (X, θ * ) < t ),
which is below W T (t -t ) by ( 17). This leads to (38).

Lemma 14 (Concentration of L 0 , L 1 , and M0 ). For all n ≥ 1, x > 0, t ∈]0, 1],

P θ * sup θ∈D L 0 (θ, t) -L 0 (θ, t) > x ≤ e -nu 2 ; (39) P θ * sup θ∈D L 1 (θ, t) -L 1 (θ, t) > x ≤ e -nu 2 ; (40) P θ * sup θ∈D M 0 (θ, t) -M 0 (θ, t) > x ≤ e -nu 2 , (41)
where

u > 0 is s.t. x ≥ 2 √ n + u.
Proof. The concentration of each is a direct application of Talagrand's inequality. To be more precise, Theorem 5.3. in (Massart, 2007)) states the following. Let ξ 1 , . . . , ξ n independent r.v., F a countable class of measurable functions s.t. a ≤ f ≤ b for every f ∈ F for some real numbers a, b, and

W = sup f ∈F | n i=1 f (ξ i ) -E(f (ξ i ))|.
Then, for any x > 0,

P(W -E(W ) ≥ x) ≤ e -2x 2 n 2 (b-a) 2 .
The result then follows by applying Lemma 15, which bounds the expectation term E(W ) in each case by 2 √ n.

Lemma 15. Let ξ 1 , ..., ξ n be independent r.v. and F be a countable set of measurable functions s.t. f ∞ ≤ 1 for f ∈ F. Then, one has

E sup f ∈F n i=1 f (ξ i ) -E(f (ξ i )) ≤ 2 √ n.
Proof. We have that

E sup f ∈F n i=1 f (ξ i ) -E n i=1 f (ξ i ) ≤ E sup f ∈F n i=1 f (ξ i ) -f (ξ i ) ,
where the ξ i s are independent r.v. with the same distribution as the ξ i s. Let ( i ) 1≤i≤n be independent Rademacher variables. Then, we have

n i=1 f (ξ i ) -f (ξ i ) D = n i=1 i (f (ξ i ) -f (ξ i ))
and

n i=1 f (ξ i ) -f (ξ i ) = E n i=1 i (f (ξ i ) -f (ξ i )) ξ 1 , . . . , ξ n , ξ 1 , . . . , ξ n .
Thus,

E sup f ∈F n i=1 f (ξ i ) -E n i=1 f (ξ i ) ≤ 2sup f ∈F E n i=1 i f (ξ i ) ξ 1 , . . . , ξ n ≤ 2sup f ∈F V n i=1 i f (ξ i ) ξ 1 , . . . , ξ n = 2sup f ∈F n i=1 (f (ξ i )) 2 ≤ 2 √ n.
where the second inequality is due to Jensen's inequality.

D Auxiliary results for the Gaussian case

D.1 Convergence rate

The likelihood of Gaussian mixture models is unbounded in general [START_REF] Chen | Consistency of the MLE under Mixture Models[END_REF]. Thus, the convergence of MLEs has been studied over a constrained subspace of the parameter space that may expand as the sample size increases, which is often referred to as a sieve MLE.

Proposition 16. Consider the mixture model (Section 2.1) in the d-multivariate Gaussian case where φ q = (π q , Σ q ) ∈ U with constrained parameter space defined as follows: U = [-a n , a n ] d ×{Σ ∈ S ++ d , λ ≤ λ 1 (Σ) ≤ λ 1 (Σ) ≤ λ} where a n ≤ L(log n) γ for some L, γ > 0, S ++ d denotes the space of positive definite matrices, with λ, λ some strictly positive constants. Then the (constrained) MLE is such that the corresponding quantity η(•, θ * ) defined by (20) satisfies η(δ n , θ * ) ≤ 1/n for n large enough, where δ n is a sufficiently large multiple of log n/n. q π * q -p n qq where p n qq ≤ min(π n q , π * q ). Thus, q =l p n ql ≥ q π n q -min(π n q , π * q ) = q,π n q ≥π * q π n qπ * q = q,π n q ≥π * q |π n q -π * q | and similarly we have that q =l p n ql ≥ q,π * q ≥π n q |π n q -π * q |. It follows that 2 q =l p n ql ≥ q |π n q -π * q |. Therefore, for sufficiently large n,

W 1 (G n , G * ) ≥ 1 2 π * min q ∆φ n q + C 4 q |∆π n q |.
This gives the result.

D.2 Gaussian computations

The following lemma holds.

Lemma 18. Let us consider the multivariate Gaussian case where φ q = (µ q , Σ q ), 1 ≤ q ≤ Q, with Q = 2, Σ 1 = Σ 2 is an invertible covariance matrix and µ 1 and µ 2 are two different vectors of R d . Then Assumptions 1, 2 and 3 hold true for α c = 0 and for a level α ∈ (0, ᾱ)\E for E a set of Lebesgue measure 0.

Proof. Let us first prove that T (X, θ) is a continuous random variable under P θ * (this is established below without assuming Σ 1 = Σ 2 for the sake of generality). We have

P θ * (T (X, θ) = t) = P θ * 1 -max 1≤q≤Q π q f φq (X) Q =1 π f φ (X) = t = P θ * max 1≤q≤Q π q f φq (X) = (1 -t) Q =1 π f φ (X) ≤ Q q=1 P θ * π q f φq (X) = (1 -t) Q =1 π f φ (X) .
Since Q = 2, the latter probability is (for say q = 1), equal to P θ * (π 1 f φ 1 (X) = (1/t -1)π 2 f φ 2 (X)) = P θ * (f φ 1 (X)/f φ 2 (X) = (1/t -1)π 2 /π 1 ) = P θ * (X -µ 1 ) t Σ -1 1 (X -µ 1 ) -(X -µ 2 ) t Σ -1 2 (X -µ 2 ) = -2 log ((1/t -1)π 2 /π 1 ) -log(|Σ 1 |/|Σ 2 |) . Now,

(X -µ 1 ) t Σ -1 1 (X -µ 1 ) -(X -µ 2 ) t Σ -1 2 (X -µ 2 ) = (X -µ 1 ) t Σ -1 1 (X -µ 1 ) -(X -µ 1 ) t Σ -1 2 (X -µ 2 ) -(µ 1 -µ 2 ) t Σ -1 2 (X -µ 2 ) = (X -µ 1 ) t (Σ -1 1 -Σ -1 2 )(X -µ 1 ) -(X -µ 1 ) t Σ -1 2 (µ 1 -µ 2 ) -(µ 1 -µ 2 ) t Σ -1 2 (X -µ 2 ) = (X -µ 1 ) t (Σ -1 1 -Σ -1 2 )(X -µ 1 ) -(µ 1 -µ 2 ) t Σ -1 2 (2X -µ 2 -µ 1 ).
Since the real matrix Σ -1 1 -Σ -1 2 is symmetric, we can diagonalize it and we end up with a subset of R d of the form for some real parameters α j , β j , γ. The result follows because this set has a Lebesgue measure equal to 0 in any case. Now, since Σ 1 = Σ 2 = Σ, we have for all t ∈ (0, 1), {T (X, θ) > t} = ∀q ∈ {1, . . . , Q}, π q f φq (X) < (1 -t)

Q =1 π f φ (X)
= {π 1 f φ 1 (X) < (1/t -1)π 2 f φ 2 (X)} ∩ {π 2 f φ 2 (X) < (1/t -1)π 1 f φ 1 (X)} = (1/t -1) -1 < π 1 f φ 1 (X) π 2 f φ 2 (X) < (1/t -1) .

Applying 2 log(•) on each part of the relation, we obtain {T (X, θ) > t} = -2 log(1/t -1) < a t X + b < 2 log(1/t -1) ,

for a = a(θ) = 2Σ -1 (µ 1 -µ 2 ) ∈ R d \{0} b = b(θ) = -(µ 1 -µ 2 ) t Σ -1 (µ 1 + µ 2 ) + 2 log(π 1 /π 2 ) ∈ R d .
Since under P θ * we have X ∼ π * 1 N (µ * 1 , Σ * ) + π * 2 N (µ * 2 , Σ * ), we have a t X + b ∼ π * 1 N (a t µ * 1 + b, a t Σ * a) + π * 2 N (a t µ * 2 + b, a t Σ * a). This yields for all t ∈ (0, 1),

P θ * (T (X, θ) > t) =π 1 Φ 2 log(1/t -1) -a t µ * 1 -b (a t Σ * a) 1/2 -Φ -2 log(1/t -1) -a t µ * 1 -b (a t Σ * a) 1/2 + π 2 Φ 2 log(1/t -1) -a t µ * 2 -b (a t Σ * a) 1/2 -Φ -2 log(1/t -1) -a t µ * 2 -b (a t Σ * a) 1/2 . (42)
A direct consequence is that for all t ∈ (0, 1), we have P θ * (T (X, θ) > t) < 1, that is, P θ * (T (X, θ) ≤ t) = P θ * (T (X, θ) < t) > 0. Hence, α c defined in ( 14) is equal to zero. Moreover, from (42), we clearly have that t ∈ (0, 1) → P θ * (T (X, θ) > t) is decreasing, so that t ∈ (0, 1) → P θ * (T (X, θ) ≤ t) is increasing. This proves that Assumption 1 holds in that case.

Let us now check Assumptions 2 and 3. Assumptions 2 and 3 (i) follow from Result 2.1 in [START_REF] Melnykov | On the distribution of posterior probabilities in finite mixture models with application in clustering[END_REF]. As for Assumption 3 (ii), from (42), we only have to show that the function t ∈ (0, 1) → ∂ ∂t Φ log(1/t-1)-α * β * is uniformly bounded by some constant C = C(α * , β * ), for any α * ∈ R and β * > 0. A straightforward calculation leads to the following: for all t ∈ (0, 1),

∂ ∂t Φ log(1/t -1) -α * β * = e -( log(1/t-1)-α * β * ) 2 /2 β * √ 2π 1 t(1 -t) . ( 43
)
Consider now t 0 = t 0 (α * , β * ) ∈ (0, 1/2) such that ( log(1/t-1)-α * β *

) 2 ≥ 2 log(1/t) for all t ∈ (0, t 0 ). It is clear that the right-hand-side of ( 43) is upper-bounded by

1 β * √
2π(1-t 0 ) on t ∈ (0, t 0 ). Similarly, let t 1 = t 1 (α * , β * ) ∈ (1/2, 1) such that ( log(1/t-1)-α * β *

) 2 ≥ 2 log(1/(1 -t)) for all t ∈ (t 1 , 1). It is clear that the right-hand-side of ( 43) is upper-bounded by

1 β * √ 2πt 1
on t ∈ (t 1 , 1). Finally, for t ∈ [t 0 , t 1 ], the upper-bound

1 β * √ 2πt 0 (1-t 1 )
is valid. This proves that Assumption 3 (ii) holds.

Let us now finally turn to Assumption 3 (iii). Lemma 11 ensures that t ∈ (0, t * ( ᾱ)) → mFCR * t is continuous increasing. Hence, t * : β ∈ (0, ᾱ) → t * (β) defined in ( 13) is the inverse of this function and is also continuous increasing. It is therefore differentiable almost everywhere in (0, ᾱ), so everywhere in (0, ᾱ)\E where E is a set of Lebesgue measure 0. By taking α in (0, ᾱ)\E, this ensures that t * is differentiable in α and thus that Assumption 3 (iii) holds.

Figure 1 :

 1 Figure 1: Data from Gaussian mixtures with three components (n = 200), in a fairly separated case (panel (a)) and an ambiguous case (panel (b)). In each panel, the left part displays the true clustering, while the right part illustrates the new procedure (plug-in procedure at level α = 10%), that does not cluster all items. The points not classified are depicted by grey crosses. Points circled in red correspond to erroneous labels.

Figure 2 :

 2 Figure 2: FCR (left panel) and selection frequency (right panel) as a function of the mean separation . Known mixture proportions and covariances setting with Q = 2, n = 100, d = 2, α = 0.1.

Figure 3 :

 3 Figure 3: Same as Figure 2 in the diagonal covariance setting.

Figure 4 :

 4 Figure 4: FCR (left panel) and selection frequency (right panel) as a function of the sample size n. Diagonal covariances setting with Q = 2, d = 2, = √ 2, α = 10%.

Figure 5 :

 5 Figure 5: FCR (left panel) and selection frequency (right panel) as a function of the nominal level α. Diagonal covariances setting with Q = 2, d = 2, = √ 2, n ∈ {200, 1000}.

Figure 6 :

 6 Figure 6: Same as Figure 5 with dimension Q = 3, d = 4, = 2, for an unconstrained model.

Figure 7 :

 7 Figure 7: Comparison of the clustering result with t-mixture modelling with ground truth labels on the WCBD dataset, restricted to the variables radius and texture, with and without selection. With the parametric bootstrap procedure applied at α = 5%, the FCR w.r.t. the ground truth labels is of 3% versus 14% without selection.

  (a) Variables: radius, texture (b) Variables: radius, texture, smoothness, compactness, concavity, symmetry, fractal dimension

Figure 8 :

 8 Figure 8: FCR and selection frequency as a function of the nominal level α.

)

  With the above notation, we can upper bound what is inside the brackets of FCR( C PI ) and mFCR( C PI ) as follows.

Figure 10 :

 10 Figure 10: FCR and selection frequency as a function of the nominal level α. Three-component modelQ = 3, π 1 = π 2 = π 3 = 1/3, Σ 1 = Σ 2 = Σ 3 = I 2 , µ 1 = 0, µ 2 = ( / √ 2, / √ 2), µ 3 = (0, 2 / √ 2).

Figure 11 :

 11 Figure 11: FCR and selection frequency as a function of the nominal level α. Unconstrained model with Q = 2, d = 2, = √ 2, n ∈ {200, 1000}.

Acknowledgments

This work has been supported by ANR-16-CE40-0019 (SansSouci), ANR-17-CE40-0001 (BA-SICS) and by the GDR ISIS through the "projets exploratoires" program (project TASTY). A. Marandon has been supported by a grant from Région Île-de-France ("DIM Math Innov"). We would like to thank Gilles Blanchard and Stéphane Robin for interesting discussions. We are also grateful to Eddie Aamari and Nhat Ho for their help for proving Lemma 17.

A Proof of our main result

A.1 An optimal procedure

We consider in this section the procedure that serves as an optimal procedure in our theory. For t ∈ [0, 1], let C * t = ( Z * , S * t ) be the procedure using the Bayes clustering Z * (6) and the selection rule S * t = {i ∈ {1, . . . , n} : T * i < t}. Let us consider the map t ∈ [0, 1] → mFCR(C * t ) and note that mFCR(C * t ) = mFCR * t as defined by (12). Lemma 11 below provides the key properties for this function.

Definition 3. The optimal procedure at level α is defined by C * t * (α) where t * (α) is defined by (13).

Proof. In the considered model, any mixture can be defined in terms of {f u , u ∈ U} and a discrete mixing measure G = Q q=1 π q δ φq with Q support points, as Q q=1 π q f φq = f u (x)dG(u). As shown by [START_REF] Ho | On strong identifiability and convergence rates of parameter estimation in finite mixtures[END_REF], the convergence of mixture model parameters can be measured in terms of a Wasserstein distance on the space of mixing measures. Let G 1 = Q q=1 π 1 q δ φ 1 q and G 2 = Q q=1 π 2 q δ φ 2 q be two discrete probability measures on some parameter space, which is equipped with metric . . The Wasserstein distance of order 1 between G 1 and G 2 is given by

where the infimum is over all couplings (p q,l ) 1≤q,l≤Q ∈ [0, 1] Q×Q such that l p q,l = π 1 q and q p q,l = π 2 l . Let G * , Ĝn denote the true mixing measure and the mixing measure that corresponds to the restricted MLE considered here, respectively. Theorem 4.2. in [START_REF] Ho | On strong identifiability and convergence rates of parameter estimation in finite mixtures[END_REF] implies that, with the notation of [START_REF] Ho | On strong identifiability and convergence rates of parameter estimation in finite mixtures[END_REF], for any n ≥ ( √ C 1 /c)δ n , and δ n ≤ C log n/n, we have

We apply this relation for n = max((

In that case, we have still n of order log n/n and the upper-bound is at most 1/n. On the other hand, if we have a convergence rate in terms of W 1 , then we have convergence of the mixture model parameters in terms of . at the same rate, see Lemma 17. This concludes the proof.

Lemma 17. Let G n = Q q=1 π n q δ φ n q be a sequence of discrete probability measures on U, and let G * , W 1 be defined as in the proof of Proposition 16. There exists a constant C only depending on

Proof. In what follows, we let {p n q,l } denote the corresponding probabilities of the optimal coupling for the pair (G n , G * ). We start by showing that (φ n q ) q → (φ * q ) q in . up to a permutation of the labels. Let σ n the permutation of the labels such that φ n q -φ * l ≥ φ n σ n (l) -φ * l for all q, l ∈ {1, ..., Q}. Then, by definition,

It follows that each φ n σ n (l) -φ * l must converge to zero. Since (φ n q ) q → (φ * q ) q up to a permutation of the labels, without loss of generality we can assume that φ n q → φ * q for all q. Let ∆φ n q := φ n q -φ * q and ∆π n

It follows from the convergence of φ n that for q = l, φ n q -φ * l ≥ C/2 for sufficiently large n. Thus,

We deduce that q =l p n ql → 0. As a result, p n qq = π * ql =q p n lq → π * q , and so, p n qq ≥ (1/2)π * min := min l π * l for sufficiently large n. On the other hand, q =l p n ql = q π n q -p n qq =

E Further experiments