# adaptive_learning_of_density_ratios_in_rkhs__d4d2692f.pdf

Journal of Machine Learning Research 24 (2023) 1-28 Submitted 8/23; Revised 11/23; Published 12/23

Adaptive Learning of Density Ratios in RKHS

Werner Zellinger werner.zellinger@oeaw.ac.at Johann Radon Institute for Computational and Applied Mathematics Austrian Academy of Sciences Linz, Austria

Stefan Kindermann kindermann@indmath.uni-linz.ac.at Industrial Mathematics Institute Johannes Kepler University Linz Linz, Austria

Sergei V. Pereverzyev sergei.pereverzyev@oeaw.ac.at Johann Radon Institute for Computational and Applied Mathematics Austrian Academy of Sciences Linz, Austria

Editor: Mahdi Soltanolkotabi

Estimating the ratio of two probability densities from finitely many observations of the densities is a central problem in machine learning and statistics with applications in two-sample testing, divergence estimation, generative modeling, covariate shift adaptation, conditional density estimation, and novelty detection. In this work, we analyze a large class of density ratio estimation methods that minimize a regularized Bregman divergence between the true density ratio and a model in a reproducing kernel Hilbert space (RKHS). We derive new finite-sample error bounds, and we propose a Lepskii type parameter choice principle that minimizes the bounds without knowledge of the regularity of the density ratio. In the special case of square loss, our method adaptively achieves a minimax optimal error rate. A numerical illustration is provided.

Keywords: density ratio estimation, reproducing kernel Hilbert space, learning theory, regularization, inverse problem

1. Introduction

1.1 Problem

Let P and Q be two probability measures on a measurable space (X, A) with compact X Rd and σ-algebra A of its measurable subsets. Assume that P is absolutely continuous with respect to Q. Then, the Radon-Nikod ym theorem grants us a Q-integrable function

c 2023 Werner Zellinger, Stefan Kindermann, Sergei V. Perverzyev.

License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v24/23-1004.html.

Zellinger, Kindermann and Pereverzyev

β : X [0, ) satisfying, for any U A,

U β(x) d Q(x). (1)

If both measures, P and Q, have densities with respect to another reference measure, e.g., the Lebesgue measure, then β equals the ratio of their densities.

The problem of learning β from samples x := (xi)m i=1 and x := (x i)n i=1, drawn independently and identically (i.i.d.) from P and Q, respectively, plays a central role in statistics and machine learning (Sugiyama et al., 2012a); its applications include anomaly detection (Smola et al., 2009; Hido et al., 2011), two-sample testing (Keziou and Leoni-Aubin, 2005; Kanamori et al., 2011), divergence estimation (Nguyen et al., 2007, 2010), covariate shift adaptation (Shimodaira, 2000; Gizewski et al., 2022; Dinu et al., 2023), generative modeling (Mohamed and Lakshminarayanan, 2016), conditional density estimation (Schuster et al., 2020), and classification from positive and unlabeled data (Kato et al., 2019). Note, that this problem is different from supervised learning (Cucker and Smale, 2001) as the given data do not include point evaluations β(x) from the desired target β.

It has been first observed by Sugiyama, Suzuki, and Kanamori (2012b) that many algorithms for density ratio estimation compute finite-sample approximations of the objective β by discretizing the minimization problem

min f H BF (β, g(f)) + λ

2 f 2 , (2)

where g(f) is a model of the Radon-Nikod ym derivative β with f H in a reproducing kernel Hilbert space (RKHS) H, BF (β, eβ) := F(β) F(eβ) F(eβ)[β eβ] is a Bregman divergence generated by some convex functional F : L1(Q) R, . is a norm on H, and λ R is a regularization parameter; see Example 1. For the exact form of the finitesample approximations applied in practice, we ask the reader for patience until Eq. (11) is stated.

As can be seen from (Sugiyama et al., 2012b, Section 3.2.1), the kernel unconstrained least-squares importance fitting procedure (Ku LSIF) in (Kanamori et al., 2009) uses Eq. (2) with F(h) = R

X (h(x) 1)2/2 d Q(x) and g = id, where id(f) = f is the identity (cf. (Kanamori et al., 2012, Eq. (4))). This leads to a discretization of the minimization problem

min f H 1 2 β f 2 L2(Q) + λ

2 f 2 . (3)

The logistic regression approach (LR) employed in (Bickel et al., 2009, Section 7) can be obtained from Eq. (2) using F(h) = R

X h(x) log(h(x)) (1+h(x)) log(1+h(x)) d Q(x) and g(f) = ef with f(x) = θTϕ(x) for some ϕ : X Rd; see (Sugiyama et al., 2012b, Section 3.2.3).

Adaptive Learning of Density Ratios in RKHS

The exponential function approach (Exp) introduced in (Menon and Ong, 2016, Section 7) can be obtained using F(h) = R

X h(x) 3/2 d Q(x) and g(f) = e2f; see (Menon and Ong, 2016, Table 1).

The square loss (SQ) is used in (Menon and Ong, 2016, Table 1) with F(h) = R

X 1/(2h(x) + 2) d Q(x) and g(f) = 1+2f

To the best of our knowledge, no error bounds are known for estimating Eq. (2) for the functionals in Example 1 that take into account the regularity of the density ratio β, except (Gizewski et al., 2022, Section 3.1) and (Nguyen et al., 2023) which hold only for Ku LSIF. Moreover, except for Ku LSIF, no method for choosing the regularization parameter λ in Eq. (2) is known that adapts to the regularity of β, i.e., a method with error bounds provably decreasing for increasing regularity.

1.2 Results

Following Menon and Ong (2016), one can relate the minimization of the data fidelity term B(f) := BF (β, g(f)) from Eq. (2), to the minimization of the expected loss with a loss function ℓ: { 1, 1} R R measuring by ℓ( 1, f(x)) and ℓ(1, f(x)), respectively, the error of a classifier f(x) which predicts whether x is drawn from P or Q.

Our first result (Example 3) shows that all loss functions ℓcorresponding to Example 1, satisfy a property called generalized self-concordance (Marteau-Ferey et al., 2019). This allows us to extend results from supervised learning in RKHSs to density ratio estimation.

Our second result (Proposition 2) provides, in a well specified setting, for large enough sample sizes and with high probability, an error bound

B(fλ x,x ) O (m + n) 2rα+α 2rα+α+1 (4)

for a minimizer fλ x,x of the empirical estimation Eq. (11) of Eq. (2) with appropriately chosen regularization parameter λ. The regularity index r and the capacity index α in Eq. (4) originate from source conditions as used in inverse problems and learning theory. In the special case of square loss (SQ), the error rate in Eq. (4) is minimax optimal in the same sense as it is minimax optimal in supervised learning, see (Caponnetto and De Vito, 2007; Blanchard and M ucke, 2018).

Our third result (Eq. (30)) is a new method for choosing the regularization parameter λ that does not need access to the regularity index r but nevertheless achieves the same rate as in Eq. (4) (see Theorem 2). Our method is based on a Lepskii-type principle balancing bias and variance terms of a local quadratic approximation of the (generally not quadratic) data fidelity B(f). Our parameter choice strategy achieves the error rate in Eq. (4) and is thus optimal in the case of square loss. A numerical example illustrates our theoretical findings.

1.3 Related Work

The representation of density ratio estimation methods as minimizers of empirical estimations of Eq. (2) has been first observed by Sugiyama et al. (2012b) and later characterized

Zellinger, Kindermann and Pereverzyev

in more detail by Menon and Ong (2016). Our work extends (Sugiyama et al., 2012b; Menon and Ong, 2016) by taking into account the effect of the regularization term λ

in Eq. (2).

In general, to the best of our knowledge, there are no error bounds similar to Eq. (4) for the class of discretized minimization problems Eq. (2). For the special case of Ku LSIF in Eq. (3), error rates have been discovered in (Kanamori et al., 2012; Gizewski et al., 2022; Nguyen et al., 2023). In particular, the error rate discovered in (Kanamori et al., 2012), for RKHS with bracketing entropy γ (0, 2), is

B(fλ z ) = O min{m, n} 2 2+γ . (5)

This rate is worse than the one in Eq. (4), whenever α(2r + 1) > 2

γ . A similar result for Ku LSIF and the special case of Gaussian kernel, is presented in Que and Belkin (2013), see Type I setting there. We can also mention (Gizewski et al., 2022, Remark 3) which provides the error bound

B(fλ z ) = O

with r originating from a source condition similar to our Assumption 5 but for the covariance operator T = R

X k(z, ) k(z, ) d Q(z) of Q instead of ρ, where k denotes the kernel of H and (u v)[f] = u, f v the rank-1 operator. Our result in Eq. (4) improves Eq. (6) for α (1, ) and 0 < r r 1

2. In the recent work (Nguyen et al., 2023), Eq. (6) is improved by additionally taking into account the capacity of the space H in terms of a new pointwise source condition on the reproducing kernel of H that allows to bound the regularized Christoffel function. Such condition can be used as alternative for the effective dimension as defined in our Assumption 6. As a result, an error bound similar to our Eq. (4) is obtained in (Nguyen et al., 2023). However, the error is measured in the H-norm and the bound holds only for the special case of the Ku LSIF.

To the best of our knowledge, the balancing principle introduced in this work is the first parameter choice method for density ratio estimation with discovered error rate. We can mention variants of cross-validation (Kanamori et al., 2012), the quasi-optimality criterion (Nguyen et al., 2023), and hints towards the use of balancing principles (Gizewski et al., 2022), but, even in the special case of Ku LSIF, we are not aware of any finite-sample error bounds related to these approaches.

Some of our proof techniques rely on (Marteau-Ferey et al., 2019), where self-concordant loss functions in the context of kernel learning were studied first. Our analysis extends (Marteau Ferey et al., 2019) to density ratio estimation and adaptive parameter choice.

Adaptive Learning of Density Ratios in RKHS

2. Notation and Auxiliaries

2.1 Estimation of Bregman Divergence

Menon and Ong (2016) study properties of F and g, which allow an intuitive estimation of Eq. (2) by discriminating i.i.d. observations x = (xi)m i=1 from P and x = (x i)n i=1 from Q. In the following, we will summarize some of these properties.

Let us start by introducing the underlying model: a probability measure ρ on X Y, Y := { 1, 1}, with conditional probability measures1 defined by ρ(x|y = 1) := P(x) and ρ(x|y = 1) := Q(x) and a marginal (w.r.t. y) probability measure ρY defined as Bernoulli measure with probability 1

2 for both events y = 1 and y = 1. We make the following assumption on the data generation process.

Assumption 1 (iid data) The data

z := (xi, 1)m i=1 (x i, 1)n i=1 X Y (7)

is an i.i.d. sample of an X Y-valued random variable Z with measure ρ.

Assumption 1 allows us to introduce a binary classification problem for the accessible data z. Recall the goal of the binary classification problem is to find, based on the data z, a classifier f : X R with a small expected risk

R(f) := E(x,y) ρ[ℓ(y, f(x))] = Z

X Y ℓ(y, f(x)) dρ(x, y) (8)

for some loss function ℓ: Y R R. In this work, we focus on strictly proper composite loss functions with twice differentiable Bayes risk, which are characterized by the following assumption.

Assumption 2 The function ℓ: Y R R has an associated invertible link function Ψ : [0, 1] R such that

1. the Bayes classifier f := arg minf:X R R(f) exists and f (x) = Ψ ρ(y = 1|x),

2. the Bayes risk G(u) := uℓ(1, Ψ(u)) + (1 u)ℓ( 1, Ψ(u)) is twice differentiable.

The main result of Menon and Ong (2016) is the following representation of the data fidelity in Eq. (2), in terms of a loss function satisfying Assumption 2.

Lemma 1 (Menon and Ong (2016), Proposition 3) Let the Bregman generator F and the density ratio model g(f) be defined by

X (1 + h(x)) G h(x) 1 + h(x)

d Q(x), g(f) := Ψ 1 f 1 Ψ 1 f , (9)

for some link function Ψ and the Bayes risk G of a loss ℓsatisfying Assumption 2. Then

BF (β, g(f)) = 2 (R(f) R(f )) . (10)

1. Existence follows from X Y being Polish (cf. (Dudley, 2002, Theorem 10.2.1), the product case).

Zellinger, Kindermann and Pereverzyev

Indeed, for all approaches in Example 1, we can find F and g as required by Lemma 1, see (Menon and Ong, 2016, Table 1). We refer to (Menon and Ong, 2016) for a recipe to construct new losses for Eq. (2) satisfying the requirements of Lemma 1.

Ku LSIF (Kanamori et al., 2009) uses ℓ( 1, v) = 1

2v2, ℓ(1, v) = v and Ψ(v) = v 1 v.

LR (Bickel et al., 2009) uses ℓ( 1, v) = log(1+ev), ℓ(1, v) = log(1+e v) and the link function Ψ(v) = log( 1

Exp (Menon and Ong, 2016) uses ℓ( 1, v) = ev, ℓ(1, v) = e v and the link function Ψ(v) = 1

SQ (Menon and Ong, 2016) uses ℓ( 1, v) = (1 + v)2, ℓ(1, v) = (1 v)2 and the link function Ψ(v) = v+1

According to Lemma 1, Eq. (2) can be expressed as regularized risk minimization objective, given g and F are constructed as specified in Lemma 1. This motivates the estimation of Eq. (2) by an empirical risk minimization

min f H 1 m + n

(x,y) z ℓ(y, f(x)) + λ

2 f 2 . (11)

Throughout this work, we will denote a minimizer of Eq. (11) by fλ z . The goal of this work is to analyze the error B(fλ z ) = BF (β, g(fλ z )) of estimating β by g(fλ z ).

2.2 Learning in RKHS with Convex Losses

Lemma 1 identifies the methods in Example 1 as risk minimization problems with loss functions as detailed in Example 2. We will see in Section 3 that these loss functions satisfy the following property when applied to functions f H from an RKHS H.

Assumption 3 (generalized self-concordance (Marteau-Ferey et al., 2019)) For any z = (x, y) X Y, the function ℓz : H R, ℓz(f) := ℓ(y, f(x)), f H, is convex, three times differentiable, and it exists a set ϕ(z) H such that

f H, h, k H : | 3ℓz(f)[k, h, h]| 2ℓz(f)[h, h] sup p ϕ(z) |k p|. (12)

The definition of self-concordance originates from the analysis of Newton s method (Nesterov and Nemirovskii, 1994) and has been generalized in (Bach, 2010; Marteau-Ferey et al., 2019). Before we review error bounds, we follow Marteau-Ferey et al. (2019) and make the following technical assumptions.

Assumption 4 (technical assumptions) For self-concordant ℓz( ) with the set ϕ(z) H in Eq. (12), it holds:

1. There exists R 0 such that for any realization z of the random variable Z, supg ϕ(z) g R almost surely.

Adaptive Learning of Density Ratios in RKHS

2. The following quantities are almost surely bounded for any realization z of the random variable Z: |ℓz(0)|, ℓz(0) , Tr( 2ℓz(0)).

3. There exists a minimizer f H := arg minf H R(f).

In the sequel, the symbols ϕ(Z) and ℓZ mean the varieties of sets ϕ(z) and functions ℓz corresponding to the realizations z of the random variable Z. The first point of Assumption 4 is standard in learning theory (Caponnetto and De Vito, 2007; Steinwart et al., 2009) and, together with point 2, assures that R(f) is well defined for all f H. Point 3 imposes that our model is well specified in the sense that the function class H contains the minimizer of R. Under these assumptions, Theorem 3 in (Marteau-Ferey et al., 2019) holds, which we state in our notation as follows:

Lemma 2 (Marteau-Ferey et al. (2019), Theorem 3) Let Assumptions 1, 3, 4 be satisfied, δ (0, 1

2], and define B1 and B2 as

B1 := sup f f H sup z supp(ρ) ℓz(f) , B2 := sup f f H sup z supp(ρ) Tr( 2ℓz(f)).

Then, whenever λ B2 and m + n is larger than

max 512 f H 2 R2 log 2

, 512 log 2

, 256R2B2 1 λ2 log 2

a minimizer fλ z of Eq. (11) satisfies, with probability at least 1 2δ,

R(fλ z ) R(f H) 84B2 1 λ(m + n) log 2

+ 2λ f H 2 . (14)

Lemma 2 is a general result, which does not take into account cases where a regularity of f H is assumed beyond f H H in Assumption 4. Such regularity can be encoded by so-called source conditions as used in the regularization theory for inverse problems (Engl et al., 1996; Bauer et al., 2007; Caponnetto and De Vito, 2007; Steinwart et al., 2009; Rudi and Rosasco, 2017; Blanchard and M ucke, 2018).

Assumption 5 (source condition) There exist r (0, 1

2], v H such that f H = H(f H)rv with the expected Hessian H(f) := E[ 2ℓZ(f)].

In the case of square loss, Assumption 5 recovers the polynomial source condition f H = T rv with covariance operator T = R

X k(z, ) k(z, ) dρ(z), for the kernel k of H and the rank-1 operator (u v)[f] = u, f v. Starting from r = 0 (assuming only f H H), the regularity of f H increases with increasing r, essentially reducing the number of eigenvectors of T needed to well approximate f H.

It is well known in learning theory (Zhang, 2002; Caponnetto et al., 2005; Caponnetto and De Vito, 2007) that the rate of convergence of regularized learning algorithms is not only influenced by the regularity of f H, but also by the capacity of the space H measured by the so-called effective dimension. We therefore make the following assumption of (Marteau-Ferey et al., 2019, Assumption 7), which generalizes (Caponnetto and De Vito, 2007, Definition 1).

Zellinger, Kindermann and Pereverzyev

Assumption 6 (capacity condition) There exist α 1, Q0 0 such that dfλ Q0λ 1

α with the degrees of freedom

dfλ := E Hλ(f H) 1

2 ℓZ(f H) 2 (15)

and Hλ(f) := H(f) + λI.

The degrees of freedom term dfλ appears as Fisher information in the asymptotic analysis of M-estimation (Van der Vaart, 2000; Lehmann and Casella, 2006), appears similarly in spline smoothing (Wahba, 1990), and reduces to the effective dimension (Caponnetto et al., 2005; Caponnetto and De Vito, 2007) dfλ = Tr(TT 1 λ ) with Tλ := T +λI for the square loss. In the latter case, Assumption 6 is equivalent to the condition σj = O(j α) for a sequence σ1, σ2, . . . of non-increasing positive eigenvalues of T (Guo et al., 2022, Theorem 5). That is, a bigger α implies that fewer eigenvectors are needed to approximate elements from the image space of T with a given capacity. On the other hand, from a regularization theory perspective, Assumption 6 can be interpreted as specifying the ill-posedness of the problem of inverting T (cf. (Blanchard and M ucke, 2018)).

Under Assumptions 5 and 6, the following result is stated in (Marteau-Ferey et al., 2019) and rephrased here in our notation. See Subsection 6.4 for more details on the derivation.

Lemma 3 (Marteau-Ferey et al. (2019), Theorem 38) Let Assumptions 1, 3 6 be satisfied, δ (0, 1

2], and define B1 and B2 by

B 1 := sup z supp(ρ) Tr( ℓz(f H)), B 2 := sup z supp(ρ) Tr( 2ℓz(f H)), L := f H H 2r(f H) ,

where f A := A 1 2 f . Whenever 0 < λ min{B 2, (2LR log 2

δ) 1/r, Q2α 0 (B 2)α(B 1) 2α} and m + n is larger than

max 5184B 2 λ log 8 4142B 2 λδ

, 1296Q2 0 L2λ1+2r+1/α

then a minimizer fλ z of Eq. (11) satisfies, with probability at least 1 2δ,

R(fλ z ) R(f H) fλ z f H 2

H(f H) fλ z f H 2

414 Q2 0 (m + n)λ1/α log 2

+ 414L2λ1+2r. (17)

In the special case of square loss (SQ), it is possible to find λ in Lemma 3 that recovers the minimax optimal error rate discovered in (Caponnetto and De Vito, 2007); see (Marteau Ferey et al., 2019, Corollary 39). However, (Marteau-Ferey et al., 2019, Corollary 39) uses an a priori choice of λ that depends on the regularity level r, which cannot be computed from the available samples.

Adaptive Learning of Density Ratios in RKHS

3. Error Rates under Regularity and Capacity

Let us start by Assumption 1. The goal of this section is to analyze the error of a density ratio model g(fλ z ) with a minimizer fλ z of Eq. (11), in terms of the data fidelity B(f) := BF (β, g(f)) as specified in Eq. (9). We note that this setting is general, in the sense that all methods in Example 1 are included.

Our analysis is based on the observation that all loss functions in Example 2 are selfconcordant as defined in Assumption 3.

Ku LSIF (Kanamori et al., 2009) uses the losses ℓ(x, 1)(f) = 1

2f(x)2, ℓ(x,1)(f) = f(x) which are three times differentiable and Eq. (12) holds with ϕ((x, y)) = {0} H.

LR (Bickel et al., 2009) is self-concordant with ϕ((x, y)) = {y Kx}, see (Marteau-Ferey et al., 2019, Example 2) and (Bach, 2010).

Exp (Menon and Ong, 2016) uses ℓ(x,y)(f) = eyf(x) which is self-concordant with ϕ((x, y)) = {y Kx}.

SQ (Menon and Ong, 2016) uses losses which are three times differentiable and Eq. (12) holds with ϕ((x, y)) = {0} H.

Before discussing faster error rates with more advanced regularity concepts, let us discuss the special role of the parameter λ when chosen to balance the two terms in Eq. (14). As an intermediate result, we will provide first error rates for regularized losses beyond the Ku LSIF approach in Eq. (3).

3.1 Slow Error Rate with A Priori Parameter Choice

We have observed above that many methods for density ratio estimation are based on selfconcordant loss functions. From Lemma 2 we know that, for large enough sample size m+n, with probability larger than 1 2δ, a minimizer fλ z of Eq. (11) satisfies the following bound:

B(fλ z ) B(f H) S(m + n, δ, λ) + A(λ), (18)

S(m + n, δ, λ) := 168 B2 1 λ(m + n) log 2

and A(λ) := 4λ f H 2 .

The question is: how to choose λ?

One strategy in learning theory is to use the value λ which balances (Lepskii, 1991; Goldenshluger and Pereverzev, 2000; Birg e, 2001; Math e, 2006; De Vito et al., 2010; M ucke, 2018; Blanchard et al., 2019; Lu et al., 2020; Zellinger et al., 2021)

η S(m + n, δ, λ ) = A(λ ) (19)

for some η 1 ensuring that λ is in the admissible set of values as, e.g., specified by Eq. (13). The value λ in Eq. (19) is achieved, due to the monotonicity of S(m + n, δ, λ) (decreasing) and A(λ) (increasing, starting from A(0) = 0).

Zellinger, Kindermann and Pereverzyev

The parameter choice λ is particularly interesting, as it minimizes the right-hand side of Eq. (18) up to a constant factor and, as a consequence, allows to achieve error rates of optimal order; see Subsection 6.1.

Proposition 1 Let Assumptions 1 4 be satisfied, and let δ (0, 1

2]. Let further λ be the solution of Eq. (19) for η := 256R2

42 f H 2, which we assume to be larger than 1. The there exists a quantity C > 0 not depending on m, n, δ, such that the minimizer fλ z of Eq. (11) satisfies

B(fλ z ) B(f H) C(m + n) 1

2 log 1 2 2

with probability at least 1 2δ, for large enough sample size m + n, which depends on δ.

Explicit bounds on the sample size m + n and the quantity C are given in Eq. (36) and Eq. (38), respectively. The value for λ specified in Proposition 1 and Eq. (35) can be computed a priori. That is, all information needed to achieve the error rate (m + n) 1

2 is available. However, this situation changes in Subsection 3.2 when the regularity of f H is taken into account.

Remark 4 Together with Example 3, our Proposition 1 provides (to the best of our knowledge) the first error rate for regularized density ratio estimation methods beyond Ku LSIF. At the same time, for B(fλ z ) = β fλ z 2 L2(Q) as used in Ku LSIF, the error has been analyzed in (Kanamori et al., 2012) in terms of the so-called bracketing entropy γ of H. In our notation, this result tells us that, if γ (0, 2) and β H (so that B(f H) = 0), then, for ϵ satisfying 1 2 2+γ < ϵ < 1 and λ 1 = O min{m, n}1 ϵ , with probability 1 δ, it holds that

B(fλ z ) = O min{m, n}ϵ 1 . (21)

The rate in Eq. (21) is faster for smaller ϵ and tends, for RKHSs with γ 2, to its optimum min{m, n} 1

2 , which is the same rate as given by our Proposition 1. For m n as motivated by Assumption 1, our result therefore recovers the state of the art (Kanamori et al., 2009) for Ku LSIF and RKHS with bracketing entropy γ 2. In the same case, the rate has been recently improved in (Gizewski et al., 2022) for regular β, which we discuss in the next Section 3.2.

3.2 Fast Error Rate Requiring A Posteriori Parameter Choice

The following result is based on Lemma 3 and it takes into account the unknown regularity of f H by Assumption 5.

Proposition 2 Let Assumptions 1 6 be satisfied for some α 1 1 2r, and let δ [ 2 e1296 , 1

2]. Let further λ be a solution of Eq. (19) with η := 1296 log 1 2

δ . Then there exists a quantity C > 0 not depending on m, n, δ, such that the minimizer fλ z of Eq. (11) satisfies

B(fλ z ) B(f H) C(m + n) 2rα+α 2rα+α+1 (22)

with probability at least 1 2δ, for large enough sample size m + n, which depends on δ.

Adaptive Learning of Density Ratios in RKHS

Explicit bounds on m+n and C are given in Eq. (41) and Eq. (43), respectively. The value λ in Proposition 2, as specified precisely in Eq. (40), depends on the regularity index r and can therefore not be computed a priori. A new method is required.

Remark 5 Together with Example 3, Proposition 2 provides (the to the best of our knowledge first) error rates result for regularized density ratio estimation methods that takes into account both, the regularity of the density ratio β and the capacity of the space H. As a result, even in the special case of Ku LSIF with B(fλ z ) = β fλ z 2 L2(Q), Proposition 2 allows to refine existing results. To see this, consider the fastest error rate of (Kanamori et al., 2012) discovered for RKHS with bracketing entropy γ (0, 2) (cf. Remark 1):

B(fλ z ) = O min{m, n} 2 2+γ . (23)

This rate is improved by O (m + n) 2rα+α 2rα+α+1 in Eq. (22) whenever α(2r +1) > 2

γ . We can also mention (Gizewski et al., 2022, Remark 3) which leads to the error bound

B(fλ z ) B(f H) = O

with r originating from a source condition similar to our Assumption 5 but for the covariance operator T = R

X k(x, ) k(x, ) d Q(x) of Q instead of ρ. The rate in Eq. (24) is slower than the one in Eq. (22) for α (1, ) and 0 < r r 1

2. In general, for the square loss (SQ), the error rate in Eq. (22) is optimal in a minimax sense, see (Caponnetto and De Vito, 2007; Steinwart et al., 2009; Blanchard and M ucke, 2018).

4. Balancing Principle using Approximation by Norm

4.1 Parameter Choice when the Norm is Known

The value λ in Proposition 2 cannot be computed directly as it depends on the regularity of β encoded in r; see Eq. (40). One solution to this problem is to estimate λ with Lepskii s balancing principle (Lepskii, 1991; Goldenshluger and Pereverzev, 2000; Birg e, 2001; Math e, 2006; De Vito et al., 2010; Lu et al., 2020; Zellinger et al., 2021). However, in general, no representation of B(fλ z ) B(f H) as squared norm is available. This prevents us from using the above referenced approaches directly, e.g., by using the norm estimates (De Vito et al., 2010, Proposition 1) or (Lu et al., 2020, Proposition 4.1).

In the following, we propose a novel form of the balancing principle based on the norm Hλ(f H) originating from the self-concordance-based upper bound in Eq. (17). Since the estimation of Hλ(f H) requires some care, we postpone it to the next Subection 4.2.

We start by defining a suitable discretization of increasing parameter candidates (λi)l i=1 R such that λ [λ1, λl] is in the range of admissible values (ensured by multiplication of η in Eq. (19)). The balancing principle is then based on checking a necessary condition. Namely, whenever λj λi λ , Lemma 3 and the monotonicity of

S(m + n, δ, λ) := 414Q2 0 (m + n)λ1/α log 2

and A(λ) := 414L2λ1+2r,

Zellinger, Kindermann and Pereverzyev

grant us the inequality fλi z fλj z 2

Hλj (f H) 2 fλj z f H 2

Hλj (f H) + 2 fλi z f H 2

2 fλj z f H 2

Hλj (f H) + 2 fλi z f H 2

2S(m + n, δ, λj) + 2A(λj) + 2S(m + n, δ, λi) + 2A(λi)

4S(m + n, δ, λj) + 4S(m + n, δ, λi)

8S(m + n, δ, λj)

8η S(m + n, δ, λj), (25)

where we have used that Hλj(f) = H(f) + λj I H(f) + λi I = Hλi(f) and η as defined in Proposition 2. Following the above reasoning, if the error bound in Lemma 3 is sharp, then the maximum λi (λi)l i=1 satisfying the above condition for all smaller λj, j {1, . . . , i 1}, can be expected to be close to λ . This leads to the following estimate

λi : fλi z fλj z 2

Hλj (f H) 8η S(m + n, δ, λj), j {1, . . . , i 1}

Importantly, Eq. (25) does not depend on the unknown regularity index r (0, 1

2] but only on the quantities m, n, Q0, α which are either given or an upper bound can be easily estimated from data. We may state the following preparatory result.

Theorem 1 Let Assumptions 1 6 be satisfied and let

λi := λ0 ξi, i {1, . . . , l}

with ξ > 1, λ0 ξ l min n B 2, 2LR log 2

r , Q2α 0 (B 2)α(B 1) 2αo , l < e1296

[ 2 e1296 , 1 4+2l]. Then there exists a quantity C > 0 not depending on m, n, δ, such that the

minimizer fλ+ z of Eq. (11) satisfies

B(fλ+ z ) B(f H) C(m + n) 2rα+α 2rα+α+1 (27)

with probability at least 1 (4 + 2l)δ, for large enough sample size m + n depending on δ.

Bounds on the sample size m + n and the quantity C are given in Eq. (44) and Eq. (48), respectively. We note that Theorem 1 achieves the same error rate as Proposition 2 but uses the parameter choice λ+ which is a posteriori computable if we have access to the

norm values fλi z fλj z 2

Hλj (f H). However, these values are not accessible, as we don t have

access to the measure ρ. This issue is solved in the next Subsection 4.2.

4.2 Parameter Choice with Estimated Norm

The following concentration result is proven in Subsection 6.4 and essentially combines analytical arguments for self-concordance losses (Marteau-Ferey et al., 2019) with concentration inequalities for Hermitian operators (Rudi and Rosasco, 2017).

Adaptive Learning of Density Ratios in RKHS

Lemma 6 Let the assumptions of Lemma 3 be satisfied, let δ (0, 1

2], denote the empirical Hessian by b H(f) := 1 m+n P z z 2ℓz(f), and let us write B A iffA B is positive semi-definite. Whenever H(fλ z ) > 0 and

m + n 16B 2 H(fλz ) log 2

then, with probability at least 1 4δ,

b Hλ(fλ z ) 6Hλ(f H) 48 b Hλ(fλ z ). (29)

Let us denote by (λi)l i=1 R a geometric sequence with λi := λ0 ξi, i {1, . . . , l} as defined in Theorem 1. Then, Lemma 6 motivates the following assumption

Assumption 7 For the sequence (λi)l i=1 there exists b > 0 with b mini {1,...,l} H(fλi z ) .

Note that for strictly convex loss functions, the Hessian is positive definite, and thus Assumption 7 is necessarily satisfied.

The same reasoning as done for Eq. (25) motivates, under Assumption 7, the estimate

λi : fλi z fλj z 2

b Hλj (f λj z ) 48η S(m + n, δ, λj), j {1, . . . , i 1}

with η := 1296 log 1(2

δ) as defined in Proposition 2. Note that Eq. (30) uses only given data or information for which upper bounds are easily estimable. Moreover, the following error rates result holds.

Theorem 2 Let all assumptions of Theorem 1 be satisfied for some l < e1296

12 1 and δ [ 2 e1296 , 1 6+6l]. Let further (λi)l i=1 satisfy Assumption 7. Then there exists a quantity C > 0 not depending on m, n, δ, such that the minimizer fλBP z of Eq. (11) satisfies

B(fλBP z ) B(f H) C(m + n) 2rα+α 2rα+α+1 (31)

with probability at least 1 (6 + 6l)δ, for large enough sample size m + n depending on δ.

Exact bounds on the sample size m+n and the quantity C are given in Eq. (57) and Eq. (61), respectively. Theorem 2 is the main result of this work. For large enough sample sizes, it provides an a posteriori parameter choice λBP that allows the minimizer fλBP z of Eq. (11) to achieve an error rate that improves with the regularity of the true solution.

Remark 7 To the best of our knowledge, Theorem 2 gives the first proof of the adaptivity to the unknown target regularity, for a parameter choice strategy in density ratio estimation. Even if similar adaptivity results hold for cross-validation in supervised learning (Caponnetto and Yao, 2010) and the aggregation method in covariate shift domain adaptation (Gizewski et al., 2022), their extension to density ratio estimation is not straight forward and an open future problem. In the special case of square loss (SQ), the order of the error rate is optimal (see Remark 5), and Eq. (30) thus provides, in this sense, adaptivity at optimal rate.

Zellinger, Kindermann and Pereverzyev

Figure 1: The goal is to learn the density ratio β = d P

d Q (black, solid).

5. Numerical Example

To illustrate the behaviour of our approach, we rely on an example of (Shimodaira, 2000; Sugiyama et al., 2007; Dinu et al., 2023; Nguyen et al., 2023) with data from two Gaussian distributions P, Q having means 4, 2 and standard deviations 1/

5, respectively, see Figure 1.

We use two different density ratio estimation methods in Eq. (11), the Exp approach, and, the Ku LSIF approach as described in Example 1. In particular, we approximate a minimizer of Eq. (11) by the conjugate gradient method applied to the parameters α1, . . . , αm+n of Eq. (11) when evaluated at a model ansatz fλ z = Pm+n j=1 αjk(xj, ) with reproducing kernel

k(x, x ) := 1 + e (x x )2

2 of H, as suggested by the representer theorem (Sch olkopf et al., 2001).

Following our goal of choosing λ, we fix a geometric sequence (λi)l i=1 R with λi := 10i, i { 3, . . . , 1} and compute

λi : fλi z fλj z 2

b Hλj (f λj z ) M λj(m + n), j {1, . . . , i 1}

for some M R and the pessimistic choice α = 1 in Assumption 6. The empirical norm in Eq. (32) can be computed, for two minimizers fλs z = Pm+n i=1 αik(xi, ) and fλt z = Pm+n i=1 βik(xi, ) of Eq. (11), by fλs z fλt z 2

b Hλt(fλt z ) = 1 m + n(α β)TKEK(α β) + λt(α β)TK(α β),

where α := (α1, . . . , αm+n), β := (β1, . . . , βm+n), K := (k(xi, xj))m+n i,j=1 and E :=

diag(e1, . . . , em+n) is a diagonal matrix with elements ei := e yi Pm+n j=1 βjk(xi,xj), in case of the Exp method, and ei := 1 yi

2 in the case of Ku LSIF, see Subsection 6.5.

To obtain theoretical error rate guarantees, Theorem 2 suggest to choose M := C as given by Eq. (61). However, as already noted in (Lu et al., 2020, Remark 6.1), this choice is too rough for the low number of samples considered in practical applications. We therefore follow (Lu et al., 2020, Remark 6.1) and choose M = Mj := Tr( b Hλj(fλj z )) 2.

Adaptive Learning of Density Ratios in RKHS

Figure 2: Results for approximating the density ratio β (black, dashed) by the Ku LSIF (green, solid) and Exp method (blue, solid). Rows: sample sizes m = n {3, 10, 100}. Columns: Parameter choices λ = 10i, i { 3, . . . , 2}. Choices of the proposed Lepskii type principle are marked by boxes in the upper left.

The results of our experiment can be found in Figure 2. The choice λ in Eq. (32) corresponds to λ = 10 2 for Ku LSIF in all three cases of dataset size m = n {3, 10, 100}. In case of the Exp method, it chooses λ = 10 1 for m = n {3, 10} and λ = 10 2 for m = n = 100. Although the choices are only optimal in two cases, w.r.t. the mean squared error evaluated at a dense grid of values, the parameter choice principle in Eq. (32) chooses always one of the two best values in the sequence.

6. Verification of Details

6.1 A priori parameter choice

The value λ satisfying Eq. (19) minimizes Eq. (18) up to a constant factor (cf. Lu and Pereverzev (2013), Section 4.3). To see this, let us denote a minimizer by λ1 := arg minλ 0 ηS(m + n, δ, λ) + A(λ). Then, either λ < λ1, in which case

ηS(m + n, δ, λ ) = A(λ ) A(λ1) η inf λ 0 [S(m + n, δ, λ) + A(λ)] ,

or λ1 λ , and

A(λ ) = ηS(m + n, δ, λ ) ηS(m + n, δ, λ1) η inf λ 0 [S(m + n, δ, λ) + A(λ)] ,

which gives, for large enough sample sizes and with high probability,

B(fλ z ) B(f H) ηS(m + n, δ, λ ) + A(λ ) 2η inf λ 0 [S(m + n, δ, λ) + A(λ)] . (33)

We will need the following technical lemma.

Zellinger, Kindermann and Pereverzyev

Lemma 8 If A, B > 0 and k 2A log(2AB), then A log(Bk) k.

Proof [Lemma 8] It holds that

A log(Bk) = A log Bk2AB

2AB + log(2AB) = A log k

2A + log(2AB)

2A + log(2AB) = k

2 + A log(2AB),

which gives the desired result whenever A log(2AB) k/2.

The following proof of Proposition 1 follows the essential steps of (Marteau-Ferey et al., 2019, Corollary 4) applied to Eq. (2) with explicit treatment of the balancing property Eq. (19) of λ .

Proof [Proposition 1] Using Assumptions 1 and 2, we obtain from Lemma 1

B(fλ z ) B(f H) = 2 R(fλ z ) R(f ) 2 (R(f H) R(f ))

= 2 R(fλ z ) R(f H) ,

where R(fλ z ) is an expectation w.r.t. the loss function ℓinducing B(fλ z ) = BF (β, g(fλ z )) as defined in Lemma 1. Let B1, B2 be as defined in Lemma 2. Then, under Assumptions 3 and 4, Lemma 2 gives, for large enough sample sizes m + n (as specified later), with probability larger than 1 2δ,

B(fλ z ) B(f H) S(m + n, δ, λ) + A(λ) (34)

for S(m + n, δ, λ) = 168 B2 1 λ(m+n) log(2

δ) and A(λ) = 4λ f H 2. Solving

η S(m + n, δ, λ ) = A(λ )

for λ with η = 162R2

42 f H 2 1 yields

λ = 16B1R m + n log 1 2 2

Let us now assume that m + n is larger that

512 f H 2 R2 log 2

, 512 log 2

, 256B2 1R2

, 9B2 2 log 6B2 2 4δB2 1R2 log 1 2

B2 1R2 log 2

In this case, λ is an admissible value as specified by the conditions of Lemma 2:

1. The condition λ B2 is satisfied since m + n 256B2 1R2

Adaptive Learning of Density Ratios in RKHS

2. The third element of the set from which the maximum is taken in Eq. (13) requires

= 3c1(m + n) 1 2 log 1

δ c1(m + n) 1 2 (37)

with c1 := 8B2 λ (m+n) 1 2 = B2 2B1R log 1

δ . Eq. (37) is guaranteed by Lemma 8 (with

k := (m + n) 1 2 , A := 3c1 and B := 1 δc), whenever 2A log(2AB) k. That is, whenever m + n is larger than

36c2 1 log2 6c2 1 δ

= 9B2 2 B2 1R2 log 1 2

log 6B2 2 4δB2 1R2 log 1 2

3. The last element from the set from which the maximum is taken in Eq. (13) requires m + n 256R2B2 1 (λ )2 log 2

δ , which is satisfied.

Note that η S(m + n, δ, λ ) + A(λ ) upper bounds Eq. (34) evaluated at λ . The desired result follows with

C := 128 f H 2 B1R. (38)

6.2 Error Rate Requiring A Posteriori Parameter Choice

The following proof of Proposition 2 uses Lemma 1 and follows the proof of (Marteau-Ferey et al., 2019, Corollary 9) applied to Eq. (2) (noting that Lemma 1 can be applied) with explicit treatment of the balancing property Eq. (19) of λ .

Proof [Proposition 2] Let us denote by L := H(f H) rf H . Using Assumptions 1 and 2, we obtain, from Lemma 1,

B(fλ z ) B(f H) = 2 R(fλ z ) R(f ) 2 (R(f H) R(f ))

= 2 R(fλ z ) R(f H) ,

where R(fλ z ) is an expectation w.r.t. the loss function ℓinducing B(fλ z ) = BF (β, g(fλ z )) as defined in Lemma 1. Let B 1, B 2 be as defined in Lemma 3. Then, under Assumptions 3 6, Lemma 3 gives, for large enough sample sizes m + n (as specified below in Eq. (41)), with probability larger than 1 2δ,

B(fλ z ) B(f H) 2S(m + n, δ, λ) + 2A(λ) (39)

for S(m + n, δ, λ) = 414 Q2 0 λ1/α(m+n) log(2

δ) and A(λ) = 414L2λ1+2r. Solving Eq. (19) for λ

and η = 1296 log 1 2

δ (notably being larger than 1 since δ 2e 1296), gives

λ = 1296Q2 0 (m + n)L2

α 1+2rα+α . (40)

Zellinger, Kindermann and Pereverzyev

In what follows, we will show that λ satisfies all assumptions from Lemma 3 whenever m + n is larger than

( Q2 0 L2(B 2)1+2r+ 1

α , Q2 0 L2

αr , 1296(B 1)2+4αr+2α

L2Q4αr+2α 0 (B 2)1+2αr+α ,

L2 (16 648B 2)1+2r+ 1

12962Q2 0 log1+2r+ 1

48(B 2)21296 4142

1296Q2 0 L2

2α 1+2rα+α ! )

1. The requirement λ B 2 is equivalent to

m + n 1296Q2 0 L2(B 2)1+2r+ 1

2. The requirement λ (2LR log 2

δ) 1/r is equivalent to

m + n 1296Q2 0 L2

3. The requirement λ Q2α 0 (B 2)α(B 1) 2α is equivalent to

m + n 1296(B 1)2+4αr+2α

L2Q4αr+2α 0 (B 2)1+2αr+α .

4. The requirement m + n 1296Q2 0 L2(λ )1+2r+1/α follows directly from the definition of λ .

5. The last requirement is

m + n 5184B 2 λ log 8 4142B 2 λ δ

= 648(m + n) α 1+2rα+α c1 log 4142

δ c1(m + n) α 1+2rα+α (42)

with c1 := 8B 2 1296Q2 0 L2 α 1+2rα+α . Eq. (42) follows from Lemma 8 (k := (m +

n) α 1+2rα+α , A := 648c1 and B := 4142

δ c1), whenever

m + n L2 (16 648B 2)1+2r+ 1

1296Q2 0 log1+2r+ 1

64(B 2)21296 4142

1296Q2 0 L2

2α 1+2rα+α !

since (m + n) α 1+2rα+α (m + n) 1 2 . The latter follows from α 1 1 2r.

Adaptive Learning of Density Ratios in RKHS

Evaluating 2η S(m+n, δ, λ )+2A(λ ), which upper bounds Eq. (39) evaluated at λ , gives the desired result for

C := 2 828L2 1296Q2 0 L2

α+2rα 1+2αr+α . (43)

6.3 Parameter Choice with Known Norm

We first prove the result assuming access to the norm Hλ(f H).

Proof [Theorem 1] Using Assumptions 1 and 2, we obtain, from Lemma 1,

B(fλ+ z ) B(f H) = 2 R(fλ+ z ) R(f ) 2 (R(f H) R(f ))

= 2 R(fλ+ z ) R(f H) ,

where R(fλ+ z ) is an expectation w.r.t. the loss function ℓinducing B(fλ+ z ) = BF (β, fλ+ z ) as defined in Lemma 1. From Lemma 3 we further know that, with probability at least 1 2δ,

B(fλ+ z ) B(f H) 2 fλ+ z f H 2

5184B 2 λ0 log 8 4142B 2 λ0δ

, 1296Q2 0 L2λ1+2r+1/α 0

We now define

λ := max{λi : A(λi) η S(m + n, δ, λi)}

with S(m + n, δ, λ) := 414Q2 0 (m+n)λ1/α log 2

δ , A(λ) := 414L2λ1+2r as used in Lemma 3 and

η := 1296 log 1 2

δ as used in Proposition 2. Using (a + b)2 2a2 + 2b2 and the triangle inequality, we obtain

B(fλ+ z ) B(f H) 4 fλ+ z fλ z 2

H(f H) + 4 fλ z f H 2

4 fλ+ z fλ z 2

Hλ(f H) + 4 fλ z f H 2

Hλ(f H) , (45)

where the last inequality follows from the fact that Hλ(f) = H(f)+λI H(f) and it holds with probability at least 1 2δ, for large enough sample size.

Zellinger, Kindermann and Pereverzyev

We will now prove bounds on the two terms in Eq. (45) separately. To bound the first term, we note that λ λ since A(λ) is increasing and S(m + n, δ, λ) is decreasing in λ. Eq. (25) implies, for any λj λ λ ,

fλ z fλj z 2

Hλj (f H) 8η S(m + n, δ, λj),

which holds with probability at least 1 2lδ for all j at the same time. As a consequence, we get λ λ+ from the maximizing property of λ+ in Eq. (26). Another consequence of λ λ+ and Eq. (26) is that

fλ+ z fλ z 2

Hλ(f H) 8η S(m + n, δ, λ). (46)

The bound fλ z f H 2

Hλ(f H) S(m + n, δ, λ) + A(λ) 2η S(m + n, δ, λ) (47)

follows from Lemma 3 and the definition of λ. Eq. (47) holds with probability at least 1 2δ. Inserting the bounds Eq. (46) and Eq. (47) into Eq. (45) gives

B(fλ+ z ) B(f H) 40η S(m + n, δ, λ),

which holds with probability at least 1 (4 + 2l)δ. Without loss of generality assume that λ0 ξs = λ λ = λ0 ξs+1. It follows that λ λ ξ and ξ1/αS(m+n, δ, λ ) S(m+n, δ, λ). Consequently,

B(fλ+ z ) B(f H) 40ξ1/αη S(m + n, δ, λ ) C(m + n) 2rα+α 2rα+α+1

holds with probability at least 1 (4 + 2l)δ and with

C := 16560ξ1/αL2 1296Q2 0 L2

α+2rα 1+2αr+α . (48)

6.4 Parameter Choice with Empirical Norm

In the following, let Rλ(f) := R(f) + λ

2 f 2, fλ := arg minf H Rλ(f) and t(f) := supz supp(ρ) supg ϕ(z) |f g| with ℓz, Z, ρ, ϕ as in Assumptions 1, 4 and 3. Recall also the definitions

Hλ(f) = H(f) + λI = E[ 2ℓZ(f)] + λI and b H(f) = 1 m + n

z z 2ℓz(f).

We need the following three lemmas.

Adaptive Learning of Density Ratios in RKHS

Lemma 9 (Marteau-Ferey et al. (2019), Proposition 15) Let Assumptions 1, 4 and 3 be satisfied, λ 0 and f1, f2 H. Then, we have

Hλ(f1) et(f1 f2)Hλ(f2) (49)

Rλ(f1) Rλ(f0) Rλ(f0)(f1 f0) ψ(t(f1 f0)) f1 f0 2 Hλ(f0) (50)

with ψ(t) = (et t 1)/t2.

Lemma 10 (Marteau-Ferey et al. (2019)) Under the conditions of Lemma 3, we have, with probability at least 1 2δ,

t(f H fλ) log(2), t(fλ fλ z ) log(2). (51)

Proof Lemma 33 in (Marteau-Ferey et al., 2019) shows that (noting that max{dfλ, (Q 0)2} (B1)2/λ from their Proposition 18 and 1/rλ(θ ) R/

λ by the remark after their Assumption 6) the conditions on n in Lemma 3 allow to apply their Proposition 16, which gives the desired result.

Lemma 11 (Marteau-Ferey et al. (2019), Rudi and Rosasco (2017)) Let the conditions of Lemma 3 be satisfied. Then, it holds, with probability at least 1 δ,

Hλ(f) 2 b Hλ(f). (52)

If, in addition, 0 < H(f) , then it holds, for all

m + n 16B 2 H(f) log 2

with probability at least 1 δ,

2Hλ(f). (54)

Proof Eq. (52) is proven in (Marteau-Ferey et al., 2019, Lemma 30). Eq. (54) follows from (Marteau-Ferey et al., 2019, Proposition 47) (attributed to (Rudi and Rosasco, 2017), Proposition 6 and Proposition 8) and (Marteau-Ferey et al., 2019, Remark 48).

We are now ready to provide more precise steps on the derivation of Lemma 3, which is essentially a re-phrasing of the proof of (Marteau-Ferey et al., 2019, Theorem 38) in our notation.

Proof [Lemma 3] From Eq. (50) and the fact that H(f) Hλ(f), we obtain

R(fλ z ) R(f H) ψ(t(fλ z f H)) fλ z f H 2

ψ(t(fλ z f H)) fλ z f H 2

Hλ(f H) , (55)

Zellinger, Kindermann and Pereverzyev

which is exactly how the proof of (Marteau-Ferey et al., 2019, Theorem 38) works. Indeed, they proceed by showing how Eq. (55) can be upper bounded by 414 Q2 0 (m+n)λ1/α log 2

δ + 414L2λ1+2r. To obtain Lemma 3, we just remark that

t(fλ z f H) t(fλ z fλ) + t(fλ z fλ)) 2 log(2) follows from Lemma 10. We further get ψ(t(fλ z f H)) ψ(2 log(2)) 1 since ψ(t) increases with t.

Lemma 6 can be obtained as follows.

Proof [Lemma 6] From Lemma 11 we get, with probability at least 1 δ,

b Hλ(fλ z ) 3

From Lemma 9, we further obtain

3 2Hλ(f H) 3

2et(fλ z f H)Hλ(f H) 3

2et(fλ z fλ)+t(fλ f H)Hλ(f H) 6Hλ(f H),

where the last inequality uses also Lemma 10. Proceeding with Eq. (52) in Lemma 11 gives

6Hλ(f H) 12 b Hλ(f H) 12et(fλ z f H) b Hλ(fλ z ) 48 b Hλ(fλ z ).

The conclusion follows whenever the above inequalities are satisfied at the same time, which happens with probability at least 1 4δ.

We are now ready to prove our main result.

Proof [Theorem 2] Following the proof of Theorem 1 line by line up to Eq. (45) and replacing λ+ by λBP gives, with probability at least 1 2δ,

B(fλBP z ) B(f H) 4 fλBP z fλ z 2

Hλ(f H) + 4 fλ z f H 2

Hλ(f H) , (56)

5184B 2 λ0 log 8 4142B 2 λ0δ

, 1296Q2 0 L2λ2+1/α 0 , 16B 2 1296b log 2

λ := max{λi : A(λi) η S(m + n, δ, λi)},

S(m + n, δ, λ) := 414Q2 0 (m+n)λ1/α log 2

δ and A(λ) := 414L2λ1+2r are defined as in Lemma 3,

and η := 1296 log 1 2

δ as defined in Proposition 2. Note that we used the requirement 1296Q2 0 L2λ2+1/α 0 1296Q2 0 L2λ1+2r+1/α 0 in Eq. (57) that is independent of r, and, we added a requirement

Adaptive Learning of Density Ratios in RKHS

based on b from Assumption 7 to satisfy all conditions needed to apply Lemma 6. From Lemma 3 and the definition of λ we obtain a bound for the second term of Eq. (56)

Hλ(f H) S(m + n, δ, λ) + A(λ) 2η S(m + n, δ, λ), (58)

with holds again with probability at least 1 2δ.

To bound the first term in Eq. (56), we note that Lemma 6 implies that

fλBP z fλ z 2

Hλ(f H) 8 fλBP z fλ z 2

b Hλ(fλ z ) , (59)

which holds with probability at least 1 4lδ for all possibilities λBP, λ {λ0, . . . , λl}. Let us now focus on all j which satisfy λj λ and note that λ λ by the monotonicity of S(m + n, δ, λ) and A(λ). For the above mentioned j, we apply Lemma 6, which grants us, with probability at least 1 2lδ for each j at the same time, fλ z fλj z 2

b Hλj (f λj z ) 6 fλ z fλj z 2

Hλj (f H) .

Now, the same reasoning as for Eq. (25) can be applied, to obtain, for any λj λ λ ,

fλ z fλj z 2

b Hλj (f λj z ) 48η S(m + n, δ, λj),

which holds with probability at least 1 (2 + 2l)δ resulting from the joint application of Lemma 3 and Lemma 6. As a consequence, we get λ λBP from the maximizing property of λBP in Eq. (30). Since λ λBP and Eq. (30) holds, we get

fλBP z fλ z 2

b Hλ(fλ z ) 48η S(m + n, δ, λ), (60)

which realizes with probability at least 1 (2+2l)δ. Combining the results above gives

B(fλBP z ) B(f H) 32 48η S(m + n, δ, λ) + 2 4η S(m + n, δ, λ) = 1544η S(m + n, δ, λ),

which holds with probability at least (6 + 6l)δ. With the same arguments as used in the proof of Theorem 1, it holds that S(m + n, δ, λ) ξ1/αS(m + n, δ, λ ) and further

B(fλBP z ) B(f H) 1544η ξ1/αS(m + n, δ, λ ) C(m + n) 2rα+α 2rα+α+1

with the constant

C := 1296 1544ξ1/α 828L2 1296Q2 0 L2

α+2rα 1+2αr+α . (61)

Zellinger, Kindermann and Pereverzyev

6.5 Derivation of Empirical Norms

Exp method Let ℓz(f) = e yf(x) for z = (x, y). Then, the reproducing property of the RKHS H with kernel k gives

2ℓz(f) = 2e y f(x) = 2e y k(x, ),f = e y k(x, ),f k(x, )k(x, ).

For the minimizer fλ z = Pm+n j=1 αjk(xj, ) of Eq. (11) as determined by the representer theorem, see, e.g. (Sch olkopf et al., 2001), it follows that

b Hλ(fλ z ) = 1 m + n

i=1 e yi Pm+n j=1 αjk(xi,xj)k(xi, )k(xi, ) + λI.

For fλs z = Pm+n j=1 αjk(xj, ) and fλt z = Pm+n j=1 βjk(xj, ) we obtain fλs z fλt z 2

b Hλt(fλt z ) = b H

1 2 λt(fλt z )(fλs z fλt z ), b H

1 2 λt(fλt z )(fλs z fλt z )

= D b Hλt(fλt z )(fλs z fλt z ), fλs z fλt z E

* b Hλt(fλt z )

j=1 (αj βj)k(xj, ),

j=1 (αj βj)k(xj, )

t=1 (αt βt)k(xi, xt)eik(xi, ),

j=1 (αj βj)k(xj, )

+ λt(α β)TK(α β)

= 1 m + n(α β)TKEK(α β) + λt(α β)TK(α β),

where α := (α1, . . . , αm+n), β := (β1, . . . , βm+n), diagonal matrix E := diag(e1, . . . , em+n), ei := e yi Pm+n j=1 βjk(xi,xj) and K := (k(xi, xj))m+n i,j=1.

Ku LSIF Let ℓ(x, 1)(f) = 1

2f(x)2 and ℓ(x,1)(f) = f(x). Then, the reproducing property of the RKHS H with kernel k gives

2ℓ(x, 1)(f) = k(x, )k(x, ), 2ℓ(x,1)(f) = 0.

For the minimizer fλ z = Pm+n j=1 αjk(xj, ) of Eq. (11), it follows that

b Hλ(fλ z ) = 1 m + n

2 k(xi, )k(xi, ) + λI.

For fλs z = Pm+n j=1 αjk(xj, ) and fλt z = Pm+n j=1 βjk(xj, ) we get, analogously to the derivation for the Exp method, fλs z fλt z 2

b Hλt(fλt z ) = 1 m + n(α β)TKEK(α β) + λt(α β)TK(α β),

where α := (α1, . . . , αm+n), β := (β1, . . . , βm+n), diagonal matrix E := diag(e1, . . . , em+n), ei := 1 yi

2 and K := (k(xi, xj))m+n i,j=1.

Adaptive Learning of Density Ratios in RKHS

7. Conclusion and Future Work

We proposed error bounds for a large class of kernel methods for density ratio estimation for which no error bounds were known before (to the best of our knowledge). The class consists of methods which minimize a regularized Bregman divergence over a reproducing kernel Hilbert space. We also proposed a Lepskii type principle for choosing the regularization parameter. The principle minimizes the error bounds without knowledge of the unknown regularity of the density ratio. As a consequence it achieves a minimax optimal error rate in the special case of square loss. The key proof technique for both, the error rates and the adaptive parameter choice, is a local quadratic approximation of the Bregman divergence, which is equivalent to an expected risk for a proper composite self-concordant loss function. The minimax optimality of our error bounds for non-square losses is an open problem.

Acknowledgements

We thank the anonymous reviewers for helpful comments and careful proofreading. 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 COMET Module S3AI managed by the Austrian Research Promotion Agency FFG.

Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4(none):384 414, 2010.

Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory. Journal of Complexity, 23(1):52 72, 2007.

Steffen Bickel, Michael Br uckner, and Tobias Scheffer. Discriminative learning under covariate shift. Journal of Machine Learning Research, 10(9), 2009.

Lucien Birg e. An alternative point of view on lepski s method. Lecture Notes-Monograph Series, pages 113 133, 2001.

Gilles Blanchard and Nicole M ucke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18:971 1013, 2018.

Gilles Blanchard, Peter Math e, and Nicole M ucke. Lepskii principle in supervised learning. ar Xiv preprint ar Xiv:1905.10764, 2019.

Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331 368, 2007.

Andrea Caponnetto and Yuan Yao. Cross-validation based adaptation for regularization operators in learning theory. Analysis and Applications, 8(02):161 183, 2010.

Zellinger, Kindermann and Pereverzyev

Andrea Caponnetto, Lorenzo Rosasco, Ernesto De Vito, and Alessandro Verri. Empirical effective dimension and optimal rates for regularized least squares algorithm. Technical report, Computer Science and Artificial Intelligence Laboratory (CSAIL), MIT, 2005.

F. Cucker and S. Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 39:1 49, 2001.

Ernesto De Vito, Sergei V Pereverzyev, and Lorenzo Rosasco. Adaptive kernel methods using the balancing principle. Foundations of Computational Mathematics, 10(4):455 479, 2010.

M.-C. Dinu, M. Holzleitner, M. Beck, D. H. Nguyen, A. Huber, H. Eghbal-zadeh, B. A. Moser, S. V. Pereverzyev, S. Hochreiter, and W. Zellinger. Addressing parameter choice issues in unsupervised domain adaptation by aggregation. International Conference on Learning Representations, 2023.

Richard M Dudley. Cambridge studies in advanced mathematics: Real analysis and probability. 74. Cambridge University Press, 2nd edition, 2002.

Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.

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.

Alexander Goldenshluger and Sergei V Pereverzev. Adaptive estimation of linear functionals in Hilbert scales from indirect white noise observations. Probability Theory and Related Fields, 118(2):169 186, 2000.

Xin Guo, Zheng-Chu Guo, and Lei Shi. Capacity dependent analysis for functional online learning algorithms. ar Xiv preprint ar Xiv:2209.12198, 2022.

Shohei Hido, Yuta Tsuboi, Hisashi Kashima, Masashi Sugiyama, and Takafumi Kanamori. Statistical outlier detection using direct density ratio estimation. Knowledge and Information Systems, 26:309 336, 2011.

Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach to direct importance estimation. The Journal of Machine Learning Research, 10:1391 1445, 2009.

Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. f-divergence estimation and twosample homogeneity test under semiparametric density-ratio models. IEEE Transactions on Information Theory, 58(2):708 720, 2011.

Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. Statistical analysis of kernelbased least-squares density-ratio estimation. Machine Learning, 86(3):335 367, 2012.

Adaptive Learning of Density Ratios in RKHS

Masahiro Kato, Takeshi Teshima, and Junya Honda. Learning from positive and unlabeled data with a selection bias. In International Conference on Learning Representations, 2019.

Amor Keziou and Samuela Leoni-Aubin. Test of homogeneity in semiparametric two-sample density ratio models. Comptes Rendus Math ematique, 340(12):905 910, 2005.

Erich L Lehmann and George Casella. Theory of point estimation. Springer Science & Business Media, 2006.

OV Lepskii. On a problem of adaptive estimation in gaussian white noise. Theory of Probability & Its Applications, 35(3):454 466, 1991.

Shuai Lu and Sergei V Pereverzev. Regularization theory for ill-posed problems. In Regularization Theory for Ill-posed Problems. de Gruyter, 2013.

Shuai Lu, Peter Math e, and Sergei V Pereverzev. Balancing principle in supervised learning for a general regularization scheme. Applied and Computational Harmonic Analysis, 48 (1):123 148, 2020.

Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach, and Alessandro Rudi. Beyond least-squares: Fast rates for regularized empirical risk minimization through selfconcordance. In Conference on Learning Theory, pages 2294 2340. PMLR, 2019.

Peter Math e. The Lepskii principle revisited. Inverse problems, 22(3):L11, 2006.

Aditya Menon and Cheng Soon Ong. Linking losses for density ratio and class-probability estimation. In International Conference on Machine Learning, pages 304 313. PMLR, 2016.

Shakir Mohamed and Balaji Lakshminarayanan. Learning in implicit generative models. ar Xiv preprint ar Xiv:1610.03483, 2016.

Nicole M ucke. Adaptivity for regularized kernel methods by Lepskii s principle. ar Xiv preprint ar Xiv:1804.05433, 2018.

Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 1994.

DH Nguyen, W Zellinger, and S Pereverzyev. On regularized Radon-Nikodym differentiation. RICAM-Report 2023-13, 2023.

Xuan Long Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization. Advances in Neural Information Processing Systems, 20, 2007.

Xuan Long 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.

Zellinger, Kindermann and Pereverzyev

Qichao Que and Mikhail Belkin. Inverse density as an inverse problem: The Fredholm equation approach. Advances in Neural Information Processing Systems, 26, 2013.

Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Advances in Neural Information Processing Systems, 30, 2017.

Bernhard Sch olkopf, Ralf Herbrich, and Alex J Smola. A generalized representer theorem. In International Conference on Computational Learning Theory, pages 416 426. Springer, 2001.

Ingmar Schuster, Mattes Mollenhauer, Stefan Klus, and Krikamol Muandet. Kernel conditional density operators. In International Conference on Artificial Intelligence and Statistics, pages 993 1004. PMLR, 2020.

Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference, 90(2):227 244, 2000.

Alex Smola, Le Song, and Choon Hui Teo. Relative novelty detection. In Artificial Intelligence and Statistics, pages 536 543. PMLR, 2009.

Ingo Steinwart, Don R Hush, Clint Scovel, et al. Optimal rates for regularized least squares regression. In Conference on Learning Theory, pages 79 93, 2009.

Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert M uller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8 (5), 2007.

Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density ratio estimation in machine learning. Cambridge University Press, 2012a.

Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density-ratio matching under the bregman divergence: a unified framework of density-ratio estimation. Annals of the Institute of Statistical Mathematics, 64(5):1009 1044, 2012b.

Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.

Grace Wahba. Spline models for observational data. SIAM, 1990.

Werner Zellinger, Natalia Shepeleva, Marius-Constantin Dinu, Hamid Eghbal-zadeh, Hoan Duc Nguyen, Bernhard Nessler, Sergei Pereverzyev, and Bernhard A Moser. The balancing principle for parameter choice in distance-regularized domain adaptation. Advances in Neural Information Processing Systems, 34, 2021.

Tong Zhang. Effective dimension and generalization of kernel learning. Advances in Neural Information Processing Systems, 15, 2002.