Practical Sharpness-Aware Minimization Cannot Converge All the Way to Optima
Authors: Dongkuk Si
Chulhee Yun
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Sharpness-Aware Minimization
convex optimization
TL;DR: We analyze the convergence guarantee and provide non-convergence examples for Sharpness-Aware Minimization (SAM) with constant perturbation size.

Abstract: Sharpness-Aware Minimization (SAM) is an optimizer that takes a descent step based on the gradient at a perturbation $y_t = x_t + \rho \frac{\nabla f(x_t)}{\lVert \nabla f(x_t) \rVert}$ of the current point $x_t$. 
Existing studies prove convergence of SAM for smooth functions, but they do so by assuming decaying perturbation size $\rho$ and/or no gradient normalization in $y_t$, which is detached from practice. To address this gap, we study deterministic/stochastic versions of SAM with practical configurations (i.e., constant $\rho$ and gradient normalization in $y_t$) and explore their convergence properties on smooth functions with (non)convexity assumptions.
Perhaps surprisingly, in many scenarios, we find out that SAM has limited capability to converge to global minima or stationary points.
For smooth strongly convex functions, we show that while deterministic SAM enjoys tight global convergence rates of $\tilde \Theta(\frac{1}{T^2})$, the convergence bound of stochastic SAM suffers an inevitable additive term $\mathcal O(\rho^2)$, indicating convergence only up to neighborhoods of optima.
In fact, such $\mathcal O(\rho^2)$ factors arise for stochastic SAM in all the settings we consider, and also for deterministic SAM in nonconvex cases; importantly, we prove by examples that such terms are unavoidable.
Our results highlight vastly different characteristics of SAM with vs. without decaying perturbation size or gradient normalization, and suggest that the intuitions gained from one version may not apply to the other.

Practical Sharpness-Aware Minimization Cannot Converge All the Way to Optima
Dongkuk Si
Chulhee Yun
Korea Advanced Institute of Science and Technology (KAIST) (dongkuksi, chulhee yun) Ckaist. ac.kr
Abstract
Sharpness-Aware Minimization (SAM) is an optimizer that takes descent step based the gradient a perturbation y; 3e (((=)) [m)]] of the current point x;- Existing studies prove convergence SAM for smooth functions, but they do so by assuming decaying perturbation size p and/or gradient normalization in yt. which is detached from practice. To address this gap, we study determinis- tic/stochastic versions of SAM with practical configurations (i.e., constant and gradient normalization in yt) and explore their convergence properties on smooth functions with (non)convexity assumptions. Perhaps surprisingly, in many scenar- ios, we find out that SAM has limited capability to converge to global minima or stationary points. For smooth strongly convex functions, we show that while de- terministic SAM enjoys tight global convergence rates of Ó 7 the convergence bound of stochastic SAM suffers inevitable additive term Op²)), indicating convergence only up to neighborhoods of optima. In fact, such (p²)) factors arise for stochastic SAM in all the settings we consider, and also for deterministic SAM in nonconvex cases; importantly, we prove by examples that such terms are unavoidable. Our results highlight vastly different characteristics of SAM with without decaying perturbation size gradient normalization, and suggest that the intuitions gained from one version may not apply the other.
Introduction
Modern neural networks are armed with a large number of layers and parameters, having a risk to overfit to training data. In order to make accurate predictions unseen data, generalization performance has been considered as the most important factor in deep learning models. Based on the widely accepted belief that geometric properties of loss landscape are correlated with generalization performance, studies have proved theoretical and empirical results regarding the relation between sharpness measures and generalization [14, 17, 19, 21, 29]. Here, sharpness of a loss at point generally refers to the degree to which the loss varies in the small neighborhood of the point.
Motivated by prior studies that show flat minima have better generalization performance [19, 21]. Foret et al. [16] propose an optimization method referred Sharpness-Aware Minimization (SAM). A single iteration of SAM consists of one ascent step (perturbation) and one descent step. Starting
[((;) from the current iterate H,, SAM first takes ascent step ze: I; + P PT]V/[;;]]] to (approximately) maximize the loss value in the p-neighborhood of æt, and then the gradient y: update æ, to 2++1. This two-step procedure gives SAM special characteristic: the tendency to search for flat minimum, i.e., a minimum whose neighboring points also return low loss value. Empirical results [3, 9, 16, 20, 25] show that SAM demonstrates an exceptional ability to perform well on different models and tasks with high generalization performance. Following the success of SAM.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Convergence of SAM with constant perturbation size after T steps. C1, C2, C3, and C4 indicate 3-smoothness, p-strong convexity, convexity, and Lipschitzness, respectively. C5 indicates the bounded variance of the gradient oracle. See Section 2.3 for definitions of C1-C5.
Optimizer
Function Class
Convergence Upwer Bounds
Reference
Deterministic SAM
C1.C2
(o.....) f(x)) ( (0xp===000x0-----0000000000
ō (exp(-T) g (o..... f(x.)
Theorem 3.1
Deterministic SAM
C1,C2
77
Theorem
Deterministic
C1,C3
$ E [V
Theorem
vT
Deterministic SAM
CI
+ + [f(=)]] 5 (0(+) + 8"p"
Theorem 3.4
Stochastic SAM
C1,C2,C5
Bf( - fr $ (xp(-7))
|-_ 102
28
Theorem
+ 12.-
Stochastic SAM
C1,C3.C5
+ /| s
v/
+ 4,8
Theorem 4.3
Stochastic SAMA
C1,C5
レ 50 +++ +
+ pppp²
Theorem 4.5
Stochastic m-SAM
C1,C4,C5
+ E [[[[V
30) 0
+ 5.
Theorem 4.6
numerous extensions of SAM have been proposed in the literature [6, 15, 18, 23, 24, 26-28, 30- 32, 34,35J. 35J.
On the theoretical side, various studies have demonstrated different characteristics of SAM [1, 2, 4, 5, 12, 13, 22, 33]. However, comprehending the global convergence properties of practical SAM on theoretical level still remains elusive. In fact, several recent results [2. 18, 27, 31, 35] attempt to prove the convergence guarantees for SAM and its variants. While these results provide convergence guarantees of SAM on smooth functions, they somewhat detached to the practical implementations of SAM and its variants. They either (1) assume decaying or sufficiently small perturbation size p [18, 27, 31, 35], whereas p is set to constant in practice; (2) assume ascent steps without gradient normalization [2], whereas practical implementations of SAM use normalization when calculating the ascent step y:-
1.1 Summary of Our Contributions
To address the aforementioned limitations of existing results, investigate convergence properties of SAM using gradient normalization in ascent steps and arbitrary constant perturbation size p. We note that to the best of our knowledge, the convergence analysis of SAM have not been carried out under the two practical implementation choices. Our analyses mainly focus on smooth functions, with different levels of convexity assumptions ranging from strong convexity to nonconvexity. We summarize our contributions below; a summary of our convergence results (upper and lower bounds) can also be found in Table
For deterministic SAM, we prove convergence to global minima of smooth strongly convex functions, and show the tightness of convergence rate in terms of T. Furthermore, establish the convergence of SAM to stationary points of smooth convex functions. For smooth nonconvex functions, prove that SAM guarantees convergence to stationary points up an additive factor Opp²). We provide a worst-case example that always suffers a matching squared gradient norm ((p²). showing that the additive factor is unavoidable and tight in terms of p.
For stochastic settings, we analyze two versions of stochastic SAM (n-SAM and m-SAM) on smooth strongly convex, smooth convex, and smooth (Lipschitz) nonconvex functions. We provide convergence guarantees to global minima or stationary points up to additive factors O(p²). In case of m-SAM, we demonstrate that these factors are inevitable and tight in terms of by providing worst-case examples where SAM fails to converge properly.
1.2 Related Works: Convergence Analysis of SAM
Recent results [18, 27, 31, 35] prove convergence of stochastic SAM and its variants to stationary points for smooth nonconvex functions. However, these convergence analyses are limited only smooth nonconvex functions and do not address convex functions. Also, as already pointed out, all the proofs require one crucial assumption detached from practice: decaying (or sufficiently small) perturbation size p. If becomes sufficiently small, then the difference between FSAM(n) (x)) max (a + E) and (ax becomes negligible, which means that they undergo approximately the same updates. Due to this reason, especially in later iterates, SAM with negligible perturbation size

---

would become almost identical to gradient descent (GD), resulting in significant difference in the convergence behavior compared to constant p.
As for existing proofs that do not require decaying p. Andriushchenko and Flammarion [2] prove conver- gence guarantees for deterministic SAM with constant p on smooth nonconvex, smooth
USAM
smooth convex, and smooth strongly convex functions, Moreover, the authors prove convergence guarantees of stochastic SAM, this time with decaying P. smooth nonconvex and smooth Polyak-Lojj Lojasiewicz functions. However, their analyses are also crucially different from the practical implementations of SAM because their proofs are for variant of SAM without gradient nor- malization in ascent steps, with updates the form of Le+1 2; 7/ (æ; + pV (x))). This form can be considered as vanilla SAM with an "effective" pertur- bation size p (xx)) ) which indicates that even with constant p. the effective perturbation size will become smaller and smaller the algorithm converges towards a stationary point. As in the case of decaying p dis- cussed above, this make huge difference in the convergence behavior.
Figure 1: Trajectory plot for function f(z, u) = (ry - 1)². The green line indi- cates global minima of f. SAM and USAM indicates SAM with and without gradient normalization, respectively, and GD indi- cates gradient descent. When USAM ap- proaches the green line, it converges nearby global minimum, which is similar GD. contrast, SAM travels along the green line, towards the flattest minimum (1,
Figure illustrates a comparison between SAM with and without gradient normalization, highlighting the disparity between their convergence points. As we predicted above, evident that they indeed reach entirely distinct global minima, exhibiting different convergence characteristics.
Discussions on the related works on the relationship between sharpness and generalization, as well as other theoretical properties of SAM, are provided in Appendix A.
1.3 Notation
The euclidean norm of vector is denoted ||0/] We let R; & {x E R x 0}, and use [++ to define max(-, 0}. We use (-) and ((-) to hide numerical constants in our upper and lower bounds, respectively. We use (-)) to additionally hide logarithmic factors. When discussing rates, we sometimes use these symbols hide everything except I', the number of SAM iterations. When discussing additive factors that arise in our convergence bounds, we use these symbols to hide all other variables except the perturbation size p. For an objective function and initialization æg of SAM, we define l A inf far and A f(xr)) f
2 Sharpness-Aware Minimization: Preliminaries and Intuitions
Before presenting the main results, we first introduce deterministic and stochastic SAM, and present definitions of function classes considered in this paper. We next introduce virtual gradient map and virtual loss that shed light on our intuitive understanding of SAM's convergence behavior.
2.1 Sharpness-Aware Minimization (SAM)
We focus minimizing function IR + F. where the optimization variable is represented by & E Rdd using the Sharpness-Awe Aware Minimization (SAM) optimizer. Instead of minimizing the vanilla objective function fæx) SAM [16] aims to minimize the SAM objective FSAM((x) where
min SAM min max f(x + E).
x ||
For p R;. the SAM loss FSAM(z) outputs the worst function value in a p-ball {w E Rd ||æ w|l S p) around æ. Assuming "sufficiently small" p. the inner maximization of (1) can be solved by anylor-approximating the objective:
arg max f(x + + Rs arg max f(x) + Vf())) = PTVパ(T Ell
vf(m) & ε(x).
|| Sp
3

---

Using this approximate solution é(x), we can define the approximate SAM objective fSAM as (SAN)(x)) & f(æ é())). In order to run gradient descent (GD) fSAM(()) one needs to calculate its gradient; however, from the definition of é(æ), we can realize that V ff (x) has terms that involve the Hessian of f. Here, SAM makes another approximation, by ignoring the Hessian term:
v fSAA((z) R V [()))aattte
From these approximations, one iteration of SAM defined as a set of two-step update equations:
V(a)) y: + P [
T++1 21 f
As seen in (2), we use 2; to denote the iterate of SAM at the t-th step. We use T to denote the number of SAM iterations. We refer to the hyperparameter / E RT as the perturbation size and 1 E R, as the step size. Note that in (2), the perturbation size p is time-invariant constant; in practice, it is common to fix p as a constant throughout training [3, 9, 16].
According to the SAM update in (2), the update cannot be defined when [ = 0. In practice, we add small numerical constant (e.g., 10 12) the denominator in order prevent numerical instability. In this paper, we ignore this constant and treat [[[[(m))]
vf(())) as 0 whenever ||V (xx))l = 0.
2.2
SAM under Stochastic Settings
To analyze stochastic SAM, we suppose that the objective is given as f(x) Ee[[(x; E)), where is a stochastic parameter (e.g., data sample) and 1(x; {) indicates the loss at point x with a random sample ç. Based on the SAM update (2), we can define stochastic SAM under this setting:
V: x, *P ((x.)
x++1 = xt (3))
We define g(x: = val {) and ((x) = V v= E) Here, & and are stochastic parameters, queried from any distribution(s) which satisfies [a: {) = [,: {) = f(x)
There are two popular variants of stochastic SAM, introduced in Andriushchenko and Flammarion [2]. Stochastic n-SAM algorithm refers to the update equation (3) when & and & are independent. In contrast, practical SAM algorithm in Foret et al. [16] employs stochastic m-SAM algorithm, which follows the update equation (3) where & is equal to Ş. We will consider both versions in our theorems.
2.3 Function Classes
We state definitions and assumptions of function classes of interest, which are fairly standard.
Definition 2.1 (Convexity). A function f Rd + R is convex if. for any y E Rd and X E [o, 1]. satisfies fAx (1 X)ы) S Af(x) (1 (1-A)) Az)(
Definition 2.2 (u-Sttong Convexity). A differentiable function f Rdd - TR is p-strongly convex there exists > 0 such that [(x 2 +()(((+(++(())))
y) + / [| vll² [ for all a. E Rd
Definition 2.3 (L-Lipschitz Continuity). A function f Rd R is L-Lipschitz continuous if there exists L 2 0 such that []f - f(x)l < L| - yll. for all y E Rd
Definition 2.4 (3-Smoothness). A differentiable function f Rd + R is 3-smooth if there exists such that [[v ( s B|| - y||. for all x, y E IRd.
Next we define an assumption considered in the analysis of stochastic SAM (3). Assumption 2.5 (Bounded Variance). The gradient oracle of a differentiable function f : Rd + IR has bounded variance if there exists o 2 0 such that
V fxx) (xx)=
Vl(2; e o², EeI[Vf(x) vl(2; Vo e Rdd
2.4 SAM as GD on Virtual Loss Convergence analysis of SAM is challenging due to the presence of normalized ascent steps. order to provide intuitive explanations of SAM's convergence properties, develop tools referred to as

---

virtual gradient map and virtual loss in this section. These tools can provide useful intuitions when
we discuss our main results.
In order to define the new tools, we first need to define Clarke subdifferential [10]. whose definition below is from Theorem 6.2.5 of Borwein and Lewis [7].
Definition 2.6 (Clarke Subdifferential), Suppose that function f Rd + IR is locally Lipschitz around a point x and differentiable on TR: \ W where W is set of measure zero. Then, the Clarke subdifferential of f at æ is (()) & cvxhull {lim, Vf(())) æt + æ, at & WJ. where cvxhull denotes the convex hull of set.
Clarke subdifferential o (x) is a convex hull of all possible limits of fx(,) as 2 approaches æ. can be thought of as extension of gradient to nonsmooth function. It is also known that for convex function f. the Clarke subdifferential of f is equal to the subgradient of f.
Using the definition of Clarke differential, we now define virtual gradient map and virtual loss of f, which can be employed for understanding the convergence of SAM.
Definition 2.7 (Virtual Gradient Map/Loss). For differentiable function f IR - R, define the f/(m) virtual gradient map G IRd + Rd of f to be Gy(z) & V PIVs(())I) Additionally, if there exists function Jj Rdd R whose Clarke subdifferential is well-defined and ÖJz(2) e ( for all æ, then we call f a virtual loss of f.
If a virtual loss y is well-defined for f. the update of SAM (2) on f equivalent to (sub)gradient descent update on the virtual loss (z) which means, Zt+11 = H ( The reason why we have use Clarke subdifferential smooth function f. there are cases where the virtual gradient map Gy is discontinuous and the virtual loss Jy (if exists) nonsmooth; the discussion below Theorem 3.1.
define the virtual loss because even for differentiable and
Note that if the differentiable function f is oinedimensional (d = 1). the virtual loss (x is always well-defined because it can be obtained by simply (Lebesgue) integrating (z). However, in case of multi multi-dimensional functions (d > 1). there no such guarantce, although G is always well-defined. We emphasize that the virtual gradient map G5 and virtual loss Jj mainly used for better intuitive understanding of our (non- noo--jconvereence results. formal proofs, we use them for analysis only if J is well-defined.
Lastly, we note that Bartlett et al. [4] also employ a similar idea of virtual loss. In case of convex quadratic objective function f(x), the authors define u, (-1)'x; Øx and formulate (different) virtual loss [u) such that SAM update on f(æ,) is equivalent to GD update on Jy (uz).
Convergence Analysis Under Deterministic Settings
In this section, we present the main results on the (non-Jconvergence of deterministic SAM with constant perturbation size and gradient normalization. We study four function classes: smooth strongly convex, smooth convex, smooth nonconvex, and nonsmooth Lipschitz convex functions.
3.1 Smooth and Strongly Convex Functions
For smooth strongly convex functions, we prove a global convergence guarantee for the best iterate.
Theorem 3.1. Consider 3-smooth and p-strongly convex function J- If we run de- terministic SAM starting at Zo with any perturbation size > O and step size n = to minimize f, we have
22 min PT max { (1, 8"pp" 23
=0(esp/
uT
36 02
min (O......)
f(x.) - - = = @xxxp
2/
A
1T2
The proof of Theorem 3.1 can be found in Appendix B.2. As for relevent existing studies, Theorem 1 of Dai et al. [13] can be adapted establish the convergence guarantee f(xT) f Ô (7), by
selecting the step size 77 = min + max { 1, log AAT
}} and employing similar proof
technique as ours. We highlight that Theorem 3.1 achieves faster convergence rate compared to the concurrent bound by Dai et al. [13]. Moreover, Theorem 11 of Andriushchenko and Flammarion [2] proves the convergence guarantee for this function class: || "=12 O (exp(-T)). but assuming
5

---

SAM without gradient normalization, and the boundedness of Here, we get slower convergence rate of O (exp(-T) - + 7 but with any p > 0 and with normalization.
By viewing SAM GD virtual loss, we can get an intuition why SAM cannot achieve exponential convergence. Consider a smooth and strongly convex function: f(z) = ! One possible virtual
loss of f is (z) 1/2 (ar + psign(x))) which is a nonsmooth and strongly convex function, for which the exponential convergence of GD impossible [8].
Indeed, we can show that the sublinear convergence rate in Theorem 3.1 is not an artifact of our analysis. Interestingly, the Ô (cxp(-T) + Tiz rate given Theorem 3.1 is right in terms of T. up to logarithmic factors. Our next theorem provides lower bound for smooth strongly convex functions.
Theorem 3.2. Suppose 2 2 For any choice of perturbation size p. step size y, and initialization Tgg, there exists differentiable, 3-smooth, and pusttrongly convex function f such that
39p2
min f(x)) fp" L (E(O....T)
1222
holds for deterministic SAM iterates.
For the proof of Theorem 3.2, refer to Appendix B.3. By comparing the rates in Theorems 3.1 and 3.2, see that the two bounds are tight in terms of T and p. The bounds are bit loose in terms of 3 and μ., but we believe that this may be partly due to our construction; in proving lower bounds, we used one-dimensional quadratic functions as worst-case examples. more sophisticated construction may improve the tightness of the lower bound, which is left for future work.
3.2 Smooth and Convex Functions
For smooth and convex functions, proving convergence of the function value to global optimum becomes more challenging, due to the absence of strong convexity. In fact, we can instead prove that the gradient norm converges to zero.
Theorem 3.3. Consider a 3-smooth and convex function f. If we run deterministic SAM starting at /22
To with any perturbation size p > O and step size 11 minn {
to minimize f, we have
13 pT
23
Σ T-1 Vf = (0 AA
A VT
+
The proof of Theorem 3.3 is given in Appendix B.4. As for relevant existing studies, Theorem 11 of Andriushchenko and Flammarion [2] proves the convergence guarantee for this function class: f - f = O (+), where E indicates the averaged æ over T iterates, while assuming SAM without gradient normalization and bounded p. Here, we prove weaker result: a convergence rate of O stationary points, albeit for any p 0 and with normalization.
One might expect that a reasonably good optimizer should converge to global minima smooth convex functions. However, it turns out that both showing convergence to global minima and finding a non-convergence example are quite challenging in this function class.
Indeed, we later show non-convergence examples for other relevant settings. For stochastic SAM, we provide a convergeee example (Theorem 4.4) the same smooth and convex function class. showing that the suboptimality gap in terms of function values cannot have an upper bound, and therefore rendering convergence to global minima impossible. For deterministic SAM in nonsmooth Lipschitz convex functions, we show example (Theorem 3.6) where convergence to the global minimum is possible only up to a certain distance proportional to p.
Given these examples, we suspect that there may also exist a non-convergence example for the determinstic SAM in this smooth convex setting. We leave settling this puzzle to future work.
3.3 Smooth and Nonconvex Functions
Existing studies prove that SAM (and variants) with decaying or sufficiently small perturbation size p converges to stationary points for smooth nonconvex functions [2, 18, 27, 31, 35]. Unfortunately, with constant perturbation size p. SAM exhibits different convergence behavior: does not converge all the way to stationary points.

---

Theorem 3.4. Consider a 3-smooth function f satisfying f = inf f(x) > -0. If we run deterministic SAM starting at wo with any perturbation size p > and step size 17 B to minimize we have
1
T T- -
AA
S SO
+ B²
Refer to the Appendix B.5 for the proof of Theorem 3.4. For comparison, Theo- rem of Andriushchenko and Flammarion [2] proves the convergence for this function class: E fxx)]1 = O (t), but again assuming SAM without gradient normalization, and boundedness of Our Theorem 3.4 guarantees ((+) convergence up to additive factor 3 p².
One might speculate that the undesirable additive factor p²p²² is an artifact of our analysis. The next theorem presents an example which proves that this extra term in fact unavoidable.
Theorem 3.5. For any p 0 and yj S B. there exists a B-smooth and (3p)--iisccitt continuous function such that, if deterministic SAM initialized at point Do sampled from a continuous probability distribution, then deterministic SAM converges to a nonstationary point, located at distance of (p)) from a stationary point, with probability
Here we present a brief outline for the proof of Theorem 3.5. For a given p. consider a ome-dimensional function f(x) = 25 sin
Figure 2(a) demonstrates the virtual loss for this example. By examining the virtual loss Jy and its stationary points, observe that SAM iterates 2t converge to non-stationary point, located at a distance of (p) from the stationary point. This means that the limit point of SAM will have gradient norm of order 1((3p), thereby proving that the additive factor in Theorem 3,4 is tight in terms of p. A detailed analysis of Theorem 3.5 is provided in Appendix B.6.
99p"
3p
Remark: why do we ignore = 2(})) As the reader may have noticed, Theorem 3.5 only considers the case 1) O()), and hence does show that the additive factor is inevitable for any choice of 1) > 0. However, one can notice that if ())), then we can consider a one-dimensional -(tt)-str convex quadratic function and show that the SAM iterates blow up infinity. For the same reason, in our other non-convergence results (Thcorems 4.2 and 4.4), we only focus on " ((3
3.4 Nonsmooth Lipschitz Convex Functions
Previous theorems study convergence of SAM assuming smoothness. The next theorem shows an example where SAM on nonsmooth convex function converges only up a(p) distance from the global minimum x". This means that for constant perturbation size p. there exist conver functions that prevent SAM from converging global minima. Appendix B.7, we prove the following:
Theorem 3.6. For any p > O and r < 7f, there exists a nonsmooth Lipschitz convex function such that for some initialization, deterministic SAM converges suboptimal points located at a distance from
of (p) from the global minimum.
4 Convergence Analysis Under Stochastic Settings
In this section, we present the main results on the convergence analysis of stochastic SAM, again with lime-invariane (constant) perturbation size p and gradient normalization. We consider both types of stochastic SAM: n-SAM and m-SAM, defined in Section 2.2. We study four types of function classes: smooth strongly convex, smooth convex, smooth nonconvex, and smooth I. Lipschitz nonconvex functions, under the assumption that the gradient oracle has bounded variance of a² (Assumption 2.5). Our results in this section reveal that stochastic SAM exhibits different convergence properties compared to deterministic SAM.
4.1 Smooth and Strongly Convex Functions
Theorem 3.1 shows the convergence of deterministic SAM to global optima, for smooth strongly convex functions. Unlike this result, we find that under stochasticity and constant perturbation size p. both n-SAM and m-SAM ensure convergence only up to an additive factor ((p))
Theorem 4.1. Consider a 3-smooth, j-strongly convex function J, and assume Assump-
tion 2.5. Under n- n-SAM, starting at zo with any perturbation size > O and step size n
7

---

(a)
(b)
(c)
Am
(d)
(c)
Figure 2: Examples virtual loss plot for deterministic and stochastic SAM. The graph drawn in green indicates f, and the graph drawn in blue indicates Jf (or E.Jy). Red arrows indicate the (expected) directions of SAM update. The (expected) updates are directed to red stars. (a) f and J in Theorem 3.5. (b) f and its component functions f(1), f(2) Theorem 4.2. (c) EJj, and its component functions J Jaa,, J,r,) in Theorem 4.2. (d) f and its component functions f()), f(2) in
Theorem 4.4. (e) 1 and its component functions y J in Theorem 4.4, For the simulation results of SAM trajectories on these functions, refer to Appendix D.
min
pT max {1, log
1AAT
}}
to minimize J, we have
23
NT
Bi0²
B32
2/82p²
(((TT)- Ō
exp
A
2,3
122
1
Under m-SAM, udditionally assuming 1(:EE) is 3-smooth for any &, the inequality continues to hold.
For the proof, please refer to Appendix C.2. Theorem 4.1 provides a convergence rate of Ö to
28
global minima, but only up to suboptimality gap
If & 3p, then Theorem 4.1 becomes:
P
UT 28
+ 2.3²
Bf(xr) - 5 exp
thereby showing a convergence rate of O (exp(-I)) modulo the additive factor.
For relevant existing studies, Theorem of Andriushchenko and Flammarion [2] proves the conver- gence guarantee for smooth stochastic SAM without gradient normalization, and perturbation size P decaying with In contrast, our analysis shows that the convergence property can be different with normalization and constant p.
functions: IEf(x, - f = O (7). but assuming
The reader might be curious if the additional O(p²) term can be removed. Our next theorem proves that the case of high gradient noise (a Bp), m-SAM with constant perturbation size p cannot converge to global optima beyond suboptimality gap R(p²), when the component function [æx;{) smooth any g. Hence, the additional term in Theorem 4.1 unavoidable, at least for the more practical version m-SAM.
Theorem 4.2. For any p > 0,9 0,830,00 0,
3p and S 108. there exists a 3-smooth and $ -sstrongyy
convex function I satisfying the following. (1) The function I satisfies Assumption 2.5. (2) The component functions E(:E) of f are 3-smooth for any &. (3) we m-SAM on initialized inside

---

a certain interval, then any arbitrary weighted average a of the iterates Lo. 21 Blf(E) f (2(p²).
must satisfy
Here we provide a brief outline for Theorem 4.2. The in-depth analysis is provided in Appendix C.3. Given p 0, 3 > 0, o > 3p, we consider me--imensional quadratic function f(x) whose component functiin (x:; {) is carefully chosen satisfy the following for I E [ 13p
f(x) - [[(+=))
_ 1 (x;EE) - 30 10
10
8
(a:
7p
6
with probability 3
x
5
(x Te 2
otherwise.
For values of x outside this interval [6 1. each component function [(x; takes the form of strongly convex quadratic function. Figures 2(b) and 2(c) illustrate the original and virtual loss function plots of [(x; E). The local concavity of component function plays a crucial role in making an attracting basin in the virtual loss, and this leads to an interval
[6
1327 bounded away from the 6
global minimum 0, from which m-SAM iterates cannot escape.
For this scenario, we obtain f(x;) f 2(p²²) and [[+( ||2 2(p²)) for all iterates. From this, realize that the additive factor in Theorem 4.1 for m-SAM is unavoidable in the Bp regime, and tight in terms of p. Moreover, the proof of Theorem 4.2 in Appendix C.3 reveals that even in the o 3p case, analogous example gives ||2 x=1 (p)) for all iterates; hence, m-SAM fails to converge all the way to the global minimum in the small a regime as well.
4.2 Smooth and Convex Functions
We now move on to smooth convex functions and investigate the convergence guarantees of stochastic SAM for this function class. As can be guessed from Theorem 3.3, our convergence analysis in this section focuses on finding stationary points, Below, we provide a bound that ensures convergence to stationary points up to additive factor.
Theorem 4.3. Consider a B-smooth, convex function f. and assume Assumption 2.5. Under n-SAM, starting at To with any perturbation size p > O and step size = min
v/
7 23 to
v Vilaz 1o22-ppp11,
minimize f, we have
T- B[V) o 0 T
3A
32p
+ 482
VT
Under m-SAM, additionally assuming ((:EE) 8-smooth for any &, the inequality continues to hold.
The proof of Theorem 4.3 can be found in Appendix C.4. Theorem 4.3 obtains a bound of O (
modulo an additive factor 4 p². Similar to Theorem 4.1, if S Sp, then Theorem 4.3 reads
T-1 I EIV = o 31
+ 4.8pp²
T
hence showing a convergence rate of (++) modulo the additive factor. Since the non-convergence example in Theorem 4.2 provides a scenario that B|| f((((())))'' = 2(p²) for all f, we can see that the extra term inevitable and also tight in terms of p.
Theorem 4.3 sounds quite weak, as it only proves convergence to a stationary point only up to an extra term. One could anticipate that stochastic SAM may actually converge global minima of smooth convex functions modulo the unavoidable additive factor. However, as briefly mentioned in Section 3.2, the next theorem presents a counterexample illustrating that ensuring convergence to global minima, even up to an additive factor, is impossible for m-SAM.
> O, and 1j S z. there exists a 3-smooth and convex function satisfying the following. (1) The function I satisfies Assumption 2.5. (2) The component functions E(:E)) of f are 3-smooth for any &. (3) If we m-SAM f initialized inside a certain interval, then any arbitrary weighted average & of the iterates 2o. T1.... must satisfy (ff(() - -f* 2 C, and the suboptimality gap C' can be made arbitrarily large and independent of the parameter p.
Theorem 4.4. For any p > 0, B >
Here, we present the intuitions of the proof for Theorem 4.4. As demonstrated in Figures 2(d) and 2(e), the local concavity of the component function significantly influences the formation of attracting

---

basins in its virtual loss, thereby creating a region from which the m-SAM updates get stuck inside the basin forever.
Also note that we can construct the function to form the basin at any point with arbitrary large function value (and hence large suboptimality gap). Therefore, establishing upper bound the convergence of function value becomes impossible in smooth convex functions. A detailed analysis for the non-convergence example is presented in Appendix C.5.
4.3 Smooth and Nonconvex Functions
We now study smooth nonconvex functions. Extending Theorem 3.4, we can show the following bound for stochastic n-SAM.
Theorem 4.5. Consider a B-smooth function f satisfying S = inf [(x) > -o,, and assume
Assumption 2.5. Under n-SAM, starting at ao with any perturbation size p O and step size
min
VA
to minimize f. we have
23
BA T
a
E B[ so
+ p²ppp.
The proof of Theorem 4.5 is provided in Appendix C.6. Notice that the non-convergence example presented in Theorem 3.5 (already) illustrates scenario where E| f(z,)= !(p²), thereby confirming the tightness of additive factor in terms of p.
The scope of applicability for Theorem 4.5 is limited to n-SAM. Compared n-SAM, m-SAM employs a stronger assumption where E. By imposing an additional Lipschitzness condition on the function f. m-SAM leads to similar but different convergence result.
Theorem 4.6. Consider a B-smooth, L-Lipschitz continuous function f satisfying f infz I f(x) > -o, and assume Assumption 2.5. Additionally assume I(., {) is B-smooth for any &. Under m--SMM starting at vo with any perturbation size > and step size 1]
to minimize f, we VA
have
1 Σ
V VB + +13) L2)
- - 0o
+ +.83pp
T 1=
VT
Corollary 4.7. Under the setting of Theorem 4.6, we get
[B] so ( +1))0²+ EE (E(O....TT
1/4
+ (1+ v5) Bp.
min
T1/4
The proofs for Theorem 4.6 and Corollary 4.7 are given in Appendix C.7. Since Theorem 3.5 presents an example where B|| fxx))l (2(p) and E( (
8p) = ?(p²), we can verify that the
additive factors in Theorem 4.6 and Corollary 4.7 are tight in terms of
As for previous studies, Theorems 2, 12, and 18 of Andriushchenko and Flammarion [2] prove the convergence of n.m-SAM for smooth nonconvex functions: + E (x))) 0 ) but assuming SAM without gradient normalization, and sufficiently small For m-SAM on smooth Lipschitz nonconvex functions, Theorem of Mi et al. [27] proves $ Ei E / (xx)) δ )
while assuming decaying p. From our results, demonstrate that such full convergence results impossible for practical versions stochastic SAM.
5 Conclusions
This paper studies the convergence properties of SAM, under constant p and with gradient normaliza- tion. We establish convergence guarantees of deterministic SAM for smooth and (strongly) convex functions. To our surprise, we discover scenarios in which deterministic SAM (for smooth nonconvex functions) and stochastic m7-SAM (for all function class considered) converge only up to unavoidable additive factors proportional to p². Our findings emphasize the drastically different characteristics of SAM with vs. without decaying perturbation size. Establishing tighter bounds in terms of 3 and μ., or scarching for non-convergence example that applies to 1--AM might be interesting future research directions.
10

---

Acknowledgments
This paper was supported by Institute of Information & communications Technology Planning & Evaluation (ITTP) grant (No. 2019-0-00075, Artificial Intelligence Graduate School Program (KAIST)) funded by the Korea govermment (MSIT). two National Research Foundation of Korea (NRF) grants (No. NRF-2019R A5A 1028324, RS-2023-0021 (132)) funded by the Korea government (MSIT), and a grant funded by Samsung Electronics Co., Ltd.
References
[1] A. Agarwala and Y. N. Dauphin. Sam operates far from home: eigenvalue regularization as a dynamical phenomenon. arXiv preprint arXivv2302.08692, 2023.
[2] M. Andriushchenko and N. Flammarion. Towards understanding sharpness-aware minimization.
In International Conference on Machine Learning, pages 639-668. PMLR, 2022.
[3] D. Bahri, H. Mobahi, and Y. Tay. Sharpness-aware minimization improves language model generalization, arXiv preprint arXiv:2110.08859, 2021.
[4] L. Bartlett M. Long, and O. Bousquet. The dynamics of sharpness-aware minimization: Bouncing across ravines and drifting towards wide minima. arXiv preprint 1rX0v:2210.01513, 2022.
[5] K. Behdin and R. Mazumder. Sharpness-aware minimization: An implicit regularization perspective. arXiv preprini arXiv:2302./1886. 2023.
[6] K. Behdin, Q. Song, A. Gupta, A. Acharya, D. Durfee, B. Ocejo, S. Keerthi, and R. Mazumder. msam: batch-avergeed sharpness- minimization. arXiv preprint arXiv:2302.09693 2023.
[7] J. M. Borwein and A. S. Lewis. Convex analysis and nonlinear optimization: Theory and examples, 2010.
[8] S. Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ Machine Learning, 8(3-4):231-351 2015.
[9] X. Chen, C.-J. Hsich, and B. Gong. When vision transformers outperform resnets without pre-training or strong data augmentations. arXiv preprint arXiv:2106.01548, 2021.
[10] H. Clarke, Y. S. Ledyaev, J. Stern, and P. R. Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008.
[11] J. M. Cohen, Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. arXiv preprint arXiv:2103.00065. 2021.
[12] E. M. Compagnoni, Orvieto, Biggio, Kersting, F. Proske, and A. Lucchi. An sde for modeling sam: Theory and insights. arXiv preprint S3t::23001.08033. 2023.
[13] Y. Dai, Ahn, and Sra. The crucial role of normalization in sharpness- minimization. arXiv preprint arXiv:2305. /5287, 2023.
[14] L. Dinh, Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets, In International Conference on Machine Learning, pages 1019-1028, PMLR, 2017.
[15] J. Du, H. Yan, J. Feng, J. T. Zhou, I.. Zhen, R. S. M. Goh, and V. Y. Tan. Efficient sharpness- aware minimization for improved training of neural networks. arXiv preprint 2rXiv:21 2021.
[16] Foret, A. Kleiner, H. Mobahi, and B. Neyshabur. Sharpness-awan aware minimization for efficiently improving generalization. arXiv preprint arX1v:2010.01412, 2020.
[17] Hochreiter and J. Schmidhuber. Simplifying neural nets by discovering flat minima. Advances in neural information processing systems, 7, 1994.

---

[18] W. Jiang, H. Yang, Y. Zhang, and J. Kwok. An adaptive policy to employ sharpness- aware minimization. In The Eleventh International Conference on Learning Representations, 2022.
[19] Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishman, and S. Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv: arXiv:1912.022 19t..0212...... 2019.
[20] J. Kaddour, L. Liu, R. Silva, and M. Kusner. When do flat minima optimizers work? In Advances in Neural Information Processing Systems, 2022.
[21] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-hatch train- ing for deep learning: Generalization gap and sharp minima, arXiv preprint arXiv: 160..04609004366 2016.
[22] H. Kim, J. Park, Y. Choi, and J. Lee. Stability analysis of sharpness aware minimization, 2023. URL. https:://///. / /arxiv..vvvvvvv////v/ wwweriiii....oeeeeeeeeeeeeoeeeee aa//a/ss/3300 22011/000..........
[23] H. Kim, Park, Y. Choi, W. Lee, and J. Lee. Exploring the effect of multi-step ascent in sharpness-awee aware aware minimization. arXiv preprint arXivv2332..0113 2023.
[24] J. Kwon, J. Kim, H. Park, and I. K. Choi. Asam: Adaptive sharpness- aware minimization for scale-invariant learning of deep neural networks. International Conference on Machine Learning, pages 5905-5914, PMLR, 2021.
[25] H. Lee, H. Cho, H. Kim, D. Gwak, J. Kim, J. Choo, S.-Y. Yun, and C. Yun. Enhancing generaliza- tion and plasticity for sample efficient reinforcement learning, arXiv preprint arXiv:2306.1077 10711, 2023.
[26] Y. Liu, S. Mai, X. Chen, C.-J. Hsieh, and You. Towards efficient and scalable sharpness- minimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12360-12370, 2022.
[27] Mi, L. Shen, T. Ren, Y. Zhou, X. Sun, R. Ji, and D. Tao. Make tharpness-wwar minimization stronger: A sparsified perturbation approach. arXiv preprint arXtv:2210.05177, 2022.
[28] T. Möllenhoff and M. E. Khan. Sam optimal relaxation of bayes. arXiv preprint arXiv:2210.01620, 2022.
[29] B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro. Exploring generalization in deep learning. Advances in neural information processing systems, 30, 2017.
[30] Y. Shi, Y. Liu, K. Wei, L. Shen, X. Wang, and D. Tao. Make landscape flatter differentially private federated learning. arXiv preprint arXiv:2303. 1242, 2023.
[31] H. Sun, L. Shen, Q. Zhong, L. Ding, S. Chen, J. Sun, J. Li, G. Sun, and D. Tao. Adasam: Boosting sharpness-awe aware minimization with adaptive learning rate and momentum for training deep neural networks. arXiv preprint arXiv:2333.0055 2023.
[32] Wang. Z. Zhang, Z. Lei, and I.. Zhang. Sharpness-aware gradient matching for domain generalization. arXiv preprint arXiv:2303. 20333333,.,033, 2023.
[33] K. Wen, T. Ma, and Z. Li. How does sharpness minimization minimize sharpness? arXiv preprint arXiv:2211.05729, 2022.
[34] X. Zhang, R. Xu, H. Yu, H. Zou, and P. Cui. Gradient norm aware minimization seeks first-order flatness and improves generalization. arXiv preprint arXiv:2303.03108 2023.
[35] J. Zhuang, B. Gong, L. Yuan, Y. Cui, H. Adam, N. Dvomek, S. Tatikonda, J. Duncan, and Liu. Surrogate gap minimization improves sharpness-awar aware training. arXiv preprint 2203v:2203.088 08065, 2022.
12

---

Contents
Introduction
1.1
Summary of Our Contributions
1.2
Related Works: Convergence Analysis of SAM
1.3
Notation
2
Sharpness-Aware Minimization: Preliminaries and Intuitions
2.1
Sharpness-Aware Minimization (SAM)
2.2 SAM under Stochastic Settings
2.3 Function Classes
2.4
SAM as GD on Virtual Loss
3
Convergence Analysis Under Deterministic Settings
3.1 Smooth and Strongly Convex Functions
3.2 Smooth and Convex Functions
3.3 Smooth and Nonconvex Functions
3.4 Nonsmooth Lipschitz Convex Functions
4
Convergence Analysis Under Stochastic Settings
4.1
Smooth and Strongly Convex Functions
4.2 Smooth and Convex Functions
4.3
Smooth and Nonconvex Functions
10
5
Conclusions
10
More Details on the Related Works of SAM
15
Proofs for (Non-JConvergencee of full-batch SAM
16
B.1 Additional Function Class and Important Lemmas
16
B.2 Convergence Proof for Smooth and Strongly Convex Functions (Proof of Theorem 3.1) 17
B.3 Lower Bound Proof for Smooth and Strongly Convex Functions (Proof of Theorem 3.2) 18
B.4 Convergence Proof for Smooth and Convex Functions (Proof Theorem 3.3)
B.5 Convergence Proof for Smooth and Nonconvex Functions (Proof of Theorem 3.4)
21
B.6 Non-convergence for Smooth and Nonconvex Function (Proof of Theorem 3.5)
22
B.7
Non-convergence for Nonsmooth and Convex Functions (Proof of Theorem 3.6).
23
Proofs for (Non-)Convergence of Stochastic SAM
26
C.I Important Lemmas Regarding Stochastic SAM
26
C.2 Convergence Proof for Smooth and Strongly Convex Functions (Proof of Theorem 4.1)
27
C.3 Non- Non-Convergence of m-SAM for Smooth and Strongly Convex Function (Proof of Theorem 4.2)
29
C.4 Convergence Proof for Smooth and Convex Functions (Proof of Theorem 4.3)
32
13

---

C.5 Non-Cone Converggeee of m-SAM for a Smooth and Convex Function (Proof of Theo- rem 4.4)
33
C.6 Convergence Proof for Smooth and Nonconvex Function under n-SAM (Proof of Theorem 4.5)
36
C.7 Convergence Proof for Smooth Lipschitz Nonconvex Function under m SAM (Proof of Theorem 4.6 and Corollary 4.7)
37
Simulation Results of SAM on Example Functions
14

---

A More Details on the Related Works of SAM
Sharpness and Generalization Hochreiter and Schmidhuber [17] propose an algorithm for finding low-complexity models with high generalization performance by finding flat minima. Keskar et al. [21] show that the poor generalization performance of large-batch training is due to the fact that large-batch training tends to converge to sharp minima. Jiang et al. [19] empirically show correlation between sharpness and generalization performance.
Motivated by prior studies, Foret et al. [16] propose Sharpness-Aware Minimization (SAM) that focuses finding flat minima by aiming (approximately) minimize (*) max [ <) instead of f. Empirical results [3, 9, 16, 20, 25] show outstanding generalization performance of SAM on various tasks and models, including recent state-of-the-an models such as ViTs, MLP-Mixers, and T5.
Other Theoretical Properties of SAM. Bartlett et al. [4] prove that for quadratic functions, SAM dynamics oscillate and align the eigenvector corresponding to the largest eigenvalue of Hessian, and show interpretation of SAM dynamics as GD on a "virtual loss". Wen et al. [33] prove that for sufficiently small perturbation size p of SAM, its trajectory follows sharpness reduction flow which minimizes the maximum eigenvalue of Hessian. Dai et al. [13] examine the properties of SAM with and without normalization. They specifically focus on the stabilization and "drift-along- minima" effects observed in SAM with normalization, which are not present in SAM without normalization. Compagnoni al. [12] derive a continuous time SDE model for SAM with and without normalization, and employ the model to explain why SAM has a preference for flat minima. Furthermore, they demonstrate that SAM with and without normalization exhibit distinct implicit regularization properties, especially for (V)T)-
Agarwala and Dauphin [1] prove that SAM produces Edge Of Stability [11] stabilization effect, at a lower eigenvalue than gradient descent, under quadratic function settings. Kim et al. [22] show that saddle point acts as an attractor in SAM dynamics, and stochastic SAM takes more time to escape saddle point than stochastic gradient descent. Behdin and Mazumder [5] study the implicit regularization perspective of SAM, and provide a theoretical explanation of high generalization performance of SAM.
While Agarwala and Dauphin [1], Behdin and Mazumder [5], Kim al. [22] provide useful insights on theoretical aspects of SAM, we point out that all proofs are restricted to SAM without gradient normalization in ascent steps. Considering the vastly different behaviors of SAM with and without normalization (Figure 1), it is not immediately clear whether these insights carry over to the practical version.
15

---

B Proofs for (Non-)Convergence of full-batch SAM
In this section, show detailed proofs and explanations regarding convergence of SAM with constant p. The SAM algorithm we consider is defined as a two-step method:
y: = 0t + Vi(a
a++1 mt (())
B.1 Additional Function Class and Important Lemmas
In this section, define additional function class to use in convergence proofs. We also state and prove a few lemmas that are used in our theorem proofs.
Definition B.1 Soolyak-Lojasiewicz, function f F satisfies μ-PL condition if there exists >> such that,
[f(x)]| 2 u(f(x) f*)
(4)
for all x E Rd.
It is well- that p-strongly convex functions are p-PL,, but not vice versa.
Lemma B.2. For differentiable and p-strongly convex finction f. we have
(V f(y:) - vf(z))) Z V (xx))l
For differentiable and convex function f, the inequality continues to hold with μ 0.
Proof. If a differentiable function f is p-strongly convex, then its gradient map æ + Vf(x) is μ-strongly monotone, i.c..
(y x. VVfx)) 2 plly =11 Yx, Rd.
Using this fact, we have
(V)(),), VS(()) (.())) = [((aa)]| P
(, V((z))
/|[/f>>)]l ||| Vs(1:) - Vs(mz))
[+(()))|
(y) - x4, Vf(v)) - vf(xx))
P
y: - - [((x))
and this finishes the proof.
Lemma B.3. For a 8-smooth and u-strongly convex function, with step size 1) S 1
2 we have
IVf((( 1228'p2
f(z++1) & f(x,) - -
2
For a 3-smooth and convex function, the inequality continues to hold with μ =
Proof. Starting from the definition of /-smoothness, we have
3
( & f(xx) + (V))))) 0e+1 - x.)) + |++1 =x,1" 1x11
2
= f(x,)) Ty / (x))) V/(ri)) + 722
/ (1))))1
2
-(wx)) TVV5(( V/(y)) vf(x.) + v)(z,))
+ n23
|V/(()) Vz(=)) + vf(x;))1
+ 173
f((x) ((())) Vf(.)) -(lx)))>\\((f))))))
VV(y.)) vf(x,))
2
16

---

+ 3
2 +1/31//))+++))((((((((())))) V/(m:) v
= -((x)) - - (1- 1/9
2 [ff(=))| 7 (1_11111_(()))))))__) Vf(v)) - vf(()))
3 [ - vf(x:))11.
+ 2
Since we assumed v S 25 both 17 (1- _2 2 and r7(1 - n 2 2/2 hold. Applying Lemma B.2
the above, we get
1123 Vf(y)) Vf(x))]
f(x++1) S f(x+))
" Vf(x))
mpp [V)()))]
2
2
2
S f(m))
"
Tppp
[V](()))]
y²8 (3 1yye mxel)²
2
3²230pp
= f(m))
7
nPP [[(=)
2
2
and this finishes the proof.
B.2 Convergence Proof for Smooth and Strongly Convex Functions (Proof of Theorem 3.1)
In this section, we prove Theorem 3.1, restated below for the sake of convenience.
Theorem 3.1. Consider a 3-smooth and p-strongly convex function f. If we run de- terministic SAM starting at Zo with any perturbation size p and step size n A'A 8"
max { lo, min MT
i1 28
to minimize f. we have
-(exp
30p²
min (E,.....TT)
f(x,) f = eexp
A
23
1
Proof. The proof is divided into two cases, based on the ffxx)) observed throughout the entire optimization process. the first case, the gradient norm ||V (xx))) at æ; sufficiently large for all / = ...... 1; in this case, we show that the SAM algorithm converges linearly. The other scenario corresponds to the case where there exists an iteration index E (O,..., 1} such that ||V (mx))l is smaller than certain threshold. In this case, we can show from the PI. inequality (4) that we are already close to global optimality.
From Lemma B.3, we have
1/
f( s f(x)) - VVxx)=)
nAP
2
2
Now, recall from Definition B.1 that j-sttrongly convex functions satisfy μ-PL inequaltiy (4). From this, get
3233pp2
n4p
f(x+1)) - < (1=)))((()))
[ +
(5)
2
Case 1: when [x;)), remains large. Let consider the first case, where [f(x))] 2
note holds for all = . - 1. In this case, (5) becomes
f(xx+1) - f s (1 (f(x)) f*),
which holds for all t O..... - 1. Unrolling the inequality, obtain
f(ØT) - f" < (1 (f(2o) f*).
Case 2: when some [Vx()) is small. In the other case where there exists t such that [ < n notice from p-PL inequality (4) that
32230p
f(x:) - = 2μ
[+(())
17

---

Therefore, combining the two cases, it is guaranteed that
172 p²
f(xz) - 5 (1- + E (O...T))
min
(6)
2413
We now elaborate how the choice of step size 1j = min { max log
" AT
results
8"p
23
in the convergence rate in the theorem statement. Naturally, there are four cases, depending on the outcomes of the min and max operations.
Case A: log
14 AAT 3"'p
1 and
AT log
AAA 13
S
Putting 1
+ JuT
log
(AATT 3"'p"
into (6),
2
p²
3 p
(4AAT2 86
min TT
f(x)) f I
log"
1272
Case B: log
# 2 8"
2 and
log
A' 1"
2
1
Substituting 1/
S
log
4 A'
2T
23
NT
3"pp"
to (6),
T
86p²
2
min
S(20)) - -
A
E O)......TT
2/3
2μ13
2/
3 82
[1 AT
S exxp
A
log²
2,3
2T1
30pp
Case C: log
AA'T"
32 1 and
1 nT
S
23
Putting 17 = nT
2
nT
log
L''T" /
into (6),
T
30p2
min 1E ().....TT
[(xt)) - - -
A
T
2T
p
AT2
T
36
8 p²
<
1
log
+
S
T
3 p2
21
1T522
Case D: log
[#'A7"
g0
< and
at
1
2
2
1
By substituting
28
<
nT
to (6) we obtain
T
ppp²
min (0....))
-ax) f 5
1
A
+
23
240
2,3
nT
8 12
exp
2,3
A
5T
Combining the four cases, we conclude
uT''
min f(x,) - fr Ō exp EE (O.....))
+
2
TTT
thereby completing the proof.
B.3 Lower Bound Proof for Smooth and Strongly Convex Functions (Proof of Theorem 3.2)
In this section, we prove Theorem 3.2, restated below for the sake of convenience.
Theorem 3.2. Suppose : 2 2. For any choice of perturbation size p. step size n, and initialization Lp, there exists differentiable, 3-smooth, and pu-strongly convex function J such that
p²
min f(x1) - f"= = =Ω 122
(O......)
holds for deterministic SAM iterates.
18

---

The proof is divided into three cases, depending on the step size. For each case, we will define and analyze one-dimensional function to show the lower bound. In doing so, without loss of generality we will fix an initialization Z0 because we can appropriately shift the function for different choices of rp.
1. For 17 S 2nT we show that there exists function f such that
min f(zz) f(z)) f- = p² 1
BE (O......)))
2. For 1 2n²
S n 3. we show existence of a function f that satisfies
min f(x)) - =2 8 P EE (E(.....TT) Th.
12T2
3. For 17 2 5.4 we show that there exists a function f succ that
3 112
min (O....))
f(x))- --=
Combining the three results, we can see that the suboptimality gap of the best iterate is at least
Q 8 T
hence proving the theorem. Below, we prove the statements for the three intervals.
Case 1: 17 S 2pT
1.
Consider a function
1 f(x) 2 2uur² 142., Vf(x) -(x p).
2 Sp. Note from the definition of f that for any 3t + p and (y() p(ze+ + p- p) p.z. Therefore, the Je p. we have 1/2 2g + P (xx)
Suppose start initialization To
2 ()(r))
112
first SAM update can be written as
I 0n
V (1 n/4) zz.
Since 1 7/ > 1- 2T 7, the inequality still holds and the same argument can be repeated for the second update, yielding
21 (21) = (1 - 11) x1 = (1 -1- n1)² zu.
In fact, (1 - n/)² 2 (1
TT 2 2 for all f. S T, so all the iterates up to or stay above p. Thus, for any = 0,.. ...... T, the iterate 2; can be written and bounded from below
82p n22
20 2
2 nn) 2o
Therefore, in this case, the suboptimality gap of the best iterate is at least
82p f())
3 p²
82
p²
up²
Bdp²
min f(x)) f" 2 EE (E......T?)
+
=
112
2n
11
2
13
1 S 17 s z. Consider function Case 2: 2nT
1
f(x) = B2², 4
Vf(x) Br. 2
Suppose we start initialization Fo
n8p
We are going to show that the SAM iterates oscillate
4-
n&p between + ndp Indeed, if x, 4-733 mm
then ( 0 and
113p + p =
4p
28p
and vf(2)) = 4- n13
4 1- 113
4 - nB
19

---

Then, after SAM update, we get
113ppp
2,3p
178pp
I+41 24 (VVVVVVV
11 4-13
4-113 -73
4 4-733
The same argument can be repeated to show that 2442 - -I++1 It. As a result, the iterates
oscillate between + n forever. In this case, the suboptimality gap is bounded from below by 43
min ((x) 5²2 2 8 nspp
32338pp
e (0.....
4 4- n/3
64
Applying 17 2 2nT yields
min f(xz) - f = =2 te
12T72
Case 3: 2 2 Consider a function
1 f(x) f(x)= 3300 vf(x) = Bz.
Let the initialization be xg = Se For any 24 2 0, we have yt = 2t + and vf(y) = B(xx + p). Then, the resulting SAM update becomes
1 It (y)) = - n3)=, - 7p (1 31
Since we have 17 2 3. we have 1- - n v -1 and I++1 has the opposite sign as and its absolute
value is least as large | We can similarly check that any further SAM update changes the sign and does not decrease the absolute value. Therefore, for all t t= 0, 0....,Ty T, we have | 2 |
Consequently, the suboptimality gap of the best iterate is at least
8ºp² 112
min f(x)) f 2 f(x0) - f(0) = S2
Remarks validity of lower bound. Lastly, comment why choose different functions and initialization for different choices of n and why suffices to provide a matching lower bound for Theorem 1. In convergence upper bounds in the form of Theorem 3.1, we aim to prove an upper bound on the following minimax risk:
inf sup ((A(f)), AEA
(7)
where A denotes the class of algorithms, F denotes the class of functions. and ((A(f) is the suboptinality measure for algorithm's 's output A(f) for function f. In the context of Theorem 3.1. our algorithm class A corresponds to the choices the "hyperparameters" 7) and wy of SAM, and the function class F here is the class analyzed by the theorem: the collection of 3-smooth and ju-strongly convex functions. From this viewpoint, Theorem 3.1 can be thought of as an upper bound on (7), with the choice of ((A(f) A min.. (zz) - f
Hence, showing matching lower bound for Theorem 3.1 amounts to showing matching lower bound for the minimax risk (7). For this purpose, suffices show that for each E A, there exists a choice of f E F such that certain lower bound holds. Therefore, we are allowed to choose different choices of f for each different choice of hyperparameters 7), p. and øy. In fact, in our proof, choose different choices of and æo for each different choice of 17, however, this is without loss of generality once we notice here that starting an algorithm at To to minimize f f() is equivalent to starting at 0 to minimize f(x Eg). Hence, even though choose different f's and 2o 's for different choices of 1y in our proof of Theorem 3.2, this is sufficient for providing a matching upper bound for Theorem 3.1.
Admittedly, some authors show stronger versions than what we show, where a single func- tion takes care of all possible hyperparameters. Indeed, such results provide lower bounds for eu inf AcLA (A(()). Recalling that sup inf S inf sup, one can notice that these sup inf lower bounds in fact much stronger than what suffices.
20

---

B.4 Convergence Proof for Smooth and Convex Functions (Proof of Theorem 3.3)
For smooth and convex function, we prove the convergence of gradient norm to zero. The theorem is restated for convenience.
Theorem 3.3. Consider a 8-smooth and convex function f. If we run deterministic SAM starting at Zo with any perturbation size p > O and step size 17 min
{
225
minimize f, we have 1
8a pT
Σ [())) T
1
0
A p
VT
Proof. Using Lemma B.3, for smooth and convex function have
f(x++1) S f(x)) 7 [xx))1 3²
2
which can be rewritten as Adding up the inequality for t O.....TT T and the dividing both sides by we get
2 (f(x)) - f(x++1)) + n130p [V(())]]
17
T Σ [f((=)]] < n/T (f(x)) f(xT)) + n1² p² ² S
2
A + n p²
(8)
T
n/T
We now spell out how the choice of step size 17 min rate in the theorem statement. There are two to be considered, depending the outcome of the min operation.
24 (v 3"pTT' 28 results in the convergence
Case
V
TT
S 23
Putting 1 =
PT
into (8), we get
1 T
2A33 2
2
2 2A33pp
(x;))
VT
VT
VT
Case B:
24 pTp2T
2
Substituting
S V
to (8) yields
23
28
FTT
43A
1
43A
3 0²
[
12
+ 3 $
T
23
T
VT
Merging the cases, we conclude
T-1
3A
A3
[f(x)))
T
VT
completing the proof.
B.5
Convergence Proof for Smooth and Nonconvex Functions (Proof of Theorem 3.4)
In this section, prove the convergence up additive factor BBpp 2 for smooth and nonconvex functions. The theorem is restated for convenience.
Theorem 3.4. Consider a 3-smooth function f satisfying == inf f(x) > -0. If we run
deterministic SAM starting Do with any perturbation size p 0 and step size B to minimize have
Σ
T-1 |Vf(x))|
3A T
+ B2p22
T
21

---

Proof. Starting from the definition of B- smoothhess, we have
3
f(x++1) & f(x)) n (.
V
2
113
f(xx))
fx;,)) !
マタ (V
1|2
+
2
V (1)))
2
2
V fxx,)) + n782
s f(x))
1 yrl1
2
V [ax))) + p=
= f(())
2
The inequality can be rearranged as
[V/((x;) (f(z)) ((x++1)) B²
Adding up the inequality for = O,....T , 1, and the dividing both sides by T, we get
2 (f(x)) + +
2A
nTT + B2
(9)
T
n/T
Substituting 7 = > to (9) yields
23A [[(x))] -
T 3
B.6 Non-convergence for a Smooth and Nonconvex Function (Proof of Theorem 3.5)
In this section, spell out the proof of our counterexample that SAM with constant perturbation size P provably fails to converge to a stationary point. Here we restate the theorem.
Theorem 3.5. For any p> 0 and r S 2.2 there exists a B-smooth and (3pp) -iischiit continuous function such that, if deterministic SAM initialized at point Dy sampled from a continuous probability distribution, then deterministic SAM converges to a nonstationary point, located at distance of (p)) from a stationary point, with probability
Proof. For x E IR, consider the following one-dimensional function: given p and B
93p²
55TT 3p +
f(x) = 25nr
sin
It is easy to check that this function is 8-smooth and 33p 5x
Lipschitz continuous. Also, let
X {a r = (0.3 + 0.6k) E Z},
which is the set of points where vx(x) 0. For SAM with perturbation size p. given the current iterate Ft, the corresponding y/: xt + [
[(re) is given by
P
if (-0.3 + 1.2k) < x; < (0.3 1.2k)p for some k E Z, if (0.3 + 1.2k)p < x < (0.9 + 1.2k) for some & E Z.
1/1 = 3e +
-P
0
o1 E X.
This leads to the following a virtual gradient map Gy:
382
5x
cos
3p
Ft
5m +
3
if (-0.3 + 1.2k) < < <0.33 + 1.2k)p for some Z,
Gy(xt) = (v))
382 5x
cos
5m 3p
Tz
3
if (0.3+ + 1.2k)p < x; < (0.9 1.2k) for some k E Z,
0
if X.
22

---

From this virtual gradient map, we can define
Y= {o (0.7 + 1. k 2) { (-0.1 + p. & E EZ)
and Y is the set of all points z where Gy(z) = 0 and V fx()) + 0.
Since f is one-dimensional function, virtual loss Jy can be obtained by integrating Gy. One possible example is
Jy(x) =
25x²
90pp sin
6T
3p
+
5x
if (-0.3 S - (0.3 + 1.2k) for some ls Z, if (0.3 + 1.2k)/ s x & (0.9 + 1.2k)p for some k E Z,
90pº
sin
5m
5m
25
3p
3
which is a piecewise B-smooth function that is minimized at points in Y and locally maximized at (non-differentiable) points in X. Since J is well-defined, we can view SAM as GD on Jy-
For sufficiently small 17 S 3 and any initialization 2o E R X, the initialization belongs to of the intervals ((-0.3 + 0.6k)) (0.3 + p.) For such small enough 7) we can guarantee that the SAM iterates will stay in the interval ((-0.3 + 0.6k)p. (0.3 + 0.6k)p) for all t 2 0. For example, suppose that 24 (-0.3p, 0.3p). Then, the next iterate will stay in the same interval and only
the image of the interval (-0.3p, 0.3p) under a map x x (-0.3p, 0.3p).
3n52 cos
a
Got is a subset of
5
3mpBp
5t
5π
x (-0.3p, 0.3p) C (-0.33p, 0.3p)
x
cos
x
+
3p
5π
c 22.2) m
2 3 cos
2
2
2
3
and the containment true if 1/8 < 1. By symmetry, the same argument can be applied to any intervals of the form ((-0.3 + 0.6k)p, (0.3 + 0.6k)p).
Thus, for any initialization zo R X, all SAM iterates stay inside the interval which xo belongs to. Inside the interval, by 8-smoothness of J,, the following descent lemma always holds:
( S Jy(x)) + (xx), re+1 - xz) + 3 || xel1?
=2
Jf(x)) [ no 2 |[Gy(z))11
Jz G
Therefore, if we add the inequalities up for 1 0, =.....; 1, we get
T-1
Σ (G)((=))12 < 3 (J,(zz) - (,(xT)) S 2 (J)(z)) - -J)) < 00, 17
where Jj A inf, (x) > -c. Since the inequality holds for all T, the series summable, which turn implies that (G,((x)) - 0 as L + cc. However, the only point the interval ((-0.3 0.6k)p, (0.3 + p) satisfying ||G](x)]| is the one in Y n ((-0.3 0.6k) (0.3 + 0.6k) Hence, if To E H \ X and 17 J. SAM must converge to a point in Y. Since æo is drawn from continuous probability distribution, 4o E R holds almost surely. This finishes the proof.
B.7 Non-convergence for a Nonsmooth and Convex Functions (Proof of Theorem 3.6)
For nonsmooth convex function, depending the initialization, SAM can converge to suboptimal point with distance (pp) from the global minimum. The theorem is restated for convenience.
Theorem 3.6. For any p > 0 and 1 < Tf, there exists nonsmooth Lipschitz, convex function f such that for some initialization, deterministic SAM converges to suboptimal points located at a distance of (p)) from the global minimum.
from
23

---

SAM
V2
Vi
(a)
(b)
Figure 3: (a) The demonstration of four seperate regions, and basis vectors of example function. (b) The trajectory of SAM for example function. As SAM enters region the update cannot get any closer to the global minima.
Proof. For æ (z(1), xz (2)) E R?? consider a
a 2-dimensional function,
f(x) max m [|z 11, (2x + 22()
(v), 02) can be established basis for R², with i1 e₁, and U2 - e| + 75 C2. Any
vector æ E IR2 can be uniquely expressed by vn and u2. Consider the region: {x b(')) +b ((2) 02 ((3) 0}.
This area can be partitioned into four separate regions.
Å f= = ((0) + 022)
- Te < ((1) < <0)
2
B: x (0)v + 6(2)o
((0) - To
- - (0) ( 60)) + v56(2) > >0}
C: f: (0))) + 662)22
6(1) 55) <0) fx -00)) + ((2) -b(1) + (5)(2) 0}
n nf ((0) b(2)
-2) V56 1p)
D: (x = ((0)) + b(2)
(()) < 0} (:00-AAUBB (AUBUC).
Figure 3(a) demonstrates the regions A, B, C, D, as well as the vectors and v2. When belongs to the set æ = 6 b(0) + b(2) ((1) < 0, we can examine four different scenarios.
Case A: x = -1000 + B(2) E A. x A
[V[[= and -Vy(y) are as follows.
v(())
α + p02,
-6() < 55612)
((1) V56(2) < -b()
y
101,
v56(2) b(1)
pu2,
v502,
-b(1) < 256(2)
fz)
/Ju2.
80) < / 56(2) < -00)
V5u2,
(5 B(1.
As result, the SAM updates V fz)) only affect U2, and does not affect on vn. Thus, if w, A, the next SAM iterate 2e+1 remains in
Case B: x = (()) v1 6(2) E B. We can verify that y = x + P PTV]( = x pu2. Therefore, -VS(y) --/5m Therefore, the SAM update shifts in the direction of U2. Hence, æ; E TB, the next SAM iterate will be T++1 (B (UCD.
Vi()

---

Case C: x = =b()2) + b E C. y= x + V/(a) [[]] = 2 - pol. 50
(V522,
((1) v56(2) < 6( +
-V((y))
b(t)) + < V5b(2) -b
U1
For 2; = (.11 01 + 6,8h 02 E C. bf < 55b < (4) + p. then SAM update shifts in the direction of 22, resulting in #++1 (BUCUD) Otherwise. the next SAM iterate a++1 shifts in the direction of +2g Consequently, #++1 can either remain in ID, or move to A.
Assume that 2++1 moves to A. Given that 0/
Tp for I2 C, we can verify that 6/41 2
7p Ba.Bd previous observation in Case A where SAM updates only affect U2 when
A, we can conclude that for all subsequent iterates 2; with i >> 1+1,, the condition b( < 7p +1 continues to hold.
Case D: x 8(2)) + B(2) E ID.
Vf(() y x + P PTV](T]] becomes
x p0z.
V5b(2) < B(1)
y
x
pul.
otherwise.
We check that fyy = V50y for all cases. So the SAM update shifts in the direction of +22- As result, if æ, E D. the next SAM iterate 2++1 will fall into 2z+1 E (BB U C ID).
Furthermore, we can verify that for x E (IB (BUCUD, 8(1) < <
Tp holds. Therefore, summing up (B DUCCUD, then Tp + n. Since the global minimum is located 2
all the cases, we can conclude that if the initial iterate æo is chosen from
all subsequent SAM iterates æ, will satisfy ((1)
at xx (0, 0), it follows that |z, x²1 70/2-11 m for every t >> O. Thus, for 1 If. we can ascertain that in this particular function, ||x, x²
v5
Te for every t >> 0, thereby proving that the distance from the global minimum is at least M(p). The trajectory plot of SAM on this example
4v5
function is illustrated in Figure 3(b).
25

---

C Proofs for (Non-)Convergence of Stochastic SAM
In this section, we provide in-depth demonstrations and proofs regarding convergence of stochastic
SAM with constant perturbation size The objective is defined as f(z) = E [=: E)}, where
represents a stochastic parameter (e.g., data sample) and ((=; {) represents the loss at point with
random sample ç. The update iteration for stochastic SAM is specified follows:
Y: = 2t + g(w))
#++1 - 02 - (1(())))
We define g(x) = {) and ī(x) = Vai E). where & and are stochastic parameters. Stochastic SAM comes in two variations: 1-SAM, where and are independent, and m-SAM, where & is equal to g.
C.1 Important Lemmas Regarding Stochastic SAM
In this section, we present a number of lemmas that are utilized in our theorem proofs regarding stochastic SAM. order to do this, we also introduce extra notation, ÿ 2t Vf(a)) deterministically ascended parameter.
as
Lemma C.1. For a differentiable and p-strongly convex f. we have
((=)) v((x))) 2 [ ī(y:) ī(b+)) + up For a differentiable and convex function f. the inequality continues to hold with μ = O.
Proof.
B(Vf(=)).0()) f(()))) (VV/ ((V vf(x))
(VV ((0.)) + (x; vf(z:))
(VV -(())) V(=)))
where we use Lemma B.2 in the last inequality, thereby completing the proof.
Lemma C.2. Under n SAM. for B-smooth and p-strongly convex function f. we have
B(V vf(x))) E[V[(())) + (f - -2322p².
Under m-SAM, additionally assuming ((:E) is 8-smooth for any & the inequality continues to hold.
Proof. First we consider n-SAM. Starting from Lemma C.I, we have
E B(Vf(z)) fxx))) 2 [(Vf(()), ((v)) ū(0:)) + (pEl
E(V/((;), V5(.)) () + /
2 El| V fx
E/I f(v) Vf(ii)) (pp)
2
1
,22
>
B fxx))l
Elyy
upB
f=;)))
2
1
g(w))
VS(x.)
=
2
2
+ /pE\\//(x)]]
- E[Vf uplE V -232p²
Next we consider m-SAM. additionally assuming I(:,E) is 3-smooth for any &, starting from Lemma C.I, we have
E B(Vf(x)) vf(x,)) 2 ((Vf(())) -())) + f(xx))
26

---

2 EE (x)))
B 3(0.))1 u Vf(x))
2
Z EIV (xx))?
Bl 9i11 + /p (
2
- 2 -
g(
Vf(z.)
E
2
[
+ /
z El +p -232p²
completing the proof.
Lemma C.3. Consider 8-smooth, j-strongly convex function f, and assume Assumption 2.5.
Under n-SAM, with step size 17 S 25' we have
Ef((+)) & - - -
nPP ( p2 32 3
Under m-SAM, additionally assuming ((:5) is B-sooohh any &, the inequality continues to hold.
Proof.
Starting from the definition of [-smoothness, we have
(x(++1) S Ef(x,) - - + 3 B1(i(1111
2
-Ef(x)) (B + Bllg(y)) [x(x))] + 1/8
3
EE| (xx))l
2
-1)3)(((((=)),))))))-- - -
= (B(
n²² El( (/ + 123
+
E [(,))(
2
2
+
V/(x,))
< <Ef(a,) - n(1 n3) ((v)) v((x)) -1 (1 1/
E| V f (xx)))1
+ + V 3E - vs(x))]12
$ <B((x)) nn1 33) vf(x)) 1/ ( 1133
E E [
+ 3 1 p²)
Since we assumed 5 23 17(1 1 - m13) 2 n/2 hold. Applying Lemma C.2, we get
- 1 \ 233
Ef(++)1) S {f(x;;) - 11(1 - 11))
1 (1 n3
E {]
+ 302 + $
2
-E/(
" E [V)x)) - ( n 1 V / (2x)) + 21183 0² 382 - 0²)
< <E(())
" [
74p E V (x)) + 2n p² 388 0² - -0²,
2
completing the proof.
C.2
Convergence Proof for Smooth and Strongly Convex Functions (Proof of Theorem 4.1)
In this section, we demonstrate the convergence result of stochastic SAM for smooth and strongly convex functions. For convenience, we restate the theorem here.
27

---

Theorem 4.1. Consider a B-smooth, p-strongly convex function f. and assume Assump- tion 2.5. Under n-SAM, starting at 2g with any perturbation size p 0 and step size nj
min 1 pr max 1, 1000-1Ap01 2: to minimize f. we have
1
- )
B|o²
2
Bs((T)) - S Ô exp
A
2,3
122
1
Under m-SAM, additionally assuming ((:5) is B-smooth any &, the inequality continues to hold.
Proof. We start the proof from Lemma C.3; in order to apply the lemma, additionally assuming
3-smoothness for component functions [(., E) is necessary for m-SAM.
Ef((++) 2 (x,) - [ I12 TPP E. [ 2n/ p² 12 -²²).
2
Since p-strongly convex functions satisfy p-PL inequality (B.1), we get
(f((++11) f S (Tf(())))))) -*) nup E V f(x))] p2 B -
Depending on the value of o, there are two cases in which the convergence rate varies.
Case a S 3p. In this case, we have
Ef(x=1) f s (1 (E)()) - f*) 1pp
E [ + 2n S (1 (a)()))) - f*)
2n p²,
and our choice of must be 23 Unrolling the inequality and substituting
28 draws out
2,3²p²
Bf(xr) - 1 S - m/14 (T 5*)
T
2
A +
2,3
kT
2,82 p
S exp
A +
23
Case B: > 3p. In this case, we have
B/(x++1) - - < (1 (p) - 1*) - nup
E1 [ (xx))) )1 + +2133pp + B - 8207)
2
< (1 m)) - 1*) + 2n13² p² + +123(00 -3213).
Again, unrolling the inequality draws out
2332p2
n)((22 32)
Ef(xr) - -f S (1 - +
+
(10)
Similar to Section B.2, substituting min { WT four cases.
max {1,
((00-184p2) ) }
u²AT
1 can result in
Case B-1: log AT M10--pPp7)
AT Blo -=2p=]
2 1, and
1
log
AT (Bo05)
Setting ?
23
pt
RT log
3(02 P2
3(02
BPP2)
1T log 3(02 - 8222)
2,3 p2
Ef(xr) - fp
+
+
2TT
1²T
17AT
PAT (100-B8'~3)
Case B-2: log 310--1PPp0
> 1, and
< pT
log
Setting 1 23
27
3(0² 3²0²)
1
2/2²p²
Ef(xT) - 8t S exp
A +
+
2,9
2
P
[KT
0 p²p²)
1¹2 AT
+ 2.3
S exp
A
+
log
2,3
TºT
3(0² - p2
28

---

Case B-3: log
1T B(02-1²p0t
S and
23 2
Setting 7) NT
1
T
3(0²
B²)²)
2
Bf((T)
-" 5
1
A
T
1²T
1
A 3(02 - -B2p²)
p²
1 T
log
B(0²²
322
P2T
A - 8 )²)
3 - B2p²)
203 p²
1TT
1TT
Case B-4: log ((021 S 1, and
1
S
Setting 1
28
nF
2
{ - p²)
1
2 p²
Ef(xT) f s exp
A
23
28
1
3 3²pp²)
2
exp
A
233
22T
Merging all four cases, we get
Bs(aT) - - 00=
(exp
nT
3
p²)
233
exp
A +
23
122
1b
thereby finishing the proof.
C.3 Non-Convergence of m-SAM for Smooth and Strongly Convex Function (Proof of Theorem 4.2)
In this section, we present a formal analysis of our counterexample, which shows that stochastic m-SAM with constant perturbation size p may fail to fully converge to global minimum, and can get close to the global minimum by only ((p). This counterexample indicates that the Opp)) term in Theorem 4.1 is unavoidable. For readers' convenience, we restate the theorem.
Theorem 4.2. For any p > 0, > 0, > 3p and 1 183. there exists a 3-smooth and @ -strrnngyy convex function f satisfying the following. (1) The function f satisfies Assumption 2.5. (2) The component functions V(: () of f are 3-smooth for any &. (3) If we run m-SAM on f initialized inside certain interval, then any arbitrary weighted average o of the iterates Fy T1.... must satisfy
([f(E) f 2 ((p²).
For E I, and constant > 0 which will be chosen later. Using these p. and a, we construct the counterexample. We consider a mieddmmesiional smooth strongly convex function
Proof.
Given 0, 3 > 0, 2 0. and 1 S 10 we choose y 2 3 c (1== 7)
3
f(x)
and the stochastic function {(x;)) can be given as
(z), with probability
((x;
((2)
otherwise,
where each component functions described below:
[ (x c 2p)² ap², x xSc-p c- p
(x)
- - - c)2,
[ - c 2p)² ap²,
p
P (g pa (I c 2p)² pap").
r x c c-c p
((9)x))
(gx² 2 (I c)2)
md
c-p5x5 x ctp c
(gx² 2 (I - 2p)² 2 pap²)
29

---

First, it is easy to verify that [x) = f(x). We can also confirm that f. f() are a-smooth, and ((0) is (1-gg) -smooth. Furthermore, | (xx) V (x)] & a² + c)² holds, along with (2p + c)². Consequently, we have [ v1(;;; <
[V](()) - (x))1 <
pa
1-p
pa 1-p (2p + c)² 2a²
(100)
2
where we used p = and (1 + P)
Now choose a - min
_ a
This choice ensures that f. fa), and f(2) are all 3-smooth, as 19 0² < o²² so the function satisfies Assumption 2.5. 5-6
5
5
desired. Also notice that 2a²..
19,7 6
< 2
For the remaining of the proof, we investigate the virtual gradient maps G and G within the specified region of interest: c-p S x S c+ p. We will then demonstrate that if we initialize m-SAM in this interval, all subsequent iterations of m-SAM will remain inside [c p, c pl. as required above.
(z) and the virtual gradient map Gaa of f(I)
Within this interval, the perturbed iterate y = P | (() can be described as follows.
< I P.
x + P.
-a(x + p c)2 <
y
Σ x > c,
0,
-a(x-- p p- c), > c. (x))) che we now calculate = P [|]])>>>]]|| and the virtual gradient map
Additionally defining Go of f(2).
x P. d, G)
c)), x x<d 1-p (r p pp-
y
J,
I d,
0,
1 x= d I-p (x + p + e))
x P.
x x>6
r x>d
Here, given c == (1+ + f) p. we can verify that
0
where 0, c', and are the global minimum (or maximum) of f. f(2), and f(), respectively.
Recall that < 5 Since 3 we have nja < 3 which will be useful for the rest of the proof. Now, we analyze 24+1, the next iterate of m-SAM. For p I S c p, the next iterate T of m-SAM using G Gyon is
Jt. + nu(x + p- p-c),
It <
24+1
Ft.
F1
Jt + na(x;; - p c)2
Ft. > c.
We will show that Tz+1 must stay within the interval [c P, + p). For the case D; = c, the inclusion is trivial. To analyze the rest, we divide into two cases.
Case A-l: c- p It <. Since nja
50
have
S 2t I Tt41 24 + na(a: + +p- c) s c c
3p
= =c nap S c
50"
Case A-2: c <1 S c p.
Since na S 50 we have
c+ p æt Zt+1 2τ na(ai p p- c + malc- p- c)
3p
= c - nap 2 c
50"
Cases A-1 and A-2 show that F141 also remains in (c - P, c + p). when we update m-SAM using Gyas (2x).
30

---

Jr
p
Jp
-2
(8)
(b)
Figure 4: The original and virtual loss plot for the example function in Theorem 4.2. The graph drawn in purple and red are the original/virtual loss of component functions. The graph drawn in green indicates f. and the graph drawn blue indicates J. (a) and its component functions f(), f(2). y and its component functions J JJL,, Jes.
We next examine the case involving Gyay The next iterate rt++1 of m-SAM using Ge (ft) (11)) is
p + p( - -- c)) It d Ft 1) 11- (xt
Tt, 82 71-p (xt + p + p( 2 c))
d
Dt > d.
Again, we divide it into two cases, since the 2₁ = c' case obvious.
Case B-1: c- p S Jz. < d. Since (1 + p)xx - (1+ +ppppp pc < 0 for H E |c p. c'), we have
c p S zt I++l It 17 - p
((1 + ((1+p).r (1 + p)p ppc)
17 a( + p)
+1 a(1 + p)
ap
p n
p
1 p
p
Since nja S
3 50. we have
allpp 1 - 1) 1-p
- 5naa 2 0, so
a(1 +
Ft + a(1 p))
up
7) --p p
p 11
1- p a(1 +
p
a(1 + +p)
ap
1
c' c'+1) 1 1-p p+ 17
1-p
1-p
a(1 + p)
= + 1
1-p p c' 4 +nop < + s
Case B-2: d < 84 S c P. Since (1 + p) + (1+ p)p pc for s4 E (c, c + p). we have
c p 2 xt 2 It+1 I2- " p
p)., (1 +1+ p)p pc)
2d -
a
((1 (p)c + (1 + ppp-pp)
1
P
a(1 + p)
1
"
p == = c-
c 5nap
I+ p
1 -
I+p
1
(1+
2 5npp
p
1+p
3
3
p = c
10
31

---

where the last inequality used rja -
3 50'
Cases B-1 and B-2 demonstrate that 2+++1 also remains within the interval [c p, + p) when
update m-SAM using Gras
To gain better intuitive understanding, we provide Figures 4(a), 4(b), demonstrating the original and virtual loss functions of f()) and f(8). In Figure 4(b), we can examine that m-SAM updates generate an attraction basin in fos, thereby making a region that m-SAM cannot escape.
The aforementioned case analyses indicate that when the initial point zn falls within the interval [c P, + pl. all subsequent iterations of m-SAM will also remain within this interval, regardless of the selected component function for updating. Given (1 +) p o.p we can conclude that all subsequent iterations of m-SAM are points located at distance of least & from the global optimum, for any 3 > 0, p > 0, and a > 0.
Moreover, in case of a > Bp, it follows that f(x) = gx²² = o0 Consequently, the suboptimality gap at any timestep is at least
f(x))- = f(x))= 2 f (6) 2(Bp²),
thereby finishing the proof.
C.4 Convergence Proof for Smooth and Convex Functions (Proof of Theorem 4.3)
In this section, we establish the convergence of stochastic SAM for smooth and convex functions to near-stationary points. For case of understanding, we provide the thcorem statement here.
Theorem 4.3. Consider a B-smooth, convex function f. and assume Assumption 2.5. Under n-SAM, starting at Fo with any perturbation size p > 0 and step size min
JA
to
minimize f, we have
D =
1 T-
BA T +
VB
320 A
+ 4,8²p²
T 10
VT
Under m-SAM, additionally assuming [(-EE) 3-smooth for any the inequality continues hold.
Proof: We start from Lemma C.3 with 0. In order to do this, additionally assuming 3-smoothness of component functions I(:,E) is necessary for m-SAM.
E (x < [xx)))) 7 "EI[V/(= +23 - -82---ppp)
-3²p²),
which can be rewritten as
((,,)( (B (Bf(x;) - (.f 433 4883 =2 - -82p?)
11
Adding up the inequality for 0, ... TT 1, and dividing both sides by T, get
2 T/T
fxx))1
< (Ef((x)) -
+ + + 28m1( 22 82
2
< n/T A + 432 + -
(11)
The convergence rate varies depending on different cases determined by the value of a.
Case A: a S 3p. In this case, it must hold that =
1
By this choice of f, we have
23
T-
2A
Σ [ <
+ 4 p2
1/T'
43A
+ 4
32

---

Case a > Bp.
Setting min {
23 we consider two cases.
1
Case B-1: V /Ba0-
A
S 2/
Putting B102-3
A into (11), we get
T-1
Bl0² - -32p2)
E V 1 4V
4 p
T
Case B-2: V B10 p2
2
1 20'
Placing 1j = 28
into (11), we get
43A
1
Σ
+2 4.8 p² 22
3(0 -
T
2B
43A
T
+
+482p
0² +2
V
3(0² - BB
Bl0²² - -320²)
43A
Bl02 3/
+
+21
+ 4z
T
Merging the two cases, we conclude
T-1
BA
V3l02 - B2D2A
Σ
+
+ +4,32p²
T t=0
T
VT
thereby completing the proof.
C.5 Non-Convergence of m-SAM for Smooth and Convex Function (Proof of Theorem 4.4)
In this section, we provide in-depth analysis of our counterexample, which demonstrates that stochastic m-SAM with constant perturbation size P can provably converge to a point that is not global minimum. Furthermore, the suboptimality gap in terms of the function value can be made arbitrarily large, hence indicating that proving convergence of m-SAM to global minima (modulo some additive factors O(p²)) is impossible. The theorem is restated for convenience.
Theorem 4.4. For any p > 0, B > 0, o O, and 1j S }. there exists a 3-smooth and convex function satisfying the following. (1) The function f satisfies Assumption 2.5. (2) The component functions ((11)) of f are 3-smooth for any &. (3) If we run m-SAM on f initialized inside a certain interval, then any arbitrary weighted average of the iterates Do, $1,... must satisfy [[) ff" 2 C, and the suboptimality gap C can be made arbitrarily large and independent of the parameter
Proof. Given > 0, 3 0, a > 0, we set an arbitrary constant > 5g and parameter a. > 0
which will be chosen later. For x IR, consider a one-dimensional smooth convex function,
x
x < 0
f(x)
ax,
T 0
and (x;;)) can be given as
[x)) (1)),
with probability p otherwise,
1x:
where the functions (() and (2) given by the following definitions.
2a [ c +
+
x 5
2a [ c +
0 r c- 4 2 < c +
(x)
(x
2a r c
c f S
33

---

7 for 2pa (r c +
+ 8
1-p (ar 2pa (r c +
050 1
(x)
1-p ar + 4pa (x c)²
c s o
p
I-p (ar + 2pa (r c - 9)
c+ i
It can be verified that f()] is mmxx
{ 8a 1-p {)] -moothh 8a [)))) -moothh, and f(2) is mmx {
p
Moreover, [V - ( (x)]1 S 9n² holds, as well as [V](() v (x)) S 9a²
p²
2)
Consequently, [ - g [2))]] - 9a²
I-p'
By selecting > 1.2 and setting a = min Bp(l-p) TvT=p) 3/P f. we can check that E1; {) = f(x),
and the component functions are 3-smooth. Additionally, f satisfies Assumption 2.5.
In the following analysis, we examine the virtual gradient maps Gaa; and G yoa) in the specified region of interest: c p S x S c+ p. For this specific interval, we are going to show that if we start m-SAM inside this interval, then all the subsequent iterates of m-SAM must stay inside the same interval [c- - p. p.c+1. pl.
In this region, y = x + P ( (a) and you
follows.
(x)
I P. c-psa<<
y
T,
1 =
I P. c< r sctp p.
Se (x + - c), c- p 9SI5 S c
32
I
2a,
c- 32 SI<c
4
G)a)(z)=
x=c
2a,
c <<<sc+ 30
Se (xt
- c)
c+ T S s
30
Additionally defining d' a c 8p;
P
we can compute y = x + p {/00/ر) [-))
and G faa as follows.
c- ps x <d
x,
2 ==c
x x P.
d d<ssctp p.
a-2op c-ps <d
T-P
G Gym
0,
x=(
a+2an 1-p
<<rsctp. p.
Now recall that 77 S 3. Given that a < next iterate Z141 of M-M using G Gyo (zx) for p z cc p
3p(1-p) we can derive 1) S 3
< 2. 1e 8p
Furthermore, the
8p
xt +
80 (x + c- p S 34 S c
3p
4
Ft 2na,
- rr <C
T+41 = F4 12-1/6 n/1
Ft.
8 =
Ft 2nja
c < 84 S c
It + 80 (x p p-
c+ 30 < x1 c p.
We will now show that 1 must remain in the interval obvious. Dividing the rest into three cases,
|e - p,c p). For the case H. c, it is
Case A-1: e- -p c 3. Since 0 S n 8a (x: + p-
c) S 2na S p.
1-p <
we have
4p 4,
p S x < t S + 0
sctp. p. 4
which proves that xt-1 also remains in (c p,c + p).
34

---

19)
41
5-
(b)
Figure 5: The original and virtual loss plot for the example function in Theorem 4.4. The graph drawn purple and red are the original/virtual loss of component functions. The graph drawn in green indicates and the graph drawn blue indicates E. (a) and its component functions f()) f(2). (b)E.Jy and its component functions J JAZ,, J
Case A-2: 32 Sxx C c J4 set S.. Since 0 S 2na S p.
1-P
g. have
4p
p S S rt+l S sax + S c
therehy proving that 2441 also remains in (c p,c p).
Case A-3:
3p 4 x, sct p. Since 0 2 nj. p
Sa (st p- -2na -p-
1-p 4p
2
P.
have
p S F4 S r+41 So. sctp.
which shows that I++1 also remains in |c - c pl.
We next consider the case of G G(v) The next iterate r+ of m-SAM using G Goos(z)) for c Tt + p given by
1-2p 1-p
c- S 21 <d
I It -1- (())
Pt.
Ft d
21
na
142p I-p
< z1 S c c.p.
Again, the F4 c' case is trivial. Considering the remaining two cases,
Case B-1: ps xr d. Since 0 2 na
1-29 1-p 2 p
1-2p > -cc p d)), we get 8p
S xt S F141 S I₁ + (c + p c) s ct
which indicates that Te+1 also remains in [c- 0, c + p).
Case B-2: d' < ds S + p. Since < na T-p
1+22 < p 1+22 < d' - (c p). we have
c-pSo; + (c p) S 8t- S xt S c
which shows that 1 also remains in |c p, c p..
The case analyses above indicate that if xo is initialized in |c- c p]. the subsequent iterates of m-SAM also remain in p, + pl, regardless of the component function chosen by m-SAM for update. Figures 5(a) and 5(b) demonstrate the original loss function and virtual loss function of component functions (()) and f(2), Due to the concavity of (1)), basin of attraction is formed in Ja,, thereby creating region where the iterations of m-SAAn SAM cannot escape.
35

---

Therefore, the suboptimality gap at any timestep is at least
a(c p) + (
a²
f(x)) [(=)) 1 f(c-
23"
Therefore, regardless of iterate averaging scheme, the suboptimality gap in terms of function value will stay above a(c p) + 23
Moreover, this suboptimality gap can be made arbitrarily large if we choose larger values of c; notice that с > 5p is the only requirement on c. Consequently, is impossible to guarantee convergence to 4 global minima, even up additive factor, for m-SAM. This finishes the proof.
C.6 Convergence Proof for Smooth and Nonconvex Function under n-SAM (Proof of Theorem 4.5)
In this section, we establish the convergence result of stochastic n-SAM for smooth and nonconvex functions. For convenience, we restate the theorem.
Theorem 4.5. Consider 3-smooth function f satisfying f = inf f()) cc, and assume
Assumption 2.5. Under n-SAM, starting at x with any perturbation size p > O and step size
" min
J
to minimize J, we have
25
BA T
ABO2A
Σ
B
50 so
+ B2
T T=
VT
Proof. Starting from the definition of B-smoothness, we have
3n2 (1))(1))1
Bf((++1) < (.. 7/B (V/(()))
S [8f()))) T/É V/(x)) Br) || Bl1 -- (2).))1
< Ef(()) - 7/ V
[x.() [ --" ( -v(x))
+ V.
3'1
S <Ef()) 2 2 11
+
12 + 302n²
2
82p2n -B0211²
= Ex(x)
2 / fxx))
2
Rearranging the inequality, we get
E [[ ) v (R.((x.) (B(++))))++ + 32 2
Adding up the inequality for 0, , 1, and dividing both sides by T, we get
2 (L)( EE(xT)) 3 + 230
(x;))
<
1/T
2A
<
+ 83pp² + 2.02n.
(12)
nT
Substituting 77 min
VA
(12), we get two cases.
28
VTBra
Case A: 23
1 <
V
23. so we have
TTpa"
2A
<
+ B 0² 2
T/
36

---

43A
VA
+
280²
+ BBp
T
VT
45A
2V
3
+ 4
T
VT
Case B:
TB00
V
23
"1
v
VT
V
and it leads
1
T-1
24
V
(xxe)]
+ B²22²² + +280'n
T
1/T
2vA
VTD002 + B0"A
1
+ 82
T
VT
3020
+ $22
VT
Merging two cases, we can conclude that
1 T-1
BA
VBO2A
T [[]
Σ
so
+ +.80p,
T
VT
thereby completing the proof.
C.7 Convergence Proof for Smooth Lipschitz Nonconvex Function under m-SAM (Proof of Theorem 4.6 and Corollary 4.7)
In this section, the convergence proof for stochastic m-SAM for smooth, Lipschitz, and nonconvex functions presented. The notation ÿJ = xt + [(..)] restated for convenience.
f((m,) is used here once again. The theorem is
Theorem 4.6. Consider a B-smooth, L-Lipschitz continuous functtion f satisfying f inf,, f(x) > -O,, and assume Assumption 2.5. Additionally assume I(., {) is B-smooth for any &. Under m-SAM, starting at Dy with any perturbation size > and step size 1) LByO to minimize f. we
VA
have
1 E +
VB + L2) VT
3p) 0
+ p.
1=
Proof. The proof technique resembles Mi et al. [27]. Starting from the definition of B-smoothness, we have
Ba7
< Ef((x)) (x)+1)
(22)( +
2 E1
< <f(())) - ((y:) Vs(a.)) - 317 E (1:))
2
Ef(() -
((DO) - -VB(VS Vf(.V-/V(VVVV
+ Brj² E( 112
< (x.)())))
Tall V [1x))11 + 7 [ +
+ "B((ū(U)) - 2(
[f(x)]] (0: =x). Vl(i:) V.(aa)) )
Bn7
+
El
2
82 E |3 Uill + nE
[3|| [((())(a))I
+ Bu
< <Ef(x)))
"
V f(x:))
-l - -=a11²]
E
2
2
32 p2p2n
g(x:)
Vf(x))
< Ef(())
+ "FIV
+ +3pmB///((a>1l
2
[[ī(()))
[[(x)]]]
37

---

Bnj
min " [ p2 + ( + 3T²
< (xx)
2 Bll
2
7 f((lV)( - 3p) 2 32 p'n + (B) Bl -
< (x)()))
2
< <Ef())) ( Bp)2 B p2n + (o² + 1.3)
Rearranging the inequality, we get
[ [[IV/()))) - Bp) 1 (E (xx) - ([((++))) + 5,3² p² + 28n(o² + L2).
Adding up the inequality for 0.... T 1, and dividing both sides by T, we get
[[[V\((>))]1 1 Bp) v T/7
(B)(())) (f((TT))++++ + 53 + 20 + 122
2A
+ 5,32p² +28n(02+111
(13)
n/
Substituting
VA to (13) yields
VBla2-130 LAyT
Σ (IV((=)))) -pp)
S
4 A + 122
+ +533pp
VT
thereby completing the proof.
From the result of Theorem 4.6, Corollary 4.7 can be derived. The corollary is restated for the ease of reference. Corollary 4.7. Under the setting of Theorem 4.6, we get
[= 0o [8A(0] + +11) 1/4 ) (1+ v5) Bp.
min x (E......TTT
T1/4
Proof. Starting from the result of Theorem 4.6, we have
[[] - -8p)
s min
(IV - [p)]]
IE (E......T))
(E......TT
$ [(.v)()) Bp)21
/BA + L2)
50
+ p.
VT
Taking the square root both sides,
(BA(02 + I.2I) 1/4
min Vf BpI} so
+ V53p.
LE
T1/4
Rearranging the inequality, we obtain
( (
min (E........
[f(x)) 5o
+ (1+ v5) Bp.
T1/4
thereby completing the proof.
38

---

0.15
SAM Iteratis
SAM Earatiss
000
10
11
(a)
(b)
(c)
200
1.60
170
110
1700
706
215
1020 2210
140%
2500
280 3000
170
(d)
(c)
(f)
Figure 6: The results of the SAM simulations on the example functions. The yellow line indicates the trajectory of SAM iterates. (a) and (d) display deterministic SAM iterates (with initialization To = 0.4) and the plot of x-coordinate values over epochs, for a smooth nonconvex function as shown in Figure 2(a) under settings in Theorem 3.5. (b) and (e) show m-SAM iterates (with initialization 20 = 4) and the plot of x-coordinate values over epochs, for the smooth strongly convex function as shown in Figure 2(b) under settings Theorem 4.2. (c) and (f) demonstrate m-SAM iterates (with initialization
9) and the plot of x-coordinate values over epochs, for the smooth convex function as shown in Figure 2(d) under settings Theorem 4.4. All plots empirically verify that practical SAM cannot converge all the way to optima. Instead, the iterates get trapped in certain regions.
D Simulation Results of SAM on Example Functions
Figure 6 shows the results of SAM simulations on the example functions considered in Sec- tions 3 and 4. It demonstrates that SAM indeed does not converge in worst-case example constructions.
39


Reviews:
[{"review_id": "bLACKyVkjf", "reviewer": "Reviewer_AJAE", "summary": "This paper examines convergence properties of sharpness-aware minimization, which is an empirically-popular algorithm for training deep neural networks, yet whose theoretical properties are poorly understood. This paper makes several contributions to the analysis of sharpness-aware minimization, which are novel in this growing literature.\n\nFor smooth and convex functions, this paper proves that the best iterate of SAM converges to the global minimizer. This is expected as, for such functions, there exists a global minimizer; thus, even after perturbations, the convergent point should still be the global minimizer.\n\nFor smooth and nonconvex functions, this paper proves that there is an additional bias term in the convergent point compared with a local minimizer. Furthermore, a lower bound example is constructed, showing that this bias term is necessary.", "questions": "- I wonder if the authors could discuss the practical implications of their findings. For example, how does the extra bias term affect the empirical performance of SAM; Does it inject some kind of regularizer that is actually helpful for the empirical performance, or is it possible to design a better algorithm that eliminates this bias term altogether?\n\n- There is a concurrent paper that studies a very related question:\n\nDai, Y., Ahn, K., & Sra, S. (2023). The Crucial Role of Normalization in Sharpness-Aware Minimization. arXiv preprint arXiv:2305.15287.\n\nIt would be helpful if the authors could discuss the relation to this paper.", "limitations": "The authors discuss the limitations of their results along with presentations in the main text. The potential societal impact of their work should be minimal, given the technical nature of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is nicely written and provides enough background knowledge for readers to understand the topic. For each theorem, the authors accompany their results with a sketch of the high-level proof arguments.\n\n- The lower-bound examples are especially interesting in terms of complementing the convergence rates.", "weaknesses": "- The results in the main text are a bit dense. It would be easier to read if the paper is formatted in a more friendly manner.\n\n- There are no experiments/simulations to complement the theoretical results. I consider this a limitation since SAM is primarily motivated as an empirically-successful algorithm, so a connection between theoretical results to their practical implications would be important for this audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for dedicating their time in evaluating our paper. Your interest in our lower bound examples is deeply appreciated. Below, we provide our responses addressing the raised questions.\n\n> **Weakness 1. The results in the main text are a bit dense.**\n\nThank you for providing insights on enhancing readability. We are making an effort to address this matter to improve the quality of our paper.\n\n> **Weakness 2. There are no simulations to complement the theoretical results.**\n\nWe have conducted supplementary simulations for the toy functions utilized in the non-convergence theorems. These simulations corroborate the validity of our theoretical proofs through empirical evidence. The results of these simulations are presented in the PDF file attached in the \"global response\". Moreover, the simulation result for the non-convergence in nonsmooth convex functions can be found in Figure 4 of Section B.6.\n\nWe would greatly appreciate it if the reviewer could take a look at these results. If these supplementary experiments are deemed insufficient, we are open to any valuable suggestions for further experimental verification.\n\n> **Question 1. Practical implications of our findings.**\n\nWe would appreciate it if you could refer to our response of Question 2 in the \"global response\".\n\n> **Question 2. Relation to [1].**\n\n[1] delves into an examination of the contrasting characteristics between SAM and USAM (SAM without normalization). They particularly focus on the stabilization property of SAM and USAM, i.e., SAM can converge with a wider range of $\\eta$ than USAM. Additionally, they study on the \"drift-along-minima\" phenomena observed in SAM, wherein SAM tends to continue drifting along a manifold of minima, while USAM easily gets stuck at a minimum. In contrast to the results in [1], our paper focuses more on the (non-)convergence properties of SAM pertaining to finding global minima or stationary points.\n\nHaving said that, the two papers indeed have a couple of directly comparable results too. In the discussion of stabilization (Theorem 1) in [1], the authors show that for $\\mu$-strongly convex $\\beta$-smooth functions, the iterates of SAM converge to a local neighborhood around the global minimum $x^*$. This theorem can be adapted to establish a convergence guarantee of $f(x_T)-f^* = \\tilde{O}(\\frac{1}{T})$, achieved by selecting step size $\\eta = \\mathrm{min}\\\\\\{\\frac{1}{\\mu T} \\mathrm{max}\\\\\\{1, \\log(\\frac{\\mu^2 \\Delta T}{\\beta^3\\rho^2})\\\\\\}, \\frac{1}{\\beta}\\\\\\}$ and employing a proof technique similar to ours. It is worth highlighting that Theorem 3.1 in our paper achieves a **faster** convergence rate for the same function class: $\\tilde{O}(\\frac{1}{T^2})$.\n\n---\n[1] Dai, Y., Ahn, K., \\& Sra, S. (2023). The Crucial Role of Normalization in Sharpness-Aware Minimization. arXiv preprint arXiv:2305.15287."}, {"review_id": "N94MdVNplM", "reviewer": "Reviewer_NH1R", "summary": "This paper studies the convergence properties of sharpness-aware minimization in a specific setting with the use of gradient normalization and arbitrary constant perturbation. The paper established convergence rates for both deterministic and stochastic SAM with various assumptions on the convexity of the objective function. The authors argue the term $\\mathcal{O}(\\rho^2)$ appearing multiple times in their bounds is in fact unavoidable by establishing corresponding lower bounds.", "questions": "- General questions:\n  -  The paper considers SAM with constant stepsizes and gradient normalization and this setting seems to be a common choice in practice. However, I do think more justification for this setting is needed, especially when [1] derived faster convergence rates for SAM without gradient normalization.\n  - It seems no methodological conclusions for the implementation of SAM are provided in the paper. Based on the results in this paper, (how) should we decrease the perturbation $\\rho$ in the algorithm so that the additive term $\\mathcal{O}(\\rho^2)$ would be resolved and thus the convergence be faster?\n\n- Small issues:\n  - There is only one lower bound result in Table 1, which looks weird to me. \n  - In line 830, does \"Assumption 4.2\" refer to Theorem 4.2?\n\n[1] M. Andriushchenko and N. Flammarion. Towards understanding sharpness-aware minimization. In International Conference on Machine Learning, pages 639–668. PMLR, 2022.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to follow.\n- The analysis covers different levels of convexity.\n- The author proves lower bounds to justify their proposed convergence rate.", "weaknesses": "- The proof of the upper bounds seems to have followed that of [1].\n- Several cases are left out, including the lower bound for the smooth and convex case of deterministic SAM, and the lower bound for the smooth and strongly-convex case of stochastic SAM with small variance.\n- Generalization is not considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for devoting their time to evaluate our paper. Here are our responses to the weaknesses raised.\n\n> **Weakness 1. Comparison with [1].**\n\nOur proofs might share similarities with those in [1]. However, our analyses overcome unique difficulties and hence different from [1]; allow us to elaborate below.\n\nFirst, our paper takes the normalization term into consideration, which is not addressed in [1]. This introduces certain unfavorable terms throughout the proof procedure. One obvious example can be found in line 772. If we ignore normalization, we would have gotten the term $\\lVert\\rho g(x_t) -\\rho \\nabla f(x_t)\\rVert^2$, which can be easily bounded using Assumption 2.5. However, our paper incorporates the normalization term, leading to a completely different expression: $\\lVert\\rho\\frac{g(x_t)}{\\lVert g(x_t)\\rVert}-\\rho\\frac{\\nabla f(x_t)}{\\lVert\\nabla f(x_t)\\rVert}\\rVert^2$, thereby rendering the analysis more challenging.\nAs a result, employing different techniques (rather than approaches found in [1]) becomes crucial to address these unfavorable terms.\n\nDue to these distinctive terms that specifically emerge in our study, many techniques from [1], such as the Lyapunov function method in Theorem 11, cannot be seamlessly transferred to our framework. In cases where these methods are not applicable, we construct an alternative strategy, such as a finely-tailored multi-case analysis based on the values of $\\rho$, $\\eta$, or $\\lVert\\nabla f(x_t)\\rVert$ (One of the examples that use an alternative method is showcased in Section B.2).\n\nSecond, the upper bounds presented in our work hold true for all $\\rho>0$. In contrast, every theorem in [1] relies on critical assumptions, like bounding $\\rho$, decaying $\\rho$, or requiring $\\rho$ to be sufficiently small. Establishing the results under less restrictive assumptions on $\\rho$ naturally requires employing distinct proof techniques.\n\n> **Weakness 2. Two cases of lower bound are left out.**\n\nWe acknowledge that the lower bound for smooth and convex functions in deterministic SAM has not been addressed in this work and is reserved for future investigations.\n\nRegarding the case of lower bound for smooth and strongly-convex functions in $m$-SAM with small variance ($\\sigma\\leq\\beta\\rho$), a modification to the proof of Theorem 4.2 allows us to at least establish a lower bound for the distance to the global minimum, denoted as $\\lVert x_t-x^* \\rVert$.\n\nIn line 827, we can modify the selection of $a = \\frac{\\beta}{5}$ and instead choose $a = \\frac{\\sigma}{5\\rho} \\leq\\frac{\\beta}{5}$. The validity of the proof remains intact with this revised choice of $a$, even when $\\sigma \\leq \\beta\\rho$. Consequently, when the initial point $x_0$ falls within the interval $[c-\\rho,c+\\rho]$ (where $c=\\frac{7}{6}\\rho$), all subsequent iterations of $m$-SAM remain within this interval. This observation indicates that even under the condition $\\sigma\\leq\\beta\\rho$, an analogous example demonstrates $\\lVert x_t-x^* \\rVert=\\Omega(\\rho)$ for all iterates.\n\nOf course, this lower bound leads to a similar lower bound on the function value: $f(x_t)-f^* = \\Omega(\\sigma \\rho)$. Nonetheless, we omitted this lower bound, as it does not tightly match the factor $O(\\rho^2)$ in the upper bound. However, it is worth highlighting that at least, even in the regime of small $\\sigma$, $m$-SAM does not achieve convergence all the way to the global minimum.\n\n> **Weakness 3. Generalization not considered.**\n\nWe would appreciate it if you could refer to our response of Question 1 in the \"global response\".\n\n> **Question 1. Justification for this setting.**\n\nSAM is commonly employed in real-world applications, while USAM (SAM without gradient normalization) serves as a theoretical variant designed for theoretical analysis and isn't used practically. As our paper focuses on practical settings, it is natural that we study SAM instead of USAM.\n\nFurthermore, USAM shows drastically different behaviors compared to SAM. This distinction is illustrated in Figure 1, where we can observe that USAM has a trajectory closer to GD than SAM. Also, [2] investigates the differences between SAM and USAM, such as the stabilization property (SAM can converge with a wider range of $\\eta$ than USAM) or the \"drift-along-minima\" phenomena (SAM tends to drift along a manifold of minima, while USAM gets stuck at a minimum). So, it is reasonable to regard USAM as an entirely different optimizer when compared to SAM, and hence natural to expect different convergence properties.\n\nHence, it is crucial to notice that the faster convergence rates in [1] for USAM do not imply similar convergence properties for SAM. Our paper specifically addresses the relatively unexplored convergence behavior of SAM under practical setups.\n\n> **Question 2. (How) Should we decrease $\\rho$?**\n\nWe would appreciate it if you could refer to our response of Question 2 in the \"global response\".\n\n> **Issues.**\n\nFor Table 1, some lower bound results have been excluded as they do not provide rates with respect to time $T$. Instead, they demonstrate that the additive factor of $O(\\rho^2)$ in upper bounds are unavoidable, thereby having different characteristics compared to the lower bound result (Theorem 3.2) presented in Table 1.\n\nThank you for pointing out the typo in line 830. The correct reference should be \"Assumption 2.5\", which indeed holds within the interval $[c-\\rho,c+\\rho]$.\n\nWe sincerely hope that the reviewer finds our response convincing, and we would appreciate it if the reviewer could consider re-evaluating our score. Thank you again for the helpful feedback.\n\n---\n[1] Andriushchenko, M., \\& Flammarion, N. (2022, June). Towards understanding sharpness-aware minimization. In International Conference on Machine Learning (pp. 639-668). PMLR.\n\n[2] Dai, Y., Ahn, K., \\& Sra, S. (2023). The Crucial Role of Normalization in Sharpness-Aware Minimization. arXiv preprint arXiv:2305.15287."}, {"review_id": "MetOAjiUP7", "reviewer": "Reviewer_T74n", "summary": "SAM is a very practical algorithm for improving generalization in deep learning, however, even the convergence properties of SAM are not well understood. The paper studies the convergence/non-convergence of SAM under various standard setups in optimization, including smooth/nonsmooth, convex/strongly convex/nonconvex, deterministic/stochastic optimization problems. The results of this paper provide a detailed and complete description of the convergence of SAM for these problems.", "questions": "1. It seems that we only have the non-convergence result of stochastic SAM for smooth and strongly convex functions for m-SAM. Can we prove similar lower bounds for n-SAM? If not, I hope the authors can explain the underlying intuition. By the way, it is proper to say \"stochastic SAM for every function classes we consider, fail to converge properly\" in Line 359?\n2. I can not fully understand the purpose of Sec. 3.4 as well as Thm. 3.6. It seems that for merely convex objectives, gradient descent also fails to converge to a global minima? See the second inequality in Thm. 2.1.7 in Nesterov's celebrated book Lectures \non Convex Optimization\", Second Edition.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Compared with existing works, the paper analyzes SAM with fixed $\\rho$ and normalization steps, which is the algorithm that people use in practice. Under these practical configurations, this paper provides different characteristics of SAM.\n2. The upper bounds give sufficient conditions for the convergence of SAM and the convergence rate of the algorithm under these conditions. Additionally, this paper also provides lower bounds to show the tightness of their upper bounds in the dependency of certain important problem parameters such as $\\rho$ and $T$.\n3. I found the lower bounds very interesting and they provide many insights about SAM. In contrast to gradient descent (GD), the result in this paper shows that deterministic SAM (full-batch SAM) fails to converge to a  stationary point even for smooth nonconvex objectives. In contrast to stochastic gradient descent (SGD), stochastic SAM (m-SAM) even fails to converge to a global minimum for smooth strongly convex objectives. These results justify the limited capability of SAM in optimization and suggest the differences between SAM and other common optimizers such as SGD/Adam/RMSProp. \n", "weaknesses": "See the questions part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for their detailed evaluation of our paper. We are truly grateful for your interest in our lower bound results. The responses addressing the questions raised are outlined below.\n\n> **Question 1. Can we prove similar lower bounds for $n$-SAM?**\n\nIndeed, we have conducted empirical investigations using toy scenarios under $n$-SAM, and observed some scenarios that manifest the same non-convergence phenomenon observed in $m$-SAM. However, the current proof technique employed for establishing the lower bound of $m$-SAM does not readily extend to $n$-SAM.\n\nTo elaborate on the underlying intuition, in $m$-SAM, the same component function is employed during both the ascending and descending steps (for formal definitions of $n$-SAM and $m$-SAM, please refer to Section 2.2). This symmetry enables us to leverage the concept of virtual loss associated with each component function (component function within the context of stochastic optimization), illustrating how iterations can be trapped within a specific interval. In contrast, $n$-SAM can employ distinct component functions for its ascending and descending steps, rendering the virtual loss of each component function less applicable. Consequently, the existing proof technique cannot be seamlessly transferred to $n$-SAM, prompting the need for an alternative approach. Developing an alternative technique for theoretically establishing the lower bound of $n$-SAM could be a viable direction for future research.\n\nOne important thing to note, though, is that $n$-SAM is a theoretical variant of SAM, which have never been used in practice. In practical scenarios, it is predominantly $m$-SAM that has gained widespread adoption, as one can check from open-source implementations of SAM on GitHub (we wish we could provide pointers here, but links are not allowed!). Since our focus is centered on the practical settings of SAM, we believe that the absence of lower bound results under $n$-SAM does not significantly harm our paper.\n\nAlso, thank you for pointing out the subtle issue in line 359. The sentence should indeed be revised to \"stochastic $m$-SAM for every function classes we consider, fail to converge properly.\"\n\n> **Question 2. The purpose of Sec 3.4.**\n\nIn the preceding Sections 3.1-3.3, we study the convergence properties of deterministic SAM for smooth functions under different convexity assumptions. This leads us to wonder whether SAM can similarly provide convergence guarantees for nonsmooth functions. Following this curiosity, we investigate whether SAM can find global minima of nonsmooth convex functions; unfortunately, the answer is on the negative. In Section 3.4, we present a lower bound of $\\Omega(\\rho)$ on the distance of SAM iterates to the global minimum. This result highlights that, unlike smooth convex functions, SAM is unable to achieve global convergence in nonsmooth convex functions.\n\nIndeed, as noted by the reviewer, Theorem 2.1.7 in [1] shows a lower bound on the distance to the global minimum for a smooth convex function. However, the cited theorem has a fundamental difference in comparison to our Theorem 3.6. Importantly, the lower bound in [1] for gradient-based methods exclusively applies to early iterates: specifically, it applies to the range of iterates where $1 \\leq t \\leq \\frac{1}{2}(n-1)$, with $t$ is the iteration index and $n$ represents the dimension of the problem. On the contrary, our established lower bound for SAM holds true for all iterations, even when $t$ goes to infinity.\n\n---\n[1] Nesterov, Y. (2018). Lectures on convex optimization (Vol. 137, p. 576). Berlin: Springer."}, {"review_id": "gpKkpMXnAQ", "reviewer": "Reviewer_y8UR", "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:\n\n1. 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).\n\n2. 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.\n\nIn 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.", "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. ", "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.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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. \n\n**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.\n\n**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. \n\n**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. \n\n**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$.\n\n**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.\n\n**4.** It is unfortunate that the lower bounds for the stochastic case needed to be corrected in the supplementary material.\n\n**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).\n\nA missed reference (just for the author's information): https://openreview.net/pdf?id=IcDTYTI0Nx shows the convergence of SAM with non-constant perturbation sizes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for dedicating their valuable time to evaluate our paper. Below are our responses to the questions raised.\n\n> **Weakness 1. Non-convergence seems obvious.**\n\nAs the reviewer correctly points out, if deterministic SAM finds a fixed point $\\tilde{x}$, it must hold that $\\nabla f(\\tilde{x}+\\rho \\frac{\\nabla f(\\tilde{x})}{\\lVert\\nabla f(\\tilde{x})\\rVert})=0$. However, this does not necessarily indicate that $\\tilde{x} + \\rho\\frac{\\nabla f(\\tilde{x})}{\\lVert\\nabla f(\\tilde{x})\\rVert} = x^*\\neq \\tilde{x}$, where $x^*$ represents a stationary point or a global minimum. This is because we treat $\\frac{\\nabla f(x)}{\\lVert\\nabla f(x)\\rVert}$ as $0$ whenever $\\nabla f(x)=0$ (see lines 123-125), which means that the converged fixed point $\\tilde{x}$ can also be $\\tilde{x} = x^*$ itself, not necessarily a point satisfying $\\lVert\\tilde{x}-x^*\\rVert=\\rho$. In light of this point, we'll clarify why the equation $\\lVert\\tilde{x}-x^*\\rVert=\\rho$ is not always true, by presenting examples in convex and nonconvex functions.\n\n- **Convex functions.**\n\nBy utilizing Lemma B.2, we get $\\langle\\nabla f(\\tilde{x}),\\nabla f(\\tilde{y})-\\nabla f(\\tilde{x})\\rangle\\geq 0$, where $\\tilde{y}=\\tilde{x}+\\rho\\frac{\\nabla f(\\tilde{x})}{\\lVert \\nabla f(\\tilde{x})\\rVert}$. Rearranging, we get $\\langle \\nabla f(\\tilde{x}),\\nabla f(\\tilde{y})\\rangle\\geq\\lVert \\nabla f(\\tilde{x})\\rVert^2$. Consequently, $\\lVert \\nabla f(\\tilde{y})\\rVert ^2 \\geq \\lVert \\nabla f(\\tilde{x})\\rVert^2$, which in turn indicates that $\\nabla f(\\tilde{y})=0$ if and only if $\\tilde{x}=x^*$, where $x^*$ is the global minimum. This implies that if SAM converges to $\\tilde{x}$, then $\\tilde{x}$ **must be** $x^*$.\n\n- **Nonconvex functions.**\n\nHere, we present scenarios wherein SAM tends to converge in proximity to a stationary point $x^*$, rather than a point located $\\rho$-away from $x^*$.\n\n**Scenario 1**: Consider a \"local maxima function,\" represented by $f(x)=-\\frac{1}{2}x^2$. We can quickly verify that a possible virtual loss (recall Definition 2.7) can be defined as\n$$\nJ_f(x)=\\\\begin{cases}\n    -\\\\frac{1}{2}(x+\\rho)^2,  &x\\leq0 \\\\\\\\\n    -\\frac{1}{2}(x-\\rho)^2,  &x>0.\n\\\\end{cases}\n$$\nTherefore, when $x_t\\in[-\\rho,\\rho]$, SAM updates tend to converge towards $x^*=0$. Precisely, we can check that for $\\eta<1$, if $x_t\\in[-\\eta\\rho,\\eta\\rho]$, the subsequent iterates remain within $[-\\eta\\rho,\\eta\\rho]$, implying $|x_t-x^*|\\leq\\eta\\rho$. This means that for sufficiently small $\\eta$, the SAM iterates stay in proximity to $x^*$ at a distance **much closer than** $\\rho$.\n\n**Scenario 2**: Consider a \"saddle function,\" denoted as $f(x,y)=x^2-y^2$. Analogous to scenario 1, the SAM iterates near the saddle point tend to converge to that saddle point. For the detailed illustration, refer to Figure 5 in [1].\n\nFrom these scenarios, we can check that for nonconvex functions, local maxima and saddle points can serve as attractors within certain regions. Consequently, there are many scenarios that SAM iterates converge to stationary points $x^*$, and we can conclude that the convergence of SAM to points $\\lVert \\tilde{x}-x^*\\rVert=\\rho$ **does not always happen** even in nonconvex settings.\n\n> **Weakness 2. There seems to be an issue in Theorem 3.2.**\n\nAs outlined in our discussion on the \"Remarks on the validity of lower bound\" (lines 634-656), our objective is to establish a lower bound for Equation (7). Specifically, we aim to demonstrate the existence of lower bound for each $A \\in \\mathcal A$, wherein we select $f \\in \\mathcal F$ accordingly. In the context of Theorem 3.2, the function class $\\mathcal{F}$ represents the collection of all $\\beta$-smooth $\\mu$-strongly convex functions, where the constants satisfy $\\frac{\\beta}{\\mu} \\geq 2$. In order to prove a lower bound, we get to choose ``worst-case'' functions from $\\mathcal F$, and this function class naturally includes 1-D quadratic functions: $f(x)=\\frac{a}{2}x^2+bx+c$, for any $a$, $b$, and $c$ satisfying $\\mu\\leq a\\leq\\beta$. It is easy to verify that the functions we have employed in Cases 1, 2, and 3 of Section B.3 belong to this particular category $\\mathcal F$. Therefore, using 1-D quadratic examples does not harm the correctness of our derivation of lower bounds.\n\nAdditionally, as for the issue raised for Case 1, even in the case of $\\beta=\\mu$, by scaling $x_0$ (in line 612) up properly and starting at $x_0 = 4\\rho$, we can get $x_t \\geq \\frac{x_0}{2} = 2\\rho$ and immediately resolve the issue.\n\n> **Weakness 3. Theorem 3.4 seems loose.**\n\nSetting $\\eta = \\frac{1}{\\beta}$ and following the same steps as in Theorem 3.4 while also combining the two terms as suggested by the reviewer, we can verify that $\\frac{1}{T}\\sum_{t=0}^{T-1}\\lVert\\nabla f(x_t)\\rVert^2\\leq \\frac{2\\beta\\Delta}{T}+\\beta^2\\rho^2$. This result shows that we can achieve a convergence rate of $O(1/T)$ to a $O(\\beta^2\\rho^2)$ stationary point without the Lipschitzness assumption. The same approach applies to stochastic $n$, $m$-SAM as well (with $\\eta=\\mathrm{min}\\\\\\{\\frac{1}{2\\beta},\\frac{\\sqrt{\\Delta}}{\\sqrt{T\\beta\\sigma^2}}\\\\\\}$ or $\\eta=\\frac{1}{\\beta}$). We greatly appreciate the reviewer's valuable input which improved our findings, and we will make sure to incorporate these improvements in the revised manuscript.\n\n> **Weakness 5. No results regarding generalization**\n\nWe would appreciate it if you could refer to our response of Question 1 in the ``global response\".\n\nWe hope that our response successfully addresses the issues raised by the reviewer, and we would greatly appreciate it if the reviewer could consider reassessing our paper. Thank you again for the insightful review.\n\n---\n[1] Kim, H., Park, J., Choi, Y., \\& Lee, J. (2023). Stability Analysis of Sharpness-Aware Minimization. arXiv preprint arXiv:2301.06308."}]

Author rebuttal:
Dear reviewers,

We sincerely thank all the reviewers for their careful evaluation of our paper and their valuable questions and comments. Your reviews have been tremendously helpful in improving our manuscript. We are glad that many reviewers recognized the comprehensiveness of our upper and lower bounds as well as their relevance to practical settings.

Below, we would like to start by addressing some concerns that were raised by multiple reviewers. We will address the remaining questions in the individual responses below.

> **Question 1. SAM was proposed to improve generalization. But this paper has no results illustrating how SAM improves generalization. (Reviewers y8UR, NH1R)**

We definitely agree that the main reason for SAM's widespread adoption is its superior generalization performance. We believe that understanding this characteristic of SAM from a theoretical perspective is of great importance and interest.

Indeed, prior researches [1,2] proved SAM's tendency to approach flat minima, but under the crucial assumption that SAM should initially converge near the global minima manifold and/or with a sufficiently small $\rho$. Yet, the question whether practical SAM really converges in the first place still remains open. Our paper tackles this gap by introducing scenarios where SAM can (or cannot) converge, under practical settings.

Our paper focuses on the convergence properties of SAM, thus the investigation of SAM's tendency to find flat minima and generalization property is outside the scope of our paper. We wish to tackle the generalization aspect of SAM in the future.

> **Question 2. Regarding the practical implication of our findings, How does the extra bias term affect the empirical performance of SAM? Also, is it possible to design a better algorithm that eliminates the extra bias term? (Reviewers AJAE, NH1R)**

Although SAM has gained much attention due to the superior generalization ability of models trained by the algorithm, our findings reveal that the capability of SAM as an optimizer is rather limited, which is quite surprising.

One straightforward method to eliminate the bias term $O(\rho^2)$ is to use USAM (SAM without gradient normalization) with a sufficiently small (or decaying) $\rho$; as demonstrated in [3], convergence guarantees for USAM have been established under such conditions. Additionally, employing SAM with a sufficiently small constant $\rho$ (which appropriately decays with $T$) can also address the extra bias term.

However, we are in fact skeptical if these modifications can be seen as "improved" algorithms, as the modified algorithms will be closer to GD (as outlined in lines 63-89 of our paper), thereby **losing** the distinct features of SAM.

The presence of an extra unavoidable bias term in the convergence bounds could potentially relate to SAM's generalization property; however, further investigation is required. As of now, no definitive conclusions can be drawn, making it a promising avenue for future research.

> **Additional experiments**

As per Reviewer AJAE's suggestion, we conducted additional experiments which demonstrate that SAM indeed does not converge in our worst-case example constructions. The results can be found in the attached pdf file below.

---
[1] Bartlett, P. L., Long, P. M., & Bousquet, O. (2022). The dynamics of sharpness-aware minimization: Bouncing across ravines and drifting towards wide minima. arXiv preprint arXiv:2210.01513.

[2] Wen, K., Ma, T., & Li, Z. (2022). How does sharpness-aware minimization minimize sharpness?. arXiv preprint arXiv:2211.05729.

[3] Andriushchenko, M., & Flammarion, N. (2022, June). Towards understanding sharpness-aware minimization. In International Conference on Machine Learning (pp. 639-668). PMLR.

Meta-review: The paper analyzes the convergence of the sharpness-aware minimization (SAM) algorithm. It provides both upper and lower bounds of convergence when the function is smooth and strongly convex, whereas in the case of smooth and nonconvex functions, it shows that convergence to a stationary point is possible only up to a certain neighborhood, and that furthermore this is unavoidable. Based on these contributions, along with the reviewers' having reached a consensus, I recommend acceptance of this paper.
Decision: Accept (spotlight)