Pith. sign in

REVIEW 4 minor 28 references

Convergence Analysis of Nystr\"om Subsampling in Covariate Shift Adaptation for Misspecified case

T0 review · 0 major / 4 minor · reviewed 2026-06-26 · grok-4.3

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

Pith's one-line read Regularized Nyström subsampling produces high-probability excess risk bounds for covariate shift adaptation in the misspecified regime.

desk verdict This paper supplies explicit high-probability excess-risk bounds for Nyström subsampling under covariate shift in the misspecified regime, including when the density ratio is estimated. read the letter →

arxiv 2606.22259 v1 pith:74PZ5Y7W submitted 2026-06-20 stat.ML cs.LGcs.NAmath.NA

Hanna Myleiko , Sergei Solodky , Vasyl Semenov This is my paper · ORCID
classification stat.MLcs.LGcs.NAmath.NA
keywords NyströmsubsamplingcovariateshiftdomainadaptationmisspecifiedcaseTikhonovregularizationexcessriskdensityratioestimationsourcecondition
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

The paper establishes that combining Tikhonov regularization with Nyström projection onto a subsampled subspace yields upper bounds on excess risk that hold with high probability. These bounds are expressed using the source condition, the effective dimension, and the sizes of the available samples from the source and target distributions. The analysis is extended to the practical case where the Radon-Nikodym derivative must be estimated from finite data, and the minimal number of additional samples required to preserve the original convergence rate is identified.

What carries the argument

Nyström projection onto a subsampled subspace combined with Tikhonov regularization, which produces the excess risk bounds under covariate shift.

What would settle it

Observe whether the excess risk fails to decay at the stated rate once the number of samples used to estimate the Radon-Nikodym derivative drops below the minimal threshold identified in the analysis.

Watch

Extended reading notes

Core claim

By combining Tikhonov regularization with Nyström projection onto a subsampled subspace, we obtain upper bounds on the excess risk that hold with high probability and are expressed in terms of the source condition, the effective dimension, and the sample sizes. We further extend the analysis to the setting where the Radon-Nikodym derivative between the target and source marginal distributions is unknown and must be approximated, and we identify the minimal additional sample sizes required to maintain the same convergence rate as in the oracle case.

Load-bearing premise

The covariate shift assumption holds exactly so that conditionals are identical, and the source condition together with the effective dimension remain well-defined and finite even though the target function lies outside the RKHS.

Editorial extensions

If this is right

  • The same convergence rate as the full-kernel method is retained while the computational cost is reduced by the subsampling.
  • Only a finite number of extra samples for density-ratio estimation is needed to keep the rate unchanged from the oracle setting.
  • The high-probability bounds continue to hold when the target function is misspecified relative to the RKHS.
  • The rates are controlled explicitly by the source condition and the effective dimension of the chosen kernel.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Practitioners facing large source and target datasets can use the subsampled method without sacrificing the theoretical rate provided the extra density samples are collected.
  • The approach may extend to other kernel-based transfer settings where the density ratio must be learned jointly with the predictor.
  • Empirical checks on synthetic data with controlled misspecification levels could confirm whether the predicted sample thresholds match observed performance.
  • If the effective dimension grows slowly, the method remains statistically efficient even as the ambient dimension increases.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The manuscript provides a convergence analysis of Nyström subsampling combined with Tikhonov regularization for kernel methods in unsupervised domain adaptation under covariate shift, specifically addressing the misspecified case where the target regression function lies outside the RKHS. High-probability upper bounds on the excess risk are derived in terms of the source condition, effective dimension, and sample sizes. The analysis is extended to the case where the Radon-Nikodym derivative is unknown and estimated from data, with conditions on additional samples to preserve the rates.

Significance. If the results hold, this work contributes to the theoretical understanding of efficient kernel-based methods for domain adaptation in realistic misspecified settings. The explicit handling of the estimated density ratio and the identification of minimal sample sizes for rate preservation are particularly useful. The use of source condition defined on the source measure allows for finite quantities even in misspecification, which is a strength. The decomposition into approximation, estimation, and sampling error terms supports the claimed rates.

minor comments (4)
  1. The abstract and introduction could more explicitly contrast the misspecified regime (r ≤ 1/2) with the well-specified case to highlight the technical challenges addressed.
  2. [§2] Definition of the effective dimension and source condition (via spectral decomposition of the source covariance operator) appears in §2; moving an explicit statement of these quantities to the notation section would improve readability.
  3. [§5] The extension in §5 for the estimated Radon-Nikodym derivative states sample-size requirements; a short remark comparing the oracle vs. estimated constants in the final rate would strengthen the presentation.
  4. A few citations to related Nyström analyses in standard (non-shift) KRR are present but could be expanded for direct rate comparisons.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work on Nyström subsampling under covariate shift in the misspecified setting and for recommending minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper derives high-probability upper bounds on excess risk for regularized Nyström subsampling under covariate shift in the misspecified regime. These bounds are expressed directly in terms of externally defined quantities (source condition parameter, effective dimension of the covariance operator under the source measure, sample sizes, and bounded Radon-Nikodym derivative). The source condition and effective dimension are introduced via the spectral decomposition of the integral operator and treated as given inputs; the error decomposition into approximation, estimation, and sampling terms follows from standard operator-theoretic arguments without reducing any claimed rate to a fitted quantity or self-citation by construction. The extension to the estimated density-ratio case supplies explicit additional sample-size requirements that preserve the oracle rate, again without circular reduction. No load-bearing step matches any of the enumerated circularity patterns.

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

Abstract supplies no explicit free parameters, axioms, or invented entities; all quantities (source condition, effective dimension, Radon-Nikodym derivative) are treated as standard objects from prior kernel and domain-adaptation literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Convergence Analysis of Nystr\"om Subsampling in Covariate Shift Adaptation for Misspecified case." pith.science (2026). https://pith.science/paper/74PZ5Y7W

@misc{pith2026260622259,
  author       = {Pith},
  title        = {Pith review of: Convergence Analysis of Nystr\"om Subsampling in Covariate Shift Adaptation for Misspecified case},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/74PZ5Y7W}},
  note         = {Machine review of arXiv:2606.22259}
}
read the original abstract

This paper investigates convergence properties of regularized Nystr\"om subsampling applied to the unsupervised domain adaptation problem under covariate shift. We focus on the low-smoothness (misspecified) case where the target function lies outside the reproducing kernel Hilbert space. By combining Tikhonov regularization with Nystr\"om projection onto a subsampled subspace, we obtain upper bounds on the excess risk that hold with high probability and are expressed in terms of the source condition, the effective dimension, and the sample sizes. We further extend the analysis to the setting where the Radon-Nikodym derivative between the target and source marginal distributions is unknown and must be approximated, and we identify the minimal additional sample sizes required to maintain the same convergence rate as in the oracle case.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 3 canonical work pages

  1. [1]

    Shimodaria Improving Predictive Inference under covariate shift by weighting the log-likelyhood function Journal of Statistical Planning and Inference

    H. Shimodaria Improving Predictive Inference under covariate shift by weighting the log-likelyhood function Journal of Statistical Planning and Inference. 90 (2000), 227 – 244

    2000

  2. [2]

    Huang, A

    J. Huang, A. Gretton, K. Borgwardt, B. Sch¨ olkopf, A. Smola Correcting Sample Selection Bias by Unlabeled Data, Advances in Neural Information Processing Systems 19 (2006), 601-608

    2006

  3. [3]

    Molchan, J

    G. Molchan, J. I. Golosov Gaussian stationary processes with asymptotic power spectrum Dokl. Akad. Nauk SSSR. 184(3), 1969

    1969

  4. [4]

    Picard Representation Formula for the Fractional Brownian Motion

    J. Picard Representation Formula for the Fractional Brownian Motion. In: Donati-Martin, C., Lejay, A., Rouault, A. (eds) S´ eminaire de Probabilit´ es XLIII. Lecture Notes in Mathematics, vol 2006. Springer, Berlin, Heidelberg, (2011). 16

    2006

  5. [5]

    Alpay, D

    D. Alpay, D. Levanony On the Reproducing Kernel Hilbert Spaces Associated with the Fractional and Bi-Fractional Brownian Motions. Potential Anal. 28 (2008), 163 – 184

    2008

  6. [6]

    L. N. Slobodeckij, Generalized Sobolev spaces and their applications to boundary value problems of partial differential equations, Leningrad. Gos. Ped. Inst. Ucep. Zap. 197 (1958), 54 – 112

    1958

  7. [7]

    Aronszajn, Boundary values of functions with finite Dirichlet integral, Techn

    N. Aronszajn, Boundary values of functions with finite Dirichlet integral, Techn. Report of Univ. of Kansas. 14 (1955), 77 – 94

    1955

  8. [8]

    Gagliardo, Propriet´ a di alcune classi di funzioni in pi´ u variabili, Ricerche Mat

    E. Gagliardo, Propriet´ a di alcune classi di funzioni in pi´ u variabili, Ricerche Mat. 7 (1958), 102 – 137

    1958

Show all 28 references
  1. [9]

    A general method of constructing regularizing algorithms for a linear ill-posed equation in Hilbert space

    Bakushinski A.B. A general method of constructing regularizing algorithms for a linear ill-posed equation in Hilbert space. USSR Comput.Math. and Math.Phys. 7 (1967), 279 – 287

    1967

  2. [10]

    Lu S., Mathe P., Pereverzyev-Jr. S. Analysis of regularized Nystr¨ om subsampling for regression function of low smoothness. Analysis and Application. 17(6) (2019), 931– 946

    2019

  3. [11]

    Regularization Theory

    Lu S., Pereverzev S.V. Regularization Theory. Selected Topics, in: Inverse and Ill-posed problems Series, vol. 58. Berlin, Boston: Walter de Gruyter GmbH, 2013

    2013

  4. [12]

    Balancing principle in supervised learning for a general regularization scheme

    Lu S., Mathe P., Pereverzyev S. Balancing principle in supervised learning for a general regularization scheme. Applied and Computational Harmonic Analysis, 48(1) (2020), 23 – 148

    2020

  5. [13]

    Geometry of linear ill-posed problems in variable Hilbert scales

    Mathe P., Pereverzev S.V. Geometry of linear ill-posed problems in variable Hilbert scales. Inverse Problems. 19 (2003), 789 – 803

    2003

  6. [14]

    On regularized Radon-Nikodym differentiation

    Nguyen D.H., Zellinger W., Pereverzyev S. On regularized Radon-Nikodym differentiation. Journal of Machine Learning Research, 25(266) (2024), 1 – 24

    2024

  7. [15]

    Discretization strategy for ill-posed problems in variable Hilbert scales

    Mathe P., Pereverzev S.V. Discretization strategy for ill-posed problems in variable Hilbert scales. Inverse Problems. 19 (2003) 1263 – 1277

    2003

  8. [16]

    S., Solodky S.G

    Myleiko G.L., Pereverzyev-Jr. S., Solodky S.G. Regularized Nystr¨ om subsampling in regression and ranking problems under general smoothness assumptions Analysis and Applications. 17 (2019), 453 – 475

    2019

  9. [17]

    On the regularization of projection methods for solving ill-posed problems

    Plato R., Vainikko G.M. On the regularization of projection methods for solving ill-posed problems. Numer. Math. 57 (1990), 63 – 79

    1990

  10. [18]

    Less is more: Nystr¨ om computational regularization

    Rudi A., Comoriano R., Rosasco L. Less is more: Nystr¨ om computational regularization. Advances in Neural Information Processing Systems. 28 (2015) 1648 –1656

    2015

  11. [19]

    Elke R., Gizewski E.R., Mayer L., Moser B.A. et al. On a regularization of unsupervised domain adaptation in RKHS. Applied and Computational Harmonic Analysis. 57(2022), 201 – 227

    2022

  12. [20]

    An Introduction to Artificial Intelligence Based on Reproducing Kernel Hilbert Spaces, 2022, 152 p

    Pereverzyev S. An Introduction to Artificial Intelligence Based on Reproducing Kernel Hilbert Spaces, 2022, 152 p

    2022

  13. [21]

    M., Veretennikov A

    Vainikko G. M., Veretennikov A. Yu. Iteration procedures in ill-posed problems. (Moscow: Nauka), 1986

    1986

  14. [22]

    Optimal rates for the regularized least squares algorithm

    Caponnetto A., De Vito E. Optimal rates for the regularized least squares algorithm. Foundations of Computational Mathematics. 7 (2007), 331 – 368

    2007

  15. [23]

    On recovery the Radon-Nikodym derivative under the big data assumption

    Myleiko H., Solodky S. On recovery the Radon-Nikodym derivative under the big data assumption. Journal of Complexity. 93 (2026), 102001. 17

    2026

  16. [24]

    L., Solodky, S

    Myleiko, H. L., Solodky, S. G. Regularized Nystr¨ om Subsampling in Covariate Shift Domain Adap- tation Problems. Numerical Functional Analysis and Optimization, 45(3) (2024), 165 – 188

    2024

  17. [25]

    https://doi.org/10.48550/arXiv.2509.05106

    Ren-Rui Liu, Zheng-Chu Guo Spectral Algorithms in Misspecified Regression: Convergence under Covariate Shift, Preprint, arXiv 2025. https://doi.org/10.48550/arXiv.2509.05106

    2025 doi

  18. [26]

    de Vito, L

    A Della Vecchia, Watusadisi A., E. de Vito, L. Rosasco Computational Efficiency under Covariate Shift in Kernel Ridge Regression, Preprint, arXiv 2025. https://doi.org/10.48550/arXiv.2505.14083

    2025 doi

  19. [27]

    “When is im- portance weighting correction needed for covariate shift adaptation? Preprint, arXiv 2023

    Gogolashvili D., Zecchin M., Kanagawa M., Kountouris M., and Filippone M. “When is im- portance weighting correction needed for covariate shift adaptation? Preprint, arXiv 2023. https://doi.org/10.48550/arXiv.2303.04020

    2023 doi

  20. [28]

    Sobolev Spaces

    Adams R., Fournier J. Sobolev Spaces. Pure and Applied Mathematics. Vol. 140 (2nd ed.). Boston, MA: Academic Press. (2003) [1975]. 18 A Appendix. Proof of Auxiliary Statements Proof of Lemma 3.11. To prove the inequality (3.26), we consider two random variables defined as ξ1(x...

    2003

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.