- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper provides analysis of False Coverage Proportion (FCP) with distribution shift. Theoretical and empirical evidence are shown to validate the results.
Critical strengths
This paper is easy to read, and rather complete. The authors provide both empirical and theoretical evidence to validate their claims.
Critical weaknesses
Unfortunately, I find this paper's contribution a little incremental. The line of FCP is widely explored, as cited by this paper. And conformal prediction under covariate shift is also well-explored. The techniques of this paper directly follow those tricks, if I may say so. Therefore, I cannot find noval contributions of this paper.
Besides, the writing of this paper is somehow confusing. I do not understand how section 3 contributes to this community, since breaking exchangeability leads to the failure of the bound is somehow expected. I do not think it deserves a whole section to validate this. Some other presentations are similar. For example, does the formula in Line 258 is rather important? I think use the in-line formula is enough. Overall, I think the writing needs a polish.
Questions for authors
Could the authors show the challenges on combining the FCP and distribution shift tricks in conformal prediction, either theoretically or empirically?
6 comments
Reply [2/4]
2. How our work overcomes these difficulties.
Our approach addresses this problem by introducing a shift-dependent population function and establishing explicit high-probability calibration-to-test inequalities.
Let and . Define the weighted empirical calibration distribution and its population counterpart as
We then introduce the population function
which explicitly captures the relationship between the weighted calibration-score distribution and the test-score distribution. Unlike the nominal level , this quantity remains meaningful even when the weighting function does not perfectly correct the shift.
The essential technical challenge is to establish a finite-sample comparison between the random weighted empirical distribution and its population counterpart . This is not a direct application of the standard conformal rank argument: the calibration distribution is self-normalized, with a random numerator and denominator constructed from the same observations, and the resulting probability must subsequently be evaluated under a potentially different test distribution.
Our analysis overcomes this difficulty in two complementary ways.
Fixed-level control (Theorem 4.1). For a prescribed , we construct an appropriate population threshold and consider
By exploiting the bounded range of these weighted variables, we establish a concentration inequality that directly controls the relevant self-normalized comparison, obtaining the explicit error
The resulting calibration-conditional inequality is
This is the crucial step that is not directly provided by existing Covariate Shift PAC guarantees under our general OPDS assumptions. Combining it with standard concentration over the independent test batch yields
Uniform control (Theorem 4.2). Extending the preceding argument uniformly over presents an additional challenge. A fixed-threshold concentration inequality cannot simply be applied to an uncountable collection of thresholds through a union bound. To address this, Appendix B.2 develops a uniform concentration argument for the weighted empirical numerator through a randomized-thinning construction. We combine a one-sided DKW inequality with McDiarmid's inequality to establish
We separately control the random normalization using Hoeffding's inequality. Combining these concentration events gives
where is explicitly characterized in Theorem 4.2. In particular, this establishes the simultaneous implication
which yields
Only after establishing this uniform calibration inequality can we invoke test-batch DKW concentration to obtain our final guarantee:
Therefore, the difficulty is not merely applying concentration twice. It lies in constructing and proving the appropriate calibration-to-test inequalities under general Distribution Shift, while explicitly controlling the dependence induced by weighted normalization and obtaining simultaneous validity over all miscoverage levels. These are the central theoretical contributions of Theorems 4.1 and 4.2.
Reply [3/4]
3. Additional contributions.
Beyond these forward guarantees, our work also addresses two important problems that are not directly resolved by the aforementioned approaches.
Inverse FCP guarantees. Rather than fixing and studying the resulting FCP, we consider the inverse problem of selecting a conformal level to achieve a prescribed target FCP with high probability. Under general OPDS, need not be strictly increasing or invertible, making direct inversion inappropriate. We address this through its generalized inverse
and establish both fixed-target and uniform-in-target guarantees in Corollaries 5.5 and 5.6. For example, the fixed-target result guarantees
for any . This extends our analysis from characterizing realized FCP to selecting a miscoverage level that satisfies a desired batch-level error tolerance.
Practical estimation and consistency. A further difficulty is that and its generalized inverse depend on unknown population distributions and are generally not directly computable. Accordingly, Section 5 develops Algorithms 1 and 2 to construct empirical approximations using weighted calibration observations, with uniform consistency established in Theorems 5.3 and 5.7 under Assumption 5.2. Importantly, Assumption 5.2 is introduced for the consistency analysis of these estimation procedures, not for the main finite-sample FCP guarantees. Algorithms 1 and 2 remain computationally applicable when this assumption is violated, although their consistency is then no longer guaranteed.
We further investigate the relaxation of this assumption in Appendix C.2. By introducing independent labeled holdout observations from the test distribution, Algorithms 3 and 4 allow the unknown population quantities to be estimated without exact score transport. Theorems C.2 and C.3 establish uniform consistency under the substantially weaker Assumption C.1, which does not require the weighted calibration-score distribution to match, or even closely approximate, the test-score distribution. These results further extend the applicability of our estimation framework to settings with imperfect weighting.
4. Summary of our contributions.
While the underlying statistical tools are classical, we respectfully emphasize that our work is not simply a direct combination of previously established FCP and Weighted CP techniques. The main contributions are:
- Establishing explicit finite-sample, high-probability FCP guarantees under general OPDS, beyond the exchangeability and Covariate Shift conditions underlying existing finite-sample approaches.
- Developing new calibration-to-test concentration arguments for self-normalized weighted empirical distributions, including uniform control over a continuum of miscoverage levels.
- Extending these guarantees to the inverse FCP problem, with both fixed-target and uniform-in-target guarantees.
- Developing practical estimation procedures, proving their consistency, and providing a theoretically justified extension under a weaker score-distribution assumption.
We have added Appendix C.5 to clarify the relationship with prior approaches and the technical challenges addressed by our finite-sample FCP guarantees under general OPDS.
References
[1] Gazin, U., Blanchard, G., & Roquain, E. (2024). Transductive conformal inference with adaptive scores. International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1504–1512. PMLR.
[2] Blain, A., Thirion, B., & Neuvial, P. (2025). False coverage proportion control for conformal prediction. Forty-second International Conference on Machine Learning (ICML).
[3] Gazin, U. (2024). Asymptotics for conformal inference. arXiv preprint arXiv:2409.12019.
[4] Pournaderi, M., & Xiang, Y. (2024). Training-conditional coverage bounds under covariate shift. arXiv preprint arXiv:2405.16594.
Reply [1/4]
W1. Unfortunately, I find ... contributions of this paper.
Q1. Could the authors show the challenges on combining the FCP and distribution shift tricks in conformal prediction, either theoretically or empirically?
We thank the reviewer for this important observation and the opportunity to clarify our theoretical contributions. We acknowledge that both False Coverage Proportion (FCP) and Weighted Conformal Prediction (CP) are well-established research directions. However, we respectfully disagree that establishing finite-sample FCP guarantees under Distribution Shift follows directly from combining existing techniques. Although these frameworks are conceptually related, their existing theoretical results do not directly resolve the key mathematical difficulties arising when calibration and test observations follow different distributions. Our contribution lies in overcoming these difficulties to establish explicit finite-sample guarantees, including uniform and inverse FCP control, under general One-Phase Distribution Shift (OPDS).
1. Why existing approaches are insufficient.
We first distinguish our contributions from three closely related lines of research.
Existing FCP theory [1, 2]. These works establish finite-sample, high-probability control of the realized FCP under exchangeability. Their guarantees exploit the joint structure of conformal p-values when calibration and test scores share the same distribution. Under Distribution Shift, this structure is generally lost, and the resulting guarantees need not remain valid. Indeed, our experiments in Section 3 (Figure 1) demonstrate that applying these bounds under Covariate Shift can result in empirical guarantee probabilities substantially below the nominal level, sometimes reaching zero.
Weighted FCP under Distribution Shift [3]. This is the closest related work, as discussed in Appendix A.2. Gazin [3] studies weighted FCP under Distribution Shift, including oracle and non-oracle weights, through functional central limit theorems characterizing the limiting FCP process. While these results provide an important asymptotic understanding of how distribution shifts affect conformal errors, weak convergence does not establish finite-sample probability guarantees. In particular, it does not provide an explicit non-asymptotic error term controlling the deviation of the realized FCP at given calibration and test sample sizes (n,m). Obtaining such guarantees requires a separate concentration analysis, rather than directly applying the asymptotic results.
PAC and training-conditional coverage under Covariate Shift [4]. These results control the conditional miscoverage probability under assumptions relating the calibration and test distributions, particularly the preservation of P(Y∣X) and suitable importance weighting. We agree that such conditional-coverage bounds can be combined with test-batch concentration to obtain FCP guarantees within their respective settings. However, our Assumptions 2.2 and 2.3 are substantially more general: they permit changes in P(Y∣X), do not require oracle density ratios, and do not assume that the weighted calibration-score distribution matches the test-score distribution. Consequently, the existing conditional-coverage guarantees cannot be directly applied.
The last distinction illustrates the central theoretical difficulty. Let
qn(α):=Ptest(pw,(n)≤α∣Dcal)
denote the calibration-conditional miscoverage probability. Since test observations are independent given the calibration data, a standard Hoeffding argument yields
P(FCPmw,(n)(α)≤qn(α)+εtest∣Dcal)≥1−δtest.
However, this only controls the realized FCP around the unknown conditional probability qn(α), not around the nominal miscoverage level α. Under general OPDS, these quantities may differ substantially. For example, consider unit weights with calibration scores S∼Unif(0,1) and test scores T∼Unif(0.5,1.5). This setting satisfies Assumptions 2.2 and 2.3, yet for α=0.1, as n→∞,
qn(0.1)⟶P(T≥0.9)=0.6.
Thus, the conditional miscoverage probability approaches 0.6, rather than the nominal level 0.1. No improvement in test-batch concentration alone can resolve this discrepancy, because the difficulty arises from the systematic difference between the underlying score distributions, not from sampling fluctuations within the test batch. This demonstrates that establishing FCP control under general OPDS requires an additional theoretical ingredient: a finite-sample characterization of qn(α) that explicitly accounts for Distribution Shift.