Summary
This paper analyzes the convergence properties of Sharpness-Aware Minimization (SAM) with **constant** perturbation size $\rho$ and gradient normalization applied to the updates; this has not been done in prior works. Both deterministic and stochastic settings are considered. The authors show the following:
1. For the strongly convex + smooth case in the deterministic setting, SAM converges to the global minimum. A matching lower bound for the rate is also presented although I'm not sure if it's correct; please see Weakness #2. For the general convex + smooth case in the deterministic setting, the authors are only able to show convergence to a stationary point (in terms of gradient norm).
2. More importantly, the authors show that in all other settings considered in the paper, SAM cannot converge to the global/local minimum. Specifically, this includes the smooth non-convex and non-smooth Lipschitz convex cases in the deterministic setting and smooth + (strongly) convex and smooth non-convex cases in the stochastic setting. Some lower bounds are also presented to complement the upper bounds.
In summary, compared to the case of decaying perturbation size $\rho$ analyzed in prior theoretical works on SAM, this work shows that using a constant $\rho$ can inhibit convergence.
Strengths
**1.** Unlike prior theoretical works on SAM, this paper considers the use of constant perturbation size and gradient normalization in the SAM update which is more aligned with practice.
**2.** The theory is comprehensive in the sense that the common function classes are covered and there is analysis for both the deterministic and stochastic settings.
**3.** In some cases, matching lower bounds are also presented to support the upper bounds. Some of the constructions and techniques for the lower bounds seemed novel to me (for e.g., Theorem 3.6) but I'm not an expert on lower bounds.
**4.** The paper is also written more or less clearly.
Weaknesses
**1.** In the abstract, the authors write: "*Perhaps surprisingly, in many scenarios, we find out that SAM has limited capability to converge to global minima or stationary points*". But I don't find the non-convergence of SAM **with constant $\rho$** (and constant step-size $\eta$) very surprising; in fact, the asymptotic convergence in Theorems 3.1 and 3.3 surprises me. I say this because of the following reason. Suppose deterministic SAM converges to some point $\tilde{x}$. Then, we must have $\nabla f\Big(\tilde{x} + \rho \frac{\nabla f(\tilde{x})}{||\nabla f(\tilde{x})||}\Big) = 0$. This means that we must have $\tilde{x} + \rho \frac{\nabla f(\tilde{x})}{||\nabla f(\tilde{x})||} = x^{\ast}$, where $x^{\ast}$ is some stationary point of $f$. So, $|| \tilde{x} - x^{\ast}|| = \rho$, i.e., if SAM with constant $\rho$ converges to some point, then that point must be $\rho$ distance away from a stationary point of $f$. Notice that if $\rho$ is a decreasing function of $t$, this (apparent) issue of non-convergence won't arise.
**2.** There seems to be an issue in Theorem 3.2 which states that $\frac{\beta}{\mu} \geq 2$. But in the proof of Theorem 3.2, one-dimensional quadratics are used to obtain lower bounds; for these one-dimensional quadratics the **tightest possible** smoothness constant = **tightest possible** strong convexity parameter. So actually, $\beta = \mu$ in all 3 cases. Now in Case 1, $x_0 = 2\rho$. But then, we get $x_t \geq \frac{x_0}{2} = \rho$. Unfortunately, this yields a vacuous lower bound of 0. Can the authors comment on this? It seems that if the current proof strategy is to be used, we would need at least 2-d quadratics where $\beta > \mu$.
**3.** In Theorem 3.4, the dependence of the convergence bound w.r.t. $T$ seems loose and I don’t think the Lipschitz assumption is required. In the second equation of the proof, there is a $-\frac{\eta}{2}||\nabla f(y_t)||^2$ term and a $\frac{\eta^2 \beta}{2}||\nabla f(y_t)||^2$ term; these two terms can be combined together and as long as $\eta \beta < 1$, the coefficient of $||\nabla f(y_t)||^2$ is negative. So I think we can get $O(1/T)$ convergence to a $O(\beta^2 \rho^2)$ stationary point with a fixed step-size independent of $T$. Also, if we follow this approach, we don’t even Lipschitzness.
**4.** It is unfortunate that the lower bounds for the stochastic case needed to be corrected in the supplementary material.
**5.** (Minor weakness but a limitation nevertheless) SAM was proposed to improve generalization. But this paper has no results illustrating how SAM improves generalization such as by converging to points that are *approximately* flat minima (or because it inhibits convergence preventing over-fitting).
A missed reference (just for the author's information): https://openreview.net/pdf?id=IcDTYTI0Nx shows the convergence of SAM with non-constant perturbation sizes.
Questions
Please address Weaknesses 1, 2 and 3. My current rating is mainly due to Weakness 1; if the authors can point out some fallacy in my understanding or convince me that the *non-convergence* of SAM isn't all that obvious, I can increase my score.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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.
Limitations
Some minor limitations have been discussed such as the loose dependence on $\beta$ and $\mu$ in Theorem 3.1. But important limitations such as Weakness #5 have not been discussed. No foreseeable negative societal impacts.