BulletTrain: Accelerating Robust Neural Network Training via Boundary Example Mining
Authors: Weizhe Hua
Yichi Zhang
Chuan Guo
Zhiru Zhang
G. Edward Suh
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial training
efficient robust neural network training
robustness against common and adversarial corruptions
accelerate robust neural network training

Abstract: Neural network robustness has become a central topic in machine learning in recent years. Most training algorithms that improve the model's robustness to adversarial and common corruptions also introduce a large computational overhead, requiring as many as ten times the number of forward and backward passes in order to converge. To combat this inefficiency, we propose BulletTrain, a boundary example mining technique to drastically reduce the computational cost of robust training. Our key observation is that only a small fraction of examples are beneficial for improving robustness. BulletTrain dynamically predicts these important examples and optimizes robust training algorithms to focus on the important examples. We apply our technique to several existing robust training algorithms and achieve a 2.2x speed-up for TRADES and MART on CIFAR-10 and a 1.7x speed-up for AugMix on CIFAR-10-C and CIFAR-100-C without any reduction in clean and robust accuracy.

BulletTrain: Accelerating Robust Neural Network Training via Boundary Example Mining
Weizhe Hua', Yichi Zhang', Chuan Guo', Zhiru Zhang', G. Edward Suh CComell University, Facebook AI Research
(wh399, y22499, zhiruz, gs272 @cornell. edu, chuanguo8 com
com
Abstract
Neural network robustness has become a central topic in machine learning in recent years. Most training algorithms that improve the model's robustness adversarial and common corruptions also introduce a large computational overhead, requiring many ten times the number of forward and backward passes in order to converge. To combat this inefficiency, we propose BullerTrain - a boundary example mining technique drastically reduce the computational cost of robust training. Our key observation is that only a small fraction of examples are beneficial for improving robustness. BulletTrain dynamically predicts these important examples and optimizes robust training algorithms to focus on the important examples. We apply our technique to several existing robust training algorithms and achieve a 2.2x speed-up for TRADES and MART on CIFAR-10 and 1.7x speed-up for AugMix on CIFAR- -O-C and CIFAR-100- without any reduction in clean and robust accuracy.
Introduction
In the past decade, the performance and capabilities of deep neural networks (DNNs) have improved at an unprecedented pace. However, the reliability of DNNs undermined by their lack of robustness against common and adversarial corruptions, raising concerns about their use in safety-critical applications such as autonomous driving (Amodei et al., 2016). Towards improving the robustness of DNNs, a line of recent works proposed robust training by generating and learning from corrupted examples in addition to clean examples (Cubuk et al., 2019; Ding et al., 2020; Hendrycks et al., 2020; Madry et al., 2018; Wang et al., 2020; Zhang al., 2019b). While these methods have demonstrably enhanced model robustness, they are also very costly to deploy since the overall training time can be increased by up ten times.
Hard negative example mining techniques have shown success in improving the convergence rates of support vector machine (SVM) (Joachims, 1999), DNNs (Shrivastava et al., 2016), metric learn- ing (Manmatha et al., 2017), and contrastive learning (Kalantidis et al., 2020). Particularly, SVM with hard example mining maintains a working set of "hard" examples and alternates between training an SVM to convergence on the working set and updating the working set, where the "hard" examples significant in that they violate the margins of the current model. Partly inspired by hard example mining, we hypothesize that there exists a small subset of examples that is critical to improving the robustness of the DNN model, so that reducing the computation of the remaining examples leads to significant reduction in run time without compromising the robustness of the model.
As depicted in Figure 1,, the essential idea is to predict and focus on the "important" subset of clean samples based on their geometric distance to the decision boundary (i.e., margin) of the current model. For example, the correctly classified clean examples with large margin are unlikely to help improving robustness as the corrupted examples generated from them are still likely to be appropriately categorized by the model. We refer to "important" examples boundary examples since they are close to the decision boundary (c.g.. D in Figure lb). After identifying the boundary
35th Conference on Ncural Information Processing Systems (NeurIPS 2021).

---

1st iteration
2nd iteration
3rd iteration
(a) Existing robust neural network training algorithms Standard robust training approaches generate corrupted samples with equal effort for all samples (c) in mini-batch.
Ce Sop
R
(b) BulletTrain The proposed scheme focuses small subset of "important" clean samples (m) and allocates computational cost on obtaining corrupted samples for those important ones. This figure illustrates the case that only generates the corrupted samples for the important samples.
Figure I:
Comparison between existing robust training approaches and Bulle(Train on a synthetic binary classification task - The dash line is the current decision boundary of the linear model and the solid line represents the updated decision boundary after taking SGD step.
examples, the computational effort generating corrupted samples can be reduced for the rest of the clean examples, thus accelerating the overall robust training process.
In this work, we propose BulletTrain' a dynamic optimization that exploits boundary example mining to reduce the computational effort of robust DNN training. BulletTrain applies to robust training against either adversarial or common corruptions. It can substantially speed up state-of-the--e algorithms (Hendrycks et al., 2020; Wang et al., 2020; Zhang et al., 2019b) with almost no loss in clean and/or robust accuracy. Figure visualizes the situation where BulletTrain generates corrupted examples only for small fraction of clean examples, while standard robust training scheme requires obtaining corrupted examples for all examples.
To the best of knowledge, Bulle(Train is the first work exploit the idea of hard example mining in the context of accelerating robust DNN training. Unlike existing approaches which are limited reducing the compute for all examples uniformly, BulletTrain distributes the compute for clean examples differently, focusing on a small set of boundary examples. BulletTrain is also generally applicable to robust training against common and adversarial corruptions. The end result is that BulletTrain can lower the rumning time of the adversarial training such as TRADES (Zhang et al., 2019b) and MART (Wang et al., 2020) by more than 2.1 on CIFAR-10 (Krizhevsky, 2009) and the robust training against common corruptions such as AugMix (Hendrycks et al., 2020) by 1.7x on CIFAR-10-C (Hendrycks and Dietterich, 2019) without compromising the clean and robust accuracy.
Robust Training Overview
Preliminaries. We focus on K-class (K 2) classification problems. Given dataset {x,, Wi) B:))i=l,.... with a clean example x; E Rdd and its associated ground truth label yi E {I, K.. DNN classifier he parameterized by generates the logits output he(x;) for each class, where (x:) (x,), hi (x:)). The predicted label jú can be expressed as = arg max 1 (x:).
To improve the robustness of DNN classifier, state-of-the-art approaches (Hendrycks and Dietterich, 2019; Madry et al., 2018; Wang et al., 2020; Zhang et al., 2019b) generate corrupted inputs x; for the corresponding clean example x; training time and minimize the loss of the classifier with respect to the corrupted input. For robustness against adversarial attacks, x can be obtained using
'The name of BulletTrain implies robust (aullet-proof) and high-speed training.

---

Algorithm 1: Standard robust DNN training algorithm.
Input :batch size m, a N-step generation function Gx for generating corrupted samples
while not converged do
Read mini-batch { Xmi W1. Mm from training set for i 1,... mr do
x (x(x:)
I1 Cx(( is an N-step procedure for generating perturbations
end
0 < 0 Vo(C((ha(x)):: D. (ho(x))) ho(xx)))
// C is the surrogate loss
end
adversarial attack methods such as projected gradient descent (PGD) (Madry et al., 2018). For robustness common corruptions and perturbations, x is generated by introducing different data augmentations (Hendrycks and Dietterich, 2019). Algorithm 1 shows pseudo-code for a standard robust training algorithm.
Computational cost of robust training. Robust DNN training algorithms such as Algorithm I improve model robustness at the cost of paying extra computational overhead. There two main sources of the overhead: 1) The procedure Gv for generating corrupted input; 2) Forward and backward propagate using the surrogate loss L with respect to both clean and corrupted samples. We denote the extra computational cost for robust neural network training as C 4). For adversarial robustness, PGD adversarial training generates the adversarially corrupted input by solving the inner maximization max4e L(x + 6, y; 0) approximately using an N-step projected gradient descent method, where A is the perceptibility threshold and is usually defined using Ip distance metric: (A = {5 |00| < <) for some e 2 0). As a result, PGD adversarial training is roughly N times more expensive than ordinary DNN training, where N is usually between and 20.
In addition, Hendrycks et al. (2020) propose to boost the robustness against common corruptions using Jensen-Shannon divergence (JSD) as the surrogate loss. JSD loss can be computed by first generating two corrupted examples (x' and x"), calculating a linear combination of the logits as )x]]+ + he (x") ))/3, and then computing L(x,x', x") [KL[[h(x)) M] (xl(ho(x') || M] + (xx") || M)) where KI. stands for the Kullback-Leeible divergence. As result, the surrogate loss for improving the robustness against common corruptions triples the cost of the ordinary training as it requires forward and backward propagation for both x', and x".
M (he (x) + (xx)
Existing efficient training algorithms. A number of recent efforts (Andriushchenko and Flammar- ion, 2020; Shafahi et al., 2019; Wong et al., 2020) aimed at reducing the complexity of adversarial example generation, which constitutes the main source of computational overhead in adversarial training. For instance, Wong et al. (2020) proposed a variant of the single-step fast gradient sign method (FGSM) in place of multi-step methods, which drastically reduced the computational cost. However, it was later shown that the single-step approaches fail catastrophically against stronger ad- versaries (Andriushchenko and Flammarion, 2020). FGSM-based methods can also cause substantial degradation in robust accuracy (Chen et al., 2020) for recently proposed adversarial training methods such as TRADES (Zhang et al., 2019b). This result suggests that the adversarial examples generated using single-step FGSM are not challenging enough for learning a robust classifier.
In addition, existing efficient training approaches cannot be generalized to robust training against com- mon corruptions. The state-of-the-eee robust training algorithms against common corruptions (Cubuk al., 2019; Hendrycks al., 2020) use data augmentations to create corrupted samples in a single pass, where the number of iterations can not be further reduced.
BulletTrain
3.1 Motivation
As discussed in Section 2, robust training can lead to a significant slowdown compared ordinary DNN training. To reduce the overhead of robust training, our key insight is that different inputs contribute unequally to improving the model's robustness (which we later show), hence we can dynamically allocate different amounts of computation (i.e., different N) for generating corrupted samples depending on their "importance". In detail, we first categorize the set of all training samples into a disjoint union of three sets outlier, robust, and boundary examples as follows:
3

---

of steps for (Na)
of steps for Xy. (Na)
# of steps for Xo (Na)
1.0
0.8
0.6
4
0.4
2
0.2
0.0
2 4
0
4
# of steps Xo (No)
steps for Xs (Ne)
steps for Xs (Ws)
(a) NA = O.
(b) No = O.
(c) NR O.
Figure 2: The robust accuracy of setting one of NB. NR. and No to be zero and varying the other two between zero and seven on MNIST - All experiments are performed on four layer convolutional neural network trained with ten epochs. The step size for cach example is set to 1.7e/N. The robust accuracy represented by color is evaluated using PGD attacks with 100 steps and 20 restarts.
Outlier examples Xo: the clean input is misclassified by the DNN model hg-
= [x arg max hg (x) # v)
(1)
k=I...,K
Boundary examples xB: the clean imput x is correctly classified while the corresponding corrupted input x' is misclassified by the DNN model fig
{x mrg (x)) A arg max hi + y)
(2)
k=....K
k=
Robust examples Xn; both the clean input x and the corresponding corrupted input x' = GN((x) are correctly classified by the DNN model hig
{x arg max hij (x) arg maggaxh/he (x))) y} k=
X
k=l....K
Note that our definition of the outlier, boundary, and robust examples is dependent the current model he and can dynamically shift during training. That is, an outlier example may become a boundary example later when the robustness of the model improves. Similarly, robust example can also become boundary or even outlier example when robustness improves in other regions of the training distribution.
Robust training algorithms improve the robustness of DNN model by increasing the classification margin for each training sample so that its distance to the corresponding corrupted sample (i.e., ||x x') x'IIp) is smaller than the margin. We hypothesize that this per-sample margin is an indicator of the amount of contribution that provided by this sample during robust training.
Outlier examples xo have a negative margin because they are misclassified by the current DNN model. Therefore, it is unnecessary to generate even "harder" corrupted examples and optimize the model using these "harder" examples.
Boundary examples XB have positive margin to the current decision boundary but can be perturbed to cause misclassification. Training on a corrupted version of these samples is most helpful to increase the margin, thus making the model more robust.
Robust examples XR already have a margin large enough to tolerate common or adversarial corruption. As a result, training corrupted versions of these examples would provide less benefit compared to training on corrupted boundary examples.
To test our hypothesis, we conduct an empirical study of PGD adversarial training against ( attack 0.3) on MNIST (LeCun et al., 2010) in leave-one-out manner. The baseline PGD training achieves 90.6% robust accuracy by setting the number of steps for all samples to be seven. In our experiment, we fix the number of PGD iterations (N) for one of XB, Xo, and X be zero while varying N between zero and seven for the other two classes of data. The separation between and X for each mini-batch of data oracle, which determined using ten PGD steps. As depicted in Figure 2a, PGD training fails to achieve a robust accuracy over 40% when the number of steps for X (NB) is zero; thus demonstrating the importance of x When No equals zero (Fig. 2b), the highest robust accuracy is 1% higher than that of the baseline, indicating that setting No zero does
Xo-

---

XR
XB
Xo
Signed prediction varlance
XR
X5
Xo
0.10
0.75
Fraction
0.05
0.50
0.00
0.25
-0.05
0.00
600
650
700
750
800
Epochs
Training iterations
Figure 3: The fraction of XR. XB, and xo over epochs on MNIST.
Figure 4: The average signed prediction variance of XR. XB, and Xo over different iterations.
not impair the effectiveness of PGD training. Lastly, Figure 2c shows that PGD training can achieve reasonable robust accuracy without paying the extra computational cost on xg. However, the highest robust accuracy achieved with this setup is 89.2%, which is 1.4% lower than the baseline. Therefore, setting non-zero Nu might help improving the robustness of the model in practice.
This empirical observation reveals an opportunity to accelerate robust DNN training by focusing on the boundary examples. In doing so, the overhead of robust DNN training is then determined by the proportion of boundary examples among all training samples. As shown in Figure 3, the fraction of x increases while the fraction of x decreases over epochs the model becomes more robust. Moreover, the fraction of X 3 is relatively small compared to the other two classes of samples since boundary examples only present within the vicinity the decision boundary. Therefore, we believe that the computational cost of robust training (CIG'N, L) can be reduced substantially by attending more to the boundary examples.
3.2 Algorithm
Separate the clean samples. First note that outlier examples can be easily separated from the other two categories because the current model misclassifies them. Thus, we use the sign of prediction to identify outliers:
+1, if arg max hx(x)) = y
Sign of prediction = 11, otherwise
(4)
We can further distinguish between the boundary and robust examples by exploiting the fact that boundary examples are closer to the decision boundary than the robust ones. As suggested by prior work on importance sampling (Chang et al., 2017), the prediction variance (Var (Softmax(h (x))) can be used to measure the uncertainty of samples in classification problem, where Var[-] and Softmax(-) stand for variance and softmax function respectively. Samples with low uncertainty are usually farther from the decision boundary than samples with high uncertainty. In other words, the prediction variance indicates the distance between the sample and the decision boundary, which can be leveraged to separate X and Xn- We multiply the sign of prediction and the prediction variance as the final metric signed prediction variance VSrrr(-) As shown in Figure 4, the signed prediction variances of x n. XB, and xo from different mini-batches are mostly rank correlated (SV [ar[xx] < SVar(xn) & SVar xx)). suggesting that the proposed metric can distinguish between different types of samples. We empirically verified that other uncertainty measures such as cross- entropy loss and gradient norm (Katharopoulos and Fleuret, 2018) perform comparably to prediction variance, and hence use the signed prediction variance in this study.
As BulletTrain aims to reduce the computational cost, requires lightweight approach to differenti- ate between samples. The outliers can be separated easily based on the sign of Sarr. To separate between XB and X with minimal cost, we propose to distinguish the two categories of samples by estimating the fraction of Xg or XR- The fractions of x and cannot be computed directly without producing the corrupted samples. Therefore, we estimate the fraction of x (FR) of the current mini-batch using an exponential moving average of robust accuracy from previous mini-batches. As the robust accuracy of the model should be reasonably consistent across adjacent mini-batches, the moving average of robust accuracy from the past is good approximation of FR of the current
5

---

XR
X
X8
Cumulative fraction
Ng
iterations
Na
# Of iterations
Fraction
FR
Count
10
Fo
NR
NA
0
No
No
0.00
0.05
0.10
0.00
0.05
0.10
Signed prediction variance
Signed prediction variance
(a) The distribution of signed prediction variance of clean samples a mini-batch.
(b) The number of steps for each sample is assigned
based on the estimated fractions Fo and FR.
Figure 5: Illustration of the compute allocation scheme The grey line shows the number of steps assigned for the clean samples a mini-batch.
Algorithm 2: BulletTrain.
Input :btch m, a process generating corrupted samples Gv classification rule f. momentum p
Fo t 0; FR +
while not converged do
10
Read mini-batch {x1, Xmi 21 ..., Dm from training set
{zi, ..., Zm {ho (1) ho (xm)))) }
12
XR, XB, XB,Xo f- ((x)) . Xm FR)
I/ Separate between examples
13
X GNo (xo), xa GNn(XR). xBB GNN((E)
If Produce corrupted examples
14
{xi, Xm} + X | Xoi {21, .. km + (xo((i)) (xi),.., (x()))
15
FR f p. FR + (1 7 Σ, [arg max, (z()* = w:)/m
If Update FR
16
0 0-e 8 - Vo(C(1 21, Zm b, (z),... d H)
17 end
mini-batch. In addition, Figure 5a shows that X and X are not completely separable using the signed prediction variance. To make conservative predictions for robust examples, scale the Fr with a scaling factor 7, where 7 E (0, 1). FR can be obtained by:
D; m 1(arg max; h (x() y4
F p- FR + (1 p) 7
(5)
m
where 1()) is the indicator function, x' are the corrupted samples in the previous mini-batch, p is the momentum, and Fn is initialized to be zero.
Compute allocation scheme. After dividing the clean examples into three sets, it is relatively straightforward to assign computational effort to the samples in each category. Following our intuition discussed in Section 3.1, we spend the largest number of steps (Nn) on the samples predicted as boundary examples. For the rest of the samples, we assign the second largest number of steps (Nn) to robust examples and the lowest number of steps (No) to outliers.
Given FR. we first compute the signed prediction variances of all clean examples as SVar"" [SVar[ha (x)])) (Var(he(xm)))) } and then formulate non-parametric classification rule (f) as:
Xo-
if Sar[hh <
f(x,, FR) xx
XB, i < SVariha (x,)] < Perreetile(SVaatt FR)
(6)
XR: otherwise
where FR equals to 1 FR and (ercentile(X,gr q) returns the 9th percentile of X. The computational cost of f comes mostly from obtaining the logits of clean example he (x), which is already computed in robust DNN training. Therefore, the additional cost for assigning compute for each sample is negligible. Figure 5 (grey line) visualizes the compute allocation scheme for mini-batch of samples. It is worth noting that the proposed ff resembles a discretized Gaussian function, suggesting that a more refined allocation scheme can be obtained from a quantized Gaussian function. Here, we present the full algorithm of BullerTrain in Algorithm 2.
BullerTrain first identifies the robust, boundary, and outlier samples during training time by applying the classification rule f to signed prediction variance. The separation is relatively accurate as the

---

Table Robust accuracy and speedup of applying BulletTrain (BT) to robust neural network training against common corruptions (AugMix) on CIFAR-I0 and CIFAR-100.
CIFAR-I0
CIFAR-100
Defenses
Rohust Acc.
F8
Theor Speedup
Rohust Acc.
Fn
Theor. Speedup
AugMix
88.8%
1x
64.0%
1x
AugMix JSD loss
86.9%
3x
60.2%
3x
AugMix + BT
88.8%
0.35
1.8x
63.6%
0.36
1.8x
signed prediction variance can capture the margin between samples and the decision boundary of the current model. Then, clean examples take either No. Nn. or NB steps to generate the corresponding corrupted samples. Since only a small fraction of samples (i.e., boundary examples) requires executing the same number of iterations (Nn) as the baseline, the computational cost is reduced significantly. Lastly, the surrogate loss is computed with respect to the clean and corrupted samples. If both Nn and No are equal to zero, the corrupted sample remains the same as the original sample, thus eliminating the additional cost of forward and backward propagation of the corrupted samples. For simplicity, we let NB be the same N in the original robust training, No be zero, and .R E [No,NB) NB).
In adversarial training, since PGD-based algorithms typically employ a large number of steps, the main saving from applying BulletTrain stems from reducing the number of steps for outlier and robust examples. In training against common corruptions, the reduction in computation comes mainly from not computing surrogate loss and gradient for corrupted samples. For example, the computational overhead of AugMix can be reduced by half if we only generate corrupted samples for half of the clean samples. We will show that this leads to a large reduction in training overhead in Section 4.
4 Experiments
Experimental setup. To demonstrate the efficacy and general applicability of the proposed scheme, we leverage BullerTrain to accelerate TRADES (Zhang et al., 2019b) and MART (Wang et al., 2020) against adversarial attacks on CIFAR-10 10 and AugMix (Hendrycks et al., 2020) against common corruptions on CIFAR- and 100AR-100-C. To make a fair comparison, we adopt the same threat model employed in the original paper and measure the robustness of the same network architectures. Specifically, we evaluate the robustness against common corruptions of WideRessNet-444 (Zagoruyko and Komodakis, 2016) using corrupted test samples in CIFAR-10-C and CIFAR-10O-C. When we apply BulletTrain to AugMix, we set No = NR = and NB = as it only allows to turn on or off the AugMiX data augmentation for clean samples. The adversarial robustness of WideRessNet-3-11 is evaluated using 2GD (i.e., PGD attack with 20 iterations) Loc attack for TRADES and MART. The perturbation (e) of the lo attacks on CIFAR- 1-00R-0-10 is set to be 0.031. Both TRADES and MART without BullerTrain are trained using 10-step PGD) with step size a = 0.007. When BulletTrain is applied, set NB 10 with 0.007, Nn E [0,2) with a 1.7e/Nn, No O, and 7 0.8.
We use the measured average fraction of xB. XR. and xo (i.e., FB. FR. and Fo) to calculate the theoretical speedup of BullerTrain, assuming that all computations without dependencies can be parallelized with unlimited hardware resources. Specifically, in adversarial training, the N iterations for generating destructive examples and one iteration for updating the model must be executed sequentially. Therefore, the theoretical speedup can be written as follows:
N +
Theoretical speedup = FB NB FR NR + Fo No +1
Reduction in computation cost. As listed in Table 1, BulletTrain can reduce the computational cost of AugMix by 1.78x and 1.75x with no and 0.4% robust accuracy drop CIFAR- 10 and CIFAR- 100, respectively. The compute savings stem from only selecting 35% of clean examples to perform the JSD loss. Compared to removing the JSD loss completely for all examples, BulletTrain improves the robust accuracy by 1.9% and 3.4% on CIFAR-10 10 and CIFAR-100, respectively.
Table 2 compares clean and robust accuracy of TRADES with and without BullerTrain. Compared to the original TRADES adversarial training STRADES>=1/8 BulletTrain with Nn = achieves a 0.3% lower robust accuracy and a 0.9% higher clean accuracy. It is worth noting that the robustness
7

---

Table 2: Robust accuracy and speedup of applying BulletTrain (BT) to TRADES adversarial training
against the white-box PGD20 attack on CIFAR-10 - 0.8 is used for TRADES with BT.
Defenses
Clean Acc.
Robust Acc.
FB
FR
Fo
Speedup
TRADES
88.64%
49. 19.14%
1
0
1x/
TRADES
84.92%
56.61%
1
0
0
1x
TRADES + FAST
93.94%
4.48%
1
0
0
5.5x / 337x
TRADES YOPO-2-5
88.47%
45.28%
I
0
-/3.1x
TRADES + YOPO-2-5
89,95%
46.60%
0
-/3.1x
TRADES + BT
87.50%
52.10%
0.26
0.55
0.18
3.0x 2.7x
T BTN 85.89 %
56.35
0.28
0.54
0.18
2.3x 2.2x
Table 3: Robust aceuracy and speedup of applying BulletTrain (BT) to MART adversarial training against the white-box PGID20 attack on CIFAR-10
0.8 is used for MART with BT.
Defenses
Clean Acc.
Robust Acc.
Fy
Fx
Fo
Theor/Wall-llock Speodup
MART
87%
57.39%
1
1x lx
MART
FAST
93.95%
0.20%
5.5x /400x
MART N
87.12%
58.11%
0.29
0.44
0.27
2.5x /
MART
NTN 86.60%
58.74%
0.30
0.43
0.26
2.2x / 119x
of BullerTrain remains comparable to TRADES against stronger attacks. Specifically, TRADES with and without BulletTrain Na=2 achieve 54.32% and 54.33% robust accuracy against PGD-100 with 10 restarts, and 54.41% and 54.49% robust accuracy against PGD-1000 with 5 restarts.
TRADES can make trade-off's between the clean and robust accuracy by varying the value of hyperparameter X. When aiming for lower robust accuracy, BulletTrain can further reduce the Nn from two to zero instead of using smaller and still obtain similar clean and robust accuracy as TRADES As result, BulletTrain achieves 2.3x and 3.0x computation reduction over the TRADES baseline targeting at 56.3% and 49.3% robust accuracy, respectively. In addition to TRADES, we also demonstrate the effectiveness of BullerTrain on MART as listed in Table 3. BulletTrain with N₂ = is able to improve the clean and robust accuracy by 2.4% and 1.3% with 2.2x less computation compared to the original MART scheme. Similar to TRADES, we can trade off robust accuracy for clean accuracy and speedup by using a smaller NR. When NR = 1, BulletTrain still achieves both higher clean and robust accuracy than the MART baseline and reduces the computational cost by 2.5x.
To compare with other efficient methods on adversarial training. we directly apply YOPO (Zhang al., 2019a) and FAST (Wong et al., 2020) on TRADES and MART. Table 2, despite the YOPO- 2-5 can improve the runtime by 3.1 the robustness accuracy of YOPO-2-5 is 10% lower than the TRADES baseline. addition, the single-step FAST training algorithm also fails to obtain a robust DNN model against PGD attack. GradAlign (Andriushchenko and Flammarion, 2020) proposes to address the catastrophic overfitting problem of FAST by introducing an additional gradient alignment regularization. While GradAlign attacks, we find that combining GradAlign and FAST still does not improve the accuracy of the robustness of FAST. We further compare the effectiveness of BulletTrain and a multi-step variant of FAST in Table 4. For BulletTrain, we change the value of NB E [3,6] 6] while fixing NR = 2, No = O.
significantly improve the robustness of the model under stronger
Table 4: Comparison of accuracy and theoretical speedup of a multi-step FAST and BulletTrain (BT)
on CIFAR-10 The numbers in parentheses show accuracy differences compared to TRADES
TRADES
Multi-stpp FAST
TRADES
BT
Theot/WWll-clock Speedup
Theor/Wall Speedup
Clean Acc. (%)
Robust Acc. (%)
NB
Clean Ace. (%)
Robust Acc. (%)
2 85.43 (+0.51)
50.56 (-6.05)
3.7x /3.0x
3
86.66 (+1.70)
$5.93 (-0.08)
3.7x /3.0x
3
84.47 (-0.45)
53.52
(-3.00)
2.8x 2
4
86.17 (+1.25)
55.77 (-0.84)
3.3x /2,8x
4
84,23 (-0.09)
53.95
(-2.00)
2.2x x
5
85,89 (+0.97)
56.17 (-0.44)
3.0x /
5 84.12 ( 0.82)
54.45
(- 2.16)
1.8x / 1.8x
86.28 (1 (11.0))
56.0 o-0.61)
2.8x 12.x
8

---

y= 0.65
0.7.7
y=
No
y= 0.7
y= 0.8
y= 0.9
No
Ne
No
Accuracy (%)
80
Accuracy (%)
80
70
70
60
60
1.9
2.0
2.2
2.4
2.5
1.6
1.8
2.0
2.2
2.6
Theoretical Speedup (x)
Theoretical Speedup (x)
Figure 6: The theoretical speedup vs. accuracy of TRADES+BT under different y values - The dash line shows the clean accuracy and the solid line represents the robust accuracy.
Figure 7: The theoretical speedup vs. accuracy of TRADES+BT under different n. values - The dash line shows the clean accuracy and the solid line represents the robust accuracy.
and 7 0.75 obtain different computation costs and accuracy. Compared the multi-step variant of FAST, BullerTrain dominates in clean accuracy, robust accuracy, and theoretical speedup. When the goal is to reduce the computational effort by 3x, BulletTrain achieves 1.4% and 2.2% improvement in clean and robust accuracy, respectively. We believe that BulletTrain outperforms existing efficient robust training approaches because BulletTrain can allocate computation for each sample dynamically based on the sample's s importance instead of reducing computation for all samples equally,
Wall-clock speedup. To measure the wall-clock speedup of BulletTrain, benchmark the robust DNN training algorithms with and without BulletTrain using a single NVIDIA GPU. We ensure that no other intensive processes reduces the runtime of AugMix from 1.82 hours to 1.08 hours and from 1.84 hours to 1.10 hours for CIFAR-10 and CIFAR-100, respectively. The runtime is reduced by 1.7x given the 1.8x theoretical speedup. TRADES baseline is trained with 76 epochs using 44.78 hours on CIFAR-IO. BulletTrain able reduce the training time of TRADES by 2.2x compared to the theoretical speedup of 2.3x. Moreover, as shown in Table 4, BulletTrain achieves a wall-clock speedup similar to that of FAST when their theoretical speedups are close, suggesting that BulletTrain can be effective in achieving real-world performance gains on the GPU.
running in parallel with the robust training job. BulletTrain
Sensitivity of hyperparameters. We further investigate the impact of hyperparameters NR and on the accuracy and theoretical speedup. Figure 6 shows that the accuracy and theoretical speedup of BulletTrain under different 7 E [0.65, 0.9). The clean and robust accuracy the choice of 7, showing the stability of BullerTrain. On the other hand, Nr controls the trade-off between the robust accuracy and clean accuracy/theoretical speedup. A smaller Ng improves the clean accuracy and the speedup while reducing the robust accuracy. Unlike FAST, choosing different NR E [0, 5] for BulletTrain does not lead significant decrease in robust accuracy.
sensitive to
Related Work
Robustness against common corruptions. Data augmentation has been a common technique to improve the generalization of DNNs (Devries and Taylor, 2017: Zhang et al., 2018). Hendrycks and Dietterich (2019) provide benchmarks to evaluate the robustness against common corruptions. AutoAgument (Cubuk al., 2019) proposes enhance the robustness by training the model with learned augmentation, which still leads to more than 10% accuracy degradation Hendryeks et al. (2020) try further improve the robust accuracy using a mix of augmentations to create different versions of corrupted examples and then leverage the JSD loss between clean and corrupted examples to optimize the model. BulletTrain can reduce the overhead of robust training by only augmenting subset of examples and computing the JSD loss for those augmented examples.
CIFAR-10-C.
Adversarial robustness. To train a robust network against powerful adversarial attacks, Madry et al. (2018) propose to introduce adversarial examples obtained by using multi-step FGSM during training, namely PGD adversarial training. Recently, PGD adversarial training has been augmented with better surrogate loss functions (Ding et al., 2020; Wang et al., 2020: Zhang et al., 2019b). In particular, MMA training (Ding et al., 2020) attempts to improve the robustness by generating adversarial examples with the optimal perturbation length, where the optimal length e* is defined as the shortest perturbation that can cause a misclassification. BulletTrain bears some similarities with the MMA training in the sense that BulletTrain also decides the number of steps based the margin

---

between the input samples and the current decision boundary. However, BulletTrain aims to reduce the computation cost of adversarial training by setting an appropriate number steps for each sample dynamically while MMA requires expensive bisection search to find the approximate value of e*.
Importance sampling. Importance sampling has been used to speed up DNN training. Schaul et al. (2015), Loshchilov and Hutter (2015), and Chang et al. (2017) sample the data based on the importance metric such as loss. Calculating the loss requires forward propagation. which makes infeasible to obtain the up-to-date value for each sample. Instead, previous works keep track of the losses of previously trained samples and select important samples based on historical data. However, since the model is updated after each training iteration, the loss of the samples which have not been used recently may be stale. In contrast, BulletTrain still goes through every sample and obtains the up-to-date scores for all samples before allocating the computational cost for each sample.
6 Conclusion and Future Work
We introduce dynamic boundary example mining technique for accelerating robust neural network training, named BulletTrain. Experimental results show that BulletTrain provides better trade-offs between accuracy and compute compared to existing efficient training methods. Potential future work includes determining the number of steps necessary for each sample.
7 Acknowledgements
would like to thank the anonymous reviewers for their constructive feedback on earlier versions of this manuscript. Weizhe Hua and Yichi Zhang supported in part by the National Science Foundation under Grant CCF-2007832. Weizhe Hua is also supported part by the Facebook fellowship.
References
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. 2016.
Concrete problems in ai safety. arXiv preprint
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. In NeurlPS, 2020.
Haw-Shiuan Chang, Erik Learned- Milleer, and Andrew McCallum. Active bias: Training more accurate neural networks by emphasizing high variance samples. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 1003-1013, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97815 11866996,,
Jinghui Chen, Yu Cheng, Zhe Gan, Quanquan Gu, and Jingjing Liu. Efficient robust training via backward smoothing. CoRR, abs/2010.01278, 2020. URL https: /ttpiviiivvv.///////eee/ea/aavva wtt.aaiwwwaaaaaaaaaeareorarreere abs abs/2010. /2010. 01278.
Ekin Dogus Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V. Le. Autoaugment: Learning augmentation policies from data. 2019. URL pestps://arxss httpss//arxxvvoorr///////0000 org/ppdf/880 09501. pdf.
Terrance Devries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout. CoRR, abs/ 110111088.55222 2017. URL http: org/ wwtp//rgg////oooooeoe 04552.
Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. MMA training: Direct input space margin maximization through adversarial training. In International Confer- ence on Learning Representations, 2020. URL https: http////ppe//eieeee//e/ee/ee net meeefformm? forum?id- AkeryxBtPP.
/
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corrup- tions and perturbations. Proceedings of the International Conference on Learning Representations, 2019.
10

---

Dan Hendrycks, Norman Mu, Ekin D. Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshmi- narayanan. AugMix: A simple data processing method to improve robustness and uncertainty. Proceedings of the International Conference on Learning Representations (ICIRR,, 2020.
Thorsten Joachims. Making Large-Scale Support Vector Machine Learning Practical, page MIT Press, Cambridge, MA, USA, 1999. ISBN 0262194163.
Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus. Hard negative mixing for contrastive learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21798-21809. Curran Associates, Inc., 2020. URL https: http://ppccceen.cceeeepepoc neurips. paper/2020/ file/ f7 cadee00bbb cc 92b 91cf www.ff44200000o P
Angelos Katharopoulos and Francois Fleuret. Not all samples are created equal:
Deep learning with importance sampling. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages
PMLR, 10-15 Jul 2018. URL http: http:://poccceeddeeeeeo mlr. press/v80 kakkaahaaarpoo wwttaaropoouoslse.. html.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://lynn.lecun.coom. wwt.e////////iisstttt.mmmm 2, 2010.
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. CoRR, org/ abs 1511.11111 06343.
abs//511.00331 1.06343, 2015. URL
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference on Learn- ing Representations, 2018. URL https:
wwtp///eeeeeeeeeee/eeeeeeeeoeeee /
R. Manmatha, Chao- Yuan Wu, Alexander J. Smola, and Philipp Krähenbühl. Sampling matters in deep embedding learning. In IEEE International Conference Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 2859-2867. IEEE Computer Society, 2017. doi: 10.1 10.100//CCV2001..3300 URL https: / /doi. org/10 1119/111CCCC 2017.309.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay, 2015. URL http::/t///.. //tp://axvvvvvv/ htrg/abs//11 1511. cite a11iv: 1 1059522ommeet: Published
at ICLR 2016.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL https://proceediing wereieeeeur.pp.mp ct/ http/aape/220133 2019/file/ 7503cfacd12055 333303333000 9b
pdf.
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training Region-based Object Detec- tors with Online Hard Example Mining. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In ICLR, 2020.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020. htRps: /
Sergey Kagoruyko and Nikos Komodakis. Wide residual networks. CoRR, Abs//605.07744 2016.
URL http::tt////iiii org/ abs/160s 07146.
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. arXiv preprint arXiv: 1905. 00877, 2019a.

---

Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing. Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning, 2019b.
Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018. URL https: // //operreview nnt/ / forum? 1d-r11dp1-RR.
12


Reviews:
[{"review_id": "wbQ3daNeQRC", "reviewer": "Reviewer_jFeM", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nSome comments:\n\nI’m not sure if outliers is a good term to be used for misclassified samples. \n\nCan 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?\n\nHow 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?\n\nWhat 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.\n\nIt 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.\n\nI appreciate the authors for comparing wall clock speedup with theoretical speedup and showing that they both compare.\n\n[1] Balaji et al., “Instance adaptive adversarial training: Improved accuracy tradeoffs in neural nets.”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As pointed out in the previous section, I see the following limitations: \n\n- Deciding (N_R, N_o, N_b) might be a laborious task\n- Experimental results on stronger attacks like PGD-100/1000 are missing\n- Adversarial training on large scale datasets Imagenet would have really helped showcase the efficacy of this method", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "jUzaLsTO23", "reviewer": "Reviewer_d8Mu", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nI 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. \n\nZhang, 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. \n\n\n====\n\nUpdate after rebuttal\n\nThanks 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There seems to be no significant negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "fW6kGDjWsR9", "reviewer": "Reviewer_5TSA", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ 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).\n+ The approach presented in the paper is sensible, well motivated and intuitive.\n+ The design decisions are also sensible and are reasonably validated experimentally.\n+ The experimental results show consistent gains in efficiency with little or no losses in performance.\n+ The paper's writing is adequate, and the narrative helps the reader understand the thought process behind the approach.\n+ While sharing motivation/intuitions with previous works, the paper's proposal in itself is original.\n\n\nWeaknesses that affect my rating:\nComment: 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):\n+ 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)\n+ Why are not results for MART reported in the \"Wall-clock speedup\" section? These results must have been computed for filling Table 3, right?\n+ 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).\n+ 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?\n+ 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.\n+ 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?\n+ I think the paper could benefit from commenting about its relation with the following:\n- Attacks Which Do Not Kill Training Make Adversarial Learning Stronger, Zhang et al., ICML2020\n- Hold me tight! Influence of discriminative features on deep network boundaries, Ortiz-Jimenez et al., NeurIPS2020\n- Decision Boundary Analysis of Adversarial Examples, He et al., ICLR2018\n- Improving Adversarial Robustness Through Progressive Hardening, Sitawarin et al., 2020.\n\n\n\nWeaknesses that do not affect my rating but should be addressed if possible:\n+ L58: the second $x_i$ in the line is not boldface. Is this on purpose?\n+ Algorithm 1 and 2: nit-picky comment: use the labels $y_i$, probably in the $G_N$ and $\\mathcal{L}$ functions.\n+ L133: unsure about the reference for MNIST.\n+ Figure 4, plot x-label legend: iteraions\n+ Figure 5(a). x-axis legend: predidction\n+ Algorithm 2, L8: I think $F_O$ is never used.\n+ 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? \n+ 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.\n+ 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.\n+ L230: with no and\n+ L263: baseline are\n+ Figure 6 caption: dash line\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they did.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)