Boosted Conformal Prediction Intervals

We thank the reviewer for their thoughtful comments. In response to each of the reviewer’s specific points:

Is this procedure amenable to any black-box predictor and can be considered a particular gradient boosting mechanism?

• As an evaluation metric, the contrast tree algorithm applies to any black-box predictor f, as it only requires three inputs, the features, the labels and the conformalized prediction intervals, which can be derived from the conformity scores calculated via the values the model predicts. Then the contrast tree algorithm automatically detects regions, where coverage is most uneven.

In general, I found the obtained improvements not overly convincing. For example, in Fig. 3 if we consider the % of data for which conditional coverage ends up being violated (above the red line) we find 33% for Local and 37% for Boosted Local.

• Assuming exchangeability, conformal prediction ensures that the average miscoverage rate over the test set is approximately 10%. The dream would be to achieve exactly 10% miscoverage within any subset of the feature space. While this might seem counterintuitive, the guarantee provided by conformal prediction implies that if one subset in the feature space has a miscoverage rate smaller than 10%, another disjoint subset must have a miscoverage rate greater than 10%. This results in prediction intervals that sometimes overcover and sometimes undercover. Figure 3 illustrates that before boosting, the conditional coverage in each leaf significantly deviates from the target rate of 10%; it is either too large or too small. After boosting, however, all groups have coverage rates that hover around 10%. Concretely, before boosting, the contrast tree identifies splits in the feature space that deviate from the 10% miscoverage rate by 15%. After boosting, the largest deviation identified by the contrast tree is reduced to no more than 6%.

In Table 1, boosting CQR only gives marginal improvements.

• Please refer to point 3 in the global rebuttal.

It would be good to compare the results to other conformal algorithms which claim to empirically (or sometimes even theoretically, under relaxed conditions or varying interpretations of conditionality) improve conditional coverage, e.g. [1,2,3,4].

• In comparison to other works aiming to improve conditional coverage, such as [1] and [2] mentioned by the reviewer, our approach offers a distinct advantage. Those works measure group conditional coverage based on user-specified groups. However, relying on predefined groups may not always be ideal. Specifically, please refer to point 4 in the global rebuttal.

Thus, tackling a more flexible scoring function comes at the cost of introducing another (fixed) functional to optimize over, with required approximations.

We agree with the reviewer that optimizing a targeted property requires a customized objective. We would like to highlight that the conformity score functions we discuss in the manuscript are arguably the two most widely used score functions for regression tasks. Although we do not address classification tasks in this project, it is worth noting that commonly used score functions in that domain, such as the threshold conformal predictor (THR) and adaptive prediction sets (APS), are also differentiable by design.

Should I understand that the boosting dataset is a separate set?

• During the boosting stage, we use the training set to simulate the conformal procedure, assessing the corresponding interval length and conditional coverage. Specifically, at each iteration of cross-validation, we divide the training set into a sub-boosting set and a sub-validation set (the held-out fold). The sub-boosting set serves as both the boosting set and the calibration set, while the sub-validation set acts as the test set. Please refer to Figure 2 for an illustrative schematic drawing. We shall work to explain this more clearly in the revised manuscript.

Response to other comments:

• We thank the reviewer for pointing out the typo in the 3rd final line of Algorithm 1. We shall fix this in the revised manuscript.
• We shall add a legend for clarity of presentation in the revised manuscript.
• We agree with the reviewer that a smaller prediction set or interval corresponds to higher power. In the manuscript, by "power loss," we intended to convey "loss of power," meaning that when the interval length is larger, we lose power. If the reviewer finds this phrasing misleading, we will rephrase it in the revised manuscript.
• We agree with the reviewer that Theorem 5.1 only proves that the search space contains the optimal solution, but does not guarantee the optimality of the numerical boosting procedure.
• We shall add hyper-referencing in the revised manuscript.

Response to questions:

• Please see our reply to the 1, 2, 3, 5 and 6th items in the Weaknesses section.
• For the motivation behind leveraging contrast trees, please refer to point 4 in the global rebuttal. One of the primary reasons we chose to approximate the empirical quantile using the Harrel-Davis quantile estimator is that it transforms the original linear combination of two samples into linear combinations of all samples, significantly enhancing the robustness of the optimization objective.
• Please refer to point 5 in the global rebuttal.

We thank the reviewer for their time spent reviewing the manuscript. In response to each of the reviewer’s specific comments on weaknesses: 1.

My main reservation with the proposed method is the seemingly marginal benefit it provides over CQR for conditional coverage, as shown in Table 1.

Please refer to point 3 in the global rebuttal.

Additionally, conditional coverage here is evaluated using contrast trees, which are baked into the objective of the boosting approach.

We would also like to clarify that while we use contrast trees in our loss function, we execute the contrast tree algorithm at each iteration of gradient boosting. In other words, we re-partition the feature space at each iteration as soon as the conformity score is updated. When we evaluate performance on the test set, we rerun the contrast tree algorithm on the test set, taking as inputs the features, the labels and the conformalized prediction intervals calculated on the test set. Therefore, the partition of the feature space at test time is different from that at boosting time.

It would be interesting to see if the improvements hold under, for example, just group-conditional coverage.

Please refer to point 4 in the global rebuttal.

2. We only partially agree with the reviewer that the improvement depends on the accuracy of the underlying model. Imagine we have infinite training data and that the underlying model perfectly identifies the conditional mean $E[Y|X]$ and the conditional expected absolute deviation $\text{MAD}(Y|X)$. Then plugging this in the local conformity score would not be optimal in terms of average interval length or conditional coverage. Below, we illustrate this with a simulated example. Assume that each X follows a uniform distribution Unif(0.1,1.1), and that $Y = X\cdot e$, where e is a random variable distributed as $\text{Beta}(a,b)-a/(a+b)$; this says that e follows a beta distribution shifted to have mean zero. We can theoretically calculate $E[Y|X]=0$, $\text{MAD}(Y|X) = X\cdot 2a^ab^b/\left(B(a,b)\cdot (a+b)^{(a+b+1)}\right)$. Here, $B(\cdot,\cdot)$ stands for the beta function. However, because a beta distribution is not symmetric, even if the training model perfectly fits $E[Y|X]$ and $\text{MAD}(Y|X)$, the conformalized prediction intervals will not be of optimal length, as shown in the left panel in the attached pdf. If we take the theoretical mean and MAD as trained, then the boosted Local score effectively adjusts for the non-symmetric nature of the underlying distribution, as shown in the right panel. The respective average conformalized interval lengths are 0.237 and 0.216. This is about a 10% reduction in size.

Response to questions:

1. We agree with the reviewer that an alternative approach could involve holding out a validation set in addition to the training, calibration, and test sets. However, as noted by the reviewer, this method presents a trade off: a small validation set can lead to high variability in prediction intervals and performance, while a large validation set may reduce the number of samples available for training, potentially limiting the model's effectiveness. In contrast, our procedure uses a form of cross-validation to avoid this trade off. To illustrate this, we will include experiments comparing the performance of the two procedures on real datasets in the revised manuscript.

2. We agree with the reviewer that the gradient boosting algorithm could potentially be replaced by other machine learning models. In this sense, the gradient boosting algorithm is not central to our contribution. Within our boosting framework, once the appropriate search space and loss function are established, any suitable machine learning model can, in principle, be used to search for an enhanced conformity score.

We thank the reviewer for their positive comments. In response to each of the reviewer’s specific comments on weaknesses:

• Please refer to point 1 in the global rebuttal.
• Please refer to point 5 in the global rebuttal.

Response to questions:

• Please refer to point 2 in the global rebuttal.
• Please refer to point 1 in the global rebuttal.
• We thank the reviewer for pointing us towards this literature. We shall include this in our revised manuscript when discussing the trade off between conditional coverage and interval length.
• In our revised manuscript, we will include additional results comparing the performance of our method with the approach outlined in [26]. While [26] primarily focuses on reducing prediction set size for classification tasks, our work is centered on regression tasks. Another difference is that [26] considers conformity scores based solely on predicted probabilities for each class. In a regression context, this approach is analogous to using only $\hat{y}$ or $\mu$ in the Local conformity score. To bridge this gap, we plan to conduct an experiment using two neural networks to fit $\mu$ and $\sigma$ in the generalized Local conformity score in an alternating fashion. The objective will be the differentiable approximation of the average prediction interval length, as formulated below line 264. Originally, the training model's objective for fitting $\mu$ was the mean squared error of $y-\mu$, and for fitting $\sigma$, it was the mean squared error of $|y-\mu|-\sigma$.

We thank the reviewer for taking the time to carefully review our manuscript. In response to each of the reviewer’s specific comments on weaknesses:

A comprehensive description of the experiment setting is necessary.

In our revision, we will more clearly describe our experimental setting. For concreteness, we shall make the following clarifications: we use the same data to train the initial prediction model and to boost. Building upon the trained prediction model $\hat{f}(x)$, we boost for an improved conformity score, and subsequently calibrate with the boosted conformity score on the calibration set. As a result, under the same exchangeability assumption as for the classical split conformal procedure, an expected marginal coverage rate of $1-\alpha$ is guaranteed on a new test point drawn from the same distribution.

Additionally, it is important to address potential outcomes if a distribution shift occurs.

We of course acknowledge that if the exchangeability assumption is violated (e.g., in the case of a distribution shift), the marginal coverage property may no longer be valid. Robustness vis a vis distribution shifts is the subject of an immense literature and outside of the scope of this paper; that said, this is an interesting direction to explore. It would be interesting to see how our boosting procedure could be combined with a line of research which relaxes the exchangeability assumption: for instance,

[1] Barber R F, Candes E J, Ramdas A, et al. Conformal prediction beyond exchangeability. The Annals of Statistics, 2023, 51(2): 816-845.

[2] Gibbs I, Candès E J. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 2024, 25(162): 1-36.

2. Please refer to point 1 in the global rebuttal.

3. Please refer to point 2 in the global rebuttal.

Response to questions:

1. We believe that different target coverage rates would not affect the effectiveness of our method. We shall report additional results with different nominal miscoverage rates in our revised manuscript.

2. We are somewhat confused about the reviewer's question. As mentioned previously, we use the training data in combination with cross validation during the boosting stage. Regarding the calibration set, as with any method that relies on a holdout set, an extremely small holdout set will inevitably lead to high variability in the performance of the method. This is not specific to our method, and in general we would not recommend relying on a small holdout set via any procedure, so we do not explicitly consider this question in our work. It is worth pointing out, however, that marginal coverage guarantees do hold regardless of sample size, since these results are “on average” and do not account for variability.