Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods
Authors: Junchi YANG
Xiang Li
Ilyas Fatkhullin
Niao He
Venue: NeurIPS 2023 poster (2023)
Keywords: Nonconvex optimization
Stochastic Gradient Descent
Adaptive methods

Abstract: The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize $\eta_t = \eta/\sqrt{t}$ relies on well-tuned $\eta$ depending on  problem parameters such as Lipschitz smoothness constant, which is often unknown in practice. In this work, we prove that SGD with arbitrary $\eta > 0$, referred to as untuned SGD, still attains an order-optimal convergence rate $\widetilde{\mathcal{O}}(T^{-1/4})$ in terms of gradient norm for minimizing smooth objectives. Unfortunately, it comes at the expense of a catastrophic exponential dependence on the smoothness constant, which we show is unavoidable for this scheme even in the noiseless setting. We then examine three families of adaptive methods — Normalized SGD (NSGD), AMSGrad, and AdaGrad — unveiling their power in preventing such exponential dependency in  the absence of information about the smoothness parameter and boundedness of stochastic gradients. Our results provide  theoretical justification for the advantage of adaptive methods over untuned SGD in alleviating the issue with large gradients.

Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods
Junchi Yang"
Xiang Li Department of Computer Science ETH Zurich, Switzerland xiang. 1i0inf..... .einf.etiin ethz. ch
Department of Computer Science ETH Zurich, Switzerland junchi yangoinf .wwianneeehh...cm ethz.
Byas Fatkhullin
Niao He
Department of Computer Science ETH Zurich, Switzerland
Department of Computer Science ETH Zurich, Switzerland niao he@inf..e..... ettz. ch
ilyas. Alyas.aathull fwt.auatklllinn 1in@ai. ethz. ch
Abstract
The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize n/vtt relies well-tuned ry depending problem param- eters such as Lipschitz smoothness constant, which is often unknown in practice. In this work, we prove that SGD with arbitrary 1) > 0, referred to as untuned SGD, still attains an order-optimal convergence rate O (T in terms of gradient norm for minimizing smooth objectives. Unfortunately, comes at the expense of a catastrophic exponential dependence on the smoothness constant, which we show is unavoidable for this scheme even in the noiseless setting. We then examine three families of adaptive methods- Normalized SGD (NSGD), AMSGrad, and AdaGrad unveiling their power in preventing such exponential dependency in the absence of information about the smoothness parameter and boundedness of stochastic gradients. Our results provide theoretical justification for the advantage adaptive methods over untuned SGD in alleviating the issue with large gradients.
1 Introduction
In this work, study the stochastic optimization problem of the form: min ZERd
f(x) = Egpr [F(:; {)),
where P is an unknown probability distribution, and f Rd + E is an É-Lipschitz smooth function and can be non-convex. In the context of machine learning, & typically represent an individual training sample drawn from the data distribution P, and x denotes the weights the model.
Stochastic Gradient Descent (SGD), originating from the seminal work [58], performs the following update iteratively:
x++1 D, 7p F Et),
where 7/ > 0 presents a positive stepsize, and V Fx,; &x) is an unbiased stochastic gradient. SGD has shown remarkable empirical success many modern machine learning applications, e.g., [7, 62]. Its efficiency is usually attributed its cheap per iteration cost and the ability operate in an
37th Conference Neural Information Processing Systems (NeurIPS 2023).
"quul contribution.

---

Table 1: Complexities of finding c-stationary point for SGD, NSGD [53], NSGD-M [14), AMSGrad-norm (norm version of AMSGrad [57]). and AdaGrad-norm [61]. We only assume is f-smooth, and unbiased stochastic gradients have bounded variance o². Hlyper-paammen Y and 7)) are untuned. Here, Ô and 52 hide polynomial terms in problem parameters and hyper- parameters. The bounds are with respect to specific algorithms and stepsizes, and lower bounds for general first-order methods still hold [11, 3]. We list each algorithm's effective stepsize at iteration t directly below its name.
(e.g..
Upper bound; deferministic
Lower bound; deterministic
Upper bound; stochastic
Lower bound; stochastic
Algorithms
SGD (Eq. 1) VF+T
δ (4e) (iee) Thhm. 1,
e e-1)
2 ((86))
δ (Acc)R(n0P& [Thm. 1. 6]
c
D (8e))
[Thm. 2]
(Thm. 2]
NSGD (Alg. 3)
Ö 3) [14] & [Prop. 1]
Ω (c-2) [11]
N/A due lower bound
Nonconvergent [Thm. 3]
NSGD-M (Alg. 1)
Ô (c-2), 1/2
Ω (c-
Ô (c-"), 3/4 [14] & [Prop. 1]
12 (c [3]
lavil
[14] & [Prop. 1]
[11]
AMSGGad norm (Alg. 2)
3 (e-)) [Thm. 5.7]
2 ((--)) [Thm. 8]
N/A due to lower bound
E (2
Thm..
AdaGrad-norm (Alg. 5)
Ō (c-2)
2 ((- [1]]
δ (c [68] & |Prop. 3]
Ω (c [3]
Vi "
[68] & [Prop. 3]
online fashion, making it suitable for large-scale problems. However, empirical evidence also reveals undesirable behaviors of SGD, often linked to challenges in selecting appropriate stepsizes. In particular, number of works report the gradient explosion effect [6, 55, 24] during the initial phase of training, which may eventually lead to divergence or prohibitively slow convergence. The phenomenon is also observed in our experiments (see Figure 1(f) when the stepsize is poorly chosen. Unfortunately, this phenomenon has not been well understood from a theoretical point of view. The classical analysis of SGD in the smooth non-convex case [22], prescribes to select a non-increasing sequence of stepsizes {m7 1121 with 77, < f/C. In particular, the choice T = 1/(VVt), guarantees to find a point with IE [ fx))ll S after O (E-) stochastic gradient calls, which is also known to be unimprovable in the smooth non-convex setting unless additional assumptions are made [3, 17].
However, the bound on the smoothness parameter& é is usually not readily available for practitioners, and the limited computing power usually prevents them from exhaustive tuning to find the best stepsize. It is therefore important to provide theoretical understanding for SGD with an arbitrary stepsize (which we refer to untuned SGD) that is agnostic the problem parameter. The following intriguing question remains clusive in the stochastic optimization literature:
How does untuned SGD with a decaying stepsize dt =n/ n/vt perform when 1j is independent of the smoothness parameter? How can explain the undesirably large gradients encountered in training with SGD?
Recently, there has been a surge of interest in adaptive gradient methods such as Adam [35], RMSProp [28), AdaDelta [69], AMSGrad [57], AdaGrad [18], Normalized SGD [26], and many others. These methods automatically adjust their stepsizes based on past stochastic gradients, rather than using pre-defined iteration- based schedules. Empirically, they are observed to converge faster than SGD and mitigate the issue of gradient explosion across a range of problems, even without explicit knowledge of problem-specifie parameters [35, 46, 55). Figure provides a basic illustration of performance differences between SGD with 7)+ 1/vl stepsizes and adaptive schemes such AdaGrad and Normalized SGD with momentum (NSGD-M) [14]. Notably, when the initial stepsize is too large (relative to 1/6 value), SGD reaches the region with large gradients, while adaptive methods do not
Given access unbiased stochastic gradient oracle with bounded variance.

---

SK3D
SGDD (7-33
107
Adbiinnd
10
Adacimul (1 m
Acaldaad (6
XRGID-M (4
NBCD--3 (6-
NOGD-RR of
105
105
Inp
Agractenn cafa
Aondlant calls
Ospaiann oile
quadratic function (6-
(b) quadratic function
(c) quadratic function (f 10)
Hit Ml
(d) ResNet (1) =
(c) ResNet (17 = 5)
(l) ResNet (1) =
Figure 1: Comparison of SGD, AdaGrad, and NSGD-M on a quadratic function f(x) = ex2 /2 and a deep neural network. SGD employs a diminishing stepsize of 17/ 1/,V., while the stepsizes for AdaGrad and NSGD-M are specified in Propositions 2 and 3, respectively. For experiments on the quadratic function, we set second row, We train 50-layer ResNet [27] on the CIFAR- 10 dataset [36] using cross-entropy loss. Due to the large randomness observed for this setting, we run each combination of optimizer and stepsize 10 times and plot both the average and variance. Note that the scale of the y-axis varies for each sub-figure and SGD diverges to NaN when 1) = 7.
for all methods and test with 3 different values of l. For the figures in the
suffer from such effect. However, the theoretical benefits of adaptive methods over SGD remain unclear. large number of existing analyses of adaptive methods assume bounded gradients, or even stochastic gradients, precluding not only fair comparison with SGD whose convergence does not need bounded gradient but also the possibility to explain their benefit when facing gradient explosions. While recent developments show that AdaGrad-type methods [20, 68) can attain O (c-1) sample complexity under the same standard assumptions for SGD analysis, there is still lack good explanation for the substantial performance gap observed in practice despite SGD with well-tuned stepsizes theoretically achieving the lower complexity bound. We will address the following open question:
Can we justify the theoretical benefits of adaptive methods over untuned SGD for smooth non-convex problems without assuming bounded gradients?
Consequently, this work is grounded on the premise that gradients may be not bounded and that hyper-parameters are independent of the problem parameters. The main contributions are follows:
We show that untuned SGD with diminishing stepsizes T) = n/ finds an e-stationary point of (-smooth function within ( corresponds to the variance of the stochastic gradient. Although this classical algorithm converges and has the optimal dependence on e, we further show that the disastrous exponential term in 2 is unavoidable even when the algorithm has access to exact gradients. This explains its proneness to gradient explosion when the problem parameter is unknown. Previous analyses have failed to capture this exponential term, since they assume 7) is well-tuned be (1/E).
(4e)) 4) iterations for any 17 0. Here, o²
AMSGrad, which was proposed to fix the nonconvergence of Adam, not yet fully understood, with previous analyses depending on bounded stochastic gradients. We show that AMSGrad (norm version) is free from exponential constants in the deterministic setting without tuning, in stark contrast with SGD. Surprisingly, in the stochastic setting when the stochastic gradients are
3

---

unbounded, we show that AMSGrad may converge at an arbitrarily slow polynomial rate. To the best of our knowledge, these are the first results for AMSGrad without assuming bounded gradients.
To further illuminate the advantages of adaptive methods, we re-examine the results for Normalized Gradient Descent (NGD), Normalized SGD with momentum (NSGD-M) from [14] and AdaGrad- norm from [68], considering stepsize independent of the problem parameters similar to untuned SGD. They all achieve near-optimal complexities while shredding off the exponential factor. As a side result, we provide a strong non-convergence result of NSGD without momentum under any bounded stepsizes, which might be of independent interest.
Our findings contribute a fresh understanding of the performance gap between SGD and adaptive methods. Albeit with a near-optimal rate, untuned SGD is vulnerable to gradient explosion and slow convergence due large exponential constant in its complexity, which be circumvented by several adaptive methods. To the best of our knowledge, this substantial difference is unaddressed in the previous literature, because the majority of analyses for SGD and adaptive methods turn to either well-tuned stepsize based on problem parameters or the assumption of bounded gradients. Part of our results are summarized in Table 1, and full results for a broader range of stepsizes can be found in Table 2 in the appendix.
1.1 Related Work
SGD in nonconvex optimization. Stochastic approximation methods and SGD in particular have long history of development [58, 34, 8, 13, 51, 56]. When the objective is é-smooth and the gradient noise has bounded variance o², Ghadimi and Lan [22] and Bottou et al. [9] prove that if stepsize " n/V,, where = nj(E, a²) and 7 is the total iteration budget, then SGD can find an e-stationary point within ( iterations. Similar complexity (up to a logarithmic term) can also be achieved by decaying stepsizes / /t [22, 17, 65]. This result was later shown to be optimal for first-order methods under these assumptions [3]. Several works consider various relaxations of the stochastic oracle model with bounded variance, for instance, biased oracle [2] and relaxed growth condition [9]. However, these results also heavily rely sufficiently small 17. e.g., 17 1/C, and the convergence behavior in the large 7) regime is rarely discussed. Remarkably, Lei et al. [39] characterize the convergence of SGD under individual smoothness and unbiased function values. They consider Robbins- stepsize schemes, which includes 17/1" when a: > 1/2, and derive (G sample complexity including exponential dependence the smoothness parameter. Unlike [39], we focus on the standard assumptions and derive better dependency in smoothness constant when a > 1/2. Importantly, we further justify that the exponential constants are unavoidable with lower bound.
Adaptive methods. We focus on methods directly using gradients to adjust stepsize, rather than other strategies like backtracking line search [4]. Normalized Gradient Descent (NGD) was introduced by [53] for quasi-convex functions. Hazan et al. [26] apply NGD and NSGD with minibatch the class of locally-que quasi-convex functions. Later, Cutkosky and Mchta [14] and Zhao et al. [74] prove NSGD with momentum minibatch can find an e-stationary point in smooth nonconvex optimization with sample complexity O(e-A) AdaGrad was introduced in the online convex optimization [18, 48]. In nonconvex optimization, AdaGrad and its scalar version, AdaGrad-norm [61], achieve competitive convergence rates with SGD [66, 43, 31, 44]. RMSProp [28] and Adam [35] use the moving average of past gradients, but may suffer from divergence without hyper-paramedt tuning [57]. Recently, it was shown the finite-sum setting that they converge to a neighborhood, whose size shrinks to O by tuning hyper-parameters [60, 72J. However, most of the results on AdaGrad and Adam-type algorithms assume both Lipschitz and bounded gradients [75, 12, 16, 66, 76]. Very recently, Faw et al. [20] and Yang et al. [68] independently show that AdaGrad-norm converges without assuming bounded gradients and without the need for tuning. attaining a sample complexity of Ö(c-4).
SGD v.S. adaptive methods. Despite similar complexities, adaptive methods typically converge faster than SGD in practice [10, 47] and are widely used to prevent large gradients [55, 23). Various attempts have been made theoretically explain these differences. Some suggest that the advantage of adaptive algorithms is their ability to achieve order-optimal rates without knowledge of problem parameters such smoothness and noise variance [66, 40, 30]. Other studies investigate the faster

---

escape from saddle points by adaptive methods [41, 50, 67]. The importance of coordinate-wist normalization in Adam has also been highlighted [5, 37J. Furthermore, the influence of heavy-tail noise on the performance of adaptive methods is studied [71]. However, most previous works do not provide an explanation for the faster convergence of adaptive methods in terms of sample complexity. Notably, Zhang et al. [70] and Wang et al. [64] explain the benefits of gradient clipping and Adam under relaxed smoothness assumption, setting where SGD with non-adaptive stepsizes may not converge. In contrast, we analyze SGD and several adaptive methods under standard smoothness and noise assumptions, distinguishing it from the recent work of Wang et al. [64] that focuses one variant of Adam for finite-sum problems with individual relaxed smoothness and random shuffling.
Problem Setting
Throughout this work, we focus on minimizing an ê-smooth function f RR R. We have access stochastic gradient oracle that returns g(2; at any point x. and we make the following standard assumptions in nonconvex optimization.
Assumption 1 (smoothness). Function f(z) is E-smooth with é > O, that is, [V ff(2))) -V(z)) s L f||=1 z2ll for any 21 and 22 E IRd...
Assumption 2 (stochastic gradients). The stochastic gradient g(æ; {) is unbiased and has a bounded variance, that is, Eg [)( = fz)) and Eg [19((=;)) E) {f(>))] S o² for any x e Id..
We present the general scheme of SGD with initial point zg and a stepsize sequence {nd 1
F++1 It g(zz;
Some commonly used stepsizes include polynomially and geometrically decaying stepsize, constant stepsize, cosine stepsize, etc. When the stepsize depends on the instantaneous past gradients, i.e., {9(2; (x) Jase, we call it adaptive stepsize, namely Normalized SGD [26], AdaGrad [18), Adam [35], AMSGrad [57], etc. In some adaptive methods, momentum is also considered, replacing g( Et) in (1) with a moving average m4+1 of the past stochastic gradients (see Section 4 for more details). To set the stage for our analysis, we assume that [=(o) - minlzeR" [(x) S A, where represents the initial gap. Given that the function class of interest nonconvex, we aim find an e-stationary point with [(x)ll S
3 Convergence of Untuned SGD
In this section, we focus on SGD with the decaying stepsize:
TJ Vt+1
where 7) >> 0 is the initial stepsize. Most convergent analysis requires v) < 2/8 [22, 9] so that there is "sufficient decrease" in function value after each update, and if 1 is carefully chosen, it can achieve the npar-optimal complexity of D(Ec-ta)) [3]. Nevertheless, as the smoothness parameter usually unknown, providing guarantees with optimal 17 or assuming r to be
does not give enough insights into practical training with SGD. Hence we interested in its convergence behavior in both small and large initial stepsize regimes, i.e., 17 S 1/E and 1) > I/E.
Theorem 1. Under Assumptions and 2, if we run SGD with stepsize nt VITI
"
where 1) > 0,
T-1
< 2AA -T
when 1) S 1/e,
B[Vf(>>))
(W22A(4e))(xTT)>
when vj > 1/e,
where r 2 [ 1] and A (A+ 102 log
This theorem implies that when the initial stepsize > 1/e, SGD still converges with a sample complexity of (( + - (4e)2rr' Although the dependency in the target accuracy is
5

---

Segment 4:
Segrentt 1: ((x
(ar) (mennit ( A/ m)
(maet1/AS m
ursjeclory
+-
exponentially
depends on 1f
Seg.
Seg.
Seg.
Seg,
Seg.
Figure 2: Demonstration of the constructed function used to prove the lower bound. The definitions of the segments comprising the function can be found in Appendix B.2.
near-optimal, it includes a disastrous exponential term in 17262. This due to polynomially decaying stepsizes: in the first stage before [(npe]= 1] iterations, the function value and gradients may keep increasing in expectation until reaching exponential term in 172 which is in stark contrast with adaptive methods that we will see in Section 4; in the second stage after t 2 т, the stepsize is small enough to decrease the function value in expectation at rate of 1/vT up to a small term in
we arbitrarily select 17 = (1), untuned SGD may induce large gradients growing exponentially in in the first stage, as observed in Figure 1. Moreover, deriving the dependence in hyper-parantnn n is crucial for assessing the effort required in its tuning: SGD with an 1 that is times larger than the optimally tuned value can yield gradient norm that is exp(poly(()) times larger in the convergence guarantee.
To the best of our knowledge, there is limited study for non-asymptotic analysis of untuned SGD under the same assumptions. Moulines and Bach [49] study untuned SGD under individual smoothness and convexity assumptions, i.e., g(x; <) is Lipschitz continuous and Far; <) is convex almost surely. They showed convergence rate of (1/TT//3) for the last iterate and a rate arbitrarily close to (L1/T)/ for the averaged iterate. Later, Fontaine et al. [21] provide ((1/T1/2) convergence rate for untumed and 7). In the nonconvex setting, Khaled and Richtárik [33] showed, using SGD with constant stepsize 1) >> O, the squared rate of O (fan + (1 + (2)) (00/2"""///A A/rr))). When the total number of iterations predetermined, selecting a constant stepsize = no/TT results in the G.b ToVT which exhibits the same dependence on T as Theorem and also includes an exponential constant. However, our focus is on settings where T known in advance.
SGD in the convex setting, albeit without an explicit dependency
gradient min B|| (xx)) converges
rate Eorn n2+
S <O Love
VT
Remark 1. We consider stepsize in the order of 1/v/, because it is known for SGD to achieve the best dependency in e for nonconvex optimization [17] and easier to compare with adaptive stepsizes. We also present the convergence results for more general polynomially decaying stepsizes, ie.. nt = (t+1)= with O < a < 1, in Theorem 6 of the appendix. There exists a trade-off between convergence speed O(1/T"=*) and the exponential term in (nt) for E 1). Intuitively, larger a leads to shorter time in adapting to 1 1/6 stepsize but a slower convergence rate. We do not consider constant stepsize, i.e., a = O, because it is well known to diverge even in the deterministic setting if the stepsize is agnostic to the problem parameter [52, 1J.
The question arises to whether the exponential term is necessary. In the following, provide lower bound for SGD under this choice of stepsize.
Theorem 2. Fixing T 2 1.n > 0, > 0 and A > 0 that me 2 5, there exists a E-sooohh function
f TR. + R and an initial point To with {(x) - f < A such that if we run Gradient Descent with
" stepsize 17c VETT then for < to = 1/ 16
2PA (8e)12 and V [ >
8A
(8e)
1322-4
V[(x))
3v7
3n

---

ifT >> to. for to <t Stst.
[V((a)) 4
1 V min ( (2n) (21))112(p1/// where Å (21)
(8e) /116-2 3rd
4
This theorem suggests that Gradient Descent (GD) with decaying stepsize 11/ VL needs at least ((0=4 / 4) iterations to find an e-stationary point in the large initial stepsize regime. Therefore, it validates that an exponential term in 2f2 multiplied by e is not avoidable even in the deterministic setting. It is crucial to note that our result is limited to untuned (S)GD with this particular stepsize scheme.
is worth pointing out that the existing lower bounds for first-order methods [3] and SGD [17] do not contain any exponential terms. On the other hand, Vaswani et al. [63] established lower bound in the strongly convex setting for GD with exponentially decreasing stepsizes (1/Z))/''n, where T denotes the total number of iterations and 17 > 0. With a quadratic function, they showed that if 1) > 3/C, the distance to the optimal solution ||a|| - x=|| exhibits exponential growth in t during the initial / log 7') iterations. However, this exponential growth is rapidly mitigated afterward, resulting in no exponential term at the final iterate T. This behavior starkly contrasts with our nonconvex setting.
We illustrate our hard instance for Theorem 2 in Figure 2, which is one-dimensional. The algorithm starts from valley of the function f(x) = Êx? /2, i.e., Segment 1. Because of the large initial stepsize and steep slope, in the first to iterations, Gradient Descent increases the function value as large as Á = .2 (8e)) /26 A). Then the iterate + jumps to the top of a very flat valley, i.e.,
Segment 4, so that Gradient Descent decreases the gradient as slowly ((T"11/4)
Why do not we assume gradients to be bounded? The assumption on bounded gradients not satisfied even for the simple function f(z) = Lx²/2 /2. When training neural networks, gradient explosion is often observed [55, 59], which directly suggests that this assumption is not satisfied or only satisfied with numerically large constant. Proposition 4 in the appendix, we also provide simple proof for the convergence under the additional assumption of bounded gradient, i.e., [=)]l S G for all v, attaining sample complexity of of without any information about problem parameters. However, compared with Theorem and 2, constant G hides the exponential term. In Figure 1, we observe that the gradient bound along the trajectory of non-adaptive stepsize can be much larger than that of adaptive stepsize even if starting from the same initial point, assuming bounded gradient will obscure the difference between them.
Power of Adaptive Methods
In this section, focus the convergence behaviors of adaptive methods, which adjust their stepsizes based on the observed gradients. In particular, when arriving at point with large gradient, adaptive methods automatically decrease their stepsizes to counter the effect of possible gradient increase; to list a few, Normalized SGD [26], AdaGrad [18), Adam [35]. Since the analysis for adaptive methods is usually on a case-by-case hasis, we will examine three examples - Normalized SGD, AMSGrad-norm and AdaGrad-norm - to establish a universal observation that they avoid exponential dependency in l without tuning. Although many existing analyses rely on bounded gradients (and function values) or information on problem parameters, we will abandon such as- sumptions noted in the previous section. We focus the norm instead of the coordinate-wiss version of adaptive methods, which means each coordinate adopts the same stepsize, because the norm version is usually dimension-indeeendee theory and practice [73, 45, 43, 38, 54, 32].
in the complexity, and is also widely used in both
4.1 Family of Normalized SGD
Normalized (Stochastic) Gradient Descent [53, 26], referred to NGD and NSGD, is one of the simplest adaptive methods. It takes the stepsize in (1) to be normalized by the norm of the current (stochastic) gradient:
7

---

TJt [g((
where (2: is a sequence of positive learning rate. Cutkosky and Mehta [14] and Zhao al. [74] show that NSGD with "/2 = 7/vTT can find an O(1/VT + o point. order to compare fairly with untuned SGD with decaying stepsize, we present modification with decaying 7t = >==//v++1 in NSGD.
Proposition 1. Under Assumption I and 2, we NSGD with 7/1 VFTI then for any 7 O.
T-1
B (())) s - + By (o)(())) T T- + 24a.
T
NGD. In the deterministic setting, by Proposition 1, NGD converges to an e-stationary point with a complexity of [( + -= for any 7 > 0, which importantly does not include any exponential term. Thus, even if the initial stepsize not small enough, it does not result in catastrophic gradient explosion.
NSGD. In the stochastic setting, Proposition implies that NSGD can find an e-stationary point only when the noise variance is small enough, i.e., σ < O(e). This is not the consequence of loose analysis. Hazan et al. [26] show that NSGD with constant = 7 does not converge when the mini-batch size is smaller than ( for a non-smooth convex function. Here we provide a non- convergence result in the gradient norm with a smooth objective for all uniformly bounded stepsizes. The intuition behind this illustrated in Figure 3 in the appendix, where Eg g(z; (o)::))/lll (ag E) can easily vanish or be in the opposite direction of V (x:) under certain noises.
Theorem 3. Fixing l > 0, > 0, > O, > 0 and stepsize sequence { with " "fmax that e² < min(o?, 2FA, 2A(a (a c)/Tmax], h. there exists an f-smooth convex function f. initial point To with (=0) - min, f (xx S A and zero-mean noises with o² variance such that the output from
NSGD satisfies E ( 2 c for all t.
This theorem implies that, given fixed function class (l, A, σ) and any sequence {rrhe uniformly upper bounded by Tmax. NSGD cannot converge to an arbitrarily small Specifically, the expected gradient norm will always stay larger than min(o, /21A, ( + VA² + 2Armax Most {7c) used in practice is upper bounded, e.g., constant or decreasing sequences. The condition 2 2/A is necessary by noting that f < (z)) min, f(x)] s 26A. Considering Tt = I/VE+I, when A 2 a and V 2 a, it matches with Proposition 1, where NSGD can only converge a ((or) -stationary point. Since Sign-SGD and NSGD coincide for miedimensional objectives, non-convergent example also applies to Sign-SGD. This sheds light on why increasing batch size improves Normalized and Sign-SGD [74, 37]. However, these methods generally different in higher dimensions, as Karimireddy et al. [29] show that sign-SGD may not converge even with full batch.
NSGD with momentum. While NSGD may not always converge, Cutkosky and Mehta [14] introduced NSGD with momentum (NSGD-M) presented Algorithm with constant n = y. We provide the following modification with diminishing Yt that eliminates the need specify the total number of runs beforehand.
Proposition 2. Under Assumptions I and 2, if then any y 0,
we we run NSGD-M with a, = Ve4z
v2 and 71 [(4])37
Σ
B
(7) log(T) r
T
where C. > O is a numerical constant.
It implies that NSGD-M attains complexity of ((17-44740) for any 7 > 0. Compared with Theorem and 2, NSGD-M not only achieves netrmoptimal dependency in the target accuracy but is agnostic to smoothness constant.
also shreds the exponential term when the

---

Algorithm 1 NSGD-M
Algorithm AMSGrad-norm
1: Input: initial point Tp, stepsize sequence
1: Input: initial point zg. momentum parameters
0 S B1 < and B2 I 1, stepsize sequence
{ momentum sequence { and ini-
{n}} and initial momentum mo and vo > 0.
tial momentum 9o-
00 to
3: for = 0.1.2... do sample &
2: for = 0, do
3: 1+++1 2t
Tt lioe 5h
5: m = =mm + (1- B1 (g( (ettiit)) Et)
Vi 5222 + +11 (1- (lgrl Ee)l
4: sample Er+1
"t -max 62 (
5: 91+1 = (1 - at)gt + aig(244136441)
8:
T++1 = It
74 m++1
V
6: end for
9: end for
4.2 AMSGrad-norm
AMSGrad was introduced by Reddi al. [57] fix the possible non-convergence issue of Adam. No- tably, current analyses of AMSGrad in the stochastic setting show a convergence rate of (1/TT//4) but they rely on the assumption of bounded stochastic gradients [12, 75], which is much stronger than assumptions used for SGD analysis. Here, we examine the simpler norm version of AMSGrad, presented in Algorithm 2. We prove that without assuming bounded stochastic gradients, AMSGrad- norm with default " = <//vt= I may converge at an arbitrarily slow polynomial rate. In fact, this holds even if the true gradients are bounded. We believe this result is of independent interest.
Theorem For any > 0, A > 0, a > 0 and > 1, there exists a l-smooth function f :R + To with (z0) inf, f()) S and noise distribution P with variance upper bounded by o², such that if we run AMSGrad-nome with 0 $ B1 S 1, < B2 and % _y, we have with probubility b. it holds that
VCFT
A
mii (E...I....TTI....
7V 2
4
16 max
1/l,
(T-
(e((t-1)) (1-1)--B
for any <<< 1, where I(-) denotes the Gamma function.
The intuition behind this theroem is that since AMSGrad utilizes the maximum norm of past stochastic gradients with momentum in the denominator of stepsizes, some noise distributions enable this maximum norm to increase polynomially, making the stepsizes too small. However, we can still explore its benefit in the deterministic setting. Whether it converges without assuming bounded gradients, to the best of our knowledge, is unknown. Here, for simplicity, we consider AMSGrad-nnom without momentum, i.c., B1 = 32 = O.
Theorem 5. Under Assumption 1, if we run AMSGrad-norm with Yi VIT vo > 0 and B1 = 82 0 in the deterministic setting, then for any and 0 < 1,
T 2A max 22
when vo < 78,
T
27 A) max(fe, 22E(M + A)}, when vn 2 7 T 222220 T
where M = E?? (1 [1+ log
The theorem implies that AMSGrad-norm achieves a complexity of ((+""~+++(0+++77>""+++++ with the default 7 1/2=1/2) [57, 12, 25). Compared with untuned Gradient Descent, it gets rid of the exponential dependency. In the proof, we show that before the first iteration 7 when stepsize nh

---

reduces to 1/C, the accumulated gradient norms Σi= VV (rz)ll are upper bounded polynomially. which is in striking contrast with SGD in Theorem 2. We further provide theoretical guarantees the appendix. We also derive matching lower bounds Theorem for any < a < 1, and justify that AMSGrad may fail to converge with constant 7/ = 7 (i.e., a 0) if the problem parameter is unknown.
for more general schemes (t+1)a with < a < in Theorem
Y
4.3 AdaGrad-norm
AdaGrad chooses its stepsize be inversely proportional the element-wise accumulated past gradients [18, 48]. Its norm-version, AdaGrad-norm [61, 66], picks stepsize in (1) to be
V o/ + Ei=o (e)
where > 0. Very recently, AdaGrad is proven to converge in nonconvex optimization without the assumption on bounded gradients or tuning 7) [20, 68]. Although the result in [68] are presented for minimax optimization problems, a similar result follows immediately for minimization problems. We present the following result for the completeness of the paper and to further illustrate the benefits of adaptive methods over SGD.
Proposition 3. Under Assumptions I and 2, if we run AdaGrad-norm, then for any v > and vo
1
2A
Vo
2v
E E||ff(=!l S
T
VT
VT
T
t=
where A = -
The above result implies complexity of Ô ((7-2 2 o² + 1 (c-2
Notably, r can be chosen to be 1/vê, it achieves the optimal complexity in both and e up to logarithmic terms like well-tuned SGD [3]. Even if i) is agnostic to f, AdaGrad-nnomm does not suffer from the exponential term present in untuned SGD. One of the intuitions in the deterministic setting, similar to the AMSGrad-norm, is that the accumulated squared gradient norm before the first iteration with stepsize smaller than 1/6 will be upper bounded by a polynomial term (see Theorem 3.2 in [42]). Another benefit of AdaGrad over other methods is to achieve optimal convergence rates simultancously in deterministic and stochastic settings with the same as "noise adaptivity", which is out of the scope of this paper.
This is sometimes referred to
Conclusion and Future Directions
We convey a crucial message: SGD with polynomially decaying stepsize can converge at the order-optimal rate, while remaining agnostic the problem-specific parameter notion that may challenge common belief. However, it is subject to exponential term, which can be avoided by utilizing appropriate adaptive scheme. We further reveal the similarity and differences between several adaptive schemes; a detailed exposition of these results can be found in Appendix A. This work opens up several avenues for future research. Firstly, would be valuable to investigate whether the benefits of adaptive methods extend to high-probabilityy convergence guarantees and apply to a broader range of adaptive optimizers. Secondly, removing the assumption of bounded gradients is crucial for comprehensive analysis of adaptive algorithms, as it can reveal the true dependence on the smoothness parameter l and highlight their advantage over SGD. Lastly, examining the impact of adaptive algorithms optimizing non-smooth nonconvex objectives, which are prevalent in training modern machine learning models, presents an interesting research direction.
Acknowledgement
The work is supported by ETH research grant and Swiss National Science Foundation (SNSF) Project Funding No. 200021-207343. Ilyas Fatkhullin is partly funded by ETH AI Center.
10

---

References
[1] Kwangjun Ahn, Jingzhao Zhang, and Suvrit Sra. Understanding the unstable convergence of gradient descent. arXiv preprini arXiv:2204.01050 2022. (Cited on page 6.)
[2] Ahmad Ajalloeian and Sebastian U. Stich. On the convergence of sgd with biased gradients. arXiv preprini arXiv:2008.0005), 2021. (Cited on page 4.)
[3] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming. pages 1-50, 2022. (Cited on pages 2, 4, 5, 7, 10, and 16.)
[4] Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966. (Cited on page 4.)
[5] Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. In International Conference on Machine Learning, pages 404-413. PMLR, 2018. (Cited on page 5.)
[6] Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157-166, 1994. (Cited on page 2.)
[7] Yoshua Bengio. Learning deep architectures for AI. Foundations and Trends in Machine Learning, 2(1):1-127, 2009. (Cited page 1.)
[8] Julius R Blum. Multidimensional stochastic approximation methods. The Annals of Mathemati- cal Statistics, pages 737-744, 1954. (Cited on page 4.)
[9] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31) 311, 2018. (Cited pages 4 and 5.)
[10] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020. (Cited page 4.)
[11] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1-2):71-120 2020. (Cited on pages and 16.)
[12] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations. International Conference on Learning Representations, ICLR, 2019. (Cited on pages 4 and 9.)
[13] Kai Lai Chung. On stochastic approximation method. The Annals of Mathematical Statistics, pages 463-483, 1954. (Cited on page 4.)
[14] Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International conference machine learning, pages 2260-2268. PMLR, 2020. (Cited pages 2, 4, 8, 16, 23, and 24.)
[15] Felipe RS De Gusmao, Edwin MM Ortega, and Gauss M Cordeiro. The generalized inverse weibull distribution. Statistical Papers, 52:591-619, 201 (Cited page 30.)
[16] Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint arXiv:2003.02332 2020. (Cited on page 4.)
[17] Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In International Conference on Machine Learning, pages
PMLR,
2020. (Cited pages 2, 4, 6, 7, 19, 21, and 28.)

---

[18] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7). 2011. (Cited on pages 2, 4, 5, 7, and 10.)
[19] Iyys Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for fsher-non-degenende policies. arXiv preprint arXiv:2302.01734 2023. (Cited on page 25.)
[20] Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Proceedings Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 313-355. PMLR. Jul 2022. (Cited on pages 3, 4, and 10.)
[21] Xavier Fontaine, Valentin De Bortoli, and Alain Durmus. Convergence rates and approximation results for sgd and its continuous counterpart. In Conference on Learning Theory, pages 1965-2058 PMLR, 2021. (Cited on page 6.)
[22] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2344);334--2368, 2013. (Cited on pages 2, 4, and 5.)
[23] Boris Ginsburg, Patrice Castonguay, Oleksii Hrinchuk, Oleksii Kuchaiev, Vitaly Lavrukhin, Ryan Leary. Jason Li, Huyen Nguyen, Yang Zhang, and Jonathan M Cohen. Stochastic gradient methods with layer-wise adaptive moments for training of deep networks. arXiv preprint 128 2019. (Cited page 4.)
[24] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. The MIT Press, 2016.
(Cited on page 2.)
[25] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprint vtXiv:21/2.034555 2021. (Cited on page 9.)
[26] Elad Hazan, Kfir Levy, and Shai Shalev- Shwartz. Beyond convexity: Stochastic quasi-convex optimization. Advances in neural information processing systems, 28, 2015. (Cited on pages 2, 4, 5, 7, and 8.)
[27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016. (Cited page 3.)
[28] Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8):2, 2012. (Cited on pages and 4.)
[29] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR. 2019. (Cited on page 8.)
[30] Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. NeurlPS, 32, 2019. (Cited on page44 4.)
[31] Ali Kavis, Kfir Levy, and Volkan Cevher. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. In ICLR, 2022. (Cited on page 4.)
[32] Ali Kavis, Stratis Skoulakis, Kimon Antonakopoulos, Leello Tadesse Dadi, and Volkan Cevher. Adaptive stochastic variance reduction for non-convex finite-sum minimization. arXiv preprint arXiv:221.001851 2022. (Cited page 7.)
12

---

[33] Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.03329, 2020. (Cited on page 6.)
[34] Kiefer and J. Wolfowitz. Stochastic Estimation of the Maximum of Regression Function.
The Annals of Mathematical Statistics, 23(3):462 466, 1952. (Cited on page 4.)
[35] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015. (Cited on pages 2, 4, 5, and 7.)
[36] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. (Cited on page 3.)
[37] Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidr. Heavy-tailed noise does not explain the gap between SGD and Adam, but sign descent might. In International Conference on Learning Representations, 2023. (Cited on pages 5 and 8.)
[38] Joffrey L Leevy and Taghi M Khoshgoftaar. survey and analysis of intrusion detection models based on cse-cic-ids2018 8 big data. Journal of Big Data, 7(1):1-19, 2020. (Cited on page 7.)
[39] Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE transactions on neural networks and learning systems, 31(10):4394 4400, 2019. (Cited on page 4.)
[40] Kfir Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive sgd with recursive momentum for nonconvex optimization. NeurIPS, 34:20571-20582, 2021. (Cited on page 4.)
[41] Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint 16110881 2016. (Cited on page 5.)
[42] Xian Li. Adaptive methods for parameter-agnoste nonconvex minimax optimization. Master's thesis, ETH Zurich, Department of Computer Science, 2022. (Cited on page 10.)
[43] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd international conference on artificial intelligence and statistics, pages 983-992. PMLR, 2019. (Cited on pages 4 and 7.)
[44] Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint 2:Xi::20077.1224 2020. (Cited page 4.)
[45] Selena Ling, Nicholas Sharp, and Alec Jacobson. Vectoradam for rotation equivariant geometry optimization. arXiv preprini arXiv:2205. 13599, 2022. (Cited on page 7.)
[46] Liyuan Liu, Haoming Jiang. Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning and beyond. In International Conference Learning Representations, 2020. (Cited page 2.)
[47] Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han. Understanding the difficulty of training transformers. arXiv preprint arXivv2004.08229, 2020. (Cited on page 4.)
[48] H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv:/002.4908. 2010. (Cited on pages and 10.)
[49] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances in neural information processing systems, 24, 2011. (Cited on page 6.)
[50] Ryan Murray, Brian Swenson, and Soummya Kar. Revisiting normalized gradient descent: Fast evasion of saddle points. IEEE Transactions Automatic Control, 64(11):4818 4824,, 2019. (Cited page 5.)
13

---

[51] A. S. Nemirovski and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. John Wiley UK/USA, 1983. (Cited on page 4.)
[52] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science Business Media, 2003. (Cited on page 6.)
[53] Yurii E Nesterov. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29(3):519-555 1311,,,,,,,11 1984. (Cited on pages 2, 4, and 7.)
[54] Werner Palfinger. Continuous remeshing for inverse rendering. Computer Animation and Virtual Worlds, 1101) 2022. (Cited on page 7.)
[55] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310-13 1310--11...11 PMLR, 2013. (Cited on pages 2, 4, and 7.)
[56] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimizatiio, 30(4):838-855 1992. (Cited page 4.)
[57] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In ICLR, 2018. (Cited on pages 2, 4, 5, and 9.)
[58] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951. (Cited on pages and 4.)
[59] Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural networks, 61: 85-117, 2015. (Cited on page 7.)
[60] Naichen Shi and Dawei Li. Rmsprop converges with proper hyperparameter. In International conference on learning representation, 2021. (Cited on page 4.)
[61] Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv: 2010. (Cited on pages 2, 4, and 10.)
[62] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. (Cited on page 1.)
[63] Sharan Vaswani, Benjamin Dubois-Taine and Reza Babanezhad. Towards ndise-ad problem-adaptive (accelerated) stochastic gradient descent. In International Conference on Machine Learning, pages 22015-22059. PMLR, 2022. (Cited on page 7.)
[64] Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tic-Yat Liu, and Wei Chen. Provable adaptivity in adam. arXiv preprint arXiv:2208. 09900, 2022. (Cited on page 5.)
[65] Xiaoyu Wang, Sindri Magnússon, and Mikael Johansson. On the convergence of step decay step-size for stochastic optimization. Advances in Neural Information Processing Systems, 34: 14226-14238, 2021. (Cited on page 4.)
[66] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Journal of Machine Learning Research, 21(1)9904--907, 2020. (Cited pages 4 and 10.)
[67] Zeke Xie, Xinrui Wang, Huishuai Zhang, Issei Sato, and Masashi Sugiyama. Adaptive inertia: Disentangling the effects of adaptive learning rate and momentum. In International Conference on Machine Learning, pages
PMLR, 2022. (Cited on page 5.)
[68] Junchi Yang, Xiang Li, and Niao He. Nest your adaptive algorithm for parameter-agnostic nonconvex minimax optimization. arXiv preprint arXiv:2206.0077. 2022. (Cited on pages 2, 3, 4, 10, 16, and 32.)
14

---

[69] D. Matthew Zeiler. Adadelta: An adaptive learning rate method. arXiv:1212.570vv1, 2012. (Cited on page 2.)
arXiv preprint
[70] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019. (Cited page 5.)
[71] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15393 2020. (Cited page 5.)
[72] Yushun Zhang, Congliang Chen, Naichen Shi, Ruoyu Sun, and Zhi-Quan Luo. Adam can converge without any modification on update rules. Advances in neural information processing systems, 2022. (Cited on page 4.)
[73] Zijun Zhang. Improved adam optimizer for deep neural networks. In 2018 IEEE/ACM 26th international symposium on quality of service (IWQoS), pages 1-2. leee, 2018. (Cited on page 7.)
[74] Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64(3):1-13, 2021. (Cited on pages 4 and 8.)
[75] Dongruo Zhou, Jinghui Chen, Yuan Cao. Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 1808,0061, 2018. (Cited on pages 4 and 9.)
[76] Fangyu Zou, Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11127-11 135, 2019. (Cited page 4.)
15

---

A Results Summary
Table 2: Comparisons of complexities to find an e-stationary point, i.e., [
S between SGD, NSGD, NSGD-M, AMSGrad-norm and AdaGrad-norm. We only assume f-smooth, and unbiased stochastic gradients have bounded variance o². Hyper-parameters (e.g., 7 and 1)) are arbitrary and untuned. In this table, Ô and Z hide polynomial terms in problem parameters and hypee-parameters, and ① also hides all logarithmic terms. We use fe denote the effective stepsize at iteration t.
Upper bound; deterministic
Lower bound; deterministic
Upper bound; stochastic
Lower bound; stochastic
Algorithms
SGD (Fq. 1) 1/:
17 (46"m) TTmejAn Jom
n ((88))
(46
a ((8))
teray"
a E (0.1) [hhm. 1,6
1/2 [Thm.
a E (0. 1) [Thm. 1.6
1/2 [Thm.
NSGD (Alg. 1/
"(-"), = VAFT
2 (c7)) [1]]
N/A due to lower bound
Nonconvergent
7h [|
[14] & [Prop. 1]
V bounded (7x) [Thm. 3]
NSGD-M (Alg. I)
(c-").a a 1/2 [14] [Prop. 1]
(c
Ö (c")). [14] & [Prop.
3/4
2 (e [3]
[11]
AMSGrad-nomn (Alg.
( ((=))-=))
) (0.
Q 2/0-w) E (0,
NIA due to lower bound
a (( 20-20) ). 1/2
Nonconvergent, a = 0 (Thm. 8]
(+1)*
Thm.. 5.
Ay E (0.5, 1) [Thm. 4]
AduGrad-norm (Alg. 5)
Ō (c-)) [68] [Prop. 3]
9 (c-))
Ô (c-") [68] & [Prop.
((==") [3]
Vi 100
[1]]
In this work, we study stochastic gradient methods for minimizing smooth functions in the parameter- agnostic regime. Firstly, we show SGD with polynomially decaying stepsize 1/Vl is able to converge with the order-optimal rate, with and without bounded gradients (Proposition 4 and Theorem 1). Its limitation lies in an unavoidable exponential term in 8² when we do not assume bounded gra- dients (Theorem 2). We demonstrate that several existing adaptive methods do not suffer from the exponential dependency, such NGD, AdaGrad, AMSGrad (Proposition and Theorem 5), and NSGD-M, AdaGrad in the stochastic setting (Proposition 2 and Proposition 3). However, it does not mean adaptive methods are always better than SGD, We provide a non-convergence result for NSGD (Theorem 3) and a slow convergence result for AMSGrad-nomn (Thoerem 4) in the stochastic case. We believe our results shed light on explaining commonly observed large gradients during training and provide a better theoretical understanding of the convergence behaviors of adaptive methods in the regime with unbounded stochastic gradients.
in the deterministic setting
B Proofs for SGD in Section 3
B.1 Upper Bounds for SGD
We provide an extended theorem of Theorem and include more general decaying stepsizes 7/(t + 1)" with 0 < a < 1.
Theorem 6. Under Assumptions I and 2, we run SGD with stepsize = =n/(t= + 1)2 where 1) > 0 and 1/2 < a < 1, then with 1) $ 1/e,
2
to²n
A +
(1 +logg 1)
when = 1/2,
1/
2
20
E T
[+=))
A
when
1/T aa
2 2
2 21-2a
A
l02n2
when < < 1/2;
1/T'a
T1 F1-2a
(1 2a)
16

---

with > 1/e,
v2 (1e) NTTT bn (1+277))
(A+
lo²n²
(1 (1+ (1+ 1og
2
when = 1/2,
2 (4
1 -1-0
a )
[
E
1 1+ En
A
V (x+))?
17 (2 a T
2 21 21-2aa
when 1/2x<00
2 (4) (2 ) T
1+ - )
A 102172
1 1 En)
T1
2(1 - 2a.)
when 0 < a < 1/2,
where ((ne)2/a-11
Proof. By E-smoothness of f(-).
f(1141) S f (Vf(2))))) 21) 21)+
T zel1
= - (V(a)))nm + tnp
2 (1)(1
Taking expectation,
+ by
V f (x,)11 + Eyp 0²
Bf(x++1) (1f(())) V
tz
t1j 0²
{R.f(x+)= 1/1
E [x+)))
(2)
2
2
We note that 17-
2xp 2
2 I when n) S f.i.e, i.e., 2 -1. Define T = [(n]]] 1/2 - 17. Therefore,
for all t < T.
Ent 0².
BB((n) +
(3)
2
2
For all t 2 we have
The E fx;))1 + Ex 0².
(4)
Summing from = 7 to T' we have
T-1
T-1 enf o²
Σ
([ -)(())))(()))))))))))))))()))))) - ((T) + Σ
(5)
2
1=
Now we want to bound E.(xx)) - ((T) S {ES(xr) - f where f 2 mingerd ((x). From (3),
Ef(re+1) ft < Ef(xx) fr + En? E V (x;, ) 2 +
En? 0²
2
2
Ex
< (1+ & E. |r]
02
2
where in the second inequality we use |V < (2] When r =
S A;
when T 2 1, recursing the inequality above, for j T,
en 0²
En
Ef(x,) - A
II
Pxp
+
Σ II
1 2
0z
2
K=
At=k1
17

---

+ Cn
o²
2
(=0
1=
Exp
1+ Pnk
A +
Σ
0²
(6)
2
1=0
1=
Also, with [V - 211 - ff 1,
Σ 2
-;ルパ!!>) S Σ meB ((()))-))
Σ
1 +
II
Pvpi )
(A+
E
0²)
The
2
-
where in the second inequality we use (6). Combining with (5) and (6), if T 21
T
The
S
II 1
eni
A Σ 2
02
+
Σ
0²
2
+ l
Σ T/
x-1
T-1
1 + CnR
A
+
1
en
0²
2
1=0
1=0
1=0
We note that
T-1
Enz
I1:o0 (L9z + (t + 1)
(Li2 + +2a)
II (1+
II
1 1
x
(++ 1)20
(T!)2a
(rl)20
t=0
t=0
126²
(2l77))
(r!)2a
V2TT (E) 7 exp ( (127+1) )
1
22 12
(217)) (4c22)² 7
(2TT)a
720
where in the third incquality we use Stirling's approximation. Therefore,
T-1 Σ
T 1 en
The "EI - (2T7)a (4020)²
1 1
Σ 7
Σ
0²)
+
2 0=0
0=0 2
Plugging in = (1(( + 1)0, when a = 1/2,
T Σ [(Vs(,))1*= < T/T7" (4e) [1 + En (1 + +2/7]]
2T
(A+
lo2.1
2 (1 + log log 7)
when 1/2<a<L 1
T-1
Σ B|Vs(()))1 <
TT 1(2x)) (Ac2ar
1+ En (1+7 -|ا
1 a ){
A
l0217
2 - 200)
when 0 <<<<<< < 1/2,
T-1 Σ [z;))1 <
2Ta
(1 (1+ a )]
(A+ 10²12T11 20
1 1+ en
((x77)
2(1-2a)
18

---

If T = 0, from (5),
T-1
Th
S A +
T
Σ
En
0²²
2
2
t=0
Plugging in ne, when = 1/2,
T-1
2VT ( A
lo217
(1 + log (1+lgTT)
2
when 1/2<a<1,
2
E
[
A
2 21 21-2a)
when 0 <a a <//2.
[ < 2T
1021271-20
A
17
2(1 20x)
Remark 2. When we run SGD with stepsize 1/2 = n/((t + 1)0, where 1/2 < a < 1, Theorem
implies a complexity of O (4e2a) (ne) ETT in the large initial stepsize regime
(ar)//a
n > L/E. Compared with the case a 1/2, when is larger, the convergence rate in T is slower, but it also comes with smaller exponent, i.e., (nE) This is because a 1/2 leads to the best convergence rate in T [17], while the faster decaying stepsize 1/2 will reach the desirable stepsize 1/l earlier so that it accumulates less gradient norms before For O < aa < 1/2, however, it comes with both larger exponent and a slower convergence rate.
Proposition (with bounded gradient). Under Assumption 1, 2 and additionally assuming that the gradient norm is upper bounded by G, i.e., [[V s G for all Rd, if we run SGD with stepsize Tr. /// + I with 1) > O, then
E
T Σ
V (2))
S
A "
bn (G2 02)
log )
VT
2
Proof. By the smoothness of f-), we have
Enf
f(1111) S f(z) - (VV((E;))), v((z))
[VF((+))))
2
Taking expectation and summing from L = 0 to -
E
n [V
- -f(x))-((11) f((r))
Σ
E [VF
1=1
T-1
SA+ + Σ
|VF
T Σ r
A +
(IV[(>))) 2 + E ()) (xx)))
2 1=
T
< A +
Σ
The (G +
2
t=0
19

---

Let
m/ n/vt+11
VT
"
E
7-
Σ
V
(x)))
S
vt+I
"
<A+
l +
C(G²
2
oz2
T-1
Σ
t t+1
rp
by
(G2
0
A +
log T.
2
B.2
Lower Bound for SGD
Proof for Theorem 2
We construct the hard instance with segments of quadratic functions. The function is symmetric about 0, and we will define it on x S 0 as below. We illustrate it in Figure 2.
Proof.
Segment 1. We define [(x) Lx² We pick such that ((xo) f" A, i.e., so
/ 24
We
define to to be the first iteration that 1/to-
4 2 i.e., to
1)² 1.. With the update rule
ViaT
It-1
ne VE+I Ft
ne vi+I
24, we have for t S to
nl
1)
22
|ay 2
II
10oo2
II
2k xxu
Vk
617222/2)
(n222/12)
1
|0o|
v 22t (xtttt/e)ee///1z 120 1
3v8 (zol
(t)!
where in the inequality use Stirling's approximation, and in the last inequality use t v 2/ 12/211 We note that
ge
- 1)
20
with S toz in the second inequality
VI
|r >
(8e) (8e) |ool
4
(8e) (8e) )2 0//22/11-11 2000?
3rd
Without loss of generality, we assume Ftg >> O. Segment is define the domain {xr |or| Ntg).
Segment 2. This segment is the mirror of Segment 1. On domain for Ito S x S 2x,, ). we define f(z) = (x x 2x,,) 12 + Ex?
Segment 3. We note that
n/
Fto+1 Tto
Thoo
Exto
Tto S -3E to +
where the inequality is from the definition of lo. and
tx
2
(8e)
(8e) (8 116-2211221 2
2
3n
3rd
We construct quadratic function such that: it passes (-2rt, lx with gradient O; the gradient at
V
I T1o+1 is
This quadratic function is uniquely defined to be
3/xxx(1// 11 m
(x + 2x1,,)
[(x)
+ Lx
4(-2It, - R1o+1) max(1/ 1/E, ET-1-1 mc}
20

---

It can be verified that this function is &-smooth: as Plo+1 -32
2 1e
VĀ
S VL
2(-2xto Blo+1lie Se
2( 11- =ta-1)
VĀ
Se.
2( 2(-221, 11o+1 V max 2i= m
The function is defined the domain (x I1t+1 S x. S )-
Segment 4. For convenience, we define w = f(x(o+1). We can verify that w 2 Å: as
1
<
1 np:
-2xta
(1-
Dto S
4V
Iro
-2
1to+1
Tto V 2
Via
4
-2.5o
Uto+1
Lxto
A (1ig
2000 )²
S Å.
4v max (1/eEE-)) 11)
2
4--2rt I1o+1) [
Lt= me)
So we conclude w 2 Å. Now we construct quadratic function similar to that in Proposition 1 of
[17]: it passes (Zt++1, w) with gradient 2/mmx (1/2 )
the minimum is Ito+1
Å E me) This quadratic function is defined to be
T-1 +1=t++1
x 1tot1 + Á ma/e1//, Ei=to+1 E1 mh
Â
f(x)
4mx (1/2, D1- +1= 7
on the domain fx : x S }. It is obvious that f(x) 2 0 and ê-smooth. Following the same reasoning of Proposition in [17], also presented as Lemma in the appendix for completeness, we can conclude for all to + 1tt
VA
[f(x))] 2
min 112)
VV max (1/4, (1/1,
ET- TT
+ t1 m
4
where in the second inequality use Ei=lo+1 11 Lt=lo+1 VFTI 1/2
T-1
The following lemma is used in the proof of Theorem 2. It is a straightforward modification of Proposition in [17]. We present it here for completeness.
Lemma Under the same setting and notations as the proof of Theorem 2, if we run gradient descent with stepsize {nt TT-1 starting from point Zi, on function
x x- 2 + Amax(1 (10,, Ei-ot nh
Â
f(x)
+ w
4 4mxx11/4 E7-1 Tt}
4
then all +15t5T,
V
[(())] 4 max (1/4, Σr- T-1
+1 m
21

---

Proof. From the update of gradient descent, we have
2t 1t + / maxx(11/, Ei n
T+++1 = It 77
1//e Ei=t++ nc}
which leads to
T-1
Å max(1/e,
Σ nh t=ta+1
2141 Ito+1
= - 2 max (1/6, Σ
T-1 Â maxx(1/e
It Ftot1
Σ t-
ne
7-1
1 1/
Recursing this, for j S T
T-1
2j Ito-1 +
Ámaxf1/4,
meb
j-1
T-1 á max
II
1
#to+1
Ito+1 +
Σ ne
2 1max(1/6 Σ
2i=to1 110
k=
exp
log
Σ
U
Â max(11/e
Σ m1
2 max (1/L, 21 11
k=t++1
t=
T-1 Σ t=
1
Å max
n}
2
where in the second inequality, we use 1/2 exp(log 1 2) for 0 S 1. This directly implies what want prove by computing ff())
C Proofs for NSGD Family in Section 4
Algorithm 3 Normalized Stochastic Gradient Descent (NSGD)
1: Input: initial point Zo
2: for = 2. do
3: sample & and set learning rate "
4: Øt++ 2t [ 9(x Ex)
5: end for
Proof for Theorem 3
Proof. Let us pick f(x) 5 with
2 L < & and a=e Tmmas"
Then we pick uo such that
2
c Ta /22. which implies that ||V (mx) > and f(o) min s A. Now we define
/22 2A
D {x -w I w with f 7max
i. For E D, have |V](()] S a and
22

---

normalization
normalization
(a) example
(b) example
Figure 3: The expected update of NSGD can vanish (example 1) or be in the opposite direction (example 2) of the true gradient. The solid black arrow represents the true gradient and the dashed arrows are the possible stochastic gradients (with equal possibilities). The solid blue arrow is the expected direction of NSGD update.
construct the noisy gradients: with d >>>
1 g( = (1 + ()))(x w.p. 2 and ((;;() = (1-))((()) w.p. 2
1
is obvious that fz(x) = Eig(2; {)] and the variance at this point E Vf(z) - g(:: E)l2
(+))1 S a² with 6 sufficiently close to With the update rule, we note that Zz+1 It 7 w.p. 1/2 and Tz41 24 Vt w.p. 1/2, and therefore
D = 1 =
Eg, V
rell L| + +wlll 2 D| = [f))))
For x & D. we have |ل|||| > e/ L + Tmax. and we assume there is no noise in the gradients. Therefore, 24 E D, we know that after one step of update || ll > c/L, which implies [/V c. Combining two cases that 24 D and H, & D, we know that f for all
Proof of Proposition 1
Proof. Denote e g( f(z)). By Lemma 2 in [14].
87:
((144))-f6e < [Vf(x))]
||elll
3
Telescoping from = to T 1, 1,
T-1
T-
Eg
[f(()))l 5
< A
relleal
+
Σ
37
3
2
1=0
1=0
Taking expectation, rearranging and using
[||e |||
S (E [1ler (2])
1/2
< o, we derive
A
80
E [|V]((>))11 < 2/ 2/2
7
3
(t + 1)
2
1=
A
1/
1/2
by log(())
?
Proof for Proposition 2
23

---

Proof. We define & 9t Vf()). By Lemma 2 in [14], for any > 0
((04))-1(ae) S 24 [
||eell
Eg
3
Telescoping from = to To 11
T-1
T-1 nll v < +
T-1 Σ
T-1
L
él
+
Σ
3
2
t=0
By taking expectation on both sides, rearranging and controlling the variance term using Lemma 2, we derive
A
T-1
T-1 By
Σ E |||VS
3T7
Σ
B || +
Σ
(1 + 1) 3//2
3/2
37
2
t=
1=U
S
377
A
+
(C1o + C2ey) log(T) + /1/2
284
3
A
S CT3M
+ (o + bx) log(T)
Lemma 2. Under the setting of Theorem there exist numerical constants C1, C2 > 0 such that for all t 2 1,
E [ S Ciauy + C2l
Iléll < (Cioy + C2b7?) log(T),
where é g Vz(zz).
Proof. Define e, g(xx(iii) Ee) Vf(x,), Vf(xx) - vf(x+t)). Then
ê-1
J++1 vs(+++1)
(1 (1-at) a.g(0441i444) (f(4)11)
[1 (1-a,)è: a,441 (1 S,
Unrolling the recursion from /
1 to = 0, we have
T-1 êT = (1)) èo +
T-1
T-1
T-1
T-1
Σ
II
(1 - a,)
Σ (1 oz) II r=
(1 (1-a7).4
t=
t=
+=t+1
t=
Define the o-filld F, == ((:o0:5o.... EI 1. Notice that for any l2 4 2 we have
Elee, cx,) E E Kee, [F..) E [Ke,, E [e,, F F = 0.
(9)
Then taking norm, applying expectation both sides of (8) and using E
[|| a, have
T-1
E []] <
II (1 an)
o +
Σ
04.4+1
II
(1-a7) a.)
(1 -
1=0
r=t+1
+E
Σ (1- a.)
II (1 (.)

---

T-1
||1
1/2
an)
E
0+C++1
II (1 - an) (1-a=))
+=t+1
T-1
0 )3 ||I|
II (1
1/2
Σ FE 1=0
T-1
(1 an)
|lettll
|
II (1 az)² -=
T-1
T-1 II
+6
o1)7
(1
-07)
1=
==t+1
T
T-1
T-1
4/2
T-1
T-1
II
0
Σ o
II (1 (1-a+) r=
o+
Ix
e,
where the first inequality holds by Jensen's inequality applied to x + x² the second inequality follows by (9) and the bound ||Se]| S f||=1-1 zell = b/ The last step is due bounded variance [[]|o]]] S and Ox, < 1.
By the choice of momentum sequence, we have ag = 1 and the first term is zero. By Lemma 3, there exist numerical constants C₁, C2 > 0 such that
Σ 1=
o II (1 (1-0+)
T-1
an)
1/2
S Clat
1/2
Σ r=0
II (1 (1-aa)) ar) I Cerraa' T=1+1
T-1
r=1+1
Therefore, for all T I, we have
E[lêr & CloaY + C2lyraT
T-1
T-1 + Cze
E
||]
$ Ci Σ
700
1/2
Σ
a
t=
T-1
T-1
< Ciar Σ
(1 (++1)) + C2ly
(l (1+1) 10++1)11/00 3/2 (1 +1+ 1)
1=0
1=0
s (Cioy ( log(T).
Lemma (Lemma 15 [19]). Let q E [0, 1), p 2 0, 7o > and let ni = (122)² 7t 70 ((t1)
for every integer t. Then for any integers and T > 1, it holds
T-1
T-1
Σ
7t II (1 n S Cyn'T'
r=1+1
where C.
20-0(1 - to exp (2º(1 0)0-0) 220+1-9(1 -2- and to
max { (1-1)22)
1- .2 (=2))) }
25

---

D Proofs for Scalar AMSGrad and AdaGrad in Section 4
The following is an extended version of Theorem 5 including " --+) with 0 < a < 1.
Theorem 7. Under Assumption 1, if run AMSGrad-norm with Yt [++1)a to 31 B2 in the deterministic setting, then for any 7y > 0 and 0 a if 00 70
0 and
T V [ 2 TT max fax(up (un, 2FA}
2A
T
v0 7l
T-1
1
22
2(M A) -T -a max 2 + A)),
(z+))
T
T
where
L
6r² 1 + log
vp -
when 1/2,
872
M
when 1/2 <a 1
2 (1 2 2a)
7(6)) -1
2-2 when 0 < a < 1/2.
2(1 -2a)u
Proof. The effective stepsize of AMSGrad-nome contains a maximum over all gradient norms in the denominator. As it is desirable to find lower bound for the effective stepsize, we begin by bounding the gradient norms.
Let T be the first iteration where the effective stepsize is less or equal to 1/E, i.e., 1/r-1 > 1/6 and Mr S 1/E. First, we assume 2 i.c. un < 7L. The time stamp itself is naturally bounded by
1 p.
by
87
M--
T
T T
We have
1/2
(g
5
<
2262.
(10)
By E-smoothness of f(-),
((x+11) S (1x) + (VI(z)), x1+1
+x+1 - rx) + || - 2xel
2
E
= =((x)) - m/ / / (xx)]
+
V (xx))1
(11)
2
< <)()) + bn
[
Therefore,
1
Σ
2
f(x)) - ((00) S 2
5
11
26

---

8-2
2 (1 + logT), when a = 1/2.
lg?
2(1 - 21-2a)' when 1/2<a <1,
272
2(1 - -2a)" when 0 < < 1/2.
We denote the right hand side as M. Also from (11) and definition of we know that f(x)) S f(zr) for t 2 and therefore, for all t 2 T,
f(x)) f -
MM+
which implies
[[ & 2f(((z)) - M) = + +A).
Therefore, we can bound for all 2 0,
S max 2P( A)}-
Fort t 2 T, by (11)
- -(())) - 11t 2 [+((2))1
By telescoping from / - T to - 1, we get
(f(x+) -((r))
nell [<(\)(
7
[f(2,)]
+ 1)a
7
[f((a))11
Tov++1
? T Ta 20 + A)) [+
Then we have
Σ [V[())1 < (s(x,) [(xT)) T 7" max(7e, 228(M + A))
7
2 (f(x)) f(x")) T max(re 22 A)}
7
2(M + + T max 22e(M + A)).
Combining with (10), we obtain
1/2 728 + 2(M + A)TT
(
[
<
max 22 + +)}.
vo
7
0=0
When O, we have
T-1 Σ
T-1
((f(z)) [(xT))
[ >
Σ
V (x
T000+1
To mo. /2
27

---

which implies
2 S
max Po. 22EA].
7
1=0
Remark 3. For any 0 < a < 1, we compare simplified AMSGrad with " = [e-1y= to SGD with Tt (-- in the deterministic case (setting 0 in Theorem 6), observe that they achieve the same convergence rate. However, the complexity of simplified AMSGrad only includes polynomial term in and E, while that of SGD includes an exponential term in (nt))/a.
In the following, we will first provide the lower bounds for scalar version of AMSGrad (referred as AMSGrad-norm) with each a E (0, 1) and discuss why it may fail with a 0 when problem parameters unknown, which means that deterministic setting. Second, show that it also fails achieve the optimal convergence rate in the stochastic setting when stochastic gradients are unbounded. To make the results more general, we consider the standard scalar AMSGrad with momentum hyper-paramette parameters $1 and (2. which is presented in Algorithm 2.
achieve the optimal complexity O -) in the
Before proceeding to our results, we present lemma which is handy for conducing lower bounds for SGD-like algorithms with momentum (see Algorithm 4). As long an upper bound is known for stepsize Yl, derive lower bound similar Proposition in [17].
Algorithm 4 General SGD with Momentum
1: Input: initial point momentum parameters S $1 < 1 and initial moment mo. 2.. 3: sample &
2: for
4: M4++1 = 8i + (1 - 31)g(11;
5: obtain stepsize 1)2 > 0
6: dt++1 24 1,+
7:
end for
Lemma 4. For any E > 0. A > 0 and T L, there exists a E-smooth function f R. R, and To with f(x) inf, (x) s A, such that if we run Algorithm 4 with deterministic gradients and
S for t = 0, 1,2, T 1, then we have
A
min Vf(xz)) 2
(0
16max(1/E,
E1 7
Proof.
We construct quadratic function similar to Proposition 1 in [17]. The following function is considered:
f(x)
4mxx
1/e,
Σ
Without loss of generality, assume the initial moment my is non-positive, and we set the initial point 2e
z0p
A
max
1/2,
7h
Otherwise the initial moment is set to be positive, then we let xo be negative and follow the same reasoning.
Since 2o is positive, the first gradient direction would be positive, i.e., vf(z)) 0. Let be the first iteration such that m, 0. By the update rule and definition of it is obvious that 2, 2 2o for 1. IfT < trivially holds that V fx(x) > V.(2)) for all t < T 1. Otherwise,
28

---

(z)))))( That is to say. the gradient we have m, = B1m7-1 + (1 -1)
estimation my used in the 7-th step has the correct direction but its magnitude is no larger than the actual gradient. Starting from the 7-th iteration, It will monotonically move left towards the solution. Note that since our stepsize small enough, i.e.,
T 1/e.
M) S f/2 max
f/ t=
the updates will remain positive, i.e., > 0 for L T. By the update rule, we note that 2 S
for & 2 T. and therefore V f( < (x()). We can conclude that for any 2 T, we have
my S V Then for t 2 1 we have
24 2
7-m
k=t-1
t-1
2 1--11
ii V (x
k=T-1
Σ
---1
Tr-1
1/e, IT-1
k=r-1
max
tec
2
2
Then conclude by
A 16max (1/E, 20 mh
[V(())] max
{1/E,
T-1
4 4max {1/E, ΣT- m1
110
Now we proceed to provide the lower bound for deterministic case.
Theorem For any > 0, 0 and T > 1, there exists a E-smooth function f R + R and zo with fxx) inf f=x I A, such that we run Algorithm with deterministic gradients,
0 0o < E and 7t (-- with y en we have (1) if < for any < and
S B2 < I, we have
A
min E (0..
[f(x))
16 (1/e, (1 (1=2) T1-ap
and (2) a for B1 = 0 and any 0 S B2 < 1, we have
min
(f)( co.
1E(0,1....T111
Remark 4. From the theorem, we can conclude that the optimal convergence rate + for (x:)) is infeasible for AMSGrad with pol polynomially decreasing stepsize. When = 0, similar result can be obtained for the case 31 2 0, B2 O and small enough vo-
Proof. For 0, we have
?
7
(t 1)ah
02
(t 1))
29

---

Let fi: v1
and then we have
Σ + - 11+1)" $ (1 1/
7 T
Applying Lemma directly gives us the desired result. For 0, we consider function
f(x) x2
Note that since Uo I Ey the function is e-smooth. Let
7
Zg 2
which satisfies the condition that ((00) S A. Then after one update
of 320 + (1
V f((0)) = -
3o
If continue this calculation, we find that the iterates will oscillate between 2 and - forever, which finishes the proof.
Proof for Theorem 4
Proof. consider a two-dimensional function f IR2 + IR, for 22) R?,
f(x) = F(z*),
where its function value only depends on the first dimension and will define F R IR later. The gradient at x is fx) (VF(x'), 0)) We add the noise only to the second dimension, i.e., g(x; E) (V (xr)), E). For any / 2 0, the probability density function of the noise as
-1 (#) ?
x 2 0;
Ps. Pg. (I)
1 (-#) -1 (-#)
T < 0,
where (r(1
Note that the distribution is symmetric and E [&L = 0. Also, we note that [al
follows the Fréchet distribution [15] with cumulative distribution function
Pr([& S x) -5-))
and
Var [c.] E [|εe|
(E [Ee))
sr
- (E [E.])
$ r2r
2
<00
where we used the exact second moment for Fréchet distribution.
30

---

Next, we will show that : maxoskgt [lxl] 8 & also follows Fréchet distribution with CDF
((+1)(-173
with probability 1.
We know that
Pr(fe =) exp (-0r(e
8 (t 1)$
Then for constant C > O,
(1+ (1+ 1)6- -7
Pr(fe S C. (++1)6-2) cxp
s. 1)$
?
(1 1)+1--11
exp
4(1 + 1)
where the last inequality by selecting C s(((--1)) and using exp (- any > 0 and 0 < m < Then using union bound, have
2
pm
S
for
v2
T Σ
Pr(f: > C (t++ for 0
4(1
1)2²
2
1=
Now we have shown that with some probability, the noise is large enough. We can use this property to provide an upper bound it for the stepsize as follow
7
T/
Vl + To++1
?
Vl Vmmxoosst (320h (1 (2)
V m (22 ( Ex
7
Vl+ I++Immaxosss ((1 32) [1]
VL+ TV( B2]E,
7
A T/.
C(++ 1)5 (11 82)
This implies
Σ i 5
(T
5).
(1 C)C C) 32)
We observe that the update with AMSGrad norm in function f corresponds to applying general SGD with momentum (Algorithm 4) to function F with stepsize M)- Therefore, we can pick a hard instance F according Lemma 4, and by noting that [[V(()) = [VF('') we reach our conclusion.
Remark 5. As we see above, the function the proof constructed by Lemma 4. We note that even assuming the gradients of f to be bounded, i.e., [IV [x)]l < K for all x, will not prevent the slow convergence in Theorem 4. This is because in the proof of Lemma 4 all iterates stay between
[0, 10 (e.g., = 1 if mo 0),
construct any Lipschitz functiio outside of this segment.
31

---

Algorithm 5 AdaGrad-norm
1: Input: initial point zo, vo > and v) > 0
2: for t = 0, 2, do
3: sample &t
4: of+1 = ot + (
5: 21+1 2t V (() Et)
6: end for
Proof for Proposition 3
Define a function f Rdd - R such that f(x, y) = f(x) - . Since the f is e-mmooth and é-strongly concave about y, the condition number is defined to k: = 1. Applying AdaGrad- norm f equivalent to applying NeAda-AdaGrad (Algorithm
Proof.
[68]) to with y = For every we know (z) - arg max, [(x, y) = 0. Then & E dll "iluuyy" (m:)]l" = 0. Plugging
20g
in = 1, & = O and batchsize M = to Theorem 3.1 in [68]. we reach the conclusion.
32


Reviews:
[{"review_id": "a5r04M8oeV", "reviewer": "Reviewer_CaFA", "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.\nIn 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. ", "questions": "Already said in the paragraph above", "limitations": "Already said in the paragraph above", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper's description of the problem it wants to tackle is good, and the questions addressed are well introduced.\n- 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.  \n- The figures summarize well the main idea of the negative result on untuned SGD and the principle of the lower bound \n- The table helps to navigate in this hairy paper\n", "weaknesses": "*Main comments*\n\nWhile 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:\n- 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?\n- 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.\n- 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.  \n\n*Minor comments*\n\n- 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.\n- 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.\n\n*Final precaution.* \n\nOverall, 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. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the comments! \n\n> **The main phenomenon ... Maybe some experiments on non-toyish problem ...**\n\nThank you for suggesting additional experiments. We have now included a large-scale experiment on a widely-used 50-layer ResNet trained on the CIFAR-10 dataset and observed similar phenomenon.  With a larger initial stepsize, SGD tends to first experience an exponential blow-up before eventually converging as the stepsize decreases sufficiently. In contrast, adaptive gradient methods are robust to the stepsize change.\nPlease find the experimental results in the uploaded PDF of the general response to all reviewers.\nWe believe these experiments are representative and well support our theoretical findings on the benefits of adaptive methods over SGD.\n\n> **The article claims ... not really serve to give an answer to the claimed question ... the set-up is still not valid for the simplest least square case … it does not seem to me as an incredible update.**\n\nBounded variance is a standard assumption in the literature (Ghadimi et al., 2013; Zaheer et al., 2018; Arjevani et al., 2023), which we believe is a good starting point to study the benefits of adaptive gradient methods over SGD. While this assumption may not cover all practical ML applications, we note that it holds for many important examples. For instance,  bounded variance assumption has been confirmed in certain deep learning tasks where stochastic gradient noises exhibit Gaussian-like patterns (Xie et al., 2020). In contrast, the bounded stochastic gradient is a much more restrictive assumption and does not hold even for Gaussian noises. From a theoretical standpoint, removing bounded gradient assumptions for adaptive methods is an important and active research topic (Faw et al., 2022; Kavis et al., 2022; Wang et al., 2023). Therefore, we believe that our efforts in moving beyond this assumption are a significant contribution.\nFurthermore, we expect our results can be extended to more relaxed assumptions, such as the expected smoothness (Khaled et al., 2022), defined as $\\mathbb{E} \\\\|g(x, \\xi)\\\\| \\leq 2A (f(x) - f^\\*) + B\\\\| \\nabla f(x) \\\\|^2 + C$ for some constants $A, B, C \\geq 0$, which accommodates the least square problem suggested by the reviewer.\n\n\n> **Finally ... it is very difficult to understand the true contribution of the article ... I, was completely lost in what was known ...**\n\n\nWe investigate different algorithms under different setups in order to provide a comprehensive and sound comparison between untuned SGD and adaptive methods. Collectively, these results reveal that a strict advantage of adaptive methods is removing the exponential factor, not achieving an order-optimal rate parameter-agnostically as commonly perceived  -- an insight that we formally prove in this paper. \n\nAs illustrated in Table 1, all entries in cells without accompanying theorem references are new results. \n\n\nWe would like to highlight that the following are the most pivotal contributions of our paper:\n\n- For SGD, when using diminishing stepsizes, it can converge without knowing $\\ell$. This convergence, however, comes with the cost of an exponential dependency on $\\eta \\ell$. We derive corresponding upper (Theorem 1 and 6) and lower (Theorem 2) bounds.\n- For AMSGrad-Norm, we provide convergence analysis for the deterministic setting with both upper and lower bounds (Theorem 5 and 8). \nIn the stochastic setting, we show that its convergence can be arbitrarily slower than any polynomial rate (Theorem 4).\n- For Normalized SGD, we establish its nonconvergence in the stochastic settings with any stepsize (Theorem 3).\n\nThe rest of our results are also novel and help support our key insight and build a complete picture. Following the reviewer's comment, we will refine the paper's structure and enhance its clarity in the new version.\n\n\n> **Theorem 1: $\\Delta$ is not defined ... there is no problem when $\\eta$ is too big ... this may be an artifact on the bounded variance stochastic gradient assumption.**\n\n\nThe symbol $\\Delta$ is defined in line 148 as the initial function value gap.\nThe convergence with a large $\\eta$ is not due to the assumption of bounded variance but rather the use of diminishing stepsizes.\nWhen $\\eta$ is excessively large, SGD will initially diverge and then converge once the value of $t$ becomes large enough to render $\\eta/\\sqrt{t}$ small. \nThe initial divergence behavior is encapsulated by the exponential dependence of $\\eta\\ell$ in the upper bound, i.e., $(4e)^{2 \\eta^2\\ell^2}$, which is the cost of excessively large initial stepsize. \n\n\n> **Theorem 2: Good lower bound ... However, why not proving it for SGD? ...**\n\nThank you for recognizing the value of our lower bound.\nWe note that the lower bound for GD is a stronger result. As GD is a special case of SGD when the gradient noise is reduced to zero, the lower bound in Theorem 2 also works for SGD. The lower bound already matches our upper bound in Theorem 1, implying that the lower bound is also tight for SGD.\n\n\n**References**\n\n- Ghadimi, Saeed, et al. \"Stochastic first-and zeroth-order methods for nonconvex stochastic programming.\" SIAM Journal on Optimization. 2013.\n- Arjevani, Yossi, et al. \"Lower bounds for non-convex stochastic optimization.\" Mathematical Programming. 2023.\n- Zaheer, Manzil, et al. \"Adaptive methods for nonconvex optimization.\"  NeurIPS. 2018.\n- Khaled, Ahmed, et al. \"Better Theory for SGD in the Nonconvex World.\" TMLR. 2022.\n- Xie, Zeke, et al. \"A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima.\" ICML. 2020.\n- Faw, Matthew, et al. \"The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance.\" COLT. 2022.\n- Kavis, Ali, et al. \"Adaptive stochastic variance reduction for non-convex finite-sum minimization.\" NeurIPS. 2022.\n- Wang, Bohan, et al. \"Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions.\" COLT. 2023."}, {"review_id": "z503972rH0", "reviewer": "Reviewer_viw9", "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.", "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.", "limitations": ".", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "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.\n\nAs 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.\n\nWhen 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.\n\nOn 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.\n\nI 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the recognition of our work.\n\n> **At a high level, one can argue that the result was \"known\" in the following sense... 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.**\n\nWe agree that this is an intuition behind our results. We note that SGD with a constant stepsize may diverge exponentially, but it is less apparent that an exponential term persists even with a _diminishing_ stepsize, while simultaneously achieving an order-optimal convergence.\nFurthermore, it is noteworthy that the exponential term is _multiplied_ by the optimal rate in both our upper and lower bounds,\nwhich is nontrivial.\n\nIn general, our results reveal that a strict advantage of adaptive methods is removing the exponential factor, not achieving an order-optimal rate parameter-agnostically as commonly perceived  -- an insight that might seem intuitive in hindsight but to our knowledge has not been formally proved in the existing literature -- and we believe it is a valuable one that deserves recognition. \n\n> **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.**\n\n\nWe appreciate the reviewer's insightful question. Our focus in this paper is on the nonconvex setting  because most of the motivating examples are in the nonconvex regime.  \n\nAfter some preliminary study, we believe that the upper bound analysis can be extended to the smooth convex setting. Analogous to the proof of Theorem 1, the analysis can be divided into two stages: the first stage is when the stepsize is still larger than $1/\\ell$; the second stage is when the stepsize has decreased to be small enough. Let $\\tau$ be the first iteration when the stepsize is less than $1/\\ell$. In the first stage, by employing techniques similar to those in Theorem 1 and leveraging convexity, we can bound  $\\\\\\|x\\_{\\tau} - x^\\*\\\\\\|^2$ by an exponential term. \nThe term  $\\\\\\|x\\_\\tau - x^\\*\\\\\\|$ then serves as an initial distance for the second stage, and we can analyze the convergence in this stage with \nthe classic analysis in the stochastic convex setting, leading to a complexity of $\\mathcal{O}(1/\\epsilon^2)$ for finding an epsilon optimal point (i.e., $f(x) - f^\\* \\leq \\epsilon$). Combining two stages together  leads to a total complexity of $\\epsilon^{-2}$ multiplied by an exponential term. \n\n\nOur original nonconvex hard instance for the lower bound does not apply here. However, we may construct a simple instance in the convex setting: a two-dimensional additive example such as $\\ell x\\_1^2 + \\lambda x\\_2^2$. This instance results in a lower bound of the order $\\exp{(\\ell^2)}\\log^2\\epsilon^{-1} + \\epsilon^{-4}$ for finding an $\\epsilon$-stationary point or $\\exp{(\\ell^2)}\\log\\epsilon^{-1} + \\epsilon^{-2}$ for finding an $\\epsilon$-optimal point. We note that the highest-order term in $\\epsilon$ is not multiplied by the exponential term. Therefore, we suspect there is a small gap with this simple hard instance, making it an interesting future direction to explore. \n"}, {"review_id": "RAmXS6EXEH", "reviewer": "Reviewer_WWqH", "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. ", "questions": "See the points above for the questions. ", "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. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "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. \n\n2) 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. \n\nThe 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:\n\n1) 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. \n\n2) 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 ?\n\n\n\n[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).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThanks for the recognition of our work.\n\n> **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.**\n\nWe thank the reviewer for mentioning this, and we will put the formal definitions for Segments-2 and 3 in the main body of the paper. In the current version, their definitions can be found in the proof for Theorem 2 (in Appendix B.2 of the supplementary material). They are constructed to connect Segment-1 to Segment-4 and guarantee the overall function is continuous and $\\ell$-smooth. \n\n\n> **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 \\geq \\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 $\\eta$ as large as possible?**\n\nIf we interpret the reviewer's question accurately, in the last sentence, the reviewer is asking \"is it true that achieving generalization is the bottleneck in chosing step-size $\\eta$ as _small_ as possible?\". \nFrom the optimization perspective, a reasonable stepsize ($\\eta \\leq 1/\\ell$) avoids blow-up, but an excessively small stepsize  results in slower convergence. This is also indicated in Theorem 1 that when $\\eta \\leq 1/\\ell$, the bound includes an $\\eta^{-1}$ factor, signaling a slowdown. The slow convergence is intuitively expected in practical scenarios when an extremely small stepsize is used. Hence, achieving generalization is not the only hindrance; a proper stepsize, e.g. $\\Theta(1/\\ell)$, is required to achieve fast optimization.\n\nWhen taking generalization into account, the situation becomes more complicated and exceeds the scope of this paper. However, we agree that the relationship between stepsize and generalization is an intriguing research topic that has been actively and extensively examined (Jastrzębski et al., 2017; He et al., 2019; Li et al., 2019; Nakkiran, 2020). \nIt would an interesting future direction to balance optimization and generalization bounds in different stepsize regimes.\n\n**References**\n\n- Jastrzębski, Stanisław, et al. \"Three factors influencing minima in sgd.\" arXiv preprint arXiv:1711.04623. 2017.\n- He, Fengxiang, et al. \"Control batch size and learning rate to generalize well: Theoretical and empirical evidence.\" NeurIPS. 2019. \n- Li, Yuanzhi, et al. \"Towards explaining the regularization effect of initial large learning rate in training neural networks.\" NeurIPS. 2019.\n- Nakkiran, Preetum. \"Learning rate annealing can provably help generalization, even for convex problems.\" arXiv preprint arXiv:2005.07360. 2020."}, {"review_id": "k5S6vBkaR9", "reviewer": "Reviewer_vyoV", "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.", "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?", "limitations": "Yes, the authors have addressed their limitations through the checklist.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the recognition of our work.\n\n> **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].**\n\n\nTo complement our experiments on MNIST, we used the CIFAR-10 dataset (Krizhevsky et al., 2009), as suggested in [24], to train a 50-layer\nResNet (He et al., 2016), which is more common and large-scale than models in [6, 54]. In these experiments, we observed a similar exponential explosion phenomenon with SGD when using large stepsizes. In contrast, adaptive methods demonstrated robustness to changes in stepsizes. The detailed experimental results can be found in the PDF of our general response to all reviewers.\n\n> **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?**\n\nIn Figure 1 of our paper, the 3-layer neural network is structured with layer sizes as follows: 784 (input size) $\\rightarrow$ 512 $\\rightarrow$ 256 $\\rightarrow$ 10.\nIn our new experiment, when we use a 50-layer ResNet -- an over-parameterized neural network with more than 23 million parameters -- we observed behaviors consistent with our findings from smaller networks.\n\n**References**\n\n- Krizhevsky, Alex, et al. \"Learning multiple layers of features from tiny images. 2009.\n- He, Kaiming, et al. \"Deep residual learning for image recognition.\" CVPR. 2016.\n"}, {"review_id": "OFjWNs51uL", "reviewer": "Reviewer_hiCA", "summary": "This paper shows mainly two things:\n(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.\n(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.\n\nThe paper also presents a novel analysis of AMSGrad that removes the bounded gradients assumption.", "questions": "1. Please address the difference between your results and the results I've mentioned in the weaknesses section. ", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The result on AMSGrad is new and a welcome addition to the literature.\n2. 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].\n\n[1] Khaled and Richtárik. Better Theory for SGD in the Nonconvex World. arXiv:2002.03329\n[2] Vaswani, Benjamin Dubois-Taine, and Babanezhad. Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent. arXiv:2110.11442.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the comments.\n\n> **The result on the exponential dependence on the smoothness constant is a known consequence of another result in the literature...**\n\n\nWe thank the reviewer for pointing out the two relevant references and we will add more discussions about them in the revision. However, we are afraid that the reviewer might have overlooked some fundamental differences between our results and theirs.\n\n**In reference [1]**, Theorem 2  states that: with a constant stepsize $\\eta$, an upper bound of $\\mathcal{O}\\left(\\eta + \\frac{(1+\\ell^2\\eta^2)^T}{\\eta T} \\right)$ holds after $T$ iterations. There are key differences from our Theorem 1:\n\n1. They consider constant stepsize $\\eta$, while we consider polynomially decreasing stepsize $\\eta/\\sqrt{t}$.\n\n2. The exponential terms are very different. Their result contains the term $(1+\\ell^2\\eta^2)^T$ with the exponent $T$, while ours is $(4e)^{2\\eta^2\\ell^2}$ with exponent $2\\eta^2\\ell^2$. \n\n3. When $\\eta$ is relatively large, their result diverges, whereas ours consistently converges.\n\n\nNote that we have also discussed in Remark 1 Line 183 - 185: \"We do not\n consider constant stepsize, i.e., $\\alpha = 0$, because it is well known to diverge even in the deterministic setting if the stepsize is agnostic to the problem parameter [1, 51].\", highlighting the divergent behavior of the constant stepsize. In contrast, the diminishing stepsizes we consider are more interesting, and always lead to convergence despite the presence of the exponential constant.\n\n\n**In reference [2]**, Theorem 5 states that there exists a quadratic function $f(x)$ such that, fixing the total number of iterations $T$, running gradient descent with stepsize $\\eta\\_t = \\frac{\\nu}{\\ell}\\left(\\frac{\\beta}{T} \\right)^{t/T}$, with $\\nu$ and $\\beta$ being some constants, will satisfy $\\\\\\|x\\_{\\tilde t + 1} - x^\\*\\\\\\| \\geq 2^{\\tilde{t}}\\\\\\|x\\_0 - x^*\\\\\\|$ at an iteration $\\tilde{t} = \\Theta(T/\\ln(T))$. The primary distinctions from our lower bound are:\n\n1. The settings are different. They consider strongly convex setting with exponentially decreasing stepsizes that requires a prefixed $T$, but we consider nonconvex setting with polynomially decreasing stepsizes. \n\n2. Their result features the exponential term $2^{\\tilde{t}}$ at a specific iteration $\\tilde{t}$, but their upper bound (as per Theorem 4 in [2]) actually does not include any exponential term at the last iteration $T$. This implies that after $\\tilde t$ iteration, gradient descent can  converge very quickly in their setting. In contrast, both our upper and lower bounds include an exponential term multiplied by $T^{-1/4}$ at the last iteration. \n\n\nWe hope our clarification on these differences addresses the reviewer's concern and we are happy to discuss more if the reviewer has further questions. "}]

Author rebuttal:
We thank the reviewers for their valuable feedback and the overall positive evaluation of our work. 

 As requested by Reviewers CaFA and vyoV, we conducted additional experiments with deep neural networks to demonstrate the gradient explosion effect on a more practical (large scale) experiment. In particular, we evaluated the performance of untuned SGD and several adaptive variants on the CIFAR-10 (Krizhevsky et al., 2009) dataset using a 50-layer ResNet (He et al., 2016). The observations are consistent: with a larger initial stepsize, SGD tends to first experience an exponential blow-up before eventually converging as the stepsize decreases sufficiently, while adaptive gradient methods are robust to the stepsize change. We kindly refer to the attached PDF below for more details.  

If the reviewers have further questions, we will be happy to address them in the discussion phase.

**References**

- Krizhevsky, Alex, et al. "Learning multiple layers of features from tiny images." 2009.
- He, Kaiming, et al. "Deep residual learning for image recognition." CVPR. 2016.

Meta-review: The paper presents valuable theoretical insights into the behavior of stochastic gradient descent (SGD) in the non-convex setting, specifically addressing, via lower bounds, potential exponential dependence on the smoothness constant when using untuned SGD. In contrast, the authors demonstrate that this exponential dependence can be avoided through adaptiveness in the optimization algorithm. While some concerns were raised regarding the empirical evaluation and clarity of contributions in relation to prior work, the authors have effectively addressed these concerns in their rebuttal. The theoretical contributions and the successful clarification of differences with existing literature warrant acceptance of the paper, which offers compelling insights into optimization algorithms' behavior and the value of adaptiveness in modern settings.
Decision: Accept (poster)