Optimally tackling covariate shift
in RKHS-based nonparametric regression

Cong Ma$\diamond$, Reese Pathak†, and Martin J. Wainwright†, ‡
---
$\diamond$ Department of Statistics, University of Chicago
† Department of Electrical Engineering and Computer Sciences, UC Berkeley
‡ Department of Statistics, UC Berkeley
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

We study the covariate shift problem in the context of nonparametric
regression over a reproducing kernel Hilbert space (RKHS). We focus on two
natural families of covariate shift problems defined using the likelihood
ratios between the source and target distributions. When the likelihood ratios
are uniformly bounded, we prove that the kernel ridge regression (KRR)
estimator with a carefully chosen regularization parameter is minimax rate-
optimal (up to a log factor) for a large family of RKHSs with regular kernel
eigenvalues. Interestingly, KRR does not require full knowledge of likelihood
ratios apart from an upper bound on them. In striking contrast to the standard
statistical setting without covariate shift, we also demonstrate that a naïve
estimator, which minimizes the empirical risk over the function class, is
strictly sub-optimal under covariate shift as compared to KRR. We then address
the larger class of covariate shift problems where likelihood ratio is
possibly unbounded yet has a finite second moment. Here, we propose a
reweighted KRR estimator that weights samples based on a careful truncation of
the likelihood ratios. Again, we are able to show that this estimator is
minimax rate-optimal, up to logarithmic factors.

##  1 Introduction

A widely adopted assumption in supervised learning [21, 6] is that the
training and test data are sampled from the same distribution. Such a no-
distribution-shift assumption, however, is frequently violated in practice.
For instance, in medical image analysis [5, 9], distribution mismatch is
widespread across the hospitals due to inconsistency in medical equipment,
scanning protocols, subject populations, etc. As another example, in natural
language processing [7], the training data are often collected from domains
with abundant labels (e.g., Wall Street Journal), while the test data may well
arise from a different domain (e.g., arXiv which is mainly composed of
scientific articles).

In this paper, we focus on a special and important case of distribution
mismatch, known as _covariate shift_. In this version, the marginal
distributions over the input covariates may vary from the training (or source)
to test (or target) data111Hereafter, we use source (resp. target) and
training (resp. testing) interchangeably., while the conditional distribution
of the output label given the input covariates is shared across training and
testing. Motivating applications include image, text, and speech
classification in which the input covariates determine the output labels [20].
Despite its importance in practice, the covariate shift problem is
underexplored in theory, when compared to supervised learning without
distribution mismatch—a subject that has been well studied in the past decades
[6].

This paper aims to bridge this gap by addressing several fundamental
theoretical questions regarding covariate shift. First, what is the
statistical limit of estimation in the presence of covariate shift? And how
does this limit depend on the “amount” of covariate shift between the source
and target distributions? Second, does nonparametric least-squares
estimation—a dominant (and often optimal) approach in the no-distribution-
shift case—achieve the optimal rate of estimation with covariate shift? If
not, what is the optimal way of tackling covariate shift?

###  1.1 Contributions and overview

We address the aforementioned theoretical questions regarding covariate shift
in the context of nonparametric regression over reproducing kernel Hilbert
spaces (RKHSs) [18]. That is, we assume that under both the source and target
distributions, the regression function (i.e., the conditional mean function of
the output label given the input covariates) belongs to an RKHS. In this
paper, we focus on two broad families of source-target pairs depending on the
configuration of the likelihood ratios between them.

We first consider the uniformly $B$-bounded family in which the likelihood
ratios are uniformly bounded by a quantity $B$. In this case, we present
general performance upper bounds for the kernel ridge regression (KRR)
estimator in Theorem 1. Instantiations of this general bound on various RKHSs
with regular eigenvalues are provided in Corollary 1. It is also shown in
Theorem 2 that KRR—with an optimally chosen regularization parameter that
depends on the largest likelihood ratio $B$—achieves the minimax lower bound
for covariate shift over this uniformly $B$-bounded family. It is worth noting
that the optimal regularization parameter shrinks as the likelihood ratio
bound increases.

We further show—via a constructive argument—that the nonparametric least-
squares estimator, which minimizes the empirical risk on the training data
over the specified RKHS, falls short of achieving the lower bound; see Theorem
3. This marks a departure from the classical no-covariate-shift setting, where
the constrained estimator (i.e., the nonparametric least-squares estimator)
and the regularized estimator (i.e., the KRR estimator) can both attain
optimal rates of estimation [23]. In essence, the failure arises from the
misalignment between the projections under the source and target covariate
distributions. Loosely speaking, nonparametric least-squares estimation
projects the data onto an RKHS according to the geometry induced by the
_source_ distribution. Under covariate shift, the resulting projection can be
extremely far away from the projection under the _target_ covariate
distributions.

In the second part of the paper, we turn to a more general setting, where the
likelihood ratios between the target and source distributions may not be
bounded. Instead, we only require the target and source covariate
distributions to have a likelihood ratio with bounded second moment. We
propose a variant of KRR that weights samples based on a careful truncation of
the likelihood ratios. We are able to show in Theorem 4 that this estimator is
rate-optimal over this larger class of covariate shift problems.

###  1.2 Related work

There is a large body of work on distribution mismatch and, in particular, on
covariate shift. Below we review the work that is directly relevant to ours,
and refer the interested reader to the book [20] and the survey [13] for
additional references.

Shimodaira [19] first studied the covariate shift problem from a statistical
perspective, and established the asymptotic consistency of the importance-
reweighted maximum likelihood estimator (without truncation). However, no
finite-sample guarantees were provided therein. Similar to our work, Cortes
and coauthors [4] analyzed the importance-reweighted estimator when the
density ratio is either bounded or has a finite second moment. However, their
analysis applies to the function class with finite pseudodimension (cf. the
book [15]), while the RKHS considered herein does not necessarily obey this
assumption. Moreover, even when the RKHS has a finite rank $D$, their result
(e.g., Theorem 8) is sub-optimal—with a rate of $\sqrt{V^{2}D/n}$ compared to
our optimal rate $V^{2}D/n$. Here $V^{2}$ is the bound on the second moment of
the likelihood ratios and $n$ denotes the number of samples. Recently, Kpotufe
and Martinet [10] investigated covariate shift for nonparametric
classification. They proposed a novel notion called transfer exponent to
measure the amount of covariate shift between the source and target
distributions. An estimator based on $k$ nearest neighbors was shown to be
minimax optimal over the class of covariate shift problems with bounded
transfer exponent. Inspired by the work of Kpotufe and Martinet, the current
authors [14] proposed a more fine-grained similarity measure for covariate
shift and applied to nonparametric regression over the class of Hölder
continuous functions. It is worth pointing out that both the transfer exponent
and the new fine-grained similarity measure are different and cannot directly
be compared to the moment conditions we impose on the likelihood ratios in
this work. In particular, there exist instances of covariate shift where the
second moment of the likelihood ratios is bounded whereas the transfer
exponent is infinite. One such case is when the source and target
distributions are both Gaussian with the same mean but different scales.
Another significant difference lies in the assumptions on the regression
function. Kpotufe and Martinet [10] and Pathak et al. [14] focused on the
class of Hölder continuous functions, while we focus on RKHSs. This leads to
drastically different optimal estimators. Schmidt-Hieber and Zamolodtchikov
[17] recently established the local convergence of the nonparametric least-
squares estimator for the specific class of 1-Lipschitz functions over the
unit interval $[0,1]$ and applied it to the covariate shift setting.

Apart from covariate shift, other forms of distribution mismatch have been
analyzed from a statistical perspective. Cai et al. [1] analyzed posterior
shift and proposed an optimal $k$-nearest-neighbor estimator. Maity et al.
[11] conducted the minimax analysis for the label shift problem. Recently,
Reeve et al. [16] studied the general distribution shift problem (also known
as transfer learning) which allows both covariate shift and posterior shift.

##### Notation.

Throughout the paper, we use $c,c^{\prime},c_{1},c_{2}$ to denote universal
constants, which may vary from line to line.

##  2 Background and problem formulation

In this section, we formulate and provide background on the problem of
covariate shift in nonparametric regression.

###  2.1 Nonparametric regression under covariate shift

The goal of nonparametric regression is to predict a real-valued response $Y$
based on a vector of covariates $X\in\mathcal{X}$. For each fixed $x$, the
optimal estimator in a mean-squared sense is given by the regression function
$f^{\star}(x)\coloneqq\mathbb{E}[Y\mid X=x]$. In a typical setting, we assume
observations of $n$ i.i.d. pairs $\\{(x_{i},y_{i})\\}_{i=1}^{n}$, where each
$x_{i}$ is drawn according to some distribution $P$ over $\mathcal{X}$, and
then $y_{i}$ is drawn according to the law $(Y\mid X=x_{i})$. We assume
throughout that for each $i$, the residual $w_{i}\coloneqq
y_{i}-f^{\star}(x_{i})$ is a sub-Gaussian random variable with variance proxy
$\sigma^{2}$.

We refer to the distribution $P$ over the covariate space as the _source
distribution_. In the standard set-up, the performance of an estimator
$\widehat{f}$ is measured according to its $L^{2}(P)$-error:

$\displaystyle\|\widehat{f}-f^{\star}\|^{2}_{P}$
$\displaystyle\coloneqq\mathbb{E}_{X\sim
P}\big{(}\widehat{f}(X)-f^{\star}(X)\big{)}^{2}\;=\;\int_{\mathcal{X}}\big{(}\widehat{f}(x)-f^{\star}(x)\big{)}^{2}p(x)dx,$
(1a) where $p$ is the density of $P$.

In the covariate shift version of this problem, we have a different goal—that
is, we wish to construct an estimate $\widehat{f}$ whose $L^{2}(Q)$-error is
small. Here the _target distribution_ $Q$ is different from the source
distribution $P$. In analytical terms, letting $q$ be the density of $Q$, our
goal is to find estimators $\widehat{f}$ such that

$\displaystyle\|\widehat{f}-f^{\star}\|^{2}_{Q}$
$\displaystyle=\mathbb{E}_{X\sim
Q}\big{(}\widehat{f}(X)-f^{\star}(X)\big{)}^{2}\;=\;\int_{\mathcal{X}}\big{(}\widehat{f}(x)-f^{\star}(x)\big{)}^{2}q(x)dx$
(1b)

is as small as possible. Clearly, the difficulty of this problem should depend
on some notion of discrepancy between the source and target distributions.

###  2.2 Conditions on source-target likelihood ratios

The discrepancy between the $L^{2}(P)$ and $L^{2}(Q)$ norms is controlled by
the _likelihood ratio_

$\displaystyle\rho(x)\coloneqq\frac{q(x)}{p(x)},$ (2)

which we assume exists for any $x\in\mathcal{X}$. By imposing different
conditions on the likelihood ratio, we can define different families of
source-target pairs $(P,Q)$. In this paper, we focus on two broad families of
such pairs.

##### Uniformly $B$-bounded families:

For a quantity $B\geq 1$, we say that the likelihood ratio is _$B$ -bounded_
if

$\displaystyle\sup_{x\in\mathcal{X}}\rho(x)\leq B.$ (3)

It is worth noting that $B=1$ recovers the case without covariate shift, i.e.,
$P=Q$. Our analysis in Section 3 works under this condition.

#####  $\chi^{2}$-bounded families:

A uniform bound on the likelihood ratio is a stringent condition, so that it
is natural to relax it. One relaxation is to instead bound the second moment:
in particular, for a scalar $V^{2}\geq 1$, we say that the likelihood ratio is
_$V^{2}$ -moment bounded_ if

$\displaystyle\mathbb{E}_{X\sim P}[\rho^{2}(X)]$ $\displaystyle\leq V^{2}.$
(4)

Note that when the uniform bound (3) holds, the moment bound (4) holds with
$V^{2}=B$. To see this, we can write $\mathbb{E}_{X\sim
P}[\rho^{2}(X)]\;=\;\mathbb{E}_{X\sim Q}[\rho(X)]\;\leq\;B$. However, the
moment bound (4) is much weaker in general. It is also worth noting that the
$\chi^{2}$-divergence between $Q$ and $P$ takes the form

$\displaystyle\chi^{2}(Q||P)=\mathbb{E}_{X\sim P}[\rho^{2}(X)]-1.$

Therefore, one can understand the quantity $V^{2}-1$ as an upper bound on the
$\chi^{2}$-divergence between $Q$ and $P$. Our analysis in Section 4 applies
under this weaker condition on the likelihood ratio.

###  2.3 Unweighted versus likelihood-reweighted estimators

In this paper, we focus on methods for nonparametric regression that are based
on optimizing over a Hilbert space $\mathcal{H}$ defined by a reproducing
kernel. The Hilbert norm $\|f\|_{\mathcal{H}}$ is used as a means of enforcing
“smoothness” on the solution, either by adding a penalty to the objective
function or via an explicit constraint.

In the absence of any knowledge of the likelihood ratio, a naïve approach is
to simply compute the _unweighted regularized estimate_

$\displaystyle\widehat{f}_{\lambda}$
$\displaystyle\coloneqq\arg\min_{f\in\mathcal{H}}\Big{\\{}\frac{1}{n}\sum_{i=1}^{n}(f(x_{i})-y_{i})^{2}+\lambda\|f\|_{\mathcal{H}}^{2}\Big{\\}},$
(5)

where $\lambda>0$ is a user-defined regularization parameter. When
$\mathcal{H}$ is a reproducing kernel Hilbert space (RKHS), then this estimate
is known as the _kernel ridge regression_ (KRR) estimate. This is a form of
empirical risk minimization, but in the presence of covariate shift, the
objective involves an empirical approximation to
$\mathbb{E}_{P}[(Y-f(X))^{2}]$, as opposed to $\mathbb{E}_{Q}[(Y-f(X))^{2}]$.

If the likelihood ratio were known, then a natural proposal is to instead
compute the _likelihood-reweighted regularized estimate_

$\displaystyle\widetilde{f}^{\mbox{\scriptsize{rw}}}_{\lambda}$
$\displaystyle\coloneqq\arg\min_{f\in\mathcal{H}}\Big{\\{}\frac{1}{n}\sum_{i=1}^{n}\rho(x_{i})(f(x_{i})-y_{i})^{2}+\lambda\|f\|_{\mathcal{H}}^{2}\Big{\\}}.$
(6)

The introduction of the likelihood ratio ensures that the objective now
provides an unbiased estimate of the expectation
$\mathbb{E}_{Q}[(Y-f(X))^{2}]$. However, reweighting by the likelihood ratio
also increases variance, especially in the case of unbounded likelihood
ratios. Accordingly, in Section 4, we study a suitably truncated form of the
estimator (6).

###  2.4 Kernels and their eigenvalues

Any reproducing kernel Hilbert space is associated with a positive
semidefinite kernel function
$\mathscr{K}:\mathcal{X}\times\mathcal{X}\rightarrow\real$. Under mild
regularity conditions, Mercer’s theorem guarantees that this kernel has an
eigen-expansion of the form

$\displaystyle\mathscr{K}(x,x^{\prime})\coloneqq\sum_{j=1}^{\infty}\mu_{j}\phi_{j}(x)\phi_{j}(x^{\prime})$
(7)

for a sequence of non-negative eigenvalues $\\{\mu_{j}\\}_{j\geq 1}$, and
eigenfunctions $\\{\phi_{j}\\}_{j\geq 1}$ taken to be orthonormal in
$L^{2}(Q)$. Given our goal of deriving bounds in the $L^{2}(Q)$-norm, it is
appropriate to expand the kernel in $L^{2}(Q)$, as we have done here (7), in
order to assess the richness of the function class.

Given the Mercer expansion, the squared norm in the reproducing kernel Hilbert
space takes the form

$\displaystyle\|f\|_{\mathcal{H}}^{2}$
$\displaystyle=\sum_{j=1}^{\infty}\frac{\theta_{j}^{2}}{\mu_{j}},\qquad\mbox{where
$\theta_{j}\coloneqq\int_{\mathcal{X}}f(x)\phi_{j}(x)q(x)dx$.}$

Consequently, the Hilbert space itself can be written as

$\displaystyle\mathcal{H}\coloneqq\bigg{\\{}f=\sum_{j=1}^{\infty}\theta_{j}\phi_{j}\;\mid\;\sum_{j=1}^{\infty}\frac{\theta_{j}^{2}}{\mu_{j}}<\infty\bigg{\\}}.$
(8)

Our goal is to understand the performance of nonparametric regression under
covariate shift when the regression function lies in $\mathcal{H}$.

Throughout this paper, we impose a standard boundedness condition on the
kernel function—namely, there exists some finite $\kappa>0$ such that

$\displaystyle\sup_{x\in\mathcal{X}}\mathscr{K}(x,x)$
$\displaystyle\leq\kappa^{2}.$ (9)

Note that any continuous kernel over a compact domain satisfies this
condition. Moreover, a variety of commonly used kernels, including the
Gaussian and Laplacian kernels, satisfy this condition over any domain.

##  3 Analysis for bounded likelihood ratios

We begin our analysis in the case of bounded likelihood ratios. Our first main
result is to prove an upper bound on the performance of the unweighted KRR
estimate (5). First, we prove a family of upper bounds (Theorem 1) depending
on the regularization parameter $\lambda$. By choosing $\lambda$ so as to
minimize this family of upper bounds, we obtain concrete results for different
classes of kernels (Corollary 1). We then turn to the complementary question
of lower bounds: in Theorem 2, we prove a family of lower bounds that
establish that for covariate shift with $B$-bounded likelihood ratios, the KRR
estimator is minimax-optimal up to logarithmic factors in the sample size.
This optimality guarantee is notable since it applies to the unweighted
estimator that does not involve full knowledge of the likelihood ratio (apart
from an upper bound).

In the absence of covariate shift, it is well-known that performing empirical
risk minimization with an explicit constraint on the function also leads to
minimax-optimal results. Indeed, without covariate shift, projecting an
estimate onto a convex constraint set containing the true function can never
lead to a worse result. In Theorem 3, we show that this natural property is no
longer true under covariate shift: performing empirical risk minimization over
the smallest Hilbert ball containing $f^{\star}$ can be sub-optimal. Optimal
procedures—such as the regularized KRR estimate—are actually operating over
Hilbert balls with radius substantially larger than the true norm
$\|f^{\star}\|_{\mathcal{H}}$.

###  3.1 Unweighted kernel ridge regression is near-optimal

We begin by deriving a family of upper bounds on the kernel ridge regression
estimator (5) under covariate shift. In conjunction with our later analysis,
these bounds will establish that the KRR estimate is minimax-optimal up to
logarithmic factors for covariate shift with bounded likelihood ratios.

######  Theorem 1.

Consider a covariate-shifted regression problem with likelihood ratio that is
$B$-bounded (3) over a Hilbert space with a $\kappa$-uniformly bounded kernel
(9). Then for any $\lambda\geq 10\kappa^{2}/n$, the KRR estimate
$\widehat{f}_{\lambda}$ satisfies the bound

$\displaystyle\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\leq\underbrace{\vphantom{\sum_{j=1}^{\infty}}4\lambda
B\|f^{\star}\|_{\mathcal{H}}^{2}}_{\mathbf{b}^{2}_{\lambda}(B)}+\underbrace{80\sigma^{2}B\frac{\log
n}{n}\sum_{j=1}^{\infty}\frac{\mu_{j}}{\mu_{j}+\lambda
B}}_{\mathbf{v}_{\lambda}(B)}$ (10)

with probability at least
$1-28\;\tfrac{\kappa^{2}}{\lambda}e^{-\frac{n\lambda}{16\kappa^{2}}}-\frac{1}{n^{10}}$.

See Section 5.1 for the proof of this theorem. In Appendix E.1, we also
present a corollary which provides a corresponding expectation bound for the
KRR estimator $\widehat{f}_{\lambda}$ for such $B$-bounded covariate shifts.

Note that the upper bound (10) involves two terms. The first term
$\mathbf{b}^{2}_{\lambda}(B)$ corresponds to the squared bias of the KRR
estimate, and it grows proportionally with the regularization parameter
$\lambda$ and the likelihood ratio bound $B$. The second term
$\mathbf{v}_{\lambda}(B)$ represents the variance of the KRR estimator, and it
shrinks as $\lambda$ increases, so that $\lambda$ controls the bias-variance
trade-off. This type of trade-off is standard in nonparametric regression;
what is novel of interest to us here is how the shapes of these trade-off
curves change as a function of the likelihood ratio bound $B$.

Figure 1 plots the right-hand side of the upper bound (10) as a function of
$\lambda$ for several different choices $B\in\\{1,5,10,15\\}$. (In all cases,
we fixed a kernel with eigenvalues decaying as $\mu_{j}=j^{-2}$, sample size
$n=8000$, and noise variance $\sigma^{2}=1$.) Of interest to us is the choice
$\lambda^{*}(B)$ that minimizes this

Figure 1: Plot of the upper bound (10) on the mean-squared error versus the
log regularization parameter $\log\lambda$ for four different choices of the
likelihood ratio bound $B$, in all cases with eigenvalues $\mu_{j}=(1/j)^{2}$,
noise variance $\sigma^{2}=1$ and sample size $n=8000$. The points marked with
$\star$ on each curve corresponds to the choice of $\lambda^{*}(B)$ that
minimizes the upper bound. Note how this minimizing value shifts to the left
as $B$ increases above the standard problem without covariate shift ($B=1$).

upper bound; note how this optimizing $\lambda^{*}(B)$ shifts leftwards to
smaller values as $B$ is increased.

We would like to understand the balancing procedure that leads to an optimal
$\lambda^{*}(B)$ in analytical terms. This balancing procedure is most easily
understood for kernels with _regular eigenvalues_ , a notion introduced in
past work [24] on kernel ridge regression. For a given targeted error level
$\delta>0$, it is natural to consider the first index $d(\delta)$ for which
the associated eigenvalue drops below $\delta^{2}$—that is,
$d(\delta)\coloneqq\min\\{j\geq 1\mid\mu_{j}\leq\delta^{2}\\}$. The eigenvalue
sequence is said to be regular if222In fact, we can relax this to only require
the minimizing $\delta$ in equation (12) to obey the tail bound.

$\displaystyle\sum_{j=d(\delta)+1}^{\infty}\mu_{j}$ $\displaystyle\leq
c\,d(\delta)\delta^{2}$ (11)

holds for some universal constant $c>0$. The class of kernels with regular
eigenvalues includes kernels of finite-rank and those with various forms of
polynomial or exponential decay in their eigenvalues; all are widely used in
practice. For kernels with regular eigenvalues, the bound (10) implies that
there is a universal constant $c^{\prime}$ such that

$\displaystyle\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\leq
c^{\prime}\Big{\\{}\delta^{2}\|f^{\star}\|_{\mathcal{H}}^{2}+\sigma^{2}B\frac{d(\delta)\log
n}{n}\Big{\\}}\qquad\mbox{where $\delta^{2}=\lambda B$.}$ (12)

We verify this claim as part of proving Corollary 1 below.

This bound (12) enables us to make (near)-optimal choices of $\delta$—and
hence $\lambda=\delta^{2}/B$. Let us summarize the outcome of this procedure
for a few kernels of interest. In particular, we say that a kernel has _finite
rank $D$_ if the eigenvalues $\mu_{j}=0$ for all $j>D$. The kernels that
underlie linear regression and polynomial regression more generally are of
this type. A richer family of kernels has eigenvalues that exhibit _$\alpha$
-polynomial decay_ $\mu_{j}\leq c\,j^{-2\alpha}$ for some $\alpha>1/2$. This
kind of eigenvalue decay is seen in various types of spline and Sobolev
kernels, as well as the Laplacian kernel. It is easy to verify that both of
these families have regular eigenvalues. To simplify the presentation, we
assume $\|f^{\star}\|_{\mathcal{H}}=1$.

######  Corollary 1 (Bounds for specific kernels).

  1. (a)

For a kernel with rank $D$, as long as $\sigma^{2}D\log n\geq 10\kappa^{2}$,
the choice $\lambda=\frac{\sigma^{2}D\log n}{n}$ yields an estimate
$\widehat{f}_{\lambda}$ such that

$\displaystyle\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\leq
c\sigma^{2}B\frac{D\log n}{n}$ (13a) with high probability.

  2. (b)

For a kernel with $\alpha$-decaying eigenvalues, suppose that $\sigma^{2}$ is
sufficiently large so that $\lambda=\linebreak
B^{-\frac{1}{2\alpha+1}}\;\big{(}\frac{\sigma^{2}\log
n}{n}\big{)}^{\frac{2\alpha}{2\alpha+1}}\geq 10\kappa^{2}/n$. Then the
estimate $\widehat{f}_{\lambda}$ obeys

$\displaystyle\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\leq
c\Big{(}\frac{\sigma^{2}B\log n}{n}\Big{)}^{\frac{2\alpha}{2\alpha+1}}$ (13b)

with high probability.

###### Proof.

We begin by proving the upper bound (12). With the shorthand
$\delta^{2}=\lambda B$, the variance term in our bound (10) can be bounded as

$\displaystyle\frac{1}{80}\mathbf{v}_{\lambda}(B)=\sigma^{2}B\frac{\log
n}{n}\sum_{j=1}^{\infty}\frac{\mu_{j}}{\mu_{j}+\delta^{2}}$
$\displaystyle\leq\sigma^{2}B\frac{\log
n}{n}\Big{\\{}\sum_{j=1}^{d(\delta)}1+\sum_{j>d(\delta)}^{\infty}\frac{\mu_{j}}{\mu_{j}+\delta^{2}}\Big{\\}},$

where, by the definition of $d(\delta)$, we have split the eigenvalues into
those that are larger than $\delta^{2}$, and those that are smaller than
$\delta^{2}$. By the definition of a regular kernel, the second term can be
upper bounded

$\displaystyle\sum_{j>d(\delta)}^{\infty}\frac{\mu_{j}}{\mu_{j}+\delta^{2}}$
$\displaystyle\leq\frac{1}{\delta^{2}}c^{\prime}\,d(\delta)\delta^{2}\;=\;c^{\prime}\,d(\delta).$

Putting together the pieces yields $\frac{1}{80}\mathbf{v}_{\lambda}(B)\leq
c_{2}\sigma^{2}B\frac{\log n}{n}d(\delta)$, for some universal constant
$c_{2}$. Combining with the bias term yields the claim (12).

We now prove claims (13a) and (13b). For a finite-rank kernel, using the fact
that $d(\delta)\leq D$ for any $\delta>0$, we can set
$\lambda=\frac{\sigma^{2}D\log n}{n}$ to obtain the claimed bound (13a). Now
suppose that the kernel has $\alpha$-polynomial decay—that is, $\mu_{j}\leq
cj^{-2\alpha}$ for some $c>0$. For any $\delta>0$, we then have $d(\delta)\leq
c^{\prime}\,(1/\delta)^{1/\alpha}$, and hence

$\displaystyle\delta^{2}+\sigma^{2}B\frac{d(\delta)\log n}{n}$
$\displaystyle\leq\delta^{2}+c^{\prime}\sigma^{2}B\frac{\log
n}{n}\big{(}\frac{1}{\delta}\big{)}^{1/\alpha}.$

By equating the two terms, we can solve for near-optimal $\delta$: in
particular, we set $\delta^{2}=\Big{(}\frac{\sigma^{2}B\log
n}{n}\Big{)}^{\frac{2\alpha}{2\alpha+1}}$ to obtain the claimed result. Notice
that this choice of $\delta^{2}$ corresponds to

$\displaystyle\lambda=\delta^{2}/B\;=\;B^{-\frac{1}{2\alpha+1}}\;\big{(}\frac{\sigma^{2}\log
n}{n}\big{)}^{\frac{2\alpha}{2\alpha+1}},$

as claimed in the corollary. ∎

###  3.2 Lower bounds with covariate shift for regular kernels

Thus far, we have established a family of upper bounds on the unweighted KRR
estimate, and derived concrete results for various classes of regular kernels.
We now establish that, for the class of regular eigenvalues, the bounds
achieved by the unweighted KRR estimator are minimax-optimal. Recall the
definition $d(\delta)=\min\\{j\geq 1\mid\mu_{j}\leq\delta^{2}\\}$, and the
notion of regular eigenvalues (11). For a Hilbert space $\mathcal{H}$, we let
$\mathcal{B}_{\mathcal{H}}(1)$ denote the Hilbert norm ball of radius one.

######  Theorem 2.

For any $B\geq 1$, there exists a pair $(P,Q)$ with $B$-bounded likelihood
ratio (3) and an orthonormal basis $\\{\phi_{j}\\}_{j\geq 1}$ of $L^{2}(Q)$
such that for any regular sequence of kernel eigenvalues $\\{\mu_{j}\\}_{j\geq
1}$, we have

$\displaystyle\inf_{\widehat{f}}\sup_{f^{\star}\in\mathcal{B}_{\mathcal{H}}(1)}\mathbb{E}[\|\widehat{f}-f^{\star}\|_{Q}^{2}]$
$\displaystyle\geq
c\;\inf_{\delta>0}\Big{\\{}\delta^{2}+\sigma^{2}B\frac{d(\delta)}{n}\Big{\\}}.$
(14)

See Appendix A for the proof of this claim.

Comparing the lower bound (14) to our achievable result (12) for the
unweighted KRR estimate, we see that—with an appropriate choice of the
regularization parameter $\lambda$—the KRR estimator is minimax optimal up to
a $\log n$ term. In particular, it is straightforward to derive the following
consequences of Theorem 2, which parallel the guarantees in Corollary 1:

  * $\bullet$

For a finite-rank kernel, the minimax risk for $B$-bounded covariate shift
satisfies the lower bound

$\displaystyle\inf_{\widehat{f}}\sup_{f^{\star}\in\mathcal{B}_{\mathcal{H}}(1)}\mathbb{E}[\|\widehat{f}-f^{\star}\|_{Q}^{2}]$
$\displaystyle\geq c\;\sigma^{2}B\frac{D}{n}.$

  * $\bullet$

For a kernel with $\alpha$-polynomial eigenvalues, the minimax risk for
$B$-bounded covariate shift satisfies the lower bound

$\displaystyle\inf_{\widehat{f}}\sup_{f^{\star}\in\mathcal{B}_{\mathcal{H}}(1)}\mathbb{E}[\|\widehat{f}-f^{\star}\|_{Q}^{2}]$
$\displaystyle\geq
c\;\Big{(}\frac{\sigma^{2}B}{n}\Big{)}^{\frac{2\alpha}{2\alpha+1}}.$

Note that both of these minimax lower bounds reduce to the known lower bounds
[24] in the case of no covariate shift (i.e., $B=1$).

###  3.3 Constrained kernel regression is sub-optimal

In the absence of covariate shift, procedures based on empirical risk
minimization with explicit constraints are also known to be minimax-optimal.
In the current setting, one such estimator is the constrained kernel
regression estimate

$\displaystyle\widehat{f}_{\mathrm{\scriptsize{erm}}}\coloneqq\arg\min_{f\in\mathcal{B}_{\mathcal{H}}(1)}\Big{\\{}\frac{1}{n}\sum_{i=1}^{n}(f(x_{i})-y_{i})^{2}\Big{\\}}.$
(15)

Without covariate shift and for any regular kernel, this constrained empirical
risk minimization procedure is minimax-optimal over all functions $f^{\star}$
with $\|f^{\star}\|_{\mathcal{H}}\leq 1$.

In the presence of covariate shift, this minimax-optimality turns out to be
false. In particular, suppose that the eigenvalues decay as
$\mu_{j}=(1/j)^{2}$, so that our previous results show that the minimax risk
for $B$-bounded likelihood ratios scales as
$\big{(}\frac{B\sigma^{2}}{n}\big{)}^{2/3}$. It turns out that there exists
$B$-bounded pair $(P,Q)$ and an associated kernel class with the prescribed
eigendecay for which the constrained estimator (15) is sub-optimal for a broad
range of $(B,n)$ pairs. In the following statement, we use $c_{1},c_{2}$ to
denote universal constants.

######  Theorem 3.

Assume that $\|f^{\star}\|_{\mathcal{H}}=1$, and that $\sigma^{2}=1$. For any
$B\in[c_{1}(\log n)^{2},c_{2}n^{2/3}]$, there exists a $B$-bounded pair
$(P,Q)$ and RKHS with eigenvalues $\mu_{j}\leq(1/j^{2})$ such that

$\displaystyle\sup_{f^{\star}\in\mathcal{B}_{\mathcal{H}}(1)}\mathbb{E}\Big{[}\|\widehat{f}_{\mathrm{\scriptsize{erm}}}-f^{\star}\|_{Q}^{2}\Big{]}\geq
c_{3}\,\frac{B^{3}}{n^{2}}.$ (16)

See Appendix B for the proof of this negative result.

In order to appreciate some implications of this theorem, suppose that we use
it to construct ensembles with $B_{n}\asymp n^{2/3}$. The lower bound (16)
then implies that over this sequence of problems, the maximal risk of
$\widehat{f}_{\mathrm{\scriptsize{erm}}}$ is bounded below by a universal
constant. On the other hand, if we apply the unweighted KRR procedure, then we
obtain consistent estimates, in particular with $L^{2}(Q)$-error that decays
as

$\displaystyle\Big{(}\frac{B_{n}}{n}\Big{)}^{2/3}$
$\displaystyle=\Big{(}\frac{n^{2/3}}{n}\Big{)}^{2/3}\;=\;n^{-2/9}.$

It is worth understanding why the constrained form of KRR is sub-optimal,
while the regularized form is minimax-optimal. Recall from Corollary 1 that
achieving minimax-optimal rates with KRR requires particular choices of the
regularization parameter $\lambda^{*}(B)$, ones that decrease as $B$ increases
(see Figure 1). This behavior suggests that the Hilbert norm
$\|\widehat{f}_{\lambda}\|_{\mathcal{H}}$ of the regularized KRR estimate with
optimal choice of $\lambda$ should grow significantly above
$\|f^{\star}\|_{\mathcal{H}}=1$ when we apply this method.

In order to confirm this intuition, we performed some illustrative simulations
over the ensembles, indexed by the pair $(B,n)$, that underlie the proof of
Theorem 3; see Appendix B for the details. With $\sigma^{2}=1$ remaining
fixed, for each given pair $(B,n)$, we simulated regularized kernel ridge
regression with the choice $\lambda=4^{2/3}n^{-2/3}B^{-1/3}$, as suggested by
Corollary 1.

Figure 2: Results based on computing the regularized KRR estimate for the
“bad” problems, indexed by the pair $(n,B)$, that underlie the proof of
Theorem 3. Each curve shows the squared Hilbert norm of the regularized KRR
estimate $\|\widehat{f}_{\lambda}\|_{\mathcal{H}}^{2}$, computed with
$\lambda=4^{2/3}n^{-2/3}B^{-1/3}$, versus the likelihood ratio bound $B$. Each
curve corresponds to a different choice of sample size $n$ as indicated in the
legend.

In Figure 2, for each fixed $n$, we plot the squared Hilbert norm
$\|\widehat{f}_{\lambda}\|_{\mathcal{H}}^{2}$ of the regularized KRR estimate
versus the parameter $B$. We vary the choice of sample size
$n\in\\{8000,16000,32000,64000,128000\\}$, as indicated in the figure legend.
In all of these curves, we see that the squared Hilbert norm is increasing as
a polynomial function of $B$. This behavior is to be expected, given the sub-
optimality of the constrained KRR estimate with a fixed radius.

##  4 Unbounded likelihood ratios

Thus far, our analysis imposed the $B$-bound (3) on the likelihood ratio. In
practice, however, it is often the case that the likelihood ratio is
unbounded. As a simple univariate example, suppose that the target
distribution $Q$ is standard normal $\mathcal{N}(0,1)$, whereas the source
distribution $P$ takes the form $\mathcal{N}(0,0.9)$. It is easy to see that
the likelihood ratio $\rho(x)$ tends to $\infty$ as $|x|\to\infty$. On the
other hand, the second moment of the likelihood ratio under $P$ remains
bounded, so that $\chi^{2}$-condition (4) applies.

The key to the success of the _unweighted_ KRR estimator (5) in the bounded
likelihood ratio case is the nice relationship between the covariance
$\bm{\Sigma}_{P}\coloneqq\mathbb{E}_{X\sim P}[\phi(X)\phi(X)^{\top}]$ of the
source distribution and the covariance $\bm{I}$ of the target distribution,
namely $\bm{\Sigma}_{P}\succeq\tfrac{1}{B}\bm{I}$. In contrast, such a nice
relationship (with $B$ replaced by $V^{2}$) does not appear to hold with
unbounded likelihood ratios. It is therefore natural to consider the
likelihood-reweighted estimate (6), as previously introduced in Section 2.3,
that ensures the nice identity $\mathbb{E}_{X\sim
P}[\rho(X)\phi(X)\phi(X)^{\top}]=\bm{I}$. In contrast to the unweighted KRR
estimator, it requires knowledge of the likelihood ratio, but we will see
that—when combined with a suitable form of truncation—it achieves minimax-
optimal rates (up to logarithmic factors) over the much larger classes of
$\chi^{2}$-bounded source-target pairs.

As noted before, one concern with likelihood-reweighted estimators is that
they can lead to substantial inflation of the variance, in particular due to
the multiplication by the potentially unbounded quantity $\rho(x)$. For this
reason, it is natural to consider truncation: more precisely, for a given
${\tau_{n}}>0$, we define the _truncated likelihood ratio_

$\displaystyle\rho_{\tau_{n}}(x)$
$\displaystyle\coloneqq\;\begin{cases}\rho(x),&\mbox{if
$\rho(x)\leq{\tau_{n}}$},\\\ {\tau_{n}},&\mbox{otherwise.}\end{cases}$ (17)

We then consider the family of estimators

$\displaystyle\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}\coloneqq\arg\min_{f\in\mathcal{H}}\Big{\\{}\frac{1}{n}\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})(f(x_{i})-y_{i})^{2}+\lambda\|f\|_{\mathcal{H}}^{2}\Big{\\}},$
(18)

where $\lambda>0$, along with the truncation level ${\tau_{n}}$, are
parameters to be specified.

We analyze the behavior of this estimator for kernels whose eigenfunctions are
$1$-uniformly bounded in sup-norm, meaning that

$\displaystyle\|\phi_{j}\|_{\infty}\coloneqq\sup_{x\in\mathcal{X}}|\phi_{j}(x)|$
$\displaystyle\leq 1\quad\mbox{for all $j=1,2,\ldots$.}$ (19)

Our choice of the constant $1$ is for notational simplicity. Although there
exist kernels whose eigenfunctions are not uniformly bounded, there are many
kernels for which this condition does hold. Whenever the domain $\mathcal{X}$
is compact and the eigenfunctions are continuous, this condition will hold.
Another class of examples is given by convolutional kernels (i.e., kernels of
the form $\mathscr{K}(x,z)=\Psi(x-z)$ for some
$\Psi:\mathcal{X}\rightarrow\real$), which have sinusoids as their
eigenfunctions, and thus satisfy this condition.

Our theorem on the truncated-reweighted KRR estimate (18) involves the kernel
complexity function
$\Psi(\delta,\mu)\coloneqq\sum_{j=1}^{\infty}\min\\{\delta^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}$,
and works for any solution $\delta_{n}>0$ to the inequality
$\mathcal{M}(\delta)\leq\delta^{2}/2$, where

$\displaystyle\mathcal{M}(\delta)$ $\displaystyle\coloneqq
c_{0}\sqrt{\tfrac{\sigma^{2}V^{2}\log^{3}(n)}{n}\Psi(\delta,\mu)}.$ (20)

Here $c_{0}$ is a universal constant, whose value is specified via the proof.

Below, we present the performance guarantee of
$\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}$ in the large noise regime
(i.e., when $\sigma^{2}\geq\kappa^{2}\|f^{\star}\|_{\mathcal{H}}^{2}$) to
simplify the statement. Theoretical guarantees for all ranges of $\sigma^{2}$
can be found in Appendix D.

######  Theorem 4.

Consider a kernel with sup-norm bounded eigenfunctions (19), and a source-
target pair with $\mathbb{E}_{P}[\rho^{2}(X)]\leq V^{2}$. Further assume that
the noise level obeys
$\sigma^{2}\geq\kappa^{2}\|f^{\star}\|_{\mathcal{H}}^{2}$. Then the estimate
$\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}$ with truncation
${\tau_{n}}=\sqrt{nV^{2}}$ and regularization
$\lambda\|f^{\star}\|_{\mathcal{H}}^{2}\geq\delta_{n}^{2}/3$ satisfies the
bound

$\displaystyle\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{Q}^{2}\leq\delta_{n}^{2}+3\lambda\|f^{\star}\|_{\mathcal{H}}^{2}$
(21)

with probability at least $1-c\>n^{-10}$. Here, we recall that $\delta_{n}>0$
is any solution to the inequality $\mathcal{M}(\delta)\leq\delta^{2}/2$, where

$\displaystyle\mathcal{M}(\delta)$
$\displaystyle=c_{0}\sqrt{\tfrac{\sigma^{2}V^{2}\log^{3}(n)}{n}\Psi(\delta,\mu)}.$

See Section 5.2 for the proof of this claim. In Appendix E.2, we also present
a corollary which provides a corresponding expectation bound for the
reweighted estimator $\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}$ for
such $V^{2}$-bounded covariate shifts.

To appreciate the connection to our previous analysis, in the proof of
Corollary 2 below, we show that for any regular sequence of eigenvalues and
$\|f^{\star}\|_{\mathcal{H}}=1$, we have

$\displaystyle\Psi(\delta,\mu)\leq c^{\prime}\;d(\delta)\delta^{2}$ (22)

for some universal constant $c^{\prime}$. Moreover, the condition
$\mathcal{M}(\delta)\leq\delta^{2}/2$ can be verified by checking the
inequality

$\displaystyle\sqrt{\frac{\sigma^{2}V^{2}\log^{3}(n)}{n}d(\delta)}\leq
c_{1}\delta.$ (23)

This further allows us to obtain the rates of estimation over specific kernel
classes.

######  Corollary 2.

Consider kernels with sup-norm bounded eigenfunctions (19).

  1. (a)

For a kernel with rank $D$, the truncated-reweighted estimator with
$\lambda=c\frac{DV^{2}\log^{3}(n)\sigma^{2}}{n}$ achieves

$\displaystyle\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{Q}^{2}\leq
c^{\prime}\frac{DV^{2}\log^{3}(n)\sigma^{2}}{n}$ (24)

with high probability.

  2. (b)

For a kernel with $\alpha$-polynomial eigenvalues, we have with high
probability

$\displaystyle\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{Q}^{2}\leq
c^{\prime}\Big{(}\frac{V^{2}\log^{3}(n)}{n}\sigma^{2}\Big{)}^{\frac{2\alpha}{2\alpha+1}},$
(25)

provided that
$\lambda=c\big{(}\frac{V^{2}\log^{3}(n)}{n}\sigma^{2}\big{)}^{\frac{2\alpha}{2\alpha+1}}$.

###### Proof.

We begin by verifying the claim (22). Recalling the definition of $d(\delta)$
as the smallest integer for which $\mu_{j}\leq\delta^{2}$, we can write

$\displaystyle\Psi(\delta,\mu)$
$\displaystyle=\sum_{j=1}^{d(\delta)}\min\\{\delta^{2},\mu_{j}\\}+\sum_{j=d(\delta)+1}^{\infty}\min\\{\delta^{2},\mu_{j}\\}\;\leq\;d(\delta)\delta^{2}+cd(\delta)\delta^{2}$

where the bound on the second sum follows from the regularity condition. This
completes the proof of the bound (22).

Given our bound (22), it is straightforward to verify the claim (23).

We now prove the bounds (24) and (25). For the finite rank case, we have
$\Psi(\delta,\mu)\leq D\delta^{2}$, which implies $\delta_{n}^{2}\leq
c\frac{DV^{2}\log^{3}(n)\sigma^{2}}{n}$ for some universal constant $c$. Apply
Theorem 4 to obtain the desired rate. Now we move on to the kernel with
$\alpha$-polynomial eigenvalues. We know from the proof of Corollary 1 that
$d(\delta)\leq c(1/\delta)^{1/\alpha}$, and hence $\Psi(\delta,\mu)\leq
c^{\prime}\delta^{2-1/\alpha}$. This implies $\delta_{n}^{2}\leq
c\Big{(}\frac{V^{2}\log^{3}n}{n}\sigma^{2}\Big{)}^{\frac{2\alpha}{2\alpha+1}},$
which together with Theorem 4 yields the claim. ∎

Corollary 2 showcases that the reweighted KRR estimator is minimax optimal (up
to log factors) over this more general $\chi^{2}$-bounded family. This can be
seen from the lower bound established in Theorem 2 and the fact that the
$\chi^{2}$-bounded family is a larger family compared to the uniformly bounded
family.

##  5 Proofs

In this section, we provide the proofs of our two sets of upper bounds on
different estimators. Section 5.1 is devoted to the proof of Theorem 1 on
upper bounds on unweighted KRR for $B$-bounded likelihood ratios, whereas
Section 5.2 is devoted to the proof of Theorem 4 on the performance of LR-
reweighted KRR with truncation.

###  5.1 Proof of Theorem 1

Define the empirical covariance operator333In this proof, all the operators
are defined with respect to the space $\ell^{2}(\mathbb{N})$.

$\displaystyle\widehat{\bm{\Sigma}}_{P}$
$\displaystyle\coloneqq\frac{1}{n}\sum_{i=1}^{n}\phi(x_{i})\phi(x_{i})^{\top},$
(26)

the population covariance operator $\bm{\Sigma}_{P}\coloneqq\mathbb{E}_{X\sim
P}[\phi(X)\phi(X)^{\top}]$, and the diagonal operator
$\bm{M}\coloneqq\mathsf{diag}(\\{\mu_{j}\\}_{j\geq 1})$.

Before we embark on the proof, we single out two important properties
regarding $\bm{\Sigma}_{P}$ and $\widehat{\bm{\Sigma}}_{P}$ that will be
useful in later proofs. For a given $\lambda>0$, we define the event

$\displaystyle\mathcal{E}(\lambda)\coloneqq\Big{\\{}\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I}\succeq\frac{1}{2}\big{(}\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I}\big{)}\Big{\\}},$
(27)

where $\bm{I}$ is the identity operator on $\ell^{2}(\mathbb{N})$.

######  Lemma 1.

For any $B$-bounded source-target pair (3), we have the deterministic lower
bound

$\displaystyle\bm{\Sigma}_{P}$ $\displaystyle\succeq\tfrac{1}{B}\bm{I}.$ (28a)
If, in addition, the kernel is $\kappa$-uniformly bounded (9), then whenever
$n\lambda\geq 10\kappa^{2}$, the event $\mathcal{E}(\lambda)$ defined in
equation (27) satisfies $\displaystyle\mathbb{P}[\mathcal{E}(\lambda)]$
$\displaystyle\geq
1-28\;\tfrac{\kappa^{2}}{\lambda}e^{-\frac{n\lambda}{16\kappa^{2}}}.$ (28b)

See Section 5.1.3 for the proof of this claim.

Equipped with Lemma 1, we now proceed to the proof of the theorem. In terms of
the basis $\\{\phi_{j}\\}_{j\geq 1}$, the KRR estimate has the expansion
$\widehat{f}_{\lambda}=\sum_{j=1}^{\infty}\widehat{\theta}_{j}\phi_{j}$, where
$\widehat{\theta}=\\{\widehat{\theta}_{j}\\}_{j\geq 1}$ is a sequence of
coefficients in $\ell^{2}(\mathbb{N})$. By the optimality conditions for the
KRR problem, we have

$\displaystyle\widehat{\theta}-\theta^{\star}$
$\displaystyle=-\lambda(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\bm{M}^{-1}\theta^{\star}+(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\big{(}\frac{1}{n}\sum_{i=1}^{n}w_{i}\phi(x_{i})\big{)}.$
(29)

By the triangle inequality, we have the upper bound
$\|\widehat{\theta}-\theta^{\star}\|_{2}^{2}\leq 2\big{(}T_{1}+T_{2}\big{)}$,
where

$\displaystyle
T_{1}\coloneqq\|\lambda(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\bm{M}^{-1}\theta^{\star}\|_{2}^{2},\quad\mbox{and}\quad
T_{2}\coloneqq\|(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\big{(}\frac{1}{n}\sum_{i=1}^{n}w_{i}\phi(x_{i})\big{)}\|_{2}^{2}.$

In terms of this decomposition, it suffices to establish that the following
bounds

$\displaystyle T_{1}\stackrel{{\scriptstyle(a)}}{{\leq}}2\lambda
B\|f^{\star}\|_{\mathcal{H}}^{2},\quad\mbox{and}\quad
T_{2}\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{40(\log
n)\sigma^{2}}{n}\sum_{j=1}^{\infty}\frac{\mu_{j}}{\mu_{j}/B+\lambda},$ (30)

hold with probability at least
$1-28\;\tfrac{\kappa^{2}}{\lambda}e^{-\frac{n\lambda}{16\kappa^{2}}}-n^{-10}$.

####  5.1.1 Proof of the bound (30)(a)

We establish that this bound holds conditionally on the event
$\mathcal{E}(\lambda)$. Following some algebraic manipulations, we have

$\displaystyle T_{1}$
$\displaystyle=\lambda^{2}\|\bm{M}^{1/2}(\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{-1/2}\theta^{\star}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\lambda^{2}\|f^{\star}\|_{\mathcal{H}}^{2}|\\!|\\!|\bm{M}^{1/2}(\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}|\\!|\\!|_{{2}}^{2}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\lambda\|f^{\star}\|_{\mathcal{H}}^{2}|\\!|\\!|\bm{M}^{1/2}(\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1/2}|\\!|\\!|_{{2}}^{2}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}2\lambda\|f^{\star}\|_{\mathcal{H}}^{2}|\\!|\\!|\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}|\\!|\\!|_{{2}}.$

Here inequality (i) follows from the fact that
$\|\bm{M}^{-1/2}\theta^{\star}\|_{2}=\|f^{\star}\|_{\mathcal{H}}$; the second
step (ii) uses the fact that
$\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I}\succeq\lambda\bm{I}$,
and step (iii) follows from the fact that we are conditioning on the event
$\mathcal{E}(\lambda)$.

Lemma 1 also guarantees that $\bm{\Sigma}_{P}\succeq\frac{1}{B}\bm{I}$, whence

$\displaystyle T_{1}\leq
2\lambda\|f^{\star}\|_{\mathcal{H}}^{2}|\\!|\\!|\bm{M}^{1/2}(\frac{1}{B}\bm{M}+\lambda\bm{I})^{-1}\bm{M}^{1/2}|\\!|\\!|_{{2}}=2\lambda\cdot\max_{j\geq
1}\left\\{\frac{\mu_{j}}{\tfrac{\mu_{j}}{B}+\lambda}\right\\}\leq 2\lambda
B\|f^{\star}\|_{\mathcal{H}}^{2}.$

This establishes the claim (30)(a).

####  5.1.2 Proof of the bound (30)(b)

Define the random vector
$W\coloneqq(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\big{(}\frac{1}{n}\sum_{i=1}^{n}w_{i}\phi(x_{i})\big{)}$.
Conditioned on the covariates $\\{x_{i}\\}_{i=1}^{n}$, $W$ is a zero-mean sub-
Gaussian random variable with covariance operator

$\displaystyle\bm{\Lambda}\coloneqq\frac{\sigma^{2}}{n}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\widehat{\bm{\Sigma}}_{P}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}.$

Consequently, by the Hanson-Wright inequality in the RKHS (cf. Theorem 2.6 in
the paper [3]), we have

$\displaystyle\mathbb{P}\big{[}T_{2}\geq 20(\log
n)\,\mathsf{trace}(\bm{\Lambda})\mid\\{x_{i}\\}_{i=1}^{n}\big{]}$
$\displaystyle\leq\frac{1}{n^{10}},$ (31)

where the probability is taken over the noise variables.

It remains to upper bound the trace. We have
$\mathsf{trace}(\bm{\Lambda})=\mathsf{trace}\big{(}\frac{\sigma^{2}}{n}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\widehat{\bm{\Sigma}}_{P}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\big{)}$,
so that

$\displaystyle\mathsf{trace}(\bm{\Lambda})$
$\displaystyle\leq\mathsf{trace}\Big{(}\frac{\sigma^{2}}{n}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\Big{)}$
$\displaystyle=\mathsf{trace}\Big{(}\frac{\sigma^{2}}{n}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\Big{)}=\mathsf{trace}\Big{(}\frac{\sigma^{2}}{n}(\bm{M}^{1/2}(\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}\Big{)}.$

Under the event $\mathcal{E}(\lambda)$, we have
$\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I}\succeq\frac{1}{2}\left(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I}\right)$,
which implies

$\displaystyle\mathsf{trace}(\bm{\Lambda})$ $\displaystyle\leq
2\frac{\sigma^{2}}{n}\mathsf{trace}\Big{(}\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}2\frac{\sigma^{2}}{n}\mathsf{trace}\Big{(}\bm{M}^{1/2}(\frac{1}{B}\bm{M}+\lambda\bm{I})^{-1}\bm{M}^{1/2}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}2\frac{\sigma^{2}}{n}\sum_{j=1}^{\infty}\frac{\mu_{j}}{\tfrac{\mu_{j}}{B}+\lambda}.$

Here step (i) follows since $\bm{\Sigma}_{P}\succeq\frac{1}{B}\bm{I}$, and
step (ii) follows from a direct calculation. Substituting this upper bound on
the trace into the tail bound (31) yields the claimed bound (30)(b).

####  5.1.3 Proof of Lemma 1

We begin with the proof of the lower bound (28a). Since $\\{\phi_{j}\\}_{j\geq
1}$ is an orthonormal basis of $L^{2}(Q)$, we have

$\displaystyle\mathbb{E}_{X\sim
Q}\big{[}\phi(X)\phi(X)^{\top}\big{]}=\mathbb{E}_{X\sim
P}\big{[}\rho(X)\phi(X)\phi(X)^{\top}\big{]}=\bm{I}.$

Thus, the $B$-boundedness of the likelihood ratio (3) implies that

$\displaystyle\bm{I}\preceq\mathbb{E}_{X\sim
P}[B\phi(X)\phi(X)^{\top}]=B\bm{\Sigma}_{P},$

which is equivalent to the claim (28a).

Next we prove the lower bound (27). We introduce the shorthand notation

$\displaystyle\widehat{\bm{\Sigma}}_{\lambda}\coloneqq\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I},\quad\mbox{and}\quad\bm{\Sigma}_{\lambda}\coloneqq\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I}$

along with the matrix
$\bm{\Delta}\coloneqq\bm{\Sigma}_{\lambda}^{-1/2}(\widehat{\bm{\Sigma}}_{\lambda}-\bm{\Sigma}_{\lambda})\bm{\Sigma}_{\lambda}^{-1/2}$.
Recalling that $|\\!|\\!|\cdot|\\!|\\!|_{{2}}$ denotes the $\ell_{2}$-operator
norm of a matrix, we first observe that
$\\{|\\!|\\!|\bm{\Delta}|\\!|\\!|_{{2}}\leq\frac{1}{2}\\}\subseteq\mathcal{E}$.
Consequently, it suffices to show that
$|\\!|\\!|\bm{\Delta}|\\!|\\!|_{{2}}\leq\tfrac{1}{2}$ with high probability.

The matrix $\bm{\Delta}$ can be written as the normalized sum
$\bm{\Delta}=\frac{1}{n}\sum_{i=1}^{n}\bm{Z}_{i}$, where the random operators

$\displaystyle\bm{Z}_{i}$
$\displaystyle\coloneqq\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\left(\phi(x_{i})\phi(x_{i})^{\top}-\bm{\Sigma}_{P}\right)\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}$

are i.i.d. The operator norm of each term can be bounded as

$\displaystyle|\\!|\\!|\bm{Z}_{i}|\\!|\\!|_{{2}}\leq
2\sup_{x\in\mathcal{X}}|\\!|\\!|\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(x)\phi(x)^{\top}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}|\\!|\\!|_{{2}}$
$\displaystyle=2\sup_{x\in\mathcal{X}}\|\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(x)\|_{2}^{2}$
$\displaystyle\leq
2\kappa^{2}|\\!|\\!|\bm{\Sigma}_{\lambda}^{-1/2}|\\!|\\!|_{{2}}^{2}\leq\frac{2\kappa^{2}}{\lambda}\eqqcolon
L,$ (32)

where the final inequality follows from the assumption that
$\sup_{x\in\mathcal{X}}\|\bm{M}^{1/2}\phi(x)\|_{2}^{2}\leq\kappa^{2}$, and the
fact that $\bm{\Sigma}_{\lambda}\succeq\lambda\bm{I}$.

On the other hand, the variance of $\bm{Z}_{i}$ can be bounded as

$\displaystyle\mathbb{E}[\bm{Z}_{i}^{2}]$
$\displaystyle\preceq\mathbb{E}[(\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(X)\phi(X)^{\top}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2})^{2}]$
$\displaystyle=\mathbb{E}[\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(X)\phi(X)^{\top}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1}\bm{M}^{1/2}\phi(X)\phi(X)^{\top}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}]$
$\displaystyle\preceq\mathbb{E}\Big{[}\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(X)\phi(X)^{\top}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}\Big{]}\cdot\sup_{x\in\mathcal{X}}\Big{\\{}\phi(x)^{\top}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1}\bm{M}^{1/2}\phi(x)\Big{\\}}$
$\displaystyle\preceq\frac{\kappa^{2}}{\lambda}\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}\eqqcolon\bm{V},$

where the last inequality follows by applying the bound (32) on
$\sup_{x\in\mathcal{X}}\|\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(x)\|_{2}^{2}$.

Suppose that we can show that

$\displaystyle\mathsf{trace}(\bm{V})$
$\displaystyle\leq\frac{\kappa^{2}}{\lambda}\cdot\frac{\kappa^{2}}{\lambda};$
(33a) $\displaystyle|\\!|\\!|\bm{V}|\\!|\\!|_{{2}}$
$\displaystyle\leq\frac{\kappa^{2}}{\lambda}.$ (33b)

We can then apply a dimension-free matrix Bernstein inequality (see Lemma 8)
with $t=1/2$ to obtain the tail bound

$\displaystyle\mathbb{P}\big{[}|\\!|\\!|\bm{\Delta}|\\!|\\!|_{{2}}\geq\tfrac{1}{2}\big{]}$
$\displaystyle\leq
28\frac{\kappa^{2}}{\lambda}\exp\Big{(}-\frac{n\lambda}{16\kappa^{2}}\Big{)},$

as long as $n\lambda\geq 10\kappa^{2}$. Thus, the only remaining detail is to
prove the bounds (33a) and (33b).

##### Proof of the bound (33a):

Using the definition of $\bm{V}$, we have

$\displaystyle\mathsf{trace}(\bm{V})=\frac{\kappa^{2}}{\lambda}\mathsf{trace}\Big{(}\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}\Big{)}$
$\displaystyle=\frac{\kappa^{2}}{\lambda}\mathbb{E}_{P}[\mathsf{trace}\big{(}\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(x)\phi(x)^{\top}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}\big{)}]$
$\displaystyle\leq\frac{\kappa^{2}}{\lambda}\cdot\frac{\kappa^{2}}{\lambda}.$

Here we have again applied the bound
$\sup_{x\in\mathcal{X}}\|\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\phi(x)\|_{2}^{2}\leq\kappa^{2}/\lambda$.

##### Proof of the bound (33b):

Recalling the definition of $\bm{\Sigma}_{\lambda}$, we see that
$|\\!|\\!|\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}|\\!|\\!|_{{2}}\leq
1$, and hence

$\displaystyle|\\!|\\!|\bm{V}|\\!|\\!|_{{2}}=\frac{\kappa^{2}}{\lambda}|\\!|\\!|\bm{\Sigma}_{\lambda}^{-1/2}\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}\bm{\Sigma}_{\lambda}^{-1/2}|\\!|\\!|_{{2}}\leq\frac{\kappa^{2}}{\lambda},$

which is the claimed upper bound on $|\\!|\\!|\bm{V}|\\!|\\!|_{{2}}$.

###  5.2 Proof of Theorem 4

We now turn to the proof of our guarantee on the truncated LR-reweighted
estimator. At the core of the proof is a uniform concentration result, one
that holds within a local ball

$\displaystyle\mathcal{G}(r)\coloneqq\\{f\in\mathcal{H}\mid\|f-f^{\star}\|_{Q}\leq
r,\text{ and }\|f-f^{\star}\|_{\mathcal{H}}\leq
3\|f^{\star}\|_{\mathcal{H}}\\}$

around the true regression function $f^{\star}$.

######  Lemma 2.

Fixing any $r>0$, we have

$\displaystyle\sup_{\begin{subarray}{c}g\in\mathcal{G}(r)\end{subarray}}\Big{\\{}\|g-f^{\star}\|_{Q}^{2}+\frac{1}{n}\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})\big{[}\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}-\big{(}g(x_{i})-y_{i}\big{)}^{2}\big{]}\Big{\\}}\leq\mathcal{M}(r)$
(34)

with probability at least $1-cn^{-10}$.

See Section 5.2.1 for the proof of this lemma.

Taking this lemma as given, we now complete the proof of the theorem. Define
the regularized radius
$\delta_{\lambda}\coloneqq\sqrt{\delta_{n}^{2}+3\lambda\|f^{\star}\|_{\mathcal{H}}^{2}}$,
and denote by $\mathcal{E}(\delta_{\lambda})$ the “good” event that the
relation (34) holds at radius $\delta_{\lambda}$. We immediately point out an
important property of the regularized radius $\delta_{\lambda}$, namely
$\mathcal{M}(\delta_{\lambda})\leq(1/2)\cdot\delta_{\lambda}^{2}$. To see
this, note that $r\mapsto\mathcal{M}(r)/r$ is non-increasing in $r$, and hence

$\displaystyle\frac{\mathcal{M}(\delta_{\lambda})}{\delta_{\lambda}}\leq\frac{\mathcal{M}(\delta_{n})}{\delta_{n}}\leq\frac{1}{2}\delta_{n}\leq\frac{1}{2}\delta_{\lambda}.$

Suppose that conditioned on $\mathcal{E}(\delta_{\lambda})$, the following
inequality holds

$\displaystyle\inf_{f\in\mathcal{H},f\notin\mathcal{G}(\delta_{\lambda})}\frac{1}{n}\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})\Big{\\{}\big{(}f(x_{i})-y_{i}\big{)}^{2}-\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}\Big{\\}}+\lambda\|f\|_{\mathcal{H}}^{2}-\lambda\|f^{\star}\|_{\mathcal{H}}^{2}>0.$
(35)

It then follows that that $\|\widehat{f}-f^{\star}\|_{Q}\leq\delta_{\lambda}$,
as desired. Consequently, the remainder of our proof is devoted to
establishing that inequality (35) holds conditioned on
$\mathcal{E}(\delta_{\lambda})$.

Given any function $f\in\mathcal{H}$ and
$f\notin\mathcal{G}(\delta_{\lambda})$, there exists an $\alpha\geq 1$ such
that $\widetilde{f}\coloneqq f^{\star}+\tfrac{1}{\alpha}(f-f^{\star})$ lies in
the set $\mathcal{H}$, and more importantly $\widetilde{f}$ lies on the
boundary of $\mathcal{G}(\delta_{\lambda})$. This follows from the convexity
of the two sets $\mathcal{H}$ and $\mathcal{G}(\delta_{\lambda})$. Since
$\widetilde{f}$ is a convex combination of $f$ and $f^{\star}$, Jensen’s
inequality implies that

$\displaystyle\rho_{\tau_{n}}(x_{i})\Big{\\{}\big{(}\widetilde{f}(x_{i})-y_{i}\big{)}^{2}-\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}\Big{\\}}+\lambda\|\widetilde{f}\|_{\mathcal{H}}^{2}-\lambda\|f^{\star}\|_{\mathcal{H}}^{2}$
$\displaystyle\quad\leq\tfrac{1}{\alpha}\left\\{\rho_{\tau_{n}}(x_{i})\Big{\\{}\big{(}f(x_{i})-y_{i}\big{)}^{2}-\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}\Big{\\}}+\lambda\|f\|_{\mathcal{H}}^{2}-\lambda\|f^{\star}\|_{\mathcal{H}}^{2}\right\\}.$

Consequently, in order to establish the claim (35), it suffices to prove that
the quantity

$\displaystyle
T\coloneqq\frac{1}{n}\;\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})\big{\\{}\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}-\big{(}\widetilde{f}(x_{i})-y_{i}\big{)}^{2}\big{\\}}+\lambda\|f^{\star}\|_{\mathcal{H}}^{2}-\lambda\|\widetilde{f}\|_{\mathcal{H}}^{2}$

is negative. Since $\widetilde{f}$ lies on the boundary of
$\mathcal{G}(\delta_{\lambda})$, we can split the proof into two cases: (1)
$\|\widetilde{f}-f^{\star}\|_{Q}=\delta_{\lambda}$, while
$\|\widetilde{f}-f^{\star}\|_{\mathcal{H}}\leq 3\|f^{\star}\|_{\mathcal{H}}$,
and (2) $\|\widetilde{f}-f^{\star}\|_{Q}\leq\delta_{\lambda}$, while
$\|\widetilde{f}-f^{\star}\|_{\mathcal{H}}=3\|f^{\star}\|_{\mathcal{H}}$.

##### Case 1:

$\|\widetilde{f}-f^{\star}\|_{Q}=\delta_{\lambda}$, while
$\|\widetilde{f}-f^{\star}\|_{\mathcal{H}}\leq 3\|f^{\star}\|_{\mathcal{H}}$.
By adding and subtracting terms, we have

$\displaystyle T$
$\displaystyle=\Biggr{[}\frac{1}{n}\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})\Big{\\{}\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}-\big{(}\widetilde{f}(x_{i})-y_{i}\big{)}^{2}\Big{\\}}+\|\widetilde{f}-f^{\star}\|_{Q}^{2}\Biggr{]}-\|\widetilde{f}-f^{\star}\|_{Q}^{2}+\lambda\|f^{\star}\|_{\mathcal{H}}^{2}-\lambda\|\widetilde{f}\|_{\mathcal{H}}^{2}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\mathcal{M}(\delta_{\lambda})-\delta_{\lambda}^{2}+\lambda\|f^{\star}\|_{\mathcal{H}}^{2}\stackrel{{\scriptstyle(ii)}}{{<}}-\frac{1}{2}\delta_{\lambda}^{2}+\lambda\|f^{\star}\|_{\mathcal{H}}^{2}\stackrel{{\scriptstyle(iii)}}{{<}}0,$

where step (i) follows from conditioning on the event
$\mathcal{E}(\delta_{\lambda})$, the equality
$\|\widetilde{f}-f^{\star}\|_{Q}^{2}=\delta_{\lambda}^{2}$, and non-positivity
of $\lambda\|\widetilde{f}\|_{\mathcal{H}}^{2}$; step (ii) follows from the
property $\mathcal{M}(\delta_{\lambda})\leq(1/2)\cdot\delta_{\lambda}^{2}$ and
step (iii) uses the definitions of $\delta_{\lambda}$ and $\lambda$.

##### Case 2:

$\|\widetilde{f}-f^{\star}\|_{Q}\leq\delta_{\lambda}$, while
$\|\widetilde{f}-f^{\star}\|_{\mathcal{H}}=3\|f^{\star}\|_{\mathcal{H}}$. By
the same addition and subtraction as above, we have

$\displaystyle T$
$\displaystyle=\Biggr{[}\frac{1}{n}\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})\Big{\\{}\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}-\big{(}\widetilde{f}(x_{i})-y_{i}\big{)}^{2}\Big{\\}}+\|\widetilde{f}-f^{\star}\|_{Q}^{2}\Biggr{]}-\|\widetilde{f}-f^{\star}\|_{Q}^{2}+\lambda\|f^{\star}\|_{\mathcal{H}}^{2}-\lambda\|\widetilde{f}\|_{\mathcal{H}}^{2}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\mathcal{M}(\delta_{\lambda})+\lambda\|f^{\star}\|_{\mathcal{H}}^{2}-\lambda\|\widetilde{f}\|_{\mathcal{H}}^{2}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{<}}\frac{1}{2}\delta_{\lambda}^{2}-3\lambda\|f^{\star}\|_{\mathcal{H}}^{2},$

Here, step (i) again follows from the conditioning on the event
$\mathcal{E}(\delta_{\lambda})$ and the assumption that
$\|\widetilde{f}-f^{\star}\|_{Q}\leq\delta_{\lambda}$. Step (ii) relies on the
facts that $\mathcal{M}(\delta_{\lambda})\leq(1/2)\cdot\delta_{\lambda}^{2}$,
$\|f^{\star}\|_{\mathcal{H}}=\|f^{\star}\|_{\mathcal{H}}$, and that
$\|\widetilde{f}\|_{\mathcal{H}}\geq 2\|f^{\star}\|_{\mathcal{H}}$. The latter
is a simple consequence of
$\|\widetilde{f}-f^{\star}\|_{\mathcal{H}}=3\|f^{\star}\|_{\mathcal{H}}$ and
the triangle inequality. Substitute in the definitions of $\delta_{\lambda}$
and $\lambda$ to see the negativity of $T$.

Combine the two cases to finish the proof of the claim (35).

####  5.2.1 Proof of Lemma 2

Define the shifted function class
$\mathcal{F}^{\star}\coloneqq\mathcal{H}-f^{\star}$, along with its
$r$-localized version

$\displaystyle\mathcal{F}^{\star}(r)\coloneqq\big{\\{}h\in\mathcal{F}^{\star}\mid\|h\|_{Q}\leq
r,\quad\text{and}\quad\|h\|_{\mathcal{H}}\leq
3\|f^{\star}\|_{\mathcal{H}}\big{\\}}.$

We begin by observing that

$\displaystyle\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}-\big{(}g(x_{i})-y_{i}\big{)}^{2}$
$\displaystyle=2w_{i}[g(x_{i})-f^{\star}(x_{i})]-\big{(}g(x_{i})-f^{\star}(x_{i})\big{)}^{2},$

which yields the following equivalent formulation of the claim in Lemma 2:

$\displaystyle\sup_{h\in\mathcal{F}^{\star}(r)}\Biggr{\\{}\frac{1}{n}\sum_{i=1}^{n}\Big{[}2w_{i}\rho_{\tau_{n}}(x_{i})h(x_{i})+\|h\|_{Q}^{2}-\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\Big{]}\Biggr{\\}}$
$\displaystyle\leq\mathcal{M}(r).$ (36)

By the triangle inequality, it suffices to show that
$T_{1}+T_{2}\leq\mathcal{M}(r)$, where

$\displaystyle
T_{1}\coloneqq\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\frac{2}{n}\sum_{i=1}^{n}w_{i}\rho_{\tau_{n}}(x_{i})h(x_{i})\Big{|},\quad\mbox{and}\quad
T_{2}\coloneqq\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\|h\|_{Q}^{2}-\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\big{\\}}\Big{|}.$

More precisely, the core of our proof involves establishing the following two
bounds:

$\displaystyle T_{1}$ $\displaystyle\leq
c\sigma\sqrt{\frac{V^{2}\log^{3}(n)}{n}}\Big{\\{}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\Big{\\}}^{1/2}\qquad\mbox{with
probability at least }1-n^{-10},\text{ and }$ (37a) $\displaystyle T_{2}$
$\displaystyle\leq
c\sqrt{\frac{V^{2}\log^{3}(n)}{n}}\cdot\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\qquad\mbox{with
probability at least }1-n^{-10}.$ (37b)

In conjunction, these two bounds ensure that

$\displaystyle T_{1}+T_{2}$ $\displaystyle\leq
c\sqrt{\frac{V^{2}\log^{3}(n)}{n}}\cdot\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}+c\sqrt{\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\frac{V^{2}\log^{3}(n)}{n}\sigma^{2}}.$
(38)

Since the kernel function is $\kappa^{2}$-bounded, we have
$\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\leq\|f^{\star}\|_{\mathcal{H}}^{2}\sum_{j=1}^{\infty}\mu_{j}\leq\kappa^{2}\|f^{\star}\|_{\mathcal{H}}^{2}$,
which together with the assumption
$\sigma^{2}\geq\kappa^{2}\|f^{\star}\|_{\mathcal{H}}^{2}$ implies that
$T_{1}+T_{2}\leq
2c\sqrt{\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\frac{V^{2}\log^{3}(n)}{n}\sigma^{2}}$.
Therefore the bound (36) holds.

It remains to prove the bounds (37a) and (37b). The proofs make use of some
elementary properties of the localized function class
$\mathcal{F}^{\star}(r)$, which we collect here. For any
$h\in\mathcal{F}^{\star}(r)$, we have

$\displaystyle|h(x)|$
$\displaystyle\leq\sqrt{10\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}},\qquad\mbox{and}$
(39a)
$\displaystyle\sum_{j=1}^{\infty}\frac{\theta_{j}^{2}}{\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}$
$\displaystyle\leq 10,\qquad\mbox{where
$h=\sum_{j=1}^{\infty}\theta_{j}\phi_{j}$.}$ (39b)

See Appendix C for the proof of these elementary claims.

####  5.2.2 Proof of inequality (37b)

We begin by analyzing the term $T_{2}$. By the triangle inequality, we have
the upper bound $T_{2}\leq T_{2a}+T_{2b}$, where

$\displaystyle T_{2a}$
$\displaystyle\coloneqq\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\|h\|_{Q}^{2}-\mathbb{E}_{P}[\rho_{\tau_{n}}(X)h^{2}(X)]\Big{|},\quad\mbox{and}$
$\displaystyle T_{2b}$
$\displaystyle\coloneqq\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\mathbb{E}_{P}[\rho_{\tau_{n}}(X)h^{2}(X)]-\frac{1}{n}\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\Big{\\}}\Big{|}.$

Note that $T_{2a}$ is a deterministic quantity, measuring the bias induced by
truncation, whereas $T_{2b}$ is the supremum of an empirical process. We split
our proof into analysis of these two terms. In particular, we establish the
following bounds:

$\displaystyle T_{2a}$ $\displaystyle\leq
c\sqrt{\frac{V^{2}}{n}}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\},\quad\mbox{and}$
(40a) $\displaystyle T_{2b}$ $\displaystyle\leq
c\sqrt{\frac{V^{2}\log^{2}(n)}{n}}\>\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\qquad\text{with
probability at least }1-n^{-10}.$ (40b)

Combining these two bounds yields the claim (37b).

##### Proof of inequality (40a):

We begin by proving the claimed upper bound on $T_{2a}$. Note that

$\displaystyle T_{2a}$
$\displaystyle\leq\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\|h\|_{Q}^{2}-\mathbb{E}_{Q}[\mathbbm{1}\\{\rho(X)\leq{\tau_{n}}\\}h^{2}(X)]\Big{|}+{\tau_{n}}\cdot\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\mathbb{E}_{P}[\mathbbm{1}\\{\rho(X)>{\tau_{n}}\\}h^{2}(X)]\Big{|}$
$\displaystyle=\sup_{h\in\mathcal{F}^{\star}(r)}\mathbb{E}_{Q}\Big{[}\mathbbm{1}\\{\rho(X)>{\tau_{n}}\\}h^{2}(X)\Big{]}+{\tau_{n}}\cdot\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\mathbb{E}_{P}[\mathbbm{1}\\{\rho(X)>{\tau_{n}}\\}h^{2}(X)]\Big{|}$
$\displaystyle\leq\mathbb{E}_{Q}\Big{[}\mathbbm{1}\\{\rho(X)>{\tau_{n}}\\}\Big{]}\cdot\sup_{h\in\mathcal{F}^{\star}(r)}\|h\|_{\infty}^{2}+{\tau_{n}}\cdot\mathbb{E}_{P}[\mathbbm{1}\\{\rho(X)>{\tau_{n}}\\}]\cdot\sup_{h\in\mathcal{F}^{\star}(r)}\|h\|_{\infty}^{2}$
$\displaystyle\leq\frac{V^{2}}{{\tau_{n}}}\cdot
10\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}+{\tau_{n}}\cdot\frac{V^{2}}{({\tau_{n}})^{2}}\cdot
10\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\},$

where the last step follows from a combination of Markov’s inequality,
Chebyshev’s inequality, and the $\ell_{\infty}$-norm bound (39a). Recalling
that ${\tau_{n}}=\sqrt{nV^{2}}$, the bound (40a) follows.

##### Proof of the bound (40b):

We prove the claimed bound on $T_{2b}$ by first bounding its mean
$\mathbb{E}[T_{2b}]$, and then providing a high-probability bound on the
deviation $T_{2b}-\mathbb{E}[T_{2b}]$.

Bound on the mean: By a standard symmetrization argument (see e.g., Chapter 4
in the book [23]), we have the upper bound

$\displaystyle\mathbb{E}[T_{2b}]\leq\frac{2}{n}\>\mathbb{E}\Big{[}\sup_{h\in\mathcal{F}^{\star}(r)}\big{|}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\big{|}\Big{]},$

where $\\{\varepsilon_{i}\\}_{i=1}^{n}$ is an i.i.d. sequence of Rademacher
variables. Now observe that

$\displaystyle\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\Big{|}$
$\displaystyle\leq\sup_{\begin{subarray}{c}\widetilde{h},h\in\mathcal{F}^{\star}(r)\end{subarray}}Z(h,\widetilde{h}),\quad\mbox{where}\quad
Z(h,\widetilde{h})\coloneqq\Big{|}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\widetilde{h}(x_{i})h(x_{i})\Big{|}.$

Writing $\widetilde{h}=\sum_{j=1}^{\infty}\tilde{\theta}_{j}\phi_{j}$, we have

$\displaystyle
Z(h,\widetilde{h})=\Big{|}\sum_{j=1}^{\infty}\tilde{\theta}_{j}\big{\\{}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})h(x_{i})\big{\\}}\Big{|}$
$\displaystyle\quad=\Big{|}\sum_{j=1}^{\infty}\tfrac{\tilde{\theta}_{j}}{\sqrt{\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}}\cdot\sqrt{\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}\big{\\{}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})h(x_{i})\big{\\}}\Big{|}$
$\displaystyle\quad\leq\sqrt{10}\,\Big{\\{}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\cdot\big{\\{}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})h(x_{i})\big{\\}}^{2}\Big{\\}}^{1/2},$

where the final step follows by combining the Cauchy–Schwarz inequality with
the bound (39b). We now repeat the same argument to upper bound the inner term
involving $h$; in particular, we have

$\displaystyle\Big{\\{}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})h(x_{i})\Big{\\}}^{2}$
$\displaystyle=\Big{\\{}\sum_{k=1}^{\infty}\theta_{k}\big{(}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\phi_{k}(x_{i})\big{)}\Big{\\}}^{2}$
$\displaystyle\leq
10\cdot\sum_{k=1}^{\infty}\left\\{\min\\{r^{2},\mu_{k}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\Big{(}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\phi_{k}(x_{i})\Big{)}^{2}\right\\}.$

Putting together the pieces now leads to the upper bound

$\displaystyle\frac{2}{n}\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\Big{|}\leq\frac{2}{n}\sup_{h,\widetilde{h}\in\mathcal{F}^{\star}(r)}Z(h,\widetilde{h})$
$\displaystyle\quad\leq\;\frac{20}{n}\;\Big{\\{}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\cdot\sum_{k=1}^{\infty}\min\\{r^{2},\mu_{k}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\big{(}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\phi_{k}(x_{i})\big{)}^{2}\Big{\\}}^{1/2}.$

By taking expectations of both sides and applying Jensen’s inequality, we find
that

$\displaystyle\mathbb{E}[T_{2b}]\leq\frac{20}{n}\Big{\\{}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\cdot\sum_{k=1}^{\infty}\min\\{r^{2},\mu_{k}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\mathbb{E}_{X,\varepsilon}\big{(}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\phi_{k}(x_{i})\big{)}^{2}\Big{\\}}^{1/2}.$
(41)

We now observe that

$\displaystyle\mathbb{E}_{X,\varepsilon}\Big{[}\big{(}\sum_{i=1}^{n}\varepsilon_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\phi_{k}(x_{i})\big{)}^{2}\Big{]}$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{X,\varepsilon}\Big{[}\varepsilon_{i}^{2}(\rho_{\tau_{n}}(x_{i}))^{2}\phi_{j}^{2}(x_{i})\phi_{k}^{2}(x_{i})\Big{]}$
$\displaystyle\leq\sum_{i=1}^{n}\mathbb{E}_{X,\varepsilon}[\rho^{2}(x_{i})]\;\leq\;nV^{2},$

where we have used the fact that $\|\phi_{j}\|_{\infty}\leq 1$ for all $j\geq
1$, and that $\rho_{\tau_{n}}(x_{i})\leq\rho(x_{i})$. Substituting this upper
bound into our earlier inequality (41) yields

$\displaystyle\mathbb{E}[T_{2b}]$ $\displaystyle\leq
20\>\sqrt{\frac{V^{2}}{n}}\cdot\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}.$
(42)

Bounding the deviation term: Recall that for any $h\in\mathcal{F}^{\star}$, we
have
$\|h\|_{\infty}\leq\sqrt{10\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}$.
Consequently, we have

$\displaystyle\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\mathbb{E}_{Q}[\mathbbm{1}\\{\rho(X)\leq{\tau_{n}}\\}h^{2}(X)]-\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\Big{|}$
$\displaystyle\leq
10{\tau_{n}}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}$
$\displaystyle=10\sqrt{nV^{2}}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}.$

In addition, we have

$\displaystyle\sup_{h\in\mathcal{F}^{\star}(r)}\sum_{i=1}^{n}\mathbb{E}\Big{[}\big{\\{}\mathbb{E}_{Q}[\mathbbm{1}\\{\rho(X)\leq{\tau_{n}}\\}h^{2}(X)]-\rho_{\tau_{n}}(x_{i})h^{2}(x_{i})\big{\\}}^{2}\Big{]}$
$\displaystyle\leq\sup_{h\in\mathcal{F}^{\star}(r)}\sum_{i=1}^{n}\mathbb{E}\big{[}(\rho_{\tau_{n}}(x_{i}))^{2}h^{4}(x_{i})\big{]}$
$\displaystyle\leq
100nV^{2}\big{(}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\big{)}^{2},$

where we have applied the $\ell_{\infty}$-norm bound (39a) as well as the
$V^{2}$-condition on the likelihood ratio. These two facts together allow us
to apply Talagrand’s concentration results (cf. Lemma 9) and obtain

$\displaystyle\mathbb{P}\Big{[}T_{2b}\geq\mathbb{E}[T_{2b}]+\tfrac{t}{n}\Big{]}$
$\displaystyle\leq\exp\left(-\frac{t^{2}}{3000nV^{2}\big{(}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\big{)}^{2}+900\sqrt{nV^{2}}\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}t}\right).$
(43)

Completing the proof of the bound (40b): We now have the ingredients to
complete the proof of the claim (40b). In particular, by combining the upper
bound (42) on the mean with the deviation bound (43), we find that

$\displaystyle T_{2b}\leq
c\sqrt{\frac{V^{2}\log^{2}(n)}{n}}\>\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\qquad\mbox{with
probability at least $1-n^{-10}$,}$

as claimed in equation (40b).

####  5.2.3 Proof of inequality (37a)

Now we focus on the first term
$T_{1}=\sup_{h\in\mathcal{F}^{\star}(r)}\Big{|}\frac{1}{n}\sum_{i=1}^{n}w_{i}\rho_{\tau_{n}}(x_{i})h(x_{i})\Big{|}$.
Repeating the same strategy as in the proof of the bound (40b), we see that

$\displaystyle
T_{1}\leq\frac{1}{n}\Big{\\{}10\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\cdot\big{(}\sum_{i=1}^{n}w_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{)}^{2}\Big{\\}}^{1/2}.$
(44)

Fix $\\{x_{i}\\}_{i=1}^{n}$. We see that
$\big{(}\sum_{i=1}^{n}w_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{)}^{2}$
is a quadratic form of independent sub-Gaussian random variables. Apply the
Hanson-Wright inequality (e.g., Theorem 6.2.1 in the book [22]) to obtain that
with probability at least $1-n^{-10}$,

$\displaystyle\big{(}\sum_{i=1}^{n}w_{i}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{)}^{2}\leq
c_{3}\sigma^{2}\sum_{i=1}^{n}\big{[}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{]}^{2}.$
(45)

It remains to control the term
$\sum_{i=1}^{n}\big{[}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{]}^{2}$. To
this end, we invoke Bernstein’s inequality to arrive at

$\displaystyle\sum_{i=1}^{n}\big{[}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{]}^{2}\leq\mathbb{E}\left[\sum_{i=1}^{n}\big{[}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{]}^{2}\right]+c_{4}\sqrt{\alpha\log
n}+c_{5}\beta\log n$

with probability exceeding $1-n^{-10}$. Here,

$\displaystyle\alpha$
$\displaystyle\coloneqq\mathbb{E}\sum_{i=1}^{n}\mathsf{Var}\Big{(}\big{[}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{]}^{2}\Big{)}\leq(nV^{2})^{2}$
$\displaystyle\beta$
$\displaystyle\coloneqq\sup_{x}|\big{[}\rho_{\tau_{n}}(x)\phi_{j}(x)\big{]}^{2}|\leq{\tau_{n}}^{2}=nV^{2},$

are the variance and range statistics, respectively. This together with the
upper bound
$\mathbb{E}\left[\sum_{i=1}^{n}\big{[}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{]}^{2}\right]\leq
nV^{2}$ implies

$\displaystyle\sum_{i=1}^{n}\big{[}\rho_{\tau_{n}}(x_{i})\phi_{j}(x_{i})\big{]}^{2}\leq
c_{6}nV^{2}\log n.$ (46)

Combine the inequalities (44), (45), and (46) to complete the proof of the
inequality (37a).

##  6 Discussion

In this paper, we study RKHS-based nonparametric regression under covariate
shift. In particular, we focus on two broad families of covariate shift
problems: (1) the uniformly $B$-bounded family, and (2) the $\chi^{2}$-bounded
family. For the uniformly $B$-bounded family, we prove that the unweighted KRR
estimate—with properly chosen regularization parameter—achieves optimal rate
convergence for a large family of RKHSs with regular eigenvalues. In contrast,
the naïve constrained kernel regression estimator is provably suboptimal under
covariate shift. In addition, for the $\chi^{2}$-bounded family, we propose a
likelihood-ratio-reweighted KRR with proper truncation that attains the
minimax lower bound over this larger family of covariate shift problems.

Our study is an initial step towards understanding the statistical nature of
covariate shift. Below we single out several interesting directions to pursue
in the future. First, it is of great importance to extend the study to other
classes of regression functions, e.g., high dimensional linear regression,
decision trees, etc. Second, while it is natural to measure discrepancy
between source-target pairs using likelihood ratio, this is certainly not the
only possibility. Various measures of discrepancy have been proposed in the
literature, and it is interesting to see what the corresponding optimal
procedures are. Thirdly, our upper and lower bounds match for regular kernels.
It is standard in the kernel regression literature to make an assumption
regarding the decay of the kernel eigenvalue sequence [2, 24]. As highlighted
by the corollaries to our main upper bound, the assumption of a regular kernel
is general enough to capture the main examples of kernels used in practice.
Additionally, we emphasize that in this paper, we have adopted a worst-case
perspective where we study the minimax rate of estimation for a sequence of
regular kernel eigenvalues, over all $B$-bounded covariate shifts. A more
instance-dependent perspective which studies these minimax rates for a fixed
$B$-bounded covariate shift pair is very interesting and left for future work.
Lastly, on a technical end, it is also interesting to see whether one can
remove the uniform boundedness of the eigenfunctions in the unbounded
likelihood ratio case, and retain the optimal rate of convergence. In the
current proof, we mainly use it to develop a localization bound (39a) which
guarantees that any function $h\in\mathcal{H}$ that is $r$-close to
$f^{\star}$ in $\ell_{2}$ sense (roughly) enjoys an $\ell_{\infty}$ bound that
also scales with $r$.

### Acknowledgements

This work was partially supported by NSF-DMS grant 2015454, NSF-IIS grant
1909365, as well as Office of Naval Research grant DOD-ONR-N00014-18-1-2640 to
MJW. RP was partially supported by a Berkeley Fellowship and an ARCS
Fellowship.

## References

  * [1] T Tony Cai and Hongji Wei.  Transfer learning for nonparametric classification: Minimax rate and adaptive classifier.  The Annals of Statistics, 49(1):100–128, 2021.
  * [2] Andrea Caponnetto and Ernesto De Vito.  Optimal rates for the regularized least-squares algorithm.  Foundations of Computational Mathematics, 7(3):331–368, 2007.
  * [3] Xiaohui Chen and Yun Yang.  Hanson–Wright inequality in Hilbert spaces with application to ${K}$-means clustering for non-Euclidean data.  Bernoulli, 27(1):586–614, 2021.
  * [4] Corinna Cortes, Yishay Mansour, and Mehryar Mohri.  Learning bounds for importance weighting.  In Advances in Neural Information Processing Systems, volume 23, pages 442–450, 2010.
  * [5] Hao Guan and Mingxia Liu.  Domain adaptation for medical image analysis: A survey.  IEEE Transactions on Biomedical Engineering, pages 1–1, 2021.
  * [6] László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al.  A distribution-free theory of nonparametric regression, volume 1.  Springer, 2002.
  * [7] Jing Jiang and ChengXiang Zhai.  Instance weighting for domain adaptation in NLP.  In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 264–271, Prague, Czech Republic, June 2007\. Association for Computational Linguistics.
  * [8] Thierry Klein and Emmanuel Rio.  Concentration around the mean for maxima of empirical processes.  The Annals of Probability, 33(3):1060–1077, 2005.
  * [9] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al.  Wilds: A benchmark of in-the-wild distribution shifts.  In International Conference on Machine Learning, pages 5637–5664. PMLR, 2021.
  * [10] Samory Kpotufe and Guillaume Martinet.  Marginal singularity and the benefits of labels in covariate-shift.  The Annals of Statistics, 49(6):3299–3323, 2021.
  * [11] Subha Maity, Yuekai Sun, and Moulinath Banerjee.  Minimax optimal approaches to the label shift problem.  arXiv preprint arXiv:2003.10443, 2020.
  * [12] Stanislav Minsker.  On some extensions of Bernstein’s inequality for self-adjoint operators.  Statistics & Probability Letters, 127:111–119, 2017.
  * [13] Sinno Jialin Pan and Qiang Yang.  A survey on transfer learning.  IEEE Transactions on knowledge and data engineering, 22(10):1345–1359, 2009.
  * [14] Reese Pathak, Cong Ma, and Martin J Wainwright.  A new similarity measure for covariate shift with applications to nonparametric regression.  arXiv preprint arXiv:2202.02837, 2022.
  * [15] David Pollard.  Convergence of stochastic processes.  Springer Science & Business Media, 2012.
  * [16] Henry WJ Reeve, Timothy I Cannings, and Richard J Samworth.  Adaptive transfer learning.  arXiv preprint arXiv:2106.04455, 2021.
  * [17] Johannes Schmidt-Hieber and Petr Zamolodtchikov.  Local convergence rates of the least squares estimator with applications to transfer learning.  arXiv preprint arXiv:2204.05003, 2022.
  * [18] Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al.  Learning with kernels: support vector machines, regularization, optimization, and beyond.  MIT press, 2002.
  * [19] Hidetoshi Shimodaira.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  Journal of statistical planning and inference, 90(2):227–244, 2000\.
  * [20] Masashi Sugiyama and Motoaki Kawanabe.  Machine learning in non-stationary environments: Introduction to covariate shift adaptation.  MIT press, 2012.
  * [21] Vladimir Vapnik.  The nature of statistical learning theory.  Springer science & business media, 1999.
  * [22] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [23] Martin J Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.
  * [24] Yun Yang, Mert Pilanci, and Martin J Wainwright.  Randomized sketches for kernels: Fast and optimal nonparametric regression.  The Annals of Statistics, 45(3):991–1023, 2017.

##  Appendix A Proof of Theorem 2

Let $\delta_{n}$ be the smallest positive solution to the inequality
$c^{\prime}\sigma^{2}B\frac{d(\delta)}{n}\leq\delta^{2}$, where $c^{\prime}>0$
is some large constant. We decompose the proof into two steps. First, we
construct the lower bound instance, namely the source, target distributions,
and the corresponding orthonormal basis. Second, we apply the Fano method to
prove the lower bound.

##### Step 1: Constructing the lower bound instance.

Let $Q$ be a uniform distribution on $\\{\pm 1\\}^{+\infty}$. For the source
distribution $P$, we set it as follows: with probability $1/B$, we sample $x$
uniformly on $\\{\pm 1\\}^{+\infty}$, and with probability $1-1/B$, we set
$x=0$. It can be verified that the pair $(P,Q)$ has $B$-bounded likelihood
ratio. Corresponding to the target distribution $Q$, we take
$\phi_{j}(x)=x_{j}$ for every $j\geq 1$. In other words, we consider a linear
kernel.

##### Step 2: Establishing the lower bound.

In order to apply Fano’s method, we first need to construct a packing set of
the function class $\mathcal{B}_{\mathcal{H}}(1)$. For a given radius $r>0$,
consider the $r$-localized ellipse

$\displaystyle\mathscr{E}(r)\coloneqq\Big{\\{}\theta\mid\sum_{j=1}^{\infty}\frac{\theta_{j}^{2}}{\min\\{r^{2},\mu_{j}\\}}\leq
1\Big{\\}}.$

It is straightforward to check that for any $\theta\in\mathscr{E}(r)$, the
function $f=\sum_{j=1}^{\infty}\theta_{j}\phi_{j}$ lies in
$\mathcal{B}_{\mathcal{H}}(1)$. This set $\mathscr{E}(r)$ admits a large
packing set in the $\ell_{2}$-norm, as claimed in the following lemma.

######  Lemma 3.

For any $r\in(0,\delta_{n}]$, there exists a set
$\\{\theta^{1},\theta^{2},\ldots,\theta^{M}\\}\subseteq\mathscr{E}(r)$ with
$\log M=d_{n}/64$ such that

$\displaystyle\|\theta^{j}-\theta^{k}\|_{2}^{2}\geq\tfrac{r^{2}}{4}\qquad\mbox{for
any distinct pair of indices $j\neq k$.}$

See Lemma 4 in the paper [24].

Having constructed the packing, we then need to control the pairwise KL
divergence. Fix an index $j\in[M]$. Let $P\times\mathscr{L}_{j}$ denote the
joint distribution over the observed data $\\{(x_{i},y_{i})\\}_{1\leq i\leq
n}$ when the true function arises from $\theta^{j}$. Then for any pair of
distinct indices $j\neq k$, we have the upper bound

$\displaystyle\mathsf{KL}(P\times\mathscr{L}_{j}\|P\times\mathscr{L}_{k})=\frac{n}{2\sigma^{2}}\cdot\mathbb{E}_{X\sim
P}\Big{[}\big{(}(\theta^{j}-\theta^{k})^{\top}\phi(X)\big{)}^{2}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\frac{n}{2\sigma^{2}B}\|\theta^{j}-\theta^{k}\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\frac{2nr^{2}}{\sigma^{2}B},$

where step (i) follows from the definition of $P$; and step (ii) follows from
applying the triangle inequality, and the fact that $\|\theta\|_{2}\leq r$ for
all $\theta\in\mathscr{E}(r)$.

Consequently, we arrive at the lower bound
$\inf_{\widehat{f}}\sup_{f^{\star}\in\mathcal{F}}\mathbb{E}[\|\widehat{f}-f^{\star}\|_{Q}^{2}]\geq\frac{r^{2}}{8}$,
valid for any sample size satisfying the condition

$\displaystyle\frac{2nr^{2}}{\sigma^{2}B}+\log 2\leq\frac{1}{2}\log
M=\frac{d_{n}}{128}.$ (47)

By the definition of a regular kernel, we have $d_{n}\geq
c\frac{n\delta_{n}^{2}}{B\sigma^{2}}$ for a universal constant $c$.
Furthermore, since $\delta_{n}$ satisfies the lower bound $\delta_{n}^{2}\geq
c^{\prime}\frac{\sigma^{2}B}{n}$, the condition (47) is met by setting
$r^{2}=c_{1}\delta_{n}^{2}$ for some sufficiently small constant $c_{1}>0$.

##  Appendix B Proof of Theorem 3

Let the sample size $n\geq 1$ and likelihood ratio bound $B\geq 1$ be given.
Our failure instance relies on a function class $\mathcal{F}_{n}$, together
with a pair of distributions $(P,Q)$. The function class $\mathcal{F}_{n}$ is
the unit ball of a RKHS with finite-rank kernel, over the hypercube
$\\{-1,+1\\}^{n}$. The kernel is given by
$\mathscr{K}(x,z)\coloneqq\sum_{j=1}^{n}\mu_{j}\phi_{j}(x)\phi_{j}(z)$. The
eigenfunctions and eigenvalues are

$\displaystyle\phi_{j}(x)=x_{j},\quad\mbox{and}\quad\mu_{j}=\frac{1}{j^{2}},\quad\mbox{for}\leavevmode\nobreak\
j=1,\ldots,n.$

To be clear, the function class is given by

$\displaystyle\mathcal{F}_{n}\coloneqq\\{\,f\coloneqq\sum_{j=1}^{n}\theta_{j}\phi_{j}\mid\sum_{j=1}^{n}\tfrac{\theta_{j}^{2}}{\mu_{j}}\leq
1\,\\}.$

The target distribution, $Q$, is the uniform distribution on
$\\{-1,+1\\}^{n}$. The source distribution is a product distribution,
$P=\otimes_{j=1}^{n}P_{j}$. We take $P_{j}$ to be uniform on $\\{+1,-1\\}$,
when $j>1$. On the other hand, the first coordinate follows the distribution

$\displaystyle
P_{1}\coloneqq\Big{(}1-\frac{1}{B}\Big{)}\delta_{0}+\frac{1}{B}\mathrm{Unif}(\\{-1,+1\\}).$

It is immediate that $(P,Q)$ have $B$-bounded likelihood ratio.

Given this set-up, our first step is to reduce the lower bound to the
separation of a single coordinate of the parameter associated with the
empirical risk minimizer and a single coordinate of the parameter associated
with a hard instance in the function class of interest $\mathcal{F}_{n}$. We
introduce a one-dimensional minimization problem that governs this separation
problem and allows us to establish our result.

###  B.1 Reduction to a one dimensional separation problem

To establish our lower bound it suffices to consider the following “hard”
function

$f^{\star}_{\mathrm{hard}}(x)=x_{1}=\sum_{j=1}^{n}({\theta^{\star}_{\mathrm{hard}}})_{j}\phi_{j}(x),\quad\mbox{where}\quad{\theta^{\star}_{\mathrm{hard}}}=(1,0,\dots,0)\in\mathbb{R}^{n}.$

Since $\phi_{j}(x)=x_{j}$ and $\mu_{j}=j^{-2}$, it follows that
$f^{\star}_{\mathrm{hard}}\in\mathcal{F}_{n}$. We can write
$\widehat{f}_{\mathrm{\scriptsize{erm}}}(x)=\sum_{j=1}^{n}(\widehat{\theta}_{\mathrm{\scriptsize{erm}}})_{j}x_{j}$,
where we defined

$\widehat{\theta}_{\mathrm{\scriptsize{erm}}}\coloneqq\arg\min\Big{\\{}\,\sum_{i=1}^{n}\big{(}\sum_{j=1}^{n}\theta_{j}x_{ij}-y_{i}\big{)}^{2}\mid\sum_{j=1}^{n}\tfrac{\theta_{j}^{2}}{\mu_{j}}\leq
1\,\Big{\\}}.$ (48)

Putting these pieces together, we see that

$\sup_{f^{\star}\in\mathcal{F}_{n}}\mathbb{E}\Big{[}\|\widehat{f}_{\mathrm{\scriptsize{erm}}}-f^{\star}\|_{Q}^{2}\Big{]}\geq\mathbb{E}\Big{[}\|\widehat{f}_{\mathrm{\scriptsize{erm}}}-f^{\star}_{\mathrm{hard}}\|_{Q}^{2}\Big{]}\stackrel{{\scriptstyle{\rm(i)}}}{{=}}\mathbb{E}\Big{[}\|\widehat{\theta}_{\mathrm{\scriptsize{erm}}}-{\theta^{\star}_{\mathrm{hard}}}\|_{2}^{2}\Big{]}\stackrel{{\scriptstyle{\rm(ii)}}}{{\geq}}\mathbb{E}\Big{[}\big{(}(\widehat{\theta}_{\mathrm{\scriptsize{erm}}})_{1}-\theta^{\star}_{1}\big{)}^{2}\Big{]}.$
(49)

Above, the relation (i) is a consequence of Parseval’s theorem, along with the
orthonormality of $\\{\phi_{j}\\}_{j=1}^{n}$ in $L^{2}(Q)$. Inequality (ii)
follows by dropping terms corresponding to indices indices $j>1$. Therefore,
in view of display (49), it suffices to show that:

$\mathbb{P}\Big{\\{}\big{(}(\widehat{\theta}_{\mathrm{\scriptsize{erm}}})_{1}-1\big{)}^{2}\geq
c_{3}\frac{B^{3}}{n^{2}}\Big{\\}}\geq\frac{1}{2}.$ (50)

###  B.2 Proof of one-dimensional separation bound (50)

We begin with a proof outline.

##### Proof outline

To establish (50), we can assume
$(\widehat{\theta}_{\mathrm{\scriptsize{erm}}})_{1}\in[0,1]$; otherwise, the
lower bound follows trivially, provided $c_{2}$ is sufficiently small, in
particular, $c_{2}\leq\sqrt[3]{1/c_{3}}$. We introduce a bit of notation:

$\widehat{\bm{\Sigma}}_{P}\coloneqq\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}\quad\mbox{and}\quad
v\coloneqq\frac{1}{n}\sum_{i=1}^{n}w_{i}x_{i}.$

Thus, we can further restrict the empirical risk minimization problem (48) to

$\displaystyle\tilde{\theta}$
$\displaystyle\coloneqq\arg\min\Big{\\{}\,\sum_{i=1}^{n}\big{(}\sum_{j=1}^{n}\theta_{j}x_{ij}-y_{i}\big{)}^{2}\mid\sum_{j=1}^{n}\frac{\theta_{j}^{2}}{\mu_{j}}\leq
1,\leavevmode\nobreak\ \leavevmode\nobreak\ \theta_{1}\in[0,1]\,\Big{\\}}$
$\displaystyle=\arg\min\bigg{\\{}\,(\theta-\theta^{\star})^{T}\widehat{\bm{\Sigma}}_{P}(\theta-\theta^{\star})-2v^{T}(\theta-\theta^{\star})\mid\sum_{j=1}^{n}\frac{\theta_{j}^{2}}{\mu_{j}}\leq
1,\leavevmode\nobreak\ \leavevmode\nobreak\ \theta_{1}\in[0,1]\,\bigg{\\}}.$
(51)

Indeed, in order to prove inequality (50), it suffices to show that

$\mathbb{P}\Big{\\{}\big{(}\tilde{\theta}_{1}-1\big{)}^{2}\geq
c_{3}\frac{B^{3}}{n^{2}}\Big{\\}}\geq\frac{1}{2}.$ (52)

Let us define an auxiliary function $g\colon[0,1]\to\mathbb{R}$, given by

$g(t)\coloneqq\inf\Big{\\{}(\theta-\theta^{\star})^{T}\widehat{\bm{\Sigma}}_{P}(\theta-\theta^{\star})-2v^{T}(\theta-\theta^{\star})\mid\sum_{j=1}^{n}\frac{\theta_{j}^{2}}{\mu_{j}}\leq
1,\leavevmode\nobreak\ \leavevmode\nobreak\ \theta_{1}=t\Big{\\}}.$ (53)

By definition (51), the choice $\tilde{\theta}$ minimizes this objective, and
therefore $\inf_{t\in[0,1]}g(t)=g(\tilde{\theta}_{1})$. The next two lemmas
concern the minimum value and minimizer of $g$. Lemma 4, which we prove in
section B.4.1, bounds the minimal value from above. Lemma 5, demonstrates that
there is an interval of length order $\sqrt{B^{3}/n^{2}}$ on which the
function $g$ is bounded away from the minimal value. We prove this result in
Section B.4.2.

\begin{overpic}[scale={0.5},unit=1mm]{separation}
\put(74.0,35.0){\scalebox{0.9}{$g(t)$}}
\put(-1.5,18.0){\scalebox{0.75}{\color[rgb]{.75,0,.25}
$-c^{*}\frac{\sqrt{B}}{n}$}} \put(98.0,61.5){\scalebox{0.75}{$t$}}
\put(25.0,66.2){\scalebox{0.8}{\color[rgb]{0,0,1} $\tilde{\theta}_{1}$}}
\put(53.0,66.2){\scalebox{0.8}{\color[rgb]{1,0,0}
$\theta^{\star}_{1}-\tfrac{\sqrt{c_{3}B^{3}}}{n}$}}
\put(80.0,66.2){\scalebox{0.8}{{$\theta^{\star}_{1}$}}} \end{overpic} Figure
3: Pictorial representation of lower bound argument, separating the first
coordinate of empirical risk minimizer, $\tilde{\theta}_{1}$, from the true
population minimizer $\theta^{\star}_{1}$. Lemma 4 establishes the upper
bound, depicted in purple above, on the minimal value of $g$. Lemma 5
establishes an interval, shown between the red dashed line and
$\theta^{\star}_{1}$ above, which excludes $\tilde{\theta}_{1}$. This allows
us to ensure that $\theta^{\star}_{1}$ and $\tilde{\theta}_{1}$ are
sufficiently separated.

######  Lemma 4 (Minimal value of empirical objective).

There is a constant $c^{*}>0$ such that

$\displaystyle g(\tilde{\theta}_{1})$
$\displaystyle\leq-c^{*}\frac{\sqrt{B}}{n}$

holds with probability at least $3/4$.

######  Lemma 5 (Separation from $\theta^{\star}_{1}$).

There exists a constant $c_{3}>0$ such that

$\displaystyle\inf_{\begin{subarray}{c}t\in[0,1]\\\ (1-t)^{2}\leq
c_{3}B^{3}/n^{2}\end{subarray}}g(t)>-c^{*}\frac{\sqrt{B}}{n}.$ (54)

where probability at least $3/4$.

Note that the constant $c^{*}$ used in Lemmas 4 and 5 is the same. Thus—after
union bounding over the two error events—with probability at least $1/2$,

$g(\tilde{\theta}_{1})<\inf_{\begin{subarray}{c}t\in[0,1]\\\ (1-t)^{2}\leq
c_{3}B^{3}/n^{2}\end{subarray}}g(t).$

Recalling that $\tilde{\theta}_{1}\in[0,1]$, we conclude on this event that
$(1-\tilde{\theta}_{1})^{2}\geq c_{3}\tfrac{B^{3}}{n^{2}}$, which furnishes
(52), and thereby establishes the required result. To complete the proof, it
then remains to establish the auxiliary lemmas stated above. Before doing so,
we record a useful lemma, which will be used multiple times later.

###  B.3 A useful lemma

######  Lemma 6.

For any quantity $\alpha\in(\frac{B}{4n^{2}},\frac{B}{4})$, with probability
at least $1-c_{1}\exp\big{(}-c_{2}\frac{B^{1/2}}{\alpha^{1/2}}\big{)}$, one
has

$\displaystyle
c\frac{B^{1/2}}{\alpha^{1/2}}\frac{1}{n}\leq\sum_{j=2}^{n}\frac{(v_{j})^{2}}{1+\frac{\alpha}{B\mu_{j}}}\leq
C\frac{B^{1/2}}{\alpha^{1/2}}\frac{1}{n}.$

Here $c_{1},c_{2},C,c>0$ are absolute constants.

###### Proof.

For each $j\geq 1$, define
$\eta_{j}\coloneqq\big{(}1+\frac{\alpha}{B\mu_{j}}\big{)}^{-1}$. We focus on
controlling the term

$\displaystyle\sum_{j=2}^{n}\eta_{j}\left[(\sqrt{n}v_{j})^{2}-1\right].$

Recall from the definition of $v$ that
$v_{j}=\frac{1}{n}\sum_{i=1}^{n}w_{i}x_{ij}.$ Under the construction of the
lower bound instance, we have
$\sqrt{n}v_{j}\stackrel{{\scriptstyle\mathsf{i.i.d.}}}{{\sim}}\mathcal{N}(0,1)$.
Therefore $\sqrt{n}v_{j})^{2}-1$ is a mean-zero sub-exponential random
variable. This allows us to invoke Bernstein’s inequality to obtain

$\displaystyle\mathbb{P}\left(\left|\sum_{j=2}^{n}\eta_{j}\left[(\sqrt{n}v_{j})^{2}-1\right]\right|\geq
t\right)\leq 2\exp\left\\{-c\min\left(\frac{t^{2}}{\sum_{j\geq
2}\eta_{j}^{2}},\frac{t}{\max_{j}\eta_{j}}\right)\right\\},$

where $c>0$ is some universal constant.

We claim that there exist three constants $C_{1},C_{2},C_{3}>0$ such that

$\displaystyle\max_{j=2,\ldots,n}\eta_{j}$ $\displaystyle\leq 1;$ (55a)
$\displaystyle\sum_{j=2}^{n}\eta_{j}^{2}$ $\displaystyle\leq
C_{1}\frac{B^{1/2}}{\alpha^{1/2}};$ (55b) $\displaystyle
C_{2}\frac{B^{1/2}}{\alpha^{1/2}}\leq\sum_{j=2}^{n}\eta_{j}$
$\displaystyle\leq C_{3}\frac{B^{1/2}}{\alpha^{1/2}}.$ (55c)

As a result, we can $t=c_{0}\frac{B^{1/2}}{\alpha^{1/2}}$ with $c_{0}$
sufficiently small to arrive at the desired conclusion.

We are left with proving the claimed relations (55). The first relation (55a)
is trivial. We provide the proof of the third inequalities (55c); the proof of
the middle one (cf. relation (55b)) follows by a similar argument. Since
$\alpha\in(\frac{B}{4n^{2}},\frac{B}{4})$, we can decompose the sum into

$\displaystyle\sum_{j=2}^{n}\eta_{j}=\sum_{j=2}^{\lfloor\sqrt{B/\alpha}\rfloor}\frac{1}{1+\frac{\alpha}{B\mu_{j}}}+\sum_{j=\lfloor\sqrt{B/\alpha}\rfloor+1}^{n}\frac{1}{1+\frac{\alpha}{B\mu_{j}}}.$

Recall that $\mu_{j}=j^{-2}$. We thus have $1\geq\frac{\alpha}{B\mu_{j}}$ for
$j\leq\lfloor\sqrt{B/\alpha}\rfloor$ and $1\leq\frac{\alpha}{B\mu_{j}}$ for
$j\geq\lfloor\sqrt{B/\alpha}\rfloor$. These allow us to upper bound
$\sum_{j=2}^{n}\eta_{j}$ as

$\displaystyle\sum_{j=2}^{n}\eta_{j}\leq\lfloor\sqrt{B/\alpha}\rfloor+\frac{B}{\alpha}\sum_{j=\lfloor\sqrt{B/\alpha}\rfloor+1}^{n}\frac{1}{j^{2}}\leq
C_{3}\frac{B^{1/2}}{\alpha^{1/2}}.$

Similarly, we have the lower bound

$\displaystyle\sum_{j=2}^{n}\eta_{j}\geq\sum_{j=2}^{\lfloor\sqrt{B/\alpha}\rfloor}\frac{1}{1+\frac{\alpha}{B\mu_{j}}}\geq\frac{1}{2}\lfloor\sqrt{B/\alpha}\rfloor\geq
C_{2}\frac{B^{1/2}}{\alpha^{1/2}}.$

This finishes the proof. ∎

###  B.4 Proof of auxiliary lemmas

In order to facilitate the proofs of these lemmas, it is useful to decompose
$\theta=(\theta_{1},\theta_{\mathsf{R}})\in\mathbb{R}\times\mathbb{R}^{n-1}$.
Additionally, we consider the constraint set

$\displaystyle\mathcal{C}(t)\coloneqq\Big{\\{}\theta_{\mathsf{R}}\in\mathbb{R}^{n-1}\mid\sum_{j=2}^{n}\frac{\theta_{j}^{2}}{\mu_{j}}\leq
1-t^{2}\Big{\\}},\quad\mbox{where}\leavevmode\nobreak\ t\in[0,1].$

This set plays a key role. In view of definition (53), we can write

$g(t)=\inf_{\theta_{\mathsf{R}}\in\mathcal{C}(t)}\,\left\\{\begin{bmatrix}t-1\\\
\theta_{\mathsf{R}}\end{bmatrix}^{\top}\widehat{\bm{\Sigma}}_{P}\begin{bmatrix}t-1\\\
\theta_{\mathsf{R}}\end{bmatrix}-2\begin{bmatrix}t-1\\\
\theta_{\mathsf{R}}\end{bmatrix}^{\top}v\right\\},$ (56)

where above we have used $\theta^{\star}=(1,0,\dots,0)$. Finally, we will use
the diagonal matrix of kernel eigenvalues
$\bm{M}\coloneqq\mathsf{diag}(\mu_{1},\mu_{2},\dots,\mu_{n})$, repeatedly.

####  B.4.1 Proof of Lemma 4

We show that with probability at least $3/4$,

$g(\omega)\leq-c^{*}\frac{\sqrt{B}}{n},\quad\mbox{where}\quad\omega\coloneqq\sqrt{1-\frac{B^{3/2}}{n}}.$
(57)

When $n^{2}\geq B^{3}$, we have $\omega\in[0,1]$. Since
$\inf_{t\in[0,1]}g(t)\leq g(\omega)$, the display (57) implies the result.

##### Proof of bound (57):

From the proof of Lemma 1, if we set $\lambda\coloneqq C\frac{\log n}{n}$ for
some constant $C>0$, then we have

$\displaystyle\tfrac{1}{2}(\bm{\Sigma}_{P}+\lambda\bm{M}^{-1})\preceq\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1}\preceq\tfrac{3}{2}(\bm{\Sigma}_{P}+\lambda\bm{M}^{-1}),$
(58)

with probability at least $1-\tfrac{1}{n}$. Consequently, for any vector
$\theta$ obeying $\theta^{\top}\bm{M}^{-1}\theta\leq 1$, we have the upper
bound

$\displaystyle\left(\theta-\theta^{\star}\right)^{\top}\widehat{\bm{\Sigma}}_{P}\left(\theta-\theta^{\star}\right)$
$\displaystyle=\left(\theta-\theta^{\star}\right)^{\top}\left(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1}\right)\left(\theta-\theta^{\star}\right)-\lambda\left(\theta-\theta^{\star}\right)^{\top}\bm{M}^{-1}\left(\theta-\theta^{\star}\right)$
$\displaystyle\leq\frac{3}{2}\left(\theta-\theta^{\star}\right)^{\top}(\bm{\Sigma}_{P}+\lambda\bm{M}^{-1})\left(\theta-\theta^{\star}\right)-\lambda\left(\theta-\theta^{\star}\right)^{\top}\bm{M}^{-1}\left(\theta-\theta^{\star}\right)$
$\displaystyle=\frac{3}{2}\left(\theta-\theta^{\star}\right)^{\top}\bm{\Sigma}_{P}\left(\theta-\theta^{\star}\right)+\frac{\lambda}{2}\left(\theta-\theta^{\star}\right)^{\top}\bm{M}^{-1}\left(\theta-\theta^{\star}\right)$
$\displaystyle\leq\frac{3}{2}\left(\theta-\theta^{\star}\right)^{\top}\bm{\Sigma}_{P}\left(\theta-\theta^{\star}\right)+2\lambda,$

where the final inequality holds since
$\left(\theta-\theta^{\star}\right)^{\top}\bm{M}^{-1}\left(\theta-\theta^{\star}\right)\leq
4$. Applying this result with the vector
$\theta=(\omega,\theta_{\mathsf{R}})^{\top}$ yields

$\displaystyle g(\omega)$
$\displaystyle\leq\min_{\theta_{\mathsf{R}}\in\mathcal{C}}\left\\{\frac{3}{2}\left[\begin{array}[]{c}\omega-1\\\
\theta_{\mathsf{R}}\end{array}\right]^{\top}\bm{\Sigma}_{P}\left[\begin{array}[]{c}\omega-1\\\
\theta_{\mathsf{R}}\end{array}\right]-2\left[\begin{array}[]{c}\omega-1\\\
\theta_{\mathsf{R}}\end{array}\right]^{\top}v+2\lambda\right\\}$ (65)
$\displaystyle=T_{1}(\omega)+T_{2}(\omega)+2\lambda+\min_{\theta_{\mathsf{R}}\in\mathcal{C}}T_{3}(\theta_{\mathsf{R}}).$
(66)

Above, we have defined

$\displaystyle T_{1}(\omega)\coloneqq\frac{3}{2}\frac{(\omega-1)^{2}}{B},\quad
T_{2}(\omega)\coloneqq-2v_{1}(\omega-1),\quad\mbox{and}\quad
T_{3}(\theta_{\mathsf{R}})\coloneqq\frac{3}{2}\|\theta_{\mathsf{R}}\|_{2}^{2}-2v_{\mathsf{R}}^{\top}\theta_{\mathsf{R}},$
(67)

and we have used the decomposition $v=(v_{1},v_{\mathsf{R}})^{\top}$. We now
bound each of these three terms in turn.

##### Controlling the term $T_{1}(\omega)$:

Recall $\omega\in[0,1]$ satisfies the equality
$1-\omega^{2}=\frac{B^{3/2}}{n}$. Consequently, we have

$\displaystyle
T_{1}(\omega)=\frac{3}{2}\frac{(1-\omega)^{2}}{B}\leq\frac{3}{2}\frac{(1-\omega^{2})^{2}}{B}=\frac{3}{2}\frac{B^{2}}{n^{2}}.$
(68)

##### Controlling the term $T_{2}(\omega)$:

For the second term, by definition of $\omega$, we have

$\displaystyle T_{2}(\omega)=2v_{1}(1-\omega)\leq 2|v_{1}|(1-\omega)\leq
2|v_{1}|(1-\omega^{2})=2|v_{1}|\cdot\frac{B^{3/2}}{n}.$ (69)

We have the following lemma to control the size of $|v_{1}|$.

######  Lemma 7.

The following holds true with probability at least 0.99

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}w_{i}x_{i1}\right|\leq\frac{10}{\sqrt{nB}}.$

###### Proof.

In view of the construction of the lower bound instance, we can calculate

$\displaystyle\mathbb{E}\left[\left(\frac{1}{n}\sum_{i=1}^{n}w_{i}x_{i1}\right)^{2}\right]=\frac{1}{n^{2}}\sum_{i=1}^{n}\mathbb{E}\left[w_{i}^{2}x_{i1}^{2}\right]=\frac{1}{nB}.$

The claim then follows from Chebyshev’s inequality. ∎

Lemma 7 demonstrates that $|v_{1}|\leq\tfrac{10}{\sqrt{nB}}$, with probability
at least $99/100$. Therefore, on this event, the bound (69) guarantees

$T_{2}(\omega)\leq 20\frac{B}{n^{3/2}}.$ (70)

##### Controlling the term $T_{3}(\theta_{r})$:

Our final step is to upper bound the constrained minimum
$\min\limits_{\theta_{\mathsf{R}}\in\mathcal{C}}T_{3}(\theta_{\mathsf{R}})$.
Since this minimization problem is strictly feasible, Lagrange duality
guarantees that

$\displaystyle\min_{\theta_{\mathsf{R}}\in\mathcal{C}}T_{3}(\theta_{\mathsf{R}})$
$\displaystyle=\min_{\theta_{\mathsf{R}}}\max_{\xi\geq
0}\left\\{\frac{3}{2}\|\theta_{\mathsf{R}}\|_{2}^{2}-2v_{\mathsf{R}}^{\top}\theta_{\mathsf{R}}+\xi(\theta_{\mathsf{R}}^{\top}\bm{M}_{\mathsf{R}}^{-1}\theta_{\mathsf{R}}-\frac{B^{3/2}}{n})\right\\}$
$\displaystyle=\max_{\xi\geq
0}\min_{\theta_{\mathsf{R}}}\left\\{\frac{3}{2}\|\theta_{\mathsf{R}}\|_{2}^{2}-2v_{\mathsf{R}}^{\top}\theta_{\mathsf{R}}+\xi(\theta_{\mathsf{R}}^{\top}\bm{M}_{\mathsf{R}}^{-1}\theta_{\mathsf{R}}-\frac{B^{3/2}}{n})\right\\}.$

The inner minimum is achieved at
$\theta_{\mathsf{R}}=\left[\frac{3}{2}\bm{I}+\xi\bm{M}_{\mathsf{R}}^{-1}\right]^{-1}v_{\mathsf{R}}$,
so that we have established the equality

$\displaystyle\min_{\theta_{\mathsf{R}}\in\mathcal{C}}T_{3}(\theta_{\mathsf{R}})$
$\displaystyle=\max_{\xi\geq
0}\left\\{-\xi\tfrac{B^{3/2}}{n}-v_{\mathsf{R}}^{\top}\left[\tfrac{3}{2}\bm{I}+\xi\bm{M}_{\mathsf{R}}^{-1}\right]^{-1}v_{\mathsf{R}}\right\\}\;=\;\max_{\xi\geq
0}\left\\{-\xi\frac{B^{3/2}}{n}-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\frac{3}{2}+\tfrac{\xi}{\mu_{j}}}\right\\}.$

It remains to analyze the maximum over the dual variable $\xi$, and we split
the analysis into two cases.

  * •

Case 1: First, suppose that the maximum is achieved at some
$\xi^{\star}\geq\tfrac{1}{B}$. In this case, we have

$\displaystyle\max_{\xi\geq
0}\left\\{-\xi\tfrac{B^{3/2}}{n}-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\tfrac{3}{2}+\tfrac{\xi}{\mu_{j}}}\right\\}\leq-\xi^{\star}\frac{B^{3/2}}{n}\leq-\frac{B^{1/2}}{n}.$

  * •

Case 2: Otherwise, we may assume that the maximum achieved at some
$\xi^{\star}\in[0,\tfrac{1}{B}]$, in which case we have

$\displaystyle\max_{\xi\geq
0}\left\\{-\xi\tfrac{B^{3/2}}{n}-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\tfrac{3}{2}+\tfrac{\xi}{\mu_{j}}}\right\\}\leq-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\tfrac{3}{2}+\tfrac{\xi^{\star}}{\mu_{j}}}\leq-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\tfrac{3}{2}+\frac{1}{B\mu_{j}}}\leq-c\frac{B^{1/2}}{n},$

where $c>0$ is a constant. Here in view of Lemma 6, the last inequality holds
with probability at least 0.9 as long as $B$ is sufficiently large.

Combining the two cases, we arrive at the conclusion that as long as $B$ is
sufficiently large, with probability at least 0.9,

$\min_{\theta_{\mathsf{R}}\in\mathcal{C}}T_{3}(\theta_{\mathsf{R}})\leq-
c_{1}\frac{B^{1/2}}{n}$ (71)

for some constant $c_{1}>0$.

##### Completing the proof:

We can now combine bounds (68), (70), and (71) on the terms
$T_{1},T_{2},T_{3}$, respectively. Note that when $n\geq 7B^{3/2}\geq 7$, all
three events and the upper bound (66) hold simultaneously, with probability
$1-(\tfrac{1}{n}+\tfrac{1}{100}+\tfrac{1}{10})\geq 3/4$. Therefore, we obtain

$\displaystyle g(\omega)$
$\displaystyle\leq\frac{3}{2}\frac{B^{2}}{n^{2}}+20\frac{B}{n^{3/2}}-c_{1}\frac{B^{1/2}}{n}+C\frac{\log
n}{n}$ $\displaystyle\leq-\frac{c_{1}}{2}\frac{B^{1/2}}{n}.$

The final inequality above holds, since $B\geq c_{1}(\log n)^{2}$ and $n\geq
7B^{3/2}$, for sufficiently large $c_{1}>0$.

####  B.4.2 Proof of Lemma 5

We will prove the slightly stronger claim that with probability at least
$3/4$, we have

$\inf_{\begin{subarray}{c}t\in[0,1]\\\ 1-t^{2}\leq\beta
B^{3/2}/n\end{subarray}}g(t)>-c^{*}\frac{\sqrt{B}}{n}$ (72)

To see that this proves the claim, note that
$\sup_{t\in[0,1]}\tfrac{(1-t^{2})^{2}}{(1-t)^{2}}=4$ Therefore, if
$(1-t)^{2}\leq\tfrac{\beta^{2}}{4}\tfrac{B^{3}}{n^{2}}$, then
$(1-t^{2})^{2}\leq\beta^{2}\tfrac{B^{3}}{n^{2}}$. Hence, (72) proves the claim
as soon as $c_{3}=\beta^{2}/4$.

##### Proof of bound (72):

On the event (58), if $\theta=(\theta_{1},\theta_{\mathsf{R}})^{\top}$ obeys
$\theta^{\top}\bm{M}^{-1}\theta\leq 1$, then we have the lower bound

$\displaystyle\left(\theta-\theta^{\star}\right)^{\top}\widehat{\bm{\Sigma}}_{P}\left(\theta-\theta^{\star}\right)$
$\displaystyle=\left(\theta-\theta^{\star}\right)^{\top}\left(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1}\right)\left(\theta-\theta^{\star}\right)-\lambda\left(\theta-\theta^{\star}\right)^{\top}\bm{M}^{-1}\left(\theta-\theta^{\star}\right)$
$\displaystyle\geq\frac{1}{2}\left(\theta-\theta^{\star}\right)^{\top}(\bm{\Sigma}_{P}+\lambda\bm{M}^{-1})\left(\theta-\theta^{\star}\right)-\lambda\left(\theta-\theta^{\star}\right)^{\top}\bm{M}^{-1}\left(\theta-\theta^{\star}\right)$
$\displaystyle=\frac{1}{2}\left(\theta-\theta^{\star}\right)^{\top}\bm{\Sigma}_{P}\left(\theta-\theta^{\star}\right)-\frac{\lambda}{2}\left(\theta-\theta^{\star}\right)^{\top}\bm{M}^{-1}\left(\theta-\theta^{\star}\right)$
$\displaystyle\geq\frac{1}{2}\left(\theta-\theta^{\star}\right)^{\top}\bm{\Sigma}_{P}\left(\theta-\theta^{\star}\right)-2\lambda,$

valid when $\lambda=C\tfrac{\log n}{n}$ for some constant $C>0$. Consequently,
we have

$\displaystyle g(\theta_{1})$
$\displaystyle\geq\min_{\theta_{\mathsf{R}}\in\mathcal{C}(\theta_{1})}\left\\{\frac{1}{2}\left(\theta-\theta^{\star}\right)^{\top}\bm{\Sigma}_{P}\left(\theta-\theta^{\star}\right)-2\left(\theta-\theta^{\star}\right)^{\top}v-2\lambda\right\\}$
$\displaystyle=\min_{\theta_{\mathsf{R}}\in\mathcal{C}(\theta_{1})}\left\\{\frac{1}{2}\frac{(\theta_{1}-1)^{2}}{B}-2v_{1}(\theta_{1}-1)+\frac{1}{2}\|\theta_{\mathsf{R}}\|_{2}^{2}-2v_{\mathsf{R}}^{\top}\theta_{\mathsf{R}}-2\lambda\right\\}$
$\displaystyle\geq-
T_{2}(\theta_{1})-2\lambda+\min_{\theta_{\mathsf{R}}\in\mathcal{C}(\theta_{1})}\\{\frac{1}{2}\|\theta_{\mathsf{R}}\|_{2}^{2}-2v_{\mathsf{R}}^{\top}\theta_{\mathsf{R}}\\}.$
(73)

where the last line identifies $-2v_{1}(\theta_{1}-1)$ with
$T_{2}(\theta_{1})$ (cf. definition (67)).

We separate the proof into two cases—mainly to get around the duality issue.

##### Case 1: $\theta_{1}=1$.

In this case, we have

$\displaystyle g(\theta_{1})\geq-2\lambda=-\frac{2C\log n}{n}.$ (74)

##### Case 2: $\theta_{1}\in[0,1)$.

We lower bound the terms in equation (73) in turn.

  * •

Lower bounding $T_{2}(\theta_{1})$. For any
$0<1-\theta_{1}^{2}\leq\beta\frac{B^{3/2}}{n}$, the following relation

$\displaystyle T_{2}(\theta_{1})\geq-2|v_{1}|\cdot|\theta_{1}-1|$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\geq}}-2|v_{1}|\cdot\left(1-\theta_{1}^{2}\right)\stackrel{{\scriptstyle(ii)}}{{\geq}}-20\beta\frac{B}{n^{3/2}}$

holds with probability at least 0.99. Here step (i) uses the fact that

$\displaystyle|\theta_{1}-1|=|1-\sqrt{1-(1-\theta_{1}^{2})}|\leq
1-\theta_{1}^{2}\qquad\text{for all }\quad\theta_{1}\in[0,1],$

and step (ii) relies on Lemma 7 and the constraint
$1-\theta_{1}^{2}\leq\beta\frac{B^{3/2}}{n}$.

  * •

Lower bounding
$\min_{\theta_{\mathsf{R}}\in\mathcal{C}^{\prime}(\theta_{1})}\\{\tfrac{1}{2}\|\theta_{\mathsf{R}}\|_{2}^{2}-2v_{\mathsf{R}}^{\top}\theta_{\mathsf{R}}\\}$.
When $\theta_{1}\in[0,1)$, the constraint set
$\mathcal{C}^{\prime}(\theta_{1})$ has non-empty interior, and the
minimization over $\theta_{\mathsf{R}}$ is strictly feasible. In this case,
strict duality holds so that

$\displaystyle\min_{\theta_{\mathsf{R}}\in\mathcal{C}^{\prime}(\theta_{1})}\left\\{\tfrac{1}{2}\|\theta_{\mathsf{R}}\|_{2}^{2}-2v_{\mathsf{R}}^{\top}\theta_{\mathsf{R}}\right\\}$
$\displaystyle=\max_{\xi\geq
0}\left\\{-\xi(1-\theta_{1}^{2})-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\tfrac{1}{2}+\tfrac{\xi}{\mu_{j}}}\right\\}$
$\displaystyle\geq-\left[n(1-\theta_{1}^{2})\right]^{-2/3}(1-\theta_{1}^{2})-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\tfrac{1}{2}+\tfrac{\left(n\left(1-\theta_{1}^{2}\right)\right)^{-2/3}}{\mu_{j}}}$
$\displaystyle=-\tfrac{\left(1-\theta_{1}^{2}\right)^{1/3}}{n^{2/3}}-\sum_{j=2}^{n}\tfrac{(v_{j})^{2}}{\tfrac{1}{2}+\tfrac{\left(n\left(1-\theta_{1}^{2}\right)\right)^{-2/3}}{\mu_{j}}}.$

Here the second line arises from a particular choice of $\xi$, namely
$\xi=\left(n(1-\theta_{1}^{2})\right)^{-2/3}.$ Since
$1-\theta_{1}^{2}\leq\beta\frac{B^{3/2}}{n}$, we further have

$\displaystyle-\frac{\left(1-\theta_{1}^{2}\right)^{1/3}}{n^{2/3}}-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\frac{1}{2}+\frac{\left(n\left(1-\theta_{1}^{2}\right)\right)^{-2/3}}{\mu_{j}}}$
$\displaystyle\geq-\frac{\beta^{1/3}B^{1/2}}{n}-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\frac{1}{2}+\frac{\left(\beta
B^{3/2}\right)^{-2/3}}{\mu_{j}}}$
$\displaystyle=-\frac{\beta^{1/3}B^{1/2}}{n}-\sum_{j=2}^{n}\frac{(v_{j})^{2}}{\frac{1}{2}+\frac{1}{\beta^{2/3}B\mu_{j}}}$
$\displaystyle\geq-\tilde{C}\frac{\beta^{1/3}B^{1/2}}{n},$

where $\tilde{C}>0$ is a constant. Here, since $B$ is sufficiently large,
Lemma 6 guarantees that the last inequality holds with probability at least
0.9.

Combining the two cases above, we arrive at the conclusion that for any
$1-\theta_{1}^{2}\leq\beta\frac{B^{3/2}}{n}$,

$\displaystyle g(\theta_{1})\geq-20\beta\frac{B}{n^{3/2}}-2C\frac{\log
n}{n}-\tilde{C}\frac{\beta^{1/3}B^{1/2}}{n}.$

Under the assumptions that $B\geq C_{1}(\log n)^{2}$ and $n\geq C_{2}B^{3/2}$
for some sufficiently large constants $C_{1},C_{2}>0$, we can choose $\beta$
sufficiently small so as to make sure that

$\displaystyle g(\theta_{1})\geq-c^{*}\frac{B^{1/2}}{n}\qquad\text{for all
}\quad 1-\theta_{1}^{2}\leq\beta\frac{B^{3/2}}{n}.$

##  Appendix C Proofs of the bounds (39)

By definition, any function $h\in\mathcal{F}^{\star}$ obeys
$\|h\|_{\mathcal{H}}\leq 3\|f^{\star}\|_{\mathcal{H}}.$ In terms of the
expansion $h=\sum_{j=1}^{\infty}\theta_{j}\phi_{j}$, this constraint is
equivalent to the bound $\sum_{j=1}^{\infty}\theta_{j}^{2}/\mu_{j}\leq
9\|f^{\star}\|_{\mathcal{H}}^{2}$. In addition, the constraint $\|h\|_{Q}\leq
r$ implies that $\sum_{j=1}^{\infty}\theta_{j}^{2}\leq r^{2}$. In conjunction,
these two inequalities imply that

$\displaystyle\sum_{j=1}^{\infty}\frac{\theta_{j}^{2}}{\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}\leq
10,$

as claimed in inequality (39b).

We now use this inequality to establish the bound (39a). For any
$x\in\mathcal{X}$, we have

$\displaystyle|h(x)|=\Big{|}\sum_{j=1}^{\infty}\theta_{j}\phi_{j}(x)\Big{|}$
$\displaystyle=\Big{|}\sum_{j=1}^{\infty}\frac{\theta_{j}}{\sqrt{\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}}\cdot\sqrt{\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}\phi_{j}(x)\Big{|}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\sqrt{\sum_{j=1}^{\infty}\frac{\theta_{j}^{2}}{\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}}\cdot\sqrt{\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}\phi_{j}^{2}(x)}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\sqrt{10\sum_{j=1}^{\infty}\min\\{r^{2},\mu_{j}\|f^{\star}\|_{\mathcal{H}}^{2}\\}}.$

Here step (i) uses the Cauchy–Schwarz inequality, whereas step (ii) follows
from the previous claim (39b) and the assumption that $|\phi_{j}(x)|\leq 1$
for all $j\geq 1$.

##  Appendix D Performance guarantees for LR-reweighted KRR

In this section, we present the performance guarantee for the LR-reweighted
KRR estimate with truncation for all ranges of $\sigma^{2}$.

Similar to the large noise regime, we define

$\displaystyle\mathcal{M}^{\mathsf{new}}(\delta)$ $\displaystyle\coloneqq
c_{0}\sqrt{\tfrac{\sigma^{2}V^{2}\log^{3}(n)}{n}\Psi(\delta,\mu)}\;\left(\sqrt{\tfrac{\Psi(\delta,\mu)}{\sigma^{2}}}+1\right).$
(75)

Our theorem applies to any solution $\delta_{n}^{\mathsf{new}}>0$ to the
inequality $\mathcal{M}^{\mathsf{new}}(\delta)\leq\delta^{2}/2$.

######  Theorem 5.

Consider a kernel with sup-norm bounded eigenfunctions (19), and a source-
target pair with $\mathbb{E}_{P}[\rho^{2}(X)]\leq V^{2}$. Then the estimate
$\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}$ with truncation
${\tau_{n}}=\sqrt{nV^{2}}$ and regularization
$\lambda\|f^{\star}\|_{\mathcal{H}}^{2}=\delta_{n}^{2}/3$ satisfies the bound

$\displaystyle\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{Q}^{2}\leq\delta_{n}^{2}$
(76)

with probability at least $1-c\>n^{-10}$.

###### Proof.

Inspecting the proof of Theorem 4 (in particular, equation (38)), one has with
high probability that

$\displaystyle\sup_{\begin{subarray}{c}g\in\mathcal{G}(\delta_{n})\end{subarray}}\Big{\\{}\|g-f^{\star}\|_{Q}^{2}+\frac{1}{n}\sum_{i=1}^{n}\rho_{\tau_{n}}(x_{i})\big{[}\big{(}f^{\star}(x_{i})-y_{i}\big{)}^{2}-\big{(}g(x_{i})-y_{i}\big{)}^{2}\big{]}\Big{\\}}\leq\mathcal{M}^{\mathsf{new}}(\delta_{n}).$

Repeating the analysis in Section 5.2 with $\delta_{\lambda}=\delta_{n}$
yields the desired claim. ∎

##  Appendix E Expectation bounds for KRR estimates

In this section, we derive expectation bounds as counterparts to our previous
high probability upper bounds on the KRR estimates. In Section E.1, we present
an expectation bound for instances with bounded likelihood ratios, essentially
as a consequence of our previous high probability statement, given in Theorem
1. Similarly, in Section E.2, we present an expectation bound for instances
which have possibly unbounded likelihood ratios, but for which the second
moment of the likelihood ratios is bounded. Again, this can be seen as an
extension of our previous high-probability statement on the truncated,
reweighted KRR estimator, as stated in Theorem 4.

###  E.1 Bounded likelihood ratio

######  Theorem 6.

Consider a covariate-shifted regression problem with likelihood ratio that is
$B$-bounded (3) over a Hilbert space with a $\kappa$-uniformly bounded kernel
(9). There are universal constants $c_{1},c_{2}>0$ such that if $\lambda\geq
c_{1}\tfrac{\kappa^{2}\log n}{n}$, the KRR estimate $\widehat{f}_{\lambda}$
satisfies the bound

$\displaystyle\mathbb{E}\big{[}\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\big{]}\leq
c_{2}\Big{\\{}\lambda
B\|f^{\star}\|_{\mathcal{H}}^{2}+\frac{\sigma^{2}B}{n}\sum_{j=1}^{\infty}\frac{\mu_{j}}{\mu_{j}+\lambda
B}+\frac{\sigma^{2}}{n}\Big{\\}}.$ (77)

Inspecting the proof, one may take $c_{1}=32,c_{2}=\tfrac{519}{256}$. The
proof of this result is presented in Section E.1.1.

An immediate consequence is the following result for regular kernels. Note
that it matches our lower bound (see Theorem 2), apart from logarithmic
factors.

######  Corollary 3.

Suppose $\sigma^{2}\geq\kappa^{2}$ and $\|f^{\star}\|_{\mathcal{H}}=1$. For
any $B\geq 1$ and any pair $(P,Q)$ with $B$-bounded likelihood ratio (3), any
orthonormal basis $\\{\phi_{j}\\}_{j\geq 1}$ of $L^{2}(Q)$, and any regular
sequence of kernel eigenvalues $\\{\mu_{j}\\}_{j\geq 1}$, there exist a
universal constant $C>0$ such that

$\displaystyle\mathbb{E}\big{[}\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\big{]}$
$\displaystyle\leq
C\;\inf_{\delta>0}\Big{\\{}\delta^{2}+\sigma^{2}Bd(\delta)\frac{\log
n}{n}\Big{\\}},$ (78)

where above $\lambda=\delta_{n}^{2}$ where
$\delta_{n}^{2}=c\frac{\sigma^{2}Bd(\delta_{n})\log n}{n}$ for a universal
constant $c>0$.

###### Proof.

Following the proof of Corollary 1, we obtain from the KRR risk bound of
Theorem 6,

$\mathbb{E}\big{[}\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\big{]}\Big{]}\leq
C_{1}\Big{\\{}\delta^{2}+\sigma^{2}Bd(\delta)\frac{\log
n}{n}\Big{\\}},\quad\mbox{where}\quad\delta^{2}=\lambda B,$ (79)

for any $\delta^{2}\geq c_{1}B\kappa^{2}\tfrac{\log n}{n}$. Adjusting
constants so that $c\geq c_{1}$, our choice of $\delta_{n}^{2}$ is valid since
$\sigma^{2}\geq\kappa^{2}$ and $d(\delta_{n})\geq 1$. Moreover, since
$\delta^{2}$ is an increasing function of $\delta$, whereas $d(\delta)$ is
nonincreasing, under the choice of
$\delta_{n}^{2}=c\frac{\sigma^{2}Bd(\delta_{n})\log n}{n}$, we have

$\Big{\\{}\delta_{n}^{2}+\sigma^{2}Bd(\delta_{n})\frac{\log n}{n}\Big{\\}}\leq
C_{2}\inf_{\delta>0}\Big{\\{}\delta^{2}+\sigma^{2}Bd(\delta)\frac{\log
n}{n}\Big{\\}},$ (80)

for a universal constant $C_{2}>0$. Note that this inequality completes the
proof of the result, with $C=C_{1}C_{2}$. ∎

####  E.1.1 Proof of Theorem 6

Using Parseval’s theorem and the optimality conditions for the KRR problem as
given in equation (29), we have
$\mathbb{E}[\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}]\leq\mathbb{E}[T_{1}]+\mathbb{E}[T_{2}]$
where

$T_{1}\coloneqq\|\lambda(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\bm{M}^{-1}\theta^{\star}\|_{2}^{2},\quad\mbox{and}\quad
T_{2}\coloneqq\|(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\big{(}\frac{1}{n}\sum_{i=1}^{n}w_{i}\phi(x_{i})\big{)}\|_{2}^{2}.$

Recall the event

$\mathcal{E}(\lambda)\coloneqq\Big{\\{}\bm{M}^{1/2}\widehat{\bm{\Sigma}}_{P}\bm{M}^{1/2}+\lambda\bm{I}\succeq\frac{1}{2}\big{(}\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I}\big{)}\Big{\\}},$

as defined in equation (27). We use this event to bound the two terms.

##### Bound for $T_{1}$

Inspecting the proof of Theorem 1 (specifically, see the proof of bound
(30)(a)), it follows that
$\mathbb{E}[T_{1}\mathbf{1}_{\mathcal{E}(\lambda)}]\leq 2\lambda
B\|f^{\star}\|_{\mathcal{H}}^{2}$. On the other hand, from inequality (ii) of
the proof of (30)(a), it also holds that

$\mathbb{E}[T_{1}\mathbf{1}_{\mathcal{E}(\lambda)^{c}}]\leq\|f^{\star}\|_{\mathcal{H}}^{2}|\\!|\\!|\bm{M}|\\!|\\!|_{{2}}\mathbb{P}(\mathcal{E}(\lambda)^{c})\leq\|f^{\star}\|_{\mathcal{H}}\kappa^{2}\mathbb{P}(\mathcal{E}(\lambda)^{c}).$

The final inequality holds since
$|\\!|\\!|\bm{M}|\\!|\\!|_{{2}}\leq\mathsf{trace}(\bm{M})=\mathbb{E}_{Q}[\sum_{j}\mu_{j}\phi_{j}^{2}(x)]\leq\kappa^{2}$.
Now, note that whenever $n\lambda\geq 32\kappa^{2}\log n$, by Lemma 1 we have
that

$\displaystyle\mathbb{E}[T_{1}\mathbf{1}_{\mathcal{E}(\lambda)^{c}}]$
$\displaystyle\leq\|f^{\star}\|_{\mathcal{H}}^{2}\mathbb{P}(\mathcal{E}(\lambda)^{c})$
$\displaystyle\leq
28\lambda\|f^{\star}\|_{\mathcal{H}}^{2}\Big{[}\big{(}\frac{\kappa^{2}}{\lambda}\big{)}^{2}\exp\Big{(}-\frac{n\lambda}{16\kappa^{2}}\Big{)}\Big{]}$
$\displaystyle\leq\frac{7}{256}\lambda\|f^{\star}\|_{\mathcal{H}}^{2}.$

Putting the pieces together, we obtain

$\mathbb{E}[T_{1}]\leq\frac{519}{256}\lambda\|f^{\star}\|_{\mathcal{H}}^{2}.$
(81)

##### Bound for $T_{2}$

By considering the expectation over $w_{i}$ conditional on the covariates and
following algebraic manipulations similar to the proof of bound (30)(b), we
have

$\mathbb{E}[T_{2}]\leq\mathbb{E}[\widetilde{}T_{2}],\quad\mbox{where}\quad\widetilde{}T_{2}\coloneqq\mathsf{trace}\Big{(}\frac{\sigma^{2}}{n}(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\Big{)}.$

Moreover, inspecting the proof of bound (30)(b), we also have

$\mathbb{E}[\tilde{}T_{2}\mathbf{1}_{\mathcal{E}(\lambda)}]\leq
2\frac{\sigma^{2}B}{n}\sum_{j=1}^{\infty}\frac{\mu_{j}}{\mu_{j}+\lambda B}.$

On the other hand, by bounding
$(\widehat{\bm{\Sigma}}_{P}+\lambda\bm{M}^{-1})^{-1}\preceq\lambda^{-1}\bm{M}$,

$\mathbb{E}[\tilde{}T_{2}\mathbf{1}_{\mathcal{E}(\lambda)^{c}}]\leq\frac{\sigma^{2}}{n}\frac{\kappa^{2}}{\lambda}\mathbb{P}(\mathcal{E}(\lambda)^{c})\leq\frac{7}{256}\frac{\sigma^{2}}{n}.$

The final inequality above is established in the same manner as in the proof
of the bound for $T_{1}$ above, when $n\lambda\geq 32\kappa^{2}\log n$. Thus,
combining the two bounds,

$\mathbb{E}[T_{2}]\leq
2\frac{\sigma^{2}B}{n}\sum_{j=1}^{\infty}\frac{\mu_{j}}{\mu_{j}+\lambda
B}+\frac{7}{256}\frac{\sigma^{2}}{n}.$

###  E.2 Unbounded likelihood ratio

######  Theorem 7.

Suppose $\sigma^{2}\geq\kappa^{2}$ and $\|f^{\star}\|_{\mathcal{H}}=1$.
Consider a kernel with sup-norm bounded eigenfunctions (19), and a source-
target pair with $\mathbb{E}_{P}[\rho^{2}(X)]\leq V^{2}$. Then, for any
orthonormal basis $\\{\phi_{j}\\}_{j\geq 1}$ of $L^{2}(Q)$ and any regular
sequence of kernel eigenvalues $\\{\mu_{j}\\}_{j\geq 1}$, there exists a
universal constant $C>0$ such that,

$\displaystyle\mathbb{E}\Big{[}\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{Q}^{2}\Big{]}$
$\displaystyle\leq
C\;\inf_{\delta>0}\Big{\\{}\delta^{2}+V^{2}d(\delta)\frac{\log^{3}n}{n}\Big{\\}}.$
(82)

Above, $3\lambda=\delta_{n}^{2}$ where $\delta_{n}^{2}$ satisfies the equation
$\delta^{2}=c\tfrac{\sigma^{2}V^{2}\log^{3}n}{n}$ for a universal constant
$c>0$.

Before giving the proof, we emphasize that—apart from logarithmic factors—this
bound is minimax optimal.

###### Proof.

By Theorem 4, there is an event $\mathcal{E}$ which has probability at least
$1-cn^{-10}$ such that the truncated, reweighted estimator
$\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}$ satisfies

$\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{Q}^{2}\leq
c_{1}\delta^{2},$

provided we select
$\lambda\asymp\delta^{2}\asymp\frac{\sigma^{2}V^{2}\log^{3}(n)d(\delta)}{n}$.
Note that under this choice of $\delta^{2}$, we have

$\delta^{2}\asymp\inf_{\delta>0}\Big{\\{}\delta^{2}+\frac{\sigma^{2}V^{2}\log^{3}(n)d(\delta)}{n}\Big{\\}}.$

Consequently, there is a constant $c_{2}>0$ such that

$\mathbb{E}\Big{[}\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{Q}^{2}\Big{]}\leq
c_{2}\;\inf_{\delta>0}\Big{\\{}\delta^{2}+\frac{\sigma^{2}V^{2}\log^{3}(n)d(\delta)}{n}\Big{\\}}+\mathbb{E}\Big{[}\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{\infty}^{2}\mathbf{1}_{\mathcal{E}^{c}}\Big{]}.$
(83)

By Cauchy-Schwarz,

$\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{\infty}^{2}\leq\kappa^{2}\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{\mathcal{H}}^{2}\leq
2\kappa^{2}(1+\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}\|_{\mathcal{H}}^{2}).$

Applying the optimality condition of the reweighted estimator
$\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}$, we have

$\lambda\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}\|_{\mathcal{H}}^{2}\leq\lambda+\sqrt{nV^{2}}\frac{1}{n}\sum_{i=1}^{n}w_{i}^{2}.$

Therefore, combining the previous two displays,

$\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{\infty}^{2}\leq
2\kappa^{2}\Big{(}2+\frac{\sqrt{nV^{2}}}{\lambda}\frac{1}{n}\sum_{i=1}^{n}w_{i}^{2}\Big{)}.$

It then follows by Cauchy-Schwarz and the sub-Gaussianity of $w_{i}$, that for
some constant $c_{3}>0$,

$\displaystyle\mathbb{E}\Big{[}\|\widehat{f}^{\mathrm{\scriptsize{rw}}}_{\lambda}-f^{\star}\|_{\infty}^{2}\mathbf{1}_{\mathcal{E}^{c}}\Big{]}$
$\displaystyle\leq
c_{3}\Big{(}\frac{\kappa^{2}}{n^{10}}+\frac{\sigma^{2}V^{2}}{\lambda
n^{4}}\kappa^{2}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle{\rm(i)}}}{{\leq}}c_{3}\frac{\sigma^{2}V^{2}}{n}\Big{(}\frac{1}{n^{9}}+\frac{\kappa^{2}}{\lambda}\frac{1}{n^{3}}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle{\rm(ii)}}}{{\leq}}c_{3}\frac{\sigma^{2}V^{2}}{n}\Big{(}\frac{1}{n^{9}}+\frac{c_{4}}{n^{2}}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle{\rm(iii)}}}{{\leq}}c_{5}\frac{\sigma^{2}V^{2}}{n}$

Above, inequality (i) uses $\sigma^{2}\geq\kappa^{2}$ and $V^{2}\geq 1$.
Inequality (ii) uses the fact that
$\lambda\asymp\delta^{2}\asymp\frac{\sigma^{2}V^{2}\log^{3}(n)d(\delta)}{n}\gtrsim\frac{\kappa^{2}}{n}$.
Finally, inequality (iii) follows by defining $c_{5}\geq c_{3}(1+c_{4})$. This
bound furnishes the result, since by applying it to the inequality (83), we
obtain the result with $C=c_{2}+c_{5}$. ∎

##  Appendix F Performance of unweighted KRR with unbounded likelihood ratios

In this section, we present the performance guarantee of the unweighted KRR
estimator when the likelihood ratios are unbounded.

######  Theorem 8.

Consider a covariate-shifted regression problem with likelihood ratios obeying
$\mathbb{E}_{P}[\rho^{2}(X)]\leq V^{2}$. Then for any $\lambda\geq
10\kappa^{2}/n$, the KRR estimate $\widehat{f}_{\lambda}$ satisfies the bound

$\displaystyle\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}\leq 2\sqrt{\lambda
V^{2}\kappa^{2}}\|f^{\star}\|_{\mathcal{H}}^{2}+40\frac{\sigma^{2}\log
n}{n}\cdot\frac{\kappa^{2}}{\lambda}$ (84)

with probability at least
$1-28\;\tfrac{\kappa^{2}}{\lambda}e^{-\frac{n\lambda}{16\kappa^{2}}}-\frac{1}{n^{10}}$.

Simple algebra shows that the unweighted KRR estimator is still consistent for
estimation under covariate shift, with a rate of
$(\frac{\sigma^{2}V^{2}}{n})^{1/3}$ (ignoring $\kappa^{2}$ and $\log$
factors). However, unfortunately, this is far from optimal.

###  F.1 Proof of Theorem 8

In view of the proof of Theorem 1, we know that

$\displaystyle\|\widehat{f}_{\lambda}-f^{\star}\|_{Q}^{2}$ $\displaystyle\leq
4\lambda\|f^{\star}\|_{\mathcal{H}}^{2}|\\!|\\!|\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}|\\!|\\!|_{{2}}$
$\displaystyle\quad+40\frac{\sigma^{2}\log
n}{n}\mathsf{trace}\Big{(}\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}\Big{)}$
(85)

holds with probability at least
$1-28\;\tfrac{\kappa^{2}}{\lambda}e^{-\frac{n\lambda}{16\kappa^{2}}}-\frac{1}{n^{10}}$.
The proof is finished with the help of the following two bounds:

$\displaystyle|\\!|\\!|\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}|\\!|\\!|_{{2}}$
$\displaystyle\leq\frac{1}{2}\sqrt{\frac{V^{2}\kappa^{2}}{\lambda}};$ (86a)
$\displaystyle\mathsf{trace}\Big{(}\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}\Big{)}$
$\displaystyle\leq\frac{\kappa^{2}}{\lambda}.$ (86b)

##### Proof of the bound (86b):

Note that
$\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}\preceq\lambda^{-1}\bm{M}$.
We therefore have

$\displaystyle\mathsf{trace}\Big{(}\bm{M}^{1/2}(\bm{M}^{1/2}\bm{\Sigma}_{P}\bm{M}^{1/2}+\lambda\bm{I})^{-1}\bm{M}^{1/2}\Big{)}\leq\mathsf{trace}(\lambda^{-1}\bm{M})\leq\frac{\kappa^{2}}{\lambda},$

where the last relation uses the fact that
$\mathsf{trace}(\bm{M})\leq\kappa^{2}$.

##### Proof of the bound (86a):

We first make the observation that the bound (86a) is equivalent to

$\displaystyle\bm{\Sigma}_{P}+\lambda\bm{M}^{-1}\succeq
2\sqrt{\frac{\lambda}{V^{2}\kappa^{2}}}\bm{I}.$ (87)