minitoc *off

Spectral Representation Learning for Conditional Moment Models

Ziyu Wang Yucen Luo Yueru Li

Tsinghua University Max Planck Institute for Intelligent Systems Tsinghua
University

Jun Zhu Bernhard Schölkopf

Tsinghua University Max Planck Institute for Intelligent Systems

###### Abstract

Many problems in causal inference and economics can be formulated in the
framework of conditional moment models, which characterize the target function
through a collection of conditional moment restrictions. For nonparametric
conditional moment models, efficient estimation often relies on preimposed
conditions on various measures of ill-posedness of the hypothesis space, which
are hard to validate when flexible models are used. In this work, we address
this issue by proposing a procedure that automatically learns representations
with controlled measures of ill-posedness. Our method approximates a linear
representation defined by the spectral decomposition of a conditional
expectation operator, which can be used for kernelized estimators and is known
to facilitate minimax optimal estimation in certain settings. We show this
representation can be efficiently estimated from data, and establish $L_{2}$
consistency for the resulting estimator. We evaluate the proposed method on
proximal causal inference tasks, exhibiting promising performance on high-
dimensional, semi-synthetic data.

$\scriptstyle\mathbf{Z}$$\scriptstyle\mathbf{X}$$\scriptstyle\mathbf{Y}$$\scriptstyle\mathbf{U}$

(a) Instrumental variable.

$\scriptstyle\mathbf{V}$$\scriptstyle\mathbf{U}$$\scriptstyle\mathbf{W}$$\scriptstyle\mathbf{T}$$\scriptstyle\mathbf{Y}$

(b) Proximal causal inference.

$\scriptstyle\mathbf{\bar{\mathbf{V}}}$$\scriptstyle\mathbf{U}$$\scriptstyle\bar{\mathbf{W}}$$\scriptstyle\mathbf{T}$$\scriptstyle\mathbf{Y}$$\scriptstyle\mathbf{V}$$\scriptstyle\mathbf{W}$

(c) Causal inference with high-dimensional observed proxies.

Figure 1: Sample causal graphs for various conditional moment models.

###  1 INTRODUCTION

Many problems in causal inference and statistics can be formulated in the
framework of _conditional moment models_ (CMMs), where the goal is to

$\text{find $f_{0}$
s.t.}~{}~{}\mathbb{E}(f_{0}(\mathbf{x})-\mathbf{y}\mid\mathbf{z})=0~{}\text{a.s.}~{}[P(dz)].$
(1)

Examples include instrumental variable (IV) regression (Wright,, 1928), where
$\mathbf{x},\mathbf{y},\mathbf{z}$ denote the treatment, outcome and
instruments (Fig. 1 a); proximal causal inference (Miao et al.,, 2018;
Tchetgen Tchetgen et al.,, 2020)), where $\mathbf{x},\mathbf{z}$ are obtained
by concatenating the treatment variable and two proxy variables of the
unobserved confounder (Fig. 1 b); and various problems in reinforcement
learning where similar instruments or proxies can be found (e.g., Chen et
al.,, 2021; Li et al., 2021a, ; Shi et al.,, 2022).

For nonparametric models, estimation of (1) usually relies on minimizing
estimable surrogates for an averaged violation of the conditional moment
restrictions,

$f\mapsto\mathbb{E}(\mathbb{E}(f(\mathbf{x})-\mathbf{y}\mid\mathbf{z})^{2}).$
(2)

It is relatively easy to establish finite-sample guarantees for (2), using
statistical learning theory techniques. However, nonparametric CMMs are
typically ill-posed (Kress et al.,, 1989), meaning that approximate
minimization of (2) cannot guarantee approximate recovery of $f_{0}$ in more
intuitive criteria, such as the $L_{2}$ norm, i.e., the root mean squared
error _over $\mathbf{x}$_. Such distinctions between identifiability and
estimability are ubiquitous in nonlinear causal problems (Horowitz,, 2014;
Maclaren and Nicholson,, 2020).

A standard approach for establishing uniform $L_{2}$ convergence is to impose
assumptions on certain moduli of continuity (Chen and Pouzo,, 2012; Knapik and
Salomond,, 2017), which directly quantifies the maximum possible $L_{2}$ error
for functions that approximately optimize (2) or its surrogate and live in the
given hypothesis space. Unfortunately, such assumptions are rather opaque: as
we explain in Section 2, they require the complexity of the hypothesis space
to be related to that of the conditional expectation operator which defines
(1), which is usually unknown a priori. These assumptions are thus difficult
to justify, especially with flexible machine learning models using neural
networks, and hard, if not impossible, to verify empirically. Therefore, it is
highly desirable to develop methods that automatically learn hypothesis spaces
with well-controlled moduli of continuity.

This work is motivated to fill this crucial gap by learning linear
representations – kernels that are based on the spectral decomposition of the
conditional expectation operator. It is long known that estimation based on
the exact decomposition would be minimax optimal in a certain sense, as we
discuss in Section 2; but no guarantee has been established for the use of
approximate decompositions that can be learned from finite observations. We
prove that such decompositions can still define hypothesis spaces with well-
controlled moduli of continuity, and present a kernel learning algorithm for
an estimator of (1) that enables $L_{2}$-consistent estimation, with rates
adaptive to certain latent variables of the problem. When instantiated on the
problem of proximal causal inference, our method demonstrates competitive
performance on high-dimensional semi-synthetic datasets.

Our analysis reveals a quantitative benefit of the kernelized formulation of
IV/CMM estimation: as shown in Section 3.2, by learning the inner product
structure in addition to the basis of the linear representation space, we can
avoid the catastrophic sharp transition behavior, in which the modulus of
continuity, and thus the $L_{2}$ error, become unbounded once the spectral
decomposition error increases above an unobservable threshold. When working
with learned kernels, the measure degrades gracefully. This is interesting
because although kernelized estimators generalize the classical sieve methods,
in past works on estimation with fixed-form representations, the theoretical
benefits of kernelized methods have been less transparent: for instance, both
approaches attain the same minimax rate (Chen and Reiss,, 2007; Wang et al.,
2021a, ).

Spectral decomposition is an important problem on its own, for which various
procedures have been proposed (Pfau et al.,, 2020; Klus et al.,, 2020; Gemp et
al.,, 2020; Deng et al., 2022b, ). We improve the understanding of this
problem by showing that faster rates of convegence can be achieved through a
contrastive learning procedure, which maximizes a variational formulation of
an $f$-divergence. This is different from existing methods based on NN models,
which not only lack the faster rate guarantees but also require more
computationally expensive bi-level optimization.

The rest of this paper is organized as follows: Section 2 reviews background
knowledge and sets up a running example. In Section 3 we establish abstract
guarantees for kernels derived from approximate spectral decompositions. In
Section 4 we construct an algorithm that fulfills the abstract criterion, and
establish $L_{2}$ consistency for the resulted estimator of (1). We review
related work in Section 5 and evaluate our method experimentally in Section 6.
Finally, we discuss the conclusion and future work in Section 7.

###  2 NOTATION AND SETUP

##### Notations

We use $P_{z},P_{x},P_{zx}$ to denote marginal data distributions of the
corresponding covariate(s), and $P_{z}\otimes P_{x}$ denotes the product
measure. For functions $f,g$ of any covariate(s), $\langle f,g\rangle_{2}$
denotes the $L_{2}$ inner product w.r.t. the respective data distribution. For
finite-dimensional vectors, $\langle\cdot,\cdot\rangle_{2}$ denotes the
Euclidean inner product. $\|\cdot\|_{2}$ denotes the induced norm.
$\operatorname{Ran}(\cdot)$ denotes the range of an operator. $\asymp$ denotes
equivalence up to multiplicative constants.

##### Conditional moment models

We first consider estimation problems in (1), which defines a continuum of
moment restrictions indexed by $z$. To derive an estimation objective, we
observe that an averaged violation of the moment restrictions, Eq. (2), can be
estimated from data:

$\displaystyle\phantom{=}\mathbb{E}(\mathbb{E}(f(\mathbf{x})-\mathbf{y}\mid\mathbf{z})^{2})$
$\displaystyle=\sup_{g\in
L_{2}(P_{z})}\mathbb{E}(2\mathbb{E}(f(\mathbf{x})-\mathbf{y}\cancel{\mid\mathbf{z}})g(\mathbf{z}))-\mathbb{E}(g^{2}(\mathbf{z}))$
$\displaystyle\approx\sup_{g\in\mathcal{I}}\frac{1}{n}\sum_{i=1}^{n}2\left(f\left(x_{i}\right)-y_{i}\right)g(z_{i})-g^{2}(z_{i}).$

In the above, $(x_{i},y_{i},z_{i})$ are i.i.d. data samples, and
$\mathcal{I}\subset L_{2}(P_{z})$ denotes a smaller space in which the
optimization can be implemented; the equality follows by a basic property of
the inner product space $L_{2}(P_{z})$, and the tower property. As the left-
hand side equals zero if and only if $f$ satisfies (1), an estimator
$\hat{f}_{n}$ can be derived:

$\displaystyle\hat{f}_{n}:=\arg\min_{f\in\mathcal{H}}\sup_{g\in\mathcal{I}}$
$\displaystyle\>\frac{1}{n}\sum_{i=1}^{n}\big{(}2(f(x_{i})-y_{i})g(z_{i})-g^{2}(z_{i})\big{)}$
$\displaystyle-\nu_{n}\|g\|_{\mathcal{I}}^{2}+\lambda_{n}\|f\|_{\mathcal{H}}^{2},$
(3)

where $\mathcal{H}$ is the hypothesis space. This type of estimator has been
proposed in Lewis and Syrgkanis, (2018); Bennett et al., (2019); Liao et al.,
(2020); Muandet et al., 2020b , and is also related to the formulation of
Muandet et al., 2020a ; Zhang et al., (2020); see Section B.1 for details.
Dikkala et al., (2020) established fast-rate convergence for the unregularized
population objective (2); their results require $\mathcal{H},\mathcal{I}$ to
have small (local Rademacher) complexity and approximation overhead. To match
the classical minimax rates (Chen and Reiss,, 2007), however, additional
assumption on $\mathcal{H}$ must be imposed (Wang et al., 2021a, ).

While (3) requires two specific choices, the choice of $\mathcal{I}$ is easier
because the requirements imposed by Dikkala et al., (2020) are the same as
those in standard learning theory. Moreover, when $\mathcal{H}$ is a
reproducing kernel Hilbert space (RKHS), there exists an “optimal RKHS”
$\mathcal{I}$ that generalizes the notion of optimal instrument (Chamberlain,,
1987), and can be efficiently learned from data (Wang et al.,, 2022).

In contrast, the choice of $\mathcal{H}$ is more difficult, especially111 A
controlled modulus of continuity can also lead to improved bounds for the
population loss (Wang et al., 2021a, ).  if one wishes to establish $L_{2}$
convergence, because it is necessary to control quantities of the form

$\displaystyle\omega_{n}^{2}$
$\displaystyle:=\sup\\{\|f-f_{0}\|_{2}^{2}:f\in\mathcal{H},$
$\displaystyle\hskip
60.00009pt\mathbb{E}(\mathbb{E}(f(\mathbf{x})-\mathbf{y}\mid\mathbf{z})^{2})\leq\delta_{n}^{2}\\},$
(4)

which translates the learning theoretic guarantees for the population loss to
the $L_{2}$ error of interest. Such moduli of continuity are properties of
$\mathcal{H}$, and rely on the interaction between the complexity of
$\mathcal{H}$ and that of the conditional expectation operator

$E:L_{2}(P_{x})\to
L_{2}(P_{z}),~{}f\mapsto\mathbb{E}(f(\mathbf{x})\mid\mathbf{z}=\cdot),$

in a certain sense. In order to illustrate the interaction, suppose $E$ has
spectral decomposition
$E=\sum_{i=1}^{\infty}\bar{s}_{i}\bar{\phi}_{i}\otimes\bar{\psi}_{i},$ where
$\\{\bar{\phi}_{i}\\}\subset L_{2}(P_{z}),\\{\bar{\psi}_{i}\\}\subset
L_{2}(P_{x})$ are the singular vectors. Then
$\mathcal{H}=\mathrm{span}\\{\bar{\psi}_{i_{1}},\ldots,\bar{\psi}_{i_{J}}\\}$
has
$\omega_{n}^{2}/\delta_{n}^{2}=\max\\{\bar{s}_{i_{1}},\ldots,\bar{s}_{i_{J}}\\}$.
More generally, controlling the modulus of continuity requires $\mathcal{H}$
to have a stronger regularization effect in the subspace spanned by the
trailing singular vectors of $E$ while less information is known about $f_{0}$
in those directions. The requirement is nontrivial for models that are not
defined in accordance to $E$, especially for flexible models such as deep
neural networks.

##### CMM as an inverse problem

(1) is related to the following linear inverse problem (Hall and Horowitz,,
2005):

$\text{find $f_{0}$ s.t.}~{}~{}Ef_{0}=\hat{g}_{n},$ (1’)

where $\hat{g}_{n}$ is a “noisy observation” for
$g_{0}:=\mathbb{E}(\mathbf{y}\mid\mathbf{z}=\cdot)$. We can assume access to
such $\hat{g}_{n}$ because relevant information about $g_{0}$ can be estimated
from data. If the operator $E$ were known, (1’) reduces to a standard linear
inverse problem, for which a common approach is to find an inner product space
$\mathcal{H}$ that well approximates $f_{0}$, and to solve the regularized
problem:

$\displaystyle\hat{f}_{n}$
$\displaystyle:=\arg\min_{f\in\mathcal{H}}\|Ef-\hat{g}_{n}\|^{2}_{2}+\lambda_{n}\|f\|_{\mathcal{H}}^{2}$
(3’)
$\displaystyle\phantom{:}=\arg\min_{f\in\mathcal{H}}\|Ef-\hat{g}_{n}\|^{2}_{2}+\lambda_{n}\|T^{-1/2}f\|_{2}^{2},$

where $T:L_{2}(P(dx))\to L_{2}(P(dx))$ is a self-adjoint operator that
characterizes the inner product $\langle\cdot,\cdot\rangle_{\mathcal{H}}$.
(3’) is closely related to (3), which also has its first term estimating
$\mathbb{E}(\mathbb{E}(f(\mathbf{x})-\mathbf{y}\mid\mathbf{z})^{2})=\|Ef-
g_{0}\|_{2}^{2}$.

The operator $T$ fully characterizes our prior knowledge about $f_{0}$. In
machine learning, such knowledge is often characterized by a kernel $k_{x}$,
which defines an RKHS (Schölkopf and Smola,, 2002). The two approaches are
often equivalent: for any $k_{x}$, setting $T$ to its $P_{x}$-integral
operator recovers the inner product structure of the corresponding RKHS;
conversely, for any self-adjoint, trace-class operator $T$, there exists an
RKHS that defines the same inner product as $\mathcal{H}$ (Steinwart and
Scovel,, 2012). Thus, the specification of a data-dependent $T$ can be
equivalently viewed as a kernel learning process.

As shown in our discussion about (1) earlier, the problem (1’) is also
typically ill-posed. Following the convention in the nonparametric literature
(e.g., Darolles et al.,, 2011; Chen and Pouzo,, 2012), we first assume the
variables $\mathbf{z}$ and $\mathbf{x}$ have no overlap, deferring the general
case to Section 4.3. Then, under mild regularity conditions, the operator $E$
is compact, and it is recognized that efficient estimation can be achieved if
$\mathcal{H}$ is defined in accordance to its SVD (Carrasco et al.,, 2007):
let $\\{\bar{\psi}_{j}\\}$ denote the sorted right singular vectors of $E$,
and $\beta>0$ be the largest number s.t. the source condition holds with
exponent $\beta$:

$f_{0}\in\operatorname{Ran}\,(E^{\top}E)^{\beta/2}.$ (5)

Then, rate-optimal estimation can be achieved by defining $\mathcal{H}$ with
$\bar{T}_{\alpha}=(E^{\top}E)^{\alpha}=\sum_{j=1}^{\infty}\bar{s}_{j}^{2\alpha}\bar{\psi}_{j}\bar{\psi}_{j}^{\top},$
for any $\alpha>0$, or by defining
$\mathcal{H}:=\mathrm{span}(\\{\bar{\psi}_{j}\\}_{j=1}^{J_{n}})$, for some
slowly growing $J_{n}$. The requirement of using the exact
$\\{\bar{\psi}_{j}\\}$ can be relaxed into a link condition (Chen and Reiss,,
2007). However, as will be explained in App. B.1 in more detail, all existing
approaches require a priori knowledge of inner product spaces of the form

$\bar{\mathcal{H}}_{{\alpha}}:=\operatorname{Ran}\,(E^{\top}E)^{\alpha/2},~{}\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}:=\|(E^{\top}E)^{-\frac{\alpha}{2}}f\|_{2}.$
(6)

This is a strong assumption, especially in high dimensions, because as we
demonstrate below, it requires knowledge of certain lower-dimensional latent
variables that explains all correlation structures between $\mathbf{x}$ and
$\mathbf{z}$.

We now set up the running example in this work, which also provides intuition
on the inductive bias of $\bar{\mathcal{H}}_{{\alpha}}$:

######  Example 2.1 (compositional model).

Let $\bar{\mathbf{x}},\bar{\mathbf{z}}$ be correlated random variables, and
$\mathbf{x}_{\perp},\mathbf{z}_{\perp}$ be s.t.
$\mathbf{x}_{\perp}\perp\\!\\!\\!\perp(\mathbf{z}_{\perp},\bar{\mathbf{x}},\bar{\mathbf{z}}),\mathbf{z}_{\perp}\perp\\!\\!\\!\perp(\mathbf{x}_{\perp},\bar{\mathbf{x}},\bar{\mathbf{z}})$.
Suppose there exist functions s.t.
$\mathbf{x}=f_{dec,x}(\bar{\mathbf{x}},\mathbf{x}_{\perp}),\mathbf{z}=f_{dec,z}(\bar{\mathbf{z}},\mathbf{z}_{\perp}),\bar{\mathbf{x}}=f_{fea,x}(\mathbf{x}),\bar{\mathbf{z}}=f_{fea,z}(\mathbf{z})$.

We can show that when $\alpha>0$, any $f\in\bar{\mathcal{H}}_{{\alpha}}$ must
have the form of $f=\bar{f}\circ f_{enc,x}$, meaning that $f$ only depends on
$\mathbf{x}$ through $\bar{\mathbf{x}}$; see App. B.2. Intuitively,
$(\bar{\mathbf{x}},\bar{\mathbf{z}})$ are informative latent variables that
explain all (nonlinear) correlations between $(\mathbf{x},\mathbf{z})$. For
all $f,f^{\prime}$ on suitable domains, we have

  1. (i)

Eq. 1 is equivalent to
$\mathbb{E}(f(\mathbf{x})-\mathbf{y}\mid\bar{\mathbf{z}})=0$.

  2. (ii)

In proxy control problems,
$\mathbb{E}(f(\mathbf{u})\mid\mathbf{x})=\mathbb{E}(f(\mathbf{u})\mid\bar{\mathbf{x}})$
and
$\mathbb{E}(f(\mathbf{u})\mid\mathbf{z})=\mathbb{E}(f(\mathbf{u})\mid\bar{\mathbf{z}})$.

  3. (iii)

$\mathbb{E}(f(\bar{\mathbf{x}})f^{\prime}(\mathbf{x}_{\perp})\mid\mathbf{z})=0$
whenver $\mathbb{E}(f^{\prime}(\mathbf{x}_{\perp}))=0$.

(ii) shows that in proxy control problems, $\bar{\mathbf{x}},\bar{\mathbf{z}}$
summarize all observable information about the latent confounder $\mathbf{u}$;
thus, they may have much lower dimensions than $\mathbf{x},\mathbf{z}$. As an
example, in the scenario of Fig. 1 (c) we can have
$\dim\bar{\mathbf{x}}\leq\dim\bar{\mathbf{v}}+\dim\mathbf{t}.$ For general
problems, (iii) shows that, under (1), any hypothesis $f_{0}(x)$ that is
falsifiable (Corfield et al.,, 2009) from data must depend on $\mathbf{x}$
only through $\bar{\mathbf{x}}$; additional components of the form
$f^{\prime}(\bar{\mathbf{x}})f^{\prime\prime}(\mathbf{x}_{\perp})$ will be
indistinguishable from noise. Thus, it is intuitive that
$\bar{\mathcal{H}}_{{\alpha}}$ may encode desirable inductive bias for
estimation. We provide additional discussion in App. B.2.

To provide further intuition on the regularity of
$\bar{\mathcal{H}}_{{\alpha}}$, we extend the example by combining it with the
classic torus example in literature (e.g., Chen and Reiss,, 2007):

######  Example 2.2 (compositional torus model).

In the setting of Ex. 2.1, let $\bar{\mathbf{z}}$ be uniformly distributed on
the torus $\mathbb{T}^{d_{l}}$, and $\bar{\mathbf{x}}\in\mathbb{T}^{d_{l}}$ be
s.t.

$\mathbb{E}(f(\bar{\mathbf{x}})\mid\bar{\mathbf{z}}=\bar{z})=\int_{0}^{1}\ldots\int_{0}^{1}\prod_{i=1}^{d_{l}}k(\bar{x}_{i}-\bar{z}_{i})f(\bar{x}_{i})d\bar{x}_{i},$

where $k$ is a 1-periodic even function. In words, $\bar{\mathbf{x}}$ is
obtained by adding to $\bar{\mathbf{z}}$ an independent noise. Its marginal
distribution is also uniform.

Let the $j$-th Fourier coefficient of $k$ be $c_{j}\asymp(1+j)^{-d_{l}p}$, for
some constant $p>0$. Then we have $\bar{s}_{j}\asymp j^{-p}$, and

$\bar{\mathcal{H}}_{{\alpha}}=\\{\bar{f}\circ f_{enc,x},\bar{f}\in W^{\alpha
pd_{l},2}_{per}\\},$

where $W^{\alpha pd_{l},2}_{per}$ denotes a periodic Sobolev space; when
$\alpha pd_{l}\in\mathbb{N}$, it is equivalent to the manifold Matérn RKHS
(Borovitskiy et al.,, 2020).

We note that a similar connection exists for (the manifold analogy of)
Gaussian noise, in which case the resulted space for $\bar{f}$ equals the
manifold Gaussian RKHS (De Vito et al.,, 2019).

###  3 BOUNDED ILL-POSEDNESS WITH LEARNED REPRESENTATIONS

As we reviewed in Section 2, knowledge of the exact SVD of $E$ would
facilitate sample-efficient estimation of (1). In reality, however, it is only
possible to approximately recover the SVD: we can only approximately optimize
certain variational objectives of it, as we can only observe $E$ indirectly
through the finite samples $\\{(z_{i},x_{i})\\}$. In this section, we show
that approximate optima of certain variational objective can still enable
efficient estimation of (1), and that thanks to the kernelized formulation of
conditional moment models, the estimation error can have a robust dependency
on the approximation quality for the SVD.

####  3.1 The Basis Learning View and a Catastrophic Transition of Estimation
Error

Before introducing our main results, let us first consider a _naïve approach_
that simply uses the learned singular vectors to define the basis of the
hypothesis space. The singular vector estimates $\\{\psi_{i}\\}_{i=1}^{J_{n}}$
can be parameterized with DNNs, and trained with the “variance explained”
formulation of SVD, so that for some $\epsilon_{n}\to 0$, it has

$\sum_{i=1}^{J_{n}}\|E\psi_{i}\|_{2}^{2}>\sum_{i=1}^{J_{n}}\|E\bar{\psi}_{i}\|_{2}^{2}-\epsilon_{n}^{2},$
(7)

Following this, we could define the learned hypothesis space as
$\mathcal{H}:=\mathrm{span}\\{\psi_{1},\ldots,\psi_{J_{n}}\\}$, and use it to
instantiate the classical sieve estimator (Chen and Reiss,, 2007).

An important limitation of this approach is that it does not learn an inner
product structure. While this did not affect convergence in the classical
setting where we had access to the exact singular vectors, it becomes
problematic now, as the learned $\\{\psi_{i}\\}$ can only be approximations in
the weak sense of (7). To see this, consider the $L_{2}$ error bound

$\displaystyle\|\hat{f}_{n}-f_{0}\|_{2}$
$\displaystyle\leq\left(\sup_{f\in\mathcal{H}}\frac{\|f-f_{0}\|_{2}}{\|E(f-f_{0})\|_{2}}\right)\|E(\hat{f}_{n}-f_{0})\|_{2}$
$\displaystyle=\|E\psi_{J_{n}}\|_{2}^{-1}\|E(\hat{f}_{n}-f_{0})\|_{2},$ (8)

where $\|E\psi_{J_{n}}\|_{2}^{-1}$ can be viewed as an ill-posedness measure.
It is easy to show that

$\|E\psi_{J_{n}}\|_{2}^{-1}<(\max\\{0,\|E\bar{\psi}_{J_{n}}\|_{2}^{2}-\epsilon_{n}^{2}\\})^{-1/2}.$
(9)

Observe that when $\epsilon_{n}^{2}\leq c\|E\bar{\psi}_{J_{n}}\|_{2}^{2}$ for
some $c<1$, both (9) and (8) can match the order of the respective bounds for
the exact basis $\\{\bar{\psi}_{j}\\}$. In this regime, these bounds can be
order-optimal, as we discuss in Example 3.1.

Unfortunately, the bound (9) blows up as
$\epsilon_{n}^{2}\to\|E\bar{\psi}_{J_{n}}\|_{2}^{2}$, yet it continues to be
tight. To see this, consider
$\\{\psi_{j}\\}:=\\{\bar{\psi}_{1},\ldots,\bar{\psi}_{J_{n}-1},\bar{\psi}_{J_{n}+M}\\}$,
and let $M\to\infty$. Thus, as soon as $\epsilon_{n}^{2}$ reaches
$\|E\bar{\psi}_{J_{n}}\|_{2}^{2}$, we lose any guarantee for
$\|E\psi_{J_{n}}\|_{2}^{-1}$ and subsequently the $L_{2}$ error. (We can
easily construct a sequence of approximate maxima for (2), for which
$\|f-f_{0}\|_{2}$ can get arbitrarily large.) This is in stark contrast to the
previous regime, and demonstrates a catastrophic transition behavior for this
naïve approach. It is especially concerning because without resorting to
extremely conservative choices of $J_{n}$, we cannot expect to estimate
$\epsilon_{n}^{2}$ or $\|E\bar{\psi}_{J_{n}}\|_{2}$ reliably from data; the
best we may hope for is to guarantee that $\epsilon_{n}^{2}$ is of an optimal
order of magnitude, which, due to the transition behavior, cannot provide any
guarantees on the estimation error.

####  3.2 Bounded Ill-posedness with Learned Kernels

The above pathology can be remedied, if we additionally learn to approximate a
carefully chosen inner product structure. Concretely, suppose $\mathcal{H}$
can be defined as

$\mathcal{H}:=\operatorname{Ran}\,\tilde{T}^{\alpha/2},~{}\|f\|_{\mathcal{H}}:=\|\tilde{T}^{-\alpha/2}f\|_{2},$
(10)

where the trace-class operator $\tilde{T}$ satisfies

$\tilde{T}:=\tilde{E}^{\top}\tilde{E},~{}~{}\text{where}~{}~{}\|\tilde{E}-E\|_{\mathrm{HS}}\leq\epsilon_{n},$
(11)

(11) is an intuitive error criterion for spectral decomposition; it also
implies (7) holds for the basis of $\mathcal{H}$ (see App. D.1). As we discuss
in App. C.1, it can be relaxed to provide further flexibility.

Let us provide some intuition for the learned inner product structure
$\langle\cdot,\cdot\rangle_{\mathcal{H}}$. From (10) and (11) we can see it
approximates that of (6), which can be viewed as weighing the $L_{2}$
orthonormal basis $\\{\bar{\psi}_{j}\\}$ using the singular values
$\bar{s}_{j}^{\alpha}$. Thus, we are imposing stronger regularization in
directions where (1’) or (1) provides less information about $f_{0}$.

We first present an approximation bound. In particular, it applies to $f_{0}$
satisfying (5).

######  Lemma 3.1 (Proof in App. C.1).

Let $\mathcal{H}$ be defined as above. Then, for any $\beta\geq\alpha$ and
$\bar{f}\in\bar{\mathcal{H}}_{{\beta}}$, there exists
$\tilde{f}\in\mathcal{H}$ s.t.

$\displaystyle\\!\\!\\!\\!\|\tilde{f}\|_{\mathcal{H}}\leq
c_{\alpha}\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}},\,\|\bar{f}-\tilde{f}\|_{2}\leq
c_{\alpha}\epsilon_{n}^{\min\\{\alpha,1\\}}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}},\\!$
(12)

where $c_{\alpha}$ is a universal constant determined by $\alpha$.

We now bound the modulus of continuity:

######  Theorem 3.1 (Proof in App. C.2).

Let $\mathcal{H},f_{0}$ be defined as above, $\tilde{f}\in\mathcal{H}$ be the
approximation to $f_{0}$ in Lem. 3.1, and
$\\{\delta_{n}\\},\\{\lambda_{n}\\}\subset\mathbb{R}_{+}$ be arbitrary
sequences of numbers. Then a “regularized moduli of continuity” satisfies

$\displaystyle\omega_{n}^{\prime 2}$
$\displaystyle:=\sup\\{\|f-f_{0}\|_{2}^{2}:f\in\mathcal{H},$
$\displaystyle\hskip
58.0001pt\|E(f-f_{0})\|_{2}^{2}+\lambda_{n}\|f\|_{\mathcal{H}}^{2}\leq\delta_{n}^{2}\\}$
(13)
$\displaystyle\phantom{:}=\mathcal{O}\big{(}\|\tilde{f}-f_{0}\|_{2}^{2}+(\lambda_{n}^{-\frac{1}{\alpha+1}}+\lambda_{n}^{-1}\epsilon_{n}^{2\alpha})\cdot$
$\displaystyle\hskip
43.00009pt(\delta_{n}^{2}+\lambda_{n}\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{2}+\|E(\tilde{f}-f_{0})\|_{2}^{2})\big{)}.$
(14)

Let us compare the result with (9), which also describes a measure of ill-
posedness. The above bound is less clean, as the approximation errors are
harder to separate. However, if we ignore it for the moment and restrict to
$\lambda_{n}\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{2}=\mathcal{O}(\delta_{n}^{2})$,
the measure of ill-posedness reduces to

$\frac{\omega_{n}^{\prime
2}}{\delta_{n}^{2}}=\mathcal{O}(\lambda_{n}^{-1/(\alpha+1)}+\lambda_{n}^{-1}\epsilon_{n}^{2\alpha}),$
(15)

which can be compared with (9). We can then instantiate (15) and (9) in the
context of our running example:

######  Example 3.1 (Ex. 2.2, continued).

Suppose $f_{0}$ satisfies (5) with $\beta={b}/{2p}$, $\alpha=\beta$, where
$b>0$ is any constant; and $\|E(\hat{f}_{n}-f_{0})\|_{2}$ can be order-
optimal. In such cases, the various quantities in the kernelized and sieve
estimators would satisfy (Chen and Reiss,, 2007; Wang et al., 2021a, )

$J_{n}\asymp n\lambda_{n}\asymp n\|E(\hat{f}_{n}-f_{0})\|_{2}^{2}\asymp
n^{1/(b+2p+1)}.$ (16)

Thus, if $\epsilon_{n}\leq Cn^{-{p}/{(b+2p+1)}}\asymp\bar{s}_{J_{n}}$, and the
constant $C$ is sufficiently small, both (9) and (15) would have the same
order, and lead to the minimax $L_{2}$ rate
$\|\hat{f}_{n}-f_{0}\|_{2}^{2}\leq\mathcal{O}(n^{-b/(b+2p+1)}).$ However, when
$C$ reaches $n^{p/(b+2p+1)}s_{J_{n}}=\mathcal{O}(1)$, the bound (9) will blow
up, whereas (15) continues to be order-optimal.

The above discussion is hypothetical, as it relies on $\epsilon_{n}^{2}$ and
$\|E(\hat{f}_{n}-f_{0})\|_{2}$ being optimized at a certain rate. As we
establish in App. E.1, The requirement on $\epsilon_{n}^{2}$ can often be met.
However, technicalities in constructing $\mathcal{I}$ will prevent us to match
the exact order of (16), and the rates we established for CMM will be slightly
worse. Nonetheless, the discussion provides valuable intuition that kernel
learning for CMM is a robust process, as the $L_{2}$ error degrades gracefully
as $\epsilon_{n}^{2}$ deteriorates.

###  4 SPECTRAL REPRESENTATION LEARNING FOR CMM

We now derive a spectral decomposition algorithm, which learns a linear
representation parameterized with DNNs, and fulfills the condition (11) with
high precision. While a number of approaches exist for spectral decomposition,
their statistical guarantees remain largely unclear. In this section, we first
establish that a contrastive learning algorithm, first proposed in HaoChen et
al., (2021) for self-supervised learning, allows us to establish fast-rate
convergence for the spectral decomposition problem, which in turn leads to
fast-rate bounds for (11). Using the learned representation and its
guarantees, we then establish $L_{2}$ error bounds for the CMM estimator (3).
Finally, we discuss the implementation of the complete algorithm.

####  4.1 Fast-Rate Spectral Representation Learning

HaoChen et al., (2021) employs the population objective

$\mathcal{D}({h}):=2\mathbb{E}_{P_{zx}}h(\mathbf{z},\mathbf{x})-\mathbb{E}_{P_{z}\otimes
P_{x}}h^{2}(\mathbf{z},\mathbf{x})-1$

which was motivated as minimizing (11) on finite neighbor graphs. We first
establish similar results in our setting, and provides more insights for the
objective:

######  Lemma 4.1 (Proof in Section D.1).

Let $J\in\mathbb{N},\epsilon_{n}>0$ be arbitrary. Let
$\Phi:\mathcal{Z}\to\mathbb{R}^{J},\Psi:\mathcal{X}\to\mathbb{R}^{J}$ be
arbitrary vector-valued functions, s.t. $h(z,x)=\Phi(z)^{\top}\Psi(x)$ is
$L_{2}(P_{z}\otimes P_{x})$-integrable. Define $(\tilde{E}f)(\cdot):=\int
f(x)h(\cdot,x)P(dx)$. Then we have

$\displaystyle\|\tilde{E}-E\|_{\mathrm{HS}}\leq\epsilon$
$\displaystyle\Leftrightarrow\mathcal{D}({h})\geq\mathcal{D}({h_{0}})-\epsilon_{n}^{2}$
$\displaystyle\Leftrightarrow\|h-h_{0}\|_{L_{2}(P_{z}\otimes
P_{x})}\leq\epsilon_{n},$ (17)

where $h_{0}:=\frac{dP_{zx}}{d(P_{z}\otimes P_{x})}$ is the Radon-Nikodym
derivative. And we have

$\displaystyle\sup_{h\in L_{2}(P_{z}\otimes P_{x})}\mathcal{D}({h})$
$\displaystyle=\mathcal{D}({h_{0}})=\mathcal{D}_{\chi^{2}}(P_{zx}\|P_{z}\otimes
P_{x})$ $\displaystyle=\mathrm{Tr}(E^{\top}E)-1.$ (18)

(17) above is a slight generalization of HaoChen et al., (2021, Lemma 3.2). It
shows that approximate optimization of $\mathcal{D}({\cdot})$ leads to an RKHS
$\mathcal{H}$ that fulfills the condition (11); its reproducing kernel equals
(see Section D.2)

$\\!\\!k_{x,p}(x,x^{\prime})=\hat{\Psi}_{n}^{\top}(x)\Sigma_{x}^{-\frac{1}{2}}(\Sigma_{x}^{\frac{1}{2}}\Sigma_{z}\Sigma_{x}^{\frac{1}{2}})^{\alpha}\Sigma_{x}^{-\frac{1}{2}}\hat{\Psi}_{n}(x^{\prime}),$
(19)

where $\hat{\Phi}_{n}^{\top}(z)\hat{\Psi}_{n}(x)=:\hat{h}_{n}(z,x)$ defines
the approximate optimum,
$\Sigma_{x}=\mathbb{E}_{\mathbf{x}}\hat{\Psi}_{n}(\mathbf{x})\hat{\Psi}_{n}^{\top}(\mathbf{x})$
denotes the uncentered covariance, and $\Sigma_{z}$ is defined similarly using
$\hat{\Phi}_{n}(\mathbf{z})$. In practice, we use its empirical approximation,

$\\!\\!k_{x}(x,x^{\prime})=\hat{\Psi}_{n}^{\top}(x)\hat{\Sigma}_{x}^{-\frac{1}{2}}(\hat{\Sigma}_{x}^{\frac{1}{2}}\hat{\Sigma}_{z}\hat{\Sigma}_{x}^{\frac{1}{2}})^{\alpha}\hat{\Sigma}_{x}^{-\frac{1}{2}}\hat{\Psi}_{n}(x^{\prime}),$
(19’)

where $(\hat{\Sigma}_{x},\hat{\Sigma}_{z})$ are plug-in estimates for
$(\Sigma_{x},\Sigma_{z})$. For theoretical analyses, we assume
$(\hat{\Sigma}_{x},\hat{\Sigma}_{z})$ are estimated using $\mathcal{O}(n)$
additional i.i.d. samples.

(18) further connects spectral decomposition and kernel learning to a
$\chi^{2}$ divergence. In particular, it shows the operator $E^{\top}E$ is
trace-class if and only if the $\chi^{2}$-divergence is finite. This is the
sufficient and necessary condition for the space $\bar{\mathcal{H}}_{{1}}$ to
have an RKHS structure (Steinwart and Scovel,, 2012), as we have also noted in
Section 2. More generally, we always have
$\mathcal{D}_{\chi^{2}}(P_{zx}\|P_{z}\otimes
P_{x})+1=\mathrm{Tr}(E^{\top}E)=\mathrm{Var}\>\bar{k}_{x}(\mathbf{x},\mathbf{x})$,
where $\bar{k}_{x}$ is the kernel for $\bar{\mathcal{H}}_{{1}}$; the variance
term on the right-hand side often appears in the analysis of kernel methods,
and can be viewed as a regularity measure. When $\alpha=1$,
$(\bar{\mathcal{H}}_{{1}},\bar{k}_{x})$ is the approximation target of
$(\mathcal{H},k_{x})$; thus, (18) provides an intuitive condition for the
well-definedness of the kernel learning process.

Lemma 4.1 concerns the approximate optimum of the population loss
$\mathcal{D}({\cdot})$. In practice, we can only optimize its finite-sample
counterpart. The following proposition bounds the estimation error incurred in
the process:

######  Proposition 4.1 (Proof in App. D.3).

Let $B,C_{1}>0,q\in(0,1]$ be constants, $h^{*}\in L_{2}(P_{z}\otimes P_{x})$
be an arbitrary function. Suppose the hypothesis space $\mathcal{F}_{h}$ is
star-shaped around $h^{*}$, and $\sup_{h\in\mathcal{F}_{h}}\|h\|_{\infty}\leq
B$, $\log N(\mathcal{F}_{h},\|\cdot\|_{\infty},\epsilon_{n})\leq
C_{1}\epsilon_{n}^{-2q}$. Let $\\{(\tilde{z}_{i},\tilde{x}_{i})\\}_{i=1}^{n}$
be $n$ i.i.d. training samples from $P_{zx}$, and
$\hat{h}_{n}:=\arg\max_{h\in\mathcal{F}_{h}}\mathcal{D}_{n}(h)$, where

$\\!\\!\mathcal{D}_{n}(h):=\frac{2}{n}\sum_{i=1}^{n}h(\tilde{z}_{i},\tilde{x}_{i})-\frac{1}{n(n-1)}\sum_{i\neq
j}h(\tilde{z}_{i},\tilde{x}_{j})^{2}$ (20)

is the empirical risk. Then there exists some $C_{q}>0$ s.t. for all
$\zeta>0$, we have, w.p. $\geq 1-\zeta$,

$\displaystyle\mathcal{D}({h_{0}})\>-$
$\displaystyle\>\mathcal{D}({\hat{h}_{n}})\leq C_{q}\Big{(}$
$\displaystyle\\!\\!\\!\mathcal{D}({h_{0}})-\mathcal{D}({h^{*}})+B^{4}n^{-\frac{1}{1+q}}+B^{4}\frac{\log\zeta^{-1}}{n}\Big{)}.$

######  Remark 4.1.

Proposition 4.1 provides fast-rate guarantees for the estimation (i.e.,
generalization) error for $\mathcal{D}({h})$.222 HaoChen et al., (2021)
established a slow rate result in their setting, which saturates at
$\Omega(n^{-1/2})$ and is less interesting in light of the discussion below.
Their main results were developed under structural assumptions on their
neighbor graph.  When $\mathcal{F}_{h}$ admits the factorized structure in
Lemma 3.1, the result is equivalent to fast-rate guarantees for spectral
decomposition as measured in $\|\cdot\|_{\mathrm{HS}}$. The $o(n^{-1/2})$
convergence rate is interesting, as it contrasts existing approaches based on
explicit normalization constraints: e.g., constraining the “eigenfunction
estimates” $\Psi$ to be orthogonal (Pfau et al.,, 2020; Deng et al., 2022b, ),
or at least having a covariance matrix with a bounded spectral norm. It would
be more challenging to establish similar guarantees for those methods, because
their constraints can only be enforced at a precision of
$\mathcal{O}(\sqrt{J_{n}/n})$, which is the error of covariance estimation.

The evaluation of our kernel (19) also involves covariance estimation.
However, at least when $\alpha\in\\{1,2\\}$, its plug-in estimate (19’) may
enjoy the same guarantees (Prop. E.1). From the perspectives of spectral
decomposition and general representation learning, Proposition 4.1 can also be
interpreted as a guarantee for the learned $\Psi$ to approximate the subspace
spanned by the leading singular vectors, as the Hilbert-Schmidt norm guarantee
implies a similar guarantee for the “variance explained” objective (7) (App.
D.1).

To obtain full guarantees for $\epsilon_{n}^{2}$, it remains to bound the
approximation error $\mathcal{D}({h_{0}})-\mathcal{D}({h^{*}})$. In Section
E.1 we provide a generic approximation result, and instantiate it on our
running example. As we will see, when using DNN models for $\mathcal{F}_{h}$,
the combined error rate $\epsilon_{n}^{2}$ can still be $o(n^{-1/2})$, and is
adaptive to the dimensionality of the informative latent variables introduced
in Example 2.1.

####  4.2 Results for Conditional Moment Models

We then turn to consistency guarantees for the estimator (3), in which
$\mathcal{H},\mathcal{I}$ are instantiated using the learned representations:
we define $\mathcal{H}$ using the kernel in (19’), in which $\hat{h}_{n}$ is
defined as in Proposition 4.1. For simplicity, we define $\mathcal{I}$ using a
symmetric choice of kernel:

$k_{z}(z,z^{\prime}):=\hat{\Phi}_{n}^{\top}(z)\hat{\Sigma}_{z}^{-\frac{1}{2}}(\hat{\Sigma}_{z}^{\frac{1}{2}}\hat{\Sigma}_{x}\hat{\Sigma}_{z}^{\frac{1}{2}})^{\alpha^{\prime}}\hat{\Sigma}_{z}^{-\frac{1}{2}}\hat{\Phi}_{n}(z^{\prime}).$
(21)

When $\alpha^{\prime}=\alpha+1$, $k_{z}$ will approximate the “optimal
instrument” kernel for $\mathcal{H}$. For technical reasons, however, our
analysis assumes $\alpha^{\prime}=1$. See App. F.2 for details.

We now present the $L_{2}$ convergence result. For brevity, below we state the
result in the setting of our running example; a more general result can be
found in Appendix F.1.

######  Theorem 4.1 (Proof in App. F.1).

Let $\mathbf{x},\mathbf{z},f_{enc,x},f_{enc,z}$ be defined as in Ex. 2.1-2.2.
Suppose $p>2$, there exists some $f_{0}$ that satisfies (5) with $\beta=b/2p$,
and $f_{enc,x},f_{enc,z}$ are $\beta_{d}$ Hölder regular (see e.g., Giné and
Nickl,, 2021) with
$2\beta_{d}\geq(p-2)\max\\{\dim\mathbf{z},\dim\mathbf{x}\\}$. Let
$\alpha\in\\{1,2\\}\leq\beta$, and

  * •

$\hat{h}_{n}(z,x)=\hat{\Phi}_{n}^{\top}(z)\hat{\Psi}_{n}(x)\in\mathcal{F}_{h}$
be the empirical risk minimizer for (49) ($\alpha=1$), or the solution to the
constrained optimization problem (58) in appendix ($\alpha=2$), using a DNN
model for $\mathcal{F}_{h}$ (see appendix),

  * •

$(k_{x},\mathcal{H},k_{z},\mathcal{I})$ be defined by (19’), (21) using
$\alpha^{\prime}=1$, $\alpha\in\\{1,2\\}$ and $\hat{h}_{n}$, with
$(\hat{\Sigma}_{x},\hat{\Sigma}_{z})$ defined using another $n$ samples
$\mathcal{D}^{(n)}_{2}$,

  * •

$\hat{f}_{n}$ be defined by (3) using $\mathcal{H},\mathcal{I}$, a third set
of $n$ i.i.d. samples $\mathcal{D}^{(n)}_{3}:=\\{(z_{i},x_{i},y_{i})\\}$, and
$(J_{n},\nu_{n},\lambda_{n})$ be chosen as in Section F.1.

Then we have, w.p. $\geq 1-n^{-10}$,

$\|\hat{f}_{n}-f_{0}\|_{2}=\tilde{\mathcal{O}}\big{(}n^{-\frac{2\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.

######  Remark 4.2.

Theorem 4.1 provides an $L_{2}$ rate of convergence without any preimposed
condition on measures of ill-posedness. Under its conditions, Chen and Reiss,
(2007) establishes the minimax lower rate of $\Omega(n^{-\frac{\alpha
p}{((1+\alpha)2p+1)}})$, which can be realized assuming knowledge of (6). Note
that both rates approach the order of $n^{-\alpha/2(\alpha+1)}$ as
$p\to\infty$. Also note that under (5), both rates only depend on $p$, and
adapt to the typically lower dimensionality of the informative latent
variables (Ex. 2.2). This is in contrast to what can possibly be established
for estimators based on fixed-form kernels; see Section F.2 for more
discussion.

To achieve similar $L_{2}$ rates, the only alternatives would be to employ
Landweber or ridge regularization _in the $L_{2}$ space_ (Carrasco et al.,,
2007), which we discuss in more detail in App. B.1. Briefly, the latter
strategy cannot adapt to $\beta>1$, whereas the application of the former
appears difficult in high dimensions, as it requires representing
$\mathcal{H}$ using a predetermined orthonormal basis. Hyperparameter
selection for these approaches will also be less trivial and cannot be based
on the comparison of (2). In aggregate, our kernel learning approach appears
the most viable in achieving similar guarantees, if one wishes to benefit from
the use of DNN models.

####  4.3 Algorithm Implementation

##### The algorithm

We instantiate the estimator (3) using the learned kernels, and estimates the
learned representation $(\hat{\Psi}_{n},\hat{\Phi}_{n})$ and $\hat{f}_{n}$ on
separate partitions of the training data. Our theoretical discussions have
assumed the variables $\mathbf{x},\mathbf{z}$ do not overlap, and employed the
kernels of (19’), (21). In practice, we use the same kernels, but impose fewer
restrictions: we consider arbitrary values of $\alpha$, use
$\alpha^{\prime}=\alpha+1$, and reuse samples when estimating the covariance
terms in $(k_{x},k_{z})$; the process is summarized in Algorithm 1. When
$\mathbf{x}$ and $\mathbf{z}$ overlap, we modify the algorithm to learn
product kernels, as we will describe shortly.

Algorithm 1 Kernel learning by spectral decomposition

0: $\\{(\tilde{z}_{i},\tilde{x}_{i})\\}_{i=1}^{n}$, hyperparameters
$J_{n},\alpha$, model
$\mathcal{F}_{h}=\\{h=\Phi_{h}(z)^{\top}\Psi_{h}(x):\Phi_{h}\in\mathcal{F}_{\Phi},\Psi_{h}\in\mathcal{F}_{\Psi}\\}$

0: learned kernels $k_{x},k_{z}$

Let $\hat{h}_{n}=\hat{\Phi}_{n}(z)^{\top}\hat{\Psi}_{n}(x)$ minimizes
$\mathcal{D}_{n}$ in (49)

$\hat{\Sigma}_{x}\leftarrow\frac{1}{n}\sum_{i=1}^{n}\hat{\Psi}_{n}(\tilde{x}_{i})\hat{\Psi}_{n}^{\top}(\tilde{x}_{i})$

$\hat{\Sigma}_{z}\leftarrow\frac{1}{n}\sum_{i=1}^{n}\hat{\Phi}_{n}(\tilde{z}_{i})\hat{\Phi}_{n}^{\top}(\tilde{z}_{i})$

return
$k_{x}(x,x^{\prime}):=\hat{\Psi}_{n}^{\prime}(x)\hat{\Sigma}_{x}^{\frac{\alpha-1}{2}}\hat{\Sigma}_{z}^{\alpha}\hat{\Sigma}_{x}^{\frac{\alpha-1}{2}}\hat{\Psi}_{n}(x^{\prime})$,
$k_{z}(z,z^{\prime}):=\hat{\Phi}_{n}^{\prime}(z)\hat{\Sigma}_{z}^{\frac{\alpha}{2}}\hat{\Sigma}_{x}^{\alpha+1}\hat{\Sigma}_{z}^{\frac{\alpha}{2}}\hat{\Phi}_{n}(z^{\prime})$

The hyperparameters $\alpha,J_{n}$ and the regularization hyperparameters
$\lambda_{n},\nu_{n}$ in (3) can be determined using the established process
in kernelized IV estimation (Singh et al.,, 2019; Muandet et al., 2020b, ;
Dikkala et al.,, 2020). The hyperparameters used in learning $\hat{h}_{n}$,
such as the DNN architecture and optimization hyperparameters, are determined
by evaluating the learning objective $\mathcal{D}_{n}$ on a held-out dataset.
As $\hat{h}_{n}$ has been trained on a subset of training data, we simply use
the other subset for validation.

##### Extensions for overlap variables

In many applications, the variables $\mathbf{x},\mathbf{z}$ may have overlap,
meaning that there exists
$(\mathbf{x}^{\prime},\mathbf{z}^{\prime},\mathbf{w})$ s.t.
$\mathbf{x}=(\mathbf{x}^{\prime},\mathbf{w}),\mathbf{z}=(\mathbf{z}^{\prime},\mathbf{w})$.
For example, in proximal causal inference, $\mathbf{w}$ will contain the
treatment variable. In such cases, we can construct product kernels for (3):
let $k_{x^{\prime}},k_{z}$ be the kernels returned by Algorithm 1, on the
dataset $\\{(\tilde{z}_{i},\tilde{x}^{\prime}_{i})\\}$. Then we can use
$k_{z}$ to define $\mathcal{I}$, and the following kernel for $\mathcal{H}$:

$k_{x}^{\prime}((x_{1}^{\prime},w_{1}),(x_{2}^{\prime},w_{2})):=k_{x^{\prime}}(x_{1}^{\prime},x_{2}^{\prime})k_{w}(w_{1},w_{2}),$

where $k_{w}$ can be a fixed-form kernel, which is appropriate for
$\mathbf{w}$ with moderate dimensions. We implement this algorithm in our
experiments. When $\mathbf{w}$ is high-dimensional, we can learn product
kernels by feeding the above $k_{x^{\prime}}$ to the extended algorithm in
Wang et al., (2022, App. G).

The product kernel constructions are related to the product basis models which
have appeared in literature (e.g., Kato,, 2013). Intuitively, more flexibility
can be expected in specifying parts of the hypothesis space that are related
to $\mathbf{w}$, as they are in some sense less affected by the ill-posedness
issue: we have $\mathbb{E}(g(\mathbf{w})\mid\mathbf{z})=g(\mathbf{w})$ for all
$g\in L_{2}(P_{w})$.

###  5 RELATED WORK

A series of works have developed estimators with a form similar to (3), as we
briefly discussed in Section 2. App. B.1 reviews additional literature and
possible strategies for achieving $L_{2}$ consistency. To our knowledge, only
Liao et al., (2020) provided an alternative result that allows the use of
adaptive ML models (e.g., DNNs) and does not rely on preimposed assumptions on
measures of ill-posedness. They have relied on $L_{2}$ regularization, and
cannot adapt to $\beta>1$, in contrast to our result (Remark 4.2, Section
B.1). Note that a separate line of work studies the use of ML for linear IV
problems with fixed dimensionality, which is a fundamentally different setting
(Singh et al.,, 2020, p. 6; Foster and Syrgkanis,, 2019, p. 8).

Our analysis for spectral representation learning (Sec. 4.1) is connected to
recent theoretical works on multi-view learning (Arora et al.,, 2019; Lee et
al.,, 2020; Tosh et al.,, 2021), which views $\mathbf{z},\mathbf{x}$ as
conditionally independent views of a latent variable. The connection between
spectral decomposition and contrastive representation learning is also being
recognized (HaoChen et al.,, 2021; Balestriero and LeCun,, 2022). App. B.3
discusses this literature in more detail. Briefly, our results are unique in
relating representation learning to divergence maximization and kernel
learning, and in establishing fast-rate convergence in a concrete high-
dimensional setting (App. E.1); in particular, there had been a lack of
understanding of approximation guarantees. Note that our results for
conditional moment models (Sec. 3, 4.2) are independently developed, and
constitute a separate contribution.

Michaeli et al., (2016) studied the estimation of SVD of $E$, using kernel
density estimates; also related are Klus et al., (2020); Kostic et al., (2022)
who studied the connected but different problem of eigendecomposition (of
similar non-self-adjoint operators) using RKHS methods. As we discuss in App.
F.2, using fixed-form kernels or similar nonparametric models for estimation
is often inapplicable for high-dimensional data, due to a provable lack of
adaptivity. However, there are also scenarios that specifically require the
decomposition of similar conditional expectation operators, restricted to
prescribed RKHSes, such as in the estimation of the conditional mean embedding
operator (Park and Muandet,, 2021; Talwai et al.,, 2022).

Concurrent to our work, Johnson et al., (2022); Deng et al., 2022a  also
studied connections between contrastive learning, spectral decomposition, and
kernel machines, and the use of kernels similar to our
$\bar{\mathcal{H}}_{{1}}$ in a generic self-supervised learning setup.
However, neither work provided statistical guarantees for the kernel learning
process or the use of learned kernels in downstream tasks.

###  6 EXPERIMENTS

We evaluate our method on synthetic and semi-synthetic datasets. The synthetic
experiment evaluates the convergence of the representation learning objective
and the $L_{2}$ error for conditional moment models; for space reasons, we
defer it to Appendix G.1. Below we describe the semi-synthetic experiment for
proximal causal inference.

Our setup is adapted from Mastouri et al., (2021) who fitted generative models
on three real-world datasets, and used simulation from the model for
evaluation. This design allows us to compare the estimated causal effect to
the “ground truth” in the fitted generative model, even though both may be
different from the (unobservable) causal effect in the real world. To emulate
a high-dimensional setup, we modify the proxy variables in their datasets by
concatenating them with $D_{ex}$ independent random variables, and
transforming them with feedforward DNNs.

As baselines, we instantiate the estimator (3) with DNN (AGMM-NN) and fixed-
form kernel (Kernel-RBF) models. The baselines have established guarantees
(for the population objective (2)), and competitive empirical performance
(Dikkala et al.,, 2020); the kernel baseline is also similar to those employed
in Mastouri et al., (2021).

We report a representative subset of results in Table 1 and Fig. 2. As we can
see, our method has strong performance, especially in high dimensions. Due to
space limits, we defer the full experiment setup and results to Section G.2.

$D_{ex}$ | AGMM-NN | Kernel-RBF | Proposed
---|---|---|---
Abortion and Crime
$4$ |  $0.12$ $[0.11,0.13]$ |  $0.14$ $[0.11,0.15]$ |  $\mathbf{0.11}$ $[0.09,0.12]$
$32$ |  $0.30$ $[0.29,0.33]$ |  $0.17$ $[0.15,0.18]$ |  $\mathbf{0.12}$ $[0.10,0.14]$
$256$ |  $0.33$ $[0.32,0.34]$ |  $0.16$ $[0.15,0.20]$ |  $\mathbf{0.11}$ $[0.10,0.12]$
Grade Retention in Reading
$4$ |  $0.05$ $[0.05,0.07]$ |  $0.07$ $[0.06,0.07]$ |  $\mathbf{0.03}$ $[0.03,0.03]$
$32$ |  $0.11$ $[0.10,0.12]$ |  $0.07$ $[0.07,0.07]$ |  $\mathbf{0.03}$ $[0.03,0.03]$
$256$ |  $0.10$ $[0.10,0.11]$ |  $0.07$ $[0.07,0.07]$ |  $\mathbf{0.03}$ $[0.03,0.04]$
Grade Retention in Math
$4$ |  $\mathbf{0.05}$ $[0.03,0.07]$ |  $0.09$ $[0.07,0.14]$ |  $\mathbf{0.05}$ $[0.03,0.10]$
$32$ |  $0.09$ $[0.07,0.10]$ |  $0.10$ $[0.07,0.17]$ |  $\mathbf{0.06}$ $[0.03,0.12]$
$256$ |  $0.08$ $[0.08,0.09]$ |  $0.09$ $[0.07,0.16]$ |  $\mathbf{0.05}$ $[0.03,0.11]$
Table 1: Semi-synthetic experiment: mean average error (MAE) for the average
treatment effect (ATE) estimates, across all datasets, for $N=2000$. We report
$50\%,25\%$ and $75\%$ percentiles across $10$ independent replications.
Boldface indicates the best result(s).  Figure 2: Semi-synthetic experiment:
test MAE for the abortion and crime data, for $D_{ex}=256$ and varying $N$. We
omit AGMM-NN which is uncompetitive in this setting. Error bar indicates the
$25\%$ and $75\%$ percentiles.

###  7 DISCUSSION

Ill-posedness is a fundamental issue in nonparametric CMMs. This work
demonstrates that representations with well-controlled measures of ill-
posedness can be robustly learned from data, by studying a kernelized CMM
estimator instantiated with learned kernels. The estimator enjoys consistency
guarantees under intuitive assumptions, and exhibits promising empirical
performance. Our results are also interesting from a few other aspects, as we
discussed.

Our learning target (6) has been a “gold standard” in a large proportion of
the nonparametric IV/CMM literature. Still, it will not suit all applications.
Section B.2 discusses its inductive bias in detail; below we briefly outline
its limitations, and possible directions for future work:

  * •

The learning target (6) does not account for overlap variables. While we have
derived extensions in Sec. 4.3 and evaluated an extended algorithm, it remains
future work to study the high-dimensional extension as mentioned, from both
empirical and theoretical perspectives.

  * •

While (6) adapts to certain latent structures which can be particularly
desirable in some scenarios (Ex. 2.1), it does not benefit from supervision
signals from $\mathbf{y}$. In such cases, our results, in particular, Thm.
3.1, could still be useful to analyze a two-phase kernel learning algorithm,
where the first phase takes in the supervision signals similar to Xu et al.,
(2020), and the second stage modifies its output using information about $E$,
to control the moduli of continuity.

  * •

While assumptions like (5) are necessary for efficient estimation, and
inference under identifiability, they can be undesirable in non-identifiable
scenarios if one wishes to construct confidence regions. These two types of
scenarios have been studied separately in the literature, and our work makes
no exception.

More broadly, different causal estimation problems necessarily require
different treatments, but the issue of ill-posedness is a recurring theme. And
so is the need to develop representation learning algorithms that address this
issue. Our work can be viewed as evidence suggesting the RKHS perspective
could be particularly helpful in such developments.

### References

  * Aleksandrov and Peller, (2016) Aleksandrov, A. B. and Peller, V. V. (2016).  Operator lipschitz functions.  Russian Mathematical Surveys, 71(4):605.
  * Arcones and Giné, (1993) Arcones, M. A. and Giné, E. (1993).  Limit theorems for u-processes.  The Annals of Probability, pages 1494–1542.
  * Arora et al., (2019) Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., and Saunshi, N. (2019).  A Theoretical Analysis of Contrastive Unsupervised Representation Learning.  arXiv:1902.09229 [cs, stat].  arXiv: 1902.09229.
  * Balestriero and LeCun, (2022) Balestriero, R. and LeCun, Y. (2022).  Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods.  Technical Report arXiv:2205.11508, arXiv.  arXiv:2205.11508 [cs, math, stat] type: article.
  * Bennett et al., (2019) Bennett, A., Kallus, N., and Schnabel, T. (2019).  Deep generalized method of moments for instrumental variable analysis.  In Advances in Neural Information Processing Systems.
  * Bhatia, (2013) Bhatia, R. (2013).  Matrix analysis, volume 169.  Springer Science & Business Media.
  * Birman et al., (1975) Birman, M. S., Koplienko, L. S., and Solomyak, M. Z. (1975).  Estimates of the spectrum of a difference of fractional powers of selfadjoint operators.  Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, (3):3–10.
  * Borovitskiy et al., (2020) Borovitskiy, V., Terenin, A., Mostowsky, P., et al. (2020).  Matérn gaussian processes on riemannian manifolds.  Advances in Neural Information Processing Systems, 33:12426–12437.
  * Carrasco et al., (2007) Carrasco, M., Florens, J.-P., and Renault, E. (2007).  Linear inverse problems in structural econometrics estimation based on spectral decomposition and regularization.  Handbook of econometrics, 6:5633–5751.
  * Chamberlain, (1987) Chamberlain, G. (1987).  Asymptotic efficiency in estimation with conditional moment restrictions.  Journal of Econometrics, 34(3):305–334.
  * Chen and Christensen, (2015) Chen, X. and Christensen, T. M. (2015).  Optimal sup-norm rates and uniform inference on nonlinear functionals of nonparametric IV regression.  arXiv preprint arXiv:1508.03365.
  * Chen and Pouzo, (2012) Chen, X. and Pouzo, D. (2012).  Estimation of Nonparametric Conditional Moment Models With Possibly Nonsmooth Generalized Residuals.  Econometrica, 80(1):277–321.
  * Chen and Reiss, (2007) Chen, X. and Reiss, M. (2007).  On Rate Optimality For Ill-posed Inverse Problems In Econometrics.  Econometric Theory, (3):497–521.
  * Chen et al., (2021) Chen, Y., Xu, L., Gulcehre, C., Paine, T. L., Gretton, A., de Freitas, N., and Doucet, A. (2021).  On instrumental variable regression for deep offline policy evaluation.  arXiv preprint arXiv:2105.10148.
  * Clémençon et al., (2006) Clémençon, S., Lugosi, G., and Vayatis, N. (2006).  Discussion: Local rademacher complexities and oracle inequalities in risk minimization.  The Annals of Statistics, 34(6):2672–2676.
  * Clémençon et al., (2008) Clémençon, S., Lugosi, G., and Vayatis, N. (2008).  Ranking and Empirical Minimization of U-statistics.  The Annals of Statistics, 36(2).
  * Corfield et al., (2009) Corfield, D., Schölkopf, B., and Vapnik, V. (2009).  Falsificationism and statistical learning theory: Comparing the popper and vapnik-chervonenkis dimensions.  Journal for General Philosophy of Science, 40(1):51–58.
  * Darolles et al., (2011) Darolles, S., Fan, Y., Florens, J.-P., and Renault, E. (2011).  Nonparametric instrumental regression.  Econometrica, 79(5):1541–1565.
  * De Vito et al., (2019) De Vito, E., Mücke, N., and Rosasco, L. (2019).  Reproducing kernel Hilbert spaces on manifolds: Sobolev and Diffusion spaces.  Number: arXiv:1905.10913 arXiv:1905.10913 [cs, math, stat].
  * Deaner, (2021) Deaner, B. (2021).  Proxy Controls and Panel Data.  arXiv:1810.00283 [econ].  arXiv: 1810.00283.
  * (21) Deng, Z., Shi, J., Zhang, H., Cui, P., Lu, C., and Zhu, J. (2022a).  Neural eigenfunctions are structured representation learners.
  * (22) Deng, Z., Shi, J., and Zhu, J. (2022b).  Neuralef: Deconstructing kernels by deep neural networks.  In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 4976–4992. PMLR.
  * Dikkala et al., (2020) Dikkala, N., Lewis, G., Mackey, L., and Syrgkanis, V. (2020).  Minimax estimation of conditional moment models.  In Advances in Neural Information Processing Systems, volume 33, pages 12248–12262.
  * Fan and Liao, (2014) Fan, J. and Liao, Y. (2014).  Endogeneity in high dimensions.  The Annals of Statistics, 42(3).
  * Foster and Syrgkanis, (2019) Foster, D. J. and Syrgkanis, V. (2019).  Orthogonal statistical learning.  arXiv preprint arXiv:1901.09036.
  * Foster et al., (2008) Foster, D. P., Kakade, S. M., and Zhang, T. (2008).  Multi-View Dimensionality Reduction via Canonical Correlation Analysis.  Technical report.
  * Fu et al., (2022) Fu, Z., Qi, Z., Wang, Z., Yang, Z., Xu, Y., and Kosorok, M. R. (2022).  Offline reinforcement learning with instrumental variables in confounded markov decision processes.  arXiv preprint arXiv:2209.08666.
  * Gemp et al., (2020) Gemp, I., McWilliams, B., Vernade, C., and Graepel, T. (2020).  Eigengame: Pca as a nash equilibrium.  arXiv preprint arXiv:2010.00554.
  * Giné and Nickl, (2021) Giné, E. and Nickl, R. (2021).  Mathematical foundations of infinite-dimensional statistical models.  Cambridge university press.
  * Gretton et al., (2005) Gretton, A., Herbrich, R., Smola, A., Bousquet, O., and Schölkopf, B. (2005).  Kernel methods for measuring independence.  Journal of Machine Learning Research, 6:2075–2129.
  * Hall and Horowitz, (2005) Hall, P. and Horowitz, J. L. (2005).  Nonparametric methods for inference in the presence of instrumental variables.  The Annals of Statistics, 33(6).
  * HaoChen et al., (2021) HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, T. (2021).  Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss.  In Advances in Neural Information Processing Systems, volume 34, pages 5000–5011. Curran Associates, Inc.
  * Hartford et al., (2017) Hartford, J., Lewis, G., Leyton-Brown, K., and Taddy, M. (2017).  Deep IV: A flexible approach for counterfactual prediction.  In International Conference on Machine Learning, pages 1414–1423.
  * Horowitz, (2014) Horowitz, J. L. (2014).  Ill-Posed Inverse Problems in Economics.  Annual Review of Economics, 6(1):21–51.
  * Johnson et al., (2022) Johnson, D. D., Hanchi, A. E., and Maddison, C. J. (2022).  Contrastive learning can find an optimal basis for approximately view-invariant functions.  arXiv preprint arXiv:2210.01883.
  * Kallenberg, (1997) Kallenberg, O. (1997).  Foundations of modern probability, volume 2.  Springer.
  * Kallus et al., (2021) Kallus, N., Mao, X., and Uehara, M. (2021).  Causal inference under unmeasured confounding with negative controls: A minimax learning approach.  arXiv preprint arXiv:2103.14029.
  * Kanagawa et al., (2018) Kanagawa, M., Hennig, P., Sejdinovic, D., and Sriperumbudur, B. K. (2018).  Gaussian processes and kernel methods: A review on connections and equivalences.  arXiv preprint arXiv:1807.02582.
  * Kato, (2013) Kato, K. (2013).  Quasi-Bayesian analysis of nonparametric instrumental variables models.  The Annals of Statistics, 41(5):2359–2390.
  * Kato et al., (2021) Kato, M., Imaizumi, M., McAlinn, K., Yasui, S., and Kakehi, H. (2021).  Learning causal models from conditional moment restrictions by importance weighting.  In International Conference on Learning Representations.
  * Klus et al., (2020) Klus, S., Schuster, I., and Muandet, K. (2020).  Eigendecompositions of Transfer Operators in Reproducing Kernel Hilbert Spaces.  Journal of Nonlinear Science, 30(1):283–315.  arXiv:1712.01572 [cs, math, stat].
  * Knapik and Salomond, (2017) Knapik, B. and Salomond, J.-B. (2017).  A general approach to posterior contraction in nonparametric inverse problems.  arXiv:1407.0335 [math, stat].  arXiv: 1407.0335.
  * Knapik et al., (2011) Knapik, B. T., van der Vaart, A. W., and van Zanten, J. H. (2011).  Bayesian inverse problems with Gaussian priors.  The Annals of Statistics, 39(5):2626–2657.
  * Kostic et al., (2022) Kostic, V., Novelli, P., Maurer, A., Ciliberto, C., Rosasco, L., and Pontil, M. (2022).  Learning dynamical systems via koopman operator regression in reproducing kernel hilbert spaces.  arXiv preprint arXiv:2205.14027.
  * Kremer et al., (2022) Kremer, H., Zhu, J.-J., Muandet, K., and Schölkopf, B. (2022).  Functional generalized empirical likelihood estimation for conditional moment restrictions.  In International Conference on Machine Learning, pages 11665–11682. PMLR.
  * Kress et al., (1989) Kress, R., Maz’ya, V., and Kozlov, V. (1989).  Linear integral equations, volume 82.  Springer.
  * Lee et al., (2020) Lee, J. D., Lei, Q., Saunshi, N., and Zhuo, J. (2020).  Predicting What You Already Know Helps: Provable Self-Supervised Learning.  arXiv:2008.01064 [cs, stat].  arXiv: 2008.01064.
  * Lewis and Syrgkanis, (2018) Lewis, G. and Syrgkanis, V. (2018).  Adversarial generalized method of moments.  arXiv preprint arXiv:1803.07164.
  * (49) Li, J., Luo, Y., and Zhang, X. (2021a).  Causal reinforcement learning: An instrumental variable approach.  arXiv preprint arXiv:2103.04021.
  * (50) Li, Y., Pogodin, R., Sutherland, D. J., and Gretton, A. (2021b).  Self-Supervised Learning with Kernel Dependence Maximization.  arXiv:2106.08320 [cs, stat].  arXiv: 2106.08320.
  * Liao et al., (2020) Liao, L., Chen, Y.-L., Yang, Z., Dai, B., Wang, Z., and Kolar, M. (2020).  Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach.  arXiv:2007.01290 [cs, stat].  arXiv: 2007.01290.
  * Lin et al., (2015) Lin, W., Feng, R., and Li, H. (2015).  Regularization Methods for High-Dimensional Instrumental Variables Regression With an Application to Genetical Genomics.  Journal of the American Statistical Association, 110(509):270–288.
  * Maclaren and Nicholson, (2020) Maclaren, O. J. and Nicholson, R. (2020).  What can be estimated? Identifiability, estimability, causal inference and ill-posed inverse problems.  arXiv:1904.02826 [cs, math, stat].  arXiv: 1904.02826.
  * Mastouri et al., (2021) Mastouri, A., Zhu, Y., Gultchin, L., Korba, A., Silva, R., Kusner, M. J., Gretton, A., and Muandet, K. (2021).  Proximal Causal Learning with Kernels: Two-Stage Estimation and Moment Restriction.  arXiv:2105.04544 [cs].  arXiv: 2105.04544.
  * Miao et al., (2018) Miao, W., Geng, Z., and Tchetgen, E. T. (2018).  Identifying Causal Effects With Proxy Variables of an Unmeasured Confounder.  arXiv:1609.08816 [stat].  arXiv: 1609.08816.
  * Michaeli et al., (2016) Michaeli, T., Wang, W., and Livescu, K. (2016).  Nonparametric Canonical Correlation Analysis.  arXiv:1511.04839 [cs, stat].  arXiv: 1511.04839.
  * (57) Muandet, K., Jitkrittum, W., and Kübler, J. (2020a).  Kernel conditional moment test via maximum moment restriction.  In Conference on Uncertainty in Artificial Intelligence, pages 41–50. PMLR.
  * (58) Muandet, K., Mehrjou, A., Lee, S. K., and Raj, A. (2020b).  Dual instrumental variable regression.  arXiv preprint arXiv:1910.12358.
  * Newey and Powell, (2003) Newey, W. K. and Powell, J. L. (2003).  Instrumental variable estimation of nonparametric models.  Econometrica, 71(5):1565–1578.
  * Park and Muandet, (2021) Park, J. and Muandet, K. (2021).  A Measure-Theoretic Approach to Kernel Conditional Mean Embeddings.  arXiv:2002.03689 [cs, stat].  arXiv: 2002.03689.
  * Pfau et al., (2020) Pfau, D., Petersen, S., Agarwal, A., Barrett, D. G. T., and Stachenfeld, K. L. (2020).  Spectral Inference Networks: Unifying Deep and Spectral Learning.  Number: arXiv:1806.02215 arXiv:1806.02215 [cs, stat].
  * Qiu et al., (2022) Qiu, S., Wang, L., Bai, C., Yang, Z., and Wang, Z. (2022).  Contrastive ucb: Provably efficient contrastive self-supervised learning in online reinforcement learning.  In International Conference on Machine Learning, pages 18168–18210. PMLR.
  * Schmidt-Hieber, (2020) Schmidt-Hieber, J. (2020).  Nonparametric regression using deep neural networks with ReLU activation function.  The Annals of Statistics, 48(4).  arXiv: 1708.06633.
  * Schölkopf and Smola, (2002) Schölkopf, B. and Smola, A. J. (2002).  Learning with Kernels.  MIT Press, Cambridge, MA, USA.
  * Shi et al., (2022) Shi, C., Uehara, M., Huang, J., and Jiang, N. (2022).  A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processes.  arXiv:2111.06784 [cs, stat].
  * Singh et al., (2020) Singh, A., Hosanagar, K., and Gandhi, A. (2020).  Machine learning instrument variables for causal inference.  In Proceedings of the 21st ACM Conference on Economics and Computation, pages 835–836.
  * Singh et al., (2019) Singh, R., Sahani, M., and Gretton, A. (2019).  Kernel Instrumental variable regression.  arXiv preprint arXiv:1906.00232.
  * Staiger and Stock, (1997) Staiger, D. and Stock, J. H. (1997).  Instrumental Variables Regression with Weak Instruments.  Econometrica, 65(3):557–586.
  * Steinwart, (2019) Steinwart, I. (2019).  Convergence types and rates in generic Karhunen-Loève expansions with applications to sample path properties.  Potential Analysis, 51(3):361–395.
  * Steinwart and Christmann, (2008) Steinwart, I. and Christmann, A. (2008).  Support Vector Machines.  Springer Science & Business Media.
  * Steinwart and Scovel, (2012) Steinwart, I. and Scovel, C. (2012).  Mercer’s theorem on general domains: On the interaction between measures, kernels, and RKHSs.  Constructive Approximation, 35(3):363–417.
  * Szabó et al., (2015) Szabó, B., Van Der Vaart, A. W., and van Zanten, J. (2015).  Frequentist coverage of adaptive nonparametric Bayesian credible sets.  The Annals of Statistics, 43(4):1391–1428.
  * Talwai et al., (2022) Talwai, P., Shameli, A., and Simchi-Levi, D. (2022).  Sobolev Norm Learning Rates for Conditional Mean Embeddings.  arXiv:2105.07446 [cs, stat].  arXiv: 2105.07446.
  * Tchetgen Tchetgen et al., (2020) Tchetgen Tchetgen, E. J., Ying, A., Cui, Y., Shi, X., and Miao, W. (2020).  An Introduction to Proximal Causal Learning.  arXiv:2009.10982 [stat].  arXiv: 2009.10982.
  * Tosh et al., (2021) Tosh, C., Krishnamurthy, A., and Hsu, D. (2021).  Contrastive learning, multi-view redundancy, and linear models.  arXiv:2008.10150 [cs, stat].
  * Wainwright, (2019) Wainwright, M. J. (2019).  High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48.  Cambridge University Press.
  * (77) Wang, Z., Zhou, Y., Ren, T., and Zhu, J. (2021a).  Quasi-Bayesian dual instrumental variable regression.  arXiv preprint arXiv:2106.08750.
  * (78) Wang, Z., Zhou, Y., Ren, T., and Zhu, J. (2021b).  Scalable quasi-bayesian inference for instrumental variable regression.  Advances in Neural Information Processing Systems, 34:10469–10482.
  * Wang et al., (2022) Wang, Z., Zhou, Y., and Zhu, J. (2022).  Fast instrument learning with faster rates.  In Thirty-Sixth Conference on Neural Information Processing Systems.
  * Wright, (1928) Wright, P. G. (1928).  Tariff on animal and vegetable oils.  Macmillan Company, New York.
  * Xu et al., (2020) Xu, L., Chen, Y., Srinivasan, S., de Freitas, N., Doucet, A., and Gretton, A. (2020).  Learning deep features in instrumental variable regression.  arXiv preprint arXiv:2010.07154.
  * Zhang et al., (2020) Zhang, R., Imaizumi, M., Schölkopf, B., and Muandet, K. (2020).  Maximum moment restriction for instrumental variable regression.  arXiv preprint arXiv:2010.07684.
  * Zhang et al., (2022) Zhang, T., Ren, T., Yang, M., Gonzalez, J., Schuurmans, D., and Dai, B. (2022).  Making linear mdps practical via contrastive representation learning.  In International Conference on Machine Learning, pages 26447–26466. PMLR.

Spectral Representation Learning for Conditional Moment Models:
Supplementary Materials

##

###  Appendix A Additional Notations and Conventions

We introduce additional notations which will be used in the appendix:
$\asymp,\lesssim,\gtrsim$ denote (in)equalities up to constants. $\prec,\succ$
denote the Löwner order between operators. $a\wedge b:=\min\\{a,b\\},a\vee
b:=\max\\{a,b\\}$. Throughout the appendix we will use
$c,c^{\prime},c_{1},c_{2},\ldots$ to refer to universal constants, and
$C,C^{\prime},C_{1},C_{2},\ldots$ to refer to constants whose value may depend
on constants introduced in the assumptions (_e.g._ , $b,p,\alpha,\beta$), but
are otherwise independent of the sample size or the data generating process.
The exact value of such constants may change from line to line.

We will occasionally abuse notations and refer to operators from a finite-
dimensional Euclidean space to some $L_{2}$ space as “infinitely wide
matrices”; e.g., given functions $\psi_{1},\ldots,\psi_{m}\in L_{2}(P_{x})$,
we may use the notation $\Psi=(\psi_{1};\ldots;\psi_{m})$ to refer to the
operator

$\Psi:L_{2}(P_{x})\to\mathbb{R}^{m},h\mapsto\begin{bmatrix}\langle\psi_{1},h\rangle_{2}\\\
\ldots\\\ \langle\psi_{m},h\rangle_{2}\end{bmatrix}.$

We also note that while in the text we do not distinguish between square-
integrable functions, such as $f:\mathcal{X}\to\mathbb{R}$, and their
respective $L_{2}$ equivalence classes, such as $[f]_{\sim}\in L_{2}(P_{x})$,
as is done in past works for readability (e.g., Chen and Reiss,, 2007), we
will make the distinction in appendix when necessary. In such places, we will
use the operator

$\mathrm{E}_{r}:L_{\infty}(P_{x})\to L_{\infty}(P_{z})$

to refer to a version of conditional expectation
$\mathbb{E}(f(\mathbf{x})\mid\mathbf{z}=\cdot)=:\mathrm{E}_{r}f$, defined with
an arbitrary version of the regular conditional probability which is fixed
throughout the work. Under basic assumptions which hold for open subsets of
$\mathbb{R}^{d}$, there exists such an $\mathrm{E}_{r}$, which is a bounded
operator; see, e.g., Wang et al., (2022, Remark B.1).

###  Appendix B Additional Discussion: Background and Related Work

####  B.1 Additional Background: Conditional Moment Models

##### Examples

To illustrate the assumptions in various conditional moment models, we provide
sample causal graphs in Fig. 1. We also recall the core assumptions in
proximal causal inference in the following example:

######  Example B.1 (proxy control, Miao et al.,, 2018).

Let the random variables
$\mathbf{v},\mathbf{w},\mathbf{t},\mathbf{u},\mathbf{y}$ be s.t.

  1. (i)

$\mathbf{y}=f_{s}(\mathbf{t},\mathbf{u})$ for some function $f_{s}$;

  2. (ii)

$\mathbf{w}\perp\\!\\!\\!\perp(\mathbf{t},\mathbf{v})\mid\mathbf{u}$;

  3. (iii)

The conditional expectation operators
$E_{ut|z}:f\mapsto\mathbb{E}(f(\mathbf{u},\mathbf{t})\mid\mathbf{t},\mathbf{v}),E_{ut|x}:f\mapsto\mathbb{E}(f(\mathbf{u},\mathbf{t})\mid\mathbf{t},\mathbf{w})$
are injective.

In the above, $\mathbf{t},\mathbf{y},\mathbf{u}$ denote the treatment,
outcome, and (unobserved) confounder. $\mathbf{v},\mathbf{w}$ denote two
observed proxies for $\mathbf{u}$. Condition (ii) is implied by the causal
graph Fig. 1 (b); Fig. 1 (c) describes a particularly interesting special
case, where the observable information about $\mathbf{u}$ can be summarized
into lower-dimensional variables $\bar{\mathbf{v}},\bar{\mathbf{w}}$. (iii)
are completeness assumptions which require $(\mathbf{v},\mathbf{w})$ to be
sufficiently informative; our statement is adapted from Deaner, (2021).

By Miao et al., (2018); Deaner, (2021), for any $f_{0}$ satisfying
$\mathbb{E}(\mathbf{y}-f_{0}(\mathbf{t},\mathbf{w})\mid\mathbf{t},\mathbf{v})=0,$
we have $\mathbb{E}(\mathbf{y}\mid\mathrm{do}(\mathbf{t}=t))=\int
P_{w}(dw)f_{0}(t,w).$ Thus, the treatment effect can be recovered by solving
the problem (1) with
$\mathbf{x}\leftarrow(\mathbf{t},\mathbf{w}),\mathbf{z}\leftarrow(\mathbf{t},\mathbf{v})$.

##### Population objectives

Estimators of the form (3) have been proposed and studied in various recent
works, as we have cited in the text. Here we provide a more complete review of
different estimators and their population objectives. Classical nonparametric
methods (Hall and Horowitz,, 2005; Newey and Powell,, 2003), as well as some
recent works in the ML literature (Hartford et al.,, 2017; Xu et al.,, 2020;
Kato et al.,, 2021) are motivated as approximately optimizing (2). In
connection with (3), Zhang et al., (2020) motivated an estimator by optimizing
a kernelized statistic from Muandet et al., 2020a . The estimator has the form
of

$\hat{f}_{n}=\arg\min_{f\in\mathcal{H}}\max_{g\in\mathcal{I},\|g\|_{\mathcal{I}}=1}\frac{1}{n}\sum_{i=1}^{n}(f(x_{i})-y_{i})g(z_{i})+\lambda_{n}\|f\|_{\mathcal{H}}^{2}.$
(22)

In both (3) and (22) the (unregularized population version of the) inner loop
reduces to (2), if we replace $\mathcal{I}$ with $L_{2}(P_{z})$. Assuming
$\mathcal{I}$ well approximates the functions
$\\{E(f-f_{0}):f\in\mathcal{H}\\}$, we can also use the inner loop of (22) to
upper bound (2), as is done in Kallus et al., (2021, pp. 51-52). Singh et al.,
(2019) studied a similar estimator to (3) for kernel hypothesis spaces, by
generalizing the classical two-stage least square estimator. As noted in Wang
et al., 2021b (, App. C.1.4), the estimator is similar to (3) and (22) up to
the choices of regularizers. Kremer et al., (2022) constructed an estimator
based on the framework of empirical likelihood; while having a different
populational objective, their nonasymptotic guarantees are still established
for (2).

##### Convergence results, measures of ill-posedness

Past works on NPIV estimation often impose variants of the link and reverse
link conditions (Chen and Reiss,, 2007, Assumptions 2, 5) which, for mildly
ill-posed inverse problems,333 Mildly ill-posed inverse problems refer to
settings where the singular values of $E$ have a polynomial decay. We restrict
to such settings, as has been done in previous works (e.g., Knapik et al.,,
2011; Szabó et al.,, 2015), because subpolynomial factors are less relevant
here, where the minimax rate has a polynomial decay.  require the existence of
$\gamma,C>0$ s.t.

$C^{-1}\|T^{\gamma}f\|_{2}\leq\|Ef\|_{2}\leq C\|T^{\gamma}f\|_{2}~{}~{}\forall
f\in\mathrm{Ran}(T^{1/2}).$ (23)

The space $\mathrm{Ran}(T^{1/2})$ has the role of the hypothesis space. If it
is chosen as in (6), (23) will hold with $\gamma=1/2\alpha$. The link and
reverse link conditions require the eigenfunctions of $T$ and $E^{\top}E$ be
related in a strong sense: setting $f=\psi_{i}$, the $i$-th eigenfunction of
$T$, in the above, we find

$\|E\psi_{i}\|_{2}\asymp
e_{i}^{2\gamma}(T)\overset{(i)}{\asymp}\bar{s}_{i}=\|E\bar{\psi}_{i}\|_{2}.$
(23’)

where $e_{i}(\cdot)$ denotes the $i$-th eigenvalue of the operator, and (i)
holds for our (6), and more generally any $T$ based on which order-optimal
$L_{2}$ rates can be derived. (23’) is not strictly equivalent to requiring
$\\{\psi_{i}\\}$ to approximate $\\{\bar{\psi}_{i}\\}$ in the sense of (7); in
particular, the leading “singular vector estimates” can incur a
$\mathcal{O}(1)$ suboptimality. However, if we consider the leading
eigenfunctions (say, $\\{\psi_{i}:i<J_{n}\\}$) to be close to optimal, we can
see that (23’) imposes very strong conditions on the higher-order
$\psi_{J_{n}}$, and cannot be implied by (7) or (11) which can possibly be
satisfied by learned singular vectors.

As discussed in Chen and Reiss, (2007, Section 2.2), our source condition (5)
implies their approximability condition (Asm. 1) if we additionally require
$\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}\leq C$ to be uniformly bounded. Their
latter condition is more common in literature, although there is no
fundamental difference and our consistency results can be adapted to such
settings with little effort.

##### Alternative strategies for $L_{2}$ consistency

In the nonparametric literature, an alternative strategy for achieving $L_{2}$
consistency is to directly impose regularizations in the $L_{2}$ space
(Carrasco et al.,, 2007). Most relevant are regularization strategies that do
not require knowledge of the SVD of $E$, which includes Tikhonov
regularization:

$\hat{f}_{n}:=\operatorname*{arg\,min}_{f\in
L_{2}(P_{x})}\|\hat{E}_{n}f-\hat{g}_{n}\|_{2}^{2}+\alpha_{n}\|f\|_{2}^{2}=\underbrace{(\hat{E}_{n}^{\top}\hat{E}_{n}+\alpha_{n}I)^{-1}}_{g_{\alpha_{n}}(\hat{E}_{n}^{\top}\hat{E}_{n})}\hat{E}_{n}\hat{g}_{n},$

and the Landweber regularization which uses a different family of
$\\{g_{(\cdot)}\\}$ and corresponds to doing gradient descent _in the
$L_{2}(P_{x})$ space_ with a fixed number of iterations (and step-size)
determined by $\alpha_{n}$. The Landweber regularization is difficult to apply
in the combination of adaptive machine learning models, because to ensure a
gradient descent-based implementation matches its definition, we need to
parameterize $f\in\mathcal{H}$ using its coefficients on a predetermined
orthonormal system in $L_{2}(P_{x})$.444 Otherwise, the result after a fixed
number of iterations will have a different form involving terms related to the
parameterization map that can no longer be eliminated.  The use of such a
fixed basis, which must be truncated for a practical implementation, will
prevent the adaptation to the informative latent structures as in Ex. 2.1.
Tikhonov regularization does not have this issue, but the resulting rate will
saturate at $\beta=1$ (Carrasco et al.,, 2007). This is in contrast to our
result, which adapts to $\beta>1$ (and provides a faster, $o(n^{-1/4})$ rate
in such cases).

Closely related is the analysis of a Tikhonov-regularized estimator, where the
regularizer is defined using RKHS norms. While the resulted estimator is
similar in form to (3), the analysis relies on a very different assumption
(e.g., Mastouri et al.,, 2021, Assumption 16), which is a source condition
different from our (5):

$f_{0}\in\operatorname{Ran}(S^{\top}S)^{\beta/2},~{}~{}\text{where}~{}~{}S:\mathcal{H}\to\mathcal{I},(Sf)(z^{\prime}):=\int
k_{z}(z,z^{\prime})f(x)dP_{zx},$ (24)

where $\mathcal{H},\mathcal{I}$ are RKHSes, and $k_{z}$ is the reproducing
kernel of $\mathcal{I}$. This approach suffers from a similar saturation
issue, in which their RKHS norm rate $\|\hat{f}_{n}-f_{0}\|_{\mathcal{H}}$
cannot go beyond $\Omega(n^{-1/4})$. While such results are not directly
comparable to ours due to the different norm, note that they cannot lead to
better $L_{2}$ rates.

Another important issue lies in hyperparameter selection. While we can usually
consider find _some_ $\alpha_{n}$ that allows for consistent estimation, it is
very unclear how optimal hyperparameters can be determined, especially when we
do not have knowledge of $\beta$; in the simplified scenarios of
$\hat{E}_{n}=E$, it can be readily shown that the choice of $\alpha_{n}$ that
optimizes $\|E(\hat{f}_{n}-f_{0})\|_{2}$ is different from the choice that
optimizes $\|\hat{f}_{n}-f_{0}\|_{2}$. This is in stark contrast to our
approach which, at least in simplified scenarios and with additional
regularity assumptions on $f_{0}$, may identify order-optimal choices of
$(\lambda_{n},\alpha)$ using the statistic $\|E(\hat{f}_{n}-f_{0})\|_{2}$ (see
e.g., Szabó et al.,, 2015).

####  B.2 Inductive Bias of the Target Space (6)

In this subsection, we discuss the inductive bias of (6) and its implications.
We note that the claims made in Example 2.1 and Example 2.2 are proved as
(25), (26), (28), (29) and Claim B.3; see also the discussion around them.

##### Compositional structure

In compositional models as described by Example 2.1, the space
$\bar{\mathcal{H}}_{{\alpha}}$ only depends on $\mathbf{x}$ through the latent
variables $\bar{\mathbf{x}}$, for any $\alpha>0$. This can be proved following
the argument in Wang et al., (2022, Section 3):555 Note we do not distinguish
between functions and their $L_{2}$ equivalence classes here, as noted in
Appendix A. More rigorous claims can be established by applying the results in
Steinwart and Scovel, (2012), just as is done in Wang et al., (2022, Appendix
B). We omit the discussion which is not particularly interesting.  since we
have the eigendecomposition
$(E^{\top}E)^{\alpha}=\sum_{i=1}^{\alpha}\bar{s}_{i}^{2\alpha}\bar{\psi}_{i}\bar{\psi}_{i}^{\top},$
the space is equivalently defined as

$\bar{\mathcal{H}}_{{\alpha}}=\Big{\\{}f=\sum_{i\in
I}s_{i}^{\alpha}a_{i}\bar{\psi}_{i}:(a_{i})\in\ell_{2}(\mathbb{N})\Big{\\}},$

where $I:=\\{i\in\mathbb{N}:\bar{s}_{i}\neq 0\\}$. But all $\bar{\psi}_{i}$
(with $i\in I$) must depend on $x$ only through $\bar{x}=f_{enc,x}(x)$: this
is because we have

$\bar{\psi}_{i}(\mathbf{x})=\bar{s}_{i}^{-1}(E^{\top}\bar{\varphi}_{i})(\mathbf{x})\overset{(i)}{=}\bar{s}_{i}^{-1}\mathbb{E}(\bar{\varphi}_{i}(\mathbf{z})\mid\mathbf{x})\overset{(ii)}{=}\bar{s}_{i}^{-1}\mathbb{E}(\bar{\varphi}_{i}(\mathbf{z})\mid
f_{enc,x}(\mathbf{x}))=:(\bar{\psi}_{i}^{l}\circ f_{enc,x})(\mathbf{x}).$

In the above, (i) follows by Claim B.1 below, (ii) by the assumed data
generating process, and $\bar{\varphi}_{i}$ denotes the respective left
singular vector of $E$; And we can verify
$\|\bar{\psi}_{i}^{l}\|_{L_{2}(P_{\bar{x}})}=1$. Following this, any
$f\in\bar{\mathcal{H}}_{{\alpha}}$ will satisfy

$f=\bar{f}\circ
f_{enc,x},~{}~{}\text{where}~{}~{}\bar{f}\in\bar{\mathcal{H}}_{\alpha}^{l}:=\Big{\\{}\bar{f}=\sum_{i\in
I}s_{i}^{\alpha}a_{i}\bar{\psi}_{i}^{l}:(a_{i})\in\ell_{2}(\mathbb{N})\Big{\\}}\subset
L_{2}(P_{\bar{x}}).$ (25)

In the setting of Example 2.1, for product functions of the form
$f^{\prime}(\bar{\mathbf{x}})f^{\prime\prime}(\mathbf{x}_{\perp})$, s.t.
$\mathbb{E}f^{\prime\prime}=0$,666 The condition
$\mathbb{E}f^{\prime\prime}=0$ was unfortunately omitted in the main text,
although it does not affect any of the discussion below, as $f^{\prime\prime}$
with non-zero mean will be equivalent to a constant function.  we have

$\mathbb{E}(f^{\prime}(\bar{\mathbf{x}})f^{\prime\prime}(\mathbf{x}_{\perp})\mid\mathbf{z})=\mathbb{E}(f^{\prime}(\bar{\mathbf{x}})\mid\mathbf{z})\mathbb{E}(f^{\prime\prime}(\mathbf{x}_{\perp})\mid\mathbf{z})=\mathbb{E}(f^{\prime}(\bar{\mathbf{x}})\mid\mathbf{z})\mathbb{E}(f^{\prime\prime}(\mathbf{x}_{\perp})).$
(26)

To understand the implication of the above observation, let us take some
$\mathbf{x}_{\perp}^{\prime}=f_{\perp}^{\prime}(\mathbf{x})$ s.t.
$\mathbf{x}_{\perp}^{\prime}\perp\\!\\!\\!\perp\bar{\mathbf{x}}$, and there
exists some function s.t.
$\mathbf{x}=f_{dec,x}^{\prime}(\bar{\mathbf{x}},\mathbf{x}_{\perp}^{\prime})$.
(Note that such $\mathbf{x}_{\perp}^{\prime}$ always exist (Kallenberg,, 1997,
Prop 5.13), and (26) holds with $\mathbf{x}_{\perp}$ replaced by
$\mathbf{x}_{\perp}^{\prime}$.) Then we have
$\mathbf{x}_{\perp}^{\prime}\perp\\!\\!\\!\perp\mathbf{z}$, and there exists a
bijection between $\mathbf{x}$ and
$(\mathbf{x}_{\perp}^{\prime},\bar{\mathbf{x}})$. Therefore, for any

$\\{h_{\perp}^{(i)}:i\in\mathbb{N}\\}\subset
L_{2}(P_{\mathbf{x}_{\perp}^{\prime}}),\\{h_{\parallel}^{(i)}:i\in\mathbb{N}\\}\subset
L_{2}(P_{\bar{\mathbf{x}}})$

that constitute ONBs for their respective $L_{2}$ space, the product functions

$\\{h^{(i,j)}:=h_{\perp}^{(i)}(f_{\perp}^{\prime}(\cdot))h_{\parallel}^{(j)}(f_{enc,x}(\cdot)),~{}i,j\in\mathbb{N}\\}$

form a complete basis for $L_{2}(P_{x})$, which is orthonormal by
independence.And any $f\in L_{2}(P_{x})$ can be written as

$f=\sum_{i,j\in\mathbb{N}}a_{ij}h^{(i,j)},~{}~{}\text{where}~{}~{}(a_{ij})\in\ell_{2}(\mathbb{N}\times\mathbb{N}).$

As the above holds for arbitrary choices of basis, let us set
$h_{\perp}^{(1)}=\mathbf{1},h_{\parallel}^{(1)}=\mathbf{1}$ to be constant
functions. Then we have

$\displaystyle\mathbb{E}(h^{(i)}_{\perp}(\mathbf{x}_{\perp}^{\prime}))$
$\displaystyle=\langle h^{(i)}_{\perp},\mathbf{1}\rangle_{2}=0,~{}\forall
i>1,$ (27) $\displaystyle Ef$
$\displaystyle=E\Big{(}\sum_{i,j\in\mathbb{N}}a_{ij}h^{(i,j)}\Big{)}\overset{(i)}{=}\sum_{i,j\in\mathbb{N}}a_{ij}Eh^{(i,j)}\overset{\eqref{eq:product-E}}{=}\sum_{i,j\in\mathbb{N}}a_{ij}\mathbb{E}(h^{(i)}_{\perp}(\mathbf{x}_{\perp}^{\prime}))\mathbb{E}(h^{(j)}_{\parallel}(\bar{\mathbf{x}})\mid\mathbf{z})$
$\displaystyle\overset{\eqref{eq:iiiii}}{=}\sum_{j\in\mathbb{N}}a_{1j}\mathbb{E}(h^{(j)}_{\parallel}(\bar{\mathbf{x}})\mid\mathbf{z})\overset{(ii)}{=}\mathbb{E}\Big{(}\sum_{j\in\mathbb{N}}a_{1j}h^{(j)}_{\parallel}(\bar{\mathbf{x}})\,\Big{|}\,\mathbf{z}\Big{)},$
(28)

where (i), (ii) both follow by continuity of the operator $E$. By (28), only
functions of the form $f=\bar{f}\circ f_{enc,x}$ can be identified from the
data.

##### Regularity

We have established that $f_{0}\in\bar{\mathcal{H}}_{{\beta}}$ satisfies
$f_{0}=\bar{f}_{0}\circ f_{enc,x}$ for some
$\bar{f}_{0}\in\bar{\mathcal{H}}_{{\beta}}^{l}$. For $f_{0}$ to be efficiently
estimable, we still need $\bar{f}_{0}$, or the space
$\bar{\mathcal{H}}_{{\beta}}^{l}$, to have good regularity.777Regularity
assumptions on $f_{enc,x}$ will be introduced in Theorem 4.1. To establish
this we just need to relate the functions $\bar{\psi}_{j}^{l}$ in (25) to the
basis of well-understood RKHSes. This is easy: as we establish in Claim B.2,
$\bar{\psi}_{j}^{l}$ are simply the right singular vectors of a latent-space
conditional expectation operator $\bar{E}$, and thus we have

$\bar{\mathcal{H}}_{{\alpha}}^{l}=\operatorname{Ran}((\bar{E}^{\top}\bar{E})^{\alpha/2}),$
(29)

and the inner product is defined using $(\bar{E}^{\top}\bar{E})^{\alpha/2}$,
similar to (6). Regularity of such spaces is well-understood in literature; in
particular, for our Example 2.2 we know by Chen and Reiss, (2007, Section 6)
that $\bar{\mathcal{H}}_{{\alpha}}^{l}$ is the periodic Sobolev space, which
proves the claim made in the example.

##### Benefits, extensions, limitations

From the perspective of estimation theory, our choice to approximate
$\bar{\mathcal{H}}_{{\alpha}}$ can be motivated from the imposed source
condition (5): as discussed in Section B.1, similar assumptions have been
essential for efficient estimation; thus, $\bar{\mathcal{H}}_{{\alpha}}$ can
be viewed as a natural choice to best utilize prior knowledge of the form (5).
From a modeling perspective, the adaptivity of $\bar{\mathcal{H}}_{{\alpha}}$
to the aforementioned latent structure can also be appealing for proxy control
problems, where $\mathbf{z}$ and $\mathbf{x}$ may contain high-dimensional
components corresponding to the two measurements of the confounder, the
information about which will be fully preserved in
$(\bar{\mathbf{z}},\bar{\mathbf{x}})$ (Claim B.3).888While in the
implementation of proximal causal inference, we define the approximation
target using $\mathbf{x}^{\prime}=\mathbf{t}$ and
$\mathbf{z}=(\mathbf{t},\mathbf{v})$, it is easy to establish similar results
for that choice.  However, there are also limitations. We have discussed the
overlap variable issue in the text; here we discuss the following issues in
more detail:

  1. (i)

Direct use of $\bar{\mathcal{H}}_{{\alpha}}$ will not benefit from information
about $\mathbf{y}$, which may provide additional adaptivity. This is most
relevant in high-dimensional IV regression (Fan and Liao,, 2014; Lin et al.,,
2015) where we want to do the variable selection for a large number of
treatments, and the available instruments are informative for a large
proportion of them. In such cases, $\bar{\mathcal{H}}_{{\alpha}}$ will be
information about all such treatments, and it will be desirable to further
reduce its complexity based on information provided by $\mathbf{y}$.
In the text we have outlined a procedure that swaps the order of these two
steps: we start with a learned hypothesis space based on $\mathbf{y}$, and
“prune” it to control the modulus of continuity; this ordering can be
preferable as it avoids estimating the less relevant parts of
$\bar{\mathcal{H}}_{{\alpha}}$, and its latter step may be justified following
the reasoning in Theorem 3.1 (which should apply to subspaces of
$L_{2}(P_{x})$). Here we note a possible alternative route, which is to
conduct variable selection on $\mathbf{z}$ first, based on the correlation
structure with $\mathbf{y}$, and use the filtered instruments to define
$\bar{\mathbf{x}}$ and $\bar{\mathcal{H}}_{{\alpha}}$.

  2. (ii)

The assumption (5) for inference or predictive uncertainty quantification. We
note that similar assumptions have been employed for these purposes: the
assumptions in, _e.g._ , Kato, (2013); Chen and Christensen, (2015) are
closely related, as discussed in Chen and Reiss, (2007, p. 502). Intuitively,
(5) is more adequate when $\mathbf{z}$ is believed to be informative. However,
when $\mathbf{z}$ is markedly non-informative and cannot explain important
aspects of $\mathbf{x}$, (5) could be violated, and the use of
$\bar{\mathcal{H}}_{{\alpha}}$ may lead to erroneously small confidence
regions. At a high level, this is not dissimilar to the weak instrument
problem in linear IV (Staiger and Stock,, 1997), which required a separate
treatment. For nonparametric models, there are relatively fewer discussions on
similar (nearly) nonidentified settings, and it is especially unclear what we
should expect for general CMM problems in such settings when good hypothesis
spaces are not known a priori.

##### Deferred claims and proofs

######  Claim B.1.

We have $E^{\top}g=\mathbb{E}(g(\mathbf{z})\mid\mathbf{x}=\cdot)$ for all
$g\in L_{2}(P_{z})$.

###### Proof.

We have, for all $h\in L_{2}(P_{x})$,

$\mathbb{E}(h(\mathbf{x})(E^{\top}g)(\mathbf{x}))=\langle
h,E^{\top}g\rangle_{2}=\langle
Eh,g\rangle_{2}=\mathbb{E}(\mathbb{E}(h(\mathbf{x})\mid\mathbf{z})g(\mathbf{z}))=\mathbb{E}(h(\mathbf{x})g(\mathbf{z})),$

which fulfills the definition of conditional expectation (Kallenberg,, 1997).
∎

######  Claim B.2.

Let $\bar{\psi}_{j}^{l}$ be defined in (25),
$\bar{\mathbf{x}},\bar{\mathbf{z}}$ be defined in Example 2.1. When
$\\{\bar{s}_{j}\\}$ are strictly decreasing, $\bar{\psi}_{j}^{l}$ must be
right singular vectors of the operator

$\bar{E}:L_{2}(P_{\bar{x}})\to
L_{2}(P_{\bar{z}}),\bar{f}\mapsto\mathbb{E}(\bar{f}(\bar{\mathbf{x}})\mid\bar{\mathbf{z}}=\cdot).$

###### Proof.

Let $\\{\bar{\psi}^{\prime}_{j}\\}$ be the singular vectors of $\bar{E}$, so
that they form an ONB for $L_{2}(P_{\bar{x}})$. It is thus clear that
$\\{\bar{\psi}^{\prime}_{j}\circ f_{enc,x}\\}$ form an ONS in $L_{2}(P_{x})$.
We claim that for all $J\in\mathbb{N}$,
$\\{\psi_{j}\leftarrow\bar{\psi}^{\prime}_{j}\circ f_{enc,x}\\}$ maximizes the
variational objective
$\mathcal{L}(\\{\psi_{j}\\}_{j=1}^{J}):=\sum_{j=1}^{J}\|E\psi_{j}\|_{2}^{2},$
where $\\{\psi_{j}\\}$ ranges over all orthonormal systems. As the singular
values are strictly decreasing, the optima of the above objective must define
the same span as the true singular vectors, and the proof will complete by the
arbitrariness of $J$. But the optimality is clear given (28),999and the fact
that
$\mathbb{E}(f(\mathbf{x})\mid\mathbf{z})=\mathbb{E}(f(\mathbf{x})\mid\bar{\mathbf{z}})a.s.$
in which we can choose $\\{\bar{\psi}^{\prime}_{j}\\}$ as
$\\{h^{(i)}_{\parallel}\\}$. ∎

######  Claim B.3.

Let $\mathbf{z}=(\mathbf{t},\mathbf{v}),\mathbf{x}=(\mathbf{t},\mathbf{w})$ be
as in Example B.1. Then we have
$\mathbb{E}(f(\mathbf{u})\mid\mathbf{x})=\mathbb{E}(f(\mathbf{u})\mid\bar{\mathbf{x}}),\mathbb{E}(f(\mathbf{u})\mid\mathbf{z})=\mathbb{E}(f(\mathbf{u})\mid\bar{\mathbf{z}}).$

###### Proof.

Any bounded linear operator is injective if and only if its adjoint has a
dense image (see e.g. Steinwart and Christmann,, 2008, p. 500). Therefore, the
completeness assumption in Ex. B.1 implies both
$\operatorname{Ran}E_{x|ut}=\operatorname{Ran}E_{ut|x}^{\top}$ and
$\operatorname{Ran}E_{z|ut}=\operatorname{Ran}E_{ut|z}^{\top}$ are dense in
$L_{2}(P_{ut})$.101010 The equalities follow by the same reasoning as Claim
B.1; $E_{x|ut}$ refers to the conditional expectation operator from
$L_{2}(P_{x})$ to $L_{2}(P_{ut})$, and $E_{z|ut}$ is defined similarly.  Now,
for any $f\in L_{2}(P_{u})\subset L_{2}(P_{ut})$ in the second equality, we
can take $h_{n}\in L_{2}(P_{x})$ s.t. $\|E_{x|ut}h_{n}-f\|_{L_{2}(P_{ut})}\to
0$. And we have

$\displaystyle E_{x|z}h_{n}$
$\displaystyle=\mathbb{E}(h_{n}(\mathbf{t},\mathbf{w})\mid\mathbf{t},\mathbf{v})\overset{(i)}{=}\mathbb{E}(\mathbb{E}(h_{n}(\mathbf{t},\mathbf{w})\mid\mathbf{t},\cancel{\mathbf{v},}\mathbf{u})\mid\mathbf{t},\mathbf{v})=E_{ut|z}(E_{x|ut}h_{n}).$
$\displaystyle\|E_{x|z}h_{n}-E_{u|z}f\|_{2}$
$\displaystyle=\|E_{ut|z}(E_{x|ut}h_{n})-E_{ut|z}f\|_{2}\leq\|E_{ut|z}\|\|E_{x|ut}h_{n}-f\|_{2}\to
0.$

In the above, (i) follows by the assumed conditional independence in Ex. B.1.
Since we also have $E_{x|z}h_{n}=E_{x|\bar{z}}h_{n}$ by the condition in Ex.
2.1, and

$\|E_{x|\bar{z}}h_{n}-E_{x|\bar{z}}h_{m}\|_{2}\leq\|E_{x|z}h_{n}-E_{x|z}h_{m}\|_{2}\leq\|E_{ut|z}\|\|E_{x|ut}h_{n}-E_{x|ut}h_{m}\|_{2}\to
0,\quad(\text{as }\min\\{n,m\\}\to\infty)$

we conclude there exists some $g\in L_{2}(P_{\bar{z}})$, which we can take as
the limit of $E_{x|\bar{z}}h_{n}\in L_{2}(P_{\bar{z}})$, s.t.

$\mathbb{E}(g(\bar{\mathbf{z}})-\mathbb{E}(f(\mathbf{u})\mid\mathbf{z}))^{2}=0.$

This proves the second equality in the claim. The first equality can be proved
similarly. ∎

####  B.3 Related Work: Representation Learning

##### Multi-view redundancy

It has been established in various settings that, given two views
$(\mathbf{x},\mathbf{z})$ of a latent variable $\mathbf{v}$, self-supervised
learning procedures can learn representations that are suitable for predicting
functions of $\mathbf{v}$, or more generally, random variables that can be
well-estimated using $\mathbf{x}$ and $\mathbf{z}$ (Foster et al.,, 2008;
Arora et al.,, 2019; Lee et al.,, 2020; Tosh et al.,, 2021). While the goal
appears different from our work, it is connected through the observation in
Tosh et al., (2021), that accurate estimation of the density ratio
$p(x,z)/p(x)p(z)$ leads to an infinite-dimensional representation that enjoys
a small approximation error. As remarked in their p. 13, Tosh et al., (2021)
did not make an attempt to construct compact finite-dimensional
approximations, and in the general case only provided a $n$-dimensional
representation, the estimability of which is also unclear; this is different
from our $\mathcal{O}(n^{1/2p})$-dimensional approximation (Section E.1), from
which we were able to establish complete learning rates.

As noted in the text, our results for representation learning are closest to
HaoChen et al., (2021), as we started with the same algorithm; we derived
different results which are useful in different contexts. Other works in this
literature also tend to have different assumptions, due to their different
goal: Arora et al., (2019); Balestriero and LeCun, (2022) considered
homogenous sample space ($\mathcal{Z}=\mathcal{X}$) with discrete latents,
which lead to a different eigenspectrum and is more suitable for
classification problems; Lee et al., (2020) assumed it is easy to reconstruct
one of the views using the other, which is suitable when its dimensionality is
low, or there is a large number of unlabeled samples.

We note that similar ideas have also appeared in recent works in reinforcement
learning (Zhang et al.,, 2022; Qiu et al.,, 2022), which studied contrastive
estimation of a Bellman operator. However, existing works in this direction
only use the Bellman operator to solve a forward problem, which is
significantly less challenging than our inverse problem setting. (On the flip
side, they require convergence in stronger norms.) Similar inverse problems
arise in relation to confounded MDPs (Kallus et al.,, 2021; Fu et al.,, 2022);
it remains future work to investigate kernel learning in such settings.

##### SVD, CCA and HSIC

Michaeli et al., (2016) formulated the SVD problem as a nonparametric analogy
of canonical correlation analysis (CCA), thereby connecting to the parametric
analysis in Foster et al., (2008). Here we connect this problem to a
maximization of the Hilbert-Schmidt Independence Criterion (HSIC, Gretton et
al.,, 2005), thereby connecting to the kernel learning algorithm Li et al.,
2021b , which was designed for self-supervised learning:

Consider a compositional model similar to Example 3.1, and suppose we know the
structure of the latent-space distribution
$P_{\bar{\mathbf{x}}\bar{\mathbf{z}}}$, and thus that of the “latent-space
RKHS”; that is, we know the function space $\bar{\mathcal{H}}_{latent,\alpha}$

$\bar{\mathcal{H}}_{{\alpha}}:=\\{\bar{f}\circ
f_{enc,x},\bar{f}\in\bar{\mathcal{H}}_{latent,\alpha}\\},$

as well as its (assumed) RKHS structure. Then we know the reproducing kernel
of $\bar{\mathcal{H}}_{{\alpha}}$ must have the form of

$\bar{k}_{\alpha,x}(x,x^{\prime})=\bar{k}_{\alpha,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bar{x}}}(f_{enc,x}(x),f_{enc,x}(x^{\prime})),$

where $\bar{k}_{latent,\alpha}$ is known;111111e.g., in Example 2.2 we may
know that $\bar{k}_{latent,\alpha}$ is a Matérn kernel on torus with an known
order. and it remains to learn $f_{enc,x}$ from data. Similarly, for
$\mathbf{z}$ we know that we need to learn the function $f_{enc,z}$ in

$\bar{k}_{\alpha,z}(z,z^{\prime})=\bar{k}_{\alpha,{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bar{z}}}(f_{enc,z}(z),f_{enc,z}(z^{\prime})).$

Now, suppose in addition that the kernel $\bar{k}_{latent,\alpha}$ is
stationary, and the marginal distributions $P_{\bar{x}},P_{\bar{z}}$ are
uniform, so that the top Mercer eigenfunction is the constant function
$\mathbf{1}$, and the kernel embedding, which can be identified using the
scaled eigenfunctions as

$\displaystyle\phi_{x}$
$\displaystyle=(\sqrt{\bar{\lambda}_{\alpha,x}^{(1)}}\bar{\psi}^{(1)}_{x}(x),\ldots,\sqrt{\bar{\lambda}_{\alpha,x}^{(m)}}\bar{\psi}^{(m)}_{x}(x),\ldots)$
$\displaystyle=(\sqrt{\bar{\lambda}_{\alpha,x}^{(1)}}\bar{\psi}_{\bar{x}}^{(1)}(f_{enc,x}(x)),\ldots,\sqrt{\bar{\lambda}_{\alpha,x}^{(m)}}\bar{\psi}_{\bar{x}}^{(m)}(f_{enc,x}(x)),\ldots)\in\ell_{2}(\mathbb{N}),$

satisfies

$\mathbb{E}_{\mathbf{x}\sim
P_{x}}\phi_{\mathbf{x}}=\mathbb{E}_{\bar{\mathbf{x}}\sim
P_{\bar{x}}}(\sqrt{\bar{\lambda}_{\alpha,x}^{(1)}}\bar{\psi}_{\bar{x}}^{(1)}(\bar{\mathbf{x}}),\ldots)=(1,0,\ldots,0,\ldots).$

where the last equality follows from the fact that

$\bar{\psi}_{\bar{x}}^{(1)}=\mathbf{1},~{}~{}\mathbb{E}\bar{\psi}_{\bar{x}}^{(i)}=\langle\bar{\psi}_{\bar{x}}^{(i)},\bar{\psi}_{\bar{x}}^{(1)}\rangle_{2}=0~{}\forall
i>1.$

Thus, the HSIC using the product kernel reduces to

$\mathrm{HSIC}_{\bar{k}_{\alpha,x}\otimes\bar{k}_{\alpha,z}}=\|\mathbb{E}(\phi_{x}\otimes\phi_{z})-(\mathbb{E}\phi_{x}\otimes\mathbb{E}\phi_{z})\|_{\mathrm{HS}}^{2}\overset{(i)}{=}\|\mathbb{E}(\phi_{x}\otimes\phi_{z})\|_{\mathrm{HS}}^{2}-1\overset{(ii)}{=}\mathrm{Tr}(\Lambda_{z}\bar{\Psi}_{z}^{\top}E\bar{\Psi}_{x}\Lambda_{x}\bar{\Psi}_{x}^{\top}E^{\top}\bar{\Psi}_{z}),$

In the above, (i) follows from the expression of kernel mean embedding derived
above (and a similar result for $z$), and (ii) follows by basic linear
algebra; and

$\bar{\Psi}_{x}:\ell_{2}(\mathbb{N})\to
L_{2}(P_{x}),(a_{i})\mapsto\sum_{i=1}^{\infty}a_{i}\bar{\psi}_{x}(\cdot)$

can be viewed as an “infinitely tall matrix” obtained by “stacking” all
eigenfunctions, and $\bar{\Psi}_{z}$ is defined similarly;
$\Lambda_{x}:\ell_{2}(\mathbb{N})\to\ell_{2}(\mathbb{N})$ is an “infinitely
large diagonal matrix” consisting of Mercer eigenvalues. With some
effort121212 While we do not detail the proof here, it consists of plugging in
the optimal choice of $U$ for (30), which must be eigenfunctions for the
operator $E^{\top}V\Lambda_{z}V^{\top}E$; and applying a Mathematics
StackExchange answer linked here.  we can prove that, when the Mercer
eigenvalues are fixed to any decreasing sequences,
$(\bar{\Psi}_{z},\bar{\Psi}_{x})$ constitutes the unique maximizer for the
objective

$(V,U)\mapsto\mathrm{Tr}(\Lambda_{z}V^{\top}EU\Lambda_{x}U^{\top}E^{\top}V),$
(30)

where $(V,U)$ ranges over all unitary transforms.

While the above derivations provided nice intuitions, and connect to the
practical self-supervised learning algorithm of Li et al., 2021b , it is
unclear if similar algorithms can be applied to solve the SVD: in practice, we
find it impossible to constrain the Mercer eigenvalues of the kernels, which
not only depends on the assumed form of the latent-space kernels
$(\bar{k}_{\alpha,\bar{x}},\bar{k}_{\alpha,\bar{z}})$, but also on the
marginal distribution of the learned latents. The latter can be altered in the
learning process, which leads to altered values of $(\Lambda_{x},\Lambda_{z})$
and subsequently that of the variational objective.

###  Appendix C Deferred Proofs: Section 3

The following facts will be used throughout the proofs:

$\|E\|=1,~{}~{}\|Ef\|_{2}=\langle f,E^{\top}Ef\rangle_{2}^{1/2}=:\langle
f,Tf\rangle_{2}^{1/2}=\|T^{1/2}f\|_{2}.$ (31)

We also recall the conventions in Appendix A.

####  C.1 Proof for Lemma 3.1

We prove the following generalization of the lemma. Note that its claim (i)
generalizes Lemma 3.1 because condition is implied by (11): the latter implies
the weaker operator norm bound $\|E-\tilde{E}\|\leq\epsilon_{n}$, which
implies (11’) with $c=1$.

######  Lemma C.1.

Let $\beta\geq 1$, $\bar{f}$ satisfy (5), and
$\mathcal{H}=\operatorname{Ran}\tilde{T}^{\alpha/2}$ as in (10). Then

  1. (i)

If $\alpha=1$, and $\tilde{T}$ satisfies

$c^{-1}(\|Ef\|_{2}-\epsilon_{n})\leq\|\tilde{T}^{1/2}f\|_{2}\leq
c(\|Ef\|_{2}+\epsilon_{n}),~{}~{}~{}\forall\|f\|_{2}=1$ (11’)

for some $c\geq 1,\epsilon_{n}>0$, there will exist $\tilde{f}\in\mathcal{H}$
s.t.

$\|\tilde{f}\|_{\mathcal{H}}\leq
c_{\alpha}\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}},~{}~{}\|\tilde{f}-\bar{f}\|_{2}\leq
c_{\alpha}\epsilon_{n}^{\alpha\wedge
1}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}},~{}~{}\|E(\tilde{f}-\bar{f})\|_{2}\leq
c_{\alpha}\epsilon_{n}^{(\alpha+1)\wedge
2}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}}.$

  2. (ii)

For any $\alpha>0$, there will exist $\tilde{f}\in\mathcal{H}$ s.t.
$\|\tilde{f}\|_{\mathcal{H}}\leq
c_{\alpha}\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}},\|\tilde{f}-\bar{f}\|_{2}\leq\|T^{\alpha/2}-\tilde{T}^{\alpha/2}\|\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}}.$

  3. (iii)

In particular, if $\tilde{T}$ satisfies (11), there will exist
$\tilde{f}\in\mathcal{H}$ s.t.

$\|\tilde{f}\|_{\mathcal{H}}\leq
c_{\alpha}\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}},~{}~{}\|\tilde{f}-\bar{f}\|_{2}\leq
c_{\alpha}\epsilon_{n}^{\alpha\wedge
1}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}}.$

  4. (iv)

In any case of (i)-(iii) above, we have, for all $f\in\mathcal{H}$, the
existence of $f^{\prime}\in\bar{\mathcal{H}}_{{\alpha}}$ s.t.

$\|f^{\prime}\|_{\bar{\mathcal{H}}_{{\alpha}}}\leq
c_{\alpha}\|f\|_{\mathcal{H}},~{}~{}\|f^{\prime}-f\|_{2}\leq
c_{\alpha}\epsilon_{n}^{\alpha\wedge 1}\|f\|_{\mathcal{H}}.$ (12’)

###### Proof.

In all cases, it suffices to prove the claim with $\beta$ replaced by
$\alpha$, since (5) holds with smaller exponents, and we have

$\|\bar{f}\|_{\bar{\mathcal{H}}_{{\alpha}}}=\|T^{-\alpha/2}\bar{f}\|_{2}\leq\|T^{(\beta-\alpha)/2}\|\|T^{-\beta/2}\bar{f}\|_{2}=\|E\|^{\beta-\alpha}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}}=\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}},$
(32)

where $T:=E^{\top}E$. We also assume without loss of generality that
$\epsilon_{n}<1$. Now we prove the three cases in turn.

##### Proof for claim (i)

By (5), there exists $g_{0}\in L_{2}(P(dx))$ s.t. $\bar{f}=T^{\alpha/2}g_{0}$.
Let $K$ be the largest integer s.t. $\bar{s}_{K}>2\epsilon_{n}$, and define

$P_{K}:=\sum_{i=1}^{K}\bar{\psi}_{i}\otimes\bar{\psi}_{i},~{}g_{\parallel}:=P_{K}g_{0},~{}f_{\parallel}:=T^{\alpha/2}g_{\parallel}.$

Then

$\displaystyle\|f_{\parallel}\|_{\bar{\mathcal{H}}_{{\alpha}}}$
$\displaystyle=\|g_{\parallel}\|_{2}\leq\|g\|_{2}=\|\bar{f}\|_{\bar{\mathcal{H}}_{{\alpha}}},$
(33) $\displaystyle\|f_{\parallel}-\bar{f}\|_{2}$
$\displaystyle=\|T^{\alpha/2}(g_{\parallel}-g_{0})\|_{2}\leq\bar{s}_{K+1}^{\alpha}\|g_{0}\|_{2}<(2\epsilon_{n})^{\alpha}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\alpha}}},$
(34) $\displaystyle\|E(f_{\parallel}-\bar{f})\|_{2}$
$\displaystyle=\|T^{(\alpha+1)/2}(g_{\parallel}-g_{0})\|_{2}<(2\epsilon_{n})^{\alpha+1}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\alpha}}},$
(35)

showing that it suffices to construct an approximation for $f_{\parallel}$.
For this purpose, first observe that for all $g\in\operatorname{Ran}P_{K}$
with $\|g\|_{2}=1$, we have $\|Eg\|_{2}=\|T^{1/2}g\|_{2}>2\epsilon_{n},$ and
thus (11’) implies
$\frac{1}{4c^{2}}g^{\top}Tg<g^{\top}\tilde{T}g<\frac{9c^{2}}{4}g^{\top}Tg,$
and

$\displaystyle\frac{1}{4c^{2}}P_{K}TP_{K}\prec P_{K}\tilde{T}P_{K}$
$\displaystyle\prec\frac{9c^{2}}{4}P_{K}TP_{K}.$

Thus, there exists $c_{\alpha}^{\prime}>0$ s.t.131313We have
$c_{\alpha}^{\prime}\leq\left(2c\right)^{\alpha}$; when (11) holds,
$c_{\alpha}^{\prime}\leq 2^{\alpha}$ only depends on $\alpha$.

$\displaystyle\|\tilde{T}^{\frac{\alpha}{2}}P_{K}(P_{K}\tilde{T}^{\alpha}P_{K})^{-1}f_{\parallel}\|_{2}=\|(P_{K}\tilde{T}^{\alpha}P_{K})^{-1/2}f_{\parallel}\|_{2}<c_{\alpha}^{\prime}\|(P_{K}T^{\alpha}P_{K})^{-1/2}f_{\parallel}\|_{2}=c_{\alpha}^{\prime}\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}.$
(36)

Consider
$\tilde{f}:=\tilde{T}^{\alpha}P_{K}(P_{K}\tilde{T}^{\alpha}P_{K})^{-1}f_{\parallel}.$
By (36), $\|\tilde{f}\|_{\mathcal{H}}=\|g^{\prime}\|_{2}$ fulfills the claimed
bound. And we have

$\displaystyle\|\tilde{f}-\bar{f}\|_{2}$
$\displaystyle\leq\|\tilde{f}-f_{\parallel}\|_{2}+\|f_{\parallel}-\bar{f}\|_{2}$
$\displaystyle=\|(I-P_{K})\tilde{T}^{\alpha}P_{K}(P_{K}\tilde{T}^{\alpha}P_{K})^{-1}f_{\parallel}\|_{2}+\|f_{\parallel}-\bar{f}\|_{2}$
$\displaystyle\leq\|(I-P_{K})\tilde{T}^{\alpha/2}\|\|\tilde{T}^{\alpha/2}P_{K}(P_{K}\tilde{T}P_{K})^{-\alpha}f_{\parallel}\|_{2}+\|f_{\parallel}-\bar{f}\|_{2}$
$\displaystyle\leq\|(I-P_{K})\tilde{T}^{\alpha/2}\|\cdot
c_{\alpha}^{\prime}\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}+(2\epsilon_{n})^{\alpha}\|f\|_{\bar{\mathcal{H}}_{{\alpha}}},$
(by (34), (36)) $\displaystyle\|E(\tilde{f}-\bar{f})\|_{2}$
$\displaystyle\leq\|E(\tilde{f}-f_{\parallel})\|_{2}+\|E(f_{\parallel}-\bar{f})\|_{2}$
$\displaystyle\leq
c_{\alpha}^{\prime}\|E(I-P_{K})\tilde{T}^{\alpha/2}\|\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}+(2\epsilon_{n})^{\alpha+1}\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}$
(by (35), (36))
$\displaystyle=c_{\alpha}^{\prime}\|E(I-P_{K})\cdot(I-P_{K})\tilde{T}^{\alpha/2}\|\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}+(2\epsilon_{n})^{\alpha+1}\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}$
$\displaystyle\leq
c_{\alpha}^{\prime}s_{K+1}\|(I-P_{K})\tilde{T}^{\alpha/2}\|\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}+(2\epsilon_{n})^{\alpha+1}\|f\|_{\bar{\mathcal{H}}_{{\alpha}}}.$

Therefore, it remains to establish that

$\|(I-P_{K})\tilde{T}^{\alpha/2}\|\leq
c_{\alpha}^{\prime\prime}\epsilon_{n}^{\min\\{\alpha,1\\}},$ (37)

for some constant $c_{\alpha}^{\prime\prime}>0$. Observe that

$\displaystyle\|(I-P_{K})\tilde{T}^{1/2}\|$
$\displaystyle=\|\tilde{T}^{1/2}(I-P_{K})\|=\sup_{\|g\|_{2}=1}\|\tilde{T}^{1/2}(I-P_{K})g\|_{2}\overset{\eqref{eq:T-cond-
relaxed}}{\leq}\sup_{\|g\|_{2}=1}c(\|E(I-P_{K})g\|_{2}+\epsilon_{n})$
$\displaystyle=c(\bar{s}_{K+1}+\epsilon_{n})<3c\epsilon_{n},$

which proves (37), and thus the claim (i).

##### Proof for Claim (ii)

Consider $\tilde{f}:=\tilde{T}^{\alpha/2}T^{-\alpha/2}\bar{f}$. Then we have

$\displaystyle\|\tilde{f}\|_{\mathcal{H}}$
$\displaystyle=\|T^{-\alpha/2}\bar{f}\|_{2}\overset{\eqref{eq:lem-gtrkhs-norm-
bound}}{\leq}\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}},$ (38)
$\displaystyle\|\tilde{f}-\bar{f}\|_{2}$
$\displaystyle\leq\|\tilde{T}^{\alpha/2}-T^{\alpha/2}\|\|T^{-\alpha/2}\bar{f}\|_{2}\leq\|\tilde{T}^{\alpha/2}-T^{\alpha/2}\|\|\bar{f}\|_{\bar{\mathcal{H}}_{{\beta}}}.$
(39)

##### Proof for Claim (iii)

It remains to bound $\|\tilde{T}^{\alpha/2}-T^{\alpha/2}\|$ using (11). First
note that (11) implies

$\|T^{1/2}-\tilde{T}^{1/2}\|\leq\|(E^{\top}E)^{1/2}-(\tilde{E}^{\top}\tilde{E})^{1/2}\|_{\mathrm{HS}}\overset{(i)}{\leq}\sqrt{2}\|E-\tilde{E}\|_{\mathrm{HS}}\leq\sqrt{2}\epsilon_{n},$
(40)

where (i) can be found as Bhatia, (2013, Eq. X.24). The result for $\alpha=1$
thus follows by (40). When $\alpha\in(0,1)$, we have

$\|\tilde{T}^{\alpha/2}-T^{\alpha/2}\|\overset{(i)}{\leq}\||\tilde{T}^{1/2}-T^{1/2}|\|^{\alpha}=\|\tilde{T}^{1/2}-T^{1/2}\|^{\alpha}\leq
2^{\alpha/2}\epsilon_{n}^{\alpha},$

where (i) is Birman et al., (1975), and $|\cdot|$ denotes the absolute value
map. For $\alpha>1$, first note that
$\max\\{\|\tilde{T}\|,\|T\|\\}\leq\|T\|+2\epsilon_{n}=\|E\|^{2}+2\epsilon_{n}\leq
3$. Thus, we have

$\|T^{\alpha/2}-\tilde{T}^{\alpha/2}\|=\|f_{\alpha}(T^{1/2})-f_{\alpha}(\tilde{T}^{1/2})\|\overset{(i)}{=}c\|f_{\alpha}\|_{B^{1}_{\infty,1}}\|T^{1/2}-\tilde{T}^{1/2}\|\overset{(ii)}{\leq}3^{\alpha+1}c\alpha\epsilon_{n}.$

In the above, $f_{\alpha}(\cdot)$ equals $x^{\alpha}$ on the interval $[0,3]$,
and is extended to the real line to satisfy the Besov norm bound
$\|f_{\alpha}\|_{B^{1}_{\infty,1}}\leq\|f_{\alpha}\|_{\infty}+\|f_{\alpha}^{\prime}\|_{\infty}\leq
2\alpha\cdot 3^{\alpha}$; (i) follows by Aleksandrov and Peller, (2016,
Theorem 1.6.1), and $c$ is the constant therein; (ii) follows by (40) and our
bound for $\|f_{\alpha}\|_{B^{1}_{\infty,1}}$. Combining, we have

$\|\tilde{T}^{\alpha/2}-T^{\alpha/2}\|\leq
c_{\alpha}\epsilon_{n}^{\alpha\wedge 1},$

for any $\alpha>0$. Plugging back to (38)-(39) completes the proof.

##### Proof for Claim (iv)

This is a symmetry version of (12) and can be proved by repeating the original
proof for each case, with all occurrences of $\tilde{T}$ and $T$ exchanged.
The symmetry is obvious for case (ii) and (iii); for for case (i), its
condition (11’) is equivalent to (recall (31))
$c^{-1}(\|T^{1/2}f\|_{2}-\epsilon_{n})\leq\|\tilde{T}^{1/2}f\|_{2}\leq
c(\|T^{1/2}f\|_{2}+\epsilon_{n}),$ which implies the symmetric condition of

$c^{-1}(\|\tilde{T}^{1/2}f\|_{2}-c\epsilon_{n})\leq\|T^{1/2}f\|_{2}\leq
c(\|\tilde{T}^{1/2}f\|_{2}+c\epsilon_{n}).$

This completes the proof. ∎

######  Remark C.1.

We note that exponentially growing constants w.r.t. regularity parameters like
$\alpha$ are common in the kernel literature. The saturation of the bound at
$\alpha>1$ is likely due to our lack of further assumptions on $\tilde{T}$.

####  C.2 Proof for Theorem 3.1

We prove a more general version of the theorem, with (11) replaced by the more
general (11’).

By Lemma C.1, we always have

$\|\tilde{f}\|_{\mathcal{H}}\leq C\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}.$
(41)

for some $C>0$ that only depends on $\alpha$ and the constant in (11’). Let us
restrict to $f$ s.t.

$\|f-\tilde{f}\|_{2}\geq\|\tilde{f}-f_{0}\|_{2},$ (42)

since other $f$ cannot possibly violate the claimed bound for
$\omega^{\prime}_{n}$: we would have $\|f-f_{0}\|_{2}^{2}\leq
4\|\tilde{f}-f_{0}\|_{2}^{2}$.

Recall the inequalities

$2(\|a\|_{2}^{2}+\|b\|_{2}^{2})\geq\|a+b\|^{2}\geq\|a\|^{2}+\|b\|^{2}-2\|a\|\|b\|\geq(1-\zeta^{2})\|a\|^{2}-(\zeta^{-2}-1)\|b\|^{2},$

which hold for any $\zeta>0$ and Hilbert norm $\|\cdot\|$. Now, by the assumed
condition of functions that appear in $\omega^{\prime}_{n}$, (41) and the
above, we have, for all $f\in\mathcal{H}$,

$\displaystyle\|E(f-\tilde{f})\|_{2}^{2}+\lambda_{n}\|f-\tilde{f}\|_{\mathcal{H}}^{2}$
$\displaystyle\leq
2\|E(f-f_{0})\|_{2}^{2}+2\lambda_{n}\|f\|_{\mathcal{H}}^{2}+2\|E(f_{0}-\tilde{f})\|_{2}^{2}+2\lambda_{n}\|\tilde{f}\|_{\mathcal{H}}^{2}$
$\displaystyle\leq
2\delta_{n}^{2}+2\|E(f_{0}-\tilde{f})\|_{2}^{2}+2C^{2}\lambda_{n}\|f_{0}\|_{\bar{\mathcal{H}}_{{\beta}}}^{2}.$

And by (42), we have

$\displaystyle\|f-f_{0}\|_{2}^{2}$ $\displaystyle\leq
2\|f-\tilde{f}\|_{2}^{2}+2\|\tilde{f}-f_{0}\|_{2}^{2}\leq
4\|f-\tilde{f}\|_{2}^{2}.$

By the two displays above, it suffices to establish that for some constant
$c_{\alpha}>0$, we have

$\displaystyle\sup_{f\in{\mathcal{H}}}\frac{\|f-\tilde{f}\|_{2}^{2}}{\|E(f-\tilde{f})\|_{2}^{2}+\lambda_{n}\|f-\tilde{f}\|_{\mathcal{H}}^{2}}\leq
c_{\alpha}(\max\\{\lambda_{n}^{1/(1+\alpha)},\lambda_{n}\epsilon_{n}^{-2\alpha}\\})^{-1},$

or equivalently,

$\displaystyle\inf_{f^{\prime}\in{\mathcal{H}},\|f^{\prime}\|_{2}=1}(\|Ef^{\prime}\|_{2}^{2}+\lambda_{n}\|f^{\prime}\|_{\mathcal{H}}^{2})\geq
c_{\alpha}^{-1}\min\\{\lambda_{n}^{1/(1+\alpha)},\lambda_{n}\epsilon_{n}^{-2\alpha}\\},$
(43)

after which the proof is complete.

Observe that for any $\|f^{\prime}\|_{2}=1$, and any $\zeta\in(1/\sqrt{2},1)$,
we have

$\displaystyle\|Ef^{\prime}\|_{2}^{2}+\lambda_{n}\|f^{\prime}\|_{\mathcal{H}}^{2}$
$\displaystyle\overset{\eqref{eq:T-cond-
relaxed}}{\geq}(c^{-1}\|\tilde{T}^{1/2}f^{\prime}\|_{2}-c\epsilon_{n})^{2}+\lambda_{n}\|f^{\prime}\|_{\mathcal{H}}^{2}$
$\displaystyle\geq(1-\zeta^{2})\|c^{-1}\tilde{T}^{1/2}f^{\prime}\|_{2}^{2}+\lambda_{n}\|f^{\prime}\|_{\mathcal{H}}^{2}-(\zeta^{-2}-1)c^{2}\epsilon_{n}^{2}$
$\displaystyle\overset{\eqref{eq:H-defn}}{=}\langle
f^{\prime},((1-\zeta^{2})c^{-2}\tilde{T}+\lambda_{n}\tilde{T}^{-\alpha})f^{\prime}\rangle_{2}-(\zeta^{-2}-1)c^{2}\epsilon_{n}^{2}$
$\displaystyle\geq\langle
f^{\prime},((1-\zeta^{2})c^{-2}\tilde{T}+\lambda_{n}\tilde{T}^{-\alpha})f^{\prime}\rangle_{2}-2(1-\zeta^{2})c^{2}\epsilon_{n}^{2},$
(44)

Since $\|f^{\prime}\|_{2}=1$, the first term above can be bounded by a
smallest eigenvalue: denote by $\\{e_{i}\\}$ the eigenvalues of $\tilde{T}$,
and define $u:=1-\zeta^{2}$, then we have

$\displaystyle\phantom{=}\inf_{\|f^{\prime}\|_{2}=1}\langle
f^{\prime},((1-\zeta^{2})c^{-2}\tilde{T}+\lambda_{n}\tilde{T}^{-\alpha})f^{\prime}\rangle_{2}-2(1-\zeta^{2})c^{2}\epsilon_{n}^{2}$
$\displaystyle=\inf_{i\in\mathbb{N}}(uc^{-2}e_{i}+\lambda_{n}e_{i}^{-\alpha})-2uc^{2}\epsilon_{n}^{2}$
$\displaystyle\geq\inf_{a>0}(ua+\lambda_{n}c^{-2\alpha}a^{-\alpha})-2uc^{2}\epsilon_{n}^{2}$
$\displaystyle=2u^{\frac{\alpha}{\alpha+1}}(c^{-2\alpha}\lambda_{n})^{\frac{1}{\alpha+1}}-2uc^{2}\epsilon_{n}^{2},~{}~{}\text{for
all }u\in(0,1/2).$

The choice of

$u:=\frac{1}{2}\min\left\\{1,c^{-2\alpha}\lambda_{n}(c\epsilon_{n})^{-2(\alpha+1)}\right\\}$

produces the bound

$\|Ef^{\prime}\|_{2}^{2}+\lambda_{n}\|f^{\prime}\|_{\mathcal{H}}^{2}\geq(2^{\frac{1}{\alpha+1}}-1)\min\\{c^{-2\alpha/(\alpha+1)}\lambda_{n}^{1/(\alpha+1)},c^{-4\alpha}\lambda_{n}\epsilon_{n}^{-2\alpha}\\}.$

This completes the proof of (43), and thus the theorem.∎

Recall the constant $c=1$ when (11) holds. And as a sanity check, we can
verify the example constructed for maximizing (9) does not violate (43): for
$\tilde{E}=\sum_{i}s_{i}\psi_{i}\otimes\psi_{i}$ to satisfy the norm
condition, we must have $s_{i}\leq\|E\psi_{i}\|_{2}+\epsilon_{n}$, which
implies a lower bound for the RKHS norm.

###  Appendix D Deferred Proofs: Representation Learning

####  D.1 Proof for Lemma 4.1

For (17), the first equivalence holds because

$\displaystyle\mathcal{D}_{\chi^{2},\mathrm{lb}}({h})+1$
$\displaystyle=\mathbb{E}_{P_{zx}}h(\mathbf{z},\mathbf{x})-\mathbb{E}_{P_{z}\otimes
P_{x}}h^{2}(\mathbf{z},\mathbf{x})=\mathbb{E}_{P_{z}\otimes
P_{x}}\left(\frac{dP_{zx}}{d(P_{z}\otimes P_{x})}h-h^{2}\right)=2\langle
h_{0},h\rangle_{L_{2}(P_{z}\otimes P_{x})}-\|h\|^{2}_{L_{2}(P_{z}\otimes
P_{x})}$ $\displaystyle=-\|h-h_{0}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+\|h_{0}\|_{L_{2}(P_{z}\otimes P_{x})}^{2},$

where the first equality is derived in the text. It remains to prove
$\|\tilde{E}-E\|_{HS}=\|h-h_{0}\|_{2}.$ For this purpose we first claim that
for all $f\in L_{2}(P_{x})$, we have

$(Ef)(\mathbf{z})=\int h_{0}(x,\mathbf{z})f(x)P_{x}(dx).~{}~{}a.s.$ (45)

To prove this, observe that for any $g\in L_{2}(P_{z})$, we have

$\displaystyle\langle
Ef,g\rangle_{2}=\mathbb{E}_{P_{xz}}f(\mathbf{x})g(\mathbf{z})=\mathbb{E}_{P_{z}\otimes
P_{x}}h_{0}(\mathbf{z},\mathbf{x})f(\mathbf{x})g(\mathbf{z})=\int\left(\int
h_{0}(x,z)f(x)P_{x}(dx)\right)g(z)dP_{z}.$

Thus, the right-hand side of (45) fulfills the definition of conditional
expectation. Now, let $\\{\phi_{j}\\},\\{\psi_{i}\\}$ be any orthonormal bases
for $L_{2}(P_{z})$, $L_{2}(P_{x})$, respectively. Then

$\displaystyle\|\tilde{E}-E\|_{HS}^{2}$
$\displaystyle=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}\langle\phi_{j},(\tilde{E}-E)\psi_{i}\rangle_{2}^{2}$
$\displaystyle\overset{(i)}{=}\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}\left(\int\phi_{j}(z)\left(\int(h-h_{0})(x,z)\psi_{i}(x)P_{x}(dx)\right)P_{z}(dz)\right)^{2}$
$\displaystyle=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}\langle
h-h_{0},\phi_{j}\otimes\psi_{i}\rangle_{L_{2}(P_{z}\otimes P_{x})}^{2}$
$\displaystyle=\|h-h_{0}\|_{2}^{2},$

where (i) follows by (45) and the definition of $\tilde{E}$. This completes
the proof for (17).

Before we prove (18), we first prove the following claim, which also appeared
in Section 3: for any
$h(z,x)=\Phi(z)^{\top}\Psi(x)=\sum_{i=1}^{J_{n}}\phi_{i}(z)\psi_{i}(x)$
satisfying (17), there exists a linear transform of $\Psi$,
$\tilde{\psi}_{i}:=\sum_{j=1}^{J_{n}}a_{ij}\psi_{j}$, s.t.

$\sum_{i=1}^{J_{n}}\|E\tilde{\psi}_{i}\|_{2}^{2}\geq\sum_{i=1}^{J_{n}}\|E\bar{\psi}_{i}\|_{2}^{2}-\epsilon_{n}^{2}.$
(46)

To establish this, let
$\mathcal{D}_{\mathrm{col}}(\Psi):=\sup_{\Phi^{\prime}:\mathcal{Z}\to\mathbb{R}^{k}}\mathcal{D}_{\chi^{2},\mathrm{lb}}({\Phi^{\prime\top}\Psi})$
be the collapsed population objective. Define the whitened feature maps
$S:=\mathbb{E}_{P_{x}}[\Psi(\mathbf{x})\Psi^{\top}(\mathbf{x})],\tilde{\Psi}(\cdot):=(S^{-1/2})^{\top}\Psi(\cdot)$.
Then we have $h=(S^{1/2}\Phi)^{\top}\tilde{\Psi}$, and

$\displaystyle\mathcal{D}_{\mathrm{col}}(\Psi)+1$
$\displaystyle=\sup_{\tilde{\Phi}:\mathcal{Z}\to\mathbb{R}^{k}}2\mathbb{E}_{P_{zx}}\tilde{\Phi}(\mathbf{z})^{\top}\tilde{\Psi}(\mathbf{x})-\mathbb{E}_{P_{z}\otimes
P_{x}}(\tilde{\Phi}(\mathbf{z})^{\top}\tilde{\Psi}(\mathbf{x}))^{2}$
$\displaystyle=\sup_{\tilde{\Phi}}2\mathbb{E}_{P_{zx}}\sum_{i=1}^{k}\tilde{\phi}_{i}(\mathbf{z})\tilde{\psi}_{i}(\mathbf{x})-\sum_{i=1}^{J_{n}}\sum_{i^{\prime}=1}^{J_{n}}\mathbb{E}_{P_{z}\otimes
P_{x}}\tilde{\phi}_{i}(\mathbf{z})\tilde{\psi}_{i}(\mathbf{x})\tilde{\phi}_{i^{\prime}}(\mathbf{z})\tilde{\psi}_{i^{\prime}}(\mathbf{x})$
$\displaystyle=\sup_{\tilde{\Phi}}2\mathbb{E}_{P_{z}}\sum_{i=1}^{k}\tilde{\phi}_{i}(\mathbf{z})(E\tilde{\psi}_{i})(\mathbf{z})-\sum_{i=1}^{J_{n}}\sum_{i^{\prime}=1}^{J_{n}}\mathbb{E}_{P_{z}}(\tilde{\phi}_{i}(\mathbf{z})\tilde{\phi}_{i^{\prime}}(\mathbf{z}))\underbrace{\mathbb{E}_{P_{x}}(\tilde{\psi}_{i}(\mathbf{x})\tilde{\psi}_{i^{\prime}}(\mathbf{x}))}_{=\delta_{ii^{\prime}}}$
$\displaystyle=\sum_{i=1}^{J_{n}}\sup_{\tilde{\phi}_{i}}\>\langle
2E\tilde{\psi}_{i}-\tilde{\phi}_{i},\tilde{\phi}_{i}\rangle_{L_{2}(P_{z})}=\sum_{i=1}^{J_{n}}\|E\tilde{\psi}_{i}\|_{L_{2}(P_{z})}^{2}.$
(47)

The proof of (46) completes by observing

$\mathcal{D}_{\chi^{2},\mathrm{lb}}({h})\leq\mathcal{D}_{\text{col}}(\Psi)\leq\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})=\sum_{i=1}^{\infty}s_{i}^{2}(E)-1.$
(48)

Finally, for (18), observe that setting
$\tilde{\psi}_{i}\leftarrow\bar{\psi}_{i},\tilde{\phi}_{i}\leftarrow\bar{\psi}_{i}$
attains the supremum in (47), at any fixed $J_{n}$. Setting $J_{n}\to\infty$
shows that $\mathcal{D}_{\chi^{2}}(P_{zx}\|P_{z}\otimes
P_{x})\geq\sum_{i=1}^{\infty}s_{i}^{2}(E)-1$. Combining with (48) completes
the proof. ∎

####  D.2 Proof for (19’)

######  Lemma D.1 (population kernel).

Let $k_{popu}$ be defined as in (19’). Then its integral operator equals
$(\tilde{E}^{\top}\tilde{E})^{\alpha}$, where $\tilde{E}$ is defined as in
Lemma 4.1.

###### Proof.

It suffices to show the integral operator defined by $k$ equals
$(\tilde{E}^{\top}\tilde{E})^{\alpha}$. First consider the $\alpha=1$ case. We
have, for all $f^{\prime}\in L_{2}(P_{x})$ and $P_{x}$-almost all $x$:

$\displaystyle(\tilde{E}^{\top}\tilde{E}f)(x)$
$\displaystyle=\left(\tilde{E}^{\top}\int
h(\cdot,x^{\prime})f(x^{\prime})dP_{x}(x^{\prime})\right)(x)$
$\displaystyle=\int h(x,z)\left(\int
h(z,x^{\prime})f(x^{\prime})dP_{x}(x^{\prime})\right)dP_{z}=\mathbb{E}_{x^{\prime},z\sim
P_{x}\otimes
P_{z}}\Psi(x)^{\top}\Phi(z)\Phi(z)^{\top}\Psi(x^{\prime})f(x^{\prime})$
$\displaystyle=\int(\Psi(x)^{\top}\Sigma_{z}\Psi(x^{\prime}))f(x^{\prime})P(dx)=\int
k(x,x^{\prime})f(x^{\prime})P(dx).$

When $\alpha\neq 1$, introduce the whitened feature maps
$\Psi^{\prime}(x)=\Sigma_{x}^{-1/2}\Psi(x),\Phi^{\prime}(z)=\Sigma_{x}^{1/2}\Phi(z)$
which defines the same $h(z,x)$. Recall our convention of using
$\Psi^{\prime}$ to also refer to the operator
$\Psi^{\prime}:L_{2}(P_{x})\to\mathbb{R}^{J}$ (Appendix A). Then the above
display implies

$\tilde{E}^{\top}\tilde{E}=\Psi^{\prime\top}\Sigma_{z}^{\prime}\Psi^{\prime}=\Psi^{\prime\top}\Sigma_{x}^{1/2}\Sigma_{z}\Sigma_{x}^{1/2}\Psi^{\prime},$

and we have, since $\Psi^{\prime}\Psi^{\prime\top}=I$,

$(\tilde{E}^{\top}\tilde{E})^{\alpha}=\Psi^{\prime\top}(\Sigma_{x}^{1/2}\Sigma_{z}\Sigma_{x}^{1/2})^{\alpha}\Psi^{\prime}.$

The claim is proved by plugging in the definition of $\Psi^{\prime}$ and
computing the integral operator. ∎

####  D.3 Proof for Proposition 4.1

We prove a slightly more general version of the proposition, as stated below.

######  Proposition D.1 (oracle inequality).

Let $B,C_{1}>0$ be constants,
$h^{*}:\mathcal{Z}\times\mathcal{X}\to\mathbb{R}$ be an arbitrary, square-
integrable function. Suppose $\\{\mathcal{F}_{h,n}\\}$ is a sequence of
hypothesis spaces indexed by $n$, which are all star-shaped around $h^{*}$,
and satisfy

$\sup_{h\in\mathcal{F}_{h,n}}\|h\|_{\infty}\leq
B,~{}~{}logN(\mathcal{F}_{h,n},\|\cdot\|_{\infty},\epsilon)\lesssim
C_{1}\epsilon^{-2}.$

Let $\hat{h}_{n},\mathcal{D}_{n}$ be defined as in the text, and
$\delta_{n,\mathcal{F}_{h,n}}\geq n^{-1/2}$ solve the inequality

$\frac{64}{\sqrt{n}}\int_{\delta^{2}}^{\delta}\sqrt{\log
N(\mathcal{F}_{h,n},\|\cdot\|_{\infty},t)}dt\leq\delta^{2}.$

Then for some $C_{2}>0$, we have, for any $\zeta\in(0,1/8)$,

$\displaystyle\mathbb{P}\left(\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})\>-\>\mathcal{D}_{\chi^{2},\mathrm{lb}}({\hat{h}_{n}})\leq
C_{2}\left(\mathcal{D}_{\chi^{2},\mathrm{lb}}({h_{0}})-\mathcal{D}_{\chi^{2},\mathrm{lb}}({h^{*}})+B^{4}\delta_{n,\mathcal{F}_{h,n}}^{2}+\frac{\log\zeta^{-1}}{n}\right)\right)\geq
1-\zeta.$

Proposition D.1 generalizes the claimed inequality in the main text. To see
this, let $q\in(0,1]$ be the smallest real number s.t. $\log
N(\mathcal{F}_{h,n},\|\cdot\|_{\infty},\epsilon)\lesssim\epsilon^{-2q}$ may
hold. Then we can choose $\delta_{n,\mathcal{F}_{h,n}}^{2}\asymp
n^{-1/(1+q)}$, recovering the claim in the text.

We now prove the proposition.

Denote by $P_{zx,n},P_{z,n},P_{x,n}$ the empirical measures determined by the
training samples, and $(P_{z}\otimes P_{x})_{n}$ the empirical measure defined
by $\\{(z_{i},x_{j}):i\neq j\\}$, so that we can write

$\mathcal{D}_{n}(h)=\mathbb{E}_{P_{zx,n}}2h-\mathbb{E}_{(P_{z}\otimes
P_{x})_{n}}h^{2}.$ (49)

We analyze the concentration of the two terms in turn.

For the first term above, by Wainwright, (2019, Theorem 14.20 (a)), there
exists some universal $c_{1}>0$ s.t. w.p. $1-\zeta/8$,

$|\mathbb{E}_{P_{zx,n}}(h-h^{*})-\mathbb{E}_{P_{zx}}(h-h^{*})|\leq
c_{1}B\delta_{n}(\|h-h^{*}\|_{L_{2}(P_{zx})}+\delta_{n}),~{}~{}\forall
h\in\mathcal{F}_{h,n},$

where

$\delta_{n}:=\delta_{n,\mathcal{F}_{h,n}}+\frac{\log(c_{1}\zeta^{-1})}{n},$

and $\delta_{n,\mathcal{F}_{h,n}}$ upper bounds the critical radius of the
local Rademacher complexity of $\mathcal{F}_{h,n}$.

Note that

$\displaystyle\|h-h^{*}\|_{L_{2}(P_{zx})}^{2}$
$\displaystyle=\mathbb{E}_{P_{z}\otimes
P_{x}}(h_{0}-h^{*}+h^{*})(h-h^{*})^{2}$
$\displaystyle\leq\|h_{0}-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}\|h-h^{*}\|_{\infty}+\|h^{*}\|_{\infty}\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}$ $\displaystyle\leq 2B(\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+\|h_{0}-h^{*}\|_{L_{2}(P_{z}\otimes P_{x})}^{2}),$

where the last line follows from the inequality
$ab\leq(\epsilon^{2}a^{2}+\epsilon^{-2}b^{2})/2$ (for all $\epsilon>0$).
Combining the above bounds with another application of the same elementary
inequality, we have, on the above high-probability event,

$|\mathbb{E}_{P_{zx,n}}(h-h^{*})-\mathbb{E}_{P_{zx}}(h-h^{*})|\leq\frac{\|h-h^{*}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}+\|h^{*}-h_{0}\|_{L_{2}(P_{z}\otimes
P_{x})}^{2}}{8}+C_{f}B^{3}\delta_{n}^{2},$ (50)

for some $C_{f}>0$.

Analysis of the second term in (49) follows Clémençon et al., (2006, 2008):
Introduce the notations

$w:=(z,x),~{}u_{h}(w,w^{\prime}):=\frac{1}{2}(h(z,x^{\prime})^{2}+h(x,z^{\prime})^{2})$

so that

$\mathbb{E}_{(P_{z}\otimes P_{x})_{n}}h^{2}=\frac{1}{n(n-1)}\sum_{i\neq
j}u_{h}(w_{i},w_{j}),~{}~{}\mathbb{E}_{P_{z}\otimes
P_{x}}h^{2}=\mathbb{E}_{P_{z}\otimes
P_{x}}h^{2}(\mathbf{z},\mathbf{x})=\mathbb{E}_{\mathbf{w},\mathbf{w}^{\prime}\sim
P_{w}}u_{h}(\mathbf{w},\mathbf{w}^{\prime}),$

where $P_{w}=P_{zx}$. (The last equality above holds because
$\mathbf{w},\mathbf{w}^{\prime}$ are i.i.d., and thus
$(\mathbf{z},\mathbf{x}^{\prime})\sim P_{z}\otimes P_{x}$.) Recall the
Hoeffding decomposition for $U$ statistic:

$\displaystyle\mathbb{E}_{(P_{z}\otimes
P_{x})_{n}}h^{2}-\mathbb{E}_{P_{z}\otimes P_{x}}h^{2}$
$\displaystyle=2T_{n}(h)+W_{n}(h),$ $\displaystyle T_{n}(h)$
$\displaystyle:=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mathbf{w}\sim
P_{w}}u_{h}(w_{i},\mathbf{w})-\mathbb{E}_{\mathbf{w},\mathbf{w}^{\prime}\sim
P_{w}}u_{h}(\mathbf{w},\mathbf{w}^{\prime}),$ $\displaystyle W_{n}(h)$
$\displaystyle:=\frac{1}{n(n-1)}\sum_{i\neq
j}u_{h}(w_{i},w_{j})-\mathbb{E}_{\mathbf{w},\mathbf{w}^{\prime}\sim
P_{w}}u_{h}(\mathbf{w},\mathbf{w}^{\prime})-2T_{n}(h).$

We first show that $W_{n}$ is insignificant. By Clémençon et al., (2008,
Theorem 11), w.p. $1-\zeta/8$, we have

$\sup_{h\in\mathcal{F}_{h,n}}|W_{n}(h)|\lesssim\frac{\mathbb{E}Z_{\epsilon}+\mathbb{E}U_{\epsilon}\sqrt{\log\zeta^{-1}}+\mathbb{E}M\log\zeta^{-1}+n\log\zeta^{-1}}{n^{2}},$
(51)

where

$\displaystyle Z_{\epsilon}$
$\displaystyle=\sup_{h\in\mathcal{F}_{h,n}}\Bigg{|}\sum_{i,j}\epsilon_{i}\epsilon_{j}u_{h}(w_{i},w_{j})\Bigg{|},~{}~{}U_{\epsilon}=\sup_{h\in\mathcal{F}_{h,n}}\sup_{\begin{subarray}{c}\alpha\in\mathbb{R}^{n},\\\
\|\alpha\|_{2}\leq
1\end{subarray}}\sum_{i,j}\epsilon_{i}\alpha_{j}u_{h}(w_{i},w_{j}),~{}~{}M=\sup_{h\in\mathcal{F}_{h,n}}\max_{1\leq
k\leq n}\sum_{i=1}^{n}\epsilon_{i}u_{h}(w_{i},w_{k}).$

and $\\{\epsilon_{i}\\}$ are i.i.d. Rademacher random variables independent of
$\\{w_{i}\\}$. We address the three terms in turn.

  1. (i)

Since $\|u_{h}\|_{\infty}\leq B^{2}$, we have $M\leq nB^{2}$.

  2. (ii)

For $Z_{\epsilon}$, define $X_{h}:=\frac{1}{n}\sum_{i\neq
j}\epsilon_{i}\epsilon_{j}u_{h}(w_{i},w_{j})$, so that $Z_{\epsilon}\leq
n\sup_{h\in\mathcal{F}_{h,n}}(B^{2}+X_{h}).$ by Arcones and Giné, (1993,
Proposition 2.2, 2.6), we have, for all $\delta^{\prime}>0$ and
$\mathcal{U}:=\\{u_{h}:h\in\mathcal{F}_{h,n}\\}$,

$\displaystyle\mathbb{E}_{\epsilon}\sup_{h\in\mathcal{F}_{h,n}}X_{h}$
$\displaystyle\leq\mathbb{E}_{\epsilon}\sup_{h,h^{\prime}\in\mathcal{F}_{h,n}}(X_{h}-X_{h^{\prime}})\leq\int_{\delta^{\prime}}^{D}\log
N(\mathcal{U},\rho,\delta)d\delta+\mathbb{E}_{\epsilon}\sup_{\begin{subarray}{c}h,h^{\prime}\in\mathcal{F}_{h,n},\\\
\rho(h,h^{\prime})\leq\delta^{\prime}\end{subarray}}(X_{h}-X_{h^{\prime}}),$

where
$\rho(h,h^{\prime}):=(\mathbb{E}_{\epsilon}(X_{h}-X_{h}^{\prime})^{2})^{\frac{1}{2}}\leq\|u_{h}-u_{h^{\prime}}\|_{\infty}\leq
2B\|h-h^{\prime}\|_{\infty}.$ Plugging back, we have

$\displaystyle\mathbb{E}_{\epsilon}\sup_{h\in\mathcal{F}_{h,n}}X_{h}$
$\displaystyle\leq\int_{\delta^{\prime}}^{D}\log
N(\mathcal{F}_{h,n},\|\cdot\|_{\infty},\delta/2B)d\delta+n\delta^{\prime}\lesssim
B^{2q}\int_{\delta^{\prime}}^{D}\delta^{-2q}d\delta+n\delta^{\prime},$

where $D=\sup_{h,h^{\prime}}\rho(u_{h},u_{h^{\prime}})\lesssim B^{2}$. Thus,
when $2q\leq 1$, we have
$\mathbb{E}_{\epsilon}\sup_{h\in\mathcal{F}_{h,n}}X_{h}\lesssim B^{2}+B\log
D$; when $q\in(1/2,1]$, we have
$\mathbb{E}_{\epsilon}\sup_{h\in\mathcal{F}_{h,n}}X_{h}\lesssim
Bn^{1-1/(2q)}\lesssim Bn\delta_{n,\mathcal{F}_{h,n}}^{2}.$ Combining, we have

$\frac{1}{n^{2}}\mathbb{E}_{\epsilon}Z_{\epsilon}\lesssim\frac{B^{2}}{n}+B\delta_{n,\mathcal{F}_{h,n}}^{2}.$

  3. (iii)

Finally, for $U_{\epsilon}$, we have

$\mathbb{E}_{\epsilon}U_{\epsilon}^{2}\leq\mathbb{E}_{\epsilon}\sup_{h\in\mathcal{F}_{h,n}}\sum_{j=1}^{n}\Bigg{(}\sum_{i=1}^{n}\epsilon_{i}u_{h}(w_{i},w_{j})\Bigg{)}^{2}=\mathbb{E}_{\epsilon}\sup_{h\in\mathcal{F}_{h,n}}\sum_{i,i^{\prime}}\epsilon_{i}\epsilon_{i^{\prime}}\underbrace{\sum_{j=1}^{n}u_{h}(w_{i},w_{j})u_{h}(w_{i^{\prime}},w_{j})}_{=:\bar{u}_{h}(w_{i},w_{i^{\prime}})}.$