Understanding Sharpness-Aware Minimization
Authors: Maksym Andriushchenko
Nicolas Flammarion
Venue: ICLR 2022 Submitted (2022)
Keywords: Sharpness-aware minimization
implicit bias
noisy labels
adversarial training

Abstract: Sharpness-Aware Minimization (SAM) is a recent training method that relies on worst-case weight perturbations. SAM significantly improves generalization in various settings, however, existing justifications for its success do not seem conclusive. First, we analyze the implicit bias of SAM over diagonal linear networks, and prove that it always chooses a solution that enjoys better generalisation properties than standard gradient descent. We also provide a convergence proof of SAM for non-convex objectives when used with stochastic gradients and empirically discuss the convergence and generalization behavior of SAM for deep networks. Next, we discuss why SAM can be helpful in the noisy label setting where we first show that it can help to improve generalization even for linear classifiers. Then we discuss a gradient reweighting interpretation of SAM and show a further beneficial effect of combining SAM with a robust loss. Finally, we draw parallels between overfitting observed in learning with noisy labels and in adversarial training where SAM also improves generalization. This connection suggests that, more generally, techniques from the noisy label literature can be useful to improve robust generalization.

Under review as a conference paper at ICLR 2022
UNDERSTANDING SHARPNESS- MINIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Sharpness-Aware Minimization (SAM) is a recent training method that relies on worst-case weight perturbations. SAM significantly improves generalization in various settings, however, existing justifications for its success do not seem conclu- sive. First, we analyze the implicit bias of SAM over diagonal linear networks, and prove that it always chooses a solution that enjoys better generalisation properties than standard gradient descent. We also provide convergence proof of SAM for non-convex objectives when used with stochastic gradients and empirically discuss the convergence and generalization behavior of SAM for deep networks. Next, we discuss why SAM can be helpful in the noisy label setting where we first show that it can help improve generalization even for linear classifiers. Then we discuss a gradient reweighting interpretation of SAM and show a further beneficial effect of combining SAM with robust loss. Finally, we draw parallels between overfitting observed in learning with noisy labels and in adversarial training where SAM also improves generalization. This connection suggests that, more generally, techniques from the noisy label literature can be useful to improve robust generalization.
INTRODUCTION
Understanding generalization of overparametrized deep neural networks is central topic of the current machine learning research. Their training objective has many global optima where the training data are perfectly fitted (Zhang et al., 2016), but different global optima lead dramatically different generalization performance (Liu et al., 2019). However, it has been observed that stochastic gradient descent (SGD) tends to converge to well-genete well-generalizing solutions, even without any explicit regularization methods (Zhang et al., 2016) 6). This suggests that the leading role is played by the implicit bias of the optimization algorithms used (Neyshabur et al., 2014): when the training objective is minimized using a particular algorithm and initialization method, it converges to specific solution with favorable generalization properties. However, even though SGD has a very beneficial implicit bias, significant overfitting can still occur, particularly in the presence of label noise (Nakkiran et al., 2019) and adversarial perturbations (Rice et al., 2020).
Recently it has been observed that the sharpness of the training loss, i.e., how quickly it changes in some neighborhood around the parameters of the model, correlates well with the generalization error (Keskar al., 2016; Jiang et al., 2019), and generalization bounds related the sharpness have been derived (Dziugaite & Roy, 2018). The idea of minimizing the sharpness to improve generalization has motivated recent works of Foret al. (2021) and Wu al. (2020) which propose to use worst-case perturbations of the weights on every iteration of training in order to improve generalization. We refer to this method as Sharpness-Awart Minimization (SAM) and focus mainly on the version proposed in Foret et al. (2021) that performs only one step of gradient ascent to approximately solve the weight perturbation problem before updating the weights.
Despite the fact that SAM significantly improves generalization in various settings, the existing justifications based on the generalization bounds provided by Foret al. (2021) and Wu et al. (2020) do not seem conclusive. The main reason is that their generalization bounds do not distinguish the worst-case robustness to worst-case weight perturbation from average-cass robustness to Gaussian noise. However the latter does not sufficiently improve generalization both Foret et al. (2021) and Wu et al. (2020) report. Moreover, their analysis does not distinguish whether the weight perturbation is applied based on some or all training examples which, as will discuss, has an important impact on generalization.
We aim at further investigating the reasons for SAM's success and make the following contributions:

---

Under review as a conference paper at ICLR 2022
We first discuss that the SAM formulation can lead to two different objectives. We show that the gradient flows on these objectives over diagonal linear networks are implicitly biased towards solutions which enjoy better generalization properties compared to the standard gradient flow.
We provide convergence results for the SAM algorithm used with stochastic gradients for non-convex objectives and discuss the convergence and generalization behavior of SAM for deep networks.
We discuss why SAM can prevent overfitting in the noisy label setting by interpreting SAM as a gradient reweighting scheme and showing the further benefits of combining it with a robust loss.
Finally, we draw parallels between overfitting in learning with noisy labels and in adversarial training where SAM also improves generalization. This connection suggests that techniques from the noisy label literature can be more generally useful to improve robust generalization.
RELATED WORK
Here we discuss relevant works on robustness in the weight space and cover the main references on overfitting in the noisy label setting and in adversarial training, two settings where weight-space robustness also improves generalization.
Weight-space robustness. Works on weight-space robustness of neural networks date back at least to 1990s (Murray & Edwards, 1993; Hochreiter & Schmidhuber, 1995). Random perturbations of the weights are used extensively in deep learning (Jim et al., 1996; Graves et al., 2013), and most prominently approaches such as dropout (Srivastava et al., 2014). Many practitioners have observed that using SGD with larger batches for training leads to worse generalization (LeCun et al., 2012), and Keskar et al. (2016) have shown that this degradation of performance is correlated with the sharpness of the found parameters. This observation has motivated many further works which focus on closing the generalization gap between small-batch and large-batch SGD (Wen et al., 2018; Haruki et al., 2019; Lin et al., 2020). More recently, Jiang et al. (2019) have shown a strong correlation between the sharpness and the generalization error on a large set of models under variety of different settings hyperparameters, beyond the batch size. This has motivated the idea of minimizing the sharpness during training to improve standard generalization, leading to Sharpness-Auw Aware Minimization (SAM) (Foret et al.. 2021). SAM modifies SGD such that on every iteration of training, the gradient is taken not at the current iterate but rather at a worst-case point in its vicinity. Zheng et al. (2021) concurrently propose a very similar weight perturbation method which also successfully improves standard generalization on multiple deep learning benchmarks. Wu et al. (2020) have also proposed a similar algorithm with the same motivation, although Wu et al. (2020) focuses on improving robust generalization of adversarial training.
Overfitting in learning with noisy labels. Arpit et al. (2017) have observed that deep networks noticeably overfit in the presence of mislabeled samples but early stopping can mitigate the problem. There are multiple other approaches that can mitigate this overfitting behavior: removing (Song et al., 2020) downweighting noisy points (Jiang et al., 2018; Huang et al., 2020), using robust losses (Ghosh et al., 2017; Zhang & Sabuncu, 2018; Menon et al., 2019). Most of these approaches explicitly or implicitly leverage the early-learning phenomenon (Liu et al., 2020) where the network tends to fit first correctly labeled points and noisy points later in training. In the context of adversarial robustness, Sanyal al. (2020) have discussed that fitting label noise can aggravate adversarial vulnerability, although removing label noise is not sufficient to achieve adversarial robustness.
Overfitting in adversarial training. Adversarial training in deep learning has been formulated as a robust optimization problem by Madry et al. (2018) where the worst-case perturbations are typically found via projected gradient descent. Rice et al. (2020) have described the robust overfitting phenomenon in adversarial training suggesting that early stopping is highly beneficial and provides a competitive baseline. However, they do not provide explanations about the reasons behind the overfitting phenomenon. The ofate-of-the-art approaches propose different ways to improve robust generalization and mitigate robust overfitting such as using additional training data (Carmon et al., 2019), weight averaging (Gowal et al., 2020; Chen et al., 2021), advanced data augmentations (Rebuffi et al., 2021) 1). Additionally, Wu et al. (2020) have shown that combining adversarial training with method similar sharpness-aware minimization also improves robust generalization.
2

---

Under review as a conference paper at ICLR 2022
3 IMPLICIT BIAS AND CONVERGENCE OF SAM
In this section, we discuss different objectives related to Sharpness- Aware Minimization (SAM) and their generalization properties, then derive convergence results for the stochastic SAM algorithm, and further discuss the convergence and generalization of SAM for deep networks.
3.1 IMPLICIT BIAS OF SAM
SAM objectives. Let (I,, Vi Wi] be the training data points and (w)) be the loss of a classifier parametrized by weights w E RIw] and evaluated at point (Ii, Wi). Foret et al. (2021) theoretically base their approach on the following objective which denote MaxSum SAM:
MaxSum SAM:
max WER | Sp
min
Σ
liww + +5)
They justify this objective via PAC-Bayesian generalization bound, although they show empir- ically (see Fig. 3 therein) that the following objective, denoted as SumMax SAM, leads to better generalization:
min Σ max l(ww + 5). #1 M
SumMax SAM:
(2)
The update rule of SAM for these objectives amounts then to a variation of gradient descent with step size it where the gradients are taken at intermediate points 1/+1/2" i.e., Wt+1
Wt- - 26 Ei= V4((w(+1/2). The two objectives, however, differ in how the points w 14+1/2 are computed since they approximately maximize different losses with inner step sizes Pr:
MaxSum: 2/+1/2 = we +
Pt (Wg(ws)
vs. SumMax: 2//1/2 = wi + PV (3)
TI 1=1
We next show formally that SumMax SAM has better implicit bias than ERM and MaxSum SAM.
Implicit bias of SumMax and MaxSum SAM. The implicit bias of gradient methods well understood for linear models where all gradient based algorithms enjoy the same implicit bias. For diagonal linear neural networks, first-order algorithms have a richer implicit bias. We consider here a sparse regression problem and predictor parametrized as fu.e u@u V@v. Before understanding how SAM induces a preferable bias, we first recall the seminal result Woodworth et al. (2020): assuming global convergence, the solution selected by the gradient flow initialised at E Rdd and denoted 3% solves the constrained optimisation problem:
8 SER4 s.L. XB= (3).
arg min
(4)
The potential ń. whose precise expression is given Eq. (12) in App. interpolates nicely between the & and the & norms according to the initialization scale a: Small initialisations lead to low fityye solutions which are known induce good generalisation properties. Large initialisations lead low f2-type solutions. Our main result is that both MaxSum and SumMax dynamics bias the flow towards solutions which still minimise the potential Φa. However does so with effective parameter Ou and OsSumMax which are strictly smaller than for suitable inner step size Thus the chosen solution has better sparsity- innuuiing properties than the solution of the gradient flow.
Proposition 1 (Informal), Assuming global convergence, the solutions selected by the MaxSum and the SumMax algorithms defined Eq. (3), taken in the infinitesimally small-yy limit and initialised at a. solve the optimisation problem (4) with effective parameters O'SmmMax and OSuMMax which satisfy:
OSamMaa ae -p +0(p²) and (MManSun - PAMussmtO
where A Sumbaa and AMaiSum are two entrywise positive vectors for which typically:
A SumMarxl2 R d 1 L(w(s))ds and || || ~ d 1 I(w(s))ds.
3

---

Under review as a conference paper at ICLR 2022
The results are formally stated in Proposition 4 and 5 in App. A. The SumMax implementations has better bias properties since its effective scale of a is considerably smaller than the one of MaxSum. is worth noting that the vectors SumMax and Max are linked with the integral of the loss function along the flow. Thereby, the speed of convergence of the training loss impacts the magnitude of the biasing effect: the slower the convergence, the better the bias, similarly what observed for SGD) by Pesme et al. (2021).
Empirical evidence for the implicit bias. We compare the per- formance of different methods (ERM, MaxSum and SumMax SAM) on the training and test losses in Fig. As predicted, the methods enjoy various generalization abilities: ERM and MaxSum SAM enjoy the same performance whereas SumMax benefits from a better implicit bias. We also note that the training loss of all the variants is converging to zero but as alluded before the convergence of SumMax SAM is slower. We show similar experiments in App. A with stochastic variants of the algorithms. As expected, their performances are better than their deterministic counterparts (Keskar et al., 2016; Pesme et al., 2021).
10p
Test Loss
10
ERM
10aa
MaxSum SAM
SumMax SAM
10-4
10a
16
10
20"
Number of iterations
100
The results the implicit bias presented above require that the algorithm converges to zero training error. Therefore we analyze next the convergence of the SAM algorithm for general non- convex functions in the practically relevant stochastic case. Note that we cannot expect rates as fast as the one observed for the previous simple model. They were due to its special structure for which fast convergence rates have been proven (Yun et al., 2021).
Teain Loss
10
ERM
16
MaxSum SAM
SSmMaax SAM
16a
10a
20
Number of iterations
Figure Implicit bias of Sum- Max SAM for diagonal network
3.2 CONVERGENCE OF SAM ALGORITIM
To make the SAM algorithm practical, Foret et al. (2021) propose on a sparse regression problem. to combine SAM with stochastic gradients. By denoting the batch indices at time by It, this leads to the following update rule:
W++1 = We
Vt'
Eva(we
+
Pt Σ Vlr(w))).
(5)
Ie
[Te]
KEL.
JEL
Importantly, the same batch J, is used for the inner and outer gradient steps which allows to interpolate
between the MaxSum (for [T,] = n) and SumMax (for [T|| = 1) update rules defined Eq. (3). However, using batch size [4g]
is inefficient in practice since it does not fully utilize the
computational accelerators such as GPUs so for most experiments, Foret et al. (2021) use a higher |4| to balance the generalization improvement with the computational efficiency.
In the following, we analyze the convergence of the update rule from Eq. (5). We make the following assumptions on the training loss L(w) = 1,4 Σ (w):
Rd. (A2) (Individual 3-smoothness). It exists 8 > 0 s.t. [V[(()) ve(u))l S B - w|l for all W. Rd and i E [1,
(A1) (Bounded variance). It exists a 2 0 s.t. E[I (l(w) VL(W))| < o0,i~
(A3) (Polyak-Lojaasewicc)) It exists μ > 0 s. [( p(L(w) - for all w. E Rd.
We have the following convergence result for the stochastic SAM algorithm (see proof in App B.2). Proposition Assume (A1-2) for the iterates (5). For any T 2 and for step-sizes "tt VTg and
Pt T1743, we have:
4 (L(wo) L.) + byT
802
[V:(w:)]
BVT
In addition, under (A3), with step-sizes =mink Jx(t+1p7 23 and Pt Vrc/B:
814-
( - L.) + 1.2TT
22,00
B[I(WT)] - I., -
1T2
4

---

Under review as a conference paper at ICLR 2022
We make several remarks regarding this theorem:
We recover the rates of SGD with the usual condition on the step size 7 (Ghadimi & Lan, 2013; Karimi et al., 2016). The ascent step-size pt has to be O(v7i) to ensure convergence. Therefore it tolerates a slower decrease than T/- This finding is aligned with the fact that the ascent step-size of SAM should not be decreased as drastically as the descent step-size when training neural networks.
The proof relies on the bound (VL(w, + [w:)), VL(w))) shows that SAM-step is well aligned with the gradient step (seem Lemma 16 in App B.2).
V(w)))) 2 (1 - n|))| V (( )) )[² which
We can obtain the same convergence result for the different variants of SAM described in the previous section. We also provide in App B.1 tighter convergence rates for the full-batch case.
SAM with normalized gradient. When SAM algorithm was first introduced, the gradient was normalized in the inner step, in order to have an ascent-step of size exactly p. This normalization is not needed to get similar performance in applications and is not favorable for optimization purposes. Indeed when used with constant step-size normalized SAM is oscillating, and the averaged iterate converges to a different point which is not necessary flatter than the solution. When decreasing step-sizes are used, then the behaviors are comparable to the ones in the unnormalized case. In App. B.3, we show experiments that suggest that SAM with and without normalization steps achieves similar improvements in terms of generalization. However, for all other experiments in the paper, rely on the normalized SAM as introduced in Foret et al. (2021) which is the main focus of our study.
3.3 CONVERGENCE AND GENERALIZATION OF SAM FOR DEEP NETWORKS
Here relate the theoretical results from the previous section with the behavior of SAM for deep networks on a standard image classification dataset.
ERM and SAM both converge but generalize differently. We compare the behavior of ERM and SAM by training a ResNet- 18 CIFAR-10 for 1000 epochs using mini-batch SGD with momentum and piece-wise constant learning rates (see App. C for experimental details) and plot the results over epochs in Fig. 2. We observe that not only the ERM model but also the model trained with SAM fits all the training points and converges to nearly zero training loss: 0.0012 for ERM vs 0.0009 for SAM. However, the SAM model has significantly better generalization performance: 3.76% vs 5.03% test error. Moreover, we observe no noticeable overfitting standard CIFAR-10: the best and last model differ at most by 0.1% test error for both methods.
20%
enoo anas erce ERM ence SAM
10%
10%
5%
1000
Eboch
5.0%
Scit lost 100 spocts
3.5%
5.0%
When is implicit bias of SAM beneficial during train- ing? To better understand the implicit bias of SAM over training iterations, we perform the following experiment: we train with ERM for 900 epochs and then use SAM for the remaining 100 epochs (ERM + SAM), and vice versa (SAM - ERM). We can see from Fig. 2 (right) that for SAM + ERM once SAM converges minimum thanks to its implicit bias, then it is not important whether we continue optimization with SAM or with ERM.
4.9%
4.0%
600
750
800
902
1000
Eppcc
Figure 2: ERM vs SAM training over epochs. Top: standard SAM training. Bottom: SAM training enabled for the first 900 epochs and last 100 epochs.
well-generalizing
In particular, we do not observe overfitting when switching to ERM. We note that it is still important here that SAM converges since SAM has to minimize the training loss below some threshold after which ERM can be potentially applied.
At the same time, for ERM - SAM we observe a different behavior: the test error clearly improves when switching from ERM to SAM. This suggests that SAM (using higher p than the standard value, see App. C) can help to escape a suboptimal minimum where ERM converges to. This phenomenon is interesting since it suggests that such fine-tuning scheme can save computations potentially start from any pre-trained model and improve its generalization on the same dataset which different from fine-tuning with SAM in the transfer learning setup covered in Foret et al. (2021).
we can
5

---

Under review as a conference paper at ICLR 2022
1975
08
97%
66
97%
Tex eror SAM
04
47%
emar on sarpli,
62
60
20%
42
poo Moreaaiii eil Taalettt, nodd coo Paaseded Tailer Rosall crstiroodd
-04
Spech
Epcch
Epech
(a) Overfitting with noisy labels
(b) Alignment with ideal V VL (w) (c) Alignment with moisy V Vininnn (w)
Figure 3: Plots over training for a ResNet- 18 trained on CIFAR-10 with 60% label noise. We can observe that (a) test error increases when we fit the noisy samples, (b) using gradients at the SAM point doesn't 't change the alignment with the ideal direction, (c) using gradients at the SAM point decreases the alignment with the noisy part.
4 WHY CAN SAM HELP AGAINST OVERFITTING OF NOISY LABELS?
In this section, we discuss another important aspect of SAM: its beneficial effect for the noisy label setting. We first analyze the development of the gradient direction over training and then interpret SAM as a gradient reweighting schemes where the gradients are reweighted according to the sharpness of the loss.
Overfitting on noisy labels and the effect of SAM. By the noisy label setting we refer to a situation where some fraction of the training labels is changed to uniformly random labels and kept fixed throughout the training. This setting is challenging since standard training with ERM leads to overfitting as illustrated in Fig. 3a. In particular, it is commonly observed (Liu et al., 2020) that at the beginning of the training ERM fits the correctly labeled training points but, after some point, starts also fit the incorrectly labeled points, which coincides with overfitting in terms of the test error. Thereby, the noisy label setting is different from the standard setting from Sec. 3.3: training to zero loss is harmful and leads to overfitting, and thus early stopping is needed (Li et al.. 2020b). Fig. 3a illustrates that early stopping indeed leads to significantly better test error for the ERM model compared to the model taken at the last epoch. At the same time, SAM noticeably improves generalization over ERM, although later in training SAM also starts to fit the noisy points and thus also requires early stopping, either explicitly via a (potentially noisy) validation set or implicitly via restricting the number of training epochs as in Foret et al. (2021).
Benefits of following the gradient direction given by SAM. Consider a batch of points Sall == {(z, y) where some labels y noisy. We define Setean and Snotey to be the subsets of Sall with clean and noisy labels respectively. We also define Strue to be the same set of points as Salean but where all the labels are correct. We denote by [s(w) = [i| E(eples (w. the loss on set of points S where w denotes the model parameters, The gradient update then can be decomposed as:
Setean| V V.S.scon (w) +
Snoisyl V I.S.vii (w)
LS (w)
Sautl
|Saul
Here want to analyze the contribution of each part of the gradient for the ERM and SAM weight updates. For this, in Fig. 3 (b) and (c), we compare the following directions over training epochs of an ERM model: VLs (w) vs. V.serue (w) and VLS... (w) vs. V LS (w) for the current point w (i.e., the ERM update) and the point w + CSAM (i.e., the SAM update). To be robust to the label noise, would like the update direction of algorithm to be maximally aligned with the ideal direction V Ls...c (w) and minimally aligned with the noisy direction V L. (w). The key observation of Fig. 3b and Fig. 3c that SAM is changing the direction of the gradient by making less aligned with the noisy direction at the later stage of training when the model starts to fit the label noise. Therefore, the SAM update is less dominated by the noisy labels and can resist overfitting longer. To better understand this effect, we discuss next the behavior of SAM when training linear classifier in a binary classification setting.
SAM improves generalization even for linear models. Since using SumMax SAM (Eq. (2)) leads to better generalization than MaxSum SAM, we consider this technique for an overparametrized
"Thss, is different from the setting where new label noise is added on each iteration (HaoChen al., 2020).

---

Under review as a conference paper at ICLR 2022
linear model fu(w) = (ww,)) trained with the cross-entropy loss & using gradient descent. The
training objective of SumMax SAM then becomes:
n
min WER4
max É (yt (w + +d,x))) 10
min wEB4
Σ
(yr (w, - p||zz112)-
(6)
We consider the following simple dataset: x (yJu, o² Ia). where y E } is the label, and is some unit vector. We use o = 0.1, input dimension = 100, n = 50 train- ing samples, and we randomize 90% of the training labels.
60%
40%
20%
Triin emor: ERM
Train emo:: SAM
We select the best step sizes for ERM and SAM via a grid search. We can from Fig. 4 that SAM with early stopping consistently (over ten random seeds) improves the test error over ERM. This illustrates that benefits of SAM extend be- yond non-convex learning tasks with multiple minima and suggests that the linear setting can be good starting point for understanding the benefit of SAM.
20%
Text wrror ERM
Tost erior, SAM
10%
0%
Ioration
Figure 4: SAM for a linear model on two Gaussians with 90% label noise.
SAM as a gradient reweighting scheme. For general non-linear binary classifier (w(),, on every iteration of gradient descent, the update direction is given by the gradient on all points:
V LL (w)
(y: fz. (w))
Ffz
TI
loss derivative
direction
When we perturb the weights with SAM, we change in general both the loss derivative e' fu (w)) and the direction given by the classifier's gradient ffz(w). However, for a linear classifier fa fa(w). (w). only f'(y fa (w)) is changed while the direction (w) = x is independent of the weights. The fact
that SAM helps even in this simple setting suggests that its crucial effect can lie only in modifying the loss derivative e' (y (w)) which leads to beneficial reweighting of the per-example gradients of noisy and clean inputs. We note that gradient reweighting also the idea behind robust losses (Ghosh et al., 2017: Zhang& & Sabuncu, 2018) as they also affect only the loss derivative while keeping the direction V fa,, (w) the same. This suggests the following interpretation of SumMax SAM:
Gradient reweighting interpretation of SAM: SumMax SAM reweights per-example gradi- ents amplifying the derivative of clean points more than the derivative of noisy points so that the overall gradient direction V Ls (w) is more aligned with L. (w).
We observe from Eq. (6) that SAM offsets the margin ys x;) of each example by p ||æalle More generally, using SumMax SAM for non-linear models guarantees that the offset is non negativv for each example as maximization of a monotonic loss & implies minimization of the margin. Note that this would not be the case for MaxSum SAM or average-case perturbations of the weights. We discuss next why offsetting the loss can be valuable to reweight the gradients of different examples.
We first note that the early-learning phenomenon which is proven to hold under some assumptions in Liu et al. (2020) implies that the correctly labeled points are fitted first during training so that at some early stage they tend to have higher margin than the noisy points. We illustrate this in Fig. 5 for linear model. We then consider the following two losses: cross-entropy loss (CE) and generalized cross-entropy loss (GCE) (Zhang& & Sabuncu, 2018) (we hide the dependency of f on w for brevity)
ECE(y fa) = log(1 + exp(-y x- fa)). LGCEly ff) fz)= 1/9 (1 (1 + exp(-v fo)) VV)))) f)))
We plot these losses in Fig. 6a (using 9 = 0.7 for GCE following Zhang & Sabuncu (2018)) together with the derivative change from adding an offset in Fig. 6b and 6c. We observe based on Fig. 6b that the offset affects more significantly the points with small positive margins (i.e., mostly correctly labeled points due to the early-learning phenomenon) whose derivative is amplified more making closer to its minimal value of -1. Fig. 6c suggests that GCE has a better effect than CE since GCE does not only decrease the derivative of points with small positive margin but it also increases the derivative of the points with small negative margin (i.e., mostly noisy points) making it closer to zero This suggests that combining GCE with SAM can lead to further benefits which is indeed confirmed experimentally in App. D.
7

---

Under review as a conference paper at ICLR 2022
Make bosts
23
Canaclabblla
Corma labes
Connect lnsale
10
-25 -24
-3.2
0.0
04
04
66
Margin
Margin value
Margin value
(a) training
Early training
(c) End training
Figure 5: An illustration of the early- phenomenon (Liu et al., 2020) on the training set for linear model. Early in training the model achieves a good separation between noisy and correctly labeled points which disappears towards the end of training.
Knedy 80 -1 Ce---rrr (001
41
-44
Margi
Margry RM
Marghy- 1tl
(a) CE and GCE losses
Derivative change for CE
(c) Derivative change for GCE
Figure 6: Introducing loss offset mainly affects points with small positive (for CE and GCE) and small negative margin (for GCE) which mostly correspond to clean and noisy points, respectively, due to the early-learing phenomenon.
An ablation study for different variations of SAM on a two-class CIFAR-10 dataset. The error rates are averaged over three random seeds and reported with the standard deviation
Table I:
NAMB
GRADIENT FORMULA LS.., (w)
ERROR RATE
ERM
Ely fry (w)) V Sx. (w)
13.47% 1 0.80
SAM DIRECTION
Eyy. la; (w)) V (WSAM)
11.30% 1 0.68
SAM DERIVATIVE
E(y - fxy (WSAM ) fa, (w)
7.45% + 0.28
SAM
(l (wSAM V (WSAM)
9.02% + 0.34
Does the loss derivative change explain the behavior of a non-linear model? To further support our gradient reweighting interpretation for non non-linear models, we show that changing only the loss derivative E' (y4+ fr. (WSAM)) (see Eq. (7)) and discarding the change of the direction leads to the main benefit in SAM. For this, we train a ResNet- 18 on a two-class CIFAR- 10 under 80% label noise with early stopping and study different ways to modify the gradient V VLs(w) used on each iteration of training. We report results in Table where we observe that SAM DIRECTION leads only to small improvement compared to ERM (13.47% to 11.30%) while SAM DERIVATIVE is helping most leading to 7.45% test error. This gives more evidence that the main improvement from using SAM comes from changing the derivative of the loss E é'(y. fa, (WSAM)) )) and not the direction ff, (WSAM) which is coherent with our gradient reweighting interpretation of SAM. We further report extra experimental details and the plots over epochs in App. D.
WHY CAN SAM HELP AGAINST ROBUST OVERFITTING?
Here draw parallels between the overfitting observed in the noisy label setting and in robust training (Rice et al., 2020) where SAM also improves generalization (Wu et al., 2020).
The effect of SAM is similar for robust overfitting. In Fig. 7, we plot the error under adversarial perturbations obtained via the PGD attack (we use 10 iterations, see details in App. D) for an fx adversarially trained model (Madry et al., 2018) with e 8/255 trained with ERM and SAM for 1000
8

---

Under review as a conference paper at ICLR 2022
epochs. For this experiment, we the SAM algorithm in Foret et al. (2021) which also leads to similar improvements of robust error as the method introduced in Wu et al. (2020) which relies on a different scaling of the layerwise perturbation bounds. We observe that, when trained for sufficiently long (contrary to Wu et al. (2020) that only train for 200 epochs), SAM also leads to overfitting, showing high similarity to the noisy label setting (Fig.
Implicit label noise in adversarial training. Related the point above, a recent work of Dong et al. (2021) ar- gues about the presence of inputs which are "noisy" for adversarial training, and whose removal mitigates robust overfitting. They further discuss that such inputs become ambiguous for human observer after adding for adver- sarial perturbations. The problem stems from the for- mulation of adversarial examples which is widely used: max] Se {(x + 6) instead of the label-preserving for- mulation max Sc, =(x)==((++)) ((x + 8) which is ob- viously impractical since we cannot query the true label y(ar + +)) at arbitrary point during training. Thus, the commonly used adversarial perturbations can change the effective label y( + 5) leading to implicit label noise. This can be confirmed by implementing label- preserving adversarial training for linear model where we know the ground truth model. We can use the same two Gaussian example as in Fig. 4 but without explicit label noise and perform adversarial training in the sub- space orthogonal to the discriminative direction j which ensures that the label of + ò is not affected. We show experimentally in Fig. 8 that (1) robust overfitting can be observed also in simple linear models and (2) using the label- bheeeeirese formulation of adversarial training pre- vents it. This suggests that robust overfitting is strongly connected to the labels of adversarial examples.
70%
60%
30%
20%
Test PGD
Test PGD emor, AT
10%
Train PGD emor,
Train PGD amor. All SAM
0%.
200
400
820
500
1000
Epoch
Figure 7: The effect of SAM robust overfitting in adversarial training is similar to its effect for noisy labels (cf. Fig. 3a).
0:40
Standard adversarial training Labul-preeerving adversaria il training
Adversaria lest error
0.35
0.20
0.15
Training iteration
Figure 8: Robust overfitting for a linear
model is not observed for label-preserving adversarial training.
Mitigating implicit label noise by SAM and other methods. Performing label-preserving adversarial training requires the knowledge of the ground truth labeling function which is impractical. Thus, in practice one has to rely on algorithms that prevent fitting the implicit label noise in other ways. We hypothesize that an early-lcaruing phenomenon similar to the one observed adversarial training, and our gradient reweighting explanation of SAM from Sec. 4 should also extend to this setting. We also note that other solutions against robust overfitting that have been recently proposed in the Sierature-such as early stopping (Rice et al., 2020), weight averaging (Gowal et al., 2020; Rebuffi et al., 2021), bootstrap (Chen et al., 2021), data removal (Dong et al., 2021) alsoo rely on the carly-lcarnigg phenomenon and have been previously explored in the noisy label literature. We confirm this further on GCE (Zhang & Sabuncu, 2018) and semi-supervised pairing terms (Luo et al., 2019) in App. D. This further suggests that both settings are closely related, and improvements in one setting can also translate to the other one which can explain the improvement from SAM against robust overfitting.
training with noisy labels (Liu et al., 2020) should also hold for
6 CONCLUSIONS AND OUTLOOK
We have discussed two different objectives motivated by SAM and analyzed their implicit bias for a diagonal linear network. Then we have provided convergence proof for the variant of SAM used in practice and confirmed empirically that the best generalization performance is achieved at solution with nearly zero training loss on a standard image classification tasks. At the same time, in the noisy label setting, it is harmful to achieve low training loss even with SAM since this would involve fitting the noisy labels. We have discussed why SAM can be helpful in this case: we observed that SAM amplifies the contribution of the correctly labeled points compared to the noisy ones in the gradient update. Finally, we argue that the overfitting observed in noisy label setting shares a lot of similarities with overfitting observed in adversarial training which can explain why SAM is also helpful there.
9

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
Theoretical results. We provide proofs of our theoretical results in the Appendix in Sec. A for the implicit bias and in Sec. for the convergence of different variants of SAM. The assumptions A1-A3 for the convergence proof's are mentioned at the beginning of Sec. 3.2. An additional assumption A2' used only for the statements the appendix and thus introduced only there.
Empirical results. To facilitate reproducibility of our experiments, in Sec. C we specify all the hyperparameters of our experiments on deep networks and linear models. Moreover, in Sec. D, we provide more details about some of the experiments from the main part.
REFERENCES
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization deep networks. arXiv preprint arXiv: urXiv:1706.05394 2017.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel. Mixmatch: holistic approach to semi- superiupereise learning. arXiv preprint hel:1995.00244. 2019.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv: 1902.06705, 2019.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. In NeurIPS, 2019.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In International Conference on Learning Representations, volume 2021.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. ICML,, 2020.
Chengyu Dong, Liyuan Liu, and Jingho Shang. Data profiling for adversarial training: On the ruin of problematic data. arXiv preprint arXiv:2102.07433 2021.
Gintare Karolina Dziugaite and Daniel Roy. Entropy-sgd optimizes the prior of pac-bayes bound: Generalization properties of entropy-sgd and data-dependent priors. In International Conference Machine Learning, pp. 1377-1386. PMLR, 2018.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference Learning Representations, 2021. URL /
wtt.:r/et/oruuuamdmmmmmmmmmom... 6Tm1mpos1rM.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368 2013.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. AAAI, 2017.
Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.03593, 2020.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5200-5209. PMLR, 09-15 Jun 2019. URL htttt:://proceednng. wtt.:/mwrr....e.mmmmmmmmmmmmll www.ssrss//177 qi an1 9b. html.
10

---

Under review as a conference paper at ICLR 2022
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep re- current neural networks. 2013 IEEE international conference on acoustics, speech and signal lece, 2013.
processing, pp.
Jeff Z HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv:2006.0868/ 2020.
Kosuke Haruki, Taiji Suzuki, Yohei Hamakawa, Takeshi Toda, Ryuji Sakai, Masahiro Ozawa, and Mitsuhiro Kimura. Gradient noise convolution (gne): Smoothing loss function for distributed large-batch sgd. arXiv preprint arXiv:1906. 10822, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. ECCV, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Simplifying neural nets by discovering flat minima. In Advances in neural information processing systems, pp. 529-536, 1995.
Lang Huang, Chao Zhang, and Hongyang Zhang. Self-adaptive training: beyond empirical risk minimization. arXiv preprint arXiv:2002.10319 2020.
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson, Av- eraging weights leads to wider optima and better generalization. arXiv preprint 880,05507. 2018.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data- driven curriculum for very deep neural networks on corrupted labels. In International Conference PMLR, 2018.
on Machine Learning, pp.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv: arXiv:1912.022 191..0278, 2019.
Kam-Chuen Jim, C Lee Giles, and Bill G Home. An analysis of noise in recurrent neural networks: convergence and generalization. IEEE Transactions on neural networks, 7(6):1424-144 1438, 1996.
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-Lojasiewinn condition. In Machine Learning and Knowledge Discovery in Databases, pp. 795-811, 2016.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On aarge-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: M.XXiv1600.0440 1609.04836, 2016.
GM Korpelevich. Extragradient method for finding saddle points and other problems. Matekon, 13 (4):35 49, 1977.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report, 2009.
Samuli Laine and Timo Aila. Temporal ensembling for sunissup learning. arXiv preprint arXiv:1610.02244 2016.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robers Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9-48. Springer, 2012.
Junnan Li, Richard Socher, and Steven CH Hoi. Dividemix: Learning with noisy labels as semi- supervised learning. arXiv preprint arXiv:2002.0739) 2020a.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 4313-4324 PMLR, 2020b.
Tao Lin, Lingjing Kong, Sebastian Stich, and Martin Jaggi. Extrapolation for large-batcl training in deep learning. In International Conference on Machine Leaming, pp. 6094-6104. PMLR, 2020.

---

Under review as a conference paper at ICLR 2022
Sheng Liu, Jonathan Niles-Weed, Narges Razavian, and Carlos Fernandez-Granda. Granda. Early-learning regularization prevents memorization of noisy labels. Advances in Neural Information Processing Systems, 33, 2020.
Shengchao Liu, Dimitris Papailiopoulos, and Dimitris Achlioptas. Bad global minima exist and sgd can reach them. arXiv preprint
2019.
Yucen Luo, Jun Zhu, and Tomas Pfister. A simple yet effective baseline for robust deep learning with noisy labels. arXiv preprint (XXXx:1999.093330 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. ICLR, 2018.
Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Can gradient clipping mitigate label noise? In International Conference on Learning Representations, 2019.
Alan F Murray and Peter Edwards. Synaptic weight noise during mip learning enhances fault- tolerance, generalization and learning trajectory. Advances in neural information processing systems, pp. 491 491,, 1993.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.0229;, 2019.
Y. Nesterov. Introductory Lectures on Convex Optimization, volume 87 of Applied Optimization. Kluwer Academic, 2004. A basic course.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv: 1412.6614, 2014.
Scott Pesme, Loucas Pillaud- Filleed-Vivien, and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: provable benefit of stochasticity. In Advances in Neural Information Processing Systems, 2021.
Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Tim- othy Mann. Fixing data augmentation improve adversarial robustness. arXiv preprint arXiv:2103.01946, 2021.
Scott Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks noisy labels with bootstrapping. arXiv preprint arXiv:1412.6596. 2014.
Leslie Rice, Eric Wong, and J Zico Kolter, Overfitting in adversarially robust deep learning. In ICML, 2020.
Amartya Sanyal, Puneet K Dokania, Varun Kanade, and Philip HS Torr How benign is benign overfitting? arXiv preprint arXiv:2007.04022 2020.
Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel. Fixmatch: Simplifying semi- supervisd learning with consistency and confidence. arXiv preprint MtXiv:20011.0665 2020.
Jiaming Song, Lunjia Hu, Yann Dauphin, Michael Auli, and Tengyu Ma. Robust and on-the-fly dataset denoising for image classification. arXiv preprint 10647, 2020.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-199 1958, 2014.
Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd- Yusof. Combating label noise in deep learning using abstention. arXiv preprint 1rXiv:1905.100 10964, 2019.
Yisen Wang, Xingjun Ma. Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 322-330, 2019.
12

---

Under review as a conference paper at ICLR 2022
Wei Wen, Yandan Wang, Feng Yan, Cong Xu, Chunpeng Wu, Yiran Chen, and Hai Li. Smoothout: Smoothing out sharp minima to improve generalization in deep learning. arXiv preprint arXiv:1805.07889, 2018.
Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3635-3673 3673. PMLR, 09-12 Jul 2020.
Dongxian Wu, Shu-tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust general- ization. NeurIPS, 2020.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. unifying view on implicit bias in training linear neural networks. In International Conference Learning Representations, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 1. .03530,, 2016.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurrnt El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In ICMI,, 2019.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint 170.v:1710.09412, 2017.
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. Advances in neural information processing systems, 31:8778-8788, 2018.
Yaowei Zheng, Richong Zhang, and Yongyi Mao. Regularizing neural networks via adversarial model perturbation. CVPR, 2021.
13

---

Under review as a conference paper at ICLR 2022
Appendix
ORGANIZATION OF THE APPENDIX
The appendix contains proofs related to sharpness and convergence of different variants of SAM that omitted from the main part of the paper due to the space constraints. Moreover, the appendix also contains additional implementation details and extended experimental results. The appendix is organized as follows:
Sec. A: proofs related to the implicit bias of SumMax and MaxSum SAM.
Sec. B: proofs related to the convergence of different variants of SAM.
Sec. C: experimental details for the epxeriments with deep networks and linear models.
Sec. D: additional experiments about the importance of the change in the loss derivative
for deep networks, improvement of standard generalization under label noise by adversarial training, and the experiment with the GCE loss and semi-supervised pairing term that mitigate robust overfitting.
A THEORETICAL ANALYSIS OF THE IMPLICIT BIAS
To understand why SAM is generalizing better than ERM consider the simpler problem of noiseless regression with 2-layer diagonal linear network for which we can precisely characterize the implicit bias of the optimizations algorithms in hand.
Overparametrised noiseless regression. We consider linear regression with inputs, outputs (x1, Vi. Vi.-.... ......---.. Fn, yn) E (IR++1). We consider the overparametrised case and assume that there exists at least one interpolating parameter 3 E Rd which fits the training set: = (8", xx) for all 1 < n. We study the quadratic loss for which the training loss is written as:
L(3) = 4n Σ (1, y1)²
1 4n
1B 2
8" xx,))
2-layer diagonal linear network. The simplest parametrisation of | is to consider 9 = which corresponds to the classical least-squares framework. In this case, first order methods (GD, with and without momentum) converge towards the same solution: they have the same implicit bias. The same holds for the variants of SAM we consider and the linear case is not helping us to distinguish them and to show their primacy on ERM. To theoretically resolve this question, we study a simple non-linear parametrisation: the quadratic parametrisation = training loss in w therefore written:
w w² with = [w w-] E R22d The
L(w) = 4n (w - w²
-2 Dz)
)²)
((3,a,)) y1)² with B w²
w²
(8)
4n
This parametrisation can be viewed simplified linear network of depth 2. Additionally to being toy neural model, this model has received recently lot of attention since it is possible to precisely characterize the implicit bias of descent algorithm on it.
Optimization algorithms.
We consider minimizing the loss I(w) using three different algorithms:
Gradient descent with infinitesimally small stepsize (in the gradient flow limit):
き VL(w,,
(9)
*The MaxSum SAM algorithm with infinitesimally small outer-stepsize and inner step size p > 0:
W = VL((; + LVW(w)
(10)
-The SumMax SAM with infinitesimally small outer-stepsize and inner step size p 0:
w =
Vli(wz + (wx))
(11)
n
14

---

Under review as a conference paper at ICLR 2022
Implicit bias of the Gradient flow.
Let define the function da for R as
d (3) - Σ afq(B:/aF) where g(2) g(z)= S/ arccinh(u//)des = v 22r))in(22/2).
1=1
(12)
Note that if we have a E R then we consider &a = A11. We will make great uses of this function to precisely characterize the implicit bias of the different algorithms we consider. Indeed, following Woodworth et al. (2020) can show the following result for the gradient flow dynamics (9)
Proposition 3 (Theorem 1 of Woodworth et al. (2020)), For any 0 < < co, if the solution 3oo of the gradient flow (9) started from wh = al for the squared parameter problem in Eq.(8) satisfies X y, then
3e arg min Pa(3) s.t. X3 BERd
(13)
where da is defined in (1.)
It worth noting that the implicit regularizer da interpolates between the & and l norms (see Woodworth et al., 2020, Theorem 2). Therefore an implicit bias depending on the scale of the initialization is observed. The algorithm, started from al, converges to the minimum & -ormm interpolator for a small and to the minimum l2 no-mo interpolator for a large. The proof follows from (a) the KKT condition for the optimization problem (13): Vé,, (w) = X v for Lagrange multiplier v and (b) the closed form solution obtained by integrating the gradient flow, w = b( v) for some function b and some vector v. Identifying Vé. (w) b (w) leads the solution.
Considering the same proof technique, we now derive the implicit bias of both variants of SAM algorithms.
Implicit bias MaxSum SAM algorithm. We characterize the implicit bias of the MaxSum dynamics (10) in the following proposition. Recall that the function &a is defined in Eq. (12).
Proposition 4. For any 0 a oc, if the solution 3z0 of the gradient flow (10) started from Wp al for the squared parameter problem in (8) satisfies 33x = y. then
8x = aarg min Φ Pommn (3) s.t. X3 =
where OiMaxSum ae an (X (,)
We note that for P small enough (MMxSSum < a. The scale of the vector 3/4 (X 2ds (which influences the bias effect) is related to the loss integral d Jo L(w(s)dds since ||r,112 nL(w(s)) (see intuition in (16)) Thereby the speed of convergence of the loss controls the magnitude of the biasing effect. However in the case of MaxSum SAM, as explained below, this effect is typically negligible because of the extra prefactor á and this implementation behaves similarly as ERM (as n shown in the experiments in Sec. 3.1).
Proof. We follow the proof technique of Woodworth al. (2020). We first derive the equation satisfics by the flow
úi(t) = _X (+) w+ (t+)))))x+tt)
2n
TT) (w(t) + 2n
(
2n
where w. (t) = w(t) + pV (ww() is the intermediate SAM step, r(t) = Xw(t)²= - and r (t) = (t)()) are the residual of w(t) and w, (t) and we denote by X = [X - X). We can directly integrate this ODE to obtain a closed form expression for w(t):
w(t) (0)) exp(
1 T S/" r+ (s)ds) expl 4nd
P. 1 (XT (xTr+(s)) d(s))ds).
(xTr(s)dd)
2n
15

---

Under review as a conference paper at ICLR 2022
Using that the flow is initialized w(0) al and the definition of (t) yields to
B()) = (1)² =0(1)
a² exp( - S r+ (5)ds) exp(
P
/ (x (xTTx(()) (+)) (X r(s))ds)
(X)rss))
2n
a² expl 1 XT ( r+ (s)ds) o exp((
(x((Tr+())) (X r(s))dss
2n
n
2a exp(-
P
I (xTr+(s)) (XT ((s)) sinh(
n x [ (s)dsss
2n²
Recall we are assuming that Ao is global minimum of the loss, i.., X, = y. Thus
X
8x bovessun (X (Xv)..
with and (2) = 2a² sinh(2), 2 r+ (s)ds and
Mau = a
(- (x (e)r+(s)) (x 4n
P
(xTrs))))s)) r(s))ss).
(14)
Denoting by
(B) b, arcsinh
2a B),
and integrating this equation, we obtain the expression of da = Ei a34(3,/o3) where q(>) = 1ex arcsinh(u/2)dte 2 v4 x2 + arcsinh(z/2).
Therefore 3r0 satisfies the KKT conditions for the minimum norm interpolator problem arg ming (3) s.t. XB y, i.e.
XBx y VΦL (Bx) T
This proves the first part of the result. Now using the definition of r (s) we obtain
(t) Xw4 (t)² y
((((t)) + px r(t) w(t))²
-(()) 2xx (()) (x r(())² w((12
-r(() + 2xx o + / ((t).
And
X xtx= +(())
which concludes the second part of the result.
Implicit bias of SumMax SAM algorithm We characterize similarly the implicit bias of the SumMax dynamics (11) in the following proposition. Recall that the function &a is defined in Eq. (12).
Proposition For any 0 a < 3c, if the solution 3x0 of the gradient flow (11) started from Wo al al for the squared parameter problem in (8) satisfies X XBx y. then
Bxc arg min Pasaut (3) S.t. X8 y.
3
where O'SumMax = ae Jo Ei (x) B(x) --) do+0((P))
In addition, if we assume that there exist R, B > such that the features are bounded || < R almost surely and that the trajectory of the flow is bounded [|3(t)]] & B for all 2 0, we have for all
p S R2 /P(BBB1188.))
O.ummarr
16

---

Under review as a conference paper at ICLR 2022
We note that for p smaller than an explicit constant depending on the problem quantities, can assert that 4MaxSuu < a. Furthermore the scale of the vector 1 So Σx= - ((s) - y ds (which influences the bias effect) is related to the loss integral d d f L(w(s))ds, through ||r= = nL(((s) (see intuition Eq. (17)). Thus the speed of convergence of the loss controls the magnitude of the biasing effect. This effect is typically important in the case of SumMax SAM (see experiments 1e..3.1).
Proof. The proof follows the same lines as the proof of Proposition 4 Let us denote by I; = [x; xi). We then have that the dynamics of the flow (11) satisfies
1
wi()
3 w
2n
1=1
Ter (t) (.::(+())rr())))) w((),
2n
where w+ (t) is the intermediate SAM step. (t)))= = ã, w(t)² ys and ri.+ (t) (t)+ ys are the residual of wt(t) and w+ (t) at the observation (Iz. Vi). Integrating we obtain:
w=() - (0) o expl - S. (+)d)) o exp(
L. ((.(()))(())))))
2n
1=1
The remainder of the proof is similar to the one of Proposition 4 and we directly obtain that
P x 1/'
(s)+())((())ss)))
OssmmMax = expx
(15)
4n 1=1
Using the definition of re,+ (t) we have
Ti,+ (t) i.. w- (t)² 9t
w()² (1 + pr
... w(t) o Tat - Ys
Tse + (x)+)
at.
And therefore
=2(00)0)))=).(0011++++++0+003001 2p(utt)))+++++++ o(t))) ( 2g))
So if p is such that 1 1 p'r,((t)((t)TT' 27 2 0 then @ssumMax < a. Using Cauchy- Cauchy-Schve Schwarz in-
equality Ir, (1))))(()) TT)) w < ||,,1[[]||| + 1|.*1111)111>> and Holder inequality ||x;3) < || |
Thus (t) T 2? S ||||||(1|||| + +|8-_1D11111 And we have the result for p S 2 (B I|(_
Comparison between SumMax and MaxSum implicit bias and connection with the loss inte-
gral We wish to compare the two leading terms MaxSum (l) (X ((()² ( x2rr))2 and JsumMax(t) (t) n
Ei= 2t),(t)² which comprise the first order in the expansion of the a and relate them to the loss value at w(t).
We first note using Cauchy-Schward inequality that IsumMax (t) 2 IMaxSmm but we aim at obtaining a more quantitative result, even though the derivation will be informal. Com- paring their fn-orss amounts to compare the empirical fourth moment Massumm (1)]] = (w w.) Ei= ||r,]| ||,æ, (w w.) and second moment squared | (t)l1 = (w
w.) w. M E T, (2w w.).
We can compare the typical operator norm of these two random matrices. Following the Lai' law, the operator norm of Wishart matrix is with high probability || Σ 2,o; d and that
17

---

Under review as a conference paper at ICLR 2022
with high-probabilliy the squared norm of Gaussian vector is ||2/||
=e d. Therefore obtain that
de
a
=
d
~
1- - |II = Σ
T3 I|
Therefore in the overparametrized regime (d >>>>>>>> n2) we typically have that Isuntte (f)
Ixtecom()) (f) s n and the
biasing effect of the SumMax implementation would tend to be O(n) time better than the biasing effect of the MaxSum implementation.
However this first insight only enables to compare Max (t) and Summaa (t). is not informative on the intrinsic biasing effect of MaxSum and SumMax SAM. With this aim, we would like to relate the quantities MMxxSm (t) and Max (t) to the loss function evaluated in w(t). With high probability (still using the concentration of a Gaussian vector) we have that
|| Maxxam (f)l (ww(t) - w.) w.))T T
| Iaa (wo(t) w.)
d(w(() - -w))
maz (w(1) w-)
m7
=d((w(t))
(16)
And using the concentration of Wishart matrices, i.e., x ] have
for large dimension d, we also
|| SumMaax (4)l 7 (w(1) w.) X xX X(w(1) w.. T 1
d
n² (w(t) w.) T
d xx IX(w(t) - w.)
(w(t) w..) = x x) - w.)
Mw(()).
(17)
These approximations provide some intuitions on why the biasing effect of both SAM implementation can be related the integral of the loss. We formal derivation of these results future work.
Additional experiments on implicit bias of stochastic methods. We provide additional experi- ment to investigate the performance of stochastic implementation the ERM, MaxSum and SumMax SAM. As explained by Pesme et al. (2021), we observe in Fig.9 that the stochastic implementations enjoy a better implicit bias than their deterministic counterparts. We note that the fact that small batch versions generalize better than full batch version is commonly observed in practice for deep networks Keskar et al. (2016). We let the characterization of the implicit bias of these stochastic implementations as future works.
B CONVERGENCE OF SAM ALGORITHM
In this section we prove the convergence of the SAM algorithm a stationary point of the function or to a minimum when the function is convex.
B. CONVERGENCE OF DETERMINISTIC SAM ALGORITHM
Here we aim to understand the one-step approximation of SAM makes sense from an optimization perspective, i.e., whether the algorithm proposed in (Foret al., 2021) successfully minimize the
18

---

Under review as a conference paper at ICLR 2022
100
10a-
Tost Loss
Train Loss
10.40
FRM
RRM
MaxeSan SAM
MaxSum SAM
SAM
SAM
ERM SGD
10:20
ERM SGD
MaxSamm SCD
MaxSum SCD
StumMix SGD
SumMax
10
10a
10
10
10
10
10
10
Number of iterations
Number of iterations
Figure 9: Implicit bias of SAM on sparse regression problem with d = 30, n 20, ~NO I). (a v). All methods are initialized at a 0.01 and used with step-size = =1/l. L. and p= 1/T. SumMax SGD converges to a solution which generalizes better (left plot) and enjoys a different implicit bias from the other methods. At the same time, all algorithms converge to global minimum of at linear rate (right plot). The convergence rate is inversely proportional to the biasing effect.
||3..lo 3. y, x B_ and (z)
training objective. This is important aspect since if an optimization algorithm cannot sufficiently minimize the training loss, the resulting classifier typically will not lead to good generalization performance, even if it has some useful implicit bias (Neyshabur et al., 2014). We first consider the following first-order optimization algorithm on the objective L parameterized by w:
W++11 = Wt 7t V(ww, + Pr L(we))
(18)
where Pt and 7t. are the step sizes of the inner and outer steps, respectively. This update rule is reminiscent of the extra-gradien algorithm (Korpelevich, 1977) but with an ascent in the inner step, i.c., the gradient evaluated not at the current iterate but the point which maximises locally the function. Moreover, this update rule can also be seen as a realization of the general extrapolated gradient descent framework suggested in Lin al. (2020). However, taking an ascent step for extrapolation is not discussed there, and the convergence properties of the update rule from equation 18, to the best our knowledge, have not been proven.
Summary of the convergence results.
Let first recall the definition of smoothness.
(A2') (B-smoothness). It exists 3 > 0 such that [V((w) - V < 3l[ - v|l for all w, E Rd.
When the function L is B-smooth, convergence to stationary points can be obtained. Proposition Assume (A2'). For any y 1/3 and p 1/3, the iterates equation 18 satisfy for all
T 0:
2
vV(ww)) < 7(1 pB)T (L(wo) - L.),
T=
If, in addition, the function L satisfies (A3), then:
L(WT) - (1- 7(1 - pB0)p) (L(wo) L.).
2
We make the following remarks:
We recover the rates gradient descent but with constants increasing with the ascent step-size
p.
The condition p < 1/8 is necessary since the point w 1/8VI((w) can be a local maximum of L. Such would be a fixed point of the algorithm without being a stationary point of L.
The proof crucially relies the bound (VL(w, +p LVVL(w)) vL(w))) 2 (1=p3)][VL(w))) which shows that SAM-step is well aligned with the gradient step (see Lemma 7) and on descent inequality similar the classical one for gradient descent (see Lemma 8).
19

---

Under review as a conference paper at ICLR 2022
For non-convex functions, full details provided in Proposition 9. When the function satifies an addition
inequality, details are Proposition 10.
For convex functions, (V pV (ww)), VL(w))) 2 VL(w))] II and convergence holds for any step-size p given that 7p is small enough. Details are provided in Proposition 11.
Auxillary Lemmas. The following lemma shows that the SAM update is well correlated with the gradient V ((w) and will be cornerstone our proof.
Lemma 7. Let L be a differentiable function and w Rdd We have the following bound for any
2 0:
[-B
3
if L is B-smooth,
(VI(W + (VL(w))), VI(w)) 2 (1 [L)) where a =
0
if L is convex
14
L is j-strongly convex.
Proof. We simply add and subtract term / [w)l in order to make use of classical inequalities bounding (V (VL(w)) VL(w2), w1 w22 by | w2ll for smooth convex functions and W1, E R
(VL(W (VL(w)), VL(w)) = VLLoo---ZZLL)))VV.LL,,Lv
1/A/F//wtt/7//000>//////////0/ [VL()]]
2 (1+ap)
where the last inequality is using that
-B
if L is B-smooth, if T is convex
(VI(w)) (((W)))V((())))..... wn - w22 2 alluc wi 11 where a
if L is ju-strongly convex.
The next lemma shows that the decrease of function values of the SAM algorithm defined in Eq.(18) can be controlled similarly as in the case of gradient descent Nesterov (2004).
Lemma 8. Assume (A2'). For any S 1/3, the iterates (18) satisfies for all 2 0:
M(w+1) S I(w.) 7(1 p&3) (1
73 - pB) [wv](
2
If in addition the function satisfies (A3) with potentially μ O, then for all 7,P 2 such that yB(2 pB) S 2, we have
L(w++1) S L(wr) - 7 (11-2 78 + pp -1 7p82 2
[V
We note that the constraints the step-size are different depending the assumptions the function L. In the non-convex case, p has to be smaller than 1/8, whereas in the convex case, has to be smaller than 2/3.
Proof. Let us define by W++1/2 W, + LVL(ww, the SAM ascent step. Using the smoothness of the function L (Assumption (A2')) (see, e.g., Nesterov, 2004), we obtain
728
1(w++1) & L(wx)) ((on))-(VV[(uu/)))) (VI(w:-)))
[L(W
The main trick is to use the binomial squares
L -VV(( [VL(4+1/2) -L 2(VL(W)1122) VL(w:)),
20

---

Under review as a conference paper at ICLR 2022
to bound
22
L(w++1) - L(wi) ((V VL(w)))
(((x))
| /
3
2 [L( 720
-(ww))
[VL(w++1/2) VL(w)))1 ( VL(w)))
S (w:) 711 -03 78
where have used Lemma and that [VL(W(+1/2) VL(1))) < 8110411/22 will < -
8 (V
If in addition the function L is convex then we can use its co-coercivity (see, e.g., Nesterov, 2004) to bound || [L( (L(w)) ((VL(()+1/2) (L(w), 1x41/2 wi) and obtain tighter bound:
223 V L(
((w++1) & L(we) 7
vL(w)))
+
2
-ww) 3²3
723
(V(()))
|
[VL(w+1/22) - VI(w))11 7(1 3-VVV VL(wx))
7B
- - 7082
S L(w)) 7(1
)1 [|VL(ux))] 7(1
) VL(w)), (L(w))
2
73
+ pM(1 - -78 7p.32
< L(w:) 7(1
2 V
2
where we have used Lemma 7.
Convergence proofs. Using the previous Lemma 8 recursively, can bound the average gradient value the iterates (18) of SAM algorithm and ensure convergence to stationary points.
Proposition 9. Assume (A2'). For any 1/B and p 1/3, the iterates equation 18 satisfies for all T 2 0:
L(wo) - L(WT)
[V((w)]
Ty(1 - [1[1-p8][11 2/8 (1- p3]
Proof. Using the Lemma 8 we obtain
711 p33 78 2 p3)) [TT((w))11 I(we)) [(we+1).
And summing these inequalities for t = 0.... .T 1 yields
L(wo) -(WTT
[V(w))]1 TT(1 11) 28 -1- (1)p
When the function L. additionally satisfies a Polyak-I oojsiewiczz condition, i.e., the Assumption (A3). linear convergence of the function value to the minimum function value can be obtained. This is the object the following proposition:
Proposition 10. Assume (A2'-3). For any y 1/3 and p 1/3, the iterates (18) satisfies for all T 2 0:
I(w)) - L. < (1 11127111111 pB) (1- 73 (1 (1-
(1--31) (I(wo) - L.).
Proof. Using the Lemma 8 and that the function L is fr Polyak-LLojssiewizz (Assumption (A3)) we obtain
l( S L(wi) 21y(1 (1) 73
(L))(L(ur) - La))
21

---

Under review as a conference paper at ICLR 2022
And subtracting the optimal value L, we get
L(wr) - L. - (1-27 2yH((1 - p$) (1 (1- y3
2 (1 - p8)) (L(w)-1) Ln)
733
< I 27H(11 - pl8 1
2 (1 - 08)) (L(wo)- -..).
2
When the function L is convex, convergence of the average of the iterates can proved. Proposition 11. Assume (A2') and L convex. For any step-sizes and p such that 73 + p3) 2. then the averaged wT + Et= we of the iterates (18) satisfies for all T 2 0:
2p8 +1
L(ëT) L. S 7(2 - 78 + p3))T 11w0 - w.ll?
If, in addition, the function L is p-strrongly convex, then:
1) wxll? |RT w. 112 S (1 - (2 7B(1+ + p)))) (2p))) (2p
The proof is using different astute Lyapunov function (which works for the non-strongly convex case).
Proof. Let us define by Vi [L(w:) L(w.)) ) + 11,, w.l12 and by w/+1/2 wi + (VL(wu) the SAM ascent step.
2 2 + P3)||V
V4+1 V (VL 00 - w.) - (VL(WW+1/2), vL(ww)) +
2p
2
(VL(WC4122) ut + (VI(w;)) w.) +
(1+ V
2p
72
7 (VI(Wr+1/22) 1/41/22),4444222 w.)
(1 p3 VL (1112221
P
2p
S 7 (1
73
(1 + ( (VL()))LL W/+1/2 w.,)
P 2
If L is convex then L(w++ 1/2) - L(w.)= - (VL(( (,)( W241/2 - w.) and therefore we obtain
2 2 7/3 (1 pB) L()+ L(w.) S Vo Ve+1.
p
2
Using the definition of w/41/2 we always have that L(We+1/2) 2 L(we) + pll L(;))l therefore
1
73 (1+ -(wn))))-(..))) Vv. V4+1
2
And taking the sum and using Jensen inequality we finally obtain:
Vo Vr+1
L(LT Σ w.) - L(w.) S
T
70 + pB))
1=0
p
If L is ju-strongly convex, we use that (VL(W(+1/2) W/+1/2 w.) 2 /1| w - w.| to obtain
[1/41/22 - w_ll2 = ||we + LVL(m)) - w. 1| = || - 10112 + (V.(w: we - w.) + p² ((:))
> || - 1 ((,,), w.)
||we 2 - I(w.)]
2pV..
Therefore we have
1102211127771)) V441 S (1 -6-774 72(2 - 73(1+ +3))) S (1- (1 + +
22

---

Under review as a conference paper at ICLR 2022
B.2
CONVERGENCE OF STOCHASTIC IMPLEMENTATIONS SAM ALGORITHM
B.2.1
CONVERGENCE OF MAXSUM GRADIENT ALGORITIIM
When the SAM algorithm is implemented with the MaxSum objective optimization objective, two different batches are using in the ascent and descent steps. We obtain the MaxSum algorithm defined as
7h Σ VL,
Pt Σ Vl.(w)) b
Wi++1
(19)
IE
BEJ.
where 1, and J, different mini-batches of data of size b. For this variant of the algorithm obtain a similar convergence result that the one obtain with the same hatch for the two steps.
Proposition 12. Assume (A1), (A2') for the iterates (19). For any T 2 0 and step-sizes To = VTB and Pt T:7.g. we have:
T [L(w))]
802
(L(wo) - L.) +
T
3VT
bvT
1=
In addition, under (A2), with step-sizes 7/2 min 3u(e+1)2 20 and Pt /rr/B:
81+4
B[L(wT)] L. (L - L..) 22
1272
burT
We obtain the same convergence result that in Proposition 2, but under the relaxed smoothness assumption (A2').
As in the deterministic case, the proof relies on two lemmas which shows that the SAM update is well correlated with the gradient and that the decrease of function values can be controlled.
Auxilliary Lemmas. The following lemma shows that the SAM update is well correlated with the gradient VL(w)). Let us denote by (L++i(w)
Eiel. V&(w), VL++1/2(w) Eie,, (w: and w/41/2 = Wi 1/ the SAM ascent step.
Lemma 13. Assume (Al) and (A2). Then for all p 2 0, l and w Rd.
E(V WVL4112(1)), VL(w)) > (1/2 VD)) 8 8²p²0²
2
The proof is similar to the proof of Lemma 7. Only the stochasticity of the noisy gradients has to be taken into account. In this aim, we consider instead the update which would have been obtained without noise, and bound the remainder using the bounded variance assumption (A1).
Proof. Let us denote by á = + PVL(w), the true gradient step. We first add and subtract 2
VVL+i(W: + PV VL(W)) = (VL++ (w + (V - 1 VL(w)) - (VL++1 VL(w)).
We bound the terms separately. We use the smoothness of (Assumption (A2')) bound the first term:
E(VL++1 (w + pV L(41/22(w) V VL(w)) = E(V pV V
VL(O), VL(W))
1
< E
(EVVL(( + pV /V (1 VL))))))))))))))) + [VL(w)]
<
8²
E F|l + pv (V w0l
[ (
2
32p²
E [VL41/2((W) - V((w)|2 + 1 + L
2
p2p022
1
+ |V(ww]1
2h
23

---

Under review as a conference paper at ICLR 2022
where we have used that the variance of mini-batch of size is bounded by 0² Note that this term can be equivalently bounded by Spa (v] if needed. For the second term, directly apply Lemma 7 to obtain
E(VL++1
= = - VL(w)) 2 (1 - ()))
The next lemma shows that the decrease of function values of SN-SAM algorithm can be controlled similarly as in the case of stochastic gradient descent.
Lemma 14. Let assume (AI, A2') then for all y S 1/(23) and 1/(23), the iterates equa- tion 19 satisfies
E L(w++1) < E ((w) - 7/40)
+ p²beta).
This lemma is analogous to Lemma in the stochastic case. The proof is very similar, with the slight difference that Lemma 13 used instead Lemma
Proof. Let us define by Wx+1/2 = we + p [V Using the smoothness of the function L (A2), we obtain
728
L(w1+1) & [(w)) (V VL(w))) + W
2
Taking the expectation and using that the variance is bounded (A1) yields to
223
E. EI(w++1) < W. [(wr) ((VI(W++1/2)) V[(w:))
E
V
V
E L(wx) - E(V (W(+1/22) S E [(we) - E(V //
VL
The main trick is still to use the binomial squares
(L(w))
to bound
[(W++1) S E. [VV 223 E V ( -
TE - 1
- -[
24:3) V ("20)))))700331
TE -,A4w)))113333////000011-1111111 - w/|2
-7(1 [111--21111112110103311010111113 -
E L(w)) [4000
- -7(1 1 -11p::/1121212201111111111111111
E L(w)) |,
||
< - -- 111-20111220111=0))]1111>11 ||----/-10000100000000000011111"
+ 2y/)]
where we have used Lemma 13 and that
- ( w
Using Lemma 14 directly obtain the following convergence result.
24

---

Under review as a conference paper at ICLR 2022
Proposition 15. Assume (AI) and (A2'). For 12(3) and p S 1/(2),, the iterates equation 5 satisfies:
E VL(w))] < (wo) - ((TT)
Ty
This proposition gives the first part of Proposition 12. The proof of the stronger result obtained when the function is in addition PL. (Assumption (A3)) is similar to the proof of Theorem 3.2 of Gower et al. (2019), only the constants are changing.
B.2.2 CONVERGENCE OF SUMMAX GRADIENT ALGORITHM
When the SAM algorithm is implemented to minimize the SumMax objective, the same batch is used in the ascent and descent steps. We obtain then iterates (5) for which we have stated the convergence result in Proposition 2. The proof follows the same lines as before with the minor different that are assuming the individual gradient ft are Lipschitz (Assumption (A2)) to control the alignment of the expected SAM direction. Let denote by (L()))
Eier. (&www)
Lemma 16. Assume (Al-2). Then have for all E RR, p 2 0 and t 20
18pp002
B( (VL, (L))), 2 (1/2 - - 12
2b
The proof is very similar to the proof of Lemma 13. The only difference is that the Assumption (A2) used instead of (A2").
Proof. Let us denote by Φ = = pV L(w). the true gradient step. We first add and subtract (t)
(VL((w + (w)), VI(w)) = (VL(ww (L) (L, VL(w)) - (V)((w) VL(w)).
We bound the two terms separately. We use the smoothness of I.; bound the first term (Assumption (A2)):
- -VLL + (V)((w)) VL, VL(W)) -
V -VL(())- (2)(1)) [L(w]]2
2
2
8²
< E ||w + (VL, - - + 1 2
2
p²
< [VL((w) VLW)I| [L(w))
And taking the expectation, we obtain:
8pp02 1
E E(VL.(w + (VL(w)) (L. VL(w))
+
E (
2b
2
For the second term, we apply directly Lemma 7
((V VL(w))) = (w)) VL(w))
2 (1 3p) L
Assembling the two inequalities yields to the result.
The next lemma shows that the decrease function values SAM algorithm can controlled similarly as in the case of gradient descent. It is analogous to Lemma 8 where different batches are used in both the ascent and descent steps of SAM algorithm.
Lemma 17. Assume (A1-2). For all 7 < 1/3 and & 1/(43). the iterates (5) satisfies
B (. [(.)) / E (T()))] >/80 1/802/b(T + 2p²
25

---

Under review as a conference paper at ICLR 2022
Proof. Let define by 1/+1/2 w/ + DV Using the smoothness of the function L which implied by (A2), we obtain
728 L(w++1) S L(we) (w VL(xm))
We still use the binomial squares
|| I (W - - 21 VL(w;))
and bound [(wr+1) by
723
L(w++1) $ L(we)
VL(w))1 1 (L441(4411/2) - -/ (L(w)))
2
723
$ L(we)
[V + 11 -V
2
7(1 7B8
(VLLI ( vL(w;))
< ((w)) 23
|v((w)|| + 333 13 (
2
- 7(1 - BB V I W1 (w(+122) ((()))
= L(w+) 323 3
[L(w))) + =
((w))]
2
- 7(1 (B)
(VL T (w) VI((w:)
-(w+) 723
(1 482 ++= + VL(())]
2
- -7(1 - (1122) VI((w:)
Taking the expectation and using Lemma 16 we obtain
L(W++1) S E L(wr) 723
4,3 E ((W))) + + + 2²) E Vb Vl++ - V((w))|l
- 711 -133 (( VL(w)))
$ <EL(w) 2²3
(1 4.2 E ((w))) 32 2222 28
2
8²0232
-7(1 x3) 3p) +
2h
< L(w.) 72. (1 ( 7 232 2 002/1 ib
p²82
2 (1- - 111-2pp(11 - 7( - 2 /
(1 + 3y8)].
2
Using Lemma 17 we directly obtain the following convergence result.
Proposition 18. Assume (AI-2). For r I 1/3 and p 1/48, the iterates (5) satisfies:
1 T-1
E < 8/3 L(wn) - E ((WT)
+ -T-27T37 + /² (3b))
T
Ty
In addition, under (A3), with step-sizes 7/- =min Ju(E+1)}
81+11 1/(33) and p. v vrlB3:
E[L(wr)) I. (T3((((wo) L.))
22,80
2T
1T
Proof. The first bound directly comes from Lemma 17. The second bound is similar to the proof of Theorem 3.2 of Gower et al. (2019), only the constants changing.
26

---

Under review as a conference paper at ICLR 2022
20%
40%
Test enror, normalzed SAM,
Test error, normalized SAM, 0.2
Test error, unnomalized SAM, p 0.3
Test emrrr unnomalized SAM, p 0.4
15%
Train error, nomalized SAM, p D.1
30%
Train eroor nomalized SAM, p D.2
Train error, unnomalized SAM, P
Train error, unnormalized SAM, p 0.4
Emor
10%
20%
5%
10%
0%
0%
200
400
600
800
1000
0
200
400
600
800
1000
Epoch
Epoch
(a) Without label noise
(b) With 60% label noise
Figure 10: Training and test error over training epochs for the normalized and unnormalized formulations of SAM. We that both variants of SAM improve the test error to similar level.
B.3 GRADIENT NORMALIZATION IN SAM
We consider here the implementation of SAM algorithm where the inner gradient step is normalized:
VL(w))
W Wt - VLL w: +
(20)
[L(w))]
We state here several claims showing that the normalized formulation in (q.) can be less favorable than the unnormalized one of (18).
Fact I: Normalized SAM does not converge with constant step-size. The last iterate of SAM with constant step-size never converging which can be easily seen on the function L(w) = 0.5w for I. Indeed SAM iterates equation 20 become Wr+1 = (1 7)w, - 7 signing(w (w), and convergence implies that the limit Woo would satisfy the fixed point woo = siiign woo) which
never holds for p >
Fact II: Normalized SAM when averaged does not necessarily converge to a flatter minimum. Let us consider the following simple function
{ 1/2w²
if w 2
I(ww)
1 1/6w
if w
When applied to this function with p 1, starting from wo = -1, then it is experimentally observed that the averaged of the iterates (20) converge to a positive point w = 0.0149 which is sharper than the origin, i.e, (w=)) 0.515 > S (0) 0.5.
Fact III: Normalized SAM can stay stuck at non-stationary points of the function it optimizes.
For any there exists a non-convex function Lp and a point upp such that V (w PPVhautl = 0
V.,[W,))
and V I. (w,) # 0. To see that, just consider the function -0.5x² and wp p.
Performance of the unnormalized SAM for deep networks. Given the potential shortcomings of the normalization step SAM, is interesting to compare the generalization properties of the normalized and unnormalized versions. For this, we repeat the experiments in Sec. 3.3 and Sec. 4 but for the unnormalized formulation in Fig. 10 with a grid search over p. We can observe that although the optimal p is not the same for both formulations (p 0.3 p 0.1 without label noise and p 0.4.4 vs P = 0.2 with 60% label noise). the test error of the normalized vs unnormalized variants very similar: 3.69% vs 3.70% without label noise, and 10.03% 10.29% with 60% label noise. Thus, given the same generalization performance, the unnormalized version may be preferred due to the lack of the shortcomings descrihed above.
27

---

Under review as a conference paper at ICLR 2022
C EXPERIMENTAL DETAILS
Experiments deep networks. In all experiments, train deep networks using SGD with step size 0.1 and momentum 0.9, and e--regularization parameter À = 0.0005. We use three datasets: CIFAR-10 Krizhevsky & Hinton (2009), CIFAR-I00 Krizhevsky & Hinton (2009), and two-class CIFAR-10 10 where we select two random classes (horse and car). We train models with basic data augmentations: random image crops and mirroring. We use pre-activation ResNet-18 18 (He et al., 2016) with a width factor 64 and piece-wise constant learning rates (with a 10-times decay at 50% and 75% epochs) for all experiments except Table 2 where we follow the setup of (Huang et al., 2020) and use ResNet-34 with cosine learning rates with one cycle. We train all models for 1000 epochs except the experiments in Tables 2, and Fig. 13 for which we use 200 epochs as they require more expensive training (due to adversarial training) or an expensive grid search over each dataset and label noise amount.
For all experiments involving SAM, we select the best based on grid search over p E {0.025, 0.05, 0.1, 0.4). In the tine-tuning ERM with SAM experiment, we used p 0.2. We do not use the m-sharpness (Foret et al., 2021) since we were not able to reproduce exactly the results of the SAM paper with batch size of 256 and m 32 (as suggested by Foret et al. (2021)) for the noisy label experiments. Instead, observed that the same performance can be achieved using smaller batch size 128 and m = 128, thus we opted for this setting which has an advantage of being significantly faster (thus, could perform detailed grid search for each setting) if only one GPU is available per run.
For model selection determine the best epoch early stopping and the best p. we 10% of examples from the noisy training set as the validation set following (Zhang & Sabuncu, 2018). We emphasize that do not assume access clean validation set to perform early stopping.
For stochastic weight averaging (SWA), we use an exponential moving average with parameter 0.999, and update the moving average every iteration. Moreover, we start SWA from the very beginning of training (e.g., similarly to Rebuffi et al. (2021)) which is not the same setting as proposed in Izmailov et al. (2018) who start SWA from a specific epoch, use different moving average coefficient, and a modified learning rate schedule. We deviate from the setting of Izmailov al. (2018) since it has much more hyperparameters than the single moving average parameter т, and those hyperparameters have to be chosen differently for the noisy label setting compared to the standard setting of Izmailov al. (2018).
For experiments with the generalized cross-entropy loss (GCE) Zhang & Sabuncu (2018) we use q = 0.7 as recommended in Zhang & Sabuncu (2018) unless mentioned otherwise.
For experiments with loo adversarial training, we use 8/255 as in Madry et al. (2018); Rice et al. (2020), iterations of Projected Gradient Descent (PGD) for training and 10 iterations for testing (following Rice et al. (2020)), step size 2c/nstus for training (as in Madry et al. (2018)) and step size c/a for evaluation (as in Croce & Hein (2020)). Note that we use PGD with 10 iterations to get understanding of the qualitative behavior over epochs without using expensive computations. However, to strengthen the evaluation, we also use AutoAttack Croce & Hein (2020) to assess the robustness of the best model over training. The model selection is performed via the validation robust error obtained via 10-iteration PGD.
Experiments on a linear model. Here we provide details for the experiments shown in Fig. 4. We train a logistic regression model without regularization using full-batch gradient descent. We use 50 training examples which are sampled from two Gaussians in 100 (00-dimensional space. Each Gaussian has the standard deviation o = 0. and the mean of each Gaussian f is sampled randomly from the unit sphere. For optimization, we initialize the weight vector randomly on the sphere of radius 1/3 and use 50 iterations of gradient descent with a step size 2.0. We use = 5.0 for SAM.
Computing infrastructure. We perform all our experiments with deep networks on NVIDIA V100 GPUs with 32GB of memory.
28

---

Under review as a conference paper at ICLR 2022
Tost
Test losa
Train loss
Train loss
loss SAM
Test SWA
losa
0.8
Choetteeet teopee 10'
0.0
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
Interpolatio
Interpoiation
Figure 11: Loss interpolations of ASM VS w WERM and WSWA VS WERM. We see that the loss interpolation for SAM is qualitatively different from SWA.
D ADDITIONAL EXPERIMENTS
Differences between SAM and Stochastic Weight Averaging. Stochastic Weight Averaging (SWA) (Izmailov et al., 2018) is a weight averaging technique that improves generalization and, similarly to SAM, also motivated from the perspective of sharpness of the loss, thus it is natural to ask whether SAM shares some similarities with SWA. To study this, we plot the loss interpolations between the weights of SAM, ERM, and SWA models (WSAM. WERMs WSAM) ) in Fig. 11 which suggest that SAM and ERM converge to different minima. This is further supported by the fact that ||wSAM - WSw All2 is large, i.e., = 1/3 of the distance of WSAM to its initialization. Interestingly, there is peak between WSAM and WERM which is, however, not too high and the model at the peak still has non-trivial test error (around 40%). This is in contrast to WSW which is located in the same valley WERM with a very sharp increase close Werm (similarly to the interpolations from Izmailov et al. (2018)). We also note another difference between SAM and SWA in the context of the fine-tuning experiment from Fig. 2: fine-tuning an SWA model will lead to slight overfitting as would converge to standard ERM model (Izmailov et al., 2018) contrary to SAM which improves generalization.
Does the loss derivative change explain the behavior of a non-linear model? Here we provide more details on the experiment from Sec. 4 about the importance of changing the loss derivative ('( Sz, (w)) with SAM as opposed to the direction of the individual gradients V (w.)
We train a pre-activation ResNet- 18 (He et al., 2016) with width factor 16 (instead of the standard 64) on two-class CIFAR-10 10 dataset (horse vs car classes) using batch size 256 and mSAM = 64 which refers to the m-sharpness defined in Foret et al. (2021)). We note that this experiment would be more difficult to perform for the multi-class setting due to the fact that l'(x; fe, (WSAM) will not be a scalar. In order to select P for each of the SA.M-assed methods, we performed a grid search over {0.001, 0.003, 0.01, 0.03, 0.1, 0.2}. We train each model three times and report the average test error (obtained with early stopping on the validation set) with the standard deviation.
In Fig. 12, we plot the test error of all the four methods the test error for SAM derivative is oscillating (unlike for other methods). the best test error over epochs (7.45% + 0.28) is lower than for other methods and close to that of SAM (9.02% + 0.34). We emphasize that all reported results are obtained via proper model selection over epochs using a validation set. To conclude, we can see that by discarding the direction of SAM the test errors start to oscillate but we still preserve the improved generalization if we use early stopping.
epochs. We see that although
Beneficial effect of combining SAM with GCE. the ad advantage of using SAM with a robust loss such as GCE (Zhang & Sabuncu, 2018) instead of CE to better leverage the early-learning phenomenon. We validate this hypothesis experimentally using ResNet-34 network trained on CIFAR-10 and CIFAR- 100 datasets and present results in Table for (40%, 60%} label noise (for the further details see App. C). We present results from the literature (Huang et al., 2020) where all of them use ResNet-34 except MentorNet which uses WRN-288100 10. Early stopping based on a noisy validation set is done for each method except those reported from the literature. We can that SAM indeed performs better with GCE than with CE which leads to competitive results. Moreover, the results can be further enhanced by using weight averaging (Izmailov et al., 2018) where it outperforms many recently proposed approaches including
We check how predictive is our explanation about
29

---

Under review as a conference paper at ICLR 2022
50%
40%
SUM derielive and
40%
SAMM carieaoi
40%
Tix cervetiive Tika marn Boldd
Stancand Bold
30%
-2%
Teltenn
80%
20%
20%
20%
10%
10%
10%
100
(a) Random seed 1
(b) Random seed 2
(c) Random seed
Test error over epochs for ERM, SAM direction, SAM derivative, and SAM for three random seeds. Although the test error for SAM derivative is oscillating, the best test over epochs (dashed line) is lower than for other methods.
Figure 12:
Table 2: Test error of CE + SAM and GCE SAM under label noise compared to methods from the literature. Using SAM with the GCE loss works better against label noise compared to using SAM with the CE loss as predicted by our gradient reweighting interpretation of SAM.
CIFAR-10
CIFAR 100
% LABEL NOISE
40%
60%
40%
60%
SCE (WANG ET AL., 2019)
13.26%
19.20%
33.59%
42.57%
MENTORNET (JIANG ET AL.. 2018)
11.00%
32.00%
DAC (THULASIDASAN AL., 2019)
9.29%
13.70%
33.08%
42.83%
SELF-ADAPTIVE TRAINING (HUANG AL., 2020)
7.36%
10.77%
28.62%
37.31% %
CE
17.06
23.06%
44.82%
58.30%
CE + SAM
7.29%
10.98%
36.79%
43.02%
GCE + SAM
7.18% %
10.41%
28.82%
37.32%
GCE + SAM + WEIGHT AGENGGING
7.62%
9.74%
27.79%
35.91 %
Self- Adap-veee Training (Huang al., 2020). We also note that it can be further combined with other successful approaches against label noise such as MixUp (Zhang et al., 2017), bootstrapping (Reed al., 2014), and semi-supervised learning approaches (Li et al., 2020a).
Mitigating robust overfitting, To illustrate how techniques from label noise can be transferred to adversarial training and improve upon robust overfitting, we benchmark here two approaches: (I) generalized cross-entropy (GCE) loss and (2) semi- cuni-superviee pairing terms (Laine & Aila, 2016; Luo et al., 2019). We train all methods for 200 epochs in Rice al. (2020). To the best of our knowledge, these approaches have not been used to prevent robust overfitting.
In Fig. 13a, we show the performance of adversarial training with the GCE loss (we use g = 0.9) instead of the standard cross cross-entropy loss. We observe that GCE is able to mitigate robust overfitting. however it does not improve the performance the best model over epochs compared to the cross- entropy loss, so its usefulness is limited.
In Fig. 13b, we show the results of adversarial training with an additional semi-supervised pairing term (Laine & Aila, 2016) that has been used mitigate label noise in, e.g., Luo et al. (2019) (see also Li et al. (2020a) for a more advanced approach). Specifically, let f be the logits of the network, xr. be the foc adversarial example generated for sample x; using the PGD attack and o; be version of x; with a different augmentation. Then the additional term that we use in the objective is:
A
[[((ad f(
(21)
which we use together with the cross-entropy adversarial examples as in standard adversarial training (Madry et al., 2018). We use À = 1.0 and a "warmup" scheme for the regularizer which consists in starting the regularizer after 50% of training epochs which is standard practice (Laine & Aila, 2016; Luo et al., 2019). Both À and the starting epoch were determined via grid search. We show in Fig. 13b the robust error over epochs given by PGD with 10 iteration of adversarial training with and without the pairing term. We can observe that adding the pairing term mitigates the robust overfitting trend, and leads to improved robust error.
30

---

Under review as a conference paper at ICLR 2022
70%
70%
50%
50%
MMN
40%
40%
W
mmm
Test PGD error, AT Test PGD error, AT GCE
Test PCD error, AT
Test PGD error, AT pairing
20%
PGD
20%
Train
Train PGD error, AT GCE
Train PGD emor, AT pakking
10%
10%
25
50
75
100
125
150
175
200
0
25
50
75
100
125
150
175
200
Epoch
Epoch
(a) Adversarial training without/with GCE
(b) Adversarial training without/with & pairing
Figure 13: Robust error over epochs for standard adversarial training compared to adversarial training with GCE and with the &g pairing term.
To make sure that the improvement is not due to gradient masking (Carlini et al., 2019), we evaluate the best model additionally with Auto (Croce & Hein, 2020). The model trained with the pairing term achieves 51.15 31.15% robust error while the standard adversarial training leads to 52.56% robust error and adversarial training with SAM achieves 50.07% robust error. Thus, we conclude that the techniques from the label noise literature (beyond simple early stopping (Rice et al., 2020)) can be successfully transferred to improve upon robust overfitting. Moreover, we note that more advanced pairing terms possible, c.g. involving temperature scaling of the logits (Berthelot al., 2019), more advanced data augmentations (Sohn et al., 2020), and other improvements over the standard pairing (Li et al., 2020a). We leave applications of more advanced pairing techniques improve upon robust overfitting as future work.
Finally, the improvement from the pairing term may also be connected to the fact that the TRADES objective (Zhang et al., 2019) often works better than standard adversarial training (see Gowal al. (2020) for exhaustive empirical study). The approach of TRADES also adds an additional pairing term that does not rely on the ground truth labels to the standard cross-entropy loss (although TRADES uses a different loss and does not different augmentation on σ.). This suggests that even some of the existing successful techniques can be interpreted based on the connection between label noise and robust overfitting.
31


Reviews:
[{"review_id": "yoi2e7HLLv", "reviewer": "Reviewer_nmv6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work provides an analysis of the sharpness aware minimization (SAM) by Foret et al. 2021. While the paper has some experiments, they are minimal and serve to reinforce the points made by the theoretical analyses. Therefore, I view this work to be a primarily theoretical work.\n\nThe first result uses the technique of Woodworth et al. 2020 to analyze the implicit bias of SAM when applied to 2-layer diagonal linear network. Although the model considered is very limited, and although the analysis technique is not novel, I still think this is a good first step. The authors summarize the results of their analysis in Proposition 1, but I am not sure if I agree with the interpretation of the anlayses. I do see that the implicit objectives differ by a factor of \\alpha^(1/n) but this is a mere multiplicative factor that should not overall affect the meaning of the implicit optimization problem. In particular, I don't fully understand the reasoning behind the claim \"The SumMax implementations has better bias properties since its effective scale of α is considerably smaller than the one of MaxSum.\" I would be happy to be corrected in the rebuttal, but otherwise I feel that Proposition 1 does not provide much insight into why MaxSum, SumMax, and regular SGD have different generalization performances.\n\nThe second result is a convergence analysis of SAM. This is a result that was missing in the original SAM paper, so it's nice that the authors establish that SAM converges to a stationary point, just as SGD does. However, the analytical techniques are not quite novel, and the conclusion says nothing about why SAM is better than SGD.\n\nFinally, the authors provide discussions on why SAM provides benefits when labels are noisy and how SAM prevents robust overfitting. While the discussions here are interesting, they are not rigorous mathematical discussions, and the experimental validation of these discussions is not very thorough. Therefore, I view the contribution of these sections to be minimal.", "summary_of_the_paper": "This work provides an analysis of the sharpness aware minimization (SAM) by Foret et al. 2021.", "summary_of_the_review": "Overall, the paper presents some interesting and useful analyses, but the analytical techniques are not very novel and they do not (at least to me) provide significant clarity on why SAM outperforms SGD.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "h45YVWiF91o", "reviewer": "Reviewer_EJMz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\nThe main strength of the paper is the theoretically sound and insightful analysis of SAM. \n\n### Weakness\n* In its present state, the paper unfortunately reads a bit like a collection of disparate specialized results, and there is no deep fundamental insight gained why SAM improves generalization over SGD.  Perhaps this could be addressed by providing a more speculative / high-level discussion in the conclusion / outlook section. \n* It is proven that SAM converges to a stationary point of the original loss (similar to SGD). To me, this is actually a weakness of SAM and not a strength, since ideally one wants a robust method to converge to points in the landscape which are non-stationary but in an overall \"flat\" low-loss region. \n* In the paper, it is mentioned that the averaged iterates of normalized-SAM converge to a different point and it is argued that this \"different\" point is a bad one (\"not necessarily flatter than the solution\").  Is this conclusion based on some empirical evidence or a theoretical insight? It would be great if the paper could elaborate on this point. \n* Should Foret et al (2021) and Wu et al (2020) really be considered concurrent work? They are quite far apart (Apr2020 vs Oct2020 on arXiv).\n* Also, there is the concurrent work to SAM https://arxiv.org/abs/2010.04925 which should be mentioned. ", "summary_of_the_paper": "The aim of the paper is to provide theoretical explanations for the recent successes of adversarial weight perturbation and sharpness-aware minimization (SAM) methods. In particular, these methods have been shown to significantly help robust generalization in deep learning and theoretical explanations for their success are missing so far. \n\nThe paper aims to fill this gap by getting a better understanding of SAM. It contributes a collection of miscellaneous results:\n* A proof that SAM provides better generalization for linear neural networks than SGD\n* The convergence of SAM is analyzed and generalization behavior is discussed\n* A new interpretation of SAM is presented in terms of gradient reweighing \n* Finally, a connection of SAM to the noisy label literature is made", "summary_of_the_review": "I believe that the collection of theoretical results on SAM is both novel and useful to the community. Moreover, the paper is well-written. If the issues mentioned in my main review can be addressed, I am inclined to increase my score and recommend acceptance of the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fiNE7UUeRtJ", "reviewer": "Reviewer_BAw4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": " I think this paper is well organized, and the proof seems solid. But I still have the following concerns:\n1. This paper doesn't analyze SAM proposed in [1]. In the SAM algorithm, the gradient is normalized in the inner step. However, the algorithm proposed in this paper doesn't include such gradient norm terms. Just as the authors have summarized in the abstract, \"$\\ldots$ relies on worst-case weight perturbations,\" the gradient norm term is one of the most important parts of the SAM algorithm. \n\nThey constructed the counterexamples for the original SAM algorithm in section B.3 to show the strength of using an unnormalized one. However, those examples are far from the practice because they are strongly convex with global minima at point zero. In this case, it is obvious that the algorithm will never converge to zero, even with a small perturbation. In practice, however, we use the cross-entropy loss for classification problems in which the good local minima would be far from zero. The training loss also has many local minima. In this case, a small perturbation will still guarantee the convergence and help find the flat minima.  \n\nIn order to show the algorithm proposed in this paper outperforms the original SAM algorithm, it would be more convincing if the authors could add more empirical comparison. I also want to ask whether the experiments in sections 3.3, 4, and 5 follow the SAM algorithm without normalization.\n\n2. I get quite confused about whether MaxSum is better than SumMax. Before the implicit bias part on page 3, the authors write, \"We next show formally that MaxSum SAM has a better implicit bias than ERM and SumMax SAM.\" Then, in the empirical part on page 4, the authors conclude that \"ERM and MaxSum SAM enjoy the same performance whereas SumMax benefits from a better implicit bias.\"\n\n3. Most of the results in this paper implicitly use the square loss rather than cross-entropy loss which limits the impact of the results. Does the implicit bias exist for cross-entropy loss? If so, it is worth adding it to the paper.\n\n4. The convergence results in section 3.2 are based on assumptions A1 and A2. Generally, do you think assumptions A1 and A2 hold for NNs? Or do those assumptions hold for the diagonal linear neural networks analyzed in section 3.1? \n\n5. Figure 1 shows that ERM and MaxSum SAM enjoy the same performance. I think maybe $\\rho$ is too small, have the authors tuned the parameter of $\\rho$?\n\n[1] Foret, Pierre, et al. \"Sharpness-aware Minimization for Efficiently Improving Generalization.\" International Conference on Learning Representations. 2020.", "summary_of_the_paper": "In this paper, the authors mainly analyzed a SAM-like algorithm with a square loss. For diagonal linear networks, this paper proves that the NNs trained by the algorithm has better generalizations than the ones trained by normal SGD. For deep NNs satisfies PL condition and other assumptions mentioned in section3, the authors can prove the algorithm will converge. The authors use a linear model to give the intuition why the SAM algorithm can generalize better on a dataset with label noise.", "summary_of_the_review": "Is the main contribution of this paper to understand the original SAM algorithm or to propose a new SAM-like algorithm with a theoretical guarantee? I think that the paper has to make more clear what are the main contributions. The proof technique used in this paper is quite standard, and the results are based on the square loss. So the impact of the results may be limited. I also have some concerns about some details, as I have mentioned in the main review. So currently, I would like to suggest a rejection, but I am open to discussion and willing to increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZV7Pp9Kp9HI", "reviewer": "Reviewer_iJV1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an ambitious paper that seeks to cover many a lot of ground, from convergence properties of SAM, to generalization error, to robustness in noisy labels and adversarial training. The reviewer believes that each of these issues merits a single paper, so to squeeze all the discussions into one paper actually dilutes each of the contributions, as I will discuss below. \n\nThe authors did a nice job to introduce the MaxSum SAM formulation and stochastic gradient descent-type algorithms to optimize the minmax objective. The first major result is Proposition 2 in which the authors use analytical techniques from SGD to control the expected gradient of SAM with stochastic gradients. The problem with this result is that, while mathematically elegant, it does not explain why SAM outperforms SGD. A theoretical explanation of SAM must be accompanied by comparison of the theory to SAM. \n\nThe next contribution has to do with SAM's robustness to noisy labels. This is good aim to study. However, the explanation falls short of being convincing. The authors merely use the fact that SAM changes the direction of the gradient to be less aligned to the noisy direction. They substantiated this fact using Figs. 3b and 3c. But this is merely *one* experiment -- ResNet-18 trained on CIFAR-10 with 60% label noise. The reviewer was hoping for a more convincing theoretical explanation for this. \n\nThe third contribution is the observation that SAM even improves generalization for linear models. This is a surprising phenomenon, but the explanation is not clear. The authors substantiate this not through theory, but through a toy example in in Fig. 4. It is not clear whether one can extrapolate the observations from this linear model to large-scale datasets. Again, I was hoping for a more theoretical explanation, since this is an \"Understanding\" paper. ", "summary_of_the_paper": "This is an ambitious paper that seeks to explain why SAM works the way it does. First, the authors try to justify the better generalization of SAM over SGD on deep networks. Next, the authors discuss why SAM is robust to noisy labels, and argue why SAM can improve generalization even for linear classifiers. Finally, the authors discuss how to further improve SAM by leveraging a gradient reweighting interpretation and combining with a robust loss. ", "summary_of_the_review": "The aims of this paper are laudable, but the explanations for short of being convincing. I would suggest the authors, in a new version of the paper, to focus solely on one aspect of SAM, and explain it fully (using theoretical results and comprehensive experiments), and comparing it to vanilla methods. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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