Volume Optimality in Conformal Prediction with Structured Prediction Sets

We thank the reviewer for detailed suggestions and providing more related works. We will ensure to make these changes to improve our paper and include discussions to related works.

• Experiments on real-world datasets would strengthen the utility of the proposed method

We implement our method and baselines on real-world datasets (See response to Reviewr Ubed for details). We also include the runtime comparison.

• A comparison of runtimes would help practitioners understand the tradeoffs between the different methods.

We will include the runtime comparison in the revision.

• Kiyani et al, 2024 "Length Optimization in Conformal Prediction" also studies optimality of prediction sets with an efficient algorithm for hypothesis classes with bounded complexity. It would be important to discuss the relation between the theoretical findings in this submission and this previous work. Furthermore, comparing the two algorithms would strengthen evidence.

We have a discussion about Kiyani et al, 2024 in Appendix A. We will include the comparison with them in the revision.

• Teneggi et al, 2023 "How to Trust Your Diffusion Model: A Convex Optimization Approach to Conformal Risk Control" also considers mean interval length minimization for conformal risk-control in high-dimensional settings.

We will discuss Teneggi et al, 2023 in the related work section.

• Connections with hypothesis testing: Could the authors expand on this connection?

Since both coverage and volume are two measures of sets (one is the data generating probability and the other is the Lebesgue measure), the volume optimality problem subject to coverage property is naturally connected to hypothesis testing between the two measures. This is exactly how we prove the impossibility result in the unsupervised setting.

Such a connection also holds when one considers conditional coverage and conditional volume optimality, and a similar impossibility result would hold.

More generally, one could consider (conditional) coverage and (conditional) restricted volume optimality. This is exactly the conformal prediction framework that we consider in the paper. While we proved that the proposed DP method satisfies both guarantees, it would be interesting to also study the sample complexity of the problem. To be more specific, one could ask if the coverage slack of order $\sqrt{(k+\log n)/n}$ in Theorem 2.5 is optimal or not. We believe the lower bound approach for this problem could also be tackled via the hypothesis testing connection. This will be a very interesting direction to explore in the future.

• Is this algorithm optimal in terms of complexity? Or could, for example, the last step of selecting the solution with minimum volume be avoided?

The final step of selecting the minimum volume solution can indeed be avoided by maintaining the best solution directly within the DP table. However, this does not improve the overall time complexity since the last step takes only $O(kn/\gamma)$ time. In practice, it is still possible to approximately implement this algorithm more efficiently through various tricks, for example by bucketing the samples.

• In Proposition 2.3, what is the role of point 1. ? How does this property of the algorithm play a role in the rest of the contributions?

Points 1 & 2 jointly guarantee that the output of the DP algorithm achieves the coverage and the restricted volume optimality with respect to the empirical distribution. Then, together with the uniform concentration, it leads to the restricted volume optimality with respect to the distribution of the testing sample in Point 2 of Theorem 2.5.

• Lines 27-30, right column: CP also provides a coverage upper-bound, which guarantees the sets are not trivial.

You are correct. We will change the wording here in the revision.

• Lines 119-127, right column: I understand $P^{n+1}$ is the measure of the test point. For $P^{n} \times \lambda$, does $P^{n}$ mean the measure of all previously observed points?

We have training data $X_1, …, X_n$ and testing data $X_{n+1}$. The $P^{n+1}$ is the joint distribution of all $n+1$ samples. In $P^{n} \times \lambda$, $P^n$ means the joint distribution of the training data with $n$ samples.

• Lines 292-294, right column: it is true that the construction is only needed for the calibration points, but it also needs to be performed for each new point at inference, which can be expensive.

The computational bottleneck is the construction of the nested system $\{S_j(x)\}{j\in[m]}$. It needs to be constructed for all calibration points $\{X_{n+1},...,X_{2n}\}$, together with the testing point $X_{2n+1}$. The $n+1$ nested systems are sufficient to evaluate the conformity score at each $y\in\mathbb{R}$. On the other hand, if one has more than one testing point, say $X_{2n+1}, …, X_{2n+r}$, then the nested systems will need to be computed for each individual one, and you are correct that it may be expensive when $r$ is large.

We sincerely thank you for the detailed and constructive feedback and the additional references that we missed. We will implement these changes in the revision of the paper.

We evaluated our method and different baseline methods on several real-world datasets in both unsupervised and supervised settings, and observed improved or competitive volumes in both settings.

For the unsupervised setting, we implement our conformalized DP method and the baseline conformalized KDE method on two real-world datasets (Acidity and Enzyme) used in density estimation literature (Richardson and Green (1997)). We set the target coverage at 80%, and repeat the experiments 50 times. We output the average and s.d. for volume and empirical coverage. We observe that our conformalized DP outputs a smaller volume prediction set than the KDE with the best bandwidth for almost all k>=2.

Acidity Dataset

Conformalized KDE Results

Conformalized DP Results

Enzyme Dataset

Conformalized KDE Results

Conformalized DP Results

For the supervised setting, we implement our method and the baseline methods on four UCI datasets Abalone, AirFoil, WineQuality, Superconductivity. These four real-world datasets are used in conformal prediction by Dhillon, Deligiannidis, and Rainforth (2024). We observe that our method outputs prediction sets with smaller volumes than baselines on two datasets WineQuality, Superconductivity. It provides competitive results on the other two datasets Abalone and AirFoil. The most prominent example showing the advantage of using unions of several intervals is the dataset WineQuality. In this dataset, the label Y space is integers from 0 to 10 for the quality of wine. The conformalized DP with 5 intervals clearly dominates all other methods including our own with k=1 due to the multimodality of prediction.

Abalone

AirFoil

WineQuality

superconductivity

Thank the reviewer for constructive suggestions and providing comprehensive references. We will make sure to implement these changes and include all related works in the revision.

• It would help to see a similar analysis done on real-world data.

We evaluated our experiments on various real-world datasets as well for the rebuttal, please see our response to Reviewer UBed for details.

• How does the proposed method compare to the baselines on computational cost?

We will include the running time comparison. Due to the time complexity of dynamic programming, our method is naturally slower than the baselines. But as we have shown in additional real dataset experiments, the running time of our method while larger is still comparable with that of baselines. Furthermore the running time of our method is dominated by the method for producing the conditional CDF estimate.

• The analysis does not include the standard deviations of the reported quantities. Since "outperforming" is a strong word (lines 407-408, column 2), one should consider the statistical significance of the results.

You're absolutely right that statistical significance is crucial when claiming "outperformance," and we will incorporate the averages and standard deviations of repeated tests to validate the results. For the unsupervised experiments on real-world datasets, we include the average and standard deviations in the result. Please see our reply to Reviewer UBed for details. The standard deviation for volume and empirical coverage is at most 10% and 2.5% respectively. We will make sure to report the standard deviations in all numerical experiments in the revision.

• Since Fig. 1a depicts the best proposed model, Fig. 1b should illustrate the best baseline model (I believe $\rho=0.25$ is the optimal hyperparameter from the search space chosen).

We agree that it makes sense for Fig. 1b to show the KDE method with the best bandwidth. We implement the baseline KDE method with $\rho=0.25$, and we will update the figure accordingly. We wanted to point out that for $\rho=0.25$, KDE still uses a relatively large interval to cover the left Gaussian, resulting in a total volume of 3.7049, much larger than our method. While the KDE method is very sensitive to the choice of bandwidth, our proposed DP is very stable with the choice of $k$ as long as it exceeds a certain threshold.

• Theorem 2.5 and 3.3 both assume i.i.d. data. How does the statement change if the calibration and test data are exchangeable and not i.i.d.?

If the data are only exchangeable, we still have the marginal coverage guarantee in Theorem 2.5 and 3.3. The volume optimality and the conditional coverage will not hold since the volume optimality is not well-defined in this case and the conditional coverage is generally impossible without additional assumptions.

• How is the index that satisfies the second requirement in Assumptions 2.4 and 3.1 chosen? Or, how is the index for step 1 in Section 4.1 chosen?

In Step 1 of Section 4.1, the index $j^*$ depends on $m$, $\alpha$, $n$ and $\delta$. The choices of $n$ and $\alpha$ are clear. For the other two parameters, $m$ stands for the discretization of $[0,1]$ in the nested system, and we typically need $m>1/\alpha$. Larger $m$ provides finer discretization for the nested system, and $m \leq n$. The number $\delta$ stands for the statistical error of estimating the (conditional) CDF. In later numerical experiments, we chose $m=50$ and $\delta=\sqrt{(k+\log n)/n}$ with $k$ being the number of intervals.

• When is the bound in Eq. 8 satisfied?

Eq. 8 is always satisfied with high probability, since the VC dimension of $\mathcal{C}_k$ is $O(k)$.

• Why is $P \ll \lambda$ required for the initial analysis in Section 2.1 (lines 76-93, column 2)?

Here, we intend to provide an example of the optimal-volume solution (the display after (3)) under the condition of $P \ll \lambda$, which means $P$ is absolutely continuous w.r.t. $\lambda$. When we introduce the notation of volume optimality in the next display, we emphasize that the condition $P \ll \lambda$ is no longer needed.

Thank you for your constructive suggestions and insightful questions.

• Since the guarantees are in expectation over the calibration set and the data is being simulated anyway, it could be good to get also the results averaged over multiple draws of the calibration data.

We appreciate this suggestion. You are right, it is important to get the results averaged over multiple draws. In the revision, we will ensure that all numerical experiments include both the average and standard deviations. In the additional experiments, we show the averages and standard deviations of repeated tests (See our response to Reviewer Ubed for details).

• Question: What is the issue (if any) generalizing this approach to prediction sets in $\mathbb{R}^n$? Does it blow up the DP space too much?

This is an excellent question. The DP approach can potentially be extended to low-dimensional spaces, such as dimension $d=2$ or $d=3$, to construct prediction sets that are unions of disjoint rectangles. However, as the dimension $d$ increases, the time and space complexity of DP grow exponentially, making it impractical for high-dimensional settings. Furthermore this is unavoidable; this problem is NP-hard in high-dimensions even for simple generalizations of intervals like Balls (even for one ball). However, we can use our framework with any algorithm that can find low-volume confidence sets (from a prescribed family) in high dimensions. More broadly, finding low-volume confidence sets in high-dimensional settings is an important and challenging task in high-dimensional statistics. Naturally, this is out of the scope of this work. In a followup project, we are currently working on computing approximately small volume prediction sets in high-dimensions like balls and ellipsoids, and unions of them.