Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods

Summary

This paper shows mainly two things: (a) SGD suffers from an exponential dependence on the initial stepsize if it is not tuned to be smaller than the learning rate. This exponential dependence is unavoidable. (b) Methods with gradient normalization and running gradient sum normalization, such as Normalized SGD, AMSGrad, and AdaGrad, suffer no such exponential dependence on the smoothness constant. The paper also presents a novel analysis of AMSGrad that removes the bounded gradients assumption.

Strengths

1. The result on AMSGrad is new and a welcome addition to the literature. 2. The paper's emphasis on the benefits of normalization even in the deterministic setting is good, since this is a point quite overlooked in the community.

Weaknesses

1. The result on the exponential dependence on the smoothness constant is a known consequence of another result in the literature. Under the assumption on the stochastic gradients $\mathbb{E} \|g(x)\|^2 <= 2 A (f(x)-f_*) + B \|\nabla f(x\||^2 + C$. Note that bounded stochastic gradient variance corresponds to $A=L$, $B=0$ and $C=\sigma$ (since bounded variance implies $E||g(x)||^2 <= ||\nabla f(x)||^2 + C <= 2 L (f(x)-f_*) + C$). The result of Theorem 2 in [1] gives for this choice ($A=L$, $B=0$, $C=\sigma$) a rate of $\frac{(1+\gamma^2 L^2)^K}{\gamma K} \delta_0 + L \gamma C$ where $\delta_0$ is the initial suboptimality. The lower bound is also known, see [2, Theorem 5]. [1] Khaled and Richtárik. Better Theory for SGD in the Nonconvex World. arXiv:2002.03329 [2] Vaswani, Benjamin Dubois-Taine, and Babanezhad. Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent. arXiv:2110.11442.

Questions

1. Please address the difference between your results and the results I've mentioned in the weaknesses section.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

The authors investigate the behavior of untuned SGD in the smooth nonconvex setting and show a new result on the convergence rate of SGD w.r.t. to gradient norm, where there is an exponential dependence on the smoothness constant. They further argue that the exponential dependence is unavoidable through a constructed class of 1-dimensional nonconvex functions. The paper then examines NSGD, AMSGrad and AdaGrad and shows that the exponential dependence can be avoided through adaptiveness, albeit without any information about the problem parameters.

Strengths

This paper offers an interesting theoretical perspective on the explosive gradient problem and the nonconvergence properties of SGD. The authors complement their theoretical results and ideas with numerical illustrations, and the paper is easy to follow. Their results seem well-justified, but I did not check their proofs in the appendix. I believe this work is of interest to the NeurIPS community.

Weaknesses

1) The current state of numerical experiments seem preliminarily and is only done on one dataset MNIST on a small-network. I would like to see a more comprehensive investigation into larger practical networks, perhaps from [6, 24, 54].

Questions

1) In figure 1, what is the size of each layer in the 3-layer neural network? What effect does over-parameterization have on the untuned SGD behavior?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes, the authors have addressed their limitations through the checklist.

Summary

This paper analyzes the complexity of finding an $\epsilon$-stationary point for untuned SGD and compares that with three families of adaptive methods - NSGD, AMSGrad and AdaGrad. Compared to previous convergence analysis results for tuned SGD and Adaptive methods: this work gets rid of several assumptions that hides the true convergence behaviour of these algorithms. Specifically, the authors do not assume the step-size for SGD to be dependent on the smoothness parameter (hence untuned) and do not assume bounded gradients for the adaptive methods. These leads to an interesting comparison for convergence of these algorithms.

Strengths

1) The authors show that untuned SGD converges to an $\epsilon$ stationary point in $O(e^{\eta^2 l^2}\epsilon^{-4})$ iterations. Although this algorithm does have optimal dependece on $\epsilon$ , it has a disastrous exponential term wrt the smoothness parameter $\eta^2 l^2$, Hence, the assumption on bounded gradients or chosing the $\eta$ to depend on $l$ is problematic, because we may not have prior knowledge of $l$. They show that even for a smooth 1D-function, the assumption of bounded gradient is problematic. This is indeed true and the experiment in figure-1 supports this claim. 2) Adaptive gradient methods adjust their step-size based on observed gradients and hence can decrease the stepe-size when encountered with a large stepe-size preventing blow-up. This work does not assume bounded gradeint assumption for these methods and show that the convergence rate does not exponenetially depend on the smoothness parameter making it more stable than untuned SGD. The core strength of the paper lies in removing assumption on bounded gradients revealing true dependency of these algorithms on smoothness parameter $l$ which highlights the advantage of adaptive methods over untuned SGD.

Weaknesses

Disclaimer: I am unfamilair with recent developments in this specific diretion. But still i really enjoyed reading this work and I feel it improves over existence convergence results. I have a few questions that i encountered but I don't list them as major weaknesses: 1) the constructed function $f(x) $ in Figure-2 does not look so. Is there an extension of the function outside the segment-1. If so, the author should mention that. Although the equation for sregment-4 and segment-1 are still provided, segment-2 and 3 are still missing. 2) From theorem-1, the main reason untuned SGD may blow up is that some initial $\eta \geq \frac{1}{l}$. But in practice SGD also converges with a small constant learning rate which does fall into this regime and in this regime it does not blow up. However, it is mostly observed that initial large learning rate SGD performs better in terms of generalization [1] . If practitioneers use a small enough (but contant) leanring rate $\eta \leq \frac{1}{l}$, then the whole issue of gradient blow-up can be avoided. Even in such practical cases, no prior knowledge of $l$ is required to select step-size $\eta$. So is it true that achieving generalization is the bottleneck in chosing step-size as large as possible ? [1] Li, Yuanzhi, Colin Wei, and Tengyu Ma. "Towards explaining the regularization effect of initial large learning rate in training neural networks." Advances in Neural Information Processing Systems 32 (2019).

Questions

See the points above for the questions.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

i believe the whole problem of gradient blow-up can be avoided by just using small enough practical $\eta$ according to Thoerem-1. But that would hurt generalization in overparameterized networks. Hence, I believe comparison of constant step SGD $\eta$ and other adaptive gradient methods should also be done in terms of generalization and not only convergence. This would give us the full picture.

Summary

This work analyses the rate of SGD and other adaptive SGD methods in reducing $\\mathbb{E}\\|\\nabla f(x_t)\\|$, where $f$ is non-convex $L$-smooth, and shows that SGD has an exponential dependence on $L$ when the stepsize is not properly tuned, while other adaptive methods do not incur this exponential dependence.

Strengths

The analysis presented in this work is fresh and interesting. The authors make a compelling case that removing the bounded gradient assumption is perhaps essential in revealing a crucial advantage of adaptive SGD methods over standard SGD. As I explain in the weakness section, I think the qualitative idea behind the described phenomenon is known. However, the quantitative results are, as far as I know, new and, in my opinion, very interesting. I think the qualitative understanding gained by the quantitative analysis is valuable, so I vote for the paper to be accepted.

Weaknesses

At a high level, one can argue that the result was "known" in the following sense. When a LR schedule of $\\eta_k=\\eta/\\sqrt{k}$ is used, $\\eta_k$ will be large for small $k$. It is known that SGD exhibits divergent behavior when the stepsize exceeds $2/L$, so SGD will initially diverge. The worst-case amount of divergence should be exponential in $L$. Once the $\\eta_k$ diminishes to a level below the divergent threshold, then the algorithm needs to recover from the initial exponential divergence, hence the rate. On the other hand, adaptive methods should not exhibit such divergent behavior (at least not to an exponential extent). Therefore, there is no initial exponential divergence, so there is no catch-up to play at the later stage of the algorithm. I think it would be worthwhile for the authors to discuss the view that the exponential constant corresponds to the amount of catch-up SGD needs to make.

Questions

Is the line of reasoning the authors lay out specific to non-convex SGD? It seems to me that a similar type of exponential dependence could be shown for the smooth-convex setup.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

.

Summary

The article under review presents results to show that untuned SGD may be less adapted than normalized versions of it when solving smooth non-convex problems. In order to prove this, the authors present several results, from upper to lower bounds on smooth non-convex problems to find a critical point, without the knowledge of the smoothness parameter. They show that while SGD may suffer from the non-adaptivity of the step-size, its normalized version get rid of this problem.

Strengths

- The paper's description of the problem it wants to tackle is good, and the questions addressed are well introduced. - While I find it a weakness too (see below), it is remarkable that the authors present both lower bounds and upper bounds on a lot of different settings. - The figures summarize well the main idea of the negative result on untuned SGD and the principle of the lower bound - The table helps to navigate in this hairy paper

Weaknesses

*Main comments* While the problem asked in the introduction on the difference between SGD and Adam (and its many variants) is an important problem where almost nothing is known, I find the answer of this article non-really convincing: - The main phenomenon pinpointed by the authors is the presence of the constant $e^{\eta^2 \ell^2}$ in the bound to find a critical point: this factor is due to the fact that, initially, the step size is too big compared to the local curvature of the function while after some time, the step-size being a decreasing function $\eta_t = \eta/\sqrt{t}$, the step-size becomes well-conditioned. While some similar phenomenon may take place for some learning problems, I am not sure that such an analysis is the crux of the problem for the comparison between Adam and SGD. Maybe some experiments on non-toyish problem might help convince the reader (or at least myself): do we really see this $e^{\eta^2 \ell^2}$ popping out and eventually really slows down the convergence? - The article claims to address, for practical purposes, and improve the theory from *bounded stochastic gradients* to *bounded variance* of the stochastic gradient: surely, theoretically it is a nice contribution, but it does not really serve to give an answer to the claimed question. Furthermore, even in this case, I think that the set-up is still not valid for the simplest least square case… so it does not seem to me as an incredible update. - Finally, as stated in the strengths paragraph, the article addresses a lot of different setups, with different algorithms, sometimes stochastic, sometimes deterministic and it is very difficult to understand the true contribution of the article if the authors do not pinpoint them. Sometimes the reader, or at least I, was completely lost in what was known, both it terms of technique and/or result. *Minor comments* - Theorem 1: $\Delta$ is not defined. I am surprised that there is no problem when $\eta$ is too big (no upper bound on $\eta$, and it does not diverge!), but this may be an artifact on the bounded variance stochastic gradient assumption. - Theorem 2: Good lower bound. I like it together with the illustration, as we understand well the phenomenon. However, why not proving it for SGD? This is only a technical limitation I guess. *Final precaution.* Overall, I have to say that I do not come from the community that analyses the general convergence of SGD for non-convex problems and its many normalized variants. Hence, it is hard to see what is the reel contribution of the authors.

Questions

Already said in the paragraph above

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Already said in the paragraph above

Response to Authors' Rebuttal

I acknowedge the response by the authors and have considered other reviewers' comments. I intend to keep my original evaluation.