Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalization

Summary

This paper sheds light on the relationship between three concepts: (a) generalization (b) flatness and (c) explicitly inducing flatness via SAM. The paper identifies that the relationship is nuanced and is based on certain architectural properties of the model. Specifically, depending on the architecture, there are three possible regimes: 1. A regime where _every flat minimizer generalizes well_ and SAM finds these minimizers. 2. A regime where _there exists flat minimizers that generalize poorly_ but SAM does _not_ find these minimizers. 3. A regime where _there exists flat minimizers that generalize poorly_ and SAM _does_ find these minimizers. The paper shows that - Regime (1) happens for 2-layer RELU networks _without_ bias - Regime (2) happens for 2-layer RELU networks _with_ bias - Regime (3) happens for 2-layer RELU networks _with_ bias, _with_ a simplified Layer Norm. Note that in all cases, the existence of a flat solution that generalizes/memorizes is proven theoretically; while the effect of SAM is demonstrated empirically.

Strengths

1. The questions formalized in the paper are novel, and well-formulated. 2. I gained a much clearer understanding of some generally unclear and confusing concepts: (a) flatness, (b) generalization and (c) explicitly inducing flatness. All these ideas are dealt with care and rigor. 3. The introduction is well-written and the chain of arguments are explained clearly. Despite being a theoretical and nuanced paper, I found it extremely easy to follow the arguments in each section. I thoroughly enjoyed reading the paper! 4. Rather than unnecessarily complicate the theory, the authors come up with a reasonably minimal settings of a 2-layer _non-linear_ model and support their arguments with either a formal result or with a rightly-designed empirical result. 5. That there are situations where the flattest solution does not generalize well is surprising from a theoretical point of view.

Weaknesses

I currently do not have any major concerns about this paper. Most of my comments are follow-up questions, which I enumerate in the next section. My most important question --- which may or may not hint at a weakness --- is below: ### Major question Q1a: Could you be more explicit about any parameter count dependence in the Rademacher complexity term of Thm 3.1 and Lemma 3.1? I am unsure if this is orthogonal to the main point of the result, so I'd also appreciate some clarity on that. Q1b: On that note, I'd also like to know why this bound would break down upon the introduction of bias into the architecture. Would one of the terms within the Rademacher complexity end up scaling with the number of datapoints?

Questions

1. Def 4.1 for the memorizing solutions appears to be incomplete and can be more formal. First, by _input data_, please clarify that you are referring to the training data. Furthermore, you also require the additional criterion that the activations of the model on _test_ data are all zero --- is this right? If not, the definition appears to be incomplete as even the raw inputs must more or less satisfy the orthogonality assumption with high probability? i.e., when we sample from a high-dimensional hypercube, two samples must more or less be orthogonal. So this alone shouldn't characterize a memorization solution? 2. Could you provide intuition for what the "flattest solution" in Eq 4 satisfies? It seems to require that _the activated top-layer weights have correspondence to the activations themselves_. I don't think Fig 3 captures this specific structure? 3. Do you empirically find that SAM learns a solution whose parameters resemble Eq 4 in any way? 4. The motivation behind the choice of loss function can be made more transparent. In particular, the main loss function used is squared error loss. In the appendix, the authors also use logistic loss _but with label smoothing_. If I am not wrong these choices ensure that the flattest minimizer exists and is unique up to some permutations. However, with pure logistic loss, the flattest minimizer would become ill-defined since there would be many different flat minimizers "at $\infty$"? I believe this is the reason behind a line of work in PAC-Bayes literature that tries to "normalize" flatness in a well-defined way. In other words, this work "sidesteps" this annoying issue; this is okay, as it still helps outline an elegant insight. But this needs to be clearly stated so that readers can put this result in context. ### Minor suggestions 1. I'd suggest making the specific notion of trace-of-hessian-based flatness clear in the abstract and in the beginning of the introduction. Since there are many notions of flatness, it would be good to be upfront about which notion is being discussed here. 2. In the introduction, I'd suggest clarifying that the SAM-related results are purely empirical. 3. Section 4 title seems incorrect. In this regime, SAM finds the _latter_ non-generalizing solution not the former one. 4. Line 167 makes an abrupt reference to a theorem that's not discussed until then. 5. It's not clear until we get to the discussion of SAM as to whether the proof is empirical or not. 6. In Sec 5.1, instead of simply referring to Thm 3.1 and 4.1, I would add a verbal description so that it's easier to follow. ### Summary Overall, I found this paper to be insightful, rigorous and clear in its message. The community would find this valuable given the confusing nature of literature in flatness. ### Post-rebuttal update I have increased my score since the authors addressed my response satisfactorily. **I'd also like to respectfully express my strong disagreement with concerns raised in the other reviews.** - Regarding "Two-layer network is too simplistic": When a certain truth has not been proven in any setting to begin with, and when someone makes headway by providing the first proof in a simple setting, it is unfair and counter-productive to hold it against them. For without that headway, there is little hope for more general analyses. In fact, IMO proofs in more general settings (like a multi-layered network) get so unwieldy as to become uninsightful. Furthermore, in this scenario, the setting is a 2-layer network which does not reduce to a linear function of its parameters. IMO, the statements in this paper are already highly non-trivial to identify, let alone prove. - Regarding considering other alternate versions of SAM, this is an interesting reformulation of the problem. Thanks to this work, we can be better posed to answer more important questions. Hence, again I don't want to fault this paper for not proving its elegant theory in various sophisticated versions of SAM. I would share this review's concern had the considered setting been far removed from practice, and promised no tangible way of extending to other situations --- this doesn't seem to be the case here, in my humble opinion.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The paper lists reasonable limitations in the conclusion.

Summary

This paper studies the connections between sharpness of the training loss and generalization performance under a simplified MLP architecture. In particular, authors show scenarios of when flat solution do/do not generalize, as well as cases when Sharpness-Aware Minimization (SAM) does/does not generalize.

Strengths

The theoretical insights of the paper are interesting and hopefully can help better understand the relationship between flatness and generalization.

Weaknesses

I think the paper has several shortcomings, outlined below. - Model setup: I think the model setup is too simplistic. The input space is binary, which I think is fine. However, no noise is considered in the model and the output label $y=x[1]x[2]$ satisfies a very specific structure. Therefore, it is not clear to me why results discussed in the paper would generalize to broader model setups, and the observations discussed here are not just an artifact of the simplistic model. As shown in Lemma 3.1, the sharpness under the paper's setup is closely related to the weight norm, which may or may not be the case in a more realistic setup. - Experiments: I don't find the experiments on SAM convincing. How is SAM implemented? How are the algorithm hyper-parameters chosen? How is SAM initialized? Maybe changing the SAM parameters and initialization would change the outcome of the experiments. Can the observation of SAM converging to non-generalizing flat solution be replicated in a more realistic setup? Is weight decay used for SAM, as specially, in this case sharpness seems to be closely related to the weight norm. - The authors miss [1]. As this paper discusses the connections between generalization and sharpness/SAM, the authors should discuss and compare their results to [1], specially as [1] discusses noisy setups. [1] Behdin, K., & Mazumder, R. (2023). Sharpness-aware minimization: An implicit regularization perspective. arXiv preprint arXiv:2302.11836.

Questions

- Maybe some visualization might help address some of my concerns in the previous part? For example visualizing the SAM/GD trajectories? - Additional experiments either on noisy data settings or more realistic deep networks might help fill some of the gaps in the paper.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

n/a

Summary

This work aims to examine different cases for which flatness implies generalization. The conclusion heavily depends on the underlying model, while there are three different scenarios that contradict with each other. Additionally, the theoretical guarantees study the generalization error at the solution, however the empirical guarantees consider the generalization error at the last iteration of the SAM algorithm. Despite the convergence of the SAM algorithm, the training horizon may also affect generalization. With alternative sampling schedules of the data-set, it can be possible to minimize the training horizon (for instance see Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning by Okanovic et al.). I think it would be useful to examine if the SAM algorithm generalizes better when considering alternative sampling schedules. In such a case, the batch-selection policy could be more significant than the sharpness minimization. As the author also mention flattest solutions are not directly associated with efficient generalization in general. Further, there is a deep literature for the edge of stability phenomenon (Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability by Cohen et al.). In this case, the sharpness increases at termination (Understanding Gradient Descent on the Edge of Stability in Deep Learning by Arora et al., Section 2. Related Works), however good generalization performance have been observed in some cases. These cases might be considerd by the authors to provide a more complete picture for the empirical part of the paper, and additional conclusion about sharpness minimization and generalization.

Strengths

The results are original and provide a partial evidence between sharpness and generalization, however the conclusion is not clear. Theorem 3.1 is an interesting result, however it is limited to a simple architecture but it is valuable.

Weaknesses

Some parts of the paper are not clear enough. For instance, there exist statements like "All flattest models generalize" while the statement holds only for certain cases. It appears that the theoretical guarantees study generalization at the solution, however in practice the generalization of the algorithm might be different (see also the Summary). The main question of the paper has been considered in prior works as well.

Questions

In theorem 3.1 the variable $\theta^*$ should be a random variable that depends on the training data-set. Is this true? In such a case the authors may consider to use the notation of the conditional expectation in the statement of the Theorem to make this fact clear.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The authors have addressed the limitations sufficiently.

Summary

This paper explores the relationship between sharpness and generalization in overparameterized neural networks. The authors challenge the popular belief that flatness of the loss function implies better generalization and show that sharpness minimization algorithms do not always lead to better generalization. Through theoretical and empirical investigation, the authors identify three different scenarios for two-layer ReLU networks, showing that the relationship between sharpness and generalization is subtle and depends on the data distributions and the model architectures. The paper's contributions include a theoretical analysis of the relationship between sharpness and generalization.

Strengths

The authors identify three scenarios for two-layer ReLU networks and provide theoretical and empirical evidence to support their findings. I believe the subtle details in architecture and distribution located in this paper are remarkable. Overall, this paper makes significant contributions to the field of generalization theory and challenges the popular belief that the flatness of the loss function implies better generalization.

Weaknesses

1. One potential weakness of the paper is that it only examines the relationship between sharpness and generalization for two-layer ReLU networks (personally, I think this is acceptable since it is very hard to analyze more complex scenarios). Additionally, the authors only examine the CIFAR-10 and CIFAR-100 datasets, and it would be valuable to examine their findings on other datasets to determine if their results generalize to other domains. 2. The expression of the article is not very friendly and a little difficult to understand. 3. There are some grammatical and formatting problems, some of which are shown as follows. 1) Pictures should be resized to make them look more coherent. In addition, the text in the image should be consistent with the font within the paper. 2) There are some spelling errors, such as “subtlely”. 3) References are poorly formatted. Please use a uniform format for references. 4) Formulas and variables should be consistent with the font within the paper. 5) Operators should be carefully defined. 6) There are some formatting issues. For example, lowercase letters as the first letter of a sentence.

Questions

1. In abstract, what does this sentence “there exist non-generalizing flattest models and sharpness minimization algorithms fail to generalize poorly” mean?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

4 excellent

Limitations

The authors have adequately addressed the limitations.

Thanks for the response!

Thanks for the clear answers! I have raised my score and updated my review.

Thank you!

Thank you for your response, I have raised the score because I think that examples of simple models are important, however I still believe that the presentation of the results and the paper requires improvement.