Tail Bounds for Canonical $U$-Statistics and $U$-Processes with Unbounded Kernels^††thanks: An initial version of this work was available here. This draft is a revised version with some edits.

In this paper, we study moment and tail bounds of second-order degenerate $U$-statistics and $U$-processes. Averages, the simplest function of a collection of random variables, are sums with each summand depending only on one element of the collection. On the other hand, $U$-statistics depend on tuples of elements in the collection. Formally, second-order $U$-statistics based on the collection of random variables $Z_{1},\ldots,Z_{n}$ is of the form

$${U}_{n}=\sum_{1\leq i\neq j\leq n}f_{i,j}(Z_{i},Z_{j}),$$

(1)

for some functions $\{f_{i,j}:\,1\leq i\neq j\leq n\}$. In this paper, we consider $U$-statistics defined on independent but possible non-identically distributed random variables $Z_{1},\ldots,Z_{n}$ defined on some measurable space. $U$-statistics, in general, are ubiquitous in statistical applications including, e.g., goodness-of-fit tests, two-sample tests using kernel-based distances as well as independence testing via permutation tests; see Kim, (2020) for an overview of this literature.

We motivate our interest in $U$-statistics using a few prototypical examples. Suppose $X_{1},\ldots,X_{n}$ are independent and identically distributed (i.i.d.) realizations of a random vector $X\in\mathbb{R}^{p}$ with Lebesgue density $f$. Consider the problem of estimating the quadratic functional

$$\Gamma(f):=\int_{\mathbb{R}^{p}}f^{2}(x)dx=\mathbb{E}\left[f(X)\right].$$

(2)

A natural estimator for this functional is given by

$$\widehat{\Gamma}(f):=\frac{1}{n(n-1)h_{n}^{p}}\sum_{1\leq i\neq j\leq n}K\left(\frac{X_{i}-X_{j}}{h_{n}}\right)=\frac{1}{n}\sum_{i=1}^{n}\widehat{f}^{(-i)}(X_{i}),$$

(3)

where $h_{n}$ represents the bandwidth and $\widehat{f}^{(-i)}(\cdot)$ represents the leave-one-out kernel density estimator:

$$\widehat{f}^{(-i)}(x)=\frac{1}{(n-1)h_{n}^{p}}\sum_{j=1,j\neq i}^{n}K\left(\frac{X_{j}-x}{h_{n}}\right).$$

(4)

Here the function $K(\cdot)$ is assumed to be symmetric and satisfies $\int_{\mathbb{R}^{p}}K(x)dx=1$. This estimator was introduced by Hall and Marron, (1987) and was studied thoroughly (in terms of adaptivity) for $p=1$ in Giné and Nickl, (2008).

Similarly, to estimate integrals involving the conditional expectation function from i.i.d. realizations $(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$ of $(X,Y)$, the following $U$-statistics appears:

$${U}_{n}^{\star}:=\frac{1}{n(n-1)h_{n}^{p}}\sum_{1\leq i\neq j\leq n}Y_{i}K\left(\frac{X_{i}-X_{j}}{h_{n}}\right)Y_{j}.$$

(5)

Aside from these prototypical examples, various other examples of such $U$-statistics are encountered in the literature on integral approximation involving kernel smoothing estimators (Newey and Ruud,, 2005; Delyon and Portier,, 2016) and the semiparametric inference literature on quadratic and integral-type functionals (Robins et al.,, 2016). In the latter literature, $U$-statistics of this type – especially in their degenerate form (see below for the definition) – are fundamentally involved in the analysis of so-called doubly robust estimators of certain functionals encountered in missing data or causal inference problems (Robins et al.,, 1994; Bang and Robins,, 2005), as well as in the literature on adaptive estimation of functionals based on so-called higher order influence functions (Robins et al.,, 2008, 2017; Liu et al.,, 2021).

Apart from the nonparametric and semiparametric statistics literature, second order $U$-statistics also arise in relation to Hanson-Wright-type inequalities. The classical Hanson-Wright inequality concerns tail bounds for the quadratic form $G^{\top}AG$ where $G$ is a standard multivariate normal random vector in $\mathbb{R}^{n}$ and $A\in\mathbb{R}^{n\times n}$ is a positive semi-definite matrix; see Theorem 3.1.9 of Giné and Nickl, (2016). For further applications of Hanson-Wright inequalities, see Rudelson and Vershynin, (2013) and Spokoiny and Zhilova, (2013), as well as the recent work of He et al., (2024) on sparse random vectors. Note that for any random vector $Y\in\mathbb{R}^{n}$ and matrix $A\in\mathbb{R}^{n\times n}$

$$Y^{\top}AY=\sum_{1\leq i,j\leq n}Y_{i}A(i,j)Y_{j},$$

(6)

where $A(i,j)$ represents the $i$-th row, $j$-th column entry in the matrix $A.$

Motivated by the examples above, we study the properties of the $U$-statistic $U_{n}$. Before proceeding further, we briefly discuss degenerate and non-degenerate $U$-statistics. See Serfling, (1980, Chapter 5) for more details. This discussion proves that for a precise understanding of the tail behavior of a $U$-statistics it suffices to consider degenerate $U$-statistics. In fact, most of the asymptotic normality results related to $U$-statistics are shown by proving asymptotic negligebility of the degenerate $U$-statistics compared to the linear statistic; see, for example, Chen and Kato, (2020). This paper is partly motivated by the cases where such asymptotic negligebility may not hold. For example, in the context of estimating $\mu^{2}$ based on IID observations $X_{1},\ldots,X_{n}$ with mean $\mu$, the unbiased estimator $\binom{n}{2}^{-1}\sum_{i\neq j}X_{i}X_{j}$ exhibits a phase transition at $\mu=O(n^{-1/2})$ in terms of rate and also the limiting distribution.

We prove two tail bounds for degenerate $U$-statistics. The first is a general result applicable to all kernels that are bounded above by a product kernel and the second result is for more structured kernels that are of importance in non- and semi-parametric estimation. Define a random variable $W$ to be sub-Weibull of order $\alpha>0$ if $\left\lVert W\right\rVert_{\psi_{\alpha}}<\infty,$ where $\psi_{\alpha}(x)=\exp(x^{\alpha})-1$ for $x\geq 0$ and

$$\left\lVert W\right\rVert_{\psi_{\alpha}}=\inf\left\{C\geq 0:\,\mathbb{E}\left[\psi_{\alpha}\left(|W|/C\right)\right]\leq 1\right\}.$$

Several properties of sum of independent sub-Weibull random variables are derived in Kuchibhotla and Chakrabortty, (2022). The main focus of this section is to extend these results to degenerate $U$-statistics.

Consider a degenerate $U$-statistics

$$U_{n}^{D}:=\sum_{1\leq i\neq j\leq n}f_{i,j}(Z_{i},Z_{j}),$$

where $Z_{1},\ldots,Z_{n}$ are independent random variables and $\{f_{i,j}(\cdot,\cdot):\,1\leq i\neq j\leq n\}$ is a collection of degenerate (or canonical) kernels, i.e.,

$$\mathbb{E}[f_{i,j}(Z_{i},Z_{j})|Z_{i}]=0=\mathbb{E}[f_{i,j}(Z_{i},Z_{j})|Z_{j}].$$

We assume the following on the degenerate kernel $f_{i,j}$:

1. (A1)

   For $1\leq i\neq j\leq n$, there exist non-negative functions $F_{i}(\cdot)$ and $G_{j}(\cdot)$ such that

   $$|f_{i,j}(Z_{i},Z_{j})|\leq F_{i}(Z_{i})G_{j}(Z_{j})\quad\mbox{and}\quad\|F_{i}(Z_{i})\|_{\psi_{\alpha}}\leq K_{F},\;\|G_{j}(Z_{j})\|_{\psi_{\beta}}\leq K_{G}.$$

The first part of assumption (A1) implies that the degenerate kernel $f_{i,j}$ can be expressed as $f_{i,j}(Z_{i},Z_{j})=F_{i}(Z_{i})w_{i,j}(Z_{i},Z_{j})G_{j}(Z_{j})$ for some collection of bounded kernels $\{w_{i,j}:1\leq i\neq j\leq n\}$. No further structure on $w_{i,j}$’s is required. In the second result we consider below, we place additional structure on $w_{i,j}$’s. The second part of assumption (A1) means that

$$\mathbb{E}\left[\exp\left(\frac{|F_{i}(Z_{i})|^{\alpha}}{K_{F}^{\alpha}}\right)\right]\leq 2\quad\mbox{and}\quad\mathbb{E}\left[\exp\left(\frac{|G_{j}(Z_{j})|^{\beta}}{K_{G}^{\beta}}\right)\right]\leq 2.$$

Equivalently, $F_{i}(Z_{i})$ is sub-Weibull$(\alpha)$ and $G_{j}(Z_{j})$ is sub-Weibull$(\beta)$, in the terminology of Kuchibhotla and Chakrabortty, (2022). To present the result, we define a few quantities. Let $(Z_{1}^{\prime},Z_{2}^{\prime},\ldots,Z_{n}^{\prime})$ be an independent copy of $(Z_{1},\ldots,Z_{n})$.

$$\begin{split}\Lambda_{1/2}&:=\left(\mathbb{E}\left[\sum_{1\leq i\neq j\leq n}f_{i,j}^{2}(Z_{i},Z_{j})\right]\right)^{1/2},\\ \Lambda_{1}&=\|(f_{i,j})\|_{L^{2}\to L^{2}},\\ &:=\sup\left\{\mathbb{E}\sum_{1\leq i\neq j\leq n}f_{i,j}(Z_{i},Z_{j}^{\prime})\gamma_{i}(Z_{i})\delta_{j}(Z_{j}^{\prime}):\,\sum_{i=1}^{n}\mathbb{E}[\gamma_{i}^{2}(Z_{i})]\leq 1,\sum_{j=1}^{n}\mathbb{E}[\delta_{j}^{2}(Z_{j}^{\prime})]\leq 1\right\},\\ \Lambda_{\alpha}&:=\max_{1\leq i\leq n}\bigg{\|}\sum_{1\leq j\leq n,j\neq i}\mathbb{E}[f_{i,j}^{2}(Z_{i},Z_{j}^{\prime})|Z_{i}]\bigg{\|}_{\psi_{\alpha/2}}^{1/2},\\ \Lambda_{\beta}&:=\max_{1\leq j\leq n}\bigg{\|}\sum_{1\leq i\leq n,i\neq j}\mathbb{E}[f_{i,j}^{2}(Z_{i},Z_{j}^{\prime})|Z_{j}^{\prime}]\bigg{\|}_{\psi_{\beta/2}}^{1/2}.\end{split}$$

(10)

The quantities $\Lambda_{1/2}$ and $\Lambda_{1}$ also appear in the moment bound for degenerate $U$-statistics with bounded kernels; see Theorem 3.2 of Giné et al., (2000). Note that $\Lambda_{\alpha}$ can be trivially bounded as

$$\Lambda_{\alpha}\leq K_{F}\max_{1\leq i\leq n}\sup_{z}\left(\sum_{\begin{subarray}{c}1\leq j\leq n,\\ j\neq i\end{subarray}}\mathbb{E}\left[\frac{f_{i,j}^{2}(z,Z_{j}^{\prime})}{F_{i}(z)}\right]\right)^{1/2}.$$

Similar comment holds for $\Lambda_{\beta}$ as well. We use $\mathfrak{C},\mathfrak{C}_{\alpha},\mathfrak{C}_{\beta}$ and $\mathfrak{C}_{\alpha,\beta}$ to denote universal constants, constants depending on $\alpha,\beta,(\alpha,\beta)$, respectively. We now present the first main result.

Theorem 1 reduces to Theorem 3.2 of Giné et al., (2000) by setting $\alpha=\beta=\infty$; note that if $\alpha=\beta=\infty$, then $\alpha^{*}=\beta^{*}=1$ and the log factors in the result become 1. The result is asymmetric in $\alpha,\beta$ only because of the structure of the proof. One can apply the result by switching the roles of $\alpha,\beta$ and take the minimum of the two bounds. We do not present this for brevity. It is interesting to note that the tail exhibits five different behaviors including the commonly expected sub-Gaussian and sub-exponential tails. Because we did not make any assumption on the symmetry of the kernel, $\alpha$ and $\beta$ can be different. Under an assumption of symmetry, $\alpha=\beta$ and Theorem 1 now yields a tail bound that only exhibits five regmies.

Assuming only (A1), Theorem 1 provides a moment and tail bound for degenerate $U$-statistics. The appearance of the constants $\Lambda_{\alpha}$ and $\Lambda_{\beta}$ might make this result difficult to apply in some applications. For this reason, we provide our second result assuming a little more structure on the kernel. Suppose we have $n$ independent random variables $Z_{1}=(X_{1},Y_{1}),Z_{2}=(X_{2},Y_{2}),\ldots,Z_{n}=(X_{n},Y_{n})$ on some measurable space and sequence of functions $\{w_{i,j}(\cdot,\cdot):\,1\leq i\neq j\leq n\}$. Consider, for functions $\phi(\cdot)$ and $\psi(\cdot)$, the $U$-statistic

$$U_{n}:=\sum_{1\leq i\neq j\leq n}f_{i,j}(Z_{i},Z_{j}),\quad\mbox{where}\quad f_{i,j}(Z_{i},Z_{j}):=\phi(Z_{i})w_{i,j}(X_{i},X_{j})\psi(Z_{j}).$$

(12)

The kernels $f_{i,j}(\cdot,\cdot)$ are not required to be degenerate here. We will derive moment and tail bounds for the degenerate version of the $U$-statistics $U_{n}^{D}$ given by

$$U_{n}^{D}:=\sum_{1\leq i\neq j\leq n}f_{i,j}^{D}(Z_{i},Z_{j}),$$

for the kernel $f_{i,j}^{D}(\cdot,\cdot)$ defined in (9). We first prove a basic lemma that reduces the problem of moment bounds on $U_{n}^{D}$ to a symmetrized version of $U_{n}$; see Theorem 3.5.3 of de la Peña and Giné, (1999). For any random variable $W$, set $\left\lVert W\right\rVert_{p}=(\mathbb{E}[|W|^{p}])^{1/p}$ for $p\geq 1$.

The proof of this lemma (given in Appendix A.2) is based on the by-now classical decoupling inequalities of de la Peña, (1992) and de la Peña and Giné, (1999, Chapter 3). The result also holds in case of degenerate $U$-processes and does not require the special structure of the kernels $f_{i,j}(\cdot,\cdot)$ in (12).

To prove moment and tail bounds for degenerate second order $U$-statistics with unbounded kernels, we use the following assumptions. Consider the following assumptions.

1. (B1)

   There exists constants $0<\alpha,\beta,C_{\phi},C_{\psi}<\infty$ such that

   $$\max_{1\leq i\leq n}\,\mathbb{E}\left[\exp\left(\frac{|\phi(Z_{i})|^{\alpha}}{C_{\phi}^{\alpha}}\right)\big{|}X_{i}\right]\leq 2,\quad\mbox{and}\quad\max_{1\leq i\leq n}\,\mathbb{E}\left[\exp\left(\frac{|\psi(Z_{i})|^{\beta}}{C_{\psi}^{\beta}}\right)\big{|}X_{i}\right]\leq 2,$$

   hold almost surely.

2. (B2)

   The functions $\{w_{i,j}(\cdot,\cdot):\,1\leq i\neq j\leq n\}$ are all uniformly bounded, that is,

   $$\max_{1\leq i\neq j\leq n}\sup_{(x,x^{\prime})\in\mathfrak{X}\times\mathfrak{X}}\,\left|w_{i,j}(x,x^{\prime})\right|\leq B_{w}.$$

The main technique in our proof is truncation and Hoffmann-Jørgensen’s inequality. Assumption (B1) implies that conditional on $X_{i}$’s the maximum of $\phi(Y_{i})$ is at most a polynomial of $\log n$ (in rate). This along with Assumption (B2) allows us to apply truncation at this rate and study the truncated part using the sharp results of Giné et al., (2000). The unbounded parts of smaller order are controlled using Hoffmann-Jørgensen’s inequality. The bound $B_{w}$ in Assumption (B2) is allowed to grown in $n$ and all the kernels are also allowed to be function of $n$. All the results to be presented here are non-asymptotic. For more applications of this technique see Kuchibhotla and Chakrabortty, (2022).

Define

$\displaystyle T_{\phi}:=8\mathbb{E}\left[\max_{1\leq i\leq n}\left|\phi(Z_{i})\right|\big{|}X_{1},\ldots,X_{n}\right],\quad T_{\psi}:=8\mathbb{E}\left[\max_{1\leq i\leq n}\left|\psi(Z_{i})\right|\big{|}X_{1},\ldots,X_{n}\right],$

and the truncated random variables

$$\begin{split}\Phi_{i,1}:=\phi(Z_{i})\mathbbm{1}\{|\phi(Z_{i})|\leq T_{\phi}\},\quad&\mbox{and}\quad\Phi_{i,2}:=\phi(Z_{i})\mathbbm{1}\{|\phi(Z_{i})|>T_{\phi}\},\\ \Psi^{\prime}_{j,1}:=\psi(Z_{j}^{\prime})\mathbbm{1}\{|\psi(Z_{j}^{\prime})|\leq T_{\psi}\},\quad&\mbox{and}\quad\Psi^{\prime}_{j,2}:=\psi(Z_{j}^{\prime})\mathbbm{1}\{|\psi(Z_{j}^{\prime})|>T_{\psi}\}.\end{split}$$

(13)

It is clear that $\phi(Z_{i})=\Phi_{i,1}+\Phi_{i,2}$ and $\psi(Z_{j}^{\prime})=\Psi^{\prime}_{j,1}+\Psi^{\prime}_{j,2}.$ Based on these, note that

$$\begin{split}\phi(Z_{i})w_{i,j}(X_{i},X_{j}^{\prime})\psi(Z_{j}^{\prime})&=\Phi_{i,1}w_{i,j}(X_{i},X_{j})\Psi^{\prime}_{j,1}+\Phi_{i,2}w_{i,j}(X_{i},X_{j})\Psi^{\prime}_{j,1}\\ &\qquad+\Phi_{i,1}w_{i,j}(X_{i},X_{j})\Psi^{\prime}_{j,2}+\Phi_{i,2}w_{i,j}(X_{i},X_{j})\Psi^{\prime}_{j,2}.\end{split}$$

(14)

The first term on the right hand side is bounded by $T_{\phi}B_{w}T_{\psi}$. The second and third terms are non-zero only when $\Phi_{i,2}$ and $\Psi^{\prime}_{j,2}$, are respectively non-zero, which can only happen with only a small probability under Assumption (B1). Finally, the fourth term can be non-zero only if both $\Phi_{i,2}$ and $\Psi^{\prime}_{j,2}$ are non-zero which can happen with even smaller probability. These four terms leads to four different degenerate $U$-statistics that will be controlled separately in Section A.3 to prove the following result. We need the following notation: for $1\leq i,j\leq n$,

$$\sigma_{i,\phi}^{2}(x)=\mathbb{E}[\phi^{2}(Z_{i})\big{|}X_{i}=x]\quad\mbox{and}\quad\sigma_{j,\psi}^{2}(x)=\mathbb{E}[\psi^{2}(Z_{j})\big{|}X_{j}=x].$$

Define $\Lambda_{2}:=C_{\phi}C_{\psi}B_{w}(\log n)^{\alpha^{-1}+\beta^{-1}}$ and

	$\displaystyle\Lambda_{{1}/{2}}$	$\displaystyle:=\left(\sum_{1\leq i\neq j\leq n}\mathbb{E}\left[\sigma_{i,\phi}^{2}(X_{i})w_{i,j}^{2}(X_{i},X_{j})\sigma_{j,\psi}^{2}(X_{j})\right]\right)^{1/2},$
	$\displaystyle\Lambda_{1}$	$\displaystyle:=\sup\left\{\sum_{1\leq i\neq j\leq n}\mathbb{E}\left[q_{i}(X_{i})\sigma_{i,\phi}(X_{i})w_{i,j}(X_{i},X_{j})\sigma_{j,\psi}(X_{j})p_{j}(X_{j})\right]:\right.$
		$\displaystyle\qquad\qquad\quad\left.\sum_{j=1}^{n}\mathbb{E}\left[q_{i}^{2}(X_{i})\right]\leq 1,\,\sum_{i=1}^{n}\mathbb{E}\left[p_{j}^{2}(X_{j})\right]\leq 1\right\},$
	$\displaystyle\Lambda_{3/2}^{(\alpha)}$	$\displaystyle:=C_{\phi}(\log n)^{1/\alpha}\sup_{x}\max_{1\leq i\leq n}\left(\sum_{j=1}^{n}\mathbb{E}\left[w_{i,j}^{2}(x,X_{j})\sigma^{2}_{j,\psi}(X_{j})\right]\right)^{1/2},$
	$\displaystyle\Lambda_{3/2}^{(\beta)}$	$\displaystyle:=C_{\psi}(\log n)^{1/\beta}\sup_{x}\max_{1\leq j\leq n}\left(\sum_{i=1}^{n}\mathbb{E}\left[w_{i,j}^{2}(X_{i},x)\sigma^{2}_{i,\phi}(X_{i})\right]\right)^{1/2},$
	$\displaystyle\Lambda_{\alpha^{*}}$	$\displaystyle:=(\log n)^{1/2}\Lambda_{3/2}^{(\alpha)}+(\log n)\Lambda_{2},\quad\mbox{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}and}$
	$\displaystyle\Lambda_{\beta^{*}}$	$\displaystyle:=(\log n)^{1/2}\Lambda_{3/2}^{(\beta)}+(\log n)\Lambda_{2}.$

The quantities $\Lambda_{1/2},\Lambda_{1},\Lambda_{3/2}^{(\alpha)},\Lambda_{3/2}^{(\beta)},\Lambda_{2}$ also appear in the case of bounded kernels as shown in Theorem 3.2 of Giné et al., (2000).

In this section, we generalize Theorem 2 to degenerate $U$-processes. Consider

$$\mathcal{U}_{n}(\mathcal{W}):=\sup_{w\in\mathcal{W}}\left|\mathcal{U}_{n}(w)\right|,\quad\mbox{where}\quad\mathcal{U}_{n}(w):=\sum_{1\leq i\neq j\leq n}\varepsilon_{i}\phi(Z_{i})w_{i,j}(X_{i},X_{j}^{\prime})\psi(Z_{j}^{\prime})\varepsilon_{j}^{\prime},$$

for some function class $\mathcal{W}$ with elements of the type $w=(w_{i,j})_{1\leq i\neq j\leq n}$. If $\mathcal{W}$ is a singleton, then this reduces to the $U$-statistic studied in Section 2. Here $\varepsilon_{1},\ldots,\varepsilon_{n}$ denote an independent sequence of Rademacher random variables as before. For simplicity, we consider the symmetrized version and by Lemma 1 the results also hold for the original degenerate $U$-process; see Theorem 3.5.3 of de la Peña and Giné, (1999) for details.