Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The main result of the paper is an upper bound on the Rademacher Complexity of neural networks in the case of adversarial examples (meaning, analyzing it with respect to the robust loss class).

Previous bounds for linear classifiers and shallow neural networks were investigated by Yin et al. (2019) and Awasthi et al. (2020).
The known methods for upper bounding the Rademacher Complexity for deep neural networks in the standard case don't apply in this case.

The main idea in this paper is to analyze the covering numbers directly (as opposed to calculating them by induction on the layers).
 
main_review: The question investigated in the paper (described above) is natural and was posed as an open question by previous papers.

The main technique seems reasonable. 

The experiments suggest that the change in the margin and the product of the weight norm may explain the larger generalization gap  (compared to the standard generalization).

Weakness: showing a depth/width-dependent lower bound could have been nice.

-Citing the paper https://arxiv.org/pdf/1810.02180.pdf (ALT19 and JMLR) is very relevant in the section "Adversarial Generalization".
It provides uniform convergence results In the case of a finite number of perturbations for a mixture of classifiers. The analysis goes through the Rademacher complexity as well.

-In section 3: d^2 should be 2^d?
summary_of_the_review: I recommend accepting the paper.

I read the overview of the main proof, but not the fully detailed proof.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors developed an upper bound of adversarial Rademacher complexity, which includes the product of weight norms. This implies that the large weight norm hinders from achieving good generalization performance in adversarial. The authors also empirically show that the product of weight norm in adversarial training is indeed much larger than that in standard training. 
main_review: Strengths: 
1.	This paper provides new bounds for adversarial Rademacher complexity. 
2.	This paper is well written and easy to read.

Weaknesses: 

The empirical validation in this paper seems insufficient:

1. Although the authors verified that the product of weight norm in adversarial training is indeed much larger than that in standard training, I think this is not a strong empirical verification of the proposed bound. The reason is there existing some constants in the bounds in adversarial training and standard training, which may be different. Therefore, simply comparing the product of the weight norm is not rigorous. I would like to see more discussion on this. We know that some of the existing deep learning theory may be only mathematically correct, thus providing sufficient empirical evidence to show the consistence between the theory and practice is important. 

2. There exists a product of the weight norm in the proposed bound, which implies that the trained model can generalize better if this product is smaller. Therefore, can we use some techniques to regularize this product during training to improve the generalization ability. The authors are recommended to give such kind of experiments to support their theoretical results. 

====after rebuttal===

After reading the response from the authors, I raised my rating. 
summary_of_the_review: 1. This paper provides a new complexity bound for adversarial training. 
2. The empirical validation of this paper is insufficient.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes new generalization bounds for adversarial training in neural networks based on the Rademacher complexity. These are more general than previous results in that they apply to neural networks of any depth. Experiments are performed on CIFAR-10 and CIFAR-100 with multiple VGG architectures. These, related with the main quantities appearing in the proposed bounds, provide an explanation for the limited generalization capacity of adversarial training.
main_review: Strengths:
- Relevant topic of theoretical investigation of adversarial examples and adversarial training, that has gained traction in recent years.
- Improved theoretical result over prior art.
- Meaningful experiments based on the theoretical results, that suggest some reasons why adversarial training does not generalize well.
- Clear and well-written paper (a few typos remain).

Weaknesses:
- It would be great if the paper included a comparison to existing adversarial bounds based on Rademacher complexity or other frameworks, e.g., plotted for a toy example or small network. Lacking this, it is harder to judge the improvement the current paper makes over prior results in terms of tightness of the bound. Moreover, it might be worth comparing the contribution to other types of theoretical approaches in the field, e.g., the provable methods that the paper cites.

Questions and other comments:
- It would be good to underline that the bounds provided also hold for convolutional neural networks earlier than the experiments section (or, more generally, what layers are covered).
- What is the impact of using PGD adversarial examples in practice instead of the optimal perturbation?
- Is it reasonable to consider a loss in the range 0-1 for neural networks?
- Are Rademacher complexity bounds tight enough for neural networks to be informative or applicable in practice?

[Update post discussion] I am raising my rating by one point, following the exchanges below.
summary_of_the_review: Good theoretical result supported by experimental evaluation on relevant topic.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper overcomes some technical difficulties to provide adversarial Rademacher complexity of deep neural networks. Compared with existing literature which try to show other variants of adversarial Rademacher complexity, this paper directly works on adversarial Rademacher complexity itself. This paper provides both the lower bound and the upper bound. Besides, this paper conduct numerical experiments to combine with the theoretical bound to justify why adversarial training has a worse generalization than standard training.
main_review: I think the main contribution of this paper is interesting. It directly overcomes the difficulties in deriving adversarial Rademacher complexity rather than using other variants. It provides both the upper bound and lower bound, both of which are important. 

However, there are still a lot of things that can be improved in this paper. Below are my major concerns towards this paper (ordered in importance). My rating is currently weak accept given the importance of the upper and lower bounds, but it could be adjusted based on the author response towards my concerns. 

[1] My understanding towards the adversarial training and the adversarial Rademacher complexity is that, both adversarial-trained and standard-trained neural networks have their own standard Rademacher complexity and adversarial Rademacher complexity. So "the generalization gap of adversarial training loss and adversarial testing loss" is larger than "the generalization gap of standard training loss and standard testing loss" for both adversarial-trained (denote as A and B) and standard-trained neural networks (denote as C and D), i.e. A>B and C>D. On the other hand, through experiments, it is observed that the adversarially trained neural networks obtains larger norms, so its generalization is worse, i.e. A>D. Is my understanding correct? Is it essential to provide evidence for A>C or B>D in other to conclude A>D? In Figure 1, what does the "generalization gap" refer to?

In addition, could you provide some insights on why the norm of adversarially trained model is larger? Why does increasing the samples size lead to a larger norm/margin? Also, given these observations, is there any way to improve the generalization performance of adversarial training? Is there any implications on the loss landscape of adversarial robust neural networks? The current Section 6 displays some observations but no detailed insights.

[1](as important as the above) The current proof of Theorem 3 only says "By the results of the lower bounds of ..., we obtain that ...". Please provide more details on the existing results and how to obtain the final result. Please provide some concrete illustrations to this either in pdf or in the discussion. 

[3] The literature review of generalization of adversarial training in this paper only considers those about Rademacher complexity. There are many other studies working on the generalization from other theoretical aspects. Below are some important articles. Please do some literature research in this general area of theoretical study and include in this paper.

-----------------Papers which provide both upper bound and lower bound-----------------

Dan, Chen, Yuting Wei, and Pradeep Ravikumar. "Sharp statistical guaratees for adversarially robust gaussian classification." International Conference on Machine Learning. PMLR, 2020.

Xing, Yue, Ruizhi Zhang, and Guang Cheng. "Adversarially Robust Estimate and Risk Analysis in Linear Regression." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

-----------------Papers about generalization properties-----------------

Allen-Zhu, Zeyuan, and Yuanzhi Li. "Feature purification: How adversarial training performs robust deep learning." arXiv preprint arXiv:2005.10190 (2020).

Javanmard, Adel, Mahdi Soltanolkotabi, and Hamed Hassani. "Precise tradeoffs in adversarial training for linear regression." Conference on Learning Theory. PMLR, 2020.

Javanmard, Adel, and Mahdi Soltanolkotabi. "Precise statistical analysis of classification accuracies for adversarial training." arXiv preprint arXiv:2010.11213 (2020).

Taheri, Hossein, Ramtin Pedarsani, and Christos Thrampoulidis. "Asymptotic behavior of adversarial training in binary classification." arXiv preprint arXiv:2010.13275 (2020).

Wu, Dongxian, Shu-Tao Xia, and Yisen Wang. "Adversarial Weight Perturbation Helps Robust Generalization." Advances in Neural Information Processing Systems 33 (2020).

Xing, Yue, Qifan Song, and Guang Cheng. "On the Generalization Properties of Adversarial Training." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

Zhai, Runtian, et al. "Adversarially robust generalization just requires more unlabeled data." arXiv preprint arXiv:1906.00555 (2019).


[4] The main idea of this paper is not hard to follow, and the authors make a lot of comparison to existing literature. It would be great if the authors could make it clear about the following questions when describing the proof steps in Theorem 1:

   (1) Which steps are different from the derivation of standard Rademacher complexity? Which steps are not essential? If we use Theorem 1 and take \epsilon=0, what steps should we modify to obtain the standard Rademacher complexity mentioned in Section 5.3?

   (2) Which steps are different from the literature about adversarial Rademacher complexity? Which steps do they skip?

   (3) Could you explain the remark after before Theorem 2 in detail?



Minor issue (not ordered in importance):

[5] When mentioning your contributions in the last paragraph of Section 1, could you write some descriptions? 
    (1) For the first contribution, is there any interesting findings in the bound?
    (2) For the second contribution, could you answer your why question? 

[6] Please consider remove Proposition 1 and 2, and move Proposition 3 to the appendix. Proposition 1 and 2 do not help deepen the understanding of the main goal of this paper. Similarly, please shorten Section 3 for inequalities which are unrelated to the main goal. 


summary_of_the_review: This paper provides some important results about the adversarial Rademacher complexity so I vote for weak acceptance. But there are many issues towards the experiments, proofs, and the writing of this paper.
review_title: null

Meta-review: The paper made a solid theoretical contribution on the adversarial  generalization bounds of multi-layer neural networks.

However, the paper, at the current form, has many issues in the claim that "the product of the norm can explain the generalization gap":

(1). Weight decay. The authors uses the weight norm as the proxy for generalization gap, however, it is unclear to me that "adversarial trained networks have a larger generalization gap" can be explained by the product of weight norms. To carefully verify this, the authors have to at least carefully tune the weight decay, to the largest possible extend so the generalization error is not hurt, and compare the product of the weight norms in this scenario.  Without weight decay, the neural networks might learn a lot of redundancies in the weights (especially with adversarial training)  which makes the product of the norm to be too large. 

The authors do perform experiments showing that with weight decay, the generalization gap becomes smaller and the norms become smaller, however, it is totally unclear to me that the weight decay considered in the experiments are actually optimal -- It could still be the case that with proper weight decay, the product of the norms in adversarial training is actually smaller comparing to that of the clean training. 


Moreover, the authors should also clarify that **the product of the norms, according to the experiments, are simply too large and they can not be used in the theoretical result to get any meaningful generalization bounds**.



(2). The product of the norm in Rademacher complexity  is tight: This  claim only holds for neural networks with 1 neurons per layer. Once there are more than one neurons, there can simply be one neuron that learns f(x) and the other learns -f(x) and they completely cancels each other. So the product of the norm is obviously NOT TIGHT for any neural network with MORE than ONE NEURON per layer. In fact, the gap can be INFINITELY large. 


Unfortunately, I like the paper very much and I hope this paper could be published, however, the claims  "the product of the norm can explain the generalization gap" is simply too misleading and ill-supported. I encourage the authors to completely remove this claim and submit the paper to COLT.
Decision: Reject