For any $\delta>0$ and $h,h^{\prime}$ s.t.
$\|h-h^{\prime}\|_{\infty}\leq\delta$, we have (noting that
$\|h-h^{\prime}\|_{\infty}\leq 2B$ always hold)

$\|\bar{u}_{h}-\bar{u}_{h^{\prime}}\|_{\infty}\leq
n(4B^{2}\delta+\delta^{2})\leq 5nB^{2}\delta.$

Thus, we can follow (ii), with $u_{h}$ replaced by $\bar{u}_{h}$ and the
constants replaced appropriately, leading to

$\displaystyle\frac{1}{n}\mathbb{E}_{\epsilon}U_{\epsilon}^{2}$
$\displaystyle\leq
5nB^{3}+\inf_{\delta^{\prime}>0}\Big{(}\int_{\delta^{\prime}}^{10nB^{3}}\log
N(\mathcal{F}_{h,n},\|\cdot\|_{\infty},\delta/5nB^{2})d\delta+n\delta^{\prime}\Big{)},$
$\displaystyle\mathbb{E}_{\epsilon}U_{\epsilon}^{2}$ $\displaystyle\lesssim
n^{2}(B^{3}+B^{2}n\delta_{n,\mathcal{F}_{h,n}}^{2}),$ $\displaystyle
n^{-2}\mathbb{E}_{\epsilon}U_{\epsilon}$ $\displaystyle\leq
n^{-2}\sqrt{\mathbb{E}_{\epsilon}U_{\epsilon}^{2}}\lesssim
n^{-1}B^{3/2}+Bn^{-1/2}\delta_{n,\mathcal{F}_{h,n}}.$

Plugging the bounds for $U_{\epsilon},Z_{\epsilon}$ and $M$ back to (51), and
recalling that $\delta_{n,\mathcal{F}_{h,n}}\geq n^{-1/2}$, we can see that,
for some $C_{W}>0$,

$\mathbb{P}\Big{(}\sup_{h\in\mathcal{F}_{h,n}}|W_{n}(h)|\leq
C_{W}\big{(}B\delta_{n,\mathcal{F}_{h,n}}^{2}+B^{2}n^{-1}\log\zeta^{-1}\big{)}\Big{)}\geq
1-\frac{\zeta}{8}.$ (51’)

It remains to deal with $T_{n}$. Introduce
$v_{h}(w):=\mathbb{E}_{\mathbf{w}\sim P_{w}}w_{h}(w,\mathbf{w})$, so that
$T_{n}=\frac{1}{n}\sum_{i=1}^{n}v_{h}(w_{i})-\mathbb{E}_{\mathbf{w}}v_{h}$.
For any $h^{*}\in L_{2}(P_{zx}),w=(z,x)$, we have

$\displaystyle v_{h}(w)$
$\displaystyle=v_{h-h^{*}}(w)+\mathbb{E}_{(\tilde{\mathbf{z}},\tilde{\mathbf{x}})\sim
P_{zx}}(h^{*}(\tilde{\mathbf{z}},x)h(\tilde{\mathbf{z}},x)+h^{*}(z,\tilde{\mathbf{x}})h(z,\tilde{\mathbf{x}}))+v_{h^{*}}(w),$
$\displaystyle=:v_{h-h^{*}}(w)+\tilde{v}_{h,h^{*}}(w)+v_{h^{*}}(w),$
$\displaystyle T_{n}(h)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}(v_{h-h^{*}}(w_{i})-\mathbb{E}_{\mathbf{w}}v_{h-h^{*}})+(\tilde{v}_{h,h^{*}}(w_{i})-\mathbb{E}_{\mathbf{w}}\tilde{v}_{h,h^{*}})+(v_{h^{*}}(w_{i})-\mathbb{E}_{\mathbf{w}}v_{h^{*}})$
$\displaystyle=:T_{n,1}(h)+T_{n,2}(h)+T_{n,3}.$

Only the first two terms depend on $h$; we address them in turn.

  1. 1.

For $T_{n,1}$, by Lemma D.2 below we have, for some $c_{1},C>0$,

$\mathbb{P}\Bigg{(}\forall
h\in\mathcal{F}_{h,n},~{}|T_{n,1}(h)|\leq\frac{1}{4}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+CB^{2}\delta_{n,\mathcal{F}_{h,n}}^{2}+CB^{4}\frac{\log\zeta^{-1}}{n}\Bigg{)}\geq
1-\frac{\zeta}{8}.$

Clearly, a similar bound holds for $|T_{n,1}(h)-T_{n,1}(h^{*})|$.

  2. 2.

$T_{n,2}(h)$ is a sample average of 1-Lipschitz functions of
$\tilde{v}_{h,h^{*}}$. Thus, by Wainwright, (2019, Theorem 14.20), there
exists some $C^{\prime}>0$ s.t. w.p. $\geq
1-\exp(-C^{\prime}n\delta_{n,\tilde{\mathcal{V}}}^{2})$, we have, for all
$h\in\mathcal{F}_{h,n}$,

$|T_{n,2}(h)-T_{n,2}(h^{*})|\leq
10\delta_{n,\tilde{\mathcal{V}}}(\|\tilde{v}_{h,h^{*}}-\tilde{v}_{h^{*},h^{*}}\|_{L_{2}(P_{w})}+\delta_{n,\tilde{\mathcal{V}}}),$

where $\delta_{n,\tilde{\mathcal{V}}}$ upper bounds the critical radius of
$\tilde{\mathcal{V}}:=\\{\tilde{v}_{h,h^{*}}(\cdot):h\in\mathcal{F}_{h,n}\\}$.
By definition we have

$\displaystyle\|\tilde{v}_{h,h^{*}}-\tilde{v}_{h^{*},h^{*}}\|_{L_{2}(P_{w})}$
$\displaystyle=\big{[}\mathbb{E}_{(\mathbf{z},\mathbf{x})\sim
P_{zx}}(\mathbb{E}_{(\tilde{\mathbf{z}},\tilde{\mathbf{x}})\sim
P_{zx}}\\{[h^{*}(h-h^{*})](\tilde{\mathbf{z}},\mathbf{x})+[h^{*}(h-h^{*})](\mathbf{z},\tilde{\mathbf{x}})\\})^{2}\big{]}^{\frac{1}{2}}$
$\displaystyle\leq 2\|h^{*}\|_{\infty}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})},$
$\displaystyle\|\tilde{v}_{h,h^{*}}-\tilde{v}_{h^{\prime},h^{*}}\|_{\infty}$
$\displaystyle\leq 2\|h^{*}\|_{\infty}\|h-h^{\prime}\|_{\infty}.$

The second inequality also implies we can choose
$\delta_{n,\tilde{\mathcal{V}}}\asymp\|h^{*}\|_{\infty}\delta_{n,\mathcal{F}_{h,n}}$.
Plugging back, we have, for some $C^{\prime\prime}>1$, and all
$\delta_{n,\tilde{\mathcal{V}}}\geq
C^{\prime\prime}B\delta_{n,\mathcal{F}_{h,n}}$,

$\displaystyle e^{-n\delta_{n,\mathcal{F}_{h,n}}^{2}/C^{\prime\prime}}$
$\displaystyle\geq\mathbb{P}(\exists
h\in\mathcal{F}_{h,n},~{}|T_{n,2}(h)-T_{n,2}(h^{*})|\geq
C^{\prime\prime}(B^{2}\delta_{n,\mathcal{F}_{h,n}}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}+B^{2}\delta_{n,\mathcal{F}_{h,n}}^{2}))$
$\displaystyle\geq\mathbb{P}\Big{(}\exists
h\in\mathcal{F}_{h,n},~{}|T_{n,2}(h)-T_{n,2}(h^{*})|\geq\frac{1}{4}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+((C^{\prime\prime}B)^{4}+B^{2})\delta_{n,\mathcal{F}_{h,n}}^{2}\Big{)}.$

We use
$\delta_{n,\tilde{\mathcal{V}}}=C^{\prime\prime}B(\delta_{n,\mathcal{F}_{h,n}}+\sqrt{\log\zeta^{-1}/n})$.

Combining the results above, we have, for some $C_{T}>0$,

$\mathbb{P}\Big{(}\forall
h\in\mathcal{F}_{h,n},~{}|T_{n}(h)-T_{n,3}|\leq\frac{1}{2}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+C_{T}B^{4}\Big{(}\delta_{n,\mathcal{F}_{h,n}}^{2}+\frac{\log\zeta^{-1}}{n}\Big{)}\Big{)}\geq
1-\frac{\zeta}{4}.$ (52)

Combining (50), (51’), (52), we can see that for some $C>0$, w.p. $\geq
1-\zeta$ we have, for all $h\in\mathcal{F}_{h,n}$,

$|\mathcal{D}_{n}(h)-\mathcal{D}_{n}(h^{*})-\mathbb{E}_{P_{zx}}(\mathcal{D}_{n}(h)-\mathcal{D}_{n}(h^{*}))|\leq\frac{3}{4}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+\frac{1}{4}\|h^{*}-h_{0}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+CB^{4}\left(\delta_{n,\mathcal{F}_{h,n}}^{2}+\frac{\log\zeta^{-1}}{n}\right).$

For $\hat{h}_{n}=\arg\max_{h\in\mathcal{F}_{h,n}}\mathcal{D}_{n}(h)$, the LHS
above is lower bounded by
$\mathbb{E}_{P_{zx}}(\mathcal{D}_{n}(h^{*})-\mathcal{D}_{n}(h)).$ Moreover,
observe that

$\displaystyle\mathbb{E}_{P_{zx}}\mathcal{D}_{n}(h)$
$\displaystyle=\mathbb{E}_{P_{zx}}2h-\mathbb{E}_{P_{z}\otimes
P_{x}}h^{2}=\mathbb{E}_{P_{z}\otimes
P_{x}}(2h_{0}h-h^{2})=\|h_{0}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+\|h_{0}-h\|_{L_{2}(P_{z}\otimes P_{x})}^{2}.$

Thus, we have

$\displaystyle\phantom{=}\|h_{0}-\hat{h}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}-\|h_{0}-h^{*}\|_{L_{2}(P_{z}\otimes P_{x})}^{2}$
$\displaystyle\leq\frac{3}{4}\|\hat{h}-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+\frac{1}{4}\|h_{0}-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+CB^{4}\left(\delta_{n,\mathcal{F}_{h,n}}^{2}+\frac{\log\zeta^{-1}}{n}\right).$
$\displaystyle\leq\frac{7}{8}\|\hat{h}-h_{0}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+\frac{11}{2}\|h_{0}-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+CB^{4}\left(\delta_{n,\mathcal{F}_{h,n}}^{2}+\frac{\log\zeta^{-1}}{n}\right),$

or

$\|h_{0}-\hat{h}\|_{L_{2}(P_{z}\otimes P_{x})}^{2}\leq
52\|h_{0}-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+8CB^{4}\left(\delta_{n,\mathcal{F}_{h,n}}^{2}+\frac{\log\zeta^{-1}}{n}\right).$

The proof completes by observing
$\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})-\mathcal{D}_{\chi^{2},\mathrm{lb}}({h})=\|h_{0}-h\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}.$ ∎

In the following lemma, note that the critical radius is defined w.r.t. the
different measure of $P_{z}\otimes P_{x}$; however, it can still be bounded
using that of the sup norm.

######  Lemma D.2.

In the setting of Proposition D.1, there exists some $c_{1}>0$ s.t. for any
$t>\delta_{n}$,

$\mathbb{P}\Big{(}\forall
h\in\mathcal{F}_{h,n},|T_{n,1}(h)|\geq\frac{1}{4}\|\Delta
h\|_{L_{2}(P_{z}\otimes P_{x})}^{2}+\frac{B^{2}}{2}t^{2}\Big{)}\leq
2e^{-c_{1}nt^{2}/B^{2}},$

where $\delta_{n}$ upper bounds the critical radius of the local Rademacher
complexity $\mathcal{R}_{n}(B_{2}(r;\mathcal{F}_{h,n}))$, and
$B_{2}(r;\mathcal{F}_{h,n}):=\\{h-h^{*}:h\in\mathcal{F}_{h,n},\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}\leq r\\}$.

###### Proof.

The proof modifies Wainwright, (2019, Section 14.1.3) with two additions of
Jensen’s inequality. Let

$Z_{n}(r):=\sup_{\Delta h\in
B_{2}(r;\mathcal{F}_{h,n})}|T_{n,1}(h)|=\sup_{\Delta h\in
B_{2}(r;\mathcal{F}_{h,n})}\Big{|}\frac{1}{n}\sum_{i=1}^{n}v_{\Delta
h}(w_{i})-\mathbb{E}_{\mathbf{w}}v_{\Delta h}\Big{|}.$

Following the same scaling argument as in their Lemma 14.8,141414Note we have
$T_{n,1}(h^{*}+\alpha\Delta h)=\alpha^{2}T_{n,1}(h^{*}+\Delta h)$, so the same
argument applies., it suffices to establish that

$\mathbb{P}\Big{(}Z_{n}(r)\geq\frac{Br\delta_{n}}{4}+\frac{B^{2}s^{2}}{4}\Big{)}\leq
2e^{-c_{2}n\min\\{s^{4}/r^{2},s^{2}\\}},$ (53)

for some $c_{2}>0$ and all $r,s>\delta_{n}$. We first bound the expectation.
We have

$\displaystyle\mathbb{E}_{\\{w_{i}\\}}Z_{n}(r)$
$\displaystyle\overset{(i)}{\leq}2\mathbb{E}_{\\{w_{i},\epsilon_{i}\\}}\sup_{\Delta
h\in
B_{2}(r;\mathcal{F}_{h,n})}\Big{|}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}v_{\Delta
h}(w_{i})\Big{|}=2\mathbb{E}_{\\{w_{i},\epsilon_{i}\\}}\sup_{\Delta h\in
B_{2}(r;\mathcal{F}_{h,n})}\Big{|}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\mathbb{E}_{\tilde{\mathbf{w}}}u_{\Delta
h}(w_{i},\tilde{\mathbf{w}})\Big{|}$
$\displaystyle\overset{(ii)}{\leq}2\mathbb{E}_{\\{w_{i},\epsilon_{i}\\}}\mathbb{E}_{\\{\tilde{w}_{i}\\}}\sup_{\Delta
h\in
B_{2}(r;\mathcal{F}_{h,n})}\Big{|}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}u_{\Delta
h}(w_{i},\tilde{w}_{i})\Big{|}$
$\displaystyle=2\mathbb{E}_{\\{w_{i},\tilde{w}_{i},\epsilon_{i}\\}}\sup_{\Delta
h\in
B_{2}(r;\mathcal{F}_{h,n})}\Big{|}\frac{1}{2n}\sum_{i=1}^{n}\epsilon_{i}(\Delta
h^{2}(z_{i},\tilde{x}_{i})+\Delta h^{2}(\tilde{z}_{i},x_{i}))\Big{|}$
$\displaystyle\leq
2\mathbb{E}_{\\{z_{i},\tilde{x}_{i},\epsilon_{i}\\}}\sup_{\Delta h\in
B_{2}(r;\mathcal{F}_{h,n})}\Big{|}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\Delta
h^{2}(z_{i},\tilde{x}_{i})\Big{|}\overset{(iii)}{\leq}4B\mathbb{E}_{\\{z_{i},\tilde{x}_{i},\epsilon_{i}\\}}\sup_{\Delta
h\in
B_{2}(r;\mathcal{F}_{h,n})}\Big{|}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\Delta
h(z_{i},\tilde{x}_{i})\Big{|}$
$\displaystyle=4B\mathcal{R}_{n}(B_{2}(r;\mathcal{F}_{h,n}))\overset{(iv)}{\leq}\frac{Br\delta_{n}}{4}.$

In the above, $\mathcal{R}_{n}(B_{2}(r;\mathcal{F}_{h,n}))$ is the Rademacher
complexity of $B_{2}(r;\mathcal{F}_{h,n})$; (i), (iii), (iv) follow the same
reasoning as Wainwright, (2019): they apply symmetrization, Lipschitz
contraction of $\mathcal{R}_{n}$, and the monotonicity of
$\mathcal{R}_{n}(B_{2}(r;\mathcal{F}_{h,n}))/r$, respectively. (ii) invokes
Jensen’s inequality and exchanges $\sup$ and $\mathbb{E}$.

Now we establish the tail bound above the expectation. Observe that

$\displaystyle\mathbb{E}_{\mathbf{w}}v_{\Delta_{h}}^{2}$
$\displaystyle=\mathbb{E}_{\mathbf{w}}(\mathbb{E}_{\tilde{\mathbf{w}}}u_{\Delta
h}(\mathbf{w},\tilde{\mathbf{w}}))^{2}\overset{(i)}{\leq}\mathbb{E}_{\mathbf{w},\tilde{\mathbf{w}}}u_{\Delta
h}(\mathbf{w},\tilde{\mathbf{w}})^{2}\overset{(ii)}{\leq}\|u_{\Delta
h}\|_{\infty}\mathbb{E}_{\mathbf{w},\tilde{\mathbf{w}}}u_{\Delta
h}(\mathbf{w},\tilde{\mathbf{w}})\leq
B^{2}\mathbb{E}_{\mathbf{z},\tilde{\mathbf{x}}}\Delta
h^{2}(\mathbf{z},\tilde{\mathbf{x}})\leq B^{2}r^{2}.$

where (i) is Jensen’s inequality, and (ii) follows by the non-negativity of
$u$. Applying Talagrand’s inequality as in Wainwright, (2019) establishes
(53). ∎

###  Appendix E Additional Results: Representation Learning

####  E.1 Overview of Results

In this section, Proposition E.1 bounds the error using the estimated kernel
(19’). Proposition E.2 establishes a generic approximation result for the
spectral representation learning objective
$\mathcal{D}_{\chi^{2},\mathrm{lb}}({h})$. Proposition E.3 and Corollary E.1
illustrate it on our main running example.

######  Proposition E.1 (estimation error of the population kernel).

Let $k_{x}$ be defined by (19’) in the text. Let $T_{x}$ be the
$P_{x}$-integral operator of $k_{x}$, and $\tilde{T}:=T_{x}^{1/\alpha}$.
Suppose $(\hat{\Sigma}_{x},\hat{\Sigma}_{z})$ are computed using $n$ i.i.d.
samples $\mathcal{D}^{(n)}_{2}=\\{(z_{c,i},x_{c,i})\\}$ independent of
$\hat{h}_{n}$. Then there exist $c^{\prime},c^{\prime\prime}>0$ s.t.

  1. (i)

when $\alpha=1$, with $\mathcal{D}^{(n)}_{2}$-probability $\geq 1-\zeta$
w.r.t. $(\hat{\Sigma}_{x},\hat{\Sigma}_{z})$, we have $\tilde{T}$ satisfies
(11’), with $c=1$, and $\epsilon_{n}^{2}$ bounded by

$\epsilon_{n}^{2}\leq\epsilon_{n,1}^{2}:=\|\hat{h}_{n}-h_{0}\|_{2}^{2}+c^{\prime}\|\hat{h}_{n}\|_{\infty}^{2}\frac{J_{n}+\log\zeta^{-1}}{n}.$

  2. (ii)

when $\alpha=2,J_{n}\leq n$, and $(\hat{h}_{n},\zeta)$ additionally satisfies

$\lambda_{max}(\Sigma_{x})\vee\lambda_{max}(\Sigma_{z})\leq
2,~{}~{}(\|\hat{\Phi}_{n}\|_{\infty}^{2}+\|\hat{\Psi}_{n}\|_{\infty}^{2})\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}\leq
c^{\prime\prime},~{}~{}\|\hat{\Psi}_{n}\|_{\infty}^{2}\lambda_{min}^{-1}(\Sigma_{x})\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}\leq
c^{\prime\prime},$ (54)

with $\mathcal{D}^{(n)}_{2}$-probability greater than $1-4\zeta$, $\tilde{T}$
will satisfy (11’) with

$c=2,~{}~{}\epsilon_{n}\leq
2\epsilon_{n,1}+c^{\prime}(\|\hat{\Psi}_{n}\|_{\infty}^{2}+\|\hat{\Phi}_{n}\|_{\infty}^{2})\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}.$

Moreover, in both cases, (12), (12’) and (14) will hold with the above
$\epsilon_{n}$.

######  Remark E.1.

Comparing with $k_{x,p}$ which satisfies Lemma 4.1 with
$\epsilon_{n}^{2}=\|\hat{h}_{n}-h_{0}\|_{2}^{2}$, we find the sampling error
in $k_{x}$ introduced an overhead of $\mathcal{O}(J_{n}/n)$. When $J_{n}$ is
chosen appropriately, this term will have a negligible order, as exemplified
in Proposition E.3 below. As we can see from the proof, the $J_{n}/n$ term may
also be replaced by some intrinsic complexity conditions for $k_{x}$ (e.g.,
metric entropy bounds, which imply the same critical radius bounds,
Wainwright,, 2019); this is also the case for all occurrences of $J_{n}$ in
the following, but we do not pursue this route for simplicity.

######  Proposition E.2 (generic approximation bound).

Let the reproducing kernel $k_{x}^{h},k_{z}^{h}$ be defined by the integral
operator $(E^{\top}E)^{1/2},(EE^{\top})^{1/2}$. Suppose $k_{x}^{h},k_{z}^{h}$
satisfy Assumption 4.1 in Wang et al., (2022). Define the truncated Gaussian
process $f_{x}^{(J_{n})}:=\sum_{j=1}^{\lceil
J_{n}/2\rceil}\epsilon_{j}\sqrt{\bar{s}_{j}}\bar{\psi}_{j},~{}\text{where
}\epsilon_{j}\sim N(0,1),$ where we recall
$E=\sum_{i=1}^{\infty}\bar{s}_{i}\bar{\varphi}_{i}\otimes\bar{\psi}_{i}$
denotes its SVD. Suppose the hypothesis space $\mathcal{F}_{x,n}$ satisfy

$\mathbb{E}_{f_{x}^{(J_{n})}}\inf_{\tilde{f}\in\mathcal{F}_{x,n}}\|f_{x}^{(J_{n})}-\tilde{f}\|_{2}^{2}\leq\epsilon_{GP,n}^{2}\leq
1.$

Suppose hypothesis space $\mathcal{F}_{z,n}\subset L_{2}(P_{z})$ satisfy a
similar bound, defined by the GP $g_{z}^{(J_{n})}:=\sum_{j=1}^{\lceil
J_{n}/2\rceil}\epsilon^{\prime}_{j}\sqrt{\bar{s}_{j}}\bar{\varphi}_{j},$ and
the same $\epsilon_{GP,n}$. Then there exists some universal $c_{F}>0$, s.t.
the hypothesis space

$\displaystyle\mathcal{F}_{h,n}:=\Bigg{\\{}h(z,x)=\sum_{i=1}^{J_{n}}\sum_{j=1}^{J_{n}}a_{ij}g_{i}(z)f_{j}(x):~{}$
$\displaystyle
g_{i}\in\mathcal{F}_{z,n},f_{j}\in\mathcal{F}_{x,n},A:=(a_{ij})=B^{\top}C,$
$\displaystyle\text{ where }B,C\in\mathbb{R}^{\lceil J_{n}/2\rceil\times
J_{n}},\|B\|+\|C\|\leq C_{F}J_{n}^{-1/2}\Bigg{\\}}$ (55)

satisfies the approximation bound

$\inf_{h\in\mathcal{F}_{h,n}}\|h-h_{0}\|_{2}^{2}\lesssim\epsilon_{GP,n}^{2}+\sum_{j\geq\lceil
J_{n}/2\rceil}\bar{s}_{j}^{2}.$

######  Remark E.2.

For the above $\mathcal{F}_{h,n}$, any $h\in\mathcal{F}_{h,n}$ can be written
in the form of $h(z,x)=(B_{h}G_{h}(z))^{\top}(C_{h}F_{h}(x))$. We introduce
the notations
$\Psi_{h}(x):=C_{h}F_{h}(x),\Phi_{h}(z):=B_{h}G_{h}(z),\hat{\Psi}_{n}:=\Psi_{\hat{h}_{n}},\hat{\Phi}_{n}:=\Phi_{\hat{h}_{n}}.$

######  Proposition E.3 (spectral decomposition, compositional Hölder model).

Let $\mathbf{x},\mathbf{z},f_{enc,x},f_{enc,z}$ be defined as in Example 2.1,
2.2. Suppose $\mathrm{dim}\;\mathbf{x}=\mathrm{dim}\;\mathbf{z}=d_{obs}$, and
$f_{enc,x},f_{enc,z}$ are $\beta_{d}$ Hölder regular. Let
$\mathcal{F}_{x,n},\mathcal{F}_{z,n}$ be specified as DNN models in Schmidt-
Hieber, (2020), with hyperparameters chosen appropriately (see proof for
details). Let $\mathcal{F}_{h,n}$ be defined as in Proposition E.2. Then with
probability $\geq 1-n^{-10}$, the estimate $\hat{h}_{n}$ in Proposition 4.1
satisfies

$\|\hat{h}_{n}\|_{\infty}^{2}=\mathcal{O}(\log^{2}n),~{}~{}\|\hat{h}_{n}-h_{0}\|_{2}^{2}=\tilde{\mathcal{O}}\Big{(}J_{n}^{-(2p-1)}+\frac{J_{n}^{2}}{n}+J_{n}\big{(}n^{-\frac{p-2}{p-1}}+n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}\big{)}\Big{)}.$
(56)

Consequently, when $\alpha=1,\beta_{l}\geq(p-2)d_{obs}/2,J_{n}\asymp
n^{(p-2)/(2p+1)(p-1)}$, we have, with probability $\geq 1-n^{-11}$ w.r.t. the
samples $(\mathcal{D}^{(n)}_{1},\mathcal{D}^{(n)}_{2})$, the RKHS
corresponding to the kernel (19’) will satisfy (11’), with $c=1$ and

$\epsilon_{n}^{2}=\tilde{\mathcal{O}}\big{(}n^{-\frac{(p-2)(2p-1)}{(p-1)(2p+1)}}\big{)}.$
(57)

######  Remark E.3.

In the above, we have only assumed $f_{enc,x},f_{enc,z}$ to have the same
regularity for notational simplicity; the result can be trivially extended.
Given (57), (12), (12’) and (14) follow immediately by Lemma C.1 and Theorem
3.1.151515Recall the proof for Theorem 3.1 only requires (11’).

######  Corollary E.1.

Let $\mathbf{z},\mathbf{x},f_{enc,x},f_{enc,z},\beta_{d},\mathcal{F}_{h,n}$ be
defined as in Proposition E.3. Let $A_{n}=\tilde{\mathcal{O}}(1)$ be some
slowly increasing sequence to be specified in the proof, and
$\hat{h}_{n}(z,x)=\hat{\Phi}_{n}^{\top}(z)\hat{\Psi}_{n}(x)$ be the solution
to the following constrained optimization problem:

$\min_{h\in\mathcal{F}_{h,n}}\mathcal{D}_{n}(h),\quad\text{s.t.}~{}~{}\lambda_{min}(\hat{\Sigma}_{x,h})\geq
A_{n}n^{-\frac{p(p-2)}{(p-1)(2p+1)}},~{}\lambda_{max}(\hat{\Sigma}_{x,h})\leq\frac{6}{5},~{}\lambda_{max}(\hat{\Sigma}_{z,h})\leq\frac{6}{5}.$
(58)

In the above,
$\hat{\Sigma}_{x,h}=\frac{1}{n}\sum_{i=1}^{n}\Psi_{n}(\tilde{x}_{i})\Psi_{n}^{\top}(\tilde{x}_{i})$,
$\hat{\Sigma}_{z,h}=\frac{1}{n}\sum_{i=1}^{n}\Phi_{n}(\tilde{z}_{i})\Phi_{n}^{\top}(\tilde{z}_{i})$
are the empirical covariance matrices, and
$(\hat{\Sigma}_{x,h},\hat{\Sigma}_{z,h},\mathcal{D}_{n})$ are all using the
samples $\mathcal{D}^{(n)}_{1}=\\{(\tilde{z}_{i},\tilde{x}_{i})\\}_{i=1}^{n}$.
Then $\hat{h}_{n}$ continues to satisfy (56). Moreover, suppose
$\beta_{l}\geq(p-2)d_{obs}/2,\alpha=2,J_{n}\asymp
A_{n}^{-1/p}n^{(p-2)/(2p+1)(p-1)}$. Then on a
$(\mathcal{D}^{(n)}_{1},\mathcal{D}^{(n)}_{2})$-measurable event w.p. $\geq
1-3n^{-11}$, the RKHS $\mathcal{H}$ corresponding to the kernel (19’) will
satisfy (12), (12’) and (14), with

$\epsilon_{n}^{2}=\tilde{\mathcal{O}}\left(n^{-\frac{(p-2)(2p-1)}{(p-1)(2p+1)}}\right).$

We now prove them in turn.

####  E.2 Proof for Proposition E.1

We first establish (11’) for the two choices of $\alpha$.

The $\alpha=1$ case: define the integral operators $T_{x,p}f:=\int
f(x)k_{x,p}(x,\cdot)dP_{x}(x)$, $T_{x}f:=\int f(x)k_{x}(x,\cdot)dP_{x}(x)$. As
$\alpha=1$, we have, for all $f\in L_{2}(P_{x})$,

$\displaystyle\langle f,T_{x}f\rangle_{2}$ $\displaystyle=\int
f(x^{\prime})\left(\int\hat{k}(x,x^{\prime})f(x)dP_{x}(x)\right)dP_{x}(x^{\prime})$
$\displaystyle=\int
f(x^{\prime})\Psi(x^{\prime})^{\top}\hat{\Sigma}_{z}\underbrace{\left(\int\Psi(x)f(x)dP_{x}(x)\right)}_{=:\mu_{f}}dP_{x}(x^{\prime})$
$\displaystyle=:\mu_{f}^{\top}\hat{\Sigma}_{z}\mu_{f}=\|\mu_{f}^{\top}\Psi(\cdot)\|_{n,2}^{2},$
$\displaystyle\langle f,T_{x,p}f\rangle_{2}$
$\displaystyle=\|\mu_{f}^{\top}\Psi(\cdot)\|_{2}^{2},$

where $\|g\|_{n,2}:=\sqrt{\frac{1}{n}\sum_{i=1}^{n}g(z_{i})^{2}}$ denotes the
empirical $L_{2}$ norm defined w.r.t. the $n$ samples used to estimate
$\hat{\Sigma}_{z}$. Therefore, it suffices to show that

$\mathbb{P}\Bigg{(}\sup_{\|f\|_{2}=1}\big{|}\|\mu_{f}^{\top}\Psi(\cdot)\|_{n,2}-\|\mu_{f}^{\top}\Psi(\cdot)\|_{2}\big{|}\
\leq
c\|\hat{h}_{n}\|_{\infty}\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}\Bigg{)}\geq
1-\zeta,$ (59)

after which we will have, on the above event, for all $\|f\|_{2}=1$,

$\displaystyle|\|\tilde{T}^{1/2}f\|_{2}-\|T^{1/2}f\|_{2}|$
$\displaystyle\leq|\|T_{x}^{1/2}f\|_{2}-\|T_{x,p}^{1/2}f\|_{2}|+|\|T_{x,p}^{1/2}f\|_{2}-\|T^{1/2}f\|_{2}|$
$\displaystyle\leq
c\|\hat{h}_{n}\|_{\infty}\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}+|\|T_{x,p}^{1/2}f\|_{2}-\|T^{1/2}f\|_{2}|$
$\displaystyle\overset{(i)}{\leq}c\|\hat{h}_{n}\|_{\infty}\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}+\|E-\tilde{E}\|_{\mathrm{HS}}$
$\displaystyle\overset{\eqref{eq:loss-
equiv-1}}{=}c\|\hat{h}_{n}\|_{\infty}\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}+\|\hat{h}_{n}-h_{0}\|_{2}.$

In the above, (i) can be found in Section C.1.

(59) follows from a standard localization argument (see e.g., Wainwright,,
2019, Theorem 14.1): the function space
$\mathcal{G}_{e}:=\\{\mu_{f}^{\top}\Psi(\cdot):\|f\|_{2}=1\\}$ is
$d$-dimensional, and has sup norm bounded by

$\sup_{g\in\mathcal{G}_{e}}\|g\|_{\infty}=\sup_{\|f\|_{2}=1}\sup_{z\in\mathcal{Z}}\int\Phi(z)^{\top}\Psi(x)f(x)dP_{x}(x)\leq\sup_{\|f\|_{2}=1}\sup_{z\in\mathcal{Z}}\|h(z,\cdot)\|_{L_{2}(P_{x})}\|f\|_{L_{2}(P_{x})}\leq\|h\|_{\infty}.$

Thus, by Wainwright, (2019, Corollary 14.5), the critical radius in their
Theorem 14.1 can be chosen as
$\delta_{n}^{2}=c^{\prime}\|h\|_{\infty}^{2}\frac{J_{n}+\log\zeta^{-1}}{n}$,
which provides the desired probability.

The $\alpha=2$ case: In this case, we have

$\displaystyle T_{x}$
$\displaystyle=\Psi^{\top}\hat{\Sigma}_{x}^{-1/2}(\hat{\Sigma}_{x}^{1/2}\hat{\Sigma}_{z}\hat{\Sigma}_{x}^{1/2})^{\alpha}\hat{\Sigma}_{x}^{-1/2}\Psi^{\top}$
$\displaystyle=(\Sigma_{x}^{-1/2}\Psi)^{\top}\Sigma_{x}^{1/2}\hat{\Sigma}_{x}^{-1/2}(\underbrace{\hat{\Sigma}_{x}^{1/2}\hat{\Sigma}_{z}\hat{\Sigma}_{x}^{1/2}}_{=:S})^{\alpha}\underbrace{\hat{\Sigma}_{x}^{-1/2}\Sigma_{x}^{1/2}}_{=:B}(\underbrace{\Sigma_{x}^{-1/2}\Psi}_{=:\Psi^{\prime}}),$
$\displaystyle\tilde{T}=T_{x}^{1/\alpha}$
$\displaystyle=\Psi^{\prime\top}(B^{\top}S^{\alpha}B)^{1/\alpha}\Psi^{\prime},$

where the last equality follows as $\Psi^{\prime}\Psi^{\prime\top}=I$. By the
result for $\alpha=1$, we know that w.p. $\geq 1-\zeta$,
$\tilde{T}^{\prime}=\Psi^{\prime\top}B^{\top}SB\Psi^{\prime}$ will satisfy
(11’) with $c=1,\epsilon_{n}=\epsilon_{n,1}$. Thus, to prove $\tilde{T}$
satisfy (11’) with the claimed constants, it suffices to show that on that
event, we have, w.p. $\geq 1-\zeta$,

$\frac{1}{4}\tilde{T}^{\prime}\prec\tilde{T}\prec 4\tilde{T}^{\prime}.$ (60)

By the operator monotonicity of the function $(\cdot)^{\frac{1}{2}}$ (Bhatia,,
2013, Theorem V.1.9), (60) is implied by $\frac{1}{16}\tilde{T}^{\prime
2}\prec\tilde{T}^{2}\prec 16\tilde{T}^{\prime 2};$ since
$\Psi^{\prime}\Psi^{\prime\top}=I$, the latter condition is equivalent to
$\frac{1}{16}B^{\top}SBB^{\top}SB\prec B^{\top}S^{2}B\prec
16B^{\top}SBB^{\top}SB,$ which in turn is implied by

$\frac{1}{16}I\prec\Sigma_{x}^{-1/2}\hat{\Sigma}_{x}\Sigma_{x}^{-1/2}\prec
16I.$ (60’)

It remains to establish (60’). Observe that for $\mathbf{x}\sim P_{x}$, The
vector $\Sigma_{x}^{-1/2}\Psi_{n}(\mathbf{x})$ is $\sigma_{x}^{2}$-subgaussian
with
$\sigma_{x}^{2}\lesssim\sup_{x\in\mathcal{X}}\|\hat{\Psi}_{n}(x)\|_{2}^{2}\lambda_{min}^{-1}(\Sigma_{x}).$
Thus, by concentration of sub-gaussian matrices (Wainwright,, 2019, Theorem
6.5), there exists some universal $c>1$, s.t. (60’) will hold w.p. $\geq
1-\zeta$ when

$(\sup_{x\in\mathcal{X}}\|\hat{\Psi}_{n}(x)\|_{2})^{2}s_{min}^{-1}(\Sigma_{x})\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}\leq
c.$

This proves (11’).

It remains to establish (12), (12’) and (14). As noted in its proof, (14)
always holds under the relaxed condition (11’). For (12), the $\alpha=1$ case
follows by Lemma C.1 (iii). When $\alpha=2$, by Wainwright, (2019, Theorem
6.5) we have, w.p. $\geq 1-2\zeta$,

$\|\hat{\Sigma}_{z}-\Sigma_{z}\|+\|\hat{\Sigma}_{x}-\Sigma_{x}\|\leq
c^{\prime\prime\prime}(\sup_{x\in\mathcal{X}}\|\hat{\Psi}_{n}(x)\|_{2}^{2}+\sup_{z\in\mathcal{Z}}\|\hat{\Phi}_{n}(z)\|_{2}^{2})\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}\overset{\eqref{eq:h-ev-
constraint}}{\leq}c^{\prime\prime\prime}c^{\prime\prime},$

for some universal $c^{\prime\prime\prime}>0$. Thus, (12) is proved by
plugging into Lemma C.1 (ii) the high-probability bound

$\displaystyle\|T^{\frac{\alpha}{2}}-\tilde{T}^{\frac{\alpha}{2}}\|$
$\displaystyle=\|\Psi^{\top}(\Sigma_{z}\Sigma_{x}\Sigma_{z}-\hat{\Sigma}_{z}\hat{\Sigma}_{x}\hat{\Sigma}_{z})\Psi\|$
$\displaystyle\lesssim\|\Psi\|^{2}(\|\hat{\Sigma}_{z}-\Sigma_{z}\|(\|\Sigma_{x}\|\|\Sigma_{z}\|+1)+(\|\Sigma_{z}\|^{2}+1)\|\hat{\Sigma}_{x}-\Sigma_{x}\|)$
$\displaystyle\overset{\eqref{eq:h-ev-
constraint}}{\lesssim}\|\hat{\Sigma}_{z}-\Sigma_{z}\|+\|\hat{\Sigma}_{x}-\Sigma_{x}\|$
$\displaystyle\lesssim(\sup_{x\in\mathcal{X}}\|\hat{\Psi}_{n}(x)\|_{2}^{2}+\sup_{z\in\mathcal{Z}}\|\hat{\Phi}_{n}(z)\|_{2}^{2})\sqrt{\frac{J_{n}+\log\zeta^{-1}}{n}}.$

(All hidden constants above are universal.) (12’) now follows by Lemma C.1
(iv), which holds for both $\alpha$. This completes the proof. ∎

####  E.3 Proof for Proposition E.2

Define $J_{h}:=\lceil J_{n}/2\rceil$,

$\bar{\Phi}:L_{2}(P_{z})\to\mathbb{R}^{J_{h}},g\mapsto\begin{bmatrix}\langle
g,\sqrt{\bar{s}_{1}}\bar{\varphi}_{1}\rangle_{2}\\\ \ldots\\\ \langle
g,\sqrt{\bar{s}_{J_{h}}}\bar{\varphi}_{J_{h}}\rangle_{2}\end{bmatrix}.$

As noted in Appendix A, we can view
$\bar{\Phi}=(\sqrt{\bar{s}_{1}}\bar{\varphi}_{1};\ldots;\sqrt{\bar{s}_{J_{h}}}\bar{\varphi}_{J_{h}})$
as an “infinitely wide matrix”. Define
$\bar{\Psi}:L_{2}(P_{x})\to\mathbb{R}^{J_{h}}$ similarly, using
$(\sqrt{\bar{s}_{1}}\bar{\psi}_{1},\ldots,\sqrt{\bar{s}_{J_{h}}}\bar{\psi}_{J_{h}})$.
Recall that by Section D.1, we have
$h_{0}(z,x)=\sum_{i=1}^{\infty}\bar{s}_{i}\bar{\varphi}_{i}(z)\bar{\psi}_{i}(x),$
and thus

$\|\bar{\Phi}^{\top}\bar{\Psi}-h_{0}\|_{2}^{2}=\sum_{j>{J_{h}}}\bar{s}_{j}^{2}.$
(61)

We now construct a probabilistic approximation to
$\bar{\Phi}^{\top}\bar{\Psi}$. Let $\\{g^{(j)}:j\in[J_{n}]\\}$ be $J_{n}$
i.i.d. copies of $g^{(J_{n})}_{z}$, so that we have

$\displaystyle\bar{G}:=\begin{bmatrix}g^{(1)}\\\ \ldots\\\
g^{(J_{n})}\end{bmatrix}=\begin{bmatrix}\epsilon_{z,11}&\ldots&\epsilon_{z,1,J_{h}}\\\
\ldots&\ldots&\ldots\\\
\epsilon_{z,J_{n},1}&\ldots&\epsilon_{z,J_{n},J_{h}}\end{bmatrix}\begin{bmatrix}\sqrt{\bar{s}_{1}}\bar{\psi}_{1}\\\
\ldots\\\
\sqrt{\bar{s}_{J_{h}}}\bar{\psi}_{J_{h}}\end{bmatrix}=:\Xi\bar{\Phi},$

where $\\{\epsilon_{z,i,j}:i\in[J_{n}],j\in[J_{h}]\\}$ are i.i.d. standard
normal variables. Define

$\tilde{G}(z):=(\tilde{g}^{(1)}(z),\ldots,\tilde{g}^{(J_{n})}(z)),$

where $\tilde{g}^{(j)}\in\mathcal{F}_{z,n}$ is the best approximation to
$g^{(j)}$. Then by the assumed condition on $\mathcal{F}_{z,n}$ we have

$\|\tilde{G}-\bar{G}\|_{2,2}^{2}=\mathbb{E}\sum_{j=1}^{J_{n}}\|\tilde{g}^{(j)}-g^{(j)}\|_{2}^{2}\leq
J\epsilon_{GP,n}^{2}.$

and by Markov’s inequality,

$\mathbb{P}_{\Xi}(\|\tilde{G}-\bar{G}\|_{2,2}^{2}\leq
9J\epsilon_{GP,n}^{2})\geq 1-\frac{1}{9}.$ (62)

We also have (Wang et al.,, 2022, Eq. 17), with high probability,

$\|(\Xi^{\top}\Xi)^{-1}\Xi^{\top}\|\leq cJ_{n}^{-1/2},$ (63)

where $c>0$ is a universal constant. Let us assume $J_{n}\geq c^{\prime}$,
where the constant $c^{\prime}$ is chosen so that the above event has
probability $\geq 8/9$. Define
$\hat{\Phi}:=(\Xi^{\top}\Xi)^{-1}\Xi^{\top}\tilde{G}.$ Then, on the
intersection of the above two events, we have

$\displaystyle\|\hat{\Phi}-\Phi\|_{2,2}$
$\displaystyle=\|(\Xi^{\top}\Xi)^{-1}\Xi^{\top}(\tilde{G}-\bar{G})\|_{2,2}\leq\|(\Xi^{\top}\Xi)^{-1}\Xi^{\top}\|\|\tilde{G}-\bar{G}\|_{2,2}\leq
3c\epsilon_{GP,n}.$

As a similar condition holds for $\mathcal{F}_{x,n}$, following the same
reasoning we find the existence of some
$\Psi:=(\Xi^{\prime\top}\Xi^{\prime})^{-1}\Xi^{\prime\top}\tilde{F},$ where
$\tilde{F}=(\tilde{f}^{(1)},\ldots,\tilde{f}^{(J_{n})})$ and
$\tilde{f}^{(j)}\in\mathcal{F}_{x,n}$, such that

$\mathbb{P}_{\Xi^{\prime}}(\|\hat{\Psi}-\Psi\|_{2,2}\leq
3c\epsilon_{GP,n})\geq\frac{7}{9}.$

Combining, we have

$\mathbb{P}_{\Xi,\Xi^{\prime}}(\max\\{\|\hat{\Phi}-\Phi\|_{2,2},\|\hat{\Psi}-\Psi\|_{2,2}\\}\leq
3c\epsilon_{GP,n})\geq\frac{5}{9}.$

Thus, there exists some $(\hat{\Phi},\hat{\Psi})$ so that the above
inequalities hold true. And we have,

$\displaystyle\|\hat{\Phi}^{\top}\hat{\Psi}-\Phi^{\top}\Psi\|_{2}^{2}$
$\displaystyle\leq
2\int\int(\hat{\Phi}(z)^{\top}(\hat{\Psi}-\Psi)(x))^{2}dP_{z}dP_{x}+2\int\int((\hat{\Phi}-\Phi)(z)^{\top}\Psi(x))^{2}dP_{z}dP_{x}$
$\displaystyle=2(\|\hat{\Phi}\|_{2,2}^{2}\|\hat{\Psi}-\Psi\|_{2,2}^{2}+\|\hat{\Phi}-\Phi\|_{2,2}^{2}\|\Psi\|_{2,2}^{2})$
$\displaystyle\leq
2((\|\Phi\|_{2,2}+\|\Phi-\hat{\Phi}\|_{2,2})^{2}\|\hat{\Psi}-\Psi\|_{2,2}^{2}+\|\hat{\Phi}-\Phi\|_{2,2}^{2}\|\Psi\|_{2,2}^{2})$
$\displaystyle\lesssim\epsilon_{GP,n}^{2}.$

Combining the above with (61), we have

$\|\hat{\Phi}^{\top}\hat{\Psi}-h_{0}\|_{2}^{2}\lesssim\epsilon_{GP,n}^{2}+\sum_{j\geq
J_{h}}\bar{s}_{j}^{2}.$

It remains to verify that

$\hat{\Phi}^{\top}\hat{\Psi}=\tilde{G}^{\top}(\underbrace{((\Xi^{\top}\Xi)^{-1}\Xi^{\top})}_{=:B})^{\top}\underbrace{(\Xi^{\prime\top}\Xi^{\prime})^{-1}\Xi^{\prime\top}}_{=:C}\tilde{F}\in\mathcal{F}_{h,n}.$
(64)

This follows from (63) and the similar condition on $\Xi^{\prime}$, and
because we always have
$\tilde{g}^{(i)}\in\mathcal{F}_{z,n},\tilde{f}^{(i)}\in\mathcal{F}_{x,n}.$
This completes the proof.∎

######  Remark E.4.

We note that for the matrices $B,C$ defined above, $A=B^{\top}C$ satisfies

$\|A\|_{F}^{2}=Tr(A^{\top}A)\leq J_{n}\|A^{\top}A\|\leq
J_{n}\|B\|^{2}\|C\|^{2}\leq c^{2}J_{n}^{-1},$

where the constant $c>0$ is universal. Thus, we have

$\mathcal{F}_{h,n}\subset\mathcal{F}_{h,n}^{\prime}:=\\{h(z,x)=\sum_{ij}a_{ij}g_{i}(z)f_{j}(x):g_{i}\in\mathcal{F}_{z,n},f_{j}\in\mathcal{F}_{x,n},A:=(a_{ij})\text{
satisfies }\|A\|_{F}\leq c^{2}J_{n}^{-1}\\}.$ (65)

####  E.4 Proof for Proposition E.3

We shall construct approximate models for the truncated Gaussian processes in
Proposition E.2, and invoke Proposition D.1, also using the covering number
bound of Lemma E.1.

First, consider the truncated Gaussian process
$g^{(J_{h})}_{z}=\sum_{i=1}^{J_{h}}\sqrt{\epsilon_{i}\bar{s}_{i}}\bar{\varphi}_{i}.$
By Claim B.2 and B.1, we have $\bar{\varphi}_{i}=\bar{\varphi}_{i}^{l}\circ
f_{enc,z}$, where $\\{\bar{\varphi}_{i}^{l}\\}$ are the left singular vectors
of the operator

$\bar{E}:L_{2}(P(d\bar{x}))\to
L_{2}(P(d\bar{z})),f_{l}\mapsto\mathbb{E}(f_{l}(\bar{\mathbf{x}})\mid\bar{\mathbf{z}}).$

Thus, we have $g^{(J_{h})}_{z}=g^{(J_{h})}_{l}\circ f_{enc,z},$ where
$g^{(J_{h})}_{l}(\bar{z})=\sum_{i=1}^{J_{h}}\sqrt{\epsilon_{i}\bar{s}_{i}}\bar{\varphi}_{i}^{l}(\bar{z})$
defines a “latent space GP”. We repeat the argument in Ex. 2.2 to characterize
its regularity. Introduce the latent function spaces

$\bar{\mathcal{I}}_{l}^{\gamma}:=\operatorname{Ran}((\bar{E}\bar{E}^{\top})^{\gamma/2}),~{}\|g\|_{\bar{\mathcal{I}}_{l}^{\gamma}}:=\|(\bar{E}\bar{E}^{\top})^{-\gamma/2}g\|_{2},$

where $\gamma>0$ is any real number. Recall $\bar{s}_{i}\asymp i^{-p}$ (Ex.
2.2). Thus, the eigenvalues of the operator $(\bar{E}\bar{E}^{\top})^{\gamma}$
decays at $e_{i}(\bar{E}\bar{E}^{\top})^{\gamma}\asymp i^{-2p\cdot\gamma}$. As
noted in Chen and Reiss, (2007), for $(\bar{\mathbf{x}},\bar{\mathbf{z}})$ as
defined in Ex. 2.2, both the left and right singular vectors of $\bar{E}$ are
the Fourier basis functions, and $\bar{\mathcal{I}}_{l}^{\gamma}$ is norm-
equivalent to the periodic Sobolev space of order $\gamma pd$. Thus, for any
$\epsilon>0$, the natural inclusion operator from
$\bar{\mathcal{I}}_{l}^{1/2}$ to $\bar{\mathcal{I}}_{l}^{(p-1-\epsilon)/2p}$
is Hilbert-Schmidt, and by Steinwart, (2019), there exists a version of
$g_{l}^{(\infty)}:=\sum_{i=1}^{\infty}\sqrt{\epsilon_{i}\bar{s}_{i}}\bar{\varphi}_{i}$
taking value in
$\bar{\mathcal{I}}_{l}^{(p-1-\epsilon)/2p}=W_{per}^{\frac{(p-1-\epsilon)d}{2}}$,
and we have

$\mathbb{E}_{g_{l}^{(J_{h})}}\|g_{l}^{(J_{h})}\|_{\bar{\mathcal{I}}_{l}^{(p-1-\epsilon)/2p}}^{2}\leq\mathbb{E}_{g_{l}^{(\infty)}}\|g_{l}^{(\infty)}\|_{\bar{\mathcal{I}}_{l}^{(p-1-\epsilon)/2p}}^{2}<\infty,$

where the first equality holds pointwise, by definition of the RKHS norm. Now,
by the Sobolev embedding theorem, we have

$\mathbb{E}_{g_{l}^{(J_{h})}}\|g_{l}^{(J_{h})}\|_{\mathcal{C}^{\frac{(p-2-\epsilon)d}{2}}}^{2}\leq\mathbb{E}_{g_{l}^{(\infty)}}\|g_{l}^{(\infty)}\|_{\bar{\mathcal{I}}_{l}^{(p-1-\epsilon)/2p}}^{2}<\infty,$

where for any $r>0$, $\mathcal{C}^{r}$ denotes the Hölder space of order $r$
(Giné and Nickl,, 2021). Note the above bound holds uniformly across all
$J_{h}\in\mathbb{N}$.

Now we invoke the approximation result in Schmidt-Hieber, (2020): by invoking
their Lemma 5 as in their Theorem 1, we find that, for any constant $C>0$,
there exists a ReLU DNN model with

$\log
N(\mathcal{F}_{z,n},\|\cdot\|_{\infty},\delta)\lesssim\big{(}n^{\frac{1}{p-1-\epsilon}}+n^{\frac{d_{obs}}{2\beta_{d}+d_{obs}}}\big{)}(\log^{2}n+\log\delta^{-1}),$
(66)

and some constant $C^{\prime}>0$, s.t. for all
$g_{l}\in\mathcal{C}^{(p-2-\epsilon)d}$ with
$\|g_{l}\|_{\mathcal{C}^{(p-2-\epsilon)d}}\leq C\log n$, we have

$\inf_{\tilde{g}\in\mathcal{F}_{z,n}}\|\tilde{g}-g_{l}\circ
f_{enc,z}\|_{2}^{2}\leq
C^{\prime}\log^{3}n\Big{(}n^{-\frac{p-2-\epsilon}{p-1-\epsilon}}+n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}\Big{)}\|g\|_{\mathcal{C}^{(p-2-\epsilon)d}}.$

By their construction, $\mathcal{F}_{z,n}$ also satisfies the sup norm bound

$B_{n}:=\sup_{g\in\mathcal{F}_{z,n}}\|g\|_{\infty}\lesssim\log n.$ (67)

Invoking the Borell-TIS inequality as in Wang et al., (2022, Appendix C.5.1),
we find

$\mathbb{E}_{g^{(J_{h})}_{z}}\inf_{\tilde{g}\in\mathcal{F}_{z,n}}\|\tilde{g}-g^{(J_{h})}_{z}\|_{2}^{2}\leq
C^{\prime}\log^{4}n\Big{(}n^{-\frac{p-2-\epsilon}{p-1-\epsilon}}+n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}\Big{)}.$

Following the same reasoning, we can establish the same approximation and
covering bounds for $(\mathcal{F}_{x,n},f_{x}^{(J_{n})})$. Thus, we conclude
that

$\epsilon_{GP,n}^{2}\leq
C^{\prime}\log^{4}n\Big{(}n^{-\frac{p-2-\epsilon}{p-1-\epsilon}}+n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}\Big{)},$
(68)

and, by Proposition E.2, the existence of some $h^{*}\in\mathcal{F}_{h,n}$
s.t.

$\|h^{*}-h_{0}\|_{2}^{2}\lesssim\log^{4}n\Big{(}n^{-\frac{p-2-\epsilon}{p-1-\epsilon}}+n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}\Big{)}+J_{n}^{-(2p-1)}.$
(69)

Plugging (66) (and a similar result for $\mathcal{F}_{x,n}$) into Lemma E.1,
and plugging the result into Proposition D.1, we find the following holds with
probability $\geq 1-\zeta$:

$\displaystyle\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})-\mathcal{D}_{\chi^{2},\mathrm{lb}}({\hat{h}_{n}})$
$\displaystyle\lesssim\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})-\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{*}})+B^{4}\Big{(}J_{n}\log^{4}n\Big{(}n^{-\frac{p-2-\epsilon}{p-1-\epsilon}}+n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}\Big{)}+\frac{J_{n}^{2}}{n}+\frac{\log\zeta^{-1}}{n}\Big{)}.$
(70)

To bound $B=\sup_{h\in\mathcal{F}_{h,n}}\|h\|_{\infty}$ above, observe that
for any $h\in\mathcal{F}_{h,n}$, we have (recall the notations in Remark E.2)

$\displaystyle\|\Phi_{h}\|_{\infty}=\sup_{z\in\mathcal{Z}}\|B_{h}G_{h}(x)\|_{2}$
$\displaystyle\leq\|B_{h}\|\cdot\sqrt{J_{n}}B_{n}\overset{\eqref{eq:combined-
space}}{\leq}C_{F}B_{n},~{}~{}~{}~{}\|\Psi_{h}\|_{\infty}\leq C_{F}B_{n},$
(71) $\displaystyle\|h\|_{\infty}$
$\displaystyle\leq\|\Psi_{h}\|_{\infty}\|\Phi_{h}\|_{\infty}\lesssim
B_{n}^{2}\overset{\eqref{eq:Bn-bound}}{\lesssim}\log^{2}n.$

Plugging (69) and the above into (70), we find

$\displaystyle\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})-\mathcal{D}_{\chi^{2},\mathrm{lb}}({\hat{h}_{n}})$
$\displaystyle\lesssim\tilde{\mathcal{O}}\Big{(}J_{n}^{-(2p-1)}+\frac{J_{n}^{2}}{n}+J_{n}\big{(}n^{-\frac{p-2}{p-1}}+n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}\big{)}+\frac{\log\zeta^{-1}}{n}\Big{)}.$
(72)

This proves (56).

When $\beta_{l}\geq\frac{p-2}{2}d_{obs}$, the term
$n^{-\frac{2\beta_{d}}{2\beta_{d}+d_{obs}}}$ does not dominate. Thus, for
$J_{n}\asymp n^{\frac{(p-2)}{(p-1)(2p+1)}}$, (72) reduces to

$\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})-\mathcal{D}_{\chi^{2},\mathrm{lb}}({\hat{h}_{n}})=\tilde{\mathcal{O}}\Big{(}n^{-\frac{(p-2)(2p-1)}{(p-1)(2p+1)}}+\frac{\log\zeta^{-1}}{n}\Big{)}.$

(57) is proved by invoking Proposition E.1 (i), and observing the added terms
do not dominate. ∎

####  E.5 Proof for Corollary E.1

We first show that with high probability (56) continues to hold for the new
$\hat{h}_{n}$. Denote by $\hat{\mathcal{F}}_{h,n}\subset\mathcal{F}_{h,n}$ the
set of functions that satisfy the eigenvalue constraints. Then
$\hat{\mathcal{F}}_{h,n}$ satisfies the same the entropy bound as
$\mathcal{F}_{h,n}$, and thus the oracle inequality (70) continues to hold. To
bound the approximation error in (70), let $h^{*}\in\mathcal{F}_{h,n}$ be
defined as in the proof of Proposition E.3; observe that we can choose
$A_{n}=\tilde{\mathcal{O}}(1)$ and $J_{n}\asymp
A_{n}^{-1/p}n^{(p-2)/(2p+1)(p-1)}$ so that
$\hat{\mathcal{F}}_{h,n}=\hat{\mathcal{F}}_{h,n,\frac{2}{3}\bar{s}_{J_{n}},\frac{6}{5}}$,
where the right hand side is defined in Lemma E.2 below. Let $E_{n}$ denote
the $\mathcal{D}^{(n)}_{1}$-measurable event defined in the lemma, with
probability $\geq 1-2n^{-11}$. By its claim (ii), we have
$h^{*}\in\hat{\mathcal{F}}_{h,n}$ on $E_{n}$. Thus, (72) and subsequently,
(56), also continue to hold.

On the event $E_{n}$, by Lemma E.2 (i) (b), (iii), (71) and our choice of
$J_{n}$, the optima $\hat{h}_{n}$ for (58) will satisfy (54) for
$\zeta=n^{-11}$. Thus, by Proposition E.1 (ii), on the intersection of $E_{n}$
and a $\mathcal{D}^{(n)}_{2}$-measurable event w.p. $\geq 1-n^{-11}$, (12),
(12’) and (14) hold with

$\epsilon_{n}^{2}=\tilde{\mathcal{O}}\left(J_{n}^{-(2p-1)}+\frac{J_{n}^{2}}{n}+J_{n}n^{-\frac{p-2}{p-1}}+\cancel{\frac{J_{n}+\log
n}{n}}\right)=\tilde{\mathcal{O}}\left(n^{-\frac{(p-2)(2p-1)}{(p-1)(2p+1)}}\right).$

This completes the proof.∎

####  E.6 Auxiliary Results

######  Lemma E.1 (covering number bound).

Let $\mathcal{F}_{x,n},\mathcal{F}_{z,n}$ be function spaces with sup norm
bounded by $B_{n}$. Let $\mathcal{F}_{h,n}$ be defined as in Proposition E.2.
Then there exists some universal $c>0$ s.t.

$\log N(\mathcal{F}_{h,n},\|\cdot\|_{\infty},\delta)\leq
cJ_{n}(\log(\mathcal{F}_{x,n},\|\cdot\|_{\infty},B_{n}^{-1}\delta)+\log(\mathcal{F}_{z,n},\|\cdot\|_{\infty},B_{n}^{-1}\delta))+J_{n}^{2}\log(1+B_{n}^{2}\delta^{-1}),$

for all $\delta>0$.

###### Proof.

We construct a covering for the slightly larger space
$\mathcal{F}_{h,n}^{\prime}$ defined in (65). Let
$\\{f^{(i)}_{c}:i\in[N_{x,\delta}]\\}$, $\\{g^{(i)}_{c}:i\in[N_{z,\delta}]\\}$
denote a pair of $\delta$-coverings of $\mathcal{F}_{x,n},\mathcal{F}_{z,n}$
in sup norm. Let $\\{A^{(i)}_{c}:i\in[N_{A,\delta}]\\}$ denote a
$B_{n}^{-1}J_{n}^{-1}\delta$-covering of $\\{A:\|A\|_{F}\lesssim
J_{n}^{-1}\\}$ in Frobenious norm. For any $h=G^{\top}AF\in\mathcal{F}_{h,n}$,
let $\tilde{G},\tilde{F},\tilde{A}$ denote the closest element of $G,F,A$ in
the respective covering set. Then we have

$\displaystyle\|h-\tilde{G}^{\top}\tilde{A}\tilde{F}\|_{\infty}\leq\|(G-\tilde{G})^{\top}\tilde{A}\tilde{F}\|_{\infty}+\|G^{\top}(\tilde{A}-A)\tilde{F}\|_{\infty}+\|G^{\top}A(\tilde{F}-F)\|_{\infty}.$

To bound the terms above, we first observe that, for any
$F^{\prime}=(f^{\prime}_{1};\ldots;f^{\prime}_{J_{n}}),G^{\prime}=(g^{\prime}_{1};\ldots;g^{\prime}_{J_{n}}),A^{\prime}\in\mathbb{R}^{J_{n}\times
J_{n}}$, we have

$\displaystyle\|G^{\prime\top}A^{\prime}F^{\prime}\|_{\infty}$
$\displaystyle=\sup_{x\in\mathcal{X},z\in\mathcal{Z}}G^{\prime}(z)^{\top}A^{\prime}F^{\prime}(x)\leq\sup_{x\in\mathcal{X},z\in\mathcal{Z}}\|G^{\prime}(z)\|_{2}\|A^{\prime}\|\|F^{\prime}(x)\|_{2}$
$\displaystyle\leq\sqrt{J_{n}}(\max_{i\in[J_{n}]}\|g^{\prime}_{i}\|_{\infty})\cdot\|A^{\prime}\|\cdot\sqrt{J_{n}}(\max_{i\in[J_{n}]}\|f^{\prime}_{i}\|_{\infty}).$
(73)

Plugging back, we have

$\displaystyle\|(G-\tilde{G})^{\top}\tilde{A}\tilde{F}\|_{\infty}$
$\displaystyle\lesssim\sqrt{J_{n}}\delta\cdot
J_{n}^{-1}\cdot\sqrt{J_{n}}B_{n}=B_{n}\delta.$
$\displaystyle\|G^{\top}A(\tilde{F}-F)\|_{\infty}$ $\displaystyle\lesssim
B_{n}\delta.$ $\displaystyle\|G^{\top}(\tilde{A}-A)\tilde{F}\|_{\infty}$
$\displaystyle\lesssim\sqrt{J_{n}}B_{n}\cdot
B_{n}^{-1}J_{n}^{-1}\delta\cdot\sqrt{J_{n}}B_{n}=B_{n}\delta.$

Thus, the set $\\{h:=\sum_{kl}g_{k}A_{kl}f_{l}\\}$ where $(g_{k},A,f_{l})$ are
in the respective covering sets defined above, constitute a
$\mathcal{O}(B_{n}\delta)$ covering for $\mathcal{F}_{h,n}^{\prime}$ (the
hidden constant is universal). The logarithm of its cardinality is

$\log N_{x,\delta}^{J_{n}}N_{z,\delta}^{J_{n}}N_{A,\delta}\leq J_{n}(\log
N_{x,\delta}+\log N_{z,\delta})+J_{n}^{2}\log(1+2B_{n}\delta^{-1}).$

The proof completes by a scaling argument. ∎

######  Lemma E.2.

Let $\mathcal{D}^{(n)}=\\{(z_{i},x_{i})\\}$ be $n$ i.i.d. samples from
$P_{zx}$. For any $h\in\mathcal{F}_{h,n}$ let $(\Psi_{h},\Phi_{h})$ be defined
as in Remark E.2, $\Sigma_{x,h}=\mathbb{E}_{\mathbf{x}\sim
P_{x}}\Psi_{h}(\mathbf{x})\Psi_{h}^{\top}(\mathbf{x})$, and
$\hat{\Sigma}_{x,h}$ denotes its empirical estimate using $\mathcal{D}^{(n)}$.
Define $(\hat{\Sigma}_{z,h},\Sigma_{z,h})$ similarly using $\Phi_{h}$. For any
$0<s<t$, define the spaces

$\displaystyle\mathcal{F}_{h,n,s,t}$
$\displaystyle:=\left\\{h\in\mathcal{F}_{h,n}:s\leq\lambda_{min}(\Sigma_{x,h})\leq\lambda_{max}(\Sigma_{x,h})\leq
t,\lambda_{max}(\Sigma_{z,h})\leq t\right\\},$
$\displaystyle\hat{\mathcal{F}}_{h,n,s,t}$
$\displaystyle:=\left\\{h\in\mathcal{F}_{h,n}:s\leq\lambda_{min}(\hat{\Sigma}_{x,h})\leq\lambda_{max}(\hat{\Sigma}_{x,h})\leq
t,\lambda_{max}(\hat{\Sigma}_{z,h})\leq t\right\\}.$

Suppose $p\geq 2,\beta_{l}\geq\frac{p-2}{2}d_{obs}$. Then there exists
$C_{0},C_{1},C_{2}>0$, and a slowly growing sequence
$M_{n}=\tilde{\mathcal{O}}(1)$ s.t. on a $\mathcal{D}^{(n)}$-measurable event
w.p. $\geq 1-2n^{-11}$, the following holds for any $n\geq C_{0},J_{n}\leq
M_{n}^{-1}n^{\frac{p-2}{(2p+1)(p-1)}}$:

  1. (i)

For any $(s,t)$:

    1. (a)

For all $h\in\mathcal{F}_{h,n,s,t}$, we have
$h\in\hat{\mathcal{F}}_{h,n,s-\Delta s_{n},t+0.1}$, for $\Delta
s_{n}=C_{1}\log^{3}n\sqrt{J_{n}}n^{-\frac{p-2}{p-1-\epsilon}}$.

    2. (b)

For any $h\in\hat{\mathcal{F}}_{h,n,s,t}$, we have
$h\in\mathcal{F}_{h,n,s-\Delta s_{n},t+0.1}$.

  2. (ii)

For $s=\frac{2}{3}\bar{s}_{J_{n}},t=\frac{11}{10}$, we have
$h^{*}\in\mathcal{F}_{h,n,s,t}\cap\hat{\mathcal{F}}_{h,n,s/2,t+0.1}$.

  3. (iii)

For the above $(s,t)$, any $h\in\mathcal{F}_{h,n,s/2,t+0.1}$ will satisfy
(54).

###### Proof.

We prove the three claims in turn.

  1. (i)

For all $h\in\mathcal{F}_{h,n}$, recall by (71) that
$\|\Psi_{h}\|_{\infty}\vee\|\Phi_{h}\|_{\infty}\leq C_{F}\log n$. Thus, by
Wainwright, (2019, Theorem 6.5), there exists some $C>0$, s.t. for all
$h\in\mathcal{F}_{h,n},\delta\in(0,1)$, we have

$\mathbb{P}_{\mathcal{D}^{(n)}}\left(\|\Sigma_{x,h}-\hat{\Sigma}_{x,h}\|\geq
C\log^{2}n\Big{(}\sqrt{\frac{J_{n}}{n}}+\delta\Big{)}\right)\leq
e^{-Cn\delta^{2}}.$ (74)

We now build a covering for
$\mathcal{S}_{x,n}:=\\{\hat{\Sigma}_{x,h}:h\in\mathcal{F}_{h,n}\\}.$ Using an
argument similar to Lemma E.1 below, and plugging in the symmetric version of
(66) for $\mathcal{F}_{x,n}$ (see the proof for details), we find, for all
$\delta^{\prime}>0$,

$\displaystyle\log N(\mathcal{S}_{x,n},\|\cdot\|,\delta^{\prime})$
$\displaystyle\leq c(J_{n}\log
N(\mathcal{F}_{x,n},\|\cdot\|_{\infty},B_{n}\delta^{\prime})+J_{n}^{2}\log(1+B_{n}^{2}\delta^{\prime-1}))$
$\displaystyle\lesssim
J_{n}(n^{1/(p-1-\epsilon)}+J_{n})(\log^{2}n+\log\delta^{\prime-1}).$

Denote by $\mathrm{F}_{h,n,\delta^{\prime}}\subset\mathcal{F}_{h,n}$ the
function set that induced the $\delta^{\prime}$-covering of
$\mathcal{S}_{x,n}$, so that its cardinality can be bounded as above. Recall
that $J_{n}\leq n^{1/(p-1-\epsilon)}$, and consider $\delta^{\prime}\leftarrow
n^{-1},\delta\leftarrow C^{\prime}n^{-(p-2)/2(p-1-\epsilon)}\sqrt{J_{n}}\log
n$, where $C^{\prime}>0$ is sufficiently large. Then a union bound over (74)
shows that

$\mathbb{P}_{\mathcal{D}^{(n)}}\Bigl{(}\sup_{\tilde{h}\in\mathrm{F}_{h,n,\delta^{\prime}}}\|\Sigma_{x,\tilde{h}}-\hat{\Sigma}_{x,\tilde{h}}\|\leq
C^{\prime}\log^{3}n\Bigl{(}\cancel{\sqrt{\frac{J_{n}}{n}}}+\sqrt{J_{n}}n^{-\frac{p-2}{2(p-1-\epsilon)}}\Bigr{)}\Bigr{)}\geq
1-e^{-(C^{\prime}/2)n^{1/(p-1-\epsilon)}J_{n}\log^{2}n}\geq 1-n^{-11}.$ (75)

For any $(s,t)$ and $h\in\mathcal{F}_{h,n,s,t}$, let
$\tilde{h}\in\mathrm{F}_{h,n,\delta^{\prime}}\cap\mathcal{F}_{h,n,s,t}$
minimize $\|\hat{\Sigma}_{x,\tilde{h}}-\hat{\Sigma}_{x,h}\|$. Then, on (75),
we have

$\displaystyle\lambda_{min}(\hat{\Sigma}_{x,h})$
$\displaystyle=\lambda_{min}(\Sigma_{x,\tilde{h}}-\Sigma_{x,\tilde{h}}+\hat{\Sigma}_{x,\tilde{h}}-\hat{\Sigma}_{x,\tilde{h}}+\hat{\Sigma}_{x,h})\geq\lambda_{min}(\Sigma_{x,\tilde{h}})-(\|\Sigma_{x,\tilde{h}}-\hat{\Sigma}_{x,\tilde{h}}\|+\|\hat{\Sigma}_{x,\tilde{h}}-\hat{\Sigma}_{x,h}\|)$
$\displaystyle\geq
s-C^{\prime}\log^{3}n\sqrt{J_{n}}n^{-\frac{p-2}{2(p-1-\epsilon)}}\cancel{-\frac{1}{n}}.$
$\displaystyle\lambda_{max}(\hat{\Sigma}_{x,h})$
$\displaystyle\leq\lambda_{max}(\Sigma_{x,\tilde{h}})+(\|\hat{\Sigma}_{x,\tilde{h}}-\Sigma_{x,\tilde{h}}\|+\|\hat{\Sigma}_{x,\tilde{h}}-\hat{\Sigma}_{x,h}\|)\leq
t+\frac{1}{10}.$

. In the above, the eigenvalue inequalities can be found as Bhatia, (2013,
Exercise III.2.5), and the second display holds for $n\geq C_{02}$
sufficiently large. Following the same argument we find
$\lambda_{max}(\hat{\Sigma}_{z,h})\leq t+\frac{1}{10}$. This proves (a).
The proof for (b) follows the same argument, with all occurrences of
$\hat{\Sigma}$ and $\Sigma$ exchanged. We omit it for brevity.

  2. (ii)

In App. E.3 we have established that
$h^{*}(z,x)=\hat{\Phi}^{\top}(z)\hat{\Psi}(x)$, where (recall our convention
in Appendix A)

$\|\hat{\Psi}-\Psi\|\leq\|\hat{\Psi}-\Psi\|_{\text{HS}}=\mathbb{E}\|\hat{\Psi}(\mathbf{x})-\Psi(\mathbf{x})\|_{2}^{2}\leq
3c\epsilon_{GP,n},~{}~{}\text{and}~{}s_{j}(\Psi)=\sqrt{\bar{s}_{j}}~{}~{}\forall
j\in[J_{n}/2].$

Thus we have, for some $C_{01}>0$ and any $n\geq C_{01}$,

$\displaystyle\lambda_{max}(\Sigma_{x,h^{*}})$
$\displaystyle\leq(\sqrt{\bar{s}_{1}}+3c\epsilon_{GP,n})^{2}=(1+3c\epsilon_{GP,n})^{2}\leq\frac{11}{10},$
$\displaystyle\lambda_{min}(\Sigma_{x,h^{*}})$
$\displaystyle=s_{min}^{2}(\hat{\Psi}^{\top})\geq(s_{min}(\Psi)-3c\epsilon_{GP,n})^{2}\geq\frac{3}{4}\bar{s}_{J_{n}}-27\epsilon_{GP,n}^{2}\geq\frac{2}{3}\bar{s}_{J_{n}},$

where the last inequality follows by plugging (68) and our condition on
$\beta_{l}$. As the same bound was established for
$\mathbb{E}\|\hat{\Phi}(\mathbf{z})-\Phi(\mathbf{z})\|_{2}^{2}$, we can
similarly show that $\lambda_{max}(\Sigma_{z,h^{*}})\leq\frac{11}{10}$, and

$h^{*}\in\mathcal{F}_{h,n,\frac{2}{3}\bar{s}_{J_{n}},\frac{11}{10}}.$

By claim (i) (b) and the fact that $\bar{s}_{J_{n}}\gg\Delta s_{n}$ for our
choice of $J_{n}$, we have
$h^{*}\hat{\mathcal{F}}_{h,n,\frac{1}{3}\bar{s}_{J_{n}},\frac{6}{5}}$.

  3. (iii)

By (71), there exists some $C\in(0,1)$ s.t. (54) holds for such $h$ as long as

$\zeta\geq e^{-CJ_{n}},~{}\bar{s}_{J_{n}}^{-1}\sqrt{J_{n}/n}\log^{2}n\leq
C,~{}\bar{s}_{J_{n}}\geq C^{-1}\epsilon_{GP,n}^{2}.$

By (68) and our condition on $\beta_{l}$, the latter two inequalities will
hold when $J_{n}\leq n^{(p-2)/(p-1)2p}.$

∎

###  Appendix F Results for Conditional Moment Models

####  F.1 Proof for Theorem 4.1

We prove the following more general result, which covers Theorem 4.1 in its
claim (ii).

######  Theorem F.1.

Suppose there exists some $f_{0}$ that satisfies (5) with $\beta\geq 1$. Let

  * •

$\hat{h}_{n}(z,x)=\hat{\Phi}_{n}^{\top}(z)\hat{\Psi}_{n}(x)$ be defined using
$n$ samples $\mathcal{D}^{(n)}_{1}$, and suppose
$\hat{\Phi}_{n}(z)\in\mathbb{R}^{J_{n}}$.

  * •

$\mathcal{D}^{(n)}_{2}$ be an independent set of $n$ i.i.d. samples,
$(k_{x},\mathcal{H})$ be defined by (19’) using
$\hat{h}_{n},\mathcal{D}^{(n)}_{2}$, and some $\alpha\in\mathbb{Z}_{+}$, and
$(k_{z},\mathcal{I})$ be defined by (21) using
$\hat{h}_{n},\mathcal{D}^{(n)}_{2}$ and $\alpha^{\prime}=1$.

  * •

$\mathcal{D}^{(n)}_{3}$ be a third independent set of $n$ i.i.d. samples from
$P_{zxy}$, and $\hat{f}_{n}$ be defined by (3), using
$k_{z},k_{x},\mathcal{D}^{(n)}_{3}$ and $\nu_{n},\lambda_{n}$ as in (86)
below.

Then for some constant $C_{N}>0$ and any $n\geq C_{N}$:

  1. (i)

Suppose $\\{\epsilon_{n}\\},\\{\zeta_{n}\\}$ be s.t. with probability $\geq
1-\zeta_{n}$, (12), (12’) and (14) hold, and that
$\|\hat{h}_{n}-h_{0}\|_{2}\leq\epsilon_{n}$. Then we have, w.p. $\geq
1-\zeta_{n}-2n^{-11}$,

$\|\hat{f}_{n}-f_{0}\|_{2}=\mathcal{O}\Big{(}\Big{(}\epsilon_{n}^{\frac{\alpha}{\alpha+1}}+\Big{(}\frac{\|\hat{h}_{n}\|_{\infty}^{2}J_{n}^{2}+\log
n}{n}\Big{)}^{\frac{\alpha}{2(\alpha+1)}}\Big{)}(1+\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{\frac{2\alpha}{\alpha+1}})\Big{)}.$
(76)

  2. (ii)

When $\mathbf{x},\mathbf{z},f_{enc,x},f_{enc,z},p,\beta_{d}$ are defined as
Theorem 4.1, $J_{n}\asymp n^{\frac{(p-2)}{(2p+1)(p-1)}}$, and either _(a)_
$\alpha=1$, $\hat{h}_{n}$ maximizes (49), or _(b)_ $\alpha=2$, $\hat{h}_{n}$
solves (58), then we have, w.p. $\geq 1-n^{-10}$,

$\|\hat{f}_{n}-f_{0}\|_{2}=\tilde{\mathcal{O}}\big{(}n^{-\frac{\alpha(p-2)}{(\alpha+1)(4p+1)}}(1+\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{\frac{2\alpha}{\alpha+1}})\big{)},$

where $\tilde{\mathcal{O}}$ hides all sub-polynomial factors.

###### Proof.

We first establish (i) in there steps:

  1. 1.

We first derive approximation and estimation bounds for $\mathcal{H}$. By (5),
on the event w.p. $\geq 1-\zeta_{n}$, (12) holds for $\bar{f}=f_{0}$, and
there exists some

$\tilde{f}_{n}\in\mathcal{H},~{}\|\tilde{f}_{n}\|_{\mathcal{H}}\lesssim\|f_{0}\|_{\bar{\mathcal{H}}_{{\alpha}}},~{}\|\tilde{f}_{n}-f_{0}\|_{2}^{2}\lesssim\epsilon_{n}^{2(\alpha\wedge
1)}\|f_{0}\|_{\bar{\mathcal{H}}_{{\alpha}}}^{2}.$ (77)

We restrict to the above event throughout the proof. For estimation, we first
claim that

$\sup_{x\in\mathcal{X}}k_{x}(x,x)\leq\|\hat{h}_{n}\|_{\infty}^{2\alpha},~{}~{}\forall\alpha\in\mathbb{Z}_{+}.$
(78)

To prove this, let $\\{(z^{s}_{i},x^{s}_{i})\\}:=\mathcal{D}^{(n)}_{2}$. Then
for
$S_{x}=\frac{1}{\sqrt{n}}(\hat{\Psi}_{n}(x_{1}^{s}),\ldots,\hat{\Psi}_{n}(x_{n}^{s})),S_{z}=\frac{1}{\sqrt{n}}(\hat{\Phi}_{n}(z_{1}^{s}),\ldots,\hat{\Phi}_{n}(z_{n}^{s})),$
we have
$\hat{\Sigma}_{z}=S_{z}S_{z}^{\top},\hat{\Sigma}_{x}=S_{x}S_{x}^{\top}$, and

$\displaystyle\|S_{z}^{\top}S_{x}\|$
$\displaystyle\leq\|S_{z}^{\top}S_{x}\|_{F}=\sqrt{n^{-2}\sum_{i=1}^{n}\sum_{j=1}^{n}\hat{\Phi}_{n}(z_{i}^{s})\hat{\Psi}_{n}(x_{j}^{s})}\leq\|\hat{h}_{n}\|_{\infty},$
$\displaystyle\|S_{z}^{\top}\hat{\Psi}_{n}(x)\|_{2}$
$\displaystyle\leq\sqrt{n}\|S_{z}^{\top}\hat{\Psi}_{n}(x)\|_{\infty}=\max_{i\in[n]}\hat{\Phi}_{n}(z_{i}^{s})\hat{\Psi}_{n}(x)\leq\|\hat{h}_{n}\|_{\infty},$
$\displaystyle k_{x}(x,x)$
$\displaystyle=\hat{\Psi}_{n}(x)^{\top}\hat{\Sigma}_{z}(\hat{\Sigma}_{x}\hat{\Sigma}_{z})^{\alpha-1}\hat{\Psi}_{n}(x)=\hat{\Psi}_{n}^{\top}(x)S_{z}(S_{z}^{\top}S_{x}S_{x}^{\top}S_{z})^{\alpha-1}S_{z}^{\top}\hat{\Psi}_{n}(x)\leq\|\hat{h}_{n}\|_{\infty}^{2\alpha}.$

Given (78), the critical radius (Wainwright,, 2019, Eq. 14.4) of local
Rademacher complexity of the unit norm ball $\mathcal{H}_{1}$ can now be
bounded as (Wainwright,, 2019, Corollary 14.5)

$\delta_{n,\mathcal{H}_{1}}^{2}\lesssim\frac{\|\hat{h}_{n}\|_{\infty}^{2\alpha}J_{n}}{n}.$
(79)

  2. 2.

We now derive approximation and estimation bounds for $\mathcal{I}$. We first
remark on the full symmetry of our previous results: as proved in Claim B.1,
$E^{\top}$ is the symmetric conditional expectation operator from
$L_{2}(P_{z})$ to $L_{2}(P_{x})$. Thus, all results in Section 3 and Section
4.1, as well as Proposition E.1, apply to $\mathcal{I}$, with all occurrences
of $z,x$ exchanged, $\bar{\mathcal{H}}_{{\alpha}}$ replaced by the following
(series of) RKHS

$\bar{\mathcal{I}}_{\alpha}:=\operatorname{Ran}(EE^{\top})^{\alpha/2},~{}\|g\|_{\bar{\mathcal{I}}_{\alpha}}:=\|(EE^{\top})^{-\alpha/2}g\|_{2},$
(80)

and $\hat{h}_{n},h_{0}$ replaced by

$\hat{h}_{n}^{*}(x,z):=\hat{h}_{n}(z,x),~{}~{}h_{0}^{*}(x,z):=h_{0}(z,x)=\frac{dP_{xz}}{d(P_{x}\otimes
P_{z})}(z,x).$

As $\|\hat{h}_{n}^{*}-h_{0}^{*}\|_{L_{2}(P_{x}\otimes
P_{z})}=\|\hat{h}_{n}-h_{0}\|_{L_{2}(P_{z}\otimes
P_{x})}\leq\epsilon_{n}^{2}$, we can invoke the symmetric version of
Proposition E.1 (with $\alpha\leftarrow\alpha^{\prime}=1$), showing that on an
event with $\mathcal{D}^{(n)}_{2}$-probability $\geq 1-n^{-11}$, the kernel
$k_{z}$ has integral operator $T_{z}=:\tilde{T}_{z}^{\alpha^{\prime}}$, where
$\tilde{T}_{z}$ satisfy

$\|E^{\top}g\|_{2}-\epsilon^{\prime}_{n}\leq\|\tilde{T}_{z}^{1/2}g\|_{2}\leq\|E^{\top}g\|_{2}+\epsilon^{\prime}_{n}~{}~{}~{}~{}\text{for
all
}\|g\|_{2}=1,~{}~{}\text{where}~{}\epsilon^{\prime}_{n}:=\epsilon_{n}+\mathcal{O}\Big{(}\|\hat{h}_{n}\|_{\infty}^{2}\frac{J_{n}+\log
n}{n}\Big{)}.$ (81)

We also condition on the above event in the remainder of the proof. As (81)
fulfills (11’), the symmetric version of Lemma C.1 (i) implies that

$\forall
g\in\bar{\mathcal{I}}_{1},~{}~{}\exists\tilde{g}\in\mathcal{I}~{}~{}s.t.~{}~{}\|\tilde{g}\|_{\mathcal{I}}\lesssim\|g\|_{\bar{\mathcal{I}}_{1}},~{}\|\tilde{g}-g\|_{2}\lesssim\epsilon_{n}^{\prime}\|g\|_{\bar{\mathcal{I}}_{1}}.$
(82)

By (12’), for all $f\in\mathcal{H}$, there exists

$\bar{f}\in\bar{\mathcal{H}}_{{\alpha}},~{}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\alpha}}}\lesssim\|f\|_{\mathcal{H}},~{}\|E(\bar{f}-f)\|_{2}\overset{\eqref{eq:basic-
facts}}{\leq}\|\bar{f}-f\|_{2}\lesssim\epsilon_{n}^{\prime}\|f\|_{\mathcal{H}}.$

By definitions, we have

$\|E\bar{f}\|_{\bar{\mathcal{I}}_{1}}\leq\|E\bar{f}\|_{\bar{\mathcal{I}}_{2}}=\|\bar{f}\|_{\bar{\mathcal{H}}_{{1}}}\leq\|\bar{f}\|_{\bar{\mathcal{H}}_{{\alpha}}}.$

Instantiating (82) with $g\leftarrow E\bar{f}\in\bar{\mathcal{I}}_{\alpha}$
and combining with the above displays establish the existence of
$g_{f}\in\mathcal{I}$ s.t.

$\|g_{f}\|_{\mathcal{I}}\lesssim\|E\bar{f}\|_{\bar{\mathcal{I}}_{1}}\leq\|\bar{f}\|_{\bar{\mathcal{H}}_{{\alpha}}}\lesssim\|f\|_{\mathcal{H}},~{}~{}\|Ef-
g_{f}\|_{2}\leq\|E(f-\bar{f})\|_{2}+\|g-g_{f}\|_{2}\lesssim\epsilon_{n}^{\prime}\|f\|_{\mathcal{H}}.$

Applying the above display to $f\leftarrow f-\tilde{f}_{n}$, we find, for all
$f\in\mathcal{H}$, the existence of $g_{f}^{\prime}\in\mathcal{I}$ s.t.

$\|g_{f}^{\prime}\|_{\mathcal{I}}\lesssim\|f-\tilde{f}_{n}\|_{\mathcal{H}},\|g_{f}^{\prime}-E(f-f_{0})\|_{2}\leq\|g_{f}^{\prime}-E(f-\tilde{f}_{n})\|_{2}+\|\cancel{E(}\tilde{f}_{n}-f_{0}\cancel{)}\|_{2}\lesssim\epsilon_{n}^{\prime}(\|f-\tilde{f}_{n}\|_{\mathcal{H}}+\|f_{0}\|_{\bar{\mathcal{H}}_{{\alpha}}}),$
(83)

where the last inequality also uses (77). This establishes the approximation
conditions. For estimation, observe

$\sup_{z\in\mathcal{Z}}k_{z}(z,z)=\sup_{z\in\mathcal{Z}}\hat{\Phi}_{n}(z)^{\top}\hat{\Sigma}_{x}\hat{\Phi}_{n}(z)=\sup_{z\in\mathcal{Z}}\frac{1}{n}\sum_{i=1}^{n}\hat{\Phi}_{n}(z)^{\top}\hat{\Psi}_{n}(x_{i}^{s})\hat{\Psi}_{n}(x_{i}^{s})^{\top}\hat{\Phi}_{n}(z)\leq\|\hat{h}_{n}\|_{\infty}^{2}.$
(84)

Since $k_{z}$ also has rank $J_{n}$, the product function space $\mathcal{G}$
defined in Dikkala et al., (2020, Eq. 2, see also App. E.2) is an RKHS with
dimensionality $J_{n}^{2}$, and has its critical radius trivially bounded as

$\delta_{n,\mathcal{G}}^{2}\lesssim\frac{\|\hat{h}_{n}\|_{\infty}^{\cancel{2\vee}2\alpha}J_{n}^{2}}{n}.$
(85)

  3. 3.

Combining (77), (79), (83), (85) fullfills the condition of Dikkala et al.,
(2020, Theorem 1), which now states that for

$\nu_{n}\asymp\lambda_{n}\asymp\frac{\|\hat{h}_{n}\|_{\infty}^{2\alpha}J_{n}^{2}}{n}+\epsilon_{n}^{\prime
2},$ (86)

we have, with probability $\geq 1-n^{-11}$ w.r.t. the samples used to estimate
$\hat{f}_{n}$,

$\|E(\hat{f}_{n}-f_{0})\|_{2}^{2}\lesssim\Big{(}\frac{\|\hat{h}_{n}\|_{\infty}^{2\alpha}J_{n}^{2}}{n}+\epsilon_{n}^{\prime
2}\Big{)}(1+\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{4})+\frac{\log
n}{n}\lesssim\Big{(}\frac{\|\hat{h}_{n}\|_{\infty}^{2\alpha}J_{n}^{2}}{n}+\epsilon_{n}^{2}\Big{)}(1+\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{4})+\frac{\log
n}{n}=:\tilde{\epsilon}_{n}^{2}.$

Now, Theorem 3.1 implies that

$\|\hat{f}_{n}-f_{0}\|_{2}^{2}=\mathcal{O}\big{(}\tilde{\epsilon}_{n}^{2}+\tilde{\epsilon}_{n}^{2\alpha}+\tilde{\epsilon}_{n}^{2\alpha/(\alpha+1)}\big{)}=\mathcal{O}\Big{(}\Big{(}\epsilon_{n}+\Big{(}\frac{\|\hat{h}_{n}\|_{\infty}^{2\alpha}J_{n}^{2}+\log
n}{n}\Big{)}^{\frac{1}{2}}\Big{)}(1+\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{2})\Big{)}^{\frac{2\alpha}{\alpha+1}}.$

This proves (76), which holds with probability $\geq 1-\zeta_{n}-2n^{-11}$.

It remains to prove the claim (ii). By Proposition E.3 (for $\alpha=1$) or
Corollary E.1 (for $\alpha=2$), on a
$(\mathcal{D}^{(n)}_{1},\mathcal{D}^{(n)}_{2})$-measurable event w. p. $\geq
1-3n^{-11}$, we have (12), (12’) and (14) hold, and

$\epsilon_{n}^{2}=\tilde{\mathcal{O}}\bigl{(}n^{-\frac{(p-2)(2p-1)}{(p-1)(2p+1)}}\bigr{)},~{}~{}\|\hat{h}_{n}\|_{\infty}=\tilde{\mathcal{O}}(1).$

The proof completes by plugging the above to (76), and observing that
$(2p-1)(p-2)/(2p+1)(p-1)\leq 4(p-2)/(4p+1)$ when $p>2$. ∎

####  F.2 Additional Discussion

##### Adaptivity

Theorem 4.1 quantified the $L_{2}$ error for conditional moment models under
assumptions on the source condition ($\beta\geq 1$), and the singular value
spectrum $\\{\bar{s}_{i}\\}$, under the compositional data generating process
Example 2.1. While we can cast any data generating process into this setup by
setting
$\bar{\mathbf{z}}\leftarrow\mathbf{z},\bar{\mathbf{x}}\leftarrow\mathbf{x}$,
the situation becomes more interesting when the observed
$(\mathbf{x},\mathbf{z})$ contains additional information, i.e., when we can
recover high-dimensional $(\mathbf{x}_{\perp},\mathbf{z}_{\perp})$ using
$(\mathbf{x},\mathbf{z})$. As we noted in Section B.2, in such settings, the
singular value spectrum of $E$ coincides with that of a latent-space
conditional expectation operator $\bar{E}$, defined by
$(\bar{\mathbf{z}},\bar{\mathbf{x}})$; and when $f_{0}$ satisfies (5), the
best possible value for $\beta$ is also determined solely by the regularity of
a latent-space function $\bar{f}_{0}$, which defines $f_{0}$ through

$f_{0}=\bar{f}_{0}\circ f_{enc,x}.$

In aggregate, the quantified rate is adaptive to such latent variable
structures, and is independent of the possibly high-dimensional variables
$(\bar{\mathbf{x}}_{\perp},\bar{\mathbf{z}}_{\perp})$ which represents
redundant information. Such results cannot be established for estimators based
on fixed-form kernels; for example, under the setup of Theorem 4.1,
$\bar{f}_{0}$ will satisfy
$\bar{f}_{0}\in\mathrm{Ran}(\bar{E}^{\top}\bar{E})^{\frac{\alpha}{2}}=W_{per}^{\alpha
pd_{l},2}\subset W^{\alpha pd_{l},2}$ (see Ex. 2.2, and derivation in App.
B.2). Across all possible $f_{enc,x}\in\mathcal{C}^{\beta_{d}}$ as assumed in
the theorem, we can only have $f_{enc,x}\in
W^{\beta_{d}+\frac{d_{obs}}{2},2}$, due to the Sobolev embedding theorem, and
thus $f_{0}=\bar{f}_{0}\circ f_{enc,x}\in W^{r,2}$, with161616 Recall our
convention (Appendix A) of using $E$ to also refer to a map between functions,
as opposed to mere $L_{2}$ equivalence classes.

$r=\min\Big{\\{}\alpha
pd_{l},\beta_{d}+\frac{d_{obs}}{2}\Big{\\}}=\min\Big{\\{}pd_{l},\beta_{d}+\frac{d_{obs}}{2}\Big{\\}},$

where $\beta_{d}\geq(p-2)d_{obs}$ as assumed in the theorem. Consequently, for
a Matérn-$\alpha^{\prime}$ RKHS, which is equivalent to
$W^{\frac{2\alpha^{\prime}+d_{obs}}{2},2}$ (see _e.g._ , Kanagawa et al.,,
2018), to contain $f_{0}$, we must have

$\alpha^{\prime}+\frac{d_{obs}}{2}\leq r\leq pd_{l}.$

This can become impossible when $d_{obs}\geq 2pd_{l}-1$, a realistic scenario
when $d_{obs}\gg d_{l}$. In contrast, our established result (LABEL:eq:cmm-
concrete-claim) is unaffected by this condition. More generally, there will
always exist regimes of $(p,d_{l},d_{obs})$, in which nonparametric models
that can only utilize differentiability conditions of $f_{0}$ will suffer from
the curse of dimensionality, whereas the learned kernel enjoys dimension-
independent guarantees.171717 Formal separability results can also be
established by comparing the established rate for
$\|E(\hat{f}_{n}-f_{0})\|_{2}$ with a nonparametric regression rate.  The
improvement comes from the established adaptivity of DNN models (Schmidt-
Hieber,, 2020).

##### Choices of $\mathcal{I}$, technical restrictions

The theorem uses the kernel (21) with $\alpha^{\prime}\leftarrow\alpha$. As
noted in the proof, this approximates a kernel with integral operator

$(EE^{\top})^{\alpha^{\prime}}=E(E^{\top}E)^{\alpha^{\prime}-1}E^{\top}.$

In general, kernels with integral operator having the form $ET_{x}E^{\top}$
are “optimal” first-stage models for $\mathcal{H}$ defined with $T_{x}$ (Wang
et al.,, 2022); this is a generalization of the concept of optimal linear
instrument (Chamberlain,, 1987). Thus, as noted in the text, a choice of
$\alpha^{\prime}\leftarrow\alpha+1$ would have approximated the optimal kernel
for $\mathcal{H}$. Our restrictions of $\alpha^{\prime}=\alpha$ and $\alpha=1$
are both due to Proposition E.1, which bounds the extra error incurred by
using plug-in estimates for the kernels (e.g., (19’) in place of (19)), but
only applies to $\alpha^{\prime}=\alpha=1$. It is unclear if this is merely a
technical artifact,181818 We note that the proof of the theorem can be
modified to establish a similar rate using the population counterpart of (21),
for $\alpha^{\prime}=\alpha+1$. We may also replace $k_{z}$ with the
construction of Wang et al., (2022), but this introduces additional
assumptions.  but in any case, our results are best viewed as a proof-of-
concept that demonstrates qualitatively desirable properties (_e.g._ ,
adaptivity). The experiments will evaluate other choices of
$(\alpha,\alpha^{\prime})$, and test other deviations from the conditions in
the theorem.

###  Appendix G Experiment Setup and Additional Results

####  G.1 Synthetic Experiment

We first evaluate our method in a more controlled setting which is consistent
with our running example. Concretely, we consider a nonparametric IV (NPIV)
problem, where the observations $(\mathbf{z},\mathbf{x},\mathbf{y})$ are
generated using the process

$\displaystyle\bar{\mathbf{z}}$
$\displaystyle\sim\mathcal{N}(0,1),~{}\bar{\mathbf{u}}\sim\mathcal{N}(0,1),~{}\bar{\mathbf{x}}:=\rho\bar{\mathbf{z}}+\sqrt{1-\rho^{2}}\bar{\mathbf{u}},~{}(\mathbf{z}_{\perp};\mathbf{x}_{\perp})\sim\mathcal{N}(0,I_{2(d-1)\times
2(d-1)}),$ $\displaystyle\mathbf{x}$
$\displaystyle:=f_{dec,x}(\bar{\mathbf{x}},\mathbf{x}_{\perp}),~{}\mathbf{z}:=f_{dec,z}(\bar{\mathbf{z}},\mathbf{z}_{\perp}),~{}\bar{\mathbf{y}}\sim\mathcal{N}(f_{0}(\bar{\mathbf{x}})+2\mathbf{u},0.01),~{}\mathbf{y}:=s_{y}^{-1}(\bar{\mathbf{y}}-m_{y}).$

In the above, $f_{dec,x},f_{dec,z}$ are chosen as randomly initialized MLPs
with two hidden layers and output dimensionality $2d$, $f_{0}$ is chosen as
the absolute value function, and the constants $s_{y},m_{y}$ are chosen to
standardize $\mathbf{y}$. This setup generalizes the low-dimensional
simulations used in a thread of NPIV works starting from Lewis and Syrgkanis,
(2018).

As the latent variables $(\bar{\mathbf{x}},\bar{\mathbf{z}})$ follow a
multivariate normal distribution, it is well known that the singular vectors
of the “latent space conditional expectation operator”,
$\bar{E}:L_{2}(P_{\bar{x}})\to L_{2}(P_{\bar{z}})$, are the scaled Hermite
polynomials, and its $j$-th singular value equals $\rho^{j}$; as we discussed
in Section B.2, $E$ and $\bar{\mathcal{H}}_{{\alpha}}$ are also defined
accordingly, provided that there exist the functions
$f_{enc,x}:x\mapsto\bar{x},f_{enc,z}:z\mapsto\bar{z}$.191919 While we do not
explicitly ensure their existence in the design, empirically we find it
possible to reconstruct $\bar{\mathbf{x}},\bar{\mathbf{z}}$ using the observed
$\mathbf{x},\mathbf{z}$.  And the $\chi^{2}$ divergence equals
$\frac{\rho^{2}}{1-\rho^{2}}$.

We are interested in the convergence of the spectral decomposition error
$\epsilon_{n}^{2}=\mathcal{D}(h_{0})-\mathcal{D}(\hat{h}_{n})$, and the NPIV
estimation error $\|\hat{f}_{n}-f_{0}\|_{2}^{2}$ using the learned kernel. For
the former, we compare $\mathcal{D}(\hat{h}_{n})$ with the $\chi^{2}$
divergence which it should converge to (Lemma 4.1), and an estimate of the
divergence

$\hat{\mathcal{D}}_{\chi^{2},n^{\prime}}:=\frac{1}{n^{\prime}}\sum_{i=1}^{n^{\prime}}(h_{0}(z_{i}^{\prime},x_{i}^{\prime})-1)^{2}.$
(87)

We compare with (87) since due to the light tail of the Gaussian distribution,
finite-sample estimates of the $\chi^{2}$ divergence may converge slowly,
especially when $\rho$ is large. For the NPIV error, we compare it with the
kernelized IV estimator (Dikkala et al.,, 2020) instantiated with a fixed-form
RBF kernel. This is only provided for the reader’s convenience, and more
baselines are included in the more realistic semi-synthetic experiment in the
following.

(a) $\rho=0.5,d=1$ (b) $\rho=0.7,d=1$ (c) $\rho=0.9,d=1$ (d) $\rho=0.7,d=1$
(e) $\rho=0.7,d=2$ (f) $\rho=0.7,d=10$

Figure 3: Synthetic experiment: estimated lower bound of
$\mathcal{D}_{\chi^{2}}[P_{zx}\|P_{z}\otimes P_{x}]$ using the learned
$\hat{h}_{n}$. Error bar denotes the $20\%$ and $80\%$ percentile across $10$
independent runs.

We vary $d\in\\{1,2,10\\},\rho\in\\{0.5,0.7,0.9\\}$ and
$n\in\\{1,2,4,8,16\\}\times 10^{3}$. For the estimation of $\hat{h}_{n}$, we
parameterize $h(z,x)=\Phi(z)^{\top}\Psi(x)$ using $4$-layer MLPs for both
$\Phi$ and $\Psi$, with Swish activation and width of $50$, and apply dropout
regularization with a rate of $0.2$. The NN model is trained with AdamW, with
a learning rate of $10^{-3}$ and batch size of $512$. We have experimented
with a variety of NN architecture and training hyperparameters and selected
this configuration by evaluating the training objective on held-out samples.
We conduct early stopping, and determine the value of $J_{n}\in\\{10,20,30\\}$
by the same validation procedure. For IV estimation, we use plug-in estimates
for the kernels (19’) and (21), and select
$\alpha\in\\{0.5,1,2,3\\},\lambda_{n}\in[0.5,2],\nu_{n}\in[0.5,2]$ using the
validation protocol of Singh et al., (2019); Muandet et al., 2020b . For the
RBF baseline, we also select the bandwidth of $k_{x}$ in
$\\{0.5,1,1.5\\}\times\mathrm{med}_{x}$, and $k_{z}$ in
$\\{1,2,3\\}\times\mathrm{med}_{z}$ using the same protocol. Note that RBF
kernels with varying bandwidths form a similar Hilbert scale (e.g., Steinwart
and Christmann,, 2008). Both methods observe a total of $2n$ samples, and are
tested on a separate set of $n^{\prime}=5n$ samples.

(a) $\rho=0.5,d=1$ (b) $\rho=0.7,d=1$ (c) $\rho=0.9,d=1$ (d) $\rho=0.7,d=1$
(e) $\rho=0.7,d=2$ (f) $\rho=0.7,d=10$

Figure 4: Synthetic experiment: IV estimation error
$\|\hat{f}_{n}-f_{0}\|_{2}^{2}$ using learned and fixed-form kernels. Error
bar denotes the $20\%$ and $80\%$ percentile across $10$ independent runs.

The results are shown in Figure 3-4. As we can see, the estimated density
ratio $\hat{h}_{n}$ approaches the ground truth as sample size increases, and
leads to accurate estimates for the $\chi^{2}$ divergence when $d$ and $\rho$
have moderate values. Obviously, estimation will become more difficult as $d$
increases; this is also the case for increasing $\rho$, in which case the
trailing eigenfunctions become more relevant in the $\chi^{2}$ divergence. As
for IV estimation, the learned kernel leads to better estimates when $d$ is
large, as we would expect given the discussion in Section F.2. It is
interesting that it also outperforms the fixed-form kernel when $d=1$, i.e.,
when no redundant latent features are present, which suggests the method may
also be useful in more classical, low-dimensional settings.

####  G.2 Proxy Control Experiment

We now turn to the proxy control experiment. Our setup is adapted from
Mastouri et al., (2021), based on which we modify the proxy variables as
follows: denote by $\bar{\mathbf{v}},\bar{\mathbf{w}}$ the low-dimensional
proxy variables in Mastouri et al., (2021); our observed proxies are generated
as

$\mathbf{v}:=f_{dec,v}(\bar{\mathbf{v}},\mathbf{v}_{\perp}),~{}\mathbf{w}:=f_{dec,w}(\bar{\mathbf{w}},\mathbf{w}_{\perp}),~{}~{}~{}\text{where}~{}\mathbf{v}_{\perp}\sim\mathcal{N}(0,I)\in\mathbb{R}^{D_{ex}},~{}\mathbf{w}_{\perp}\sim\mathcal{N}(0,I)\in\mathbb{R}^{D_{ex}}$

are independent of all other variables, and $f_{dec,v},f_{dec,w}$ are randomly
initialized neural networks with two hidden layers, and output dimensionality
$4$ times the input dimensionality. The other data variables are kept
unchanged. We vary $D_{ex}\in\\{0,4,32,256\\},N\in\\{1000,2000,4000,8000\\}$.

For our method, we employ a tensor product kernel described in Section 4.3,
where $k_{w}$ is an RBF kernel with bandwidth determined by the median trick;
the other hyperparameters are determined as in Section G.1. For the RBF
baseline, we use RBF kernels, with bandwidth determined from the same grid as
in Section G.1, using the same protocol. For the AGMM-NN baseline, we vary the
learning rates in $\\{5,10,50\\}\times 10^{-4}$ and $L^{2}$ regularization in
$\\{5,10\\}\times 10^{-5}$, and report the configuration that attains the best
median MSE. For all configurations, we repeat the experiment for $10$ times
and report the $25\%,50\%$, and $75\%$ percentile of the test MAE. All methods
observe a total of $2N$ samples.

The results are shown in Table 1, Fig. 2 in the text, and Fig. 5 below. As we
can see, the proposed method outperforms other baselines in most settings and
becomes especially competitive as the dimensionality of the observed proxy
variables increases.

Figure 5: Proxy experiment: test MAE for varying $n$, and
$D_{ex}\in\\{0,4\\}$.