# Debiased Kernel Methods

Rahul Singh
MIT Economics
<EMAIL_ADDRESS>
###### Abstract

I propose a practical procedure based on bias correction and sample splitting
to calculate confidence intervals for functionals of generic kernel methods,
i.e. nonparametric estimators learned in a reproducing kernel Hilbert space
(RKHS). For example, an analyst may desire confidence intervals for
functionals of kernel ridge regression or kernel instrumental variable
regression. The framework encompasses (i) evaluations over discrete domains,
(ii) treatment effects of discrete treatments, and (iii) incremental treatment
effects of continuous treatments. For the target quantity, whether it is
(i)-(iii), I prove pointwise $\sqrt{n}$ consistency, Gaussian approximation,
and semiparametric efficiency by finite sample arguments. I show that the
classic assumptions of RKHS learning theory also imply inference.

##  1 Introduction

The reproducing kernel Hilbert space (RKHS) is a popular nonparametric setting
in machine learning. For example, kernel ridge regression is a classic
algorithm for prediction, with impressive attributes. Computationally, it has
a closed form solution; empirically, it adapts well to local nonlinearity
while preserving smoothness; statistically, it is minimax optimal with respect
to mean square error [15]. However, practical confidence intervals for
functionals of this classic procedure–under general and weak conditions–have
remained elusive.

A recent literature proposes kernel methods for causal learning problems, such
as nonparametric instrumental variable regression [81] and nonparametric
treatment effects [83, 80], that share the impressive attributes of kernel
ridge regression. The motivation for these causal kernel methods is policy
evaluation in social science and epidemiology. In social science and
epidemiology, however, confidence intervals are essential. By providing
confidence intervals, this paper disembarrasses a broad class of machine
learning algorithms for practical use.

I provide conceptual, algorithmic, and statistical contributions to RKHS
theory.

Conceptual. The generality of the framework is threefold. First, I unify (i)
evaluations over discrete domains, (ii) treatment effects of discrete
treatments, and (iii) incremental treatment effects of continuous treatments
into one general inference problem. Second, I allow for any nonparametric
kernel method with a known learning rate. Third, I allow for the covariates to
be discrete or continuous, and low, high, or infinite dimensional. As such,
the main results apply to kernel methods trained on texts, graphs, or images.

Algorithmic. I provide a general purpose procedure to automatically debias
(i)-(iii) for pointwise inference. The debiasing is novel, and I show that is
has a one line, closed form solution. Its only hyperparameters are kernel
hyperparameters and ridge regression penalties, just like kernel ridge
regression. The former have well known heuristics, and the latter are easily
tuned by cross validation.

Statistical. For the target quantity, whether it is (i)-(iii), I prove
pointwise $\sqrt{n}$ consistency, Gaussian approximation, and semiparametric
efficiency by finite sample arguments. The analysis explicitly accounts for
each source of error in any finite sample size. Formally, I show that the
classic assumptions of RKHS learning theory also imply inference.

The structure of the paper is as follows. Section 1.1 describes related work.
Section 2 articulates the general inference problem. Section 3 proposes the
general purpose debiasing procedure and furnishes confidence intervals.
Sections 4 and 5 present the main theoretical contributions. Section 6
concludes.

###  1.1 Related work

Functionals. By focusing on functionals, i.e. scalar summaries, of
nonparametric quantities, this paper continues the tradition of classic
semiparametric statistical theory [50, 32, 35, 65, 48, 71, 97, 12, 56, 69, 98,
13, 57, 1, 58, 2, 92, 49, 3]. Whereas classic semiparametric theory studies
functionals of densities or regressions over low dimensional domains, I study
functionals of generic kernel methods over domains that may include discrete
treatments and low, high, or infinite dimensional covariates. In classic
semiparametric theory, an object called the Riesz representer of the
functional appears in asymptotic variance calculations [56, 36]. For exactly
the same reasons, it appears in the practical procedure for confidence
intervals that I propose.

Debiasing. In asymptotic inference, the Riesz representer is inevitable.
Motivated by this insight, a growing literature directly incorporates the
Riesz representer into estimation, which amounts to debiasing known estimators
[32, 13, 99, 7, 8, 9, 10, 41, 42, 43, 93, 64, 23, 60, 66, 38, 39, 40, 14, 101,
102]. Doubly robust estimating equations serve this purpose [70, 69, 96, 95,
51, 91]. A geometric perspective on debiasing emphasizes Neyman orthogonality:
by debiasing, the learning problem for the functional of interest becomes
orthogonal to the learning problem for the underlying nonparametric object
[61, 62, 98, 67, 100, 9, 10, 22, 6, 21, 30]. In this work, I debias kernel
methods using doubly robust estimating equations. The learning problem for
(i)-(iii) becomes orthogonal to the learning problem for the underlying kernel
method.

Sample splitting. With debiasing alone, a key challenge remains: for
inference, the function class in which the nonparametric quantity is learned
must be Donsker. However, popular nonparametric settings in machine learning
such as the RKHS are not Donsker. A solution to this challenging issue is to
combine debiasing with sample splitting [11, 77, 48, 98, 67]. The debiased
machine learning (DML) and targeted maximum likelihood literatures are
responsible for this insight [76, 74, 75, 96, 100, 95, 28, 94, 22, 46, 21,
45]. In particular, DML delivers simple sufficient conditions for inference on
functionals in terms of learning rates of the underlying regression and the
Riesz representer [22, 21]. The analysis of Section 4 is written at this level
of generality. Whereas the existing DML theory is asymptotic, I provide the
first finite sample analysis of DML with black box machine learning.

Automatic debiasing. Since standard statistical learning theory provides rates
for nonparametric regression, what remains is estimation and analysis that
provides sufficiently fast rates for the Riesz representer. However, the Riesz
representer may be a complex object. Even for simple functionals such as
policy effects, its closed form involves ratios of densities, which would
imply slow rates. A crucial insight is that the Riesz representer is directly
identified from data; with some creativity, it can be estimated and analyzed
directly, without estimating or analyzing its components [68, 59, 4, 24, 26,
33, 34, 82, 73, 25]. For the RKHS context, I propose a novel estimator of the
Riesz representer that generalizes kernel ridge regression. I derive its fast
rate in Section 5.

Kernel methods. Recent developments in the kernel methods literature motivate
this project. In particular, a new toolkit addresses causal learning problems
such as instrumental variable regression [81, 55, 29], treatment effects under
selection on observables [63, 54, 83], and treatment effects with negative
controls [80]. Confidence intervals are essential for practical use in policy
evaluation, yet they have remained elusive until now. As explained above, a
key contribution is fast rate analysis for a new Riesz representer estimator.
My analysis directly builds on the seminal work of [15], which provides
minimax optimal rates for kernel ridge regression. As such, classic learning
theory assumptions imply the learning rate for the Riesz representer and hence
inference for the functional.

##  2 Framework

###  2.1 General inference problem

The general inference problem is to find a confidence interval for
$\theta_{0}\in\mathbb{R}$ where

$\theta_{0}=\mathbb{E}[m(W,\gamma_{0})],\quad\gamma_{0}\in\mathcal{H}$

$m:\mathcal{W}\times\mathcal{H}\rightarrow{\mathbb{R}}$ is an abstract
formula. $W\in\mathcal{W}$ is a concatenation of random variables in the model
excluding the outcome $Y\in\mathcal{Y}\subset\mathbb{R}$. $\mathcal{H}$ is an
RKHS, consisting of functions of the form
$\gamma:\mathcal{W}\rightarrow\mathbb{R}$. I denote its kernel by
$k:\mathcal{W}\times\mathcal{W}\rightarrow\mathbb{R}$, and its feature map
$\phi:\mathcal{W}\rightarrow\mathcal{H}$, $w\mapsto k(w,\cdot)$.

The first set of examples are functionals of kernel ridge regresssion. These
statistical quantities have causal interpretation under the assumption of
unconfoundedness, also called selection on observables. The simplest example
is evaluation over a discrete domain.

######  Example 2.1 (Evaluation of nonparametric regression).

$W$ are covariates, and $\gamma_{0}(w)=\mathbb{E}[Y|W=w]$. Then evaluation at
location $w$ is $\theta_{0}=\gamma_{0}(w)$. I require that $W$ are discrete.

Next, I turn to classic treatment effects in causal inference: average
treatment effect (ATE), average treatment effect with distribution shift (ATE-
DS), average treatment on the treated (ATT), and conditional average treatment
effect (CATE). I generalize each of these classic effects to have discrete
treatment values rather than binary treatment values. The expressions follow
from [72, 20, 37].

######  Example 2.2 (Treatment effects of discrete treatments under selection
on observables).

$W=(D,X)$ are treatment and covariates, and
$\gamma_{0}(d,x)=\mathbb{E}[Y|D=d,X=x]$. For heterogeneous effects, I replace
$X$ with $(V,X)$ where $V$ is the low dimensional subcovariate of interest. I
require that $(D,V)$ are discrete.

  1. 1.

ATE. The mean potential outcome of treatment value $d$ is given by
$\theta_{0}=\mathbb{E}[\gamma_{0}(d,X)]$.

  2. 2.

ATE-DS. The mean potential outcome of treatment value $d$ under distribution
shift is given by $\theta_{0}=\tilde{\mathbb{E}}[\gamma_{0}(d,X)]$, where
$\tilde{\mathbb{E}}$ is the expectation over an alternative population.

  3. 3.

ATT. The mean potential outcome of treatment value $d^{\prime}$ for the
subpopulation who received treatment value $d$ is given by
$\beta_{0}=\frac{\theta_{0}}{\mathbb{P}(d)}$ where
$\theta_{0}=\mathbb{E}[\gamma_{0}(d^{\prime},X)\mathbbm{1}_{D=d}]$.

  4. 4.

CATE. The mean potential outcome of treatment value $d$ for the subpopulation
with subcovariate value $v$ is given by
$\beta_{0}=\frac{\theta_{0}}{\mathbb{P}(v)}$ where
$\theta_{0}=\mathbb{E}[\gamma_{0}(d,v,X)\mathbbm{1}_{V=v}]$.

In a couple instances, the quantity of interest is $\beta_{0}\in\mathbb{R}$,
which is a ratio of $\theta_{0}\in\mathbb{R}$ and a marginal probability. By
standard arguments, inference for $\theta_{0}$ implies inference for
$\beta_{0}$ by delta method. In the examples so far, I have restricted
treatment to be discrete. I now allow treatment to be continuous. The
expression follows from [37, 73].

######  Example 2.3 (Incremental treatment effects of continuous treatments
under selection on observables).

$W=(D,X)$ are treatment and covariates, and
$\gamma_{0}(d,x)=\mathbb{E}[Y|D=d,X=x]$. I now allow $D$ to be continuous. The
incremental treatment effect weighted by the density $\omega$ over treatment
values is $\theta_{0}=\mathbb{E}[S(U)\gamma_{0}(U,X)]$ where
$S(u)=-\frac{\omega^{\prime}(u)}{\omega(u)}$ and $U$ is drawn from $\omega$
independently of $X$.

The examples listed so far are statistical quantities that coincide with
causal quantities under the assumption of no unobserved confounding. Often, in
observational data, unobserved confounding drives spurious correlations. The
next set of examples are statistical quantities that coincide with causal
quantities despite unobserved confounding. They are functionals of kernel
instrumental variable regression. In instrumental variable regression, the
analyst has access to auxiliary variables called instruments. Again, I begin
with evaluation.

######  Example 2.4 (Evaluation of nonparametric instrumental variable
regression).

$W=(X,Z)$ are covariates and instruments. $\gamma_{0}(x)$ is the solution to
$\mathbb{E}[Y|Z=z]=\mathbb{E}[\gamma_{0}(X)|Z=z]$. Then evaluation at location
$x$ is $\theta_{0}=\gamma_{0}(x)$. I require that $X$ are discrete.

Next, I revisit the classic treatment effects in causal inference. This time,
I relax the assumption of no unobserved confounding. In its place, I assume
access to two auxiliary variables called negative controls, which leads to new
statistical quantities. The expressions follow from [52, 53, 90].

######  Example 2.5 (Treatment effects of discrete treatments under negative
controls).

$W=(D,X,\tilde{W})$ are treatment, covariates, and negative control outcome.
$Z$ is the negative control treatment. $\gamma_{0}(d,x,\tilde{w})$ is the
solution to
$\mathbb{E}[Y|D=d,X=x,Z=z]=\mathbb{E}[\gamma_{0}(D,X,\tilde{W})|D=d,X=x,Z=z]$.
For heterogeneous effects, I replace $X$ with $(V,X)$ where $V$ is the low
dimensional subcovariate of interest. I require that $(D,V)$ are discrete.

  1. 1.

ATE. The mean potential outcome of treatment value $d$ is given by
$\theta_{0}=\mathbb{E}[\gamma_{0}(d,X,\tilde{W})]$.

  2. 2.

ATE-DS. The mean potential outcome of treatment value $d$ under distribution
shift is given by $\theta_{0}=\tilde{\mathbb{E}}[\gamma_{0}(d,X,\tilde{W})]$,
where $\tilde{\mathbb{E}}$ is the expectation over an alternative population.

  3. 3.

ATT. The mean potential outcome of treatment value $d^{\prime}$ for the
subpopulation who received treatment value $d$ is given by
$\beta_{0}=\frac{\theta_{0}}{\mathbb{P}(d)}$ where
$\theta_{0}=\mathbb{E}[\gamma_{0}(d^{\prime},X,\tilde{W})\mathbbm{1}_{D=d}]$.

  4. 4.

CATE. The mean potential outcome of treatment value $d$ for the subpopulation
with subcovariate value $v$ is given by
$\beta_{0}=\frac{\theta_{0}}{\mathbb{P}(v)}$ where
$\theta_{0}=\mathbb{E}[\gamma_{0}(d,v,X,\tilde{W})\mathbbm{1}_{V=v}]$.

As before, delta method transforms inference about $\theta_{0}\in\mathbb{R}$
into inference about $\beta_{0}\in\mathbb{R}$. Finally, I allow treatment to
be continuous in the negative control setting. The expression generalizes [37,
73].

######  Example 2.6 (Incremental treatment effects of continuous treatments
under negative controls).

$W=(D,X,\tilde{W})$ are treatment, covariates, and negative control outcome.
$Z$ is the negative control treatment. $\gamma_{0}(d,x,\tilde{w})$ is the
solution to
$\mathbb{E}[Y|D=d,X=x,Z=z]=\mathbb{E}[\gamma_{0}(D,X,\tilde{W})|D=d,X=x,Z=z]$.
I now allow $D$ to be continuous. The incremental treatment effect weighted by
the density $\omega$ over treatment values is
$\theta_{0}=\mathbb{E}[S(U)\gamma_{0}(U,X,\tilde{W})]$ where
$S(u)=-\frac{\omega^{\prime}(u)}{\omega(u)}$ and $U$ is drawn from $\omega$
independently of $(X,\tilde{W})$.

###  2.2 Structure on the functional

To prove validity of the confidence interval, I require that the formula $m$
is mean square continuous.

######  Assumption 2.1 (Mean square continuity).

There exists $\bar{L}_{m}<\infty$ s.t.

$\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\cdot\mathbb{E}[\gamma(W)]^{2}$

This condition will be key in Section 4, where I reduce the problem of
inference for $\theta_{0}$ into the problem of learning
$(\gamma_{0},\alpha^{\min}_{0})$, where $\alpha^{\min}_{0}$ is introduced
below. It is a powerful condition, yet it is easily satisfied in all of the
examples above.

######  Proposition 2.1 (Verifying continuity for examples).

For each of the evaluation and discrete treatment effect examples above,
Assumption 2.1 holds if the corresponding propensity scores are bounded away
from zero. For the incremental treatment effect examples, Assumption 2.1 holds
if $S(u)$ is bounded, and the ratio of $\omega(u)$ over the propensity is
bounded.

It is helpful to define the operator $M:\gamma(\cdot)\mapsto m(\cdot,\gamma)$
to represent the formula $m$. Wherever possible, the notation is consistent
with companion work [25], in which we propose and analyze confidence intervals
for adversarial estimators over generic function spaces. For the present
analysis, I require further structure on the operator $M$.

######  Assumption 2.2 (Bounded linear operator).

$M\in\mathcal{L}(\mathcal{H},\mathcal{H})$, i.e. $M$ is a bounded linear
operator from $\mathcal{H}$ to $\mathcal{H}$.

As long as the RKHS includes constant and Dirac functions with respect to
evaluated components, I can show $M:\mathcal{H}\rightarrow\mathcal{H}$ for the
examples above. Moreover, I can show that this operator is bounded and linear.
I appeal to the fact that the RKHS is a space in which evaluation is a bounded
linear functional. This is a key point, since $\|M\|_{op}<\infty$ will
underpin learning rates in Section 5.

######  Proposition 2.2 (Verifying boundedness for examples).

Construct the RKHS $\mathcal{H}$ over $\mathcal{W}$ as the tensor product of
RKHSs $\\{\mathcal{H}_{j}\\}$ over components $\\{W_{j}\\}$ of $W$, i.e.
$k(w,w^{\prime})=\prod_{j}k_{j}(w_{j},w_{j}^{\prime})$. Moreover, assume each
$k_{j}$ is bounded by some $\kappa_{j}<\infty$. If $W_{j}$ is a discrete
random variable, assume there exists a constant $c_{j}>0$ s.t.
$k_{j}(w_{j},w_{j}^{\prime})-c_{j}^{2}$ is positive definite over
$\mathcal{W}_{j}$. Then in each of the examples above, Assumption 2.2 holds.
For incremental effects, I additionally require $S\in\mathcal{H}_{d}$, which
is an indirect restriction on $\omega$.

######  Proposition 2.3 (Consequences of RKHS construction).

If a kernel $k_{j}$ is discrete then its RKHS $\mathcal{H}_{j}$ contains Dirac
functions. If such a $c_{j}$ exists, then $\mathcal{H}_{j}$ contains constant
functions. Let $c^{\max}_{j}$ be the largest such $c_{j}$ satisfying the
desired property. Then
$\|\mathbbm{1}_{\mathcal{H}_{j}}\|_{\mathcal{H}_{j}}=\frac{1}{c^{\max}_{j}}$.

From the closed form expression for a kernel $k_{j}$, $c_{j}^{\max}$ is often
obvious by inspection. With these results, I can now write

$m(w,\gamma)=[M\gamma](w)=\langle
M\gamma,\phi(w)\rangle_{\mathcal{H}}=\langle\gamma,M^{*}\phi(w)\rangle_{\mathcal{H}}$

where $M^{*}$ is the adjoint of $M$.

###  2.3 Reisz representation

An RKHS $\mathcal{H}$ is a subset of $L^{2}(\mathbb{P})$, the space of square
integrable functions with respect to the measure $\mathbb{P}$. In this
discussion, I temporarily set aside RKHS geometry and focus on
$L^{2}(\mathbb{P})$ geometry. Denote the $L^{2}(\mathbb{P})$ norm by
$\|\cdot\|_{2}$. In anticipation of later analysis, I consider the restricted
model of $\gamma_{0}\in\Gamma\subset\mathcal{H}\subset L^{2}(\mathbb{P})$,
where $\Gamma$ is some convex function space. In RKHS learning theory, mean
square rates are adaptive to the smoothness of $\gamma_{0}$, encoded by
$\gamma_{0}\in\Gamma$.111As a preview, I will take $\Gamma=\mathcal{H}^{c}$,
which is a smoother RKHS than $\mathcal{H}$. Conveniently,
$closure(span(\mathcal{H}^{c}))=\mathcal{H}^{c}$, and
$\mathcal{H}^{1}=\mathcal{H}$.

######  Proposition 2.4 (Riesz representation).

Suppose Assumption 2.1 holds. Further suppose $\gamma_{0}\in\Gamma$. Then
there exists a Riesz representer $\alpha_{0}\in L^{2}(\mathbb{P})$ s.t.

$\mathbb{E}[m(W,\gamma)]=\mathbb{E}[\alpha_{0}(W)\gamma(W)],\quad\forall\gamma\in\Gamma$

Moreover, there exists a unique minimal Riesz representer
$\alpha_{0}^{\min}\in closure(span(\Gamma))$ that satisfies this equation.

Riesz representation delivers a doubly robust formulation of the target
$\theta_{0}\in\mathbb{R}$. We view $(\gamma_{0},\alpha^{\min}_{0})$ as
nuisance parameters that we must learn in order to learn and infer
$\theta_{0}$.

$0=\mathbb{E}[\psi_{0}(W)],\quad\psi_{0}(w)=\psi(w,\theta_{0},\gamma_{0},\alpha^{\min}_{0}),\quad\psi(w,\theta,\gamma,\alpha)=m(w,\gamma)+\alpha(w)[y-\gamma(w)]-\theta$

The term $\alpha(w)[y-\gamma(w)]$ is the product of the Riesz representer and
the kernel method residual. It serves as a bias correction for the term
$m(w,\gamma)$. This formulation is doubly robust in the sense that the moment
function for $\theta_{0}$ remains valid if either $\gamma_{0}$ or $\alpha_{0}$
is correct, i.e.

$0=\mathbb{E}[\psi(W,\theta_{0},\gamma_{0},\alpha)]\quad\forall\alpha\in
L^{2}(\mathbb{P}),\quad
0=\mathbb{E}[\psi(W,\theta_{0},\gamma,\alpha_{0})]\quad\forall\gamma\in
L^{2}(\mathbb{P})$

While any Riesz representer $\alpha_{0}$ will suffice for valid learning and
inference, the minimal Riesz representer $\alpha_{0}^{\min}$ confers
semiparametric efficiency [24, Theorem 4.2].

##  3 Algorithm

###  3.1 Confidence interval

The goal of this paper is general purpose learning and inference for
$\theta_{0}$, where $\theta_{0}\in\mathbb{R}$ may be an (i) evaluation over
discrete domain, (ii) treatment effect of discrete treatment, or (iii)
incremental treatment effect of continuous treatment. In Section 2, I
demonstrated that any such $\theta_{0}$ is a mean square continuous functional
of an RKHS function $\gamma_{0}\in\mathcal{H}$ and hence has a unique minimal
representer $\alpha_{0}^{\min}$. In this section, I describe a meta algorithm
to turn kernel estimators $\hat{\gamma}$ of $\gamma_{0}$ and $\hat{\alpha}$
for $\alpha_{0}^{\min}$ into an estimator $\hat{\theta}$ of $\theta_{0}$ such
that $\hat{\theta}$ has a valid and practical confidence interval. This meta
algorithm is precisely debiased machine learning (DML) [22, 21].

Recall that $\hat{\gamma}$ may be any one of a number of different kernel
methods such as kernel ridge regression or kernel instrumental variable
regression. To preserve this generality, I do not instantiate a choice of
$\hat{\gamma}$; I treat it as a black box. In subsequent analysis, I will only
require that $\hat{\gamma}$ converges to $\gamma_{0}$ in mean square error.
This mean square rate is guaranteed by existing learning theory. As such, the
inferential theory builds directly on the learning theory.

The target estimator $\hat{\theta}$ as well as its confidence interval will
depend on nuisance estimators $\hat{\gamma}$ and $\hat{\alpha}$. For now, I
refrain from instantiating the estimator $\hat{\alpha}$ for
$\alpha_{0}^{\min}$. As we will see in subsequent analysis, the general theory
only requires that $\hat{\alpha}$ converges to $\alpha^{\min}_{0}$ in mean
square error. This property can be verified by extending classic learning
theory arguments, which I reserve for Section 5.

######  Algorithm 3.1 (Target and confidence interval).

Partition the sample into folds $\\{I_{\ell}\\}_{\ell=1:L}$. Denote by
$I_{\ell}^{c}$ observations not in fold $I_{\ell}$

  1. 1.

For each fold $\ell$, estimate $\hat{\gamma}_{\ell}$ and $\hat{\alpha}_{\ell}$
from observations in $I_{\ell}^{c}$

  2. 2.

Estimate $\hat{\theta}$ as

$\hat{\theta}=\frac{1}{n}\sum_{\ell=1}^{L}\sum_{i\in
I_{\ell}}\\{m(W_{i},\hat{\gamma}_{\ell})+\hat{\alpha}_{\ell}(W_{i})[Y_{i}-\hat{\gamma}_{\ell}(W_{i})]\\}$

  3. 3.

Estimate its $(1-a)\cdot 100$% confidence interval as

$\hat{\theta}\pm
c_{a}\frac{\hat{\sigma}}{\sqrt{n}},\quad\hat{\sigma}^{2}=\frac{1}{n}\sum_{\ell=1}^{L}\sum_{i\in
I_{\ell}}\\{m(W_{i},\hat{\gamma}_{\ell})+\hat{\alpha}_{\ell}(W_{i})[Y_{i}-\hat{\gamma}_{\ell}(W_{i})]-\hat{\theta}\\}^{2}$

where $c_{a}$ is the $1-\frac{a}{2}$ quantile of the standard Gaussian.

###  3.2 Bias correction

Algorithm 3.1 is a meta algorithm that takes as inputs the sample, the
algorithm $\hat{\gamma}$ for $\gamma_{0}$, and the algorithm $\hat{\alpha}$
for $\alpha_{0}^{\min}$. A broad literature already proposes and analyzes
estimators $\hat{\gamma}$. I now propose an estimator $\hat{\alpha}$ that
extends kernel ridge regression. As such, existing learning guarantees for
kernel ridge regression will extend to $\hat{\alpha}$.

For readability, in the main text I focus on the Riesz representer for
functionals of kernel ridge regression. The Riesz representer for functionals
of kernel instrumental variable regression is a straightforward extension that
incurs additional notation, which I reserve for the Appendix.

I motivate the new estimator by the following property.

######  Proposition 3.1 (Riesz representer loss).

Suppose the kernel $k(w,w^{\prime})$ is bounded. Then

$\alpha^{\min}_{0}\in\operatorname*{\arg\\!\min}_{\alpha\in\mathcal{H}}\mathcal{L}(\alpha),\quad\mathcal{L}(\alpha)=-2\langle\alpha,M^{*}\mu\rangle_{\mathcal{H}}+\langle\alpha,T\alpha\rangle_{\mathcal{H}}$

where $T=\mathbb{E}[\phi(W)\otimes\phi(W)]$ is the uncentered covariance
operator and $\mu=\mathbb{E}[\phi(W)]$ is the kernel mean embedding.

The quantities $(\mu,T)$ generalize the sufficient statistics
$(\tilde{M},\tilde{G})$ in automatic debiased machine learning (Auto-DML) [24,
26]. In Auto-DML, which uses $p$ explicit basis functions,
$\tilde{M}\in\mathbb{R}^{p}$ is the moment vector and
$\tilde{G}\in\mathbb{R}^{p\times p}$ is the covariance matrix. In my approach,
which uses the countable spectrum of the kernel $k$ as implicit basis
functions, $\mu\in\mathcal{H}$ is the kernel mean embedding [85] and
$T:\mathcal{H}\rightarrow\mathcal{H}$ is the covariance operator [31].

Next, I define the regularized Reisz representer in this context. The
regularization is a ridge penalty with regularization parameter $\lambda$.

######  Definition 3.1 (Kernel ridge Riesz representer: Population).

$\alpha_{\lambda}=\operatorname*{\arg\\!\min}_{\alpha\in\mathcal{H}}\mathcal{L}_{\lambda}(\alpha),\quad\mathcal{L}_{\lambda}(\alpha)=\mathcal{L}(\alpha)+\lambda\|\alpha\|^{2}_{\mathcal{H}}$

I define the estimator as the empirical analogue. To lighten notation, I
abstract from sample splitting and consider the setting where $n$ observations
are used.

######  Definition 3.2 (Kernel ridge Riesz representer: Sample).

$\hat{\alpha}=\operatorname*{\arg\\!\min}_{\alpha\in\mathcal{H}}\mathcal{L}^{n}_{\lambda}(\alpha),\quad\mathcal{L}^{n}_{\lambda}(\alpha)=-2\langle\alpha,M^{*}\hat{\mu}\rangle_{\mathcal{H}}+\langle\alpha,\hat{T}\alpha\rangle_{\mathcal{H}}+\lambda\|\alpha\|^{2}_{\mathcal{H}}$

where $\hat{T}=\frac{1}{n}\sum_{i=1}^{n}[\phi(W_{i})\otimes\phi(W_{i})]$ and
$\hat{\mu}=\frac{1}{n}\sum_{i=1}^{n}\phi(W_{i})$.

As a kernel estimator, $\hat{\alpha}$ can be implemented by simple matrix
operations. Whereas kernel methods typically involve matrix operations of the
matrix $K^{(1)}\in\mathbb{R}^{n\times n}$ with $(i,j)$-th entry
$k(W_{i},W_{j})$, this kernel method involves an extended kernel matrix
$K\in\mathbb{R}^{2n\times 2n}$. Intuitively, if $m$ is a partial or complete
evaluation, then the same partial or complete evaluations should apply to the
dictionary of features.

Wherever possible, I preserve the notation of companion work on adversarial
estimation [25]. Given a formula $m$, define $\phi^{(m)}(w)=M^{*}\phi(w)$.
Define the operator $\Phi:\mathcal{H}\rightarrow\mathbb{R}^{n}$ with $i$-th
row $\langle\phi(W_{i}),\cdot\rangle_{\mathcal{H}}$ and likewise the operator
$\Phi^{(m)}:\mathcal{H}\rightarrow\mathbb{R}^{n}$ with $i$-th row
$\langle\phi^{(m)}(W_{i}),\cdot\rangle_{\mathcal{H}}$. Finally define the
concatenated operator $\Psi:\mathcal{H}\rightarrow\mathbb{R}^{2n}$ that is
constructed by concatenating $\Phi$ and $\Phi^{(m)}$. By construction,
$K=\Psi\Psi^{*}$. For intuition, it is helpful to conceptualize these
operators as matrices. Informally,

$\Psi=\begin{bmatrix}\Phi\\\ \Phi^{(m)}\end{bmatrix},\quad
K=\begin{bmatrix}K^{(1)}&K^{(2)}\\\
K^{(3)}&K^{(4)}\end{bmatrix}=\begin{bmatrix}\Phi\Phi^{*}&\Phi(\Phi^{(m)})^{*}\\\
\Phi^{(m)}\Phi^{*}&\Phi^{(m)}(\Phi^{(m)})^{*}\end{bmatrix}$

Note that $\\{K^{(j)}\\}_{j\in[4]}\in\mathbb{R}^{n\times n}$ and hence
$K\in\mathbb{R}^{2n\times 2n}$ can be computed from data, though they depend
on the choice of formula $m$.

######  Proposition 3.2 (Extended kernel matrix: Computation).

Suppose the conditions of Proposition 2.2 hold. In the case of complete
evaluation with $m(W,\gamma)=\gamma(w)$,

$K^{(1)}_{ij}=k(W_{i},W_{j}),\quad K^{(2)}_{ij}=K^{(3)}_{ji}=k(W_{i},w),\quad
K^{(4)}_{ij}=\frac{k(W_{i},w)k(W_{j},w)}{(c^{\max})^{2}}$

where $c^{\max}=\prod_{j}c_{j}^{\max}$. In the case of partial evaluation with
$m(W,\gamma)=\gamma(d,X)$,

$\displaystyle K^{(1)}_{ij}$ $\displaystyle=k(D_{i},D_{j})k(X_{i},X_{j}),\quad
K^{(2)}_{ij}=K^{(3)}_{ji}=k(D_{i},d)k(X_{i},X_{j})$ $\displaystyle
K^{(4)}_{ij}$
$\displaystyle=\frac{k(D_{i},d)k(D_{j},d)}{(c_{d}^{\max})^{2}}k(X_{i},X_{j})$

With this additional notation, I prove that $\hat{\alpha}$ has a closed form
solution and derive that solution. My argument is an extension of the classic
representer theorem for kernel methods [47, 78].

######  Proposition 3.3 (Generalized representer theorem).

There exists some $\rho\in\mathbb{R}^{2n}$ s.t. $\hat{\alpha}=\Psi^{*}\rho$.

I use this generalized representation theorem to derive the closed form of
$\hat{\alpha}$ in terms of matrix operations.

######  Algorithm 3.2 (Kernel ridge Riesz representer: Computation).

Given observations $\\{W_{i}\\}$, formula $m$, and evaluation location $w$

  1. 1.

Calculate $K^{(j)}\in\mathbb{R}^{n\times n}$ as defined above

  2. 2.

Calculate $\Omega^{2n\times 2n}$ and $u,v\in\mathbb{R}^{2n}$ by

$\Omega=\begin{bmatrix}K^{(1)}K^{(1)}&K^{(1)}K^{(3)}\\\
K^{(3)}K^{(1)}&K^{(3)}K^{(3)}\end{bmatrix},\;v=\begin{bmatrix}K^{(2)}\\\
K^{(4)}\end{bmatrix}\mathbbm{1}_{n},\;u_{i}=\begin{cases}k(W_{i},w)&\text{ if
}i\in\\{1,...,n\\}\\\ \tilde{k}(W_{i},w)&\text{ if
}i\in\\{n+1,...,2n\\}\end{cases}$

where $\mathbbm{1}_{n}\in\mathbb{R}^{n}$ is a vector of ones,
$k(w,w^{\prime})=\langle\phi(w),\phi(w^{\prime})\rangle_{\mathcal{H}}$, and
$\tilde{k}(w,w^{\prime})=\langle\phi(w),M\phi(w^{\prime})\rangle_{\mathcal{H}}$

  3. 3.

Set $\hat{\alpha}(w)=v^{\top}(\Omega+n\lambda K)^{-1}u$

For comparison, if $\hat{\gamma}$ is kernel ridge regression, then
$\hat{\gamma}(w)=v^{\top}(K^{(1)}+n\lambda I)^{-1}u$ where $v_{i}=Y_{i}$ and
$u_{i}=k(W_{i},w)$.

##  4 Validity of confidence interval

I write this section at a high level of generality so that it can be used in
future work. In particular, I abstract from the RKHS framework. I assume high
level conditions and consider black box estimators
$(\hat{\gamma},\hat{\alpha})$. I prove by finite sample arguments that
$\hat{\theta}$ defined by Algorithm 3.1 is consistent, and its confidence
interval is valid and semiparametrically efficient. In Section 5, I will
verify the high level conditions in the RKHS framework.

Towards this end, define $\sigma^{2}=\mathbb{E}[\psi_{0}(W)]^{2}$,
$\eta^{3}=\mathbb{E}|\psi_{0}(W)|^{3}$, and
$\zeta^{4}=\mathbb{E}[\psi_{0}(W)]^{4}$. Write the Berry Esseen constant as
$c^{BE}=0.4748$ [79]. The result will be in terms of abstract mean square
rates on the nuisances.

######  Definition 4.1 (Mean square error).

Write the conditional mean square error of
$(\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})$ trained on $I^{c}_{\ell}$ as

$\mathcal{R}(\hat{\gamma}_{\ell})=\mathbb{E}[\\{\hat{\gamma}_{\ell}(W)-\gamma_{0}(W)\\}^{2}|I^{c}_{\ell}],\quad\mathcal{R}(\hat{\alpha}_{\ell})=\mathbb{E}[\\{\hat{\alpha}_{\ell}(W)-\alpha_{0}(W)\\}^{2}|I^{c}_{\ell}]$

We are now ready to state the first main result, which is a finite sample
Gaussian approximation.

######  Theorem 4.1 (Gaussian approximation).

Suppose

$\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq\bar{\sigma}^{2},\quad\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma(W)]^{2},\quad\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}$

Then w.p. $1-\epsilon$,

$\sup_{z\in\mathbb{R}}\left|\mathbb{P}\left(\frac{\sqrt{n}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right)-\Phi(z)\right|\leq
c^{BE}\left(\frac{\eta}{\sigma}\right)^{3}n^{-\frac{1}{2}}+\frac{\Delta}{\sqrt{2\pi}}+\epsilon$

where $\Phi(z)$ is the standard Gaussian c.d.f. and

$\Delta=\frac{3L}{\epsilon\cdot\sigma}\left\\{(\sqrt{L}_{m}+\bar{\alpha})\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}+\bar{\sigma}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}+\sqrt{n}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}\right\\}$

Theorem 4.1 is the first finite sample DML argument for black box machine
learning. It is a finite sample refinement of the asymptotic black box theorem
in [22]. It is a black box generalization of the main result in [24], which
provides a finite sample analysis specific to the Dantzig selector. By Theorem
4.1, the neighborhood of Gaussian approximation scales as
$\frac{\sigma}{\sqrt{n}}$. It is therefore helpful to bound the magnitude of
the asymptotic variance $\sigma^{2}$.

######  Proposition 4.1 (Variance bound).

Suppose the conditions of Theorem 4.1 hold. Then

$\sigma^{2}\leq
3(\bar{L}_{m}\mathbb{E}[\gamma_{0}(W)]^{2}+\bar{\alpha}^{2}\bar{\sigma}^{2}+\theta^{2}_{0})$

Observe that finite sample Gaussian approximation is in terms of the true
asymptotic variance $\sigma^{2}$. I now provide a guarantee for its estimator
$\hat{\sigma}^{2}$.

######  Theorem 4.2 (Variance estimation).

Suppose

$\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq\bar{\sigma}^{2},\quad\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma(W)]^{2},\quad\|\hat{\alpha}_{\ell}\|_{\infty}\leq\bar{\alpha}^{\prime}$

Then w.p. $1-\epsilon^{\prime}$,

$|\hat{\sigma}^{2}-\sigma^{2}|\leq\Delta^{\prime}+2\sqrt{\Delta^{\prime}}(\sqrt{\Delta^{\prime\prime}}+\sigma)+\Delta^{\prime\prime}$

where

$\Delta^{\prime}=\frac{24L}{\epsilon^{\prime}}\\{[\hat{\theta}-\theta_{0}]^{2}+[\bar{L}_{m}+(\bar{\alpha}^{\prime})^{2}]\mathcal{R}(\hat{\gamma}_{\ell})+\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})\\},\quad\Delta^{\prime\prime}=\sqrt{\frac{2}{\epsilon^{\prime}}}\zeta^{2}n^{-\frac{1}{2}}$

Theorem 4.2 is a both a black box generalization and a finite sample
refinement of the asymptotic theorem in [26] specific to the Lasso. Theorems
4.1 and 4.2 immediately imply sufficient conditions for validity of the
proposed confidence interval.

######  Corollary 4.1 (Confidence interval).

Suppose the assumptions of Theorems 4.1 and 4.2 hold as well as the regularity
condition on moments
$\left\\{\left(\frac{\eta}{\sigma}\right)^{3}+\zeta^{2}\right\\}n^{-\frac{1}{2}}\rightarrow
0$. Assume

$(\sqrt{\bar{L}_{m}}+\bar{\alpha}+\bar{\alpha}^{\prime})\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\overset{p}{\rightarrow}0,\quad\bar{\sigma}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}\overset{p}{\rightarrow}0,\quad\sqrt{n}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\overset{p}{\rightarrow}0$

Then the estimator $\hat{\theta}$ given in Algorithm 3.1 is consistent, i.e.
$\hat{\theta}\overset{p}{\rightarrow}\theta_{0}$, and the confidence interval
given in Algorithm 3.1 includes $\theta_{0}$ with probability approaching the
nominal level, i.e.
$\lim_{n\rightarrow\infty}\mathbb{P}\left(\theta_{0}\in\left[\hat{\theta}\pm\frac{\hat{\sigma}}{\sqrt{n}}\right]\right)=1-a$.

Corollary 4.1 summarizes simple sufficient conditions for inference in terms
of learning rates. Verifying these conditions is the goal of the next section.

##  5 Validity of bias correction

###  5.1 Goals

To employ Corollary 4.1, I must verify several conditions. In terms of the
general inference problem, I must show

$\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq\bar{\sigma}^{2},\quad\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma(W)]^{2},\quad\|\alpha_{0}\|_{\infty}\leq\bar{\alpha},\quad\|\hat{\alpha}_{\ell}\|_{\infty}\leq\bar{\alpha}^{\prime}$

Proposition 2.1 already previewed some of the relevant analysis. In what
follows, I articulate the mild requirements for these conditions to hold. The
same mild requirements will also furnish learning rates to satisfy

$(\sqrt{\bar{L}_{m}}+\bar{\alpha}+\bar{\alpha}^{\prime})\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\overset{p}{\rightarrow}0,\quad\bar{\sigma}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}\overset{p}{\rightarrow}0,\quad\sqrt{n}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\overset{p}{\rightarrow}0$

Note that the product condition
$\sqrt{n}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\overset{p}{\rightarrow}0$
allows a tradeoff: one of the learning rates may be slow, as long as the other
is sufficiently fast to compensate. While proving these results, I will
abstract from sample splitting in order to improve readability. In other
words, I will prove results for $(\hat{\gamma},\hat{\alpha})$ trained on the
full sample rather than $I^{c}_{\ell}$.

###  5.2 Assumptions

I place standard, weak assumptions on the supports of $(Y,W)$.

######  Assumption 5.1 (Original spaces).

Assume

  1. 1.

$W\in\mathcal{W}$ is a Polish space, i.e. separable and completely metrizable
topological spaces

  2. 2.

$Y\in\mathcal{Y}\subset\mathbb{R}$

A Polish space may be low, high, or infinite dimensional. Random variables
with support in a Polish space may be discrete or continuous. Next, I place
standard, weak assumptions on the RKHS $\mathcal{H}$.

######  Assumption 5.2 (RKHS regularity).

Assume

  1. 1.

$k$ is bounded. Formally,
$\sup_{w\in\mathcal{W}}\|\phi(w)\|_{\mathcal{H}}\leq\sqrt{\kappa}$

  2. 2.

$\phi(w)$ is measurable

  3. 3.

$k$ is characteristic

Commonly used kernels are bounded. Boundedness implies Bochner integrability,
which permits the exchange of expectation and inner product. Measurability is
a similarly weak condition. The characteristic property ensures injectivity of
the kernel mean embedding $\mu$, and hence uniqueness of the RKHS
representation [87, 88, 86]. See [86] for examples.

Proposition 2.1 verifies
$\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma(W)]^{2}$ for a
broad class of important examples. I now verify
$\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq\bar{\sigma}^{2}$,
$\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}$, and
$\|\hat{\alpha}\|_{\infty}\leq\bar{\alpha}^{\prime}$ under Assumptions 5.1 and
5.2.

######  Proposition 5.1 (Bounded noise and bounded Riesz representer).

Suppose $\gamma_{0}\in\mathcal{H}$ and Assumptions 5.1 and 5.2 hold. Then

$\bar{\sigma}^{2}=2(\mathbb{E}[Y]^{2}+\kappa\|\gamma_{0}\|^{2}_{\mathcal{H}}),\quad\bar{\alpha}=\sqrt{\kappa}\|\alpha^{\min}_{0}\|_{\mathcal{H}},\quad\bar{\alpha}^{\prime}=\frac{\kappa\|\alpha^{\min}_{0}\|_{\mathcal{H}}}{\sqrt{\lambda}}$

The next two assumptions are the crux of the RKHS learning paradigm [15, 84].
The former is an assumption about the smoothness of $\gamma_{0}$, parametrized
by a scalar $c\in[1,2]$. The latter is an assumption about the effective
dimension of the RKHS, parametrized by a scalar $b\in(1,\infty]$.

In preparation, define the convolution operator
$L_{k}:L^{2}(\mathbb{P})\rightarrow L^{2}(\mathbb{P})$, $f\mapsto\int
k(\cdot,w)f(w)d\mathbb{P}(w)$. $L_{k}$ is a self adjoint, positive, compact
operator, so by the spectral theorem we can denote its countable eigenvalues
and eigenfunctions by $\\{\lambda_{j}\\}$ and $\\{\varphi_{j}\\}$,
respectively:
$L_{k}f=\sum_{j=1}^{\infty}\lambda_{j}\langle\varphi_{j},f\rangle_{2}\cdot\varphi_{j}$.

With this notation, I express $L^{2}(\mathbb{P})$ and the RKHS $\mathcal{H}$
in terms of the series $\\{\varphi_{j}\\}$. If $f\in L^{2}(\mathbb{P})$, then
$f$ can be uniquely expressed as $f=\sum_{j=1}^{\infty}a_{j}\varphi_{j}$ and
the partial sums $\sum_{j=1}^{J}a_{j}\varphi_{j}$ converge to $f$ in
$L^{2}(\mathbb{P})$. Indeed,

$L^{2}(\mathbb{P})=\left\\{f=\sum_{j=1}^{\infty}a_{j}\varphi_{j}:\;\sum_{j=1}^{\infty}a_{j}^{2}<\infty\right\\},\quad\langle
f,g\rangle_{2}=\sum_{j=1}^{\infty}a_{j}b_{j}$

for $f=\sum_{j=1}^{\infty}a_{j}\varphi_{j}$ and
$g=\sum_{j=1}^{\infty}b_{j}\varphi_{j}$. By [27, Theorem 4], the RKHS
$\mathcal{H}$ corresponding to the kernel $k$ can be explicitly represented as

$\mathcal{H}=\left\\{f=\sum_{j=1}^{\infty}a_{j}\varphi_{j}:\;\sum_{j=1}^{\infty}\frac{a_{j}^{2}}{\lambda_{j}}<\infty\right\\},\quad\langle
f,g\rangle_{\mathcal{H}}=\sum_{j=1}^{\infty}\frac{a_{j}b_{j}}{\lambda_{j}}$

Let us interpret this result, known as Picard’s criterion [5]. Recall that
$\\{\lambda_{j}\\}$ is a weakly decreasing sequence. The RKHS $\mathcal{H}$ is
the subset of $L^{2}(\mathbb{P})$ for which higher order terms in the series
$\\{\varphi_{j}\\}$ have a smaller contribution. Finally, I define

$\mathcal{H}^{c}=\left\\{f=\sum_{j=1}^{\infty}a_{j}\varphi_{j}:\;\sum_{j=1}^{\infty}\frac{a_{j}^{2}}{\lambda^{c}_{j}}<\infty\right\\}\subset\mathcal{H},\quad
c\in[1,2]$

which is interpretable as an even smoother RKHS. We are now ready to state the
smoothness assumption.

######  Assumption 5.3 (Smoothness).

Assume $\gamma_{0}\in\mathcal{H}^{c}$ for some $c\in[1,2]$.

In other words, $\gamma_{0}$ is a particularly smooth element of
$\mathcal{H}$; it is well approximated by the leading terms in the series
$\\{\varphi_{j}\\}$. This condition appears under the name of the source
condition in both statistical learning [84, 15] and econometrics [17, 16, 19,
18]. An abstract, equivalent version of this assumption is helpful for
analysis.

######  Proposition 5.2 (Consequences of smoothness).

The following statements are equivalent: (i) $\gamma_{0}\in\mathcal{H}^{c}$;
(ii) there exists some witness function $f\in\mathcal{H}$ s.t.
$\gamma_{0}=T^{\frac{c-1}{2}}f$; (iii) there exists some witness function
$\tilde{f}\in L^{2}(\mathbb{P})$ s.t.
$\gamma_{0}=L_{k}^{\frac{c}{2}}\tilde{f}$. Moreover,
$\gamma_{0}\in\mathcal{H}^{c}$ implies $\alpha^{\min}_{0}\in\mathcal{H}^{c}$.

The effective dimension condition is also in terms of the spectrum.

######  Assumption 5.4 (Effective dimension).

If the RKHS is finite dimensional, write $J\leq\beta<\infty$ and $b=\infty$.
If the RKHS is infinite dimensional, the eigenvalues $\\{\lambda_{k}\\}$ decay
at a polynomial rate: $\iota\leq j^{b}\cdot\lambda_{j}\leq\beta$ for $j\geq
1$, where $\iota,\beta>0$ and $b\in(1,\infty)$.

Note that $\\{\lambda_{k}\\}$ are also the eigenvalues of the covariance
operator $T$.

######  Proposition 5.3 (Consequences of effective dimension).

If Assumption 5.4 holds then $\lambda_{j}=\Theta(j^{-b})$. Moreover,
$L_{k}(\cdot)=\sum_{j=1}^{\infty}\lambda_{j}\langle\varphi_{j},\cdot\rangle_{2}\cdot\varphi_{j}$
if and only if $T(\cdot)=\sum_{j=1}^{\infty}\lambda_{j}\langle
e_{j},\cdot\rangle_{2}\cdot e_{j}$ where
$e_{j}=\sqrt{\lambda_{j}}\varphi_{j}$.

The spectrum of a random vector’s covariance characterizes its dimension. In
this sense, the assumption on spectral decay quantifies effective dimension.
Following [15], I denote by $\mathcal{P}(b,c)$ the class of distributions that
satisfy Assumptions 5.3 and 5.4.

###  5.3 Guarantees

Assumptions 5.1, 5.2, 5.3, and 5.4 are classic assumptions in RKHS learning
theory. I quote a classic result on the mean square rate for kernel ridge
regression. This result also requires a weak condition on the noise.

######  Assumption 5.5 (Noise).

$Y=\gamma_{0}(W)+\varepsilon$ where $\varepsilon$ is bounded, Gaussian, or
subGaussian.

######  Theorem 5.1 (Kernel ridge regression: MSE [15]).

Suppose Assumptions 5.1, 5.2, 5.3, 5.4, and 5.5 hold. Calibrate the ridge
regularization sequence s.t.

$\lambda=\begin{cases}n^{-\frac{1}{2}}&\text{ if }\quad b=\infty\\\
n^{-\frac{b}{bc+1}}&\text{ if }\quad b\in(1,\infty),\;c\in(1,2]\\\
\ln^{\frac{b}{b+1}}(n)\cdot n^{-\frac{b}{b+1}}&\text{ if }\quad
b\in(1,\infty),\;c=1\end{cases}$

Then kernel ridge regression $\hat{\gamma}$ trained on $\\{W_{i}\\}_{i\in[n]}$
satisfies

$\lim_{\tau\rightarrow\infty}\lim_{n\rightarrow\infty}\sup_{\rho\in\mathcal{P}(b,c)}\mathbb{P}_{\\{W_{i}\\}\sim\rho^{n}}(\mathcal{R}(\hat{\gamma})>\tau\cdot
r_{n})=0$

where
$\mathcal{R}(\hat{\gamma})=\mathbb{E}[\\{\hat{\gamma}(W)-\gamma_{0}(W)\\}^{2}|\\{W_{i}\\}_{i\in[n]}]$
and

$r_{n}=\begin{cases}n^{-1}&\text{ if }\quad b=\infty\\\
n^{-\frac{bc}{bc+1}}&\text{ if }\quad b\in(1,\infty),\;c\in(1,2]\\\
\ln^{\frac{b}{b+1}}(n)\cdot n^{-\frac{b}{b+1}}&\text{ if }\quad
b\in(1,\infty),\;c=1\end{cases}$

Moreover, the rate is optimal when $b\in(1,\infty)$ and $c\in(1,2]$. It is
optimal up to a logarithmic factor when $b\in(1,\infty)$ and $c=1$.

Recall that $b=\infty$ is the finite dimensional regime;
$b\in(1,\infty),\;c\in(1,2]$ is the infinite dimensional regime with
polynomial spectral decay and additional smoothness; $b\in(1,\infty),\;c=1$ is
the infinite dimensional regime with polynomial spectral decay and no
additional smoothness. A similar result is available for kernel instrumental
variable regression by combining [81, Theorem 4] with [29, Lemma 11].

Remarkably, an almost identical result is possible for the kernel ridge Riesz
representer. This is the second main result of the paper. The result is almost
for free in the sense that it only requires replacing Assumption 5.5 with
Assumptions 2.1 and 2.2. Indeed, the core techniques are the same. A similar
result holds for the Riesz representer of functionals of kernel instrumental
variable regression by generalizing [81] rather than [15].

######  Theorem 5.2 (Kernel ridge Riesz representer: MSE).

Suppose Assumptions 2.1 and 2.2 as well Assumptions 5.1, 5.2, 5.3, and 5.4
hold. Calibrate the ridge regularization sequence $\lambda$ as in Theorem 5.1.
Then the kernel ridge Riesz representer $\hat{\alpha}$ trained on
$\\{W_{i}\\}_{i\in[n]}$ satisfies

$\lim_{\tau\rightarrow\infty}\lim_{n\rightarrow\infty}\sup_{\rho\in\mathcal{P}(b,c)}\mathbb{P}_{\\{W_{i}\\}\sim\rho^{n}}(\mathcal{R}(\hat{\alpha})>\tau\cdot
r_{n})=0$

where
$\mathcal{R}(\hat{\alpha})=\mathbb{E}[\\{\hat{\alpha}(W)-\alpha^{\min}_{0}(W)\\}^{2}|\\{W_{i}\\}_{i\in[n]}]$
and $r_{n}$ is as in Theorem 5.1

######  Corollary 5.1 (Confidence interval).

Suppose the assumptions of Theorems 5.1 and 5.2 hold as well as the regularity
condition on moments
$\left\\{\left(\frac{\eta}{\sigma}\right)^{3}+\zeta^{2}\right\\}n^{-\frac{1}{2}}\rightarrow
0$. Then for any $c\in(1,2]$ and $b\in(1,\infty]$, the estimator
$\hat{\theta}$ is consistent, i.e.
$\hat{\theta}\overset{p}{\rightarrow}\theta_{0}$, and the confidence interval
includes $\theta_{0}$ with probability approaching the nominal level, i.e.
$\lim_{n\rightarrow\infty}\mathbb{P}\left(\theta_{0}\in\left[\hat{\theta}\pm\frac{\hat{\sigma}}{\sqrt{n}}\right]\right)=1-a$.

Recall that in Assumption 5.3, $c=1$ means $\gamma_{0}$ is correctly specified
as an element in $\mathcal{H}$, while $c>1$ means $\gamma_{0}$ is in the
interior of $\mathcal{H}$. As long as $\gamma_{0}$ is in the interior of the
RKHS, rather than at the boundary, we can construct valid confidence intervals
by kernel matrix operations. Meanwhile, the RKHS may be finite or infinite
dimensional, as long as the spectrum decays at some polynomial rate
$\lambda_{j}=\Theta(j^{-b})$ with $b>1$.

###  5.4 Trimming

Examining the proof of Corollary 5.1, the only condition that fails to hold
when $c=1$ is
$\bar{\alpha}^{\prime}\sqrt{\mathcal{R}(\hat{\gamma})}\overset{p}{\rightarrow}0$.
Specifically, the bound on $\bar{\alpha}^{\prime}$ given in Proposition 5.1
diverges too quickly. A solution is to trim the kernel ridge Riesz representer
using a known bound on the minimal Riesz representer $\alpha_{0}^{\min}$. In
particular, consider the following estimator.

######  Algorithm 5.1 (Kernel ridge Riesz representer: Trimming).

Given $\hat{\alpha}$ calculated from Algorithm 3.2, set

$\tilde{\alpha}(w)=\begin{cases}-\bar{\alpha}&\text{ if
}\quad\hat{\alpha}(w)<-\bar{\alpha}\\\ \hat{\alpha}(w)&\text{ if
}\quad\hat{\alpha}(w)\in[-\bar{\alpha},\bar{\alpha}]\\\ \bar{\alpha}&\text{ if
}\quad\hat{\alpha}(w)>\bar{\alpha}\end{cases}$

Denote by $(\tilde{\theta},\tilde{\sigma}^{2})$ the estimators for
$(\theta_{0},\sigma^{2})$ calculated from Algorithm 3.1 using
$(\hat{\gamma},\tilde{\alpha})$ rather than $(\hat{\gamma},\hat{\alpha})$.

######  Corollary 5.2 (Confidence interval with trimming).

Suppose the assumptions of Theorems 5.1 and 5.2 hold as well as the regularity
condition on moments
$\left\\{\left(\frac{\eta}{\sigma}\right)^{3}+\zeta^{2}\right\\}n^{-\frac{1}{2}}\rightarrow
0$. Then for any $c\in[1,2]$ and $b\in(1,\infty]$, the estimator
$\tilde{\theta}$ is consistent, i.e.
$\tilde{\theta}\overset{p}{\rightarrow}\theta_{0}$, and the confidence
interval includes $\theta_{0}$ with probability approaching the nominal level,
i.e.
$\lim_{n\rightarrow\infty}\mathbb{P}\left(\theta_{0}\in\left[\tilde{\theta}\pm\frac{\tilde{\sigma}}{\sqrt{n}}\right]\right)=1-a$.

Now the case $c=1$ is allowed. Since $c=1$ simply means
$\gamma_{0}\in\mathcal{H}$, the inference result allows us to actually relax
Assumption 5.3. In other words, smoothness beyond correct specification
hastens learning but is irrelevant to inference. Meanwhile, the RKHS may be
finite or infinite dimensional, as long as the spectrum decays at some
polynomial rate $\lambda_{j}=\Theta(j^{-b})$ with $b>1$.

##  6 Conclusion

For any kernel method with a mean square learning rate, I propose a practical
procedure to based on bias correction and sample splitting to calculate
confidence intervals for its functionals. The inferential results are almost
free in the sense that classic learning theory assumptions, together with a
mean square continuity condition, are enough to justify the procedure. By
providing confidence intervals for functionals of kernel ridge regression and
kernel instrumental variable regression, I facilitate their use in social
science and epidemiology.

## Acknowledgments and Disclosure of Funding

I am grateful to Alberto Abadie, Anish Agarwal, Victor Chernozhukov, Anna
Mikusheva, Whitney Newey, Devavrat Shah, Vasilis Syrgkanis, Suhas Vijaykumar,
and Yinchu Zhu for helpful discussions. I am grateful to the Jerry A Hausman
Graduate Dissertation Fellowship for financial support.

## References

  * [1] Chunrong Ai and Xiaohong Chen.  Efficient estimation of models with conditional moment restrictions containing unknown functions.  Econometrica, 71(6):1795–1843, 2003.
  * [2] Chunrong Ai and Xiaohong Chen.  Estimation of possibly misspecified semiparametric conditional moment restriction models with different conditioning variables.  Journal of Econometrics, 141(1):5–43, 2007.
  * [3] Chunrong Ai and Xiaohong Chen.  The semiparametric efficiency bound for models of sequential moment restrictions containing unknown functions.  Journal of Econometrics, 170(2):442–457, 2012.
  * [4] Susan Athey, Guido W Imbens, and Stefan Wager.  Approximate residual balancing: Debiased inference of average treatment effects in high dimensions.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(4):597–623, 2018.
  * [5] Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco.  On regularization algorithms in learning theory.  Journal of Complexity, 23(1):52–72, 2007.
  * [6] Alexandre Belloni, Victor Chernozhukov, Ivan Fernández-Val, and Christian Hansen.  Program evaluation and causal inference with high-dimensional data.  Econometrica, 85(1):233–298, 2017.
  * [7] Alexandre Belloni, Victor Chernozhukov, and Christian Hansen.  Inference for high-dimensional sparse econometric models.  arXiv:1201.0220, 2011.
  * [8] Alexandre Belloni, Victor Chernozhukov, and Christian Hansen.  Inference on treatment effects after selection among high-dimensional controls.  The Review of Economic Studies, 81(2):608–650, 2014.
  * [9] Alexandre Belloni, Victor Chernozhukov, and Kengo Kato.  Uniform post-selection inference for least absolute deviation regression and other Z-estimation problems.  Biometrika, 102(1):77–94, 2014.
  * [10] Alexandre Belloni, Victor Chernozhukov, and Lie Wang.  Pivotal estimation via square-root lasso in nonparametric regression.  The Annals of Statistics, 42(2):757–788, 2014.
  * [11] Peter J Bickel.  On adaptive estimation.  The Annals of Statistics, pages 647–671, 1982.
  * [12] Peter J Bickel, Chris AJ Klaassen, Peter J Bickel, Ya’acov Ritov, J Klaassen, Jon A Wellner, and YA’Acov Ritov.  Efficient and Adaptive Estimation for Semiparametric Models, volume 4.  Johns Hopkins University Press Baltimore, 1993.
  * [13] Peter J Bickel and Yaacov Ritov.  Estimating integrated squared density derivatives: Sharp best order of convergence estimates.  Sankhyā: The Indian Journal of Statistics, Series A, pages 381–393, 1988.
  * [14] Jelena Bradic and Mladen Kolar.  Uniform inference for high-dimensional quantile regression: Linear functionals and regression rank scores.  arXiv:1702.06209, 2017.
  * [15] Andrea Caponnetto and Ernesto De Vito.  Optimal rates for the regularized least-squares algorithm.  Foundations of Computational Mathematics, 7(3):331–368, 2007.
  * [16] Marine Carrasco.  A regularization approach to the many instruments problem.  Journal of Econometrics, 170(2):383–398, 2012.
  * [17] Marine Carrasco, Jean-Pierre Florens, and Eric Renault.  Linear inverse problems in structural econometrics estimation based on spectral decomposition and regularization.  Handbook of Econometrics, 6:5633–5751, 2007.
  * [18] Marine Carrasco and Barbara Rossi.  In-sample inference and forecasting in misspecified factor models.  Journal of Business & Economic Statistics, 34(3):313–338, 2016\.
  * [19] Marine Carrasco and Guy Tchuente.  Regularized LIML for many instruments.  Journal of Econometrics, 186(2):427–442, 2015.
  * [20] Gary Chamberlain.  Panel data.  Handbook of Econometrics, 2:1247–1318, 1984.
  * [21] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins.  Double/debiased machine learning for treatment and structural parameters: Double/debiased machine learning.  The Econometrics Journal, 21(1), 2018.
  * [22] Victor Chernozhukov, Juan Carlos Escanciano, Hidehiko Ichimura, Whitney K Newey, and James M Robins.  Locally robust semiparametric estimation.  arXiv:1608.00033, 2016.
  * [23] Victor Chernozhukov, Christian Hansen, and Martin Spindler.  Valid post-selection and post-regularization inference: An elementary, general approach.  Annual Review of Economics, 7(1):649–688, 2015.
  * [24] Victor Chernozhukov, Whitney Newey, and Rahul Singh.  De-biased machine learning of global and local parameters using regularized Riesz representers.  arXiv:1802.08667, 2018.
  * [25] Victor Chernozhukov, Whitney Newey, Rahul Singh, and Vasilis Syrgkanis.  Adversarial estimation of Riesz representers.  arXiv:2101.00009, 2020.
  * [26] Victor Chernozhukov, Whitney K Newey, and Rahul Singh.  Automatic debiased machine learning of causal and structural effects.  arXiv:1809.05224, 2018.
  * [27] Felipe Cucker and Steve Smale.  On the mathematical foundations of learning.  Bulletin of the American Mathematical Society, 39(1):1–49, 2002\.
  * [28] Iván Díaz and Mark J van der Laan.  Targeted data adaptive estimation of the causal dose–response curve.  Journal of Causal Inference, 1(2):171–192, 2013.
  * [29] Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis.  Minimax estimation of conditional moment models.  arXiv:2006.07201, 2020.
  * [30] Dylan J Foster and Vasilis Syrgkanis.  Orthogonal statistical learning.  arXiv:1901.09036, 2019.
  * [31] Kenji Fukumizu, Francis R Bach, and Michael I Jordan.  Dimensionality reduction for supervised learning with reproducing kernel hilbert spaces.  Journal of Machine Learning Research, 5(Jan):73–99, 2004.
  * [32] Rafail Z Hasminskii and Ildar A Ibragimov.  On the nonparametric estimation of functionals.  In Proceedings of the Second Prague Symposium on Asymptotic Statistics, 1979.
  * [33] David A Hirshberg and Stefan Wager.  Debiased inference of average partial effects in single-index models.  arXiv:1811.02547, 2018.
  * [34] David A Hirshberg and Stefan Wager.  Augmented minimax linear estimation.  arXiv:1712.00038v5, 2019.
  * [35] I Ibragimov and R Has’minskii.  Statistical estimation, vol. 16 of.  Applications of Mathematics, 1981.
  * [36] Hidehiko Ichimura and Whitney K Newey.  The influence function of semiparametric estimators.  arXiv:1508.01378, 2015.
  * [37] Guido W Imbens and Whitney K Newey.  Identification and estimation of triangular simultaneous equations models without additivity.  Econometrica, 77(5):1481–1512, 2009.
  * [38] Jana Jankova and Sara Van De Geer.  Confidence intervals for high-dimensional inverse covariance estimation.  Electronic Journal of Statistics, 9(1):1205–1229, 2015.
  * [39] Jana Jankova and Sara Van De Geer.  Confidence regions for high-dimensional generalized linear models under sparsity.  arXiv:1610.01353, 2016.
  * [40] Jana Jankova and Sara Van De Geer.  Semiparametric efficiency bounds for high-dimensional models.  The Annals of Statistics, 46(5):2336–2359, 2018.
  * [41] Adel Javanmard and Andrea Montanari.  Confidence intervals and hypothesis testing for high-dimensional regression.  The Journal of Machine Learning Research, 15(1):2869–2909, 2014\.
  * [42] Adel Javanmard and Andrea Montanari.  Hypothesis testing in high-dimensional regression under the Gaussian random design model: Asymptotic theory.  IEEE Transactions on Information Theory, 60(10):6522–6554, 2014\.
  * [43] Adel Javanmard and Andrea Montanari.  Debiasing the lasso: Optimal sample size for Gaussian designs.  The Annals of Statistics, 46(6A):2593–2622, 2018.
  * [44] Palle Jorgensen and Feng Tian.  Discrete reproducing kernel Hilbert spaces: Sampling and distribution of Dirac-masses.  The Journal of Machine Learning Research, 16(1):3079–3114, 2015\.
  * [45] Edward H Kennedy.  Optimal doubly robust estimation of heterogeneous causal effects.  arXiv:2004.14497, 2020.
  * [46] Edward H Kennedy, Zongming Ma, Matthew D McHugh, and Dylan S Small.  Nonparametric methods for doubly robust estimation of continuous treatment effects.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(4):1229, 2017.
  * [47] George Kimeldorf and Grace Wahba.  Some results on Tchebycheffian spline functions.  Journal of Mathematical Analysis and Applications, 33(1):82–95, 1971.
  * [48] Chris AJ Klaassen.  Consistent estimation of the influence function of locally asymptotically linear estimators.  The Annals of Statistics, pages 1548–1562, 1987.
  * [49] Michael R Kosorok.  Introduction to Empirical Processes and Semiparametric Inference.  Springer Science & Business Media, 2007.
  * [50] B Ya Levit.  On the efficiency of a class of non-parametric estimates.  Theory of Probability & Its Applications, 20(4):723–740, 1976\.
  * [51] Alexander R Luedtke and Mark J Van Der Laan.  Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy.  Annals of Statistics, 44(2):713, 2016.
  * [52] Wang Miao, Zhi Geng, and Eric J Tchetgen Tchetgen.  Identifying causal effects with proxy variables of an unmeasured confounder.  Biometrika, 105(4):987–993, 2018.
  * [53] Wang Miao and Eric Tchetgen Tchetgen.  A confounding bridge approach for double negative control inference on causal effects.  arXiv:1808.04945, 2018.
  * [54] Krikamol Muandet, Motonobu Kanagawa, Sorawit Saengkyongam, and Sanparith Marukatat.  Counterfactual mean embeddings.  arXiv:1805.08845, 2018.
  * [55] Krikamol Muandet, Arash Mehrjou, Si Kai Lee, and Anant Raj.  Dual iv: A single stage instrumental variable regression.  arXiv:1910.12358, 2019.
  * [56] Whitney K Newey.  The asymptotic variance of semiparametric estimators.  Econometrica, pages 1349–1382, 1994.
  * [57] Whitney K Newey, Fushing Hsieh, and James M Robins.  Undersmoothing and bias corrected functional estimation.  Technical report, MIT Department of Economics, 1998.
  * [58] Whitney K Newey, Fushing Hsieh, and James M Robins.  Twicing kernels and a small bias property of semiparametric estimators.  Econometrica, 72(3):947–962, 2004.
  * [59] Whitney K Newey and James R Robins.  Cross-fitting and fast remainder rates for semiparametric estimation.  arXiv:1801.09138, 2018.
  * [60] Matey Neykov, Yang Ning, Jun S Liu, and Han Liu.  A unified theory of confidence regions and testing for high-dimensional estimating equations.  Statistical Science, 33(3):427–443, 2018.
  * [61] Jerzy Neyman.  Optimal asymptotic tests of composite statistical hypotheses.  In Probability and Statistics, page 416–444. Wiley, 1959.
  * [62] Jerzy Neyman.  C ($\alpha$) tests and their use.  Sankhyā: The Indian Journal of Statistics, Series A, pages 1–21, 1979.
  * [63] Xinkun Nie and Stefan Wager.  Quasi-oracle estimation of heterogeneous treatment effects.  arXiv:1712.04912, 2017.
  * [64] Yang Ning and Han Liu.  A general theory of hypothesis tests and confidence regions for sparse high dimensional models.  The Annals of Statistics, 45(1):158–195, 2017.
  * [65] Johann Pfanzagl.  Lecture notes in statistics.  Contributions to a General Asymptotic Statistical Theory, 13, 1982\.
  * [66] Zhao Ren, Tingni Sun, Cun-Hui Zhang, and Harrison H Zhou.  Asymptotic normality and optimalities in estimation of large Gaussian graphical models.  The Annals of Statistics, 43(3):991–1026, 2015.
  * [67] James Robins, Lingling Li, Eric Tchetgen, Aad van der Vaart, et al.  Higher order influence functions and minimax estimation of nonlinear functionals.  In Probability and Statistics: Essays in Honor of David A. Freedman, pages 335–421. Institute of Mathematical Statistics, 2008.
  * [68] James Robins, Mariela Sued, Quanhong Lei-Gomez, and Andrea Rotnitzky.  Comment on "performance of double-robust estimators when inverse probability weights are highly variable".  Statistical Science, 22(4):544–559, 2007.
  * [69] James M Robins and Andrea Rotnitzky.  Semiparametric efficiency in multivariate regression models with missing data.  Journal of the American Statistical Association, 90(429):122–129, 1995.
  * [70] James M Robins, Andrea Rotnitzky, and Lue Ping Zhao.  Analysis of semiparametric regression models for repeated outcomes in the presence of missing data.  Journal of the American Statistical Association, 90(429):106–121, 1995.
  * [71] Peter M Robinson.  Root-n-consistent semiparametric regression.  Econometrica, pages 931–954, 1988.
  * [72] Paul R Rosenbaum and Donald B Rubin.  The central role of the propensity score in observational studies for causal effects.  Biometrika, 70(1):41–55, 1983.
  * [73] Dominik Rothenhäusler and Bin Yu.  Incremental causal effects.  arXiv:1907.13258, 2019.
  * [74] Dan Rubin and Mark J van der Laan.  A general imputation methodology for nonparametric regression with censored data.  Technical report, UC Berkeley Division of Biostatistics, 2005.
  * [75] Daniel Rubin and Mark J van der Laan.  Extending marginal structural models through local, penalized, and additive learning.  Technical report, UC Berkeley Division of Biostatistics, 2006.
  * [76] Daniel O Scharfstein, Andrea Rotnitzky, and James M Robins.  Adjusting for nonignorable drop-out using semiparametric nonresponse models.  Journal of the American Statistical Association, 94(448):1096–1120, 1999.
  * [77] Anton Schick.  On asymptotically efficient estimation in semiparametric models.  The Annals of Statistics, 14(3):1139–1151, 1986.
  * [78] Bernhard Schölkopf, Ralf Herbrich, and Alex J Smola.  A generalized representer theorem.  In International conference on computational learning theory, pages 416–426. Springer, 2001.
  * [79] Irina Shevtsova.  On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands.  arXiv:1111.6554, 2011.
  * [80] Rahul Singh.  Kernel methods for unobserved confounding: Negative controls, proxies, and instruments.  arXiv:2012.10315, 2020.
  * [81] Rahul Singh, Maneesh Sahani, and Arthur Gretton.  Kernel instrumental variable regression.  In Advances in Neural Information Processing Systems, pages 4595–4607, 2019.
  * [82] Rahul Singh and Liyang Sun.  De-biased machine learning in intrumental variable models for treatment effects.  arXiv:1909.05244, 2019.
  * [83] Rahul Singh, Liyuan Xu, and Arthur Gretton.  Kernel methods for policy evaluation: Treatment effects, mediation analysis, and off-policy planning.  arXiv:2010.04855, 2020.
  * [84] Steve Smale and Ding-Xuan Zhou.  Learning theory estimates via integral operators and their approximations.  Constructive Approximation, 26(2):153–172, 2007.
  * [85] Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf.  A Hilbert space embedding for distributions.  In International Conference on Algorithmic Learning Theory, pages 13–31, 2007.
  * [86] Bharath Sriperumbudur.  On the optimal estimation of probability measures in weak and strong topologies.  Bernoulli, 22(3):1839–1893, 2016.
  * [87] Bharath Sriperumbudur, Kenji Fukumizu, and Gert Lanckriet.  On the relation between universality, characteristic kernels and RKHS embedding of measures.  In International Conference on Artificial Intelligence and Statistics, pages 773–780, 2010.
  * [88] Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet.  Universality, characteristic kernels and RKHS embedding of measures.  Journal of Machine Learning Research, 12(7), 2011.
  * [89] Dougal J Sutherland.  Fixing an error in Caponnetto and de Vito (2007).  arXiv:1702.02982, 2017.
  * [90] Eric J Tchetgen Tchetgen, Andrew Ying, Yifan Cui, Xu Shi, and Wang Miao.  An introduction to proximal causal learning.  arXiv:2009.10982, 2020.
  * [91] B Toth and MJ van der Laan.  TMLE for marginal structural models based on an instrument.  Technical report, UC Berkeley Division of Biostatistics, 2016.
  * [92] Anastasios Tsiatis.  Semiparametric Theory and Missing Data.  Springer Science & Business Media, 2007.
  * [93] Sara Van de Geer, Peter Bühlmann, Ya’acov Ritov, and Ruben Dezeure.  On asymptotically optimal confidence regions and tests for high-dimensional models.  The Annals of Statistics, 42(3):1166–1202, 2014.
  * [94] Mark J van der Laan and Alexander R Luedtke.  Targeted learning of an optimal dynamic treatment, and statistical inference for its mean outcome.  Technical report, UC Berkeley Division of Biostatistics, 2014.
  * [95] Mark J Van der Laan and Sherri Rose.  Targeted Learning: Causal Inference for Observational and Experimental Data.  Springer Science & Business Media, 2011.
  * [96] Mark J Van Der Laan and Daniel Rubin.  Targeted maximum likelihood learning.  The International Journal of Biostatistics, 2(1), 2006.
  * [97] Aad Van Der Vaart et al.  On differentiable functionals.  The Annals of Statistics, 19(1):178–204, 1991.
  * [98] Aad W Van der Vaart.  Asymptotic Statistics, volume 3.  Cambridge University Press, 2000.
  * [99] Cun-Hui Zhang and Stephanie S Zhang.  Confidence intervals for low dimensional parameters in high dimensional linear models.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(1):217–242, 2014.
  * [100] Wenjing Zheng and Mark J Van Der Laan.  Asymptotic theory for cross-validated targeted maximum likelihood estimation.  2010\.
  * [101] Yinchu Zhu and Jelena Bradic.  Breaking the curse of dimensionality in regression.  arXiv:1708.00430., 2017.
  * [102] Yinchu Zhu and Jelena Bradic.  Linear hypothesis testing in dense high-dimensional linear models.  Journal of the American Statistical Association, 113(524):1583–1600, 2018.

##  Appendix A Framework

###### Proof of Proposition 2.1.

I consider each functional of kernel ridge regression. The arguments for the
functionals of kernel instrumental variable regression are identical.

  1. 1.

Evaluation.

$\mathbb{E}[\gamma(w)]^{2}=\\{\gamma(w)\\}^{2}=\left\\{\mathbb{E}\left[\gamma(W)\frac{1\\{W=w\\}}{\mathbb{P}(w)}\right]\right\\}^{2}\leq\left\\{\frac{\mathbb{E}|\gamma(W)|}{\mathbb{P}(w)}\right\\}^{2}\leq\frac{\mathbb{E}[\gamma(W)]^{2}}{\mathbb{P}(w)^{2}}$

i.e. $\bar{L}_{m}=\mathbb{P}(w)^{-2}$

  2. 2.

Treatment effects. For ATE,

$\mathbb{E}[\gamma(d,X)]^{2}=\mathbb{E}\left[\frac{1\\{D=d\\}}{\mathbb{P}(d|X)}\gamma(D,X)^{2}\right]\leq\frac{\mathbb{E}\left[\gamma(D,X)\right]^{2}}{\inf_{x}\mathbb{P}(d|x)}$

i.e. $\bar{L}_{m}=\\{\inf_{x}\mathbb{P}(d|x)\\}^{-1}$. ATE-DS, ATT, and CATE
are similar.

  3. 3.

Incremental treatment effect.

$\displaystyle\mathbb{E}[S(U)\gamma(U,X)]^{2}$
$\displaystyle=\mathbb{E}\left[\frac{\omega(D)}{f(D|X)}S(D)^{2}\gamma(D,X)^{2}\right]$
$\displaystyle\leq\sup_{u}S(u)^{2}\cdot\sup_{d,x}\frac{|\omega(d)|}{f(d|x)}\cdot\mathbb{E}\left[\gamma(D,X)^{2}\right]$

i.e. $\bar{L}_{m}=\sup_{u}S(u)^{2}\cdot\sup_{d,x}\frac{|\omega(d)|}{f(d|x)}$

∎

###### Proof of Proposition 2.2.

As in the proof of Proposition 2.1, it is sufficient to show the results for
functionals of kernel ridge regression.

  1. 1.

Evaluation.

    1. (a)

$M:\mathcal{H}\rightarrow\mathcal{H}$.

For each constituent RKHS $\mathcal{H}_{j}$, the existence of $c_{j}$ implies
that $\mathcal{H}_{j}$ includes the constant function over $\mathcal{W}_{j}$.
Hence if $\gamma\in\mathcal{H}$ then $\gamma$ evaluated in its $j$-th argument
is also an element of $\mathcal{H}$ (since it becomes constant with respect to
its $j$-th argument).

    2. (b)

$\|M\|_{op}<\infty$.

Write $M\gamma=\gamma(w)\mathbbm{1}_{\mathcal{H}}$ where
$\mathbbm{1}_{\mathcal{H}}$ is the constant function in $\mathcal{H}$. The
definition of an RKHS as a space where evaluation is a bounded linear
functional can be seen from

$\gamma(w)=\langle\gamma,\phi(w)\rangle_{\mathcal{H}}\leq\|\gamma\|_{\mathcal{H}}\sqrt{\kappa}$

Hence

$\frac{\|M\gamma\|_{\mathcal{H}}}{\|\gamma\|_{\mathcal{H}}}\leq\frac{\|\gamma\|_{\mathcal{H}}\sqrt{\kappa}\|\mathbbm{1}_{\mathcal{H}}\|_{\mathcal{H}}}{\|\gamma\|_{\mathcal{H}}}=\sqrt{\kappa}\|\mathbbm{1}_{\mathcal{H}}\|_{\mathcal{H}}$

i.e. $\|M\|_{op}=\sqrt{\kappa}\|\mathbbm{1}_{\mathcal{H}}\|_{\mathcal{H}}$

  2. 2.

ATE (and ATE-DS).

    1. (a)

$M:\mathcal{H}\rightarrow\mathcal{H}$.

See the argument for evaluation above.

    2. (b)

$\|M\|_{op}<\infty$.

Denote $\phi(w)=\phi(d)\otimes\phi(x)$ and
$\gamma=\gamma_{d}\otimes\gamma_{x}$. Write
$M\gamma=[\gamma_{d}(d)\mathbbm{1}_{\mathcal{H}_{d}}]\otimes\gamma_{x}$ where
$\mathbbm{1}_{\mathcal{H}_{d}}$ is the constant function in $\mathcal{H}_{d}$.
As before

$\gamma_{d}(d)=\langle\gamma_{d},\phi(d)\rangle_{\mathcal{H}_{d}}\leq\|\gamma_{d}\|_{\mathcal{H}_{d}}\sqrt{\kappa_{d}}$

Hence

$\frac{\|M\gamma\|_{\mathcal{H}}}{\|\gamma\|_{\mathcal{H}}}\leq\frac{\|\gamma_{d}\|_{\mathcal{H}_{d}}\sqrt{\kappa_{d}}\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}\cdot\|\gamma_{x}\|_{\mathcal{H}_{x}}}{\|\gamma_{d}\|_{\mathcal{H}_{d}}\cdot\|\gamma_{x}\|_{\mathcal{H}_{x}}}=\sqrt{\kappa_{d}}\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}$

i.e.
$\|M\|_{op}=\sqrt{\kappa_{d}}\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}$

  3. 3.

ATT (and CATE).

    1. (a)

$M:\mathcal{H}\rightarrow\mathcal{H}$.

Consider the extension $\delta(d_{1},x,d_{2})$ of $\gamma(d_{1},x)$ with
feature map $\phi(d_{1})\otimes\phi(x)\otimes\phi(d_{2})$. Since
$\mathcal{H}_{d}$ contains the constant function, any $\gamma$ can be
trivially extended this way: take
$\delta=\delta_{d_{1}}\otimes\delta_{x}\otimes\delta_{d_{2}}=\gamma_{d_{1}}\otimes\gamma_{x}\otimes\mathbbm{1}_{\mathcal{H}_{d}}$.
With this notation, write
$M\delta=[\delta_{d_{1}}(d^{\prime})\mathbbm{1}_{\mathcal{H}_{d}}]\otimes\delta_{x}\otimes\mathbbm{1}_{d_{2}=d}$.
Note that
$\delta_{d_{1}}(d^{\prime})\mathbbm{1}_{\mathcal{H}_{d}}=\gamma_{d_{1}}(d^{\prime})\mathbbm{1}_{\mathcal{H}_{d}}\in\mathcal{H}_{d}$
since $\mathcal{H}_{d}$ contains constant functions.
$\delta_{x}=\gamma_{x}\in\mathcal{H}_{x}$ by construction. Finally,
$\mathbbm{1}_{d_{2}=d}\in\mathcal{H}_{d}$ since $\mathcal{H}_{d}$ contains
Dirac functions.

    2. (b)

$\|M\|_{op}<\infty$.

As before

$\delta_{d_{1}}(d^{\prime})=\langle\delta_{d_{1}},\phi(d^{\prime})\rangle_{\mathcal{H}_{d}}\leq\|\delta_{d_{1}}\|_{\mathcal{H}_{d}}\sqrt{\kappa_{d}}$

Hence over functions of the form
$\delta=\delta_{d_{1}}\otimes\delta_{x}\otimes\mathbbm{1}_{\mathcal{H}_{d}}$

$\frac{\|M\delta\|_{\mathcal{H}}}{\|\delta\|_{\mathcal{H}}}\leq\frac{\|\delta_{d_{1}}\|_{\mathcal{H}_{d}}\sqrt{\kappa_{d}}\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}\cdot\|\delta_{x}\|_{\mathcal{H}_{x}}\cdot\|\mathbbm{1}_{d_{2}=d}\|_{\mathcal{H}_{d}}}{\|\delta_{d_{1}}\|_{\mathcal{H}_{d}}\cdot\|\delta_{x}\|_{\mathcal{H}_{x}}\cdot\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}}=\sqrt{\kappa_{d}}\cdot\|\mathbbm{1}_{d_{2}=d}\|_{\mathcal{H}_{d}}$

i.e.
$\|M\|_{op}=\sqrt{\kappa_{d}}\cdot\|\mathbbm{1}_{d_{2}=d}\|_{\mathcal{H}_{d}}$

  4. 4.

Incremental treatment effects.

    1. (a)

$M:\mathcal{H}\rightarrow\mathcal{H}$. Consider the extension
$\delta(d_{1},x,d_{2})$ of $\gamma(d_{1},x)$ with feature map
$\phi(d_{1})\otimes\phi(x)\otimes\phi(d_{2})$ as above. Since
$\mathcal{H}_{d}$ contains the constant function, any $\gamma$ can be
trivially extended this way: take
$\delta=\delta_{d_{1}}\otimes\delta_{x}\otimes\delta_{d_{2}}=\gamma_{d_{1}}\otimes\gamma_{x}\otimes\mathbbm{1}_{\mathcal{H}_{d}}$.
With this notation, write $M\delta=\delta_{d_{1}}\otimes\delta_{x}\otimes S$.
Note that $\delta_{d_{1}}=\gamma_{d_{1}}\in\mathcal{H}_{d}$ by construction.
Similarly $\delta_{x}=\gamma_{x}\in\mathcal{H}_{x}$ by construction. Finally,
$S\in\mathcal{H}_{d}$ is an indirect assumption on the density $\omega$.

    2. (b)

$\|M\|_{op}<\infty$. Over functions of the form
$\delta=\delta_{d_{1}}\otimes\delta_{x}\otimes\mathbbm{1}_{\mathcal{H}_{d}}$

$\frac{\|M\delta\|_{\mathcal{H}}}{\|\delta\|_{\mathcal{H}}}=\frac{\|\delta_{d_{1}}\|_{\mathcal{H}_{d}}\cdot\|\delta_{x}\|_{\mathcal{H}_{x}}\cdot\|S\|_{\mathcal{H}_{d}}}{\|\delta_{d_{1}}\|_{\mathcal{H}_{d}}\cdot\|\delta_{x}\|_{\mathcal{H}_{x}}\cdot\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}}=\frac{\|S\|_{\mathcal{H}_{d}}}{\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}}$

i.e.
$\|M\|_{op}=\frac{\|S\|_{\mathcal{H}_{d}}}{\|\mathbbm{1}_{\mathcal{H}_{d}}\|_{\mathcal{H}_{d}}}$

∎

###### Proof of Proposition 2.3.

See [44, Theorem 2.12] for the first result. For the second result, recall
that a function $f:W\rightarrow\mathbb{R}$ is an element of $\mathcal{H}$ iff
$k(w,w^{\prime})-cf(w)f(w^{\prime})$ is positive definite for some $c>0$. Then
$\|f\|_{\mathcal{H}}=\frac{1}{c}$ for the largest possible $c$. ∎

###### Proof of Proposition 2.4.

First, I show that the functional $\gamma\mapsto\mathbb{E}[m(W,\gamma)]$ is
bounded as a functional over $L^{2}(\mathbb{P})$. Write

$\\{|\mathbb{E}[m(W,\gamma)]|\\}^{2}\leq\\{\mathbb{E}|m(W,\gamma)|\\}^{2}\leq\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma(W)]^{2}$

Therefore

$\frac{|\mathbb{E}[m(W,\gamma)]|}{\|\gamma\|_{2}}\leq\frac{\sqrt{\bar{L}_{m}}\|\gamma\|_{2}}{\|\gamma\|_{2}}\leq\sqrt{\bar{L}_{m}}$

Hence Riesz representation theorem w.r.t $L^{2}(\mathbb{P})$ implies existence
of the RR $\alpha_{0}\in L^{2}(\mathbb{P})$. [24, Lemma S3.1] guarantees
existence of the unique minimal Riesz representer $\alpha_{0}^{\min}\in
closure(span(\Gamma))$. ∎

##  Appendix B Algorithm

###### Proof of Proposition 3.1.

Recall that $\gamma_{0}\in\Gamma$ implies that the minimal representer
$\alpha_{0}^{\min}\in\Gamma\subset\mathcal{H}$ by Proposition 2.4. Trivially,

$\alpha^{\min}_{0}\in\operatorname*{\arg\\!\min}_{\alpha\in\mathcal{H}}\mathcal{R}(\alpha),\quad\mathcal{R}(\alpha)=\mathbb{E}[\alpha^{\min}_{0}(W)-\alpha(W)]^{2}$

Note that

$\displaystyle\mathcal{R}(\alpha)$
$\displaystyle=\mathbb{E}[\alpha^{\min}_{0}(W)-\alpha(W)]^{2}$
$\displaystyle=\mathbb{E}[\alpha^{\min}_{0}(W)]^{2}-2\mathbb{E}[\alpha_{0}(W)\alpha(W)]+\mathbb{E}[\alpha(W)]^{2}$
$\displaystyle=C-2\mathbb{E}[m(W,\alpha)]+\mathbb{E}[\alpha(W)]^{2}$

Boundedness of the kernel implies Bochner integrability of $\phi(\cdot)$,
which then allows us to exchange expectation and inner product. By the RKHS
representation property and Bochner integrability of $\phi(\cdot)$

$\mathbb{E}[m(W,\alpha)]=\mathbb{E}[\langle\alpha,M^{*}\phi(w)\rangle_{\mathcal{H}}]=\langle\alpha,M^{*}\mu\rangle_{\mathcal{H}},\quad\mu=\mathbb{E}[\phi(W)]$

and

$\mathbb{E}[\alpha(W)]^{2}=\mathbb{E}[\langle\alpha,\phi(W)\rangle^{2}_{\mathcal{H}}]=\langle\alpha,T\alpha\rangle_{\mathcal{H}},\quad
T=\mathbb{E}[\phi(W)\otimes\phi(W)]$

∎

###### Proof of Proposition 3.2.

In both cases

$\displaystyle K^{(1)}_{ij}$
$\displaystyle=\langle\phi(W_{i}),\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle K^{(2)}_{ij}$
$\displaystyle=\langle\phi(W_{i}),\phi^{(m)}(W_{j})\rangle_{\mathcal{H}}=\langle\phi(W_{i}),M^{*}\phi(W_{j})\rangle_{\mathcal{H}}=\langle
M\phi(W_{i}),\phi(W_{j})\rangle_{\mathcal{H}}$ $\displaystyle K^{(4)}_{ij}$
$\displaystyle=\langle\phi^{(m)}(W_{i}),\phi^{(m)}(W_{j})\rangle_{\mathcal{H}}=\langle
M^{*}\phi(W_{i}),M^{*}\phi(W_{j})\rangle_{\mathcal{H}}=\langle
M\phi(W_{i}),M\phi(W_{j})\rangle_{\mathcal{H}}$

where the final equality holds by opening up the definition of $M$. Formally,

$\displaystyle\langle M^{*}\phi(W_{i}),M^{*}\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle M[M^{*}\phi(W_{i})],\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle
m(\cdot,M^{*}k(W_{i},\cdot)),\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle
M^{*}[m(\cdot,k(W_{i},\cdot))],\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle
m(\cdot,k(W_{i},\cdot)),M\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle M\phi(W_{i}),M\phi(W_{j})\rangle_{\mathcal{H}}$

I now specialize these expressions.

  1. 1.

Complete evaluation

$\displaystyle[M\gamma](\cdot)$
$\displaystyle=m(\cdot,\gamma(\cdot))=\gamma(w)\mathbbm{1}_{\mathcal{H}}(\cdot)$
$\displaystyle[M\phi(W)](\cdot)$
$\displaystyle=m(\cdot,k(W,\cdot))=k(W,w)\mathbbm{1}_{\mathcal{H}}(\cdot)$

Hence

$\displaystyle\langle\phi(W_{i}),\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=k(W_{i},W_{j})$ $\displaystyle\langle
M\phi(W_{i}),\phi(W_{j})\rangle_{\mathcal{H}}$ $\displaystyle=\langle
k(W_{i},w)\mathbbm{1}_{\mathcal{H}},\phi(W_{j})\rangle_{\mathcal{H}}=k(W_{i},w)$
$\displaystyle\langle M\phi(W_{i}),M\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle
k(W_{i},w)\mathbbm{1}_{\mathcal{H}},k(W_{j},w)\mathbbm{1}_{\mathcal{H}}\rangle_{\mathcal{H}}=k(W_{i},w)k(W_{j},w)\|\mathbbm{1}_{\mathcal{H}}\|^{2}_{\mathcal{H}}$

  2. 2.

Partial evaluation

$\displaystyle[M\gamma](\cdot)$
$\displaystyle=m(\cdot,\gamma(\cdot))=[\gamma_{d}(d)\mathbbm{1}_{\mathcal{H}_{d}}(\cdot)]\otimes\gamma_{x}(\cdot)$
$\displaystyle[M\phi(W)](\cdot)$
$\displaystyle=m(\cdot,k(W,\cdot))=[k(D,d)\mathbbm{1}_{\mathcal{H}_{d}}(\cdot)]\otimes
k(X,\cdot)$

Hence

$\displaystyle\langle\phi(W_{i}),\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle\phi(D_{i})\otimes\phi(X_{i}),\phi(D_{j})\otimes\phi(X_{j})\rangle_{\mathcal{H}}$
$\displaystyle=k(D_{i},D_{j})k(X_{i},X_{j})$ $\displaystyle\langle
M\phi(W_{i}),\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle[k(D_{i},d)\mathbbm{1}_{\mathcal{H}_{d}}]\otimes\phi(X_{i}),\phi(D_{j})\otimes\phi(X_{j})\rangle_{\mathcal{H}}$
$\displaystyle=k(D_{i},d)k(X_{i},X_{j})$ $\displaystyle\langle
M\phi(W_{i}),M\phi(W_{j})\rangle_{\mathcal{H}}$
$\displaystyle=\langle[k(D_{i},d)\mathbbm{1}_{\mathcal{H}_{d}}]\otimes\phi(X_{i}),[k(D_{j},d)\mathbbm{1}_{\mathcal{H}_{d}}]\otimes\phi(X_{j})\rangle_{\mathcal{H}}$
$\displaystyle=k(D_{i},d)k(D_{j},d)\|\mathbbm{1}_{\mathcal{H}_{d}}\|^{2}_{\mathcal{H}_{d}}\cdot
k(X_{i},X_{j})$

∎

###### Proof of Proposition 3.3.

Note that

$M^{*}\hat{\mu}=\frac{1}{n}\sum_{i=1}^{n}M^{*}\phi(W_{i})=\frac{1}{n}\sum_{i=1}^{n}\phi^{(m)}(W_{i})$

and

$\hat{T}\alpha=\frac{1}{n}\sum_{i=1}^{n}[\phi(W_{i})\otimes\phi(W_{i})]\alpha=\frac{1}{n}\sum_{i=1}^{n}\langle\alpha,\phi(W_{i})\rangle_{\mathcal{H}}\phi(W_{i})$

Write the objective as

$\mathcal{L}^{n}_{\lambda}(\alpha)=\frac{1}{n}\sum_{i=1}^{n}\left\\{-2\langle\alpha,\phi^{(m)}(W_{i})\rangle_{\mathcal{H}}+\langle\alpha,\phi(W_{i})\rangle^{2}_{\mathcal{H}}\right\\}+\lambda\|\alpha\|^{2}_{\mathcal{H}}$

Recall that for an RKHS, evaluation is a continuous functional represented as
the inner product with the feature map. Due to the ridge penalty, the stated
objective is coercive and strongly convex w.r.t $\alpha$. Hence it has a
unique minimizer $\hat{\alpha}$ that obtains the minimum.

Write $\hat{\alpha}=\hat{\alpha}_{n}+\hat{\alpha}^{\perp}_{n}$ where
$\hat{\alpha}_{n}\in row(\Psi)$ and $\hat{\alpha}_{n}^{\perp}\in null(\Psi)$.
Substituting this decomposition of $\hat{\alpha}$ into the objective, we see
that

$\mathcal{L}^{n}_{\lambda}(\hat{\alpha})=\mathcal{L}^{n}_{\lambda}(\hat{\alpha}_{n})+\lambda\|\hat{\alpha}_{n}^{\perp}\|^{2}_{\mathcal{H}}$

Therefore

$\mathcal{L}^{n}_{\lambda}(\hat{\alpha})\geq\mathcal{L}^{n}_{\lambda}(\hat{\alpha}_{n})$

Since $\hat{\alpha}$ is the unique minimizer, $\hat{\alpha}=\hat{\alpha}_{n}$.
∎

###### Derivation of Algorithm 3.2.

By Proposition 3.3, $\hat{\alpha}=\Psi^{*}\rho$. Substituting this expression
into $\mathcal{L}^{n}_{\lambda}(\alpha)$ gives
$\mathcal{L}^{n}_{\lambda}(\rho)$.

$\displaystyle\mathcal{L}^{n}_{\lambda}(\rho)$
$\displaystyle=-2\rho^{\top}\Psi\frac{1}{n}\sum_{i=1}^{n}\phi^{(m)}(W_{i})+\rho^{\top}\Psi\hat{T}\Psi^{*}\rho+\lambda\rho^{\top}\Psi\Psi^{*}\rho$
$\displaystyle=-\frac{2}{n}\rho^{\top}\sum_{i=1}^{n}\Psi\phi^{(m)}(W_{i})+\frac{1}{n}\rho^{\top}\Psi\Phi^{*}\Phi\Psi^{*}\rho+\lambda\rho^{\top}\Psi\Psi^{*}\rho$
$\displaystyle=-\frac{2}{n}\rho^{\top}v+\frac{1}{n}\rho^{\top}\Omega\rho+\lambda\rho^{\top}K\rho$

where

$\Omega=\Psi\Phi^{*}\Phi\Psi^{*},\quad v=\sum_{i=1}^{n}\Psi\phi^{(m)}(W_{i})$

Differentiating, the FOC gives

$0=-\frac{2}{n}v+\frac{2}{n}\Omega\rho+2\lambda K\rho\iff\rho=(\Omega+n\lambda
K)^{-1}v$

To evaluate the estimator at a test location $w$ involves computing

$\hat{\alpha}(w)=\langle\hat{\alpha},\phi(w)\rangle_{\mathcal{H}}=\rho^{\top}\Psi\phi(w)=v^{\top}(\Omega+n\lambda
K)^{-1}\Psi\phi(w)$

Finally note that

$\langle\phi^{(m)}(w),\phi(w^{\prime})\rangle_{\mathcal{H}}=\langle
M^{*}\phi(w),\phi(w^{\prime})\rangle_{\mathcal{H}}=\langle\phi(w),M\phi(w^{\prime})\rangle_{\mathcal{H}}$

∎

##  Appendix C Validity of confidence interval

###  C.1 Gateaux differentiation

For readability, I introduce the following notation for Gateaux
differentiation.

######  Definition C.1 (Gateaux derivative).

Let $u(w),v(w)$ be functions and let $\tau,\zeta\in\mathbb{R}$ be scalars. The
Gateaux derivative of $\psi(w,\theta,\gamma,\alpha)$ with respect to its
argument $\gamma$ in the direction $u$ is

$[\partial_{\gamma}\psi(w,\theta,\gamma,\alpha)](u)=\frac{\partial}{\partial\tau}\psi(w,\theta,\gamma+\tau
u,\alpha)\bigg{|}_{\tau=0}$

The cross derivative of $\psi(w,\theta,\gamma,\alpha)$ with respect to its
argument $(\gamma,\alpha)$ in the directions $(u,v)$ is

$[\partial^{2}_{\gamma,\alpha}\psi(w,\theta,\gamma,\alpha)](u,v)=\frac{\partial^{2}}{\partial\tau\partial\zeta}\psi(w,\theta,\gamma+\tau
u,\alpha+\zeta v)\bigg{|}_{\tau=0,\zeta=0}$

######  Proposition C.1 (Calculation of derivatives).

$\displaystyle[\partial_{\gamma}\psi(w,\theta,\gamma,\alpha)](u)$
$\displaystyle=m(w,u)-\alpha(w)u(w)$
$\displaystyle[\partial_{\alpha}\psi(w,\theta,\gamma,\alpha)](v)$
$\displaystyle=v(w)[y-\gamma(w)]$
$\displaystyle[\partial^{2}_{\gamma,\alpha}\psi(w,\theta,\gamma,\alpha)](u,v)$
$\displaystyle=-v(w)u(w)$

###### Proof.

For the first result, write

$\psi(w,\theta,\gamma+\tau u,\alpha)=m(w,\gamma)+\tau
m(w,u)+\alpha(w)[y-\gamma(w)-\tau u(w)]-\theta$

For the second result, write

$\psi(w,\theta,\gamma,\alpha+\zeta v)=m(w,\gamma)+\alpha(w)[y-\gamma(w)]+\zeta
v(w)[y-\gamma(w)]-\theta$

For the final result, write

$\displaystyle\psi(w,\theta,\gamma+\tau u,\alpha+\zeta v)$
$\displaystyle=m(w,\gamma)+\tau m(w,u)+\alpha(w)[y-\gamma(w)-\tau u(w)]+\zeta
v(w)[y-\gamma(w)-\tau u(w)]-\theta$

Finally, take scalar derivatives with respect to $(\tau,\zeta)$. ∎

By using the doubly robust moment function, we have the following helpful
property.

######  Proposition C.2 (Mean zero derivatives).

For any $(u,v)$,

$\mathbb{E}[\partial_{\gamma}\psi_{0}(W)](u)=0,\quad\mathbb{E}[\partial_{\alpha}\psi_{0}(W)](v)=0$

###### Proof.

For the first result, write

$\mathbb{E}[\partial_{\gamma}\psi_{0}(W)](u)=\mathbb{E}[m(W,u)-\alpha_{0}(W)u(W)]$

Then appeal to the definition of the Riesz representer. For the second result,
write

$\mathbb{E}[\partial_{\alpha}\psi_{0}(W)](v)=\mathbb{E}[v(W)[y-\gamma_{0}(W)]]$

In the case of nonparametric regression, $\gamma_{0}(w)=\mathbb{E}[Y|W=w]$ and
we appeal to law of iterated expectations. In the case of nonparametric
instrumental variable regression, $\gamma_{0}(w)=h(x)$ s.t.
$\mathbb{E}[Y|Z=z]=\mathbb{E}[h(X)|Z=z]$. The result then holds for
$v(w)=v(z)$. ∎

###  C.2 Taylor expansion

Train $(\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})$ on observations in
$I_{\ell}^{c}$. Let $m=|I_{\ell}|=\frac{n}{L}$ be the number of observations
in $I_{\ell}$. Denote by $\mathbb{E}_{\ell}[\cdot]$ the average over
observations in $I_{\ell}$.

######  Definition C.2 (Foldwise target and oracle).

$\displaystyle\hat{\theta}_{\ell}$
$\displaystyle=\mathbb{E}_{\ell}[m(W,\hat{\gamma}_{\ell})+\hat{\alpha}_{\ell}(W)\\{Y-\hat{\gamma}_{\ell}(W)\\}]$
$\displaystyle\bar{\theta}_{\ell}$
$\displaystyle=\mathbb{E}_{\ell}[m(W,\gamma_{0})+\alpha_{0}(W)\\{Y-\gamma_{0}(W)\\}]$

######  Proposition C.3 (Taylor expansion).

Let $u=\hat{\gamma}_{\ell}-\gamma_{0}$ and $v=\hat{\alpha}_{\ell}-\alpha_{0}$.
Then
$\sqrt{m}(\hat{\theta}_{\ell}-\bar{\theta}_{\ell})=\sum_{j=1}^{3}\Delta_{j{\ell}}$
where

$\displaystyle\Delta_{1{\ell}}$
$\displaystyle=\sqrt{m}\mathbb{E}_{\ell}[m(W,u)-\alpha_{0}(W)u(W)]$
$\displaystyle\Delta_{2{\ell}}$
$\displaystyle=\sqrt{m}\mathbb{E}_{\ell}[v(W)\\{Y-\gamma_{0}(W)\\}]$
$\displaystyle\Delta_{3{\ell}}$
$\displaystyle=\sqrt{m}\mathbb{E}_{\ell}[-u(W)v(W)]$

###### Proof.

An exact Taylor expansion gives

$\psi(w,\theta_{0},\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})-\psi_{0}(w)=[\partial_{\gamma}\psi_{0}(w)](u)+[\partial_{\alpha}\psi_{0}(w)](v)+[\partial^{2}_{\gamma,\alpha}\psi_{0}(w)](u,v)$

Averaging over observations in $I_{\ell}$

$\displaystyle\hat{\theta}_{\ell}-\bar{\theta}_{\ell}$
$\displaystyle=\mathbb{E}_{\ell}[\psi(W,\theta_{0},\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})]-\mathbb{E}_{\ell}[\psi_{0}(W)]$
$\displaystyle=\mathbb{E}_{\ell}[\partial_{\gamma}\psi_{0}(W)](u)+\mathbb{E}_{\ell}[\partial_{\alpha}\psi_{0}(W)](v)+\mathbb{E}_{\ell}[\partial^{2}_{\gamma,\alpha}\psi_{0}(W)](u,v)$

Finally appeal to Proposition C.1. ∎

###  C.3 Residuals

######  Definition C.3 (Mean square error).

Write the conditional mean square error of
$(\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})$ trained on $I^{c}_{\ell}$ as

$\displaystyle\mathcal{R}(\hat{\gamma}_{\ell})$
$\displaystyle=\mathbb{E}[\\{\hat{\gamma}_{\ell}(W)-\gamma_{0}(W)\\}^{2}|I^{c}_{\ell}]$
$\displaystyle\mathcal{R}(\hat{\alpha}_{\ell})$
$\displaystyle=\mathbb{E}[\\{\hat{\alpha}_{\ell}(W)-\alpha_{0}(W)\\}^{2}|I^{c}_{\ell}]$

######  Proposition C.4 (Residuals).

Suppose

$\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq\bar{\sigma}^{2},\quad\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma(W)]^{2},\quad\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}$

Then w.p. $1-\frac{\epsilon}{L}$,

$\displaystyle|\Delta_{1\ell}|$ $\displaystyle\leq
t_{1}=\sqrt{\frac{6L}{\epsilon}}\sqrt{\bar{L}_{m}+\bar{\alpha}^{2}}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}$
$\displaystyle|\Delta_{2\ell}|$ $\displaystyle\leq
t_{2}=\sqrt{\frac{3L}{\epsilon}}\bar{\sigma}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}$
$\displaystyle|\Delta_{3\ell}|$ $\displaystyle\leq
t_{3}=\frac{3\sqrt{L}}{\epsilon}\sqrt{n}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}$

###### Proof.

I proceed in steps

  1. 1.

Markov inequality

$\displaystyle\mathbb{P}(|\Delta_{1\ell}|>t_{1})$
$\displaystyle\leq\frac{\mathbb{E}[\Delta^{2}_{1\ell}]}{t_{1}^{2}}$
$\displaystyle\mathbb{P}(|\Delta_{2\ell}|>t_{2})$
$\displaystyle\leq\frac{\mathbb{E}[\Delta^{2}_{2\ell}]}{t_{2}^{2}}$
$\displaystyle\mathbb{P}(|\Delta_{3\ell}|>t_{3})$
$\displaystyle\leq\frac{\mathbb{E}|\Delta_{3\ell}|}{t_{3}}$

  2. 2.

Law of iterated expectations

$\displaystyle\mathbb{E}[\Delta^{2}_{1\ell}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\Delta^{2}_{1\ell}|I^{c}_{\ell}]]$
$\displaystyle\mathbb{E}[\Delta^{2}_{2\ell}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\Delta^{2}_{2\ell}|I^{c}_{\ell}]]$
$\displaystyle\mathbb{E}|\Delta_{3\ell}|$
$\displaystyle=\mathbb{E}[\mathbb{E}[|\Delta_{3\ell}||I^{c}_{\ell}]]$

  3. 3.

Bounding conditional moments

Conditional on $I_{\ell}^{c}$, $(u,v)$ are nonrandom. Moreover, observations
within fold $I_{\ell}$ are independent. Hence

$\displaystyle\mathbb{E}[\Delta^{2}_{1\ell}|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}[\\{m(W,u)-\alpha_{0}(W)u(W)\\}^{2}|I^{c}_{\ell}]$
$\displaystyle\leq
2\mathbb{E}[m(W,u)^{2}|I^{c}_{\ell}]+2\mathbb{E}[\\{\alpha_{0}(W)u(W)\\}^{2}|I^{c}_{\ell}]$
$\displaystyle\leq
2(\bar{L}_{m}+\bar{\alpha}^{2})\mathcal{R}(\hat{\gamma}_{\ell})$

Similarly

$\displaystyle\mathbb{E}[\Delta^{2}_{2\ell}|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}[\\{v(W)[Y-\gamma_{0}(W)]\\}^{2}|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}[v(W)^{2}\mathbb{E}[\\{Y-\gamma_{0}(W)\\}^{2}|W,I^{c}_{\ell}]|I^{c}_{\ell}]$
$\displaystyle\leq\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})$

Finally

$\displaystyle\mathbb{E}[|\Delta_{3\ell}||I^{c}_{\ell}]$
$\displaystyle=\sqrt{m}\mathbb{E}[|-u(W)v(W)||I^{c}_{\ell}]$
$\displaystyle\leq\sqrt{m}\mathbb{E}[u(W)^{2}|I^{c}_{\ell}]\mathbb{E}[v(W)^{2}|I^{c}_{\ell}]$
$\displaystyle=\sqrt{m}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}$

  4. 4.

Collecting results

$\displaystyle\mathbb{P}(|\Delta_{1\ell}|>t_{1})$
$\displaystyle\leq\frac{2(\bar{L}_{m}+\bar{\alpha}^{2})\mathcal{R}(\hat{\gamma}_{\ell})}{t_{1}^{2}}=\frac{\epsilon}{3L}$
$\displaystyle\mathbb{P}(|\Delta_{2\ell}|>t_{2})$
$\displaystyle\leq\frac{\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})}{t_{2}^{2}}=\frac{\epsilon}{3L}$
$\displaystyle\mathbb{P}(|\Delta_{3\ell}|>t_{3})$
$\displaystyle\leq\frac{\sqrt{m}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}}{t_{3}}=\frac{\epsilon}{3L}$

Therefore w.p. $1-\frac{\epsilon}{L}$, the following inequalities hold

$\displaystyle|\Delta_{1\ell}|$ $\displaystyle\leq
t_{1}=\sqrt{\frac{6L}{\epsilon}}\sqrt{\bar{L}_{m}+\bar{\alpha}^{2}}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}$
$\displaystyle|\Delta_{2\ell}|$ $\displaystyle\leq
t_{2}=\sqrt{\frac{3L}{\epsilon}}\bar{\sigma}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}$
$\displaystyle|\Delta_{3\ell}|$ $\displaystyle\leq
t_{3}=\frac{3L}{\epsilon}\sqrt{m}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}$

Finally recall $m=\frac{n}{L}$

∎

###  C.4 Main argument

######  Definition C.4 (Overall target and oracle).

$\hat{\theta}=\frac{1}{L}\sum_{\ell=1}^{L}\hat{\theta}_{\ell},\quad\bar{\theta}=\frac{1}{L}\sum_{\ell=1}^{L}\bar{\theta}_{\ell}$

######  Proposition C.5 (Oracle approximation).

Suppose the conditions of Proposition C.4 hold. Then w.p. $1-\epsilon$

$\frac{\sqrt{n}}{\sigma}|\hat{\theta}-\bar{\theta}|\leq\Delta=\frac{3L}{\epsilon\cdot\sigma}\left\\{(\sqrt{\bar{L}_{m}}+\bar{\alpha})\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}+\bar{\sigma}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}+\sqrt{n}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}\right\\}$

###### Proof.

I proceed in steps

  1. 1.

Decomposition

Write

$\displaystyle\sqrt{n}(\hat{\theta}-\bar{\theta})$
$\displaystyle=\frac{\sqrt{n}}{\sqrt{m}}\frac{1}{L}\sum_{\ell=1}^{L}\sqrt{m}(\hat{\theta}_{\ell}-\bar{\theta}_{\ell})$
$\displaystyle=\sqrt{L}\frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{3}\Delta_{j\ell}$

  2. 2.

Union bound

Define the events

$\mathcal{E}_{\ell}=\\{\forall j\in[3],\;|\Delta_{j\ell}|\leq
t_{j}\\},\quad\mathcal{E}=\cap_{\ell=1}^{L}\mathcal{E}_{\ell},\quad\mathcal{E}^{c}=\cup_{\ell=1}^{L}\mathcal{E}^{c}_{\ell}$

Hence by the union bound and Proposition C.4,

$\mathbb{P}(\mathcal{E}^{c})\leq\sum_{\ell=1}^{L}\mathbb{P}(\mathcal{E}^{c}_{\ell})\leq
L\frac{\epsilon}{L}=\epsilon$

  3. 3.

Collecting results

Therefore w.p. $1-\epsilon$,

$\displaystyle\sqrt{n}|\hat{\theta}-\bar{\theta}|$
$\displaystyle\leq\sqrt{L}\frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{3}|\Delta_{jk}|$
$\displaystyle\leq\sqrt{L}\frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{3}t_{j}$
$\displaystyle=\sqrt{L}\sum_{j=1}^{3}t_{j}$

Finally I simplify $\\{t_{j}\\}$. For $a,b>0$,
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$. Moreover, $3\geq\sqrt{6},\sqrt{3}$.
Finally, for $\epsilon\leq 1$,
$\frac{1}{\sqrt{\epsilon}}\leq\frac{1}{\epsilon}$. In summary

$\displaystyle t_{1}$
$\displaystyle\leq\frac{3\sqrt{L}}{\epsilon}(\sqrt{\bar{L}_{m}}+\bar{\alpha})\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}$
$\displaystyle t_{2}$
$\displaystyle\leq\frac{3\sqrt{L}}{\epsilon}\bar{\sigma}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}$
$\displaystyle t_{3}$
$\displaystyle\leq\frac{3\sqrt{L}}{\epsilon}\sqrt{n}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}$

∎

###### Proof of Theorem 4.1.

By Berry Esssen theorem, as in [24, Proof of Theorem 4.1, Step 3]

$\mathbb{P}\left(\frac{\sqrt{n}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right)-\Phi(z)\leq
c^{BE}\left(\frac{\eta}{\sigma}\right)^{3}n^{-\frac{1}{2}}+\frac{\Delta}{\sqrt{2\pi}}+\epsilon$

and

$\mathbb{P}\left(\frac{\sqrt{n}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right)-\Phi(z)\geq
c^{BE}\left(\frac{\eta}{\sigma}\right)^{3}n^{-\frac{1}{2}}-\frac{\Delta}{\sqrt{2\pi}}-\epsilon$

where $\Phi(z)$ is the standard Gaussian c.d.f. and $\Delta$ is defined in
Proposition C.5. ∎

###  C.5 Variance estimation

###### Proof of Proposition 4.1.

Write

$\displaystyle\sigma^{2}$
$\displaystyle=\mathbb{E}[m(W,\gamma_{0})+\alpha_{0}^{\min}(W)\\{Y-\gamma_{0}(W)\\}-\theta_{0}]^{2}$
$\displaystyle\leq
3\left(\mathbb{E}[m(W,\gamma_{0})]^{2}+\mathbb{E}[\alpha_{0}^{\min}(W)\\{Y-\gamma_{0}(W)\\}]^{2}+\theta_{0}^{2}\right)$

Then note

$\mathbb{E}[m(W,\gamma_{0})]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma_{0}(W)]^{2}$

and

$\mathbb{E}[\alpha_{0}^{\min}(W)\\{Y-\gamma_{0}(W)\\}]^{2}\leq\bar{\alpha}^{2}\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq\bar{\alpha}^{2}\bar{\sigma}^{2}$

∎

######  Definition C.5 (Shorter notation).

For $i\in I_{\ell}$, define

$\displaystyle\psi_{i}$
$\displaystyle=\psi(W_{i},\theta_{0},\gamma_{0},\alpha_{0})$
$\displaystyle\hat{\psi}_{i}$
$\displaystyle=\psi(W_{i},\hat{\theta},\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})$

######  Proposition C.6 (Foldwise second moment).

$\mathbb{E}_{\ell}[\hat{\psi}_{i}-\psi_{i}]^{2}\leq
4\left\\{[\hat{\theta}-\theta_{0}]^{2}+\sum_{j=4}^{6}\Delta_{j\ell}\right\\}$

where

$\displaystyle\Delta_{4\ell}$ $\displaystyle=\mathbb{E}_{\ell}[m(W,u)]^{2}$
$\displaystyle\Delta_{5\ell}$
$\displaystyle=\mathbb{E}_{\ell}[\hat{\alpha}_{\ell}(W)u(W)]^{2}$
$\displaystyle\Delta_{6\ell}$
$\displaystyle=\mathbb{E}_{\ell}[v(W)\\{Y-\gamma_{0}(W)\\}]^{2}$

###### Proof.

Write

$\displaystyle\psi_{i}-\hat{\psi}_{i}$
$\displaystyle=m(W_{i},\hat{\gamma}_{\ell})+\hat{\alpha}_{\ell}(W_{i})[Y_{i}-\hat{\gamma}_{\ell}(W_{i})]-\hat{\theta}-\left\\{m(W_{i},\gamma_{0})+\alpha_{0}(W_{i})[Y_{i}-\gamma_{0}(W_{i})]-\theta_{0}\right\\}$
$\displaystyle\quad\pm\hat{\alpha}_{\ell}[Y-\gamma_{0}(W_{i})]$
$\displaystyle=[\theta_{0}-\hat{\theta}]+m(W_{i},u)-\hat{\alpha}_{\ell}(W_{i})u(W_{i})+v(W_{i})[Y-\gamma_{0}(W_{i})]$

Hence

$[\psi_{i}-\hat{\psi}_{i}]^{2}\leq
4\left\\{[\theta_{0}-\hat{\theta}]^{2}+m(W_{i},u)^{2}+[\hat{\alpha}_{\ell}(W_{i})u(W_{i})]^{2}+[v(W_{i})\\{Y-\gamma_{0}(W_{i})\\}]^{2}\right\\}$

Finally take $\mathbb{E}_{\ell}[\cdot]$ of both sides. ∎

######  Proposition C.7 (Residuals).

Suppose

$\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq\bar{\sigma}^{2},\quad\mathbb{E}[m(W,\gamma)]^{2}\leq\bar{L}_{m}\mathbb{E}[\gamma(W)]^{2},\quad\|\hat{\alpha}_{\ell}\|_{\infty}\leq\bar{\alpha}^{\prime}$

Then w.p. $1-\frac{\epsilon^{\prime}}{2L}$,

$\displaystyle\Delta_{4\ell}$ $\displaystyle\leq
t_{4}=\frac{6L}{\epsilon^{\prime}}\bar{L}_{m}\mathcal{R}(\hat{\gamma}_{\ell})$
$\displaystyle\Delta_{5\ell}$ $\displaystyle\leq
t_{5}=\frac{6L}{\epsilon^{\prime}}(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell})$
$\displaystyle\Delta_{6\ell}$ $\displaystyle\leq
t_{6}=\frac{6L}{\epsilon^{\prime}}\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})$

###### Proof.

I proceed in steps analogous to Proposition C.4.

  1. 1.

Markov inequality

$\displaystyle\mathbb{P}(|\Delta_{4\ell}|>t_{4})$
$\displaystyle\leq\frac{\mathbb{E}[\Delta_{4\ell}]}{t_{4}}$
$\displaystyle\mathbb{P}(|\Delta_{5\ell}|>t_{5})$
$\displaystyle\leq\frac{\mathbb{E}[\Delta_{5\ell}]}{t_{5}}$
$\displaystyle\mathbb{P}(|\Delta_{6\ell}|>t_{6})$
$\displaystyle\leq\frac{\mathbb{E}[\Delta_{6\ell}]}{t_{6}}$

  2. 2.

Law of iterated expectations

$\displaystyle\mathbb{E}[\Delta_{4\ell}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\Delta_{4\ell}|I^{c}_{\ell}]]$
$\displaystyle\mathbb{E}[\Delta_{5\ell}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\Delta_{5\ell}|I^{c}_{\ell}]]$
$\displaystyle\mathbb{E}[\Delta_{6\ell}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\Delta_{6\ell}|I^{c}_{\ell}]]$

  3. 3.

Bounding conditional moments

Conditional on $I_{\ell}^{c}$, $(u,v)$ are nonrandom. Moreover, observations
within fold $I_{\ell}$ are independent. Hence

$\mathbb{E}[\Delta_{4\ell}|I^{c}_{\ell}]=\mathbb{E}[\\{m(W,u)\\}^{2}|I^{c}_{\ell}]\leq\bar{L}_{m}\mathcal{R}(\hat{\gamma}_{\ell})$

Similarly

$\mathbb{E}[\Delta_{5\ell}|I^{c}_{\ell}]=\mathbb{E}[\\{\hat{\alpha}_{\ell}(W)u(W)\\}^{2}|I^{c}_{\ell}]\leq(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell})$

Finally

$\displaystyle\mathbb{E}[\Delta_{6\ell}|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}[\\{v(W)[Y-\gamma_{0}(W)]\\}^{2}|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}[v(W)^{2}\mathbb{E}[\\{Y-\gamma_{0}(W)\\}^{2}|W,I^{c}_{\ell}]|I^{c}_{\ell}]$
$\displaystyle\leq\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})$

  4. 4.

Collecting results

$\displaystyle\mathbb{P}(|\Delta_{4\ell}|>t_{4})$
$\displaystyle\leq\frac{\bar{L}_{m}\mathcal{R}(\hat{\gamma}_{\ell})}{t_{4}}=\frac{\epsilon^{\prime}}{6L}$
$\displaystyle\mathbb{P}(|\Delta_{5\ell}|>t_{5})$
$\displaystyle\leq\frac{(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell})}{t_{5}}=\frac{\epsilon^{\prime}}{6L}$
$\displaystyle\mathbb{P}(|\Delta_{6\ell}|>t_{6})$
$\displaystyle\leq\frac{\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})}{t_{6}}=\frac{\epsilon^{\prime}}{6L}$

Therefore w.p. $1-\frac{\epsilon^{\prime}}{2L}$, the following inequalities
hold

$\displaystyle|\Delta_{4\ell}|$ $\displaystyle\leq
t_{4}=\frac{6L}{\epsilon^{\prime}}\bar{L}_{m}\mathcal{R}(\hat{\gamma}_{\ell})$
$\displaystyle|\Delta_{5\ell}|$ $\displaystyle\leq
t_{5}=\frac{6L}{\epsilon^{\prime}}(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell})$
$\displaystyle|\Delta_{6\ell}|$ $\displaystyle\leq
t_{6}=\frac{6L}{\epsilon^{\prime}}\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})$

∎

######  Proposition C.8 (Oracle approximation).

Suppose the conditions of Proposition C.7 hold. Then w.p.
$1-\frac{\epsilon^{\prime}}{2}$

$\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}\leq\Delta^{\prime}=4\\{\hat{\theta}-\theta_{0}\\}^{2}+\frac{24L}{\epsilon^{\prime}}\\{[\bar{L}_{m}+(\bar{\alpha}^{\prime})^{2}]\mathcal{R}(\hat{\gamma}_{\ell})+\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})\\}$

###### Proof.

I proceed in steps analogous to Proposition C.5

  1. 1.

Decomposition

By Proposition C.6

$\displaystyle\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}$
$\displaystyle=\frac{1}{L}\sum_{\ell=1}^{L}\mathbb{E}_{\ell}[\hat{\psi}_{i}-\psi_{i}]^{2}$
$\displaystyle\leq
4[\hat{\theta}-\theta_{0}]^{2}+\frac{4}{L}\sum_{\ell=1}^{L}\sum_{j=4}^{6}\Delta_{j\ell}$

  2. 2.

Union bound

Define the events

$\mathcal{E}^{\prime}_{\ell}=\\{\forall j\in\\{4,5,6\\},\;|\Delta_{j\ell}|\leq
t_{j}\\},\quad\mathcal{E}^{\prime}=\cap_{\ell=1}^{L}\mathcal{E}^{\prime}_{\ell},\quad(\mathcal{E}^{\prime})^{c}=\cup_{\ell=1}^{L}(\mathcal{E}_{\ell}^{\prime})^{c}$

Hence by the union bound and Proposition C.7,

$\mathbb{P}((\mathcal{E}^{\prime})^{c})\leq\sum_{\ell=1}^{L}\mathbb{P}((\mathcal{E}_{\ell}^{\prime})^{c})\leq
L\frac{\epsilon^{\prime}}{2L}=\frac{\epsilon^{\prime}}{2L}$

  3. 3.

Collecting results

Therefore w.p. $1-\frac{\epsilon^{\prime}}{2}$,

$\displaystyle\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}$ $\displaystyle\leq
4[\hat{\theta}-\theta_{0}]^{2}+\frac{4}{L}\sum_{\ell=1}^{L}\sum_{j=4}^{6}|\Delta_{j\ell}|$
$\displaystyle\leq
4[\hat{\theta}-\theta_{0}]^{2}+\frac{4}{L}\sum_{\ell=1}^{L}\sum_{j=4}^{6}t_{j}$
$\displaystyle=4[\hat{\theta}-\theta_{0}]^{2}+4\sum_{j=4}^{6}t_{j}$

∎

######  Proposition C.9 (Markov inequality).

Suppose $\mathbb{E}[\psi_{0}(W)]^{4}<\infty$. Then w.p.
$1-\frac{\epsilon^{\prime}}{2}$

$|\mathbb{E}_{n}[\psi_{i}]^{2}-\sigma^{2}|\leq\Delta^{\prime\prime}=\sqrt{\frac{2}{\epsilon^{\prime}}}\frac{\sqrt{\mathbb{E}[\psi_{0}(W)]^{4}}}{\sqrt{n}}$

###### Proof.

Let

$Z_{i}=\psi_{i}^{2},\quad\bar{Z}=\mathbb{E}_{n}[Z_{i}],\quad\mathbb{E}[Z]=\sigma^{2}$

By Markov inequality

$\mathbb{P}(|\bar{Z}-\mathbb{E}[Z]|>t)\leq\frac{\mathbb{V}[\bar{Z}]}{t^{2}}=\frac{\epsilon^{\prime}}{2}$

Note that

$\mathbb{V}[\bar{Z}]=\frac{\mathbb{V}(Z)}{n}=\frac{\mathbb{E}[\psi_{0}(W)^{2}]^{2}}{n}=\frac{\mathbb{E}[\psi_{0}(W)]^{4}}{n}$

Solving,

$\frac{\mathbb{E}[\psi_{0}(W)]^{4}}{nt^{2}}=\frac{\epsilon^{\prime}}{2}\iff
t=\sqrt{\frac{2}{\epsilon^{\prime}}}\frac{\sqrt{\mathbb{E}[\psi_{0}(W)]^{4}}}{\sqrt{n}}$

∎

###### Proof of Theorem 4.2.

I proceed in steps.

  1. 1.

Decomposition of variance estimator

Write

$\hat{\sigma}^{2}=\mathbb{E}_{n}[\hat{\psi}_{i}]^{2}=\mathbb{E}_{n}[\\{\hat{\psi}_{i}-\psi_{i}\\}+\psi_{i}]^{2}=\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}+2\mathbb{E}_{n}[\\{\hat{\psi}_{i}-\psi_{i}\\}\psi_{i}]+\mathbb{E}_{n}[\psi_{i}]^{2}$

Hence

$\hat{\sigma}^{2}-\mathbb{E}_{n}[\psi_{i}]^{2}=\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}+2\mathbb{E}_{n}[\\{\hat{\psi}_{i}-\psi_{i}\\}\psi_{i}]$

  2. 2.

Decomposition of difference

Next write

$\hat{\sigma}^{2}-\sigma^{2}=\\{\hat{\sigma}^{2}-\mathbb{E}_{n}[\psi_{i}]^{2}\\}+\\{\mathbb{E}_{n}[\psi_{i}]^{2}-\sigma^{2}\\}$

Focusing on the former term

$\hat{\sigma}^{2}-\mathbb{E}_{n}[\psi_{i}]^{2}=\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}+2\mathbb{E}_{n}[\\{\hat{\psi}_{i}-\psi_{i}\\}\psi_{i}]$

Moreover

$\displaystyle\mathbb{E}_{n}[\\{\hat{\psi}_{i}-\psi_{i}\\}\psi_{i}]$
$\displaystyle\leq\sqrt{\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}}\sqrt{\mathbb{E}_{n}[\psi_{i}]^{2}}$
$\displaystyle\leq\sqrt{\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}}\sqrt{|\mathbb{E}_{n}[\psi_{i}]^{2}-\sigma^{2}|+\sigma^{2}}$
$\displaystyle\leq\sqrt{\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}}\left(\sqrt{|\mathbb{E}_{n}[\psi_{i}]^{2}-\sigma^{2}|}+\sigma\right)$

  3. 3.

High probability events

From the previous step, we see that to control
$|\hat{\sigma}^{2}-\sigma^{2}|$, it is sufficient to control two expressions:
$\mathbb{E}_{n}[\hat{\psi}_{i}-\psi_{i}]^{2}$ and
$|\mathbb{E}_{n}[\psi_{i}]^{2}-\sigma^{2}|$. These are controlled in
Propositions C.8 and C.9, respectively. Therefore w.p. $1-\epsilon^{\prime}$,

$|\hat{\sigma}^{2}-\sigma^{2}|\leq\left\\{\Delta^{\prime}+2\sqrt{\Delta^{\prime}}(\sqrt{\Delta^{\prime\prime}}+\sigma)\right\\}+\Delta^{\prime\prime}$

∎

###  C.6 Corollary

###### Proof of Corollary 4.1.

Immediately from $\Delta$ in Theorem 4.1,
$\hat{\theta}\overset{p}{\rightarrow}\theta_{0}$ and

$\lim_{n\rightarrow\infty}\mathbb{P}\left(\theta_{0}\in\left[\hat{\theta}\pm\frac{\sigma}{\sqrt{n}}\right]\right)=1-a$

For the desired result, it is sufficient that
$\hat{\sigma}^{2}\overset{p}{\rightarrow}\sigma^{2}$, which follows from
$\Delta^{\prime}$ and $\Delta^{\prime\prime}$ in Theorem 4.2. ∎

##  Appendix D Validity of bias correction

###  D.1 Preliminaries

######  Proposition D.1 (First order conditions).

Define $g=M^{*}\mu$ and $\hat{g}=M^{*}\hat{\mu}$. Then

$T\alpha_{0}^{\min}=g,\quad\alpha_{\lambda}=(T+\lambda)^{-1}g,\quad\hat{\alpha}=(\hat{T}+\lambda)^{-1}\hat{g}$

###### Proof.

Take derivatives of $\mathcal{L}$, $\mathcal{L}_{\lambda}$, and
$\mathcal{L}^{n}_{\lambda}$ ∎

######  Proposition D.2 (Relation of norms).

$\mathcal{R}(\alpha)=\mathbb{E}[\alpha(W)-\alpha_{0}^{\min}(W)]^{2}=\|T^{\frac{1}{2}}(\alpha-\alpha_{0}^{\min})\|^{2}_{\mathcal{H}}$

###### Proof.

[15, Proposition 1.iii], using the fact that mean square error equals excess
risk. ∎

######  Proposition D.3 (Concentration).

Let $(\Omega,\mathcal{F},\rho)$ be a probability space. Let $\xi$ be a random
variable on $\Omega$ taking value in a real separable Hilbert space
$\mathcal{K}$. Assume there exists $(a,b)>0$ s.t.

$\|\xi(\omega)\|_{\mathcal{K}}\leq\frac{a}{2},\quad\mathbb{E}\|\xi\|^{2}_{\mathcal{K}}\leq
b^{2}$

Then for all $n\in\mathbb{N}$ and $\eta\in(0,1)$,

$\mathbb{P}_{\\{\omega_{i}\\}\sim\rho^{n}}\left(\left\|\frac{1}{n}\sum_{i=1}^{n}\xi(\omega_{i})-\mathbb{E}[\xi]\right\|_{\mathcal{K}}\leq
2\ln(2/\eta)\left[\frac{a}{n}+\frac{b}{\sqrt{n}}\right]\right)\geq\frac{1}{\eta}$

###### Proof.

A simplification of [15, Proposition 2] ∎

###  D.2 Learning theory quantities

###### Proof of Proposition 5.1.

Write

$\mathbb{E}[Y-\gamma_{0}(W)]^{2}\leq
2\mathbb{E}[Y]^{2}+2\mathbb{E}[\gamma_{0}(W)]^{2}$

Since $\gamma_{0}\in\mathcal{H}$,

$|\gamma_{0}(w)|=|\langle\gamma_{0},\phi(w)\rangle_{\mathcal{H}}|\leq\sqrt{\kappa}\|\gamma_{0}\|_{\mathcal{H}}$

$\gamma\in\mathcal{H}$ implies $\alpha_{0}^{\min}\in\mathcal{H}$, so

$|\alpha^{\min}_{0}(w)|=|\langle\alpha^{\min}_{0},\phi(w)\rangle_{\mathcal{H}}|\leq\sqrt{\kappa}\|\alpha^{\min}_{0}\|_{\mathcal{H}}$

and likewise

$|\hat{\alpha}(w)|=|\langle\hat{\alpha},\phi(w)\rangle_{\mathcal{H}}|\leq\sqrt{\kappa}\|\hat{\alpha}\|_{\mathcal{H}}$

Finally, I bound $\|\hat{\alpha}\|_{\mathcal{H}}$. By identical arguments to
Proposition 3.1,

$\hat{\alpha}=\operatorname*{\arg\\!\min}_{\alpha\in\mathcal{H}}\mathcal{R}^{n}_{\lambda}(\alpha),\quad\mathcal{R}^{n}_{\lambda}(\alpha)=\mathbb{E}_{n}[\alpha^{\min}_{0}(W)-\alpha(W)]^{2}+\lambda\|\mathcal{\alpha}\|^{2}_{\mathcal{H}}$

Hence

$\lambda\|\hat{\alpha}\|^{2}_{\mathcal{H}}\leq\mathcal{R}^{n}_{\lambda}(\hat{\alpha})\leq\mathcal{R}^{n}_{\lambda}(0)=\mathbb{E}_{n}[\alpha_{0}^{\min}(W)]^{2}\leq\kappa\|\alpha^{\min}_{0}\|^{2}_{\mathcal{H}}$

Therefore

$\|\hat{\alpha}\|_{\mathcal{H}}\leq\frac{\sqrt{\kappa}\|\alpha^{\min}_{0}\|_{\mathcal{H}}}{\sqrt{\lambda}},\quad|\hat{\alpha}(w)|\leq\frac{\kappa\|\alpha^{\min}_{0}\|_{\mathcal{H}}}{\sqrt{\lambda}}$

∎

###### Proof of Proposition 5.2.

For the first result, write $f=\sum_{k=1}^{\infty}a_{k}\varphi_{k}$ and appeal
to [15, Remark 2]. The second result follows from Proposition 2.4. ∎

###### Proof of Proposition 5.3.

The result follows from [15, Remark 2]. ∎

###### Proof of Theorem 5.1.

Immediate from [15, Theorems 1 and 2]. ∎

######  Definition D.1 (Learning theory quantities).

Define

$\displaystyle\mathcal{A}(\lambda)$
$\displaystyle=\mathcal{R}(\alpha_{\lambda})$
$\displaystyle\mathcal{B}(\lambda)$
$\displaystyle=\|\alpha_{\lambda}-\alpha_{0}^{\min}\|^{2}_{\mathcal{H}}$
$\displaystyle\mathcal{N}(\lambda)$ $\displaystyle=Tr((T+\lambda)^{-1}T)$

######  Proposition D.4 (Bounds on learning theory quantities).

Under Assumption 5.3

$\mathcal{A}(\lambda)\leq\lambda^{c}R,\quad\mathcal{B}(\lambda)\leq\lambda^{c-1}R,\quad
R=\|T^{\frac{1-c}{2}}\gamma_{0}\|^{2}_{\mathcal{H}}$

Under Assumption 5.4

$\mathcal{N}(\lambda)=Tr((T+\lambda)^{-1}T)\leq\begin{cases}\beta^{\frac{1}{b}}\frac{\pi/b}{\sin(\pi/b)}\lambda^{-\frac{1}{b}}&\text{
if }b<\infty\\\ J&\text{ if }b=\infty\end{cases}$

###### Proof.

See [15, Proposition 3] for $\mathcal{A}(\lambda)$ and $\mathcal{B}(\lambda)$.
See [89, Section 1] for $\mathcal{N}(\lambda)$. ∎

###  D.3 High probability events

In preparation for the main argument, I prove high probability events by
concentration, appealing to Proposition D.3.

######  Definition D.2 (High probability events).

Define

$\displaystyle\mathcal{E}_{1}$
$\displaystyle=\left\\{\|(T+\lambda)^{-1}(\hat{T}-T)\|_{\mathcal{L}_{2}(\mathcal{H},\mathcal{H})}\leq
2\ln(6/\eta)\left[\frac{2\kappa}{\lambda
n}+\sqrt{\frac{\kappa\mathcal{N}(\lambda)}{\lambda n}}\right]\right\\}$
$\displaystyle\mathcal{E}_{2}$
$\displaystyle=\left\\{\|(T-\hat{T})(\alpha_{\lambda}-\alpha_{0}^{\min})\|_{\mathcal{H}}\leq
2\ln(6/\eta)\left[\frac{2\kappa\sqrt{\mathcal{B}(\lambda)}}{n}+\sqrt{\frac{\kappa\mathcal{A}(\lambda)}{n}}\right]\right\\}$
$\displaystyle\mathcal{E}_{3}$
$\displaystyle=\left\\{\|(T+\lambda)^{-\frac{1}{2}}(\hat{g}-\hat{T}\alpha_{0}^{\min})\|_{\mathcal{H}}\leq
2\ln(6/\eta)\left[\frac{1}{n}\sqrt{\Gamma^{2}\frac{\kappa}{\lambda}}+\sqrt{\frac{\Sigma^{2}\mathcal{N}(\lambda)}{n}}\right]\right\\}$

where

$\Sigma=\|M\|_{op}+\sqrt{\kappa}\|\alpha_{0}^{\min}\|_{\mathcal{H}},\quad\Gamma=2\Sigma$

I design $\mathcal{E}_{3}$ to resemble [15, eq. 48].

######  Proposition D.5 (High probability events).

Suppose Assumptions 2.1 and 2.2 as well Assumptions 5.1 and 5.2 hold. Then

$\mathbb{P}(\mathcal{E}_{j}^{c})\leq\frac{\eta}{3},\quad j\in\\{1,2,3\\}$

###### Proof.

The argument for $\mathcal{E}_{1}$ immediately precedes [15, eq. 41]. The
argument for $\mathcal{E}_{2}$ is identical to [15, eq. 43]. I verify
$\mathcal{E}_{3}$ appealing to Proposition D.3. Define

$\xi_{i}=(T+\lambda)^{-\frac{1}{2}}\\{M^{*}\phi(w_{i})-[\phi(w_{i})\otimes\phi(w_{i})]\alpha_{0}^{\min}\\}$

Note that

$\mathbb{E}[\xi_{i}]=(T+\lambda)^{-\frac{1}{2}}\\{g-T\alpha_{0}^{\min}\\}=0$

Towards concentration, I analyze $\|\xi\|_{\mathcal{H}}$ and
$\mathbb{E}\|\xi\|^{2}_{\mathcal{H}}$

  1. 1.

Bound on $\|\xi\|_{\mathcal{H}}$

Write

$\displaystyle\|\xi_{i}\|_{\mathcal{H}}$
$\displaystyle\leq\|(T+\lambda)^{-\frac{1}{2}}\|_{op}\|M^{*}\phi(w_{i})-[\phi(w_{i})\otimes\phi(w_{i})]\alpha_{0}^{\min}\|_{\mathcal{H}}$
$\displaystyle\leq\frac{1}{\sqrt{\lambda}}(\sqrt{\kappa}\|M\|_{op}+\kappa\|\alpha_{0}^{\min}\|_{\mathcal{H}})$
$\displaystyle=\frac{a}{2}$

  2. 2.

Bound on $\mathbb{E}\|\xi\|^{2}_{\mathcal{H}}$

Write

$\xi_{i}=(T+\lambda)^{-\frac{1}{2}}Q\phi(w_{i}),\quad
Q=\\{M^{*}-\alpha_{0}^{\min}(w_{i})I\\}$

Then by properties of trace,

$\displaystyle\|\xi_{i}\|^{2}_{\mathcal{H}}$
$\displaystyle=\langle(T+\lambda)^{-1}Q\phi(w_{i}),Q\phi(w_{i})\rangle_{\mathcal{H}}$
$\displaystyle=Tr(Q^{*}(T+\lambda)^{-1}Q[\phi(w_{i})\otimes\phi(w_{i})])$
$\displaystyle\leq\|Q\|_{op}Tr((T+\lambda)^{-1}Q[\phi(w_{i})\otimes\phi(w_{i})])$
$\displaystyle=\|Q\|_{op}Tr(Q[\phi(w_{i})\otimes\phi(w_{i})](T+\lambda)^{-1})$
$\displaystyle\leq\|Q\|^{2}_{op}Tr([\phi(w_{i})\otimes\phi(w_{i})](T+\lambda)^{-1})$
$\displaystyle=\|Q\|^{2}_{op}Tr((T+\lambda)^{-1}[\phi(w_{i})\otimes\phi(w_{i})])$

Clearly

$\|Q\|_{op}\leq\|M\|_{op}+\sqrt{\kappa}\|\alpha_{0}^{\min}\|_{\mathcal{H}}$

Hence

$\mathbb{E}\|\xi\|^{2}_{\mathcal{H}}\leq\left\\{\|M\|_{op}+\sqrt{\kappa}\|\alpha_{0}^{\min}\|_{\mathcal{H}}\right\\}^{2}\cdot\mathcal{N}(\lambda)=b^{2}$

  3. 3.

Concentration

In summary

$a=\frac{2}{\sqrt{\lambda}}(\sqrt{\kappa}\|M\|_{op}+\kappa\|\alpha_{0}^{\min}\|_{\mathcal{H}}),\quad
b=\left\\{\|M\|_{op}+\sqrt{\kappa}\|\alpha_{0}^{\min}\|_{\mathcal{H}}\right\\}\sqrt{\mathcal{N}(\lambda)}$

Therefore w.p. $1-\eta/3$

$\displaystyle\left\|(T+\lambda)^{-\frac{1}{2}}(\hat{g}-\hat{T}\alpha_{0}^{\min})\right\|_{\mathcal{H}}$
$\displaystyle\leq 2\ln(6/\eta)\left(\frac{a}{n}+\frac{b}{\sqrt{n}}\right)$
$\displaystyle=2\ln(6/\eta)\left(\frac{2(\sqrt{\kappa}\|M\|_{op}+\kappa\|\alpha_{0}^{\min}\|_{\mathcal{H}})}{n\sqrt{\lambda}}+\frac{\left\\{\|M\|_{op}+\sqrt{\kappa}\|\alpha_{0}^{\min}\|_{\mathcal{H}}\right\\}\sqrt{\mathcal{N}(\lambda)}}{\sqrt{n}}\right)$
$\displaystyle=2\ln(6/\eta)\left(\frac{1}{n}\sqrt{\Gamma^{2}\frac{\kappa}{\lambda}}+\sqrt{\frac{\Sigma^{2}\mathcal{N}(\lambda)}{n}}\right)$

∎

###  D.4 Main argument

######  Proposition D.6 (Abstract rate).

Suppose Assumptions 2.1 and 2.2 as well Assumptions 5.1 and 5.2 hold. If

$C_{\eta}=4\cdot 96\ln^{2}(6/\eta),\quad
n\geq\frac{2C_{\eta}\kappa\mathcal{N}(\lambda)}{\lambda},\quad\lambda\leq\|T\|_{op},\quad\Sigma=\|M\|_{op}+\sqrt{\kappa}\|\alpha_{0}^{\min}\|_{\mathcal{H}}$

then w.p. $1-\eta$

$\mathcal{R}(\hat{\alpha})\leq
C_{\eta}\left(\mathcal{A}(\lambda)+\frac{\kappa^{2}\mathcal{B}(\lambda)}{n^{2}\lambda}+\frac{\kappa\mathcal{A}(\lambda)}{n\lambda}+\frac{\kappa\Sigma^{2}}{n\lambda}+\frac{\Sigma^{2}\mathcal{N}(\lambda)}{n}\right)$

###### Proof.

I proceed in steps, following the proof structure of [15, Theorem 4].

  1. 1.

Decomposition

By [15, eq. 36],

$\mathcal{R}(\hat{\alpha})\leq
3\left\\{\mathcal{A}(\lambda)+\mathcal{S}_{1}(\lambda,\\{w_{i}\\})+\mathcal{S}_{2}(\lambda,\\{w_{i}\\})\right\\}$

where

$\displaystyle\mathcal{S}_{1}(\lambda,\\{w_{i}\\})$
$\displaystyle=\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}(\hat{g}-\hat{T}\alpha_{0}^{\min})\right\|^{2}_{\mathcal{H}}$
$\displaystyle\mathcal{S}_{2}(\lambda,\\{w_{i}\\})$
$\displaystyle=\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}(T-\hat{T})(\alpha_{\lambda}-\alpha_{0}^{\min})\right\|^{2}_{\mathcal{H}}$

  2. 2.

Bound on $\mathcal{S}_{2}(\lambda,\\{w_{i}\\})$

Write

$\mathcal{S}_{2}(\lambda,\\{w_{i}\\})\leq\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}\right\|^{2}_{op}\left\|(T-\hat{T})(\alpha_{\lambda}-\alpha_{0}^{\min})\right\|^{2}_{\mathcal{H}}$

    1. (a)

Bound on $\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}\right\|_{op}$

By [15, eq. 39], under $\mathcal{E}_{1}$

$\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}\right\|_{op}\leq\frac{1}{\sqrt{\lambda}}$

    2. (b)

Bound on
$\left\|(T-\hat{T})(\alpha_{\lambda}-\alpha_{0}^{\min})\right\|_{\mathcal{H}}$

Under $\mathcal{E}_{2}$

$\left\|(T-\hat{T})(\alpha_{\lambda}-\alpha_{0}^{\min})\right\|_{\mathcal{H}}\leq
2\ln(6/\eta)\left(\frac{2\kappa\sqrt{\mathcal{B}(\lambda)}}{n}+\sqrt{\frac{\kappa\mathcal{A}(\lambda)}{n}}\right)$

In summary, under $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$

$\displaystyle\mathcal{S}_{2}(\lambda,\\{w_{i}\\})$
$\displaystyle\leq\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}\right\|^{2}_{op}\left\|(T-\hat{T})(\alpha_{\lambda}-\alpha_{0}^{\min})\right\|^{2}_{\mathcal{H}}$
$\displaystyle\leq\frac{1}{\lambda}\cdot\\{2\ln(6/\eta)\\}^{2}\cdot
2\left(\left\\{\frac{2\kappa\sqrt{\mathcal{B}(\lambda)}}{n}\right\\}^{2}+\left\\{\sqrt{\frac{\kappa\mathcal{A}(\lambda)}{n}}\right\\}^{2}\right)$
$\displaystyle=8\ln^{2}(6/\eta)\left(\frac{4\kappa^{2}\mathcal{B}(\lambda)}{n^{2}\lambda}+\frac{\kappa\mathcal{A}(\lambda)}{n\lambda}\right)$

  3. 3.

Bound on $\mathcal{S}_{1}(\lambda,\\{w_{i}\\})$

Write

$\mathcal{S}_{1}(\lambda,\\{w_{i}\\})\leq\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}(T+\lambda)^{\frac{1}{2}}\right\|^{2}_{op}\left\|(T+\lambda)^{-\frac{1}{2}}(\hat{g}-\hat{T}\alpha_{0}^{\min})\right\|^{2}_{\mathcal{H}}$

    1. (a)

Bound on
$\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}(T+\lambda)^{\frac{1}{2}}\right\|_{op}$

By [15, eq. 47], under $\mathcal{E}_{1}$

$\left\|T^{\frac{1}{2}}(\hat{T}+\lambda)^{-1}(T+\lambda)^{\frac{1}{2}}\right\|_{op}\leq
2$

    2. (b)

Bound on
$\left\|(T+\lambda)^{-\frac{1}{2}}(\hat{g}-\hat{T}\alpha_{0}^{\min})\right\|_{\mathcal{H}}$

Under $\mathcal{E}_{3}$

$\|(T+\lambda)^{-\frac{1}{2}}(\hat{g}-\hat{T}\alpha_{0}^{\min})\|_{\mathcal{H}}\leq
2\ln(6/\eta)\left[\frac{1}{n}\sqrt{\Gamma^{2}\frac{\kappa}{\lambda}}+\sqrt{\frac{\Sigma^{2}\mathcal{N}(\lambda)}{n}}\right]$

Therefore by [15, eq. 49], under $\mathcal{E}_{1}$ and $\mathcal{E}_{3}$

$\mathcal{S}_{1}(\lambda,\\{w_{i}\\})\leq
32\ln^{2}(6/\eta)\left(\frac{\kappa\Gamma^{2}}{n^{2}\lambda}+\frac{\Sigma^{2}\mathcal{N}(\lambda)}{n}\right)$

∎

###### Proof of Theorem 5.2.

Finally, I combine the abstract rate in Proposition D.6 with the bounds of
Proposition D.4, following [89, Section 2]. The absolute constant depends only
on $(R,\kappa,\Sigma,\beta,b,c)$. Note that $\Sigma$ introduces dependence on
$(\|M\|_{op},\|\alpha_{0}^{\min}\|_{\mathcal{H}})$. ∎

###### Proof of Corollary 5.1.

I verify the conditions of Corollary 4.1 appealing to Theorems 5.1 and 5.2. In
particular, by the symmetry of Theorems 5.1 and 5.2, I must show

$(\sqrt{\bar{L}_{m}}+\bar{\alpha}+\bar{\alpha}^{\prime}+\bar{\sigma})\sqrt{r_{n}}\rightarrow
0,\quad\sqrt{n}\cdot r_{n}\rightarrow 0$

By Proposition 2.1, $\sqrt{\bar{L}_{m}}<\infty$ is a constant. By Proposition
5.1, $\bar{\alpha}<\infty$ and $\bar{\sigma}<\infty$ are also constants.
However, $\bar{\alpha}^{\prime}$ scales as $\lambda^{-\frac{1}{2}}$. Therefore
the remaining conditions to verify are

$\lambda^{-\frac{1}{2}}\sqrt{r_{n}}\rightarrow 0,\quad\sqrt{n}\cdot
r_{n}\rightarrow 0$

I consider each case

  1. 1.

$b=\infty$.

    1. (a)

$n^{\frac{1}{4}}\cdot n^{-\frac{1}{2}}\rightarrow 0$

    2. (b)

$\sqrt{n}\cdot n^{-1}\rightarrow 0$

  2. 2.

$b\in(1,\infty),\;c\in(1,2]$.

    1. (a)

$n^{\frac{1}{2}\frac{b}{bc+1}}\cdot n^{-\frac{1}{2}\frac{bc}{bc+1}}\rightarrow
0\iff c>1$

    2. (b)

$\sqrt{n}\cdot n^{-\frac{bc}{bc+1}}\rightarrow 0\iff bc>1$

  3. 3.

$b\in(1,\infty),\;c=1$.

    1. (a)

$\ln^{-\frac{1}{2}\frac{b}{b+1}}(n)n^{\frac{1}{2}\frac{b}{b+1}}\cdot\ln^{\frac{1}{2}\frac{b}{b+1}}(n)n^{-\frac{1}{2}\frac{b}{b+1}}=1$

    2. (b)

$\sqrt{n}\cdot\ln^{\frac{b}{b+1}}(n)\cdot n^{-\frac{b}{b+1}}\rightarrow 0\iff
b>1$

∎

###### Proof of Corollary 5.2.

Since $\|\alpha_{0}^{\min}\|_{\infty}\leq\bar{\alpha}$, the trimming can only
possibly improve mean square error, and the rates in Theorem 5.2 continue to
hold for the trimmed estimator $\tilde{\alpha}$ defined in Algorithm 5.1.

As in Corollary 5.1, I must show

$(\sqrt{\bar{L}_{m}}+\bar{\alpha}+\bar{\alpha}^{\prime}+\bar{\sigma})\sqrt{r_{n}}\rightarrow
0,\quad\sqrt{n}\cdot r_{n}\rightarrow 0$

By Proposition 2.1, $\sqrt{\bar{L}_{m}}<\infty$ is a constant. By Proposition
5.1, $\bar{\alpha}<\infty$ and $\bar{\sigma}<\infty$ are also constants.
Moreover, trimming implies that $\bar{\alpha}^{\prime}=\bar{\alpha}<0$ is a
constant. Therefore the remaining condition to verify is

$\sqrt{n}\cdot r_{n}\rightarrow 0$

In the proof of Corollary 5.1, I verify this condition for across regimes. ∎

##  Appendix E Tuning

###  E.1 Ridge penalty

I present a tuning procedure based on cross validation for the ridge penalty
$\lambda$ of the kernel ridge Riesz representer estimated in Algorithm 3.2.
The cross validation exploits the sample splitting in Algorithm 3.1. The
procedure finds a cross validated value $\lambda^{*}\in\Lambda$, where
$\Lambda\subset\mathbb{R}$ is a grid of possible values.

Recall that $\hat{\alpha}_{\ell}$ is the kernel ridge Riesz representer
estimated using observations in $I^{c}_{\ell}$. By construction,
$\hat{\alpha}_{\ell}$ depends on $\lambda$ via Algorithm 3.2. The cross
validation loss arises from the definition of the empirical loss
$\mathcal{L}^{n}_{\lambda}(\alpha)$, dropping the ridge term and setting
$\alpha=\hat{\alpha}_{\ell}$ for each observation $i\in I_{\ell}$.

######  Algorithm E.1 (Cross validation).

Partition the sample into folds $\\{I_{\ell}\\}_{\ell=1:L}$. Denote by
$I_{\ell}^{c}$ observations not in fold $I_{\ell}$.

  1. 1.

For each possible value $\lambda\in\Lambda$ and for each fold $\ell$, estimate
$\hat{\alpha}_{\ell}$ from observations in $I_{\ell}^{c}$ according to
Algorithm 3.2

  2. 2.

Set $\lambda^{*}$ as

$\lambda^{*}\in\operatorname*{\arg\\!\min}_{\lambda\in\Lambda}\mathcal{L}(\lambda),\quad\mathcal{L}(\lambda)=\frac{1}{n}\sum_{\ell=1}^{L}\sum_{i\in
I_{\ell}}\left\\{-2m(W_{i},\hat{\alpha}_{\ell})+\hat{\alpha}_{\ell}(W_{i})^{2}\right\\}$

###  E.2 Kernel

In principle, I could instead use cross validation to tune kernel
hyperparameters in the same way that I use cross validation to tune ridge
penalties. However, given the choice of product kernel, this approach becomes
impractical in high dimensions. Therefore I rely on heuristics to set kernel
hyperparameters.