SALR: Sharpness-aware Learning Rates for Improved Generalization
Authors: Xubo Yue
Maher Nouiehed
Raed Al Kontar
Venue:  (2021)
Keywords: Loss-surface
sharpness
learning rate
generalization

Abstract: In an effort to improve generalization in deep learning, we propose SALR: a sharpness-aware learning rate update technique designed to recover flat minimizers. Our method dynamically updates the learning rate of gradient-based optimizers based on the local sharpness of the loss function. This allows optimizers to automatically increase learning rates at sharp valleys to increase the chance of escaping them. We demonstrate the effectiveness of SALR when adopted by various algorithms over a broad range of networks. Our experiments indicate that SALR improves generalization, converges faster, and drives solutions to significantly flatter regions. 

Under review as a conference paper at ICLR 2021
SALR: SHARPNESS-AWARE LEARNING RATES FOR IMPROVED GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In effort to improve generalization in deep learning, we propose SALR: a sharpness-awand aware learning rate update technique designed recover flat minimiz- ers. Our method dynamically updates the learning rate of gradient-based opti- mizers based on the local sharpmess of the loss function. This allows optimizers automatically increase learning rates at sharp valleys to increase the chance of escaping them. We demonstrate the effectiveness of SALR when adopted by var- ious algorithms over broad range of networks. Our experiments indicate that SALR improves generalization, converges faster, and drives solutions to signifi- cantly flatter regions.
INTRODUCTION
Generalization in deep learning has recently been an active area research. The efforts to improve generalization over the past two decades have brought upon many cornerstone advances and techniques; be it dropout (Gal & Ghahramani] 20166). batch-normalization (Toffe & Szegedy| [2015). data-augmentation
Training Functice
Testing Fonction
(Shorten & Khoshgoftaar 2019). weight de- cay (Loshchilov & Hutter, 2019), adaptive
Flat Minimum
Sharp Mininnen
gradient-based optimization (Kingma & Ba 2015). architecture design and search (Ra- dosavovic et al., 2020), ensembles and their Bayesian counterparts (Garipov et al. 20188] Iz-
Figure 1: conceptual sketch of flat and sharp minima (Keskar et al. 2017).
mailov et al. 2018), amongst many others. Yet, recently, researchers have discovered that the con- cept of sharpness/Hatness plays a fundamental role in generalization. Though sharpness was first discussed in the context of neural networks in the early work of Hochreiter & Schmidhuber (997)).
was only brought to the forefront of deep learning research after the seminal paper by Keskar investigate decreased generalization performance when large batch sizes are used (LeCun et al.) 2012) in stochastic gradient descent (SGD), Keskar et al. (2017) notice that this phenomena can be justified by the ability of smaller batches to reach flat minimizers. Such flat minimizers in turn, generalize well as they are robust to low precision arithmetic or noise in the parameter space (Dinh al.
al.) (2017). While trying
Kleinberg et al. 2018), as shown in Figure !
Since then, the generalization ability of flat minimizers has been repeatedly observed in many recent works (Neyshabur et al. 201 Goyal et al.) 2017] Li al. 2018 Izmailov al. 2018). Indeed, flat minimizers can potentially tie together many of the aforementioned approaches aimed at general- ization. For instance, (1) higher gradient variance, when batches are small, increases the probability to avoid sharp regions (same can be said for SGD compared to GD) (Kleinberg et al., 2018 (2) averaging over multiple hypotheses leads to wider optima in ensembles and Bayesian deep learning (Izmailov et al. 2018) (3) regularization techniques such dropout werrparametterizaton
adjust the loss landscape into one that allows first order methods to favor wide valleys (Chaudhari
et al. 2019 Allen-Zhu et al. 2019).
In this paper we study the direct problem of developing an algorithm that can converge to flat min- Smizers.Specifically, introduce SALR: sharpness aware learning rate designed explore the

---

Under review as a conference paper at ICLR 2021
loss-surface of an objective function and avoid undesired sharp local minima. SALR dynamically updates the learning rate based on the sharpness of the neighborhood of the current solution. The idea is simple: automatically increase the learning rates relatively sharp valleys in an effort to escape them. One of the key features of SALR is that it can be fitted into any gradient based method such Adagrad (Duchi et. 2 2 ADAM (Kingma & Bal (015) and also into recent approaches towards escaping sharp valleys such as Entropy-SGD (Chaudhari et al. 2019).
1.1 RELATED WORK
From a theoretical perspective, generalization of deep learning solutions has been explained through
multiple lenses. One of which uniform stability (Bottou & Le Cun 2005 Bottou & Bousquet
2008 Hardt et al. 2016 Gonen & Shalev-Shwartz, [017 [Bttoou et al., 2018). An algorithm is
uniformly stable if for all data sets differing only one element, nearly the same outputs will be
produced (Bousquet & Elisseeff 22022) Hardt et al. (2016) show that SGD satisfies this property and derive a generalization bound for models learned with SGD. From a different viewpoint, [Corro-] manska et al. (2015); Kawaguchi (2016); (Pogroo et al. (201)): Mohri et al. (2018) attribute gener-
alization to the complexity of the hypothesis-spaae space. Using measures like Rademacher complexity
(Mohri & Rostamizadeh 2009) and the Vapnik-Chee Cherik-Chervonenkis (VC) dimension (Sontag) 1998). the
former works show that deep hypothesis spaces are typically more advantageous in representing complex functions. Besides that, the importance of flatness on generalization has been theoretically highlighted through PAC-Bayes bounds (Dziugaite & Roy| 2017; Neyshabur et al., 2017b] Waang et al. 2018). These papers highlight the ability derive non-vacuous generalization bounds based on the sharpness of a model class while arguing that relatively flat solutions yield tight bounds.
From an algorithmic perspective, approaches to recover flat minima are still limited. Most no- tably, Chaudhari et al. (2019) developed the Entropy-SGUP algorithm. Entropy defines a local- entropy-based objective which smoothens the energy landscape based on its local geometry. This in turn allows SGD to attain flatter solutions. Indeed, this approach was motivated by earlier work in statistical physics (Baldassi et al. 2015) 2016) which proves the existence of non-isolated solutions that generalize well in networks with discrete weights. Such non-isolated solutions correspond to flat minima in continuous settings. The authors then propose a set of approaches based on ensembles and replicas of the loss to favor wide solutions. Not too far, recent methods in Bayesian deep learn- ing (BDL) have also shown potential to recover flat minima. BDL basically averages over multiple hypotheses weighted by their posterior probabilities (ensembles being special case of BDI. (lz- mailov et al. (018)) ). One example, is the stochastic weighted averaging (SWA) algorithm proposed by Izmailov et al. (2018). SWA simply averages over multiple points along the trajectory of SGD to potentially find flatter solutions compared to SGD. Another example is the SWA-Gaussian (SWAG). SWAG defines a Gaussian posterior approximation over neural network weights. Afterwards, sam- ples are taken from the approximated distribution to perform Bayesian model averaging (Maddox ct al. 2019).
Here we also note the recent work by Patel (2017) which partially motivates our method. Upon the aformentioned observations in Keskar et al. (017). Patel (2077) shows that the learning rate lower- bound threshold for the divergence of batch SGD, run on quadratic optimization problems, increases for larger batch-sizes. In general non-convex settings, given a problem with N local minimizers, one can compute N lower bound thresholds for local divergence of batch SGD. The number of minimizers for which batch SGD can converge non-decreasing in the batch size. This is used to explain the tendency of low-batch SGD converge to flatter minimizers compared to batch SGD. The former result links the choice of batch size and its effect on generalization to the choice of the learning rate. With the latter being tunable parameter, our knowledge, developing dynamic choice of the learning rate that targets convergence to flat minimizers has not been studied before.
2 GENERAL FRAMEWORK
In this paper, we propose framework that dynamically chooses a Sharpness-Aware Learning Rate to promote convergence to flat minimizers. More specifically, our proposed method locally approxi- mates sharpness at the current iterate and dynamically adjusts the learning rate accordingly. In sharp regions, relatively large learning rates are attained to increase the chance of escaping that region. In contrast, when the current iterate belongs flat region, our method returns relatively small
2

---

Under review as a conference paper at ICLR 2021
learning rate to guarantee convergence, Our framework can be adopted by any local search descent method and detailed Algorithm
Algorithm 1: Sharpness-Awarr Learning Rate (SALR) Framework
Input: Starting point 0g. initial learning rate TJu Number of iterations K.
for k = 0, ........ K do
Estimate Sy, the local sharpness around the current iterate 0k:
Set T/e
Median {
i=1 Compute 0x+1 using some local search descent method (Gradient Descent, Stochastic Gradient Descent, ADAM,
end
Return 0x-
As detailed in Algorithm every iterate k, we compute the learning rate as a function of the local sharpness parameters {Sa]_-. أ- The main intuition is to have the current learning rate to be an increasing function the current estimated sharpness. Since the scale of the sharpness at different points vary when using different networks datasets (Dinh et al. 2017), we normalize estimated sharpness by dividing by the median of the sharpness of previous iterates. For instance in Figure 2 despite having similar sharpness measure, we consider the minimizer around O = 1 to be sharp relative to the blue plot and flat relative to red plot. Normalization resolves this issue by helping our sharpness measure attain scale invariant properties.
One can think of the median previous sharpness values as a global sharpness parameter the al- gorithm is trying to learn. When & is sufficiently large, the variation in the global sharpness pa- rameter among different iterates will be minimal. From an algorithmic perspective, SALR exploits a neighborhood around the current iterate dynamically compute a desired learning rate while simultaneously exploring the sharpness of the landscape to refine this global sharpness parameter.
Misiniixx
Suom Mhinissea
Mannorr
Figure 2: Sharp/Flat minimizers relative to the landscape.
SHARPNESS MEASURE
Several sharpness/flatness measures have been defined in recent literature (Rangamani et al. 2019 Keskar et al., 2017: Hochreiter & Schmidhuber 1997). For instance, Hochhreter & Schmidhuber (997) computes flatness by measuring the size of the connected region the parameter space where the objective remains approximately constant. In more recent paper, |Rangamani et al. (219)) proposed a scale invariant flatness measure based on the quotient manifold. Computing such notions for complex non-convex landscapes can be intractable in practice. In addition to the cited Kssults/Keskaa et al. (2017) quantifies flatness by finding the difference between the maximum value of the loss function within small neighborhood around given point and the current value. More specifically, they define sharpness as follows:
S(e, 0)
(E,
and S(E = max ʃ(0') - -()),
+ S(A)
0'Em, (0)
where (+) is a euclidean ball with radius E centered at @ and 1+ f(0) is normalizing coefficient. One drawback of equation T is that the sharpness value around maximizer nearly zero. To resolve
3

---

Under review as a conference paper at ICLR 2021
this issue, one can simply modify the sharpness measure in equation T as follows:
See 0)
max
f(0') min !(0").
O'EB,
o'E (0)
can be easily shown that if 0 is a local minimizer, equation i equivalent to equation T Both mea- sures defined in equation| and equation2]requini solving a possibly non-convex function which is in general NP-Hard. For computational feasibility, we provide a sharpness approximation by running nı gradient ascent and n2 gradient descent steps. The resulting solutions are used to approximate the maximization and minimization optimization problems. Here we note that our definition for
sharpness does not include normalizing coefficient, as median { in Algorithm plays this role. The details of the approximation are shown in the Definition Definition 1. Given 0 E RR", iteration numbers n, and n2,, and step-size y, we define the sharpness measure
!
((0) & f(0 k.t (ma)) f(0x) + f(0x) f(Ok, (1)) f(0((t) ((0(m))
where
0
(0) k,+
0 - O%
V _
1ig
V vf(e
(/ O2
((ma) k,+
and
O2 +
i=0
In contrast to the measures defined in equation 2 and equation 7 Definition 7 does not require ball radius E. However, our definition requires specifying the step-size y and the number of ascent and descent iterations.
Remark 2.
Remark Running gradient descent/ascent with fixed step-size near a minimizer can return a very small sharpness value even if the minimizer is sharp. This is due to the small gradient norm around a minimizer. To resolve this issue, we normalize the gradient at every descent/ascent step. Moreover, normalizing by the norm of the gradient helps in understanding the radius of the ball containing the iterates yod
(0.-1111 and {0()) j==1"
Figure shows the plots of the three different sharpness measures defined in this section when computed for a function f(0)= = 0.50 sin (30) + 1. Notice that the blue plot corresponding to the sharpness measure (0-) attains zero value at local maximizers compared a positive value for the other two sharpness plots. Moreover, notice that the sharpness value in these three plots attains a small value near the local minimizer. This can be explained by our choice of radius & 0.1 which limits the neighborhood being exploited. Increasing the radius for ((E,-) and S(E, -) (increasing n1 and n2 for 5) will provide higher values around the minimizer. We next show that using sharpness measure in Definition]] [ gradient descent with SALR framework in Algorithm T denoted GD-SALR, escapes sharp local minima.
(350
0.0
Sy My 8
0.7
$10.1, )
0.1
0.8
0.5
0.5
1.5
2.5
0.6
2.5
Figure 3: Sharpness measure plots for d. S, and $ on function f.
THEORETICAL RESULTS
In this section, we focus analyzing the convergence of vanilla GD when adopting our sharpness- aware learning rate framework in Algorithm[] We show that GD-SALR escapes any given neighbor- hood of a sharp local minimum by choosing sufficiently large step-size. Throughout this section,
4

---

Under review as a conference paper at ICLR 2021
make the following assumptions that standard for the convergence theory of gradient descent methods.
Assumption 1. The objective function f is twice continuously differentiable and Lo-Lipschitz, con- tinuous. The gradient function V.(()) is L-Lipschitz continuous with Lipschitz constant L. Fur- thermore, the gradient norm is bounded, i.e. there exists a scalar constant 9maz > such that [[] S Imax for all O.
The next theorem shows that GD with a sufficiently large step-size escapes given strongly convex neighborhood around local minimum 0"
Theorem 4. Suppose that is j--ttrongyy convex function in a neighborhood B3(0*) around local minimum 0", i.e. Amin (V2f(0) 2 ffoor all = 1Bx(0)) & [0]10 0" S 6}. Running vanilla
2 + for some fixed 0, there exists To with
GD with Ou (B²(0)) and learning rale The 0g $ (B*(").
Proof. The proof of lemma is relegated to the Appendix
Our next result shows that GD-SALR escapes sharp local minima by dynamically choosing suffi- ciently large step-size in a local strongly convex region.
Theorem 5. Suppose that f is a ju-strongly convex function in neighborhood lB((0)) around
local minimum 0" iee. Amin (V2 2 μ for all (B, - {0 l|e 0- ll S 6). Under
Assumption 7 run GD-SALR (Gradient descent with step size choice according to Algorithm 7 and Definition with
a
a2
Imin T.
11 2
2
112
2
and 7
log
P Imin
01
llog
1
μ Imin
02
T. Jmaz
Jmin
T. J.max
where
(2 + e
Gminj
(2+ e
122 gmin
a1
and
a2 nu9maaz
C, 7/0 > 0,
(ulaaazzz L Iminnt) 2(gmaz 9mintt)
2L gmax"
and 9min > 0 is a lower bound that satisfies
{||TS (ol=-") 1IV Imin.
max
If 8 > max(n1, ny2%,, then there exists with 0g & BB((
Proof. The proof of the theorem is relegated to the Appendix
C
Remark 6. In the context of machine learning, our theorem shows that our algorithm can potentially escupe sharp regions even when the data are used (full-butch). In their work, Patel (2017) show that when using large batch sizes require higher learning rate escape sharp minima. This provides an insight on the favorable empirical results presented in Section 6 when running SGD- SALR. Moreover, our dynamic choice of high learning rate in sharp regions can potentially allow running SGD with larger batch sizes while still escaping sharp minimizers. This in turn provides an avenue for improved parallelism (Dean et al. 2012 Das al. 20166).
In the next section, we generalize our proposed framework to the stochastic setting.
5 STOCHASTIC APPROXIMATION OF SHARPNESS
The concept of generalization is more relevant when solving problems arising in machine learn- ing settings. Under the empirical risk minimization framework, the problem of training machine learning models can be mathematically formulated as the following optimization problem
min f(0) A 2
Σ f(()),
(3)

---

Under review as a conference paper at ICLR 2021
where fs is loss function parameterized with parameter 0 corresponding to data point (1. The most popular algorithm used to solve such optimization problems is the stochas- tic gradient descent which iteratively updates the parameters using the following update rule:
0 02 1)k
Σ vI((Os))
|BEE
where B3 is the batch sampled at iteration i and 77 is the learning rate. To apply our framework in stochastic settings, we provide stochastic procedure for computing the sharpness measure a given iterate. Details are provided in 2 By adopting A our framework can be applied numerous popular algorithms like SGD, ADAM and Entropy-SGD. The detailed implementation of SGD-SALR and ADAM-SALA can be found in Algorithms and in Appendix A
Algorithm 2: Calculating stochastic sharpness at iteration k
Data: batch size By. base learning rate y.. current iterate θ₁. iteration number n1, 722
Set (00)
+,+ 0 k.- OR:
for i 0: n1 1 do
VJ
(++1) = [00 k.-
k.-
B
JEB
Vf
end
for i = 0: 0:122 1 do
@ k.+) Vf
0(++1) +,+
0 k,t +
[Bx] jE
Vfi
end
Return Sg
1
fo
(0 (m2))
Σ fs (111))
Rit
BB jEB
jEBn
EMPIRICAL RESULTS
In this section, we present experimental results on image classification and text prediction datasets. We show that our framework SALR can be adopted by many optimization methods and achieve notable improvements over a broad range of networks. We compare SALR with Entropy-SGID (Chaudhari et al., 2019) and SWA (Izmailov al. 2018). Besides those benchmarks, we also use the conventional SGD and ADAM (Kingma & Ba 2015) as baseline references. All aforementioned methods are trained with batch normalization (loffe & Szegedy (015)) and dropout of probability 0.5 after each layer (Gal & Ghahramani] 2016). We replicate each experiment 30 times to obtain the mean and standard deviation of testing errors. our experiments, we do not tune any hyper- parameters. We consider some typical networks such as mnistfc (loffe & Szegedy] 2015). ResNet (He et al. 2016), DenseNet (landola et al. 2014), MobileNetV2 (Sandler et al. 2018) and RegNetX RRadoavvvvic et al. 2020).
6.1 MNIST/CIFAR--0
We run Algorithm 3 SGD-SALR for 20 epochs. We collect the sharpness measure every = 2 iterations and set 7 n22 = as detailed in Algorithm 2 The experimental settings for other benchmark models are as follows: (1) SGD: we run SGD for 100 epochs using decay learning rates. (2) SWA: the setting is the same as SGD. In the SWA stage, we switch to a cyclic learning rate schedule as suggested in Izmailov et al. (2018) (3) Entropy-SGD: following the setting in Chaudhari et al. (201)). we train Entropy-SGD for 20 epochs and set Langevin iterations L, = 5. (4) Entropy-SGD-SALR the setting is same Entropy -GD,, however, we update the learning rate of Entropy-Soa SGD using Algorithm?? 2 Further details on each benchmark setting can be found in Appendix D The results are reported Table 1

---

Under review as a conference paper at ICLR 2021
Entropy- SGD
Entropy-SGD- SALR
SGD-
Network
SGD
SWA
SALR
ResNet18
98.97 (0.01)
98.99 (0.01)
99.11 (0.01)
99.19 (0.01)
99.21 (0.03)
RegNetX
99.02 (0.03)
98.95 (0.01)
99.20 (0.03)
99.47 (0.01)
99.45 (0.01)
L.Nett
98.50 (0.01)
98.69 (0.0T)
99.05 (0.03)
99.16 (0.OT)
99.17(0:01)
MobileNetV2
98.79 (0.02)
98.80 (0.01)
99.26 (0.00)
99.44 (0.01)
99.50 (0.01)
mnistfee
98.02 (0.02)
98.21 (0.02)
98.58 (0.0T)
99.00 (0.0T)
99.02 (0.0T)
Table 1: Classification accuracy on MNIST
We increase the number of training epochs for Entropy-SGDDen SGD/Entropy- SrEEEntroyy-GD----.. SALR/SGD- to 40 and the training epochs of SGD/SWA to 200. Experimental results are reported in Table 2
Entropy- SGD
Entropy-SGD- SALR
SGD-
Network
SGD
SWA
SALR
ResNet18
88.17 (0.04)
88.56 (0.01)
91.05 (0.01)
91.21 (0.01)
91.21 (0.02)
ResNet50
88.44 (0.03)
88.83 (0.01)
90.80 (0.03)
92.27 (0.01)
92.44 (0.01)
AII-CNN-BN
91.93 (0.01)
92.20 (0.01)
91.13 (0.01)
92.16 (0.01)
92.45 (0.05)
ResNet101 95.11 (0.02)
95.56 (0.01)
95.51 (0.01)
95.87 (0.01)
95.99 (0.00)
RegNetX
94.24 (0.02)
94.23 (0.01)
94.26 (0.01)
95.00 (0.01)
95.01 (0.01)
Table 2: Classification accuracy on CIFARIO
To illustrate the flexibility of our framework, we change the base optimizer SGD to ADAM and re-rum all the experiments under similar setting that of Table 2 Results are reported in Table Finally, in Table 4 we report the sharpness measure of the final solution obtained by each op- timization approach. We also conduct some experiments on CIFAR-100. Results are deferred to Appendix.
3
Entropy- ADAM
Entropy-ADAMN SALR
ADAM-
Network
ADAM
SWA
SALR
ResNet18
88.01 (0.01)
88.43 (0.01)
91.06 (0.01)
91.17 (0.01)
91.23 (0.01)
ResNet50
87.98 (0.02)
88.41 (0.03)
90.61 (0.01)
92.29 (0.01)
92.31 (0.01)
All-CNN-BN
91.95 (0.01)
92.27 (0.01)
91.10 (0.01)
92.15 (0.01)
92.35 (0.01)
ResNet101
95.00 (0.01)
95.57 (0.01)
95.56 (0.01)
96.03 (0.01)
95.97 (0.00)
RegNetX
94.33 (0.01)
94.12 (0.01)
94.21 (0.01)
95.06 (0.01)
95.02 (0.01)
Table 3: Classification accuracy on CIFARIO using ADAM
6.2 TEXT PREDICTION
We train an LSTM network on the Penn Tree Bank (PTB) dataset for word-level text prediction. This dataset contains about one million words. Following the guideline [1] and [2], we train PTB-LSTM with 66 million weights. SGD and SWA are trained with 55 epochs. Entropy-SGI (L (6=5) and SALR (c = 2) are trained with 11 epochs. Overall, all methods have the same number of gradient calls (i.e., wall-clock times). We then train LSTM to perform character- level text-prediction using War and Peace (WP). We follow the procedures in [2] and [3]. We train Adam/SWA and EntD with 50 and 10 epochs, respectively. We report the perplexity on the test set in Table 5
6.3 ANALYSIS
Based on Tables 5 we can obtain some important insights. First, methods adopting SALR show superior performance over their benchmarks. This increase in classification accuracy (or decrease in perplexity) consistent across both datasets and range of network structures. We also observed that SGD-SALR tends to outperform other SALR based methods in most settings while achieving comparable results in others. Second, and more interestingly, this superior performance is achieved with 5 times less epochs compared to SGD, ADAM and SWA. The caveat however is that SALR and Entropy respectively require (n1 + n2)/cc = and L,, = 5 more gradient calls at each iteration, hence making the total computational needs the same as ADAM, SGD and SWA. Third and as shown in Table it is clear that SALR drives solutions to significantly flatter regions. This highlights the effectiveness of dynamically adjusting learning rates based the relative sharpness of the current
7

---

Under review as a conference paper at ICLR 2021
Entropy SGD
Entropy-SGD SALR
SGD
x10-3
SGD
SWA
SALR
ResNet18
3,23 (0.47)
3.14 (0,51)
1.66 (0.41)
1.04 (0.40)
0.99 (0.36)
ResNet50
8.11 (0.52)
7.65 (0.33)
3.55 (0.44)
3.63 (0.31)
3.22 (0.63)
AII-CNN-EN
11.02 (1.00)
10.65 (1.21)
6.12 (0.88)
6.35 (0.84)
6.30 (0.9T)
ResNet101
7.00 (0.87)
6.91 (0.22)
5.33 (0.60)
6.07 (0.82)
6.13 (0.70)
RegNetX
9.56 (1.03)
9.66 (0.69)
9.41 (0.50)
8.77 (0.68)
8.90 (0.74)
Table 4: Sharpness of final solutions (CIFAR-10) SGD))
PTB
SGD
SWA
Dntropy-SGD
SALR
PTB-LSTM
78.4 (0.22)
78.1 (0.25)
72.15 (0.16)
71.42 (0.14)
WP-LSTM
1.223 (0.01) 1.220 (0.05)
1.095 (0.01)
1.089 (0.02)
Table 5: Perplexity PTB/WP
iterate. To further demonstrate the advantage of SALR framework, we plot the testing error curves for SGD, Entropy-SGD, Antropy-SALR and SALR in (Left) Interestingly, the overall trend when adding SALR to SGD drastically changed with the trend smoothly and more consistently increasing its performance. This can be potentially explained through the capability of SALR to quickly escape sharp regions relative to SGD and hence attain larger and more consistent rates of improvement across Epochs. We also plot the change of sharpness/learning rates over some SALR iterations in the last Epoch in Figure A (Right). This figure highlights the dynamics of both learning rates and sharpness, highlighting that the median sharpness tends to stabilize and hence leading to proportional relationship between learning rates and sharpness.
Training Epoch (SGD)
100
SGD
0.020
Learning Rate Sharpness
0.015
Entropy-SGD
20
Entropy-SALR SGD-SALR
0.015
Learning Rate
0.010
Testing
0.010
15
0.005
0.005
0.000
0.000
10
20
30
40
40
Training Epoch (Entropy(SALR)
Iterations
Figure 4: (Left) AII-CNN-BN: Change of Testing Errors over Epochs. (Right) Change of sharpness and learning rate over iterations.
DISCUSSION & OPEN PROBLEMS
In this paper we introduce SALR: an optimization tool that aims to recover flat minima through dynamically updating the learning rate based the current solution's relative sharpness. SALR can be readily plugged into any gradient based method. Experiments show that SALR can deliver promising improvements over a range optimization methods and network structures. In light of this work. we hope researchers further investigate landscape dependant learning rates as they can offer a potential alternative/uniffyig framework for many aforementioned attempts to achieve improved generalization. Also, quasi-Newton approximations of S instead of first order methods and generalization bounds for SALR remain open problems worth investigating.
REFERENCES
Zeyuan Allen-Zhu Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242-252, PMLR, 2019.
8

---

Under review as a conference paper at ICLR 2021
Carlo Baldassi, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Sub- dominant dense clusters allow for simple learning and high computational performance in neural networks with discrete synapses. Physical review letters, 115(12):128100) 2015.
Carlo Baldassi, Christian Borgs, Jennifer T Chayes, Alessandro Ingrosso, Carlo Lucibello, Luca Saglietti, and Riccardo Zecchina. Unreasonable effectiveness of learning neural networks: From accessible states and robust ensembles to basic algorithmic schemes. Proceedings of the National Academy of Sciences, 113(48) E7662, 2016.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334-334, 1997.
Léon Bottou and Olivier Bousquet. The tradcoff's large scale learning. Advances in neural information processing systems, pp. 161-168, 2008
Léon Bottou and Yann Le Cun. On-line learning for very large data sets. Applied stochastic models in business and industry, 21(2):137-11,, 2005.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, (0(2):223-314 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526, 2002.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):
124018, 2019.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pp. 192-204, 2015,
Dipankar Das, Sasikanth Avancha, Dheevatsa Mudigere, Karthikeyan Vaidynathan, Srinivas Srid- haran, Dhiraj Kalamkar, Bharat Kaul, and Pradeep Dubey. Distributed deep learning using syn- chronous stochastic gradient descent. arXiv preprint wrXiv:1602.0670, 2016.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. In Advances in neural information processing systems, pp. 1223-1231, 2012.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. International Conference on Machine Learning, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXhv:1003.11000 2017.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, 2016.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, pp. 8789-8798, 2018.
Alon Gonen and Shai Shalev-Shwartz. Fast rates for empirical risk minimization of strict saddle problems. JMLR: Workshop and Conference Proceedings, 2017.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: 170.006777 2017.

---

Under review as a conference paper at ICLR 2021
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
Forrest landola, Matt Moskewicz, Sergey Karayev, Ross Girshick, Trevor Darrell, and Kurt Keutzer. Densenet: Implementing efficient convnet descriptor pyramids. arXiv preprint arXiv: 1404. 1869, 2014.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by re- ducing internal covariate shift. International Conference on International Conference on Machine Learning. 2015.
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. Averaging weights leads to wider optima and better generalization. Uncertainty in Artificial In- telligence, 2018.
Andrej Karpathy, Justin Johnson, and Li Fei-Fei. Visualizing and understanding recurrent networks. arXiv preprint arXiv:1566.000 02078, 2015.
Kenji Kawaguchi. Deep learning without poor local minima. Advances neural information processing systems, pp. 586-594, 2016.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. Inter- national Conference on Learning Representations, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? International Conference on Machine Learning, 2018.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Raod Robert Müller. Efficient backprop. In Neural nelworks: Tricks of the trade, pp. 9-48. Springer, 2012.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land-
scape of neural nets. In Advances in Neural Information Processing Systems, pp. 6389-6399, 2018.
Ilya Loshchilov and Frank Hutter, Decoupled weight decay regularization. International Conference Learning Representations, 2019.
Wesley Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. In Advances in Neural Information Processing Systems, pp. 13153-13164 2019.
Mehryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for non-iid processes.
In Advances in Neural Information Processing Systems, pp. 1097-1104, 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning- MIT press, 2018.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization deep learning. In Advances neural information processing systems, pp. 5947-5956, 2017a.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally margin bounds for neural networks. arXiv preprint arXiv: 0996644474 2017b.
10

---

Under review as a conference paper at ICLR 2021
Vivak Patel. The impact of local geometry and batch size stochastic gradient descent for noncon- vex problems. arXiv preprint arXiv:1709.04711 2017.
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but shallow-networks avoid the curse of dimensionality; a review. Inter- national Journal of Automation and Computing, 14(5):503-519, 2017.
Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Designing network design spaces. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10428-10436, 2020.
Akshay Rangamani, Nam H Nguyen, Abhishek Kumar, Dzung Phan, Sang H Chin, and Trac D Tran. A scale invariant flatness measure for deep network minima. arXiv preprint arXiv: 1902.02434, 2019.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chich Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510 4520, 2018.
Connor Shorten and Taghi M Khoshgoftaar, survey on image data augmentation for deep learning- Journal of Big Data, 6(1):60, 2019.
Samuel L Smith and Quoe V Le. A bayesian perspective generalization and stochastic gradient descent. International Conference on Learning Reprexentations, 2017.
Samuel L Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc Le. Don't decay the learning rate, increase the batch size. International Conference on Learning Representations, 2018.
Eduardo Sontag. Ve dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96, 1998.
Huan Wang, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. Identifying generalization properties neural networks. arXiv preprint /809.00400 2018.
Wei Wen, Yandan Wang, Feng Yan, Cong Xu, Chunpeng Wu, Yiran Chen, and Hai Li. Smoothout: Smoothing sharp minima improve generalization in deep learning. arXiv preprint arXiv:1805.07898, 2018.
Wojciech Zaremba, Ilya Sutskever, and Oriol Vinyals. Recurrent neural network regularization. arXiv preprint arXiv: 1409. 2014.

---

Under review as a conference paper at ICLR 2021
Supplementary Material
A EXAMPLES OF SALR-BASED ALGORITHMS
The SALR framework be fitted into many optimization algorithms. In this section provide some examples. In Algorithm 3 and 4 algorithm, respectively.
we present the SGD-SALR algorithm and the ADAM-SALR
Algorithm 3: The SGD-SALR Algorithm
Data: base learning rate number of iterations K, frequency c, initial weight On Result: weight vector 0.
Set S = 0:
for k 0 K do
if k: mod c= 0 then
Caleulate Sg using Algorithm
end
Compute S = Median ({S+)
Sp S
Set 17s- = 170
1
0k+1 0% 17
Bxl EJEB. Vf,(0%);
end
Set
0
Return O.
Algorithm 4: The ADAM-SALR Algorithm
Data: base learning To. exponential decay rates for the moment estimates 31, B2 (0,1), number of iterations K, frequency c, initial weight 6, perturbation e
Result: weight vector O.
Set S = 0;
Set me 0g =
for i = 0: K do
k: mod c then
Calculate Sz using Algorithm
end
Compute S Median ({5x))
S₁ S
Set 1/8
9 =
(Ok)
B&
je
m Bim; + (1 - B1)g
0k41 = 3rru + (1 32)9²
M = m (1- gl g(+l)
Tk+1 = ux/(1 (1 B2 gk+l)
0x+1 O₁ 7 / + e);
end
Set 0k:
Return 0.
12

---

Under review as a conference paper at ICLR 2021
B PROOF OF THEOREM 4
Proof. According to the update rule of vanilla gradient descent, it follows that by mean-valuue theo-
rem there exists [0x. 0*] such that
0x+1 0 = O2 0" - 1/2: (0xx))
02 0" The
04)
I Th V² f(O) (0x -0),
where the last equality holds since l* is local minimum. By taking the norm, we get
0 2 || - 7) jo| || 1' 11 I 7hs v² (0,
|0
where the last inequality holds by our local strong convexity assumption, the fact that O (B²) and our choice of Th- The former choice also imply that
||0 - 00 N (N&H
1) 0b
0* 2 + c)] 1"
which yields
0 0'1l 2 (1 + e 100 0'1
1
Let |00
0*1 = D and h
log
5 then
log(1 + +
|
0" || 2
which completes our proof.
C PROOF OF THEOREM 5
Proof. According to Lemma rumning vanilla gradient descent with 77s 2 2+ for some fixed
0 escapes the neighborhood IB, (0"). Hence, to complete proof, it suffices show that GD-SALR will dynamically choose a sufficiently large step size.
We first start by computing lower bound for our local sharpness approximation in local strongly convex regions. By definition,
Sg = f (0 (12)
(0 ((()1) = ) (o!mz) - f(O+) + f(Ow)
We start by computing a lower bound for [(0x) (o(mn))
By descent lemma (Bertsekas) 1997).
0 (1+11)
S
0 +
(++1)
0
L
(+1)
2
7 vs
(1)) ||
+
L
2
By summing over the nn iterations, we get
s(x))
(ofmz) (1))
2
V
||
ni
(4)
1=0
(++)
By mean value theorem, there exists
z
0
with
v 0 (
= vs
(1)
+ 42
0
(+1) [
(
Vf
(0
- 3 V2 (
v k.
13

---

Under review as a conference paper at ICLR 2021
which yields
(11-yp/gman Vf _ )
L ymaz pe Jmin
L Jmmax
Here the inequality holds by local strong convexity and the fact that i E (00) due to our choice of 8, the upper bound on the norm of the gradient, and our choice of y. Substituting back into equation 4 we get
s(Ox) s S (of
L Imax
14 Jmnn
V 00
1)
n1
9max
9mán
Imax
-1) (
L Imax
n1 R2 -1 1) V/ (0(----)
L
H1mmn
L Jmar
1 J.mmi
2
Jmar
Jemón
((
L ymaz
n
|5 (o(---1))
n1 Ln
p
L
L. 9maz
I Imin
2
(5)
By our choice of mi, we have
(1+ L Imaz pa J.gmmn
p.min
11
112 M1 01
(6)
The inequality holds since
11. Gmnn
IA Jran
11 01
log 1
= n1 log
1
1V
2
log(1+)101),
Immax - 1l Imin
L Imaz - p Jmmin
Vn 01 +
where the first inequality holds by our choice of n, and the second inequality is an upper bound of log(1 + z). By substituting equation in equation 5 and using our assumption that
min
V
||| Vf (00. (1)) Z Imin
we get
f(On)= - f (o(m.)
Jmaz
Imii
R2 I
2
T2 01 Imin
L
2L
12+c) c
)
(
Lo Frein
nı
L
We now compute lower bound for (ma)
f
=(O)). By local strong convexity of f, we have
/ (o((t))
2 (0
+
V
(1)
(++1)
0x.
(1)
>
/
0
(1+1)
0
2
2
= = (0
(0())
||
222
k
2
By summing over the n2 iterations, we get
-1
/ (0 (2n) 5(0x) 27
Σ
| (0 (0%,+)]+
(8)
2
1=0
By mean value theorem, there exists 2/ E (0 0 0,t
with
V ( (141))
= V (0 ) + v2 (24+)) )
(o(+))))
-0 (
A,+
vʃ (1))
= = (0()) + +g (24
/
kk+
14

---

Under review as a conference paper at ICLR 2021
which yields
V 0 (
(m/gma)) V (
k.tt
Here the inequality holds by local strong convexity and the fact that z E (8)) the upper bound on the norm of the gradient, and our choice of y. Substituting back into equation we get
(0 Ri+
f(0k)
21 7
no
(1 + 7p/ gmarr)))) 1IVs (0).
?227
(9)
Imaz
((1+
19min
-1) / 00
)|
a2
L gmas
2
By our choice of n2,, we have
P9min
n2
1 +
- -1 12 122 02.
(10)
L Imax
The inequality holds since
log
1 + p4mmin
n2 log
14
p9mmmn
7202
log( n222),
L Imaz
L ginax
1220
where the first inequality holds by our choice of ri and the second inequality is an upper bound of log(1 + z). By substituting equation in equation 9 and using our assumption that
min { vs
(m)
2 Jmins
get
f
(0 ( k.t
f(0x)
Imax Imax2202 R2202 Grnin
122/1
21
(11)
(2 (2+c)
To Grnén
M 122
11
By adding equation and equation
11 we obtain
S. (ni n2)
2 (2++)
(Lo
Lo Imné
(12)
117700
6x). Using the Lipschitz property of function, we
We now provide an upper bound for Median
have
f (0x) f (0(m)))
Σ
f
(0%
(0
< Lo
1 k
(++1)
= niLoo (13)
1=0
==0
n2g -1
122 11
I (0(m)) (12a) ki+
- (0x)
(++1)
(0(0) k.+
Lo
|1o
( k.t
((0) k.t
= n2 Lov. (14)
k.t
==
1=0
Combining equation 13 and equation
14 we get
(n1 n2) (ni + n2) Imin Lo
S Median
Sx
(15)
According to the definition of our learning rate, combining equation 12 and equation 15 results in the following inequality
Sk 2 +
7/0
(16)
s
The proof is concluded using Theorem
15

---

Under review as a conference paper at ICLR 2021
D EXPERIMENTAL SETTING
In this section, we provide the detailed experiment settings. All methods are trained with batch normalization and dropout with probability 0.5 after each layer. The batch size is 128. The base learning rate is set to 0.01. Both batch size and learning rate can be adjusted but their ratio should remain constant as suggested in Smith & Le (2017); Smith et al. (2018).
D.1 MNIST
1. SGD: we train SGD for 100 epochs with a learning rate 0.01 that drops by a factor of 10 after every 30 epochs.
2. SWA: in the first 75 epochs, rate schedule with αι = 10-3 and ar2 = 10-4, where a the initial learning rate within a cycle and 0g is the ending learning rate within cycle.
the regular SGD. We then switch to cyclic learning
3. Ent:opy-SGD: we train Entropy-SGD for 20 epochs with L = 5. The learning rate for the stochastic gradient Langevin dynamics (SGLD) is 0.1 with thermal noise 10-4, The initial value of the scope is set to 0.03 which increases by a factor of 1.001 after each parameter update.
4. Srrropy-SGD-SALR the learning rate for Entropy-SOrI is updated based on Algorithm (c = 2 = 0.002).
5. SGD-SALR: we use base learning rate 0.01 and 2, 0.002.
D.2 CIFAR-10
1. SGD: we train SGD for 200 epochs with a learning rate 0.01 that drops by factor of 10 after every 30 epochs.
2. SWA: in the first 150 epochs, rate schedule with 01 = 5 x 10-4 3 and 0g = 1 x 10-4.
the regular SGD. We then switch to cyclic learning
3. Entropy-SGDD we train Entropy-SGD for 40 epochs with L The learning rate for the SGLD is set to 0.1 with thermal noise 10 The initial value of the scope is set to 0.03 which increases by a factor of 1.001 after each parameter update.
4. Srropy--SGD-AAL. the learning rate for Entropy-SCr -GDD is updated based on Algorithm (c = 2 = 0.002).
5. SGD-SALR: we use base learning rate 0.01 and 2, 0.002.
E MORE EXPERIMENTS
In this section, we have added more experimental results illustrate the performance of SALR.
1. We train LSTM network the Penn Tree Bank (PTB) dataset for word-level text pre- diction. Following the guideline in Zaremba et al. (2014) and Chaudhari et al. (2019), we train PTB-LSTM with 66 million weights. SGD and SWA are trained with 55 epochs. Entropy-SGD (L = 5) and SALR (c 2) are trained with 11 epochs. Overall, all methods have the number of gradient calls (i.e., wall-clock times). We report the word-level perplexity on the test set. Both Entropy-SGi -GD and SALR can obtain lower perplexities with much fewer training epochs.
PTB
SGD
SWA 78.1 (0.25)
Entropy-SGD
SALR 71.42 (0.14)
PTB-LSTM
78.4 (0.22)
72.15 (0.16)
Table 6: Perplexity on PTB
2. We train an LSTM to perform character-Ieve text-prediction using War and Peace (WP). We follow the procedures in Chaudhari al. (2019) and Karpathy al. (2015). We train Adam/SWA and methods have the same number of gradient calls.
with 50 and 10 epochs, respectively. Overall, all
16

---

Under review as a conference paper at ICLR 2021
WP
SGD 1.223 (0.01)
SWA 1.220 (0.05)
Entropy-SGD 1.095 (0.01)
SALR 1.089 (0.02)
LSTM
Table 7: Perplexity on War and Peace
3. We add two experiments on CIFAR-10 10 and CIFAR-100.
ResNet56
SGD
SWA
Entropy-SGD
SALR
CIFAR-I0 10
93.25 (0.04)
93.33 (0.02)
94.17 (0.01)
94.35 (0.01)
CIFAR-100
74.75 (0.02)
74.72 (0.01)
75.29 (0.01)
75.30 (0.01)
Table 8: More Results on CIFAR-10/100
4. We compare SALR with SmoothOut (Wen et al. minima by averaging over multiple perturbed copies of the landscape. We run SALR, SmoothOut and AdamSmoothOut on CIFAR-10 and CIFAR-100 five times using ResNet 44.
2018), technique to smooth out sharp
ResNet44 SmoothOut
AdamSmoothOut
SALR
CIFAR-10
92.02 (0.02)
92.15 (0.03)
92.45 (0.01)
CIFAR-I00
68.70 (0.02)
69.21 (0.02)
70.35 (0.03)
Table SmoothOut
In conclusion, SALR deliver improvement over range of dataset.
17


Reviews:
[{"review_id": "qywSDgUKPR_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes an algorithm that aims at finding a flat minimizer. The high-level strategy in the design of the proposed algorithm is increasing the learning rate when the iterate is in the region of a sharp minimizer. The authors claim that by increasing the learning rate, the iterate can get out of the undesired region. To estimate the local landscape (local sharpness), the authors provide a heuristic, which requires running gradient descent and gradient ascent for some number of iterations. The proposed algorithm has a promising result empirically, compared to entropy SGD (Chaudhari et al.) which also aims at finding a solution that generalizes well.\n\nStrength:\n\n(1) Paper is written well. The motivation is clearly explained. \n\n(2) The algorithm is easy to implement.\n\n(3) The algorithm seems to work well in practice.\n\nWeakness:\n\n(1) Compared to the empirical results shown in the paper, the theoretical result is relatively weak. My concern is that Theorem 5 does not differentiate between flat and sharp local minima. Specifically, it could be the case that the conditions of the theorem are satisfied and that the iterate generated by the proposed algorithm escapes flat minima eventually.\n\nThe paper will be in a much better shape if the theoretical result shows that the iterate escapes sharp local minima while attracts to flat minima.\n\n(2) (Computational overhead) Since the algorithm has a subroutine to estimate the local landscape, it incurs computational overhead compared to the baselines. I hope the authors can discuss this issue.\n\nMinor:\n\n(1) (Assumption 1) What are the examples that satisfy the assumption?\n\n(2) (Remark 3 and normalization in Definition 1) \nI agree with Remark 3, but the argument made in Remark 3 also implies that the normalization will reduce the sharpness value when the gradient is large, which might be an undesired effect.\n\n===\nOverall, I think this is a reasonable paper and I am happy to increase the score if the authors respond well. \n\n=== after rebuttal ===\n\nI thank the authors for the feedback. \n\nRegarding the proposed theorem, I was hoping to see if the iterate can stay in the flat minima instead of leaving the region eventually, as the constant of the local strong convexity is inside the log's, which is not very sensitive to the value (the landscape) and might be tricky to provide useful guidance to differentiate flat and sharp minima.\n\nI decided to maintain my score, but I still recommend a weak accept of this paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "o1C5et8uRlE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a simple method (SALR) to encourage the SGD to converge to flatter minima for better generalization. The basic idea is that it increases the learning rate when the sharpness is high, vice versa, such that SGD can escape sharp regions quickly. The sharpness is measured by the difference between the maximum and minimum found by a local SGD with a few fixed steps.\n\nThe paper is well written and easy to follow, and shows some interesting observations, such as:\n1. SALR can achieve a comparable accuracy using 5 times less epochs in the outer SGD. It will be interesting to see if increasing the epochs can achieve higher accuracy or not;\n2. The learning dynamics shown in Figure 4 (Right), indicating SGD escapes some local optima.\n\nHowever, there are following issues in the paper:\n\n1. discussion on connections to previous works\n\n  1.1. the sharpness in \"Definition 1\" is highly correlated to gradient magnitude. When the region is smooth, we can loosely say a larger sharpness means a larger gradient magnitude (see Figure 3). Therefore, SALR uses a larger learning rate when the gradient is large. This is contradictory to Adam/AdaGrad, which decreases the learning rate when the accumulated gradients are large. Please explain.\n\n  1.2. the motivation of increasing learning rate in SALR is to increase noise to escape sharp regions. SmoothOut [1] also injects noise to escape sharp regions, by averaging over the same neural network under different small perturbations of parameters. Please clarify the difference.\n\n2. experiments\n\n  2.1. the baselines in Table 1-3 are underperforming than expected. For LeNet, any SGD can achieve above 99% easily. The accuracy (88.44%) of ResNet-50 on Cifar-10 is also unexpectedly low [2].\n\n  2.2. Assuming SALR converges to flatter and flatter regions as it learns, we should expect the sharpness drops as the iteration goes. This is not observed in Figure 4 Right.\n\nMinor:\nThe bold highlight should go to \"5.33 (0.60)\" in the 4th row in Table 4.\n\n\n[1] https://arxiv.org/abs/1805.07898\n[2] https://benchmarks.ai/cifar-10", "extra_scores": {}, "extra_text": {}}, {"review_id": "HotIyKkJicT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method called SALR, which adeptly updates the learning rate based on the local sharpness of the loss function to escape the sharp local minimum. By doing this, the author shows that their method can enhance the generalization and converge speed during the training procedure by encouraging the network to converge to a flat minimum.\n\nThe paper provides theoretical analysis as well as empirical results to support their claim.  For the theory part, the paper gives the evidence to prove that SALR can get a better converge rate while in the empirical part, the authors test SALR on MNIST and CIFAR10 using several different network structures.\n\nHere are the pros and Cons I think in these parts. \n\nPros:\n1. The analysis of the converge rate part looks good for me. Though I do not check the proof one-by-one.\n2. The experiment covers different networks and different optimizers, which greatly shows the algorithms generalization ability in most of the gradient-based optimizer.\n\nCons:\n1. When calculating stochastic sharpness in empirical using algorithm 2, it seems that we need additional n1 and n2 steps. What is the value of n1 and n2 in empirical? This can slow down the gradient calculation speed a lot, I am worrying this can cause the algorithm very expensive to apply in many cases.\n\n2. The empirical experiment result still seems limited. \n    (1). The author only tests several large networks on MNIST and CIFAR10, which makes its generalization statement weak. Moreover, I notice that the author actually does not even test CIFAR10 on MobileNetV2. \n    (2). For the statement of faster converge speed, I can not actually see the obvious change from the empirical result from figure 4.\n\nSuggestions:\n1. Could you add more experiments on other benchmarks like CIFAR100 and even ImageNet? If it is hard, could you clarify what is the bottleneck?\n\n2. It should be good to see more ablation studies towards the converging speed in the empirical experiment.\n\n\nOverall, I think this paper gives interesting points with the theoretical analysis. However, I still think the algorithm is hard to convince me in the empirical parts. \n\n============================== Update after author's response ==============================\n\nThe additional experiments look good to me, it solves most of my concern, I would like to lift the score to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4KttAUE1U7N", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper proposes SALR, a new optimization algorithm which adapts the learning rate to avoid sharp local minimas. This is achieved by computing/approximating the sharpness at different iterations and increasing the learning rate when the sharpness is high.\n\nEmpirical tests are performed on MNIST, and CIFAR-10, showing that the proposed method works better as compared to naive SGD, and entropy SGD.\n\nStrong Points:\n+ The problem being studied is very important and can have high impact for cases such as large batch training in which getting \"trapped\" in sharp minima is a problem\n+ The paper does a good job of intuitively explaining their algorithm which adds noise in sharp regions by increasing learning rate.\n\n\n\nMajor Comments:\n\nWhile the proposed algorithm is interesting but the theoretical and empirical results provided need to be strengthened further to support the claims. In particular, please note the following:\n\n1- The empirical results are very limited. Given that the theoretical results are only for simple convex settings, a much more thorough empirical analysis would be needed to evaluate the proposed method.\n\n2- What happens if you have negative curvature?\n\n\n3- The theoretical proof provided is for simple convex problems. It is not clear how these results would extend to non-convex settings.\n\n4- What is the overhead of the proposed method in terms of wall clock time?\n\n5- How does the proposed approach compare with existing methods such as cyclical learning rate?\n\nI will look for the rebuttal and will adjust my score accordingly. \n\nSuggestions for improvement:\n\nThere needs to be a more thorough evaluation of the paper for more challenging learning tasks such as ImageNet classification, and language modeling with transformers. There also needs to be tests to show when the proposed method fails (for example strict saddle points) and how this can be avoided. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to update the learning rate dynamically by increasing it in areas with higher sharpness and decreasing it otherwise. This would the hopefully leads to escaping sharp valleys and better generalization. Authors further provide some related theoretical results and several experiments to show effectiveness of their models.

All reviewers find the proposed method well-motivated, novel and interesting. The paper is well-written and easy to follow. However, both theoretical results and empirical evaluations could be improved significantly:

1- The theoretical results as is provides little to no insight about the algorithm and unfortunately, authors do not discuss the insights from the theoretical results adequately in the paper. See for eg. R1's comments about this.

2- Given that the theoretical results are not strong, the thoroughness in empirical evaluation is important and unfortunately the current empirical results is not convincing. In particular, there are two main areas to improve:

a) Based on the Appendix D, the choice of hyper-parameters seem to be made in an arbitrary way and all models are forced to use the same hyper-parameters. This way, the choice of hyper-parameters could potentially favor one method over the other. A more principled approach is to tune hyper-parameters separately for each method.

b) It looks like the choice of #epochs has been made in an arbitrary way. For all experiments, it would be much more informative to have a figure similar to the left panel of Fig. 4 but with much more #epochs so that reader can clearly see if the benefit of SALR would disappear with longer training or not.

c) Based on the current results, SALR's performance  is on par with that of Entropy-SGD on CIFAR-100 and WP and there is a very small gap between them on CIFAR-10 and PTB. I highly recommend adding ImageNet results to make the empirical section stronger. The other option is to compare against other methods in fine-tuning tasks. That is, take a checkpoint of a trained model on ImageNet and compare SALR with other methods on several fine-tuning tasks.

Given the above issues, my final recommendation is to reject the paper. I want to thank authors for engaging with reviewers during the discussion period and adding several empirical results to the revision. I hope authors would address the above issues as well and resubmit their work.
Decision: Reject