# High-Dimensional Kernel Methods under Covariate Shift:
Data-Dependent Implicit Regularization

Yihang Chen  Fanghui Liu  Taiji Suzuki  Volkan Cevher

###### Abstract

This paper studies kernel ridge regression in high dimensions under covariate
shifts and analyzes the role of importance re-weighting. We first derive the
asymptotic expansion of high dimensional kernels under covariate shifts. By a
bias-variance decomposition, we theoretically demonstrate that the re-
weighting strategy allows for decreasing the variance. For bias, we analyze
the regularization of the arbitrary or well-chosen scale, showing that the
bias can behave very differently under different regularization scales. In our
analysis, the bias and variance can be characterized by the spectral decay of
a data-dependent regularized kernel: the original kernel matrix associated
with an additional re-weighting matrix, and thus the re-weighting strategy can
be regarded as a data-dependent regularization for better understanding.
Besides, our analysis provides asymptotic expansion of kernel
functions/vectors under covariate shift, which has its own interest.

Machine Learning, ICML

##  1 Introduction

In statistical learning theory (Vapnik, 1999), the fundamental assumption is
that the training and test data are drawn from the same distribution. However,
in real-world applications, test data may generated quite differently from the
training data. One of the most common situations is the _covariate shifts_
(Shimodaira, 2000; Sugiyama et al., 2007), where the training and test
distributions of inputs (covariates) are different.

The importance weighting (IW) (Shimodaira, 2000) is a typical way to handle
covariate shift. Let $p$ and $q$ be the marginal distributions over the
training and test covariates, respectively, the IW method adopts their Radon-
Nikodym derivative as the importance weighting (IW) function, i.e.,
${w}(\bm{x})={\mathrm{d}}q(\bm{x})/{\mathrm{d}}p(\bm{x})$. Hence, the IW
function weights the loss function, leading to an unbiased estimator of the
expected loss under the test distribution. Empirically, the IW method has been
widely used in machine learning (e.g., Huang et al., 2006; Sugiyama et al.,
2008; Cortes et al., 2010; Sugiyama et al., 2012; Fang et al., 2020) from
linear to kernel estimator as well as neural networks. Theoretically, the IW
method can achieve nice statistical properties (e.g., minimax rate) under
certain settings for kernel ridge regression (Ma et al., 2023; Gogolashvili et
al., 2023).

However, recent work on high-capacity models, e.g., nonparametric and over-
parameterized models111Over-parameterized models admit the fact that the
number of parameters is larger than the number of training data. Modern neural
networks belong to this setting., demonstrate that, the IW strategy is not
beneficial under certain settings, e.g., over-parameterized linear regression
(Zhai et al., 2023), $k$-nearest neighbors classifier (Kpotufe & Martinet,
2021) for _interpolation_ under well-specified cases. Nevertheless, for some
misspecified cases, the IW correction is still needed for non-parametric
kernel ridge regression (Gogolashvili et al., 2023).

We can see the separation in the effect of IW for low/high-capacity models
under (mis)-specified settings. But how the generalization result depends on
the choice of model capacities, and its interplay with the regularization
level in terms of bias-variance trade-off remains unclear. Intuitively, the IW
strategy obtains the unbiased estimation of the original empirical risk
minimization, leading to a decreasing variance to some extent; while the
approximation between the estimator and the target function will change,
leading to an increasing bias to some extent. As such, refined analyses based
on bias-variance trade-offs are required to understand the following question:

_How does IW affect bias-variance trade-off in high-capacity models?_

We attempt to address this question by uncovering the mystery behind the IW
strategy in covariate shifts from the bias-variance trade-off. To be specific,
in this work, we focus on kernel ridge regression (KRR) in _high dimensions_
with data dimension $d$ and size $n$ both large under the IW strategy, a
typical regularized-based nonparametric regression over reproducing kernel
Hilbert spaces (RKHSs). This choice allows for studying different learning
paradigms, for example, neural networks can be described by neural tangent
kernel (Jacot et al., 2018) under certain settings; the high-dimensional
setting matches practical image application via over-parameterized neural
networks; the model capacity can be tuned by the regularization parameter.
Accordingly, the kernel interpolation can be regarded as a special case of KRR
by taking the explicit regularization sufficiently close to zero, which
follows the spirit of over-parameterized neural networks for _interpolation
learning_.

Formally, given $n$ training data $\bm{Z}=\\{(\bm{x}_{i},y_{i})\\}_{i=1}^{n}$,
the estimator of KRR in high dimensions under a general IW function
$\overline{w}(\bm{x})$ is given by

$\overline{f}_{\lambda,\bm{Z}}\\!:=\\!\operatornamewithlimits{arg\,min}_{f\in\mathcal{H}}\\!\left\\{\\!\frac{1}{n}\sum_{i=1}^{n}\overline{w}(\bm{x}_{i})\left(f\left(\bm{x}_{i}\right)\\!-\\!y_{i}\right)^{2}\\!+\\!\lambda\|f\|_{\mathcal{H}}^{2}\\!\right\\}\,,$
(1)

where $\lambda>0$ is the regularization parameter.

###  1.1 Contributions

We summarize the contributions and findings as below:

  * •

We present the asymptotic expansion of high dimensional kernels
$k(\bm{x},\bm{x}^{\prime})$ under covariate shifts, where the nonlinearity in
kernels can be eliminated by the kernel function curvature, see Lemma 4.3.

  * •

We present bias-variance decomposition for KRR in high dimensions with
covariate shift. To be specific, for variance, via the asymptotic expansion,
we demonstrate that the IW strategy can be regarded as an implicit data-
dependent regularization on the respective kernel. The estimation of variance
heavily depends on the spectral decay of the expected covariance matrix over
$q$ or such data-dependent regularized kernel, and allows for a decreasing
variance to some extent, see Section 4.3.

  * •

For bias, via the asymptotic expansion, we demonstrate that i) near
interpolation (i.e., the regularization $\lambda$ is sufficiently small), the
bias term can be upper bounded by two parts, one is an intrinsic bias that
only depends on the covariate shift problem itself, in a constant order;
another is the importance re-weighting bias, which depends on the spectral
decay of data-dependent regularized kernels. ii) if we choose a proper
regularization parameter, the IW strategy does not hurt the bias, i.e., the
bias can tend to zero, see Section 4.4 for details.

We hope our analysis provides a better understanding on the role of the IW
strategy in terms of bias-variance trade-off, and would like to motivate the
community to think about powerful IW strategies to handle distribution shifts,
more generally.

###  1.2 Related works

##### High-dimensional kernel regression

To tackle the high-dimensional regression, one line of research (Mei et al.,
2021, 2022; Ghorbani et al., 2020, 2019; Misiakiewicz & Mei, 2022; Xiao et
al., 2022; Ghosh et al., 2021; Fang et al., 2020; Aerni et al., 2023)
asymptotically characterizes the precise risk of kernel regression under some
specific data distributions, such as uniform distributions on the sphere or
hypercube vertices, so that the kernel’s eigenfunctions and eigenvalues can be
explicitly accessed. Another line of research (Liang & Rakhlin, 2020; Liu et
al., 2021; McRae et al., 2022) provides non-asymptotic bounds by high-
dimensional random matrix concentration in El Karoui (2010).

##### Covariate shift

There has been extensive analysis of kernel regression under covariate shift
in the fixed dimensions. In the well-specified case, the standard maximum
likelihood estimation leads to the optimal model, and the importance re-
weighting is unnecessary (Zhai et al., 2023; Ge et al., 2023). Ma et al.
(2023); Gogolashvili et al. (2023) analyze different importance re-weighting
functions. Feng et al. (2023) additionally provide a uniform analysis for
kernel regression of general loss function under covariate shifts. However,
the analysis of the fixed-dimension kernel requires an appropriate choice of
$\lambda$ to balance the bias and variance. Apart from re-weighting, the
transfer exponent (Kpotufe & Martinet, 2021) is another metric to evaluate the
distribution mismatch, as well as another variant (Pathak et al., 2022).

##### Random matrix theory

In the specific case of the linear kernel, a series of works use the random
kernel theory to asymptotically characterize the precise risk (Hastie et al.,
2022; Karoui, 2013; Dicker, 2016; Wu & Xu, 2020; Lu et al., 2023). There is
also a series of works focusing on covariate shift in the high-dimensional
random feature regression (Tripuraneni et al., 2021b, a). However, their
results did not consider the data-dependent importance re-weighting, explained
as below.

Classical RMT is able to provide an exact characteristic formulation of the
limiting distribution of covariance matrix via its Stieltjes transform, and
then its solution can be obtained from the popular Marc̆enko–Pastur equation.
However, since the IW strategy is regarded as a data-dependent transformation
(we will discuss it later), the limiting distribution of the “data-dependent”
covariance matrix can not be directly obtained, which requires more effort and
advanced techniques in the RMT community. We leave this as an open question.

##### Notations

We denote the decreasing eigenvalues of any matrix
$\bm{A}\in\mathbb{R}^{n\times n}$ by
$\lambda_{1}(\bm{A})\geq\lambda_{2}(\bm{A})\dots\geq\lambda_{n}(\bm{A})$, and
the spectrum of $\bm{A}$ by
$\bm{\Lambda}(\bm{A}):=\\{\lambda_{i}(\bm{A})\\}_{i=1}^{n}$. We call
$a\lesssim b$ or $a=O(b)$ if and only if there exists constant $C$ independent
of $n,d$, such that $a\leq C\cdot b$. We call a positive function $f(d)\asymp
d^{a}$ if and only if
$\sup\lim_{d\to\infty}f(d)/d^{a+\epsilon}=0,\inf\lim\lim_{d\to\infty}f(d)/d^{a-\epsilon}=+\infty$
for any $\epsilon>0$. We use the abbreviation $[d]=\\{1,2,\cdots,d\\}$ for
integer $d$.

Organization The paper is organized as below: Section 2 introduce our problem
settings and Section 3 makes the required assumptions for our proof. Our main
results are given in Section 4 and the conclusion is drawn in Section 5.

##  2 Problem Settings

We introduce our problem settings in terms of the data generation process
under covariate shift and the used kernel function in RKHS.

Data generation process: We follow the classical statistical learning
framework (Cucker & Zhou, 2007). Let $\mathcal{X}\subseteq\mathbb{R}^{d}$ be
the input space (compact domain) and $\mathcal{Y}\subset\mathbb{R}$ is the
label space, we observe $n$ i.i.d. pairs $\bm{Z}=\\{(\bm{x}_{i},y_{i})$,
$1\leq i\leq n\\}$, where $\bm{x}_{i}$ are the covariates and
$y_{i}\in\mathcal{Y}$ are the labels. Suppose these $n$ pairs are drawn from a
unknown probability distribution $p(\bm{x},y):=p(\bm{x})\rho(y|\bm{x})$, where
$p(\bm{x})$ as the marginal distribution of $\rho$ on $\mathcal{X}$ and
$\rho(y|\bm{x})$ as the conditional distribution at $\bm{x}\in\mathcal{X}$
induced by $\rho$. Let $\widehat{\mathbb{E}}_{n}$ be the expectation on the
empirical measure
$\widehat{p}_{n}(\bm{x}):=\frac{1}{n}\sum_{i=1}^{n}\delta_{\bm{x}_{i}}(\bm{x})$.
The objective of our learning problem is to find a learning model that is a
good approximation of the “target function”
$f_{\rho}(\bm{x})=\int_{Y}y\mathrm{d}\rho(y|\bm{x})\,,\forall\bm{x}\in X$ as
the conditional mean. We assume that there exists a $\sigma_{\varepsilon}>0$
such that $y(\bm{x})=f_{\rho}(\bm{x})+\varepsilon$, and
$\mathbb{E}[\varepsilon]=0$,
$\mathbb{V}[\varepsilon]\leq\sigma_{\varepsilon}^{2}$.

Re-weighting in covariate shift: Under the covariate shift setting where the
test data is not sampled from $p(\bm{x})$ but the test distribution as
$q(\bm{x})$. To handle this, we introduce the importance re-weighting strategy
with the density ratio
${w}(\bm{x})={\mathrm{d}}q(\bm{x})/{\mathrm{d}}p(\bm{x})$. Here we consider a
general version by introducing the weighting distribution
$\overline{q}(\bm{x})$ such that
$\overline{w}(\bm{x}):={\mathrm{d}}\overline{q}(\bm{x})/{\mathrm{d}}p(\bm{x})$,
where we use $\overline{w}(\bm{x})$ as importance weighting. In general,
$\overline{q}$ can be unnormalized density, with
$\overline{Z}:=\int_{\bm{x}\sim\bm{X}}{\mathrm{d}}\overline{q}(\bm{x})$.
However, without loss of generality, we can assume $\overline{Z}=1$.
Otherwise, we can replace $\lambda$ with $\lambda\overline{Z}$. Accordingly,
when $\overline{w}(\bm{x}):=1$, our minimization problem is reduced to the
standard unweighted empirical risk minimization; when
$\overline{w}(\bm{x}):=w(\bm{x})$, it is reduced to the standard importance
re-weighting by the density ratio.

In this paper, the used learning model is kernel ridge regression endowed by
RKHS in high dimensions as described below, where the training dataset size
$n$ and data dimension $d$ satisfy $n/d\to\zeta$ with $\zeta\in(0,\infty)$ as
$d\to\infty$, and $\zeta_{\min}\leq n/d\leq\zeta_{\max},\forall n,d$. This is
the standard setting in high-dimensional kernel regression (Liang & Rakhlin,
2020; Liu et al., 2021; Mei et al., 2022).

###  2.1 RKHS and kernels

The Reproducing kernel Hilbert space (RKHS) $\mathcal{H}$ is a Hilbert space
$\mathcal{H}$ endowed with the inner product $\langle\cdot,\cdot\rangle_{K}$
of functions $f:\mathcal{X}\rightarrow\mathbb{R}$ with a reproducing kernel
$K:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ where
$K(\cdot)\in\mathcal{H}$ and $f(\bm{x})=\langle f,K(\bm{x},\cdot)\rangle_{K}$
(Mercer, 1909). We assume that $K$ is bounded, i.e., there exists a constant
$1\leq\kappa<\infty$ such that
$\sup_{\bm{x}\sim\mathcal{\bm{X}}}K(\bm{x},\bm{x})\leq\kappa$.

Define
$\mathcal{L}_{q}^{2}:=\\{f:\mathcal{X}\to\mathbb{R}|\|f\|_{q}^{2}\leq\infty\\}$,
and $\|f\|_{q}^{2}:=\int_{\mathcal{X}}f^{2}(\bm{x}){\mathrm{d}}q(\bm{x})$. For
ease of our analysis, let us introduce the integral operator
${L}_{q}:\mathcal{L}_{q}^{2}\rightarrow\mathcal{L}_{q}^{2}$ with respect to
the test distribution $q(\bm{x})$:

$\displaystyle L_{q}f=\int
K(\cdot,\bm{x}^{\prime})f(\bm{x}^{\prime}){\mathrm{d}}q(\bm{x}^{\prime})\,,$

and denote the set of eigenfunctions of this integral operator by
$\bm{\phi}(\bm{x})=\\{\phi_{1}(\bm{x}),\phi_{2}(\bm{x}),\ldots,\phi_{o}(\bm{x})\\}$,
where $o$ could be $\infty$. We have that

$\displaystyle
L_{q}\phi_{i}=\lambda_{i}\phi_{i},~{}~{}\text{and}~{}~{}\int\phi_{i}(\bm{x})\phi_{j}(\bm{x}){\mathrm{d}}q(\bm{x})=\delta_{ij}\,.$
(2)

Denote $\bm{\Lambda}={\rm diag}(\lambda_{1},\cdots,\lambda_{o})$ as the
collection of non-negative eigenvalues, with
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{o}$. We can write
$K(\cdot,\cdot)$ via the spectral notation

$\displaystyle
K(\bm{x},\bm{x}^{\prime})=\bm{\phi}(\bm{x})^{\top}\bm{\Lambda}\bm{\phi}(\bm{x}^{\prime})\,.$

We define the empirical integral operator on the training dataset $\bm{X}$,

$\displaystyle
L_{{q},\bm{X}}f:=\frac{1}{n}\sum_{i=1}^{n}{w}(\bm{x}_{i})f(\bm{x}_{i})K(\cdot,\bm{x}_{i})\,.$

Similarly, we can define $L_{\overline{q}}$, and $L_{\overline{q},\bm{X}}$ for
weighting distribution $\overline{q}$.

###  2.2 Interpolation and regression

Let
$\bm{X}:=[\bm{x}_{1},\bm{x}_{2},\cdots,\bm{x}_{n}]^{\top}\in\mathbb{R}^{n\times
d}$ be the data matrix,
$\bm{y}:=[y_{1},y_{2},\cdots,y_{n}]^{\top}\in\mathbb{R}^{n}$ be the label
vector, and $\bm{Z}:=[\bm{X},\bm{y}]$ be the concatenation. Besides, we denote
$\bm{K}(\bm{X},\bm{X})=[K(\bm{x}_{i},\bm{x}_{j})]_{ij}\in\mathbb{R}^{n\times
n}$ be the kernel matrix. Extending this definition, for
$\bm{x}\in\mathcal{\bm{X}}$ we denote by
$\bm{K}(\bm{x},\bm{X})\in\mathbb{R}^{1\times n}$ the matrix of values
$[\bm{K}(\bm{x},\bm{x}_{1}),\ldots,\bm{K}(\bm{x},\bm{x}_{n})]$, and
$\bm{K}(\bm{X},\bm{x}):=\bm{K}(\bm{x},\bm{X})^{\top}\in\mathbb{R}^{n\times
1}$.

##### Interpolation

The unweighted interpolation estimator is defined as

$\displaystyle
f_{\bm{Z}}:=\operatornamewithlimits{arg\,min}_{f\in\mathcal{H}}\|f\|_{K},~{}~{}\text{s.t.}~{}~{}f(\bm{x}_{i})=y_{i},~{}\forall
i\in[n]\,.$ (3)

When $\bm{K}(\bm{X},\bm{X})$ is invertible222For ease of analysis, we assume
the $\bm{K}(\bm{X},\bm{X})$ has full rank., solution to (3) can be written in
the closed form:

$\displaystyle f_{\bm{Z}}(\bm{x})$
$\displaystyle=\bm{K}(\bm{x},\bm{X})\bm{K}(\bm{X},\bm{X})^{-1}\bm{y}\,.$ (4)

Actually, in the interpolation problem, the IW strategy does work due to the
constraint $\bar{w}_{i}[f(\bm{x}_{i})-y_{i}]=0$, which naturally coincides
with Zhai et al. (2023). Accordingly, we consider the regularized regression
weighted by $\overline{w}(\bm{x})$ in Eq. 1. Let
${\overline{\bm{W}}({\bm{X}})}:={\rm
diag}(\overline{w}(\bm{x}_{i}))_{i=1}^{n}$, the solution to Eq. 1 can be
written in the closed form:

$\displaystyle\overline{f}_{\lambda,\bm{Z}}(\bm{x})$
$\displaystyle=\bm{K}(\bm{x},\bm{X})(\bm{K}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}\bm{y}\,.$

We are interested in the generalization performance of
$\overline{f}_{\lambda,\bm{Z}}$ estimated by the excess risk w.r.t. the test
distribution $q$ $\|\overline{f}_{\lambda,\bm{Z}}-{f}_{\rho}\|_{q}^{2}$.

##  3 Assumptions

In this paper, we make the following assumptions, including the type of the
considered kernels, data, and ratio. Besides, we also introduce assumptions on
the model, e.g., the source condition on the target function, and the capacity
condition.

###  3.1 Basic assumptions on kernel, data distribution

Firstly, we consider the two forms of kernels in this paper for asymptotic
expansion:

  * •

_inner product kernel_ ,
$K(\bm{x},\bm{x}^{\prime}):=h\left(\langle\bm{x},\bm{x}^{\prime}\rangle/d\right)$;

  * •

_radial kernel_ ,
$K(\bm{x},\bm{x}^{\prime}):=h(-\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2}/d)$.

where $h(\cdot):\mathbb{R}\rightarrow\mathbb{R}$ is a non-linear Lipschitz
smooth function in a neighborhood of $0$. Following (El Karoui, 2010), we
assume $h$ to ensure the positive definiteness of the asymptotic expansion of
the original kernel.

######  Assumption 3.1 (Assumptions on $h$).

We assume $h:\mathbb{R}\to\mathbb{R}$ is a smooth function that satisfies the
following constraints in the neighborhood of 0,

$\displaystyle h(x)\geq
0,h^{\prime}(x)>0,~{}~{}h^{\prime\prime}(x)>0,~{}~{}h^{\prime\prime}(x)\leq
M_{h}\,.$

Remark: We give an example of three widely-used kernels and their
corresponding non-linear activation $h$. Each instantiation of $h$ satisfies
Assumption 3.1.

Table 1: Kernels and their corresponding $h$. Kernel | Formulation | $h(x)$
---|---|---
Polynomial | $(1+\frac{1}{d}\langle\bm{x},\bm{x}^{\prime}\rangle)^{k}$ | $(1+x)^{k}$
Exponential | $\exp(\frac{2}{d}\langle\bm{x},\bm{x}^{\prime}\rangle)$ | $\exp(2x)$
Gaussian | $\exp(-\frac{1}{d}\|\bm{x}-\bm{x}^{\prime}\|_{2}^{2})$ | $\exp(x)$

In the next, we consider a general class of data distributions of
$\bm{x}\in\mathbb{R}^{d}$.

######  Definition 1.

Denote $\mathcal{P}_{0}$ as the set of distributions of the random variable
$\bm{x}\sim\mu$ satisfying the following properties.

We assume there exists $\bm{\Sigma}_{\mu}\in\mathbb{R}^{d\times d}$, such that
$\bm{z}=\bm{\Sigma}_{\mu}^{-1/2}\bm{x}\in\mathbb{R}^{d}$. Each element of
$\bm{z}$ is independent and identically distributed on some distribution
${\widetilde{\mu}}$. We make the following assumptions on $\widetilde{\mu}$,

  * •

Sub-Gaussian. $\widetilde{\mu}$ is sub-Gaussian.

  * •

Identity Variance. Define the $i$-th moment of distribution $\widetilde{\mu}$,
$\kappa_{{\mu},i}:=\mathbb{E}_{z\sim{\widetilde{\mu}}}(z)^{i}$, we have
$\kappa_{\widetilde{\mu},1}=0,\kappa_{\widetilde{\mu},2}=1$, i.e.,
$\mathbb{E}_{\bm{z}}\bm{z}\bm{z}^{\top}=\bm{I}$.

  * •

Uniform Boundedness. There exists integer $m_{\mu}\geq 0$, such that
$|{\bm{z}}(k)|\lesssim d^{\frac{2}{8+m_{r}}}$. We additionally define constant
$\theta_{\mu}:=\frac{1}{2}-\frac{2}{8+m_{\mu}}$ for future simplicity.

######  Assumption 3.2 (Bounded Distribution).

The training distribution $p$ and test distribution $q$ belong to
$\mathcal{P}_{0}$, with
$\bm{\Sigma}_{p},\bm{\Sigma}_{q},m_{p},m_{q},\theta_{p},\theta_{q},\tau_{p},\tau_{q}$
being defined in Definition 1.

Remark: This assumption (or distribution class $\mathcal{P}_{0}$) is widely
used in high-dimensional statistics (Liang & Rakhlin, 2020; Liu et al., 2021;
Wu & Xu, 2020). The data distribution is assumed to be not too heavy-tailed,
with possible structure between the entries with zero-mean and unit-variance
and bounded moment with respect to $d$. The identity variance assumption
ensures that $\mathbb{E}_{\bm{x}\sim\mu}\bm{x}={\bf
0},\mathbb{E}_{\bm{x}\sim\mu}\bm{x}\bm{x}^{\top}=\bm{\Sigma}_{\mu}$, i.e.,
$\bm{\Sigma}_{\mu}$ is the covariance matrix of $\bm{x}\sim\mu$.

######  Assumption 3.3 (Similar Covariate).

We assume $\max\\{\|\bm{\Sigma}_{p}\|,\|\bm{\Sigma}_{q}\|\\}=O(1)$. Define
$\bm{\Sigma}_{pq}:=\bm{\Sigma}_{p}^{-1}\bm{\Sigma}_{q}$, and $\exists
c_{pq}\geq 0$ such that ${\rm Tr}(\bm{\Sigma}_{pq})/d\lesssim d^{c_{pq}}$. To
bound the distribution shifts, we additionally assume
$c_{pq}<2\theta_{q}-\frac{1}{2}=\frac{1}{2}-\frac{4}{8+m_{q}}$.

Remark: When $\bm{\Sigma}_{p}=\bm{\Sigma}_{q}$, we have $c_{pq}=0$, this
assumption always holds due to $m_{q}>0$. We make this assumption to provide a
more precise characterization of the similarity between $\bm{\Sigma}_{p}$ and
$\bm{\Sigma}_{q}$ via $\langle\bm{\Sigma}_{p}^{-1},\bm{\Sigma}_{q}\rangle$,
which aims to describe the difficulty of distribution shift. The distribution
shift is small when $c_{pq}$ is close to 0. The upper bound for $c_{pq}$ is a
sufficient condition to ensure the linear approximation of the kernel $K$, see
Lemma 4.3.

For the ratios $w(\bm{x}),\overline{w}(\bm{x})$, we make the following
assumption.

######  Assumption 3.4 (Bounded Ratio (Gogolashvili et al., 2023)).

For the probability ratio $v\in\\{w,\overline{w}\\}$, there exist constants
$t_{v}\in[0,1]$, $W_{v}(d)>0$ and $\sigma_{v}(d)>0$, where
$W_{v}(d),\sigma_{v}(d)$ is dependent on dimension $d$, such that, for all
$m\in\mathbb{N}$ with $m\geq 2$, it holds that

$\displaystyle\left(\int_{X}v(x)^{\frac{m-1}{t_{v}}}{\mathrm{d}}q(x)\right)^{t_{v}}\leq\frac{1}{2}m!W_{v}(d)^{m-2}\sigma_{v}(d)^{2}\,,$
(5)

where the left-hand side for $t_{v}=0$ is defined as
$\left\|v^{m-1}\right\|_{\infty}$, the essential supremum of $v^{m-1}$ with
respect to $q$. We additionally assume that for sufficiently large $d$,

$\displaystyle W_{v}(d)\leq W_{v}\cdot
d^{c_{v,1}},\sigma_{v}(d)\leq\sigma_{v}\cdot d^{c_{v,2}}\,,$

with $c_{v,1}\leq 2c_{v,2}$, and $c_{v,2}\leq\frac{1}{4}$.

Remark: Assumption 3.4 covers the uniform bounded ratio by taking
$t_{w}=0,W_{w}=\sigma_{w}^{2}=\arg\max_{\bm{x}}w(\bm{x})$.

###  3.2 Assumptions on model

In the next, we present the used assumptions for our analysis of the target
function and model capacity. Firstly, we consider the source condition of the
target function $f_{\rho}$.

######  Assumption 3.5.

(Source condition (Smale & Zhou, 2004, 2007)) We have
$f_{\rho}\in\mathcal{H}$, and there exists
$\frac{1}{2}\leq\overline{r}<1,\overline{g}_{\rho}\in\mathcal{L}_{q}^{2}$ such
that ${f}_{\rho}=(L_{\overline{q}})^{\overline{r}}\overline{g}_{\rho}$. We
additionally assume
$\max\\{\|f_{\rho}\|_{\mathcal{H}},\|\overline{g}_{\rho}\|_{q},\|f_{\rho}\|_{\infty}\\}\leq
C_{\mathcal{H}}d^{c_{\mathcal{H}}}$.

Remark: Source condition is widely used in the kernel literature (Smale &
Zhou, 2004, 2007; Caponnetto & De Vito, 2007). Intuitively, a larger
$\overline{r}$ indicates that $f_{\rho}$ is smoother. When $q=\overline{q}$,
Assumption 3.5 is reduced to the standard source condition on distribution
$q$. When $\overline{r}=1/2$, we have
$\|f_{\rho}\|_{\mathcal{H}}=\|g_{\rho}\|_{q}$. One key difference with
classical high-dimensional analysis (Liang & Rakhlin, 2020) is that we do not
always need a uniform constant upper bound of $\|f_{\rho}\|_{\mathcal{H}}$
over $d$.

For a kernel matrix $\bm{K}$, We define it capacity by
$\mathcal{N}(\bm{K},b)$, which is widely used in (Nakkiran et al., 2020;
Dobriban & Wager, 2018; Liang & Rakhlin, 2020; Jacot et al., 2020; Nakkiran et
al., 2020).

######  Definition 2 (Capacity).

Given a kernel matrix $\bm{K}$ and a parameter $b>0$, we denote its capacity
as

$\displaystyle\mathcal{N}(\bm{K},b):={\rm
Tr}\left[(\bm{K}+b\bm{I})^{-2}\bm{K}\right]=\sum_{i=1}^{n}\frac{\lambda_{i}(\bm{K})}{\left(b+\lambda_{i}(\bm{K})\right)^{2}}\,.$

The capacity can also be defined for the operator. The following assumption
describes the model capacity of kernel methods in terms of "effective
dimension".

######  Assumption 3.6 (Capacity condition (Caponnetto & De Vito, 2007)).

For any $\lambda>0$, there exists $E_{\mu}>0$ and $s_{\mu}\in[0,1]$ such that
for distribution $\mu\in\\{q,\overline{q}\\}$,

$\displaystyle\mathcal{N}_{\mu}(\lambda):={\rm
Tr}((L_{\mu}+\lambda)^{-1}L_{\mu})\leq
E_{\mu}^{2}\lambda^{-s_{\mu}},\forall\lambda\in(0,1]\,.$

Remark: The effective dimension $\mathcal{N}_{\mu}(\lambda)$ measures the
capacity of the kernel regression model with the regularization $\lambda$,
which can be interpreted by an estimate of the number of eigenvalues of
$L_{r}$ larger than $\lambda$. If the eigenvalues of $L_{r}$, i.e.
$\lambda_{r,i}$, decay at the asymptotic order $O(i^{-1/s_{\mu}})$, Assumption
3.6 holds. A small $s_{\mu}$ indicates that the eigenvalues of $L_{r}$ decay
at a faster rate, and Assumption 3.6 always holds when $s_{\mu}=1$ and
$E_{\mu}=\sqrt{\kappa}$, where
$\kappa=\max\\{\sup_{\bm{x}\in\mathcal{X}}K(\bm{x},\bm{x}),1\\}$.

###  3.3 Summary of notations

We have introduced several constants in this assumption above. We summarize it
here.

$\bm{\Sigma}_{\mu},\widetilde{\mu},\kappa_{\mu,i},m_{\mu},\theta_{\mu}$ :
assumptions on distribution $\mu=p,q$. See Definition 1.

$c_{pq}$: trace of $\bm{\Sigma}_{pq}$. See Assumption 3.3.

$t_{v},W_{v}(d),\sigma_{v}(d),c_{v,1},c_{v,2}$; upper bound of the probability
ratio. See Assumption 3.4.

$\overline{r},c_{\mathcal{H}}$: source condition. See Assumption 3.5.

$s_{\mu},E_{\mu}$: effective dimension. See Assumption 3.6.

##  4 Main results

In this section, we present the main results: the bias and variance the excess
risk of the estimator $\overline{f}_{\lambda,\bm{Z}}$ can be conducted from
bias-variance decomposition. Then we derive the estimation for the bias and
variance, respectively.

###  4.1 Bias-variance decomposition

To conduct bias-variance decomposition, we need the noiseless version of Eq. 1
for analysis.

$\begin{split}&\overline{f}_{\lambda,\bm{X}}:=\\\
&\operatornamewithlimits{arg\,min}_{f\in\mathcal{H}}\left\\{\frac{1}{n}\sum_{i=1}^{n}\overline{w}(\bm{x}_{i})\left(f\left(\bm{x}_{i}\right)\\!-\\!f_{\rho}(\bm{x}_{i})\right)^{2}\\!+\\!{\lambda}\|f\|_{\mathcal{H}}^{2}\right\\}\,,\end{split}$
(6)

i.e., to replace $y_{i}$ with its expectation $f_{\rho}(\bm{x}_{i})$. Using
the notations of the empirical operator, we have

$\displaystyle\overline{f}_{\lambda,\bm{X}}=(L_{\overline{q},\bm{X}}+{\lambda}I)^{-1}L_{\overline{q},\bm{X}}f_{\rho}\,.$

We then provide the bias-variance decomposition
$\|\overline{f}_{\lambda,\bm{Z}}-{f}_{\rho}\|_{q}$ by the following lemma,
with the proof deferred to Section A.1.

######  Lemma 4.1.

We consider the excess risk $\|\overline{f}_{\lambda,\bm{Z}}-{f}_{\rho}\|_{q}$
conditioned on $\bm{X}$ for our re-weighting estimator (1), admitting the
following bias-variance decomposition:

$\displaystyle\mathbb{E}_{\bm{y}|\bm{X}}\|\overline{f}_{\lambda,\bm{Z}}-{f}_{\rho}\|^{2}_{q}$
$\displaystyle=$
$\displaystyle{\mathbb{E}_{\bm{y}|\bm{X}}\|\overline{f}_{\lambda,\bm{Z}}-\overline{f}_{\lambda,\bm{X}}\|_{q}^{2}}+{\|\overline{f}_{\lambda,\bm{X}}-{f}_{\rho}\|_{q}^{2}}:={\sf
V}+{\sf B}^{2}\,.$

Clearly, the bias term does not rely on the label noise and the variance is
independent of the target function $f_{\rho}$, which matches the spirit of the
bias-variance decomposition.

###  4.2 Asymptotic expansion of high dimensional kernels

Considering the inner product kernel and radial kernel introduced in Section
3, El Karoui (2010) demonstrate that when $\bm{X}\sim p$, the related kernel
matrix $\bm{K}(\bm{X},\bm{X})$ in high dimensions can be well approximated by
${\bm{K}^{{\rm lin}}}(\bm{X},\bm{X})$ (detailed later) in spectral norm. We
state the approximation in Lemma 4.2 as below. This result will help us to
disentangle the nonlinearity of kernel functions in high dimensions.

######  Lemma 4.2 (El Karoui (2010)).

Assuming the kernel $K$ is the inner-product kernel or the radial kernel, and
the training data $\bm{X}\sim p$, under Assumption 3.1 and 3.2, we have

$\displaystyle\|\bm{K}(\bm{X},\bm{X})-{\bm{K}^{{\rm
lin}}}(\bm{X},\bm{X})\|_{2}\rightarrow 0\,,$

as $n,d\to\infty,n/d\to\zeta$, where ${\bm{K}^{{\rm lin}}}(\bm{X},\bm{X})$ is
defined by

${\bm{K}^{{\rm
lin}}}(\bm{X},\bm{X}):=\alpha_{p}\mathbbm{1}\mathbbm{1}^{\top}+\beta_{p}\frac{\bm{X}\bm{X}^{\top}}{d}+\gamma_{p}\bm{I}+\bm{T}_{p}\,,$
(7)

with non-negative parameters $\alpha_{p}$, $\beta_{p}$, $\gamma_{p}$, and the
additional matrix $\bm{T}_{p}$ given in Table 2.

We can see that, the kernel matrix in high dimensions can be mainly
approximated by its covariance matrix with an implicit regularization term
$\gamma_{p}\bm{I}$. Besides, the positive-definiteness of $\bm{K}^{\rm lin}$
can be guaranteed under Assumption 3.1, $\alpha_{p},\beta_{p},\gamma_{p}>0$.
By Assumption 3.1, we can directly derive $\alpha_{p},\beta_{p}>0$.
$\exists\delta,\delta^{\prime}\in[0,1]$, for the inner-product kernels, such
that $\gamma_{p}=h^{\prime\prime}(\delta\tau_{p})\tau_{p}^{2}/2>0$; and for
the radial kernels, such that
$\gamma_{p}=2h^{\prime\prime}(-2\delta^{\prime}\tau_{p})\tau_{p}^{2}>0$.

In the presence of covariate shifts, where the training data $\bm{X}$ is
sampled from $p$ and the test data $\bm{x}$ is sampled from $q$, the
approximation of the related kernel vector $\bm{K}(\bm{X},\bm{x})$ involves
$q$, and thus previous expansion (El Karoui, 2010) cannot be directly applied
to our setting. In this case, we state the relation in Lemma 4.3, which
additionally relies on Assumption 3.3, with the proof deferred to Section A.2.

######  Lemma 4.3.

Under Assumption 3.1, 3.2 and 3.3, where $c_{pq}<2\theta_{q}-1/2$, with the
training data $\bm{X}\sim p$ and a test data $\bm{x}\sim q$, we have

$\displaystyle\mathbb{E}_{q}\|\bm{K}(\bm{X},\bm{x})-\bm{K}^{\rm
lin}(\bm{X},\bm{x})\|_{2}\to 0\,,$

as $n,d\to\infty,n/d\to\zeta$, where ${\bm{K}^{{\rm lin}}}(\bm{x},\bm{X})$ is
defined by

$\displaystyle{\bm{K}^{{\rm
lin}}}(\bm{X},\bm{x}):=\beta_{pq}\frac{\bm{X}\bm{x}}{d}+\bm{T}_{pq}(\bm{X},\bm{x})\,,$

with non-negative parameters $\beta_{pq}$, and the additional vector
$\bm{T}_{pq}$ given in Table 2.

The approximation of $\bm{K}(\bm{X},\bm{X})$ and $\bm{K}(\bm{X},\bm{x})$ under
covariate shift can help us estimate the variance and bias. To ensure the
convergence of the residual term, we require $c_{pq}<2\theta_{q}-1/2$ in
Assumption 3.3.

Table 2: Parameters of the linearized kernel ${\bm{K}^{{\rm lin}}}$ involved
with the curvature of $h$, when $\bm{X}\sim p$.

Parameters | Inner-Product Kernels | Radial Kernels
---|---|---
$\alpha_{p}$ | $h(0)+h^{\prime\prime}(0)\frac{{\rm Tr}\left(\bm{\bm{\Sigma}}_{p}^{2}\right)}{2d^{2}}$ | $h(-2\tau_{p})+2h^{\prime\prime}(-2\tau_{p})\frac{{\rm Tr}\left(\bm{\bm{\Sigma}}_{p}^{2}\right)}{d^{2}}$
$\beta_{p}$ | $h^{\prime}(0)$ | $2h^{\prime}(-2\tau_{p})$
$\gamma_{p}$ | $h(\tau_{p})-h(0)-\tau_{p}h^{\prime}(0)$ | $h(0)-2\tau_{p}h^{\prime}(-2\tau_{p})-h(-2\tau_{p})$
$\bm{T}_{p}$ | $\bm{0}_{n\times n}$ |  $-h^{\prime}(-2\tau_{p})\bm{A}+\frac{1}{2}h^{\prime\prime}(-2\tau_{p})\bm{A}\odot\bm{A}$ 1
$\beta_{pq}$ | $h^{\prime}(0)$ | $2h^{\prime}(-(\tau_{p}+\tau_{q}))$
$\bm{T}_{pq}$ | $\bm{0}_{n\times 1}$ |  $-h(-(\tau_{p}+\tau_{q}))\cdot\mathbbm{1}-\frac{\beta_{pq}}{2}\bm{A}(\bm{X},\bm{x})$ 2

  * 1

$\bm{A}:=\mathbbm{1}\bm{\psi}^{\top}+\bm{\psi}\mathbbm{1}^{\top}$, where
$\bm{\psi}\in\mathbb{R}^{n}$ with
$\psi_{i}:=\|\bm{x}_{i}\|^{2}_{2}/d-\tau_{p}$.

  * 2

$\bm{A}(\bm{X},\bm{x}):=\psi_{\bm{x}}+\bm{\psi}$, where
$\psi_{\bm{x}}=\|\bm{x}\|^{2}_{2}/d-\tau_{q}$.

In the next, we are ready to present our results on the estimation for
variance and bias. For ease of analysis, we focus on the _inner product_
kernel for future estimation. The results on radial kernels require additional
efforts to control non-zero $\bm{T}_{pq}$, which goes beyond the main target
of this work.

###  4.3 Variance estimation

In this section, we present the estimation for the variance from the
perspective of a data-dependent regularized kernel. This helps us to have a
better understanding of the role of re-weighting in variance.

######  Theorem 4.4 (Variance: Data-dependent regularization).

Let $\delta\in(0,1)$, under Assumption 3.1, 3.2 and 3.3, then for large $d$,
with probability at least $1-\delta-2d^{-2}$ with respect to a draw of
$\bm{X}\sim p$ and $\epsilon>0$, the variance can be estimated by

$\displaystyle{\sf V}\leq$
$\displaystyle\frac{8\sigma_{\varepsilon}^{2}\|\bm{\Sigma}_{q}\|}{d}\underbrace{\mathcal{N}\left(\frac{\bm{X}\bm{X}^{\top}}{d}+\frac{\lambda
n}{\beta_{p}}{\overline{\bm{W}}({\bm{X}})}^{-1};\frac{\gamma_{p}}{\beta_{p}}\right)}_{\text{dominated
term}~{}{\sf V}_{\bm{x}}}$ (8) $\displaystyle+$
$\displaystyle\frac{8\sigma_{\varepsilon}^{2}}{\gamma_{p}^{2}}d^{-(4\theta_{q}-1-2c_{pq})}\log^{4(1+\epsilon)}d\,.$

Remark: We do not need the boundedness (Assumption 3.4) on $\overline{\bm{W}}$
for the estimation of variance. Nevertheless, Assumption 3.3, with
$c_{pq}<2\theta_{q}-\frac{1}{2}$, is required to ensure the similarity between
training and test distribution for the kernel approximation. Otherwise, a
large difference between training and test distribution leads to the
divergence of the residual term as $d\to\infty$. For example, when training
and test data are sampled from two distributions with almost zero overlap, it
will be impossible to generalize to the test distribution. In the unshifted
case ($\bm{\Sigma}_{p}=\bm{\Sigma}_{q}$ and $c_{pq}=0$ in Assumption 3.3)
leads to the second term in Eq. (8) admits a smaller value (or higher rate) at
the order of $d^{-(4\theta_{q}-1)}$.

Since the first term ${\sf V}_{\bm{x}}$ in Eq. (8) dominates the estimation
for variance, we detail this in the next part.

The dominated term in Eq. 8 can be represented as

$\displaystyle{\sf
V}_{\bm{x}}\asymp\frac{1}{d}\mathcal{N}\left(\frac{\bm{X}\bm{X}^{\top}}{d}+\frac{\lambda
n}{\beta_{p}}{\overline{\bm{W}}({\bm{X}})}^{-1};\frac{\gamma_{p}}{\beta_{p}}\right)\,,$
(9)

which implies that the variance is well controlled by the capacity of
$\bm{K}^{\rm lin}+\lambda n\overline{\bm{W}}^{-1}$. An intuitive example is to
choose $(\overline{\bm{W}})^{-1}$ by $c\bm{I}$ with a large constant $c$ such
that $\bm{K}^{\rm lin}+n\lambda\overline{\bm{W}}^{-1}$ has larger eigenvalues,
allowing for a smaller effective dimension; and thus the variance (strictly
speaking, its estimation) can decrease to some extent under this case. In
fact, since the re-weighting strategy $\overline{\bm{W}}$ is quite general
(not limited to the importance ratio $\bm{W}$), there always exists suitable
selection schemes that allow for a smaller
$\mathcal{N}\left(\frac{\bm{X}\bm{X}^{\top}}{d}+\frac{\lambda
n}{\beta_{p}}{\overline{\bm{W}}({\bm{X}})}^{-1};\frac{\gamma_{p}}{\beta_{p}}\right)$
(and smaller variance) in theory.

Besides, as a diagonal matrix $\overline{\bm{W}}$, each element
$[\overline{\bm{W}}]_{ii}$ only affects the similarity of the data point
${\bm{x}}_{i}$ and itself. That means, the data points are “importance
reweighted” but the similarity among different data points is unchanged. In
this case, importance weighting can be regarded as a special case of active
learning and even data subsampling (Kolossov et al., 2024). This motivates us
to design more advanced active learning-based algorithms to select important
data points, which is beneficial to handle covariate shifts in practice.

###  4.4 Bias estimation

In this subsection, we aim to derive the estimation for bias. We first present
the spectral decomposition of the kernel to handle all scales of
regularization parameter $\lambda>0$, see Section 4.4.1. In the next, we
analyze a special choice of regularization parameter $\lambda$, i.e.,
$\lambda\asymp n^{-c_{\lambda}}$, which stems from the classical analysis in
the kernel literature (Gogolashvili et al., 2023; Ma et al., 2023) and
incorporates the dimension-dependent shifts to accommodate the high-
dimensional setting, see Section 4.4.2.

####  4.4.1 Bias under arbitrary regularization

Here we present the bias estimation from the spectral decomposition of the
kernel. Note that the analysis in this part allows for any choice of
regularization parameter. We consider the uniform boundedness of the re-
weighting function and RKHS norm of the target function, i.e., a special case
of Assumption 3.5 and 3.4. Accordingly, we have the following theorem, with
the proof deferred to Section A.4.

######  Theorem 4.5 (Bias under arbitrary $\lambda$).

Let $\delta\in(0,1)$, under Assumption 3.1, 3.2 and 3.3, Assumption 3.5 with
$\bar{r}=\frac{1}{2},c_{\mathcal{H}}=0$, Assumption 3.4 for bounded ratio:
$\overline{w}(\bm{x}),w(\bm{x})\leq W_{\max}$. We have the bias ${\sf B}$ is
upper bounded as ${\sf B}\leq{\sf B}_{\rm in}+{\sf B}_{\rm iw}\,,$ where ${\sf
B}_{\rm in}$ is the _intrinsic bias_ that only depends on the problem of
covariate shift from $p$ to $q$ via the ratio ${w}(\bm{x})$

$\displaystyle{\sf B}_{\rm in}\\!:=\\!{\rm Tr}\left(\bm{K}^{\rm
lin}{\bm{W}}\right)/n\,.$

The second term is the re-weighting bias ${\sf B}_{\rm iw}$ that depends on
the choice of $\overline{w}(\bm{x})$, $w(\bm{x})$, and $\lambda$, for
$\epsilon>0$,

$\begin{split}&{\sf B}_{\rm iw}\\!:=\\!{4\lambda^{2}n}{\rm
Tr}\left(\left(\lambda n\bm{I}\\!+\\!{{\bm{K}^{\rm
lin}\overline{\bm{W}}}}\right)^{-2}{{\bm{K}^{\rm
lin}{\bm{W}}}}\right)\\!+\\!\lambda^{2}\kappa W_{\max}\\\ &+6\kappa
W_{\max}\sqrt{\frac{\log
1/\delta}{2n}}+\widetilde{C}d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)W_{\max},\end{split}$

with probability at least $1-4\delta$ for sufficiently large $d$.

Remark: We make the following remarks:

1) In our analysis, the first term ${\sf B}_{\rm in}$ describes the intrinsic
bias of the distribution shift problem, in a constant order, which is
independent of any specific re-weighting way. This coincides with results from
high dimensional statistics for interpolation learning, e.g., (Hastie et al.,
2022; Liang & Rakhlin, 2020).

2) The second term ${\sf B}_{\rm iw}$ involves the re-weighting strategy and
its original ratio, which contributes to the importance re-weighting bias.
Since $\overline{\bm{W}}$ can be chosen quite generally, it allows for a
smaller ${\sf B}_{\rm in}$ to some extent. More importantly, as $\lambda\to
0$, the re-weighting bias ${\sf B}_{\rm iw}$ will be close to zero.

Further, if we choose the re-weighting function $\overline{w}$ with the ratio
$w$, then the estimation for the bias in Theorem 4.5 can be simplified as
below, Section A.4.

######  Corollary 4.5.1 (Bias: $\overline{w}=w$).

Under the same setting of Theorem 4.5, choosing the re-weighting strategy
$\overline{w}$ as the ratio $w$, and $\lambda=o(1)$, for sufficiently large
$d$, the bias can be simplified as

${\sf B}\lesssim\frac{{\rm Tr}(\bm{K}^{\rm
lin}\bm{W})}{n}+\lambda^{2}n\mathcal{N}\left({\bm{K}^{\rm
lin}\bm{W}},n\lambda\right)+o(1)\,,w.h.p\,,$

We can see that the bias term is controlled by the spectral decay of the re-
weighting kernel matrix $\bm{K}^{\rm lin}\bm{W}$ via the importance ratio.

Discussion on excess risk: Combining Eq. (9) and Theorem 4.5, taking
$\lambda=o(1)$, the summation of the bias and variance (i.e., the excess risk)
admits

$\begin{split}&{\sf B+V}\approx{\sf B}_{\rm in}+{\sf V}_{\bm{x}}\\\
\lesssim&\frac{{\rm Tr}(\bm{K}^{\rm
lin}\bm{W})}{n}+\frac{1}{d}\mathcal{N}\left(\frac{\bm{X}\bm{X}^{\top}}{d}+\frac{\lambda
n}{\beta_{p}}{\overline{\bm{W}}({\bm{X}})}^{-1};\frac{\gamma_{p}}{\beta_{p}}\right)\,.\end{split}$

There exists a trade-off between the intrinsic bias ${\sf B}_{\rm in}$ and the
dominated term ${\sf V}_{\bm{x}}$ in variance: a suitable $\overline{\bm{W}}$
that can be chosen generally, allows for a decreasing variance but the
intrinsic bias ${\sf B}_{\rm in}$ will not decrease due to the covariate shift
problem itself, determined by
${w}(\bm{x})={\mathrm{d}}q(\bm{x})/{\mathrm{d}}p(\bm{x})$. Nevertheless, at
least, under re-weighting, the variance and re-weighting bias can be
decreased; the estimator can still generalize well, and the convergence rate
is unchanged.

####  4.4.2 Bias under well-chosen regularization

We follow the classical analysis for kernel methods (which does not require
the high dimension condition) to derive the estimation for bias. This analysis
cannot deal with the situation where $\lambda\to 0$.

We start by defining the data-free limit of Eq. 6. Denote the data-free limit
of $\overline{f}_{\lambda,\bm{X}}$ by $\overline{f}_{\lambda}$,

$\displaystyle\overline{f}_{\lambda}$
$\displaystyle:=\operatornamewithlimits{arg\,min}_{f\in\mathcal{H}}\left\\{\left\|f-f_{\rho}\right\|_{\overline{q}}^{2}+\lambda\|f\|_{\mathcal{H}}^{2}\right\\}\,,$

then the solution $\overline{f}_{\lambda}$ in the data-free limit can be
written as

$\displaystyle\overline{f}_{\lambda}$
$\displaystyle=\left(L_{\overline{q}}+\lambda
I\right)^{-1}L_{\overline{q}}f_{\rho}\,.$

Accordingly, the bias can be decomposed into

$\displaystyle{\sf
B}\leq\|\overline{f}_{\lambda,\bm{X}}-\overline{f}_{\lambda}\|_{q}+\|\overline{f}_{\lambda}-f_{\rho}\|_{q}:={\sf
B}_{\rm data}+{\sf B}_{\lambda}\,,$

where ${\sf B}_{\rm data}$ denotes the data-dependent bias from $\bm{X}\sim
p$, and ${\sf B}_{\lambda}$ denotes the (data-free) regularization bias by
$\lambda>0$.

We present the estimation for the bias under a (not small) regularization
parameter to balance ${\sf B}_{\rm data}$ and ${\sf B}_{\lambda}$, see the
proof in Section A.4. The assumptions here are weaker than those in Theorem
4.5, exemplified by the assumptions on the source condition (Assumption 3.5)
and the upper bound of the density ratio (Assumption 3.4).

######  Theorem 4.6 (Bias).

Under Assumption 3.1, 3.2, 3.5, 3.6 and 3.4 with
$\overline{r}\in[\frac{1}{2},1)$, $E_{q},E_{\overline{q}}>0$,
$s_{q},s_{\overline{q}}\in[0,1]$, $t_{w},t_{\overline{w}}\in[0,1]$,
$W_{w}(d),W_{\overline{w}}(d),\sigma_{w}(d),\sigma_{\overline{w}}(d)\geq 0$,
$c_{w,1},c_{w,2},c_{\overline{w},1},c_{\overline{w},2}\geq 0$, and
$c_{\mathcal{H}}\geq 0$. When $n,d\to\infty,n/d\to\zeta$, for any
$\delta\in(0,1)$, let
$\overline{A}=t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}}$ and the
following two scalars $c_{\lambda},C_{\lambda}$,

$\displaystyle
c_{\lambda}:=\frac{1-4c_{\overline{w},2}}{2\overline{r}+\overline{A}}\,,$

and

$\displaystyle C_{\lambda}^{(1+\overline{A})s_{\overline{q}}}\geq
64(W_{\overline{w}}+\sigma_{\overline{w}}^{2})E_{\overline{q}}^{2(1-t_{\overline{w}})}(2/\zeta)^{2c_{\overline{w},2}}\log^{2}(6/\delta)\,.$

Choosing $\lambda:=\cdot C_{\lambda}n^{-c_{\lambda}}$, then with probability
at least $1-\delta$, for sufficiently large $d$, when
$c_{\mathcal{H}}<\overline{r}c_{\lambda}$, it holds that

$\displaystyle{\sf B}\lesssim
n^{-\overline{r}c_{\lambda}+c_{\mathcal{H}}}\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{1/2}\,.$

For general $\lambda$, we have, with $\lesssim$ here hiding the dependence on
$n$,

$\displaystyle{\sf
B}\lesssim(\lambda^{\overline{r}}+\lambda^{-\frac{1}{2}})\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{\frac{1}{2}}\,.$

Remark: As shown in the proof, when $\lambda\to 0$, the upper bound in Theorem
4.6 will diverge ${O}(\lambda^{-1/2})$; and when $\lambda\to\infty$, the upper
bound in Theorem 4.5 will diverge $O(\lambda^{2})$. Therefore, we can combine
Theorems 4.6 and 4.5:

${\sf
B}\lesssim\min\\{(\lambda^{\overline{r}}+\lambda^{-\frac{1}{2}})\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{\frac{1}{2}},{\sf
B}_{\rm in}+{\sf B}_{\rm iw}\\}\,.$

That means, under the assumption of Theorem 4.5, if the regularization
parameter decays to 0 with a certain power of $n$, then Theorem 4.6 provides a
good estimation, where the bias converges to zero. If $\lambda$ decays much
faster and is sufficiently close to 0, we adopt Theorem 4.5, which provide a
uniform upper bound.

##  5 Conclusion

In this work, we provide a refined analysis on high dimensional kernel ridge
regression under covariate shifts. Our results provide a non-asymptotic
expansion of inner-product and radial kernels in high dimensions under
covariate shifts. Our results on variance show that, the variance can be well
controlled by the capacity of the data-dependent regularized kernel. Our
results on bias give a thorough analysis, demonstrating that the intrinsic
bias cannot be decreased but the re-weighting bias can tend to zero if the
regularization term is sufficiently small. One limitation of this work is that
our results only provide the upper bounds as well as empirical validation in
Appendix B but no exact formulation of the bias and variance. This is because
RMT cannot be directly applied to our setting when involving the IW strategy.
Nevertheless, our estimation still provides interesting findings to understand
the role of re-weighting in terms of bias-variance trade-off.

## Acknowledgements

This work was carried out when YC was an intern in the EPFL LIONS group. This
work was supported by Hasler Foundation Program: Hasler Responsible AI
(project number 21043), the Army Research Office and was accomplished under
Grant Number W911NF-24-1-0048, and Swiss National Science Foundation (SNSF)
under grant number 200021_205011. TS was partially supported by JSPS KAKENHI
(24K02905) and JST CREST (JPMJCR2115, JPMJCR2015). Corresponding author:
Fanghui Liu.

## Impact statement

In this work, we study the role of re-weighting strategy in a high-capacity
model, i.e., kernel ridge regression in high dimensions. Since this work is
theoretical, there is no potential implications in security or trustworthy
machine learning.

## References

  * Aerni et al. (2023) Aerni, M., Milanta, M., Donhauser, K., and Yang, F.  Strong inductive biases provably prevent harmless interpolation.  _arXiv preprint arXiv:2301.07605_ , 2023.
  * Boucheron et al. (2013) Boucheron, S., Lugosi, G., and Massart, P.  Concentration inequalities: A nonasymptotic theory of independence,(2013), 2013.
  * Caponnetto & De Vito (2007) Caponnetto, A. and De Vito, E.  Optimal rates for the regularized least-squares algorithm.  _Foundations of Computational Mathematics_ , 7(3):331–368, 2007.
  * Cortes et al. (2010) Cortes, C., Mansour, Y., and Mohri, M.  Learning bounds for importance weighting.  In _Advances in Neural Information Processing Systems_ , pp. 442–450, 2010.
  * Cucker & Zhou (2007) Cucker, F. and Zhou, D. X.  _Learning theory: an approximation theory viewpoint_ , volume 24.  Cambridge University Press, 2007.
  * Dicker (2016) Dicker, L. H.  Ridge regression and asymptotic minimax estimation over spheres of growing dimension.  _arXiv preprint arXiv:1601.03900_ , 2016.
  * Dobriban & Wager (2018) Dobriban, E. and Wager, S.  High-dimensional asymptotics of prediction: Ridge regression and classification.  _The Annals of Statistics_ , 46(1):247–279, 2018.
  * El Karoui (2010) El Karoui, N.  The spectrum of kernel random matrices.  _Ann. Statist._ , 38(1):1–50, 2010.
  * Fang et al. (2020) Fang, T., Lu, N., Niu, G., and Sugiyama, M.  Rethinking importance weighting for deep learning under distribution shift.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , pp. 11996–12007, 2020.
  * Feng et al. (2023) Feng, X., He, X., Wang, C., Wang, C., and Zhang, J.  Towards a unified analysis of kernel-based methods under covariate shift.  _arXiv preprint arXiv:2310.08237_ , 2023.
  * Ge et al. (2023) Ge, J., Tang, S., Fan, J., Ma, C., and Jin, C.  Maximum likelihood estimation is all you need for well-specified covariate shift.  _arXiv preprint arXiv:2311.15961_ , 2023.
  * Ghorbani et al. (2019) Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A.  Linearized two-layers neural networks in high dimension.  _arXiv preprint arXiv:1904.12191_ , 2019.
  * Ghorbani et al. (2020) Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A.  When do neural networks outperform kernel methods?  _Advances in Neural Information Processing Systems_ , 33:14820–14830, 2020.
  * Ghosh et al. (2021) Ghosh, N., Mei, S., and Yu, B.  The three stages of learning dynamics in high-dimensional kernel methods.  _arXiv preprint arXiv:2111.07167_ , 2021.
  * Gogolashvili et al. (2023) Gogolashvili, D., Zecchin, M., Kanagawa, M., Kountouris, M., and Filippone, M.  When is importance weighting correction needed for covariate shift adaptation?  _arXiv preprint arXiv:2303.04020_ , 2023.
  * Hastie et al. (2022) Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J.  Surprises in high-dimensional ridgeless least squares interpolation.  _Annals of statistics_ , 50(2):949, 2022.
  * Huang et al. (2006) Huang, J., Smola, A. J., Gretton, A., Borgwardt, K. M., and Scholkopf, B.  Correcting sample selection bias by unlabeled data.  In _Proceedings of the 19th International Conference on Neural Information Processing Systems_ , pp. 601–608, 2006.
  * Jacot et al. (2018) Jacot, A., Gabriel, F., and Hongler, C.  Neural tangent kernel: Convergence and generalization in neural networks.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Jacot et al. (2020) Jacot, A., Simsek, B., Spadaro, F., Hongler, C., and Gabriel, F.  Kernel alignment risk estimator: Risk prediction from training data.  _Advances in neural information processing systems_ , 33:15568–15578, 2020.
  * Karoui (2013) Karoui, N. E.  Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results.  _arXiv preprint arXiv:1311.2445_ , 2013.
  * Kolossov et al. (2024) Kolossov, G., Montanari, A., and Tandon, P.  Towards a statistical theory of data selection under weak supervision.  In _The Twelfth International Conference on Learning Representations_ , 2024.
  * Kpotufe & Martinet (2021) Kpotufe, S. and Martinet, G.  Marginal singularity and the benefits of labels in covariate-shift.  _The Annals of Statistics_ , 49(6):3299–3323, 2021.
  * Liang & Rakhlin (2020) Liang, T. and Rakhlin, A.  Just interpolate: Kernel “ridgeless” regression can generalize.  _THE ANNALS_ , 48(3):1329–1347, 2020.
  * Liu et al. (2021) Liu, F., Liao, Z., and Suykens, J.  Kernel regression in high dimensions: Refined analysis beyond double descent.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 649–657. PMLR, 2021.
  * Lu et al. (2023) Lu, W., Zhang, H., Li, Y., Xu, M., and Lin, Q.  Optimal rate of kernel regression in large dimensions.  _arXiv preprint arXiv:2309.04268_ , 2023.
  * Ma et al. (2023) Ma, C., Pathak, R., and Wainwright, M. J.  Optimally tackling covariate shift in rkhs-based nonparametric regression.  _The Annals of Statistics_ , 51(2):738–761, 2023.
  * McRae et al. (2022) McRae, A. D., Karnik, S., Davenport, M., and Muthukumar, V. K.  Harmless interpolation in regression and classification with structured features.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 5853–5875. PMLR, 2022.
  * Mei et al. (2021) Mei, S., Misiakiewicz, T., and Montanari, A.  Learning with invariances in random features and kernel models.  In _Conference on Learning Theory_ , pp. 3351–3418. PMLR, 2021.
  * Mei et al. (2022) Mei, S., Misiakiewicz, T., and Montanari, A.  Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration.  _Applied and Computational Harmonic Analysis_ , 59:3–84, 2022.
  * Mercer (1909) Mercer, J.  Xvi. functions of positive and negative type, and their connection the theory of integral equations.  _Philosophical transactions of the royal society of London. Series A, containing papers of a mathematical or physical character_ , 209(441-458):415–446, 1909.
  * Misiakiewicz & Mei (2022) Misiakiewicz, T. and Mei, S.  Learning with convolution and pooling operations in kernel methods.  _Advances in Neural Information Processing Systems_ , 35:29014–29025, 2022.
  * Nakkiran et al. (2020) Nakkiran, P., Venkat, P., Kakade, S., and Ma, T.  Optimal regularization can mitigate double descent.  _arXiv preprint arXiv:2003.01897_ , 2020.
  * Pathak et al. (2022) Pathak, R., Ma, C., and Wainwright, M.  A new similarity measure for covariate shift with applications to nonparametric regression.  In _International Conference on Machine Learning_ , pp. 17517–17530. PMLR, 2022.
  * Shimodaira (2000) Shimodaira, H.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  _Journal of Statistical Planning and Inference_ , 90(2):227–244, 2000.
  * Smale & Zhou (2004) Smale, S. and Zhou, D.-X.  Shannon sampling and function reconstruction from point values.  _Bulletin of the American Mathematical Society_ , 41(3):279–305, 2004.
  * Smale & Zhou (2007) Smale, S. and Zhou, D.-X.  Learning theory estimates via integral operators and their approximations.  _Constructive approximation_ , 26(2):153–172, 2007.
  * Sugiyama et al. (2007) Sugiyama, M., Nakajima, S., Kashima, H., Buenau, P., and Kawanabe, M.  Direct importance estimation with model selection and its application to covariate shift adaptation.  _Advances in neural information processing systems_ , 20, 2007.
  * Sugiyama et al. (2008) Sugiyama, M., Suzuki, T., Nakajima, S., Kashima, H., Von Bünau, P., and Kawanabe, M.  Direct importance estimation for covariate shift adaptation.  _Annals of the Institute of Statistical Mathematics_ , 60:699–746, 2008.
  * Sugiyama et al. (2012) Sugiyama, M., Suzuki, T., and Kanamori, T.  _Density Ratio Estimation in Machine Learning_.  Cambridge University Press, 2012.
  * Tripuraneni et al. (2021a) Tripuraneni, N., Adlam, B., and Pennington, J.  Covariate shift in high-dimensional random feature regression.  _arXiv preprint arXiv:2111.08234_ , 2021a.
  * Tripuraneni et al. (2021b) Tripuraneni, N., Adlam, B., and Pennington, J.  Overparameterization improves robustness to covariate shift in high dimensions.  _Advances in Neural Information Processing Systems_ , 34:13883–13897, 2021b.
  * Vapnik (1999) Vapnik, V.  _The nature of statistical learning theory_.  Springer science & business media, 1999.
  * Wu & Xu (2020) Wu, D. and Xu, J.  On the optimal weighted $\ell_{2}$ regularization in overparameterized linear regression.  _Advances in Neural Information Processing Systems_ , 33:10112–10123, 2020.
  * Xiao et al. (2022) Xiao, L., Hu, H., Misiakiewicz, T., Lu, Y., and Pennington, J.  Precise learning curves and higher-order scalings for dot-product kernel regression.  _Advances in Neural Information Processing Systems_ , 35:4558–4570, 2022.
  * Yu et al. (2016) Yu, F. X. X., Suresh, A. T., Choromanski, K. M., Holtmann-Rice, D. N., and Kumar, S.  Orthogonal random features.  _Advances in neural information processing systems_ , 29, 2016.
  * Zhai et al. (2023) Zhai, R., Dan, C., Kolter, J. Z., and Ravikumar, P. K.  Understanding why generalized reweighting does not improve over ERM.  In _The Eleventh International Conference on Learning Representations_ , 2023.

##  Appendix A Proofs

###  A.1 Bias-variance decomposition

###### Proof of Lemma 4.1.

Recall the closed-form solution of our IW estimator
$\overline{f}_{\lambda,\bm{Z}}(\bm{x})$ and its noiseless version
$\overline{f}_{\lambda,\bm{X}}(\bm{x})$, we have

$\displaystyle\overline{f}_{\lambda,\bm{Z}}(\bm{x})$
$\displaystyle=\bm{K}(\bm{x},\bm{X})(\bm{K}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}\bm{y}\,.$
$\displaystyle\overline{f}_{\lambda,\bm{X}}(\bm{x})$
$\displaystyle=\bm{K}(\bm{x},\bm{X})(\bm{K}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}f_{\rho}(\bm{X})\,.$

Define
$\bm{\varepsilon}:=\bm{y}-\mathbb{E}[\bm{y}|\bm{X}]=\bm{y}-f_{\rho}(\bm{X})$,
due to $\mathbb{E}_{y|\bm{X}}(\bm{\varepsilon})=0$, we have

$\displaystyle\mathbb{E}_{\bm{y}|\bm{X}}(\overline{f}_{\lambda,\bm{Z}}(\bm{x})-f_{\rho})^{2}$
$\displaystyle=\mathbb{E}_{\bm{y}|\bm{X}}\left(K(\bm{x},\bm{X})(\bm{K}(\bm{X},\bm{X})+\lambda
n\bm{I})^{-1}\bm{\varepsilon}\right)^{2}+(\overline{f}_{\lambda,\bm{X}}(\bm{x})-f_{\rho}(\bm{x}))^{2}\,.$

Using Fubini’s theorem, we have

$\displaystyle\mathbb{E}_{\bm{y}|\bm{X}}\|\overline{f}_{\lambda,\bm{Z}}-f_{\rho}\|^{2}_{q}=\int\mathbb{E}_{\bm{y}|\bm{X}}(\overline{f}_{\lambda,\bm{Z}}(\bm{x})-f_{\rho})^{2}{\mathrm{d}}q(\bm{x})=\mathbb{E}_{\bm{y}|\bm{X}}\|\overline{f}_{\lambda,\bm{Z}}-\overline{f}_{\lambda,\bm{X}}\|_{q}^{2}+\|\overline{f}_{\lambda,\bm{X}}-f_{\rho}\|_{q}^{2}\,,$

which implies

$\displaystyle\mathbb{E}_{\bm{y}|\bm{X}}\|\overline{f}_{\lambda,\bm{Z}}-f_{\rho}\|^{2}_{q}=\mathbb{E}_{\bm{y}|\bm{X}}\|\overline{f}_{\lambda,\bm{Z}}-\overline{f}_{\lambda,\bm{X}}\|_{q}^{2}+\|\overline{f}_{\lambda,\bm{X}}-f_{\rho}\|_{q}^{2}\,.$

∎

###  A.2 Approximation

####  A.2.1 Inner-product kernel

######  Lemma A.1.

Under Assumption 3.2 and 3.3, and $\theta_{p},\theta_{q},c_{pq}$’s
definitions, we have with probability at least $1-d^{-2}$ with respect to the
draw of $\bm{X}\sim p$, for $\epsilon>0$ and $d$ large enough,

$\displaystyle\mathbb{E}_{q}\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\|^{2}$ $\displaystyle\leq
d^{-(4\theta_{q}-1-2c_{pq})}\log^{4(1+\epsilon)}d\,.$

###### Proof of Lemma A.1.

The proof framework follows (Liang & Rakhlin, 2020, Lemma B.2) but we need to
provide a precise analysis to handle the covariance shift for $\bm{x}\sim q$.
Conditioned on $\bm{x}_{i},1\leq i\leq n$, by Bernstein’s inequality
(Boucheron et al., 2013), with probability at least $1-\exp(-t)$ on
$\bm{x}\sim q$, for all $i\in[n]$, we have

$\displaystyle\left|\frac{\bm{x}^{\top}\bm{x}_{i}}{d}\right|$
$\displaystyle=\left|\frac{\langle\bm{\Sigma}_{q}^{1/2}\bm{x}_{i},\bm{\Sigma}_{q}^{-1/2}\bm{x}\rangle}{d}\right|$
$\displaystyle\leq\sqrt{\frac{2\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|^{2}}{d}}\frac{\sqrt{t}+\log^{\frac{1+\epsilon}{2}}d}{\sqrt{d}}+\frac{1}{3}\frac{\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|_{\infty}d^{\frac{2}{8+m_{q}}}(t+\log^{1+\epsilon}d)}{d}$
$\displaystyle\leq\sqrt{\frac{2\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|^{2}}{d}}\frac{\sqrt{t}+\log^{\frac{1+\epsilon}{2}}d}{\sqrt{d}}+\frac{1}{3}\frac{\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|d^{\frac{2}{8+m_{q}}}(t+\log^{1+\epsilon}d)}{d}$
$\displaystyle=\frac{\sqrt{2}\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|}{\sqrt{d}}\frac{\sqrt{t}+\log^{\frac{1+\epsilon}{2}}d}{\sqrt{d}}+\frac{1}{3}\frac{\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|}{\sqrt{d}}d^{\frac{2}{8+m_{q}}-\frac{1}{2}}(t+\log^{1+\epsilon}d)$
$\displaystyle=\frac{\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|}{\sqrt{d}}\left(\sqrt{2}d^{-1/2}(\sqrt{t}+\log^{\frac{1+\epsilon}{2}}d)+\frac{1}{3}d^{-\theta_{q}}(t+\log^{1+\epsilon}d)\right)\,,$

where the first inequality uses Assumption 3.2 such that

$\displaystyle\max_{k}\left|[\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}](k)\cdot[\bm{\Sigma}_{q}^{-1/2}\bm{x}](k)\right|\leq\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|_{\infty}d^{\frac{2}{8+m_{q}}}.$

Applying Lemma A.4 with Assumption 3.2 and 3.3, we have for all $j$, with
probability at least $1-d^{-2}$ on $\mathcal{X}$

$\displaystyle\max_{i}\frac{\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|^{2}}{d}\leq\|\bm{\Sigma}_{q}\|\max_{i}\frac{\|\bm{\Sigma}_{q}^{-1/2}\bm{x}_{i}\|^{2}}{d}=\|\bm{\Sigma}_{q}\|\max_{i}\frac{\|\bm{\Sigma}_{q}^{-1/2}\bm{\Sigma}_{p}^{1/2}\bm{\Sigma}_{p}^{-1/2}\bm{x}_{i}\|^{2}}{d}\lesssim\frac{{\rm
Tr}(\bm{\Sigma}_{pq})}{d}+d^{-\theta_{p}}\log^{\frac{1+\epsilon}{2}}d\,.$

We use the entry-wise Taylor expansion for the smooth kernel, let
$\bm{x}_{i}^{\prime}=c\bm{x}+(1-c)\bm{x}_{i}$ for some $c\in[0,1]$,

$\displaystyle K(\bm{x},\bm{x}_{i})-K^{\rm lin}(\bm{x},\bm{x}_{i})$
$\displaystyle=\frac{h^{\prime\prime}(\bm{x}_{i}^{\prime})}{2}\left(\frac{\bm{x}^{\top}\bm{x}_{i}}{d}\right)^{2}\lesssim\left(\frac{\bm{x}^{\top}\bm{x}_{i}}{d}\right)^{2}\,.$

Therefore, with probability at least $1-\exp(-t)$ with respect to $\bm{x}\sim
q$, conditionally on $\bm{x}_{i}\sim p,1\leq i\leq n$, for sufficiently large
$d$,

$\begin{split}\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\|&\lesssim\sqrt{d}\max_{i}\left(\frac{\bm{x}^{\top}\bm{x}_{i}}{d}\right)^{2}\\\
&\lesssim\sqrt{d}\max_{i}\frac{\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|^{2}}{d}\left(d^{-1}(t+\log^{1+\epsilon}d)+d^{-2\theta_{q}}(t^{2}+\log^{2(1+\epsilon)}d)\right)\\\
&\lesssim\sqrt{d}\max_{i}\frac{\|\bm{\Sigma}_{q}^{1/2}\bm{x}_{i}\|^{2}}{d}\left(d^{-2\theta_{q}}(t^{2}+\log^{2(1+\epsilon)}d)\right)\qquad\text{[since
$\theta_{q}\leq\frac{1}{2}$]}\\\ &\lesssim
d^{-2\theta_{q}+1/2}(t^{2}+\log^{2(1+\epsilon)}d)\left(\frac{{\rm
Tr}(\bm{\Sigma}_{pq})}{d}+d^{-\theta_{p}}\log^{\frac{1+\epsilon}{2}}d\right)\\\
&\lesssim d^{-2\theta_{q}+1/2+c_{pq}}(t^{2}+\log^{2(1+\epsilon)}d)\end{split}$
(10)

Define $z(t):=C\cdot
d^{-2\theta_{q}+1/2+c_{pq}}(t^{2}+\log^{2(1+\epsilon)}d)$, the above states
that conditioned on $\bm{X}$

$\displaystyle\mathbb{P}\left(\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\|\geq z(t)\right)\leq 2\exp(-t),\quad\forall t>0\,.$

Therefore, by the change of variables, we have

$\begin{split}\mathbb{E}_{\bm{x}\sim q}\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\|^{2}&=\int_{\mathbb{R}_{+}}2z\cdot\mathbb{P}(\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\|\geq z){\mathrm{d}}z\\\ &\leq
C\int_{\mathbb{R}_{+}}d^{-4\theta_{q}+1+2c_{pq}}(t^{2}+\log^{2(1+\epsilon)}d)\exp(-t)2t{\mathrm{d}}t\\\
&\leq
C\int_{\mathbb{R}_{+}}d^{-4\theta_{q}+1+2c_{pq}}t^{3}\log^{2(1+\epsilon)}d\exp(-t){\mathrm{d}}t\\\
&\lesssim d^{-(4\theta_{q}-1-2c_{pq})}\log^{4(1+\epsilon)}d\,,\end{split}$

with probability at least $1-d^{-2}$ on $\bm{X}$, for sufficiently large $d$.
Here the constant is superseded by an additional $\log^{2(1+\epsilon)}d$.
Therefore, as long as Assumption 3.3 is satisfied, we have
$4\theta_{q}-1-2c_{pq}>0$, and the residual term above will converge to 0 as
$d\to\infty$. ∎

####  A.2.2 Radial kernel

######  Lemma A.2.

Let $\\{\bm{x}_{i}\\}_{i=1}^{n}$ be i.i.d. random vectors in $\mathbb{R}^{d}$,
whose entries are i.i.d., mean $0$, variance $1$ and $|x_{i}(k)|\leq C\cdot
d^{\frac{2}{8+m}}$. For any positive semi-definite matrices $\bm{\Sigma}$
whose operator norms are uniformly bounded in $d$, and $n/d$ is asymptotically
bounded, with $\theta=\frac{1}{2}-\frac{2}{8+m}$, with probability at least
$1-d^{-2}$, for $\epsilon>0$, we have

$\displaystyle\max_{i\neq
j}\left|\frac{(\bm{x}_{i}-\bm{x}_{j})^{\top}\bm{\Sigma}(\bm{x}_{i}-\bm{x}_{j})}{d}-2\frac{{\rm
Tr}(\bm{\Sigma})}{d}\right|\leq 4d^{-\theta}\log^{\frac{1+\epsilon}{2}}d\,,$

for $d$ large enough.

###### Proof of Lemma A.2.

We write, for $i\neq j$,

$\displaystyle(\bm{x}_{i}-\bm{x}_{j})^{\top}\bm{\Sigma}(\bm{x}_{i}-\bm{x}_{j})-2{\rm
Tr}(\bm{\Sigma})=\bm{x}_{i}^{\top}\bm{\Sigma}\bm{x}_{i}+\bm{x}_{j}^{\top}\bm{\Sigma}\bm{x}_{j}-2\bm{x}_{i}^{\top}\bm{\Sigma}\bm{x}_{j}\,.$

By Lemma A.4, for $i\neq j$,

$\displaystyle\left|\frac{\bm{x}_{i}^{\top}\bm{\Sigma}\bm{x}_{i}}{d}-\frac{{\rm
Tr}(\bm{\Sigma})}{d}\right|\leq
d^{-\theta}\log^{\frac{1+\epsilon}{2}}d,\quad\left|\frac{\bm{x}_{i}^{\top}\bm{\Sigma}\bm{x}_{j}}{d}\right|\leq
d^{-\theta}\log^{\frac{1+\epsilon}{2}}d\,.$

Therefore,

$\displaystyle\left|\frac{(\bm{x}_{i}-\bm{x}_{j})^{\top}\bm{\Sigma}(\bm{x}_{i}-\bm{x}_{j})}{d}-2\frac{{\rm
Tr}(\bm{\Sigma})}{d}\right|$
$\displaystyle=\left|\left(\frac{\bm{x}_{i}^{\top}\bm{\Sigma}\bm{x}_{i}}{d}-\frac{{\rm
Tr}(\bm{\Sigma})}{d}\right)+\left(\frac{\bm{x}_{j}^{\top}\bm{\Sigma}\bm{x}_{j}}{d}-\frac{{\rm
Tr}(\bm{\Sigma})}{d}\right)-2\frac{\bm{x}_{i}^{\top}\bm{\Sigma}\bm{x}_{j}}{d}\right|$
$\displaystyle\leq 4d^{-\theta}\log^{\frac{1+\epsilon}{2}}d\,.$

∎

######  Lemma A.3.

Under the Assumption 3.1, 3.2 and 3.3, and $\theta_{p},\theta_{q},c_{pq}$’s
definitions, we have with probability at least $1-3d^{-2}$ with respect to the
draw of $\bm{X}\sim p$, for $d$ large enough,

$\displaystyle\mathbb{E}_{q}\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\|^{2}$ $\displaystyle\lesssim
d^{-(4\min\\{\theta_{p},\theta_{q}-c_{pq}/2\\}-1)}\log^{2(1+\epsilon)}d\,.$

###### Proof of Lemma A.3.

We start with the entry-wise Taylor expansion for the smooth kernel at
$-(\tau_{p}+\tau_{q})$

$\displaystyle
K(\bm{x},\bm{x}_{j})=h\left(-\frac{1}{d}\|\bm{x}-\bm{x}_{j}\|_{2}^{2}\right)$
$\displaystyle=$ $\displaystyle
h(-(\tau_{p}+\tau_{q}))-h^{\prime}(-(\tau_{p}+\tau_{q}))\left(\frac{1}{d}\|\bm{x}-\bm{x}_{j}\|^{2}-(\tau_{p}+\tau_{q})\right)+\frac{h^{\prime\prime}(-(\tau_{p}+\tau_{q}))}{2}\left(\frac{1}{d}\|\bm{x}-\bm{x}_{j}\|^{2}-(\tau_{p}+\tau_{q})\right)^{2}$
$\displaystyle+$ $\displaystyle O(d^{-3/2})$ $\displaystyle=$ $\displaystyle
h(-(\tau_{p}+\tau_{q}))-h^{\prime}(-(\tau_{p}+\tau_{q}))\left(\psi_{\bm{x}}+\psi_{j}-\frac{2\bm{x}^{\\!\top}\bm{x}_{j}}{d}\right)+\frac{h^{\prime\prime}(\tau_{p}+\tau_{q})}{2}\left(\psi_{\bm{x}}+\psi_{j}-\frac{2\bm{x}^{\\!\top}\bm{x}_{j}}{d}\right)^{2}+O(d^{-3/2})$
$\displaystyle=$ $\displaystyle K^{\rm
lin}(\bm{x},\bm{x}_{j})+\frac{h^{\prime\prime}(-(\tau_{p}+\tau_{q}))}{2}\left(\frac{1}{d}\|\bm{x}-\bm{x}_{j}\|_{2}^{2}-(\tau_{p}+\tau_{q})\right)^{2}+O(d^{-3/2})\,,$

where $\psi_{j}=\|\bm{x}_{j}\|^{2}_{2}/d-\tau_{p}$ for $j\in[n]$ as defined
before. We expand
$\frac{1}{d}\|\bm{x}-\bm{x}_{j}\|_{2}^{2}-(\tau_{p}+\tau_{q})$ by

$\displaystyle\frac{1}{d}\|\bm{x}-\bm{x}_{j}\|_{2}^{2}-(\tau_{p}+\tau_{q})=$
$\displaystyle\frac{\bm{x}^{\top}\bm{x}+\bm{x}_{i}^{\top}\bm{x}_{i}-2\bm{x}^{\top}\bm{x}_{i}-{\rm
Tr}(\bm{\Sigma}_{p})-{\rm Tr}(\bm{\Sigma}_{q})}{d}\,,$

By a similar proof of Eq. 10 in Lemma A.1, conditioned on $\bm{x}_{i},1\leq
i\leq n$, with probability at least $1-\exp(-t)$,

$\displaystyle\left|\frac{\bm{x}^{\top}\bm{x}_{i}}{d}\right|\lesssim
d^{-(\theta_{q}-c_{pq}/2)}(t+\log^{1+\epsilon}d)\,.$

Therefore, setting $t:=2\log d$, with probability at least $1-d^{-2}$, we have

$\displaystyle\left|\frac{\bm{x}^{\top}\bm{x}_{i}}{d}\right|\lesssim
d^{-(\theta_{q}-c_{pq}/2)}(2\log d+\log^{1+\epsilon}d)\,.$

By Lemma A.4 and 3.2, and $\bm{x}\sim q$, we have with probability at least
$1-d^{-2}$,

$\displaystyle\left|\frac{\bm{x}^{\top}\bm{x}}{d}-\frac{{\rm
Tr}(\bm{\Sigma}_{q})}{d}\right|=\left|\frac{(\bm{\Sigma}_{q}^{-1/2}\bm{x})^{\top}\bm{\Sigma}_{q}(\bm{\Sigma}_{q}^{-1/2}\bm{x})}{d}-\frac{{\rm
Tr}(\bm{\Sigma}_{q})}{d}\right|\leq
d^{-\theta_{q}}\log^{\frac{1+\epsilon}{2}}d\,.$

By Lemma A.4 and 3.2, and $\bm{x}_{i}\sim p$, we have with probability at
least $1-d^{-2}$,

$\displaystyle\left|\frac{\bm{x}_{i}^{\top}\bm{x}_{i}}{d}-\frac{{\rm
Tr}(\bm{\Sigma}_{p})}{d}\right|=\left|\frac{(\bm{\Sigma}_{p}^{-1/2}\bm{x}_{i})^{\top}\bm{\Sigma}_{p}(\bm{\Sigma}_{p}^{-1/2}\bm{x}_{i})}{d}-\frac{{\rm
Tr}(\bm{\Sigma}_{p})}{d}\right|\leq
d^{-\theta_{p}}\log^{\frac{1+\epsilon}{2}}d\,.$

In total, with probability at least $1-3d^{-2}$, for sufficient large $d$, we
have

$\displaystyle K(\bm{x},\bm{x}_{i})-K^{\rm
lin}(\bm{x},\bm{x}_{i})\lesssim\left(\frac{1}{d}\|\bm{x}-\bm{x}_{j}\|_{2}^{2}-(\tau_{p}+\tau_{q})\right)^{2}\lesssim
d^{-2\min\\{\theta_{p},\theta_{q}-c_{pq}/2\\}}\log^{1+\epsilon}d\,,$

which leads to

$\displaystyle\mathbb{E}_{q}\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\|^{2}\lesssim
d^{-(4\min\\{\theta_{p},\theta_{q}-c_{pq}/2\\}-1)}\log^{2(1+\epsilon)}d\leq
d^{-(4\min\\{\theta_{p},\theta_{q}-c_{pq}/2\\}-1)}\log^{4(1+\epsilon)}d\,.$

By the definition of $\theta_{p}$ in Definition 1, we have
$\theta_{p}>\frac{1}{4}$. Therefore, as long as Assumption 3.3 is satisfied,
we have $\theta_{q}-c_{pq}/2>\frac{1}{4}$, and the residual term above will
converge to 0 as $d\to\infty$. ∎

###  A.3 Variance

####  A.3.1 Proof for variance

######  Lemma A.4 (Liang & Rakhlin (2020, Proposition A.1)).

Let $\\{\bm{x}_{i}\\}_{i=1}^{n}$ be i.i.d. random vectors in $\mathbb{R}^{d}$,
whose entries are i.i.d., mean $0$, variance $1$ and $|x_{i}(k)|\leq C\cdot
d^{\frac{2}{8+m}}$. For any positive semi-definite matrices $\bm{\Sigma}$
whose operator norms are uniformly bounded in $d$, and $n/d$ is asymptotically
bounded, with $\theta=\frac{1}{2}-\frac{2}{8+m}$, we have with probability at
least $1-d^{-2}$, for $\epsilon>0$,

$\displaystyle\max_{i,j}\left|\frac{\bm{x}_{i}^{\top}\bm{\Sigma}\bm{x}_{j}}{d}-\delta_{ij}\frac{{\rm
Tr}(\bm{\Sigma})}{d}\right|\leq d^{-\theta}\log^{\frac{1+\epsilon}{2}}d\,,$

for $d$ large enough.

###### Proof of Theorem 4.4 (Inner product kernels).

According to the definition of ${\sf V}$ and
$\mathbb{E}[\bm{y}|\bm{X}]=f_{\rho}(\bm{X})$, we have

$\displaystyle{\sf V}$ $\displaystyle=\int\mathbb{E}_{\bm{y}|\bm{X}}{\rm
Tr}\left(K(\bm{x},\bm{X})(\bm{K}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}(\bm{y}-f_{\rho}(\bm{X}))(\bm{y}-f_{\rho}(\bm{X}))^{\top}\right.$
$\displaystyle\ \left.(\bm{K}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}K(\bm{X},\bm{x})\right){\mathrm{d}}q(\bm{x})$
$\displaystyle\leq\int\|(\bm{K}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}K(\bm{X},\bm{x})\|^{2}\|\mathbb{E}_{\bm{y}|\bm{X}}\left[(\bm{y}-f_{\rho}(\bm{X}))(\bm{y}-f_{\rho}(\bm{X}))^{\top}\right]\|{\mathrm{d}}q(\bm{x})\,.$

Note that
$\mathbb{E}_{\bm{y}|\bm{X}}\left[(y_{i}-f_{\rho}(\bm{x}_{i}))(y_{j}-f_{\rho}(\bm{x}_{j}))\right]=0$
for $i\neq j$, and
$\mathbb{E}_{\bm{y}|\bm{X}}\left[(y_{i}-f_{\rho}(\bm{x}_{i}))^{2}\right]\leq\sigma_{\varepsilon}^{2}$,
we have
$\|\mathbb{E}_{\bm{y}|\bm{X}}\left[(\bm{y}-f_{\rho}(\bm{X}))(\bm{y}-f_{\rho}(\bm{X}))^{\top}\right]\|\leq\sigma_{\varepsilon}^{2}$.
Accordingly, the variance under our IW estimator can be estimated by

$\displaystyle\bm{V}$
$\displaystyle\leq\sigma_{\varepsilon}^{2}\int\|(\bm{K}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}K(\bm{X},\bm{x})\|^{2}{\mathrm{d}}q(\bm{x})=\sigma_{\varepsilon}^{2}\mathbb{E}_{q}\|(\bm{K}(\bm{X},\bm{X})+\lambda
n\overline{\bm{W}}(\bm{X}))^{-1}K(\bm{X},\bm{x})\|^{2}\,.$

By Table 2 the following linearization of the inner product kernel holds:

$\displaystyle\bm{K}^{\rm lin}(\bm{X},\bm{X})$
$\displaystyle:=\gamma_{p}\bm{I}+\alpha_{p}\mathbbm{1}\mathbbm{1}^{\top}+\beta_{p}\frac{\bm{X}\bm{X}^{\top}}{d}\in\mathbb{R}^{n\times
n},$ $\displaystyle\bm{K}^{\rm lin}(\bm{X},\bm{x})$
$\displaystyle:=\beta_{p}\frac{\bm{X}\bm{x}}{d}\in\mathbb{R}^{n\times 1},$

By Assumption 3.2, according to (Liang & Rakhlin, 2020, Proposition A.2), the
kernel matrix admits the following asymmetric approximation with
$\theta_{p}:=\frac{1}{2}-\frac{2}{8+m_{p}}$,

$\displaystyle\left\|\bm{K}(\bm{X},\bm{X})-\bm{K}^{\rm
lin}(\bm{X},\bm{X})\right\|$ $\displaystyle\leq
d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)\,,\quad\text{w.p.}~{}1-\delta-d^{-2}\,.$
(11)

The approximation $\left\|\bm{K}(\bm{X},\bm{X})-\bm{K}^{\rm
lin}(\bm{X},\bm{X})\right\|$ is different from (Liang & Rakhlin, 2020, Lemma
B.2), since training dataset $\bm{X}$ is sampled from $p$ and the expectation
under $q$. We prove this approximation under distribution shift in Lemma A.1,
such that

$\displaystyle\mathbb{E}_{q}\left\|\bm{K}(\bm{x},\bm{X})-\bm{K}^{\rm
lin}(\bm{x},\bm{X})\right\|^{2}$ $\displaystyle\leq
d^{-(4\theta_{q}-1-2c_{pq})}\log^{4(1+\epsilon)}d\,,\quad\text{w.p.}~{}1-d^{-2}\,.$
(12)

By Eq. 11, as a direct consequence, one can see that for sufficiently large
$d$, such that
$d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)\leq\gamma/2$,
with probability $1-\delta-d^{-2}$, we have

$\displaystyle\left\|(\bm{K}+\lambda
n\overline{\bm{W}}^{-1})^{-1}\right\|\leq{\|\bm{K}\|^{-1}\leq\frac{1}{\|\bm{K}^{\rm
lin}\|-d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)}}\leq\frac{1}{\gamma_{p}-d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)}\leq\frac{2}{\gamma_{p}},$
(13) $\displaystyle\left\|(\bm{K}+\lambda
n\overline{\bm{W}}^{-1})^{-1}(\bm{K}^{\rm lin}+\lambda
n\overline{\bm{W}}^{-1})\right\|\leq{\left\|(\bm{K}+\lambda
n\overline{\bm{W}}^{-1})^{-1}(\bm{K}+\lambda
n\overline{\bm{W}}^{-1}+\bm{K}^{\rm lin}-\bm{K})\right\|}$ $\displaystyle\leq
1+\|(\bm{K}+\lambda
n\overline{\bm{W}}^{-1})^{-1}\|\cdot\|\bm{K}(\bm{X},\bm{X})-\bm{K}^{\rm
lin}(\bm{X},\bm{X})\|$ $\displaystyle\leq
1+\frac{d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)}{\gamma_{p}-d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)}\leq\frac{\gamma_{p}}{\gamma_{p}-d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)}\leq
2\,.$ (14)

Combining Eqs. 12, 13 and 14, the variance can be estimated by

$\begin{split}{\sf
V}&\leq\sigma_{\varepsilon}^{2}\mathbb{E}_{q}\|(\bm{K}(\bm{X},\bm{X})+\lambda
n\overline{\bm{W}}(\bm{X})^{-1})^{-1}\bm{K}(\bm{X},\bm{x})\|^{2}\\\ &\leq
2\sigma_{\varepsilon}^{2}\mathbb{E}_{q}\|(\bm{K}(\bm{X},\bm{X})+\lambda
n\overline{\bm{W}}(\bm{X})^{-1})^{-1}\bm{K}^{\rm lin}(\bm{X},\bm{x})\|^{2}\\\
&+2\sigma_{\varepsilon}^{2}\left\|(\bm{K}(\bm{X},\bm{X})+\lambda
n\overline{\bm{W}}(\bm{X})^{-1})^{-1}\right\|^{2}\cdot\mathbb{E}_{q}\|\bm{K}(\bm{X},\bm{x})-\bm{K}^{\rm
lin}(\bm{X},\bm{x})\|^{2}\\\ &\leq
2\sigma_{\varepsilon}^{2}\left\|(\bm{K}(\bm{X},\bm{X})+\lambda{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}(\bm{K}^{\rm
lin}(\bm{X},\bm{X})+\lambda n\overline{\bm{W}}(\bm{X})^{-1})\right\|^{2}\\\ &\
\mathbb{E}_{q}\|(\bm{K}^{\rm lin}(\bm{X},\bm{X})+\lambda
n\overline{\bm{W}}(\bm{X})^{-1})^{-1}\bm{K}^{\rm
lin}(\bm{X},\bm{x})\|^{2}+\frac{8\sigma_{\varepsilon}^{2}}{\gamma_{p}^{2}}d^{-(4\theta_{q}-1-2c_{pq})}\log^{4(1+\epsilon)}d\\\
&\leq 8\sigma_{\varepsilon}^{2}\mathbb{E}_{q}\|(\bm{K}^{\rm
lin}(\bm{X},\bm{X})+\lambda n\overline{\bm{W}}(\bm{X})^{-1})^{-1}\bm{K}^{\rm
lin}(\bm{X},\bm{x})\|^{2}+\frac{8\sigma_{\varepsilon}^{2}}{\gamma_{p}^{2}}d^{-(4\theta_{q}-1-2c_{pq})}\log^{4(1+\epsilon)}d\,.\end{split}$
(15)

Besides, the IW estimator under the linearized kernel matrix leads to

$\displaystyle\mathbb{E}_{q}\|(\bm{K}^{\rm lin}(\bm{X},\bm{X})+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1})^{-1}\bm{K}^{\rm
lin}(\bm{X},\bm{x})\|^{2}$ $\displaystyle=\mathbb{E}_{q}{\rm
Tr}\left(\left[\gamma_{p}\bm{I}+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1}+\alpha_{p}\mathbbm{1}\mathbbm{1}^{\top}+\beta_{p}\frac{\bm{X}\bm{X}^{\top}}{d}\right]^{-2}\beta_{p}\frac{\bm{X}\bm{x}}{d}\beta_{p}\frac{\bm{x}^{\top}\bm{X}^{\top}}{d}\right)$
$\displaystyle={\rm Tr}\left(\left[\gamma_{p}\bm{I}+\lambda
n{\overline{\bm{W}}({\bm{X}})}^{-1}+\alpha_{p}\mathbbm{1}\mathbbm{1}^{\top}+\beta_{p}\frac{\bm{X}\bm{X}^{\top}}{d}\right]^{-2}\beta_{p}^{2}\frac{\bm{X}\bm{\Sigma}_{q}\bm{X}^{\top}}{d^{2}}\right)$
$\displaystyle\leq\frac{\|\bm{\Sigma}_{q}\|}{d}{\rm
Tr}\left(\left[\frac{\gamma_{p}}{\beta_{p}}\bm{I}+\frac{\lambda
n}{\beta_{p}}{\overline{\bm{W}}({\bm{X}})}^{-1}+\frac{\bm{X}\bm{X}^{\top}}{d}\right]^{-2}\frac{\bm{X}\bm{X}^{\top}}{d}\right)$
$\displaystyle=\frac{\|\bm{\Sigma}_{q}\|}{d}\mathcal{N}\left(\frac{\bm{X}\bm{X}^{\top}}{d}+\frac{\lambda
n}{\beta_{p}}{\overline{\bm{W}}({\bm{X}})}^{-1};\frac{\gamma_{p}}{\beta_{p}}\right)\,,$

with the following constants, $\beta_{p}=h^{\prime}(0)=O(1)$,
$\gamma_{p}=O((\tau_{p})^{2})$.

Finally, combining previous results, with probability at least
$1-\delta-2d^{-2}$, for sufficiently large $d$, we have

$\displaystyle{\sf
V}\leq\frac{8\sigma_{\varepsilon}^{2}\|\Sigma_{q}\|}{d}\mathcal{N}\left(\frac{\bm{X}\bm{X}^{\top}}{d}+\frac{\lambda
n}{\beta_{p}}{\overline{\bm{W}}({\bm{X}})}^{-1};\frac{\gamma_{p}}{\beta_{p}}\right)+\frac{8\sigma_{\varepsilon}^{2}}{\gamma_{p}^{2}}d^{-(4\theta_{q}-1-2c_{pq})}\log^{4(1+\epsilon)}d\,.$

∎

###  A.4 Bias

In the next, we present the proof for the bias based on whether the used
regularization parameter is small. We firstly give the proof for Theorem 4.6
and then Theorem 4.5.

######  Lemma A.5.

Let $g(\bm{x})\in\mathbb{R}$ that satisfies $\forall g\in\mathcal{G}$,
$|g(\bm{x})|\leq\kappa$ for all $\bm{x}$. Then with probability at least
$1-2\delta$, we have for i.i.d. $\bm{x}_{i}\sim q$

$\displaystyle\sup_{g\in\mathcal{G}}\left|\mathbb{E}g(\bm{x})-\widehat{\mathbb{E}}_{n}g(\bm{x})\right|$
$\displaystyle\leq\mathbb{E}\sup_{g\in\mathcal{G}}\left|\mathbb{E}g(\bm{x})-\widehat{\mathbb{E}}_{n}g(\bm{x})\right|+\kappa\sqrt{\frac{\log
1/\delta}{2n}}$ $\displaystyle\leq
2\mathbb{E}\sup_{g\in\mathcal{G}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}g(\bm{x}_{i})+\kappa\sqrt{\frac{\log
1/\delta}{2n}}$ $\displaystyle\leq
2\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}g(\bm{x}_{i})+3\kappa\sqrt{\frac{\log
1/\delta}{2n}}\,,$

where $\mathbb{E}_{\epsilon}$ denotes the conditional expectation with respect
to i.i.d. Rademacher random variables $\epsilon_{1},\ldots,\epsilon_{n}$.

####  A.4.1 Proof of Theorem 4.5

###### Proof of Theorem 4.5.

For the bias, we use the spectral decomposition of the kernel. To be specific,
denote $f_{\rho}(\bm{x})=\sum_{i=1}\phi_{i}(\bm{x})f_{i}$ with $f_{i}$ being
the coefficients of $f$ under the basis $\phi_{i}(\bm{x})$, we can write it as
$f(\bm{x})=\bm{\phi}(\bm{x})^{\top}\bm{f}$ where
$\bm{f}=[f_{1},f_{2},\ldots,f_{p}]^{\top}$ can be a possibly infinite vector.
Accordingly, the bias term can be formulated as

$\displaystyle\bm{B}$
$\displaystyle=\int\left|\bm{\phi}^{\top}(\bm{x})\bm{\Lambda}^{1/2}\left[\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})+\lambda
n\overline{\bm{W}}^{-1}]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}-\bm{I}\right]\bm{\Lambda}^{-1/2}\bm{f}_{\rho}\right|^{2}{\mathrm{d}}q(\bm{x})$
$\displaystyle\leq\int\left\|\left[\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})+\lambda
n\overline{\bm{W}}^{-1}]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}-\bm{I}\right]\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right\|^{2}{\mathrm{d}}q(\bm{x})\cdot\|\bm{\Lambda}^{-1/2}\bm{f}_{\rho}\|^{2}$
$\displaystyle=\|f_{\rho}\|_{\mathcal{H}}^{2}\int\left\|\left[\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})+\lambda
n\overline{\bm{W}}^{-1}]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}-\bm{I}\right]\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right\|^{2}{\mathrm{d}}q(\bm{x})\,.$

We note the following fact

$\displaystyle\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})+\lambda
n\overline{\bm{W}}({\bm{X}})^{-1}]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}-\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}\right)$
$\displaystyle\cdot\left(I-\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}\right)$
$\displaystyle=$
$\displaystyle\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})+\lambda
n\overline{\bm{W}}({\bm{X}})^{-1}]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}-\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}\right)$
$\displaystyle-$
$\displaystyle\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})+\lambda
n\overline{\bm{W}}({\bm{X}})^{-1}]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}$
$\displaystyle+$
$\displaystyle\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}$
$\displaystyle=$ $\displaystyle\ \mathbf{0}\,,$

with $A^{-1}-B^{-1}=B^{-1}(B-A)A^{-1}$, the main part in the bias term can be
split into the following two terms

$\displaystyle\int\left\|\left[\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})+\lambda
n\overline{\bm{W}}({\bm{X}})^{-1}]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}-I\right]\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right\|^{2}{\mathrm{d}}q(\bm{x})$
$\displaystyle=$
$\displaystyle\underbrace{\int\left\|\left[\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}-I\right]\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right\|^{2}{\mathrm{d}}q(\bm{x})}_{\tt(A)}$
$\displaystyle+$
$\displaystyle\underbrace{\int\left\|\left[\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\left[I+\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})\overline{\bm{W}}({\bm{X}})/(\lambda
n)\right]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}\right]\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right\|^{2}{\mathrm{d}}q(\bm{x})}_{\tt(B)}\,.$

We assume the SVD decomposition of
$\bm{\Lambda}^{\frac{1}{2}}\bm{\phi}(\bm{X})=\widehat{\bm{U}}\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top},\widehat{\bm{U}}\in\mathbb{R}^{p\times
n},\widehat{\bm{\Sigma}}\in\mathbb{R}^{n\times
n},\widehat{\bm{V}}\in\mathbb{R}^{n\times n}$ and the
$\bm{K}(\bm{X},\bm{X})=\bm{\phi}^{\top}(\bm{X})\bm{\Lambda}\bm{\phi}(\bm{X})$
has full rank as mentioned in the main text.

Part (A) is essentially ridgeless regression under the distribution shift. We
modify the proof from Liang & Rakhlin (2020) by introducing the additional re-
weighting quantity $\overline{w}(\bm{x})$.

Denote the top $k$ columns of $\widehat{\bm{U}}$ to be $\widehat{\bm{U}}_{k}$,
and $P_{\widehat{\bm{U}}_{k}}^{\perp}$ to be projection to the eigenspace
orthogonal to $\widehat{\bm{U}}_{k}$. By observing that
$\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})(\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X}))^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}$
is a projection matrix, it is clear that for all $k\leq n$,

$\displaystyle{\tt(A)}$
$\displaystyle\leq\|f_{\rho}\|_{\mathcal{H}}^{2}\int\left\|P^{\perp}_{\widehat{\bm{U}}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right)\right\|^{2}{\mathrm{d}}q(\bm{x})\leq\|f_{\rho}\|_{\mathcal{H}}^{2}\int\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right)\right\|^{2}{\mathrm{d}}q(\bm{x})\,.$
(16)

Denote the function $g$ indexed by any rank-$k$ projection $\bm{U}_{k}$ as

$\displaystyle
g_{\bm{U}_{k}}(\bm{x}):=\left\|P_{\bm{U}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}={\rm
Tr}\left(w(\bm{x})\bm{\phi}^{\top}(\bm{x})\bm{\Lambda}^{1/2}\bm{U}_{k}\bm{U}_{k}^{\top}\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right)\,.$
(17)

Clearly, $\|\bm{U}_{k}\bm{U}_{k}^{\top}\|_{F}=\sqrt{k}$. Define the function
class

$\displaystyle\mathcal{G}_{k}:=\\{g_{\bm{U}_{k}}(\bm{x}):\bm{U}_{k}^{\top}\bm{U}_{k}=\bm{I}_{k}\\}\,.$

It is clear that $g_{\widehat{\bm{U}}_{k}}\in\mathcal{G}_{k}$. Observe that
$g_{\widehat{\bm{U}}_{k}}$ is a random function that depends on the data
$\bm{X}$, and we will bound the bias term using the empirical process theory.
Recall that $w(\bm{x})={\mathrm{d}}q(\bm{x})/{\mathrm{d}}p(\bm{x})$, it is
straightforward to verify that

$\displaystyle\mathbb{E}_{\bm{x}\sim
q}\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right)\right\|^{2}$
$\displaystyle=\int_{X}\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}{\mathrm{d}}p(\bm{x})\,,$
$\displaystyle\widehat{\mathbb{E}}_{n}\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\sqrt{w(\bm{x}_{i})}\right)\right\|^{2}$
$\displaystyle=\frac{1}{n}{\rm
Tr}\left(P^{\perp}_{\widehat{\bm{U}}_{k}}\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X}){\bm{W}}({\bm{X}})\bm{\phi}^{\top}(\bm{X})\bm{\Lambda}^{1/2}P^{\perp}_{\widehat{\bm{U}}_{k}}\right)$
$\displaystyle=\frac{1}{n}\sum_{j>k}\lambda_{j}(\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}}))\,.$

Using symmetrization in Lemma A.5 with $\kappa W_{\max}$, where $W_{\max}$ is
the uniform boundedness of re-weighting ratio given by Assumption 3.4, with
probability at least $1-2\delta$, we have

$\displaystyle\int_{X}\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\right)\right\|^{2}{\mathrm{d}}q(\bm{x})-\frac{1}{n}\sum_{j>k}\lambda_{j}(\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}}))$
$\displaystyle=$
$\displaystyle\mathbb{E}_{p}\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}-\widehat{\mathbb{E}}_{n}\left\|P^{\perp}_{\widehat{\bm{U}}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\sup_{\bm{U}_{k}:\bm{U}_{k}^{\top}\bm{U}_{k}=\bm{I}_{k}}\left(\mathbb{E}-\widehat{\mathbb{E}}_{n}\right)\left\|P^{\perp}_{\bm{U}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}_{\epsilon}\sup_{\bm{U}_{k}:\bm{U}_{k}^{\top}\bm{U}_{k}=\bm{I}_{k}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left(\left\|\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\sqrt{w(\bm{x}_{i})}\right\|^{2}-\left\|P_{\bm{U}_{k}}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\sqrt{w(\bm{x}_{i})}\right)\right\|^{2}\right)+3\kappa
W_{\max}\sqrt{\frac{\log 1/\delta}{2n}}\,,$

by the Pythagorean theorem. Since $\epsilon_{i}$’s are symmetric and zero-mean
and $\left\|\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\right\|^{2}$ does not
depend on $\bm{U}_{k}$, the last expression is equal to

$\displaystyle
2\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}_{k}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}g(\bm{x}_{i})+3\kappa
W_{\max}\sqrt{\frac{\log 1/\delta}{2n}}\,.$

We further bound the Rademacher complexity of the set $\mathcal{G}_{k}$

$\displaystyle\mathbb{E}_{\epsilon}\sup_{g\in\mathcal{G}_{k}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}g(\bm{x}_{i})=\mathbb{E}_{\epsilon}\sup_{\bm{U}_{k}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}g_{\bm{U}_{k}}(\bm{x}_{i})$
$\displaystyle=\mathbb{E}_{\epsilon}\frac{1}{n}\sup_{\bm{U}_{k}}\left\langle\bm{U}_{k}\bm{U}_{k}^{\top},\sum_{i=1}^{n}\epsilon_{i}w(\bm{x}_{i})\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\bm{\phi}^{\top}(\bm{x}_{i})\bm{\Lambda}^{1/2}\right\rangle$
$\displaystyle\leq\frac{\sqrt{k}}{n}\mathbb{E}_{\epsilon}\left\|\sum_{i=1}^{n}\epsilon_{i}w(\bm{x}_{i})\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\bm{\phi}^{\top}(\bm{x}_{i})\bm{\Lambda}^{1/2}\right\|_{F}\,,$

by the Cauchy-Schwarz inequality and the fact that
$\|\bm{U}_{k}\bm{U}_{k}^{\top}\|_{F}\leq\sqrt{k}$. The last expression is can
be further evaluated by the independence of $\epsilon_{i}$’s

$\displaystyle\frac{\sqrt{k}}{n}\left\\{\mathbb{E}_{\epsilon}\left\|\sum_{i=1}^{n}w(\bm{x}_{i})\epsilon_{i}\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\bm{\phi}^{\top}(\bm{x}_{i})\bm{\Lambda}^{1/2}\right\|_{F}^{2}\right\\}^{1/2}$
$\displaystyle=\frac{\sqrt{k}}{n}\left\\{\sum_{i=1}^{n}w(\bm{x}_{i})^{2}\left\|\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\bm{\phi}^{\top}(\bm{x}_{i})\bm{\Lambda}^{1/2}\right\|_{F}^{2}\right\\}^{1/2}$
$\displaystyle=\sqrt{\frac{k}{n}}\sqrt{\frac{\sum_{i=1}^{n}w(\bm{x}_{i})^{2}K(\bm{x}_{i},\bm{x}_{i})^{2}}{n}}\,.$

We have, with probability at least $1-2n\delta$,

$\displaystyle{\tt(A)}\leq\inf_{0\leq k\leq
n}\left\\{\frac{1}{n}\sum_{j>k}\lambda_{j}(\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}}))+2\sqrt{\frac{k}{n}}\sqrt{\frac{\sum_{i=1}^{n}w(\bm{x}_{i})^{2}K(\bm{x}_{i},\bm{x}_{i})^{2}}{n}}+3\kappa
W\sqrt{\frac{\log 1/\delta}{2n}}\right\\}.$

Part (B) involves the regularization parameter $\lambda$ and the general
weighting function $\overline{w}$. Recall the SVD decomposition of
$\bm{\Lambda}^{\frac{1}{2}}\bm{\phi}(\bm{X})=\widehat{\bm{U}}\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}$,
by direct computation, we have

$\displaystyle\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})[\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X})]^{-1}\left[I+\bm{\phi}^{\top}(\bm{X})\bm{\Lambda}\bm{\phi}(\bm{X})\overline{\bm{W}}({\bm{X}})/(\lambda
n)\right]^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}$ $\displaystyle=$
$\displaystyle\widehat{\bm{U}}[\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n)]^{-1}\widehat{\bm{U}}^{\top}\,.$

It is also straightforward to verify that

$\displaystyle\widehat{\mathbb{E}}_{n}\left\|\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X})(\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}\bm{\phi}(\bm{X}))^{-1}\left(I+\bm{\phi}^{\top}(\bm{X})\bm{\Lambda}\bm{\phi}(\bm{X})\overline{\bm{W}}({\bm{X}})/(\lambda
n)\right)^{-1}\bm{\phi}(\bm{X})^{\top}\bm{\Lambda}^{1/2}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}$
$\displaystyle=$
$\displaystyle\widehat{\mathbb{E}}_{n}\left\|\widehat{\bm{U}}(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-1}\widehat{\bm{U}}^{\top}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}$
$\displaystyle=$ $\displaystyle\frac{1}{n}{\rm
Tr}\left(\widehat{\bm{U}}(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-2}\widehat{\bm{U}}^{\top}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{X}){\bm{W}}({\bm{X}})\bm{\phi}^{\top}(\bm{X})\bm{\Lambda}^{1/2}\right)\right)$
$\displaystyle=$ $\displaystyle\frac{1}{n}{\rm
Tr}\left((\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-2}\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}\right)$
$\displaystyle=$ $\displaystyle\frac{1}{n}{\rm
Tr}\left((\widehat{\bm{V}}\widehat{\bm{\Sigma}})^{-1}(\bm{I}+\widehat{\bm{V}}\widehat{\bm{\Sigma}}\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})/(\lambda
n))^{-2}(\widehat{\bm{V}}\widehat{\bm{\Sigma}})\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}\right)\quad\text{[using
$(\bm{I}+AB)^{-1}=B^{-1}(\bm{I}+BA)^{-1}B$]}$ $\displaystyle=$
$\displaystyle\lambda^{2}{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}(\bm{X},\bm{X})\overline{\bm{W}}({\bm{X}})}{n}\right)^{-2}\frac{\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)\,.$

Therefore, by Lemma A.5 with $\kappa W$, with probability at least
$1-2\delta$, we have

$\displaystyle(\mathbb{E}_{p}-\widehat{\mathbb{E}}_{n})\left\|\widehat{\bm{U}}(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-1}\widehat{\bm{U}}^{\top}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\sup_{\bm{U}}\left(\mathbb{E}_{p}-\widehat{\mathbb{E}}_{n}\right)\left\|{\bm{U}}(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-1}{\bm{U}}^{\top}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x})\sqrt{w(\bm{x})}\right)\right\|^{2}$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}_{\epsilon}\sup_{\bm{U}}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left\|{\bm{U}}(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-1}{\bm{U}}^{\top}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\sqrt{w(\bm{x}_{i})}\right)\right\|^{2}+3\kappa
W_{\max}\sqrt{\frac{\log 1/\delta}{2n}}\,.$

Similarly, we obtain

$\displaystyle\mathbb{E}_{\epsilon}\sup_{U}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\left\|{\bm{U}}(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-1}{\bm{U}}^{\top}\left(\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\sqrt{w(\bm{x}_{i})}\right)\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\left\|(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-2}\right\|_{F}\cdot\frac{1}{n}\mathbb{E}_{\epsilon}\left\|\sum_{i=1}^{n}\epsilon_{i}w(\bm{x}_{i})\bm{\Lambda}^{1/2}\bm{\phi}(\bm{x}_{i})\bm{\phi}^{\top}(\bm{x}_{i})\bm{\Lambda}^{1/2}\right\|_{F},$
$\displaystyle\leq$
$\displaystyle\left\|(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-2}\right\|_{F}\cdot\sqrt{\frac{1}{n}}\sqrt{\frac{\sum_{i=1}^{n}w(\bm{x}_{i})^{2}K(\bm{x}_{i},\bm{x}_{i})^{2}}{n}}\,,$

where

$\displaystyle\left\|(\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-2}\right\|_{F}^{2}={\rm
Tr}\left((\bm{I}+\widehat{\bm{\Sigma}}\widehat{\bm{V}}^{\top}\overline{\bm{W}}({\bm{X}})\widehat{\bm{V}}\widehat{\bm{\Sigma}}/(\lambda
n))^{-4}\right)$ $\displaystyle=$ $\displaystyle{\rm
Tr}\left((\bm{I}+\bm{K}(\bm{X},\bm{X})\overline{\bm{W}}({\bm{X}})/(\lambda
n))^{-4}\right)=\lambda^{4}{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}(\bm{X},\bm{X})\overline{\bm{W}}({\bm{X}})}{n}\right)^{-4}\right)\leq
n\,.$

In total, we have

$\displaystyle{\tt(B)}\leq$ $\displaystyle\lambda^{2}\left\\{{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}(\bm{X},\bm{X})\overline{\bm{W}}({\bm{X}})}{n}\right)^{-2}\frac{\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)+\sqrt{\frac{\sum_{i=1}^{n}w(\bm{x}_{i})^{2}K(\bm{x}_{i},\bm{x}_{i})^{2}}{n}}\right\\}$
$\displaystyle+$ $\displaystyle 3\kappa W_{\max}\sqrt{\frac{\log
1/\delta}{2n}}\,.$

In (A), if we take $k=0$, then with probability $1-4\delta$,

$\displaystyle{\tt(A)+(B)}\leq$ $\displaystyle{\rm
Tr}\left(\frac{\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)+\lambda^{2}\left\\{{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}(\bm{X},\bm{X})\overline{\bm{W}}({\bm{X}})}{n}\right)^{-2}\frac{\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)\right.$
$\displaystyle+$
$\displaystyle\left.\sqrt{\frac{\sum_{i=1}^{n}w(\bm{x}_{i})^{2}K(\bm{x}_{i},\bm{x}_{i})^{2}}{n}}\right\\}+6\kappa
W_{\max}\sqrt{\frac{\log 1/\delta}{2n}}\,.$

In the next, we consider the discretization of $\bm{K}$ to $\bm{K}^{\rm lin}$,
according to (Liang & Rakhlin, 2020, Proposition A.2), the kernel matrix
admits the following asymmetric approximation with
$\theta_{p}:=\frac{1}{2}-\frac{2}{8+m_{p}}$

$\displaystyle\left\|\bm{K}(\bm{X},\bm{X})-\bm{K}^{\rm
lin}(\bm{X},\bm{X})\right\|$ $\displaystyle\leq
d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)\,,\quad\text{w.p.}~{}1-\delta-d^{-2}\,.$

Therefore, we have

$\displaystyle\left|{\rm
Tr}\left(\frac{\bm{K}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)-{\rm
Tr}\left(\frac{\bm{K}^{\rm
lin}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)\right|\leq
W_{\max}\cdot\left\|\bm{K}(\bm{X},\bm{X})-\bm{K}^{\rm
lin}(\bm{X},\bm{X})\right\|\,.$

Besides, we have the following estimates

$\displaystyle\left\|\left(\lambda\bm{I}+\frac{\bm{K}\overline{\bm{W}}}{n}\right)^{-1}\left(\lambda\bm{I}+\frac{\bm{K}^{\rm
lin}\overline{\bm{W}}}{n}\right)\right\|$
$\displaystyle=\left\|\left(\lambda\overline{\bm{W}}^{-1}+\frac{\bm{K}}{n}\right)^{-1}\left(\lambda\overline{\bm{W}}^{-1}+\frac{\bm{K}^{\rm
lin}}{n}\right)\right\|$ $\displaystyle\leq 1+\left\|\left(\lambda\cdot
n\overline{\bm{W}}^{-1}+{\bm{K}}\right)^{-1}\left({\bm{K}-\bm{K}^{\rm
lin}}\right)\right\|$ $\displaystyle\leq
1+\frac{\gamma_{p}}{\gamma_{p}-d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)}\leq
2\,.$

Then we further have

$\displaystyle\left(\lambda\bm{I}+\frac{\bm{K}\overline{\bm{W}}}{n}\right)^{-2}\frac{\bm{K}{\bm{W}}}{n}$
$\displaystyle=$ $\displaystyle\left(\lambda\bm{I}+\frac{\bm{K}^{\rm
lin}\overline{\bm{W}}}{n}\right)^{-2}\left(\lambda\bm{I}+\frac{\bm{K}^{\rm
lin}\overline{\bm{W}}}{n}\right)^{2}\left(\lambda\bm{I}+\frac{\bm{K}\overline{\bm{W}}}{n}\right)^{-2}\frac{\bm{K}^{\rm
lin}{\bm{W}}}{n}+\left(\lambda\bm{I}+\frac{\bm{K}\overline{\bm{W}}}{n}\right)^{-2}\frac{(\bm{K}-\bm{K}^{\rm
lin}){\bm{W}}}{n}\,.$

Accordingly, we have

$\displaystyle\lambda^{2}{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}\overline{\bm{W}}}{n}\right)^{-2}\frac{\bm{K}{\bm{W}}}{n}\right)$
$\displaystyle\leq\lambda^{2}\left\|\left(\lambda\bm{I}+\frac{\bm{K}\overline{\bm{W}}}{n}\right)^{-1}\left(\lambda\bm{I}+\frac{\bm{K}^{\rm
lin}\overline{\bm{W}}}{n}\right)\right\|^{2}{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}^{\rm
lin}\overline{\bm{W}}}{n}\right)^{-2}\frac{\bm{K}^{\rm
lin}{\bm{W}}}{n}\right)$ $\displaystyle+{\lambda^{2}}{n}{\rm Tr}(\left(\lambda
n\bm{I}+{\bm{K}\overline{\bm{W}}}\right)^{-2})\|{(\bm{K}-\bm{K}^{\rm
lin}){\bm{W}}}\|$ $\displaystyle\leq 4{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}^{\rm
lin}\overline{\bm{W}}}{n}\right)^{-2}\frac{\bm{K}^{\rm
lin}{\bm{W}}}{n}\right)+d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)n^{-1}.$

Therefore, we have, since $n\asymp d$,

$\displaystyle{\tt(A)+(B)}\leq$ $\displaystyle{\rm Tr}\left(\frac{\bm{K}^{\rm
lin}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)+4\lambda^{2}{\rm
Tr}\left(\left(\lambda\bm{I}+\frac{\bm{K}^{\rm
lin}(\bm{X},\bm{X})\overline{\bm{W}}({\bm{X}})}{n}\right)^{-2}\frac{\bm{K}^{\rm
lin}(\bm{X},\bm{X}){\bm{W}}({\bm{X}})}{n}\right)$ $\displaystyle+$
$\displaystyle\lambda^{2}\kappa W_{\max}+6\kappa
W_{\max}\sqrt{\frac{\log(1/\delta)}{2n}}+2d^{-\theta_{p}}(\delta^{-1/2}+\log^{\frac{1+\epsilon}{2}}d)\,.$

Finally, we conclude the proof. ∎

####  A.4.2 Proof of Theorem 4.6

###### Proof of Theorem 4.6.

By Gogolashvili et al. (2023, Lemma 16) and Assumption 3.5, since
$f_{\rho}\in\mathcal{H}$, under Assumption 3.5, we have the following
estimates for ${\sf B}_{\lambda}$, i.e.,

$\displaystyle{\sf
B}_{\lambda}\leq\lambda^{\overline{r}}\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{1/2}\|\overline{g}_{\rho}\|_{q},\forall\lambda\geq
0\,.$

The estimation of ${\sf B}_{\rm data}$ relies on (Gogolashvili et al., 2023,
Theorem 20), under Assumption 3.5 and 3.6, we have with probability at least
$1-\delta$,

$\displaystyle{\sf B}_{\rm data}\leq
16\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{1/2}(\|f_{\rho}\|_{\infty}+\|f_{\rho}\|_{\mathcal{H}})\cdot\left(\frac{W_{\overline{w}}(d)}{n\sqrt{\lambda}}+\sigma_{\overline{w}}^{2}(d)\sqrt{\frac{\mathcal{N}_{\overline{q}}^{1-t_{\overline{w}}}(\lambda)}{n\lambda^{t_{\overline{w}}}}}\right)\log\left(\frac{6}{\delta}\right)$
$\displaystyle\leq
16\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{1/2}(\|f_{\rho}\|_{\infty}+\|f_{\rho}\|_{\mathcal{H}})(W_{\overline{w}}d^{c_{\overline{w},1}}n^{-1}\lambda^{-1/2}+\sigma_{\overline{w}}^{2}E_{\overline{q}}^{1-t_{\overline{w}}}d^{2c_{\overline{w},2}}n^{-1/2}\lambda^{-(t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}})/2}))\log(6/\delta)\,,$

given

$\displaystyle n\lambda^{1+t_{\overline{w}}}\geq
64(W_{\overline{w}}(d)+\sigma_{\overline{w}}^{2}(d))(\mathcal{N}_{\overline{q}}(\lambda))^{1-t_{\overline{w}}}\log^{2}(6/\delta)\,.$
(18)

Therefore, for general $\lambda$, we have

$\displaystyle{\sf
B}\lesssim(\lambda^{\overline{r}}+\lambda^{-\frac{1}{2}})\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{\frac{1}{2}}.$

Recall that $\lambda=C_{\lambda}^{-c_{\lambda}}$ and $n\sim d$, we have with
probability at least $1-\delta$,

$\displaystyle{\sf B}_{\rm data}+{\sf
B}_{\lambda}\leq\lambda^{\overline{r}}\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{1/2}\|\overline{g}_{\rho}\|_{q}$
$\displaystyle+16\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{1/2}(\|f_{\rho}\|_{\infty}+\|f_{\rho}\|_{\mathcal{H}})(W_{\overline{w}}d^{c_{\overline{w},1}}n^{-1}\lambda^{-1/2}+\sigma_{\overline{w}}^{2}E_{\overline{q}}^{1-t_{\overline{w}}}d^{2c_{\overline{w},2}}n^{-1/2}\lambda^{-(t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}})/2}))\log(6/\delta)$
$\displaystyle\lesssim
n^{-\overline{r}c_{\lambda}}+n^{-(1-c_{\lambda}/2-c_{\overline{w},1})}+n^{-(1/2-2c_{\overline{w},2}-c_{\lambda}(t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}})/2)}\,.$

where the last inequality only considers the dependence on $n$. Due to the
following fact from Assumption 3.4, we have

$\displaystyle 1-c_{\lambda}/2-c_{\overline{w},1}\geq
1/2-c_{\overline{w},1}\geq
1/2-2c_{\overline{w},2}-c_{\lambda}(t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}})/2\,,$

we can conclude that the second term decays faster than the third term.

We choose $c_{\lambda}$ to balance the first and the third term, i.e.
$\overline{r}c_{\lambda}=\frac{1-4c_{\overline{w},2}-c_{\lambda}(t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}})}{2}$,
which leads to

$\displaystyle
c_{\lambda}=\frac{1-4c_{\overline{w},2}}{2\overline{r}+t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}}}\,.$

where $c_{\overline{w},2}<0$ from Assumption 3.4 to ensure $c_{\lambda}>0$.
Besides, we have

$\displaystyle
64(W_{\overline{w}}(d)+\sigma_{\overline{w}}^{2}(d))(\mathcal{N}_{\overline{q}}(\lambda))^{1-t_{\overline{w}}}\log^{2}(6/\delta)\leq
64(W_{\overline{w}}\cdot d^{c_{\overline{w},1}}+\sigma_{\overline{w}}^{2}\cdot
d^{2c_{\overline{w},2}})E_{\overline{q}}^{2(1-t_{\overline{w}})}\lambda^{-s_{\overline{q}}(1-t_{\overline{w}})}\log^{2}(6/\delta)$
$\displaystyle\leq$ $\displaystyle
64(W_{\overline{w}}+\sigma_{\overline{w}}^{2})d^{2c_{\overline{w},2}}C_{\lambda}^{-s_{\overline{q}}(1-t_{\overline{w}})}E_{\overline{q}}^{2(1-t_{\overline{w}})}\cdot
n^{c_{\lambda}s_{\overline{q}}(1-t_{\overline{w}})}\log^{2}(6/\delta)\,.$

Therefore, for Eq. 18, the constant $C_{\lambda}$ has to satisfy

$\displaystyle
64(W_{\overline{w}}+\sigma_{\overline{w}}^{2})d^{2c_{\overline{w},2}}C_{\lambda}^{-s_{\overline{q}}(1-t_{\overline{w}})}E_{\overline{q}}^{2(1-t_{\overline{w}})}\cdot
n^{c_{\lambda}s_{\overline{q}}(1-t_{\overline{w}})}\log^{2}(6/\delta)\leq
n\lambda^{1+t_{\overline{w}}}=C_{\lambda}^{1+t_{\overline{w}}}n^{1-(1+t_{\overline{w}]})c_{\lambda}}\,.$

We expand $c_{\lambda}$, and using the fact $n/d\to\zeta$, we have that for
sufficiently large $d$, $n/d\geq\zeta/2$,

$\displaystyle
64(W_{\overline{w}}+\sigma_{\overline{w}}^{2})E_{\overline{q}}^{2(1-t_{\overline{w}})}(2/\zeta)^{2c_{\overline{w},2}}\log^{2}(6/\delta)n^{c_{\lambda}(s_{\overline{q}}(1-t_{\overline{w}})+t_{\overline{w}}+1)+2c_{\overline{w},2}-1}\leq
C_{\lambda}^{1+t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}}}\,,$

Since $\frac{1}{2}\leq\overline{r}\leq 1$,

$\displaystyle
c_{\lambda}(s_{\overline{q}}(1-t_{\overline{w}})+t_{\overline{w}}+1)+2c_{\overline{w},2}-1=\frac{1-2\overline{r}+2c_{\overline{w},2}(2\overline{r}-2-(t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}}))}{2\overline{r}+t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}}}\leq
0\,.$

the following constraints would suffice for Eq. 18,

$\displaystyle
C_{\lambda}^{1+t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}}}\geq
64(W_{\overline{w}}+\sigma_{\overline{w}}^{2})E_{\overline{q}}^{2(1-t_{\overline{w}})}(2/\zeta)^{2c_{\overline{w},2}}\log^{2}(6/\delta)\,.$

Recall the definition of $c_{\mathcal{H}}$ in Assumption 3.5, with probability
at least $1-\delta$, we have

$\displaystyle{\sf B}\leq{\sf B}_{\rm data}+{\sf B}_{\lambda}\leq
n^{-\overline{r}c_{\lambda}+c_{\mathcal{H}}}\|L_{q}(L_{\overline{q}}+\lambda)^{-1}\|^{1/2}\left\\{162C_{\mathcal{H}}(W_{\overline{w}}+\sigma_{\overline{w}}E_{\overline{q}}^{1-t_{\overline{w}}})\log(6/\delta)C_{\lambda}^{-\frac{t_{\overline{w}}+(1-t_{\overline{w}})s_{\overline{q}}}{2}}+C_{\lambda}^{\overline{r}}\|\overline{g}_{\rho}\|_{q}\right\\}\,.$

∎

##  Appendix B Experiments

To quantitatively evaluate our derived error bounds for the bias and variance,
we generate a synthetic dataset under a known $f_{\rho}$, with different
decays of the kernel matrix.

(a) variance ($\alpha=0.5$) (b) variance ($\alpha=1$) (c) variance
($\alpha=1.5$)

(d) bias ($\alpha=0.5$) (e) bias ($\alpha=1$) (f) bias ($\alpha=1.5$)

Figure 1: We plot the empirical excess error, variance, bias and the scaled
theoretical upper bound scaled V and scaled B under different decays with
$\lambda\propto n^{-1/2}$.

##### Eigenvalue decays.

For a positive semi-definite matrix $\bm{A}\in\mathbb{R}^{n\times n}$ with
rank $r(\bm{A})$, we say $\bm{A}$ have one of the following polynomial decay
if and only if $\lambda_{i}(\bm{A})\propto ni^{-a}$ with $a>1$ for $i\leq
r(\bm{A})$.

##### Data generation.

We assume $y_{i}=\sin(\|\bm{x}\|^{2})+\epsilon$ with the target function
$f_{\rho}(\bm{x})=\sin(\|\bm{x}\|_{2}^{2})$ and Gaussian noise $\varepsilon$
of zero-mean and unit variance. The training samples $\bm{x}_{i}$ are
generated from $\bm{x}_{p,i}=\bm{\Sigma}_{p}^{1/2}\bm{z}_{i}$, and the test
samples are generated from $\bm{x}_{q,i}=\bm{\Sigma}_{q}^{1/2}\bm{z}_{i}$.
Therefore, let $\bm{X}_{p}$ and $\bm{X}_{q}$ be the training and test data
matrices respectively, and $\bm{Z}=[\bm{z}_{1},\cdots,\bm{z}_{n}]^{\top}$ we
have $\bm{X}_{p}\bm{X}_{p}^{\top}=\bm{Z}\bm{\Sigma}_{p}\bm{Z}^{\top}$ and
$\bm{X}_{q}\bm{X}_{q}^{\top}=\bm{Z}\bm{\Sigma}_{q}\bm{Z}^{\top}$. In our
experiments, we take 1) $\bm{\Sigma}_{p}$ as a diagonal matrix that has
diagonal entries with $a=0.5,1,1.5$ for polynomial decay, and
$\bm{\Sigma}_{p}$ as the perturbed $\bm{\Sigma}_{q}$, i.e.,
$(\bm{\Sigma}_{q})_{i,i}^{-1}=(\bm{\Sigma}_{p})_{i,i}^{-1}+\epsilon^{\prime},\epsilon^{\prime}\sim{\rm
Unif}[0,1]$; take 2) $\bm{Z}$ as a random orthogonal matrix with almost i.i.d.
entries such that $\bm{X}_{p}\bm{X}_{p}^{\top}$ and
$\bm{X}_{q}\bm{X}_{q}^{\top}$ have the same eigen-decays as the
$\bm{\Sigma}_{p}$ and $\bm{\Sigma}_{q}$. Specifically, we use the QR
decomposition on a random Gaussian matrix to obtain an orthogonal matrix (Yu
et al., 2016).

##### Experimental settings

We set the dimension $d=500$, and the number of test data points to be 2500.
We vary the number of training data points as (100, 200, 300, 400, 450, 480,
520, 550, 600, 700, 784, 900, 1000, 1200, 1500, 2000). We set the kernel
$K(\bm{x},\bm{x}^{\prime})=(1+\langle\bm{x},\bm{x}^{\prime}\rangle/d)^{p}$
with $p=5$, who admits $\beta=p$ independent of $\bm{\Sigma}_{p}$. We take the
re-weighting function as the truncated probability ratio of distribution $p$
and $q$, i.e., let $\overline{q}=q$ and truncate the ratios to 10. Finally, we
run on 10 random seeds and calculate the mean and average.

##### Choice of $\lambda$

For the target function $f_{\rho}$ that belongs to the RKHS, we have the
source condition $\overline{r}=1/2$. Besides, for the distribution $p$ of the
polynomial decay $\alpha$, we take the capacity constant $s_{\overline{q}}=1$.
By the boundedness of ratios, we have $t_{\overline{w}}=c_{\overline{w},2}=0$.
By Theorem 4.6, we have $c_{\lambda}=1/2$. Therefore, we set $\lambda\propto
n^{-1/2}$.

##### Observations

Fig. 1 (a) - (f) show the trends of the test risk, variance, and bias, which
match our upper bound. From the log-log plot of the bias, we observe that our
bound is upper bound but not identical to the true rate of the bias decay.
Besides, if $n$ is large, the upper bound of variance and bias will tend to
zero under the IW strategy, which demonstrates that the IW strategy is not
harmful to high dimensional kernel methods under covariate shift, at least.
All the variances show the unimodal property, and the derived upper bound (as
well as the peak) coincides with the empirical ones.