# Training Guarantees of Neural Network Classification Two-Sample Tests by
Kernel Analysis

Varun Khurana111Department of Applied Mathematics, Brown University,
Providence, RI 02906. Xiuyuan Cheng222Department of Mathematics, Duke
University, Durham, NC, 27708. Alexander Cloninger333Department of Mathematics
and Halicioğlu Data Science Institute, University of California, San Diego,
San Diego, CA, 92093.

###### Abstract

We construct and analyze a neural network two-sample test to determine whether
two datasets came from the same distribution (null hypothesis) or not
(alternative hypothesis). We perform time-analysis on a neural tangent kernel
(NTK) two-sample test. In particular, we derive the theoretical minimum
training time needed to ensure the NTK two-sample test detects a deviation-
level between the datasets. Similarly, we derive the theoretical maximum
training time before the NTK two-sample test detects a deviation-level. By
approximating the neural network dynamics with the NTK dynamics, we extend
this time-analysis to the realistic neural network two-sample test generated
from time-varying training dynamics and finite training samples. A similar
extension is done for the neural network two-sample test generated from time-
varying training dynamics but trained on the population. To give statistical
guarantees, we show that the statistical power associated with the neural
network two-sample test goes to 1 as the neural network training samples and
test evaluation samples go to infinity. Additionally, we prove that the
training times needed to detect the same deviation-level in the null and
alternative hypothesis scenarios are well-separated. Finally, we run some
experiments showcasing a two-layer neural network two-sample test on a hard
two-sample test problem and plot a heatmap of the statistical power of the
two-sample test in relation to training time and network complexity.

##  1 Introduction

The ability to compare whether two datasets $\widehat{P}\sim p$ and
$\widehat{Q}\sim q$ came from the same data-generating process (i.e. checking
if $p=q$ or $p\neq q$) is a problem studied for many years. Traditionally, the
methods to answer this question are called two-sample tests. As a non-
exhaustive list of applications, two-sample testing is widely used in testing
drug efficacy [12], studying behavioral differences in psychology [4],
pollution impact studied in environmental science research [5], and market
research impact studies [6]. The most basic method to compare distributions is
by comparing means with a $t$-test, proportions with a $z$-test, variances
with Levene’s test, medians with a Mann-Whitney U test, or overall
distributions with a Kolmogorov-Smirnov test. The advent of complex, high-
dimensional data in fields like genomics, finance, and social media analytics
has exposed limitations in these traditional methods, particularly in terms of
handling non-linearity, complex interactions, and the curse of dimensionality.
The flexibility and scalability of neural networks make them particularly
suited to tackle the challenges posed by modern datasets, suggesting their
potential to revolutionize two-sample testing.

This paper is not the first to explore the idea of using neural networks or
classifiers for two-sample testing. In particular, [23] showed properties and
analyzed the performance of the so-called Classifier Two-Sample Test (C2ST)
and specifically showcasing theoretically what the statistical power of such
two-sample tests. To go further in the neural network direction, [9] expanded
[15]’s work and used the neural tangent kernel (NTK) for the kernel involved
in a maximum mean discrepancy (MMD) problem. Yet their analysis still did not
relate the NTK MMD performance to the behavior of neural network
classification two-sample tests. Moreover, [7] introduced a neural network-
based two sample test statistic using the classification logit and showed
theoretical guarantees for test power for sub-exponential density problems.
One may be hesitant to use a neural network for two-sample tests since with a
big enough neural network and long enough training time, a neural network
could find a separation for data coming from the same distribution. Our
approach alleviates this hesitation since we train the neural network on a
small time-scale and ensure our network is initialized to output 0 for all
values. We also conduct time analysis on two levels. First, we analyze the
time needed for achieving a desired level of deviation or detection in the
two-sample test. Second, we provide time approximations between different
training regimes, which extends the analysis of the time needed for detection
to different training regimes.

###  1.1 Main Contributions

Our main contributions to the field are the following:

  1. 1.

We perform some time analysis on the neural tangent kernel (NTK) derived from
our neural network and show that the time it takes for the neural network two-
sample test to learn does not depend on the entire spectrum of the NTK but
rather only a subset of the spectrum on which the labels or witness function
$f^{*}=\frac{p-q}{p+q}$ non-trivially projects onto. This behavior is a result
of averaging behavior of the neural network two-sample test.

  2. 2.

We approximate the population-level neural network dynamics and finite-sample
neural network dynamics with the population-level NTK dynamics. This allows
the time analysis performed on the NTK dynamics to transfer to the other two
training regimes. Additionally, we notice here that there is a balancing act
of not training the neural network too long so that the the approximations
hold but long enough to detect differences in the datasets. This balancing act
is further informed by the complexity of the neural network considered in
relation to the difficulty of the two-sample test problem.

Our main result essentially shows that as long as $p$ and $q$ are “separated
enough”, our neural network two-sample test can detect the difference before
the same detection would take place if $p=q$. This idea comes about as test
power analysis and test time analysis. In particular, we can summarize the
main result of value as the following two informal theorems. Here, let
$\widehat{T}$ denote the neural network two-sample test.

######  Theorem 1.1 (Informal Test Power Analysis).

For particular type 1 error

$\displaystyle\mathbb{P}(\widehat{T}>\tau|H_{0})=\alpha,$

where $\alpha$ is the power level, the statistical power goes to 1, i.e. we
have

$\displaystyle\mathbb{P}\Big{(}\widehat{T}>\tau\big{|}\begin{subarray}{c}f^{*}\text{nontrivially
projects onto first $k$}\\\ \text{eigenfunctions of zero-time NTK
$K_{0}$}\end{subarray}\Big{)}\to 1,$

as the training and test samples sizes go to $\infty$.

######  Theorem 1.2 (Informal Test Time Analysis).

Assume that $f^{*}$ nontrivially projects onto only the first $k$
eigenfunctions of the zero-time NTK $K_{0}$. Consider a desired detection
level $\epsilon>0$ and time separation level $C\epsilon\geq\gamma>0$. Further
assume that the projection of $f^{*}$ onto the first $k$ eigenfunctions has a
“large enough norm/energy.” Then with high probability,

$\displaystyle t^{+}(\epsilon)-t^{-}(\epsilon)\geq\gamma>0,$

where $t^{-}(\epsilon)$ and $t^{+}(\epsilon)$ are the minimum times needed for
the neural network two-sample test to detect a deviation $\epsilon$ when
$f^{*}$ projects onto the first $k$ eigenfuctions and the null hypothesis,
respectively.

In the formal versions of these theorem (as shown in Corollary 6.10 and
Corollary 6.9, respectively), the detection level $\epsilon>0$ possible is
perturbed by a time-approximation error between the actual neural network two-
sample test and the zero-time NTK two-sample test. This adds a small amount of
complexity to the informal theorem above and there are lower bound conditions
on $f^{*}$ to ensure detectability. We also discuss (in a subsequent remark to
Corollary 6.9) which detection level is the most trustworthy. A visual for
this graph is given in Figure 1.

Figure 1: Visual for detection levels $t^{+}(\epsilon)$ and $t^{-}(\epsilon)$
being well-separated.

The efficacy of neural network-based two-sample tests hinges on the dynamics
of training and network complexity. A key insight is that as soon as gradient
descent begins, the two-sample test becomes significantly more effective. To
illustrate this, we work out a toy example in Section 3.1 where we distinguish
between two multivariate normal distributions with identical covariance
matrices but different means. Utilizing a simple linear neural network, we
show that even a single gradient descent step can markedly improve the test’s
ability to detect differences in distributions. This improvement is rooted in
how the network parameters adjust to reflect the underlying statistical
properties of the data, thereby enhancing the test’s sensitivity. In the
broader analysis done in later chapters, we show the theory that balances
small training time scales with network complexity to ensure our two-sample
test works well.

###  1.2 Structure of the paper

We review some papers in Section 2 that study the same topic that we explore
in this paper. We discuss specifics of how the training time-scale interplays
with the network complexity in Section 2.2. In Section 3, we introduce the
main notation, a motivating example, and concepts that we will need for the
rest of the paper.

In Section 4, we describe in detail three training dynamics that we consider
for the two-sample test. First, we consider the case of realistic (finite-
sample time-varying) dynamics; second, we consider population (population-
level time-varying) dynamics; and finally, we consider the zero-time neural
tangent kernel (NTK) auxiliary dynamics, where the analysis is easier to
understand. The population dynamics offer useful insight into the limit of the
realistic dynamics as the number of samples increases. We emphasize that the
results for the realistic and population dynamics scenarios are similar, but
the realistic dynamics require more care to work out the analogous results as
the population dynamics. For the zero-time NTK auxiliary dynamics, we conduct
a full analysis in Section 4.3. By solving for the actual solution of the
zero-time NTK dynamics, we are able to find an exact form for the two-sample
test in this regime by using the spectrum of the NTK. The exact form of the
two-sample test further allows us to conduct some time analysis. The time
analysis is done to show guarantees for when the null hypothesis is correct or
when the alternative hypothesis is correct. For the alternative hypothesis, we
can estimate the minimum time needed for sensing an error level $\epsilon>0$.
For the null hypothesis statement, we can estimate the maximum time needed
before we are able to sense past an error level $\epsilon>0$. Using proof
techniques similar to [25], these time-analysis results are adapted later to
the other training settings by using approximation and estimation between the
different settings.

Section 5 estimates both the realistic and population dynamics with the zero-
time NTK dynamics. The approximation guarantees between the realistic and
zero-time NTK dynamics hold up to a factor of $t^{5/2}$ and depends on how
many data points are sampled from both $p$ and $q$ whilst the population
dynamics are approximated by the zero-time NTK dynamics up to a factor of
$t^{3/2}$, where $t$ denotes time. We additionally approximate the two-sample
statistics in the realistic and population dynamics scenarios with the zero-
time NTK two-sample statistic. Finally, we show the two-sample statistic in
the realistic and populations dynamics case are monotonically increasing under
mild assumptions.

In Section 6, we extend the time analysis done for the zero-time NTK dynamics
situation to the realistic dynamics (Section 6.2) and population dynamics
(Section 6.1) cases. These extensions depends heavily on the results of
Section 5. For the reader wishing to delve into the proofs, the actual proofs
of the realistic dynamics and population dynamics cases are written in
sequential progression in Appendix C and Appendix B. The process of extending
the time analysis requires using the approximations from Section 5 together
with the time analysis theorems in Section 4.3. In particular, if the zero-
time NTK dynamics two-sample test are able to detect $f^{*}$ faster than the
approximation guarantees of Section 5, then all the time analysis for the NTK
auxiliary dynamics also holds for the realistic and population two-sample
tests.

The results shown in Section 6.2 and Section 6.1 showcase that our neural
network two-sample test is more useful in identifying when the alternative
hypothesis is correct. Moreover, we see a sort of balancing act of training on
short time scales and increasing the complexity of the neural network. These
specifics are discussed in more detail in Section 2.2. Finally, in Section 7
we show empirical evidence of the statistical power of the neural network two-
sample test on a hard two-sample test problem.

##  2 Previous Works and Our Work

###  2.1 Previous Works

#### Classification and two-sample testing.

As mentioned, classifier two-sample tests are not new [15, 23, 14]. These
approaches demonstrated that a well-trained classifier could effectively
identify distributional discrepancies. More traditional two-sample methods use
methods such as kernel two-sample test and maximum mean discrepancy (MMD) [15,
8, 26, 19] but adhere to the classification two-sample test spirit. More
recently, there has been growing interest in developing two-sample tests based
on neural networks, leveraging the power of deep learning to address some of
the limitations of classical two-sample tests [22, 7, 20, 11]. [3] applied MMD
to generative adversarial netowrks (GANs) for imporoved distribution
comparison. Kernel MMD was also extended to the neural tangent kernel (NTK)
for two-sample testing by [9]. Variations of a neural network-based two-sample
test are present in [18] and [7]. The analysis done in this paper goes further
by using small time approximations between the NTK-based kernel machines and
the actual neural network training dynamics. To accomplish this, we use very
similar proof techniques to [25], but rather than using a loss rescaling to
get into the lazy training regime [10], we are able to use small time
approximations for the NTK.

#### Neural Tangent Kernels.

We heavily use the neural tangent kernel (NTK) in this paper for tractable
analysis which is extended to realistic dynamics for the actual trained neural
network. The concept of NTKs comes from the seminal work of [17], who
demonstrated that training dynamics of a neural network can be approximated by
a kernel method, where the kernel is the NTK. Many studies have extended and
refined NTK theory since the seminal work. [2] extended the NTK analysis to
convolutional neural networks and showed how NTKs evolve during training.
Other works [21, 13, 1, 24, 10] have studied the hierarchical structure of
NTKs, convergence guarantees for training over-parameterized neural networks,
and implicit regularization effects of NTKs. Many of these works simplify the
NTK with either a large-width assumption or a small-time assumption where the
NTK dynamics and neural network dynamics are similar. For this paper, our
neural network must be large enough to capture the target function $f^{*}$ but
small enough to ensure small-time approximation holds between the NTK and the
true neural network.

###  2.2 Difference of Our Work from Previous NTK Literature

Our NTK analysis introduces a novel perspective by balancing time scales and
network complexity, distinguishing it from traditional NTK analysis.
Specifically, we focus on the small-time regime to assess the two-sample test,
which aims to identify when the alternative hypothesis is correct. Our
approach relates the training time to the complexity of the zero-time NTK and
the projection of the weighted difference of densities $\frac{p-q}{p+q}(x)$
onto the zero-time NTK’s eigenfunctions. We analyze both population-level and
finite-sample dynamics in relation to the zero-time NTK, ensuring our
approximations hold within this short-time regime. This delicate balance
depends on the problem’s complexity and the neural network’s complexity.

Consider the scenario where the densities $p$ and $q$ are significantly
different. If the zero-time NTK’s larger eigenvalue functions correspond to
low-frequency eigenfunctions, the two-sample test can produce positive results
quickly since $\frac{p-q}{p+q}$ will likely project onto low-frequency
eigenfunctions. Conversely, when $p$ and $q$ are similar, $\frac{p-q}{p+q}$
projects onto higher frequency eigenfunctions, requiring more time or a larger
neural network for detection.

Moreover, balancing short-time and long-time scales necessitates managing
neural network complexity. The complexity must be sufficient to capture
$\frac{p-q}{p+q}$ on the NTK’s eigenbasis, but the estimation accuracy of the
zero-time NTK decreases with larger networks. Fortunately, the approximation
depends on the product of neural network complexity and time, which allows for
good detection even with small time scales, counteracting approximation
losses.

Our empirical results span neural networks with various parameter-to-sample
ratios, from severely under-parameterized to highly over-parameterized
regimes, demonstrating the robustness of our NTK analysis in different
settings.

##  3 Notation and Background

We will study a neural network two-sample test, which will test whether two
datasets came from the same distribution or not. In particular, assume that we
are given datasets $X=\\{x_{i}\\}_{i=1}^{n_{p}}\subseteq\mathbb{R}^{d}$ and
$Z=\\{z_{j}\\}_{j=1}^{n_{q}}\subseteq\mathbb{R}^{d}$. We will endow samples
from $X$ to have labels $1$ whilst samples from $Z$ will have labels $-1$. To
give some more structure to our problem, we will moreover assume that the
datasets $X$ and $Z$ are sampled from distributions $p(x)dx$ and $q(x)dx$,
respectively, where $p$ and $q$ are associated density functions. From $X$ and
$Z$, note that we can construct finite-sample empirical measures

$\displaystyle\widehat{p}(x)dx=\frac{1}{n_{p}}\sum_{i=1}^{n_{p}}\delta_{x_{i}}(x)dx$
$\displaystyle\widehat{q}(x)dx=\frac{1}{n_{q}}\sum_{j=1}^{n_{q}}\delta_{z_{j}}(x)dx$

respectively. In the same fashion, we can assume that we are given independent
test samples from each of $p$ and $q$ to generate
$X_{test}=\\{x_{i}^{*}\\}_{i=1}^{m_{p}}$ and
$Z_{test}=\\{z_{j}\\}_{j=1}^{m_{q}}$ as well as corresponding test empirical
measures $\widehat{p}_{test}(x)dx$ and $\widehat{q}_{test}(x)dx$. These test
sets will be used when considering the finite-sample two-sample test on test
data. We now introduce the following notation

$\displaystyle\|f\|_{L^{2}(p+q)}=\bigg{(}\int_{\mathbb{R}^{d}}|f(x)|^{2}(p(x)+q(x))dx\bigg{)}^{1/2}$
$\displaystyle\|f\|_{L^{2}(\widehat{p}+\widehat{q})}=\bigg{(}\int_{\mathbb{R}^{d}}|f(x)|^{2}(\widehat{p}(x)+\widehat{q}(x))dx\bigg{)}^{1/2}.$

Assume that our neural network architecture has associated parameters space
$\Theta\subseteq\mathbb{R}^{M_{\Theta}}$ so that our neural network is given
as $f:\mathbb{R}^{d}\times\Theta\to\mathbb{R}$ and will be trained on an
$\ell_{2}$ loss function against the labels as shown here

$\displaystyle\widehat{L}(\theta)$
$\displaystyle=\frac{1}{2}\bigg{(}\frac{1}{n_{p}}\sum_{i=1}^{n_{p}}\big{(}f(x_{i},\theta)-1\big{)}^{2}+\frac{1}{n_{q}}\sum_{j=1}^{n_{q}}\big{(}f(z_{j},\theta)+1\big{)}^{2}\bigg{)}$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)-1\big{)}^{2}\widehat{p}(x)dx+\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)+1\big{)}^{2}\widehat{q}(x)dx\bigg{)}.$

As a precursor to the more concrete notation introduced in Section 4, we will
use the general rule of thumb of distinguishing mathematical objects in
different training dynamics by:

  1. 1.

Realistic (finite-sample time-varying) mathematical objects are adorned with
hats, such as $\widehat{u}$.

  2. 2.

Population (population-level time-varying) mathematical objects are not
adorned with any specific notation, such as $u$.

  3. 3.

Auxillary NTK (population-level zero-time NTK) mathematical objects are
adorned with bars, such as $\overline{u}$.

The notation for these different training dynamics used in Section 4 is
represented in Table 1.

Notation | Realistic | Population | Auxillary NTK
---|---|---|---
Params | $\widehat{\theta}(t)$ | $\theta(t)$ | $\theta_{0}=\theta(0)$
Output | $\widehat{u}(x,t)=f(x,\widehat{\theta}(t))$ | $u(x,t)=f(x,\theta(t))$ | $\overline{u}(x,t)$
Statistic | $\widehat{T}_{train}(t),\widehat{T}_{test}(t),\widehat{T}_{pop}(t)$ | $T(t)$ | $\overline{T}(t)$
Kernel | $\widehat{K}_{t}(x,x^{\prime})$ | $K_{t}(x,x^{\prime})$ | $K_{0}(x,x^{\prime})$
Error | $\begin{subarray}{c}\widehat{e}_{p}(x,t)=\widehat{u}(x,t)-1\\\ \widehat{e}_{q}(x,t)=\widehat{u}(x,t)+1\end{subarray}$ | $e=u-f^{*}$ | $\overline{e}=\overline{u}-\Pi_{K_{0}}(f^{*})$
Table 1: Overview of notation used for three training dynamics.

###  3.1 Motivating Example

For our motivating example two-sample test scenario, we consider when our
probability distributions of interest are two multivariate normals with the
same covariance matrix but different means. In particular, with a fixed
covariance matrix $\Sigma$, we let $p\sim N(\mu_{1},\Sigma)$ and $q\sim
N(\mu_{2},\Sigma)$ with labels $1$ and $-1$ respectively. Assume that we work
with a linear neural network given by

$\displaystyle f(x;a,W,b)=\frac{1}{M_{\Theta}}a^{\top}\Big{(}Wx+b\Big{)}$

where $x\in\mathbb{R}^{d},a\in\mathbb{R}^{M_{\Theta}}$,
$W\in\mathbb{R}^{M_{\Theta}\times d}$, and $b\in\mathbb{R}^{M_{\Theta}}$. For
ease assume that $M_{\Theta}$ is even, then for initialization, let $b=0$ and
opt to make $a_{i}=1$ for $i\leq M_{\Theta}/2$ and $a_{i}=-1$ otherwise. For
$W$, we will generate a random matrix
$\widetilde{W}\in\mathbb{R}^{(M_{\Theta}/2)\times d}$ and let
$W=\begin{bmatrix}\widetilde{W}\\\ -\widetilde{W}\end{bmatrix}$. These choices
will ensure that $f(x)=0$ for all $x$.

Recall the gradient of $f$ with respect to its parameters is given by

$\displaystyle\frac{\partial f}{\partial a}(x)=\frac{1}{M_{\Theta}}(Wx+b)$
$\displaystyle\frac{\partial f}{\partial W}(x)=\frac{1}{M_{\Theta}}ax^{\top}$
$\displaystyle\frac{\partial f}{\partial b}(x)=\frac{1}{M_{\Theta}}a.$

We will show that just one population-level gradient descent step with this
setup will allow the two-sample test to detect the difference in distributions
with high probability. In particular, recall that with our initialization

$\displaystyle\frac{\partial\widehat{L}(\theta_{0})}{\partial
f}(x)=\begin{cases}-1&x\sim p\\\ 1&x\sim q\end{cases}.$

Now with learning rate $\eta$, one gradient descent step gives us

$\displaystyle a^{(1)}$ $\displaystyle=a-\eta\int\frac{\partial f}{\partial
a}(x)\frac{\partial\widehat{L}}{\partial f}(x)d(p+q)(x)$
$\displaystyle=a-\eta\int\frac{1}{M_{\Theta}}Wxd(q-p)(x)=a-\frac{\eta}{M_{\Theta}}W(\mu_{2}-\mu_{1})$
$\displaystyle W^{(1)}$ $\displaystyle=W-\eta\int\frac{\partial f}{\partial
W}(x)\frac{\partial\widehat{L}}{\partial f}(x)d(p+q)(x)$
$\displaystyle=W-\eta\int\frac{1}{M_{\Theta}}ax^{\top}d(q-p)(x)=W-\frac{\eta}{M_{\Theta}}a(\mu_{2}-\mu_{1})^{\top}$
$\displaystyle b^{(1)}$ $\displaystyle=b-\eta\int\frac{\partial f}{\partial
b}(x)\frac{\partial\widehat{L}}{\partial f}(x)d(p+q)(x)$
$\displaystyle=b-\eta\int\frac{1}{M_{\Theta}}ad(q-p)(x)=b-0=0.$

This means that after the first gradient descent step, we have

$\displaystyle f(x;a^{(1)},W^{(1)},0)$
$\displaystyle=\bigg{(}a-\frac{\eta}{M_{\Theta}}W(\mu_{2}-\mu_{1})\bigg{)}^{\top}\Bigg{(}\bigg{(}W-\frac{\eta}{M_{\Theta}}a(\mu_{2}-\mu_{1})^{\top}\bigg{)}x\Bigg{)}$
$\displaystyle=\frac{\eta}{M_{\Theta}}\bigg{(}\|a\|^{2}\langle\mu_{1}-\mu_{2},x\rangle+\langle
W(\mu_{1}-\mu_{2}),Wx\rangle$ $\displaystyle+\frac{\eta}{M_{\Theta}}\langle
a,W(\mu_{2}-\mu_{1})\rangle\langle\mu_{2}-\mu_{1},x\rangle\bigg{)}.$

Now notice that if we consider the two-sample test

$\displaystyle\int f(x;a^{(1)},W^{(1)},0)d(p-q)(x)$
$\displaystyle=\frac{\eta}{M_{\Theta}}\bigg{(}\|a\|^{2}\|\mu_{1}-\mu_{2}\|^{2}+\|W(\mu_{1}-\mu_{2})\|$
$\displaystyle+\frac{\eta}{M_{\Theta}}\langle
a,W(\mu_{1}-\mu_{2})\rangle\|\mu_{1}-\mu_{2}\|\bigg{)}.$

In essence, if $\eta$ is small enough the two-sample test will be positive and
the farther $\mu_{1}$ is away from $\mu_{2}$, the easier it becomes to detect.

In the case that we have $W$ fixed and $M_{\Theta}$ is large, we can see that
$a$ is trying to learn $W(\mu_{1}-\mu_{2})$. From a qualitative point of view,
we only really need one row $w$ of $W$ to form a hyperplane that separates
$\mu_{1}$ and $\mu_{2}$, assuming that $0,\mu_{1},\mu_{2}$ do not all fall on
the same line (and $\mu_{1}$ and $\mu_{2}$ are not on opposite sides of 0).
Moreover, the larger we pick $M_{\Theta}$, the random matrix $W$ gets a
greater probability of producing such a row $w$. Moreover, producing such a
$w$ becomes increasingly more likely when we center the data so that the
origin is between the two means.

###  3.2 Relating Finite-sample and Population-level Loss

We now revert to the more general case of neural networks considered and
recall the form of $\widehat{L}(\theta)$. Notice that when
$n_{p},n_{q}\to\infty$, we get a population-level loss given by

$\displaystyle L(\theta)$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)-1\big{)}^{2}p(x)dx+\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)+1\big{)}^{2}q(x)dx\bigg{)}$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)^{2}p(x)-2f(x,\theta)p(x)+p(x)$
$\displaystyle+f(x,\theta)^{2}q(x)+2f(x,\theta)q(x)+q(x)\big{)}dx\bigg{)}$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)^{2}-2f(x,\theta)\underbrace{\frac{p(x)-q(x)}{p(x)+q(x)}}_{f^{*}((x)}+1\big{)}(p(x)+q(x))dx\bigg{)}.$

Here we can notice that

$\displaystyle\|f(\cdot,\theta)-f^{*}(\cdot)\|_{L^{2}(p+q)}^{2}=\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)^{2}-2f(x,\theta)f^{*}(x)+(f^{*}(x))^{2}\big{)}(p(x)+q(x))dx.$

If we add the constant

$\displaystyle
C=\frac{1}{2}\int_{\mathbb{R}^{d}}4\frac{p(x)q(x)}{p(x)+q(x)}dx,$

we get that

$\displaystyle
L(\theta)=\frac{1}{2}\|f(\cdot,\theta)-f^{*}(\cdot)\|_{L^{2}(p+q)}^{2}+C.$

To see this, notice that

$\displaystyle\frac{1}{2}\int_{\mathbb{R}^{d}}\Big{(}(f^{*}(x))^{2}(p(x)+q(x))+\frac{4p(x)q(x)}{p(x)+q(x)}\Big{)}dx$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}\Big{(}\frac{(p(x)-q(x))^{2}}{(p(x)+q(x))^{2}}(p(x)+q(x))+\frac{4p(x)q(x)}{p(x)+q(x)}\Big{)}dx$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}\Big{(}\frac{p(x)^{2}-2p(x)q(x)+q(x)^{2}+4p(x)q(x)}{p(x)+q(x)}\Big{)}dx$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}^{d}}\Big{(}\frac{(p(x)+q(x))^{2}}{p(x)+q(x)}\Big{)}dx=\frac{1}{2}\int_{\mathbb{R}^{d}}p(x)+q(x)dx.$

This means that minimizing $L(\theta)$ is the same as minimizing
$\|f-f^{*}\|_{L^{2}(p+q)}^{2}$ as the constant doesn’t depend on $\theta$.
Importantly, this means that our target function in the population-level
training regimes will be

$\displaystyle f^{*}(x):=\frac{p(x)-q(x)}{p(x)+q(x)}.$

###  3.3 Two-Sample Test

Given probability densities $p$ and $q$, the two-sample test assesses whether
to accept the null hypothesis $H_{0}$ or reject it for $H_{1}$, where

$\displaystyle H_{0}:p=q,\hskip 85.35826ptH_{1}:p\neq q.$

In words, our test is constructed using the average output of the neural
network on measure $p$ minus the average output of the neural network on
measure $q$. This will give either population-level two-sample tests or
finite-sample two-sample tests on the datasets $X_{test}$ and $Z_{test}$. In
particular, for the population-level statistic, we can define

$\displaystyle\mu_{p}(\theta)=\int_{\mathbb{R}^{d}}f(x,\theta)dp(x),\hskip
8.5359pt\mu_{q}(\theta)=\int_{\mathbb{R}^{d}}f(x,\theta)dq(x)$ $\displaystyle
T(\theta;p,q)=(\mu_{p}(\theta)-\mu_{q}(\theta))=\int_{\mathbb{R}^{d}}f(x,\theta)d(p-q)(x);$

whereas, for the finite-sample statistic on test data, we can define

$\displaystyle\mu_{\widehat{p}_{test}}(\theta)=\int_{\mathbb{R}^{d}}f(x,\theta)d\widehat{p}_{test}(x),\hskip
8.5359pt\mu_{\widehat{q}_{test}}(\theta)=\int_{\mathbb{R}^{d}}f(x,\theta)d\widehat{q}_{test}(x)$
$\displaystyle
T(\theta;\widehat{p}_{test},\widehat{q}_{test})=(\mu_{\widehat{p}_{test}}(\theta)-\mu_{\widehat{q}_{test}}(\theta))=\int_{\mathbb{R}^{d}}f(x,\theta)d(\widehat{p}_{test}-\widehat{q}_{test})(x).$

Here, we define the neural network two-sample test for a neural network
$f(\cdot,\theta)$ by $T(\theta;\widehat{p}_{test},\widehat{q}_{test})$. Given
a test threshold $\tau>0$, we reject the null hypothesis if
$|T(\theta;\widehat{p}_{test},\widehat{q}_{test})|>\tau$. Moreover, we control
the false discovery of the null by finding the smallest $\tau$ such that
$\text{Pr}[|T(\theta;\widehat{p}_{test},\widehat{q}_{test})|>\tau|H_{0}]\leq\alpha$,
where $0<\alpha<1$ is the significance level. To find $\tau$, we use a
permutation test.

In Section 4, we will consider different training regimes and each of these
training regimes will have different notions of the two-sample test, which
change by what the output of the neural network is and which probability
measures the two-sample test statistic is computed on. Particularly, the
training regime with the zero-time NTK will end up using not the neural
network by the function that is trained under zero-time NTK dynamics. The
specific notation regarding the two-sample test will be discussed there.

##  4 The Three Training Dynamics

We will consider the following three different training dynamics for our
neural network. For all of scenarios, however, we assume the following.

######  Assumption 4.1.

The neural network is initialized with parameters $\theta_{0}$ such that
$f(x,\theta_{0})=0$ for all $x\in\mathbb{R}^{d}$.

For the benefit of the reader, Figure 2 provides a roadmap of how the test
time and power theorems are proven and the dependencies inherent for the
results. Importantly, Figure 2 explains that most of the approximated results
for the realistic and population dynamics depend on the exact results of the
zero-time NTK auxiliary dynamics. The longest and most technical result of the
roadmap is Proposition 5.11.

Figure 2: Roadmap of Theory and Results. Blue denotes zero-time NTK auxiliary
dynamics, gray denotes population dynamics, and red denotes realistic
dynamics.

###  4.1 Realistic Dynamics

These finite-sample time-varying dynamics are the most realistic as these are
the dynamics that will arise in practice. Here, we tend to denote all the
associated quantities with a hat. Since we use gradient descent to optimize,
we denote the parameters trained from finite-sample data as
$\widehat{\theta}(t)$ and will denote the associated neural network’s output
as $\widehat{u}(x,t)=f(x,\widehat{\theta}(t))$. Now, let us inspect the
equation used to optimize the parameters.

$\displaystyle\widehat{L}(\theta)$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)-1\big{)}^{2}\widehat{p}(x)dx+\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)+1\big{)}^{2}\widehat{q}(x)dx\bigg{)}$
$\displaystyle-\dot{\widehat{\theta}}(t)$
$\displaystyle=\partial_{\theta}\widehat{L}(\widehat{\theta}(t))$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\nabla_{\theta}f(x,\widehat{\theta}(t))\Big{(}\big{(}f(x,\widehat{\theta}(t))-1\big{)}\widehat{p}(x)+\big{(}f(x,\widehat{\theta}(t))+1\big{)}\widehat{q}(x)\Big{)}dx\bigg{)}$
$\displaystyle\partial_{t}\widehat{u}(x,t)$
$\displaystyle=\langle\nabla_{\theta}f(x,\widehat{\theta}(t)),\dot{\widehat{\theta}}\rangle_{\Theta}=-\langle\nabla_{\theta}f(x,\widehat{\theta}(t)),\partial_{\theta}\widehat{L}(\widehat{\theta}(t))\rangle_{\Theta}$
$\displaystyle=-\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\langle\nabla_{\theta}f(x,\widehat{\theta}(t)),\nabla_{\theta}f(x^{\prime},\widehat{\theta}(t))\rangle_{\Theta}\Big{(}\big{(}f(x^{\prime},\widehat{\theta}(t))-1\big{)}\widehat{p}(x^{\prime})$
$\displaystyle+\big{(}f(x^{\prime},\widehat{\theta}(t))+1\big{)}\widehat{q}(x^{\prime})\Big{)}dx^{\prime}\bigg{)}.$

We define the time-varying finite-sample neural tangent kernel by

$\displaystyle\widehat{K}_{t}(x,x^{\prime})=\langle\nabla_{\theta}f(x,\widehat{\theta}(t)),\nabla_{\theta}f(x^{\prime},\widehat{\theta}(t))\rangle_{\Theta}.$

We can further define density-specific residuals

$\displaystyle\widehat{e}_{p}(x,t)=\big{(}f(x,\widehat{\theta}(t))-1\big{)}$
$\displaystyle\widehat{e}_{q}(x,t)=\big{(}f(x,\widehat{\theta}(t))+1\big{)}.$

This means that

$\displaystyle\partial_{t}\widehat{u}(x,t)$
$\displaystyle=-\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\widehat{K}_{t}(x,x^{\prime})\Big{(}\big{(}f(x^{\prime},\widehat{\theta}(t))-1\big{)}\widehat{p}(x^{\prime})+\big{(}f(x^{\prime},\widehat{\theta}(t))+1\big{)}\widehat{q}(x^{\prime})\Big{)}dx^{\prime}\bigg{)}$
$\displaystyle=-\frac{1}{2}\Big{(}\mathbb{E}_{x^{\prime}\sim\widehat{p}}\widehat{K}_{t}(x,x^{\prime})\widehat{e}_{p}(x^{\prime},t)+\mathbb{E}_{x^{\prime}\sim\widehat{q}}\widehat{K}_{t}(x,x^{\prime})\widehat{e}_{q}(x^{\prime},t)\Big{)}.$

In the context of the two sample test, since this training regime uses only
finite training samples, we will study the two-sample test statistic’s
behavior evaluated on the training samples, the test samples (independent from
the training samples), and the population. We denote these different evaluated
test statistics by

$\displaystyle\widehat{T}_{train}(t):$
$\displaystyle=T(\widehat{\theta}(t);\widehat{p},\widehat{q})=\Big{(}\mathbb{E}_{x\sim\widehat{p}}-\mathbb{E}_{x\sim\widehat{q}}\Big{)}f(x,\widehat{\theta}(t))=\Big{(}\mathbb{E}_{x\sim\widehat{p}}-\mathbb{E}_{x\sim\widehat{q}}\Big{)}\widehat{u}(x,t),$
$\displaystyle\widehat{T}_{test}(t):$
$\displaystyle=T(\widehat{\theta}(t);\widehat{p}_{test},\widehat{q}_{test})=\Big{(}\mathbb{E}_{x\sim\widehat{p}_{test}}-\mathbb{E}_{x\sim\widehat{q}_{test}}\Big{)}f(x,\widehat{\theta}(t))$
$\displaystyle=\Big{(}\mathbb{E}_{x\sim\widehat{p}_{test}}-\mathbb{E}_{x\sim\widehat{q}_{test}}\Big{)}\widehat{u}(x,t),$
$\displaystyle\widehat{T}_{pop}(t):$
$\displaystyle=T(\widehat{\theta}(t);p,q)=\Big{(}\mathbb{E}_{x\sim
p}-\mathbb{E}_{x\sim
q}\Big{)}f(x,\widehat{\theta}(t))=\Big{(}\mathbb{E}_{x\sim
p}-\mathbb{E}_{x\sim q}\Big{)}\widehat{u}(x,t),$

where $\widehat{T},\widehat{T}_{test},\widehat{T}_{pop}$ denote the evaluation
on the training samples, test samples, and population, respectively.

###  4.2 Population Dynamics

These population dynamics are essentially what would happen as the number of
samples in our datasets grows larger and larger, since here we train on the
population yet still have time-varying dynamics. In this case, we denote the
path of the parameters as simply $\theta(t)$ and will denote the associated
neural network’s output as $u(x,t)=f(x,\theta(t))$. We showed earlier that the
population-level loss is equivalent to simply minimizing
$\mathcal{L}(\theta)=\frac{1}{2}\|f(\cdot,\theta)-f^{*}(\cdot)\|_{L^{2}(p+q)}$.
This means that training the population-level neural network is equivalent to
running gradient descent on $\mathcal{L}$. Moreover, we can define the
population level error function as $e(x,t)=f(x,\theta(t))-f^{*}(x)$. Using
these facts, we get the following

$\displaystyle-\dot{\theta}(t)$
$\displaystyle=\partial_{\theta}\mathcal{L}(\theta(t))=\frac{1}{2}\int_{\mathbb{R}^{d}}\nabla_{\theta}f(x,\theta(t))\big{(}f(x,\theta(t))-f^{*}(x)\big{)}(p+q)(x)dx$
$\displaystyle\partial_{t}u(x,t)$
$\displaystyle=\langle\nabla_{\theta}f(x,\theta(t)),\dot{\theta}(t)\rangle_{\Theta}=-\langle\nabla_{\theta}f(x,\theta(t)),\partial_{\theta}\mathcal{L}(\theta(t))\rangle_{\Theta}$
$\displaystyle=-\frac{1}{2}\int_{\mathbb{R}^{d}}\langle\nabla_{\theta}f(x,\theta(t)),\nabla_{\theta}f(x^{\prime},\theta(t))\rangle_{\Theta}\big{(}f(x^{\prime},\theta(t))-f^{*}(x^{\prime})\big{)}(p+q)(x^{\prime})dx^{\prime}.$

Now we define the population level time-varying neural tangent kernel

$\displaystyle
K_{t}(x,x^{\prime})=\langle\nabla_{\theta}f(x,\theta(t)),\nabla_{\theta}f(x^{\prime},\theta(t))\rangle_{\Theta}.$

This finally implies that

$\displaystyle\partial_{t}u(x,t)=-\frac{1}{2}\mathbb{E}_{x^{\prime}\sim
p+q}K_{t}(x,x^{\prime})e(x^{\prime},t)=\partial_{t}e(x,t).$

Contrary to the realistic dynamics, we only care about the population-level
two-sample test statistic with these population dynamics since these dynamics
trains on the population itself. We denote the two-sample test statistic
associated to these population-level time-varying dynamics by

$\displaystyle T(t):=T(\theta(t);p,q)=\int_{\mathbb{R}^{d}}u(x,t)d(p-q)(x),$

where we are integrating the neural network output over the entire densities.

###  4.3 Zero-time Auxiliary Dynamics

The zero-time auxiliary dynamics are characterized by training on the
population but having the dynamics driven by the zero-time NTK. With these
zero-time auxiliary dynamics, we will denote related quantities with a bar so
that the output of the trained function here becomes $\bar{u}(x,t)$ with
$\bar{u}(x,0)=f(x,\theta_{0})$. At this point, consider the zero-time NTK of
the neural network $f(\cdot,\theta_{0})$ by

$\displaystyle
K_{0}(x,x^{\prime})=\langle\nabla_{\theta}f(x,\theta_{0}),\nabla_{\theta}f(x^{\prime},\theta_{0})\rangle_{\Theta}.$

According to [25, Lemma 4.3], assuming that
$\|\nabla_{\theta}f(x,\theta_{0})\|_{\Theta}$ is squared integrable on
$\mathbb{R}^{d}$ against measure $(p(x)+q(x))dx$, the zero-time kernel can act
as a kernel integral operator and admits a spectral decomposition, which we
can write as

$\displaystyle(L_{K_{0}}g)(x)$
$\displaystyle=\int_{\mathbb{R}^{d}}K_{0}(x,x^{\prime})g(x^{\prime})(p+q)(x^{\prime})dx^{\prime}=\sum_{\ell=1}^{M}\lambda_{\ell}\langle
g,u_{\ell}\rangle_{L^{2}(p+q)}u_{\ell}(x),$

where $\lambda_{1}\geq\lambda_{2}\geq\dotsc\geq\lambda_{M}$. Although we can
find an extended basis for $\ell>M$ for $L^{2}(p+q)$, the associated
eigenvalues of $K_{0}$ are 0 on eigenfunctions $u_{\ell}$ for $\ell>M$. Since
$K_{0}$ does not effectively have full basis for $L^{2}(p+q)$, the quantities
that we work with will need to be projected onto the range of the operator
$L_{K_{0}}$. This motivates the following definition.

######  Definition 4.2.

Denote the projection operator onto the range of $L_{K_{0}}$ by $\Pi_{K_{0}}$.

Now we can define the associated error function

$\displaystyle\bar{e}(x,t)=\bar{u}(x,t)-\Pi_{K_{0}}(f^{*})(x).$

Since $f^{*}$ is fixed, the dynamics of our model that we care about will be
given by

$\displaystyle\partial_{t}\bar{u}(x,t)=-\frac{1}{2}\mathbb{E}_{x^{\prime}\sim
p+q}K_{0}(x,x^{\prime})\bar{e}(x^{\prime},t)=\partial_{t}\bar{e}(x,t).$

With the simplicity in the model dynamics, we can attain better analysis.
Using this interpretation, we know that

$\displaystyle\partial_{t}\bar{e}(\cdot,t)=-\frac{1}{2}(L_{K_{0}}\bar{e}(\cdot,t))=-\sum_{\ell=1}^{M}\lambda_{\ell}\langle\bar{e}(\cdot,t),u_{\ell}\rangle_{L^{2}(p+q)}u_{\ell}.$

We formulate an ansatz of what $\bar{e}(\cdot,t)$ would be so that it
satisfies this differential equation. In particular, consider

$\displaystyle\bar{e}(\cdot,t)=\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}u_{\ell}.$

The following proposition ensures that this indeed is a solution of the
differential equation of interest.

######  Proposition 4.3 (Zero-Time Auxiliary Dynamics Solution).

The solution

$\displaystyle\bar{e}(\cdot,t)=\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle u_{\ell}$

solves the differential equation

$\displaystyle\partial_{t}\bar{e}(\cdot,t)=-\frac{1}{2}(L_{K_{0}}\bar{e}(\cdot,t))=-\sum_{\ell=1}^{M}\lambda_{\ell}\langle\bar{e}(\cdot,t),u_{\ell}\rangle_{L^{2}(p+q)}u_{\ell}.$

The proof of Proposition 4.3 is given in Appendix A.

For these zero-time auxiliary dynamics, we can now talk about the two-sample
test statistic. In particular, recalling that
$\bar{u}=\bar{e}+\Pi_{K_{0}}(f^{*})$, we will set

$\displaystyle\overline{\mu_{p}}(t)$
$\displaystyle=\int_{\mathbb{R}^{d}}\bar{u}(x,t)dp(x)=\int_{\mathbb{R}^{d}}(\bar{e}(x,t)+\Pi_{K_{0}}(f^{*})(x))p(x)dx,$
$\displaystyle\overline{\mu_{p}}(t)$
$\displaystyle=\int_{X}\bar{u}(x,t)dq(x)=\int_{X}(\bar{e}(x,t)+\Pi_{K_{0}}(f^{*})(x))q(x)dx.$

Similar to the population (population-training data time-varying) dynamics, we
only care about the population-level two-sample test statistic for this
training regime since we use the entire population for training. For this
training regime, we will denote the associated two-sample test by

$\displaystyle\overline{T}(t):=\overline{\mu_{p}}(t)-\overline{\mu_{q}}(t)=\int_{\mathbb{R}^{d}}\bar{u}(x,t)d(p-q)(x).$

Note that in this case, $\overline{T}(t)$ is not determined by the parameters
of the neural network changing but rather by the output of the NTK trained
dynamics. With this in mind, we get the following lemma.

######  Lemma 4.4 (Zero-Time Auxiliary Statistic).

The population-level zero-time kernel dynamics two-sample test statistic is
given by

$\displaystyle\overline{T}(t)$
$\displaystyle=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\sum_{\ell\geq
1}e^{-t\lambda_{\ell}}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}^{2}.$

The proof of Lemma 4.4 is in Appendix A.

Note that there is some time-analysis we can undertake at this point. First,
you can notice that at $t=0$,

$\displaystyle\overline{T}(0)=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\underbrace{\sum_{\ell\geq
1}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}^{2}}_{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}}=0,$

and for any time $t>0$, we have $\overline{T}(t)>0$. We will find a
theoretical minimum time $t(\epsilon)$ such that
$\overline{T}(t(\epsilon))\geq\epsilon$. Let us define a few quantities before
delving into the main result.

######  Definition 4.5.

Let $S\subseteq\\{1,\dotsc,M\\}$, then we can consider how much of the norm
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}$ (and hence the norm of $f^{*}$) lies
on the eigenbasis subset $V_{S}=\\{u_{\ell}\\}_{\ell\in S}$. In particular, we
have

$\displaystyle\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}=\|f^{*}\|_{S}^{2}=\sum_{\ell\in
S}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}=x_{S}\|f^{*}\|_{L^{2}(p+q)}^{2}.$

Since $\langle u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}=\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}$ for $\ell\leq M$, we can also define these
quantities for $f^{*}$ rather than just $\Pi_{K_{0}}(f^{*})$. Moreover, we can
define the minimum and maximum eigenvalue that exist for the eigenvectors that
lie in $V_{S}$ by defining

$\displaystyle\lambda_{\min}(S)=\min_{\ell\in S}\lambda_{\ell},\hskip
14.22636pt\lambda_{\max}(S)=\max_{\ell\in S}\lambda_{\ell}.$

Then we have the following theorem.

######  Proposition 4.6 (Minimum Detection Time – Zero-Time Auxiliary).

Let $\epsilon>0$ and assume that there exists a finite subset
$S\subset\\{1,\dotsc,M\\}$ such that

$\displaystyle\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}=\|f^{*}\|_{S}^{2}=\sum_{\ell\in
S}\langle u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}>\epsilon$

and $\lambda_{\min}(S)>0$. Then

$\displaystyle
t(\epsilon)\geq\lambda_{\min}(S)\log\bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}-\epsilon}\bigg{)}=\lambda_{\min}(S)\log\bigg{(}\frac{\|f^{*}\|_{S}^{2}}{\|f^{*}\|_{S}^{2}-\epsilon}\bigg{)}$

ensures that $\overline{T}(t(\epsilon))\geq\epsilon$.

The proof of Proposition 4.6 is in Appendix A.

######  Remark 4.7.

Let us analyze the function

$\displaystyle g(\epsilon,S)$
$\displaystyle=\min_{S\in\mathcal{S}_{1}(\epsilon)}\lambda_{\min}(S)\log\bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}-\epsilon}\bigg{)}.$

Notice first that the largest that $\epsilon$ can be is
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}$ because as $t\to\infty$, we get that
$\overline{T}(t)\to\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}$ and it is easy to
see that $\overline{T}(t)$ is monotonic in $t$. Now notice that as $\epsilon$
gets larger, we need $S$ to satisfy
$\|f^{*}\|_{S}^{2}=\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}>\epsilon$ to make sure that
$g(\epsilon,S)$ is well-defined. Moreover, we need $\lambda_{\min}(S)>0$
otherwise we find that $g(\epsilon,S)=0$ which is the trivial bound. In
particular, we will want the fraction
$\epsilon/\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}$ to be as small as possible to give
the smallest possible non-trivial time.

We have an analogous statement for when we want our test statistic to be less
than $\epsilon$. In particular, we get that

######  Proposition 4.8 (Maximum Undetectable Time – Zero-Time Auxiliary).

Let $\epsilon>0$ and assume that there exists a finite subset
$S\subset\mathbb{N}$ such that

$\displaystyle\frac{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}>0$

and $\lambda_{\max}(S)>0$. Then

$\displaystyle
t(\epsilon)\leq\lambda_{\max}(S)\log\Bigg{\\{}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon}\Bigg{\\}}$

ensures that $\overline{T}(t(\epsilon))\leq\epsilon$.

The proof of Proposition 4.8 is in Appendix A. Now if we optimize over all
such subsets $S$, we get the following corollary.

######  Corollary 4.9 (Detection Times – Zero-Time Auxiliary).

Let $0<\epsilon<\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}$. Assume that the set

$\displaystyle\mathcal{S}_{1}(\epsilon)$
$\displaystyle=\\{S\subset\mathbb{N}:\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}>\epsilon,\lambda_{\min}(S)>0\\}\neq\emptyset$
$\displaystyle\mathcal{S}_{2}(\epsilon)$
$\displaystyle=\\{S\subset\mathbb{N}:(\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon)/\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}>0,\lambda_{\max}(S)>0\\}\neq\emptyset.$

Then

$\displaystyle t\geq
t_{1}^{*}(\epsilon):=\min_{S\in\mathcal{S}_{1}(\epsilon)}\lambda_{\min}(S)\log\Bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}-\epsilon}\Bigg{)}$

ensures that $\overline{T}(t)\geq\epsilon$ whilst

$\displaystyle t\leq
t_{2}^{*}(\epsilon):=\max_{S\in\mathcal{S}_{2}(\epsilon)}\lambda_{\max}(S)\log\Bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon}\Bigg{)}$

ensures that $\overline{T}(t)\leq\epsilon$.

Here let us remark what occurs in the case when our null hypothesis is correct
versus when the alternative is correct.

######  Remark 4.10.

If $H_{0}$ is true (so that $p=q$), then $f^{*}=0$. We can’t apply the theorem
above then since the assumption is not satisfied; however, we note by
inspection that $\overline{T}(t)=0$ for all $t$. If
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}<\delta$ for small $\delta>0$, then note
that both Proposition 4.6 and Proposition 4.8 limit $\epsilon<\delta$. This
means that $\overline{T}(t)$ can only detect small changes. On the other hand,
if we are under $H_{1}$ (so that $p\neq q$) and we assume that
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}>\delta$ for some larger $\delta>0$, then
$\epsilon$ can be made much larger and should be more easy to detect.

##  5 Realistic and Population Dynamics Approximation

The results in this section are crucial and foundational for building the
results in Section 6. In essence, we are trying to show that $\widehat{u}$ and
$u$ are close to $\bar{u}$, which can easily imply that the associated two-
sample statistics $\widehat{T}$ and $T$ are close to $\overline{T}$. After
showing that the statistics are close the zero-time NTK statistic, we will
show $\widehat{T}$ and $T$ are monotonically increasing in time in order to
prove Theorem 6.6 and Theorem 6.2.

The general process of showing $\widehat{u}$ and $u$ are close to $\bar{u}$
requires

  1. 1.

Showing that $\widehat{\theta}(t)$ and $\theta(t)$ are close to
$\theta(0)=\theta_{0}$ in time. Along with 5.2, this is used to ensure that
$K_{t}$ is close to $K_{0}$. Note that this is all that is needed to show $u$
is close to $\bar{u}$.

  2. 2.

Show that a neural network version of matrix Bernstein’s inequality holds for
the sampled kernel $\widehat{K}_{t}$. Along with showing the parameters are
close, 5.2 and 5.3 are used here to show that $\widehat{K}_{t}$ is close to
$K_{0}$.

Formally, there are a few assumptions that we will need to ensure the analysis
works. To start, let $B_{R}$ denote the open ball of radius $R$ with center
$\theta_{0}$ and assume that $u(x,0)=\bar{u}(x,0)=f(x,\theta_{0})=0$ for all
$x$. For much of the analysis of realistic and population dynamics going
forward, we will use the following lemma heavily.

######  Lemma 5.1.

$\mathcal{L}(\theta(0))=\|u(\cdot,0)-f^{*}\|_{L^{2}(p+q)}^{2}=\|\bar{u}(\cdot,0)-f^{*}\|_{L^{2}(p+q)}^{2}=\|f^{*}\|_{L^{2}(p+q)}^{2}$.

###### Proof.

Notice that since $u(\cdot,0)=\bar{u}(\cdot,0)=f(x,\theta_{0})=0$, we have the
result. ∎

For both the realistic and population dynamics, we will need to assume bounded
and Lipschitz gradient as shown in the following assumption.

######  Assumption 5.2 (Gradient Condition).

There exists positive constants $R,L_{1}$, and $L_{2}$ such that

  1. 1.

(Boundedness) For any $\theta\in B_{R}$,
$\sup_{x\in\text{supp}(p+q)}\|\nabla_{\theta}f(x,\theta)\|\leq L_{1}$.

  2. 2.

(Lipschitz) For any $\theta_{1},\theta_{2}\in B_{R}$,
$\sup_{x\in\text{supp}(p+q)}\|\nabla_{\theta}f(x,\theta_{1})-\nabla_{\theta}f(x,\theta_{2})\|\leq
L_{2}\|\theta_{1}-\theta_{2}\|$.

For only the realistic dynamics case, we will need to assume a large enough
training sample size as is specified in the following assumption in order to
get a matrix Bernstein type statement for our neural network.

######  Assumption 5.3 (Sample Size Condition).

For $A>0$ (representing a desired probability level), consider the function

$\displaystyle
h(n)=\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n)+\log(2M_{\Theta})}{n}}.$

Assume that the training sample sizes $n_{p}$ and $n_{q}$ are large enough
that $h(n_{p})<\frac{3}{2}$ and $h(n_{q})<\frac{3}{2}$.

###  5.1 Population Dynamics Approximation

As the population dynamics have no sample size associated to them, we do not
need to worry about $n_{p}$ or $n_{q}$. In this case, we use that the loss

$\displaystyle\mathcal{L}(\theta)=\frac{1}{2}\|f(\cdot,\theta)-f^{*}(\cdot)\|_{L^{2}(p+q)}$

is decreasing to get the following lemma.

######  Lemma 5.4 (Population-Dynamics Parameter Bound).

Assume that $u(x,0)=\bar{u}(x,0)=0$, then

$\displaystyle\|\theta(t)-\theta(0)\|$
$\displaystyle\leq\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}.$

Moreover, if

$\displaystyle t\leq\bigg{(}\frac{R}{\|f^{*}\|_{L^{2}(p+q)}}\bigg{)}^{2},$

then $\theta(t)\in B_{R}$.

The proof of Lemma 5.4 is contained in Appendix B. Now with 5.2, we can
further bound the operator norm of the difference $K_{t}-K_{0}$ with the
following lemma.

######  Lemma 5.5 (Population-Dynamics NTK Bound).

Let $\theta(t)\in B_{R}$, then under 5.2, we have

$\displaystyle\|K_{t}-K_{0}\|_{L^{2}(p+q)}\leq
2L_{1}L_{2}\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}.$

The proof of Lemma 5.5 is contained in Appendix B. Now we use this result for
bounding the difference $\|u-\bar{u}\|_{L^{2}(p+q)}$. In particular, we have
the following proposition.

######  Proposition 5.6 (Population-Dynamics Output Approximation).

Under 5.2 and

$\displaystyle t$
$\displaystyle\leq\bigg{(}\frac{R}{\|f^{*}\|_{L^{2}(p+q)}}\bigg{)}^{2},$

we get

$\displaystyle\|(u-\bar{u})(\cdot,t)\|_{L^{2}(p+q)}=\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}\leq\frac{8}{3}L_{1}L_{2}\|f^{*}\|_{L^{2}(p+q)}^{2}(t)^{3/2}.$

The proof of Proposition 5.6 is contained in Appendix B. Now let us extend our
zero-time NTK two-sample test results to the population-level time-varying
kernel two-sample test. We first notice the following corollary.

######  Corollary 5.7 (Population Statistic Bound).

Under 5.2 and

$\displaystyle t\leq\bigg{(}\frac{R}{\|f^{*}\|_{L^{2}(p+q)}}\bigg{)}^{2},$

we have

$\displaystyle\Big{|}T(t)-\overline{T}(t)\Big{|}\leq\sqrt{2}\frac{8}{3}L_{1}L_{2}\|f^{*}\|_{L^{2}(p+q)}^{2}(t)^{3/2}.$

The proof of Corollary 5.7 is contained in Appendix B. For further time
analysis in the alternative hypothesis case below, we will need to show that
this two-sample test $T(t)$ is monotonically increasing. We will be able to
show this if our population-level neural network has increasing norm. This
assumption is not unsupported since we initialize as $u(x,0)=f(x,\theta(0))=0$
and our target function $f^{*}(x)=\frac{p-q}{p+q}(x)$ has non-zero norm. Using
this assumption, we get the following theorem (with proof contained in
Appendix B).

######  Lemma 5.8 (Population Statistic Monotonicity).

Assume that $\|u(x,t)\|_{L^{2}(p+q)}$ is monotonically increasing on the
interval $[0,\tau]$, then $T(t)$ is monotonically increasing on $[0,\tau]$.

Note that we only need 6.1 for this theorem to work.

###  5.2 Realistic Approximation

Since the realistic approximation represents a neural network trained on
finite samples and time-varying dynamics, we will be using finite-samples,
which require some concentration inequalities and need a few extra assumptions
than the population-dynamics case. To start off, recall that for our finite-
sample we have $n_{p}$ training samples from density $p$ and $n_{q}$ samples
from density $q$. Moreover, recall that our finite-sample loss function is
given by

$\displaystyle\widehat{L}(\theta)$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)-1\big{)}^{2}\widehat{p}(x)dx+\int_{\mathbb{R}^{d}}\big{(}f(x,\theta)+1\big{)}^{2}\widehat{q}(x)dx\bigg{)}$

Using that this loss decreases in time, we get the following lemma.

######  Lemma 5.9 (Realistic Parameter Bound).

Assume that $\widehat{\theta}(0)=\theta(0)$ and that $f(x,\theta(0))=0$, then

$\displaystyle\|\widehat{\theta}(t)-\theta(0)\|_{\Theta}\leq\sqrt{t}.$

Moreover, if $\theta(0)\in B_{R}$, then $t\leq R^{2}$ ensures that
$\widehat{\theta}(t)\in B_{R}$.

We prove Lemma 5.9 in Appendix C. Using 5.3, we can apply Lemma D.4 to get the
following lemma to be used later.

######  Lemma 5.10 (Neural Net Matrix Bernstein).

Assume that $\theta\in B_{R}$, then under 5.2 and 5.3 and let $p$ be a
probability density, consider the random $M_{\Theta}$-by-$M_{\Theta}$ matrix

$\displaystyle
X_{i}=\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top}-\mathbb{E}_{x\sim
p}\nabla_{\theta}f(x,\theta)\nabla_{\theta}f(x,\theta)^{\top}.$

If $n$ is the number of samples from $p$, then with probability greater than
$1-n^{-A}$, we have

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}X_{i}\|\leq\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n)+\log(2M_{\Theta})}{n}}.$

The proof of Lemma 5.10 is in Appendix C and is used in the following
proposition.

######  Proposition 5.11 (Realistic Output Approximation).

Assume that $t\leq R^{2}$ (so that $\theta(t)\in B_{R}$) as well as 5.2 and
5.3, then with probability $\geq 1-n_{p}^{-A}-n_{q}^{-A}$, we have

$\displaystyle\|(\widehat{u}-\bar{u})(\cdot,t)\|_{L^{2}(p+q)}$
$\displaystyle\leq C_{1}t+C_{2}t^{3/2}+C_{3}t^{2}+C_{4}t^{5/2},$

where the dependence of the constants is given by $C_{1}=C(L_{1})$,
$C_{2}=C(L_{1},L_{2},f^{*})$, $C_{3}=C(L_{1},f^{*},n_{p},n_{q},M_{\Theta},A)$,
and $C_{4}=C(L_{1},L_{2},f^{*},n_{p},n_{q},M_{\Theta},A)$.

Note that the more technical version of Proposition 5.11 is contained in
Proposition C.1 along with its proof. We will use Proposition 5.11 to show
that the finite-sample two-sample test statistic and zero-time kernel
population-level two-sample test statistic are close for $\widehat{T}_{pop}$,
$\widehat{T}_{train}$, and $\widehat{T}_{test}$ (i.e. the evaluation of the
finite-sample two-sample test statistic on the population, training samples,
and test samples, respectively). For $\widehat{T}_{pop}$, we get the following
proposition.

######  Proposition 5.12 (Realistic Population-Evaluated Statistic).

Assume the conditions of Proposition 5.11, then with probability $\geq
1-(n_{p}^{-A}+n_{q}^{-A})$, we get the time-approximation error function

$\displaystyle\big{|}\widehat{T}_{pop}(t)-\overline{T}(t)\big{|}$
$\displaystyle\leq
C_{1}t+C_{2}t^{3/2}+C_{3}t^{2}+C_{4}t^{5/2}:=\delta_{pop}(t),$

where $C_{1},C_{2},C_{3},C_{4}$ are exactly the constants from Proposition
5.11. Moreover, note that this error function is monotonic.

###### Proof of Proposition 5.12.

Mimic the proof of Corollary 5.7 mutatis mutandis applying Proposition 5.11. ∎

Now for $\widehat{T}_{test}(t)$, the test size sample sizes come into play
since

$\displaystyle\widehat{T}_{test}(t)=T(\widehat{\theta}(t);\widehat{p}_{test},\widehat{q}_{test})=\big{(}\mathbb{E}_{x\sim\widehat{p}_{test}}-\mathbb{E}_{x-\widehat{q}_{test}}\big{)}\widehat{u}(x,t),$

with test sample sizes $m_{p}$ and $m_{q}$ for $\widehat{p}_{test}$ and
$\widehat{q}_{test}$, respectively. We also describe the time-approximation
error function in the next proposition, which will be used for the theorems
and corollaries afterwards.

######  Proposition 5.13 (Realistic Test Sample-Evaluated Statistic).

Assume the conditions of Proposition 5.11, then with probability $\geq
1-(m_{p}^{-A}+m_{q}^{-A})$, we have

$\displaystyle|\widehat{T}_{test}(t)-\widehat{T}_{pop}(t)|\leq
L_{1}^{2}t\sqrt{2}\bigg{(}\sqrt{\frac{A\log(m_{p})}{m_{p}}}+\sqrt{\frac{A\log(m_{q})}{m_{q}}}\bigg{)}.$

Moreover, with probability $\geq
1-(m_{p}^{-A}+m_{q}^{-A}+n_{p}^{-A}+n_{q}^{-A})$, we get the time-
approximation error function

$\displaystyle\big{|}\widehat{T}_{test}(t)-\overline{T}(t)\big{|}$
$\displaystyle\leq\tilde{C}_{1}t+C_{2}t^{3/2}+C_{3}t^{2}+C_{4}t^{5/2}:=\delta(t),$

where $\tilde{C}_{1}=C(L_{1},A,m_{p},m_{q})$ and $C_{2},C_{3},C_{4}$ are
exactly the constants from Proposition 5.11. Finally, note that this error
function $\delta(t)$ is monotonic.

The proof of this proposition is located in Appendix C.

######  Remark 5.14.

We note that Proposition 5.13 works for $\widehat{T}_{train}$ if we replace
$m_{p}$ and $m_{q}$ with $n_{p}$ and $n_{q}$ respectively. Since the error
function $\delta$ depends on whether we use test samples or training samples,
we will regard the error function by $\delta_{test}(t)$ and
$\delta_{train}(t)$ to distinguish these cases. In particular, the only
constant that is different in $\delta_{train}$ and $\delta_{test}$ is
$\tilde{C}_{1}$, where we change $m_{p}$ and $m_{q}$ to $n_{p}$ and $n_{q}$,
respectively. Moreover, using the triangle inequality, we can see that

$\displaystyle|\widehat{T}_{test}(t)-\widehat{T}_{train}(t)|\leq
L_{1}^{2}t\sqrt{2}\bigg{(}\sqrt{\frac{A\log(m_{p})}{m_{p}}}+\sqrt{\frac{A\log(n_{p})}{n_{p}}}$
$\displaystyle+\sqrt{\frac{A\log(m_{q})}{m_{q}}}+\sqrt{\frac{A\log(n_{q})}{n_{q}}}\bigg{)}.$

Finally, we may also deduce from Proposition 5.13 that

$\displaystyle|\widehat{T}_{train}(t)-\widehat{T}_{pop}(t)|\leq
L_{1}^{2}t\sqrt{2}\bigg{(}\sqrt{\frac{A\log(n_{p})}{n_{p}}}+\sqrt{\frac{A\log(n_{q})}{n_{q}}}\bigg{)}.$

To do further time-analysis in this finite-sample training case, we will need
that $\widehat{T}_{train}(t)$ is monotonic in time. We will then use sampling
concentration of $\widehat{T}_{train}$ with $\widehat{T}_{pop}$ and
$\widehat{T}_{test}$ to extend the two-sample test statistic to these two
different evaluation settings.

######  Lemma 5.15 (Realistic Statistic Monotonicity).

Assume that there is an interval $[0,\widehat{\tau}]$ such that
$|\widehat{u}(x,s)|\leq 1$ for $s\in[0,\widehat{\tau}]$ and
$x\in\text{supp}(\widehat{p}+\widehat{q})$. Then $\widehat{T}_{train}(t)$ is
monotonically increasing on $[0,\widehat{\tau}]$.

Note that the assumption of Lemma 5.15 is exactly 6.4. We include the proof of
Lemma 5.15 in Appendix C.

######  Remark 5.16.

Note that the assumption $|\widehat{u}(x,s)|\leq 1$ definitely holds for at
least small time intervals since the training dynamics are smooth and
$\widehat{u}(x,0)=0$. Moreover, we crucially use the fact that the training
loss is decreasing for the proof of Lemma 5.15.

##  6 Test Statistic Time and Power Analysis

We want to extend the zero-time auxiliary time analysis of Proposition 4.6 and
Proposition 4.8 to the realistic and population dynamics cases. The general
method of extending the time analysis of the zero-time auxiliary analysis
requires us to

  1. 1.

Done in Section 5: Approximate the realistic and population dynamics outputs
($\widehat{u}$ and $u$, respectively) with the zero-time auxiliary output
$\bar{u}$,

  2. 2.

Done in Section 5: Extend the approximation to the realistic two-sample
statistic and population-dynamics two-sample statistic as well as show
monotonicity of the statistics,

  3. 3.

Done in this section: Combine the two-sample approximations with the time
analysis of Proposition 4.6 and Proposition 4.8.

Here, it is useful to recall that both the realistic and population dynamics
need 5.2 whilst only the realistic dynamics need the additional 5.3.

###  6.1 Population Time Analysis

Since the population dynamics do not have any samples, we cannot really
perform any test power analysis in this scenario. We can, however, use
approximation theorems from Section 5.1 to extend the zero-time NTK time
analysis theorems.

We need to counteract the time-dependent estimation error shown in Corollary
5.7. The next theorem, which is geared towards discovering the alternative
hypothesis, necessarily assumes first that the minimum time needed to detect
an error $\epsilon$ in Corollary 4.9 is smaller than $\epsilon$ and second
that the time scale we work on is valid for detection. Note that as the size
of the neural network grows, the minimum time needed for detection decreases
but $L_{1}$ and $L_{2}$ below increase; thus, there is an interplay of making
sure your neural network is large but not too large. We will need the
following monotonicity assumption for the alternative hypothesis time
analysis.

######  Assumption 6.1 (Population Monotonicity Condition).

Assume that $\|u(x,t)\|_{L^{2}(p+q)}^{2}$ is monotonically increasing on
$[0,\tau]$.

For this next theorem, recall from Corollary 4.9 that

$\displaystyle t_{1}^{*}(\epsilon)$
$\displaystyle:=\min_{S\in\mathcal{S}_{1}(\epsilon)}\lambda_{\min}(S)\log\Bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}-\epsilon}\Bigg{)},$
$\displaystyle t_{2}^{*}(\epsilon)$
$\displaystyle:=\max_{S\in\mathcal{S}_{2}(\epsilon)}\lambda_{\max}(S)\log\Bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon}\Bigg{)}.$

######  Theorem 6.2 (Minimum Detection Time – Population).

Assume 5.2 and 6.1 hold and let $\epsilon>0$. Then for

$\displaystyle\min\bigg{(}\tau,\Big{(}\frac{R}{\|f^{*}\|_{L^{2}(p+q)}}\Big{)}^{2}\bigg{)}\geq
t\geq t_{1}^{*}(\epsilon),$

where $t_{1}^{*}(\epsilon)$ is defined in Corollary 4.9, we get

$\displaystyle|T(t)|\geq\epsilon-\frac{8\sqrt{2}}{3}\|f^{*}\|_{L^{2}(p+q)}^{2}L_{1}L_{2}\big{(}t_{1}^{*}(\epsilon)\big{)}^{3/2}.$

If $\epsilon$ is not large enough to make the right-hand sides of the
inequalities positive or $t_{1}^{*}(\epsilon)$ is not smaller than $\tau$ or
$(R/\|f^{*}\|_{L^{2}(p+q)})^{2}$, the bound is vacuous.

We prove Theorem 6.2 in Appendix B. Now, the following theorem is useful in
showing the null hypothesis and necessarily needs the time to be smaller the
maximum time needed to detect $\epsilon$ as well as the time needed to stay in
$B_{R}$ (so that Proposition 5.6 holds).

######  Theorem 6.3 (Maximum Undetectable Time – Population).

Let $\epsilon>0$. Under 5.2 and for

$\displaystyle
t\leq\min\Bigg{\\{}\Big{(}\frac{R}{\|f^{*}\|_{L^{2}(p+q)}}\Big{)}^{2},t_{2}^{*}(\epsilon)\Bigg{\\}},$

where $t_{2}^{*}(\epsilon)$ is defined in Corollary 4.9, we have

$\displaystyle|T(t)|\leq\epsilon+\frac{8\sqrt{2}}{3}\|f^{*}\|_{L^{2}(p+q)}^{2}L_{1}L_{2}\big{(}t_{2}^{*}(\epsilon)\big{)}^{3/2}.$

The proof of Theorem 6.3 is given in Appendix B.

###  6.2 Realistic Time Analysis

Following the approximation theorems of Section 5.2, we can first get the
realistic dynamics extension of the zero-time NTK time-analysis theorems and
second conduct test power analysis. Specifically for the minimum detection
analysis, we need the following assumption, which will ensure monotonicity of
the two-sample statistic in the realistic dynamics case.

######  Assumption 6.4 (Realistic Monotonicity Condition).

Assume that there is an interval $[0,\widehat{\tau}]$ such that
$|\widehat{u}(x,s)|\leq 1$ for $s\in[0,\widehat{\tau}]$ and
$x\in\text{supp}(\widehat{p}+\widehat{q})$.

######  Remark 6.5.

Note that the assumption $|\widehat{u}(x,s)|\leq 1$ definitely holds for at
least small time intervals since the training dynamics are smooth and
$\widehat{u}(x,0)=0$. Moreover, we crucially use the fact that the training
loss is decreasing for the proof of Lemma 5.15.

Recall from Corollary 4.9 the $\epsilon$-detection time thresholds for the
zero-time NTK two-sample test given by

$\displaystyle t_{1}^{*}(\epsilon)$
$\displaystyle:=\min_{S\in\mathcal{S}_{1}(\epsilon)}\lambda_{\min}(S)\log\Bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}-\epsilon}\Bigg{)},$
$\displaystyle t_{2}^{*}(\epsilon)$
$\displaystyle:=\max_{S\in\mathcal{S}_{2}(\epsilon)}\lambda_{\max}(S)\log\Bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon}\Bigg{)}.$

From a birds-eye view, note that the following realistic time analysis
theorems assume

  1. 1.

5.2 and 5.3

  2. 2.

For the minimum $\epsilon$-detection time analysis, $t_{1}^{*}(\epsilon)\leq
t\leq\min(R^{2},\widehat{\tau})$, where $\widehat{\tau}$ comes from 6.4. For
the maximum $\epsilon$-undetectability time analysis,
$t\leq\min\\{R^{2},t_{2}^{*}(\epsilon)\\}$.

To counteract the time-valued approximation error of $\bar{u}$ with
$\widehat{u}$, we must assume that the error detection level is greater than
the approximation error.

######  Theorem 6.6 (Minimum Detection Time – Realistic).

Let $\epsilon>0$. Assume that 5.2, 5.3, and 6.4 hold. If
$\max(R^{2},\widehat{\tau})\geq t\geq t_{1}^{*}(\epsilon)$, then

  1. 1.

with probability $\geq 1-2(n_{p}^{-A}+n_{q}^{-A})$,

$\displaystyle|\widehat{T}_{train}(t)|$
$\displaystyle\geq\epsilon-\delta_{train}(t_{1}^{*}(\epsilon)),$

  2. 2.

with probability $\geq 1-(n_{p}^{-A}+n_{q}^{-A}+m_{p}^{-A}+m_{q}^{-A})$,

$\displaystyle|\widehat{T}_{test}(t)|$
$\displaystyle\geq\epsilon-\delta_{train}(t_{1}^{*}(\epsilon))-L_{1}^{2}t\sqrt{2}\bigg{(}\sqrt{A\log(m_{p})/m_{p}}+\sqrt{A\log(m_{q})/m_{q}}$
$\displaystyle+\sqrt{A\log(n_{p})/n_{p}}+\sqrt{A\log(n_{q})/n_{q}}\bigg{)},$

  3. 3.

with probability $\geq 1-(n_{p}^{-A}+n_{q}^{-A})$,

$\displaystyle|\widehat{T}_{pop}(t)|$
$\displaystyle\geq\epsilon-\delta_{train}(t_{1}^{*}(\epsilon))-L_{1}^{2}t\sqrt{2}\bigg{(}\sqrt{A\log(n_{p})/n_{p}}+\sqrt{A\log(n_{q})/n_{q}}\bigg{)},$

where the approximation error function

$\displaystyle\delta_{train}(t)$
$\displaystyle=C(L_{1},A,n_{p},n_{q})t+C_{2}t^{3/2}+C_{3}t^{2}+C_{4}t^{5/2}$

comes from Proposition 5.13 with training samples and $t_{1}^{*}(\epsilon)$
from Corollary 4.9. Moreover, if $\epsilon$ is not large enough to make the
right-hand sides of the inequalities positive, the bounds are vacuous.

We don’t need monotonicity for the maximum undetectibility time case in
Corollary 4.9 because we use the regular triangle inequality. Thus, the
following theorem holds for each of $\widehat{T}_{train},\widehat{T}_{test},$
and $\widehat{T}_{pop}$ with their respective time-approximation error
functions

$\displaystyle\delta_{test}(t)$
$\displaystyle=C(L_{1},A,m_{p},m_{q})t+C_{2}t^{3/2}+C_{3}t^{2}+C_{4}t^{5/2}$
$\displaystyle\delta_{pop}(t)$
$\displaystyle=C_{1}t+C_{2}t^{3/2}+C_{3}t^{2}+C_{4}t^{5/2},$

where $C_{1},C_{2},C_{3},C_{4}$ are constants from Proposition 5.11 and
$C(L_{1},A,m_{p},m_{q})$ comes from Proposition 5.13.

######  Theorem 6.7 (Maximum Undetectability Time – Realistic).

Let $\epsilon>0$ and assume

$\displaystyle t\leq\min\Big{\\{}R^{2},t_{2}^{*}(\epsilon)\Big{\\}},$

where $t_{2}^{*}(\epsilon)$ is defined in Corollary 4.9. Then

  1. 1.

with probability $\geq 1-2(n_{p}^{-A}+n_{q}^{-A})$, we have

$\displaystyle|\widehat{T}_{train}(t)|$
$\displaystyle\leq\epsilon+\delta_{train}(t_{2}^{*}(\epsilon)),$

  2. 2.

with probability $\geq 1-(n_{p}^{-A}+n_{q}^{-A}+m_{p}^{-A}+m_{q}^{-A})$, we
have

$\displaystyle|\widehat{T}_{test}(t)|$
$\displaystyle\leq\epsilon+\delta_{test}(t_{2}^{*}(\epsilon)),$

  3. 3.

with probability $\geq 1-(n_{p}^{-A}+n_{q}^{-A})$, we have

$\displaystyle|\widehat{T}_{pop}(t)|$
$\displaystyle\leq\epsilon+\delta_{pop}(t_{2}^{*}(\epsilon)).$

where $\delta_{train},\delta_{test},\delta_{pop}$ are time approximation error
functions coming from Remark 5.14 and Proposition 5.12.

We include the proofs of both Theorem 6.6 and Theorem 6.7 in Appendix C. These
theorems are used to perform the power analysis in Section 6.3.

###  6.3 Realistic Statistical Power Analysis

Assuming we are in the realistic dynamics scenario, we want to perform some
amount of test power analysis by showing that the amount of time it takes to
detect a desired deviation level $\epsilon>0$ is much faster in the
alternative hypothesis case versus the null hypothesis case. To do such
quantitative analysis, however, we need a more concrete setting. To this end,
consider the more concrete setting of $f^{*}$ lying on the first $k$
eigenfunctions of $K_{0}$. Now, we want to see if the time to detect
$\epsilon$ is larger whether we are in the null hypothesis or in the first $k$
eigenfunction assumption. Solving this problem becomes slightly complex since
there is a time-approximate error term in the deviation that comes from
Proposition 5.13. Since this assumption is not exactly the logical complement
of the null, we define the setting more concretely.

######  Definition 6.8 (Projected Target Function).

If $\Pi_{K_{0}}(f^{*})$ nontrivially projects only onto the first $k$
eigenfunctions of $K_{0}$ holds true, we denote the projected target function
on the first $k$ eigenfunctions as $\Pi_{K_{0}}(f^{*})=f^{*}_{k}$. We denote
the test statistic when $f^{*}_{k}\neq 0$ by
$\widehat{T}_{train,k}(t),\widehat{T}_{test,k}(t),\widehat{T}_{pop,k}(t)$
evaluated on the training set, test set, and population, respectively, and
when the evaluation set is understood from the context, we use
$\widehat{T}_{k}(t)$. If $p=q$, we say the null hypothesis holds. We denote
the test statistic under this null hypothesis by
$\widehat{T}_{train,null}(t),\widehat{T}_{test,null}(t)$, and
$\widehat{T}_{pop,null}(t)$ depending on the evaluation set, and when the
evaluation set is understood from the context, we use $\widehat{T}_{null}(t)$.

In this definition, note $f^{*}$ is not supported on just the first $k$
eigenfunctions, but rather only the projection via the zero-time kernel
$\Pi_{K_{0}}(f^{*})$ is supported on the first $k$ eigenfunctions. This means
that $f^{*}$ may have a nonzero component that is orthogonal to
$\Pi_{K_{0}}(f^{*})$. Note that we have three two-sample test situations since
the two-sample test depends on which dataset it is evaluated on. In
particular, we will combine the results for
$\widehat{T}_{pop},\widehat{T}_{test},$ and $\widehat{T}_{train}$ into the
following corollary since the only difference is given by a difference in
constants.

######  Corollary 6.9 (Realistic Test Time Analysis).

Let $\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}/2>\epsilon>0$ be a detection
level. Now consider the evaluation dependent constant

$\displaystyle
C^{+}=\begin{cases}C_{pop}^{+}=\sqrt{2}L_{1}^{2}4&\widehat{T}_{pop}(t)\text{
evaluation}\\\
C_{train}^{+}=\sqrt{2}L_{1}^{2}\Bigg{(}4+\sqrt{A\frac{\log(n_{p})}{n_{p}}}+\sqrt{A\frac{\log(n_{q})}{n_{q}}}\Bigg{)}&\widehat{T}_{train}(t)\text{
evaluation}\\\
C_{test}^{+}=\sqrt{2}L_{1}^{2}\Bigg{(}4+\sqrt{A\frac{\log(m_{p})}{m_{p}}}+\sqrt{A\frac{\log(m_{q})}{m_{q}}}\Bigg{)}&\widehat{T}_{test}(t)\text{
evaluation}\end{cases},$

coming from Proposition 5.13 and Proposition 5.12 and consider a time
separation level $\epsilon/C^{+}\geq\gamma>0$. Let $t^{-}(\epsilon)$ be such
that for $t\geq t^{-}(\epsilon)$, we have $\widehat{T}_{k}(t)\geq\epsilon$
(for our different evaluation settings). Similarly, let $t^{+}(\epsilon)$ be
such that for $t\geq t^{+}(\epsilon)$, we have
$\widehat{T}_{null}(t)\geq\epsilon$. If we assume

$\displaystyle\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}>\max\Bigg{\\{}\frac{2\epsilon\exp\Big{(}(\epsilon/C^{+}-\gamma)/\lambda_{k}\Big{)}}{\exp\Big{(}(\epsilon/C^{+}-\gamma)/\lambda_{k}\Big{)}-1},\max_{a\in\\{1,5/2\\}}\frac{2\epsilon\exp\Big{(}(\epsilon/C^{-})^{1/a}/\lambda_{k}\Big{)}}{\exp\Big{(}(\epsilon/C^{-})^{1/a}/\lambda_{k}\Big{)}-1}\Bigg{\\}},$

where $C^{-}=C^{+}+C_{2}+C_{3}+C_{4}$ and the constants $C_{2},C_{3},C_{4}$
coming from Proposition 5.11, then

$\displaystyle t^{+}(\epsilon)-t^{-}(\epsilon)\geq\gamma>0$

with probability

$\displaystyle\geq\begin{cases}1-(n_{p}^{-A}+n_{q}^{-A})&\widehat{T}_{pop}(t)\text{
evaluation}\\\
1-(n_{p}^{-A}+n_{q}^{-A}+m_{p}^{-A}+m_{q}^{-A})&\widehat{T}_{test}(t)\text{
evaluation}\\\ 1-2(n_{p}^{-A}+n_{q}^{-A})&\widehat{T}_{train}(t)\text{
evaluation}\end{cases}.$

The proof of Corollary 6.9 is in Appendix C. To discuss statistical power, we
use the following statement to show that for a particular type 1 error

$\displaystyle\mathbb{P}(\widehat{T}_{null}(t)>\tau|H_{0})=\alpha$

the statistical power goes to 1, i.e. we have

$\displaystyle\mathbb{P}\Big{(}\widehat{T}_{test}(t)>\tau\big{|}\Pi_{K_{0}}(f^{*})=f_{k}^{*}\Big{)}\xrightarrow{n_{p},n_{q},m_{p},m_{q}\to\infty}1.$

This idea is formalized in the following corollary.

######  Corollary 6.10 (Realistic Test Power Analysis).

Let $\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}/2>\epsilon>0$ be a detection
level. Given training and test sample sizes $n_{p},n_{q},m_{p},m_{q}$, let

$\displaystyle\widetilde{C}=\sqrt{2}L_{1}^{2}\Bigg{(}\sqrt{\frac{A\log(m_{p})}{m_{p}}}+\sqrt{\frac{A\log(m_{q})}{m_{q}}}+\sqrt{\frac{A\log(n_{p})}{n_{p}}}+\sqrt{\frac{A\log(n_{q})}{n_{q}}}\bigg{)}$

and $C^{-}_{test}=C^{+}_{test}+C_{2}+C_{3}+C_{4}$, where constants
$C^{+}_{test}$ come from Corollary 6.9 and $C_{2},C_{3},C_{4}$ come from
Proposition 5.11. If we assume

$\displaystyle\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}>\max_{a\in\\{1,5/2\\}}\frac{2\epsilon\exp\Big{(}(\epsilon/(C^{-}_{test}+\widetilde{C}))^{1/a}/\lambda_{k}\Big{)}}{\exp\Big{(}(\epsilon/(C^{-}_{test}+\widetilde{C}))^{1/a}/\lambda_{k}\Big{)}-1},$

then for

$\displaystyle t_{1}^{*}(2\epsilon)\leq
t\leq\min_{a\in\\{1,5/2\\}}\bigg{(}\frac{\epsilon}{C_{test}^{-}+\widetilde{C}}\bigg{)}^{1/a},$

we have $\widehat{T}_{test,k}(t)>\epsilon$ and
$\widehat{T}_{test,null}(t)<\epsilon$ with probability $\geq
1-(n_{p}^{-A}+n_{q}^{-A}+m_{p}^{-A}+m_{q}^{-A})$. Moreover, for a two-sample
level $0<\alpha<1$ (typically $\alpha=0.05$) with $\alpha\geq
n_{p}^{-A}+n_{q}^{-A}+m_{p}^{-A}+m_{q}^{-A}$ and test threshold
$\tau\leq\epsilon$, we have

$\displaystyle\mathbb{P}\Big{(}\widehat{T}_{test}(t)>\tau\big{|}\Pi_{K_{0}}(f^{*})=f_{k}^{*}\Big{)}$
$\displaystyle\geq 1-n_{p}^{-A}+n_{q}^{-A}+m_{p}^{-A}+m_{q}^{-A}.$

The proof is included in Appendix C.

######  Remark 6.11.

From the proof of Corollary 6.9, we can see that the maximum time separation
level is governed by

$\displaystyle\frac{\epsilon}{C^{+}}-\lambda_{k}\log\bigg{(}\frac{\|f^{*}_{k}\|_{L^{2}(p+q)}^{2}}{\|f^{*}_{k}\|_{L^{2}(p+q)}^{2}-2\epsilon}\bigg{)}.$

Notice that if $\epsilon=\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}x$ for some fraction
$0<x<1$, then we can simplify this expression. In particular, we see that our
expression changes to

$\displaystyle\gamma(x)$
$\displaystyle=\frac{\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}x}{C^{+}}-\lambda_{k}\log\bigg{(}\frac{1}{1-2x}\bigg{)}$
$\displaystyle=\frac{\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}x}{C^{+}}-\lambda_{k}\log\bigg{(}\frac{1/2}{1/2-x}\bigg{)}.$

From this, we can see that it is necessary that $0<x<\frac{1}{2}$. Note that
as $x\to 0$, we get $\gamma(x)\to 0$; but as $x\to\frac{1}{2}$, we get
$\gamma(x)\to-\infty$. Since $\gamma(x)$ is not decreasing, we can find a
maximum for the time separation $\gamma(x)$. In particular, we see that

$\displaystyle\gamma^{\prime}(x)=\frac{\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}}{C^{+}}-\lambda_{k}\frac{1/2-x}{1/2}\frac{1/2}{(1/2-x)^{2}}=\frac{\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}}{C^{+}}-\lambda_{k}\frac{1}{1/2-x}.$

Notice that $\gamma^{\prime}(x)=0$ implies that

$\displaystyle
x=\frac{1}{2}-\frac{\lambda_{k}C^{+}}{\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}}.$

Moreover, we note that this is a maximum since

$\displaystyle\gamma^{\prime\prime}(x)=-\lambda_{k}\frac{1}{(1/2-x)^{2}}<0.$

Obviously, this only makes sense if

$\displaystyle\frac{1}{2}>\frac{\lambda_{k}C^{+}}{\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}}\iff\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}>2\lambda_{k}C^{+}.$

This means that as long as $f_{k}^{*}$ has large enough norm, our neural
network two-sample test should be most trustworthy when we observe deviation
$\epsilon=\frac{\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}}{2}-\lambda_{k}C^{+}$ since
that is the deviation level with the maximum time separation between the
assumption $\Pi_{K_{0}}(f^{*})=f_{k}^{*}$ and the null hypothesis $p=q$.

######  Remark 6.12.

It is instructive to note what are fixed parameters versus parameters to be
chosen in Corollary 6.9. First, notice that the complexity of our neural
network determines not only the constants $C^{+}$, $C^{-}$, and $\lambda_{k}$
but also whether or not the assumption $\Pi_{K_{0}}(f^{*})=f^{*}_{k}$ holds.
Although $f^{*}=\frac{p-q}{p+q}$ is fixed inherently from the two-sample test
problem, we assume that the complexity of the neural network is fixed at
initialization, which fixes these constants, the hypothesis, and how large
$\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}$ is. This means that the only choosable
parameters are $\epsilon$ and $\gamma$ (which is upper bounded by $\epsilon$).
Moreover, note that the upper bound
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}/2\geq\epsilon>0$ is an artifact of
side-stepping the time-approximation error from Proposition 5.13. In
particular, playing around with the proof of Corollary 6.9, it is possible to
get a different bound for $\|f_{k}^{*}\|_{L^{2}(p+q)}^{2}$ albeit with the
deviation level given by $\epsilon-\delta(t)$ (depending on the evaluation
set).

##  7 Experiments

We run our neural network two-sample test on two different data-generating
processes. One of the data-generating processes is a characteristically hard
two-sample test problem where the datasets $\widehat{P}$ and $\widehat{Q}$
come from a Gaussian mixture model. The second data-generating process only
aims to differentiate two multivariate Gaussians from each other. We scale the
neural network complexity in terms of a ratio with respect to the number of
samples in the training set. Additionally, we run permutation tests to find
the threshold $\tau$ at the $95$-percentile. We run around 500 different tests
and check whether the test statistic is larger than the threshold found from
the 95th percentile. We now showcase specifics of the data generating process
and how the neural network is constructed.

###  7.1 Data Generating Process

Our hard two-sample testing problem is given by setting $P$ and $Q$ both to be
Gaussian mixture models given by

$\displaystyle P$
$\displaystyle=\sum_{i=1}^{2}\frac{1}{2}\mathcal{N}(\mu_{i}^{h},I_{d})$
$\displaystyle Q$
$\displaystyle=\sum_{i=1}^{2}\frac{1}{2}\mathcal{N}\Bigg{(}\mu_{i}^{h},\begin{bmatrix}1&\Delta_{i}^{h}&0_{d-2}\\\
\Delta_{i}^{h}&1&0_{d-2}\\\
0_{d-2}^{\top}&0_{d-2}^{\top}&I_{d-2}\end{bmatrix}\Bigg{)},$

where $\mu_{1}^{h}=0_{d}$, $\mu_{2}^{h}=0.5*\mathbf{1}_{d}$,
$\Delta_{1}^{h}=0.5$, and $\Delta_{2}^{h}=-0.5$. For the purposes of testing,
we assume that we have balanced sampling of $N$ from each distribution $P$ and
$Q$ so that the total number of samples is $2N$. The number of test samples is
typically set to be $M<N$.

###  7.2 Neural Network Architecture

We use a neural network architecture of $L$ layers and a layer-width size of
$k$. We choose the number of parameters in the neural network $kL$ as
different ratios of the number of training samples. For example, if we
consider the ratio $0.01$ and $N=1000$, then $kL=10$. To adhere closely to the
setup of the theory, we initialize our neural network symmetrically to make
sure at time 0 our neural network returns 0. We make sure to initialize the
neural network weights with the He initialization introduced in [16] so that
the weights are initialized from a random normal distribution with variance
$\frac{2}{k}$. This initialization ensures that our neural network training
doesn’t result in any exploding or vanishing gradients. We train the neural
network with a learning rate of 0.1.

###  7.3 Test Results

We have attached below a heatmap of the statistical power as a function of the
number of epochs as well as the ratio of parameters to samples.444All the code
for producing these plots is on Github at
https://github.com/varunkhuran/NTK_Logit.  Additionally we attach the
evolution of the neural network two-sample test for a particular setting for
reference. The hyperparameters for these tests essentially used a learning
rate $\eta=0.1$, $100$ permutation tests, dimensionality of $d=20$, training
sample size of $N=6000$ from each of $P$ and $Q$, a testing sample size of
$M=1000$ from each of $P$ and $Q$, and $L=2$ layers. We train for a maximum of
15 epochs and use a batch size of 50. Moreover, our significance level
$\alpha$ is the $95$th percentile. We calculate the power of our neural
network two-sample test by checking which of our 1000 tests lie past the 95th
percentile of their respective permutation test and calculate the power by the
ratio of all tests that lie past the 95th percentile divided by the total
number of tests 1000. We try this experiment with ratios of parameters to
number of training samples to see any double descent type of behavior in how
well the statistical power performs.

Figure 3: Plots statistical power for each epoch and ratio of parameters-to-
samples when we are in the alternative hypothesis case with $P$ and $Q$ as
above.

Observing Figure 3, we notice that as the number of epochs increases the
statistical power increases as well. On the ratio of parameters to training
samples axis, however, we note that the smaller sized neural networks still
produce fairly good statistical power with enough neural network training. The
case when we are in the null hypothesis with samples drawn from $P$ is shown
in Figure 4. In the null hypothesis, we see that the statistical power is much
lower than in the alternative hypothesis case, as expected.

Figure 4: Plots statistical power for each epoch and ratio of parameters-to-
samples when we are in the null hypothesis case with samples from $P$.

## Acknowledgements

AC was supported by NSF DMS 2012266, NSF CISE 2403452, and a gift from Intel.
XC is partially supported by NSF DMS-2237842, NSF DMS-2134037, NSF DMS-2007040
and Simons Foundation.

## References

  * [1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International conference on machine learning, pages 242–252. PMLR, 2019.
  * [2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  Advances in neural information processing systems, 32, 2019.
  * [3] Mikołaj Bińkowski, Danica J Sutherland, Michael Arbel, and Arthur Gretton.  Demystifying mmd gans.  arXiv preprint arXiv:1801.01401, 2018.
  * [4] Graham L Bradley, Zakaria Babutsidze, Andreas Chai, and Joseph P Reser.  The role of climate change risk perception, response efficacy, and psychological adaptation in pro-environmental behavior: A two nation study.  Journal of Environmental Psychology, 68:101410, 2020.
  * [5] K Bucci, M Tulio, and CM Rochman.  What is known and unknown about the effects of plastic pollution: A meta-analysis and systematic review.  Ecological Applications, 30(2):e02044, 2020.
  * [6] Alvin C Burns and Ann Veeck.  Marketing research.  Pearson, 2020.
  * [7] Xiuyuan Cheng and Alexander Cloninger.  Classification logit two-sample testing by neural networks for differentiating near manifold densities.  IEEE Transactions on Information Theory, 68(10):6631–6662, October 2022.
  * [8] Xiuyuan Cheng, Alexander Cloninger, and Ronald R Coifman.  Two-sample statistics based on anisotropic kernels.  Information and Inference: A Journal of the IMA, 9(3):677–719, 2020\.
  * [9] Xiuyuan Cheng and Yao Xie.  Neural tangent kernel maximum mean discrepancy.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 6658–6670. Curran Associates, Inc., 2021.
  * [10] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  Advances in neural information processing systems, 32, 2019.
  * [11] Kacper P Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton.  Fast two-sample testing with analytic representations of probability measures.  Advances in Neural Information Processing Systems, 28, 2015.
  * [12] S. Dara, S. Dhamercherla, S.S. Jadav, et al.  Machine learning in drug discovery: A review.  Artificial Intelligence Review, 55:1947–1999, 2022.
  * [13] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  arXiv preprint arXiv:1810.02054, 2018.
  * [14] Jerome H Friedman.  On multivariate goodness-of-fit and two-sample testing.  Statistical Problems in Particle Physics, Astrophysics, and Cosmology, 1:311, 2003.
  * [15] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  J. Mach. Learn. Res., 13(null):723–773, mar 2012.
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE international conference on computer vision, pages 1026–1034, 2015.
  * [17] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  Advances in neural information processing systems, 31, 2018.
  * [18] Matthias Kirchler, Shahryar Khorasani, Marius Kloft, and Christoph Lippert.  Two-sample testing using deep learning.  In International Conference on Artificial Intelligence and Statistics, pages 1387–1398. PMLR, 2020.
  * [19] Jonas M Kübler, Wittawat Jitkrittum, Bernhard Schölkopf, and Krikamol Muandet.  A witness two-sample test.  In International Conference on Artificial Intelligence and Statistics, pages 1403–1419. PMLR, 2022.
  * [20] Jonas M Kübler, Vincent Stimper, Simon Buchholz, Krikamol Muandet, and Bernhard Schölkopf.  Automl two-sample test.  Advances in Neural Information Processing Systems, 35:15929–15941, 2022.
  * [21] Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124002, December 2020.
  * [22] Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J Sutherland.  Learning deep kernels for non-parametric two-sample tests.  In International conference on machine learning, pages 6316–6326. PMLR, 2020.
  * [23] David Lopez-Paz and Maxime Oquab.  Revisiting classifier two-sample tests.  In International Conference on Learning Representations, 2017.
  * [24] Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration.  Applied and Computational Harmonic Analysis, 59:3–84, 2022.
  * [25] Matthew Repasky, Xiuyuan Cheng, and Yao Xie.  Neural stein critics with staged L2-regularization.  IEEE Transactions on Information Theory, 2023.
  * [26] Antonin Schrab, Ilmun Kim, Mélisande Albert, Béatrice Laurent, Benjamin Guedj, and Arthur Gretton.  Mmd aggregated two-sample test.  Journal of Machine Learning Research, 24(194):1–81, 2023.

##  Appendix A Proofs for Section 4.3

###### Proof of Proposition 4.3.

We simply just need to take the derivative of the solution and show that it is
exactly the differential equation, then the uniqueness of solutions of
differential equations implies that our ansatz is indeed the solution. To see
this, let us call the solution

$\displaystyle e^{*}(\cdot,t)=\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}u_{\ell}.$

Now notice that

$\displaystyle\partial_{t}e^{*}(\cdot,t)=-\sum_{\ell=1}^{M}\lambda_{\ell}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}u_{\ell}.$

On the other hand, let us plug in the ansatz $e^{*}$ into the differential
equation and see what we get. In particular,

$\displaystyle-\sum_{j=1}^{M}\lambda_{j}\langle
u_{j},e^{*}(\cdot,t)\rangle_{L^{2}(p+q)}u_{j}$
$\displaystyle=-\sum_{j=1}^{M}\lambda_{j}\langle
u_{j},\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}u_{\ell}\rangle_{L^{2}(p+q)}u_{j}$
$\displaystyle=-\sum_{j,\ell=1}^{M}\lambda_{j}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}\underbrace{\langle
u_{j},u_{\ell}\rangle_{L^{2}(p+q)}}_{\delta_{j\ell}}u_{j}$
$\displaystyle=-\sum_{\ell=1}^{M}\lambda_{\ell}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}u_{\ell}$
$\displaystyle=\partial_{t}e^{*}(\cdot,t).$

This shows the result. ∎

###### Proof of Lemma 4.4.

Now our two-sample test statistic becomes

$\displaystyle\overline{T}(t)$
$\displaystyle=\overline{\mu_{P}}(t)-\overline{\mu_{Q}}(t)$
$\displaystyle=\int_{\mathbb{R}^{d}}\Pi_{K_{0}}(f^{*})(x)(p-q)(x)dx+\int_{\mathbb{R}^{d}}\bar{e}(x,t)d(p-q)(x)$
$\displaystyle=\int_{\mathbb{R}^{d}}\Pi_{K_{0}}(f^{*})(x)\frac{p-q}{p+q}(x)d(p+q)(x)+\int_{\mathbb{R}^{d}}\bar{e}(x,t)d(p-q)(x)$
$\displaystyle=\langle\Pi_{K_{0}}(f^{*}),f^{*}\rangle_{L^{2}(p+q)}+\int_{\mathbb{R}^{d}}\bar{e}(x,t)d(p-q)(x).$

Extending the eigenfunctions $\\{u_{\ell}\\}_{\ell=1}^{M}$ to a full basis for
$L^{2}(p+q)$ given by $\\{u_{\ell}\\}_{\ell=1}^{\infty}$, we can see that the
term with $f^{*}$ reduces to

$\displaystyle\langle\Pi_{K_{0}}(f^{*}),f^{*}\rangle_{L^{2}(p+q)}$
$\displaystyle=\bigg{\langle}\sum_{\ell=1}^{\infty}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}u_{\ell},\sum_{\ell^{\prime}=1}^{\infty}\langle
u_{\ell}^{\prime},f^{*}\rangle_{L^{2}(p+q)}u_{\ell}^{\prime}\bigg{\rangle}_{L^{2}(p+q)}$
$\displaystyle=\sum_{\ell=1}^{\infty}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}$
$\displaystyle=\sum_{\ell=1}^{\infty}\underbrace{\langle\Pi_{K_{0}}(u_{\ell}),f^{*}\rangle_{L^{2}(p+q)}}_{\ell>M\implies
0}\langle u_{\ell},f^{*}\rangle_{L^{2}(p+q)}$
$\displaystyle=\sum_{\ell=1}^{M}\langle\Pi_{K_{0}}(u_{\ell}),f^{*}\rangle_{L^{2}(p+q)}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}$ $\displaystyle=\sum_{\ell=1}^{M}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}.$

Now since $\langle u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}=\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}$ for $\ell\leq M$, we see that

$\displaystyle\langle\Pi_{K_{0}}(f^{*}),f^{*}\rangle_{L^{2}(p+q)}$
$\displaystyle=\sum_{\ell=1}^{M}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}^{2}$
$\displaystyle=\langle\Pi_{K_{0}}(f^{*}),\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}.$

At this point, we plug in our ansatz and get

$\displaystyle\overline{T}(t)$
$\displaystyle=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}+\int_{\mathbb{R}^{d}}\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}u_{\ell}(x)d(p-q)(x)$
$\displaystyle=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}+\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}\int_{\mathbb{R}^{d}}u_{\ell}(x)d(p-q)(x).$

At this point, recall that we used the initialization $\theta_{0}$ such that
$\bar{e}(\cdot,0)=\bar{u}(x,0)-\Pi_{K_{0}}(f^{*})=f(x,\theta_{0})-\Pi_{K_{0}}(f^{*})=-\Pi_{K_{0}}(f^{*})=\Pi_{K_{0}}\big{(}\frac{q-p}{p+q}\big{)}(x)$.
Along with the fact that $\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}=\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}$ for $\ell\leq M$, we use this fact to see
that

$\displaystyle\langle u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}$
$\displaystyle=\langle u_{\ell},-\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}$
$\displaystyle=\int_{\mathbb{R}^{d}}u_{\ell}(x)\Pi_{K_{0}}\Big{(}\frac{q-p}{p+q}\Big{)}(x)(p(x)+q(x))dx$
$\displaystyle=\int_{\mathbb{R}^{d}}u_{\ell}(x)\frac{q-p}{p+q}(x)(p(x)+q(x))dx$
$\displaystyle=\int_{\mathbb{R}^{d}}u_{\ell}(x)d(q-p)(x)$
$\displaystyle\implies\langle u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}$
$\displaystyle=-\int_{\mathbb{R}^{d}}u_{\ell}(x)d(p-q)(x).$

This means that

$\displaystyle\overline{T}(t)$
$\displaystyle=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}+\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}\underbrace{\int_{\mathbb{R}^{d}}u_{\ell}(x)d(p-q)(x)}_{-\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}}$
$\displaystyle=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\sum_{\ell\geq
1}e^{-t\lambda_{\ell}}\langle
u_{\ell},\bar{e}(\cdot,0)\rangle_{L^{2}(p+q)}^{2}.$

We get the result by seeing that $\bar{e}(\cdot,0)=-\Pi_{K_{0}}(f^{*})$ and
that applying the square gets rid of the negative sign. So we’re done. ∎

###### Proof of Proposition 4.6.

We want to find the smallest time $t$ so that

$\displaystyle\overline{T}(t)$ $\displaystyle\geq\epsilon$
$\displaystyle\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}^{2}$
$\displaystyle\geq\epsilon$
$\displaystyle\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon$
$\displaystyle\geq\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}^{2}.$

Now using our specific subset $S\subseteq\\{1,\dotsc,M\\}$, so that

$\displaystyle\langle u_{\ell},f^{*}\rangle_{L^{2}(p+q)}=\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)},$

allows us to consider the following analysis.

$\displaystyle\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}$ $\displaystyle=\sum_{\ell\in
S}\underbrace{e^{-t\lambda_{\ell}}}_{\leq e^{-t\lambda_{\min}(S)}}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}+\sum_{\ell\not\in
S}\underbrace{e^{-t\lambda_{\ell}}}_{\leq 1}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}$ $\displaystyle\leq
e^{-t\lambda_{\min}(S)}\underbrace{\sum_{\ell\in S}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}}_{\|f^{*}\|_{S}^{2}}+\underbrace{\sum_{\ell\not\in
S}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}}_{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\|f^{*}\|_{S}^{2}}$
$\displaystyle=e^{-t\lambda_{\min}(S)}\|f^{*}\|_{S}^{2}+\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\|f^{*}\|_{S}^{2}.$

We want this quantity to still be less than
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon$ and to ensure this, we get

$\displaystyle
e^{-t\lambda_{\min}(S)}\|f^{*}\|_{S}^{2}+\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\|f^{*}\|_{S}^{2}$
$\displaystyle\leq\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon$
$\displaystyle e^{-t\lambda_{\min}(S)}\|f^{*}\|_{S}^{2}-\|f^{*}\|_{S}^{2}$
$\displaystyle\leq-\epsilon$ $\displaystyle e^{-t\lambda_{\min}(S)}-1$
$\displaystyle\leq-\frac{\epsilon}{\|f^{*}\|_{S}^{2}}$ $\displaystyle
e^{-t\lambda_{\min}(S)}$ $\displaystyle\leq
1-\frac{\epsilon}{\|f^{*}\|_{S}^{2}}$ $\displaystyle-t\lambda_{\min}(S)$
$\displaystyle\leq\log\Big{(}1-\frac{\epsilon}{\|f^{*}\|_{S}^{2}}\Big{)}$
$\displaystyle t$
$\displaystyle\geq\log\bigg{(}\Big{(}1-\frac{\epsilon}{\|f^{*}\|_{S}^{2}}\Big{)}^{-\lambda_{\min}(S)}\bigg{)}.$

Rearranging the right-hand side and noticing that on $S$ we have
$\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}=\|f^{*}\|_{S}^{2}$, we get the result. ∎

###### Proof of Proposition 4.8.

We want to find the largest time $t$ so that

$\displaystyle\overline{T}(t)$ $\displaystyle\leq\epsilon$
$\displaystyle\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}^{2}$
$\displaystyle\leq\epsilon$
$\displaystyle\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon$
$\displaystyle\leq\sum_{\ell\geq 1}e^{-t\lambda_{\ell}}\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}^{2}.$

Now using our specific subset $S$ and that $\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle_{L^{2}(p+q)}=\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}$ for $\ell\leq M$ allows us to consider the
following analysis.

$\displaystyle\sum_{\ell=1}^{M}e^{-t\lambda_{\ell}}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}$ $\displaystyle=\sum_{\ell\in
S}\underbrace{e^{-t\lambda_{\ell}}}_{\geq e^{-t\lambda_{\max}(S)}}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}+\sum_{\ell\not\in
S}\underbrace{e^{-t\lambda_{\ell}}}_{\geq 0}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}^{2}$ $\displaystyle\geq
e^{-t\lambda_{\max}(S)}\underbrace{\sum_{\ell\in S}\langle
u_{\ell},f^{*}\rangle_{L^{2}(p+q)}}_{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}$
$\displaystyle=e^{-t\lambda_{\max}(S)}\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}.$

We want our lower bound found above to still be greater than
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon$ and to ensure this, we get

$\displaystyle e^{-t\lambda_{\max}(S)}\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}$
$\displaystyle\geq\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}-\epsilon$
$\displaystyle e^{-t\lambda_{\max}(S)}$
$\displaystyle\geq\frac{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}-\frac{\epsilon}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}$
$\displaystyle-t\lambda_{\max}(S)$
$\displaystyle\geq\log\bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}-\frac{\epsilon}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}\bigg{)}$
$\displaystyle t$
$\displaystyle\leq\log\Bigg{\\{}\bigg{(}\frac{\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}-\frac{\epsilon}{\|\Pi_{K_{0}}(f^{*})\|_{S}^{2}}\bigg{)}^{-\lambda_{\max}(S)}\Bigg{\\}}.$

Rearranging the right-hand side, we get the result. ∎

##  Appendix B Proofs for Population Dynamics

###### Proof of Lemma 5.4.

Recall that the dynamics of $\theta$ can be written as

$\displaystyle\dot{\theta}(t)=-\nabla_{\theta}\mathcal{L}(\theta(t))=-\mathbb{E}_{x\sim
p+q}\big{[}\nabla_{\theta}f(x,\theta(t))e(x,t)\big{]}.$

Moreover, note that we can write

$\displaystyle\|\theta(t)-\theta(0)\|$
$\displaystyle\leq\int_{0}^{t}\|\dot{\theta}(s)\|ds\leq\int_{0}^{t}\|\nabla_{\theta}\mathcal{L}(\theta(s))\|ds$
$\displaystyle\leq\sqrt{t}\bigg{(}\int_{0}^{t}\|\nabla_{\theta}\mathcal{L}(\theta(s))\|^{2}ds\bigg{)}^{1/2},$

where the last inequality comes from the basic $L_{p}$-$L_{q}$ inclusion
inequality. Additionally, we know that

$\displaystyle\frac{d}{dt}\mathcal{L}(\theta(t))=\langle\nabla_{\theta}\mathcal{L}(\theta(t)),\dot{\theta}(t)\rangle=-\|\nabla_{\theta}\mathcal{L}(\theta(t))\|^{2}\leq
0.$

This not only implies that $\mathcal{L}(\theta(t))$ is decreasing but also
allows us to write

$\displaystyle\|\theta(t)-\theta(0)\|$
$\displaystyle\leq\sqrt{t}\bigg{(}\int_{0}^{t}\|\nabla_{\theta}\mathcal{L}(\theta(s))\|^{2}ds\bigg{)}^{1/2}$
$\displaystyle=\sqrt{t}\Big{(}\mathcal{L}(\theta(0))-\mathcal{L}(\theta(t))\Big{)}^{1/2}$
$\displaystyle\leq\sqrt{t}\sqrt{\mathcal{L}(\theta(0))}.$

At this point, we can notice that
$\mathcal{L}(\theta(0))=\|u(x,0)-f^{*}\|_{L^{2}(p+q)}^{2}=\|f^{*}\|_{L^{2}(p+q)}^{2}$.
This finally gives us the result

$\displaystyle\|\theta(t)-\theta(0)\|$
$\displaystyle\leq\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}.$

We need $\theta(t)\in B_{R}$ and one way to ensure this is

$\displaystyle\|\theta(t)-\theta(0)\|$
$\displaystyle\leq\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}\leq R$ $\displaystyle\implies
t$ $\displaystyle\leq\bigg{(}\frac{R}{\|f^{*}\|_{L^{2}(p+q)}}\bigg{)}^{2}$

∎

###### Proof of Lemma 5.5.

Let $w\in L^{2}(p+q)$, then note that for our kernel integral operator
$K_{t}$, we have $\langle w,\mathbb{E}_{x^{\prime}\sim
p+q}K_{t}(\cdot,x^{\prime})w(x^{\prime})\rangle_{L^{2}(p+q)}$ equals

$\displaystyle\mathbb{E}_{x\sim p+q}\mathbb{E}_{x^{\prime}\sim
p+q}w(x)\langle\nabla_{\theta}f(x,\theta(t)),\nabla_{\theta}f(x^{\prime},\theta(t))\rangle_{\Theta}w(x^{\prime})$
$\displaystyle=\langle\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x),\mathbb{E}_{x^{\prime}\sim
p+q}\nabla_{\theta}f(x^{\prime},\theta(t))w(x^{\prime})\rangle_{\Theta}$
$\displaystyle=\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}^{2}.$

This means that $\langle w,\mathbb{E}_{x^{\prime}\sim
p+q}(K_{t}-K_{0})(\cdot,x^{\prime})w(x^{\prime})\rangle_{L^{2}(p+q)}$ equals

$\displaystyle\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}^{2}-\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(0))w(x)\|_{\Theta}^{2}$
$\displaystyle=(\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}+\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(0))w(x)\|_{\Theta})$
$\displaystyle\cdot(\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}-\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(0))w(x)\|_{\Theta}).$

Now using Minkowski’s integral inequality and 5.2(1), we get

$\displaystyle\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}$
$\displaystyle\leq\mathbb{E}_{x\sim
p+q}\|\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}$
$\displaystyle\leq\mathbb{E}_{x\sim
p+q}\|\nabla_{\theta}f(x,\theta(t))\|_{\Theta}\|w(x)\|$ $\displaystyle\leq
L_{1}\mathbb{E}_{x\sim p+q}\|w(x)\|$ $\displaystyle\leq
L_{1}\|w\|_{L^{2}(p+q)}.$

Notice that this implies

$\displaystyle\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}+\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(0))w(x)\|_{\Theta}\leq
2L_{1}\|w\|_{L^{2}(p+q)}.$

Now using 5.2(2), we have

$\displaystyle\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(t))w(x)\|_{\Theta}-\|\mathbb{E}_{x\sim
p+q}\nabla_{\theta}f(x,\theta(0))w(x)\|_{\Theta}$
$\displaystyle\leq\|\mathbb{E}_{x\sim
p+q}(\nabla_{\theta}f(x,\theta(t))-\nabla_{\theta}f(x,\theta(0)))w(x)\|_{\Theta}$
$\displaystyle\leq\mathbb{E}_{x\sim
p+q}\|\nabla_{\theta}f(x,\theta(t))-\nabla_{\theta}f(x,\theta(0))\|_{\Theta}\|w(x)\|$
$\displaystyle\leq L_{2}\|\theta(t)-\theta(0)\|_{\Theta}\|w\|_{L^{2}(p+q)}$
$\displaystyle\leq L_{2}\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}\|w\|_{L^{2}(p+q)}.$

This means that

$\displaystyle\langle w,\mathbb{E}_{x^{\prime}\sim
p+q}K_{t}(\cdot,x^{\prime})w(x^{\prime})\rangle_{L^{2}(p+q)}\leq
2L_{1}L_{2}\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}\|w\|_{L^{2}(p+q)}^{2}.$

Finally this proves that $\|K_{t}-K_{0}\|_{L^{2}(p+q)}\leq
2L_{1}L_{2}\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}$. ∎

###### Proof of Proposition 5.6.

Note that

$\displaystyle\partial_{t}(u-\bar{u})(x,t)=\partial_{t}(e-\bar{e})(x,t)=\mathbb{E}_{x^{\prime}\sim
p+q}\big{[}K_{0}(x,x^{\prime})\bar{e}(x^{\prime},t)-K_{t}(x,x^{\prime})e(x^{\prime},t)\big{]}$
$\displaystyle=-\mathbb{E}_{x^{\prime}\sim
p+q}\big{[}(K_{t}(x,x^{\prime})-K_{0}(x,x^{\prime}))\bar{e}(x^{\prime},t)+K_{t}(x,x^{\prime})(e-\bar{e})(x^{\prime},t)\big{]}.$

Notice here that because
$K_{t}(x,x^{\prime})=\langle\nabla_{\theta}f(x,\theta(t)),\nabla_{\theta}f(x^{\prime},\theta(t))\rangle$,
we have that $K_{t}$ is a positive semi-definite operator (we will use this
later). Now if we take an inner product with $e-\bar{e}$ on both sides of the
equation, we get

$\displaystyle\frac{d}{dt}\frac{1}{2}\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}^{2}$
$\displaystyle=\langle(e-\bar{e})(\cdot,t),\partial_{t}(e-\bar{e})(\cdot,t)\rangle_{L^{2}(p+q)}$
$\displaystyle=\langle(e-\bar{e})(\cdot,t),-\mathbb{E}_{x^{\prime}\sim
p+q}\big{[}(K_{t}(x,x^{\prime})-K_{0}(x,x^{\prime}))\bar{e}(x^{\prime},t)$
$\displaystyle+K_{t}(x,x^{\prime})(e-\bar{e})(x^{\prime},t)\big{]}\rangle_{L^{2}(p+q)}$
$\displaystyle\leq|\langle(e-\bar{e})(\cdot,t),-\mathbb{E}_{x^{\prime}\sim
p+q}\big{[}(K_{t}(x,x^{\prime})-K_{0}(x,x^{\prime}))\bar{e}(x^{\prime},t)\big{]}\rangle_{L^{2}(p+q)}|$
$\displaystyle\leq\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}\|K_{t}-K_{0}\|_{L^{2}(p+q)}\|\bar{e}(\cdot,t)\|_{L^{2}(p+q)}$
$\displaystyle\leq\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}\|K_{t}-K_{0}\|_{L^{2}(p+q)}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)},$

where the first inequality comes from the fact that $K_{t}$ is a positive
semi-definite operator as well as using absolute values whilst the second
inequality comes from using the Cauchy-Schwartz-Bunyakovsky inequality along
with the kernel integral operator norm bound of
$\|K_{t}-K_{0}\|_{L^{2}(p+q)}$. Now recalling that
$\bar{e}(\cdot,0)=\Pi_{K_{0}}(f^{*})$ and using Parseval’s identity, the last
inequality comes from the fact that

$\displaystyle\|\bar{e}(\cdot,t)\|_{L^{2}(p+q)}^{2}$
$\displaystyle=\sum_{\ell=1}^{M}\underbrace{e^{-2t\lambda_{\ell}}}_{\leq
1}|\langle u_{\ell},\bar{e}(\cdot,0)\rangle|^{2}\leq\sum_{\ell=1}^{M}|\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle|^{2}=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}.$

From Lemma 5.5, we get that

$\displaystyle\frac{d}{dt}\frac{1}{2}\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}^{2}$
$\displaystyle\leq
2L_{1}L_{2}\sqrt{t}\|f^{*}\|_{L^{2}(p+q)}\cdot\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\cdot\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}.$

Now, finally notice that

$\displaystyle\frac{1}{2}\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}^{2}$
$\displaystyle=\int_{0}^{t}\Big{(}\frac{d}{dt}\frac{1}{2}\|(e-\bar{e})(\cdot,s)\|_{L^{2}(p+q)}^{2}\Big{)}ds$
$\displaystyle\leq
2L_{1}L_{2}\|f^{*}\|_{L^{2}(p+q)}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\int_{0}^{t}\sqrt{s}\|(e-\bar{e})(\cdot,s)\|_{L^{2}(p+q)}ds.$

Let $t^{*}\leq t$ be the time such that

$\displaystyle\sup_{s\in[0,t]}\|(e-\bar{e})(\cdot,s)\|_{L^{2}(p+q)}=\|(e-\bar{e})(\cdot,t^{*})\|_{L^{2}(p+q)}.$

Then, we find that

$\displaystyle\frac{1}{2}\|(e-\bar{e})(\cdot,t^{*})\|_{L^{2}(p+q)}^{2}$
$\displaystyle\leq
2L_{1}L_{2}\|f^{*}\|_{L^{2}(p+q)}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\|(e-\bar{e})(\cdot,t^{*})\|_{L^{2}(p+q)}\int_{0}^{t^{*}}\sqrt{s}ds,$

but this implies

$\displaystyle\frac{1}{2}\|(e-\bar{e})(\cdot,t^{*})\|_{L^{2}(p+q)}$
$\displaystyle\leq
2L_{1}L_{2}\|f^{*}\|_{L^{2}(p+q)}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\frac{2}{3}(t^{*})^{3/2}$
$\displaystyle\implies\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}$
$\displaystyle\leq
4L_{1}L_{2}\|f^{*}\|_{L^{2}(p+q)}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\frac{2}{3}(t^{*})^{3/2}$
$\displaystyle\leq(8/3)L_{1}L_{2}\|f^{*}\|_{L^{2}(p+q)}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}(t)^{3/2},$

where we use the fact that
$\|(e-\bar{e})(\cdot,t)\|_{L^{2}(p+q)}\leq\|(e-\bar{e})(\cdot,t^{*})\|_{L^{2}(p+q)}$
and $t^{*}\leq t$. Finally using that
$\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\leq\|f^{*}\|_{L^{2}(p+q)}$ gives the
result, so we’re done. ∎

###### Proof of Corollary 5.7.

Notice that

$\displaystyle\Big{|}T(t)-\overline{T}(t)\Big{|}$
$\displaystyle=\bigg{|}\int_{\mathbb{R}^{d}}(u-\bar{u})(x,t)d(p-q)(x)\bigg{|}$
$\displaystyle\leq\bigg{|}\int_{\mathbb{R}^{d}}(u-\bar{u})(x,t)d(p)(x)\bigg{|}+\bigg{|}\int_{\mathbb{R}^{d}}(u-\bar{u})(x,t)d(q)(x)\bigg{|}$
$\displaystyle\leq\int_{\mathbb{R}^{d}}|(u-\bar{u})(x,t)|d(p)(x)+\int_{\mathbb{R}^{d}}|(u-\bar{u})(x,t)|d(q)(x)$
$\displaystyle=\int_{\mathbb{R}^{d}}|(u-\bar{u})(x,t)|d(p+q)(x)$
$\displaystyle\leq\sqrt{2}\|u-\bar{u}\|_{L^{2}(p+q)},$

where the last inequality comes from using a basic $L_{1}$-$L_{2}$ inclusion
inequality. Now using Proposition 5.6, we get the result, and we’re done. ∎

###### Proof of Lemma 5.8.

Note that the loss
$\mathcal{L}(\theta(t))=\|f(\cdot,\theta(t))-f^{*}\|_{L^{2}(p+q)}^{2}$ is
monotonically decreasing since

$\displaystyle\frac{d}{dt}\mathcal{L}(\theta(t))=\langle\nabla_{\theta}\mathcal{L}(\theta(t)),\dot{\theta}(t)\rangle=-\|\nabla_{\theta}\mathcal{L}(\theta(t))\|^{2}\leq
0.$

So we have that $\mathcal{L}(\theta(s))\geq\mathcal{L}(\theta(t))$ if $0\leq
s\leq t\leq\tau$. Writing out the loss as
$\mathcal{L}(\theta(s))=\|f(\cdot,\theta(s))\|_{L^{2}(p+q)}^{2}-2\langle
f(\cdot,\theta(s)),f^{*}\rangle_{L^{2}(p+q)}+\|f^{*}\|_{L^{2}(p+q)}^{2}$, we
can see

$\displaystyle\mathcal{L}(\theta(s))$
$\displaystyle\geq\mathcal{L}(\theta(t))$
$\displaystyle\|f(\cdot,\theta(s))\|_{L^{2}(p+q)}^{2}-2\langle
f(\cdot,\theta(s)),f^{*}\rangle_{L^{2}(p+q)}$
$\displaystyle\geq\|f(\cdot,\theta(t))\|_{L^{2}(p+q)}^{2}-2\langle
f(\cdot,\theta(t)),f^{*}\rangle_{L^{2}(p+q)}$ $\displaystyle\langle
f(\cdot,\theta(t))-f(\cdot,\theta(s)),f^{*}\rangle_{L^{2}(p+q)}$
$\displaystyle\geq|f(\cdot,\theta(t))\|_{L^{2}(p+q)}^{2}-\|f(\cdot,\theta(s))\|_{L^{2}(p+q)}.$

Notice that because $u(x,t)=f(x,\theta(t))$ and we assume that
$\|u(x,t)\|_{L^{2}(p+q)}^{2}$ is increasing in time, we know that

$\displaystyle\langle
f(\cdot,\theta(t))-f(\cdot,\theta(s)),f^{*}\rangle_{L^{2}(p+q)}$
$\displaystyle\geq\underbrace{|f(\cdot,\theta(t))\|_{L^{2}(p+q)}^{2}-\|f(\cdot,\theta(s))\|_{L^{2}(p+q)}}_{\geq
0}$
$\displaystyle\int_{\mathbb{R}^{d}}\big{(}u(x,t)-u(x,s)\big{)}\frac{p-q}{p+q}(x)d(p+q)(x)$
$\displaystyle\geq 0$
$\displaystyle\int_{\mathbb{R}^{d}}\big{(}u(x,t)-u(x,s)\big{)}d(p-q)(x)$
$\displaystyle\geq 0$ $\displaystyle\int_{\mathbb{R}^{d}}u(x,t)d(p-q)(x)$
$\displaystyle\geq\int_{\mathbb{R}^{d}}u(x,s)d(p-q)(x).$

So we see that on the interval $[0,T]$, the two-sample test statistic $T(t)$
is monotonically increasing. ∎

###### Proof of Theorem 6.2.

Using the assumption

$\displaystyle\min\bigg{(}\tau,\Big{(}\frac{R}{\|f^{*}\|_{L^{2}(p+q)}}\Big{)}^{2}\bigg{)}\geq
t\geq t_{1}^{*}(\epsilon)$

allows us to use Corollary 5.7, Corollary 4.9, and Lemma 5.8 simultaneously.
Using monotonicity and the reverse triangle inequality shows that

$\displaystyle|T(t)|$
$\displaystyle\geq|T(t_{1}^{*}(\epsilon))|\geq\Big{|}\overline{T}(t_{1}^{*}(\epsilon))\Big{|}-\Big{|}T(t_{1}^{*}(\epsilon))-\overline{T}(t_{1}^{*}(\epsilon))\Big{|}\bigg{|}$
$\displaystyle\geq\epsilon-\frac{8\sqrt{2}}{3}\|f^{*}\|_{L^{2}(p+q)}^{2}L_{1}L_{2}\big{(}t_{1}^{*}(\epsilon)\big{)}^{3/2}$

where we can get rid of the absolute values by assumption. So we’re done. ∎

###### Proof of Theorem 6.3.

Because of the assumption on $t$, we can use both Corollary 4.9 as well as
Corollary 5.7. Using the triangle inequality gives us

$\displaystyle|T(t)|$
$\displaystyle\leq\Big{|}\overline{T}(t)\Big{|}+\Big{|}T(t)-\overline{T}(t)\Big{|}\leq\epsilon+\frac{8\sqrt{2}}{3}\|f^{*}\|_{L^{2}(p+q)}^{2}L_{1}L_{2}t$
$\displaystyle\leq\epsilon+\frac{8\sqrt{2}}{3}\|f^{*}\|_{L^{2}(p+q)}^{2}L_{1}L_{2}\big{(}t_{2}^{*}(\epsilon)\big{)}^{3/2}.$

So we’re done. ∎

##  Appendix C Proofs for Realistic Dynamics

###### Proof of Lemma 5.9.

Similar to the proof of Lemma 5.4, we recall that

$\displaystyle\dot{\widehat{\theta}}(t)$
$\displaystyle=-\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\nabla_{\theta}f(x,\widehat{\theta}(t))\Big{(}\big{(}f(x,\widehat{\theta}(t))-1\big{)}\widehat{p}(x)+\big{(}f(x,\widehat{\theta}(t))+1\big{)}\widehat{q}(x)\Big{)}dx\bigg{)}$
$\displaystyle=-\nabla_{\theta}\widehat{L}(\widehat{\theta}(t)).$

Moreover, recall that

$\displaystyle\frac{d}{dt}\widehat{L}(\widehat{\theta}(t))=\langle\nabla_{\theta}\widehat{L}(\widehat{\theta}(t)),\dot{\widehat{\theta}}(t)\rangle_{\Theta}=-\|\nabla_{\theta}\widehat{L}(\widehat{\theta}(t))\|_{\Theta}\leq
0.$

This already shows that
$\widehat{L}(\widehat{\theta}(t))\leq\widehat{L}(\theta(0))$. Now, notice that

$\displaystyle\|\widehat{\theta}(t)-\theta(0)\|_{\Theta}$
$\displaystyle\leq\int_{0}^{t}\|\dot{\widehat{\theta}}(s)\|_{\Theta}ds\leq\sqrt{t}\bigg{(}\int_{0}^{t}\|\dot{\widehat{\theta}}(s)\|_{\Theta}^{2}ds\bigg{)}^{1/2}$
$\displaystyle\leq\sqrt{t}\bigg{(}\int_{0}^{t}\|\nabla_{\theta}\widehat{L}(\widehat{\theta}(s))\|_{\Theta}^{2}ds\bigg{)}^{1/2}$
$\displaystyle=\sqrt{t}\sqrt{\widehat{L}(\widehat{\theta}(0))-\widehat{L}(\widehat{\theta}(t))}\leq\sqrt{t}\sqrt{\widehat{L}(\widehat{\theta}(0))}.$

Now because $f(\cdot,\theta(0))=f(\cdot,\widehat{\theta}(0))=0$, we get that

$\displaystyle\widehat{L}(\theta(0))$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\big{(}f(x,\theta(0))-1\big{)}^{2}\widehat{p}(x)dx+\int_{\mathbb{R}^{d}}\big{(}f(x,\theta(0))+1\big{)}^{2}\widehat{q}(x)dx\bigg{)}$
$\displaystyle=\frac{1}{2}\bigg{(}\int_{\mathbb{R}^{d}}\widehat{p}(x)dx+\int_{\mathbb{R}^{d}}\widehat{q}(x)dx\bigg{)}=1.$

So this implies that

$\displaystyle\|\widehat{\theta}(t)-\theta(0)\|_{\Theta}\leq\sqrt{t}.$

For the second statement, just notice that we want to ensure
$\|\widehat{\theta}(t)-\theta(0)\|_{\Theta}\leq R$. With our bounds, this is
ensured if

$\displaystyle\sqrt{t}\leq R.$

Readjusting this expression gives us the result. ∎

###### Proof of Lemma 5.10.

Notice that $\mathbb{E}X_{i}=0$ and

$\displaystyle\|X_{i}\|\leq\|\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top}\|+\mathbb{E}_{x\sim
p}\|\nabla_{\theta}f(x,\theta)\nabla_{\theta}f(x,\theta)^{\top}\|\leq
3L_{1}^{2}.$

Moreover, notice that

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}X_{i}X_{i}^{\top}\|\leq\frac{1}{n}\sum_{i=1}^{n}\|\underbrace{\mathbb{E}X_{i}X_{i}^{\top}}_{I}\|.$

Simplifying $I$, we see

$\displaystyle I$ $\displaystyle=\mathbb{E}_{x_{i}\sim
p}\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top}\|\nabla_{\theta}f(x_{i},\theta)\|^{2}$
$\displaystyle-2(\mathbb{E}_{x_{i}\sim
p}\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top})^{2}$
$\displaystyle+(\mathbb{E}_{x_{i}\sim
p}\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top})^{2}.$

This means that

$\displaystyle I$ $\displaystyle=\mathbb{E}_{x_{i}\sim
p}\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top}\|\nabla_{\theta}f(x_{i},\theta)\|^{2}-(\mathbb{E}_{x_{i}\sim
p}\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top})^{2},$

which implies

$\displaystyle\|I\|$ $\displaystyle\leq\mathbb{E}_{x_{i}\sim
p}\underbrace{\|\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top}\|\|\nabla_{\theta}f(x_{i},\theta)\|^{2}}_{\leq
L_{1}^{4}}$ $\displaystyle+\underbrace{\|\mathbb{E}_{x_{i}\sim
p}\nabla_{\theta}f(x_{i},\theta)\nabla_{\theta}f(x_{i},\theta)^{\top}\|^{2}}_{L_{1}^{4}}$
$\displaystyle\leq 2L_{1}^{4}.$

Since $X_{i}$ is symmetric, we know the same bound holds for
$X_{i}^{\top}X_{i}$ terms. This means that $\nu=2L_{1}^{4}$. Finally, using
Lemma D.4 and cleaning some terms, we get that

$\displaystyle\text{Pr}\Big{[}\|\frac{1}{n}\sum_{i=1}^{n}X_{i}\|\geq
t\Big{]}\leq
2M_{\Theta}\exp\bigg{\\{}-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+t)}\bigg{\\}}.$

Let us consider when

$\displaystyle
t=\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n)+\log(2M_{\Theta})}{n}}.$

Moreover, we can choose $n$ large enough such that

$\displaystyle\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n)+\log(2M_{\Theta})}{n}}<\frac{3}{2},$

then we have that

$\displaystyle\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+t)}$
$\displaystyle>\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+(3/2))}$
$\displaystyle-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+t)}$
$\displaystyle<-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+(3/2))}$
$\displaystyle\exp\bigg{\\{}-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+t)}\bigg{\\}}$
$\displaystyle<\exp\bigg{\\{}-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+(3/2))}\bigg{\\}}$
$\displaystyle\implies
2M_{\Theta}\exp\bigg{\\{}-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+t)}\bigg{\\}}$
$\displaystyle\leq
2M_{\Theta}\exp\bigg{\\{}-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+(3/2))}\bigg{\\}}.$

So with our choice of $t$, we actually get that

$\displaystyle
2M_{\Theta}\exp\bigg{\\{}-\frac{nt^{2}}{2L_{1}^{2}(2L_{1}^{2}+(3/2))}\bigg{\\}}$
$\displaystyle=2M_{\Theta}\exp\bigg{\\{}-\frac{(2L_{1}^{2}(2L_{1}^{2}+(3/2)))(A\log(n)+\log(2M_{\Theta}))}{2L_{1}^{2}(2L_{1}^{2}+(3/2))}\bigg{\\}}$
$\displaystyle=2M_{\Theta}\exp\bigg{\\{}-(A\log(n)+\log(2M_{\Theta}))\bigg{\\}}$
$\displaystyle=n^{-A}.$

Taking the compliment of this event, we get that with probability greater than
$1-n^{-A}$

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}X_{i}\|\leq\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n)+\log(2M_{\Theta})}{n}}.$

So we’re done. ∎

######  Proposition C.1.

Assume that $t\leq R^{2}$ (so that $\theta(t)\in B_{R}$) as well as 5.2 and
5.3, then with probability $\geq 1-n_{p}^{-A}-n_{q}^{-A}$, we have
$\|(\widehat{u}-\bar{u})(\cdot,t)\|_{L^{2}(p+q)}$ is less than or equal to

$\displaystyle 4L_{1}^{2}t$
$\displaystyle+4L_{1}L_{2}t^{3/2}\|f^{*}\|_{L^{2}(p+q)}\Big{(}1+2L_{1}^{3}t^{2}\sqrt{2(2L_{1}^{2}+3/2)\frac{A\log(n_{p})+\log(2M_{\Theta})}{n_{p}}}\Big{)}^{1/2}$
$\displaystyle+4L_{1}L_{2}t^{3/2}\|f^{*}\|_{L^{2}(p+q)}\Big{(}1+2L_{1}^{3}t^{2}\sqrt{2(2L_{1}^{2}+3/2)\frac{A\log(n_{q})+\log(2M_{\Theta})}{n_{q}}}\Big{)}^{1/2}$
$\displaystyle+t^{2}\cdot\sqrt{2}L_{1}^{3}\|f^{*}\|_{L^{2}(p+q)}\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n_{p})+\log(2M_{\Theta})}{n_{p}}}$
$\displaystyle+t^{2}\cdot\sqrt{2}L_{1}^{3}\|f^{*}\|_{L^{2}(p+q)}\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n_{q})+\log(2M_{\Theta})}{n_{p}}}.$

So that $\|(\widehat{u}-\bar{u})(\cdot,t)\|_{L^{2}(p+q)}$ is $O(t^{5/2})$.

###### Proof of Proposition C.1.

Inspecting $\partial_{t}(\widehat{u}-\bar{u})$ more closely, we see that

$\displaystyle 2\partial_{t}(\widehat{u}-\bar{u})(\cdot,t)$
$\displaystyle=-\mathbb{E}_{x^{\prime}\sim\widehat{p}}\widehat{K}_{t}(\cdot,x^{\prime})\widehat{e}_{p}(x^{\prime},t)-\mathbb{E}_{x^{\prime}\sim\widehat{q}}\widehat{K}_{t}(\cdot,x^{\prime})\widehat{e}_{q}(x^{\prime},t)$
$\displaystyle+\mathbb{E}_{x^{\prime}\sim
p}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t)+\mathbb{E}_{x^{\prime}\sim
q}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t).$

Notice that

$\displaystyle-\mathbb{E}_{x^{\prime}\sim\widehat{p}}\widehat{K}_{t}(\cdot,x^{\prime})\widehat{e}_{p}(x^{\prime},t)+\mathbb{E}_{x^{\prime}\sim
p}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t)$
$\displaystyle=-\bigg{\\{}\mathbb{E}_{x^{\prime}\sim\widehat{p}}\widehat{K}_{t}(\cdot,x^{\prime})(\widehat{e}_{p}(x^{\prime},t)-\bar{e}(x^{\prime},t))+\mathbb{E}_{x^{\prime}\sim\widehat{p}}(\widehat{K}_{t}-K_{0})(\cdot,x^{\prime})\bar{e}(x^{\prime},t)$
$\displaystyle+\Big{(}\mathbb{E}_{x^{\prime}\sim\widehat{p}}-\mathbb{E}_{x^{\prime}\sim
p}\Big{)}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t)\bigg{\\}}.$

For $q$, we get a similar form

$\displaystyle-\mathbb{E}_{x^{\prime}\sim\widehat{q}}\widehat{K}_{t}(\cdot,x^{\prime})\widehat{e}_{q}(x^{\prime},t)+\mathbb{E}_{x^{\prime}\sim
q}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t)$
$\displaystyle=-\bigg{\\{}\mathbb{E}_{x^{\prime}\sim\widehat{q}}\widehat{K}_{t}(\cdot,x^{\prime})(\widehat{e}_{q}(x^{\prime},t)-\bar{e}(x^{\prime},t))+\mathbb{E}_{x^{\prime}\sim\widehat{q}}(\widehat{K}_{t}-K_{0})(\cdot,x^{\prime})\bar{e}(x^{\prime},t)$
$\displaystyle+\Big{(}\mathbb{E}_{x^{\prime}\sim\widehat{q}}-\mathbb{E}_{x^{\prime}\sim
q}\Big{)}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t)\bigg{\\}}.$

Putting this together, we get

$\displaystyle
2\partial_{t}(\widehat{u}-\bar{u})(\cdot,t)=\underbrace{-\mathbb{E}_{x^{\prime}\sim\widehat{p}}\widehat{K}_{t}(\cdot,x^{\prime})(\widehat{e}_{p}(x^{\prime},t)-\bar{e}(x^{\prime},t))}_{I_{1,p}}$
$\displaystyle+\underbrace{\mathbb{E}_{x^{\prime}\sim\widehat{p}}(K_{0}-\widehat{K}_{t})(\cdot,x^{\prime})\bar{e}(x^{\prime},t)}_{I_{2,p}}+\underbrace{\Big{(}\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}}\Big{)}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t)}_{I_{3,p}}$
$\displaystyle\underbrace{-\mathbb{E}_{x^{\prime}\sim\widehat{q}}\widehat{K}_{t}(\cdot,x^{\prime})(\widehat{e}_{q}(x^{\prime},t)-\bar{e}(x^{\prime},t))}_{I_{1,q}}+\underbrace{\mathbb{E}_{x^{\prime}\sim\widehat{q}}(K_{0}-\widehat{K}_{t})(\cdot,x^{\prime})\bar{e}(x^{\prime},t)}_{I_{2,q}}$
$\displaystyle+\underbrace{\Big{(}\mathbb{E}_{x^{\prime}\sim
q}-\mathbb{E}_{x^{\prime}\sim\widehat{q}}\Big{)}K_{0}(\cdot,x^{\prime})\bar{e}(x^{\prime},t)}_{I_{3,q}}.$

Similar to the proof of Proposition 5.6, we will consider

$\displaystyle\frac{d}{dt}\|(\widehat{u}-\bar{u})(\cdot,t)\|_{L^{2}(p+q)}^{2}$
$\displaystyle=\langle(\widehat{u}-\bar{u})(\cdot,t),2\partial_{t}(\widehat{u}-\bar{u})(\cdot,t)\rangle_{L^{2}(p+q)}$
$\displaystyle=\langle(\widehat{u}-\bar{u})(\cdot,t),I_{1,p}+I_{1,q}\rangle_{L^{2}(p+q)}+\langle(\widehat{u}-\bar{u})(\cdot,t),I_{2,p}+I_{2,q}\rangle_{L^{2}(p+q)}$
$\displaystyle+\langle(\widehat{u}-\bar{u})(\cdot,t),I_{3,p}+I_{3,q}\rangle_{L^{2}(p+q)}$
$\displaystyle\leq\langle(\widehat{u}-\bar{u})(\cdot,t),I_{1,p}+I_{1,q}\rangle_{L^{2}(p+q)}$
$\displaystyle+\|(\widehat{u}-\bar{u})(\cdot,t)\|_{L^{2}(p+q)}\Big{(}\|I_{2,p}+I_{2,q}\|_{L^{2}(p+q)}+\|I_{3,p}+I_{3,q}\|_{L^{2}(p+q)}\Big{)}.$

So we’ll need to bound $I_{2,p},I_{2,q},I_{3,p}$, and $I_{3,q}$ and will deal
with the $I_{1,p}$ and $I_{1,q}$ terms at the end.

Before starting, let $A_{P}$ be the event that

$\displaystyle\|(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\nabla_{\theta}u(x^{\prime},\theta(0))^{\top}\|\leq\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n_{p})+\log(2M_{\Theta})}{n_{p}}}$

and let $A_{Q}$ be the event that

$\displaystyle\|(\mathbb{E}_{x^{\prime}\sim
q}-\mathbb{E}_{x^{\prime}\sim\widehat{q}})\nabla_{\theta}u(x^{\prime},\theta(0))\nabla_{\theta}u(x^{\prime},\theta(0))^{\top}\|\leq\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n_{q})+\log(2M_{\Theta})}{n_{q}}}.$

Note that from Lemma 5.10, we know that $A_{P}$ occurs with probability $\geq
1-n_{p}^{-A}$ and $A_{Q}$ occurs with probability $\geq 1-n_{q}^{-A}$. Since
these events are disjoint, notice that

$\displaystyle\text{Pr}\big{(}A_{P}\cap
A_{Q}\big{)}=1-\text{Pr}\big{(}A_{P}^{c}\cup
A_{Q}^{c}\big{)}=1-n_{p}^{-A}-n_{q}^{-A}$

where $A_{P}^{c}$ and $A_{Q}^{c}$ are the complements of $A_{P}$ and $A_{Q}$
respectively. We work in the regime that both $A_{P}$ and $A_{Q}$ occur.

Bounding $I_{3,p}$ and $I_{3,q}$: We will first work with just $I_{3,p}$ and
will notice that the method of bounding $I_{3,q}$ is the same. Then using the
triangle inequality, we will get our bounds. Notice that

$\displaystyle I_{3,p}$
$\displaystyle=\langle\nabla_{\theta}u(\cdot,\theta(0)),(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\bar{e}(x^{\prime},t)\rangle_{\Theta}$
$\displaystyle\implies\|I_{3,p}\|_{L^{2}(p+q)}$
$\displaystyle\leq\Big{\|}\underbrace{\|\nabla_{\theta}u(\cdot,\theta(0))\|_{\Theta}}_{\leq
L_{1}}\Big{\|}_{L^{2}(p+q)}\|(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\bar{e}(x^{\prime},t)\|_{\Theta}$
$\displaystyle\leq\sqrt{2}L_{1}\|\underbrace{(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\bar{e}(x^{\prime},t)}_{a_{3}}\|_{\Theta}.$

Now we can use the fact that

$\displaystyle\bar{e}(x,t)$ $\displaystyle=-\int_{0}^{t}\mathbb{E}_{y\sim
p+q}K_{0}(x,y)\bar{e}(y,s)ds$
$\displaystyle=-\int_{0}^{t}\langle\nabla_{\theta}u(x,\theta(0)),\mathbb{E}_{y\sim
p+q}\nabla_{\theta}u(y,\theta(0))\bar{e}(y,s)\rangle_{\Theta}ds.$

This means that we can rewrite $a_{3}$ as

$\displaystyle a_{3}=-\int_{0}^{t}\big{[}(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\nabla_{\theta}u(x^{\prime},\theta(0))^{\top}\big{]}\mathbb{E}_{y\sim
p+q}\nabla_{\theta}u(y,\theta(0))\bar{e}(y,s)ds.$

This would mean that $\|a_{3}\|_{\Theta}$ is bounded by

$\displaystyle\int_{0}^{t}\|(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\nabla_{\theta}u(x^{\prime},\theta(0))^{\top}\|\underbrace{\|\nabla_{\theta}u(y,\theta(0))\|_{\Theta}}_{\leq
L_{1}}\mathbb{E}_{y\sim p+q}\|\bar{e}(y,s)\|ds$ $\displaystyle\leq
tL_{1}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\|\|(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\nabla_{\theta}u(x^{\prime},\theta(0))^{\top}\|.$

Now recalling that $\bar{e}(\cdot,0)=\Pi_{K_{0}}(f^{*})$ and using Parseval’s
identity, the last inequality comes from the fact that

$\displaystyle\|\bar{e}(\cdot,t)\|_{L^{2}(p+q)}^{2}$
$\displaystyle=\sum_{\ell=1}^{M}\underbrace{e^{-2t\lambda_{\ell}}}_{\leq
1}|\langle u_{\ell},\bar{e}(\cdot,0)\rangle|^{2}\leq\sum_{\ell=1}^{M}|\langle
u_{\ell},\Pi_{K_{0}}(f^{*})\rangle|^{2}=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2}.$

So we only need to bound the operator norm of

$\displaystyle\|(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\nabla_{\theta}u(x^{\prime},\theta(0))^{\top}\|.$

To this end, since we assume that we are working under event $A_{P}\cap
A_{Q}$, we can again use Lemma 5.10 and get that with probability greater than
$1-{n_{p}}^{-A}-n_{q}^{-A}$,

$\displaystyle\|(\mathbb{E}_{x^{\prime}\sim
p}-\mathbb{E}_{x^{\prime}\sim\widehat{p}})\nabla_{\theta}u(x^{\prime},\theta(0))\nabla_{\theta}u(x^{\prime},\theta(0))^{\top}\|\leq\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n_{p})+\log(2M_{\Theta})}{n_{p}}}.$

Now putting all these bounds together, we get that

$\displaystyle\|I_{3,p}\|_{L^{2}(p+q)}\leq
t\cdot\sqrt{2}L_{1}^{3}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n_{p})+\log(2M_{\Theta})}{n_{p}}}.$

For ease later on, let us define

$\displaystyle
g_{3}(t,n)=t\cdot\sqrt{2}L_{1}^{3}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n)+\log(2M_{\Theta})}{n}}.$

Note that because we are working under event $A_{P}\cap A_{Q}$, we know that
with probability greater than $1-n_{p}^{-A}-{n_{q}}^{-A}$

$\displaystyle\|I_{3,q}\|_{L^{2}(p+q)}\leq
t\cdot\sqrt{2}L_{1}^{3}\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}\sqrt{2L_{1}^{2}(2L_{1}^{2}+3/2)\frac{A\log(n_{q})+\log(2M_{\Theta})}{n_{q}}}=g_{3}(t,n_{q}).$

Now let us bound $I_{2,p}$ and $I_{2,q}$.

Bounding $I_{2,p}$ and $I_{2,q}$: We will again bound for $I_{2,p}$ and
essentially use the same logic for bounding $I_{2,q}$. Note that

$\displaystyle\|I_{2,p}\|_{L^{2}(p+q)}^{2}$ $\displaystyle=\mathbb{E}_{x\sim
p+q}\Big{|}\mathbb{E}_{x^{\prime}\sim\widehat{p}}(\widehat{K}_{t}-K_{0})(x,x^{\prime})\bar{e}(x^{\prime},t)\Big{|}^{2}$
$\displaystyle\leq\mathbb{E}_{x\sim
p+q}\Big{(}\mathbb{E}_{x^{\prime}\sim\widehat{p}}|(\widehat{K}_{t}-K_{0})(x,x^{\prime})||\bar{e}(x^{\prime},t)|\Big{)}^{2}.$

Using Lemma 5.9, note that

$\displaystyle|\widehat{K}_{t}(x,x^{\prime})-K_{0}(x,x^{\prime})|$
$\displaystyle=|\langle\nabla_{\theta}u(x,\widehat{\theta}(t)),\nabla_{\theta}u(x^{\prime},\widehat{\theta}(t))\rangle-\langle\nabla_{\theta}u(x,\theta(0)),\nabla_{\theta}u(x^{\prime},\theta(0))\rangle|$
$\displaystyle\leq\|\nabla_{\theta}u(x,\widehat{\theta}(t))\|_{\Theta}\|\|\nabla_{\theta}u(x^{\prime},\widehat{\theta}(t))-\nabla_{\theta}u(x^{\prime},\theta(0))\|_{\Theta}$
$\displaystyle+\|\nabla_{\theta}u(x,\widehat{\theta}(t))-\nabla_{\theta}u(x,\theta(0))\|_{\Theta}\|\nabla_{\theta}u(x^{\prime},\theta(0))\|_{\Theta}$
$\displaystyle\leq 2L_{1}L_{2}\|\widehat{\theta}(t)-\theta(0)\|_{\Theta}\leq
2L_{1}L_{2}\sqrt{t}.$

Now the only thing left to bound is
$\mathbb{E}_{x^{\prime}\sim\widehat{p}}|\bar{e}(x^{\prime},t)|$. To do this,
recalling the time-integrated form of $\bar{e}$, we have that

$\displaystyle\mathbb{E}_{x\sim\widehat{p}}|\bar{e}(x,t)|=\|\bar{e}(\cdot,t)\|_{L^{1}(\widehat{p})}\leq\Big{(}\|\bar{e}(\cdot,t)\|_{L^{2}(\widehat{p})}^{2}\Big{)}^{1/2}.$

Now notice that

$\displaystyle\|\bar{e}(\cdot,t)\|_{L^{2}(\widehat{p})}^{2}=\mathbb{E}_{x\sim\widehat{p}}|\bar{e}(x,t)|^{2}=(\mathbb{E}_{x\sim\widehat{p}}-\mathbb{E}_{x\sim
p})|\bar{e}(x,t)|^{2}+\mathbb{E}_{x\sim p}|\bar{e}(x,t)|^{2}.$

Because integrating a positive function over both $p$ and $q$ is an upper
bound of just integrating over $p$, we know that

$\displaystyle\mathbb{E}_{x\sim
p}|\bar{e}(x,t)|^{2}=\|\bar{e}(\cdot,t)\|_{L^{2}(p)}^{2}\leq\|\bar{e}(\cdot,0)\|_{L^{2}(p+q)}^{2}=\|\Pi_{K_{0}}(f^{*})\|_{L^{2}(p+q)}^{2},$

so we only need to deal with the first term. In particular, using the time-
integrated form of $|\bar{e}(x,t)|^{2}$, we get that equals