Incremental Randomized Smoothing Certification

We thank the reviewer for insightful and constructive feedback.

It seems to me that this method is more expensive than computing the certificate directly on the quantized version. To claim that the approach is more efficient, the authors assume that the certificates for are available for all $x$ The authors assume that the test data is already available and that the certificates have already been computed. I don't see how this can be realistic.

I think there is a misunderstanding with the motivation of our setup. Please see common response C1 for the motivation of the setup that we focus on in this work.

IRS is not applicable while certifying individual approximate networks. We focus on the scenarios where we intend to certify multiple similar networks on a fixed test set to compute the certified radii. Computing certified radii for similar networks is a common occurrence when a user is comparing and selecting the best approximation for a network using techniques such as approximation tuning. For certifying the first network we cannot use IRS, however, for all subsequent network certifications, we can use IRS for faster certification.

Why do the authors use the same Gaussian samples (same seed) in Algorithm 3? Is there any benefit?

Yes, using the same seed is crucial for making our algorithm 2x faster. The estimation of $\zeta_{x}$ involves computing $f(x+\epsilon)$ and $f^p(x+\epsilon)$ on Gaussian-corrupted versions of the input $x$. Given that we have already conducted this computation for $f$, we store the results for those samples in the cache. Consequently, we only need to compute $f^p$ on Gaussian-corrupted inputs. To ensure the soundness of this process, we utilize the same Gaussian corruptions for $f^p$ by retaining and reusing the seed. This approach incurs small memory and computational overhead.

Thanks for pointing it out, we will further clarify our reasoning for using the same Gaussian samples in the paper.

We thank the reviewer for insightful and constructive comments.

The practical usefulness of the proposed method is not clear. As randomized smoothing produces certificates at inference time, in order to calculate the certificate around a given point in this approach, the edge device would need access to both the original as well as the modified neural network models, which is not feasible.

Please see common response C1 for motivation. IRS is not applicable for improving the inference time efficiency of RS. We focus on the common occurrences where the goal is to compute certified radius for multiple similar networks offline for comparison. For instance, when the user is selecting the best approximation for a network using the approximation tuning techniques as described in C1. We are happy to provide additional clarification to ensure a better understanding of our motivation.

We thank the reviewer for insightful and constructive feedback.

Demanding prerequisite: I am not sure how likely the IRS algorithm is applicable in practice. It seems like the IRS will require many prerequisites. For example, IRS needs to know the certification cache from the original neural network, which makes the requirement more demanding.

Please see common response C1 for motivation. The prerequisite is common in the scenario where the objective is to compute a certified radius for multiple similar networks offline. For example, when the user aims to select the best approximation for a network by utilizing techniques such as approximation tuning.

Novelty issue with the theory: for the theory part, most of the theorems are built upon theorem 1 in [Cohen et al 2019] and are direct applications of that theorem, hence raising a novelty issue.

Theorems 2, 3, and 4 combined are crucial to prove the soundness of our Algorithm. Theorem 1 by [Cohen et al 2019] considers standard RS for a single network. Our theorems show how to use the estimated value of $\zeta_x$ to transfer the certification guarantees across networks. We believe that this result is non-trivial and a novel theoretical contribution.

We thank the reviewer for insightful and constructive comments.

Insight 1 in Section 3.1 is not very convincing in the sense of a single setting of $n=1k$ and, where it usually costs $10k-100k$ samples for Monte Carlo sampling in estimation. More examples can be given to show is $\zeta_{x}$ is small.

In Appendix A4, we show $\zeta_{x}$ for all networks and $\sigma$ values. We will point to this section in our insight 1. By considering $n=1000$ (smaller than $n=10k,100k$) we show that $\zeta_{x}$ is small with high confidence. The choice of smaller value $n$ for these experiments gives a strong argument that the IRS algorithm that uses the $\zeta_{x}$ estimate is likely to work well as it needs fewer samples to show that $\zeta_{x}$ is small. If the reviewer still thinks that experiments with larger values of $n$ would help strengthen this argument, we will add it to the paper.

For insight 2 and Figure 2, although the needed samples are much less compared to 0.5, it still needs 41.5k and there is no significant reduction compared to naive Monte Carlo randomized smoothing (10k-100k). A better way is to use an example of the current estimation of $p_A$ and to show the needed samples are much less when estimating $\zeta_{x}$ compared to $p_A$.

Firstly, we appreciate your suggestion and we will make the change accordingly. We agree with the reviewer that the evidence on the distribution of $p_A$ strengthens the insight to motivate that the IRS algorithm will improve the sample efficiency. In appendix section A5, we show our observations on the distribution $p_A$ for different $\sigma$s. These observations show that $p_A$ is not close to $1$, especially when the $\sigma$ is larger. We will be happy to put these observations as one of our insights to make our presentation stronger.

The choice of threshold $\gamma$ seems to be critical from the experiment results and the authors use grid search to optimize it. If I understand it correctly, whether to estimate $\zeta_{x}$ actually depends on whether is closer $\zeta_{x}$ to 0 than $p_A$ is to 1. So ideally, there can be some theoretical analysis for choosing $\gamma$ in terms of $\zeta_{x}$ and $p_A$.

Yes, your understanding is correct, in the IRS algorithm the decision to estimate $\zeta_{x}$ depends on whether $\zeta_{x}$ is closer to 0 than $p_A$ is to 1.

While this analysis can be theoretically interesting, practically, we do not anticipate the analysis to help with the efficiency of the search compared to grid search for the following reasons. We found out that the final ACR is not too sensitive around the best choice of $\gamma$, and a simple grid search works quite well for this search. Since $\zeta_{x}$ is a function of each input $x$, for such an analysis to work it should rely on the distribution of $\zeta_{x}$ over different $x$s - computing that can be potentially expensive.

I think there is a missing ablation study of directly using naive Monte Carlo to estimate instead of reusing seeds in terms of both certified radius and certification time.

In theory, using naive Monte Carlo without seed reuse will not change the certified radius and it will be 2x slower than reusing seeds. We are happy to emphasize this in the paper. If the reviewer thinks that additional experiments will benefit the paper, we will add it in the revised version.