Computational Efficiency under Covariate Shift in Kernel Ridge Regression
Authors: Andrea Della Vecchia
Arnaud Mavakala Watusadisi
Ernesto De Vito
Lorenzo Rosasco
Venue: NeurIPS 2025 spotlight ()
Keywords: statistical learning theory
kernel methods
covariate shift
random projections
Primary area: theory
TL;DR: We show that kernel ridge regression under covariate shift can be made computationally efficient using Nyström random projections, achieving optimal statistical rates without sacrificing accuracy.

Abstract: This paper addresses the covariate shift problem in the context of nonparametric regression within reproducing kernel Hilbert spaces (RKHSs). Covariate shift arises in supervised learning when the input distributions of the training and test data differ, presenting additional challenges for learning. Although kernel methods have optimal statistical properties, their high computational demands in terms of time and, particularly, memory, limit their scalability to large datasets. To address this limitation, the main focus of this paper is to explore the trade-off between computational efficiency and statistical accuracy under covariate shift. We investigate the use of random projections where the hypothesis space consists of a random subspace within a given RKHS. Our results show that, even in the presence of covariate shift, significant computational savings can be achieved without compromising learning performance.

Computational Efficiency under Covariate Shift in Kernel Ridge Regression
Andrea Della Vecchia Swiss Finance Institute (SFI)
Arnaud Mavakala Watusadisi
MaLGa, DIBRIS University of Genova
EPFL
andrea dew.eelllllll.. www.leleecchaa@pppl.cco
5775617@studentl unige. it
Ernesto De Vito
Lorenzo Rosasco
MaLGa, DIMA
MaLGa, DIBRIS
University of Genova ernesto. devi wowiittuunneiii.
University Genova
Istituto Italiano di Tecnologia
lorenzo. rosascolunige....
Abstract
This paper addresses the covariate shift problem in the context of nonparametric regression within reproducing kernel Hilbert spaces (RKHSs). Covariate shift arises in supervised learning when the input distributions of the training and test data differ, presenting additional challenges for learning. Although kernel methods have optimal statistical properties, their high computational demands in terms time and, particularly, memory, limit their scalability to large datasets. To address this limitation, the main focus of this paper to explore the trade-off between computational efficiency and statistical accuracy under covariate shift. We investigate the of random projections where the hypothesis space consists of random subspace within a given RKHS. Our results show that, even in the presence of covariate shift, significant computational savings can be achieved without compromising learning performance.
Introduction
Classical supervised learning assumes that the training and test data distributions are identical Vapnik (1999). However, in practice, it is often the case that there is significant mismatch between the two Quinonero-Candee et al. (2022). This discrepancy can arise from various factors, such as inconsistencies measurement equipment, differences in data collection domains, or variations in subject populations Koh et al. (2021). Among these scenarios, one particularly interesting and common case known as covariate shift Sugiyama & Kawanabe (2012). Covariate shift occurs when the marginal distributions of the input covariates differ between the training and test data, while the conditional distribution of the output label given the input covariates remains unchanged Shimodaira (2000); Cortes et al. (2008). This phenomenon is observed in variety of well-studied learning problems, including among all domain adaptation Ben-David et al. (2006); Mansour et al. (2009); Cortes & Mohri (2014); Zhang et al. (2012), active learning Wiens (2000); Kanamori & Shimodaira (2003); Sugiyama & Ridgeway (2006), natural language processing Jiang & Zhai (2007), and medical image analysis Guan & Liu (2021).
Despite its practical significance, covariate shift remains relatively underexplored in theoretical frameworks compared to the classical setting where distribution mismatch is assumed. Recently, several studies have attempted to bridge this gap. A widely adopted approach to addressing covariate shift involves correcting the learning objective by reweighting the loss function using the so-called
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

importance weighting (IW) function. This function corresponds to the Radon-Nikode derivative of the test marginal distribution with respect to the training marginal distribution Huang et al. (2006); Sugiyama et al. (2012); Fang et al. (2020). Shimodaira (2000) was the first to demonstrate the consistency of the importance-war weightedd maximum likelihood estimator, while in Cortes et al. (2010) the authors derived suboptimal unite-ssmple bounds for restricted function classes with finite pseudodimension. In the context of nonparametric regression in reproducing kernel Hilbert spaces (RKHSs) and under the assumption that the regression function belongs to the RKHS (well-specified case), Gizewski et al. (2022) provided optimal excess risk convergence results for the minimizer of the reweighted empirical risk when the weight function is known and uniformly bounded. In Ma et al. (2023), authors recently showed that the standard unweighted kernel ridge regression estimator is still minimax optimal under an appropriate choice of the regularization parameter, provided the IW function is uniformly bounded or its second moment is bounded. Similar results for nonparametric classification were obtained in Kpotufe & Martinet (2021). We also mention Schmidt-Hieher & Zamolodtchikov (2024); Pathak et al. (2022) in the context of nonparametrie regression for classes of functions different from RKHSs, and Wen et al. (2014); Lei et al. (2021); Yamazaki al. (2007) for parametric models. Building on Ma et al. (2023), in Gogolashvili et al. (2023) the authors extended the analysis (simplified) misspecified case, where the regression function is not assumed to lie in the RKHS itself, but its projection is. In this setting, the authors showed that, under covariate shift, the unweighted classic KRR predictor not a consistent estimator of the projection of the regression function. In such cases, IW correction is necessary.
Kernel methods provide a robust framework for nonparametric learning. but their scalability is limited by high computational and memory costs costs-challenges that clearly do not disappear under covariate shift. To address this, researchers have developed more efficient strategies, ranging from improved optimization (Johnson& & Zhang, 2013; Schmidt et al., 2017) to randomized linear algebra techniques (Mahoney, 2011; Drineas & Mahoney, 2005; Woodruff, 2014; Calandriello et al., 2017). These aim to reduce costs, raising a key question: do such shortcuts compromise statistical accuracy? Recent work suggests they often do not (Rudi al., 2015; Bach, 2017: Bottou & Bousquet, 2008; Sun et al., 2018; Rudi & Rosasco, 2017; Della Vecchia et al.. 2021). A promising approach is to restrict the hypothesis space lower-dimensional (random) subspace, as in sketching (Kpotufe & Sriperumbudur, 2019) and random projection methods ( (Woodruff. 2014), including Nyström methods for kernels (Smola & Schökopf, 2000; Williams & Seeger, 2001). Recent results confirm that these methods can achieve both computational efficiency and statistical accuracy, for both smooth and general convex losses (Rudi et al., 2015; Bach, 2013; Harteau-Feree et al., 2019; Della Vecchia et al., 2024).
Although random projection techniques-such as the Nyström method-have been widely studied in standard learning settings, their use under covariate shift remains largely unexamined. A recent step in this direction was taken by Myleiko & Solodky (2024), building on the framework of Gizewski et al. (2022). The authors consider Nyström subsampling in a setting where weights are known and uniformly bounded, and derive optimal risk bounds that. in the case of Tikhonov regularization, can be recovered as a special case of our results.
Contribution. In this paper, we investigate the regression under the covariate shift setting. Unlike most of the previous work in this setting, employ random projection techniques, specifically the Nyström method, to improve the algorithm's scalability and efficiency. Our primary goal is explore the balance between computational effi- ciency and statistical accuracy in this framework. By analyzing the interplay among regularization, subspace size, and the various parameters that characterize the complexity of the problem, we identify the conditions under which the best-known statistical guarantees can be achieved while drastically reducing computational costs. Notably, we show that our algorithm achieves remarkable result: despite Nyström approximation. it attains the best rates reported in the literature without compromis- ing statistical accuracy. all while being significantly more computationally efficient. Regarding the theoretical aspects, while we build upon established results from the random projections literature, our novel proofs presented here address additional technical challenges arising from the mismatch between training and test distributions, as well as the potential unboundedness of the weighting function in the empirical risk minimization. Full technical details are provided in Appendix B. Finally, we validate these theoretical findings through simulations and real data experiments.
correction for kernel ridge
Limitations. As remarked in Section 5, Assumption 3 imposes boundedness of all moments of the weight function. While this is a relatively strong condition, especially when compared to the mere second-moment boundedness required in Ma al. (2023), it is essential in our setting ensure
2

---

the applicability of the Nyström method with ALS sampling in the unbounded case. Assumption 2 ensures that the projection of the regression function onto the hypothesis space H. exists and lies within H. rather than on its boundary. This is slightly more general than the standard well-specified setting, but conceptually similar. We do not consider the fully misspecified case here, which introduces significant additional complexity (see interpolation spaces in Steinwart & Christmann (2008) for example). Finally, as mentioned in Section 8, more refined understanding of the role of the constants in the learning rate bounds could explain why, in practice, misalignment between training and test distributions can sometimes be benign or, conversely, highly adversarial, depending on its relation with the source condition. These directions are left for future work.
Organization. The paper organized as follows. In Section 2, we introduce the key definitions and notations used throughout the paper, while refreshing KRR in the classical setting. Section 3 provides an overview of KRR in the covariate shift setting. Section 4, we present empirical risk minimization on random subspaces using Nyström. Section 5 explores the interplay between computational efficiency and statistical accuracy. Section extends our analysis to scenarios where the true IW function is unknown. Section presents series of simulations and real-world experiments.
2 Background
We start defining some key quantities will need in the rest of the paper, see e.g. Caponnetto & De Vito (2007); Smale & Zhou (2007). Given a measurable space X', probability distribution on X, space of square-integrable functions T2 with respect measure / and Reproducing Kernel Hilbert Space (RKHS) 7 of (bounded) kernel K X x X + R, with (.(-) K(x,)) H. define
Sp : H + L (S₂f) = Kz) = f(x) 1 a.s. and $1.9 = / Kag(z)dp.
for f E H. g E 122, Covariance operator En H. + H is defined as Enp = S = F [K @ Kz). Define the sampling operator S: H + R" associated with set {II,..., Inl E X", for f E H. as
1 Vi Kay DER".
= (=f):=((xa)) (f, K Kuin, i [m], and (D) =
2.1 Classical Setting
Classical nonparametric regression aims to predict real-valued output ) R given vector of covariates X E X. More formally, let X x R be a probability space with distribution p. where X' and R are the input and output spaces, respectively. Let px denote the marginal distribution of p on X' and p( (x) the conditional distribution on R given x E X. For any fixed x E X', the optimal estimator in mean-squared sense is given by the regression function g" (x) = ydp(y)æ)) i.e.
arg min R(g) E((Y - 9 yER
The minimization problem is generally unsolvable since the distribution p is unknown. In practice, we only have access to a dataset n input-output pairs (I,, 34 3:) E (X' x IR) sampled independently and identically (i.i.d.) from the joint distribution p. i.e. (I1, 21), ..... (I,,, U/)) ~ p(x,y).
common approach to derive an approximation of g" involves restricting the hypothesis space from all measurable functions to real separable Hilbert space H. and replacing the expected risk R with the (regularized) empirical risk Rx H o0) defined as
RA(1
yy - fxx))) AISI SEH, ^>0.
71
The (Regularized) Empirical Risk Minimization (ERM) algorithm then solves:
fx = arg min Rs-
(2)
When H is an RKHS, as in the rest of this paper, the resulting estimator is known as the kernel ridge regression (KRR) estimator. Our primary goal is to upper bound the excess risk of fx, i.e.
E(fx) == R(fx) - R(g") = Ilfa 1' Here, the equality follows from standard result, for example Caponnetto & De Vito (2007).
3

---

3 Covariate Shift Setting
The covariate shift setting introduces an additional complexity: training and test distributions may differ, but only through their marginals, while sharing the same conditional distribution:
p² (I, v) - (())))))((>,
(xr v) p(yl=))x (x).
Since the regression function g" only depends on the conditional distribution, which is identical for both paa and ptr it is unique. As in the standard setting, we are provided with input-output pairs (Ii,, 1:) E (X x R) sampled i.i.d. from p" i... (01.8/)..... (Xn, y/) ~ (²'
The challenge consists in the fact that we train our model using samples from the p²*, but we aim to evaluate its performance on new data drawn from pt Then, we want to upper bound the excess risk
E(Aa) 11. -'
Note that the empirical risk computed from par samples is biased estimate of the expected risk under pte, As result, minimizing it may yield predictor that performs well on the test distribution.
3.1 Aaportance-Weightiinn (IW) Correction
The goal of importance-weighting (IW) correction is to construct an unbiased estimator of the risk with respect to test distribution pt while using data sampled from pt The idea is to reweight ERM samples based on their relevance to the test distribution, ensuring good performance under pT If xxx < P we can define the IW function representing the weight assigned to point E X' as the Radon-Nikodym derivative of p' with respect to X
w(x) = dp's
x (x).
(3)
Points that are likely be encountered during testing (p' is large) while training time (p% is small) are considered particularly relevant and will receive higher weights.
be sampled
In the rest of the paper, we will focus on applying this framework in the context of kernel methods. Assumption 1. H is an RKHS with scalar product (s,)) and associated kernel K : X' x X + R.
We define the regularized importance-weighted empirical risk, for all f E H. as
Rx = w(x)) (K), Allf112
(4)
where H 3 K2(+) K K(x,) .) For the square loss, the minimizer fx of eq. (4) is given by:
(x = (3t M -1 M...
(5)
where My is the diagonal matrix with i-th entry w(xx)- In case weights all positive, we have
(x) = Σ che K (x) span K K Ka.). c² (R nAM E ER"
(6)
where is the kernel Gram matrix, and M, w is the diagonal matrix with i-th entry 1/w(w;;) Since the regression function g" may not generally belong to H (i.e., the model may be misspecified),
we introduce the best approximation fH E H of g" with respect to the I distance. px
Assumption 2. There exists an JH E H such that
E(fx) = min {(f)
min |lf gg g011200- JEH
JEH
Note that, while the minimizer might not be unique, we select SH as the unique minimizer with minimal norm (De Vito et al., 2021). In the following, we will evaluate the performance of our estimator relative to the best estimator in H. i... fH

---

Computations A significant limitation of the procedure outlined above is the computational cost associated with the n matrix inversion required to compute the estimator, see (6). This operation has complexity of (n²) ) in time and (n²)) in memory, making it impractical when n > 10
4 ERM on Random Subspaces and the Nyström Method
In this paper, we consider an efficient approximation of the above procedure based on considering a subspace B c 'H and solving the corresponding
regularized ERM problem
min Rx (3),
(8)
BEB
with 3x the unique minimizer. As clear from (6), choosing B Hn = span K ......, Kg,) is equivalent to considering the full space H and yields the same solution in (5). However, a natural alternative is to consider smaller subspace:
B = Hm = span ......., K }
where { _m C (xI,..., Jn is a random subset of the input points and m S n. This is equivalent Nyström approximation (Williams & Seeger, 2000). A basic approach is to select these points uniformly at random from the training dataset. Alternatively, we can employ more refined sampling techniques, such as using leverage scores (Drineas et al., 2012)
((a) (R(R +
i i;
(10)
Since in practice computing leverage scores directly can be computationally expensive, approxima- tions (4) have been considered (Drineas et al., 2012; Cohen al., 2015; Alaoui & Mahoney, 2015). In particular, we consider the following one. Definition 1 (I' (T-approximate leverage scores). Let (I= be the leverage scores associated the training set for given a. Let 0, to > and T > 1. We say that (i,(a))ī= are T T-ppproximate leverage scores with confidence 6, when with probability at least 1-6. ô,
T [(()) < (()) & Th(a), Ei (1, (1.....n).
n). a a>1a lo-
(11)
Given the Tappprxximate leverage scores for > lg. ALS sampling proceeds by independently drawing samples 1 F.m from the training set with replacement, where each point x; is selected with probability (a(1) = 4(aa// Σ, (a). All the results in the next sections are obtained under ALS sampling.
We can now define the Nyström W-KRR problem follows:
-33) 2 + A 111 = arg min 1 1 -S SPm +X1I
fX. araggmin min SEHm
/
JEH
(12)
where Pm the orthogonal projection operator onto Hm, given by Pm. VV* see Appendix A. Taking the derivative and using the first order condition (see Appendix A), the Nyström estimator can be expressed as:
V(V* S' MV + - S* M... Alternatively, using some linear algebra, it can also be written
frm
(13)
(x)
Σ
Jo' K (x),
The = (R nm M R nm + n nXR RT
- nm M...
(14)
where (x) spant (K K ) T E Rm. R E R2xm, (Kam)is K( Ty) and Rmm E 1Rmx (Kmm)ki = K (5,, k5) (see derivation in Appendix A).
Computations From eq. (14), is clear that the Nyström method can offer significant computational benefits. Unlike eq. (13), computing our projected estimator only requires Om + m²n) time and
(mm) memory, compared to the previous ((n²) and On²). When & n the difference between the two can be big and efficient implementations such as in Rudi al. (2017); Meanti et al. (2020) can drastically reduce computational requirements.
5

---

Statistical Guarantees
In this section, we aim derive excess risk bounds for the Nyström estimator presented in eq. (13). We begin by introducing the technical assumptions required for the subsequent analysis.
5.1 Further Assumptions
The following assumption, inspired by Gogolashvili et al. (2023), ensures the boundedness of the importance-weighenn (IW) function or of its moments.
Assumption 3. Let w / /dpx be the IW function. There exist constants q E [0, W > 0 and a such that Vp E N, P D2? 2
U ((x)) dp'tt
1 Follw-220.
(15)
where the left-hand side for = is defined as || "1o0, the ess sup with respect to p'x-
Considering the uniformly bounded case |/wl|x < Co, Assumption 3 is satisfied for g O. When is not uniformly bounded, Assumption 3 can still be satisfied for q E (0, 1] if the moments of are bounded. For example, it is satisfied for q E (0, W 3 1, > and
2px (f (
do' (x) > 1) < o² exp (-W-1e/)) for all 1
dox
(see Appendix in Gogolashvili et al. (2023) for the detailed result). Equivalently, Assumption can be stated as condition on the Rényi divergence between p and x' (Mansour et al., 2009; Cortes et al., 2010). It follows that this assumption can be interpreted as requirement for the test distribution p deviate significantly from the train distribution 2xx with q E [0, 1] quantifying the extent of the deviation. Introducing the parameter is useful for presenting results such as Theorem 1 in unified form, which can then be specialized the two cases considered in Corollary 1: uniformly bounded (q- 0) and possibly unbounded (g # 0) weights. Note that in Ma et al. (2023), weaker assumption requiring only the second moment be bounded is considered. The stronger condition in eq. (15) is anyway crucial in our case to apply the Nyström method in the unbounded setting (see Appendix B and how the proof differentiates from Rudi et (2015)).
Assumption 4. The range of the outpul Y E IR is upper bounded, i.e. Y E [-B, B < co.
Furthermore, we make the following regularity assumption, usually known as source condition.
Assumption 5 (Source condition). There exist 1/2 < r & 1 and g E L (X, p\x) with l|sll & R for some R > 0 such that fx L'g, where L Sp is the integral operator.
Assumption 5 and its equivalent formulations (e.g., Assumption 4 in Rudi al. (2015)) are common in literature (Smale & Zhou, 2007; Caponnetto De Vito, 2007). r quantifies the smoothness of the target function fH and the extent which it can be well approximated by functions in H. For r == 1/2, the assumption is always satisfied. Intuitively, a larger r implies fu being smoother.
Finally, we impose an assumption on the capacity of our RKHS, which roughly measures the number of eigenvalues of Σ greater than (Zhang, 2005; Caponnetto & De Vito, 2007).
Definition 2 (Effective dimension). For X > 0, define the random variable N₂(A) (E,(E + Al)-KKe), with x E X distributed according to p. then N₂(A) = EANa( is called effective dimension.
Assumption 6 (Capacity condition). AA > 0, there exists 0 & < 1, Q O... Na (A) < QX
is known that the condition in Assumption 6 is ensured the eigenvalues (πx); of the covariance operator Σ satisfy a polynomial decaying condition 1-1 (see Appendix C).
5.2 Excess Risk Bounds
In this section, we present our main theoretical results. We will derive excess risk bounds for the Nyström predictor defined in eq. (13) and we will show that Nyström approximation does not affect the sfate-of-art art rates of convergence while instead reducing both time and memory requirements.

---

We present now the main result of the paper.
Theorem 1. Under assumptions 1,2,3,4,56, for ALS sampling, let 8
0,
(256WW+0 (og" 70--)+++4
< &
[Sllo and m B 144T log Sn with proba-
bility greater equal than 1
-
1/2 E 64B (R(()))) -R(fx)
W
o2
log + 43RX.
nd 9)11--9)+
The detailed proof of Theorem can be found in Appendix B.
the weighting function w bounded, i.e. || < 0o, then Assumption satisfied for y = We specify Theorem for this setting against the unbounded one.
Corollary 1. Under the assumptions and conditions as in Theorem 1.
(a) with Assumption satisfied by q = and choosing x (11w01100/1 mit with m 2
(n/llu/loo))rr) log n, with high probability
E(fX,) 11 fn 113 ||wlloo
(16)
x (n/(W + +02))==0 2tt with m 2
(b) with Assumption 3 satisfied by q and choosing (n/(W + +z)) ननं log n, with high probability
E(f),m 11
full pse
1
2
(17)
The rate in eq. (16) matches the optimal convergence rate of standard kernel ridge regression (KRR) established in Caponnetto De Vito (2007). However, explicitly depends on || [oa which can become arbitrarily large as the training and test distributions diverge. This result also recovers Theorem 2.1 from Myleiko & Solodky (2024) for Tikhonov regularization in the special case 1. Compared their work, we consider ALS sampling, which enables fast rates under suitable capacity condition. Furthermore, we extend the analysis to the case of unbounded importance weights. Specifically, eq. (17) shows that when the weighting function is unbounded (i.e., q in Assumption 3), the convergence rate deteriorates to Onn 3FfT). This slower rate, which does not depend on the capacity assumption 6), is always worse than the rate in eq. (16). These findings consistent with the results reported in Gogolashvili et al. (2023) for the full (non-projected) model. Note that the rate in eq. (17) can possibly be improved, by clipping the unbounded IW function w at a threshold that depends on n (see Section 5.2.2 in Gogolashvili et al. (2023)). This idea follows Corollary 2 of Ma al. (2023), although the result is not directly comparable due to differing assumptions.
under our Nyström approximation,
Example 1. To illustrate the benefits of the Nyström approach, consider for example the common setting 9 0, r 1/2 and y 1. From eq. (16), we achieve the optimal rate of ((n=1/22 (Caponnetto & De Vito, 2007), with m O /n log(n)). This results in computational costs of Omm mm²n) = Onn/n + n²) in time and O (mn) O(n//) in memory. These are significantly lower than the costs of the non-approximated method, respectively O(n²) and (
6 Unknown Weights
Clearly, when dealing with real data, assuming knowledge of the exact weighting function w is unrealistic. Instead, if we have access to estimate an approximate weighting function v 2 w and control the error resulting from this approximation. Let choose function e such that there exists a probability distribution pkx with
samples from both distributions, we can attempt
dpx (x)
v(x)
(18)
dp' (x)
7

---

L.e. v(z) is the Cadon-Nikodiee derivative of p'x with respect to px. Note that, in general, P'x # PX. Similarly eq. (7) in Assumption we assume that
f = arg min (f) = - 11px
(19)
FEN
exists (again we consider the unique with minimal norm in case of multiple minimizers). Furthermore, we assume that e satisfies Assumptions 3, 5, 6 with constants V.n, 7, Q. respectively. Since is chosen, weights v() are known for all x E N, allowing us to compute the estimator
f V(V S M.SV + V M.g.
(20)
where M, is the diagonal matrix with diagonal entries u(z1)..... v(x,), Still, we are interested in the excess risk of this estimator with respect the original p distribution.
Denoting = Exp and Dn = Egx, we decompose the excess risk of fX,m as:
E(f) = 11.3.m fullps < | Ilopllfx.m -Hellex +Ilf full8x
(21)
Well Specified Case If g" H. then clearly g" = -HH= f and eq. (21) simplifies to: IiS... - & | 1lpp - sH
fx1l3x
(22)
The second term corresponds to what have already analyzed in Theorem with the distribution pke and its associated weighting function w replaced by p3 and v. The first term quantifies the additional cost incurred due to the mismatch between Xx and p Ussing Proposition 5 from Appendix C, we can show that if we set v(x) = I, i.e. pg pxx then ||ΣΣ lop < ||w]|oc- This indicates that, when w is bounded, we have a finite control on the appearing term involving the two covariance operators.
By setting (1]w) n)) क, and ensuring m Z कr.न logn, n, then, with high probability
fx 11
< /wwl oo
(23)
72
where we used the fact that ||0]|c = 1. It is important to note that, when compared with the bound in eq. (16), which assumes knowledge of the true (typically unknown) weights, we achieve the same rate in n. This means that, when the model is well-specified, the classical Nyström-ERR ERM algorithm gives the same rate as the importance- weighted variant, despite the covariate shift between train and test distributions. This result agrees with findings in Ma et al. (2023); Gogolashvili et al. (2023), where anyway random projection approximations are not involved. More than that, we emphasize that although the rate remains the same, the dependence on || which is assumed finite but can be arbitrarily large, is worse than in eq. (16), where the true w is employed.
Misspecified Case JN + fü- In particular, the term [| - ~x in eq. (21) is not zero, and its magnitude can become arbitrarily large, depending on the severity of the mismatch between x and p*c
In the misspecified case, the situation is more complex since in general g" *
7 Simulations and real data experiments
As emphasized in the introduction, the main goal of this study is to show that the Nyström method can deliver significant computational savings under covariate shift without compromising accuracy.
7.1 Simulations
We start by reproducing the experimental setting in Gogolashvili et al. (2023). We want to solve regression problem using KRR with RBF kernel in the context of distribution shift, assuming o ~ N(ter, ). pIx ~ (pte Eee) and pay # Ptes Der + Lee. The regression function
(x) = eie
1 KEN, CEN,
where the parameter & controls the level of misspecification. Note that, in fact, when increases, the regression function becomes essentially wisce-wise constant, and neither constant nor discontinuous
8

---

Wonghtd 1M1
1.0
Rhightad RMM
KRB
XBR
Weightd Myarfon 1012
Wedggtts Nyrsom KSB
0.8
10
0.
0.9
04
0.3
0.2
Figure I: On the left: MSE for the different models varying the number train samples n. The result for Nyström W-KRR model is obtained for optimal m. On the right: n 3000, optimal m is selected as the smallest for which Nyström W- W-KRR matches the full W-KRR model (m = 1000 here).
functions belong to the RKHS of the Gaussian kernel. Data samples are generated following v/" 9" (af") Ei, vt g" (x/²), with x!" xxx xt! o² and & (0) Figure shows the results in this setting for k = 50. In the plot on the left, we observe that the two weighted models, namely KRR with IW correction (W-KRR) and its
version (Nyström W-KRR), perform similarly. As expected, the simple (unweighted) KRR model shows a performance gap. On the right, despite reaching the same eπror of the weighted KRR model, Nyström approximation can lead to important computational savings allowing for choosing a number of Nyström centers m < n.
7.2 Experiments on Benchmark Datasets
As regards real-world applications, we conduct experiments on commonly used benchmark datasets in the domain adaptation field (Wang & Sun, 2024; Wilson et al., 2020; He al., 2023; Dinu et al., 2023). The size of the original datasets is reduced case of memory issues with KRR and W-KRR when building the full Gram matrix K (see memory bottlenecks in Section 4). In these experiments, weights are estimated using RuLSIF method (Yamada et al., 2013; Liu et al., 2013). We consider 4 real-world datasets: HHAR (Stisen et al., 2015), WISDM (Kwapisz et al., 201 1), HAR70+ (Ustad al., 2023) and HARChildren (Tørring et al., 2024). These datasets consist of data collected from multiple users using wearable sensors, such as accelerometers and gyroscopes. To simulate covariate shift, we train each model on data collected from one user and evaluate on data from different user. We employ an RBF kernel with length-scale parameter 7 and regularization parameter X, both selected via validaanii. The results reported in Table are obtained using ALS sampling (see Definition 1), specifically through the BLESS fast implementation described in Rudi et al. (2018). For comparison, Table 2 in Appendix presents analogous results obtained with uniform sampling of the Nyström centers. Additional details on the datasets and experimental setup are provided in Appendix D.
Table 1: Performances of the various methods, both in terms of MSE and training/prediction time.
HAR70- (n 20000)
HARChildren 15006)
HHAR 15500)
WISDM 25000)
MSE
train pped
MSE
train p
MSE
t
MSE
tmii
pred
KRR
10
1614 2 16.
266
10
07
876 4
10.5 0.9 78 3280 48
38 t
W.RRR
5.0.1.2
1785
13.5
9.0.1...
18
1034 a
9.9
30
3
Ny W-RRR
5.1 1 0.2 80
4:
19
10 0.1
13.2 a 0.6
8.0
4.2
1.1
18 0.1
655 4 0.4 0.1
4.7 033
9.9 0.4 1.4 0.1
The above Table shows that the two methods using IW correction achieve the best and essentially equal performance. However, in terms of computational efficiency, our Nyström W-KRR method, offers significant time and memory savings. The number of Nyström points m required by Nyström W- KRR is 1100, 1800, 1400, and 1550, for HAR70+, HARChildren, HHAR, and WISDM, respectively.

---

8 Conclusions and Future Work
In this paper, we showed that even under covariate shift, random projection techniqess-pariiull particularly the Nyström method- can significantly enhance computational efficiency without any loss in learning performance. We provide new statistical bounds for our compressed Nyström algorithm, showing that it matches the optimal statistical guarantees of the full W-KRR model. Leveraging results from random projection theory, we developed novel technical proofs to account for the mismatch between training and test distributions and the potential unboundedness of the IW function. We evaluated the effectiveness of our approach through simulations and experiments on real-world datasets.
However, several questions remain open for future investigation. Although optimal rates achieved in the well-specified case, the misalignment between the training and test distributions relative to the larget function (see the source condition in Assumption 5) appears to play critical role empirically, as it can make covariate shift either benign or severely adversarial. A deeper understanding of this phenomenon may come from more detailed analysis of the constants in the learning bounds and their influence on the overall rate (see eq. (21) and the interaction between the covariance operators of source and target distributions).
Acknowledgments
L. R. acknowledges the financial support of the European Commission (Horizon Europe grant ELIAS 101 120237), the Ministry of Education, University and Research (FARE grant ML4IP R205T7J2KP), the European Research Council (grant SLING 819789), the U.S. Air Force Office of Scientific Research (EA8665-22-1-7034)) the Ministry of Education, University and Research (grant BAC FAIR PE00000013, funded by the EU NGEU), and MIUR (PRIN 202244A7YL). This work represents only the views of the authors. The European Commission and the other organizations are not responsible for any use that may be made of the information it contains. The research by Arnaud M. Watusadisi and L.R. was funded by a grant provided by the Liguria Region in collaboration with Leonardo SpA. The research by E.D.V has been partially supported by the MIUR grant PRIN 202244A7YL, by the PNRR project "Harmonic Analysis and Optimization in ddinite-Dimensionn Statistical Learning- - Future Artificial Intelligence Fair Spoke 10" (CUP BSC240004100077 and by the MIUR Excellence Department Project awarded to Dipartimento di Matematica, Università di Genova (CUP D33C23001 1 10001). E.D.V. is member of the Gruppo Nazionale per I' Analisi Matematica, la Probabilità e le loro Applicazioni (GNAMPA) of the Istituto Nazionale di Alta Matematica (INdAM).
References
Alaoui, A. and Mahoney, M. W. Fast randomized kernel ridge regression with statistical guarantees. In Advances in Neural Information Processing Systems, pp. 775-783, 2015.
Bach, F. Sharp analysis of low-rank kernel matrix approximations. In Conference on learning theory, pp. 185-209, PMLR, 2013.
Bach, F. On the equivalence between kernel quadrature rules and random feature expansions. The Journal of Machine Learning Research, 18(1):714-751, 2017.
Ben-David, S., Blitzer, J., Crammer, K., and Pereira, F. Analysis of representations for domain adaptation. Advances in neural information processing systems, 19, 2006.
Ben-Israel, A. and Greville, T. N. Generalized inverses: theory and applications. Springer Science & Business Media, 2006.
Bottou, L. and Bousquet, O. The tradeoff' of large scale learning. In Advances in neural information processing systems, pp. 161-168, 2008
Boucheron, S., Lugosi, G., and Massart, P. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford, 2013.
Calandriello, D., Lazaric, A., and Valko, M. Distributed adaptive sampling for kernel matrix
approximation. In Artificial Intelligence and Statistics, pp. 1421-1429. PMLR, 2017.
10

---

Caponnetto, A. and De Vito, E. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
Cohen, M. B., Lee, Y. T. Musco, C., Musco, C., Peng, R., and Sidford, A. Uniform sampling for matrix approximation. In Proceedings of the 2015 conference innovations in theoretical computer science, pp. 181 181-190, 2015.
Cortes, C. and Mohri, M. Domain adaptation and sample bias correction theory and algorithm for regression. Theoretical Computer Science, 519:103-126, 2014.
Cortes, C., Mohri, M., Riley, M., and Rostamizadeh, Sample selection bias correction theory. In International conference algorithmic learning theory, pp. 38-53. Springer, 2008
Cortes, C., Mansour, Y., and Mohri, M. Learning bounds for importance weighting. Advances in neural information processing systems, 23, 2010.
De Vito, E., Rosasco, L., and Rudi, A. Regularization: From inverse problems to large-scale machine learning. Harmonic and Applied Analysis: From Radon Transforms Machine Learning, pp. 246-296, 2021.
Della Vecchia, A., Mourtada, J., De Vito, E.,, and Rosasco, L. Regularized erm random subspaces. In International Conference on Artificial Intelligence and Statistics, pp. 6006-4014, PMLR, 2021.
Della Vecchia, A., De Vito, E., Mourtada, J., and Rosasco, L. The nyström method for convex loss functions. Journal of Machine Learning Research, 25(360):1-60, 2024.
Dinu, M.-C., Holzleitner, M., Beck, M., Nguyen, D., Huber, A., Eghbal-zadeh, H., Moser, B. A., Pereverzyev, S., Hochreiter, S., and Zellinger, W. Addressing parameter choice issues in unsupervised domain adaptation by aggregation. In The Eleventh International Conference on Learning Representations, 2023, URL
Drineas, P. and Mahoney, M. W. On the nyström method for approximating gram matrix for improved kernel-based learning. journal of machine learning research, 6(Dec):2153-2177) 2005.
Drineas, P., Magdon-Ismail, M.. Mahoney, M. W., and Woodruff, D. P. Fast approximation of matrix coherence and statistical leverage. The Journal of Machine Learning Research, 13())3375-3306, 2012.
Fang, T., Lu, N., Niu, G., and Sugiyama. M. Rethinking importance weighting for deep learning under distribution shift. Advances in neural information processing systems, 1996 2020.
Fujii, J., Fujii, M.. Furuta, T., and Nakamoto, R. Norm inequalities equivalent to heinz inequality. Proceedings of the American Mathematical Society, 118(3):827-830) 1993.
Gizewski, E. R., Mayer, L.,, Moser, B. A., Nguyen, D. H., Pereverzyev Jr, S., Pereverzyev, S. V., Shepeleva, N., and Zellinger, W. On regularization of unsupervised domain adaptation rkhs. Applied and Computational Harmonic Analysis, 57:201-2277 2022.
Gogolashvili, D., Zecchin, M., Kanagawa, M., Kountouris, M., and Filippone, M. When importance weighting correction needed for covariate shift adaptation? arXiv preprint 2xXiv:2303.04020 2023.
Guan, H. and Liu, M. Domain adaptation for medical image analysis: survey. IEEE Transactions on Biomedical Engineering, 173-11113 2021.
He, H., Queen, O., Koker, T., Cuevas, C., Tsiligkaridis, T., and Zitiik, M. Domain adaptation for time series under feature and label shifts. In International Conference on Machine Learning, pp. 12746-12774 PMLR, 2023.
Huang, J., Gretton, A., Borgwardt, K., Schölkopf, B., and Smola. A. Correcting sample selection bias by unlabeled data. Advances in neural information processing systems, 19, 2006.
Jiang, J. and Zhai, C. Instance weighting for domain adaptation in nlp. ACL, 2007.

---

Johnson, R. and Zhang, T. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Kanamori, T. and Shimodaira, H. Active learning algorithm using the maximum weighted log- likelihood estimator. Journal of statistical planning and inference, 116(1):149-16) 2003.
Koh, P. W., Sagawa, S., Marklund, H., Xie, S. M., Zhang, M., Balsubramani, A., Hu, W. Yasunaga. M., Phillips, R. L.., Gao, I., et al. Wilds: A benchmark of in-the-wild distribution shifts. In International conference on machine learning, pp. 5637-5664. PMLR, 2021.
Kpotufe, S. and Martinet, G. Marginal singularity and the benefits of labels in covariate-shift. The Annals of Statistics, (9(6))3299-3323, 2021.
Kpotufe, S. and Sriperumbudur, B. K. Kernel sketching yields kernel jl. arXiv preprint
UtXiv:1908.05818. 2019.
Kwapisz, J. R., Weiss, G. M., and Moore, S. A. Activity recognition using cell phone accelerometers. ACM SigKDD Explorations Newsletter, 12(2):74-2, 2011.
Lei, Q.. Hu, W., and Lee, J. Near-optimal linear regression under distribution shift. In International Conference on Machine Learning, pp. 6164-6174. PMLR, 2021.
Liu, S., Yamada, M., Collier, N., and Sugiyama, M. Change-point detection in time-series data by relative density-ratio estimation. Neural Networks, 43:72-83, 2013.
Ma, C., Pathak, R., and Wainwright, M. J. Optimally tackling covariate shift in rkhs-based nonpara- metric regression. The Annals of Statisties, 51(2):738-761, 2023.
Mahoney, M. W. Randomized algorithms for matrices and data. Foundations and Trends@ in Machine Learning, 3(2):123-224, 2011.
Mansour, Y., Mohri, M., and Rostamizadeh, A. Domain adaptation: Learning bounds and algorithms. arXiv preprint a arXiv:0902.34400, 2009.
Marteau-Ferey, U., Ostrovskii, D., Bach, F. and Rudi, A. Beyond least-squares: Fast rates for regularized empirical risk minimization through self-conccrdance.. In Conference on Learning Theory, pp. 2244-2340. PMLR, 2019.
Meanti, G., Carratino, L.,, Rosasco, I.., and Rudi, A. Kernel methods through the roof: handling billions of points efficiently. Advances Neural Information Processing Systems, 33:14410- 14422, 2020.
Myleiko, H. L. and Solodky, S. G. Regularized nyström subsampling in covariate shift domain adaptation problems. Numerical Functional Analysis and Optimization, 6553):165-188, 2024.
Pathak, R., Ma, C., and Wainwright, M. A new similarity measure for covariate shift with applications to nonparametric regression. In International Conference on Machine Learning, pp. 17517-17530. PMLR, 2022.
Quiñonero-Candee J., Sugiyama. M., Schwaighofer, A., and Lawrence, N. D. Dataset shift in machine learning. Mit Press, 2022.
Rudi, A. and Rosasco, I.. Generalization properties of learning with random features. Advances in Neural Information Processing Systems 30, pp. 3215-3225, 2017.
Rudi, A., Camoriano, R., and Rosasco, L.. Less is more: Nyström computational regularization. arXiv preprint S55i::1507.04711 28, 2015.
Rudi, A., Carratino, L., and Rosasco, L. Falkon: An optimal large scale kernel method. In Advances in Neural Information Processing Systems, pp. 1888-3898. 2017.
Rudi, A., Calandriello, D., Carratino, I.., and Rosasco, I.. On fast leverage score sampling and optimal learning. In Advances in Neural Information Processing Systems, pp. 5672-5682, 2018.
12

---

Schmidt, M., Le Roux, N., and Bach, F. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-11) 2017.
Schmidt-Hiehe Hieber, J. and Zamolodtchikov. P. Local convergence rates of the nonparametric least squares estimator with applications to transfer learning. Bernoulli, 30(3):1845 1844-187777777 2024.
Shimodaira, H. Improving predictive inference under covariate shift by weighting the log- lilliiiiihoodd function. Journal of statistical planning and inference, 90(2):227 224444 2000.
Smale, S. and Zhou, D.-X. Learning theory estimates via integral operators and their approximations. Constructive approximation, 26(2):153-172, 2007.
Smola, A. J. and Schökopf. B. Sparse greedy matrix approximation for machine learning. In Proceedings of the seventeenth international conference on machine learning, pp. 911-918, 2000.
Steinwart, and Christmann, A. Support vector machines. Springer Science & Business Media, 2008.
Stisen, A., Blunck, H., Bhattacharya, S., Prentow, T. S., Kjærgaard, M. B., Dey, A., Sonne, T., and Jensen, M. M. Smart devices are different: Assessing and mitigatingmobile sensing heterogeneities for activity recognition. In Proceedings of the 13th ACM conference on embedded networked sensor systems, pp. 127-140, 2015.
Sugiyama, M. and Kawanabe, M. Machine learning in non-stationary enviromments: Introduction to covariate shift adaptation. MIT press, 2012.
Sugiyama, M. and Ridgeway, G. Active learning in approximately linear regression based on conditional expectation of generalization error. Journal of Machine Learning Research, 7(1), 2006.
Sugiyama, M., Suzuki, T., and Kanamori, T. Density ratio estimation in machine learning. Cambridge University Press, 2012.
Sun, Y., Gilbert, A., and Tewari, A. But how does it work in theory? linear svm with random features. In Advances in Neural Information Processing Systems, pp. 3379-3388, 2018.
Tørring, M. F., Logacjov, A., Brændvik, S. M., Ustad, A., Roeleveld, K., and Bardal, E. M. Validation of two novel human activity recognition models for typically developing children and children with cerebral palsy. Plos one, 19())e0308833, 2024.
Ustad, A., Logacjov, A., Trollebo, S. Ø., Thingstad, P., Vereijken, B., Bach, K., and Maroni, N. S. Validation of an activity type recognition model classifying daily physical behavior in older adults: the har70+ model. Sensors, 23(5):2368, 2023.
Vapnik, V. The Nature of Statistical Learning Theory. Springer Science & Business Media, 1999.
Wang, X. and Sun, R. Domain adaptation of time series classification. IEEE Access, 2024.
Wen, J., Yu, C.-N., and Greiner, R. Robust learning under uncertain test distributions: Relating covariate shift to model misspecification. In International Conference on Machine Learning, pp. 631-639, PMLR, 2014.
Wiens, P. Robust weights and designs for biased regression models: Least squares and generalized m-estimation. Journal of Statistical Planning and Inference, 83(2):395-412, 2000.
Williams, C. and Seeger, M. Using the nyström method to speed up kernel machines. Advances in neural information processing systems, 13, 2000.
Williams, C. K. and Seeger, M. Using the nyström method speed up kernel machines. In Advances in neural information processing systems, pp. 682-688, 2001.
Wilson, G., Doppa, J. R., and Cook, J. Multi-source deep domain adaptation with weak supervision for time-series sensor data. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1768-1778. 2020.
13

---

Woodruff, D. Sketching as tool for numerical linear algebra. arXiv preprint arXiv: MrXiv:1411.4357 2014.
Yamada, M., Suzuki, T., Kanamori, T., Hachiya, H.,, and Sugiyama, M. Relative density-ratio estimation for robust distribution comparison. Neural computation, 25(5):1324-15 1370, 2013.
Yamazaki, K., Kawanabe, M., Watanabe, S., Sugiyama, M., and Müller, K.-R. Asymptotic bayesian generalization error when training and test distributions are different. In Proceedings of the 24th international conference on Machine learning, pp. 1079-1086, 2007.
Zhang. C., Zhang. L.,, and Ye, J. Generalization bounds for domain adaptation. Advances in neural information processing systems, 25, 2012.
Zhang, T. Learning bounds for kernel regression using effective data dimensionality. Neural Computation, 17(9):2077-22) 2005.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
14

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Section 3, Section 5, Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 7, Appendix D
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
15

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e-g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: datasets are open access, see Appendix D. The implemented algorithms are classic models implementable with standard tools such sklearn.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https//nips.cc/public
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (htips: for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Section 7, Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
16

---

Answer: [Yes]
Justification: Section 7
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emoor bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section 7, Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https//leeump.cccoooldchhheeneee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
17

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical work to provide understanding of basic machine learning models, which aims to advance the field of Machine Learning. There might potential
societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Section 7, Appendix D
18

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
19

---

Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (ttp://ceeui..ccccooocccee//555) for what should or should not be described.
20

---

A Derivation of the estimators
We define some quantities we will need when deriving our estimators. Following Section 2, we define the sampling operator 2m H + R associated with the subset (T1...., _mp C {.1..... 2n as
2m Hm IRT, (Zml) (J, Hm.
(24)
with its adjoint
m Σ
Zn : - Hms 2
C
KKz Vž E Rm.
(25)
1=1
Moreover, consider the singular value decomposition (SVD) of 2m and 2m
2m = UDV"
Z =V
with U: R* + Rm, D: - R* the diagonal matrix of singular values sorted in non-decreasing order D = diag(O1..... ................................ TT) with 01 > > T > 0, V R + Hm. k & m such that U = Ig and VVV Ιa- The projection operator with range Hm, is given by P.. = VV* We used this fact in Section 4. We derive an expression for the KRR minimizer when considering IW correction and Nyström approximation.
Lemma (Nyström W-KRR estimator). mizer can be written as
Given the minimization problem (12), the unique mini-
Px = VVV S + AI)-' M..
(26)
where x > 0, y (yi....,bbo ya) and the matrix M diag(u((1)) .... (((n))
Proof. Eq. (12) can be rewritten as
Ma SPmm - -m]|== (M (MM -1)
(27)
Using first-order condition we have that
P
Pms Sth M
3P Px
2 Sm SMMi + 2APx.. = 0,
(28)
n
n
that is
(P. MrS Sn)) Sm MaTj.
(29)
Replacing P., = VV* we obtain
V Xnl)V' fxr VV S* "MMy
(30)
Multiplying both sides by V and using that (V* S* SV + And) invertible, we obtain
v f S +
S*
(31)
The result is obtained multiplying both side by V and remembering that frr E Hm.
We can express our estimator in an alternative form which will be useful the actual implementation of the algorithm.
Lemma (Nyström W-KRR estimator, representer theorem form). The above minimizer Fr.... can be also written as
m
(x)
C Σ 1=1
K(),, 7= (RT M R Rum + nd n RT mm
Tm Mu
(32)
where Rum K F.))
S2; RRnxm, (Rum)is = K (xte, and Rmm 2n E Rmxx (R (Rmm)ss
21

---

Proof. Eq. (26) can be rewritten as
fx.m V(V' S" + MaN
-VDUUU-'(V' My + Anl)--D--UUUDY M.. = (2m M,. + AZ ) 7,m S* MuT
(33)
where we used (FGH)1= H (see the full-rank factorization of the pseudo-inverse (Ben- Israel & Greville, 2006)) with F =UUD, V* SV + AnI and H DUT. Using the definitions of Kmm and K we have
(K Mw Kmm + Ankmma) RT Muy S Mc + AZ AZ) Mw
(34)
and substituting this expression above we get the result.
Main proofs
To prove Theorem 1, we will need the following two propositions.
Proposition (Empirical Effective Dimension). Let (A) = Th Under assumption
for any 5 > 0 and (o) 1- 6,
|E|| then the following holds with probability
(w(()) N (A)
2
Ng
Proof. Let's call N 0 (A) = ((A) to simplify the notation. The proof partially follows the structure of Proposition 1 Rudi et al. (2015), with some complications deriving from the presence of the (pos- sibly unbounded) weights. Define D 1/2 ( - )
1/2 Using Lemma 18 in Gogolashvili al. (2023) we have that [| Ilus < 3/4, when ndl+9 > 64 (W + +²2) (2)= log (3). We can rewrite
(a(A)- = Tr 5-1
S. mw - -ΣE"' = Tr A-1 { -E Σ
(35)
A ATrE 1/2 (1 (I- "= (SnN Σ -
(36)
ATTE 1/2 (I-Bw) BBrー1/12
(37)
Following Rudi al. (2015) and using that, for any symmetric linear operator - H the following identity holds
(I-X) = x +
Applying the above identity with X = B
> A 1/2 (--B)) B" 1/2
< Tr - 1/2 BUN 1/2
E. x 1/2 1112 1/2 (I Bu)
-1 Bus 1/2
Tr + >
To find an upper bound for notice that
11
71
22

---

with 5. = (Kx, A kz,) ² E R ii.d. random variables with E [rz] and E(si]. Using Lemma 18 in Gogolashvili al. (2023) and general version of Bernstein inequality requiring. instead of boundedness, only an appropriate control of moments (Boucheron et al., 2013), we have with probability greater than
W An
Nax (o)(1)) Alton
2 3
A A
oo
log
As regards B, write B = ||Ql12s where Q = 21/25x 1/2 Bu0 (I- Bu0
-1/2
moreover
1101 < | 1/2 2 A300 1
(1 B
-1/2112
< 4 B 1 Iis
x
HS
11/2 2
since (1-
Bw)
< (1
1- < 4, for n\ > 64 (W + + (A) log" (3).
Using again Lemma 18 in Gogolashvili et al. (2023) and version of the Bernstein inequality for Hilbert space-valued random variables (see for example Caponnetto & De Vito (2007)) we obtain with probability greater than 1 8
2
W
N Nox(2))
log 2 (5)
B
< 16
+
An
Al+on
Putting all together, with probability 1 1- 8:
2
W
Nax (A)'
4
W
Nox (2)'-9
(c(A)-N(1)) <4
4
+
log
+
16
+ o
log 2
An
Xt+an
An
\l+0n
(38)
W
W
4
<
4
+ +oV
log
+
16
+ +ov 27(1-o)+1+0m
log²
An
X0(1-a)+1+on
An
(39)
Using that A(1) > |ΣΣ1'| > 1/2 X <
|Σ||
we have
-N())
(40)
W
1
4 5
to +oV
log
+
(41)
N Wose(A)DN)
Nose (A)=+922ton
W
(4)
+1
+
log² 2
Nosse (A)
(42)
Noye(1) (2)Am
Nogg( (A)
8
2W
4
4 5
2W
4
log² (1))
4
+ Vo
log
+ 16
+
V/
Nose (2). (43)
An
luten
An
Xitan
Then for 256(W+o") log")
< A & |ل|| with probability 1-8
n
(a) 2N1())
Proposition (Nyström approximation with ALS sampling). Let (1((t)" be the collection of i=1
approximate leverage scores. Let À > 0 and P^ be defined Px(t) ((x)/E,en' (y(A) any
23

---

m > 144T pip (A) log Sn 8 E N with N [I....... Let = (ii.....iin) imm) be collection of indices independently sampled with replacement from N according the probability distribution Px. Let Pm be the projection operator on the subspace Hm span { Kr, x; j E J and J be the subcollection of 3 with all the duplicates removed. Under Assumption 3 and 6, for any 6 > the following holds with probability 1 25
II(I Pm)x 1// <
when the following conditions are satisfied;
there exists T > and Ao > O such that (T:(1) are T T-approximate leverage scores for any t > Xo (see Definition 1).
do V 256(W+0²) Ing2 (4/8) 40-24+14
Proof. Let's call E Egpe to simplify the notation. Define 5/4. Next, define the diagonal
when Px(1) O, where ((i) is the number of times the index present in the collection J. We have that
matrix H E R=*x with (H)s 0 when Px( and (H) nq(()
(f)
HS
1 m
g()) K2. Kz. (1(1)
1
Σ w(x,))
Kay Kay- Px()
m
JEJ
Now, considering that
a(z) Px(3)
0 for any j E J, thus ran S H. = Hm. Therefore, by using Prop.
3 and 7 in Rudi et al. (2015), we exploit the fact that the range of Pm is the same of S H to obtain
111 Pm)
1/2 2
> ( + +1)
1/2
11/
A
3(A)
with 3(A) = Amax 1 ( HSw
Considering that the function (1 xx- -1 is increasing on -00 < x < 1, in order to bound A/(1 3()) we need an upperbound for (A). Here split B(A) in the following way,
B(A) < Amax (2x 1/2 [2- Em)) Σx 1/2
Amax [>x (S...
St S. Σx 1/2
(A)
(a(A))
31 can be bounded as in eq. (44).
As regards 82:
32(A) < |=1/2
1/2 (I.. - - 1/2
< | 1/2 1 |
|
Dwe - 3: Sw)) E0
mnd
Let
B₂(A) Bs(A)= S|1 (In- - S HSr $m = ||5 1/2 1/3 H $1112
Note that S. = ( S S. x1) (Ru + xXn) Kn since Kn =nS, n with
(Rw),s = w(x) (2, 1/2 (z),
Thus, if we let T be the eigendecomposition of k,,, have that (R + XnI) R
U(D - An T and thus S-13; = U(D + DUT In particular this implies that S. =UQ1/Q11/20 with Q (D AnI) Therefore have
Ba(A) = | 1--1/3 --)- 1-12 = @/ -1-UQUH
H2
24

---

Consider the matrix A = -22 and let be the i-th column of A, and e, be the i-th canonical basis vector for each E N. We prove that ||a:ll = (x)),, the true leverage score, since
a 1| = Q ei e, UQUT; = (RRi+ Ant) -1 Rw
((())
Considering that Ek=1
q(k)
agag = =Ei= 1
Pati) we have
PA(K]
Ba(A) - AA - m
a.a
Px(1)
Moreover, by the T-approximation property of the approximate leverage scores (see Def. 1 in Rudi al. (2015)), we have that for all E (1....,n). when À > Ao the following holds with probability
1 1-
(a(1) = 4(A)
T 4(A) 4,4()
= T ||ll|
AAT
Then, can apply Prop. 9 in Rudi et al. (2015), so that, after union bound, obtain the following inequality with probability 5 T:
2 2| log
2n
2|A 2T2 Tr AAT log
2n
2 2og 2n
21 w (A) log 2n
(A <
3m
m
3m
m
(RRu + 2nt)
-1 Rw
where the last step follows from ||
1 and Tr (AAT)
Tr (ind (A).. Applying proposition 1 we have that (N) & 3Nox (A) with prob-
ability 1 T,, when
128 (4/6)
1+9
E |E|| Thus, by taking a union bound again, we
n
have
2oo 2n
16T pt (A) log 2n
(A(A) &
7
3m
with probability 2T - 8. The last step is to bound
|> 1/2 we
as follows
12 Aw
||
| E Aw Σx 1/2 - - -||++= 1/2 (Ew Σ² E < 11+n.
We can bound v) using Lemma 18 in Gogolashvili et al. (2023) (see eq. (44)). Finally, by collecting the above results and taking a union bound we have
with
|>>1//2 SSn - x .
1/2
W
o2N p (A)2-9
2 log
16T NoTe (A) 2 2og 2n
(A) log 2n
B(A) < 4
+
$V
+11 + 1))
An
1n
3m
m
with probability 1 - 4T 8- = - 28 when
256 to )) log (4/88)
& A & |
Note that, if
select 256(W+o")) Inn" (4/8)) 713-0)++4
E|| and > 1447 N 23 (A) 8n have
"
B(A) < 5/6, so that
|1- P..) 2112|2 < <6A
with probability 1 - 28.
We can now proceed with the proof of Theorem 1.
25

---

Proof of Theorem 1
proof of Theorem 1. We split the excess risk
R(((mm) - R(sHe) 1/2
fxmm - 171 1/ = ||1 - S20
(V E. V + +1) -v. 3 Ma - [H0 7
/V/2V(VV* Snm V + A1) V' My - 3 3544)
+
1 v(V S + ay) VV S.. 1
H
8
Term &
11/25-1112
1/2 wx
12/2 V(V E Ewa v) -1 1 wn
51/2
2//
xx
5/2
Mw - -S1+) 14
A1
A1 < Σ1/25
1/2
21/25-112 1/2
EB
wd
Ag
using
lemma 8 in Rudi et al. (2015) it's easy to show that
$1/2 Lnd
u E St/2///l and therefore
the only possible values for A2 are 0 and 1. Then
A < 1
Ag = 3: using proposition 7 in Rudi et al. (2015) we have
B < 1 - b
if Amax
Σ 1/2 Emm) ) 1/2
<1. 1.
Applying Lemma 18 in Gogolashvili et al. (2023) we get, with probability greater than 1 8
Amax Σ 1-1/2
Sym ) 1/2
|> (x. S.m M
4
W An
+
o2N p3
(A)2-9
log
2
HS
Xltan
(44)
and for nd2+9 > 64 (W + N (A)2-9 log² (3) with probability greater than 1-6 8 the above quantity is less or equal than 3/4.
Ay:
To control this term we use lemma 19 in Gogolashvili et al. (2023), where & wr. We obtain that, with probability greater or equal than 1- 6 Σ 1/2 ww:) Kr
71 Σ & - E[E]
= - 12 M 3
<B
W
+
o2N oe (2)1-9
log
nyA
n\g
7
26

---

Term B
As regards B. following Rudi et al. (2015) we proceed as follows.
Noting that
V(v"Ew V' VV* VV*, we have
I-V(V* V2 V)- = DIV
+ SV
I - VV)-
(VV"EAAV)- (1 VV") + AV EVV'"-VV--'
= (1- + EV ''-- V(V V) -' Ewx (1 (V-)
By assumption 5, we have
fm H
<
|
< fxl'full & R. Define r' =
1/2 to simplify the notation. Using the above decomposition, rewrite term B as
B <
1/2
T V(V EVV.E. E
| fx H
<R
1 1/2
| (I - VV-) Σx + RA
1n
1/2
1:/2 V( 12
R
Smm V) V 201
|| |
11/2
/x/² (T
VV*) Σ
<R(1 + (0)
|2:// (1 (1-
+R3A A
11/2V
1/2
VV
B1
8.2
with 0
-//2>>110" 1/2
B.I::
B.1 B11 = ||=1|1//0 (1
(v-) 2x' < <|
( - -vy | -v 2x
Since VV* is a projection operator, we have that (1 VV*) (1- (1-V))"" for any 0. therefore, by applying Cordes inequality (see proposition 6) to
(1 1--vvV Σx we have
-a- - ---v 2
< [I- VV x 2nd
This term can be controlled using Proposition 2 above.
B.2:
B.2
|1
[ ア < Σx
< 53//2(11 -) E/1 /|
/ 21
< 82r >
( v) 1/2 (V.S
-1
(vr 177²
= 8
(V
v + +
-01/2r))
< //21//2 = =3,,
where the first step is obtained multiplying and dividing by En the second step by applying Cordes incquality, the third step by Prop. in Rudi et al. (2015).
Putting all together, for [256 log log (4/8)
711-0++44
x &
[ and m > 1447 log 8n 8
with probability greater or equal than 1 8
(R((xmm) - R(HH) 1/2
W
0²
8 8
4B3²
log
+ 3RR - 300x + +R32..
27

---

Under the above conditions on À we have that B < and
0 < 2 and then for
(25 log" (1/6)
Tp oFtl
| and m > 1447
log 8n with probability 8
greater equal than 8-8
1/2
W
o²
8 log 8
R(fxmm) -R(22e)
& 64B
+ 43RA
nd
C Known results
In this section, we derive tight bounds for the effective dimension (A) defined in Definition when assuming polynomial decay of the eigenvalues (Z) of the covariance operator Σ. Proposition 3 (Polynomial eigenvalues decay, Proposition 3 in Caponnetto & De Vito (2007)). for some y E Rt and 1 < 3 +00
then
3 3-1 x 1/8
N6(1 &
(45)
Proof. Since the function a/ 0/(a + A) is increasing in and using the spectral theorem UDU combined with the fact that TrUUDU*) = Tr(U(U"*)) D))
TrD
N,(A)) =
(46)
0 +
Y +
The function 7/(7 + 2) is positive and decreasing,
100
N₂(A) <
dr
0
7 x
1/8
dr
7 + 78
< 7
1-1
A
1/8
(47)
3
since ( < 3/(3--1)) - 1).
Further improvements can be found assuming exponential decay of the eigenvalues (Σ{ of E. Proposition 4 (Exponential eigenvalues decay, Proposition Della Vecchia et al. (2021)). ffr some 7, 3 E IRto, & ye 35 then
N₂(A) < log(1 + 7/A)
(48)
B
Proof.
4.00
N₂(A)= = Σ
1 + Mesi <
1 1 N dx,
(49)
1+
1/0
==1
1=1
t=1
where X' A/7. Using the change of variables
a0 we get
log - log(1 + X't) +00
(49) = B J
1+ Xt
dt
B 3
t 1 + Nt.
dt
B
1
log
t.
)] +00 1
log(1/X)) + log(1 + x
(50)
1+ Xt
3
28

---

So we finally obtain
N,(A) & / [og(7//) + log(1
+ log(1
+/>1)/ log(1 + 7/A)
(51)
Next proposition gives some relations between weights and covariance operators.
Proposition 5. Suppose that pe is absolutely continuous with respect p'x, and the Radon-Nikodym derivative dp' /d'xx is bounded by G E R. Then
|
&G,
see Gogolashvili et al. (2023). Moreover, w(x)) oo and v(x) > 0 for all x. E X, with and defined as in eq. (3) and (18) respectively, then
Proof. For operators and on H. denote by A > B that A a non-negative operator. Let :==lldp 1|dp' / 1o For all f E H. we have
(f,EfM f. ( (kaf())d0((())
- ((aaaa)) (
do' 4 (+) dox
= P(x)
Therefore, we have
E M GE, & G(E, + A1)
EE, + X1) & GI,
where 0:
H + H is the identity operator. This implies assertion. The second part comes simply from the fact that
EEE + 2) 2) < G. which proves the first
(EEN) = (x)
dpk
dpk dpx
(z) / (()))())) -0
| (f.Enf)
dp
((z)
(Cordes Inequality Fujii et al. (1993)). Let A, B two positive semidefinite bounded linear operators a separable Hilbert space. Then
Proposition
| BA < ||B|
when 0 < s < 1.
D Experimental Details and Datasets
This section includes some additional details on the experimental setting and detailed summary of all the datasets presented.
The four datasets consist of data collected from multiple users using wearable sensors, such as accelerometers and gyroscopes. We allocate 1% of the test dataset for weight estimation, reserving the remaining 99% for predictions. Weights are estimated using Relative Unconstrained Least- Squares Importance Fitting (RuLSIF) method, which minimizes the relative density-ratio divergence between distributions (Yamada et al., 2013; Liu et al., 2013).Th experiments were conducted in Python 2018 MacBook Pro with 2.3 GHz Intel Core i5 Quad-Core processor, 16GB of RAM, and no GPU.
We give here brief description of the four datasets.
29

---

The HHAR dataset (Stisen et al., 2015), accessible on DR-NTU (Data), dataset DOE: https://tboorr//02119999//0/00
version used: 3.0 (May 27, 2022). license: CC BY-NC 4.0, authors of the dataset version: Mohamed Ragab and Emadeldeen Eldele. It comprises 13,062,475 samples with 10 features for human activity recognition using smartphone and smartwatch sensors. It explores the effect of sensor heterogeneity on activity recognition algorithms, aiming to classify physical activities, Data were collected from accelerometer and gyroscope sensors during activities like Biking, Sitting, Standing, Walking, Stair Up, and Stair Down. Nine users participated, using 4 smartwatches (2 LG, Samsung Galaxy) and smartphones (2 each of Samsung Galaxy S3 mini, Samsung Galaxy S3, LG Nexus 4, and Samsung Galaxy S+). Features include accelerometer readings (x, y, z). user ID, device, model, and activity labels. Non-essential columns- -indx, arrival time, and creation time-were removed. The categorical columns (device and model) were converted to numerical values. User A has 1,218,871 samples designated training data, from which 15,500 samples were randomly selected, while user H provides the test data.
The HAR70+ dataset (Ustad et al.. 2023), available from the UCI Machine Learning Repository, dataset DOI: https://doi.org/ http:/ii.rr/00.4444//14 10.24432/C5CW3DD version used: Latest version available via the Norwegian Centre for Research Data (NSD), license: CC BY 4.0 (Creative Commons Attribution 4.0 International), dataset authors: Aleksej Logacjov, Astrid Ustad. It contains 2,259,,597 samples with 6 features for activity classification. Data were recorded from 18 older adults (ages 70-95) wearing two Axivity AX3 accelerometers at 50 Hz for 40 minutes in a semi-structured, free-living setting. Five participants used walking aids. Sensors were placed on the right thigh and lower back. Activities such as walking, shuffling, ascending/descending stairs, standing, sitting, and lying were annotated frame- by-framee using chest- camera video. For training and testing, used data from two files: 518.csv, containing 141,714 14 samples with 6 features, and 516.csv, containing 138,278 samples with 6 features. From 518.csv, 20,000 samples were randomly selected for training. To introduce covariate shift and study feature selection, the timestamp and thigh accelerations in the and directions were excluded.
The HARChildren dataset (Tørring et al., 2024), available on DR-NTU (Data), dataset DOI: https://doi.org// ort./... 10/E/CCCC version used: published on August 30, 2024, license: CCO 1.0, dataset authors: Marte Fossflaten Tørring et al. It contains over million samples with 8 features for activity classification. It includes data from 63 typically developing (TD) children and 16 children with Cerebral Palsy (CP), classified at levels I and II of the Gross Motor Function Classification System (GMFCS). These children wore two accelerometers, on the lower back and thigh. The features initially included timestamp and accelerometer readings (x, y. 7), but the timestamp was removed during preprocessing. The recorded activities include walking, running, shuffling, ascending and descending stairs, standing, sitting, lying, bending, cycling seated, cycling standing, and jumping. For training and testing, two files were used: 004.csv, which contains 354,139 samples, and 010.csv, which contains 238,574 samples. From 010.csv, 15,000 samples were randomly selected for training, while 004.csv was used for testing.
The WISDM dataset (K (Kwapisz et al., 2011), available on DR-NTU (Data), dataset DOI: https://doi.or/// 0. 1999//99//WWSSB version used: 1.0 (May 27, 2022), license: CC BY- NC 4.0, dataset authors: Mohamed Ragab and Emadeldeen Eldele. It contains 1,098,209 samples with 5 features from accelerometer and gyroscope data collected 20 Hz using smartphones and smartwatches. Data were recorded from 36 users performing 18 activities for 3 minutes each. Features include a user ID, activity code (label), and sensor readings (x, y, z). User 12 has 32,641 samples designated as training data, from which 25,000 samples were randomly selected, while user 19 provides the test data.
common way to specify the grid of possible values of À is to consider geometric series. Remark 1 (Geometric grid). Let Amin and Xmaz the smallest and largest values of the regularization parameter we wish to consider and let
1/1Q-1)
b Ammax
Amin
We generate geometric grid of Q values of the regularization if for q 1,...,00 Q. we let
Xy ba Xmins
30

---

so that X1 Amin and xq= = Amar.
We used A1 10 4 Aq = 1 and Q 10 to generate the geometric grid. We also propose method for generating geometric sequenee of y values, derived from distinct formulas for even and odd indices.
Remark 2. The following values represent the parameter yy for the Gaussian kernel:
10-3+
k odd,
7kk
5 10 10-3+
k even,
k= 1=1,2...,,6
We optimize the hyperparameters using hold-out cross valsdaana,,,,,,,, partitioning the dataset into 70% for training and 30% for validation. For each combination of hyperparameters À and y, we train the model on train and Yrain and validate on Xva and Bval-
HISARt Dhcanee
HARCh Idren dotaset
n:1 5500 617
n-15000, 5-7
Weigrtad
Wasgtte
5
Hyazon 1011
20
25
3
20-
2
250
500
750
1000
1250
1500
1750
1020
1220
1500
1750
Figure 2: These plots illustrate the results in Table I for HHAR and HARChildren datasets.
As regards the simulations, we report here the parameters used to generate the results in Figure 1: A 50 (that we consider misspecified), per (0.7, 0.7). of diag(0.7,00. 0.7), fre (1.8, 1.8),
2 = d0ag(0.5, 0.5), e" 0.2, e C2 10.
Table 2: Performances of the various methods, both in terms of MSE and training/prediction time using uniform sampling.
HAR70 (n 2000)
HARChsldren (n 15000)
HHAR (n 15500)
WISDM (ir 25000)
MSE r train (5) ppred (s)
MSE
tmin (s) 1 pred (s)
MSE
I train (6) I poed (s)
MSE
tmin (s) ppedd (s)
KRR
10
1694 2 15.0 0.5
26.6 a 0.9 702 12 10.2 n.4
3.7 474.03 0.3
870 1 10.5 0.0.9
7.8 0.1 3280 68
3
W-KRR
002
1785 2 16.1 +03
185+00
088
800 + 26 9.0 U.1
1.8 0.3
1034 #0
49-+00 0.1
488 02 396 90
33+22
Ny W-KRR
5.0 0.1
07
0.1
12.9 0.2 57
2.2 6.2 L.
1.79 4: 0.01
5.9 0.1.
134 0.2 48 18 0.1 32
7.2 0.1
Table 2 shows that even when using uniform sampling, the two methods with importance weighting (IW) correction achieve the best and essentially equal performance. However, the number of Nyström points m required by Nyström W-KRR is 5500, 6500, 1750, and 4500 for HAR70+, HARChildren, HHAR, and WISDM respectively, which represents increase compared to the ALS method.
31


Reviews:
[{"review_id": "b8kaLyz6Gf", "reviewer": "Reviewer_zfAH", "summary": "This paper tackles the covariate shift problem in nonparametric regression within reproducing kernel Hilbert spaces (RKHSs). While kernel methods offer strong statistical guarantees, their high computational and memory costs limit their scalability. To address this, the authors propose using random projections to define a random subspace of the RKHS, aiming to balance computational efficiency and statistical accuracy under covariate shift. The study demonstrates that this approach can yield substantial computational savings without sacrificing learning performance, even when training and test distributions differ.", "questions": "It is well known that the Nyström method can be used to scale up a wide range of computations involving kernel matrices. I am curious how the statistical guarantees presented in this work offer new insights into the practical application of the Nyström method under covariate shift—particularly regarding the choice of sampling scheme, determination of sampling size, and the trade-offs in performance compared to exact computations.  Specifically, while statistical guarantees are valuable, do they shed light on why subsampling often leads to improved performance in practice especially in case of large sample size in terms of predictive accuracy?\n\nI would like to clarify whether all the empirical and theoretical results in this paper are based solely on the approximate leverage score (ALS) sampling scheme. If so, I would encourage the authors to include a comparison with uniform random sampling, particularly in the empirical evaluations. In many cases, random sampling is not only significantly cheaper but can also yield comparable or even better accuracy than ALS (see, for example, Figure 1, left panel in [1]). Including results based on random sampling would provide valuable insights and broaden the practical relevance of the work.\n\n[1] Petros Drineas et al.,  An Experimental Evaluation of a Monte-Carlo Algorithm for Singular Value Decomposition.", "limitations": "n/a", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\nThe authors derived excess risk bounds for the Nyström predictor defined in Eq. (12), and show that the Nyström approximation does not compromise the state-of-the-art convergence rates, while significantly reducing the computational burden.\n\nWeaknesses \n\n1. I am not sure whether the provided analysis could shed light on practical applications (see questions), and also  in interpreting the empirical results reported in Table~1 where the MSE of Nystrom method in KRR is even lower than without this approximate sampling scheme.\n\n2. The authors employ a more sophisticated sampling strategy using approximate leverage scores (ALS) instead of uniform random sampling. However, in many cases, random sampling can be both more accurate and significantly cheaper than ALS (see related questions for details). In this regard, the analysis in this paper may be less generalizable or practically advantageous than it appears. (see more details in questions).", "was_revised": true, "final_justification": "I have read through the authors responses, which addressed some of my concerns.", "rebuttal": "Thank you for these insightful questions.\n\nAbout the points you raised:\nOur analysis provides new insights in three key directions:\n\n1.\t**New insights in Nyström applications**:\nWhile the Nyström method is widely used to accelerate kernel computations, most existing analyses assume identical training and test distributions. In contrast, our results explicitly account for covariate shift, including cases with unbounded importance weights, and prove the versatility of the method also in the domain adaptation framework. We show that approximate leverage score (ALS) sampling preserves the optimal convergence rates of full importance-weighted KRR even under covariate shift.\n\n2.\t**Determination of sampling size:**\nOur risk bounds specify how the number of Nyström centers $m$ should scale with the sample size $n$, the regularization parameter, and the complexity of the hypothesis space (via the effective dimension). This gives explicit guidance on how to choose $m$ to achieve the same statistical accuracy as the exact algorithm while reducing time and memory costs by orders of magnitude.\n\n3.\t**Why subsampling can improve accuracy in practice:**\nTheoretically, subsampling does not degrade predictive performance asymptotically. In practice, particularly for very large datasets, the effect the reviewer is mentioning, where accuracy is even improved, can sometimes be attributed to reduced numerical errors and implicit regularization from working in a lower-dimensional subspace. This is consistent with Table 1, where the Nyström approximation achieves accuracy statistically comparable to the exact method despite significantly lower computational cost.\n\nOverall, our work extends Nyström guarantees to a nontrivial covariate shift setting and provides explicit prescriptions for sampling design and computational–statistical trade-offs that were previously unavailable.\n\n\n**Clarification on Table 1 interpretation**\n\nThe results in Table 1 are consistent with our theoretical findings:\n\n1.\tWhy standard KRR performs worse:\nStandard KRR ignores covariate shift, being trained and evaluated under the assumption that training and test data follow the same distribution. While harmless in well-specified models, this assumption degrades performance in more general misspecified settings. The experiments confirm that methods incorporating importance-weight correction consistently outperform standard KRR.\n\n2.\tComparison between W-KRR and W-Nyström KRR:\nOur theoretical analysis shows that W-Nyström KRR matches the statistical guarantees of W-KRR while greatly reducing computational cost. Table 1 confirms this empirically: the mean squared error (MSE) of W-Nyström KRR is **statistically indistinguishable** from W-KRR (considering the provided confidence intervals), with small fluctuations attributable to Nyström point selection (via ALS) and cross-validation randomness. Importantly, W-Nyström KRR achieves this accuracy with much lower runtime, which is precisely its intended benefit.\n\n**Uniform sampling vs. ALS**\n\nWe agree that uniform sampling is often competitive in practice and is simpler and cheaper to implement.\nHowever, ALS sampling has stronger theoretical guarantees, leading to tighter error bounds because it adapts to the spectral structure of the kernel matrix. Uniform sampling is agnostic to these properties and typically requires more Nyström points to achieve the same approximation accuracy. As shown by [2], leverage score sampling matches the statistical guarantees of exact kernel ridge regression with fewer centers than uniform sampling, often improving numerical stability and convergence speed (e.g., FALKON-BLESS vs. uniform sampling). In fact, their results show that, although computing leverage scores is more expensive upfront, uniform sampling can ultimately be more costly because it often requires a larger sample size to achieve the same accuracy. This observation is empirically confirmed in [3], where Table 4 shows that, despite its lower sampling cost, uniform sampling frequently needs more Nyström points than leverage score sampling to match accuracy. As a result, even without the overhead of computing leverage scores, uniform sampling can end up being more expensive overall in terms of both runtime and memory.\nNotice also that the mentioned paper by [1] studied a simpler norm-based weighting scheme—not modern leverage score sampling—and in the context of approximate SVD algorithms. A more recent paper of the same author focusing on leverage score sampling and its benefits is instead [4].\n\nSince our paper focuses on theoretical guarantees and validation of those results, we adopted ALS sampling to align with the setting in which these guarantees hold. That said, extending our experiments to include uniform sampling is straightforward, and **we have already added an additional table in the appendix to empirically illustrate this comparison**. As expected, our results are consistent with previous findings: while uniform sampling can achieve accuracy comparable to ALS, it often requires sampling significantly more Nyström points and, in some cases, even results in higher overall computational cost, effectively nullifying the benefits of its simpler sampling scheme.\n\n\n**References**\n\n[1] Drineas, Petros, et al. An Experimental Evaluation of a Monte-Carlo Algorithm for Singular Value Decomposition, LNCS, 2003.\n\n[2] Rudi, Alessandro, et al. On Fast Leverage Score Sampling and Optimal Learning, NeurIPS, 2018.\n\n[3] Della Vecchia, Andrea, et al. Regularized ERM on Random Subspaces, AISTATS, 2021.\n\n[4] Drineas, Petros, et al. Fast Approximation of Matrix Coherence and Statistical Leverage, JMLR, 2012."}, {"review_id": "IVf378jyvI", "reviewer": "Reviewer_wwtt", "summary": "This paper tackles the problem of computational efficiency of kernel methods in out-of-distribution (OOD) scenarios. The authors consider importance-weighting (IW) correction to handle distribution mismatch and random projections (the Nystrom method) to improve efficiency, and rigorously analyze the interplay between the two. They extend the previous literature on random-projection methods to the covariate-shift case and propose an efficient algorithm. On realistic datasets, the algorithm is shown to run much faster while achieving similar prediction accuracy to the naive kernel regression.\n\nI could not follow the entire mathematical framework, but I think the general idea is to constrain the solution space by considering only a subset of training data to reduce computational overhead and to apply the IW framework on the restricted space. The authors then prove excess-risk bounds for this algorithm and find that the Nyström method does not really decrease OOD generalization with IW.", "questions": "One could alternatively approximate the kernel with random features without subsampling training inputs. How does your method compare to that?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths\n\n1. The manuscript is clearly written and well organized; the necessary theoretical concepts are introduced in a clean way.\n2. The paper studies two important problems in classical machine learning—efficiency and OOD generalization—simultaneously.\n3. The assumptions and limitations are described clearly.\n\n### Weaknesses\n\n1. It was hard for me to follow the analysis after Section 5.\n2. The theory assumes ALS to subsample inputs, but its definition is missing. The authors do not discuss how ALS compares to naive subsampling. The choice of subset directly affects IW correction, and it is not clear to me whether ALS is optimal.\n3. The paper only considers IW to treat OOD generalization and does not discuss alternative methods.\n\n**Some minor comments/suggestions**\n\n* It may help the reader to increase the font size in the figure.\n* In line 300: W-KRR → IW-KRR.\n* You could provide a step-by-step description of the algorithm for practitioners.", "was_revised": true, "final_justification": "I think this paper's results are solid and potentially impactful. The authors do a good job of explaining the problem clearly, providing a good summary of the previous literature, and stating exactly what their contribution is. With the authors' promised clarifications, I think it will be a highly readable paper, even for non-experts like me.", "rebuttal": "Thank you for the detailed feedback. We already implemented your comments and suggestions to improve clarity and readability of the paper.\n\nResponses to the Specific Points Raised\n\n\n1.\tWe refer to the answer to reviewer q7kD to some additional explanation of section 6.\nIn case of acceptance, we plan to use the additional page to add explanatory comments and intermediate steps to make the reasoning easier to follow.\n\n2.    As also noted by other reviewers, we will move the definition of ALS sampling (previously in Appendix B) into the main text and provide additional explanation. Moreover, **we already added an additional table (analogous to Table 1) in the appendix to empirically compare uniform sampling with ALS in practice**. As expected, our results are consistent with previous findings: while uniform sampling can achieve accuracy comparable to ALS, it often requires sampling significantly more Nyström points and, in some cases, even results in higher overall computational cost, effectively nullifying the benefits of its simpler sampling scheme.\n\nWe will attempt to provide some explanations regarding 'optimality' below. ALS sampling is well-known among simple independent sampling schemes: Nyström approximation with ALS achieves the same excess risk rate as full KRR using only $m=O(\\mathcal{N}(λ))$ Nyström points (see Theorem 1, line 208). Uniform sampling can achieve the same rate but typically requires more points. More sophisticated subset-selection strategies (e.g., adaptive greedy selection, DPPs, pivoted Cholesky) can sometimes use fewer points, but they are computationally more expensive or require additional information (e.g., partial SVD).\nFor this reason, ALS sampling is widely regarded as a principled and computationally efficient choice, which aligns with the theoretical scope of our paper (see also answer to reviewer zfAH).\n\n3) We agree that out-of-distribution (OOD) generalization can be addressed through multiple approaches. In this paper, we focused on importance weighting (IW) because it is one of the most widely used and mathematically well-established methods for covariate shift. IW provides a clear probabilistic framework (via the Radon–Nikodym derivative) and allows for precise statistical guarantees, which aligns with our goal of providing non-asymptotic theoretical results and connecting them with efficient algorithms. We leave as a future direction the exploration of other approaches.\n\n**Random features and alternative methods**\n\nIndeed, a natural extension of our work is to perform a similar analysis under covariate shift using alternative approximation techniques such as sketching or random features. In this first paper, however, we focused on the Nyström method because its data-adaptiveness generally leads to stronger performance: by selecting representative points from the training set, Nyström better captures the geometry of the data. Both theoretical and empirical studies (e.g., Yang et al., 2012, “Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison”) have shown that Nyström often achieves superior approximation accuracy for the same computational budget.\n\nThat said, extending our theoretical framework to random features and other approximation methods in the covariate-shift setting is an exciting direction for future work."}, {"review_id": "s0YTwvI6z5", "reviewer": "Reviewer_q7kD", "summary": "This paper aims to reduce the computational cost of RKHS-based non-parametric regression under covariate shift between the training and testing distributions. Traditionally, this problem is addressed using kernel ridge regression with importance weighting (IW) correction, which has a computational complexity of $O(n^3)$, making it impractical for large datasets. To address this, the authors propose a Nyström-based approximation method that restricts the search for the minimizer to a low-dimensional random subspace of the RKHS. They prove that the proposed method achieves the optimal convergence rate when the importance weights are known, and they extend the results to the case of unknown weights. Empirical results demonstrate both the efficiency and accuracy of the approach.", "questions": "You could address the three points raised under 'Weaknesses' to improve your rating.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n* The use of Nyström approximation in the context of non-parametric regression under covariate shift is both relevant and innovative. The paper provides strong statistical guarantees, including non-asymptotic results and effective dimension.\n* The related work on kernel ridge regression and its approximations is generally well-situated. However, some notable methods, such as Random Features and SGD, which could also be applicable in this context (especially from a computational standpoint), are omitted.\n* The extension of the method to scenarios with unknown IW is interesting.\n\n**Weaknesses**\n\n* Based on Section 6, it remains unclear whether knowledge of the IW  leads to improved convergence rates. Clarifying this would strengthen the theoretical contributions.\n* Some important assumptions, such as the requirement that the test distribution is dominated with respect to the training distribution, are not sufficiently highlighted. This assumption rules out support shift and is critical to the theoretical guarantees.\n* The misspecified setting (addressed in Section 6) is treated as the harder case, yet there is no discussion of it in Section 5. This separation is confusing, as it leaves the reader uncertain whether the guarantees proven earlier apply only in the well-specified case.\n\n**Writing Suggestions**\n\n* There is redundancy in the presentation of equations, especially in Section 4. Additionally, the definition of the Nyström ALS method should appear in the main. Readers unfamiliar with Nyström methods may find it difficult to understand the approach without it.\n* Notation could be made more consistent—for instance, both $\\int$ and $\\mathbb{E}$ are used for same integration (with $\\mu$) in Section 2. Some definitions, such as the norm $\\Vert \\cdot \\Vert_\\rho$, are also missing.\n\nIn summary, I appreciate the paper's solid mathematical foundation, the clever approach to addressing the problem, and the empirical validation. However, there is room for improvement in terms of clarity and overall soundness.", "was_revised": true, "final_justification": "I am pleased to raise my score for this interesting paper, which features a solid mathematical foundation and a relevant machine learning application.", "rebuttal": "Thank you for the detailed feedback and writing suggestions. We have implemented your advice to improve clarity and readability throughout the paper, uniformizing the notation for expectations and clarifing that $\\| . \\|_{\\rho}$ is simply the norm in $L_2(\\rho)$. In particular, as also suggested by other reviewers, we plan to use the additional space to move Appendix B (definition of ALS) into the main text and provide additional commentary to aid readers unfamiliar with Nyström methods.\n\n---\n\n### Responses to the Specific Points Raised\n\n1. **Convergence rates with and without known importance weights (Section 6)**\nSection 6 addresses the more realistic scenario where the importance weights are unknown and must be estimated from data.  \nIn the well-specified setting (Eq. (21)), consistent with Ma et al. (2023) and Gogolashvili et al. (2023) (both in the full model setting, without Nyström approximation), we show that the convergence rate in Eq. (22) (with estimated weights) matches the rate in Eq. (15) (with exact weights).  \n\nAs noted in lines 262–264, while the dependence on $n$ is unchanged, the dependence on the infinity norm of $w$ differs and Eq. (22) exhibits a worse dependence. Despite statistical learning theory typically focusing on the dependence on $n$, it is important to note that in practice $\\|\\|w\\|\\|_\\infty$ can be large under extreme covariate shift, meaning that—even with identical rates—the bound may still deteriorate because of this constant.  \nIn particular, the interpretation, based on the rate, that IW correction is useless in the well-specified setting can be misleading in applications under severe shift.\n\nIn the misspecified setting, lack of knowledge of the true weights is more critical: the resulting estimator is no longer unbiased, and the error generally does not vanish as $n \\to \\infty$, due to an additional term that remains (lines 265–267). We have clarified these distinctions in the revised version.\n\n---\n\n 2. **Importance of the absolute continuity assumption**\nWe agree that the assumption that the test distribution is absolutely continuous with respect to the training distribution is crucial and deserves to be emphasized.  \nThis assumption underpins all importance-weighted analyses, as the Radon–Nikodym derivative $w$ must exist to define the weights.  \nIntuitively, without overlapping support, the training data cannot provide information about the regression function in regions that only appear in the test distribution.  \nWe will explicitly highlight the importance of this assumption and its implications in the revised text.\n\n---\n\n 3. **Well-specified vs. misspecified settings (Sections 5 and 6)**\nThe results in Section 5 are proven under Assumption 2, which slightly extends the standard well-specified setting commonly used in the literature.  \nAs discussed in the Limitations paragraph (lines 88–91), Assumption 2 allows the regression function to lie outside $\\mathcal{H}$ but guarantees that its projection onto the hypothesis space $\\mathcal{H}$ exists and belongs to its interior rather than its boundary. From the perspective of the technical proofs, this setting is conceptually similar to the standard well-specified case and slightly extends prior work on covariate shift.\n\nThe fully misspecified setting (no condition even on the projection) is technically much more challenging and, to our knowledge, is not yet addressed in the covariate shift literature.  \nA full treatment of this case (e.g., involving interpolation spaces as in Steinwart & Christmann, 2008) is beyond the scope of our current work but represents an important direction for future research.  \n\nSection 6 serves as an additional caution regarding the study of the misspecified setting in the realistic scenario where the true importance weights are unknown. Extending from the well-specified case to the more general misspecified setting, even in the simplified framework under Assumption 2, requires additional care: misspecification not only increases technical complexity, but also introduces practical issues, including potential loss of consistency (lines 265–267). In particular, the predictor $\\widehat{f}^v_{\\lambda,m}$ learned with approximate weights $v$ is **not a consistent estimator of the target** $f_\\mathcal{H}$ anymore, leading to an arbitrarily large error term $\\|\\|f^v_\\mathcal{H} - f_\\mathcal{H}\\|\\|_{\\rho_X^{te}}$ when $v$ is a poor approximation of $w$ (see Eq. (20) and discussion at line 266).\n\nWe will clarify better in the text the distinction between well-specified (regression function in $\\mathcal{H}$), the \"simplified\" misspecified case under Assumption 2 (the regression function not in $\\mathcal{H}$ but it's projection is), and the fully misspecified case (that we do not analyse).\n\n---\n\nWe refer to the answer to reviewer wwtt about the use of other approximation methods such as Random Features or sketching. As regards SGD and early stopping, this can be an interesting alternative to our KRR analysis, as pointed out in the answer to reviewer CabK. We leave these directions to future works for a complete comparison."}, {"review_id": "JUVHOMYMRu", "reviewer": "Reviewer_CabK", "summary": "Under the learning setting where the covariate shift presents, this manuscript investigates the trade-off between computational efficiency and statistical accuracy in kernel ridge regression. Specifically, the authors show the employing random projection techniques, e.g., Nystrom method, in KRR can achieve optimal convergence rates while dramatically reducing computational costs. Studies are extended to unknown IW functions.", "questions": "Intuitively, why is Assumption 3 crucial to apply Nystrom method? Do authors think it is necessary? Or it can be relaxed further with different mathematical tools.", "limitations": "Yes. Authors provide a paragraph in introduction to describe the limitations in terms of the theoretical assumptions and their results.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Strength\n\n1. clear writing, easy to follow. \n2. The authors honestly state limitations of their studies, such as the misspecified case they considered, although slightly more general, but conceptually align with well-specified case.\n3. Clear discussions about related works, including how assumptions are different and what results are (non-)comparable with existing results.\n4. The simulation setting mimics the misspecified setting.\n\n# Weakness:\n\n1. The biggest incentive of consider random projection technique to build KRR estimators is the necessity to compute the inverse of the sample covariance operator, or specifically the matrix in eq. (6). However, KRR is well-known to be a special case of spectral regularized algorithms, including KRR, kernel gradient descent or gradient flow, etc. Therefore, if one generates the estimator via KGD (or others), one can at least avoid the computational time bottleneck of KRR’s matrix inversion.\n2. It is interesting to see the strong moment assumption (Assumption 3) over the weight function is crucial for applying Nystron method. While technically explanations are provided in Appendix C, it would be more reader-friendly to provide some intuitive explanations.  \n3. While having the eigenvalue of covariance operator decay polynomially satisfy Assumption 6, applying Gaussian kernel will not satisfy this assumption. Using Matern kernel with finite order seems more reasonable and align with the assumption. \n4. For those who are not familiar with random projection technique in kernel methods, lines 150 - 154 could be a bit overwhelming. That being said, authors still provided enough details in the Appendix. If there is more room allowed, it can be further detailed. Also, missing argmin at the r.h.s. of eq. (18).", "was_revised": true, "final_justification": "The author responses address my concerns. Since my original rating has been positive, I will keep it as it was.", "rebuttal": "Thank you for the detailed feedback. \n\n1. As pointed out, the closed-form KRR estimator requires solving a linear system, which indeed represents the main computational bottleneck.  \nFirst-order iterative schemes such as kernel gradient descent (KGD) or stochastic gradient methods (SGM) avoid matrix inversion and can be computationally advantageous through early stopping.  \nSpecifically, if the algorithm stops after $T$ iterations, the time complexity is $O(T n^2)$ for gradient descent and conjugate gradient methods [1],[2], and $O(T n)$ for stochastic gradient methods [3].  \nThese procedures are well understood from a statistical perspective, but they still face significant computational and, more importantly, memory challenges for large datasets, since they require storing and repeatedly multiplying by the empirical kernel matrix, which is at least quadratic in the sample size.  \n\nThen, even in this case, a natural way to alleviate these limitations is to replace the full kernel matrix with a low-rank approximation, such as the Nyström method or random features, as widely studied in the literature [4],[5],[6].  \nThese approximations reduce the storage cost from $O(n^2)$ to $O(n m)$ and the per-iteration cost from $O(n^2)$ to $O(n m)$, where $m \\ll n$ is the chosen rank, and can be used not only with KRR but also with iterative schemes like KGD or SGM.  \n\nIn other words, switching from closed-form KRR to gradient-based solvers does not eliminate the fundamental memory bottleneck associated with storing and manipulating the full kernel matrix; it merely shifts the computational burden.  \nLow-rank approximations—Nyström, random features, or random projections—can therefore be beneficial across all spectral regularization methods, regardless of whether they are solved in closed form or via iterative optimization.\n\n---\n\n2.  Assumption 3 is needed because, under covariate shift, the importance weights can in principle be unbounded. When applying the Nyström method, we rely on concentration results to control the error of sampling-based approximations of covariance operators. Standard tools such as Bernstein inequalities work well for bounded or sub-exponential random variables, but not for arbitrarily heavy-tailed weights.\n\nAssumption 3 addresses this by imposing a moment condition on the weights: while individual weights are not strictly bounded, the probability of encountering extremely large values is sufficiently small. Intuitively, this prevents rare but extreme weights from dominating the empirical estimates, which could otherwise destabilize the approximation and invalidate the concentration results. From a practical perspective, this reflects the fact that importance weighting works reliably when the shift between training and test distributions is not too extreme (the assumption can also be seen as a condition on the Rényi divergence between test and train distribution, see line 177).\n\nWe do not rule out that different mathematical tools—e.g., truncation strategies or robust concentration inequalities etc.—could relax this assumption further, but future work in this direction is needed to understand that. As regards our analysis, Assumption 3 remains crucial and it's not directly relaxable, but it guarantees a good balance between generality and analytical tractability, while being already common in importance-weighted learning literature. \n\n---\n\n3. We chose the RBF (Gaussian) kernel because it is widely used in both theory and practice, making it a natural benchmark for our experiments.  \nWhile Assumption 6 requires a polynomial decay of the covariance operator eigenvalues, the RBF kernel actually satisfies an even stronger property—its eigenvalues **decay exponentially rather than polynomially**.  Then Assumption 6 is also satisfied by the RBF kernel.\nHence, the RBF kernel is fully compatible with our theoretical framework, and our results hold under an even more favorable spectral condition. That said, as the reviewer noted, the Matérn kernel is also a perfectly valid choice within our model.\n\n---\n\n4. As also suggested by other reviewers, we will use the extra space to move the details of ALS sampling to the main text.\n\n---\n\nWe tried to answer your question at point 2) .\n\n**References**  \n[1] Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. *Early stopping and nonparametric regression: An optimal data-dependent stopping rule.* Journal of Machine Learning Research, 15(1):335–366, 2014.  \n[2] Gilles Blanchard and Nicole Krämer. *Optimal learning rates for kernel conjugate gradient regression.* In Advances in Neural Information Processing Systems, pages 226–234, 2010.  \n[3] Lorenzo Rosasco and Silvia Villa. *Learning with incremental iterative regularization.* In Advances in Neural Information Processing Systems, pages 1621–1629, 2015.  \n[4] Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. *Learning with SGD and random features.* Advances in Neural Information Processing Systems 31, 2018.  \n[5] Junhong Lin and Lorenzo Rosasco. *Optimal Rates for Learning with Nyström Stochastic Gradient Methods.* arXiv preprint arXiv:1710.07797, 2017.  \n[6] Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco. *FALKON: An optimal large scale kernel method.* Advances in Neural Information Processing Systems 30, 2017."}]

Author rebuttal:

Meta-review: This paper addresses the covariate shift problem in nonparametric regression within reproducing kernel Hilbert spaces (RKHSs). 
The authors leverage Nyström method to work with a random subspace of the RKHS. 
This allows one to balance between computational efficiency and statistical accuracy under covariate shift.

The main contribution lies in analyzing kernel ridge regression (KRR) under covariate shift, where the authors rigorously characterize the trade-off between computational cost and generalization performance. Notably, they show that using random projections can significantly reduce computational complexity while still achieving optimal convergence rates.

The paper is well-written and clearly motivated. Reviewers appreciated the technical contributions and the relevance of the problem, though they also suggested that the clarity and overall soundness of the presentation could be further improved. 
I encourage the authors to take this feedback into account in a future revision.

Overall, this is a solid contribution that provides valuable insights into scalable kernel methods under distribution shift.
I thus recommend acceptance.
Decision: Accept (spotlight)