Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: ## Post-discussion reassessment

See relevant post below.

## Summary of contributions

In 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
$$
w_{t+1} = w_t - \lambda \hat g_t
$$
where $\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.

The paper's results can be summarized as follows:

1. 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.

2. 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]

3. They provide a specific range of parameters under which the AMSGrad algorithm converges to the undesirable maximizer of item (1) above.

[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.]
main_review: ## Post-discussion reassessment

See relevant post below.

## Evaluation and recommendation

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 around a 7), the reported results do not suffice to support the paper's (overly ambitious) narrative claims, hence my overall reject recommendation.

I 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).

To 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".]

Now, 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.]

What 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.

In 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.

To 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".

If 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.


## Specific comments

To help the authors, I am providing below a list of specific points that should be revised to better reflect the paper's actual contributions.

1. 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.

1. 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.

    At any rate, blanket statements like this should be avoided unless the authors are prepared to back them up with a deeper theoretical treatment.

1. 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.

1. 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.

1. 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.

1. 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.

1. 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.

1. 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").

1. 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.

1. 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.

1. 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).

1. 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.

Overall, 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.



## References

[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.

[2] Robin Pemantle, Nonconvergence to unstable points in urn models and stochastic aproximations, Annals of Probability 18 (1990), no. 2, 698–712.

[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.

[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_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.

The 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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
Specifically, 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.
Further, 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.
It is also shown that AMSgrad must converge to a local maximum on some non-convex distributions.

The 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.

The results are augmented by empirical studies verifying the theorems directly, along with a very simple small neural network experiment.
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.

This 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.

Another 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).

My 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.

Note: for proposition 3, I believe do you need to say that $a<0$?
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 
The 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. 
main_review: 
The 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.

Strong points.
The 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.
The paper questions the usual assumptions and gives convincing theoretical and empirical evidence. This view of research is encouraging.
The 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.

Weak points.
The 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Many theoretical works have studied SGD, but they commonly rely on
restrictive and unrealistic assumptions about the noise. In this work,
the authors construct example optimization problems illustrating that, if these assumptions
are relaxed, SGD can exhibit many strange behaviors, including (1) SGD can converge to
local maxima, (2) SGD may escape saddle points arbitrarily slowly, (3) SGD
can prefer sharp minima over flat ones, and (4) AMSGrad can converge to local
maxima.
Therefore, the authors conclude that in the most general nonconvex case, many counter-intuitive phenomena of SGD may arise and
contrast to the commonly held presumptions.
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. 

Specifically, 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. 

The 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.

summary_of_the_review: See the comments above.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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. 

The 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.

There is one important issue which I would be happy to see the author’s response:

The 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?
If 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?

There are also some issues with the presentation, but  I believe they can be fixed:

1) 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.

2) 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.

3) Having both Theorem 1 and Proposition 3 is redundant. I think it would be clearer to just write the main result here.

4) 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.

5) Figure 2 is not a figure, but an algorithm (or just a list of equations).

6) Beginning of Section 6: what the underline should highlight? It breaks in a middle of a word…

7) 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.

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.
review_title: null

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)