One Sample is Enough to Make Conformal Prediction Robust

We thank the reviewer for reading our paper and we are happy that the reviewer liked it.

1. Thank you for pointing out the typos, surely we would modify it in the camera ready version.
2. The reviewer is right. We should definitely add a section on a summary of how each prior method is functioning. We would definitely add that to the camera ready. We also agree that the paper is introducing many term and notations which makes it uneasy to read.
3. Of course; we will add a section in the appendix with a brief discussion on how robustness certificates, and how CP work. Hopefully that would make the reading of the paper easier.
4. Sure. We have discussed its adaptability to regression while showing something like that is definitely helpful in illustrating it. By the time of publication we did not find a good example of smoothing based regression on a large data. But for the camera ready we would try to add such experiment at least with a synthetic dataset. We also like to draw your attention to the image segmentation certificate in Figure 7 which uses single-sample robust conformal risk control.
5. Indeed any smoothing-based certificate is directly applicable to both RCP1, and BinCP for free. If the reviewer refers to the more practical smoothing noises, we can use the recipe from [22] in combination prop 2. If the question is whether RCP1 adapts with other types of robustness guarantees including verifiers, it is not adaptable. But randomized smoothing shows to be very strong in terms of certifiable radii, and in our case efficiency of the set size. And since this method is model (and score) agnostic in can easily adapt to any machine learning model.

We thank the reviewer for reading our paper and for the comments. Here we discuss the raised weaknesses:

1. The are two terms that should be distinguished: (1) the guarantee holds marginal over augmented noise. (2) The guarantee (marginal over noise) holds for the worst case perturbation. So here the noise is what the defender adds to any (including perturbed) input, the perturbation is what the adversary introduces to the clean data. Our guarantee holds marginal to the noise we introduce not the perturbations the adversary applies. This is a very important distinction of a certified worst-case robustness (ours) and an average-case robustness like [12] (in our references). We discussed this further in line 377. Formally for $\tilde{x} = x + \delta$ we provide a guaranteed prediction set using $\tilde{x} + \epsilon = x + \delta + \epsilon$ which is marginal over $\epsilon$ for the worst case $\delta$. This means that our comparison with BinCP[24] is fair as we both target the same worst-case guarantee. Moreover, being marginal over random noise is not uncommon in the literature. For example the highly popular APS score function introduces uniform random noise, and there the 1-alpha guarantee is also only marginal over the introduced noise. See Chapter 9.1 in [add reference].

2. We draw the reviewer’s attention to Fig 2-right and Fig 5-right where we discuss noises other than isotropic Gaussian, specifically Laplace and Uniform noise. Indeed Section 3.1 modifies the result from Yang et al [22] to adapt RCP1 with smoothing of all shapes and sizes. RCP1 itself is independent to the noise type — any smoothing scheme, and threat model can be adapted to RCP1 for free.

3. In terms of result: Existing worst-case CP guarantees are categorized into two main regimes: (1) smoothing based approaches which are robust for large radii while requiring may MC samples (computationally expensive), and (2) verification and Lipschitz based approaches which are efficient but only support very small radii. Our work is computationally efficient and works for large radii which is the first method which has both benefits.

   In terms of theoretical novelty: In order not to use MC sampling, we need to rely on the non-exact (probabilistic) setup which is unique to the case of conformal prediction — we can not apply the same method to have a certified top-class prediction. Similarly other methods did not need to prove that the certificate is convex. Notably, the proof that allows us to work with a single sample is completely orthogonal to the other smoothing based CP approaches, as they redefine the score function and show the score changes are bounded; that is basically why the need to estimate the score by MC sampling. Here we prove it by leveraging and lower bounding the coverage probability which is not needed to be estimated.

We thank the reviewer for the constructive feedback. First we respond to the technical flaw, then we address other raised concerns and questions.

Potential Theoretical Error. Thanks for pointing that out. Turns out the reviewer is right about the flaw in line 119, however since the conclusion is about coverage probability marginal over noise and data, the rest of the proof holds independently of this statement.

First - Example of why the reviewer is right: Assume a one dimensional data x randomly in range of [0, 1], and the noise to be also uniform random from the same range. And the score to be S = X + E. Then one set of fixed $E_i$’s is $E_1 = 0, E_2 = 0.1, \dots, E_{10} = 1$. From the definition of the score function the $1 - \alpha$ quantile is the addition of the two quantiles over the X’s and E’s. While the quantile over X’s holds the same, the one over E’s introduces a bias since the noises are ordered, leaving the overall quantile inequality invalid.

Importantly the proof remains valid even without this argument. This is intuitive assuming that the noises augmentation is a part of the model inference. Moreover, for other randomized score functions like APS the guarantee similarly holds over the marginalization of the noise. We refer to Chapter 9.1 of [2] showing the same argument applies for any randomised score function — a random noise augmentation of the input is essentially a randomised score function. In short, the 1 - alpha guarantee holds because noise-augmentation with i.i.d. noise is symmetric. The rest of the proof does not rely on the second half of the line 119. Thank you for pointing that out. In the next version, we’ll remove this part and the other occurrences of the same argument which is line 129 and the footnote in page 4.

Heavy and Hard-to-Understand Notations. In light of the reviewer’s comment we found some typos that made it harder to read:

• The first half of line 119: The equation is $\Pr[\hat{S}_{n+1} \ge \hat{q}] \ge 1 - \alpha$ for $\hat{q} = ...$.
• The first half of line 83: The equation is $\mathcal{C} _{\mathcal{B}}(\boldsymbol{x} _{n+1}) = \{y:s(\tilde{\boldsymbol{x}} _{n+1}, y) \ge \bar{q}\}$.

Also regarding the notations $c^\uparrow$, and $c^\downarrow$, we adapted them from [24] and defined in line 81 as certified upperbounds and lowerbounds of the score, although we agree that it is necessary to bring the rigorous notation which says: $c^\downarrow[f, x, \mathcal{B}]$ is the certified lowerbound for function $f$ in $\mathcal{B}(x)$. We’ll surely add modifications in the camera-ready version. If the reviewer has a concrete suggestion on how to improve the notation we would gladly consider it. We also try to reduce the quantity of the variables in a way that doesn’t affect the mathematical rigor.

Unclear Writing and Algorithm. We agree that an algorithm would enhance the understandability of the paper. We ask the reviewers attention to the lines 51 to 54 where we discuss the high level implementation. In general the algorithm is exactly same as conventional CP, only with applying noise before computing the score functions and finding the upper bound $1 - \alpha’$. We will add the following peudocode to the camera ready paper.

Algorithm 1: RCP1 – Single Sample Robust Conformal Prediction

• Input:

The calibration set $\mathcal{D} _{\mathrm{cal}} = \{(x _i, y _i)\} _{i=1}^ n$

The score function $s: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$

The test point $x_{n+1}$,

target coverage level $1 - \alpha$

perturbation ball $\mathcal{B}_r$

smoothing scheme $\xi$

• Output:
  $\mathcal{C} _r(x _{n+1}) \subseteq \mathcal{Y}$

1. Step 1. Draw noise from the smoothing scheme, compute conformity scores for augmented calibration data:

   for i = 1 to n do
       \epsilon_i ∼ \xi  
       s_i \gets s(x_i + \epsilon_i, y_i)
   end for
   

2. Step 2.

   • Compute corrected level:
     $1 - \alpha' = c^{\uparrow}[1 - \alpha, \mathcal{B}_r]$
   • Compute the $(1 - \alpha')$ quantile with correction:
     $q \leftarrow Q(\alpha'; \{s_1, \dots, s_n\})$

3. Step 3. Construct the prediction set for the test input:
   $\mathcal{C} _r(x _{n+1}) = \{y \in \mathcal{Y} : s(x _{n+1} + \epsilon _{n+1}, y) \ge q\}$

4. Return $\mathcal{C} _r(x _{n+1})$

Questions:

1. It means if you do not apply any robustness guarantee, and use vanilla CP, only if instead of inference over $x$, we forward the model with $x + \epsilon$, the resulting CP shows some robustness. This robustness means that the amount by which the empirical coverage deviates from the guarantee is significantly less than the case where we only apply the forward on $x$. As you see in Figure 1 - left, the dashed lines (which are CP without changing the quantile level) do not drastically drop as the red line drops.
2. The proposed prediction set for the potentially perturbed $\tilde{x}$ is $\mathcal{C} _r(x _{n+1}) = \{y \in \mathcal{Y} : s(x _{n+1} + \epsilon _{n+1}, y) \ge q\}$, where $q \leftarrow Q(\alpha'; \{s_1, \dots, s_n\})$ with $1 - \alpha' = c^{\uparrow}[1 - \alpha, \mathcal{B}_r]$. And here the guarantee is the same $1 - \alpha$ for any worst-case adversarial perturbation up to radius $r$.
3. The lower-bound in Prop 1 is not greater than $1 - \alpha$. It is lower, but using the randomized smoothing (and in our case noise augmentation) helps us for this lower-bound not to get too deviated. For further clarification: we show that vanilla CP over noise augmented inference leads to a coverage guarantee $c^\downarrow[1-\alpha, \mathcal{B}]$, which means that by calibrating to $c^\uparrow[1-\alpha, \mathcal{B}]$ allows us to achieve $1 - \alpha$ coverage. This is via lemma 3 in [24].
4. It can be of any form, including the definition from [24] or our definition. The argument in line 108 is a generalised version of this argument: “if the clean point $x$ is covered by vanilla CP not accounting for perturbation radius $r$, then robust CP also covers the perturbed point $\tilde{x}$. Notably there, the argument is 0/1 here we discuss that the argument should say that the robust prediction set $C_r$ has a higher probability to cover the perturbed point compared to the vanilla set $C_0$ for the clean point.

Once again we thank the reviewer for pointing out the mistake, we surely remove it from the proof, but nevertheless the proof holds even without that statement.

We are very thankful that you read the paper, and very grateful that you liked it.

Parallel comparison with BinCP. If by parallel comparison you refer to running both up to the same wall-clock time, indeed BinCP returns full sets if limited to the time RCP1 returns its result. Besides the sampling, BinCP and RCP1 both apply a single binary certificate; which means that although the binary certificate is negligible in computational time, they both have same cost in terms of calling the certificate. The only difference is that BinCP needs more than one forward pass and with only one forward pass (equal or parallel setup) it returns trivial sets of $\mathcal{C}(x) = \mathcal{Y}$.

This also answers the first question. Additionally the bottleneck in BinCP is independent to the choice of the smoothing scheme. It is only due to several runs of the model on the same data. As shown empirically.

Second question. We think the reviewer refers to when sample rate is low in BinCP — otherwise what we show is that RCP1 only works with a single sample. The set size for BinCP increases up to returning all possible classes. Here we provide an intuitive reason behind it:

When the score is defined as some statistical term over the model and smooth input, since the certificate works with exact probabilities, we should estimate that statistics. For example consider the case where the score function is defined as the mean of the score distribution (over smooth input). There is a ground truth value, but finding that value is intractable. Instead we compute an interval which covers that true score with a very high probability (e.g. 0.999) — known as confidence interval. The size of this confidence interval decreases by introducing more MC samples. For correctness of robust CP we should (conservatively) take the lower bound of this interval and that is what contributes to increasing the size of the prediction set.

The main contribution of this work is to find another variable to apply the robustness certificate over — a variable that is not needed to be estimated and that is the coverage probability. What we show is that the expected coverage probability (which is already given despite the number of MC samples) is lower bounded. Prior works showed similar for the score function (or quantile of scores which is a function of scores) and scores should be estimated.

We thank the reviewer for reading our paper; we understand that the writing was difficult to follow; and surely we’ll update the camera ready to enhance the readability. Here we discuss the questions and unclear parts. If the results remains yet unclear, we are more than happy to discuss further:

RCP1 vs other smoothing-based robust CP approaches. Consider the robustness certificate (Eq 4) as a black-box that receives a probability (or generally any bounded value) and returns a lower (and upper) bound for that probability. Now among the previous methods (RSCP+, CAS, BinCP) all applied this bound on the score function. RSCP+ defines the new score as the mean of the smooth score distribution, CAS does the same only through the CDF of that distribution finds a better bound (a better black-box), and BinCP applies the lower bound on the quantile of the scores. This work derives a lower bound on the coverage probability itself. Then it reverse engineers a higher $1 - \alpha’$ such that its lower bound is above $1 - \alpha$.

What is different? All three prior methods are bounding the score function. Since the robustness certificate works with exact probabilities, we need to estimate that value from Monte Carlo examples (estimate the mean of some smooth scores from m samples), and since we are estimating with finite samples we should account for final sample correction. This correction creates a trade-off: more samples per point results in tighter confidence interval (smaller sets), so we should either get large sets, or run many forward passes.

Oppositely, since we apply the lower bound on a given probability $1 - \alpha$, we do not need to estimate it. Therefore, with only one (noise augmented) inference, we can compute the robust prediction sets.

What are the challenges? The proof is generally different, and since this $1 - \alpha$ is the expectation of a Beta distribution itself, we should prove that the smoothing-based lower bound can move from each run to the total expectation. For that we needed to prove that robustness certificates are convex.

Also from the description, we answered that we do not propose a new robustness certificate. We change the way we are using it in conformal prediction to improve the computational efficiency. Same applies to all three mentioned prior works.

Why we need sampling in prior works? Since in prior works the object which we wanted to bound within the threat model is the mean (quantile, or any other statistics) of a distribution which we don’t know. And computing that statistics exactly is intractable. Therefore, we need to estimate it via samples, and more samples result in a more precise estimation of that value.

Figure 2. The solid line is the theoretical lower bound, derived in Proposition 1, which should be (and is) lower than the empirical line which is the dashed line (both are for single sample). So the empirical coverage should be higher than what we compute as a lower bound. The figure shows that indeed the lower bound holds. Note, that this solid line is computed for a target of 1-alpha = 90% — lower bounding the worst-case coverage if it is calibrated with 90%. For example, for r=0.2 we get worst-case coverage of ~81%. If we want worst-case coverage of 90%, as a defense to the perturbations, we find an initial higher 1-alpha=95% which after the lower bound becomes 90%.

Algorithm. You are right. Although we discuss the general algorithm in the introduction (lines 81-83), still nowhere else we explicitly define the algorithm. In following we bring the pseudocode, and later we will add it to the camera ready version. The algorithm is to do both calibration and defining prediction set same as vanilla CP with two differences: (1) instead of inference over $x$, we should apply inference over one sample from $x + \epsilon$. (2) Instead of $1 - \alpha$ we should aim for coverage guarantee of $c^\uparrow[1- \alpha, \mathcal{b}]$ to attain $1 - \alpha$.

Algorithm 1: RCP1 – Single Sample Robust Conformal Prediction

• Input:

The calibration set $\mathcal{D} _ {\mathrm{cal}} = \{(x_i, y_i)\}_{i=1}^n$

The score function $s: \mathcal{X} \times \mathcal{Y} \to \mathbb{R}$

the test point $x_{n+1}$

target coverage level $1 - \alpha$

perturbation ball $\mathcal{B} _ r$

smoothing scheme $\xi$

• Output:
  $\mathcal{C} _ r(x_{n+1}) \subseteq \mathcal{Y}$

1. Step 1. Draw noise from the smoothing scheme, compute conformity scores for augmented calibration data:

   for i = 1 to n do
       \epsilon_i ∼ \xi  
       s_i \gets s(x_i + \epsilon_i, y_i)
   end for
   

2. Step 2.

   • Compute corrected level:
     $1 - \alpha' = c^{\uparrow}[1 - \alpha, \mathcal{B}_r]$
   • Compute the $(1 - \alpha')$ quantile with correction:
     $q \leftarrow Q(\alpha'; \{s_1, \dots, s_n\})$

3. Step 3. Construct the prediction set for the test input:

$\mathcal{C} _r (x _{n+1}) = \{ y \in \mathcal{Y} : s(x _{n+1} + \epsilon _{n+1}, y) \ge q \}$

4. Return $\mathcal{C} _r(x _{n+1})$

Idea behind the proof of Prop 1. We answered this question in the beginning of our response. If the intuition is not yet clear we would be very happy to introduce it again. Thank you for pointing this out. We would definitely add a similar description before the proof of the proposition in the camera ready.

Also we borrowed Zargarbashi and Bojchevski’s definition of $c^\downarrow$ and $c^\uparrow$ without rigorously defining it. $c^\downarrow[f, x, \mathcal{B}]$ is the certified lower bound for function f in the nearby points around the point x which is $c^\downarrow[f, x, \mathcal{B}] = \lambda \Leftrightarrow \forall x’ \in \mathcal{B}(x): \lambda \le f(x’)$.

We are very thankful for the reviewer’s comment on the readability of the paper. We will surely add descriptions and intuitions to make it more clear. If there is any part that is not yet clear we would be more than happy to further introduce it.

We really appreciate the reviewer's reply. We address the questions, and if parts of our response isn't clear, please let us know, and we are more than happy to clarify further.

a. Yes, it is a quantile over the random data point, and its label, augmented with random noise (form the smoothing). In practice the value q is one sample from the distribution of quantile over augmented inputs from Dcal. To know the distribution better, q comes from a distribution made by: (1) sampling a calibration set (2) augmenting inputs x with one random noise from the smoothing scheme. So it is a mixture over the smoothing scheme and the generative data distribution.

b. Sorry again for confusion. $c^\downarrow[f, x, \mathcal{B}]$ itself is the lower bound of function f over any point in B(x). But in our case:

• It encodes the lower bound of the smooth coverage after perturbation.
• We should think of two noises distinctively. One comes from the smoothing scheme, and one is added by the adversary -- we refer to that as perturbation. The smoothing doesn't change the alpha as we calibrate over noise-augmented input, and we also evaluate on noise augmented input (therefore the distribution doesn't change). This lower bound captures the probability of coverage (1 - alpha) when the adversary applies the perturbation.
• The definition of $c^\downarrow$ is actually for any function f (smooth or non-smooth). In smooth functions (where f has some noise augmentation in it) this lower bound is computed easier, and usually the lower bound is higher -- the function changes slowly (in expectation) when smoothing noise is added to it.

c. Same as the previous papers, for smooth functions we can find this lower (and upper) bound independent to the model (function). In fact the bounds that we use for smooth function (a function evaluated on a smooth augmented input) is computed for the worst case function. So intuitively imagine a model with smoothing in the input space; for computing the bounds we set the function aside and answer that "what is the bound for worst (or any) function and the worst point in B(x) if it is equipped with smoothing and that worst function has same expectation at x". This allows us to treat the model as a black box and apply the same robustness results to any model.

d. In this work yes and in other related works no. In fact the bound only works with exact probability. Therefore if you use it on a variable that its exact mean is not known, then you need to estimate it (with many samples), draw a confidence interval around it, and apply the bound on the edge of that interval.

One novelty of our work is that we find a variable that doesn't need to be estimated -- the 1 - alpha expected coverage is known exactly and therefore the bound can apply without any sampling and confidence intervals.

Regarding the point c. please note that the smoothing-based bound could be computed for any arbitrary smoothing function and threat model B(x), we use L2 and isotropic Gaussian as an example, and in Section 3.1 we discuss how to find the bound for any other smoothing/ball following the results from [22].