Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work provides an analysis of the sharpness aware minimization (SAM) by Foret et al. 2021.
main_review: This work provides an analysis of the sharpness aware minimization (SAM) by Foret et al. 2021. While the paper has some experiments, they are minimal and serve to reinforce the points made by the theoretical analyses. Therefore, I view this work to be a primarily theoretical work.

The first result uses the technique of Woodworth et al. 2020 to analyze the implicit bias of SAM when applied to 2-layer diagonal linear network. Although the model considered is very limited, and although the analysis technique is not novel, I still think this is a good first step. The authors summarize the results of their analysis in Proposition 1, but I am not sure if I agree with the interpretation of the anlayses. I do see that the implicit objectives differ by a factor of \alpha^(1/n) but this is a mere multiplicative factor that should not overall affect the meaning of the implicit optimization problem. In particular, I don't fully understand the reasoning behind the claim "The SumMax implementations has better bias properties since its effective scale of α is considerably smaller than the one of MaxSum." I would be happy to be corrected in the rebuttal, but otherwise I feel that Proposition 1 does not provide much insight into why MaxSum, SumMax, and regular SGD have different generalization performances.

The second result is a convergence analysis of SAM. This is a result that was missing in the original SAM paper, so it's nice that the authors establish that SAM converges to a stationary point, just as SGD does. However, the analytical techniques are not quite novel, and the conclusion says nothing about why SAM is better than SGD.

Finally, the authors provide discussions on why SAM provides benefits when labels are noisy and how SAM prevents robust overfitting. While the discussions here are interesting, they are not rigorous mathematical discussions, and the experimental validation of these discussions is not very thorough. Therefore, I view the contribution of these sections to be minimal.
summary_of_the_review: Overall, the paper presents some interesting and useful analyses, but the analytical techniques are not very novel and they do not (at least to me) provide significant clarity on why SAM outperforms SGD.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The aim of the paper is to provide theoretical explanations for the recent successes of adversarial weight perturbation and sharpness-aware minimization (SAM) methods. In particular, these methods have been shown to significantly help robust generalization in deep learning and theoretical explanations for their success are missing so far. 

The paper aims to fill this gap by getting a better understanding of SAM. It contributes a collection of miscellaneous results:
* A proof that SAM provides better generalization for linear neural networks than SGD
* The convergence of SAM is analyzed and generalization behavior is discussed
* A new interpretation of SAM is presented in terms of gradient reweighing 
* Finally, a connection of SAM to the noisy label literature is made
main_review: ### Strengths
The main strength of the paper is the theoretically sound and insightful analysis of SAM. 

### Weakness
* In its present state, the paper unfortunately reads a bit like a collection of disparate specialized results, and there is no deep fundamental insight gained why SAM improves generalization over SGD.  Perhaps this could be addressed by providing a more speculative / high-level discussion in the conclusion / outlook section. 
* It is proven that SAM converges to a stationary point of the original loss (similar to SGD). To me, this is actually a weakness of SAM and not a strength, since ideally one wants a robust method to converge to points in the landscape which are non-stationary but in an overall "flat" low-loss region. 
* In the paper, it is mentioned that the averaged iterates of normalized-SAM converge to a different point and it is argued that this "different" point is a bad one ("not necessarily flatter than the solution").  Is this conclusion based on some empirical evidence or a theoretical insight? It would be great if the paper could elaborate on this point. 
* Should Foret et al (2021) and Wu et al (2020) really be considered concurrent work? They are quite far apart (Apr2020 vs Oct2020 on arXiv).
* Also, there is the concurrent work to SAM https://arxiv.org/abs/2010.04925 which should be mentioned. 
summary_of_the_review: I believe that the collection of theoretical results on SAM is both novel and useful to the community. Moreover, the paper is well-written. If the issues mentioned in my main review can be addressed, I am inclined to increase my score and recommend acceptance of the paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors mainly analyzed a SAM-like algorithm with a square loss. For diagonal linear networks, this paper proves that the NNs trained by the algorithm has better generalizations than the ones trained by normal SGD. For deep NNs satisfies PL condition and other assumptions mentioned in section3, the authors can prove the algorithm will converge. The authors use a linear model to give the intuition why the SAM algorithm can generalize better on a dataset with label noise.
main_review:  I think this paper is well organized, and the proof seems solid. But I still have the following concerns:
1. This paper doesn't analyze SAM proposed in [1]. In the SAM algorithm, the gradient is normalized in the inner step. However, the algorithm proposed in this paper doesn't include such gradient norm terms. Just as the authors have summarized in the abstract, "$\ldots$ relies on worst-case weight perturbations," the gradient norm term is one of the most important parts of the SAM algorithm. 

They constructed the counterexamples for the original SAM algorithm in section B.3 to show the strength of using an unnormalized one. However, those examples are far from the practice because they are strongly convex with global minima at point zero. In this case, it is obvious that the algorithm will never converge to zero, even with a small perturbation. In practice, however, we use the cross-entropy loss for classification problems in which the good local minima would be far from zero. The training loss also has many local minima. In this case, a small perturbation will still guarantee the convergence and help find the flat minima.  

In order to show the algorithm proposed in this paper outperforms the original SAM algorithm, it would be more convincing if the authors could add more empirical comparison. I also want to ask whether the experiments in sections 3.3, 4, and 5 follow the SAM algorithm without normalization.

2. I get quite confused about whether MaxSum is better than SumMax. Before the implicit bias part on page 3, the authors write, "We next show formally that MaxSum SAM has a better implicit bias than ERM and SumMax SAM." Then, in the empirical part on page 4, the authors conclude that "ERM and MaxSum SAM enjoy the same performance whereas SumMax benefits from a better implicit bias."

3. Most of the results in this paper implicitly use the square loss rather than cross-entropy loss which limits the impact of the results. Does the implicit bias exist for cross-entropy loss? If so, it is worth adding it to the paper.

4. The convergence results in section 3.2 are based on assumptions A1 and A2. Generally, do you think assumptions A1 and A2 hold for NNs? Or do those assumptions hold for the diagonal linear neural networks analyzed in section 3.1? 

5. Figure 1 shows that ERM and MaxSum SAM enjoy the same performance. I think maybe $\rho$ is too small, have the authors tuned the parameter of $\rho$?

[1] Foret, Pierre, et al. "Sharpness-aware Minimization for Efficiently Improving Generalization." International Conference on Learning Representations. 2020.
summary_of_the_review: Is the main contribution of this paper to understand the original SAM algorithm or to propose a new SAM-like algorithm with a theoretical guarantee? I think that the paper has to make more clear what are the main contributions. The proof technique used in this paper is quite standard, and the results are based on the square loss. So the impact of the results may be limited. I also have some concerns about some details, as I have mentioned in the main review. So currently, I would like to suggest a rejection, but I am open to discussion and willing to increase my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This is an ambitious paper that seeks to explain why SAM works the way it does. First, the authors try to justify the better generalization of SAM over SGD on deep networks. Next, the authors discuss why SAM is robust to noisy labels, and argue why SAM can improve generalization even for linear classifiers. Finally, the authors discuss how to further improve SAM by leveraging a gradient reweighting interpretation and combining with a robust loss. 
main_review: This is an ambitious paper that seeks to cover many a lot of ground, from convergence properties of SAM, to generalization error, to robustness in noisy labels and adversarial training. The reviewer believes that each of these issues merits a single paper, so to squeeze all the discussions into one paper actually dilutes each of the contributions, as I will discuss below. 

The authors did a nice job to introduce the MaxSum SAM formulation and stochastic gradient descent-type algorithms to optimize the minmax objective. The first major result is Proposition 2 in which the authors use analytical techniques from SGD to control the expected gradient of SAM with stochastic gradients. The problem with this result is that, while mathematically elegant, it does not explain why SAM outperforms SGD. A theoretical explanation of SAM must be accompanied by comparison of the theory to SAM. 

The next contribution has to do with SAM's robustness to noisy labels. This is good aim to study. However, the explanation falls short of being convincing. The authors merely use the fact that SAM changes the direction of the gradient to be less aligned to the noisy direction. They substantiated this fact using Figs. 3b and 3c. But this is merely *one* experiment -- ResNet-18 trained on CIFAR-10 with 60% label noise. The reviewer was hoping for a more convincing theoretical explanation for this. 

The third contribution is the observation that SAM even improves generalization for linear models. This is a surprising phenomenon, but the explanation is not clear. The authors substantiate this not through theory, but through a toy example in in Fig. 4. It is not clear whether one can extrapolate the observations from this linear model to large-scale datasets. Again, I was hoping for a more theoretical explanation, since this is an "Understanding" paper. 
summary_of_the_review: The aims of this paper are laudable, but the explanations for short of being convincing. I would suggest the authors, in a new version of the paper, to focus solely on one aspect of SAM, and explain it fully (using theoretical results and comprehensive experiments), and comparing it to vanilla methods.
review_title: null

Meta-review: As evident by the title the paper focuses on understanding sharpness-aware minimization which is a contemporary training procedure  based on minimizing the worse case perturbation of the weights in ball. It has been observed that SAM improves the generalization and this paper aims to demystify this success. They also provide a convergence proof of SAM for non-convex objectives in a simplified setting and also discuss benefits of SAM in the noisy label setting.The reviewers thought this paper was an interesting first step The reviewers raised concerns about (1) novelty of the proof technique, (2) interpretation of the analysis. The response mitigated some the concerns but did not resolve them. I concur with the reviewers. The paper has some nice insights and good potential. However, there are a few things that need to be clarified and the paper has to be substantially rewritten to reflect this and thus I do not recommend acceptance at this time.
Decision: Reject