Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper pays attention to the computation of adversarial training, by pointing out that even in the simple case (nonsmooth), the descent direction is not given by the worst-case perturbation, as opposed to common practice in the AT community. The paper then proposes a method that, under the assumption of a finite number of worst-case perturbations, computes the correct descent direction. 
strength_and_weaknesses: Strength:

I appreciate the conceptual idea of this paper a lot. The starting point of the paper is the observation that the descent direction not necessarily corresponds to the worst-case perturbation. Given the fact that this is typically assumed always be the case in the AT community, this paper has provided a refreshing perspective on how should we do AT correctly. The constructed counterexamples are also easy to understand. 

Weakness:

The potential downside of this paper is that the proposed method (DDD) is inherently computationally expensive. As the authors advocate the usage of multiple worst-case perturbations, adopting DDD would require at least several times of computational effort compared to the already expensive standard AT procedure. 

Another concern that I have is the similar final performance achieved by both AT and DDD. It seems that their performance differs by some margin only in the initial stage of the training, but is getting much closer to the final stage. This to some extent, has limited the potential practical impact of the proposed method. 



clarity,_quality,_novelty_and_reproducibility: Quality: 
The paper is very well written. Delivers a simple yet interesting observation clearly. The observation is to the best of my knowledge novel in the literature of AT. 

Clarity: 
The paper is well organized. The constructive counter-examples are well explained and the authors have done a good job maintaining their simplicity. 

Originality: The main claim and the proposed methods are novel. I appreciate the paper being bold and challenging the mainstream practices. 
summary_of_the_review: This paper focuses on the bring forward the issue that (a single) adversarial example might not give the descent direction, challenging a common belief adopted in the practice of this field. It did this with simple examples making its arguments. This is the strongest point of this paper. The proposed method, on the other hand, is computationally expensive compared to the original AT, and the final performance is comparable to AT, which is to some extent surprising given the fact that AT is supposedly not a correct method, the main theoretical claim made by this paper. The practical side of the claim and method proposed in this paper seems a little bit limited by its current shape.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper points out an issue in a recent theoretical result that motivates the adversarial training algorithm. The authors construct counter examples and provide explanations about the issue they identify, and then further propose a Danskin's Descent Direction for training robust neural networks.
strength_and_weaknesses: Strengths: 

The claims of the paper seem solid, and the paper is well written. 

The proposed method is backed up by experiments.

Weaknesses: 

Theorem 2 is based on the assumption that the set of optimal adversarial perturbations is finite. This is a strong and sometimes unrealistic assumption.

According to the authors' discussion, it seems that Madry et al. (2018, Corollary C.2) could be made rigorous by adding an assumption such as "$\phi(\theta)$ is differentiable at $\theta$". Even with this additional assumption, this result seems sufficient to motivate the adversarial training algorithm. 

Because of the above reasons, the advantage of the proposed DDD method over the adversarial training method is not very clear. After all, the theoretical guarantee for the proposed DDD method (Theorem 2) is also based on an unrealistic assumption. The DDD method also seems to be computationally more expensive than adversarial training. 
clarity,_quality,_novelty_and_reproducibility: The paper is written clearly and the results are novel.
summary_of_the_review: This paper points out an important issue in adversarial training. The paper is well written and the claims seem solid. However, the proposed method is still questionable and more justification is needed to demonstrate its advantage over existing methods.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: The starting point for this paper is the observation that one of the key theorems in (Madry et al., 2018) is incorrect.  In particular, the authors show that the interpretation of Danskin's theorem in (Madry et al., 2018) uses the incorrect form of the directional derivative.  They provide several counterexamples to demonstrate this flaw, which yield interesting insights on the problem of adversarial training.

Based on these observations, the authors propose Danskin's Descent Direction (DDD), an algorithm that is designed to solve the standard minimax formulation of adversarial training.  They show that their method is more stable than PGD on several benchmarks, although the empirical gains are somewhat modest at convergence.  
strength_and_weaknesses: ### Strengths

**Soundness.**  This paper seems to be technically quite sound.  It is certainly the most rigorous paper that I have reviewed in my batch of papers this year at ICLR.  The analysis of Danskin's theorem and of the result in (Madry et al., 2018) appears to be correct, which indeed calls into question one of the foundational assumptions underpinning adversarial training.  

The counterexamples shed new light on the problem as well.  I particularly appreciated the fact that after disproving the theorem from (Madry et al., 2018), the authors took it one step forward.  They ask: In the case when I'm not at a locally optimal point, is the result of (Madry et al., 2018) still incorrect.  And via a more intricate, although still pleasingly elementary, construction, they show that another counterexample exists.  This is thorough work, and I believe that it should be commended.

**Algorithm.**  The algorithm proposed by the authors seemed relatively natural.  While it is clearly up for debate whether the set of maximizers is finite, I think it's not an unreasonable assumption to make.  And the authors provide some nice empirical evidence that at the very least, the set is not a singleton.  Given this, Thm. 2 makes sense given the context of the paper, and it leads to a relatively practical algorithm.  Nice!

**Well written.**  This paper is relatively well written.  The related work was thorough.  And in general, the logic and flow of the paper was solid.  I really enjoyed reading it!

### Weaknesses

**Minor inconsistencies in notation.**  One point of confusion: if $\delta\in\mathbb{R}^p$, then $\mathcal{S}\subset\mathbb{R}^p$ in (1).  In (2), we have $\delta_i\in\mathbb{R}^p$, and therefore $\delta$ seems to be an element of $\mathbb{R}^{p\times k}$, meaning that $\mathcal{S}\subset \mathbb{R}^{p\times k}$ (or perhaps of $\mathbb{R}^{pk}$).  This is a bit inconsistent, as it would be nice to think of $\mathcal{S}$ as belonging to a particular space.

**Confusing presentation of the key theorem.**  One key step of this paper is to present the theorem of (Madry et al., 2018), which is done in Corollary 1.  Before presenting this result, the authors say that

> "Corollary 1 is an equivalent rephrasing of Madry et al. (2018, Corollary C.2.), and is derived as a consequence of Theorem 1. 
 Unfortunately counterexample 1 shows that it is false:"

Let Thm. 1 (Danskin's theorem) be A and let Cor. 1 be B.  Based on my reading, this sentence says that A implies B, since "derived" (to me) means "correctly derived."  The authors then say that B is false.  By the contrapositive, this would imply that A is false.  Based on the rest of the paper, I know that this is not what the authors are trying to say.  So I would suggest rewording this part to emphasize that A does not imply B, as some readers may get confused by this point, and that is quite undesirable given that this is one of the most important points in the paper.

I would also recommend defining a "descent direction" before it is mentioned in Cor. 1.  This would make it easier to understand the result in Cor. 1 without having to read on until a later section.  

**A minor recommendation.**  I would recommend removing the phrase: "a basic concept in multivariable calculus."  This may only be my opinion, but I feel that this phrase may be perceived by some readers as a little bit disrespectful to (Madry et al., 2018), especially given that (Madry et al., 2018) is a relatively influential paper.  Yes, this idea is often introduced in a college-level calculus course.  But it took until now for anyone to notice this subtle distinction. 

**Explain Madry et al.'s results in more detail.**  I think it's well worth spending more time on the results of the original paper.  The discussion at the bottom of page 3 is relatively terse.  In particular, I believe that it would be beneficial for the authors to expand on the sentence:

> "However, we cannot guarantee that the function will decrease if we move in the opposite direction..."

During my first pass through the paper, I didn't understand this part.  Underscoring the fact that Madry et al. assume that $D_\gamma \phi(\theta) > 0$ *implies that* $D_{-\gamma} \phi(\theta) < 0$ is essential here, because it is at the heart of why the original result was not correct.  It may be worth proving that for the two-sided directional derivative, this property does hold.  Although elementary, I think this would help build intuition for the reader.

**Oracle?**  I didn't understand what the authors meant by a "heuristic oracle."  The word "heuristic" seems to defeat the purpose of an oracle.  Could the authors explain more here?

**Computation time.**  A downside of the proposed method is obviously the computation time.  It seems clear that at convergence, DDD doesn't offer a significant improvement over PGD given that it seems to get 10x more steps.  I may have missed this, but did the authors compare PGD-100 to DDD-10, which would constitute a comparison where each algorithm got roughly the same computational budget?
clarity,_quality,_novelty_and_reproducibility: **Clarity.**  The paper was easy to read.

**Quality.**  The results were technically sound, and the experiments were thorough.

**Novelty.**  The algorithm seems novel, and this work offers a fresh perspective on adversarial training.  

**Reproducibility.**  This seems relatively easy to reproduce based on the details given in the paper.
summary_of_the_review: Overall, I thought this was a really solid paper.  It makes some interesting insights, and the result is an algorithm that seems to have some nice empirical properties.  There are a few drawbacks, such as the increased computation time.  Most of the weaknesses listed above are relatively minor.  Therefore, I think this paper should be accepted.

---

**Post rebuttal comments.**  The authors have addressed each of my concerns.  Therefore, I will raise my score, as I believe that the additional clarifications and theoretical results improve the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors point out that the interpretation of Danskin's Theorem that was used to motivate the Adversarial Training paradigm in the seminal paper from Madry et al. (2018) relies on a misunderstanding of the notion of directional derivative employed in the theorem. As a consequence, PGD, the most commonly employed adversarial training scheme, might not follow descent directions. The authors present a solution to this, assuming finitely-many global optimizers of the inner maximization, and show that it helps in practice in setttings where Danksin's Theorem would hold.
strength_and_weaknesses: The authors raise awareness about a mistaken interpretation of Danskin's Theorem when motivating adversarial training, and demonstrate its relevance through counter-examples and empirical evidence. A solution to this problem is presented (DDD), and its relative effectiveness on smooth networks (without BatchNorm) is shown. 
At this stage, the contribution is purely technical: the practical relevance of the presented method is limited because of its inferior performance in the setting that attains the maximal robust accuracy (ReLU + BatchNorm). Furthermore, DDD greatly increases the runtime per iteration, making its practical employability limited.
Nevertheless, I believe the findings to be of great interest to the community. 

In my opinion, the strength of the paper could benefit if the authors addressed the following limitations:
- Typically, in the context of adversarial training, the inner maximization is not run to convergence. Indeed, this holds also for the presented experiments. Therefore, DDD is not guaranteed to yield a descent direction for the robust loss even when the conditions of Danksin's Theorem hold. It would be important for the authors to comment on why DDD helps in this setting. Indeed, getting to a guaranteed global optimum of the inner maximization would require running a complete verification algorithm based on Branch and Bound (it would be nice if the authors touched on this, and mentioned relevant methods in the literature). 
- Practical limitations (in practice the overall best-performing method remains PGD) should be stated in intro and abstract (as the authors do in the conclusions) . The statement on the early stages should be limited to the smooth setup (the difference in Figure 4b seems to be too small to be statistically reliable).

As a minor point: why not Frank-Wolfe for the smooth simplex-constrained optimization problem that arises from DDD?
Finally, the fact that the inner maximization in AT is not run to global optimality would be visibile if the authors provided a magnified version of the high-loss region of Figure 2.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, the content is well-presented and organized. To the best of my knowledge, the problem the authors point out is not well-known in the adversarial training literature, for which the presented solution is novel.
summary_of_the_review: The authors point out an interesting problem in the adversarial training literature: while the practical effectiveness of the presented method is limited at best, and the presented solution is never used in the setting for which it is motivated (the inner maximization is never run to convergence, as that would require running formal neural network verification), I believe the paper is a first step towards more principled adversarial training algorithms.
Nevertheless, the authors should be more direct about the limitations of the proposed solution and its empirical relevance, from the beginning of the paper. I will be willing to increase my score after this and the other weaknesses I pointed out are addressed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper points out an error in the justification of adversarial training using Danskin's theorem when the inner maximization problem has no unique maximum. In this case the negative gradient computed at a particular local maximum need not be a descent direction. The authors illustrate this with examples and provide a new algorithm which is computationally much more expensive.

Strength:
- revealing a wrong argument in the original justification of adversarial training
- provide a fix under the assumption that the set of maximizers is finite
- they show (new theorem 3) that this fix still works for approximate maximizers which "cover" the set of potentially infinite maximizers

Weakness:
- as the authors admit, the results are well-known in the optimization community, so in that sense the result just fixes a wrong argument in a well-known paper
- the suggested alternative DDD is significantly more expensive than adversarial training
- the new method cannot outperform PGD based adversarial training

All reviewers support acceptance, in particular after the authors added the improved result of Theorem 3. While at the moment this paper mainly is a fix to a wrong argument in a well-cited paper, it could inspire subsequent work to improve or better understand adversarial training and thus this is a clear accept.

Detailed comments:
- I could not find details on the computation of robust accuracy, in any case I suggest to use strong attacks like AutoAttack to evaluate the curves in Figure 5 so that there is no doubt that the advantage of DDD is only an evaluation artefact


justification_for_why_not_higher_score: There is no apparent practical impact of this result yet and the results are known in the optimization community.
justification_for_why_not_lower_score: The paper fixes an error in the justification of adversarial training, which is the main technique to achieve empirical adversarial robustness. Thus this paper contributes to the foundations of this field.
Decision: Accept: poster