Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work proposes backward smoothing as an advanced random initialization to improve a model's adversarial robustness. The paper is well-written and easy to follow. However, I have the following concerns:
1) The paper argues that random initialization can help fast adversarial training because it helps improve the smoothness of the loss function. However, a recent work "Understanding and Improving Fast Adversarial Training" has a very nice explanation and solution on this problem, which is much more convincing to me.
2) Even if I accept the condition that random initialization helps improve the smoothness of the loss function, the motivation showing in Figure 3 that the current smoothing effect by using random initialization is not sufficient can not convince me. It is definitely in the expectation that KL divergence between clean and adversarial examples would be much greater than random initialization. And I do not think that this can shed any light on the insufficient smoothness by the current random initialization.
3) At the end of section 4, the authors mention that "Note that the proposed Backward Smoothing seems also compatible with Adversarial Training. However, Adversarial Training does not contain terms using KL divergence loss, which may hinder its performance. We will show this empirically in Section 5." I tried to find experiments with backward smoothing applied to standard adversarial training but did not find these results. It would be good if the authors can point it to me if I missed them. Conditioned on  that we observe backward smoothing does not greatly help standard adversarial training, this failure case raises a great concern to me. Compared to random initialization, backward smoothing provides a better random initialization which can provide better smoothness. My question is: why a better random initialization can not generalize to standard adversarial training?
4) For Table 5, it is necessary to include FAST TRADES as backward smoothing is mainly applied to TRADES.
5) Does backward smoothing really help adversarial robustness or it just plays the tradeoff game between clean accuracy and adversarial robustness? For example in Table 8, comparing FAST Trades and backward smoothing, backward smoothing provides better adversarial robustness but sacrifices a big clean accuracy. 

In all, I vote for a reject for the current version of this work.

********After Discussion*************
I thank the authors for answering my questions and performing additional experiments. Some of my concerned are addressed during the discussion stage. Therefore, I raise my score from 4 to 5. However,  I still hold my opinions that this work does not have a strong motivation, does not help too much for standard adversarial training and has a potential trade-off problem.
review_title: Insufficient motivations and the improvements seem to be a trade-off.

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Summary:**
The paper proposes a new algorithm for performing fast adversarial training. The proposed algorithm consists in solving the inner maximization problem in the following way: first, one takes a step of projected gradient descent (PGD) wrt an auxiliary loss (motivated by the idea of backward smoothing), and then one takes another step of PGD wrt the original loss function which is the KL divergence as suggested by the TRADES paper. The authors argue that taking two steps of PGD wrt different losses leads (perhaps, surprisingly) to higher robustness compared to taking two steps of PGD wrt the same original loss function.


**Pros:**
- Better robustness of models when computations are bounded with only 2 steps of PGD to solve the inner maximization problem.
- Thorough robustness evaluation which includes the recent AutoAttack.
- Ablation studies that help to better understand the influence of the two main hyperparameters of the proposed method.
- The paper is clearly written although I would rather disagree with the justifications for the proposed method (see below).


**Cons:**
- The explanations from Section “Why random initialization helps?” are not convincing because randomness is just one part of the solution proposed by Wong et al. (2020) to solve the inner maximization procedure. Another part is reducing the step size from 2\*eps to 1.25\*eps which effectively reduces the norm of the perturbation compared to standard FGSM as discussed in a recent related paper Andriushchenko & Flammarion (2020). Therefore, taking into account the crucial effect of the step size as shown in Fig. 3 in Wong et al. (2020), I don’t think there is a reason to believe that randomness *alone* has any positive influence on the solution of the inner maximization problem. This is my main concern as the whole paper is built on the connection to randomized smoothing. I would be open to raise the score if you can show that randomization alone (with a single $\xi$ or even multiple $\xi$ to approximate the expectation in Eq. (3.2)) with the full step size (2\*eps) alone can prevent catastrophic overfitting and help to achieve better robustness.
- All the experiments are performed for eps=8/255 which is close to the eps for which even standard FGSM leads to high robustness (e.g., see Fig. 1 in Andriushchenko & Flammarion (2020)). Thus, it would be highly beneficial to show that the proposed approach works equally well compared to the competing approaches for a higher eps, e.g. eps=16/255 on CIFAR-10.
- The proposed procedure of backward smoothing already appears in the literature in [Diversity can be Transferred: Output Diversification for White- and Black-box Attacks](https://arxiv.org/abs/2003.06878) where they propose a very similar algorithm but with the goal of obtaining a better adversarial attack (and thus they use multiple steps of PGD to solve it instead of just one). Although this paper is not yet published (accepted at NeurIPS’20), I think it would be important to at least acknowledge this connection.
- I am still quite surprised that for the inner maximization problem, taking two steps of PGD wrt *different* losses leads to higher robustness compared to taking two steps of PGD wrt the same original loss function. In order to rule out potentially suboptimal choice of the step size for *Fast TRADES (2-step)*, I would be interested in seeing results of a grid search over it, i.e. similarly to Table 7 but for *Fast TRADES (2-step)*.


**Minor suggestions:**
- Fig. 2: the best step size is at the boundary of the grid {10/255, 8/255, 7/255}, thus it would make sense to extend the grid with even smaller values of the step size to make sure that Fast TRADES is not reported with suboptimal hyperparameters.
- I'm also a bit surprised that *"Backward smoothing ... even outperforms the state-of-the-art robust training methods"* since the SOTA robust training methods include much more steps of PGD and thus they solve better the inner maximization problem. Why is their performance worse? Can it be, for example, because their hyperparameters were not sufficiently tuned (unlike for proposed method)?
- Table 5: the listed "AT" baseline is quite weak (44.04%) from Madry et al. (2018). It would be better to use the results / models from Rice et al. (2020) which show results of AT+early stopping comparable to that of TRADES.
- Table 5: it would be useful to add *Fast TRADES (2-step)* to the table as this is the most interesting baseline.


**Score:**
My current score is 4/10 but I would be willing to raise it if my first two concerns (mentioned in **Cons**) are resolved.

------

**Update after the public discussion:**

Thanks a lot to the authors for clarifying many details and providing additional experimental data. In the updated version of the paper, the authors improve the results of the baseline "Fast TRADES (2-step)" and add additionally a stronger baseline of "Fast AT (2-step)" (except on CIFAR-10 with eps=16/255 where it's missing). However, at least for eps=8/255 on CIFAR-10, CIFAR-100, Tiny ImageNet, the authors show consistent improvements over the baselines with comparable computational cost ("Fast TRADES (2-step)" and "Fast AT (2-step)"). This is an interesting result, although it's not clear to me whether it's specific to eps=8/255 or it would generalize also to higher epsilons such as eps=12/255 or eps=16/255. 

On the other hand, I still think that the current motivation of the method is very incomplete and it is still unclear why the proposed method should work in the first place. Perhaps, it's a good idea to further develop the additional experiments about the curvature of the loss surface at different points in the input space.

Then I think there is additional work to be done in terms of understanding what the proposed method actually does (even if we don't take into account how it was motivated -- via randomized smoothing or not). In particular, it's still completely unclear to me why 2 steps of PGD with respect to the original KL divergence (i.e. Fast TRADES (2-step)) works worse than first 1 step with respect to one KL-divergence and then 1 step with respect to another KL-divergence (i.e. Backward Smoothing). This seems quite ad-hoc and requires further explanations, in my opinion. Moreover, I find it also quite puzzling that Backward Smoothing even outperforms 10-step TRADES / AT as shown in Tables 3 and 4 -- not sure about a justification behind this.

Taking into account all of this, I update my score from 4/10 to 5/10. I think the paper can still be improved in various ways: both in terms of the motivation and experimental results.
review_title: Good experimental results but I don't agree with the motivation of the method (+ results on larger eps should be shown)

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes Backward Smoothing to close the gap in terms of robustness between standard multi-step and fast (one or two steps) adversarial training (AT). In particular, at high level, given a network $f$, a point $x$ and its logits $f(x)$ it suggests to first sample a random perturbation $\psi$ in the logits space around $f(x)$ and second computing, via one step of gradient descent, $\xi^*$ so to minimize the KL-divergence between the softmax values of $f(x) + \psi$ and $f(x + \xi^*)$. Then $x + \xi^*$ is used as starting point for one-step AT. The rationale behind the scheme is that the random step commonly added to $x$ before AT might be not sufficient to achieve a smoothing effect on the loss function and then an effective optimization.

Pros
1. The proposed method is simple and easily integrated into the TRADES training scheme.
2. The empirical results are strong, as Backward Smoothing  achieves better robustness than other fast AT versions and is more efficient that multi-step AT (including TRADES) with little loss in robustness. Also, the models are thoroughly tested with many white- and black-box attacks.

Cons
1. The theoretical explanation of why random initialization helps and the connection to randomized smoothing (Sec. 3) is not very convincing in my opinion. Randomized smoothing aims at estimating better directions for the gradient step, but it's not clear whether this is the case when using a single random point (this would need to be experimentally validated). An alternative explanation of the role of random initialization is presented in (Andriushchenko & Flammarion, 2020), which would be worth discussing.
2. The proposed method seems to share some similarities with ODI (Tashiro et al., 2020), which also proposes a scheme to find good starting points for PGD-based adversarial attacks optimizing some (randomly sampled) loss in the logits space. While in that work there's no focus on adversarial training, the overall idea looks similar, and I think the authors should comment on this.

Other comments and questions
1. In the comparison to other methods, I think for completeness it'd be good to show also Fast AT with 2 steps, since it has the same computational cost as Backward Smoothing and Fast AT performs better than Fast TRADES especially on CIFAR-100 and Tiny ImageNet. Additionally, including other techniques for fast adversarial training (Shafahi et al., 2019, Andriushchenko & Flammarion, 2020) might give a more complete picture.
2. In Table 5, the gap between Backward Smoothing and TRADES is larger than what reported in Table 2. Is this because of the larger architecture or just the evaluation with stronger attacks (or something else)?
3. How does the proposed technique behave for larger $\epsilon$? Is it still able to achieve results similar to multi-step AT (usually for larger $\epsilon$ the gap between single- and multi-step AT becomes even larger)?

Overall, as mentioned above, the paper presents strong empirical results which support the proposed method. However, the justification for the method as presented is not particularly convincing and should be better validated. Also, a discussion of the similarities with prior work seems needed.

Tashiro et al., "Diversity can be Transferred: Output Diversification for White- and Black-box Attacks"

---
Update after rebuttal

After reading the authors' response and the other reviews, I think the paper has quite clear pros and cons.

The experimental results (especially at $\epsilon=8/255$) are strong and the underlying idea of finding a good starting point for single step adversarial training makes sense to me (see reply below).

On the other side, the initial (and partially current) explanation relying on randomized smoothing given by the authors is not convincing, in particular when discussing the role of the random step in the success of Fast AT. The new experiments provided in the revision which rather analyze the smoothness of the starting point found by Backward Smoothing look like a much better explanation of the success of the proposed method (note that although the overlap of terminology I don't see a direct interpretation of the smoothness of the loss function at some specifically crafted point in terms of randomized smoothing). This should be more thoroughly analyzed and commented, which would consist in a quite major update of the paper in my opinion.

The current version doesn't provide an exhaustive motivation and analysis of the proposed method (in any direction, randomized smoothing or others), although the revision improves in this sense. Then, although I appreciate the good empirical results and I'm still in favor of the proposed method, I have to lower the score. I encourage the authors to clarify the weaknesses of the paper, which might result in a better understanding of what's needed for a successful fast adversarial training.
review_title: Good empirical results, theoretical explanation to improve

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: This paper seeks to reduce the training time of TRADES adversarial training. It tries to understand fast adversarial training methods (single-step adversary methods) by viewing the random initialization of the adversarial perturbation in the PGD steps as randomized smoothing, making the inner maximization (the adversary) easier. They find empirically that this smoothing isn't enough for vanilla fast adversarial training with the TRADES objective (in the sense that it doesn't improve much beyond fast AT after switching out the objective), requiring large step sizes that bring instability to training. Then, they aim to improve fast TRADES by their proposed algorithm, "backward smoothing", which first perturbs the output of the model and then solves the inverse problem to find the corresponding input that would make this perturbation. The intuition is to make sure that the smoothing averages over a variety of output values to get a stronger smoothing effect. This seems to give similar results to TRADES while cutting down the training time significantly (only two inner PGD steps).

Strengths:
- The paper is pretty clearly written, the results are impressive in terms of cutting down the training time of TRADES about 4x, and there are a substantial number of experiments, including fair comparisons with 2-step fast TRADES and on strong attacks. 
- Sometimes, the robust accuracy is even better than TRADES, but the clean accuracy is almost always a bit worse.
- They use many steps of PGD (100 steps) for robust accuracy evaluation.
- The method is relatively simple (similar mechanics to PGD), and uses only 2 inner gradient steps. It seems to give more stable results than fast AT or fast TRADES, although most of the stability gain seems to come from switching to the TRADES objective (Fig 5).

Weaknesses:
- My main concern is the backward smoothing method seems general but only really works for TRADES (and not PGD AT). The intuitions that motivate the method don't seem special to TRADES, so it would be good to have some understanding of this phenomenon. Can the intuition given in the paper be verified somehow? Also, other papers have shown that tweaking PGD-AT (such as using early stopping) allows it to get just as good or better results than TRADES, so it's not clear that we should necessarily prefer a method based on TRADES. 
- The authors mention the natural way to increase smoothing, which would be to use larger random perturbations. They argue that because of the norm constraint, we cannot increase the perturbations. However, even with the norm constraint it's clear that larger perturbations would not be the same as small perturbations, and could plausibly have a different effect. This point would be more convincing if there were some experiments just using larger perturbations for random initialization.
- Fast TRADES seems to be at a different point of the tradeoff curve between natural accuracy and robust accuracy, and perhaps it responds differently to the TRADES hyperparameter. From Table 2,3 etc. , we can see that Fast TRADES tends to improve natural accuracy and be worse than robust accuracy than TRADES. Could tuning the hyperparameter for Fast TRADES be enough to emulate the TRADES result?

Other/clarifications:
- Can the authors clarify how $\xi$ is initialized in eq 4.4? 
- Is there any insight to what differences between backward smoothing and TRADES are exposed with a stronger attack?
review_title: Review

Meta-review: This paper studies efficient robust training. The key idea is to use backward smoothing as an advanced random initialization to improve a model's adversarial robustness. The approach is sound, well grounded, and quite logical. Results demonstrate the effectiveness.

However, there exists some limitations:

1) Andriushchenko & Flammarion, 2020 gives a better and more fundamental explanation on how to address fast adversarial training.

2) Backward smoothing does not generalize to standard adversarial training. In other words, it only works for KL divergence loss rather than cross-entropy loss, and it seems that backward smoothing does not address the fundamental problem of fast adversarial training.

3) If we compare the performance of Fast TRADES and Backward Smoothing since Backward Smoothing intends to improve Fast TRADES, there is always a tradeoff between clean accuracy and adversarial robustness, e.g., Table 4 and Table 8. 

4) Randomized smoothing is helpful for one-step adversarial training and randomized smoothing in general seems to be orthogonal to the proposed method. Moreover, 2-step PGD training can perform similarly well to backward smoothing while being much simpler conceptually.

In the end, I think that this paper may not be ready for publication at ICLR, but the next version must be a strong paper if above limitations can be well addressed.
Decision: Reject