On the Convergence of AdaGrad(Norm) on $\mathbb{R}^d$: Beyond Convexity, Non-Asymptotic Rate and Acceleration
Authors: Zijian Liu
Ta Duy Nguyen
Alina Ene
Huy Nguyen
Venue: ICLR 2023 poster (2023)
Keywords: Convex Optimization
Adaptive Algorithms

Abstract: Existing analysis of AdaGrad and other adaptive methods for smooth convex optimization is typically for functions with bounded domain diameter. In unconstrained problems, previous works guarantee an asymptotic convergence rate without an explicit constant factor that holds true for the entire function class. Furthermore, in the stochastic setting, only a modified version of AdaGrad, different from the one commonly used in practice, in which the latest gradient is not used to update the stepsize, has been analyzed. Our paper aims at bridging these gaps and developing a deeper understanding of AdaGrad and its variants in the standard setting of smooth convex functions as well as the more general setting of quasar convex functions. First, we demonstrate new techniques to explicitly bound the convergence rate of the vanilla AdaGrad for unconstrained problems in both deterministic and stochastic settings. Second, we propose a variant of AdaGrad for which we can show the convergence of the last iterate, instead of the average iterate. Finally, we give new accelerated adaptive algorithms and their convergence guarantee in the deterministic setting with explicit dependency on the problem parameters, improving upon the asymptotic rate shown in previous works. 

Published as a conference paper at ICLR 2023
ON THE CONVERGENCE OF ADAGRAD(NORM) ON R4: BEYOND CONVEXITY, NON-ASYMPTOTIC RATE AND ACCELERATION
Zijian Liu"
Ta Duy Nguyen' & Alina Ene Boston University
Huy L. Nguyen
New York University 21306 133660nyu.ccmm edu
Northeastern University hu. nouycnnnort www.:e/wttttttttttteeeeeome cdu
( (taduy, aono) cdu
ABSTRACT
Existing analysis of AdaGrad and other adaptive methods for smooth convex optimization is typically for functions with bounded domain diameter. In un- constrained problems, previous works guarantee an asymptotic convergence rate without an explicit constant factor that holds true for the entire function class. Fur- thermore, the stochastic setting, only modified version of AdaGrad, different from the one commonly used in practice, in which the latest gradient is not used to update the stepsize, has been analyzed. Our paper aims bridging these gaps and developing a deeper understanding of AdaGrad and its variants in the standard setting of smooth convex functions as well as the more general setting of quasar convex functions. First, we demonstrate new techniques to explicitly bound the convergence rate of the vanilla AdaGrad for unconstrained problems in both de- terministic and stochastic settings. Second, propose variant of AdaGrad for which we can show the convergence of the last iterate, instead of the average it- erate. Finally, give new accelerated adaptive algorithms and their convergence guarantee in the deterministic setting with explicit dependency on the problem parameters, improving upon the asymptotic rate shown in previous works.
INTRODUCTION
In recent years, the prevalence of machine learning models has motivated the development of new optimization tools, among which adaptive methods such as Adam (Kingma & Ba 2014), AmsGrad (Reddi et al. 2018)), AdaGrad (Duchi et al. (011]) emerge as the most important class of algorithms. These methods do not require the knowledge of the problem parameters when setting the stepsize as traditional methods like SGD, while still showing robust performances in many ML tasks.
However, it remains challenge to analyze and understand the properties of these methods. Take AdaGrad and its variants for example. In its vanilla scalar form, also known as AdaGradNorm, the step size is set using the cumulative sum of the gradient norm of all iterates far. The work of Ward et al. (2020) has shown the convergence of this algorithm for non-convex funtions by bound- ing the decay of the gradient norms. However, in convex optimization, usually we require stronger the function value gap. This is where we lack theoretical under- standing. Even in the deterministic setting, most existing works (Levy 2017 | Levy al. 2018 Ene et al. 202T) rely on the assumption that the domain of the function is bounded. The dependence on the domain diameter can become an issue if it unknown or cannot be readily estimated. Other works for unconstrained problems (Antonakopoulos et al.) 2020 2022) offer a convergence rate that depends on the limit of the step size sequence. This limit is shown to exist for each function, but without explicit value, and more importantly, it is not shown to be a constant for the entire func- tion class. This means that these methods essentially do not tell us how fast the algorithm converges in the worst case. Another work by Ene & Nguyen (2022) gives explicit rate of convergence for the entire class but requires the strong assumption that the gradients are bounded even in the smooth setting and the convergence guarantee has additional error terms depending on this bound.
convergence diterion-bbundee
"Equal contribution, corresponding authors.

---

Published as a conference paper at ICLR 2023
In the stochastic setting, common approach is to analyze modified version of AdaGrad with off-by-one step size, i.c. the gradient at the current time step is not taken into account when setting the new step size. This is where the gap between theory and practice exists.
1.1 OUR CONTRIBUTION
In this paper, we make the following contributions. First, demonstrate method to show an explicit non-asmmptotic convergence rate of AdaGradNorm and AdaGrad on Rd in the deterministic setting. Our method extends to more general function class known as 7-quasar convex functions with a weaker condition for smoothness. To the best of our knowledge, we are the first to prove this result. Second, we present new techniques analyze stochastic AdaGradNorm and offer an explicit convergence guarantee for 7-quasar convex optimization on IR with mild assumption on the noise of the gradient estimates. We propose two new variants of AdaGradNorm which demonstrate the convergence of the last iterate instead of the average iterate as shown in AdaGradNorm. Finally, we propose a new accelerated algorithm with two variants and show their non-asymptotic convergence rate in the deterministic setting.
1.2 RELATED WORK
Adaptive methods There has been a long line of works on adaptive methods, including AdaGrad
(Duchi et al. 201T). RMSProp (Tieleman al., 2012) and Adam (Kingma & Ba, 2014). AdaGrad
was first designed for stochastic online optimization; subsequent works (Levy) 2017; Kavis et al.,
2019 Bach & Levy| 2019; Antonakopoolos et al. 2020 Ene et al. 2021) analyzed AdaGrad and
various adaptive algorithms for convex optimization and generalized them for variational inequality problems. These works commonly assume that the optimization problem is contrained in a set with bounded diameter. [ & Orabona (2019) are the first analyze variant of AdaGrad for unbounded domains where the latest gradient is not used to construct the step size, which differs from the standard version of AdaGrad commonly used in practice. However, the algorithm and analysis of Li & Orabona (2019) set the initial step size based on the smoothness parameter and thus they do not adapt to it. Other works provide convergence guarantees for adaptive methods for unbounded domains, yet without explicit dependency on the problem parameters (Antonakopoulos et al.. 2020
).22). 1. or for a class of strongly convex functions (Xie et al., 2020). Another work by Ene & Nguyen (0222) requires the strong assumption that the gradients are bounded even for smooth functions and the convergence guarantee has additional error terms depending on the gradient upperbound. Our work analyzes the standard version of AdaGrad for unconstrained and general convex problems and shows explicit convergence rate in both the deterministic and stochastic setting.
Accelerated adaptive methods have been designed to achieve O(1/I²) and O(I/VT) respectively in the deterministic and stochastic setting in the works of Levy et al. (2018) Ene & Nguyen (2022); Antonakopoulos et al.] (022).. We show different variants and demonstrate the same but explicit
accelerated convergence rate in the deterministic setting for unconstrained problems.
Analysis beyond convexity The convergence of some variants of AdaGrad has been established for nonconvex functions in the work of & Orabonal (2019); Ward et al. (2020); Faw et al. (2022) under various assumptions. Other works (Li & Orabona, 2020 Kavis et al. 2022 demonstrate the convergence with high probability. We refer the reader Faw et al. (2022) for more detailed survey on AdaGrad-style methods for nonconvex optimization. In general, the criterion used to study these convergence rates is the gradient norm of the function, which is weaker than the function value gap normally used in the study of convex functions. In comparison, we study the convergence of AdaGrad via the function value gap for broader notion of convexity, known as quasar-convexity, as well more generalized definition of smoothness.
2 PRELIMINARIES
We consider the following optimization problem: minimizenegd F(z),, where F is differentiable satisfying F* = inf zEz= F(x) > -co and x- arg min F(x) # 0. We will use the following notations throughout the paper: at = max {a, 0}. a V = max {a, b). [n] = (1,2,--.,)) nn) and || || denotes the no-nr ||. ||2 for simplicity.
2

---

Published as a conference paper at ICLR 2023
Algorithm AdaGradNorm
Algorithm Stochastic AdaGradNorm
Initialize: 21, > 0
Initialize: 21,
for to
for to
b. V b/ Ei= (VF())) 2 = Zt VV,)())
6, V b8 Ei=1 [F;();
2+41 24 |V(=))]
Additionally, we list below the assumptions that will be used in the paper.
1. y-quasar convexity: There exists > (0, 1] such that F* 2 (V
Rd
where x" aig F F()). When y 1, also known as star-convex.
P. Convexity: F' is convex. This stronger assumption implies that Assumption I holds with = 1.
Weak L-smoothness: 3L such that F(x) F /F Ya Rd.
5 yl1 Vr, E R 2". L-smoothness: EL diag (Lie(1) with L, > 0 such that F(x) S F F(y) (VF v) +
2'. L-smoothness: 3L 0 such that F(x) s F(y) (1)
|| - vll2. Vr, E Rdd where |a]l / (a, La).
In the stochastic setting, assume that have access to stochastic gradient oracle F(r) that independent of the history of the randommess and it satisfies the following assumptions:
3. Unbiased gradient estimate: =[VF(=))= =
Sub-Weibul noise: E EXp (VFF()))V((()))))))))) S exp(1) for some 0 > 0.
Here, give brief discussion of our assumptions. Assumption 1 is introduced by Hinder et al. (2020) and it is strictly weaker than Assumption 1'. Assumption is a relaxation Assumption 2 the latter is the standard definition of smoothness used in many existing works (see (uuille-scuuret et al. (2021) for a detailed comparison between different smoothness conditions). Assumption 2" used analyze the AdaGrad algorithm which uses per-coordinate step sizes. Assumption is a standard assumption in stochastic optimization problems. Assumption is more general and encapsulates sub- Gabssinn (# 1/2, used Li & Orabonal (2019)) and sub-exponential noise
(0 = 1). We refer the reader to Vladimirova et al. (2020) for more discussion on sub- Weibull noise.
3 CONVERGENCE OF ADAGRADNORM ON Rd UNDER QUAUARR CONVEXITY
We first turn our attention to AdaGradNorm (Algorithm in the deterministic setting, which will serve as the basis for the understanding Stochastic AdaGradNorm (Algorithm 2 and determin- istic AdaGrad (Algorithm 7). To the best of our knowledge, convergence rate these three algorithms on Rd. Due to the space limit, we defer the theorem of the convergence guarantee of AdaGrad and its proof to Section A.3 in the appendix.
are the first to present the explict
3.1 ADAGRADNORM
Previous analysis of AdaGradNorm often aims at bounding the gradient norm of smooth nonconvex functions, conducted for smooth convex functions in constrained problems with bounded domain. Bounding the gradient norm is strictly weaker than bounding the function value gap due the fact that [|v](= < 2L(((z) F*). where L is the smoothness parameter. For convex functions, the common analysis will always meet the following intermediate step
b
F(x:) - F <
|
10 || - x [1] + Other terms.
2m
Assuming bounded domain is way making the terms scope after taking the sum over all iterations L. This is critical in the analysis, but the same
by [llar x11 || I=]] tele- 2n
3

---

Published as a conference paper at ICLR 2023
time leads the dependence the domain diameter, which can be hard to estimate. For un- constrained problems, a natural approach is to divide the terms by br, so that the remaining terms by [||e, - 2- 1|2 | x= ==]]²] can telescope. Our key insight is that we can bound the function value gap via the step size be. which in turn can be bounded via the function value gap. This self- bounding argument allows us to finally prove the convergence rate. This result holds under more general conditions than convexity and smoothness (Assumptions and 2).
Theorem 3.1. With Assumptions and 2, AdaGradNorm admits
Eie F(r.) T
2L [ -x' 11?
+ 4nL log"
2nL
+ bo)
[1ar] [|=)=x""|*
2n log" 7
27L 700
79
7bu
7177
T
Proof. Starting from the ququaa convexity of F, we have
(VF(xt), 2z x²)
bt
F(x,) - F <
(xx - 11+1, 1, x²))
mm
[||, - x x²112
1|-1411 - x² + ||a0e+1 - xxe1=
2ym
Notice that J4+1 - Dt -nb; FF(xt). Dividing both sides by by and taking the sum over we obtain
F F(xr) F
|0] x011
y /F(x)))1
be
2711
2-bz
1=1
Note that F also satisfies Assumption 2, i.e., F(x:)) - F > [VF(
Therefore
F(x:) - F
|FF(11]
F(xt)
F
[1]
x=11
[F(x:)]
2b
4Tb;
bt
2-y11
270;
T
F( F*
x+1l"
T
n
1
[VF(2;)]1
b
2Lb
We can bound the term A by the technique commonly used the analysis of adaptive methods. Let
T the last such that by S 24L
If b,
>
20L
we have <
S
2q
log"
+
2nL Otherwise
ybu
1
b
63
7
b2
2n
log + 2
A
log
-
2
2Lb
6
62_
ybu
t=1
1=1
Thus we always have A <
2n
log"
2rL. ybu
and obtain
7
T
F
(xt)
F
11
x=
1|2
+
27
log" +
2nL
by
?
7b0
which gives
T Σ
||0] - -
2n
+ 20L
F(xe) - F* br
log
7177
?
ybu
1=1
Note that by Assumption again, we have
T 63 Σ
by = 63
VF(2))12 =
2L (F(x)) - F²).
1=1
t=1
Let AT ΣT, F(xx)- - F=, then
AT 5 /B3 + 2LAT
||:1 - 122
2n log
2
Tho
+ Ar |2 x²1
4nL log
2
||:01 - x21
2n
2
+ bo
+
log
?m
Ybo
777
?
ybu
Dividing both sides by T. we get the desired result.
4

---

Published as a conference paper at ICLR 2023
When F is convex (which implies ? 1). using the above theorem and convexity, obtain the following convergence rate for the average iterate:
Corollary 3.2. With Assumptions I' and 2, for Fr Eim!" AddGGrdNorm admits
[2 1'11i-=x'1" 4n log" 20L bu)
ar [ai-x" I12 +
log
2 bn
F(TT) F
4
The rate Theorem 3.1 can improved by a factor 1/4r by replacing Assumption 2 by 2'. The details and the proof deferred into Section A. in the appendix.
3.2 STOCHASTIC ADAGRADNORM
In this section, we consider the stochastic setting where we only have access to an unbiased gradient estimate (xx,) of V (zz)) (Assumption 3). As expected for stochastic method, the accumulation of noise is the reason that we can only expect an O(1vVT) convergence rate, instead of O(1 (() This convergence rate is already shown by prior works (Lev et al. 2018) under the bounded do- main assumption. However, in unbounded domain, when extending our previous analysis to the stochastic setting, that is, dividing both sides by bt, we will face several challenges. One of such is Face), - xx). To handle this term, often we see that existing works, such Li & Orabona 2019), analyze modified version of Stochastic AdaGradNorm with off-by-
the term (VF
one stepsize, i.c., b = / 69 E [[;)(=;)] in which the latest gradient F is not used to calculate b. This allows to decouple the dependency of b, on the randomness at time t, thus in expectation (VF,
F((x)), 2t - x²)] = 0. Yet, this analysis does not apply to the standard algorithm which more commonly used in practice.
To the best of our knowledge, we are the first to propose a new technique that can show the con- vergence Algorithm 2 on IR without going through the off-by-one stepsize. Here, we briefly compared the assumptions in our analysis with the assumptions in Li & Orabona (2019). Assump- tions 2' and 3 used in both works are standard. Meanwhile, Assumptions (y-quasar convexity) and 4 (sub-War Weibull noise) in analysis much weaker than the convexity and sub-Gaussian noise assumptions in Li & Orabona (2019). Besides, we note that, while the guarantee in Li
& Orabona 2019 is bound on E E[V (E F(x.) - F(x*))/T we will present bound for E EE F(x,) F(I"))/T), which is stronger criterion that is often used in convex analysis. We also remark that the algorithm and analysis Li & Orabona (2019) still require the smoothness parameter to set the initial stepsize, thus their method is not fully adaptive.
The first observation is that, if let & = F(x)) F(r.) be the stochastic error and My max [r] & 212, My is bounded by o² logg" ex' with probability at least Appendix A). which can give a high probability bound on by.
(c.f. Lemma A.4
Lemma 3.3. Suppose F satisfies Assumptions 2' and 4, if Mr S 0² log
eT then 5
4g by 2bg + 4(F(x1) - F*) 4nLlog" bu N
n
Tlog 20 eT
oT 16. log
log 1+
0
17
8
Lemma 3.3 gives us an insight: b, = Ō(1 + / tlog t). Note that this can be expected since we know the classic choice the step size for SGD is of the order of O(1 + ovt). Hence, are willing accept extra log terms in the convergence guarantee, the appearance of log b, is accommodatable. Next we will introduce our novel technique, which, to the best of our knowledge, the first method that allows to analyze the standard Stochastic AdaGradNorm on Rdd
Lemma 3.4. Suppose F satisfies Assumptions 1 and 3 then
T 1-
F(xt) F(x*)
||ا|
x 1
2n
MM
by + log
E
<
(1)
br
771
7
bp
5

---

Published as a conference paper at ICLR 2023
Proof sketch. Starting from the y-quasar convexity, with simple transformations, obtain
F(x))= - F (-Ea, Tt x²) b, (1 - x= || - x=1 | 244 -=211)
7
2
Here we introduce our novel technique: instead of dividing by bt, we divide both sides by 26, - bu- This divisor causes a slight non-uniformity between the coefficients of the distance terms || - x² || making the sum of them not telescoping. However, this is exactly what want to handle the difficult term 7(2he bb)
i- which does not disappear after taking the expectation.
F F(x)) - F
(-Et, Et, Jt - x²)
be
|1
x²
0e+11
x 11 +
|| 2eel
E
R
2b: bu
(2be bo)
2b. bo
2ym
The key step is use Sauchy-Schwand inequality for the term
Er 24 x²)
||&ll|
2x x=='=="1""
with the appropriate coefficient À that the term | 2|² can be absorbed to make telescoping
sum 26.-1 bb - by -1 The remaining terms freee of x"; hence can be more easily
bb
bounded. We obtain
F(x)) F*
b |/2e - x²'l 112
be 11 x²
((x))
E
S E
Ze 11
2b.
bn
2yn bo)
2ym(2b: bo)
2
where
Ze
Now we have a telescoping sum
21
2b
26,
27m bp)
bell =r'll
Taking the sum over f, we have
F(xe)
F+
T
F F(a,)
F
E
2b.
2b.
bu
|
xx 11?
T
T 17
F(x,))
Ze
|
+ E
27m77
2707
[=1
Proceeding to bound each term, we will obtain Lemma 3.4
We emphasize the following crucial aspect of Lemma 3.4 the inequality gives us relationship between the function gap and the stepsize by, which we know how to bound with high probability and On the other hand, this relationship not ideal due to the fact that on the I.H.S. of ( we have not obtained decoupling between the function gap and by. To this end, introduce the second novel technique. Let AT D. F(x)) -F(x") write
under Assumptions
AT = Ar E(6) + Ar (
where we define the event E(8) My S d² log? ef' J. For the first term, when E(8) happens, we also know from Lemma 3.3 that the stepsize is bounded. Thus can bound
Σ D F(x.) F(x*) by E(8)
E A 1 F(O]
br
which leads us back to Lemma 3.4 We can bound the second term using a tail bound for the event (8)), knowing from the first observation that Pr [5)]
8. From this insight, and using the self-bounding argument as in the proof of Theorem 3.1 we finally obtain the following result.
Theorem 3.5. Suppose F satisfies Assumptions 1. 2', 3 and 4, Stochastic AdaGradNorm admits
F(x.) - F(x*) -0 -0 (o² log 2, log(1 + 2 log T))
1
a log o
T
VT

---

Published as a conference paper at ICLR 2023
Algorithm 3 AdaGradNorm-Las
Algorithm 4 AdaGradNorm-Lae Last
Initialize: 21,7 77
0, A
> 0,
Initialize: 31, 0,8 [2/3, 1),pi for t to T
for to to
b
(61
124 + =1=1
| 2 x
b.
110 + Σ 21+1
Pi
Pt
I(+1 = It "1 VF()))
(F(2))
696
Remark 3.6. In the big-O notation, we only show the dependency on and 0 for simplicity. The dependeney on the other parameters will be made explicit the proof of the theorem. By setting a = O, we obtain the standard convergence rate E[(Ei= F(æ:) F(xx)))()) /) = O(1/T) as shown in Section 3.1 for the deterministic setting. This means our analysis adapts to the noise parameter a.
Finally, it is worth pointing out that even when we relax Assumption 2 to Assumption 2, we can still provide a convergence guarantee for Stochastic AdaGradNorm. We present the result Theorem A.9 in the appendix.
4
LAST ITERATE CONVERGENCE OF VARIANTS OF ADAGRADNORM FOR 7- 7-QUASAR CONVEX AND SMOOTH MINIMIZATION ON Rd
In Section 3 under Assumptions 1 and 2, we proved that the average iterate produced by AdaGrad- Norm converges at the 1/T rate, i.e., - F(xx)- F /T 0(1/T). A natural question is whether there exists adaptive algorithm that can guarantee the convergence of the last iterate. In this section, we give an affirmative answer by presenting two simple variants of AdaGradNorm and show convergence of the last iterate under Assumptions and 2'.
In Algorithm 3 by setting = i- Fx;)]] has bigger coefficient than in the standard AdaGradNorm. Should we use the 2 --ower (A = 0) instead of 2+ with A > 0, h, will grow faster compared with the same term AdaGradNorm. We will see later that A still leads to the convergence of the last iterate. However, we first focus on the easier case with A > 0 and state convergence rate of Algorithm ii Theorem[4.]
Theorem 4.1.
With Assumptions and 2', by taking Pt = 1 in Algorithm we have
i
(2
[111-2 [ 77
+ +1()) + 9(4) $
1
[1 1-=
+ 9(())
F(+T41) F
where
(2+A))()
log
DL %0 nL
A 2
and s(A) = (2 + A)n )m
2n
2nL 7h0
M(A)= = (2+ f. log
log"
A E (0
2h
bo
An issue with variant is that, when using 2+ power, the stepsize ceases to be scale-invariant. Algorithm 4 shows different approach, using the scale-invariant power }/2 but different stepsize 6/63-1 for a constant å E [2/3, 1). The tradeoff that the provable convergence rate of the second variant depends exponentially on the smoothness parameter. We also note that, when 5 1, we obtain the same algorithm as when setting A = 0 in the previous variant.
Remark 4.2. by every algorithm is only for stabilization and is set to constant that very close to practice. However, the first stepsize in Algorithm i.e., b/b0-6 will explode. To avoid this issue, we can simply set the first stepsize as by instead of b4b/ We note that, under this change, Algorithm still admits provable convergence rate. However, for simplicity, we keep b 1 in both the description of the algorithm and its analysis.
Theorem 4.3. With Assumptions and 2', by taking Pt = in Algorithm 4 we have
by exp
(()) 1-8
1(())
F(TT+1) - F² <
T

---

Published as a conference paper at ICLR 2023
where k(6) [is)=z" 12
22 7/7"" 60
(1
+
2nL 750
8 --
log"
2nL 760
1
70
in Algorithm or equivalently 5 - 1 in Algorithm 4 First, by seeing A tends to O, we can expect convergence rate depending exponentially on the problem parameters. When A = O, while we can still expect a bound of the function gap via the final stepsize by, bounding by becomes problematic. In the proof of Theorem
To finish this section, we briefly discuss the case when A
4.1 bound by, we use the sum Et= [VF(
E 124 - This sum only admits by
bipt
lower bound in terms of by when A > O, thus the argument does not work when A 0. However, it is still possible to give asymptotic rate under the "-quasar convexity assumption. If we further assume that F is convex, we can give a non-asymptotic rate. The main idea on how to bound by is as follows. Let be the last time such that b. n1/22. The increment from br+1 to by be bounded by observing that the increase in each step [V+)(=) < E.pb?. Moreover, the critical step is the increase from by by+1, which again can be analyzed via the function gap and smoothness. We
present the asymptotic and non-symptotic convergence rate and their analysis in Sections B.4 and B.5 in the appendix.
ACCELERATED VARIANTS OF ADAGRADNORM FOR CONVEX AND SMOOTH MINIMIZATION ON R"
In this section, by using the stronger Assumption 1', give new algorithms that achieve the celerated rate O matching the optimal rate in T for convex and smooth optimization for un- constrained deterministic problems. Our new algorithms are adapted from the acceleration scheme introduced in Auslender & Teboulle (2006) (see also Lan (2020). They are also similar to existing adaptive accelerated methods designed for bounded domains, including Levy et al. (2018); Ene al.) (2021). However, previous analysis does not apply in unconstrained problems; we therefore have to make necessary modifications.
To the best of our knowledge, in unconstrained problems under the deterministic setting, the only existing analysis for an accelerated method was introduced (Antonakopoulos et al. (2022). Here we discuss some limitations of this work. The convergence rate for the weighted average iterate T1+1/2 is given by
1 T2
f(T+112)- 0o
R lim b, 100
Kn.
lim by
1000
where is a KA -stsrongyy convex mirror map funetion, R₁ max M(x) - min ((x) is the range of h. This result is only applicable when the domain is unbounded but the range of the mirror map bounded. Even in the standard lz setup with h(x) = 1 |||x||? this assumption does not hold. Moreover, due to the term lim,- bt. the above guarantee dependent on the particular function. Thus, while a standard convergence guarantee is applicable to say, all SVM models with Huber loss, the above guarantee varies for each SVM model and there is universal bound for all of them.
We further highlight some key differences between this work and ours. While the convergence rate above depends the convergence of the stepsize, for both our variants, we will show explicit convergence rate that holds universally for the entire function class. Second, the algorithm in Anton- extra gradient method which requires to calculate gradients twice in one iteration. Instead, our algorithms only need one gradient computation per iteration. Fi- nally, our algorithms guarantee the convergence of the last iterate opposed to that for the weighted average iterate as shown above.
akopoulos et al. (202) is based
Algorithm shows the first variant. For an accelerated method, the step size typically has the form b, (b3 Ei= s (VFF?)) 1 where VF; is the gradient evaluated at time i, and s; O
However in order to be able to give an explicit convergence rate, Algorithm usee smaller &, with power 1_ with A > 0. When A 0, we can only show an asymptotic convergence rate, similarly to AAtonakooooulss al. (2022). We first focus on the case when A > 0. In the appendix we will discuss the convergence of the algorithm when A = O. We have the following theorem.
8

---

Published as a conference paper at ICLR 2023
Algorithm 5 AdaGradNorm-Ase
Algorithm AdaGradNorm
Initialize:
w1. > 0,
0,ac
Initialize: x1 W1, 0, E 12/3, 0, > 0 for 1 T
0, q: > 0
for 1 to T
Ur (1
4z) az)Wy + dxTt
U2 (1 Oe) (e) + 04
by = (b2+a
+ Ei=1 |( ズोΙ
b, [bg + Ei= IIV
of
F++1 St geb
1 (
F+41 = Et q:b;b/-1
n
W6++1 = (1 ap W + 0+
W++1 (1 ar)wr + a,2
Theorem 5.1. Suppose F satisfies Assumptions 1' and 2', let a,
1TT 9: = in Alg.
then
[21/2* - 2211
4h(A)
xz 11? ||00
F(Wr+1)- F
+ 66
+ h(4)
T(T +
172
1
2m
where
(24
Lnj²
1 log"
A 21 1
MA)=
hoo
(2+A)
log
A E (0,
26 1-
b0
Similarly to the second variant in the previous section, also have scale-invariant accelerated algorithm, shown in Algorithm 6 using power 2 but smaller stepsize 1/1/1/ This algorithm also has an exponential dependency on the problem parameters, which is given in the following theorem. Remark 5.2. Similar to Remark 4.2 the first stepsize in Algorithm 6 i.c., 6/60-6 can be replaced by bj. However, for simplicity, we keep 6660-6 in both the description of the algorithm and its analysis.
Theorem 5.3. Suppose F satisfies Assumptions 1' and 2', let a; - a: = 3 in Alg. then
bo exp
s(8) 1-8
(s(5)
F(WT+1)= F E +1)+1
where s(0) =
||x'=x1 2n
1
1
bp 2
Similarly to the previous section, we give more detailed discussion of the convergence of the Algorithm 5 when A = 0 or equivalently Algorithm when when While we can still show an accelerated ( asymptotic convergence rate, we only present an O(1/T2 1/T) non-asymptotic rate. The difference between these algorithms and the ones in the previous section is that the stepsize b, increases much faster. More precisely, the increment in each step is now (((=) instead of ((x))) Thus can only show upperbound for b, that grows linearly with time, which leads to the 0(1/T² + 1/T) convergence rate.
in Section C.4 in the appendix.
6 CONCLUSION AND FUTURE WORK
In this paper, we go back to the most basic AdaGrad algorithm and study its convergence rate in gen- eralized smooth convex optimization. We prove explicit convergence guarantees for unconstrained problems in both the deterministic and stochastic setting. Building on these insights, we propose new algorithms that exhibit last iterate convergence, with and without acceleration. We see our work as primarily theoretical since the first and foremost goal is to understand properties of existing algorithms that work well in practice. We refer the reader to the long line of previous works (Duchi
et al. 201 1: Levy 2017 Kavis al. [019 Bach & Levy] 2019 Antonakopoulos et al. [0200] Ene
ct al. 2021 Ene & Nguyen 2022] Antonakopoulos et al. (022) that have already demonstrated the behavior of AdaGrad and accelerated adaptive algorithms empirically.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
TN and AE were supported in part by NSF CAREER grant CCF-1750333 NSF grant III-1908510, and Alfred P. Sloan Research Fellowship. HN supported in part by NSF CAREER grant CCF-1750716 and NSF grant CCF-1909314.
Reproducibility Statement.
We include the full proofs of all theorems in the Appendix.
REFERENCES
Kimon Antonakopoulos, E Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra- gradient methods for min-max optimization and games. arXiv preprint arXiv:2010. 12100, 2020.
Kimon Antonakopoulos, Dong Quan Vu, Volkan Cevher, Kfir Levy, and Panayotis Mertikopoulos. Undergrad: universal black-box optimization method with almost fimension-free convergence rate guarantees. In International Conference on Machine Learning, pp. 772-795, PMLR, 2022.
Alfred Auslender and Mare Teboulle. Interior gradient and proximal methods for convex and conic optimization. SIAM Journal on Optimization, 16(3):697-725 2006.
Francis Bach and Kfir Levy. universal algorithm for variational inequalities adaptive to smooth- ness and noise. In Conference on learning theory, pp. 164-194. PMLR, 2019.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Alina Ene and Huy Nguyen. Adaptive and universal algorithms for variational inequalities with optimal convergence. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 36, pp.
Alina Ene, Huy L Nguyen, and Adrian Vladu. Adaptive gradient methods for constrained convex optimization and variational inequalities. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 7314-7321, 2021.
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. arXiv preprint arXiv:2202.05799 2022.
Charles Guille-Fseuret, Manuela Girotti, Baptiste Goujaud, and loannis Mitliagkas. A study of condition numbers for first-order optimization. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2261-1266 PMLR, 13-15 Apr 2021. html
URL httpp::/ http://cceecccoo.....eeee/////// https///ww..oplleeeeeeeeeeeeee.
mlr www.ppresssllll
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on learning theory, pp. 1894-1938. PMLR, 2020.
Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher: Unixgrad: universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in Neural Information Processing Systems, 32, 2019.
Ali Kavis, Kfir Levy, and Volkan Cevher. High probability bounds for a class nonconvex gorithms with adagrad stepsize. In 10th International Conference Learning Representations (ICLR), 2022.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11X.v:1412.6998, 2014.
Guanghui Lan. First-order and stochastic optimization methods for machine learning. Springer, 2020.
Kfir Levy. Online to offline conversions, universality and adaptive minibatch sizes. Advances in Neural Information Processing Systems, 30, 2017.
10

---

Published as a conference paper at ICLR 2023
Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceler- ation. Advances Neural Information Processing Systems, 31, 2018.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. The 22nd international conference on artificial intelligence and statistics, pp. 983- 992. PMLR, 2019.
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint (rXXv:2007.142900 2020.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Reprexentations, 2018.
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-mmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26-31, 2012.
Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. Sub-weibull distributions: Generalizing sub-gaussiaa and sub-exponential properties to heavier tailed distributions. Stat, (1):e318, 2020.
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.
Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient de- scent. In International conference on artificial intelligence and statistics, pp. 1475-1485, PMLR, 2020.

---

Published as a conference paper at ICLR 2023
A MISSING PROOFS FROM SECTION 3
A.1 ADAGRADNORM
As we pointed out before, possible to obtain an improvement by factor 1/7 compared with Theorem 3.1 by assuming L-smoothness instead of weak L-smoothness.
Theorem A.1. With Assumptions and 2', AdaGradNorm admits
E F(x.) F" T
[1||11== 2 log"
bu)
[m] -001==1
2n
log
2nL bo
by
79
7
T
Proof. Note that Assumption 2' can imply Assumption 2, so following the same proof of Theorem we still have
||] x=
2m
2
Σ F(x)) Fr br
log
7T7
7bo
However, from here, will bound by directly, rathe than the self bounded argument in the previous proof. By the L-smoothness, we know
L | 1111
F(x++1) F(xx) $ (VF(z)), Je+1- 34411 xx) +
Lnp 1)
[F(x))]1
=
263 by
VF(x))]1
(F(xz) - F(1(+1))
Ln 1
|F(2))1
+
be
by
by
Sum up from 1 to T, we know
T
VF(:0112
T
Ln
< (F(x1) - F(IT+1)) +
b
by
2 " (F(=1) -F("))
Ln
1
|V((2))1
b,
Use the the same proof technique as before, we can bound
Σ
L
[F(x1)]1 < log
7L bo
and
T
VF(x,)]1
T
63
T
>
b. b = by by.
b,
b;
1=1
Hence, we know
2
nL
by < (F(11)F((2) + 2n log
bo by
Ll 111
nL
< "
+ log*
+ bu- bo
By using this bound br, can get the final result with improvement by factor 1/7. n
12

---

Published as a conference paper at ICLR 2023
A.2 STOCHASTIC ADAGRADNORM
We will employ the following notations for convenience
A, Σ F(1.) F"; ==1
& = (F(x)) VF(xx);
M, max ||&.11
=Eit!
Before diving into the details of our proof, we first present some technical results we will use in the proof of Theorem 3.5
A.2.1 TECHNICAL LEMMAS
To start with, under Assumptions and only, obtain a bound for term close final goal År.
Lemma A.2. (Lemma 3.4
Suppose F satisfies Assumptions 1 and 3, we have
AT
112
27 7
MT
bt
E
E
log
br
777
by
Proof. We start by using the 7-quasar convexity of the function F
(FF(x)) Ez - -x²)
F(x:) F <
(V()))) (F())), x4 - x²) FV(())) F2 - -x*)
7
Et, x²) by
(1:2g x x²12
| - x= | xz
7
2
Dividing both sides by 2b; bo and taking expactations, we have
F(I:) Fa 2h: bo
(- Jt x²t) (2h, bo)
by
| x²1
|04+1
x=1 +
||
26 11
<
2b. by
2ym
Now no longer have a telescoping sum the R.H.S.. However, this is exactly what we want to handle the difficult term (-Er_x==²") which does not disappear after taking the expectation. The key step is to use
7(26, bn)
inequality for the term
KK-E, 2i x²)1
S 2
11E.112
||,, - x= 112
2X
with the appropriate coefficient À so that the term || x= 2 can be absorbed to make telescoping
sum by ||
-
b. [., |
The remaining terms free of z;; hence can be more easily
2h.
2b. bo
13

---

Published as a conference paper at ICLR 2023
bounded. To do this, note that
Ee, 24 - x²)
E
(2b, - bn)
=E
(-he: 24 - x²))
2b: - 60
2b, 60
A
<E
||4| 1( Se, 22 - x">l
|A|
b
b, 2ym bu)
<E
|
11Ea11
2-m(2b - bo)
b--1
2ymr(22g (2b, - 1009 105)
be
||ace - x011))
+ |A|
2-11(22111 - -bo)
E
17
1|Eel1
7/0
26, bo
26: b0
b
bc
12 - x=" 11
+ E
26:-1 60
2b, bo
2
Thus we have
F(xx) FM
E
2h, bo
<
1
1|E/11
ybu
2br-1 bo
2b, - bu
G (are)
b
||:0 - 1=1
be 1| - x 112
7
+ E
+
2717/ 27/1(221-1 (24-1
1b)
(2b, - bb)
2-bb(2bl bn)
7
2b, - bo 11Ea
<
ybo
26,-1 - b0
1 (
b._1 1| - 1²11²
by || - x= 112
+
E
+
27m bo)
(2b: - bu)
276b
Now we have telescoping sum
b--1 [20 - x²
by || - 1=
2yn](2b,_) bo)
2yn((bb bp)
and the remaining terms are free It x². Taking the sum over i, we have
T
F(are) ) F
2b, bo
T
1
<
115x
2xb0
26, by
2b, bo
1=1
|| x= 11
m/
Fxxx)1
E
2
27
14

---

Published as a conference paper at ICLR 2023
First for the easy term E
E
2 (x+)]l²
we have
1=
2,,6
7
(x;))1
b2
D
E
2712
27
1i2
-
E
Σ
log 6 - log b2
27
1=1
2 E
bf
log
(3)
bo
Next, we bound
17
1
1
1|
7b0
2h 1
bo
2b, bn
1
1
SE
MT
7bo
2b,-1
bo
2b. - bn
77
SE
MT
(4)
700
Plugging the bounds
and
into
we have
E
F(I:)
F
E
F(x1) F
|| 1²
17 E
[MT]
+
log
br
2b.
2b: bo
2/m
708
7
bo
The last step is using > F(w.)- F*
-(x))FF
Ar. to finish the proof.
2br
Due to the appearance Mr in Lemma A.2 it natural consider what we can obtain under the additional Assumption 4, i.e., sub- weibul noise with parameter 6. We first provide the following simple bound on E [[]Se|]?]. The result is not new and the proof is only included for completeness.
Lemma A.3. Under Assumption 4, Vt E [T', we have
[|E < r'20 + 1)eo?.
Proof. We first note that from the definition of neb-Weibull noise, the tail of ||Ee]] can be bounded as follows
E [exp ((I))]1/o))/0)] exxp (1 (u/o)110)
Pr [ll 2 w|
exp ((u/o)z/0)
Then we can obtain
| 12] = / 2u |||||| u| du
|
2u 2uexp 1 (u/o)110) du
fo 220-1 exp(-u)dd
20e02
= r(20 1)ea²
where u is substituted by の in the second equation.
Next, we prove a high probability bound on My, the proof of which is inspired by Lemma in & Orabona 2020).
15

---

Published as a conference paper at ICLR 2023
Lemma A.4. Under Assumption 4, given 0 < 8 < 1, define the event
MT S o² 20 29 ef'
E(6)
8
we have Pr [E(6)) 21 -8
Proof. Note that
Pr Mr 2 u] = =Pr
max ||5.112 2 u [
Pr
max [
|| /
E
exp
exp ((ul/2/0)1/0)
7
E [exp ((I1E= (1)))/)))))/00)
exp ((w) (//1///////// 10)
T Texp (1
(2 /0)///)))/)))))))))))))))))
Choose u = o2log20 sT to obtain
20 eT
Pr Mr 2 0² log"
S 6.
Lastly, we will find an upper bound on the p-th moment of Mr.
Lemma A.S. Under Assumption 4, given >> O, there is
E
M
S
22 (1og2 20p (T(40p + 1)e2T9) + +1).
Proof. Note that in Lemma A.4 we proved
Pr [Mr 2 u] < exp (1 (1- (o212/0)1100
Let E()) be the same as it in Lemma
A.4
Then, by Holder's 's inequality we have
E M = E [M [(8)
+ E
[=())
$ E
[M B(8)
+
EE
M2
E [1 [90o
20p eT
20 log
+
E
M2
20p eT
2p
log
+
2pu20-1 (M 2 ujdu
ef
< o
29 log
20p
+
2pu 1iip--TTest exp (1 - (12/2/o)110) du
eT
29 log
20p
o
2p
/T(40p + 1)eT8
TT
log 20p
+
T[40pt + 1)eT6)
8
Choose 8 1(10p+1)e2
1, we have
E |
s σ² 20 (log20> (T(40p+ + 1)e + +1).
16

---

Published as a conference paper at ICLR 2023
Note that all the above results only depend on Assumptions 1, 3 and without requiring the smooth- ness of F.
A.2.2 PROOF THEOREM 3.5
Theorem 3.5 requires Assumption 2' additionally. Thus we first show that under Assumptions 2'
and 4. by enjoys Ö(1 / T log" 28 T) upper bound with high probability.
Lemma A.6. (Lemma 3.3 Suppose F satisfies Assumptions 2 anddd 4. Under the event E(()
Mr S log 20 eT we have
br S (T( = 260 + 4(F(z1) FP)) + log 7L
ET
2 "og""""o"""""
cT
bo 1
4o
T Tlog"
20
log
1+
8
bg
Additionally, by Lemma A.4 there is
1 1- Pr < Pr pbr S gr))
Proof. We start by using the smoothness of F
F(E++1) - F((+)) < (VF())) (r+) - -xt) + _ ||:111 - xzll?
2
7 (VF(z)) FF(z))) + T²L
FF(x)))1
2b
T2a1.
" (VF(z)) F((z.)) Fx)))) |[()))) 2b}
V
b.
b < 2 (F(x:) - F(1++1)) + 25e, 4 F((x))
1 (
+
b
Taking the sum over i have
FF()))11 2(F(m)) -FF) +
(Ec. VF(I))
(T 1 11) |[F(EN))
1=1 b
by
Using the common technique, we know that ΣT over, for the I.H.S.
( n6
1 < 2nL %/ More-
T
(F(I))1
63 07-1
Σ
b br bo
by
b;
Thus we have
2(F(x1) - FF))
nT.
(E,, F())))
by < by +
L
+ Σ
17
bo
1=1
17

---

Published as a conference paper at ICLR 2023
For the last term in this equation,
notice that (E,, VF(2))
VMT (F()))) |l. hence
br - 2(F( - )
+nn nT. + bo + +2
T
(5t. VF()))
17
bu
be
t=1
2(F(x1) -P²) 1 7 + bo 22 MT
F
17
be
(0) 2(F(x1)) - -F*)
nb.
T
|FF((1)))
+ L log"
+ bo + +2/M,
T
bo
1=1
2(F(xr)) - -F*)
nI
T'
03
62
17 2n I log"
+ bo +
4M
bo
by
[=1
2(F - P*) + 2 log"
I + bu +
B 4Mr.T log
$ 1
bo
bg
where (a) is due to Jensen's 's inequality. We can write
by
bg + 16M
4M log
4MTT
log
log
6
16
69 + 16Mr
4M
+ llog
bg + 16MrT
bg
by
b6
16M7T
$
+ 4.4 log
4
bg
Hence
bt bp 2(F(I1) - -F
nL
b2
69 16M7T
17
21 log"
bo
|
+ 4447Tllg
bg
2(F(x1)-FF
nL
bT
b + 16M7T
< 60
21 log
+ 2
MrT log
11
bn
2
bg
which gives us
4(F(x1) Fx)
nb
D + 16MTT
br S 2hg +
+ 4n logt
+ 4/
Mr
17
bu
bg
Recall the definition of the event (()) is MT S 0² log 28 of thus we know
br S 2bg + 4(F(x1) -F²) + 4 log
7h + 40
20 ef 5
160 log
29
log
log
1
bo
By using Lemma A.6 we can consider the following decomposition
E [r]
E
AT
E [Ar1
AT br
E
by
1l ((8)
+ Ar [+))
AT
{6)())
1 F(())
+ [[
bT
Ar
(
+
by
18

---

Published as a conference paper at ICLR 2023
Note that Lemma 1.2mmaaA.2lam
tells us
AT
||
1=
211 ?
MT
bt by
E
R2
log
br
bg
Hence our remaining task is to find a proper bound on E lemma.
(x which is stated in the following
Lemma A.7. Under Assumptions 2' and 4 we have
[Ar & F((1)) - F + Log" + nL.
by
T8 + +nEE [Mdl]]
log
13/281/1
2b0
bg
Proof. We restart from the smoothness of F:
+ ,/L
F(1++1) - F(c.)) S - b,
(VF(s)) FF(.)), FF(x))) " (1;)11
(FF(x.))
b.
2b
Taking the over 8, have for t 2
- -(xx)-((x)) S
(VP(s))
+ Σ
"
(
2b2
b,)
nT.
$ 1 log
|
2bg
Following the same proof of Lemma A.6, we have
12
F(z() - F* F(())) - F + L
+ m M Me-1(t - 1) log
26o
Now we bound Ar as follows
T AT Σ F(x)) F
T F(I1) F² Σ
n
62_
F(m)) - F* + 112 log"
+ = M, Mi-1(1 1) log
2bo
t=2
TLL
T
< F(x1)= - F= + 1 Log
T +
m
Me-1 - 1) log
2bn
Dg
t=2
< (F(1)) F + 1²² L log"
T
T + m
MT log
62 log
73/22
2bn
bg
Thus we obtain
E ( < (A(x))- F + 2
1
T8 + nE
( |Mr log
ba (
73/2.
2h
Here we invoke Holder's inequality for three variables: for p, q, > 0, 1/p + 1/g + 1/r = 1 then
E 2| < ""
By substituting X = VT. Y = V
log
= 1 E=(6))
and p = 4, 2, 4, we have
E
Mr log
b2 1 (8)
Et/4 [M 1//2
log
b by
E
1/1
[
[=))
b9 bg
S
///4
[M2]
log E
81/4
19

---

Published as a conference paper at ICLR 2023
So finally get
7L
[[AT)ET1)) F(x1) F + 172 log
T8
2bp
by
+ nB11/4 [MG]
log E
73/281/4
b
Lemma A.8. Suppose F satisfies Assumptions 1, 2', 3 and 4 then
E Arl
2no (2(16-1) 11129 log 29 T Ci)
|01 x²11?
7
b bg
Sgr
log EE
2-11
y0g
na 12/20-1300 log T C2)
F(r1) F + 1 2
log"
[b
+
2b
+
[+ log
VT
7
2
where C1 = 2(28-1)*
1)+
log20 28 (T(40 + 1)e + and C2 = 1(- log (T(80 + 1)c²) + 1 are two
constants and
4(F(x1)- - FP)
4n log n
9r 200 +
n
bu
26 log 20 (5T))
40
T Tlog 20 (eT5)log
1
bg
Proof. As stated above, we know
E [Ar]
= E
Ar B(6)
+ E [ [-0]
AT bT
E
bt B(6)
+ E (
AT
9r (8)E
1 (()))
+E [EAAIEA())
br
AT
S (8)E
+ E8
(7-1)
by
3 gr)
||:0]
x= 1|
27
MT
bt bo
E
+ log
+ E [ [x)
2ym
7
| - 1²
21
< gō)
+
EE
[Mr]
+
log E
+ E [ATIE<08
27m
70%
bg
where (a) is due Lemma A.6
(b) is by Lemma A.2
Lemma A.7 gives us
A < (((x)) - 2
nL
T8 + 1/ [M+]
log
T3/2
2bo
Pluggin this bound, we have
E [Ar]
x= 1=1 111--=11
2n 7
+ ! log E
[1
Sor(
E [MT]
27111
7
+ (F((r)) - + 1)2
log*
T8 + 1/ 1/4 [M
log E
3//41//4
2h
20

---

Published as a conference paper at ICLR 2023
Now we take 8 = T and let gr == gr 4) obtain
[AT]
||| - 1²1
2nj
12
S9r
+
[r]
log
271
700
?
nT.
by
+ 73
F(x1) - F* L
+ nEEu/4 [M+]]
log E
VT.
2bo
From Lemma
A.5 we know
E [ S o² (log20 (T(40 + 1)e2TT) +1) s 222 log (T) + C1)
and
E [M]] I (log" (8(80 + 1)e2T2) + +1
= E [M]] = a (log (T + 1)e²T2) + +1) 1/4
S (o(log((((8))) + 1))2T2) + +1)
I 20 1jv8 11 log T C2)
Hence we have
E [Ar
2n1o² (2(00-1)v20 log 20 T T ci
||0] x01
by bg
"
Sgr
log E
2/m
+
F(11) F 172 log"
2he
7h
+ no 2 22(20-1)v) 11v0 log T +5) V
log E
b2
VT
7
2no (2(10-1)V20 log2 T Ci
[2] - 11
+ 7
b 63
<gr
log EE'
2-m7
yb
7
na 22100-13)) 1/v0 log T + C3)
F(x1) F*
L log*
2b
(1+ log E
b2 bg
vT
T3
2
With these results, we can finally show the theorem 3.5
Proof of Theorem 3.5 The key technique we use is the self-bounding argument. That is, we have expressed a bound for E [A]] via E[bg//b]], now we will show how to bound this term via Ar. To do this, rely the smoothness assumption and Lemma A.3
T
E
+
F
t=1
< b9 + E
21
+E Σ 2 (
< 1/ 2T(20 + 1)eo 2T + E 4L Σ F(x)) - F(x*)
$ b3 + 20 + 1)co²T 2T 4LE [A]].
Thus from Lemma A.8 we write
2T(20 + 1)
4L
E [rr]] s Go + G1 log 1+
+
E [Ar]
(5)
bg
21

---

Published as a conference paper at ICLR 2023
where
F(21)
F Log
nh
n1
(2(20-11v0 log T C2 VT
Go
2bg
+
73
2 20
2no (2(40-1)v20 log
(T) + +01)
|101 x=11
+ 9r
2717
yb
=0 1 σ
T Tlog" 28 T (1 2 log 20 T)gr
(2 1ive log" T Cz) VT
11
79T
G
=0 0 T Tlog20 20 T + gT
2hg- + 4(F(x))) - F
n
160 160 27 log 28 (ET
+ 4n log"
+ 40 1 by
Tlog (cTT) 1
bg
= 1 T Tlog" 28 Tlog(1 + log T)
Now we solve 5 Consider two cases:
If 4LE Ar]
< 220 + 2) then
40 + 11)e0 2T
E [Ar] < Go Gi log
1+
bg
(T 2 21 + 1)eo² then
8L E [AT] bi
E Ar] S Go + Gi log
1
1 + 8L E [Ar]
by
16LG1
Go + Gi log
+ Gi log
1+
1 16T.G
by
+
82 E [A]]
63
16LG1
S Go + G
+G log
1+
+ 16LG, /bg
b3
E
[A]]
16LG1
S Go + G1 +
+ +G1 log
1+
2
16el.1
+ AEAr]] s 2G, 2G, 2G, log
1+
In both cases, we have
E [[Ar] < 3Go 2G1 + 2G log [+ 16eLGi
41 + 1)eo²T
Gi log 1
bg
=0(11 poly(o" log log(11 2 T)))(1 + +ov Tlog T)
Dividing both sides by T concludes the proof.
A.2.3 CONVERGENCE OF STOCHASTIC ADAGRADNORM UNDER WEAKER ASSUMPTIONS
Note that Theorem 3.5 depends on the stronger Assumption 2' instead of Assumption 2. Besides, in Section 3.J. we proved that Assumptions and are enough to ensure that AdaGradNorm can converge in the deterministic setting. Hence it is reasonable to conjecture Stochastic AdaGradNorm can also converge replacing Assumption 2' by Assumption In this section, we show that, indeed, this conjecture is true.
22

---

Published as a conference paper at ICLR 2023
Theorem A.9. Suppose F satisfies Assumptions 1, 2, 3 and 4, Stochastic AdaGradNorm admits
1= F(x1) - F(x*)
= =0 (1L polyooooo([((ooV)) log T))
( (1]
0112
))
E
+
T
VT
T1/4
Proof.
First we invoke Lemma
A.2
to get
Ar
||
x=1 11
27 7
Mr
by
E
E
log
bt
7
6g
bo
Using Holder's inequality we have
21
x 112
2n
MT
bt
V
AT
S
+
E
+
log
[bTT]
D/
bn
[1 x=1
2n
27 log
[br]
$
+
[Mr] +
E [bT]
760
bo
Applying Lemma
A.5 with p = 1 to get
E [ a² (log2 (T(40 1)e2T2) +
s 0² 2228 log 20 (I2) 22 log (I 1)e²) + +1)
o² (240 log 28 T + +C)
where C = log (T(40 + 1)E?) +1.
Besides, note that
T 69 2 Σ
bt
(F(x))) <
|1 + 4LAT So +
2
11
LAT.
t=l
1=1
Thus we know
E br S
+
1lEel1 + 22 +2VLLn LAT.
T
5 60 +
Σ
E ||| + 2VLE A
1=1
$ bo + v /20 1) 2V
V
where the last inequality is due to Lemma Hence, by letting
A.3
B1 [1 12
2n
220 log
28
T + c) 0²
?7)
763
= 0 + 0² log T)
B2 bn v 20 + 1)ea2T
= 0 + +VVT)
X E AT
solve the following inequality
))
2n log
B2 + 2v 2VLx L.X
X²
<
Bi +
(Br + (B2+2VLX))
7
bn
get the final result.
23

---

Published as a conference paper at ICLR 2023
A.3 ADAGRAD
Algorithm 7 AdaGrad
Initialize: 21," > 0
for = = T
for j = 1 d
br. v bb.5 Ei (V)((z)))
I ((zz)
1t = T...j bL.
In this section, we will extend the result of AdaGradNorm to AdaGrad (Algorithm 7 in the deter- ministic setting. To our knowledge, rate of AdaGrad on Rd. First, we examine the growth of the stepsize.
the first to give the explicit bound of the counvergence
Lemma A.10. Suppose F satisfies Assumptions 1 and 2", we have
d 2(F((11)
F*) + 2n Σ Lg log
d
nT bo.s
Σ bT. S
bu.j +
jml
Proof. By smoothness we have
Iz+1 Ft+1 xxt) + |1++1 - xelli
F(set1) F(ar)) S (VF())),
d
+ 1.g9?
Σ
1
=
b
267
j=1
11 vfF(Ee) S F(x))= F(E441) + Σ
I.g1?
1
vFF(2))
2bb
26%
2b15)
j=1
j=1
d
v,F(xi) S F(m))
F" +
1
V)F(ei)?
2bnJ
26%
2br.3
(=1
Note that, for the L.H.S.,
T
T
02 2.j
18- 1-
(xx)))
1
2bc.j
2
bi.j
j=1 t=1
d
T
7
> 2
br..
11
1=1 1=1
d
7 Σ
(bT boos)
2 ==1
Besides,
T
d
T >
d
Σ
17
1) v ((x))
1
v, F(x))²
2b2
2br5
2
b
j=1
17
d
T3
Lin
V FF(()))²
(Tj is the last l such thatbe. S n2)
1/²
122
67 15
1,j
2 1=1
b
1=1
21²
Log log*
bo.j
j=1
24

---

Published as a conference paper at ICLR 2023
Hence have
bo.j + 2(F(x1) -F)
d
L.g log nL.
br
+ 21j Σ
bo.s
7
-=1
j=1
Theorem A.11 states the convergence guarantee for Algorithm 7
Theorem A.1. Suppose F satisfies Assumptions I and 2", we have
ΣT F(x)) -
T
d ji= bo.s + 2(F(a))-F") + 2n Ei Ljj logt
2L bo.)
111-="10,
+
2n
2nj11
bo.s)
79
?
dd II
where
d - x I Σ ( -
|
Before going into the proof, it is worth discussing the result above as well as the main challenges and differences compared with AdaGradNorm. For simplicity, let b, diag(br.)). We can expect that, by a similar argument that we used before to bound the function value gap via the stepsize, we will have
ETs F(x1) F g(br)
[| ||21-0"||2
2n dd
Zj=1
bu.j)
717
T
where g(by) is a function of the last stepsize and the factor obtained in similar manner as before, but in d-dimensions. The challenge is that since the stepsize is vector, it is not possible to use "division" by the stepsize in AdaGradNorm. On the one hand, we can overcome this by rewriting the argument; on the other hand, this problem will incur exponential rate for g (br)) dependent the smoothness parameters.
I ta-=21 "
2z 2==1
2nhg
bo.s)
799)
Proof. We can write
Tz+1 = n7,b VVF(x)...
Starting from 7-quasar convexity
(VF(I)) 24 - x*))
F(x)) - F <
7
(b. (Ix x(+1), -xx)
||
x= 112
|| 12.1...
207
|x x= I1..
||
x- 1=,
+ "
|VF(2)))
277y
24
Note that F also satisfies Assumption 2"
VF
F(xx) - F*
2
25

---

Published as a conference paper at ICLR 2023
Hence
F(11)= F
IVF(
I F(xt) - F
2
4
1 - x² 201
| x2
2117
27
F(xt)
F
12 x=1l "1..
- | x2'1..
"
VF
b.
|VF()))
2
217Y
27
4
7 F(x+)= - F <
22 x² x'1
| x'...
Σ
d
1
V,F(s,)?
ybu
2Lj
==1
Taking the sum over t
T
F(x1) - F
|| - xz x=11b. -110+11 - 11
1
v)F(x,)
1/7
The
21,
1=1
t=1 j=
[1
1b,
||oT+1
x=' br
T
|1
x=
2011
-b
+
d
1
v)F(21)?
7m77
2L
1=
j=1
Due to the excess term
2t=2
T
1 18, in the RHS, need to proceed and bound ||
79
x²
2
b.-1" First, observe that since the I.H.S. is non-negative,
[TT41
x= Foy
|2] x= 1B
x² br b
11
1 1
v)F(I,)
79
2L,
t=
1=1
To upperbound ||
==1 .l..- key observation is that
| - x 121
[2T+1
x² 2"112,
|2T+1 =2'1 by | x² br-
br
2 | - 22 by min
&
bT+1K by.k
Hence for T'
|TT+| - x=" 112
by
7:7)
< max
by+1, -1)
||] - x² 12
+
|
x
b
11
1)
V,
v)F(2))
br,k
77
7/1)
7b.,
21.y'
2=
j=1
26

---

Published as a conference paper at ICLR 2023
| liy bT-1
By using this bound for the last term
obtain
T
F(xe)=
=F
[1
1b,
|1T+11 x=1lb,
T
1 xx
d
1
1
+
Vj F(F(2))2
977
71
Tbr.j
2Lj
2
t=
j=1
21
x= IlB
T- 1
1 - x² 2211
T
d
b.
11
V Fxa)2
M
bb.
2L,
2
t=1 j=1
bT.
-1 1)
|11 - x 111
T
100
x=
II.
Di-1
T-1
vyF(as)²
+ max
-1K
717
717
2L,
1=1 j=1
bT
||:0-12 - 11
T-1 1
10 x b
T-
1
[,F(xr)?
= max
by-1,
?!77
ybrs
2L
1=2
1=1
j=l
1
2Lj/ )
()F(E))
Continue to unroll this relation and for convenience let [ maxk
br.k
1. we
have
11-1A
F(x1) - F
max
be.k
1 - x*1 11,
max
be
Σ
17
1
v
1,
791
be-
7br.
2L.;
be
||01 - x 101
T
T
be
(
1
v(F(2))
max
max
b &
t
b
2L
j=1
(=-+1
Given j. if big > 27hg we know
max bek II M=t+1
1
2n
T
by
(2nT1 bo.i
v(F(2,)
<05
max
k b
2L,)
?
b
27

---

Published as a conference paper at ICLR 2023
Otherwise, let Ty be the last t such that dej
20hy
also have
7
T
be,k
11
FzF(2))²
max
lc
1
2[j
(=++1
beck
1
max
1
2Lj )
T
biok
1
max
V
vxF(2²)
1,
2L}
T
bick
FfF(1))²
b 1,8
1=2
b
1 Tj bi 1/-1. 1.1
max
11-1,8
De,
T
bi.k
27 Σ
max
bisi
bb-lid 1,
1
2m
T
br,k
2nLs
boo
max
7
1
Hence we know
d
T
T
beik
1
max
b
7brs
[xF(11)²
E=f+1
21
by
2xpla bos)
+
Σ
max
7
k
1
Thus we have
T
F(xt)= - F
T
by.k
12 11,
d
T
T
be
( Then
1
II
V FzF(21)2
max
max
by 1,k
7/71
be 1.20
2Lj
j=1 1=1
(=++1
max by,k
| x011
27
2gL bo.s
+
b
717
7
7
j=1
From Lemma A.10
d
2(F(I1) F*)
T bo.j
brs
bo.j
+ 2n Σ
Lg log
j=1
Using AM-GM we have
2d 2j=1
1
2(F(x1) FF) F*)
nb
bT
5
Σ
bo.s
2n
T, log
dd
77
bo.j
28

---

Published as a conference paper at ICLR 2023
Note that
br.
bb_
max
3
115
b
b1
1=2
==
br.j
bu.j
1
Σ 5=1
bo. + 2(F(21) FF*)
2n
b log
nl. bu.i
dd [1==1 bn.j
j=1
Hence
F(x.) F
br.j
||] - x=1 Ib
27
max
+
bo.s
J b
791
7
7
j=1 butt
d
2(F(a))-F=)
2n ΣØ= Lug log
bg.)
||=] x
+ 2n
=1=1
(2nLs
buo))
79
7
7
dd 1 bn.j
which finishes the proof.
B MISSING PROOFS FROM SECTION
B.1 IMPORTANT LEMMA
First, we state a general lemma that can be used for a more general setting. The proof of the lemma standard.
Lemma B.1. Suppose F satisfies Assumptions and 2' and the following conditions hold:
Ty is generated by Ft+1 It V ((x)), with 17 > 0 and > 0 is non-decreasing:
P: (0, 1] satisfies
1 1-Pe11
P1 1:
Pt
P1+1
Then we have
F(XT+1) F
[2] x²
T
L
Pt
PrC
12
<
+
(6)
preT
7T7)
20s
71)
2
E
t=1
29

---

Published as a conference paper at ICLR 2023
Proof. Starting from L-smoothness
F(1(+1) Fx()) z (VF(2,), J441 - x1) T. |1 - x2l1?
2
2pt (VF(It), x++1 - -z) + 1 2pe (1-22)) (VF(z)), 2z41 - xz)) + 2
L
rx+1 - xel1
2p (VF(z)), x² - -xe) + 2p: FVF( F441 - -x)
?
?
2pt
L
+ (1- ?
(VF( 2141 - rz) +
I(+1 - 22l1
2
< 2p. (F - F(xx)) + P.C
[|| xx11 - ||02++1 - x=12 - | - x||
1 1 ?
2pt
Ct | - 23 112 + L
|| =zell
2
2pr (F* - F(xx)) + PiCe
[[].r - x" 112 - || - x² 12]
7M
L Pict
| - -2xl?
1)
?
Note that Assumption 2 can be implied by Assumption 2", hence we have
[V <7 [ 1
F F'=F(aa) S
2L
2r72L
Therefore
F(I++1) - F(+,) S 2p. (F - -F(x)))
PeCt
[|| - 2²112- | - x² x2
mm
I
pect
+
| - 1iel2
2
n
?
$ Pc
(F* F(x1))
pic?
1 -12el2
+
PeCt
[|| x01 11 x=]]]]
2112L
+ 2 17 ?T7
1 Ct
P.c.
|| -20l
(F* - F(xx)) +
Pice
[||:r= - x11 -112011 x11
Pt
?.7
+
1
at
Pect
p.c.
|| - xel1?
2
n
27²²
We obtain
F(x+11) F
1 Pt
1 x=
|| 122
(F(x))
-F*)
Pice
PiG
?17
L
1
Pt
Pece
| 1rel2
20,
7
7m
2
Pt.
Note that we require 1 2
1-pr+1 and e is increasing hence
1-Pc+1
Pc+1
1 P
Ptc
P++1ce
Pe41C411
which leads to ((1T+1) - F
PrCt
1 1-P1 Pi (F(x1) - FF)) | 12
T
L
Pt
Pec
|| - =x+112
Pici
?17
2c,
7M1)
2012
Pt
1=1
1-P1 Pi (F(z1) - -F") + || - 121
L
Pt
PEC
F
Pic
7m7
2c,
mm
2m L
c/Pr
30

---

Published as a conference paper at ICLR 2023
By setting P1 we get the desired result.
B.2 FIRST VARIANT
Note that if we assume pr satisfies the condition in Lemma B.I by replacing ot by by, we have
F(rr+1) F
|11 x 1
T
1
Pt peb 20p2
of ?(VVF(1)))
prbr
2b
bipt
immediately.
Now
our
two
left
tasks to bound the residual
term
ΣE1
L
pab 2
D' FF and find an upper bound on br. Lemmas
B.2
26
77
ppp:
and
B.3
demonstrate we achieve these two goals.
Lemma B.2. Pf for every t. we have
T
L
1 (
I 1M4)
2b.
2m
blp
T
Pt.
pebe
S 9(A)
2n121. L
biP:
1=1
where
(2+ (2+
nI. log"
by
A 221
(2 +
A)m
22m
4
2nL 7/0
M(A)= =
and g(A)=
log
(2+
log"
+ nI. bo
A E (0,
7
20
Proof. We first bound
T
L
1
r V
2h:
211
bipt
If 6, > nL, we know
L
17
Σ
<OS
2h.
21
Otherwise, we define the time
max {1 E (T), be nD. Hence, have
L 1
L
1
17 ((
L
2b
2m
by.
2b
21
biPt
2b:
2n
8%P:
v72
L.
x
2b:
2m
2b,
b3p
t=1
L
B2+A
D
2+4
2
67
2+A
x 6 A--1
2
6
2
12+A
[=1
Dis1
((L))
A A>1
2
63
12+
<<1
b2+4
1244
A
2
1=1
A <1
2
6.
(2+Ain(y)) 4
log bp
nl.
A 2
(2+Amn L 26
log bo
nl
A <
3
M(D))
31

---

Published as a conference paper at ICLR 2023
By applying similar argument, prove
Pt
peb
n² 1
((()).
7 21
lipt
Lemma B.3. Suppose all the conditions in Lemma B.1 are satisfied by replacing by by, addition- ally, assume Pt. S 1, we will have
+ +MA)+ + bg #
x 11
by
<
?1
Proof. Using Lemma B.1 by replacing ot by be, we know F(TT+1)
F
prbr
||0 x=
11
L
1
Pt
pebe
V
1/
717
26;
1
Mm
2012L)
bipt
|01 - x= 1=2
T
Pt
pebe
vp (V
nI1 (x))1
+
2b
2m
2r²2
|001 - 11
al V (
h(A) g(A)
26 Pt
Y77
where the last inequality is by Lemma B.2 Noticing F(4T+1) F 2 0, we know
(Fx)))
| 11
((()))))))))) + g()).
Pr
Now we use the update rule of be to get
T n
1
T
12+
b
7
T
1 6/
7
(6 b
20/pr
2 [=1
62
2
2
[=1
Hence we know
$
br
2
[1
xz
+
h(A)
+ + bg
Equipped with Lemmas B.2 and
B.3 we can give a proof of Theorem 4.1
Proof. Note that Pt all the conditions in Lemma B. are satisfied by replacing at by b.. Hence we have
F(rr+1) F
11 x=1
T
L
Pt
pibe
V
17
prbr
?97
2h
7
20
D.
t=1
[1 - 11
T
1
Pt
P.b.
n²²
V
+
77)
2h:
21
711
2n
1=1
[ - 11
+ h(A) + g(A).
?m
where the last inequality is by Lemma
B.2
Multiplying both sides by brb we get
|-]==" + h(()) + 9(4)
by
F(rr+1) F
T
By using the upper bound of by in Lemma B.3 finish the proof.
32

---

Published as a conference paper at ICLR 2023
B.3 SECOND VARIANT
Similar to the previous section, what we need to do is to bound the residual term v'll (F and find an upper bound on cr where et b/b
E L + Pt pede 20, " mn 2nj²L
cip: here. We first bound the residual term by the following lemma.
Lemma B.4. If pt & for every t. we have
L
r
)1
T²L
bo
1
2cr
21
G.P
bo
1
t=1
T
Pt
PICI
n/²
V (2))l
2n
2
-
log +
2
717
201²
dpPt
70
7bo
760
1=1
where 4 = b/bb11
1-
Proof. Note that
69
1, this means cıis monotone increasing. We first bound
G-11
6,
T
L
1
2 (((]
20t
2n
cpP
If c1 > n,, we know
Σ
T
L
1
VF(x;)11
<0s
rT²L.
1
bp
+
20r
21)
cipt
bo
1p
1=1
Otherwise, let 7 max {t
E [ S nb}. We have
Σ
T
L
1
17 2
20c
2m/
cip
20tp
1=1
7 L
bi 12
67 b
3-33- 36
1/2
3
1=1
b, b
L
b,b.
1=1
S 1
bo
bz
1/8
Note that e, 1666-11 < nT b, s
nh
Hence
(b, 1
1
80
b0
by
bo
(nL) 1/5
b0
Combinging two cases, there is always
Σ
T
2
by
2c
2n
d.p
bo
Tp
[=1
Now turn to the second bound. If L// we know
Σ
T
Pt.
PiCt
(
0
<
2n
2
--2
log
27L
m
2n
dp
70
7b0
7
33

---

Published as a conference paper at ICLR 2023
Otherwise, we define the time
max (t E
[T] s 2mL/7). Then, have
T
Pt
Pice
r² (
Pt
rj
(x,))
211²
71
Gp
VF(+))
dprt
Us 19-11
"
17 Σ
bt
2-26 b3
62-1
7 1=1
b
1/6
Because 6;6,-1 ce S 2 for t T, we know b, s
2nL
Usinn this bound
7b4
be
2-28
11
24L
3-2
0/
bb-1
by
766
by
t=1
17
2
3 3-2
12
70o
by
[=1
--2
21
1
be
log
7
bbu
bu
2m
2mp
27L
log
76
ybn
7b0
The proof is completed.
As before, our last task is bound eT. It is enough bound by since eT S bbr. Lemma B.S. Suppose all the conditions in Lemma B. are satisfied by replacing by by addition- ally, assume Pt. E 1, we will have
-
3
[1 x1' 11
9L +
+ 70
2nL
log
+
2nL ybo
by
7bp
by < bo exp
1
8
Proof. By Lemma B.1 we know
0 F(IT+1) - F
PrCT
| - 111
T
L
Peee
17 V
71
20
1)
799)
2T
CEPr
7m1
| x=1
L
1
Pt
PIGE
17 F
M FFF)))1
+
711
20r
21
711
2
F.
207
nl v1x))(1
11 121
L
1
Pt.
Pice
r7 (
+
M
20g
21
2
t=1
x²
1 L
by
3
2m
2mL
$-2
2
log
bn
n2
78
ybn
ybo
34

---

' remains true for some Published as a conference paper at ICLR 2023
where the last inequality is by Lemma B.4 Note that for the L.H.S., we have
T
n V
T
bj-
7
b
2-26
bi-1
26
2cppt
2 t=1
01
1-1
2-26
b
b
t=1
be = (1(1
bt
2 (1 - 8)
log b
5)
log
bu
Hence know
3 -
hg
2
2nL
log"
20L 7.00
79'
bg
1T.
7h0
by S by exp
1
Finally, the proof of Theorem 4.3 similar to the proof of Theorem
hence, which is omitted.
B.4 AN ASYMPTOTIC RATE WHEN A 0 AND 8 =
As mentioned before, by setting A = 0 in Algorithm 3 and 5 = 1 in Algorithm 4 we obtain the same algorithm. The square root update rule of b, and the step size now are both more similar to the original AdaGradNorm. Intuitively, we can also expect the convergence of the last iterate in this case; furthermore, by taking the limit when A + 0 and - we can have a sense of the exponential dependency of the provable convergence rate the problem parameters. However, previous analysis strictly requires that A > O and < 1, thus does not apply here.
In this section, partially confirm the convergence of this variant by proving asymptotic rate, i.e, F(oT+1)- F* = (1/T). Unfortunately, under Assumptions and 2', we cannot figure out the explicit dependency of the convergence rate the problem parameters. However, in the next section, we will give an explicit rate by replacing Assumption with the stronger Assumption l'. As stated, our goal prove Theorem B.6lin this section.
Theorem B.6. Suppose F satisfies Assumptions and 2', when A for Algorithm or equiva- lently, 5 = for Algorithm by taking Pt we have
- F F""
Before starting the proof, we first discuss why we can obtain only an asymptotic rate when A = and 5 = 1. As before, one can still expect that F(rr+1) F < byC constant C. However, critical difference will show up when want find explicit upper bound on by. Using the proof of Lemma B.3 as an example (similarly for the proof of Lemma B.5), one key step is to get Et= [VF(2)]]
O(1), where in the previous analysis, by replacing bep.
IVP(201 by 62+A 67+A with A > O, we can lower bound ΣT= Pt
[VF((s)) by function
of by and finally give an explicit bound on br. However, this is not possible when A = as 02-12_
Et. |VF(,,)]
IT
The only information we can get from IT by
- O(1) is 67
02
lim
1. This is not enough to tell us whether by upper bounded or not. Lemma B.8
by
will use rate as desired. is worth pointing out that finding an asymptotic without explicit dependency on the problem parameters is the approach used in some of the previous work, such as Antonnakopoulos et al. (2022). This also gives us a glimpse of the method used to analyze the convergence of the accelerated methods in Section 5]
argument finally show that limy by co, which leads to asymptotic
Now we start the proof. As before, we can employ Lemma B.I Hence we only need to bound the residual terms following
35

---

Published as a conference paper at ICLR 2023
Lemma B.7. Suppose pt I 1, when A = 0 for Algorithm 3
equivalently, 8 1 for Algorithm
we have
T
L
1
17 rf
nL bo
-
26
21)
bipc
[=1
Σ
T
Pt
peb
2n
log
2
ym
2012
blpt
7
bb
1=1
The proof is essentially similar the proof of Lemmas B.2 and B.4 hence omit it here.
Lemma B.8. Suppose all the conditions in Lemma B. are satisfied by replacing by by, then when A for Algorithm 3 or equivalently, 8 = for Algorithm 4 we have
lim bt D0c <0. T T-00
Proof. First note that by is increasing, by the Monotone convergence theorem, we know tem by doo exists. We aim to show boo co. By Lemma B.I and replacing ct by b, we have
F(IT+1)- - F
pr bT
[1 x= 12
L
Pr
Pid,
17 (
2b:
1)
7M11
2012
D.
[1] 112
L
1
Pt.
pebe
1
17² (F=))
+
2b:
21
7!1
21y2T.)
2n
11 - x=' 112
T
Pt.
pebe
n
Fxx))1
+
2b:
21]
71
21
Dipt
21pppt
1=1
21
x= 1|2
+
20
2mL
+
+
log
?
bn
7
7bo
2bp
t=1
where the last inequality is by Lemma
B.7 Noticing F ((T+1)
F* 2 0. we know
T
nl
VF(x)11
x |
1n
2n
log 2nL
2bfP:
7
+
11 bo
-1
+
7
700
which implies
(F(22)11
2||211
x=1
nb
+
24L 700
+2
-1
log
b...
?17
bu
?
We observe that
[F())]]
Pr
= b2
[F(2r)
b7 pr
Taking log to both sides, we get
T
T
log by. = log b3
+
log [VF(1.]1
< log 13 +
|
b7p:
[=1
| F (xx)]]
VF(2.]1
00
log by
bp
S log
13 +
|V [VP())]] bpp.
V F
36

---

Published as a conference paper at ICLR 2023
Note that Inequality ( tells us lim
[V(() pipt
0, hence we can let T the time such that
[V
for
t 2 T. Then know
2
VI
|r(all
|
DPP
bppt
bppt
P(
F(
bipt
biPt
bifs
|F
b7
VF xz )11
+ 2
F
bi.t
bypt
FFx)))]
bf
+
2||21
101
+
-1
4
log
2 ybo
[x+))]]
?p2
bn
?
The above result implies log by has uniform upper bound which means d
Now we can start to prove Theorem B.6
Proof. Note that when A 0 for Algorithm equivalently, ō = 1 for Algorithm 4 all the conditions in Lemma B. are satisfied by replacing ce by bt. Hence we have
if
7
F(rr+1)- - F
J1 - 12
T
Pt
pebe
7 F
prbt
79
2b:
11
Y1
2012
t=1
[11 - 11
L
1
Pt
ptb
17² SIIVEL FF()))1
+
771
2b,
211
777
2
bipt
t=1
[1 - x= 12
27
2n
-1
+
log"
bn
?
700
where the last inequality is by Lemma
B.7
Multiplying both sides bypr we wknow
bt
[1
11
207
2
F(IT+1) rM <
+ 17
1
+ log*
T
71
bo
?
700
0
|
- x²1
+
2n
log + 27L
<
+
-1 1
+
T
by
7
7b0
1
0
T
where the last line is by Lemma B.8
B.5 A NON-ASYMPTOTIC RATE WHEN AND 8 FOR CONVEX SMOOTH FUNCTIONS
In the previous section, only give asymptotic rate when A 0 and 8 1. In the following, we will show that, by replacing Assumption by the stronger Assumption 1', a non-asymptotic rate can be obtained as stated in Theorem[B.9 B.9
Theorem B.9. Suppose F satisfies Assumptions l' and 2', when = 0 for Algorithm 3 or equiv- alently, 8 = for Algorithm 4 by taking Pt 7, we have
[|] 1a-x111 11
2nL bo
-
2n
F(IT+1) F² <
T
where b
max
nk :
bg + V F( )1 exp
21
1/2
+
2nL
bp
-1)
-))
- -1) 1)}}}
I 1m0-00112 + nLy 1
22 bu
1
exp
3|| 3|10)-0"11
+ 3
2n1 bo
37

---

Published as a conference paper at ICLR 2023
We first give another well-known characterization of convex and L-smooth functions without proof. Lemma B.10. Suppose F satisfies Assumption I' and 2', then Vz, y IR
(VF(x) (f()), [VF(() VF())
I.
Next, we state a simple variant of Lemma B.I the proof of which is essentially the same as the proof of Lemma B.1 hence we omit Lemma B.11. Suppose the following conditions hold:
F satisfies Assumptions I' "andd" 2';
* P: E (0, 1) satisfies
1-P:11
P1 = 1. P++1
When A = ffror Algorithm
or equivalently, 5 = 1 for Algorithm
4
we have
F( -
F
L
1
Pt
of
V (x::)l
prby
27
2b
7
2m
b
The same as Lemma B.7 we give the following bound on the residual term without proof.
Lemma B.12. Suppose ps < 1, when = 0 for Algorithm 3 or equivalently, 6 = for Algorithm
we have
L
1
(F)))
2nL
Σ
2bt
4n
biPt
2
Again, the above two lemmas give
||-] - 11112 217
+
F(#1+1) F* br
1
(8)
2m
bg
W.l.o.g,, we assume by ph in the following analysis. Otherwise, we can use the bound by S nI. 2
get trivial convergence rate. Now define the time
{
{ E [T],
n S 2 vo.
max
This time 7 extremly useful and will finally help us bound by. Now we list the following three important lemmas related to time 7. Lemma B.13. With Assumptions 1' andd 2', when t 2 2 [[F((z)) is non-increasing.
Proof. Taking Fzay 1 in Lemma B.10 get
(x)) V V
{(FF(a)) V F x(t1)
= (VF(I.) VF(4+1)), [VF(I))
by
- (2- |VF( 1IF 2
?
", (VF())), VF(
Note that when 2 1, 1, we know by of + 1/
by
> 0, hence we have
||F((x))1 + |F
by
(VF(zt), VF(I++1)
L by
n
|VF(2=)]| + ( 7
-
2b,
which implies [F( < IVF(())) This is just what want.
38

---

Published as a conference paper at ICLR 2023
Lemma B.14. With Assumptions 1' and 2'. if when t 2 7 7 2
|VF(1))
X 3
Proof. This is because
V VF(2)1?
t| (xx))11 ?
6.p.
b/ + Ei i V (2:))1
$ (1- (22
$ (1 =
21 -
where the last inequality is because
1 2 T + hence ||VF(=-))|| 2 |[V[())] by Lemma
B.13
Note that / 2 2, so [VF(2)]
< 21- S 3
1
BEPt
Lemma B.15. With Assumptions 1' ana 2', if =
by+1 S bb + (VF()))) v 1
[1 -
x
2n/
-1
112
bn
Proof. If = 0, we have
b,41 = 18 + /F
Otherwise, we know + 12 2, hence
62 = 6, + (T + 1V
$ b3 2L +1 (F (x++1) -F))
< b + 2T, 7 +1 11 by
|:01 - -x112
-1) -2)
(21/L
2np
2m
2 bo
$ 6 + 4Lb,
| x=1
+ 17
2nL
-1)
2m
2
bo
1
|2] - x011
+ nj2 L2
tbo -
2
112
||- - w=11
(2m
bb++ S nT,
+
-
112
bu
where the second inequality is due to
8
Now we combine Lemmas B. and B.15 to get an upper bound for by.
Lemma B.16. With Assumptions / and 2', if =
nL 2
3||21 - 1=12
12L
by < max
b3 + VF(
+3
-
172
by
+ |xg
12
12nL bo
3 3|/01 - x 1²
12
7L
+
-1
exp
+ 3
-11
122
172
bo
39

---

Published as a conference paper at ICLR 2023
Proof. Note that if by I nL 2. are done. If by
ni
2
we will bound by as follows:
(xT))12
b = 1
Pr
02
7 by
12 r+1
II
[F(2r]11 11
V ((.))
1|
1
bIPT
t
p/
3 log bi S log b? 41 +
Σ
log
1
1
1=++2
bppt
VF(+I12
< log bZ 17+1% +
[VF(2)]
t= +
bipt
31 F=)))))
I log b2
7+1
+
bipt
1=
where the last inequality is by Lemma B.14 B.12 we can find
Noticing p: = S 1, combining Lemmas B.1 and
2 2
x² 1²
2npl.
-1)
+2
bept
112
bo
Hence we know
3/ |
log by. S log 62
7+1
+
Σ
bipee
1=
61|01] xx 11
2np..
+
< log 62 7+1
+
6
-
1/2
bn
6||
x=11
2
1 ")
+
b7 S 62 42 exp
6
1/2
bo
The last step is to use the bound on b,+1 in Lemma
B.15
Finally, the proof of Theorem B.9 is obtained by simply using Lemma B. to Equation {
C MISSING PROOFS FROM SECTION
C.1 IMPORTANT LEMMA
First, we state a general lemma that can be used for a more general setting. The proof of the lemma standard.
Lemma C.1. Suppose F satisfies Assumptions I' and 2' and the following conditions hold:
we is generated by
0t- = (1 - (r) )w,, + ae
D++1 = Ft " VF()))
qiat
Wh+1 (1 W, a,3141
with 17 > O and > 0 is non non-decreasing:
ar E (0, 1] and qi 2 as satisfy 1 >
1-a01 01 = acq a4419441
Then we have
F(WT+1) - F* <
|||| x²
T
L
V (2))
aTqreT
21
2b,
21)
2
t=1
40

---

Published as a conference paper at ICLR 2023
Proof. Starting from smoothness
F(w(-1)- F(v))
S(VF(v)), Wh+1 -v) + L |w++1 vell
=(1 (VF v2) + a. 2441 14) + , vell
|10t+11
-(1 a,) ( (VF w m u. (VF(e) x² - vz) + a. (VF((()) 21+1 - x²) + [l - well
5(1 - a. (F(w)) F(u))) + + F(e))) + I1+1 x²) + 2 |1 - w/ll
Thus
F(W(41) F = (1- FT) + a. (VF()))))))))))))))))))))))))) 0141 x²) + ||00+1 - well
where the last inequality is due to the convexity of F. gett (Ie 1x+1) and Wr+1 - 2 = at (I1+1 xz) obtain
Using the update rule VF(w)) =
7
F(W++1) F S (1
F*)
agqcct
||
xzll²
-|x==
La, 11? -1|2211 sall²) +
| xell
21
2
Dividing both sides by agqec, and sumning up from to T, we have
T 1 -F(w+)))
Σ
- F*) S
-- at (F(w:) - FF)
agqict
aeqict
Lar
1
|
=1112 2n
1|x0 x11"
2q10:
211
t=1
Note that 04 S 9t, argect
2 1-4r41 and ar = 1. Thus
04119411441
F(wT+1) - F
|00 - x11
T
1
|| - x
aTΩTCT
2m
2b.
21)
1=1
[1 x 1²
L
1
217
2b,
2m
c.
1=1
C.2 FIRST VARIANT
By using Lemma C.I the proof idea of Theorem 5.1 is the same as the proof of Theorem 4.1 Hence, omit it for brevity.
C.3 SECOND VARIANT
By using Lemma we omit here.
C.I the proof idea of Theorem 5.3 the same as the proof of Theorem 4.3
Hence,
C.4 A DISCUSSION ON WHEN A AND
Algorithms 5 and 6 become one when A and 8 As discussed in B.4 find a explicit bound on by. First, we give an asymptotic rate Theorem C,2 idea is the same as the proof of Theorem B.6 thus is omitted.
the challenge is to
which the proof
41

---

Published as a conference paper at ICLR 2023
Theorem C.2. Suppose F satisfies Assumptions I and 2', when A 0 for Algorithm lently, for Algorithm by taking a₁ 2+1' 1² we have
equiva-
F(WT+1)- - (1/Tg).
Now, we aim to prove the following non-asymptotic rate.
Theorem C.3. Suppose F satisfies Assumptions / and 2', when A = 0 for Algorithm S lently, 8 for Algorithm by taking at
equiva-
2 Pt 4. we have
{600
4n ba
1121=2"12
I'L log"
7h 60
16L
[ 11i-x" [[_
log
n..
2n
bo
2nj
F(WT+11) - F* S
T(T
T +
1
We shortly discuss here why we can only give a rate in the order of 1/T but not 1/T Recall that in the proof of Theorem B.9. the key step that after a certain time, |/V ]I is non-increasing sequence, by using which we can finally give constant upper bound on by that finally helps us to get the final 1/7 rate. However, it is unclear under what condition on b,, [VF()))) now will be non-increasing sequence in our accelerated algorithm. Thus it is unclear possible to give constant bound on by. Instead, we will show b, can increase at most linearly in this accelerated scheme by new trick, for which reason, we can finally obtain the rate in the order
whether it is
of 1/T. This guarantees that the convergence of the last iterate no worse than the variants in Section 4
Proof. As before, to start with, we use Lemma
C.I
F(WT+1) - F
L
1
n
V F
(2)))1
arQIbr
21
2b,
2m
02
By using by - 01%1111 +
[VF((e)) and the same technique in the previous proof, we know b7
Σ
L
1
17
5
1/L to
log
1 bo
2hg
2n)
bZ
So we have
[2] 11
L
nL bo
F(WT+1) F I orgrbT
log"
21
bo
Now we turn to bound b, by observing
[V:(2))]
b7 = b +
< 1 + 2 2[) VF(W41113
F(
2L 11 w++1ll
<b <b +
of
2I 0f 1 - x3 11?
2 V F ((
b +
2
2
12
b3
2T.2
|
12
42

---

Published as a conference paper at ICLR 2023
(2 1167-b7-
where the last inequality is due to a₂ S Then we use 111-111111
1/
62
and || [V(++++))] & (L((F()+1) - F*) $ LL to get
b/ < b/-1 + 21 (b} b9-1)
DLa,
21/² L (b)
b)-1)
by
+4Lb,D
b7
b
b
b, S
+ 2n/² 1,?
+ AL.D
bt
by
$ 11-1 2 1
1
1
+ 4LD
bi-1
by
212
b, S bo
4LDI.
bp
Using this bound, we finally get
F(WT+1) - F S arQrOTD D
bo
1=2 + ALDT) D
by
T(T 1)
60
12 by
||11="1
x
log
nL bn
16L
2 L
log
nL
2
2n
by
2n
bp
bo
T(T
T +
1
D EXPERIMENTS
10
762--7
10
10
AdaGrsftirm Last
dveraged
LesoredNerr-Lstt cpsivoernty. 2-13
AouGredNem--oot 1600
AesGreaNomm. Last 1-
1079
ReaGredfaammAes equiakkentyy
Aeudteeteernscc (0
Figure I: Function value gap for different algorithms
In this section, we provide empirical evidence to compare the performances of our algorithms in the deterministic setting. Our test function follows the quadratic function used to prove the lower bound of the first order method constructed by Nesterov (Nesterov et al.) 2018). That is
F F(x) = r11 + x 2 + Ed-1 ===
(xl
rii 11)²
x z(1].
2
43

---

Published as a conference paper at ICLR 2023
where æ[i] refers to the i-th coordinate of point R It is known that F is 4-smooth and convex with the unique minimizer
i [+] = d 1
Vi E [d].
We fix d 101 and set the time horizon to T 1000 in the test. The starting point æ) is initial- ized randomly satisfying that every coordinate is uniformly chosen in [0, 1). All algorithms share the same ø1- For the adaptive algorithms, we choose by 10 and set
without any fur- ther tuning. We also compare with an accelcrated algorithm Lan 2020), which requires using the smoothness constant I.
The result is shown in Figure 1 We can find that our Algorithms and admit the last iterate convergence. Additionally, both our accelerated algorithms, i.e., Algorithms and o enjoy the accelerated property without knowing the smoothness parameter and are competitive against Ac- celerated Gradient Descent (Lan) 2020) which requires the smooth parameter to set the step size. Another interesting observation is that it seems AdaGradNorm also exhibits the last iterate conver- gence. However, whether this is indeed property of AdaGradNorm has not been confirmed by the theory. We leave this future direction.
44


Reviews:
[{"review_id": "atuT1NekulR", "reviewer": "Reviewer_sbsF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces some new analysis technique of the convergence of AdaGrad on the unbounded domain, in the smooth convex optimization setting. The authors prove that several variants of AdaGrad can converge (in both average and the last literature sense) to the optimum without the need of additional assumptions. ", "summary_of_the_review": "In summary, I do like the idea of the paper as a theory person. However, I just feel like it should be further improved in its current form. \n\nI highly appreciate the authors for trying to find new ways to prove the convergence of AdaGrad, and its variants, and I believe the results could be very significant. Extending the current results to, e.g., stochastic AdaGrad, last iterate convergence of AdaGrad would be much more interesting than dealing with the variant AdaGradNorm. Or extending the results to the nonconvex setting would be very interesting. \n\nThat being said, the above suggestions may make the paper a bit too-long and too technical for a (mostly deep-learning) conference like ICLR, I would suggest re-submitting to ML journals like JMLR, or theory conferences like COLT.\n\nI am happy to change my rating if the authors can convince me of their contributions.", "strength_and_weaknesses": "Strength:\n  1. The proposed analysis techniques are, as far as I am aware, novel and interesting\n  2. The authors have formulated the analysis in a way that is easy to understand their contributions\n\nWeaknesses:\n\n  Before I start talking about the weakness, I want to emphasize that, as a theory person, I highly appreciate the authors for trying to figure out different ways to provide the convergence analysis of algorithms. Although I don't really have enough time to read all the proof details, the analysis that the authors try to provide are very interesting and potentially impactful. \n\n  However, I have the feeling that the paper is a bit over-selling, or the results presented are not really matched with the authors' claims. Most of the paper is concentrated on a variant of AdaGrad, AdaGradNorm, which I admit that I am not familiar with. I think it is not very popular, and the analysis techniques that the authors have used for this algorithm, maynot be easily transferrable to the vanilla AdaGrad algorithm. I tried to read some parts of the Appendix as well, and it seems that the only setting that the authors have provided analysis on AdaGrad is, the deterministic setting (Sec A.3). The stochastic version of AdaGrad is not analyzed.\n\n  Moreover, the nice properties and the variants are all proposed based on the AdaGradNorm algorithm, instead of the original AdaGrad algorithm. Can we propose similar variants for AdaGrad and get similar properties? This makes it also hard to interpret the results as a more advanced/detailed analysis of AdaGrad, but rather AdaGradNorm. Therefore, I feel the results in this paper are important, but the way the authors sell them are not completely aligned with the results.\n\n  Finally, the results are established under the quasar-convex setting, and I wonder whether they can be further extended to the nonconvex setting. (I have a very strong feeling that this can be done easily since in the nonconvex setting, similar things such as the telescopic sums in Sec 3.1 appear in the analysis too). Some (simple and synthetic) experimental results that support the correctness of the theorems will be highly appreciated.\n\n\n*After Rebuttal*\n\nI thank the authors for a nice rebuttal. I have increased my rating.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Wgtbk-W6nA", "reviewer": "Reviewer_qVCv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence of AdaGrad and its variants over the convex objectives. Specifically, the authors first prove the convergence of AdaGrad-Norm both in the deterministic case and in the stochastic case. Compared to existing results, the derived results remove the bounded domain assumption. The authors then propose two types of variants of AdaGrad. The first type can ensure the last iterate convergence in the deterministic case and the second can achieve a faster convergence rate.", "summary_of_the_review": "Despite that the results do improve those in the existing literature, I find that the studied problem is less interesting, the theoretical results may be further improved, and the proposed algorithms need to be justified in more detail. ", "strength_and_weaknesses": "**Strength**\n\n1. The presentation of this paper is clear and it is easy to understand the results of this paper and the proof technique.\n\n**Weakness**\n\n1. I am not sure whether understanding the convergence of AdaGrad in the convex regime is an important question. First, to the best of my knowledge, AdaGrad is seldomly adopted in machine learning practice, especially in deep learning. Second, I think that it is more important to study the non-convex setting.\n\n2. The current logic and organization of this paper need to be improved. The current organization of this paper seems to \"collect\" all the results. For example, AdaGrad-Norm Last is proposed to ensure the last iteration convergence of AdaGrad-Norm. But does AdaGrad-Norm really fail to converge in terms of the last iteration or it is just due to the limitation in proof? Discussion is needed here.\n\n3. While removing the bounded domain assumption, the result for the stochastic case is still somewhat restricted. For convex objectives, SGD is known to converge with the bounded noise variance assumption, which is strictly weaker than the sub-gaussian noise assumption. Can similar results be derived for AdaGrad-Norm?\n\n4. While Section 1.1 claims \"show an explicit non-asymptotic convergence rate of AdaGrad-Norm and AdaGrad on $R^d$ in the deterministic setting\", I only find such a result for AdaGrad-Norm (Theorem 3.1). Did I miss something?\n\n5. I feel that the authors need to include some experiments to justify the usefulness of the proposed AdaGrad-Norm variants. For example, does AdaGrad-Norm-Acc really converge faster than AdaGrad-Norm over convex objectives? Also, what is the advantage of AdaGrad-Norm-Acc over Nesterov's momentum given that they can both achieve the lower bound of the convergence rate?\n\n6. There are missing related works. Faw et al. (2022) derive the convergence of AdaGrad-Norm in the non-convex setting with the least assumptions. They also provide detailed references to the works studying the convergence of AdaGrad.\n\n**References**\n\nFaw et al., The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance, 2022", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Oo4GJlIOx4B", "reviewer": "Reviewer_iRiy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a theoretical analysis of AdaGradNorm which is a variant of AdaGrad in the unconstrained domain. As much as it is known this is the first analysis that extends the convergence analysis of Adagrad to the unconstrained domain. They analyze both deterministic and stochastic settings. The analysis is provided for the quasar-convex that is bigger than the class of convex functions and includes it. Finally, they also propose accelerated variants of AdaGradNorm in the deterministic setting with convergence analysis which indicates the acceleration occurs compared to Non-accelerated variants. \n", "summary_of_the_review": "\nComments: \n1- As an empirical justification, it would be useful to include some empirical results for your accelerated variant in the paper. \n\n2- Although your title is about analyzing AdaGrad the analysis is actually for AdaGradNorm. I suggest either changing the title or extending your analysis for the vanilla/general AdaGrad. \n\nMinor comments: \n1- Adding numbers for your important equations would be helpful. \n2- In the 2nd last eq in page 6, I guess a \\sum is missing. \n", "strength_and_weaknesses": "As much as it is known this is the first analysis that extends the convergence analysis of Adagrad to the unconstrained domain. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster