{"id":"5b67c77d-8b9e-4345-8ab6-66981795c302","arxiv_id":"2501.11413","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new bound relates the expected size of W-CRC prediction sets under covariate shift to generalization error, shift severity, and calibration and training data sizes.","lead":"This paper derives a mathematical bound on the size of prediction sets produced by weighted conformal risk control when the data distribution shifts between training and testing. The bound shows how calibration set size, training set size, and the severity of the shift interact, and it could help practitioners decide how to split their data.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix B's Eq. (43) bounds the covariate-shift bias with KL(PX||P'X), but w≤Wbar only bounds KL(P'X||PX); as written, the verification of Assumption 3 for practical algorithms fails.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: Assumption 3 is the gate between the theorem and practical algorithms, and its verification in Appendix B relies on Eq. (43), which uses the incorrect KL direction. My independent reading agrees. The proof of Theorem 1 itself is conditional on Assumption 3 and does not reuse Eq. (43), so the theorem is not internally contradicted; a reader who grants Assumption 3 obtains the stated bound. The defect is in the supporting claim that Assumption 3 holds for Gibbs posteriors, DP-ERM, and SGLD, and it is straightforwardly repairable by replacing KL(PX||P'X) with KL(P'X||PX) and re-checking the Pinsker constant. I also reviewed Appendix C and found no additional fatal issue: the Hoeffding step, the replacement of W by \\bar W, and the construction of \\hat λ are consistent given Assumption 3. The experiments' qualitative nature is a secondary weakness but not the decisive one. Therefore the appropriate disposition remains CONDITIONAL, matching the reader's verdict; no change is needed.","tokens_in":13511,"tokens_out":16120,"duration_ms":163047,"concrete_test":"Test the inequality in Eq. (43) on X={0,1} with P_X=(0.5,0.5), P'_X=(0,1), so w=(0,2) and \\bar W=2. Eq. (43) would require KL(P_X||P'_X) ≤ log 2, but KL(P_X||P'_X)=∞, while KL(P'_X||P_X)=log 2. Then re-derive the bias bound with KL(P'_X||P_X), using the Pinsker constant from [33, Lemma 1]; if the resulting additive term is \\bar L sqrt(0.5 log \\bar W) rather than \\bar L sqrt(log \\bar W), update Assumption 3 and all dependent displays (18), (20), (21), (44), (53) and verify the qualitative conclusions in Section III-D are unchanged.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central bound (Theorem 1, Eq. (20)) is conditional on Assumption 3, and the only argument that Assumption 3 is satisfied by the Gibbs, DP-ERM, and SGLD algorithms named in Section III-A is the PAC-Bayes derivation in Appendix B. That derivation fails at Eq. (43). There, the shift bias is bounded as ∆b(Q|Dtr) ≤ \\bar L sqrt(KL(PX||P'X)) ≤ \\bar L sqrt(log \\bar W), where w(x)=P'_X(x)/P_X(x) ≤ \\bar W. The second inequality has the wrong KL direction: w≤\\bar W gives KL(P'_X||P_X)=E_{P'_X}[log w] ≤ log \\bar W, whereas KL(P_X||P'_X)=E_{P_X}[log(1/w)] can be arbitrarily large (even infinite) under Assumption 2. Example: X={0,1}, P_X=(1/2,1/2), P'_X=(0,1) satisfies w≤2, but KL(P_X||P'_X)=∞. Consequently, the appendix does not establish that Assumption 3 holds for the cited algorithms. The main theorem itself remains a valid conditional statement, and the flaw is repairable by using KL(P'_X||P_X) (and the correct Pinsker constant, which introduces a factor 1/√2 if [33] is used as cited), but every occurrence of \\bar L sqrt(log \\bar W) in Eqs. (18), (20), (21), (44), and (53) must be checked against that constant. Since the paper's claimed link from generalization properties of standard algorithms to W-CRC inefficiency runs through this assumption, this is the load-bearing weak point.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript presents a training-time bound on the expected size of prediction sets produced by weighted conformal risk control (W-CRC) under covariate shift. The main result, Theorem 1, relates the expected set size to the nonconformity score density, the training empirical risk, the covariate-shift bound \\bar W, the target risk level, and the training and calibration set sizes, under Assumptions 1–3. An appendix aims to show that Assumption 3 holds for Gibbs posteriors, differentially private ERM, and SGLD, and the paper reports localization experiments that illustrate qualitative trends consistent with the bound.","tokens_in":13806,"tokens_out":12629,"duration_ms":117780,"significance":"If the conditional result and its verification are correct, the paper provides a useful bridge between the generalization properties of a base predictor and the efficiency of weighted conformal risk control, with practical implications for choosing training/calibration splits under distribution shift. The writing is clear, the conditional theorem is plausible, and the topic is timely. However, the paper's value depends critically on Assumption 3 being satisfied by standard algorithms, and the current verification of that assumption is defective because of an incorrect KL-divergence inequality.","major_comments":[{"comment":"The inequality KL(P_X||P'_X) ≤ log \\bar W is asserted from w(x) = P'_X(x)/P_X(x) ≤ \\bar W, but this is incorrect: w ≤ \\bar W implies KL(P'_X||P_X) = E_{P'_X}[log w(X)] ≤ log \\bar W, whereas KL(P_X||P'_X) = E_{P_X}[log(1/w(X))] can be arbitrarily large, or infinite, under Assumption 2. The example X={0,1}, P_X=(1/2,1/2), P'_X=(0,1) satisfies w ≤ 2 yet KL(P_X||P'_X)=∞. This invalidates the derivation of the bias bound Δb(Q|Dtr) ≤ \\bar L sqrt(log \\bar W) and therefore the proof that Assumption 3 holds for the Gibbs, DP-ERM, and SGLD algorithms named in Section III-A. Since this is the only step connecting the mutual-information bound to the covariate-shift term, the claimed applicability of Theorem 1 to those algorithms is not established. The repair is to use KL(P'_X||P_X) instead, and to re-derive the constant. All occurrences of the term \\bar L sqrt(log \\bar W) in Eqs. (18), (20), (21), (44), and (53) must be re-checked against the corrected inequality.","section":"Appendix B, Eq. (43)"},{"comment":"Even after reversing the KL direction, the bound in Eq. (43) uses an implicit constant of 1 in front of sqrt(KL), whereas the cited result [33, Lemma 1] for sub-Gaussian random variables typically yields a constant involving sqrt(2) or 1/sqrt(2) depending on the exact statement (e.g., via Pinsker's inequality). The authors should derive the precise constant and state explicitly the resulting form of Assumption 3, because the quantitative behavior of the inefficiency bound in Theorem 1 and the discussion in Section III-D depend on the magnitude of this covariate-shift bias term.","section":"Appendix B, Eq. (43) and Assumption 3"}],"minor_comments":[{"comment":"The notation \\hat L_Q(λ, X|D) uses the full dataset D in the argument, but the sum runs only over the calibration set; consider writing Dcal for clarity.","section":"Section II-C, Eq. (10)"},{"comment":"The figures plot \"relative inefficiency\" without stating whether the values are averaged over multiple realizations of the training and calibration splits; adding error bars or repeated-seed results would strengthen the empirical validation.","section":"Section IV, Figures 3 and 4"},{"comment":"The step from Eq. (51) to Eq. (53) replaces λ* by \\hat λ with \\hat λ ≥ λ*; this is valid only because the exponential factor is at most 1, so the integrand on [λ*, \\hat λ] is bounded by γ(r). Please state this explicitly to help the reader.","section":"Appendix C, proof of Theorem 1"},{"comment":"The phrase \"the the product distribution\" contains a duplicated article.","section":"Appendix B, first paragraph"},{"comment":"Reference [27] appears to duplicate the previously cited work [14] (Dhillon et al.); please consolidate to avoid confusion.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The conditional theorem is likely sound, but the paper's central claim that Assumption 3 is satisfied by standard learning algorithms is currently unsupported due to the reversed KL divergence in Eq. (43). This is a clear technical error that is repairable, but the authors must also verify the Pinsker/sub-Gaussian constant and re-derive the affected equations. The experiments are only qualitative and do not directly test the numerical tightness of the bound. If the KL issue is fixed, the paper could become acceptable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real, non-trivial extension—the first training-time bound I know for W-CRC set size under covariate shift—and the main theorem is a clean conditional statement. But the paper tries to show Assumption 3 holds for standard algorithms, and that argument fails at Eq. (43) in Appendix B: w ≤ Wbar bounds KL(P'_X||P_X), not KL(P_X||P'_X), and the latter can be infinite. That is the load-bearing link to practice, so as written the verification is not established.\n\nWhat is genuinely good: Theorem 1 relates inefficiency to the NC-score density, empirical training risk, shift magnitude Wbar, risk level, and ncal/ntr, and the discussion is honest—the bound is explicitly conditional on a stated assumption. The proof is self-contained and I don't see a gap in the main concentration step. The data-split insight (more calibration data helps when shift is large) is a useful practical heuristic, and the experiments qualitatively match it, though they never evaluate the bound numerically.\n\nSoft spots, in order: (1) The Appendix B justification is broken at Eq. (43). Fixing it means using KL(P'_X||P_X) and the correct Pinsker constant, which puts a 1/√2 factor in every occurrence of Lbar sqrt(log Wbar)—Eqs. (18), (20), (21), (44), (53). That is mechanical but needs doing. (2) Assumption 3 is strong—a uniform bound on the generalization gap that includes the shift bias—and the paper does not check it empirically. (3) Experiments are trend-matching only; the bound itself is not computed. These are real but not fatal, because the theorem is honest about its condition.\n\nWho this is for: researchers working on conformal risk control under distribution shift, especially those who want a finite-sample, training-time handle on prediction set efficiency. It deserves a serious referee—the idea is interesting and the main proof largely holds—but I would not accept it in current form. The authors need to fix the KL direction and either find a valid verification or state Assumption 3 as an unverified premise.\n\nMy recommendation: send to peer review with a request for major revision, and make the referee aware of the specific Appendix B issue.","headline":"A genuine extension of the authors' conformal efficiency bound to covariate shift, but the verification of the key generalization assumption has a wrong-direction KL inequality that needs repair.","tokens_in":14436,"tokens_out":1834,"would_cite":false,"duration_ms":18451,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the expected size of W-CRC prediction sets under covariate shift is bounded before deployment by training-time quantities, so prediction-set informativeness can be evaluated when the model is built.","keywords":["weighted conformal risk control","covariate shift","prediction set efficiency","conformal prediction","generalization bound","set-valued prediction","uncertainty quantification","RSSI localization"],"falsifier":"Run W-CRC on a task with computable likelihood ratios and a known NC-score density, record actual expected set sizes over many trained models, and check whether any realization violates Eq. (20) at a rate exceeding $\\delta$; alternatively, directly measure $\\Delta(Q|D_{\\mathrm{tr}}) = \\sup_\\lambda |\\hat{L}_Q(\\lambda|D_{\\mathrm{tr}}) - L_Q(\\lambda)|$ and compare it with the Assumption 3 right-hand side across many training draws.","tokens_in":13244,"feed_emoji":"📐","tokens_out":6460,"duration_ms":61177,"temperature":0.7,"pith_summary":"Weighted conformal risk control (W-CRC) turns point predictions into prediction sets that meet a user-specified risk under covariate shift, but the size of those sets—how informative they are—could previously only be measured after deployment. This paper proves that the expected set size is bounded at training time by quantities the user can inspect: the base predictor's generalization gap, the training and calibration set sizes, the risk level, and the maximum likelihood ratio between test and training covariates. The bound makes the efficiency-reliability tradeoff visible before deployment, including how much calibration data is needed to counteract a given shift. Experiments on RSSI-based localization confirm the predicted ordering: larger covariate shifts and smaller calibration sets produce larger prediction regions.","feed_headline":"Set size under covariate shift is now bounded before test time","feed_subtitle":"A new theorem ties prediction-set inefficiency to training data, calibration data, and the magnitude of the shift.","key_machinery":"The load-bearing object is the W-CRC threshold selector, which compares a weighted empirical loss—calibration losses reweighted by likelihood ratios $w(x) = P'_X(x)/P_X(x)$ and augmented with a worst-case test point—to the target risk $\\alpha$. Around this sit three ingredients: the non-conformity score density $\\gamma(r)$, which counts how many labels have score near $r$ and turns set size into an integral; the generalization gap $\\Delta(Q|D_{\\mathrm{tr}})$, which the paper bounds through mutual-information and Rademacher arguments; and a Hoeffding concentration step that yields the exponential tail in Eq. (20).","core_discovery":"The central result is Theorem 1: under a bounded, non-increasing loss, a bounded likelihood ratio $w(x) \\leq \\bar{W}$, and a generalization-gap bound on the base predictor, the W-CRC expected set size satisfies Eq. (20) with probability at least $1-\\delta$ over the training set. The bound writes the normalized inefficiency $\\Lambda_{\\mathrm{W-CRC}}(D_{\\mathrm{tr}})/|\\mathcal{Y}|$ as the integral of the NC-score density $\\gamma(r)$ up to a threshold $\\hat{\\lambda}$ plus an exponentially decaying tail over larger scores. The threshold $\\hat{\\lambda}$ itself is determined by the empirical training risk, the target risk $\\alpha$, the shift bound $\\bar{W}$, $n_{\\mathrm{cal}}$, $n_{\\mathrm{tr}}$, and the generalization constant $\\beta(\\delta, n_{\\mathrm{tr}})$. The theorem therefore converts the post-hoc question 'how big are the sets?' into a training-time computation.","pith_inferences":["Beyond the paper's claims, one could test tightness directly: estimate $\\gamma(r)$ and the actual generalization gap on the localization task, then compare measured set sizes with the right-hand side of Eq. (20).","Beyond the paper's claims, the proof route suggests a label-shift analogue: reweight calibration losses by $P'_Y/P_Y$; the covariate-shift generalization-gap bound would need to be replaced by a label-shift concentration argument.","Beyond the paper's claims, the monotonicity in $\\bar{W}$ points to a practical lever: clipping or smoothing estimated likelihood ratios should reduce the bound and, if the bound is tight, the realized set size."],"forward_implications":["For a fixed total data budget, the bound identifies a training/calibration split that minimizes worst-case set size, and that split shifts toward calibration as the covariate shift $\\bar{W}$ grows.","Increasing calibration size $n_{\\mathrm{cal}}$ shrinks the inefficiency bound both through faster exponential decay and through a smaller threshold $\\hat{\\lambda}$.","Growing the training set helps mainly when the covariate shift is mild; under large $\\bar{W}$, the irreducible $\\bar{L}\\sqrt{\\log \\bar{W}}$ term dominates.","The bound can be evaluated entirely at training time, so a practitioner can compare candidate data splits and reliability levels without test data."],"supporting_citations":[{"why":"Establishes weighted exchangeability and the likelihood-ratio weighting that W-CRC uses to handle covariate shift.","marker":"[11]"},{"why":"Defines W-CRC and proves the α-reliability guarantee that the paper takes as its starting point.","marker":"[12]"},{"why":"Provides the no-shift conformal generalization-informativeness bound that this paper extends to covariate shift.","marker":"[15]"},{"why":"Introduces the NC-score density used to express expected set size as an integral over score levels.","marker":"[27]"},{"why":"Supplies the KL-divergence bound used in Appendix B to justify the covariate-shift bias term in Assumption 3.","marker":"[33]"},{"why":"Provides the Hoeffding inequality used in the concentration step of the Theorem 1 proof.","marker":"[34]"},{"why":"Supplies the real-world RSSI fingerprinting dataset for the localization experiments.","marker":"[28]"}],"fun_headline_variants":["New bound predicts conformal set size under covariate shift","Training-time theorem bounds prediction set inefficiency","Covariate shift no longer hides set size until test time","Weighted conformal risk control gets a pre-test efficiency bound","Set size under shift: now computable from training data alone"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Assumption 3: the worst-case gap between the set predictor's training-set risk and its risk under the test distribution is at most $\\beta(\\delta,n_{\\mathrm{tr}})/\\sqrt{n_{\\mathrm{tr}}} + \\bar{L}\\sqrt{\\log \\bar{W}}$, with probability $1-\\delta$; if this generalization-gap bound is violated in practice, the set-size bound in Eq. (20) no longer holds.","fun_headline_variants_meta":{"raw":{"variants":["New bound predicts conformal set size under covariate shift","Training-time theorem bounds prediction set inefficiency","Covariate shift no longer hides set size until test time","Weighted conformal risk control gets a pre-test efficiency bound","Set size under shift: now computable from training data alone"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000179,"raw_usage":{"total_tokens":1303,"prompt_tokens":951,"completion_tokens":352,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":271}},"tokens_in":567,"tokens_out":352,"duration_ms":3980,"temperature":1.0,"reasoning_tokens":271,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:18:30.460330+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run W-CRC on a task with computable likelihood ratios and a known NC-score density, record actual expected set sizes over many trained models, and check whether any realization violates Eq. (20) at a rate exceeding $\\delta$; alternatively, directly measure $\\Delta(Q|D_{\\mathrm{tr}}) = \\sup_\\lambda |\\hat{L}_Q(\\lambda|D_{\\mathrm{tr}}) - L_Q(\\lambda)|$ and compare it with the Assumption 3 right-hand side across many training draws.","supporting_citations":[{"cited_title":"Confor- mal prediction under covariate shift,","cited_arxiv_id":null,"evidence_quote":"Establishes weighted exchangeability and the likelihood-ratio weighting that W-CRC uses to handle covariate shift."},{"cited_title":"Generalization and informativeness of conformal prediction,","cited_arxiv_id":null,"evidence_quote":"Provides the no-shift conformal generalization-informativeness bound that this paper extends to covariate shift."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Hoeffding inequality used in the concentration step of the Theorem 1 proof."},{"cited_title":"Sigfox and LoRaW AN datasets for fingerprint localization in large urban and rural areas,","cited_arxiv_id":null,"evidence_quote":"Supplies the real-world RSSI fingerprinting dataset for the localization experiments."}],"review_version":1}