Strong Approximations for Empirical Processes Indexed by Lipschitz Functions

Supplemental Appendix to “Strong Approximations for Empirical Processes Indexed by Lipschitz Functions”

}

\setcounter{page}{0}\thispagestyle{empty}

\thispagestyle{empty}

\onehalfspacing \setcounter{page}{1} \pagestyle{plain}

\singlespacing \setcounter{tocdepth}{3}

\onehalfspacing

Additional Notation

We introduce additional notation and definitions complementing those given in Section 2 of the paper. See Ambrosio-Fusco-Pallara_2000_book, wellner2013weak-SA, Gine-Nickl_2016_Book-SA, and references therein, for background definitions and more details.

Let $\mathcal{U}, \mathcal{V} \subseteq \mathbb{R}^q$. We define $\mathcal{U} - \mathcal{V} = \{\mathbf{u} - \mathbf{v}: \mathbf{u} \in \mathcal{U}, \mathbf{v} \in \mathcal{V}\}$. We define $\mathcal{U} \triangle \mathcal{V} = (\mathcal{U} \setminus \mathcal{V}) \cup (\mathcal{V} \setminus \mathcal{U})$. Let $\operatorname{det}(\mathbf{A})$ be the determinant of the matrix $\mathbf{A}$. Let $\Phi(z)$ be the distribution function of $\mathsf{Normal}(0,1)$, and $\mathsf{Bern}(p)$ denote the Bernoulli distribution with parameter $p\in(0,1)$. For a real-valued random variable $X$, the $L_p$-norm is defined as $\|X\|_p = \mathbbm{E}[|X|^p]^{1/p}$ for $1 \leq p < \infty$. The $\sigma$-algebra generated by $X$ is denoted by $\boldsymbol{\sigma}(X)$. For $\alpha > 0$, the $\psi_\alpha$-norm of $X$ is given by $\|X\|_{\psi_\alpha} = \min\big\{ \lambda > 0 : \mathbbm{E}\big[\exp\big(\big(\frac{|X|}{\lambda}\big)^\alpha\big)\big] \leq 2 \big\}$. For $\mathbf{x} \in \mathbb{R}^q$ and $r > 0$, let $B(\mathbf{x}, r)$ denote the Euclidean ball with radius $r$ centered at $\mathbf{x}$. For a matrix $\mathbf{A} \in \mathbb{R}^{q \times q}$, $\lVert \mathbf{A} \rVert$ denotes its operator norm. Using standard empirical process notation, $\mathbbm{E}_n[f(\mathbf{x}_i)]$ denotes the empirical average $n^{-1} \sum_{i = 1}^n[f(\mathbf{x}_i) - \mathbbm{E}[f(\mathbf{x}_i)]]$ based on random sample $(\mathbf{x}_i: 1 \leq i \leq n)$. For sequences of real numbers, we write $a_n = \Omega(b_n)$ if there exists some constant $C$ and $N > 0$ such that $n > N$ implies $|a_n| \geq C |b_n|$.

Let $\mathscr{S} \subseteq \mathbb{R}^q$ and $Q$ be a measure on $(\mathscr{S}, \mathcal{B}(\mathscr{S}))$. The semi-metric $\mathfrak{d}_Q$ on $L_2(Q)$ is defined by $\mathfrak{d}_Q(f, g) = \big(\|f - g\|_{Q,2}^2 - \big(\int f \, dQ - \int g \, dQ\big)^2\big)^{1/2}$, for $f, g \in L_2(Q)$. For a class $\mathscr{F} \subseteq L_2(Q)$, let $C(\mathscr{F}, \mathfrak{d}_Q)$ denote the class of all continuous functionals on the space $(\mathscr{F}, \mathfrak{d}_Q)$. For $\alpha > 0$, the $C^\alpha$-norm of a real-valued measurable function $f$ on $(\mathscr{S}, \mathcal{B}(\mathscr{S}))$ is given by $\|f\|_{C^\alpha} = \max_{|k| \leq \lfloor \alpha \rfloor} \sup_{\mathbf{x} \in \mathscr{S}} |D^k f(\mathbf{x})| + \max_{|k| = \alpha} \sup_{\mathbf{x} \neq \mathbf{y} \in \mathscr{S}} \frac{|D^k f(\mathbf{x}) - D^k f(\mathbf{y})|}{\|\mathbf{x} - \mathbf{y}\|_2^{\alpha - \lfloor \alpha \rfloor}}$. The space $C^\alpha(\mathscr{S})$ denotes the collection of all real-valued measurable functions on $(\mathscr{S}, \mathcal{B}(\mathscr{S}))$ with $C^\alpha$-norm bounded by 1. For real-valued functions $f,g$ on $(\mathbb{R}^d,\mathcal{B}(\mathbb{R}^d))$, the convolution of $f$ and $g$ is the function $f \ast g$ such that $f \ast g(x) = \int_{-\infty}^{\infty}f(y)g(x - y) d y, x \in \mathbb{R}$. If $\mathscr{F}$ and $\mathscr{G}$ are two sets of functions from measure space $(\mathcal{U},\mathcal{B}(\mathcal{U}))$ to $\mathbb{R}$ and $(\mathcal{V},\mathcal{B}(\mathcal{V}))$ to $\mathbb{R}$, respectively, then $\mathscr{F} \cdot \mathscr{G}$ denotes the class of measurable functions $\{f \cdot g: f \in \mathscr{F}, g \in \mathscr{G}\}$ from $(\mathcal{U} \times \mathcal{V}, \mathcal{B}(\mathcal{U}) \otimes \mathcal{B}(\mathcal{V}))$ to $\mathbb{R}$. For a semi-metric space $(\mathscr{F}, \mathfrak{d})$ of real-valued measurable functions on $(\mathscr{S}, \mathcal{B}(\mathscr{S}))$, $N_{[\,]}(\varepsilon, \mathscr{F}, \mathfrak{d})$ denotes the bracketing number.

For a probability measure $P$ on $(\mathscr{S}, \mathcal{B}(\mathscr{S}))$, a $P$-Brownian bridge is a centered Gaussian random function $(W_P(f): f \in L_2(P))$ with covariance given by $\mathbbm{E}[W_P(f) W_P(g)] = P(fg) - P(f)P(g)$ for $f, g \in L_2(P)$. A class $\mathscr{F} \subseteq L_2(P)$ is said to be $P$-pregaussian if there exists a version of the $P$-Brownian bridge $W_P$ such that $W_P \in C(\mathscr{F}; \mathfrak{d}_P)$ almost surely.

Finally, we use $a_n \lesssim b_n$ to denote that $a_n = O(b_n)$ with only a universal constant, not a function of the data generating process or related parameters. For $K \in \mathbb{N}$, we repeatedly employ the index sets $\mathcal{I}_K = \{(j,k) \in \mathbb{N} \times \mathbb{N}: 1 \leq j \leq K, 0 \leq k < 2^{K - j}\}$ and $\mathcal{J}_K = \{(j,k) \in \mathbb{N} \times \mathbb{N}: 0 \leq j \leq K, 0 \leq k < 2^{K - j}\}$.

Additional Main Definitions

Let $\mathscr{F}$ be a class of measurable functions from a probability space $(\mathbb{R}^q, \mathcal{B}(\mathbb{R}^q), \mathbbm{P})$ to $\mathbb{R}$. We introduce several additional definitions that capture properties of $\mathscr{F}$, complementing those in Section 2.1.

Suppose \(\mathscr{S}\) is also a class of measurable functions from the probability space \((\mathbb{R}^q, \mathcal{B}(\mathbb{R}^q), \mathbbm{P})\) to \(\mathbb{R}\). We generalize the definition of the uniform covering number to \(\mathscr{F} \times \mathscr{S}\).

General Empirical Process

Recall that $\mathbf{x}_i\in \mathcal{X} \subseteq \mathbb{R}^d$, $i=1,\dots,n$, are i.i.d. random vectors supported on a background probability space $(\Omega,\mathcal{F},\mathbbm{P})$, and the general empirical process is

where $\mathscr{H}$ is a possibly $n$-varying class of functions. As briefly explained after Theorem 1 is presented in the paper, its proof relies on the following decomposition:

where $\mathscr{H}_\delta$ denotes a discretization (or meshing) of $\mathscr{H}$ (i.e., $\delta$-net of $\mathscr{H}$), and the terms $\lVert X_n - X_n\circ\pi_{\mathscr{H}_\delta} \rVert_{\mathscr{H}}$ and $\lVert Z_n^X\circ\pi_{\mathscr{H}_\delta}-Z_n^X \rVert_{\mathscr{H}}$ capture the fluctuations (or oscillations) of $X_n$ and $Z_n^X$ relative to the meshing for each of the stochastic processes. These terms are handled using standard arguments for empirical processes. Then, following Rio_1994_PTRF-SA, the term $\lVert X_n - Z_n^X \rVert_{\mathscr{H}_\delta}$ is further decomposed into three terms: $\lVert \mathtt{\Pi}_{0} X_n - \mathtt{\Pi}_{0} Z_n^X \rVert_{\mathscr{H}_{\delta}}$ and $\lVert \mathtt{\Pi}_{0} Z_n^X - Z_n^X \rVert_{\mathscr{H}_\delta}$ represent a mean square projection onto a Haar function space, where $\mathtt{\Pi}_{0} X_n(h) = X_n \circ \mathtt{\Pi}_{0} h$ with $\mathtt{\Pi}_{0}$ the $L_2$ projection onto piecewise constant functions on a carefully chosen partition of $\mathcal{X}$, while the final term $\lVert \mathtt{\Pi}_{0} X_n - \mathtt{\Pi}_{0} Z_n^X \rVert_{\mathscr{H}_{\delta}}$ captures the coupling between the projected empirical process and the projected Gaussian process (on a $\delta$-net of $\mathscr{H}$, after the $L_2$ projection).

The proof of Theorem 1 first constructs the Gaussian process $(Z_n^X(h): h \in \mathscr{H})$ on a possibly enlarged probability space supporting the empirical process $(X_n(h): h \in \mathscr{H})$, and then bounds each of the five error terms described above. The proof is given in Section (ref), and it exploits the existence of a surrogate measure and normalizing transformation (Section (ref)), along with a collection preliminary technical results (Section (ref)) that may be of independent interest. More specifically, our preliminary technical results are organized as follows:

Section (ref) introduces a reduction argument via the surrogate measure and the normalizing transformation in order to apply the preliminary technical results from Section (ref) to prove Theorem 1. Specifically, the surrogate measure and normalizing transformation reduce the problem to the case where $\mathbf{x}_i \thicksim \mathsf{Uniform}([0,1]^d)$. Section (ref) gives the proof of Theorem 1. Section (ref) presents additional results of independent interest, which are used in Section (ref) to prove the results discussed in Section 3.2 of the paper. Finally, Section (ref) provides technical details underlying Example 1 in the paper.

Preliminary Technical Results

This section presents preliminary technical results that are used to prove Theorem 1. Whenever possible, these results are presented at a higher level of generality, and therefore may be of independent theoretical interest. Throughout this section, we employ the following assumption.

Compared to the assumptions in Theorem 1, this assumption does not require the existence of a surrogate measure and normalizing transformation. It will be applied in the analysis of each term in the error decomposition, where we work with the $\mathbbm{P}_X$ distribution. Section (ref) illustrates how the normalizing transformation enables the use of the surrogate measure $\mathbb{Q}_{\mathcal{H}}$, providing greater flexibility in the data generating process. This reduction through the normalizing transformation is a crucial step in the proof of Theorem 1 (Section (ref)).

Cells Expansions

We introduce two definitions of quasi-dyadic cells expansions. Recall that $\mathcal{I}_K = \{(j,k) \in \mathbb{N} \times \mathbb{N}: 1 \leq j \leq K, 0 \leq k < 2^{K - j}\}$ and $\mathcal{J}_K = \{(j,k) \in \mathbb{N} \times \mathbb{N}: 0 \leq j \leq K, 0 \leq k < 2^{K - j}\}$.

This definition implies $\frac{1}{2} \frac{2}{1 + \rho} \leq \mathbbm{P}(\mathcal{C}_{j-1,2k})/\mathbbm{P}(\mathcal{C}_{j,k}) \leq \frac{1}{2} \frac{2 \rho}{1 + \rho}$ for all $(j,k) \in \mathcal{I}_K$, since each $\mathcal{C}_{j-1,l}$ is a disjoint union of $2^{j-1}$ cells of the form $\mathcal{C}_{0,k}$, which implies the third condition in Definition (ref). Furthermore, $\mathbbm{P}(\mathcal{C}_{j-1,2k}) = \mathbbm{P}(\mathcal{C}_{j-1,2k+1}) = \frac{1}{2} \mathbbm{P}(\mathcal{C}_{j,k})$ in the special case $\rho = 1$, that is, the child level cells are obtained by splitting the parent level cells dyadically in probability.

The next definition specializes the dyadic expansion scheme to axis-aligned splits.

Projection onto Piecewise Constant Functions

For a quasi-dyadic expansion $\mathscr{C}_{K}(\mathbbm{P}, \rho)$, the span of the Haar basis based on the terminal cells is

For $h \in L_2(\mathbbm{P})$, the mean square projection of $h$ onto $\mathscr{E}_K$ is

Because $\mathtt{\Pi}_{0}(\mathscr{C}_{K}(\mathbbm{P},\rho))[h]$ is a linear combination of Haar functions, we obtain the following orthogonal decomposition.

To save notation, we will write $\mathtt{\Pi}_{0}$ for $\mathtt{\Pi}_{0}(\mathscr{C}_{K}(\mathbbm{P},\rho))$ whenever the underlying cells expansion is clear from the context. For a class of functions $\mathscr{H}$ on $(\mathbb{R}^d,\mathcal{B}(\mathbb{R}^d),\mathbbm{P})$ such that $\mathscr{H} \subseteq L_2(\mathbbm{P})$, denote $\mathtt{\Pi}_{0} \mathscr{H} = \{\mathtt{\Pi}_{0} h: h \in \mathscr{H}\}$.

Strong Approximation Constructions

This section employs the notations and conventions introduced in Sections (ref) and (ref). Unless explicitly stated otherwise, we assume a quasi-dyadic expansion $\mathscr{C}_{K}(\mathbbm{P}_X, \rho)$ is given. Let $(\widetilde{\xi}_{j,k}:(j,k) \in \mathcal{I}_K)$ be i.i.d. standard Gaussian random variables. Let $F_{(j,k),m}$ be the cumulative distribution function of $(S_{j,k} - m p_{j,k})/\sqrt{m p_{j,k}(1 - p_{j,k})}$, where $S_{j,k}$ is a $\mathsf{Bin}(m, p_{j,k})$ random variable with $p_{j,k} = \mathbbm{P}_X(\mathcal{C}_{j-1,2k})/\mathbbm{P}_X(\mathcal{C}_{j,k})$, and $G_{(j,k), m}(t) = \inf \{x: F_{(j,k),m}(x) \geq t\}$.

We define the collection of random variables $(U_{j,k}: (j,k) \in \mathcal{J}_K)$ and $(\widetilde{U}_{j,k}: (j,k) \in \mathcal{I}_K)$ via the following iterative scheme:

Then, $(U_{j,k}: (j,k) \in \mathcal{J}_K)$ has the same joint distribution as $(\sum_{i = 1}^n e_{j,k}(\mathbf{x}_i): (j,k) \in \mathcal{J}_K)$ from Lemma (ref). By the Vorob'ev–Berkes–Philipp theorem dudley2014uniform, $(\widetilde{\xi}_{j,k}: (j,k) \in \mathcal{I}_K)$ can be constructed on a possibly enlarged probability space such that the previously constructed $U_{j,k}$ satisfies $U_{j,k} = \sum_{i = 1}^n e_{j,k}(\mathbf{x}_i)$ almost surely for all $(j,k) \in \mathcal{J}_K$. We will show that the $\widetilde{\xi}_{j,k}$'s can be given as a Brownian bridge indexed by $\widetilde{e}_{j,k}$'s from Lemma (ref). Recall the definitions given in Section (ref).

Under the conditions of Lemma (ref), take $(Z_n^X(h): h \in \mathscr{H} \cup \mathtt{\Pi}_{0} \mathscr{H})$ to be a $\mathbbm{P}_X$-Brownian bridge such that $Z_n^X(\cdot) \in C(\mathscr{H} \cup \mathtt{\Pi}_{0} \mathscr{H},\mathfrak{d}_{\mathbbm{P}_X})$ almost surely. Since $(Z_n^X(\widetilde{e}_{j,k}):(j,k) \in \mathcal{I}_K)$ are independent random variables with distribution $\mathsf{Normal}(0,\mathbbm{P}_X(\mathcal{C}_{j-1,2k})\mathbbm{P}_X(\mathcal{C}_{j-1,2k+1})\mathbbm{P}_X(\mathcal{C}_{j,k})^{-1})$ for $(j,k) \in \mathcal{I}_K$, by Skorohod Embedding lemma dudley2014uniform, on a possibly enlarged probability space, the Brownian bridge $(Z_n^X(h): h \in \mathscr{H} \cup \mathtt{\Pi}_{0} \mathscr{H})$ can be constructed such that it satisfies

for all $(j,k) \in \mathcal{I}_K$. Moreover, for all $g \in \mathtt{\Pi}_{0} \mathscr{H}$,

where $\widetilde{V}_{j,k} = \sqrt{n}Z_n^X(\widetilde{e}_{j,k})$ for all $(j,k) \in \mathcal{I}_K$. The difference between $X_n(g)$ and $Z_n^X(g)$, for all $g \in \mathtt{\Pi}_{0} \mathscr{H}$, will rely on the coefficient $(\widetilde{\beta}_{j,k}(g):(j,k)\in \mathcal{I}_K, g \in \mathtt{\Pi}_{0} \mathscr{H})$ and the coupling between $\widetilde{U}_{j,k}$ and $\widetilde{V}_{j,k}$, which is the essence of Theorem 2.1 in Rio_1994_PTRF-SA. Although Rio_1994_PTRF-SA is stated for i.i.d. $\mathsf{Uniform}([0,1])$ random variables, the underlying process only depends through the counts of the random variables taking values in each interval of the form $[k2^{-j}, (k+1)2^{-j})$ for $(j,k) \in \mathcal{J}_K$, which have the same distribution as the counts $(\sum_{i=1}^n \mathbbm{1}(\mathbf{x}_i\in\mathcal{C}_{j,k}):(j,k) \in \mathcal{J}_K)$. Therefore, we have the following corollary of Rio_1994_PTRF-SA under Assumption (ref). Recall the definitions given in Section (ref).

Lemma (ref) relies on a coupling of $\mathsf{Bin}(m,1/2)$ random variables with Gaussian random variables. A weaker coupling also holds for $\mathsf{Bin}(m,p)$ with the error term only depending on how far away $p$ is bounded away from $0$ and $1$, as the following lemma establishes.

This generalization of Tusn\'ady's Lemma enables the following strong approximation for the case of a quasi-dyadic cells expansion.

Meshing Error

For $0 < \delta \leq 1$, consider the $(\delta \mathtt{M}_{\mathscr{H},\mathcal{X}})$-net of $(\mathscr{H}, \lVert \cdot \rVert_{\mathbbm{P}_X,2})$ over $\mathcal{X}$, $\mathscr{H}_\delta$, with cardinality no larger than $\mathtt{N}_{\mathscr{H},\mathcal{X}}(\delta,\mathtt{M}_{\mathscr{H},\mathcal{X}})$. Define $\pi_{\mathscr{H}_{\delta}}: \mathscr{H} \mapsto \mathscr{H}$ such that $\lVert \pi_{\mathscr{H}_{\delta}}(h) - h \rVert_{\mathbbm{P}_X,2} \leq \delta \mathtt{M}_{\mathscr{H},\mathcal{X}}$ for all $h \in \mathscr{H}$. To simplify notation, in this section the parameters of $\mathscr{H}$ (Definitions 4 to 12) are taken with $\mathcal{C} = \mathcal{X}$, and the index $\mathcal{C}$ is omitted whenever there is no confusion.

Strong Approximation Errors

To simplify notation, in this section the parameters of $\mathscr{H}$ (Definitions 4 to 12) are taken with $\mathcal{C} = \mathcal{X}$, and the index $\mathcal{C}$ is omitted whenever there is no confusion. The next lemma controls the strong approximation error for projected processes.

Projection Error

To simplify notation, in this section the parameters of $\mathscr{H}$ (Definitions 4 to 12) are taken with $\mathcal{C} = \mathcal{X}$, and the index $\mathcal{C}$ is omitted whenever there is no confusion. The following lemma controls the mean square projection onto piecewise constant functions.

In particular, if $\mathbbm{P}_X=\mathsf{Uniform}([0,1]^d)$ and $\mathscr{C}_{K}(\mathbbm{P}_X, 1)=\mathscr{A}_{K}(\mathbbm{P}_X, 1)$, then for all $t > 0$,

Surrogate Measure and Normalizing Transformation

This section studies the properties of the surrogate measure $\mathbb{Q}_\mathscr{H}$ and normalizing transformation $\phi_\mathscr{H}$ introduced in condition (ii) of Theorem 1. The following lemma characterizes the connections between the original and the transformed parameters of $\mathscr{H}$ (Definitions 4 to 12) when deploying $\mathbb{Q}_\mathscr{H}$ and $\phi_\mathscr{H}$.

General Result: Proof of Theorem 1

First, we make a reduction through the surrogate measure and normalizing transformation. We want to show that under assumption (ii) in Theorem 1, the empirical process $(X_n(h): h \in \mathscr{H})$ can be written as an empirical process based on i.i.d $\mathsf{Uniform}([0,1]^d)$ random variables. Let $\mathcal{Z}_{\mathscr{H}} = \mathcal{X} \cap \operatorname{Supp}(\mathscr{H})$. Since $\mathbb{Q}_\mathscr{H} = \operatorname*{\mathfrak{m}} \circ \phi_\mathscr{H}$ by Assumption (ii) in Theorem 1, and $\mathbb{Q}_\mathscr{H}|_{\mathcal{Z}_\mathscr{H}} = \mathbbm{P}_X|_{\mathcal{Z}_\mathscr{H}}$,

To define the $\mathsf{Uniform}([0,1]^d)$ random variables on the probability space that $\mathbf{x}_i$'s live in, we define a joint probability measure $\mathbb{O}$ on $(\mathbb{R}^d \times \mathbb{R}^d, \mathcal{B}(\mathbb{R}^{2d}))$ such that for all $A \in \mathcal{B}(\mathbb{R}^{2d})$:

where $\Pi_{1:d}(A) = \{\mathbf{x} \in \mathbb{R}^d: (\mathbf{x},\mathbf{u}) \in A \text{ for some } \mathbf{u} \in \mathbb{R}^{d}\}$, $\Pi_{d+1:2d}(A) = \{\mathbf{u} \in \mathbb{R}^d: (\mathbf{x},\mathbf{u}) \in A \text{ for some } \mathbf{x} \in \mathbb{R}^{d}\}$, and $A^{\mathbf{u}} = \{\mathbf{x} \in \mathbb{R}^d: (\mathbf{x},\mathbf{u}) \in A\}$. See Figure (ref) for a graphical illustration.

Then we can check that (i) the marginals of $\mathbb{O}$ are $\mathbbm{P}_X$ and $\mathfrak{m} \circ \phi_{\mathscr{H}}$, respectively; (ii) $\mathbb{O}|_{\mathcal{Z}_{\mathscr{H}} \times \mathbb{R}^d \cup \mathbb{R}^d \times \mathcal{Z}_{\mathscr{H}}}$ is supported on $\{(\mathbf{x},\mathbf{x}): \mathbf{x} \in \mathcal{Z}_{\mathscr{H}}\}$. By Skorohod embedding dudley2014uniform, on a possibly enlarged probability space, there exists a $\mathbf{u}_i, 1 \leq i \leq n$ i.i.d. $\operatorname{Uniform}([0,1]^d)$ such that $(\mathbf{x}_i,\phi_\mathscr{H}^{-1}(\mathbf{u}_i))$ has joint law $\mathbb{O}$. In particular, if $\mathbf{x}_i \in \mathcal{Z}_{\mathscr{H}}$, then $\mathbf{x}_i = \phi_{\mathscr{H}}^{-1}(\mathbf{u}_i)$; if $\mathbf{x}_i \in \mathcal{Z}_{\mathscr{H}}^c$, then $\phi_{\mathscr{H}}^{-1}(\mathbf{u}_i) \in \mathcal{Z}_{\mathscr{H}}^c$, and since $\mathcal{Q}_\mathscr{H} \subseteq \mathcal{X} \cup (\cap_{h \in \mathscr{H}} \operatorname{Supp}(h)^c)$, $\phi_{\mathscr{H}}^{-1}(\mathbf{u}_i) \in \cap_{h \in \mathscr{H}} \operatorname{Supp}(h)^c$.

Thus, we take $\widetilde{h} = h \circ \phi_{\mathscr{H}}^{-1}$, and consider the new class of functions $\widetilde{\mathscr{H}} = \{\widetilde{h}: h \in \mathscr{H}\}$. For any $h \in \mathscr{H}$,

where the second equality follows because $\mathbf{x}_i=\phi_{\mathscr{H}}^{-1}(\mathbf{u}_i)$ on the event $\{\mathbf{x}_i \in \mathcal{Z}_{\mathscr{H}}\}$, and $h(\mathbf{x}_i) = h(\phi_{\mathscr{H}}^{-1}(\mathbf{u}_i)) = 0$ (a.s.) on the event $\{\mathbf{x}_i \in \mathcal{Z}_{\mathscr{H}}^c\}$. Hence, we work with an equivalent empirical process

In particular, $\mathbf{u}_i$ has the uniform distribution $\mathbbm{P}_U$ which has a Lebesgue density $f_U$ that is bounded from above and below on its support $[0,1]^d$,

and Assumption (ref) is satisfied with the random sample $(\mathbf{u}_i: 1 \leq i \leq n)$ with $\mathbf{u}_i\thicksim\mathbbm{P}_U$ and the class of functions $\widetilde{\mathscr{H}}$. We thus consider $\mathscr{A}_{K}(\mathbbm{P}_U,1)$, an axis aligned dyadic expansion of depth $K$ with respect to probability measure $\mathbbm{P}_U = \mathsf{Uniform}([0,1]^d)$. Suppose $\mathscr{E}_K$ ($\mathtt{M}_{\mathscr{H},\mathcal{Q}_{\mathscr{H}}} = \mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d}$) and $\mathtt{\Pi}_{0} = \mathtt{\Pi}_{0}[\mathscr{A}_{K}(\mathbbm{P}_U,1)]$ are defined based on $\mathscr{A}_K(\mathbbm{P}_U,1)$ as in Section (ref). By Lemma (ref) and Lemma (ref), $\widetilde{\mathscr{H}} \cup \mathtt{\Pi}_{0} \widetilde{\mathscr{H}} $ is $\mathbbm{P}_U$-pregaussian, hence by the same construction given in Section (ref), on a possibly enlarged probability space, there exists a mean-zero Gaussian process $\widetilde{Z}_n^X$ indexed by $\widetilde{\mathscr{H}} \cup \mathtt{\Pi}_{0} \widetilde{\mathscr{H}}$ such that with almost sure continuous sample path such that

and $U_{j,k} = \sum_{i = 1}^n e_{j,k}(\mathbf{u}_i)$ for all $(j,k) \in \mathcal{J}_K$. Let $\widetilde{\mathscr{H}}_{\delta}$ be a $\delta \mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d} = \delta \mathtt{M}_{\mathscr{H},\mathcal{Q}_{\mathscr{H}}}$-net of $\widetilde{\mathscr{H}}$ with cardinality no greater than $\mathtt{N}_{\widetilde{\mathscr{H}},[0,1]^d}(\delta,\mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d})$.

The proof proceeds by bounding each of the terms in the decomposition

and then balancing their contributions.

Given the cells $\mathscr{A}_{K}(\mathbbm{P}_U,1)$, we have $\mathcal{U}_j \subseteq [-2^{-\frac{K - j}{d}+1}, 2^{-\frac{K - j}{d}+1}]^d$. Then, by Lemma (ref), for all $t > 0$,

where

Now we calculate the $\mathtt{C}_{\widetilde{\mathscr{H}}_{\delta},K}$ term. Let $\widetilde{h} \in \widetilde{\mathscr{H}}$ and take $(\widetilde{h}_\ell)_{\ell \in \mathbb{N}}$ be any sequence of real-valued functions on $([0,1]^d,\mathcal{B}([0,1]^d))$ such that $\widetilde{h}_{\ell} \rightarrow \widetilde{h}$ $\mathfrak{m}$-almost surely, and are bounded by $2 \mathtt{M}_{\mathscr{H}}$ on $\mathcal{X}$. Moreover, by Dominated Convergence Theorem, the definition of $\mathtt{K}_{\widetilde{\mathscr{H}},[0,1]^d}^*$ and similar arguments as in the proof of Lemma (ref), for each $(j,k) \in \mathcal{I}_K$,

Since the above inequality holds for all sequences $(h_{\ell})_{\ell \in \mathbb{N}}$ such that $\widetilde{h}_{\ell} \rightarrow \widetilde{h}$ $\mathfrak{m}$-almost surely, and are bounded by $2 \mathtt{M}_{\mathscr{H}}$ on $[0,1]^d$, Definitions (ref) and (ref) implies

It follows from the definition of $\mathtt{C}_{\widetilde{\mathscr{H}},K}$ in Lemma (ref) that

For projection error, by Lemma (ref), for all $t > 0$, with probability at least $1 - 2 \mathtt{N}_{\widetilde{\mathscr{H}},[0,1]^d}(\delta,\mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d}) e^{-t}$,

We balance the previous two errors by choosing $K = \lfloor d^{-1} \log_2 n\rfloor$ and get for all $t >0$, with probability at least $1 - 2 \exp(-t)$,

where

By Lemma (ref) we bound the meshing error by, for all $t > 0$,

where \[\mathsf{F}_n(t,\delta) = J(\delta, \widetilde{\mathscr{H}}, \mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d}) \mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d} + \frac{\mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d} J^2(\delta, \widetilde{\mathscr{H}}, \mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d})}{\delta^2 \sqrt{n}} + \delta \mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d} \sqrt{t} + \frac{\mathtt{M}_{\widetilde{\mathscr{H}},[0,1]^d}}{\sqrt{n}} t.\] Take the Gaussian process $(Z_n(h): h \in \mathscr{H})$ such that, almost surely, $Z_n(h) = \widetilde{Z}_n(\widetilde{h})$ for all $h \in \mathscr{H}$. The result then follows from the decomposition that

and Lemma (ref) to establish the relationships between the parameters of $\mathscr{H}$ over $\mathcal{Q}_{\mathscr{H}}$ and those of $\widetilde{\mathscr{H}}$ over $[0,1]^d$. \qed

Additional Results

In what follows, we drop the dependence on $\mathcal{C} = \mathcal{Q}_{\mathscr{F}}$ for all quantities in Definitions 4-12. That is, to save notation, we set $\mathtt{TV}_{\mathscr{F}}=\mathtt{TV}_{\mathscr{F},\mathcal{Q}_{\mathscr{F}}}$, $\mathtt{K}_{\mathscr{F}}=\mathtt{K}_{\mathscr{F},\mathcal{Q}_{\mathscr{F}}}$, $\mathtt{M}_{\mathscr{F},\mathcal{X}}=\mathtt{M}_{\mathscr{F},\mathcal{Q}_{\mathscr{F}}}$, $M_{\mathscr{F},\mathcal{X}}(\mathbf{u})=M_{\mathscr{F},\mathcal{Q}_{\mathscr{F}}}(\mathbf{u})$, $\mathtt{L}_{\mathscr{F}}=\mathtt{L}_{\mathscr{F},\mathcal{Q}_{\mathscr{F}}}$, and so on, whenever there is no confusion.

Proofs of Corollaries 1, 2, and 3

Example 1: Kernel Density Estimation

To simplify notation, in this section the parameters of $\mathscr{H}$ (Definitions 4 to 12) are taken with $\mathcal{C} = \mathcal{Q}_\mathscr{H}$, and the index $\mathcal{C}$ is omitted whenever there is no confusion.

Surrogate Measure and Normalizing Transformation

We show that the two sets of primitive conditions discussed in the paper imply condition (ii) in Theorem 1.

First, consider the case $\mathcal{X} = \times_{l = 1}^d[\mathsf{a}_l, \mathsf{b}_l]$, $- \infty \leq \mathsf{a}_l < \mathsf{b}_l \leq \infty$ and $\mathcal{W}$ is arbitrary. Observe that $\mathbb{Q}_{\mathscr{H}} = \mathbbm{P}_X$ is always a valid surrogate measure for $\mathbbm{P}_X$ with respect to $\mathscr{H}$, according to Definition 2. The conclusion then follows from Case 1 from Section 3.1 with $f_Q = f_X$.

Second, consider the case when $\mathcal{X}$ may be unbounded. We present a general construction, and then specialize it to the example discussed in the paper. Suppose we can find $\mathcal{Q}_\mathscr{H}$ diffeomorphic to $[0,1]^d$ such that $\mathcal{X} \cap \operatorname{Supp}(\mathscr{H}) \subseteq \mathcal{Q}_\mathscr{H} \subseteq \mathcal{X} \cup \operatorname{Supp}(\mathscr{H})^c$, with $\mathbbm{P}_X(\mathcal{X} \cap \operatorname{Supp}(\mathscr{H})) < 1$ and $\operatorname*{\mathfrak{m}}(\mathcal{Q}_\mathscr{H} \setminus (\mathcal{X} \cap \operatorname{Supp}(\mathscr{H}))) > 0$. Setting $\mathbb{Q}_\mathscr{H}$ to be the probability measure with Lebesgue density $f_Q$ such that

then $\mathbb{Q}_\mathscr{H}$ is a surrogate measure of $\mathbbm{P}_X$ with respect to $\mathscr{H}$. Suppose $\chi$ is a diffeomorphism from $\mathcal{Q}_\mathscr{H}$ to $[0,1]^d$. Since we assumed $\mathcal{X} \cap \operatorname{Supp}(\mathscr{H}) \subseteq \mathcal{Q}_\mathscr{H} \subseteq \mathcal{X} \cup \operatorname{Supp}(\mathscr{H})^c$, with $\mathbbm{P}_X(\mathcal{X} \cap \operatorname{Supp}(\mathscr{H})) < 1$ and $\operatorname*{\mathfrak{m}}(\mathcal{Q}_\mathscr{H} \setminus (\mathcal{X} \cap \operatorname{Supp}(\mathscr{H}))) > 0$, we can check that (1) $f_Q$ is supported and positive on $\mathcal{Q}_\mathscr{H}$, (2) $f_Q$ agrees with $f_X$ on $\mathcal{X} \cap \operatorname{Supp}(\mathscr{H})$. Then Case 2 in Section 3.1 implies $\phi_{\mathscr{H}} = T_{\mathbb{Q}_\mathscr{H} \circ \chi^{-1}} \circ \chi$ is a valid normalizing transformation, and condition (ii) in Theorem 1 holds. Suppose $0 < \inf_{\mathbf{x} \in \mathcal{X} \cap \operatorname{Supp}(\mathscr{H})} f_X(\mathbf{x})< \sup_{\mathbf{x} \in \mathcal{X} \cap \operatorname{Supp}(\mathscr{H})} f_X(\mathbf{x})< \infty$ and $\frac{\sup_{\mathbf{x} \in [0,1]^d} |\operatorname{det}(\nabla\chi^{-1}(\mathbf{x}))|}{\inf_{\mathbf{x} \in [0,1]^d} |\operatorname{det}(\nabla\chi^{-1}(\mathbf{x}))|}\lVert \lVert \nabla \chi^{-1} \rVert_2 \rVert_{\infty} < \infty$, then we have $\mathtt{c}_1 = O(1)$ and $\mathtt{c}_2 = O(1)$ (and hence $\mathtt{c}_3 = O(1)$).

For a concrete example, consider the case $\mathcal{X} = \mathbb{R}^d_+$, $\mathcal{W} = \times_{l = 1}^d [\mathsf{a}_l,\mathsf{b}_l]$, $0 \leq \mathsf{a}_l < \mathsf{b}_l < \infty$, and $\mathcal{K} = [-1,1]^d$. Observe that $\operatorname{Supp}(\mathscr{H}) \cap \mathcal{X} = \times_{l = 1}^d [(\mathsf{a}_l - b)_+, \mathsf{b}_l + b] = \times_{l=1}^d [\overline{\mathsf{a}}_l, \overline{\mathsf{b}}_l]$. Since $\mathcal{X} = \mathbb{R}^d_+$, $\mathbbm{P}_X(\times_{l=1}^d [\overline{\mathsf{a}}_l, \overline{\mathsf{b}}_l]) < 1$. Moreover, we can check that $\mathcal{X} \cap \operatorname{Supp}(\mathscr{H}) \subseteq \mathcal{Q}_\mathscr{H} \subseteq \mathcal{X} \cup \operatorname{Supp}(\mathscr{H})^c$ and $\mathbb{Q}_{\mathscr{H}}$ agrees with $\mathbbm{P}_X$ on $\mathcal{X} \cap \operatorname{Supp}(\mathscr{H})$. The rest then follows from the general construction above.

Class \texorpdfstring{$\mathscr{H}$}{H} and Its Corresponding Constants

Let $\mathscr{H} = \{h_{\mathbf{w}}: \mathbf{w} \in \mathcal{W} \}$ with $h_{\mathbf{w}}(\cdot) = b^{-d/2}K(b^{-1}(\mathbf{w} - \cdot))$. Since $K$ is compactly supported and Lipschitz, $\mathtt{M}_{\{K\}} < \infty$. Hence, $\mathtt{M}_{\mathscr{H}} = b^{-d/2} \mathtt{M}_{\{K\}} \leq C_K b^{-d/2}$ and $\mathtt{L}_{\mathscr{H}} \leq b^{-\frac{d}{2}-1}\mathtt{L}_{\{K\}} \leq C_K b^{-d/2-1}$, where $C_K$ is a constant that only depends on the kernel function $K$. Since $\sup_{\mathbf{w} \in \mathcal{W}} \operatorname*{\mathfrak{m}}(\operatorname{Supp}(h_{\mathbf{w}})) \leq C_K b^d$ and each $h_{\mathbf{w}}$ is differentiable,

To upper bound $\mathtt{K}_{\mathscr{H}}$, let $\mathcal{D} \subseteq \mathcal{Q}_\mathscr{H}$ be a cube with edges of length $\mathtt{a}$ parallel to the coordinate axises. Consider the following two cases: (i) if $\mathtt{a} < b$, then $\mathtt{TV}_{\mathscr{H},\mathcal{D}} \leq C_K b^{-d/2-1}\mathtt{a}^d \leq C_K b^{-d/2} \mathtt{a}^{d-1}$; (ii) if $\mathtt{a} > b$, then $\mathtt{TV}_{\mathscr{H},\mathcal{D}} \leq C_K \sup_{\mathbf{w} \in \mathcal{W}} \operatorname*{\mathfrak{m}}(\operatorname{Supp}(h_{\mathbf{w}})) \mathtt{L}_{\mathscr{H}} \leq C_K b^{d} b^{-d/2-1} \leq C_K b^{-d/2} b^{d-1} \leq C_K b^{-d/2} \mathtt{a}^{d-1}$. This shows $$\mathtt{K}_{\mathscr{H}} \leq C_K b^{-d/2}.$$ Next, by a change of variables,

Finally, we check that $\mathscr{H}$ is a VC-type class. We will apply Lemma 7 from Cattaneo-Chandak-Jansson-Ma_2024_Bernoulli-SA on the class $\mathtt{M}_{\mathscr{H}}^{-1} \mathscr{H}$. To check the conditions in this lemma, define $g_{\mathbf{w}}(\cdot) = b^{-\frac{d}{2}}\mathtt{M}_{\mathscr{H}}^{-1}K(\cdot)$ for all $\mathbf{w} \in \mathcal{W}$. Note that $g_{\mathbf{w}}$ is the same function for all $\mathbf{w} \in \mathcal{W}$ in this setting (but, more generally, our results allow for functions varying with the evaluation point such as in the case of boundary adaptive kernels). Then $\mathtt{M}_{\mathscr{H}}^{-1}\mathscr{H} = \{g_{\mathbf{w}}(\frac{\mathbf{w} - \cdot}{b}): \mathbf{w} \in \mathcal{W}\}$, and there exists a constant $c_K$, only depending on $\mathtt{M}_{\{K\}}$ and $\mathtt{L}_{\{K\}}$, such that

We can apply Lemma 7 from Cattaneo-Chandak-Jansson-Ma_2024_Bernoulli-SA, which is modified upon Lemma 4.1 from Rio_1994_PTRF-SA, to show that for all $0 < \varepsilon < 1$, $\mathtt{N}_{\mathtt{M}_{\mathscr{H}}^{-1} \mathscr{H}}(\varepsilon, 1) \leq c_K \varepsilon^{-d-1} + 1,$ and hence

The conclusions on uniform Gaussian strong approximation rates then follow from Corollaries 1--3.

Multiplicative-Separable Empirical Process

Let $\mathbf{z}_i=(\mathbf{x}_i, y_i)\in \mathcal{X}\times\mathcal{Y} \subseteq \mathbb{R}^d\times\mathbb{R}$, $i=1,\dots,n$, be i.i.d. random vectors supported on a background probability space $(\Omega,\mathcal{F},\mathbbm{P})$. The multiplicative-separable empirical process is

where $\mathscr{G}$ and $\mathscr{R}$ are possibly $n$-varying classes of functions. Notably, if we take $\mathscr{H} = \mathscr{G} \cdot \mathscr{R} = \{g \cdot r: g \in \mathscr{G}, r \in \mathscr{R}\}$, then the above process can also be written as a generic empirical process based on $(\mathbf{z}_i: 1 \leq i \leq n)$ because

Hence, the same decomposition for the $X_n$ process also applies for the $G_n$ process:

where $(\mathscr{G} \times \mathscr{R})_\delta$ denotes a discretization (or meshing) of $\mathscr{G} \times \mathscr{R}$ (i.e., $\delta$-net of $\mathscr{G} \times \mathscr{R}$), and the terms $\lVert G_n - G_n\circ\pi_{(\mathscr{G} \times \mathscr{R})_\delta} \rVert_{\mathscr{G} \times \mathscr{R}}$ and $\lVert Z_n^G\circ\pi_{(\mathscr{G} \times \mathscr{R})_\delta}-Z_n^G \rVert_{\mathscr{G} \times \mathscr{R}}$ capture the fluctuations (or oscillations) of $G_n$ and $Z_n^G$ relative to the meshing for each of the stochastic processes. $\lVert \mathtt{\Pi}_{1} G_n - \mathtt{\Pi}_{1} Z_n^G \rVert_{(\mathscr{G} \times \mathscr{R})_\delta}$ and $\lVert \mathtt{\Pi}_{1} Z_n^G - Z_n^G \rVert_{(\mathscr{G} \times \mathscr{R})_\delta}$ represent projections onto a Haar function space, where $\mathtt{\Pi}_{1} G_n(h) = G_n \circ \mathtt{\Pi}_{1} h$. The operator $\mathtt{\Pi}_{1}$ is a projection onto piecewise constant functions that respects the multiplicative structure of the $G_n$ process. The final term $\lVert \mathtt{\Pi}_{1} G_n - \mathtt{\Pi}_{1} Z_n^G \rVert_{(\mathscr{G} \times \mathscr{R})_\delta}$ captures the coupling between the empirical process and the Gaussian process (on a $\delta$-net of $\mathscr{G} \times \mathscr{R}$, after the projection $\mathtt{\Pi}_{1}$).

A general result under uniform entropy integral conditions is presented in Section (ref), and a corollary under a VC-type condition is presented in Section (ref). The proofs exploit the existence of a surrogate measure and normalizing transformation of $\mathscr{G}$ with respect to $\mathbb{P}_X$, the law of $\mathbf{x}_1$, as developed in Section (ref). The preliminary technical results differ from those in Section (ref) by explicitly leveraging the multiplicative structure of the empirical process, and are organized as follows.

Preliminary Technical Results

This section presents preliminary technical results that are used to prove Theorem (ref). Whenever possible, these results are presented at a higher level of generality, and therefore may be of independent theoretical interest. Throughout this section, we employ the following assumption.

Compared to the assumptions in Theorem 2, this assumption does not require the existence of a surrogate measure or a normalizing transformation. It will be applied in the analysis of terms in the error decomposition, where we work with the distribution $\mathbbm{P}_Z$, and an extra condition on the existence of Lebesgue density of $\mathbbm{P}_X$ is assumed whenever necessary (Section (ref)). The surrogate measure and the normalizing transformation will be used in the proof of Theorem (ref) with the help of Section (ref), providing greater flexibility in the data generating process.

Cells Expansions

Projection onto Piecewise Constant Functions

Consider a cylindered quasi-dyadic expansion $\mathcal{C}_{M,N}(\mathbbm{P}, \rho)$ where $\mathbbm{P}$ is the joint distribution of a random vector $(\mathbf{X}, Y)$ taking values in $(\mathbb{R}^d \times \mathbb{R}, \mathcal{B}(\mathbb{R}^d) \otimes \mathcal{B}(\mathbb{R}))$. Define the span of the Haar basis over the terminal cells as described in Section (ref), specifically

For $h \in L_2(\mathbbm{P})$, recall that the mean square projection of $h$ onto $\mathscr{E}_{M+N}$ is given by

and the $\beta$-coefficients are defined by

Then we still have

where

for all $(j,k) \in \mathcal{I}_{M+N} = \{(j,k) \in \mathbb{N} \times \mathbb{N}: 1 \leq j \leq M+N, 0 \leq k < 2^{M + N - j}\}$. We refer to $\mathtt{\Pi}_{0}(\mathcal{C}_{M,N}(\mathbbm{P}, \rho))$ as $\mathtt{\Pi}_{0}$ for simplicity.

To address the separable structure of $g(\mathbf{X}) r(Y)$, we define the product-factorized projection from $L_2(\mathbbm{P})$ to $\mathscr{E}_{M+N} = \operatorname{Span}\{\mathcal{C}_{0,k} = \mathcal{X}_{0,l} \times \mathcal{Y}_{l,0,m} : 0 \leq l < 2^M, 0 \leq m < 2^N, k = 2^N l + m\}$, defined as

and

and $\widetilde{\gamma}_{j,k}(g, r) = \gamma_{j-1,2k}(g, r) - \gamma_{j-1,2k+1}(g, r)$. We refer to $\mathtt{\Pi}_1(\mathcal{C}_{M,N}(\mathbbm{P}, \rho))$ as $\mathtt{\Pi}_{1}$ for simplicity.

The Haar basis representation in Equation (ref) decomposes the function into layers of increasingly localized fluctuations. However, at lower layers ($1 \leq j \leq N$), the local fluctuation is characterized by the product-factorized projection $\mathbbm{E}[g(\mathbf{X}) | \mathbf{X} \in \mathcal{X}_{0,l}] \cdot \mathbbm{E}[r(Y) | \mathbf{X} \in \mathcal{X}_{0,l}, Y \in \mathcal{Y}_{l,0,m}]$, rather than $\mathbbm{E}[g(\mathbf{X}) r(Y) | \mathbf{X} \in \mathcal{X}_{0,l} \times \mathcal{Y}_{l,0,m}]$. This distinction makes $\mathtt{\Pi}_1(\mathcal{C}_{M,N}(\mathbbm{P},\rho))[g, r]$ generally different from $\mathtt{\Pi}_{0}(\mathcal{C}_{M,N}(\mathbbm{P},\rho))[g \cdot r]$.

Now, we define the empirical processes indexed by projected functions. For any real valued functions $g$ on $\mathbb{R}^d$ and $r$ on $\mathbb{R}$ such that $\int_{\mathbb{R}^d} \int_{\mathbb{R}} g(\mathbf{x})^2 \mathbbm{P}(d y d \mathbf{x}) < \infty$ and $\int_{\mathbb{R}^d}\int_{\mathbb{R}}r(y)^2\mathbbm{P}(d y d \mathbf{x}) < \infty$, we define

recalling $(X_n(f) : f \in \mathscr{F})$ is the empirical process based on a random sample $(\mathbf{z}_i = (\mathbf{x}_i, y_i) : 1 \leq i \leq n)$ with

Strong Approximation Construction

In this section, we construct the Gaussian process $Z_n^G$ (along with some auxiliary Gaussian processes) on a possibly enlarged probability space to couple with the empirical process $G_n$.

The construction of the Gaussian process essentially follows from the arguments in Section (ref) with $\mathbf{z}_i$'s replacing $\mathbf{x}_i$'s. (Recall that $\mathbf{z}_i = (\mathbf{x}_i, y_i)$ in this section.) We start with a Gaussian process indexed by $(\mathscr{G} \cdot \mathscr{R}) \cup \mathtt{\Pi}_{0}(\mathscr{G} \times \mathscr{R}) \cup \mathtt{\Pi}_{1}(\mathscr{G} \times \mathscr{R})$ with almost sure continuous sample paths, and take conditional quantile transformations of Gaussian process indexed by $\mathbbm{1}_{\mathcal{C}_{j,k}}$ to construct counts of $(\mathbf{x}_i, y_i)$'s on the cells $\mathcal{C}_{j,k}$'s. By a Skorohod embedding argument, this Gaussian process can be taken on a possibly enriched probability space. More precisely, we have the following result.

The above two lemmas allow for constructions of Gaussian processes and projected Gaussian processes as counterparts of the empirical processes in Section (ref). In particular, we take $Z_n^G, \mathtt{\Pi}_{0} Z_n^G, \mathtt{\Pi}_{1} Z_n^G$ to be the empirical processes indexed by $\mathscr{G} \times \mathscr{R}$ such that

We also define the following ancillary processes for analysis:

In particular, $(Z_n^G(g,r): g \in \mathscr{G}, r \in \mathscr{R})$ has almost sure continuous trajectories in $(\mathscr{G} \times \mathscr{R},\mathfrak{d}_{\mathbbm{P}_Z})$

The following ancillary lemma for uniform covering number and uniform entropy integrals is used in the proof of Lemma (ref).

Meshing Error

To simplify notation, the parameters of \(\mathscr{G}\) (Definitions 4 to 12) are taken with \(\mathcal{C} = \mathcal{X}\), and the index \(\mathcal{X}\) is omitted where there is no ambiguity; the parameters of \(\mathscr{R}\) (Definitions 4 to 12) are taken with \(\mathcal{C} = \mathcal{Y}\), and the index \(\mathcal{Y}\) is omitted where there is no ambiguity; and the parameters of \(\mathscr{G} \times \mathscr{R}\) (Definitions 4 to 12, (ref), (ref)) are taken with \(\mathcal{C} = \mathcal{X} \times \mathcal{Y}\), and the index \(\mathcal{X} \times \mathcal{Y}\) is omitted where there is no ambiguity. We also define, for $\delta \in (0,1]$,

and

For \(0 < \delta \leq 1\), consider a \(\delta \mathtt{M}_{\mathscr{G}} \|M_{\mathscr{R}}\|_{\mathbbm{P}_Y ,2}\)-net of \((\mathscr{G} \times \mathscr{R}, \|\cdot\|_{\mathbbm{P}_Z,2})\), denoted by \((\mathscr{G} \times \mathscr{R})_{\delta}\), with cardinality at most \(\mathtt{N}_{\mathscr{G} \times \mathscr{R}}(\delta, \mathtt{M}_{\mathscr{G}} \|M_{\mathscr{R}}\|_{\mathbbm{P}_Y,2})\). Define the projection onto the \(\delta\)-net as a mapping \(\pi_{(\mathscr{G} \times \mathscr{R})_{\delta}} : \mathscr{G} \times \mathscr{R} \to \mathscr{G} \times \mathscr{R}\) such that \(\|\pi_{(\mathscr{G} \times \mathscr{R})_{\delta}}(g, r) - g r\|_{\mathbbm{P}_Z,2} \leq \delta \mathtt{M}_{\mathscr{G}} \|M_{\mathscr{R}}\|_{\mathbbm{P}_Y,2}\) for all \(g \in \mathscr{G}\) and \(r \in \mathscr{R}\).

Strong Approximation Errors

To simplify notation, the parameters of \(\mathscr{G}\) (Definitions 4 to 12) are taken with \(\mathcal{C} = \mathcal{X}\), and the index \(\mathcal{X}\) is omitted where there is no ambiguity; the parameters of \(\mathscr{R}\) (Definitions 4 to 12) are taken with \(\mathcal{C} = \mathcal{Y}\), and the index \(\mathcal{Y}\) is omitted where there is no ambiguity; and the parameters of \(\mathscr{G} \times \mathscr{R}\) (Definitions 4 to 12, (ref), (ref)) are taken with \(\mathcal{C} = \mathcal{X} \times \mathcal{Y}\), and the index \(\mathcal{X} \times \mathcal{Y}\) is omitted where there is no ambiguity. Recall we also define, for $\delta \in (0,1]$,

and

Projection Error

To simplify notation, the parameters of \(\mathscr{G}\) (Definitions 4 to 12, (ref), (ref)) are taken with \(\mathcal{C} = \mathcal{X}\), and the index \(\mathcal{X}\) is omitted where there is no ambiguity; the parameters of \(\mathscr{R}\) (Definitions 4 to 12) are taken with \(\mathcal{C} = \mathcal{Y}\), and the index \(\mathcal{Y}\) is omitted where there is no ambiguity; and the parameters of \(\mathscr{G} \times \mathscr{R}\) (Definitions 4 to 12, (ref), (ref)) are taken with \(\mathcal{C} = \mathcal{X} \times \mathcal{Y}\), and the index \(\mathcal{X} \times \mathcal{Y}\) is omitted where there is no ambiguity. Recall we also define, for $\delta \in (0,1]$,

and

To analyze the projection error, we employ the decomposition

where $\mathtt{\Pi}_{0} G_n(g,r) - G_n(g,r)$ represents the $L_2$ projection error, and $\mathtt{\Pi}_{1} G_n(g,r) - \mathtt{\Pi}_{0} G_n(g,r)$ denotes the mis-specification error. Specifically, the $L_2$ projection error captures the minimum loss incurred by projecting onto the class of piecewise constant functions over the cells $\mathscr{E}_{M + N}$. In contrast, the mis-specification error reflects the additional loss introduced when shifting from the $L_2$ projection to the product-factorized projection.

First we bound the mis-specification error.

Next we bound the $L_2$ projection error.

Using a truncation argument and the previous two lemmas, we get the bound on $\mathtt{\Pi}_{1}$-projection error with tail control.