Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction
Authors: Kaifeng Lyu
Zhiyuan Li
Sanjeev Arora
Venue: NeurIPS 2022 Accept (2022)
Keywords: normalization
sharpness
gradient descent
scale-invariance
theoretical analysis
edge of stability

Abstract: Normalization layers (e.g., Batch Normalization, Layer Normalization) were introduced to help with optimization difficulties in very deep nets, but they clearly also help generalization, even in not-so-deep nets. Motivated by the long-held belief that flatter minima lead to better generalization, this paper gives mathematical analysis and supporting experiments suggesting that normalization (together with accompanying weight-decay) encourages GD to reduce the sharpness of loss surface. Here ``sharpness'' is carefully defined given that the loss is scale-invariant, a known consequence of normalization. Specifically, for a fairly broad class of neural nets with normalization, our theory explains how GD with a finite learning rate enters the so-called Edge of Stability (EoS) regime, and characterizes the trajectory of GD in this regime via a continuous sharpness-reduction flow.

Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction
Kaifeng Lyu
Zhiyuan Li Department of Computer Science Princeton University fklyu,zhiyuani arooaa)css princeton.eeii prrtettta
Sanjeev Arora
Abstract
Normalization layers (c.g., Batch Normalization, Layer Normalization) were intro- duced to help with optimization difficulties in very deep nets, but they clearly also help generalization, even in not-so-deep nets. Motivated by the long-held belief that flatter minima lead to better generalization, this paper gives mathematical analysis and supporting experiments suggesting that normalization (together with accompanying weight-decay) encourages GD reduce the sharpness of loss sur- face. Here "sharpness" is carefully defined given that the loss is scale-invariant, a known consequence of normalization. Specifically, for a fairly broad class of neural nets with normalization, our theory explains how GD with a finite learning rate enters the so-called Edge of Stability (EoS) regime, and characterizes the trajectory of GD in this regime via a continuous charpness-reductio flow.
1 Introduction
Training modern deep neural nets crucially relies on normalization layers to make the training process less sensitive to hyperparameters and initialization. The two of the most popular normalization layers are Batch Normalization (BN) [55] for vision tasks and Layer Normalization (LN) [9] for language tasks. Recent works also proposed other normalization layers aiming for better performance, most no- tably including Group Normalization (GN) [120), Weight Normalization (WN) [102], Scaled Weight Standardization (SWS) [97, 53, 14], etc. Most normalization layers amount reparametrization of the neural net so that the loss becomes invariant to the scale of most parameters, and with a minor change, to all parameters: L(ew) L(w) for all scalings
[55, 7, 77J. The current paper assumes this scale-invariance for all parameters and analyzes the trajectory of gradient descent with weight decay (WD):
w++1 + (1 , [(w.).
The use of WD is a common practice that has been adopted in training state-of-the-as neural nets, such as ResNets [46, 47] and Transformers [29, 15]. Previous ablation studies showed that adding WD to normalized nets indeed leads to better generalization [126, 72, 125]. More notably, Liu al. [83] conducted experiments of training ResNets initialized from global minima with poor test accuracy, and showed that SGD with WD escapes from those bad global minima and attains good test accuracy. In contrast, training with vanilla SGD yields significant generalization degradation.
In the traditional view, WD regularizes the model by penalizing the parameter norm, but this may appear nonsensical for scale-invariant loss because one can scale down the norm arbitrarily without changing the loss value. However, the scale of the parameter does matter in backward propagation, and thus WD can affect the training dynamics. In particular, simple calculus shows wll
) & T and [2[(w) = 1 V2L( [ ) x TT so WD is in effect trying to enlarge the gradient and Hessian in training. This makes the training dynamics very different from unnormalized nets and requires revisiting classical convergence analyses [77, 78, 84, 80).
V((w) = | VL(
w w
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

train loss
spherical sharpness effective
A((VE((U 2 LR
Top-10 singular values of the recovered matrix
test loss
2
10a
20
30
10a
10
10
10a
0-
10k
20k
30k
0
10k
20k
30k
0
10k
20k
30k
10k
20k
30k
steps
steps
steps
steps (d)
(a)
(b)
(c)
Figure I: Experiment overparameterized matrix completion with Batch Normalization. Given 800 (32%) entries of rank-2 matrix M E R50x50, use GD+WD optimize the loss L(U, V) == T (BN
Mr,))² where U, V p000000 (thus no explicit constraint rank). Starting
from step ~ 2k. spherical sharpness drops significantly (b), which encourages low-rank (d) and causes the test loss (MSE of all entries) to decrease from 1.12 to 0.013 (a). See also Appendix P.I.
train
spherical sharpness
A A[W))((w) 2/ LR
test acc
2 effective LR
train loss
100
105
300
10"
75
200
10
50
100
10-2
25
0
25k 50k
75k
25k 50k
75k
25k
50k
75k
25k 50k
75k
steps
steps (b)
steps
steps
(a)
(c)
(d)
Figure 2: In training smooth and scale invleiina VGG-11 on CIFAR- 10 with (full-batch) GD+WD, the spherical sharpness keeps decreasing and the test accuracy keeps increasing. BN is added after every linear layer to ensure scale-invariance. 100% training accuracy is achieved after ~ 680 steps (dotted line), but the training continues for ~ 47k steps, the spherical sharpness keeps decreasing (b) and the test accuracy increases from 19 to 72.0% (a). Then the training exhibits destabilization but the test accuracy is further boosted to 84.3%. Removing either of BN or WD eliminates this phenomenon; see Appendices P.4 and P.S.
The current paper aims to improve mathematical understanding of how normalization improves generalization. While this may arise from many places, focus studying the dynamics of (full- batch) GD (1), which is a necessary first step towards understanding SGD. We show that the interplay between normalization and WD provably induces an implicit bias to persistently reduce the sharpness of the local loss landscape during the training process, which we call the cearpness-reduction bias.
It is long believed that flatter minima generalize better [50, 63, 95], but the notion of sharpness/Ratness makes sense only it is carefully defined in consideration various symmetries in neural nets. One of the most straightforward measures of sharpness is the maximum eigenvalue of Hessian, namely (v ((w)) But for normalized nets, this sharpness measure is vulnerable to weight rescaling, because one can scale the weight norm to make minimizer arbitrarily flat [31]. Also, this sharpness measure may not decrease with the number of training steps: an empirical study by Cohen et al. [24] shows that for various neural nets (including normalized nets), GD has an overwhelming tendency to persistently increase λ₁ (((,) until it reaches the Edge of Stability (EoS) regime, regime where \₃ (V² ((w:)) stays around 2/ (i) the learning rate). See also Section 6 and Figure 2c.
1.1 Our Contributions
The sharpness measure we use in this paper takes care of the scale-invariane, in normalized nets. We are motivated by our experiments on matrix completion (with BN) and CIFAR- 10, where our sharpness measure decreases as the training proceeds, and the generalization improves accordingly: see Figures and 2. We note that techniques from previous works [92, 95, 37] can be easily adopted here to establish a PAC-Bayes bound on the test error, where our sharpness measure appears as an additive term (see Appendix C).

---

Definition 1.1 (Spherical Sharpness), For a scale-invariam loss ((w) (i.e., [(ew) = ((w) for all c >> 0), the spherical sharpness at w IR P is defined by X (V² (( | )), of the Hessian matrix after projecting w onto the unit sphere.
the maximum eigenvalue
Based on Definition 1.1, we study the aforementioned sharpness-reductin bias in training normalized nets with GD+WD (defined in (I)). For constant learning rate f) and weight decay 2, we can rewrite this rule equivalently as Projected Gradient Descent (PGD) on the unit sphere with adaptive learning rates, Oc+1 + O0 - Ti. V (OO)), where O.- :- Tiw==la is the direction of wo, and ît. is the "effective" learning rate at step t (see Lemma 3.1). We call v7, adaptive because it can be shown to resemble the behaviors of adaptive gradient methods (e.g., RMSprop [49]): iie increases when gradient is small and decreases when gradient is large (Figure 3). Our main contributions are as follows:
wt
1. After 0e reaches a point near the manifold of minimizers of C. we theoretically show that the effective learning rate ij increases until GD enters a regime where 2/ roughly equals to the spherical sharpness (or equivalently 2/ R X1 (V² (V²L(m)))) namely the EoS regime (Section 4.1).
2. In the EoS regime, we show that for GD with a small (but finite) learning rate, Or oscillates around the manifold and moves approximately along sharpness-reductioon flow, which is gradient flow for minimizing spherical sharpness on the manifold (with gradient-dependent learning rate) (Section 4.2).
3. As an application of our theory, we show that for linear regression with BN, GD+WD finds the minimizer that corresponds to the linear model with minimum weight norm, which looks surprisingly the same as the conventional effect of WD but is achieved through the completely different sharpness-reductiion mechanism (Section 5).
4. We experimentally verified the sharpness-reduction phenomenon predicted by our theorem and its benefits to generalization CIFAR-10 with VGG-11 and ResNet-200, as well matrix completion with BN (Appendix P).
5. We generalize our theoretical results of charpness-reductionn bias to broader class of adaptive gradient methods, most notably a variant of RMSprop with scalar learning rate (Appendix B).
Technical Contribution. Our proof technique is novel and may have independent interest to the ML community. The main challenge is that we need to analyze the implicit bias of GD in the EoS regime which crucially relies on step size being finite - this is in sharp contrast to many previous works on implicit bias of GD [107, 106, 87, 59, 43, 42, 76, 100, 4, 22, 79, 88, 101, 108, 38) where the same bias exists at infinitesimal LR. Our analysis is inspired by a previous line of works [13, 25, 81] showing that label noise can drive SGD move on the minimizer manifold along the direction of minimizing the trace of Hessian. We borrow a few lemmas from those analyses, but the overall proof strategy is very different because our setting does not even have any stochastic gradient noise. Instead, we connect the dynamics in the EoS regime to power methods and show that GD oscillates around the minimizer manifold. This oscillation then becomes a driving power that pushes the parameter to move on the manifold. Finally, we analyze the speed of this movement by modeling two key parameters of the dynamics as a 1-dimensional Hamiltonian system (Figure 6). To the best of our knowledge, we are the first to provide theoretical proof for a sharpness measure to decrease during the standard GD training, without any additional regularization (e.g., label noise [13, 25, 81)) and without involving uncommon variants of GD (e.g., normalized GD or non-smooth wrappings on the loss function [8]).
2 Related Works
Sharpness and Generalization. It has been long believed that flat minima generalize better [50]. Several empirical studies [63, 74, 117. 57] verified the positive correlation between flatness and generalization. Neyshabur et al. [95] justiffie this via PAC-Bayes theory [92]. Several other theoretical papers explored the generalization properties of flat minima specifically for two-layer nets [13, 94, 44, 81,30] and deep linear nets [93]. Jiang et al. [60] conducted extensive experiments for all existing generalization measures to evaluate their correlation and causal relationships with generalization error, concluding that sharpness-bases measures perform the best overall. In light of this, Foret et al. [37] proposed SAM algorithm to improve the generalization by minimizing the sharpness. Despite so many positive results on sharpness-basd based measures, a common issue of many works is that the measures may suffer from sensitivity to rescaling of parameters in deep nets [31]. Another issue is that the minima could lie in asymmetric valleys that are flat on one side and sharp on the other [45].
3

---

Understanding Normalization Layers. The benefits of normalization layers can be shown in various aspects. series of works studied the forward propagation of deep nets at random ini- tialization, showing that normalization layers stabilize the growth of intermediate layer outputs with depth [14, 10, 28], provably avoid rank collapse [26] and orthogonalize representations [27]. Although these works mainly focused on BN [55], Lubana et al. [85], Labatie et al. [67] provided thorough discussions on the applicabiliit of these arguments to other normalization layers. is also believed that BN has a unique regularization effect through the noise in batch statistics [86, 111, 104).
Several other works argued that normalization layers lead to a smoothening or preconditioning effect of the loss landscape [103, 12, 39, 61, 82, 68], which may help optimization. By analyzing the training dynamics, Arora et al. [7] rigorously proved that normalization yields an auto-tuning effect of the effective learning rate 1/. which makes the asymptotic speed of optimization much less sensitive to the learning rate and initialization. In linear regression settings, Cai et al. [16], Kohler et al. [65] showed that training with BN leads to faster convergence rate; Wu et al. [1 19] studied the implicit regularization effect of WN [102]. For two-layer nets with normalization, Ma and Ying [90] derived mean-field formulation of the training dynamics; Dukler et al. [33] proved convergence rate via NTK-based analysis. The current paper focuses on the interplay between normalization and WD during training, whereas all the above works either do not analyze the dynamics or assume no WD.
Interplay Between Normalization and WD. A common feature of normalization layers (including but not limited to BN, WN, LN, GN, SWS) is that they make the loss invariant to the scale of layer weights. In presence of both scale-invariance and WD, training dynamics can go out of the scope of the classical optimization theory, e.g., one train the net to small loss with learning rates exponentially increasing [77]. A series of works investigated into the interplay between normalization and WD) and argued that the training dynamic with SGD eventually reaches an "equilibrium" state, where the parameter norm [78, 113, 21] and the size of angular update [1 [114] become stable. Li et al. [78]. Wang and Wang [115] provided empirical and theoretical evidence that the function represented by the net also equilibrates to a stationary distribution that is independent of initialization. This could be related to Liu et al. [83]'s experiments on the ability of SGD with WD to escape from bad initialization, but it remains unclear why the generalization should be good at the equilibrium state. In this paper, we focus on (full-batch) GD, which the most basic and important special case of SGD.
3 Preliminaries
Let SD-1 := 10 PER' 10 = 1} be the unit sphere equipped with subspace topology. We say loss function L(w) defined on RDD {0] is scale-invarian if L(cw) = L(w) for all c 0. In other words, the loss value does not change with the parameter norm. For a differentiable scale- invariant function L(w). the gradient is homooeeouus and it is always perpendicular to w. i... VL(cw) = c (((w) for all > 0 and (VL(w), w) = 0 (see Lemma D.1).
The focus of this paper is the dynamics of GD+WD on scale-invariant loss. (1) gives the update rule for learning rate (LR) r and weight decay (WD) Å. We 0, = wh T denote the projection of W; onto 8D-1 at step I. We write GD+WD on scale-invariant loss as specific kind of Projected Gradient Descent (PGD) and define the effective learning rale to be the LR în
(I (1-AA]][u; || that
appears in the update rule of PGD. This notion is slightly different from the effective learning rate defined in previous works [113, 52, 71, but ours is more convenient for our analysis.
Lemma 3.1. When the parameters w, are updated as (1), Og satisfies the following equation:
Or+1 = [[, +/. L(O.))
(2)
-1-5A\|:::B is called the effective learning rate at step i, and II: u projection operator that projects any vector onio the unit sphere.
where i
w
is the
4 GD+WD on Scale-Invariant Loss Functions
This section analyzes GD+WD (1) on a scale-invariant loss L(w), particular what happens after approaching a manifold of local minimizers. Section 4.1 analyzes the dynamics in the stable regime, where loss is guaranteed to decrease monotonically, and Theorem 4.2 suggests w, can get close to a local minimizer at some time to. We show that the effective LR keeps increasing after to, causing

---

GD+WD to eventually leave this stable regime and enter new regime which we call the Edge of Stability (EoS). In Section 4.2, we establish our main theorem, which connects the dynamics of w, in the EoS regime to sharpness-reduction flow.
4.1 GD+WD Eventually Leaves the Stable Regime
A standard step of analyzing optimization methods is do Taylor expansion locally for the loss function, and show that how the optimization method decreases the loss using a descent lemma. In case of scale-invariant loss functions, we use H (w) == ( E I to denote the Hessian matrix of L at w E PR and X (w)) == (H to denote the top eigenvalue of Hw)).
Lemma 4,1 (Descent Lemma). For scale-invariant loss L(w), at step t of GD+WDD we have
[(0,+1) - ((),) - -fr((1 īJ i max/ /2) V))
where X suPae (V is upper bound of spherical sharpness locally.
This descent lemma shows that the training loss (())) keeps decreasing as long as the effective LR he is smaller than 2/ 2/Amax. We call the regime of ît < 2/ /maxx as the stable regime of GD+WD. If de 2/x with small difference, then we call it as the Edge of Stability (EoS) regime. We remark that this condition for EoS regime is essentially the same as R 2/XH (w) in Cohen et al. [24]'s definition because f/t X f) X (w)); see Appendix G.3.
Fix an initial point wp E PR \ [0). Now we aim to characterize the dynamics of GD+WD when LR f and WD Ả are small enough. The convergence rate of GD+WD has been analyzed by Li et al. [80]. Here we present a variant of their theorem that bounds both the gradient and effective LR.
Theorem 4.2 (Variant of Theorem D.2, Li et al. [80]). Let L(w) be a ccale-invarian loss function and p2= sup (uup[VV[[(w)]]l w E 1 be the smoothness constant of L restricted on the unit
sphere. For GD+WD (1) with njλ S 1/2 and no S x²pa(1-pX) let To = 2RA
In
[woll
steps, there
p2
must exist 0 S S To such that [[ < 8x p2 and it S =1-2(1-0A))
Theorem 4.2 shows that for some In < To. [V. O(vi)) and too S x2
< 2 which
02
means 0t, is an approximate first-order stationary point of L on the unit sphere. This does not guarantee that Or, is close to any global minimizer, but in practice the training loss rarely gets stuck at non-optimal value when the model is overparameterized [70, 96, 71, 125]. We are thus motivated to study the case where Ot, not only has small gradient [[V2(0 >)3 S O(xi) but also is close to a local minimizer 0 E gD of C in the sense that 10,,, 11 S ((())) (assuming smoothness, the latter implies the former).
As the gradient is small near the local minimizer 0*, start- ing from step fo. the norm of w, decreases due to the effect of WD. See Figure 3a. Since the effective LR is inversely proportional to ||w.l1.. this leads to the effective LR to increase. Then Theorem 4.4 will show that the GD+WD dynamic eventually leaves the stable regime at some time I > lo. and enters the EoS regime where ît R 2/ 2/2/1xx-
(1 (1- MA)
AFL(W)
Wimt
Wesk
(a)
(b)
To establish Theorem 4.4, we need to assume that C satis- fies Polyak-Lojasiewiez (PL) condition locally, which is standard regularity condition in the optimization literature to ease theoretical analysis around a minimizer. Intuitively, PL condition guarantees that the gradient grows faster than quadratic function as we move a parameter O away from 0". Note that PL condition is strictly weaker than convexity as the function can still be non-convex under PL condition (see, e.g., [62]].
Figure 3: The norm of w. decreases when gradient is small and increases when gradient is large.
Definition 4.3 that L. satisfies SD-1 if for some neighborhood U C gD of YO U VC(() 2 μ. (C(0) - L(O))).
Condition). For scale-invariant loss L(w) and μ > O. we say condition (or PLPL.) locally around a local minimizer 0* on
5

---

Theorem 4.4. Let L(w) be C² -m-oohh scale-invariant loss that satisfies μ-PL around a local
minimizer 0 on the unit sphere, and P2 == sup( sup[[V
w 1---i J. For GD+WD on [(w) with learning rate î and weight decay X, if at some step to. 1 0 ll Σ O((Ai)
and nh. S 2. < Xi1or. and if Xn is small enough, then there exists a time t > to such that 00,, 0 1= ((2))))/2 and fit -x (((
2
4.2 Dynamics at the Edge of Stability
From the analysis the previous subsection, we know that 0 can get close to a local minimizer 0* and enter the EoS regime some step 1,. But what happens after t
Figure 4 gives a warm-up example on 3D scale-invariant loss C R {0} + R. where the black line mani- fold I" consisting of all the minimizers. In training with GD+WD, 0₂ first goes close
3D
local minimizer Co, then Theorem 4.4 suggests that WD causes the effective LR to steadily increase until the dynamic enters the EoS regime. Now something interesting happens O, moves bit away from Çu and starts to oscillate around the manifold r. This oscillation is not completely perpendicular to I' but actually forms a small angle that pushes O, to move downward persistently until Og approaches the minimizer S. denoted the plot.
flattsst
-1
For a general ceale-invariant loss L: C + R, which minimizer does O, move towards? In this work, we consider the setting where there is manifold 7' consisting only of local minimizers (but not necessarily all of them). We show that 0g always oscillates around the manifold once it approaches the manifold and enters the EoS regime, and meanwhile 0, keeps moving in direction of reducing spherical sharpness.
1
Figure 4: The trajectory of 0, on a 3D scale-invarian loss function. Darker color means lower loss on the unit sphere, and points in the black line are minimizers (see Appendix F). In the end, 0g approaches the flattest one (red star).
4.2.1 Assumptions
Now we formally introduce our main assumption on the local minimizer manifold r. Assumption 4.5. The loss function C : \ {0} + IR Cmmsoooth and scale-invariant. I' a C²-smooth, (Dr -)ddimensional submanifold of D for some 0 < Dr < D, where every 0 E I is a local minimizer of on SD and rank (())) = Dr- Dr-
Scale-invariance has become a standard assumption in studying neural nets with normalization layers [77, 78, 84]. For VGG and ResNet, the scale-invariance can be ensured after making minor changes to the architectures (see Appendix Q. The training loss L may not be smooth if the activation is ReLU, but lately it has become clear that differentiable activations such as Swish [98], GeLU [48] can perform equally well. Swish is indeed used in our VGG-11 experiments (Figure 2), but ResNet with ReLU activation also exhibits a sharpness- reduction bias empirically (see Appendix P.2).
For any local minimizer O E Г, the eigenvalues X (0) must be non-negative. And ( = 0 for all D Dr < < D, since I' is of dimension DT- 1. The condition rank H (())
D Dr ensures that the Hessian is maximally non-degenerate on l', which also appears as a key assumption previous works [81, 8, 35). This condition simplifies the calculus on I' in our analysis as it ensures that the null space of the matrix H H0) equals to the tangent space of I' at 0 E l'. It is also closely related to PL condition (Definition 4.3) as Assumption 4.5 implies that L()) satisfies PL (for some 0) locally around every 0 e I' on the unit sphere (Arora et al. [8], Lemma B.3).
To ease our analysis, we also need the following regularity condition
ensure that the largest cigenvalue is unique. In our experiments, sharpness reduction happens even when the multiplicity of the top eigenvalue more than 1, but we leave the analysis of that case to future work.
Assumption 4.6. For all 0 e r. ( (0). That is, the top eigenvalue of H (0) is unique.

---

4.2.2 Main Theorem
First, we define Yiu == =iA the intrinsic learning rate (name from Li et al. [78]) for convenience. As suggested in Theorems 4.2 and 4.4, 0, can get close to a local minimizer and be in the EoS regime at some step f1: if Co is the local minimizer, then |0o, Coll2 Onh and ît. In our main theorem, we start our analysis from step L while setting 4 = 0 WLOG (otherwise we can shift the step numbers). We connect GD+WD in the EoS regime to the following gradient flow (3) on the manifold minimizing spherical sharpness (with gradient-dependen learning rate), and show that one step of GD+WD tracks a time interval of length Tha in the gradient flow.
X- O(hin") )
d
2 log (F(TT) S(T) = 4 V log (S(T)))
(()) = So E
(3)
dr
Here we use the notation V (() for any R: RD - R to denote the projection of ((()) onto the tangent space (T)
r. ((T) reduces sharpness as it moves in direction of the negative gradient of log ([(T) on r. A simple chain rule shows how fast the spherical sharpness decreases:
d dt
2 V log (C(T))
2 Vr log (F((()) --2
for small gradient; for large gradient.
log ((((T)) = 4 + I log (C(T))
Note that it is not enough to just assume that 0, is close So- If 0, So holds exactly, then the subsequent dynamic of w, described by w, (1 -r)'' wo with direction unchanged. There are also some other bad initial directions of wo that may not lead to the blarpness-reduction bias. This motivates us to do a smoothed analysis for the initial direction: the initial direction is Ç with tiny random perturbation, where the perturbation scale is allowed to vary from exp( tm -o()) o(1)) to Yhin 1/2-o(11)
and we show that a good initial direction is met with high probability as Yhin - 0.' Alternatively, one can regard it modeling of the tiny random noise in GD+WD due to the precision errors in floating-poin operations. See Figure 5b; the training loss can never be exactly zero in practice.
Initialization Scheme. Given a local minimizer Ço E I', we initialize wo E RRP {0} as follows: Cott draw & (N from Gaussian and set the direction of wn T<o+El2
where on can take
any value in (exp(-n/h) Vmn
=(())) Tha )/u 1/2--(1)); then set the parameter norm ||uoll2 to be any value that
satisfies i0 TPiCoo
2
S Vhu
1/2-0(1), where ijo = (1-0X)][mo1B the effective LRR for the first step.
Theorem 4.7. Under Assumptions 4.5 and 4.6, for GD+WD (1) with sufficiently small intrinsic learning rate ;= niS. if follow the above initialization scheme for some Ço E I, then with probability 1 - Om (0 112))(1)), the trajectory of 0, Tw:ll= approximately tracks sharpness- reduction flow Ç [0, + I that starts from Çu and evolves as the ODE (3) up to time T (if solution exists), in the sense that 110,- ((trmn)l2 O( (//44401))) ) for all 0 < S T/Tu-
Remark 4.8 (Magnitude of Oscillation). As suggested by Figure 4, O, actually oscillates around the manifold. But according to our analysis, the magnitude of oscillation is as small as O (12220((1) so it is absorbed into final bound O 1/4-o(3)) for the distance between O and ((rraa).
4.2.3 Proof Idea
Throughout our proof, we view GD+WD for w, as PGD for 0 with effective LR îj. (Lemma 3.1). To track O, with ((t7mn) for each step t, we construct a local minimizer Φ; E I' that serves as the "projection" of O, onto the manifold I', in the sense that the displacement 2, := O, Φi is approximately perpendicular to the tangent space of I at Φi. Our entire proof works through induction. According the initial conditions, the dynamic is initially in the EoS regime: ||a:||| Σ //n
1/2-o(1)
and bū, 2/ (xx)) < <n / 112-o(1) at t = 0. In our induction, we maintain the induction hypothesis that these two EoS conditions continue hold for all 2 O.
Here 7m -(() can be constant, (log((// (l/n))),, or O(polylog(1, (onylogg(//ma) mn.)). but not 7 if c > 0 is a constant. As mentioned later, this need for random initialization is very similar to the one needed in power method for computing eigenvalues.
7

---

[|] s ||szlla
test loss
spherical sharpness
h, is even)
174y di.lla
train loss
2 / effective LR
hy is odd)
1.00
10-1
4.8
10-7
4.6-
0.50
0.00
10-10
4.4
0.25
10-11
4.2
-0.02
0.00
4.0
0
10k 20k
30k
40k
1k
2k
3k
4k
5k
1k
2k
3k
4k
5k
1k
2k
3k
4k
5k
steps
steps (b)
steps (c)
steps (d)
(a)
Figure 5: Illustration of the oscillation and periodic hehaviors of GD+WD on linear regression with BN (see
Sections 4.2.3 and 5). The training loss decreases to R 10 14 in the first 1K steps and achieves test loss 0.26. Starting from step 1k. the dynamic enters the EoS regime. (a). The test loss decreases to 0. as distance
measure the flattest solution (M) decreases towards 0: (b). The training loss oscillates around
10 in
the EoS regime: (c). //vr switches back and forth between being smaller and larger than >i (db): (d). The parameter oscillates around the minimizer manifold along the top eigenvector direction, and the magnitude of oscillation |he rises and falls periodically.
Period- Two Oscillation. A key insight in our proof is that after few initial steps, 0, is oscillating around Φ, along the (O) directions, where vf(() (0) is a unit top eigenvector of H (0) and is
chosen a way that wf (0) is continuous on f'. More specifically, 2 = h of (b:) + O[1 (l2) for he := (x), of"( (Φ:)) The oscillation is of period 2: h4 0 when is even and he < 0 when t is odd. See Figure 5d for an example.
This oscillation can be connected to a power method for the matrix I - ny. H (.). In the EoS regime, we can approximate 0.+1 (when x, small) as 0(+1 OI, n VL().) IT H ($)) s 0, i): ( )x; by Taylor expansions of V L and II: RD (0) - SD-1 We can further show that Φ.+1 = Φ, due to our choice of projections. Then the connection to power method is shown below:
3t+1 & 0.+1 Φ. R (I ī H (o.))
By simple linear algebra, (0))) is an eigenvector of I - î/, H (bb), associated with eigenvalue
1 1- A (o))) ~ 1. The remaining eigenvalues are (1 - A/AA H (t)) 2=2- where ( ) is the i-th
largest eigenvalue of H (0:), and they lie in the range (-1, 1] since X x (Φ.) [0, A All (dr)). Using
similar analysis to power method, show that æ, quickly aligns to the direction of ((.)) after few initial steps, as the corresponding eigenvalue has approximately the largest absolute value." 2
To formally establish the above result, we need tiny initial alignment between æo and vt (do)) just as the initial condition in power method. This is where we need the initial random perturbation.
Oscillation Drives & to Move. This period-two oscillation is the driving power to push Φ to move on the manifold. The main idea here is to realize that the oscillation direction deviates slightly from the direction of = (Φ):) by using higher-ordet approximation. We specifically use the Taylor approximation to show that this deviation leads Φe to move slightly on I: after each cycle of oscillation, Φ1+2 R Φ 44ξ Vr log (Ør)) + Om 1.5-0(1)), which resembles two steps of gradient descent on / to minimize the logarithm of spherical sharpness with learning rate 2h,-
Periodic Behavior of h, and i/. It remains to analyze the dynamics of h, so that we can know how fast the sharpness reduction is. Our analysis inspired by an empirical study from Lobacheva et al. [84], which reveals a periodic behavior of gradients and effective learning rates in training normalized nets with weight decay. In our theoretical setting, we capture this periodic behavior by showing that he and îtt do evolve periodically. See Figures 5c and 5d for an example.
The key is that 7e changes as an adaptive gradient method: îi: increases when gradient is small and decreases when gradient is large (due to the effect of WD; see Figures 3a and 3b), and in our case the gradient norm scales as hhe since (L.).) h4 (b) ) ((.)). By the power method approximation,
2 *Our construction of Φb, ensures that ay only has small overlap with the 1-eigenspace of I - ij. (p)), so 2c can only align (cb).
8

---

h4+2 = (1- (o:))) he, so |hg| decreases when de < 2/ (6:). But |hg] cannot decrease forever, since ît. increases when [hg is sufficiently small. When nt rises to over 2/ (Φr), |hy] changes from decreasing to increasing according to our approximation. But h, cannot increase indefinitely either, since ft. decreases when [hg] is sufficiently large. A period finishes when ij. < ( holds again.
In our theoretical analysis, we connect this periodic behavior with I-dimensional Hamiltonian system (see Appendix H.2), and show that 2 in each step can be approximated by its average value in the period without incurring a large error. Further calculations show that this average value is approximately 4+ Vr log (Citmm))llla the learning rate in the flow (3) multiplied with V/in- We can therefore conclude that each step of Φ. (or 0+) tracks a time interval of 7/nn in the flow.
27h
Extensions. We note that this periodic behavior not limited to GD+WD on scale-invariant loss, since the above intuitive argument holds as long as the effective LR changes adaptively with respect to gradient change. Based on this intuition, an important notion called Quasi-RMSprop scheduler is proposed. For a PGD method, learning rate scheduler is rule for changing the effective LR in each step, and Muasi-RMSpropp is a specific class of schedulers we define, including the way that the effective LR changes in GD+WD is done in a unified way that works as long as the effective LR changes in each step according to scheduler. As by-product, a similar theorem can be proved for GD (without projection) on non-scale-invariant loss if the LR changes as a Quasi-RMSprop in each step. For example, we can extend our analysis R.Sprop with scalar learning rate. See Appendix B.
scale-invariant loss (if viewed PGD). Our proof
5 Case Study: Linear Regression with Batch Normalization
In this section, we analyze the GD+WD dynamics on linear regression with Batch Normalization (BN), as simple application of our theory. Let {(x, 31)) be a dataset, where æ; E IR and y: E IR are inputs and regression targets. We study the wer-pparameterized case where d > n, and we assume that the regression targets are generated by an unknown linear model.
classic linear model is parameterized by (w. b) E Rdd x R and outputs w ToTa x + b given input æ. but now add BN to the output. More specifically, consider
coraalnormalized linear model ((x; (x; w, 7, 3) == 7 w -- + 3, where 111 ai are the mean and standard deviation of (w a ! over the whole d and the bias term b is cancelled out due to BN. Note that ((x; w, w,y, 8) is still a linear function with respect to æ. Let fxx E Rdd and Σx E R be the mean and covariance of the input data far H= Then ((x; w; 7: 33 can be rewritten as:
01
((:; w. 3) = u T x + b,
where w :0:=10m wl/Ww/.
b: B - ~ Pxx-
(4)
No matter how is set, the output mean and variance of + always (3 and 722 To simplify our analysis, we fix 3, to be non-trainalee trainiaai constants so that the mean and variance of 4's output match with those of [y that is, we set 33 Hy and 7 By to be the mean and standard deviation of y over the whole dataset. Then the training loss is L(w) :- +.2 Eie(n) (PE w, w, -)))
(2(2;;
Theorem 5.1. In our setting of linear regression with BN, the sharpness- reduucton flow C defined in (3) converges to the solution w" E Sd that minimizes sharpness X >l(w") on I, regardless of the initialization. Moreover, the coefficients (zd, b) associated with w" (defined in (4)) are the optimal solution of the following constrained optimization problem (M):
min
S.t.
w x3 b Vo:
Vi E [n].
(M)
At first sight the result may appear trivial because the intent of WD is to regularize L²-norm. But this is deceptive because in scale-invariant nets the regularization effect of WD is not explicit. This result also challenges conventional view of optimization. GD is usually viewed as a discretization of its continuous counterpart, gradient flow (GF), and theoretical insight for the discrete update including convergence rate and implicit bias is achieved by analyzing the continuous counterpart (See Appendix for a list). However, GF does not have the same charpness-reduceee discussed in [77], adding WD only performs a rime-rescaling on the GF trajectory scale-invariant loss, but does not change the point that GF converge to if we project the trajectory onto the unit sphere. One can easily show that GF may converge to any zero-loss solution, but no matter how small
bias as GD. As
Note that the batch size n here
running full-batch GD

---

LR is. GD exhibits the reduuciion bias towards the optimal solution of (M). To our best knowledge, this result is the first concrete example where even with arbitrarily small LR, GD can still generalize better than GF under natural settings.
6 Discussion
Experimental Verification of Sharpness Reduction. Besides Figures and 2, Appendix P.1 provides additional matrix completion experiments with different data size, and Appendix P.2 provides CIFAR-10 experiments with ResNet-20. all these experiments, we observed that GD continues to improve the test accuracy even after fitting the training set, and this phenomenon is correlated with the decreasing trend of spherical sharpness. See also Appendix P.3 for the validation for the periodic behavior we analyze in theory.
Ablation Studies Normalization and Weight Decay. Our theoretical analysis crucially relies on the interplay between normalization and WD to establish the searpness-reductio flow. We also conducted ablation studies on normalization and WD highlight the importance of this interplay. First, if normalization is removed, the spherical sharpness becomes undefined, and we do not know if GD implicitly minimizes any sharpness measure. But even if a similar measure does exist, it cannot be strongly related to generalization, because we can verify that the test accuracy becomes very bad without normalization (56.8% on CIFAR-10, Figure 14), and continuing training after fitting the training set no longer improves test accuracy. Second, if WD is removed, the analysis in Arora et al. [7] guarantees convergence
stable regime, and we can verify that the spherical sharpness and test accuracy stop changing when the loss is small. The final test accuracy is stuck at 66.4% (Figure 15), whereas training with WD leads to 84.3%.
Explaining the Progressive Sharpening and EoS Phenomena. Cohen et al. [24] conducted ex- tensive empirical studies on the dynamics of GD in deep learning (without weight decay), formally Wx+1 < w. V [(w:). They observed the progressive sharpening phenomenon: À (V² [(w:)) tends to increase so long as it is less than 2/ Then they observed that the training typically enters the EoS regime, which they define 2/ and (2) the training loss f(w:) goes up and down over short timescales, yet still decreases in the long-term run. A recent research trend focuses on explaining the progressive sharpening and EoS phenomena [1, 91, 8, 18). Our work corresponds to an important special case where L(w) is
regime that (1) (VV2 hovers right at, or just above
scale-invariant loss with L [e-reuularization, namely [(w) + 2 1|w By analyzing the interplay between normalization and WD, the first part of our results (Section 4.1) attributes progressive sharpening norm change, and the second part (Section 4.2) justifies in theory that the training can make progress in the EoS regime. See Appendix G.3 for more discussion.
Conclusions and Future Work
We exhibited settings where gradient descent has an implicit bias to reduce spherical sharpness in training neural nets with normalization layers and weight decay, and we verified experimentally this sharpness- reduuctin- bias predicted by theorem well as its generalization benefit CIFAR- 10.
Our theoretical analysis applies to dynamics around a minimizer manifold and requires a small (but finite) learning rate so that we can show that the parameter oscillates locally and approximately tracks a sharpness-reduccion flow. We note that in practice a decrease in spherical sharpness observed even with moderate LR and even before getting close to minimizer manifold. Explaining these phenomena is left for future work. Now we list some other future directions. The first to generalize our results to SGD, where the sharpness measure may not be the spherical sharpness and could depend on the structure of gradient noise. Second, to understand the benefit of reducing spherical sharpness on specific tasks, e.g., why does reducing spherical sharpness encourage low-rank on matrix completion with BN (Figure I)? Third, to study sharpness- reduction bias for neural net architectures that are not
on all parameters (e.g., with certain unnormalized layers).
Acknowledgements
This work funded by NSF, ONR, Simons Foundation, DARPA and SRC. ZL. is also supported by Microsoft Research PhD Fellowship.
10

---

References
[1] Kwangjun Ahn, Jingzhao Zhang, and Suvrit Sra. Understanding the unstable convergence of gradient descent. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 247-257. PMLR, 17-23 Jul 2022.
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in over- parameterized neural networks, going beyond two layers. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Bus E. Fox, and R. Garnett, editors, Advances in Neural Informa- tion Processing Systems, volume 32. Curran Associates, Inc., 2019.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over wver-parametciizatoon In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 242-252 PMLR, 09-15 Jun 2019.
[4] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Bus Buc. E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 7411-7422. Curran Associates, Inc., 2019.
[5] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322- 332.. PMLR, 2019.
[6] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Informa- tion Processing Systems 32, pages 8139-88 8148. Curran Associates, Inc., 2019.
[7] Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis of auto rate-tuning by batch normalization. In International Conference Learning Representations, 2019.
[8] Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge of stability in deep learning. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 948-1024. PMLR, 17-23 Jul 2022.
[9] Jimmy Lei Ba. Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.0644 2016.
[10] David Balduzzi, Marcus Frean, Lennox Leary, J. P. Lewis, Kurt Wan-Duo Ma, and Brian McWilliams. The shattered gradients problem: If resnets are the answer, then what is the question? In Doina Precup and Yee Whye Tch, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 342-350. PMLR, 06-11 Aug 2017.
[11] David Barrett and Benoit Dherin. Implicit gradient regularization. International Conference Learning Representations, 2021.
[12] Johan Bjorck, Carla Gomes, and Bart Selman. Understanding batch normalization. arXiv preprint 1806.
2018
[13] Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an omstein-uhlenbel like process. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 483-513. PMLR, 12-12 Jul 2020.
[14] Andrew Brock, Soham De, and Samuel I. Smith. Characterizing signal propagation to close the performance gap in unnormalized resnets. In International Conference on Learning Representations, 2021.

---

[15]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[16] Yongqiang Cai, Qianxiao Li, and Zuowei Shen. A quantitative analysis of the effect of batch normalization gradient descent. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 382-890. PMLR, 09-15 Jun 2019.
[17] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-But E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[18] Lei Chen and Joan Bruna. On gradient descent convergence beyond the edge of stability. arXiv preprint arXiv:2206.0417 2022.
[19] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much ver-pprrameterization is sufficient to learn deep ReLU networks? In International Conference on Learning Representa- tions, 2021.
[20] Yuejie Chi, Yue M. Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20):5239-5266 2019. doi: 10.110///S2200199372222
[21] Vitaliy Chiley, lya Sharapov, Atli Kosson, Urs Koster, Ryan Reece, Sofia Samaniego de la Fuente, Vishal Subbiah, and Michael James. Online normalization for training neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[22] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338. PMLR, 2020.
[23] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnet,, editors, Advances in Neural Information Processing Systems 32, pages 2937-2947, Curran Associates, Inc., 2019.
[24] Jeremy Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2021.
[25] Alex Damian, Tengyu Ma, and Jason D Lee. Label noise SGD provably prefers flat global minimizers. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances Neural Information Processing Systems, volume 34, pages 27449-27461. Curran Associates, Inc., 2021.
[26] Hadi Daneshmand, Jonas Kohler, Francis Bach, Thomas Hofmann, and Aurelien Lucchi. Batch normalization provably avoids ranks collapse for randomly initialised deep networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18387-18398. Curran Associates, Inc., 2020.
[27] Hadi Daneshmand, Amir Joudaki, and Francis Bach. Batch normalization orthogonalizes representations in deep random networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
12

---

[28] Soham De and Sam Smith. Batch normalization biases residual blocks towards the identity function deep networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19964-19975. Curran Associates, Inc., 2020.
[29] Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT:
Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguis- tics: Human Language Technologies, Volume (Long and Short Papers), pages 4171-
4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 111888//1//1911160 1423.
[30] Lijun Ding, Dmitriy Drusvyatskiy, and Maryam Fazel. Flat minima generalize for low-rank matrix recovery, arXiv preprint arXiv:2203. 03756, 2022.
[31] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1019-1028. PMLR, 06-11 Aug 2017.
[32] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning, pages 1675-1685. PMLR, 2019.
[33] Yonatan Dukler, Quanquan Gu, and Guido Montufar. Optimization theory for ReLU neural networks trained with normalization layers. Hal Daumé and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2751-2760. PMLR, 13-18 Jul 2020.
[34] K. J. Falconer. Differentiation of the Limit Mapping in Dynamical System. Journal of the London Mathematical Society, 52-27(2) 04 1983. ISSN 0024-6107. doi: 10. 10.11122 10.1112/jlms/2-221 27..3.55.
[35] Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research, 21(136):1-45 2020.
[36] Robert L. Foote. Shorter notes: Regularity of the distance function. Proceedings of the American Mathematical Society, 92(1):153-155 1984. ISSN 00029939, 10886826.
[37] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
[38] Rong Ge, Yunwei Ren, Xiang Wang, and Mo Zhou. Understanding deflation process in over- parameereeee tensor decomposition. Advances in Neural Information Processing Systems, 34, 2021.
[39] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2322-2441 PMLR, 09-15 Jun 2019.
[40] Justin Gilmer, Behrooz Ghorbani, Ankush Garg, Sneha Kudugunta, Behnam Neyshabur, David Cardoze, George Edward Dahl, Zachary Nado, and Orhan Firat. A loss curvature perspective on training instabilities of deep learning models. In International Conference on Learning Representations, 2022.
[41] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6151-6159, Curran Associates, Inc., 2017.
13

---

[42] Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems Curran Associates, Inc., 2018.
31, pages
[43] Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems,
31, 2018
[44] Jeff Z. HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. In Mikhail Belkin and Samory Kpotufe, editors. Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2315-2357, PMLR, 15-19 Aug 2021.
[45] Haowei He, Gao Huang, and Yang Yuan. Asymmetric valleys: Beyond sharp and flat local minima. Advances in neural information processing systems, 32, 2019.
[46] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings ofe IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[47] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision ECCV 2016, pages 630-645, Cham, 2016. Springer International Publishing. ISBN 978-3-319-46493-0.
[48] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs). arXiv preprint 17Xiv:6606008433 2016.
[49] Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a: Overview of mini-batch gradient descent. Technical report, 2012. URL ht / //www. ca. tor.oto...dduuoooo..............
httim//nncc3//////// heeee/////sside//eeeeeee /ttp////eeeeeetreeeeeeeeeeeeeeee 1ec...c...... pdf.
[50] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 91):1144, 1997.
[51] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[52] Elad Hoffer, Ron Banner, Itay Golan, and Daniel Soudry. Norm matters:
efficient and accurate normalization schemes in deep networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[53] Lei Huang. Xianglong Liu, Yang Liu, Bo Lang, and Dacheng Tao. Centered weight normaliza- tion in accelerating training of deep neural networks. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
[54] Hikaru Ibayashi and Masaaki Imaizumi. Exponential escape efficiency of SGD from sharp minima in non-stationary regime. arXiv preprint arXiv:2111.0400 1400044 2021.
[55] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 448-456, Lille, France, 07-09 Jul 2015. PMLR.
[56] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett, editors, Advances in Neural Information Processing Systems 31, pages 8571 1580. Curran Associates, Inc., 2018
14

---

[57] Stanistaw Jastrzębski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey, Three factors influencing minima in SGD. arXiv preprint arXiv:/711.04623, 2017.
[58] Stanislaw Jastrzebski, Maciej Szymczak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho, and Krzysztof Geras. The break-even point on optimization trajectories of deep neural networks. In International Conference on Learning Representations, 2020.
[59] Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 2020.
Curran Associates, Inc.,
[60] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where to find them. In International Conference on Learning Representations, 2020.
[61] Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. The normalization method for alleviating pathological sharpness wide neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[62] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewiez condition. In European Conference on Machine Learning and Knowledge Discovery in Databases Volume 9851, ECML PKDD 2016, pages 795-811, Berlin, Heidelberg, 2016. Springer-Verlag. ISBN 9783319461274, doi: 10.1007/ 978-3-319-46122-1555
[63] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
[64] Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does SGD escape local minima? In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2698-2707. PMLR, 10-15 Jul 2018
[65] Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann, Ming Zhou, and Klaus Neymeyr. Exponential convergence rates for batch normalization: The power of length- direction decoupling in non-convex optimization. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 806-815, PMLR, 16-18 Apr 2019.
[66] Lingkai Kong and Molei Tao. Stochasticity of deterministic gradient descent: Large learning rate for multiscale objective function. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2625-2638. Curran Associates, Inc., 2020.
[67] Antoine Labatie, Dominic Masters, Zach Eaton- and Carlo Luschi. activations to match batch normalization while removing batch dependence. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages (6990-17006 Curran Associates, Inc., 2021.
[68] Susanna Lange, Kyle Helfrich, and Qiang Ye. Batch normalization preconditioning for neural network training. Journal of Machine Learning Research, 23(72): 2022.
[69] Beatrice Laurent and Pascal Massart. Adaptive estimation quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
15

---

[70] Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1246-1257, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
[71] Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael I Jordan, and Benjamin Recht. First-order methods almost always avoid saddle points. arXiv preprint arXiv:1710.07406, 2017.
[72] Aitor Lewkowyez and Guy Gur-Ari. On the training dynamics of deep networks with L_2 regularization. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 4790-4799. Curran Associates, Inc., 2020.
[73] Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint urXiv:2003.0222 2020.
[74] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 31, 2018.
[75] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[76] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over- parameterized matrix sensing and neural networks with quadratic activations. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 2-47. PMLR, 06-09 Jul 2018
[77] Zhiyuan Li and Sanjeev Arora. An exponential learning rate schedule for deep learning. In International Conference on Learning Representations, 2020.
[78] Zhiyuan Li, Kaifeng Lyu, and Sanjeev Arora. Reconciling modern deep learning with tra- ditional optimization analyses: The intrinsic learning rate. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 14544-14555
Curran Associates, Inc., 2020.
[79] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning, In International Conference on Learning Representations, 2021.
[80] Zhiyuan Li, Srinadh Bhojanapalli, Manzil Zaheer, Sashank Reddi, and Sanjiv Kumar. Robust training of neural networks using scale invariant architectures. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 12656-12684 12684. PMLR, 17-23 Jul 2022.
[81] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after SGD reaches loss? - mathematical framework. In International Conference on Learning Representations, 2022.
[82] Zinan Lin, Vyas Sekar, and Giulia Fanti. Why spectral normalization stabilizes GANs: Analysis and improvements. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 9625-9638. Curran Associates, Inc., 2021.
[83] Shengchao Liu, Dimitris Papailiopoulos, and Dimitris Achlioptas. Bad global minima exist and sgd can reach them. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8543-8552. Curran Associates, Inc., 2020.
16

---

[84] Ekaterina Lobacheva, Maxim Kodryan, Nadezhda Chirkova, Andrey Malinin, and Dmitry P Vetrov. On the periodic behavior of neural network training with batch normalization and weight decay. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 11545-15560 Curran Associates, Inc., 2021.
[85] Ekdeep S Lubana, Robert Dick, and Hidenori Tanaka. Beyond batchnorm: Towards a unified understanding of normalization in deep learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 4778-4791 Curran Associates, Inc., 2021.
[86] Ping Luo, Xinjiang Wang, Wenqi Shao, and Zhanglin Peng. Towards understanding regu- larization batch normalization. In International Conference on Learning Representations, 2019.
[87] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.
[88] Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34. 2021.
[89] Chao and Lexing Ying. On linear stability of SGD and input-smoothness of neural networks. A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[90] Chao Ma and Lexing Ying. A Riemannian mean field formulation for two-layer neural networks with batch normalization. Research in the Mathematical Sciences, 9(3):47, July 2022. ISSN 2197-9847.
[91] Chao Ma, Daniel Kunin, Lei Wu, and Lexing Ying. Beyond the quadratic approximation: The multiscale structure of neural network loss landscapes. Journal of Machine Learning, 1(3): 247-267, 2022. ISSN 2790-2048.
[92] David McAllester. Simplified PAC-Bayesian margin bounds. In Learning theory and Kernel machines, pages 203-215. Springer, 2003.
[93] Rotem Mulayoff and Tomer Michaeli. Unique properties of flat minima in deep networks. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 7108-7115 PMLR, 13-18 Jul 2020.
[94] Rotem Mulayoff, Tomer Michacli, and Daniel Soudry. The implicit bias of minima stability: A view from function space. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 17749-17761. Curran Associates, Inc., 2021.
[95] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. Advances neural information processing systems, 30, 2017.
[96] Ioannis Panageas and Georgios Piliouras. Gradient Descent Only Converges to Minimizers: Non-lsol Critical Points and Invariant Regions. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1 1222 Dagstuhl, Germany, 2017. Schloss Ceestuull-LibbiizZeeeee 11.4230/LIIIcs.ITCSS.000
fuer Informatik. ISBN 978-3-95977-002-33 doi:
[97] Siyuan Qiao, Huiyu Wang. Chenxi Liu, Wei Shen, and Alan Yuille. Micro-batch training with batch-channel normalization and weight standardization. arXiv preprint 2019.
[98] Prajit Ramachandran, Barret Zoph, and Quoe V Le. Searching for activation functions. arXiv preprint arXiv: 2017.
17

---

[99] Akshay Rangamani, Nam H. Nguyen, Abhishek Kumar, Dzung Phan, Sang Peter Chin, and Trac D. Tran. A scale invariant measure of flatness for deep network minima. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),
pages 1680-1684, 2021.
[100] Noam Razin and Nadav Cohen. Implicit regularization in deep learning may be explainable by norms, In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21 11117422111 21187. Curran Associates, Inc., 2020.
[101] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages I 18422-18462 PMLR, 17-23 Jul 2022.
[102] Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[103] Shibani Santurkar, Dimitris Tsipras, Andrew lyyas, and Aleksander Madry. How does batch normalization help optimization? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 2483-2493. Curran Associates, Inc., 2018.
[104] Alexander Shekhovtsov and Boris Flach. Stochastic normalizations as bayesian learning. In C. V. Jawahar, Hongdong Li, Greg Mori, and Konrad Schindler, editors, Computer Vision ACCV 2018, pages 463-479, Cham, 2019. Springer International Publishing. ISBN 978-3- 030-20890-5.
[105] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference on Learning Representations, 2015.
[106] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19 (70):1-57, 2018.
[107] Daniel Soudry, Elad Hoffer, and Nathan Srebro. The implicit bias of gradient descent separable data. In International Conference on Learning Representations, 2018.
[108] Dominík Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information Processing Systems, 34, 2021.
[109] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
[110] Hidenori Tanaka and Daniel Kunin. Noether's 's learning dynamics: Role of symmetry breaking in neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 25646-25660. Curran Associates, Inc., 2021.
[111] Mattias Teye, Hossein Azizpour, and Kevin Smith. Bayesian uncertainty estimation for batch normalized deep networks. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4907-4916. PMLR, 10-15 Jul 2018.
[112] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using PAC-Bayesian analysis. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9636-9647 PMLR, 13-18 Jul 2020.
18

---

[113] Twan van Laarhoven. L2 regularization versus batch and weight normalization. arXiv preprint arXiv:/706.055: 053500 2017.
[114] Ruosi Wan, Zhanxing Zhu, Xiangyu Zhang, and Jian Sun. Spherical motion dynamics: Learning dynamics of normalized neural network using sgd and weight decay. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 6380-6391. Curran Associates, Inc., 2021.
[115] Yi Wang and Zhiren Wang. Three- stage evolution and fast equilibrium for SGD with non- degerate critical points. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 23092-233 23113, PMLR, 17-23 Jul 2022.
[116] Yuqing Wang. Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate tames ho- mogeneity: Convergence and balancing effect. In International Conference on Learning Representations, 2022.
[117] Lei Wu, Zhanxing Zhu, et al. Towards understanding generalization of deep learning: Perspec- tive of loss landscapes. arXiv preprint arXiv:1706. 10239, 2017.
[118] Lei Wu, Chao Ma, and Weinan E. How sgd selects the global minima in over-parameterized learning: A dynamical stability perspective. In S. Bengio, H. Wallach, H. Larochelle, K. Grau- man, N. Cesa- Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[119] Xiaoxia Wu, Edgar Dobriban, Tongzheng Ren, Shanshan Wu, Zhiyuan Li, Suriya Gunasekar, Rachel Ward, and Qiang Liu. Implicit regularization and convergence for weight normalization. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2835-2847. Curran Associates, Inc., 2020.
[120] Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018.
[121] Zeke Xie, Issei Sato, and Masashi Sugiyama. diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference on Learning Representations, 2021.
[122] Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian pro- cess behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:/902.04700 2019.
[123] Mingyang Yi, Qi Meng, Wei Chen, Zhi-ming Ma, and Tie- Yan Liu. Positively scale-invariant flatness of ReLU neural networks. arXiv preprint 1xX3::9903.022. 2019.
[124) Mingyang Yi, Huishuai Zhang, Wei Chen, Zhi-Ming Ma, and Tie-Yan Liu. Bn-invariant sharpness regularizes the training model to better generalization. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 4164-4170. International Joint Conferences on Artificial Intelligence Organization, 7 2019.
[125] Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference Learning Representations, 2017.
[126] Guodong Zhang, Chaoqi Wang, Bowen Xu, and Roger Grosse. Three mechanisms of weight decay regularization. In International Conference on Learning Representations, 2019.
[127] Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7654-7663. PMLR, 09-15 Jun 2019.
[128] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over par-paaraeeeriized deep ReLU networks. arXiv preprint 1t.i::1811.0880 2018.
19

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sections 4.2.1 and 7.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We are basically theoretical work studying the generalization myestery in deep learning. We do not see any negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] The assumptions of our main theorem for GD+WD on scale-invariant loss are stated in Section 4.2. For GD/PGD with Muasi-pMMprrop schedulers general, see Appendix B.3.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices and for the proofs for our main theorems, Appendix O for the proof for the linear example.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material URL)? [Yes] See our supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix Q.
(c) Did you report error bars (c.g., with respect to the random seed after running experiments multiple times)? [No] Most of our experiments have only once due computational constraints, but we verified the sharpness sharpness-reduction reduction bias across various settings.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]] See Appendix Q
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you diseuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica-
ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
20


Reviews:
[{"review_id": "ws6lYnYb11U", "reviewer": "Reviewer_qMdw", "summary": "The current paper argues that benefits of BatchNorm in regards to generalization have been under-discussed and tries to develop a novel analysis for the same. To this end, the authors prove that under weight decay and a scale-invariant loss, as induced if there is a BatchNorm corresponding to all parameters, the model's training functions in two regimes: stable and edge-of-stable (EoS), which arises because the use of weight decay forces parameter norm to increase. In the EoS regime, under assumptions such as existence of a manifold of minimizers, it is shown that scale invariance will force the model to follow a \"sharpness-reduction\" flow, i.e., a gradient flow under which the sought solution is trying to minimize sharpness. Sharpness is defined by taking scale-invariance into account.", "questions": "See weaknesses. ", "limitations": "Primarily, there is scope for improvements in experiments and discussion on relevant related works.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nI think the analysis in this paper is strong and the proposed tools, though extensions of prior works to some extent, can be of interest beyond the paper's goal. The overall story is very well laid and I really enjoyed reading the paper. \n\n\n### Weaknesses\n\nI think the paper has few primary weaknesses in its current form and they should be easy to address. I strongly encourage the authors to do the same and am happy to raise my score accordingly.\n\n* Related work: While the related work is decently broad, I think a few highly relevant papers have been missed. Specifically, Luo et al. (https://arxiv.org/abs/1809.00846) developed an objective that approximates BatchNorm's regularization effects. It would be important to cite the paper and compare if its results relate with the proposed sharpness reduction flow (could they be similar in some settings?). Second, Tanaka and Kunin (https://arxiv.org/abs/2105.02716) developed a detailed relationship between models trained using SGD under normalization layers and adaptive gradient methods such as RMSprop. The authors claim their proposed link is the first, but this paper has a similar relationship derived via analyzing symmetry breaking of scale invariant losses under fiinite learning rate. It would be important to highlight how the authors' results differ.\n\n* Experiments: While I enjoyed the analysis, I think the experiments lack some ablative baselines demonstrating how lack of BatchNorm would have not yielded similar generalization or similar sharpness reduction. For example, in Figure 2 with CIFAR-10 results, one can train the model without BatchNorm and achieve similar or better test accuracy using the initialization strategy proposed by Daneshmand et al. (see section 4 of https://arxiv.org/abs/2003.01652). Would one see a similar reduction in sharpness? In fact, Daneshmand et al. argue in their work that BatchNorm's effectiveness cannot be explained via scale invariance and as long as one gets a rank-maximizing signal flow at initialization, good generalization is achieved. Then, the experiment suggested above will help understand whether the current paper's position is correct.\n\n* Extension to other layers: I think it is important to include discussion on why similar results on sharpness reduction will not be seen with other normalization layers. Technically, most normalization layers have scale invariance at some granularity (e.g., channel-level in InstanceNorm or layer-level in LayerNorm). Several of those layers are unable to match BatchNorm in its effectiveness, but some of them do when they have similar signal propagation characteristics, as shown by Lubana et al. (https://arxiv.org/abs/2106.05956). ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pN0qsQN_-Ie", "reviewer": "Reviewer_CDHW", "summary": "This paper shows that normalization along with weight decay biases full-batch gradient descent with finite step sizes towards flat solutions.", "questions": "N/A", "limitations": "The authors do discuss their assumptions in detail, and they do mention the limitations of their work at understanding broader deep learning phenomena.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths and Contributions:\n\n-The paper’s organization is great, and it’s easy to follow.\n\n-This paper explains the EoS phenomenon theoretically, which to my knowledge was previously a puzzling unexplained observation.\n\n-The paper does a reasonable job of providing intuition behind the theory.\n\n\nWeaknesses\n\n-Throughout the paper, starting in the first sentence of the intro, grammatical errors make the paper a bit hard to read, but I was still able to understand everything after re-reading some sentences a couple times.  Not a huge deal but definitely worth fixing before publication.\n\n-Empirically, the benefits of weight decay are unclear.\n\n-Other works have found that full-batch GD finds sharper mins than SGD in the absence of, for example, gradient clipping.  The difference between sharp/flat properties of full-batch and stochastic training calls into question exactly what this work can tell us about the dynamics of training routines people actually use, which are nearly always stochastic.  It would be interesting to connect your findings to the effects of stochasticity on training.\n\n-The empirical validation is very sparse.  I realize that there has already been a lot of work on the sharp/flat hypothesis and normalization layers from an empirical perspective, but ablations on the assumptions of the theory (i.e. experiments to see if the predictions of the theory still hold empirically under weaker assumptions) would be interesting.\n\n-Minor point: the scale invariance problem for flatness measurements like the spectral norm of the Hessian is a very special (and particularly coarse) case of a broader space of reparameterization problems by which different parameter settings may yield the same function but not the same flatness.  A number of stronger invariant metrics have been proposed, for example invariant to filter-wise rescaling, but it would also be interesting to show function-space properties (e.g. classifier margins, etc) rather than parameter-space ones.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "W_J8vRWR1qR", "reviewer": "Reviewer_1MUm", "summary": "This paper concerns on the optimization aspect when training deep neural networks (DNNs) with normalization techniques. Normalized DNNs are prevalent and often have high performance in practice. However, little is theoretically known. This paper analyzes the role of using normalization and weight decay when training by gradient descent (GD). This paper shows that normalization + weight decay can help GD move to flat region, can impose an implicit bias to reduce sharpness. The authors find that when GD reach the manifold of minimizers, it can move to the Edge of Stability regime. Once in this regime, we can move to a less sharp region on the manifold when using more GD steps. Some experiments on VGG-11, ResNet-20, matrix completion, and linear regression using Batch normalization further support their theory.", "questions": "- Normalization methods often have their own trainable parameters. Those trainable params are important to DNNs' performance in practice. Why this paper does not take those params into consideration? Ignoring those params may not provide correct understanding of normalized DNNs.\n- There is a high fluctuation after 47k training steps in Figure 2. It suggests that when moving out of minimizer manifold, the training loss will be extremely high. Does it indicate that the manifold of minimizers disconnect with the outside or there are some \"hole\" around that manifold?\n", "limitations": "The authors discuss some limitations of this work. I encourage the authors to state clearly the scope of this paper and redesign their experiments.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper provides an interesting view about training normalized DNNs by GD, adding to our knowledge about the behavior of practical DNNs. After reaching the manifold of minimizers, it can move to the Edge of Stability regime, and continue moving to a less sharp region. There is close connection between flat minima and generalization.\n- Some experiments on some DNNs, matrix completion, and linear regression are done to further support their theory.\n\nWeaknesses:\n- Despite of the main focus on normalization, this paper uses only \"scale-invariant\" property to derive their results. This property appears in some methods such as layer norm, instance norm, group norm. However, some other normalization methods (e.g., batch norm - BN) do not ensure scale-invariant loss. The reason is that BN computes the variance of an input signal from the whole training data, and therefore an BN operation is data-dependent and will be dynamic over the training course. This fact violates the assumption about scale-invariant loss in this paper.\n- Due to the above reason, the scope of this paper is unclear and the theory may mismatch their experiments. BN seems not to follow their theory, but the experiments use only BN. The authors should redesign their experiments and narrow down the scope.\n\nMinor: \"reduce the sharpness of the loss\" may not reflect the true nature. A loss function is often fixed before training. Therefore, one may not reduce its sharpness when minimizing the loss. Instead, GD may move from a sharp point to another less sharp point. \n\n======\nAfter reading the authors' response, I now see no more mismatch. I hence slightly increase my score.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Pghv4wbV_f8", "reviewer": "Reviewer_pjae", "summary": "This paper studies the dynamics of sharpness for networks with normalization layers (invariant losses) that are trained using gradient descent with weight decay. The authors define spherical sharpness to account for the scale-invariance of the loss function. They first show theoretically that when neural network parameters get close to a minimizer, after some time, they would enter the \"edge of stability\" regime where both the learning rate and the network parameters would oscillate. Next, it is theoretically shown that at this edge of stability, the network parameters converge to a sharpness-reduction flow with a period-2 oscillation.  Finally, the theoretical results are showcased for a few experimental settings.", "questions": "1- It is not clear why the combination of BN and WD is interesting to study? It seems a bit random.\n\n2- Why are so many jumps in the train/test accuracy curves of Figure 2? What explains the drops in the training accuracy to below 100%? In typical experimental settings (training a VGG on CIFAR-10) such oscilations don't occur.\n\n3- How are Figures 1 and 2 showing that \"settings where normalization provably induces an implicit bias to persistently reduce sharpness in training, which we call the sharpness-reduction bias\". It is not clear why the reduction in sharpness is linked to BN? \n\n\n", "limitations": "The limitations of the work have been mentioned in the conclusion section.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe problem (why normalization helps generalization) is of interest to the community. The theoretical contributions are rather complete and indeed provide a reasonable answer to the problem. The technical contribution with regards to showing the sharpness reduction property for gradient descent (without any stochastic noise) is solid. The practicality of the assumptions has also been considered (lines 209-214). There are even many results that are mentioned mainly in the appendix. \n\nWeaknesses:\n\nThe main point missing from the paper is the motivation behind the particular choice of the setting (BN+WD). Perhaps an empirical example would be nice to motivate this; first showing without BN there is no decrease in sharpness, but then after adding normalization layers there is. \n\nI would suggest a proofread for the paper to fix typos and rewrite some sentences to make them more clear. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JO_W4HEsLfo", "reviewer": "Reviewer_hMQT", "summary": "The authors presented analysis that Gradient Descent (GD) reduce spherical sharpness in training neural networks with normalization layers.\nTheir analysis is done by going through the trajectory of GD, from the stable regime into the Edge of Stability (EoS) regime.\nIn the EoS regime, the trajectory oscillates around the local minimizer manifold, and moves toward the a direction that reduces spherical sharpness.\nIn that regime the author shows, through inductive proof on two EoS condition, that a periodic behavior moves the gradient through until it minimizes the error.\nThe authors experimentally verified their findings on CIFAR-10 with batch-normalized, scale-invariant VGG-11 and ReNet-20, using Swish activation function. \n", "questions": "Typo, Grammar, clarification etc.:\nPg.3, ln. 91: generalizaiton —> generalization\nPg.3, ln. 95: with different with different —> with different\nPg.3, ln. 201: moves towards —> moves toward\n", "limitations": "The paper is theoretical in nature. Any negative societal impact would have to come from, at the current stage, a hard-to-foresee application of the research.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As more of a user of deep neural networks (both Computer Vision and NLU), I feel that the paper can be inaccessible to the general AI community. For one quite a large part of the proof is in the appendix, most reader will just take it to heart that things will work out. However, through that process, reader may lose grounded-ness of what should be kept tracked. \n\nI would say, making better use of the neural network results of the optimization at certain stages may help. That is to show what more is needed to be learned (which images went from misclassified to classified) and how batch normalization allows for that to happen.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept