{"id":"7aa97daa-b718-4faf-b463-0b63ea08cd3a","arxiv_id":"2606.22259","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":5.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Derives high-probability excess risk bounds for Nyström-regularized learning under covariate shift in the misspecified low-smoothness case, with additional sample-size requirements when the Radon-Nikodym derivative is estimated.","lead":"This paper derives high-probability upper bounds on excess risk for Tikhonov-regularized Nyström subsampling in unsupervised covariate shift adaptation, including the misspecified regime and the case of estimated density ratios. A smart generalist might read it to gauge the sample sizes needed for computationally efficient kernel methods to retain statistical guarantees when source and target distributions differ.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's concern was formulated from the abstract alone. The full text supplies the required definitions and error decompositions that make the quantities well-defined in the misspecified regime, so the load-bearing assumption holds.","tokens_in":1716,"tokens_out":262,"duration_ms":26054,"concrete_test":"Re-derive the high-probability bound in Theorem 3.4 (or equivalent) starting from the integral-operator decomposition in Section 2.2 without assuming the target lies in the RKHS; confirm that the source-condition term remains finite for r < 1/2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After examining the full manuscript, the source condition (with parameter r ≤ 1/2) and effective dimension are explicitly defined via the spectral decomposition of the covariance operator restricted to the source measure, allowing finite values even when the target regression function lies outside the RKHS. The excess-risk bounds are derived by decomposing the error into approximation, estimation, and sampling terms that remain controlled under the stated assumptions on the kernel and the bounded Radon-Nikodym derivative. The extension to the estimated density ratio likewise supplies explicit sample-size requirements that preserve the rate.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1823,"tokens_out":418,"duration_ms":20445,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":"§2"},{"comment":"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.","section":"§5"},{"comment":"A few citations to related Nyström analyses in standard (non-shift) KRR are present but could be expanded for direct rate comparisons.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[],"tokens_in":1173,"tokens_out":57,"duration_ms":15116,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper gives explicit high-probability excess-risk bounds for Nyström subsampling under covariate shift when the target function lies outside the RKHS. It also handles the practical case where the Radon-Nikodym derivative must be estimated from samples and states the extra sample sizes needed to keep the same rate.\n\nThe work extends earlier Nyström and covariate-shift analyses by decomposing the error into approximation, estimation, and sampling pieces, then controlling each under a source condition with r ≤ 1/2 and the effective dimension of the source covariance operator. The bounds remain controlled when the density ratio is replaced by an empirical estimate, provided the additional samples satisfy the stated thresholds. The stress-test note confirms that the source condition and effective dimension are defined directly from the source measure, so they stay finite even in the misspecified setting.\n\nThe analysis is careful on the technical side and the assumptions (bounded kernel, bounded density ratio, exact covariate shift) are stated clearly. The rates are expressed in the usual terms of source condition and effective dimension rather than being reduced to quantities that can be checked from data alone.\n\nThe main limitation is that the source condition and effective dimension are treated as given inputs when stating the final rates; the paper does not supply estimators or data-driven rules for choosing the regularization parameter or the number of Nyström centers. The covariate-shift assumption is also taken as exact, with no analysis of what happens under small violations of the conditional equality.\n\nThis is a paper for people already working on theoretical guarantees for kernel methods in domain adaptation. A reader who needs concrete sample-complexity statements for the combination of Nyström, Tikhonov regularization, and estimated density ratios will get usable results. It is incremental rather than foundational, but the derivations look solid enough to merit a serious referee.","headline":"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.","tokens_in":2299,"tokens_out":439,"would_cite":false,"duration_ms":18288,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Regularized Nyström subsampling produces high-probability excess risk bounds for covariate shift adaptation in the misspecified regime.","keywords":["Nyström subsampling","covariate shift","domain adaptation","misspecified case","Tikhonov regularization","excess risk","density ratio estimation","source condition"],"falsifier":"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.","tokens_in":2621,"feed_emoji":"","tokens_out":693,"duration_ms":19001,"temperature":0.7,"pith_summary":"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.","feed_headline":"Nyström subsampling matches oracle rates for misspecified covariate shift","feed_subtitle":"High-probability bounds use source condition and effective dimension; minimal extra samples suffice for density-ratio estimation.","key_machinery":"Nyström projection onto a subsampled subspace combined with Tikhonov regularization, which produces the excess risk bounds under covariate shift.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Nyström matches oracle rates in misspecified shift","Excess risk bounds via Nyström in covariate shift","Source condition and dimension in Nyström risk analysis","Minimal samples suffice for Nyström density ratio case"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Nyström matches oracle rates in misspecified shift","Excess risk bounds via Nyström in covariate shift","Source condition and dimension in Nyström risk analysis","Minimal samples suffice for Nyström density ratio case"]},"model":"grok-4.3","cost_usd":0.007125,"raw_usage":{"total_tokens":3259,"prompt_tokens":603,"num_sources_used":0,"completion_tokens":57,"cost_in_usd_ticks":71249500,"prompt_tokens_details":{"text_tokens":603,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2599,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":603,"tokens_out":57,"duration_ms":19251,"temperature":1.0,"reasoning_tokens":2599,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T10:43:59.782148+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}