Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: The aim of this paper is to provide a theoretical analysis of adversarial training under the linear classification setting. The main result states that, under many technical assumptions,  adversarial training using gradient descent may converge to the hard margin SVM classifier with a fast rate. Here "fast" is not the standard 1/T fast rates but, rather, a rate of o(1/log T) (in comparison to recent results that looked into the convergence of gradient descent with logistic loss to the hard-margin SVM solution).

Overall, the paper is not recommended for publication for many reasons. 

First, the notation used is sometimes imprecise and in some cases it is entirely wrong. For example, the authors decided to use x_i to replace the product y _i x_i in order to "simplify" notation. This makes things really hard to follow. The authors need to use a different symbol, such as z to stand for the product yx. Second, some equations do not appear to be correctly typed (e.g. in Page 1, standard learning should have xi not x). Third, the authors use epsilon to denote two different things (one for the definition of linearly separable data and one for the robustness radius), and so on. 

Second, the paper needs to be proof-read. It has a lot of typos and grammatical errors that make sentences difficult to understand. Examples include: 
- "while there several outliers are not or even not linearly separable", 
- "a simple generalization error bound informs the high loss on test set"

Third, some of the mathematical results do not make sense. For example,  Definition 1 has two conditions, the first one is immediately satisfied once the second condition is satisfied, so why both? Also, in Proposition 1, the authors should mention that both sets are subsets of a linearly separable superset. In that case, the conclusion of Proposition 1 is obvious. Definitely, if data are linearly separable, then the hard margin will shrink as more examples are added (it cannot increase by definition of "maximum" margin). Moreover, in Example 1, the authors conclude with an inequality of norms and I don't see how this follows from the description of the example. The example is generic and there is nothing that indicates one norm would be larger than the other. 

Forth, the authors make many assumptions about the loss without mentioning one example that satisfies them. In fact, the loss function they used later in the experiments violates Assumption 2.

Some additional comments: 
- How did the authors arrive at Eq 4? I don't see how this follows from the assumptions. Can you please elaborate? 
- I am not aware of any book written by Vapnik in 1995 called "Convex Optimization". I think the authors meant the SVM paper. 

Given all of these issues and the fact that the main result is incremental and holds under a very limited setting (homogenous linear classifiers under a strong separability assumption) and relies on very strong assumptions about the loss function that may not be achievable to begin with, I do not recommend acceptance. 

=========== 
#Post Rebuttal Remarks

Regarding the rate of convergence, just to be clear, I was only clarifying what the term "fast" meant in the paper, not complaining. So, this did not affect my score. The notation issues need to be fixed and the authors need to ensure that mathematical equations are written precisely, as stated in my review. 

Thanks for clarifying the issue about the loss functions. I agree that the example they mentioned satisfy it but it is not a common loss used in practice.
review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: This paper provides some analyses of the difference between adversarial training and standard training for linear classification problem. In particular, it proves that when the data is \eps linearly separable, adversarial training converges faster than standard trading. It also argues that when the data is not \eps linearly separable, adversarial training is more robust to outlier. Simulations are constructed to verify the arguments in the paper but there is no experiments on real dataset. 

The first result of this paper is interesting, that adversarial training converges faster than standard training. Studying the difference between the convergent points between adversarial training and standard training is also an interesting research problem. However, I still have two main concerns about the current version of the paper.
1. The paper is trying to develop rigorous results, but its writing is arguably not rigorous. Many statement are not clear and some notations are used without definition. Section 4.1 has many vague statements. See more concrete comments below. 
2. I am not sure about the significance of the results in the paper. The results highly depend on the linear setting with convex losses. More than that, Theorem 1 assumes the \eps strongly linear separable, and Theorem 2 assumes a large \eps (if the statement is that |w* x_{k,i}| is less than a large number, it seems much less interesting). These are very strong assumptions that are usually not true in practice. Experimental results only cover carefully designed simulation as well.

Detailed comments for item 1 above:
1. Assumption 3, what is the quantifier for w? Is it for every w? There exists some w? How do you guarantee by “rescale the norm of w” (from the footnote) to make sure that c_1 is not -\infty?
2. Lemma 1, this is for every x_i, or some particular x_i?
3. What is w(t)?
4. What is the condition on \eta in Theorem 1? Why it is O(\eta) in equation (11) or equation (24)?
5. The claims in section 4.1 seem to be depended on carefully designed examples. Would it still true rigorously for general cases? 
6. In section 4.1.2 first paragraph, why ||w_t|| can not go to infinity? in the third paragraph, how assumption 2 implies p^k_i / p^k`_j = o(1), or later  p^k_i / p^k`_j = O(1)?
7. In section 4.2 second paragraph, what is “k_th category”?
8. Is w^* unique in Theorem 2?

review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: TL;DR: The paper gives interesting, theoretical results to adversarial training. The paper only uses linear classifiers, which are hardly the same problem as deep networks where adversarial attacks are problematic. Some conclusions from theorems can be vague or informal, and therefore are not very convincing. I vote for rejecting this paper since it is hard to claim it informs deep learning research (the motivating reason for doing adversarial training). However, I am not familiar with theoretical analysis of adversarial attack/defense, so I am open to counter-arguments.

=================
1.    What is the specific question/problem tackled by the paper?
The paper gives a theoretical analysis to the theoretically less-studied procedure of adversarial training, and shows properties of adversarial training in comparison to regular training, for both linearly separable data or inseparable data. The paper sheds light on some empirical behavior of adversarially trained networks, namely that they are more robust to outliers and lower in performance.

2.    Is the approach well motivated, including being well-placed in the literature?
I am not an expert of adversarial samples, so I am ill-equipped to judge the novelty of the paper. The research direction itself is well motivated, and in the realm of deep learning, it is posed as a first paper to theoretically analyze adversarial training.
However, the authors only analyzed linear classifiers. This makes the results of the paper ill-suited for deep networks, whose non-linearity is arguably the reason why adversarial samples are such a problem. The motivation of the paper is thus greatly diminished. For linear classifiers, I do not know if there are existing work on their robustness when perturbation of samples are being trained on, but to be well-placed in the literature, the authors must either claim there is none, or cite those papers.

3.    Does the paper support the claims? This includes determining if results, whether theoretical or empirical, are correct and if they are scientifically rigorous.
Claims and novelties in this paper include:
(1) Adversarial training converges faster than regular training if samples are ε-strongly linearly separable,
(2) If samples are not "ε-strongly linearly separable", adversarial training is robust to outliers, while regular training is not,
(3) Confidence is low for all (training) samples if ε is large. 

Only (1) seems to be sufficiently proved. I am not certain that this is a very useful result, and I am open to counter-arguments.
(2) and (3) have steps that are vague and informal:

(2) That regular training is susceptible to outliers is proof by example and people already know that. Also the claim relies on the assumption that pi^1 and pj^2 are on the same scale, while those samples that violate the decision boundary can have arbitrarily large pi^1 or pj^2. Since outliers are often the violators, and inliers often are not, a small number of carefully placed outliers can make ||p2|| quite large while each pi^1 can be very small. It is also worth noting the logic seems to boil down to "N1>>N2, so inliers should overwhelm outliers, making the training robust". The claim is not guaranteed.

(3) I am not very sure if I understand it correctly, but the logic seems to be that the logits are bounded, so they cannot be too large, and so the confidence is low. However, the bound also involves the magnitude of w and x from the other class, so the final step of the proof is either unclear or the bound can indeed be quite large. Note that |wx| does not need to be very large for the confidence to be high (e.g. if logit is 5, the confidence is 1/(1+e^-5)=99.3%). The claim also relies on the assumption that epsilon is larger than the distance between the farthest points in the dataset, which is extreme since you can find an adversarial sample that can be considered to be simultaneously "close enough" to the two most dissimilar samples in the dataset.

In the end, the results are not very convincing or useful for informing deep learning research.

=============
To improve paper:
- Clarify motivation and how this would inform adversarial training highly non-linear classifiers;
- Add related work for robustness to perturbation of linear models, or state that they don't exist;
- Clarify weaknesses in the claims.

Editorial changes:
Definition 2: "logit" <--- people call this probability estimates; logits are wTx
Sec. 4.1.2 needs to clarify what k in x_i^k means -- it's continued from proposition 1 which at first glance is irrelevant


=================
Post rebuttal

Apologies for not interacting earlier due to deadlines. 
The rebuttal does not address my major concern (motivation), nor does it discuss its relationship with related work. The math questions are not answered very clearly; I do not see how section 4.1.2 proves p_i^1 has the same scale as p_j^2, except maybe that they are all smaller than some constant for certain samples. And other discussions in the rebuttal simply confirms my concern. 
In summary, I think this paper is not yet ready for publication.


review_title: Official Blind Review #3

Meta-review: This paper studies adversarial training in the linear classification setting, and shows a rate of convergence for adversarial training of o(1/log T) to the hard margin SVM solution under a set of assumptions. 

While 2 reviewers agree that the problem and the central result is somewhat interesting (though R3 is uncertain of the applicability to deep learning, I agree that useful insights can often be gleaned from studying the linear case), reviewers were critical of the degree of clarity and rigour in the writing, including notation, symbol reuse, repetitions/redundancies, and clarity surrounding the assumptions made.

No updates to the paper were made and reviewers did not feel their concerns were addressed by the rebuttals. I therefore recommend rejection, but would encourage the authors to continue refining their paper in order to showcase their results more clearly and didactically.
Decision: Reject