Robust estimation of U-statistics

Introduction

By a classical inequality of Hoeffding (1963), for a bounded kernel $h$, for all $\delta>0$,

and we also have the “Bernstein-type” inequality

where $\sigma^{2}=\text{Var}\left(h(X_{1},\ldots,X_{m})\right)$.

A symmetric kernel $h$ is said to be $P$-degenerate of order $q-1$, $1<q\leq m$, if for all $x_{1},\ldots,x_{q-1}\in\mathcal{X}$,

is not a constant function. In the special case of $m_{h}=0$ and $q=m$ (i.e., when the kernel is $(m-1)$-degenerate, $h$ is said to be $P$-canonical. $P$-canonical kernels appear naturally in the Hoeffding decomposition of a $U$-statistic, see de la Peña and Giné (1999).

Arcones and Giné (1993) proved the following important improvement of Hoeffing’s inequalities for canonical kernels: If $h-m_{h}$ is a bounded, symmetric $P$-canonical kernel of $m$ variables, there exist finite positive constants $c_{1}$ and $c_{2}$ depending only on $m$ such that for all $\delta\in(0,1)$,

In the special case of $P$-canonical kernels of order $m=2$, (3) implies that

with probability at least $1-\delta$. Note that this rate of convergence is significantly faster than the rate $O_{p}(n^{-1/2})$ implied by (2).

The next example illustrates why classical $U$-statistics fail under heavy-tailed distributions.

(see Zolotarev (1986), Nolan (2015)). Then it follows from the properties of $\alpha$-stable distributions (summarized in Proposition 9 in the Appendix) that there exists a constant $c>0$ depending only on $\alpha$ and $\gamma$ such that

and therefore there is no hope to reproduce an upper bound like (5). Below we show how this problem can be dealt with by replacing the $U$-statistics by a more robust estimator.

Our approach is based on robust mean estimators in the univariate setting. Estimation of the mean of a possibly heavy-tailed random variable $X$ from i.i.d. sample $X_{1},\ldots,X_{n}$ has recently received increasing attention. Introduced by Nemirovsky and Yudin (1983), the median-of-means estimator takes a confidence level $\delta\in(0,1)$ and divides the data into $V\approx\log\delta^{-1}$ blocks. For each block $k=1,\ldots,V$, one may compute the empirical mean $\widehat{\mu}_{k}$ on the variables in the block. The median $\overline{\mu}$ of the $\widehat{\mu}_{k}$ is the so-called median-of-means estimator. A short analysis of the resulting estimator shows that

with probability at least $1-\delta$ for a numerical constant $c$. For the details of the proof see Lerasle and Oliveira (2011). When the variance is infinite but a moment of order $1<p\leq 2$ exists, the median-of means estimator is still useful, see Bubeck et al. (2013). This estimator has recently been studied in various contexts. $M$-estimation based on this technique has been developed by Lerasle and Oliveira (2011) and generalizations in a multivariate context have been discussed by Hsu and Sabato (2013) and Minsker (2015). A similar idea was used in Alon et al. (2002). An interesting alternative of the median-of-means estimator has been proposed by Catoni (2012).

The rest of the paper is organized as follows. In Section 2 we introduce a robust estimator of the mean $m_{h}$ and present performance bounds. In particular, Section 2.1 deals with the finite variance case. Section 2.2 is dedicated to case when $h$ has a finite $p$-th moment for some $1<p<2$ for $P$-degenerate kernels. Finally, in Section 3, we present an application to clustering problems.

Robust U𝑈U-estimation

The estimator has a parameter $V\leq n$, the number of blocks. A partition $\mathcal{B}=(B_{1},\ldots,B_{V})$ of $\{1,\ldots,n\}$ is called regular if for all $K=1,\ldots,V$,

For any $B_{i_{1}},\ldots,B_{i_{m}}$ in $\mathcal{B}$, we set

Note that, mostly in order to simplify notation, we only take those values of $U_{B_{i_{1}},\ldots,B_{i_{m}}}(h)$ into account that correspond to distinct indices $i_{1}<\cdots<i_{m}$. Thus, each $U_{B_{i_{1}},\ldots,B_{i_{m}}}(h)$ is a so-called decoupled $U$-statistics (see the Appendix for the definition). One may incorporate all $m$-tuples (not necessarily with distinct indices) in the computation of the median. However, this has a minor effect on the performance. Similar bounds may be proven though with a more complicated notation.

A simpler alternative is obtained by taking only “diagonal” blocks into account. More precisely, let $U_{B_{i}}(h)$ be the $U$-statistics calculated using the variables in block $B_{i}$ (as defined in (1)). One may simply calculate the median of the $V$ different $U$-statistics $U_{B_{i}}(h)$. This version is easy to analyze because \big{|}\{i\leq V\ :U_{B_{i}}(h)\geq b\}\big{|} is a sum of independent random variables. However, this simple version is wasteful in the sense that only a small fraction of possible $m$-tuples are taken into account.

In the next two sections we analyze the performance of the estimator $\overline{U}_{\mathcal{B}}(h)$.

Next we present a performance bound of the estimator $\overline{U}_{\mathcal{B}}(h)$ in the case when $\sigma^{2}$ is finite. The somewhat more complicated case of infinite second moment is treated in Section 2.2.

where $K_{m}=2^{\frac{7}{2}m+1}m^{\frac{m}{2}}$.

When $q=m$, the kernel $h-m_{h}$ is $P$-canonical and the rate of convergence is then given by $(\log\delta^{-1}/n)^{m/2}$. Thus, the new estimator has a performance similar to standard $U$-statistics as in (3) and (4) but without the boundedness assumption for the kernel. It is important to note that a disadvantage of the estimator $\overline{U}_{\mathcal{B}}(h)$ is that it depends on the confidence level $\delta$ (through the number of blocks). For different confidence levels, different estimators are used.

Because of its importance in applications, we spell out the special case when $m=q=2$. In Section 3 we use this result in an example of cluster analysis.

where $\delta_{x}$ denotes the Dirac measure at the point $x$. Observe that $\pi_{0}h=P^{m}h$ and for $k>0$, $\pi_{k}h$ is a $P$-canonical kernel. $h$ can be decomposed as

If $h$ is assumed to be square-integrable (i.e., $P^{m}h^{2}<\infty$), the terms in (9) are orthogonal. If $h$ is degenerate of order $q-1$, then for any $1\leq k\leq q-1$, $\pi_{k}h=0$.

We begin with a “weak” concentration result on each $U_{B_{i_{1}},\ldots,B_{i_{m}}}(h)$. Let $B_{i_{1}},\ldots,B_{i_{m}}$ be elements of $\mathcal{B}$. For any $B\in\mathcal{B}$, we have $\frac{n}{2|\mathcal{B}|}\leq|B|\leq\frac{2n}{|\mathcal{B}|}$. We denote by $\mathbf{k}=(k_{1},\ldots,k_{m})$ an element of $I_{B_{i_{1}},\ldots,B_{i_{m}}}$. We have, by the above-mentioned orthogonality property,

The last inequality is obtained by counting, for any fixed $\mathbf{k}$ and $t$, the number of elements $\mathbf{l}$ such that $|\mathbf{k}\cap\mathbf{l}|=t$. Thus,

Combining the two displayed equations above,

By Chebyshev’s inequality, for all $r\in(0,1)$,

We set $x=2^{m}\sigma\frac{|\mathcal{B}|^{q/2}}{n^{q/2}r^{1/2}}$, and

Since $|\mathcal{B}|\geq 32m\log(\delta^{-1})$, with probability at least $1-\delta$, we have

with $K_{m}=2^{\frac{7}{2}m+1}m^{\frac{m}{2}}$. The upper bound for the lower tail holds by the same argument. ∎

2 Bounded moment of order p𝑝p with 1<p≤21𝑝21<p\leq 2

In this section, we weaken the assumption of finite variance and only assume the existence of a centered moment of order $p$ for some $1<p\leq 2$. The outline of the argument is similar as in the case of finite variance. First we obtain a “weak” concentration inequality for the $U$-statistics is each block and then use the property of the median to boost the weak inequality. While for the case of finite variance weak concentration could be proved by a direct calculation of the variance, here we need the randomization inequalities for convex functions of $U$-statistics established by de la Peña (1992) and Arcones and Giné (1993). Note that, here, a $P$-canonical technical assumption is needed.

Another use of (11) with $t=r=\frac{1}{4}$ gives

To see why the bound of Theorem 3 gives essentially the right order of magnitude, consider again the example described in the introduction, when $m=2$, $h(X_{1},X_{2})=X_{1}X_{2}$, and the $X_{i}$ have an $\alpha$-stable law $S(\gamma,\alpha)$ for some $\gamma>0$ and $1<\alpha\leq 2$. Note that an $\alpha$-stable random variable has finite moments up to (but not including) $\alpha$ and therefore we may take any $p=\alpha-\epsilon$ for any $\epsilon\in(0,1-\alpha)$. As we noted it in the introduction, there exists a constant $c$ depending on $\alpha$ and $\gamma$ only such that for all $1\leq i_{1}<i_{2}\leq V$,

and therefore (15) is essentially the best rate one can hope for.

Cluster analysis with U𝑈U-statistics

In this section we illustrate the use of the proposed mean estimator in a clustering problem when the presence of possibly heavy-tailed data requires robust techniques.

Let $\Pi_{K}$ be a finite class of partitions $\mathcal{P}$ of $\mathcal{X}$ into $K$ cells and define $W^{*}=\min_{\mathcal{P}\in\Pi_{K}}W(\mathcal{P})$.

Given $X_{1},\ldots,X_{n}$ be i.i.d. random variables distributed as $X$, the goal is to find a partition $\mathcal{P}\in\Pi_{K}$ with risk as close to $W^{*}$ as possible. A natural idea–and this is the approach of Clémençon (2014)–is to estimate $W(\mathcal{P})$ by the $U$-statistics

and choose a partition minimizing the empirical clustering risk $\widehat{W}_{n}(\mathcal{P})$. Clémençon (2014) uses the theory of $U$-processes to analyze the performance of such minimizers of $U$-statistics. However, in order to control uniform deviations of the form $\sup_{\mathcal{P}\in\Pi_{K}}|\widehat{W}_{n}(\mathcal{P})-W(\mathcal{P})|$, exponential concentration inequalities are needed for $U$-statistics. This restricts one to consider bounded dissimilarity measures $D(X,X^{\prime})$. When $D(X,X^{\prime})$ may have a heavy tail, we propose to replace $U$-statistics by the median-of-means estimators of $W(\mathcal{P})$ introduced in this paper.

Let $\mathcal{B}$ be a regular partition of $\{1,\ldots,n\}$ and define the median-of-means estimator $\overline{W}_{\mathcal{B}}(\mathcal{P})$ of $W(\mathcal{P})$ as in (6). Then Theorem 1 applies and we have the following simple corollary.

Once uniform deviations of $\overline{W}_{\mathcal{B}}(\mathcal{P})$ from its expected value are controlled, it is a routine exercise to derive performance bounds for clustering based on minimizing $\overline{W}_{\mathcal{B}}(\mathcal{P})$ over $\mathcal{P}\in\Pi_{K}$.

Let $\widehat{\mathcal{P}}=\mathop{\rm argmin}_{\mathcal{P}\in\Pi_{K}}\overline{W}_{\mathcal{B}}(\mathcal{P})$ denote the empirical minimizer. (In case of multiple minimizers, one may select one arbitrarily.) Now for any $\mathcal{P}_{0}\in\Pi_{K}$,

This result is to be compared with Theorem 2 of Clémençon (2014). Our result holds under the only assumption that $D(X,X^{\prime})$ has a finite second moment. (This may be weakened to assuming the existence of a finite $p$-th moment for some $1<p\leq 2$ by using Theorem 3). On the other hand, our result holds only for a finite class of partitions while Clémençon (2014) uses the theory of $U$-processes to obtain more sophisticated bounds for uniform deviations over possibly infinite classes of partitions. It remains a challenge to develop a theory to control processes of median-of-means estimators–in the style of Arcones and Giné (1993)–and not having to resort to the use of simple union bounds.

In the rest of this section we show that, under certain “low-noise” assumptions, analogous to the ones introduced by Mammen and Tsybakov (1999) in the context of classification, to obtain faster rates of convergence. In this part we need bounds for $P$-canonical kernels and use the full power of Corollary 2. Similar arguments for the study of minimizing $U$-statistics appear in Clémençon et al. (2008), Clémençon (2014).

We assume the following conditions, also considered by Clémençon (2014):

There exists $\mathcal{P}^{*}$ such that $W(\mathcal{P}^{*})=W^{*}$

There exist $\alpha\in$ and $\kappa<\infty$ such that for all $\mathcal{P}\in\Pi_{K}$ and for all $x\in\mathcal{X}$,

Note that $\alpha\leq 2$ since by the Cauchy-Schwarz inequality,

The proof Corollary 5 is postponed to the Appendix.

Appendix

Here we summarize some of the key tools for analyzing $U$-statistics that we use in the paper. For an excellent exposition we refer to de la Peña and Giné (1999).

Let $\{X_{i}\}$ be i.i.d. random variables taking values in $\mathcal{X}$ and let $\{X_{i}^{k}\},\ k=1,\ldots,m$, be sequences of independent copies. Let $\Phi$ be a non-negative function. As a corollary of Theorem 3.1.1 in de la Peña and Giné (1999) we have the following:

where $C_{m}=2^{m}(m^{m}-1)((m-1)^{m-1}-1)\times\cdots\times 3$. Moreover, if the kernel $h$ is symmetric, then,

An equivalent result for tail probabilities of $U$-statistics is the following (see Theorem 3.4.1 in de la Peña and Giné (1999)):

Under the same hypotheses as Theorem 6, there exists a constant $C_{m}$ depending on $m$ only such that, for all $t>0$,

If moreover, the kernel $h$ is symmetric then there exists a constant $c_{m}$ depending on $m$ only such that, for all $t>0$,

The next Theorem is a direct corollary of Theorem 3.5.3 in de la Peña and Giné (1999).

where $C_{m}=2^{mp}$ and $c_{m}=2^{-mp}$.

The same conclusion holds for decoupled $U$-statistics.

2 α𝛼\alpha-stable distributions

$f_{\gamma,\alpha}(x)$ is an even function.

$f_{\gamma,\alpha}(x)\underset{x\to+\infty}{\sim}\alpha\gamma^{\alpha}c_{\alpha}x^{-\alpha-1}$ with $c_{\alpha}=\sin(\frac{\pi\alpha}{2})\Gamma(\alpha)/\pi$.

$S_{n}$ has a $\alpha$-stable law $S(\gamma n^{1/\alpha},\alpha)$.

(i) and (iv) follow directly from the definition. (ii) is proved in the introduction of Zolotarev (1986). (iii) is a consequence of (ii). ∎

3 Proof of Corollary 5

Define $\Lambda_{n}(\mathcal{P})=\widehat{W}_{n}(\mathcal{P})-W^{*}$, the $U$-statistics based on the sample $X_{1},\ldots,X_{n}$, with symmetric kernel

We denote by $\Lambda(\mathcal{P})=W(\mathcal{P})-W^{*}$ the expected value of $\Lambda_{n}(\mathcal{P})$. The main argument in the following analysis is based on the Hoeffding decomposition. For all partitions $\mathcal{P}$,

Simple computations show that $\text{Var}\left(h^{(2)}(X_{1},X_{2})\right)=2\text{Var}\left(h^{(1)}(X)\right)$ and therefore,

Using again (11) with $r=\frac{1}{4}$, by $|B|\geq\frac{n}{128\left\lceil\log(N/\delta)\right\rceil}$, there exists a constant $C$ such that for any $\mathcal{P}\in\Pi_{K}$, with probability at least $1-2\delta/N$,

with probability at least $1-2\delta$. Using (17), we obtain

References