# On regularized Radon-Nikodym differentiation

Duc Hoan Nguyen<EMAIL_ADDRESS>
Werner Zellinger<EMAIL_ADDRESS>
Sergei Pereverzyev<EMAIL_ADDRESS>
Johann Radon Institute for Computational and Applied Mathematics
Austrian Academy of Sciences
Altenberger Straße 69, 4040 Linz, Austria

###### Abstract

We discuss the problem of estimating Radon-Nikodym derivatives. This problem
appears in various applications, such as covariate shift adaptation,
likelihood-ratio testing, mutual information estimation, and conditional
probability estimation. To address the above problem, we employ the general
regularization scheme in reproducing kernel Hilbert spaces. The convergence
rate of the corresponding regularized algorithm is established by taking into
account both the smoothness of the derivative and the capacity of the space in
which it is estimated. This is done in terms of general source conditions and
the regularized Christoffel functions. We also find that the reconstruction of
Radon-Nikodym derivatives at any particular point can be done with high order
of accuracy. Our theoretical results are illustrated by numerical simulations.

Keywords: Density ratio, Reproducing kernel Hilbert space, Radon-Nikodym
differentiation

##  1 Introduction

This paper is focused on the use of regularized kernel methods in the context
of estimating the ratio of two probability density functions, which can also
be called the Radon-Nikodym derivative of the corresponding probability
measures.

Recently the estimation of Radon-Nikodym derivatives has gained significant
attention due to its potential applications in such tasks as covariate shift
adaptation, outlier detection, divergence estimation, and conditional
probability estimation. Here we may refer to Sugiyama et al. (2012) and
references therein. In order to address the above problem, various kernel-
based approaches are available. In particular, several regularization schemes
in reproducing Kernel Hilbert space (RKHS) can be employed Nguyen et al.
(2010); Kanamori et al. (2012); Que and Belkin (2013); Schuster et al. (2020);
Gizewski et al. (2022).

As can be seen from the above studies, the convergence of algorithms for
Radon-Nikodym differentiation is influenced not only by the smoothness of the
approximated function but also by the capacity of the approximating space.
Though there are several studies that employed a particular regularization
technique, such as Tikhonov–Lavrentiev regularization, to the best of our
knowledge there is no study considering more general regularization schemes
and taking into account both the above-mentioned factors, i.e. smoothness and
capacity. For example, in Kanamori et al. (2012) and Que and Belkin (2013)
(see Type I setting there) only the capacity of the approximating space has
been incorporated into error estimations, and in Gizewski et al. (2022) and
Schuster et al. (2020) only the smoothness has been considered.

Besides, since in some applications the point values of the Radon-Nikodym
derivatives are of interest, it seems natural to study their approximation in
spaces, where pointwise evaluations are well-defined. However, in Kanamori et
al. (2012) and Que and Belkin (2013) the approximation has been analyzed in
the space of integrable functions, where pointwise evaluations are not well-
defined.

In the present paper, we aim to overcome the above limitations. More
precisely, we study general regularization schemes and analyze their accuracy
with respect to both the smoothness of the Radon-Nikodym derivative and the
capacity of the RKHS in which it is estimated. This is done in terms of
general source conditions and regularized Christoffel functions. We then
establish accuracy bounds of the corresponding regularized algorithm in the
norm of RKHS and pointwise. Finally, we present some numerical illustrations
supporting our theoretical results.

##  2 Assumptions and auxiliaries

In the problem of estimation of Radon-Nikodym derivatives, we consider two
probability measures $p$ and $q$ on a space $\mathbf{X}\subset\mathbbm R^{d}$.
The information about the measures is only provided in the form of samples
$X_{p}=\\{x_{1},x_{2},\ldots,x_{n}\\}$ and
$X_{q}=\\{x_{1}^{\prime},x_{2}^{\prime},\ldots,x_{m}^{\prime}\\}$ drawn
independently and identically (i.i.d) from $p$ and $q$ respectively. Moreover,
we assume that there is a function $\beta:\mathbf{X}\rightarrow[0,\infty)$,
which can be viewed as the Radon-Nikodym derivative $\frac{dq}{dp}$ of the
probability measure $q(x)$ with respect to the probability measure $p(x)$, and
for any measurable set $A\subset\mathbf{X}$ it holds

$\int_{A}dq(x)=\int_{A}\beta(x)dp(x).$

Our goal is to approximate the Radon-Nikodym derivative
$\beta(x)=\frac{dq}{dp}$ by some function $\hat{\beta}(x)$ based on the
observed samples. As it has been already explained in Introduction, we in fact
need a strategy that ensures a good pointwise approximation to the derivatives
$\beta(x)$. Then it seems to be logical to estimate $\beta(x)$ in the norm of
some RKHS, in which pointwise evaluations are well-defined.

Let $\mathcal{H}_{K}$ be a reproducing Kernel Hilbert space with a positive-
definite function $K:\mathbf{X}\times\mathbf{X}\rightarrow\mathbbm R$ as
reproducing kernel. We assume that $K$ is a continuous and bounded function,
such that for any $x\in\mathbf{X}$

$\left\lVert K(\cdot,x)\right\rVert_{\mathcal{H}_{K}}=\left\langle
K(\cdot,x),K(\cdot,x)\right\rangle_{\mathcal{H}_{K}}^{\frac{1}{2}}=[K(x,x)]^{\frac{1}{2}}\leq\kappa_{0}<\infty.$

Let $L_{2,\rho}$ be the space of square-integrable functions
$f:\mathbf{X}\rightarrow\mathbb{R}$ with respect to the probability measure
$\rho$. We define $J_{q}:\mathcal{H}_{K}\hookrightarrow L_{2,q}$ and
$J_{p}:\mathcal{H}_{K}\hookrightarrow L_{2,p}$ as the inclusion operators,
such that for instance, $J_{q}$ assigns to a function $g\in\mathcal{H}_{K}$
the same function seen as an element of $L_{2,q}$. In the sequel, we
distinguish two sample operators

$\displaystyle
S_{X_{q}}f=(f(x_{1}^{\prime}),f(x_{2}^{\prime}),\ldots,f(x_{m}^{\prime}))\in\mathbbm
R^{m},$ $\displaystyle
S_{X_{p}}f=(f(x_{1}),f(x_{2}),\ldots,f(x_{n}))\in\mathbbm R^{n},$

acting from $\mathcal{H}_{K}$ to $\mathbbm R^{m}$ and $\mathbbm R^{n}$, where
the norms in later spaces are generated by $m^{-1}$-times and $n^{-1}$-times
the standard Euclidean inner products, such that, for example, for
$u=(u_{1},u_{2},\ldots,u_{m}),w=(w_{1},w_{2},\ldots,w_{m})\in\mathbbm R^{m},$

$\left\langle u,w\right\rangle_{\mathbbm
R^{m}}=\frac{1}{m}\sum_{j=1}^{m}u_{j}w_{j},\hskip 14.22636pt\left\lVert
u\right\rVert_{\mathbbm R^{m}}=\left\langle u,u\right\rangle_{\mathbbm
R^{m}}^{\frac{1}{2}}=\left(\frac{1}{m}\sum_{j=1}^{m}u_{j}^{2}\right)^{\frac{1}{2}}.$

Then the adjoint operators $S_{X_{q}}^{*}:\mathbbm
R^{m}\rightarrow\mathcal{H}_{K}$ and $S_{X_{p}}^{*}:\mathbbm
R^{n}\rightarrow\mathcal{H}_{K}$ are given as

$\displaystyle
S_{X_{q}}^{*}u(\cdot)=\frac{1}{m}\sum_{j=1}^{m}K(\cdot,x_{j}^{\prime})u_{j},\hskip
14.22636ptu=(u_{1},u_{2},\ldots,u_{m})\in\mathbbm R^{m},$ $\displaystyle
S_{X_{p}}^{*}v(\cdot)=\frac{1}{n}\sum_{i=1}^{n}K(\cdot,x_{i})v_{i},\hskip
14.22636ptv=(v_{1},v_{2},\ldots,v_{n})\in\mathbbm R^{n}.$

In the literature, various RKHS-based approaches are available for a Radon-
Nikodym derivative estimation. Here we may refer to Kanamori et al. (2012) and
to references therein. As it can be seen from Que and Belkin (2013), and also
from Gizewski et al. (2022), conceptually, under the assumption that
$\beta\in{\mathcal{H}_{K}}$, several of the above approaches can be derived
from a regularization of an operator equation, which can be written in our
terms as

$\displaystyle J_{p}^{*}J_{p}\beta=J_{q}^{*}J_{q}\mathbf{1}.$ (1)

Because of the compactness of the operator $J_{p}^{*}J_{p}$, its inverse
$(J_{p}^{*}J_{p})^{-1}$ cannot be a bounded operator in ${\mathcal{H}_{K}}$,
which makes the equation (1) ill-posed. Here, $\mathbf{1}$ is the constant
function that takes the value $1$ everywhere, and almost without loss of
generality, we assume that $\mathbf{1}\in{\mathcal{H}_{K}}$, because otherwise
the kernel $K_{1}(x,x^{\prime})=1+K(x,x^{\prime})$ will, for example, be used
to generate a suitable RKHS containing all constant functions.

Since there is no direct access to the measures $p$ and $q$, the equation (1)
is inaccessible as well, but the samples $X_{p}$ and $X_{q}$ allow us to
access its empirical version

$\displaystyle S_{X_{p}}^{*}S_{X_{p}}\beta=S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}.$
(2)

A regularization of equation (2) may serve as a starting point for several
approaches of estimating the Radon - Nikodym derivative $\beta$. For example,
as it has been observed in Kanamori et al. (2012); Gizewski et al. (2022), the
known kernel mean matching (KMM) method Huang et al. (2006) can be viewed as
the regularization of (1) by the method of quasi (least-squares) solutions,
originally proposed by Valentin Ivanov (1963) and also known as Ivanov
regularization (see, for example, Oneto et al. (2016) and Page and Grünewälder
(2019) for its use in the context of learning). At the same time, from Theorem
1 of Kanamori et al. (2012) it follows that the kernelized unconstrained
least-squares importance fitting (KuLSIF) proposed in Kanamori et al. (2012)
is in fact the application of the Lavrentiev regularization scheme to the
empirical version (2) of the equation (1), that is in KuLSIF we have

$\displaystyle\hat{\beta}=\beta_{\mathbf{X}}^{\lambda}=(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{-1}S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}.$ (3)

As we have already mentioned in Introduction, early bounds of the accuracy of
Radon-Nikodym numerical differentiation have relied only on the capacity of
the approximating space. For example, in Nguyen et al. (2010); Kanamori et al.
(2012) the capacity of the underlying space ${\mathcal{H}_{K}}$ has been
measured in terms of the so-called bracketing entropy, and in Kanamori et al.
(2012) the value of the regularization parameter $\lambda$ in KuLSIF (2) has
been chosen depending on that capacity measure. Note that, in such approach,
there is no possibility of incorporating into the regularization the
information about other factors, such as the smoothness of the approximated
derivative $\beta$, which, as we know from Gizewski et al. (2022), also
influences the regularization accuracy. Therefore, in the present study, we
follow Pauwels et al. (2018) and employ the concept of the so-called
regularized Christoffel function that allows direct incorporation of the
regularization parameter $\lambda$ into the definition of a capacity measure.
Consider the function

$\displaystyle C_{\lambda}(x)=\left\langle K(\cdot,x),(\lambda
I+J_{p}^{*}J_{p})^{-1}K(\cdot,x)\right\rangle_{\mathcal{H}_{K}}=\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}K(\cdot,x)\right\rVert^{2}_{\mathcal{H}_{K}}$
(4)

Note that in Pauwels et al. (2018) the reciprocal of $C_{\lambda}(x)$, i.e.
$\frac{1}{C_{\lambda}(x)}$, was called the regularized Christoffel function,
but for the sake of simplicity, we will keep the same name also for (4). Note
also that in the context of supervised learning where usually only one
probability measure, say $p$, is involved, the expected value

$\mathcal{N}(\lambda)=\int_{\mathbf{X}}C_{\lambda}(x)dp(x)$

of $C_{\lambda}(x)$, called the effective dimension, has been proven to be
useful Caponnetto and De Vito (2007). This function is used as a capacity
measure of ${\mathcal{H}_{K}}$.

At the same time, if more than one measure appears in the supervised learning
context, as is for example the case in the analysis of Nyström subsampling
Rudi et al. (2015); Lu et al. (2019), then the $C$-norm of the regularized
Christoffel function

$\displaystyle\mathcal{N}_{\infty}(\lambda):=\sup_{x\in\mathbf{X}}C_{\lambda}(x)$
(5)

is used in parallel with the effective dimension $\mathcal{N}(\lambda)$. This
gives a hint that $\mathcal{N}_{\infty}(\lambda)$ could also be a suitable
capacity measure for analysing the accuracy of Radon-Nikodym numerical
differentiation.

We will need the following statement.

###### Lemma 1

Let $b_{0}>0$ be such that $|\beta(x)|\leq b_{0}$ for any $x\in\mathbf{X}$.
Then with probability at least $1-\delta$ we have

$\displaystyle\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{p}}^{*}S_{X_{p}}\beta-
S_{X_{q}}^{*}S_{X_{q}}\mathbf{1})\right\rVert_{\mathcal{H}_{K}}\leq\left(1+\sqrt{2\log\frac{2}{\delta}}\right)\sqrt{\mathcal{N}_{\infty}(\lambda)}\sqrt{\frac{b_{0}}{n}+\frac{1}{m}}.$

The proof of Lemma 1 is based on Lemma 4 of Huang et al. (2006), which we
formulate in our notations as follows

###### Lemma 2

(Huang et al. (2006)) Let $\phi$ be a map from $\mathbf{X}$ into
$\mathcal{H}_{K}$ such that
$\left\lVert\phi(x)\right\rVert_{\mathcal{H}_{K}}\leq R$ for all
$x\in\mathbf{X}$. Then with probability at least $1-\delta$ it holds

$\left\lVert\frac{1}{m}\sum_{j=1}^{m}\phi(x_{j}^{\prime})-\frac{1}{n}\sum_{i=1}^{n}\beta(x_{i})\phi(x_{i})\right\rVert_{\mathcal{H}_{K}}\leq\left(1+\sqrt{2\log\frac{2}{\delta}}\right)R\sqrt{\frac{b_{0}^{2}}{n}+\frac{1}{m}}.$

Now we can return to Lemma 1.

Proof  We define a map $\phi:\mathbf{X}\rightarrow\mathcal{H}_{K}$ as
$\phi(x)=(\lambda I+J_{p}^{*}J_{p})^{-\frac{1}{2}}K(\cdot,x)$,
$x\in\mathbf{X}$. It is clear that

$\left\lVert\phi(x)\right\rVert_{\mathcal{H}_{K}}=\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}K(\cdot,x)\right\rVert_{\mathcal{H}_{K}}=\sqrt{C_{\lambda}(x)}\leq\sqrt{\mathcal{N}_{\infty}(\lambda)}.$

Therefore, for the map $\phi$ the condition of the above Lemma 2 is satisfied
with $R=\mathcal{N}_{\infty}(\lambda)$. Then directly from that lemma, we have

$\displaystyle\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{p}}^{*}S_{X_{p}}\beta-
S_{X_{q}}^{*}S_{X_{q}}\mathbf{1})\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle=\left\lVert\frac{1}{n}\sum_{i=1}^{n}\beta(x_{i})\phi(x_{i})-\frac{1}{m}\sum_{j=1}^{m}\phi(x_{j}^{\prime})\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\leq\left(1+\sqrt{2\log\frac{2}{\delta}}\right)\left(\sqrt{\frac{b_{0}^{2}}{n}+\frac{1}{m}}\right)\sqrt{\mathcal{N}_{\infty}(\lambda)}.$

##  3 General regularization scheme and general source conditions

All of the available regularization methods have the potential to be employed
for the regularization of equation (2). In particular, we will use a general
regularization scheme to construct a family of approximate solutions
$\beta_{\mathbf{X}}^{\lambda}$ of (1) as follows

$\displaystyle\beta_{\mathbf{X}}^{\lambda}=g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})S_{X_{q}}^{*}S_{X_{q}}\mathbf{1},$
(6)

where $\\{g_{\lambda}\\}$ is a family of operator functions parametrized by a
regularization parameter $\lambda>0$.

###  3.1 General regularization scheme

Recall (see, for example, Definition 2.2 in Lu and Pereverzyev (2013)) that
regularization schemes can be indexed by parametrized functions
$g_{\lambda}:[0,c]\rightarrow\mathbbm R$, $\lambda>0.$ The only requirements
are that there are positive constants
$\gamma_{0},\gamma_{-\frac{1}{2}},\gamma_{-1}$ for which

$\displaystyle\begin{split}\sup_{0<t\leq
c}|1-tg_{\lambda}(t)|&\leq\gamma_{0},\\\ \sup_{0<t\leq
c}\sqrt{t}|g_{\lambda}(t)|&\leq\frac{\gamma_{-\frac{1}{2}}}{\sqrt{\lambda}},\\\
\sup_{0<t\leq c}|g_{\lambda}(t)|&<\frac{\gamma_{-1}}{\lambda}.\end{split}$ (7)

Here and in the sequel, we adopt the convention that $c$ denotes a generic
positive coefficient, which can vary from appearance to appearance and may
only depend on basic parameters such as $p$, $q$, $\kappa_{0}$, $b_{0}$, and
others introduced below.

The qualification of a regularization scheme indexed by $g_{\lambda}$ is the
maximal $s>0$ for which

$\displaystyle\sup_{0<t\leq
c}t^{s}|1-tg_{\lambda}(t)|\leq\gamma_{s}\lambda^{s},$ (8)

where $\gamma_{s}$ does not depend on $\lambda$. Following Definition 2.3 of
Lu and Pereverzyev (2013) we also say that the qualification $s$ covers a non-
decreasing function $\varphi:[0,c]\rightarrow\mathbbm R$, $\varphi(0)=0,$ if
the function $t\rightarrow\frac{t^{s}}{\varphi(t)}$ is non-decreasing for
$t\in(0,c].$ Note that the higher qualification is the more rapidly increasing
functions can be covered, and in this way, as it can be seen below, the more
smoothness of approximated solutions can be utilized in the regularization.

Observe that the Lavrentiev regularization used in KuLSIF (3) is indexed by
$g_{\lambda}(t)=(\lambda+t)^{-1}$ and has qualification $s=1$. The
qualification of this regularization scheme can be increased if one employs
the so-called iteration idea, according to which regularized algorithms need
to be repeated such that, for example, the approximate Radon-Nikodym
derivative $\beta_{\mathbf{X}}^{\lambda}=\beta_{\mathbf{X}}^{\lambda,l}$
obtained in the previous $l$-th step plays the role of an initial guess for
the next approximation
$\beta_{\mathbf{X}}^{\lambda}=\beta_{\mathbf{X}}^{\lambda,l+1}$. In this
regularization the approximation (6) can be obtain iteratively as follows

$\displaystyle\beta_{\mathbf{X}}^{\lambda,0}$ $\displaystyle=0,$
$\displaystyle\beta_{\mathbf{X}}^{\lambda,l}$ $\displaystyle=(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{-1}(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}+\lambda\beta_{\mathbf{X}}^{\lambda,l-1}),\hskip
8.5359ptl\in\mathbbm N.$

After $k$ such iterations we obtained the approximation
$\beta_{\mathbf{X}}^{\lambda}=\beta_{\mathbf{X}}^{\lambda,k}$ that can be
represented in the form (6) with

$g_{\lambda}(t)=g_{\lambda,k}(t)=\frac{1-\frac{\lambda^{k}}{(\lambda+t)^{k}}}{t}.$

The regularization indexed by $g_{\lambda,k}(t)$ has the qualification $k$
that can be taken as large as desired. Moreover, for
$g_{\lambda}(t)=g_{\lambda,k}(t)$ the requirements (7), (8) are satisfied with
$\gamma_{0}=1,\gamma_{-\frac{1}{2}}=k^{\frac{1}{2}},\gamma_{-1}=k,\gamma_{k}=1.$

For the sake of shortness, we introduce the residual function

$r_{\lambda}(t):=1-tg_{\lambda}(t),$

for which (7), (8) give the bounds $r_{\lambda}(t)\leq\gamma_{0}$ and
$|t^{s}r_{\lambda}(t)|\leq\gamma_{s}\lambda^{s}.$

###  3.2 General source conditions

As mentioned in the previous section, the equation (1) is inaccessible, but
the result Mathé and Hofmann (2008) of the regularization theory tells us that
there is always a continuous, strictly increasing function
$\varphi:[0,\|J_{p}^{*}J_{p}\|_{\mathcal{H}_{K}}]\rightarrow\mathbbm R$ that
obeys $\varphi(0)=0$ and allows the representation of the solution of (1) in
terms of the so-called source condition:

$\displaystyle\beta=\varphi(J_{p}^{*}J_{p})\nu_{q},\hskip
8.5359pt\nu_{q}\in{\mathcal{H}_{K}}.$ (9)

The function $\varphi$ above is usually called the index function. Moreover,
for every $\epsilon>0$ one can find such $\varphi$ that (9) holds true for
$\nu_{q}$ with

$\|\nu_{q}\|_{\mathcal{H}_{K}}\leq(1+\epsilon)\|\beta\|_{\mathcal{H}_{K}}.$

Note that since the operator $J_{p}^{*}J_{p}$ is not accessible, there is a
reason to restrict ourselves to consideration of such index functions
$\varphi$, which allow us to control perturbations in the operators involved
in the definition of source conditions. A class of such index functions has
been discussed in Mathé and Pereverzev (2003); Bauer et al. (2007), and here
we follow those studies. Namely, we consider the class
$\mathcal{F}=\mathcal{F}(0,c)$ of index functions
$\varphi:[0,c]\rightarrow\mathbbm R_{+}$ allowing splitting
$\varphi(t)=\vartheta(t)\psi(t)$ into monotone Lipschitz part
$\vartheta,\vartheta(t)=0,$ with the Lipschitz constant equal to 1, and an
operator monotone part $\psi,\psi(0)=0.$

Recall that a function $\psi$ is operator monotone on $[0,c]$ if for any pair
of self-adjoint operators $U,V$ with spectra in $[0,c]$ such that $U\leq V$
(i.e. $V-U$ is an non-negative operator) we have $\psi(U)\leq\psi(V)$.

Examples of operator monotone index functions are $\psi(t)=t^{\nu},$
$\psi(t)=\log^{-\nu}\left(\frac{1}{t}\right),$
$\psi(t)=\log^{-\nu}\left(\log\frac{1}{t}\right),0<\nu\leq 1,$ while an
example of a function $\varphi$ from the above defined class $\mathcal{F}$ is
$\varphi(t)=t^{r}\log^{-\nu}\left(\frac{1}{t}\right),r>1,0<\nu\leq 1,$ since
it can be splitted in a Lipschitz part $\vartheta(t)=t^{r}$ and an operator
monotone part $\psi(t)=\log^{-\nu}\left(\frac{1}{t}\right).$

We will need the result of Proposition 3.1 in Pereverzyev (2022), which we
formulate in our notations as follows

###### Lemma 3

(Pereverzyev (2022)) Let $\varphi:[0,c]\rightarrow\mathbbm R$, $\varphi(0)=0,$
be any non-decreasing index function. If the qualification $s$ of the
regularization indexed by a family $\\{g_{\lambda}\\}$ covers the function
$\varphi$, then for any $\lambda\in(0,c]$ it holds

$\sup_{t\in[0,c]}|r_{\lambda}(t)\varphi(t)|\leq\gamma_{0,s}\varphi(\lambda),$

where $\gamma_{0,s}=\max\\{\gamma_{0},\gamma_{s}\\}$, and
$\gamma_{0},\gamma_{s}$ are the coefficients appearing in (7) and in (8).

To estimate the regularized Christoffel functions we slightly generalize a
source condition for kernel sections $K(\cdot,x)$ that has been used in
various contexts in Lu et al. (2019) and De Vito et al. (2014).

###### Assumption 4

(Source condition for kernel) There is an operator concave index function
$\xi:[0,\left\lVert J^{*}_{p}J_{p}\right\rVert]\to[0,\infty)$ and $\xi^{2}$ is
covered by qualification $s=1$ such that, for all $x\in\mathbf{X}$,

$K(\cdot,x)=\xi(J^{*}_{p}J_{p})v_{x},\hskip 8.5359pt\left\lVert
v_{x}\right\rVert_{\mathcal{H}_{K}}\leq c,$

where $c$ does not depend on $x$.

We mention the following consequence of Assumption 4.

###### Lemma 5

Under Assumption 4,

$\mathcal{N}_{\infty}(\lambda)\leq c\frac{\xi^{2}(\lambda)}{\lambda}.$

Proof  This simply follows from

$\displaystyle\mathcal{N}_{\infty}(\lambda)$
$\displaystyle=\sup_{x\in\mathbf{X}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}K(\cdot,x)\right\rVert^{2}_{\mathcal{H}_{K}}$
$\displaystyle=\sup_{x\in\mathbf{X}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}\xi(J^{*}_{p}J_{p})v_{x}\right\rVert^{2}_{\mathcal{H}_{K}}$
$\displaystyle\leq\sup_{x\in\mathbf{X}}\left\lVert
v_{x}\right\rVert^{2}_{\mathcal{H}_{K}}\sup_{t\in\left[0,||J^{*}_{p}J_{p}||\right]}|(\lambda+t)^{-\frac{1}{2}}\xi(t)|^{2}$
$\displaystyle\leq c\sup_{t}|(\lambda+t)^{-1}\xi^{2}(t)|$ $\displaystyle\leq
c\lambda^{-1}\sup_{t}\bigg{|}\left(1-t(\lambda+t)^{-1}\right)\xi^{2}(t)\bigg{|}$
$\displaystyle\leq c\lambda^{-1}\sup_{t}|r_{\lambda}(t)\xi^{2}(t)|$
$\displaystyle\leq c\frac{\xi^{2}(\lambda)}{\lambda},$

where in the last inequality we have used Lemma 3, Assumption 4, and the fact
that the Lavrentiev regularization indexed by
$g_{\lambda}(t)=(\lambda+t)^{-1}$ has the qualification $s=1$.

###### Remark 6

In Pauwels et al. (2018), the asymptotic behavior of the regularized
Christoffel functions $C_{\lambda}(x)$ as $\lambda\to 0$ has been analyzed for
translation invariant kernels $K(x,t)=K(x-t)$. Our Lemma 5 can be viewed as an
extension of that analysis based on the general source conditions on the
kernel sections $K_{x}(\cdot)=K(\cdot,x)\in{\mathcal{H}_{K}}$.

##  4 Error estimates in RKHS

In this section, we discuss error estimates between $\beta$ and
$\beta_{\mathbf{X}}^{\lambda}$ for RKHS norm. To this end, we consider an
auxiliary regularized approximation $\bar{\beta}^{\lambda}$ defined as follows

$\displaystyle\bar{\beta}^{\lambda}=g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})S_{X_{p}}^{*}S_{X_{p}}\beta.$
(10)

Then we decompose the error bound into two parts:

$\displaystyle\left\lVert\beta-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}\leq\left\lVert\beta-\bar{\beta}^{\lambda}\right\rVert_{\mathcal{H}_{K}}+\left\lVert\bar{\beta}^{\lambda}-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}.$
(11)

We call the first term on the right-hand side of (11) the approximation error,
and the second term the noise propagation error.

Following Lu et al. (2020), we introduce the functions

$\displaystyle\mathcal{B}_{n,\lambda}$
$\displaystyle:=\frac{2\kappa_{0}}{\sqrt{n}}\left(\frac{\kappa_{0}}{\sqrt{n\lambda}}+\sqrt{\mathcal{N}(\lambda)}\right),$
(12) $\displaystyle\Upsilon(\lambda)$
$\displaystyle:=\left(\frac{\mathcal{B}_{n,\lambda}}{\sqrt{\lambda}}\right)^{2}+1,$
(13)

which will be useful in the subsequent analysis.

Moreover, we need the following estimates from Lu et al. (2020) that are valid
with probability at least $1-\delta$ and can be written in our notations as

$\displaystyle\left\lVert
J^{*}_{p}J_{p}-S_{X_{p}}^{*}S_{X_{p}}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\leq\frac{4\kappa_{0}^{2}}{\sqrt{n}}\log\frac{2}{\delta},$ (14)
$\displaystyle\left\lVert(\lambda
I+J^{*}_{p}J_{p})^{-1/2}(J^{*}_{p}J_{p}-S_{X_{p}}^{*}S_{X_{p}})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\leq\mathcal{B}_{n,\lambda}\log\frac{2}{\delta},$ (15)
$\displaystyle\Xi:=\left\lVert(\lambda I+J_{p}^{*}J_{p})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{-1}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\leq
2\left[\left(\frac{\mathcal{B}_{n,\lambda}\log\frac{2}{\delta}}{\sqrt{\lambda}}\right)^{2}+1\right].$
(16)

###### Proposition 7

(Approximation error bound).

  1. 1.

If $\beta$ meets source condition (9), where $\varphi$ is an operator monotone
index function, then

$\left\lVert\beta-\bar{\beta}^{\lambda}\right\rVert_{\mathcal{H}_{K}}\leq
c(\gamma_{0}+\gamma_{-1})\Xi\varphi(\lambda),\hskip
8.5359pt0<\lambda\leq\kappa_{0}.$

  2. 2.

If $\beta$ meets source condition (9), where
$\varphi=\vartheta\psi\in\mathcal{F}(0,c)$ with $c$ is large enough and if the
qualification of the regularization $g_{\lambda}$ covers
$\vartheta(t)t^{\frac{3}{2}}$, then

$\left\lVert\beta-\bar{\beta}^{\lambda}\right\rVert_{\mathcal{H}_{K}}\leq
c\Xi\varphi(\lambda)+\psi(\kappa_{0})\gamma_{0}\left\lVert
J_{p}^{*}J_{p}-S_{X_{p}}^{*}S_{X_{p}}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}.$

Proof  The Proposition 7 can be proved by repeating line by line the argument
of the proof of Proposition 4.3 in Lu et al. (2020), where the items denoted
there as $T$, $T_{x}$, $f^{\dagger}$ and $\bar{f}_{x}^{\lambda}$ should be
substituted by $J_{p}^{*}J_{p}$, $S_{X_{p}}^{*}S_{X_{p}}$, $\beta$, and
$\bar{\beta}^{\lambda}$, respectively.

###### Proposition 8

(Noise propagation error bound). Let
$\beta_{\mathbf{X}}^{\lambda},\bar{\beta}^{\lambda}$ be defined by (3), (10).
Then with probability at least $1-\delta$ it holds

$\left\lVert\bar{\beta}^{\lambda}-\beta_{\mathbf{X}}^{\lambda}\right\rVert_{\mathcal{H}_{K}}\leq
c\left(\gamma_{-\frac{1}{2}}^{2}+\gamma_{-1}^{2}\right)^{\frac{1}{2}}\Xi^{\frac{1}{2}}\frac{1}{\sqrt{\lambda}}\left(m^{-\frac{1}{2}}+n^{-\frac{1}{2}}\right)\sqrt{\mathcal{N}_{\infty}(\lambda)}\left(\log^{\frac{1}{2}}\frac{1}{\delta}\right).$

Proof  From (16) and well-known Cordes inequality we have

$\displaystyle\left\lVert(\lambda I+J_{p}^{*}J_{p})^{1/2}(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{-1/2}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\leq\Xi^{1/2}.$ (17)

Then using (7) and Lemma 1, we can continue

$\displaystyle\left\lVert\bar{\beta}^{\lambda}-\beta_{\mathbf{X}}^{\lambda}\right\rVert_{\mathcal{H}_{K}}\leq$
$\displaystyle\left\lVert
g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\leq$ $\displaystyle\left\lVert
g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{1}{2}}\right\lVert_{\mathcal{H}_{K}}\left\lVert(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{-\frac{1}{2}}(\lambda
I+J^{*}_{p}J_{p})^{\frac{1}{2}}\right\lVert_{\mathcal{H}_{K}}\times$
$\displaystyle\times\left\lVert(\lambda
I+J^{*}_{p}J_{p})^{-\frac{1}{2}}(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\lVert_{\mathcal{H}_{K}}$
$\displaystyle\leq$ $\displaystyle\sup_{0<t\leq
c}|g_{\lambda}(t)(\lambda+t)^{\frac{1}{2}}|\Xi^{\frac{1}{2}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{p}}^{*}S_{X_{p}}\beta-
S_{X_{T}}^{*}S_{X_{T}}\mathbf{1})\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\leq$
$\displaystyle(\gamma_{-\frac{1}{2}}^{2}+\gamma_{-1}^{2})^{\frac{1}{2}}\frac{1}{\sqrt{\lambda}}\Xi^{\frac{1}{2}}\left(1+\sqrt{2\log\frac{2}{\delta}}\right)\left(\sqrt{\frac{b_{0}^{2}}{n}+\frac{1}{m}}\right)\sqrt{\mathcal{N}_{\infty}(\lambda)}$
$\displaystyle\leq$ $\displaystyle
c\left(\gamma_{-\frac{1}{2}}^{2}+\gamma_{-1}^{2}\right)^{\frac{1}{2}}\frac{1}{\sqrt{\lambda}}\Xi^{\frac{1}{2}}\left(m^{-\frac{1}{2}}+n^{-\frac{1}{2}}\right)\sqrt{\mathcal{N}_{\infty}(\lambda)}\left(\log^{\frac{1}{2}}\frac{1}{\delta}\right).$

The next proposition summaries of Proposition 7 and 8.

###### Proposition 9

If $\beta$ meets source condition (9), where $\varphi$ is an operator monotone
index function, then with probability at least $1-\delta$ it holds

$\displaystyle\left\lVert\beta-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}\leq
c\left(\Upsilon(\lambda)\varphi(\lambda)+\frac{1}{\sqrt{\lambda}}[\Upsilon(\lambda)]^{\frac{1}{2}}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\sqrt{\mathcal{N}_{\infty}(\lambda)}\right)\left(\log\frac{2}{\delta}\right)^{2}.$

If $\beta$ meets source condition (9), where
$\varphi=\vartheta\psi\in\mathcal{F}(0,c)$ with $c$ is large enough, and if
the qualification of the regularization $g_{\lambda}$ covers
$\vartheta(t)t^{\frac{3}{2}}$ then with probability at least $1-\delta$ the
total error allows for the bound

$\displaystyle\left\lVert\beta-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}\leq
c\left(\Upsilon(\lambda)\varphi(\lambda)+n^{-\frac{1}{2}}+\frac{1}{\sqrt{\lambda}}[\Upsilon(\lambda)]^{\frac{1}{2}}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\sqrt{\mathcal{N}_{\infty}(\lambda)}\right)\left(\log\frac{2}{\delta}\right)^{2}.$

Proof  We first prove the results for $\beta$ meets source condition (9),
where $\varphi$ is an operator monotone index function. Using the error
estimates in Proposition 7 and 8, and (12) - (16), we have

$\displaystyle\left\lVert\beta-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}\leq$
$\displaystyle
c(\gamma_{0}+\gamma_{-1})\left[\left(\frac{\mathcal{B}_{n,\lambda}\log\frac{2}{\delta}}{\sqrt{\lambda}}\right)^{2}+1\right]\varphi(\lambda)$
$\displaystyle+\left(\gamma_{-\frac{1}{2}}^{2}+\gamma_{-1}^{2}\right)^{1/2}\frac{1}{\sqrt{\lambda}}\sqrt{\left(\frac{\mathcal{B}_{n,\lambda}\log\frac{2}{\delta}}{\sqrt{\lambda}}\right)^{2}+1}\left(\log^{\frac{1}{2}}\frac{1}{\delta}\right)\left(m^{-\frac{1}{2}}+n^{-\frac{1}{2}}\right)\sqrt{\mathcal{N}_{\infty}(\lambda)}$
$\displaystyle\leq$ $\displaystyle
c\left(\Upsilon(\lambda)\varphi(\lambda)+\frac{1}{\sqrt{\lambda}}[\Upsilon(\lambda)]^{\frac{1}{2}}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\sqrt{\mathcal{N}_{\infty}(\lambda)}\right)\left(\log\frac{2}{\delta}\right)^{2}.$

Similarly, if $\beta$ meets source condition (9), with
$\varphi=\vartheta\psi\in\mathcal{F}(0,c)$ and the qualification of the
regularization $g_{\lambda}$ covers $\vartheta(t)t^{\frac{3}{2}}$, we have

$\displaystyle\left\lVert\beta-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}\leq$
$\displaystyle
c\left[\left(\frac{\mathcal{B}_{n,\lambda}\log\frac{2}{\delta}}{\sqrt{\lambda}}\right)^{2}+1\right]\varphi(\lambda)+\psi(\kappa_{0})\gamma_{0}\frac{4\kappa_{0}^{2}}{\sqrt{n}}\log\frac{2}{\delta}$
$\displaystyle+c\frac{1}{\sqrt{\lambda}}\sqrt{\left(\frac{\mathcal{B}_{n,\lambda}\log\frac{2}{\delta}}{\sqrt{\lambda}}\right)^{2}+1}\left(\log^{\frac{1}{2}}\frac{1}{\delta}\right)\left(m^{-\frac{1}{2}}+n^{-\frac{1}{2}}\right)\sqrt{\mathcal{N}_{\infty}(\lambda)}$
$\displaystyle\leq$ $\displaystyle
c\left(\Upsilon(\lambda)\varphi(\lambda)+n^{-\frac{1}{2}}+\frac{1}{\sqrt{\lambda}}[\Upsilon(\lambda)]^{\frac{1}{2}}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\sqrt{\mathcal{N}_{\infty}(\lambda)}\right)\left(\log\frac{2}{\delta}\right)^{2}.$

We will also need the following statement proven in Lu et al. (2020) as Lemma
4.6.

###### Lemma 10

Lu et al. (2020) There exists a $\lambda_{*}$ satisfying
$\mathcal{N}(\lambda_{*})/\lambda_{*}=n$. For
$\lambda_{*}\leq\lambda\leq\kappa_{0}$, there holds

$\displaystyle\mathcal{B}_{n,\lambda}\leq\frac{2\kappa_{0}}{\sqrt{n}}\left(\sqrt{2}\kappa_{0}+\sqrt{\mathcal{N}(\lambda)}\right).$
(18)

This yields

$\displaystyle\Upsilon(\lambda)\leq 1+(4\kappa_{0}^{2}+2\kappa_{0})^{2}$ (19)

and also

$\displaystyle\mathcal{B}_{n,\lambda}\left(\mathcal{B}_{n,\lambda}+\sqrt{\lambda}\right)\leq(1+4\kappa_{0})^{4}\min\left\\{\lambda,\sqrt{\frac{\kappa_{0}}{n}}\right\\},$
(20)

for $n$ large enough.

For $\lambda>\lambda_{*}$ we can make the statement of Proposition 9 more
transparent.

###### Theorem 11

Let $K$ satisfies Assumption 4, and $\lambda\geq\lambda^{*}$. Then under the
assumptions of Proposition 9, with probability at least $1-\delta$, it holds

$\displaystyle\left\lVert\beta-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}\leq
c\left(\varphi(\lambda)+(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\frac{\xi(\lambda)}{\lambda}\right)\left(\log\frac{2}{\delta}\right)^{2}.$

Consider $\theta_{\varphi,\xi}(t)=\frac{\varphi(t)t}{\xi(t)}$ and
$\lambda=\lambda_{m,n}=\theta_{\varphi,\xi}^{-1}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})$,
then

$\left\lVert\beta-\beta^{\lambda}_{\mathbf{X}}\right\rVert_{\mathcal{H}_{K}}\leq
c\varphi\left(\theta_{\varphi,\xi}^{-1}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\right)\log^{2}\frac{1}{\delta}.$

###### Remark 12

As we already mentioned, the accuracy of the approximation (6) in RKHS has
also been estimated in Theorem 2 of Gizewski et al. (2022). In our terms, the
result of Gizewski et al. (2022) can be written as follows:

$\displaystyle\left\lVert\beta-\beta_{\mathbf{X}}^{\lambda}\right\rVert_{\mathcal{H}_{K}}\leq
c\varphi\left(\theta_{\varphi}^{-1}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\right)\log\frac{1}{\delta}.$
(21)

where $\theta_{\varphi}(t)=\varphi(t)t$. To simplify the comparison of Theorem
11 and (21), let us consider the case when $\beta$ meets the source condition
(9) with $\varphi(t)=t^{\eta}$. In this case the bound (21) can be reduced to

$\displaystyle\left\lVert\beta-\beta_{\mathbf{X}}^{\lambda}\right\rVert_{\mathcal{H}_{K}}=O\left((m^{-\frac{1}{2}}+n^{-\frac{1}{2}})^{\frac{\eta}{\eta+1}}\right).$
(22)

It is noteworthy that the error bound established in Theorem 2 of Gizewski et
al. (2022) does not take into consideration the capacity of
${\mathcal{H}_{K}}$. Such an additional factor can be accounted in terms of
Assumption 4 . Assume that $K$ satisfies Assumption 3.2 with
$\xi(t)=t^{\varsigma},0<\varsigma\leq\frac{1}{2}$, then for
$\lambda=\lambda_{m,n}=\theta_{\varphi,\xi}^{-1}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})$,
the bound in Theorem 11 gives

$\left\lVert\beta-\beta_{\mathbf{X}}^{\lambda}\right\rVert_{\mathcal{H}_{K}}=O\left((m^{-\frac{1}{2}}+n^{-\frac{1}{2}})^{\frac{\eta}{\eta+1-\varsigma}}\right),$

that is better than the order of accuracy given by (22). Then one can conclude
that the bound in Theorem 11 obtained by our argument generalizes, specifies,
and refines the results of Gizewski et al. (2022).

Recall that the bounds in Theorem 11 are valid for $\lambda>\lambda_{*}$.
Using Lemma 5 and 10 one can prove that $\lambda=\lambda_{m,n}$ also satisfies
the above inequality. The corresponding proof can be easily recovered from
Figure 1.

Figure 1: Relation between $\lambda_{*}$ and $\lambda_{m,n}$.

##  5 Error bounds for the pointwise evaluation

In this section, we discuss the error between point values of $\beta(x)$ and
$\beta_{\mathbf{X}}^{\lambda}(x)$ for any $x\in\mathbf{X}$. In view of the
reproducing property of $K$ we have

$\displaystyle|\beta(x)-\beta^{\lambda}_{\mathbf{X}}(x)|=\big{|}\left\langle
K_{x},\beta-\beta^{\lambda}_{\mathbf{X}}\right\rangle_{\mathcal{H}_{K}}\big{|}$
$\displaystyle=\big{|}\left\langle
K(\cdot,x),\beta-\beta^{\lambda}_{\mathbf{X}}\right\rangle_{\mathcal{H}_{K}}\big{|}$
$\displaystyle=\big{|}\left\langle\xi(J^{*}_{p}J_{p})v_{x},\beta-\beta^{\lambda}_{\mathbf{X}}\right\rangle_{\mathcal{H}_{K}}\big{|}$
$\displaystyle\leq
c\left\lVert\xi(J^{*}_{p}J_{p})(\beta-\beta^{\lambda}_{\mathbf{X}})\right\rVert_{\mathcal{H}_{K}}.$
(23)

Similarly, we obtain

$\displaystyle|\beta(x)-\bar{\beta}^{\lambda}(x)|$ $\displaystyle\leq
c\left\lVert\xi(J^{*}_{p}J_{p})(\beta-\bar{\beta}^{\lambda})\right\rVert_{\mathcal{H}_{K}},$
$\displaystyle|\bar{\beta}^{\lambda}(x)-\beta^{\lambda}_{\mathbf{X}}(x)|$
$\displaystyle\leq
c\left\lVert\xi(J^{*}_{p}J_{p})(\bar{\beta}^{\lambda}-\beta^{\lambda}_{\mathbf{X}})\right\rVert_{\mathcal{H}_{K}},$

that allows for the following decomposition of the error bound

$\displaystyle|\beta(x)-\beta^{\lambda}_{\mathbf{X}}(x)|\leq
c\left(\left\lVert\xi(J^{*}_{p}J_{p})(\beta-\bar{\beta}^{\lambda})\right\rVert_{\mathcal{H}_{K}}+\left\lVert\xi(J^{*}_{p}J_{p})(\bar{\beta}^{\lambda}-\beta^{\lambda}_{\mathbf{X}})\right\rVert_{\mathcal{H}_{K}}\right).$
(24)

In the following propositions, we estimate the terms on the right-hand side of
(24).

###### Proposition 13

Let Assumption 4 be satisfied. Assume also that $\beta$ and the regularization
indexed by $g_{\lambda}$ meet the conditions of Proposition 7. Then

$\displaystyle\left\lVert\xi(J_{p}^{*}J_{p})(\beta-\bar{\beta}^{\lambda})\right\rVert_{\mathcal{H}_{K}}\leq
c\xi(\lambda)\left(\Xi^{\frac{3}{2}}\varphi(\lambda)+(\gamma_{0}+\gamma_{\frac{1}{2}})\Xi^{\frac{1}{2}}\psi(\kappa_{0})\left\lVert
J^{*}_{p}J_{p}-S_{X_{p}}^{*}S_{X_{p}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\right).$

for $\varphi\in\mathcal{F}(0,c)$, while for an operator monotone index
function $\varphi$ we have

$\displaystyle\left\lVert\xi(J^{*}_{p}J_{p})(\beta-\bar{\beta}^{\lambda})\right\rVert_{\mathcal{H}_{K}}\leq
c(\gamma_{0}+\gamma_{\frac{3}{2}})\Xi^{\frac{3}{2}}\xi(\lambda)\varphi(\lambda).$

Proof  The analysis below is based on a modification of arguments developed in
Lu et al. (2020) for estimating the $L_{2,p}$-norm of any function $f\in
L_{2,p}$ in terms of
$\left\lVert(J_{p}^{*}J_{p})^{\frac{1}{2}}f\right\rVert_{\mathcal{H}_{K}}$.
For the reader’s convenience, we present this modification in detail.

First of all, directly from Lemma A.1 Lu et al. (2020), it follows that, if
$g_{\lambda}$ is any regularization with qualification $1$, then

$\displaystyle\left\lVert r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{1}{2}}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\leq\sqrt{(\gamma_{0}^{2}+\gamma_{\frac{1}{2}}^{2})}\lambda^{\frac{1}{2}}.$
(25)

If $g_{\lambda}$ has qualification at least $3/2$ then

$\displaystyle\left\lVert r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{3}{2}}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\leq\sqrt{8(\gamma_{0}^{2}+\gamma_{\frac{3}{2}}^{2})}\lambda^{\frac{3}{2}}.$
(26)

If $\beta$ meets source condition (9), then for any $\lambda>0$

$\displaystyle\left\lVert\xi(J^{*}_{p}J_{p})(\beta-\bar{\beta}^{\lambda})\right\rVert_{\mathcal{H}_{K}}=\left\lVert\xi(J^{*}_{p}J_{p})(I-g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})S_{X_{p}}^{*}S_{X_{p}})\beta\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip
34.14322pt=\left\lVert\xi(J^{*}_{p}J_{p})(I-g_{\lambda}(x^{*}S_{X_{p}})S_{X_{p}}^{*}S_{X_{p}})\varphi(J^{*}_{p}J_{p})v\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 34.14322pt\leq\left\lVert\xi(J_{p}^{*}J_{p})(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\varphi(J_{p}^{*}J_{p})v\right\rVert_{{\mathcal{H}_{K}}}.$
(27)

Now we are going to estimate each component on the right-hand side of (5).
From the proof of Lemma 5, we have

$\displaystyle\left\lVert\xi(J_{p}^{*}J_{p})(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}.$ (28)

Observe also that

$\displaystyle\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\varphi(J_{p}^{*}J_{p})v\right\rVert_{{\mathcal{H}_{K}}}$
$\displaystyle\hskip 48.36958pt\leq\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+J_{p}^{*}J_{p})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-1}\varphi(J_{p}^{*}J_{p})v\right\rVert_{{\mathcal{H}_{K}}}.$

Moreover, using (16) and the bounds (17) and (26), we get

$\displaystyle\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+J_{p}^{*}J_{p})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\hskip 19.91684pt\leq\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{-\frac{1}{2}}(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+J_{p}^{*}J_{p})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\hskip 19.91684pt\leq\Xi^{\frac{1}{2}}\left\lVert(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})(\lambda I+S_{X_{p}}^{*}S_{X_{p}})^{-1}(\lambda
I+J_{p}^{*}J_{p})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\hskip 19.91684pt\leq\Xi^{\frac{1}{2}}\left\lVert(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\Xi$
$\displaystyle\hskip 19.91684pt=\left\lVert
r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{3}{2}}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\Xi^{\frac{3}{2}}$
$\displaystyle\hskip 19.91684pt\leq
c\Xi^{\frac{3}{2}}\lambda^{\frac{3}{2}}\left(\gamma_{0}+\gamma_{\frac{3}{2}}\right).$

Besides, using the same argument as in the proof of Lemma 5, for an operator
monotone index function $\varphi$ we have

$\displaystyle\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-1}\varphi(J_{p}^{*}J_{p})v\right\rVert_{{\mathcal{H}_{K}}}\leq
c\frac{\varphi(\lambda)}{\lambda}\left\lVert v\right\rVert_{\mathcal{H}_{K}}.$
(29)

Thus,

$\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\varphi(J_{p}^{*}J_{p})v\right\rVert_{{\mathcal{H}_{K}}}\leq
c\left(\gamma_{0}+\gamma_{\frac{3}{2}}\right)\Xi^{\frac{3}{2}}\lambda^{\frac{1}{2}}\varphi(\lambda).$

Substituting (28) and the above estimate into (5), we obtain the second bound
of the proposition.

Now we turn to proving the first bound and assume that $\beta$ meets (9) with
$\varphi=\vartheta\psi$. Then we have

$\displaystyle\left\lVert\xi(J_{p}^{*}J_{p})(\beta-\bar{\beta}^{\lambda})\right\rVert_{\mathcal{H}_{K}}\leq$
$\displaystyle\left\lVert\xi(J^{*}_{p}J_{p})r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\vartheta(S_{X_{p}}^{*}S_{X_{p}})\psi(J^{*}_{p}J_{p})v\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle+\left\lVert\xi(J_{p}^{*}J_{p})r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\vartheta(J^{*}_{p}J_{p})-\vartheta(S_{X_{p}}^{*}S_{X_{p}}))\psi(J^{*}_{p}J_{p})v\right\rVert_{\mathcal{H}_{K}}.$
(30)

Further, we estimate separately each term on the right-hand side of (5). By
using (28) and (29), the first term is estimated as follows:

$\displaystyle\left\lVert\xi(J^{*}_{p}J_{p})r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\vartheta(S_{X_{p}}^{*}S_{X_{p}})\psi(J^{*}_{p}J_{p})v\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 19.91684pt\leq\left\lVert\xi(J^{*}_{p}J_{p})(\lambda
I+J^{*}_{p}J_{p})^{-\frac{1}{2}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\left\lVert(\lambda
I+J^{*}_{p}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\vartheta(S_{X_{p}}^{*}S_{X_{p}})\psi(J^{*}_{p}J_{p})v\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 39.83368pt\times\left\lVert(\lambda
I+J^{*}_{p}J_{p})^{-1}\psi(J^{*}_{p}J_{p})v\right\rVert_{{\mathcal{H}_{K}}}$
$\displaystyle\hskip 19.91684pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\left\lVert(\lambda
I+J^{*}_{p}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\vartheta(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+J^{*}_{p}J_{p})\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\frac{\psi(\lambda)}{\lambda}\left\lVert
v\right\rVert_{\mathcal{H}_{K}}$ $\displaystyle\hskip 19.91684pt\leq
c\frac{\xi(\lambda)\psi(\lambda)}{{\lambda}^{\frac{3}{2}}}\Xi^{\frac{1}{2}}\left\lVert(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\vartheta(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\Xi$
$\displaystyle\hskip 19.91684pt\leq
c\frac{\xi(\lambda)\psi(\lambda)}{{\lambda}^{\frac{3}{2}}}\Xi^{\frac{3}{2}}\vartheta(\lambda)\lambda^{\frac{3}{2}}$
$\displaystyle\hskip 19.91684pt\leq
c\xi(\lambda)\varphi(\lambda)\Xi^{\frac{3}{2}},$ (31)

and with the use of (25) we can estimate the second term in (5) as

$\displaystyle\left\lVert\xi(J_{p}^{*}J_{p})r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\vartheta(J^{*}_{p}J_{p})-\vartheta(S_{X_{p}}^{*}S_{X_{p}}))\psi(J^{*}_{p}J_{p})v\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 14.22636pt\leq\left\lVert\xi(J_{p}^{*}J_{p})(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\vartheta(J^{*}_{p}J_{p})-\vartheta(S_{X_{p}}^{*}S_{X_{p}}))\psi(J^{*}_{p}J_{p})v\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 14.22636pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\left\lVert(\vartheta(J^{*}_{p}J_{p})-\vartheta(S_{X_{p}}^{*}S_{X_{p}}))\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}$
$\displaystyle\hskip 14.22636pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\left\lVert
J^{*}_{p}J_{p}-S_{X_{p}}^{*}S_{X_{p}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\psi(\kappa_{0})\left\lVert
v\right\rVert_{\mathcal{H}_{K}}$ $\displaystyle\hskip 14.22636pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\Xi^{\frac{1}{2}}\left\lVert(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})^{\frac{1}{2}}r_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\left\lVert
J^{*}_{p}J_{p}-S_{X_{p}}^{*}S_{X_{p}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}$
$\displaystyle\hskip 14.22636pt\leq
c\xi(\lambda)\Xi^{\frac{1}{2}}\left(\gamma_{0}+\gamma_{\frac{1}{2}}\right)\left\lVert
J^{*}_{p}J_{p}-S_{X_{p}}^{*}S_{X_{p}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}.$
(32)

Substituting (5) and (5) into (5), we obtain

$\displaystyle\left\lVert\xi(J_{p}^{*}J_{p})(\beta-\bar{\beta}^{\lambda})\right\rVert_{\mathcal{H}_{K}}\leq
c\xi(\lambda)\left(\Xi^{\frac{3}{2}}\varphi(\lambda)+(\gamma_{0}+\gamma_{\frac{1}{2}})\Xi^{\frac{1}{2}}\left\lVert
J^{*}_{p}J_{p}-S_{X_{p}}^{*}S_{X_{p}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\right).$

###### Proposition 14

Assume that Assumption 4 be satisfied. Then it holds

$\left\lVert\xi(J_{p}^{*}J_{p})(\bar{\beta}^{\lambda}-\beta_{\mathbf{X}}^{\lambda})\right\rVert_{\mathcal{H}_{K}}\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\Xi(\gamma_{-1}+\gamma_{0}+1)\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}.$

Proof  Using (9), (16) and (28), we derive

$\displaystyle\left\lVert\xi(J_{p}^{*}J_{p})(\bar{\beta}^{\lambda}-\beta_{\mathbf{X}}^{\lambda})\right\rVert_{\mathcal{H}_{K}}\leq\left\lVert\xi(J_{p}^{*}J_{p})g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 42.67912pt\leq\left\lVert\xi(J_{p}^{*}J_{p})(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}\right\rVert_{{\mathcal{H}_{K}}\rightarrow{\mathcal{H}_{K}}}\times$
$\displaystyle\hskip 153.6447pt\times\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 42.67912pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+J_{p}^{*}J_{p})^{\frac{1}{2}}\right\rVert_{{\mathcal{H}_{K}}\to{\mathcal{H}_{K}}}\times$
$\displaystyle\hskip 165.02606pt\times\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 42.67912pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\Xi^{\frac{1}{2}}\left\lVert
g_{\lambda}(S_{X_{p}}^{*}S_{X_{p}})(\lambda
I+S_{X_{p}}^{*}S_{X_{p}})\right\rVert_{\mathcal{H}_{K}}\Xi^{\frac{1}{2}}\times$
$\displaystyle\hskip 165.02606pt\times\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 42.67912pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\Xi\sup_{t}\big{|}g_{\lambda}(t)(\lambda+t)\big{|}\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}$
$\displaystyle\hskip 42.67912pt\leq
c\frac{\xi(\lambda)}{\sqrt{\lambda}}\Xi(\gamma_{-1}+\gamma_{0}+1)\left\lVert(\lambda
I+J_{p}^{*}J_{p})^{-\frac{1}{2}}(S_{X_{q}}^{*}S_{X_{q}}\mathbf{1}-S_{X_{p}}^{*}S_{X_{p}}\beta)\right\rVert_{\mathcal{H}_{K}}.$

Now we can combine (24) with Propositions 13, 14 and with Lemma 1. Then the
same argument as in the proof of Proposition 9 gives us the following
statement.

###### Theorem 15

Under the assumption of Propositions 13 and 14, for $\lambda>\lambda_{*}$ with
probability at least $1-\delta$, for all $x\in\mathbf{X}$, we have

$\displaystyle|\beta(x)-\beta^{\lambda}_{\mathbf{X}}(x)|\leq
c\xi(\lambda)\left(\varphi(\lambda)+(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})\frac{\xi(\lambda)}{\lambda}\right)\left(\log\frac{2}{\delta}\right)^{2},$

and for
$\lambda=\lambda_{m,n}=\theta_{\varphi,\xi}^{-1}(m^{-\frac{1}{2}}+n^{-\frac{1}{2}}),$

$|\beta(x)-\beta^{\lambda}_{\mathbf{X}}(x)|\leq
c\xi(\lambda_{m,n})\varphi(\lambda_{m,n})\log^{2}\frac{1}{\delta}.$

###### Remark 16

Let us consider the same index functions $\varphi(t)=t^{\eta}$ and
$\xi(t)=t^{\varsigma}$ as in Remark 12, where the accuracy of order
$O\left((m^{-\frac{1}{2}}+n^{-\frac{1}{2}})^{\frac{\eta}{\eta+1-\varsigma}}\right)$
has been derived for (6). Under the same assumptions, Theorem 15 guarantees
the accuracy of order
$O\left((m^{-\frac{1}{2}}+n^{-\frac{1}{2}})^{\frac{\eta+\varsigma}{\eta+1-\varsigma}}\right)$.
This illustrates that the reconstruction of the Radon-Nikodym derivative at
any particular point can be done with much higher accuracy than its
reconstruction as an element of RKHS. But let us stress that the above high
order of accuracy is guaranteed when the qualification $s$ of the used
regularization scheme is higher than that of the Lavrentiev regularization or
KuLSIF (3).

##  6 Numerical illustrations

In our examples, we simulate inputs $X_{p}=(x_{1},x_{2},\ldots,x_{n})$ to be
sampled from the normal distribution $p\sim N(2,5)$, while the inputs
$X_{q}=(x_{1}^{\prime},x_{2}^{\prime},\ldots,x_{m}^{\prime})$ are sampled from
the normal distribution $q\sim N(\mu_{q},0.5)$ with $\mu_{q}=\\{2,3,4\\}$. In
this case, the Radon-Nikodym derivative $\beta=\frac{dq}{dp}$ is known to be

$\beta(x)=\sqrt{10}e^{\frac{(x-2)^{2}-10(x-\mu_{q})^{2}}{10}}.$

In the algorithms described in Section 3, we choose the kernel as

$\displaystyle K(x,x^{\prime})=1+e^{-\frac{(x-x^{\prime})^{2}}{2}},$

which is a combination of a universal Gaussian kernel with a constant such
that the corresponding space $\mathcal{H}_{K}$ contains all constant
functions.

We are going to illustrate that to achieve high order of accuracy for
reconstruction of the Radon-Nikodym derivative at any particular point, as it
is guaranteed by Theorem 15, one needs to employ a regularization with the
qualification that is higher than 1. For doing this we use a particular case
of the general regularization scheme (6), namely the iterated Lavrentiev
regularization, to compute the values of the approximate Radon-Nikodym
derivative
$\beta_{\mathbf{X}}^{\lambda}=(\beta_{1}^{\lambda},\beta_{2}^{\lambda},\cdots,\beta_{n}^{\lambda})$
with $\beta_{i}^{\lambda}=\beta_{\mathbf{X}}^{\lambda}(x_{i})$.

Recall that the $k$ times iterated Lavrentiev regularization is indexed by the
functions

$\displaystyle
g_{\lambda}(t)=g_{\lambda,k}(t)=\left(1-\frac{\lambda^{k}}{(\lambda+t)^{k}}\right)t^{-1},$
(33)

and has the qualification $s=k$.

For $g_{\lambda}(t)=g_{\lambda,k}(t)$ the vector of values of the approximate
Radon-Nikodym derivative
$\beta^{\lambda}_{\mathbf{X}}=\beta^{\lambda,k}_{\mathbf{X}}$ given by (6),
(33) is the $k$-th term of the sequence

$\displaystyle\beta^{\lambda,l}_{\mathbf{X},0}$ $\displaystyle=0,$
$\displaystyle\beta^{\lambda,l}_{\mathbf{X}}$
$\displaystyle=\left(n\lambda\mathbf{I}+\mathbf{K}\right)^{-1}\left(n\lambda\beta^{\lambda,l-1}_{\mathbf{X}}+\bar{F}\right),\hskip
14.22636ptl=1,2,\ldots,k.$ (34)

where $\mathbf{I}$ is $n$ by $n$ identity matrix,
$\mathbf{K}=\left(K(x_{i},x_{j})\right)_{i,j=1}^{n}$, and
$\bar{F}=(F_{i})_{i=1}^{n}$ with
$F_{i}=\frac{n}{m}\sum_{j=1}^{m}K(x_{i},x_{j}^{\prime}).$

The algorithm (6) has been implemented with $m=n=100$ and
$k=\\{1,2,3,5,10\\}$. The regularization parameter $\lambda$ is chosen by the
so-called quasi-optimality criterion (see, for example, Bauer and Reiß (2008),
Kindermann et al. (2018)),
$\bar{\lambda}\in\\{\lambda_{\iota}=\lambda_{0}\varrho^{\iota},\iota=1,2,\ldots,w\\},\varrho<1$
such that for $\bar{\lambda}=\lambda_{\iota_{0}},$

$\left\lVert\beta^{\lambda_{\iota_{0}}}_{\mathbf{X}}-\beta^{\lambda_{\iota_{0}-1}}_{\mathbf{X}}\right\rVert_{\mathbbm
R^{n}}=\min\left\\{\left\lVert\beta^{\lambda_{\iota}}_{\mathbf{X}}-\beta^{\lambda_{\iota-1}}_{\mathbf{X}}\right\rVert_{\mathbbm
R^{n}},\iota=1,2,\ldots,w\right\\}.$

Taking into consideration Theorem 15 and Figure 1, one can expect that
$\bar{\lambda}\approx\lambda_{m,n}>(m^{-\frac{1}{2}}+n^{-\frac{1}{2}})$.
Therefore, for $n=m=100$ it is natural to look for $\bar{\lambda}$ within
interval $[0.1,0.9]$, and in our experiments we choose $\lambda_{0}=0.9$,
$\varrho=\sqrt[9]{\frac{1}{9}}$, and $w=9$, such that
$\lambda_{\iota}\in[0.1,0.9]$.

(a)

(b)

(c)

Figure 2: Mean-square deviation in examples with (a) $X_{q}\sim N(2,0.5)$, (b)
$X_{q}\sim N(3,0.5)$, and (c) $X_{q}\sim N(4,0.5)$.

The performance of each implementation has been measured in terms of the mean-
square deviation (MSD).

$MSD=n^{-1}\sum_{i=1}^{n}\left(\beta(x_{i})-\beta^{\lambda,k}_{\mathbf{X}}(x_{i})\right)^{2}.$

A summary of the performance over 20 simulations of $(x_{i})_{i=1}^{n}$,
$(x_{j}^{\prime})_{j=1}^{m}$ in all cases $\mu_{q}=\\{2,3,4\\}$ is presented
in the form of box plots in Figure 2. It can be clear seen that in our
examples the considered realization of the iterated Laventiev regularization
outperforms its original version $(k=1)$. This supports a conclusion from
Theorem 15 suggesting the use of high qualification regularization for
pointwise evaluation of Radon-Nikodym derivation.

The performance of the algorithm (6) for a particular simulation is displayed
in Figure 3. In this figure, the exact values $\beta$ are shown by the line,
and the $\beta^{\lambda,1}_{\mathbf{X}}(x_{i})$,
$\beta^{\lambda,2}_{\mathbf{X}}(x_{i})$,
$\beta^{\lambda,3}_{\mathbf{X}}(x_{i})$,
$\beta^{\lambda,5}_{\mathbf{X}}(x_{i})$, and
$\beta^{\lambda,10}_{\mathbf{X}}(x_{i})$ are denoted correspondingly by green
triangles, red squares, cyan diamonds, yellow stars, and blue crosses.

(a)

(b)

(c)

Figure 3: The performance of the algorithm for a particular simulation with
(a) $X_{q}\sim N(2,0.5)$, (b) $X_{q}\sim N(3,0.5)$, and (c) $X_{q}\sim
N(4,0.5)$.

Acknowledgments and Disclosure of Funding

The research reported in this paper has been funded by the Federal Ministry
for Climate Action, Environment, Energy, Mobility, Innovation and Technology
(BMK), the Federal Ministry for Digital and Economic Affairs (BMDW), and the
Province of Upper Austria in the frame of the COMET–Competence Centers for
Excellent Technologies Programme and the COMET Module S3AI managed by the
Austrian Research Promotion Agency FFG.

## References

  * Bauer and Reiß (2008) Frank Bauer and Markus Reiß.  Regularization independent of the noise level: an analysis of quasi-optimality.  _Inverse Problems_ , 24(5):055009, aug 2008.  doi: 10.1088/0266-5611/24/5/055009.  URL https://dx.doi.org/10.1088/0266-5611/24/5/055009.
  * Bauer et al. (2007) Frank Bauer, Sergei V. Pereverzyev, and Lorenzo Rosasco.  On regularization algorithms in learning theory.  _J. Complex._ , 23:52–72, 2007.
  * Caponnetto and De Vito (2007) A. Caponnetto and E. De Vito.  Optimal rates for the regularized least-squares algorithm.  _Foundations of Computational Mathematics_ , 7(3):331–368, 2007.  doi: 10.1007/s10208-006-0196-8.
  * De Vito et al. (2014) Ernesto De Vito, Lorenzo Rosasco, and Alessandro Toigo.  Learning sets with separating kernels.  _Applied and Computational Harmonic Analysis_ , 37(2):185–217, 2014.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2013.11.003.
  * Gizewski et al. (2022) Elke R. Gizewski, Lukas Mayer, Bernhard A. Moser, Duc Hoan Nguyen, Sergiy Pereverzyev Jr, Sergei V. Pereverzyev, Natalia Shepeleva, and Werner Zellinger.  On a regularization of unsupervised domain adaptation in RKHS.  _Applied and Computational Harmonic Analysis_ , 57:201–227, 2022.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2021.12.002.
  * Huang et al. (2006) Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola.  Correcting sample selection bias by unlabeled data.  _Advances in neural information processing systems_ , 19, 2006.
  * Kanamori et al. (2012) Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama.  Statistical analysis of kernel-based least-squares density-ratio estimation.  _Machine Learning_ , 86:335–367, 2012.  doi: 10.1007/s10994-011-5266-3.
  * Kindermann et al. (2018) Stefan Kindermann, Sergiy Pereverzyev Jr, and Andrey Pilipenko.  The quasi-optimality criterion in the linear functional strategy.  _Inverse Problems_ , 34(7):075001, may 2018.  doi: 10.1088/1361-6420/aabe4f.  URL https://dx.doi.org/10.1088/1361-6420/aabe4f.
  * Lu and Pereverzyev (2013) Shuai Lu and Sergei Pereverzyev.  _Regularization theory for ill-posed problems. Selected topics_.  01 2013.  ISBN 978-3-11-0286645-5.
  * Lu et al. (2019) Shuai Lu, Peter Mathé, and Sergiy Pereverzyev.  Analysis of regularized Nyström subsampling for regression functions of low smoothness.  _Analysis and Applications_ , 17(06):931–946, 2019.  doi: 10.1142/S0219530519500039.
  * Lu et al. (2020) Shuai Lu, Peter Mathé, and Sergei V. Pereverzev.  Balancing principle in supervised learning for a general regularization scheme.  _Applied and Computational Harmonic Analysis_ , 48(1):123–148, 2020.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2018.03.001.
  * Mathé and Hofmann (2008) Peter Mathé and Bernd Hofmann.  How general are general source conditions?  _Inverse Problems_ , 24(1):015009, jan 2008.  doi: 10.1088/0266-5611/24/1/015009.  URL https://dx.doi.org/10.1088/0266-5611/24/1/015009.
  * Mathé and Pereverzev (2003) Peter Mathé and Sergei V Pereverzev.  Discretization strategy for linear ill-posed problems in variable hilbert scales.  _Inverse Problems_ , 19(6):1263, oct 2003.  doi: 10.1088/0266-5611/19/6/003.
  * Nguyen et al. (2010) XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan.  Estimating divergence functionals and the likelihood ratio by convex risk minimization.  _IEEE Transactions on Information Theory_ , 56(11):5847–5861, 2010.  doi: 10.1109/TIT.2010.2068870.
  * Oneto et al. (2016) Luca Oneto, Sandro Ridella, and Davide Anguita.  Tikhonov, Ivanov and Morozov regularization for support vector machine learning.  _Machine Learning_ , 103(1):103–136, 2016.
  * Page and Grünewälder (2019) Stephen Page and Steffen Grünewälder.  Ivanov-regularised least-squares estimators over large rkhss and their interpolation spaces.  _J. Mach. Learn. Res._ , 20(120):1–49, 2019.
  * Pauwels et al. (2018) Edouard Pauwels, Francis Bach, and Jean-Philippe Vert.  Relating leverage scores and density using regularized christoffel functions.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Pereverzyev (2022) Sergei Pereverzyev.  _An Introduction to Artificial Intelligence Based on Reproducing Kernel Hilbert Spaces_.  Springer International Publishing, 05 2022.  ISBN 978-3-030-98315-4.  doi: https://doi.org/10.1007/978-3-030-98316-1.
  * Que and Belkin (2013) Qichao Que and Mikhail Belkin.  Inverse density as an inverse problem: The Fredholm equation approach.  _Advances in Neural Information Processing Systems_ , 26:., 2013.
  * Rudi et al. (2015) Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco.  Less is more: Nyström computational regularization.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.
  * Schuster et al. (2020) Ingmar Schuster, Mattes Mollenhauer, Stefan Klus, and Krikamol Muandet.  Kernel conditional density operators.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 993–1004. PMLR, 26–28 Aug 2020.
  * Sugiyama et al. (2012) Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori.  _Density Ratio Estimation in Machine Learning_.  Cambridge University Press, 2012.  doi: 10.1017/CBO9781139035613.