Pith. sign in

REVIEW 14 references

Computational Efficiency under Covariate Shift in Kernel Ridge Regression

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Nyström-approximated importance-weighted kernel ridge regression achieves the same optimal excess-risk rates as the full method under covariate shift, with sublinear time and memory costs.

arxiv 2505.14083 v1 pith:QCAIMM76 submitted 2025-05-20 stat.ML cs.LG

Andrea Della Vecchia , Arnaud Mavakala Watusadisi , Ernesto De Vito , Lorenzo Rosasco This is my paper · ORCID
classification stat.MLcs.LG
keywords covariateshiftcomputationalkernellearningefficiencyrandomregression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Machine learning models usually assume that training and test data come from the same distribution. In practice, they often differ, a situation called covariate shift: the input values shift while the relationship between input and output stays the same. Kernel ridge regression is a classical method that works well in theory but needs n by n matrices, which is slow and memory-hungry for large datasets. This paper combines kernel ridge regression with the Nyström method, a standard trick that solves the problem on a small random sample of the training points instead of all of them. The authors add importance weights to correct for the shift between training and test distributions, and they analyze the statistical cost of the approximation. Their main theorem says that, under standard regularity assumptions, the approximation achieves the same convergence rates as the full weighted method: for bounded importance weights, the error decays at the optimal rate, and for unbounded weights, at a slower but still useful rate. The number of sampled points can be much smaller than the dataset size, cutting time and memory dramatically. The paper also tests the method on real human-activity sensor data, where one user's data is used for training and another user's for testing. The fast weighted approximation matches the accuracy of the full weighted method while being orders of magnitude faster. The theoretical results rely on several assumptions, including a strong condition on how far apart the training and test distributions are allowed to be.
Extended reading notes

Core claim

Theorem 1 (Section 5.2): under Assumptions 1-6, for ALS sampling, with high probability the Nyström IW-KRR estimator satisfies ||R(f̂^w_{λ,m}) - R(f_H)||^{1/2} ≤ 64B(W/(n√λ) + sqrt(σ²/(n λ^{γ(1-q)+q}))) log(8/δ) + 43R λ^r. Corollary 1 then gives E(f̂^w_{λ,m}) ≲ (||w||∞/n)^{2r/(2r+γ)} for bounded weights (q=0) and E ≲ n^{-2r/(2r+1)} for unbounded weights (q=1), matching the full W-KRR rates.

Load-bearing premise

Assumption 3 (eq. 14, Section 5.1): the importance weight w must satisfy a uniform moment condition, which for q=0 means w is bounded and for q>0 means a sub-Gaussian-type tail condition on w. The authors state this stronger condition is 'crucial' for the Nyström method in the unbounded case, and it is used in Propositions 1-2 and Theorem 1. If real data have heavy-tailed density ratios, the guarantees do not apply.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 2 free parameters · 8 assumptions · 0 invented entities

The theoretical derivation relies only on the assumptions and external lemmas listed above; no free parameters are fitted to data to produce the rates, and no new entities are introduced. The only hand-chosen quantities are experimental hyperparameters tuned by cross-validation.

free parameters (2)
  • regularization parameter λ (experimental) = cross-validated on a 10-point geometric grid from 10^-4 to 1
    Chosen by hold-out cross-validation in Section 7; not part of the theoretical derivation.
  • RBF kernel bandwidth γ (experimental) = values from Remark 2 (10^-3 to 5·10^2)
    Selected via cross-validation in the empirical study; the theoretical results use the symbol γ for the capacity exponent instead.
assumptions (8)
  • standard math H is an RKHS with bounded kernel (Assumption 1).
    Standard framework for kernel ridge regression; used throughout the paper.
  • domain assumption There exists f_H minimizing ||f - g*||² over H (Assumption 2).
    Defines the benchmark in the misspecified case; standard in learning theory.
  • ad hoc to paper Importance weight w satisfies the moment condition (Assumption 3, eq. 14).
    Stronger than the second-moment condition in Ma et al. (2023); the authors call it crucial for the Nyström analysis in the unbounded case (Section 5.1).
  • domain assumption Outputs are bounded: Y ∈ [-B, B] (Assumption 4).
    Used to control the noise term A4 via Lemma 19 from Gogolashvili et al. (2023).
  • domain assumption Source condition f_H = L^r g with r ∈ [1/2,1] (Assumption 5).
    Standard smoothness assumption controlling the approximation error term B.
  • domain assumption Capacity condition N_{ρte}(λ) ≤ Q λ^{-γ} (Assumption 6).
    Bounds the effective dimension and determines the required number of Nyström centers m.
  • ad hoc to paper T-approximate leverage scores exist for all λ ≥ λ0 (Definition 2).
    The ALS sampling guarantee in Proposition 2 depends on this condition; the paper uses ALS from Rudi et al. (2018) but inherits this requirement.
  • standard math External bounds: Lemma 18 and Lemma 19 from Gogolashvili et al. (2023), Propositions 3, 7, 9 from Rudi et al. (2015), and Cordes inequality (Fujii et al. 1993).
    Unproved in the paper and used as black boxes in Appendix C.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computational Efficiency under Covariate Shift in Kernel Ridge Regression." pith.science (2026). https://pith.science/paper/QCAIMM76

@misc{pith2026250514083,
  author       = {Pith},
  title        = {Pith review of: Computational Efficiency under Covariate Shift in Kernel Ridge Regression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QCAIMM76}},
  note         = {Machine review of arXiv:2505.14083}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2505.14083 by the authors.

Figure 1
Figure 1. On the left: MSE for the different models varying the number of train samples [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. The graphs above illustrate the results summarized in Table [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 10 canonical work pages

  1. [1]

    (2015) it’s easy to show that bΣ1/2 wλ V(V ∗ bΣwλV) −1V ∗ bΣ1/2 wλ 2 = bΣ1/2 wλ V(V ∗ bΣwλV) −1V ∗ bΣ1/2 wλ , and therefore the only possible values forA 2 are0and1

    Proof of Theorem 1 proof of Theorem 1.We split the excess risk as R( bf w λ,m)− R(fH) 1/2 = bf w λ,m −f H ρte X = Σ1/2( bf w λ,m −f H) H = Σ1/2(V(V ∗ bΣwV+λI) −1V ∗ bS∗Mwy−f H) H ⩽ Σ1/2V(V ∗ bΣwV+λI) −1V ∗ bS∗Mw(y− bSfH) H| {z } A + + Σ1/2(I−V(V ∗ bΣwV+λI) −1V ∗ bΣw)fH H| {z } B TermA A⩽ Σ1/2 bΣ−1/2 wλ | {z } A1 bΣ1/2 wλ V(V ∗ bΣwλV) −1V ∗ bΣ1/2 wλ | {z }...

    work page 2015

  2. [2]

    log2(4/δ) n 1 1+q ⩽λ⩽∥Σ∥ , then the following holds with probability 1−δ, | bNw(λ)− Nρte X (λ)| Nρte X ⩽2. Proof. Let’s call Nρte X (λ) =N(λ) to simplify the notation. The proof partially follows the structure of Proposition 1 in Rudi et al. (2015), with some complications deriving from the presence of the (pos- sibly unbounded) weights. Define bBw = Σ−1/...

    work page 2015

  3. [4]

    We derive an expression for the KRR minimizer when considering IW correction and Nyström approximation. Lemma 1(Nyström IW-KRR estimator).Given the minimization problem in (11), the unique minimizer can be written as bf w λ,m =V(V ∗ bS∗ cMw bSV+λI) −1V ∗ bS∗ cMw by(25) whereλ >0,by= (y 1, ..., yn)T and the matrix cMw = diag(w(x1), ..., w(xn)). Proof.Eq. (...

    work page 2006

  4. [6]

    This term can be controlled using Proposition 2 above

    to (I−V V ∗) Σr′ λ , we have (I−V V ∗) Σr′ λ = (I−V V ∗)2r Σ 1 2 2r′ λ ⩽ (I−V V ∗) Σ1/2 λ 2r′ . This term can be controlled using Proposition 2 above. 20 •B.2: B.2⩽λ bΣ1/2 wλ V(V ∗ bΣwλV) −1V ∗ bΣr′ wλ bΣ−r′ wλ Σr′ λ ⩽λ bΣ1/2 wλ V(V ∗ bΣwλV) −1V ∗ bΣr′ wλ bΣ−1/2 wλ Σ1/2 λ 2r′ ⩽β 2r′ λ V ∗ bΣwλV 1/2 V ∗ bΣwλV −1 V ∗ bΣwλV r′ =β 2r′ λ V ∗ bΣwV+λI −(1/2−r′) ...

    work page 2015

  5. [10]

    log2(4/δ) n 1 γ(1−q)+1+q ⩽λ⩽∥Σ∥, •m⩾144T 2Nρte X (λ) log 8n δ . Proof. Let’s call Σ = Σ ρte X to simplify the notation. Define τ=δ/4 . Next, define the diagonal matrix H∈R n×n with (H) ii = 0 when Pλ(i) = 0 and (H) ii = nq(i) mPλ(i) when Pλ(i)>0 , where q(i)is the number of times the indexiis present in the collectionI. We have that bS∗ wH bSw = 1 m nX i=...

    work page 2015

  6. [11]

    Thus, by taking a union bound again, we have β3(λ)⩽ 2 log 2n τ 3m + s 16T 2Nρte X (λ) log 2n τ m with probability1−2τ−δ

    log2(4/δ) n 1 1+q ⩽λ⩽∥Σ∥ . Thus, by taking a union bound again, we have β3(λ)⩽ 2 log 2n τ 3m + s 16T 2Nρte X (λ) log 2n τ m with probability1−2τ−δ. The last step is to bound Σ−1/2 λ bΣ1/2 wλ 2 , as follows Σ−1/2 λ bΣ1/2 λw 2 = Σ−1/2 λ bΣλwΣ−1/2 λ = I+ Σ −1/2 λ bΣw −Σ Σ−1/2 λ ⩽1 +η, 18 with η= Σ−1/2 λ bΣw −Σ Σ−1/2 λ . We can bound η using Lemma 18 in Gogol...

    work page 2023

  7. [14]

    log2(4/δ) n 1 γ(1−q)+1+q ⩽λ⩽∥Σ∥ , and m⩾144T 2Qλ−γ log 8n δ , with probability greater or equal than1−δ R( bf w λ,m)− R(fH) 1/2 ⩽64B W n √ λ + r σ2 nλγ(1−q)+q ! log 8 δ + 43Rλr. D Known results In this section, we derive tight bounds for the effective dimension Nρ(λ) defined in Definition 1 when assuming polynomial decay of the eigenvaluesσ j(Σ)of the cov...

    work page 2007

  8. [2007]

    B., Lee, Y

    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 on innovations in theoretical computer science, pp. 181–190,

    work page 2015

Show all 14 references
  1. [2011]

    Domain adaptation: Learning bounds and algorithms

    11 Mansour, Y ., Mohri, M., and Rostamizadeh, A. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3430,

    arXiv

  2. [2012]

    Learning bounds for kernel regression using effective data dimensionality

    Zhang, T. Learning bounds for kernel regression using effective data dimensionality. Neural Computation, 17(9):2077–2098,

  3. [2017]

    Less is more: Nyström computational regularization

    Rudi, A., Camoriano, R., and Rosasco, L. Less is more: Nyström computational regularization. arXiv preprint arXiv:1507.04717, 28,

    arXiv

  4. [2020]

    Woodruff, D. P. Sketching as a tool for numerical linear algebra. arXiv preprint arXiv:1411.4357,

    arXiv

  5. [2021]

    and Sriperumbudur, B

    Kpotufe, S. and Sriperumbudur, B. K. Kernel sketching yields kernel jl. arXiv preprint arXiv:1908.05818,

    1908 arXiv

  6. [2022]

    When is importance weighting correction needed for covariate shift adaptation? arXiv preprint arXiv:2303.04020,

    Gogolashvili, D., Zecchin, M., Kanagawa, M., Kountouris, M., and Filippone, M. When is importance weighting correction needed for covariate shift adaptation? arXiv preprint arXiv:2303.04020,

    arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.