Towards a Unified Analysis of Kernel-based Methods Under Covariate Shift
Authors: Xingdong Feng
Xin HE
Caixing Wang
Chao Wang
Jingnan Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: kernel methods
covariate shift
reproducing kernel Hilbert space (RKHS)

Abstract: Covariate shift occurs prevalently in practice, where the input distributions of the source and target data are substantially different. Despite its practical importance in various learning problems, most of the existing methods only focus on some specific learning tasks and are not well validated theoretically and numerically. To tackle this problem, we propose a unified analysis of general nonparametric methods in a reproducing kernel Hilbert space (RKHS) under covariate shift.  Our theoretical results are established for a general loss belonging to a rich loss function family, which includes many commonly used methods as special cases, such as mean regression, quantile regression, likelihood-based classification, and margin-based classification. Two types of covariate shift problems are the focus of this paper and the sharp convergence rates are established for a general loss function to provide a unified theoretical analysis, which concurs with the optimal results in literature where the squared loss is used. Extensive numerical studies on synthetic and real examples confirm our theoretical findings and further illustrate the effectiveness of our proposed method.

Towards a Unified Analysis of Kernel-based Methods Under Covariate Shift
Xingdong Feng', Xin He', Caixing Wang'; Chao Wang', Jingnan Zhang²
Schooo of Statistics and Management, Shanghai University of Finance and Economics
2 Inteeraational Institute of Finance, School of Management,
University of Science and Technology of China (feng.xte xingdong, he he. xxm.xin11111 / sesaaillluuffeee edu. cn (wang. caixing, wang. chao) Cstu. shufe edu. cn jnzhang@ustc. edu.
Abstract
Covariate shift occurs prevalently in practice, where the input distributions of the source and target data are substantially different. Despite its practical importance various learning problems, most of the existing methods only focus on some specific learning tasks and are not well validated theoretically and numerically. To tackle this problem, propose unified analysis of general nonparametric methods in a reproducing kernel Hilbert space (RKHS) under covariate shift. Our theoretical results are established for a general loss belonging to a rich loss function family, which includes many commonly used methods as special cases, such as mean regression, quantile regression, likelihood- classification, and margin-bass classification. Two types of covariate shift problems are the focus of this paper and the sharp convergence rates established for general loss function to provide a unified theoretical analysis, which concurs with the optimal results in literature where the squared loss is used. Extensive numerical studies synthetic and real examples confirm our theoretical findings and further illustrate the effectiveness of our proposed method.
Introduction
Covariate shift is phenomenon that commonly occurs in machine learning, where the distribution of input features (covariates) changes between the source (or training) and target (or test) data, while the conditional distribution of output values given covariates remains unchanged (Shimodaira 2000
Pan & Yang. 2010). Such a phenomenon is illustrated in Figure where the learned predictive function from the source data may significantly differ from the true function. Thus, the prediction performance can be largely degraded since the predictive function has not been trained on data that accurately represents the target environment. Covariate shift can arise in a variety of domains, including medicine and healthcare (Wei et al.) 2015) Hajiramezanali et al. 2018). remote sensing
(Tuia et al. (20TT), and natural language and speech processing (Yamada al. 2009 Fei Liu 2015). Various factors contribute to covariate shift, such as data sampling bias (c.g., patient demographics healthcare applications), changes in the studied population (c.g., vocabulary evolution in natural language processing), or measurement and observational errors (c.g., sensor noise or calibration errors the sensor domain). Compared to the well well-studied supervised learning without such a distribution mismatch (Györfi et al., 22022), there still exists some gap in both theoretically and numerically understanding the influence of the covariate shift under various kernel-based learning problems.
"Caixing Wang is the corresponding author and all the authors contributed equally to this paper and their names are listed in alphabetical ordering.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This paper provides unified analysis of the kernel-based methods under covariate shift. Moreover, a general loss function is considered, which is allowed belong rich loss function family and thus includes many commonly used methods regression, likelihood-basel classification, and margin-based classification. This paper considers two types of covariate shift problems in which the importance ratio is assumed to be uniformly bounded or to have a bounded second moment. A unified theoretical analysis has been provided that the sharp convergence rates are established for general loss function under two evaluation metrics, which concurs with the optimal results in Ma et al. (2023) where the squared loss is used. Our theoretical findings also validated by variety of synthetic and real-life examples.
special cases, such as mean regression, quantile
24
Targr
Jours
Leared fon
Target
23
01
(a)
(b)
Figure 1: (a) The probability density functions of normal distributions with μa = 0, o² = 0.4 that the source data is driven from and μu 1.5, o² = 0.6 that the target data is driven from, respectively; (b) the learned function trained by using the source data and the true mean regression function. Note that the considered example serves as an illustration that satisfies case (ii) in Section 2.3
Our contributions. The contributions of this paper are multi-fold. We propose unified analysis of the kernel-based methods under covariate shift, which provides an insightful understanding of the influences of covariate shift on the kernel-based methods both theoretically and numerically. By utilizing empirical process in learning theory, we investigate the theoretical behaviors of several estimators under various conditions. with particular emphasis on different importance ratio cases between the source and target distributions. Specifically, we show that the unweighted estimator achieves the optimal learning rates in terms of both C and the excess risk with respect to the target distribution under the uniformly bounded case. Yet, the unweighted estimator is sub- optimal under the bounded second moment case. Then, we construct weighted estimator by using an appropriate truncated ratio, which again attains sharp convergence rate. Unlike kernel ridge regression (KRR), the estimator for the general loss does not have an explicit form, making many classical analysis techniques inapplicable (Lian) 2022) and in our technical proofs, the theoretical derivation is much more involved due to the considered general loss function. Numerous experiments synthetic data and multi-source real data with various loss functions confirm theoretical findings. To some extent, this paper provides a comprehensive study of the numerical performance of the kernel-based methods under various scenarios with covariate shift.
Related work. Some most related works including covariate shift adaptation and importance ratio estimation are presented below.
Covariate shift adaptation. (Shimodaira (2000) investigates the impact of covariate shift in para- metric regression with maximum likelihood estimation and proposes an importance-weightng (IW) estimator, which has a significant improvement when the misspecification does exist. (Sugiyama & Müller (2005b) further extend this work by analyzing an unbiased estimator for -e-error. These fundamental works also motivate variety of follow-up studies under the parametric setting Sugiyama & Storkey (2006): Yamazaki et al. (2007); WWnn et al. (2014); Lei et al. (2021). Beyond the parametric setting, Kpotule& & Martinet (2021) consider the nonparametric classification problem and provide new minimax result that concisely captures the relative benefits of source and target labeled data under covariate shift. Focusing on the Hölder continuous regression function class, [Pathak et al.) (2022) propose new measure of distribution mismatch between the source and target distributions. Ma et al. (2023) and Gogolashvili et al. (2023) establish the optimal learning rates for KRR over RKHS. Recently, covariate shift in overparameterized models, such as high-dimensional models and neural networks, has also drawn tremendous attention from relevant researchers (Hendrycks
Dietterich 2019 Byrd & Lipton| 2019 Hendrycks et al. 2021 Tripuraneni et al. 2021).

---

Importance ratio estimation. A straightforward approach to estimating the importance ratio is separately estimating the source and target densities by kernel density estimation (Sugiyama & Müller 2005a Baktaahmotlagh et al. 2014) and then computing the ratio. In practice, it is more efficient to directly estimate the importance ratio by minimizing some discrepancy measures between distributions, including kernel mean matching (Huang et al., 2006) Gretton et al. 2209), Kullback-
Leibler divergence (Sugiyama et al. 2007a 2012) and non-negative Bregman divergence (Kato & Teshima 2021).
Notation. In this paper, we use to denote a universal constant that may vary from line line. For two sequence On and bn, we say x b, if and only if an (b,,) and b O(ax) hold.
2 Problem formulation
2.1 Learning within rich family of loss functions
Suppose that the random pair (x, y) is drawn from some unknown distribution Px, with
(f1,-..,Typ) E X, where X' R2 is compact support and y y C R. In the literature of machine learning, the true target function f is often defined as the minimizer of the expected risk with pre-specified loss function -(--)) : x R + R that
== argmin, (f) = argmin, F. [T((
Throughout this paper. we consider a general loss function belonging to a rich loss function family that
L (yy.) is assumed to be convex and locally сr. Cr.-Lipschitz continuous (Wainwright, 2019 Dasgupta
et al. 2019), that is for some V 2 0, there exists constant cr. > such that [T,y, w) L (yyww) w')l S
cz wi| holds for all pairs w, w/ E [-V, VJ and E Y. A variety of popularly used loss functions satisfy these two conditions, including
Squared loss: L(y. f(x) = (y f(x))² with cr 2 (Mg V), for any lvl I My with constant M, > 0;
Check loss: L(y, f(x) = (y (xx)) (T 4uSS((0)) with et = 1 and quantile level r;
Huber loss: [(v.((x)) = - (x))) if by [(x) S 5, - s(x) - 1 otherwise,
with ez. Ōō;
Logistic loss: T(y: / (x)) log(1 + expl y (x) /lgg with ez (log 2)og2)-Le) /(1
e" e²);
with Hinge loss: L(y. = (1 - -f with ez = 1.
Note that the explicit form of fr may differ from one loss another. For example, for the squared loss, (x) = E'y/ x]; for the check loss, fx( = Qy(y) x) with Q, (yl x) = inf P(Y < u|x) 2 r: for the hinge loss, f sign P(y = = - 1/2) with sign(-) denoting the sign function. Moreover, we require f E Hxx where Hx denotes the RKHS induced by pre-specified kernel function ((:-)) X x X + R. In practice, one of the most important tasks in machine learning is to learn f from the source data and use the estimated predictive function f for prediction in the target data.
2.2 Measurement under source and target distributions
Classical learning problems often explicitly or implicitly assume that the source and target data are drawn from the same distribution. Precisely, the source data comes from a joint distribution Ps Ps x PS where Py) x is the conditional distribution and PS is the input distribution with density function E Then, the performance of the estimated predictive function ʃ is usually evaluated by the L (2(P))-erro or the excess risk error with respect to Ps that
11 Fxx-s [[(x)[ ['(x)) E (( Fis ((.. I(y, I (x))]
where Fix-. and Ess are the expectation over P5 and Ps conditioning on the observed data, re- spectively. When covariate shift occurs, the target data may come from some totally different joint
3

---

distribution Pr = p x in the sense that although pyl representing the regression or classifica- tion rule remains invariant, P differs significantly from Px We also assume that P has density function P Obviously, it is reasonable to evaluate f under Pr instead of Ps. Then, our primary interest is the (Px)) ) eeroor or the excess risk error with respect to Pr that
f = Ex-T f(x)) Et( - - = [L f(x)) - L(v. fx))],
where Ex-T and Er are the expectation over P and Pr conditioning on the observed data, respectively. the rest of this paper, I defined as the optimal function under the target distribution such that f argming E [T [(x))
2.3 Kernel-based estimation under covariate shift and importance ratio correction
Suppose that random sample 2 = {(x5 -,,,,,) ) are i.id. drawn from the source distribution Ps. We consider the classical nonparametric estimation problem in RKHS (Vapnik 1999) that
1 = argmin -
Σ M ((x))) + A|l/IR
(2)
fEHK n
1=1
where À is the regularization parameter. Without covariate shift, the first term on the right side of (2) is unbiased estimator of (f). However, it becomes biased when covariate shift occurs, and thus may lead to inaccurate predictive estimator. To tackle this issue, we consider the importance
ratio measuring the discrepancy between distributions that is Φ(x) (x) p (x), for any E X, and we notice that f L(y. (x)) (x)dP,) yd = [] ( f(x)) (x)dP,, dx. Inspired by this, the weighted version of (2) can be used, which leads to importance ratio weighted (IRW) estimator that
R Σ LV. + AISII.. SEHK Y
J = argmin
(3)
Throughout this paper, focus two types of the importance ratio that
(xx) is a-uniformly bounded that is supxex ((x) S a, for some positive constant or;
(ii) 6xx)'s 's second moment is bounded that is Ex~s (x)] < 6,, for some constant B² 2 1.
Note that case (i) reduces to the classical case without covariate shift if = Yet, the bounded case is somewhat restrictive, and much weaker condition is considered in case (ii). It is also clear that case (i) can be regarded as a special case of case (ii) by taking 8² a. To see this, we have
Fxxs(((x))] Fx [x(x) < a. It is interesting to notice that these two cases are related to Rényi divergence (Rényi 1961) between Φ and px Specifically, the conditions cases (i) and (ii) are equivalent to requiring Dxo (p* || () and D2(0E [(]]) being bounded (Cortes et al. 2010).
respectively. Moreover, as pointed out by Ma et al. (2023). 3). (3) may result significant inflation of the variance, largely due to the unbounded importance ratio. Thus, it is natural to consider truncated
importance ratio with a pre-specified threshold value Yn > (Ma et al. 2023 Gogolashvili et al. 2023). Precisely, consider the following truncation
Sn (x) := min {o(x),
Accordingly, the following truncated important ratio weighted (TIRW) estimator is considered that
argmin
(x ( f(x²)) + Allf1
(4)
jEHx
where the theoretical suggestion of the choice of 7n is provided in Section
3 Main results
In this section, we provide unified theoretical analysis of the unweighted estimator in (2) and the TIRW estimator in 4 under two types of importance ratio. Let H. denote the RKHS induced by

---

symmetric, continuous, and positive semi-definite kernel function (,,-): : x x X + R. Under some regularity conditions, Mercer's theorem (Mereer 1909) guarantees that K has an eigen-expansion of the form
K(x,x') E (x)م
where {ughي21 are the eigenvalues and (1/3 are the orthonormal eigenfunctions of (X, {s fxx p (x)dx < so}. We expand the kernel in L P2) for deriving bounds under the target distribution. For any HK. we have f Σ}=1 ay4; with aj fx f())(,,
(x)xx)x(x)))))) (x) (x)dx and the RKHS-norm is ||ʃl = Ej=13 03/13 < C0. The kernel complexity function of Hk is
then given as R(6) V n Σー= min(0², )= In literature, R(6) is important to quantify the localized Rademacher complexity of Hx. which helps to build tight bounds in kernel-basce methods [Mendelson] 2002 Koltchinskii & Yuan 2010). For theoretical simplicity. we assume [|.f' in the rest of this paper, which is commonly considered in machine learning literature (Yang et al.
2017 Li al. 202I). The following technical assumptions are required for the theoretical analysis. analysis..
Assumption 1: There exists some constant A > O such that suPxEx K(x,x, x)] < K, and the eigenfunctions (15))22
uniformly bounded such that supxex [x0y(x)] I for all j 1.
Assumption 2: For some sufficiently small constant u > 0, we assume Es [L f(x))
E, [L (y, (x))] > co - holds with some constant co > 0, for all - S u, where TE (S.))
Assumption imposes a boundedness condition on the kernel function and its corresponding eigen- functions, which is commonly considered in the literature and satisfied by many popularly used kernel functions with the compact support condition (Smalc & Zhou| 2007 Steinwart et al. 2009 Mendelson & Neeman 2010). Assumption 2 is a local co-Strong convexity condition of the expected loss function with respect to (X, PS) and (Xx Px at f" Similar assumptions are also con- sidered by (Steinwart& & Christmann (2008); ; Wainwright (2019): Li et al. (2021); Lian (202)). Note that many popularly used loss functions, including squared loss, check loss, Huber loss, logistic loss, and hinge loss, satisfy this assumption. More detailed discussions on Assumption 2 are deferred to Section A.7 of the supplementary material.
3.1 Convergence rate for the uniformly bounded case
We begin to establish the convergence rate of the unweighted estimator f under the uniformly bounded case with covariate shift.
Theorem Under Assumptions 1-2, if the importance ratio is a-uniformly bounded, let X > 8 /4 with 8n being the smallest positive solution to C' C'Vlog nogg /a6) S cg5² /2, then for some constant
Ci > 0, with probability at least 1 - n 51, we have
If f 12 (8% 225 2c
(5)
Furthermore, based on ()) we have
(tt cra 22, 1/2
(6)
Note that the existence and uniqueness of 6, in Theorem is guaranteed for any kernel class (Bartlett
ct al. 2005). To facilitate the comprehension of Theorem [ we define an index as d(6) = min 2
1 8 for given target error level 5 0. It is known that the kernel with eigenvalues satisfying d)=d(()+ M4 I Cd(5)5² is referred to as the regular kernel class (Yang et al. 2017). From the definition of d(ō) and regular kernel, we can get that Σラn min(62, = d())82, thus the inequality Colog nigg ((vā)) < co02/2 /2 in Theorem can be directly simplified Va log ndl Van)/n S Cō under the assumption that [] = 1. Consequently, we can rewrite (5) as
that Dc
lf - 1 s Ca(82 + log n
d( d(vao)).
5

---

where 8 satisfies a log d( (5)) S C8 and À = 8² (see Section C.4 of the supplementary material for the detailed proof). The bound in 7 controls a type of blas-variance tradeoff by the choice of and hence A. Under the uniformly bounded case. Ma et al. (023) has established minimax rate of
the order a 8s0 {82 + = } for the squared loss function. It is worthnoting that the result in (7) can also attain this lower bound up to logarithmic factor under some weaker conditions. Particularly, the assumption of Ma et al. (2023) that the noise terms are uub-Gaussian is no longer needed in ( Although the convergence rate of 6 is sub-optimal for general loss function L considered in Section 2.1 it becomes optimal at the rate of c6 (6% 2c7 >) if the following assumption holds.
Assumption 3: For some sufficiently small constant u > 0, we assume Er [L f(x)] ET [L f & c llf f'1 holds with some constant ca > co > 0, for all || fl S u.
In fact, Assumption 3 a mild condition that can be satisfied by many commonly used losses. For instance, for the squared loss, the equality always holds with of 1; for the check loss, Assumption 3 is satisfied if the conditional density of the noise term is uniformly bounded (Zhang et al., 2021 Lian 2022). Moreover, the regular kernel class includes kernels with either finite rank (i.e.. linear or pol polynomial kernels), polynomially decayed eigenvalues (i.e., Sobolev kernels), or exponentially decayed eigenvalues (i.e., Gaussian kernels). Corollary provides the convergence rate of f over these three specific kernel classes.
Corollary 1. Under Assumptions 1-3, if the kernel has a finite rank D, and let À C Dlgn then with probability at least 1 =1, we have
--- e((r") SC C Doog
(8)
12
and if the eigenvalues of the kernel decay polynomially such as μjj S Cj-2 with some constant 2r
r > f/2 j = 1, ...,,, and let x = Ca
log ) 2r then with probability at least 1 - n "
we have
a
22"ogg log
n
and if eigenvalues of the kernel decay exponentially such as J4y x e
CJ logs and let X C log
then with probubility at least 1 - n 61,
=1, we have
a² loloog" n C S
-F- -
(()) S
(10)
n
Note that these bounds in (0) reduce the known minimax lower bounds Yang et al. 2017) for the squared loss without covariate shift (i.e., a = 1). As the uniform boundedness implies the boundedness of the second moment, the convergence rate of the TIRW estimator f for the uniformly bounded case is similar Theorem in the next section by replacing a with 8².
3.2 Convergence rate for the second moment bounded case
The optimality for the a-uniformly bounded importance ratio condition relies the inequality that f 1 I all 1". Yet, such a desired relation is not guaranteed for the second moment bounded case. Theorem
2 shows that the unweighted estimator ff is still consistent, but not optimal. Theorem 2. Under Assumptions 1-2, if the importance ratio satisfies that Fxxss ( I f32 let X > cod2 /4 with &n being the smallest positive solution to C CVVlonnR(ee -1 teereer / 3228)2/2) < co /2, then for some constant 02 > 0, with probubility at least 1 n -2, we have
IIf - 1 CLC B2
(62 + 20g 12) 1/2
(11)
Furthermore, based on
we have
12)1/2 1/2 -(0)))(()) < e2 CLV 8 (6, 200 22)'2)
(12)
6

---

To see the bound in 1II is sub-optimal, we consider the kernel with finite rank D, we can show that 6n V log" " y1/s, and if take À 1 log n ya/3, the unweighted estimator satisfies " that |1f 1 Op(( ( D l )1/3), which is far from the optimal rate (see Section C.4 of the a
"
supplementary material for examples of finite rank, polynomially and exponentially decay kernel classes). To deal with the sub-optimality, Eslo(x)L(y) f(x)) = Er fx))). The following theorem shows that the TIRW estimator f can again reach a sharp convergence rate up to logarithmic factors under some mild conditions.
consider the importance ratio correction ensuring that
Theorem 3. Under Assumptions 1-2, if the importance ratio satisfies that Ex [xx=s(²((x) (x)] S B², ler
2 with on being the smallest positive solution to C C log (R(() S cy62/2 and set the
truncation level " = nnB2, then for some constant C3 > O, with probability at least 1 - n= we have
11F - 17 S 6n + 2c7 X.
(13)
Furthermore, based on we have
-) - E -
1 _co6 22.
(14)
Similar to when dealing with regular kernel classes, the bounds in 13 and (14) become
11
S c(6" + 32
log"
n d())
(15)
where 5 is any solution of 33 d(6) - C82 and A x 82. Since the second moment boundedness
can be implied by the uniform boundedness, it can be concluded that f also reaches the minimax lower bound for the square loss up to logarithmic factors (with a substituted by 82). For three specific kernel classes, we also have the following Corollary for the TIRW estimator fo.
Corollary Under Assumptions 1-2, if the kernel has a finite rank D, and let X C then with probability at least 1 c3, we have
S C DDgg
(16)
and the eigenvalues of the kernel decay polynomially such as μ1j S Cjj with a constant 1/2 for j 1.2...., and let X C( 882 log n 2041, then with probability at least 1 n- Sa we have
[32 (32log"
IF4
1 f x Ef SC
(17)
and if the eigenvalues of the kernel decay exponentially such as U X e Cjlos,, and let = C 3d log" then with probability at least 1 cs, we have
32 log"
- - et Ef(s) S C
(18)
n
For easy reference, we summarize some important theoretical results that have been established by us in table
Table 1: Established convergence rates under different cases
Uniformly bounded case
Moment bounded case
Kernel class
Unweighted estimator
TIRW estimator
Unweighted estimator
TIRW estimator
Finite rank 1)
Op( a DDlan n
Op( Dlgg
Op(( ( (
Op( 8 Dly? 2
Polynomial decay
(p(( loge bioly
Op(( 2pm
Op(( logn
Op(( log
Exponential decay
Op 10o22
Op( 2
Op(( (0
Op( (2
7

---

4 Numerical experiments
In this section, validate theoretical analyses by performing numerical experiments on both synthetic data and real applications. To estimate the importance ratios, we apply the Kullback-Leibler importance estimation procedure (KLIEP) (Sugiyama et al., 2007b), and the estimation details are provided in the supplementary material. For brevity, we only report the performance of kernel-based quantile regression (KQR) where the check loss is used in synthetic data analysis, and the performance of kernel support vector support machine (KSVM) with hinge loss in the real data analysis; completed results for other loss functions as well as the detailed settings and results for the other examples, including for the multi-dimensional cases, can be found in Section A of the supplementary material. In our experiments, we consider the RKHS induced by Gaussian kernel in all the examples, and all the experiments are replicated 100 times in the synthetic data analysis.
4.1 Synthetic data analysis
We investigate the performance of KQR under covariate shift with the following generating model
y = f + (1+ (x- 0.5)² o(s - (T)(,),,
where fo( sin(TT)) with E R. & denotes the CDF function of the standard normal distribution and E ~ (0, 1). We consider 2 ~ N Nu1, of) and p ~ N N(ug ož) with μr = 0. of = 0.4, U2g = 0.5, o3 = 0.3 for the uniformly bounded case and μ1 0 = 0.3. #2 1, 0 = 0.5 for the moment bounded case, respectively. Moreover, we set r = 0 and σ = 0.5 for the homoscedastic case, and r r= 1 and ø 0.3 for the heteroscedastic case, respectively. Note that the simulation results for the case that T = 0.3 and r = 1 are presented in Figure [under the uniformly bounded case and 3 under the moment bounded case; completed results for other cases are provided in the supplementary material. We compare the averaged mean square error (MSF) and empirical excess risk of the unweighted estimator and weighted estimator, either with true estimated weights across different choices of regularization parameter X, source sample size n,, and target sample size m.
in Figure
9.45
way't
ROC
1.20
3.00
3.00
33:8
6:10
2.00
600
logio
(a)
(b)
(c)
013
Emarigme Ag0
0.00
0.75
2.00
100
(d)
(I)
Figure 2: Averaged MSE and empirical excess risk for unweighted KQR, TIRW KQR with true weight and estimated weight, respectively. Note that in (a) and (d), the curves are plotted with respect to log À with 500, m 1000; in (b) and (e) the curves are plotted with respect n with fixed m 1000, A 10 4; in (c) and (f), the curves are plotted with respect to m with fixed n 500, x 10-4
From (a) and (d) in Figure 2 we can conclude that the error of the unweighted estimator is very close to that of the weighted estimator for the uniformly bounded case, which is consistent with our theoretical findings in Section 3 For the moment bounded case as demonstrated in (a) and (d) of Figure the weighted estimator consistently outperforms its unweighted counterpart for all choices of X. Even when À is far from its optimal choice, the weighted estimator still maintains lower
8

---

IRA F
1x
100
200
2024
300
150
200
350
380
(b)
wight
Titsk von Primnnt warpt
loguA
80 600 200 300 400
200
200
(d)
(f)
Figure 3: Averaged MSE and empirical excess risk for unweighted KQR, TIRW KQR with true weight and estimated weight, respectively. Note that in (a) and (d), the curves are plotted with respect log with n 500, m 1000; in (b) and (e) the curves are plotted with respect to a with fixed m 1000, 10-4; (c) and (f), the curves are plotted with respect to m with fixed n = 500, A = =110 10"
error level with significant improvement over the unweighted estimator whose error is on occasion extremely high for small choices of X. Additionally, it is clear from Panels (b) and (e) of Figures 2 and that in the moment bounded case, the error curves for the unweighted estimator have some significant gaps with those of the weighted estimator, while in the bounded case, these curves tend to coincide grows. It is also clear from the table that the trends in Figure 2 (b)-(c) and Figure 3 (b)-(e) almost agree with the explicit convergence rate where the Gaussian kernel with exponential decay is used. This phenomenon is consistent with our theoretical conclusion that the unweighted estimator can only achieve sub-optimal rates when the importance ratio is moment bounded and attain optimal rates when uniformly bounded. Finally, note that the target sample size has subtle influence on all the estimators, as demonstrated in Panels (c) and (f) of Figures and 3
4.2 Real case study
We consider the binary classification problem on the Raisin dataset, which is available in https //rrchive. ics. uci uci.edu/mm edu/ml/ ml/datasets. phpp The dataset contains 900 instances and 7 attributes. After standardization, the data are first randomly split into source and target datasets. We introduce a binary random variable s that serves as a labeling indicator and assign it to the source dataset if s = 0. To ensure that the conditional distribution of different datasets remains invariant, we require s to be conditionally independent with the response y given the covariate x (Zadrozny) 2004)] Quinonero-Cander et al. (2008). We implement KSVM in which the covariate shift only exists in the first covariate. Specifically, for E >> O, we conduct the splitting rule as P(s; = 1 x,) = min(1, (z /e), where 0i,0 is the first element of x; and min; ( We refer to E as the shift level that a smaller value of e favors a greater distinction between source and target datasets. We set the turning parameter C2= (nd)=1 For the TIRW estimator,
importance weighted cross
validation (IWCV) (Sugiyama et al. 2007a) to tune the truncation parameter 7n. We refer to Section A in the supplementary material for the details of the adopted method.
Figure 4 summarizess the accuracy rate and standard error in different settings. As shown in this figure, the unweighted estimator has poor performance on target data, even for the optimal choice of C), Nevertheless, the weighted estimator has a significant improvement in performance. Surprisingly, the weighted estimator is relatively stable with respect to the choices of Cx, which is consistent with our results on synthetic data, Moreover, we can find that a proper truncation slightly improves the accuracy rate of the weighted estimator while reducing its variation.

---

8
(b) 8
(c) 10
Figure 4: Averaged accuracy rate for unweighted KSVM, IRW KSVM and TIRW KSVM with different shift levels respectively.
Conclusion
In this work, we propose unified analyzing framework for kernel-based methods under covariate shift and show that the predictive function can be better estimated by using the distribution infor- mation of the covariates from both aspects of theory and numerical performance. The established theoretical results fulfill the gap in understanding the influence the covariate shift under various kernel-based learning problems, both researchers and practitioners may benefit from our theoretical findings. Extensive numerical studies also provide empirical evidence and confirm the established theoretical results. Note that it is very interesting to test if there exists distribution shift in practical applications and if the distribution shift satisfies the uniformly bounded or moment bounded assump- tions. Unfortunately, the relevant approaches have remained lacking to our best knowledge. And it is interesting to note that as shown in our real applications, the TIRW estimator always outperforms the unweighted estimator, and thus we suggest using the TIRW estimator to analyze the real-life dataset. Moreover, in the theory, we directly use the true importance ratio, and it difficult to derive the consistency of the estimated ratio and plug it into our theoretical analysis. In the machine learning literature, there exist several measures to quantify the divergence between two distributions, including but not limited f-divergence, Wasserstein distance and kernel mean matching. still an open problem if still works when we use other measures rather than the importance ratio. We leave such promising and interesting topics as potential future work.
Acknowledgment
Xingdong Feng's research is supported in part by NSFC-12371270 and Shanghai Science and Technol- ogy Development Funds (23JC1402100) Xin He's research supported in part by ASFC-1190137, and Program for Innovative Research Team of Shanghai University of Finance and Economics. This research is also supported by Shanghai Research Center for Data Science and Decision Technology and the Fundamental Research Funds for the Central Universities.
References
Baktashmotlagh. M., Harandi, M. T., Lovell, B. C., & Salzmann, M. (2014). Domain adaptation on the statistical manifold. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (pp. 2481-2488).
Bartlett, L., Bousquet, O., & Mendelson, S. (2005) Local rademacher complexities. The Annals of Statistics, 33, 1497-1537.
Byrd, J., & Lipton, Z. (2019). What is the effect of importance weighting in deep learning? In Proceedings of the 36th International Conference on Machine Learning (pp. 872-881), PMLR volume 97.
Cortes, C., Mansour, Y., & Mohri, M. (2010). Learning bounds for importance weighting. Advances in Neural Information Processing Systems, 23,
Dasgupta, S., Goldberg, Y., & Kosorok, M. R. (2019). Feature elimination in kernel machines in moderately high dimensions. The Annals of Statistics, 47, 497-526.
10

---

Fei, G., & Liu, B. (2015). Social media text classification under negative covariate shift. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (pp. 2347-2356).
Gogolashvili, D., Zecchin, M., Kanagawa, M., Kountouris, M., & Filippone, M. (2023). When is importance weighting correction needed for covariate shift adaptation? arXiv preprint arXiv:2303.04020..
Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., & Schölkopf, B. (2009). Covariate shift by kernel mean matching. Dataset Shift in Machine Learning, 3, 131-160.
Györfi, L., Köhler, M., Krzyžak, A., & Walk, H. (2002). A distribution-free theory of nonparametric regression volume Springer.
Hajiramezanali, E., Zamani Dadaneh, S., Karbalayghareh, A., Zhou, M., & Qian, X. (2018). Bayesian multi-domain learning for cancer subtype discovery from next-generation sequencing count data. Advances in Neural Information Processing Systems, 31.
Hendrycks, D., Basart, S., Mu, N., Kadavath, S., Wang, F., Dorundo, E., Desai, R., Zhu, T., Parajuli, S., Guo, M. et al. (2021). The many faces of robustness: critical analysis of -fittr-distritttinn generalization. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 8340-8349).
Hendrycks, D., & Dietterich, T. (2019). Benchmarking neural network robustness to common corruptions and perturbations. arXiv preprint arXiv: 12061.
Huang, J., Gretton, A.. Borgwardt, K., Schölkopf. B.. & Smola, A. (2006). Correcting sample selection bias by unlabeled data. Advances in Neural Information Processing Systems, 19, 601- 608.
Kato, M., & Teshima, T. (2021). Non-negative Bregman divergence minimization for deep direct density ratio estimation. In Proceedings of the 38th International Conference Machine Learning 5pp.5320-53333 PMLR volume 139.
Koltchinskii, V., & Yuan, M. (2010). Sparsity in multiple kernel learning. The Annals of Statistics, 38, 3660-3695.
Kpotufe, S., & Martinet, G. (2021). Marginal singularity and the benefits of labels in covariate-shift. The Annals of Statistics, 49, 3299-3323,
Lei, Q., Hu, W. & Lee, J. (2021). Near-optimal linear regression under distribution shift. In Proceedings of the 38th International Conference on Machine Learning (pp. 6164-6174). PMLR volume 139.
Li, Z., Ton, J.-F., Oglic, D., & Sejdinovic, D. (2021). Towards unified analysis of random fourier features. Journal of Machine Learning Research, 22, 4887-4937.
Lian, H. (2022). Distributed learning of conditional quantiles in the reproducing kernel Hilbert space. Advances in Neural Information Processing Systems, 35, 11686-11696.
Ma, C., Pathak, R., & Wainwright, M. J. (2023). Optimally tackling covariate shift in rkhs-based nonparametric regression. The Annals of Statistics, in press, 1-38.
Mendelson, S. (2002). Geometric parameters of kernel machines. In Computational Learning Theory: 15th Annual Conference on Computational Learning Theory (pp. 29-43)
Mendelson, S., & Neeman, J. (2010). Regularization in kernel learning. The Annals of Statistics, 38, 526-565.
Mercer, J. (1909). Functions of positive and negative type and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society A, 209, 415-446.
Pan, S. J., & Yang, Q. (2010). A survey on transfer learning. IEFE Transactions on Knowledge and Data Engineering, 22, 1345-1359.

---

Pathak, R., Ma, C., & Wainwright, M. (2022). A new similarity measure for covariate shift with applications to nonparametric regression. In Proceedings of the 39th International Conference on Machine Learning (pp. 17517-17530). PMLR volume 162.
Quinonero-Candela. J., Sugiyama, M., Schwaighofer, A., & Lawrence, (2008). Dataset shift in machine learning. Mit Press.
Rényi, A. (1961). On measures entropy and information. Proceedings of the Fourth Berkeley Symposium Mathematical Statistics and Probability (pp. 547-562). volume 4.
Shimodaira, H. (2000). Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal Statistical Planning and Inference, 90, 227-244.
Smale, S., & Zhou, D. (2007). Learning theory estimates via integral operators and their approxima- tions. Constructive Approximation, 26, 153-172.
Steinwart, I., & Christmann, A. (2008). Support vector machines. Springer Science & Business Media.
Steinwart, I., Scovel, C., & Hush, D. R. (2009). Optimal rates for regularized least squares regression. In Proceedings of the Annual Conference on Learning Theory, 2009 (pp. 79-93).
Sugiyama, M., Krauledat, M., & Müller, K.-R. (2007a). Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 985-1005.
Sugiyama, M., & Müller, K.-R. (2005a). Input-dependent estimation of generalization error under covariate shift. Statistics Decisions, 23, 249-279.
Sugiyama, M., & Müller, K.-R. (2005b). Model selection under covariate shift. In Proceedings of the 15th International Conference on Artificial Neural Networks: Formal Models and Their Applications- Volume Part II (pp. 235-23 235-240).
Sugiyama, M., Nakajima, S., Kashima, H., Buenau, P., & Kawanabe, M. (2007b). Direct importance estimation with model selection and its application covariate shift adaptation. Advances in Neural Information Processing Systems, 20, 1433-1440.
Sugiyama, M., Storkey, J. (2006). Mixture regression for covariate shift. Advances Neural Information Processing Systems, 19, 1337-1344.
Sugiyama, M., Suzuki, T., Kanamori, T. (2012). Density-ratio matching under the Bregman divergence: unified framework of density-ratio estimation. Annals of the Institute of Statistical Mathematics, 64, 1009-1044.
Tripuraneni, N., Adlam, B., & Pennington, J. (2021). Overparameterrizaion improves robustness to covariate shift in high dimensions. Advances in Neural Information Processing Systems, 34, 13883-13897.
Tuia, D., Pasolli, E., & Emery, W. J. (2011). Using active learning to adapt remote sensing image classifiers. Remote Sensing of Environment, 115, 2232-2242.
Vapnik, V. (1999). The nature of statistical learning theory. Springer Science & Business Media.
Wainwright, M. (2019). High-dimensional statistics: A non-asymplotic viewpoint volume 48. Cambridge University Press.
Wei, D.. Ramamurthy, K. N., Varshney, K. R. (2015). Health insurance market risk assessment: Covariate shift and k-anonymity, In Proceedings of the 2015 SIAM International Conference on Data Mining (pp. 226-234). SIAM.
Wen, J., Yu, C.-N., & Greiner, R. (2014). Robust learning under uncertain test distributions: Relating covariate shift to model misspecification. In Proceedings of the s International Conference on Machine Learning (pp. 631-639). PMLR volume 32.
12

---

Yamada, M., Sugiyama, M., & Matsui, T. (2009). Covariate shift adaptation for semi-supert supervsee speaker identification. In 2009 IEEE International Conference on Acousties, Speech and Signal Processing (pp. 1661-1664). IEEE.
Yamazaki, K., Kawanabe, M., Watanabe, S., Sugiyama, M., & Müller, K.-R. (2007). Asymptotic Bayesian generalization error when training and test distributions are different. In Proceedings of the 24th International Conference on Machine Learning (pp. 1079-1086).
Yang, Y., Pilanci, M., & Wainwright, M. J. (2017). Randomized sketches for kernels: Fast and optimal nonparametric regression. The Annals of Statistics, 45, 991 1023.
Zadrozny, B. (2004). Learning and evaluating classifiers under sample selection bias. In Proceedings of the 21th International Conference on Machine Learning (pp. 903-910).
Zhang, F., Li, R., Lian, H. (2021). Approximate nonparametric quantile regression in reproducing kernel Hilbert spaces via random projection. Information Sciences, 547, 244-254.
13


Reviews:
[{"review_id": "JuLU2S9Y6Q", "reviewer": "Reviewer_bSPk", "summary": "This paper studies the generalization guarantees of non-parameteric methods in RKHS under covariate shift.\nCompared to previous work (Ma et al. AOS2023), the authors extend their results from the squared loss to general Lipchitz loss functions.\nThe derived results show that\n\n- under the uniformly bounded case for the importantce ratio, the unweighted estimator achieves the optimal learning rates in the $L2(d PT)$ space, where $PT$ is the target distribution. \n- under the bounded second monment case, the above estimator is sub-optimal.\n- under a truncated ratio, a sharp learning rate can be achieved.\n", "questions": "- Why does $\\phi_n(x_i) \\leq \\phi(x_i)$ hold in line 193?\n\n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- generalization analysis under covariate shift is derived from the squared loss to general loss functions\n- Under the the uniformly bounded case and bounded second moment case for the importantce ratio, the results can recover the result under the squared loss\n- the results are derived under the truncated case", "weaknesses": "- Extension from the squared loss to general Lipschitz loss functions is based on Assumption 2. More discussion on this assumption is required for specific loss functions. If the space is limited, the discussion can be deferred to the appendix.\n\n- There are several parts unclear in the proof. For example,  in the proof of Lemma C.1.2, the notations $P_n$ and $P$ are undefined in Eq.(2), and more details are needed for the first inequality in Eq. (2). \n\n- The proof idea and structure is almost the same as (Ma et al. 2023). For example, there is no significant difference between the proof of Theorem 3 and Lemma 2 in (Ma et al. 2023). This is because, under Assumption 2 and Eq. (10), the results under Lipschitz loss functions can be well controlled. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review of our paper and the valuable feedback you provided. We have carefully considered your comments and have made significant efforts to address each of your concerns.\n\n**weakness 1**\n\nThanks a lot for your precious suggestion. Detailed discussions on Assumption 2 for specific loss functions have been added at the very beginning of the Appendix in the revised version. Precisely, recall that Assumption 2 is a local $c_0$-strongly convexity condition on the expected loss function with respect to $\\mathcal{L}^2(\\mathcal{X},P^S_x)$ and $\\mathcal{L}^2(\\mathcal{X},P^T_x)$ at $f^*$. So verifying Assumption 2 is equivalent to verifying the local $c_0$ strongly convexity of the loss function. Here are some examples: for the squared loss $L(y,f(\\mathbf{x}))=(y-f(\\mathbf{x}))^2$, note that for any $y \\in \\mathcal{R}$, the function $z \\rightarrow (y-z)^2$ is strongly convex with parameter $c_0=1$, so $f \\rightarrow L(y,f(\\mathbf{x}))$ satisfies the condition in Assumption 2 with $c_0=1$.  For the Huber loss ${L}(y, f(\\mathbf{x}))=(y-f(\\mathbf{x}))^2$, if $|y-f(\\mathbf{x})| \\leq \\delta; \\delta|y-f(\\mathbf{x})|-\\frac{1}{2} \\delta^2$, otherwise, since this loss function is locally equivalent to the squared loss, so it is locally strongly convex under mild tail condition on $y-f^*(\\mathbf{x})$. For the check loss ${L}(y, f(\\mathbf{x}))=(y-f(\\mathbf{x}))\\left(\\tau-I_{\\{y\\leq f(\\mathbf{x})\\}}\\right)$, the local strong convexity holds if the conditional density of $y-f^*(\\mathbf{x})$ given $\\mathbf{x}$ is bounded away from $0$ uniformly [1]. For other loss functions such as logistic loss, hinge loss, and so on, mode discussions and verifications are provided in Appendix, and we also refer to pages 470-472 in [2] for the details.\n\n**Weakness 2**\n\nThanks a lot for your valuable comments on the notation and detail of the poof.  We have proofread the technical proof and all the necessary definitions and details have been added in the revised version.  Specifically, for the proof of Lemma C.1.2,  we have provided the definitions that $P\\varphi:=E_{S}[\\varphi(\\mathbf{x},y)]$  and $P_n \\varphi:=(1/n)\\sum_i \\varphi(\\mathbf{x}_i,y_i)$ for the measurable function $\\varphi(\\mathbf{x},y)$ with $\\varphi(\\mathbf{x},y)=\\phi_n(\\mathbf{x})(L(y,f(\\mathbf{x}))-L(y,f^*(\\mathbf{x})))$ in Eq.(2), and clearly clarified that the expectation $E[\\cdot]$ is taking with respect to all random variables contained in it.  Moreover, detailed explanations for the first inequality in Eq. (2) have also been added and some reference has also been properly provided, such as Proposition 4.11 in [2]. Precisely, it is derived from the symmetrization technique, which states that for any class of measurable functions $\\mathcal{F}$,  we have $E[\\sup (P_n-P)\\varphi]\\le 2E[ \\sup (1/n) \\sum_i \\sigma_i \\varphi({\\mathbf{x}}_i,y_i)  ] $, where $\\sigma_i$'s are the Rademacher variables. Additionally, it is necessary to stress that the coefficients $g_j$'s of the expansion for $g=f-f^*$ in the proof of Lemma C.2.1 corresponds to orthonormal eigenfunctions of $\\mathcal{L}^2(\\mathcal{X},P_x^T)$ instead of $\\mathcal{L}^2(\\mathcal{X},P_x^S)$.\n\n**Weakness 3**\n\nThanks a lot for your comments.  We admit that work in [3] makes tremendous contributions to the theories for the squared loss function under covariate shift and it is true that the Lipschitz property of loss functions and Assumption 2 play a crucial role in establishing our theoretical results. Yet, we want to emphasize that there still exist significant theoretical gaps from extending the squared loss function to the general loss function. \n\nIt is well-known that the estimator of KRR with squared loss has an explicit solution. Then, [3] takes advantage of the analytic solution to establish several critical results, including the theoretical bounds similar to Theorem 1 and 2 in our paper. Yet, \nwhen the general loss function is considered, such an explicit solution does not exist, and different theoretical treatments are needed. Specifically, we turn to another proof strategy by noting the relation between $\\||f-f^*\\||_S$ and $\\||f-f^*\\||_T$ as shown in Eq. (10), which motivates us to establish Lemma C.2.1 where the constraint set $\\Theta^\\prime(\\nu)$ is associated with the $\\mathcal{L}^2$-norm $\\||f-f^*\\||_S$,  which is significantly different from Lemma C.1.2 and the traditional practice by using $\\||f-f^*\\||_T$. Based on Lemma C.2.1, together with the definitions of $\\mathcal{Q}(\\delta), \\mathcal{G}(\\delta)$ and $\\mathcal{P}(\\delta)$ as in the proofs of Theorem 1 and 2, we successfully establish the convergence rates for unweighted estimators under covariate shift. It is worth pointing out that the convergence rate established in [3] can be regarded as a special case of our theoretical result,  which matches the upper bounds in Theorem 1 and 2.  Additionally,  we also established the sharp bounds in terms of excess risk under various cases, which provides a  unified analysis of kernel-based methods under covariate shift.\n\nWe want to emphasize that to some extent, this paper also provides a comprehensive study on the numerical performance of the kernel-based methods under various scenarios with covariate shift, which lends further support to the unified analysis and also presents the contributions of this paper.\n\n**Question**\n\nThanks a lot for your comment. In fact, $\\phi_n({\\mathbf{x}}_i)$ is the truncation version of $\\phi({\\mathbf{x}}_i)$ that is $\\phi_n(\\mathbf{x})=\\min\\left(\\phi(\\mathbf{x}),\\gamma_n\\right)$ as defined in Line 142 of the main text, and thus the inequality $\\phi_n({\\mathbf{x}}_i)\\leq \\phi({\\mathbf{x}}_i)$ holds directly.  \n\n**Reference**\n\n[1] Lian, H. (2022). Distributed learning of conditional quantiles in the reproducing kernel Hilbert space.\n\n[2] Wainwright M J. High-dimensional statistics: A non-asymptotic viewpoint. \n\n[3] Ma, C., Pathak, R., & Wainwright, M. J. (2023). Optimally tackling covariate shift in RKHS-based\nnonparametric regression.\n"}, {"review_id": "0FjESIv22I", "reviewer": "Reviewer_u3FW", "summary": "The authors study the covariate shift setting of nonparametric (kernel) methods\n(Regularized Empirical Risk Minimization with optional importance weighing) with\nan analysis which includes a wide array of losses and and two conditions on the\nimportance function. They establish sharp convergence which corroborate other\nrates in literature. Additionally they provide experiments showing these rates\nin practice.\n", "questions": "Could the authors clarify the discrepancy between the theorems and practice in terms of the importance function $\\phi$? You mention that you use an estimated function as plugin, do you expect it should be possible to prove results when using a plugin instead of the real thing?\n", "limitations": "Same as in Questions section. No need for societal impact limitation.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Quality: The authors extend the results to a wide array of losses and two types of covariate shift problems which is nice.\n- Clarity: The paper is well-written and notation makes it easy to follow\n", "weaknesses": "- There are quite a bit of terms which are unknown in practice and they need to\n  estimate the importance function which limits the practical impact of the\n  method.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and helpful comments on our work! Our point-by-point responses to your comments are given below. \n\n**Weakness**\n\nThanks a lot for your comments. We admit that the true importance ratio is unknown in practical applications, which needs to be estimated from the unlabeled test data. However, we want to emphasize that in literature, many existing methods [1,2,3] can be directly applied to accurately estimate the importance ratio. As illustrated in our extensive numerical experiments, the numerical performances of the implemented method with the true importance ratio and the estimated importance ratio are negligible in both synthetic and real-life examples. This implies that the importance ratio can be efficiently estimated, which may help the practical implementation of the proposed method.\n\n**Question**\n\nThank you very much for your comments. We want to clarify that our theoretical results are established with the known true importance ratio. Yet, as you mentioned in the previous comment, the importance ratio is unknown in practical applications. We admit that there exist some gaps between the theory and practice, but we also want to emphasize that such gaps commonly exist in the literature on covariate shift as far as we know [4,5]. We agree that it is very interesting to establish some similar theoretical results by using the plugin estimator and to our best knowledge, such results are still unknown in the literature, possibly due to the existing theoretical obstacles.  We decide to leave such a promising topic as potential future work, but add some detailed discussions on the possible route for establishing the theoretical results at the end of the supplemental file in the revised version.  Specifically, the key step is that we need to well control the term $\\sup_{f \\in \\Theta(\\delta)}|(1/n)\\sum_{i=1}^n(\\widehat{\\phi}_n({\\mathbf{x}}_i)-{\\phi}_n({\\mathbf{x}}_i))(L(y_i, f({\\mathbf{x}}_i))-L(y_i, f^*({\\mathbf{x}}_i))) |$, and thus the strong convergence rate of $\\widehat{\\phi}_n-{\\phi}_n$ is required. We want to point out that the summands contained in this term are not independent since the estimated importance ratio $\\widehat{\\phi}$ uses the source data, and some advanced technical tools are needed. Once this term is well bounded, we can establish the results similar to Theorem 3 by using the existing proof technique with slight modification.\n\n**Reference**\n\n[1] Huang, J., Gretton, A., Borgwardt, K., Schölkopf, B., & Smola, A. (2006). Correcting sample selection bias by unlabeled data.\n\n[2] Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., & Schölkopf, B. (2009). Covariate shift by kernel mean matching.\n\n[3] Sugiyama, M., Nakajima, S., Kashima, H., Buenau, P., & Kawanabe, M. (2007b). Direct importance estimation with model selection and its application to covariate shift adaptation.\n\n[4] Tibshirani, R. J., Foygel Barber, R., Candes, E., & Ramdas, A. (2019). Conformal prediction under covariate shift. \n\n[5] Ma, C., Pathak, R., & Wainwright, M. J. (2023). Optimally tackling covariate shift in RKHS-based\nnonparametric regression."}, {"review_id": "6SbqqLDsS0", "reviewer": "Reviewer_ZoXA", "summary": "The paper provides a unified analysis of convergence properties for different kernel-based estimators under covariate shift. The analysis covers different loss functions and is focused on standard and importance weighted empirical risk estimators. The former are specified in Eq. (1) and the latter in Eq. (3). \n\nThe first assumption is pretty standard and requires a uniformly bounded kernel function. The second assumption enforces a locally strong convexity on the expected loss function relative to source and target marginal distributions (source available during training, target assumed to be shifted and available at test time). The assumptions that characterize the distribution shift are given on page 4 (lines 131 and 132): i) in the first case the importance weights are $\\alpha$-uniformly bounded, ii) in the second case the second moment of the importance weight function is bounded. \n\nTheorem 1 gives convergence bounds relative to case i) under the assumptions above. Further assumption is made to give a more readable interpretation of the bound in Corollary 1 which ties the convergence rate to kernel spectrum decay.\nTheorem 2 gives a similar convergence result in a more difficult case ii), again under the assumptions listed above.\nTheorem 3 considers an estimator that uses importance weighted empirical risk estimator, with truncated importance weights to avoid issues with tail samples. It is for case ii) and bounded second moment of importance weights. The latter result indicates much tighter convergence rate than the one in Theorem 2 that considers standard estimator without importance weighting.\nEmpirical analysis illustrates the tightness of the bounds on synthetically generated learning tasks and a real-case study. ", "questions": "The formulation of theorems should be cleaned as currently there are symbols that have not been introduced properly. For instance, it is unclear what $\\delta_n$ refers to here and how it is related to $\\delta$. The authors have spent a fair amount of space to illustrate the bounds and allow for readers to build some intuition. However, still the clarity could be a bit improved by moving from Appendix C.4 the part that transforms Eq. (5) to (7). At first, I had the impression that the right hand side just will not converge under the assumption on $c_0$ and $\\lambda$.", "limitations": "Adequately addressed", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "While I have not checked the proofs, the theoretical part of the paper is its strongest point. It is also an interesting characterization of distribution shift carried into the bounds and would be interesting to see what other more granular specifications are possible for future studies. A relative comparison between Theorem 2 and 3 also illustrates the utility of truncated importance weighted estimator, which might be important for practical applications. ", "weaknesses": "Empirical study might be the weakest part of the paper but given its nature should be fine. It might also be interesting to see how relevant are the assumptions on distribution shift relative to practical applications and datasets. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your dedicated time reviewing our paper and valuable insights! Our point-by-point responses to your comments are given below. \n\n**Weakness**\n\nThanks a lot for your valuable suggestions. We want to point out that due to the space limit, only a small fraction of numerical experiments are reported in the main text. Actually, a lot of numerical experiments on synthetic data and real data are presented in Section A of the supplementary material, where many other loss functions and multi-dimensional cases are considered. Moreover, we applied the proposed method to a wide range of real datasets and the numerical performance is summarized in Table 1 in Section A of the supplementary material. To some extent, this paper provides a comprehensive study of the numerical performance of the kernel-based methods under various scenarios with covariate shift. \n\nWe agree with you that it is very interesting and meaningful to test if there exists a distribution shift in practical applications and datasets and if the distribution shift satisfies the uniformly bounded or moment bounded assumptions. Unfortunately, the relevant approaches have remained lacking to our best knowledge.  We decide to leave such a promising topic as potential future work. And it is interesting to note that as shown in our real applications, the TIRW estimator always outperforms the unweighted estimator, and thus we suggest using the TIRW estimator to analyze the real-life dataset.\n\n**Question**\n\nThank you very much for your suggestions.  In the revised version, we have rearranged the formulation of theorems and added some more descriptions of the introduced symbols and obtained results to provide more intuitive explanations of the established theoretical results. Some of the modifications are listed below:\n\nFirstly, in Theorem 1, $\\delta_n$ is defined as the smallest positive value $\\delta$ satisfying  $C\\sqrt{\\log n} R(\\sqrt{\\alpha}\\delta)\\le c_0\\delta^2/2$. Similar modifications have been made in other established results, including Theorems 2 and 3. Moreover, some useful discussions on $\\delta_n$ have also been added just behind Theorem 1.\n\nSecondly, we have moved some detailed explanations from Appendix C.4 to clarify  the transformation from \n Eq.(5) to (7) in the main text.  Specifically,  the kernel complexity function $R(\\delta)$  can be well approximated by $C\\sqrt{(1/n)d(\\delta)\\delta^2}$ for the regular kernel class that includes many widely used kernels, such as the kernels with polynomial or exponential decay in their eigenvalues. Then, the link from $R(\\delta)$ to $d(\\delta)$  can be used to derive Eq. (7). Moreover, the explicit formulation of $\\delta^2_n$ corresponding to specific kernels can be obtained by using the bound of $d(\\delta)$. For example, $d(\\delta)\\lesssim \\log(1/\\delta^2)$ with $0<\\delta<1$ for Gaussian kernel and $d(\\delta)\\lesssim \\delta^2$ for the finite rank kernel.  Once $\\delta^2_n$ is determined, the upper bounds can be immediately obtained by applying theorems with the choice of $\\lambda\\asymp \\delta_n^2$, and then we have $\\||\\widehat{f}-f^*\\||^2_T\\lesssim \\delta^2_n$ from Eq.(5)."}, {"review_id": "Ivij3ls0tw", "reviewer": "Reviewer_qhGh", "summary": "This manuscript presents convergence rates for kernel methods under covariate shift. Results fit quite a general framework, including common classification and regression losses. Two approaches are analyzed: (i) a usual M-estimator and (ii) an importance-sampling-like M-estimator. It is shown theoretically and empirically that the latter outperform the former.", "questions": "1) What is $f_j$ Line 154?\n2) What does $\\psi_j \\le Cj^{-2r}$ (Lines 201 and 235) mean, given that $\\psi_j$ is a function? Is a norm missing?\n3) Does the trends (evolution with respect to $n$) observed in Figure 2 (b)-(e) and Figure 3 (b)-(e) is of the order $\\left( \\frac{\\log n}{n} \\right)^q$ or $\\left( \\frac{\\log^2 n}{n} \\right)^q$ as exhibited in Table 1?", "limitations": "Limitations are not addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The analysis presented in this paper provides interesting theoretical results regarding learning under covariate shift, which is a contemporary topic. The manuscript is well organized; it explains clearly the problem, state the results while discussing the hypotheses and, at the end, illustrates the theoretical findings by a numerical experiment.\nI would like to stress that discussions regarding hypotheses are opportune and corollaries provide intelligible results.\nThe take-home message, stating that the importance-sampling-like estimator is better that the naive one, is interesting and confirms practitioners’ intuition. ", "weaknesses": "Major remarks:\n1) My main concern is about the novelty of the proofs: hypotheses (i) and (ii) look like straightforward tools to link expectations under the source distribution to the target distribution by linearity or Cauchy-Schwarz inequality. I had a very quick glance to the supplementary material and it confirmed this guess (although I admit that I may be wrong). I think that its important, in order to assess the contribution of the paper, that the authors explain the original derivations appearing in the proofs, with respect to techniques used for obtaining similar results without covariate shift (unfortunately, I have no reference in mind).\n2) Another (minor) point is that Figure 1 does not seem to verify neither hypothesis (i) nor (ii) since $\\phi(x)$ seems to explode when $x \\to \\infty$. If it is the case, it would be better to find another example (or at least to discuss this point). If it is not the case, it would be informative to explain it.\n\nSome suggestions of improvement:\n1)  $f^*$ is defined in Section 2.1, before the problem setting in Section 2.2. However, in practice, it corresponds to the optimal function under the target distribution, which is not clearly stated. I suggest to make it clear.\n2) Although an informed reader understand definitions Line 113, it is not totally clear that expectations are conditioned by observed data. I suggest to had this information.\n3) $D$ could be added after “Finite rank” in Table 1.\n4) Line 264, it is not totally clear that “For the moment bounded case” correspond to Figure 3. I suggest to had it.\n\nTypographical remarks:\n1) Extra “the” Line 5.\n2) “that” instead of “that is” Lines 126, 131 and 132.\n3) In Theorems 1-3, $\\delta_n$ should satisfy an inequality that involves $\\delta$ instead of $\\delta_n$.\n4) There are $\\phi(\\textrm x)$ instead of $\\phi(\\textrm x)^2$ Lines 212 and 223.\n5) Full points are missing in captions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments and valuable suggestions! Our point-by-point responses to your comments are given below.\n\n**Major remark 1**\n\nThanks a lot for your concern with the novelty of our proofs. We admit that our proofs use many classical empirical process techniques, such as the concentration inequality  (Lemma C.1.1.) and the symmetrization technique (Eq.(10) in Section C of supplementary material, which is also popularly used for establishing the theoretical results without covariate shift [1,2]. Yet, we want to emphasize that there exist some significant differences in proofs between the traditional regime and the case under covariate shift. Following your suggestion, we have highlighted the proof ideas and motivations under the covariate shift and compared the difference with the case without covariate shift in the revised version.  Some key points are summarized as follows:\n\nFirstly, under the classical case without covariate shift, we only need to control the supremum over a functional class of empirical process, which is defined as the empirical sum minus its expectation counterpart, and then, some classical empirical process techniques such as symmetrization technique and Talagrand’s concentration inequality can be directly adopted. Yet, under the case with covariate shift, we need to control the difference between the empirical sum with the samples driven from the source model and the expectation under the target model, as shown in Lemma C.1.2 of Appendix. Thus, we first need to decompose the total error in the proof of Lemma C.1.2. into two parts: the first part $D_1$ is the classic empirical process formulation and the second part $D_2$  is the residual which doesn't exist in the case without covariate shift.  For $D_1$, the main difference is that we have an extra importance ratio term and we need some hypotheses (uniformly bounded or moment bounded) on the ratio to bound it using the Cauchy-Schwarz inequality and Lipschitz-continuous assumption. For $D_2$, we use a technical truncation strategy to bound it. The truncation $\\gamma_n$ plays a crucial role in balancing the empirical error and the approximation error. In fact, a fast diverging $\\gamma_n$ may reduce the approximation error but compromise the empirical error. We use the optimal truncation $\\gamma_n=\\sqrt{n\\beta^2}$ which ensures the empirical error and approximation error converge at the same order up to a $\\log$ factor. This proof strategy is significantly different from that under the classical case without covariate shift.\n\nSecondly, to establish the convergence rates for unweighted estimators in both uniformly bounded and moment bounded cases,  we can't trivially construct a constraint set associated with the $\\mathcal{L}^2$-norm $\\||f-f^*\\||_T$ under the target distribution, as the classical case without covariate shift. To tackle this problem, we notice the relation between $\\||f-f^*\\||_S$ and $\\||f-f^*\\||_T$ as shown in Eq. (10) in Appendix, which motivates us to construct the constraint set $\\Theta^\\prime(\\nu)$ associated with $\\||f-f^*\\||_S$ as in Lemma C.2.1. Also note that the coefficients $g_j$'s of the expansion for $g=f-f^*$ in the proof of Lemma C.2.1 corresponds to orthonormal eigenfunctions of $\\mathcal{L}^2(\\mathcal{X},P_x^T)$ instead of the $\\mathcal{L}^2(\\mathcal{X},P_x^S)$. \nBased on Lemma C.2.1, together with the definitions of $\\mathcal{Q}(\\delta), \\mathcal{G}(\\delta)$ and $\\mathcal{P}(\\delta)$ as illustrated in the proofs of Theorem 1 and 2, we successfully establish the convergence rates for unweighted estimators under covariate shift. This proof strategy is significantly different from that under the classical case without covariate shift.\n\n**Major remark 2**\n\nThanks a lot for your suggestions. In the original version, Figure 1 serves as an illustration of the phenomenon of covariate shift, and indeed, it may not be a good example. It has been replaced by a new example, which satisfies hypothesis (ii), and more explanations have also been added in the revised version. The modified Figure 1 is also attached in the Author Rebuttal pdf.\n\n**Suggestions of improvement**\n\nThank you for all your suggestions. 1. The reason for defining $f^*$ in Section 2.1 is to introduce the considered loss family. In the revised version, we have clearly stated that the true target function $f^*$ is defined under the target distribution in Section 2.2. 2. We have made it clear in the revised version by clarifying that the expectations are conditioned by the observed data. 3. ``Finite rank D' has been added in 'Table 1. 4. We will rewrite line 264 to “For the moment bounded case as demonstrated in (a) and (d) of Figure 3”.\n\n**Question 1 and 2**\n\nThanks a lot for pointing out the notation mistakes. Actually, $f_j$ should be replaced by $a_j$ where $a_j$ is defined in Line 153,  $\\psi_j$ should be replaced by $\\mu_j$ where $\\{\\mu_j\\}$'s are the eigenvalues of the kernel function defined in Line 151, and they have been corrected in the revised version.\n\n**Question 3**\n\nThanks a lot for your comment. In the original version, although the Gaussian kernel is used in the simulation, we do not provide the theoretical result for the kernel class with exponential decay.  In the revised version, we have added the explicit convergence rates corresponding to this kernel class in Table 1 which is also attached in the Author Rebuttal pdf. It is thus clear from the table that the trends in Figure 2 (b)-(e) and Figure 3 (b)-(e) almost agree with our theoretical findings where the Gaussian kernel with exponential decay is used. Additional numerical results presented in the supplementary material also confirm the theoretical convergence rates. \n\n**Reference**\n\n[1] Yang, Y., Pilanci, M., & Wainwright, M. J. (2017). Randomized sketches for kernels: Fast and\noptimal nonparametric regression. \n\n[2] Lian, H. (2022). Distributed learning of conditional quantiles in the reproducing kernel Hilbert space.\n"}]

Author rebuttal:
Thank you sincerely for your insightful comments and for dedicating your valuable time and effort toward the thorough evaluation of our paper.  We have carefully considered all questions, concerns, and comments raised by the reviewers. The insights and suggestions from reviewers have greatly contributed to enhancing the quality and clarity of our work. And we provided detailed responses to each review separately.  We also meticulously incorporated our responses into the revised paper and supplementary materials, mainly covering the following aspects: to highlight the contributions of this paper from the aspects of theory and practical application; to provide more details and insightful understanding about the established results; to correct all the typos, add some more descriptions of the definitions and make clear the introduced symbols. The attached pdf is a revised figure and table (Reviewer qhGh). Once again, we extend our heartfelt gratitude for your time, expertise, and contribution to our work.

Meta-review: The reviewers unanimously recommended to accept the paper.
Decision: Accept (poster)