Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness

Thanks a lot for your review. We appreciate the comments and questions that will help improve the clarity of the paper. We would like to emphasize that the resulting (theoretically grounded) methods are reasonably simple ($\sim10$ lines of code) and (a heuristic) SotA uses $50\\%$ more samples and thus the improvement is significant. Furthermore, we provide lower bounds suggesting that it is impossible to significantly improve the performance estimation tasks. We are happy to provide further clarifications if needed and we kindly ask you to consider increasing the score if you are satisfied with the responses

Weaknesses

1. Grammatical errors

Sorry for this. We are aware of some of them and will try to eliminate them.

2. Why are 2 methods included when they perform similarly?

We decided to include both methods for two main reasons apart from the completeness: (1) Betting works better for easy problems while UB is better for the harder ones. (2) We do not only want to propose a method for randomized smoothing. We want the reader to understand the subtleties of the task so they can potentially use this framework in a different context. In certain settings it might be easier to adopt the UB-CS and elsewhere the betting one.

3. Paper flow is difficult to follow

We tried to make the writing as clear as possible and we suspect that some difficulty is inherent due to the technical complexity of the presented topics. We would like to increase the clarity of the paper, could you please share in what parts were difficult to follow?

4.a Approaches include a great deal of complexity

The derivations of the methods are sometimes involved, but the methods themselves are then rather straightforward to implement. On line 243 (top of page 7) we show both proposed algorithms and they can be implemented in 12 simple lines of pseudocode (Python code would be in almost a 1-to-1 correspondence, invoking library function bisect). Union bound CS is just as complex code as the baseline (Horvath, 2022).

4.b ...for relatively minimal improvement

We want to stress that we consider the improvements of our methods to be significant. The SotA method (1) require roughly $50\\%$ more samples than our methods, (2) cannot be used in the very large sample regime and (3) is only heuristic

On the contrary, our method is optimal in a certain sense and is competitive with ideal methods which strictly outperform the best possible methods for this task. Thus, we not only provide an empirically strong method outperforming SotA by $50\\%$, but also demonstrate that significant further improvements on this task are impossible.

Questions

1. Why is the blue line in Fig 1 jagged?

This is a property of the Copper-Pearson intervals - that we wanted to demonstrate - resulting in them being conservative in general. We discuss it in the paragraph starting at line 138. In Example A.2 (and figure 3) we work out a simple example for B(2,p) using elementary math demonstrating why this behavior occurs. Briefly, in setting of Fig 1a, $p_1=0.912$ and $p_2=0.933$ will not be contained in the upper confidence interval only when observing $100$ heads from $100$ tosses. This happens for $p_1$ with probability $\alpha_1 = 10^{-4}$ and for $p_2$ with probability $\alpha_2 = 10^{-3}$ which are then points on the jagged blue line.

2. Why do we assume that there are some constants $c,C$ such that $0 <c <p <C < 1$? (answer copied for Reviewer NzaR)

This is a purely technical assumption for the clarity of exposition. This way we can hide the dependency of the width of the confidence interval on $p$ (so the width scales as $n^{-\frac12}$ and thus simplify the discussion on the width when $np \asymp 1$ where it exhibits complicated behavior (anything between $n^{-\frac12}$ and $n^{-1}$) covered in the referred book. We move the discussion in appendix and replace the paragraph in the main text by the following:

For the simplicity of exposition, let the width of a confidence interval at level $1-\alpha$ with $n$ samples be $\asymp \sqrt{\log(1/\alpha)/n}$. This way, we hide the dependency on $p$ into $\asymp$. In the full generality, the width of the confidence intervals exhibits many decay regimes between the rates $\sqrt{p(1-p)\log (1/\alpha)/n}$ (when $np \gtrsim 1$) and $\log(1/\alpha)/n$ (when $np \asymp 1$). Our algorithms capture the correct scaling of the confidence intervals. Further discussion is provided in Appendix.

3. Understanding Fig 2

Our bottom-left y axis label might have not been the best choice, we will update both captions on the left by words. In the notation of Algorithm 1,2; in the top-left we plot U_t - L_t, while on bottom-left we plot both U_t and L_t (i.e., top = width of CS, bottom = CS itself). We find the setting to be described exhaustively in the caption, but we needed to keep it short due to space constraints. We will put the following in the caption of the left part: "In the notation of Algorithms 1,2, the sequence of $U-L$ is in the top figure, while both sequences $U$ and $L$ are in the bottom figure." See the enclosed pdf for the new figure.

4. Why are the gains from randomized CI not diminishing with increasing $n$?

The randomized and deterministic CIs are only equal when the realization of a uniform r.v. on the interval [0,1] is 1 (so almost surely the randomized ones are larger). The difference in widths gets smaller as $n$ grows; however in Fig 1b. we show the certified radii with Gaussian smoothing and so we plot $\Phi^{-1}(\underline p)$ ($\Phi$ is Gaussian CDF). It holds that $\lim_{p \to 1} \Phi^{-1}( p) = \infty$, so even when the absolute difference between the deterministic and randomized CI lower-bound of $p$ decreases, the difference between the certified radii roughly stays the same because the growth of $\Phi^{-1}$ is increasing quickly around $1$. This holds only when $\underline p \sim 1$ which is the relevant part of Fig 1b.

Thanks a lot for your thorough review! We appreciate the insightful comments that will help with the paper. If we satisfactorily answer your questions and reservations, we kindly ask you to consider increasing your score.

Questions

• Does it apply to more general formulations of smoothing?

Yes, our methodology can be directly applied to all[1] randomized smoothing works we are aware of as they have the same estimation subroutine. Some examples of such non-additive smoothing are Wasserstein smoothing[2] and Image transformation smoothing[3] and they both use the standard estimation procedure in randomized smoothing due to (Cohen, 2019). We state this explicitly in the paper

[1]: modulo the deterministic ones, where there is no estimation. Additionally, rarely a soft base classifiers are considered instead of hard ones. Here one would need to use e.g., empirical Bernstein bound instead of Clopper-Pearson; alternatively the betting wealth needs to be computed in a different way.
[2]: Levine et al. Wasserstein Smoothing: Certified Robustness against Wasserstein Adversarial Attacks
[3]: Fischer et al. Certified Defense to Image Transformations via Randomized Smoothing

• Applicability to more general tasks; e.g., estimate the maximum certified radius within some tolerance

Yes, the methods can be directly applied. We run the confidence sequences until a stopping condition is met (in the paper, it was that certain value of $p$ is outside of the confidence sequence). In the proposed task the stopping criterion might be that $r(hi) < r(lo) + \varepsilon$, where the current confidence interval on the probability is $[lo, hi]$ and $r(p)$ is the radius computed from probability $p$. In the example, we know (at certain confidence) that $r(lo)$ is underestimating the true certified radius and $r(hi)$ is overestimating it; and so when the stopping criterion is met, we return conservative estimate $r(lo)$, but we know that it is at-most $\varepsilon$ smaller than the true radius. We will include this task in the paper. Please see the enclosed pdf for preliminary results.

Clarity

Thanks for the pointers, we will fix the problems.

• Start of setction 2.2

We move the content of the first paragraph after the definition 2.5 and the following remark.

• Section 3, definition 3.1

We agree that the section is brief, we will expand it using the extra page. In the paper, we try to strike a balance between the generality (so the results can be readily transfered) and the clarity of the connection to randomized smoothing. We think that the task from Definition 3.1 is natural and we would like to keep it in this form. We agree that the definition might seem to come out of nowhere and we will provide more motivation for it.

• Paragraph after line 189 (answer copied for Reviewer xWqy)

This is a purely technical assumption for the clarity of exposition. This way we can hide the dependency of the width of the confidence interval on $p$ (so the width scales as $n^{-\frac12}$ and thus simplify the discussion on the width when $np \asymp 1$ where it exhibits complicated behavior (anything between $n^{-\frac12}$ and $n^{-1}$) covered in the referred book. We move the discussion in appendix and replace the paragraph in the main text by the following:

For the simplicity of exposition, let the width of a confidence interval at level $1-\alpha$ with $n$ samples be $\asymp \sqrt{\log(1/\alpha)/n}$. This way, we hide the dependency on $p$ into $\asymp$. In the full generality, the width of the confidence intervals exhibits many decay regimes between the rates $\sqrt{p(1-p)\log (1/\alpha)/n}$ (when $np \gtrsim 1$) and $\log(1/\alpha)/n$ (when $np \asymp 1$). Our algorithms capture the correct scaling of the confidence intervals. Further discussion is provided in Appendix.

Minor

Thanks for all the relevant points. We integrate all of them but comment here only one the "open ended" ones.

• In which sense is the randomized interval optimal?

They are the shortest possible in expectation. We state it formally in the paper: For any binomial r.v. $X \sim \mathcal{B}(n, p)$ and any $q$ (where $p,q$ are probabilities and $n$ is number of samples), $\mathbb{P}(q \in CI_{\text{our}}(X)) \leq \mathbb{P}(q \in CI_{\text{other}}(X))$, where $CI_\text{our}$ is our proposed randomized confidence interval and $CI_\text{other}$ is any other confidence interval at the same confidence level as ours, and so our intervals are the shortest one in expectation.

• Is [0, v(x)] the upper confidence interval?

We called it the lower confidence interval since it contains the low values. On the other hand $v(x)$ is the upper bound for the estimated quantity. We are open to rename the interval if it helps the clarity.

• Definition of coverage for randomized intervals

We update the definition so to cover the random intervals. The coverage is the probability of the true parameter appearing in the confidence interval, where the probability is not only over sampling, but also over the randomness of the intervals.

• Problems with Conclusions

Thanks, we agree. We rewrite it in the following way:

In this paper, we investigated the statistical estimation procedures related to randomized smoothing and improved them in the following two ways: (1) We have provided a strictly stronger version of confidence intervals than the Clopper-Pearson confidence interval. (2) We have developed confidence sequences for sequential estimation in the framework of randomized smoothing, which will greatly reduce the number of samples needed for adaptive estimation tasks. Additionally, we provided matching algorithmic upper bounds with problem lower bounds for the relevant statistical estimation task.

Limitations

We will add Imagenet experiments and with multiple models (we already have multiple models for CIFAR and $\ell_1, \ell_2$ tasks.) We will include your proposed task.

Thanks for your review and typos! We will clarify the binomial case. We are ready to answer any questions if any arise!