A Unified Stability Analysis of SAM vs SGD: Role of Data Coherence and Emergence of Simplicity Bias
Authors: WEI-KAI CHANG
Rajiv Khanna
Venue: NeurIPS 2025 poster ()
Keywords: Stochastic Gradient Descent (SGD)
Sharpness-Aware Minimization (SAM)
Linear Stability Analysis
Two-Layer ReLU Networks
Stability and Convergence
Primary area: optimization

Abstract: Understanding the dynamics of optimization algorithms in deep learning has become increasingly critical, especially as models grow in scale and complexity. Despite the empirical success of stochastic gradient descent (SGD) and its variants in finding solutions that generalize well, the precise mechanisms underlying this generalization remain poorly understood. A particularly intriguing aspect of this phenomenon is the bias of optimization algorithms towards certain types of minima—often flatter or simpler—especially in overparameterized regimes. While prior works have associated flatness of the loss landscape with better generalization, tools to mechanistically connect data, optimization algorithms, and the nature of the resulting minima are still limited. For instance, methods like Sharpness-Aware Minimization (SAM) have shown practical gains by explicitly promoting flatness, but lack a unified theoretical framework explaining their influence across different data structures and model architectures. In this work, we introduce a comprehensive linear stability analysis framework to dissect the behavior of optimization algorithms—SGD, random perturbations, and SAM—in neural networks, focusing particularly on two-layer ReLU models. Our approach is built upon a novel coherence measure that captures the interaction between data geometry and gradient similarity, providing new insights into why and how certain solutions are favored.

A Unified Stability Analysis of SAM vs SGD: Role of Data Coherence and Emergence of Simplicity Bias
Wei-Kai Chang Purdue University chang986@purdue. edu
Rajiv Khanna Purdue University rajivak@purdue. edu
Abstract
Understanding the dynamics of optimization in deep learning is increasingly im- portant models scale. While stochastic gradient descent (SGD) and its variants reliably find solutions that generalize well, the mechanisms driving this general- ization remain unclear. Notably, these algorithms often prefer flatter simpler minima panticullrlyyllyyyyy in overparameterized settings. Prior work has linked flat- ness to generalization, and methods like Sharpness-Aware Minimization (SAM) explicitly encourage flatness, but a unified theory connecting data structure, op- timization dynamics, and the nature of learned solutions is still lacking. In this work, we develop a linear stability framework that analyzes the behavior of SGD, random perturbations, and SAM-particularly in two-layer ReLU networks. Cen- tral to our analysis is coherence measure that quantifies how gradient curvature aligns across data points, revealing why certain minima stable and favored during training. (Code are available in: cnttps://gt thub. cow.ub.ccmm/caagg1101100 Stability.Analysis..o Aww.Aninnsssaddd and Stmpliiittmmiittttyyyymmmmmioy Biaty--iBiggi
Introduction
Modern deep networks often achieve low training error even in extreme overparameterized settings, yet they generalize surprisingly well. A key question is why the particular solutions found by standard training procedures tend to generalize, when many other parameter configurations could fit the training data but fail on test data. A body of work has suggested that stochastic gradient descent (SGD) implicitly favors solutions associated with flat minima (i.e. wide, low-curvature regions of the loss) which correlate with better generalization [Keskar et al. 2017 Hochreiter and Schmidhuberj 1997]. Recent algorithms like Sharpness-Awe
Minimization (SAM) explicitly optimize for flatness and further improve generalization Fooeet et al., 2021]. A complementary line of reasoning posits an implicit simplicity bias overparameterized neural networks: given choice of multiple functions that fit the training data, SGD tends to find those that rely on simpler or more "intuitive" features, rather than complex or idiosyneratic ones. Empirical evidence shows that neural networks often learn the most predictive yet simplest patterns in the data first, and may entirely ignore more complex features if the simple ones already suffice [Arpit et al.) 2017 Shah et al., 2020). This built-in Occam's 's razor has been offered an explanation for why DNNs do not overfit even when they could in principle memorize the training set [Valle-Péree et al. 2019
Both the flat-minima hypothesis and the simplicity bias hypothesis provide important clues to neural network generalization. Yet it remains unclear how these perspectives connect, and what underlying mechanism drives this preferential selection of solutions by SGD. In particular, why should an algorithm like SGD prefer flat minima feature-simple solutions in the first place? And how do modifications to the optimizer Minimization (SAM) Forret et al., [02T]] - alter these preferences? Intriguingly, recent empirical evidence further suggests that even among multiple minima of equal overall flatness, SAM can
such as adding random noise or using Sharpness-Awan
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

exhibit an additional implicit bias favoring those solutions that generalize better [Andriushchenko al.) 2023| Wen et al., [023a| Springer et al. 2024). This calls for unified theoretical framework to explain which minima are favored by different training dynamics and why.
Towards this goal, we analyze the linear stability of different optimization methods around minima of the loss landscape to gain insight into which minima are attractors for the dynamics. Crucially, we focus on a notion of data coherence [Dexter et al., 2024] that captures how similar or aligned the contributions of different training examples are to the local curvature of the loss. This measure serves as a bridge between data geometry and the stability of minima: intuitively, solutions where many examples share common "directions" in parameter space (high coherence) are more stable under SGD dynamics, whereas solutions that fit each example independently (low coherence) are less stable. In turn, we prove that the emergence of an implicit simplicity bias that is introduced based on which minima are stable vs unstable and leads SGD to favor simpler solutions that utilize shared features across data points instead of memorizing idiosyncrasies of individual examples.
Furthermore, our framework allows us to compare standard SGD with two variations: a simple random perturbation method (which injects isotropic noise during training) and SAM. We find that injecting small random perturbations has essentially the same stability criteria as plain SGD, indicating that when viewed through the lens of linear stability, it does not fundamentally change which minima are favored but increases the speed of escape from unstable minima. In contrast, SAM imposes a stricter stability requirement: it penalizes directions with high curvature via an effective Hessian factor in the update. As a result, our analysis predicts that SAM will actively avoid sharper (narrow) minima even when SGD might be marginally stable there, and instead SAM will gravitate even more strongly toward not just flatter, but more highly coherent solutions. In effect, SAM amplifies the simplicity bias inherent in SGD by further discouraging solutions that depend on complex, fragile combinations of features. Notably, this extends the conventional view of SAM as merely favoring flat minima: our analysis shows that it also induces bias toward solutions of lower complexity that rely on shared structure across examples.
Contributions. Our work helps paint coherent picture in which the "flat minima + good gener- alization" heuristic and the "SGD finds simple functions" heuristic are two sides of the same coin. We articulate this connection rigorously and in doing so, also suggest that interventions like SAM, which further insist on flatness, are effectively heightening the simplicity bias an interpretation consistent with recent findings that SAM-trained models prefer more parsimonious representations (Andiushhhhenko et al. [023], can enlarge the regime of benign overfitting when compared to SGD [Chen et al., 2023 and can empirically choose better generalizing minima even there are mul-
tiple minima with the same flatness [Wen et al. 2023a Our main contributions can be summarized
as follows:
Unified Linear Stability Analysis. By linearizing the training dynamics around a candidate minimum, we derive the first known precise stability conditions for a randomly perturbed variant of SGD, and SAM explain when a solution will be an attractor under each algorithm. We examine a data-dependent coherence matrix that measures the alignment between eer-example loss Hessians. We prove that the spectral properties of this coherence matrix directly govern stability: roughly, solutions where training examples yield highly aligned curvature (high coherence) remain stable under larger learning rates.
Matching lower bounds. To show tightness of our analysis, we derive matching lower bounds on the stability trace under SAM, further cementing exponential divergence when coherence and curvature align unfavorably.
Emergence of Simplicity Bias for SGD. We prove that if the training data admits a "simple" global solution (where the model uses few common set of features for many examples), the solution will exhibit high coherence and thereby strong stability, causing SGD to prefer it over more complex solutions (which have lower coherence and are unstable under similar conditions). This result bridges the gap between data geometry and the classical flatness- generalization argument, as highly coherent solutions tend to be flatter in the aggregate sense.
SAM intensifies the Simplicity Bias. Our analysis indicates that SAM's update rule effectively makes even harder for solutions with disparate, high-curvature directions to remain stable. Consequently, we show that the data coherence explains why SAM not only

---

finds flatter minima than SGD, but also drives the model toward using more aligned (and hence fewer) features. This aligns with recent empirical observations that SAM leads to simpler or more generalizable representations in deep models (Andriushchenko et al. 2023 Wen et al. 2023a Springer et al. 2024].
Empirical Validation. We validate our theoretical insights on two-layer ReLU network, where we can analytically characterize different types of solutions. We prove, for instance, that in a two-layer network, a solution that memorizes each training example in separate neuron corresponds to a diagonal coherence matrix (no shared features), whereas solution that generalizes by using common features yields off-diagonal coherence and dominant principal component. Our results confirm that SGD (and especially SAM) is unlikely converge to the memorizing solution when a simpler one exists, consistent with the simplicity bias phenomena observed in practice.
2 Background
We begin by introducing the linear stability framework, which forms the foundation for our analysis. Linear stability provides principled way to analyze the local behavior of iterative optimization algorithms the vicinity of critical points (c.g., local minima or saddle points) by linearizing the update dynamics. This framework has been used to study convergence properties of SGD and its variants and has recently emerged as a useful tool to characterize generalization-relewe behavior such the ability escape sharp minima (Wu et al. 2018 Dexter al. 2024
Linearized Dynamics near Minimum. Consider a twice-diiferentiable loss function L(w) over model parameters w E Idd, and suppose w* is local minimum. Let wi w- be the perturbation
from the minimum at time t. Expanding the gradient in a Taylor series around w", we obtain
V((wx) = VL(w" + 6c) R V V²T("")
since VL(w*) 0. For generic optimization algorithm with update rule w4+1 Wt 199t. the linearized dynamics become
61+1 -I-nHH,0,
where H; is an approximation to the local curvature (e.g.. the Hessian or stochastic surrogate), In the case of stochastic gradient descent (SGD), the curvature matrix H₃ is typically estimated using a mini- batch of training samples. Let S, denote randomly sampled batch of size B and define the
stochastic Hessian estimate as
H.
Σ
H, where H. V2l(w; y:)-
B
Then, the SGD update becomes
We+1 = W/ - -H = --,HH));; = Jewr.
where we use Jg to denote the random linear operator at iteration t. For deterministic full-batch gradient descent, we replace H, with the full Hessian H 1 Σi= H; and drop the hat notation.
To study the torg-term behavior of the iterates, we analyze the expected squared norm of the weights:
E ww [ = E[uo JT J J2 Jo E[Tr(J+ ... Swwon JT ... J.
Assuming We (0, I), reduce analyzing the quantity E[ ... JT Jr J.)), which captures the contraction or expansion behavior of the iterates under the sequence of update matrices. See more details discussion of assumption in appendix A
Stability criterion. The system is said to be linearly stable at w² under a given optimization method if the expected squared norm B[]lwx||? remains bounded as h -> xa. A sufficient condition for this that the spectral norm of the average update matrix E J.T J,] is strictly less than 1. For full-batch gradient descent, this reduces to requiring 7 <
More generally, in the presence of stochasticity and structure in the data, one can derive stability conditions involving both the Hessian spectrum and how curvature is distributed across examples. This motivates the use of data-dependent coherence measure, which we introduce next.
3

---

Definition 1. Coherence measure Dexter et al. 2024]. For a collection of per-example Hessians [Hi define the coherence matrix S E R with entries Sig = || 1 (Tr(H,,
The coherence measure is defined as follows:
Amax(S) (S)
maXign Amaxx (H))
High coherence corresponds to strong alignment in the curvature directions induced by different training examples. Intuitively, perturbations in shared directions lead to large changes in loss across many samples, which creates stronger restorative gradient and thus stabilizes the solution. This measure plays a central role in our analysis: we show that both SGD and SAM favor solutions with high coherence, and that SAM in particular exhibits stronger divergence from low-coherence solutions due its amplified curvature penalty. The next section builds on this foundation to characterize the dynamics of SGD, random perturbation, and SAM using linear stability theory.
3
Main Results
3.1 SGD under Random Perturbation
To better understand how optimization algorithms behave near critical points, we begin by analyzing
a simple but illustrative baseline: random perturbation- baase SGD [Bisla al.) [022]. This variant injects additive noise into each update step and has been used to improve generalization to escape sharp minima:
Wt-1 We 17 sl(w - 6,) We ryH, - 1,168
While this method has been empirically studied, its behavior under the linear stability framework has not been formally characterized. Our goal to quantify how the injected noise affects both the convergence region and the escape rate from unstable minima. By addressing these questions, we establish a baseline against which we can evaluate SAM's behavior. The following theorem provides bounds the trajectory norm under random perturbations, showing how noise modifies the divergence behavior without altering the stability threshold.
Theorem 3.1. Given update rule (3)
1. Sufficient condition for divergence is as follows:
0 n
1)
2. (Comparative Divergence Speed) Suppose Tr[J2k] S Coa for some constants Co and Ork, then the divergence rate of the random perturbation method is asymptotically within constant factor of that of standard SGD:
Elll w]l Random, lower bound O(1)
lim 1-00
E. [[ SGD, lower bound
3. Suppose the step size satisfies the convergence criterion established in prior stability anal- yses (e.g., Dexter al.) (2024)). Then, under the random perturbation update (3) the expected squared norm of the iterates remains bounded as - co:
lim E MMa Wk] lupper bound O(1)
k0000
Discussion. Theorem 3.1 characterizes the behavior of random perturbation under the linear stability framework. We find that the divergence threshold for instability remains unchanged from standard SGD as derived by Dexter et al. (2044) (part 1), implying that adding random noise does not alter which minima are stable. However, once minimum is unstable, the injected noise causes the iterates to diverge at a constant faster rate (part 2). This observation aligns with the intuitive role of noise in facilitating exploration during training. Further, in the stable regime, the iterates do not

---

converge exactly to the minimum, but instead remain in a bounded region around it (part 3), This residual variance arises from the persistent noise and illustrates tradeoff: random perturbation aids exploration but limits precision. 'ogether,, these results position random perturbation useful baseline control for SAM as we now show that SAM's behavior is due fundamentally different mechanism that biases optimization toward aligned, lower-complexity minima.
3.2 Sharpness aware minimization (SAM)
We now analyzing SAM, an algorithm explicitly designed to seek flatter minima by optimizing a worst-case perturbed loss. SAM replaces the standard gradient descent step with descent direction that maximizes the loss within neighborhood of the current iterate. Formally, the gradient can be approximated
Vi(w)
VI(w)SAM Vl(w +
V(w
Under the quadratic setting, write the iterate update process
V((w))
Wx+11 w/ V sl
V[(++]]]
nI-nHe + Hwwll
H)
While the gradient update in SAM admits a closed-form expression under the quadratic approxima- tion, the presence of the norm in the denominator-ias -ie.. inntoduursuuesss significant analytical challenges due to its dependence on the current iterate. To facilitate tractable analysis, we follow prior works (Andriushchenko and Flammarion 2022 Du et al., 2022 Zhou et al., 2025 and replace this quantity by fixed scalar value This simplification allows us to isolate the effect of the curvature term and focus on the directional dynamics introduced by the sharpness-aware perturbation. Under this update, the SAM update reduces to linear transformation governed by effective Hessian (I + H) which portrays a stricter stability criterion and fundamentally
of the form HSAM different optimization dynamics than SGD. This allows SAM to not only escape sharp minima more aggressively but also to selectively stabilize solutions that exhibit coherent curvature, thereby am- plifying simplicity bias. In our theory, analyze the noise arising from the alignment of the space spanned by different sample which accumulate over steps. For the following, we provide simplified version of our theory (see Appendix CC8 and Appendix [.9 exact details).
Theorem 3.2 ((immplified) Linear Stability of SAM). Consider the update rule of SAM under quadratic loss approximation:
W++1 = (1- (I (..eH) Wt.
where He is the mini-batch Hessian at time t, is the SAM perturbation radius, and a is fixed approximation to [H..
1. Divergence criterion. SAM diverges if the largest eigenvalue of the Hessian exceeds the following threshold:
σ 1 71
-1) 1/2 (
Amax (H)
Compared to SGD, this condition is stricter due to the additional curvature-dependen term in the denominator, implying that SAM escapes sharp minima more aggressively.
2. Convergence criterion. there exists e (0,1) such that
2-c
Vi ld].
17
17
and the accumulated noise decays sufficiently fast (see Appendix C.9 converge expectation:
then the iterates
lim Blllea [1 0.
k
5

---

see the divergence part proof in Appendix C.8 and see the convergence part of proof in Appendix C
Theorem 3.2 shows that the optimization dynamics of SAM are also governed by the coherence measure that captures how sample gradients align. However, if we map the SAM dyanamics to those of SGD as per Eq ( we can extrapolate that SAM operates on sharper surface where the effective Hessian and coherence matrix becomes
Discussion:
L1 H, HSAM (1+ (1+11)
P Tr[[I+ (I) P HHHH a
SSAM.1 =
a
SAM's update effectively introduces additional Hessian-dependent factor penalizing directions with large curvature which tightens the stability criterion. Qualitatively, a solution that might be marginally stable under SGD (with eigenvalues just below the SGD stability threshold) can become unstable under SAM if even a single eigen-direction has curvature beyond SAM's narrower tolerance. This theoretical insight aligns well with SAM's 's design goal of seeking flat minima [Foret et al. 202T], but it goes further by pinpointing which sharp minima are especially disfavored: namely, those where the sharpness arises from directions that are not supported uniformly by all training examples. By contrast, if a sharp curvature direction is "universal" across examples (high coherence). is somewhat mitigated in our stability condition intuitively, SAM is less alarmed by curvature that stems from feature direction that all data agree on, than by curvature that comes from one-off fluctuations. In practical terms, this means SAM biases training even more strongly toward solutions that rely on global features of the data. Solutions that depend any single example (or small subset of examples) in a unique way will tend have some high-curvature direction localized to that example's loss, making them unstable under SAM even if SGD might have tolerated them. Further, SAM also escapes exponentially faster from minima that it deems as unstable.
We now show the optimality of the SAM divergence bound with matching lower bound: [n], > 0 and a E [n]] that satisfied
Theorem 3.3. For every choice of X > 0, n N, B E
A1 + P x2)
20 lo + n
1)-
(5)
B
there exist a set of PSD matrices (Hi)sel)) such that Amnax (H) A1 lim Je..
3.3 Emergence of Simplicity Bias: Realization in Two-Layer ReLU Models
We now instantiate the linear stability framework in concrete neural network setting to analyze how the theoretical insights developed so far translate to realistic model architectures. Specifically, we focus on a two-layer ReLU network trained with mean squared error (MSE) loss:
fm( = W2 ReLU(W1r xx+++ +b,
where W1 E IRdaxd maps inputs to hidden units, W2 E Rixd2 maps activations to output, and b E d2ds is bias term.
This setting allows us to bridge abstract notions such as curvature, coherence, and stability with concrete properties of network solutions including memorization, feature sharing, and low-rank structure. We adopt a synthetic data distribution from prior work [Wen et al.) 2023a where inputs 1] are drawn i.i.d. and labels generated y [0]] ensuring that both simple and complex solutions exist.
Crucially, we analyze the Hessian of the MSE loss under exact interpolation. In this regime, the gradient of the loss at the optimum is zero and the Hessian simplifies to:
==
Vou Vw.
enabling direct application of our earlier stability results. By examining how per-sample gradients align across examples, we quantify the coherence structure of different solutions and show how this governs their stability under SGD and SAM.

---

Memorization and Coherence. We begin by characterizing memorization in our setup data point memorized if it activates unique hidden neuron [Wen et all 2023a]. A memorized solution is one where each training point is memorized. A generalizing solution reuses the same features (neurons) across multiple samples, resulting aligned gradients and higher coherence. The following result formalizes the relationship between memorization and coherence.
Theorem 3.4 (Coherence Characterization of Memorization). two-layer ReL.U network defines a memorizing solution if and only if the coherence matrix S is diagonal.
This observation implies that in the memorizing regime, the sample-wise Hessians are orthogonal, i... Hy] O for * j. As a result, the coherence matrix reduces to a diagonal form, elim- inating any cross-sample interaction. Consequently, the corresponding stability condition degrades to its weakest form, as no spectral amplification arises from off off-diagonal terms.
In contrast, generalizing solutions induce non-trivial off-diagonal components in S, reflecting shared activation patterns or feature overlap across examples. This coherent structure enhances the dominant eigenvalue of S, thereby tightening convergence guarantees and improving stability under both SGD and SAM. Hence, any statistical or geometric correlation among training samples inherently rules the memorizing case and promotes more favorable optimization dynamics.
Constructing Generalizing Solutions. To systematically explore generalization within this frame- work, we define family of (C, -ggneerliizi solutions, where C' controls the number of active features and r determines the sharpness of the solution. For fixed r, all such solutions are equally flat in trace norm, but differ in complexity through C.
Definition 2. --geerraliizn solution) Let (a1, 02,-0.,,a E 10. We construct W1 such that each hidden unit encodes pattern of the form:
W1, r r. [(-1)(s (-1)
(-1)ac .......0J 0].
with j indexing a binary encoding of the a; 's i.e. j = + Σ 2i-la; a4. We set Waljl = (-1)ar
match. For k C. W1, = 0, W [k] 0, b[k] 0.
It is straightforward to verify that Tr = , (d+ 1) + r², indicating that r controls the flatness of the solution. The minimum trace-and thus the flattest solution is achieved when (d + 1)2/4. For any fixed r, the overall flatness Tr(H) HT) remains constant regardless of C. The weights W1 exhaustively encode all possible feature values, and the bias b ensures that ReLU( b) activates only one row that match x. Given that y = x =0]xx[1] [1] (as described in Section 3.3). the construction guarantees that each (C, -enerraiizz solution is also interpolating: f(x;) = yi for all E [n]. In this framework, C' acts as a complexity currogate-controlliggg the number of features usid-while preserving identical flatness across interpolating solutions. An illustrative example is provided in Appendix C.T As we show next, the coherence matrix spectrum depends heavily on C:
Theorem 3.5 (SGD Stability of (C.r)- Generalizing Solutions). Fix r = (d+ + 11 Then, with probability least 1 - 5, for randomly drawn dataset of size n, the top eigenvalue of the coherence matrix under a (C, r) --gnerrllizing solution satisfies:
Amaxe (S) = 0 (g" n (d (d+1))12).
while max, Amax (H:) = 2(d+
(See Appendix C.11 for dependency of 8) combining with Theorem for the SGD bounds [Dexter cet al. (2024). this implics that simpler (low-C) generalizing solutions are more stable under SGD, when all candidate solutions lie in equally flat regions of the loss.
SAM Favors Simpler Solutions. Finally, we analyze how SAM further shifts this preference. Under SAM, the coherence matrix becomes
S SAAM
Tr [I++ {
which accentuates the interaction between aligned directions. As result, the top eigenvalue of SSAM grows more sharply for generalizing solutions with small C than for more complex ones.
This bias is formalized in the following bound:
7

---

deabaRy
Seauaity
Melhrod
Merhod
Roy
10
20
(d)
(a)
(b)
(c)
Figure I: Comparison of optimization dynamics across different methods and configurations. (a) SAM's dyanamies over different hyper-parameter settings (Red:diverging Blue:converging). (b)
Boundary comparison: SGD, random perturbation, SAM. SGD and random perturbation bound-
aries largely overlap. while SAM diverges in more combination of batch size and (c) SAM
boundaries at different 2: Higher & further tightens the SAM boundary between the converging and diverging regimes. (d) Convergence under different C, fixed For 2-layer ReLU networks, SAM converges faster across varying C' with fixed r.
Method Sai
Coberence Measure
ER
Aroo (B+)
Avao (77)
Tr(l7)
333 942
12740 265
6.167
94.58 385
6.776
$1.954
SAM 0.01
121.473
10105 268
6.2
$2.882
6.211
48.401
SAM 0.00
90.309
6421 689
6
70.948
4.988
38.461
SAM 0.3
65.656
3445.964
3.6
$2.294
3.834
29.140
Table 1: Coherence and fessiannbbase metries across methods. ER stand for effective rank of the features. We perform PCA on the features of training data and set the threshold for effective rank be 90 percent to determine the activation pattern used in different combination of parameters and optimization.
Theorem 3.6 (SAM Stability of (C,r) (C,r)-Genennte Generalizing Solutions). Under a (C, generalizing solu- tion for a randomly iid drawn dataset of size n, the top eigenvalue of the RAM-induces coherence matrix satisfies:
p 2(d
1) 2c
0²
1 ( n
Amax (SAM)=O! (d+ 1) (1
()((d+
22d
2c
2
and,
max Amax (II P H)H,) = 2(d+ (1+
P a 2(d 2(d 1)²)
Combining with Theorem 3.2. Theorem 3.6 shows that SAM not only escapes sharp minima more aggressively, but also amplifies stability differences between simple and complex solutions by favoring solutions with smaller C' more aggressively, further biasing optimization toward lower-complexity minima. This explains recent empirical observations of SAM inducing low-rank or structured representations even when curvature alone does not distinguish between candidate solutions.
4 Experiments
In the experimental section, we empirically validate the following key aspects of our theoretical framework: (1) The behavior of SAM, random perturbation, and SGD under varying combinations of batch size B and noise scale a to validate our theoretical findings. (2) The dynamics different optimization algorithms in the vicinity of various rggenerliizz solutions, again for validating our theory, (3) The influence the coherence measure throughout the training process, its role in optimization, and its sensitivity to different training hyperparameters across methods.
Local: Linear stability in quadratic loss for different algorithms (B, We investigate the diverging/convergingg behavior compared to our theoretical upper and lower bounds over different values of (B, .) for quadratic loss. For space, the experimental setup is moved to Appendix C.3 The results are presented in Fig [[). The dashed line and solid line are plotted as per Theorem
3.3 and Theorem 3.2 respectively. We observe gap in small batch size setting also apparent from our theory but for larger batch sizes, our theory can accurately predict the diverging and converging

---

behaviors, For Figures [b)c), we compare the experimental boundary of SGD, random perturb and SAM and observe that the boundary between stable and unstable regimes shift as we increase the ratio L as also predicted by our theory. Additionally, SGD and random perturbation algorithm show strong overlap in the boundary which also aligns with our theoretical results.
Local: Linear stability in MSE loss for different algorithms in 2-layer ReLU network. To study the local behaviors of different algorithms, we initialize the model around the (C,r) solution (Def. 2 with small Gaussian noise N (0, 0.01) to the model weights to ensure non-zero gradients. We sample n 100 data points as described in set up in section From hggure]) we observe for smaller C, the converging speed is indeed faster compared to those with high C' as expected from our theory. Additionally, we find that when compared between SGD and SAM, SAM demonstrate higher converging speed which also aligns with our analysis. (See Appendix C.4 for additional details)
Global: The role of coherence in the training. In this section, investigate the role of the coherence measure through the training dynamics using the setup in the previous section. The final results is presented in Table A key finding is that SAM substantially reduces the effective coherence measure compared to SGD. To better understand the representational changes induced by SAM, we also compute the effective rank of the learned features. Specifically, we perform principal component analysis (PCA) on the training features and define the effective rank as the minimum number of components required to explain 90% of the variance. We observe a consistent decrease in effective rank alongside coherence, suggesting that SAM encourages more compact and structured representations an observation that aligns with our theoretical predictions.
Furthermore, we track the evolution of the coherence measure throughout the training (Figure. 2 and find that it varies dynamically, rather than remaining fixed. This suggests that coherence is nonstationary quantity during optimization, and tracking its trajectory may yield new insights into the evolving relationship between data samples. Coferer
Gremme
Figure 2:
2-layer ReLU network. SAM imposes strong regularization on the maximum elementwise Hessian eigenvalue, and this also reduces the largest eigenvalue of the coherence matrix, which implies the stability condition is satisfied with smaller a.
Conclusion. Our analysis reveals that the stability properties of optimization algo- esseeiallyy in the presence of data coherence- central to the emergence of generalization and simplicity in deep learning. We show that SAM amplifies this implicit bias by selectively sta- bilizing flatter, more coherent solutions, offering a theoretical explanation for empirical success. These results suggest unifying lens to interpret generalization stability-driven selection of solutions, and open avenues for designing optimizers that align algorithmic bias with data geometry.
Limitation. A primary limitation of our work is the reliance on a linear approximation of the loss landscape, as our analysis focuses on local behavior near minima. While we empirically explore the relationship between the coherence measure and training hyperparameters using two-layer ReLU networks, extending this investigation to larger models and real-world datasets remains an important direction for future work. Such studies could offer deeper insights into the practical significance of coherence in larger deep learning systems. For more discussion regarding limitation and practical or potential direction, provide detailed exposition in appendix A
Acknowledgments
We thank the Central Indiana Corporate Partnership AnalytiXIN Initiative for their support.

---

References
E. M. Achour, Malgouyres, and S. Gerchinovitz. The loss landscape of deep linear neural networks: second-orde analysis. Journal of Machine Learning Research, 25(242):1-76, 2024.
URL https://jmlr.... http://mmlrrrrr/ppaaaaaee wwt.ooog/ppae.eee arggpapers/v25/233 040330049..00 html
M. Andriushchenko and N. Flammarion. Towards understanding Sharpness-Aware Minimiza- tion. In Proceedings of the 39th International Conference Machine Learning (ICML), vol- ume 162, pages 639-668. PMLR, 2022. URL hatps::/pproceedingg mlr press/v162/
andriushchenkoo22a htmll
M. Andriushchenko, D. Bahri, H. Mobahi, and N. Flammarion. Sharpness-Aware Minimization leads to low-rank features. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023.
D. Arpit, S. Jastrzebski, N. Ballas, D. Krueger, E. Bengio, M. Kanwal, T. Maharaj. A. Fischer, A. Courville, Y. Bengio, and S. Lacoste-Julien. A closer look at memorization in deep networks. Proceedings of the 34th International Conference on Machine Learning (ICML), 70:233-242, wttp./eee/////rrtttiiiii. 2017. /ttt://////eeeeeoo...../////////
R. Bhatia. Matrix Analysis, volume 169 of Graduate Texts in Mathematics. Springer, 1997. URL https://links springer www.angrrrroooeoeaoo www.coommmoaaa www.cooooo///eeeccce
book/ookkoooooooo 100 1607 11000008--14611111
D. Bisla, J. Wang, and A. Choromanska. Low-pass filtering SGD for recovering flat optima in the deep learning optimization landscape. In Proceedings of the 25th International Conference on Artificial Intelligence and Statisties (AISTATS), volume 151 of Proceedings of Machine Learning Research, pages 8299-8333 PMLR, 2022. URL https::/proceee: bisla22a.
mlr press//151/
Chatterjee. Coherent gradients: An approach to understanding generalization in gradient descent- based optimization. In 8th International Conference Learning Representations (ICLR), 2020. URL https:://pperreiieet hwtpppeerreieeeeeeeeeeeeeeeeeeee hett/forrmmiiirryeee0EEW
Z. Chen, J. Zhang, Y. Kou, X. Chen, C.-J. Hsich, and Q. Gu. Why does sharpness-aware minimization generalize better than sgd? In Advances in Neural Information Processing Systems (NeurIPS), 2023. /
G. Dexter, B. Ocejo, S. S. Keerthi, A. Gupta, A. Acharya, and R. Khanna. A precise characterization of stability using loss surface geometry, International Conference on Learning Representations (ICLR), 2024. URL wtt.htttss//oopeeeiiieeee
net htt./ffrrmiiddduMM
L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference Machine Learning (ICML), volume 70, pages 1019-1028, 2017. URL
mlr. catpssss/v///dnh//// html
J. Du, H. Yan, J. Feng. J. T. Zhou, L. Zhen, R. S. M. Goh, and V. Tan. Efficient Sharpness- Aware Minimization for improved training of neural networks. In International Conference on Learning Representations (ICLR), 2022. URL
net http://www.....eooooommd/dddtnde
P. Foret, A. Kleiner, H. Mobahi, and B. Neyshabur. Sharpness-aware minimization for efficiently improving generalization. 9th International Conference on Learning Representations (ICLR), 2021. URL https:://///ppeere/
net/ meet/forumiddd-Tnnnle
S. Gunasekar, B. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit reg- ularization in matrix factorization. In Advances in Neural Information Processing Sys- tems (NeurIPS), 2017. URL https: httpp::/papprr: hwtppppprrr..iii.ccppppppppp...p foaape_filees/pppr/201///// 3599912221eecaae666777ccccceeee3 hbbp
M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In 33rd International Conference on Machine Learning (ICML), volume 48 pages 1225-1234, 2016. httpss:::///reeeeee httpgs///ppccecddngggglpppeeesss
Hochreiter and J. Schmidhuber. Flat minima. Neural Computation, 9(1): 1997. URL. https://www. mi jorrsssjorrnass.ooom doi wtt.:r//bb/1.11/////ee....
wwwo///eco...ccocooooooeooeeeeee 1997.9.1.1
10

---

Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations (ICLR), 2020. URL https://openreviert htw.eeww.eeeteteeeeeeeeeeeeeeeee net:/forumm?dd-SIIIPPPBB
D. Kalimeris, G. Kaplun, P. Nakkiran, B. Edelman, T. Yang. B. Barak, and H. Zhang. SGD on neural networks learns functions of increasing complexity. In Advances in Neural Information Processing Systems (NeurIPS) 32, pages 3491-3501, 2019. URL httpp::/ppooceee//iee
N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In 5th International Conference on Learning Representations (ICLR), 2017. URL http::///ppeeeeeiieee http://wwww.e.eeeooo/////doooooe
R. Khanna, B. Kim, Ghosh, and S. Koyejo. Interpreting black box predictions using fisher kernels. In Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics (AISTATS), volume 89, pages 3382-3390. PMLR, 2019.
m1 r. pwwps/v89 1at99///haaaaaala html
J. Kwon, J. Kim, H. Park, and I. K. Choi. ASAM: Adaptive sharpness-aware minimization for scale-invariant learning of deep neural networks. In 38th International Conference Machine Learning (ICML), pages 5905-5914, 2021. URL htttt::://prcceedinngggg///////t mlr peal..pres//v19// kwon21b. html
H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the loss landscape of neural nets. In Advances Neural Information Processing Systems (NeurIPS), volume 31. 2018 URL https://papen: http//ppppss.sss..... httipps.c//aaer/211///ass c41Bbbbe666006600077766666665553
html
K. Lyu and J. Li. Gradient descent maximizes the margin of homogencous neural networks. In Inter- national Conference on Learning Representations (ICLR), 2020. URL https:
net met/foorumiid-SJeLiggRt.
C. Ma and L. Ying. On linear stability of sgd and input-smoothness of neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021. URL httpst //openreview net httt///oondd/dy/o/iiiiiii
D. Morwani, J. Batra, P. Jain, and Netrapalli. Simplicity bias in 1-hidden layer neural networks. In Advances in Neural Information Processing Systems (NeurIPS) 36, 2023. URL https:// openreview net /tt.:/rrmmm/11PPxxc000
R. Mulayoff and T. Michaeli. Exact mean square linear stability analysis for sgd. In Proceedings of the Shirtt-Seventh Conference on Learning Theory (COLT), volume 247, pages 3915-3969. PMLR, 2024. Utt.https::/prroeediiig http:/pppeeoooooo...eereeeeeeeaa
mlr. pttps//s///24////aaaafff222
V. Papyan, X. Han, and D. L. Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences (PNAS), 117(40): 24652 24663, 2020. https:/::///oi org 10. 1073 /003//pas... /pap//passs.. 2015509117
K. A. Sankararaman, S. De. Z. Xu, W. R. Huang, and Goldstein. The impact of neu- gradient confusion and stochastic gradient descent. In
ral network overparameterization 37th International Conference on Machine Learning (ICML), pages 8469-8479, 2020. URL www..s.www..........e...e. wwt.ppeesssse/eeeeeee htt.111///aaaaaaaaaaa.....0
https://proceeednng: mlr
H. Shah, K. Tamuly, A. Raghunathan, P. Jain, and P. Netrapalli. The pitfalls of sim- plicity bias in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020, URL https: wtw.tttttt/t/tttteet htttps://proceedings www.:eeddiinnnn.niis.....
D. Soudry, E. Hoffer, M. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1-57, 2018. URL. https: //wmm///m///////// www.rrorg/pppee http//appes//vv/11// 188, html

---

J. M. Springer, V. Nagarajan, and A. Raghunathan. Sharpness aware minimization enhances feature quality balanced learning. In Proceedings of the 12th International Conference on Learning Representations' (ICIR), 2024. URI.htttp://ppenrevvies www.eeennettooutteeeeee net./oorum?dd--xDaajpppp....
G. Valle-Pérez, C. Q. Camargo, and A. A. Louis. Deep learning generalizes because the parameter- function map is biased towards simple functions. In 7th International Conference on Learning Representations (ICLR), 2019. httLltt////oppereeeeee .ntt/ forum/id=rye4g33.m
K. Wen, Z. Li, and T. Ma. Sharpness minimization algorithms do not only minimize sharpness to achieve better generalization. In Advances in Neural Information Processing Systems, volume 36, 2023a. Utt.https://openreeee wwt.ee/eeeeeoooommdddaaaaaaaaaaa
K. Wen, I. Ma, and Z. Li. How does sharpness-aware minimization minimize sharpness? In Inter- national Conference on Learning Representations (ICLR), 2023b. URL URLLhttps//ppeeeeiiie
L. Wu and W. Su. The implicit regularization of dynamical stability stochastic gradient descent. In Proceedings of the 40th International Conference Machine Learning (ICML), 2023, URL https://procceedings. mlr. ppwps/v2weeees//epe wt..00//ww23rrtttt
L. Wu, C. Ma, and W. E. How sgd selects the global minima in over-parameterized learn- ing: A dynamical stability perspective. Advances in Neural Information Processing Sys- tems (NeurlPS), 31, 2018. URL httttp::/pproceednng. wwwpddiinnnnnnninnnie.eeeee 088155666668829299077666666689
L. Wu, M. Wang. and W. Su. The alignment property of sgd noise and how helps select flat minima: A stability analysis. In Advances in Neural Informa- tion Processing Systems, 2022.
1e5c8dll66220e33ec550....o https:/pppeer.niisscc/pppppee wttppppcc/ppppe//222//aaaaa
URL https::/papers.ee
html
Y. Zhang. H. He, J. Zhu, H. Chen, Y. Wang, and 7. Wei. On the duality between Sharpness-Aware Minimization and adversarial training. In Proceedings of the 41st International Conference on 22w.g///5.h/......m
Machine Learning (ICML), 2024. html
http::/pppoceednng..ll..pp... mlr.
Z. Zhou, M. Wang, Y. Mao, B. Li, and J. Yan. Sharpness- aware minimization efficiently selects flatter minima late in training. In International Conference Learning Representations (ICLR), 2025. https Utt /ttp::::////////////eeee ew wwwpr//wwwwe.eeeeeeerrretieeeeee www.tttt.ooorrr.....aaa........
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] is generally preferable to "[No] ", is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset general, answering "[No]" " or "[NA] " not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer is often more nuanced, so please just your best judgment and write a justification to elaborate. All supporting evidence can appear either the main paper the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
used"). In
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: see main context and abstract
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize to other settings.
It is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the limitation of the paper at the end
13

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or a speech-to-ted teeecttt-ttett system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification:
See proof in appendix C.9
C.11
C.13
C.7
and theory section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
See experiment section in main context and details in section
C55
4
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. novel architecture, describing the architecture
For example, if the contribution fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code available at http:p//gg..hhua..ooo/ccaappootp Analysis_ande and Simplicity-Biaass.......a.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc/
wtt.oodeessiiissioooooooi.ooo..o public//uuides/CodSSuitt ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ctp://gguuiee/ooeeuumbmiiiiiii ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See experiment main context and details in section
C.5
C.3
C.4
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
See experiment section and details in section C.5
C.4
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See experiment section in main content and details in section C.5
C,3
C.4
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
See details in experiment section in main context and details in section
C.5
C.3
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction..
Broader impacts
Question: Does the paper diseuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address socictal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups). privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
17

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: See experiment section in main context and details in section C.5 C.4 and related work in appendix B
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, wwwpeets.pppsiiittaaaea th thcode com/ commdaaasetss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of derived asset (if has changed) should provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/modell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
18

---

Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to L.MM policy http:s///eerrissccc/ooffeerreees for what should or should not be described.
19

---

A More discussion on limitation and practical implication
Assumption and simplification: Our theoretical analysis is limited linear approximation near local minima, which may not capture the full dynamics of training. While our analysis is local, this regime remains highly relevant: empirical studies show that loss landscapes are often locally approximately quadratic, even in overparameterized models [Li et al. theoretical frameworks for optimization and generalization [Achour et al., 2024 Wen et al.) [2023b] Since training often proceeds through plateau phases near minima, local dynamics are central to understanding stability. Like gradient flow and neural tangent kernel analyses, our work adopts simplifying assumptions that, while not universally valid, yield valuable insights. Our approach aligns with prior work demonstrating the utility of local approximations.
2018). motivating many
Other than linear assumption, we also utilize assumption and simplification such as i.i.d. data, two- layer ReLU networks, and restrict ourselves to basic optimizers (SGD, SAM). We offer clearification for the above assumption in following:
First, the i.i.d sampling assumption is standard in theoretical deep learning (e.g., generalization bounds, stochastic processes) and reflects how minibatches are typically drawn in practice. Studying non-i.id. settings like curriculum or imbalanced sampling is a valuable direction for future work.
Second, while generrannil solutions are restricted, they reflect key structures observed in deep networks-especialy especially in activation patterns. ReLU networks exhibit rich symmetries (e.g.. permuta- tion, rescaling) that yield exponentially many equivalent solutions with identical loss, gradient, and Hessian, making our framework practically relevant despite its constraints. Such simplifications are common to enable tractable analysis.
Third, we focus on plain SGD and SAM to isolate the roles of noise and sharpness in a clean setting. Extending optimizers like momentum SGD or Adam, which interact with curvature in subtle ways, is a promising direction that can reveal more optimization properties under data geometry structure.
Lastly, our analysis reveals limitation of optimization dynamics in settings where the data exhibits high redundancy or strongly correlated features. In such cases, the linear stability criteria become less sensitive solution complexity, many parameter configurations yield similar activation patterns and induce comparable coherence measures. This results in a potential blind spot: the optimization algorithm may fail to distinguish between simple and complex solutions if the underlying data geometry does not sufficiently break symmetry. Recognizing this limitation offers a valuable direction for future theoretical work, particularly in understanding how optimization behavior is shaped not only by the loss landscape but also by the structure and diversity of the training data.
Practical Implications: In terms of practicality of the proposed coherence measure, it is com- putationally expensive and not typically used in training. Our work is intended as a first step in highlighting coherence as potentially valuable conceptual lens for understanding training dynamics and generalization. While the coherence measure is not yet standard diagnostic tool, this is also true for many theoretical quantities when first introduced. A relevant example is sharpness (e.g.. max- imum eigenvalue of the Hessian), which was originally difficult to compute at scale, yet it inspired successful optimization strategies such SAM that approximate the principle indirectly. Similarly, although computing exact gradient coherence or per-sample Hessian quantities is currently expen- sive, we see this motivation for future work on scalable surrogates or proxies. Our contribution is to show that coherence connects to stability in a theoretically grounded way. suggesting that it could inform the design of future optimizers or monitoring tools, even if not computed directly.
For potential direction for design of algorithm, one concrete idea is to adapt the learning rate based on coherence between mani--atchhss- baducee--reuuinng it when gradients are aligned, and increasing it when they diverge. Other possibilities include regulator that promote gradient alignment or batch selection strategies favoring coherence. While we have not explored these experimentally, view them as promising directions for future work.
Larger Empirical Scope:
To investigate the scalability and practical relevance of our insights, we conducted additional experiments on the CIFAR-I0 dataset using a ResNet- 18 model (11.7M parameters). To approximate the coherence measure in tractable way, used the pairwise dot
product of per-sample gradients normalized by the maximum gradient norm: max Vill For further approximation, We compute this on a fixed subset of 100 samples (10 per class) to construct a coherence matrix. For the feature rank calculation, we record the features from before the last linear
V4
20

---

layer for whole training dataset and use PCA to calculate the rank of feature with explain ratio up 99.9 percent. According to our experiments, we find that the feature rank decrease as expected and the the approximated coherence measure also closely follow the training process despite milder trends due to the approximation. The results are shown in following:
Optimizer
Rank
Coherence
SGD
148.33 + 3.22
1.0045 + 0.0020
SAM (0.05)
157.67 + 9.29
1.0052 + 0.0060
SAM (0.1)
144.33 + 7.10
1.0771 + 0.0680
SAM (0.2)
128.67
5.51
1.0907 = 0.0890
Table 2: Effect of Optimizer and SAM radius on feature rank and coherence. We record the rank and coherence subset of CIFARIO after training for 200 epochs.
B Related Work
Flat vs. sharp minima and generalization. The connection between the geometry of minima and
generalization in deep networks has been studied extensively. Hoccreiter and Schmidhuber [1997)
first argued that flat minima (regions in parameter space where the loss remains low) correspond to
better generalization, while sharp minima might lead to worse generalization. Keskar et al. [2017]
provided empirical evidence that large-batch SGD tends to find sharper minima than small batch SGD, correlating with higher test error, bringing this idea to prominence. However, Dinh et al.
2017] pointed out that the sharpness of minimum is not an invariant property (reparameterizations of the model can change the Hessian spectrum without affecting generalization,, cautioning that one
must carefully define "sharpness" (e.g.. by normalizing for scale or using local subspace measures). Our work incorporates this perspective by focusing on relative stability analysis: effectively, we look at sharpness in the context of the optimizer's step size and algorithm, which is invariant to certain rescaling (for example, SAM's notion of sharpness implicitly accounts for parameter scale through the perturbation magnitude).
Sharpness-Awer Aware Minimization (Foret et al., 2021 and follow-up methods (c.g.. adaptive SAM by Kwon al. 202 investigations in Chen et al. 2023) directly encode flatness into the training objective. By explicitly favoring flatter minima, SAM biases the training trajectory toward solutions that are less sensitive to perturbations in parameter space (Zhang et al. 2024 Chen et al. 2023]. Empirically, SAM has demonstrated improved generalization actoss many tasks. The work of
Andriushchenko et al. [023) is particularly relevant to our findings: they show that SAM not only finds flatter minima but that the learned features (e.g., the covariance of layer activations) tend to be lower rank, suggesting the model focuses on a smaller set of principal components of the data. This aligns with result that SAM bias can lead to simpler (more coherent) feature usage. There have also been studies connecting flatness to other measures like noise stability: Jiang et al.) (020) evaluate variety of complexity measures (including some Hessian-based) to see which best predict generalization; they found that no single measure works universally, but a combination can. Our introduction of coherence could add new dimension to such measures, since it incorporates data-dependent interactions.
Linear stability. Linear stability has gained increasing attention in recent machine learning research as tool to characterize the local convergence or divergence behavior around minima. This framework enables a unified perspective that jointly considers the data distribution, loss landscape geometry, and optimization dynamics. Prior works such as Wu et al. [2018, 2022], Wu and Su [2023] leveraged linear stability to analyze how noise interacts with local minima and to derive convergence criteria based on the Frobenius norm of the Hessian and Ma and Ying 2021] use the framework of linear stability to study property of noise in terms of higher order moment. More recently. Dexter et al. 2024] introduced a coherence- of the data through the Hessian. These lines of work provide valuable new perspectives the interplay between data and optimization pperspectiees that are difficult to obtain through classical optimization analysis alone-and offer deeper understanding of local training dynamics.
measure that captures fine-graing mne-grained alignment properties
Our work closely related to [Wu et al. 2018 2022 Dexter et al. 2024 Wu and Su 2023 Mulayoff
and Michaeli 2024 Compared to Dexter et al. 2024 who focused on the analysis of SGD, we
21

---

take one step further and analyze random noise injected SGD and SAM. Specifically, we investigate how SAM influences local optimization dynamics and how interacts with the structure of the data. Furthermore, we provide an explicit analysis of two-layer ReLU networks, revealing connections between linear stability, neural activations, and solution stability. This helps elucidate the role of SAM in shaping both the geometry and generalization behavior of trained models. Finally, unlike these prior works, we also set up realization of the theory to a two layer neural network and discuss how the insight from analysis in linear stability can be transferred to the neural network and show how the pattern of activation in neural network can related to result of linear stability, Specifically, explicitly construct a 2-layer neural network with several solutions of the same sharpness but different complexity (captured by the sparsity in the activation pattern), and show that SGD (and SAM even more aggressively) prefers simpler (sparser) solutions.
Stability and implicit bias in optimization. Our use of "stability" is in the sense of dynamical stability of fixed points for the parameter update. This differs from the notion of algorithmic stability in learning theory (e.g.. .s..[rartte et al. 2016), which concerns how sensitive the final model is to removal of training example. Algorithmic stability yields generalization bounds but doesn't directly explain which solution is picked. Nonetheless, both concepts are linked: an optimizer that always returns the same minimum despite small data perturbations might be one that has a strong attractor basin (stable solution).
A large body of work on implicit bias of gradient methods has focused on linear models or homoge- neous models, proving that gradient descent converges to particular norm Norm-minimizzng solutions or maximum margin solutions (Soudry et al. 2018 Gunasekar et al. 2017]. For exadple, et al. 2018) show that for linearly separable data and logistic loss, SGD converges to the max-7-2-margin classifier. This can be seen as form of simplicity bias (since a max- max-margin separator in linear space is a simpler decision boundary than a complex wiggle that also separates the data). In deep networks, Lyu and Li [2020] extended this to deep homogeneous networks (showing convergence to margin maximization). These works explain which solution among the continuum of minimizers is chosen, in terms of margins or norms. Our work provides a complementary lens: rather than characterizing the final solution in closed-form, we explain it via the dynamics preferences (coherence and stability during training). Margin and flatness might be connected; indeed, a large margin classifier often corresponds to a broad basin in loss landscape. Exploring the link between coherence and margin could be interesting (perhaps high coherence solutions also align with large margin in classification tasks).
The notion of simplicity bias has been documented empirically by several works. Arpit et al. [0117] found that deep nets first fit the "easy" patterns (e.g., clean labels) before memorizing noisy data, indicating a bias towards simpler functions. Kalimeris et al. [2019) and Valle-Pérez et al. [2019] argued from a infornattio//comiintoiiis perspective that, because there are exponentially more complex functions than simple ones, random initialization plus SGD is more likely to land in simple function that fits the data (if such exists). (hhah et al. (2020) (Pitfalls of Simplicity Bias) constructed datasets with multiple features to quantify this bias and showed it can hurt robustness. Our results give a theoretical underpinning to these observations by linking them to the Hessian structure and training dynamics: effectively, the simple patterns correspond to directions in which many data points have aligned gradients, hence those get learned quickly and form a stable basis for the solution, whereas complex patterns do not align and either get learned later or not at all.
Recently, Morwani et al. (0033) provided rigorous analysis of simplicity bias olnn ReLU networks (in the infinite width, lazy training regime). They defined simplicity in terms of the function depending on a low-dimensional projection of inputs and proved that indeed gradient descent finds such diwddmmeniooall solutions under certain conditions. Their findings dovetail nicely with our coherence interpretation diw-dimensional projection usage implics high alignment among gradients of those inputs). While their analysis is specialized to particular regime, ours aims to be more generally intuitive and spans beyond the NTK regime by considering the Hessian of the nonlinear model.
Another related concept is Neural Collapse [Papyan et al. 2020 which describes that at the final layer of a classifier, the class means and features tend to align in certain simple symmetric patterns. Neural collapse occurs in the late phase of training and indicates a sort of self-organizationn of features. This might be seen as high-coherence structure in the last-layer gradients for examples of the same
22

---

class, While our work did not directly address neural collapse, the idea that training dynamics lead aligned and symmetric configurations is broadly consistent.
Data geometry and gradient alignment. The role of data distribution learning dynamics has been explored under terms like gradient confusion (Sankararaman et al. 2020) and gradient aligument. When gradients of different examples are more aligned, training converges faster and perhaps finds simpler models. Sankararaman al. [2020] demonstrated that increasing overparameterization can reduce gradient confusion (making gradients more aligned by virtue of more flexible models finding a common direction) up to point, which speeds up convergence. Chatterjee [2200] studied how examples that are hard or easy influence learning: easy examples likely align well with the gradient direction. Our coherence matrix formalizes one aspect of gradient alignment (at a second-ordes level, but one could similarly define Gıj = Ve, Ve, for first-order gradients). In fact, one could incorporate first-order coherence in our analysis; we focused on Hessian since it directly ties to stability, but gradient dot products matter for the actual update direction in SGD. A high Hessian coherence usually also implies gradient coherence at w" if ut is zero training error solution (gradients are zero at w", but consider nearby points earlier in training). Also, this Gram matrix-like definition of alignment appears in several related formulations.
its simplest form, the gradient Gram matrix G.j V Vl, has been used to quantify gradient diversity, mutual coherence, or feature alignment in analyses of SGD [Sankararaman et al. 2020]. In neural tangent kernel (NTK) theory or fisher kernel terminology [Khanna et al. 2019], closely related object appears the empirical kernel matrix, whose (i.j) entry is given by V f(,, w) V w). which offer interpretation for the relationship among data.
In summary, our work synthesizes ideas from these threads: we put forth coherence as a data- dependent quantifier that influences stability of solutions, thereby linking the optimizer's implicit bias to the geometry of data in parameter space. By doing so, we integrate perspectives from flat minima research, implicit bias theory, and empirical studies of feature learning, We hope this unification will spur further research in understanding and controlling the biases of gradient-based training in deep learning.
C Appendix - Experiments and Proofs
C.1 Illustrative example for (C, solution and calculation of the r and trace
Recall our construction for (C, ( generallzzzng solutions. We design W1 by an exhaustive enumera-
tion of all possible feature constructions of size C. In other words, Vfai, a2. E {0. 10 let the
7th row of W, be Wi.; = r((11)01, (-1)a2, (1))),..(1111"") (-1)ac, O, ........ with 1+ 2 a, Similarly, let bb]] -r(C 1). We Wali 1-1)aar+a, For k > C. Wi, 0. W2lk] O, b[k] 0.
The following is the W1 with d = 5, c = 3, and hidden layer with 10 neurons.
1
0
0
0
1
1
0
0
1
0
0
0
(6)
0
00000
0
2000
0
23

---

The following is the W2 with d = 5, c = 3,
and hidden layer with 10 neurons.
The following is the b with d 5, 3,
and hidden layer with 10 neurons.
2
2
(8)
2
For the following, we show calculation of relationship between trace Hessian. We first show the trace of one sample and corresponding flatness. As we known in previous calculation that gradient can be as follows:
ReLU(W1,127)
ReLU W2,1 [ 1,14; > 0/æ:
(9)
W2,, [ 1,d,4; WW,d,; 0]z; W22,1[W11118 > 0]
12
And the Hessian is V (z. (for zero loss solution) Then the trace will be Tr VV (x:)) Now, have exactly activation time due the
bias (b) that impose such restriction. Therefore, the [ (z+)]12 = r2 p²+ + = =2 (d+11
24

---

C.2 Role of coherence measure in dynamics
Figure 3: 2-layer ReLU network. We found that the SAM method can impose strong regulation on the maximum eigenvalue elementwise, and this also reduce the strengthen of the largest eigenvalue of the coherence matrix. It means that the stability condition can be satisfied with smaller o. From experiments, find that the sharpness of the solution impose strong regulation of the eigenvalue of the coherence matrix.
Gobereste
Cohernane
Sarta Leved
Caberence Modti Lemoni
Connenc
Figure 4: 2-layer ReLU network. (Left) Comparison of SGD and SAM with different p. (Middle) We perform the same set of experiment with increased learning rate from 0.1 to 0.3. (Black to Red) (Right) SGD with different contrast loss strengthen (0.0, 0.1, 0.01). Through out the experiments, we find uniform shifting behavior for different algorithm with different strength but the relationship between max; Amaxx (H:) and (S) form strong regression line.
C.3 Experiment details Local Linear stability in quadratic loss for different algorithms (B,a)
The experiments in this section serve to understand the local behavior of in terms of the linear stability. By studying the behavior near the local minimum, we aim to verify the correctness of our theory. We follow the same experiment set up reproduce the plot in Dexter et al. [2024], We first initialize H, mejef for all i E [o] and H; me +10 ++1 otherwise. We use m 2n so that the sharpness of the minima (Amax(H) is controlled to be 2. We set the learning rate to smaller than 1 make sure diverging behavior arise due to noise not the sharpness. The loss function in the optimization is I(w)= = 1 Σn W.Ww and the gradient is Vi(w) theory setting. For all the experiment in this section, we set n 100. For each set of parameters (B, 11, o), we determine divergence or converence by conducting 1000 steps update of the weight and calculate the norm of the weight. If the weight norm is 1000 times larger than original initialization, we classify it as diverging and vice versa. For each tuple, we perform the experiment 10 times. the diverging behavior occurs more than half of the experiments set, we mark the specific tuple as diverging. The experiments involved in our work are done with CPU only.
D H2w that satisfies our
C.4 Experiment details Local Linear stability in mse loss for different algorithms in 2-layer ReLU network.
We use the dimension of data d = 100 and the dimension of hidden layer is set to 50. Further, we use the batch size B = 10, the SAM epochs and log the loss over epochs. All experiments comparing different algorithms are done with same initialization using the same random seed. The results are averaged over 5 runs.
0.01, and the learning rate 1/ 0.01. We train for 50
25

---

C,5
Experiment details Global: The role of coherence in the training.
To make the analysis more computationally tractable while tracking multiple quantities simultane- ously, we reduce the model size: the input dimension is set to 15, the hidden layer size to 10, and the number of training samples to 50. All other hyperparameters remain the same as in the Section 4
26

---

C.6 Some identities and definition
We summarize the background and identities used through out the proof.
Definition 3. The definition of Hessian and subset of Hessian where 24 is random variables with Bernoulli distribution
B H1 B ==1
HH = Σ H
(10)
Lemma C.I. Consider two matrix A, with being Positive semidefinite, then
Amax (A) Tr[B] Tr[AB] 2 Amin Tr[B]
(11)
The Amin; Amax are smallest and largest eigenvalue of the matrix A.
Lemma C.2. Consider two matrix A, B, C, then
Tr(ABC]= =
(12)
Lemma C.3. 11212 norm inequality: For any I R. 11111/122 I ||0|| S Vdl|==12
Lemma C.4. Binomial coefficient: For all n., E such that S n, the binomial coefficients satisfy that
(5
11
n1
(n=)) k
n
+
(13)
k
Lemma C.5. For any matrix M E IR ||Mll I ||M]|s I M where || Is, is norm of the spectrum of M, and the inequality is obtain through 11-12 norm inequality. Lemma C.6. For matrices Mr...M E RRxx, Tr[M,...MM s Me....sssss. (see Bhatia (997]]
C.7 Proof for Random perturbation
Theorem C.7. Give update rule
1. The condition for divergence is the same as that for SGD (Dxttr et al.
2024 follows:
1
n
2. (Comparative Divergence Speed) Suppose Tr[Jak] < Cock for some constants Co and og,, then the divergence rate of the random perturbation method asymptotically within constant factor of that of standard SGD:
Elllww|1
Random, lower bound O(1)
lim
E El 12 SGD, lower bound
3. Suppose the step size satisfies the convergence criterion established in prior stability anal- yses (e.g., Dexter et al.) (2024)). Then, under the random perturbation update (3) the expected squared norm of the iterates remains bounded k -
lim FlW Wk lupeer hound O(1)
Proof. Define H 1 Σ H.. Now consider k steps after, we can have expression for uy as following:
wh = Je..J
Σ II H.).
(14)
1=1
0'++1
We consider the dot product of wa and take expectation over all random process in between:
Flw wx] = F[[ wio Σ II
(J.
H&5,)
Σ
1=
M=++1
J
Elug Jy. Ja... wol + n" E
II (e)H())))
II J0H18
(15)
27

---

We first consider the second term. Note that all the cross terms are eliminated as they are independent each other:
II H))))
II
e=(+1
M=t+1
=n E
H,)
o Σ
Jk....
2 of
Pk.
min
(16)
The term TR. can be decomposed into the following according to Dexter et al. 2024
v20 12 min (H) E[Tr((J (.. 22 of (H)
Tr + 2
Hy ... 1! ve Hy
Bn n1
y1...yt
2 7 min (H)
T
+ 1 11
1) Amax (
(17)
The last term represent the growth of the perturbation over time step. Contrary to the original analysis, the dependency of the magnitude the summation dependency, the criterion for diverging is still the same as we only require that (2) 2 1)Amax(HH) to be larger than i.c.,
summation of geometric series. However, despite
2
72
1)
(18)
max
Now, observe that the perturbation base method will change the fundamental criterion for the diverging. However, it will change the speed of diverging. We first consider the summation.
12 Ammax )( 11)(1 \max ) (D.
1)* 1)
1/2 7 (H)
20) n 1) = =
12 Amax 13 -1)
1=1
(19)
Now we impose assumption on the growth of the Tr(J2k) by assuming that it grow with pattern * and calculate the sum of it.
Caa(a* -1)
Coa'
(20)
Finally, we temporarily denote the term (3 Amax (H)) - 1) to be and the overall lower bound for the calculation will be:
Coalat - 1)
r(r 1om--1. -1)
Elwi wk] 2 C + nds rk + o
a + nd5
(21)
28

---

Now we set the = 1 and compare with the original naive SGD and set that a 2
Eluug Wi Random, lower bound
lim
oi
x2
(22)
Elug wk SGD. lower bound
The escaping speed of the random perturbation base method is faster by constant. Now set that S r
2 E Elwgg Wk Random, lower bound 1 + 0f min F
r
lim 11000
(23)
Elwg wk JSGD, lower bound
No matter which term dominates, we will have constant faster escaping efficiency compared to the original naive SGD.
Now, we consider the convergence behavior, we first note that there exists c and such that Jf..... S C((1 e)² + +)* Here, we temporarily denote ((1 - e)a + E) to r. We apply
this identity to the above equation and we will get the following:
EluE wa] S O+ + Amax
Σ Cr
1=1
(24)
r(1 - pk))
Crr + 1/² Amax
1 --r
We consider long term behavior (i.e., k 0c)
lim Elwi wk] S 17 Xmax R-000
(25)
1
We observe that there exist residual terms relating to the perturbation itself and this fits our intuition that the random perturbation method will usually hover around the minimum as the noise injected can lead to less accurate estimation of the gradient direction.
29

---

C.8 Proof for divergence theorem
Theorem C.8. For update rules as following:
Wer = (T H) L H)
(26)
Define Jq = -7- (T H)), then
1.There exist My such that
E[JE ...I
T
T JI...kl Mr
(27)
with
M₁ j2h
1
Σ
(I L H)H ... LH)H (I+ (T+LH)
H ny (T
LH
Bn
n
a
a
Vi..0:=1
(28)
2. The Trace of Mj can be lower bounded by the following:
Tr[Ma] 2 2k
)a(1 + Amin (H)) Tr
Σ
H. H.H
(29)
Bn
n²
01...u==1
3. The Trace of M2 is lower bounded through d:
Tr[Ma]
22 n1
-1) +
Amial )mi)(H))
1 22h nd5 Amax (H) 2
(30)
B
The diverging criterion for SAM under linear stability is:
Amax H)
σ n
21 11)21110
L Ami (H))
(31)
B
Proof. We prove by induction as follows.
Base case: k=1
E[J1 T J1] E((T 1) LT - HT. + 2)H)
F - T.
nP
HHH HH.) म I'P H +
T²p²
HH? H
a
a²
2n 2
np 12 17
2
E|
n²p H
HE
T²p²
HE H
a
a²
(32)
We know that
E(H?)
112
+
Bn 7
Σ H?
(33)
and will have
EiJi J,] = J2 22(
1
(1
H) >
HT 2
Bn
(34)
-Mi
30

---

Induction case: k-1 to k
EiJk T ...J T' Jr...Al Jul E[Jk T
Ms Mkl
=[((T - 1111 nP H)*
MyMM. Ma-1 1 1
7P H H))
7p M - 7 Ha Hx + I'P qe H
-E[Mk-1 - 7
nP HH + P
HHAMM--H + p2pp
HH
a²
-M +np
(I
P H) H.M H 2H)
P
nB
n²
a
a
(35)
Now, we subsititude the expression of M into the expression and we will have the follows:
T J1 J1...K] 2 JM + + Elja T ...I'
1
(1 + - H +LH)
BB
nt
=]]j2(0-11 + 11
1)
1/2 (k-1)
Σ
(1+ L H) mn ... H? (I+ L H Hy .I L
Bn
n
a
a
( nB
1
(I
+
P H)
Hi (2( 1)
n
a
2(k
1
1
Σ
(1+ P H I. l H 91
(1 H ... p (I l LI) LH)
Bn
n
a
a
a
Vi V=
22h
+ 17
2/
1
Σ
(I l H H ...
(I HHHz (I
P H) H (I + H
Bn
a
a a
a
y1...lk
M4
(36)
Now, we wish to analyze the trace of the matrix Mj. For simplicity, we analyze the latter term of the expression.
Tr [r[M+]
1 Bn
Σ
n
(I+ P H)H 9o ... .......I L HH (I P H))... (I P H))
n²
a
a
a
Ve...e-
(37)
We first focus specific term in the summation.
Tr
P
H)H (I. P
H) 91
(I+
P H) H)... Hy (I
p H)
a
a P
a
a (I+ L H) Hy....Hy...
Tr((T
0
H)² H yu (T
H) H
(I P H2 m1
(T+
P H
a
a
a
2 (1
+ Amin 2H))2TH Uk
0 HH 21 (T +
L LH)...H...
a
= (1 Amin (H) (H))313 3 (1 + 11 H! b1
(1 2 || . Hyp (1 2 H)H21 yk
a
a
2 (1+ + Amin (H)) Tr Hy H² Hy (I p H) (I....I (I
H) H2 m
(I
p H) H).. (I
p H)]
a
(38)
Here, use the lemma
C.I By continue pruning, will have the following:
31

---

P H)H Tri(I + P H Hy ... +
a in (T+ + P Hy...HHu. Hu (I + L (H) 2 (1 + Xmii (H)) Tr|H Hy, ........,, H Hy
a
(39)
We apply this to the summation in Ms and we will get
Tr[M&] 2 22 Bn n22) (1 Amin (1)) Trl
Σ
yn Hy ..Ilyl
(40)
Now, we connect the M₂ with the coherence measure in the following:
Tr[Ma] 2 27 2
P (1
Amin (H))
Σ
Hy H...H Hyul
Bn n
yn...y==1
= 1) 2k
(111 +
P
mmin (H)) 2k
Hy Hy 1
Bn
n
M1..36=11 =1
2 17
(1(1 +
Amin (H)) 2k
Σ
H yk
H y1 113.
Bn
n
d
VI...e==1
(41)
1
2 n22h
(*11 +
min (H))2k
Tr(H M1 H 12
Bn
n²
d
2 17
2k
1
(1 +
Amin (H))
Tr
Bn
n²
d
1
1
2 11
2k
(a +
Amin (H))2k
Tr(
Bn
n
nd
for the above we use lemma
C.5 and we know the following from Dexter et al. 2024
Tr(H
Tr
< Σ [T
(42)
La
y
Finally, we can have the following:
1
n² nd &ogh 2 (Tr(H+)))
Tr[M&] 2
2k
(1(11
+
Nmii (H))
Bn n2
12
1
)*11
+ p
Amin (H))
nd Log 12 (Tr(11+1)²
1 n
Bn
n²
a
(43)
= 1,
1)at (1 +
p Amiin (H))
22h nd (Tr(H
1
B
2 2k n1
1)*(1 +
0 Amin (H)
22h nd. Amax H HH)2k 2k
B
We then will have the following condition for diverging:
Amax (H) 2 0 n
- 1) (1 L Amin (H))
(44)
"1 B
32

---

C.9
Proof for convergence theorem
Theorem C.9. For update rules as following:
P H))
W41 = (I nH +
(45)
a
1. There exist N, such that
k Nr
EiJK .F.J.. Jf. J....kk] 1 Σ 2(k
(46)
r=0
and
11
N4 = 11
2k(
Σ
(T+
nn ... (I+ 2 H
H H2
(I P L ... Hy, (1 + L H
nB
n
a
a in
a
(47)
2. The N, can be upper bounded as following
TH[N,] < 11 B
-
d ab Amax (HSA)) 4h
(48)
o SAM
2k
3. Suppose there exist (0,1) and we will have converging criterion such that
<
P
x2
Vi [d]
and
a
7
lim 10000
5
1
1
nB
m2
1
E
(I L H yx ...(1 + L H (1+ P H)...
H. nn (1
P H)
91-9/2---M4-
(49)
then will have that lingg IF Jt.. =0
Proof. We first define N, as follows:
N₂ = 1) 2k
Σ
(1+ Hm 2 LH)H, (1 LH).. H (1 + L
nB n
a
(50)
We define No
we want to prove the following:
k Nr )) ((k-r)
Fl
J
Σ
(51)
r=0
Base case: k=1
= E[([ -n "P (HHHT T( nH 7P ((H))
a Eu+ L 2 -
-2 nB nt
(52)
(1-6)2No + N₁
The first condition (1 +) e) / is achieved when the condition of the assumption satisfied. We demonstrate why that is the case
I=I-nH(1+ P H
(53)
a
33

---

and observe the following
-(1-c) 1 J 1 (1 =
(54)
First, we focus on the By replacing the definition of J into the equation, we will reach
J² (1-
(55)
(1 - (1+ (0)(+++1)))) [1))² 31 61-6)
(56)
By removing the square term,
(1 --- nI + + 3 (1 l
(57)
Rearrange will give
el 3 n + H)
(58)
By decomposing each eigenvalue direction, we can have that
- + Px
(59)
"
We perform the same operation on the other direction and we will have
2 -
A
X3 a
(60)
1
The e in our analysis represent the deterministic term in each step as we use it to upper bound _ Compared to SGD, the e can be larger as the term I H larger than I I- Hn n H² in each direction. The deterministic part of update process can shrink faster compared to the SGD. The analysis implicitly incorporate through e. For the other part, N1 represent the randomness in the operation which can be directly checked that if we increase the batch size to n1, we will have the term vanished. The format of the N, rely on how different sample align with each other and this form origin of the noise. Compared to the tradition analysis, we can have more subtle observation of the noise through this specific form as we no longer need to assume the structure of the noise or we can assume the how each sample align with each other to see the final form of the noise and this can reveal more insight of the relationship between sample for further analysis. Now, we proceed to induction step.
Induction case: k-1
k-1 1
(K-1))
(k-1) N..Jaa
EJ
H J JR] 3 EEJ
(2(k-1-1)
r
r=
= JT[ h-1
(k-()) (k-11) N.)J + 1p( n
k-1
(k-1)) N.) (T)
(1 )) 2(k 1--) )((-
Σ
(T
+
P
H) H
Σ
(1 3) 22
n²
r
0=0
3 - 2)
(1 - c) 2(k 1-r k - 11)
N₂ + 1
1
1
2)2(k-11))
kk (K-1) (K-1) (I l - H)
nb
n²
r=0
Σ 2(h-))
k-1
(k: 1k-1) 1)
Nr + 17
k-1
2(k--1-))
(k-1) E(+
(I+ P
HH p 'H)
r
nb nt?
r
a
a
A-1
(k- (k-1) Nr + Σ (1 5)
R-1 1
(k- (k-1) N,+1
Σ (1
2(
r))
2(
11-)
1-r)
r
0=0
(61)
34

---

By reordering the term, we will have the following using lemma C.4
Σ 11 c)
k-1 1
2( m)
-
Nr + Σ (1 c) ((2-r)
h -
1) Nr
r
1=0
1=1
(1 2)2h No + Σ ((1 -c 2)((m))) (k- 1 (1 2)((k-)) h (k=1)
k-1
(r- )., + N
(62)
k (1 (2((k))) Σ
k
N
Similarly, as require that the [r[ term to be smaller than e², we can upper bound the term with constant C' such that 1 Tr[[N]] & C. and therefore,
er
&
A (+)
k Σ (-) (1 == c)2(k-n
Σ (1 ()(
Tr S
C
(63)
=[(11c)22
For the last step, ask the [r[N, term to be smaller than can further bound it. Despite we can upper bound through e, we can still analysis its magnitude. If it is smaller, it will also converge faster. The distinction between SAM and SGD is that SAM has extra multiplication (I + 2 H) and this result from the operation with the gradient ascent intermediate step. We can find that this can potentially make the process unstable it amplify the noise through out the process and this fit in to our general believe that SAM can make the optimization process less stable but still converge fast due to the shrink of the deterministic term. Note that unlike the tradition analysis that require step size to be 1 I 2 (M we ask for different criterion for converging. This due to the fact that analysis the origin of noise which comes from aligmment of samples and the traditional analysis focus more on the deterministic part which directly involve eigenvalue of Hessian and usually the analysis specify the noise with covariance matrix instead.
we
To answer the relationship between and the N,. We first consider the following inequility
A1) & Tr(s*)
Σ
[ H ||....I.HH H& lI
y1 m1..
(64)
Tr(H,, Hy ).... Ty
n (IF((12))
S nk dl >max
Now, we defined a new form of coherence matrix and Hessian to accomadate the SAM algorithm as following:
SSAM.
V (T((T+ 2T) l m)
(65)
a
(I+ l H Σ H
HSam,
(66)
1m1
Now, go back to the N,
35

---

Tr(N,)
1
Tr((T+ L H (T. (T+ H (T 2 H)
H yk.
(T
L m)
BB
22
11/
1
Σ
I1 H yb ... L H 1|
nB
11
2k
1
Σ
11
L H1 H4 yb 1 |1(1
L H1 H a
BB
a
2k
1
VVd max II(1 L H. 11 1= I=1...
1
B
a
11 2h
1
> "Vd max d' (Amax ((T + P H)H))) n
1
B
i=l...
1
1
yk gokt 2 max Mmax (11 & Amax HSAM) akk
S 117th 2h
B
Amax SSAM)22
1
1 y c 22 Amax (HSAM) OSAM
B
n
(67)
In our analysis, through new definition of the coherence matrix and Hessian, we find that SAM is performing optimization on the loss surface that is amplified by + P. H. The loss surface is
sharper as it give larger eigenvalue in each direction. If we compared about the ratio Amaz r²
(H) and
Amax ( we can see question about which one is larger or smaller will need more information JaM about the exact coherence matrix to determine. They can be the same or different depending on the relationship between samples. However, for both of the method, if the solution give larger coherence measure, they both converge faster for the specific solution and vice versa.
C.10 Proof for theorem 3.4
Proof. We know that the V can be written as following:
ReI.U(Wi,127)
ReLU (,,)) 12,1 1,13, > 0]æ;
(68)
W2, 12 1,2, 0].; W2,1 > 0]
W [Wi,,, > 0]
where the gradient is taken with respect to parameter (W2, Wi, b) in sequence. For each element in the coherence matrix, we will have
$ || 11 || v Tr( 11 u -
(69)
As the activation of the samples are orthogonal each other in memorizing solution. The orthogonal in activation will also give the gradient orthogonal property and therefore,
Tr, (VI.Vf)²²
(70)
Therefore, the coherence matrix is diagonal in the setting. The corresponding coherence measure is small compared to other solution and we can conclude that the memorizing solution relatively hard to find during optimization process as seen in the prior work with coherence measure. The reverse also true. If the coherence matrix diagonal, then the solution is memorizing solution. As if we have two data activation overlap, the gradient product will not be zero.
36

---

C.11 Proof for theorem 3.5
Proof. Suppose we draw a dataset with size uniformly random. The coherence matrix becomes
block diagonal matrix with eigenvalue being 2(d++ ((d+1)$ max |S,] where S is the set with data matched to specific feature extracted by W1,1 and we know the following:
Sus
(z.) Vu (z2)) 2(d 1)
(71)
We estimate the following:
P( max i=1...2c
|S 2 nu + nc).
(72)
We can find that by union bound
20
P( max 10..2
|Sa] 2 ne) S P([S:) nu ne)
(73)
Let 1 and 6
Also, we know that by |S;] is a sum of independent variables X that fall into the category and we can formulate through chernoff bound:
C+log
ze
P[[S: 2 nu ne) P Σ a X3 2 cc) exp(( I exp(-(C log f)) c-0
Xx
(74)
Therefore,
2c
P( max (=1...2
|Sa| 2 + nE) $
Σ
P([S.)
2 nu ne)
1=1
2
(75)
C-8
e
i=1
< 6
C.12 Proof for theorem 3.6
Proof. For the generalizing solution, we can analyze the element in the coherence matrix. Tr((I + g HI) & H)) We can see that if two samples do not share the same activation, the specific a element will zero. We consider average value for the element that are within the same cluster. As they are in the same cluster, the H; H,- Hs
E EI Xa) Tr[[I+ LI)H EL X
Tr| L & + _ HHHHH,
E( Σ Xx)
Tr|H?]
2p THE
X
P² o²
Tr(H Σ XxX*]
kR
El Σ Xx) Tr(Hs)
1+
2p Tr(Hs]
X
Tr(H3) Σ XaXwi
(76)
where the Σx X₁ are random variables indicating the sample inside the specific cluster or not. The other term is the strengthen of coherence elementwise. We can observe that this is convex function terms of the random variables and therefore we can lower bound by taking the expectation first in each random variable:
37

---

E( 2 Xx)
+ P TT((T+
P H (T
a
a
(77)
2 E
Xu TrHHs)
2p Hr
E
X1
+
1 1 n2 a²
TH
Σ lsk'
Xv Xw.
k=
The key lies the term E|ERE:
which not simply the multiplication of the two individual probability and we an find that is z ( x and we will have the following:
Xx
EIC E Xz)
L L H) /
Tr|(1+
L
a
2d + 1)²/1= 1+
2p 2d + 1)
+
1
))4(d+1)
(78)
a
2
a 22c
n
2"
2
" 2d + 2
V)& (1 2(d
1)
)a
1²
1 2
1
1)((d+1)
2c
a²
2
Now, the even stronger dependency of the number of features used can also be translated to the probability statement. With probability 1 5, the eigenvalue of the coherence matrix is upper
bounded by O (d+1)= (1
2(d+1)
2 )2 G 2 -(d ()(d+)))
using the same method
in appendix C.12
The additional higher order interacting term give strong additional bias toward solution with lower that the term become more significant when the data dimension (also
C, by observation, model dimension) becomes higher and cannot be neglect for modern deep learning scenario in terms of overparameter region. Also, check the correctness of result, find that by replacing p be zero, we can recover back to the case for SGD exactly.
To calculate the eigenvalue of max; Amax we will need calculate the average number of the data that align with each other as follows:
max Amax ((I + L H)H,) max Amax
(1I +
na
max
V
(I; 2c
2(d 1) P 2d + 1)
2
(79)
38

---

C.13 Proof for theorem 3.3
Proof. follow the construction of prior work Dexter et al. 2024 and focus on the term E ['T[[TT.) J] where J = 1 -- "2 HnH (Note that H, = 2; Hr where H; is Bernoulli with probability B being 1) with the probability of sampling each sample being independent Bernoulli distribution. The construction of set (Hi) is such that H; meief, Vi E [o] and H; = 0 otherwise, and Ain so that Amax(H) m A1. Note that Amax (S) ma and max; Amax (H,) m and the coherence measure is exactly Also under this construction, E| Jf JI...
m
a
Tr(E[(J?' 31 as all matrix involved are commuting with i.dd sampled.
We have following:
ElJr JJ E nH.
7P (I nH, OP H(H))
a "P
IPP "HH HH²) + HHAH
p²p²²
E|I 2n
(HH; H,H) + H a H + 11 + +2 H + ppp²
a
a²
= I - 2n - 2 71
H +
1
Σ (
a
Bn
n
(80)
Now, we calculate ETJ Jee (e1 is the only direction that involve interaction different samples) will give us
ET = 1- 21/1 - 2 x + n +
P
120² Bn n² (1
Xi
L 2x1 x1)
n²
a²
σ
(81)
We need the term to be smaller than to avoid growing infinitely
1 1 27A1 - 72 > + nA? + "
n²p²
-----111
1
1 72
-xm)
X
+
17²
(1 )1
<1 (82)
a
a²
Bn
We can rearrange and obtain the following:
2n ( P 2x1)² + 72( m1 1)(1 P x1 x 0
(83)
a
We find that we can divide the equation on both side by n71 (1 (x)1) and have
-2 + m + x1)
nl B
1)(1+
P x1) 00
(84)
a
a o
Now, we can rearrange and have the following:
71 +
L (x1)
- 1
+ +1)
(85)
0
(1
L
A1))
+ 10) 52
(86)
a
B
Finally, we will have
20 n
A1 + _x1
- 11-00 0)-
(87)
11 B
The additional term (1+ P X1) result from the SAM modified surface gives more restricted learning rate choice compared to the SGD. We can also check the result by setting p 0 and will find that reduce to the original SGD criterion.
39

---

C.14 Theorem from Dexter et al. [2024]
Theorem Let (Ji be a sequence of i.i copies of / defined in linearized SGD. {H, Nej
have coherence measure If
mmxx (H) 2 or Amax (1) 11
1)-
then lim ElI 20000
(88)
Theorem For every choice of Amax > 0,n E B. [n], > 0 and a E [n]. that satisfies:
20 (0 +
Amax
1)-1
(89)
There exists a set PSD matrices [Hi)) such that Amax (H) Amax and limg Eil EkI.k...illl N..
Lemma 4.1 Let Je be independent Jacobians of SGD dynamics,
(1) If
2
2 n.B
Amax 2 17
lim
Hy
11F
(90)
n
V1...
then lim F... J1133 =
(2) for some E (0,1). 1),
2 - (HH 7
7 172
vi [d]
and
lim
(
Σ
H
H
||
(91)
ck 10000 nB
n²
01-.
then lim
El| J
1| 0
40


Reviews:
[{"review_id": "F4IsOvudN2", "reviewer": "Reviewer_k5uF", "summary": "This paper presents a unified stability analysis for SGD and Sharpness-Aware Minimization. The authors develop a linear stability framework that covers standard SGD, a noise-injected variant, and SAM, centered on a data coherence matrix capturing the alignment of per-example Hessians. They prove that minima with high coherence remain stable under SGD while low-coherence (memorizing) solutions are unstable, explaining why SGD implicitly favors simple feature-sharing solutions. SAM further penalizes high curvature via an effective Hessian factor, imposing a stricter stability criterion that biases optimization toward even more coherent minima. Key contributions include exact stability conditions for both algorithms, matching lower bounds that demonstrate tightness, theoretical proofs linking coherence to an implicit simplicity bias, and an empirical study on a two-layer ReLU network showing that SAM consistently reduces coherence and effective feature rank relative to SGD.", "questions": "1. The analysis highly depends on several simplification assumptions, including local linearization, $(C,r)$-generalizing solutions, etc. In addition, the analysis stops at focus on a two-layer ReLU model. Are these main assumptions and conditions reasonable to assume and commonly used in real training of modern models? And is it possible to generalize the analysis to more complicated situations?  How do the authors anticipate these insights extending to deeper or more complex neural architectures? For example, would a deep convolutional or transformer model exhibit a similar coherence-driven stability behavior? Are there new challenges (e.g. multiple dominant Hessian directions, non-linear interactions between layers) in applying the coherence measure and stability criteria to much deeper networks?\n\n2. Measuring and Using Coherence in Practice: The paper introduces the data coherence matrix as a key quantity. Is it feasible to compute or approximate this coherence measure for practical-scale datasets and networks, and could it be used as a diagnostic tool?\n\n3. In the conclusion the authors suggest that their perspective could “open avenues for designing optimizers that align algorithmic bias with data geometry”, is there any insight or intuition on such algorithm based on the paper's discovery? Did the authors consider any concrete strategies, such as adaptively adjusting the learning rate or batch selection based on coherence, or designing new regularization terms that promote alignment of per-sample gradients?\n\n4. As brought up by the authors in the limitation, would it be possible to provide more experiments with larger models and real-wold datasets for verification of the paper's findings?", "limitations": "The paper includes a separate paragraph on the limitations of the paper, in which they discuss the linear approximation and lack of more experiments. Other simplifications and possible practical implications can also be noted.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength:**\n\n - Novel Unified Theory: The authors propose a unified linear stability framework that links SGD’s flat-minima bias and its implicit simplicity bias as arising from a common coherence-based mechanism. They derive exact stability conditions for SGD (with and without noise) and SAM in terms of a data-dependent coherence spectrum, establish matching lower bounds to confirm tightness, and formalize these insights as theorems extending prior analyses.\n\n - Empirical Validation: The authors include a well-designed empirical verification on a two layer ReLU network with analytically constructed minima from memorizing to simple solutions. They show that both SGD and SAM converge to low complexity solutions and that SAM achieves lower coherence and feature rank than SGD. These results, though based on a small model, confirm the theoretical predictions.\n---\n**Weakness:** \n\n - Reliance on Local Linearization: A core limitation of the analysis is its reliance on a linear approximation of the dynamics around a critical point (local minimum). All stability conclusions are derived in this linearized regime, assuming the optimizer is near a candidate solution and the loss can be approximated quadratically. This means the theory primarily addresses local stability (or instability) of a given minimum rather than the full global training trajectory. Real training often explores highly non-linear regions far from any critical point, and the local results may not extend to the full trajectory. This point is mentioned as limitation by the authors.\n\n - Strong Assumptions and Simplifications: Along with linearization, the analysis involves other simplifying assumptions. For example, theoretical results assume i.i.d. sampled data and focus on one specific model architecture for derivations (two-layer networks with ReLU). The constructed “$(C, r)$-generalizing solutions” framework (Definition 2) is clever for analysis, but it may not cover the full richness of real neural network solutions. Moreover, the study considers only vanilla SGD (with or without isotropic noise) and SAM. It’s unclear if and how the conclusions would change under some common training variations, including momentum and adaptive methods.\n\n - Unclear Direct Practical Implications: While the paper provides an insightful explanation for why SAM and SGD find certain minima, some of the innovations seems to be difficult for applications. For example, the coherence measure, which is a very important principle in the paper, is not something typically monitored during training, and computing per-example Hessian information is prohibitively expensive for large datasets. Thus, applying the coherence metric as a diagnostic or design principle in real training could be challenging.\n\n - Limited Empirical Scope: The experimental validation, while useful, is restricted to a toy setting (a two-layer ReLU network on a synthetic task with $n=100$ samples). This leaves open the question of how well the insights translate to larger-scale deep learning tasks and architectures. For instance, do modern deep networks exhibit the same coherence dynamics, and does SAM similarly reduce the effective feature rank in practice? Extending the experiments to more realistic settings would strengthen confidence that the coherence measure and stability conditions are broadly applicable.", "was_revised": true, "final_justification": "The authors have addressed my concerns with thoughtful discussion and clear explanations. In particular, their clarification of the previously oversimplified theoretical settings enhances the paper’s core contributions and makes its central ideas more interesting and meaningful.\n\nAccordingly, I am raising my score to 4. I also recommend that the authors incorporate key explanations and discussions from the rebuttal into the paper in the next revision.", "rebuttal": "1. Reliance on Local Linearization: The reviewer is concerned that the paper’s theoretical analysis is limited to a linear approximation near local minima, which may not capture the full dynamics of training. They question the broader applicability of the results, given that real training often explores non-linear regions far from any critical point. \n\nWe thank the reviewer for highlighting this limitation, which we acknowledge in the main text. While our analysis is local, this regime remains highly relevant: empirical studies show that loss landscapes are often locally approximately quadratic, even in overparameterized models [1], motivating many theoretical frameworks for optimization and generalization [2, 3]. Since training often proceeds through plateau phases near minima, local dynamics are central to understanding stability. Like gradient flow and neural tangent kernel analyses, our work adopts simplifying assumptions that, while not universally valid, yield valuable insights. Our approach aligns with prior work (e.g., Dexter et al., 2024; Wu et al., 2022) demonstrating the utility of local approximations, and we will clarify these motivations in the revision.\n\n[1] Hao Li., Visualizing the loss landscape of neural nets. NeurIPS,2018\n\n[2] El Mehdi Achour., The loss landscape of deep linear neural networks: a second-order analysis. JMLR 2024.\n\n[3] Kaiyue Wen. How does sharpness-aware minimization minimize sharpness? arXiv 2022.\n\n\n2. Strong Assumptions and Simplifications: The reviewer notes that the analysis relies on strong simplifying assumptions, such as i.i.d. data, two-layer ReLU networks, and basic optimizers (SGD, SAM). They question whether the proposed framework of generalizing solutions captures the complexity of real neural networks, and whether the conclusions extend to other training settings like momentum or adaptive methods.\n\nFirst, the i.i.d. sampling assumption is standard in theoretical deep learning (e.g., generalization bounds, stochastic processes) and reflects how minibatches are typically drawn in practice. Studying non-i.i.d. settings like curriculum or imbalanced sampling is a valuable direction for future work.\n\nSecond, while $({C}, r)$-generalizing solutions are restricted, they reflect key structures observed in deep networks—especially in activation patterns. ReLU networks exhibit rich symmetries (e.g., permutation, rescaling) that yield exponentially many equivalent solutions with identical loss, gradient, and Hessian, making our framework practically relevant despite its constraints. Such simplifications are common to enable tractable analysis.\n\nLastly, we focus on plain SGD and SAM to isolate the roles of noise and sharpness in a clean setting. Extending to optimizers like momentum SGD or Adam, which interact with curvature in subtle ways, is a promising direction we plan to pursue. We appreciate the reviewer’s suggestion and will note this in the revision.\n\n3. Unclear Direct Practical Implications: The reviewer raises concern about the practicality of the proposed coherence measure, noting that it is computationally expensive and not typically used in training. They question how feasible it is to apply this concept in real-world settings as a diagnostic or design tool.\n\nOur work is intended as a first step in highlighting coherence as a potentially valuable conceptual lens for understanding training dynamics and generalization. While the coherence measure is not yet a standard diagnostic tool, this is also true for many theoretical quantities when first introduced. A relevant example is sharpness (e.g., maximum eigenvalue of the Hessian), which was originally difficult to compute at scale, yet it inspired successful optimization strategies such as SAM that approximate the principle indirectly. Similarly, although computing exact gradient coherence or per-sample Hessian quantities is currently expensive, we see this as a motivation for future work on scalable surrogates or proxies. Our contribution is to show that coherence connects to stability in a theoretically grounded way, suggesting that it could inform the design of future optimizers or monitoring tools, even if not computed directly. We will be glad to include this perspective and the challenges of practical deployment in the discussion section of the updated version.\n\n4. Limited Empirical Scope : The reviewer questions the empirical scope of the paper, noting that experiments are limited to a small synthetic setup. Asking whether the theoretical insights, such as coherence dynamics and feature rank reduction by SAM, hold for large-scale models and datasets, and suggest extending the experiments to larger architectures to verify applicability.\n\n| Optimizer   | Rank               | Coherence        |\n|-------------|--------------------|------------------|\n| SGD         | 148.3333 ± 3.215   | 1.0045 ± 0.002    |\n| SAM 0.05    | 157.6667 ± 9.292   | 1.0052 ± 0.006    |\n| SAM 0.1     | 144.3333 ± 7.095   | 1.0771 ± 0.068    |\n| SAM 0.2     | 128.6667 ± 5.508   | 1.0907 ± 0.089    |\n\nWe appreciate the reviewer’s suggestion. To investigate the scalability and practical relevance of our insights, we conducted additional experiments on the CIFAR-10 dataset using a ResNet-18 model (11.7M parameters). To approximate the coherence measure in a tractable way, we used the pairwise dot product of per-sample gradients normalized by the maximum gradient norm:  $\\frac{\\nabla l_i \\nabla_jl}{\\max_k ||\\nabla l_k||}$ For further approximation, We compute this on a fixed subset of 100 samples (10 per class) to construct a $100 \\times 100$ coherence matrix. For the feature rank calculation, we record the features from before the last linear layer for whole training dataset and use PCA to calculate the rank of feature with explain ratio up to 99.9 percent. According to our experiments, we find that the feature rank decrease as expected and the the approximated coherence measure also closely follow the training process despite milder trends due to the approximation.\n\n5. Highly depends on several simplification assumptions: The analysis relies on simplifying assumptions (e.g., local linearization, two-layer ReLU models, specific generalizing solutions). The reviewer asks whether these assumptions are reasonable in modern training settings, and whether the results could extend to deeper architectures like CNNs or other modern structures. They also raise the question of potential new challenges in applying coherence-based stability analysis to such models (e.g., multiple dominant Hessian directions, non-linear layer interactions).?\n\nWe appreciate the reviewer’s question. While our analysis relies on standard simplifying assumptions—local linearization and two-layer ReLU networks—these are common in the literature and have yielded useful insights into deep learning dynamics (e.g., [1][2]). Despite the simplified setting, our framework captures gradient coherence and stability, which we find to remain meaningful even in large-scale models like ResNet-18 (see CIFAR-10 results). Extending this theory to deeper architectures is a promising next step. Though deeper models introduce challenges like multi-modal Hessians and inter-layer interactions, approximations such as blockwise or layer-wise coherence may offer practical paths forward, which we plan to explore.\n\n[1] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. COLT, PMLR, 2020.\n\n[2] Lei Wu. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv, 2017.\n\n6. Measuring and Using Coherence in Practice: The paper proposes data coherence as a central concept. The reviewer asks whether this coherence measure can be feasibly computed or approximated at scale, and whether it could realistically serve as a diagnostic tool in practice.\n\nWe appreciate the reviewer’s question. We agree that coherence is a promising quantity with the potential to provide deeper insight into training dynamics and generalization. While computing the full coherence matrix exactly is impractical for large-scale models, similar to how Hessian-related quantities (e.g., sharpness or trace) are often approximated, we believe coherence can be approximated efficiently using small batches or low-rank projections. As demonstrated in our experiments (e.g., ResNet18 on CIFAR-10), such approximations can already reveal meaningful trends. Developing principled and scalable approximations of coherence, and understanding how it correlates with training outcomes, is a promising direction for future work.\n\n7. Potential direction for design of algorithm: The reviewer asks whether the paper offers any concrete ideas or intuitions for designing new optimizers that align algorithmic behavior with data geometry such as adjusting learning rates or batch selection based on coherence, or adding regularization terms tied to per sample gradient alignment.\n\nWe thank the reviewer for the insightful suggestion. Our analysis aims to inspire optimizers that leverage gradient coherence to align with data geometry. One concrete idea is to adapt the learning rate based on coherence between mini-batches—reducing it when gradients are aligned, and increasing it when they diverge. Other possibilities include regularizers that promote gradient alignment or batch selection strategies favoring coherence. While we have not explored these experimentally, we view them as promising directions for future work."}, {"review_id": "gsCkd0x8Md", "reviewer": "Reviewer_fbHT", "summary": "This paper studies the dynamical stability of a randomly perturbed version of SGD and SAM, owing to both algorithms' generalization capabilities. Framed in the setup of Dexter et al. (2024)'s coherence measure, the paper shows that SAM enforces a tighter coherence matrix, and connects this to work showing its better generalization capabilities compared to SGD. Experiments with a synthetic dataset are shown.", "questions": "* Could you better contextualize the novelty of this paper and distinguish it from Wu & Su (2023)? I'm not convinced by the appendix's statement that the MSE loss being used is a limitation of that work that is addressed here.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n* This paper addresses an important topic (flat minima/generalization), and adds to a growing body of work that studies it through the lens of stability.\n* The paper is generally well-written and easy to follow.\n* Most of the relevant work in the area has been thoroughly discussed in the appendix.\n\n**Weaknesses:**\n\n* The novelty of this paper with respect to other work on dynamical stability (such as Wu & Su (2023)) is unclear. In Appendix B, the authors attempt to distinguish their work as, \"... but compared to prior works [Wu et al., 2018, 2022, Wu and Su, 2023], instead of assuming mean square loss, we have more general abstraction to include different kind of loss function.\" This is not true: for example, Wu & Su (2023) use a generic loss function and Hessian throughout their analysis as well (similar to this paper), and only use the MSE as an example in Section 2. The rest of their work studies a general ERM problem, with a gradient $g$ and a Hessian $H$ (though their paper uses the associate empirical Fisher matrix $G$ instead of $H$).\n* This paper would benefit from a brief explanation of Dexter et al. (2024), since that work is the basis for some of the theory and the experimental setup. As such, it is useful to readers to understand why the specific experimental setup is chosen.\n* After Theorem 3.1, the paper states, \"Further, in the stable regime, the iterates do not converge exactly to the minimum, but instead remain in a bounded region around it (part 3)\". Is this true for all minima, or only when $w^* = 0$? To me, part 3 seems to instead suggest that while the iterates remain in a bounded region, that region may not be symmetric around the minimum; is this accurate?\n* In Definition 2, it would be beneficial to use a consistent notation, i.e., either $W_{1, j}$ or $W_1[j]$, as used for $W_2$.\n* In Appendix C.1, \"Take the trace will be ...\" --> \"Then the trace is ...\"\n* In Appendix C.1, $e_1$ is not defined.\n\nWu, L., & Su, W. J. (2023). The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descent. International Conference on Machine Learning. http://arxiv.org/abs/2305.17490", "was_revised": true, "final_justification": "* My primary concern with the paper was regarding its novelty wrt prior work such as Wu & Su (2023). In their rebuttal, the authors clearly point out where that paper makes specific assumptions that this work does not--this clearly addresses my concern and demonstrates the novelty of this paper.  \n* The authors also address my other concerns clearly. The authors should add the discussion from their rebuttal to the camera-ready version (e.g., the distinction from prior work, which can be added to the appendix; notation issues).\n\nAlthough I am deciding between a 4 and a 5, I do not have any further concerns with this paper, and therefore I am updating my score to 5.", "rebuttal": "1. The novelty of this paper with respect to other work on dynamical stability (such as Wu \\& Su (2023)) is unclear. In Appendix B, the authors attempt to distinguish their work as, \"... but compared to prior works [Wu et al., 2018, 2022, Wu \\& Su, 2023], instead of assuming mean square loss, we have more general abstraction to include different kind of loss function.\" This is not true: for example, Wu \\& Su (2023) use a generic loss function and Hessian throughout their analysis as well (similar to this paper), and only use the MSE as an example in Section 2. The rest of their work studies a general ERM problem, with a gradient and a Hessian (though their paper uses the associate empirical Fisher matrix). \n\nWe thank the reviewer for the helpful clarification. Upon revisiting Wu \\& Su (2023), we agree that their broader framework is presented in terms of general empirical risk minimization, and that their analysis of generalization error and sharpness indeed applies to a general loss and Hessian (or Fisher). Our statement in Appendix B was too strong and will be revised accordingly. That said, we would like to clarify a subtle but important distinction: while their overall setup is general, the key linear stability analysis in Wu \\& Su (2023) especially the parts relying on spectral properties of the Jacobian or stability matrix is carried out under the mean squared error (MSE) loss. The use of MSE enables concrete expressions for the Hessian and simplifications that arise from its symmetry and quadratic form. For instance, Proposition 3.2 builds on Equation (3), which assumes MSE, leading to the specific Hessian form in Equation (2). Proposition 3.4 similarly uses this structure, and its derivation in Equation (23), as noted in Appendix B.2, depends on Lemma 3.3 — both of which are MSE-specific. While Wu \\& Su later discuss generalization using broader loss functions, their linear stability bounds are derived concretely under the MSE setting. We hope this clarifies the intended distinction, and we appreciate the opportunity to correct and clarify our prior statement.\n\n2. This paper would benefit from a brief explanation of Dexter et al. (2024), since that work is the basis for some of the theory and the experimental setup. As such, it is useful to readers to understand why the specific experimental setup is chosen.\n\nWe appreciate the reviewer for the question. Our work generalizes the stability framework of Dexter et al 2024 on SGD analysis to include Sharpness-Aware Minimization (SAM) and random perturbation SGD, revealing that SAM imposes a stricter and more geometry-sensitive stability condition than SGD. It proves that SAM preferentially selects solutions with higher inter-sample curvature alignment, even when sharpness is held constant. Unlike Dexter et al, which focuses solely on SGD, this paper formalizes the link between stability and simplicity bias across optimizers and instantiates the theory in two-layer ReLU networks, distinguishing generalizing from memorizing solutions by their coherence structure.\n\n3. After Theorem 3.1, the paper states, \"Further, in the stable regime, the iterates do not converge exactly to the minimum, but instead remain in a bounded region around it (part 3)\". Is this true for all minima, or only when w*=0? To me, part 3 seems to instead suggest that while the iterates remain in a bounded region, that region may not be symmetric around the minimum; is this accurate?\n\nWe thank the reviewer for the thoughtful question. We clarify that the statement following Theorem 3.1 holds more generally and is not restricted to the case where w*=0. Since we are interested in dyanamics around optima actual value of $w^*$ does not matter. The key point is that due to the presence of additive noise (independent of the curvature or symmetry of the loss landscape) iterates do not converge exactly to the minimizer, but instead fluctuate within a bounded region. If we look at equation (3), we can find that even under w*=0, there will still be non-zero update of the weight. This is not the result of the loss landscape but the noise that is added into the algorithm artificially. Here, we provide several random perturbation base algorithms (see ref [1][2]) that gradually decrease the noise during the training to achieve better convergence behavior as support for our statement.\n\n[1] Bisla., A. Low-pass filtering sgd for recovering flat optima in the deep learning optimization landscape. AISTATS, 2022.\n\n[2] Yong Liu. Random sharpness-aware minimization. NeurIPS, 2022.\n \n4. In Definition 2, it would be beneficial to use a consistent notation.\n \nWe thank the reviewer for addressing the issue. We will modify it accordingly in the updated version.\n\n5. In Appendix C.1, $e_1$ is not defined.\n\nWe appreciate reviewer for pointing that out. $e_1$ is the Canonical orthonormal basis with 1 as its first element and zero otherwise. We will incorporate this definition in the updated version.\n\n6. Could you better contextualize the novelty of this paper and distinguish it from Wu Su (2023)? I'm not convinced by the appendix's statement that the MSE loss being used is a limitation of that work that is addressed here.\n\nWe see our novelty in two different parts compared to prior work:\n\nFirst, Coherence base analysis: We use the Hessian coherence matrix as a central object to capture alignment between per-sample gradients. This sheds light on how SGD and SAM interact differently with different  data distributions — particularly in terms of stability and generalization — an aspect that is not a focus of Wu \\& Su (2023). In contrast to their emphasis on the noise structure interaction with Fisher information matrix, our analysis reveals how data geometry influences the stability of solutions through coherence. This directly provides a theoretical bases for empirical observations on simplicity bias made by other papers. (see [1] [2])\n\nSecond, bridging linear stability to neural network structure via activation patterns: A key novelty of our work is connecting linear stability theory to the activation patterns in ReLU networks. We show that generalizing solutions tend to induce more coherent gradients, which in turn correspond to simpler (i.e. more sparse, and more structured activation patterns. This provides a concrete way to interpret algorithmic bias (e.g., from SAM) in terms of neural architecture behavior — a perspective not developed in Wu \\& Su or related stability works. We hope these clarifications help highlight how our work complements and extends the existing body of literature on optimization dynamics.\n\n[1] K. Gatmiry, Z. Li, S. J. Reddi, and S. Jegelka, “Simplicity bias via global convergence of sharpness minimization,” arXiv, 2024\n\n[2] Springer, J. M., Nagarajan, V., and Raghunathan, A. (2024). Sharpness-aware minimization\nenhances feature quality via balanced learning. ICLR."}, {"review_id": "6GnzCDHdK3", "reviewer": "Reviewer_tCPY", "summary": "This work analyzes two widely used algorithms: SGD and SAM, where the focus is on understanding two properties of the trained network parameters (local minima): the sharpness/flatness of the minima and its relation to generalization, and the tendency of SGD to find simpler minima especially in overparametrized regimes.  \n\nThe main results of this paper provide evidence that flatness and simplicity (sometimes) come together, and that insisting on flatness (like SAM does) coms with an inherent bias for simplicity.\n\nTo this end the authors utilize a linear stability framework and the data coherence measure derived by Dexter et al. Their first result (Theorem 3.1) concerns SGD with random perturbation shows that adding random noise to SGD doers not alter which minima are stable, and furthermore that once a minimum is unstable, the noise causes the iterates to diverge at a faster rate. \n\nTheir second result (that I found more interesting) shows that under quadratic loss, SAM dynamics are biased towards coherence measure that captures how sample gradients align, but SAM also penalizes directions with large curvature. In addition, they show a matching lower bound on the SAM divergence. \n\nFinally, the authors consider realistic model architectures and quantify the coherence structure of different solutions, showing how this governs their stability under SGD and SAM.", "questions": "I found Definition 2 of $(C,r)$-generalizing solution a bit ill-defined and unnatural. What is a (C,r) generalizing solution? You define $W_1$ and $W_2$, but do not state what a $(C,r)$ generalizing solution is.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: The considerations of this paper shed light on interesting properties of SGD and SAM, and address important phenomenon. I was able to verify most of the theoretical results except Theorem 3.5 and they appear correct. I believe this paper will be of broad interest to the NeurIPS community and vote acceptance.\n\nWeaknesses: First, I believe related work should appear in the main body of the paper, not in an appendix. \nNext, all of the analysis is based on behavior near local minima, and hence the linear approximation of the loss landscape is easier to handle. Finally, the paper only studies two-layer ReLU networks. In terms of novelty, the work appears to be bordering on being incremental, but I feel there is sufficient novelty in the SAM and the 2-layer results to warrant acceptance.", "was_revised": true, "final_justification": "I think this paper should be presented at NeurIPS, as it tackles important issues.", "rebuttal": "1. Weaknesses: First, I believe related work should appear in the main body of the paper, not in an appendix. Next, all of the analysis is based on behavior near local minima, and hence the linear approximation of the loss landscape is easier to handle. Finally, the paper only studies two-layer ReLU networks. In terms of novelty, the work appears to be bordering on being incremental, but I feel there is sufficient novelty in the SAM and the 2-layer results to warrant acceptance.\n\nWe thank the reviewer for the thoughtful comments and for recognizing the novelty in our results. We have tried to provide all contextualized related works and cited them inline in the introduction itself. As such, we did not feel a separate related works section (which is mostly 'additiona related works') added a lot of value over what is already in the intro. If the reviewer strongly feels otherwise, we are happy to move it to the main paper. We agree that it plays an important role in framing the contributions of the paper. \n\nRegarding novelty, our coherence-based analysis offers a new perspective on how property of data interacts with optimization. Unlike prior works that focus solely on sharpness, we show that alignment in the loss landscape—driven by data coherence—can act as a stabilizing factor, revealing a previously underexplored mechanism for generalization. This insight leads to a theoretical breakthrough by integrating data-dependent property into the analysis of optimization and generalization. Furthermore, our framework bridges loss landscape geometry, distribution of data, and simplicity bias in neural networks. We view this as a key advancement, as simplicity bias is a defining feature of modern deep networks and often touted as an important aspect of explaining generalization (see ref[1][2]). Our results thus help connect optimization theory with broader aspects of deep learning, filling a critical gap in existing understanding.\n\nOn the focus on local analysis, we fully acknowledge this as a limitation. Any approximation of neural networks for theoretical tractability, including neural tangent kernels,  infinite widths of intermediate layers, gradient flows, bayesian perspective on sgd, make some assumptions that may not always hold. However, we believe the characterization of behavior around local minima is still highly relevant in modern deep learning and is grounded in empirical observations. Training dynamics often enter a hovering regime where the loss plateaus and the optimizer oscillates near a minimum for a substantial portion of training. This regime is known to influence generalization and stability properties. Our analysis is intended as a first step to provide a rigorous foundation for understanding this important phase of training. Lastly, while it is true that our theoretical analysis is grounded in two-layer ReLU networks, we emphasize that this model class has been widely used to uncover foundational insights in deep learning theory. (see ref [3][4]). The simplifications being made for RELU constructions are highly relevant to modern data and neural network interactions. Moreover, we extend our experimental validation to deeper architectures (e.g., ResNet-18 on CIFAR-10) and show the correspondence to coherence and feature-rank trends unearthed through our theoretical analysis, suggesting that the insights transfer beyond the two-layer setting. We agree that generalizing the theory to deeper or more complex networks is an exciting and important future direction, but we hope the reviewer sees the importance of our work as a stepping stone in that direction. We appreciate the reviewer’s overall positive assessment and constructive feedback.\n\n[1] K. Gatmiry, Z. Li, S. J. Reddi, and S. Jegelka, “Simplicity bias via global convergence of sharpness minimization,” arXiv, 2024\n\n[2] Springer, J. M., Nagarajan, V., and Raghunathan, A. (2024). Sharpness-aware minimization\nenhances feature quality via balanced learning. ICLR.\n\n[3] El Mehdi Achour., The loss landscape of deep linear neural networks: a second-order analysis. JMLR 2024.\n\n[4] Kaiyue Wen. How does sharpness-aware minimization minimize sharpness? arXiv 2022.\n\n\n\n2. I found Definition 2 of -generalizing solution a bit ill-defined and unnatural. What is a (C,r) generalizing solution? You define and , but do not state what a generalizing solution is.\n\nWe thank the reviewer for pointing this out and apologize for the lack of clarity. In our work, a generalizing solution refers to a solution (i.e., a set of network weights) that achieves zero test classification error under the data distribution we mentioned in the main context (section 3.3). (i.e., $y = f_w(x) \\;\\;\\forall x,y \\sim \\mathcal{D}$) To be more specific, we provide one example in the appendix C.1. To provide intuitive understanding, the C in (C,r) solution controls how many neurons are activated in the first layer, and r control the the flatness in the solution as mentioned in the Definition 2 and the paragraph underneath. We will revise the main text to more clearly introduce what we mean by a generalizing solution before presenting Definition 2. If the reviewer has a specific concern about the formulation, we would be happy to address it in greater detail.\n\nNote that the generalizing solutions encompass exponentially many parameter configurations due to inherent symmetries in neural networks such as hidden unit permutations and layer-wise scaling invariance. These transformations preserve important properties such as loss, gradient, and Hessian, resulting in a broad equivalence class of solutions with indistinguishable local geometry. Our work provides a principled characterization of the optimization dynamics within this rich class. Moreover, it demonstrates the compatibility of our framework with broader aspects of deep learning, including simplicity bias and representation learning."}, {"review_id": "1LRESxVl8N", "reviewer": "Reviewer_e2Jp", "summary": "This paper explores the dynamics of specific optimization algorithms (SGD, random perturbations of SGD, and SAM) and their perceived bias towards flatter or simpler solutions, especially in overparameterized regimes. The authors suggest a linear stability analysis framework as a tool to understand and quantify this behavior. Their approach relies on data and gradient similarity and attempts to explain why certain solutions are preferred for these optimization algos. The experiments are limited to two-layer ReLU networks.", "questions": "I don't have any major (decision altering) questions.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "This is a well-written paper and addresses an interesting property that has been evidenced in neural network training, that \n\nThis is interesting work but I'm afraid I'm not an expert enough in this area to properly validate much of the analysis. The analysis is limited to three optimization algorithms (SGD, SGD with noise, and SAM) and the experiments focus only on two-layer ReLU networks. From my background, the development appears correct though and the analysis is useful. These factors limit my ability to classify this as a \"5:Accept: ..high impact on at least one sub-area of AI or moderate-to-high impact on more than one area of AI\" so I feel a rating of 4 is appropriate.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the response. Here we provide brief summary for our paper to help understanding it in more depth and we are glad to answer any question that the reviewer may have:\nThis paper is for the first time studies what properties of data (and not just global properties of the function) ensure stochastic optimization algorithms like Stochastic Gradient Descent (SGD) and Sharpness-Aware Minimization (SAM) settle in or escape from local minima in complex NN training, and why some local minima they find generalize better than others. \n\nAt the heart of our work is the idea of data coherence — a new way to measure how consistent the gradients (training signals) are across different data points. We show that when the gradients point in more similar directions (i.e., high coherence), optimization tends to be more stable, and the resulting models tend to generalize better. SAM is better at finding such minima, and SGD will `settle' in some incoherent minima that SAM will escape from. We analyze this behavior mathematically in two layer ReLU networks. Using this framework, we prove that stability during training is influenced by both the data and the algorithm, and we show that SAM encourages the algorithm to prefer more coherent, stable solutions than vanilla SGD. \n\nFor the novelty of our theory, we summarize as follows:\n\n1. Role of coherence in the optimization: We highlight the role of data coherence in shaping optimization dynamics, showing for the first time the importance of distribution of data itself (beyond its global properties such as Lipschitz-ness) and hot it actively interacts with the geometry of the loss landscape. In particular, coherent data distributions lead to more stable optimization trajectories, while datasets with many outliers (i.e., low coherence) can exhibit instability. This perspective helps bridge the gap between optimization theory and data.\n\n2. New analysis for SAM: Our framework provides a novel analysis of Sharpness-Aware Minimization (SAM), showing that SAM implicitly penalizes incoherent solutions. This reveals that SAM not only promotes flat minima but also enforces stronger alignment between the solution and the underlying data, offering new insight into its generalization behavior.\n\n3. We show that coherent solutions often correspond to simpler activation patterns, providing a functional interpretation of coherence in terms of network behavior. This connection offers a new lens to understand generalization, establishing a link amongst solution simplicity, data alignment, and internal network representations.\n\nTo ground our theory in practice, we conduct experiments that:\n\n1. Show coherence improves generalization and guarantee the stability of the solution. The new connection between data and optimization process that reveal the role of data in optimization. \n\n2. Show that SAM leads to simpler (lower-rank) feature representations, indicating that coherence is reflected in the activation patterns of neural networks. This insight leverages the layered structure of deep networks and bridges theoretical analysis with the internal behavior of practical architectures.\n\n3. Extend beyond toy settings to larger models and datasets like CIFAR-10 (see response for Response for Reivewer k5uF). Overall, our work contributes a new theoretical tool based on coherence and local stability to explain and potentially design better training algorithms that align with the structure of the data."}]

Author rebuttal:

Meta-review: This paper presents a unified stability analysis of SGD and SAM through the lens of data coherence, offering a novel perspective on the emergence of simplicity bias in optimization. The reviewers found the theoretical contributions to be interesting and technically solid, particularly the coherence-based framework that connects data geometry, stability of solutions, and generalization, as well as the new analysis of SAM’s role in preferring coherent minima. The main concerns centered on the simplifying assumptions (local linearization, two-layer ReLU networks, and basic optimizers) and the limited scope of empirical validation, which initially raised doubts about the generality and practical relevance of the results. However, the authors’ rebuttal was detailed and convincing: they clarified the novelty compared to prior work (notably Wu & Su, 2023), justified the theoretical assumptions, and supplemented the work with additional experiments on CIFAR-10/ResNet-18 showing that the coherence-based insights extend beyond toy settings. Reviewers engaged with the authors’ clarifications, and two reviewers raised their scores post-rebuttal, while the others maintained positive evaluations. Overall, the consensus is that despite its limitations, the work provides a principled and meaningful theoretical framework that enriches our understanding of optimizer bias, coherence, and generalization, making it a valuable contribution for the NeurIPS community. I recommend acceptance as a poster.
Decision: Accept (poster)