Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied the generalization performance of adversarial training from the stability perspective. They first derived the minimax lower bound of generalization gap for convex Lipschitz functions, which identifies the gap compared to existing generalization results of SGDmax; then authors proposed Smoothed-SGDmax which shares the same convergence guarantee while achieves the aforementioned (vanishing) minimax lower bound, i.e., fix the gap.
strength_and_weaknesses: Strength:
1. The paper is well-written and the flow is clear
2. The proposed algorithm successfully overcomes the nonvanishing generalization errors in existing SGDmax results, while still share the same convergence guarantee

Weakness:
1. The tools in algorithm building are not that novel.
2. The problem setting is the convex regime, which is a bit restricted (to be a bit picky)
clarity,_quality,_novelty_and_reproducibility: I think the paper is well-written and easy to follow. The results concern both lower and upper bounds, which reveals both novelty and significance.
summary_of_the_review: Generally I don't have immediate questions to ask.

Some typos:
1. Theorem 4.2, $\alpha_t$ and $\alpha$, do you suggest that you are always using constant stepsize $\alpha_t\equiv\alpha$?
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies the effect of using adversarially robust on generalization
error.  In particular they show that the generalization error achieved by
SGDmax contains a constant term that does not tend to 0 as the sample size
increases.  They show that they can remove this constant term in the error by
using a smooth variant of SGDmax.


strength_and_weaknesses: Strengths

1. The paper studies the important and well-motivated problem of adversarial
training and proposes a new method that improves generalization.

Weaknesses

1. The paper is hard to parse and follow and there are numerous typos and
inconsistencies in the notation.  One of the main results of this work (Theorem
4.1) seems to be a direct corollary of prior work but still the proof provided
in Appendix A.1 is hard to follow.

2. I did not find the Smoothed-SGDMax method proposed by the authors
particularly novel since approximating non-smooth terms with their
corresponding Moreau envelopes is pretty standard.


Typos and other Issues

Theorem 4.2 does not show that SGDmax does not achieve the minimax lower bound.
It only gives an upper bound for the generalization error of SGD that does
not match the lower bound of Theorem 4.1.

Page 2, next to Figure 1. "By contrast, Our approach"

Page 3, First paragraph of Related Work. "This has led to a series of work aimed at training..."

Page 13, Proof of Theorem 4.1. "Where $C_4$ is a universal constant". There is no constant $C_4$ in the expression (A.2).

Page 13, Proof of Lemma 5.1. The sentence in Element 1 of the proof does not parse.

Page 13, "Then, take the derivative of $M(u)$ with respect to $u$, we have"


clarity,_quality,_novelty_and_reproducibility: The paper is clearly not well-written.  I recommend that the authors carefully
proof-read the manuscript and fix the various typos and issues in notation.
summary_of_the_review: Overall, I found the paper not well-written and I believe that it would benefit
a lot by careful proofreading. I do not think that in its current state this
work is ready for publication.   Perhaps after a revision, the contributions of
this would also become clearer.  Given the fact that the paper is not
well-written and the contributions do not seem very exciting, I am currently
inclined towards rejection but I am willing to reconsider if the authors and/or
other reviewers can prove otherwise.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors investigate the generalization error in optimizing the expected adversarial loss. They utilize the generalization-optimization decomposition and techniques from stability analyses to reveal the minimax optimal optimization algorithm for the adversarial loss. For the lower bound, they show that any algorithm with the convergence rate $s(T)$ suffers from the generalization gap at least $s(T)/n$, where n is the sample size. For the upper bound, they develop an optimization algorithm employing the Moreau envelope to smoothen the adversarial loss function so that the SGD is stabilized. They show that it achieves the optimal generalization gap with $s(T)=T$. Also, they analyzed the optimization algorithm with the approximated Moreau envelope, which gives the same optimal rate. The empirical evaluations demonstrate that their algorithm can avoid robust overfitting.

strength_and_weaknesses: Strength:
- The minimax optimality in the adversarial loss minimization is crucial for understanding adversarial robustness.
- The inexact version of the proposed algorithm is novel.
Weakness:
- The minimax lower bound result has issues in its originality and correctness.
- The exact version of their algorithm has an originality issue.
clarity,_quality,_novelty_and_reproducibility: I'll give comments on each topic. 

(Minimax lower bound)
First, the statement of Theorem 4.1 looks weird. The authors take maximization over h inner the minimization over the algorithms. It implicitly assumes that the learner does not know the adversarial loss h, which conflicts with the setting in which the learner knows h. In Chen et al.'s analyses, they take the inner maximization over the distribution D,  which is unknown to the learner. Even if the statement is fixed so that the maximization is over D, I cannot find any difference from Chen et al., 2018. It seems that the originality of Theorem 4.1 is significantly low.

Second, and more importantly, the lower bound in Theorem 4.1 might be incorrect due to the possibly invalid assumption of Eq. 4.1. The results of Xing et al. and Xiao et al. guarantee an adversarial loss for convex and Lipschitz losses is an element of H in Eq. 4.1. It is not proved that there is a set of g such that the induced adversarial losses are equivalent to H in 4.1. We might need to think of a smaller set of losses as the adversarial losses, by which the minimax error might be smaller. Theorem 4.1 may be correct under the assumption of Eq. 4.1, while it might not be the minimax lower bound on the adversarial loss minimization.

(Exact algorithm)
I cannot find any difference from Lemma 2.5 in the following paper:
- D. Davis and D. Drusvyatskiy. Proximal methods avoid active strict saddles of weakly convex functions. Foundations of Computational Mathematics, 2022.
It is better to clarify the difference between Lemma 5.1 and the result of Davis and Drusvyatskiy. 

Given Lemma 5.1, Theorem 5.1 is just an application of Hardt et al.'s result. I cannot find any novelty in this analysis.

(Inexact algorithm)
The inexact version of the algorithm and its analyses may be novel. It is nice that the inexact one achieves the same rate as the exact one.

(Experimental results)
The experimental results of Figure 2 adequately demonstrate the benefit of the proposed algorithm. One thing unclear is why the robust training accuracy of AT, whereas the present algorithm achieves high accuracy. Could the authors clarify this point?

I have one thing unclear in Figure 3. What does 10:0 mean? Does it mean no training data?

Minor comments:
- The authors claim that SGDmax does not achieve the minimax lower bound with the evidence of Theorem 4.2. However, Theorem 4.2 just demonstrates the upper bound, which might have a tightness issue. Fortunately, the original work reveals the matching algorithm-specific lower bound, which is better to support the claim.
summary_of_the_review: The minimax optimality of the adversarial loss minimization is a well-motivated and interesting direction. However, I found some issues or low originality in most results. Also, while their main idea is to employ the Moreau envelope, it is not original, as Hardt et al. discuss it as a way to control stability. I thus recommend the rejection.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the generalization problem in adversarial training. Specifically, it presents a minimax lower bound of the generalization gap, proposes Smoothed-SGDMax that achieves the bound. Connection to stochastic weight averaging (SWA) is also presented. 
strength_and_weaknesses: **Strength**

* Despite robust overfitting has been observed for quite some time and efforts have been spent to understand its root cause, the problem remain mostly open. This paper is a new effort towards solving this important problem, namely, understanding the generalization behaviour of the SGDMax algorithm in adversarial training.

* The paper provides novel perspectives (a lower bound) in characterizing the generalization gap with respect to the optimization gap. The proposed Smoothed-SGD algorithm is intuitively sensible, theoretically justified and empirically validated. 

* The theoretical analysis appears solid. 

** Weakness **

* Requiring the functions in class ${\cal H}$ to be convex significantly limits the applicability of the developed results. 
* Comparing with SGDMax, Smoothed-SGDMax does show improved generalization. However even with Smoothed-SGDMax, there still appears a significant gap between training and test robust accuracies (e.g., green and red curves in Figure 1). Such a gap appears much larger than its counter-part in (regular) training.  Then it seems that non-smoothness can not fully explain robust overfitting.   

clarity,_quality,_novelty_and_reproducibility: Overall the paper is well and clearly written.  The results are also novel and original. 

There may still be some room for improving the presentation and bringing out more insight. For example, how the non-smoothness of the adversarial loss impacts the algorithmic stability of SGDMax is not discussed. As this appears a key motivation justifying the proposal of Smoothed-SGDMax, its deserves some careful discussion in my opinion.




summary_of_the_review: Overall the paper is mostly well written with novel results towards better understanding of an important problem (robust overfitting) in deep learning, although the results are built on strong assumptions, rather distant from practice.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studied the generalization performance of adversarial training from the stability perspective. The authors first derived a minimax lower bound of generalization gap, and then proposed a smoothed-SGDmax algorithm using the technique of Moreau envelop which enjoys a generalization bound that matches the lower bound. In particular, smoothed-SGDmax algorithm eliminates the "the generalization error floor" of standard SGDmax algorithm without the smoothing technique proposed in this paper.

During the AC-reviewer meeting, all reviewers agree on that fact this paper studies an important problem is important. The results are also interesting, reviewers learned something new from the paper that potentially worth publishing. However, after seeing the updated version of the draft, reviewers still believe there remain a fair amount of mathematical typos in paper which hurts the quality. (Despite reviewers agree that the idea of Moreau envelope may not have been extensively used in the problem considered in this paper before, the proof is different from Hardt et al., 2016) reviewers still feel the technical novelty is a bit lacking, and it seems the results follow from the relatively standard analysis even though it is not exact the same from the existing papers. It's the combination of these two make this paper borderline leaning towards rejection.

I will recommend the authors to (1) fix the typos (I can also easily see a few even in the revised version); (2) highlight the technical challenges answering "why the results actually take a lot effort to get" and then maybe retry a similar venue.
justification_for_why_not_higher_score: technical novelty is lacking. The results seem not hard to achieve.
Decision: Reject