AdaGrad under Anisotropic Smoothness
Authors: Yuxing Liu
Rui Pan
Tong Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: Optimization theory
Convergence analysis
Stochastic optimization
Adaptive gradient methods
Primary area: optimization

Abstract: Adaptive gradient methods have been widely adopted in training large-scale deep neural networks, especially large foundation models. Despite the huge success in practice, their theoretical advantages over classical gradient methods with uniform step sizes across all coordinates (e.g. SGD) have not been fully understood, especially in the large batch-size setting commonly used in practice. This is because the only theoretical result that can demonstrate this benefit was obtained in the original paper of Adagrad for convex nonsmooth objective functions, which is insufficient for large batch algorithms. In this work, we attempt to resolve this gap between theory and practice by proposing a novel anisotropic generalized smoothness assumption and providing corresponding analysis of Adagrad. It is shown that under anisotropic smoothness and noise conditions, AdaGrad can achieve faster convergence guarantees in terms of better dimensional dependence than algorithms with uniform step sizes across all coordinates. Experiments in logistic regression and instruction following fine-tuning tasks provide strong evidence to support our novel assumption and theoretical analysis.

Published as a conference paper at ICLR 2025
ADAGRAD UNDER ANISOTROPIC SMOOTHNESS
Yuxing Liu"
Rui Pan"
Tong Zhang
University of Illinois Libana-Champall
(yuxing6, ruip4, tozhang Bachnng)111111 gillincis, allincis.edu
ABSTRACT
Adaptive gradient methods have been widely adopted in training large-scale deep neural networks, especially large foundation models. Despite the huge success in practice, their theoretical advantages over classical gradient methods with uniform step sizes across all coordinates (e.g. SGD) have not been fully understood, espe- cially in the large batch-size setting commonly used in practice. This is because the only theoretical result that can demonstrate this benefit original paper of Adagrad for convex nonsmooth objective functions, which is insufficient for large batch algorithms. In this work, we attempt to resolve this gap between theory and practice by proposing a novel anisotropic generalized smooth- ness assumption and providing corresponding analysis of Adagrad. is shown that under anisotropic smoothness and noise conditions, AdaGrad can achieve faster convergence guarantees in terms of better dimensional dependence than algorithms with uniform step sizes across all coordinates. Experiments in logistic regression and instruction following fine-tuning tasks provide strong evidence to support our novel assumption and theoretical analysis.
obtained the
INTRODUCTION
To solve the stochastic optimization problem
min (w) A [els(w; w E
adaptive gradient methods (Duchi et al. 2014, Loshchilov Hutter 2017) are among the most popular methods. These methods have gained incredible importance from their superior efficiency, especially in training large foundation models, where large batch sizes are commonly employed. One of the most important features of adaptive gradient methods is the coordinate-wise anisotropic step size. Take Adagrad (Duchi et al. 2011 Streeter McMahan 2010), the first adaptive gradient method as an example, which writes
2011 Zeiler 2012 Tieleman et al., 2012 Kingma & Ba
W++1 = W. AAAA g::
where gr notes the stochastic gradient estimation obtained at w, and A, * L is a diagonal matrix, representing the square root of coordinate-wiig wise summation of former gradient estimations.
Despite the huge success in practice, as also noted Li (202T): Kunstner et al. (2023): et al. (2024), the theoretical understanding of when and why adaptive gradient methods enjoy acceleration over classical gradient algorithms with uniform step size across all coordinates such as SGD, still limited. On the theory side, the original Adagrad paper Duchi et al. (2011): Streeter & McMahan (2010) shows the superiority of Adagrad over SGD the convex non-smooth scheme, suggesting that if the gradients are sparse and the predictor is limited in appropriate convex set, Adagrad can converge faster terms of better dimensional dependence. However, as the convergence rates in nonsmooth settings rely on the scale of stochastic gradients, their results be insufficient for the smooth and large-batch training scheme, which is a realistic setting gaining extensive focus. This is because the scale of stochastic gradients does not decrease linearly the batch size M increases. Therefore, if we fix the stochastic gradient computation number N = MT,, where M is the batch size and I' is the total iteration number, such that increasing M leads linear decrease in T.
"Equal contribution.

---

Published as a conference paper at ICLR 2025
the original convergence rate O(I/VT) may be unsatisfying. Fine analysis in smooth settings can solve this problem as the obtained convergence results in this case depend on the gradient variance, which decreases linearly the batch size M increases. Many theoretical papers have also conducted analysis of popular adaptive gradient methods (e.g. Adagrad, Adam) in smooth settings under smoothness and noise assumptions with respect to ||: 12- However, to the best of our knowledge, their proven results have no better or even worse dimensional dependence than the standard convergence results of SGD in the same settings. The existence of this gap between theory and practice makes us wonder: Can we obtain better theoretical guarantees of adaptive gradient methods to explain their practical success, especially in large batch settings?
To answer this question. it would be a good starting point to revisit the well-known insight of adaptive gradient methods. Intuitively, Adagrad shines when the problem is highly imbalanced, i.e., coordinates of the gradients have very different magnitudes. It schedules a larger learning rate (compared to SGD) for coordinates with small gradients and thus converges faster. This implies that the performance of adaptive gradient methods relies largely on the anisotropic structure of the problem. However, existing standard assumptions fail to describe this property. Take the standard smoothness (Nesterov et al. 2018) as an example, which assumes constant L 0 such that LLI 3 V f(w) = LLa for all w. It is evident that this assumption is coordinate- wise equivalent and cannot reflect the imbalance between coordinates, thus the benefits of adaptive gradient methods are hidden, as in the results of Vaswani et al. (2020); Défossez et al. (020): Wang et al.) (2023).
To better explore the provable benefits of adaptive gradient methods, it is necessary to employ appropriate assumptions that can better describe the structure of models. In this paper, we consider the anisotropic smoothness and noise assumptions. Based on these assumptions, we give novel convergence analysis of Adagrad and show that Adagrad can adapt well to the problem's anisotropic nature. To extend our results to more general setting, we additionally introduce novel generalized anisotropic smoothness assumption and provide corresponding analysis of AdaGrad. By comparisons between the convergence results of Adagrad and gradient methods with step sizes across all coordi- nates (SGI) and AdaGrad-Norm (Streeter & McMahan 20TO) as two representatives), we justify the power of adaptive gradient methods when the problem has highly anisotropic nature.
Our contributions are summarized as follows:
1. We present a fine-grained analysis of Adagrad under anisotropic smoothness and noise assumptions, leading novel theoretical convergence guarantees for Adagrad. We further introduce a generalized form of anisotropic smoothness, extending these results to more practical settings.
2. We discuss how the convergence results indicate the potential benefits of AdaGrad compared to algorithms with coordinate-wisely uniform step sizes such as SGD and AdaGrad-Norm.
3. Experiments on logistic regressions on real-world datasets and tostuuttoo-followinng fine- tuning with GPT-2 provide concrete empirical evidence to support our claims.
2 RELATED WORK
Adaptive gradient methods. Adaptive gradient methods are popular optimizers for training neural networks (Choi et al. 2019 Vani & Rao 2019). Among them, Adagrad (Duchi et al. 2011 Streeter & &McMahan| 2010) is considered to be the first adaptive gradient method in this branch, which was originally proposed to solve non-smooth online convex optimization problems. Ever since its first appearance, numerous adaptive gradient methods have emerged, such as RMSProp (Tieleman et al.) 2012), AdaDelta (Zeiler) 2012). Adam (Kingma & Ba 2014), SC-Adagrad (Mukkamala & Hein 2017). Adam (Loshchilov Hutter 2017). WNGrad (Wu et al., 2018). AMSGrad (Reddi et al.
2019). , SAdam (Wang al. 2019) to name few. They have revolutionized the field of deep neural network training, and are still widely adopted in the literature of large language models (Radford
al. 2019 Touvron et al. 2023 Touvron et al.).
Note that the comparison between upper bounds is commonly adopted in past literature, e.g. (Bernstein) al. 201 Sa Allen-Zhu 2018), though theoretically it only suggests the worst-case performance comparison of algonthmms.
2

---

Published as a conference paper at ICLR 2025
Convergence results of SGD. Stochastic gradient descent (SGD), popular optimizer for many real-world tasks, has been extensively studied in the literature (Robbins & Monro 1951 Nemirovsks
& Yudin 1978, Nemirovskij & Yudin 1983 Nemirovski et al. 2009 Hazan et al. [007)
et al. 201 [Saamir & Zhang, 2013). In the smooth stochastic optimization scheme, Moulines and Ghadimi & Lan (2013) gave analysis of SGD under standard assumptions in the convex and nonconvex settings separately. More recently, ZZhang et al. (2019) introduced the
&
(Lo, L1) -smootthsssss to relax the standard smoothness assumption and studied the convergence of
SGD and clipped SGD under this assumption. A line of following work appeared after that (Zhang
ct al.
2020a Chen et al. 2020, Gorbunov et al. 2020 Qian al.. 2021
Koloskova et al. 2023).
Convergence results of Adagrad. As the pioneering work of Adagrad. Duchi et al. (2011) provided an analysis for Adagrad's 's convergence guarantees online convex optimization settings, showing acceleration over SGD when the gradients are sparse. However, the presented analysis is only for general nonsmooth objectives, which is insufficient to explain Adagrad's 's effectiveness under large batch settings. After that, Levy et al. (2018); : Vaswani et al. (2020) studied the smooth convex convergence but showed no better results than SGD. On another side, the convergence of Adagrad or its close variants in the smooth nonconvex setting has been extensively studied (Li & Orabona
2019 Défossez et al. [0200) Ward et al., 2020 Faw et al. 2022 2023 Wang et al. [203]] Kavis
et al. 2022 Liu et al. 2023b Attia & Koren 2023 Hong & Lin 2024b Among them, Ward et al.
(2200) obtained the (1/vVT) rate of Adagrad- Norm under global bounded gradient assumption.
More recently, |Fww et al. (2023): [Wan et al. (2023) further improved the result to hold under the
(Lo, L Ls)-smoothnsss assumptions. There are also extensive studies focused on the convergence of Adam and its close variants, we list some of them here for reference: (Reddi et al. 2019
De et al.
2018|Défossee et al.] 20200, Guo et al. 202T] Zhang et al. 2022. Wang et al. 2022 Li et al. 2024
Wang et al. 2024 Hong& & Lin 2024a).
Theoretical understanding of adaptive gradient methods. Surprisingly, though the community tends to have common sense that adaptive gradient methods converge much faster than algorithms with uniform step sizes in specific tasks, theoretical explanations on when and why this happens are relatively rare compared to extensive empirical studies. It worth pointing out that among all the above-mentioned works on theoretical analysis of adaptive gradient methods, only the initial Adagrad analysis (Duchi al., 2011 clearly shows this acceleration in terms of possibly lower dimensional dependence in the online convex programming setting. How adaptive gradient methods can help accelerate convergence in smooth or large batch stochastic optimization still remains unclear. We also notice that -isachiianchi et al. (2007); Orabona & Pál (2015) 201 8); Zhuang et al. (2022) mentioned the intuition of scale-free algorithms Zhuang et al. (2022) demonstrates the connection between scale-freee freenefseeesss of adaptive gradient methods and better condition number dependence. More recently, Zhang et al. (024)) Das et al. (2024) also investigated why Adam is effective in certain tasks compared to SGD and gives theoretical results in quadraties settings. However, their results more intuitive with very restrictive analysis that are insufficient to explain real-worl tasks. In another line of work, [Bernstein et al. (201 Sa): Wu et al. (2020); Kunstner et al. (2023): ; Liu et al. (202a)) suggests a relation between the benefits of adaptive gradient methods and their sign-based nature. These intuitions may shed light on the theoretical understanding of adaptive gradient methods.
Large batch training. Large batch training enjoys extensive focus for its practical impact. has been observed that large batch sizes are beneficial for accelerating large model training in practice (You et al. 2017a b) 2018 2019 Pan et al. 2022). Furthermore, large batch training is valuable acceleration technique in distributed machine learning (Verbraeken et al. (2200 and pretraining (Zhou et al. (023). where adaptive gradient methods are popular. In particular, it is a
common practice in pretraining of large language models to combine large batch sizes with adaptive gradient methods (Radford et al. 2019 Touvron et al. 2023 Touvron et af.).
Concurrent Work. In parallel with our work, Maladkar et al. 2024) also investigates the use of anisotropic assumptions to describe the nonconvex convergence of AdaGrad. Though the starting points are similar, there are some notable differences between the two works. First, our result applies to more general smoothness assumption that can well describe practical neural network training (as in Figure [] and covers the result in Maladkar et al. (2024). Second, We include a convex part in our paper, which is a simpler case for illustrating the power of anisotropic assumptions. Based on this part and our new assumption and theory, we also did various empirical verifications in the experiment part, which provides strong evidence for our theory. Third, Maladkar et al. (2024) further introduced a
3

---

Published as a conference paper at ICLR 2025
lower bound for gradient fi-norm convergence of SGD, which may help rggorous comparison between SGD and AdaGrad in the nonconvex case. However, it's not clear whether E no-n is a better convergence measure and it depends the training curvature. To conclude, both the work contribute to a better theoretical understanding of the benefits of adaptive gradient methods.
3 PRELIMINARIES
3.1 NOTATIONS
We use O to denote the coordinate-wise product of vectors and without leading to confusion, v- sometimes used to denote the coordinate-wise square root of vector diagonal matrix. Let H E Raxd be a symmetric positive definite matrix, we denote the vector norm induced by H that [|
H w Hw. With slightly abuse of notation, for a vector h TR4, we denote ||w|| Ej=1 wz For symmetric positive definite matrix E Raddd and convex set W we introduce the H-based projection operator II (-) such that W (w) argmin ||z w As discussed in Hazan et al. (2007), the projection is convex program and can be solved efficiently.
Let us denote W f (w: the stochastic gradient oracle at w and g: the gradient estimation employed Wt. Fi - (go.- ... gg- stands for the sigma field of the gradient estimators from the first iteration to the t - iteration. We use E[-] to denote total expectation over Fr where T is the maximum iteration number and E2[-] as an abbreviation of the conditional expectation B[-[Fr].
3.2 PROBLEM SETTINGS AND ASSUMPTIONS
We study the stochastic optimization problem ( where we can only access the stochastic gradient oracle {) at w. Throughout this paper, we consider the following assumptions.
Assumption 3.1 (Convexity). ʃ()) is convex. For convex cases, we search solution in closed convex set W R&d such that there exists at least one optimal solution w. E W and
max w w'll S Doo and max ||w - w'll S D2. w.w'EW
(2)
w.w's EW
Assumption 3.2 (Lower bounded). There exists constant f such that for w E Rd, f(w) 2 f"
Assumption 3.3 (Anisotropic L-smoothness). There exists positive vector L = [L,,.... La] E R such that f(.) is L-smotth, namely, for w, w' E ERd
[Vf(w) - Vf(w')lL-1 S 1/w -w'l..
(3)
Assumption 3.1 and 3.2 are standard for convex and nonconvex problems, respectively. Assump-
tion 3.3 is an anisotropic generalization of the smoothness condition, which has also been employed in line of work on SignSGD (Bernstein et al. [0018|bb) It is also worth pointing out that a similar block Lipschitz assumption is commonly employed the study of coordinate descent (Wright 2015) Richtárik & Takáε 2016). It can be an interesting direction to find out the relations in between. The intuition Assumption 3.3 can be understood in the following manner. When the loss function f(-)
is twice-differentiable Assumption 3.3 is equivalent to 2 A diag(L) that implies the standard
smoothness assumption by L = L oo When the Hessian of f(-) is imbalanced, namely, coordinates have very different scales, L be adapted
this imbalanced distribution and describe tighter upper bound of the Hessian of f(-), resulting in [[]] < Ld. This benefit is realistic as the highly imbalanced spectrum distribution of the Hessian has been widely observed in multiple circumstances (Sagun et al. 2016; Arjevani & Field, 2020 Pan et al. 2021). The power of this adaptation shines when adaptive gradient methods are employed.
We consider the standard stochastic approximation framework (Kushner & Clark 2012) and denote
the gradient noise at w to be n w; E å (f(w)= - V (w: We assume the following assumptions on gradient noise throughout this paper.
Assumption 3.4 (Unbiased Independent gradient). Each (ww; is independently drawn and E [[(w In(w;(] {)] 0.
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 Adagrad
1-1 E R. IR, and batch size M E 1: Input: wo E I2 [1h [m))==
2: Initialize V-1 =
3: for t = =0 to T do
4: Sample mini- B, with [B,] = M uniformly
5: g: M7 EfEB, Vw.(ww::)
6: V: V.-I+ (g: о gz)
7: A, = diag( Vi)
8: Option I: W++1 W (we n A g:)
9: Option II: We+1 W. 7/ gr
10: end for
Output: 1/T T-1
Wt
Assumption 3.5 (Anisotropic noise). There exists positive vector 1.,...., Fal Ry such that
[w;)(w)))] S aj for all
[d].
Note that Assumption 3.5 implies the standard bounded noise assumption by [[||n[w e) S | Intuitively. it upper bounds all the coordinates of n(w: {) instead of only the norm and gives more detailed information the scale of noise. Generally, Combining Assumption and 3.5 allows more fine-grained analysis, which can take the sparsity the model into account. Note that the anisotropic noise assumption has also been explored in other lines of studies on sign-based methods (Bernstein
et al.
2018ale by Crawshaw et al. 2022) and quadratics (Dieuleveut et al. [2017] Ge et al. 2019 Pan
al. 2021: 2023). It is also closely related to Assumption 2 in Zhang et (2020b) where the
authors attempt to model the heavy-taile tailedess of neural networks.
4 ADAGRAD WITH ANISOTROPIC ASSUMPTIONS
How to accelerate the convergence of SGD has been fundamental problem in training machine learning models. One possible approach is lower the implicit dependence of dimension d. As discussed in Nguyen et al. (2019), in smooth strongly convex settings, the lower bound of SGD can be d times larger than a wider class of algorithms including adaptive gradient methods. The original Adagrad paper (Duchi et al. 2011) showed that Adagrad has better dimension dependence than SGD when the stochastic gradients are generally sparse the non-smooth convex scheme. However, in the stochastic smooth optimization scheme, to the best of our knowledge, existing theoretical results are insufficient to account for the benefit of adaptive gradient methods. We attempt to fill the gap, equipped with the anisotropic Assumptions 3.3 and 3.5
4.1 CONVEX CASES
For a warmup, we present results in the convex case to first gain some intuition on how the anisotropic assumptions can better describe the convergence of AdaGrad in the large batch setting.
Theorem 4.1 (Convex convergence of Adagrad). Under Assumptions 3.
for the sequence { {we WT= generated by Adagrad (Algorithm with option I) with constant step size =
3.3 3.4
3.5
Doc, it holds that for WT = (1/T) ET- Wt.
(P (
(Dolloll
Doo |oll
LI, T
D2
D D
E [f((wr) f(w.) O
+0
VMT
Note that is employed mainly for numerical stability and is commonly very small (in order 10 by default). Theorem 4.1 shows that the convergence AdaGrad depends on [[L]], and ||a|] which require Assumptions 3.3 and 3.5 describe. contrast, if we only use the standard L-smooth and oî- bounded gradient variance assumption, explicit dimensional dependence will be inevitably involved, resulting in worse results than coordinate-witg uniform step sizes like Vaswani et al. (2020) To better how Theorem 4.3 can describe the potential benefits of AdaGrad, also include the convergence
5

---

Published as a conference paper at ICLR 2025
rates of SGD and AdaGrad-Norm representatives of algorithms with coordinate-wist wisely uniform step sizes here
[[w.)]=-0 = D2 | (D2)
|[ D3
SGD AdaGrad-Norm:
E [[((w) f(w.)]
VMT +
(6)
T
By comparing the results in Theorem and (6. we can find that whether AdaGrad better than [|]|, Di [ II D2
SGD or AdaGrad-None largely relies the ratios D=o D=llol and
which reflect the sparsity of the curvature, noise, and the geometry of W. When M small such that the variance term, i.c. the term relevant with o, is dominant, ct al. (201T) for nonsmooth cases. Generally, when (1) a is sparse, i.c. has very different scales in different coordinates, which implies that ||o 12 < Válloll2s (2) W satisfies that D2 is close to viD... which can be satisfied by setting W to be hypercube, the variance term of Adagrad might be much smaller than that of SGD. When a large batch size employed, the bias term, the ( term irrelevant with noise, also be important, and thus the superior performance of Adagrad in this case additionally requires that (3) is sparse such that ||ا|| < d || Following Duchi et al.
Dailarlaa
conclusion is consistent with that presented in Duchi
12011) also provide concrete example for better understanding the quantities in Appendix B
Remark 4.2. It is also worth pointing out that the ratio between bias terms of Theorem 4.1 and (6 can
be order (1/d) in extreme cases, while the variance ratio can only be ((1/vd) This suggests an even sharper possible gap when M is large and might provide some intuition on the observation that adaptive gradient methods benefit more from large batch size than SGD (Kunstner et 2023)
4.2 NONCONVEX CASES
Next we consider the more general nonconvex scheme.
Theorem 4.3 (Nonconvex convergence of Adagrad). Under Assumptions 3.2
3.3
3.4
3.5 for
the sequence [we]i=i 17'11 generated by Adagrad (Algorithm) with option II) with constant step size
Lll holds that
N 7
2 )ー=
= AILI
|
L
A
E
V
T
VMT
MvT
T
de [L]|
A
de ||o||
+0
T
VMT
where = (((w)) - f and we use Õ(.) to hide (ogarithmiccaaatt
is worth pointing out that Theorem 4.3 obtains convergence of [[W(())] instead of the common [VW(())l by algorithms with coordinate- wise uniform step sizes like SGD, which indicates at most vd times tighter results when the gradients are generally dense. Similar to the convex case, the introduction of the anisotropic assumptions 3.3 and 3.5 removes the explicit dependence on dimension d compared to existing results adaptive gradient methods like Défossez et al. (2020);
Liu et al. (2023b); Zhang et al. (2022); Wang et al. (2022). rendering AdaGrad at least comparable to algorithms with cordinate-wisehte uniform step sizes like SGD, which has the following results:
( (VILLIaa A ||0l2 W VMT
|L A T
SGD:
IE
| [V](()]l3
We can find that when the batch size is large enough such that M 2 ||o [[[[ A), the compar- ison between Theorem 4.3 and (7) is generally consistent with the comparison between SGD and SignSGD (Bernstein et al. (0) It mainly relies on the sparsity of (((w)) L, and ar which can determine the ratio between the upper bounds. Generally speaking, when L and
sparse and the gradients V (w,,) are relatively dense, Adagrad shines compared to SGD in terms of having
"W also include the standard proof of SGD and discussions convex SGD convergence in Appendix D for completeness. The result of AdaGrad-Norm can he found in Levy al. 2018)

---

Published as a conference paper at ICLR 2025
Table I: We summarize the convergence rates of algorithms under the nonconvex smooth settings, with large enough batch size such that M z || /[]] A). Note that we omit logarithmic terms here. The convergence of SGD in the smooth setting is standard result, and we include the theorem in the appendix for reference. Also, we leave the convergence of SGD under generalized smoothness blank as it is generally incomparable with other results, which we will discuss in Section 5
Convergence Objective
Algorithms
Anisotropic Smooth
Anisotropic Generalized Smooth
Ml Allo la
SGD
[
VNT Theorom D.3
/L LoA
LI
vMT7
AdaGrad-Norm
(B [BW]V
Alllll
1.a2²
Faw et al. 2023
Faw al. 2023
y االااا
[h
[[ 4||0 11
VMT
T.
AdaGrad
(L(W)(())))))
VMT Theorem
L bc Aljall
+
11 4
4.3
<MT
Theorem
5.3
tighter convergence guarantee. We note that this can be realistic case, as can be extremely sparse based on many observations on multiple scenarios (Sagun et al. [216)] Arjevani & Field 2020))
Pan al. 2021). and on the other side, ||= and /f(w=)]ll [V((w))lz can be mild constants examined by
Bernstein et al. (2018)). Therefore, with all these conditions satisfied, we show the potentially faster convergence of AdaGrad compared to SGD. Also, the consistency between the convergence results of
AdaGrad and SignSGD provides theoretical insights into the close relation between adaptive gradient methods and sign-based methods.
ADAGRAD WITH GENERALIZED ANISOTROPIC SMOOTHNESS
In previous sections, have discussed how AdaGrad potentially outperform algorithms with uniform step sizes under the anisotropic smoothness settings. However, the loss function in practice can commonly dissatisfy the smoothness assumption, with local smoothness potentially unbounded. To better describe the complicated real cases, Zhang et al. (2019) introduce the (Lo, -mmoothhesss as generalization of the standard L-smoothness, which can written as
[VS(w)- - VS(w')lla S (Lo + Ln [V[(w)ll)) www-wll2
for all ||w w'll 1/T,, (Zhang al., 2020a). By involving the gradient term to describe the local smoothness, this assumption can even be applicable to describe neural networks (Zhang et al. 2019 Crawshaw al.) (002)). this section, we discuss an extension of both the anisotropic L-smoothness and the (Lo, L1) -smoothness and the corresponding convergence results of AdaGrad.
Assumption 5.1 (Anisotropic (Lo; L, smmothhssss) There exists positive vectors Lg [Lo. Lo.a] E RR and L [L.. Li,d] IRŞ such that f(-) is (-moooh,,,o namely, for w, w' E W such that [ww w'll w'll,, S Vd, it holds that
[V((w) ff(w") V [[((())))= S ||w How-wllen W'll
(9)
where L( (w) [[[ww)......... L ( E Id and [L(w)]; = Lo.j + LL, [0,((w) for all j [d].
For one thing, Assumption is natural generalization Assumption 3.3 and can directly imply
by setting L 0, hence also enjoys the nice properties we have discussed for Assumption 3.3 Also. in the spirits 8 we include the gradient magnitudes to describe the local smoothness. Instead of
the absolute value of each coordinate of the gradient, which is intuitively more relevant to the anisotropic nature of curvature. We also conducted numerical experiments to verify the validity of the assumption, as shown in Figure
the gradient 2-norm,
7

---

Published as a conference paper at ICLR 2025
Remark 5.2. It is also worth noticing that similar but different coordinate- wise generalized smooth- ness assumption has been considered in Crawshaw et al. (2022):
(w) 02 fw")) s (Lo. + L1 |0, (w)l) w'wl
(10)
for all 1/w w/1 ||2 S 1/ || and all coordinates j [d]. Compared to this assumption. As- sumption 5.1 offers several evident advantages: (1) Assumption 3.1 d. not require conditions for each coordinate; (2) Experiments show that Assumption 5.1 can well describe the real anisotropic curvature; (3) Technically, it is difficult to avoid explicit existence of d in the final convergence bound of AdaGrad if Eqn. (0)) employed, for instance, even the convergence of the Generalized SignSGD obtained in Crawshaw et al. 2022) has explicit dependence d.
Theorem 5.3 (Convergence of Adagrad with generalized smoothness).
Under Assumptions 3.2 3.4
3.5
5.1
for the sequence { {wijt=1 ) generated by Adagrad (Algorithm
1 with option II) with constant
Loll
step size tp = r
min
it holds that
2
v Loll A
||ll 10
| A
E
V fw:)))
=0
+
T
VMT
MVT
T
t=
|L A Al|ol +
1
A2
+
VMT
T
+ (e(vlll
de
Loll, A +
||
Iox A)
de ||ll||
T
VMT
where A - ((wo)) f and we use Õ(.) to hide logarithmic factors..
Note that Theorem 5.3 is generalization of Theorem 4.3 based on the relation between Assumptions
5.1 and 3.3 which can directly imply Theorem 4.3 by simply setting L 0. Intuitively, the interpretation of the theorem leads to the following implications.
Comparison with SGD. Zhang et al. (2019) show that SGD generally requires an additional assumption on universally bounded gradients obtain convergence under the generalized (Lo, L1)- smoothness, and thus clipping should be introduced. The theoretical properties of clipped SGD has been extensively studied after that. However, to the best of our knowledge, existing results on
clipped SGD either require restrictive noise assumptions (Zhang et al.) 2019 2020a Chen et al.
2020, Qian al., 202T) or can only shows worse rate on T and M (Koloskova et al.] 2023] Gorbunoy al. 2020). These results are generally incomparable with Theorem 4.3 showing the superiority of adaptive gradient methods, as also found in existing results (Wang et al.
2023 Li et al. 2024).
Comparison with AdaGrad-Norm. One can also look at the convergence results of AdaGrad- Norm (Streeter & McMahan 2010), a scalar step size variant of AdaGrad, with assumption (8:
AdaGrad-Norm: (E ( =ō ( VMT
L + L ||112 L
VMT
T
which is obtained by taking y to optimize the upper bound in Theorem 3 in Faw et al. (2023). ). is worth noticing that in the case L1 O, the comparison between AdaGrad and AdaGrad-Norm is
generally consistent with that between AdaGrad and SGD discussed in Section 4 showing AdaGrad's effectiveness for anisotropic problems. On the other hand, when it comes to the general (Lo, L,)- smoothness assumption. things become more complicated given the indeterminate relationship between the anisotropic L, and L, in (8) This relation is mainly about whether Assumption [5.] or the initial (Lo, Li -smoothness assumption can better fit the common training settings, such as large-scale language model pre-training, which is an intriguing topic worth exploring in the future. Remark 5.4. (Technical Contribution) From the technical perspective, our proof generally considers similar main line to Défossez et al.) (2020); Ward et al. (2020) but involves multiple novel proof techniques to remove the restrictive assumption on globally bounded || f(w)]] and enable the presence of generalized smoothness. Also, Theorem 1he3rem|4.3|camm directly imply comparable convergence result of AdaGrad- -Nrm with Faw et al. (2023); Wang et al. (2023) while it avoids the complicated proof in Faw et al. (2023) and the heavy dependence on 1/c in Wang et al. (2023). On the other hand, however, Faw et al. (2023): Waan et (2023) allows relaxed noise assumption, which may be of interest and we leave it for possible future work.
8

---

Published as a conference paper at ICLR 2025
6
EXPERIMENTAL RESULTS
6.1 CONVEX CASE
To verify the aforementioned theoretical results, conduct experiments logistics regressions, whose loss functions are generally convex smooth. Specifically, we utilize real-world datasets a 44, a6a, 9a, real 1- simm and revl. bi ry from libsvm (Chang & Lin 201T), which comprises of N = 4781, 11220, 32561, 20242 and 72309 samples respectively. Within the former three datasets, each sample has feature of d 123 dimensions, which are generally sparse given only 14 non-zero-valued dimensions in average for each sample. For the latter two large datasets, each sample possesses 47, 236 and d 20, 958 feature dimensions individually each dataset, where only 51.29 and 74.05 dimensions in average are non-zero. More details of the experimental setup are available in Appendix A
Table Statistics on logistic regression. D2 max; |/w,- w- and Doc max; l| w. |loc are estimated by the maximum value under all searched settings without loss explosion. Smaller values in Cvar A Doe / D2 represent better theoretical bounds for Adagrad when compared with SGD. is evident that in large sparse datasets, Do0 is much smaller than D2, verifying the empirical gains of Adagrad implied by our theory.
DATASET
Doo
D2
||]|]
|L]|
CVAR
A4A
9.73
32.24
14.87
7.26
0.30
A6A
8.88
28.57
14.87
7.26
0.31
A9A
9.79
29.43
14.87
7.27
0.32
REAL-SIM
34.70
729.50
2.00
1.01
0.05
RCVI. 1.11.BIC BIN
15.32
635.47
2.00
1.02
0.02
As shown by the results presented in Table 3 for cases when the variance term dominates, e.g. a9a, Adagrad demonstrates similar convergence behaviors for varied batch sizes. This behavior cannot be explained by previous nonsmooth theories, since T = N/M should provide worse convergence guarantees (1 /V) when batch size M increases. Furthermore, Adagrad constantly provides faster convergence than SGD, which verifies the superiority suggested in our theorems. In addition, when the batch size increases and the bias term becomes dominant, Adagrad is affected less than SGD, showing its robustness against different batch sizes.
Table 3:
Training losses of SGD and Adagrad logistic regression over 3 seeds with batch size M. Note that Adagrad's convergence behavior is generally unaffected by the batch size when AM vN.
(f(w) f(w.)) x 10
(SMALL)
M ==1
M
M 16
M
M 256
M 1024
SGD
2.66:t0.08
2.32+0034
3.47++0.07
2.24::.14
4.61+t0.03
8.47:t0.05
24A
ADAGRAD
0.22+0.03
0.22=0.03
0.25+0.03
0.2420.03
0.29:0.03
0.51=0.08
SGD
0.87-1.09
1.40:1.01
0.82:10.09
1.5610.03
1.03:10.01
2.53-10.3
A6A
ADAGRAD
0. 061000000
0.10:0.00
0. 0.1600001
0.21
0.1740.01
0.20:1002
SGD
0.7710.08
0.47
0.48.10.05
0.5810.01
0.52-10.06
0.76:10.01
A9A
ADAGRAD
0. 04.00
0.14
0.15++0.00
0.16++0.1
0.20++0.01
0.12++0.02
(f()) f(w.)) x 10
DATASET (Large)
METHOD
M ==1 1
M = 4
M 16
= 64
M = 256
M = 1024
SGD
0.42-1008
0.27=0.08
0.52+10.06
0.92-0.03
1.5740.02
2.68-10.01
READ-BIK
ADAGRAD
0. 14:000000
0.14:10.00
0. 0.14:10.00
0.1420.00
0.1540..0
0.19:10.00
SGD
0.48++0.02
0.28
0.68++0.04
1.33+0.04
5.02++0.16 2.55++0.21
BINRRY
ADAGRAD
0. 0.10:10.00
0.10:00.00
0.10::0.00
0.1110.00
0.14:10.01
0.20-10.1

---

Published as a conference paper at ICLR 2025
6.2 NONCONVEX CASE
For nonconvex cases, we check the instruction- following fine-tuning task on Alpaca (Taori al.
Table 4: Losses on instruction following tasks with dataset Alpaca and GPT2 model.
2023) dataset with GPT-2 (Radford et al.] 2019)) model. GPT-2 utilizes GELU (Hendrycks & Gim
TraiNIng Loss f(w)
pel 2016) as its activation function. As shown in Table can be observed that Adagrad still outper- forms SGD with different batch sizes. The loss gap especially salient under large batch sizes. This also confirms that Adagrad's convergence speed is not significantly affected by the large batch size, which matches the results in theory. Full experimental details are available in Appendix A
METHOD
M 32
64
128
2.29
ADAGRAD
2.14
2.12
2.11
M = 256
512
1024
SGD
2,36
2:45
2.57
ADAGRAD
Assumption 5.1 in dimension j- 92066
Assumption dimension -96596
0.0030
0.005
0.0025
90
0.004
0.0020
60
00
0.003
0.00.5
-40
0.002
40
0.00.0
0.0005
-20
01001
-31
0.0000
0.003
0.50
1.00
0
(8)(())
x10
[)((ww))
x10
Assumption 5.1 cl dimersion j-712320
Assumpzion dimension j-1106833
100
0.0000
80
80
0.1le: 0./0
400
B./wi-a 21 (M6
0.013
60
-10
0.010
10
11:005
-20
0.005
20
0,0000
0.000
[9,](w]]
x10-7
[[]](w]]
X100
Figure Verification of Assumption 5.1 GPT-2 on Alpaca dataset. x-axis: [0,f(w)l, y-axis: [0, 8; [//"[w//////// w'lj. where the color represents the iteration index of w. We run Adam with full gradients for 100 steps and randomly selected nearby points w and w' along the trajectory to plot the scatter points.
We also examine Assumption 5.1 under this non-convex setting by following the common practice of (Zhang et al. 2019; Crawshaw et al., (022).. Due to the inherent dependency on dimensions in Assumption 5.1 we randomly sample a small portion of the parameters in GPT-2 to check. As shown in Figure I linear bound of local smoothness with respect to the gradient value holds in all randomly chosen dimensions. Notice that the observed condition in Figure T is even stronger, as directly implies Assumption 5.1 by summing up all the dimensions.
7 CONCLUSION
In this paper, present the theoretical convergence results of Adagrad under anisotropic smoothness and noise assumptions. We further introduce a novel anisotropic generalized smoothness assumption to extend the aforementioned results in more fine-grained analysis. Based on the theorems, we conduct comparisons between the convergence rates AdaGrad and SGD and AdaGrad HhaGrdd-Norm the large batch settings. which provides deeper theoretical understanding of when and why adaptive gradient methods can outperform classical gradient algorithms with coordinate-we uniform step sizes. Empirical studies offer strong evidence to support our proposed assumptions and theory.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1-51, 2018.
Yossi Arjevani and Michael Field. Analytic characterization of the hessian in shallow relu models: A tale of symmetry. Advances in Neural Information Processing Systems, 33:5441-5452, 2020.
Amit Attia and Tomer Koren. Sgd with adagrad stepsizes: Full adaptivity with high probability to unknown parameters, unbounded gradients and affine variance. arXiv preprint arXiv:2302.08783, 2023.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar, signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018a.
Jeremy Bernstein, Jiawei Zhao. Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote communication efficient and fault tolerant. arXiv preprint arXlv:1810.05291, 2018b.
Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-orde bounds for predic- tion with expert advice. Machine Learning. 66:321-352, 2007.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1 2011.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances Neural Information Processing Systems, 33:13773-13782. 2020.
Dami Choi. Christopher J Shallue, Zachary Nado, Jachoon Lee, Chris J Maddison, and George E Dahl. On empirical comparisons of optimizers for deep learning. arXiv preprint arXiv:1910.055 190.05444, 2019.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 35:9955-9966 2022.
Rudrajit Das, Naman Agarwal, Sujay Sanghavi, and Inderjit S Dhillon. Towards quantifying the preconditioning effect of adam. arXiv preprint arXiv:2402.07114 2024.
Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and empirical comparison to nesterov acceleration. arXiv preprint arXiv:1807.06666, 2018
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint 0:Xi::2003.02395, 2020.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for lqaat-squares regression. The Journal of Machine Learning Research, 18(1): 3520-3570, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
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 Conference on Learning Theory, pp. 313-355. PMLR, 2022.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. In The Thirty Sixth Annual Conference Learning Theory, pp. 89-160. PMLR, 2023.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.112333 2023.

---

Published as a conference paper at ICLR 2025
Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. In Advances in Neural Information Processing Systems, pp. 14977-14988, 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042-15053, 2020.
Robert Gower,
Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. International Conference on Artificial Intelli- gence and Statistics, pp. 1315-132 1323. PMLR, 2021.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International conference on machine learning. pp. 5200-5209, PMLR, 2019.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tiabba Yang. A novel convergence analysis for algorithms of the adam family. arXiv preprint arXhv:2112.03559, 2021.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69:169-192, 2007.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint
arXiv:1606.08411 08415, 2016.
Yusu Hong and Junhong Lin. On convergence of adam for stochastic optimization under relaxed assumptions. arXiv preprint arXiv:2402.03982 2024a.
Yusu Hong and Junhong Lin. Revisiting convergence of adagrad with relaxed assumptions. arXiv preprint arXiv:2402. 13794, 2024b.
Ali Kavis, Kfir Ychuda Levy, and Volkan Cevher. High probability bounds for class of nonconvex algorithms with adagrad stepsize. arXiv preprint #rXiv:2204.02833 2022.
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint AxXi::0002.03329, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 6980, 2014.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 17343-17363. PMLR, 2023.
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be. arXiv preprint arXiv:2304.1 20...33444.3. 2023.
Harold Joseph Kushner and Dean S Clark. Stochastic approximation methods for constrained and unconstrained systems, volume 26. Springer Science & Business Media, 2012.
Kfr Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. Advances in neural information processing systems, 31, 2018.
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36, 2024.
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, pp. 983-992. PMLR, 2019.
12

---

Published as a conference paper at ICLR 2025
Yan Li, Dhruv Choudhary, Xiaohan Wei, Baichuan Yuan, Bhargav Bhushanam, Tuo Zhao, and Guanghui Lan. Frequency-aware sgd for efficient embedding learning with provable benefits. arXiv preprint arXiv:2110.04844, 2021.
Hong Liu, Zhiyuan Li, David Hall, Percy Liang, and Tengyu Ma. Sophia: A scalable stochastic second-orde order optimizer for language model pre- training.. arXiv preprint arXiv:2305. 14342, 2023a.
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probability convergence of stochastic gradient methods. In International Conference on Machine Learning, pp. 21884-21914 PMLR, 2023b.
lly Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:/608.03383 2016.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 1rX00:171..0500,, 2017.
Devyani Maladkar, Ruichen Jiang, and Aryan Mokhtari. Convergence analysis of adaptive gradient methods under refined smoothness and noise assumptions. arXiv preprint arXiv:2406. 04592, 2024.
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011.
Lev Muchnik, Sen Pei, Lucas C Parra, Saulo DS Reis, José S Andrade Jr, Shlomo Havlin, and Hermán A Makse. Origins of power-law degree distribution in the heterogeneity of human activity in social networks. Scientific reports, 3(1): 2013.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. In International conference machine learning, pp. 2545-2553, PMLR, 2017.
Arkadi Nemirovski and D Yudin. On cezari's convergence of the steepest descent method for approx- imating saddle point of convex-concave functions. In Soviet Mathematics. Doklady, volume 19, pp. 258 259, 1978.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574- 2009.
Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Phuong_ Ha Nguyen, Lam Nguyen, and Marten van Dijk. Tight dimension independent lower bound the expected convergence rate for diminishing step sizes in sgd. Advances in Neural Information Processing Systems, 32, 2019.
Francesco Orabona. A modern introduction to online learning. arXiv preprint 1rXiv:1912.1321:. 2019.
Francesco Orabona and Dávid Pál. Scale-free algorithms for online linear optimization. In Interna- tional Conference on Algorithmic Learning Theory, pp. 287-301. Springer, 2015.
Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716: 50-69, 2018
Rui Pan, Haishan Ye, and Tong Zhang. Eigeneurve: Optimal learning schedule for sgd quadratic objectives with skewed hessian spectrums. arXiv preprint arXiv:2110.14109, 2021.
Rui Pan, Shizhe Diao, Jianlin Chen, and Tong Zhang. Extremebert: A toolkit for accelerating pretraining of customized bert. arXiv preprint arXiv:2211.17201 2022.
Rui Pan, Yuxing Liu, Xiaoyu Wang, and Tong Zhang. Accelerated convergence of stochastic heavy ball method under anisotropic gradient noise. arXiv preprint 2r2. 2023.
13

---

Published as a conference paper at ICLR 2025
Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao. Understanding gradient clipping in incremental gradient methods. In International Conference on Artificial Intelligence and Statistics, pp. 1504-1512. PMLR. 2021.
Zhaonan Qu, Wenzhi Gao, Oliver Hinder, Yinyu Ye, and Zhengyuan Zhou. Optimal diagonal preconditioning: Theory and practice. arXiv preprini arXiv:2209.000 2022.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv: 100.5647, 2011.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv: 092377, 2019.
Peter Richtárik and Martin Takáč. Parallel coordinate descent methods for big data optimization. Mathematical Programming. 156:433-484, 2016.
Peter Richtárik and Martin Takáe. Stochastic reformulations of lincar systems: algorithms and convergence theory. SIAM Journal on Matrix Analysis and Applications, 41(2):887-524 2020.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476 2016.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pp- 71-79. PMLR, 2013.
Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprini arXiv: 1002.480024 2010.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction -oolooiinnn Ilama model. https://githis com/ tat sa- stanford alpaca] 2023.
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Hugo Touvron, Louis Martin, and Kevin Stone. Llama 2: Open Foundation and Tune-Tuned Chat Models.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. LLaMA: Open and Efficient Foundation Language Models. 2023. doi: 10.48550/ARX1.2202.. 13971. URL Utt.httss:///axa :ttps::///axvvi www.rxiw..wrgg.oooo /200 13971 Publisher: arXiv Version Number: 1.
S Vani and TV Madhusudhana Rao. An experimental approach towards the performance assessment of various optimizers on convolutional neural network. In 2019 3rd international conference on frends electronics and informatics (ICOET), pp. 331-336. IEFE, 2019.
Sharan Vaswani, Issam H Laradji. Frederik Kunstner, Si Yi Meng, Mark Schmidt, and Simon Lacoste- Julien. Adaptive gradient methods converge faster with over-parameterizztion (and you can do line-search). arXiv preprint arXiv:2006.06833 2020.
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. Acm computing surveys (csur), 53(2): 1-33, 2020.
14

---

Published as a conference paper at ICLR 2025
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tie- Yan Liu, and Wei Chen. Provable adaptivity in adam. arXiv preprint arXiv:2208.0990009 2022.
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference Learning Theory, pp. 161-190. PMLR, 2023.
Bohan Wang. Jingwen Fu, Huishuai Zhang. Nanning Zheng, and Wei Chen. Closing the gap between the upper bound and lower bound of adam's iteration complexity. Advances in Neural Information Processing Systems, 36, 2024.
Guanghui Wang, Shiyin Lu, Weiwei Tu, and Lijun Zhang. Sadam: A variant of adam for strongly convex functions. arXiv preprint arXiv: Mww.i/905999999 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Journal of Machine Learning Research, 21(1):9047-9076, 2020.
Stephen J Wright. Coordinate descent algorithms. Mathematical programming, 151(1):3-344 3-34, 2015.
Xiaoxia Wu, Rachel Ward, and Léon Bottou. Wngrad: Learn the learning rate in gradient descent.
arXiv preprint / 008.8003..8833 2018
Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, and Rong Ge. Dissecting hessian: Understanding common structure of hessian in neural networks. arXiv preprint arXiv:2010.04261, 2020.
Hongzhi Yin, Bin Cui, Jing Li, Junjie Yao, and Chen Chen. Challenging the long tail recommendation. arXiv preprint arXiv: 20566700, 2012.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint arxiv: 1708.000.0000 038888, 2017a.
Yang You, Zhao Zhang, C Hsieh, James Demmel, and Kurt Keutzer. 100-epoch imagenet training with alexnet in 24 minutes. arXiv preprint (Sdiv:1709000000 8, 2017b.
Yang You, Zhao Zhang, Cho-Jui Hsieh, James Demmel, and Kurt Keutzer. Imagenet training in minutes. In Proceedings of the 47th International Conference on Parallel Processing, pp. 1-10, 2018.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint urXiv: 2019.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701 2012.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:15511 1-15521, 2020a.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprin! arXiv: 1905. /881, 2019.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33: 15318-115393 2020b.
Tong Zhang. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023. doi: 10.1017/978 10010999777
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, 35: 28386-28399, 2022.
Yushun Zhang, Congliang Chen, Tian Ding, Ziniu Li, Ruoyu Sun, and Zhi Quan Luo. Why trans- formers need adam: A hessian perspective. arXiv preprint arXiv:2402. 16788, 2024.
15

---

Published as a conference paper at ICLR 2025
Ce Zhou, Qian Li, Chen Li, Jun Yu, Yixin Liu, Guangjing Wang. Kai Zhang, Cheng Ji, Qiben Yan, Lifang He, et al. comprehensive survey on pretrained foundation models: A history from bert to chatgpt. arXiv preprint arXiv:2302.0944 2023.
Zhenxun Zhuang, Mingrui Liu, Ashok Cutkosky, and Francesco Orabona. Understanding adamw through proximal methods and scale-freeness. arXiv preprint arXiv:2202.0008) 2022.
George Kingsley Zipf. Human behavior and the principle of least effort: An introduction to human ecology. Ravenio Books, 2016.
A MORE EXPERIMENTAL DETAILS
A.I CONVEX CASE
For a4a, a and a9a, we rum 100 epochs of optimization with SGD and Adagrad individually, start- ing from uniform distribution initialization Wo E U(-0.05 0.05) To find the best hyperparameter, grid searches are conducted for both algorithms, with the search space being initial learning rate y E {10.0, 1.0, 0.1, 0.01} and learning rate schedules being either constant т/ = 7) or inverse square root decay The n/ 7t I, the same choices as in theorems. For large datasets real- salllsan -sim and nevl.binary. all settings stay the same, except for the number of epochs 3 and the initialization Wo (ddddddddd,,... 1/d) 10-2
Since it is generally hard to obtain analytical closed-form solutions for logistic regressions, we run gradient descent for 10 epochs obtain an approximated optimum w, for small datasets a aa, a and a9a. For larger ones real 1-ss-sth isim and rcv1. bi nary, we run 10 epochs of Adagrad instead, since GD converges much slower in comparison. addition, for computing ||H||2 large datasets, we run 10 iterations of power iteration to approximate the largest eigenvalue, which quickly converge desired precisions < 10-5
Table 5: Statistics on logistic regression. D2 max; ||w, - w-ll2 and Doo = max; || - w. oloo estimated by the maximum value under all searched settings without loss explosion. Smaller values in Ovar A D D2 represent better theoretical bounds for Adagrad when compared with SGD, and Chius (I]L]) D/ [|o corresponds to the bias difference.
DATASET
Doo
D2
|L]]
|
OVaR
CHIAS
min; f(w)) f(w.) SGD
ADAGRAD
A4A
9.73
32.24
14.87
7.26
0.30
0.19
1.46 x x10
6.88 x10
x6*
8.88
28.57
14.87
7.26
0.31
0.20
4.36 x x10
6.39 x10
A9A
9.79
29.43
14.87
7.27
0.32
0.23
3.47 x x10-
5.04 x10-5
A.2 NONCONVEX CASE
For all experiments, we run 3 epochs of optimization with SGD and Adagrad, which is one of the recommended settings of the Alpaca dataset (Taori et al. 2023) (nttps://github com/ - htt.:/iiieeeeieeeninnreeeeeee
Eatsu-lab/ stanford
We search the learning rate 77 E (1.0, 10 10 10 3, 1, 10 10 ") and report the best result training loss for both SGD and Adagrad. The maximum sequence length is set to 512, along with the learning rate schedule being set to cosine decay (Loshchilov & Hutter 2016). Other settings remain the same as default ones in huggingface transformers (ht /ttp::///ithii
com/ wwt.cooo..c.aaeeee http:/hggggggccce/////c trans formers). In all our implementations, we use the version t rans wormerororrrrreooooooooorre --.0--4.3 4.38..8... 2. conducted on single A40 GPU, where gradient accumulation is adopted for batch sizes larger than 128 to reduce memory cost.
All experiments
In addition to the presented results, include in Figure the loss curves of SGD and Adagrad under batch sizes 256 and 512. They represent the typical loss decrease tendency all experiments, where Adagrad converges faster than SGD since the beginning, and converges a point with smaller loss.
16

---

Published as a conference paper at ICLR 2025
train/loss
train/loss
SGD Adagrad
SGD Adagred
3
train/global step
train/global step
100
200
300
400
500
600
50
100
150
200
250
300
Figure 2: Training loss curves of SGD and Adagrad for instruction following tasks on Alpaca with GPT2. Left: batch size 256, Right: batch size 512.
Regarding licenses, the Alpaca dataset is released under Creative Commons Attribution- NonCommercial 4.0 International Public License hhttss://githiii com/ humm/tassu-laah stanford aaaaafoor..a.paaaaa///////aaaaaa LICENSE,,,, while GPT-2 is released under MIT Li- cense
The code repository of huggingface 'transformers' is released under Apache License 2.0 (https://gitee com/
co openai-e---... poppenai-coommmitt//ggagaaeaeee
B AN EXAMPLE THE CONVEX CASE
Following the SVM example Duchi et (011 we provide Example B.1 to create concrete case to help our illustration.
Example B.1. Consider finite-sum optimization problem in hypercube W:
f(w) =
(x w),
where o; : R + IR are convex and twice-differentiable functions and x; E Rd w W. We assume that the first and second order derivatives bounded such that (w)] G1 and of (w) s G2 for all i and w E W. We also assume that the data points {x:} yield that
4
Mp.
for 2 1 and denote H = 1/n Di x;X; In this case, stochastic gradient yields that
Vwf(w;;) = X (x(xTW) w),
where is uniformly sampled from m).
Note that Example B.I includes wide range of problems such linear and logistic regression. We can check that the problem Example B.I yields Assumptions of Theorem D.I and 4.1 As the stochastic gradients sampled uniformly with replacement, the variance of gradient noise is reduced by factor M, where M is the batch size, as proven in Lemma C22] We also assume an exponential tail quantify the imbalance of Hessian in following example.
17

---

Published as a conference paper at ICLR 2025
Assumption B.2. We say the problem has an exponential tail when there exists some constants T >> 1/d such that
1 Σ x
H j.j
exp (-rj)
for all j - 1,.. d. where without loss of generality, we assume that H 2 Ha, for all j S k.
Note that the exponential tail is a typical example of highly imbalanced distributions data, which common in natural language modeling Zipf (2016), social networks Muchnik et al. (2013), and recommender systems Yin et al. (2012). Then recall the comparison between AdaGrad and SGD in the convex case:
E [[f(wr) - f(w.)[ = -[w (
Doc || |Lll D&
AdaGrad:
VMT
T
D2 ||
||اا
D3
SGD & AdaGrad-Norm:
E [f((w) f(w.)(
VMT
T
and we take the following ratios to denote the difference in bias and variance terms separately.
Doo |ol||
L
D
R1
R2
A
D2 12 12
L D2
As we take W to be hypercuhe, it holds that D3 = dD
Concerning R1, we have
max ||l||
[x 2 G1M1
WEW
j=1
and similarly,
|| 12 < max
Σ Σ
[x] w)] X2, S G.M2.
WEW
n 1=1 j=1
Therefore, based on the heavy-tailed assumption (Assumption B.2
we can obtain that
o((o) R1 = V Φ(D) = MiDos M1
x Ei= exp
2-)
/ 1 exp (-T)
M2D2 VdM2 VaΣ exp (-Tj)
exp --
Vd
we consider to be a mild constant, should be clear that R₁ can be close to 1/Vd and Rı < 1. On the other side, we have for all W.
1 0 (w) x 3 GzH.
0 ニ 2 f(w)
Moreover, that the diagonal matrix Lm- diagonal (L) satisfies L, 2 G2H a sufficient condition for the smoothness assumption (Assumption 3.3 This is equivalent to that L HL,
1 < 1/G2.
Thus actually Lm can be taken as the optimal solution to an optimization problem:
min LER
|L s.t.
< G2
which shares a similar form with the optimal diagonal preconditioner problem in solving linear systems, where an optimal preconditioner for fixed matrix can result in much faster convergence as pointed out in Qu et al. (2022). As an example, when H is diagonally dominant, we can choose
L, diagonal H) which takes the diagonal entries. Then we have ||[|| 2G H, and
[[]]] 2G2tr (H). In this case, based on the heavy-tailed assumption (Assumption B.2 we have
(L) tr (H) D2
tr (H(H)
1 exp((T)
R2
<
(DD
H1 (H,,
dexp(--fr)
exp (-7) d'
When is mild constant, it should be clear that R2 can be close 1/d and R₂ < 1.
To conclude, in this concrete example, address that R1 can be close 1/vd, R2 be close to 1 1/d and both R, R2 & 1, showing that AdaGrad has better dimensional dependence than SGD and AdaGrad and the larger gap between bias terms than that of variance terms.
18

---

Published as a conference paper at ICLR 2025
C PROOF PRELIMINARIES
Notations. In the appendix, we define
E SEB,
Vw.f(wst - vf(w.) = M
1
Σ n(w:;(
(11)
M
EEB,
to note the gradient noise at iteration 1. We further use Vieij gt.j and n. to denote the j-th coordinate of V (W:)), ge and n,, separately.
Lemma C.1 (Projection). Suppose W S IR is closed convex set and A E IRdxd is symmetric and positive definite Then for w E Rdd w E [T] if and only if for all a E W,
1
1 ||w- w/
w 2
(12)
2
2
or equivalently, for all z E W,
w A(W w)) 0.
(13)
simply follows the definition. To prove 13 take any W and a E (0, we know that oz + (1 a)w E W as W is convex set. Hence by [12), we have
Proof. Equation 12
w w 2
[w - laz + (1 ao)
2
|
w
S 2
[l(w
w) a(z w)ll
2
0
1z
w 1 - a (z w, w,A(w w))
2
w, A(w - w)
21
2
w
2
As a can be arbitrarily close to 0, we have that
13 holds.
With the definition of 11 batch size M.
can obtain the following lemma describing the variance reduced by
Lemma C.2 (Variance reduced by batch size). Under Assumption 3.4
3.5
it holds that
E2
[n S
(14)
M
Proof. It holds that
27
o3
E, 122
=E,
Σ
n2
n,(w;:))
Σ
Er (wr,
M
M
M
SEB.
SEB.
where the second equality is based on the independence of n(w;;
C.1 PROPERTIES OF ASSUMPTION
The following is the descent lemma based on Assumption 5.1 We basically follow similar proof
techniques to Zhang et al. (2019 2020a): Crawshaw et al. (022) but obtain results because of the difference in assumption.
Lemma C.3 (Descent lemma). Under Assumption 5.1 for all w, w' E W such that l| w'll, S
Vd, holds that
f(w') S ((w) + (VS(w), w' -w) Σ
(Lo.i + L1,50, /w' - (15)
J=1
where w' w/, denotes the absolute value of the j-th coordinate of w'
19

---

Published as a conference paper at ICLR 2025
Algorithm 2 SGD
1: Input: wo E RRd {m 1
T-1 E R, and batch size M E N
2: for / 0 to T
3: Sample mini-batch B, with |B, = M uniformly
4: gi = M EEEB, fwe:
5: Option I: W W (We T(gi))
6: Option II: We+1 = Wt m/
7: end for
8: Output: 1/T EE Wt
Algorithm 3 Adagrad-Nomm
Input: Wo Rd mmo E R. e IR, and batch size M E N
2: Initialize v-1 e²
3: for t To do
4: Sample mini-batch B, with |B, = M uniformly
5: g: M EeEr, V (we:()
6: Tt Ut-1 + 1lg:12
7: b. = V
8: Option I: Wi+1 W (w: be
Di g))
9: Option II: Wi+1 = We b, g:
end for
11:
Output: 1/T Wt
Proof. Denote w. = uww + (1 u)w with a E [0, 1]. Based on the Taylor expansion, we have
f(w') (f))=[(W]] =f(]++ S/' (Vf(ww),. w w) du
-f(w) + (Vf(w), w) + S'' (Vf(wa) - -V(())) w' - -w) du
-/(w) + (V/(W), W' - w) + /// Σ (0,s(ww) -0;((-)((w' - -w),du
d
1=1
<f(w) + (Vf(w), w)
10 0r((w))²
Lo.j L1 (0,f(w))) |wo w wldd
Lo.s + L1.j (0)](w)))
f(w) + (Vf(w), w' w) + S'' Σ
(Lo,s + In (0.f(w))) wa wl? du
1=1
=f(w) + (Vf(w), w' w) + Σ (Lo.j + L1 (0,f(w))) w' -wl? L udu
=f(w) + (V) w' w) +
(Lo.j + L1 (w)f(w))) |w' ww
2 1=1
where Cauchy-Schwand inequality in the first inequality.
D STANDARD CONVERGENCE OF SGD
Theorem D.1 (Convex convergence SGD), Under Assumption 3.7 3.3 3.4 3.3 for the sequence
(wr)?= generated by SGD (Algorithm) 2 with option 1), if appropriately take step size t).
20

---

Published as a conference paper at ICLR 2025
M (1
J. it holds that for wT - 1/T E/T 22- We.
minl
L
(
D2 1oll VMT
[ | D2
[[((wT)- f(w.)]
Remark D.2. Here consider decaying step size schedule Te O (1/vi) for SGD, which commonly used and usually more efficient than constant step size. Note that under the same settings, the convex convergence of SGD with the same step size schedule can also depend on just |ww w-ll instead of D2, if we use a slightly different proof approach compared to Theorem D.1 One can refer to Theorem 5.7 in Garrigos & Gower (023) for this different approach. While it can obtain convergence with dependence on Woo- - w. l2 instead of D2, it suffers from an additional logarithmic term in the bound when using step size 7/2 = O (1/v/) (1/v))- Therefore, we think each of these two approaches has its own merits and we take the current approach for discussion.
Theorem D.3 (Nonconvex convergence of SGD), Under Assumption 3.2 3.3 3.4 3.5
for the sequence [w; J===1 generated by SGD (Algorithm 2 with option II), if we appropriately take step size T
1.
7
- L.
it holds that f.
L
(f(wo) f*)
|all2
[ (f(wo) - f*)
| [V
+
V MT
T
Theorem D.1 and D.3 are standard results of the convergence of SGD under [L -mooohh settings.
Similar results have been extensively studied (e.g. (Orabona 2019 Garrigos & Gower 2023 Ghadimi
Lan 2013
Bernstein et al. 2018a). We also include the proof below for completeness.
Proof of Theorem D.I For w. E W, it holds that
E, ||e+1
w. E
W: Te w.
[W,- w. 112 21, E, (gg,, W. w.)l + E
lgg [|
|| w=11 21 (VS(w,), w. w.) + . V
[V((,, TB [1n.11]]]
where n. = -g: (W:::) With convexity and standard smoothness of f(-). we have
(V)(W)) W. w.) 2 f(w)) f(w.) and (Vf(w:), we -w-)= 1
IVf(w)))
D
Then after rearranging, it holds that
(2 - 7) [Ill ((((,) - f(w.)) 1 1/t w.112 10r--w.12. -E,
|wo-
||e+1 - + + ||m012
wal12]
1/t
If we take summation and full expectation with m7s < 1/L and m7 m1+1 for ==rt=1. 1, T, it holds that
B(f(w:) - f(w.)l <
E
ww,
w.112
1
|| -...-w..l.
w.ll2
E
n. 11
1/p
0=
141
E
1
|w:
w.1l2
||
w.1l
Th
||اا|
17
176
M
||
w.1l2
||
w.1l3
E [|w:-wwll
7/7
17-1
||o||
T/
M
21

---

Published as a conference paper at ICLR 2025
D
7-1
T
1/1 o
D2
+
1
1h-1
M
1=1
t=
D
Th
|
2
9--1
M
t=
Therefore, by having both sides of the inequality divided by T and making use of the convexity, we conclude the proof that
E [s(TT) - s(w.)]
Asm.
3.1
Σ
(
D2
T
Σ
T
1---1 T
MT
where Wy 1/T Wt. Then by taking
D3M
min
|L||
[ 1)
where p is a constant, we can obtain that
D3
|0|
1-1
E B[((wr)- - s(w.)] 5
+
Σ Th
1/-
MT
t=
|Illo0
D3
D3 o 2
D o
+
22/2.
T
MT
MT
where the second inequality holds as
T-1
T-1
T-1
v++I Vt
T-1
= 2
t+1-t =2 Σ
Vt + 11+1---110 -2=v11
Vt+1+
VE
1=0
t=
1=U
t=
Thus by taking
2. we finish the proof.
Proof of Theorem D.3 Based on the smoothness condition, it holds that
|L ||
f(W++1) Sf(w)) (V.f(w.), W++1 W.) +
well2
=f(w.) - 7/t (V.((::), )g)) [ 1 Igell2
2
Sf(w:) - T. (V gi) + ||L||
ne
||
|
f(w((w
) 11
||
ne 11
By taking expectation, we have
|L
E [f(w++1)
SI [f
nB
(V g:)]
60
IE
gt
2
||L||
| "i E
[[[[(w))]
E
|12]
EE
f (w.)) )1
[|mm112]]
2
14
| 0o
L 10 T/ ||o
12
EE [f(w.)] E
| (V.((w))l''
JE
[IV
2M
<E[s(w.)]
Th E 2
[VS(()))
LL
oi ||012
2M
where n, Vf(w.)) gi and the last inequality holds as we take me S 1/ [| have after rearranging that
As me 7,
Σ
[IV
2B[s(wo) - s((W)] 1/T
L
00
" 7|
T
M
2(f - 1*)
L
17
O
2
T/
M
Then by taking = min
([ww)) JM
we finish the proof.
[ll...
[L] ... o
22

---

Published as a conference paper at ICLR 2025
E PROOF OF THEOREM 4.1
To prove Theorem 4.1 we first look at the standard AdaGrad convergence under the non-smooth convex stochastic optimization setting,
Theorem E.1 (Convergence for convex nonsmooth AdaGrad). Under Assumption 3.1 3.4 for the sequence {we) generated by Algorithm with constant step size n = 9), it holds that
1
D n
T-1
T-1
c D2 2m
E[f(wa) f(w.) - 17
E
i
(16)
V2
!=U
(=0
Proof. This proof is a stochastic optimization version of the proof of AdaGrad in the online convex
learning scheme Duchi al. (201T); Streeter & McMMhan (2010): Zhang (2023). We also include the proof here for completeness.
First, we give an important result that the gradient norm can be expressed as A. Ar-1-
B 12,
Bi.
X - ur (A, Ac-1); (17)
+
Ars + A-11.
==1
j=1
j=1
where we note Xe, is the j-th coordinate of A,. Then we start the proof.
12
E, || -...-w-l1. 1
E
W: A,A, ge [
E2
| w.1l2. -2n (ge. We -w.) + n/ l|g: A'A!!
E2
W w.11%,]
2n (VS(we), w. -. w.) Ee ni² ||B: 11
w w. w. 11
2n (Vf(w.)) w. w.) Ee [nâtr (A. Ac-
w. w.112 11
217e (f(w)) - f(w.)) + E. [1,tr (A, - -A-1)]]
Ee ||w, w. w.112.-A...
W: w.ll 2n (f(we) - -(W.)-fww.)). E. [1 (A, Ac-1)) E, D tr (A, - Ac-1)],
where the third inequality holds as f()) is convex. After taking 1, summing up, taking full expectation and rearrangement, we can obtain that
T-1
E (f(w)) - f(w.)l S
E
W
W.ll -|We+1 - w.1
21
t=
D2
T-
+
Σ (=0
E [tr (A, - Ar-1)]
2
2m
|Wo-
w. 1I11
WT w.ll2 w
D2
[tr (AT-1
2m
21
2m
DDD
11
D
d Σ j=1
T T-1
+
E
gi
21
2
2m
eD3
D2
T-1
+
V2
E
V Vf2
+
n
2n
2m
1=0
where take A-1 eIa and the last inequality holds / S Vo
/ for all x, 2 0.
for
n
23

---

Published as a conference paper at ICLR 2025
Then consider giving bound on the noise summation term.
Lemma E.2 (variance bound). Under Assumption 3.4 and
3.5
holds that
|
E
n
v MT
1=
Proof. It holds that
d
T
d
T
vT
Σ
Σ
n
S
Ex
M
VM
j=1
/=1
where the first inequality holds as Jensen's inequality.
Then we are ready to prove Theorem
Proof of Theorem 4.1 From Theorem
we can obtain that
T-1
D2
T-1
T-1
D2
Σ
[[[((w))
V
2n
j=1
1=
and in Lemma
E.2
we bound the noise term.
Then we consider the bias term. It holds that
1
T-1
E
E
D
Lg
t=0
t=
T |L||
T-1 Σ
|
[ (w 1-.1)
L
where the first inequality Lemma G.1 and the second inequality holds the Jensen's 's inequality. Moreover, based on the smoothness assumption (Assumption 3.3). we can obtain that
E
[V](w: 12 s [[((w)) - f(w.)].
2T
Thus if we denote expression that
1/T 1=
E (f(w,) - f(w,)( w.)]. }}, then combining [6). there is simplified
A C-CCiVA - -CCo O,
where from Theorem E. and Lemma
D2
|||
Co ||||| + <Di
C
7
G-
V2
T
VMT 2n
Then we can solve this inequality by conducting simple derivation that
V
1
CC [c3
2
1
A < [C + (C + (C
4CC,)
2
C + 2CC.
If we replace C, Co and C₁ by their corresponding value, we can obtain that
T
Σ Bif(w.) f(w.)) < 2
D2
1
D2
| 1l
DD
n
T 1=
17
T
V2
VMT
T/T
If we further take the optimal step size 1) Dax based on this bound, can obtain that
1 T
|||
D2
v2D ||
cD3
Σ E(f(w)) ( (w.))
+
+
T
T
VMT
D
which concludes the proof.
24

---

Published as a conference paper at ICLR 2025
E. RELAXATION OF THE NOISE ASSUMPTION
Note that Assumption 3.5 assumes a universal bound on the noise. However, similar to a line of recent works on SGD Richhtáiik & Takác 2020 Gower al. 2019 2021 Khaled & Richtárik 2020), Theorem 4.1 can also be extended to the settings that we only assume upper bound of noise varaacce on w, as Assumption E.3 with Assumption 3.3 replaced by an assumption that aligns with the expected smoothness (Assumption E.4.. Based on this setting, our analysis can be well adapted to the interpolation or overparameterized scheme.
Assumption E.3 (Anisotropic noise on w.). There exists a positive vector o, = [o.,1..... a. E Rd such that for all w. E W that are minimum of f(-), it holds that
E [n, (wa:()))) - o for all j E [d].
(18)
Assumption E.4 (Expected anisotropic smoothness). There exists positive vector L, [L.,I....,,Ly L. E R4 such that f(-) is L,-expected smooth, namely, for w E W, g(-) is the stochastic gradient oracle and all w. W that are the minimum of f(+), holds that
E [ll(() g(w. (((w.)]..1) s S(w) f(w").
(19)
With these two assumptions replaced, we may rewrite the last step in Theorem E. such that
7-1
d
Σ
E
B?,
j ==1
Σ t=0
E
2lg(w,)) s(w.)))
E 2 2lg(w. )13
t=
2T M
2 L. 11
EE [lg(w.) - B(w.) + ||o.
V
T-1
2T B [[(w)) - S(w.)] 1o-11 V M
4
| 11
Then we can process the proof of Theorem 4.1 the same manner, which gives the following convergence result:
T-1 Σ
|| D3 T
DOo I0
<D²
f(w.) f(w
VMT
DxT
Over-paraeeterized models usually result in interpolation of the data, which typically holds Fwf(w.::) = f((w)= = 0, which corresponds to that or, = 0. Therefore, we have O (1/T) convergence rate for AdaGrad under over-paramtterizatton based on this relaxation of the noise assumption.
F PROOF OF THEOREM 5.3
In this section, we prove the convergence of AdaGrad in the nonconvex generalized smooth setting. Note that by setting L, 0, the proof below be directly applied prove Theorem 4.3 Let us first
give a brief overview. Based on Assumption 3.3 and Lemma C,3 when we set 17t = S 1/ L boo it holds that ||W++1
wellz, S vd and
d (Lays + Lig (eal) | w.l?
f(w(-1) f(w.) + (Vf(W.) Wei1 wi) +
==1
d
(Lo.j + LI,j (esll gis
=f(w.) -7 (V)(w), A,'g)) A, +
2
Ae."
j=1
25

---

Published as a conference paper at ICLR 2025
Here critical problem is it is nontrivial to straightforwardly transfer V.((V B:)l to [.[ V [( [w)ll] as both A, and is relevant with gr. To deal with this issue, we consider an auxiliary diagonal matrix A, with each diagonal entry being
X2 X E, [
(20)
for all j [d]. Note that this auxiliary sequence is the same Défossez (2020), but our proof technique is much different and obtains better results. Then we consider
Be) (V((()),A) Bi) (Vf(we), (A," A, g1
and attempt bound the second term, which is described in Lemma FT
Another problem is how to bound the additional terms introduced by the generalized smoothness, namely, >S Lı V fe.l
si,, Xe,; We use the divide-and-conquee strategy to have this additional term resolved by the existing terms, as described in Lemma R2
With these issues solved, the final convergence property would determined by
T-1 Σ E (
(f..)) A, 8.)
which largely relies on EE [tr (Ae)] that we bound in Lemma F.4 Note that Lemma F.4 considers a different main line and is important for the proof. Then we are ready to complete the proof of Theorem/5.3
Lemma F1 (Bound of (((()), (A,'-A;")
(2')8:)..
B1)).
Under the same setting as Theorem 5.3 if
we take diagonal matrix As as defined in (20). it holds that
Es (VS((w), (A,+ (A5t- A7t) -15--,7) g:) >
gi.j A
20y E.
+
(21)
/=1
Proof. It holds that
(vs(we), (A-1-1,1) g:
d
St.jtt.
1
11
Aes We.
j=1
fun (g%, Es [B%
dejdee (Xenj j + )e.s))
(22)
St.j Braa 88. - Ex, [gg,1]]
Ne.gde. (Xe.s + \e.s)
V Ve |g
|iyl - v Ex (B7,))
de.jde.s
where in the first inequality we take the properties of absolute values. In the last inequality, we use the fact that
X2 2
E,
gi.j 2 E, gg,
and = = gi, 2 gi.
Then we consider an arbitrary coordinate j [d]. By applying inequality 31 with
(1stJl
E
gr.i
E2
[
gr
C
2
No.
26

---

Published as a conference paper at ICLR 2025
it holds that
V Ve,g
[t.j
V
Re
Bi.
Bi.j X
1 V
V
E
E.
+
E2,
|r,
[
de.
2
2c
X
|ttyl
Bx [si,)]
A
Vst.
BL,1
E2,
2
2
X
27
gi.
V
Vfh
Ee
|gr, - V Ee (B..))
E
+
A7
2
2
V
Bi x
20 Ex
2
where in the second inequality use the fact that
( (1Bt))
27
E2
V R. [Bf,]]
2
[i.g]
2
[|g
|l V
Th [B?,]]
2E,
[BT.]]
22
Ex
[s?.]]
V
and the last inequality is based on the fact that
Eg ( [B v Be
27
[B,]]]
21E,
2E,
[|gr,s]]
EE [B7.]]
-2
E2
EE,
[x?,]]
B,, [|
E2
(g
E2. || ||gr.] 11
-2
E2
[Bt.]]
E2
+ E2 [|
E2 [B?..]]
E3 [gt 1
22
E4 18.
E4
[Bt,]]
E. [|gt,]]]
3
2
E2 [ o3
5 20
E, [lBr.il]
Thus by substituting into 22
we can obtain that
E (VVS(w)), (A
A,
gr
EE
V
|g.
V
Ex [
J=1
V V
gi
20 E.
2
j=1
j=l
d
Σ
20
Bi.
(V((w))
AV
2
1=1
which concludes the proof.
Lemma F.2 (Bound of Lı
V
2
Under the same settings as Theorem 5,3
it holds that
d Li
d
E,
V
fe,
gi
< L
(Vf(w)). (V +
L o E,
gi.
(23)
x2
1=1
X
1=1
27

---

Published as a conference paper at ICLR 2025
Proof. Let first consider arbitrary coordinate j E [d] and two regarding /Vayl (1) If ff.l & o, we have
Bi.
Bi.j
Ex L Vftj
LI
fi.j Ex
I L1
o
(2)
Else, we have V fisl 2 j.
this case, we have
Si.j
gi.j
E,
V
2V fi.
E2
E4
S
1-1
+ Bi.j
X +
Eg
[gi.]
X2 11 +
E.
gr.j
N
where we use the Jensen inequality of convex function h(x)
=
-r 02_z
in the first inequality. Therefore,
V
BL
Li V E.
2
V
1
des
where in the last inequality we use the fact that [ftt combining the two cases, we have
E gg. S
E
[BL,]]
S des By
2
Bi.j
Bi.j
LI L Vi E.
2L
L
dejj
X3
and by summing up. have
g
E,
Li Vi
< 2 L
A.
+ > L ,E,
gú,
X
X2.5
z=1
Lemma F.3 (Bound of ET-
g X
Under the same settings of Theorem 5.3 for all j E [d], it holds
tr (AA-1))))
E
< 21
E
(24)
Proof. It holds that
-
Y
A 1 2B
1)
tr 11 ))
E
IE
In
In
2n
E
t=0
where the first inequality based on Lemma G.3 and the fact that X2, X2 + g7, and the second incquality is based on Jensen's 's inequality
Lemma F4 (Bound of tr (A,)). Under the same settings of Theorem 5.3 it holds that
E tr (AT-1)] 2de + (f(wo) -f)
1
(25)
2n |ool, + 5vT ||||| +0)
5 (n + +3VT BVT((o)),)) In
e
28

---

Published as a conference paper at ICLR 2025
Proof. As we take 1) I 1/ || we have || -Well, S Vdd. Then from Assumption 3.3 and
Lemma C.3 it holds that
15
d
f(We+1) f(w.) + (Vf(w.), -wa) +
(Lo.5 + L1. (i,g)) We+1 wel3
2
j=1
112
d
Bin
=f(w)) - 17 (V)(w)). 8/)) +
(Lo.s + L1 (Vees))
2
X3,
.=1
1
Bi.
-f(w:) - 17 (Bc. A,'8:)
Σ
(Lo.) + L1 fe,l)
+ 1] (ne, Ai)
X2.
j=1
1/2
Bis
<f(w.) - 17 (BL, A, A,'::)
(Lo.j + [1 + |mاm))))
+ 17 (nee (n, A()
X2.1
j=l
=f(w.) - 17 (Br. A, 81)
+
1
2
2
Lo,d
BL.
X2
2 ,=1
2
L
1,5
g
X
j=1
112 d + Σ
| |
grd
2
+ [n, A, B1)
2 3=1
X2
s/(W,) - 11 (Bri Ar 1 (8)
+ 11
Load
17¹ Σ
L1
gr
2
X
j=l
j=1
112
Σ ااا |
g
Dr.
X
Ae.j
j=1
j=1
where we use absolute value inequality. Then we deal with the terms separately by
122
g
gt.
3
S
Bi.
n2 |
(Be,
AT'Bi)
X2.3
2
X2
2
Ae.
2
j=1
j=1
5 gt A, 1 Bt)
where we use the fact that |g,ي S Xe. and 1) S 1/ [1ll,o-
Similarly, we can also obtain that
2 d
gi X2,
17.
2
|
17
L
Dt.j
Lis ney
2
2
At.j
2
Ao.5
j=1
j=1
where we use the fact that |g:u| S Ae.i and 1 S 1/ 1/I|Lilloo By combining the bounds of the two terms, we can obtain that
f(we)s f(we1) S f(w)) - " 2 A8 (i)) + 172 d
2 j=1
Lo.j
X2
gi.
37
2
Σ
d
n
|
A
j=1
Then after summation in and rearrangement, it holds that
2 (g: A, 81) s Σ (f(w)) - f(W++))+
T-1
2 d 2
Lo.j
T-1
gi.j N1.
31
d
T-1 1
n
gg
2
1=0
j=1
t=0
1=1
1=
7
d
T-1
3
T-1
T-1
1
g
2
<f(wo) - f(Wr) + Lo.j
2
2
y=1
1=0
1=0
29

---

Published as a conference paper at ICLR 2025
where in the last inequality we use
Inequality. Moreover, it holds that gi
T-1 (B,
d T-1
gi.j
d T-1
T-1 X X² 1
Bi)
Xu.j
X1,5 A--15
A + Ac-1.
j=1
j=1
(ee - )
tr (AT-1 A-1);
where A-1 = eLg. Then by combining the two inequalities together with Lemma F3 and taking expectation, obtain that
2 E (Ar Str (A-1) + [[]((w)) - f(wr)] + 27
Lo.
E
17
j=1
d
T-1
T-1
2
+3 3
E
m
X
j=1
24
d
tr
(1T
de + B[s(wo) s(wr)] + 27)
Lo,
In
E
/=1
d
T-1
T-1
I Σ 1=0
gid
2
+3 Σ E
Σ
2 .j
X2
j=1
<d + B[s(wo)
S(WT)] + 21) Σ
d
Lo. In
E
tr
(AT-1)
1=1
d
T-1
T 1
gi
+3 3 Σ
E
Σ
n
X
j=1
1=0
1=0
24
tr (AT-1)
de + ((oo) S(WT)] + 21
Lo. In
E
tr (AT-1)
333T ||011 V
2E In
e
[or
E tr (Ar-1)
<de + 2 BB(s(wo)- ([((W))))ww]]) + [2 + 5VT [|all.) In
where the second inequality is based on the Jensen inequality and the third inequality is based on the Cauchy-Schware inequality. Then by taking
Eltr (AT-1)l
2n Loll + 5 ||
de + [[((w)) - f(Wr)]
C
and Co
in Lemma G.4 and using Assumption 3.2
we can obtain that
[r (A)-1)) <dde + ([(ww) - (r)
2n Loll, + +5VT |0011 +e
+ 2n Lolh + +5TT|(0T)) In
which concludes the proof.
Then ready prove Theorem 5.3
30

---

Published as a conference paper at ICLR 2025
Proof of Theorem 5.3 As we take 17 I 1/ || we have ||we+1 wellz, Vd. Then from
Assumption 3.3 and Lemma C.3 it holds that
f(w(-1) (wa) (Vf(w)) W4+1 wee
Σ
(Lu + Li (fel)) [We41 wal?
j=1
"
d
gij
((ww:)nn<vil A, Bi)
+
Σ
(Lo.s + L1 (&ee))
2
X2
j=1
Then by taking expectation and summation on we can obtain that
11 +
(l(((w(1))) )
Σ
f(w)))
7
Σ
E,
(Vf(())) AF Bi)]
Lo.j
E,
2
1=
t=0
1/
Bi.j
+
V ft. E
2 j=1
X
28
T
f(w:) 1
E, (( (Vf((,)) ). 4- |/)g
+
118
Σ
d
Lo.3
T-1
E
gr.
2
1
j=1
1=0
+ n² |اااا
(V
E2
1=U
(26)
We first consider the second term on the right hand side of 26 It holds that
Σ (V A,
( (V(())) Ar'g/ )
[( (Vf((w)), (A,'-AA - A1,1) 8:)
E
T-1 d
(Vf(()) A f.'s:)l + Σ
g
E
20 E
t=0
(=0
Therefore, after substituting the incquality and (24p into 26) and setting 1) S
we have
Σ
(Vf(()). A.' 1:)]
4 = - f(wr) + (12 ||a|| + | [Loll In
E
(tr (AT-))3)
E
1=0
(27)
Moreover, for the left hand side of 27 we have
[V A. 8:) }:)] -E ( (VS((.))
A. [
= Σe E
V fe.
j=1
[ x2 1.
+ Ee
[gr.)]
V Veal 1
E
X2 1s + Vf,, + +o²
d
V
2
22 - + ΣT- 1 f22 +
3=1
31

---

Published as a conference paper at ICLR 2025
Thus by taking summation have
Vi 2
Σ E ( A, 8i)|
Σ Σ
E
\ 1 + Ex=o V + 0
1 1=0
Σi=o /
E
\7 - Σn=
V
E
Et V
(28)
ErT V vsz +
j=1
E
Σi=1 El=o fc, ?
V + E + +o
where in the second last and last inequality we apply Cauchy- inequality
B| < E
[ E
[M]]}
1 and Σ 1X, S
Σ
x²
Σ j= 1
Y
We can further deal with the denominator such that for all j E [d].
T-1
T-1 1
T-1
E
X2
15 +
Σ
V
to²
SE
S.
+
V f22 +o²
==0
==0
-E
+ E
Σ (B&) ns.5) 2
T-1 1 Σ ==0
T-1
ΣE
g
+
Σ 2g + 2n +o²
x=0
T
T-1 Σ ==0
<3E
2 8N.
+
2n to
N
==0
T
5
3E
+ / 10,
3E [r. + VT VT lo,
(29)
where the first and the third inequality holds va 6b+b5 S Vo + vbb for b 0 and the second
incquality holds as (a + b)² < 2a² + 252 for a, b R. Therefore, with Lemma F.1 bounding tr (A:).
combining 27 with 28 and (29) can obtain that
E
V st 2
d
T-1
E
v22 +
J
1=1
==0
32

---

Published as a conference paper at ICLR 2025
(tr (AI-1)
- [(wT)) + (12 |||||| + 2n [Iool,)
E
3R [tr (AT-1)] + VT + |
(tr (AI-1) 11)
[ls((w) - f(wT)] |||||| + 2nj ||Lolli) In
30B(n) 6dc + +VV (4B(n) 12V),
where denote
1 (f(wo) 5*) + Clog: B(n)
V V=1lo11 Glog
27
and
Clog = In
2dc (f(wo) ff"
17
2m | 5 |oll +e ))
+ 2m) Loll + 55 (1vlll In
=0 (logT)
based on Lemma F.4 By taking 1 = min
Loll A
where A - f(wo) - f", we can
obtain that
B(n) = ( (VILoll A [Lelbo 2).
Then combining the fact proven Lemma G.5 that
T
Σ
V
Vf(w,)
t=
and dividing T in both side, we obtain that
Lo A
o 1
|Loll
A
E
Σ
[VS(W)))
=6
VMT
MVT
T
LL
A A|00|
L
1
A2
+
VMT
T
de
+
| 1oc
A)
de ||al|]
+
T
VMT
which concludes the proof.
G
USEFUL LEMMAS
Lemma G.1 useful inequality). Assume a non-negative sequence {0,}7=1 and a positive sequence {sy 1 with Σn= Sj, holds that
1
(30)
$
8j
j=1
The inequality holds as an equality if and only if for all 1, n and j = 1,...
E
8j
33

---

Published as a conference paper at ICLR 2025
Proof. We first multiply S by both sides and take the square, then the right- hand side minus the left-hand side will be
S
81
3
Ijj
Jz
Sj
8j
j=l
j=
i=1
j=1
1=1
2
Σ
$j
jfi
{j
2
xz 0
84
which concludes the proof. Note that this result is an application of the
incquality.
Lemma G.2 (A basic inequality). For 0 and x. y
R. it holds that
1 2
rx 2
500 +
(31)
2c
Lemma G.3 (sum of ratios with the denominator being the sum of past numerators). Assume non-negative sequence (an) and e >> O. We define bn =i= ag. Then holds that
N
Ot
bN + :x++)
S In
(32)
b +
1=1
Proof. It holds that
at
ax
< - In
b. +
c by
=ln(b, + 6) - In(h, ag +
= In(( e) In(bi-1 1 + e);
where the inequality is based on the fact that æ S In(1 + x) for x > -1 and we set by
Then
by summing up for 1 to N we finish the proof.
Lemma G.4 (Solving inequality x S Co + C₁ In Assume C₁ 2 Co > 0 and x > 0. If Co Cj In (where In denotes the natural logarithm), holds that for C 2 5,
x S 2Co + CCi InCi +e).
(33)
Proof. Denote g(z)= x In Co. Then have g convex function and attains uniform lower bound at Cj. For x 2 C1 is a monotonically increasing function. Therefore, to verify (33). it is equivalent to verify that if 20, (Ci In(Ci + e), where ( = then Co C₁ In We begin the verification then.
Denote
2C, + {C₁ In(C e). Then we have
z - (Co + C2 In 2) = (Co + C In (2C + In
22 - Co + ž 20, + C (4C
=G InIn +)) In In(2 +e)))
where the second inequality is based on the fact that
C₁ In (2Co + CCi In(Ci + e)) S Co - C, InCC +
for Co 2 0 and Ç 2 2. Then let consider function h(y) Cnn + e) In (Sy In + e)) for
y 2 0 and we have h(1) 2 O. We also have
Cyln(y+ +e) (<in(y+ e)) +
1
S 1 yte) te y (y+ e) In(y +
Sy
h' h'(y) y te e
34

---

Published as a conference paper at ICLR 2025
which implies that y 1, we have (1) 2 0 and thus h(y)
0 for 2 1. For y E (0. it is
also straightforward to obtain that hyy 2 < - In(5 In + e)) I
Therefore, we conclude that
h(y) 0. By substituting C1, we have
(Co C1 In 2) 2 0
and thus x v Co + C1 æ implies x S z, which finishes the proof.
Lemma G.5 (comparison of measures). For sequence {at.)} with I,... T and j = 1, I,.. d, holds that
2
d
d
at,
(34)
Proof. It holds that
2
T
2
1=1
t=
Σ
a
ortc ar.jzl
t=1
T
11,2
Jr.ji utaia
Vji + j2.
The last inequality follows from the Cauchy-Schward Inequality. Thus we finish the proof.
35


Reviews:
[{"review_id": "d5QzNsnZaj", "reviewer": "Reviewer_FCcu", "summary": "This paper provides a detailed analysis of the AdaGrad optimization algorithm under anisotropic smoothness assumptions, addressing gaps in theoretical convergence for large-scale tasks. It introduces a new anisotropic smoothness framework that better explains AdaGrad’s convergence speed, especially for large-batch training. Experiments on logistic regression and GPT-2 fine-tuning support these theoretical claims, showing AdaGrad’s improved performance over SGD.", "questions": "Can please you better compare to Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions - D Maladkar, R Jiang, A Mokhtari - arXiv preprint arXiv:2406.04592, 2024?\nAlso, is much work required to generalize to Adam?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strength lies in its novel anisotropic assumptions, which align well with AdaGrad’s observed performance in high-dimensional settings. The experiments effectively validate the theoretical benefits, highlighting AdaGrad’s adaptability to large batch sizes and diverse data structures. For the rest it is a standard optimization analysis.", "weaknesses": "This kind of work always relies on assumptions which limits their applicability to the setting of interests, as neural networks. However, this is common and not really an issue. See also questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mRJqtN6Ejc", "reviewer": "Reviewer_zDPR", "summary": "The work provide analysis result for the convergence of Adagrad for training of machine learning models with large batch size, emphasizing the effects of anisotropic smoothness. The authors then compare the results with similar results for SGD and Adagrad-norm and point out the potential of Adagrad. In general, the work can be helpful to under stand the training process.", "questions": "1. Convexity is used in a large part of the paper. In many machine learning models, there are more parameters than data. In this case, local minima w* may not be isolated points. Instead, it can be a manifold. What is the impact of overparametrization to the results in this work?\n\n2. In Table 2, the authors list the coefficients and norms in the analytical results. It is also important to see how well the convergence of the loss (or gradients) are controlled by these coefficients and norms.\n\n3. For Table 4, since the work mainly discusses the convergence rate of Adagrad, it is better to show how the loss converges and how do the  authors select hyperparameters.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The work provides an analysis result which may be the first one for Adagrad. This can be helpful for others to understand the potential of Adagrad and select optimizers for training tasks.", "weaknesses": "The numerical results are not sufficient to verify the assumptions and analytic results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tzg940bfS7", "reviewer": "Reviewer_14gU", "summary": "This paper studies the convergence of Adagrad under anisotropic smoothness conditions. The main contributions are:\n1. Defining the anisotropic smoothness condition.\n2. Studying the convergence of Adagrad for convex and nonconvex problem under the anisotropic condition.\n3. Further nonconvex results for relaxed smoothness conditions. \n\nStrength:\n\nI think the paper is presented in a very clean and organized manner. The key results and discussions are clear. \n\nUp to my knowledge, although anisotropic smoothness were hinted across different setups, there is no very systematic study prior to this work. Therefore, I think the results here can be a valid contribution to optimization theory.\n\nWeakness:\n\n-The results are not surprising, and hence I didn't find the analysis / statements to be novel.\n\n\n-In addition to reviewing adagrad analyses, it would be helpful to review anisotropic analysis. Several related works that I could think of : analysis on coordinate descent;  Nesterov's study on zero-order methods; adagrad's advantage on sparse gradients; Adam's convergence on infinity norm rather than l2 norm of gradients, etc.\n\nAlthough, the above results probably are not directly comparable, it would be good to summarize and discuss the differences.\n\nSome results that can make the work more impressive are listed below:\n\n-Lower bounds to justify when and why adaptive step,  diagonal / full matrix adaptivity are sufficient / insufficient would be very interesting. \n\n-Given the analysis, can faster methods be proposed for neural nets?", "questions": "See summary", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "See summary", "weaknesses": "See summary", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "asV82XlXbu", "reviewer": "Reviewer_JNL4", "summary": "This paper analyzed the convergence rate of AdaGrad, showing that AdaGrad converges faster than SGD with respect to the dimension of parameters.", "questions": "See the weakness section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper analyzed the convergence rate of AdaGrad. Then, it showed that the convergence rate of SGD depends on $D_{\\infty}$, while the rate of AdaGrad depends on $D_2$. $D_2$ depends on the dimension of parameters, while $D_{\\infty}$ does not. Thus, this paper claimed that AdaGrad converges faster than SGD.", "weaknesses": "1. The authors compared the convergence rate of AdaGrad in Theorem 4.1 and the convergence rate of SGD, Eq. (6). The convergence rate in Eq. (6) depends on $D_2$, while the tighter convergence rate that depends on only $\\| x_0 - x^\\star\\|$ was more common. \n\n2. $D_\\infty$ does not depend on the dimension of the parameter. However, it is unclear whether $D_\\infty$ is smaller than  $\\| x_0 - x^\\star\\|$.\n\n2. Theorem 4.1 assumes that $L_1 = 0$, which sounds a bit strong assumption. The reviewer feels that it would be better to provide the intuition why this assumption is necessary, at least in the Appendix.\n\n2. It was confusing which term corresponds to \"bias term\" in line 272.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)