We thank the reviewer for their feedback. Here we address the weaknesses and questions:

W1. We agree that without specifying the setup the numbers can be confusing, therefore we have rewritten the corresponding part denoting that the drop is reported on CIFAR-10 dataset. However, the higher efficiency with lower sample rate is consistent for all datasets.

W2 and W3. In light of the reviewer’s comment we added Section E in the appendix that provides a high level introduction to randomized-smoothing based guarantees, and the effect of confidence intervals. Additionally, we supported the arguments with synthetic experiments which highlights the effect of sample size on each confidence interval. In short the answer is as following:

As discussed in Section 5, robust CP in combination with probabilistic certificates requires us to compute either the true mean for RSCP, the true CDF for CAS, or the true Bernoulli parameter for BinCP. Since these values are unknown and computing them exactly is intractable we estimate them using Monte-Carlo (MC) sampling. For correctness of the certificate, we need to define confidence intervals that includes the true values with $1 - \eta$ probability (collectively) and account for this probability in calibration. The width of these confidence intervals (CIs) decreases with the number of MC samples — if a confidence interval is tighter, with fewer samples, we can attain the same (or smaller) width.

Let $X \sim \mathcal{N}(0, 1)$ and $Y = f(X)$ for any arbitrary model f and $Z=Y>\tau$ for some constant $\tau$. To understand why binarization helps, think of $Y$ as the conformal score and $Z$ as the binarized score. Here $Z$ is a binary random variable with some unknown probability of success $p$. To estimate $p$ we can apply the exact Clopper Pearson CI. However, to estimate the mean of $Y$ we need to use the Hoeffding or Bernstein CI which provide wider (conservative) CIs. Since wider intervals increase the chance of a label to be in the prediction set, they directly effect the average set size.

W4. In Section E we discuss the effect of sampling rate and the tightness of the confidence intervals on the average set size. A wider interval means a larger shift of the conformal quantile toward lower values. Similarly, at the test time confidence intervals shift the test score to higher values to ensure the validity of the certificate. Both of these shifts are increasing the chance of any label to be added to the prediction set, which means increase in the average set size. Additionally, the average of binary scores is often higher than the average of soft scores. To see this let $s_i$ be the soft score. Since $b_i = s_i > \tau$ is bigger than $s_i$ (for a high enough $s_i$ or low enough $\tau$), the average $1/N \sum_i b_i$ is also bigger than $1/N \sum_i s_i.$ Indeed, on our real-world data (CIFAR-10) the binarized average is bigger than the soft average in 89.8% cases (of true class for $\tau=0.3$). Bigger average implies better worst-case probability which implies smaller sets.

We thank the reviewer for reading our paper and the comments which helps to increase the quality of our work. Here we address the concerns.

Conditional coverage. This is a very interesting point. Thank you. We can study clean conditional coverage, or adversarial conditional coverage. For all existing robust CP method, by increasing the radius r, we increase the clean marginal coverage (since the sets are conservative) which in turn increases clean conditional coverage. To better understand the effect of BinCP on the clean conditional coverage, we did an empirical study to answer several different questions. We included the empirical results in Section D (appendix, Fig. 10).

To estimate clean conditional coverage we follow the procedure in Romano et al. 2020 that computes the worst-slice coverage gap. How to estimate conditional coverage under adversarial attacks is an open problem that has not been studied so far.

First we ask how smoothing and binarization affects conditional coverage. In Fig. 10, we see that smoothing alone (without any robustness, i.e. $r=0$) decreases the coverage gap (compare TPS with STPS). Adding binarization on top, does not change the coverage gap. Next, we ask what is the effect of robustness (increasing the radius r)? As expected, with $r>0$, the marginal coverage and the worst-slice conditional coverage increase.

Alternative attacker goals. Other objectives, including changing the set size and decreasing conditional coverage are both important and interesting. We leave this for future work.

Class-conditional coverage. We add empirical results on clean class-conditional coverage in Section D (appendix, Fig. 11). As in the previous question, we again consider the effect of smoothing and binarization. We see that for some classes there is better class-conditional coverage before smoothing (TPS), while for some classes it is better after smoothing (STPS). On the other hand, binarization (BinCP) always improves over STPS, i.e. it is closer to the nominal level compared the non-robust but smooth model (STPS).

Information loss. Since binarization is not a 1-1 operation, strictly speaking there is information loss due to the data processing inequality. However, it is not clear whether the classical notion of (mutual) information is relevant in this case. Think of NNs that process raw data to learn some representations. Under the classical view, the representation always have less information, however, often they are more useful, e.g. fitting a linear classifier on the learned representation is better than fitting a linear classifier in the input space. This idea has been studied at depth in Yilun et al 2020, and Pimentel et al 2021 under the names of usable (predictive) information and Bayesian information.

Similarly, in our case we should consider what information is useful for CP, e.g. information about the ranking of different data points. We leave this interesting question for future work and thank the reviewer for pointing it out.

Comparison with Yan et al, 2024 (RSCP+). Jeary et al, 2024 has shown (in Table 1 in their paper) a strong improvement compared to RSCP+. We show a strong improvement to Jeary et al, 2024 in Section D. Fig. 9. Therefore, by transitivity, we expect BinCP to perform better than RSCP+. We are trying to run their method on the same setup and we will report the result in another comment.

Combining calibration-time and test-time robustness. These two methods are two alternative variants that can not be combined. Specifically in Lemma 2 we show that calibration-time and test-time robustness are exactly equal after binarization. Similarly Zargarbashi et al. 2024 (CAS) show that the calibration and test time robustness are equivalent approaches (Fig 4 center in their original paper). Therefore a hybrid approach is equivalent to applying robustness guarantee on CP twice. Another intuition behind avoiding such combination is that BinCP only uses Clopper Pearson confidence intervals however Yan et al, 2024 need to add one additional Hoeffding bound which significantly effects the efficiency of the final sets. We have discussed the effect of different confidence intervals in section E.

References:

Yaniv Romano, Matteo Sesia, and Emmanuel J. Cand`es. Classification with valid and adaptive coverage. arXiv: Methodology, 2020.

Linus Jeary, Tom Kuipers, Mehran Hosseini, and Nicola Paoletti. Verifiably robust conformal pre- diction, 2024.

Xu, Yilun, et al. "A theory of usable information under computational constraints." arXiv preprint arXiv:2002.10689(2020).

Pimentel, Tiago, and Ryan Cotterell. "A Bayesian framework for information-theoretic probing." arXiv preprint arXiv:2109.03853 (2021).

We thank the reviewer for reading our paper and the detailed discussion of the problems. We are happy that the reviewer liked our paper.

Readability. In almost all mentioned cases we have updated the paper, however we wanted to highlight the following comments.

Lines 129-131. Yes the reviewer is right. For the upper bound (test-time robustness) the ball is $\mathcal{B}^{-1}$. We corrected that. Thank you for mentioning. For the lower-bound (calibration-time robustness) the $\mathcal{B}$ ball is correct.

Lines 246-250. The solution of Eq. 5 (the worst $\tilde{\boldsymbol{x}}$ and the worst $h$) is always at the border of the perturbation ball; e.g. for Gaussian smoothing $\\|\boldsymbol{x} - \tilde{\boldsymbol{x}}\\|_2 = r$. Additionally, the problem is rotation and translation invariant, meaning that we can move and rotate the coordinates to where we have $\boldsymbol{x} = [0, \dots, 0]$ and $\tilde{\boldsymbol{x}} = [r, 0, \dots, 0]$. Therefore, the solution to Eq. 5, is not dependent to the point, and by design of the problem it is also not dependent to the definition of the function $f$. Therefore, we can write the lower bound just as a function of the ball, and the scalar $p$. In light of the comment we changed some parts of the text. We also refer to Section B where we discuss canonical points. This is discussed in detail both in [1] and [2].

Lines 173-181. We provided this paragraph as another sketch of the proof aside the proof of Prop. 1 in the appendix. We agree that the discussion in these lines is confusing. We try to come up with some illustration for the camera ready version.

Line 238, the variable r. This is the maximum possible magnitude of the perturbation, or simply the radius of the ball in the l2-norm threat model. We agree that it is better to define it explicitly. For that we modified line 113.

Line 229, function f. Yes the reviewer is right. We intentionally did not write the subscript y. The definition in the following lines is for any general function f. However, we agree that this can be confusing. We added a description that this applies for all classes in the modified version.

We again thank the reviewer for the time and comments on the paper which helps to make it stronger. In case that there is any missing point or further discussion we would be happy to receive follow-up comments.

[1] Kumar, Aounon, et al. "Certifying confidence via randomized smoothing." Advances in Neural Information Processing Systems 33 (2020): 5165-5177.

[2] Lee, Guang-He, et al. "Tight certificates of adversarial robustness for randomly smoothed classifiers." Advances in Neural Information Processing Systems 32 (2019).

We thank the reviewer for reading our paper and for comments. We are happy that the reviewer liked our paper. Here we address the concerns:

On randomized smoothing. In light of the reviewer’s comment, we added a Section E (in the appendix) on a high level explanation of randomized smoothing-based certificate. The purpose of that section is just to deliver a high level intuition. In the end, for a detailed technical discussion we referred to highlighted works in randomized smoothing. We hope that the description can help to gain an intuition about the prior state of the art Zargarbashi et al. 2024. In case that the description needs to be improved we would be happy to hear from the reviewer again.

Definition of Robust CP. The reviewer is right. Since $\tilde{\boldsymbol{x}} _ {n+1} \in \mathcal{B}({\boldsymbol{x}} _ {n+1})$ is deterministic the probability of this event is always 1. Therefore $\Pr[y _ {n+1} \in \bar{\mathcal{C}}(\tilde{\boldsymbol{x}} _ {n+1}) | \tilde{\boldsymbol{x}} _ {n+1} \in \mathcal{B} ({ \boldsymbol{x} } _ {n+1} ) ]$ equals $\Pr[ y _ {n+1} \in \bar{\mathcal{C}} (\tilde{\boldsymbol{x}} _ {n+1}) , \tilde{\boldsymbol{x}} _ {n+1} \in \mathcal{B}({\boldsymbol{x}} _ {n+1})]$. In prior work there is the following equivalent definition $\Pr[y _ {n+1} \in \bar{\mathcal{C}}(\tilde{\boldsymbol{x}} _ {n+1}) , \forall\tilde{\boldsymbol{x}} _ {n+1} \in \mathcal{B}({\boldsymbol{x}} _ {n+1})]$. This definition best captures the intuition that we want $1 - \alpha$ coverage for any perturbed point. We modified the notation based on the reviewer’s comment in the updated version.

Notations in Prop 1. We agree that the Prop. 1 introduces many notations. However we tried to deliver an intuition about what each defined variable is encoding in the rest of Section 3. We also proposed an alternative sketch of the proof based on vanilla conformal prediction in lines 173 to 181 (“quantile view”).

Questions. As discussed in Section 5, robust CP in combination with probabilistic certificates requires us to compute either the true mean for RSCP, the true CDF for CAS, or the true Bernoulli parameter for BinCP. Here by concentration inequality we specifically refer to confidence intervals (CIs) of the unknown quantitates that we need to estimate. For instance, let $x_i \sim \mathcal{N}(0, 1)$ for $i$ from $0$, to $n$. With $y_i = f(x_i)$, the $y_i$ values have a different continuous distribution. However, $z_i = \mathbb{I}[f(x_i) \ge \tau]$ is a Bernoulli distribution with unknown parameter $p$. Although we don’t know the distribution of the $y_i$’s, we can bound their mean with Hoeffding or Bernstein inequalities. The resulting confidence interval is conservative (wider). For the value $p$, we can estimate an exact confidence interval for $p$ with Clopper Pearson resulting in the smallest possible confidence interval. In Section E, we have added two experiments that compare setups using different inequalities and study the effect of binarization as well. Our added experiments show that binarization and estimating the Bernoulli parameter helps, specially with lower sample rates.

In case there is any further questions or points missed from the response we would be thankful if the reviewer points them out.