REVIEW 2 major objections 5 minor 38 references
Spectral Algorithms under Covariate Shift
T0 review · 2 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read This paper proves that a clipped-weight spectral algorithm achieves near-optimal regression rates under covariate shift even when density ratios are unbounded.
desk verdict Solid, genuinely new extension of covariate-shift rates to spectral algorithms, but the main theorems overstate what the proofs establish because a bounded-output assumption is used and never stated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the weighted spectral estimator in a reproducing kernel Hilbert space, formed by applying a filter function $g_\lambda$ (with qualification $\nu_g\ge 1/2$) to the empirical weighted covariance operator $S_X^\top W S_X$. The argument runs through three error terms: an approximation term controlled by the filter qualification and smoothness $r$, a sample-error term controlled by Bernstein inequalities in Hilbert space, and a weight-bias term controlled by concentration of the empirical average of the density ratio. The crucial mechanisms are the effective dimension $N(\lambda)=\operatorname{Tr}((\lambda I+L_K)^{-1}L_K)$ for complexity, the normalized weight $\bar w(x_i)=w(x_i)/\frac1n\sum_j w(x_j)$ for bounded average weight, and the clipping threshold $D_n$ that keeps the operator norm of the empirical covariance operator from growing like $O(n)$ while truncating tails of $w$. The clipping is what removes the saturation at $r=3/2$ that afflicts normalized weights.
What would settle it
Take a covariate-shift regression where the density ratio satisfies the paper's moment condition but the output noise is heavy-tailed, e.g. $y=f_\rho(x)+\varepsilon$ with $t_2$ noise, and numerically estimate the excess prediction error of the clipped weighted spectral algorithm as $n$ grows. If the observed rate is clearly slower than $n^{-r/(2r+\beta)+\epsilon}$ or the confidence statement fails, the missing bounded-output assumption is load-bearing; conversely, if the rate holds, the assumption is removable.
Extended reading notes
Core claim
For a weighted spectral estimator $f^{\hat w}_{z,\lambda}=g_\lambda(S_X^\top \hat W S_X)S_X^\top \hat W \bar y$ with clipped weights $\hat w(x)=\min\{w(x),D_n\}$, the paper proves an excess prediction error bound $\|f^{\hat w}_{z,\lambda}-f_\rho\|_{L^2_{\rho^{te}_X}}\le \tilde C_{r,\epsilon}\, n^{-r/(2r+\beta)+\epsilon}(\log 6/\delta)^2$ under a Rényi-type moment assumption on the density ratio, smoothness $f_\rho=L_K^r u_\rho$, and an effective-dimension condition $N(\lambda)\le C_0\lambda^{-\beta}$. The regularization and clipping thresholds are chosen as $\lambda=n^{-1/(2r+\beta)+\epsilon/r}$ and $D_n=n^{\alpha\epsilon}$ for $1/2\le r\le 3/2$, or $D_n=n^{\alpha\epsilon/(r-1/2)}$ for $r>3/2$. The parameter $\alpha\in[0,1]$, which controls how far the test distribution may deviate from the training distribution, affects only the clipping threshold and not the rate. This is what the authors mean by approaching the optimal capacity-dependent rates arbitrarily closely: for any $\epsilon>0$, the rate exponent is within $\epsilon$ of $r/(2r+\beta)$.
Load-bearing premise
The proofs assume the response is uniformly bounded around the regression function, $|y-f_\rho(x)|\le 2M$, in order to apply Bernstein moment bounds, yet the main theorems do not state this bounded-output assumption; if the outputs are heavy-tailed, the claimed rates are not justified.
Editorial extensions
If this is right
- If the main theorem is correct, importance-weighted kernel ridge regression and other spectral algorithms under covariate shift achieve rates within $\epsilon$ of the capacity-dependent optimum even when density ratios are unbounded.
- The saturation at $r=3/2$ is not inherent to spectral regularization; clipping resolves it, so smooth target functions no longer waste extra regularity.
- For uniformly bounded density ratios, weighting is unnecessary: the classical unweighted spectral algorithm already reaches minimax optimal rates on the test distribution.
- The exponent $r/(2r+\beta)$ matches the standard minimax rate for kernel regression, so covariate shift itself does not degrade the achievable rate once weights are handled properly.
Reading between the lines
- Editorial inference: Because $\alpha$ enters only through the clipping threshold $D_n$, a data-driven or Lepski-type choice of $D_n$ might deliver the same near-optimal rates without knowing $\alpha$ exactly.
- Editorial inference: The proofs use the bounded-output condition $|y-f_\rho(x)|\le 2M$ in the Bernstein moment bounds, but the main theorems do not state it; if outputs are heavy-tailed, robust losses or output truncation may be needed for the rates to survive.
- Editorial inference: The error decomposition depends only on filter qualification, effective dimension, and weight concentration, so the same clipping technique likely transfers to other spectral settings such as functional regression or online kernel learning under covariate shift.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies spectral algorithms for nonparametric regression in a reproducing kernel Hilbert space under covariate shift, where the training and test input distributions differ but the conditional distribution of the output given the input is unchanged. The main results are: (i) Theorem 5, an optimal-rate guarantee for the classical unweighted spectral algorithm under a bounded density ratio; (ii) Theorem 2 and Corollary 3, which analyze a normalized-weight spectral algorithm and prove capacity-independent rates when the density ratio is potentially unbounded, subject to a saturation phenomenon at regularity r = 3/2; and (iii) Theorem 4, which introduces a clipped-weight spectral algorithm and proves rates of order n^{-r/(2r+beta)+epsilon}, arbitrarily close to the capacity-dependent optimal rates. The technical core is an operator-valued error decomposition combined with Bernstein-type concentration inequalities in Hilbert spaces and effective-dimension estimates.
Significance. If the stated results hold, they would meaningfully extend the existing theory of importance-weighted kernel ridge regression under covariate shift to the broad family of spectral algorithms, removing restrictive bounded-eigenfunction assumptions used in earlier work (e.g., Ma et al. 2023) and addressing the saturation effect of normalized weights. The paper is methodical: the error decompositions in Section 3 are carefully derived, the constants are made explicit, and the proofs rely on standard, checkable concentration arguments. However, two load-bearing assumptions are missing from theorem statements, so the theorems as written are broader than what the proofs actually establish. These omissions are fixable but currently block acceptance.
major comments (2)
- [§4.1, Proposition 17 and §4.2, Proposition 22] The proofs of both Proposition 17 and Proposition 22 require a uniform bound on the response variable. In Proposition 17, the moment calculation for eta(x,y) = (lambda I + L_K)^(-1/2) w(x)(y - f_rho(x)) K_x replaces |y - f_rho(x)|^p by (2M)^p, and the proof of Proposition 22 bounds E||xi_3||^2 by 4M^2 D_n \hat N(lambda). Neither the general setup in Section 1 (where Y = R is declared) nor the statements of Theorems 2 and 4 include any bounded-output or conditional-sub-Gaussian assumption. Consequently, the claimed rates for heavy-tailed responses are not justified, and the constants C' and \tilde C_{r,epsilon} depend on an M that is never defined. The fix is straightforward: add an explicit assumption such as |y| <= M almost surely (or a sub-Gaussian/sub-exponential tail condition) to the setup and to the statements of Theorems 2 and 4, and note how M enters the constants.
- [Theorem 5 and Lemma 27] The statement of Theorem 5 does not contain any assumption on the density ratio w, yet its proof invokes Lemma 27, which requires the weight function to be uniformly bounded, |w(x)| <= U. Without this assumption the key estimate ||L_K^{1/2}(lambda I + \tilde L_K)^(-1/2)||_op <= sqrt(U) is unavailable, so the theorem is not established under the assumptions as written. Please add the bounded-density-ratio assumption to Theorem 5, or modify the proof if the result is intended to hold without it.
minor comments (5)
- [Theorem 2] The condition beta + alpha(1 - beta) >= 1, combined with the standing bounds 0 < alpha <= 1 and 0 < beta <= 1, is equivalent to alpha = 1 or beta = 1. The theorem statement should say this explicitly, because as written the phrase 'under Assumption 1 with 0<alpha<=1 and Assumption 3 with 0<beta<=1' suggests coverage of the full range, which is not what the condition allows.
- [Proposition 22] The definition of J3 in Proposition 10 is (lambda I + \hat L_K)^(-1/2)(S_X^\top \hat W \bar y - S_X^\top \hat W S_X f_rho), but Proposition 22 states the target as (lambda I + \hat L_K)^(-1/2)(S_X^\top \hat W \bar y - S_X^\top \hat W f_rho), omitting the S_X before f_rho. Please make the notation consistent.
- [Proposition 17] The proof of Proposition 17 uses sums over m, writing 1/m and P_{j=1}^m, although the sample size throughout the paper is n. This appears to be a typographical carryover; please replace all occurrences of m with n in that proposition and its proof.
- [Throughout] There are several typographical errors, including 'yeilds' in Proposition 12, 'conifidence' in Proposition 12, and inconsistent spacing in the Rényi divergence display. A careful proofreading pass is needed.
- [Theorem 4, discussion after the theorem] The statement that rates can 'approach the optimal capacity-dependent convergence rates arbitrarily closely' should be qualified: the exponent becomes n^{-r/(2r+beta)+epsilon}, but the constant \tilde C_{r,epsilon} depends on epsilon and grows through factors such as the factorial of ceil(1/epsilon). Thus the closeness is in the exponent, with constants that may degrade as epsilon decreases; this is worth stating explicitly for precision.
Circularity Check
No significant circularity: results are derived from concentration inequalities and operator calculus; Theorem 5's use of Guo et al. (2017) is independent published support.
full rationale
The central contributions (Theorems 2 and 4) are obtained by direct sample-error and operator-norm estimates: Propositions 15-18 and 20-25 apply Bernstein inequalities (Lemmas 11, 14, 19) and filter-function identities (Lemmas 6-8); no parameter is fitted to data, and the rates n^{-r/(2r+beta)+epsilon} are not re-imported from Assumptions 1-3. The unweighted result (Theorem 5) invokes Theorem 2 of Guo et al. (2017) after proving Lemma 27; that citation is a prior published theorem, not the present target, and the authors' overlap does not make the cited result unverified. The one substantive issue in the manuscript is a missing assumption: Proposition 17 and Proposition 22 use the pointwise bound |y-f_rho(x)| <= 2M, but the main setup only states Y=R, so the stated theorems are broader than what the proofs establish; this is a correctness gap, not a circularity, because the bound is not an input that is later renamed as the output.
Assumptions & free parameters
assumptions (5)
- standard math RKHS setup: X compact metric space, K Mercer kernel, kappa = sup sqrt(K(x,x)) < infinity.
- domain assumption Assumption 1: Renyi-type moment condition on the density ratio w with parameters alpha in [0,1], C>0, sigma>0.
- domain assumption Assumptions 2 and 4: source condition f_rho = L_K^r u_rho with respect to rho_te or rho_tr.
- domain assumption Assumptions 3 and 5: effective dimension bound N(lambda) <= C0 lambda^{-beta}.
- ad hoc to paper Bounded response: |y| <= M almost surely, implicitly used in proofs.
Cite this review
Pith. "Pith review of Spectral Algorithms under Covariate Shift." pith.science (2026). https://pith.science/paper/BVESYI4Z
@misc{pith2026250412625,
author = {Pith},
title = {Pith review of: Spectral Algorithms under Covariate Shift},
year = {2026},
howpublished = {\url{https://pith.science/paper/BVESYI4Z}},
note = {Machine review of arXiv:2504.12625}
}
read the original abstract
Spectral algorithms leverage spectral regularization techniques to analyze and process data, providing a flexible framework for addressing supervised learning problems. To deepen our understanding of their performance in real-world scenarios where the distributions of training and test data may differ, we conduct a rigorous investigation into the convergence behavior of spectral algorithms under covariate shift. In this setting, the marginal distributions of the input data differ between the training and test datasets, while the conditional distribution of the output given the input remains unchanged. Within a non-parametric regression framework over a reproducing kernel Hilbert space, we analyze the convergence rates of spectral algorithms under covariate shift and show that they achieve minimax optimality when the density ratios between the training and test distributions are uniformly bounded. However, when these density ratios are unbounded, the spectral algorithms may become suboptimal. To address this issue, we propose a novel weighted spectral algorithm with normalized weights that incorporates density ratio information into the learning process. Our theoretical analysis shows that this normalized weighted approach achieves optimal capacity-independent convergence rates, but the rates will suffer from the saturation phenomenon. Furthermore, by introducing a weight clipping technique, we demonstrate that the convergence rates of the weighted spectral algorithm with clipped weights can approach the optimal capacity-dependent convergence rates arbitrarily closely. This improvement resolves the suboptimality issue in unbounded density ratio scenarios and advances the state-of-the-art by refining existing theoretical results.
Reference graph
Works this paper leans on
-
[1]
Theory of reproducing kernels
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68 0 (3): 0 337--404, 1950
1950
-
[2]
Matrix A nalysis, V olume 169 of G raduate T exts in M athematics, 1997
Rajendra Bathis. Matrix A nalysis, V olume 169 of G raduate T exts in M athematics, 1997
work page 1997
-
[3]
On regularization algorithms in learning theory
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory. Journal of Complexity, 23 0 (1): 0 52--72, 2007
work page 2007
-
[4]
Discriminative learning under covariate shift
Steffen Bickel, Michael Br \"u ckner, and Tobias Scheffer. Discriminative learning under covariate shift. Journal of Machine Learning Research, 10 0 (9), 2009
2009
-
[5]
Optimal learning rates for kernel conjugate gradient regression
Gilles Blanchard and Nicole Kr \"a mer. Optimal learning rates for kernel conjugate gradient regression. Advances in Neural Information Processing Systems, 23, 2010
work page 2010
-
[6]
Domain generalization by marginal transfer learning
Gilles Blanchard, Aniket Anand Deshmukh, Urun Dogan, Gyemin Lee, and Clayton Scott. Domain generalization by marginal transfer learning. Journal of Machine Learning Research, 22 0 (2): 0 1--55, 2021
work page 2021
-
[7]
Concentration Inequalities: A Nonasymptotic Theory of Independence
St \'e phane Boucheron, G \'a bor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013
2013
-
[8]
Optimal rates for the regularized least-squares algorithm
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7 0 (3): 0 331--368, 2007
2007
Show all 38 references
-
[9]
Learning bounds for importance weighting
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. Advances in Neural Information Processing Systems, 23, 2010
2010
-
[10]
Learning Theory: An Approximation Theory Viewpoint
Felipe Cucker and Ding-Xuan Zhou. Learning Theory: An Approximation Theory Viewpoint. Cambridge University Press, 2007
2007
-
[11]
Learning from examples as an inverse problem
Ernesto De Vito, Lorenzo Rosasco, Andrea Caponnetto, Umberto De Giovannini, Francesca Odone, and Peter Bartlett. Learning from examples as an inverse problem. Journal of Machine Learning Research, 6 0 (5), 2005
2005
-
[12]
Computational efficiency under covariate shift in kernel ridge regression
Andrea Della Vecchia, Arnaud Mavakala Watusadisi, Ernesto De Vito, and Lorenzo Rosasco. Computational efficiency under covariate shift in kernel ridge regression. arXiv preprint arXiv:2505.14083, 2025
2025 arXiv
-
[13]
Regularization of inverse problems
Heinz W Engl and Ronny Ramlau. Regularization of inverse problems. In Encyclopedia of Applied and Computational Mathematics, pages 1233--1241. Springer, 2015
2015
-
[14]
Spectral algorithms for functional linear regression
Jun Fan, Zheng-Chu Guo, and Lei Shi. Spectral algorithms for functional linear regression. Communications on Pure and Applied Analysis, 23 0 (7): 0 895--915, 2024
2024
-
[15]
Rethinking importance weighting for deep learning under distribution shift
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. Advances in Neural Information Processing Systems, 33: 0 11996--12007, 2020
2020
-
[16]
Towards a unified analysis of kernel-based methods under covariate shift
Xingdong Feng, Xin He, Caixing Wang, Chao Wang, and Jingnan Zhang. Towards a unified analysis of kernel-based methods under covariate shift. Advances in Neural Information Processing Systems, 36: 0 73839--73851, 2023
2023
-
[17]
Spectral algorithms for supervised learning
L Lo Gerfo, Lorenzo Rosasco, Francesca Odone, E De Vito, and Alessandro Verri. Spectral algorithms for supervised learning. Neural Computation, 20 0 (7): 0 1873--1897, 2008
2008
-
[18]
On a regularization of unsupervised domain adaptation in RKHS
Elke R Gizewski, Lukas Mayer, Bernhard A Moser, Duc Hoan Nguyen, Sergiy Pereverzyev Jr, Sergei V Pereverzyev, Natalia Shepeleva, and Werner Zellinger. On a regularization of unsupervised domain adaptation in RKHS . Applied and Computational Harmonic Analysis, 57: 0 201--227, 2022
2022
-
[19]
When is importance weighting correction needed for covariate shift adaptation? arXiv preprint arXiv:2303.04020, 2023
Davit Gogolashvili, Matteo Zecchin, Motonobu Kanagawa, Marios Kountouris, and Maurizio Filippone. When is importance weighting correction needed for covariate shift adaptation? arXiv preprint arXiv:2303.04020, 2023
2023 arXiv
-
[20]
Covariate shift by kernel mean matching
Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Sch \"o lkopf. Covariate shift by kernel mean matching. Dataset Shift in Machine Learning, 3 0 (4): 0 5, 2009
2009
-
[21]
Capacity dependent analysis for functional online learning algorithms
Xin Guo, Zheng-Chu Guo, and Lei Shi. Capacity dependent analysis for functional online learning algorithms. Applied and Computational Harmonic Analysis, 67: 0 101567, 2023
2023
-
[22]
Learning theory of distributed spectral algorithms
Zheng-Chu Guo, Shao-Bo Lin, and Ding-Xuan Zhou. Learning theory of distributed spectral algorithms. Inverse Problems, 33 0 (7): 0 074009, 2017
2017
-
[23]
Lo RA : Low-rank adaptation of large language models
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lo RA : Low-rank adaptation of large language models. International Conference on Learning Representations, 1 0 (2): 0 3, 2022
2022
-
[24]
A least-squares approach to direct importance estimation
Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach to direct importance estimation. Journal of Machine Learning Research, 10: 0 1391--1445, 2009
2009
-
[25]
Statistical analysis of kernel-based least-squares density-ratio estimation
Takafumi Kanamori, Taiji Suzuki, and Masashi Sugiyama. Statistical analysis of kernel-based least-squares density-ratio estimation. Machine Learning, 86 0 (3): 0 335--367, 2012
2012
-
[26]
Distributed learning with regularized least squares
Shao-Bo Lin, Xin Guo, and Ding-Xuan Zhou. Distributed learning with regularized least squares. Journal of Machine Learning Research, 18 0 (92): 0 1--31, 2017
2017
-
[27]
Balancing principle in supervised learning for a general regularization scheme
Shuai Lu, Peter Math \'e , and Sergei V Pereverzev. Balancing principle in supervised learning for a general regularization scheme. Applied and Computational Harmonic Analysis, 48 0 (1): 0 123--148, 2020
2020
-
[28]
Optimally tackling covariate shift in RKHS -based nonparametric regression
Cong Ma, Reese Pathak, and Martin J Wainwright. Optimally tackling covariate shift in RKHS -based nonparametric regression. The Annals of Statistics, 51 0 (2): 0 738--761, 2023
2023
-
[29]
Multiple source adaptation and the R \'e nyi divergence
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Multiple source adaptation and the R \'e nyi divergence. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, UAI 2009, pages 367--374. AUAI Press, 2009
2009
-
[30]
General regularization in covariate shift adaptation
Duc Hoan Nguyen, Sergei Pereverzyev, and Werner Zellinger. General regularization in covariate shift adaptation. Data-driven Models in Inverse Problems, 31: 0 245, 2024
2024
-
[31]
Estimating divergence functionals and the likelihood ratio by convex risk minimization
XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56 0 (11): 0 5847--5861, 2010
2010
-
[32]
A survey on transfer learning
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering, 22 0 (10): 0 1345--1359, 2009
2009
-
[33]
Optimum bounds for the distributions of martingales in B anach spaces
Iosif Pinelis. Optimum bounds for the distributions of martingales in B anach spaces. The Annals of Probability, pages 1679--1706, 1994
1994
-
[34]
Improving predictive inference under covariate shift by weighting the log-likelihood function
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference, 90 0 (2): 0 227--244, 2000
2000
-
[35]
Estimating the approximation error in learning theory
Steve Smale and Ding-Xuan Zhou. Estimating the approximation error in learning theory. Analysis and Applications, 1 0 (01): 0 17--41, 2003
2003
-
[36]
Covariate shift adaptation by importance weighted cross validation
Masashi Sugiyama and Matthias Krauledat. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8: 0 985--1005, 2007
2007
-
[37]
Density Ratio Estimation in Machine Learning
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, 2012
2012
-
[38]
Adaptive learning of density ratios in RKHS
Werner Zellinger, Stefan Kindermann, and Sergei V Pereverzyev. Adaptive learning of density ratios in RKHS . Journal of Machine Learning Research, 24 0 (395): 0 1--28, 2023
2023
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.