Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: **Contributions:**
This paper extends results on the implicit bias of gradient descent (GD) Soudry et al. (2018)[3] for the case of gradient descent based adversarial training (GDAT).

**1) Theoretical result for L2 norm:** Convergence of standard risk in GDAT is significantly faster than its counterpart in the standard clean training using GD: For any fixed iteration T, when the adversarial perturbation during training has bounded l2-norm, the classifier learned by GDAT converges to the maximum l2-norm margin classifier at the rate of O(1/√T), exponentially faster than the rate O (1/ log T ) obtained when training with only cleaned data Soudry et al. (2018) [3].

**2) theoretical result for Lq norm:** When the adversarial perturbation during training has bounded l_q-norm with q > 1, with a proper choice of c, the gradient descent based adversarial training is directionally convergent to a maximum mixed-norm margin classifier, which has a natural interpretation of robustness, as being the maximum $l_2$-norm margin classifier under worst-case $l_q$-norm perturbation to the data.

The paper is well written and easy to understand. I haven’t checked the proofs, but I focused on readability and motivations. 

I have the following questions.

**Theoretical questions:**
- Can you please explain the intuition of lemma 3.2 and 3.3 for convergence?
**Experiments questions:**
Keeping in mind that the core of the paper is about proving that GDAT enjoys the same implicit bias as GD and better convergence performance on clean data, I can’t help myself by asking you how these properties reflect in experiments with deep Neural Networks:
    - Can you please clarify your motivation for the reduction of the performance gap when the with of the hidden layer increases (Figure 2)? It is not clear what do you mean by ...“as network width increases, the margin on the samples outputted by the hidden layer also increases”...
My personal interpretation of the results is that the inner maximization problem is much harder to solve and being approximated, the effect of the GDAT is much less prominent, meaning that PGD is not enough to benefit from adversarial training in this sense. What do you think about it?
    - Take away message of the paper: adversarial training accelerates convergence. Theoretical results are for the training empirical loss.
Is this also the case of the validation loss? You observe this behavior for the case of a single MLP on MNIST binary problem 2 vs 9 (appendix E) claiming that adversarial training improves generalization performance.
This is not observed in the literature, it is actually the opposite [1, 2]: it exists a tension between robustness and performance on the clean test set. Why do you think you are not observing this? My guesses:
    - you are analysing a very simple binary problem
    - your model is very simple and comparable to a linear classifier, so your theoretical results hold.

[1][1805.12152 Robustness May Be at Odds with Accuracy](https://arxiv.org/abs/1805.12152)
[2][1810.12715 On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://arxiv.org/abs/1810.12715)
[3][1710.10345 The Implicit Bias of Gradient Descent on Separable Data](https://arxiv.org/abs/1710.10345)

review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: The paper studies the implicit bias of gradient based adversarial training for linear models on separable data with the exponential loss. Both l2 and general lq perturbations are studied.

For l2, the authors show that for small enough perturbations, the algorithm converges in direction to the max l2 margin solution, with faster convergence rates compared to standard gradient descent, both for the clean loss and the parameter direction (O(1/sqrt(T)) instead of O(1/log(T))).
For lq, convergence to a different max-margin direction is shown, given according to a mixture of the l2 and lp norms, though the parameter convergence is slower.
These results are further illustrated by numerical experiments.

The topic of the paper is novel and interesting, in particular the finding that adversarial training can lead to benefits in terms of optimization in addition to robustness, as well as the characterization of the inductive bias obtained when using lq perturbations in adversarial training (i.e. a mixture of lp and l2 norms, rather than just lp). Granted, the setting of linear models is a bit limited, but it provides a first step for more realistic models. The paper is also well written, and also has a nice numerical validation of the results. Overall, I am in favor of acceptance.

Here are some questions/comments that could be further discussed:
* for l2, while the obtained rates for parameter convergence are better in their dependence on T, they depend on a data-dependent quantity alpha in contrast to standard GD, suggesting that the rate could be worse for small alpha: is there a trade-off here? would standard GD be preferable if alpha is small, or could the current rate (7) automatically adapt to such settings?

* in Theorem 3.4, how does the choice of c come into play? can you obtain better rates by optimizing it (ideally this should happen when q=2)? Regarding the comment on tending to the lq-norm margin for c -> gamma_q, is this at the cost of poorer convergence?

* for lq perturbations, while I agree that the studied algorithm is interesting since that's what's used in practice for deep networks, I do wonder if in this specific setting you could get better convergence (and with the right norm lp instead of the mixture) by optimizing using the appropriate geometry, e.g. with mirror descent.

* the analyzed algorithm considers optimal perturbations -- do you have a sense of how robust the theory is to errors in the inner optimization?


minor comments/typos:
* second bullet in 'main contributions': 'mixed-norm margin' could be further explained, or at least point to the definition. The terminology is also confusing as it sounds like a matrix mixed-norm
* 'polyhedral cone ...': bar{u} should be u?
* after Theorem 3.2 'not an issue': not so clear, this should be discussed further (see comment above)
* section 3.2, "defer discussion for 1, infty": you could provide a flavor of the results for these cases in the main text, given their prominence in practice
* figure 1(b): for the direction plot, is it actually u_2? how should this plot be interpreted given that the two curves converge to a different direction?
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: The paper applies theory on implicit bias of gradient descent to an adversarial training toy example. It attempts to utilize the theoretical results for deriving insights on how adversarial training establishes robustness. The theoretical results are complemented with experiments on linear classifiers and small neural networks.

The key technical contributions look mostly like an application of the existing theory on implicit bias of gradient descent, thus I would rate the originality of this work as moderate. From the point of view of adversarial machine learning, I don't consider the results to be significant. In particular, there is a large discrepancy between the theoretical results on the toy example and the empirical convergence behaviour of adversarial training of neural networks (compare Figure 2 and 3). In particular, the theoretically derived exponential speed-up of adversarial training for the toy example is not reflected by empirical observations for practically relevant adversarial training tasks (e.g. consider the convergence behaviours reported by Goodfellow et al. (2014) or Madry et al. (2017)). Thus, the theory doesn't seem to be generally applicable beyond the linear toy model. A clear discussion of its limitations is missing.

Overall, while this may be an interesting extension of the existing body of literature on the implicit bias of gradient descent, I find that from an adversarial machine learning perspective this paper does not meet its objective to derive generally applicable insights on how adversarial training works. 
review_title: Official Blind Review #1

Meta-review: This paper provides theoretical guarantees for adversarial training.  While the reviews raise a variety of criticisms (e.g., the results are under a variety of assumptions), overall the paper constitutes valuable progress on an emerging problem.
Decision: Accept (Poster)