# Gaussian universality for approximately polynomial functions of high-
dimensional data

Kevin Han Huang  Morgane Austern  Peter Orbanz

###### Abstract

We establish an invariance principle for polynomial functions of $n$
independent high-dimensional random vectors, and also show that the obtained
rates are nearly optimal. Both the dimension of the vectors and the degree of
the polynomial are permitted to grow with $n$. Specifically, we obtain a
finite sample upper bound for the error of approximation by a polynomial of
Gaussians, measured in Kolmogorov distance, and extend it to functions that
are approximately polynomial in a mean squared error sense. We give a
corresponding lower bound that shows the invariance principle holds up to
polynomial degree $o(\log n)$. The proof is constructive and adapts an
asymmetrisation argument due to V. V. Senatov. As applications, we obtain a
higher-order delta method with possibly non-Gaussian limits, and generalise a
number of known results on high-dimensional and infinite-order U-statistics,
and on fluctuations of subgraph counts.

60F17,

62E17,

Approximation by polynomial of Gaussians,

Limit theorem with non-Gaussian limits,

Lindeberg’s principle,

Berry-Esséen bound,

High-dimensional statistics,

Infinite-order U-statistics,

Delta method,

###### keywords:

[class=MSC]

###### keywords:

journalname authorprefix

, and
University College London, Harvard University and University College London

##  Introduction and main results

Gaussian universality results approximate functions of $n$ random vectors in
distribution by substituting each argument by a Gaussian surrogate, typically
as $n$ grows [11, 41, 35]. Informally, such results are of the form

$f_{n}(X_{n1},\ldots,X_{nn})\;\approx\;f_{n}(Z_{n1},\ldots,Z_{nn})\qquad\text{
in distribution as }n\rightarrow\infty$ (1)

where the arguments $X_{ni}$ are independent random vectors in
$\mathbb{R}^{d(n)}$ for each ${n\in\mathbb{N}}$. The approximation substitutes
independent Gaussian vectors ${Z_{ni}}$, where each ${Z_{ni}}$ has the same
mean, and covariance as $X_{ni}$. The case where the dimension $d(n)$ grows
with $n$ at a specified rate is commonly referred to as the high-dimensional
regime. Applications of Gaussian universality range from the spectra of large
random matrices [11, 55, 56, 61, 3] to the risk of neural networks and other
high-dimensional regressors [35, 28, 39, 25, 31].

The two main results presented here are (i) a Gaussian universality result for
polynomials that upper-bounds the approximation error in (1), and (ii) a lower
bound. The upper bound is a finite-sample bound that applies if $f_{n}$ is a
polynomial ${p_{m}:\mathbb{R}^{nd(n)}\rightarrow\mathbb{R}}$ of degree
${m(n)\leq n}$. Both $m(n)$ and $d(n)$ may grow with $n$. Since the set of
polynomials of degree $\leq m(n)$ in the space
${L_{2}=L_{2}(X_{n1},\ldots,X_{nn})}$ of square-integrable functions forms a
linear subspace, the bound describes Gaussian universality for functions in
this subspace. We extend it to functions whose $L_{2}$ distance to the
subspace is small. We show how the result can be used to generalise results on
infinite-order U-statistics [57, 13, 29, 60, 62, 22, 5] and on fluctuations on
subgraph counts [30, 4, 34]. Since any function in $L_{2}$ can be approximated
to arbitrary precision by a polynomial of sufficiently high degree, the result
applies in principle to all $L_{2}$ functions, but as the degree of the
polynomial increases, the upper bound on the approximation in (1)
deteriorates. That raises the question whether the bound can be improved. Our
second main result shows that that is at least in general not possible: The
bound is essentially optimal over the class of polynomials of degree $\leq
m(n)$, for ${m(n)=o(\log n)}$.

###  Outline

The remainder of this section states the main results (Section 1.2) and
surveys related work (Section 1.3). Additional universality results on
V-statistics follow in Section 2, and applications to the delta method,
U-statistics, and random graphs in Section 3. All proofs are in Sections 4–10.
The appendix contains an additional example, and details on some results
Senatov [51] used in our proofs.
Notation. Throughout, we suppress dependence on $n$, and use the abbreviations

$d\;=\;d(n)\qquad m\;=\;m(n)\qquad X_{i}\;=\;X_{ni}\qquad
X\;:=\;(X_{1},\ldots,X_{n})\,.$

The variables ${X_{1},\ldots,X_{n}}$ are always independent (but not
necessarily identically distributed) random elements of $\mathbb{R}^{d}$, and
$p_{m}$ is a polynomial ${\mathbb{R}^{nd}\rightarrow\mathbb{R}}$ of degree
$m$. By an absolute constant, we mean a constant that does not depend on $n$,
$d$, or $m$, on $p_{m}$, or on the law of $X$.

###  Main results

Applying (1) directly to a polynomial $p_{m}$ yields the approximation
$p_{m}(Z)$, for a collection of Gaussian vectors

$Z\;\coloneqq\;(Z_{1},\ldots,Z_{n})\qquad\text{ where }\quad
Z_{1}\operatorname{{\perp\\!\\!\\!\perp}}\ldots\operatorname{{\perp\\!\\!\\!\perp}}Z_{n}\quad\text{
and }\quad Z_{i}\sim\mathcal{N}(\mathbb{E}[X_{i}],\text{\rm Var}[X_{i}])\;.$

In this case, ${p_{m}(Z)}$ computes powers up to degree $m$ of each surrogate
variable. Our universality results rely on Lindeberg’s principle, which
considers a telescoping-sum expansion

$\displaystyle f_{n}(X_{1},\ldots,X_{n})-f_{n}(Z_{1},\ldots,Z_{n})$
$\displaystyle\;=\;\operatorname{\medmath\sum}_{i=1}^{n}\big{(}f_{n}(X_{1},\ldots,X_{i-1},X_{i},Z_{i+1},\ldots,Z_{n})-f_{n}(X_{1},\ldots,X_{i-1},Z_{i},Z_{i+1},\ldots,Z_{n})\big{)}\;,$

followed by a Taylor expansion of each summand with respect to their $i$-th
argument. While this adapts well to a multilinear function $f_{n}$, it is not
directly applicable to $p_{m}$, which involves higher powers of $X_{i}$. This
motivates us to augment the original random vectors: For each $i\leq n$,
consider the centred powers of $X_{i}$,

$\displaystyle\bar{X}_{i}\;\coloneqq\;X_{i}-\mathbb{E}X_{i}\;,\;\;\;\overline{X_{i}^{\otimes
2}}\coloneqq X_{i}^{\otimes 2}-\mathbb{E}\big{[}X_{i}^{\otimes
2}\big{]}\;,\;\;\;\;\;\ldots\;,\;\;\;\;\;\overline{X_{i}^{\otimes m}}\coloneqq
X_{i}^{\otimes m}-\mathbb{E}\big{[}X_{i}^{\otimes m}\big{]}\;,$

and define the concatenated random tensor

$\displaystyle\mathbf{X}_{i}\;\coloneqq\;\begin{pmatrix}\,\bar{X}_{i}\;,\;\overline{X_{i}^{\otimes
2}}\;,\;\ldots\;,\;\overline{X_{i}^{\otimes m}}\,\end{pmatrix}$ (2)

with dimension ${D=d+d^{2}+\ldots+d^{m}}$. For a suitable tensor $T_{m}$ of
polynomial coefficients, we then have

$\displaystyle p_{m}(X)-\mathbb{E}[\,p_{m}(X)]\;=\;\langle
T_{m}\,,\,(1,\mathbf{X}_{1})^{\top}\otimes\ldots\otimes(1,\mathbf{X}_{n})^{\top}\rangle\;=:\;q_{m}(\mathbf{X}_{1},\ldots,\mathbf{X}_{n})\;.$
(3)

See Section 2.1 for details on tensor notation. The function $q_{m}$ is
multilinear. As surrogates for the “augmented” variables
${\mathbf{X}=(\mathbf{X}_{1},\ldots,\mathbf{X}_{n})}$, we choose a collection
of Gaussian vectors

$\Xi\;\coloneqq\;(\xi_{1},\ldots,\xi_{n})\qquad\text{ where
}\quad\xi_{1}\operatorname{{\perp\\!\\!\\!\perp}}\ldots\operatorname{{\perp\\!\\!\\!\perp}}\xi_{n}\quad\text{
and }\quad\xi_{i}\sim\mathcal{N}(\mathbb{E}[\mathbf{X}_{i}],\text{\rm
Var}[\mathbf{X}_{i}])\;.$

Choosing the function $f_{n}$ in (1) as either $p_{m}$ or $q_{m}$ then yields
the approximations

$p_{m}(X)\;\approx\;p_{m}(Z)\qquad\text{ or }\qquad
p_{m}(X)\;\approx\;\mathbb{E}[p_{m}(X)]+q_{m}(\Xi)$

Although $q_{m}$ multiplies $n$ coefficients, the tensor $T_{m}$ is such that
no resulting power exceeds $m$. The variable $q_{m}(\Xi)$ is thus a degree-$m$
polynomial of Gaussians. Our Theorem 1 provides an approximation by
$q_{m}(\Xi)$, and we defer to Section 2.2 for situations where $q_{m}(\Xi)$
may be further approximated by $p_{m}(Z)$. The bound is given in terms of the
moment terms

$\displaystyle\sigma\;\coloneqq$ $\displaystyle\;\sqrt{\text{\rm
Var}\,q_{m}(\mathbf{X})}\;\;$ and $\displaystyle\;M_{\nu;i}\;\coloneqq$
$\displaystyle\;\|\partial_{i}q_{m}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\|_{L_{\nu}}\;,$
(4)

where
$\mathbf{W}_{i}\coloneqq(\mathbf{X}_{1},\ldots,\mathbf{X}_{i-1},\mathbf{0},\xi_{i+1},\ldots,\xi_{n})\in\mathbb{R}^{nD}$
and
${\|{\,\vbox{\hbox{\tiny$\bullet$}}\,}\|_{L_{\nu}}=(\mathbb{E}|{\,\vbox{\hbox{\tiny$\bullet$}}\,}|^{\nu})^{1/\nu}}$.

######  Theorem 1 (Main result).

Fix $\nu\in(2,3]$. Then there exists some absolute constant $C>0$ such that

$\displaystyle\big{|}\mathbb{P}(\sigma^{-1}q_{m}(\mathbf{X})\leq
t)-\mathbb{P}(\sigma^{-1}q_{m}(\Xi)\leq
t)\big{|}\;\leq\;C\,\Big{(}\mfrac{\sum_{i=1}^{n}M_{\nu;i}^{\nu}}{(1+t^{2})^{\nu/2}\,\sigma^{\nu}}\Big{)}^{\frac{1}{\nu
m+1}}\;$

for every $n,m,d\in\mathbb{N}$, every $t\in\mathbb{R}$, and every $\sigma>0$.
Moreover, we have $\mathbb{E}[q_{m}(\mathbf{X})]=\mathbb{E}[q_{m}(\Xi)]=0$ and
$\text{\rm Var}[q_{m}(\mathbf{X})]=\text{\rm Var}[q_{m}(\Xi)]$.

######  Remark.

A few comments: (i) Dimension dependence. The upper bound depends on the
dimension $d$, via the moment terms defined in (4). (ii) Monotone
transformations. Theorem 1 also applies to strictly monotone functions of
polynomials (since it controls a Kolmogorov distance, which is invariant under
strictly monotone transforms). For example, an exponential of
$q_{m}(\mathbf{X})$ can be approximated by an exponential of $q_{m}(\Xi)$.

The polynomials of degree $\leq m$ in $L_{2}(X)$ form a linear subspace of
$L_{2}(X)$. Theorem 1 approximates functions in this subspace. A simple
modification extends the result to functions that are close to the subspace in
the $L_{2}$ norm:

######  Theorem 2 (Approximate polynomials).

Fix $\nu\in(2,3]$. There exists some absolute constant $C>0$ such that, for
every $n,m,d\in\mathbb{N}$ and $\sigma>0$,

$\displaystyle\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}\big{(}\sigma^{-1}f(X)\leq
t\big{)}-\mathbb{P}\big{(}\sigma^{-1}$ $\displaystyle q_{m}(\Xi)\leq
t\big{)}\big{|}$ $\displaystyle\;\leq$
$\displaystyle\;C\Big{(}\Big{(}\mfrac{\|f(X)-q_{m}(\mathbf{X})\|_{L_{2}}}{\sigma}\Big{)}^{\frac{2}{2m+1}}+\Big{(}\mfrac{\sum_{i=1}^{n}M_{\nu;i}^{\nu}}{\sigma^{\nu}}\Big{)}^{\frac{1}{\nu
m+1}}\Big{)}\;$

for every measurable function $f:\mathbb{R}^{nd}\rightarrow\mathbb{R}$.

In Section 3, we apply this version of the result to obtain:

  1. 1.

A high-dimensional delta method. Due to a phase transition across polynomial-
of-Gaussian approximations of different degrees, the resulting limit
distributions for functions of sample averages may non-Gaussian and even non-
consistent. See Proposition 8 for the result and a simple example where such
transition happens in high dimensions.

  2. 2.

Finite sample bounds that generalise a range of existing results on high-
dimensional and infinite-order U-statistics [57, 13, 29, 60, 62, 22, 5]. The
degree of the U-statistic may grow faster than $\log n$, provided the degree
of the approximating polynomial of Gaussians is $o(\log n)$. See Proposition
9.

  3. 3.

Results on fluctuations of subgraph densities at different orders, which
extend those in [30, 4, 34] by characterising a full range of vertex-level and
edge-level fluctuations with finite-sample bounds. See Section 3.3.

######  Remark (Variance domination).

Theorem 2 reduces the three examples above to a single property that we refer
to as _variance domination_ : Provided that $\mathbb{E}[f(X)]=0$, the
behaviour of $f(X)$ matches that of a polynomial up to an error that depends
only on the variance ratio $\text{\rm Var}[f(X)-q_{m}(\mathbf{X})]/\text{\rm
Var}[q_{m}(\mathbf{X})]$. In other words, $f(X)$ can be approximated by a
polynomial if we can extract a polynomial component of $f(X)$ that “dominates
in variance”. For the subgraph densities in Section 3.3, for example, variance
domination corresponds exactly to known geometric conditions that determine
which fluctuation is dominant.

A question not addressed by Theorem 1 is whether the bound is tight. Clearly,
it may be suboptimal if additional information about $f_{n}$ or the law of $X$
is available. For example, choose the $X_{i}$ as centred i.i.d. random
elements of $\mathbb{R}$ with unit variance, $p_{m}(X)$ as the empirical
average ${\sum_{i=1}^{n}X_{i}/n}$, and $\nu=3$. The Berry-Esséen theorem then
applies and guarantees a rate of ${O(n^{-1/2})}$, whereas Theorem 1 yields

$\displaystyle\Big{|}\mathbb{P}\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}X_{i}\leq
t\Big{)}-\mathbb{P}\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}\xi_{i}\leq
t\Big{)}\Big{|}\;\leq\;C\,\Big{(}\mfrac{\|X_{1}\|_{L_{3}}}{\sqrt{n}\,(1+t^{2})^{3/2}}\Big{)}^{\frac{1}{4}}\;=\;O(n^{-1/8})\;.$

If the only assumption made in (1) is that $f_{n}$ is polynomial of degree
${\leq m}$, however, the bound is essentially tight:

######  Theorem 3 (Lower bound).

Fix $\nu\in(2,3]$, and assume that $m$ is even with $m=o(\log n)$. Then there
exist a sequence of probability measures $\mu^{(n)}_{\nu,\sigma_{0}}$ , a
sequence of polynomials ${p^{*}_{m}=p^{*}_{m(n)}}$, and absolute constants
${c,C>0}$ and ${N\in\mathbb{N}}$, such that

$\displaystyle cn^{-\frac{\nu-2}{2\nu m}}\;\leq$
$\displaystyle\;\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}(p^{*}_{m}(X)\leq
t)-\mathbb{P}(p^{*}_{m}(Z)\leq t)\big{|}\;\leq\;Cn^{-\frac{\nu-2}{2\nu
m+2}}\;,$ $\displaystyle cn^{-\frac{\nu-2}{2\nu m}}\;\leq$
$\displaystyle\;\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}\big{(}q^{*}_{m}(\mathbf{X})\leq
t\big{)}-\mathbb{P}\big{(}q^{*}_{m}(\Xi)\leq
t\big{)}\big{|}\;\leq\;Cn^{-\frac{\nu-2}{2\nu m+2}}$

for i.i.d. variables ${X_{1},\ldots,X_{n}\sim\mu^{(n)}_{\nu,\sigma_{0}}}$ and
all $n\geq N$.

###### Proof.

See Section 6. Our proof is inspired by an asymmetric construction by Senatov
[51] that controls the probability of a centred multivariate average lying in
a sequence of uncentred Euclidean balls. For our problem, a different
asymmetrisation is required to obtain a comparable lower bound to the upper
bound from Theorem 1. Section 5 motivates the proof and constructs
$(\mu^{(n)}_{\nu,\sigma_{0}})$ and $(p_{m}^{*})$ explicitly. ∎

######  Remark.

For a generic function $f_{n}:\mathbb{R}^{nd}\rightarrow\mathbb{R}$, Theorem 2
establishes a universality result when $f_{n}$ is well-approximated by its
$m$-th order Taylor expansion. Theorem 3 shows that this Taylor approximation,
which becomes more accurate as $m$ grows, trades off against the
distributional approximation in (1), which deteriorates with $m$. In other
words, when no additional information about $f_{n}$ or the law of $X$ is
available, the error bound obtained from Theorem 1 is near-optimal, and
becomes tight as $m$ grows.

###  Related work

A large body of work on Gaussian universality already exists, with
applications across probability, statistics and machine learning: Notable
examples include characterising the spectrum of large random matrices [11, 55,
56, 61, 3] and analysing the risk of regression and neural network estimators
[35, 28, 39, 25, 31]. Those most relevant to our work are surveyed below.

_Lindeberg’s principle._ Gaussian universality results are typically proven
using Lindeberg’s method. This method was generalized beyond the central limit
theorem by Rotar [49, 48], Mossel, O’Donnell, and Oleszkiewicz [40, 41], and
Chatterjee [11]. An advantage of this method, compared to distribution-
specific techniques such as Fourier analysis or Stein’s method, is that it
adapts easily to nonlinear estimators with unknown asymptotic distributions.
On the other hand, it is known to result in sub-optimal error rates for a
range of specific problems (see the discussion after Theorem 3.3 in [12] for
empirical averages, and the remark in Section 4 of [8] for random matrices).
This sub-optimality is due to too much smoothing: Lindeberg’s principle
approximates the Kolmogorov metric by an integral probability metric, with
test functions that are at least twice-differentiable with a
${(\nu-2)}$-Hölder second derivative for some ${\nu>2}$. Theorem 3 shows this
sub-optimality is a necessary price of generality: For the general class of
$n$-dependent probability measures, Theorem 3 shows the bounds obtained by
Lindeberg’s principle are, in fact, near-optimal.

_Invariance principle for general multilinear forms._ The use of Lindeberg’s
method for multilinear forms goes back to Rotar [49, 48], who obtained
asymptotic approximations by polynomials of Gaussian for fixed $m$ and $d$. By
additionally employing Carbery-Wright inequality [10], Mossel et al. [41]
obtain a finite-sample Kolmogorov-distance bound for univariate data
distributions. Recent work also considers convergence in total variation, in
both the asymptotic [45] and the finite-sample regime [2, 36]. Another line of
work [23, 24] adapts the multivariate Stein’s method to general functions of
asymptotically normal random vectors, where the error bounds explicitly sum
over the $d$ different coordinates of the random vectors. These results either
explicitly assume $m$ and $d$ to be fixed, or impose implicit requirements
that may be too strong for modern applications. Indeed, the main technical
work behind our Theorem 1 and its applications is to obtain tight dependence
on $d(n)$ and $m(n)$, which allow our bounds to apply to the high-dimensional
regime.

_Error bounds for Gaussian universality._ Although the lower bound in our
Theorem 3 is new, similar rates in the upper bound have been observed in the
literature. For the problem of non-Gaussian approximation of a degree-two
U-statistic with kernel $u$, the known rates depend on the number of non-zero
eigenvalues of the Hilbert-Schmidt operator associated with $u$: $O(n^{-1})$
for five non-zero eigenvalues [26], $O(n^{-1/12})$ for one non-zero eigenvalue
[63], and $O(n^{-1/14})$ without eigenvalue assumptions [32]. It is also
conjectured in [63] that $O(n^{-1/12})$ is optimal, based on a result by
Senatov [51] that the Gaussian approximation of a heavy-tailed multivariate
average in a carefully chosen sequence of Euclidean balls is
$\Omega(n^{-1/12})$. Our proof of Theorem 3 relies on adapting an asymmetry
argument by [51] (see Section 5 for a sketch of intuition). Theorem 3 (with
$\nu=3$) does not directly address the conjecture by [63]: We provide a rate
between $n^{-1/6m}$ and $n^{-1/(6m+2)}$, but for a mixture of a heavy-tailed
average and a degree-$m$ V-statistic of Gaussians. It remains a open question
whether a similar lower bound holds for degree-$m$ U-statistics.

_Distribution approximations for high-dimensional statistics._ The
approximation of specific estimators in high-dimensional regimes is the
subject of an extensive literature. Such regimes differ by the parameters that
grow with $n$. Examples include degree-two U-statistics with $d=d(n)$ [13, 60,
62, 22, 32], quadratic forms with $n$-dependent weights [5], infinite-order
U-statistics with $m=m(n)$ [57, 53], and statistics with high-dimensional
outputs [15, 14, 53]. Our results assume univariate outputs, but allow general
dependence of $d$, $m$ and weights of the polynomial on $n$. The extension to
functions that can be approximated by polynomials in an $L_{2}$ sense, in
Theorem 2, plays a key role in our applications. For additional references on
U-statistics and subgraph count statistics, and more detailed comparisons to
our results, see Section 3.

_Terminology: Gaussian universality._ We use the term Gaussian universality to
refer to the approximation of a function of $(X_{i})_{i\leq n}$ by the same
function of Gaussian vectors $(Z_{i})_{i\leq n}$. Some parts of the
literature—for example, in the context of Gaussian approximation of Wiener
chaos—use the term instead to indicate that the overall function is
asymptotically normal, see e.g. Chapter 11 of [42]. Our usage of the term is
related to the notion of penultimate approximations: Examples include chi-
square and shifted-gamma distributions as approximations for the Gaussian CLT
limit [27, 7] and the Type-III extreme value distribution for extreme value
theorem [16]. While those penultimate approximations typically yield sharper
approximation rates than the final limits (Gaussian or extreme value
distributions), our approximations do not.

##  Additional results on universality

This section first makes the definition of the variables $\mathbf{X}_{i}$
precise. Section 2.2 shows that, under a mild condition, the approximations by
${p_{m}(Z)}$ and by ${\mathbb{E}[p_{m}(X)]+q_{m}(\mathbf{X})}$ are
asymptotically equivalent for simple V-statistics that arise for example from
the delta method.

###  Approximation by polynomials of Gaussian: details

To specify polynomials of vectors, we use tensor notation: By a tensor $T$ of
size ${d_{1}\times\ldots\times d_{k}}$, we mean an element of
${\mathbb{R}^{d_{1}\times\ldots\times d_{k}}}$. The tensor product of $k$
vectors ${x_{i}\in\mathbb{R}^{d_{i}}}$ is the tensor $\otimes_{i}x_{i}$ with
entries

$\otimes_{i\leq k}\,x_{i}({j_{1},\ldots,j_{k}})\;=\;x_{1}({j_{1}})\cdots
x_{k}({j_{k}})\quad\text{ for }j_{1}\leq d_{1},\ldots,j_{k}\leq d_{k}\;,$

and we write ${x_{1}^{\otimes r}:=\otimes_{i\leq r}\,x_{1}}$ for short. The
scalar product of two tensors of equal size is

$\langle S,T\rangle\;:=\;\operatorname{\medmath\sum}_{i_{1}\leq
d_{1},\ldots,i_{k}\leq
d_{k}}S(i_{1},\ldots,i_{k})T(i_{1},\ldots,i_{k})\qquad\text{ for
}S,T\in\mathbb{R}^{d_{1}\times\ldots\times d_{k}}\;,$

or equivalently the Euclidean scalar product in
${\mathbb{R}^{d_{1}\times\ldots\times d_{k}}}$. Any polynomial $p_{m}$ of
degree ${\leq m}$ can be represented as

$\displaystyle
p_{m}(x_{1},\ldots,x_{n})\;=\;T_{0}+\operatorname{\medmath\sum}_{\begin{subarray}{c}r_{1}+\ldots+r_{n}\leq
m\end{subarray}}\langle T_{r_{1},\ldots,r_{n}}\,,\,x_{1}^{\otimes
r_{1}}\otimes\ldots\otimes x_{n}^{\otimes r_{n}}\rangle\;,$

where $T_{0}$ is a scalar and each $T_{r_{1},\ldots,r_{n}}$ is a tensor of
size ${d^{r_{1}}\times\ldots\times d^{r_{n}}}$. Having defined the augmented
random tensor $\mathbf{X}_{i}$ in (2), we can write $p_{m}$ as

$\displaystyle p_{m}(X)\;=\;\mathbb{E}[\,p_{m}(X)]\,+\,\langle
T_{m}\,,\,(1,\mathbf{X}_{1})^{\top}\otimes\ldots\otimes(1,\mathbf{X}_{n})^{\top}\rangle$
(5)

for a tensor $T_{m}$. $T_{m}$ is determined completely by $T_{0}$ and
$(T_{r_{1},\ldots,r_{n}})_{r_{1},\ldots,r_{n}\leq m}$. Since $p_{m}$ has
degree $m$, $T_{m}$ is such that for $m^{\prime}>m$, all $m^{\prime}$-fold
products of $\mathbf{X}_{1},\ldots,\mathbf{X}_{n}$ correspond to zero
coefficients in $T_{m}$.

Throughout the article, we also make use of the tensor vectorisation operator.
For a tensor $T$ of size $d_{1}\times\ldots\times d_{k}$, we define the
corresponding flattened vector as

$\displaystyle\text{\rm
vec}(T)\;\coloneqq\;\big{(}\,T(1,\ldots,1,1)\,,\,T(1,\ldots,1,2)\,,\,\ldots\,,\,T(d_{1},\ldots,d_{k-1},d_{k})\,\big{)}^{\top}\;\in\mathbb{R}^{d_{1}\cdots
d_{k}}\;.$

###  Simple V-statistics

In Section 1.2, we have motivated the approximation of
$p_{m}(X)-\mathbb{E}[p_{m}(X)]$ by $q_{m}(\Xi)$, a polynomial of the augmented
variables, by noting how $q_{m}$ adapts well to Lindeberg’s principle. On the
other hand, in the case of
$p_{m}(X)=g(\frac{1}{\sqrt{n}}\sum_{i=1}^{n}X_{i})$, the continuous mapping
theorem suggests an approximation by $p_{m}(Z)$, a polynomial of the original
variables, at least when $g$ and $d$ are fixed in $n$. A natural question is
whether the two approximations, i.e. the two different notions of Gaussian
universality, coincide. Note that in the high-dimensional regime, it is non-
trivial to show that one may replace $X_{i}$’s by $Z_{i}$’s: [23, 24] have
used Stein’s method and a Lipschitz argument to control the approximation
error by $p_{m}(Z)$ in smooth function bounds, but those bounds are only well-
controlled when dimension $d$ grows sublinearly in $n$ and not well-adapted to
the high-dimensional setting.

In this section, we confirm that the two notions of universality do coincide
in the high-dimensional regime, under a mild moment condition and for simple
V-statistics. We focus on the case where $X_{1},\ldots,X_{n}$ are i.i.d. zero-
mean and consider, for $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$, the statistic

$\displaystyle
v_{m}(x_{1},\ldots,x_{n})\;\coloneqq\;\mfrac{1}{n^{m}}\operatorname{\medmath\sum}_{i_{1},\ldots,i_{m}\in[n]}\langle
S,\,x_{i_{1}}\otimes\ldots\otimes x_{i_{m}}\rangle\;,$ (6)

where $S\in\mathbb{R}^{d^{m}}$ is a deterministic, symmetric tensor. Note that
this is exactly the dominating quantity under an $m$-th order delta method,
and when $S$ is not required to be symmetric, any $p_{m}(X)$ of the form (5)
can be written as a weighted sum of such V-statistics.

The moment condition is cumbersome to state, but can be motivated as follows.
We first notice that for the distributions of $p_{m}(Z)$ and $q_{m}(\Xi)$ to
agree, we require the contribution of terms like $Z_{i}^{\otimes m}$ (found in
$p_{m}(Z)$) and $\mathcal{N}(\mathbb{E}[X_{i}^{\otimes m}],\text{\rm
Var}[X_{i}^{\otimes m}])$ (found in $q_{m}(\Xi)$) to be negligible. To make
the condition well-adapted to a setting where $d$ and the law of $X_{i}$’s may
vary in $n$, we need careful controls for all possible $m$-fold products of
$Z_{i}$’s and of $X_{i}$’s with at least one repeated element. We coin this
moment condition $\delta$-regularity:

######  Definition 4.

$v_{m}$ is $\delta$-regular with respect to $X$ if, for some $\delta\in[0,1)$,
there exists an absolute constant $C>0$ such that for all $j\in[m-1]$,

$\displaystyle\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\max\bigg{\\{}\text{\rm
Var}\bigg{[}\bigg{\langle}S\,,\,\bigotimes_{l=1}^{j}X_{l}^{\otimes
q_{l}}\bigg{\rangle}\bigg{]}\,,\,\text{\rm Var}\bigg{[}\bigg{\langle}S\,,\,$
$\displaystyle\bigotimes_{l=1}^{j}Z_{l}^{\otimes
q_{l}}\bigg{\rangle}\bigg{]}\bigg{\\}}$ (7) $\displaystyle\;\leq$
$\displaystyle\;Cn^{m+\delta}m^{-j}\,\text{\rm Var}[v_{m}(X)]\;,$
$\displaystyle\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\max\bigg{\\{}\bigg{(}\mathbb{E}\bigg{[}\bigg{\langle}S\,,\,\bigotimes_{l=1}^{j}X_{l}^{\otimes
q_{l}}\bigg{\rangle}\bigg{]}\bigg{)}^{2}\,,\,\bigg{(}\mathbb{E}\bigg{[}\bigg{\langle}S\,,\,$
$\displaystyle\bigotimes_{l=1}^{j}Z_{l}^{\otimes
q_{l}}\bigg{\rangle}\bigg{]}\bigg{)}^{2}\bigg{\\}}$ (8) $\displaystyle\;\leq$
$\displaystyle\;C\,n^{m+\delta}\,\text{\rm Var}[v_{m}(X)]\;.$

######  Remark.

The $n^{m}$ factor on the RHS balances the variance of the un-normalised
V-statistic $v_{m}(X)$. The $m^{-j}$ factor accounts for both the multiplicity
of terms of the form on LHS in $\text{\rm Var}[v_{m}(X)]$,
$\binom{m-1}{j-1}=O(m^{j-1})$, and the fact that the moment of a univariate
standard Gaussian $\eta$ grows as $\mathbb{E}[\eta^{m}]=O(m^{m/2})$. In Lemma
22, we provide a verification of $\delta$-regularity for a degree-$m$
V-statistic of univariate Gaussians as part of the proof of Theorem 3.
Sufficient conditions for verifying $\delta$-regularity are deferred to Remark
1. There, we show that when $m$ and $d$ are fixed, up to a spectral condition,
$\delta$-regularity always holds. It suggests that the requirement of
$\delta$-regularity is specific to our high-dimensional setup, where both $m$
and $d$ may grow in $n$.

We are ready to state the main result of this subsection, which confirms that
under $\delta$-regularity for the V-statistic $v_{m}$ in (6), the
approximations by $q_{m}(\Xi)$ and $p_{m}(Z)-\mathbb{E}[p_{m}(X)]$ do agree.
Here and below, we let $q^{v}_{m}$ be the multilinear representation of
$v_{m}$ defined in (3).

######  Proposition 5.

Fix $\nu\in(2,3]$ and let $(X_{i})_{i\leq n}$ be i.i.d. zero-mean. If $v_{m}$
is $\delta$-regular with respect to $X$ for some $\delta\in[0,1)$, there exist
some absolute constants $C,C^{\prime}>0$ such that

$\displaystyle\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}\big{(}\sigma^{-1}(q^{v}_{m}(\Xi)+\mathbb{E}[v_{m}(X)])\leq
t\big{)}-\mathbb{P}\big{(}\sigma^{-1}v_{m}(Z)\leq
t\big{)}\big{|}\,\;\leq\;\,Cn^{-\frac{1-\delta}{2m+1}}\;,$
$\displaystyle\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}(\sigma^{-1}v_{m}(X)\leq
t)-\mathbb{P}(\sigma^{-1}v_{m}(Z)\leq
t)\big{|}\,\;\leq\;\,Cn^{-\frac{1-\delta}{2m+1}}+C^{\prime}\Delta_{\delta}\;,$
$\displaystyle\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}(\sigma^{-1}(v_{m}(X)-\mathbb{E}[v_{m}(X)])\leq
t)-\mathbb{P}(\sigma^{-1}(v_{m}(Z)-\mathbb{E}[v_{m}(Z)])\leq t)\big{|}$
$\displaystyle\hskip
200.0003pt\,\;\leq\;\,Cn^{-\frac{1-\delta}{2m+1}}+C^{\prime}\Delta_{\delta}\;,$

where the error term is defined as

$\displaystyle\Delta_{\delta}\;\coloneqq\;\Big{(}\mfrac{\sum_{i=1}^{n}M_{\nu;i}^{\nu}}{\sigma^{\nu}}\Big{)}^{\frac{1}{\nu
m+1}}\;.$

######  Remark.

(i) Proposition 5 is proved by an adaptation of variance domination in Theorem
2 together with the variance ratio bounds in Lemma 6. (ii) While
$\mathbb{E}[v_{m}(X)]$ does not necessarily equal $\mathbb{E}[v_{m}(Z)]$, the
third bound of Proposition 5 implies that the difference is asymptotically
negligible. (iii) An explicit bound on $\Delta_{\delta}$ is given in Lemma 7.

The proof of Proposition 5 is included in Section 9, and an illustration of
Gaussian universality for a toy V-statistic in Section A.1. The proof makes
use of the next two lemmas, which are also useful for subsequent applications.
Their proofs are included in Section 9. The first lemma shows that
$\delta$-regularity can be used to control two variance ratios, which are
similar to the moment ratio obtained from variance domination (Theorem 2):

######  Lemma 6.

Suppose $(X_{i})_{i\leq n}$ are i.i.d. zero-mean. Assume that $v_{m}$ is
$\delta$-regular with respect to $X$ for some $\delta\in[0,1)$. Also assume a
coupling between $\xi_{i}$ and $Z_{i}$ such that $\xi_{i1}=Z_{i}$ almost
surely. Then there exists some absolute constants $C,C_{*}>0$ such that

$\displaystyle\mfrac{\|q^{v}_{m}(\Xi)+\mathbb{E}[v_{m}(X)]-v_{m}(Z)\|_{L_{2}}^{2}}{\text{\rm
Var}[q^{v}_{m}(\Xi)]}\;\leq\;\mfrac{C^{m}}{n^{1-\delta}}$

and $\big{(}1-(C_{*})^{m}n^{-(1-\delta)/2}\big{)}^{2}\leq\frac{\text{\rm
Var}[v_{m}(Z)]}{\text{\rm
Var}[v_{m}(X)]}\;\leq\;\big{(}1+(C_{*})^{m}n^{-(1-\delta)/2}\big{)}^{2}$.

The next lemma applies Theorem 1 to show Gaussian universality with respect to
the augmented variables $\mathbf{X}$, and use the simple structure of $v_{m}$
to bound the moment ratio explicitly. The error bounds are given in terms of
both $M_{\nu;i}$ defined in Theorem 1 for $q^{v}_{m}$ and

$\displaystyle\alpha_{\nu}(S,k)\;\coloneqq\;\bigg{\|}\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\Big{\langle}S\,,\,\overline{X_{1}^{\otimes
p_{1}}}\otimes\ldots\otimes\overline{X_{k}^{\otimes
p_{k}}}\,\Big{\rangle}\bigg{\|}_{L_{\nu}}\quad\text{ for }\nu\in[2,3]\text{
and }k\in[m]\;.$

We also provide upper and lower bounds on $\text{\rm Var}[v_{m}(X)]$ in terms
of $\alpha_{2}(S,k)$.

######  Lemma 7.

Fix $\nu\in(2,3]$ and let $(X_{i})_{i\leq n}$ be i.i.d. zero-mean. Then there
exists some absolute constant $C>0$ such that, for every $n,m,d\in\mathbb{N}$,
$t\in\mathbb{R}$ and $\sigma=\text{\rm Var}[v_{m}(X)]>0$,

$\displaystyle\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}(\sigma^{-1}q^{v}_{m}(\mathbf{X})\leq
t)-\mathbb{P}(\sigma^{-1}q^{v}_{m}(\Xi)\leq
t)\big{|}\;\leq\;C\Big{(}\mfrac{\sum_{i=1}^{n}M_{\nu;i}^{\nu}}{\sigma^{\nu}}\Big{)}^{\frac{1}{\nu
m+1}}\;=\;C\Delta_{\delta}\;.$

Meanwhile, if $n\geq 2m^{2}$, there exist absolute constants
$C^{\prime},C_{1},C_{2}>0$ such that

$\displaystyle\qquad\qquad\qquad\quad\Delta_{\delta}\;\leq\;C^{\prime}\,n^{-\frac{\nu-2}{2\nu
m+2}}\,\beta_{m,\nu}^{\frac{\nu}{2\nu
m+2}}\;,\qquad\beta_{m,\nu}\;\coloneqq\;\mfrac{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{\nu}(S,k))^{2}}{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{2}(S,k))^{2}}\;,$
$\displaystyle\text{ and
}\quad\mfrac{(C_{1})^{m}}{n^{2m}}\operatorname{\medmath\sum}_{k=1}^{m}\mbinom{n}{k}\,(\alpha_{2}(S,k))^{2}\;\leq\;\text{\rm
Var}[v_{m}(X)]\;\leq\;\mfrac{(C_{2})^{m}}{n^{2m}}\operatorname{\medmath\sum}_{k=1}^{m}\mbinom{n}{k}\,(\alpha_{2}(S,k))^{2}\;$

######  Remark.

The moment bound in Lemma 7 involves a ratio of the $\nu$-th moment versus the
second moment of the same quantity. In fact, the ratio is a strict
generalisation of the moment ratio from the classical Berry-Esséen bound for
sample averages ($m=1$), and similar to the Berry-Esséen ratio, we expect it
to be $O(1)$ for distributions that are not too heavy-tailed. A crude upper
bound on this ratio is deferred to Remark 2.

######  Remark 1 (Sufficient condition for verifying $\delta$-regularity).

A sufficient condition for $\delta$-regularity can be obtained from a moment
condition and a spectral condition. Recall that $\text{\rm vec}(T)$ is the
vectorisation of a tensor $T$ (Section 2.1), and let $\lambda_{\rm max}(A)$
and $\lambda_{\rm min}(A)$ denote the maximum and minimum eigenvalues of a
real symmetric matrix $A$. Suppose there exist $\omega^{(1)}_{\rm
max},\omega^{(2)}_{\rm max}>0$ such that for all $j\leq m-1$ and any
$q_{1},\ldots,q_{j}\in\mathbb{N}$ that sum up to $m$,

$\displaystyle\lambda_{\rm max}\Big{(}\text{\rm Var}\Big{[}\text{\rm
vec}\Big{(}\otimes_{l=1}^{j}X_{l}^{\otimes q_{l}}\Big{)}\Big{]}\Big{)}\;\leq$
$\displaystyle\;\omega^{(1)}_{\rm max}\;,$ $\displaystyle\lambda_{\rm
max}\Big{(}\mathbb{E}\Big{[}\text{\rm
vec}\Big{(}\otimes_{l=1}^{j}X_{l}^{\otimes q_{l}}\Big{)}\text{\rm
vec}\Big{(}\otimes_{l=1}^{j}X_{l}^{\otimes
q_{l}}\Big{)}^{\top}\Big{]}\Big{)}\;\leq$ $\displaystyle\;\omega^{(2)}_{\rm
max}\;.$

and suppose $\lambda_{\rm min}(\Sigma_{2})>0$, where

$\displaystyle\Sigma_{2}\;\coloneqq\;\text{\rm Var}[\text{\rm
vec}(Q_{X})]\;,\qquad\qquad
Q_{X}\;\coloneqq\;\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq 1\end{subarray}}\overline{X_{1}^{\otimes
p_{1}}}\otimes\ldots\otimes\overline{X_{k}^{\otimes p_{k}}}\;\;.$

WLOG take $\|\text{\rm vec}(S)\|=1$. Then we have

$\displaystyle\eqref{eq:delta:reg:var}\;\leq\;\omega^{(1)}_{\rm
max}\;,\qquad\qquad\eqref{eq:delta:reg:mean}\;\leq\;\omega^{(2)}_{\rm
max}\;,\qquad\qquad\text{\rm Var}[v_{m}(X)]\;\geq\;C^{m}n^{-m}\lambda_{\rm
min}(\Sigma_{2})$

for some absolute constant $C>0$ provided that $n\geq 2m^{2}$; the third bound
is obtained from Lemma 7. Since $m=o(\log(n))$, $C^{m}=O(n^{\epsilon})$ for
any $\epsilon>0$, so to show $\delta$-regularity, it suffices to check that
for some constant $C>0$, some $\delta\in[0,1)$ and some $\epsilon>0$,

$\displaystyle\max\\{\omega^{(1)}_{\rm max}\,,\,\omega^{(2)}_{\rm
max}\\}\;\leq$ $\displaystyle\;C\,n^{\delta-\epsilon}\,\lambda_{\rm
min}(\Sigma_{2})\,.$

Notice that $\lambda_{\rm min}(\Sigma_{2})$ is the minimum eigenvalue of the
covariance matrix of $X_{1}$ when $m=1$. Moreover, when $m$ and $d$ are fixed,
up to a positive minimum eigenvalue condition, $\delta$-regularity always
holds. We emphasise that the above only gives crude bounds on the quantities
in Definition 4. Instead of taking the minimum eigenvalue of $\Sigma_{2}$, it
can often be easier to compute $\text{\rm Var}[v_{m}(X)]$ directly: One
approach is to decompose a V-statistic as a sum of U-statistics (see Lemma 27)
followed by using known moment formulas for U-statistics (see Section 8). Such
an approach is used in Lemma 22 as part of the proof of Theorem 3.

######  Remark 2 (Upper bound on the moment ratio in Lemma 7).

We again use a spectral condition. Consider $\Sigma_{2}$ and $Q_{X}$ defined
in Remark 1, and the analogue of $\Sigma_{2}$ but with a fourth moment:

$\displaystyle\Sigma_{4}\;\coloneqq$
$\displaystyle\;\mathbb{E}\Big{[}\,\text{\rm vec}\big{(}Q_{X}^{\otimes
2}\big{)}\,\text{\rm vec}\big{(}Q_{X}^{\otimes 2}\big{)}^{\top}\,\Big{]}\;.$

Write $\omega_{\rm max}(A)$ as the maximum eigenvalue of a matrix $A$, and
assume that $\omega_{\rm min}(\Sigma_{2})>0$. Then by noting $\nu<4$, an upper
bound on the moment ratio in Lemma 7 is given as

$\displaystyle\beta_{m,\nu}\;\leq\;\mfrac{\omega_{\rm
max}(\Sigma_{4})^{1/2}}{\omega_{\rm min}(\Sigma_{2})}\;.$

##  Applications

In this section, we obtain generalisations of several existing results as
applications of our theorems. For notational simplicity, we mostly consider
i.i.d. data and symmetric functions. As our general results also hold in the
non-i.i.d. and asymmetric case, the interesting phenomena we observe can be
readily extended, and Section 3.3 provides one such example. Notably, since
any degree-$m$, symmetric polynomial of $n$ variables can be written as a
weighted sum of U-statistics and V-statistics with degree $\leq m$, all our
applications will be reduced to studying the asymptotic distributions of
U-statistics and V-statistics. The proofs for all results in this section are
included in Section 10.

###  Higher-order delta method

We first extend the classical delta method [47, 6] to a high-dimensional
setup. Assume that $(X_{i})_{i\leq n}$ are i.i.d. and, for some smooth
function $g:\mathbb{R}^{d}\rightarrow\mathbb{R}$, define

$\displaystyle\hat{g}(X)\;\coloneqq\;g\Big{(}\mfrac{1}{n}\operatorname{\medmath\sum}_{i=1}^{n}X_{i}\Big{)}\;=\;g\Big{(}\mfrac{1}{n}\operatorname{\medmath\sum}_{i=1}^{n}\bar{X}_{i}+\mathbb{E}[X_{1}]\Big{)}\;,\qquad\text{
where }\bar{X}_{i}=X_{i}-\mathbb{E}[X_{1}]\;.$

$\hat{g}(X)$ is called a plug-in estimator of $g(\mathbb{E}X_{1})$. A guiding
example is $g_{\rm toy}(x)\coloneqq x^{\top}x$, which yields a simple
V-statistic

$\displaystyle\hat{g}_{\rm toy}(X)\;\coloneqq\;g_{\rm
toy}\Big{(}\mfrac{1}{n}\operatorname{\medmath\sum}_{i=1}^{n}X_{i}\Big{)}\;=\;\mfrac{1}{n^{2}}\operatorname{\medmath\sum}_{i,j=1}^{n}X_{i}^{\top}X_{j}\;.$

To see how the distribution of the plug-in estimator behaves through variance
domination, consider a Taylor expansion

$\displaystyle\hat{g}_{\rm toy}(X)-g_{\rm
toy}(\mathbb{E}[X_{1}])\;=\;\mfrac{2}{n}\operatorname{\medmath\sum}_{i=1}^{n}\bar{X}_{i}^{\top}\mathbb{E}[X_{1}]\,+\,\mfrac{1}{n^{2}}\operatorname{\medmath\sum}_{i,j=1}^{n}\bar{X}_{i}^{\top}\bar{X}_{j}\;.$

The variances of the first and second-order expansions are respectively on the
order

$\displaystyle\Theta\Big{(}\mfrac{\partial g_{\rm
toy}(\mathbb{E}[X_{1}]}{\sqrt{n}}\Big{)}\;=$
$\displaystyle\;\Theta\Big{(}\mfrac{\mathbb{E}[X_{1}]^{\top}\text{\rm
Var}[X_{1}]\mathbb{E}[X_{1}]}{\sqrt{n}}\Big{)}\;,$ (9) $\displaystyle\text{
and }\qquad\Theta\Big{(}\mfrac{\partial^{2}g_{\rm
toy}(\mathbb{E}[X_{1}]}{\sqrt{n}}\Big{)}\;=$
$\displaystyle\;\Theta\Big{(}\mfrac{\text{\rm
Var}[\bar{X}_{1}^{\top}\bar{X}_{2}]}{n}+\mfrac{\text{\rm
Var}[\bar{X}_{1}^{\top}\bar{X}_{1}]}{n^{3/2}}\Big{)}\;.$ (10)

Classically when $d$ is fixed, normality of the plug-in estimator follows from
the first-order delta method whenever $\partial g(\mathbb{E}[X_{1}])\neq 0$.
For $\hat{g}_{\rm toy}(X)$, this condition is equivalent to
$\mathbb{E}[X_{1}]\neq 0$, and exactly corresponds to when the first-order
Taylor expansion dominates in variance. In the high-dimensional regime,
however, the moment terms above can vary with $n$ through their
$d$-dependence: Take $X_{i}\sim\mathcal{N}(\mu,I_{d})$ with $\|\mu\|_{2}=1$,
which yields

$\displaystyle\eqref{eq:plug:in:toy:first:var}\;=$
$\displaystyle\;\Theta\Big{(}\mfrac{1}{\sqrt{n}}\Big{)}$ and
$\displaystyle\eqref{eq:plug:in:toy:second:var}\;=$
$\displaystyle\;\Theta\Big{(}\mfrac{d}{n}+\mfrac{d}{n^{3/2}}\Big{)}\;.$

Even though $\mu=\mathbb{E}[X_{1}]$ and therefore $\partial
g(\mathbb{E}[X_{1}])$ is non-zero, the first-order term is still dominated in
variance by the second-order term when $d=\omega(\sqrt{n})$: The first-order
delta method fails to hold, and the plug-in estimator is no longer
asymptotically normal. We now formalise this in a result concerning an $m$-th
order delta method.

#### Derivatives.

A delta method relies on the derivatives of $g$, and some shorthands are
introduced next. For $x,x_{1},\ldots,x_{m}\in\mathbb{R}^{d}$ and
$m\in\mathbb{N}\cup\\{0\\}$, we define

$\displaystyle g_{m}^{(x)}(x_{1},\ldots,x_{m})\;\coloneqq$
$\displaystyle\;\mfrac{1}{m!}\big{\langle}\partial_{m}\,g(x)\,,\,(x_{1}-\mathbb{E}X_{1})\otimes\ldots\otimes(x_{m}-\mathbb{E}X_{1})\big{\rangle}$
$\displaystyle\hat{g}_{m}^{(\mathbb{E}X_{1})}(x_{1},\ldots,x_{n})\;\coloneqq$
$\displaystyle\;n^{-m}\,\operatorname{\medmath\sum}_{i_{1},\ldots,i_{m}\in[n]}\,g_{m}^{(\mathbb{E}X_{1})}\big{(}x_{i_{1}},\ldots,x_{i_{m}}\big{)}\;.$

which is a degree-$m$ polynomial function. If $g$ is $(m+1)$-times
continuously differentiable everywhere, we can perform an $m$-th order Taylor
expansion with the integral remainder. Let $S_{n}\coloneqq n^{-1}\sum_{i\leq
n}\bar{X}_{i}$ and draw $\Theta\sim\textrm{Uniform}[0,1]$ independently of
$X$. Then almost surely

$\displaystyle\hat{g}(X)\;=\;g(\mathbb{E}X_{1})+\operatorname{\medmath\sum}_{j=1}^{m}\hat{g}_{j}^{(\mathbb{E}X_{1})}(X)\,+\,(m+1)\mathbb{E}\big{[}(1-\Theta)^{m+1}\,\hat{g}_{m+1}^{(\mathbb{E}X_{1}+\Theta
S_{n})}(X)\,\big{|}\,X\big{]}\;.$

Note that when $\hat{g}_{m+1}^{(\mathbb{E}X_{1}+\Theta S_{n})}$ is independent
of $\Theta$, the $(m+1)$ factor is cancelled out by
$\mathbb{E}[(1-\Theta)^{m+1}]=(m+1)^{-1}$. The penultimate approximation will
be identified by comparing which term of the Taylor expansion dominates in
variance.

For simplicity of notation, we will assume that
$\hat{g}^{(\mathbb{E}X_{1})}_{m}$ is $\delta$-regular with respect to
$(\bar{X}_{i})_{i\leq n}$ (see Definition 4 and Remark 1 for a sufficient
condition), so that we can apply universality directly to $X$ and not just the
augmented variables. In the case of $g_{\rm toy}$ with
$\bar{X}_{i}\sim\mathcal{N}(0,I_{d})$, this corresponds to requiring
$\bar{X}_{1}^{\top}\bar{X}_{1}$ to be negligible in variance, which always
holds in view of (10).

#### Moments.

The result involves several moment terms. For each
$m\in\mathbb{N}\cup\\{0\\}$, define

$\displaystyle\mu_{m}\;\coloneqq\;\mathbb{E}\,\hat{g}_{m}^{(\mathbb{E}X_{1})}(X)\;.$

Note that $\mu_{0}=g(\mathbb{E}X_{1})$, which is the target of estimation
under the plug-in principle. We also define, for $\nu\in(2,3]$ and $k\in[m]$,
the moment terms

$\displaystyle\epsilon_{m}\;\coloneqq\;\mfrac{\text{\rm
Var}\Big{[}\sum_{l=1}^{m-1}\hat{g}^{(\mathbb{E}X_{1})}_{l}(X)\Big{]}}{\text{\rm
Var}\Big{[}\hat{g}_{m}^{(\mathbb{E}X_{1})}(X)\Big{]}}+\mfrac{(m+1)^{2}\Big{\|}\mathbb{E}\Big{[}(1-\Theta)^{m+1}\,\hat{g}_{m+1}^{\big{(}\mathbb{E}X_{1}+\Theta
n^{-1}\sum_{i\leq
n}\bar{X}_{i}\big{)}}(X)\Big{|}X\Big{]}\Big{\|}_{L_{2}}^{2}}{\text{\rm
Var}\Big{[}\hat{g}_{m}^{(\mathbb{E}X_{1})}(X)\Big{]}}\,,$
$\displaystyle\alpha_{m,\nu}(k)\coloneqq\bigg{\|}\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\Big{\langle}\mfrac{\partial_{m}g(\mathbb{E}X_{1})}{m!}\,,\,\overline{(X_{1}-\mathbb{E}X_{1})^{\otimes
p_{1}}}\otimes\ldots\otimes\overline{(X_{k}-\mathbb{E}X_{1})^{\otimes
p_{k}}}\,\Big{\rangle}\bigg{\|}_{L_{\nu}},$ $\displaystyle\text{ and
}\beta_{m,\nu}\;\coloneqq\;\mfrac{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{m,\nu}(k))^{2}}{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{m,2}(k))^{2}}\;.$

$\epsilon_{m}$ is a variance ratio that is small when the $m$-th order term
dominates other terms of Taylor expansion in variance (Theorem 2; see Remark 3
for a further upper bound). $\beta_{m,\nu}$ is a V-statistic analogue of the
classical Berry-Esséen ratio from Lemma 7 (see Remark 2 for a further upper
bound). The next result gives finite-sample bounds both for approximating
$\hat{g}(X)$ by $\hat{g}_{m}^{(\mathbb{E}X_{1})}(Z)$ and by a Gaussian.

######  Proposition 8.

Assume that $g$ is $(m+1)$-times continuously differentiable and that
$\hat{g}^{(\mathbb{E}X_{1})}_{m}$ is $\delta$-regular (Definition 4) with
respect to $(X_{i}-\mathbb{E}X_{1})_{i\leq n}$ for some $\delta\in(0,1)$.
Then, there are some absolute constants $C,c>0$ such that for all
$n,m,d\in\mathbb{N}$ with $n\geq 2m^{2}$ and any $\nu\in(2,3]$, we have

$\displaystyle\sup\nolimits_{t\in\mathbb{R}}\big{|}\mathbb{P}\big{(}\hat{g}(X)-\operatorname{\medmath\sum}_{l=0}^{m}\mu_{l}\leq
t\big{)}-\mathbb{P}\big{(}\,\hat{g}_{m}^{(\mathbb{E}X_{1})}(Z)-\mathbb{E}\big{[}\hat{g}_{m}^{(\mathbb{E}X_{1})}(Z)\big{]}\leq
t\,\big{)}\big{|}\;\leq\;\Delta_{\hat{g},m}\;,$
$\displaystyle\qquad\text{where
}\quad\Delta_{\hat{g},m}\;\coloneqq\;C\Big{(}\epsilon_{m}^{\frac{1}{2m+1}}+n^{-\frac{1-\delta}{2m+1}}+n^{-\frac{\nu-2}{2\nu
m+2}}\,\beta_{m,\nu}^{\frac{\nu}{2\nu m+2}}\Big{)}\;.$

######  Remark.

(i) Proposition 8 considers only the case when one of the derivatives
dominates, but can be readily extended to the case when several terms dominate
at the same time: This is done by applying variance domination (Theorem 2) to
the appropriate dominating quantity. (ii) The second term of the normal
approximation bound comes from replacing the normalisation $\text{\rm
Var}\big{[}\hat{g}_{m}^{(\mathbb{E}X_{1})}(Z)\big{]}$ by $\text{\rm
Var}\big{[}\hat{g}_{m}^{(\mathbb{E}X_{1})}(X)\big{]}$.

######  Remark 3 (Upper bound on $\epsilon_{m}$).

Using a triangle inequality and a Jensen’s inequality, we can obtain a further
upper bound on the first term of $\epsilon_{m}$ as

$\displaystyle(m-1)\,\sum_{l=1}^{m-1}\mfrac{\text{\rm
Var}\Big{[}\hat{g}_{l}^{(\mathbb{E}X_{1})}(X)\Big{]}}{\text{\rm
Var}\Big{[}\hat{g}_{m}^{(\mathbb{E}X_{1})}(X)\Big{]}}\;.$

Each summand involves variances of V-statistics, whose upper and lower bounds
are given in Lemma 7. As discussed in Remarks 1 and 2, these variance ratios
can either be controlled by a further spectral bound or an explicit
computation. An analogous bound applies to the second term, provided that the
$(m+1)$-th derivative satisfies some stability condition: One example of such
a condition is the existence of some $\nu>2$ such that

$\displaystyle\Big{\|}\,\hat{g}_{m+1}^{(\mathbb{E}X_{1}+\Theta
S_{n})}(X)-\hat{g}_{m+1}^{(\mathbb{E}X_{1})}(X)\,\Big{\|}_{L_{\nu}}\;=\;o(1)\;.$

When $g$ is infinitely differentiable, Proposition 8 implies that the
asymptotic distribution of $\hat{g}(X)$ is determined by its $m$-th order
Taylor expansion for the smallest $m$ such that $\epsilon_{m}\rightarrow 0$,
i.e. the $m$-th order term that dominates in variance. As such, Proposition 8
strictly generalises the $m$-th order delta method by replacing the
requirement that all lower derivatives are zero with the condition that
$\epsilon_{m}=o(1)$, whereas the finite-sample bound introduces a second
condition $\beta_{m,\nu}=o(n^{(\nu-2)/2\nu})$ analogous to a Berry-Esséen
moment ratio. In the high-dimensional regime, Proposition 8 generalises the
observations in $g_{\rm toy}$ to show two aspects of delta method that depart
from classical behaviours:

  * •

_Non-Gaussianity despite a non-zero first derivative._ The approximation by a
degree-$m$ polynomial of Gaussians can dominate the first-order Gaussian term,
when the first derivative is negligible compared to some $m$-th derivative. We
do note that this polynomial of Gaussians may still be asymptotically
Gaussian, and the condition for Gaussianity can be characterised by the fourth
moment phenomenon [46, 43, 44] when $X_{i}$’s have isotropic covariance
matrices – see Remark 4.

  * •

_Non-consistency (under the plug-in principle)._ By the first bound of Theorem
2 and a Markov’s inequality, we see that if $\Delta_{\hat{g},m}=o(1)$ and
$\text{\rm Var}\big{[}\hat{g}_{m}^{(\mathbb{E}X_{1})}(Z)\big{]}=o(1)$, then

$\displaystyle\hat{g}(X)-\operatorname{\medmath\sum}_{l=0}^{m}\mu_{l}\;\xrightarrow{\mathbb{P}}\;0\;.$

Recall that under the plug-in principle, $\hat{g}(X)$ is intended as an
estimator for $g(\mathbb{E}X_{1})=\mu_{0}$. Since, by linearity,

$\displaystyle\mu_{1}\;=\;\mathbb{E}\big{[}\langle\partial
g(\mathbb{E}X_{1}),X_{1}-\mathbb{E}X_{1}\rangle\big{]}\;=\;0\;,$

$\hat{g}(X)$ is indeed consistent when Proposition 8 holds with $m=1$ (e.g. in
the classical case with non-zero first derivative). When $m>1$, however,
$\hat{g}(X)$ may be non-consistent, and the bias is exactly given by the limit
of $\sum_{l=2}^{m}\mu_{l}$.

######  Remark 4 (Asymptotic normality of a polynomial of Gaussians).

An additional subtlety is that in high dimensions, a degree-$m$ polynomial of
Gaussians may itself be asymptotically Gaussian: This can be seen from
$\hat{g}_{\rm toy}(X)$ with $X_{i}\sim\mathcal{N}(\mu,I_{d})$, whose second-
order term satisfies

$\displaystyle\mfrac{1}{n^{2}}\operatorname{\medmath\sum}_{i,j=1}^{n}\bar{X}_{i}^{\top}\bar{X}_{j}\;\overset{d}{=}\;\mfrac{d}{n}\times\mfrac{1}{d}\operatorname{\medmath\sum}_{j=1}^{d}\eta_{j}^{2}\qquad\text{
with }\eta_{j}\overset{i.i.d.}{\sim}\mathcal{N}(0,1)\;.$

This is an average of i.i.d. variables, and becomes asymptotically normal when
$d$ and $n$ both grow. More generally, this is related to the fourth moment
phenomenon [46, 43, 44], which states that a sequence of a symmetric
multilinear form of i.i.d. standard normal variables with fixed degree is
asymptotically Gaussian if and only if the excess kurtosis converges to zero.
In the case of Proposition 8, the asymptotic distribution of
$\hat{g}_{m}^{(\mathbb{E}X_{1})}(Z)$ is equivalent to a multilinear form of
Gaussians under $\delta$-regularity (Proposition 5), which is symmetric by
construction, so the fourth moment phenomenon applies when we additionally
require $\text{\rm Var}[X_{1}]=I_{d}$.

######  Remark.

Theorem 1 and Theorem 2 in fact apply to a more general version of delta
method on $g_{n}(T_{n})$, where we consider a sequence of random variables
$\\{T_{n}\\}_{n=1}^{\infty}$ determined by $X_{1},\ldots,X_{n}$ and a sequence
of well-behaved functions $\\{g_{n}\\}_{n=1}^{\infty}$. The only requirement
is a suitable Taylor approximation of the estimator, which yields the
polynomial structure. Degree-$m$ U-statistics, discussed next, give such an
example.

###  Degree-$m$ U-statistics

Let $Y_{1},\ldots,Y_{n}$ be i.i.d. random variables taking values in some
general (not necessarily Euclidean), possibly $n$-dependent measurable space
$\mathcal{E}\equiv\mathcal{E}(n)$. Given a symmetric function
$u:\mathcal{E}^{m}\rightarrow\mathbb{R}$, consider the degree-$m$ U-statistic
given by

$\displaystyle u_{m}(Y)\;\coloneqq$
$\displaystyle\;\mfrac{1}{n(n-1)\ldots(n-m+1)}\operatorname{\medmath\sum}_{i_{1},\ldots,i_{m}\in[n]\text{
\rm distinct }}u(Y_{i_{1}},\ldots,Y_{i_{m}})\;.$ (11)

Classically, under a technique called the Hájek projection, the asymptotic
distribution of $u_{m}(Y)$ can be approximated by that of a degree-$M$
polynomial of Gaussians, where

$\displaystyle
M\;\coloneqq\;\min\\{j\in[m]\,:\,\sigma_{j}>0\\}\;,\qquad\text{and
}\quad\sigma_{j}^{2}\coloneqq\text{\rm
Var}\,\mathbb{E}[u(Y_{1},\ldots,Y_{m})\,|\,Y_{1},\ldots,Y_{j}]\;.$

See [21], [50] and Chapter 5.4 of [52] for references on the classical theory
for U-statistics. In this section, we show how the high-dimensional
asymptotics of $u_{m}(Y)$, where $\mathcal{E}=\mathbb{R}^{d}$ with $m$ and $d$
allowed to be large relative to $n$, can again be obtained with our general
results.

We will invoke a functional decomposition assumption similar to the one used
in [32] to obtain finite-sample bounds. For each $K\in\mathbb{N}$, we consider
approximating $u(y_{1},\ldots,y_{m})$ by a polynomial of $m$ vectors in
$\mathbb{R}^{K}$,

$\displaystyle\operatorname{\medmath\sum}_{k_{1},\ldots,k_{m}=1}^{K}\lambda^{(K)}_{k_{1}\ldots
k_{m}}\phi^{(K)}_{k_{1}}(y_{1})\times\ldots\times\phi^{(K)}_{k_{m}}(y_{m})\;,$

where for each $K$, the $mK$ coordinates are defined via a triangular array of
$\mathcal{E}\rightarrow\mathbb{R}$ functions $\\{\phi^{(K)}_{k}\\}_{k\leq
K,K\in\mathbb{N}}$ evaluated at $y_{1},\ldots,y_{m}$, and the polynomial
weights are given by a triangular array of real values
$\\{\lambda^{(K)}_{k_{1}\ldots k_{m}}\\}_{k_{1},\ldots,k_{m}\leq
K,K\in\mathbb{N}}$. The $L_{\nu}$ approximation error is denoted as

$\displaystyle\varepsilon_{K;\nu}\;\coloneqq\;\big{\|}\operatorname{\medmath\sum}_{k_{1},\ldots,k_{m}=1}^{K}\lambda^{(K)}_{k_{1}\ldots
k_{m}}\phi^{(K)}_{k_{1}}(Y_{1})\times\ldots\times\phi^{(K)}_{k_{m}}(Y_{m})-u(Y_{1},\ldots,Y_{m})\big{\|}_{L_{\nu}}\;.$

######  Assumption 1.

There exists some $\nu\in(2,3]$ such that, for every fixed $n$, $m$, $d$ and
$\mathcal{E}$, as $K\rightarrow\infty$, the error
$\varepsilon_{K;\nu}\rightarrow 0$ for some choice of
$\\{\phi^{(K)}_{k}\\}_{k\leq K,K\in\mathbb{N}}$ and
$\\{\lambda^{(K)}_{k_{1}\ldots k_{m}}\\}_{k_{1},\ldots,k_{m}\leq
K,K\in\mathbb{N}}$.

######  Remark.

(i) 1 is very mild: In the appendix, we show how it holds with $\nu=2$ under
mild assumptions on the $L_{2}$ space equipped with the measure of $Y_{1}$
(Lemma 31), and how it holds for $\mathcal{E}=\mathbb{R}^{d}$ and any $u$
well-approximated by a Taylor expansion (Lemma 32). (ii) Unlike asymptotic
U-statistics results that use the $L_{2}$ decomposition from Hilbert-Schmidt
operator theory (see e.g. Chapter 5.4 of [52]), 1 does not require
orthogonality or boundedness conditions on $\phi^{(K)}_{k}$ or
$\lambda^{(K)}_{k_{1}\ldots k_{m}}$ and also allow them to vary with $K$ or
$n$. In particular, they are generally not unique and can be chosen at
convenience for verification of the assumption.

#### Penultimate approximation.

To identify the dominating component, we first recall that by Hoeffding’s
decomposition theorem (see e.g. Theorem 1.2.1 of [18]),

$\displaystyle
u_{m}(y_{1},\ldots,y_{n})\;=\;\mathbb{E}[u(Y_{1},\ldots,Y_{m})]\,+\,\operatorname{\medmath\sum}_{j=1}^{m}\mbinom{m}{j}\,U^{\rm
H}_{j}(y_{1},\ldots,y_{n})\;,$ (12)

where each Hoeffding’s decomposition $U^{\rm H}_{j}(Y)$ is a degenerate
degree-$j$ U-statistic defined by

$\displaystyle U^{\rm H}_{j}(y_{1},\ldots,y_{n})\;\coloneqq$
$\displaystyle\;\mfrac{1}{n(n-1)\ldots(n-j+1)}\operatorname{\medmath\sum}_{i_{1},\ldots,i_{j}\in[n]\text{
\rm distinct }}u^{\rm H}_{j}(y_{i_{1}},\ldots,y_{i_{j}})\;,$ $\displaystyle
u^{\rm H}_{j}(y_{1},\ldots,y_{j})\;\coloneqq$
$\displaystyle\;\operatorname{\medmath\sum}_{r=0}^{j}(-1)^{j-r}\operatorname{\medmath\sum}_{1\leq
l_{1}<\ldots<l_{r}\leq
j}\mathbb{E}\big{[}u(y_{l_{1}},\ldots,y_{l_{r}},Y_{1},\ldots,Y_{m-r})\big{]}\;.$

Under 1, each Hoeffding’s decomposition can be approximated by a polynomial of
$\mathbb{R}^{K}$ vectors, to which our universality results can be applied.
Let $\mu_{k}\coloneqq\mathbb{E}[\phi_{k}(Y_{1})]\in\mathbb{R}$ and
$\Xi^{(K)}\coloneqq\\{\xi^{(K)}_{1},\ldots,\xi^{(K)}_{n}\\}$ be a collection
of i.i.d. zero-mean Gaussian random vectors in $\mathbb{R}^{mK}$ with the same
variance as $(\phi^{(K)}_{1}(Y_{1}),\ldots,\phi^{(K)}_{K}(Y_{1}))^{\top}$. For
$j\in[m]$ and $K\in\mathbb{N}$, the penultimate approximation for $U^{\rm
H}_{j}(Y)$ is therefore given as a polynomial of $\mathbb{R}^{K}$ Gaussians,

$\displaystyle U^{(K)}_{j}(\Xi^{(K)})\;\coloneqq$
$\displaystyle\;\mfrac{1}{n(n-1)\ldots(n-j+1)}\operatorname{\medmath\sum}_{i_{1},\ldots,i_{j}\in[n]\text{
\rm distinct
}}\tilde{u}_{j}^{(K)}(\xi^{(K)}_{i_{1}},\ldots,\xi^{(K)}_{i_{j}})\;,$ (13)
$\displaystyle u^{(K)}_{j}(v_{1},\ldots,v_{j})\;\coloneqq$
$\displaystyle\;\operatorname{\medmath\sum}_{k_{1},\ldots,k_{m}=1}^{K}\,\lambda^{(K)}_{k_{1}\ldots
k_{m}}v_{1k_{1}}\cdots v_{jk_{j}}\,\mu_{k_{j+1}}\cdots\mu_{k_{m}}\;.$

#### Moments.

By variance domination, the asymptotic distribution of $u_{m}(Y)$ is
determined by the relative size of the rescaled variances, given for $M\in[m]$
as

$\displaystyle\rho_{m,n;M}\;$
$\displaystyle\coloneqq\;\mfrac{\sum_{r\in[m]\setminus
M}\sigma_{m,n;r}^{2}}{\sigma_{m,n;M}^{2}}\;,$ $\displaystyle\text{where
}\;\sigma_{m,n;j}^{2}\;\coloneqq\;\mbinom{m}{j}^{2}\mbinom{n}{j}^{-1}\text{\rm
Var}\,\mathbb{E}[u(Y_{1},\ldots,Y_{m})\,|\,Y_{1},\ldots,Y_{j}]\qquad\text{ for
}j\in[m]\;.$

$\sigma^{2}_{m,n;j}$ describes the contribution of $U^{\rm H}_{j}$ to the
overall variance of $u_{m}(Y)$ (Lemma 26). The bound also depends on a Berry-
Esséen moment ratio, given for $\nu\in(2,3]$ and $M\in[m]$ as

$\displaystyle\tilde{\beta}_{M,\nu}\;\coloneqq\;\mfrac{\big{\|}u_{M}^{\rm
H}\big{(}Y_{1},\ldots,Y_{M}\big{)}\big{\|}_{L_{\nu}}}{\big{\|}u_{M}^{\rm
H}\big{(}Y_{1},\ldots,Y_{M}\big{)}\big{\|}_{L_{2}}}\;.$

######  Proposition 9.

Suppose 1 holds for some $\nu\in(2,3]$. Then there is some absolute constant
$C>0$ such that for every $n,m,d\in\mathbb{N}$ and $M\in[m]$, we have

$\displaystyle\sup\nolimits_{t\in\mathbb{R}}\Big{|}\mathbb{P}\big{(}u_{m}(Y)-\mathbb{E}[u(Y_{1},\ldots,Y_{m})]\leq
t\big{)}-\lim_{K\rightarrow\infty}$
$\displaystyle\mathbb{P}\Big{(}\mbinom{m}{M}\,U_{M}^{(K)}(\Xi^{(K)})\leq
t\Big{)}\Big{|}$ $\displaystyle\;\leq\;C\Big{(}n^{-\frac{\nu-2}{2(\nu
M+1)}}\tilde{\beta}_{M,\nu}^{\frac{\nu}{\nu
M+1}}+\rho_{m,n;M}^{\frac{1}{2M+1}}\Big{)}\;.$

We emphasise that Proposition 9 allows the degree of the U-statistic $m$ to be
much larger than $\log n$: In the above bound, when
$\tilde{\beta}_{M,\nu}=O(1)$ and $\rho_{m,n;M}=o(1)$, we only require the
degree of the polynomial of Gaussians to satisfy $M=o(\log n)$, with no
explicit requirement on $m$. This allows Proposition 9 to recover many known
results on high-dimensional U-statistics. Similar to Proposition 8, there are
two cases under which a normal approximation is allowed, but with different
variances:

  1. (i)

When $M=1$, the distributional limit
$\lim_{K\rightarrow\infty}U_{1}^{(K)}(\Xi^{(K)})$, when exists, is Gaussian.
In this case, Proposition 9 provides a finite-sample bound for the Gaussian
approximation of $u_{m}(Y)$, a potentially infinite-order U-statistic (IOUS).
Notably if $\tilde{\beta}_{M,\nu}$ is bounded, the only dependence on $m$ in
the bound is through $\rho_{m,n;M}$; when $d$ is fixed and $\text{\rm
Var}\,\mathbb{E}[u(Y_{1},\ldots,Y_{m})\,|\,Y_{1},\ldots,Y_{j}]\in(0,\infty)$
is fixed for all $j\in[m]$, we can compute

$\displaystyle\rho_{m,n;1}\;=\;\Theta\Big{(}m\,\Big{(}\mfrac{m^{2}}{n^{-1}}\Big{)}^{m}\Big{)}\;.$

Therefore when $d$ is fixed and $M=1$, Gaussianity holds if $m=o(n^{-1/2})$.
This agrees with known optimal growth condition on $m$ for Gaussianity of 1d
IOUS [57]. On the other hand, when $d$ and the variances are allowed to
change, $\rho_{m,n;1}$ has more complex dependence on $n$; this can lead to a
more stringent or relaxed condition on the size of $m$.

  2. (ii)

When $M>1$, $U_{M}^{(K)}(\Xi^{(K)})$ is a degree-$M$ polynomial of Gaussians.
Since the approximating polynomial of Gaussians is allowed to vary in $n$, the
resultant approximation may still be Gaussian in view of the fourth moment
phenomenon [46, 43, 44] (see Remark 4).

The above two cases recover many existing works on the normal approximation of
a high-dimensional degree-two U-statistic: Some of those results come without
a fourth-moment condition and require assumptions similar to those for (i)
[13, 29, 60, 62], whereas others consider a fourth moment condition and fall
under (ii) [22, 5]. A practical consequence of (ii) is that a degenerate
U-statistic – often found in hypothesis testing and which requires numerical
approximation due to its classical non-Gaussianity [38] – may be Gaussian in
high dimensions.

Meanwhile, as with Proposition 8, Proposition 9 highlights when $u_{m}(Y)$ may
be asymptotically non-Gaussian. Here, non-Gaussianity happens not according to
the degeneracy of the U-statistic, but depending on the relative sizes of the
rescaled variances $\sigma_{m,n;j}^{2}$. This has been highlighted in the
literature for specific statistics [5, 32]. We also refer readers to [32] for
empirical evidence of the transition of a $U$-statistic between different
limits in high dimensions: There, variance domination reduces to problem-
specific hyperparameter choices.

######  Remark.

The same argument in this section can be extended to a U-statistic of non-
identically distributed data, although a more elaborate decomposition than
(12) is required to accommodate for the fact that
$\mathbb{E}[u(y_{1},\ldots,y_{r},Y_{1},\ldots,Y_{m-r})]$ may not be equal to
$\mathbb{E}[u(y_{1},\ldots,y_{r},Y_{2},\ldots,Y_{m-r+1})]$. Section 3.3
illustrates such an example.

###  Higher-order fluctuations of subgraph counts

We apply our results to characterise the possible asymptotic distributions of
subgraph counts. We shall see that variance domination recovers and extends
the geometric conditions considered by Hladkỳ et al. [30] and Bhattacharya et
al. [4] for obtaining different limits, and our results also apply to the
edge-level fluctuations considered by Kaur and Röllin [34].

For a symmetric, measurable graphon function $w:[0,1]^{2}\rightarrow[0,1]$, we
generate a random graph $G_{n}$ with vertex set $[n]$ by drawing independent
(not necessarily identically distributed) random variables $(U_{i})_{i\leq n}$
and $(V_{ij})_{1\leq i<j\leq n}$, and joining an edge $i\sim j$ whenever
$V_{ij}\leq w(U_{i},U_{j})$. Note that when
$U_{i},V_{ij}\overset{i.i.d.}{\sim}\textrm{Uniform}[0,1]$, this corresponds to
joining the vertices $i$ and $j$ with probability $w(U_{i},U_{j})$
independently for all $1\leq i<j\leq n$. We denote

$Y_{ij}\;\coloneqq\;\mathbb{I}_{\\{V_{ij}\leq w(U_{i},U_{j})\\}}$

as the edge indicator variables, $K(S)$ as the complete graph on the vertex
set $S\subseteq[n]$, and $E(H^{\prime})$ as the edge set of a graph
$H^{\prime}$. Given a non-empty simple graph $H$ with $m=m(n)$ number of
vertices and $k=k(n)$ number of edges, we are interested in the number of
subgraphs in $G_{n}$ that are isomorphic to $H$, described by the subgraph
count statistic

$\displaystyle\kappa(Y)\;\coloneqq\;\operatorname{\medmath\sum}_{1\leq
i_{1}<\ldots<i_{m}\leq
n}\;\operatorname{\medmath\sum}_{H^{\prime}\subseteq\mathcal{G}_{H}(\\{i_{1},\ldots,i_{m}\\})}\;\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H^{\prime})}Y_{i_{s}i_{t}}\,,$

where $\mathcal{G}_{H}(S)$ denotes the collection of all subgraphs of $K(S)$
that are isomorphic to $H$.

To derive the asymptotic limit, we first consider the conditionally centred
indicator variable $\bar{Y}_{ij}\coloneqq Y_{ij}-w(U_{i},U_{j})$. By
expressing the above sum as a sum over edges, we have

$\displaystyle\kappa(Y)\;=$ $\displaystyle\;\operatorname{\medmath\sum}_{1\leq
i_{1}<\ldots<i_{m}\leq
n}\;\operatorname{\medmath\sum}_{H^{\prime}\subseteq\mathcal{G}_{H}(\\{i_{1},\ldots,i_{m}\\})}\;\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H^{\prime})}w(U_{i_{s}},U_{i_{t}})$
$\displaystyle\;+\operatorname{\medmath\sum}_{\begin{subarray}{c}\\{(i_{1},j_{1}),\ldots,(i_{k},j_{k})\\}\subseteq
E(K_{n})\\\ \text{is a set of distinct
edges}\end{subarray}}\;\delta_{H}\big{(}\\{(i_{s},j_{s})\\}_{s\in[k]}\big{)}\,\operatorname{\medmath\prod}_{s=1}^{k}\bar{Y}_{i_{s}j_{s}}\;\eqqcolon\;\kappa_{1}(U)+\kappa_{2}(\bar{Y})\;,$

where $\delta_{H}(I)$ is the indicator function on whether the graph formed by
the edge set $I$ is isomorphic to $H$. $\kappa_{1}(U)$ represents vertex-level
fluctuations, and $\kappa_{2}(\bar{Y})$ represents edge-level fluctuations.
There are two cases depending on which term dominates in variance:

Case 1: Vertex-level fluctuations. Let $(U_{i})_{i\leq n}$ be i.i.d. for
notational simplicity. $\kappa_{1}(U)$ is now an (unnormalised) degree-$m$
U-statistic of i.i.d. variables with the kernel

$\displaystyle
u_{1}(x_{1},\ldots,x_{m})\;\coloneqq\;\operatorname{\medmath\sum}_{H^{\prime}\subseteq\mathcal{G}_{H}(\\{1,\ldots,m\\})}\;\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H^{\prime})}w(x_{i_{s}},x_{i_{t}})\;.$

By applying Proposition 9 to $\binom{n}{m}^{-1}\kappa_{1}$ and
$U\coloneqq(U_{i})_{i\leq n}$, we obtain the error of approximating
$\kappa(Y)$ by a degree-$M$ polynomial of Gaussians, which corresponds to the
$M$-th Hoeffding decomposition of $\kappa_{1}(Y)$. The variance of this
approximation can be computed as

$\displaystyle\sigma_{m,n;M}^{2}$
$\displaystyle\;\coloneqq\;\mbinom{m}{M}^{2}\mbinom{n}{M}^{-1}\text{\rm
Var}\,\mathbb{E}[u_{1}(U)\,|\,U_{1},\ldots,U_{M}]$ $\displaystyle\;=$
$\displaystyle\;\mbinom{m}{M}^{2}\mbinom{n}{M}^{-1}\text{\rm
Var}\,\mathbb{E}\Big{[}\operatorname{\medmath\sum}_{H^{\prime}\subseteq\mathcal{G}_{H}(\\{1,\ldots,m\\})}\;\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H^{\prime})}w(U_{i_{s}},U_{i_{t}})\,\Big{|}\,U_{1},\ldots,U_{M}\Big{]}\;.$

A guiding example is when $H=K_{2}$, i.e. $\kappa(Y)$ is the edge count: In
this case, the variances of the Gaussian component and the quadratic-form-of-
Gaussian component are respectively

$\displaystyle\sigma_{m,n;1}^{2}\;=$ $\displaystyle\;\mfrac{4}{n}\text{\rm
Var}\,\mathbb{E}[w(U_{1},U_{2})|U_{1}]$ and
$\displaystyle\sigma_{m,n;2}^{2}\;=$
$\displaystyle\;\mfrac{2}{n(n-1)}\text{\rm Var}[w(U_{1},U_{2})]\;,$

which determine the asymptotic distribution of $\kappa(Y)$.

Consider the setup where $w$ and $H$ are fixed. Note that $\sqrt{\text{\rm
Var}[\tilde{U}_{M}^{(K)}(\Xi^{(K)})]}=O(n^{-\frac{M}{2}})$ (Lemma 26): When
the approximation by the $M$-th Hoeffding decomposition holds, this
corresponds to what is known in the literature as an $n^{m-\frac{M}{2}}$-order
fluctuation in $\kappa(Y)$ [34]. Since $\sigma^{2}_{m,n;j}=O(n^{-j})$ for all
$j\in[m]$, the Gaussian approximation ($M=1$) holds unless
$\sigma^{2}_{m,n;1}=0$, which happens if and only if

$\displaystyle\operatorname{\medmath\sum}_{H^{\prime}\subseteq\mathcal{G}_{H}(\\{1,\ldots,m\\})}\;\mathbb{E}\Big{[}\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H^{\prime})}w(U_{i_{s}},U_{i_{t}})\,\Big{|}\,U_{1}\Big{]}\;\text{ is
constant almost surely }.$ (14)

In the case of $H=K_{2}$, this condition reads

$\displaystyle\mathbb{E}[w(U_{1},U_{2})\,|\,U_{1}]\;\text{ is constant almost
surely },$

i.e. the expected degree of a given vertex is constant. Compare (14) to
Theorem 1.2 of [30] and Theorem 2.9 of [4]: Those results state that the limit
of $\kappa(Y)$ may be Gaussian on the order $n^{m-\frac{1}{2}}$, or a Gaussian
plus an independent sum of weighted and centred chi-squares on the order
$n^{m-1}$, depending on an $H$-regularity condition: $w$ is $H$-regular if,
for almost every $x\in[0,1]$,

$\displaystyle\mfrac{1}{m}\operatorname{\medmath\sum}_{i=1}^{m}\;\mathbb{E}\Big{[}\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H)}w(U_{i_{s}},U_{i_{t}})\,\Big{|}\,U_{i}=x\Big{]}\;=\;\mathbb{E}\Big{[}\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H)}w(U_{i_{s}},U_{i_{t}})\Big{]}\;.$ (15)

As remarked by (2.11) of [4], (15) is equivalent to requiring LHS of (15) to
be constant for almost every $x\in[0,1]$, which is in turn equivalent to our
condition in (14). Indeed, in the case of $H=K_{2}$, (14) requires the random
graph to be regular on average.

In summary, using $H$-regularity to distinguish order-$n^{m-\frac{1}{2}}$ and
$n^{m-1}$ fluctuations [30, 4] is equivalent to using variance domination to
distinguish approximations by Hoeffding decompositions with $M=1$ versus
$M=2$. Meanwhile, variance domination provides more: We can now characterise
all fluctuations in $\kappa_{1}(U)$ on the orders
$n^{m-\frac{1}{2}},n^{m-1},\ldots,n^{\frac{m}{2}}$, all with finite-sample
bounds. We may also study a “high-dimensional” setup, where $w$ and $H$ are
allowed to vary in $n$.

#### Vertex-level fluctuations usually dominate edge-level fluctuations.

All arguments above assume that $\text{\rm Var}[\kappa_{2}(\bar{Y})]$ is
negligible, which we now investigate. For convenience, we re-index
$(\bar{Y}_{ij})_{i,j\in E(K_{n})}$ as $\bar{Y}_{1},\ldots,\bar{Y}_{n_{*}}$,
where $n_{*}=|E(K_{n})|=\binom{n}{2}$.

######  Lemma 10.

There are some absolute constants $c,C>0$ such that

$\displaystyle\text{\rm Var}[\kappa_{2}(\bar{Y})]\;\leq$
$\displaystyle\;C^{k}\,|\mathcal{G}_{H}([n])|\;\mathbb{E}\Big{[}\max\nolimits_{i_{1},\ldots,i_{k}\in[n_{*}]\text{
distinct}}\,\operatorname{\medmath\prod}_{l=1}^{k}\text{\rm
Var}[\bar{Y}_{i_{l}}\,|\,U]\Big{]}\;,$ $\displaystyle\text{\rm
Var}[\kappa_{2}(\bar{Y})]\;\geq$
$\displaystyle\;c^{k}\,|\mathcal{G}_{H}([n])|\;\mathbb{E}\Big{[}\min\nolimits_{i_{1},\ldots,i_{k}\in[n_{*}]\text{
distinct}}\,\operatorname{\medmath\prod}_{l=1}^{k}\text{\rm
Var}[\bar{Y}_{i_{l}}\,|\,U]\Big{]}\;.$

Consider again the setup with $w$ and $H$ fixed. Let $\rm{Aut}(H)$ be the set
of all automorphisms of $H$. Provided that the expectations in Lemma 10 are
$\Theta(1)$, we have

$\displaystyle\mbinom{n}{m}^{-2}\text{\rm
Var}[\kappa_{2}(\bar{Y})]\;=\;\Theta\Big{(}\mbinom{n}{m}^{-2}|\mathcal{G}_{H}([n])|\Big{)}\;=\;\Theta\Big{(}\mbinom{n}{m}^{-1}\,\mfrac{m!}{|\rm{Aut}(H)|}\Big{)}\;=\;\Theta(n^{-m})\;.$

Under variance domination, this is to be compared to

$\displaystyle\sigma_{m,n;M}^{2}=\mbinom{m}{M}^{2}\mbinom{n}{M}^{-1}\text{\rm
Var}\,\mathbb{E}\Big{[}\operatorname{\medmath\sum}_{H^{\prime}\subseteq\mathcal{G}_{H}(\\{1,\ldots,m\\})}\;\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H^{\prime})}w(U_{i_{s}},U_{i_{t}})\,\Big{|}\,U_{1},\ldots,U_{M}\Big{]}.$

When the $M$-th Hoeffding’s decomposition is a valid penultimate
approximation, $\sigma_{m,n;M}$ is assumed to be non-zero, and therefore

$\sigma_{m,n;M}^{2}\;=\;\Theta(n^{-M})\;.$

As a result, $\kappa_{1}(Y)$ always dominates $\kappa_{2}(Y)$ in variance when
$M<m$. This agrees with the observation in [34], who provide a detailed
illustration for simple subgraphs.

Case 2: Edge-level fluctuations. Consider again the degree-$M$ polynomial-of-
Gaussian approximation of the vertex-level fluctuations in Case 1. When $M=m$
or when $w$ and $H$ are allowed to vary in $n$, $\kappa_{2}(\bar{Y})$ is no
longer guaranteed to be negligible. Moreover, as argued by [34] and as evident
from the above analysis, focusing only on $\kappa_{1}(U)$ means ignoring edge
randomness, which is not helpful if e.g. one wants to perform statistical
tests on the edge properties of the random graph. [34] proves a Gaussian limit
for $\kappa_{2}(\bar{Y})$ by using the orthogonal decomposition of a
generalised U-statistic of $U$ and $V$ proposed by [33]. We consider a variant
of their setting by conditioning on $U=(U_{i})_{i\leq n}$: This fixes
$\kappa_{1}(U)$, whereas $\kappa_{2}(\bar{Y})$ is an incomplete U-statistic —
where the asymmetry arises from $\delta_{H}$ — and involves independent but
non-identically distributed variables $(\bar{Y}_{i})_{i\leq n_{*}}$. As our
results can handle asymmetric estimators and non-identically distributed data,
we may obtain a polynomial-of-Gaussian approximation for $\kappa_{2}(\bar{Y})$
by slightly modifying the proof of Proposition 9. Let $Z=(Z_{i})_{i\leq
n_{*}}$ be conditionally normal variables defined by

$\displaystyle
Z_{i}\,|\,U\;\;\overset{i.i.d.}{\sim}\;\;\mathcal{N}\big{(}\mathbb{E}[\bar{Y}_{i}\,|\,U]\,,\,\text{\rm
Var}[\bar{Y}_{i}\,|\,U]\big{)}\;.$

The penultimate approximation for $\kappa_{2}(\bar{Y})$ is the incomplete
U-statistic

$\displaystyle\kappa_{2}(Z)\;=\;\operatorname{\medmath\sum}_{\begin{subarray}{c}\\{(i_{1},j_{1}),\ldots,(i_{k},j_{k})\\}\subseteq
E(K_{n})\\\ \text{is a set of distinct
edges}\end{subarray}}\;\delta_{H}\big{(}\\{(i_{s},j_{s})\\}_{s\in[k]}\big{)}\,\operatorname{\medmath\prod}_{s=1}^{k}Z_{i_{s}j_{s}}\;,$

######  Proposition 11.

Assume that $\text{\rm Var}[\kappa_{2}(Z)\,|\,U]>0$ almost surely. Then there
exist some absolute constant $C>0$ such that for every $n\geq 2$ and
$m,k\in\mathbb{N}$, almost surely,

$\displaystyle\sup_{t\in\mathbb{R}}\Big{|}\mathbb{P}\big{(}\kappa(Y)-\mathbb{E}[\kappa(Y)|U]$
$\displaystyle\leq t\,\big{|}\,U\big{)}-\mathbb{P}\big{(}\kappa_{2}(Z)\leq
t\,\big{|}\,U\big{)}\Big{|}\;\leq\;C\,n^{-\frac{\nu-2}{\nu
k+1}}\,\rho_{\bar{Y}}(U)^{\frac{1}{\nu k+1}}\;,$ $\displaystyle\text{ where
}\;\;\rho_{\bar{Y}}(U)\;\coloneqq\;\mfrac{\max\nolimits_{i_{1},\ldots,i_{k}\in[n_{*}]\text{
distinct}}\,\operatorname{\medmath\prod}_{l=1}^{k}\mathbb{E}\big{[}\big{|}\bar{Y}_{i_{l}}\big{|}^{\nu}\,\big{|}\,U\big{]}}{\min\nolimits_{i_{1},\ldots,i_{k^{\prime}}\in[n_{*}]\text{
distinct}}\,\operatorname{\medmath\prod}_{l=1}^{k^{\prime}}\mathbb{E}\big{[}\big{|}\bar{Y}_{i_{l}}\big{|}^{2}\,\big{|}\,U\big{]}^{\nu/2}}\;.$

######  Remark 5.

The max-min ratio $\rho_{\bar{Y}}$ can be avoided by directly using the error
bound from Theorem 1: In exchange, the bound is given as a sum of non-
identical moment terms and the convergence rate cannot be read off directly.
This tradeoff is common for asymmetric estimators and non-identically
distributed data, although simplifications may be possible for specific
statistics.

Discussion: A full characterisation of $\kappa(Y)$. Our results can be used to
provide a complete characterisation of the possible asymptotics of $\kappa(Y)$
when $(U_{i})_{i\leq n}$ and $(V_{ij})_{1\leq i<j\leq n}$ are only required to
be independent. By considering the kernel

$\displaystyle u_{*}((x_{i})_{i\leq m},(v_{ij})_{1\leq i<j\leq
m})\;\coloneqq\;\operatorname{\medmath\sum}_{H^{\prime}\subseteq\mathcal{G}_{H}([m])}\;\operatorname{\medmath\prod}_{(i_{s},i_{t})\in
E(H^{\prime})}\mathbb{I}_{\\{v_{ij}\leq w(x_{i},x_{j})\\}}\;,$

we can express $\kappa(Y)$ in the form of the generalised U-statistic studied
by Janson and Nowicki [33]. The general strategy then consists of

  1. (i)

Extend 1 to accommodate the structure of this generalised U-statistic, and
assume that $u_{*}((U_{i_{l}})_{l\leq m},(V_{i_{l_{1}}j_{l_{2}}})_{1\leq
l_{1}<l_{2}\leq m})$ can be approximated by some multilinear form of feature
maps of each $U_{i_{l}}$ and $V_{i_{l_{1}}j_{l_{2}}}$ in $L_{\nu}$ for some
$\nu\in(2,3]$;

  2. (ii)

Centre each feature map to obtain a generalised form of Hoeffding’s
decomposition (12).

In fact, the orthogonal decomposition proposed by [33] is exactly (i) with
$\nu=2$ with i.i.d. $U_{i}$’s and i.i.d. $V_{ij}$’s: This is analogous to how
1 for degree-two polynomials is motivated by the $L_{2}$ decomposition of a
Hilbert-Schmidt operator used for studying a degenerate degree-two
U-statistic. The structure of $u_{*}$ will allow the decompositions in (ii) to
be interpreted as projections onto different subgraphs of $H$. Penultimate
approximations can then be obtained via Theorem 1 and Theorem 2 with finite-
sample guarantees.

Some difficulties persist in the most general case: (i) Due to asymmetry and
non-identically distributed data, the bounds can be loose or not immediately
interpretable, as discussed in Remark 5; (ii) Even if a penultimate
approximation is established, the limiting distribution for an asymmetric
polynomial of Gaussians is highly dependent on the weights and may not be
immediately obvious. An interesting future direction is to combine the general
results we develop with application-specific analysis: Bounds may greatly
simplify under specific random graph models, and different penultimate
approximations can yield natural graph-based interpretations, as already
established in [30, 34, 4].

##  Proof of Theorem 1

The proof idea is standard: We first compare the distributions on a class of
smooth functions via Lindeberg’s principle (e.g. Chapter 9 of [58]). The
smooth function bound is then combined with the Carbery-Wright inequality
[10], an anti-concentration bound for a polynomial of Gaussians, to obtain the
bound in the Kolmogorov metric. In this section, we also include several
lemmas that will simplify subsequent proofs.

We use a smooth approximation of an indicator for bounding the probability of
a given event; see a standard usage in e.g. the proof of Theorem 3.3 in [12].

######  Lemma 12 (Lemma 34 of [32]).

Fix any $m\in\mathbb{N}\cup\\{0\\}$ and $\tau,\delta\in\mathbb{R}$. Then there
exists an $m$-times differentiable $\mathbb{R}\rightarrow\mathbb{R}$ function
$h_{m;\tau;\delta}$ such that
$h_{m;\tau+\delta;\delta}(x)\;\leq\;\mathbb{I}_{\\{x>\tau\\}}\leq
h_{m;\tau;\delta}(x)$. For $0\leq r\leq m$, the $r$-th derivative
$h^{(r)}_{m;\tau;\delta}$ is continuous and bounded above by $\delta^{-r}$.
Moreover, for every $\epsilon\in[0,1]$, $h^{(m)}$ satisfies that

$\displaystyle|h^{(m)}_{m;\tau;\delta}(x)-h^{(m)}_{m;\tau;\delta}(y)|\;\leq\;C_{m,\epsilon}\,\delta^{-(m+\epsilon)}\,|x-y|^{\epsilon}\;,$

with respect to the constant $C_{m,\epsilon}=\binom{m}{\lfloor
m/2\rfloor}(m+1)^{m+\epsilon}$.

The next result allows us to control the difference in expectation of the
above approximation functions evaluated at independent random quantities:

######  Lemma 13.

Fix $t\in\mathbb{R}$, $\delta>0$ and define $h_{t;\delta}\equiv
h_{2;t;\delta}$ as in Lemma 12. Let $\mathbf{V},\mathbf{Z},\mathbf{W}$ be some
random vectors in $\mathbb{R}^{b}$ and $Y$ be a random variable in
$\mathbb{R}$, with dependence allowed. Then there exists an absolute constant
$C$ such that for any $\nu\in(2,3]$ and $\delta>0$, we have

$\displaystyle|\mathbb{E}[h_{t;\delta}(\mathbf{W}^{\top}\mathbf{V}+Y)-h_{t;\delta}(\mathbf{W}^{\top}\mathbf{Z}+Y)]|\;\leq\;Q_{1}+Q_{2}+Q_{3}\;,$

where

$\displaystyle Q_{1}\;\coloneqq$
$\displaystyle\;\big{|}\mathbb{E}\big{[}h^{\prime}_{t;\delta}(Y)\,\mathbf{W}^{\top}(\mathbf{V}-\mathbf{Z})\big{]}\big{|}\;,\quad\quad
Q_{2}\;\coloneqq\;\mfrac{1}{2}\,\big{|}\mathbb{E}\big{[}h^{\prime\prime}_{t;\delta}(Y)\,\big{(}\mathbf{W}^{\top}\,\big{(}\mathbf{V}\mathbf{V}^{\top}-\mathbf{Z}\mathbf{Z}^{\top}\big{)}\,\mathbf{W}\big{)}\big{]}\big{|}\;,$
$\displaystyle Q_{3}\;\coloneqq$
$\displaystyle\;54\delta^{-\nu}(\|\mathbf{W}^{\top}\mathbf{V}\|_{L_{\nu}}^{\nu}+\|\mathbf{W}^{\top}\mathbf{Z}\|_{L_{\nu}}^{\nu})\;.$

Assume additionally that $(\mathbf{V},\mathbf{Z})$ is independent of
$(\mathbf{W},Y)$. If $\mathbb{E}[\mathbf{V}]=\mathbb{E}[\mathbf{Z}]$, then
$Q_{1}=0$. If $\text{\rm Var}[\mathbf{V}]=\text{\rm Var}[\mathbf{Z}]$, then
$Q_{2}=0$.

###### Proof of Lemma 13.

Since $h_{t;\delta}$ is twice continuously differentiable, by a second-order
Taylor expansion with the integral remainder, we get that for any
$w,r\in\mathbb{R}$,

$\displaystyle h_{t;\delta}(u)\;=$
$\displaystyle\;h_{t;\delta}(r)+h^{\prime}_{t;\delta}(r)\,(u-r)+\operatorname{\scaleobj{.8}{\int}}_{r}^{u}h^{\prime\prime}_{t;\delta}(t)\,(u-t)\,d$
$\displaystyle\;=$
$\displaystyle\;h_{t;\delta}(r)+h^{\prime}_{t;\delta}(r)\,(u-r)+\operatorname{\scaleobj{.8}{\int}}_{0}^{1}h^{\prime\prime}_{t;\delta}\big{(}(u-r)\theta+r\big{)}\,(u-r)^{2}(1-\theta)\,d\theta$
$\displaystyle\;=$
$\displaystyle\;h_{t;\delta}(r)+h^{\prime}_{t;\delta}(r)\,(u-r)+\mathbb{E}\Big{[}h^{\prime\prime}_{t;\delta}\big{(}(u-r)\Theta+r\big{)}\,(u-r)^{2}(1-\Theta)\Big{]}\;,$
(16)

where $\Theta\sim\textrm{Uniform}[0,1]$. By applying this expansion once with
$u=\mathbf{W}^{\top}\mathbf{V}+Y,r=Y$ and once with
$u=\mathbf{W}^{\top}\mathbf{Z}+Y,r=Y$, we get that

$\displaystyle\big{|}\mathbb{E}$
$\displaystyle\big{[}h_{t;\delta}(\mathbf{W}^{\top}\mathbf{V}+Y)-h_{t;\delta}(\mathbf{W}^{\top}\mathbf{Z}+Y)\big{]}\big{|}$
$\displaystyle\;=$
$\displaystyle\;\Big{|}\mathbb{E}\Big{[}h^{\prime}_{t;\delta}(Y)\,(\mathbf{W}^{\top}\mathbf{V})-h^{\prime}_{t;\delta}(Y)\,(\mathbf{W}^{\top}\mathbf{Z})+h^{\prime\prime}_{t;\delta}\big{(}\Theta\mathbf{W}^{\top}\mathbf{V}+Y\big{)}\,(\mathbf{W}^{\top}\mathbf{V})^{2}(1-\Theta)$
$\displaystyle\;\;\;\;\;\;\;-h^{\prime\prime}_{t;\delta}\big{(}\Theta\mathbf{W}^{\top}\mathbf{Z}+Y\big{)}\,(\mathbf{W}^{\top}\mathbf{Z})^{2}(1-\Theta)\Big{]}\Big{|}\;.$

By adding and subtracting two second derivative terms evaluated at $t$, we can
further obtain

$\displaystyle\big{|}\mathbb{E}\big{[}h_{t;\delta}$
$\displaystyle(\mathbf{W}^{\top}\mathbf{V}+Y)-h_{t;\delta}(\mathbf{W}^{\top}\mathbf{Z}+Y)\big{]}\big{|}$
$\displaystyle\;=$
$\displaystyle\;\Big{|}\mathbb{E}\big{[}h^{\prime}_{t;\delta}(Y)\,\mathbf{W}^{\top}(\mathbf{V}-\mathbf{Z})\big{]}+\mathbb{E}\big{[}h^{\prime\prime}_{t;\delta}(Y)\,\big{(}(\mathbf{W}^{\top}\mathbf{V})^{2}-(\mathbf{W}^{\top}\mathbf{Z})^{2}\big{)}(1-\Theta)\big{]}$
$\displaystyle\;\,+\mathbb{E}\big{[}\big{(}h^{\prime\prime}_{t;\delta}\big{(}\Theta\mathbf{W}^{\top}\mathbf{V}+Y\big{)}-h^{\prime\prime}_{t;\delta}(Y)\big{)}\,(\mathbf{W}^{\top}\mathbf{V})^{2}(1-\Theta)\big{]}$
$\displaystyle\;\,-\mathbb{E}\big{[}\big{(}h^{\prime\prime}_{t;\delta}\big{(}\Theta\mathbf{W}^{\top}\mathbf{Z}+Y\big{)}-h^{\prime\prime}_{t;\delta}(Y)\big{)}\,(\mathbf{W}^{\top}\mathbf{Z})^{2}(1-\Theta)\big{]}\Big{|}$
$\displaystyle\;\eqqcolon$
$\displaystyle\;|Q_{1}+Q_{2}+Q_{V}-Q_{Z}|\;\leq\;|Q_{1}|+|Q_{2}|+|Q_{V}|+|Q_{Z}|\;.$
(17)

We handle the four terms individually. $Q_{1}$ is already in the desired form.
$Q_{2}$ can be simplified by noting that $\Theta$ is independent of all other
variables:

$\displaystyle
Q_{2}\;=\;\mfrac{1}{2}\,\mathbb{E}\big{[}h^{\prime\prime}_{t;\delta}(Y)\,\big{(}\mathbf{W}^{\top}\,\big{(}\mathbf{V}\mathbf{V}^{\top}-\mathbf{Z}\mathbf{Z}^{\top}\big{)}\,\mathbf{W}\big{)}\big{]}\;.$

Now to handle $Q_{V}$ and $Q_{Z}$, we use a Jensen’s inequality to move the
absolute sign inside the expectation and note that $1-\Theta$ is bounded in
norm by $1$:

$\displaystyle|Q_{V}|\;=$
$\displaystyle\;\big{|}\mathbb{E}\big{[}\big{(}h^{\prime\prime}_{t;\delta}\big{(}\Theta\mathbf{W}^{\top}\mathbf{V}+Y\big{)}-h^{\prime\prime}_{t;\delta}(Y)\big{)}\,(\mathbf{W}^{\top}\mathbf{V})^{2}(1-\Theta)\big{]}\big{|}$
$\displaystyle\;\leq$
$\displaystyle\;\mathbb{E}\big{[}\big{|}h^{\prime\prime}_{t;\delta}\big{(}\Theta\mathbf{W}^{\top}\mathbf{V}+Y\big{)}-h^{\prime\prime}_{t;\delta}(Y)\big{|}\times\big{(}\mathbf{W}^{\top}\mathbf{V}\big{)}^{2}\big{]}\;.$

Recall the Hölder property of $h^{\prime\prime}_{t;\delta}$ from Lemma 12: For
any $\epsilon\in[0,1]$ and $x,y\in\mathbb{R}$, we have

$\displaystyle\big{|}h^{\prime\prime}_{t;\delta}(x)-h^{\prime\prime}_{t;\delta}(y)\big{|}\;\leq$
$\displaystyle\;54\delta^{-2-\epsilon}\,|x-y|^{\epsilon}\,\;,$

Applying this to the bound above with $\epsilon=\nu-2\in(0,1]$,
$x=\Theta\mathbf{W}^{\top}\mathbf{V}+Y$ and $y=Y$, while noting that
$|\Theta|$ is bounded above by $1$ almost surely, we get that

$\displaystyle|Q_{V}|\;\leq$
$\displaystyle\;54\,\delta^{-\nu}\mathbb{E}\big{[}|\Theta\mathbf{W}^{\top}\mathbf{V}|^{\nu-2}\,(\mathbf{W}^{\top}\mathbf{V})^{2}\big{]}\;\leq\;54\,\delta^{-\nu}\,\big{\|}\mathbf{W}^{\top}\mathbf{V}\big{\|}_{L_{\nu}}^{\nu}\;.$

To deal with $Q_{Z}$, the argument is the same except $\mathbf{V}$ is replaced
by $\mathbf{Z}$:

$\displaystyle|Q_{Z}|\;\leq\;54\,\delta^{-\nu}\,\big{\|}\mathbf{W}^{\top}\mathbf{Z}\big{\|}_{L_{\nu}}^{\nu}\;.$

Applying the bounds to (17) then gives the first desired bound:

$\displaystyle\big{|}\mathbb{E}\big{[}h_{t;\delta}(\mathbf{W}^{\top}\mathbf{V}+Y)$
$\displaystyle-
h_{t;\delta}(\mathbf{W}^{\top}\mathbf{Z}+Y)\big{]}\big{|}\leq|Q_{1}|+|Q_{2}|+54\,\delta^{-\nu}\big{(}\big{\|}\mathbf{W}^{\top}\mathbf{V}\big{\|}_{L_{\nu}}^{\nu}+\big{\|}\mathbf{W}^{\top}\mathbf{Z}\big{\|}_{L_{\nu}}^{\nu}\big{)}\;.$

In the case where $\mathbb{E}[\mathbf{V}]=\mathbb{E}[\mathbf{Z}]$ and
$(\mathbf{V},\mathbf{Z})$ is independent of $(\mathbf{W},Y)$, we get that

$\displaystyle Q_{1}\;=$
$\displaystyle\;\mathbb{E}\big{[}h^{\prime}_{t;\delta}(Y)\,\mathbf{W}^{\top}(\mathbf{V}-\mathbf{Z})\big{]}\;=\;\mathbb{E}\big{[}h^{\prime}_{t;\delta}(Y)\,\mathbf{W}^{\top}\mathbb{E}[\mathbf{V}-\mathbf{Z}]\big{]}\;=\;0\;.$

Similarly in the case where $\text{\rm Var}[\mathbf{V}]=\text{\rm
Var}[\mathbf{Z}]$ and $(\mathbf{V},\mathbf{Z})$ is independent of
$(\mathbf{W},Y)$, we have

$\displaystyle
Q_{2}\;=\;\mfrac{1}{2}\,\mathbb{E}\big{[}h^{\prime\prime}_{t;\delta}(Y)\,\big{(}\mathbf{W}^{\top}\,\mathbb{E}[\mathbf{V}\mathbf{V}^{\top}-\mathbf{Z}\mathbf{Z}^{\top}]\,\mathbf{W}\big{)}\big{]}\;=\;0\;.$

∎

The next lemma is convenient for simplifying moment terms involving Gaussians:

######  Lemma 14.

Consider a zero-mean $\mathbb{R}^{b}$-valued Gaussian vector $\eta$. Suppose
$\text{\rm Var}[\eta]=\text{\rm Var}[V]$ for some $\mathbb{R}^{b}$ zero-mean
random vector $V$ and let $W$ be a random vector in $\mathbb{R}^{b}$
independent of $\eta$ and $V$. Then for any real number $\nu\geq 2$, we have

$\displaystyle\mathbb{E}\big{[}\big{|}W^{\top}\eta\big{|}^{\nu}\big{]}\;\leq\;\mfrac{2^{\nu/2}\,\Gamma\big{(}\frac{\nu+1}{2}\big{)}}{\sqrt{\pi}}\,\mathbb{E}\big{[}|W^{\top}V|^{\nu}\big{]}\;,$

where $\Gamma$ represents the Gamma function. In the case $\nu=2$, we have
$\text{\rm Var}[W^{\top}\eta]=\text{\rm Var}[W^{\top}V]$.

###### Proof of Lemma 14.

Note that $W$ is independent of $\eta$ and $V$. Conditioning on $W$,
$W^{\top}\eta$ is a zero-mean normal random variable with variance given by

$\displaystyle W^{\top}\text{\rm Var}[\eta]W\;=$
$\displaystyle\;W^{\top}\text{\rm
Var}[V]W\;=\;\mathbb{E}\big{[}W^{\top}VV^{\top}W\big{|}W\big{]}\;=\;\mathbb{E}\big{[}(W^{\top}V)^{2}\big{|}W\big{]}\;.$

Applying the formula of the $\nu$-th moment of a Gaussian random variable
followed by a Jensen’s inequality with $\nu\geq 2$, we get that

$\displaystyle\mathbb{E}\big{[}\big{|}W^{\top}\eta\big{|}^{\nu}\big{]}\;=\;\mathbb{E}\big{[}\mathbb{E}\big{[}\big{|}W^{\top}\eta\big{|}^{\nu}\big{|}W\big{]}\big{]}\;=$
$\displaystyle\;\mfrac{2^{\nu/2}\,\Gamma\big{(}\frac{\nu+1}{2}\big{)}}{\sqrt{\pi}}\mathbb{E}\big{[}\mathbb{E}\big{[}(W^{\top}V)^{2}\big{|}W\big{]}^{\nu/2}\big{]}$
$\displaystyle\;\leq$
$\displaystyle\;\mfrac{2^{\nu/2}\,\Gamma\big{(}\frac{\nu+1}{2}\big{)}}{\sqrt{\pi}}\mathbb{E}\big{[}|W^{\top}V|^{\nu}\big{]}\;.$

In the case $\nu=2$, the above becomes an equality and we get $\text{\rm
Var}[W^{\top}\eta]=\text{\rm Var}[W^{\top}V]$. ∎

We also restate the Carbery-Wright inequality (Theorem 8 of [10]) with our
notation:

######  Lemma 15 (Carbery-Wright inequality).

Let $Q(\mathbf{x})$ be a polynomial of $\mathbf{x}\in\mathbb{R}^{d}$ of degree
at most $m$ taking values in $\mathbb{R}$, and $\eta$ be a standard Gaussian
vector taking values in $\mathbb{R}^{d}$. Then there exists a constant $C$
independent of $Q$, $d$ or $m$ such that, for every $t\in\mathbb{R}$,

$\displaystyle\mathbb{P}\big{(}|Q(\eta)|\leq
t\big{)}\;\leq\;C\,t^{1/m}(\mathbb{E}[|Q(\eta)|^{2}])^{-1/2m}\;.$

###### Proof of Theorem 1.

We first note that since $q_{m}$ is affine in each argument,
$\mathbb{E}[q_{m}(\Xi)]=\mathbb{E}[q_{m}(\mathbf{X})]=0$. Meanwhile, by
applying Lemma 14 repeatedly, $\text{\rm Var}[q_{m}(\mathbf{X})]=\text{\rm
Var}[q_{m}(\Xi)]$. This proves the second part of Theorem 1.

To prove the first part, we denote $\tilde{q}_{m}\coloneqq\sigma^{-1}q_{m}$
for simplicity. We first approximate the probability terms. For
$\tau\in\mathbb{R}$ and $\delta>0$, let $h_{\tau;\delta}\equiv
h_{2;\tau;\delta}$ be the twice continuously differentiable function defined
in Lemma 12, which satisfies that
$h_{\tau+\delta;\delta}(x)\leq\mathbb{I}_{\\{x>\tau\\}}\leq
h_{\tau;\delta}(x)$ for any $\tau\in\mathbb{R}$. This allows us to bound

$\displaystyle\mathbb{P}(\tilde{q}_{m}(\mathbf{X})>t)-\mathbb{P}(\tilde{q}_{m}(\Xi)>t-\delta)\;=$
$\displaystyle\;\mathbb{E}\big{[}\mathbb{I}_{\\{\tilde{q}_{m}(\mathbf{X})>t\\}}-\mathbb{I}_{\\{\tilde{q}_{m}(\Xi)>t-\delta\\}}\big{]}$
$\displaystyle\;\leq$
$\displaystyle\;\mathbb{E}\big{[}h_{t;\delta}\big{(}\tilde{q}_{m}(\mathbf{X})\big{)}-h_{t;\delta}\big{(}\tilde{q}_{m}(\Xi)\big{)}\big{]}\;,$

and similarly

$\displaystyle\mathbb{P}(\tilde{q}_{m}(\Xi)>t+\delta)-\mathbb{P}(\tilde{q}_{m}(\mathbf{X})>t)\;\leq$
$\displaystyle\;\mathbb{E}\big{[}h_{t+\delta;\delta}\big{(}\tilde{q}_{m}(\Xi)\big{)}-h_{t+\delta;\delta}\big{(}\tilde{q}_{m}(\mathbf{X})\big{)}\big{]}\;.$

By expressing
$\mathbb{P}(\tilde{q}_{m}(\Xi)>t-\delta)\;=\;\mathbb{P}(\tilde{q}_{m}(\Xi)>t)+\mathbb{P}(t-\delta<\tilde{q}_{m}(\Xi)\leq
t)$ and performing a similar decomposition for
$\mathbb{P}(\tilde{q}_{m}(\Xi)>t+\delta)$, we obtain that

$\displaystyle\big{|}\mathbb{P}(\sigma^{-1}q_{m}(\mathbf{X})\leq t)-$
$\displaystyle\mathbb{P}(\sigma^{-1}q_{m}(\Xi)\leq
t)\big{|}\;=\;|\mathbb{P}(\tilde{q}_{m}(\mathbf{X})>t)-\mathbb{P}(\tilde{q}_{m}(\Xi)>t)|$
$\displaystyle\;\leq$
$\displaystyle\;\max\\{\mathbb{P}(t-\delta<\tilde{q}_{m}(\Xi)\leq
t)\,,\,\mathbb{P}(t\leq\tilde{q}_{m}(\Xi)<t+\delta)\\}+\max\\{E_{t},E_{t+\delta}\\}$
$\displaystyle\;\leq$
$\displaystyle\;\mathbb{P}(t-\delta<\tilde{q}_{m}(\Xi)<t+\delta)+E_{t}+E_{t+\delta}\;,$
(18)

where we have defined
$E_{\tau}\coloneqq|\mathbb{E}[h_{\tau;\delta}(\tilde{q}_{m}(\mathbf{X}))-h_{\tau;\delta}(\tilde{q}_{m}(\Xi))]|$
for $\tau\in\mathbb{R}$. The next step is to control quantities of the form
$E_{\tau}$ by Lindeberg’s principle. We recall
$\mathbf{W}_{i}=(\mathbf{X}_{1},\ldots,\mathbf{X}_{i-1},\mathbf{0},\xi_{i+1},\ldots,\xi_{n})\in\mathbb{R}^{nD}$
and define
$\mathbf{W}_{i}^{*}=(\mathbf{X}_{1},\ldots,\mathbf{X}_{i-1},\mathbf{X}_{i},\xi_{i+1},\ldots,\xi_{n})$.
Then by expanding the difference into a telescoping sum and applying a
triangle inequality,

$\displaystyle E_{\tau}\;=$
$\displaystyle\;|\mathbb{E}[h_{\tau;\delta}(\tilde{q}_{m}(\mathbf{X}))-h_{\tau;\delta}(\tilde{q}_{m}(\Xi))]|$
$\displaystyle\;\leq$
$\displaystyle\;\operatorname{\medmath\sum}_{i=1}^{n}|\mathbb{E}[h_{\tau;\delta}(\tilde{q}_{m}(\mathbf{W}_{i}^{*}))-h_{\tau;\delta}(\tilde{q}_{m}(\mathbf{W}_{i-1}^{*}))]|$
$\displaystyle\;\overset{(a)}{=}$
$\displaystyle\;\operatorname{\medmath\sum}_{i=1}^{n}|\mathbb{E}[h_{\tau;\delta}(\tilde{q}_{m}(\mathbf{W}_{i}^{*}))-h_{\tau;\delta}(\tilde{q}_{m}(\mathbf{W}_{i-1}^{*}))]|\;\eqqcolon\;\operatorname{\medmath\sum}_{i=1}^{n}E_{\tau;i}\;.$

We focus on bounding each $E_{\tau;i}$. By noting that $q_{m}$ is affine in
the $i$-th argument, we get

$\displaystyle\tilde{q}_{m}(\mathbf{W}_{i}^{*})\;=$
$\displaystyle\;\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}+\tilde{q}_{m}(\mathbf{W}_{i})$
and $\displaystyle\tilde{q}_{m}(\mathbf{W}_{i-1}^{*})\;=$
$\displaystyle\;\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\xi_{i}+\tilde{q}_{m}(\mathbf{W}_{i})\;.$

Note that $\mathbf{X}_{i}$ and $\xi_{i}$ are zero-mean with the same variance,
and are independent of $\mathbf{W}_{i}$. This allows us to apply Lemma 13: For
any $\nu\in(2,3]$ and $\delta>0$, we have

$\displaystyle E_{\tau;i}\;=$
$\displaystyle\;\big{|}\mathbb{E}\big{[}h_{\tau;\delta}\big{(}\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}+\tilde{q}_{m}(\mathbf{W}_{i})\big{)}-h_{\tau;\delta}\big{(}\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\xi_{i}+\tilde{q}_{m}(\mathbf{W}_{i})\big{)}\big{]}\big{|}$
(19) $\displaystyle\;\leq$
$\displaystyle\;54\,\delta^{-\nu}\,\big{(}\big{\|}\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\big{\|}_{L_{\nu}}^{\nu}+\big{\|}\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\xi_{i}\big{\|}_{L_{\nu}}^{\nu}\big{)}\;.$

Since $\xi_{i}$ is a Gaussian with the same mean and variance as
$\mathbf{X}_{i}$ and both are independent of $\partial_{i}f(\mathbf{W}_{i})$,
by Lemma 14 and noting that $\nu\leq 3$, there is an absolute constant
$C^{\prime}>0$ such that

$\displaystyle\mathbb{E}\big{[}|\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\xi_{i}|^{\nu}\big{]}\;\leq$
$\displaystyle\;C^{\prime}\,\big{\|}\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\big{\|}_{L_{\nu}}^{\nu}\;.$

By additionally noting that
$M_{\nu;i}=\sigma\|\partial_{i}\tilde{q}_{m}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\|_{L_{\nu}}$
by definition, we get that

$\displaystyle E_{\tau;i}\;\leq$
$\displaystyle\;54(C^{\prime}+1)\,\delta^{-\nu}\sigma^{-\nu}M_{\nu;i}^{\nu}\;.$

Summing over $i=1,\ldots,n$ then gives

$\displaystyle E_{\tau}$
$\displaystyle\;\leq\;\operatorname{\medmath\sum}_{i=1}^{n}E_{\tau;i}r\;\leq\;54(C^{\prime}+1)\,\mfrac{\sum_{i=1}^{n}M_{\nu;i}^{\nu}}{\delta^{\nu}\sigma^{\nu}}\;.$
(20)

On the other hand, by Lemma 15, there exists an absolute constant $C^{*}>0$
such that

$\displaystyle\mathbb{P}(t-\delta<\tilde{q}_{m}(\Xi)<$ $\displaystyle
t+\delta)\;\leq\;C^{*}\delta^{1/m}(\mathbb{E}[|\tilde{q}_{m}(\Xi)-t|^{2}])^{-1/2m}$
$\displaystyle\;\overset{(a)}{=}$
$\displaystyle\;C^{*}\delta^{1/m}(\sigma^{-2}\text{\rm
Var}[q_{m}(\Xi)]+t^{2})^{-1/2m}\;\overset{(b)}{=}\;C^{*}\delta^{1/m}(1+t^{2})^{-1/2m}\;.$
(21)

In $(a)$ and $(b)$, we have used that $\mathbb{E}[f(\Xi)]=0$ and $\text{\rm
Var}[f(\Xi)]=\text{\rm Var}[f(\mathbf{X})]=\sigma^{2}$. Substituting (20) and
(21) into (18), we get that there exists some absolute constant $C>0$ such
that

$\displaystyle\big{|}\mathbb{P}(\sigma^{-1}q_{m}(\mathbf{X})\leq
t)-\mathbb{P}(\sigma^{-1}q_{m}(\Xi)\leq
t)\big{|}\;\leq\;\mfrac{C}{2}\Big{(}\mfrac{\delta^{1/m}}{(1+t^{2})^{1/2m}}+\mfrac{\sum_{i=1}^{n}M_{\nu;i}^{\nu}}{\delta^{\nu}\sigma^{\nu}}\Big{)}\;.$

Finally by choosing $\delta=(1+t^{2})^{\frac{1}{2+2\nu
m}}\big{(}\sigma^{-\nu}\sum_{i=1}^{n}M_{\nu;i}^{\nu}\big{)}^{\frac{m}{\nu
m+1}}$, we get the desired bound that

$\displaystyle\big{|}\mathbb{P}(\sigma^{-1}f(\mathbf{X})\leq
t)-\mathbb{P}(\sigma^{-1}f(\Xi)\leq
t)\big{|}\;\leq\;C\,\Big{(}\mfrac{\sum_{i=1}^{n}M_{\nu;i}^{\nu}}{(1+t^{2})^{\nu/2}\sigma^{\nu}}\Big{)}^{\frac{1}{\nu
m+1}}\;.$

∎

##  Constructions for Theorem 3

The key ingredient of the proof of Theorem 3 is a suitable sequence of heavy-
tailed probability measures $\mu^{(n)}_{\nu,\sigma_{0}}$ and statistic
$p^{*}_{m}$. Before stating the exact constructions, we first motivate them by
discussing our proof technique.

#### Adapting an asymmetry argument from Senatov [51].

The overall idea is to construct a mixture of an average of a heavy-tailed
random variable, which is poorly approximated via Gaussian universality, and a
degree-$m$ V-statistic of Gaussians, which has good approximation by the same
V-statistic of an i.i.d. copy of Gaussians at small $m$ but poor approximation
at large $m$. The technical steps to obtain a tight lower bound, however, are
highly non-trivial. Our strategy is inspired by Example 9.1.3 of Senatov [51]:
They construct a sequence of probability measures on $\mathbb{R}^{d}$ to
demonstrate how a multivariate normal approximation bound on a chosen sequence
of Euclidean balls may depend on eigenvalues of the covariance matrix. Two key
mathematical ingredients of their work are

  1. (i)

a heavy-tailed univariate variable, whose i.i.d. average is poorly
approximated by a Gaussian, and

  2. (ii)

an asymmetry argument by considering Euclidean balls not centred at the origin
while studying averages of mean-zero random vectors.

To adapt the construction in [51] for our problem, we make one key
observation: The probability of a mean-zero average lying in a radius-$r$
Euclidean ball centred at the origin is exactly the probability of a degree-2
V-statistic taking values in $[0,r^{2})$. In other words, (i) gives the heavy-
tailed variable we need, and (ii) is almost our V-statistic except that the
Euclidean balls in Senatov [51] are not centred at the origin. Unfortunately,
while the asymmetry in (ii) is key to the proof by Senatov [51], it breaks the
connection to V-statistics, and a naive application of Senatov’s results gives
very loose bounds. Instead, we create a different asymmetry by asking
$p^{*}_{m}(X)$ to be a mixture of an odd-degree V-statistic and an even-degree
V-statistic, which allows Senatov’s argument to be adapted. An additional
distinction of our proof from [51] is that, to accommodate a growing degree
$m$, we need to derive finer moment controls.

We are ready to state the constructions. For $m=m(n)$ even, consider the
polynomial

$\displaystyle p^{*}_{m}(x_{1},\ldots,x_{n})\;\coloneqq$
$\displaystyle\;\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}x_{i1}+\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}x_{i_{j}2}\Big{)}^{m}\;\;\text{
for }x_{i}=(x_{i1},x_{i2})\in\mathbb{R}^{2}\;.$

The distribution $\mu^{(n)}_{\nu,\sigma_{0}}$ is the law of a bivariate random
vector with a heavy-tailed coordinate and a Gaussian coordinate. We first
construct the heavy-tailed variable.

#### A heavy-tailed univariate distribution $\tilde{\mu}_{\nu,\sigma}$.

For $\nu>2$ and $\sigma\in(0,1)$, we define

$\displaystyle p\;=$ $\displaystyle\;\sigma^{2\nu/(\nu-2)}\in(0,1)$ and
$\displaystyle x_{0}\;=$ $\displaystyle\;\sigma/\sqrt{6p}\;=\;x\;,$

and let $U_{1}$ be a discrete random variable taking values in
$\\{-x_{0},0,2x_{0}\\}$ with

$\displaystyle\mathbb{P}(U_{1}=-x_{0})\;=\;2p\;,\qquad\mathbb{P}(U_{1}=0)\;=\;1-3p\quad\text{
and }\quad\mathbb{P}(U_{1}=2x_{0})\;=\;p\;.$

Let $Z_{1}\sim\mathcal{N}(0,\sigma^{2})$ and define a smoothed version of $U$
as

$\displaystyle V_{1}\;\coloneqq\;2^{-1/2}U_{1}+2^{-1/2}Z_{1}\;.$

Write $\tilde{\mu}_{\nu,\sigma}$ as the law of $V_{1}$. When $\nu=3$, this is
the heavy-tailed distribution constructed in Example 9.1.3 of [51]. Roughly
speaking, the construction is such that if we set
$\sigma=\sigma_{n}\rightarrow 0$ as $n\rightarrow\infty$, then $\text{\rm
Var}[V_{1}]=\sigma_{n}^{2}\rightarrow 0$, but the $\nu$-th central moment of
$V_{1}$ remains $\Theta(1)$.

Let $V_{2},\ldots,V_{n}\overset{i.i.d.}{\sim}\tilde{\mu}_{\nu,\sigma}$ and
draw an independent $Z^{\prime}_{1}\sim\mathcal{N}(0,\sigma^{2})$. We now list
three results on $\tilde{\mu}_{\nu,\sigma}$, which extend the results by [51]
to a general $\nu$ and admit similar proofs. Since the original proofs are
highly condensed, we include proofs for all lemmas with more detailed steps
and intuitions in Section B.2.

######  Lemma 16.

$\mathbb{E}\,V_{1}=0$ and $\text{\rm Var}\,V_{1}=\sigma^{2}$. Moreover, there
exist absolute constants $c_{1},c_{2}>0$ such that for all $\omega\geq 1$,
$\mathbb{E}|V_{1}|^{\omega}\leq
c_{1}^{\omega}\sigma^{-\frac{2(\omega-\nu)}{\nu-2}}+c_{2}^{\omega}\sigma^{\omega}\omega^{\omega/2}$.

######  Lemma 17.

There exists some absolute constant $A>0$ such that, defining the function
$F_{q}(x)\coloneqq\frac{A}{n^{1/2}\sigma^{\nu/(\nu-2)}}\big{(}1-\frac{x^{2}}{\sigma^{2}}\big{)}e^{-x^{2}/(2\sigma^{2})}$,
we have

$\displaystyle\sup\nolimits_{x\in\mathbb{R}}\Big{|}\mathbb{P}\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}V_{i}<x\Big{)}-\mathbb{P}(Z^{\prime}_{1}<x)-F_{q}(x)\Big{|}\;\leq\;\mfrac{2}{n\sigma^{2\nu/(\nu-2)}}\;.$

######  Lemma 18.

Suppose there exists some constant $M\geq 10$ such that
$\sigma^{\nu/(\nu-2)}\geq Mn^{-1/2}$ and $n\geq 6M^{2}$. Then there is some
constant $C_{M}>0$ that depends only on $M$ such that, for all
$x\in\mathbb{R}$, we have

$\displaystyle\Big{|}\mathbb{P}\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}V_{i}<x\Big{)}-\mathbb{P}(Z^{\prime}_{1}<x)\Big{|}\;\leq\;C_{M}\Big{(}\mfrac{\max\\{1,\sigma^{3}\\}}{n^{1/2}\sigma^{\nu/(\nu-2)}}e^{-\frac{x^{2}}{16\sigma^{2}}}+\mfrac{1}{n^{3/2}x^{4}\sigma^{(8-\nu)/(\nu-2)}}\Big{)}\;.$

Lemma 16 gives the moment controls needed to handle a polynomial with growing
degrees, whereas Lemma 17 and Lemma 18 give tight upper and lower error bounds
on the Gaussian approximation of a heavy-tailed average.

#### The bivariate distribution $\mu^{(n)}_{\nu,\sigma_{0}}$.

Now for a fixed $\nu\in(2,3]$ and some absolute constant $\sigma_{0}>0$, set a
standard deviation parameter

$\displaystyle\sigma_{n}\;\coloneqq$
$\displaystyle\;\min\big{\\{}\sigma_{0}\,n^{-\frac{\nu-2}{2\nu}}\,,\,1\big{\\}}\;\in\;(0,1)\;.$

With a slight abuse of notation, we consider

$\displaystyle V_{1},\ldots,V_{n}\;\overset{i.i.d.}{\sim}$
$\displaystyle\;\tilde{\mu}_{\nu,\sigma_{n}}$ and $\displaystyle
Y_{1},\ldots,Y_{n}\;\overset{i.i.d.}{\sim}$
$\displaystyle\;\mathcal{N}(0,1)\;,$

and define $\mu^{(n)}_{\nu,\sigma_{0}}$ as the law of $(V_{1},Y_{1})$.

In summary, the statistic we consider is a mixture of a heavy-tailed average
and an even-degree V-statistic of Gaussian random variables:

$\displaystyle p^{*}_{m}(X)\;\coloneqq$
$\displaystyle\;\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}V_{i}+\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}Y_{i}\Big{)}^{m}\;=\;v^{*}_{1}(V)+v^{*}_{m}(Y)\;,$

where we have denoted $V\coloneqq(V_{i})_{i\leq n}$, $Y\coloneqq(Y_{i})_{i\leq
n}$ and the rescaled degree-$m^{\prime}$ V-statistic as

$\displaystyle
v^{*}_{m^{\prime}}(x^{\prime}_{1},\ldots,x^{\prime}_{n})\;\coloneqq\;\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}x^{\prime}_{i}\Big{)}^{m^{\prime}}\quad\text{
for }x^{\prime}_{1},\ldots,x^{\prime}_{n}\in\mathbb{R}\;.$

##  Proof for Theorem 3

Recall that $q^{*}_{m}$ is the multilinear representation of $p^{*}_{m}$ with
respect to $X$. The proof consists of three main steps:

  1. (i)

By carefully exploiting the heavy-tailedness of $V_{i}$’s and the asymmetry of
$v^{*}_{m^{\prime}}$, we can obtain the first lower bound for the
approximation of $p^{*}_{m}(X)$ by $p^{*}_{m}(Z)$ (Lemma 19);

  2. (ii)

By applying Theorem 1 to approximate
$p^{*}_{m}(X)=q^{*}_{m}(\mathbf{X})+\mathbb{E}[p^{*}_{m}(X)]$ by
$q^{*}_{m}(\Xi)+\mathbb{E}[p^{*}_{m}(X)]$, the second upper bound in Theorem 3
reduces to a moment control (Lemma 21);

  3. (iii)

By verifying $\delta$-regularity and modifying the argument of Proposition 5,
we can approximate $q^{*}_{m}(\Xi)+\mathbb{E}[p^{*}_{m}(X)]$ further by
$p^{*}_{m}(Z)$ (Lemma 22).

We introduce some more notation. Note that we can express
$X_{i}=(V_{i},Y_{i})$ and $\mathbf{X}_{i}=(V_{i},\mathbf{Y}_{i})$, where
$\mathbf{Y}_{i}=(Y_{i},\ldots,Y_{i}^{m}-\mathbb{E}[Y_{i}^{m}])$.
Correspondingly, we express $Z_{i}=(Z_{V;i},Z_{Y;i})$, where
$Z_{V;i}\sim\mathcal{N}(0,\text{\rm Var}\,V_{i})$ and
$Z_{Y;i}\sim\mathcal{N}(0,\text{\rm Var}\,Y_{i})$, and
$\xi_{i}=(\xi_{V;i},\xi_{\mathbf{Y};i})$, where
$\xi_{V;i}\sim\mathcal{N}(0,\text{\rm Var}\,V_{i})$ and
$\xi_{\mathbf{Y};i}\sim\mathcal{N}(\mathbf{0},\text{\rm
Var}\,\mathbf{Y}_{i})$. Denote the collections $Z_{V}\coloneqq(Z_{V;i})_{i\leq
n}$, $Z_{Y}\coloneqq(Z_{Y;i})_{i\leq n}$ and
$\Xi_{\mathbf{Y}}\coloneqq(\xi_{\mathbf{Y};i})_{i\leq n}$. It is also
convenient to denote $q^{*}_{v;m}$ as the multilinear representation of
$v^{*}_{m}$ with respect to $Y$, since

$\displaystyle q^{*}_{m}(\mathbf{X})\;=$
$\displaystyle\;v^{*}_{1}(V)+q^{*}_{v;m}(\mathbf{Y})$ and $\displaystyle
q^{*}_{m}(\Xi)\;\overset{d}{=}$
$\displaystyle\;v^{*}_{1}(Z_{V})+q^{*}_{v;m}(\Xi_{\mathbf{Y}})\;.$

######  Lemma 19.

Fix $\nu>2$. Assume that $m$ is even with $m=o(\log n)$. Then there exist some
absolute constants $c,\sigma_{0}>0$ and $N\in\mathbb{N}$ such that, for any
$n\geq N$,

$\displaystyle\mathbb{P}\big{(}p^{*}_{m}(Z)<-2\sigma_{n}$
$\displaystyle\big{)}-\mathbb{P}\big{(}p^{*}_{m}(X)<-2\sigma_{n}\big{)}\;\geq\;cn^{-\frac{\nu-2}{2\nu
m}}\;.$

###### Proof of Lemma 19.

Since the second coordinate of $X_{i}$ is already Gaussian, the main hurdle is
to approximate the heavy-tailed average by a Gaussian. Let $F_{V}$ be the
c.d.f. of $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}V_{i}$ – an empirical average of
the heavy-tailed coordinates – and $F_{Z}$ be the c.d.f. of
$\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Z_{i}$, where $Z_{i}$’s are i.i.d. zero-mean
random variables with the same variance as $V_{1}$. Write $\varphi$ be the
p.d.f. of $\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Y_{i}\sim\mathcal{N}(0,1)$.
Recalling that $m$ is even and denoting

$\displaystyle
I(x)\;\coloneqq\;F_{Z}(-2\sigma_{n}-x^{m})-F_{V}(-2\sigma_{n}-x^{m})\;,$

we can bound the quantity of interest as

$\displaystyle\mathbb{P}\big{(}p^{*}_{m}(Z)<-2\sigma_{n}\big{)}-\mathbb{P}\big{(}p^{*}_{m}(X)$
$\displaystyle<-2\sigma_{n}\big{)}\;=\;\operatorname{\scaleobj{.8}{\int}}_{0\leq
x^{m}<\infty}I(x)\varphi(x)dx$ $\displaystyle\;\geq$
$\displaystyle\;\operatorname{\scaleobj{.8}{\int}}_{0\leq
x^{m}\leq\kappa^{m}\sigma_{n}}I(x)\varphi(x)dx-\Big{|}\operatorname{\scaleobj{.8}{\int}}_{|x|>\kappa\sigma_{n}^{1/m}}I(x)\varphi(x)dx\Big{|}$
$\displaystyle\;\eqqcolon$ $\displaystyle\;J_{1}-J_{2}\;.$

Bounding $J_{1}$.  Recall that for $y\in\mathbb{R}$, Lemma 17 provides an
error bound for approximating the difference $F_{Z}(y)-F_{n}(y)$ by

$\displaystyle-
F_{q}(y)\;=\;\mfrac{A}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\,\Big{(}\mfrac{y^{2}}{\sigma_{n}^{2}}-1\Big{)}\,e^{-y^{2}/(2\sigma_{n}^{2})}$

for some absolute constant $A>0$. Therefore

$\displaystyle J_{1}\;\geq$
$\displaystyle\;\operatorname{\scaleobj{.8}{\int}}_{x^{m}\leq\kappa^{m}\sigma_{n}}-F_{q}(-2\sigma_{n}-x^{m})\varphi(x)dx-\mfrac{2}{n\sigma_{n}^{2\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}\leq\kappa^{m}\sigma_{n}}\varphi(x)dx$
$\displaystyle\;\overset{(a)}{\geq}$
$\displaystyle\;\mfrac{A}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}\leq\sigma_{n}}\Big{(}\mfrac{(2\sigma_{n}+x^{m})^{2}}{\sigma_{n}^{2}}-1\Big{)}\,e^{-(2\sigma_{n}+x^{m})^{2}/(2\sigma_{n}^{2})}\varphi(x)dx$
$\displaystyle\;-\mfrac{2}{n\sigma_{n}^{2\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}\leq\kappa^{m}\sigma_{n}}\varphi(x)dx$
$\displaystyle\;\overset{(b)}{\geq}$
$\displaystyle\;\mfrac{3e^{-9/2}A}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}\leq\sigma_{n}}\varphi(x)dx-\mfrac{2}{n\sigma_{n}^{2\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}\leq\kappa^{m}\sigma_{n}}\varphi(x)dx\;.$

In $(a)$, we have restricted the first integral to a smaller ball by noting
that $\kappa\geq 1$; in $(b)$, we have noted in the first integral that
$4\sigma_{n}^{2}\leq(2\sigma_{n}+x^{m})^{2}\leq 9\sigma_{n}^{2}$ in the domain
of integration. By recalling that $\varphi$ is the p.d.f. of
$\mathcal{N}(0,1)$, we can bound the integrals above and obtain

$\displaystyle J_{1}\;\geq$
$\displaystyle\;\mfrac{3e^{-9/2}A}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\,\mfrac{2\sigma_{n}^{1/m}}{\sqrt{2\pi}}\exp\Big{(}-\mfrac{\sigma_{n}^{2/m}}{2}\Big{)}-\mfrac{4\kappa\sigma_{n}^{1/m}}{n\sigma_{n}^{2\nu/(\nu-2)}}$
$\displaystyle\;\geq$
$\displaystyle\;\mfrac{\sigma_{n}^{1/m}}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\Big{(}A_{1}e^{-\frac{1}{2}\sigma_{n}^{2/m}}-\mfrac{A_{2}\kappa}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\Big{)}$

for some absolute constants $A_{1},A_{2}>0$.

Bounding $J_{2}$. Recall that
$\sigma_{n}=\min\big{\\{}\sigma_{0}n^{-\frac{\nu-2}{2\nu}}\,,\,1\big{\\}}$,
which implies

$\displaystyle\sigma_{n}^{\frac{\nu}{\nu-2}}\;\geq\;\min\big{\\{}\sigma_{0}^{\frac{\nu}{\nu-2}}n^{-1/2}\,,\,1\big{\\}}\;\geq\;\sigma_{0}^{\frac{\nu}{\nu-2}}n^{-1/2}\;.$

Suppose we choose $\sigma_{0}$ such that
$\sigma_{0}^{\frac{\nu}{\nu-2}}>6^{-1/2}$. Since $6(6^{-1/2})^{2}=1\leq n$, by
applying Lemma 18 with $M=6^{-1/2}$, there exists some absolute constant $C>0$
such that

$\displaystyle J_{2}\;=$
$\displaystyle\;\Big{|}\operatorname{\scaleobj{.8}{\int}}_{x^{m}>\kappa^{m}\sigma_{n}}\big{(}F_{Z}(-2\sigma_{n}-x^{m})-F_{n}(-2\sigma_{n}-x^{m})\big{)}\varphi(x)dx\Big{|}$
$\displaystyle\;\leq$
$\displaystyle\;\mfrac{C}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}>\kappa^{m}\sigma_{n}}e^{-\frac{(2\sigma_{n}+x^{m})^{2}}{16\sigma_{n}^{2}}}\varphi(x)dx$
$\displaystyle\qquad\;+\mfrac{C}{n^{3/2}\sigma_{n}^{(8-\nu)/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}>\kappa^{m}\sigma_{n}}\mfrac{1}{(2\sigma_{n}+x^{m})^{4}}\varphi(x)dx$
$\displaystyle\;\eqqcolon$ $\displaystyle\;J_{21}+J_{22}\;.$

By applying a change-of-variable, we get that

$\displaystyle J_{21}\;\leq$
$\displaystyle\;\mfrac{C}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}>\kappa^{m}\sigma_{n}}e^{-\frac{x^{2m}}{16\sigma_{n}^{2}}}\varphi(x)dx$
$\displaystyle\;=$
$\displaystyle\;\mfrac{C\sigma_{n}^{1/m}}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}>\kappa^{m}}e^{-\frac{x^{2m}}{16}}\varphi\big{(}\sigma_{n}^{1/m}x\big{)}dx$
$\displaystyle\;\overset{(a)}{\leq}$
$\displaystyle\;\mfrac{2C\sigma_{n}^{1/m}}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x>\kappa}e^{-\frac{x^{2m}}{16}}dx$
$\displaystyle\;\leq$
$\displaystyle\;\mfrac{2C\sigma_{n}^{1/m}}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x>\kappa}(2m)\Big{(}\mfrac{x}{\kappa}\Big{)}^{2m-1}e^{-\frac{x^{2m}}{16}}dx$
$\displaystyle\;\leq$
$\displaystyle\;\mfrac{A_{3}\,\sigma_{n}^{1/m}}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}\kappa^{2m-1}}$

for some absolute constant $A_{3}>0$. In $(a)$, we have noted that
$\varphi(x)\leq 1$ and the integrand is symmetric in $x$. Similarly, we can
bound

$\displaystyle J_{22}\;\leq$
$\displaystyle\;\mfrac{C}{n^{3/2}\sigma_{n}^{(8-\nu)/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}>\kappa^{m}\sigma_{n}}\mfrac{1}{x^{4m}}\varphi(x)dx$
$\displaystyle\;\leq$
$\displaystyle\;\mfrac{C}{n^{3/2}\sigma_{n}^{(8-\nu)/(\nu-2)}}\operatorname{\scaleobj{.8}{\int}}_{x^{m}>\kappa^{m}\sigma_{n}}\mfrac{1}{x^{4m}}dx$
$\displaystyle\;=$
$\displaystyle\;\mfrac{(4m-1)C}{n^{3/2}\sigma_{n}^{(8-\nu)/(\nu-2)}\,\sigma_{n}^{4-1/m}\,\kappa^{4m-1}}$
$\displaystyle\;=$
$\displaystyle\;\mfrac{A_{4}\,\sigma_{n}^{1/m}(4m-1)}{n^{3/2}\sigma_{n}^{3\nu/(\nu-2)}\kappa^{4m-1}}$

for some absolute constant $A_{4}>0$.

Combining the bounds. Combining the bounds, we get that if
$\sigma_{0}^{\frac{\nu}{\nu-2}}>6^{-1/2}$, then

$\displaystyle\mathbb{P}\big{(}$ $\displaystyle
p^{*}_{m}(Z)<-2\sigma_{n}\big{)}-\mathbb{P}\big{(}p^{*}_{m}(X)<-2\sigma_{n}\big{)}\;\geq\;J_{1}-J_{2}$
$\displaystyle\;\geq$
$\displaystyle\;\mfrac{\sigma_{n}^{1/m}}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\Bigg{(}A_{1}e^{-\frac{1}{2}\sigma_{n}^{2/m}}-\mfrac{A_{2}\kappa}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}-\mfrac{A_{3}}{\kappa^{2m-1}}-\mfrac{A_{4}(4m-1)}{n\,\sigma_{n}^{2\nu/(\nu-2)}\,\kappa^{4m-1}}\Bigg{)}\;.$

Recall that
$\sigma_{n}=\min\big{\\{}\sigma_{0}n^{-\frac{\nu-2}{2\nu}}\,,\,1\big{\\}}$ and
$m=o(\log n)$. Take the absolute constants $N_{1}\in\mathbb{N}$ sufficiently
large such that
$A_{1}e^{-\frac{1}{2}\sigma_{0}^{2/m}N_{1}^{-\frac{\nu-2}{m\nu}}}\geq\frac{1}{2}A_{1}$,
$\kappa>2$ sufficiently large such that
$\frac{A_{3}}{\kappa^{2m-1}}<\frac{1}{9}A_{1}$, $\sigma_{0}>0$ sufficiently
large such that
$\frac{A_{2}\kappa}{\sigma_{0}^{\nu/(\nu-2)}}<\frac{1}{9}A_{1}$ and
$\frac{A_{4}}{\sigma_{0}}\frac{4m-1}{\kappa^{4m-1}}<\frac{1}{9}A_{1}$, and
finally $N_{2}\in\mathbb{N}$ sufficiently large such that
$\sigma_{0}N_{2}^{-\frac{\nu-2}{2\nu}}<1$. Then we get the desired bound that,
for some absolute constant $c>0$ and all $n\geq
N\coloneqq\max\\{N_{1},N_{2}\\}$,

$\displaystyle\mathbb{P}\big{(}p^{*}_{m}(Z)<-2\sigma_{n}\big{)}-\mathbb{P}\big{(}p^{*}_{m}(X)<-2\sigma_{n}\big{)}\;\geq\;\mfrac{A_{1}}{6}\mfrac{\sigma_{n}^{1/m}}{n^{1/2}\sigma_{n}^{\nu/(\nu-2)}}\;\geq\;cn^{-\frac{\nu-2}{2\nu
m}}\;.$

∎

To obtain the desired moment controls, we will need to use tight bounds on the
moments of a univariate Gaussian. The proof of the following result is
included in Section B.1.

######  Lemma 20.

Let $Z\sim\mathcal{N}(0,1)$. Then there exist some absolute constants $C,c>0$
such that

  1. (i)

for any $\nu\geq 1$, $\mathbb{E}|Z|^{\nu}\leq C\nu^{\nu/2}$;

  2. (ii)

for any $m_{1},m_{2}\in\mathbb{N}$ with different parities, $\text{\rm
Cov}[Z^{m_{1}},Z^{m_{2}}]=0$;

  3. (iii)

for $m_{1},m_{2}\in\mathbb{N}$ with the same parity, $\text{\rm
Cov}[Z^{m_{1}},Z^{m_{2}}]>c^{m_{1}+m_{2}}(m_{1}+m_{2})^{(m_{1}+m_{2})/2}$.

The next result controls the moment ratio arising from Theorem 1.

######  Lemma 21.

Fix $\nu\in(2,3]$ and assume that $n\geq 2m^{2}$. Then for some absolute
constant $C>0$,

$\displaystyle\mfrac{\sum_{i=1}^{n}\big{\|}\partial_{i}\,q_{m}^{*}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\big{\|}_{L_{\nu}}^{\nu}}{\big{(}\text{\rm
Var}[p_{m}^{*}(X)]\big{)}^{\nu/2}}\leq C^{m}n^{-\frac{\nu-2}{2}},\quad\text{
where
}\mathbf{W}_{i}\coloneqq\big{(}\mathbf{X}_{1},\ldots,\mathbf{X}_{i-1},0,\xi_{i+1},\ldots,\xi_{n}\big{)}\;.$

###### Proof of Lemma 21.

First note that by independence,

$\displaystyle\sigma\;=\;\sqrt{\text{\rm
Var}[q_{m}^{*}(\mathbf{X})]}\;=\;\sqrt{\text{\rm Var}[v^{*}_{1}(V)]+\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})]}\;\geq\;\sqrt{\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})]}\;.$

Next to bound the $\nu$-th moment, denote
$W_{V;i}\coloneqq(V_{1},\ldots,V_{i-1},0,Z_{V;i+1},\ldots,Z_{V;n})$ and
$\mathbf{W}_{\mathbf{Y};i}\coloneqq(\mathbf{Y}_{1},\ldots,\mathbf{Y}_{i-1},0,\xi_{\mathbf{Y};i+1},\ldots,\xi_{\mathbf{Y};n})$.
By a triangle inequality, we get that

$\displaystyle\big{\|}\partial_{i}\,q_{m}^{*}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\big{\|}_{L_{\nu}}\;=$
$\displaystyle\;\big{\|}\partial_{i}\,v^{*}_{1}(W_{V;i})V_{i}+\partial_{i}\,q^{*}_{v;m}(\mathbf{W}_{Y;i})^{\top}\mathbf{Y}_{i}\big{\|}_{L_{\nu}}$
$\displaystyle\;\leq$
$\displaystyle\;n^{-1/2}\|V_{i}\|_{L_{\nu}}+\big{\|}\partial_{i}\,q^{*}_{v;m}(\mathbf{W}_{Y;i})^{\top}\mathbf{Y}_{i}\big{\|}_{L_{\nu}}\;.$

Since $\nu\in(2,3]$, the quantity to control can be bounded for some absolute
constant $C_{1}>0$ as

$\displaystyle\mfrac{\sum_{i=1}^{n}\big{\|}\partial_{i}\,q_{m}^{*}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\big{\|}_{L_{\nu}}^{\nu}}{\big{(}\text{\rm
Var}[p_{m}^{*}(X)]\big{)}^{\nu/2}}\;\leq$
$\displaystyle\;\mfrac{4n^{-\frac{\nu-2}{2}}\|V_{1}\|_{L_{\nu}}+4\operatorname{\medmath\sum}_{i=1}^{n}\big{\|}\partial_{i}\,q^{*}_{v;m}(\mathbf{W}_{Y;i})^{\top}\mathbf{Y}_{i}\big{\|}_{L_{\nu}}^{\nu}}{(\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})])^{\nu/2}}$ $\displaystyle\;\leq$
$\displaystyle\;\mfrac{C_{1}n^{-\frac{\nu-2}{2}}}{(\text{\rm
Var}[v^{*}_{m}(Y)])^{\nu/2}}+\mfrac{4\operatorname{\medmath\sum}_{i=1}^{n}\big{\|}\partial_{i}\,q^{*}_{v;m}(\mathbf{W}_{Y;i})^{\top}\mathbf{Y}_{i}\big{\|}_{L_{\nu}}^{\nu}}{(\text{\rm
Var}[v^{*}_{m}(Y)])^{\nu/2}}\;.$ (22)

In the first inequality, we have used a Jensen’s inequality to note that
$(a+b)^{\nu}\leq 2^{\nu-1}(a^{\nu}+b^{\nu})\leq 4(a^{\nu}+b^{\nu})$ and noted
that $V_{i}$’s are i.i.d.; in the second inequality, we have used the moment
bound on $V_{1}$ from Lemma 16 and noted that $\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})]=\text{\rm
Var}[q^{*}_{v;m}(\mathbf{Y})]=\text{\rm Var}[v^{*}_{m}(Y)]$ by a repeated
application of Lemma 14 and property of the multilinear representation. The
first term can be controlled by using the lower bound from Lemma 20:

$\displaystyle\text{\rm Var}[v^{*}_{m}(Y)]\;=\;\text{\rm
Var}\Big{[}\Big{(}\mfrac{1}{\sqrt{n}}\operatorname{\medmath\sum}_{i=1}^{n}Y_{i}\Big{)}^{m}\Big{]}\;=\;\text{\rm
Var}[Y_{1}^{m}]\;\geq\;(c_{2}^{\prime})^{m}(2m)^{m}\;\geq\;c_{2}$ (23)

for some absolute constants $c^{\prime}_{2},c_{2}>0$. The second term can be
controlled by applying Lemma 7: Since $n\geq 2m^{2}$, there exists some
absolute constant $C_{3}>0$ such that

$\displaystyle\mfrac{\operatorname{\medmath\sum}_{i=1}^{n}\big{\|}\partial_{i}\,q^{*}_{v;m}(\mathbf{W}_{Y;i})^{\top}\mathbf{Y}_{i}\big{\|}_{L_{\nu}}^{\nu}}{(\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})])^{\nu/2}}\;\leq\;C_{3}\,n^{-\frac{\nu-2}{2}}\,\Bigg{(}\mfrac{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{\nu}^{*}(k))^{2}}{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{2}^{*}(k))^{2}}\Bigg{)}^{\frac{\nu}{2}}\;,$
(24)

where

$\displaystyle\alpha_{\nu}^{*}(k)\;\coloneqq\;\bigg{\|}\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\,\operatorname{\medmath\prod}_{l=1}^{k}\big{(}Y_{l}^{p_{l}}-\mathbb{E}Y_{l}^{p_{l}}\big{)}\bigg{\|}_{L_{\nu}}\;.$

We are left with bounding $\alpha_{2}^{*}(k)$ and $\alpha_{\nu}^{*}(k)$. Since
$Y_{i}$’s are i.i.d. standard normals, the proof is down to using the moment
bounds for standard normals from Lemma 20. For convenience, we denote
$\overline{Y_{l}^{p_{l}}}\coloneqq Y_{l}^{p_{l}}-\mathbb{E}Y_{l}^{p_{l}}$ from
now on. We can then express

$\displaystyle(\alpha_{2}^{*}(k))^{2}\;=\;\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\operatorname{\medmath\sum}_{\begin{subarray}{c}q_{1}+\ldots+q_{k}=m\\\
q_{1},\ldots,q_{k}\geq 1\end{subarray}}\,\text{\rm
Cov}\bigg{[}\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\,,\,\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\bigg{]}\,.$

We now show by induction that for some absolute constant $c>0$,

$\displaystyle\text{\rm
Cov}\bigg{[}\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\,,\,\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\bigg{]}\;\geq\;\operatorname{\medmath\prod}_{l=1}^{k}\mathbb{I}_{\\{p_{l}\equiv
q_{l}\,(\textrm{mod
}2)\\}}\,c^{p_{l}+q_{l}}\,(p_{l}+q_{l})^{(p_{l}+q_{l})/2}\;.$

For $k=1$, this directly holds for all $p_{l},q_{l}\in[m]$ by the lower bound
of Lemma 20. Suppose this holds for $k-1$, then by the total law of covariance
and noting that all variables are centred and independent,

$\displaystyle\text{\rm
Cov}\bigg{[}\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\,,\,\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\bigg{]}\;=$
$\displaystyle\;\mathbb{E}\,\text{\rm
Cov}\bigg{[}\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\,,\,\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\,\bigg{|}\,Y_{k-1}\bigg{]}$
$\displaystyle\;=$
$\displaystyle\;\mathbb{E}\Big{[}\overline{Y_{k}^{p_{k}}}\,,\,\overline{Y_{k}^{q_{k}}}\Big{]}\,\text{\rm
Cov}\bigg{[}\operatorname{\medmath\prod}_{l=1}^{k-1}\overline{Y_{l}^{p_{l}}}\,,\,\operatorname{\medmath\prod}_{l=1}^{k-1}\overline{Y_{l}^{p_{l}}}\bigg{]}$
$\displaystyle\;\geq$ $\displaystyle\;\text{\rm
Cov}[Y_{k}^{p_{k}}\,,\,Y_{k}^{q_{k}}]\operatorname{\medmath\prod}_{l=1}^{k-1}\mathbb{I}_{\\{p_{l}\equiv
q_{l}\,(\textrm{mod }2)\\}}\,c^{p_{l}+q_{l}}\,(p_{l}+q_{l})^{(p_{l}+q_{l})/2}$
$\displaystyle\;\geq$
$\displaystyle\;\operatorname{\medmath\prod}_{l=1}^{k}\mathbb{I}_{\\{p_{l}\equiv
q_{l}\,(\textrm{mod
}2)\\}}\,c^{p_{l}+q_{l}}\,(p_{l}+q_{l})^{(p_{l}+q_{l})/2}\;.$

This finishes the induction, and in particular implies

$\displaystyle(\alpha_{2}^{*}(k))^{2}\;\geq$
$\displaystyle\;c^{2m}\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\operatorname{\medmath\sum}_{\begin{subarray}{c}q_{1}+\ldots+q_{k}=m\\\
q_{1},\ldots,q_{k}\geq
1\end{subarray}}\operatorname{\medmath\prod}_{l=1}^{k}\mathbb{I}_{\\{p_{l}\equiv
q_{l}\,(\textrm{mod }2)\\}}\,(p_{l}+q_{l})^{(p_{l}+q_{l})/2}$
$\displaystyle\;\overset{(a)}{\geq}$
$\displaystyle\;c^{2m}\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\operatorname{\medmath\sum}_{\begin{subarray}{c}q_{1}+\ldots+q_{k}=m\\\
q_{1},\ldots,q_{k}\geq 1\end{subarray}}$
$\displaystyle\qquad\times\operatorname{\medmath\prod}_{l=1}^{k}\mathbb{I}_{\\{p_{l}\equiv
q_{l}\,(\textrm{mod
}2)\\}}\,\mfrac{(p_{l}+q_{l})^{(p_{l}+q_{l})/2}+(c^{\prime})^{p_{l}+q_{l}}(p_{l}+q_{l}+1)^{(p_{l}+q_{l}+1)/2}}{2}$
$\displaystyle\;\geq$
$\displaystyle\;(c^{\prime\prime})^{2m}\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\operatorname{\medmath\sum}_{\begin{subarray}{c}q_{1}+\ldots+q_{k}=m\\\
q_{1},\ldots,q_{k}\geq 1\end{subarray}}(p_{l}+q_{l})^{(p_{l}+q_{l})/2}$

for some absolute constant $c^{\prime\prime}>0$. In $(a)$, we have noted that

$\displaystyle(p_{l}+q_{l})^{(p_{l}+q_{l})/2}\;=$
$\displaystyle\;(p_{l}+q_{l})^{-1/2}(p_{l}+q_{l})^{(p_{l}+q_{l}+1)/2}$
$\displaystyle\;\geq$
$\displaystyle\;\big{(}(p_{l}+q_{l})^{-1/2}2^{-(p_{l}+q_{l}+1)/2}\big{)}(p_{l}+q_{l}+1)^{(p_{l}+q_{l}+1)/2}$
$\displaystyle\;\geq$
$\displaystyle\;(c^{\prime})^{p_{l}+q_{l}}(p_{l}+q_{l}+1)^{(p_{l}+q_{l}+1)/2}$

for some absolute constant $c^{\prime}>0$. On the other hand, by a triangle
inequality and noting that $Y_{i}$’s are i.i.d., we have

$\displaystyle\big{(}\alpha_{\nu}^{*}(k)\big{)}^{2}\;=$
$\displaystyle\;\bigg{\|}\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\,\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\bigg{\|}_{L_{\nu}}^{2}$
$\displaystyle\;\leq$
$\displaystyle\;\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\operatorname{\medmath\sum}_{\begin{subarray}{c}q_{1}+\ldots+q_{k}=m\\\
q_{1},\ldots,q_{k}\geq
1\end{subarray}}\Big{\|}\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{p_{l}}}\Big{\|}_{L_{\nu}}\Big{\|}\operatorname{\medmath\prod}_{l=1}^{k}\overline{Y_{l}^{q_{l}}}\Big{\|}_{L_{\nu}}$
$\displaystyle\;=$
$\displaystyle\;\operatorname{\medmath\sum}_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\operatorname{\medmath\sum}_{\begin{subarray}{c}q_{1}+\ldots+q_{k}=m\\\
q_{1},\ldots,q_{k}\geq
1\end{subarray}}\operatorname{\medmath\prod}_{l=1}^{k}\Big{\|}\overline{Y_{1}^{p_{l}}}\Big{\|}_{L_{\nu}}\Big{\|}\overline{Y_{1}^{q_{l}}}\Big{\|}_{L_{\nu}}\;.$

By noting that $\nu\leq 3$ and using the moment bound in Lemma 20, we get that
for some absolute constants $C^{\prime},C^{\prime\prime}>0$,

$\displaystyle\Big{\|}\overline{Y_{1}^{p}}\Big{\|}_{L_{\nu}}^{\nu}\Big{\|}\overline{Y_{1}^{q}}\Big{\|}_{L_{\nu}}^{\nu}\;=$
$\displaystyle\;\mathbb{E}\big{[}\big{|}Y_{1}^{p}-\mathbb{E}[Y_{1}^{p}]\big{|}^{\nu}\big{]}\mathbb{E}\big{[}\big{|}Y_{1}^{q}-\mathbb{E}[Y_{1}^{q}]\big{|}^{\nu}\big{]}$
$\displaystyle\;\leq$
$\displaystyle\;C^{\prime}\mathbb{E}[|Y_{1}|^{p\nu}]\mathbb{E}[|Y_{1}|^{q\nu}]\;\leq\;C^{\prime\prime}p^{p\nu/2}q^{q\nu/2}\;\leq\;C^{\prime\prime}(p+q)^{(p+q)\nu/2}\;.$

This implies that

$\displaystyle\big{(}\alpha_{\nu}^{*}(k)\big{)}^{2}\;\leq$
$\displaystyle\;\sum_{\begin{subarray}{c}p_{1}+\ldots+p_{k}=m\\\
p_{1},\ldots,p_{k}\geq
1\end{subarray}}\sum_{\begin{subarray}{c}q_{1}+\ldots+q_{k}=m\\\
q_{1},\ldots,q_{k}\geq
1\end{subarray}}\operatorname{\medmath\prod}_{l=1}^{k}(C^{\prime\prime})^{1/\nu}(p_{l}+q_{l})^{(p_{l}+q_{l})/2}\;\leq\;(c^{\prime\prime\prime})^{2m}\big{(}\alpha_{2}^{*}(k)\big{)}^{2}$

for some absolute constant $c^{\prime\prime\prime}>0$. (24) then becomes

$\displaystyle\mfrac{\operatorname{\medmath\sum}_{i=1}^{n}\big{\|}\partial_{i}\,q^{*}_{v;m}(\mathbf{W}_{Y;i})^{\top}\mathbf{Y}_{i}\big{\|}_{L_{\nu}}^{\nu}}{(\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})])^{\nu/2}}\;\leq$
$\displaystyle\;C_{3}\,n^{-\frac{\nu-2}{2}}\,\Bigg{(}\mfrac{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{\nu}^{*}(k))^{2}}{\sum_{k=1}^{m}\binom{n}{k}(\alpha_{2}^{*}(k))^{2}}\Bigg{)}^{\frac{\nu}{2}}\;\leq\;(c^{\prime\prime\prime})^{\nu
m}\,C_{3}\,n^{-\frac{\nu-2}{2}}\;.$

Plugging in this bound and (23) into (22), we get that

$\displaystyle\mfrac{\sum_{i=1}^{n}\big{\|}\partial_{i}\,q_{m}^{*}(\mathbf{W}_{i})^{\top}\mathbf{X}_{i}\big{\|}_{L_{\nu}}^{\nu}}{\big{(}\text{\rm
Var}[p_{m}^{*}(X)]\big{)}^{\nu/2}}\;\leq$
$\displaystyle\;\mfrac{C_{1}n^{-\frac{\nu-2}{2}}}{c_{2}^{\nu/2}}+4(c^{\prime\prime\prime})^{\nu
m}\,C_{3}\,n^{-\frac{\nu-2}{2}}\;\leq\;C^{m}n^{-\frac{\nu-2}{2}}$

for some absolute constant $C>0$. This finishes the proof. ∎

The next result allows $q^{*}_{m}(\Xi)+\mathbb{E}[p^{*}_{m}(X)]$ to be
approximated by $p^{*}_{m}(Z)$.

######  Lemma 22.

Let $C$ and $c$ be the absolute constants in the upper and lower bounds in
Lemma 20, and assume that $m\leq\delta(\log n)(2+\max\\{\log
c,0\\}+\max\\{\log C,0\\})^{-1}$ for some $\delta\in[0,1)$. Also assume that
$Z_{Y}$ and $\Xi_{\mathbf{Y}}$ are coupled such that $Z_{Y;i}=\xi_{Y;i1}$
almost surely. Then there exists some absolute constant $C^{\prime}>0$ such
that

$\displaystyle\mfrac{\|q^{*}_{m}(\Xi)+\mathbb{E}[p^{*}_{m}(X)]-p^{*}_{m}(Z)\|_{L_{2}}^{2}}{\text{\rm
Var}[q^{*}_{m}(\Xi)]}\;\leq\;\mfrac{(C^{\prime})^{m}}{n^{1-\delta}}\;.$

###### Proof of Lemma 22.

We first compute the quantities from (7) and (8) in the definition of
$\delta$-regularity, which can be bounded together as

$\displaystyle\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}$
$\displaystyle\max\bigg{\\{}\Big{(}\mathbb{E}\Big{[}n^{m/2}\operatorname{\medmath\prod}_{l=1}^{j}Y_{l}^{q_{l}}\Big{]}\Big{)}^{2}\,,\,\text{\rm
Var}\Big{[}n^{m/2}\operatorname{\medmath\prod}_{l=1}^{j}Y_{l}^{q_{l}}\Big{]}\bigg{\\}}$
$\displaystyle\;\leq\;n^{m}\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\Big{\|}\operatorname{\medmath\prod}_{l=1}^{j}Y_{l}^{q_{l}}\Big{\|}_{L_{2}}^{2}\;\;=\;\;n^{m}\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\operatorname{\medmath\prod}_{l=1}^{j}\|Y_{1}^{q_{l}}\|_{L_{2}}^{2}$
$\displaystyle\;\leq\;n^{m}\,\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\,\operatorname{\medmath\prod}_{l=1}^{j}\big{(}C(2q_{l})^{q_{l}}\big{)}\;\;\leq\;\;n^{m}\,(2C)^{m}\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\,\operatorname{\medmath\prod}_{l=1}^{j}q_{l}^{q_{l}}$

for some absolute constant $C>0$. Note that we have used independence followed
by Lemma 20 again, and that we only need to bound the above for $j\in[m-1]$.
We shall now perform an induction to show that

$\displaystyle
Q(j,m)\;\coloneqq\;\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\,\operatorname{\medmath\prod}_{l=1}^{j}q_{l}^{q_{l}}\;=\;(m-j+1)^{m-j+1}\;.$

This holds trivially for $j=1<m$. To prove this for $j\geq 2$ and $m>j$,
suppose the statement holds for all $j^{\prime}<j$ and all
$m^{\prime}>j^{\prime}$. By applying the pigeonhole principle, $q_{1}$ can
only take values in $[m-j+1]$, and

$\displaystyle Q(j,m)\;=$
$\displaystyle\;\max_{q_{1}\in[m-j+1]}q_{1}^{q_{1}}Q(j-1,m-q_{1})$
$\displaystyle\;=$
$\displaystyle\;\max_{q_{1}\in[m-j+1]}q_{1}^{q_{1}}(m-q_{1}-j+2)^{m-q_{1}-j+2}\;=\;\max_{q_{1}\in[m-j+1]}\psi_{m-j+2}(q_{1})\;,$

where we have denoted
$\psi_{m^{\prime}}(x)=x^{x}(m^{\prime}-x)^{m^{\prime}-x}$, defined for
$x\in[0,m^{\prime}]$. Since $\psi_{m^{\prime}}(x)$ is strictly convex with a
minimum at $x=m^{\prime}/2$, its maximum is obtained at the boundary, so

$\displaystyle
Q(j,m)\;=\;\psi_{m-j+2}(1)\;=\;(m-1-j+2)^{m-1-j+2}\;=\;(m-j+1)^{m-j+1}\;.$

This finishes the induction and implies that

$\displaystyle\max_{q_{1}+\ldots+q_{j}=m\,,\,q_{l}\in\mathbb{N}}\max\bigg{\\{}\Big{(}\mathbb{E}\Big{[}n^{m/2}\operatorname{\medmath\prod}_{l=1}^{j}Y_{l}^{q_{l}}\Big{]}\Big{)}^{2}\,,\,\text{\rm
Var}\Big{[}n^{m/2}\operatorname{\medmath\prod}_{l=1}^{j}Y_{l}^{q_{l}}\Big{]}\bigg{\\}}$
$\displaystyle\;\leq\;n^{m}\,(2C)^{m}\,m^{m-j+1}$
$\displaystyle\;\leq\;n^{m}\,(2\max\\{C,1\\})^{m}\,m^{m-j+1}c^{m}m^{-m}\text{\rm
Var}[v^{*}_{m}(Y)]$
$\displaystyle\;\leq\;(4\max\\{c,1\\}\max\\{C,1\\})^{m}n^{m}m^{-j}\text{\rm
Var}[v^{*}_{m}(Y)]$ $\displaystyle\;=\;e^{m(\log 4+\max\\{\log
c,0\\}+\max\\{\log C,0\\})}n^{m}m^{-j}\text{\rm Var}[v^{*}_{m}(Y)]$
$\displaystyle\;<\;e^{m(2+\max\\{\log c,0\\}+\max\\{\log
C,0\\})}n^{m}m^{-j}\text{\rm Var}[v^{*}_{m}(Y)]$
$\displaystyle\;\leq\;n^{m+\delta}m^{-j}\text{\rm Var}[v^{*}_{m}(Y)]\;,$

where we have used the assumption on $m$ in the last line. This implies that
$v^{*}_{m}$ in (6) is $\delta$-regular with respect to $Y$. By Lemma 6, there
is some absolute constant $C^{\prime}>0$ such that

$\displaystyle\mfrac{\|q^{*}_{v;m}(\Xi_{\mathbf{Y}})+\mathbb{E}[v^{*}_{m}(Y)]-v^{*}_{m}(Z_{Y})\|_{L_{2}}^{2}}{\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})]}\;\leq\;\mfrac{(C^{\prime})^{m}}{n^{1-\delta}}\;.$

Recall that
$v^{*}_{m}(Z_{Y})-\mathbb{E}[v^{*}_{m}(Y)]=p^{*}_{m}(Z)-\mathbb{E}[p^{*}_{m}(X)]-v^{*}_{1}(Z_{V})$
and, by the coupling assumption,
$q^{*}_{v;m}(\Xi_{\mathbf{Y}})=q^{*}_{m}(\Xi)-v^{*}_{1}(Z_{V})$ . Also, since
$v^{*}_{m}(Y)=\big{(}n^{-1/2}\sum_{i=1}^{n}Y_{i}\big{)}^{m}\overset{d}{=}Y_{1}^{m}$,
by Lemma 20, $\text{\rm Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})]=\text{\rm
Var}[v^{*}_{m}(Y)]>c^{m}\,(2m)^{m}$ for some absolute constant $c>0$. These
imply the desired bound that

$\displaystyle\mfrac{\|q^{*}_{v;m}(\Xi)-(p^{*}_{m}(Z)-\mathbb{E}[p^{*}_{m}(X)])\|_{L_{2}}^{2}}{\text{\rm
Var}[f^{*}(\Xi)]}\;=\;\mfrac{\|q^{*}_{v;m}(\Xi_{\mathbf{Y}})+\mathbb{E}[v^{*}_{m}(Y)]-v^{*}_{m}(Z_{Y})\|_{L_{2}}^{2}}{\text{\rm
Var}[v^{*}_{1}(Z_{V})]+\text{\rm
Var}[q^{*}_{v;m}(\Xi_{\mathbf{Y}})]}\;\leq\;\mfrac{(C^{\prime})^{m}}{n^{1-\delta}}\;.$

∎

Let $X^{\prime}$ and $Y^{\prime}$ be two real-valued random variables. We will
make use of the following bound for controlling the influence of $Y^{\prime}$
on $X^{\prime}+Y^{\prime}$.

######  Lemma 23.

For any $a,b\in\mathbb{R}$ and $\epsilon>0$, we have

$\displaystyle\mathbb{P}(a\leq X^{\prime}+Y^{\prime}\leq
b)\;\leq\;\mathbb{P}(a-\epsilon\leq X^{\prime}\leq
b+\epsilon)+\mathbb{P}(|Y^{\prime}|\geq\epsilon)\;,$
$\displaystyle\mathbb{P}(a\leq X^{\prime}+Y^{\prime}\leq
b)\;\geq\;\mathbb{P}(a+\epsilon\leq X^{\prime}\leq
b-\epsilon)-\mathbb{P}(|Y^{\prime}|\geq\epsilon)\;.$

###### Proof of Lemma 23.

By conditioning on the size of $Y$, we have

$\displaystyle\mathbb{P}(a\leq X^{\prime}+Y^{\prime}\leq b)\;=$
$\displaystyle\;\mathbb{P}(a\leq X^{\prime}+Y^{\prime}\leq
b\,,\,|Y^{\prime}|\leq\epsilon)+\mathbb{P}(a\leq X^{\prime}\leq
b\,,\,|Y^{\prime}|\geq\epsilon)$ $\displaystyle\;\leq$
$\displaystyle\;\mathbb{P}(a-\epsilon\leq X^{\prime}\leq
b+\epsilon)+\mathbb{P}(|Y^{\prime}|\geq\epsilon)\;,$

and by using the order of inclusion of events, we have the lower bound

$\displaystyle\mathbb{P}(a\leq X^{\prime}+Y^{\prime}\leq b)\;\geq$
$\displaystyle\;\mathbb{P}(a+\epsilon\leq X^{\prime}\leq
b-\epsilon\,,\,|Y^{\prime}|\leq\epsilon)$ $\displaystyle\;=$
$\displaystyle\;\mathbb{P}(a+\epsilon\leq X^{\prime}\leq