Rectifying Conformity Scores for Better Conditional Coverage

We thank the reviewer for the thorough and constructive feedback, which helps improve our manuscript. Below, we address your valuable points:

The main limitations of RCP can be summarized as follows:

• The quality of the prediction regions heavily depends on the basic conformity score $V$. For example, if the underlying multi-output conformal method predicts hyperrectangular sets, RCP will also predict hyperrectangular sets.
• The quality of the conditional coverage of the intervals crucially depends on the quality of the conditional quantile estimator $\hat{\tau}(x)$ of the conformity score. The marginal coverage guarantee is always ensured; however, the guarantee of conditional coverage clearly depends on how $\hat{\tau}(x)$ approaches $\tau_*(x)$, the "exact" quantile. A key contribution of our work is the explicit tracking of how errors in quantile estimation influence conditional coverage error.

Additional experiment on synthetic data. Following your advice, we conducted an additional experiment on synthetic data to investigate the case of learned quantile estimate. We used a simple MLP trained on a dataset of varying sizes ranging from 100 to 500 points (note that the calibration dataset size in this experiment is equal to 500). The resulting plot can be found via https://pdfhost.io/v/ND3Dt3PahY_Additional_synthetic_data_experiment We see that the conditional coverage is not perfect, but RCP outperforms the standard CP already for a relatively small data size of 100 points.

Why assumption H2 is needed? This assumption ensures that the score function is compatible with the adjustment function. Only valid $t$ values will be supplied to $f\_t(v)$ to ensure that H1 is satisfied. For example, if $f_t(v)=tv$ then $\hat{\tau}(x)$ has to be positive.

Connection with normalized conformity scores. There is indeed a connection to prior works on normalized conformity scores. We will incorporate these references into the literature review of the camera-ready version (if accepted). Normalized Conformity Scores (NCS) all share the core idea of normalizing nonconformity scores by the predictive accuracy of the underlying model at new data points. This normalization aims to enhance the efficiency of conformal predictions by assigning wider prediction intervals to challenging instances and narrower intervals to easier ones, with the difficulty determined by the accuracy of the predictive model itself. However, these studies generally lack a detailed analysis of approximate conditional coverage, which distinguishes our work. Furthermore, we can recover the specific formulation of normalized nonconformity scores through an appropriate choice of the function $f_{\tau}(v)$. However, the criterion employed in our method to estimate $\hat{\tau}(x)$ fundamentally differs.

We provide further details below.

• U. Johansson et al. [1] and Papadopoulos et al. [2] investigate NCS methods, which enhance standard conformal prediction by dynamically adjusting prediction interval sizes according to instance difficulty. Normalization in their methods involves a parameter $\beta$, which balances the model's prediction error and the estimation of difficulty. However, these methods lack explicit theoretical guarantees. Their NCS can be represented within our framework through a specific choice of the function $f_{\tau}(v) = v/(\tau + \beta)$. Notably, the estimation approach employed in these papers uses least-squares regression on residuals, in contrast to the quantile regression approach adopted in RCP. The central goal in RCP is to construct a "rectified" conformity score that aligns conditional and unconditional quantiles at a target level--an objective distinct from NCS.

• The paper by Dewolf et al. [3] provides an insightful summary of normalized conformal predictors, introducing the concept of a taxonomy function, which they assume to be discrete. In their own terms, the taxonomy function "divides the instance space based on an estimate of the uncertainty," for example, by partitioning the feature space through binning the (conditional) standard deviation. However, their analysis is restricted to an oracle setting, meaning that the theoretical developments rely on an exact, known normalizing function. Consequently, their work does not address the practical scenario in which this normalizing function must be estimated from data.

[1] H. Papadopoulos, A. Gammerman, and V. Vovk. Normalized nonconformity measures for regression conformal prediction. In Proceedings of the IASTED International Conference on Artificial Intelligence and Applications (AIA 2008), pages 64–69, 2008.

[2] U. Johansson, H. Boström, and T. Löfström. Investigating normalized conformal regressors. In 2021 IEEE Symposium Series on Computational Intelligence (SSCI), pages 1–8. IEEE, 2021.

[3] N. Dewolf, B. De Baets ,and W. Waegeman, Conditional validity of heteroskedastic conformal regression. Arxiv 2023.

We acknowledge the critical feedback and aim to address the raised points. Below we clarify why the undiscussed references, while indeed valuable, mostly address aspects different from the specific problem we focus on. The following discussion highlights the distinctive advantages of our RCP method for constructing confidence sets in multivariate prediction, offering exact marginal coverage and strong theoretical guarantees for conditional coverage.

Discussion of the references provided in the review.

• Among the papers cited, Gibbs et al. (2023) is the one most directly related to our work, as it acts as a wrapper on given conformity scores. It has already been discussed, but additional comments and experiments are worthwhile. From a computational point of view, their method (called CPCG below) is very intensive, mainly because the wrapper uses a form of the "full conformal" idea, which requires solving an optimization problem at test time. Its strength lies mainly in finite-sample guarantees tailored explicitly to specific feature subsets and covariate shifts (see Theorem 2 for finite-dimensional class). This targeted approach suits group conditional coverage (Corollary 1) well. In contrast, RCP uses a split-conformal idea that estimates a quantile function on a special subset of the data, which greatly improves computational complexity. Also, for RCP, we provide a more generic theoretical result that is agnostic to a particular estimation method used (Theorem 4), and also specify it for the case of local quantile regression (Proposition 5). The proof of the results is not straightforward and requires the usage of non-trivial technical tools such as very recent extensions of DKW inequality (see Lemma 16).

• Cherian et al. (2024) is a CP framework tailored for LLMs. The method is not easily applicable to conventional regression or standard multivariate classification scenarios, where more broadly effective methods like RCP are more natural.

• Xie et al. (2024) refine conformity scores via gradient boosting to enhance conditional coverage while achieving exact marginal coverage in univariate prediction models. This method is constrained to scalar outcomes and lacks a natural extension to multidimensional settings. Further, the lack of analytically interpretable theoretical guarantees on conditional coverage and reliance on numerous hyperparameters and differentiable approximations complicates both theoretical understanding and practical implementation.

• Kiyani’s (2024) CPL method combines conditional validity and optimized efficiency through constrained optimization, designed exclusively for univariate prediction intervals. While CPL provides exact coverage tailored for a specific class $\mathcal{F}$, it is fundamentally limited by its complexity. Specifically, the reliance on intricate optimization procedures limits broader practical application, especially for multivariate outputs. In contrast, RCP’s computational simplicity and broader versatility in handling multivariate scenarios position it distinctly ahead.

Thus, among these methods, RCP clearly emerges as superior, particularly in multivariate predictive contexts. It balances precision in conditional coverage with practical simplicity, computational efficiency, and broader applicability.

Empirical comparison with CQR and CPCG. We conducted an additional experiment to directly compare RCP and CPCG (see https://pdfhost.io/v/26gN4fUeS2_rebuttal-R3jf). We observe that CPCG and RCP give similar conditional coverage, while RCP is at least two orders of magnitude faster. Compared to CQR, it trains a quantile regression model directly on the whole training set, while RCP can be applied to any black-box model and does not require access to the training data or internal model structure. Figure 10 shows that RCP can match or outperform CQR in a multidimensional setting.

Technical novelty. The technical novelty of RCP lies in its approach to enhancing conditional coverage through the concept of "rectifying" conformity scores. Unlike conventional methods requiring estimating the entire conditional distribution for multivariate predictions, RCP simplifies the problem by calculating only the conditional quantile of a univariate conformity score. This quantile estimation is a wrapper around classical methods explicitly tailored for multivariate prediction sets. Furthermore, RCP provides explicit theoretical lower bounds on conditional coverage, directly linking prediction accuracy to the quantile estimation approximation error. These results are based on careful and non-trivial analysis as discussed above. While competitive methods exist for univariate predictions, such comparisons are irrelevant, as univariate scenarios are explicitly not our targeted application. Thus, our proposed RCP method represents a meaningful advancement, combining clear theoretical foundations with practical efficiency for multivariate prediction tasks.

We thank the reviewer for the thorough and constructive feedback, which helps improve our manuscript. Below, we address your valuable points:

Effectiveness of quantile estimation in high-dimensional settings: Indeed, quantile estimation accuracy critically affects RCP performance. In our experiments, we selected neural networks and local quantile regression specifically due to their scalability to higher dimensions. However, we acknowledge that our explicit evaluation in very high-dimensional regimes remains limited. Following your suggestion, we will include additional discussions and empirical results to better highlight performance and trade-offs in higher-dimensional settings.

Choice of the transformation $f_t$ There are numerous possible choices for the function $ f_t $. Thus far, we have always restricted ourselves to relatively simple transformations, often inherited from the literature on "normalized conformity scores," which we recognize should have been more thoroughly credited. We believe it is important that the proposed method remains simple and does not rely on hyperparameters, ensuring that the computational cost of this wrapper stays reasonable.

Additional experiments with challenging multivariate distributions: We appreciate your suggestion for extending experiments to more complex multivariate distributions, as this would further reinforce our empirical validation. However, our current synthetic and real-world examples demonstrate clear advantages, while the datasets have dimensions up to 16. In our revised submission, we will incorporate an experiment that highlights RCP’s behavior on more challenging multivariate datasets.

Impact of incorrect quantile estimation: We agree that understanding the impact of incorrect quantile estimation beyond synthetic noise is crucial. To address your comment, we plan to include a detailed analysis showing how estimation errors affect coverage in more realistic settings, thereby providing deeper insights into RCP’s robustness and practical utility.

Extension to sequential settings: Your question regarding sequential adaptation is insightful. While we had not previously explored this application, we find it highly promising. There are no conceptual or methodological difficulties; however, from a theoretical standpoint, everything remains to be developed. RCP’s framework naturally extends to online learning by sequentially updating the quantile estimator based on newly observed data. We envision future work that formally explores sequential conformal adaptations and briefly outline such potential directions in our revision.

Clarification of minor points:

• We will correct inconsistent notation for $\hat{\tau}(x)$ throughout Section 4.
• The Lipschitz constant "L" in Theorem 4 will be explicitly defined earlier to improve readability.
• Figures 3 & 4 will indicate dataset sizes in the revised manuscript for enhanced clarity.

We appreciate your recognition of RCP’s conceptual novelty and theoretical rigor and your acknowledgment of our thorough experimental evaluation. Your suggestions significantly strengthen the manuscript, and we will diligently incorporate these improvements.

We thank the reviewer for the thorough and constructive feedback. Below, we address your questions:

Q1: RCP's conditional coverage guarantee hinges on accurate estimation ... Even if the quantile regressor is misspecified, RCP’s conformal calibration guarantees valid marginal coverage by construction. Nevertheless, poor quantile estimates affect conditional coverage: underestimations yield local under-coverage, whereas overestimations produce overly conservative intervals. Such failure modes highlight that RCP inherits biases from quantile regression, reducing conditional efficiency despite correct marginal coverage. This sensitivity was illustrated in our synthetic experiments; additional examples and analysis will be provided.

Q2: RCP estimates a single... RCP computes quantiles of a nonconformity score and thus only concerns with the right tail of the distribution (when the nonconformity score gets large). Therefore, obtaining intervals with lower and upper quantile estimates is not typically needed. Note that for a one-dimensional prediction target, we can, of course, work with CQR-type interquantile intervals as a specific nonconformity score.

Q3: How restrictive are the assumptions about monotonicity and invertibility of the transformation functions? The monotonicity is essential for our approach as we insist on preserving the ordering of the conformity scores. After adjustment by a function with a fixed argument $\varphi$, a "large" nonconformity score must remain larger than a smaller one. Invertibility is a technical requirement that underlines our construction, but it is not as restrictive as the monotonicity assumption.

Q3: Can your method... the answer is yes. As an example, the adjustment function $f_t(v) = t + v$ does not restrict the range of scores. Specifically, it does not impose positivity or negativity constraints, thus naturally accommodating scenarios where the score can assume both negative and positive values. This flexibility is crucial for handling general scoring functions, ensuring applicability across a broad range of prediction tasks without additional transformations or restrictions.

Q4: The bound in Theorem 4 depends on... The Lipschitz property of the quantile function is standard in the statistical literature on conditional quantile estimation — see, for instance, the works [1,2] on this topic. It is difficult to delve into such subtle technical conditions in a short discussion. We will include a more substantial discussion of these contributions in the revised version.

[1] Y.K. Lee, E. Mammen, B. U. Park. "Backfitting and smooth backfitting for additive quantile models." 2010.

[2] M. Reiß, Y. Rozenholc, C. Cuenod. "Pointwise adaptive estimation for robust and quantile regression." arXiv:0904.0543. 2009.

Q5: Have you evaluated the size... Thank you for your suggestion. You're absolutely right — because RCP can generate larger sets for test instances with higher uncertainty, the resulting sets tend to have wider volume on average.

However, when looking at the median volume, avoiding outliers, RCP outperforms baselines:

We will report these metrics in Section 7.2.

Q6: How sensitive is performance... We discuss the sensitivity with respect to the choice of adjustment function in Appendices A.3-4. The choice has a significant influence on the results, as the ability of fixed single-parameter functions to rectify the results highly depends on the properties of the score distribution. An interesting future work is to design more flexible data-dependent adjustment functions. Sensitivity with respect to quantile regression is discussed in Appendix A.2, showing that a better fit of the quantile model improves the results.