PAC-Bayes Generalization Certificates for Learned Inductive Conformal Prediction

Summary

Inductive Conformal Prediction (ICP) provides a coverage guarantee of constructed prediction sets, while does not provide any guarantee on the efficiency of prediction sets. The efficiency depends on a conformity score function, and direct approaches optimize the score function to minimize the efficiency of prediction sets in two steps: (1) given a hold-out set from a calibration set, optimize the score function, and (2) given another hold-out set from a calibration set, run an ICP algorithm. However, the direct approaches do not provide a generalization guarantee for efficiency. The proposed approach combines ICP and the PAC-Bayes to provide generalization guarantees for both coverage and efficiency. In particular, the paper provides novel generalization bounds for coverage and efficiency and proposes an algorithm from them, where the efficacy is evaluated on regression and image classification problems.

Strengths

**Originality**: The paper proposes new generalization bounds on coverage and efficiency. **Quality**: The proposed algorithm is supported by theorems, making the algorithm rigorous. **Clarity**: I like the paper structure. It first provides the main theories, and then explains an algorithm with practical details (appreciate it). **Significance**: I believe the PAC-Bayes interpretation introduces an interesting, novel view on conformal prediction, which could trigger interesting CP algorithms.

Weaknesses

Combining PAC-Bayes and ICP is very interesting, though I have a few concerns. 1. It is not easy to find the benefit of the bound on efficiency (i.e., Thm2). This is novel, but in Algorithm 1, it also uses the first term of (8). What is the algorithmic benefit of the efficiency bound Thm2? 2. I assume that this paper uses the PAC-style ICP (4) as the baselines (i.e., “the standard ICP approach” and “a learned ICP approach”. However, (4) is known to be loose (as clearly mentioned in Vovk [2012]. In the same Vovk’s paper, it also has a tighter ICP (i.e., Proposition 2b in Vovk [2012]) and its tightness (and efficiency) is also well-demonstrated in deep learning applications in [R1]. If the authors use the tiger PAC-style ICP, would “the standard ICP” and “a learned ICP” baselines be possible to be better than the proposed approach in Figure 4? 3. It is unclear what the benefit of PAC-Bayes is in achieving an efficient prediction set. Based on Line 50 (i.e., “our framework allows us to utilize the entire calibration dataset…”), I initially thought that the proposed approach fully utilizes the calibration set (while direct approaches require splitting calibration sets into two). However, the proposed approach also needs to split the calibration sets for prior learning (i.e., Line 238). At this point, I was unsure of the benefit of combining PAC-Bayes with ICP. My guess is simultaneous optimization of a score function distribution Q and threshold \hat{tau} is one factor for achieving a better efficiency than the baselines, but I want to hear the author's clarification. 4. The nonconformity score function of the standard ICP in regression is quite weak, which misleads readers. The score function with only the residual (i.e., Line 282) is not recommended as it does not encode per sample uncertainty (as also mentioned in the paper). Instead, a variance normalized score function (i.e., (8) in [R2], 3.6 in [R1], or 2.2.1 in [R3]) is a better choice, where the variance is simply trained via a training set. Given this better score function, I don’t think “the standard ICP” result in Figure 3 is as poor as shown in the paper. [R1] https://arxiv.org/abs/2001.00106 [R2] http://proceedings.mlr.press/v91/vovk18a/vovk18a.pdf [R3] https://arxiv.org/abs/1612.01474

Questions

Each question is associated with each weakness in Weaknesses. 1. What is the algorithmic benefit of the efficiency bound in Thm2? 2. If the authors use the tiger PAC-style ICP (i.e., Proposition 2b in Vovk [2012]), would “the standard ICP” and “a learned ICP” baselines be possible to be better than the proposed approach in Figure 4? 3. Could you clarify on the benefit of PAC-Bayes in achieving an efficient prediction set? 4. If the authors use the variance normalized score function, do we still observe the same limitation of “the standard ICP” in Figure 3?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The limitations are clearly stated in Conclusion, and I agree with that.

Summary

This work first derives coverage and efficiency generalization bound using PAC-Bayes for inductive conformal prediction. Furthermore, a practical algorithm, basing bayesian learning and conformal training, is proposed to learn efficient nonconformity score functions. In experiment section, the proposed algorithm is shown to outperform two baselines (original ICP and learned ICP) in some scenarios.

Strengths

1, This work is mathematically solid, by combining PAC-Bayes theory with inductive conformal prediction. Particularly, it derives a efficient loss bound using PAC-Bayes for ICP. 2, In the experiment section, the proposed method outperforms other two baselines (original ICP and learned ICP) in many scenarios, demonstrating high efficiency, especially when limited calibration data is available. 3, The manuscript is well-written; and proposed method is mathematically sound.

Weaknesses

1, In the abstract, it is claimed that "the entire calibration dataset" can be utilized. In the practical algorithm, splitting the calibration dataset is still needed (to derive a good prior). As a result, in my opinion, the mentioned claim is at least controversial. 2, Though not mentioned, the proposed algorithm could be expensive in training and inference, as multiple models need to be sampled. 3, The empirical evaluation is insufficient. Only one synthetic dataset and one practical dataset are used. It would be appreciated if experiments on more practical datasets. With more empirical results, it could be more convincing to claim that the proposed method produces more efficient prediction sets.

Questions

1, How are the two derived bounds connected to the proposed algorithm?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

1, The computation complexity might be so high that the proposed method cannot trivial extend to larger datasets and models. 2, Without good prior, the derived bounds might be too loose.

Summary

The efficiency of set-valued predictor is crucial and less explored, this paper use the framework of PAC-Bayes to obtain the generalization bounds on both the coverage and the efficiency of set-valued predictors. The authors also propose a novel algorithm to optimize the efficiency without a separate hold-out dataset. They provide a theoretical guarantee for the proposed method and empirically verify the superiority of the proposed method.

Strengths

- This paper uses the framework of PAC-Bayes to analyze the efficiency of inductive conformal prediction, which is novel and less explored. - The algorithm proposed by this paper does not require a separate hold-out dataset, while still having a theoretical guarantee of coverage. - This paper is well organized and the presentations are clear to me.

Weaknesses

- To achieve the test-time coverage, the key constraint is shown in Corollary 2.1. However, the authors do not show whether it is satisfied in the experiments. - In the experiments, the authors show the average size of the prediction set, but I think the marginal coverage evaluated on the test data in the experiments is also important, and does a smaller average size of the prediction set empirically lead to worse coverage? - In the experiments, the description of the ***learned*** baseline is unclear. Do the authors train the model using the method proposed in [1]? Meanwhile, the authors miss a recent work [2] that aims to output a smaller conformal prediction set with higher conditional coverage. [1] and [2] should be chosen as baselines in the experiments. [1] David Stutz, Krishnamurthy Dvijotham, Ali Taylan Cemgil, Arnaud Doucet. Learning Optimal Conformal Classifiers. ICLR 2022. [2] Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, Yanfei Zhou. Training Uncertainty-Aware Classifiers with Conformalized Deep Learning. NeurIPS 2022.

Questions

Please see the weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

A limitation of this paper is that the theoretical results and proposed method can only be applied for a stochastic model.

Summary

Accurate uncertainty estimation is crucial in building robust and trustworthy machine learning systems. This paper utilizes PAC-Bayes theory and inductive conformal prediction (ICP) to develop a practical algorithm that fine-tunes parameters and score functions using calibration data, while ensuring inference coverage and efficiency. Empirical validation of this work shows that it is effective and outperforms prior methods.

Strengths

The paper presents a well-executed translation from theory to practical algorithm and provides a comprehensive analysis of related work. It also discusses the practical considerations in their proposed algorithm and effectively demonstrates its ability to make efficient predictions and achieve good generalization certificates in two experiments.

Weaknesses

Here are some suggestions for improving the original content: 1. It would be beneficial to provide more information and explanation in section 5.2 to help readers better understand the algorithm. 2. Consider including an experiment that explores the tradeoff between desired coverage and prediction performance. This would provide valuable insights into the algorithm's effectiveness.

Questions

I am interested in understanding the extent to which distribution shift can affect the performance of calibration and its coverage. Adding more noise to MNIST figures can increase the level of uncertainty, making it more challenging to ensure accuracy.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper identifies various limitations and proposes practical solutions to address them. The significance of this work lies in its contribution to achieving a more reliable and secure ML system. Particularly, it demonstrates its effectiveness in providing assurance to enhance the calibration of uncertainty.

Summary

This paper considers the setting of inductive conformal prediction (ICP). In this setting, given a learned point-predictor, a calibration set and a scoring function is used to obtain a set-valued predictor that contains the correct label with high probability. A drawback of previous approaches is that, for ICP guarantees to be valid, the scoring function has to be fixed, or part of the calibration set needs to be used to learn the scoring function, while the remaining part is used to learn the coverage sets. In order to solve this, the paper proposes to use PAC-Bayesian bounds for self-certified learning, so that the scoring function can be learned from the calibration data, while using the same calibration data to obtain test-time bounds by using generalization guarantees. The approach relies on new bounds, which are similar to known PAC-Bayesian bounds but specialized to the ICP setting, and data-dependent Gaussian priors according to a standard procedure. Numerical results demonstrate the potential of the proposed approach to improve ICP in low-data settings. **Post-Rebuttal edit**: I read the author rebuttal, which addressed my questions, and consequently updated the rating (as stated below).

Strengths

— The paper proposes a creative and relevant use of the PAC-Bayesian framework for a practical use-case — The presentation is pedagogic, providing an essentially self-contained summary of the necessary background from ICP and PAC-Bayes — In addition to just presenting bounds, the paper suggests a well-motivated practical algorithm that is shown to have potential to improve results for certain settings. The interpretation of the PAC-Bayesian bound as providing a "KL budget" is neat.

Weaknesses

— The discussion of the PAC-Bayesian bounds does not make it entirely clear what the relation to prior work is (see questions below). — The improvements that are seen in the numerical experiments appear to be marginal, and mostly within the error bars. The non-monotonicity in the order between "Learned" and "PAC-Bayes" in Figure 4 (middle) appears to highlight that they are essentially indistinguishable. Also, it was not entirely clear to me how Figure 3 demonstrated an improvement for PAC-Bayes.

Questions

— Theorem 1, in terms of the binary KL, is very similar to the Maurer-Langford-Seeger bound (see, e.g., Maurer (2004)). In Maurer's result, a smaller $B(N)$ is found. However, I don't think that the two arguments of your binary KL are related by an expectation as in Maurer's derivation, which necessitates the path that you take. Is this interpretation correct? I think the paper would benefit by clarifying the relation to these classical PAC-Bayesian bounds. — The derivation of Theorem 3, once the step has been taken from $\mathcal L$ to $R$, appears to be the same as a standard PAC-Bayesian bound via "sub-Gaussian"-type concentration for bounded random variables. Is there any other difference in terms of the proof? — In the introduction, you refer to PAC-Bayesian priors as data-independent, which may cause some confusion since you use data-dependent priors in your experiments. Perhaps a note should be made that they can be data-dependent in certain circumstances. --- Maurer, A Note on the PAC Bayesian Theorem, 2004 ___ --- Minor comments: Eq (5): Should this be averaged over the posterior? This is typically the case for PAC-Bayes bounds. Line 196: “for all for all” Line 197: bounuded -> bounded in footnote Line 326: “we found that optimizing the yielded a poor prior” incomplete sentence Donkser -> Donsker Overfull margins in appendix

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are adequately discussed. Perhaps it can be made clearer that the proposed approach does not yield particularly significant improvements over the "Learned" baseline.

Discussion

Thanks for the detailed responses. I wish to initiate the discussion. - *Efficiency bound (Theorem 2)*: the answer is a bit confusing. Based on the answer, the second term is useful in hyper-parameter selection but not useful in test-time performance, which sounds inconsistent. Usually, we use a loss function in hyper-parameter selection and the best model is also good w.r.t. the same loss function. Can you clarify the counter-intuitive usage? What is the hyper-parameter selection procedure? What is $K$ (which is not appeared in the paper)? Can I say that you're using $\delta'$ in Algorithm 1, instead of $\delta$? - *Vovk Prop 2b*: To my understanding (based on the empirical coverage violation), the author's implementation of *Vovk Prop 2b* has some issues. I'd recommend to draw the whisker plot such that the open interval from the bottom tip of the whisker plot contains $100\delta$ % of samples --- this is the meaning of $\delta$. If the bottom of the whisker plot is still below of the desired coverage rate, then it's the sign of implementation bugs. I think comparison to this tighter baseline should be provided to justify the efficacy of the proposed approach. - *Benefit of PAC-Bayes:*: I'm not quite convinced the provided intuitive explantation. For example, consider the claim of "the score function over-fits to the portion of calibration data – then, when recalibrating the model". For the low-data regime, I agree that the score function overfits, but during the recalibration, the low-sample size is still accounted (i.e., Vovk Prop 2a/2b are a function of the sample size). I think we need to see empirical benefits of PAC-Bayes compared to the **fixed** "Learned (Vovk 2b)" first for further discussion. - "Variance-normalized score function": I guess my concern was not addressed. In other words, my point is that "Learned ICP + Recal" essentially wastes calibration samples and that's why its efficiency is poor (i.e., a weaker baseline). A better way is considering the variance-normalized score function and recalibration with a **full** calibration set (i.e., a stronger baseline). This should be the starting point. Given this stronger baseline, I would be excited if the PAC-Bayes results outperform the stronger baseline. In short, I found the baseline used in this paper is weak in two senses: (1) a weak scoring function (i.e., the paper does not use the variance-normalized score function) and (2) a weak ICP PAC bound (i.e., the paper does not use Vovk Proposition 2b). This does not convince myself whether the PAC-Bayes can serve as an exciting new bound. So, I'll maintain my score at this point, but I hope to see a better PAC-Bayes bound!