Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper is concerned with a uniform stability analysis of adversarial training, in order to gain a better understanding of the robust overfitting phenomenon.
To this end the authors introduce a class of $\eta$-approximately smooth functions, i.e., functions $h$ whose gradient is approximately Lipschitz continuous and satisfies
$$\|\nabla h(\theta_1) - \nabla h(\theta_2)\|\leq L \|\theta_1-\theta_2\| + \eta.$$
This is motivated by the fact that the adversarial loss $h(\theta; z) := \max_{\|z'-z\|\leq\varepsilon} g(\theta; z')$ is $\eta$-approximately smooth with $\eta=2 L_z \varepsilon$ where $L_z$ is the Lipschitz constant of $z\mapsto\nabla_\theta g(\theta, z)$.

The authors then prove bounds for the generalization and the optimization gap of stochastic gradient descent (SGD) applied to the adversarial risk for different assumptions on the loss function (such as different degrees of convexity). The most notable discovery is that the generalization gap after $T$ steps of SGD with learning rate $\alpha$ contains and extra term of order $L_z \varepsilon T \alpha$. The authors make the point that this explains robust overfitting since this term blows up for more and more SGD steps. This is also indicated by their numerical results.


strengths_and_weaknesses: Strenghts: 

The paper is structured in a clear way and the arguments are easy to follow. The analysis of gradient descent type schemes for $\eta$-approximately smooth functions is a valuable contribution on its own (at least I think its novel). The main strengths of the contribution are (1) a uniform stability analysis which depends on the adversarial budget $\varepsilon$ and extends to non-convex losses and (2) a theoretical explanation of robust overfitting.

Weaknesses: 

My main criticism is that the Lipschitz gradient assumption $\|\nabla_\theta g(\theta, z_1) - \nabla_\theta g(\theta,z_2)\| \leq L_z \|z_1 - z_2\|$ $\forall \theta$ with respect to the input variable $z$ seems very strong. Note that $L_z$ multiplies the adversarial budget $\varepsilon$ in the stability estimates. Standard network architectures are known to be very far from being Lipschitz continuous with a moderate constant. In the light of this, demaning uniform Lipschitz continuity of the loss w.r.t. $z$ appears to be questionable. This is particularly important since recently it was shown that adversarial training leads to a total variation regularization instead of Lipschitz regularization, see [1,2]. Hence, in practice such uniform Lipschitz continuity may get lost during the optimization. 
This issue requires some more explanations and justifications.
Besides that, the paper would benefit from a careful language revision.

[1] Finlay, C., Oberman, A. M., & Abbasi, B. (2018). Improved robustness to adversarial examples using Lipschitz regularization of the loss.
[2] Bungert, L., Trillos, N. G., & Murray, R. (2021). The geometry of adversarial training in binary classification. arXiv preprint arXiv:2111.13613.
questions: I have a couple of questions and remarks which should be taken into account for a revised version of the article:

- a short paragraph on notation would be good. In particular, you should remark that you use the Euclidean norm not any norm.
- Assumption 4.1: comment on the third assumption (see above)
- Lemma 4.2: the comments before and after the lemma are a little confusing: This lemma shows that the adversarial loss is $\eta$-approximately smooth and not that its not Lipschitz smooth. For this you would need a lower bound.
- Lemma 4.2: Why is $h$ differentiable with respect to $\theta$? A priori, this is not obvious due to the maximum in $z$.
- line 170: Calling (4.2) SUBgradient descent seems out of place. This is just stochastic gradient descent and the gradient is a proper gradient by your assumptions.
- line 198: did you mean to refer to Eq. (5.1) instead of (5.3)? 
- Corollary 5.2 basically shows that the inner maximization problem does not play a role at all in your analysis and you could just choose an arbtrary point which is $\varepsilon$-close to $z$. I suspect this is due to the strong Lipschitz assumption on the gradient of $h$ (see above). This should be pointed out.
- Theorem 5.3 should read: "IT exists a function h...", "THERE EXIST data sets S and S'..."
- line 223: Is the improvement from L (the $\theta$ Lipschitz constant of the loss) to $L_z\varepsilon$ really an improvement?
- line 223: I thought $L$ is the Lipschitz constant of the loss and not its gradient?
- lines 223-230: the language of this paragraph is clumsy and should be revised. 
- Theorems 5.4 and 5.5 have slightly different wording which is confusing. For instance, "we run SGD" versus "we run SGD on the adversarial surrogate". Are there different assumptions here? 
- Theorem 5.4: It should read $\alpha\leq 1/\beta$.
- Maybe formula (6.2) could be moved to the beginning of the article. It seems to contain the main contribution.
- Could one use a discrepancy principle (as used for variational regularization schemes to solve inverse problems) for the early stopping?
- lines 347-348: For small values of $\varepsilon$ I agree that the robust test accuracy seems to behave linearly in $\varepsilon$ but not necessarily for large values ($\varepsilon=10$).
limitations: The limitations of the assumption of an input-Lipschitz continuous gradients of the loss function should be discussed.

Negative societal impact is not to be expected.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: - The paper shows that the adversarial loss is approximately gradient Lipschitz, with the smoothness dependent on the adversarial perturbation size $\varepsilon$
- The paper derives an $\varepsilon$ dependent generalization bounds, and interprets the bounds to argue that overfitting is a result of the non-smoothness of the adversarial loss
- The paper analyzes common methods to mitigate adversarial overfitting to show that they are stability promoting
- Experiments on SVHN, CIFAR-10, CIFAR-100, Imagenet to verify the bounds
strengths_and_weaknesses: Strengths:
1. Good presentation, and explains necessary context/background well
2. Interesting result, and the paper provides a clear interpretation of it to explaining the robust overfitting phenomenon. The derived bound seems significant and is potentially useful beyond adversarial training literature. Very clear explanation of how this result compares to existing bounds
3. Section 6 provides interpretations of methods which have been shown to reduce robust overfitting - this part is quite interesting

Weaknesses:
1. The derived result doesn't seem to explain why robust generalization requires significantly more datapoints (compared to regular training), and why this reduces robust overfitting. It seems that the bound derived would imply that robust overfitting would occur at the same rate regardless of $n$. We understand that this is perhaps outside of the scope of the paper, however a mention of this missing piece might be helpful
2. A limitations sections explaining aspects of robust overfitting remain unexplained by this bound would be useful.
3. Experiments feel a bit rudimentary, i.e. it feels like the experiments section verifies already known results, without a real attempt at nitpicking/ablating the theory. The reviewer is unsure what experiments could be conducted to improve this section
questions: 1. See weaknesses 1, 2. Do the authors have opinions on this?
2. Does robust overfitting affect non-adversarial training based defenses such as randomized smoothing? Perhaps this could be useful evidence in support of the paper in case these other methods do face the same overfitting issue.
limitations: See weaknesses/questions section.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a stability analysis ( and the consequent generalization analysis) of adversarial training. In order to tackle the nonsmoothness of adversarial loss, it introduces the eta approximation smoothness as an analysis tool. It derives a better rate than prior works with new theoretical insights. 
strengths_and_weaknesses: The paper is well written and I believe it makes a good contribution to this line of research. 


questions: One suggestion is that the theory considers gradient descent of empirical adversarial loss, while in practice, the optimization is done by an alternative min-max type optimization. I wonder whether this gap is essential or not.
limitations: N.A.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the algorithmic stability of adversarial training. Compared to existing literature, it provides a better way to describe the smoothness of adversarial training, and obtain a more intuitive description on the algorithmic stability, convergence, and generalization error in adversarial training. Theorems and experiments are provided to justify their arguments.
strengths_and_weaknesses: Strengths:

[1] Different from existing literature, this paper provides another aspect of approximate smoothness to analyze the algorithmic stability of adversarial training. General results in algorithmic stability may not fit adversarial training very well, and this work overcomes this issue.

[2] This paper provides theoretical results in terms of algorithmic stability, generalization, and optimization, which together characterize the adversarial training process. The theorems are easy to understand. They also provide a lower bound result, which further strengthens their contribution.

Weaknesses: 

[1] Given a real data set, the relationship between \eps and \eta is fixed. Therefore, from the current experiments, it is not so convincing that the large generalization gap is caused by a large \eta. It would be great if the authors can provide some simulation studies to verify the relationship between \eta and the generalization when varying L and \eps. It would be even better if there is a simulation in other tasks rather than adversarial training to justify the relationship between \eta and generalization error.

[2] This paper does not provide enough new insights on how to improve adversarial training. For example, this paper argues the necessity of early stopping, but it is a known conclusion as in Bassily et. al. (2020). In Xing et. al. (2021), they consider the noise-injection method to improve robustness, which is beyond Bassily et. al. (2020) and particular for adversarial training. However, in this submission, the authors only mention some potential solutions without any strong evidence.

[3] This submission compares a lot with Xing et. al. (2021), and mentions a lot of weaknesses of that paper. However, after reading Xing et. al. (2021), my understanding is that they directly verify the effectiveness of the noise injection (optimal rate), so there is no need to work on a fine-grained analysis on a sub-optimal rate in their paper. Please tune your description when describing Xing et. al. (2021).



questions: Please help address my concerns in the weaknesses section.
limitations: NA
review_title: null

Meta-review: metareview: This paper uses uniform stability to study generalization in networks under adversarial training. The authors use their framework to understand robust overfitting: the phenomenon in which a network is adversarially robust on the training set, but generalize poorly. The theoretical results in this paper are backed up by experiments and applications to provide theoretical clarity to a number of common methods for reducing overfitting.

All reviewers supported acceptance of this paper. Reviewers enjoyed the exposition and writing, and found the theoretical developments and explanation of overfitting to be convincing. Finally, the reviewers liked the experiments backing up the theory and the practical applications.

confidence: Certain
Decision: Accept