SGD Can Converge to Local Maxima
Authors: Liu Ziyin
Botao Li
James B Simon
Masahito Ueda
Venue: ICLR 2022 Spotlight (2022)
Keywords: stochastic gradient descent
saddle points
convergence
amsgrad
deep learning

Abstract: Previous works on stochastic gradient descent (SGD) often focus on its success. In this work, we construct worst-case optimization problems illustrating that, when not in the regimes that the previous works often assume, SGD can exhibit many strange and potentially undesirable behaviors. Specifically, we construct landscapes and data distributions such that (1) SGD converges to local maxima, (2) SGD escapes saddle points arbitrarily slowly, (3) SGD prefers sharp minima over flat ones, and (4) AMSGrad converges to local maxima. We also realize results in a minimal neural network-like example. Our results highlight the importance of simultaneously analyzing the minibatch sampling, discrete-time updates rules, and realistic landscapes to understand the role of SGD in deep learning.

Published as a conference paper at ICLR 2022
SGD WITH A CONSTANT LARGE LEARNING RATE CAN CONVERGE TO LOCAL MAXIMA
Liu Ziyin', Botao James Simon , & Masahito Ueda'
l 'Te University of Tokyo ENS,, Université PSL, CNRS, Sorbonne Université, Université de Paris á University of California, Berkeley
ABSTRACT
Previous works stochastic gradient descent (SGD) often focus its success. In this work, we construct worst-case optimization problems illustrating that, when not in the regimes that the previous works often assume, SGD can exhibit many strange and potentially undesirable behaviors. Specifically, we construct landscapes and data distributions such that (1) SGD converges local maxima, (2) SGD escapes saddle points arbitrarily slowly, (3) SGD prefers sharp minima over flat ones, and (4) AMSGrad converges to local maxima. We also realize results a minimal neural network-like example. Our results highlight the importance of simultaneously analyzing the minibatch sampling, discrete-time updates rules, and realistic landscapes to understand the role of SGD in deep learning.
INTRODUCTION
SGD is the main optimization algorithm for training deep neural networks, and understanding SGD is widely regarded as key step the path to understanding deep learning (Bottou, 2012; Zhang et al., 2018; Xing et al., 2018; Mori et al., 2021; Du et al., 2018; Allen-Zhe et al., 2018; Wojtowytsch, 2021a;b; Gower al., 2021; Ziyin et al., 2022b; Gurbuzbalaban al., 2021; Zou et al., 2021; Li et al., 2021; Feng and Tu, 2021). Despite its algorithmic simplicity (could be described by only two lines of equations), SGD hard to understand. The difficulty is threefold: (1) SGD discrete-tima in nature, and discrete-tima dynamics are typically much more complicated to solve than their continuous- time counterparts (May, 1976); (2) SGD noise state-dependent (Ziyin et al., 2022b; Hodgkinson and Mahoney, 2020); and (3) the loss landscape can be nonlinear and non-convex, involving many local minima, saddle points, and degeneracies (the Hessian not full-rank) in the landscape (Xing et al., 2018; Wu et al., 2017). Each of these difficulties is so challenging that very few works attempt to deal with all of them simultaneously. Most previous works on SGD are limited to the cases when the loss landscape is strongly convex (Ziyin et al., 2022b; Liu et al., 2021; Hoffer et al., 2017; Mandt et al., 2017), or when the noise is assumed to be Gaussian and time- memeindependent (Zhu et al., 2019; Jastrzebski et al., 2017; Xie et al., 2021);; for the works that tackle SGD in non-convex setting, often strong conditions are assumed. The reliance on strong assumptions regarding each of the challenges means that our present understanding of SGD for deep learning could be speculative. This work aims to examine some commonly held presuppositions about SGD and show that when all the three challenging factors are taken together, many counter-intuitive phenomena may arise. Since most of these phenomena are potentially undesired, this work can also be seen as a worst-case analysis of SGD.
In this work, we study the behavior of SGD in toy landscapes with non-convex loss and multi-minima. We approach the problem of SGD convergence from a different angle from many of the related works: instead of studying when SGD will converge, our result helps answer the question of when SGD might fail. In particular, the problem setting considers discrete-time SGD close to saddle points, where the noise is due to minibatch sampling, and the learning rate is held constant throughout training. In the next section, we define the SGD algorithm and the necessary notations. In Sec. 3, we discuss the related works. A warmup example is provided in Sec. 4. Sec. 5 introduces the main results. Sec. 6 presents the numerical simulations, including a minimal example involving a neural network. We also encourage the readers examine the appendix. Sec. A presents additional experiments. Sec. B

---

Published as a conference paper at ICLR 2022
10
15-
8-
1.5
0.8
landscape
Loss landscape
Initial distr isstrbbttion
5
Initial distribution
10
10 Finall distribttion
distribution
0.4
2
0.5
-1.0
0.55
0.0
0.5
1.0
0
-2
0.0
-1.0
00.5
0.0
0.5
1.0
0.0
Figure I: SGD converges to local maximum for the example studied in Sec. 5.1. Left: Distribution w on the quadratic potential, L zw² /2: the histograms different colors show the distribution of model parameters different time steps. Middle: Distribution the fourth-order potential, L = zw² /2 w Right: Escape probability function of a and X. The parameters space is divided into absorbing phase where
attracted to local maximum (in dark blue) and an active phase where ur successfully escapes the two central hins (in white).
presents a continuous-ting analysis of the problems in the main text and is relevant for discussing the unique discrete-time features of SGD, Sec. presents all the proofs.
BACKGROUND
Notation and Terminology. We use Ả to denote the learning rate. is the model parameter. L(w;,) x)), with the caret symbol denotes the sampled loss function, which a function of the data point, and L := E, [] is the loss landscape averaged over the data distribution; for notational conciseness, we often hide the dependence of L on æ when the context is clear. The lowercase denotes the time step of optimization. The phrases loss, objective, and potential are also used interchangeably.
Now, we introduce the minibatch SGD algorithm. The objective of SGD can be defined as pair (L, p(x)) such that L is differentiable function and p(x) is a probability density, We aim at finding the minimizer of the following differentiable objective:
L(w) = E,--(r) [ [ww;))),
(1)
where x is a data point drawn from distribution p(x) and w R is the model parameter, The gradient descent (GD) algorithm for I. is defined the update rule w/ 16:1 Tw for some randomly initialized wo, where X is the learning rate. The following definition defines SGD.
Definition The minibatch SGD algorithm computes the update to the parameter w with the following equation: w., W Art, where 9. V V.,. (wx=-1;ze). and Ta is drawn from p(x) such that x; is independent of I, for i
3 RELATED WORKS
Escaping Saddle Points. Because neural networks are highly nonlinear, the landscape of neural networks is believed to have many local minima and saddle points (Du al., 2017; Kleinberg et al., 2018; Reddi et al., 11).. is thus crucial for the optimization algorithm to be able to overcome saddle points efficiently and escape suboptimal minimum. However, the majority of works on escaping saddle points assume no stochasticity or only artificially injected noise (Li et al., 2017; Du al., 2017: Jin al., 2017; Ge et al., 2015; Reddi al., 2018b; Lee et al., 2016; Pemantle, 1990). Some physics-inspired approaches take the stochasticity into account but often rely on continuous-tim approximation and nontrivial assumptions regarding the stationary distribution of the parameter (Mori et al., 2021; Xie et al., 2021; Liu et al., 2021). In the context of stochastic non-convex optimization, one setting that SGD is known to escape saddles and converge well is when the learning rate decreases zero in the training (Pemantle, 1990; Vlaski and Sayed, 2019; Mertikopoulos et al., 2020). In contrast, we only consider the case when the learning rate is held fixed. We stress that result does not contradict these previous results. On the opposite, result reinforces the idea that the learning rate needs to be carefully chosen and scheduled when convergence is an essential concern.
Role of Minibatch Noise. One indispensable aspect of SGD is its stochasticity originated from minibatch sampling (Wu al., 2020; Ziyin et al., 2022b; Zhu et al., 2019; Hodgkinson and Mahoney,
2

---

Published as a conference paper at ICLR 2022
2020), whose strength and structure are determined by the model architecture and the data distribution. Moreover, it has been observed that the models trained with SGD significantly outperform the models directly trained with GD (Hoffer et al., 2017). Therefore, understanding the role of minibatch noise is of both fundamental and practical value. However, in the previous works, the focus is on analyzing the behavior of SGD the landscape specified by I,; the unique structures due the noise in SGI) are often treated in an oversimplified manner without referring to the actual models in deep learning or the actual data distributions. For example, Daneshmand et al. (2018) assumes that the noisy gradient is negatively correlated with the least-eigenvalue direction of the Hessian, an assumption that its validity unclear when the Hessian is not full rank. Kleinberg et al. (2018) assumes that the noise in SGD makes the landscape one-point strongly convex, which implies that the loss landscape before the convolution is already close to a strongly convex landscape. Another commonly assumed condition is that the loss-landscape satisfies the Lojasiewicz condition, which is non-convex but implies the unrealistic condition that there is no local minimum except the global minimum (Karimi et al., 2020; Wojtowytsch, 202Ia; Vaswani et al., 2019), which is not sufficient to understand the complicated dynamics that often happen in a setting with many minima (for example, a deep linear net (Ziyin et al., 2022a)). In Sec. 6.3, we show that these assumptions are violated for minimal nonlinear neural network with two layers and one hidden neuron. While our example may or may not be directly relevant for realistic settings in the deep learning practice, our work highlights the importance of analyzing the actual noise structure imposed by a deep neural network in future works.
Large Learning Rate Regime. Recently, it has been realized that networks trained at a large learning rate have a better performance than networks trained with a vanishing learning rate (lazy training) (Chizat and Bach, 2018). Lewkowycz et al. (2020) shows that there a qualitative difference between the lazy training regime and the large learning rate regime; the performance features two plateaus in testing accuracy in the two regimes, with the large learning rate regime performing much better. However, almost no previous theory exists for understanding SGD at a large learning rate. Our work also relevant for understanding what happens at a large learning rate.
A WARM-UP EXAMPLE
This section studies special example of the main results of our work. While the setting of this example is restricted, it captures the essential features and mechanisms of SGD that we will utilize to prove the main results. Consider the following loss function:
i(w)= x
2 w²
(2)
where x, w é R and x is drawn from an underlying distribution p(z) at every time-step. We let
E[x] = a/2 and assume that Var[x] o² is finite. This gives rise to a true, sample-averaged loss of T(w)= "w2. The stationary point of this loss function is w = 0. When a > 0, the underlying (deterministic) landscape is a minimum; the a > 0 case is now well understood in the discrete-time limit and when the underlying noise is state-dependent (Liu et al., 2021). When a O, the point 0 is a local maximum; one hopes that the underlying dynamics escape to infinity, and our goal is to understand the behavior of SGD in this case.
The following proposition and proof show that for the zero zero-mean and bounded distribution p(z), SGD cannot escape from the local maximum when the learning rate is set to be 1.
Proposition Lei x = 1 and < 0 and p(x) be the distribution such that x = and x = - + a with equal probubility. Then, w converges to w 0 with probability 1 with the SGD algorithm, independent of the initialization.
Proof. By the definition of the SGD algorithm, we have
with probability 0.5;
W (2 a) a)w: otherwise.
(3)
Therefore, after t time steps, we has most 2 probability of being non-zero. For infinite t, w, = with probability 1.
This simple toy example illustrates a few important points. First of all, it suggests that one cannot use the expected value of w to study the escape problem of SGD. The expectation value of w, is
Fy [_[[w] (1 a/2) = (1 a/2)'uo wwo woe woe In(1-//2)
(4)
3

---

Published as a conference paper at ICLR 2022
which is an exponentially fast escape from any initialization wo for 0. In fact, In(1 - a) is exactly the escape time scale of the GD algorithm. This is counter-intuitive SGD will converge to the local maximum with probability 1, even if its expected value escapes the local maximum exponentially fast.
Alternatively, one might also hope to use the expected loss the norm En,, [[(ww) ||w=12 as the metric of escape, but is not hard to see that they suffer the same problem. At time f, because w/ = 0 with probability 1-21 2-2" and W; (2 a)wo ww with probability 2-*, we have [[L(w:) oc w 32 which also predicts an exponentially fast escape. Again, this fails to reflect the fact that SGD has only a vanishingly small probability of escaping the constructed local maximum. Statistically speaking, the norms of we fail to be good metrics to measure the escape rate because these metrics are not robust against outliers. In our example, there is only 2- probability for SGD to escape the local minimum, yet the speed at which this outlier escapes the maximum outweighs the decay in its probability through time, thus contributing more to the expected norm than any other events. This example also shows the difficulty and subtlety of dealing with the escape problem. This example (together with Sec. 5.1) )) also emphasizes the importance of showing convergence in probability for future works in non-convex optimization because convergence in expectation is not sufficient to guarantee good empirical performance. The results in the rest of this work can be seen as extensions of this special case to less restrictive settings.
MAIN RESULTS
In this section, we present our four main theoretical results: (1) SGD may converge to a local maximum; (2) SGD may escape a saddle point arbitrarily slowly; (3) SGD may prefer sharp minima over flat ones; and (4) AMSGrad may converge to a local maximum.
5.1 SGD MAY CONVERGE TO A LOCAL MAXIMUM
We show that there are cases where SGD may fail to escape saddle points, while GD can successfully escape; this contradicts the suggestions in Kleinberg et al. (2018) that SGD always escapes local minimum faster than GD. It is appropriate to begin with the definition a saddle point.
Definition 2. w is said to stationary point of L(w) if V ((w)= w is minimum of for all w/ in sufficiently small neighborhood of w. L(w') 2 [w). ). is said to be saddle point if w is a stationary point but not a local minimum.
This definition of saddle points, which includes local maxima, agrees with the common definition in the literature (Daneshmand et al., 2018). The following proposition generalizes our warmup example to family of ID problems in which SGD converges to a local maximum.
Proposition 2. Let Eq. 2 be the loss function. Let X > O, and p(1) be such that μ E[[n Axr] and 8² == Var[In]] [1= >xl]; then SGD converges to the local maximum in probability if p < O.
Proof Sketch. We first show that 1 In /w//wol obeys normal distribution as t + co. This allows us J
to deduce the cumulative distribution function (c.d.f.) of w as t The c.d.f. has an bifurcative dependence on the sign of μ == [[[n|] 1 Ar|]. When < O, the distribution of we converges to 0 in probability. See Sec. C.2 for the detailed proof. O
Corollary 1. Let Eq. 2 be the loss function and p(x) f 1)(x=1)++ (000-1+)=0000++ ((x+1=a):: then SGD converges to the local maximum in probability if
02 8a 8
a-1 <><
(5)
2(a
One special feature of this example is that the state-dependent noise vanishes at the saddle point. In this particular example, this is achieved by having an SGD noise proportional to the gradient thus vanishing at the saddle point. This type of structure may be relevant for deep learning because vanishing noise at a stationary point and state-dependent noise can appear at the origin of a deep net, where weights of all layers zero. Note that the convergence is independent of the actual shape of the distribution p(x), and so may apply to many kinds of distributions besides the Bermoulli distribution considered. There three different regimes/phases for this simple escaping problem
4

---

Published as a conference paper at ICLR 2022
(also see Fig. 1-iight). The escape regime À 9-Va2-8o+8 is also present when > O; it means that 2(a-1)
in this regime, SGD will also escape wp even if it is local minimum. This regime is not present if we perform continuous-ting time analysis (Sec. B), showing that this region is due to the instability of the discrete-time SGD algorithm. This kind of escaping is undesirable because, in this regime. the local
gradient cannot provide any guidance for minimizing the loss. The region - X a-Va2-8a=5 is
2(a-1)
the trapped regime. This is due to the special structure of the minibatch noise- - a comparison with the continuous-ting analysis suggests that SGD will not be trapped if the noise is not position dependent (Sec. B. The small learning rate regime À < T-T is the successful escape regime because the SGD noise is of order X² and becomes negligible at a small À (Liu et al., 2021). This regime corresponds to the lazy learning regime of training: with negligible noise and vanishing gradient, SGD is known to optimize neural networks well (Du et al., 2018). This discussion also justifies our later choice for placing an upper bound to X and focusing only on the second and third regime in Sec. 5.3 and 5.4.
It is important to understand why the previous works that show that the previous guarantees of convergence do not apply to this particular example, for example, Ge et al. (2015). comparison, the SGD algorithm is not guaranteed to escape the saddle point in this example because two crucial assumptions of Ge et al. (2015) is violated: (1) the gradient does not have a bounded fluctuation around its mean (and so even parameters very far away from the saddle can be brought back close to the saddle point due to the noise), and (2) we do not inject additive noise to the gradient and the actual noise decreases as we approach the saddle point (and the closer we to the saddle point, the less likely one can escape). The standard theoretical guarantee of convergence in Ge et al. (2015) thus does not apply to this example. This example shows that the minibatch noise of SGD is very special and can strongly influence convergence. A continuous-timy analysis in Section B of this example shows that the convergence local maxima occurs when the minibatch noise dominates the gradient, namely, when the signal to noise ratio becomes smaller than 1. This suggests the importance of minibatch noise in influencing the dynamics of SGD. This suggests that the signal-to-noke ratio can be an important parameter in SGD dynamics and may deserve more future research.
5.2 SGD MAY ESCAPE SADDLE POINTS ARBITRARILY SLOWLY
In the previous section, we have shown that one can adversarially construct a loss function for a fixed learning rate such that the SGD algorithm converges to local maximum. This section shows that, even if one can tune the learning rate at will, there is a loss landscape where SGD can take an arbitrarily long time to escape, no matter how one chooses the learning rate. We begin by defining the escape rate.
Definition 3. The asymptotic average escape rate of w at learning rate X, (A), is defined as y:= lim 1
i |E,, [In [w:]]. The optimal escape rate is defined as 7 := (A)
Remark. This definition can be seen as a generalization of the Lyapunov exponent to a probabilistic setting. We note that this definition of escape rate differentiates this work from the standard literature on escaping saddles, where the focus on the time scale for reaching a local minimum when saddle points exist (Ge et al., 2015; Daneshmand et al., 2018; Jin et al., 2017), 7,, while our definition ferettionoocusee on the time scale of escaping a specified saddle point. These two time seales can be vastly different.
As discussed in the previous section, the undesired escape can be achieved by setting the learning rate to be arbitrarily large; however, this is not possible in practice because the learning rate of SGD is inherently associated with the stability of learning, and À usually has to be much smaller than 1.
50(z= a 1), where 8 is the Dirac delta function, and X S 1. Then, for any E > 0, there exists such that supx 7(A) < e.
Proposition 3. Let the loss function be Eq. (2), 0 and p(z) ~ ]0xx= - 1)
Specifically, 7 In 2-o and, for any > 0, 7 < if [a] s 2 Ve2e 1- 26 +
2/1-0'
Namely, the SGD algorithm can escape the saddle point of Eq. (2) arbitrarily slowly. Intuitively, one expects escaping to be easier as we increase the learning rate (Kleinberg et al., 2018), and that the escape rate should monotonically increase as we increase the learning rate. This example conveys a novel message that the escaping efficiency is not monotonically increasing as the learning rate increases. For this example, the escape rate first decreases and starts to increase only when À is quite large. This example also shows the subtlety in the escaping problem. On the one hand, one needs to avoid a too large learning rate to avoid training instability. On the other hand, one cannot use too
5

---

Published as a conference paper at ICLR 2022
small learning rate because small learning rate also makes optimization slow. Thus, there should be a tradeoff between learning speed and learning stability, and we may construct a general theory for finding the best learning rate that achieves the best tradeoff; however, this tradcoff problem is sufficiently complex problem on its own and is beyond the scope of the present work.
5.3 SGD MAY PREFER SHARPER MINIMA
Modern deep neural networks are often overparametrized and can easily memorize all the training data points. This means that the traditional metrics such Rademacher complexity cannot be used to guarantee the generalization capability of SGD (Zhang et al., 2017). Nevertheless, neural networks are found to generalize very well. This inspired the hypothesis that SGD, the main training algorithm of neural networks, contains some implicit regularization effect such that it biases the neural network towards simpler solutions (Neyshabur et al., 2017: Soudry et al., 2018). One hypothesized mechanism of this regularization is that SGD selects flat minima over the sharp ones (Hochreiter and Schmidhuber, 1997; Meng et al., 2020; Xie al., 2021: Liu al., 2021; Mori al., 2021; Smith and Le, 2018; Wojtowytsch, 2021b) In this work, we show that this may not be the case because the dynamics and convergence of SGD crucially depend on the underlying mini-batch noise, while the sharpness of the landscape is independent of the noise. Before introducing the results, let us first define the sharpness
local minimum.
Definition 4. Let w" be a local minimum of the loss function L(w): the sharpness s(w") of local minimum w is defined as sww")= == Tr(v [ww)]. We say that a minimum wi is sharper than w if and only if s(w") > swa)).
In this definition, the sharpness is the trace of the Hessian of the quadratic approximation the local minimum. Other existing definitions, such as the determinant of the Hessian, are essentially similar this definition (Dinh et al., 2017).
For an explicit construction, consider the following objective on a 2-dimensional landscape:
(wi + w2)² 2 1 [[[(w] 2022² [(w1, w2) _
(wi - w2)* (wi + w2)* 2aw2 xbws]
(6)
for a, b> 0 and p(x)= _ō(x0 1) f0(xx+ 11. The diagonal terms of the Hessian of the loss function given by
8² o
[w,, w2) = 2 12w + 12w6;
8
i (wi, w2) - 2a + 12w 12wg.
There are four local minima in total for this loss function. These minima and their sharpnesses are
(W1, w2) = (+1z2.
with =
(8)
(w = ( with s 4 4a.
Ita
We see that for positive a, the minima at (0, + show that SGD will converge to these sharper minima. For this example, assume that wi and wa are bounded because, if initialized sufficiently far from the origin, the fourth-orde term will cause divergence.
1+0 are sharper than the other two minima. We
Proposition 4. Let the loss function be Eq. (6), |wil and |uz) 1. For any X e f.ror some constant c= c= 0(1), there exists some b such that if SGD converges in probability, it will converge to the sharper minimum at (wi,w>) (0, V 1tt).
Remark. In this example, the noise is not not full-rank, which is often the case deep learning setting for overparametrized networks ( (Wojtowytsch, 202 For example, when weight decay is used, the Hessian of the loss function should be full rank, while the rank of the noise covariance should be proportional to the inherent dimension of the data points, which is in general much smaller than the dimension of the Hessian in deep learning (Ansuini al., 2019).
The proof is technical and given in the appendix Sec. C.5. In fact, it has been controversial whether finding a flat minimum can help generalization. For example. Dinh et al. (2017) shows that, for every flat minimum of ReI. U-based net, there exists minimum that is arbitrarily sharper and generalizes

---

Published as a conference paper at ICLR 2022
well. However, this work does not rule out the possibility that conditioning by using gradient- based optimization, the performance of the sharper minima that gradient descent finds is worse than the performance of the flatter minima. If this assumption is valid, then biasing gradient descent towards flatter minima can indeed help. and the stochasticity of SGDD has been hypothesized to help this regard. However, our construction shows that SGD, its own, may be incapable of helping SGD converge to a flatter minimum. At least some other assumptions need to be invoked to show that SGD may help. For example, the definition of the neural networks may endow these models with special kind of Hessian and noise structure that, when combined with SGD, results in miraculous generalization behavior. However, no previous work has pursued this direction in sufficient depth to our knowledge, and future studies in this direction may be fruitful.
5.4 NON-CONVERGENCE OF ADAPTIVE GRADIENTS
m4 = 31 (1- B1)
(9)
Adam (Kingma and Ba, 2014) and its closely related variants such as RMSProp (Tieleman and Hinton, 2012) have been shown to converge to a local maximum even for some simple convex loss landscapes (Reddi al., 201 8a). The proposed fix, named AMSGrad. takes the maximum of all the previous preconditioners in Adam. This section shows that AMSGrad may also converge to local maximum even in simple non-
U, = 820 + (1 3g )
(10)
6 max (t)
(11)
A
w, W--1
Vor my.
(12)
convex settings. Let p(r) and Dr- vi(I,, Wr-1), the Adam algorithm is given by Eq. (9)-(1),, where vp = mig = O. We have removed the numerical smoothing constant e from the denominator, which causes
problem if wo is initialized away from 0. Here, 81 is the momentum hyperparameter. it is called the preconditioner, and 33 is the associated hyperparameter. The standard value for 31 is 0.9 and Bg is 0.999. In our theory, shows that a similar problem exists when 31 > 0 (with additional interesting findings). Intuitively, this is easy understand because AMSGrad behaves like SGD asymptotically, to wait for long enough, and the results in previous sections would apply. The construction below follows this intuition.
only consider the case when 8₁ O. The experiment section
only have
Let we E [-,,1], and wo O. For fixed X < 1 and the loss function in Eq. (2) there exists a < O such that the AMSGrad algorithm converges in probability to a local maximum.
Proposition 5.
Remark. The proof is given in Sec. C.6. Note that the example we construct is similar to the original construction in Reddi et al. (2018a) that shows that Adam converges to a maximum while AMSGrad succeeds in reaching the global minimum. In their example (with some rescaling). the gradient is a random variable
with probubility a 1; Cu <0 with probability 1- << 1;
9:
(13)
such that the expected gradient is negative, and Adam is shown to converge to the direction opposite the gradient descent (therefore a maximum). our example, the gradient is (roughly)
Wt-1 G = -(1 + +a)w--1
with probability 1/2:
(14)
with probability 1/2.
Therefore, our example can be seen as a minimal generalization of the Reddi et al. (2018a) example to non-convex setting.
EXPERIMENTAL DEMONSTRATIONS
We perform experiments to illustrate the examples studied this work. Due to space limitations, we illustrate the escape rate and the convergence to sharper minima example in Appendix Sec. A.
6.1 SGD CONVERGES TO LOCAL MAXIMUM
Numerical results are obtained for the setting described in section 5.1. See Fig. 1-Left. The loss landscape is defined by L(w)= tow?. In this numerical example, set À = 0.8 and a -1, and the histogram is plotted with 2000 independent runs. We see that the distribution converges to the local maximum at 0 as the theory predicts. For better qualitative understanding. also plot
7

---

Published as a conference paper at ICLR 2022
0.20
2.00
AMSSGrd
Alam
satnng 0222
treining loss
0.04
AMS5ired
-0.04
Acam
-0.06
CD
-0.08
-0.08
-0.08
-0.00
-0.10
10
1.0
102
training dtops
trining stoce
AMSGrad diverges the local maximum with or without momentum in the example studied in See 5.4, Our result shows that AMSGrad always attracted to the local maximum, while Adam has the potential of escaping the local maximum with momentum. Left: without momentum. Right: with momentum.
Figure 2:
the empirical phase diagram of this setting in Fig. 1-Right. We perform numerical evaluations for different combinations of a and À on a a À plane, and for each combination, we plot the percentage of w that escapes the central bin (white is 100% and dark blue is 0%). For completeness, plot the case when a > 0, i.e., when the critical point at w O is a local minimum. The orange line shows where the phase transition is expected to happen according Eq. (5). The fact that the orange line agrees exactly with the empirical phase transition line confirms our theory.
also
We also numerically study a closely related fourth-order loss landscape, defined as L(w)= ((w)= + 7 1w², where the distribution p(x) is the same before. The expected loss L(w) has two local minima located as w = -2a We are interested in whether SGD can converge to these two points successfully; note that, without the fourth-order term, this loss is the same as the quadratic loss we studied. See Fig. I-Middle. As before, a = -1 and À = O.S. We see that the distribution of w also concentrates towards the local maximum after training. and local minimum even if a significant proportion of w is initialized close to these two minima. A phase diagram analysis is given in the Sec. A.I.
is found to converge to the two
6.2 NON- VORGGENVE OF AMSGRAD
In this section, we illustrate the example of the convergence behavior of AMSGrad described in Sec. 5.4; for reference, we also plot the behavior of Adam and gradient descent for this example. See Fig. 2. The experiment is the average over 2000 runs, each with 5 10a steps. The uncertainty is reflected by the shaded region (almost invisibly small). The loss function is the same as discussed in Sec. 5.4 with a -0.1. For illustration purposes, we À 0.2 and 32 = 0.999 for both Adam and AMSGrad. When momentum is used, we set 31 = 0.9. GD is run with a learning rate of 0.01. Without momentum, both Adam and AMSGrad converge to the local maximum with almost the same speed. When momentum is added, AMSGGrd still converges to the local maximum. Curiously, Adam no longer attracted to the local maximum but also remains away from the local minimum. This suggests that Adam, with momentum, might have better capability of escaping saddle points than AMSGrad and might be preferable to AMSGrad in a non-convex setting.
6.3 A ToY NEURAL NETWORK EXAMPLE
We have now illustrated several SGD phenomena we studied in artificial settings, inspiring the natural question of whether they occur for an actual neural network. Here construct a neural- net-like optimization problem to show that the problems with convergence might indeed arise for a neural network. The toy neural network function is given by f(x) wzo (w)z), where w1, Wa IR. o is the nonlinearity, and we let (xx) = x² as a minimal example. This is the simplest kind of nonlinear feedforward network one can construct (2 layer with single hidden neuron). We also pick a minimal dataset with a single data point: x = 1 with probability 1 and E (-1,2) 2), each with probability 0.5, i.e., the label has degree of inherent uncertainty, which is often the case in real problems. We use mean squared eτror (MSE) as the loss function. Therefore, the expected loss is L(w1, w2) = (w2w, 1)2 + (w2wf 2)2. The global minimum L 2.25 is degenerate, and is achieved when W1 = 1/V22wz. There is also a manifold of saddle points given by {(w1, w2 [w1 = 0, wa 2 0}, all with L 2.5. Despite the simplicity of this example, it contains few realistic features in a realistic problem, including (1) inherent uncertainty in the data, (2) a nonlinear hidden layer, and (3) degenerate minimum with zero eigenvalues in the Hessian.
8

---

Published as a conference paper at ICLR 2022
13
2.50
2.45
6.3
38
Saddle
43
0.3
2.40
Diverge
-15
-65
2:35
-26
-14
2083
2.30
11.0
20
-35
36
2089
2.25
0.000 0.025 0.050 0.075 0.100 0.125 0.150
learning
Figure 3: Convergence of a two-layer one onc-neuron neural network to a saddle point. The blue region shows the empirical density of converged parameter distribution. Left: À = 0.001 at step 10000 converges to global minima. Mid: X 0.1 at step 10000 converges to saddle point. Right: Average loss in equilibrium as function of learning rate. The loss function diverges for learning rates larger than 0.108.
More importantly, most previous works on the convergence escaping behavior of SGD are inapplicable to this example. One dominant assumption is the p-Hessian Lipschitz property (Jin et al., 2017; Ge et al., 2015), which does not hold for this example in particular. Another common assumption the PI. condition (Karimi et al., 2020; Wojtowytsch, 2021a; Vaswani et al., 2019), which does not apply due to the existence of the saddle point. One recent assumption is that the loss function is 1-point convex for all points (Kleinberg et al., 2018), which is also ruled out because (0,0) 0) is not 1- 1-point strongly convex. Another relevant assumption is the correlated negative curvature assumption, which also does not hold for (0, 0). We explain in Sec. A.5 in detail why these conditions violated.
See Fig. 3 for the experimental results with this example. Here, wi is initialized uniformly in [-1, -1,1] 1]; w2 is initialized uniformly in [o. 1] be closer the global minimum and away from the saddle point (standard initialization such as initializing in [] does not change the conclusion). The left figure shows the stationary distribution of the model parameter a small learning rate (A 0.001). All the parameters are located in the global-minimum valley as expected. In contrast, when the learning rate large (A 0.1), the central figure shows that all models (1000 independent runs) converge to the saddle point at (0. 0). The right figure investigates this change more systematically and shows the change in the average stationary training loss of the models as we increase the learning rate from 0.001 to 0.15. We see that for small learning rate, the training loss is close to that of the global minima (L= 2.25), and for significant range of large learning rates, the model invariably converges to saddle point (L 2.5). One additional interesting observation is that the model diverges at x 0.11, and there is almost no sign of such divergence (such as increased fluctuation) when the learning rate is close the divergent threshold. This example shows the relevance of our results to the study of neural networks. In fact, it has often been noticed that at convergence, many large-scale neural networks in real tasks exhibit negative eigenvalues in the Hessian (Alain al., 2019; Granziol et al., 2019). The existence of negative eigenvalues at a late time suggests either the possibility that the algorithm has yet escape or that it has indeed been attracted to such saddle points; if the latter is true, then our work offers an explanation. The emergence of negative eigenvalues at the end of training serves as indirect evidence that our result may be relevant for larger neural networks. thus remains an important open question to prove (and identify the condition of) or disprove the convergence of larger and deeper neural networks to local maximum.
7 DISCUSSION
We have shown that when the learning rate is not carefully chosen or scheduled, SGD can exhibit many undesirable behaviors, such convergence to local maxima saddle points. The limitation of our work is clear. At best, all the constructions we made are minimal and simplistic toy examples that are far from practice, and investigating whether the discovered messages are relevant for deep learning or not is the one important immediate future step. Other relevant questions include: (1) Does convergence to saddle points help or hurt generalization? (2) If it hurts, how can we modify SGD to avoid saddle points better? We suspect changing learning rates, changing batch size, or injecting noise may help, but convincing theoretical guarantee in a realistic setting is yet lacking. (3) saddle points do not have worse generalization, our results motivate for understanding why. This is especially relevant because we showed that using a large learning rate is more likely to converge to saddle points, while previous works have shown that using large learning rate can improve generalization; combined, this may imply that certain saddle points may have intriguing but unknown regularization effects.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENT
We thank the anonymous reviewers for providing detailed and constructive feedback for our draft. Ziyin thanks Jie Zhang for the help during the writing of this manuscript. Ziyin is financially supported by the GSS Scholarship from the University of Tokyo. BL acknowledges CNRS for financial support and Werner Krauth for all kinds of help. JS gratefully acknowledges support from the National Science Foundation Graduate Fellow Research Program (NSF-GREP) under grant DGE 1752814. This work was supported by KAKENHI Grant Numbers JP EP18H011 145 and JP2 1H0515 from the Japan Society for the Promotion of Science.
REFERENCES
Alain, G., Roux, N. L.., and Manzagol, P.-. (2019). Negative eigenvalues of the hessian in deep neural networks. arXiv preprint arXiv:1902.02366.
Allen-Zhu, Z., Li, Y., and Song, Z. (2018). A convergence theory for deep learning via over- parameterization. arXiv preprint 1rXiv:1811.0330
Ansuini, A., Laio, A., Macke, J. H., and Zoccolan, D. (2019). Intrinsic dimension of data representa- tions in deep neural networks.
Bottou, L. (2012). Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pages 421-436. Springer.
Chizat, L. and Bach, F. (2018). A note on lazy training in supervised differentiable programming. arXiv preprini arXiv: 1812.07956, 8.
Daneshmand, H., Kohler, J., Lucchi, A., and Hofmann, T. (2018). Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pages 1155-1164. PMLR.
Dinh, L.,, Pascanu, R., Bengio, S., and Bengio, Y. (2017). Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR.
Du, S. S., Jin, C., Lee, J. D., Jordan, M. I., Poczos, B., and Singh, A. (2017). Gradient descent can take exponential time to escape saddle points. arXiv preprint arXiv: 104.10
Du, S. S., Zhai, X., Poczos, B., and Singh, A. (2018). Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint 181000044
Feng, Y. and Tu, Y. (2021). The inverse flattese-flatness relation in stochastic gradient descent is critical for finding flat minima. Proceedings of the National Academy of Sciences, 118(9).
Ge, R., Huang, F., Jin, C., and Yuan, Y. (2015). Escaping from saddle points coints-online gradient for tensor decomposition. In Conference on learning theory, pages 797-842, PMLR.
online stochastic
Gower, R., Sebbouh, O., and Loizou, N. (2021). Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference on Artificial Intelligence and Statistics, pages 1315-1325 1323. PMLR.
Granziol, D., Garipov, T., Zohren, S., Vetrov, D., Roberts, S., and Wilson, A. G. (2019). The deep learning limit: are negative neural network eigenvalues just noise? In ICML. 2019 Workshop on Theoretical Physics for Deep Learning.
Gurbuzbalaban, M., Simsekli, U., and Zhu, L. (2021). The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, pages 3964-3975. PMLR
Hochreiter, S. and Schmidhuber, J. (1997). Flat minima. Newral Computation, 9(1):1-42.
Hodgkinson, L. and Mahoncy, M. W. (2020). Multiplicative noise and heavy tails in stochastic optimization. arXiv preprint 2006.0660006
Hoffer, E.. Hubara, I., and Soudry, D. (2017). Train longer, generalize better: closing the general- ization gap in large batch training of neural networks. In Proceedings of the 31 International Conference Neural Information Processing Systems, pages 1729-1739
10

---

Published as a conference paper at ICLR 2022
Jastrzebski, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y., and Storkey, A. (2017). Three factors influencing minima sgd. arXiv preprint arXiv:1711.0462..
Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. (2017). How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR.
Karimi, H., Nutini, J., and Schmidt, M. (2020), Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewe condition.
Kingma, D. P. and Ba, J. (2014). Adam: A method for stochastic optimization. CoRR, abs/ hts//141..am 1412.9980
Kleinbeng, B., Li, Y., and Yuan, Y. (2018). An alternative view: When does sgd escape local minima? In International Conference on Machine Learning, pages 2698-2707. PMLR.
Lee, J. D., Simchowitz, M., Jordan, M. I., and Recht, B. (2016). Gradient descent only converges to minimizers. In Conference on learning theory, pages 1246-1257. PMLR.
Lewkowyez, A., Bahri, Y., Dyer, E., Sohl-Dickstein, J., and Gur-Ari, G. (2020). The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.022/8.
Li, H., Xu, Z., Taylor, G., Studer, C., and Goldstein, T. (2017). Visualizing the Loss Landscape of Neural Nets. ArXiv e-prints.
Li, Z., Malladi, S., and Arora, S. (2021). On the validity of modeling sgd with stochastic differential equations (sdes). arXiv preprint 1oXi::2002.124700
Liu, K., Ziyin, L., and Ueda, M. (2021). Noise and fluctuation of finite learning rate stochastic gradient descent.
Mandt, S., Hoffman, M. D., and Blei, D. M. (2017). Stochastic gradient descent approximate bayesian inference. Journal of Machine Learning Research, 18:1-35.
May, R. (1976). Simple mathematical models with very complicated dynamics. nature. vol. 251, june. 10.
Meng, Q., Gong, S., Chen, W., Ma, Z.-M., and Liu, T.-Y. (2020). Dynamic of stochastic gradient descent with state-dependent noise. arXiv preprint arXhv:2006.13719.
Mertikopoulos, P., Hallak, N., Kavis, A., and Cevher, V. (2020). On the almost sure convergence of stochastic gradient descent in non-convex problems. arXiv preprint arXiv:2006.1 1144.
Mori, T., Ziyin, L., Liu, K., and Ueda, M. (2021). Logarithmic landscape and power-law escape rate of sgd. arXiv preprint arXiv:2105.0955:
Neyshabur, B., Tomioka, R., Salakhutdinov, R., and Srebro, N. (2017). Geometry of optimization and implicit regularization in deep learning. arXiv preprint arXiv:1705.033:
Pemantle, R. (1990). Nonconvergence to unstable points in urn models and stochastic approximations. The Annals of Probability, 18(2):698-712.
Reddi, S., Kale, S., and Kumar, S. (2018a). On the convergence adam and beyond. International Conference Learning Representations.
Reddi, S., Zaheer, M., Sra, S., Poczos, B., Bach, F., Salakhutdinov, R., and Smola, A. (2018b). A generic approach for escaping saddle points. In International conference on artificial intelligence and statistics, pages 1233-1242. PMLR.
Smith, S. and Le, Q. (2018). bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S.. and Srebro, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1)22222-2878.
Tieleman, T. and Hinton, G. (2012). Lecture 35-sRmop Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning.

---

Published as a conference paper at ICLR 2022
Vaswani, S., Bach, F., and Schmidt, M. (2019). Fast and faster convergence of sgd for parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1195-1204. PMLR.
Vlaski, S. and Sayed, A. H. (2019). Second-order guarantees of stochastic gradient descent in non-convex optimization.
Welling, M. and Teh, Y. W. (2011). Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-II), pages 681-688. Citeseer.
Wojtowytsch, S. (2021a). Stochastic gradient descent with noise of machine learning type. part i: Discrete time analysis. arXiv preprint arXiv:2105.01650
Wojtowytsch, S. (2021b). Stochastic gradient descent with noise of machine learning type. part ii: Continuous time analysis. arXiv preprint S.Xix:2006002588
Wu, J., Hu, W., Xiong, H., Huan, J., Braverman, V., and Zhu, Z. (2020). On the noisy gradient descent that generalizes as sgd. In International Conference on Machine Learning, pages 10367-10376. PMLR.
Wu, L., Zhu, Z., and E. W. (2017). Towards Understanding Generalization Deep Learning: Perspective of Loss Landscapes. ArXiv e-prints.
Xie, Z., Sato, I., and Sugiyama, M. (2021). diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference on Learning Representations.
Xing. C., Arpit, D., Tsirigotis, C., and Bengio, Y. (2018). A walk with sgd. cite arxiv11802.08777Commeee First two authors contributed equally.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2017). Understanding deep learning requires rethinking generalization.
Zhang, C., Liao, Q. Rakhlin, A., Miranda, B., Golowich, N., and Poggio. T. (2018). Theory of deep learning iib: Optimization properties of sgd. arXiv preprint arXiv:1801.02255
Zhu, Z., Wu, J., Yu, B., Wu, L., and Ma, J. (2019). The anisotropic noise stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In International Conference on Machine Learning, pages 7654-7663. PMLR.
Ziyin, L., Li, B., and Meng, X. (2022a). Exact solutions of a deep linear network. arXiv preprint 2202.0477..
Ziyin, L., Liu, K., Mori, T. and Ueda, M. (2022b). Strength of minibatch noise in SGD. In International Conference Learning Representations.
Zou, D., Wu, J., Braverman, V., Gu, Q., and Kakade, S. M. (2021). Benign overfitting of constant- stepsize sgd for linear regression. arXiv preprint arXiv:2103.1266
12

---

Published as a conference paper at ICLR 2022
A ADDITIONAL EXPERIMENTS
A. PHASE DIAGRAM OF THE FOURTH-ORDER LOsS FUNCTION
With two proper local minima, the fourth-order loss function is more realistic loss function than the one we considered in Sec. 5.1. We also performed one experiment in the main text (See Fig. 1). Here, we plot its empirical phase diagram in Figure We see that for this loss landscape also, there is some region such that for all X, SGD converges to the local maximum. This loss landscape is very difficult to study in discrete time as is known lead to chaotic behavior at large learning rate (May, 1976). Therefore, we alternatively try to understand this landscape using continuous approximation. See Sec. B.
2.0
1.0
1.5
0.8
0.4
0.5
-0.5 0.0
1.0
0.0
Figure 4: Escape probability from the local maximum function of and À with fourth-order loss landscape. The parameters space is divided into an absorbing phase where w is attracted to the local maximum and an active phase where w escapes to infinity successfully. The orange line the theoretical phase transition line for the quadratic loss function. We see that when À is small, the line based on quadratic loss also gives good agreement with the fourth-order loss. This suggests that part of this result is universal and independent of the details of the loss function.
A.2 ESTIMATING THE ESCAPE RATE
In the escape rate experiments, the empirical results are obtained from the proposed approximation. Here, we show that it is valid. See Fig. 5, where we plot the estimated function of the training step. We see that the estimated value converges within about steps. We, therefore, estimate the escape rates at time step 100 in the main text.
0.4
02
A
0.0
A 0.8
-044
20
40
80
100
Figure 5: Escape rate 7 function of time step obtained when a -1, showing that 7, defined in Equation (73), is indeed a well-defined quantity when is large. y becomes stable after roughly 40 steps.
A.3 ESCAPE RATE EXPERIMENTS
This section illustrates the slow escape problem studied in Sec. 5.2. See Fig. 6. y is calculated by averaging the first 50 time steps across 2000 independent runs. We see that, as our theory predicts, as |a| gets closer 0, the optimal escape rate decreases towards This implies that there exists a landscape such that SGD is arbitrarily slow at learning, independent of parameter tuning. One additional observation that the optimal learning rate is neither too large nor too small, i.e., there seems to be a tradeoff between the escape speed and escape probability (and between the speed and stability). See also the discussion the end of Sec. 5.2.
13

---

Published as a conference paper at ICLR 2022
2.0
1.0
0.2
0.6
< 1.0
0.2
0.2
0.0
-1.
-0.5
0.0
1.0
0.0
0.2
0.4
0.6
0.8
2.0
Figure 6: Escape rate "y as a function of learning rate À with quadratic loss landscape, obtained by simulations. We note that the escape-rate analysis yields results which are compatible with the phase diagram.
1.6
600
5.0
400
-03
-02
200
-38
-15
-15
+3.
Figure 7: Evolution of the distribution of w in landscape where two flat minima and two sharp minima exist. As Proposition 4 shows, the model parameters converge to the sharper minima even if initialized in the flat minimum. Left: Initialization. Mid: step 2. Right: step 10000.
A.4 CONVERGENCE TO THE SHARPER MINIMUM
We use the same 2-dimensional loss landscape defined Sec. 5.3. The experiment run with 2000 independent simulations and learning rate 0.05. See Fig. 7, where we overlap the underlying landscape with the empirical distribution (the heat map). We see that, even though the initialization overlaps significantly with the local flatter minimum, all points converge to the sharper minimum, as the theorem predicts.
A.5 INADEQUACY OF STANDARD ASSUMPTIONS FOR THE NEURAL NETWORK EXAMPLE
In this section, we show that the standard assumptions in the previous literature do not hold for the example studied in Sec. 6.3. One common assumption is that the loss function p-Hessian Lifschitz.
Definition 5. A loss function L is said be p-Hessian Lifschitz if, for some p 0,
Vw, w/, [(w) L" pl[w -w'l-
(15)
This certainly does not hold for the example we considered. Explicitly. let wz 0, the Hessian H(w) of the loss function is
H m2 HWw,, -Hwz.w 0,
(16)
and
H Hwy = =
(17)
Let Wi oo violates the p-Hessian Lifschitz property.
Another common assumption for the non-convex setting is the PL condition.
Definition 6. Let I.* be the value of I. at the global minimum. A loss function I. is said to satisfy the PI. (Lojasiewitz) condition
Vw, /|VI[[(()] ((L())) L*),
(18)
for some > 0.
This also does not hold due to the existence of the saddle point. Let (w1, w2) = (0.0). The gradient zero, but the right-hand side is greater than 0.
Recently, the correlated negative curvature assumption has been proposed to study the escaping behavior of SGD.
14

---

Published as a conference paper at ICLR 2022
Definition 7. Let Vw be the eigenvector of the minimum eigenvalue of the Hessian (w). L satisfies the correlated negative curvature assumption if, for some > O,
Vw, Ww,WEl(Vw (L, w))]=
(19)
where ir the data point.
This also does not hold. The point (0, violates this condition because (L, w) 0 for all
(W1, w2) = (0, 0). In fact, it is exactly this point that violates this condition that the SGD converges in this example.
Recently, the one point strongly convex assumption has been proposed to study the escaping behavior of SGD.
Definition 8. A loss function is said to satisfy the c-one point strongly convex condition with respect to w" for all gradient noise > O, define v w (w)) we have
(-VE, Aw, w y) cl| w vl2
(20)
where is the random noise caused by minibatch sampling.
This assumption is equivalent to that the loss landscape strongly convex after convoluting with the noise. This condition implies that there is only single stationary point. However, this is not the case, consider any point with w1 = and W2 S O. These points have zero gradient for w1 S and so e = with probability 1. Then, these points all have the same loss after the convolution:
E - Xc)] L(v),
(21)
which either imply that the landscape is not convex or that there is more than stationary point, and so the system not one point strongly convex !
'One notices that the origin, where all the parameters are zero, is a special point in the problem. In fact, the origin may be very special point in the landscape of deep neural networks in general. For example, see Ziyin al. (2022a).
15

---

Published as a conference paper at ICLR 2022
B CONTINUOUS-TIME APPROXIMATION WITH FOKKER-PLANCK EQUATION
In this section, we study the examples we studied in the main text in a continuous- approximation, in order to understand the unique aspects of discrete-time SGD. Compared with the discrete-time analysis, continuous-time analysis is usually more powerful in terms of calculation: it is able to deal with more complicated potentials.
B.1
FOKKER PLANCK EQUATION AND ITS STATIONARY DISTRIBUTION
Recall that the SGD update takes the form (see Sec. 2)
Aw, -VVL Av when À < 1, the above equation may be approximated by a continuous-time process (Mandt et al., 2017)
(22)
A VCW))dW())
d = Ldt
(23)
VS
where À is the learning rate; we have also introduced S as the batch size. dW(t) is stochastic process satisfying
(dW ~ dt)d), H[dW (t)dW((tt))))) x o(t-t).
(24)
By the definition of the underlying discrete-time process, the term dw(t) depends only on w(t) and has no dependence on w(t + dt). Thus, the stochastic integration should be interpreted as Ito.
For simplicity, we only consider one-dimensional version of the Fokker-Plane Planck, which is
OP[ w. t (0). a (w, t/ (0), 0),
(25)
Ōt
Ew
where J[w, (O), 0] is the probability flow. The current J[w, (w)( 0] is:
ST.
X² a (C, P(w, (0), 2S dw
J[w, (0)
(26)
Ow
Assuming that the SGD dynamics is ergodic, there is a unique stationary distribution for when t + oo that can be found to
2S J dw C(w) dw
ʃ
1 aL
((w) C(w)
exp
(27)
We will apply this equation to study the relevant problems in this work.
B.2 A GENERAL CASE
In this section, we consider (a slightly more general version of) the fourth-order potential we studied in the main text. The average loss landscape in this model is
I(w) aw2 bno
(28)
where b > 0, guarantees that the w is bounded regardless the value of a. In the limit of - this function reduces to saddle point problem we studied in Sec. 5.1. Besides the SGD noise, additive noise is also present in the dynamics. The variance of the additive noise has no dependence on w. When the additive noise is present, the update rule (equation of motion) is
(w (()(/))) (t)dt) Amm (t) (ta
(29)
where both (1) and na (!) are both Crnstein-Uhlenbee process, denoting multiplicative noise and additive noise respectively. The w-dependent covariance of w is C(w) w². The SGD noise is thus multiplicative noise. Thm (t) and has a variance -8 dt, while the additive noise (f) has variance of o² where is positive constant denoting the strength of the additive noise. If the
vx(1)²
16

---

Published as a conference paper at ICLR 2022
multiplicative noise is seen part of the loss landscape, (2) coincides with the 2nd-order term in the loss landscape. There is no correlation between the additive noise and the SGD noise, ie. (l (t) (t') = 0. The additive noise can be seen the artificially injected noise, a technique sometimes used for aiding the escape or for Bayesian learning purposes (Jin et al., 2017; Welling and Teh, 2011).
The additive noise vanishes in the limit of a - O, and the model becomes a normal SGD with 4th-order loss functiin. is always possible define a noise 7/ (t), whose contribution equivalent to the contribution of both the SGD and the additive noise, and the equation of motion becomes
(t(()) - (1(a/2)((t)) bw bw (t)] + (t)
(30)
This transformed noise (t) thus has mean and variance of ( (w())² +o²) dd. Define v7(1)
((//// w o², the equation of motion becomes
w(t)
dw(() =>\((a/2)w()
bw bw (1) \V
S + +z2((1).
(31)
Comparing with (23), one finds
((w) 2² So²
(32)
The solution of the corresponding Fokker-Plance equation is
25
(a/2) + bw
P(w) oc w² So²
exp
dw
X
w2 So²
25b
( So
w
Sorw
= (w² + -S exp
dw
2 So²
= (w² -S exp
2Sh
wdw
25h
a
So02 S
w + Soz dw
X
2b
Sb
Sa
0²026
= (w² + So0 cxp
w
In (w² + SO?)
21
x
Further simplification yields
P(w) x (w² + 1- sann?
Sb w
cxp
(33)
The function P(w) is finite everywhere and decays exponentially to 0 when - co, regardless of the values of the parameters a, b, o,S. S. This indicates that f dw(w2 So0)-1 - sa exp [-p[- [hshw?
has a well-defined value. As a consequence, there is no concentration of measure. Thus, w(() can be fall into any interval with finite probability after big enough t, indicating that w(t) can be arbitrarily far away from 0. In practice, this means that w(t) escapes from the saddle point 0 regardless of the value of the parameters.
2.0
lardscape
vidil distribution
Final distr ibulion
-0.
-1.0
-0.5
0.0
0.5
1.0
Figure 8: Stationary distribution of with additive noise of = 0.1 with quadratic loss landscape. All the other parameters are identical to those in Fig. I. This distribution has finite width.
The effect of additive noise is better understood when b = 0. In this case, which corresponds to the case shown in 1, neither concentrates
escapes oo.. Instead, it stays near 0 without
17

---

Published as a conference paper at ICLR 2022
converging to it. The stationary distribution of w when b = 0, obtained by numerical simulation, is shown in Fig.8. The other settings are identical to the ones in Fig. The stationary distribution exists, but does not concentrate at 0 in the stationary distribution. First of all, this figure shows that the additive noise helps SGD to escape saddle point. the designed landscape is a part of a realistic landscape, having broader distribution means having more chance of being attracted by another minimum. However, this figure also shows that w would stay in the neighborhood of w 0 until the noise is big enough. Thus, having additive noise and long enough training time does not guarantee the efficiency of escape.
In the language of Bayesian inference, In [P(w)] is the likelihood of w. i, the most probable value of w, is defined by the relation
d d dw
=
(34)
which reads
d
Sa
Sb +5o7)] X w
0
[n((w2+5o)))
[wu +
dw
2X
A
-1
90
b
2,5b
2w
w2
+ So²
w=
Sa
ba
Sb
W
-1
( w + So²)
2X
À
X
a
Sb
2b
The likelihood maximizer
0,
a >
24 5
(35)
96
26
a 5
When -22, the maximum likelihood parameter is w 0. When < <-24 // 5B
-
equally likely. This resembles the phase transition in statistical physics and we call 22 the critical value of a, or, the "critical a". For the energy landscape, when > 0 there is only one global minimum w- and when a 0 there are two global minima at - likelihood solutions, we see that the likelihood maximizer given by SGD is in fact a biased estimator of the underlying minima.
3
26 Comparing with the maximum
There is bias term introduced by the SGD noise in both the critical a and the value of the most probable w. This term vanishes when S co, i.e. when the SGD noise vanishes. This indicates that, when the noise is state-dependent, there is no reason to expect SGD to be an unbiased or consistent estimator of the minimizer, as some works assume.
B.3 4-TH ORDER POTENTIAL WITH MULTIPLICATIVE NOISE
In this subsection, we study a 4-th order loss landscape in SGD dynamics without additive noise. The average loss function with 4th-order term is
aw
b
L(w)
(36)
4 4
the SGD update rule (i.e., the equation of motion) in this case is
1 VS n()(())
dw((t) = - (a{(2))))( + bw (1)]dt
(37)
where the definition of 17 is identical to the previous example. The solution of corresponding stationary Pokker-Planck equation is
P(w)
S0
exp
Sb w²
(38)
x
18

---

Published as a conference paper at ICLR 2022
When
So 2X
< 1,
(39)
P(w) diverges at w = O. The normalization factor, i.e. integral f- dww 22- 30 diverges due the divergence at This solution could be seen as limit of (33) when the additive noise vanishes. As the strength of the additive noise growing while the distribution remains normalized. For O, the function w exp 5 w²] 0, P(w) approaches 0 everywhere except for
exp Sb w²) also
O, the normalization factor keep
is always finite. Thus. in the limit is straight forward to check that the normalization factor diverges slower that P(0) as o - 0. As a consequence, when O, P(w) diverges at 0 and P(w) becomes Dirac delta function. This corroborates with the result in Sec. 5.3 that a small a leads to concentration of measure towards the local maximum.
0. It
Compared with (33), one finds that the additive noise prevents the concentration of measure. Thus, in practice, the additive noise helps SGD escape the local minimum or saddle point. However, the existence of additive noise does not change the critical a and the position of the peaks.
B.4 QUADRATIC POTENTIAL
At last, we consider the continuous approximation of the model treated in the Sec. 5.1, Let the loss function be
T w i
(40)
2
and we have
E [++] @ wh C(w)) = 3 L [vevee
(41)
v L(w.)V((w.)" =
The SGD update rule (i.e., the equation of motion) in 1d is
Aw(() = Ow =trrw(t).
L
(42)
(43)
With the continuous approximation, the equation of motion becomes
dio(t) = -aaa/)))((())) + Vs w()(())
(44)
where 7111 ~N di). By comparing with the 1d Fokker-Plance equation,
L(w) 7 w B(w) = w.
(45)
The stationary distribution of w is
P(w)
exp
S
dw
a
2 x
(46)
The only difference between the solution in this case and the one in the 4th-order-loss case is the exponential factor, showing that the 4th-order potential does nothing but keeping w(t) bounded. The function w 2 & diverges at w 0 or w :o0 depending on the value of a. However, the stationary distribution, being a limit of (33), is well defined. the case that it diverges at w P(w) becomes delta function. On the contrary, there are two peaks infinitely far away from 0 when 2- de diverges not concentrate at 0, corresponding to
oo. Being able escape requires that the probability measure of does
Su 2X
1.
(47)
This straight line agrees approximately with the boundary of the lower branch of the phase diagram in Fig. 9. This condition escaping is worth interpretation. Note that a the local curvature and reflects the strength of the gradient signal. In contrast, the strength of the SGD noise is proportional
19

---

Published as a conference paper at ICLR 2022
to X/S.² The term Sa/2A is thus the signal to noise ratio of this learning problem, and the escaping condition is exactly when the signal becomes larger than the noise. This analysis, therefore, pinpoints the cause of the convergence to saddle points to be the dominance of the SGD noise over the gradient.
Also, this example raises an interesting question regarding the mechanism of SGD that causes a convergence to the local maximum. From the perspective of the types of convergence, the SGD mechanism behind proposition may be different from that of proposition 2. However, from the perspective of continuous-time analysis. there really the same mechanism that governing the SGD dynamics behind proposition and 2 (namely, the fact that the noise has dominated the gradient).
2.0
1.0
0.8
1.5
0.6
1.0
0.4
0.5
-1.0
-0.5
0.0
0.5
1.0
Figure Escape probability as function of a and A. The parameters space is divided into an absorbing phase where w is attracted to the local maximum (in dark blue) and an active phase where w successfully escapes the two central bins (in white). The orange line denotes the analytical convergence bound on À as function of obtained in the discrete-time calculation, while the red dashed line denotes the same bound obtained by the continuous- time calculation. Here the batch size S is set to 1. The result given by the continuous-time process agrees well with the discrete-time process in the small small a limit.
"See Ziyin al. (2022h), for example.
20

---

Published as a conference paper at ICLR 2022
C DELAYED PROOFS
C.I. TWO FREQUENTLY USED LEMMAS
We first prove the following lemma regarding the limiting distribution of In lurel-
Lemma 1. Let the loss function be L(w) 2/ p(z) such that Var[x] o² and [= a << O and that p(x) is continuous in ô-neighborhood of x and wo O. Then, for wi generated by SGD after t time steps.
1
(In|wo/wwol 11) - ~(0,88)
(48)
Vi
where μ E. [n A and 8 Var[Iu Xxr], where À O is the learning rate.
Proof. After steps of SGD, we have
(49)
This leads to
In
W2
Σ In/1 Xarl-
(50)
Wy
Now, since p(1 1z) is continuous in the neighborhood of by assumption, can apply Proposition 6 (appendix) to show that the first and second moment of In - Ax exists, whereby we can apply the central limit theorem obtain
We
Anll) - ~0,
In
(51)
Wg
where s² Var[In/1 Az|] This proves the lemma. O
Proposition 6. (xx-p(()) [In? [x]] is finite if the second moment of p(z) exists and if p(z) is continuous the neighborhood of x 0.
Proof. Since p(z) is continuous in the neighborhood of x = O, then there exists ö > 0 such that for all
lej < 8, 1p(6) -p(x)] e for some e > 0. This means that we can divide the integral over p(x) into
three regions:
(h-p())[nn/xf))) [ drp(x:) In [xr]
(52)
dap(x:) In? |od| S dop(s))n² |o|+ Js- dxp(x) In |ad.
(53)
The second term can be bounded as
S drp(#)) In |o| (p(0) c] S do dolnn
(54)
2[[(()) cl L.² dx In
(55)
-[[ + (In x 21n 2)
(56)
+ +
2m 5 + 2) 00.
(57)
The first and the third term can also be bounded. Since In |a|| is convex function in the regions 2 8 and x S respectively. We can find linear functions ox + of x such that ax + b In for x 2 This leads to
S1 de ln |u| { da p(x)(ax 6)²
(58)
dx p(=) +)2
(59)
Arp(x)(a²2=*) 2abx + b2)
(60)
a p2p 2abbu +b?
(61)
21

---

Published as a conference paper at ICLR 2022
where we have used the notation E[=*]= = jlg and B[x²]= = μ,, which by assumption is finite. The case for 2 - is completely symmetric and can also be bounded by a" f2 2ablu1 + 6². Therefore, we have shown that
Ex) In [x]²] 2 p2 + 2abp1 + 6²) 2(p(0) + c))( (In2 8 2 In + 2) s co.
(62)
This proves the proposition. O
Remark. Note that, the continaity in the neighborhood of is not necessary condition. For example, one can also prove that R.. [In [a|]] is finite if p(x) is bounded and its second moment exists.
C.2 PROOF OF PROPOSITION
Proof. The case when Wo = 0 is trivially true, we therefore consider the case wio * 0. By Lemma 1, we have
1 ct
~0,66)
(63)
where we have defined 24 means that
1
(In
tu), 1==
E[In |
Ax|] and 8² Var[In|1 Ax[]. This
/
we
W
W
lim
In
lim t-000
exp
In
ty
(64)
t0000
wo
21.²
By definition, luvd /wole tu Therefore, we have
(Iroleteen lim P(perl c) lim P (Irole Te-ly > ))= 1-+00
0 if μ 0: μu 0,
(65)
for all O. In other words, since μ and o are t-independent, in the infinite limit, the sign of becomes crucial. When > O, the limiting distribution diverges to infinity; when μ < 0, |wv converges to in probability. This finishes the proof.
C.3 PROOF OF COROLLARY
Proof. By the definition of p(z),
= M[In|1 - Ax|]
(66)
In|1 X/ ++|In||1 |n|11X0 A(a-aaa1)
In|1
(67)
2
1n|(1-1)(1
1) -(aa 1)){
(68)
while 2² is indeed constant in time. Therefore, the asymptotic distribution of w, is solely dependent on the sign of p. The above equation implies that μ 0 when
((1 - (1-A)[1- - A(a 1)]] > 1.
(69)
When À S 1, the above equation is solved by
A
(70)
a 1
When À 1, the above equation solves
a / Sa + 8
X
(71)
2(a 1)
only when the learning rate satisfies the above two conditions can escape from the local maximum. Conversely, SGD cannot escape the local minimum when
a 5As a -
Va²
8a
(72)
2(a-1)
We done. D
22

---

Published as a conference paper at ICLR 2022
C.4 PROOF OF PROPOSITION 3
Proof. By Lemma I, we have that
E
In
Wt
(n((1- - 2)(1 A(a- 1)]];
(73)
Wo
2
where the second equality follows from the assumption that À < 1. We differentiate with respect to to find the critical escape rate:
a
(74)
2)
Since is convex in A, it follows that this critical escape rate is the maximum escape rate. Plugging this into μ,, we obtain that
((X*) = (2- = In
2 - a 4)1-a) 2 Se
(75)
ie., the optimal escape rate can be made smaller than any e if we set
|a| 2 -e
(76)
This finishes the proof. C
C.5 PROOF OF PROPOSITION 4
Proof. suffices to show that wa converges to 0 with probability 1 because, if this is the case, the only possible local minimum to converge to is (w1, w2) = (0, +v
Ita
The SGD dynamics
Awi1 = 1oo-==-X(221.... Awi, 12u3, wi,t x,bwi1,);
(77)
Awyy = -X(-2w2, + 4w + 12w W22 2aw22,)-
We focus the dynamics of w1. By the definition of the noise we have that wi,+ [1 + X(2 -) 4xw 12Au with probability 1/2:
W1.+1
wi, [1 + X(2 + b) 4xw 12 with probability 1/2.
(78)
Equivalently,
W1,t+1
1+ 2(2-((2))) - 4uu 12
with probability 1/2:
(79)
1+ 122x22+2 b)) -xw
12 with probability 1/2.
W1.r
Since 0 4A + 12\w2, 16A,, we can define new random variable rz:
[max() (|1 X(2 D)), X(2 0) 16X)) if xr 2 0; mmx X(2 (1+ A(2 6) 16X1)
r = r(z)) =
(80)
if x; s 0.
By construction, r; 2 |1 /wi,d for all values of mt. This implies that | IT. rs and
so,
[ r >c))
P(wwi// w c) s P
(81)
i.e., if [[ Fx converges to 0 with probability 1, wi,t must also converge to zero with probability 1.
We let } 6 (note that this is the value of b such that is minimized for both cases), and obtain that
8A
if 2, 2 O;
max (|1 2X1, 11 10AI) The rest of the proof follows from applying the central limit theorem to 7 Σi= Inr, in Lemma 1. The result is that [ r converges to 0 with probabiliy 1 if
Pt
if ,4 0.
(82)
===EE[1r Inr,
In In(8) 2N, |1 10A))<< O.
(83)
The above inequality solves to
1
As
- (1+V6)
(84)
20
which is of order O(1) stated in the theorem statement. This proves the proposition.
23

---

Published as a conference paper at ICLR 2022
C.6 PROOF OF PROPOSITION 5
Proof. First we note that, since |wx] s 1
1 = | s 1 + a.
(85)
By the definition of the AMSGrad algorithm, we have that
vt = 32 + (1 32)
(86)
i (
(87)
Since do = and [eel | s 1 we have that
14 ss+
(88)
for all t, and so
max 0, max vs 1
(89)
Meanwhile, since & monotonically increasing series and upper bounded by + a, it must
converge to a constant ( < c +
Now, as before, we want to upper bound the random variable
1
In
In
11
(90)
Wt
where μ E[In M5x11
Since 0 converges to c, there must exists positive integer (()) such that
for any 6 > 0, UN $ cc-c c. This allows us to divide the sum to two terms:
W++1
1
A
I
In
4
(91)
W/
V
Ut
A
In
1
In
hx Ft
16
(92)
0z
i=N+1
where we introduced 0 s k2 S e. But the first term is of order O(1/vl) and converges to O, and so for sufficiently large f, the first term is also smaller than arbitrary e. This means that
in
In
- H +
(93)
1=1
Ve-
kt
We consider the random variable
with probability with probability
21
(94)
k
a)
We now define a new random variable
if oz
rx(x)) == 1+
(95)
(1- a1
if = -
where we defined the constant m := max(11 A/va.11 A/Ve- c)) One can easily check that
Ti 2 m. This means that
.o.
P p 1-0
We1 wo
(96)
i.e., if rr converges in probability, the proof of Proposition 2. One finds that the condition for r; converge in probability to 0 is
MP++ Mio
must also converge 0 in probability. Proceeding in
m
- a) <0,
(97)
24

---

Published as a conference paper at ICLR 2022
which is equivalent to
A (1
|
a)
<1.
(98)
Since is arbitrary, we let 0 and obtain
(
(1 a) 51.
(99)
Denote A/Vcas as X, this condition solves to
a Va² 8a 88
S X
(100)
a-1
2(a- 1)
Setting a such that the above condition met, AMSGrad will converge to probability, For À This completes the proof. C
25


Reviews:
[{"review_id": "vRtNZYC8iPM", "reviewer": "Reviewer_bMKE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper brings a very interesting viewpoint on the optimization process of SGD. I think it is widely conjectured that adding noise to the optimization algorithm is beneficial (e.g. Jin et al. 2017). In this paper, several artificial examples are given where adding noise can have the opposite effect, e.g. SGD may converge to a global maximum while using GD on the population loss of the same objective will not. This raises many interesting questions regarding the effect of noise in optimization and is a novel contribution as I understand it. \n\nThe authors also provide several different examples for which SGD behaves in an unintuitive way, e.g. converging to a sharp minimum rather than a flat one. This may show that the results for implicit bias (which are usually given for GD or GF) may not be directly applicable to SGD. The experimental section is also nice and provides empirical evidence for the validity of the theoretical results. Specifically, the one neuron example provides evidence that when the assumptions from previous papers on escaping saddle points are not satisfied, then it may happen that indeed SGD may not escape them.\n\nThere is one important issue which I would be happy to see the author’s response:\n\nThe difference between the results in Section 5.2 and 5.4 is confusing. In 5.2 the claim is that even if the learning rate changes, then SGD may escape saddle points slowly. In Proposition 3 there doesn’t seem to be any sign that the learning rate can change. If it doesn’t change during training, then how is this result different from the one given in 5.1?\nIf the learning rate does change, then in Section 5.4, AMSGrad without momentum is just SGD with an adaptive learning rate, how is it different from the result in 5.2?\n\nThere are also some issues with the presentation, but  I believe they can be fixed:\n\n1) What is \\delta in Proposition 3 and Corollary 1? The only definition of \\delta I found was in Lemma 1 in the appendix. If it is really as defined there then it is extremely confusing and should be defined in the main part of the paper.\n\n2) In Definition 3, why is w_t inside ln? Could it just be defined without ln? I think the authors should provide some intuition for this definition.\n\n3) Having both Theorem 1 and Proposition 3 is redundant. I think it would be clearer to just write the main result here.\n\n4) Also, Theorem 1 talks about *the* saddle point, while from the phrasing of the theorem it is not clear why there is a single saddle point.\n\n5) Figure 2 is not a figure, but an algorithm (or just a list of equations).\n\n6) Beginning of Section 6: what the underline should highlight? It breaks in a middle of a word…\n\n7) The d subscript on the arrow (e.g. equations 59, 62). Is it convergence with probability? I think this is a non-standard notation and should be defined.\n", "summary_of_the_paper": "The paper provides several artificial examples on which SGD has an unintuitive behavior. This includes: (1) SGD converges to a local maximum; (2) If the learning rate is not fixed then SGD takes arbitrarily long time to escape saddle points; (3) SGD may prefer sharper minima (in contrast to several hypotheses regarding the implicit bias of GD); (4) Adaptive methods may also converge to a global maximum. Several experiments are made, varifying the theoretical results.", "summary_of_the_review": "I think this paper provides an interesting and novel view on SGD, and brings forward scenarios for which SGD behaves differently from GD and from the intuition provided in previous papers. This is an important step in understanding the optimization process of SGD, its limitations, and its benefits. There is one issue which I would be happy to see the author’s response. There are also some issues with the presentation which I think can be fixed. In total, I believe the merits of this paper outweigh its flow and it should be accepted.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "maZxNLjuau7", "reviewer": "Reviewer_k2vd", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\nThe abnormal behavior of SGD is out of expectation from the first sight. At the same time these behaviors should be as expected because the experimental settings are specifically chosen and break usual assumptions.\n\nStrong points.\nThe paper has explicitly demonstrate the convergence point in expectation is distinct from that with high probability. In practice, people care more about the convergence with high probability. Thus, this paper emphasizes the importance of the convergence with high probability.\nThe paper questions the usual assumptions and gives convincing theoretical and empirical evidence. This view of research is encouraging.\nThe paper is clear and easy to follow. The reviewer verified several claims and did not find wrong points, though the whole proof was not thoroughly examined.\n\nWeak points.\nThe artificial examples are far from the optimization of practical neural network. To make the result more convincing and useful in practice, it still needs to study the with high probability of the model setting and data setting, how SGD will perform and whether the constructed scenarios will be encountered.", "summary_of_the_paper": "\nThe paper constructs example optimization problems to illustrate that SGD may behave strangely, out of common expectation, when some assumption is removed, e.g., decaying learning rate and the noise nature. It shows that SGD can converge to local maxima with high probability for specific cases. ", "summary_of_the_review": "The paper has interesting observations including  for SGD, which are not carefully discussed in literature. Personally the reviewer would like to see the paper published on important venue like ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kn7ixqa8Xdj", "reviewer": "Reviewer_DCLz", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "## Post-discussion reassessment\n\nSee relevant post below.\n\n## Evaluation and recommendation\n\nThere are two axes that have to be evaluated in this paper: the mathematical value of the authors' contributions, and the positioning thereof. Regrettably, my assessment varies drastically along these two axes: while I find the authors' results mathematically interesting and suitable for ICLR, the overall narrative is encumbered by a series of vague and often confusing statements that are (a) detrimental to the paper; and (b) not needed in the first place. Thus, while on the mathematical axis I consider the paper to be a good fit for ICLR (I would rate it around a 7), the reported results do not suffice to support the paper's (overly ambitious) narrative claims, hence my overall reject recommendation.\n\nI believe that these shortcomings can be mitigated by toning down the paper's claims - but this will also require significant work from the authors. For this reason, I am providing below some necessary context for item (1) above (which, judging from the paper's title, seems to be what the authors consider to be the main contribution of the paper).\n\nTo begin, if we consider ordinary (non-stochastic) gradient descent applied to the loss function $L(w) = w^2/2$, it is trivial to see that the generated sequence explodes in value if $\\lambda>1$ – perhaps the worst possible \"convergence to a global maximum\" catastrophe that one could encounter. This is a fundamental and inescapable failure of gradient descent: if the step-size is not chosen appropriately, all sorts of undesirable phenomena can be observed (both in practice and in theory). Well-documented failures of this type are precisely the reason that the tuning of the step-size of SGD plays such an important role in the field. Hence, in this context, the authors' statement that undesirable phenomena (convergence to maximizers) can indeed occur if SGD is run with a large, out-of-tune step-size is hardly \"surprising\". [To be clear, I _do not_ believe that a result needs to be \"surprising\" in order to be worthwhile, but I _did_ lose count of how many times the authors claimed their results are \"surprising\".]\n\nNow, what is interesting in the authors' analysis is the specification of the range of $\\lambda$ for which these deleterious outcomes can arise in the quadratic toy model of item (1) above and the CLT analysis that they provide (which, incidentally, relies heavily on the specific loss model considered). However, what lessons can be inferred for neural network training from this 1-dimensional example is highly debatable - and the authors' one-neuron, quadratic-activated \"neural-network-like\" example in Section 6.3 is no less artificial than the examples of Sections 4 and 5. [By the way, given that both of the authors' examples are custom-made to allow calculations in quasi-closed form, statements concerning \"restrictive and unrealistic assumptions about the nature of the noise\" seem out of place.]\n\nWhat I found lacking in the above is a thorough comparison with the work of Ge et al. [1]. Specifically, how does the authors' \"trapped regime\" compare to that predicted by [1]? More concretely, if we take Corollary 1 as a starting point, what is the precise value for $\\lambda$ below which [1] guarantees saddle-point avoidance? Is there a gap with the authors' trapping bounds or are they sharp? Given that the two results – that of the authors' and that of [1] – indicate completely different behaviors for (SGD), I would expect a much more in-depth comparison between the two.\n\nIn a similar vein, it is also unfortunate that the authors seem to ignore a series of results showing that SGD with a decreasing step-size avoids saddle-points with probability $1$ – cf. the general paper [2] and the more recent references [3,4] below. In fact, one of the most popular neural network training methods involves staircase step-size schedules that begin at a large value which is then progressively halved towards the end of the training horizon - and this, precisely to enhance the algorithm's convergence properties. The authors' theory does not cover this important part of the literature, so their claims are - at best - incomplete in this regard.\n\nTo summarize, the paper does not \"run counter to the established wisdom of the field\". If anything, it serves to _reinforce_ this wisdom by providing an interesting cautionary tale to the effect that \"SGD _with a large, constant step-size_ can converge to local maxima\".\n\nIf the authors can provide a revised version toning down the various overselling issues identified above, I would be happy to raise my score accordingly. Otherwise, even though I find the paper's mathematical contributions interesting and suitable for ICLR, I cannot recommend acceptance at this stage: the paper contains a number of \"sound bite\"-like statements that are non-mathematical and not appropriate for a theory paper, so this would only serve to increase confusion in the field.\n\n\n## Specific comments\n\nTo help the authors, I am providing below a list of specific points that should be revised to better reflect the paper's actual contributions.\n\n1. Title: see above. Without any further quantifiers (and despite the word \"can\"), the current title suggests that \"convergence to maximizers\" is a ubiquitous phenomenon - whereas it is anything but.\n\n1. Abstract: the statement concerning restrictive and unrealistic assumptions is out of place. If the authors refer to the \"multiplicative\" nature of the noise, they should note that the stochastic loss function $\\hat L(w;x) = (w-x)^2/2$, $x\\in\\{-1,1\\}$, has additive noise at its minimum and it is neither more nor less \"realistic\" than their toy example. In fact, it can be argued that the principal reason that the author's example exhibits convergence to a non-minimizing stationary point is that all batches become critical at the _same_ point - but, in turn, this is an unrealistic assumption in itself.\n\n    At any rate, blanket statements like this should be avoided unless the authors are prepared to back them up with a deeper theoretical treatment.\n\n1. A minor - and, admittedly, subjective - remark: the choice $a<0$ can become confusing in reading the various expressions (keeping track of what is negative and what isn't). I believe it would improve readability if $x$ took the values $1$ and $-1-a$ with $a>0$ (i.e., switching notation from $a$ to $-a$), but this is of course up to the authors.\n\n1. A more important issue: the $a>0$ case is poorly explained in the paper and the corresponding part of Fig. 1 is misleading. For $a>0$, convergence to $0$ is the desired behavior, so coloring that region as \"problematic\" is not appropriate.\n\n1. I was bemused with the \"sharp vs. shallow\" statement: especially since the trace of the Hessian is only a local attribute that does not suffice to characterize the basin of attraction of a (non-quadratic) minimum, I do not see why this is \"counter to established wisdom to the field\". Again, I would recommend providing an accurate mathematical description and letting readers draw their individual conclusions instead of trying to maneuver the narrative in this way.\n\n1. The authors are making a series of claims for the applicability of their results to neural networks, but these are based on a \"network\" with a single neuron. I would again recommend moderation - otherwise, this is a textbook case of a faulty generalization.\n\n1. The statement that \"SGD noise is multiplicative and state-dependent\" is too vague and lacks context. Again, I understand that the authors wish to motivate their specific counterexample, but blanket statements like that only serve to weaken their paper - not strengthen it.\n\n1. When mentioning continuous-time approaches, I was surprised that the authors did not discuss the stohastic approximation framework for the study of SGD by Ljung, Kushner and Yin, and Pemantle (to state but some of the most classical results). I already mentioned this literature in the context of SGD with a decreasing step-size above, and since the authors seem to be interested in the continuous-time limit, this is a second reason why this literature should be discussed in detail. This also comes up when discussing related works in p.2 (as these works do not assume \"artificially injected noise\").\n\n1. Still on the issue of related work: the authors seem to be confusing the Polyak-Łojasiewicz condition with the Kurdyka-Łojasiewicz condition. The former is global, and indeed restrictive; the latter is local, and includes all semi-algebraic functions (or more general any function defined by an o-minimal structure). I would encourage the authors to study in more depth the work of Bolte and co-authors on the topic - and, in addition, I would like to point out that all examples considered by the authors satisfy the KL condition.\n\n1. Appendices B and C are quite disconnected from the rest of the paper: they concern a completely different model with very different results and attributes, so I would suggest removing them altogether.\n\n1. While interesting and easy to work out, Proposition 1 is very special: if $\\lambda=1$, we get an exact Newton update, which gets to $0$ in a single iteration, and thus remains there forever due to the authors' multiplicative randomness model. In this regard, Proposition 1 is not truly representative of what's going on (e.g., in Proposition 2).\n\n1. In their discussion of Proposition 1, the authors also briefly discuss the difference between convergence in probability and convergence in expectation. I believe this distinction in the modes of convergence of random variables is an important take-away of this work, and one worth describing in more detail. If the paper's message is that we need to be careful about how we interpret SGD convergence and avoidance results, then this should be made clearer.\n\nOverall, I trust that the above should suffice to indicate the tone and tenor of the changes that would be expected from a revision. As I said, the authors do not need to oversell their contributions: in my opinion, the mathematical content of the paper is enough for ICLR, and taking a more factual approach in describing said contributions would be much better for the paper.\n\n\n\n## References\n\n[1] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points – Online stochastic gradient for tensor decomposition, COLT ’15: Proceedings of the 28th Annual Conference on Learning Theory, 2015.\n\n[2] Robin Pemantle, Nonconvergence to unstable points in urn models and stochastic aproximations, Annals of Probability 18 (1990), no. 2, 698–712.\n\n[3] Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher, On the almost sure convergence of stochastic gradient descent in non-convex problems, NeurIPS ’20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.\n\n[4] Stefan Vlaski and Ali H. Sayed, Second-order guarantees of stochastic gradient descent in non-convex optimization, https://arxiv.org/abs/1908.07023, 2019.", "summary_of_the_paper": "## Post-discussion reassessment\n\nSee relevant post below.\n\n## Summary of contributions\n\nIn this paper, the authors examine whether SGD with a large, constant step-size avoids local maximizers (or, more generally, undesirable saddle points of the underlying minimization problem). More precisely, they focus on the algorithm\n$$\nw_{t+1} = w_t - \\lambda \\hat g_t\n$$\nwhere $\\lambda>0$ is the algorithm's step-size, and $\\hat g_t$ is a (stochastic) gradient of the (stochastic) loss function $\\hat L(w;x)$, with $x$ a random variable.\n\nThe paper's results can be summarized as follows:\n\n1. If $\\hat L(w;x) = (x/2) \\cdot w^2$, the authors identify a range of values of $\\lambda$ (which depends on the distribution of $x$) such that, in probability, $w_t$ converges to $0$ – which, under the specified distributional assumptions for $x$, is the global maximum of $L = \\mathbb{E}[\\hat L]$. This is made precise in Propositions 1 and 2, and Corollary 1.\n\n2. They provide a quartic loss function under which SGD converges to the function's sharper minimizers (as measured by the trace of the Hessian at said points). [Proposition 4]\n\n3. They provide a specific range of parameters under which the AMSGrad algorithm converges to the undesirable maximizer of item (1) above.\n\n[In the supplement, the authors also provide an analysis of a gradient-like diffusion (Appendices B and C), which they discuss as a continuous-time model of (SGD). This part is not directly connected to the rest of the paper, so I am not including it in my evaluation below.]", "summary_of_the_review": "There are two axes that have to be evaluated in this paper: the mathematical value of the authors' contributions, and the positioning thereof. Regrettably, my assessment varies drastically along these two axes: while I find the authors' results mathematically interesting and suitable for ICLR, the overall narrative is encumbered by a series of vague and often confusing statements that are (a) detrimental to the paper; and (b) not needed in the first place. Thus, while on the mathematical axis I consider the paper to be a good fit for ICLR (I would rate it between 6 and 7), the reported results do not suffice to support the paper's (overly ambitious) narrative claims, hence my overall reject recommendation.\n\nThe detailed scores below do not refer solely to the paper's technical proofs, but they also take into account the various non-mathematical claims made by the authors throughout the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_XwPiKR08i3", "reviewer": "Reviewer_Jqcm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found this paper thought-provoking and enjoyable to read. The fundamental concept it suggests seems to be that we need to think more carefully about our assumptions and goals when proving results about optimization algorithms - e.g. it is often believed that convergence to critical points is fine since very likely adding a little noise will prevent converging to maxima or escaping saddle points.\n\nThis leads to my first objection: the theoretical results would be much improved if they included an analysis of adding a small amount of noise to SGD's iterates. However, from looking at the constructions my intuition is that such perturbations may not change the overall message of the paper too much.\n\nAnother missing component is an analysis of the \"theoretical standard\" decaying learning rate of $O(1/\\sqrt{t})$ (note that AMSgrad does not have this decaying property).\n\nMy main concern thus is that the paper is perhaps not going the full distance to realize its goals, and I would encourage the authors to address these issues in the revision. However, I think overall the observations are useful and may inform future thought about design of optimization algorithms or analysis.\n\nNote: for proposition 3, I believe do you need to say that $a<0$?", "summary_of_the_paper": "This paper demonstrates on several fairly simple (e.g. 1-dimensional quadratic) objectives that stochastic gradient descent may easily have very poor behavior: it could converge to a maximum, or diverge even in convex settings if the learning rate is too high. \nSpecifically, it is shown that for any learning rate, there is is a distribution over quadratics whose expectation is $-rx^2$ for some $r\\ge 0$ such that SGD will converge to the maximum at 0, and there is also a distribution whose expectation is $rx^2$ such that SGD still diverges even on this convex loss. Note that the distribution (and $r$) depend on the learning rate.\nFurther, there are distributions such that SGD must escape a saddle point very slowly, and a distribution over 2-dimensional quartics such that SGD will converge to a \"sharp\" rather than a \"flat\" minimum.\nIt is also shown that AMSgrad must converge to a local maximum on some non-convex distributions.\n\nThe results are proven by choosing a particular distribution over quadratic objectives that causes the logarithm SGD's iterate to be a sum of i.i.d. random variables. Then the central limit theorem provides an understanding of the limiting behavior of these iterates.\n\nThe results are augmented by empirical studies verifying the theorems directly, along with a very simple small neural network experiment.", "summary_of_the_review": "The paper introduces some interesting examples accompanied with relevant commentary. The examples are simple enough to be easily understood, but may leave a bit to be desired in generality.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Ti7x4Vx8QUd", "reviewer": "Reviewer_MX9i", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well written and has a good presentation. The work constructs some examples to illustrate the possible counter-intuitive phenomena of SGD. While the main point of the paper is very interesting, it is not clear what can we learn from these special example problems. \n\nSpecifically, the example in eq.(2) constructed to show convergence to local maxima has a very special structure that is unlikely to occur in machine learning practice. The main point conveyed by the authors is that the population loss associated with eq(2) is a strongly concave function with a local maxima point at $w=0$, and if we perform SGD with the constructed Bernoulli data distribution, then it is possible that SGD converges to this local maxima w.p. 1. However, the constructed Bernoulli data distribution generates negatively correlated data samples, i.e., $x = 1$ or $-1+a, a<0$. This is the main reason that SGD may get stuck at this local maxima, because the loss associated with the data $x=1$ has a strongly convex landscape while the data $x=-1+a$ has a strongly concave landscape. Hence, one can find a regime of learning rate in which the gradient descent on the strongly convex loss dominates the strongly concave loss, and converges to the maxima. However, this requires the data points are highly negatively correlated, which rarely happens in machine learning practice. \n\nThe other constructed examples in the paper have similar issues. Overall, the examples given in the paper may be too extreme to provide a good understanding of SGD in machine learning practice. On the other hand, this may suggest that in addition to the existing assumptions of SGD, there might be other undiscovered structures in deep learning that prevent SGD from behaving anomalously.\n", "summary_of_the_paper": "Many theoretical works have studied SGD, but they commonly rely on\nrestrictive and unrealistic assumptions about the noise. In this work,\nthe authors construct example optimization problems illustrating that, if these assumptions\nare relaxed, SGD can exhibit many strange behaviors, including (1) SGD can converge to\nlocal maxima, (2) SGD may escape saddle points arbitrarily slowly, (3) SGD\ncan prefer sharp minima over flat ones, and (4) AMSGrad can converge to local\nmaxima.\nTherefore, the authors conclude that in the most general nonconvex case, many counter-intuitive phenomena of SGD may arise and\ncontrast to the commonly held presumptions.", "summary_of_the_review": "See the comments above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the paper provides interesting counter examples for the SGD with constant step-size (that relies on a relative noise model that diminishes at the critical points), which provide critical (counter) insights into what we consider as good convergence metrics, such as expected norm of the gradient. 

The initial submission took a controversial position between the mathematical statements and the presentation of the statements on the behavior of the SGD method in non-convex optimization problems. While the mathematical is sufficient for acceptance at ICLR, the presentation was inferring conclusions that could have been misread by the community.

I am really happy to state that the review as well as the rebuttal processes helped improved the presentation of the results that I am excited to recommend acceptance.
Decision: Accept (Spotlight)