# Adaptive Testing for High-Dimensional Data

Yangfan<EMAIL_ADDRESS>[ Runmin
<EMAIL_ADDRESS>[ Xiaofeng<EMAIL_ADDRESS>[
Department of Statistics, University of Illinois at Urbana Champaignpresep=,
]e1,e3  Department of Statistics, Texas A&M Universitypresep=, ]e2

###### Abstract

In this article, we propose a class of $L_{q}$-norm based U-statistics for a
family of global testing problems related to high-dimensional data. This
includes testing of mean vector and its spatial sign, simultaneous testing of
linear model coefficients, and testing of component-wise independence for
high-dimensional observations, among others. Under the null hypothesis, we
derive asymptotic normality and independence between $L_{q}$-norm based
U-statistics for several $q$s under mild moment and cumulant conditions. A
simple combination of two studentized $L_{q}$-based test statistics via their
$p$-values is proposed and is shown to attain great power against alternatives
of different sparsity. Our work is a substantial extension of He et al.,
(2021), which is mostly focused on mean and covariance testing, and we manage
to provide a general treatment of asymptotic independence of $L_{q}$-norm
based U-statistics for a wide class of kernels. To alleviate the computation
burden, we introduce a variant of the proposed U-statistics by using the
monotone indices in the summation, resulting in a U-statistic with asymmetric
kernel. A dynamic programming method is introduced to reduce the computational
cost from $O(n^{qr})$, which is required for the calculation of the full
U-statistic, to $O(n^{r})$ where $r$ is the order of the kernel. Numerical
studies further corroborate the advantage of the proposed adaptive test as
compared to some existing competitors.

Independence testing,

Simultaneous testing,

Spatial sign,

U-statistics,

###### keywords:

, and

##  1 Introduction

High-dimensional data, where the dimension $p$ could be comparable to or
exceeds the sample size $n$, are ubiquitous and are encountered on a regular
basis in many scientific fields. In practice, it is often of interest to test
some overall patterns of low-dimensional features of high-dimensional data.
This includes testing of mean vectors (Chen and Qin,, 2010; Cai et al.,, 2014;
Wang et al.,, 2015; He et al.,, 2021), covariance matrices (Li and Chen,,
2012; He et al.,, 2021), and regression coefficients in the linear models
(Zhong and Chen,, 2011), as well as component-wise independence in high-
dimensional observations (Han et al.,, 2017; Leung and Drton,, 2018).

These problems can be formulated as $H_{0}:\Theta=\bm{0}$, where $\bm{0}$ is a
vector of all zeros, $\Theta=\\{\theta_{l},l\in{\cal L}\\}$ is a high-
dimensional vector with ${\cal L}$ being the index set, and $\\{\theta_{l}\\}$
being the corresponding parameters of interest. For this type of global
testing problem, many methods have been developed in the literature, and there
are two dominating brands. One is the $L_{2}$ norm based test with sum-of-
squares-type statistics, which is widely used in the context of mean testing
(Bai and Saranadasa,, 1996; Chen and Qin,, 2010; Goeman et al.,, 2006; Gregory
et al.,, 2015; Srivastava and Du,, 2008; Srivastava et al.,, 2016), covariance
testing (Bai et al.,, 2009; Chen et al.,, 2010; Ledoit and Wolf,, 2002; Li and
Chen,, 2012), and other testing problems such as component-wise independence
test (Leung and Drton,, 2018). The other is the $L_{\infty}$ norm based test
with maximum-type statistics. See examples in mean testing (Cai et al.,, 2014;
Hall and Jin,, 2010), covariance testing (Cai and Jiang,, 2011; Cai et al.,,
2013; Jiang,, 2004; Liu et al.,, 2008; Shao and Zhou,, 2014) and component-
wise independence testing (Han et al.,, 2017; Drton et al.,, 2020). It is well
known that sum-of-squares-type statistics are powerful against dense
alternative, where $\Theta$ has a large proportion of nonzero elements with
large $\|\Theta\|_{2}$, whereas maximum-type statistics target at sparse
alternative, where $\Theta$ has few nonzero elements with a large
$\|\Theta\|_{\infty}$. In practice, it is often unrealistic to assume a
particular type of alternative and there is little knowledge about the type of
alternative if any. Thus there is a need to develop new test that can be
adaptive to different types of alternatives, and have good power against a
broad range of alternatives, including moderately sparse and moderately dense
ones.

In addition to $L_{2}$ and $L_{\infty}$ type statistics, Xu et al., (2016) and
Wu et al., (2019) developed a family of von Mises V-statistics of $L_{q}$-type
for testing $\|\Theta\|_{q}^{q}$ for $q=2,3,\cdots$, which are usually biased
estimators. In a recent paper, He et al., (2021) proposed a U-statistics
framework and constructed unbiased and asymptotically independent estimators
of $\|\Theta\|_{q}^{q}$ . Then they combine the $L_{q}$-norm based test
statistics, including the cases $q=2,6,\infty$, by aggregating the individual
$p$-values. The resulting test is adaptive in the sense that it can capture a
wide range of alternatives. However, the U-statistics considered in He et al.,
(2021) mainly focus on the mean and covariance testing problem and its
corresponding kernel function is of order 1. It is natural to ask whether the
asymptotic normality and independence for $L_{q}$-norm based U-statistics hold
for more general kernels and can go beyond the mean and covariance testing
problem.

In this article, we aim to advance the $L_{q}$-norm based tests and their
combination to a broader set of testing problems. In particular, our framework
provides a more general treatment and includes U-statistic of order larger
than 1, which naturally occurs in problems including testing the nullity of
linear regression coefficients [Zhong and Chen, (2011)], and component-wise
independence testing based on Kendall’s $\tau$ and Spearman’s $\rho$ (Leung
and Drton,, 2018). In addition, our framework allows us to extend the spatial
sign-based test developed in Wang et al., (2015) for $L_{2}$ to its $L_{q}$
counterpart, which seems not included in He et al., (2021). Our asymptotic
theory covers some of those developed in He et al., (2021) as special cases,
and further broadens the applicability of the $L_{q}$ norm based tests and
their combination. In our theory development, we also derive a new Hoeffding
decomposition that is finer than the classical one, by taking into account the
special structure of the kernel functions. We note that the new decomposition
holds for a wider class of kernels with tensor product structures and can be
of broad interest.

Computationally speaking, the calculation of full U-statistics for
$\|\Theta\|_{q}^{q}$, $q=4,6,\cdots$ is very challenging. He et al. (2021)
developed a computationally efficient algorithm to make the computation
feasible by taking advantage of a recursive structure in the statistics.
However, their algorithm seems only applicable to the kernel of order 1, and
an extension to the higher order case is difficult. To this end, we propose a
family of U-statistics with monotone index in the summation to ease the
computational burden of calculating the full U-statistics. They are
essentially U-statistics with asymmetric kernels, which can be computed much
faster than the full U-statistics via dynamic programming. While we pay a
price in terms of a constant loss of statistical efficiency, the new
U-statistics with asymmetric kernels can be calculated efficiently in
$O(n^{r})$ time, as opposed to $O(n^{qr})$ for the brute-force approach, where
$r$ equals the order of the kernel function.

The rest of the paper is organized as follows. In Section 2, we introduce the
problem settings and propose the family of $L_{q}$-type U-statistics for both
one-sample and two-sample testing problems. We also include several motivating
examples where the proposed statistics can be applied. Section 3 includes the
main theory, such as asymptotic normality and independence of the proposed
U-statistics with different $q$’s under the null. The power analysis under the
alternative is also included. In Section 4, we propose a variant of
U-statistic with asymmetric kernels, for which dynamic programming can be
applied to compute the statistic efficiently. Section 5 includes all
simulation results, and Section 6 includes a real data application. We
conclude the paper in Section 7. All technical proofs are gathered in the
supplement.

Notations. We use capital letters (e.g. $X_{i}$) to denote random vectors, and
corresponding lowercase ones (e.g. $x_{ij}$) to denote their components. We
use $\sum^{*}$ to denote the summation over all mutually distinct indices. For
two functions $f(X_{1},\ldots,X_{r})$ and $g(Y_{1},\ldots,Y_{s})$, we define
their tensor product $f\otimes g$ as functions

$(f\otimes
g)(X_{1},\ldots,X_{r};Y_{1},\ldots,Y_{s})=f(X_{1},\ldots,X_{r})g(Y_{1},\ldots,Y_{s}).$

We define $(\otimes)^{s}f=f\otimes[(\otimes)^{s-1}f]$ for $s\geq 2$
recursively. We denote $\\{1,\ldots,n\\}$ as $[n]$, and $\\{m,m+1,\ldots,n\\}$
as $[m,n]$. We use $I$ to denote a sequence of (not necessarily distinct)
indices in $[n]$, $(i_{1},i_{2},\ldots,i_{m})$, and we denote
$(X_{i_{1}},X_{i_{2}},\ldots,X_{i_{m}})$ as $X_{I}$. In particular, we have
$X_{[c]}=(X_{1},\ldots,X_{c})$. We define $P_{m}(n)$ as the collection of all
subsets of $[n]$ with cardinality $m$, i.e.

$P_{m}(n)=\\{\\{i_{1},i_{2},\ldots,i_{m}\\}\subseteq[n]:\text{ All indices are
distinct with each other}\\}.$

For $f(n)$ and $g(n)$, we write $f\asymp g$ if $f(n)/g(n)\rightarrow 1$ as
$n\rightarrow\infty$. Throughout the paper, we define
$\|X\|_{q}^{q}=\sum_{l=1}^{p}x_{l}^{q}$ for any vector
$X=(x_{1},\ldots,x_{p})\in\mathbb{R}^{p}$ and $q\in\mathbb{Z}_{+}$. Note that
we did not take the absolute value of $x_{l}$ and hence $\|\cdot\|_{q}$ is not
equal to the classical $l_{q}$ norm for odd $q$. We use $e_{t}(r)$ to denote a
vector in $\mathbb{R}^{r}$ with $t$-th element being 1 and others 0.

##  2 Background

###  2.1 One-Sample Test

Suppose we observe some i.i.d. (independent and identically distributed)
samples $X_{1},\ldots,X_{n}\in\mathbb{R}^{p}$ from some underlying
distribution and $p$ is comparable to or exceeds sample size $n$. The goal is
to test some high-dimensional parameters
$\Theta=\Theta(X_{i})=\\{\theta_{l}:l\in\mathcal{L}\\}=\bm{0}$. We can
construct a family of unbiased U-statistics for
$\|\Theta\|_{q}^{q}=\sum_{l\in\mathcal{L}}\theta_{l}^{q}$. For each $l$, we
start with some kernel functions $h_{l}$ of order $r$ satisfying
$\mathbb{E}[h_{l}(X_{[r]})]=\theta_{l}$. We can then introduce a new kernel
$\otimes^{q}h_{l}$ with order $qr$, whose expectation equals $\theta_{l}^{q}$.
Recall that

$\otimes^{q}h_{l}(X_{[qr]})=h_{l}(X_{[r]})h_{l}(X_{[r+1,2r]})\cdots
h_{l}(X_{[(q-1)r+1,qr]}).$

Let $P^{n}_{m}=\frac{n!}{(n-m)!}$. Then we can define the associated
U-statistic

$U_{n,q}=\sum_{l\in\mathcal{L}}(P^{n}_{qr})^{-1}\sum^{*}_{1\leq
i_{1},\ldots,i_{qr}\leq
n}\prod_{c=1}^{q}h_{l}(X_{i_{(c-1)r+1}},\ldots,X_{i_{cr}}).$

In the definition of $L_{q}$ norm above, we do not take the absolute value (in
contrast to classical definition), due to the construction of the U-statistic.
In the extreme case, where the positive components cancel out with the
negative ones, the $L_{q}$ norm $\|\Theta\|_{q}^{q}$ can be (nearly) zero for
odd $q$, even if $\Theta$ is not a zero vector. Therefore, we will mainly
consider even $q$ in this paper, i.e. $q\in 2\mathbb{Z}_{+}$, although our
theoretical results can be extended to general $q\in\mathbb{Z}_{+}$.

Note that the one-sample mean testing problem studied in He et al., (2021) is
included in the proposed framework. Specifically,
$\mathcal{H}_{0}:\mathbb{E}[X_{i}]=\mu_{0}=(\mu_{0,1},\ldots,\mu_{0,p}$), the
family of U-statistics proposed in He et al., (2021) can be recovered by
taking $\mathcal{L}=[p]$, order $r=1$ and $h_{l}(X_{i})=x_{i,l}-\mu_{0,l}$. We
have $\mathbb{E}[U_{n,q}]=\|\mathbb{E}[X_{1}]-\mu_{0}\|_{q}^{q}$. For mean-
testing statistics, the asymptotic independence for $\\{U_{n,q}\\}_{q\in
Z^{+}}$ is derived from asymptotic joint normality along with
${\mbox{cov}}(U_{n,q_{1}},U_{n,q_{2}})=0$ for $q_{1}\not=q_{2}$. For
illustration, consider the example where $q_{1}>q_{2}$. For any summand
$X_{i_{1}}\cdots X_{i_{q_{1}}}$ in $U_{n,q_{1}}$, and $X_{j_{1}}\cdots
X_{j_{q_{2}}}$ in $U_{n,q_{2}}$, there must be at least one $c$ such that
$i_{c}$ is not in the set $\\{j_{1},\ldots,j_{q_{2}}\\}$ and hence their
covariance will be 0. This argument highly relies on the fact that the kernel
function has order 1. For kernels with higher order, we cannot expect the
covariance to be exactly 0, but we may still show the asymptotic negligibility
of the covariance (after proper scaling) and hence asymptotic independence
between these U-statistics for different $q$’s, by imposing some regularity
assumptions.

###  2.2 Two-Sample Test

Suppose we observe two i.i.d. samples $X_{1},\ldots,X_{n}\in\mathbb{R}^{p}$
and $Y_{1},\ldots,Y_{m}\in\mathbb{R}^{p}$. And we want to test some high-
dimensional parameter
$\Theta=\Theta(X_{i},Y_{i})=\\{\theta_{l}:l\in\mathcal{L}\\}=\bm{0}$. The
approach is similar to one-sample test, as we are now interested in
$\|\Theta\|_{q}^{q}$ and we want to test if $\|\Theta\|_{q}^{q}=0$.

For each $l\in\mathcal{L}$, we can construct a family of two-sample
U-statistic based on some kernel function $h_{l}(X_{[r]};Y_{[r]})$ of order
$(r,r)$ satisfying $\mathbb{E}[h_{l}(X_{[r]};Y_{[r]})]=\theta_{l}$. Similar to
one-sample testing, we may consider $\otimes^{q}h_{l}$ with order $(qr,qr)$
whose expectation equals $\theta_{l}^{q}$, i.e.

$\otimes^{q}h_{l}(X_{[qr]};Y_{[qr]})=h_{l}(X_{[r]};Y_{[r]})\cdots
h_{l}(X_{[(q-1)r+1,qr]};Y_{[(q-1)r+1,qr]}).$

We can then define the associated U-statistic

$\displaystyle U_{n,m,q}=$
$\displaystyle\sum_{l\in\mathcal{L}}(P^{n}_{qr}P^{m}_{qr})^{-1}\sum^{*}_{1\leq
i_{1},\ldots,i_{qr}\leq n}\sum^{*}_{1\leq j_{1},\ldots,j_{qr}\leq m}$
$\displaystyle\prod_{c=1}^{q}h_{l}(X_{i_{(c-1)r+1}},\ldots,X_{i_{cr}};Y_{i_{(c-1)r+1}},\ldots,Y_{i_{cr}}).$

As is the case for one-sample testing problem, the family of statistics for
two-sample mean testing in He et al., (2021) is also a special case of the
above two-sample U-statistics.

###  2.3 Motivating Examples

In this section, we present some examples that are included in the above
formulation. We mainly focus on the examples in one-sample testing problems,
as their counterparts for two-sample testing can be constructed in a
straightforward way.

  * •

Mean (zero) testing, $\mathcal{H}_{0}:\mu:=\mathbb{E}[X_{i}]=\bm{0}$ (He et
al.,, 2021). In this case, $\mathcal{L}=[p]$, $r=1$ and
$h_{l}(X_{i})=x_{i,l}$.

  * •

Spatial sign based testing (Wang et al.,, 2015),
$\mathcal{H}_{0}:\mathbb{E}[X_{i}\,/\,\|X_{i}\|\,]=\bm{0}$. We can take
$\mathcal{L}=[p]$, $r=1$ and $h_{l}(X_{i})=x_{i,l}\,/\,\|X_{i}\|$.

  * •

Covariance testing for data with zero mean,
$\mathcal{H}_{0}:\Sigma:={\mbox{var}}(X_{i})=\Sigma_{0}$ for some given
$\Sigma_{0}=(\sigma_{p_{1}p_{2}})_{p_{1},p_{2}=1}^{p}$. In this case,
$\mathcal{L}=\\{l=(p_{1},p_{2}),1\leq p_{1}\leq p_{2}\leq p\\},r=1$ and
$h_{l}(X_{i})=x_{ip_{1}}x_{ip_{2}}-\sigma_{p_{1}p_{2}}$. In particular, to
test if the covariance has banded structure, i.e.
$\sigma_{p_{1},p_{2}}=0,|p_{1}-p_{2}|\geq d$, we can take
$\mathcal{L}=\\{l=(p_{1},p_{2})\in[p]^{2},p_{2}\geq p_{1}+d\\},r=1$ and
$h_{l}(X_{i})=x_{ip_{1}}x_{ip_{2}}$. This example is also studied in He et
al., (2021).

  * •

Component-wise independence testing. $\mathcal{H}_{0}:x_{i,p_{1}}$ and
$x_{i,p_{2}}$ are independent for any $p_{1}\not=p_{2}$. For Kendall’s $\tau$
based test (Leung and Drton,, 2018), we essentially test
$\mathcal{H}_{0}^{\tau}:P(x_{1,p_{1}}<x_{2,p_{1}},x_{1,p_{2}}<x_{2,p_{2}})=1/4$
for any $p_{1}\not=p_{2}$, against $\mathcal{H}_{1}^{\tau}$: negation of
$\mathcal{H}_{0}^{\tau}$. Let $\mathcal{L}=\\{l=(p_{1},p_{2}),1\leq
p_{1}<p_{2}\leq p\\},r=2$ and
$h_{l}(X_{i},X_{j})={\mbox{sgn}}(x_{i,p_{1}}-x_{j,p_{1}}){\mbox{sgn}}(x_{i,p_{2}}-x_{j,p_{2}})$.

  * •

Component-wise independence testing with Spearman’s $\rho$ (Leung and Drton,,
2018). In this case,
$\mathcal{H}_{0}^{\rho}:P(x_{1,p_{1}}<x_{2,p_{1}},x_{1,p_{2}}<x_{3,p_{2}})=1/4$
for any $p_{1}\not=p_{2}$, and $\mathcal{H}_{1}^{\rho}$ is the negation of
$\mathcal{H}_{0}^{\rho}$. We take $\mathcal{L}=\\{l=(p_{1},p_{2}),1\leq
p_{1}<p_{2}\leq p\\}$, $r=3$ and $h_{l}(X_{i},X_{j},X_{k})$ to be the
symmetric version of
${\mbox{sgn}}(x_{i,p_{1}}-x_{j,p_{1}}){\mbox{sgn}}(x_{i,p_{2}}-x_{k,p_{2}})$,
i.e.

$\displaystyle h_{l}(X_{i},X_{j},X_{k})=$
$\displaystyle\frac{1}{6}\big{[}{\mbox{sgn}}(x_{i,p_{1}}-x_{j,p_{1}}){\mbox{sgn}}(x_{i,p_{2}}-x_{k,p_{2}})+{\mbox{sgn}}(x_{i,p_{1}}-x_{k,p_{1}}){\mbox{sgn}}(x_{i,p_{2}}-x_{j,p_{2}})$
$\displaystyle+{\mbox{sgn}}(x_{j,p_{1}}-x_{i,p_{1}}){\mbox{sgn}}(x_{j,p_{2}}-x_{k,p_{2}})+{\mbox{sgn}}(x_{j,p_{1}}-x_{k,p_{1}}){\mbox{sgn}}(x_{j,p_{2}}-x_{i,p_{2}})$
$\displaystyle+{\mbox{sgn}}(x_{k,p_{1}}-x_{i,p_{1}}){\mbox{sgn}}(x_{k,p_{2}}-x_{j,p_{2}})+{\mbox{sgn}}(x_{k,p_{1}}-x_{j,p_{1}}){\mbox{sgn}}(x_{k,p_{2}}-x_{i,p_{2}})\big{]}.$

  * •

Simultaneous test of linear regression coefficients (Zhong and Chen,, 2011).
For linear model $Y=X\bm{\beta}+\varepsilon$, we test
$\mathcal{H}_{0}:\bm{\beta}=\bm{\beta}_{0}$ against
$\mathcal{H}_{a}:\bm{\beta}\not=\bm{\beta}_{0}$. We take
$\mathcal{L}=[p],r=2$, and

$h_{l}\big{(}(X_{1},Y_{1}),(X_{2},Y_{2})\big{)}=[\,(X_{1}-X_{2})(Y_{1}-Y_{2}-(X_{1}-X_{2})^{T}\bm{\beta}_{0})\,\big{]}_{l}/2,$
(1)

and the parameter of interest equals
$\Theta=\Sigma(\bm{\beta}-\bm{\beta}_{0})$ with $\Sigma:={\mbox{var}}(X)$.

  * •

Two-sample spatial sign test (Chakraborty and Chaudhuri,, 2017),
$\mathcal{H}_{0}:\Theta=\bm{0}$ with
$\Theta=\mathbb{E}[\,(X_{i}-Y_{j})\,/\,\|X_{i}-Y_{j}\|\,]$. We take
$\mathcal{L}=[p]$, $r=1$ and two-sample kernel

$h_{l}(X_{i},Y_{j})=(x_{i,l}-y_{j,l})/\,\|X_{i}-Y_{j}\|.$

##  3 Theoretical Analysis

This section includes the asymptotic theory for the proposed statistics. We
start with kernels of order one and then move onto kernels of higher order.

###  3.1 Asymptotic Theory for Order-One Kernels

For kernels of order $r=1$, we have

$U_{n,q}=\sum_{l\in\mathcal{L}}(P^{n}_{q})^{-1}\sum^{*}_{1\leq
i_{1},\ldots,i_{q}\leq n}\prod_{c=1}^{q}h_{l}(X_{i_{c}}).$

Write $\mathcal{L}=[L]$ and define
$Y_{i}=(y_{i,1},\ldots,y_{i,L})^{T}=(h_{1}(X_{i}),\ldots,h_{L}(X_{i}))^{T}\overset{\Delta}{=}H(X_{i})$,
with
$\Sigma=(\sigma_{l_{1},l_{2}})_{l_{1},l_{2}\in\mathcal{L}}={\mbox{var}}(Y_{i})$.
In this way, we can view $U_{n,q}$ as the U-statistic for testing
$\mathbb{E}[Y_{i}]\equiv\bm{0}$. The analysis for mean-testing would directly
apply. For example, we can calculate the variance as

$\displaystyle{\mbox{var}}(U_{n,q})=$
$\displaystyle(P^{n}_{q})^{-2}\sum_{l_{1},l_{2}\in\mathcal{L}}\sum^{*}_{1\leq
i_{1},\ldots,i_{q}\leq n}\sum^{*}_{1\leq j_{1},\ldots,j_{q}\leq
n}\mathbb{E}\left[\,\prod_{c=1}^{q}y_{i_{c},l_{1}}y_{j_{c},l_{2}}\right]$
$\displaystyle=$
$\displaystyle(P^{n}_{q})^{-2}q!\sum_{l_{1},l_{2}\in\mathcal{L}}\sum^{*}_{1\leq
i_{1},\ldots,i_{q}\leq
n}\prod_{c=1}^{q}\mathbb{E}[y_{i_{c},l_{1}}y_{i_{c},l_{2}}]$
$\displaystyle\asymp$ $\displaystyle
q!n^{-q}\sum_{l_{1},l_{2}\in\mathcal{L}}\sigma_{l_{1},l_{2}}^{q}=q!n^{-q}\|\Sigma\|_{q}^{q}.$

For $q_{1}\not=q_{2}$, we have

$\displaystyle{\mbox{cov}}(U_{n,q_{1}},U_{n,q_{2}})=$
$\displaystyle(P^{n}_{q_{1}})^{-1}(P^{n}_{q_{2}})^{-1}\sum_{l_{1},l_{2}\in\mathcal{L}}\sum^{*}_{1\leq
i_{1},\ldots,i_{q_{1}}\leq n}\sum^{*}_{1\leq j_{1},\ldots,j_{q_{2}}\leq
n}\prod_{c_{1}=1}^{q_{1}}\prod_{c_{2}=1}^{q_{2}}\mathbb{E}[y_{i_{c_{1}},l_{1}}y_{j_{c_{2}},l_{2}}]=0,$

since there must be at least one $i_{c_{1}}$ or $j_{c_{2}}$ that is distinct
from any other index when $q_{1}\not=q_{2}$.

The analysis in He et al., (2021) can be applied directly, but instead we
shall follow the argument used in Zhang et al., (2021) and impose the
following weaker moment conditions and some cumulant assumptions.

######  Assumption 1 ($r=1$).

Suppose $Y_{1},\ldots,Y_{n}$ are i.i.d. copies of $Y_{0}$ with variance matrix
$\Sigma$, and the following conditions hold.

  1. 1.

There exists constants $C_{p}>0$ depending on $p$ such that
${\mbox{tr}}(\Sigma)\geq C_{p}L.$

  2. 2.

$Y_{0}$ has up to fourth moment with
$\sup_{l\in\mathcal{L}}\mathbb{E}[y_{0,l}^{4}]<C$, and for $u=2,3,4$ we have

$\left|\operatorname{cum}\left(y_{0,l_{1}},\ldots,y_{0,l_{u}}\right)\right|\leq
C_{p}^{u/2}\left(1\vee\max_{1\leq i,j\leq
u}\left|l_{i}-l_{j}\right|\right)^{-\kappa},\quad\text{ for some }\kappa>2.$

The above assumptions are slightly weaker than those in Zhang et al., (2021)
but sufficient for deriving the asymptotic distributions as presented in the
following theorem, since we do not need to show the process convergence, as
required in Zhang et al., (2021). The above cumulant assumption is implied by
geometric moment contraction [cf. Proposition 2 of Wu and Shao, (2004)] or
physical dependence measure proposed by Wu, (2005) [cf. Section 4 of Shao and
Wu, (2007)], or $\alpha-$mixing (with polynomial decaying rate for mixing
coefficients) [Andrews, (1991), Zhurbenko and Zuev, (1975)] in the time series
setting. It basically imposes weak dependence among the $p$ components in the
data. Our theory does not require an ordering of components and holds as long
as a permutation of $p$ components satisfies the cumulant assumption, as our
test statistic is invariant to the permutation of components.

######  Theorem 3.1 ($r=1$).

Suppose Assumption 1 holds. Under the null, we have for any $q\in
2\mathbb{Z}_{+}$,

$(q!)^{-1/2}n^{q/2}\|\Sigma\|_{q}^{-q/2}U_{n,q}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N(0,1).$

Furthermore, for any finite set $I\subseteq 2\mathbb{Z}_{+}$, $(U_{n,q})_{q\in
I}$ are asymptotically jointly independent.

For mean and covariance testing, Assumption 1 usually holds with $C_{p}$ being
a constant independent of $p$. For spatial sign based testing, we have
$H(X_{i})=X_{i}/\|X_{i}\|_{2}$. In this case, we have
$\displaystyle\sum_{l\in\mathcal{L}}\mathbb{E}[y_{i,l}^{2}]=\mathbb{E}[\,\|Y_{i}\|_{2}^{2}\,]\equiv
1$, so Assumption 1 does not hold if $C_{p}$ is a fixed constant as in Zhang
et al., (2021). To this end, we provide a separate proof to show the CLT for
spatial sign-based test statistics; see Appendix A.2 for details. To
summarize, for order-one kernels, the proposed U-statistics include those
studied in He et al., (2021) as a special case, and the asymptotic theory is
justified under weaker assumptions (e.g. we only require the existence of
fourth-order moment). Moreover, the theory can be extended to spatial sign
based test, which is not covered by He et al., (2021). On the other hand, He
et al., (2021) obtained asymptotic independence among $L_{q}$-based
U-statistics and maxmum-type statistics for mean and covariance testing
problems, which is not covered here.

###  3.2 Hoeffding Decomposition for Kernels with Higher Order

For kernels with order $r>1$, the asymptotic theory is more involved. We start
with a new Hoeffding decomposition that takes into account the special
structure of $U_{n,q}$. Without loss of generality, here we assume $h_{l}$ is
symmetric over its arguments for all $l\in\mathcal{L}$. We also assume
$\mathbb{E}[h_{l}(X_{[r]})]=0$ as we focus on the null.

For $1\leq t\leq r$, define the projected kernels

$\displaystyle h_{l,t}(x_{1},\ldots,x_{t})=$
$\displaystyle\mathbb{E}[h_{l}(x_{1},\ldots,x_{t},X_{t+1},\ldots,X_{r})]$
$\displaystyle=$
$\displaystyle\mathbb{E}[h_{l}(X_{1},\ldots,X_{t},X_{t+1},\ldots,X_{r})\mid
X_{1}=x_{1},\ldots,X_{t}=x_{t}].$

We call $h_{l}$ has degeneracy of order $s\in[1,r]$, if $h_{l,t}\equiv 0$ for
any $1\leq t<s$ while $h_{l,s}\not=0$. In particular, $h_{l}$ is called non-
degenerate if $s=1<r$; and is fully degenerate if $s=r$. Note that we view
$h_{l}$ with $r=1$ as fully degenerate for convention.

We further define the following (order-$t$ for $1\leq t\leq r$) Hajék
projection

$\displaystyle h_{l}^{(t)}(x_{1},\ldots,x_{t})=$
$\displaystyle\sum_{s=1}^{t}(-1)^{t-s}\times\sum_{1\leq i_{1}<\cdots<i_{s}\leq
t}h_{l,s}(x_{i_{1}},\ldots,x_{i_{s}}).$

In particular, we have $h_{l}^{(1)}=h_{l,1}$. When $r=2$, we have

$h_{l}^{(2)}(X_{1},X_{2})=h_{l}(X_{1},X_{2})-h_{l}^{(1)}(X_{1})-h_{l}^{(1)}(X_{2}),$

which is a fully degenerate kernel. In general, $h_{l}^{(t)}$ is always fully
degenerate with order $t$.

The Hajék projection is the cornerstone for deriving the Hoeffding’s
decomposition. In fact, the classical Hoeffding decomposition is derived based
on the fact that a kernel function equals the summation over all Hajék
projected kernels of different orders. However, instead of directly applying
the projection to $\otimes^{q}h_{l}$, we write $h_{l}$ as the summation over
the projected kernels $h_{l}^{(t)}$ and apply the distribution law to
decompose $\otimes^{q}h_{l}$ into some products of $h_{l}^{(t)}$.

For illustration, consider a kernel $h_{l}$ with order $r=2$. We may write

$h_{l}(X_{1},X_{2})=h_{l}^{(1)}(X_{1})+h_{l}^{(1)}(X_{2})+h_{l}^{(2)}(X_{1},X_{2}).$

By applying distribution law, we have, e.g., for $q=2$,

$\displaystyle(\otimes^{2}h_{l})(X_{1},X_{2},X_{3},X_{4})$ (2)
$\displaystyle=$
$\displaystyle[h_{l}^{(1)}(X_{1})+h_{l}^{(1)}(X_{2})+h_{l}^{(2)}(X_{1},X_{2})][h_{l}^{(1)}(X_{3})+h_{l}^{(1)}(X_{4})+h_{l}^{(2)}(X_{3},X_{4})]$
$\displaystyle=$
$\displaystyle(\otimes^{2}h_{l}^{(1)})(X_{1},X_{3})+(\otimes^{2}h_{l}^{(1)})(X_{1},X_{4})+(\otimes^{2}h_{l}^{(1)})(X_{2},X_{3})+(\otimes^{2}h_{l}^{(1)})(X_{2},X_{4})$
$\displaystyle+(h_{l}^{(1)}\otimes
h_{l}^{(2)})(X_{1},X_{3},X_{4})+(h_{l}^{(1)}\otimes
h_{l}^{(2)})(X_{2},X_{3},X_{4})$ $\displaystyle+(h_{l}^{(1)}\otimes
h_{l}^{(2)})(X_{3},X_{1},X_{2})+(h_{l}^{(1)}\otimes
h_{l}^{(2)})(X_{4},X_{1},X_{2})$
$\displaystyle+(\otimes^{2}h_{l}^{(2)})(X_{1},X_{2},X_{3},X_{4}).$

Therefore, we may decompose $\otimes^{2}h_{l}$ into $\otimes^{2}h_{l}^{(1)}$,
$h_{l}^{(1)}\otimes h_{l}^{(2)}$ and $\otimes^{2}h_{l}^{(2)}$.
The argument based on distribution law is applicable to general settings, and
we may write $\otimes^{q}h_{l}$ as the summation of many tensor products of
$h_{l}^{(t)}$. To characterize these summands, we define

$h^{\bm{\alpha}}_{l}=[\otimes^{\alpha_{1}}h_{l}^{(1)}]\otimes[\otimes^{\alpha_{2}}h_{l}^{(2)}]\otimes\cdots\otimes[\otimes^{\alpha_{r}}h_{l}^{(r)}],$
(3)

for $\bm{\alpha}\overset{\Delta}{=}(\alpha_{1},\ldots,\alpha_{r})$. In
particular, $\sum_{t=1}^{r}t\alpha_{t}$ is the order of $h_{l}^{\bm{\alpha}}$,
and $\alpha_{t}$ is the count of $h_{l}^{(t)}$ in the formula (3). It is
straightforward to see that $\otimes^{q}h_{l}$ equals the summation of
$h_{l}^{\bm{\alpha}}$ for all vectors $\bm{\alpha}\in\mathbb{N}^{r}$ s.t.
$\sum_{t=1}^{r}\alpha_{t}=q$. In particular, $\otimes^{2}h_{l}^{(1)}$,
$h_{l}^{(1)}\otimes h_{l}^{(2)}$ and $\otimes^{2}h_{l}^{(2)}$ in (2) is
associated with $\bm{\alpha}=(2,0)$, (1,1) and (0,2), respectively.

Although $h_{l}$ is a symmetric kernel, $h_{l}^{\bm{\alpha}}$ is not symmetric
in general. Define the symmetric counterpart of $h^{\bm{\alpha}}_{l}$ as
$\tilde{h}^{\bm{\alpha}}_{l}$. Note that $\tilde{h}^{\bm{\alpha}}_{l}$ is a
fully degenerate kernel of order $\sum_{t=1}^{r}t\alpha_{t}$, as $h^{(t)}_{l}$
is fully degenerate. For example, the kernel $h_{l}^{(1)}\otimes h_{l}^{(2)}$
in (2) associated with $\bm{\alpha}=(1,1)$ is fully degenerate with order
$r=3$. It is asymmetric as
$h_{l}^{\bm{\alpha}}(X_{1},X_{2},X_{3})=h_{l}^{(1)}(X_{1})h_{l}^{(2)}(X_{2},X_{3})$,
and its symmetric counterpart is defined through

$\displaystyle\tilde{h}_{l}^{\bm{\alpha}}(X_{1},X_{2},X_{3})=$
$\displaystyle\frac{1}{3}\Big{[}h_{l}^{(1)}(X_{1})h_{l}^{(2)}(X_{2},X_{3})+h_{l}^{(1)}(X_{2})h_{l}^{(2)}(X_{1},X_{3})+h_{l}^{(1)}(X_{3})h_{l}^{(2)}(X_{1},X_{2})\Big{]}.$

We define the following U-statistic associated with $h_{l}^{\bm{\alpha}}$,
which appears in the Hoeffding decomposition of $U_{n,q}$. Note that
$c=\sum_{t=1}^{r}t\alpha_{t}$ is the order of $h_{l}^{\bm{\alpha}}$.

$\displaystyle U_{n,\bm{\alpha}}=$
$\displaystyle(P_{c}^{n})^{-1}\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1},i_{2},\cdots,i_{c}\leq n}^{*}h_{l}^{\bm{\alpha}}(X_{1},\ldots,X_{c})$
$\displaystyle=$
$\displaystyle\binom{n}{c}^{-1}\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<i_{2}<\cdots<i_{c}\leq
n}\tilde{h}_{l}^{\bm{\alpha}}(X_{1},\ldots,X_{c}).$

With $U_{n,\bm{\alpha}}$, we have the following decomposition.

######  Lemma 3.2.

There exists some constants $C_{\bm{\alpha}}>0$ such that

$U_{n,q}=\sum_{c=qs}^{qr}\sum_{\bm{\alpha}:\sum_{t}t\alpha_{t}=c}C_{\bm{\alpha}}U_{n,\bm{\alpha}},$
(4)

where $s$ is the degeneracy of $h_{l}$.

######  Remark.

In general, the Hoeffding decomposition (4) is a finer composition than the
classical one. The classical decomposition is simply based on Hajék projection
of $\otimes^{q}h_{l}$, whereas (4) instead takes into account the tensor
product structure of $\otimes^{q}h_{l}$ and applies distribution law. This
finer decomposition allows us to directly impose assumptions on Hajék
projections of $h_{l}$ (and some related quantities), otherwise the
assumptions will be too abstract to comprehend. We can write the classical
Hoeffding decomposition using the kernel $\otimes^{q}h_{l}$ as
$U_{n,q}=\sum_{c=qs}^{qr}C^{[c]}U_{n,q}^{[c]},$ where $C^{[c]}$ are some
constants, and $U_{n,q}^{[c]}$ is the U-statistic associated with the Hajék
projection of $\otimes^{q}h_{l}$ with order $c$, and includes all
$U_{n,\bm{\alpha}}$ with kernel $\tilde{h}_{l}^{\bm{\alpha}}$ of order $c$.

For example, consider $r=3$ and $q=2$, following the same argument as (2), we
can decompose $\otimes^{3}h_{l}$ into six kernels: $\otimes^{2}h_{l}^{(1)}$,
$h_{l}^{(1)}\otimes h_{l}^{(2)}$, $h_{l}^{(1)}\otimes h_{l}^{(3)}$,
$\otimes^{2}h_{l}^{(2)}$, $h_{l}^{(2)}\otimes h_{l}^{(3)}$ and
$\otimes^{2}h_{l}^{(3)}$. The classical Hoeffding decomposition, instead,
combines the kernels with the same order, e.g. $h_{l}^{(1)}\otimes
h_{l}^{(3)}$ and $\otimes^{2}h_{l}^{(2)}$, and hence only contains 5 terms. It
is not difficult to see that the proposed decomposition coincides with the
classical one for $r\leq 2$.

In general, for any kernel function that can be written as the tensor product
of several functions, their Hajék projections can be used to derive a finer
Hoeffding decomposition in the same way that we obtain (4) by applying
distribution law.

It is worth noting that there is one special type of $\bm{\alpha}$ that plays
an important role in the above decomposition, where only $t$-th component of
$\bm{\alpha}$ equals $q$, and all other components are zero, i.e.
$\bm{\alpha}=qe_{t}(r)$. for $t=1,...,r$. The associated $h_{l}^{\bm{\alpha}}$
is equal to $\otimes^{q}h_{l}^{(t)}$. We denote its symmetric version as
$H_{l,q}^{(t)}$, so

$H_{l,q}^{(t)}(X_{[qt]})=[(qt)!]^{-1}\sum_{I\in
P_{qt}(qt)}(\otimes)^{q}h_{l}^{(t)}(X_{I}),$

and the associated U-statistic as $U_{n,q}^{(qt)}$. In the context of previous
illustrating example with $r=2$, $U_{n,q}^{(q)}$ and $U_{n,q}^{(2q)}$ are the
U-statistics associated with $\otimes^{q}h_{l}^{(1)}$ and
$\otimes^{q}h_{l}^{(2)}$ respectively.

In Section 3.3, we show that the asymptotic variance can be characterized by

$\tilde{\Sigma}_{t}(q)\overset{\Delta}{=}\sum_{l_{1},l_{2}\in\mathcal{L}}{\mbox{cov}}(H_{l_{1},q}^{(t)}(X_{[qt]}),H_{l_{2},q}^{(t)}(X_{[qt]}))={\mbox{var}}(H_{q}^{(t)}(X_{[qt]})),$
(5)

where we have defined
$H_{q}^{(t)}\overset{\Delta}{=}\sum_{l\in\mathcal{L}}H_{l,q}^{(t)}$.

Next, we also define

$\sigma_{t}(l_{1},l_{2})\overset{\Delta}{=}{\mbox{cov}}(h_{l_{1}}^{(t)}(X_{[t]}),h_{l_{2}}^{(t)}(X_{[t]})),\quad
l_{1},l_{2}\in\mathcal{L},$

and

$\displaystyle\Sigma_{t}(q)\overset{\Delta}{=}\sum_{l_{1},l_{2}\in\mathcal{L}}\sigma_{t}^{q}(l_{1},l_{2})=\sum_{l_{1},l_{2}\in\mathcal{L}}{\mbox{cov}}\big{(}(\otimes^{q}h_{l_{1}}^{(t)})(X_{[qt]}),(\otimes^{q}h_{l_{2}}^{(t)})(X_{[qt]})\big{)}={\mbox{var}}\big{(}\sum_{l\in\mathcal{L}}(\otimes^{q}h_{l}^{(t)})(X_{[qt]})\big{)},$

for $q\in 2\mathbb{Z}_{+},1\leq t\leq r$. The definition is similar to
$\tilde{\Sigma}_{t}(q)$, and in particular, we have
$\tilde{\Sigma}_{1}(q)=\Sigma_{1}(q)$ since $\otimes^{q}h_{l}^{(1)}$ is
symmetric so $H_{l,q}^{(1)}=\otimes^{q}h_{l}^{(1)}$. In general, we have
$\tilde{\Sigma}_{t}(q)\leq\Sigma_{t}(q)$ due to Cauchy-Schwarz inequality. For
illustration, consider $t=2$ and $q=2$. We have

$\displaystyle H_{2}^{(2)}(X_{1},X_{2},X_{3},X_{4})=$
$\displaystyle\sum_{l\in\mathcal{L}}\frac{1}{3}\Big{[}h_{l}^{(2)}(X_{1},X_{2})h_{l}^{(2)}(X_{3},X_{4})+h_{l}^{(2)}(X_{1},X_{3})h_{l}^{(2)}(X_{2},X_{4})$
$\displaystyle+h_{l}^{(2)}(X_{1},X_{4})h_{l}^{(2)}(X_{2},X_{3})\Big{]}.$

Cauchy-Schwarz inequality then implies that

${\mbox{cov}}\left(H_{2}^{(2)},H_{2}^{(2)}\right)\leq{\mbox{var}}\left(\sum_{l\in\mathcal{L}}\otimes^{2}h_{l}^{(2)}\right)=\Sigma_{2}(2),$

and hence $\tilde{\Sigma}_{2}(2)\leq\Sigma_{2}(2)$. We remark that
$\Sigma_{t}(q)$ is more convenient for the order analysis, although it does
not characterize the asymptotic variance.

###  3.3 Asymptotic Theory for Order-One Kernels

As the decomposition described in the previous section is a finer version of
the traditional Hoeffding decomposition, it inherits most of the properties of
Hoeffding’s decomposition such as the orthogonality among projections with
different orders. Therefore it can be used to analyze the asymptotic
distribution of $U_{n,q}$. We make the following assumptions to derive the
leading term in the decomposition.

######  Assumption 2.

Suppose $h_{l}$ has the degeneracy of order $s$. We have
$\Sigma_{t}(q)=o\big{(}n^{q(t-s)}\Sigma_{s}(q)\big{)}$ for any $s<t\leq r$ and
$q\in 2\mathbb{Z}_{+}$, and
$\Sigma_{s}(q)=O\big{(}\tilde{\Sigma}_{s}(q)\big{)}$.

When $s=1$, the assumption is equivalent to
$\Sigma_{t}(q)=o\big{(}n^{q(t-1)}\Sigma_{1}(q)\big{)}$ as
$\Sigma_{1}(q)=\tilde{\Sigma}_{1}(q)$. For illustration, suppose $h_{l}$ has
order 2. If it is degenerate, then the first statement in the Assumption 2 is
automatically satisfied since $s=r=2$ in this case and it suffices to verify
the second one. On the other hand, if $h_{l}$ is not degenerate, i.e. $s=1$,
then the second statement in the assumption holds as
$\Sigma_{1}(q)=\tilde{\Sigma}_{1}(q)$ , and it suffices to verify
$\Sigma_{2}(q)=o\big{(}n^{q}\Sigma_{1}(q)\big{)}$ i.e.

$\sum_{l_{1},l_{2}\in\mathcal{L}}\mathbb{E}^{q}[h_{l_{1}}^{(2)}(X_{[2]})h_{l_{2}}^{(2)}(X_{[2]})]=o\left(n^{q}\sum_{l_{1},l_{2}\in\mathcal{L}}\mathbb{E}^{q}[h_{l_{1}}^{(1)}(X_{1})h_{l_{2}}^{(1)}(X_{1})]\right).$

This is trivially satisfied if
$\mathbb{E}[h_{l_{1}}^{(2)}(X_{[2]})h_{l_{2}}^{(2)}(X_{[2]})]$ and
$\mathbb{E}[h_{l_{1}}^{(1)}(X_{1})h_{l_{2}}^{(1)}(X_{1})]$ (and hence the
summations) have the same order, which is true in most settings such as
simultaneous testing of linear model coefficients and component-wise
independence testing discussed in Section 2.3. For example, for Kendall’s
$\tau$ we have $\Sigma_{2}(q)=7^{q}\Sigma_{1}(q)=(7/9)^{q}p(p-1)/2$ (see
Appendix A.4 for more details).

In general, when $h_{l}$ has degeneracy of order $s$, the Hajék projection
$h_{l}^{(t)}\equiv 0$ for any $1\leq t<s$, which implies $h_{l,\bm{\alpha}}=0$
if its order $\sum_{t}t\alpha_{t}$ is less than $qs$, and the non-zero kernel
of lowest order is $H_{q,l}^{(s)}$ (corresponding to $\bm{\alpha}=q\cdot
e_{t}(r))$). Note that this is the only non-zero kernel with order $qs$. The
following lemma states that the U-statistic $U_{n,q}^{(qs)}$ with kernel
$H_{q,l}^{(s)}$ is indeed the leading term.

######  Lemma 3.3.

Suppose the kernel $h_{l}$ has degeneracy of order $s\in[1,r]$. Under
Assumption 2, we have under the null, it holds for any $q\in 2\mathbb{Z}_{+}$
that $U_{n,q}=\binom{r}{s}^{q}U_{n,q}^{(qs)}[1+o_{p}(1)]$

In view of Lemma 3.3, the leading term $U_{n,q}^{(qs)}$ in the Hoeffding
decomposition is a U-statistic that has fully degenerate kernels
$\otimes^{q}h_{l}^{(s)}$ induced by $h_{l}^{(s)}$. Therefore it suffices to
study the asymptotic theory of U-statistic associated with fully degenerate
($r=s$) kernel $h_{l}$, without loss of generality, and then apply the result
to $h_{l}^{(s)}$. We make the following assumption for any fully degenerate
kernel, which is applicable to $h_{l}^{(s)}$. Recall that
$\sigma_{t}(l_{1},l_{2})\overset{\Delta}{=}{\mbox{cov}}(h_{l_{1}}^{(t)}(X_{[t]}),h_{l_{2}}^{(t)}(X_{[t]}))$.

######  Assumption 3.

Suppose $h_{l}$ is a fully degenerate kernel function with order $r\geq 1$. We
have the followings hold for any $q\in 2\mathbb{Z}_{+}$.
(a)
$\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}[\sigma_{r}(l_{1},l_{2})\sigma_{r}(l_{3},l_{4})\sigma_{r}(l_{1},l_{4})\sigma_{r}(l_{2},l_{3})]^{q/2}=o\left(\tilde{\Sigma}_{r}^{2}(q)\right)$.
(b1) $h_{l}$ has up to $4$-th moments with
$\sup_{l\in\mathcal{L}}\mathbb{E}[h_{l}^{4}(X_{[r]})]<C,$ and for any $q$
there exists a constant $C_{q}$ such that

$\sum_{l_{1},...,l_{u}\in\mathcal{L}}|{\mbox{cum}}^{q}(h_{l_{1}}(X_{i_{1}^{(1)}},\ldots,X_{i_{r}^{(1)}}),\ldots,h_{l_{u}}(X_{i_{1}^{(u)}},\cdots,X_{i_{r}^{(u)}}))|\leq
C_{q}\tilde{\Sigma}_{r}^{u/2}(q),$

for $u=2,3,4$ and any $u$ groups of distinct indices
$(i_{1}^{(u)},\ldots,i_{r}^{(u)})$.
Moreover, if $r>1$, the following holds.
(b2) $h_{l}$ has up to $q$-th moments with
$\sup_{l\in\mathcal{L}}\mathbb{E}[h_{l}^{q}(X_{[r]})]<C,$ and

$\sum_{l_{1},...,l_{u}\in\mathcal{L}}|{\mbox{cum}}^{q/c}(h_{l_{1}}(X_{I_{1}}),\ldots,h_{l_{u}}(X_{I_{c}}))|=o(\tilde{\Sigma}_{r}^{2}(q)),$

for $u=3,4;1\leq c\leq q$ and $I_{1},\ldots,I_{c}\in P_{cr}(n)$ such that any
element only appears in two $I_{t}$’s and $I_{t}\not=I_{s}$ for any $t\not=s$.

######  Remark.

In summary, Assumption 3 requires certain summability on the joint cumulants
of $H_{l_{1},q}^{(s)},H_{l_{2},q}^{(s)},H_{l_{3},q}^{(s)},H_{l_{4},q}^{(s)}$
for all $l_{1},...,l_{4}\in\mathcal{L}$. In particular, Assumption 3 (b2) is a
new assumption made for $r>1$, compared to those for $r=1$. This is due to the
complexity in the fourth moment of kernels with $r>1$. These summability
assumptions guarantee that the asymptotic variance $U_{n,q}^{(qr)}$ is indeed
characterized by $\tilde{\Sigma}_{r}(q)$ and martingale CLT holds. In fact,
Assumption 1 implies Assumption 3 (a) and (b1), and they are natural
generalizations of the assumptions made in Zhang et al., (2021), whose
argument is focused on $r=1$.

Assumption 3 represents abstract properties of the $h_{l}$ since our framework
allows general kernels and the verification for them requires case-by-case
analysis. To shed some light on its feasibility, we demonstrate the
verifiability of our assumptions using several commonly studied U-statistics
and the assumptions can all be straightforwardly verified. We include the
results in Appendix A.

######  Proposition 3.4 (Degenerate kernel, $r=s$).

Suppose Assumption 3 holds. Under the null, we have for any $q\in
2\mathbb{Z}_{+}$,

$[(qr)!]^{-1/2}n^{qr/2}\tilde{\Sigma}_{r}^{-1/2}(q)U_{n,q}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N(0,1).$

Furthermore, for any finite set $I\subseteq 2\mathbb{Z}_{+}$, $(U_{n,q})_{q\in
I}$ are asymptotically jointly independent.

Combining Proposition 3.4 and Lemma 3.3, we immediately have the following
result.

######  Theorem 3.5 (General case).

Suppose $h_{l}$ is a kernel function with order $r$, and has degeneracy of
order $s\leq r$. In addition, Assumption 2 and 3 hold for $h_{l}^{(s)}$. Then
we have under the null, for any $q\in 2\mathbb{Z}_{+}$,

$[(qs)!]^{-1/2}\binom{r}{s}^{-q}n^{qs/2}\tilde{\Sigma}_{s}^{-1/2}(q)U_{n,q}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N(0,1).$

Furthermore, for any finite set $I\subseteq 2\mathbb{Z}_{+}$, $(U_{n,q})_{q\in
I}$ are asymptotically jointly independent.

Recall that we call any kernels with order $r=1$ fully degenerate by our
convention. Hence Proposition 3.4 and Theorem 3.5 both contain Theorem 3.1 as
a special case, which includes the mean and covariance testing in He et al.,
(2021) and the spatial sign based test studied in Wang et al., (2015).
Moreover, in Appendix A we demonstrate that the assumptions are satisfied
under more broad settings such as simultaneous testing of linear model
coefficients and component-wise independence testing based on Kendall’s $\tau$
and Spearman’s $\rho$.

To end this section, we consider a special case for illustration where the
kernel $h_{l}$ is non-degenerate ($s=1$). As we discussed, it suffices to
verify Assumption 3 (a) and (b1) for $h_{l}^{(1)}$, which is implied by
Assumption 1 for $h_{l}^{(1)}$ (as Assumption 2.1 in Zhang et al., (2021)
implies Assumption 6.1 therein). We summarize the result in the following
corollary.

######  Corollary 3.6 ($s=1$).

Suppose $h_{l}$ is a non-degenerate kernel with order $r$, and Assumption 2
holds so that $\Sigma_{t}(q)=o(n^{q(t-1)}\Sigma_{1}(q))$ for any $1<t\leq r$.
Moreover, Assumption 1 holds for
$Y_{i}=(h_{l}^{(1)}(X_{i}))_{l\in\mathcal{L}}$. Then we have under the null,
for any $q\in 2\mathbb{Z}_{+}$,

$(q!)^{-1/2}r^{-q}n^{q/2}\Sigma_{1}^{-1/2}(q)U_{n,q}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N(0,1).$

Furthermore, for any finite set $I\subseteq 2\mathbb{Z}_{+}$, $(U_{n,q})_{q\in
I}$ are asymptotically jointly independent.

###  3.4 Power Analysis

In this section, we derive the asymptotic theory of the U-statistic $U_{n,q}$
under the alternative. Suppose
$\mathbb{E}[h_{l}(X_{1},\ldots,X_{r})]=\theta_{l}$. Define the centered
U-statistic $\tilde{h}_{l}=h_{l}-\theta_{l}$. We have

$\displaystyle U_{n,q}=$
$\displaystyle(P_{qr}^{n})^{-1}\sum_{l\in\mathcal{L}}\sum_{I\in
P_{qr}(n)}[(\otimes)^{q}(\tilde{h}_{l}+\theta_{l})](X_{I})$ (6)
$\displaystyle=$
$\displaystyle\|\Theta\|_{q}^{q}+\tilde{U}_{n,q}+\sum_{c=1}^{q}\binom{q}{c}(P_{cr}^{n})^{-1}\sum_{l\in\mathcal{L}}\sum_{I\in
P_{cr}(n)}\theta_{l}^{q-c}[(\otimes)^{c}\tilde{h}_{l}](X_{I}),$

where we have viewed the constant $\theta_{l}$ as a function so that
$\theta_{l}(X_{I})\equiv\theta_{l}$ and $\tilde{U}_{n,q}$ is the proposed
$L_{q}$-type U-statistic associated with $\tilde{h}_{l}$.

Since $\tilde{h}_{l}$ has zero mean, we have the asymptotic normality of
$n^{qs/2}\tilde{\Sigma}_{s}^{-1/2}(q)\tilde{U}_{n,q}$, and hence it is natural
to define the signal level as

$\gamma_{n,q}=n^{qs/2}\tilde{\Sigma}_{s}^{-1/2}(q)\|\Theta\|_{q}^{q}.$

We also make he following assumption to bound the cross-product terms under
the local alternative where $\gamma_{n,q}$ goes to some non-zero constant.

######  Assumption 4.

Suppose $h_{l}$ has degeneracy of order $s$. We have for any $q\in
2\mathbb{Z}_{+}$ and $c=1,\ldots,q-1$,

$\sum_{l_{1},l_{2}\in\mathcal{L}}\theta_{l_{1}}^{q-c}\theta_{l_{2}}^{q-c}\sigma_{s}^{c}(l_{1},l_{2})=o\big{(}n^{-(q-c)s}\tilde{\Sigma}_{s}(q)\big{)}.$

With Assumption 4, we have the following theorem under the alternative.

######  Theorem 3.7.

Under the same assumption as Theorem 3.5. We have the followings for any $q\in
2\mathbb{Z}_{+}$.

  * •

Suppose $\gamma_{n,q}\rightarrow\infty$. Then
$n^{qs/2}\tilde{\Sigma}_{s}^{-1/2}(q)U_{n,q}\stackrel{{\scriptstyle\cal
P}}{{\longrightarrow}}\infty$.

  * •

Suppose $\gamma_{n,q}\rightarrow 0$. Then $U_{n,q}$ has the same asymptotic
distribution as the limiting null.

  * •

Suppose Assumption 4 holds. Under the local alternative where
$\gamma_{n,q}\rightarrow\gamma\in(0,\infty)$, we have

$n^{qs/2}\tilde{\Sigma}_{s}^{-1/2}(q)U_{n,q}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N\left(\gamma,(qs)!\binom{r}{s}^{2q}\right).$ (7)

As a result of Theorem 3.7, when $\gamma_{n,q}\rightarrow\infty$, we have
$U_{n,q}/\|\Theta\|_{q}^{q}=1+o_{p}(1)$, and hence $U_{n,q}$ is a ratio-
consistent estimator of $\|\Theta\|_{q}^{q}$.

Since Lemma 6.1 of Zhang et al., (2021) states that for $s=1$, Assumption 4 is
implied by Assumption 1 (imposed on $h_{l}^{(1)}$), we have the following
corollary.

######  Corollary 3.8 ($s=1$).

Suppose $h_{l}$ is non-degenerate, and Assumption 1 holds for $h_{l}^{(1)}$.
Moreover, Assumption 2 also holds. Then we have the first two cases in Theorem
3.7. In addition, under the local alternative where
$\gamma_{n,q}\rightarrow\gamma\in(0,\infty)$, we have for any $q\in
2\mathbb{Z}_{+}$,

$n^{q/2}\tilde{\Sigma}_{1}^{-1/2}(q)U_{n,q}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N\left(\gamma,q!r^{2q}\right).$

To illustrate the power behavior with different $q\in 2\mathbb{Z}_{+}$, we
consider $\Theta=\delta\cdot(\bm{1}_{d},\bm{0}_{L-d})^{T}$ ($L=|\mathcal{L}|$)
for simplicity. In view of (7), to compare the finite-sample power, it
suffices to investigate

$\frac{\mathbb{E}[U_{n,q}]}{\sqrt{{\mbox{var}}(U_{n,q})}}\asymp\frac{n^{qs/2}\tilde{\Sigma}_{s}^{-1/2}(q)\|\Theta\|_{q}^{q}}{[(qs)!]^{1/2}\binom{r}{s}^{q}},$

for different $q$. We assume that $\tilde{\Sigma}_{s}(q)\asymp a^{q}N$ for
some $a>0$ and $N=N(L)$ depending on $L$, so that we have

$\frac{\mathbb{E}[U_{n,q}]}{\sqrt{{\mbox{var}}(U_{n,q})}}\asymp[(qs)!]^{-1/2}\binom{r}{s}^{-q}n^{qs/2}a^{-q/2}N^{-1/2}\delta^{q}d.$
(8)

To achieve (asymptotic) power $\Phi(R-z_{1-\alpha})$ for some $R>0$, we let
$\mathbb{E}[U_{n,q}]/\sqrt{{\mbox{var}}(U_{n,q})}=R$ and solve
$\delta=\delta(q)$ from (8) to obtain

$\delta(q)\asymp\binom{r}{s}\sqrt{a}[(qs)!]^{1/2q}(\sqrt{N}R/d)^{1/q}n^{s/2}.$
(9)

Given $\delta=\delta(q)$, the U-statistic $U_{n,q}$ has fixed asymptotic power
$\Phi(R-z_{1-\alpha})$. Therefore, we hope to find $q\in 2\mathbb{Z}_{+}$
associated with the smallest $\delta(q)$, which tends to have highest power.
Note that we consider one-sided test, since even $q$ implies that the $L_{q}$
norm of the parameter is always nonnegative. We have the following result that
mimics Proposition 2.3 in He et al., (2021).

######  Proposition 3.9.

The optimal $q$ that minimizes $\delta(q)$ in (9) is achieved at

  * •

2, if $d\geq\sqrt{N}R$;

  * •

some $q\in 2\mathbb{Z}_{+}$, and is increasing in $\sqrt{N}R/d$ if
$d>\sqrt{N}R$.

######  Remark.

Proposition 3.9 is derived under the assumption
$\Theta=\delta(\bm{1}_{d},\bm{0}_{L-d})$, and can be straightforwardly
extended to more general $\Theta$, e.g. $\theta_{j}=\delta r^{j}$ (or $\delta
j^{a}$) for some constant $r$ (or $a$) and $j\leq d$, as long as
$\|\Theta\|_{q}$ can be calculated explicitly. It basically demonstrates that
when $\Theta$ is dense, the optimal $q$ is 2. As $\Theta$ gets sparser, the
optimal $q$ gets larger. This coincides with our intuition.

##  4 Test Statistics and Computation

###  4.1 Computation for Order-One Kernels with Dynamic Programming

When $h_{l}$ has order 1, i.e. $r=1$, we have

$U_{n,q}=\sum_{l\in\mathcal{L}}(P^{n}_{q})^{-1}\sum^{*}_{1\leq
i_{1},\ldots,i_{q}\leq n}\prod_{c=1}^{q}h_{l}(X_{i_{c}}).$

In this case, we can apply dynamic programming to speed up the computation and
calculate the statistic exactly. In particular, we define for $q\leq m\leq n$

$D_{q,l}(m)=\sum_{1\leq i_{1}<\cdots<i_{q}\leq
m}\prod_{c=1}^{q}h_{l}(X_{i_{c}}).$

We have $U_{n,q}=\binom{n}{q}^{-1}\sum_{l\in\mathcal{L}}D_{q,l}(n).$ Fix a
component $l\in\mathcal{L}$. Note that $D_{1,l}(m)=\sum_{i=1}^{m}h_{l}(X_{i})$
is simply the cumulative sum of the sequence $\\{h_{l}(X_{i})\\}_{i=1}^{n}$,
and can be calculated efficiently in $O(n)$. Afterwards, we can use the
following approach to calculate $D_{c,l}$ from $D_{c-1,l}$ recursively,

$D_{c,l}(m)=D_{c,l}(m-1)+D_{c-1,l}(m-1)h_{l}(X_{m}),\quad m\geq c,$

with $D_{c,l}(m)=0$ for $1\leq m<c$. We run this step for $c=2,\ldots,q$ and
each step takes $O(n)$ time.

In summary, the total cost of calculating $D_{q,l}(n)$ and $U_{n,q}$ are
$O(qn)$ and $O(qn|\mathcal{L}|)$, respectively, which is a huge reduction from
brute-force calculation that requires $O(qn^{q}|\mathcal{L}|)$ computation.

###  4.2 An Asymmetric U-statistic for Kernels with Higher Order

The method in last section only works for $h_{l}$ with order 1. However, it
motivates us to consider the following U-statistic for $r>1$, to which dynamic
programming can be applied.

$U_{n,q}^{M}=\sum_{l\in\mathcal{L}}\binom{n}{qr}^{-1}\sum_{1\leq
i_{1}<\cdots<i_{qr}\leq
n}\prod_{c=1}^{q}h_{l}(X_{i_{(c-1)r+1}},\ldots,X_{i_{cr}}).$

Here we only consider all monotone indices in each summand, so that dynamic
programming is applicable as we discuss next. We use the superscript $M$ to
emphasize the monotonicity, and to distinguish it from $U_{n,q}$. Note that
$U_{n,q}^{M}$ is essentially a U-statistic with asymmetric kernel.

To see the difference between $U_{n,q}$ and $U_{n,q}^{M}$, consider the case
$r=2$ and $q=2$. Then $U_{n,q}$ is essentially U-statistic of order $q\cdot
r=4$. In this case, the (symmetric) kernel for $U_{n,q}$ is given by

$\frac{1}{3}\big{[}h_{l}(X_{1},X_{2})h_{l}(X_{3},X_{4})+h_{l}(X_{1},X_{3})h_{l}(X_{2},X_{4})+h_{l}(X_{1},X_{4})h_{l}(X_{2},X_{3})\big{]},$

while that for $U_{n,q}^{M}$ equals $h_{l}(X_{1},X_{2})h_{l}(X_{3},X_{4})$.
Although $U_{n,q}^{M}$ is also a U-statistic of order 4, the number of unique
summand in $U_{n,q}$ is 3 times that of $U_{n,q}^{M}$.

To apply dynamic programming, we define for $qr\leq m\leq n$,

$D_{q,l}^{M}(m)=\sum_{1\leq i_{1}<\cdots<i_{qr}\leq
m}\prod_{c=1}^{q}h_{l}(X_{i_{(c-1)r+1}},\ldots,X_{i_{cr}}).$

We first initialize $D_{0,l}^{M}(m)\equiv 1$ for $1\leq m\leq n$. Then we use
the following recursive updating formula for $c=1,\ldots,q$ and $m\geq cr$,

$D_{c,l}^{M}(m)=D_{c,l}^{M}(m-1)+\sum_{(c-1)r<i_{1}<\cdots<i_{r-1}<m}D^{M}_{c-1,l}(i_{1}-1)h_{l}(X_{i_{1}},\cdots,X_{i_{r-1}},X_{m}),$

with $D^{M}_{c,l}(m)=0$ for $1\leq m<cr$. Note that the calculation for each
$c,m$ is $O(m^{r-1})$. Therefore, the total costs of obtaining
$D_{q,l}^{M}(n)$ and $U_{n,q}^{M}$ are $O(qn^{r})$ and
$O(qn^{r}|\mathcal{L}|)$ respectively, much better than the brute force
approach with $O(qn^{qr}|\mathcal{L}|)$ computation.

As an illustrating example that summarizes the idea of the recursive formula,
again consider the case $r=2,q=2$. Suppose we have calculated $D_{2,l}^{M}(m)$
for $m<n$ and the full sequence $D_{1,l}^{M}$. To obtain $D_{2,l}^{M}(n)$, we
only need to calculate the difference between $D_{2,l}^{M}(n)$ and
$D_{2,l}^{M}(n-1)$, which consists of terms of form
$h_{l}(X_{i},X_{j})h_{l}(X_{k},X_{n})$ for $1\leq i<j<k<n$. If we fix $k$, we
can factor $h_{l}(X_{k},X_{n})$ out, the summation over $h_{l}(X_{i},X_{j})$
is simply $D_{1,l}^{M}(k-1)$ and we obtain

$D_{2,l}^{M}(n)=D_{2,l}^{M}(n-1)+\sum_{k=3}^{n-1}D^{M}_{1,l}(k-1)h_{l}(X_{k},X_{n}).$

It is not difficult to see that the asymptotic variance of $U_{n,q}^{M}$ has
order $n^{qs/2}\Sigma_{r}(q)$, which is proportional to $\Sigma_{s}$ instead
of $\tilde{\Sigma}_{s}$ as the latter describes the variance of the symmetric
kernel $H_{l,q}^{(s)}$ and hence $U_{n,q}$. However, as the leading term in
the Hoeffding-type decomposition of $U_{n,q}^{M}$ is a weighted U-statistic,
it is technically difficult to derive the exact form of the asymptotic
variance, but we still expect the asymptotic normality and independence to
hold, and we conjecture that there exists some constant $C_{q,s}^{M}$ such
that

$n^{qs/2}\Sigma_{s}^{-1/2}(q)U_{n,q}^{M,(qs)}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N(0,C_{q,s}^{M}),$

and we leave the rigourous proof for future research. If $h_{l}$ is fully
degenerate, i.e. $s=r$, then it is not difficult to see that
$C_{q,s}^{M}=(qr)!$ as $U_{n,q}$ and $U_{n,q}^{M}$ coincides in this case. In
Section 4.3, we propose a permutation based variance estimation procedure,
which avoids calculating the exact variance.

###  4.3 Variance Estimator

In Section 3.3, we have shown that

$[(qs)!]^{-1/2}\binom{r}{s}^{-q}n^{qs/2}\tilde{\Sigma}_{s}^{-1/2}(q)U_{n,q}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N(0,1).$

However, as $\tilde{\Sigma}_{s}(q)$ is unknown, we shall propose an unbiased
estimator $\hat{\Sigma}_{s}(q)$ for $\tilde{\Sigma}_{s}(q)$, with which we may
define the following studentized statistic,

$T_{n,q}=[(qs)!]^{-1/2}\binom{r}{s}^{-q}n^{qs/2}\hat{\Sigma}_{s}^{-1/2}(q)U_{n,q}$
(10)

Interestingly, the estimator $\hat{\Sigma}_{s}(q)$ still falls into the
framework introduced in this paper, i.e., it is the proposed U-statistic
$U_{n,q}$ associated with some kernels derived from $h_{l}$. Therefore, the
ratio-consistency is guaranteed by the theories in Section 3.3.

For illustration, consider $h_{l}$ with order 1. In this case, we have

$\tilde{\Sigma}_{1}(q)=\sum_{l_{1},l_{2}\in\mathcal{L}}{\mbox{cov}}^{q}\big{(}h_{l_{1}}(X_{1}),h_{l_{2}}(X_{1})\big{)}.$

Consider
$\mathcal{L}^{2}=\\{\bm{l}=(l_{1},l_{2}):l_{1},l_{2}\in\mathcal{L}\\}$, and
$\Theta=\big{(}\theta_{\bm{l}}\big{)}_{\bm{l}\in\mathcal{L}^{2}}$ with
$\theta_{\bm{l}}={\mbox{cov}}\big{(}h_{l_{1}}(X_{1}),h_{l_{2}}(X_{1})\big{)}$,
and the kernel $g_{\bm{l}}(X_{1})=h_{l_{1}}(X_{1})h_{l_{2}}(X_{1})$.

We can estimate $\tilde{\Sigma}_{1}(q)=\|\tilde{\Theta}\|_{q}^{q}$ with the
proposed U-statistic associated with $g_{\bm{l}}$, i.e.

$\sum_{\bm{l}\in\mathcal{L}^{2}}(P^{n}_{q})^{-1}\prod_{c=1}^{q}g_{\bm{l}}(X_{c})=\sum_{l_{1},l_{2}\in\mathcal{L}}(P^{n}_{q})^{-1}\prod_{c=1}^{q}h_{l_{1}}(X_{c})h_{l_{2}}(X_{c}).$

This is an unbiased estimator under the null where $\mathbb{E}[h_{l}]\equiv
0$. To handle the non-zero mean under the alternative, we simply center
$h_{l}$ and define
$\tilde{h}_{l}(X_{1})=h_{l}(X_{1})-\frac{1}{n}\sum_{i=1}^{n}h_{l}(X_{i}).$ We
modify the kernels $g_{\bm{l}}$ correspondingly, and define
$\tilde{g}_{\bm{l}}(X_{1})=\tilde{h}_{l_{1}}(X_{1})\tilde{h}_{l_{2}}(X_{1})$.
Then we may estimate $\tilde{\Sigma}_{1}(q)$ with the associated statistic

$\hat{\Sigma}_{1}(q)\overset{\Delta}{=}\sum_{\bm{l}\in\mathcal{L}^{2}}(P^{n}_{q})^{-1}\prod_{c=1}^{q}\tilde{g}_{\bm{l}}(X_{c})=\sum_{l_{1},l_{2}\in\mathcal{L}}(P^{n}_{q})^{-1}\prod_{c=1}^{q}\tilde{h}_{l_{1}}(X_{c})\tilde{h}_{l_{2}}(X_{c}).$

It is expected that $\hat{\Sigma}_{1}(q)$ is a ratio-consistent estimator for
$\tilde{\Sigma}_{1}(q)$, although a formal justification is beyond the scope
of this paper.

In general, for any non-degenerate ($s=1$) kernels with order $r>1$, we may
follow a similar procedure. Under the null, we may define the kernel
$g_{\bm{l}}(X_{1})=h_{l_{1}}^{(1)}(X_{1})h_{l_{2}}^{(1)}(X_{1})$. When the
exact form of $h_{l}^{(1)}$ is unknown, one approach is to estimate it based
on the sample and derive a plug-in estimator. An alternative approach is to
apply the fact that

$\mathbb{E}[h_{l_{1}}^{(1)}(X_{1})h_{l_{2}}^{(1)}(X_{1})]=\mathbb{E}[h_{l_{1}}(X_{1},\ldots,X_{r})h_{l_{2}}(X_{r},\ldots,X_{2r-1})],$

and define
$g_{\bm{l}}=h_{l_{1}}(X_{1},\ldots,X_{r})h_{l_{2}}(X_{r},\ldots,X_{2r-1})$ as
a kernel with order $2r-1$ instead. To guarantee the consistency under the
alternative, we have to define $\tilde{g}_{\bm{l}}$, the counterpart of
$g_{\bm{l}}$ obtained by centering $h_{l}^{(1)}$ or $h_{l}$. Moreover, we can
also consider the U-statistic with monotone indices, i.e. $U_{n,q}^{M}$ to
save computational cost, since we are only interested in obtaining a ratio-
consistent estimator for $\tilde{\Sigma}_{1}(q)$.

When $s>1$, the form becomes even more complicated. Since the computation of
$U_{n,q}$ with large $q$ is generally infeasible for $r\geq 2$, we recommend
using $U_{n,q}^{M}$ to construct the test in practice, and hence we do not
discuss the variance estimation for $U_{n,q}$ in the case $s\geq 2$.

For $U_{n,q}^{M}$, as discussed in Section 4, it is expected to be
asymptotically normal with asymptotic variance proportional to
$\Sigma_{s}(q)$, and we follow some non-parametric approaches to estimate the
asymptotic variance. One approach is to use permutation based variance
estimator. This applies to any testing problems where the distribution of the
test statistic is invariant up to certain permutations under the null, and
hence the proposed U-statistics computed on the permuted data has the same
distribution as the null distribution. For example, any test for component-
wise independence satisfies this property. The permutation based method is
also applicable to linear model coefficient testing example (under certain
model assumptions) introduced in Section 2.3.

For illustration, let $\sigma:[n]\rightarrow[n]$ denote a permutation on
$[n]$. To simulate the distribution of the following U-statistic, which was
proposed for testing the linear model coefficients.

$\displaystyle U_{n,q}^{M}=$
$\displaystyle(P^{n}_{2q})^{-1}\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{2q}\leq
n}2^{-q}\prod_{c=1}^{q}[(X_{i_{2c-1}}-X_{i_{2c}})(Y_{i_{2c-1}}-Y_{i_{2c}}-(X_{i_{2c-1}}-X_{i_{2c}})^{T}\bm{\beta}_{0})]_{l}$
$\displaystyle=$
$\displaystyle(P^{n}_{2q})^{-1}\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{2q}\leq
n}2^{-q}\prod_{c=1}^{q}[(X_{i_{2c-1}}-X_{i_{2c}})(E_{i_{2c-1}}-E_{i_{2c}})]_{l},$

where we have defined $E_{i}\overset{\Delta}{=}Y_{i}-X_{i}\bm{\beta}_{0}$ for
$i=1,\ldots,n$. Then we may consider

$U_{n,q}^{M,\sigma}=(P^{n}_{2q})^{-1}\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{2q}\leq
n}\prod_{c=1}^{q}h_{l}\big{(}(X_{i_{2c-1}},Y_{\sigma(i_{2c-1})}),(X_{i_{2c}},Y_{\sigma(i_{2c)}})\big{)},$

for any random permutation $\sigma$. Under the null
$\bm{\beta}=\bm{\beta}_{0}$, $E_{i}=\varepsilon_{i}$ is i.i.d. and independent
of $X_{i}$. Therefore, the distribution of $U_{n,q}^{M,\sigma}$ coincides with
that of $U_{n,q}^{M}$ under the null, and can be used to estimate the
asymptotic variance. To be more precise, consider $B$ random permutations
$\sigma_{1},\ldots,\sigma_{B}$. We estimate ${\mbox{var}}(U_{n,q}^{M})$ by the
permutation based sample variance, i.e.

$V_{n,q}^{M}=\frac{1}{B-1}\sum_{b=1}^{B}\left(U_{n,q}^{M,\sigma_{b}}-\frac{1}{B}\sum_{b^{\prime}=1}^{B}U_{n,q}^{M,\sigma_{b^{\prime}}}\right)^{2}.$

The studentized statistic is then defined as
$T_{n,q}^{M}=\frac{U_{n,q}^{M}}{\sqrt{V_{n,q}^{M}}}.$ We may also conduct
permutation based test by obtaining the critical value directly from the
empirical distribution of $\\{U_{n,q}^{M,\sigma_{b}}\\}_{b=1}^{B}$.
Empirically, we find that two approaches have similar performance when
$B=100$, and hence we only report the result of $T_{n,q}^{M}$ in the
simulations.

We remark that if we have computational power to calculate the full
U-statistic $U_{n,q}$, this permutation based approach is still applicable to
estimating the variance of $U_{n,q}$, and we simply replace
$U_{n,q}^{M,\sigma}$ by $U_{n,q}^{\sigma}$, that is, the full U-statistic
calculated on permuted sample.

The other possible approach is the (multiplier) bootstrap method. However, the
theoretical analysis for bootstrap based U-statistic with high orders is
challenging (Arcones and Gine,, 1992), and in this paper we rely mainly on the
permutation based approach.

###  4.4 Adaptive Testing Procedure

Let $I$ be a set of $q\in 2\mathbb{Z}_{+}$ (e.g. {2,6}). Under the null
$T_{n,q}$’s are asymptotically independent for different $q\in I$, we may
construct an adaptive test straightforwardly by combining $q\in I$. Denote the
$p$-values associated with $T_{n,q}$ as $p_{q}$, then we may define the
statistic of the adaptive test associated with $I\subseteq 2\mathbb{Z}_{+}$ as
$p_{ada}=\min_{q\in I}p_{q}$, and its corresponding $p$-value equals to
$1-(1-p_{ada})^{|I|}$.

Equivalently, if we want to conduct a level-$\alpha$ test, we may define the
adaptive test function with $I$ as

$\phi_{I,\alpha}=\max_{q\in I}\phi_{q,1-(1-\alpha)^{1/|I|}},$

where $\phi_{q,\alpha}$ is the level-$\alpha$ test based on $T_{n,q}$, i.e.
$\phi_{q,\alpha}=\mathbbm{1}(T_{n,q}>\Phi(1-\alpha))$ with $\Phi(x)$ denoting
the cdf of standard normal. Therefore, the adaptive test rejects the null if
one of $T_{n,q}$’s exceeds its critical value $\Phi((1-\alpha)^{1/|I|})$.
Similar procedure can be straightforwardly applied to $T_{n,q}^{M}$ as well.

In general, a smaller $q$ (say $q=2$) has higher power against dense
alternative, while a larger $q$ is favored under sparse alternative. With
adaptive test, we can combine the advantages of different $q$’s and achieve
high power against both dense and sparse alternatives, and the power of the
adaptive test goes to 1 as long as one of the test statistics $T_{n,q}$ has
asymptotic power 1. Since the corrected level $1-(1-\alpha)^{1/|I|}$ is
decreasing in $I$, it may hurt the overall power of the adaptive test to
include too many $q$ in $I$, even though each single-$q$ based test might be
optimal for some particular alternative. To have better finite sample
performance, we recommend to combine two single-$q$ based tests in practice,
which has relatively high power against alternatives with different sparsity.

###  4.5 Two Sample Asymmetric U-statistics

In this section, we introduce the two-sample U-statistics with monotone index,
which the dynamic programming can also be applied to. We mainly consider
kernels with order (1,1) for illustration, as the main motivating example is
the two-sample spatial sign test (Chakraborty and Chaudhuri,, 2017). Suppose
we observe two i.i.d. samples $X_{1},\ldots,X_{n}\in\mathbb{R}^{p}$ and
$Y_{1},\ldots,Y_{m}\in\mathbb{R}^{p}$. We want to test some high dimensional
parameter
$\Theta=\Theta(X_{i},Y_{i})=\\{\theta_{l}:l\in\mathcal{L}\\}=\bm{0}$. Recall
the full U-statistic is defined as

$U_{n,m,q}=\sum_{l\in\mathcal{L}}(P^{n}_{q}P^{m}_{q})^{-1}\sum^{*}_{1\leq
i_{1},\ldots,i_{q}\leq n}\sum^{*}_{1\leq j_{1},\ldots,j_{q}\leq
m}\prod_{c=1}^{q}h_{l}(X_{i_{c}},Y_{j_{c}}).$

In particular, for the spatial sign test, we take
$\mathcal{L}=\\{1,\ldots,p\\}$, and
$h_{l}(X_{i},Y_{j})=(x_{i,l}-y_{j,l})\,/\,\|X_{i}-Y_{j}\|$.

As the computation of $U_{n,m,q}$ is $O(n^{q}m^{q})$, we consider the
monotonically-indexed counterpart as follows,

$U_{n,m,q}^{M}=\sum_{l\in\mathcal{L}}\binom{n}{q}^{-1}\binom{m}{q}^{-1}\sum_{1\leq
i_{1}<\cdots<i_{q}\leq n}\sum_{1\leq j_{1}<\cdots<j_{q}\leq
m}\prod_{c=1}^{q}h_{l}(X_{i_{c}},Y_{j_{c}}).$

With dynamic programming, we can speed up the computation of $U_{n,m,q}^{M}$
to $O(mn)$. For $q\leq i\leq n$ and $q\leq j\leq m$, define

$S_{q,l}^{M}(i,j)=\sum_{1\leq i_{1}<\cdots<i_{q-1}<i}\sum_{1\leq
j_{1}<\cdots<j_{q-1}<j}h_{l}(X_{i},Y_{j})\prod_{c=1}^{q-1}h_{l}(X_{i_{c}},Y_{j_{c}}),$

which involves all the summands in $U_{n,m,q}^{M}$ s.t. the largest indices of
$X$ and $Y$ are $i$ and $j$, respectively. We also define

$D_{q,l}^{M}(i,j)=\sum_{1\leq i_{1}<\cdots<i_{q}\leq i}\sum_{1\leq
j_{1}<\cdots<j_{q}\leq j}\prod_{c=1}^{q}h_{l}(X_{i_{c}},Y_{j_{c}}).$

If we view $S_{q,l}(i,j)$ as a matrix indexed by $i\in[1,n],j\in[1,m]$, then
$D_{q,l}(i,j)$ adds up all the elements that is top and left to the $(i,j)$-th
element. In particular, we have

$U_{n,m,q}^{M}=\binom{n}{q}^{-1}\binom{m}{q}^{-1}\sum_{l\in\mathcal{L}}D_{q,l}^{M}(n,m),$

and $S_{q,l}^{M}(i,j)=D_{q-1,l}^{M}(i-1,j-1)h_{l}(X_{i},Y_{j})$. We first
initialize $D_{0,l}^{M}(i,j)\equiv 1$ for all $i,j$. Then we use the following
recursive updating formula for $c=1,\ldots,q$ and $i,j\geq c$,

$\displaystyle D_{c,l}^{M}(i,j)=$ $\displaystyle
S_{c,l}^{M}(i,j)+D_{c,l}^{M}(i-1,j)+D_{c,l}^{M}(i,j-1)-D_{c,l}^{M}(i-1,j-1)$
$\displaystyle=$ $\displaystyle
D_{c-1,l}^{M}(i-1,j-1)h_{l}(X_{i},Y_{j})+D_{c,l}^{M}(i-1,j)+D_{c,l}^{M}(i,j-1)-D_{c,l}^{M}(i-1,j-1).$

We conjecture that the statistics $U_{n,m,q}$ and $U_{n,m,q}^{M}$ are both
asymptotically normal. Their variances can be estimated by permutation (i.e.
randomly permuting the data between two samples), similar to the one-sample
setting.

##  5 Simulation Studies

In this section, we examine the finite sample performance of the proposed
single-$q$ and adaptive tests via simulations. Throughout this section, for
kernels with $r=1$ such as the spatial sign test, we use $T_{n,q}$ based on
the variance estimator introduced in Section 4.3; for $r>1$, we construct the
test with $T_{n,q}^{M}$ using the permutation based variance estimator.
Section 5.1 presents the simulation results for one-sample test of spatial
sign, and Section 5.4 includes its two-sample counterpart. Section 5.2
contains the results for testing component-wise independence, and Section 5.3
corresponds to testing the nullity of linear model coefficients. For all
testing problems, we perform 1000 Monte Carlo replications.

###  5.1 Tests for Spatial Sign

In this subsection, we want to test

$\mathcal{H}_{0}:\mathbb{E}[X_{i}/\|X_{i}\|\,]=\bm{0}\quad
v.s.\quad\mathcal{H}_{a}:\mathbb{E}[X_{i}/\|X_{i}\,\|]\not=\bm{0}.$

This is similar to the standard mean-testing problem
$\mathcal{H}_{0}:\mathbb{E}[X_{i}]=\bm{0}$ and
$\mathcal{H}_{a}:\mathbb{E}[X_{i}]\not=\bm{0}$, with certain elliptical
symmetry assumption, but does not require the existence of first moment. Wang
et al., (2015) extended the U-statistic based two sample test by Chen and Qin,
(2010) and proposed the $L_{2}$-norm based spatial sign test statistic, which
is indeed a special case of our U-statistic with kernel
$h_{l}(X_{i})=x_{i,l}/\|X_{i}\|$ and $q=2$, although they use a different
variance estimator. Through both theory and simulations, Wang et al., (2015)
found that their test has slight power loss compared to the test by Chen and
Qin, (2010) for Gaussian data, but has much higher power for heavy-tailed
data. However, the $L_{2}$-norm based spatial sign test mainly targets at
dense alternatives, and their performance under the sparse alternative is not
yet examined.

Below we generate the simulated data from the model $X_{i}=Z_{i}+\mu$, where
$Z_{i}\in\mathbb{R}^{p}$ has i.i.d. standard normal or $t_{3}$ components. We
include both sparse and dense alternatives, (corresponding to $r=2$ and $r=p$,
respectively) and also consider both light and heavy-tailed distributions
(i.e., standard normal versus $t_{3}$). Table 1 collects the size and power
results. Among all the tests being compared, we mention that mean test with
$q=2$ corresponds to the test by Chen and Qin, (2010) (up to a different
variance estimator), spatial sign test with $q=2$ corresponds to the test by
Wang et al., (2015) (up to a different variance estimator). Our test with
$q=2$ performs very similar to the test by Chen and Qin, (2010) (for mean
test) and the test by Wang et al., (2015) (for spatial sign test), and
therefore we omit the results of their tests.

DGP | $\delta,r$ | Test | $q=2$ | $q=4$ | $q=6$ | $q=2,4$ | $q=2,6$
---|---|---|---|---|---|---|---
Gaussian | 0, NA | mean | 6.1 | 5.9 | 3.0 | 6.4 | 5.4
spatial sign | 5.8 | 6.1 | 3.2 | 6.4 | 5.6
0.3, 2 | mean | 74.3 | 96.3 | 90.0 | 96.3 | 91.4
spatial sign | 74.5 | 96.0 | 90.0 | 96.2 | 92.1
0.1, $p$ | mean | 100 | 92.2 | 37.8 | 100 | 100
spatial sign | 100 | 92.1 | 37.3 | 100 | 100
$t_{3}$ | 0, NA | mean | 6.1 | 4.5 | 1.9 | 6.8 | 4.8
spatial sign | 6.2 | 4.8 | 2.1 | 6.9 | 4.9
0.4, 2 | mean | 42.7 | 73.1 | 57.6 | 72.7 | 63.6
spatial sign | 51.1 | 79.3 | 65.4 | 80.1 | 71.1
0.1, $p$ | mean | 98.2 | 30.1 | 14.5 | 97.0 | 97.0
spatial sign | 99.8 | 36.5 | 15.6 | 99.3 | 99.3
Table 1: Size and power in percentage for mean and spatial sign test

As seen from Table 1, the size for smaller $q$ (i.e., $q=2,4$) tends to be
more accurate than that for large $q$ (i.e., $q=6$), which exhibits some
undersize. The adaptive test based on $q=2,4$ has slight oversize whereas the
size for $q=2,6$ appears accurate. In terms of the power, single $q$ tests
based on large and small $q$’s correspond to high power against sparse and
dense alternatives, respectively, as expected. Moreover, for both alternatives
and all $q$, there is no obvious power loss when we compare the spatial sign
test to the mean test for Gaussian data, but the former has notable higher
power for $t_{3}$-distributed data. This suggests that the power robustness
and advantage of spatial-sign test based on $L_{2}$ norm, as discovered first
in Wang et al., (2015), carries over to the more general $L_{q}$-norm setting.
Finally, we see that the adaptive tests have overall good power against both
sparse and dense alternatives, and they are always very close to the best
single $q$ test in power. It appears that the adaptive test with $q=$(2,4)
slightly outperforms its counterpart with $q=$(2,6) in the sparse regime,
which might be related to its slight oversize for both settings.

###  5.2 Tests for Component-wise Independence

In this subsection, we compare several tests for the componentwise
independence based on Kendall’s $\tau$ statistic. We generate i.i.d. data
$X_{1},\ldots,X_{n}\in\mathbb{R}^{p}$ according to the following two settings
used in Leung and Drton, (2018).

  * •

Gaussian vectors with banded covariance matrix: $X_{i}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}N(0,\Sigma)$ for $i=1,\ldots,n$, where
$\Sigma=(\sigma_{ab})_{a,b=1}^{p}$ with
$\sigma_{ab}=(1-\delta)1\\{a=b\\}+\delta 1\\{a\leq r,~{}b\leq r\\}$.

  * •

$t$-distribution with banded covariance matrix: $X_{i}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\Sigma^{1/2}Z$ for $i=1,\ldots,n$, where $\Sigma$ is given
above, and $Z_{ij}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}t_{3};~{}i=1,\ldots,n;j=1,\ldots,p$.

We set $\delta=0$ under the null,
$(\delta,r)=(0.5,3),\,(0.3,4),\,(0.25,6),\,(0.15,10),\,(p,0.05)$ for
alternatives with different sparsity levels, and $(n,p)=(100,50)$.

Among the tests we compare, we include our test $U_{n,q}^{M}$ with a
permutation-based variance estimator, the Kendall’s $\tau$ based maximum-type
statistic introduced in Han et al., (2017) (denoted as $L_{\infty}$ in Table
2), the Kendall’s $\tau$ based sum-of-squares-type statistic proposed in Leung
and Drton, (2018) (denoted as $L_{2}$ in Table 2), a simple combination of
$L_{2}$ and $L_{\infty}$ based on Bonferroni correction (denoted as
$L_{2}\&L_{\infty}$ in Table 2).

Note that the $L_{2}$ test by Leung and Drton, (2018) includes the diagonal
terms, and is only asymptotically unbiased. They also have an unbiased
$L_{2}$-type statistic, which is a special case of our proposed full
U-statistic with $q=2$, and its performance is very similar to the biased
version according to the simulations, so is not reported. Leung and Drton,
(2018) also introduce an efficient algorithm based on inclusion-exclusion law
to reduce the computational complexity from $O(n^{2r})$ to $O(n^{r})$ ($r=2$
in this example). However, this idea can only be applied to $q=2$, and in
general, their idea can speed up the computation from $O(n^{qr})$ to
$O(n^{(q-1)r})$ for the exact U-statistic. Our monotonically-indexed
U-statistic $U_{n,q}^{M}$ loses a constant ratio of efficiency compared to
$U_{n,q}$, but can reduce the computational burden to $O(n^{r})$ for any $q$.

DGP | $\delta,r$ | $q=2$ | $q=4$ | $q=6$ | $q=2,4$ | $q=2,6$ | $L_{2}$ | $L_{\infty}$ | $L_{2}\&L_{\infty}$
---|---|---|---|---|---|---|---|---|---
Gaussian | 0, NA | 5.5 | 5.0 | 5.8 | 6.4 | 7.3 | 5.8 | 4.6 | 5.6
0.5, 3 | 38.8 | 96.2 | 95.6 | 96.4 | 95.2 | 43.8 | 98.6 | 97.2
0.3, 4 | 25.4 | 42.6 | 34.0 | 45.0 | 38.8 | 29.0 | 39.4 | 41.4
0.25, 6 | 43.8 | 47.0 | 30.0 | 56.4 | 48.0 | 51.8 | 37.0 | 53.2
0.15, 10 | 48.4 | 22.2 | 11.6 | 48.2 | 45.4 | 53.6 | 14.6 | 50.0
0.05, $p$ | 95.4 | 14.4 | 9.0 | 93.6 | 93.8 | 96.2 | 13.0 | 94.6
$t_{3}$ | 0, NA | 4.3 | 4.9 | 4.7 | 5.2 | 5.1 | 5.2 | 2.9 | 4.3
0.5, 3 | 54.0 | 99.8 | 99.6 | 99.8 | 99.8 | 60.0 | 100 | 99.8
0.3, 4 | 40.4 | 72.0 | 63.2 | 70.2 | 64.2 | 44.2 | 71.2 | 68.4
0.25, 6 | 71.2 | 80.0 | 64.4 | 83.6 | 77.4 | 76.2 | 66.8 | 78.4
0.15, 10 | 78.6 | 47.6 | 22.6 | 76.0 | 73.0 | 83.2 | 27.8 | 76.8
0.05, $p$ | 100 | 30.8 | 16.0 | 100 | 100 | 100 | 23.8 | 100
Table 2: Size and power in percentage for Kendall’s $\tau$ tests

In Table 2, we report the size and power of all Kendall $\tau$ based tests for
a range of alternatives with varying degrees of sparsity. As we can see, the
sizes for most tests are accurate, except for the adaptive test with $q=(2,6)$
for Gaussian data and the $L_{\infty}$ method for the $t_{3}$ case. In terms
of the power, the proposed statistic with $q=2$ and $L_{2}$ method in Leung
and Drton, (2018) are favored for dense alternative, whereas our statistics
based on large $q$ or $L_{\infty}$ method in Han et al., (2017) have higher
power under sparse alternative. The $L_{2}$ method slightly outperforms our
studentized $U_{n,q}^{M}$ (with $q=2$), which is expected since the
monotonically indexed-U statistic is less (statistically) efficient compared
to full $U$ statistic.The adaptive test based on $q=(2,4)$ seems to have
comparable performance with $L_{2}\&L_{\infty}$ (i.e., a simple combination of
$L_{2}$ and $L_{\infty}$ based on naive Bonferroni correction), although the
asymptotic independence between $L_{2}$ and $L_{\infty}$ statistics based on
Kendall’s $\tau$ seems yet established in the literature. In some mildly
sparse or mildly dense cases (i.e., $(\delta,r)=(0.3,4),(0.25,6)$), we see
that the adaptive test based on $q=(2,4)$ slightly outperforms
$L_{2}\&L_{\infty}$, demonstrating the additional merit by incorporating
$L_{q}$ norm based test, where $q\not=2,\infty$, in forming the adaptive test.

###  5.3 Tests for Linear Model Coefficients

In this subsection, we present some simulation results for testing the nullity
of linear regression coefficients. Let the data
$\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ be i.i.d. samples from linear model
$Y_{i}=X_{i}\bm{\beta}+\varepsilon_{i}$ and the goal is to test
$\mathcal{H}_{0}:\bm{\beta}=\bm{0}$ against
$\mathcal{H}_{a}:\bm{\beta}\not=\bm{0}$. Recall that the kernel function is of
order 2 as in (1), with $\bm{\beta}_{0}=\bm{0}$,
$h_{l}(W_{1},W_{2})=(x_{1,l}-x_{2,l})(Y_{1}-Y_{2})/2,$ and the parameter to
test equals $\Sigma\bm{\beta}$. The test statistic proposed in Zhong and Chen,
(2011) is indeed a special case of ours with $q=2$ (hence their kernel is of
order $qr$=4), standardized by a different variance estimator. We set
$(n,p)=(100,50),\,(200,100)$, $\bm{\beta}=\delta(\bm{1}_{r},\bm{0}_{p-r})$,
and generate $X_{i}\sim N(0,\Sigma)$ independent of $\varepsilon_{i}\sim
N(0,1)$. We consider $\Sigma=(\sigma_{a,b})_{a,b=1}^{p}$ from AR(1) structure
with $\sigma_{a,b}=\rho^{|a-b|}$, and $q=2,4,6$.

In Table 3, we present the results for $U_{n,2}$, $U_{n,q}^{M}$-based tests
(with permutation-based variance estimator) for $q=2,4,6,(2,4)$ and $(2,6)$,
Bonferonni type combination of $U_{n,2}$ with $U_{n,q}^{M}$ for $q=4,6$.
Computationally speaking, the computational cost for the monotonically indexed
U-statistic $U_{n,q}^{M}$ and the studentized statistic $T_{n,q}^{M}$ is
$O(n^{2})$ for any $q$. The full calculation of $U_{n,2}$ is implemented via
the efficient algorithm proposed in Leung and Drton, (2018) so the cost is
reduced from $O(n^{4})$ to $O(n^{2})$. In our unreported simulations, we also
compare the performance of $U_{n,2}$ (with permutation-based variance
estimator) to that of Zhong and Chen, (2011), and find that they lead to very
similar results. Note that the computation of the studentized test in Zhong
and Chen, (2011) requires $O(n^{4})$ computation.

$(n,p)$ | $\delta,r,\rho$ | $U_{n,q}$ | $U_{n,q}^{M}$ |  $U_{n,2}$ & $U_{n,q}^{M}$
---|---|---|---|---
$q=2$ | $q=4$ | $q=6$ | $q=2,4$ | $q=2,6$ | $q=4$ | $q=6$
(100,50) | 0, NA, 0 | 6.3 | 5.7 | 6.4 | 3.1 | 6.3 | 4.6 | 7.2 | 5.7
0, NA, 0.5 | 7.0 | 6.5 | 4.6 | 4.1 | 6.5 | 5.7 | 7.0 | 6.4
0.25, 2, 0 | 29.2 | 21.2 | 28.4 | 17.8 | 31.2 | 25.4 | 34.4 | 29.4
0.25, 2, 0.5 | 60.4 | 45.6 | 62.6 | 49.6 | 65.2 | 57.0 | 69.6 | 62.8
0.05, $p$, 0 | 31.2 | 24.8 | 8.0 | 6.8 | 22.8 | 22.2 | 27.8 | 26.4
0.05, $p$, 0.5 | 98.0 | 92.2 | 45.6 | 19.6 | 89.6 | 89.6 | 96.8 | 97.0
(200,100) | 0, NA, 0 | 5.7 | 5.5 | 4.9 | 3.5 | 5.1 | 5.6 | 5.2 | 5.3
0, NA, 0.5 | 6.6 | 5.9 | 3.9 | 2.6 | 6.3 | 5.1 | 6.8 | 5.5
0.25, 2, 0 | 45.2 | 32.4 | 56.8 | 46.8 | 58.2 | 52.6 | 63.8 | 57.8
0.25, 2, 0.5 | 81.6 | 62.2 | 93.6 | 90.4 | 92.8 | 92.0 | 94.6 | 93.8
0.035, $p$, 0 | 42.4 | 30.4 | 10.2 | 7.6 | 27.8 | 28.0 | 36.2 | 36.6
0.035, $p$, 0.5 | 100 | 99.4 | 57.6 | 28.6 | 99.4 | 99.4 | 100 | 100
Table 3: Size and power in percentage for linear model coefficients testing

As we can see from Table 3, all tests appear to have quite reasonable size,
and there are some mild size distortion in some cases. As expected, large $q$
has higher power against sparse alternative while small $q$ outperforms under
dense alternative. Comparing $U_{n,2}$ with $U_{n,2}^{M}$, we see a noticeable
power loss for $U_{n,2}^{M}$. This is not surprising since the monotonically
indexed U-statistic tends to lose some statistical efficiency. In the event
that the computational complexity of $L_{2}$-norm test statistic can be made
to $O(n^{2})$, we recommend to calculate the full U-statistic, i.e., $U_{n,2}$
and combine with $U_{n,q}^{M}$ for $q=4,6$. For this example, the adaptive
test based on $U_{n,2}$ and $U_{n,4}^{M}$ appears to have the best power or
close to the best single-$q$ test in power.

###  5.4 Two-Sample Tests for Spatial Sign

In this subsection, we study the size and power property for two-sample
spatial sign test developed by (Chakraborty and Chaudhuri,, 2017) and compare
with its $L_{q}$-norm based extension and adaptive tests. The first sample is
generated as $\\{X_{i}\\}_{i=1}^{n}=\\{Z_{i}+\mu\\}_{i=1}^{n}$ and the second
sample $\\{Y_{j}\\}_{j=1}^{m}$, where we set
$\mu=\delta(\bm{1}_{r}^{T},\bm{0}_{p-r}^{T})^{T},$ and generate $\\{Y_{i}\\}$
and $\\{Z_{j}\\}$ in the following way:

  * •

Standard Gaussian: $Y_{i},Z_{j}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}N(0,I_{p});~{}i=1,\ldots,n;\,j=1,\ldots,m$.

  * •

$t$-distribution: $Y_{il},Z_{jl}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}t_{3};~{}i=1,\ldots,n;\,j=1,\ldots,m;\,l=1,\ldots,p$.

We set $n=m=50,\,p=100$.

DGP | $\delta,r$ | $q=2$ | $q=4$ | $q=6$ | $q=2,4$ | $q=2,6$
---|---|---|---|---|---|---
Gaussian | 0, NA | 2.9 | 6.2 | 6.8 | 4.2 | 5.2
1, 2 | 17.2 | 94.2 | 91.0 | 91.2 | 90.8
0.3, $p$ | 96.4 | 69.2 | 37.2 | 95.6 | 96.2
$t_{3}$ | 0, NA | 2.4 | 5.0 | 5.6 | 4.2 | 4.7
1, 2 | 3.8 | 37.8 | 41.4 | 34.0 | 38.6
0.5, $p$ | 98.3 | 76.6 | 45.6 | 97.4 | 97.5
Table 4: Size and power in percentage for two-sample spatial sign test

According to Table 4, most tests have relatively accurate size, except for the
case $q=2$, which exhibits slightly conservative size for two-sample spatial
sign test. This is opposite to the findings in one-sample test where large $q$
tends to be conservative. As is the case for one-sample spatial sign test,
small and large $q$ correspond to high power against dense and sparse
alternatives, respectively. Again, the adaptive test based on $(2,4)$ or
$(2,6)$ combines the advantages of single $q$ tests and has comparable power
to the best single-$q$ test.

##  6 Real Data Application

In this section, we apply the two-sample spatial sign based test (with
permutation) to the Connectionist Bench dataset publicly available at machine
learning UCI website (http://www.cs.ucr.edu/eamonn/time_series_data). The
dataset we examined contains 111 samples of sonar signals from metal cylinder
and 97 samples from rocks. We follow the approach in (Chakraborty and
Chaudhuri,, 2017) to study the size and power of the proposed two sample test
with different $q$s. For the size simulation, we randomly generate two
subsamples with sample size 40 from the rock sample, and calculate the average
rejection rate. In terms of the power, we generate two subsamples also with
sample size 40 from metal and rock samples, and find the average rejection
probability from 1000 repetitions. The results are summarized in Table 5.

Statistic | $q=2$ | $q=4$ | $q=6$ | $q=2,4$ | $q=2,6$
---|---|---|---|---|---
Size | 2.1 | 5.9 | 6.2 | 4.1 | 5.5
Power | 22.2 | 48.7 | 30.1 | 42.6 | 33.2
Table 5: Size and power in percentage for a real data application

As we can see from the table, $q=2$ exhibits conservative size while all other
tests have relatively accurate size. As regards the power, $q=4$ has highest
power followed by $q=6$, which outperforms $q=2$, implying that the underlying
alternative is better captured with $q=4$ than $q=2$. With adaptive test
combining $q=2,4$ (or $2,6$), we can obtain higher power than the single $q$
based statistic with $q=2$ as studied in Chakraborty and Chaudhuri, (2017).
This clearly demonstrates the value of the adaptive tests we developed. In
practice, it would be informative to determine which $q$ is more powerful to
the data at hand, and which pair of $q$s to use in adaptive combination. We
leave this topic to future research.

##  7 Conclusion

In this paper, we propose a family of $L_{q}$-norm based U-statistics for
high-dimensional i.i.d. data and show that they are asymptotically normal and
independent for different $q$s under mild moment and cumulant assumptions. Our
work is inspired by He et al., (2021), who first demonstrated the asymptotic
normality and independence of $L_{q}$-norm based U-statistics for testing of
mean vectors and covariance matrices. Our results are obtained for a broad
class of kernel functions, and can be viewed as a significant extension of
those in He et al., (2021), which is limited to kernel function of order $1$.
In particular, we highlight the usefulness of our results in both theory and
simulations for several global testing problems that are not covered by He et
al., (2021), including one sample spatial sign based test, simultaneous
testing of linear model coefficients, component-wise independent tests via
Kendall’s $\tau$, and two sample spatial sign based test.

To capture both sparse and dense alternatives, we develop a simple Bonferonni
type combination of two studentized $L_{q}$-norm based test statistics via
their p-values, and show that it leads to an adaptive test with high power
against both dense and sparse alternatives. To alleviate the computational
burden, we propose a variant of symmetric U-statistic by focusing on monotone
indices in the summation, to which the idea of dynamic programming can be
applied. With some moderate loss of statistical efficiency, we are able to
reduce the computation cost from $O(n^{qr})$, which corresponds to full
symmetric U-statistic, to $O(n^{r})$, where $r$ is the order of the kernel.
According to the simulation results, it appears that a combination of the
existing $L_{2}$ norm based test with monotonically indexed $L_{q}$ norm based
test ($q=4$ or $6$) achieves satisfactory power against both sparse and dense
alternatives with the computational cost of order $O(n^{2})$.

To conclude, we mention a few worthy future directions. It would be
interesting to generalize the asymptotic theory to high-dimensional time
series, as many of the global testing problems we tackled here can be
naturally posed for high-dimensional time series data. We expect that this
extension will be nontrivial since temporal dependence can bring non-
negligible impact on the validity of normal approximation for $L_{q}$-norm
based test statistic. Moreover, it might also be interesting to extend our
methodology and theory to change point detection problem, which is similar to
but more involved than a two sample testing problem due to the unknown change-
point locations; see Zhang et al., (2021) for the use of $L_{q}$-norm based
test statistics for the mean change-point testing in high-dimensional data.
Finally, estimation of asymptotic variance is an important problem for
inference and yet to be addressed in the high-dimensional setting. We
conjecture that Bootstrap can work but may deserve some caution due to the
high-dimensionality of observations, and a rigorous theory is needed. We leave
these open problems for future study.

Supplement to “Adaptive Testing for High-dimensional Data" The supplementary
material contains all the proofs for theoretical results stated in the paper.

## References

  * Andrews, (1991) Andrews, D. W. (1991).  Heteroskedasticity and autocorrelation consistent covariance matrix estimation.  Econometrica: Journal of the Econometric Society, pages 817–858.
  * Arcones and Gine, (1992) Arcones, M. A. and Gine, E. (1992).  On the bootstrap of U and V statistics.  The Annals of Statistics, 20(2):655–674.
  * Bai et al., (2009) Bai, Z., Jiang, D., Yao, J.-F., and Zheng, S. (2009).  Corrections to lrt on large-dimensional covariance matrix by rmt.  The Annals of Statistics, 37(6B):3822–3840.
  * Bai and Saranadasa, (1996) Bai, Z. and Saranadasa, H. (1996).  Effect of high dimension: by an example of a two sample problem.  Statistica Sinica, 6(2):311–329.
  * Cai et al., (2013) Cai, T., Liu, W., and Xia, Y. (2013).  Two-sample covariance matrix testing and support recovery in high-dimensional and sparse settings.  Journal of the American Statistical Association, 108(501):265–277.
  * Cai and Jiang, (2011) Cai, T. T. and Jiang, T. (2011).  Limiting laws of coherence of random matrices with applications to testing covariance structure and construction of compressed sensing matrices.  The Annals of Statistics, 39(3):1496–1525.
  * Cai et al., (2014) Cai, T. T., Liu, W., and Xia, Y. (2014).  Two-sample test of high dimensional means under dependence.  Journal of the Royal Statistical Society: Series B: Statistical Methodology, 76(2):349–372.
  * Chakraborty and Chaudhuri, (2017) Chakraborty, A. and Chaudhuri, P. (2017).  Tests for high-dimensional data based on means, spatial signs and spatial ranks.  The Annals of Statistics, 45(2):771–799.
  * Chen and Qin, (2010) Chen, S. X. and Qin, Y.-L. (2010).  A two-sample test for high-dimensional data with applications to gene-set testing.  The Annals of Statistics, 38(2):808–835.
  * Chen et al., (2010) Chen, S. X., Zhang, L.-X., and Zhong, P.-S. (2010).  Tests for high-dimensional covariance matrices.  Journal of the American Statistical Association, 105(490):810–819.
  * Drton et al., (2020) Drton, M., Han, F., and Shi, H. (2020).  High-dimensional consistent independence testing with maxima of rank correlations.  The Annals of Statistics, 48(6):3206–3227.
  * El Karoui, (2009) El Karoui, N. (2009).  Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond.  The Annals of Applied Probability, 19(6):2362–2405.
  * Goeman et al., (2006) Goeman, J. J., Van De Geer, S. A., and Van Houwelingen, H. C. (2006).  Testing against a high dimensional alternative.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(3):477–493.
  * Gregory et al., (2015) Gregory, K. B., Carroll, R. J., Baladandayuthapani, V., and Lahiri, S. N. (2015).  A two-sample test for equality of means in high dimension.  Journal of the American Statistical Association, 110(510):837–849.
  * Hall and Jin, (2010) Hall, P. and Jin, J. (2010).  Innovated higher criticism for detecting sparse signals in correlated noise.  The Annals of Statistics, 38(3):1686–1732.
  * Han et al., (2017) Han, F., Chen, S., and Liu, H. (2017).  Distribution-free tests of independence in high dimensions.  Biometrika, 104(4):813–828.
  * He et al., (2021) He, Y., Xu, G., Wu, C., and Pan, W. (2021).  Asymptotically independent u-statistics in high-dimensional testing.  The Annals of Statistics, 49(1):154–181.
  * Jiang, (2004) Jiang, T. (2004).  The asymptotic distributions of the largest entries of sample correlation matrices.  The Annals of Applied Probability, 14(2):865–880.
  * Ledoit and Wolf, (2002) Ledoit, O. and Wolf, M. (2002).  Some hypothesis tests for the covariance matrix when the dimension is large compared to the sample size.  The Annals of Statistics, 30(4):1081–1102.
  * Leung and Drton, (2018) Leung, D. and Drton, M. (2018).  Testing independence in high dimensions with sums of rank correlations.  The Annals of Statistics, 46(1):280–307.
  * Li and Chen, (2012) Li, J. and Chen, S. X. (2012).  Two sample tests for high-dimensional covariance matrices.  The Annals of Statistics, 40(2):908–940.
  * Liu et al., (2008) Liu, W.-D., Lin, Z., and Shao, Q.-M. (2008).  The asymptotic distribution and berry–esseen bound of a new test for independence in high dimension with an application to stochastic optimization.  The Annals of Applied Probability, 18(6):2337–2366.
  * Shao and Zhou, (2014) Shao, Q.-M. and Zhou, W.-X. (2014).  Necessary and sufficient conditions for the asymptotic distributions of coherence of ultra-high dimensional random matrices.  The Annals of Probability, 42(2):623–648.
  * Shao and Wu, (2007) Shao, X. and Wu, W. B. (2007).  Local whittle estimation of fractional integration for nonlinear processes.  Econometric Theory, 23(5):899–929.
  * Srivastava and Du, (2008) Srivastava, M. S. and Du, M. (2008).  A test for the mean vector with fewer observations than the dimension.  Journal of Multivariate Analysis, 99(3):386–402.
  * Srivastava et al., (2016) Srivastava, R., Li, P., and Ruppert, D. (2016).  Raptt: An exact two-sample test in high dimensions using random projections.  Journal of Computational and Graphical Statistics, 25(3):954–970.
  * Wang et al., (2015) Wang, L., Peng, B., and Li, R. (2015).  A high-dimensional nonparametric multivariate test for mean vector.  Journal of the American Statistical Association, 110(512):1658–1669.
  * Wang et al., (2022) Wang, R., Zhu, C., Volgushev, S., and Shao, X. (2022).  Inference for change points in high-dimensional data via selfnormalization.  The Annals of Statistics, 50(2):781–806.
  * Wu et al., (2019) Wu, C., Xu, G., and Pan, W. (2019).  An adaptive test on high-dimensional parameters in generalized linear models.  Statistica Sinica, 29(4):2163–2186.
  * Wu, (2005) Wu, W. B. (2005).  Nonlinear system theory: Another look at dependence.  Proceedings of the National Academy of Sciences, 102(40):14150–14154.
  * Wu and Shao, (2004) Wu, W. B. and Shao, X. (2004).  Limit theorems for iterated random functions.  Journal of Applied Probability, 41(2):425–436.
  * Xu et al., (2016) Xu, G., Lin, L., Wei, P., and Pan, W. (2016).  An adaptive two-sample test for high-dimensional means.  Biometrika, 103(3):609–624.
  * Zhang et al., (2021) Zhang, Y., Wang, R., and Shao, X. (2021).  Adaptive inference for change points in high-dimensional data.  Journal of the American Statistical Association, In press.
  * Zhong and Chen, (2011) Zhong, P.-S. and Chen, S. X. (2011).  Tests for high-dimensional regression coefficients with factorial designs.  Journal of the American Statistical Association, 106(493):260–274.
  * Zhurbenko and Zuev, (1975) Zhurbenko, I. and Zuev, N. (1975).  On higher spectral densities of stationary processes with mixing.  Ukrainian Mathematical Journal, 27(4):364–373.

SUPPLEMENT TO “ADAPTIVE TESTING FOR HIGH-DIMENSIONAL DATA”

BY YANGFAN ZHANG, RUNMIN WANG AND XIAOFENG SHAO

The supplement is organized as follows. In Appendix A, we verify the
assumptions for the main theory for several testing problems we focus on.
Appendix B includes all technical proofs.

##  Appendix A Verification of Assumptions

In this section, we verify the assumptions on different testing problems. We
first summarize the assumptions we need to check. Assumption 2 is trivial if
the order of the kernels is one ($r=1$), or more generally, if the kernel is
fully degenerate ($r=s$). Assumption 3 (b2) is necessary only for degenerate
kernels ($s>1$).

###  A.1 Mean testing and covariance testing

These two examples have kernels with order $r=1$, so we only meed to check
Assumption 3 (a) and (b1). They are implied by Assumption 1 and the proof can
be found in Wang et al., (2022) for mean testing, with $C_{p}=c_{0}$ for some
constant $c_{0}$. Therefore, our theory applies if $X_{i}$ satisfies
Assumption 1. In terms of covariance testing, it suffices to view
$(x_{i,p_{1}}x_{i,p_{2}})_{(p_{1},p_{2})\in\mathcal{L}}$ as i.i.d. random
vectors in $\mathbb{R}^{|\mathcal{L}|}$ and verify Assumption 1 for them.

###  A.2 Spatial sign testing

For spatial sign, recall $h_{l}(X_{i})=x_{i,l}/\|X_{i}\|$ and
$H_{l,q}(X_{1},\ldots,X_{q})=h_{l}(X_{1})\cdots h_{l}(X_{q})$. It is
technically difficult to verify Assumption 1 for $h_{l}$ directly. Instead, we
show the martingale CLT for $D_{n,q}$. As we need to go through the proof of
the main theorem in Appendix B, we only highlight the new argument required
for spatial sign. Recall that the associated martingale difference sequence
(with proper normalization) is given by

$\displaystyle\xi_{n,i}=$
$\displaystyle\alpha_{1}q!n^{-q/2}\tilde{\Sigma}^{-1/2}_{1}(q)\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{q-1}<i}H_{l,q}^{(t)}(X_{i_{1}},\ldots,X_{i_{q-1}},X_{i})$
$\displaystyle+\alpha_{2}Q!n^{-Q/2}\tilde{\Sigma}^{-1/2}_{1}(Q)\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{Q-1}<i}H_{l,Q}^{(t)}(X_{i_{1}},\ldots,X_{i_{Q-1}},X_{i})$
$\displaystyle\overset{\Delta}{=}$
$\displaystyle\alpha_{1}q!\xi_{n,i}^{(1)}+\alpha_{2}Q!\xi_{n,i}^{(2)}.$

Following Wang et al., (2015), we consider elliptically distributed random
vectors $X_{i}$ with

$X_{i}=\mu+\varepsilon_{i},\quad\varepsilon_{i}=\Gamma R_{i}U_{i},$ (11)

where $\Gamma\in\mathbb{R}^{p\times p}$, $U_{i}$ is uniformly distributed on
the unit sphere in $\mathbb{R}^{p}$ and $R_{i}\geq 0$ is some scale random
variable independent with $U_{i}$. Denote $\Omega=\Gamma\Gamma^{T}$, then the
covariance matrix $\Sigma=p^{-1}D\Omega$ with
$D\overset{\Delta}{=}\mathbb{E}[R_{i}^{2}]$. Denote $W_{i}=\Gamma
U_{i}=(w_{i,1},\ldots,w_{i,p})^{T}$ and we have $X_{i}=R_{i}W_{i}$ so
$\mathbb{E}[W_{i}]=\mathbb{E}[X_{i}]=\bm{0}$ under the null .

Consider the event
$A_{i}=\left\\{\|W_{i}\|^{2}\geq\frac{{\mbox{tr}}(\Omega)}{2p}\right\\}$. From
Lemma 3 in Wang et al., (2015), we have

$P(A_{i})\geq
1-c_{1}\exp\left\\{\frac{{\mbox{tr}}^{2}(\Omega)}{-128p\lambda_{\max}^{2}(\Omega)}\right\\},$

with $c_{1}=2\exp{(\pi/2)}$ being a constant.

We make the following assumption similar to Assumption (C2) in Wang et al.,
(2015), so that we may apply the concentration inequality developed by (El
Karoui,, 2009).

######  Assumption 5.

Assume the random vectors $X_{i}$ follow elliptical distribution as (11), and

$p^{2q-2}\exp\left\\{\frac{{\mbox{tr}}^{2}(\Omega)}{-128p\lambda_{\max}^{2}(\Omega)}\right\\}=O(1).$
(12)

The assumption is mildly stronger than Wang et al., (2015) and can be verified
similar to the argument therein, since we expect the exponential term to decay
to 0 at a fast rate. To be more precise, let
$\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{p}$ denote the eigenvalues
of $\Sigma$. Assume there are $k_{1}$ eigenvalues decaying to 0 and $k_{2}$
ones diverging to $\infty$ at rate $p^{a}$ for some $a>0$. The remaining
$(p-k_{1}-k_{2})$ eigenvalues are assumed to be bounded below by some $b>0$.
We assume $k_{1}$ and $k_{2}$ are bounded and recall that we consider high-
dimensional setting where $p\rightarrow\infty$. We have

$\frac{{\mbox{tr}}(\Sigma)}{\sqrt{p}\lambda_{\max}(\Sigma)}\geq\frac{b(p-k_{1}-k_{2})}{\sqrt{p}\lambda_{p}}.$

Therefore, the exponential term decays to 0 faster than $p^{2-2q}$ as long as
$a<1/2$. The assumptions can also be satisfied with extra restrictions even if
$k_{1}$ and $k_{2}$ also diverge to $\infty$. The second statement essentially
assumes that $R_{i}$ has bounded fourth moment after proper standardization.

To apply the martingale CLT (Theorem 35.12 in Billingsley (2008)), we need to
verify the following two conditions.
$\displaystyle(i)\quad\forall\varepsilon>0,\sum_{i=1}^{n}\mathbb{E}\left[{\xi}_{n,i}^{2}\textbf{1}\left\\{\left|{\xi}_{n,i}\right|>\varepsilon\right\\}\Big{|}\mathcal{F}_{i-1}\right]\stackrel{{\scriptstyle
p}}{{\rightarrow}}0$.
$\displaystyle(ii)\quad
V_{n}=\sum_{i=1}^{n}\mathbb{E}\left[{\xi}_{n,i}^{2}|\mathcal{F}_{i-1}\right]\stackrel{{\scriptstyle
p}}{{\rightarrow}}\alpha_{1}^{2}(qr)!+\alpha_{2}^{2}(Qr)!$.

The key result required for (i) (ii) is equation (14) or Lemma 7.2 (i), i.e.,

$\sum_{l_{1},\ldots,l_{4}\in\mathcal{L}}\mathbb{E}\left[\prod_{u=1}^{4}h_{l_{u}}(X_{i_{1}^{(u)}})\cdots
h_{l_{u}}(X_{i_{q}^{(u)}})\right]=\sum_{l_{1},\ldots,l_{4}\in\mathcal{L}}\mathbb{E}\left[\prod_{u=1}^{4}H_{l_{u}}(X_{i_{1}^{(u)}},\cdots,X_{i_{q}^{(u)}})\right]\leq\tilde{\Sigma}_{1}^{2}(q).$
(13)

Consider the event
$A_{q}=\left\\{\|W_{i}\|^{2}\geq\frac{{\mbox{tr}}(\Omega)}{2p},\,i=1,\ldots,q.\right\\}$.
From Lemma 3 in Wang et al., (2015), we have

$P(A_{q})\geq
1-qc_{1}\exp\left\\{\frac{{\mbox{tr}}^{2}(\Omega)}{-128p\lambda_{\max}^{2}(\Omega)}\right\\},$

with $c_{1}=2\exp{(\pi/2)}$ being a constant.

Note that we have

$\displaystyle\sum_{l_{1},\ldots,l_{4}\in\mathcal{L}}\mathbb{E}\left[\prod_{u=1}^{4}H_{l_{u}}(X_{i_{1}^{(u)}},\cdots,X_{i_{q}^{(u)}})\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}H_{l}(X_{1},\cdots,X_{q})\right)^{4}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\frac{\sum_{l\in\mathcal{L}}w_{1,l}\cdots
w_{q,l}}{\|W_{1}\|\cdots\|W_{q}\|}\right)^{4}(1_{A_{q}}+1_{A_{q}^{c}})\right]$
$\displaystyle\leq$
$\displaystyle({\mbox{tr}}(\Omega)/2p)^{-2q}\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}w_{1,l}\cdots
w_{q,l}\right)^{4}\right]+P(A_{q}^{c})\quad(q\geq 2).$ $\displaystyle\leq$
$\displaystyle({\mbox{tr}}(\Omega)/2p)^{-2q}(\mathbb{E}[R_{1}^{4}])^{-q}\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}x_{1,l}\cdots
x_{q,l}\right)^{4}\right]+P(A_{q}^{c})\quad(x_{i,l}=R_{i}w_{i,l}).$
$\displaystyle\lesssim$
$\displaystyle(D{\mbox{tr}}(\Omega)/2p)^{-2q}\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}x_{1,l}\cdots
x_{q,l}\right)^{4}\right]+P(A_{q}^{c})\quad(\mathbb{E}[R_{i}^{4}]\geq\mathbb{E}^{2}[R_{i}^{2}]=D^{2})$
$\displaystyle\lesssim$
$\displaystyle{\mbox{tr}}^{-2q}(\Sigma)\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}x_{1,l}\cdots
x_{q,l}\right)^{4}\right]+P(A_{q}^{c})\quad(\Sigma=p^{-1}D\Omega)$

Note that we have (from the verification for mean-testing)

$\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}x_{1,l}\cdots
x_{q,l}\right)^{4}\right]\lesssim\|\Sigma\|_{q}^{2q},$

is of order $p^{2}$ at most which along with the fact that
${\mbox{tr}}(\Sigma)$ is of order at least $p$ implies

${\mbox{tr}}^{-2q}(\Sigma)\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}x_{1,l}\cdots
x_{q,l}\right)^{4}\right]\lesssim p^{2-2q}.$

As regards $\tilde{\Sigma}_{1}(q)$, we have

$\displaystyle\tilde{\Sigma}_{1}^{1/q}(q)=$
$\displaystyle\left(\sum_{l_{1},l_{2}\in\mathcal{L}}\mathbb{E}^{q}\left[\frac{x_{1,l_{1}}x_{1,l_{2}}}{\|X_{1}\|^{2}}\right]\right)^{1/q}\geq\left(\sum_{l\in\mathcal{L}}\mathbb{E}^{q}\left[\frac{x_{1,l}^{2}}{\|X_{1}\|^{2}}\right]\right)^{1/q}$
$\displaystyle=$ $\displaystyle
p^{1/q-1}\left(\sum_{l\in\mathcal{L}}\mathbb{E}^{q}\left[\frac{x_{1,l}^{2}}{\|X_{1}\|^{2}}\right]\right)^{1/q}\left(\sum_{l\in\mathcal{L}}1^{q/(q-1)}\right)^{1-1/q}$
$\displaystyle\geq$ $\displaystyle
p^{1/q-1}\sum_{l\in\mathcal{L}}\mathbb{E}\left[\frac{x_{1,l}^{2}}{\|X_{1}\|^{2}}\right]=p^{1/q-1}.$

Therefore, we conclude that $\tilde{\Sigma}_{1}(q)\geq p^{1-q}$. To conclude
(13), it remains to note that (12) implies $P(A_{q}^{c})\lesssim p^{2-2q}$.
The proof is then complete.

###  A.3 Testing the nullity of linear regression coefficients

Denote $W_{i}=(X_{i},Y_{i})$. Without loss of generality, we assume
$\mathbb{E}[X]=0$ and let
$\Sigma=(\Sigma_{l_{1},l_{2}})_{l_{1},l_{2}=1}^{p}\overset{\Delta}{=}{\mbox{var}}(X)$.
Under the null, we have

$h_{l}(W_{[2]})=(\varepsilon_{1}-\varepsilon_{2})(x_{1,l}-x_{2,l}),\quad
l=1,\ldots,p,$

where we have dropped the factor 1/2 to ease the notations. Therefore,

$h_{l}^{(1)}(W_{1})=\mathbb{E}[h_{l}(W_{[2]})|W_{1}]=\varepsilon_{1}x_{1,l},$

and

$h_{l}^{(2)}(W_{[2]})=h_{l}(W_{[2]})-h_{l}^{(1)}(W_{1})-h_{l}^{(1)}(W_{2})=-(\varepsilon_{1}x_{2,l}+\varepsilon_{2}x_{1,l}).$

Since the kernel is not degenerate, it suffices to check Assumption 2 and 3
(a,b1). However, by defining i.i.d. zero-mean random variables
$Y_{i}\overset{\Delta}{=}\varepsilon_{i}X_{i}$ such that
${\mbox{var}}(Y)=\sigma^{2}\cdot\Sigma$ with
$\sigma^{2}\overset{\Delta}{=}{\mbox{var}}(\varepsilon_{1})$, we can see that
$h_{l}^{(1)}(W_{i})=y_{i,l}$. Therefore, Assumption 3 (a) and (b1) are
satisfied if Assumption 1 holds for i.i.d. random vectors
$\varepsilon_{i}X_{i}$.

Next we check Assumption 2, i.e.
$\tilde{\Sigma}_{2}(q)=o(n^{q}\tilde{\Sigma}_{1}(q))$, or equivalently,
$\Sigma_{2}(q)=o(n^{q}\Sigma_{1}(q))$. Note that

$\displaystyle\sigma_{1}(l_{1},l_{2})=$
$\displaystyle\mathbb{E}[\varepsilon_{1}x_{1,l_{1}}\varepsilon_{1}x_{1,l_{2}}]=\sigma^{2}\Sigma_{l_{1},l_{2}},$
$\displaystyle\sigma_{2}(l_{1},l_{2})=$
$\displaystyle\mathbb{E}[(\varepsilon_{1}x_{2,l_{1}}+\varepsilon_{2}x_{1,l_{1}})(\varepsilon_{1}x_{2,l_{2}}+\varepsilon_{2}x_{1,l_{2}})]=2\sigma^{2}\Sigma_{l_{1},l_{2}}=2\sigma_{1}(l_{1},l_{2}).$

Therefore, we have $\Sigma_{2}(q)=2^{q}\Sigma_{1}(q)$ and hence Assumption 2
holds.

###  A.4 Component-wise independence testing with Kendall’s $\tau$

We first verify Assumption 2 by showing $\Sigma_{2}(q)=o(n^{q}\Sigma_{1}(q))$.
Recall $\mathcal{L}=\\{l=(d,d^{\prime}),1\leq d<d^{\prime}\leq p\\}$ in this
example, and we denote $L=|\mathcal{L}|=p(p-1)/2$. For $l=(d,d^{\prime})$, as

$h_{l}(X_{[2]})={\mbox{sgn}}(x_{1,d}-x_{2,d}){\mbox{sgn}}(x_{1,d}-x_{2,d^{\prime}}),$

we have under the null with component-wise independence,

$\displaystyle h_{l}^{(1)}(X_{1})=$
$\displaystyle\mathbb{E}[h_{l}(X_{[2]})|X_{1}]=(2F_{d}(x_{1,d})-1)(2F_{d^{\prime}}(x_{1,d^{\prime}})-1),$
$\displaystyle h_{l}^{(2)}(X_{[2]})=$ $\displaystyle
h_{l}(X_{[2]})-h_{l}^{(1)}(X_{1})-h_{l}^{(1)}(X_{2}),$

where we have used $F_{d}$ to denote the cdf of $x_{1,d}$. We assume $X_{i}$
has continuous distributions. Therefore,
$U_{d}\overset{\Delta}{=}F_{d}(x_{1,d})\sim Unif(0,1)$, and they are
independent under the null. We have

$\displaystyle\sigma_{1}(l_{1},l_{2})=$
$\displaystyle\mathbb{E}[h_{l_{1}}^{(1)}(X_{1})h_{l_{2}}^{(1)}(X_{1})]=\mathbb{E}[(2U_{d_{1}}-1)(2U_{d_{1}^{\prime}}-1)(2U_{d_{2}}-1)(2U_{d_{2}^{\prime}}-1)]$
$\displaystyle=$ $\displaystyle
I(l_{1}=l_{2})\cdot\mathbb{E}[(2U_{d_{1}}-1)^{2}]\mathbb{E}[(2U_{d_{1}^{\prime}}-1)^{2}]=\frac{1}{9}\cdot
I(l_{1}=l_{2}),$ $\displaystyle\sigma_{2}(l_{1},l_{2})=$
$\displaystyle\mathbb{E}[h_{l_{1}}(X_{[2]})h_{l_{1}}(X_{[2]})]-2\mathbb{E}[h_{l_{1}}^{(1)}(X_{1})h_{l_{2}}^{(1)}(X_{1})]$
$\displaystyle=$ $\displaystyle
I(l_{1}=l_{2})-\frac{2}{9}I(l_{1}=l_{2})=\frac{7}{9}I(l_{1}=l_{2}).$

Therefore, we have $\Sigma_{2}(q)=7^{q}\Sigma_{1}(q)=(7/9)^{q}L$ and hence
Assumption 2 holds for $h_{l}^{(1)}$.

Since the kernel is not degenerate, it remains to check Assumption 3 (a) and
(b1).

For (a), we have

$\displaystyle\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}[\sigma_{1}(l_{1},l_{2})\sigma_{1}(l_{3},l_{4})\sigma_{1}(l_{1},l_{4})\sigma_{1}(l_{2},l_{3})]^{q/2}=\left(\frac{7}{9}\right)^{2q}L.$

It is indeed $o(\Sigma_{2}^{2}(q))$ as $p\rightarrow\infty$ and as
$\Sigma_{2}^{2}(q)=(7/9)^{2q}L^{2}$.

To simplify notations, we denote $h_{l_{h}}^{(1)}(X_{1})$ by $Z_{l_{h}}$. For
(b1), we have

$\displaystyle{\mbox{cum}}(Z_{l_{1}},\ldots,Z_{l_{4}})=\mathbb{E}[Z_{l_{1}}Z_{l_{2}}Z_{l_{3}}Z_{l_{4}}]-\mathbb{E}[Z_{l_{1}}Z_{l_{2}}]\mathbb{E}[Z_{l_{3}}Z_{l_{4}}]-\mathbb{E}[Z_{l_{1}}Z_{l_{3}}]\mathbb{E}[Z_{l_{2}}Z_{l_{4}}]-\mathbb{E}[Z_{l_{1}}Z_{l_{4}}]\mathbb{E}[Z_{l_{2}}Z_{l_{3}}].$

It is straightforward to see that each term in RHS is bounded by a constant.
Moreover, if there is at least one index $l_{h}$ such that $d_{h}$ or
$d_{h}^{\prime}$ is not equal to any other, then RHS is zero since $U_{d}$’s
are independent. Therefore, for a term to be non-zero, we must have each
$d_{h}$ and $d_{h}^{\prime}$ appear at least twice in
$\\{l_{1},l_{2},l_{3},l_{4}\\}=\\{d_{1},d_{1}^{\prime},\ldots,d_{4},d_{4}^{\prime}\\}$,
which implies that the summation
$\sum_{l_{1},\ldots,l_{4}\in\mathcal{L}}=\sum_{1\leq d_{1}<d_{1}^{\prime}\leq
p,\ldots,1\leq d_{4}<d_{4}^{\prime}\leq p}$ contains at most $O(p^{4})$ terms.
We conclude that

$\displaystyle\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}{\mbox{cum}}({h_{l_{1}}^{(1)}(X_{1}),\ldots,h_{l_{4}}^{(1)}(X_{1})})=O(p^{4})=O(L^{2})=O(\Sigma_{2}^{2}(q)),$

and (b1) holds.

##  Appendix B Technical Proofs of the Theorems

###  B.1 Proof of Lemma 3.2

For the ease of notation, we define the unnomarlized version of $U_{n,q}$ and
$U_{n,\bm{\alpha}}$ with

$D_{n,q}=\frac{n!}{(n-qr)!}U_{n,q};\quad
D_{n,\bm{\alpha}}=\frac{n!}{(n-c)!}U_{n,\bm{\alpha}},$

where $c=\sum_{t}t\alpha_{t}$ is the order of $h_{l}^{\bm{\alpha}}$.

For $I=(i_{1},i_{2},\ldots,i_{qr})\in P_{qr}(n)$, denote
$I_{c}=(i_{(c-1)r+1},\ldots,i_{cr})\in P_{r}(n)$ for $c=1,\ldots,q$, so we may
also write $I=(I_{1},I_{2},\ldots,I_{q})$. We have

$\displaystyle D_{n,q}=$ $\displaystyle\sum_{l\in\mathcal{L}}\sum_{I\in
P_{qr}(n)}(\otimes^{q}h_{l})(X_{I})$ $\displaystyle=$
$\displaystyle\sum_{l\in\mathcal{L}}\sum_{I\in
P_{qr}(n)}\prod_{c=1}^{q}h_{l}(X_{I_{c}})$ $\displaystyle=$
$\displaystyle\sum_{l\in\mathcal{L}}\sum_{I\in
P_{qr}(n)}\prod_{c=1}^{q}\left(\sum_{t=1}^{r}\sum_{J\subseteq
I_{c}:|J|=t}h_{l}^{(t)}(X_{J})\right)$ $\displaystyle=$
$\displaystyle\sum_{l\in\mathcal{L}}\sum_{c=q}^{qr}\frac{(n-c)!}{(n-qr)!}\sum_{\bm{\alpha}:\sum_{t}t\alpha_{t}=c}C_{\bm{\alpha}}\sum_{I\in
P_{c}(n)}h_{l}^{\bm{\alpha}}(X_{I})$ $\displaystyle=$
$\displaystyle\sum_{c=q}^{qr}\frac{(n-c)!}{(n-qr)!}\sum_{\bm{\alpha}:\sum_{t}t\alpha_{t}=c}C_{\bm{\alpha}}D_{n,\bm{\alpha}},$

for some constants $C_{\bm{\alpha}}$, where we have used the fact that

$h_{l}(X_{I})=\sum_{t=1}^{r}\sum_{J\subseteq I:|J|=t}h_{l}^{(t)}(X_{J}),$ (14)

and combine the terms with the same kernel $h_{l}^{\bm{\alpha}}$ (i.e. with
the same $\bm{\alpha}$) into their corresponding U-statistic. Therefore we
conclude that

$U_{n,q}=\sum_{c=q}^{qr}\sum_{\bm{\alpha}:\sum_{t}t\alpha_{t}=c}C_{\bm{\alpha}}U_{n,\bm{\alpha}}.$

Since the kernel $\tilde{h}_{l,\bm{\alpha}}$ with order $\sum_{t}t\alpha_{t}$
less than $qs$ equals 0, we may also start the index in the summation from
$c=qs$ instead of $c=q$.

Note that $C_{\bm{\alpha}}$ can be calculated explicitly in general. We only
derive it for $\bm{\alpha}=e_{t}(r)$ required for the leading term. In (14),
the decomposition of $h_{l}$ contains $\binom{r}{t}$ terms in $h_{l}^{(t)}$.
Therefore, the total number of terms in $\otimes^{q}h_{l}^{(t)}$ equals
$P^{n}_{n-qr}\binom{r}{t}^{q}$. Therefore, for $\bm{\alpha}=e_{t}(r)$, we have
$P^{n}_{n-qr}\binom{r}{t}^{q}=\frac{(n-c)!}{(n-qr)!}P^{n}_{c}C_{\bm{\alpha}}$,
by matching the number of terms $\otimes^{q}h_{l}^{(t)}$, which implies that
$C_{\bm{\alpha}}=\binom{r}{t}^{q}$.

###  B.2 Proof of Lemma 3.3

We analyze the asymptotic variance of $U_{n,\bm{\alpha}}$.

For $\bm{\alpha}=(\alpha_{1},\ldots,\alpha_{r})$, we define

$\tilde{\sigma}_{\bm{\alpha}}(l_{1},l_{2})=\mathbb{E}[\tilde{h}_{l_{1}}^{\bm{\alpha}}(X_{I})\tilde{h}_{l_{2}}^{\bm{\alpha}}(X_{I})],$

and
$\tilde{\Sigma}_{\bm{\alpha}}=\sum_{l_{1},l_{2}}\tilde{\sigma}_{\bm{\alpha}}(l_{1},l_{2})$.
Note that by Cauchy–Schwarz inequality, we have

$\displaystyle\tilde{\Sigma}_{\bm{\alpha}}=\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}\tilde{h}_{l}^{\bm{\alpha}}(X_{I})\right)^{2}\right]\leq\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}h_{l}^{\bm{\alpha}}(X_{I})\right)^{2}\right]=\sum_{l_{1},l_{2}\in\mathcal{L}}\prod_{t=s}^{r}\sigma_{t}^{\alpha_{t}}(l_{1},l_{2}),$

as $\sum_{l\in\mathcal{L}}\tilde{h}_{l}^{\bm{\alpha}}$ is the symmetrized
kernel of $\sum_{l\in\mathcal{L}}h_{l}^{\bm{\alpha}}$. Moreover, applying
Hölder’s inequality, we have

$\sum_{l_{1},l_{2}\in\mathcal{L}}\prod_{t=s}^{r}\sigma_{t}^{\alpha_{t}}(l_{1},l_{2})\leq\prod_{t=s}^{r}\left(\sum_{l_{1},l_{2}\in\mathcal{L}}\sigma_{t}^{q}(l_{1},l_{2})\right)^{\alpha_{t}/q}=\prod_{t=s}^{r}\Sigma_{t}^{\alpha_{t}/q}(q).$

Recall that the Hoeffding decomposition can be written as

$U_{n,q}=\binom{r}{s}^{q}U_{n,q}^{(qs)}+\sum_{c=qs+1}^{qr}\sum_{\bm{\alpha}:\sum_{t}t\alpha_{t}=c}C_{\bm{\alpha}}U_{n,\bm{\alpha}},$

Note that $\tilde{h}_{l}^{\bm{\alpha}}$ is fully degenerate and orthogonal,
which implies
${\mbox{var}}(U_{n,\bm{\alpha}})=O(n^{-c}\tilde{\Sigma}_{\bm{\alpha}})$ with
$c=\sum_{t}\alpha_{t}$ and
${\mbox{var}}(U_{n,q}^{(qs)})=O(n^{-qs}\tilde{\Sigma}_{s}(q))$. Therefore, we
have for any $\bm{\alpha}$ such that $\sum_{t}t\alpha_{t}>qs$,

$\displaystyle{\mbox{var}}(U_{n,\bm{\alpha}})=O(n^{-c}\tilde{\Sigma}_{\bm{\alpha}})$
$\displaystyle=$ $\displaystyle
O(n^{-c}\Sigma_{\bm{\alpha}})=O\left(n^{-c}\prod_{t=s}^{r}\Sigma_{t}^{\alpha_{t}/q}(q)\right)\quad(\tilde{\Sigma}_{\bm{\alpha}}\leq\Sigma_{\bm{\alpha}}\text{
and H\"{o}lder})$ $\displaystyle=$ $\displaystyle
o\left(n^{-c}\prod_{t=s}^{r}n^{\alpha_{t}(t-s)}\Sigma_{s}^{\alpha_{t}/q}(q)\right)$
$\displaystyle=$ $\displaystyle
o(n^{-qs}\tilde{\Sigma}_{s}(q))=o\big{(}{\mbox{var}}(U_{n,q}^{(qs)})\big{)},$

by Assumption 2. Therefore, we have all terms but $U_{n,q}^{(qs)}$ are
negligible and complete the proof.

###  B.3 Proof of Proposition 3.4

The degeneracy of $h_{l}$ implies that $\otimes^{q}h_{l}$ is also fully
degenerate, and we have $D_{n,q}=D_{n,q}^{(qr)}$. Note that with a slight
abuse of notation, we define $D_{n,q}^{(qr)}=\binom{n}{qr}U_{n,q}^{(qr)}$
(instead of the coefficient equal to $\frac{n!}{(n-qr)!}$) in this section, so
that

$D_{n,q}^{(qr)}=\sum_{l\in\mathcal{L}}\sum_{1\leq i_{1}<\cdots<i_{qr}\leq
n}H_{l,q}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr}}).$

. By Wold’s device, it suffices to show that for any $q\not=Q\in
2\mathbb{Z}_{+}$ and $\alpha_{1},\alpha_{2}\in\mathbb{R}$,

$\alpha_{1}n^{-qr/2}\tilde{\Sigma}^{-1/2}_{r}(q)D_{n,q}^{(qr)}+\alpha_{2}n^{-Qr/2}\tilde{\Sigma}^{-1/2}_{r}(Q)D_{n,Q}^{(Qr)}\stackrel{{\scriptstyle\cal
D}}{{\longrightarrow}}N(0,\alpha_{1}^{2}(qr)!+\alpha_{2}^{2}(Qr)!).$

The degeneracy of kernel implies that LHS is a martingale, whose martingale
difference is

$\displaystyle\xi_{n,i}=$
$\displaystyle\alpha_{1}(qr)!n^{-qr/2}\tilde{\Sigma}^{-1/2}_{r}(q)\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{qr-1}<i}H_{l,q}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X_{i})$
$\displaystyle+\alpha_{2}(Qr)!n^{-Qr/2}\tilde{\Sigma}^{-1/2}_{r}(Q)\sum_{l\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{Qr-1}<i}H_{l,Q}^{(r)}(X_{i_{1}},\ldots,X_{i_{Qr-1}},X_{i})$
$\displaystyle\overset{\Delta}{=}$
$\displaystyle\alpha_{1}(qr)!\xi_{n,i}^{(1)}+\alpha_{2}(Qr)!\xi_{n,i}^{(2)}.$

Note that $(qr)!$ and $(Qr)!$ in the first line appear due to the permutation
across $qr$ and $Qr$ indices. To apply the martingale CLT (Theorem 35.12 in
Billingsley (2008)), we need to verify the following two conditions.
$\displaystyle(i)\quad\forall\varepsilon>0,\sum_{i=1}^{n}\mathbb{E}\left[{\xi}_{n,i}^{2}\textbf{1}\left\\{\left|{\xi}_{n,i}\right|>\varepsilon\right\\}\Big{|}\mathcal{F}_{i-1}\right]\stackrel{{\scriptstyle
p}}{{\rightarrow}}0$.
$\displaystyle(ii)\quad
V_{n}=\sum_{i=1}^{n}\mathbb{E}\left[{\xi}_{n,i}^{2}|\mathcal{F}_{i-1}\right]\stackrel{{\scriptstyle
p}}{{\rightarrow}}\alpha_{1}^{2}(qr)!+\alpha_{2}^{2}(Qr)!$.

To prove (i), it suffices to show that

$\sum_{i=1}^{n}\mathbb{E}[\xi_{n,i}^{4}]\lesssim\sum_{i=1}^{n}\mathbb{E}[(\xi_{n,i}^{(1)})^{4}+(\xi_{n,i}^{(2)})^{4}]\rightarrow
0.$

Note that

$\displaystyle\sum_{i=1}^{n}\mathbb{E}[(\xi_{n,i}^{(1)})^{4}]=n^{-2qr}\tilde{\Sigma}_{r}^{-2}(q)\sum_{i=1}^{n}\mathbb{E}\left[\left(\sum_{1\leq
i_{1}<\cdots<i_{qr-1}<i}\sum_{l\in\mathcal{L}}H_{l,q}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X_{i})\right)^{4}\right]$
$\displaystyle\lesssim$
$\displaystyle\sum_{i=1}^{n}n^{-2qr}\tilde{\Sigma}_{r}^{-2}(q)n^{2(qr-1)}\mathbb{E}\left[\prod_{u=1}^{4}H_{l_{u},q}^{(r)}(X_{i_{1}^{(u)}},\ldots,X_{i_{qr-1}^{(u)}},X_{i})\right]$
$\displaystyle\lesssim$ $\displaystyle n^{-1}\rightarrow 0,$

where the first inequality uses the fact that all subscripts have to appear at
least twice to have nonzero expectation and the second inequality is due to
Lemma B.1. Similar argument leads to
$\sum_{i=1}^{n}\mathbb{E}[(\xi_{n,i}^{(2)})^{4}]\rightarrow 0.$

To prove (ii), we decompose the summation into two parts,

$\displaystyle\sum_{i=qr}^{n}\mathbb{E}[(\xi_{n,i}^{(1)})^{2}|\mathcal{F}_{i-1}]$
$\displaystyle=$ $\displaystyle
n^{-qr}\widetilde{\Sigma}_{r}^{-1}(q)\sum_{l_{1},l_{2}\in\mathcal{L}}\sum_{i=qr}^{n}\sum_{i_{t}^{(1)}<i,i_{t}^{(2)}<i}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr-1}^{(1)}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}^{(2)}},\ldots,X_{i_{qr-1}^{(2)}},X_{i})\mid\mathcal{F}_{i-1}\right]$
$\displaystyle=$ $\displaystyle
n^{-qr}\widetilde{\Sigma}_{r}^{-1}(q)\sum_{l_{1},l_{2}\in\mathcal{L}}\sum_{i=qr}^{n}\Bigg{(}\sum_{i_{t}^{(1)}<i,i_{t}^{(2)}<i}^{(1)}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr-1}^{(1)}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}^{(2)}},\ldots,X_{i_{qr-1}^{(2)}},X^{\prime})\mid\mathcal{F}_{i-1}\right]$
$\displaystyle+\sum_{i_{t}^{(1)}<i,i_{t}^{(2)}<i}^{(2)}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr-1}^{(1)}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}^{(2)}},\ldots,X_{i_{qr-1}^{(2)}},X^{\prime})\mid\mathcal{F}_{i-1}\right]\Bigg{)}$
$\displaystyle\overset{\Delta}{=}$ $\displaystyle V_{n}^{(1)}+V_{n}^{(2)},$

where $\sum^{(1)}$ to be over the indices where $i_{t}^{(1)}$ and
$i_{t}^{(2)}$ can be all paired up to a permutation, for $t=1,2,\ldots,qr-1$,
and $\sum^{(2)}$ includes all others, and we have replace $X_{i}$ by a dummy
variable $X^{\prime}$ since we are taking its expectation (conditioning on
others). Note that we have abbreviate
$i_{1}^{(u)}<i_{2}^{(u)}<\cdots<i_{qr-1}^{(u)}<i$ as $i_{t}^{(u)}<i$ in the
above expression of summation for $u=1,2$, to ease the notation.

We first show $V_{n}^{(1)}\stackrel{{\scriptstyle\cal
P}}{{\longrightarrow}}[(qr)!]^{-1}$. Since

$\displaystyle\mathbb{E}[V_{n}^{(1)}]=$ $\displaystyle
n^{-qr}\widetilde{\Sigma}_{r}^{-1}(q)\sum_{l_{1},l_{2}\in\mathcal{L}}\sum_{1\leq
i_{1}<\cdots<i_{qr}\leq
n}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})\right]$
$\displaystyle\rightarrow$ $\displaystyle[(qr)!]^{-1},$

it suffices to show

$\mathbb{E}\left[\left(V_{n}^{(1)}\right)^{2}\right]\rightarrow[(qr)!]^{-2},$

which implies convergence in $L^{2}$ and hence the convergence in probability.
In fact, we have

$\displaystyle\mathbb{E}[(V_{n}^{(1)})^{2}]=$ $\displaystyle
n^{-2qr}\widetilde{\Sigma}_{r}^{-2}(q)\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\sum_{i,j=qr}^{n}\sum_{i_{t}<i}\sum_{j_{t}<j}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})\right.$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\left.H_{q,l_{3}}^{(r)}(X_{j_{1}},\ldots,X_{j_{qr-1}},X^{\prime\prime})H_{q,l_{4}}^{(r)}(X_{j_{1}},\ldots,X_{j_{qr-1}},X^{\prime\prime})\right].$

We decompose the summation into $\sum^{(a)}$ and $\sum^{(b)}$, where
$\sum^{(a)}$ includes the term such that $\\{i_{t}\\}_{t=1}^{qr-1}$ and
$\\{j_{t}\\}_{t=1}^{qr-1}$ have no intersection, and $\sum^{(b)}$ includes all
others. Note that

$\displaystyle
n^{-2qr}\tilde{\Sigma}_{r}^{-2}(q)\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\sum_{i,j=qr}^{n}\sum_{i_{t}<i,j_{t}<j}^{(a)}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})\right.$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}\left.H_{q,l_{3}}^{(r)}(X_{j_{1}},\ldots,X_{j_{qr-1}},X^{\prime\prime})H_{q,l_{4}}^{(r)}(X_{j_{1}},\ldots,X_{j_{qr-1}},X^{\prime\prime})\right]$
$\displaystyle\asymp$ $\displaystyle
n^{-2qr}\tilde{\Sigma}_{r}^{-2}(q)\sum_{i,j=qr}^{n}\binom{i}{qr-1}\binom{j}{qr-1}\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\mathbb{E}\big{[}H_{q,l_{1}}^{(r)}(X_{[qr]})H_{q,l_{2}}^{(r)}(X_{[qr]})\big{]}\mathbb{E}\big{[}H_{q,l_{3}}^{(r)}(X_{[qr]})H_{q,l_{4}}^{(r)}(X_{[qr]})\big{]}$
$\displaystyle\asymp$ $\displaystyle
n^{-2qr}\tilde{\Sigma}_{r}^{-2}(q)[(qr)!]^{-2}n^{2qr}\tilde{\Sigma}_{r}^{2}(q)=[(qr)!]^{-2}.$

For $\sum^{(b)}$, we lose at least one degree of freedom due to the matching
indices between $\\{i_{t}\\}$ and $\\{j_{t}\\}$. Therefore, by Lemma B.1 (i),
we have

$\displaystyle
n^{-2qr}\widetilde{\Sigma}_{r}^{-2}(q)\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\sum_{i,j=qr}^{n}\sum_{i_{t}<i,j_{t}<j}^{(b)}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr-1}},X^{\prime})\right.$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\left.H_{q,l_{3}}^{(r)}(X_{j_{1}},\ldots,X_{j_{qr-1}},X^{\prime\prime})H_{q,l_{4}}^{(r)}(X_{j_{1}},\ldots,X_{j_{qr-1}},X^{\prime\prime})\right]$
$\displaystyle=$ $\displaystyle O(\frac{1}{n})\tilde{\Sigma}_{r}^{-2}(q)\cdot
O(\tilde{\Sigma}_{r}^{2}(q))\rightarrow 0..$

Therefore, we conclude $V_{n}^{(1)}$ converges to $[(qr)!]^{-2}$ in $L^{2}$.

For $V_{n}^{(2)}$, it suffices to show
$\mathbb{E}[(V_{n}^{(2)})^{2}]\rightarrow 0$ to conclude its negligibly. Note
that the summand in $V_{n}^{(2)}$ is nonzero only if any index in
$\\{i_{t}^{(u)},j_{t}^{(u)}\\}$ appears at least twice. The summation over
terms that has some index to appear more than twice is $O(1/n)$ due to the
additional loss of order in $n$. Therefore, we focus on terms whose indices
all appear exacting twice, and the number of summands also has order
$O(n^{2qr})$, similar to $\sum^{(a)}$ in the analysis of $V_{n}^{(1)}$. By
Lemma B.1, we have

$V_{n}^{(2)}=n^{-2qr}\tilde{\Sigma}_{r}^{-2}(q)\cdot O(n^{2qr})\cdot
o(\tilde{\Sigma}_{r}^{2}(q))\rightarrow 0.$

which implies $V_{n}^{(2)}$ converges to 0 in $L^{2}$. Therefore, we conclude
$\sum_{i=qr}^{n}\mathbb{E}[(\xi_{n,i}^{(1)})^{2}|\mathcal{F}_{i-1}]\stackrel{{\scriptstyle\cal
P}}{{\longrightarrow}}[(qr)!]^{-2}$. Similarly, we have
$\sum_{i=Qr}^{n}\mathbb{E}[(\xi_{n,i}^{(2)})^{2}|\mathcal{F}_{i-1}]\stackrel{{\scriptstyle\cal
P}}{{\longrightarrow}}[(Qr)!]^{-2}$, and
$\sum_{i=qr}^{n}\mathbb{E}[\xi_{n,i}^{(1)}\xi_{n,i}^{(2)}|\mathcal{F}_{i-1}]\stackrel{{\scriptstyle\cal
P}}{{\longrightarrow}}0$. By putting all pieces together, we complete the
proof.

######  Lemma B.1.

Given four groups of indices that are distinct within group.
$\\{i_{1}^{(u)},\ldots,i_{qr}^{(u)}\\},\\{j_{1}^{(u)},\ldots,j_{qr}^{(u)}\\}$
for $u=1,2$.
(i) Under Assumption 3 (b1), we have

$\displaystyle\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr}^{(1)}})H_{q,l_{2}}^{(r)}(X_{i_{1}^{(2)}},\ldots,X_{i_{qr}^{(2)}})\right.$
$\displaystyle~{}~{}~{}~{}\left.H_{q,l_{3}}^{(r)}(X_{j_{1}^{(1)}},\ldots,X_{j_{qr}^{(1)}})H_{q,l_{4}}^{(r)}(X_{j_{1}^{(2)}},\ldots,X_{j_{qr}^{(2)}})\right]$
$\displaystyle=$ $\displaystyle O(\tilde{\Sigma}_{r}^{2}(q)).$

(ii) Moreover, suppose $\\{i_{1}^{(1)},\ldots,i_{qr-1}^{(1)}\\}$ are not
identical to $\\{i_{1}^{(2)},\ldots,i_{qr-1}^{(2)}\\}$, and each element in
$\\{i_{t}^{(1)},i_{t}^{(2)},j_{t}^{(1)},j_{t}^{(2)}\\}_{t=1}^{qr-1}$ appears
exactly twice. Under Assumption 3 (a) and (b2), we have

$\displaystyle\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr-1}^{(1)}},X^{\prime})H_{q,l_{2}}^{(r)}(X_{i_{1}^{(2)}},\ldots,X_{i_{qr-1}^{(2)}},X^{\prime})\right.$
$\displaystyle~{}~{}~{}~{}\left.H_{q,l_{3}}^{(r)}(X_{j_{1}^{(1)}},\ldots,X_{j_{qr-1}^{(1)}},X^{\prime\prime})H_{q,l_{4}}^{(r)}(X_{j_{1}^{(2)}},\ldots,X_{j_{qr-1}^{(2)}},X^{\prime\prime})\right]$
$\displaystyle=$ $\displaystyle o(\tilde{\Sigma}_{r}^{2}(q)).$

###### Proof of Lemma B.1.

For (i), by AM-GM inequality, since $H_{q,l}^{(r)}$ is the symmetrized kernel
of $\otimes^{q}h_{l}^{(r)}$, we have

$\displaystyle\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr}^{(1)}})H_{q,l_{2}}^{(r)}(X_{i_{1}^{(2)}},\ldots,X_{i_{qr}^{(2)}})\right.$
$\displaystyle~{}~{}~{}~{}\left.H_{q,l_{3}}^{(r)}(X_{j_{1}^{(1)}},\ldots,X_{j_{qr}^{(1)}})H_{q,l_{4}}^{(r)}(X_{j_{1}^{(2)}},\ldots,X_{j_{qr}^{(2)}})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}H_{q,l}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr}^{(1)}})\right)\left(\sum_{l\in\mathcal{L}}H_{q,l}^{(r)}(X_{i_{1}^{(2)}},\ldots,X_{i_{qr}^{(2)}})\right)\right.$
$\displaystyle~{}~{}~{}~{}\left.\left(\sum_{l\in\mathcal{L}}H_{q,l}^{(r)}(X_{j_{1}^{(1)}},\ldots,X_{j_{qr}^{(1)}})\right)\left(\sum_{l\in\mathcal{L}}H_{q,l}^{(r)}(X_{j_{1}^{(2)}},\ldots,X_{j_{qr}^{(2)}})\right)\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}H_{q,l}^{(r)}(X_{i_{1}^{(1)}},\ldots,X_{i_{qr}^{(1)}})\right)^{4}\right]\quad\text{(H\"{o}lder's
inequality)}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}\otimes^{q}h_{l}^{(r)}(X_{1},\ldots,X_{qr})\right)^{4}\right]\quad\text{(AM-
GM inequality, as $H_{q,l}^{(r)}$ is an average of $\otimes^{q}h_{l}$)}$
$\displaystyle=$
$\displaystyle\sum_{l_{1},\ldots,l_{4}\in\mathcal{L}}\mathbb{E}[h_{l_{1}}(X_{1},\ldots,X_{r})\cdots
h_{l_{1}}(X_{(q-1)r+1},\ldots,X_{qr})\cdots$ $\displaystyle
h_{l_{4}}(X_{1},\ldots,X_{r})\cdots h_{l_{4}}(X_{(q-1)r+1},\ldots,X_{qr})]$

The remaining proof of (i) is identical to Lemma 6.1 in Zhang et al., (2021).
We include a self-contained proof here. We show a slightly stronger result
that matches Zhang et al., (2021) as follows.

Claim: Under Assumption 3 (b1), for any
$i_{1}^{(u)},i_{2}^{(u)},...,i_{qr}^{(u)}$ that are all distinct with
$u=1,2,3,4$, we have

$\displaystyle\Big{|}\sum_{l_{1},\ldots,l_{4}\in\mathcal{L}}\mathbb{E}[$
$\displaystyle h_{l_{1}}(X_{i_{1}^{(1)}},\ldots,X_{i_{r}^{(1)}})\cdots
h_{l_{1}}(X_{i_{(q-1)r+1}^{(1)}},\ldots,X_{i_{qr}^{(1)}})\cdots$ (15)
$\displaystyle h_{l_{4}}(X_{i_{1}^{(4)}},\ldots,X_{i_{r}^{(4)}})\cdots
h_{l_{4}}(X_{i_{(q-1)r+1}^{(4)}},\ldots,X_{i_{qr}^{(4)}})]\Big{|}\lesssim\tilde{\Sigma}_{r}^{2}(q).$

Proof of Claim: Define
$I_{t}^{(u)}=(i_{(r-1)t+1}^{(u)},\ldots,i_{(rt)}^{(u)})$. By Hölder’s
Inequality, we have

$\displaystyle\left|\sum_{l_{1},...,l_{4}\in\mathcal{L}}\mathbb{E}[h_{l_{1}}(X_{I_{1}^{(1)}})\cdots
h_{l_{1}}(X_{I_{q}^{(1)}}))\cdots h_{l_{4}}(X_{I_{1}^{(4)}})\cdots
h_{l_{4}}(X_{I_{q}^{(4)}})]\right|$ $\displaystyle=$
$\displaystyle\left|\mathbb{E}\left[\prod_{u=1}^{4}\sum_{l_{u}\in\mathcal{L}}[h_{l_{u}}(X_{I_{1}^{(u)}})\cdots
h_{l_{u}}(X_{I_{q}^{(u)}})\right]\right|$ $\displaystyle\leq$
$\displaystyle\prod_{u=1}^{4}\left\\{\mathbb{E}\left[\left(\sum_{l_{u}\in\mathcal{L}}[h_{l_{u}}(X_{I_{1}^{(u)}})\cdots
h_{l_{u}}(X_{I_{q}^{(u)}})\right)^{4}\right]\right\\}^{1/4}.$

Note that

$\displaystyle\mathbb{E}\left[\left(\sum_{l\in\mathcal{L}}[h_{l}(X_{1},\ldots,X_{r})\cdots
h_{l}(X_{(q-1)r+1},X_{qr})\right)^{4}\right]$ $\displaystyle=$
$\displaystyle\sum_{l_{1},...,l_{4}\in\mathcal{L}}\mathbb{E}^{q}[h_{l_{1}}(X_{1},\ldots,X_{r})\cdots
h_{l_{4}}(X_{1},\ldots,X_{r})]$ $\displaystyle\lesssim$
$\displaystyle\sum_{l_{1},...,l_{4}\in\mathcal{L}}\mathbb{E}^{q}[h_{l_{1}}(X_{1},\ldots,X_{r})h_{l_{2}}(X_{1},\ldots,X_{r})]\mathbb{E}^{q}[h_{l_{3}}(X_{1},\ldots,X_{r})h_{l_{4}}(X_{1},\ldots,X_{r})]$
$\displaystyle+\sum_{l_{1},...,l_{4}\in\mathcal{L}}|{\mbox{cum}}^{q}(h_{l_{1}}(X_{1},\ldots,X_{r}),\ldots,h_{l_{4}}(X_{1},\ldots,X_{r}))|$
$\displaystyle\lesssim$
$\displaystyle\Sigma_{r}^{2}(q)\asymp\tilde{\Sigma}_{r}^{2}(q).$

where the second last line in the above inequalities is due to the CR
inequality and the definition of joint cumulants. We therefore conclude (i).

For (ii), to ease the notation, we write LHS as

$\displaystyle\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\mathbb{E}\left[H_{q,l_{1}}^{(r)}(X_{i_{1}},\ldots,X_{i_{qr}})H_{q,l_{2}}^{(r)}(X_{i_{qr+1}},\ldots,X_{i_{2qr}})\right.$
$\displaystyle~{}~{}~{}~{}\left.H_{q,l_{3}}^{(r)}(X_{i_{2qr+1}},\ldots,X_{i_{3qr}})H_{q,l_{4}}^{(r)}(X_{i_{3qr+1}},\ldots,X_{i_{4q}})\right],$

with the constraint that $i_{qr}=i_{2qr}$ and $i_{3qr}=i_{4qr}$. Since
$H_{q,l}^{(r)}$ is the average of $\otimes^{q}h_{l}^{(r)}$ over different
arguments, we may decompose the expectation in LHS as a linear combination of
finite many terms with form

$\displaystyle[\otimes^{q}h_{l_{1}}^{(r)}(X_{I_{1}})][\otimes^{q}h_{l_{2}}^{(r)}(X_{I_{2}})][\otimes^{q}h_{l_{3}}^{(r)}(X_{I_{3}})][\otimes^{q}h_{l_{4}}^{(r)}(X_{I_{4}})],$

where $I_{1},I_{2},I_{3},I_{4}$ are permutations of
$\\{i_{t}\\}_{t=1}^{qr},\\{i_{t}\\}_{t=qr+1}^{2qr},\\{i_{t}\\}_{t=2qr+1}^{3qr},\\{i_{t}\\}_{t=3qr+1}^{4qr}$,
respectively. We further write $I_{u}=(I_{u1},\ldots,I_{uq})$ where $I_{uc}$
is an index set containing $r$ elements, for $u=1,\ldots,4;\,c=1,\ldots,q$.
Since each element in $\\{I_{1},\ldots,I_{4}\\}$ appears exactly twice, we
consider the following two cases.

  * •

The index set $I_{uc}$ pairs with each other. In this case, the constraint
that $I_{1}\not=I_{2}$ and $i_{qr}=i_{2qr},i_{3qr}=i_{4qr}$ implies that there
exist $c_{1},c_{2},c_{3},c_{4}$ such that
$I_{1,c_{1}}=I_{3,c_{3}},I_{1,c_{1}}=I_{4,c_{4}}$, or
$I_{1,c_{1}}=I_{4,c_{4}},I_{2,c_{2}}=I_{3,c_{3}}$. Moreover, the assumption on
the indices implies that $I_{1q}=I_{2q}$ and $I_{3q}=I_{4q}$. Assumption 3 (a)
implies that the term is $o_{p}(\tilde{\Sigma}_{r}^{2}(q))$ by Hölder’s
inequality. The arguments are essentially the same as the proof of Lemma 6.3
in the supplemental material of Zhang et al., (2021). Therefore we only sketch
the outline of the proof here for illustration, and we refer the readers to
the supplemental material of Zhang et al., (2021) for a complete proof.

  * •

Suppose the index sets $\\{I_{uc}\\}$ are not all paired with each other. We
then decompose the expectation using the cumulants, and write it as the
summation over the products of cumulants. We use the cumulant decomposition to
write the term as many products of cumulants and expectation, with form

$\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}\prod_{k=1}^{K}{\mbox{cum}}(h_{u_{1}^{(k)}}(I_{u_{1}^{(k)},c_{1}^{(k)}}),\ldots,h_{u_{m_{k}}^{(k)}}(X_{I_{u_{m_{k}}^{(k)},c_{m_{k}}^{(k)}}})),$
(16)

where $(B_{1},B_{2},\ldots,B_{K})$ is a partition of $(I_{1},\ldots,I_{4})$
with
$B_{k}=(I_{u_{1}^{(k)},c_{1}^{(k)}},\ldots,I_{u_{m_{k}}^{(k)},c_{m_{k}}^{(k)}})$,
we have assumed that the blocks are minimal in the sense that
$B_{1},\ldots,B_{K}$ have no overlap with each other. Otherwise, we may
further decompose some blocks into the product of smaller blocks due to the
independence. Since $I_{uc}$ are not all paired, there exist at least one
block $B_{k_{0}}$ that contains $I_{uc}$ for at least three different $u$ in
{1,2,3,4}, which we denote as

${\mbox{cum}}^{q/m_{k}}(h_{l_{1}}(X_{i_{1}},\ldots,X_{i_{r}}),\ldots,h_{l_{u}}(X_{i_{(c-1)r+1}},\ldots,X_{i_{cr}}),$
(17)

with $u=3$ or 4 and $c=m_{k}$, for simplicity. Using Hölder’s inequality, we
can bound (the absolute value of) (16) by

$\prod_{k=1}^{K}\left(\sum_{l_{1},l_{2},l_{3},l_{4}\in\mathcal{L}}{\mbox{cum}}^{q/m_{k}}(h_{u_{1}^{(k)}}(I_{u_{1}^{(k)},c_{1}^{(k)}}),\ldots,h_{u_{m_{k}}^{(k)}}(X_{I_{u_{m_{k}}^{(k)},c_{m_{k}}^{(k)}}}))\right)^{m_{k}/q}.$

Each term is $O(\tilde{\Sigma}_{r}^{m_{k}/2q})$, so the product is
$O(\tilde{\Sigma}_{r}^{2})$ as $\sum_{k=1}^{K}m_{k}=4q$. However, note that
the term in RHS associated with (17), i.e.

${\mbox{cum}}^{q/c}(h_{l_{1}}(X_{i_{1}},\ldots,X_{i_{r}}),\ldots,h_{l_{u}}(X_{i_{(c-1)r+1}},\ldots,X_{i_{cr}}),$

which is $o(\tilde{\Sigma}_{r}^{c/2q}(q))$ by Assumption 3 (b2), This implies
(16) is $o_{p}(\tilde{\Sigma}_{r}^{2}(q))$ and completes the proof.

$\diamondsuit$

######  Remark.

Note that we have to make a stronger assumption (b2) in addition to (b1), due
to the structure for kernels with order $r>2$. In fact, for $r=1$, Lemma B.1
(ii) is implied by (b1), which implies the martingale CLT. However, for
general $r$, a direct extended assumption like (b1) does not imply the lemma
trivially, and we have to impose a stronger assumption (b2).

###  B.4 Proof of Theorem 3.7

To simplify the notations, we define

$U_{n,q,l}=(P^{n}_{qr})^{-1}\sum_{1\leq i_{1},i_{2},\cdots,i_{qr}\leq
n}(\otimes^{q}h_{l})(X_{1},\ldots,X_{qr}),$

so that $\displaystyle U_{n,q}=\sum_{l\in\mathcal{L}}U_{n,q,l}$, and

$U_{n,\bm{\alpha},l}=(P^{n}_{m})^{-1}\sum_{1\leq i_{1},i_{2},\cdots,i_{m}\leq
n}h_{l}^{\bm{\alpha}}(X_{1},\ldots,X_{m}),$

where $m$ is the order of $h_{l}^{\bm{\alpha}}$, i.e.,
$m=\sum_{t}t\alpha_{t}$, so that $\displaystyle
U_{n,\bm{\alpha}}=\sum_{l\in\mathcal{L}}U_{n,\bm{\alpha},l}$.

Recall $\tilde{U}_{n,q}$ is the proposed U-statistic associated with the
centered kernel $\tilde{h}_{l}$. We also define the counterpart of $U_{n,q,l}$