Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper contains three main contributions. First, this paper shows that using EoT ($m>1$) is not always necessary to break randomized defenses, i.e., it does not necessarily save the number of gradient computations. Second, it shows a theoretical result in a toyish setting that the robustness of randomized models is at odds with their utility (accuracy). This is not an impossibility result but rather, the authors propose some settings where such a trade-off exists. Lastly, the paper supports the second the previously mentioned theoretical results with empirical ones on two types of defenses (BaRT and randomized smoothing).
strengths_and_weaknesses: # Strengths
1. The paper addresses an interesting yet under-explored problem. Rigorous studies are lacking on randomized models/defenses.
2. While the setup for the theoretical part is toyish, the results are comprehensive. I would have missed the more interesting results, in my opinion, in the appendix if I didn't check out Appendix C.2. The paper might benefit from bringing up or summarizing some of these results in the main paper.
3. Experiment setup seems mostly rigorous and up to date with recent works. 
4. The presentation is good. The main messages are all easy to understand, and the results mostly support the claims well.

# Weaknesses
1. The main and only major weakness is that the overall contribution is slightly limited (justified in a. and b. below). Personally, I find the two main observations in this paper interesting. However, the paper seems to miss the final part, i.e., I find the following questions unanswered: What's next? What does this mean to future research? How do we improve defenses? Should we abandon randomized defenses? What are concrete settings that this defense works (with some supporting results)?  
  a. *Theory*: As mentioned in the summary, there is no guarantee that the trade-off between utility, i.e., invariance, and robustness must hold. The results do cover a reasonable set of settings used by the proposed defenses, but none really exclude the possibility of using other forms of randomness or aggregation methods that may not conform to this trade-off or in general achieve a better trade-off.  
  b. *Empirical*: I don't believe that the empirical contribution quite makes up for the limitation in the theoretical part. Additional experiments on more models and defenses might be good. Surely, all defenses are not made equal and so they should not be on the same trade-off curve. Could the authors make a stronger claim about which defense might look more promising? Or maybe a heuristic to properly choose $m$ and $k$ without just trying out a lot of them?

Note that I'm not set in stone about this. The authors and the other reviewers may convince me otherwise.

# Minor Weaknesses
I think of these as suggestions or room for improvement rather than things I penalize this paper for.
1. I believe that Pinot et al. [2021] (https://arxiv.org/abs/2102.10875) might be related to this work, at least remotely. This work is not peer-reviewed as far as I can find so I'm not imposing any penalty. However, I'd recommend citing and discussing their result as well since they also show many solid theoretical results on randomized defense.
2. Maybe the comparison between the benefits of the number of PGD steps ($m$) and the number of EoT samples ($k$) can be put in the perspective of stochastic gradient descent. For instance, from the central limit theorem, we know that variance decreases by $1/k$ and $1/\sqrt{k}$ for standard deviation. We also know that the variance of the gradient estimates affects the convergence rate of SGD (see this [paper](https://cpn-us-w2.wpmucdn.com/sites.gatech.edu/dist/f/330/files/2016/02/NonconvexSA-Revision-9-25-13.pdf)). This might allow one to predict, in theory, the optimal value of $k$ and $m$ given $\sigma$ and $k \times m$. 
3. Presentation of Figure 3 and 4: I don't think the epoch views are necessary. I would also recommend plotting the attack success rate or robust accuracy vs clean accuracy to show the trade-off better. 

# Very Trivial Weaknesses
1. Reference [10] and [11] are duplicates.
2. It's a bit difficult to compare a fixed number of gradient computation ($k \times m$) in Figure 1 and 2. It just takes another little step to multiply the numbers. I don't have a good suggestion for this without significantly changing the figure (e.g., x-axis is just $k \times m$).
questions: 1. What about the robustness-invariance trade-off in the targeted setting? The invariance is needed for accuracy when it represents $F_\theta(x) = y$, i.e., "prediction has to be correct after the random transform." However, the defender needs *no* invariance for the wrong class, correct? We don't care, almost in all cases, that $F_\theta(x) = F(x)$ when they are both wrong. The defense can surely use this to its advantage. I expect that the robustness-invariance trade-off is far less important, if it exists at all, in the targeted setting. 
2. In Figure 4a and 4c, we can see that the red and the green solid lines start to diverge at large $\sigma$. This means that the trade-off somewhat disappears here, i.e.,  you gain more robustness while the accuracy does not go down. Why does this happen on randomized smoothing and not BaRT? Why is this the case? Could it be that the attack is sub-optimal with large $\sigma$? It might be good to show that the attack does indeed converge by no large $m$ and $k$ could possibly increase the attack success rate further.
3. Do all attacks in the paper use AutoPGD? If so, did the authors take into account the observation that EoT is unnecessary could be, at least partially, an effect of the adaptive step size from AutoPGD?
limitations: This is adequately discussed in Appendix F.
review_title: null

final_score: 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.
review_content: summary: "On the Limitations of Stochastic Pre-processing Defenses" discusses strategies for the adequate evaluation of adversarial attacks against systems defended by stochastic components. Previous work generally considers expectation-over-transformations to be necessary to attack these defenses, but the submission shows that merely running standard defenses with larger step budgets can often be sufficient in overcoming these defenses. The submissions supplements this finding with further analysis on the interactions of robustness and invariance with the stochastic nature of these defenses.
strengths_and_weaknesses: I like the clarity of writing and presentation of the findings in this work. The grouping of stochastic defenses into defenses with and without meaningful stochasticity is nicely illustrated and exemplified.

The experimental evaluation underpins these findings for two defenses, barrage-of-transformations and randomized smoothing. Overall I don't have a lot of say here, I liked the evaluations done by the authors and find the results interesting. The overall topic is not groundbreaking, but reinvestigating the properties of stochastic preprocessing is, in my opinion, illuminating for the wider community. 

The only minor weakness I see is that the evaluations center on two classic stochastic defenses. Recently there has been a lot of renewed interest in stochastic defenses, especially based on diffusion processes (For example Nie et al, "Diffusion Models for Adversarial Purification
" at ICML this year). I think the impact of this submission could be improved by also considering one such "newer" attempted adversarial defense, where would this defense fall in the categorization of stochastic defenses proposed in this work?
questions: As described above, how would a stochastic defense based on diffusion processes be categorized? Do the findings of this work for older defenses also hold for these newer stochastic defenses?
limitations: n.a.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work investigates stochastic pre-processing defenses both empirically and theoretically. Specifically, the authors first revisit previous stochastic pre-processing defenses and explain why such defenses are broken. Then, the authors study recent stochastic defenses that exhibit more randomness and show that they also face key limitations.

－－post rebuttal－－
Thank the author for providing detailed rebuttals. My major concerns are addressed. I raise my score and tend to accept this paper.
strengths_and_weaknesses: Strengths:
1. This work focuses on an interesting topic, namely, the effectiveness of stochastic defenses.
2. In general, the paper is well organized.

Weaknesses:
1. My major concern is the novelty of the findings. The finding that applying EOT is only beneficial when the defense is sufficiently randomized is trivial to me. The other finding is that a trade-off between the model’s robustness provided by the defense and its invariance to the applied defense, which is also expected. When the model becomes invariant to the applied randomness, the function modeled by a model is more ‘deterministic’. The randomness is expected to bring less robustness to the model.

2. Some claims made in this paper are inappropriate, to my knowledge, e.g., in Line 46-47. The work [2] shows that EOT can be used to break stochastic defenses. However, the necessity of EOT is not claimed since they mainly aim to show that stochastic defenses can be easily broken with EOT.

3. Besides the success rate, an analysis of created adversarial noises should be presented. What is the difference between the adversarial noises created by PGD(n*m) or PGD(n)+EOT(m)? Similarly, what is the difference between the adversarial noises created on models with different degrees of randomness? The visualization of the noises might reveal more interesting conclusions.

4. It is great that the main experiments are conducted on ImageNet dataset. It will be better if the experiments on a smaller dataset, e.g.CIFAR10, can be provided. It is not clear if the experimental observation still holds when the input space is smaller.

questions: I expected systematic guidance to design attacks and defenses regarding randomness from this paper. It will bring more value to the community if the author can provide one. The one provided in Discussion section is a good starting point.

I also encourage the authors to provide the expected experiments listed in weaknesses.

limitations: This work provides an analysis of the existing techniques, namely, stochastic defense. The new technique is the focus of this paper. The only limitation of this work is its novelty.
review_title: null

Meta-review: metareview: This paper considers the effectiveness of stochastic preprocessing methods at achieving adversarial robustness. It shows empirically that the common Expectation of Transformations attack is not necessary to break many such defenses, as these defenses are vulnerable to standard PGD attacks when the amount of randomization is small. In a specific setup, the authors prove a trade-off between the utility and robustness of randomization defenses, and demonstrate on real data sets that such a trade-off exists for two randomized defenses (Barrage of Random Transforms and randomized smoothing). Although there is concern about the lack of clear impact on the development of future defense schemes, the reviewers found the message and empirical results of the paper to be illuminating.
confidence: Less certain
Decision: Accept