Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces BulletTrain - an algorithm for speeding up robust training algorithms for both adversarial and corruption based robustness. This is an important problem to study because robust training (adversarial training in particular) is generally expensive which makes it hard to scale these algorithms on large datasets. The algorithm proposed in this paper, while being lightweight and easy to implement, shows strong empirical gains. Overall, I like this paper.
main_review: The main contribution of this paper is to divide the training examples into three sets: outliers, boundary and robust examples. After dividing these samples, each set of samples is allotted a different perturbation generation budget. While dividing samples into different sets have been explored already in the context of adversarial training (for example, [1]), I believe this paper does a good job of neatly packaging this idea into a simple framework. The authors argue that boundary samples are the most important ones to train on. This has been neatly illustrated in Figure 2. Use of lower budgets for robust and outlier samples provides good gains in computation. To separate the three sets of samples, the authors use a metric called signed prediction variance which is again very easy to compute. Good empirical results on different benchmarks highlight the significance of the proposed approach.

Some comments:

I’m not sure if outliers is a good term to be used for misclassified samples. 

Can you comment on the failure modes of signed prediction variance. I agree that prediction variance is a decent measure of uncertainty, but it has some drawbacks as well. Can you use other measures used in uncertainty estimation to improve the performance?

How to decide N_R, N_o and N_b? Is there a principled way to decide this? For example if I give you a computational budget, how do you choose  (N_R, N_o, N_b) triplet for this budget?

What happens if you perform adversarial evaluation on stronger attacks, say PGD-100 or PGD-1000 with multiple restarts? Its important to evaluate stronger attacks to check if things like gradient masking happens. I would recommend authors to have these numbers to get a complete picture.

It would be really nice if the authors perform adversarial training on large scale datasets like Imagenet where adversarial training is super expensive. If BT is able to train adversarial training on Imagenet faster, it would be an amazing result.

I appreciate the authors for comparing wall clock speedup with theoretical speedup and showing that they both compare.

[1] Balaji et al., “Instance adaptive adversarial training: Improved accuracy tradeoffs in neural nets.”

limitations_and_societal_impact: As pointed out in the previous section, I see the following limitations: 

- Deciding (N_R, N_o, N_b) might be a laborious task
- Experimental results on stronger attacks like PGD-100/1000 are missing
- Adversarial training on large scale datasets Imagenet would have really helped showcase the efficacy of this method
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a technique for reducing the computational cost of robust training by dynamically selecting which samples to assign the most compute power to during either adversary generation (for robustness against adversaries) or the forward pass of alternative samples (for robustness against common corruptions). The approach assigns compute power according to proximity to decision boundary; such quantity is estimated, in turn, by a (simple yet effective) proxy that is defined in the paper. The method is sensible, intuitive and well motivated. Experimental results show sizable gains in efficiency with little or no losses in robustness.
main_review: Strengths:
+ The paper's object of study is interesting for the robustness community (in terms of providing further understanding as to what are the particular factors that affect robustness) and also for the deep learning community (in terms of how such an approach can make robust training more compute friendly for other applications).
+ The approach presented in the paper is sensible, well motivated and intuitive.
+ The design decisions are also sensible and are reasonably validated experimentally.
+ The experimental results show consistent gains in efficiency with little or no losses in performance.
+ The paper's writing is adequate, and the narrative helps the reader understand the thought process behind the approach.
+ While sharing motivation/intuitions with previous works, the paper's proposal in itself is original.


Weaknesses that affect my rating:
Comment: overall I like the paper's idea, but the main drawback from my perspective is that there are a couple unclear items in the experiments. In particular, the largest one being the disproportionate importance that *theoretical* speedups are given, instead of actual empirical speedups. In any case, I think the empirical results would still yield the same conclusions as those presented in the paper, but these results should be reported. If these results are reported and the conclusions are still the same, as I suspect (and provided other reviewers do not raise concerns I may have overlooked), I am willing to suggest the acceptance of this paper. Next, I outline my largest concerns (in order of importance):
+ In Tables 1-4, what does "Theor. Speedup" mean? Are these *theoretical* gains, or actual gains as measured empirically? If they are the former (as I assume, given the paragraph named "Wall-clock speedup" on L258), then it must also be explained how the fractions $\bar{F}_x$ were estimated across training iterations, as they are fundamental for the overall compute time, right? Also importantly, if all the clean/robust accuracies were computed such that these tables could be filled, it also means that the actual speedups must have been measured too, so why not report them in these tables along with the theoretical speedups? (and the same comment can be made for Figs. 6 and 7)
+ Why are not results for MART reported in the "Wall-clock speedup" section? These results must have been computed for filling Table 3, right?
+ I think the experiment reported in the Section 3.1 (more specifically L132) is interesting, and I agree with the results and the conclusion drawn from them. However, I would inquire about an implementation concern: Figure 2, in particular subfigures (b) and (c), shows that there is a *dramatic* change in robust accuracy when varying steps in for $N_B$ from $1\to2\to3$: robust accuracy can suddenly jump from $\sim0$ to $>0.8$. I find this result intriguing, and even a bit suspicious. Is it possible that this is because the size of steps taken by PGD are not dependent on the amount of steps that are taken (as this is nowhere reported for this experiment, but apparently was indeed used for the main experiments, as reported in L228)? That is, can it be the case that we are observing this phenomenon mainly because training with such few steps does not allow optimization to reach the boundary of the $\epsilon$-ball constraints? In principle this would mean that the model is being trained against weaker adversaries, while always being evaluated against stronger ones. If this is the case, I think this invalidates the results presented here (even though I still think that fixing for this issue would still yield the same overall conclusions presented in the paper).
+ The distribution reported in Figure 5(a) seems a bit weird: (i) why are these results for a single mini-batch? Why not show this for the entire dataset? (ii) at what stage of training is this being computed? Please specificy, and (iii) a large portion of the examples appear to be incorrectly classified ("outliers"), but this contradicts what was shown in Figure 3, no?
+ Did the authors consider assessing how good of an estimate is the usage of Signed-Prediction Variance as a proxy for knowing which samples are $\mathbf{x}_R$ or $\mathbf{x}_B$? For instance, computing this quantity for all samples and also computing the adversaries of these samples with a PGD attack with lots of iterations, or running DeepFool/FAB to estimate the distance to the decision boundary? Such validation would have been interesting.
+ The intuition behind using the consistency of robust accuracy across adjacent mini-batches is sensible, but would not this assumption (namely Eqn. (6)) induce a bias for $F_R$? As the algorithm will always be estimating the new $F_R$ by using the PGD steps budget that was itself defined by the previous $F_R$? Could the authors comment on this phenomenon?
+ I think the paper could benefit from commenting about its relation with the following:
- Attacks Which Do Not Kill Training Make Adversarial Learning Stronger, Zhang et al., ICML2020
- Hold me tight! Influence of discriminative features on deep network boundaries, Ortiz-Jimenez et al., NeurIPS2020
- Decision Boundary Analysis of Adversarial Examples, He et al., ICLR2018
- Improving Adversarial Robustness Through Progressive Hardening, Sitawarin et al., 2020.



Weaknesses that do not affect my rating but should be addressed if possible:
+ L58: the second $x_i$ in the line is not boldface. Is this on purpose?
+ Algorithm 1 and 2: nit-picky comment: use the labels $y_i$, probably in the $G_N$ and $\mathcal{L}$ functions.
+ L133: unsure about the reference for MNIST.
+ Figure 4, plot x-label legend: iteraions
+ Figure 5(a). x-axis legend: predidction
+ Algorithm 2, L8: I think $F_O$ is never used.
+ Table 1 and 2 should report in the caption what $\bar{F}_x$ stands for. Further, how exactly are these quantities being computed? By the end of training? Or when? 
+ In Tables 1-4, what convention do bold-faces and underlines follow? I think their current usage is misleading, as the reader may think the best results are obtained with the proposed approach, when they are not.
+ The caption of Table 2 states that $\epsilon = 0.8$ is used for TRADES with BT (same thing for Table 3 and MART). What does this experimental setup mean? That the TRADES adversaries are being computed within a ball of this radius? Or that the robust accuracy reported here is being computed within such ball? The answer to this question could very much change how the reported results are understood.
+ L230: with no and
+ L263: baseline are
+ Figure 6 caption: dash line


limitations_and_societal_impact: Yes, they did.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes to accelerate robust training by identifying three categories of examples in each mini-batch: outlier examples (the clean example is misclassified), boundary examples (the clean example is correctly classified but can be perturbed to an adversarial example), and robust examples (can be robustly classified). The proposed method sets different numbers of attack steps for the three categories respectively, and in particular, the step number is set to 0 for outlier examples and 2 for robust examples, which is smaller than boundary examples. Thereby, the cost on outlier examples and robust examples is reduced. Experiments show that the proposed method has an around 1.7X~2.1X speed-up with similar robust accuracy. 
main_review: This paper is mostly clearly written, and the proposed method is mostly well motivated. However, I am not certain on some technical details. For line 172, why should outliers be determined based on SVar? If outliers are just misclassified examples, why can’t they be determined just by the classification on the clean examples? Besides, Eq. (6) needs more explanations. Why is this transformation good for separating $X_B$ and $X_R$? Does it really perform well in experiments? In the experiments, there is a speed-up compared to the baseline, but ~2X speed-up is probably not very significant. 

I think the comparison with prior works is probably not sufficient, especially on the comparison with prior works for accelerating adversarial training. This paper has mentioned Andriushchenko and Flammarion, 2020; Shafahi et al., 2019; Wong et al., 2020. But the experiments seem to have only involved Wong et al., 2020. I think it is important to also include empirical comparison with other prior works, considering ~2X speed-up is not very large. And a comparison with Zhang el. al., 2019 (cited below) is probably also needed. 

Zhang, D., Zhang, T., Lu, Y., Zhu, Z., & Dong, B. (2019). You only propagate once: Accelerating adversarial training via maximal principle. arXiv preprint arXiv:1905.00877. 


====

Update after rebuttal

Thanks to the authors for the rebuttal! I think most of my concerns have been well addressed. With the new discussion and results from the authors, I'm increasing my recommendation to 6.
limitations_and_societal_impact: There seems to be no significant negative social impact.
review_title: null

Meta-review: This work proposes to a method to accelerate robust training of neural networks by focusing on boundary examples. The idea is interesting and is well received by the reviewers. The paper is well motivated and clearly writing. Authors' rebuttal also did a great work at resolving the concerns from the reviewers. 


On the other hand, there are some weaknesses that we hope the authors make efforts to address in the final version. This includes (as summarized by reviewer 5TSA during discussion): (1) experimental validation of the signed-prediction variance proxy used in the paper, and (2) lack of comparison with other defenses/attacks. In particular, Reviewer d8Mu mentioned critical comparisons that the paper should have reported initially: comparisons with YOPO, Free and GradAlign. Reviewer 5TSA  was particularly concerned with the disproportionate importance given to theoretical speedups in contrast to empirical speedups.
Decision: Accept (Poster)