# Deep Learning Methods for Proximal Inference via Maximum Moment Restriction

Benjamin Kompa
Department of Biomedical Informatics
Harvard Medical School
<EMAIL_ADDRESS>&David R. Bellamy*
Department of Epidemiology, CAUSALab
Harvard School of Public Health
<EMAIL_ADDRESS>
&Thomas Kolokotrones
Department of Epidemiology
Harvard School of Public Health
<EMAIL_ADDRESS>
&James M. Robins
Department of Epidemiology, CAUSALab
Harvard School of Public Health
<EMAIL_ADDRESS>
&Andrew L. Beam
Department of Epidemiology, CAUSALab
Harvard School of Public Health
<EMAIL_ADDRESS>
Denotes equal contribution

###### Abstract

The No Unmeasured Confounding Assumption is widely used to identify causal
effects in observational studies. Recent work on proximal inference has
provided alternative identification results that succeed even in the presence
of unobserved confounders, provided that one has measured a sufficiently rich
set of _proxy variables_ , satisfying specific structural conditions. However,
proximal inference requires solving an ill-posed integral equation. Previous
approaches have used a variety of machine learning techniques to estimate a
solution to this integral equation, commonly referred to as the _bridge
function_. However, prior work has often been limited by relying on pre-
specified kernel functions, which are not data adaptive and struggle to scale
to large datasets. In this work, we introduce a flexible and scalable method
based on a deep neural network to estimate causal effects in the presence of
unmeasured confounding using proximal inference. Our method achieves state of
the art performance on two well-established proximal inference benchmarks.
Finally, we provide theoretical consistency guarantees for our method.

##  1 Introduction

Causal inference is concerned with estimating the effect of a treatment $A$ on
an outcome $Y$ from either observational data or the results of a randomized
experiment. An estimand of primary importance is the _average causal effect_
(ACE), which is the expected difference in $Y$ caused by changing the
treatment from value $a$ to $a^{\prime}$ for each unit in the study
population, and is defined as a contrast between the expected value of the
potential outcomes at the two levels of the treatment:
$\mathbb{E}[Y^{a^{\prime}}]-\mathbb{E}[Y^{a}]$. However, in observational
settings, the ACE is rarely equal to the observed difference in conditional
means, $\mathbb{E}[Y|A=a^{\prime}]-\mathbb{E}[Y|A=a]$ due to confounding. In
an attempt to eliminate the influence of confounding, investigators measure
putative confounders $X$ and subsequently make adjustments for $X$ in their
analyses.

Given $X$, common approaches, such as standardization and inverse probability
weighting (Hernán and Robins [1]), obtain valid estimates of the ACE given
that the following assumptions hold: i) Positivity: $Pr[A=a|X=x]>0$ for all
$x$ in the population, ii) Consistency: $Y^{a}=Y$ for all individuals with
$A=a$, iii) No unmeasured confounding which results in conditional
exchangeability: $Y^{a}\perp\\!\\!\\!\perp A|X$., and iv) No model
misspecification.

The assumptions are typically unverifiable for continuous data. While model
misspecification is likely in all real-world scenarios, flexible models and
doubly robust estimators have been developed to mitigate the effect of this
assumption[2]. Therefore, the assumption of conditional exchangeability, or
equivalently, the No Unmeasured Confounding Assumption (NUCA), is the defining
characteristic of this broad set of approaches to causal effect estimation
(Hernán and Robins [3]). However, in many settings, it is unrealistic to
assume that we are able to measure a sufficient set of confounders for $A$ and
$Y$ such that conditional exchangeability holds.

_Proximal inference_ is a recently introduced framework that allows for the
identification of causal effects even in the presence of unmeasured
confounders [4, 5]. Proximal inference requires categorizing the measured
covariates into three groups: treatment-inducing proxy variables $Z$, outcome-
inducing proxy variables $W$, and “backdoor” variables $X$ that affect both
$A$ and $Y$ (i.e. typical confounders). See Figure 1 for an example of a
directed acyclic graph (DAG) that admits identification under the assumptions
of proximal inference. The proxy sets $W$ and $Z$ must contain sufficient
information about the remaining unobserved confounders $U$, a condition that
can be formalized by completeness assumptions. Under these and several other
conditions, one can estimate average potential outcomes from data even in the
presence of unmeasured confounding. Proximal inference has potential
applications in medical settings, where a natural question is the effect of a
treatment on an outcome in the presence of unmeasured confounding. Before
applying proximal inference to real world problems, more validation is
required before they can be used safely to inform medical decision-making.

Existing methods for proximal inference can be divided into two categories:
two-stage regression procedures and methods that impose a maximum moment
restriction (MMR). In two-stage regression procedures, the first stage aims to
predict outcome-inducing proxy variables $W$ as a function of $A$, $X$, and
$Z$. Then, the second stage regression estimates outcomes $Y$ as a function of
the predicted $\hat{W}$ and the treatment $A$, and measured confounders $X$.
Tchetgen Tchetgen et al. [5] introduced the first estimation technique for
proximal inference which was a two-stage procedure that used a model based on
ordinary least squares regression. Mastouri et al. [6] extended this framework
by replacing simple linear regression with kernel ridge regression. Xu et al.
[7] increased feature flexibility further by incorporating neural networks as
feature maps instead of kernels.

In contrast, MMR methods are single-stage procedures to estimate average
potential outcomes. Muandet et al. [8] introduced MMR for reproducing kernel
Hilbert spaces (RKHS). MMR critically relies on the optimization of a
V-statistic or U-statistic for learning a function needed to calculate the
ACE. Zhang et al. [9] used an MMR method to obtain point identification of the
ACE in the instrumental variable (IV) setting and incorporated neural networks
into their method trained with the V-statistic as a loss function and
optimized using stochastic gradient descent. Mastouri et al. [6] demonstrated
that the MMR framework with kernel functions can be used for proximal
inference as well as IV regression.

In this work, we introduce a new method, Neural Maximum Moment Restriction
(NMMR) which is a flexible neural network approach that is trained to minimize
a loss function derived from either a U-statistic or V-statistic to satisfy
MMR in the proximal setting. The method introduced in this work makes several
novel contributions to the proximal inference literature:

  * •

We introduce a new, single stage method based on neural networks for
estimating potential outcomes and the ACE in the presence of unmeasured
confounding.

  * •

We provide new theoretical consistency guarantees for our method.

  * •

We demonstrate state-of-the-art (SOTA) performance on two well-established
proximal inference benchmark tasks.

  * •

We show for the first time how to incorporate domain-specific inductive biases
using a convolutional model on a proximal inference task that uses images.

  * •

We provide the first unbiased estimate of the MMR risk function using the
U-statistic rather than V-statistic in the proximal setting.

Figure 1: A summary of NMMR. Our method estimates the bridge function $h$,
which can be used to compute the average potential outcome
$\mathbb{E}[Y^{a}]$. We rely on structural assumptions for the causal DAG
generating the data. NMMR uses a U or V statistic to train a neural network
that solves a risk function that reflects a maximum moment restriction
function.

##  2 Background: Proximal Inference

In this manuscript, capital, caligraphic, and lowercase letters (e.g. $A$,
$\mathcal{A}$, and $a$) denote random variables and their corresponding ranges
and realizations, respectively. Estimates of random variables and functions
will be indicated by hats, e.g. $\hat{Y}$ and $\hat{h}$ are estimates of $Y$
and $h$, respectively.

Our goal is to estimate, for each level of treatment, $a$, the expected
potential outcome $\mathbb{E}[Y^{a}]$. Without loss of generality, we refer to
$A$ as a treatment, though it could refer to any (possibly continuous)
intervention. Proximal inference allows us to do this, in the presence of
unobserved confounders, $U$, provided that we have a sufficiently rich set of
proxies, $(W,Z)$, that obey certain structural assumptions. We may also
include observed confounders, $X$. We also require the following:

######  Assumption 1.

Given $(A,U,W,X,Y,Z)$, $Y\perp\\!\\!\\!\perp Z|A,U,X$ and
$W\perp\\!\\!\\!\perp(A,Z)|U,X$.

Figure 1 provides an example of a DAG that satisfies these assumptions. The
following completeness conditions formalize the notion that the proxies are
“sufficiently rich”:

######  Assumption 2.

For all $f\in L^{2}$ and all $a\in\mathcal{A},x\in\mathcal{X}$,
$\mathbb{E}[f(U)|A=a,X=x,Z=z]=0$ for all $z\in\mathcal{Z}$ if and only if
$f(U)=0$ almost surely.

######  Assumption 3.

For all $f\in L^{2}$ and all $a\in\mathcal{A},x\in\mathcal{X}$,
$\mathbb{E}[f(Z)|A=a,W=w,X=x]=0$ for all $w\in\mathcal{W}$ if and only if
$f(Z)=0$ almost surely.

We will use two other assumptions at various points in the paper. The first
guarantees the uniqueness of the bridge function, while the second ensures the
risk function does not have false zeros.

######  Assumption 4.

$\mathbb{E}\left[f\left(A,W,X\right)\middle|A,X,Z\right]=0$
$\mathrm{P}_{A,X,Z}$-almost surely if and only if $f\left(A,W,X\right)=0$
$\mathrm{P}_{A,W,X}$-almost surely.

######  Assumption 5.

$k:\left(\mathcal{A}\times\mathcal{X}\times\mathcal{Z}\right)^{2}\to\mathbb{R}$
is continuous, bounded, and Integrally Strictly Positive Definite (ISPD), so
that $\int
f\left(\xi\right)k\left(\xi,\xi^{\prime}\right)f\left(\xi^{\prime}\right)d\xi
d\xi^{\prime}>0$ if and only if $f\neq 0$ $\mathrm{P}_{A,Z,X}$-almost surely.

Assumptions 1-3 together with several regularity assumptions (see assumptions
(v)-(vii) in [4]) ensure that there exists a function $h$ such that:

$\mathbb{E}[Y|A=a,X=x,Z=z]=\int_{\mathcal{W}}h(a,w,x)p(w|a,x,z)dw$ (1)

Equation 1 is a Fredholm integral equation of the first kind; its solution,
$h$, is often called the “bridge function.” Theorem 1 of Miao et al. [4] shows
that the expected potential outcomes are given by:

$\mathbb{E}[Y^{a}]=\int_{\mathcal{W},\mathcal{X}}h(a,w,x)p(w,x)dwdx=\mathbb{E}_{W,X}[h(a,W,X)]$
(2)

We can obtain unbiased estimates of the expected potential outcomes,
$\mathbb{E}[Y^{a}]$, by splitting the sample, using the first part of the data
to estimate the bridge function $h$, by some $\hat{h}$, and using the second
part of the data to compute the empirical mean of $\hat{h}$ with $a$ fixed to
the value of interest,
$\hat{\mathbb{E}}[Y^{a}]=\frac{1}{M}\sum_{i=1}^{M}\hat{h}(a,w_{i},x_{i})$.
From these, we can obtain other quantities of interest, like the ACE.

In what follows, all norms will be $L^{2}$ with respect to the relevant
probability measure, unless otherwise noted. If necessary, we will explicitly
denote the norm of $f$ with respect to a probability measure
$\mathcal{P}_{U,V,\dots}$ by $\|f\|_{\mathcal{P}_{U,V,\dots}}$ or
$\|f\|_{2,\mathcal{P}_{U,V,\dots}}$.

##  3 Related Work

Kuroki and Pearl [10] first established identification of a causal effect in
the setting of unobserved confounders by leveraging noisy proxy variables,
$W$, to “recover” the distribution of $U$, potentially using external datasets
to estimate $p(w|u)$. Tchetgen-Tchetgen and colleagues extended these results
to allow for identification without recovery of $U$ in Miao et al. [4] and
Tchetgen Tchetgen et al. [5], also providing a 2-Stage Least Squares (2SLS)
method to identify and estimate causal effects under the assumption that the
bridge function is linear. Cui et al. [11] introduced a bridge function for
Inverse Probability Weighting (IPW), which enabled IPW and Doubly Robust (DR)
proximal estimators, for which they presented influence functions under binary
treatment. This was extended in Ghassami et al. [12] and further explored by
Kallus et al. [13], who provided alternative identification assumptions as
well as results for general treatments. The latter two works also consider the
use of adversarial methods for estimation, which were previously utilized by
Lewis and Syrgkanis [14] and Bennett et al. [15] in the Instrumental Variable
(IV) setting and Dikkala et al. [16] in conditional moment models.

Other early investigators include Deaner [17], who developed machine learning
techniques for proximal inference introducing a method based on a two-stage
penalized sieve distance minimization. Several later works similarly employed
two-stage regressions with increasingly flexible basis functions to estimate
potential outcomes. Mastouri et al. [6] developed a two-stage kernel ridge
regression (Kernel Proxy Variables “KPV”) to estimate the bridge function $h$,
allowing more flexibility than the linear basis of Tchetgen Tchetgen et al.
[5]. Xu et al. [7] further improved upon this with an adaptive basis derived
from neural networks. Their two stage regression method, Deep Feature Proxy
Variables (DFPV), established the previous SOTA performance on the proximal
benchmark tasks that we consider in our work. Singh and colleagues also
considered two stage kernel models in the IV setting [18] and RKHS techniques
for proximal inference [19].

An alternative approach based on maximum moment restriction (MMR) uses single-
stage estimators of the bridge function. MMR-based methods were established in
Muandet et al. [8] as a way to enforce conditional moment restrictions [20].
Zhang et al. [9] introduced the MMR framework to the IV setting, which can be
considered a subset of proximal inference without outcome-inducing proxies $W$
and with additional exclusion restrictions [5]. There are now several machine
learning methods that can be applied in the IV setting [21, 14, 18, 16, 22]

Of note, Zhang et al. [9] introduced MMR-IV, which is related to work by Lewis
and Syrgkanis [14] and Dikkala et al. [16]. MMR-IV involves optimizing a
family of risk functions based on U or V-statistics [23]. However, Zhang et
al. [9] only considered IV, rather than proximal, inference and only optimized
neural networks by a loss that corresponds to the V-statistic. The V-statistic
provides a biased estimate [23] of its corresponding risk function, such as
$R(h)$ in Equation 3.

Finally, Mastouri et al. [6] introduced an MMR-based method for proximal
inference called Proximal Maximum Moment Restriction (PMMR). PMMR extends the
MMR framework to the proximal setting through the use of kernel functions and
also optimizes Equation 3 via a V-statistic. For a comparison of our model to
PMMR and MMR-IV, see Table 1.

##  4 Our Method: Neural Maximum Moment Restriction (NMMR)

In this work we propose _Neural Maximum Moment Restriction_ (NMMR): a method
to estimate expected potential outcomes $\mathbb{E}[Y^{a}]$ in the presence of
unmeasured confounding. We use deep neural networks due to their flexibility,
scalability, and adaptability to diverse data types (e.g. using convolutions
for images). By rewriting maximum moment restrictions [8] as U and
V-statistics [6, 9], we show how a single-stage neural network procedure can
be used to estimate the bridge function.

Following Muandet et al. [8] and Zhang et al. [9], we rewrite the integral
equation (1) as a _conditional moment restriction_ :
$\mathbb{E}[Y-h(A,W,X)|A,X,Z]=0$. Then, for any measurable
$g:\mathcal{A}\times\mathcal{X}\times\mathcal{Z}\to\mathbb{R}$,
$\mathbb{E}[(Y-h(A,W,X))g(A,X,Z)|A,X,Z]=0$ , and, thus,
$\mathbb{E}[(Y-h(A,W,X))g(A,X,Z)]=0$, so we can use unconditional expectations
instead of conditional ones. This is the basis of the MMR framework of Muandet
et al. [8]. Since this yields an infinite number of moment restrictions we
employ a minimax strategy to estimate $h$ by minimizing the risk $R(h)$ for
the worst-case value of $g$:

$\displaystyle R(h)$ $\displaystyle=\sup_{\|g\|\leq
1}(\mathbb{E}[(Y-h(A,W,X))g(A,X,Z)])^{2}$ (3)

Following Zhang et al. [9]’s work in the IV setting, Mastouri et al. [6]
(Lemma 2) showed that, if $g$ is an element of an RKHS, $R(h)$ can be
rewritten in the form

$\displaystyle R_{k}(h)$
$\displaystyle=\mathbb{E}[(Y-h(A,W,X))(Y^{\prime}-h(A^{\prime},W^{\prime},X^{\prime}))k((A,X,Z),(A^{\prime},X^{\prime},Z^{\prime}))]$

where $(A^{\prime},W^{\prime},X^{\prime},Y^{\prime},Z^{\prime})$ are
independent copies of the random variables $(A,W,X,Y,Z)$ and
$k:(\mathcal{A}\times\mathcal{Z}\times\mathcal{X})^{2}\to\mathbb{R}$ is a
continuous, bounded, and Integrally Strictly Positive Definite (ISPD) kernel.
Then, if $h$ satisfies $R_{k}(h)=0$, $\mathbb{E}[Y-h(A,W,X)|A,X,Z]=0$
$\mathrm{P}_{A,X,Z}$-almost surely. Thus, if we can find a neural network $h$
that satisfies $R_{k}(h)=0$, we will have obtained a
$\mathrm{P}_{A,X,Z}$-almost sure solution to Equation 1 and can compute any
expected potential outcome by using Equation 2.

The empirical risk $\hat{R}_{k,n}$ given data
$\mathcal{D}=\\{(a_{i},w_{i},x_{i},y_{i},z_{i})\\}_{i=1}^{N}$ can be written
as either a U or V-statistic, respectively [23]:

$\displaystyle\hat{R}_{k,U,n}(h)$
$\displaystyle=\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}{\left(y_{i}-h_{i}\right)\left(y_{j}-h_{j}\right)k_{ij}}$
$\displaystyle\hat{R}_{k,V,n}(h)$
$\displaystyle=\frac{1}{n^{2}}\sum_{i,j=1}^{n}{\left(y_{i}-h_{i}\right)\left(y_{j}-h_{j}\right)k_{ij}}$

where $h_{i}=h\left(a_{i},w_{i},x_{i}\right)$ and
$k_{ij}=k\left(\left(a_{i},z_{i},x_{i}\right),\left(a_{j},z_{j},x_{j}\right)\right)$.
$\hat{R}_{k,U,n}(h)$ is the minimum variance unbiased estimator of $R_{k}(h)$
[23], while $\hat{R}_{k,V,n}(h)$ is a biased estimator of $R_{k}(h)$. In order
to prevent overfitting, we add an additional penalty to our risk function
$\Lambda:\mathcal{H}\times\Theta_{\mathcal{H}}\to\mathbb{R}_{+}$, which is a
function of $h$ as well as, possibly, its parameters, $\theta_{h}$ (e.g.
network weights). Specifically, we take $\Lambda$ to be an $L^{2}$ penalty on
the weights so $\Lambda\left[h,\theta_{h}\right]=\sum_{i}\theta_{h,i}^{2}$. We
then denote the penalized risk functions by
$\hat{R}_{k,U,\lambda,n}(h)=\hat{R}_{k,U,n}(h)+\lambda\Lambda\left[h,\theta_{h}\right]$
and
$\hat{R}_{k,V,\lambda,n}(h)=\hat{R}_{k,V,n}(h)+\lambda\Lambda\left[h,\theta_{h}\right]$,
respectively. In practice, $\hat{R}_{k,U,\lambda,n}(h)$ is slightly biased,
but, in simulations, is much less biased than even the unpenalized
$\hat{R}_{k,V,n}(h)$. Previous work either did not consider the U-statistic
[6], or did not utilize the U-statistic [9]. In our work, we introduce two
variants of our method, NMMR-U and NMMR-V, where the former is optimized with
a U-statistic and the latter a V-statistic. We train the neural networks in
both variants with the regularized loss function:

$\displaystyle\mathcal{L}$
$\displaystyle=(Y-h(A,W,X))^{t}K(Y-h(A,W,X))+\lambda\Lambda\left[h,\theta_{h}\right]$

where $(Y-h(A,W,X))$ is a vector of residuals from the neural network’s
predictions and $K$ is a kernel matrix with entries $k_{ij}$. We choose $k$ to
be an RBF kernel (see Appendix B). If $\mathcal{L}$ represents a V-statistic,
we include the main diagonal elements of $K$, while if $\mathcal{L}$
represents a U-statistic, we set the main diagonal to be 0. Once we’ve
obtained an optimal neural network $\hat{h}$, we can compute an estimate of
the expected potential outcome with data from a held-out dataset with $M$ data
points

$\displaystyle
D_{\mathcal{W},\mathcal{X}}=\\{(w_{i},x_{i})\\}_{i=1}^{M},\quad\hat{\mathbb{E}[Y^{a}]}=\frac{1}{M}\sum_{i=1}^{M}\hat{h}(a,w_{i},x_{i})$

In contrast to PMMR [6], which uses kernels as feature maps for proxy and
treatment variables, NMMR uses adaptive feature maps from neural networks.
NMMR is similar to MMR-IV [9], but MMR-IV is restricted to the instrumental
variable (IV) setting rather than the proximal inference setting. Table 1
places NMMR in context with existing methods for proximal inference and IV
regression.

Table 1: Comparison of the most related methods to NMMR.

Method | Setting | # of Stages | Hypothesis Class | Optimization Objective
---|---|---|---|---
KPV [6] | Proximal | 2 | Kernels | 2-stage least squares
DFPV [7] | Proximal | 2 | Neural Networks | 2-stage least squares
MMR-IV [9] | IV | 1 | Neural Networks | V-statistic
PMMR [6] | Proximal | 1 | Kernels | V-statistic
NMMR-V (ours) | Proximal | 1 | Neural Networks | V-statistic
NMMR-U (ours) | Proximal | 1 | Neural Networks | U-statistic

##  5 Consistency of NMMR

In this section we provide a probabilistic bound on the distance of the
estimated bridge function, $\hat{h}_{k,\lambda,n}$, from the true bridge
function, $h^{*}$, in terms of the Radamacher complexity
$\mathcal{R}_{n}(\mathcal{F})$ of a class of functions $\mathcal{F}$ derived
from elements of the hypothesis space $\mathcal{H}$ and the fixed kernel, $k$.
Note that
$\hat{R}_{k,\lambda,n}(h)=\hat{R}_{k,n}(h)+\lambda\Lambda\left[h,\theta_{h}\right]$
(see Section 4). We use this bound to demonstrate that, under mild conditions,
$\hat{h}_{k,\lambda,n}$ converges in probability to $h^{*}$, and that, under
an additional completeness assumption, $h^{*}$ is unique
$\mathrm{P}_{A,W,X}$-almost surely. This provides a consistent estimate of
$\mathbb{E}[Y^{a}]$.

######  Theorem 1.

Let $\tilde{h}_{k}$ minimize $R_{k}(h)$ and $\hat{h}_{k,U,\lambda,n}$ minimize
$\hat{R}_{k,U,\lambda,n}(h)$ for $h\in\mathcal{H}$,
$k:(\mathcal{A}\times\mathcal{X}\times\mathcal{Z})^{2}\to[-M_{k},M_{k}]$,
$\Lambda:\mathcal{H}\times\Theta_{h}\to[0,M_{\lambda}]$, and let
$h^{*}:\mathcal{A}\times\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ satisfy
$\mathbb{E}\left[Y-h^{*}(A,W,X)\middle|A,X,Z\right]=0$
$\mathrm{P}_{A,X,Z}$-almost surely, where

$\displaystyle R_{k}(h)$
$\displaystyle=\mathbb{E}\left[\left(Y-h\left(A,W,X\right)\right)\left(Y^{\prime}-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$
$\displaystyle\hat{R}_{k,U,\lambda,n}(h)$
$\displaystyle=\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}\left[\left(y_{i}-h\left(a_{i},w_{i},x_{i}\right)\right)\left(y_{j}-h\left(a_{j},w_{j},x_{j}\right)\right)\right.$
$\displaystyle\hskip
120.00018pt\times\left.k\left(\left(a_{i},x_{i},z_{i}\right),\left(a_{j},x_{j},z_{j}\right)\right)\right]+\lambda\Lambda[h,\theta_{h}]$

Also let,

$\displaystyle d_{k}^{2}\left(h,h^{\prime}\right)$
$\displaystyle=\mathbb{E}\left[\left(h\left(A,W,X\right)-h^{\prime}\left(A,W,X\right)\right)\left(h\left(A^{\prime},W^{\prime},X^{\prime}\right)-h^{\prime}\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)\right.$
$\displaystyle\hskip
60.00009pt\times\left.k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$

Then, $d_{k}^{2}\left(h^{*},h\right)=R_{k}(h)$ and, with probability at least
$1-\delta$,

$\displaystyle d_{k}^{2}\left(h^{*},\hat{h}_{k,U,\lambda,n}\right)$
$\displaystyle\leq d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$ $\displaystyle\leq
d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

Further, if Assumption 5 holds, so $k$ is ISPD, then $d_{k}$ is a metric on
$L^{2}_{\mathcal{AXZ}}$ and, if the right hand side of the inequality goes to
zero as $n$ goes to infinity,
$d_{k}\left(\mathbb{E}\left[h^{*}\middle|A,X,Z\right]-\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\right)\xrightarrow{\mathrm{P}}0$
so
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$
in $d_{k}$. Also,
$\left\|\mathbb{E}\left[h^{*}\middle|A,X,Z\right]-\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\right\|_{\mathrm{P}_{A,X,Z}}\xrightarrow{\mathrm{P}}0$
so
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$
in $L^{2}\left(\mathrm{P}_{\mathcal{A,X,Z}}\right)-norm$.

$\displaystyle\mathcal{F}^{\prime}_{a,x,z}=\left\\{f_{a,x,z}\ \middle|\
\exists_{h\in\mathcal{H}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f_{a,x,z}\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$
$\displaystyle\mathcal{F}^{\prime}=\left\\{f\ \middle|\
\exists_{h\in\mathcal{H},a\in\mathcal{A},x\in\mathcal{X},z\in\mathcal{Z}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$

Corollary 8 provides a similar result for V-statistic estimators of $R(h)$,
meaning we can choose to use either U or V-Statistics and have similar
guarantees. In Theorem 1 if the quadratic form converges at a particular rate,
say $n^{-\frac{1}{2}}$,
$\mathbb{E}\left[\hat{h}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$,
under the metric induced by the kernel, $d_{k}$, at half the rate, in this
case $n^{-\frac{1}{4}}$. This is similar to Kallus et al. [13]’s findings in
the unstabilized case.

######  Theorem 2.

Under Assumption 4, $h^{*}$ is the unique solution to the integral equation
$\mathrm{P}_{A,W,X}$-almost surely. Further, if
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$,
$\hat{h}_{n}\xrightarrow{\mathrm{P}}h^{*}$.

See Appendix A for proofs of Theorems 1 and 2. Taken together, these results
tell us that, as long as our optimization algorithm is successful in
estimating $\hat{h}_{k,\lambda,n}$, it will asymptotically approach the true
bridge function, $h^{*}$. In order for this to occur, the right hand side of
the inequalities in Theorem 1 must go to zero, which requires not only that
the Rademacher terms vanish, but also that $\tilde{h}_{k}$ must approach
$h^{*}$ arbitrarily closely as $n$ increases. In practice, this means
increasing the complexity of the neural network, but doing so slowly enough
the Rademacher complexity terms still decrease with sample size. Following Xu
et al. [7], we note that recent results from Neyshabur et al. [24] suggest
that the Rademacher complexity of a fixed network scales like
$n^{-\frac{1}{2}}$ (similar to many other popular hypothesis classes) and
that, although we cannot compute the scaling of the Rademacher terms directly
due to the presence of the kernel function, we expect that they will decline
with sample size and that, as the neural network becomes more complex, their
scaling will more closely resemble terms derived from a pure neural network.
Finally, we require that the regularization parameter decrease as sample size
grows, which will, again, depend on the balance between increasing sample
size, which tends to decrease the need for regularization, and increasing
complexity, which tends to increase its importance. Thus, by choosing an
appropriate growth rate for the network complexity, we expect the
aforementioned terms to vanish as $n$ increases to infinity, and, with them,
the entire right hand side, making $\hat{h}_{k,\lambda,n}$ a consistent
(likely $\sqrt{n}$) estimator of $h^{*}$.

We can also compare the convergence of the estimated bridge function to that
of its projection onto $L^{2}_{\mathcal{AXZ}}$. Prior literature has focused
on a measure of “ill-posedness”
$\tau=\sup_{h\in\mathcal{H}}\|h-h^{*}\|_{2}\left\|\mathrm{E}\left[h-h^{*}\middle|A,Z,X\right]\right\|_{2}^{-1}$.
If $\tau$ is finite, then the rate of convergence of the estimated bridge
function will be at worst $\tau$ times that of its projection (it will be
slower by a factor of $\tau$). This will be the case whether we measure
convergence using
$\left\|\mathrm{E}\left[h-h^{*}\middle|A,Z,X\right]\right\|_{2}$ or the metric
induced by $k$.

##  6 Experiments

###  6.1 Overview of Baseline Models

We compare the performance of NMMR-U and NMMR-V to that of several previous
approaches, which we describe briefly here. The baselines can be divided into
two categories: structural and naive. Structural approaches leverage causal
information about the data generating process. They include Kernel Proxy
Variables (KPV) [6], Proximal Maximum Moment Restriction (PMMR) [6], Deep
Feature Proxy Variables (DFPV) [25], Causal Effect Variational Autoencoder[26]
(CEVAE), and the two-stage least squares model (2SLS) from Miao et al. [4].
For a review of KPV, PMMR, and DFPV, see Section 3. CEVAE is an autoencoder
approach derived by Xu et al. [7] from Louizos et al. [26]. 2SLS is a two-
stage least squares method which assumes that the bridge function $h$ is
linear [5].

The naive approaches serve as baselines and do not use causal information,
instead directly regressing $A$ and $W$ on the outcome $Y$. These methods
include a naive neural network (Naive net), ordinary least squares regression
(LS), and ordinary least squares with quadratic features (LS-QF). Naive Net is
a neural network that has undergone the same architecture search as NMMR
(described further in Appendix B) that is trained to predict $Y$ directly from
$A$ and $W$ by minimizing observational MSE,
$\frac{1}{n}\sum_{i=1}^{n}(y-\hat{y})^{2}$. Least Squares (LS) is the standard
linear regression model that predicts $Y$ using a linear combination of $A$
and $W$. Least Squares with Quadratic Features (LS-QF) is the same as LS but
with additional quadratic terms $A^{2},W^{2},AW$.

We evaluate NMMR-U, NMMR-V and baseline methods on two synthetic benchmark
tasks from Xu et al. [7]. The first is a simulation of how ticket prices
affect the number of tickets sold in the presence of a latent confounder:
demand for travel (the Demand experiment). The second is an experiment where
the goal is to recover a property of an image that is influenced by an
unobserved confounder (the dSprite experiment). The Demand experiment is a
low-dimensional estimation problem, whereas dSprite is high-dimensional as $A$
and $W$ are 64x64=4096-dimensional. dSprite leverages image-specific models,
which are rarely used in the causal inference literature. Neither task uses
$X$. For the Demand experiment we evaluate all the methods mentioned above,
whereas for the dSprite experiment, we omit 2SLS, LS, and LS-QF because of
their lack of scalability to high-dimensional settings.

Experiments were conducted in PyTorch 1.9.0 (Python 3.9.7), using an A100 40GB
or TitanX 12GB GPU and CUDA version 11.2. They can be run in minutes for
simpler models (LS, LS-QF, 2SLS) and in several hours for the larger
experiments and more complex models (DFPV, NMMR). The code to reproduce our
experiments can be accessed on GitHub.111https://github.com/beamlab-
hsph/Neural-Moment-Matching-Regression

###  6.2 Demand Experiment

Figure 2: NMMR-U and NMMR-V achieve state of the art performance across all
sample sizes. Causal MSE (c-MSE) of NMMR and baseline methods in the Demand
experiment. Each method was replicated 20 times and evaluated on the same 10
test values of $\mathbb{E}[Y^{a}]$ each replicate. Each individual box plot
represents 20 values of c-MSE. See Table S4 for the statistics of each
boxplots

Hartford et al. [21] introduced a data generating process for studying
instrumental variable regression, and Xu et al. [7] adapted it to the proximal
setting. The goal is to estimate the effect of airline ticket price $A$ on
sales $Y$, which is confounded by demand $U$ (e.g. seasonal fluctuations). We
use the cost of fuel, $Z=(Z_{1},Z_{2})$, as a treatment-inducing proxy and
number of views at a ticket reservation website, $W$, as an outcome-inducing
proxy (Figure S1). Additional simulation details and the structural equations
underlying the causal DAG can be found in Appendix C.1.

Each method was trained on simulated datasets with sample sizes of 1000, 5000,
10,000, and 50,000. To assess the performance of each method, we evaluated $a$
at 10 equally-spaced intervals between 10 and 30. We compared each method’s
estimated potential outcomes, $\hat{E}[Y^{a}]$, against estimates of the
truth, $E[Y^{a}]$, obtained from Monte Carlo simulations (10,000 replicates)
of the data generating process for each $a$. The evaluation metric is the
causal mean squared error (c-MSE) across the 10 evaluation points of $a$:
$\frac{1}{10}\sum_{i=1}^{10}(\mathbb{E}[Y^{a_{i}}]-\hat{\mathbb{E}}[Y^{a_{i}}])^{2}$.
For MMR-based methods, predictions are computed using a heldout dataset,
$\mathcal{D}_{\mathcal{W}}$ with 1,000 draws from $W$ so
$\hat{\mathbb{E}}[Y^{a_{i}}]=|D_{\mathcal{W}}|^{-1}\sum_{j}^{|D_{\mathcal{W}}|}\hat{h}(a_{i},w_{j})$,
i.e. a sample average of the estimated bridge function over $W$. We performed
20 replicates for each method on each sample size, where a single replicate
yields one c-MSE value. Figure 2 summarizes the c-MSE distribution for each
method across the four sample sizes. NMMR-U has the lowest c-MSE across all
sample sizes, with NMMR-V a close second. DFPV encounters difficulties with
the larger sample sizes of 10,000 and 50,000, potentially due to convergence
issues with its feature maps. Similarly, PMMR and KPV could not scale to
$n=50,000$.

For a more in-depth view of the potential outcome curve estimated by each
method, we provide replicate-wise potential outcome prediction curves for each
of the 4 sample sizes in Figures S3-S6. Least Squares estimates relatively
unbiased prediction curves due to the nature of the data generating process
and has very low variance. LS-QF matches some of the curvature, although its
c-MSE distribution (not shown) is not better than LS. Kernel-based methods,
KPV and PMMR, are highly biased. DFPV is less biased, but still suffers from a
lack of flexibility. Both NMMR variants demonstrate the benefit of added
flexibility and have lower variance, resulting in a lower c-MSE.

Finally, we also varied the variance of the Gaussian noise terms in the
structural equations for $Z$ and $W$, in order to examine how each method
performs with varying quality proxies for $U$ (see Appendix E). Figure S10,
shows that NMMR-V is more robust to proxy noise than NMMR-U. This could be
because U-statistics yield unbiased, but higher variance, estimators than
V-statistics, so, when proxies are less reliable, the estimated risk function
$R_{k}(h)$ is less stable. Kernel-based methods (KPV and PMMR) perform
increasingly well with noisier proxies, which is likely related to the fact
that they are less data-adaptive. Figures S11 through S18 show replication-
wise prediction curves across all 72 noise levels, with one grid plot per
method.

###  6.3 dSprite Experiment

Figure 3: Causal MSE (c-MSE) of NMMR and baseline methods in the dSprite
experiment. Each method was replicated 20 times and evaluated on the same 588
test images $A$ each replicate. Each individual box plot represents 20 values
of c-MSE. See Table S5 for the statistics of each boxplots

The second benchmark uses the dSprite dataset from Matthey et al. [27], which
was initially adapted to instrumental variable regression in Xu et al. [25],
and repurposed for proximal inference in Xu et al. [7]. This image dataset
consists of 2D shapes procedurally generated from 6 independent parameters:
color, shape, scale, rotation, posX, and posY. All possible combinations of
these parameters are present exactly once, generating 737,280 total images. In
this experiment, we fix shape = heart, color = white, resulting in 245,760
images, each of which contains 64x64=4096 pixels. The causal DAG for this
problem is shown in Figure S7. The structural equations and detailed data
generating mechanism underlying the causal DAG can be found in Appendix C.6.

In the DAG, $Fig(\cdot)$ represents the act of retrieving the image from the
dSprite dataset with the given arguments. $A$ and $W$ are vectors representing
noised images of a heart shape, where the heart has a size (_scale_),
orientation (_rotation_), horizontal position (_posX_), and vertical position
(_posY_). For an exemplar image $A$ and $W$, see Figure S8. The benchmark
computes

$\displaystyle\mathbb{E}[Y^{a}]$
$\displaystyle=\frac{\frac{1}{10}\left\|vec(a)^{t}B\right\|_{2}^{2}-5000}{1000}$

where $B$ is a $4096\times 10$ matrix of $\mathcal{U}(0,1)$ weights from Xu et
al. [7]. The observed outcome is computed as

$\displaystyle Y$
$\displaystyle=\frac{\frac{1}{10}\left\|vec(A)^{t}B\right\|_{2}^{2}-5000}{1000}\times\frac{(31\times
U-15.5)^{2}}{85.25}+\epsilon,\quad\epsilon\sim\mathcal{N}(0,0.5)$

$U$ is a discrete uniform random variable with

$\displaystyle\mathbb{E}\left[\frac{(31\times U-15.5)^{2}}{85.25}\right]=1$

that dictates the vertical position of the shape in $A$, as well as the value
of $Y$, making $U$ a confounder of $A,Y$. We hypothesized that a convolutional
neural network would be exceptionally strong at recovering this information
about $U$ from the images $A$ and $W$.

Similar to the Demand experiment, we trained each method on simulated datasets
with sizes 1,000, 5,000, and 7,500, followed by an evaluation on the same test
set as Xu et al. [7]. This test set contains 588 images $A$ that span the
range of scale, rotation, posX and posY values (see Appendix C.9) and the 588
corresponding values of $\mathbb{E}[Y^{a}]$. The evaluation metric is again
c-MSE:

$\displaystyle\frac{1}{588}\sum_{i=1}^{588}\left(\mathbb{E}[Y^{a_{i}}]-\hat{\mathbb{E}}[Y^{a_{i}}]\right)^{2}$

We performed 20 replicates for each method on each sample size. Figure 3 shows
that NMMR-U or NMMR-V is consistently lowest in c-MSE, with NMMR-V showing
substantial improvement with increasing sample size. Due to the high
dimensionality of the images $A$ and $W$, we could not evaluate Least Squares,
LS-QF or 2SLS on this experiment. KPV and PMMR do not improve much with
increasing sample size. The Naive net, which uses the same underlying
convolutional neural network architecture as NMMR but is trained using
observational MSE, performs second-to-worst, with a much larger c-MSE than
NMMR-U or NMMR-V. This reinforces the need to use causal knowledge in
scenarios where it is available.

##  7 Conclusion

In this work we have presented a novel method to estimate potential outcomes
in the presence of unmeasured confounding using deep neural networks. Though
our method is promising, it has several limitations. For very high dimensional
data, calculating the kernel matrix $K$ in the loss function can be
computationally intensive (see Appendix D). Additionally, mapping real world
scenarios to DAGs that satisfy Assumption 1 is non-trivial and technically
unverifiable (e.g. we cannot be truly sure that $W$ has no impact on $A$),
though unverifiable assumptions are inherent to causal inference.

Further, the present work focuses on methods that estimate only the outcome
bridge function, rather than also estimating the IPW bridge function, which
would permit us to construct a doubly robust estimator, as is done in Cui et
al. [11] and Kallus et al. [13]. However, our method extends naturally to this
setting and we expect to explore such estimators in future work.

In summary, we provide a new single stage estimator and show how it can be
trained on a U-statistic based loss in addition to existing approaches based
on V-statistics. We further prove theoretical convergence properties of our
method. On established proximal inference benchmarks, our method achieves
state of the art performance in estimating causal quantities. Finally, since
our approach is a single-stage neural network, it potentially unlocks new
domains for causal inference where deep learning has had success, such as
imaging.

## References

  * Hernán and Robins [2021] Miguel A. Hernán and James M. Robins.  _Casual inference: What if_.  CRC Press, 2021.
  * Funk et al. [2011] Michele Jonsson Funk, Daniel Westreich, Chris Wiesen, Til Stürmer, M. Alan Brookhart, and Marie Davidian.  Doubly Robust Estimation of Causal Effects.  _American Journal of Epidemiology_ , 173(7):761–767, 03 2011.  ISSN 0002-9262.  doi: 10.1093/aje/kwq439.  URL https://doi.org/10.1093/aje/kwq439.
  * Hernán and Robins [2006] Miguel A Hernán and James M Robins.  Estimating causal effects from epidemiological data.  _Journal of Epidemiology & Community Health_, 60(7):578–586, 2006.
  * Miao et al. [2018] Wang Miao, Zhi Geng, and Eric Tchetgen Tchetgen.  Identifying causal effects with proxy variables of an unmeasured confounder.  _Biometrika_ , 105(4):987–993, December 2018\.
  * Tchetgen Tchetgen et al. [2020] Eric J Tchetgen Tchetgen, Andrew Ying, Yifan Cui, Xu Shi, and Wang Miao.  An introduction to proximal causal learning.  September 2020.
  * Mastouri et al. [2021] Afsaneh Mastouri, Yuchen Zhu, Limor Gultchin, Anna Korba, Ricardo Silva, Matt Kusner, Arthur Gretton, and Krikamol Muandet.  Proximal causal learning with kernels: Two-Stage estimation and moment restriction.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 7512–7523. PMLR, 2021\.
  * Xu et al. [2021] Liyuan Xu, Heishiro Kanagawa, and Arthur Gretton.  Deep proxy causal learning and its application to confounded bandit policy evaluation.  _Adv. Neural Inf. Process. Syst._ , 34:26264–26275, December 2021.
  * Muandet et al. [2020] Krikamol Muandet, Wittawat Jitkrittum, and Jonas Kübler.  Kernel conditional moment test via maximum moment restriction.  In Jonas Peters and David Sontag, editors, _Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)_ , volume 124 of _Proceedings of Machine Learning Research_ , pages 41–50. PMLR, 2020\.
  * Zhang et al. [2020] Rui Zhang, Masaaki Imaizumi, Bernhard Schölkopf, and Krikamol Muandet.  Maximum moment restriction for instrumental variable regression.  October 2020.
  * Kuroki and Pearl [2014] Manabu Kuroki and Judea Pearl.  Measurement bias and effect restoration in causal inference.  _Biometrika_ , 101(2):423–437, March 2014.
  * Cui et al. [2020] Yifan Cui, Hongming Pu, Xu Shi, Wang Miao, and Eric Tchetgen Tchetgen.  Semiparametric proximal causal inference.  November 2020.
  * Ghassami et al. [2022] Amiremad Ghassami, Andrew Ying, Ilya Shpitser, and Eric Tchetgen Tchetgen.  Minimax kernel machine learning for a class of doubly robust functionals with application to proximal causal inference.  151:7210–7239, 2022.
  * Kallus et al. [2021] Nathan Kallus, Xiaojie Mao, and Masatoshi Uehara.  Causal inference under unmeasured confounding with negative controls: A minimax learning approach.  March 2021.
  * Lewis and Syrgkanis [2018] Greg Lewis and Vasilis Syrgkanis.  Adversarial generalized method of moments.  March 2018.
  * Bennett et al. [2019] Andrew Bennett, Nathan Kallus, and Tobias Schnabel.  Deep generalized method of moments for instrumental variable analysis.  May 2019.
  * Dikkala et al. [2020] Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis.  Minimax estimation of conditional moment models.  _Adv. Neural Inf. Process. Syst._ , 33:12248–12262, 2020\.
  * Deaner [2018] Ben Deaner.  Proxy controls and panel data.  September 2018.
  * Singh et al. [2019] Rahul Singh, Maneesh Sahani, and Arthur Gretton.  Kernel instrumental variable regression.  _Adv. Neural Inf. Process. Syst._ , 32, 2019.
  * Singh [2020] Rahul Singh.  Kernel methods for unobserved confounding: Negative controls, proxies, and instruments.  December 2020.
  * Newey and Powell [2003] Whitney K Newey and James L Powell.  Instrumental variable estimation of nonparametric models.  _Econometrica_ , 71(5):1565–1578, September 2003\.
  * Hartford et al. [2017] Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy.  Deep IV: A flexible approach for counterfactual prediction.  In Doina Precup and Yee Whye Teh, editors, _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1414–1423. PMLR, 2017\.
  * Kato et al. [2021] Masahiro Kato, Masaaki Imaizumi, Kenichiro McAlinn, Shota Yasui, and Haruo Kakehi.  Learning causal models from conditional moment restrictions by importance weighting.  September 2021.
  * Serfling [1980] Robert J Serfling.  _Approximation Theorems of Mathematical Statistics_.  John Wiley & Sons, September 1980.
  * Neyshabur et al. [2018] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro.  The role of over-parametrization in generalization of neural networks.  September 2018.
  * Xu et al. [2020] Liyuan Xu, Yutian Chen, Siddarth Srinivasan, Nando de Freitas, Arnaud Doucet, and Arthur Gretton.  Learning deep features in instrumental variable regression.  _arXiv preprint arXiv:2010.07154_ , 2020.
  * Louizos et al. [2017] Christos Louizos, Uri Shalit, Joris M Mooij, David Sontag, Richard Zemel, and Max Welling.  Causal effect inference with deep latent-variable models.  _Advances in neural information processing systems_ , 30, 2017.
  * Matthey et al. [2017] Loic Matthey, Irina Higgins, Demis Hassabis, and Alexander Lerchner.  dsprites: Disentanglement testing sprites dataset.  https://github.com/deepmind/dsprites-dataset/, 2017.
  * Simonyan and Zisserman [2014] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for Large-Scale image recognition.  September 2014.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes] The claims made in the abstract and
introduction are reflected in Sections 4, 5, and 6

    2. (b)

Did you describe the limitations of your work? [Yes] See Section 7

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]
See Section 1 where we discuss potential medical impacts.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
See Section 5 and Appendix A

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] See Appendix
A

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
Available here https://github.com/beamlab-hsph/Neural-Moment-Matching-
Regression

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] See Appendix B and C as well as our code

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes] We reported results across 20 random seeds
in all our Figures and Tables.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See details
in Section 6

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] We
described the fork of assets from Xu et al. [7] in Section 6

    2. (b)

Did you mention the license of the assets? [Yes] See 6, MIT license

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] Available here https://github.com/beamlab-hsph/Neural-Moment-
Matching-Regression

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A] Synthetic data

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A] Synthetic data

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Proofs

######  Lemma 3.

Let $X$ be a random variable taking values in $\mathcal{X}$ and let
$\mathcal{F}$ be a family of measurable functions with
$f\in\mathcal{F}:\mathcal{X}^{2}\to[-M,M]$, with each $f\in\mathcal{F}$
optionally, and possibly not uniquely, (partially) parameterized by
$\theta_{f}\in\Theta_{\mathcal{F}}$,
$\Lambda:\mathcal{F}\times\Theta_{\mathcal{F}}\to\left[0,M_{\Lambda}\right]$,
and $\lambda\geq 0$. Then, for any $\delta>0$, with probability at least
$1-\delta$, any IID sample $S=\left\\{x_{i}\right\\}_{i=1}^{n}$ drawn from
$\mathrm{P}_{X}$ satisfies

$\displaystyle\mathbb{E}f=\mathbb{E}_{X,X^{\prime}}f\left(X,X^{\prime}\right)$
$\displaystyle\leq\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]$
$\displaystyle\qquad+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{1}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]$
$\displaystyle\leq\mathbb{E}f+\lambda
M_{\Lambda}+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)$
$\displaystyle\quad+2M\left(\frac{2}{n}\log\frac{1}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\mathbb{E}f=\mathbb{E}_{X,X^{\prime}}f\left(X,X^{\prime}\right)$
$\displaystyle\leq\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]$
$\displaystyle\qquad+2\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)+6M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]$
$\displaystyle\leq\mathbb{E}f+\lambda
M_{\Lambda}+2\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)$
$\displaystyle\quad+6M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$

where $\mathcal{R}_{S}$ is the empirical Rademacher Complexity, given by:

$\displaystyle\mathcal{R}_{S}\left(\mathcal{F}\right)=\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f\left(x_{i}\right)$

where $\epsilon$ is a Rademacher random vector taking values uniformly in
$\\{-1,1\\}^{n}$, $S_{-i}=\left\\{x_{j}\right\\}_{j=1,j\neq i}^{n}$,
$\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}\right)=n^{-1}\sum_{i=1}^{n}\mathcal{R}_{S_{-i}}\left(\mathcal{F}\right)$,
$\mathcal{F}_{1}=\left\\{g\ \middle|\
\exists_{f\in\mathcal{F},x^{\prime}\in\mathcal{X}}\forall_{x\in\mathcal{X}}\left[g(x)=f\left(x^{\prime},x\right)\right]\right\\}$,
$\mathcal{F}_{2}=\left\\{g\ \middle|\
\exists_{f\in\mathcal{F},x^{\prime}\in\mathcal{X}}\forall_{x\in\mathcal{X}}\left[g(x)=f\left(x,x^{\prime}\right)\right]\right\\}$,
and $\mathcal{R}_{n}$ is the (expected) Rademacher complexity for a sample of
size $n$, $\mathcal{R}_{n}=\mathbb{E}_{S}\mathcal{R}_{S}$, where the
expectation is over all samples, $S$, of size $n$.

Finally, if the elements of $\mathcal{F}$ are symmetric, so that
$\forall_{f\in\mathcal{F},x,x^{\prime}\in\mathcal{X}}\left(f\left(x,x^{\prime}\right)=f\left(x^{\prime},x\right)\right)$,
$\mathcal{F}_{1}=\mathcal{F}_{2}$.

In particular, $\theta_{f}$ might be the weights associated with the neural
network $f$. Note that, as is the case for neural networks, $\theta_{f}$ may
not be uniquely determined by $f$, so that multiple $\theta$s may be
associated with the same $f$. We may also take
$\Theta_{\mathcal{F}}=\emptyset$, so that $f$ is regarded purely as an element
of $\mathcal{F}$.

###### Proof.

Let $\hat{E}_{S}f=\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}f\left(x_{i},x_{j}\right)$,
$\hat{E}_{S,\lambda}f=\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]$,
$\tilde{E}_{S}f=\frac{1}{n}\sum_{i=1}^{n}E_{X}f\left(x_{i},X\right)$,
$\phi(S)=\sup_{f\in\mathcal{F}}\left(\hat{\mathbb{E}}_{S}f-\mathbb{E}f\right)$,
$\phi^{(1)}(S)=\sup_{f\in\mathcal{F}}\left(\hat{E}_{S}f-\tilde{E}_{S}f\right)$,
and
$\phi^{(2)}(S)=\sup_{f\in\mathcal{F}}\left(\tilde{\mathbb{E}}_{S}f-\mathbb{E}f\right)$.
Note that
$\mathbb{E}_{S}\hat{\mathbb{E}}_{S}f=\mathbb{E}_{X,X^{\prime}}f\left(X,X^{\prime}\right)=\mathbb{E}f=\mathbb{E}_{X,X^{\prime}}f\left(X,X^{\prime}\right)=\mathbb{E}_{S}\tilde{\mathbb{E}}_{S}f$.
Also, let $S^{\prime}=\left\\{x_{i}^{\prime}\right\\}_{i=1}^{n}$ and let
$S_{i}=\left\\{x_{i,j}\right\\}_{j=1}^{n}$ be obtained from $S$ by replacing
$x_{i}$ by $x_{i}^{\prime}$, so that $x_{i,j}=x_{j}$ for $j\neq i$ and
$x_{i,i}=x_{i}^{\prime}$. In order to apply McDiarmid’s Inequality, we must
find bounds, $c_{i}$ such that
$\left|\phi\left(S_{i}\right)-\phi(S)\right|\leq c_{i}$ for $i=1,\dots,n$.

$\displaystyle\left|\phi\left(S_{i}\right)-\phi(S)\right|$
$\displaystyle=\left|\sup_{f\in\mathcal{F}}\left(\hat{\mathbb{E}}_{S_{i}}f-\mathbb{E}f\right)-\sup_{f\in\mathcal{F}}\left(\hat{\mathbb{E}}_{S}f-\mathbb{E}f\right)\right|$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left|\left(\hat{\mathbb{E}}_{S_{i}}f-\mathbb{E}f\right)-\left(\hat{\mathbb{E}}_{S}f-\mathbb{E}f\right)\right|$
$\displaystyle=\sup_{f\in\mathcal{F}}\left|\hat{\mathbb{E}}_{S_{i}}f-\hat{\mathbb{E}}_{S}f\right|$
$\displaystyle=\sup_{f\in\mathcal{F}}\left|\frac{1}{n(n-1)}\sum_{j,k=1,k\neq
j}^{n}f\left(x_{i,j},x_{i,k}\right)-\frac{1}{n(n-1)}\sum_{j,k=1,k\neq
j}^{n}f\left(x_{j},x_{k}\right)\right|$
$\displaystyle\leq\frac{1}{n(n-1)}\sup_{f\in\mathcal{F}}\sum_{j,k=1,k\neq
j}^{n}\left|f\left(x_{i,j},x_{i,k}\right)-f\left(x_{j},x_{k}\right)\right|$
$\displaystyle=\frac{1}{n(n-1)}\left(\sum_{j=1,j\neq
k,k=i}^{n}\sup_{f\in\mathcal{F}}\left|f\left(x_{i,j},x_{i,i}\right)-f\left(x_{j},x_{i}\right)\right|\right.$
$\displaystyle\hskip 80.00012pt+\left.\sum_{k=1,k\neq
j,j=i}^{n}\sup_{f\in\mathcal{F}}\left|f\left(x_{i,i},x_{i,k}\right)-f\left(x_{i},x_{k}\right)\right|\right)$
$\displaystyle=\frac{1}{n(n-1)}\left(\sum_{j=1,j\neq
i}^{n}\sup_{f\in\mathcal{F}}\left|f\left(x_{j},x_{i}^{\prime}\right)-f\left(x_{j},x_{i}\right)\right|\right.$
$\displaystyle\hskip 80.00012pt+\left.\sum_{k=1,k\neq
i}^{n}\sup_{f\in\mathcal{F}}\left|f\left(x_{i}^{\prime},x_{k}\right)-f\left(x_{i},x_{k}\right)\right|\right)$
$\displaystyle=\frac{1}{n(n-1)}\left(\sum_{j=1,j\neq
i}^{n}\sup_{f\in\mathcal{F}}2M+\sum_{k=1,k\neq
i}^{n}\sup_{f\in\mathcal{F}}2M\right)\leq\frac{2}{n(n-1)}\cdot(n-1)\cdot 2M$
$\displaystyle=4Mn^{-1}$

so we can choose $c_{i}=c=4Mn^{-1}$. The exponent in McDiarmid’s Inequality is
then
$-2\epsilon^{2}\left(\sum_{i=1}^{n}c_{i}^{2}\right)^{-1}=-2\epsilon^{2}\left(n\cdot\left(4Mn^{-1}\right)^{2}\right)^{-1}=-2\epsilon^{2}\left(16M^{2}n^{-1}\right)^{-1}=-\frac{1}{8}nM^{-2}\epsilon^{2}$.
Setting $\frac{\delta}{2}=e^{-\frac{1}{8}nM^{-2}\epsilon^{2}}$ gives
$\epsilon=\left(-\frac{8M^{2}}{n}\log\frac{\delta}{2}\right)^{\frac{1}{2}}=M\left(\frac{8}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}=2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$.
Then, McDiarmid’s Inequality yields,

$\displaystyle\mathrm{P}\left[\phi(S)-\mathbb{E}_{S}\phi(S)\geq\epsilon\right]\leq\frac{\delta}{2},\quad\mathrm{P}\left[\mathbb{E}_{S}\phi(S)-\phi(S)\geq\epsilon\right]\leq\frac{\delta}{2}$

so that, with probability $1-\frac{\delta}{2}$,
$\phi(S)\leq\mathbb{E}_{S}\phi(S)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$.
We now need to compute $\mathbb{E}_{S}\phi(S)$. However, this is difficult to
do directly, so we instead compute it separately for $\phi^{(1)}$ and
$\phi^{(2)}$. Let $\epsilon$ be a Rademacher random vector taking values
uniformly in $\\{-1,1\\}^{n}$. Then,

$\displaystyle\mathbb{E}_{S}\phi^{(1)}(S)$
$\displaystyle=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\hat{E}_{S}f-\tilde{E}_{S}f\right)$
$\displaystyle=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}^{n}f\left(x_{i},x_{j}\right)-\frac{1}{n}\sum_{i=1}^{n}E_{X}f\left(x_{i},X\right)\right)$
$\displaystyle=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}^{n}f\left(x_{i},x_{j}\right)-\frac{1}{n}\sum_{i=1}^{n}E_{S^{\prime}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}f\left(x_{i},x^{\prime}_{j}\right)\right)$
$\displaystyle=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}E_{S^{\prime}}\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}^{n}\left(f\left(x_{i},x_{j}\right)-f\left(x_{i},x^{\prime}_{j}\right)\right)$
$\displaystyle\leq\mathbb{E}_{S,S^{\prime}}\sup_{f\in\mathcal{F}}\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}^{n}\left(f\left(x_{i},x_{j}\right)-f\left(x_{i},x^{\prime}_{j}\right)\right)$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{S,S^{\prime}}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\left(f\left(x_{i},x_{j}\right)-f\left(x_{i},x^{\prime}_{j}\right)\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{x_{i},S_{-i},S^{\prime}_{-i}}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\left(f\left(x_{i},x_{j}\right)-f\left(x_{i},x^{\prime}_{j}\right)\right)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\epsilon}\mathbb{E}_{x_{i},S_{-i},S^{\prime}_{-i}}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\epsilon_{j}\left(f\left(x_{i},x_{j}\right)-f\left(x_{i},x^{\prime}_{j}\right)\right)$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\left[\mathbb{E}_{x_{i},S_{-i},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\epsilon_{j}f\left(x_{i},x_{j}\right)\right.$ $\displaystyle\hskip
60.00009pt+\left.\mathbb{E}_{x_{i},S^{\prime}_{-i},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}-\epsilon_{j}f\left(x_{i},x^{\prime}_{j}\right)\right]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{x_{i}}\left[\mathbb{E}_{S_{-i},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\epsilon_{j}f\left(x_{i},x_{j}\right)\right.$ $\displaystyle\hskip
60.00009pt+\left.\mathbb{E}_{S_{-i},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\epsilon_{j}f\left(x_{i},x_{j}\right)\right]$
$\displaystyle=\frac{2}{n}\sum_{i=1}^{n}\mathbb{E}_{x_{i}}\mathbb{E}_{S_{-i},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\epsilon_{j}f\left(x_{i},x_{j}\right)$
$\displaystyle=\frac{2}{n}\sum_{i=1}^{n}\mathbb{E}_{x_{n}}\mathbb{E}_{S_{-n},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1}^{n-1}\epsilon_{j}f\left(x_{n},x_{j}\right)$
$\displaystyle=2\mathbb{E}_{x_{n}}\mathbb{E}_{S_{-n},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{j=1}^{n-1}\epsilon_{j}f\left(x_{n},x_{j}\right)=2\mathbb{E}_{X}\mathbb{E}_{S_{-n},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{i=1}^{n-1}\epsilon_{i}f\left(X,x_{i}\right)$
$\displaystyle\leq
2\mathbb{E}_{S_{-n},\epsilon}\sup_{f\in\mathcal{F},x\in\mathcal{X}}\frac{1}{n-1}\sum_{i=1}^{n-1}\epsilon_{i}f\left(x,x_{i}\right)=2\mathbb{E}_{S_{-n}}\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F},x\in\mathcal{X}}\frac{1}{n-1}\sum_{i=1}^{n-1}\epsilon_{i}f\left(x,x_{i}\right)$
$\displaystyle=2\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)$

where, in the seventh line, we note that the inner sum depends only on
$S=\left\\{x_{i}\right\\}\cup S_{-i}$ and $S^{\prime}_{-i}$, but not
$x^{\prime}_{i}$, in the eighth line, we introduce Rademacher variables
because reversing the order of the difference is equivalent to swapping
elements between $S_{-i}$ and $S^{\prime}_{-i}$ and, since the expectation is
over all possible pairs of samples, its value is unchanged, in the tenth line,
we note that negation simply interchanges pairs of Rademacher vectors, so the
expectation is unchanged, and, in the final line, $\mathcal{F}_{1}=\left\\{g\
\middle|\
\exists_{f\in\mathcal{F},x^{\prime}\in\mathcal{X}}\forall_{x\in\mathcal{X}}\left[g(x)=f\left(x^{\prime},x\right)\right]\right\\}$.

$\displaystyle\mathbb{E}_{S}\phi^{(2)}(S)$
$\displaystyle=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\tilde{\mathbb{E}}_{S}f-\mathbb{E}f\right)=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\tilde{\mathbb{E}}_{S}f-\mathbb{E}_{S^{\prime}}\tilde{\mathbb{E}}_{S^{\prime}}f\right)=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\mathbb{E}_{S^{\prime}}\left(\tilde{\mathbb{E}}_{S}f-\tilde{\mathbb{E}}_{S^{\prime}}f\right)$
$\displaystyle\leq\mathbb{E}_{S,S^{\prime}}\sup_{f\in\mathcal{F}}\left(\tilde{\mathbb{E}}_{S}f-\tilde{\mathbb{E}}_{S^{\prime}}f\right)$
$\displaystyle=\mathbb{E}_{S,S^{\prime}}\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\sum_{i=1}^{n}E_{X}f\left(x_{i},X\right)-\frac{1}{n}\sum_{i=1}^{n}E_{X}f\left(x_{i}^{\prime},X\right)\right)$
$\displaystyle=\mathbb{E}_{S,S^{\prime}}\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\sum_{i=1}^{n}\left(E_{X}f\left(x_{i},X\right)-E_{X}f\left(x_{i}^{\prime},X\right)\right)\right)$
$\displaystyle=\mathbb{E}_{\epsilon}\mathbb{E}_{S,S^{\prime}}\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left(E_{X}f\left(x_{i},X\right)-E_{X}f\left(x_{i}^{\prime},X\right)\right)\right)$
$\displaystyle\leq\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}E_{X}f\left(x_{i},X\right)+\mathbb{E}_{S^{\prime},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}-\epsilon_{i}E_{X}f\left(x_{i}^{\prime},X\right)$
$\displaystyle=\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}E_{X}f\left(x_{i},X\right)+\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}E_{X}f\left(x_{i},X\right)$
$\displaystyle=2\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}E_{X}f\left(x_{i},X\right)\leq
2\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F},x\in\mathcal{X}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f\left(x_{i},x\right)$
$\displaystyle=2\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)$

where, in the fifth line, we introduce Rademacher variables because changing
the order of the difference is equivalent to swapping elements between $S$ and
$S^{\prime}$, and, since the expectation is over all possible pairs of
samples, its value is unchanged, in the seventh line, we note that negation
simply interchanges pairs of Rademacher vectors leaving the expectation
unchanged, and, in the final line, $\mathcal{F}_{2}=\left\\{g\ \middle|\
\exists_{f\in\mathcal{F},x^{\prime}\in\mathcal{X}}\forall_{x\in\mathcal{X}}\left[g(x)=f\left(x,x^{\prime}\right)\right]\right\\}$.
Then,

$\displaystyle\mathbb{E}_{S}\phi(S)$
$\displaystyle=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\hat{\mathbb{E}}_{S}f-\mathbb{E}f\right)=\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\hat{\mathbb{E}}_{S}f-\tilde{\mathbb{E}}_{S}f+\tilde{\mathbb{E}}_{S}f-\mathbb{E}f\right)$
$\displaystyle\leq\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\hat{\mathbb{E}}_{S}f-\tilde{\mathbb{E}}_{S}f\right)+\mathbb{E}_{S}\sup_{f\in\mathcal{F}}\left(\tilde{\mathbb{E}}_{S}f-\mathbb{E}f\right)=\mathbb{E}_{S}\phi^{(1)}(S)+\mathbb{E}_{S}\phi^{(2)}(S)$
$\displaystyle=2\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+2\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)$

Finally, combining the above results tells us that, with probability
$1-\frac{\delta}{2}$, $\phi(S)\leq
2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
so
$\hat{\mathbb{E}}_{S}f\leq\mathbb{E}f+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$.
Replacing $\phi(S)$ by
$\phi^{\prime}(S)=\sup_{f\in\mathcal{F}}\left(\mathbb{E}f-\hat{\mathbb{E}}_{S}f\right)$
in the above proof yields
$\mathbb{E}f\leq\hat{\mathbb{E}}_{S}f+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$.
Since $\lambda\geq 0$, $0\leq\Lambda\leq M_{\Lambda}$,
$0\leq\lambda\Lambda\left[f,\theta_{f}\right]\leq\lambda M_{\Lambda}$, so we
also have,

$\displaystyle\mathbb{E}f$
$\displaystyle\leq\hat{\mathbb{E}}_{S}f+\lambda\Lambda\left[f,\theta_{f}\right]+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle=\hat{\mathbb{E}}_{S,\lambda}f+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\hat{\mathbb{E}}_{S,\lambda}f=\hat{\mathbb{E}}_{S}f+\lambda\Lambda\left[f,\theta_{f}\right]$
$\displaystyle\leq\mathbb{E}f+\lambda
M_{\Lambda}+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$

Using $2\delta$ in place of $\delta$, we see that, with probability at least
$1-\delta$,
$\mathbb{E}f\leq\hat{\mathbb{E}}_{S,\lambda}f+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{1}{\delta}\right)^{\frac{1}{2}}$
and $\hat{\mathbb{E}}_{S,\lambda}f\leq\mathbb{E}f+\lambda
M_{\Lambda}+2\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)+2M\left(\frac{2}{n}\log\frac{1}{\delta}\right)^{\frac{1}{2}}$,
yielding the first two inequalities.

In order to obtain results in terms of the empirical Rademacher complexity,
$\mathcal{R}_{S}$, instead of the (expected) Rademacher complexity,
$\mathcal{R}_{n}$, we need to apply McDiarmid’s Inequality a second time. Let
$\mathcal{G}$ be a family of measurable functions with
$g\in\mathcal{G}:\mathcal{X}\to[-M,M]$, Let
$\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{G}\right)=n^{-1}\sum_{i=1}^{n}\mathcal{R}_{S_{-i}}\left(\mathcal{G}\right)$,
so that
$\mathbb{E}_{S}\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{G}\right)=\mathcal{R}_{n-1}\left(\mathcal{G}\right)$.
Then,

$\displaystyle\left|\hat{\mathcal{R}}_{n-1,S_{i}}\left(\mathcal{G}\right)-\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{G}\right)\right|$
$\displaystyle=\left|n^{-1}\sum_{k=1}^{n}\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}\frac{1}{n-1}\sum_{j=1,j\neq
k}^{n}\epsilon_{j}g\left(x_{i,j}\right)-n^{-1}\sum_{k=1}^{n}\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}\frac{1}{n-1}\sum_{j=1,j\neq
k}^{n}\epsilon_{j}g\left(x_{j}\right)\right|$
$\displaystyle=\frac{1}{n(n-1)}\left|\sum_{k=1}^{n}\mathbb{E}_{\epsilon}\left(\sup_{g\in\mathcal{G}}\sum_{j=1,j\neq
k}^{n}\epsilon_{j}g\left(x_{i,j}\right)-\sup_{g\in\mathcal{G}}\sum_{j=1,j\neq
k}^{n}\epsilon_{j}g\left(x_{j}\right)\right)\right|$
$\displaystyle\leq\frac{1}{n(n-1)}\sum_{k=1}^{n}\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}\sum_{j=1,j\neq
k}^{n}\left|\epsilon_{j}\left(g\left(x_{i,j}\right)-g\left(x_{j}\right)\right)\right|$
$\displaystyle=\frac{1}{n(n-1)}\sum_{k=1}^{n}\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}\left|g\left(x_{i}^{\prime}\right)-g\left(x_{i}\right)\right|I(k\neq
i)$ $\displaystyle\leq\frac{1}{n(n-1)}\sum_{k=1}^{n}I(k\neq
i)\mathbb{E}_{\epsilon}2M=\frac{1}{n(n-1)}\sum_{k=1,k\neq i}^{n}2M$
$\displaystyle=2Mn^{-1}$

where, in the fifth line, we note that the term inside the absolute value is
potentially nonzero if and only if it involves $x_{i}^{\prime}$, which occurs
in each sum over $j$ exactly once, except in the case in which $k\neq i$, in
which case it does not occur at all.

$\displaystyle\left|\mathcal{R}_{S_{i}}\left(\mathcal{G}\right)-\mathcal{R}_{S}\left(\mathcal{G}\right)\right|$
$\displaystyle=\left|\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}n^{-1}\sum_{j=1}^{n}\epsilon_{j}g\left(x_{i,j}\right)-\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}n^{-1}\sum_{j=1}^{n}\epsilon_{j}g\left(x_{j}\right)\right|$
$\displaystyle\leq
n^{-1}\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}\sum_{j=1}^{n}\left|\epsilon_{j}\left(g\left(x_{i,j}\right)-g\left(x_{j}\right)\right)\right|=n^{-1}\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}\left|g\left(x_{i}^{\prime}\right)-g\left(x_{i}\right)\right|$
$\displaystyle\leq n^{-1}\mathbb{E}_{\epsilon}2M$ $\displaystyle=2Mn^{-1}$

Combining the above results gives,

$\displaystyle\left|\left(\hat{\mathcal{R}}_{n-1,S_{i}}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S_{i}}\left(\mathcal{F}_{2}\right)\right)-\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)\right|$
$\displaystyle=\left|\left(\hat{\mathcal{R}}_{n-1,S_{i}}\left(\mathcal{F}_{1}\right)-\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)\right)+\left(\mathcal{R}_{S_{i}}\left(\mathcal{F}_{2}\right)-\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)\right|$
$\displaystyle\leq\left|\hat{\mathcal{R}}_{n-1,S_{i}}\left(\mathcal{F}_{1}\right)-\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)\right|+\left|\mathcal{R}_{S_{i}}\left(\mathcal{F}_{2}\right)-\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right|=2Mn^{-1}+2Mn^{-1}$
$\displaystyle=4Mn^{-1}$

This is the same value we obtained previously, so that the corresponding
$\epsilon=2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$. Then,
McDiarmid’s Inequality gives,

$\displaystyle\mathrm{P}\left[\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)-\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)\geq\epsilon\right]$
$\displaystyle\leq\frac{\delta}{2}$
$\displaystyle\mathrm{P}\left[\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\right)-\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)\geq\epsilon\right]$
$\displaystyle\leq\frac{\delta}{2}$

so that, with probability $1-\frac{\delta}{2}$,
$\mathcal{R}_{n-1}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2}\right)\leq\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$.
Combining this with the previous results shows that, with probability at least
$1-\delta$,
$\mathbb{E}f\leq\hat{\mathbb{E}}_{S,\lambda}f+2\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)+\left(2M+2\cdot
2M\right)\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}=\hat{\mathbb{E}}_{S,\lambda}f+2\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)+6M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
and $\hat{\mathbb{E}}_{S,\lambda}f\leq\mathbb{E}f+\lambda
M_{\Lambda}+2\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2}\right)\right)+6M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$,
yielding the second pair of inequalities.

Finally, if the elements of $\mathcal{F}$ are symmetric, so that
$\forall_{f\in\mathcal{F},x,x^{\prime}\in\mathcal{X}}f\left(x,x^{\prime}\right)=f\left(x^{\prime},x\right)$,
if $g\in\mathcal{F}_{1}$ then
$\exists_{f\in\mathcal{F},x^{\prime}\in\mathcal{X}}\forall_{x\in\mathcal{X}}\left(g(x)=f\left(x^{\prime},x\right)=f\left(x,x^{\prime}\right)\right)$,
so $g\in\mathcal{F}_{2}$ as well and
$\mathcal{F}_{1}\subseteq\mathcal{F}_{2}$. Likewise, if $g\in\mathcal{F}_{2}$
then
$\exists_{f\in\mathcal{F},x^{\prime}\in\mathcal{X}}\forall_{x\in\mathcal{X}}\left(g(x)=f\left(x,x^{\prime}\right)=f\left(x^{\prime},x\right)\right)$,
so $g\in\mathcal{F}_{1}$ as well and
$\mathcal{F}_{2}\subseteq\mathcal{F}_{1}$. Thus,
$\mathcal{F}_{1}=\mathcal{F}_{2}$.

∎

######  Corollary 4.

The inequalities in Lemma 3 can be strengthened to the following:

$\displaystyle\mathbb{E}f\leq$ $\displaystyle\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]$
$\displaystyle\qquad+2\mathbb{E}_{X}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,X}\right)\right)+2M\left(\frac{2}{n}\log\frac{1}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]\leq\mathbb{E}f+\lambda
M_{\Lambda}$
$\displaystyle\qquad+2\mathbb{E}_{X}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,X}\right)\right)+2M\left(\frac{2}{n}\log\frac{1}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\mathbb{E}f\leq$ $\displaystyle\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]$
$\displaystyle\qquad+2\mathbb{E}_{X}\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2,X}\right)\right)+6M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}f\left(x_{i},x_{j}\right)+\lambda\Lambda\left[f,\theta_{f}\right]\leq\mathbb{E}f+\lambda
M_{\Lambda}$
$\displaystyle\qquad+2\mathbb{E}_{X}\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2,X}\right)\right)+6M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$

$\mathcal{F}_{1,x}=\left\\{g_{x}\ \middle|\
\exists_{f\in\mathcal{F}}\forall_{x^{\prime}\in\mathcal{X}}\left[g_{x}\left(x^{\prime}\right)=f\left(x,x^{\prime}\right)\right]\right\\}$,
$\mathcal{F}_{2,x}=\left\\{g_{x}\ \middle|\
\exists_{f\in\mathcal{F}}\forall_{x^{\prime}\in\mathcal{X}}\left[g_{x}\left(x^{\prime}\right)=f\left(x^{\prime},x\right)\right]\right\\}$

If the elements of $\mathcal{F}$ are symmetric, then
$\mathcal{F}_{1,x}=\mathcal{F}_{2,x}$.

###### Proof.

This follows directly from the proof of Lemma 3 in which we show that
$\mathbb{E}_{S}\phi^{(1)}(S)\leq
2\mathbb{E}_{X}\mathbb{E}_{S_{-n},\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n-1}\sum_{i=1}^{n-1}\epsilon_{i}f\left(X,x_{i}\right)=2\mathbb{E}_{X}\mathcal{R}_{n-1}\left(\mathcal{F}_{1,X}\right)$
and $\mathbb{E}_{S}\phi^{(2)}(S)\leq
2\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}E_{X}f\left(x_{i},X\right)\leq
2\mathbb{E}_{X}\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f\left(x_{i},X\right)\\\
=2\mathbb{E}_{X}\mathcal{R}_{n}\left(\mathcal{F}_{2,x}\right)$. Using these
sharper bounds in the expressions (obtained from McDiarmid’s inequality) in
Lemma 3 (and using $2\delta$ in place of $\delta$) yields the first pair of
equations.

In order to obtain the second pair of expressions, we again need to apply
McDiarmid’s inequality. Using results from the proof of lemma 3,

$\displaystyle\left|\mathbb{E}_{X}\left(\hat{\mathcal{R}}_{n-1,S_{i}}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{S_{i}}\left(\mathcal{F}_{2,X}\right)\right)-\mathbb{E}_{X}\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2,X}\right)\right)\right|$
$\displaystyle=\left|\mathbb{E}_{X}\left(\hat{\mathcal{R}}_{n-1,S_{i}}\left(\mathcal{F}_{1,X}\right)-\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1,X}\right)\right)+\mathbb{E}_{X}\left(\mathcal{R}_{S_{i}}\left(\mathcal{F}_{2,X}\right)-\mathcal{R}_{S}\left(\mathcal{F}_{2,X}\right)\right)\right|$
$\displaystyle\leq\mathbb{E}_{X}\left|\hat{\mathcal{R}}_{n-1,S_{i}}\left(\mathcal{F}_{1,X}\right)-\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1,X}\right)\right|+\mathbb{E}_{X}\left|\mathcal{R}_{S_{i}}\left(\mathcal{F}_{2,X}\right)-\mathcal{R}_{S}\left(\mathcal{F}_{2,X}\right)\right|$
$\displaystyle=\mathbb{E}_{X}2Mn^{-1}+\mathbb{E}_{X}2Mn^{-1}=2Mn^{-1}+2Mn^{-1}$
$\displaystyle=4Mn^{-1}$

Since this is the same value of $c_{i}$ we obtained in lemma 3, McDiarmid’s
Inequality holds for
$\epsilon=2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$, so
that, with probability at least $1-\frac{\delta}{2}$,
$\mathbb{E}_{X}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,X}\right)\right)\leq\mathbb{E}_{X}\left(\hat{\mathcal{R}}_{n-1,S}\left(\mathcal{F}_{1,X}\right)+\mathcal{R}_{S}\left(\mathcal{F}_{2,X}\right)\right)+2M\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$.
Then, the second pair of expressions is obtained by replacing $\delta$ by
$\frac{\delta}{2}$ in the first pair of expressions and combining the result
with the above inequality. Since each of these expressions hold with
probability at least $1-\frac{\delta}{2}$, their combination will hold with
probability at least $1-2\cdot\frac{\delta}{2}=1-\delta$, as claimed.

If the elements of $\mathcal{F}$ is symmetric, so that
$\forall_{f\in\mathcal{F},x,x^{\prime}\in\mathcal{X}}f\left(x,x^{\prime}\right)=f\left(x^{\prime},x\right)$,
if $g\in\mathcal{F}_{1,x}$ then
$\exists_{f\in\mathcal{F}}\forall_{x^{\prime}\in\mathcal{X}}\left[g_{x}\left(x^{\prime}\right)=f\left(x,x^{\prime}\right)=f\left(x^{\prime},x\right)\right]$,
so $g\in\mathcal{F}_{2,x}$ as well and
$\mathcal{F}_{1,x}\subseteq\mathcal{F}_{2,x}$. Likewise, if
$g\in\mathcal{F}_{2,x}$
$\exists_{f\in\mathcal{F}}\forall_{x^{\prime}\in\mathcal{X}}\left[g_{x}\left(x^{\prime}\right)=f\left(x^{\prime},x\right)=f\left(x,x^{\prime}\right)\right]$,
so $g\in\mathcal{F}_{1,x}$ as well and
$\mathcal{F}_{2,x}\subseteq\mathcal{F}_{1,x}$. Thus,
$\mathcal{F}_{1,x}=\mathcal{F}_{2,x}$.

∎

######  Lemma 5.

Let $h\in\mathcal{H}:\mathcal{A}\times\mathcal{W}\times\mathcal{X}\to[-M,M]$
such that if $h\in\mathcal{H}$, $-h\in\mathcal{H}$,
$\mathcal{Y}\subseteq[-M,M]$,
$k:\left(\mathcal{A}\times\mathcal{Z}\times\mathcal{X}\right)^{2}\to\left[-M_{k},M_{k}\right]$,
$\forall_{a,a^{\prime}\in\mathcal{A},x,x^{\prime}\in\mathcal{X},z,z^{\prime}\in\mathcal{Z}}\left(k\left(\left(a,x,z\right),\left(a^{\prime},x^{\prime},z^{\prime}\right)\right)=k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right)$,
and $\Xi=(A,W,X,Y,Z)$. Additionally, let
$f_{h,k}\left(\left(a,w,x,y,z\right),\left(a^{\prime},w^{\prime},x^{\prime},y^{\prime},z^{\prime}\right)\right)=\left(y-h\left(a,w,x\right)\right)\\\
\times\left(y^{\prime}-h\left(a^{\prime},w^{\prime},x^{\prime}\right)\right)k\left(\left(a,x,z\right),\left(a^{\prime},x^{\prime},z^{\prime}\right)\right)$
Then,

$\displaystyle\mathbb{E}_{\Xi}\mathcal{R}_{n}\left(\mathcal{F}_{1,\Xi}\right)$
$\displaystyle=\mathbb{E}_{\Xi}\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)$
$\displaystyle\leq
2M\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\qquad+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=2M\mathbb{E}_{A,X,Z}\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$ $\displaystyle\leq
2M\mathbb{E}_{S,\epsilon}\sup_{h\in\mathcal{H},a\in\mathcal{A},x\in\mathcal{X},z\in\mathcal{Z}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(a,x,z\right)\right)$
$\displaystyle\qquad+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=2M\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle\mathcal{F}^{\prime}_{a,x,z}=\left\\{f_{a,x,z}\ \middle|\
\exists_{h\in\mathcal{H}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f_{a,x,z}\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$
$\displaystyle\mathcal{F}^{\prime}=\left\\{f\ \middle|\
\exists_{h\in\mathcal{H},a\in\mathcal{A},x\in\mathcal{X},z\in\mathcal{Z}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$

###### Proof.

Let $\mathcal{F}=\left\\{g\ \middle|\
\exists_{h\in\mathcal{H}}\left(g=f_{h,k}\right)\right\\}$. Since, for all
$h\in\mathcal{H}$, $f_{h,k}$ is manifestly symmetric, we have
$\mathcal{F}_{1}=\mathcal{F}_{2}$ and
$\mathcal{F}_{1,\xi}=\mathcal{F}_{2,\xi}$, where these classes are defined in
lemma 3 and corollary 4, respectively. We now compute
$\mathbb{E}_{\Xi}\mathcal{R}_{n}\left(\mathcal{F}_{1,\Xi}\right)=\mathbb{E}_{\Xi}\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)$.

$\displaystyle\mathbb{E}_{\Xi}$
$\displaystyle\mathcal{R}_{n}\left(\mathcal{F}_{1,\Xi}\right)=\mathbb{E}_{\Xi}\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)=\mathbb{E}_{\Xi}\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f\left(x_{i},\Xi\right)$
$\displaystyle=\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f\left(\left(a_{i},w_{i},x_{i},y_{i},z_{i}\right),\left(A,W,X,Y,Z\right)\right)$
$\displaystyle=\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left(y_{i}-h\left(a_{i},w_{i},x_{i}\right)\right)\left(Y-h\left(A,W,X\right)\right)$
$\displaystyle\hskip 120.00018pt\times
k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle=\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\left(Y-h\left(A,W,X\right)\right)\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left(y_{i}-h\left(a_{i},w_{i},x_{i}\right)\right)$
$\displaystyle\hskip 200.0003pt\times
k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\leq\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}Y\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\quad+\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}-Y\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\quad+\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}-h\left(A,W,X\right)\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\quad+\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}h\left(A,W,X\right)\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$

We analyze each of these four terms separately.

$\displaystyle\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}$
$\displaystyle\sup_{h\in\mathcal{H}}Y\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle=\mathbb{E}_{A,X,Y,Z,S,\epsilon}Y\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle=\mathbb{E}_{A,X,Y,Z,S}Y\cdot\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\epsilon}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle=\mathbb{E}_{A,X,Y,Z,S}Y\cdot\frac{1}{n}\sum_{i=1}^{n}0\cdot
y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)=\mathbb{E}_{Y}Y\cdot
0$ $\displaystyle=0$

$\displaystyle\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}$
$\displaystyle\sup_{h\in\mathcal{H}}-Y\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\leq\mathbb{E}_{A,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\left|Y\right|\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)\right|$
$\displaystyle\leq\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}M\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)\right|$
$\displaystyle=M\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$

where the final equality is due to the fact that $h\in\mathcal{H}$ if and only
if $-h\in\mathcal{H}$, so that the supremum of the sum will be equal to the
supremum of its absolute value.

$\displaystyle\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}\sup_{h\in\mathcal{H}}h\left(A,W,X\right)\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\leq\mathbb{E}_{A,W,X,Z,S,\epsilon}\sup_{h,h^{\prime}\in\mathcal{H}}h^{\prime}\left(A,W,X\right)\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\leq\mathbb{E}_{A,W,X,Z,S,\epsilon}\sup_{h,h^{\prime}\in\mathcal{H}}\left|h^{\prime}\left(A,W,X\right)\right|\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)\right|$
$\displaystyle\leq\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}M\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)\right|$
$\displaystyle=M\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$

where the final equality follows, as above, because $h\in\mathcal{H}$ if and
only if $-h\in\mathcal{H}$.

$\displaystyle\mathbb{E}_{A,W,X,Y,Z,S,\epsilon}$
$\displaystyle\sup_{h\in\mathcal{H}}-h\left(A,W,X\right)\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\leq\mathbb{E}_{A,W,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\left|h\left(A,W,X\right)\right|\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)\right|$
$\displaystyle\leq\mathbb{E}_{A,X,Z,S,\epsilon}M\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)\right|$
$\displaystyle=M\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\\{-1,1\\}}h\cdot\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}y_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle=M\mathbb{E}_{A,X,Z,S}\mathbb{E}_{\epsilon}\sup_{h\in\\{-1,1\\}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}hy_{i}k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\leq M\cdot\mathbb{E}_{A,X,Z,S}MM_{k}\left(2\log
2\right)^{\frac{1}{2}}n^{-\frac{1}{2}}=M\cdot MM_{k}\left(2\log
2\right)^{\frac{1}{2}}n^{-\frac{1}{2}}$ $\displaystyle=\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

where the final inequality follows from Massart’s Finite Lemma using
$\left|yk\right|\leq MM_{k}$. Combining these results gives,

$\displaystyle\mathbb{E}_{\Xi}\mathcal{R}_{n}\left(\mathcal{F}_{1,\Xi}\right)$
$\displaystyle=\mathbb{E}_{\Xi}\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)$
$\displaystyle\leq 0+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle\quad+M\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\quad+M\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle=2M\mathbb{E}_{A,X,Z,S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\qquad+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=2M\mathbb{E}_{A,X,Z}\mathbb{E}_{S,\epsilon}\sup_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(A,X,Z\right)\right)$
$\displaystyle\qquad+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=2M\mathbb{E}_{A,X,Z}\mathbb{E}_{S,\epsilon}\sup_{f_{A,X,Z}\in\mathcal{F}^{\prime}_{A,X,Z}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f_{A,X,Z}\left(a_{i},w_{i},x_{i},z_{i}\right)$
$\displaystyle\qquad+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=2M\mathbb{E}_{A,X,Z}\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$ $\displaystyle\leq
2M\mathbb{E}_{S,\epsilon}\sup_{h\in\mathcal{H},a\in\mathcal{A},x\in\mathcal{X},z\in\mathcal{Z}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}h\left(a_{i},w_{i},x_{i}\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(a,x,z\right)\right)$
$\displaystyle\qquad+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=2M\mathbb{E}_{S,\epsilon}\sup_{f\in\mathcal{F}^{\prime}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f\left(a_{i},w_{i},x_{i},z_{i}\right)+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=2M\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle\mathcal{F}^{\prime}_{a,x,z}=\left\\{f_{a,x,z}\ \middle|\
\exists_{h\in\mathcal{H}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f_{a,x,z}\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$
$\displaystyle\mathcal{F}^{\prime}=\left\\{f\ \middle|\
\exists_{h\in\mathcal{H},a\in\mathcal{A},x\in\mathcal{X},z\in\mathcal{Z}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$

∎

######  Lemma 6.

Let $\mathcal{X}$ be a measurable space, $\mu$ be a $\sigma$-finite measure on
$\mathcal{X}$, $\mathcal{F}_{0}$ be a collection of $\mu$-measurable
functions, with $f\in\mathcal{F}_{0}:\mathcal{X}\to\mathbb{R}$,
$k:\mathcal{X}^{2}\to\mathbb{R}$ be symmetric and measurable with respect to
the product measure ($\mu\times\mu$), and $\mathcal{F}$ be the quotient space
of $\mathcal{F}_{0}$ in which functions are identified if they are equal
$\mu$-almost everywhere. For $f,g\in\mathcal{F}_{0}$, define the bilinear form
$\langle f,g\rangle_{k}=\int f(x)k(x,y)g(y)d\mu(x,y)$, where $\mu$ is the
product measure. Then, $\langle\rangle_{k}$ is an inner product on
$\mathcal{F}$ if and only if $k$ is an Integrally Strictly Positive Definite
(ISPD) kernel, so that, for all $f\in\mathcal{F}_{0}$ such that $f\neq 0$
$\mu$-almost everywhere, $\int f(x)k(x,y)f(y)d\mu(x,y)>0$. Further, if $k$ is
ISPD, then it defines a metric on $\mathcal{F}$ by
$d_{k}(f,g)=\|f-g\|_{k}=\langle f-g,f-g\rangle_{k}^{\frac{1}{2}}$.

###### Proof.

For $f,g\in\mathcal{F}_{0}$,

$\displaystyle\langle cf+g,h\rangle_{k}$
$\displaystyle=\int(cf+g)(x)k(x,y)h(y)d\mu(x,y)$ $\displaystyle=c\int
f(x)k(x,y)h(y)d\mu(x,y)+\int g(x)k(x,y)h(y)d\mu(x,y)$ $\displaystyle=c\langle
f,h\rangle_{k}+\langle g,h\rangle_{k}$ $\displaystyle\langle f,g\rangle_{k}$
$\displaystyle=\int f(x)k(x,y)g(y)d\mu(x,y)=\int g(y)k(y,x)f(x)d\mu(x,y)$
$\displaystyle=\int g(x)k(x,y)f(y)d\mu(x,y)$ $\displaystyle=\langle
g,f\rangle_{k}$

so $\langle\rangle_{k}$ is a bilinear form, as claimed.

To see that $\langle\rangle_{k}$ is well defined on $\mathcal{F}$. Note, that,
if $f=f^{\prime}$ a.e., then

$\displaystyle\left|\langle f,g\rangle_{k}-\langle
f^{\prime},g\rangle_{k}\right|$ $\displaystyle=\left|\int
f(x)k(x,y)g(y)d\mu(x,y)-\int f^{\prime}(x)k(x,y)g(y)d\mu(x,y)\right|$
$\displaystyle\leq\int\left|f(x)-f^{\prime}(x)\right|\left|k(x,y)\right|\left|g(y)\right|d\mu(x,y)$
$\displaystyle=\int\left|\left(f-f^{\prime}\right)(x)\right|\left|k(x,y)\right|\left|g(y)\right|d\mu(x,y)$
$\displaystyle=\int\int\left|\left(f-f^{\prime}\right)(x)\right|\left|k(x,y)\right|\left|g(y)\right|d\mu(x)d\mu(y)=\int
0d\mu(y)$ $\displaystyle=0$

where, in the fourth line, we use Tonelli’s Theorem and the fact that
$f-f^{\prime}=0$ a.e., so $\left|f^{\prime}-f\right||k||g|=0$ $\mu_{x}$-a.e.
and, thus, the inner integral is $0$. Thus, if $f=f^{\prime}$ a.e., $\langle
f,g\rangle_{k}=\langle f^{\prime},g\rangle_{k}$. By the symmetry of the
bilinear form, if $g=g^{\prime}$ a.e. $\langle f^{\prime},g\rangle_{k}=\langle
f^{\prime},g^{\prime}\rangle_{k}$, so that, if $f=f^{\prime},g=g^{\prime}$
a.e. $\langle f,g\rangle_{k}=\langle f^{\prime},g^{\prime}\rangle_{k}$, so
$\langle\rangle_{k}$ is well defined on $\mathcal{F}$.

If $k$ is also ISPD, then, for $f\neq 0$ $\mu$-almost everywhere, $\langle
f,f\rangle_{k}=\int f(x)k(x,y)f(y)d\mu(x,y)>0$, so that, combined with the
above results, $\langle\rangle_{k}$ is an inner product on $\mathcal{F}$.
Conversely, if $\langle\rangle_{k}$ is an inner product, then, for $f\neq 0$
$\mu$-almost everywhere, $\langle f,f\rangle_{k}>0$, so $k$ is ISPD, by
definition.

Since $\langle\rangle_{k}$ is an inner product, it defines a norm $\|\|_{k}$
on $\mathcal{F}$ by $\|f\|_{k}=\langle f,f\rangle_{k}^{\frac{1}{2}}$. Let
$d_{k}(f,g)=\|f-g\|_{k}$. Since $\|\|_{k}$ is a norm,
$d_{k}(f,g)=\|f-g\|_{k}=|-1|\|g-f\|_{k}=\|g-f\|_{k}=d_{k}(g,f)$ and, if $f\neq
g$ a.e., then, $d_{k}(f,g)=\|f-g\|_{k}>0$, while
$d_{k}(f,f)=\|f-f\|_{k}=\|0\|_{k}=0$. Finally,
$d_{k}(f,h)=\|f-h\|_{k}=\|f-g+g-h\|_{k}\leq\|f-g\|_{k}+\|g-h\|_{k}=d_{k}(f,g)+d_{k}(g,h)$
by the subadditivity of the norm, so that the triangle inequality holds and
$d_{k}$ is a metric on $\mathcal{F}$, as claimed.

∎

######  Theorem 1.

Let $\tilde{h}_{k}$ minimize $R_{k}(h)$ and $\hat{h}_{k,U,\lambda,n}$ minimize
$\hat{R}_{k,U,\lambda,n}(h)$ for $h\in\mathcal{H}$,
$k:(\mathcal{A}\times\mathcal{X}\times\mathcal{Z})^{2}\to[-M_{k},M_{k}]$,
$\Lambda:\mathcal{H}\times\Theta_{h}\to[-0,M_{\lambda}]$, and let
$h^{*}:\mathcal{A}\times\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ satisfy
$\mathbb{E}\left[Y-h^{*}(A,W,X)\middle|A,X,Z\right]=0$
$\mathrm{P}_{A,X,Z}$-almost surely, where

$\displaystyle R_{k}(h)$
$\displaystyle=\mathbb{E}\left[\left(Y-h\left(A,W,X\right)\right)\left(Y^{\prime}-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$
$\displaystyle\hat{R}_{k,U,\lambda,n}(h)$
$\displaystyle=\frac{1}{n(n-1)}\sum_{i,j=1,i\neq
j}^{n}\left[\left(y_{i}-h\left(a_{i},w_{i},x_{i}\right)\right)\left(y_{j}-h\left(a_{j},w_{j},x_{j}\right)\right)\right.$
$\displaystyle\hskip
120.00018pt\times\left.k\left(\left(a_{i},x_{i},z_{i}\right),\left(a_{j},x_{j},z_{j}\right)\right)\right]+\lambda\Lambda[h,\theta_{h}]$

Also let,

$\displaystyle d_{k}^{2}\left(h,h^{\prime}\right)$
$\displaystyle=\mathbb{E}\left[\left(h\left(A,W,X\right)-h^{\prime}\left(A,W,X\right)\right)\left(h\left(A^{\prime},W^{\prime},X^{\prime}\right)-h^{\prime}\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)\right.$
$\displaystyle\hskip
60.00009pt\times\left.k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$

Then, $d_{k}^{2}\left(h^{*},h\right)=R_{k}(h)$ and, with probability at least
$1-\delta$,

$\displaystyle d_{k}^{2}\left(h^{*},\hat{h}_{k,U,\lambda,n}\right)$
$\displaystyle\leq d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$ $\displaystyle\leq
d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

Further, if Assumption 5 holds, so $k$ is ISPD, then $d_{k}$ is a metric on
$L^{2}_{\mathcal{AXZ}}$ and, if the right hand side of the inequality goes to
zero as $n$ goes to infinity,
$d_{k}\left(\mathbb{E}\left[h^{*}\middle|A,X,Z\right]-\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\right)\xrightarrow{\mathrm{P}}0$
so
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$
in $d_{k}$. Also,
$\left\|\mathbb{E}\left[h^{*}\middle|A,X,Z\right]-\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\right\|_{\mathrm{P}_{A,X,Z}}\xrightarrow{\mathrm{P}}0$
so
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$
in $L^{2}\left(\mathrm{P}_{\mathcal{A,X,Z}}\right)$-norm.

$\displaystyle\mathcal{F}^{\prime}_{a,x,z}=\left\\{f_{a,x,z}\ \middle|\
\exists_{h\in\mathcal{H}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f_{a,x,z}\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$
$\displaystyle\mathcal{F}^{\prime}=\left\\{f\ \middle|\
\exists_{h\in\mathcal{H},a\in\mathcal{A},x\in\mathcal{X},z\in\mathcal{Z}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$

###### Proof.

Let $\Xi=\left\\{A,W,X,Y,Z\right\\}$. Since $\tilde{h}_{k}$ minimizes
$R_{k}(h)$ and $\hat{h}_{k,U,\lambda,n}$ minimizes
$\hat{R}_{k,U,\lambda,n}(h)$ for $h\in\mathcal{H}$,
$\hat{R}_{k,U,\lambda,n}\left(\hat{h}_{k,U,\lambda,n}\right)\leq\hat{R}_{k,U,\lambda,n}\left(\tilde{h}_{k}\right)$.

Taking
$f\left(\left(a,w,x,y,z\right),\left(a^{\prime},w^{\prime},x^{\prime},y^{\prime},z^{\prime}\right)\right)=\left(y-h\left(a,w,x\right)\right)\left(y^{\prime}-h\left(a^{\prime},w^{\prime},x^{\prime}\right)\right)\\\
k\left(\left(a,x,z\right),\left(a^{\prime},x^{\prime},z^{\prime}\right)\right)$,
noting that $|f|\leq(M+M)^{2}\cdot M_{k}=(2M)^{2}M_{k}=4M^{2}M_{k}$, and
applying lemma 3 and corollary 4 to $R_{k}(h)=\mathbb{E}f$ and
$\hat{R}_{k,U,\lambda,n}(h)=\hat{E}_{S,\lambda}f$ tells us that, with
probability at least $1-\frac{\delta}{2}$,

$\displaystyle R_{k}(h)$
$\displaystyle\leq\hat{R}_{k,U,\lambda,n}(h)+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\hat{R}_{k,U,\lambda,n}(h)$ $\displaystyle\leq R_{k}(h)+\lambda
M_{\lambda}+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$

so, with probability at least $1-\delta$,

$\displaystyle R_{k}\left(\hat{h}_{k,U,\lambda,n}\right)$
$\displaystyle\leq\hat{R}_{k,U,\lambda,n}\left(\hat{h}_{k,U,\lambda,n}\right)+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq\hat{R}_{k,U,\lambda,n}\left(\tilde{h}_{k}\right)+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+4\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$

Applying lemma 5 yields,

$\displaystyle R_{k}\left(\hat{h}_{k,U,\lambda,n}\right)$ $\displaystyle\leq
R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+4\left(2M\mathbb{E}_{A,X,Z}\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+2M\mathbb{E}_{A,X,Z}\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+4\left(\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}(n-1)^{-\frac{1}{2}}+\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+4\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}\left(\left(\frac{n}{n-1}\right)^{\frac{1}{2}}+1\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+4\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}\cdot\frac{5}{2}$
$\displaystyle=R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$ $\displaystyle\leq
R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\qquad+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

By assumption, $h^{*}$ satisfies
$\mathbb{E}\left[Y-h^{*}(A,X,X)\middle|A,X,Z\right]=0$
$\mathrm{P}_{A,X,Z}$-almost surely, so that,

$\displaystyle\mathbb{E}\left[Y-h(A,W,X)\middle|A,X,Z\right]=\mathbb{E}\left[Y-h^{*}(A,W,X)+h^{*}(A,W,X)-h(A,W,X)\middle|A,X,Z\right]$
$\displaystyle=\mathbb{E}\left[Y-h^{*}(A,W,X)\middle|A,X,Z\right]+\mathbb{E}\left[h^{*}(A,W,X)-h(A,W,X)\middle|A,X,Z\right]$
$\displaystyle=0+\mathbb{E}\left[h^{*}(A,W,X)-h(A,W,X)\middle|A,X,Z\right]$
$\displaystyle=\mathbb{E}\left[h^{*}(A,W,X)-h(A,W,X)\middle|A,X,Z\right]$

$\mathrm{P}_{A,X,Z}$-almost surely. Then,

$\displaystyle R_{k}(h)$
$\displaystyle=\mathbb{E}\left[\left(Y-h\left(A,W,X\right)\right)\left(Y^{\prime}-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\left(Y-h\left(A,W,X\right)\right)\left(Y^{\prime}-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)\right.\right.$
$\displaystyle\hskip
120.00018pt\times\left.\left.k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\middle|\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Y-h\left(A,W,X\right)\middle|A,X,Z\right]\right.$
$\displaystyle\hskip
120.00018pt\times\left.\mathbb{E}\left[Y^{\prime}-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\middle|A^{\prime},X^{\prime},Z^{\prime}\right]\right.$
$\displaystyle\hskip
120.00018pt\times\left.k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[h^{*}\left(A,W,X\right)-h\left(A,W,X\right)\middle|A,X,Z\right]\right.$
$\displaystyle\hskip
120.00018pt\times\left.\mathbb{E}\left[h^{*}\left(A^{\prime},W^{\prime},X^{\prime}\right)-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\middle|A^{\prime},X^{\prime},Z^{\prime}\right]\right.$
$\displaystyle\hskip
120.00018pt\times\left.k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\left(h^{*}\left(A,W,X\right)-h\left(A,W,X\right)\right)\left(h^{*}\left(A^{\prime},W^{\prime},X^{\prime}\right)-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)\right.\right.$
$\displaystyle\hskip
120.00018pt\times\left.\left.k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\middle|\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right]\right]$
$\displaystyle=\mathbb{E}\left[\left(h^{*}\left(A,W,X\right)-h\left(A,W,X\right)\right)\left(h^{*}\left(A^{\prime},W^{\prime},X^{\prime}\right)-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)\right.$
$\displaystyle\hskip
120.00018pt\times\left.k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$
$\displaystyle=d_{k}^{2}\left(h^{*},h\right)$

Thus,

$\displaystyle d_{k}^{2}\left(h^{*},\hat{h}_{k,U,\lambda,n}\right)$
$\displaystyle=R_{k}\left(\hat{h}_{k,U,\lambda,n}\right)$ $\displaystyle\leq
R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$ $\displaystyle\leq
d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\qquad+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

If the right hand side of this expression goes to zero as $n$ goes to
infinity, then, for any $\delta,\epsilon>0$, we can find $n$ such that the
right hand side is less than $\epsilon$. Further, since we can do this for any
value of $\delta$, we can choose a sequence of $\delta_{n}$s decreasing in
$n$, so that $\lim_{n\to\infty}\delta_{n}=0$, so that the left hand side
converges in probability. If $k$ is ISPD, by Lemma 6, $d_{k}$ is a metric on
$L^{2}_{\mathcal{AXZ}}$. Thus,
$d_{k}\left(h^{*},\hat{h}_{k,U,\lambda,n}\right)\xrightarrow{\mathrm{P}}0$, so
$\mathbb{E}\left[\hat{h}_{k,U,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$,
in $d_{k}$. Further, the fact that $k$ is Integrally Strictly Positive
Definite, implies that
$\left\|\mathbb{E}\left[h^{*}\middle|A,X,Z\right]-\mathbb{E}\left[\hat{h}_{k,U,\lambda,n}\middle|A,X,Z\right]\right\|_{\mathrm{P}_{A,X,Z}}\xrightarrow{\mathrm{P}}0$,
so that
$\mathbb{E}\left[\hat{h}_{k,U,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$,
in $L^{2}\left(\mathrm{P}_{\mathcal{AXZ}}\right)$-norm, as well.

∎

######  Lemma 7.

Let $f:\mathcal{X}^{2}\to[-M,M]$,
$\forall_{x\in\mathcal{X}}f\left(x,x\right)\geq 0$,
$\hat{U}_{n}[f]=\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}^{n}f\left(x_{i},x_{j}\right)$, and
$\hat{V}_{n}[f]=n^{-2}\sum_{i,j=1}^{n}f\left(x_{i},x_{j}\right)$. Then,
$(n-1)\hat{U}_{n}[f]\leq n\hat{V}_{n}[f]\leq(n-1)\hat{U}_{n}[f]+M$.

###### Proof.

$\displaystyle(n-1)\hat{U}_{n}[f]$ $\displaystyle=n^{-1}\sum_{i,j=1,j\neq
i}^{n}f\left(x_{i},x_{j}\right)\leq
n^{-1}\sum_{i,j=1}^{n}f\left(x_{i},x_{j}\right)$
$\displaystyle=n\hat{V}_{n}[f]=n^{-1}\left(\sum_{i,j=1,j\neq
i}^{n}f\left(x_{i},x_{j}\right)+\sum_{i,j=1,j=i}^{n}f\left(x_{i},x_{j}\right)\right)$
$\displaystyle\leq
n^{-1}n(n-1)\hat{U}_{n}[f]+n^{-1}\sum_{i=1}^{n}f\left(x_{i},x_{i}\right)\leq(n-1)\hat{U}_{n}[f]+M$

so

$\displaystyle(n-1)\hat{U}_{n}[f]\leq
n\hat{V}_{n}[f]\leq(n-1)\hat{U}_{n}[f]+M$

∎

######  Corollary 8.

Let $\tilde{h}_{k}$ minimize $R_{k}(h)$ and $\hat{h}_{k,V,\lambda,n}$ minimize
$\hat{R}_{k,V,\lambda,n}(h)$ for $h\in\mathcal{H}$ and let
$h^{*}:\mathcal{A}\times\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ satisfy
$\mathbb{E}\left[Y-h^{*}(A,W,X)\middle|A,X,Z\right]=0$
$\mathrm{P}_{A,X,Z}$-almost surely, where

$\displaystyle R_{k}(h)$
$\displaystyle=\mathbb{E}\left[\left(Y-h\left(A,W,X\right)\right)\left(Y^{\prime}-h\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$
$\displaystyle\hat{R}_{k,V,\lambda,n}(h)$
$\displaystyle=n^{-2}\sum_{i,j=1}^{n}\left(y_{i}-h\left(a_{i},w_{i},x_{i}\right)\right)\left(y_{j}-h\left(a_{j},w_{j},x_{j}\right)\right)k\left(\left(a_{i},x_{i},z_{i}\right),\left(a_{j},x_{j},z_{j}\right)\right)$
$\displaystyle\qquad+\lambda\Lambda[f,\theta_{f}]$

Also let,

$\displaystyle d_{k}^{2}\left(h,h^{\prime}\right)$
$\displaystyle=\mathbb{E}\left[\left(h\left(A,W,X\right)-h^{\prime}\left(A,W,X\right)\right)\left(h\left(A^{\prime},W^{\prime},X^{\prime}\right)-h^{\prime}\left(A^{\prime},W^{\prime},X^{\prime}\right)\right)\right.$
$\displaystyle\hskip 40.00006pt\left.\times
k\left(\left(A,X,Z\right),\left(A^{\prime},X^{\prime},Z^{\prime}\right)\right)\right]$

Then, $d_{k}^{2}\left(h^{*},h\right)=R_{k}(h)$ and, with probability at least
$1-\delta$,

$\displaystyle d_{k}^{2}\left(h^{*},\hat{h}_{k,V,\lambda,n}\right)$
$\displaystyle\leq d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\mathbb{E}_{A,X,Z}\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}_{A,X,Z}\right)\right)$
$\displaystyle\qquad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}+\left(4M^{2}M_{k}+\lambda
M_{\lambda}\right)(n-1)^{-1}$ $\displaystyle\qquad+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$ $\displaystyle\leq
d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\qquad+\left(4M^{2}M_{k}+\lambda
M_{\lambda}\right)(n-1)^{-1}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

Further, if Assumption 5 holds, so $k$ is ISPD, then $d_{k}$ is a metric on
$L^{2}_{\mathcal{AXZ}}$ and, if the right hand side of the inequality goes to
zero as $n$ goes to infinity,
$d_{k}\left(\mathbb{E}\left[h^{*}\middle|A,X,Z\right]-\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\right)\xrightarrow{\mathrm{P}}0$
so
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$
in $d_{k}$. Also,
$\left\|\mathbb{E}\left[h^{*}\middle|A,X,Z\right]-\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\right\|_{\mathrm{P}_{A,X,Z}}\xrightarrow{\mathrm{P}}0$
so
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$
in $L^{2}\left(\mathrm{P}_{\mathcal{A,X,Z}}\right)$-norm.

$\displaystyle\mathcal{F}^{\prime}_{a,x,z}=\left\\{f_{a,x,z}\ \middle|\
\exists_{h\in\mathcal{H}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f_{a,x,z}\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$
$\displaystyle\mathcal{F}^{\prime}=\left\\{f\ \middle|\
\exists_{h\in\mathcal{H},a\in\mathcal{A},x\in\mathcal{X},z\in\mathcal{Z}}\forall_{a^{\prime}\in\mathcal{A},x^{\prime}\in\mathcal{X},z^{\prime}\in\mathcal{Z}}f\left(a^{\prime},w^{\prime},x^{\prime},z^{\prime}\right)=h\left(a^{\prime},w^{\prime},x^{\prime}\right)k\left(\left(a^{\prime},x^{\prime},z^{\prime}\right),\left(a,x,z\right)\right)\right\\}$

###### Proof.

Defining $f$ and $\Xi$ as in Theorem 1, then
$\hat{R}_{k,U,n}(h)=\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}^{n}f_{h}\left(\xi_{i},\xi_{j}\right)$,
$\hat{R}_{k,U,\lambda,n}(h)=\frac{1}{n(n-1)}\sum_{i,j=1,j\neq
i}^{n}f_{h}\left(\xi_{i},\xi_{j}\right)+\lambda\Lambda[f,\theta_{f}]$,
$\hat{R}_{k,V,n}(h)=n^{-2}\sum_{i,j=1}^{n}f_{h}\left(\xi_{i},\xi_{j}\right)$,
$\hat{R}_{k,V,\lambda,n}(h)=n^{-2}\sum_{i,j=1}^{n}f_{h}\left(\xi_{i},\xi_{j}\right)+\lambda\Lambda[f,\theta_{f}]$,
Noting that $|f|\leq 4M^{2}M_{k}$ and applying Lemma 7 to
$\hat{R}_{k,U,\lambda,n}$ and $\hat{R}_{k,V,\lambda,n}$ yields,

$\displaystyle\hat{R}_{k,\lambda,n}(h)$
$\displaystyle=\hat{R}_{k,U,n}(h)+\lambda\Lambda[f,\theta_{f}]\leq\frac{n}{n-1}\hat{R}_{k,V,n}(h)+\lambda\Lambda[f,\theta_{f}]$
$\displaystyle\leq\frac{n}{n-1}\hat{R}_{k,V,n}(h)+\frac{n}{n-1}\lambda\Lambda[f,\theta_{f}]=\frac{n}{n-1}\hat{R}_{k,V,\lambda,n}(h)$
$\displaystyle\leq\hat{R}_{k,U,n}(h)+(n-1)^{-1}4M^{2}M_{k}+\frac{n}{n-1}\lambda\Lambda[f,\theta_{f}]$

From the proof of Theorem 1, with probability at least $1-\frac{\delta}{2}$,
we have,

$\displaystyle R_{k}(h)$
$\displaystyle\leq\hat{R}_{k,\lambda,n}(h)+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\hat{R}_{k,\lambda,n}(h)$ $\displaystyle\leq R_{k}(h)+\lambda
M^{2}+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$

Recalling that $\hat{h}_{k,V,\lambda,n}$ minimizes
$\hat{R}_{k,V,\lambda,n}(h)$ and $\tilde{h}_{k}$ minimizes $R_{k}(h)$ over
$\mathcal{H}$, so that
$\hat{R}_{k,V,\lambda,n}\left(\hat{h}_{k,V,\lambda,n}\right)\leq\hat{R}_{k,V,\lambda,n}\left(\tilde{h}_{k}\right)$
and combining the above expressions gives,

$\displaystyle R_{k}$
$\displaystyle\left(\hat{h}_{k,V,\lambda,n}\right)\leq\hat{R}_{k,U,\lambda,n}\left(\hat{h}_{k,V,\lambda,n}\right)+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq\frac{n}{n-1}\hat{R}_{k,V,\lambda,n}\left(\hat{h}_{k,V,\lambda,n}\right)+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq\frac{n}{n-1}\hat{R}_{k,V,\lambda,n}\left(\tilde{h}_{k}\right)+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq\hat{R}_{k,n}\left(\tilde{h}_{k}\right)+(n-1)^{-1}4M^{2}M_{k}+\frac{n}{n-1}\lambda\Lambda[f,\theta_{f}]+2\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)$
$\displaystyle\quad+8M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq
R_{k}\left(\tilde{h}_{k}\right)+(n-1)^{-1}4M^{2}M_{k}+\frac{n}{n-1}\lambda
M_{\lambda}+4\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)$
$\displaystyle\quad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\leq R_{k}\left(\tilde{h}_{k}\right)+\left(4M^{2}M_{k}+\lambda
M_{\lambda}\right)(n-1)^{-1}+\lambda
M_{\lambda}+4\mathbb{E}_{\Xi}\left(\mathcal{R}_{n-1}\left(\mathcal{F}_{1,\Xi}\right)+\mathcal{R}_{n}\left(\mathcal{F}_{2,\Xi}\right)\right)$
$\displaystyle\quad+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$

Using Lemma 5 and results from the proof of Theorem 1,

$\displaystyle R_{k}\left(\hat{h}_{k,V,\lambda,n}\right)$ $\displaystyle\leq
R_{k}\left(\tilde{h}_{k}\right)+\left(4M^{2}M_{k}+\lambda
M_{\lambda}\right)(n-1)^{-1}+\lambda M_{\lambda}$
$\displaystyle\qquad+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\qquad+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$
$\displaystyle=R_{k}\left(\tilde{h}_{k}\right)+\lambda
M_{\lambda}+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\qquad+\left(4M^{2}M_{k}+\lambda
M_{\lambda}\right)(n-1)^{-1}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

Recalling that $d_{k}^{2}\left(h^{*},h\right)=R_{k}(h)$, we have,

$\displaystyle d_{k}^{2}\left(h^{*},\hat{h}_{k,V,\lambda,n}\right)$
$\displaystyle\leq d_{k}^{2}\left(h^{*},\tilde{h}_{k}\right)+\lambda
M^{2}+8M\left(\mathcal{R}_{n-1}\left(\mathcal{F}^{\prime}\right)+\mathcal{R}_{n}\left(\mathcal{F}^{\prime}\right)\right)+16M^{2}M_{k}\left(\frac{2}{n}\log\frac{2}{\delta}\right)^{\frac{1}{2}}$
$\displaystyle\qquad+\left(4M^{2}M_{k}+\lambda
M_{\lambda}\right)(n-1)^{-1}+10\left(2\log
2\right)^{\frac{1}{2}}M^{2}M_{k}n^{-\frac{1}{2}}$

∎

######  Theorem 2.

Under Assumption 4, $h^{*}$ is the unique solution $\mathrm{P}_{A,W,X}$-almost
surely. Further, if
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$,
$\hat{h}_{k,\lambda,n}\xrightarrow{\mathrm{P}}h^{*}$.

###### Proof.

Let $h^{*},h^{*\prime}$ both be zeros of
$\mathbb{E}\left[Y-h\left(A,W,X\right)\middle|A,X,Z\right]$,
$\mathrm{P}_{A,X,Z}$-almost surely, then

$\displaystyle\mathbb{E}$
$\displaystyle\left[\left(h^{*}-h^{*\prime}\right)\left(A,W,X\right)\middle|A,X,Z\right]=\mathbb{E}\left[\left(h^{*}-Y+Y-h^{*\prime}\right)\left(A,W,X\right)\middle|A,X,Z\right]$
$\displaystyle=\mathbb{E}\left[Y-h^{*\prime}\left(A,W,X\right)\middle|A,X,Z\right]-\mathbb{E}\left[Y-h^{*}\left(A,W,X\right)\middle|A,X,Z\right]=0-0$
$\displaystyle=0$

$\mathrm{P}_{A,X,Z}$-almost surely, so $h^{*}=h^{*\prime}$
$\mathrm{P}_{A,W,X}$-almost surely.

If
$\mathbb{E}\left[\hat{h}_{k,\lambda,n}\middle|A,X,Z\right]\xrightarrow{\mathrm{P}}\mathbb{E}\left[h^{*}\middle|A,X,Z\right]$,
$\left\|\mathbb{E}\left[\left(\hat{h}_{n}-h^{*}\right)\left(A,W,X\right)\middle|A,X,Z\right]\right\|_{\mathrm{P}_{A,X,Z}}\xrightarrow{\mathrm{P}}0$,
meaning that the convergence occurs $\mathrm{P}_{A,X,Z}$-almost surely, so, by
assumption,
$\left\|\hat{h}_{n}-h^{*}\right\|_{\mathrm{P}_{A,W,X}}\xrightarrow{\mathrm{P}}0$,
so $\hat{h}_{n}\xrightarrow{\mathrm{P}}h^{*}$.

∎

##  Appendix B Hyperparameter Tuning & Model Architecture

We tuned the architectures of the Naive Net and NMMR models on both the Demand
and dSprite experiments. The Naive Net used MSE loss to estimate $Y^{a}$,
while NMMR relied on either the U-statistic or V-statistic.

Within each experiment, the Naive Net and NMMR models used similar
architectures. In the Demand experiment, both models consisted of 2-5
(“Network depth” in Table S1) fully connected layers with a variable number
(“Network width”) of hidden units.

In the dSprite experiment, each model had two VGG-like heads [28] that took in
$A$ and $W$ images and applied two blocks of {Conv2D, Conv2D, MaxPool2D} with
3 by 3 kernels. Each Conv2D layer had 64 filters in the first block, then 128
filters in the second block. The output of the second block was flattened,
then projected to 256 dimensions. Two subsequent fully connected layers were
used, with their number of units determined by the “layer width decay” factor
in Table S1. For example, if this factor was 0.5, then the two layers would
have 128 and 64 units, respectively.

We performed a grid search over the following parameters:

Table S1: Grid of hyperparameters for our naive neural network and NMMR
models.

Hyperparameter | Demand | dSprite
---|---|---
Learning rate | {3e-3, 3e-4, 3e-5} | {3e-4, 3e-5, 3e-6}
L2 penalty | {3e-5, 3e-6, 3e-7} | {3e-6, 3e-7}
# of epochs | 3000 | 500
Batch size | 1000 | 256
Layer width decay |  | {0.25, 0.5}
Network width | {10, 40, 80} |
Network depth | {2, 3, 4, 5} |

We selected the final hyperparameters by considering the lowest average
U-statistic or V-statistic on held-out validation sets for NMMR or the MSE for
the Naive Net. For the Demand experiment, we repeated this process 10 times
with different random seeds and averaged the statistics. For the dSprite
experiment, we had 3 repetitions.

Full hyperparameter choices for all methods used in this work are available in
our code. The hyperparameters selected for NMMR were tuned for each dataset:

Table S2: Optimal hyperparameters for NMMR methods

Hyperparameter | NMMR-U Demand | NMMR-U dSprite | NMMR-V Demand | NMMR-V dSprite
---|---|---|---|---
Learning rate | 3e-3 | 3e-5 | 3e-3 | 3e-5
L2 penalty | 3e-6 | 3e-6 | 3e-6 | 3e-7
# of epochs | 3,000 | 500 | 3,000 | 500
Batch size | 1,000 | 256 | 1,000 | 256
Layer width decay | — | 0.25 | — | 0.5
Network width | 80 | — | 80 | —
Network depth | 4 | — | 3 | —

The hyperparameters for Naive Net for each dataset were:

Table S3: Optimal hyperparameters for Naive Net model

Hyperparameter | Naive Net Demand | Naive Net dSprite
---|---|---
Learning rate | 3e-3 | 3e-5
L2 penalty | 3e-6 | 3e-6
# of epochs | 3,000 | 500
Batch size | 1,000 | 256
Layer width decay | — | 0.25
Network width | 80 | —
Network depth | 2 | —

Another hyperparameter of note is the choice of kernel in the loss function of
NMMR. Throughout, we relied on the RBF kernel:

$k(x_{i},x_{j})=e^{\frac{-||x_{i}-x_{j}||_{2}^{2}}{2\sigma^{2}}}$

with $\sigma=1$. For future work, we could consider other choices of the
kernel or tune the length scale parameter $\sigma$. In the dSprite experiment,
the kernel function is applied to pairs of $Z$ and $A$ data. Since $A$ is an
$64\times 64$ image, we chose to concatenate $(z_{i},0.05a_{i})$ as input to
the kernel for the $i$-th data point. One could also consider tuning this
multiplicative factor, but in practice we found that it allowed for both $Z$
and $A$ to impact the result of the kernel function.

##  Appendix C Experiment Details

###  C.1 Demand Data Generating Process

The Demand experiment has the following structural equations:

  * •

Demand: $U\sim\mathcal{U}(0,10)$

  * •

Fuel cost: $[Z_{1},Z_{2}]=[2\sin(2\pi U/10)+\epsilon_{1},2\cos(2\pi
U/10)+\epsilon_{2}]$

  * •

Web page views: $W=7g(U)+45+\epsilon_{3}$

  * •

Price: $A=35+(Z_{1}+3)g(U)+Z_{2}+\epsilon_{4}$

  * •

Sales: $Y=A\times\min(\exp(\frac{W-A}{10}),5)-5g(U)+\epsilon_{5}$

  * •

where
$g(u)=2\left(\frac{(u-5)^{4}}{600}+e^{-4(u-5)^{2}}+\frac{u}{10}-2\right)$, and
$\epsilon_{i}\sim\mathcal{N}(0,1)$

###  C.2 Demand causal DAG

$A$: Price$Z$: Cost$U$: Demand$Y$: Sales$W$: Views Figure S1: Causal DAG for
the Demand experiment.

###  C.3 Demand Exploratory Data Analysis

In Figure S2, Panels A and B show that $W$ is a more informative proxy for $U$
than $Z$, although neither relationship is one-to-one. Panel C shows that the
true potential outcome curve, denoted by the black curve $a\mapsto E[Y^{a}]$,
deviates from the observed $(A,Y)$ distribution due to confounding. In
particular, the largest deviation occurs at smaller values of $A$. The goal of
each method is to recover this average potential outcome curve given data on
$A,Z,W,$ and $Y$.

Figure S2: Views of the $A,Z,W,Y,U$ relationships. (A) $Z_{1}$ (red) and
$Z_{2}$ (orange) have sinusoidal relationships with $U$, (B) $W$ has a far
less noisy relationship with $U$, and (C) the observed distribution $(A,Y)$
(blue) deviates from the true average potential outcome curve (black).

###  C.4 Demand Boxplot Statistics

Table S4 contains the median and interquartile ranges (in parentheses) of the
c-MSE values compiled in the boxplots shown in Figure 2. NMMR demonstrated
state of the art performance on the Demand benchmark. We also extended the
benchmark to include training set sizes of 10,000 and 50,000 data points,
whereas Xu et al. [7] originally included 1,000 and 5,000 data points. We
observed that NMMR-U had strong performance across all dataset sizes. PMMR and
KPV were unable to run on 50,000 training points due to computational limits
on their kernel methods, while DFPV exhibited a large increase in c-MSE as
training set size increased.

Table S4: Demand Boxplot Median & (IQR) values

| Training Set Size
---|---
Method | 1,000 | 5,000 | 10,000 | 50,000
PMMR | 587.51 (40.35) | 466.5 (33.47) | 423.1 (29.26) | —
KPV | 469.94 (97.07) | 481.32 (54.8) | 470.62 (29.3) | —
Naive Net | 160.35 (33.78) | 186.97 (30.22) | 204.36 (113.71)) | 224.09 (33.17)
CEVAE | 180.8 (161.26) | 214.98 (120.88) | 170.58 (176.1) | 171.98 (293.27)
2SLS | 82.08 (18.82) | 83.16 (4.51) | 82.1 (5.55) | 82.01 (2.22)
DFPV | 41.83 (11.78) | 48.22 (7.73) | 87.14 (471.59) | 242.15 (464.38)
LS | 63.19 (5.82) | 65.14 (2.64) | 64.98 (2.44) | 64.65 (0.74)
NMMR-U (ours) | 23.68 (8.02) | 16.21 (10.55) | 14.25 (4.46) | 14.27 (12.47)
NMMR-V (ours) | 23.41 (11.26) | 30.74 (17.73) | 42.88 (29.45) | 62.18 (16.97)

###  C.5 Demand Prediction Curves

Figures S3-S6 provide the individual predicted potential outcome curves of
each method in the Demand experiment. While Figure 2 provides a summary of the
c-MSE, this does not give a picture of the model’s actual estimate of
$\mathbb{E}[Y^{a}]$. These figures give an insight into ranges of $A$ for
which each model provides particularly accurate or inaccurate estimates of the
potential outcomes. Across all training set sizes, methods are most accurate
in the region where the training observations of $Y$ are closest to the ground
truth (see Figure S2).

Figure S3: Demand experiment with 1,000 training data points with the true
average potential outcome curves (black) and each method’s predicted potential
outcome curves (blue). Each method was replicated 20 times, generating one
predicted curve per replicate. Note that with only a limited amount of data,
most methods only recover the true curve in the later half of the range of
$A$. See Figure S2. Figure S4: Demand experiment with 5,000 training data