Keywords: Exchangeable bootstrap, Empirical process, Exchangeable pair, Self-bounding function, Confidence region, Two-sample test, Permutation test.

1 Introduction↩︎

Bootstrap techniques are central tools for statistical inference, since they provide generic, data-dependent ways of approximating the sampling distribution of a statistic. Such information indeed allows one to build confidence intervals or to calibrate statistical tests, especially when the limiting sampling distribution of the statistic of interest is unknown or intractable.

The asymptotic validity of non-parametric bootstrap schemes has been addressed in wide generality in the context of the classical empirical process theory, where the ambiant dimension is fixed. More precisely, considering Efron’s empirical bootstrap ([1]), Giné and Zinn [2] characterized the functional central limit theorem and the uniform law of large numbers for the bootstrap empirical process indexed by a general class of functions, conditional on the data sample (both almost surely and in probability). Præstgaard and Wellner [3] – see also [4] – also proved conditional (again, almost surely and in probability) Donsker-type theorems and uniform laws of large numbers for the exchangeable bootstrap, under general moment conditions.

Recently, efforts have been made to extend the bootstrap theory to high-dimensional situations, where the dimension grows with the sample size. In a series of papers, Chernozhukov, Chetverikov, Kato and Koike notably obtained central limit theorems and non-asymptotic approximation rates for the wild and empirical bootstraps, with logarithmic dependence in the dimension ([5]–[9], see also [10] for a recent survey with further references). The proofs developed by these authors are based on Gaussian approximations of suprema of empirical processes, Gaussian anti-concentration and comparison inequalities. Applications include multiple testing, confidence regions for high-dimensional vectors, post-selection inference, to name but a few. Further statistical outcomes are discussed [10].

In this article, we prove concentration inequalities for the supremum of the bootstrap empirical process, for both Efron’s empirical bootstrap and the exchangeable bootstrap. To our best knowledge, such concentration inequalities are new. Indeed, as further explained in Section 4.1, this amounts to proving concentration inequalities for suprema of weighted sums of random variables, where the weights have the essential property of being exchangeable. Considering a weighted sum of exchangeable variables, Foygel Barber [11] recently obtained Hoeffding and Bernstein-type concentration inequalities. In terms of exchangeable bootstrap, the framework considered in [11] corresponds to analyzing the concentration conditionnally on data. But the fundamental difference with our problem is that there is only one sum that is considered in [11], corresponding to the degenerate situation where the supremum of the bootstrap empirical process is taken over a singleton. Nonetheless, we recover in a bounded setting a sub-Gaussian behavior (Hoeffding-type concentration) for the supremum of the exchangeable bootstrap empirical process, as can be seen in Theorem 2 below.

In order to give a clear idea of the concentration inequalities obtained in this article, let us state here two of our main results. We start with the concentration of the expectation of the supremum of the exchangeable weighted empirical process, conditioned on data.

When the weights are i.i.d. Rademacher variables, it is well-known that such a statistic, usually termed the conditional Rademacher average, is a self-bounding function [12], [13] (see also [14]–[16]). Consequently, it satisfies a Poisson-type concentration inequality, the variance proxy for the sub-Gaussian regime being proportional to the expectation. For a definition of the self-bounding property, see Section 4.1 below, following [16]. Considering exchangeable weights having a finite first moment, we extend the self-bounding property to the conditional expectation of the supremum of the exchangeable bootstrap process.

More precisely, let \((\xi_i)_{1\leq i \leq n}\) be exchangeable weights such that \(\mathbb{E}[\vert \xi_1 \vert]=\kappa<+\infty\) and \[\sum_{i = 1}^n \xi_i = 0\quad a.s.\] Let \((E,\mathcal{B})\) be a measure space and let \(\mathcal{T}\) be a set of measurable functions from \(E\) to \([-1,1]\). We define the function \(\overline{g}\) on the set \(E^n\) by \[\overline{g}((x_i)_{1 \leq i \leq n}) = \mathbb{E} \left[ \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_i t(x_{i}) \right].\] Note that this expectation is indeed well-defined. If \((x_{i})_{1 \leq i \leq n}\) is a realization of \(n\) i.i.d. random variables, then \(\overline{g}((x_{i})_{1 \leq i \leq n})\) represents the bootstrap estimate of the expected supremum.

We consider now the concentration of the supremum of the bootstrap empirical process, conditionally on the data. Note that for Efron’s bootstrap, the bootstrap empirical process is, conditionally on the data, a standard empirical process (see Section 2), the concentration of which is alrady captured by classical results, such as Bousquet’s ([17]) and Klein-Rio’s inequalities ([18]). Hence, we focus on the generic exchangeable bootstrap, that necessitates new inequalities.

First note that exchangeability of the weights \((\xi_i)_{1\leq i \leq n}\) ensures that, for any random permutation \(\sigma\) independent of the weights, the distribution of \((\xi_{\sigma(i)})_{1\leq i \leq n}\) is identical to the distribution of \((\xi_i)_{1\leq i \leq n}\). Actually, letting a uniform random permutation act on the weights indices and conditioning on the values of the weights will allow us to prove a sub-Gaussian concentration inequality. For convenience, we rather denote in this context the (fixed) values of weights by \(w=(w_i)_{1\leq i \leq n}\).

Compared to classical results pertaining to the concentration of the supremum of the empirical process around its mean, difficulties for proving concentration of its exchangeable bootstrap version are essentially due to the dependencies between the weights. Indeed, as exposed extensively in [16], classical techniques based on modified log-Sobolev inequalities, such as the one used in the proofs of Bousquet’s and Klein-Rio’s inequalities ([17], [18]) for the supremum of the empirical process, heavily rely on independence between random variables in the sums, and on tensorization properties in particular.

As further explained in Section 4.1, we prove Theorem 2 by making use of a so-called “exchangeable pair” technique, which has its origin in the work of Stein ([19], [20], see also [21]). In the context of concentration inequalities, the exchangeable pair approach was initiated by Chatterjee in his pathbreaking PhD thesis ([22], see also [23], [24]). As emphasized for instance in [25], one major strength of the exchangeable pair approach to concentration of measure is that it typically allows one to deal with dependent and complex systems of random variables, such as in statistical mechanics or in random graph theory ([24], [26]). Chatterjee’s approach has also been successfully adapted to concentration of random matrices [27], [28].

In Theorem 2 above, the statistic of interest is a functional of a random permutation. As detailed in Section 4, we implement the exchangeable pair technique through the use of refined arguments by White [29], who studies the strong mixing time of a random walk on the symmetric group converging to the uniform distribution. Actually, using that strong mixing time would induce an extra logarithmic factor depending on the sample size in our concentration bounds, so we rather exploit a weaker notion, that we call the strong convergence time.

Theorems 1 and 2 are general devices, that may be helpful in many statistical contexts. As a proof of concept, we use these results to obtain new insights in two applications: multivariate mean confidence intervals and two-sample testing, see Sections 6 and 7 respectively.

The paper is organized as follows. We present in Section 2 the objects of interest and some known results, especially concerning bounds for the mean of the bootstrap empirical process. Then Sections 3 and 4 focus respectively on the concentration of the conditional mean, with respect to the data, of the supremum of the bootstrap empirical process and the concentration conditional to the data. In particular, we describe in Section 4.1 some essential steps of our strategy for proving a concentration inequality, conditional to the data, for the supremum of the bootstrap empirical process. In addition, we provide a general bound combining these two aspects in Section 5. Finally, in Sections 6 and 7 respectively, we establish new multivariate confidence regions for the mean and new non-asymptotic bounds for the power of various non-parametric two-sample tests. Technical parts of the proofs and further remarks are deferred to the Supplementary Material.

2 The bootstrap empirical process↩︎

Let \((E,\mathcal{B})\) be a measurable space and let \(\mathcal{T}\) be a bounded class of measurable functions from \(E\) to \(\mathbb{R}\). Define a “distance” between two probability distributions \(P,Q\) on \((E,\mathcal{B})\) by \[d_{\mathcal{T}}(P,Q) = \sup_{t \in \mathcal{T}} \left\{ \int t dP - \int t dQ \right\}.\] Note that if \(\mathcal{T}\) is symmetric and “large enough”, so that the separation axiom is satisfied for \(d_\mathcal{T}\), then \(d_\mathcal{T}\) is a distance. In that case, the distance \(d_\mathcal{T}\) is known as an “integral probability metric” and can be used to construct two-sample tests (known as MMD tests [30], see also Section 7.2.3 below) as well as minimum distance estimators based on minimizing the distance of the empirical measure to a model, such as the minimum Wasserstein estimator [31]. Let \(X_1,\ldots,X_n\) be i.i.d. random variables belonging to \(E\) and denote by \(P_n\) the empirical measure.

Consider the quantity \[d_\mathcal{T}(P_n,P) = \sup_{t \in \mathcal{T}} \left\{ (P_n - P)(t) \right\}\,\] i.e. the supremum of the empirical process based on the class \(\mathcal{T}\), where for any probability measure \(Q\) with an integrable function \(t\), we set \(Q(t)=\int t dQ\). The quantity \(d_\mathcal{T}(P_n,P)\) plays a key role in controlling the statistical error of the MMD tests and minimum distance estimators based on the distance \(d_\mathcal{T}\). It also controls the generalization error of M-estimators in statistical learning, when \(\mathcal{T}\) is the class of functions \[\left\{ (x,y) \mapsto c(s(x),y) : s \in m \right\} \; ,\] where \(c\) is the contrast function and \(m\) is some model for the predictor (classifier or regression function). For these applications, it is important to be able to estimate the expectation and/or the quantiles of the random variable \(d_\mathcal{T}(P_n,P)\).

In this article, we consider the use of the bootstrap to approximate the (unknown) distribution of \(d_\mathcal{T}(P_n,P)\). The bootstrap heuristic applied to \(d_\mathcal{T}(P_n,P)\) consists in using the conditional distribution of \[c_W d_\mathcal{T}(P_n^W,P_n) = c_W\sup_{t \in \mathcal{T}} \left\{ (P_n^W - P_n)(t) \right\}\] knowing \(P_n\) as a proxy for the unconditional distribution of \(d_\mathcal{T}(P_n,P)\). Here, \(P_n^W\) is a bootstrap empirical measure based on the empirical measure \(P_n\) and auxiliary (independent) randomization \(W\), while \(c_W\) is a constant depending only on the distribution of \(W\). In Efron’s original approach [1], \(P_n^W\) is obtained by sampling \(n\) times with replacement from \(P_n\), leading to a bootstrap empirical measure of the form \[\label{eq95bootstrap95distrib} P_n^W = \frac{1}{n} \sum_{i = 1}^n W_i \delta_{X_i},\tag{1}\] where \(W\) is a multinomial random vector with success probabilities \(1/n\). More generally, the exchangeably weighted bootstrap [3], [32] consists in any measure of the form 1 with weights \(W\) such that

• \(\frac{1}{n} W\) is a probability vector,

• \(W\) is independent from the data,

• \(W\) is exchangeable.

We can therefore rewrite \(d_\mathcal{T}(P_n^W,P_n)\) as \[d_{\mathcal{T}}(P_n^W,P_n) = \frac{1}{n} \sup_{t \in \mathcal{T}} \left\{ \sum_{i = 1}^n (W_i-1) t(X_i) \right\} = \frac{1}{n} \sup_{t \in \mathcal{T}} \left\{ \sum_{i = 1}^n \xi_i t(X_i) \right\}\] where \(\xi = W-1\) is an exchangeable random vector which sums to \(0\). This leads to the following definition.

Note that we do not require \(X\) to be an i.i.d. vector, unlike the bootstrap setting described above. This generalization allows to treat the two-sample case, where variables are not i.i.d. under the alternative. Measurability issues seem similar to those that arise for the empirical process, let us only mention the following sufficient condition.

For completeness, we give a proof of Lemma 1 in Section 8.1 of the Supplementary Material. By default, we will always assume in this article that \(\mathcal{T}\) is indeed separable for the product topology in \(\left[-1, 1\right]^E\), which ensures the measurability of \(g\).

According to the bootstrap heuristic, the distribution of \(g(X,\xi)\) knowing the sample \(X\) approximates the distribution of \(nd_\mathcal{T}(P_n,P)\) up to a universal constant. In particular, the conditional expectation \(\mathbb{E}\left[ g(X,\xi) | X \right]\) should approximate \(n \mathbb{E}[d_\mathcal{T}(P_n,P)]\), the expected supremum of the empirical process, up to a universal constant. Let us introduce notation for these quantities.

Let us now give a brief overview of the problem and known results. Note that \(\overline{g}(X) = \mathbb{E}[g(X,\xi) | X]\) for \(X,\xi,g\) given by Definition 1. In that case, the bootstrap heuristic states that \(c_W \overline{g}(X)\) approximates the constant \(M_n(P)\) in distribution. This assertion can be decomposed into two claims: firstly, the expectation \(\mathbb{E}[\overline{g}(X)] = \mathbb{E}[g(X,\xi)]\) is approximately \(c^{-1}_W M_n(P)\) for some universal constant \(c_W\), secondly \(\overline{g}(X)\) concentrates around its expectation.

Concerning the first claim, upper and lower bounds for \(\mathbb{E}[g(X,\xi)]\) as a function of \(M_n(P)\) have been investigated in the literature. In the i.i.d. setting, Fromont [33] establishes the universal lower bound \(\mathbb{E}[g(X,\xi)] \geq \mathbb{E}[(\xi_1)_+] M_n(P)\). Arlot [34] observes that this lower bound can be improved to \(\mathbb{E}[g(X,\xi)] \geq \mathbb{E}[|\xi_1|] M_n(P)\) under a symmetry assumption on the class \(\mathcal{T}\) but that it is tight in general. For i.i.d. data, Han and Wellner [35] provide a sharp upper bound that only depends on the tails of the weights and on the supremum of the corresponding Rademacher process, where the original weights are replaced by independent Rademacher variables. Exchangeability of the weights is not actually needed for that bound. For the sake of completeness, we provide in Section 8.11 of the Supplementary Material, some upper and lower bounds that are instrumental in our applications.

The second claim, i.e. the concentration of \(\overline{g}(X)\) around its expectation, is the subject of section 3 of this article. Together with the results described in the latter paragraph, it validates to some extent the bootstrap heuristic for the approximation of the expected supremum \(M_n(P)\) in the non-asymptotic setting.

The bootstrap heuristic applies in principle to the whole distribution of \(n d_\mathcal{T}(P_n,P)\), not just its expectation. Bousquet’s inequality ([17]) shows that \(n d_\mathcal{T}(P_n,P)\) concentrates at the right of its expectation \(M_n(P)\), so by the bootstrap heuristic, the same ought to be true of the law of \(g(X,\xi)\) knowing \(X\). In the case of Efron’s bootstrap, this is indeed the case and can easily be proved, actually using Bousquet’s inequality and the fact that \(P_n^W\) is the empirical measure of an i.i.d. sample drawn from \(P_n\). More precisely, we have the following result.

Theorem 3 is a direct application of Bousquet’s inequality for the concentration of the empirical process, and we omit its proof.

In the general case, \(g(x,\xi)\) is of the form \[\sup_{a \in A} \left\{ \sum_{i = 1}^n a_i \xi_i \right\}\] for some bounded set \(A \subset \mathbb{R}^n\). The random vector \(\xi\) is exchangeable and sums to \(0\), which means that it can be written in the form \(\xi = Z_\sigma\), where \(\sigma\) is a uniform random permutation and \(Z\) is an arbitrary random vector valued in the set \[S = \left\{ z \in \mathbb{R}^n : z_1 \leq z_2 \leq ... \leq z_n , \sum_{i = 1}^n z_i = 0 \right\}.\] Since \(Z\) may be arbitrary, concentration of \(g(x,\xi)\) around \(\overline{g}(x)\) cannot hold under only the assumptions of definition 1. Indeed, if \(g(x,\xi)\) concentrates around \(\overline{g}(x)\) for some \(\xi\), one can replace \(\xi\) by \(\Lambda \xi\) for some non-negative random variable \(\Lambda\). This yields \(g(x,\Lambda \xi) = \Lambda g(x,\xi) \approx \Lambda \overline{g}(x)\), which fails to concentrate around its expectation.

Rather than concentration around \(\overline{g}(x)\), we study in Section 4 the concentration of \(g(x,Z_\sigma)\) around \(\overline{g}_Z(x) = \mathbb{E}[g(x,Z_\sigma) | Z]\), which amounts to setting \(\xi = w_\sigma\) for some fixed vector \(w\in S\). This is indeed the setting of Theorem 2. As \(w_\sigma\) is exchangeable and sums to \(0\), the same concentration result (Theorem 1) applies to \(\overline{g}(X)\) and to \(\overline{g}_Z(X)\) conditionally on \(Z\), yielding concentration of \(\overline{g}_Z(X)\) around \(\mathbb{E}\left[ g(X,Z_\sigma) | Z \right]\). Moreover, by the same argument, bounds for \(\mathbb{E}\left[ g(X, \xi) \right]\), such as Propositions 16 and 17, also apply conditionally on \(Z\). Thus, we can to a large extent treat \(g(X,\xi)\) as if \(\xi\) were of the form \(w_\sigma\) for some fixed vector \(w\) with sum \(0\). This approach is worked out in Section 5 and yields general deviation upper bounds for \(g(X,\xi)\).

3 Self-bounding property of the expectation conditioned on data↩︎

Let \(g,X,\xi\) and \(\overline{g}\) be given by Definitions 1 and 2. In order to establish the concentration properties of \(\overline{g}(X)\) for a vector of independent variables \(X = (X_1,\ldots,X_n)\), we will rely on the notion of a self-bounding function (see [16]). For completeness, we state the following definition (corresponding more precisely to the notion of a “strongly \((a,b)-\)self-bounding function” in [16]).

Note that this definition makes sense for any function \(f\), not necessarily measurable. However, to derive concentration inequalities, measurability of \(f\) and \(f_i\) is required. For this, the following lemma is useful.

We now come to the main theorem of this section.

Our principal contribution in Theorem 4 is the self-bounding property of \(\overline{g}\); the rest follows from known properties of self-bounding functions ([16]). Beyond exchangeability, it worth noting that the only constraint on the weights is integrability, which seems minimal and holds for all resampling weights used in practice, as far as we know.

The proof of Theorem 4 is deferred to Section 8.2 of the Supplementary Material. The main idea is to build lower proxy functions \(\bar{g}_i\) of \(\bar{g}\), as in Definition 3, by acting on the indices of the vector \(\xi\) through random permutations \(\tau_{i,J}\) and arguing that, by exchangeability, it does not change its distribution.

4 Concentration conditional on data↩︎

In practice, the quantity \(\overline{g}(x)\) generally cannot be calculated exactly, but is usually approximated by the Monte Carlo estimate \[\hat{g}_B(x) = \frac{1}{B} \sum_{b =1}^B \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_i^{(b)} t(x_{i})\;,\] where \((\xi^{(b)})_{b = 1,\ldots,B}\) are i.i.d. draws from the weight vector \(\xi\). In other applications, such as the non-parametric two sample tests discussed in Section 7, the quantity of interest is not the conditional mean \(\overline{g}(X)\) but rather a quantile of the conditional distribution of \[g(X,\xi) = \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_i t(X_{i})\] knowing \(X\), known as a “bootstrap quantile”. One way to handle both quantities is to derive concentration inequalities for \(g(x,\xi)\) around its mean \(\overline{g}(x)\).

In this section, we focus on weights of the form \(\xi = w_\sigma\) where \(w \in \mathbb{R}^n\) is a deterministic vector such that \(\sum_{i = 1}^n w_i = 0\) and \(\sigma \in \mathfrak{S}_n\) is a uniform random permutation. Consequences for general exchangeable weights are derived in section 5, following the argument sketched at the end of Section 2.

4.1 Proof steps for Theorem 2↩︎

For the sake of clarity, we briefly describe in this section some techniques that will be instrumental in our proofs. We also explain relations with some classical lemmas pertaining to the literature of concentration inequalities.

4.1.1 Exponential moments and a decoupling inequality↩︎

The concentration of a random variable is related to the behavior of its moments ([16], [36]). In the following, we will be interested in random variables with some finite exponential moments. Through the use of the classical Cramér-Chernoff method, it will thus be sufficient for us to control their moment-generating function.

Let us consider a random variable \(Z\), defined on the measurable space \((\mathcal{Z},\mathcal{T})\), and a measurable function \(g:(\mathcal{Z},\mathcal{T}) \rightarrow \mathbb{R}\), such that the moment-generating function of \(g(Z)\), denoted by \(\varphi_{g(Z)}\), is well-defined at the right-neighborhood of the origin: there exists \(\theta_0>0\) such that \(\varphi_{g(Z)}(\theta_0)=\mathbb{E}[e^{\theta_0 g(Z)}]<+\infty\). Denote also \(g_0(Z)=g(Z)-\mathbb{E}[g(Z)]\), the expectation of \(g(Z)\) being indeed well-defined in this case. Then, for any \(\theta \in (0,\theta_0)\), the quantity \(\mathbb{E}[g_0(Z) e^{\theta g_0(Z)}]\) is also well-defined, and it corresponds to the derivative of \(\varphi_{g_0(Z)}\) at the point \(\theta\).

In this setting, a quite standard approach to derive concentration inequalities for \(g_0(Z)\) ([16]) consists in establishing and solving a differential inequality for its moment-generating function. In this article, we will rather use the following result.

The above theorem readily implies that if there exists a random variable \(Y_\theta\) such that \(\mathbb{E}[g_0(Z) e^{\theta g_0(Z)}]\leq \mathbb{E}[Y_\theta e^{\theta g_0(Z)}]\), then it holds: \(\varphi_{g_0(Z)}(\theta)\leq \mathbb{E}[e^{\theta Y_\theta}]\). Consequently, one may consider Lemma 3 a “decoupling” inequality.

The first part of Lemma 3 above was proved in [37], as a consequence of a duality formula for the entropy. Considering in addition the version with strict inequalities, we further prove in Section 8.4 of the Supplementary Material that Lemma 3 is actually equivalent to that duality formula, that we recall now: for a non-negative random variable \(X\) such that \(\mathbb{E}[X\log(X)]<+\infty\), it holds \[{\rm Ent}(X):=\mathbb{E}[X\log(X)]-\mathbb{E}[X]\log(\mathbb{E}[X])=\sup_{U\, \text{s.t.}\, \mathbb{E}[e^{U}]=1}\mathbb{E}[UX]\;.\] In other words, Lemma 3 is nothing but another formulation of the duality formula for the entropy. This remark seems to be new, up to our best knowledge.

4.1.2 A covariance inequality through exchangeable pairs↩︎

In order to use Lemma 3 above for a centered function \(g_0=g-\mathbb{E}[g(Z)]\), notice first that \[\mathbb{E}[g_0(Z) e^{tg_0(Z)}]=\mathop{\mathrm{cov}}\left(g(Z),e^{tg_0(Z)}\right)\; ,\] thus casting the problem of bounding the left-hand side quantity into the quite developed framework of covariance inequalities. Covariance inequalities indeed appear to be useful in a variety of domains. Let us simply provide here some pointers to the literature for applications in particle systems ([38]–[40]), convex geometry and log-concavity ([41]–[43]), functional inequalities ([44]–[48]) and also, more importantly for us, concentration inequalities ([37], [49]–[53]).

Our strategy in Section 4.1.3 below will be to follow the path initiated by Sourav Chatterjee in his PhD thesis [22] (see also [23], [24]), by taking advantage of an exchangeable pair argument inspired by the pioneering work of Charles Stein related to rates of convergence in the central limit theorem.

The exchangeable pair approach is indeed very well suited for functionals of sums of random variables, especially when there are dependencies among these random variables, which is the case in general in the present article, where we consider exchangeable bootstrap statistics.

For completeness, the proof of Lemma 4 can be found in Section 8.3 of the Supplementary Material. It appears that positive parts in the term \(V_+(Z)\) of the covariance inequality, compared to absolute values, can bring substantial improvements when used to address concentration, due for instance to potential asymmetry between right and left tails. They will play an essential role when considering the supremum of the (bootstrap) empirical process.

In light of Lemma 4 applied with \(\psi=e^{t\cdot}\), Inequality ?? of Lemma 3 is satisfied with \(X=tg(Z)\) and \(Y=t^2V_+(Z)\). Lemma 3 then gives \[\label{eq:bound95Laplace95exch} \varphi_{g_0(Z)}(t)\leq \mathbb{E}[\exp(t^2V_+(Z))]\;.\tag{2}\]

Hence, the control of the moment generating function of \(g_0(Z)\) reduces to the one of \(V_+(Z)\), with the parameter taken to the square. In general, there is a major gain in switching to \(V_+(Z)\). In particular, whatever \(Z\), \(V_+(Z)\) is a non-negative random variable.

4.1.3 Implementing the exchangeable pair argument↩︎

Let \(w \in \mathbb{R}^n\) be a centered vector (i.e. \(\sum_{i = 1}^n w_i = 0\)) and let \(\sigma \in \mathfrak{S}_n\) be a uniform random permutation. The vector \(\xi = w_\sigma\) is thus exchangeable and centered. Let \[g_x(\sigma) = g(x,w_\sigma) = \sup_{t \in \mathcal{T}} \left\{ \sum_{i = 1}^n w_{\sigma(i)} t(x_{i}) \right\}.\] The only source of randomness here is the random permutation \(\sigma\). Hence, we are interested in the concentration properties of certain functions of a random permutation. Using the method of exchangeable pairs, we shall establish general concentration results for such functions which may be of intrinsic interest.

Let \(g: \mathfrak{S}_n \to \mathbb{R}\) be a function and let \(\sigma \in \mathfrak{S}_n\) be a uniform random permutation. In order to apply Lemma 4 to \(g(\sigma)\), we need to construct an exchangeable pair \((\sigma, \sigma')\) and an antisymmetric function \(F\).

Consider by analogy the case of an i.i.d. vector \(X = (X_1,\ldots,X_n)\), instead of a random permutation \(\sigma\). In that case, as first discovered in [22], some classical concentration results - according to the assumptions on \(g\) - can be recovered by taking the exchangeable pair \((X,X')\) where \(X_i' = X_i\) except for some random index \(I\) where \(X_I' = X_I^*\) is drawn from an i.i.d. copy of \(X\) (denoted \(X^*\)). Indeed, simplifications occur in the computations since in the exchangeable pair \((X,X')\), \(X'\) represents a “small modification” of \(X\), which acts only on a small number of coordinates of \(X\) (\(1\) coordinate in this case).

For permutations, the smallest number of coordinates which can be modified from \(\sigma\) to \(\sigma'\) is \(2\), which leads to the pairs \((\sigma, \sigma \tau_{I,J})\) or \((\sigma, \tau_{I,J} \sigma)\) for some random transposition \(\tau_{I,J}\) independent from \(\sigma\). We choose the distribution of \(\tau_{I,J}\) to be invariant under permutations of the indices in \(\left\{ 1,\ldots, n\right\}\), that is of the form \[\label{eq95loi95transpo95al} \alpha_0 \delta_{\mathrm{Id}} + \frac{2(1-\alpha_0)}{n(n-1)} \sum_{i = 1}^{n-1} \sum_{j = i+1}^n \delta_{\tau_{i,j}},\tag{3}\] i.e. equal to the identity with probability \(\alpha_0\) and uniformly distributed over the non-trivial transpositions. The pairs \((\sigma, \sigma \tau_{I,J})\) and \((\sigma, \tau_{I,J} \sigma)\) are then exchangeable and equal in distribution since \[(\sigma, \sigma \tau_{I,J}) = (\sigma \tau_{I,J} \tau_{I,J}, \sigma \tau_{I,J}) \text{ and } (\sigma, \tau_{I,J} \sigma) = (\sigma, \sigma \tau_{\sigma^{-1}(I), \sigma^{-1}(J)}).\] By convention, we write \((\sigma, \sigma') = (\sigma, \sigma \tau_{I,J})\).

Now that the pair is defined, Chatterjee’s work [22] yields a standard method of constructing \(F\) and of bounding \((F(\sigma, \sigma'))_+\), which is the great strength of his approach. Let us briefly describe it here in a somewhat informal manner (see Proposition 12 in the Supplementary Material for a rigorous statement).

For any permutation \(\pi\), let \(P_\pi\) be the conditional distribution of \(\sigma'\) knowing that \(\sigma = \pi\), i.e. the Markov kernel associated with the pair \((\sigma, \sigma')\). For any integer \(k\), let \(P_\pi^k\) be the \(k\)-th iterate of the Markov kernel, i.e. the distribution of the \(k\)-th element of a Markov chain started at \(\pi\) and with transition kernel \(\pi \mapsto P_\pi(\cdot)\) on \(\mathfrak{S}_n\). Here, this Markov chain is the “transposition random walk” on the permutation group. Given any two permutations \(\pi,\pi'\), the function defined by \[\label{eq95def95F95gen} F(\sigma,\sigma') = \sum_{k = 0}^{+ \infty} P_\pi^k g - P_{\pi'}^k g\tag{4}\] is well defined due to the mixing properties of the transposition random walk (see Proposition 12). Moreover, it is obviously antisymmetric and satisfies \[\mathbb{E} \left[ F(\pi,\pi') | \sigma \right] = \sum_{k = 0}^{+ \infty} P_\sigma^k g - \mathbb{E}\left[P_{\sigma'}^k f | \sigma \right] = \sum_{k = 0}^{+ \infty} P_\sigma^k g - P_\sigma^{k+1} g = g(\sigma) - Pg \;,\] where \(P\) is the uniform distribution on \(\mathfrak{S}_n\). This proves that \(F\) satisfies the hypotheses of lemma 4. In order to derive useful results from Lemma 4, it remains to bound \((F(\sigma, \sigma'))_+\). A possibility is to use a coupling argument (Chatterjee [22]), but no Markov coupling can merge faster than \(\mathcal{O}(n^2)\) [54] here. In a work on concentration of Haar measures ([55]), Chatterjee rather used directly the mixing property of the chain in total variation distance. In this article, we employ a hybrid approach in order to deliver an optimized bound.

Formally, let \((I_j,J_j)_{j \geq 1}\) be an i.i.d. sequence independent from \((I,J)\) and with the same distribution. Let \(\pi_0 = \mathrm{Id}\) and for any \(k \geq 1\), \[\pi_k = \pi_{k-1} \circ \tau_{I_k,J_k} = \tau_{I_1,J_1} \tau_{I_{2},J_{2}} ... \tau_{I_{k-1},J_{k-1}} \tau_{I_k,J_k}.\] This defines a random walk on the symmetric group, called the (right) transposition random walk, started at the identity. We then define \[\sigma_k = \sigma \pi_k \text{ and } \sigma_k' = \sigma' \pi_k\] for all \(k \in \mathbb{N}\). Clearly, the two chains never meet (unless \(\sigma = \sigma'\)), however they both converge in total variation to the uniform distribution on \(\mathfrak{S}_n\). In particular, the distributions of the two chains become closer and closer over time. To exploit this property, we introduce the concept of “strong convergence time” defined below.

A specific class of “strong convergence times” are the strong stationary times (also known as strong uniform times) which are such that the distribution of \(\pi_k\) (and hence of \(\tau_{i,j} \pi_k\)) is uniform on \(\mathfrak{S}_n\) for all \(k \geq T\) (knowing that this event has occurred). As is clear from the definition, these “strong stationary times” are closely related to the mixing properties of the Markov chain \((\pi_k)_{1 \leq k \leq n}\). Several authors have worked to construct strong stationary times for the transposition random walks [29], [56]; these times have expectation of order \(\mathcal{O}(n \log n)\), which is known to be optimal [56], [57]. In contrast, the property required by definition 4 is weaker than full mixing and so it stands to reason that the strong convergence times should be smaller on average than the strong uniform times. In fact, we shall see that strong convergence times can be constructed with expectation of order \(\mathcal{O}(n)\). First, let us show how strong convergence times can be used to bound \(F\).

The proof of Lemma 5 can be found in Section 8.5.2 of the Supplementary Material. Using the covariance inequality (Lemma 4), the decoupling inequality (Lemma 3) and Lemma 5 above yields the following theorem, the proof of which can be found in Section 8.5.3 of the Supplementary Material.

This concentration result appears to be new. Works by Bobkov [58] and Tolstikhin [59] (see also [60]) established a sub-Gaussian bound with variance parameter proportional to \(\left\| V_+(g,\sigma) \right\|_\infty,\) but only for \((m,n)-\)symmetric functions, i.e. functions \(g\) which are invariant under permutation of the first \(m\) and last \(n-m\) coordinates, for some \(m \in \{1,\ldots,n\}\). In the case of the function \(g_x,\) this amounts to requiring the vector \(w\) to only take two values \(a,b\) on the first \(m\) and last \(n-m\) coordinates, respectively. Another difference is that our bound involves exponential moments of \(V_+(g_x,\sigma)\) instead of an almost sure upper bound. The bound of Theorem 5 depends on the choice of a strong convergence time \(T_{i,j}\). If one of the known strong stationary times is used, this yields \(r(T)\) of order \(n \log n\) and there is an extra logarithmic term compared to the results of Bobkov and Tolstikhin. A bound of this kind was obtained by Chatterjee [55], but with \(V_+(g,\sigma)\) replaced by \[V(g,\sigma) = \frac{1}{n} \sum_{i = 1}^n \sum_{j = 1}^n (g(\sigma) - g(\sigma \tau_{i,j}))^2.\] Aside from removing the extra \(\log n\) term, Theorem 5 introduces a positive part in the variance proxy \(V_+(g,\sigma)\), which makes suprema such as \(g_x\) much easier to handle.

To remove the extra logarithm and prove Equation ?? , we now show that the construction of a certain strong stationary time, due to White [29], can be modified to yield a strong convergence time \(T_{1,2}\) with \(\mathbb{E}[T_{1,2}]\) and \(r(T_{1,2})\) of order \(n\).

The construction of \(\mathcal{P}(t)\) (“marking scheme D” in [29]) is such that the largest block does not shrink, i.e. there always exists \(B \in \mathcal{P}(t+1)\) such that \(P_m(t) \subset B\). It follows by induction that the maximal blocks \(P_m(t)\) form a nested sequence for all \(t\) larger than the hitting time of \(\left[ \left\lceil\tfrac{n}{2} \right\rceil,+\infty \right)\) by \((|P_m(t)|)_{t \in \mathbb{N}}\). This guarantees that \(\{i,j\} \subset P_m(t)\) remains true for all \(t \geq T_{i,j}\): thus, \[\{t \geq T_{i,j} \} = \left\{ |P_m(t)| > \frac{n}{2} \text{ and } \{i,j\} \subset P_m(t) \right\}.\] Moreover, White proved ([29]) that the law of \(\pi_t\) knowing \(\mathcal{P}(t)\) is invariant under transpositions \(\tau_{k,l}\) whenever \(k,l\) belong to the same block of \(\mathcal{P}(t)\). It follows that \(T_{i,j}\) is a strong convergence time in the sense of Definition 4.

Based on the work of White [29] and our own calculations (see Section 8.5.4 of the Supplementary Material), we can prove the following bound for \(r(T_{1,2})\).

We now return to the original problem of finding concentration bounds for the resampled supremum \(g(x,\sigma)\) around its expectation \(\overline{g}(x)\). By Theorem 5, this amounts to finding a majorant for \(V_+(g_x,\sigma)\). This is the point of the following Proposition, which proof is detailed in Section 8.5.5 of the Supplementary Material.

Theorem 5 and Propositions 6 and 7 directly yield the following bound on the moment generating function of \(g_x(\sigma)\).

Theorem 8 shows that \(g_x(\sigma)\) is sub-Gaussian with variance factor \(\mathcal{O}\left(v_+(x) \right)\). Compared to the bootstrap version of Bousquet’s inequality, which applies to the Efron weights (Theorem 3), the variance proxy is smaller (\(v_+(x)\) instead of \(2\overline{g}(x) + v_+(x)\)) and the tail behaviour is sub-Gaussian instead of sub-Poisson. This corresponds to the tail behaviour of the weights, which are bounded in Theorem 8 and essentially Poisson distributed in Theorem 3.

In the special case where \(w \in \left\{- \frac{1}{l}, \frac{1}{k} \right\}^n\) with \(k + l = n,\) the conclusion of Theorem 8 follows from Tolstikhin’s version of Bobkov’s inequality [59], [60] Theorem 8 is more general since it allows for arbitrary centered \(w\). This greater generality does come at the price of a worse constant (\(19\) in Inequality ?? instead of \(2\) in Tolstokhin’s inequality), though one should note that the constant \(19\) in Inequality ?? can likely be improved, either through a more refined analysis of the construction in [29] or using a different strong convergence time. In section 8.6 of the Supplementary Material, we also give a probabilistic proof of Tolstikhin’s Theorem that recovers the right constant up to terms of order \(1/n\), using the method of exchangeable pairs. This essentially shows that the difference in constants is not due to some inherent defect in our proof strategy.

5 A general deviation bound↩︎

Let us now combine Theorems 1 and 2 in order to derive a general high probability upper bound comparing the quantity \(g(X,\xi)\) – see Definition 1 above – with the expected supremum of the associated empirical process. Let \(\sigma \in \mathfrak{S}_n\) be a random permutation, independent from \(\xi\) and define \[\overline{g}_\xi(x) = \mathbb{E} \left[ \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_{\sigma(i)} t(x_i) | \xi \right]\;.\] First notice that Theorem 1 applies to \(\overline{g}_\xi\) conditionally on \(\xi\), yielding concentration of \(\overline{g}_\xi(X)\) around \[\mathbb{E}[g(X,\xi_\sigma) | \xi] = \mathbb{E} \left[ \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_{\sigma(i)} t(X_{i}) | \xi \right].\] The latter quantity can be bounded from above and from below by the results recalled in Section 8.11 of the Supplementary Material. For example, according to Proposition 17, \[\mathbb{E} \left[ \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_{\sigma(i)} t(X_{i}) | \xi \right] \leq \left\| \xi \right\|_\infty \mathbb{E} \left[ \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \bigl(t(X_{i}) - \mathbb{E}[t(X_i)] \bigr) \right].\] Now, it remains to bound the quantity \[g(X,\xi) - \overline{g}_\xi(X) = \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_{\sigma(i)} t(x_i) - \mathbb{E} \left[ \sup_{t \in \mathcal{T}} \sum_{i = 1}^n \xi_{\sigma(i)} t(x_i) | \xi \right].\] Conditioning on \(\xi = w\), this is equivalent to the concentration of \[\sup_{t \in \mathcal{T}} \left\{ \sum_{i = 1}^n w_{\sigma(i)} t(x_{i}) \right\}\;,\] which results from Theorem 2. This yields the following general probability upper bound on \(g(X,\xi)\).

The proof of Theorem 9 can be found in Section 8.7 of the Supplementary Material.

Inequality ?? is not a “true” concentration inequality since the upper bound depends on \(\xi\) and hence is random. In particular, the leading term \(M_n(\xi)\) is not the expectation \(\mathbb{E}[g(X,\xi)] = \mathbb{E}[g(X,\xi_\sigma)]\) but rather the conditional expectation, \(\mathbb{E} \left[ g(X,\xi_\sigma) | \xi \right]\). It is easy to show that concentration of \(g(X,\xi)\) around its expectation cannot hold at this level of generality: for example, replacing \(\xi\) by \(\Lambda \xi\) for some independent nonnegative random variable \(\Lambda\) yields \(g(X,\Lambda \xi) = \Lambda g(X,\xi)\), which fails to concentrate.

In the exchangeable bootstrap perspective, the point of using \(g(X,\xi)\) is to approximate the distribution of the associated empirical process supremum. In applications, one is typically interested in comparing \(g(X,\xi)\) to \(M_n\) rather than to \(\mathbb{E}[g(X,\xi)]\). If \(g(X,\xi)\) is known to concentrate (as is the case for Efron’s bootstrap), this still leaves the final step of relating \(\mathbb{E}[g(X,\xi)]\) to \(M_n,\) using for example Proposition 17. Any such bound that is valid for all exchangeable bootstrap weights will apply also to \(M_n(\xi)\) since conditionally on \(\xi,\) \(\xi_\sigma\) is exchangeable with null sum and independent from \(X\). For example, using Proposition 17 immediately yields \(M_n(\xi) \leq 2\left\| \xi \right\|_\infty M_n\). Thus, Theorem 9 should be as useful as a “real” concentration inequality for the purpose of bounding \(g(X,\xi)\) by a function of \(M_n\) with high probability.

In fact, if Proposition 17 is used to compare expectations then the dependence on \(\xi\) significantly strengthens the result compared to a deterministic concentration bound, yielding a non-trivial inequality even for unbounded weights. For example, if \(M_n \to + \infty\), then Theorem 9 and Proposition 17 together imply that \[\mathbb{E}[g(X,\xi)] \leq 2(1+o(1)) \mathbb{E} [\left\| \xi \right\|_\infty] M_n\] whereas Proposition 17 by itself only yields \(\mathbb{E}[g(X,\xi)] \leq 2 \left\| \left\| \xi \right\|_\infty \right\|_{L^\infty} M_n\).

The bound of Theorem 9 is not conditional on \(X\), unlike Theorem 8. However, we shall see that it still implies bounds on the upper tail of the bootstrap quantiles. In the rest of this section, let us denote by \(q_\alpha(Y)\) the least \(1-\alpha\) quantile of a random variable \(Y\), i.e. \[q_\alpha(Y) = \inf \left\{q \in \mathbb{R}: 1-\alpha \leq \mathbb{P}\left( Y \leq q \right) \right\} = \inf \left\{q \in \mathbb{R}: \mathbb{P}\left( Y > q \right) \leq \alpha \right\}.\] Similarly, let \(q_\alpha(Y | Z)\) denote the conditional quantile of order \(1-\alpha\). In particular, \(q_\alpha(g(X,\xi) | X)\) denotes the bootstrap quantile of order \(1-\alpha\) (defined up to a negligible event). The key tool is the following simple lemma.

The proof of Lemma 6 can be found in Section 8.7 of the Supplementary Material. As a result of this lemma, we can state a universal bound on the bootstrap quantiles. As it turns out, this bound also applies, with no modification, to the empirical bootstrap quantiles based on a random sample \((\xi_{(b)})_{b = 1,\ldots,B}\). For simplicity, we assume that the weights \(\xi\) are of the form \(1 - W\) or \(W-1\), where \(\frac{1}{n}W\) is an exchangeable probability vector; that is, the vector \(\xi\) is obtained from the weights of the exchangeably weighted bootstrap in the manner described in Section 2.

The proof of Corollary 1 can be found in Section 8.7 of the Supplementary Material.

According to the bootstrap heuristic, the bootstrap quantile \(\hat{q}_\alpha^B\) should approximate the quantile \[q_\alpha \left( \sup_{t \in \mathcal{T}} \sum_{i = 1}^n t(X_{i}) - \mathbb{E}[t(X_{i})] \right),\] up to a constant depending on the weights, as \(n,B \to + \infty\). By Bousquet’s inequality for the empirical process, we therefore expect a bound of the form \[\label{eq95conc95quant95opt} \hat{q}_\alpha^B \leq M_n + R \sqrt{|\log \alpha| (2M_n + \sigma^2)} - R \log \alpha\;,\tag{5}\] with \(R\) bounded in probability independently of \(\alpha\) as \(B\) tends to \(+\infty\). Corollary 1 yields a similar bound, but with \(M_n\) replaced by \(M_n(\xi)\) and \(R\) depending on \(\left\| \xi \right\|_\infty\). If the processes \((t(X_{i}))_{t \in \mathcal{T}}\) are symmetric and \[\left\| \left\| \xi_i \right\|_\infty \right\|_{L^\infty} \approx \mathbb{E}[|\xi|_1] \approx 1,\] then the above optimal bound follows by Proposition 17. In general, proving a bound of the form 5 with leading constant \(1\) is a difficult question, which goes beyond concentration of measure, since \(\mathbb{E}[g(X,\xi)]\) is not equal to \(M_n\). Significant work has been done to prove the validity of the bootstrap heuristic for suprema on finite index sets \(\mathcal{T}\) [9], but the bounds depend on the cardinality of \(\mathcal{T}\). Thus, for infinite \(\mathcal{T}\), the convergence rate established by such methods will vary depending on the entropy of \(\mathcal{T}\), as for Donsker and Glivenko-Cantelli theorems. It may well be that the convergence rate of \(\mathbb{E}[g(X,\xi)]/M_n\) to \(1\) likewise depends on the entropy of \(\mathcal{T}\). In contrast, the results of this article require no assumptions on \(\mathcal{T}\) other than those which guarantee the measurability of suprema.

6 Application I: Confidence regions for the mean in high-dimension↩︎

6.1 Presentation↩︎

In this section, we assume that the space \(E\) is a Banach space with norm \(\left\| \cdot \right\|\). The sample \((X_i)_{1 \leq i \leq n}\) is made of i.i.d. random vectors valued in \(E\), with common expectation \(\mu\). The expectation \(\mu\) can be estimated by the empirical mean \[\overline{X}_n = \frac{1}{n} \sum_{i = 1}^n X_i\;.\] A norm ball of the form \(B(\overline{X}_n,\hat{r}_\alpha)=\left\{x\in E\; /\; \Vert x-\overline{X}_n\Vert \leq \hat{r}_\alpha \right\}\), for some radius \(\hat{r}_\alpha>0\), provides a natural confidence region adapted to the geometry of \(E\). In order for \(B(\overline{X}_n,\hat{r}_\alpha)\) to have coverage \(1-\alpha,\) the data-dependent radius \(\hat{r}_\alpha\) must be such that \[\label{eq95def95conf95reg} \mathbb{P} \left( \left\| \overline{X}_n - \mu \right\| > \hat{r}_\alpha \right) \leq \alpha.\tag{6}\] For finite-dimensional \(E\), an asymptotically valid \(\hat{r}_\alpha\) can be constructed using covariance estimation and the central limit theorem. However, the quality of this approximation is heavily dependent on the space \((E,\left\| \cdot \right\|)\), primarily through its dimension, and the distribution \(P\). Applications in biology also produce high dimensional datasets where the dimension \(d\) of \(E\) is much larger than the sample size \(n\) [61]. In such cases, classical asymptotic arguments fail and the empirical covariance does not provide a reliable estimate of the true covariance matrix anymore.

The bootstrap provides an alternative method of calibrating \(\hat{r}_\alpha\), that does not suffer from a curse of dimensionality (as we shall see later). For a general norm \(\left\| \cdot \right\|\) and given resampling weights \((\xi_i)_{1 \leq i \leq n}\) satisfying Definition 1, the bootstrap estimate of \(\mathbb{E}\left[ \left\| \overline{X}_n - \mu \right\| \right]\) is \[\hat{R}_n = \mathbb{E} \left[\frac{1}{n} \left\| \sum_{i = 1}^n \xi_i X_i \right\| \Bigr| X_1,\ldots,X_n \right].\] The concentration inequalities of this article apply to \(\hat{R}_n\) and yield sharper bounds than the existing literature, to the best of our knowledge.

6.2 New confidence bounds↩︎

First, let us see how this problem relates to our setting. Let \(\mathcal{B}^*\) be the unit ball of the dual of \(E\), that is the set of linear functionals \(l: E \to \mathbb{R}\) such that \(|l(x)| \leq \left\| x \right\|\) for all \(x \in E\). By the Hahn-Banach theorem, for all \(x \in E\), \[\left\| x \right\| = \sup_{l \in \mathcal{B}^*} l(x).\] It follows that \[\left\| \overline{X}_n - \mu \right\| = \sup_{l \in \mathcal{B}^*} l\left(\overline{X}_n - \mu \right) = \frac{1}{n} \sup_{l \in \mathcal{B}^*} \left\{\sum_{i = 1}^n l(X_i) - l(\mu) \right\} \;,\] where by linearity and continuity of \(l,\) \(\mathbb{E}[l(X_i)] = l(\mu)\). It follows that \(\left\| \overline{X}_n - \mu \right\|\) is the supremum of the empirical process associated with the function class \(\mathcal{B}^*\). Likewise, the statistic \[n \hat{R}_n=\mathbb{E}\left[ \sup_{l\in \mathcal{B}^*} \left\{ \sum_{i=1}^n \xi_il(X_i)\right\}\bigl\vert X\right]\] is of the form of the quantity \(\overline{g}\) in Definition 2. Applying Theorem 1 yields the following result.

Theorem 10 yields confidence upper and lower bounds on \(\left\| \overline{X}_n - \mu \right\|\) based on the bootstrap statistic \(\hat{R}_n\), given the constant \(M\) and an upper bound on \(\sigma_\mathcal{B}\). A version of Theorem 10, that gives slightly more precise bounds for symmetric random variables, can be found in Section 8.8 of the the Supplementary Material (Theorem 15), with a detailed proof.

To the best of our knowledge, the state of the art theory on this bootstrap approach to mean estimation was established in an article by Arlot et al. [61]. Their setting is slightly different from the present one since instead of general norms, they consider sub-additive functions bounded by one of the \(p\)-norms. Common to both settings is the case of the \(p\)-norms which can be used as a point of comparison.

They consider two assumptions: that \(X\) is a Gaussian vector or that \(X\) is symmetric about \(\mu\) with \(\left\| X - \mu \right\|\) almost surely bounded by a constant \(M\). In the bounded symmetric case, their confidence bound is based on the bounded difference inequality and controls the deviations through a term of the form \(M/\sqrt{n}\). We are able to improve their result in this case, controlling the deviations through the smaller term \(\sqrt{M \hat{R}_n}\), yielding a sharper confidence bound.

Furthermore, the leading constants \(\kappa,b\) in the upper and lower bounds of Theorem \(\ref{thm95conf95reg95mean}\) can be made very close to \(1\) by an adequate choice of the resampling weights: for example, if \(n\) is even, taking \(\xi\) to be a random permutation of a fixed vector \(w \in \{-1,1\}^n\) having equal numbers of \(1\)s and \(-1\)s yields matching constants \(\kappa = b = 1\) for symmetric \(X_1\) (by Theorem 15). Optimizing over \(\theta > 0\) yields a remainder term of order \[\max \left\{ \sigma_\mathcal{B}\sqrt{\frac{x}{n}}, \sqrt{\frac{xM}{n} \hat{R}_n}, \frac{xM}{n} \right\}\;.\] Since \(M \geq \max \left\{ \sigma_\mathcal{B}, \kappa^{-1}\hat{R}_n \right\}\), for fixed \(x > 0,\) this bound is indeed sharper than the \(M \sqrt{\frac{x}{n}}\) given by [61]. The improvement can be quite significant: for example, if \(\left\| \cdot \right\|\) is the Euclidean norm and \(X_1\) is a random vector of dimension \(d_n\) with i.i.d. coordinates \(X_{1,j}\) such that \(\left\| X_{1,j} - \mu_j \right\|_{L^\infty} = c\) and \(\mathrm{Var}(X_{1,j}) = \sigma^2,\) then \(M = c d_n,\) \(\sigma_\mathcal{B}= \sigma\) and \(\mathbb{E}\left[ \left\| \overline{X}_n - \mu \right\| \right] \leq \sqrt{\mathbb{E}[\Vert \overline{X}_n-\mu\Vert^2]}= \sigma \sqrt{d_n/n}\). It follows that the bound of [61] is never of the correct order when \(d_n \to +\infty,\) whereas some standard calculations show that ours remains sharp as long as \(d_n = o(n)\).

More generally, the remainder terms are negligible if \(M \ll n \hat{R}_n\) and \(\frac{\sigma_\mathcal{B}}{\sqrt{n}} \ll \hat{R}_n\). Since \(\mathbb{E}[\hat{R}_n] \leq 2b \sigma_\mathcal{B}/\sqrt{n}\) if \(E\) is of dimension \(1\) (by using Proposition 17) and since, by assuming without loss of generality that \(l^*\in \mathcal{B}^*\) is such that \(\mathop{\mathrm{var}}(l^*(X_1))=\sigma^2_\mathcal{B}\), it holds \[\mathbb{E}\left[ \left\| \overline{X}_n - \mu \right\| \right] \geq \mathbb{E} \left[ \left| \frac{1}{n} \sum_{i = 1}^n l^*(X_i-\mu) \right| \right] \underset{n \to +\infty}{\sim} \sqrt{\frac{2}{\pi}} \frac{\sigma_\mathcal{B}}{\sqrt{n}}\;,\] the assumption that \(\hat{R}_n \gg \sigma_\mathcal{B}/\sqrt{n}\) can be interpreted as the claim that we are in a high-dimensional setting. Provided then that \(M \ll \sigma_\mathcal{B}\sqrt{n}\), the bounds of Theorem 10 are first-order correct.

Note also that Theorem 10 does not quite yield a practical confidence upper bound, since the quantity \(\sigma_\mathcal{B}\) depends on the unknown distribution of the data. In general, \(\sigma_\mathcal{B}\) can be estimated with \[\hat{\sigma}_\mathcal{B}^2 = \sup_{l \in \mathcal{B}^*} \hat{\sigma}_l^2 \text{ where } \hat{\sigma}_l^2 = \frac{1}{n} \sum_{i = 1}^n \left(l(X_i) - l(\overline{X}_n) \right)^2\; ,\] which is biased upward by Jensen’s inequality and is asymptotically consistent if \(\mathcal{B}^*\) is not too large (i.e. if it forms a Donsker class). If \(l^* \in \mathcal{B}^*\) attains the supremum in the definition of \(\sigma_\mathcal{B}\), then \(\hat{\sigma}_\mathcal{B}^2 \geq \hat{\sigma}_{l^*}^2\) where \(\hat{\sigma}_{l^*}^2\) is the empirical estimator of \(\mathrm{Var}(l^*(X_i)) = \sigma_\mathcal{B}^2\) based on the sample \(\left(l^*(X_i)\right)_{1 \leq i \leq n}\). Thus, \(\hat{\sigma}_\mathcal{B}\) can be substituted for \(\hat{\sigma}_{l^*}\) in confidence upper bounds for the (one-dimensional) standard deviation, such as those of [62], yielding a valid non-asymptotic confidence upper bound for \(\sigma_\mathcal{B}\) and thus a valid confidence region for \(\mu\) using Theorem 10. Alternatively, if \(\left\| \cdot \right\|\) is an \(\ell^p\)-norm on \(\mathbb{R}^d\), \(\sigma_\mathcal{B}\) and \(\hat{\sigma}_\mathcal{B}\) can be replaced by \(\left\| \sigma \right\|_p, \left\| \hat{\sigma} \right\|_p\), where \[\sigma = \left(\sqrt{\mathrm{Var}(\langle e_j, X_{1} \rangle)} \right)_{1 \leq j \leq d}, \hat{\sigma} = \left( \sqrt{\frac{1}{n} \sum_{i = 1}^n \langle e_j, X_i - \overline{X}_n \rangle^2 } \right)_{1 \leq j \leq d}\] and \((e_j)_{1 \leq j \leq d}\) is the canonical basis, as proposed by [61] for their bound in the Gaussian case. The following lemma shows that \(\left\| \sigma \right\|_p, \left\| \hat{\sigma} \right\|_p\) are never smaller than \(\sigma_\mathcal{B},\hat{\sigma}_\mathcal{B}\), respectively. Thus, in theory, \(\hat{\sigma}_\mathcal{B}\) provides a better confidence bound than \(\left\| \hat{\sigma} \right\|_p\) when \((E,\left\| \cdot \right\|) = (\mathbb{R}^d, \left\| \cdot \right\|_p)\). However, \(\left\| \hat{\sigma} \right\|_p\) may be preferable in practice since it is much easier to compute.

The proof of Lemma 7 can be found in Section 8.8 of the Supplementary Material.

7 Application II: Permutation two-sample testing↩︎

Let us introduce the non-parametric permutation two-sample test, that will be the statistical problem of interest in this section.

Assume that we have access to two independent samples \(X = (X_1,\ldots,X_n)\) and \(Y = (Y_1,\ldots,Y_m)\), of distributions \(P^{\otimes n}\) and \(Q^{\otimes m}\) respectively. Let also \(Z = (X,Y)\) be the concatenation of the two samples. The classical two-sample testing problem is to test the null hypthesis \(H_0:P=Q\) against the alternative \(H_1:P\neq Q\).

A generic approach to two-sample testing consists in choosing a class of functions \(\mathcal{F}\) and considering the following test statistic: \[\label{def95stat95test} T_{n,m}(\mathcal{F}) = \sup_{f \in \mathcal{F}} \left\{ \frac{1}{n} \sum_{i = 1}^n f(X_i) - \frac{1}{m} \sum_{j = 1}^m f(Y_j) \right\}\;.\tag{7}\] Classical examples, such as Kolmogorov-Smirnov, Kernel Mean Discrepancy tests or testing with respect to the Wasserstein distance, fall into this setting and will be further discussed in Section 7.2 below.

Heuristically, the statistic \(T_{n,m}(\mathcal{F})\) is expected to be larger under the alternative than under the null hypothesis. The test will thus depend on a threshold, above which the null hypothesis is rejected.

In general, the distribution of the statistic 7 under the null hypothesis is unknown. Hence, a bootstrap method can be used to select the significance threshold for the test. More precisely, let \[w = \left(\underbrace{\frac{1}{n},\ldots,\frac{1}{n}}_{n \text{ times}}, \underbrace{\frac{- 1}{m},\ldots,\frac{-1}{m}}_{m \text{ times}} \right)\] and let \(\xi = (w_{\sigma(i)})_{1 \leq i \leq n+m}\) , where \(\sigma\) is a uniform random permutation. Remark that \(\xi\) is exchangeable and that \(\sum_{i = 1}^{n+m} \xi_i = 0\). Hence, the results of Sections 3 and 4 above apply for \(\xi\).

The so-called permutation test ([63], [64]) rejects at level \(\alpha\) when \[\{T_{n,m}(\mathcal{F}) \geq \hat{q}_B(\alpha) \}\;,\] where \(\hat{q}_B(\alpha) = \hat{q}_B(Z,\alpha)\) is the empirical \(1-\alpha\) quantile based on the sample \[\left( \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} \xi_i^{(b)} f(Z_i) \right\} \right)_{b = 0,\ldots,B},\] with \(\xi^{(0)}=w\) and \((\xi^{(b)})_{1 \leq b \leq B}\) an i.i.d. sample, independent from \((Z,\xi)\), with the same distribution as \(\xi\). More precisely, by setting \(T_{\xi}(Z)=\sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} \xi_i f(Z_i) \right\}\), we have \[\hat{q}_B(\alpha)= \inf\{ q\,/\,\hat{F}^{(\ell)}_B(q)\geq 1-\alpha\}\;,\] where \(\hat{F}^{(\ell)}_B\) is the left-continuous version of the empirical cumulative distribution function of \((T_{\xi^{(0)}}(Z),\ldots,T_{\xi^{(B)}}(Z))\), \[\hat{F}^{(\ell)}_B (x) := \frac{1}{B+1} \sum_{b=0}^{B} \mathbb{I}_{\left\{T_{\xi^{(i)}}< x\right\}}\;.\] Equivalently, if \(T^{[0]}\leq\ldots\leq T^{[B]}\) stands for the order statistics of \((T_{\xi^{(0)}}(Z),\ldots,T_{\xi^{(B)}}(Z))\), then \(\hat{q}_B(\alpha)=T^{[m]}\), with \(m=\lceil (B+1)(1-\alpha)\rceil\), where \(\lceil x\rceil\) stands for the smallest integer larger than or equal to the real number \(x\). Using exchangeability, it can be shown (see for instance [65]) that this test controls the type-I error at level \(\alpha\), for any value of \(B\), that is: \(P_{H_0}(T_{n,m}(\mathcal{F}) \geq \hat{q}_B(\alpha))\leq \alpha\), where the notation “\(P_{H_0}\)” indicates that the probability of the event is computed under the assumption that \(P=Q\).

The concentration inequalities of Theorems 1 and 2 will allow us to give a non-asymptotic analysis of the power of the permutation two-sample test in terms of the integral probability metric \[d_{\mathcal{F}}(P,Q) := \sup_{f \in \mathcal{F}} \left\{ \int f dP - \int f d Q \right\}\;.\]

Note that if we assume that \(d_{\mathcal{F}}\) is a distance - as it is the case in the examples of Section 7.2 -, then it is symmetric in its arguments. Hence, the supremum over \(\mathcal{F}\) in its definition is equal to the supremum over \(\mathcal{F}\cup -\mathcal{F}\). We will thus assume that \(\mathcal{F}\) is a symmetric class, in the sense that if the function \(f\) belongs to \(\mathcal{F}\) then the function \(-f\) also belongs to \(\mathcal{F}\).

Our approach in non-asymptotic, based on Theorems 1 and 2. We refer to [4] for an account on the asymptotic theory of permutation two-sample testing.

7.1 A general result↩︎

Let us denote, for a distribution \(R\in\left\{ P,Q\right\}\), \(\sigma^2_R(\mathcal{F})=\sup_{f\in\mathcal{F}}\left\{\mathop{\mathrm{var}}_{R}(f(Z)) \right\}\), \(V=\sup_{f\in \mathcal{F}} \left\{ n \mathop{\mathrm{var}}(f(X_1)) + m\mathop{\mathrm{var}}(f(Y_1)) \right\}\) and, for any positive integer \(k\), \[M_{k}(R)=\mathbb{E}_{R^{\otimes k}}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{i=1}^{k} f(Z_i)-\mathbb{E}[f(Z_i)]\right\}\right].\]

The proof of Theorem 11 makes use of Theorems 1 and 13 and is deferred to Section 8.9 of the Supplementary Material. Indeed, for the specific weights of the permutation test, Tolstikhin’s inequality (Theorem 13) achieves better constants than Theorem 2. See also the related discussion in Section 8.6.

Let us comment on the separation rates obtained in Theorem 11. Note first that, as expected due to the symmetry between the pairs \((P,n)\) and \((Q,m)\) in the testing problem, the bound are symmetric in these variables.

Another preliminary remark consists in noting that the quantity \(M_k(R)/k\) is non-increasing in \(k\) for any probability measure \(R\) (see Lemma in Section 8.9.2 of the Supplementary Material). Hence, we have \(m/(n(n+m))M^2_n(P)=\mathcal{O}(M_n(P))\) and the same holds true with \(P\) replaced by \(Q\) and the pair \((n,m)\) switched.

Assume that the length of the two samples are similar, i.e. \(n \asymp m\). If the class \(\mathcal{F}\) is such that \(\sqrt{n} = \mathcal{O}(M_n(R))\) for \(R \in \{P,Q\}\) – which is the case as soon as \(\mathcal{F}\) contains two functions that are not \(R\)-a.e. equal –, then the separation rate in both ?? and ?? is \[\max \left\{ \frac{M_{n}(P)}{n}, \frac{M_{m}(Q)}{m} \right\} \;,\] i.e. the rate of convergence in the uniform law of large numbers for the class \(\mathcal{F}\).

It is worth noting that the main difference between Inequalities ?? and ?? is that Inequality ?? has factors that depend on the variances \(\sigma_R^2(\mathcal{F})\), \(R\in \left\{P,Q\right\}\), and \(V\), whereas in comparison, the controls are uniform (i.e. numerical constants replace the variance terms) in Inequality ?? . From a technical viewpoint, this is due to the two possible choices provided by Proposition 7 for bounding the quantity of the form \(V_+(g,\sigma)\) appearing in our proof of Theorem 11. If the variance terms are of the order of absolute constants, then Inequalities ?? and ?? are of the same order.

Finally, note that in the case of the Kolmogorov-Smirnoff test and the Wasserstein test in dimension 1, it holds \(M_n(R) = \mathcal{O}(\sqrt{n})\) for \(R \in \{P,Q\}\), which gives a parametric separation rate, of the order \(\mathcal{O}(1/\sqrt{n})\). See Section 7.2 below for more details about these specific tests.

7.2 Some examples↩︎

Fix some confidence level \(\alpha \in \left(0; \frac{1}{3} \right]\), some desired power level \(1 - 3\delta\) and define \(\alpha_B\) as in Theorem 11, i.e \[\alpha_B = \left(1 + \frac{1}{B} \right) \left( \alpha - \sqrt{\frac{3\alpha}{B} \log \left( \frac{1}{\delta} \right)} - \frac{1}{B+1} \right).\]

7.2.1 Kolmogorov-Smirnov two-samples test↩︎

The test statistics \(T^{(KS)}_{n,m}\) used in the Kolmogorov-Smirnov two-sample test [66] is \[T^{(KS)}_{n,m} = \sup_{x \in \mathbb{R}} \left| \frac{1}{n} \sum_{i = 1}^n \mathbb{I}\{X_i \leq x \} - \frac{1}{m} \sum_{j = 1}^m \mathbb{I}\{Y_j \leq x\} \right|\;.\] Using the notations of Section 7.1 above, it holds \(T^{(KS)}_{n,m}=T_{n,m}(\mathcal{F})\) for \[\mathcal{F}:=\left\{ c\mathbb{I}_{(-\infty,x]}\, / \, c\in\left\{ -1, 1\right\}, \; x\in \mathbb{R}\right\} \;,\] the symmetrized class of indicators of right-closed half-lines in \(\mathbb{R}\). The corresponding distance \(d_{\mathcal{F}}\) between probability measures is the so-called Kolmogorov distance, given by \[d_{\mathcal{F}}(P,Q)= d_{KS}(P,Q) = \sup_{x\in \mathbb{R}} \vert F(x)-G(x)\vert\;,\] where \(F\) and \(G\) are the cumulative distribution functions of \(P\) and \(Q\) respectively. The class \(\mathcal{F}\) is bounded, moreover for any distribution \(P\), \[\sigma^2_P(\mathcal{F}) = \sup_{f \in \mathcal{F}} \mathop{\mathrm{var}}(f(X)) = \sup_{x \in \mathbb{R}} \{ F(x) (1-F(x)) \} \leq \frac{1}{4}\;,\] with equality when the measure \(P\) is atomless. This means that there is little to gain by taking the variance into account: thus, we apply Equation ?? of Theorem 11. By the DKW inequality [67] with optimal constant [68], for any \(x > 0\), any \(k \in \mathbb{N}\) and any i.i.d. sample \((Z_i)_{1 \leq i \leq k}\) with common distribution function \(H\), \[\mathbb{P} \left( \sup_{t \in \mathbb{R}} \left| \frac{1}{k} \sum_{i = 1}^k \mathbb{I}\{Z_i \leq t \} - H(t) \right| \geq x \right) \leq 2e^{-2kx^2}\;,\] which implies that, for all \(k \in \mathbb{N}\) and any distribution \(R\), \[M_k(R) = \mathbb{E} \left[ k \sup_{t \in \mathbb{R}} \left| \frac{1}{k} \sum_{i = 1}^k \mathbb{I}\{Z_i \leq t \} - H(t) \right| \right] \leq 2k \int_0^{+\infty} e^{-2k x^2} dx = \sqrt{\frac{k \pi}{2}}\;.\] The following result is a corollary of Theorem 11 and the above bounds.

Usually, the Kolmogorov-Smirnov statistic \(T_{n,m}(\mathcal{F})\) is used together with a threshold of the form \[c_\alpha \sqrt{\frac{1}{n} + \frac{1}{m}} \approx \sqrt{2 \log \left( \frac{2}{\alpha} \right)} \sqrt{\frac{1}{n} + \frac{1}{m}}\] based on the limiting distribution of \(T_{n,m}(\mathcal{F})\) worked out by Smirnov [66]. This approximation can be poor for finite samples, while the exact critical value is hard to compute [69]. Using the DKW inequality [67] with optimal constant [68], the power of the above test can be shown to be at least \(1 - \delta\) whenever \[d_{KS}(P,Q) \geq c_\alpha \sqrt{\frac{1}{n} + \frac{1}{m}} + \sqrt{\frac{1}{2} \log \left( \frac{2}{\delta} \right)} \left( \frac{1}{\sqrt{n}} + \frac{1}{\sqrt{m}} \right).\] Corollary 2 shows that a similar guarantee holds for the permutation test, which is exact and does not rely on the knowledge of the asymptotic distribution of \(T_{n,m}(\mathcal{F})\).

7.2.2 Testing with respect to the Wasserstein distance↩︎

In this section, we make use of the so-called Wasserstein distance \(d_W\) – or Wasserstein-\(1\) distance – defined as follows: for any two distributions \(P\) and \(Q\) on a metric space \((\mathcal{X}, d)\), the Wasserstein distance between \(P\) and \(Q\) is \[d_W(P,Q)=\sup_{\mathcal{F}}\left\{Pf-Qf \right\}\;,\] where \(\mathcal{F}={\rm Lip}_1(\mathcal{X})\) is the set of \(1-\)Lipschitz functions on \((\mathcal{X},d)\). Given two samples with empirical distributions \(P_n\) and \(Q_m,\) the Wasserstein distance \(d_W(P_n,Q_m)=T_{n,m}(\mathcal{F})\) can be used as a test statistic for the two-sample problem. We refer to Ramdas [70] for a recent survey on Wasserstein two-sample testing, with a focus on relations to other classical testing problems. Unlike the case of the Kolmogorov-Smirnov statistic, the distribution of \(d_W(P_n,Q_m)\) under the null depends on \(P\). Ramdas et al. [70] resolve this problem in dimension \(1\) by modifying the test statistic, but their approach is specific to the one-dimensional case. Instead, we consider here the use of the bootstrap to calibrate the threshold. As we discussed previously, this yields an exact test no matter what the distribution of \(T_{n,m}(\mathcal{F})\) actually is.

When \(\mathcal{X}\) is compact, the functions belonging to \(\mathcal{F}\) can be centered by their respective mean value, with respect to any probability measure on \(\mathcal{X}\), in order to ensure that they all take values in \([-{\rm diam}(\mathcal{X}), {\rm diam}(\mathcal{X})]\), where \({\rm diam}(\mathcal{X})=\sup\left\{ d(x,y):x,y\in \mathcal{X}\right\}\) is the diameter of the set \(\mathcal{X}\). This comes from the following identity: for any probability measure \(P\) on \(\mathcal{X}\), any \(f \in \mathcal{F}\) and any \(x\in \; \mathcal{X}\), we have \[f(x)-Pf=\int (f(x)-f(y))P(dy) \leq \int_{\mathcal{X}} d(x,y) dP(y) \leq \mathrm{diam}(\mathcal{X})\;.\] Moreover, for any \(f \in \mathcal{F},\) \[\mathrm{Var}(f(X)) = \frac{1}{2} \mathbb{E} \left[ (f(X) - f(X'))^2 \right] \leq \frac{1}{2} \mathbb{E} \left[ d(X,X')^2 \right]\;,\] so we have that \[\sigma_P^2(\mathcal{F}) = \sup_{f \in \mathcal{F}} \left\{ \mathrm{Var}(f(X)) \right\} \leq \frac{1}{2} \mathbb{E} \left[ d(X,X')^2 \right].\] The separation rate of the test based on \(d_W(P_n,Q_m)\) is determined by the rate of growth of \(M_{l}(R) = l \mathbb{E}[d_W(R_{l},R)]\) for \(R \in \{P,Q\}\) and \(l \in \{n,m\}\), i.e. by the rate of convergence of \(\mathbb{E}[d_W(R_{l},R)]\) to \(0\), where \(R_{l}\) denotes the empirical distribution of an i.i.d. sample of size \(l\) from \(R\).

Let us consider the case where \(\mathcal{X}= \mathbb{R}^k\) and \(d(x,y) = \left\| x-y \right\|\) for some norm \(\left\| \cdot \right\|\). If the dimension \(k = 1, \left\| \cdot \right\| = |\cdot|\), and we have that \[d_W(R_{l},R) = \int_{\mathbb{R}} \left| F_{l}(t) - F_R(t) \right| dt\;,\] where \(F_{l}, F_R\) are the cumulative distribution functions of \(R_{l}\) and \(R\), respectively. It follows by Jensen’s inequality that \[M_{l}(R) \leq \sqrt{l} \int_{\mathbb{R}} \sqrt{F_R(t)(1-F_R(t))} = \mathcal{O} \left( \sqrt{l} \right) \;,\] provided that \(J_1(R)=\int_{\mathbb{R}} \sqrt{F_R(t)(1-F_R(t))} < +\infty\). As proved in [71], the finiteness of \(J_1(R)\) is in fact necessary and sufficient for a convergence of \(\mathbb{E}[d_W(R_l,R)]\) at the rate \(n^{-1/2}\).

In dimension \(d \geq 2\), it follows from the work of Fournier and Guillin [72] that for any \(q > 2\) and some constant \(C\) depending only on \(q,d\) and the norm \(\Vert \cdot \Vert\), \[\mathbb{E} \left[ d_W(R_{l},R) \right] \leq C \mathbb{E} \left[ d(X,\mathbb{E} X)^q \right]^{1/q} \frac{\log(1+l)}{\sqrt{l}} \label{ineq95W95dim2}\tag{8}\] when \(d = 2\) and \[\label{ineq95W95dimsup3} \mathbb{E} \left[ d_W(R_{l},R) \right] \leq C \mathbb{E} \left[ d(X,\mathbb{E} X)^q \right]^{1/q} l^{- 1/d}\tag{9}\] when \(d \geq 3\). Fournier and Guillin [72] give examples that show that this rate is attained for some distribution \(R\) on \(\mathbb{R}^d\), up to a \(\sqrt{\log l}\) factor when \(d = 2\). Unlike the one-dimensional case, this is only a worst-case bound: for example, if \(R\) is concentrated on an affine subspace of dimension \(k < d\), \(d_W(R_{l},R)\) behaves as in dimension \(k\). Thus, under the assumption that the distributions \(P,Q\) admit a moment of order \(q > 2,\) we are able in Corollary 3 below to derive the separation rate for the Wasserstein two-sample test.

To simplify the bounds, we assume that the two samples are of equivalent size, that is \(n \leq m \leq \rho n\) for some \(\rho > 1\). Theorem 11 then yields the following Corollary.

Thus, the separation rate of the bootstrap Wasserstein test is of order \(\frac{1}{\sqrt{n}}\) in dimension \(1\) and almost of order \(\frac{1}{\sqrt{n}}\) in dimension \(2\) (up to a \(\log n\) factor). For dimensions greater than \(2\), the worst-case rate worsens: there is a curse of dimensionality. Note however that this applies only to continuous distributions: for singular distributions concentrated on a subspace, the separation rate of the Wasserstein test adapts to the lower dimensionality. For continuous distributions, a possible solution considered in the literature is to replace \(T_{n,m}(\mathcal{F})\) with a dimensionally reduced version. If this dimensionally reduced Wasserstein distance is an integral probability metric, then it can likewise be analysed using Theorem 11. For example, this is the case of the max-sliced Wasserstein distance [73].

7.2.3 Kernel Maximum Mean Discrepancy Tests↩︎

The Maximum Mean Discrepancy between \(P\) and \(Q\) is an integral probability metric defined as \[{\rm MMD}(\mathcal{H},P,Q)=\max_{f\in B^1_\mathcal{H}}\left\{ \mathbb{E}_P[f(X)] - \mathbb{E}_Q[f(Y)]\right\},\] where \(\mathcal{H}\) is a Reproducing Kernel Hilbert Space associated to a (Mercer) kernel \(k(\cdot, \cdot)\) on a measure space \(\mathcal{X}\) and \(B_\mathcal{H}=\left\{f\in \mathcal{H}\, / \,\Vert f \Vert_\mathcal{H}\leq 1\right\}\) is the unit ball of \(\mathcal{H}\) endowed with its natural norm. Assuming that the kernel is bounded, that is, \[\kappa = \sup_{x \in \mathcal{X}} \sqrt{k(x,x)} < +\infty,\] then (by a standard argument) the functions of \(\mathcal{F}= B^1_\mathcal{H}\) are uniformly bounded by \(\kappa\), so the results of this article apply.

Let us however mention that in the context of the MMD test, the use of empirical process techniques can be bypassed through the use of test statistics that corresponds to an empirical version of the following formula, \[{\rm MMD}^2(\mathcal{H},P,Q)=\mathbb{E}[k(X,X^\prime)]+\mathbb{E}[k(Y,Y^\prime)]-2\mathbb{E}[k(X,Y)],\] where \(X^\prime\) is a copy of \(X\), similarly for \(Y^\prime\) and \(Y\), and all the random variables are independent. Nevertheless, it is instructive to compare the results derived from theorem 11 with what can be achieved using these alternative techniques.

In the RKHS setting, the general method considered in this article yields the test statistic \[\begin{align} T_{n,m}^{\mathcal{H}} &= {\rm MMD}(\mathcal{H},P_n,Q_m) \\ &= \left\| \frac{1}{n} \sum_{i = 1}^n k(X_i,\cdot) - \frac{1}{m} \sum_{j = 1}^m k(Y_j,\cdot) \right\|_{\mathcal{H}} \\ &= \left( \frac{1}{n^2} \sum_{i = 1}^n \sum_{i' = 1}^n k(X_i,X_{i'}) + \frac{1}{m^2} \sum_{j = 1}^m \sum_{j' = 1}^m k(X_j,X_{j'}) - \frac{2}{nm} \sum_{i = 1}^n \sum_{j = 1}^n k(X_i,Y_j) \right)^{1/2} \addtocounter{equation}{1}\label{eq95kern95MMD} \end{align}\tag{10}\] where \(P_n,Q_m\) denote the empirical distributions associated with the two samples \(X = X_1,\ldots,X_n\) and \(Y = Y_1,\ldots,Y_m\). This test statistic was one of several considered by Gretton [30], under the notation \({\rm MMD}_b(\mathcal{H},X,Y)\). Alternative, unbiased test statistics can be obtained by eliminating some of the terms in equation 10 . Concerning \(T_{n,m}^{\mathcal{H}}\), Theorem 7 in [30] shows that the test which rejects when \[T_{n,m}^{\mathcal{H}} \geq \kappa \left(\frac{2}{\sqrt{n}} + \frac{2}{\sqrt{m}} + \sqrt{2\left( \frac{1}{n} + \frac{1}{m} \right) \log \left( \frac{2}{\alpha} \right)} \right)\] has level \(\alpha\) and separation rate \(\frac{\kappa}{\sqrt{n}}\) in \({\rm MMD}\) distance. In comparison, the permutation test estimates the optimal threshold instead of using a worst-case bound and thus should adapt better to favourable properties of the distributions \(P,Q\). Using Theorem 11, we can show that its separation rate is still bounded by \(\frac{\kappa}{\sqrt{n}}\) in the worst case.

When \(\delta = \alpha\) and \(B\) is large enough, the lower bound of Corollary 4 is the same as Gretton’s proposed threshold, up to a numerical factor of \(3\) and the negligible remainder term \[\frac{12\kappa}{n+m} \log \left( \frac{1}{\delta} \right).\]

8 Supplementary material↩︎

8.1 Around measurability↩︎

8.2 Proof of the self-bounding property↩︎

8.3 Exchangeable pair covariance inequality↩︎

8.4 Decoupling lemma and entropy duality formula↩︎

We provide here a detailed proof of Lemma 3, which essentially follows the lines of the proof given in [37]. We also prove that Lemma 3 is equivalent to the following duality formula for the entropy : for a non-negative random variable \(Z\) such that \(\mathbb{E}[Z\log(Z)]<+\infty\), it holds \[{\rm Ent}(Z)=\mathbb{E}\left[Z\log\left(Z\right)\right]-\mathbb{E}[Z]\log(\mathbb{E}[Z])=\sup_{U\, \text{s.t.}\, \mathbb{E}[e^{U}]=1}\mathbb{E}[ZU]\;.\]

The proof of Lemma 3 is based on the duality formula for the entropy. Conversely, let us now prove that the duality formula for the entropy is a consequence of Lemma 3.

Consider a non-negative random variable \(Z\) such that \(\mathbb{E}[Z\log(Z)]<+\infty\). If \(\mathbb{E}[Z]=0\), then \(Z=0\) a.s. and the duality formula holds. Now, assume that \(\mathbb{E}[Z]>0\) and set \(V=\log(Z/\mathbb{E}[Z])\). It holds \(\mathbb{E}[e^V]=1\), hence \({\rm Ent}(Z)=\mathbb{E}[ZV]\leq \sup_{U\, \text{s.t.}\, \mathbb{E}[e^{U}]=1}\mathbb{E}[ZU]\;.\) Furthermore, we have the identity \({\rm Ent}(Z)/\mathbb{E}[Z]=\mathbb{E}[Ve^V]\), so if we assume that \({\rm Ent}(Z)<\mathbb{E}[UZ]\) for some random variable \(U\) such that \(\mathbb{E}[e^U]=1\), we also have \(\mathbb{E}[Ve^V]={\rm Ent}(Z)/\mathbb{E}[Z]<\mathbb{E}[UZ/\mathbb{E}[Z]]=\mathbb{E}[Ue^V]\), which gives by Lemma 3, \(1=\mathbb{E}[e^V]<\mathbb{E}[e^U]\). This means that \(\sup_{U\, \text{s.t.}\, \mathbb{E}[e^{U}]=1}\mathbb{E}[ZU]\leq {\rm Ent}(Z)\). This concludes the proof of the duality formula for the entropy, that consisted in establishing both inequalities.

8.5 Proofs of the result on concentration of the resampled empirical process conditioned on data↩︎

8.5.1 Existence of the antisymmetric function↩︎

8.5.2 Proof of Lemma 5↩︎

8.5.3 Proof of Theorem 5↩︎

Let us now analyze the concentration of \(f(\sigma)\). Fix some strong stationary time \(T\). Let \(\psi\) be the moment generating function of \(f(\sigma) = g(\sigma) - \mathbb{E}[g(\sigma)]\). By Lemma 4, \[\begin{align} \psi'(\theta)=\mathbb{E}[f(\sigma)e^{\theta f(\sigma)}] &\leq \theta \mathbb{E}\left[ (f(\sigma) - f(\sigma'))_+ (F(\sigma,\sigma'))_+ e^{\theta f(\sigma)} \right] \nonumber\\ &= \theta \mathbb{E}\left[\mathbb{E}[(g(\sigma) - g(\sigma'))_+ (F(\sigma,\sigma'))_+\vert \sigma] e^{\theta f(\sigma)} \right]\;. \label{eq95Vplus95sigma} \end{align}\tag{13}\] By Lemma 5 and since \(\sigma' = \sigma\) if \(I = J\), \[\begin{align} &(g(\sigma) - g(\sigma'))_+ (F(\sigma,\sigma'))_+ \\ \leq & \mathbb{I}\{ I \neq J \} \sum_{k = 0}^{+ \infty} \mathbb{E} \left[ (g(\sigma) - g(\sigma'))_+ (g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+ \mathbb{I}\{ k < T_{I,J} \} \bigl| \sigma,I,J \right]\;. \end{align}\] Let \(p_k = \mathbb{P}(k < T_{1,2})\). By the Cauchy-Schwarz inequality, \[\begin{align} &(g(\sigma) - g(\sigma'))_+ (F(\sigma,\sigma'))_+ \\ &\quad \leq \sum_{k = 0}^{+ \infty} \sqrt{p_k} (g(\sigma) - g(\sigma'))_+ \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma,I,J \right]^{1/2} \\ &\quad \leq \sum_{k = 0}^{+\infty} \frac{\sqrt{p_k}}{2} \left( (g(\sigma) - g(\sigma'))_+^2 + \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma,I,J \right] \right)\;. \end{align}\] Define the random variable \[W = \sum_{k = 0}^{+\infty} \frac{\sqrt{p_k}}{2} \mathbb{E} \left[ (g(\sigma) - g(\sigma \tau_{I,J}))_+^2 + (g(\sigma \circ \pi_k) - g(\sigma \tau_{I,J} \circ \pi_k))_+^2 \bigl| \sigma \right]\;.\] It follows from equation 13 that \[\psi'(\theta) \leq \theta \mathbb{E}[ W e^{\theta f(\sigma)} ]\] for any \(\theta \geq 0\). Lemma 3 implies therefore that \[\psi(\theta) \leq \mathbb{E}[\exp(\theta^2 W)]\;.\] Let \(r = \sum_{k = 0}^{+\infty} \sqrt{p_k}\) (assuming it is finite). Then \[W = \sum_{k = 0}^{+\infty} \frac{\sqrt{p_k}}{2r} \left( r\mathbb{E}[(g(\sigma) - g(\sigma'))_+^2|\sigma] + r\mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma \right] \right)\;.\] By convexity of the exponential function, \[\begin{align} &\exp(\theta^2 W) \leq \frac{1}{2} \exp \left(r\theta^2 \mathbb{E}[(g(\sigma) - g(\sigma'))_+^2|\sigma] \right)+\ldots\\ \ldots + & \frac{1}{2} \sum_{k = 0}^{+\infty} \frac{\sqrt{p_k}}{r} \exp \left(r \theta^2 \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma \right] \right)\;. \end{align}\] Moreover, by Jensen’s inequality, \[\begin{align} & \exp \left(r \theta^2 \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma \right] \right) \\ \leq & \mathbb{E}\left[ \exp \left(r \theta^2 \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma, \pi_k \right] \right) | \sigma \right]\;, \end{align}\] which implies that \[\begin{align} &\mathbb{E} \left[ \exp(\theta^2 W) \right] \leq \frac{1}{2} \mathbb{E} \left[ \exp \left(r\theta^2 \mathbb{E}[(g(\sigma) - g(\sigma'))_+^2|\sigma] \right) \right] \nonumber \\ &\quad + \frac{1}{2} \sum_{k = 0}^{+\infty} \frac{\sqrt{p_k}}{r} \mathbb{E}\left[ \exp \left(r \theta^2 \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma, \pi_k \right] \right) \right]\;. \label{eq95Jensen95permut} \end{align}\tag{14}\] Now, remark that for any permutation \(\pi\) and any transposition \(\tau = \tau_{i,j}\), \[\tau_{i,j} \circ \pi = \pi \circ \tau_{\pi^{-1}(i),\pi^{-1}(j)}\;.\] In particular, \[\sigma' \circ \pi_k = \sigma \circ \tau_{I,J} \circ \pi_k = (\sigma \circ \pi_k) \circ \tau_{\pi_k^{-1}(I),\pi_k^{-1}(J)}\;.\] Conditional on \(\sigma,\pi_k\), the pair \(\pi_k^{-1}(I),\pi_k^{-1}(J)\) follows the same distribution as \(I,J\). Hence \[\mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma, \pi_k \right] = \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma \circ \pi_k \circ \tau_{I,J}))_+^2 \bigl| \sigma, \pi_k \right]\;.\] By independence of \(\pi_k\) from \(\sigma\), \(\sigma \circ \pi_k\) is also a uniform random permutation and is independent from \(\tau_{I,J},\) which means that the pair \((\sigma \circ \pi_k, \sigma \circ \pi_k \circ \tau_{I,J})\) has the same distribution as the pair \((\sigma, \sigma')\). In particular, \[\mathbb{E}\left[ \exp \left(r \theta^2 \mathbb{E} \left[(g(\sigma \circ \pi_k) - g(\sigma' \circ \pi_k))_+^2 \bigl| \sigma, \pi_k \right] \right) \right] = \mathbb{E} \left[ \exp \left(r\theta^2 \mathbb{E}[(g(\sigma) - g(\sigma'))_+^2|\sigma] \right) \right].\] Injecting this upper bound into equation 14 yields \[\mathbb{E} \left[ \exp(\theta^2 W) \right] \leq \mathbb{E} \left[ \exp \left(r\theta^2 \mathbb{E}[(g(\sigma) - g(\sigma'))_+^2|\sigma] \right) \right]\] and it follows that \[\psi(\theta) \leq \mathbb{E} \left[ \exp \left(r\theta^2 \mathbb{E}[(g(\sigma) - g(\sigma'))_+^2|\sigma] \right) \right]\] for any \(\theta \geq 0\). Now, conclude by observing that \[\begin{align} \mathbb{E}[(g(\sigma) - g(\sigma'))_+^2|\sigma] &= \mathbb{E}[(g(\sigma) - g(\sigma \tau_{I,J}))_+^2| \sigma ] \\ &= \frac{2(1-\alpha_0)}{n(n-1)} \sum_{i = 1}^{n-1} \sum_{j = i+1}^n (g(\sigma) - g(\sigma \tau_{i,j}))_+^2 \\ &= \frac{1-\alpha_0}{n-1} V_+(g,\sigma)\;. \end{align}\]

8.5.4 Proof of Proposition 6↩︎

Let \(T = T_{1,2}\) for short. Define the following times \[\begin{align} T_1 &= \min \left\{t \geq 0 : |P_m(t)| \geq \frac{n}{3} \right\} \\ T_2 &= \min \left\{t \geq 0 : |P_m(T_1 + t)| > \frac{n}{2} \right\} \\ T_3 &= \min \left\{t \geq 0 : \{i,j\} \cap P_m(T_1 + T_2 + t) \neq \emptyset \right\} \\ T_4 &= \min \left\{t \geq 0 : \{i,j\} \subset P_m(T_1 + T_2 + T_3 + t) \neq \emptyset \right\} \\ &= T - T_1 - T_2 - T_3. \end{align}\] By construction, \(T = T_1 + T_2 + T_3 + T_4\). \((T_i)_{1 \leq i \leq 4}\) are stopping times; let \((\mathcal{F}_i)_{1 \leq i \leq 4}\) be the corresponding stopped \(\sigma\)-algebras. Let \[s = \min \left(1.01, 1 + \frac{1}{3n} \right).\] The proof of [29] shows that \(T_1\) is stochastically dominated by \(S_{n-1}\), the hitting time of \(n-1\) by a biased random walk \((X_t)_{t \geq 0}\) started at \(X_0 = 0\) and with increment distribution \[\mathbb{P}(X_1 = 1) = \frac{1}{3}, \mathbb{P}(X_1 = - 1) = \frac{1}{6}, \mathbb{P}(X_1 = 0) = \frac{1}{2}.\] By the strong Markov property and translation equivariance, the distribution of \(S_{n-1}\) is that of an i.i.d. sum of \(n-1\) variables distributed as \(S_1\), the hitting time of \(1\). Thus, \[\mathbb{E}[s^{T_1}] \leq \mathbb{E}[s^{S_1}]^{n-1} = G_1(s)^{n-1}\] where \[G_1(s) = \mathbb{E}[s^{S_1}].\] Now, conditioning on the first step of the walk, we see that

• If \(X_1 = 1\) then \(S_1 = 1\) by definition

• If \(X_1 = 0\), we have wasted one step, the conditional distribution of \(S_1\) is the (unconditional) distribution of \(S_1 + 1\).

• If \(X_1 = -1\), two upward steps need to be taken, so the conditional distribution of \(S_1\) is that of \(1 + S_1 + S_1^*\), where \(S_1^*\) is an i.i.d. copy of \(S_1\).

This leads to the equation \[G_1(s) = \frac{s}{3} + \frac{s}{2} G_1(s) + \frac{s}{6} G_1(s)^2\] i.e. \[\frac{s}{6} G_1(s)^2 - \left(1 - \frac{s}{2} \right) G_1(s) + \frac{s}{3} = 0.\] This quadratic equation has two solutions, only one of which belongs to \([0,1]\) when \(s \in [0,1]\). This yields \[\label{eq95calc95G1} G_1(s) = \frac{3}{s} \left(1 - \frac{s}{2} - \sqrt{1 - s + \frac{s^2}{36}} \right)\tag{15}\] at least for \(s\in [0,1]\).

The right-hand side can be analytically continued to the open disk \(B(0,s_*)\), where \[s_* = \frac{1}{\frac{1}{2} + \frac{\sqrt{2}}{3}} > 1.02.\] To see this, remark that for any complex \(z\) such that \(|z| < s_*\), \[\begin{align} \mathrm{Re}\left(1 - z + \frac{z^2}{36} \right) &= 1 - \mathrm{Re}(z) + \frac{\mathrm{Re}(z)^2 - \mathrm{Im}(z)^2}{36} \\ &= 1 - \mathrm{Re}(z) + \frac{2\mathrm{Re}(z)^2 - |z|^2}{36} \\ &\geq 1 - \mathrm{Re}(z) + \frac{\mathrm{Re}(z)^2}{18} - \frac{(s_*)^2}{36} \\ &> 1 - s_* + \frac{(s_*)^2}{36} \text{ since } |\mathrm{Re}(z)| \leq |z| < s_* \\ &> 0, \end{align}\] so that the function \[\psi: z \mapsto \frac{3}{z} \left(1 - \frac{z}{2} - \sqrt{1 - z + \frac{z^2}{36}} \right)\] is well defined and analytic on \(B(0,s_*) \backslash \{0\}\), where \(\sqrt{\cdot}\) denotes the analytic continuation of the ordinary square root function to the open half-plane \(\{z : \mathrm{Re}(z) > 0\}\). \(0\) is a removable singularity as can easily be checked using Taylor expansion. Since \(\psi\) is analytic on \(B(0,s_*)\), the radius of convergence of its Taylor series at \(0\) is at least \(s_*\). By equation 15 , the Taylor series of \(\psi\) at \(0\) is \[\sum_{k = 0}^{+\infty} z^k \mathbb{P}(S_1 = k) = G_1(z),\] which proves that \(G_1\) is well-defined and equal to \(\psi\) on \(B(0,s_*)\) and in particular on \((0,s_*)\).

Since \(S_1\) is integer-valued, \(G_1\) is convex on \([0;s_*)\), in particular \[G_1(s) \leq 1 + \frac{G_1(1.01)-1}{0.01}(s-1) \leq 1 + 6.81(s-1) \leq 1 + \frac{6.81}{3n}\] and hence \[\mathbb{E}[s^{T_1}] \leq \left(1 + \frac{6.81}{3n} \right)^{n-1} \leq \exp \left( \frac{6.81}{3} \right) \leq 9.68.\] Consider now \(T_2\). As explained in the proof of [29], at each time step \(t\) such that \(\frac{n}{3} \leq k = |P_m(t)| \leq \frac{n}{2}\), there is a probability at least \[\frac{k(n-k)}{n(n-1)} \geq \frac{1}{3} \frac{2}{3} = \frac{2}{9}\] of increasing the size of \(P_m(t)\) by (at least) one, conditional on the past. Thus, conditionally on the past up to time \(T_1\), the distribution of \(T_2\) is dominated by the sum of \(\frac{n}{2} - \frac{n}{3} + 1 = \frac{n}{6}+1\) independent geometric variables with parameter \(\frac{2}{9}\), so that \[\mathbb{E}\left[s^{T_2} | \mathcal{F}_1 \right] \leq \left(\frac{\frac{2}{9}s}{1 - \left(1 - \frac{2}{9} \right)s} \right)^{\frac{n}{6}+1} = \left( \frac{2s}{9 - 7s} \right)^{\frac{n}{6}+1} \leq \frac{2\times 1.01}{9 - 7\times1.01} \left( \frac{2s}{9 - 7s} \right)^{\frac{n}{6}}\] which is well-defined and finite for all \(s < \frac{9}{7}\). By convexity of the function \(u \mapsto \frac{2u}{9-7u}\), we have that \[\frac{2s}{9 - 7s} \leq 1 + \left(\frac{2\times 1.01}{9 - 7\times 1.01} - 1 \right) \frac{s-1}{0.01} \leq 1 + \frac{4.67}{3n}\] which yields \[\mathbb{E}\left[s^{T_2} | \mathcal{F}_1 \right] \leq 1.047 \left( 1 + \frac{4.67}{3n} \right)^{\frac{n}{6}} \leq 1.047 \exp \left( \frac{4.67}{18} \right) \leq 1.36.\] Consider now \(T_3\) and \(T_4\). Once \(t \geq T_1 + T_2\), that is, once \(|P_m(t)|\) becomes strictly larger than \(\frac{n}{2}\), [29] is such that the block that was maximal at time \(T_1 + T_2\) continues to grow and hence remains maximal at all later times.

At each time step \(t \geq T_1 + T_2\), assuming \(i,j \notin P_m(t)\), [29] yields \(i \in P_m(t+1)\) or \(j \in P_m(t+1)\) as soon as \((I_{t+1},J_{t+1}) \in \{i,j\} \times P_m(t) \cup P_m(t) \times \{i,j\}\), which happens with probability \[\frac{2|P_m(t)|}{n(n-1)} \geq \frac{1}{n-1}.\] Thus, conditionally on the past up to time \(T_1 + T_2,\) \(T_3\) is stochastically dominated by a geometric distribution with parameter \(\frac{1}{n-1}\), which yields \[\mathbb{E}\left[ s^{T_3} | \mathcal{F}_2 \right] \leq \frac{\frac{s}{n-1}}{1 - \frac{n-2}{n-1}s}.\] Now, \(s \leq \frac{3n+1}{3n}\) hence \[\begin{align} \frac{n-2}{n-1} s &\leq \frac{3n^2 - 5n - 2}{3n^2 - 3n} \\ &\leq 1 - \frac{2}{3(n-1)} \\ 1 - \frac{n-2}{n-1} \frac{3n+1}{3n} &\geq \frac{2}{3(n-1)} \text{hence} \\ \frac{\frac{s}{n-1}}{1 - \frac{n-2}{n-1}s} &\leq \frac{3}{2}s \\ &\leq 1.5 \times 1.01 \\ &= 1.515. \end{align}\] Similarly, conditionally on the past up to time \(T_1 + T_2 + T_3,\) \(T_4\) is stochastically dominated by a geometric distribution with parameter \(\frac{1}{2(n-1)}\), so that \[\mathbb{E}\left[ s^{T_4} | \mathcal{F}_3 \right] \leq \frac{\frac{s}{2(n-1)}}{1 - \frac{2n-3}{2n-2}s}.\] Since \(s \leq \frac{3n+1}{3n}\), \[\begin{align} \frac{2n-3}{2n-2} s &\leq \frac{6n^2 - 7n - 3}{6n^2 - 6n} \\ &\leq 1 - \frac{1}{6(n-1)} \\ \frac{\frac{s}{2(n-1)}}{1 - \frac{2n-3}{2n-2}s} &\leq 3s \\ &\leq 3\times 1.01 \end{align}\] It follows that \[\mathbb{E}\left[ s^{T_3} | \mathcal{F}_2 \right] \leq 1.515, \quad \mathbb{E}\left[ s^{T_4} | \mathcal{F}_3 \right] \leq 3.03.\] This finally yields \[\mathbb{E}[s^T] = \mathbb{E} \left[ s^{T_1} \mathbb{E}\left[ s^{T_2} | \mathcal{F}_1 \right] \mathbb{E}\left[ s^{T_3} | \mathcal{F}_2 \right] \mathbb{E}\left[ s^{T_4} | \mathcal{F}_3 \right] \right] \leq 9.68\times 1.36 \times 1.515 \times 3.03 \leq 60.5\] Now, for any \(t \geq 1\), by Markov’s inequality, \[\mathbb{P} \left( T \geq t \right) = \mathbb{P} \left( s^T \geq s^t \right) \leq \frac{\mathbb{E}\left[ s^T \right]}{s^t} \leq \frac{60.5}{s^t}.\] Let \[t_* = \inf \left\{t > 0 : s^t \geq 60.5 \right\} = \frac{\log(60.5)}{\log(s)},\] it follows that \[\begin{align} r(T) &= \sum_{t = 0}^{+\infty} \sqrt{\mathbb{P}(T > t)} \\ &= \sum_{t = 1}^{+\infty} \sqrt{\mathbb{P}(T \geq t)} \\ &\leq \lfloor t_* \rfloor + \sum_{t = \lfloor t_* \rfloor + 1}^{+\infty} \sqrt{\frac{60.5}{s^t}} \\ &\leq \lfloor t_* \rfloor + \sum_{t = 0}^{+\infty} s^{- \frac{t}{2}} \\ &\leq t_* + \left(1 - \frac{1}{\sqrt{s}} \right)^{-1}. \end{align}\] Since \(s = \min \left(1.01, 1 + \frac{1}{3n} \right)\), by convexity of \(u \mapsto \frac{1}{\sqrt{u}}\), \[\frac{1}{\sqrt{s}} \leq 1 - 100*\left(1 - \frac{1}{\sqrt{1.01}} \right) (s-1) \leq 1 - 0.496 \min \left(0.01, \frac{1}{3n} \right)\] and thus \[\left(1 - \frac{1}{\sqrt{s}} \right)^{-1} \leq \frac{\max(100,3n)}{0.496} \leq \max(202, 6.05 n).\] Moreover, by concavity of the logarithm, \[\log(s) \geq 100\times \log(1.01) \min \left(0.01, \frac{1}{3n} \right) \geq 0.995 \min \left(0.01, \frac{1}{3n} \right)\] and so \[t_* \leq \frac{\log(60.5)}{0.995} \max(100,3n) \leq \max\left(413, 12.37 n \right).\] This finally yields \[r(T) \leq \max \left(615, 18.42 n \right)\] as claimed.

8.5.5 Proof of Proposition 7↩︎

Consider now the specific case of the function \[g_x: \sigma \mapsto \sup_{t \in \mathcal{T}} \left\{ \sum_{i = 1}^n w_{\sigma(i)} t(x_i) \right\}.\] Define the set \[\mathcal{K}(x) = \overline{\left\{ (t(x_i))_{1 \leq i \leq n} : t \in \mathcal{T}\right\}} \subset \mathbb{R}^n\] which is closed and bounded (by assumption) and such that \[g_x(\sigma) = \sup_{z \in \mathcal{K}(x)} \sum_{i = 1}^n w_{\sigma(i)} z_i\;.\] As \(\mathcal{K}(x)\) is compact, we can choose for each \(\pi \in \mathfrak{S}_n\), \[\overline{z}(\pi) \in \underset{z \in \mathcal{K}(x)}{\mathrm{argmax}} \sum_{i = 1}^n w_{\pi(i)} z_i \;.\] Since \(\mathfrak{S}_n\) is finite, this does not raise measurability issues. Let \(\hat{z}\) denote the random variable \(\overline{z}(\sigma)\). Let \(I,J\) be independent and uniformly distributed on \(\{1,\ldots,n\}\), then \[\begin{align} g_x \left( \sigma \right) - g_x(\sigma \circ \tau_{I,J}) &\leq \sum_{i = 1}^n w_{\sigma(i)} \hat{z}_i - \sum_{i = 1}^n w_{(\sigma \circ \tau_{I,J})(i)} \hat{z}_i \\ &= w_{\sigma(I)} \hat{z}_{I} + w_{\sigma(J)} \hat{z}_J - w_{\sigma(J)} \hat{z}_I - w_{\sigma(I)} \hat{z}_J \\ &= \left(w_{\sigma(I)} - w_{\sigma(J)} \right) \left(\hat{z}_I - \hat{z}_J \right). \end{align}\] It follows that \[\left( g_x \left( \sigma \right) - g_x(\sigma \circ \tau_{I,J}) \right)_+^2 \leq \left[ \left(w_{\sigma(I)} - w_{\sigma(J)} \right) \left(\hat{z}_I - \hat{z}_J \right) \right]_+^2 \leq \left(w_{\sigma(I)} - w_{\sigma(J)} \right)^2 \left(\hat{z}_I - \hat{z}_J \right)^2.\] As a consequence, since \(\hat{z} =\overline{z}(\sigma)\) depends on \(\sigma\) but not on \(I,J\) and since \(V_+(g_x,\sigma)=n\mathbb{E}[ \left( g_x \left( \sigma \right) - g_x(\sigma \circ \tau_{I,J}) \right)_+^2\vert \sigma]\), we have \[V_+(g_x,\sigma) \leq n\sup_{t \in \mathcal{T}} \left\{ \mathbb{E} \left[ \left(w_{\sigma(I)} - w_{\sigma(J)} \right)^2 \left(t(x_I) - t(x_J) \right)^2 \bigl| \sigma \right] \right\} := W\;.\] If the quantities \(t(x_i)\) all belong to \([-1,1]\), then \[V_+(g_x,\sigma) \leq W \leq 4n \mathbb{E} \left[ \left(w_{\sigma(I)} - w_{\sigma(J)} \right)^2 | \sigma \right] = 8 \sum_{i = 1}^n w_i^2\;.\] In general, since \(w_i \in [a;b]\) for all \(i\in \left\{ 1,\ldots, n\right\}\) by definition, \[\begin{align} V_+(g_x,\sigma) &\leq n(b-a)^2 \sup_{t \in \mathcal{T}} \left\{ \mathbb{E} \left[ \left(t(x_I) - t(x_J) \right)^2 \bigl| \sigma \right] \right\} \\ &= n(b-a)^2 \sup_{t \in \mathcal{T}} \left\{ \frac{1}{n^2} \sum_{i = 1}^n \sum_{j = 1}^n (t(x_i) - t(x_j))^2 \right\} \\ &= 2(b-a)^2 \sup_{t \in \mathcal{T}} \left\{ \sum_{i = 1}^n (t(x_i) - \overline{t}_{x})^2 \right\}\;, \end{align}\] where \(\overline{t}_{x}\) denotes the empirical mean, \[\overline{t}_{x} = \frac{1}{n} \sum_{i = 1}^n t(x_i)\;.\] This concludes the proof of Proposition 7.

8.6 A version of Tolstikhin’s theorem using the method of exchangeable pairs↩︎

Let us recall first Tolstikhin’s concentration inequality ([59], see also [60]), which is a clever modification of a previous result by Bobkov ([58]).

The result describes the concentration of some functions defined on the symmetric group \(\mathfrak{S}_n\), \(n\geq 3\), and satisfying some invariance conditions. More precisely, let us state the definition of \((k,n)\)-symmetric functions.

Tostikhin’s result can expressed as follows.

The point of this section is to prove a version of Tolstikhin’s result using the method of exchangeable pairs. More precisely, we will prove the following theorem.

8.7 Proofs related to Section 5↩︎

8.8 Confidence regions for the mean: optimized version and proof↩︎

The following version of Theorem 10 handles the special case of symmetric random variables.

Theorem 15 yields Theorem 10 by setting \(\eta = 2\). Let us prove Theorem 15.

Assume that \(\left\| X_1 - \mu \right\| \leq M,\) then since \(\sum_{i = 1}^n \xi_i = 0\), \[\begin{align} \frac{n \hat{R}_n}{M} &= \mathbb{E} \left[\left\| \frac{1}{M} \sum_{i = 1}^n \xi_i(X_i-\mu) \right\| | X_1,\ldots,X_n \right] \\ &= \mathbb{E} \left[ \sup_{l \in \mathcal{B}^*} \left\{ \sum_{i = 1}^n \xi_i l\left( \frac{X_i-\mu}{M} \right) \right\} \Bigr| X_1,\ldots,X_n \right] \\ &= \overline{g}(X), \end{align}\] setting \(\mathcal{T}= \{x \mapsto l \left( \frac{x-\mu}{M} \right) : l \in \mathcal{B}^* \}\). Let \(\kappa =\mathbb{E}[|\xi_1|]\). By Theorem 4, with probability at least \(1 - e^{-x}\), \[\frac{n\hat{R}_n}{M} \geq \frac{n\mathbb{E}[\hat{R}_n]}{M} - \sqrt{12\kappa x \mathbb{E}[\hat{R}_n]} \sqrt{\frac{n}{M}}\] and \[\frac{n\hat{R}_n}{M} \leq \frac{n\mathbb{E}[\hat{R}_n]}{M} + \sqrt{12\kappa x \mathbb{E}[\hat{R}_n]} \sqrt{\frac{n}{M}} + 5 \kappa x\] which yields \[\begin{align} \hat{R}_n &\geq \mathbb{E}\left[\hat{R}_n \right] - \sqrt{12 \kappa M \mathbb{E}[\hat{R}_n]} \sqrt{\frac{x}{n}} \\ \hat{R}_n &\leq \mathbb{E}\left[\hat{R}_n \right] + \sqrt{12 \kappa M \mathbb{E}[\hat{R}_n]} \sqrt{\frac{x}{n}} + 5 \kappa M \frac{x}{n} \end{align}\] on events \(E_x^1, E_x^2\) each with probability \(\geq 1 - e^{-x}\). By lemma 8, on \(E_x^1,\) \[\mathbb{E}\left[\hat{R}_n \right] \leq \hat{R}_n + \sqrt{12 \kappa M} \sqrt{\frac{x}{n}} \sqrt{\hat{R}_n + 3\kappa M \frac{x}{n}} + 6\kappa M \frac{x}{n}.\] Hence, for any \(\theta > 0,\) \[\begin{align} \mathbb{E}\left[\hat{R}_n \right] &\leq (1+\theta) \hat{R}_n + \left(3\theta + \frac{3}{\theta} \right) \kappa M \frac{x}{n} + 6 \kappa M \frac{x}{n} \\ &\leq (1+\theta) \hat{R}_n + \left(\theta + \frac{1}{\theta} + 2 \right) 3\kappa M \frac{x}{n}. \addtocounter{equation}{1}\label{eq95conf95ubd95boot} \end{align}\tag{18}\] Moreover, by lemma 8, for any \(\theta \in [0,1],\) on \(E_x^2\) \[\begin{align} \mathbb{E}\left[\hat{R}_n \right] &\geq (1-\theta) \left( \hat{R}_n - 5 \kappa M \frac{x}{n} \right) - 3\kappa M \frac{x}{n} \left(\frac{1}{\theta} + \theta - 2 \right) \\ &= (1-\theta) \hat{R}_n - \kappa M \frac{x}{n} \left( \frac{3}{\theta} - 1 - 2\theta \right) \addtocounter{equation}{1}\label{eq95conf95lbd95boot} \end{align}\tag{19}\]

On the other hand, by Bousquet’s inequality [16] for the centered empirical process \[\begin{align} \frac{n}{M} \left\| \overline{X}_n - \mu \right\| &= \sup_{l \in \mathcal{B}^*} \left\{ \sum_{i = 1}^n l \left( \frac{X_i - \mu}{M} \right) \right\} \end{align}\] for any \(x > 0\), with probability at least \(1 - e^{-x},\) \[\frac{n}{M} \left\| \overline{X}_n - \mu \right\| \leq \frac{n}{M} \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \sqrt{2x\left(2\frac{n}{M} \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \frac{n \sigma_\mathcal{B}^2}{M^2} \right)} + \frac{2x}{3}\] which yields \[\left\| \overline{X}_n - \mu \right\| \leq \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \sqrt{\frac{2x}{n}} \sqrt{2M \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \sigma_\mathcal{B}^2} + \frac{2x M}{3 n}.\] where \(\sigma_\mathcal{B}^2\) is the “wimpy variance”, \[\sigma_\mathcal{B}^2 = \sup_{l \in \mathcal{B}^*} \left\{ \mathrm{Var}(l(X_1)) \right\}.\] Thus, for any \(\theta > 0\), \[\begin{align} \left\| \overline{X}_n - \mu \right\| &\leq (1+\theta) \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \frac{M x}{\theta n} + \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} + \frac{2x M}{3 n} \\ &\leq (1+\theta) \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} + \left(\frac{1}{\theta} + \frac{2}{3} \right) \frac{M x}{n} \end{align}\]

Let \(\eta = 1\) if \(X_1\) is symmetric about \(\mu\) and \(\eta = 2\) otherwise. Now, by Proposition 16 and since \(\mathbb{E}[(\xi_1)_+] = \frac{1}{2} \mathbb{E}[|\xi_1|] = \frac{\kappa}{2},\) \[\mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] \leq \frac{\eta}{\kappa} \mathbb{E}[\hat{R}_n],\] so combining the above bound with equation 18 yields \[\left\| \overline{X}_n - \mu \right\| \leq (1+\theta)^2 \frac{\eta}{\kappa} \hat{R}_n + \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} + \left( 3\eta \left(\frac{1}{\theta} + 3 + 3\theta + \theta^2 \right) + \frac{1}{\theta} + \frac{2}{3} \right) \frac{xM}{n}\] for any \(\theta > 0\), with probability at least \(1 - 2e^{-x}\). Finally, \[\left\| \overline{X}_n - \mu \right\| \leq (1+\theta)^2 \frac{\eta}{\kappa} \hat{R}_n + \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} + \left(\frac{3\eta + 1}{\theta} + 9\eta + 1 + 9 \eta \theta + 3 \eta \theta^2 \right) \frac{xM}{n}.\] Consider now the lower confidence bound. By the Klein-Rio lower bound [18], with probability at least \(1 - e^{-x}\), \[\frac{n}{M} \left\| \overline{X}_n - \mu \right\| \geq \frac{n}{M} \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] - \sqrt{2x\left(2\frac{n}{M} \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \frac{n \sigma_\mathcal{B}^2}{M^2} \right)} - 2x\] or equivalently, \[\left\| \overline{X}_n - \mu \right\| \geq \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] - \sqrt{\frac{2x}{n}} \sqrt{2M \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] + \sigma_\mathcal{B}^2} - 2M \frac{x}{n}.\] Thus, for any \(\theta \in [0,1],\) \[\begin{align} \left\| \overline{X}_n - \mu \right\| &\geq (1-\theta) \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] - \frac{Mx}{\theta n} - \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} - 2 \frac{Mx}{n} \\ &= (1-\theta) \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] - \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} - \left(\frac{1}{\theta} + 2 \right) \frac{Mx}{n} \end{align}\] By Proposition 17, \(\eta b \mathbb{E} \left[ \left\| \overline{X}_n - \mu \right\| \right] \geq \mathbb{E}[\hat{R}_n]\). It follows from equation 19 that on an event with probability at least \(1 - 2e^{-x}\), \[\begin{align} \left\| \overline{X}_n - \mu \right\| &\geq (1-\theta)^2 \frac{\hat{R}_n}{\eta b} - M \frac{\kappa x}{\eta b n} \left(\frac{3}{\theta} - 4 - \theta + 2\theta^2 \right) - \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} - \left(\frac{1}{\theta} + 2 \right) \frac{Mx}{n} \\ &\geq (1-\theta)^2 \frac{\hat{R}_n}{\eta b} - \sigma_\mathcal{B}\sqrt{\frac{2x}{n}} - \left(\frac{3\kappa}{\eta b} + 1 \right) \frac{xM}{\theta n} - \left(2 - 4 \frac{\kappa}{\eta b} + \theta^2 \frac{\kappa}{\eta b} \right) \frac{xM}{n} \end{align}\] which proves the lower bound.

8.9 Two-sample test: proof of Theorem 11↩︎

8.9.1 Main steps of the proof↩︎

Grant the notations of Section 7. Recall that we consider being under the alternative, where \(P\neq Q\), and that the goal is to control the test power, measured by the quantity \(\mathbb{P}(T_{n,m}(\mathcal{F})>\hat{q}_B(\alpha))\), with respect to the value of the distance \(d_\mathcal{F}(P,Q)\).

• Step 1: Relating the empirical quantile \(\hat{q}_B(\alpha)\) to the true distribution:

Denote \(T_{\xi}(Z)=\sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} \xi_i f(Z_i) \right\}\). Recall also that the quantity \(\hat{q}_B(\alpha)\) is the empirical \((1-\alpha)\)-quantile, for the left-continuous cumulative distribution function \(\hat{F}^{(\ell)}_B\), of the sample \((T_{\xi^{(b)}}(Z))_{b=0}^B\). Recall that \(\xi^{(0)}=w\) and \((\xi^{(b)})_{b=1}^B\) is an i.i.d. sample, with the same distribution as \(\xi=(w_{\sigma(i)})_{i=1}^{n+m}\) and independent of \(Z\) and \(\xi\). Hence \(\hat{q}_B(\alpha)\) should be close to the \((1-\alpha)\)-quantile of \(T_{\xi}\). The following lemma, the proof of which can be found in Section 8.9.2, quantifies the latter assertion.

Let us assume that \(\alpha, n\) and \(B\) are such that the right-hand side of Inequality (?? ) is smaller than one, and denote \(\alpha_B(\delta)\in (0,1)\) such that \[1-\alpha_B(\delta) = \left (1+\frac{1}{B}\right)\left(1-\alpha + \sqrt{\frac{3\alpha\log(1/\delta)}{B}}\right)\; .\]

• Step 2: Assessing the “true quantile” \(q_\delta(Z)\) by concentration of \(T_\xi(Z)\):

Let us now compute an admissible value for \(q_\delta(Z)\). To do so, we control the concentration of \(T_\xi(Z)\) in two steps. First, we apply Theorem 13 to obtain the concentration conditionally on \(Z\). Second, we apply Theorem 1, giving access to the concentration of \(\mathbb{E}[T_\xi(Z)\vert Z]\) around \(\mathbb{E}[T_\xi(Z)]\).

Note that the vector \(w\) has coordinates with two possible values, \(1/n\) and \(-1/m\). Hence, according to Theorem 13, we have, for any \(t\geq 0\), \[\begin{align} \mathbb{P}(T_\xi(Z)-\mathbb{E}[T_\xi(Z)\, \vert \, Z]\geq t \, \vert \, Z) &\leq \exp\left( -\frac{t^2}{8\left(\frac{1}{n}+\frac{1}{m}\right)^2} \max \left( \frac{1}{v_+(Z)}, \frac{n+m+2}{nm} \right) \right) \label{ineq95concen95g95x} \\ &\leq \exp \left(- \frac{t^2}{8 \Delta_{n,m}^2} \right) \;, \end{align}\tag{20}\] where \[v_+(Z) = \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} \left(f(Z_i) - \frac{1}{n+m} \sum_{j = 1}^{n+m} f(Z_j) \right)^2 \right\}\] and \[\label{eq95def95Delta-nm} \Delta_{n,m} = \min \left(2\left( \frac{1}{n} + \frac{1}{m} \right) \sqrt{2v_+(Z)}, 2\sqrt{2\left( \frac{1}{n} + \frac{1}{m} \right)} \right).\tag{21}\] By reparametrizing the inequality, we get, for any \(\beta\in (0,1)\), \[\label{concen95T95xi} \mathbb{P}\left(T_\xi(Z) \geq \mathbb{E}[T_\xi(Z)\, \vert \, Z]+ \Delta_{n,m} \sqrt{\log\left(\frac{1}{\beta}\right)}\Biggl|Z\right) \leq \beta\;.\tag{22}\] Hence, by taking \(\beta=\alpha_B\), we obtain \[1-F^{(\ell)}_{T_\xi(Z)}\left(\mathbb{E}[T_\xi(Z)\, \vert \, Z]+ \Delta_{n,m} \sqrt{\log\left(\frac{1}{\alpha_B}\right)}\right)\leq \alpha_B\;,\] which gives that the value \[\label{value95q95delta95Z} q_\delta(Z)= \mathbb{E}[T_\xi(Z)\, \vert \, Z]+ \Delta_{n,m} \sqrt{\log\left(\frac{1}{\alpha_B}\right)}\tag{23}\] works. In order to compare the values of \(T_{n,m}(\mathcal{F})\) and \(q_\delta(Z)\) with high probability, we will control each random variable separately, and in particular, relate each of those quantities to the distance \(d_\mathcal{F}(P,Q)\).

• Step 3: upper deviations of \(q_\delta(Z)\):

Using Theorem 1, we have, for any \(t>0\), \[\mathbb{P}\left(\mathbb{E}[T_\xi(Z)\, \vert \, Z]\geq \mathbb{E}[T_\xi(Z)]+2\sqrt{3\mathbb{E}[\vert \xi_1\vert]\mathbb{E}[T_\xi(Z)]t}+\frac{5\mathbb{E}[\vert \xi_1\vert]t}{2}\right) \leq \exp(-t).\] Using the fact that for any \(a,b, \kappa>0\), \(\sqrt{ab}<\kappa a+b(4\kappa)^{-1}\), together with the identity \(\mathbb{E}[\vert \xi_1\vert]=2/(n+m)\), we obtain, for any \(t,\kappa>0\), \[\label{concen95cond95exp95T95xi} \mathbb{P}\left(\mathbb{E}[T_\xi(Z)\, \vert \, Z]\geq (1+\kappa)\mathbb{E}[T_\xi(Z)]+\frac{6}{n+m}\left(1+\frac{1}{\kappa}\right)t\right) \leq \exp(-t).\tag{24}\] Taking \(\kappa = 1\) and combining with equation 23 yields \[\label{eq95ubd95q-delta95gen} q_\delta(Z) \leq 2\mathbb{E}[T_\xi(Z)] + \Delta_{n,m} \sqrt{ \log \left( \frac{1}{\alpha_B} \right)} + \frac{12}{n+m} \log \left( \frac{1}{\beta} \right)\tag{25}\] with probability no less than \(1 - \beta\). To bound \(\Delta_{n,m}\) with high probability, let us bound \(v_+(Z)\). By noticing that \[v_+(Z)=\frac{1}{2(n+m)}\sup_{f\in \mathcal{F}}\left\{ \sum_{i,j = 1}^{n+m} \left(f(Z_i) - f(Z_j) \right)^2 \right\}\;,\] we prove in Lemma 11 below that the function \(v_+/4\) is \((2,0)\)-self-bounding. Hence, by [16], we have for any \(t>0\), \[\mathbb{P}\left(v_{+}(Z) \geq \mathbb{E}[v_{+}(Z)]+4\sqrt{\mathbb{E}[v_{+}(Z)]t}+\frac{10t}{3} \right) \leq \exp(-t)\;,\] which implies, for any \(t,\kappa>0\), \[\label{concen95v4343} \mathbb{P}\left(v_{+}(Z) \geq (1+\kappa)\mathbb{E}[v_{+}(Z)]+4\left(1+\frac{1}{\kappa}\right)t\right) \leq \exp(-t)\;.\tag{26}\] Combining Inequalities (25 ) and (26 ) with \(t=\log(1/\beta)\) and \(\kappa=1\) together with Identity 21 , we get: for any \(\beta \in (0,1)\), with probability larger than \(1-2\beta\), \[\begin{align} &q_\delta(Z)\leq 2\mathbb{E}[T_\xi(Z)]+ \frac{12}{n+m}\log\left(\frac{1}{\beta}\right)+4\left(\frac{1}{n}+\frac{1}{m}\right)\sqrt{\left(\mathbb{E}[v_{+}(Z)]+4\log\left(\frac{1}{\beta}\right)\right) \log\left(\frac{1}{\alpha_B}\right)}\;. \end{align}\]

• Step 4: Control of the expectations:

By denoting \(Z^{(2)}_{i,j,f}=(f(Z_i)-f(Z_j))^2\), we have \[\mathbb{E}[v_{+}(Z)]\leq \frac{1}{2(n+m)} \mathbb{E}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{i,j=1}^{n+m} Z^{(2)}_{i,j,f}-\mathbb{E}\left[Z^{(2)}_{i,j,f}\right]\right\}\right] + \frac{1}{2(n+m)}\sup_{f\in \mathcal{F}} \left\{ \sum_{i,j=1}^{n+m} \mathbb{E}\left[Z^{(2)}_{i,j,f}\right] \right\}\;.\] Furthermore, \[\mathbb{E}\left[Z^{(2)}_{i,j,f}\right]=\mathop{\mathrm{var}}(f(Z_i))+\mathop{\mathrm{var}}(f(Z_j))+(\mathbb{E}[f(Z_i)]-\mathbb{E}[f(Z_j)])^2\;.\] Consequently, \[\begin{align} \frac{1}{2(n+m)}\sum_{i,j=1}^{n+m}\mathbb{E}\left[Z^{(2)}_{i,j,f}\right] & \leq \frac{n+m-1}{n+m} (n \mathop{\mathrm{var}}(f(X_1))+ m \mathop{\mathrm{var}}(f(Y_1)))+\frac{nm}{n+m}(Pf-Qf)^2\\ &\leq n \mathop{\mathrm{var}}(f(X_1))+ m \mathop{\mathrm{var}}(f(Y_1))+\frac{nm}{n+m}(Pf-Qf)^2\;. \end{align}\] In addition, let us denote \(\bar{f}_i=f(Z_i)-\mathbb{E}[f(Z_i)]\). Note that for both \(i<j\leq n\) and \(n<i<j\), \[Z^{(2)}_{i,j,f}=(\bar{f}_i-\bar{f}_j)^2\;.\] Also, for \(i\leq n<j\), \[Z^{(2)}_{i,j,f}-\mathbb{E}[Z^{(2)}_{i,j,f}]=(\bar{f}_i-\bar{f}_j)^2-\mathbb{E}[(\bar{f}_i-\bar{f}_j)^2]-2(Pf-Qf)(\bar{f}_i-\bar{f}_j)\;.\] Using these identities, we obtain \[\begin{align} &\mathbb{E}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{i,j=1}^{n+m} Z^{(2)}_{i,j,f}-\mathbb{E}\left[Z^{(2)}_{i,j,f}\right]\right\}\right] \nonumber\\ \leq& \mathbb{E}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{\substack{i,j=1}}^{n+m} (\bar{f}_i-\bar{f}_j)^2-\mathbb{E}\left[(\bar{f}_i-\bar{f}_j)^2\right]\right\}\right] + 4d_\mathcal{F}(P,Q)\mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\vert \sum_{i=1}^{n} \sum_{j=n+1}^{n+m} (\bar{f}_i-\bar{f}_j)\right\vert \right] \;.\nonumber \label{upper95square951}\\ \end{align}\tag{27}\] Now, for the first term at the right-hand side of Inequality (27 ), by expanding the quantities \((\bar{f}_i-\bar{f}_j)^2\), we obtain \[\begin{align} &\mathbb{E}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{\substack{i,j=1}}^{n+m} (\bar{f}_i-\bar{f}_j)^2-\mathbb{E}\left[(\bar{f}_i-\bar{f}_j)^2\right]\right\}\right]\\ = & \mathbb{E}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{\substack{i,j=1}}^{n+m} (\bar{f}^2_i-\mathbb{E}[\bar{f}_i^2]+ \bar{f}^2_j-\mathbb{E}[\bar{f}_j^2])-2\sum_{\substack{i,j=1}}^{n+m}\bar{f}_i\bar{f}_j+2\sum_{\substack{i,j=1}}^{n+m}\mathbb{E}[\bar{f}_i\bar{f}_j]\right\}\right]\\ = & \mathbb{E}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{\substack{i,j=1}}^{n+m} (\bar{f}^2_i-\mathbb{E}[\bar{f}_i^2]+ \bar{f}^2_j-\mathbb{E}[\bar{f}_j^2])-2\left(\sum_{\substack{i=1}}^{n+m}\bar{f}_i\right)^2+2\sum_{\substack{i=1}}^{n+m}\mathbb{E}[\bar{f}^2_i]\right\}\right]\\ \leq & 2(n+m) \mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\{\sum_{i=1}^{n+m} \bar{f}_i^2-\mathbb{E}[\bar{f}_i^2]\right\} \right]+2(n\mathop{\mathrm{var}}(f(X_1))+m\mathop{\mathrm{var}}(f(Y_1)))\\ \leq & 4(n+m)\mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\{\sum_{i=1}^{n+m} \varepsilon_i \bar{f}_i^2\right\} \right]+2(n\mathop{\mathrm{var}}(f(X_1))+m\mathop{\mathrm{var}}(f(Y_1)))\;, \end{align}\] where \((\varepsilon_i)_{i=1}^n\) is a collection of independent Rademacher variables, independent also of the \(Z_i\)’s. Note that, almost surely, \(\bar{f}_i \in [-2,2]\) for any \(i\in \left\{ 1,\ldots, n+m\right\}\), which gives by the contraction principle (conditionally to the \(Z_i\)’s and using that the function \(x\rightarrow x^2/4\) is a contraction on \([-2,2]\)), \[\begin{align} &\mathbb{E}\left[\sup_{f\in \mathcal{F}}\left\{\sum_{\substack{i,j=1}}^{n+m} (\bar{f}_i-\bar{f}_j)^2-\mathbb{E}\left[(\bar{f}_i-\bar{f}_j)^2\right]\right\}\right]\\ \leq & 16(n+m)\mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\{\sum_{i=1}^{n+m} \varepsilon_i \bar{f}_i\right\} \right]+2(n\mathop{\mathrm{var}}(f(X_1))+m\mathop{\mathrm{var}}(f(Y_1)))\\ \leq & 32 (n+m)\mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\vert\sum_{i=1}^{n+m} \bar{f}_i \right\vert \right] +2(n\mathop{\mathrm{var}}(f(X_1))+m\mathop{\mathrm{var}}(f(Y_1)))\\ \leq & 32 (n+m)(M_n(P)+M_m(Q))+2(n\mathop{\mathrm{var}}(f(X_1))+m\mathop{\mathrm{var}}(f(Y_1)))\;.\\ \end{align}\] As for the second term on the right-hand side of Inequality 27 , it holds \[\begin{align} \mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\vert \sum_{i=1}^{n} \sum_{j=n+1}^{n+m} (\bar{f}_i-\bar{f}_j)\right\vert \right] & \leq m \mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\vert \sum_{i=1}^{n} \bar{f}_i\right\vert \right]+n\mathbb{E}\left[ \sup_{f\in \mathcal{F}}\left\vert \sum_{j=n+1}^{n+m} \bar{f}_j\right\vert \right]\\ &=mM_n(P)+nM_m(Q)\;. \end{align}\] Putting things together and setting \(\alpha_k=k/(n+m)\) for \(k\in \{ n, m\}\) and \(V=\sup_{f\in \mathcal{F}} \left\{ n \mathop{\mathrm{var}}(f(X_1)) + m\mathop{\mathrm{var}}(f(Y_1)) \right\}\), we get \[\begin{align} \label{upper95v9543} &\mathbb{E}\left[v_+(Z)\right]\nonumber\\ \leq & 16 (M_n(P)+M_m(Q))+2d_\mathcal{F}(P,Q)(\alpha_m M_n(P)+\alpha_n M_m(Q))+\left(1+\frac{1}{n+m}\right)V+2\frac{nm}{n+m}d_\mathcal{F}^2(P,Q) \nonumber\\ \leq & 16 (M_n(P)+M_m(Q))+\left(\frac{1}{n}+\frac{1}{m}\right)(\alpha_m M_n(P)+\alpha_n M_m(Q))^2+\frac{3V}{2}+3\frac{nm}{n+m}d_\mathcal{F}^2(P,Q)\;, \end{align}\tag{28}\] where in the last inequality, we used the fact that for any \(a,b,\eta>0,\) \(2ab\leq \eta a^2+b^2/\eta\), by choosing \(\eta=(nm)/(n+m)\) – which gives \(1/\eta=1/n+1/m\) –, \(a=d_\mathcal{F}(P,Q)\) and \(b=\alpha_m M_n(P)+\alpha_n M_m(Q)\). Furthermore, one can note that \[\begin{align} & \left(\frac{1}{n}+\frac{1}{m}\right)(\alpha_m M_n(P)+\alpha_n M_m(Q))^2 \\ \leq & 2 \left(\frac{1}{n}+\frac{1}{m}\right)(\alpha^2_mM^2_n(P)+\alpha^2_nM^2_m(Q)) \\ = & \frac{2m}{n(n+m)} M^2_n(P)+ \frac{2n}{m(n+m)} M^2_m(Q)\;. \end{align}\] Plugging the latter upper-bound in the right-hand side of Inequality 28 , we get \[\mathbb{E}[v_+(Z)] \leq 16 (M_n(P)+M_m(Q))+\frac{2m}{n(n+m)} M^2_n(P)+ \frac{2n}{m(n+m)} M^2_m(Q)+ \frac{3V}{2}+\frac{3nm}{n+m}d_\mathcal{F}^2(P,Q)\;.\] We turn now to the control of the expectation of \(T_\xi(Z)\) under the alternative, where \(P\neq Q\). Define for any distribution \(R\) the quantity

\[\begin{align} \delta_{n,m}(R) & = \mathbb{E}_{Z \sim R^{\otimes (n+m)}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} \xi_i f(Z_i) \right\} \right]\\ & = \mathbb{E}_{Z \sim R^{\otimes (n+m)}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} \xi_i (f(Z_i)-R(f)) \right\} \right] \;, \end{align}\] where the latter equality comes from the condition \(\sum_{i = 1}^{n+m} \xi_i=0\). Define also \[\delta_{n,m}(R,S) = \mathbb{E}_{X \sim R^{\otimes n}} \mathbb{E}_{Y \sim S^{\otimes m}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n} \xi_i f(X_i) + \sum_{j = 1}^{m} \xi_{j+n} f(Y_j) \right\} \right],\] the expected value of the threshold when \(X\) follows the distribution \(R\) and \(Y\) follows a different distribution \(S\). We have the following result, proved in Section 8.9.2 below.

Note that, under the alternative, we have \(\mathbb{E}[T_\xi(Z)]=\delta_{n,m}(P,Q)\). Hence, Lemma 10 gives \[\label{ubd95Esp95T-xi-Z} \mathbb{E}[T_\xi(Z)] \leq \delta_{n,m}(P) + \delta_{n,m}(Q) + \frac{d_{\mathcal{F}}(P,Q)}{\sqrt{n+m-1}} .\tag{29}\] We also have, \[\begin{align} \delta_{n,m}(R) & = \mathbb{E}_{Z \sim R^{\otimes (n+m)}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} w_{\sigma(i)} (f(Z_i)-R(f)) \right\} \right]\\ & = \mathbb{E}_{Z \sim R^{\otimes (n+m)}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} w_{i} (f(Z_{\sigma^{-1}(i)})-R(f)) \right\} \right]\\ & = \mathbb{E}_{R^{\otimes (n+m)}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n+m} w_{i} (f(Z_{i})-R(f))\right\} \right]\; , \end{align}\] where the last identity comes from the exchangeability of the i.i.d. vector \((Z_1,\ldots,Z_n)\). Hence, by the sub-addivity of the supremum and the symmetry of \(\mathcal{F}\), we get \[\begin{align} \delta_{n,m}(R) &\leq \frac{1}{n} \mathbb{E}_{ R^{\otimes (n)}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{i = 1}^{n} (f(Z_{i})-R(f)) \right\} \right] + \frac{1}{m} \mathbb{E}_{ R^{\otimes (m)}} \left[ \sup_{f \in \mathcal{F}} \left\{ \sum_{j = 1}^{m} (f(Z_{i})-R(f)) \right\} \right]\\ &= \frac{M_n(R)}{n}+\frac{M_m(R)}{m} \;. \end{align}\]

• Step 5: Putting things together to bound \(q_\delta(Z)\) from above:

Putting the previous computations together, we get that, with probability at least \(1-2\beta\), \[\begin{align} &q_\delta(Z) \nonumber\\ &\leq \frac{2}{n}(M_n(P)+M_n(Q))+\frac{2}{m}(M_m(P)+M_m(Q))+\frac{2d_{\mathcal{F}}(P,Q)}{\sqrt{n+m-1}}+ \frac{12}{n+m}\log\left(\frac{1}{\beta}\right)+ \nonumber \\ &+ 4\left(\frac{1}{n}+\frac{1}{m}\right) \sqrt{\log\left(\frac{1}{\alpha_B}\right)} \times\nonumber \\ &\sqrt{16 (M_n(P)+M_m(Q))+\frac{2m}{n(n+m)} M^2_n(P)+ \frac{2n}{m(n+m)} M^2_m(Q)+\frac{3V}{2}+\frac{3nm}{n+m}d_\mathcal{F}^2(P,Q)+4\log\left(\frac{1}{\beta}\right)}\;. \label{upper95q95delta} \end{align}\tag{30}\] Moreover, from equations 25 , 29 and 21 , it follows that \[\begin{align} q_\delta(Z) &\leq \frac{2}{n}(M_n(P)+M_n(Q))+\frac{2}{m}(M_m(P)+M_m(Q))+\frac{2d_{\mathcal{F}}(P,Q)}{\sqrt{n+m-1}} \nonumber \\ &\quad + 2\sqrt{2\left(\frac{1}{n} + \frac{1}{m} \right) \log \left( \frac{1}{\alpha_B} \right)} + \frac{12}{n+m}\log\left(\frac{1}{\beta}\right) \label{ubd95qdelta95hoeff} \end{align}\tag{31}\]

• Step 6: deviations from below for \(T_{n,m}(\mathcal{F})\):

To control the power of the test, it remains to bound from below the statistic \(T=T_{n,m}(\mathcal{F})\). Fix some \(\varepsilon > 0\). Let \(f \in \mathcal{F}\) be such that \(Pf - Qf \geq d_{\mathcal{F}}(P,Q) - \varepsilon\). By definition of \(T,\) \[T \geq \frac{1}{n} \sum_{i = 1}^n f(X_i) - \frac{1}{m} \sum_{j = 1}^n f(Y_j) \geq \frac{1}{n} \sum_{i = 1}^n (f(X_i) - Pf) - \frac{1}{m} \sum_{j = 1}^m (f(Y_j) - Qf) + d_{\mathcal{F}}(P,Q) - \varepsilon.\] By Hoeffding’s inequality, with probability greater than \(1 - e^{-t}\), \[T \geq d_{\mathcal{F}}(P,Q) - \varepsilon - \sqrt{2t\left(\frac{1}{n} + \frac{1}{m} \right)}.\] Since this bound holds for any \(\varepsilon > 0\), it follows that with probability at least \(1 - \delta\), \[\label{lbd95test95stat95hoeff} T \geq d_{\mathcal{F}}(P,Q) - \sqrt{2\left(\frac{1}{n} + \frac{1}{m} \right)\log\left( \frac{1}{\delta} \right)}.\tag{32}\] Thus, if the right-hand side of Inequality 32 is greater than the right-hand side of 31 with \(\beta=\delta\), then \[\mathbb{P}(T>\hat{q}_B(\alpha)) \geq 1-3\delta.\] In other words, the type 2 error of the test is at most \(3\delta\). A few calculations show that this is ensured if \[\begin{align} &\left(1 - \frac{2}{\sqrt{n+m-1}} \right) d_{\mathcal{F}}(P,Q) \\ &\quad \geq \frac{2}{n}(M_n(P)+M_n(Q))+\frac{2}{m}(M_m(P)+M_m(Q))+ \frac{12}{n+m}\log\left(\frac{1}{\delta}\right) \\ &\quad + \sqrt{\frac{1}{n} + \frac{1}{m}} \left(2\sqrt{2\log \left( \frac{1}{\alpha_B} \right)} + \sqrt{2\log \left( \frac{1}{\delta} \right)} \right). \end{align}\] Let us now control the type 2 error by taking into account the variance terms. By Bernstein’s inequality, with probability greater than \(1 - e^{-t}\), \[\begin{align} T &\geq d_{\mathcal{F}}(P,Q) - \varepsilon - \sqrt{2t \left( \frac{\mathop{\mathrm{var}}(f(X_1))}{n} + \frac{\mathop{\mathrm{var}}(f(Y_1))}{m} \right)} - t \left( \frac{1}{n} \vee \frac{1}{m} \right) \\ &\geq d_{\mathcal{F}}(P,Q) - \varepsilon - \sqrt{2t \left( \frac{\sigma^2_P(\mathcal{F})}{n} + \frac{\sigma^2_Q(\mathcal{F})}{m} \right)} - t \left( \frac{1}{n} \vee \frac{1}{m} \right). \end{align}\] Again, this bound holds for any \(\varepsilon > 0\), which gives that, with probability at least \(1 - \delta\), \[\label{lbd95test95stat95alternative} T \geq d_{\mathcal{F}}(P,Q) - \sqrt{2\log\left(\frac{1}{\delta}\right) \left( \frac{\sigma^2_P(\mathcal{F})}{n} + \frac{\sigma^2_Q(\mathcal{F})}{m} \right)} - \log\left(\frac{1}{\delta}\right)\left( \frac{1}{n} \vee \frac{1}{m} \right).\tag{33}\] Thus, if the right-hand side of Inequality 33 is greater than the right-hand side of 30 with \(\beta=\delta\), then \[\mathbb{P}(T>\hat{q}_B(\alpha)) \geq 1-3\delta.\] A few basic calculations show that this is ensured if \[\begin{align} &\left(1 - \frac{2}{\sqrt{n+m-1}}-4\sqrt{3\left(\frac{1}{n}+\frac{1}{m}\right)\log\left(\frac{1}{\alpha_B}\right)} \right) d_{\mathcal{F}}(P,Q)\\ &\quad \geq \left(\frac{1}{n}\vee \frac{1}{m}\right)\log\left( \frac{1}{\delta}\right)+ \frac{2}{n}(M_n(P)+M_n(Q))+\frac{2}{m}(M_m(P)+M_m(Q))+ \frac{12}{n+m}\log\left(\frac{1}{\delta}\right) \\ &+ \sqrt{2\left( \frac{\sigma^2_P(\mathcal{F})}{n} + \frac{\sigma^2_Q(\mathcal{F})}{m} \right)\log\left(\frac{1}{\delta}\right)} +2\left(\frac{1}{n}+\frac{1}{m}\right)\sqrt{\log\left(\frac{1}{\alpha_B}\right)} \times \\ &\times\sqrt{\left(34 (M_n(P)+M_m(Q))+\frac{2m}{n(n+m)} M^2_n(P)+ \frac{2n}{m(n+m)} M^2_m(Q)+V+4\log\left(\frac{1}{\beta}\right)\right)}\;. \end{align}\] This complete the proof of Theorem 11.

8.9.2 Technical Lemmas↩︎

8.10 Proofs of corollaries of Theorem 11↩︎

8.10.1 Proof of Corollary 3↩︎

It follows from the work of Fournier and Guillin ([72] with \(p = 1\) and \(q = r > 2\)) that \[\frac{1}{l} M_l(R) \leq C_0 V_r(R) \frac{L_l}{l^\gamma}\] for all \(l \in \mathbb{N}\), any \(r > 2\) and any dimension \(d \geq 1\). Moreover, Theorem 11 applies since \(\mathcal{F}\) is a pointwise closed class of measurable functions valued in \([-1,1]\). We bound the terms of Equation ?? as follows. By Inequalities 8 and 9 , \[\frac{2}{n}(M_n(P)+M_n(Q))+\frac{2}{m}(M_m(P)+M_m(Q)) \leq 2C_0 \left( \frac{L_n}{n^\gamma} + \frac{L_m}{m^\gamma} \right) (V_r(P) + V_r(Q))\;.\] Moreover, we have seen that for two independent random vectors with distribution \(R\), \[\sigma_R^2(\mathcal{F}) \leq \frac{1}{2} \mathbb{E}[d(X,X')^2] \leq \frac{1}{2} \mathbb{E} \left[ (d(X,\mu) + d(\mu,X'))^2 \right] \leq \mathbb{E}\left[ d(X,\mu)^2 + d(X',\mu)^2 \right]\] from which it follows that \[\sigma^2_R(\mathcal{F}) \leq 2V_2(R)\] and \[\sqrt{2\left( \frac{\sigma^2_P(\mathcal{F})}{n} + \frac{\sigma^2_Q(\mathcal{F})}{m} \right)\log\left(\frac{1}{\delta}\right)} \leq 2 \sqrt{ \left(\frac{V_2(P)}{n} + \frac{V_2(Q)}{m} \right) \log\left(\frac{1}{\delta}\right)}\;.\] Consider now the sum \(S\) under the square root on the last line of Equation ?? . Since \[V \leq n\sigma^2_P(\mathcal{F}) + m\sigma_Q^2(\mathcal{F}) \leq 2(nV_2(P) + mV_2(Q)) \leq 2n(V_2(P) + \rho V_2(Q))\] and \[\begin{align} \frac{2m}{n(n+m)} M_n^2(P) + \frac{2n}{m(n+m)} M_m^2(Q) &\leq \frac{2m}{n(n+m)} 2n M_n(P) + \frac{2n}{m(n+m)} 2m M_m(Q) \\ &\leq 4(M_n(P) + M_m(Q))\;, \end{align}\] it follows that \[\begin{align} 2\left(\frac{1}{n} + \frac{1}{m}\right)\sqrt{S} &\leq \frac{4}{n} \sqrt{38(M_n(P) + M_m(Q)) + 2n(V_2(P) + \rho V_2(Q)) + 4\log\left( \frac{1}{\delta} \right)} \\ &\leq \frac{4}{\sqrt{n}} \sqrt{2(V_2(P) + \rho V_2(Q))} + \frac{4}{n} \sqrt{38C_0 \left( L_n n^{1-\gamma} V_r(P) + L_m (m)^{1-\gamma} V_r(Q) \right)} \\ &\quad + \frac{8}{n} \sqrt{\log \left( \frac{1}{\delta} \right)} \\ &\leq \frac{4}{\sqrt{n}} \sqrt{2(V_2(P) + \rho V_2(Q))} + \frac{C\sqrt{L_n}}{n^{\frac{1+\gamma}{2}}} + \frac{8}{n} \sqrt{\log \left( \frac{1}{\delta} \right)}\;, \end{align}\] where \(C\) depends on \(C_0,\rho,V_r(P)\) and \(V_r(Q)\). The remaining terms on the right-hand side of Equation ?? are of order \[\frac{1}{n} \log \left( \frac{1}{\delta} \right).\]

8.10.2 Proof of Corollary 4↩︎

8.11 Bounds for the expectation of the supremum of the bootstrap empirical process↩︎

The following upper and lower bounds for the mean of the supremum of the exchangeable bootstrap empirical process are instrumental in our proofs related to sections 6 and 7. We believe that they are folklore results. Nonetheless, for the sake of completeness, we provide complete proofs.

In particular, they are consequences of the most advanced results, that are due to Han and Wellner ([35]).

Let us start with a universal lower bound.

Proposition 16 can be compared, for instance, with the lower bound of Lemma 2.9.1 in [4]. One may indeed notice that the proof of the latter lemma, which proceeds with similar arguments as our proof below, does not require that the weights be independent. One can also notice that exchangeability of the weights is not required in Proposition 16.

When the weights are bounded, it is also possible to give simple upper bounds by a symmetrization argument. Such results will be sufficient for our needs. Further results related to unbounded weights can be found in [35].

References↩︎