Large Learning Rate Matters for Non-Convex Optimization
Authors: Amirkeivan Mohtashami
Martin Jaggi
Sebastian U Stich
Venue: Submitted to ICLR 2023 (2023)
Keywords: large learning rates
GD
SGD
non-convex optimization

Abstract: When training neural networks, it has been widely observed that a large step size is essential in stochastic gradient descent (SGD) for obtaining superior models. However, the effect of large step sizes on the success of SGD is not well understood theoretically. 
Several previous works have attributed this success to the stochastic noise present in SGD.  However, we show through a novel set of experiments that the stochastic noise is not sufficient to explain good non-convex training, and that instead the effect of a large learning rate itself is essential for obtaining best performance.
We demonstrate the same effects also in the noise-less case, i.e. for full-batch GD. We formally prove that GD with large step size---on certain non-convex function classes---follows a different trajectory than GD with a small step size, which can lead to convergence to a global minimum instead of a local one. 
Finally, we also demonstrate the difference in trajectories for small and large learning rates for real neural networks, again observing that large learning rates allow escaping from a local minimum, confirming this behavior is indeed relevant in practice.

Under review as a conference paper at ICLR 2023
LARGE LEARNING RATE MATTERS FOR NON-CONVEX OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
When training neural networks, it has been widely observed that a large step size is essential in stochastic gradient descent (SGD) for obtaining superior models. However, the effect of large step sizes on the success of SGD is not well under- stood theoretically. Several previous works have attributed this success to the stochastic noise present SGD. However, we show through novel set of ex- periments that the stochastic noise is not sufficient to explain good non-convex training, and that instead the effect a large learning rate itself is essential for ob- taining best performance. We demonstrate the same effects also in the noise-less case, i.e. for full-batch GD, We formally prove that GD with large step size- on certain non-convex function classes follows different trajectory than GD with a small step size, which can lead to convergence to global minimum instead of a local one. Finally, we also demonstrate the difference in trajectories for small and large learning rates for real neural networks, again observing that large learning rates allow escaping from local minimum, confirming this behavior is indeed relevant in practice.
INTRODUCTION
While using variants of gradient descent (GD), namely stochastic gradient descent (SGD), has be- come standard for optimizing neural networks, the reason behind their success and the effect of various hyperparameters is not yet fully understood. One example is the practical observation that using a large learning rate in the initial phase of training is necessary for obtaining well performing models (Li et al., 2019). Though this behavior has been widely observed practice, not fully captured by existing theoretical frameworks.
Recent investigations of SGD's success (Kleinberg et al., 2018; Pesme et al., 2021) have focused on understanding the implicit bias induced by the stochasticity. Note that the effective variance of the trajectory due the stochasticity of the gradient is moderated by the learning rate (see Appendix F for more intuition). Therefore, using larger learning rate amplifies the stochasticity and the implicit bias induced by it which can provide a possible explanation for the need for larger learning rates. We show that this explanation is incomplete by demonstrating cases where using stochasticity with arbitrary magnitude but with a small learning rate, can not guarantee convergence to global minimum whereas using a large learning rate can. Furthermore, we provide practical method to increase stochasticity without changing the learning rate when training neural networks and observe that increased stochasticity can not replace the effects of large learning rates. Therefore, it is important to study how larger learning rate affects the trajectory beyond increasing the stochasticity.
To that end, in this work we show that randomly initialized gradient descent with a high learning rate provably escapes local minima and converges the global minimum over of class of non-convex functions. In contrast, when using a small learning rate, GD over these functions can converge to local minimum instead. We note that for brevity, we focus our results on the full-batch GD.
We further show the positive effect of using a high learning rate to increase the chance of completely avoiding undesirable regions of the landscape such as a local minimum. Note that this behavior does not happen when using the continuous version of GD, ie. gradient flow which corresponds to using infinitesimal step sizes. The difference remains even after adding the implicit regularization term identified in (Smith et al., 2021) in order to bring trajectories of gradient flow and gradient descent closer.

---

Under review as a conference paper at ICLR 2023
We would like to note that throughout the paper, we sometimes misuse the terms "global" and "local" minimum to refer to desirable and undesirable minima respectively. For example when discussing generalization. a desirable minimum might not have the lowest objective value but enjoy properties such as flatness.
Finally, to show the relevance of our theoretical results in practice, we demonstrate similar effects can happen in neural network training by showing evidence of escape from local minimum when applying GD with high learning rate on a commonly used neural network architecture. Our obser- vations signify the importance of considering the effects of high learning rates for understanding the success of GD.
Overall, our contributions can be summarized follows:
Demonstrating the exclusive effects of large learning rates even in the stochastic setting both in theory and in practice, showing that they can not be reproduced by increasing stochasticity and establishing the importance of analyzing them.
Capturing the distinct trajectories of large learning rate GID and small learning rate GD in theory on a class of functions, demonstrating the empowering effect of large learning rate to escape from local minima.
Providing experimental evidence showing that gradient descent escapes from local minima in neu- ral network training when using large learning rate, establishing the relevance of our theoretical results in practice.
2 RELATED WORK
Extensive literature exists on studying the effect of stochastic noise on the convergence of GD. Sev- eral works have focused on the smoothing effect of injected noise (Chaudhari et al., 2017; Kleinberg et al., 2018; Orvieto et al., 2022; Wang et al., 202 In (Vardhan & Stich, 2022) has been shown that by perturbing the parameters at every step (called perturbed GD) it is possible to converge the minimum of a function f while receiving gradients of f g. assuming certain bounds on g. Other works use different models for the stochastic noise in SGD and use it obtain convergence bounds or to show SGD prefers certain type (usually flat) of minima (Wu et al., 2018; Xie et al., 2021). In order better understand the effect of various hyperparameters
convergence, Jastrzebski et al. (2019); Jastrzbski et al. (2018) show the learning rate (and its ratio to batch size) plays an important role in determining the minima found by SGD. In (Pesme et al., 2021) was shown that SGD has an implicit bias in comparison with gradient flow and its magnitude depends on the learning rate. While this shows one benefit of using large learning rates, in this work, we provide evidence that the effect of learning rate optimization goes beyond controlling the amount of induced stochastic noise.
Prior work also experimentally establish existence of different phases during training of neural network. Cohen et al. (2021) show that initially Hessian eigenvalues tend to grow until reaching the convergence threshold for the used learning rate, state they call "Edge of Stability". This growth is also reported in (Lewkowycz et al., 2020) for the maximum eigenvalue of the Neural Tangent Kernel (Jacot et al., 2018) where it has also been observed that this value decreases later in training. leading to convergence. Recent works have also investigated GD's behavior at the edge of stability for some settings (Arora et al., 2022) obtaining insights such as its effect on balancing norms of the layers of a two layer ReLU network (Chen & Bruna, 2022). In our results, GD is above the conventional stability threshold while it is escaping from local minimum but returns to stability once the escape is finished.
In (Elkabetz & Cohen, 2021) it is conjectured that gradient descent and gradient flow have close trajectories for neural networks. However, the aforementioned observations suggest that gradient descent with large learning rate visits different set of points in the landscape than GD with small learning rate. Therefore, this conjecture might not hold for general networks. The difference in trajectory is also supported by the practical observation that large learning rate leads to better model (Li et al., 2019).
To bridge this gap and by comparing gradient flow and gradient descent trajectories, Barrett & Dherin (2021) identify an implicit regularization term on gradient norm induced by using discrete steps. Still, this term is not enough to remove local minimum from the landscape. Other implicit regularization terms specific to various problems have also been proposed in the literature (Ma et al., 2020; Razin & Cohen, 2020; Wang et al., 2021b). In this paper, we provide experimental evidence
2

---

Under review as a conference paper at ICLR 2023
and showcase the benefits of using large step sizes that are unlikely to be representable through regularization term, suggesting that considering discrete steps might be necessary to understand the success of GD.
The type of obstacles encountered during optimization of a neural network is a long-standing ques- tion in the literature. Lee et al. (2016) show that gradient descent with random initialization almost surely avoids saddle points. However it still unclear whether local minima are encountered during training. In (Goodfellow & Vinyals, 2015) it was observed that the loss decreases monotonically over the line between the initialization and the final convergence points. However, was later shown that this observation does not hold when using larger learning rates (Lucas et al., 2021). Swirszez et al. (2017) also show that is possible to create datasets which lead to a landscape containing local minima. Furthermore, better visualization of the landscape shows non-convexities can be observed on some loss functions (Li et al., 2018). For the concrete case of two layer ReLU networks, Safran & Shamir (2018) show gradient descent converges local minima quite often without the help of over-parameetrizzaion.. Also, it was shown that in the over-parameterized setting, the network is not locally convex around any differentiable global minimum and one-point strong convexity only holds in most but not all directions (Safran et al., 2021). These observations show the importance of understanding the mechanisms of escaping local minima. We also use these observations to make assumptions that are practically justifiable.
There also exists a body of work on which properties of minimum leads to better generalization (Dinh et al., 2017: Dziugaite & Roy. 2017; Keskar et al., 2017; Tsuzuku et al., 2020). In this work, goal is to show the abilitt of gradient descent to avoid certain minima when using high learning rate. However, the argument about whether these minima offer better or worse generalization is outside the scope of this work.
MAIN RESULTS
Theoretical Proof of Escaping From Local Minima with a Large Learning Rate The need for large learning rate in practice is commonly explained based on the intuition of escaping certain local minima. However, a theoretical setting where GD escapes from local minimum and converges to global minimum is lacking. Such settings are necessary both for understanding success of GD and for analyzing the effectiveness of other optimizers. In this work, we introduce a class of functions where such behavior can be observed from GD. This is stated in Theorem which we describe here informally and leave the formal version to Section 4.1.
Theorem 1 (Informal). There exists a class of functions having at least two minima x² and x, where GD initialized on a random point, converges to x, with a large learning rate almost surely but might converge to x! with small learning rate.
Theoretical Analysis of Avoiding Local Minima As an alternative to escaping from minima, we note that due to discrete steps in GD, it may not visit any point in an arbitrary but small part of the landscape X, such as a local minimum. However, note that there may still exist a set of starting points for which GD iterates reach point in X. Therefore, assuming the starting point is chosen randomly, not visiting any point in X is a probabilistic event. In this work, we provide a lower bound for the probability of this event in Theorem 2 which we state here informally and postpone the formal statement to Section 4.2.
Theorem 2 (Informal). For any arbitrary part (subset) of the landscape X sufficiently far from the global minimum, let Ex be the probabilistic event that GD, when initialized randomly from a large enough set, will not iterate over any point in X. Then under certain assumptions on the landscape, Pr [Ex] can be lower bounded where the bound depends monotonically increasing on the learning rate and inversely on the size of X (as measured by Lebesgue measure). In particular, if X is finite, this probability is I.
The dependence of the lower bound on the learning rate is intuitive as a larger learning rate allows larger steps and makes less probable (but not impossible) to visit a small part of the landscape as illustrated in Figure 1. We note that avoiding a region is inherently different from escaping from it. In particular, as can be seen in the example, this region can be almost completely flat. In this case, once that GD reaches a point in this region, it will instantly converge. Furthermore, the region can even contain points where the function can not be differentiated. Therefore, such effect can not be compensated for by adding previously identified implicit regularization terms such the one in
3

---

Under review as a conference paper at ICLR 2023
2000
2000 small
Jeaal lerga
lange
lago
1000
1000
1000
10
(a) GD escapes with large LR.
(b) GD escapes with both LRs.
(c) GD does not escape.
Figure I: Success of GD to avoid a region based on the magnitude of learning rate when initialized from differ- ent points. While various cases are possible, it is more likely to avoid the minimum with higher learning rate.
(Smith al., 2021). This suggests other methods are needed bridge the gap between gradient flow and GD. We demonstrate both effects of escaping and avoiding local minima on an example function in Appendix H.
Importance of Large Learning Rate Despite the Effects of Stochastic Noise One possible ex- planation for the need of large learning rate the magnification of the effect of stochastic noise (see Appendix F for further intuition), facilitating escaping from local minima. While this explanation can not explain the success full-batch GD, it is more common to use SGD in practice. Therefore, this explanation makes it questionable whether it is necessary understand direct effects of learning rate on the trajectory or it enough to only consider the stochastic noise.
In this work, we show that the effects of using a large learning rate goes beyond magnifying stochas- tic noise. To that end, we first provide an example in Section 4.3 where escaping from local mini- mum and converging to the global minimum can only be achieved with large learning rate even in presence of stochastic noise. Furthermore, we demonstrate this result in practice in Section 5.1 by de- coupling the effect of stochastic noise on the trajectory and the magnitude of the learning rate when training neural networks. Our experiment results show that the effects of the large learning rate re- main crucial for converging to the correct minimum even in presence of (magnified) stochastic noise.
Demonstrating Effects Large Learning Rate Neural Networks While escaping local min- ima is an intuitive explanation, an escape is not clearly observed while training a neural network using GD with a large learning rate even though converges to a different minimum. particular, it seems GD automatically avoids cases where gets close to local minima and then escapes from it. This makes hard to verify the relevance of escaping behavior for neural network landscape. We do so in Section 5.2 by deliberately finding point close minimum that GD would converge to with small learning rate. In contrast, when applying GD with a large learning rate from this point, we can clearly observe an escape both in the trajectory and in the value of the loss.
THEORETICAL ANALYSIS
We now state our results more formally. For our theoretical analysis, we focus optimizing the minimization problem
f. := min f(x)
XER
using (full-batch) gradient descent with random initialization. For completeness, we provide a pseudo code in the Appendix A, Algorithm 1.
As is done widely in the literature, we assume smoothness (as defined in Definition 1) over regions of the landscape to ensure the gradient does not change too sharply.
Definition (L-smoothness). function f: Rdd + R L-smooth if it is differentiable and there exists a consiant L > O such that:
[Vx(x) Vf(y)) < L|[x - -ll,,
Vx, E RRd
Similarly, we need to ensure sharpness of certain regions, in particular around a local minima, to obtain results. Therefore, to ensure lower bound for sharpness in analysis, we use one- point strong convexity assumption on these regions as defined the following definition which also commonly appears in the literature:
4

---

Under review as a conference paper at ICLR 2023
Tuan:N induering Mo.
200
300-
250-
250-
200-
200-
150-
150-
1-
100
105
50-
50-
Figure 2: A case where GD keeps returning to sharp minimum showing that lower bound the distance the global mini- mum might be necessary to show it can be avoided.
(a) GD with small LR converges to the minimum.
(b) GD with large LR escapes the minimum.
Figure 3: Different behaviors of GD based on the magnitude of learning rate in escaping converging sharp minima. GD with high enough learning rate always escapes the minimum.
Definition (j--one-pointe sosene--oint-stoongyy-oommm f: Rdd a constant > 0 such that:
(OPSC) with respect to x, over M). A function R is one-point strongly convex with respect to x, if differentiable and there exists
(V)(x), x x.) 2 x.11?
Vx M.
Assuming OPSC property common in the literature. When this assumption is applied over the whole landscape, it has been shown to guarantee convergence to x, (Kleinberg et al., 2018; 8; Lee et al., 2016; Safran et al., 2021). However, this work we only make this assumption hold on limited part of the landscape, namely regions around a local minima. Furthermore, we use this assumption to ensure sharpness which we show can result escaping from the regions where this assumption holds rather than converging to them. Note that recent works have verified both theoretically and empirically that landscapes of neural networks satisfy this property to some extent (Kleinberg et al., 2018: Safran al., 2021). For example, Safran et al. (2021) show that the condition is satisfied with high probability over the trajectory of perturbed gradient descent on over-parameterized two- layer ReLU networks when initialized in neighborhood of global minimum. We also note that there exists other variants of this definition such as quasi-strong convexity (Necoara et al., 2019) or (L, ())trro)) quasar convexity (Hinder et al., 2020), which are similar but slightly stronger.
4.1 ESCAPING FROM LOCAL MINIMA WITH LARGE LEARNING RATE
We first state a lemma which is the key to proving Theorem 1. In particular, this lemma defines set of criteria for the region M around a minimum xi as well as the region around M, called P(M), that ensures GD escapes from M moving toward different minimum x.. To build further intuition, Figure provides an example of how GD with large learning rate may escape a sharp minimum. Figure 4 provides an illustration of different regions defined in the theorem's statement.
Lemma 1. Let f be a function that is and randomly initialized over set W with L(W) > Let M be a with diameter T, containing local minimum x! and define P(M) fx $ M ||x 1xx-x0 x 1l2 S /
and consider rumning GD with learning rate ?
3} to be the set sur-
rounding M. Assume f is L Lgghbol smoohh and p.. PP-OPPC over P(M) with respect to (global) minimum x, that is sufficiently far from M, formally, ||x.
x ll2 2 r 1+ / (3n -3](1 1-VI-79.
Finally, assume is UP-OPSC with respect to xt over M where n² > 21." Then, using suitable
p.,
learning rate 2/2 < 7 S 43, if GD reaches a point M, will escape M and reach a point with distance to x. of less than | xx11 almost surely.
Note that this lemma allows for multiple local minima exist on the landscape and only applies constraints around each local minimum. Furthermore, we point out that the lemma only ensures that GD will exit the local minima after some steps. In order to obtain convergence guarantees to the global minimum, it is necessary assume a convergence property well. Indeed, this is how we build the class of functions to prove Theorem 1. We provide a complete proof of Lemma I in Appendix D and proceed by discussing some of our assumptions:
the rest of the landscape as
OPSC condition inside M We assume f is OPSC with respect to a different minima inside M in order to ensure GD will escape from M. However, other conditions might also ensure the same
5

---

Under review as a conference paper at ICLR 2023
1500
x
-M)
X+
200
(M(M)
1250
PIM)
1000
500
50
250
-10.0
-5.0
0.0
Figure 4: Illustration of different regions defined
An example where convergence to global minimum can only be achieved by using both stochastic noise and large learning rate but not with either used alone.
Figure 5:
Lemma 1.
effect. The theorem would also hold with those assumptions. Note that the sharpness of M with respect the rest of landscape is reflected through the lower bound on je and is necessary we can set the learning rate in the given range. As an example, when f is quadratic function everywhere except M (such as in Figure 4), we have μ.. L and the lower bound becomes μ 2L.
OPSC condition around M We combine this assumption with the assumption on M being suffi- ciently far from the global minimum in order to ensure that once GD escapes from local minima, the gradient points strongly towards x This ensures that GD will reach a point closer to the global minimum after escaping M. While the OPSC assumption is not necessary to show GD will never converge to M and may be replaceable by alternatives, an assumption on the distance to x. might be necessary to show GD will not return M. For example, consider quadratic function where the region around minimum is replaced by sharper quadratic function, as plotted in Figure 2. In this case, GD with high learning rate will keep returning M though will never converge to it. As alternatives to OPSC assumption number of steps (which Corollary states can not to any point in M almost surely) or assume directly that the gradient points strongly away from M. Finding similar assumptions is grounds for future work.
P(M). one can assume GD converges in at most fixed
Given Lemma 1, it can be seen that if is possible to ensure the iterations of GD get closer to the global minimum on the of the landscape, is possible to ignore existence of the region M. This is because either the iterations would never cross M or if they do, they will eventually reach a point closer to the global minimum according Lemma We build the class of functions for Theorem based on this observation. We now state the formal statement of Theorem and leave the proof to Appendix E.
Theorem 1 (Formal). Consider any function f that is L-smooth and p4- PP-OPSC with respect to the global minimum x, in its landscape except on a region M containing a local minimum xt satisfying the conditions in Lemma 1. GD initialized randomly inside M converges to x! with In contrast, GD initialized randomly over any arbitrary set W with positive Lebesgue measure L(W)= > will instead converge to x, with a large learning rate 1 almost surely.
small learning rate 7 < T "one"
4.2 AVOIDING LOCAL MINIMA
The following key lemma used to prove Theorem 2.
Lemma 2. Assume gradient descent is initialized randomly on the set W and is run with learning rate ? S 21' Let X E Rd be an arbitrary set of points the landscape. Assume f is L-smooth over Rd XX. Let L(S) denote the Lebesgue measure of any set S. The probability of encountering any points of X. in the first T steps of gradient descent, i.e. X; E X for some 1 < < T is at most +))+ ((X)
C(W).
We provide the complete proof in Appendix B. Note that the lemma makes assumption over X. Furthermore, the dependence of the bound on seems inevitable in general since the opti- mization might force the iterations toward certain regions, such the region around the minimum.

---

Under review as a conference paper at ICLR 2023
When using standard GD, by making assumptions the landscape to ensure the iterations of GD move away from the undesired region X, the bound can be instead adapted to depend inversely on the learning rate which controls the speed of progression. We use such assumption to prove Theorem which we state formally here and leave its proof to Appendix C.
Theorem 2 (Formal), Let X be an arbitrary set of points. Assume f is L-smooth and p. P.-OPSC with respect to a minima 2, & X over R. X. Define cx [n x - x.
E X and Tw == sup[lix x+Il x E W.. The probability of not encountering any points of X during
running gradient descent with y S fx is at least 1 24 rw 1uge 2007 ((X) Z(W)
when cx S rw
and is 1 otherwise.
4.3 IMPORTANCE OF LARGE LEARNING RATE DESPITE THE EFFECTS OF STOCHASTIC NOISE
We now consider the of SGD where the stochastic noise is applied additive term to the gradient. The update step of SGD in this case would be:
X == X 7--7((V/) (V)((x) Et)
(3)
For example, when the global objective f(xx a finite sum of n different objectives, e-g. one for each data point, we will have & == VSr, (x) fxx where ry is the index of data point used in t-th step.
In this section we consider the case where the noise &, is drawn from a uniform distribution Uniform(-o; or) and assess the convergence point of GD on an example function plotted in Fig- ure 5. This function contains local minima x' and a global minimum I.. Optimally, we would like ensure convergence to the global minimum regardless of the initialization point. We now show that this is not possible using small learning rate regardless of the magnitude of the noise. However, we show that when using a large enough learning rate alongside the stochastic noise, is possible to obtain the desired result. We state this in the following proposition and leave more formal description and its proof to Appendix G.
Proposition Consider running SGD on the function plotted in Figure If the learning rate is sufficiently small, starting close to x², the iterates will never converge to the optimum x, nor to small region around it regardless of the magnitude of the noise. On the other hand, by using a large learning rate, given that the stochastic noise satisfies certain bounds, GD will succeed to converge to the optimum v, given any starting point.
EXPERIMENTS
We now provide practical evidence show the effects of high learning rate also apply and are essential in optimization of neural networks. In our experiments we train a ResNet-18 (He et al., 2016) without batch normalization on CIFAR1O (Krizhevsky & Hinton, 2009) dataset.
5.1 DISENTANGLING EFFECTS OF STOCHASTIC NOISE AND LEARNING RATE
As can be seen from (3), reducing the learning rate would also reduce the variance of the effective stochastic noise > This entanglement makes hard to assess the effects of stochastic noise and large learning rate separately. We design the following method to maintain the level of noise when reducing the learning rate.
SGD with Repeats In order to simulate the same magnitude of noise while still using smaller learning rate, every time a mini-batch drawn, we use it for steps before drawing another mini- batch. Note that when the bias of the mini-batch to be amplified k times, so when reducing learning rate by &/ the overall magnitude remains unchanged. This is explained in more detail in Appendix F.
we recover standard SGD. Re-using the same batch times, allows
We compare standard SGD with learning rate 0.01, standard SGD with learning rate 0.001, and SGD with &- = 10 and learning rate 0.001. We apply 0.0005 weight decay, 0.9 momentum, and decay the learning rate at epochs 80, 120, and 160 by 0.1. Results without momentum are reported in Appendix M. When training with standard SGD and learning rate 0.001 we train the model for 10 times more epochs (2000 epochs) in order to obtain a fair comparison and rescale its plot to 200 epochs. In this case, learning rate decay happens at epochs 800, 1200, and 1600. Note that
7

---

Under review as a conference paper at ICLR 2023
63-
0.01 Stanfford
0.01 Standard
73-
y- 0.001 Resicats
y- 000001 Ropeats
70
120
150
200
150
150
200
(Kormaized) Epsch
(oormalzed) Coech
Figure 6: Comparsion between performance of SGD with different learning rates. The gap in performance between large and small learning rates, even after repeatedly using the same batch to maintain the effect of stochastic noise, suggests that learning rate has an effect on trajectory beyond controlling stochastic noise. Re- peating batches is turned off at epoch 200 and 10 additional epochs are performed (green). For the experiment with 2000 epochs (orange), the plot is normalized to 200 epochs.
when running SGD with k = 10 repeats, we perform 10 steps using each batch while going through the whole dataset at each epoch. Therefore, the total number of steps in SGD with k: = 10 is the same as standard SGD with 2000 epochs. Furthermore, when we have k model for 10 more epochs at the end and use each batch only once (as in standard SGD) during the additional epochs. We perform these additional steps since training for several steps on one batch at the end of training might lead to overfitting on that batch which is not desirable for test performance. In Appendix K we also experiment with turning off repeats earlier in the training and observe no significant improvement. Finally, we ensure that the experiment with k = 10 uses the same initialization point and the same ordering of batches used for training with learning rate 0.01.
we train the
The results (averaged over runs) are plotted in Figure 6. The first clear observation that SGD with learning rate 0.01 leads to much better model than SGD with learning rate 0.001. More importantly, while amplifying the noise through repeats helps lower the gap, still has performance below training with the large learning rate.
Explaining the positive effect of using SGD over GD convergence has been the focus of several prior work. For example, Kleinberg et al. (2018) argue that applying SGD allows optimization to be done over smoothed version of the function which empirically satisfies good convergence prop- erties, particularly, one-point strong convexity toward a minimum. We argue that our observation provides a more complete overview and suggests that even after applying stochastic noise (which for example can lead to smoothing of the function), there might be certain regions of the landscape that can only be avoided using a high learning rate. As we described above, one can consider the effect of stochastic noise to be the improvement observed when using repeats with small learning rate in comparison with training in a standard way which still does not close the gap with training us- ing a high learning rate. Therefore, the effects of using high learning rate, such as those described in Section& 4, are still important in determining the optimization trajectory even in stochastic setting.
5.2 COMPARING TRAJECTORIES OF LARGE AND SMALL LEARNING RATES
In Section 4, proved some of the effects of using large step sizes in avoiding escaping certain minima in the landscape. We now demonstrate that these effects can be observed in real world applications such as training neural networks. To be able to observe the effect of large learning rate more clearly, we first warm-start the optimization by running SGD with a small learning rate 0.001 with A: 10 repeats (as described in Section 5.1) for 20 epochs to obtain parameters Xwarm We do this to get near a minimum that would be found when using the small learning rate. Then, we start full-batch GD from Xwann with two different learning rate 0.001 (small) and 0.01 (large). We do not apply momentum when performing full-batch GD but apply 0.0005 weight decay. However we did not observe any visible difference in the results without weight decay. Similar to (Li et al., 2018), we obtain the first two principal components of the vectors Xi Xo, X2 Xo, ... ,,, Xo and plot the trajectory along these two directions in Figure 7. We can clearly observe that GD with a large learning rate changes path and moves toward a different place in the landscape. GD continues the different path even when the learning rate is reduced back to 0.001 after 400 steps. Furthermore, looking at the loss values, can observe peak the beginning of training that closely resembles
8

---

Under review as a conference paper at ICLR 2023
P=0.00 0.001
large
yreduced 0.053
-02-
-04
Than
-066
2-
-08-
-10-
0.6
PC3
(a) Trajectory of (full-batch) GD with small and large learning rate.
(b) The value of train loss when using different values of learning rate.
Figure 7: Behavior of GD for learning rates 0.001 (small) and 0.01 (large). The initialization is obtained by warm-starting the network using SGD with small learning rate 0.001. Using a large learning rate changes the trajectory sharply and even if the learning rate is reduced again after several steps (blue line) move toward a different direction in the landscape. This is accompanied by a sharp increase of loss at beginning that can be attributed to GD escaping from local sharp region in the landscape.
what we expect to observe when GD is escaping from a local sharp region. This clearly shows that these behaviors of GD are not merely theoretical and are also relevant in real world applications.
Note that while do not observe similar high spikes in the loss in the next steps, we conjecture that this behavior of escaping sharp regions is constantly happening throughout training. This is also confirmed by observations (Cohen et al., 2021) which show sharpness increases throughout train- ing until reaching the threshold 2 where is the learning rate. GD will then oscillate between being sharper and smoother than this threshold. As result of constantly avoiding sharp regions, symptoms of an escape such as a spike loss not observed. While we observe smaller increases in the loss, these can be due to oscillations also observed in (Cohen et al., 2021) along the highest eigenvectors which are not the same as escaping. Results in the same work show that in these cases the param- eters do not move in these directions and only oscillate around the same center. Developing better visualization techniques or identifying other effects of using high learning rate on GD's trajectory can help explain this behavior further and both of these directions ground for future work.
FUTURE WORK
Obtaining further insight on how GD avoids locally sharp regions, for example by developing better methods for visualization of the landscape and trajectory, is grounds for future work. Furthermore, there are various extensions possible the theoretical results obtained in this paper. For example, it might be possible to show other effects of using a large learning rate on trajectory that facilitate escaping from local minima. Finally, obtaining similar results with relaxed set of assumptions would also be an interesting direction of research.
7 CONCLUSION
In this paper, we highlight that high learning rate can provably lead to avoiding or escaping local minima and reaching global minimum. Based on this result, argue that analyzing GD with infinitesimally small learning rate is not sufficient to understand its success unlike what was suggested in prior work (Elkabetz & Cohen, 2021). Furthermore, by designing method to amplify stochastic noise without increasing the learning rate, we disentangle the effects of stochastic noise and high learning rates. We observe that while higher stochastic noise leads to better model, it is not enough to close the gap with the model obtained using a high learning rate. Therefore, we argue that the effect of learning rate goes beyond controlling the impact of stochastic noise even in SGD. In contrast, recent works on analyzing success of SGD focus on continuous settings (Xie al.. 2021) and only take step size into account when modeling the noise (Pesme et al., 2021). We hope that our results will encourage future work on large step size regime. Finally, we demonstrate that the escape from sharp regions can happen in training of neural networks, hence signifying the relevance of the effects of large learning rate in real world applications.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding Gradient Descent on Edge of Stability in Deep Learning, June 2022. URL http: http:://///iiv.///a org/ abs math].
wwtg:og////beaeeeee 2205. 09745, S3iv:2205.099445 [es,
David G. T. Barrett and Benoit Dherin. Implicit gradient regularization. In 9th International Conference on Learning Representations, ICLR 2021. Virtual Event, Austria, May 3-7, 2021, 2021.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jen- nifer T. Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. 5th International Conference on Learning Representations ICLR 2017. Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Lei Chen and Joan Bruna, On Gradient Descent Convergence beyond the Edge Stability, June 2022. URL http:/ / /arxivi wttpg/////////// 2206 04172. arXiv:2206.044 04172 [cs, math, stat].
Jeremy M. Cohen, Simran Kaur, Yuanzhi Li, J. Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In 9th International Conference on Learning Representa- tions, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 1019-1028, 2017.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the Thirty- Third Conference on Uncertainty Artificial Intelligence, UAI 2017, Sydney, Australia, August 1 1-15, 2017, 2017.
Omer Elkabetz and Nadav Cohen. Continuous vs. discrete optimization of deep neural networks. In Advances in Neurul Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6- 14, 2021, virtual, pp. 4947-4960, 2021.
Tan J. Goodfellow and Oriol Vinyals. Qualitatively characterizing neural network optimization prohlems. In 3rd International Conference on Learning Representations, ICIR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770 778, 2016. doi: 10.1109/CVPR.2016.
Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni. Neat-optimal methods for minimizing star-convex functions and beyond. Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Gruz. Austria], volume 125 of Proceedings of Muchine Learning Research, pp. 1894-1938, 2020.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernl:: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréul, Canada, pp. 8580 8589, 2018
Stanislaw Jastrzebski, Zachary Kenton, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos J. Storkey, On the relation between the sharpest directions of DNN loss and the SGD step length. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Stanisaw Jastrzbski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima SGD. arXiv:1711 04623 Jcs, stat), 2018
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 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does SGD escape local minima? In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 Stockholmsmässoon Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 2703- 2712, 2018
10

---

Under review as a conference paper at ICLR 2023
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent converges to mini- mizers. (002.0460004491 [cs, math, stat), 2016.
Aitor Lewkowyez, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. ArXiv preprint, 2ass20033022114 2020.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems 31; Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 6391-6401, 2018.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pp. 11669-11680, 2019.
James Lucas. Juhan Bae, Michael R. Zhang, Stanislav Fort, Richard Zemel, and Roger Grosse. Analyzing Monotonic Linear Interpolation in Neural Network Loss Landscapes, ArXiv preprint, abs/2104.11044, 2021.
Cong Ma. Kaizheng Wang. Yuejie Chi, and Yuxin Chen, Implicit regularization in nonconvex statistical es- timation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolu- tion. Foundations of Computational Mathematics, 20(3)451-632, 2020. ISSN 1615-3375, 1615-3383. doi: 10.
I. Necoara, Yu. Nesterov, and F. Glineur: Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1):69 107, 2019. ISSN 1436-4646.
Antonio Orvieto, Hans Kersting, Frank Proske, Francis Bach, and Aurelien Lucchi. Anticorrelated noise injec- tion for improved generalization. arXiv:2202.0288 [cs, math, stat], 2022.
Scott Pesme, Loucas Pillaud-Vivis and Nicolas Flammarion. Implicit bias of SGD for diagonal linear net- works: a provable benefit stochasticity. In Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 29218-2299999 292300, 2021.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. In Advances in Neural Information P Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Itay Safran and Ohad Shamir. Spurious local minima common in two-layer relu neural networks. In Proceedings of the 35th International Conference on Machine Learning, ICML. 2018, Stockholmsmässcnn, Stockholm, Sweden, Jul 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 4430- 4438, 2018.
Itay Safran, Gilad Ychudai, and Ohad Shamir. The effects of mild over paramerrmtttiinnaoonn on the optimization landscape of shallow ReLU neural networks. arXiv:2006.0100 {cs, stat), 2021.
Samuel I.. Smith, Benoit Dherin, David G. T. Barrett, and Soham De. On the origin of implicit regularization in stochastic gradient descent. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Grzegorz Swirszez, Wojeiech Marian Czamecki, and Razvan Pascanu. Local minima in training of neural networks. arXiv:1611.00 160310 (cs, stat], 2017.
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Normalized flat minima: Exploring scale invariant defini- tion of flat minima for neural networks using pac-bayesian analysis. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 9636-9647, 2020.
Harsh Vardhan and Sebastian U. Stich. Tackling benign nonconvexity with smoothing and stochastic gradients. arXiv:220200052 [cs, star), 2022.
Xingyu Wang. Sewoong Oh, and Chang- Han Rhee. Eliminating sharp minima from SGD with truncated heavy- tailed noise. arXiv:2102.04297 (cs, math, stat), 2021a.
Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large I learning Rate Tames Homogeneity: Conver- gence and Balancing Fffect.. ArXiv preprint, abs/21 10.00677, 2021h.
11

---

Under review as a conference paper at ICLR 2023
Lei Wu, Chao Ma, and Weinan E. How SGD selects the global minima in over-parameterized learning: dynamical stability perspective. Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NewrlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8289 8298, 2018
Zeke Xie, Issci Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradi- ent descent exponentially favors flat minima. In 9th International Conference on Learning Representations, JCLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
12

---

Under review as a conference paper at ICLR 2023
A GRADIENT DESCENT WITH RANDOM INITIALIZATION
Algorithm 1 Gradient Descent with Random Initialization
1: Pick Xy randomly from the set W.
2: for 1....P do
3: X₁ f- Xt-1 (VX(x--1)
4: end for
B PROOF OF LEMMA
Lemma. Assume gradient descent is initialized randomly on the set W and is run with learning rale & S zt- Let X Rd be the of points that should not be encountered by GD and assume L-smooth over Rd X. Let L(S) denote the Lebesgue measure of any S. The probability of encountering any points of X in the first T steps of gradient descent, i.e. X; E X for some 1 S TT is at most 21 2(8)
D(W)
Proof. Define gxx) == x>=x>V(xx When y < since f is I-smooth over Dy :R X, results of Lee et al. (2016) show (xx is a diffeomorphism over Dg. As result, the function g" obtained by applying g for T times also a diffeomorphism over the set
Drr = Rd UX (X)U....) (x)
According to the change of variable formula for Lebesgue measure (for example, see (Bogachev, 2006, Eq. (3.7.2))), for any measurable set Y C DDr
(Y)) = / Idet Vg (y))dy.
Since 7 S 1. we have for any y E Dg,
27.
det Voly) = (
The last equality holds because smoothness ensures all eigenvalues fx) are at most L. So for any eigenvalue X 1 γd, 1-2 Using this result, also can obtain det Vg"(y) 2 2- for any E Dgr. Thus, we have
C(g² (Y)) 2 2 TdL))
which means,
(x)))) < 2Tdd((X)
Note that while the above argument works for T 2 1, the former inequality also trivially holds for = 0. Hence
T c((o') (()
T
2dd ((X)
1=0
C(X)
2nd
1=0
(T+ (T())
where in the last inequality we used 2 + + .T. < this result.
T+,, The theorem follows directly from
13

---

Under review as a conference paper at ICLR 2023
The following corollary directly follows from Lemma 2. We use this corollary in proving Lemma to avoid cases where we directly land on a minimum with V f =0
Corollary 1. Let I be smooth. If X is a set with ((X) = O, for example when it is finite set of points, the probability of encountering X throughout training with gradient descent using ? S 2L and random initialization over set W with L(W) > 0 is O.
C PROOF OF THEOREM 2
Theorem. Let f L-smooth and Hu-OPSC with respect to a minima 2, over Rd \ X. Define cx = inf x.ll x E X} and := supllix x. W). The probability of encountering any points of X during running gradient descent with 7 S Hy is upper bounded by
2 m Te.)
((X) when cx I rw and is zero otherwise. C(W)
Proof. Due μ., -PSSC property of the landscape over 12 X, long x2 & X, we have
Xx+1
x. 12 = x [xx( x1112
|| x+112 - 27 (V ʃ (xxx)) -x--x xx) + [
< (1 2nμ. 7²2 3/\2)||xx - -1,+11
I (1 72pu, 11 [1xx)) x 11
I (1 )/,))/x x. 112
where the last inequality holds because # Hence, if x, $ X for 1 [ 1]. have
||xT x, 112 S (1 - -/p=)² ( x1
S (1 - 7ppk.)) "rop rw
ex log2 Fir
Let To = log, (1 (1-7p.) For > To. we have
X 5
<xx,,
which means Xy & X. Therefore, if GD does not reach any point in X in the first To steps, it will not reach any point in X afterwards neither. Therefore, probability of encountering any point in X is the same as the probability of encountering such points in the first To steps. According to Lemma 2, this value bounded as:
2lo+
((X) Z(W)
2d
CX lops (1- vo+)
((X)
TW
C(W)
2d
FW
1oog
(1- 79
((X)
CX
L(W)*
D PROOF OF LEMMA
Lemma. Let I be a function that is SmgthhatSmooth and consider running GI) with learning rate randomly initialized over a W with L(W) Let M be set with diameter т, containing
local minimum x² and define P(M) fx M
||x -xx x112 S 2 3} to be the set sur-
rounding M. Assume J. is L < Legobaa-smooth and Po-OOPC over P(M) with respect to (globul)
14 / "haa (11--1330133111 1-VI-
minimum X, that is sufficiently far from M, formally, ||x. x ll2 2 r
Finally, assume is -PPOPSC with respect to xf over M where n² > 21 Then, using suitable
p.
learning rate 2 < S 44, if GD reaches a point M, will escape and reach a point with distance to x. of less than Ixx x+I| almost surely.
14

---

Under review as a conference paper at ICLR 2023
Proof. Let t be the smallest step where E M. Using Corollary 1, X, # xt almost surely.
Therefore ||x; x O. Since y > At, we have
X++1 x 112
|X5 [V((x) ) - x1
X x 11 27 f x x))
2 X xi1 113
= X x 12
- x (12))
N X x 12
(2221///000000000 - x'112 - 21|x; x (2)
2 | x 12
V (xx ||2|||| -
7
(4)
||x, x 112 + 7p xx x 11((ruu 2)
1 (2 1 - 3)|[x - -x112
0 and (B) is obtained by using the lower bound yul > 2. Therefore, the distance to x grows at least with the rate 27/²² - 3 > 1. Hence, GD is guaranteed to reach point X outside M for some & > If ||x++ - x.Il S ||xt x.Il - T, we are done. Otherwise, we verify that this condition holds for Xi+k+1-
where (A) holds because y/ -
First note that
||xc+k x 11 X1+k-1 - -V/((x+*>> x111
= X1+k-11 - x - 27 (V)(x Xe+k-1 + +
1 - -x'11 - 271² + L22obba)
S (2 - 27/u' + +, Liahhal)
S (r² Lgiobal - 3)
where the last inequality holds because 7 > n²
[x++++1 - x.112 = 1 (x(+++++)) - x.11
||x+ x+113 27 (V (V](xx+));xx+E X x.) +721 1 ( (x++
1 x. 112 27/44 + +
| x+ x+11(11 7//=);
where in the last inequality we used 7 s 4t We can now write
[xx+2+1
x. 122 < (|xx x. lll + |x(+ x (12) / 7.
z [|xt x. ||2 + r / 7/2 2 L - 3) /1 - 7/p
Given the lower bound on distance ||x| - -x, we have
r(y (7 global 3)(1 yp.) 1) S ||xt 1xx1x11((1 / v1.)
This yields
|x+4+11 x. S |xxt x,
completing the proof.
E
PROOF OF THEOREM 1
Consider any function f that is T-smooth and -OPSCCC with respect to some minimum x, in its land- scape except on region M containing a local minimum xf satisfying the conditions Lemma 1.
GD initialized randomly inside M converges to xf with a small learning rate 7 < 1
n²
but will
instead converge to x, with large learning rate 2 < 7 S # almost surely.
15

---

large learning rate satisfying , < 7 S + Furthermore, we allow initialization over any arbitrary In this case, for each iterate, Under review as a conference paper at ICLR 2023
_²
Proof. When GD is initialized inside M and the learning rate is small satisfying ? we have -PPOPSC and Smgothessmootnnesss inside M, the iterates will satisfy
since
||x+11
x11 |xx [Vx(x, x!
= | x! 11 2x (V - - +
(1 27p² + - elobal ||||||xxxx -x112
$ (1 7(2n² -- globbal)) )) x1112
(1 )|1) - -x xx112
Therefore, GD will converge to xl. Let us now consider case when GD instead applied using
set (instead of only subsets of .M as long as they satisfy L(W) > X₁ M, similar to above we have
[Xx+1 - x. 12 & (1 >xx)lxx+ x,tarl1.
If X, E M, Lemma 1 shows that there exists k > 0 such that X M and ||x++* x. 1 is less than distance of any point distance to decreases. Therefore, for any >'> + k this distance ||x, x, remains less than the distance of any point in to X.. This guarantees that Xy & M. Hence the distance to x, keeps decreasing which means GD will converge x..
to x.. Since X++# & M the above argument holds and the
F EFFECT OF LEARNING RATE ON STOCHASTICITY
Let us focus on the case where f(x) is the finite-sum N Em fi(x). Then, using large learning rate kn, the iterates would satisfy
X X,
-x ((V),,()) Vs(())).
(4)
Let assume that the deviation direction of each data point from the true gradient changes very slowly, i.e. the functions f; f are extremely smooth. Then, using a smaller learning rate we instead have
X
Frees (xe-i)
(x(++)))
(ren()) - v((x))))
k-1
[x(++))
Σ (Vrrn)())) Vs(x,)).
1=0
1=0
To compare the strength of noise each case we can for example compare the variance the right hand side. Let x² == N (V,(x)) - vx(x,) Then, the variance when using the large learning rate would be o22 When using a smaller learning rate and sampling at each step to obtain r. the variance is instead ko² and is therefore reduced. However, using SGD with repeats, i.e. using Tzti = rs for S i < 1-1, we recover the same variance as the large learning rate. Therefore, using SGD with repeats, allows maintaining the same level of noise while still using smaller learning rate.
G PROOF OF PROPOSITION 3
We first state the following key theorem which describes criteria ensuring escaping from or staying around minimum:
16

---

Under review as a conference paper at ICLR 2023
Theorem 4. Let M be ball with radius centered at minimum x² and assume f is Lm-othhth over M and pCOOPSC with respect to x!. Consider running SGD with a small learning rate n S
1² Assume that when running SGD such that the oracle noise is bounded 203
Eig (xx(f(x)) o² o².
Furthermore assume that for some S 1 we have Pr [ll. 1 > 0for all E M. Assume SGD reaches a point in M. Ifo² < 22,² it will remain in M with probability al least 2 On the other hand, if c²202 2
2-mpT
7 p² + e for some >> 0 it will escape M almost surely.
Proof. Let & denote the parameters an iteration such that x, E M. We have
E x
x2 ||x x1| 2 (Eg,, X, x 2 ge 11
||x x|1 || 27 (V((x,), x, x + V +2200
< ||x, - x x113(1 27'²' + + + +
S (1(11 Tul +
< <1 Yp 2
Thus, using Markov inequality we have
Pr [[]x++1 - -x < 1- 74f
1
2
which shows the claim. On the other hand, let := probability least p > 0 have
:= Pr [ll.: - V c.o.j. Then with
||x++1
x 112
||xe (xx(x)) x1 7(8 v((())))
X - x! x112 27 (V](x)), x, x!) ( (= VX(xx)1
2 X - x! 1 2 /X
X2 - x + -
N | x + -1tp:///////t///1------2----///1
2 Xt - x 11 + /111/////x)/)lxlxxxx>>>>>
- 22700
Z || 1 x! x1 + 7/ |x: - 11112 2) 22200²
M X x! x112 + > 2) + 2y +6
N X x! x1113 ++++ 1
This means the distance xi grows least with the constant e. Let q == =. Therefore, with probability at least p", one of x.+1..... Xt+g will be out of M. This holds for any consecutive iterates. Partitioning the iterates to parts of consecutive iterates of size q, each part has positive probability of containing a point outside M. Therefore SGD will reach a point outside of M almost surely.
The function plotted in Figure 5 can be formally defined as follows:
f1()) == 86400 a) (2.9 a)²) 2.9
/2(1) = 3((x + (3)
fa(z) = 300(2 3.1)² + f2(.1)
x2
x 2.9
f1(
293
fx)
f2(x)
3<
fa(x)
3.1
450 * ((1)2 -0116) + fa(..7
3.7 <x
17

---

Under review as a conference paper at ICLR 2023
with a 2.9
22.9 360
and 3 86410000(3 a.).. This function satísfies the following properties:
fun is 2-smooth over {z 2.9}.
Jm is 900-OPSC towards 4.1 and 900-smooth over {x 1..7 < x).
Ji is 4.5-OPSC towards 4.1 over {<r 3.108 < x).
We now proceed to proving Proposition 3, stating it formally here:
Proposition 3. Consider running SGD on Sin with stochastic noise &. drawn i.i.d. at each step from the uniform distribution (riform((ooo)) If the learning rale is small such that it satisfies < 30 the algorithm will not converge to F. for some set of initialization points with positive Lebesgue measure. In contrast, with a large learning rate satisfying 0.4 S 7 0.5 it possible to choose a such that the algorithm will converge to almost surely.
Proof. Assume 7 <
1 Consider the case where the algorithm is initialized inside M1 = {ar 900
3.7 < x < 4.5}. Then if a satisfies o² < 900 0.4² it will remain in M1 with positive probability according Theorem 4. According to the same theorem, If this bound is not satisfied, then we have o" 2 2-2-2.9² which means any time SGD reaches point in M, := {ar 2.9 < 2.9), it will escape from it almost surely within constant number of steps. This means that the algorithm will never stay close to x. forever or for an arbitrarily long number of steps.
Now consider the case where the learning rate is large enough. Choose such that 5.1 < a < 5.5. Note that if the iterates reach the set {a 22.9 < 2.9) they will never exit it since we have
I (2x &t)
[(1 2y) E - (1 - +
S (1
+ 27
2.9.
We will now show that from any other point there is a positive probability of reaching the range [-2.9, 2.9]. This fact combined with the almost sure guarantee of not escaping from [-2.9, 2.9]. proves that the algorithm will converge to this set almost surely.
Note that fu is 4.5-OPSC towards x = 4 over the set {a 3.108 < x}. Since > 0.45, it can be seen from the proof of Lemma 1 that SGD will continue get further from this set. Furthermore, given the direction of the gradients it is clear that the iterates would alternate between being less and more than 4. Therefore, some point, the iterates will exit this set reaching a point Hy < 3. 108. Note that with a positive probability, the noise will not interfere with this escape since there is at least 0.5 probability that the noise is aligned with the gradient direction.
while it is in
3.1 < x 3. 3.108, the gradient value is less than Since a > 5.1 there is a positive probability of moving to the region x < 3.1. When 2.9 < < 3.1, because of the positive probability of alignment between the gradient and the noise, SGD will move to x < 2.9 with positive probability. Finally, given the smoothness of the region < 2.9, if x < 2.9 SGD will converge toward
r, = 0, ultimately reaching the region 2299 < x < 2.9 with positive probability. This completes the proof.
H TOY EXAMPLE
In order to demonstrate the effects discussed in Section 4. we experiment with running GD over simple function. The landscape of this function is plotted in Figure 8a and its formula is presented in Appendix I. The function has two minima, one near the initialization and one further away. Since the near-init minimum is almost completely flat, i.e. gradient is constant and equal to zero (except for the edges which are extremely sharp lines order to ensure the function remains continuous), GD reaches point in this region, it will remain there. However, as this region is very close to the initialization, Lemma (more particularly Corollary 2) suggests that GD with large enough learning rate, will probably not reach any points in this region. To demonstrate this more clearly, plot the trajectory of GD from several initialization points in Figure It is worth noting that even with large learning rate it is possible for GD to get stuck in this region while it is possible avoid this
18

---

Under review as a conference paper at ICLR 2023
2000 4
initialization range
1.0
sharp minimum
1500
global minima
0.6
global minimum
1000
sharp minimum
near-init minimum
roto
0.2
0.0
10-2
lcarning rate llo scale)
(a) Landscape of function
(b) Distribution of convergence to each minima
Figure 8: The function used in toy experiments which has two local minima, a mostly flat minima near initialization points and a sharp minima furtherr away. It can clearly observed how as the learning rate grows the two effects of avoiding parts of the landscape and escaping sharp minimas allow GD to converge to the global minimum.
region even with a small learning rate. However, as suggested by our theoretical upper bound, the probability of this phenomenon increases with the learning rate.
The other minimum is much sharper than the of the function and therefore escaping behavior similar to the one described by Lemma 1. This behavior is demonstrated in Figure 3. Note that unlike the previous case, GD with large learning rate always (except when landing directly at the minimum) escapes the sharp minimum while GD with small learning rate converges.
expect
We measure rate of convergence of GD for 100 different random initialization to each of these three regions for different learning rates. The results are plotted in Figure 8b. We observe that as the learning increases, the rate avoiding the near initialization minimum increases. While the learning rate is not still high enough, GD will converge the sharp minimum while the learning rate increases further, is also able to escape the sharp minimum and converge to the global minimum. This behavior is completely compatible with what be expected based the results and effects discussed in Section 4.
I FUNCTION FOR TOY EXAMPLE
- 1600((z 2.5) 2000(2 2.5)* + 800(x 2.5)3 1020(r 2.5)2
2 x 33
1411.2 (1- (1-10((z 8.4))
8.4 x S 8.40001,
f(z)
8.40001 S 8.59999,
1479.2 x (10 8.6) +1)
8.59999 $ x $ 8.6,
20
otherwise.
J 2D TOY EXAMPLE
To build more intuition and show the effect of large learning rate extends to multi-dimensions. we also provide toy example on 2D. Figure shows the landscape of our toy example which contains four local minima that are also sharp. Consider GD initialized randomly
the region W = (xx y) 3 5 x, < 4). Then, using a small learning rate GD will converge to the minimum in the region [1.2] x []. However, using larger learning rate allows escaping that minimum. Increasing the magnitude, GD can also jump over the minimum completely. In these cases, GD will converge towards the global minimum at (0,0).
19

---

Under review as a conference paper at ICLR 2023
15
Figure 9: The landscape the function f(z v) = x² + y² 200ReLU ReLU(l - Re
|x) (2 (y]))
K RESULTS OF STOPPING REPEATS FROM DIFFERENT EPOCHS
In Section 5.1, we explained that at the end of training we stop using the same batch for & steps and train in the standard way (each batch used just once) for additional 10 epochs. This was done to make sure the model that is used to obtain the accuracy on the test data not overfitted on one hatch which might be more likely to happen the end of the training. In this section, we also experiment with stopping repeats, i.c. using the same batch for & steps, earlier in the training. The result is plotted in Figure 10. No significant improvement observed.
90
80
Accuracy
70
y= 0.01 Standard
y= 0.001 10 Repeats (Until 201)
60
y= 0.001 Standard 2000epoch
0.001 10 Repeats (Until 71)
50
y= 0.001 10 Repeats (Until 101)
0.001 10 Repeats (Until 131)
40
50
100
150
200
Figure 10: Plot of test accuracy when stop using the batch several times (doing repeats) different epochs. can be clearly observed stopping epoch does not affect the final accuracy and gap with the case of GD with a large learning rate can be clearly observed.
EXPERIMENTS ON CIFAR 00
In order to make sure results extend to other scenarios, repeat the experiments in Section 5.1 on CIFAR 100 and observe a similar behavior. The accuracy on the train and test datasets during training plotted in Figure 11.
20

---

Under review as a conference paper at ICLR 2023
100
50
Test Accurac)
40
30-
85
Train
80
= 0.01
Standard
y= 0.01 Slandard
10-
0.001
Standard 2000spoch
75-
0.001 Standard 2000epoch
y 0.001 10 Repcots
y- 0.001 10 Rapeats
0
50
100
150
200
50
160
150
200
(Normalized) Epach
(Normalized) Epoch
Figure 11: Comparsion between performance of SGD with different learning rates on CIFAR100. Repeating batches is turned off epoch 200 and 10 additional epochs performed (green). For the experiment with 2000 epochs (orange), the plot normalized 200 epochs. For more explanations refer to Figure and Section 5.1.
M EXPERIMENTS ON SGD WITHOUT MOMENTUM
In Section 5.1, we designed an experiment to show the effect of large learning rate important and goes beyond controlling the effect of stochastic noise on the trajectory. Since our goal was to demonstrate the relevance and importance of analyzing these effects for the practical scenarios, we used the standard training settings including momentum and weight decay. For completeness, in this section we also include the results of applying SGD with repeats without momentum and without weight decay. We compare standard SGD with learning rate 0.05. standard SGD with learning rate 0.005, and SGD with k = 10 repeats and learning rate 0.005. Accuracy on test and train datasets throughout training is plotted in Figure 12. The figure also contains the accuracy during training with momentum to allow comparison. As expected, applying SGD without momentum performs worse than SGD with momentum. The gap between small and large learning rate can be observed in this case as well. However, we do not observe an improvement when applying repeats.
100
80
80
Test Accuracy
60-
80
40
Standard
0.05 Standard
y 0. 0.005- Standard - 2000epoch
20
y- 0.005 Standard 2000cpach
0.005
0.005 Repeats
100 (Normalized Epach
200
100 (Normalized) Epoch
150
Figure Comparsion between performance of SGD without momentum and weight decay and with different learning rates on CIFARIO. Repeating batches is turned off at epoch 200 and 10 additional epochs are per- formed (green). For the experiment with 2000 epochs (orange), the plot is normalized to 200 epochs. For more explanations refer to Figure 6 and Section 5.1.
N LOss ON THE LINE BETWEEN LARGE AND SMALL LEARNING RATE TRAJECTORIES
In Section 5.2, we observed that GD with a large learning rate shows behavior similar to escaping and follows different trajectory than GD with the small learning rate. In this section, we plot the loss along the line between the first point in the trajectory of GD with small learning rate (hereafter called the origin) and different points along the trajectory of GD with the large learning rate. Figure 13 shows the loss based on the norm of the distance to the origin. As expected the loss increases along the line between the origin and points at the beginning of the trajectory. This is when GD is showing
21

---

Under review as a conference paper at ICLR 2023
escaping behaviors. However, interestingly, the loss is decreasing along the line between the origin and points encountered later in the trajectory.
6
30
100
Lo55
1.0
1.2
Distance Norm
Figure 13: The value of loss along the line between the first point in the trajectory of GD with small learning rate and different points in the trajectory of GD with large learning rate. For more detailed explanation of the settings, refer Section 5.2. Each line corresponds to the value of loss measured 30 points along the line between initialization and parameters after an step. step number each line is written in box located on the top-right the plot.
ADDITIONAL REFERENCES
V.I. Bogachev. Measure Theory. Springer Berlin Heidelberg, 2006. ISBN 378-3-540--4513-8.
22


Reviews:
[{"review_id": "mKzmy5FEJoU", "reviewer": "Reviewer_hE2g", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This work considers the effect of large stepsize for GD in non-convex optimization. It shows theoretically that, under certain conditions, with a large stepsize GD can escape/avoid undesirable minimum, and in comparison, GD/SGD with small stepsize might converge into the undesirable minimum. \n\nThen the paper turns to present some empirical results. By re-using a mini-batch for multiple times, the work can, approximately, control the stepsize and the gradient noise in SGD in separate. By comparing this SGD variant with small/large stepsize SGD, some insights are drawn that the effect of large stepsize for SGD can go beyond simply a larger gradient noise. The second part of the experimental results are for verifying the provided theory. ", "summary_of_the_review": "Please see above. I will consider re-evaluate based on the authors reply but at this point I do not think this work qualifies being published. ", "strength_and_weaknesses": "# Strength \n1. The work considers a very important topic: understanding the effect of large stepsize in SGD. Despite the caveats in the theory (please see more in below), I (and I believe many others in the community) share somewhat similar understanding as the authors have proved in their theorems. \n2. I find most of the presentation is good. I especially like the cartoon figures, which speak for themself in a very nice way. \n3. The design in Section 5.1 is very interesting to me. I think this design could inspire more follow-up study on SGD (stepsize and noise).\n\n# Weakness\nMost of my criticism about this work will be about their theorems.\n\n1. Thm1 could have cited [Wu, et al, 2018]. Note that the \"linear stability\" in [Wu, et al, 2018] can exactly explain the results in Thm 1. Because for the choice of stepsize, $x\\_\\\\dagger$ is not linear stable but $x\\_\\*$ is linear stable. Granted, Thm1 discusses the behavior of the GD in an integrated manner, but the techniques are standard, using the assumptions on the one-point-convexity. I strongly suggest to add some discussion on [Wu, et al, 2018]. \n\n2.  Definition2 could be made more clear by specifying in the condition that $M$ is a fixed set (connected? compact? containing $x\\_\\*$? ...). \n\n3. Theorem 1, could define what is $\\\\mathcal{L}$. I assume it refers to some measure over the randomness of the initialization?\n\n4. Lemma 2 and Theorem 2. The failure probability has a crude, exponential dependence on dimension $d$ and number of iterates $T$. Such an exponential dependence makes the result rather weak and less interesting. I would like to see some discussion on how tight these are. That is, can we improve the dependence on $d$ and $T$ or not? Is the current exponential dependence purely artificial?\n\n5. Both Theorem 1 and 2 put strong assumptions on the landscape of the loss (e.g., exactly two minimum). Moreover, proposition 3 is dedicated for a special example. I am not against to look at special cases for drawing intuition, but the theorems in their current form fail to qualify this work as a solid theory work, in my humble opinion.  \n\n6. I feel the theory and the experiments have only tangential connections. Indeed, the theorems are all for optimization and have little to do with generalization/learning. But crucial in the experiments are the test accuracy for each algorithm. Is it possible to connect the specific loss landscape required for the theorem to some nature learning settings? If not I can hardly see why these losses are important examples for understanding the learning ability of SGD. \n\n# Missing Literature\nIn fact, multiple existing works have investigated the effect of large stepsize and discussed their importance for SGD (and are not from the perspective of enlarging the gradient noise). For an incomplete list, please see the following and the references therein:\n\n[1] Wu, Jingfeng, et al. \"Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate.\" ICLR 2021.\n\n[2] Beugnot, Gaspard, Julien Mairal, and Alessandro Rudi. \"On the Benefits of Large Learning Rates for Kernel Methods.\" COLT 2022.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RcbiWofr_w", "reviewer": "Reviewer_opfE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper tries to  explain why large learning rate is important in non-convex optimiztion.\nThis paper shows that  GD with large step size—on\ncertain non-convex function classes—follows a different trajectory than GD with\na small step size, which can lead to convergence to a global minimum instead of a\nlocal one.\nThe intuition behind this paper is direct and easy to follow.\nThe proofs in this paper are solid.", "summary_of_the_review": "This paper tries to  explain why large learning rate is important in non-convex optimiztion.\nThis paper shows that  GD with large step size—on\ncertain non-convex function classes—follows a different trajectory than GD with\na small step size, which can lead to convergence to a global minimum instead of a\nlocal one.\nThe intuition behind this paper is direct and easy to follow.\nThe proofs in this paper are solid.", "strength_and_weaknesses": "Pros: The inituition of this paper is easy to follow and it can explain why a large learning rate is preferred in a class of non-convex functions. The proofs in this paper are solid and easy to understand.\n\nCons: The writing seems a little messy. Lemma 1 is not easy to read. I also doubt  whether the claim in this paper holds for training neural networks. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1azDmOliBq", "reviewer": "Reviewer_juk2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper shows that a large learning rate can provably escape local minima and reach global minima for smooth and one-point-strongly-convex functions, while a small learning rate would not work. The paper further shows that a higher stochastic noise is not enough to close the gap with the model trained with a large learning rate.  Some experiments are conducted to disentangle the effects of stochastic noise and learning rate, to compare small and learning rates when training neural networks.", "summary_of_the_review": "The paper considered the effects of a large learning rate and showed that under smooth and one-point-strong-convex assumptions large learning rate is better than a small learning rate. However, it is unclear that how relevant these results are because the authors did not analyze the trajectory of a certain neural network but some contrived functions (e.g., Proposition 3). The experimental design has some issues. Overall the insight is not significant compared with previous work, such as [Li et al. NeurIPS 2019], which formally analyzed the effect of the learning rate in a certain neural network.", "strength_and_weaknesses": "Strength:\n\n1. The paper is clearly-written and the main message is clear.\n2. The literature review is sufficient.\n\nWeaknesses:\n1. The large learning rate is indeed important in neural network training, but the authors did not analyze the neural network training trajectory of gradient descent theoretically: instead, the authors simply assumed the function is smooth and one-point-strongly-convex, and there are exactly two minima. I am not sure the insight obtained in this paper can be generalized in neural networks since some arguments are made over some contrived functions (e.g., the function plotted in Figure 5).\n\n2. I am wondering what is the real technical contribution of this paper. It seems to be that the proof technique is standard: it uses standard proof roadmaps for smooth functions and combines with the one-point-strong-convexity to obtain the relationship between two consecutive iterates. \n\n3. The experiments are not well-designed. In Section 5.1, to disentangle the effects of learning rate and the stochastic noise, the authors should consider noiseless case instead of noisy case with different scale: the reason is that the noise does not only affect the current solution but also affects the whole trajectory of gradient descent. Why the authors turns off batch normalization? \n\n4. The insight of Section 5.2 is very similar to Figure 1 in [Li et al. NeurIPS 2019]. Although [Li et al. NeurIPS 19] did not plot the principal component but it is clear that small and large learning rate gradient descent have different trajectories (Please refer to Section 4 in [Li et al. NeurIPS 2019]).\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject