On Volume Minimization in Conformal Regression

We sincerely thank the reviewer for their valuable feedback and for pointing out relevant related work. Below, we address each of their questions and comments.

• Q1 In https://link.springer.com/book/10.1007/b106715, Theorem 2.10, the authors provide a proof by construction, that can be used to derive the narrowest possible (in the sense of diameter or volume) conformal prediction region. How does the authors' work relate to that result?.

We appreciate the reviewer for highlighting this result. After carefully examining Theorem 2.10 and its proof, we find that our work does not explicitly relate to it. From our understanding, the proof constructs a theoretical conformal set that is guaranteed to be at least as efficient as a given conservatively valid confidence predictor. However, it is not evident that this result can be leveraged to construct a conformal predictor of minimal size in practice. In contrast, our approach explicitly formulates and empirically solves the length minimization problem.

• Q2 In https://proceedings.mlr.press/v216/sale23a.html, the authors show that the volume is not a good measure for (epistemic) uncertainty for classification problems with more than 2 classes. How does this result compare with what the authors present in their paper?.

The referenced paper differs significantly from our work. First, it does not explicitly address Conformal Prediction (CP) but rather focuses on credal sets as a means of quantifying uncertainty. Additionally, their analysis is centered on classification, whereas our work focuses on regression (extending to high-dimensional settings is left as future work by the authors). That being said, the authors do show that, in dimensions greater than two, measuring uncertainty through the volume of the credal set is inadequate—at least with respect to the axioms they propose (Section 3 of [1]). To draw a direct comparison between our work and the one mentioned by the reviewer, one would need to establish a precise connection between credal sets and conformal prediction and investigate whether the results in [1] extend to the volume of conformal prediction sets. We find this to be an interesting open question for further analysis of CP as an Uncertainty Quantification (UQ) technique.

[1] https://proceedings.mlr.press/v216/sale23a.html

• Q3 Despite the ubiquitous claim that [...] for future research.

We thank the reviewer for bringing these references to our attention. We fully agree that CP is better described as an uncertainty representation tool rather than a UQ technique, which is why we deliberately avoided making such a claim in our work. It appears that this comment, like the previous question, highlights a general limitation of CP rather than a specific limitation of our contribution. Nevertheless, we find that linking CP with more classical UQ frameworks (e.g., credal sets) presents an exciting research direction. We will mention this in the conclusion of our paper as a promising avenue for future work.

• Q4 It is also worth to notice that CP is not entirely model-free, since the volume (and diameter) of the resulting conformal prediction region depends on the choice of the non-conformity score. This was already pointed out in https://www.arxiv.org/abs/2502.06331. The authors are suggested to include this fact in their work.

We fully agree with the reviewer, as this observation aligns with one of the conclusions of our paper: the choice of the prediction set class $\mathcal{C}$, which depends on $\mathcal{F}$ in Section 3, has a significant impact on the volume of the conformal prediction region. We will clarify this point in the final version of our manuscript and include a reference to the mentioned paper (noting that it was made available after the ICML submission deadline).

We sincerely appreciate the reviewer’s thoughtful feedback and the references provided. We acknowledge that some relevant prior works were overlooked, and we will incorporate them into the related work section to ensure a more comprehensive discussion. While we recognize that this may slightly refine the novelty claims of certain aspects of our work, we firmly believe that our contribution remains distinct and complementary to these existing efforts.

In particular, while most of the cited works (except [5], which focuses on linking CP set size to the conditional entropy $H(Y|X)$) aim to theoretically analyze the size of conformal prediction (CP) sets, none explicitly study the notion of "excess volume loss" introduced in our work. This metric quantifies the gap between the CP set size and an oracle reference, offering a more precise measure of inefficiency. For instance, while [4] provides a PAC-Bayesian upper bound on CP set size, their analysis does not incorporate an oracle baseline, preventing an explicit characterization of suboptimality.

Below, we present a new paragraph that will be added to the related work section, directly addressing the reviewer’s concerns.

---

New Paragraph: Comparison with Missing Related Works

Recent studies [1,2,3] have analyzed the expected size of split CP sets, highlighting key factors such as the impact of the score function choice [1] and the generalization properties of the base predictor [2,3]. In [4], the authors take a step further by deriving a PAC-Bayesian upper bound on the expected CP set size, involving an empirical estimate of the size and a KL divergence term. They also propose an algorithm that modifies the calibration step of split CP to minimize their bound; however, they do not explicitly instantiate their bound for their proposed algorithm, leaving the practical implications unclear.

Our work differs from these approaches in several fundamental ways. First, our theoretical guarantees are PAC-based rather than PAC-Bayesian, eliminating the need for restrictive assumptions such as boundedness of the score function or target variable $Y$. More crucially, our analysis introduces an upper-bound on the excess volume loss, explicitly quantifying how much larger the CP set is compared to an oracle reference. This perspective is absent in prior works, which focus only on bounding the expected CP set size without reference to an optimal baseline. Finally, it is worth mentioning [5], which provides an information-theoretic perspective by linking CP set size to conditional entropy.

---

$\alpha$ different between learning and calibration

This is an interesting question. To address it, we conducted additional experiments where the QAE problem was solved with $\alpha_{QAE} = 0.05, 0.1$ and $0.9$. The results are presented in the following anonymous figures: (1) Figure 1 – Length for Normal and Normal + Extreme, (2) Figure 2 – Length for Pareto and Pareto + Extreme, (3) Figure 3 – Coverage for Normal and Normal + Extreme, (4) Figure 4 – Coverage for Pareto and Pareto + Extreme.

From Figures 1 and 2, we observe that QAE with $\alpha_{QAE}=0.1$ produces the smallest prediction sets. However, when no extreme values are present, the choice of $\alpha_{QAE}$ appears to have little impact. In contrast, when extreme values exist in the distribution, selecting $\alpha_{QAE}=0.05$ significantly deteriorates the final prediction sets. This is expected, as the dataset is constructed such that 5% of the values are extreme. Consequently, QAE with $\alpha_{QAE} = 0.05$ attempts to find $\hat{f}$ that minimizes the error for these extreme values, which is the opposite of being "robust." Figures 3 and 4 confirm that the calibration step ensures the final coverage remains close to 0.9.

Notice that a similar sensitivity to $\alpha$ can be observed in other conformal prediction methods, such as CQR, when the $\alpha_{CQR}$ values for the quantile regressors are poorly chosen.

We sincerely thank the reviewer for their thoughtful and constructive feedback. We are especially grateful for their recognition of the clarity and novelty of our contribution, particularly our use of statistical learning theory in the context of split conformal prediction. We will incorporate the suggested writing improvements in the final version of the manuscript. Below, we address the reviewer’s main questions and remarks.

Questions

• Q1. The assumptions to obtain Theorem 3.7 are not clearly stated: are the training and the calibration data assumed to be i.i.d.?

Yes, our theoretical analysis, including Theorem 3.7, assumes that both the training and calibration data are i.i.d. We will explicitly state this assumption in the manuscript.

• Q2. I guess that unfortunately, there are no theoretical guarantees for the computationally more efficient procedure described in Section 3.3? This looks like a critical limitation, which my score takes into account (I would raise it if I misunderstood this).

The reviewer is correct—our theoretical guarantees currently apply only to the idealized procedure, and we do not yet have formal guarantees for the computationally efficient variant. We acknowledge this as a limitation and appreciate the reviewer bringing it to our attention. We will explicitly discuss this in the manuscript and highlight it as an important direction for future theoretical research.

• Q3. Could you clarify the statement "theoretical analysis highlights how the complexity of the prediction function classes impacts the prediction interval's length"? From my understanding the upper bound (13) given in Theorem 3.7 is only an upper bound, and can only give some insights, especially as both its first and third terms depend on the complexity of the prediction function classes.

The reviewer is absolutely right that Theorem 3.7 provides an upper bound rather than a precise characterization of the true interval length. Our goal was to emphasize that this bound offers insights into how the complexity of the function class influences the gap between the constructed interval length, $\lambda(C_{\hat{f},\hat{t}}^{1-\alpha})$, and the optimal one $\lambda(C_{f^*,t^*}^{1-\alpha})$. Specifically, as the complexity of the function class increases, more training data is required for the bound on this difference to converge.

• Q4. Did you consider the length minimization problem for another non-conformity score? If you did, do you know if similar results hold for signed non-conformity scores (such as the residuals), which seem more adapted to the asymmetric heavy-tailed distribution you considered in Section 5?

To clarify, our framework does not explicitly rely on a chosen non-conformity score. Instead, the choice of score function is implicitly determined by the class of prediction sets, $\mathcal{C}$, that we consider—namely, intervals of constant (Section 3) or adaptive (Section 4) lengths. Conversely, in standard split conformal prediction, one can view the choice of non-conformity score as implicitly defining a class of prediction sets.

In Section 3, the scores used in the calibration step correspond to absolute residuals $|y-f(x)|$, whereas in Section 4, they take the form $|y-f(x)| - s(x)$, which are signed scores. To answer the reviewer’s question, since we have not considered alternative classes of prediction sets, we have not explored other types of score functions. However, as emphasized in our conclusion, extending our framework to other classes of prediction sets (and therefore score functions) is an important direction for future work.

• Q5. I am surprised that the empirical coverages given in Figures 2-3-4 are, on average, slightly below the nominal coverage of 90%. How did you implement the SCP procedure in your experiments?

We appreciate the reviewer pointing out this observation. After re-running our experiments, we found that the slight undercoverage was due to the limited number of repetitions in our empirical evaluation—averaging over 50 trials was not sufficient to smooth out random fluctuations. Indeed, due to the inherent stochasticity of different random datasets, finite-sample variability can cause slight deviations from the coverage. We will clarify this in the appendix.

We sincerely thank the reviewer for their constructive feedback and insightful questions. Below, we address each point in detail. We also appreciate the suggestions regarding our real-world data experiments and the approximation of the indicator function—these will be included in the final version using the extra page.

Questions:

• For Theorem 3.7, what does the distribution of $Y$ being atom less imply? Why is that required? In Proposition 3.1, what happens when $(n_c+1)(1-\alpha)$ is an integer? Will the same proof not extend to this setting?

We address both questions together, as they are closely related. In both Theorem 3.7 and Proposition 3.1, at least one of the two conditions must hold. This requirement stems from a technical detail in our proofs, where we rely on an inversion property of the quantile function with the cumulative distribution function (e.g., line 583). This inversion does not behave well when the distribution has atoms, requiring careful handling. In the context of regression, assuming that $Y$ is atomless is a reasonable and often natural assumption.

• What are the differences between the analysis done in this paper and that of Romano et al. [2019] to develop conformal quantile regression?

There seems to be a misunderstanding. In Romano et al. [2019], the authors construct prediction intervals by performing quantile regression of $Y$ given $X$ at levels $\alpha/2$ and $1-\alpha/2$, without learning a scalar prediction function. In contrast, our approach first learns a prediction function $f$ by minimizing the empirical $(1-\alpha)$-QAE, and then (for Ad-EffOrt) estimates the quantile function of the residuals $|Y-f(X)|$ given $X$ to construct the prediction interval. While both methods involve quantile regression, their objectives differ. Additionally, Romano et al. [2019] do not theoretically analyze the size of the resulting prediction sets.

• What are the differences between the algorithmic choices in this paper and that of Stutz et al. [2022]?

Stutz et al. [2022] propose a method to incorporate conformalization directly into the learning phase by minimizing inefficiency through a differentiable loss. Key differences with our work include:

1. Their focus is on classification, while we consider regression with residual scores.

2. Our method directly optimizes the $(1-\alpha)$-quantile of the scores, whereas they define and minimize an efficiency loss, necessitating an additional data split. Additionally, we use a different technique for the smoothing of the quantile function.

3. Their approach requires a more complex algorithm, making theoretical analysis of prediction set sizes more challenging, whereas we provide explicit theoretical results on set sizes.

Overall, while both approaches share conceptual similarities (e.g., smooth quantile computation), the methodologies differ significantly.

• How is Collarary 3.3 different from other bounds like Lei and Wasserman [2013]?

Could the reviewer be more precise by providing an equation to which he/she refers to in Lei and Wasserman [2013]? After a carefull check, it seems that this paper contains mostly asymptotic results, holding for their specific KDE-based estimator, but we might have missed something.

• Is it possible to experimentally validate the theoretical results?

We made additional experiments to validate the theoretical result of Prop. 3.1. In the two following figures: https://ibb.co/G4MPB244, https://ibb.co/MDJDG33J, we illustrate the bound when $\delta=.2$ and $\alpha=0.5$. The first figure displays the evolution of one realisation of $\lambda(\hat{C})$ (in blue) and the rhs term of Eq. (7) (denoted $2Q$, in orange) with respect to the number of calibration points $n_c$. The second figure displays an histogram of the distribution of $\lambda(\hat{C})$ when $n_c=200$. The red line corresponds to $2Q$, the rhs term of Eq. (7).

• Isn't splitting the data across steps 1 and 2 of Ad-EffOrt better to avoid overfitting?

This is a valid point. Splitting the data could improve generalization and reduce the prediction interval size. Theoretically, this could also facilitate deriving a bound similar to Theorem 3.7. However, even if overfitting occurs during training, the calibration step naturally corrects it by increasing the size of the prediction intervals.

• Is there a proof for Proposition 3.6? Yes, the proof is provided in Appendix B.2.

Other Related Work: We appreciate the additional references. As our work focuses on regression, we had not included classification-specific papers; however, we will incorporate them in the final version. Most of the other cited works are already referenced in our paper, except for Dhillon et al. [2024], for which we refer the reviewer to our response to Reviewer d77L.