F Chazal

P Massart

B Michel

Rates of convergence for robust geometric inference

Distances to compact sets are widely used in the field of Topological Data Analysis for inferring geometric and topological features from point clouds. In this context, the distance to a probability measure (DTM) has been introduced by Chazal et al. (2011b) as a robust alternative to the distance a compact set. In practice, the DTM can be estimated by its empirical counterpart, that is the distance to the empirical measure (DTEM). In this paper we give a tight control of the deviation of the DTEM. Our analysis relies on a local analysis of empirical processes. In particular, we show that the rates of convergence of the DTEM directly depends on the regularity at zero of a particular quantile function which contains some local information about the geometry of the support. This quantile function is the relevant quantity to describe precisely how difficult is a geometric inference problem. Several numerical experiments illustrate the convergence of the DTEM and also confirm that our bounds are tight.

Introduction and motivation

The last decades have seen an explosion in the amount of available data in almost all domains of science, industry, economy and even everyday life. These data, often coming as point clouds embedded in Euclidean spaces, usually lie close to some lower dimensional geometric structures (e.g. manifold, stratified space,...) reflecting properties of the system from which they have been generated. Inferring the topological and geometric features of such multivariate data has recently attracted a lot of interest in both statistical and computational topology communities.

Considering point cloud data as independent observations of some common probability distribution P in R d , many statistical methods have been proposed to infer the geometric features of the support of P such as principal curves and surfaces [START_REF] Hastie | Principal curves[END_REF], multiscale geometric analysis [START_REF] Arias-Castro | Adaptive multiscale detection of filamentary structures in a background of uniform random points[END_REF], density-based approaches [START_REF] Genovese | On the path density of a gradient field[END_REF] or support estimation, to name a few. Although they come with statistical guarantees these methods usually do not provide geometric guarantees on the estimated features.

On another hand, with the emergence of Topological Data Analysis [START_REF] Carlsson | Topology and data[END_REF], purely geometric methods have been proposed to infer the geometry of compact subsets of R d . These methods aims at recovering precise geometric information of a given shape -see, e.g. Chazal et al. (2009a,b); [START_REF] Chazal | Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees[END_REF]; [START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF]. Although these methods come with strong topological and geometric guarantees they usually rely on sampling assumptions that do not apply in statistical settings. In particular, these methods can be very sensitive to outliers. Indeed, they generally rely on the study of the sublevel sets of distance functions to compact sets. In practice only a sample drawn on, or close, to a geometric shape is known and thus only a distance to the data can be computed. The sup norm between the distance to the data and the distance to the underlying shape being exactly the Hausdorff distance between the data and the shape, we see that the statistical analysis of standards TDA methods boils down to the problem of support estimation in Hausdorff metric. This last problem has been the subject of much study in statistics (see for instance [START_REF] Cuevas | On boundary estimation[END_REF][START_REF] Devroye | Detection of abnormal behavior via nonparametric estimation of the support[END_REF][START_REF] Singh | Adaptive hausdorff estimation of density level sets[END_REF]. Being strongly dependent of the estimation of the support in Hausdorff metric, it is now clear why standard TDA methods may be very sensitive to outliers.

To provide a more robust approach of TDA, a notion of distance function to a measure (DTM) in R d has been introduced by [START_REF] Chazal | Geometric inference for probability measures[END_REF] as a robust alternative to the classical distance to compact sets. Given a probability distribution P in R d and a real parameter 0 ≤ u ≤ 1, [START_REF] Chazal | Geometric inference for probability measures[END_REF] generalize the notion of distance to the support of P by the function δ P,u : x ∈ R d → inf{t > 0 ; P ( B(x, t)) ≥ u}

(1)

where B(x, t) is the closed Euclidean ball of center x and radius t. To avoid issues due to discontinuities of the map P → δ P,u , the distance to measure (DTM) function with parameter m ∈ [0, 1] and power r ≥ 1 is defined by

d P,m,r (x) : x ∈ R d → 1 m m 0 δ r P,u (x)du 1/r . ( 2
)
It was shown in [START_REF] Chazal | Geometric inference for probability measures[END_REF] that the DTM shares many properties with classical distance functions that make it well-adapted for geometric inference purposes. First, it is stable with respect to perturbations of P in the Wasserstein metric (see Theorem 1 in the next section). This property implies that the DTM associated to close distributions in the Wasserstein metric have close sublevel sets. Moreover, when r = 2, the function d 2 P,m,2 is semiconcave ensuring strong regularity properties on the geometry of its sublevel sets. Using these properties, [START_REF] Chazal | Geometric inference for probability measures[END_REF] (Section 4) show that, under general assumptions, if P is a probability distribution approximating P , then the sublevel sets of d P ,m,2 provide a topologically correct approximation of the support of P . The introduction of DTM has motivated further works and applications in various directions such as topological data analysis Buchet et al. (2015a), GPS traces analysis Chazal et al. (2011a), density estimation [START_REF] Biau | A weighted k-nearest neighbor density estimate for geometric inference[END_REF], deconvolution [START_REF] Caillerie | Deconvolution for the Wasserstein metric and geometric inference[END_REF] or clustering [START_REF] Chazal | Persistence-based clustering in riemannian manifolds[END_REF] just to name a few. Approximations, generalizations and variants of the DTM have also been recently considered in [START_REF] Buchet | Efficient and robust persistent homology for measures[END_REF]; [START_REF] Guibas | Witnessed k-distance[END_REF]; [START_REF] Phillips | Geometric inference on kernel density estimates[END_REF].

In practice, the measure P is usually only known through a finite set of observations X n = {X 1 , . . . , X n } sampled from P , raising the question of the approximation of the DTM. A natural idea to estimate the DTM from X n is to plug the empirical measure P n instead of P in the definition of the DTM. This "plug-in strategy" corresponds to computing the distance to the empirical measure (DTEM). It can be applied with other estimators of the measure P , for instance in [START_REF] Caillerie | Deconvolution for the Wasserstein metric and geometric inference[END_REF] it was proposed to plug a deconvolved measure into the DTM.

For m = k n , the DTEM satisfies

d r Pn,k/n,r (x) := 1 k k j=1 x -X n r (j) ,
where x-X n (j) denotes the distance between x and its j-th neighbor in {X 1 , . . . , X n }. This quantity can be easily computed in practice since it only requires the distances between x and the sample points.

Let us introduce

∆ n,m,r (x) := d r Pn,m,r (x)d r P,m,r (x)

(3) and ∆n,m,r (x) := d Pn,r,m (x)d P,m,r (x).

The aim of this paper is to study the deviations and the rates of convergence of ∆ n,m,r (x). The functional convergence of the DTEM has been studied recently in [START_REF] Chazal | Robust topological inference: Distance to a measure and kernel distance[END_REF] where it is shown that the parametric convergence rate in 1/ √ n is achieved under reasonable assumptions. In this paper we address the question of the convergence in probability and the rates of convergence in expectation of ∆ n,m,r (x), both from an asymptotic and non asymptotic point perspective.

The stability properties of DTM with respect to Wasserstein metrics suggests that this problem could be addressed using known results about the convergence of empirical measure P n to P under Wasserstein metrics. This last problem has been the subject of many works in the past [START_REF] Del Barrio | The central limit theorem for the Wasserstein distance between the empirical and the true distributions[END_REF][START_REF] Del Barrio | Asymptotics for L 2 functionals of the empirical quantile process, with applications to tests of fit based on weighted Wasserstein distances[END_REF][START_REF] Rachev | Mass transportation problems, volume II of Probability and its Applications[END_REF] and it is still an active field of research [START_REF] Dereich | Constructive quantization: Approximation by empirical measures[END_REF][START_REF] Fournier | On the rate of convergence in wasserstein distance of the empirical measure[END_REF]. We show in the paper that such a basic approach does not lead to optimal results and does not provide a correct understanding of the influence of the parameter m.

We adopt an alternative approach based on the observation that the DTM only depends on a push forward measure of P on the real line. Indeed, the DTM can be rewritten as follows:

d r P,m,r (x) = 1 m m 0 F -1 x,r (u)du, (4)
where F -1 x,r is the quantile function of the push forward probability measure of P by the function x -• r (see appendix A.1 for a rigorous proof). Then

∆ n,m,r (x) := 1 m m 0 F -1 x,r,n (u) -F -1 x,r (u) du. ( 5
)
where F x,r,n is the empirical distribution function of the observed distances (to the power r): x -X 1 r , . . . , x -X n r . We study the convergence of ∆ n,m,r (x) to zero with both an asymptotic and non asymptotic points of view. An asymptotic approach means that we take k = k n := mn for some fixed m and we study the mean rate of convergence to zero of ∆ n, kn n ,r (x). A non asymptotic approach means that n is fixed and then the problem is to get a tight expectation bound on ∆ n, k n ,r (x). In particular, we are particularly interested in the situation where k n is chosen very close to zero. This situation is of primary interest since it corresponds to the realistic situation where we use the DTM to clean the support from a small proportion of outliers.

Our results rely on a local analysis of the empirical process to compute tight deviation bounds of ∆ n, k n ,r (x). More precisely, we use a sharp control of a supremum defined on the uniform empirical process. Such local analysis has been successfully applied in the literature about non asymptotic statistics, for instance [START_REF] Mammen | Smooth discrimination analysis[END_REF] obtain fast rates of convergence in classification. For a more general presentation of these ideas in model selection, see [START_REF] Massart | Concentration inequalities and model selection[END_REF] and in particular Section 1.2 in the Introduction of this monograph.

We show that the rates of convergence of ∆ n, k n ,r (x) directly depends on the regularity at zero of F -1

x,r . This quantile function appears to be the relevant quantity to describe precisely how difficult is a geometric inference problem. The second contribution of this paper is relating the regularity of the quantile function F -1

x,r to the geometry of the support, establishing a link between the complexity of the geometry problem and a purely probabilistic quantity.

Rates of convergence derived from stability results of the DTM are presented in Section 2. Our main results, the deviations bounds and the rates of convergence of ∆ n, k n ,r (x) derived from the local analysis, are given in Section 3. These results are given in term of the regularity if the quantile function

F -1
x,r . Generally speaking, it is not easy to determine what is the regularity of the quantile function F -1

x,r

given a distribution P and an observation point x ∈ R d . Indeed, it depends on the shape of the support of P , on the way the measure P is distributed on its support and on the position of x with regards to the support of P . This is why, in the results given in Section 3, the assumptions are made directly on the quantile functions F -1

x . Section 4 is then devoted to the geometric interpretation of these results and their assumptions. In Section 5, several numerical experiments illustrate the convergence of the DTEM and also confirm that our bounds are sharp. Proofs and background about empirical processes and quantiles can be found in the appendices.

Notation. Let a ∧ b and a ∨ b denotes the minimum and the maximum between two real numbers a and b. The Euclidean norm on R d is • . The open Euclidean ball of center x and radius t is denoted by B(x, t). For some point x and a compact set K in R d , the distance between x and K is defined by Kx := inf y∈K yx . The Hausdorff distance between two compact sets K and K is denoted by Haus (K, K ). A probability distribution on R defined by a distribution function F is denoted by dF . The quantile function F -1 of dF is defined by

F -1 (u) := inf{t ∈ R , F (t) ≥ u}, 0 < u < 1.
By monotonicity, the quantile function F -1 can be extended in 0 and at 1 by setting F -1 (0) = inf{t ∈ R , F (t) > 0}, and F -1 (1) = sup{t ∈ R , F (t) < 1}. Finally, for two positive sequences (a n ) and (b n ), we use the standard notation a n b n if there exists a positive constant C such that a n ≤ Cb n .

2 Rates of convergence derived from the DTM stability

The DTM satisfies several stability properties for the Wasserstein metrics. The aim of this section is to derive rates of convergence of the DTEM from stability results of the DTM together with known results about the convergence of the empirical measure under Wasserstein metrics.

Let us first remind the definition of the Wasserstein metrics in R d . For r ≥ 1, the Wasserstein distance W r between two probability measures P and P on R d is given by W r (P, P ) = inf

π∈Π(P, P ) R d ×R d
xy r π(dx, dy)

1 r
, where Π(P, P ) is the set of probability measures on R d × R d with marginal distributions P and P , see for instance [START_REF] Rachev | Mass transportation problems, volume II of Probability and its Applications[END_REF] or [START_REF] Villani | Optimal Transport: Old and New[END_REF].

The stability of the DTM with respect to the Wasserstein distance W r is given by the following theorem.

Theorem 1 [START_REF] Chazal | Geometric inference for probability measures[END_REF]). Let P and P be two probability measures on R d . For any r ≥ 1 and any m ∈ (0, 1) we have d P,m,rd P ,m,r ∞ ≤ m -1 r W r (P, P ).

Notice that [START_REF] Chazal | Geometric inference for probability measures[END_REF] prove this theorem for r = 2, but the proof for any r ≥ 1 is exactly the same.

We now give the pointwise stability of the DTM with respect to the Kantorovich distance W 1 between push forward measures on R. This result easily derives from the expression (4) of the DTM given in Introduction, a rigorous proof is given in Appendix A.1.

Proposition 1. For some point x in R d and some real number r ≥ 1, let dF x,r and d Fx,r be the push-forward measures by the function y → xy r of two probability measures P and P defined on R d . Then, for any x ∈ R d :

d r P,m,r (x) -d r P ,m,r (x) ≤ 1 m W 1 (dF x,r , d Fx,r ) .
Convergence results for ∆ n,m,r can be directly derived from the stability results given in Theorem 1 and Proposition 1. For instance, it can be easily checked that, for any x ∈ R d , W 1 (dF x,r , dF n,x ) tends to zero almost surely (see for instance the Introduction Section of del [START_REF] Del Barrio | The central limit theorem for the Wasserstein distance between the empirical and the true distributions[END_REF]. This together with Proposition 1 gives the almost surely pointwise convergence to zero of ∆ n,m,r (x).

Regarding the convergence in expectation, using Theorem 1 in R d for d > r/2, we deduce from [START_REF] Fournier | On the rate of convergence in wasserstein distance of the empirical measure[END_REF] or from [START_REF] Dereich | Constructive quantization: Approximation by empirical measures[END_REF] that

E ∆ n, k n ,r ∞ ≤ k n -1/r EW r (P, P n ) ≤ k n -1/r [EW r r (P, P n )] 1/r ≤ C k n -1/r n -1/d .
Nevertheless this upper bound is not sharp: assume that k n := mn for some fixed constant m ∈ (0, 1) then the rate is of the order of n -1/d . We show below that the parametric rate 1/ √ n can be obtained by considering the alternative stability result given in Proposition 1. In the one-dimensional case, a direct application of Fuibini's theorem gives that (see for instance Theorem 3.2 in [START_REF] Bobkov | One-dimensional empirical measures, order statistics and Kantorovich transport distances[END_REF])

√ nE [W 1 (dF x,r , dF x,r,n )] ≤ ∞ 0 F x,r (t)(1 -F x,r (t))dt =: J 1 (dF x,r ), (6)
where dF x,r and dF x,r,n are the push forward probability measures of P and P n by the function x-• r . Note that [START_REF] Bobkov | One-dimensional empirical measures, order statistics and Kantorovich transport distances[END_REF] have completely characterized the convergence of EW 1 (µ, µ n ) in the one-dimensional case, in term of J 1 (µ) for µ a probability measure on the real line and µ n its empirical counterpart. From Proposition 1 and the upper bound (6) we derive that

E ∆ n, k n ,r (x) ≤ n k J 1 (dF x,r ) √ n . ( 7
)
The integral

J 1 (dF x,r ) is finite if E X -x 2r+δ < ∞ for some δ > 0.
We thus obtain a pointwise rate of convergence in 1/ √ n under reasonable moment conditions, if we take k n := mn for some fixed constant m ∈ (0, 1). However, the upper bound (7) does not allow us to describe correctly how the rate depends on the parameter m = k n . For instance, if k n is very small, the bound blows up in all cases while it should not be the case for instance with discrete measures. The reason is that the stability results are too global to provide a sharp expectation bound for small values of k n . To obtain better upper bounds on the rate of convergence of the DTEM, we will directly control the fluctuations of ∆ n, k n ,r by considering a supremum over the underlying empirical process.

Main results

We fix r ≥ 1 and we henceforth write F x for F x,r to facilitate the reading. In the same way we will use the notation F -1 x , ∆P,m , d P,m since there is no ambiguity on the power term r. Given an observation point x ∈ R d , we introduce the modulus of continuity ωx of F -1 x (possibly infinite) which is defined for any v ∈ (0, 1] by ωx (v) := sup

(u,u )∈[0,1] 2 , u-u ≤v |F -1 x (u) -F -1 x (u )|.
Note that the fact that ωx is finite is equivalent to the fact that the support of P is bounded. An extensive discussion about the relation between the sampling measure P and the modulus of continuity of F -1 x is proposed in Section 4. The function ωx being non decreasing and non negative, it has a non negative limit ωx (0 + ) at zero. In particular we do not assume here that ωx (0 + ) = 0. In other terms we do not assume that F -1

x is continue. We extend ωx at zero by taking ωx (0) = ωx (0 + ). In the following, it will be sufficient in our results to consider upper bounds on the modulus of continuity, that is a non negative function ω x on [0, 1] such that ω x (v) ≥ ω(v) for any v ∈ [0, 1]. A modulus of continuity being a non decreasing function, we will assume that such an upper bound ω x is non decreasing on [0, 1]. For technical reasons and without loss of generality, we will also assume that ω x is a continuous function, which takes its values in [ω(0), ω(1)] ⊂ R+ . For such a function ω x we also introduce its invert function ω -1

x which is defined on [ω(0), ω(1)]. We extend this function to R + by taking ω -1

x (t) = 0 for any t ∈ [0, ω(0)] and ω -1 x (t) = 1 for any t ≥ ω(1). In particular, ω -1 x (ω x (u)) = u for any u ∈ [0, 1].

In this section, we show that the rate of convergence of

∆ n, k n (x) is of the order of ωx( k n ) √ k .

Local analysis of the distance to the empirical measure in the bounded case

We first consider the behavior of the distance to the empirical measure when the observations X 1 , . . . , X n are sampled from a distribution P with compact support in R d . Let F -1

x be the quantile function of x -X 1 r and let ∆ n, k n be defined by (3).

Theorem 2. Let x be a fixed observation point in R d . Assume that ω x : [0, 1] → R + is an upper bound on the modulus of continuity of F -1

x . Assume moreover that ω x is an increasing and continuous function on [0, 1].

For any

λ > 0, if k < n 2 then P |∆ n, k n (x)| ≥ λ 2 ≤ exp - 1 64 kλ 2 F -1 x k n -F -1 x (0) 2 + exp - 3 16 kλ F -1 x k n -F -1 x (0) + exp   - n 2 4k    ω -1 x   k 1/4 λ 8 ω x 2 √ k n      2    + exp   - 3n 8 ω -1 x   k 1/4 λ 2 ω x 2 √ k n     + exp   - √ k 8 λ ω x 2 √ k n   + exp   - 3k 3/4 4 λ 2ω x 2 √ k n    := (λ), (8) otherwise P |∆ n, k n (x)| ≥ λ 2 ≤ exp   -2nλ 2 k n F -1 k n -F -1 (0) 2   + exp   -2n ω -1 x k √ n ω x 1 √ n λ 2 2   + exp   - k √ nω x 1 √ n λ   .
Furthermore, in all cases we have P |∆ n, k n (x)| ≥ λ = 0 for any λ > ω x (1).

2. Assume moreover that ω x (u)/u is a non increasing function, then for any k ∈ {1, . . . , n}:

E |∆ n, k n (x)| ≤ C √ k F -1 x k n -F -1 x (0) + ω x √ k n (9) ≤ 2C √ k ω x k n , ( 10
)
where C is an absolute constant.

The proof of the Theorem is based on a particular decomposition of ∆ n, k n (x), see Lemma 5 in Appendix. This decomposition allows us to consider the deviations of the empirical process rather than the deviations of the quantile process. The proof is given in Appendix A.

Let us now comment the final bound on expectation (10). This bound can be rewritten as follows:

E ∆ n, k n (x) n k 1 √ n k n ω x k n . ( 11
)
The term n k comes from the definition of the DTM, it is the renormalization by the mass proportion k n . The term 1 √ n corresponds to a classical parametric rate of convergence. The term k n is obtained thanks to a local analysis of the empirical process. More precisely, it derives from from a sharp control of the variance of a supremum over the uniform empirical process. The term ω x k n corresponds to the statistical complexity of the problem, expressed in term of the regularity of the quantile function F -1

x .

Theorem 2 can be interpreted with either an asymptotic or a non asymptotic point of view. Taking a non asymptotic approach, we consider n as fixed. A first result here is that we obtain sharp upper bounds for small values of k n . In the most favorable case where ωx (u) ∼ u, we see in ( 10) that an upper bound of the order of 1 n is reached. This is direct consequence of the local analysis we use to control the empirical process in the neighborhood of the origin. As mentioned before, assuming that k n is very small corresponds to the realistic situation where we use the DTM to clean the support from a small proportion of outliers. Now, taking an asymptotic approach, a second result of Theorem 2 is that it allows us to consider the asymptotic behavior of ∆ n, k n (x) under all possible regimes, that is for all sequences (k n ) n∈N . For instance, with the classical approach where k n is such that k n /n = m for some fixed value m ∈ (0, 1), we then obtain the parametric rate of convergence 1/ √ n, as in the asymptotic functional results given in [START_REF] Chazal | Robust topological inference: Distance to a measure and kernel distance[END_REF].

Another key fact about Theorem 2 is that the upper bound (9) depends on the regularity of F -1

x through the function

Ψ x : m → ω x (m) √ m .
Moreover, if ω(0 + ) = 0, we see that the upper bound (9) depends on the regularity of F -1 x only at 0 for n large enough. For instance, if k n is such that k n /n = m for some fixed value m ∈ (0, 1) such that

F -1 x (m) > F -1
x (0), coming back to (9), we find that for n large enough:

ω x √ k n n = ω x 1 √ n m < F -1 x (m) -F -1 x (0).
In this context, the right hand term of Inequality ( 9) is of the order of

Ψx( kn n ) √ kn where Ψ x (m) := F -1 x (m) -F -1 x (0) √ m
for any m ∈ (0, 1).

We now give additional remarks about Theorem 2.

Remark 1. If the quantile function F -1

x is η-Holder, then ω x (u) = Au η for some constant A ≥ 0 and thus we have

E |∆ n, k n (x)| 1 √ n k n η-1/2
.

Remember that Holder functions with power η > 1 are constants, we can thus assume that η ≤ 1.

Remark 2. Assuming that ω x (u)/u is a non increasing function roughly means that ω x is a concave function. Our result is thus satisfied if we can find an concave function which is an upper bound on the modulus of continuity of the quantile function. We show in Section 4.4 that it is satisfied for a large class of measures.

Remark 3. For values of k n not close to zero, the rate is consistent with the upper bound (7) deduced from the approach based on the stability results. However, Theorem 2 is more satisfactory since it describes the statistical complexity of the problem through the regularity of the quantile function.

Remark 4. The application u → u 1/r is 1/r-Holder on R + with Holder constant 1 since 1/r < 1. It yields:

| ∆n, k n ,r (x)| ≤ |∆ n, k n ,r (x)| 1/r . ( 12
)
where ∆n, k n ,r (x) is defined by (1). We deduce an expectation bound on ∆n, k n ,r (x) from Jensen's Inequality and Inequality (12):

E | ∆n, k n ,r (x)| 1 √ n k n -1/2 ω x k n 1/r .
Remark 5. As already mentioned before, to prove Theorem 2, we consider the deviations of the empirical process rather than the deviations of the quantile process. Indeed, the more direct approach that consists in directly controlling the deviations of the quantile process gives slower rates. More precisely, using Proposition 7 given in Appendix borrowed from [START_REF] Shorack | Empirical processes with applications to statistics[END_REF], it can be shown that

E |∆ n, k n (x)| ω x √ k n . For instance, if ω x (u) = Au η , we obtain E |∆ n, k n ,r (x)| √ k n η
which is slower than the rates given in Remark 1.

To complete the results of Theorem 2, we give below a lower bound using Le Cam's lemma (see Lemma 8 in Appendix). Let ω be a continuous and increasing function on [0, 1] and let x ∈ R d . We introduce that class of probability measures:

P ω := P is a probability measure on R d such that ω(u) ≥ ωx (u) for any u ∈ [0, 1] .
In the previous definition, the function ω is as before the modulus of continuity of the quantile function of the distribution of the push-forward measure of P by the function y → yx r .

Proposition 2. Assume that there exists P ∈ P ω , c > 0 and ū ∈ (0, 1), such that

c F -1 x (u) -F -1 x (0) ≥ ω(u) for any u ∈ (0, ū]. (13)
Then, there exits a constant C which only depends on c, such that for any k ≤ ūn.

sup

P ∈Pω E |∆ n, k n ,r (x)| ≥ inf dn(x) sup P ∈Pω E dr n (x) -d r P,m,r (x) ≥ C n k 1 n ω k -1 n ,
where the infimum is than over all the estimator dn (x) of d P,m,r (x) defined from a sample X 1 , . . . , X n of distribution P .

The Assumption ( 13) is not very strong. It means that ω is not a too large upper bound on the modulii of continuity of the quantile functions. More precisely, it says that there exists a distribution P ∈ P ω for which ω can be comparable to the modulus of continuity of the quantile functions F -1

x in the neighborhood of the origin.

Note that this lower bound matches with the upper bound of Theorem 2 when k is very small since it is of the order of ω k n . Providing the correct lower bound for all values of k is not obvious. As far as we know there is no standard method in the literature for computing lower bounds for this kind of functional and we consider that this issue is beyond the scope of this paper.

Local analysis of the distance to the empirical measure in the unbounded case

The previous results provide a description of the fluctuations and mean rates of convergence of the empirical distance to measure. However, when the support of P is not bounded, the quantile function F -1 x tends to infinity at 1 and the modulus of continuity of F -1 x is not finite. In such a situation, Theorem 2 can not be applied. We now propose a second result about the fluctuations of the DTEM, under weaker assumptions on the regularity of F -1

x . The following result shows that under a weak moment assumption, the rate of convergence is the same as for the bounded case, up to a term decreasing exponentially fast to zero. Theorem 3. Let m ∈ (0, 1) and some observation point x ∈ R d . Assume that ω x, m is an upper bound of the modulus of continuity of F -1

x on (0, m]:

for any u, u ∈ [0, m] 2 , |F -1 x (u) -F -1 x (u )| ≤ ω x, m(|u -u |). ( 14
)
Assume moreover that ω x, m is increasing and continuous function on [0, m]. Then, for any k < n 1 2 ∧ m and any λ > 0:

P |∆ n, k n (x)| ≥ λ 2 ≤ (λ) + exp - √ k 8 exp n 2 4k m - k n 2 λ + exp - 3 8 exp n 2 8k m - k n 2 k 3 8 λ 2 + 2 exp - n 2 2k m - k n 2 ∧    n k-1 2 1 -F λ 6 k n n-k+1    (15)
where (λ) is the upper bound given in Theorem 2, with ω x replaced by ω x, m. Assume moreover that ω x, m(u)/u is a non increasing function and that P has a moment of order r. Then

E ∆ n, k n (x) ≤ C √ n k n -1/2 F -1 x k n -F -1 x (0) + ω x, m √ k n +C x,r, m√ k exp - n 2 4k m - k n 2 .
where C is an absolute constant and C x,r, m only depends on the quantity E Xx r and on m.

As for the bounded case, if ω(0

+ ) = 0 and if F -1 x (m) > F -1 x (0)
, then the rate of convergence is still of the order of Ψx(m) √ n . Note that this result is interesting even when the measure P is supported on a compact set. Indeed, assume that the quantile function F -1

x is not continuous, then ω-1 x (0) > 0. However, if F -1

x is smooth in the neighborhood of zero, for m small enough the assumption ( 14) may be satisfied with a function ω x, m which can be very small in the neighborhood of zero. Theorem 3 may provide better bounds in this context than those given by Theorem 2. This fact also confirms that the deviations of the DTEM mainly relies on the local regularity of the quantile function F -1

x at the origin rather then on its global regularity.

Convergence of the distance to the empirical measure for the sup norm

The previous results address the pointwise fluctuations of the DTEM. We now consider the same problem for the sup norm metric on a compact domain D of R d . Let N (D, t) be the covering number of D, that is the smallest number of balls B(x i , t) with x i ∈ D, such that i B(x i , t) ⊃ D. Since the domain D is compact, there exists two positive constants c and ν ≤ d such that for any t > 0 :

N (D, t) ≤ ct -ν ∨ 1.
We assume that there exists a function ω D : (0, 1] → R + which uniformly upper bounds the modulus of continuity of the quantile functions (F -1

x ) x∈D : for any u, u ∈ (0, 1] 2 and for any x ∈ D:

|F -1 x (u) -F -1 x (u )| ≤ ω D (|u -u |).
We also assume as before that ω D is an increasing and continuous function on [0, 1].

Theorem 4. Under the previous assumptions, for any k

≤ n 2 , E sup x∈D |∆ n, k n (x)| ≤ C √ n k n -1/2 F -1 x k n -F -1 x (0) log +   k F -1 x k n -F -1 x (0) 2 ν+5   + C √ n k n -1/2 ω D √ k n log +     √ k ω D √ k n   ν-1   ≤ C √ n k n -1/2 ω D √ k n log +    k ν+5 F -1 x √ k n -F -1 x (0) 2ν+5 ∧ ω D √ k n ν-1   
where log + (u) = (log u) ∨ 1 for any u ∈ R + . The constant C is an absolute constant if r = 1 otherwise it depends on r and on the Hausdorff distance between D and the support of P .

This bound is deduced from a deviation bound on sup x∈D |∆ n, k n (x)| which is given in the proof. Up to a logarithm term, the rate is the same as for the pointwise convergence. As for the pointwise convergence, this result could be easily extended to the case of non compactly supported measures.

4 The geometric information carried by the quantile function F -1

x

The upper bounds we obtain in the previous section directly depend on the regularity of F -1

x . We now give some insights about how the geometry of the support of the sampling measure in R d impacts the quantile function F -1

x .

Compact support and modulus of continuity of the quantile function

A geometric characterization of the existence of ωx on [0, 1] can be given in term of the support of the sampling measure P . The following Lemma is borrowed and adapted from [START_REF] Bobkov | One-dimensional empirical measures, order statistics and Kantorovich transport distances[END_REF]:

Lemma 1. Given the sampling measure P in R d and an observation point x ∈ R d , the following properties are equivalent:

1. the modulus of continuity of the quantile function F -1 x satisfies ωx (u) < ∞ for any u ≤ 1 ;

2. the push-forward distribution of P by the function x -• r is compactly supported ; 3. P is compactly supported.

In particular, if P is compactly supported, we can always take as an upper bound on ωx the constant function ω x = Haus ({x}, K). Of course this is not a very relevant choice to describe the rate of convergence of the DTEM.

Connexity of the support and modulus of continuity of the quantile function

While discontinuity of the distribution function corresponds to atoms, discontinuity points of the quantile function corresponds to area with empty mass in R d (see the right picture of Figure 1). The fact that ωx (0 + ) = 0 is directly related to the connexity of the support of the distribution dF x . Indeed, it is equivalent to assuming that the support of dF x is a closed interval in R + , see for instance Proposition A.7 in [START_REF] Bobkov | One-dimensional empirical measures, order statistics and Kantorovich transport distances[END_REF].

In the most favorable situations where the support of P is a connected set, then ωx (0 + ) = 0 and the faster ωx tends to 0 at 0, the better the rate we obtain. However, for some point x ∈ R d , it is also possible for the support of dF x to be an interval even when the support of P is not a connected set of

x t K F x (t) F -1 x (u) u x t K F x (t) F -1 x (u)
u Figure 1: Left: one situation where the support of P is not a connected set whereas the support of dF x is (for r = 1). The quantile function F -1 x is continuous. Right: one situation where the support of dF x is is not a connected set ; the quantile functionF -1

x is not continous.

R d (see the left picture of Figure 1). In the other case, when the support of dF x is not a connected set, the term ωx (0) roughly corresponds to the maximum distance between two consecutive intervals of the support of dF x (see the right picture of Figure 1). Our results can still be applied in these situations but the upper bounds we obtain in this case are larger because ω x ( k n ) can not be smaller than ωx (0).

Uniform modulus of continuity of F -1

x,r versus local continuity of F -1

x,r at the origin Though stronger than continuity, a natural regularity assumption on F -1

x,r is assuming that this last is also concave:

Lemma 2. If F -1
x is concave then we can take ω x = F -1

x -F -1 x (0). In particular, if x is in the support of P then we can take ω x = F -1

x .

If we take r = 1, in many simple situations we note that the cumulative distribution function F x,1 roughly behaves as a power function t , where is the dimension of the support. In this context, the quantile function F -1

x,1 roughly behaves as a power function in u 1/ . We then have that

F -1 x,r (u) = F -1 x,1 (u) r behaves as u r
. This is for instance the case for (a, b) standard measures, as shown in the next section. These considerations suggest that if r/ < 1, in many situations the quantile function is concave and then ω x is of the order of F -1

x -F -1 x (0). This means that the upper bound on E∆ P,n, k n is of the order of 1 √ n Ψ x ( k n ). More generally, as noticed in the comments following Theorem 2, the term

F -1 x ( k n ) -F -1
x (0) is the dominating term in the upper bound (9). We may check with the numerical experiments of Section 5 that the function Ψ x yet captures the correct monotonicity of E∆ P,n, k n as a function of k n .

The case of (a, b) standard measures

The intrinsic dimensionality of a given measure in R d can be quantified by the so-called (a, b)standard assumption which assumes that there exists a > 0, ρ 0 > 0 and b > 0 such that ∀x ∈ K, ∀r ∈ (0, ρ 0 ), P (B(x, ρ)) ≥ a ρ b , where K is the support of P . This assumption is popular in the literature about set estimation (see for instance [START_REF] Cuevas | Set estimation: another bridge between statistics and geometry[END_REF][START_REF] Cuevas | On boundary estimation[END_REF]. More recently, it has also been in used in Chazal et al. (2014b,c); [START_REF] Fasy | Confidence sets for persistence diagrams[END_REF] for statistical analysis inTopological Data Analysis. Since K is compact, by reducing the constant a to a smaller constant a if necessary, we easily check that this assumption (4.4) is equivalent to

∀x ∈ K, P (B(x, ρ)) ≥ 1 ∧ aρ b .
We now give a control on the two key terms ω x and F -1

x (u) -F -1 x (0) which are involved in the bounds on expectations of Section 3.

Lemma 3. Let P be a probability measure on R d which is (a, b) standard on its support K. Then, for any u ∈ [0, 1],

F -1 x (u) -F -1 x (0) ≤ r u a 1/b u a 1/b + K -x r-1
, where r is the power parameter in the definition (2) of the DTM. Assume moreover that K is a connected set of R d . Then, for any h ∈ (0, 1) we have

ωx (h) ≤ r h a 1/b Haus ({x}, K) r-1 . x K π K (x 0 ) √ t √ t -d K (x 0 ) + x F -1 x (t) 1/r F -1 x (t + h) 1/r K x 1 α(h)
x 2

x 3

Figure 2: About the modulus of continuity of the quantile function F -1 x in the case of (a, b)standard measures in R d .

Proof. We have (see the left picture of Figure 2)

F x (t) = P B x, t 1/r ≥ P B π K (x), t 1/r -K -x + where π K (x) is a point of R d which satisfies K-x = π K (x)-x . Then F x (t) ≥ a t 1/r -K -x + b
and we find that

F -1 x (u) ≤ u a 1/b + K -x r
. Next, we have F -1 x (0) = Kx r and the first point derives by upper bounding the derivatives of v → [v + Kx ] r .

We now assume that K is a connected set. Let (u, h) ∈ (0, 1) 2 such that u + h ≤ 1 and F -1

x (u) > F -1 x (0). We can also assume that

F -1 x (u + h) > F -1 x (u). Let α(h) = [F -1 x (u + h)] 1/r - [F -1
x (u)] 1/r (see the right picture of Figure 2). By definition of a quantile, there exists a point

x 1 ∈ K ∩ B x, [F -1 x (u + h)] 1/r \ B x, [F -1 x (u)] 1/r . If F -1
x (u) > 0 then for the same reason there exists a point

x 2 ∈ K ∩ B x, [F -1 x (u)] 1/r . If F -1 x (u) = 0 then x ∈ K and we take x 2 = x. Next, since K is a connected set, there exists a point x 3 ∈ K ∩ B x, [F -1 x (t)] 1/r + α 2 .
The measure P being (a, b)-standard, we find that

h ≥ P B x 3 , α(h) 2 ≥ a α(h) 2 b .
Then,

[F -1 x (t + h)] 1/r -[F -1 x (t)] 1/r ≤ 2 a 1/b h 1/b , and thus F -1 x (t + h) -F -1 x (t) ≤ ra -1/b F -1 x (t + h) r-1 h 1/b ,
which proves the Lemma. 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 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 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 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 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 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 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 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 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 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 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 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 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 q q q q q q q q q q q q q q q q q q q q qq 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 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 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 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 q q q q q q q q q q q q q q q q q q q -2 -1 0 1 2

One sample of 500 observations in R

x 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 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 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 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 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 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 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 qq 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 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 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 q q q q qq 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 q qq 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 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 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 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 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 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 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 q q q q Noiseless model Clutter noise model

Gaussian noise model

Observation point

One sample for the Clutter noise model 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 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 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 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 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 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 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 q q q q q q q q q q q Observation point

Numerical experiments

In this section, we illustrate with numerical experiments that the expectation bounds given on ∆ n, k n in Section 3 are sharp. In particular, we check that the function Ψ x has the same monotonicity as the function m → E∆ n, k n (x).

We consider four different geometric shapes in R, R 2 and R 3 , for which a visualization is possible: see Figures 3 and4.

• Segment Experiment in R. The shape K is the segment [0, 1] in R.

• 2-d shape Experiment in R 2 . A closed curve has been drawn at hand in R 2 . It has been next approximated by a polygonal curve with a high precision. The shape K is the compact set delimited by the polygon curve.

• Fish Experiment: a 2-d surface in R 3 . The shape K is the discrete set defined by a point cloud of 216979 points approximating a 2-d surface representing a fish. This dataset is provided courtesy of CNR-IMATI by the AIM@SHAPE-VISIONAIR Shape Repository.

• Tangle Cube Experiment in R 3 . The shape K is the tangle cube, that is the 3-d manifold defined as the set of points

(x 1 , x 2 , x 3 ) ∈ R 3 such that x 4 1 -5x 2 2 + x 4 2 -5x 2 2 + x 4 3 -5x 2 3 + 10 ≤ 0.
For each shape, we consider three generative models. These models are standard in support estimation and geometric inference, see [START_REF] Genovese | Manifold estimation and singular deconvolution under hausdorff loss[END_REF] for instance.

• Noiseless model: X 1 , . . . X n are sampled from the uniform probability distribution P uni on K.

• Clutter noise model: X 1 , . . . X n are sampled from the mixture distribution

P cl = πU +(1-π)P
where U is the uniform measure on a box B which contains K and where π is a proportion parameter. • Gaussian convolution model: X 1 , . . . X n are sampled from the distribution P g = P Φ(0, σI d ) where Φ(0, σ) is the centered isotropic multivariate Gaussian distribution on R d with covariance matrix σI d . We take σ = 0.5 in all the experiments.

We use the same notation P for any of the probability distributions P uni , P cl or P g . An observation point x is fixed for each experiment. For each experiment and each generative model, from a very large sample drawn from P we compute very accurate estimations of the quantile functions F -1 x,r and of the DTM d P ,m,t (x). Next, we simulate n-samples from P and we compute the DTEM for each sample. We take n = 500 for the two first experiments and n = 2000 for the two others. The trials are all repeated 100 times and finally we compute some approximations of the error E∆ n, k n ,r (x) with a standard Monte-Carlo procedure, for all the sampling measures P . The DTMs and the DTEMs are computed for the powers r = 1, r = 2 , and also for r = 3 for the Tangle Cube Experiment. We also compute the function m → Ψ(m). The simulations have been performed using R software (R Core Team, 2014) and we have used the packages FNN, rgl, grImport and sp.

Results

The figures 5 to 8 give the results of the four experiments with the three generative models. The top graphics of Figures 5 to 8 represent the quantiles functions F -1

x,r in each case. For the noiseless models, the behavior of F -1

x,r at the origin is directly related to the power r and to the intrinsic dimension of the shape. For r = 1 , the quantile is linear for the the segment, it is roughly in √ m for the 2-d shape and for the Fish Experiment. It is of order of m 1/3 for the Tangle Cube. We observe that F -1 x,r is roughly linear with r = 2 for the 2-d shape and the Fish shape, and with r = 3 for the Tangle Cube.

The quantile functions of the noise models in the four cases start from zero since the observation is always taken inside the supports of P cl and P g . A regularity break for the quantile function of the clutter noise model can be observed in the neighborhood of m = P (B(x, Kx r )). The quantile functions for the Gaussian noise is always smoother.

The main point of these experiments is that, in all cases, the function m → Ψ(m) show the same monotonicity as the expected error studied in the paper : m → E∆ n,m,r (x). These results confirm that the function Ψ provides a correct description of E∆ n,m,r .

We also observe that the function : m → E∆ n,m,r does not have one typical shape : it can be an increasing curve, a decreasing curve or even an U-shape curve. Indeed, the monotonicity depend on many factors among with the intrinsic dimension of the shape, its geometry, the presence of noise and the power coefficient r.

Conclusion

When the data is corrupted by noise, the distance to measure is one clue for performing robust geometric inference. For instance it can be used for support estimation and for topological data analysis using persistence diagrams, as proposed in [START_REF] Chazal | Robust topological inference: Distance to a measure and kernel distance[END_REF]. In practice, a "plug-in" approach is adopted by replacing the measure by its empirical counterpart in the definition of the DTM. The main result of this paper is providing sharp non asymptotic bounds on the deviations of the DTEM.

The DTM has been recently extended to the context of metric spaces in [START_REF] Buchet | Efficient and robust persistent homology for measures[END_REF]. For the sake of simplicity, we have assumed that P is a probability measure in R d . However, all the results of the paper can be easily adapted to more general metric spaces by considering the push forward distribution of P by d(x, •) r where d is the metric in the sampling space.

This paper is a step toward a complete theory about robust geometric inference. Our results give preliminary insights about how tuning the parameter m in the DTEM, which is a difficult question. The experiments proposed in Section 5 show that the term E∆ n,m,r (x) does not have a typical monotonic behavior with regard to m and thus classical model selection methods can be hardly applied to this problem. We intent to study this non standard model selection problem in future works.

A Proofs

A.1 Preliminary results for the DTM

Rewritting the DTM in term of quantile function

Let P a probability distribution in R d , x ∈ R d and r ≥ 1. Let F x,r be the distribution function of the random variable x -X r , where the distribution of the random variable X is P . The preliminary distance function to P δ P,u : x ∈ R d → inf{t > 0 ; P ( B(x, t)) ≥ u} can be rewritten in term of the quantile function F x,r :

Lemma 4. For any u ∈ (0, 1), we have δ r P,u (x) = F -1 x,r (u). In particular, δ P,u (x) = F -1

x,1 (u).

Proof. Note that for any t ∈ R + , F x,r (t) = P (B(x, t 1/r )). Next,

{t ≥ 0 ; P (B(x, t 1/r )) ≥ } = {s r ; s ≥ 0 , P (B(x, s)) ≥ }
and we deduce that

F -1 x,r ( ) = inf{s r ; s ≥ 0 , P (B(x, s)) ≥ } = δ r P, (x).
where we have used the continuity of s → s r for the last equality.

From Lemma 4 we directly derive the expression of the DTM in term of the quantile function F -1 x,r , as given by Equation ( 4) in the Introduction Section: Let F and F be the cdfs of two probability measures dF and d F on R. Recall that, for any p ≥ 1, and any measure µ and μ in R:

d r P,m,r (x) = 1 m m 0 F -1 x,r (
W r r (dF, d F ) = 1 0 | F -1 (u) -F -1 (u)| r du , (16)
see for instance see for instance [START_REF] Vallender | Calculation of the wasserstein distance between probability distributions on the line[END_REF]. Thus

m 0 | F -1 (u) -F -1 (u)| duldu ≤ W r 1 (F, F )
and the proof follows using Equation (4).

A decomposition of ∆ n, k n ,r . For any x ∈ R d , any r ≥ 1 we have F -1

x,n,r (0) ≥ F -1 x,r (0) ≥ 0 since F x,r is the cdf of the random distance x -X r whose support is included in R + . From Equation ( 5) and geometric considerations (see figure 9) we can rewrite ∆ n,m,r as given in the following Lemma.

Lemma 5. The quantity ∆ n, k n ,r can be rewritten as follows:

∆ n, k n ,r (x) := n k k n 0 F -1 x,n,r (u) -F -1 x,r (u) du = n k F -1 x,r ( k n )∨F -1 x,n,r ( k n ) F -1 x,r (0)
F x,r (t) ∧ k n -F x,n,r (t) ∧ k n dt. m F -1 x,n,r F -1 x,r 0 k n F -1 x,r,n (0)
F -1 x,r ( k n ) F -1 x,r,n ( k n ) F -1 x,r (0)

A.2 Proof of Theorem 2

We recall that we use the notation F for F x,r and F n for F x,n,r in the proof.

Upper bound on the fluctuations of

∆ n, k n (x)
We first check that P |∆ n, k n (x)| ≥ λ = 0 for λ ≥ ω x (1). Note that ω x (1) < ∞ because the support of P is compact. Let G n and G -1 n be the empirical uniform distribution function and the empirical uniform quantile function (see Section B). Starting from the definition (5) of the DTM and using Proposition 3 in Appendix B, we obtain that for λ ≥ 0 and k ≤ n:

P |∆ n, k n (x)| ≥ λ ≤ P   sup u∈[0, k n ] F -1 G -1 n (u) -F -1 (u) ≥ λ   ≤ P   sup u∈[0, k n ] ω x G -1 n (u) -u ≥ λ   ≤ P   sup u∈[0, k n ] G -1 n (u) -u ≥ ω -1 x (λ)   ,
and this probability is obviously zero for any λ ≥ ω x (1).

We now prove the deviation bounds starting from Lemma 5. If

F -1 ( k n ) ≤ F -1 n ( k n ), then ∆ n, k n (x) = n k F -1 ( k n ) F -1 (0) {F (t) -F n (t)} dt + n k F -1 n ( k n ) F -1 ( k n ) k n -F n (t) dt
and thus

∆ n, k n (x) ≤ n k F -1 ( k n ) F -1 (0) |F (t) -F n (t)| dt A + n k F -1 n ( k n ) F -1 ( k n ) k n -F n (t) dt 1 F -1 n ( k n )≥F -1 ( k n ) B ( 17
) If F -1 ( k n ) > F -1 n ( k n ), then ∆ n, k n (x) = n k F -1 n ( k n ) F -1 (0) {F (t) -F n (t)} dt + n k F -1 ( k n ) F -1 n ( k n ) F (t) - k n dt
and thus

∆ n, k n (x) ≤ n k F -1 n ( k n ) F -1 (0) |F (t) -F n (t)| dt + n k F -1 ( k n ) F -1 n ( k n ) k n -F (t) dt ≤ n k F -1 n ( k n ) F -1 (0) |F (t) -F n (t)| dt + n k F -1 ( k n ) F -1 n ( k n ) {F n (t) -F (t)} dt ≤ n k F -1 ( k n ) F -1 (0) |F (t) -F n (t)| dt.
In all cases, Inequality ( 17) is thus satisfied.

• Local analysis : deviation bound of ∆ n, k n (x) for k n close to zero. We now prove the deviation bound for k n < 1 2 . We first upper bound the term A in (17). According to Proposition 5 in Appendix B, for any u 0 ∈ (0, 1 2 ) and any λ > 0:

P sup u∈[0,u 0 ] |G n (u) -u| ≥ λ ≤ 2 exp - nλ 2 (1 -u 0 ) 2 2u 0 1 1 + (1-u 0 )λ 3u 0 . ( 18
)
For u 0 ≤ 1 2 and λ > 0 it yields

P sup t∈[F -1 (0),F -1 (u 0 )) |F n (t) -F (t)| ≥ λ = P sup u∈[0,u 0 ) |G n (u) -u| ≥ λ ≤ 2 exp - nλ 2 (1 -u 0 ) 2 2u 0 1 1 + (1-u 0 )λ 3u 0 ≤ 2 exp - nλ 2 (1 -u 0 ) 2 4u 0 + 2 exp - 3nλ(1 -u 0 ) 4 ,
where we have used Proposition 3 in Appendix B for the first equality, (18) for the second inequality, and that for any u, v > 0, exp(-u/(1 + v) ≤ exp(-u/2) + exp(-u/(2v)). The term A can be upper bounded by controlling the supremum of

|F n -F | over F -1 (0), F -1 k n . If k n < 1 2 , it yields P (A ≥ λ) ≤ P   n k F -1 k n -F -1 (0) sup t∈[F -1 (0),F -1 ( k n )) |F n (t) -F (t)| ≥ λ   ≤ 2 exp   - nλ 2 (1 -k n ) 2 4 k n k n F -1 k n -F -1 (0) 2   + 2 exp - 3nλ(1 -k n ) 4 k n F -1 k n -F -1 (0) ≤ 2 exp   - n 16 k n λ F -1 k n -F -1 (0) 2   + 2 exp - 3n 8 k n λ F -1 k n -F -1 (0) (19)
We now upper bound B. We have

B ≤ n k F -1 n k n -F -1 k n k n -F n F -1 k n 1 F -1 n ( k n )≥F -1 ( k n ) . (20)
Thus, according to Proposition 3 in Appendix B,

P (B ≥ λ) ≤ P n k F -1 G -1 n k n -F -1 k n k n -G n k n 1 G -1 n ( k n )≥ k n ≥ λ ≤ P (B 0 ≥ λ)
where

B 0 := n k ω x G -1 n k n - k n n k k n -G n k n .
Let θ ∈ (0, 1) to be chosen further. We have

2B 0 ≤ θ n k ω x G -1 n k n - k n 2 B 2 1 + 1 θ n k k n -G n k n 2 B 2 2
Then we can write

P (B ≥ λ) ≤ P B 1 ≥ √ λ + P B 2 ≥ √ λ ≤ P G -1 n k n - k n ≥ ω -1 x √ λ θ k n + P G n k n - k n ≥ θ √ λ k n .
Thus,

P (B ≥ λ) ≤ 2 exp      - n ω -1 x √ λ θ k n 2 4k/n      + 2 exp     - 3nω -1 x √ λ θ k n 8     +2 exp - n 2 θ 2 k n λ 4k + 2 exp - 3θn 4 k n √ λ (21)
where we have used Propositions 4 and 6. According to (17), we have

P ∆ n, k n (x) ≥ λ ≤ P (A ≥ λ 2 ) + P (B ≥ λ 2 ).
We then obtain the following deviation bound from Inequalities ( 19) and ( 21) for any k n < 1 2 and any λ > 0:

P |∆ n, k n (x)| ≥ λ 2 ≤ exp - n 64 F -1 k n -F -1 (0) 2 k n λ 2 + exp - 3n 16 k n λ F -1 k n -F -1 (0) + exp   - n 2 4k ω -1 x 1 θ λ 8 k n 2   + exp - 3n 8 ω -1 x 1 θ λ 2 k n + exp - nθ 2 λ 8 + exp - 3θn 4 λ 2 k n , (22)
where θ will be chosen further in the proof.

• Deviation bound of ∆ n, k n (x) for k n ≥ 1 2 . For controlling A, we now use the DKW Inequality (see Theorem 5), it gives that

P (A ≥ λ) ≤ P n k F -1 k n -F -1 (0) sup t∈[0,1] |F n (t) -F (t)| ≥ λ ≤ 2 exp   -2nλ 2 k n F -1 k n -F -1 (0) 2  
We decompose B into B 1 and B 2 as before. We use DKW again for B 1 and B 2 . For the quantile term

B 1 , note that    sup u∈[0, k n ] G -1 n (u) -u > λ    ⊂ sup u∈[0,1] G -1 n (u) -u > λ = sup t∈[0,1]
|G n (t) -t| > λ .

We find that for any θ > 0 :

P |∆ n, k n (x)| ≥ λ 2 ≤ exp   -2nλ 2 k n F -1 k n -F -1 (0) 2   + exp   -2n ω -1 x 1 θ λ 2 k n 2   + exp -n θ2 λ k n . (23)
where θ will be chosen further in the proof.

Upper bound on the expectation of ∆ n, k n (x)

• Case k n ≤ 1 2 . By integrating the probability in ( 22), we obtain

E |∆ n, k n (x) 2 ≤ 16 √ π 1 √ n k n -1 2 F -1 k n -F -1 (0) + 16 3n k n -1 F -1 k n -F -1 (0) + λ>0 exp   - n 2 4k ω -1 x 1 θ λ 2 k n 2   dλ I 1 + λ>0 exp - 3n 8 ω -1 x 1 θ λ 2 k n dλ I 2 + 8 θ 2 n + 32 9 1 θ 2 n 2 n k (24)
Since ω x (u)/u is a non increasing function, we have that ω -1 x (t)/t is a non decreasing function. Then, for any positive constants λ 1 and λ 2 :

I 1 + I 2 ≤ λ 1 + λ>λ 1 exp   - n 2 4k 1 λ 1 ω -1 x 1 θ λ 1 2 k n 2 λ 2   dλ + λ 2 + λ>λ 2 exp - 3n 8λ 2 ω -1 x 1 θ λ 2 2 k n λ dλ =     λ 1 + 2 √ k n λ 1 ω -1 x 1 θ λ 1 2 k n     +     λ 2 + 8λ 2 3nω -1 x 1 θ λ 2 2 k n    
We then take

λ 1 = 2 θ n k ω x 2 √ k n 2 and λ 2 = 2 θ n k ω x 8 3n
2 and we find that

I 1 + I 2 ≤ 4 θ n k ω x 2 √ k n 2 + 4 θ n k ω x 8 3n 2 .
We then choose

θ 2 = 1 √ nω x 2 √ k n k n
to balance the terms I 1 and 8 θ 2 n in (24). The deviation bound given in the theorem corresponds to this choice for θ.

Finally, note that ω x

√ 2k n ≤ √ 2ω x √ k n
because ω x (u)/u is a non increasing function and we obtain that there exists an absolute constant C such that

E ∆ n, k n (x) ≤ C √ n k n -1/2 F -1 k n -F -1 (0) + ω x √ k n . (25)
• Case k n ≥ 1 2 . We integrate the deviations ( 23) and we obtain that

E ∆ n, k n (x) ≤ C 1 √ n F -1 k n -F -1 (0) k n + θ n k ω x 1 √ n 2 + 1 θ2 n n k . ( 26
)
We then choose

θ2 = 1 √ nω x 1 √ n .
The deviation bound given in the Theorem correspond to this choice for θ. Since n k ≤ √ 2 ≤ 2, we see that the expectation bound (26) for this choice of θ can be rewritten as the expectation bound (25). This concludes the proof of Theorem 2. We first consider the case d = 1. For applying Le Cam's Lemma (Lemma 8), we need to find two probabilities P 0 and P 1 which distances to measure are sufficiently far from each other. Without loss of generality we can assume that x = 0. Let P ∈ P ω which satisfies (13). We can assume that P is supported on R + since the push forward measure of P by the norm is in P ω and also satisfies (13). Let F -1 be the quantile function of P . For some n ≥ 1, let P 0 := P and let

A.3 Proof of Proposition

2 u F -1 0,r F -1 1,r 1 1 n 0 m = k n F -1 0,r (0)
P 1 := 1 n δ 0 + P [0, F -1 (1-1/n)]
, where δ 0 is a Dirac distribution at zero and where P [a,b] is the restriction of the measure P to the set [a, b]. For i = 0, 1, let P i,r be the push-forward measure of P i by the power function t → t r on R + . Let also F i,r and F -1 i,r be the distribution function and the quantile function of P i,r , see Figure 10 for an illustration. Note that that P 1,r = 1 n δ 0 + P 0,r | [0,F -1 0,r (1-1/n)] . Thus P 1 is in P ω because

F -1 1,r (u) = F -1 0,r (0) if u ≤ 1 n , F -1 0,r (u -1/n) otherwise.
The probability measures P 0 and P 1 are absolutely continuous with respect to the measure µ := δ 0 + P . The density of P 0 with respect to µ is p 0 := 1 (0,+∞) whereas the density of P 1 with respect to µ is

p 1 = 1 n 1 {0} + 1 (0, F -1 (1-1/n)] . Thus, T V (P 0 , P 1 ) = R + |p 1 (t) -p 0 (t)| dµ(t) = 1 n + P F -1 1 - 1 n , ∞ = 2 n .
Next, [1 -T V (P 0 , P 1 )] 2n = (1 -2 n ) 2n → e -4 as n tends to infinity. Moreover,

d r P 0 ,r (x) -d r P 1 ,r (x) = n k k n 0 F -1 0,r (u) -F -1 1,r (u) du ≥ n k F -1 1,r ( k n ) F -1 1,r (u-1/n) {F 1,r (t) -F 0,r (t)} dt
according to basic geometric calculations. Thus,

d r P 0 ,r (x) -d r P 1 ,r (x) ≥ n k 1 n F -1 1,r k n -F -1 1,r (0) ≥ n k 1 n F -1 0,r k n -F -1 0,r (0) ≥ n k c n ω k n .
where we have used Assumption(13) for the last inequality. We conclude using Le Cam's Lemma.

We now consider the case d ≥ 2. Let P ∈ P ω which satisfies (13). By considering the push-forward measure of P by the function

R d -→ R + × {0} d-1 y -→ ( y , 0, . . . , 0) ,
we see that it is aways possible to assume that there exist a probability P supported on R + × {0} d-1 which satisfies ( 13). Now, it is then possible to define P 0 and P 1 as in the case d = 1 except that their support is now in R + × {0} d-1 . Following the same construction, the quantities T V (P 0 , P 1 ) and d r P 0 ,r (x)d r P 1 ,r (x) take the same values as in the case d = 1. We thus obtain the same lower bound as in the case d = 1.

A.4 Proof of Theorem 3

Inequality (17) in the proof of Theorem 3 is still valid. We can also use the deviation bound (19) on A for the case k n ≤ 1 2 . Regarding the deviation bound on B, we restart from Inequality (20) and we note that

n k F -1 G -1 n k n -F -1 k n k n -G n k n 1 G -1 n ( k n )≥ k n ≤ n k F -1 G -1 n k n -F -1 k n k n -G n k n 1 k n ≤G -1 n ( k n )≤ m + n k F -1 G -1 n k n -F -1 k n k n -G n k n 1 G -1 n ( k n )> m ≤ n k ω -1 x G -1 n k n - k n k n -G n k n 1 G -1 n ( k n )≤ m B + n k F -1 G -1 n k n k n -G n k n 1 G -1 n ( k n )> m B 3
By definition of B, B and B 3 , and using Proposition 3 in Appendix B, we obtain that

P |∆ n, k n (x)| ≥ λ ≤ P A ≥ λ 2 + P B ≥ λ 2 ≤ P A ≥ λ 2 + P B ≥ λ 2 + P B 3 ≥ λ 2 (27)
where P A ≥ λ 2 + P B ≥ λ 2 has already been upper bounded in the Proof of Theorem 3. We now upper bound the deviations of B 3 . For any θ 3 ∈ (0, 1) to be chosen further, we have:

2B 3 ≤ θ 3 F -1 G -1 n k n 2 1 G -1 n ( k n )> m B 2 4 + 1 θ 3 n k k n -G n k n 2 B 2 5 .
We have

P (B 3 ≥ λ 2 ) ≤ P B 4 ≥ λ 2 + P B 5 ≥ λ 2 where P B 5 ≥ λ 2 ≤ 2 exp - kθ 2 3 λ 8 + 2 exp - 3θ 3 k 8 λ 2 . ( 28
)
The probability P B 4 ≥ λ 4 can be upper bounded in two different ways: one using a concentration argument et one based on the Beta distribution of G -1 n . According to Proposition 6, we have

P B 4 ≥ λ 2 ≤ P G -1 n k n - k n ≥ F λ 2 1 θ 3 ∨ m - k n ≤ 4 exp - n 2 2k m - k n 2 . ( 29
)
Next, it is well known (see for instance p.97 in Chapter 3 of [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]

that G -1 n k n has a Beta(k, n -k + 1) distribution with density on [0, 1]: t → n! (k -1)!(n -k)! t k-1 (1 -t) n-k .
Thus, for any t ∈ (0, 1), P G -1

n k n ≥ 1 -t ≤ n k-1 t n-k+1 . Thus P B 4 ≥ λ 2 ≤ P B 4 > λ 3 ≤ P G -1 n k n > F λ 3 1 θ 3 ∨ m ≤ n k -1 1 -F λ 3 1 θ 3 ∨ m n-k+1 (30)
where the first inequality allows us to deal with a strict comparaison, which is necessary to rewrite the probability in term of the cdf. Note that a similar bound can be obtained using Bennett's inequality for B 4 . We now upper bound E|∆ n, k n (x)|. We only need to control the deviations of B 3 . Since P has a moment of order r, for any t > 0:

t (1 -F (t)) = tP ( x -X r > t) ≤ E x -X r =: C x,r .
Then for any λ > 0 (and n larger than 3):

∞ 0 P B 4 ≥ λ 2 dλ ≤ 4 λ 0 exp - n 2 2k m - k n 2 dλ + n k -1 ∞ λ 1 -F λ 3 1 θ 3 n-k+1 dλ ≤ 4 λ exp - n 2 2k m - k n 2 + 2 n √ 3C x,r θ 3 n-k+1 ∞ λ λ -n+k-1 2 dλ ≤ 4 λ exp - n 2 2k m - k n 2 + 8 λ n 4 √ 3C x,r θ 3 √ λ n-k+1 ≤ 4 λ exp - n 2 2k m - k n 2 + exp -(n -k + 1) log 4 √ 3C x,r θ 3 √ λ
We choose λ to balance the two terms inside the brackets:

λ = 4 √ 3C x,r θ 3 log n 2 2k(n -k + 1) m - k n 2 2
and then

∞ 0 P B 3 ≥ λ 2 dλ ≤ ∞ 0 P B 4 ≥ λ 2 dλ + ∞ 0 P B 5 ≥ λ 2 dλ ≤ C x,r, m 1 kθ 2 3 + θ 2 3 exp - n 2 2k m - k n 2
where C x,r, m only depends on C x,r and m. We thus take θ

2 3 = exp n 2 4k ( m-k n ) 2 √ k
and we obtain that

∞ 0 P B 3 ≥ λ 2 dλ ≤ C x,r, m√ k exp - n 2 4k m - k n 2 .
The deviation bound given in the Theorem derives from ( 27), ( 28), ( 29) and ( 30) with this value for θ 3 .

A.5 Proof of Theorem 4

We first recall the following Lemma from [START_REF] Chazal | Geometric inference for probability measures[END_REF]. We give the proof of the Theorem for r = 1. The calculations are also valid r > 1 by replacing λ by λC D,r in the probability bounds. The deviation bound of the Theorem can be proved with a simple union bound strategy. Up to enlarging the constant c, we can write N (D, λ) ≤ cλ -ν for any λ ≤ ω D (1). Now, for a given λ ≤ ω D (1), there exists an integer N ≤ cλ -ν and N points (x 1 , . . . , x N ) laying in D such that i=1...N B(x i , λ) ⊇ D. For any point x ∈ D, there exists a point π λ (x) of {x 1 , . . . , x N } such that xπ λ (x) ≤ λ 2 . According to Lemma 7, we have

|∆ n, k n ,1 (x) -∆ n, k n ,1 (π λ (x))| ≤ λ 2 . ( 31
)
According to Theorem 2, we have for any k < n 2 and any λ > 0:

P sup i=1...N |∆ n, k n ,1 (x i )| ≥ λ 2 ≤ 1 ∧ 2cλ -ν (λ) if λ ≤ ω D (1), 0 if λ > 2ω D (1), (32)
where

(λ) = exp - 1 64 kλ 2 F -1 x k n -F -1 x (0) 2 + exp - 3 16 kλ F -1 x k n -F -1 x (0) + exp   - n 2 4k    ω -1 D   k 1/4 λ 8 ω D 2 √ k n      2    + exp   - 3n 8 ω -1 D   k 1/4 λ 2 ω D 2 √ k n     + exp   - √ k 8 λ ω D 2 √ k n   + exp   - 3k 3/4 4 λ 2ω D 2 √ k n   
=: 1 (λ) + 2 (λ) + 3 (λ) + 4 (λ) + 5 (λ) + 6 (λ).

Using ( 31) and (32), we find that P sup x∈D |∆ n, k n (x)| ≥ λ is also upper bounded by the right hand term of (32).

We now integrate each term in λ -ν (λ). For the first one, let

α k,n = 1 64 k [F -1 x ( k n )-F -1
x (0)] 2 , then for any λ k,n > 0:

∞ 0 1 ∧ 2cλ -ν 1 (λ)dλ ≤ λ k,n + 2cλ -ν k,n ∞ λ k,n exp -α k,n λ 2 dλ ≤ λ k,n + 2c λ -ν-1 k,n α k,n exp(-α k,n λ 2 k,n ).
We balance these two terms by taking

λ n = log + [αk,n] ν+5 2α k,n
, it gives:

∞ 0 1 ∧ 2cλ -ν 1 (λ)dλ log + [α k,n ] +5 α k,n . (33)
The upper bound for the second term can be obtained in the same way. For the third term, let

β k,n := k 1/4 1 8 ω D 2 √ k n
. Since ω -1 D (t)/t is non decreasing, for any λ k,n > 0:

∞ 0 1 ∧ 2cλ -ν 3 (λ)dλ ≤ λ k,n + 2cλ -ν k,n ∞ λ k,n exp   - n 2 ω -1 D β k,n √ λ 2 4k    dλ ≤ λ k,n + 2cλ -ν k,n ∞ λ k,n exp   - n 2 4k ω -1 D β k,n λ k,n λ k,n 2 λ   dλ ≤ λ k,n + 4c k n 2 λ -ν k,n ω -1 D β k,n λ k,n 2 exp - n 2 4k ω -1 D β k,n λ k,n 2 .
We balance the two terms in the upper bounds by taking

λ k,n =        1 β k,n ω D     2 √ k n log +      β k,n ω D 2 √ k n   2(ν-1)               2 .
Indeed, we then obtain that:

∞ 0 1 ∧ 2cλ -ν 3 (λ)dλ λ k,n + λ k,n log +   β k,n ω D 2 √ k n 2(ν-1)          1 β k,n ω D     2 √ k n log +      β k,n ω D 2 √ k n   2(ν-1)               -2(ν-1)   ω D 2 √ k n β k,n   2(ν-1) λ k,n + λ k,n        ω D     2 √ k n log +      β k,n ω D 2 √ k n   2(ν-1)               -2(ν-1) ×     ω D     2 √ k n log +      β k,n ω D 2 √ k n   2(ν-1)            2(ν-1) λ k,n
where we have used log + ≥ 1 and the fact that ω D (u) is non decreasing for the second inequality. Since ω D (u)/u is non increasing and log + ≥ 1, we find that

λ k,n k -1/2 ω D √ k n -1      ω D √ k n log +     √ k ω D √ k n   ν-1        2 ω D √ k n √ k log +     √ k ω D √ k n   ν-1   . ( 34
)
We proceed in the same way to show that the upper bound (34) is also valid for 5 for 6 . The bound in expectation given in the Theorem is of the order of the sum of the upper bounds (33) and (34).

B Uniform empirical and quantile processes

This section brings together known exponential inequalities for the uniform empirical process and of the uniform quantile process. These results can be found for instance in Chapter 11 of [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]. Let ξ 1 , . . . , ξ n be n i.i.id. uniform random variables. The uniform empirical distribution function is defined by

G n (t) = 1 n n i=1 1 ξ i ≤t for 0 ≤ t ≤ 1.
The inverse uniform empirical distribution function is the function

G -1 n (u) = inf{t | G n (t)
> u} for 0 ≤ u ≤ 1. Proposition 3. For any x ∈ R d and any n ∈ N * :

F x,n -F x D = G n (F x ) -F x and F -1 x,n -F -1 x D = F -1 x G -1 n -F -1
x , where F x and F x,n are defined in the Introduction Section.

B.1 Exponential inequalities for the uniform empirical process

Let the function Φ defined on R by

Φ(λ) := 2(λ+1)[log(1+λ)-1] λ 2 if λ > -1, +∞ otherwise.
Next result is a point-wise exponential inequality for the deviations of the uniform empirical process ( √ n [G n (t)t]) t≥0 .

Proposition 4 (Inequality 1 and Proposition 1 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]). For any 0 ≤ t ≤ t 0 ≤ 1 2 and any λ > 0, we have

P √ n |G n (t) -t| ≥ λ ≤ 2 exp - λ 2 2t Φ λ t √ n ≤ 2 exp - λ 2 2t 0 Φ λ t 0 √ n ≤ 2 exp - λ 2 2t 0 1 1 + λ 3t 0 √ n .
The first Inequality comes from Bennett's Inequality and from the fact that nG n (t) follows a Binomial(n, t) distribution. The second Inequality derives from the fact that λ → λΦ(λ) is a non decreasing function, see Point (9) of Proposition 1 p.441 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]. The last inequality is Bernstein's Inequality, it can be derived by upper bounding Bennett's Inequality with the following result, see Point (10) of Proposition 1 p.441 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]:

Φ(λ) ≥ 1 1 + λ 3 for any λ ∈ R. ( 35
)
The famous DKW inequality [START_REF] Dvoretzky | Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator[END_REF] gives an universal exponential inequality for empirical processes. The tight constant comes from [START_REF] Massart | The tight constant in the dvoretzky-kiefer-wolfowitz inequality[END_REF]:

Theorem 5. For any λ > 0:

P sup t∈[0,1] √ n |G n (t) -t| ≥ λ ≤ 2 exp -2λ 2 .
However, in the neighborhood of the origin, a tighter uniform exponential inequality can be given.

Proposition 5 (Inequality 2 p. 444 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]). Let t 0 ∈ (0, 1 2 ). Then, for any λ > 0,

P sup t∈[0,t 0 ] √ n G n (t) -t 1 -t ≥ λ 1 -t 0 ≤ 2 exp - λ 2 2t 0 Φ λ t 0 √ n ≤ 2 exp - λ 2 2t 0 1 1 + λ 3t 0 √ n .
This local result directly derives from the fact that Gn(t)-t

1-t 0≤t<1

is a martingale (Proposition 1 p.133 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]). The second inequality directly derives from the previous one together with Inequality (35).

Lemma 8. Let P be a set of distributions. For P ∈ P, let θ(P ) take values in a metric space (X, ρ).

Let P 0 and P 1 in P be any pair of distributions. Let X 1 , . . . , X n be drawn i.i.d. from some P ∈ P. Let θ = θ(X 1 , . . . , X n ) be any estimator of θ(P ), then sup P ∈P E P n ρ(θ, θ) ≥ 1 8 ρ (θ(P 0 ), θ(P 1 )) [1 -TV(P 0 , P 1 )] 2n .

Figure 3 :

 3 Figure 3: Left: samples drawn for each generative model for the Segment Experiment. Right: one sample drawn from the clutter noise model for the 2-d Shape Experiment. The observation point is represented by a blue cross.

Figure 4 :

 4 Figure 4: Left: 3-d plot of the shape for the Fish Experiment. Right: a 3-d plot of a sample drawn for the uniform measure on the Tangle Cube. The observation point is represented by the blue point outside of the shape.

Figure 7 :

 7 Figure 7: Quantiles functions F -1x,r (top), expected error E∆ n, k n ,r (x) (middle) and theoretical upper bounds Ψ (bottom) with powers r = 1 (left) and r = 2 (right), for the Fish Experiment.

Figure 8 :

 8 Figure 8: Quantiles functions F -1x,r (top), expected error E∆ n, k n ,r (x) and theoretical upper bounds Ψ (bottom) with powers r = 1 (left) and r = 2 (right), for the Tangle Cube Experiment.

Figure 9 :

 9 Figure 9: Calculation of ∆ n, k n ,r (x) by integrating the grey domain horizontally or vertically.

Figure 10 :

 10 Figure 10: The two quantile functions F -1 0 and F -1 1 .

Lemma 6 (

 6 [START_REF] Chazal | Geometric inference for probability measures[END_REF]). For any (x, y) ∈ (R d ) 2 and any m ∈ (0, 1):|d P,m,r (x)d P,m,r (y)| ≤ xy .Next Lemma directly derives from Lemma 6.Lemma 7. For r = 1, the function x → ∆ n,m,1 (x) is 1-Lipschitz on R d . For r > 1, the function x → ∆ n,m,r (x) is C D,r -Lipschitz on the compact domain D where C D,r depends on r and on the Hausdorff distance between D and the support of P .

  u)du.

					F x -1 F x -1 F x -1							F x -1 F x -1 F x -1
		0.6 0.7 2000 2500 50							0.4 0.5 5e+06 6e+06 2500
	Quantile	0.2 0.3 0.4 0.5 20 1000 30 1500 40						Quantile	2e+06 1000 0.2 0.3 3e+06 1500 4e+06 2000
		0.1 500				Noiseless Noiseless Noiseless		0.1 1e+06 500				Noiseless Noiseless Noiseless
		0.0 10				Clutter noise Gaussian noise Clutter noise Gaussian noise Clutter noise Gaussian noise	0.0 0 0e+00				Clutter noise Gaussian noise Clutter noise Clutter noise Gaussian noise Gaussian noise
		0.00 0.00 0.00	0.05 0.05 0.05	0.10 0.10 0.10	0.15 0.15 0.15	0.20 0.20 0.20	0.25 0.25 0.25	0.30 0.30 0.30	0.00 0.00 0.00	0.05 0.05 0.05	0.10 0.10 0.10	0.15 0.15 0.15	0.20 0.20 0.20	0.25 0.25 0.25	0.30 0.30 0.30
					m=k/n m=k/n m=k/n							m=k/n m=k/n m=k/n
					E(∆ n ) E(∆ n ) E(∆ n )							E(∆ n ) E(∆ n ) E(∆ n )
		0.05 2.5				Noiseless Noiseless Noiseless		40				Noiseless
		0.04 100 2.0				Clutter noise Gaussian noise Clutter noise Gaussian noise Clutter noise Gaussian noise	0.020 30 150000 35				Clutter noise Gaussian noise
		0.03 80 1.5							0.015 25
		0.02 60 1.0							0.010 100000 20
									15
		0.01 40 0.5							0.005 10 50000				Noiseless Noiseless Clutter noise Clutter noise
		0.00							0.000 5				Gaussian noise Gaussian noise
		0.00 0.00 0.00	0.05 0.05 0.05	0.10 0.10 0.10	0.15 0.15 0.15	0.20 0.20 0.20	0.25 0.25 0.25	0.30 0.30 0.30	0.00 0.00 0.00	0.05 0.05 0.05	0.10 0.10 0.10	0.15 0.15 0.15	0.20 0.20 0.20	0.25 0.25 0.25	0.30 0.30 0.30
					m=k/n m=k/n m=k/n							m=k/n m=k/n m=k/n
					Ψ Ψ Ψ							Ψ Ψ Ψ
		2.5 7000 300				Noiseless Clutter noise Gaussian noise Noiseless Clutter noise Gaussian noise Gaussian noise Noiseless Clutter noise	1.0 1e+07 5000				Noiseless Clutter noise Gaussian noise
		1.5 2.0 4000 150 200 5000 6000 250							0.6 0.8 6e+06 3000 8e+06 4000
		1.0 3000 100							0.4 4e+06 2000
		0.5 2000 50							0.2 2e+06 1000				Noiseless Clutter noise Noiseless Clutter noise
		0.0 0							0.0				Gaussian noise Gaussian noise
		0.00 0.00 0.00	0.05 0.05 0.05	0.10 0.10 0.10	0.15 0.15 0.15	0.20 0.20 0.20	0.25 0.25 0.25	0.30 0.30 0.30	0.00 0.00 0.00	0.05 0.05 0.05	0.10 0.10 0.10	0.15 0.15 0.15	0.20 0.20 0.20	0.25 0.25 0.25	0.30 0.30 0.30
					m=k/n m=k/n m=k/n							m=k/n m=k/n m=k/n

Figure 5: Quantiles functions F -1 x,r (top), expected error E∆ n, k n ,r (x) (middle) and theoretical upper bounds Ψ (bottom) with powers r = 1 (left) and r = 2 (right), for the Segment Experiment.

Figure 6: Quantiles functions F -1 x,r (top), expected error E∆ n, k n ,r (x) (middle) and theoretical upper bounds Ψ (bottom) with powers r = 1 (left) and r = 2 (right), for the 2-d Shape Experiment.

Acknowledgments: The authors are grateful to Jérome Dedecker for pointing out the key decomposition Lemma 5 of the DTM. The authors were supported by the ANR project TopData ANR-13-BS01-0008.

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 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 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 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 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 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 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 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 q q q q q qq 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 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 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 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 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 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 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 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 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 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 q q q q q q B.2 Exponential inequalities for the uniform quantile process

The general strategy followed in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF] to prove exponential inequalities for the uniform quantile process consists in rewriting inequalities on G -1 n into inequalities on G n . For more details see for instance the proof of Inequality 2 p.415, or Lemma 1 p. 457 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]. We introduce the function Φ defined on R by

We give below a point-wise exponential bound for the uniform quantile process.

Proposition 6 (Inequality 1 p. 453 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]). For all λ > 0 and all 0 < u ≤ u 0 < 1, we have

The second Inequality derives from the property that λ → λ Φ(λ) is a nondecreasing function, see point (10) of Proposition 1 p.455 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]. The last inequality comes from the following lower bound, see Point (12) of Proposition 1 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]:

The following result is an uniform exponential inequality for the quantile process in the neighborhood of the origin.

Proposition 7 (Inequality 2 p. 457 in [START_REF] Shorack | Empirical processes with applications to statistics[END_REF]). Let u 0 ∈ (0, 1 2 ) and n ≥ 1. Then, for any λ > 0 such that

we have

This first Inequality comes from Proposition 5, the second Inequality is deduced from the first one using (36).

B.3 Le Cam's Lemma

The version of Le Cam's Lemma given below is from [START_REF] Yu | Assouad, Fano, and Le Cam[END_REF]. Recall that the total variation distance between two distributions P 0 and P 1 on a measured space (X , B) is defined by TV(P 0 , P 1 ) = sup B∈B |P 0 (B) -P 1 (B)|.

Moreover, if P 0 and P 1 have densities p 0 and p 1 with respect to the same measure λ on X , then TV(P 0 , P 1 ) = 1 2 1 (p 0 , p 1 ) := X |p 0p 1 |dλ.