High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize
Authors: Ali Kavis
Kfir Yehuda Levy
Volkan Cevher
Venue: ICLR 2022 Poster (2022)
Keywords: adaptive methods
nonconvex optimization
stochastic optimization
high probability bounds

Abstract: In this paper, we propose a new, simplified high probability analysis of AdaGrad for smooth, non-convex problems. 
More specifically, we focus on a particular accelerated gradient (AGD) template (Lan, 2020), through which we recover the original AdaGrad and its variant with averaging, and prove a convergence rate of $\mathcal O (1/ \sqrt{T})$ with high probability without the knowledge of smoothness and variance. 
We use a particular version of Freedman's concentration bound for martingale difference sequences (Kakade & Tewari, 2008) which enables us to achieve the best-known dependence of $\log (1 / \delta )$ on the probability margin $\delta$. 
We present our analysis in a modular way and obtain a complementary $\mathcal O (1 / T)$ convergence rate in the deterministic setting. 
To the best of our knowledge, this is the first high probability result for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness and uniform variance bound, which simultaneously has best-known dependence of $\log( 1/ \delta)$. 
We further prove noise adaptation property of AdaGrad under additional noise assumptions.

Published as a conference paper at ICLR 2022
HIGH PROBABILITY BOUNDS FOR A CLASS OF NON- CONVEX ALGORIHTMS WITH ADAGRAD STEPSIZE
Ali Kavis
Kfir Y. Levy'
Volkan Cevher
EPAL (LIONS)
Technion
EPFL (LIONS)
all f. fakvvsss @epfl.co ch
kfirylevy
vo 1 kan, cevher
@technion.ac.ii
@epfl.
ABSTRACT
In this paper, we propose new, simplified high probability analysis of AdaGrad for smooth, non-convex problems. More specifically. we focus on particular accelerated gradient (AGD) template (Lan, 2020), through which we recover the original AdaGrad and its variant with averaging, and prove convergence rate OL/vVT) with high probability without the knowledge of smoothness and variance. We use particular version of Freedman's 's concentration bound for martingale difference sequences (Kakade & Tewari, 2008) which enables us achieve the best-known dependence of log(1/8) on the probability margin 6. We present our analysis in a modular way and obtain a complementary (1/TT) convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability result for AdaGrad with a truly adaptive scheme, i.e., completely oblivious the knowledge of smoothness and uniform variance bound, which simultaneously has best-known dependence of log(1/0) We further prove noise adaptation property of AdaGrad under additional noise assumptions.
INTRODUCTION
Adaptive gradient methods are staple of machine learning (ML) in solving core problems such as
min f(x) == E.-D [x;; wERd
(P)
where the objective fz) possibly non-convex, and D is a probability distribution from which the random vector is drawn. Problem (P) captures for instance empirical risk minimization or finite-sum minimization (Shalev-Shwartz Ben-David, 2014) problems, where = represents the mini-batches and D corresponds to the distribution governing the data or its sampling strategy.
Within the context of large-scale problems, including streaming data, computing full gradients extremely costly, if not impossible. Hence, stochastic iterative methods are the main optimizer choice in these scenarios. The so-called adaptive methods such as AdaGrad (Duchi et al., 2011), Adam (Kingma & Ba. 2014) and AmsGrad (Reddi et al., 2018) have witnessed surge of interest both theoretically and practically due to their off-the-shelf performance. For instance, adaptive optimization methods are known to show superior performance in various learning tasks such as machine translation (Zhang et al., 2020; Vaswani et al., 2017).
From a theoretical point of view, existing literature provides quite comprehensive understanding regarding the expected behaviour of existing adaptive learning methods. Nevertheless, these results do not capture the behaviour of adaptive methods within a single/few runs, which is related the probabilistic nature of these methods. While there exists high probability analysis of vanilla SGD for non-convex problems (Ghadimi & Lan, 2013), adaptive methods have received limited attention in this context.
Our main goal in this paper is understand the probabilistic convergence properties of adaptive algorithms, specifically AdaGrad, while focusing their problem parameter adaptation capabilities the non-convex setting. In this manuscript, adaptivity refers to the ability of an algorithm to ensure
Viterhi fellow

---

Published as a conference paper at ICLR 2022
convergence without requiring the knowledge of quantities such smoothness modulus variance of noise. Studies along this direction largely exist for the convex objectives; for instance, Levy et al. (2018) shows that AdaGrad can (implicitly) exploit smoothness and adapt to the magnitude of noise in the gradients when (x) is convex in (P).
This alternative perspective adaptivity is crucial because most existing analysis, both for classical and adaptive methods, assume to have access to smoothness constant, bound on gradients (Reddi et al., 2018) and even noise variance (Ghadimi & Lan, 2013). In practice, it is difficult, if not impossible, to compute or even estimate such quantities. For this purpose, in the setting of (P) we study a class of adaptive gradient methods that enable us to handle noisy gradient feedback without requiring the knowledge of the objective's 's smoothness modulus, noise variance or a bound on gradient norms.
We summarize our contributions as follows:
1. We provide a modular, simple high probability analysis for AdaGrad-type adaptive methods.
2. We present the first optimal high probability convergence result of the original AdaGrud algorithm for non-convex smooth problems. Concretely,
(a) we analyze a fully adaptive step-size, oblivious to Lipschitz constant and noise variance,
(b) we obtain the best known dependence of log( (1/5) on the probability margin 8.
(c) we show that under sub-Gaussian noise model, AdaGrad adapts to noise level with high probability, i.c, as variance o + O, convergence rate improves, 1/vT - 1/T.
3. We present new extensions of AdaGrad that include averaging and momentum primitives, and prove similar high probability bounds for these methods, as well. Concretely, we study a general adaptive template which individually recovers AdaGrad, AdaGrad with averaging and adaptive RSAG (Ghadimi & Lan, 2016) for different parameter choices.
In the next section, we will provide a broad overview of related work with an emphasis on the recent developments. Section 3 formalizes the problem setting and states our blanket assumptions. Section 4 introduces the building blocks of our proposed proof technique while proving convergence results for AdaGrad. We generalize the convergence results of AdaGrad for a class of nonconvex, adaptive algorithms in Section 5. Finally, we present concluding remarks in the last section.
2 RELATED WORK
Adaptive methods for stochastic optimization As an extended version of the online (projected) GD (Zinkevich, 2003), AdaGrad (Duchi et al., 2011) is the pioneering work behind most of the contemporary adaptive optimization algorithms Adam, AmsGrad and RmsProp (Tieleman & Hinton, 2012) to name few. Simply put, such AdaGrad-type methods compute step-sizes on-the-fly fly-fly by accumulating gradient information and achieve adaptive regret bounds as a function of gradient history (see also (Tran & Phong, 2019; Alacaoglu et al., 2020b; Luo et al., 2019; Huang et al., 2019)).
Universality, adaptive methods and acceleration We call an algorithm universal if it achieves optimal rates under different settings, without any modifications. For convex minimization problems, Levy et al. (2018) showed that AdaGrad attains rate of O(1/T a /VT by implicitly adapting to smoothness and noise levels; here 7 is the number of oracle queries and a is the noise variance. They also proposed an accelerated AdaGrad variant with scalar step-size. The latter result was extended for compactly constrained problems via accelerated Mirror-Prox algorithm (Kavis et al., 2019), and for composite objectives (Joulani al., 2020). Recently, Ene et al. (2021) have further generalized the latter results by designing novel adaptive, accelerated algorithm with per-coordinate step-sizes. Convergence properties of such algorithms under smooth, non-convex losses are unknown to date.
Adaptive methods for nonconvex optimization Following the popularity of neural networks, adaptive methods have attracted massive attention due to their favorable performance in training and their ease of tuning. The literature is quite vast, which is impossible to cover exhaustively here. Within the representative subset (Chen et al., 2019; Zaheer et al., 2018; Li & Orabona, 2019; Zou al., 2019; Defossez et al., 2020; Alacaoglu et al., 2020a; Chen et al., 2020; Levy et al., 2021). The majority of the existing results on adaptive methods for nonconvex problems focus on in expectation performance.
2

---

Published as a conference paper at ICLR 2022
High probability results Ghadimi & Lan (2013) are the first to analyze SGD in the non-convex regime and provide tight convergence bounds. Nevertheless, their method requires a prior knowledge of the smoothness modulus and noise variance. In the context of adaptive methods, Li & Orabona (2020) considers delayed AdaGraa (with lag-one-behind step-size) for smooth, non-convex losses under subgaussian noise and proved
rate. Under similar conditions, Zhou et al. (2018) proves convergence of order (( log(1 (og(1/6))/7 + 1/vT) for AdaGrad. However, both works require the knowledge of smoothness to set the step-size. Morcover, Ward et al. (2019) guarantees that AdaGrad with scalar step-size convergences at (((1)) log(()/vV? rate with high probability. Although their framework is oblivious smoothness constant, their dependence of probability margin is far from optimal. More recently, under heavy-tailed noise having bounded pd moment for p E (1, 2), Cutkosky Mehta (2021) proves a rate of (log / (r(p-1)/(pp----1 for clipped normalized SGD with momentum; nevertheless their method requires the knowledge of (a bound on) the behavior of the heavy tails.
SETUP AND PRELIMINARIES
As we stated in the introduction, we consider the unconstrained minimization setting
min f(x) := Ez-D [f =)],
aERd
where the differentiable function f: R IR is smooth and (possibly) nonconvex function.
We are interested in finding first-order e-stationary point satisfying f < where |i-I| de- notes the Euclidean norm for the sake of simplicity. As the standard measure of convergence, we will quantify the performance of algorithms with respect to average gradient norm, + E [Vx+)]]]
immediately implies convergence in minimum gradient norm, min (f Moreover, note that if we are able bound T Σ [f(=))] then by choosing to output solution ör which is chosen uniformly at random from the set of query points {Ii,..., Fr)), }, then we ensure that E|| J ( == + Σ [ is bounded.
function is called G-Lipschitz continuous if satisfies
f(x) - f(y) s G æ - vll, Vx, E dom(f),
(1)
which immediately implies that
[ S G, Vz E dom(f).
(2)
differentiable function is called L-smooth if it has L-Lipschitz gradient
[))()) v < T||= yll, Yr, E dom(V.).
(3)
An equivalent characterization is referred to as the "descent lemma" (Ward et al., 2019; Beck, 2017).
[f(z) - f()) - (V f(w), x - w\ s (L/2)]l= w112.
(4)
Assumptions on oracle model: We denote stochastic gradients with ff(x) V fz; ) for some random vector drawn from distribution D. Since our template embraces single-call algorithms, we use this shorthand notation for simplicity. An oracle is called (conditionally) unbiased if
E
[=]]]] = fz(z), Vz E fV....
(5)
Gradient estimates generated by first-order oracle are said to have bounded variance if they satisfy
[(li)(x) - [x]]]] < a V E (Vom(V.).
(6)
Finally, we assume that the stochastic gradient are bounded almost surely, i.c..
[V < G, Vx E dom(V.))
Remark 1. Bounded variance assumption (6) is standard in the analysis of stochastic methods (Lan, 2020). Similarly, for the analysis of adaptive methods in the nonconvex realm, it is very common to assume bounded stochastic gradients (see (Zaheer et al., 2018; Zhou et al., 2018; Chen et al., 2019; Li & Orabona, 2020) and references therein).
3

---

Published as a conference paper at ICLR 2022
4 PROPOSED ANALYSIS AND ADAGRAD
This section introduces our proposed proof technique as well as our main theoretical results for AdaGrad with proof sketches and discussions on the key elements of our theoretical findings. We will present a high-level overview of our simplified, modular proof strategy while proving complementary convergence result for AdaGrad under deterministic oracles. In the sequel, we refer to the name AdaGrad as the scalar step-size version (also known as AdaGrad-Noma as presented in Algorithm 1.
Algorithm I AdaGrad
Input: time horizon T I1 E Rd, step-size ( Go > 0
I: for = 1.... T do
2:
Generate Gr f(z))
3:
1/: V G 11.. ||
4: 2++1 24 11.9t
5: end for
Before moving forward with analysis, let us first establish the notation we will use to simplify the presentation. In the sequel, we use [T] shorthand expression for the (1,2, T) We will use A, = f(x)) - min f(x) as a concise notation for objective suboptimality and A Amax max A, will denote the maximum over A,. In the rest of Section 4, we denote stochastic gradient of f at by 9t f((x)) (a ze) and its deterministic equivalent as Gr = (z(e).. We also use the following notation for the noise vector & := 9t: Gt.
Notice that AdaGrad (Alg. 1) does not require any prior knowledge regarding the smoothness modulus nor the noise variance. The main results in this section is Theorem 4.2, where we show that with high probability AdaGrad obtains an optimal rate ((lo((//))/VT) for finding an approximate stationary point. Moreover, Theorem 4.1 shows that in the deterministic case AdaGrad achieves optimal rate of O(/TT), thus establishing its universality.
4.1 TECHNICAL LEMMAS
We make use of few technical lemmas while proving our main results, which we refer our proof sketches. We present them all at once before the main theorems for completeness. First, Lemmas 4.1 and 4.2 are well-known results from online learning, essential for handling adaptive stepsizes.
Lemma 4.1. Let 01, On be a sequence of non-negative real numbers. Then, holds that
a
a
0
ag
a2
Σk= ak
Lemma 4.2. Let 01, ... be sequence of non-negative real numbers. Then, it holds that
< 1 + log
1
a₁
1=
1=1
The next lemma is the key for achieving the high probability bounds.
Lemma 4.3 (Lemma Kakade & Tewari (2008)). Let X, be martingale difference sequence such that [X|] < b. Let also define
Var,-1(X;) Var (X, Xi,..., X.-1) E [X] XI...., (....)
and VT Et
Var.- (X+) as the sum of variances. For 8 < 1/e and T 2 3, it holds that
T
PP
X > max (2V 36
V2VVV,36 log(1/8) Vlog(1/8) < 4 log(T)6
(8)
4

---

Published as a conference paper at ICLR 2022
4.2 OVERVIEW OF PROPOSED ANALYSIS
We will start by presenting the individual steps of our proof and provide insight into its advantages. In the rest of this section, solely focus AdaGrad, however, the same intuition applies to the more general Algorithm 2 as we will make clear in the sequel. Using the shorthand notations of Jr (xz) and 9t 2)( = gr- + E,, the classical analysis begins with,
Lui |1
(z4+1) ((x,) S - To (0e, Ex)
which is due to the smoothness property in Eq. (4). Re-arranging and summing over 1 (T) yields,
I. Σ nh 11
Σ nelloall S f(x1) - f(x") + Σ ni (o
The main issue in this expression is the ne Ei) term, which creates measurability problems due to the fact hat T)e and & are dependent random variables. On the left hand side, the mismatch between " and l 2 prohibits the use of technicals lemmas as we accumulate stochastic gradients for Vh-- Moreover, we cannot make use of Holder-type inequalities as we deal with high probability results. Instead, we divide both sides by Th, then sum over and re-arrange obtain a bound of the form,
T
L (x)
1
A
me nel1
7J1
Tk
Th-
2
1=2
t=1
A
L 2
max
(gr, Et)
nc 11a 1|
T/
This modification solves the two aforementioned problems, but we now need to ensure boundedness of function values, specifically the maximum distance the optimum, Amax. In fact, neural networks with bounded activations (e.g. sigmoid function) in the last layer and some objective functions in robust non-convex optimization (e.g. Welsch loss (Barron, 2019)) satisfy bounded function values. However, this is restrictive assumption make for general smooth problems and we will prove that it is bounded or at least it grows no faster than OloggT))) As a key element of our approach, we show that is the case for Alg. 1 & 2. Now,
position to state overview of our proof:
1. Show that AmIx S O(log(() (T)) with high probability or Amax I 0(1) (deterministic).
2. Prove that ΣT (gr, &1) < Ö(VT) with high probability using Lemma 4.3.
3. Show that L T ET Thl 9el2 O(VT) by using Lemma 4.1.
For completeness, we will propose a simple proof for AdaGrad in the deterministic setting. This will showcase advantages of our approach, while providing some insight into it. We provide sketch of the proof, whose full version will be accessible in the appendix.
Theorem 4.1. Let xe be generated by Algorithmm I with Go 0 for simplicity. Then, it holds that
1 T
(
( + L)3
+)²
[+(x)) 50
T
Proof Sketch (Theorem 4.1). Setting 9r fxx)), deterministic counterpart of Eq. (9) becomes
T Σ
T
T
|
max
L
Th ||
S max L)
Σ
12
2
T/T
t=1
where we obtain the final inequality using Lemma 4.1. Now, we show that AT+1 is bounded for any T. Using descent lemma and summing over E [T'.
Ln
- - = f(x1) - f(x²)
1) 11
2
5

---

Published as a conference paper at ICLR 2022
Now, define to max {t E [T]] n > } such that
Lii
1) I for any t to Then,
((oT+))-((x") S A +
Σ
to
Lite
-1
T/e 1111
Σ
Lite -1) nhe 1r:1
2
t=
L
L (1 log
SA
ge
||
S A +
log (1
L+/44))
2
t=1
where the definition of lg and Lemma 4.2 for the last inequality. Since this is true for any T, the bound holds for A max. as well. Defining X V - | the original expression reduces to X² & (Amax + L) X. Solving for X, plugging in the bound for Amax and dividing by T results in
1 T
(
+ log (T2/4)))
Vf(=))]
T E=1
T
Remark To our knowledge, the most relevant analysis was provided by Ward et al. (2019), which achieves (log(())/T convergence rute. Our new approuch enables us to remove log( (T) factor.
4.3 HIGH PROBABILITY CONVERGENCE UNDER STOCHASTIC ORACLE
Having introduced the building blocks, we will now present the high probability convergence bound for AdaGrad (Algorithm 1). Let us begin by the departure point of our proof, which is Eq. (9)
max
Cgt Ee)
L
me 1l19
(10)
T/
2
(*8)
(***)
We can readily bound expression (* using Lemma 4.1. Hence, what remains is to argue about high probability bounds for expressions (*) and (**), which we do in the following propositions.
Proposition 4.1. Using Lemma 4.3, with probability 1 4 log(T)ō and 5 < 1/e, we have
T
T Σ t=1
Ee) S 20 1og(1/8)
12 3(2 + GG))og(1/6).
The last ingredient of the analysis the bound on A. The following proposition ensures a high probability bound of order (log(t)) A, under Algorithm 1.
Proposition 4.2. Let be generated by AdaGrad Go > 0. With probability at least - 4log(!)8,
A s A 2T. (1 log (max (1, + (21) + '6''M, + 02) ( (18( M2.
where M₁ = 3G2 + GG) and M2 = Go (2G + GG).
As an immediate corollary, since the statement of Proposition 4.2 holds for any t, holds for Amax by definition. Hence, we have that max4e (r] A; Amax < O (A1 L log(T) + o² log(1/8)) with high probability for any time horizon T.. In the light of the above results, we are now able to present our high probability bound for AdaGrad.
Theorem 4.2. Let Ti be the sequence of iterates generated by AdaGrad. Under Assumptions 2, 6, for Amax < 0 (Ai + L log(T) + o log(1/))), with probability at least 1 - 8 log(T")
T
(Amax + L) Go + 3(2 + GG))og((/8) + (Amox + I. + 2Go / Tog(118)
T
T
VT

---

Published as a conference paper at ICLR 2022
Proof Sketch (Theorem 4.2).
Define Ft
(x() and gr Vf(= 2))
9t + &c. By Eq. (10),
T
T
T
Σ 1=1
Oc. Ei) +
m 19
Tf
t=1
t=1
Invoking Lemma 4.1 on the last and using Proposition 4.1 for the second expression, have with probability at least 4 log(T))
T
T
T Σ
Σ |g S (Amax + L) 1)
GO +
Σ
1 + 20 1og(1/0)
19 + 3( + (og) (6)
Finally, we use the bounds on the gradient norms 1 ll S and IIeell S G, re- aeearrg the terms and
divide both sides by T. Due to Proposition 4.2, with probability at least 1 - log(
T
( max + L) Go + 3(G² + GG))og(1//) (Amax + L) 2G / (1/
10dl
T
T
VT
where Amax S 0. (AI (AI++ + Log((T) + o² log(t)) We keep Amax in the bound due to lack of space.
4.4 NOISE ADAPTATION UNDER SUB-GASB AEB-GAASIIAN NOISE MODEL
To knowledge, under the standard setting consider (unbiased stochastic gradients with bounded variance), noise adaptation is not achieved for high probability convergence to first-order stationary points, specifically for AdaGrad-type adaptive methods. We call an algorithm noise adaptive if the convergence rate improves 1/vT 1/T variance -> 0. Following the technical results and approach proposed by Li & Orabona (2020), we will prove that high probability convergence of AdaGrad (Algorithm 1) exhibits adaptation to noise under sub-Gaussian noise model. First, we will introduce the additional assumption on the noise. We assume that the tails of the noise behaves as Lub-Gaussian if,
V
vf())]]3 [=] S cxp(o²).
(11)
This last assumption the noise is more restrictive than standard assumption of bounded variance. Indeed, Eq. (11) implies bounded variance (Eq. (6)). Finally, we conclude with the main theorems. We first establish high probability bound on Amax and then present noise noise-adaptive rates for AdaGrad.
Theorem 4.3. Let Ie be generated by AdaGrad and define AS = fxx) min fx). Under nub-Gaussian noise assumption in Eq. (11), with probability al least 36,
A41 S A1 +3G G2 + +2G log σ
r² log (1/()
4Go
I 1o max {1, G.) + 2G + 20 tlog
Theorem 4.4. Let Te be generated by AdaGrad and define A. f(x)) min f()). Under Gobs-Gassian noise assumption as in Eq. (11) and considering high probability boundedness of Amax due to Theorem 4.3, with probability least - 58,
T
32 (Amax + T + (Amax + L) (Go + o (log(()))) + 802 lo2log(110) 8 (Amax + L.) 1 2
T
T
VT
1=1
Remark 3. By introducing the sub-Gaussian noise model, we manage to achieve a high probability convergence bound that is adaptive to noise, while removing the dependence on a bound on stochastic gradients in the final result.
GENERALIZATION TO AGD TEMPLATE
Having proven the high probability convergence for AdaGrad, we will now present extension of our analysis to the more general accelerated gradient (AGD) template, which corresponds to a specific reformulation of Nesterov's acceleration (Ghadimi & Lan, 2016).
7

---

Published as a conference paper at ICLR 2022
Algorithm 2 Generic AGD Template
Input: Horizon T', 51 x1 E R ar E (0, 1], step-sizes (nherr trehee
1: for = 1.... T do
2:
T,- 0t33 + (1- (1-at)ãt
3: Set 9: f(²z) or gt fz(z) = (x(22)
4: 2++1 = 11:9t
5:
it41 Ft - 7ttt
6:
end for
This particular reformulation was recently referred to linear coupling (Allen-Zhu & Orecchia, 2016), which is an intricate combination of mirror descent (MD), gradient descent (GD) and averaging. In the sequel, we focus two aspects of the algorithm: averaging parameter a, and selection of (adaptive) step-sizes 77 and "/- We could recover some well-known algorithms from this generic scheme depending on parameter choices, which display in Table 1.
Our reason behind choosing this generic algorithm is two-fold. First, it helps us demonstrate flexibility of our simple, modular proof technique by extending to a generalized algorithmic template. Second, as an integral element of this scheme, we want to study the notion of averaging (equivalently momentum (Defazio, 2021)), which is important primitive for machine learning and optimization problems. For instance, it is necessary for achieving accelerated convergence in convex optimization (Nesterov, 1983; Kavis et al., 2019), while it helps improve performance in neural network training and stabilizes the effect of noise (Defazio, 2021; Sutskever et al., 2013; Liu et al., 2020).
Next, we will briefly introduce instances of Algorithm 2, their properties and the corresponding parameter choices. We identify algorithms regarding the choice of averaging parameter a and step sizes т) and T/.- The averaging parameter o, has two possible forms: Oa 2/(1 + 1) for weighted 1/L for uniform averaging. We take
2/(L + 1) by default in our analysis, as is a key element in achieving acceleration in the convex setting. Let us define the AdaGrad step size once more, which we to define 77 and 7t+
averaging and
i = -G + Σ
| 13
Go 0.
(12)
The first instance of Algorithm initialization, we have Fi ž1 21. The fact that 17, = % 7e implies the equivalence ã, r, for any E [T), which ignores averaging step. The second instance we obtain is AdaGrad with averaging,
the AdaGrad, i.c. I++1 = I₁ Tt Since ã = .i by
F4 = 0g + (1 (1-0x)tt--
(13)
1x+1
where 7): 7j and 7 O. For the initialization 2 = ē1. we can obtain by induction that ã, Tz-1- hence the scheme above. The final scheme we will analyze is RSAG algorithm proposed by Ghadimi & Lan (2016). It selects step size pair that satisfies 7/4 (1 + ar) 7/ and n/- Tit generating 3-sequence algorithm as in the original form of Algorithm 2.
Table 1: Example methods covered by the generic AGD template.
Algorithm
Weights (ot)
Step-size (1i,71))
AdaGrad
N/A
1]t i/r
AdaGrad w/ Averaging
0₁ 1-1
1
1]t agtt
7
Adaptive RSAG(Ghadimi & Lan, 2016)
at [-1
1] 7
%t = (1 + 0r. M
AcceleGrad(Levvy et al., 2018)
Q: [-1
1)t R
"t Rd Tj.
Before moving on to convergence results, we have an interesting observation concerning time-scale difference between step sizes for AdaGrad, AdaGrad with averaging and RSAG. Precisely, n is always only a constant factor away from 7/ This phenomenon has an immediate connection to acceleration in the convex realm, will independently discuss the end of this section.
8

---

Published as a conference paper at ICLR 2022
Having defined instances of Algorithm 2, will present high probability convergence rates for them. Similar to Eq. (10) for AdaGrad, we first define a departure point of similar structure in Proposition 5.1, then apply Proposition 4.1 and 4.2 in the same spirit before to finalize the bound.
Let us define 9r = (āt) and 9. = Vf( 24) = Ie + fe. Following the notation (Ghadimi & Lan, 2016), let [ proof, which is due to Ghadimi & Lan (2016).
T-1 with 11 Now, can begin with the departure point of the
Proposition 5.1. Let It. be generated by Algorithm 2 where 9t.
< (f( ze)
9t. + & and
3r = V((t). Then, it holds that
Amax + 2L
L
T
T
Oe (T) 72)2
Σ |elll
E
[gell + Σ
(ges Ex)
4/
2TTT
Tg
(*8)
Next, we will deliver the complementary bound on term (+) in Proposition 5.1. Proposition 5.2. Using the recursive definition of r, we have
T E (11-ax)L
2
if ar = T
at log(T
Pt
if a, =
Finally, we present the high probability convergence rates for AdaGrad with averaging and RSAG. Theorem 5.1. Let ve be the sequence generated by AdaGrad with averaging or adaptive RSAG, Under Assumptions 2, 6, for Amar I 0 A1 Loog (T) 0² log(1/ with probability 1 8 logg(T) (
Go(Aman 3I. + Llog(max (1, (1, Go (?T)) + 3(2 GG)log((1))
1
G(Dmor + 3L + L log(mmxx GT + G2T) + 2Go 2Gooologo11///
discussion on acceleration and nonconvex analysis: AGD and its variants are able to converge at the fast rate of ((1/T²) (Nesterov, 2003) for smooth, convex objectives, while matching the convergence rate of GD in the nonconvex landscapes. fact, the mechanism that allows them to converge faster could even restrict their performance when convexity assumption is lifted. We will conclude this section with brief discussion on this phenomenon.
As we mentioned previously, step-sizes for AdaGrad, its averaging variant and RSAG have the same time scale up to a constant factor. However, AcceleGrad, an accelerated algorithm, has time-scale difference of (L)) between T/2 and 7/. and it runs with modified step-size of n (1 + Ei= 0 1 ()) This scale difference is not possible to handle with standard approaches or our proposed analysis. If we look at second term in Proposition 5.1, it roughly evaluates to
2MT
where each summand ((t)) orders magnitude larger compared to other methods. A factor of or 2 f2 is absorbed by the modified step-size, but this term still grows faster than we can manage. We aim to understand it further and improve upon in our future attempts.
CONCLUSIONS
We propose a simple and modular high probability analysis for a class of AdaGrad-type algorithms. Bringing AdaGrad into the focus, we show that our new analysis techniques goes beyond and generalizes to the accelerated gradient template (Algorithm 2) which individually recovers AdaGrad, AdaGrad with averaging and adaptive version of RSAG (Ghadimi & Lan, 2016). By proposing a modification over standard analysis and relying on concentration bounds for martingales, we achieve high probability convergence bounds for the aforementioned algorithms without requiring the knowledge of smoothness L and variance o while having best-known dependence of log(1/8) on 5. To our knowledge, this is the first such result for adaptive methods, including AdaGrad.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement no 725594 time-data) K.Y. Levy acknowledges support from the Israel Science Foundation (grant No. 447/20).
REFERENCES
Ahmet Alacaoglu, Yura Malitsky, and Volkan Cevher. Convergence of adaptive algorithms for weakly convex constrained optimization, 2020a.
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. A new regret analysis for Adam-type algorithms. In Hal Daum III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 202-210. PMLR, 13-18 Jul 2020b. URL http: httt:://proccednngg mlr. www..press/vie /atsss/vv19/// wwa1119/accaaao wlwaaagaacaaggaaaaaaaaaa htmi.
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent, 2016.
Jonathan T. Barron. A general and adaptive robust loss function. In 2019 JEEE/CVF Conference Computer Vision and Puttern Recognition (CVPR), pp. 4326-4334, 2019. doi: 10.1109/ 2019.00446.
Amir Beck. First-Order Methods in Optimization. SIAM-Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2017. ISBN 1611974984.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks, 2020.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019. URL https: :ttttps::/opeeeee http:///ppeeeee.eeeeeeeeoeeeeeee fareet/ffrmmmidd-aee x30 9tm.
Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails, 2021.
Aaron Defazio. Momentum via primal averaging: Theoretical insights and learning rate schedules for non-convex optimization, 2021.
Alexandre Defossez, Leon Bottou, Francis Bach, and Nicolas Usunier. On the convergence of adam and adagrad, 03 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul))2121-2155 2011.
Alina Ene, Huy L. Nguyen, and Adrian Vladu. Adaptive gradient methods for constrained convex optimization and variational inequalities, 2021.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, (3(4):2341-2368 2013.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program., 156(12):5999, March 2016. ISSN 0025-5610. doi: 10. 11077/10107-015--881-88. URL 1f
doi.
-15 0871-8 8,
Haiwen Huang, Chang Wang, and Bin Dong. Nostalgic adam: Weighting more of the past gradients when designing the adaptive learning rate. In Proceedings of the Eventy-Eighth International Joins Conference on Artificial Intelligence, IJCAI-19, pp. 2556-2566 International Joint Conferences on Artificial Intelligence Organization, 7 2019. doi: 10.24963/ijeaa.2211/335.. URL https: //doi.org/10 24963/ jeai. 201 9/ /55.
10

---

Published as a conference paper at ICLR 2022
Pooria Joulani, Anant Raj. Andras Gyorgy, and Csaba Szepesvari. A simpler approach to celerated optimization: iterative averaging meets optimism. In Hal Daum III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 4984-4993. PMLR, 13-18 Jul 2020. URL https: /ttp://pp/eeedeeeo ngs mm
wtt..mll...rr.. presss.ppe////m... vv1vvv111v91 9/ joul anw.aannn0a...... html.
Sham M. Kakade and Ambuj Tewari. On the generalization ability of online jig sisttonggly/ii, convex programming algorithms. In Proceedings of the 2 International Conference on Neural Informa- tion Processing Systems, NIPS'08, 08, pp. 801808, Red Hook, NY, USA, 2008. Curran Associates Inc.
ISBN 978 9781605
Ali Kavis, Kfir Y. Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 6260-6269. Curran Associates, Inc., 2019.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Guanghui Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer, 2020.
Kfir Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. In Neural and Information Processing Systems (NeurIPS), December 2018.
Kfir Yehuda Levy, Ali Kavis, and Volkan Cevher. STORM+:
Fully adaptive SGD with recursive momentum for nonconvex optimization. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:// openreview net/ net/forumg sidiiidkkkeee 6qKpxt.....
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Twenty-Secone International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 983-9922 PMLR, 16-18 Apr 2019. URL http:/ http:///poceenneeeeeeeee .ml.. prwss/ 1t//111990 19..99c.. html.
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum, 2020.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum, 2020.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate, 2019.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex opti- mization. COLT 2010, pp. 244, 2010.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate o(1/k?). Dokd. Akad. Nauk SSSR, 369:543-547, 1983.
Yurii Nesterov. Introductory lectures on convex optimization. 2004, 2003.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithmss. Cambridge University Press, USA, 2014. ISBN 1107057132.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 1139-1147, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL https:/ / /proceedings ml press v28 wtt.//tskeeeee1. html.

---

Published as a conference paper at ICLR 2022
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2), 2012.
Phuong T. Tran and L. T. Phong. On the convergence proof of amsgrad and a new version. IEEE Access, 7:61706-61766. 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL
nwwrips. wwwprrpp..ccppppr///222 cc/papprr/2017/Elee 3 1wddaaacccaaaaaaaaaaaaaa
pdf.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: landscapes. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference ing Research, pp. 6677-6686. PMLR, 09-15 Jun 2019. URL httt:::/pp/ootoo http:///oceeeeenee//eee mlr.
Sharp convergence nonconvex
Machine Learning, volume 97 of Proceedings of Machine Learn-
press / w/w./wallllll a. html.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Besa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: httpps://proceediing. www.ipe.urcccom paper 220prr/2188 8/ fillil1111 e 90365351 ccc 7437 30 300ccc4e//b332233appeer
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models?, 2020.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. ArXiv, abs/ 0e011188.006777 05671, 2018.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'03, 03, pp. 928935. AAAI Press, 2003. ISBN 1577351894,
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for conver- gences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
12

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 PROOF OF TECHNICAL LEMMAS IN SECTION 4.1
Lemma 4.1. Let 01,..., On be a sequence of non-negative real numbers. Then, holds that
04 2
ai
k=1 a3
Proof. For the proof of first iniequality, please check Appendix A.4 of Levy et al. (2018), while that of the second one can be found at Appendix B of McMahan & Streeter (2010), which corresponds to their Lemma 5.
Lemma 4.2. Let 01, ... be sequence of non-negative real numbers. Then, it holds that
S + log
1
Σ
aj
k=
Proof. We will follow the proof steps of Levy et al. (2018) with slight modification. The proof is due to induction.
For the base case of n 1:
1 1 1 1 + a1)
a1
Assume that the statement holds up to and including
1. Then, for n
n
n-
n 1
a
+ log 1
Σ
0g
On
- + log
ae
1j
2i=1
ag
We want to show that for any an. the second inequality with the question mark (?) holds. Let us define
Σ Focusing the second inequality and arranging the terms we get,
1 1
aj
S log
1= 04
1 1+
1=1
Og
On
llog
1+
Σm= aj
On
< log
1+
Σ aj
Notice that
On
An
1= Oj
On
On
1==
Σn= ==
0i
12
i==
-1=1
a;
E 4;
Σi ac
== 0;
1
a
+
Combining both expressions,
< log( + x)
1 x
which always holds whenever 0.
13

---

Published as a conference paper at ICLR 2022
Lemma 4.3 (Lemma in Kakade & Tewari (2008)), Let Xt be martingale difference sequence such that [ I b. Let us also define
Var--1(X;) Var (X2 Xi,... X = [X Xi.... Xt-1].
and define Vp = =E Var;-1(X,) as the sum of variances. For < 1/e and T 2 3. it holds that
IP
X max (2V Vr. 3by 3l///1/1//))) Vlog(1/8)
< (Tg
(14)
Proof. The proof of this lemma could found at the beginning of the Appendix section Kakade & Tewari (2008), which is their Lemma 3 in the main text.
A.2 PROOFS IN SECTION 4.3
Theorem 4.1. Let be generated by Algorithm I with Go 0 for simplicity. Then, it holds that
1
T
0o (Ai + L)²
T
T
Proof (Theorem 4.1). Setting gr (xt),
deterministic counterpart of Eq. (9) becomes
T
T
T
Σ
+
L
Σ
1lll <
(A max L)
1
TJT
2
1=1
1=1
1=1
where we obtain the final inequality using Lemma 4.1. Now, we show that Ar41 is bounded for any T. Using descent lemma and the update rule for xz.
f(1+1)) - f(x))= S (ōt, xc-1 - xz) + 1 |1 - x
- | 112 +
11
2
Summing over / E (T), telescoping function values and re- c--aranggng right-hand side,
f(1r41) - f(x)) S
Σ 1=1
T
Lm]
-1
1)
17
11
2
T
Taje
((Tr-)- - S f(()) f(x')
+
Σ
-1)mmlll nh mell
-1
2
1=1
where x² = arg ming inzd (x)). Now, define to = max {l E [7] me > 2) such that
Lmu
- -1)
2
0 for any > to. Then,
to
Lif:
Lm:
Σ
no mall 12
Σ
1 no 1ll
2
t=1
t
L
tq
$ A +
Me ||
(Lemma 4.2)
2
1=1
L
to
$ A
+
+ log
1 Σ
|o.11
(Definition of 17.)
2
1=1
L
1
< A +
1 log
+
(Definition of (n)
2
L
1
A
1 1 log
1
2
14

---

Published as a conference paper at ICLR 2022
where use the definition of tu and Lemma 4.2 for the last inequality. Since this is true for any T, the bound holds for max such that Amax $ A1+ 1 (1 + log (L2/4)). Now, define X E ll then the original expression reduces to X² < (Amax + L) X. Solving for X trivially yields
T
S max + L)
X
Σ
|1 S (Amxx + L)²
1=1
Plugging in the bound for Amx and dividing by T gives,
T
( [S(+))
Y/2 3 + log 1 L2
4 ))
Theorem 4.2. Let dx be the sequence of iterates generated by AdaGrad. Under Assumptions 6,
for Amax 00 A L + a² (1))1/ with probability at least 1 8 log(())
T
10 < (Amar + Go + 3(2 + GG)log(1/8) (Amer + +L) 2G (og(1/8)
T
T
vT
E=
Proof (Theorem 4.2). Define
V
(xx) and gr
Vf(xi 2x) = + E.. By Eq. (10),
T
T
T
Σ
max
Σ
(oe, E.) +
L
Σ
mellsal1
T/T
2
[m]
Invoking Lemma 4.1 and plugging the bound for the term (**) from Proposition 4.1 achieve with probability - 6
T
1olel $ (A max + L)
GO +
| 20 /log(110)
@ 3( GG))log(1/8) Σ
1=1
< (Amax + L) G + GTT + 2Go 2 3(G + GG))og((/0))
$ (Amax + L) Go 3G2 GG))og((/)) + (Amax 2L) G 2Go 2Go /log(1/8) VT
Dividing both sides by T, we achieve the bound,
(Amax Go 3(G G1))og(1/0)
(A max L) 2Go log(1/8)
19.l
VT
Now, we will incorporate the high probability bound for Amax to complete the convergence proof. Essentially,
interested in scenarios in which both the statement of Proposition 4.1 and the statement of Proposition 4.2 holds, simultaneously. with high probability. Formally, let the statement of Proposition 4.1 be denoted as event A and the statement of Proposition 4.2 as event B. We have already proven that
P ( > - (
&
PBB 2 4 log(T)ō
What we want to obtain is lower bound to P (An B), which is
P P(AN = (A) + P (B) P (AUB)
> 1 - 4 logo ( + 4 ( -P (AUB)
2 2 - 8 (og(())) - 1llgg
which is the best we could do due to the unknown extent of dependence between events A and B. Hence, integrating the results of Proposition 4.2, with probability at least (og()))
| < AAmax L) Go + 3(G2 + GG) (Amax L) + 2Go (og(1//oo11//) log(1/8)
T
T
15

---

Published as a conference paper at ICLR 2022
where
Amax - A + 2L (1 + log mmax(1, (a) + ( + Go GT3 + + o + GT + GG)
Proposition 4.1. Using Lemma 4.3, with probability 1 (lg((T)ō with 1/e, we have
Σ Ee) S 20 llo((18))
Σ 1 12 + 3(6 GG))og(1/6).
Proof. We have to show that the random variable (gr, Ex) is martingale difference sequence and satisfies the conditions in Lemma 4.3. Let us define F, o (ft...., (1) as the o-algebra generated by randomness up to, and including &r. Notice that J, is the natural filtration of - -gt, Et). Then, need to show that
1. -ge. Ee) integrable.
2. martingale (difference) property holds, (1 0.
First off, show that -gr, ) integrable:
E (ge, E E [[]
|1 11]
G² E [ [I]
$ G² 0² < t00,
where the second inequality is due to towering property of expectation. Then, the maritngale property:
(gt, F.)
(it [E
(ūr, 0) 0
Before applying Lemma 4.3, we need to verify that | (āt, E is bounded:
(ge. &t)l = (g.. 9i ge)l |||@e|| (3.. ge)
| 2 + - Ge. ge 11 + 11 Illgel S G2 + GG,
where we used G--ipschitzness of f and almost sure boundedness of stochastic gradients gr. Now, we are able make the high probability statement. By Lemma 4.3, with probability 4 log(T)) for
8 1/e, have
T
(ge, Ee) & max
2
Σ
E (Gt. E,) 3. + GG) 1og(1/5) Vlog(1/5)
t=1
(18(1
2,
Σ
E Bllgg 1 + + G Vlo((1/o)
Ilg(118)
2,
1 2 + +( + 02
[=1
< 2x 1og(1/8)
Σ
11 2 3(G² + GG)log(1/00
where we used Cauchy-Seheee Schhaar-Schazzzat inequality for the inner product to obtain inequality (1) and bounded variance assumption to obtain (2).
16

---

Published as a conference paper at ICLR 2022
Proposition 4.2. Let be generated by AdaGrad Go O. With probability at least - 4log(t)6
1++1 S A1 +2 (1 + log G ( (21) + G (Mi + log(1/)) + M2,
where M1 3(G + GG) and M2 1 (2G² + GG).
Proof. We will handle this bound in two cases. First, we show the bound for AdaGrad, and then for the remaining algorithms. Indeed, the bounds for the two differ by factor of constants., hence we will use the larger bound for all three algorithms.
Case (AdaGrad)
Let 9t fz(z) and 9: = f 26), such that Øt 9r + & Then, by smoothness
Lofe
f(x+11) - f(xx) - - T/ (āt, 9t) + 2 119:11
Lo
-ollaall1 no (Tr Ex) +
||
2
Defining x² min f(x) as the global minimizer of f and summing over & [2],
L
((T+1)- f(x)) s f(1)) f(x
Th | 2
9t
T (ges Ee)
(15)
2
(A)
(B)
(
Term (A) At this point, we will keep this term as it will be coupled with the sum-of-conditional- variances term which will be obtained through martingale concentration.
Term (B)
T n
L T
Me 2
19
12 =
Σ
(Lemma 4.2)
2
G3 Σ |
t=1
L
T
|lael ))
+ log max(1, 1, GØ} + Σ
(Bounded gradients)
2
t=1
L
mmxx(1, Gb + (
$
1 + log
2
Bounding term (C)
r
T
T
Σ
no Ct. &1)
$ Σ -
-m-1
Ex)
+
Σ
(M--1 - m7) (gr, Ex)
(C.I)
We will make of Lemma 4.3 to achieve high probability bounds term (C.1). To do so, need to prove that X, 1 (ār, & is a martingale difference sequence and validate some of its properties:
1. - (gr, Ex) absolutely integrable:
-|--%-1 (gr,
&1 < GT Bi (ge, &I
s G '' + [|
< G (G² + 0²) < +00
2. T/- (ār, Et) is adapted its natural filtration J, a ; ..., Et)
17

---

Published as a conference paper at ICLR 2022
3. It satisfies the martingale (difference) property:
-1 (gt, Et) Fi-1] 10, Fi 1) =0
4. X₃ = (9t, E.) is bounded:
-āe Ex) - GO (gh, ExYl S (1lrr12 + 1I G
5. Conditional variance of X, = 1/--1 (g:. Et):
Var;-1(X,) = (77-1 (t, {2))² Fi-1] ]
S Go 2B (gt, {1) Fi-1] ]
$ G lloe E ||& Fi-1]
S Go o0 |
Term (C.1) Now, we are at a position to apply Lemma 4.3 on term (C.1). With probability
1 (og())ō
7-- (gr, max
2
(100 (0), Fr-1),30,
3, (G² GO) (lg((16)
Vlog(1/8)
T
S max
2
Σ
2² _
+ +GG Vlog(1/0)
20 v log(1/0)
2h |1ce| 33 GG))og(1/0)
(D)
Term (C.2):
T
(1). S Σ (m--1 - m/ Kgr, E
T
$ (G² + GG) Σ
(m--1 - mp)
< GG + GG)
Terms (A) + (D): All the underbraced term but expression (D) either grows as O (log(T)), or is upper bounded by a constant. The worst-case growth of term (D) is O(VT), which we will keep under control via term (A).
T
T
(A) + (D) < 20 2 log(1/8)
mi
1
nel
@ell
1=1
T Σ
T
< 220/log(1/0)
11
Go Σ
[| 1
1=1
T
T
T
< 220v/o8(110)
Σ
n2 11 - Go Σ
n 11 2 Go Σ
(vi
1/ 11.
t=1
1=1
T
T
< 20 (oV/o/((1/)
Σ
2 |1 Go Σ
2/
|1@a + G2
1=1
18

---

Published as a conference paper at ICLR 2022
In order to characterize the growth of this expression, let define f(z) 2a (log(1/5) Ggæ, which is a concave function as its second derivative is non non-positive. Now, looking at derivative of f.
d dx f(2) o [Voo(110)
Go.
Vz
which 0t Gp log(1/8). This is indeed the point at which the function attains its maximum. For the final step of the proof, we define Z7 = Σim n 1l Then,
(A) + (D) & f(Zr) + Go n
S f log( 1/6) + GoG
oo GoG
Final bound Plugging all the expression together and setting Yo = Th with probability at least 1 4log(T)o,
((T++))-(e+) S ((x1)=(((x)) + (1 + log G + GOT))
(3 GG) o²) log(1/6) 1 + GG)
Since this result holds for any T, to make consistent with the statement of the proposition, we re-state the bound with t.
+ 2 (1 + log (max Gb) + (21))
[(x+1)) - -(x=) S
(3 + GG) + oz) log(1/8)
+ 12G GG)
Case 2 (AdaGrad w/ Averaging & RSAG) Let us define stochastic gradient at 3e as gt ff( 9s where 9. (..). Then, by smoothness,
f(r(+1) - f(x)) < (Vf(zz) 21 - -x²) + 2 T++1 zrl1
Lnzz
(o 9t) no fzz)) ge) +
||
(Cauchy-Schwarz)
2
+ Lifi
= --IllVf(x))) n (g. {t) vf( 11ll9111
|l
(Smoothness)
Li
=- (g, E + Lops 1 xx 1ll111e111 +
(Young's ineq.)
2
-1 no (g., Ex) + || -x,11= 1ng11
Using recursive expansion of || - xell2 and summing over E [T],
I
(M7-
-2x
Ar-1 < A
+
(1 - re
11
+
L ll melloel1 - me (ō. E2)
2
af
t=
k=
A
L
Σ
Tx
(n )2
119e
Lo 11 11.1..11 mh (or
2
az
19

---

Published as a conference paper at ICLR 2022
First, we plug in a, 11) and invoke Proposition 5.2. Recognizing that hy mpl =a for both RSAG and AdaGrad with averaging,
AT+1 S A
112 + 2L
+
T Ei)
tm1
(A)
(B)
Observe that this expression is the same as Eq. (15) up to replacing &/ term (B) of AdaGrad with 2T. Hence, the same bounds hold up to incorporating the aforementioned change. With probability
1 (Tg(
f(oT-1) s f(11) f(x") 2L (1 log max Gg) + GTT) 0²) log(1/6)
+
+ G2G + GG)
Similarly, since this holds for any T, re-state the results with for consistency,
f((+11) f(x*) < (()) - f(x*)())))))))))))) + 2L log maxxf Gbt + 64t)
+ (3 + o²) log(1/6) + (20 GG)
A.3 PROOFS IN SECTION
Proposition 5.1. Let Tr. be generated by Algorithm where ge (((a)). Then, it holds that
V (((ei
Dt & and
Gell 2
Amax + 2L
L
E
okk
T
ag
(n
71) ||
+
(ges Ee)
1T
21T
a
(+0)
Proof. This result is due to Ghadimi & Lan (2016); Lan (2020) up to introducing adaptive step-sizes. We follow their derivations in the deterministic setting and incorporate it with our high probability analysis. Then,
L 2
f(z(+1) f(x.) s (Vf(z.), 7:41 xZ)
x
21112
Liii
S - (2:)) Vs(()) + Er) +
2
Laii ||
= - 122 ( (T+), & - (V(r)) - V V.())), gt) +
I
S <-mlloi (ō. ........ {t) + || | - 12 + Lnl gell
2
where we used descent lemma (Eq. (4)) in the first inequality, and update rule for x,-1 in Algorithm 2, line in the second inequality. For the last line, we use Cauchy-Schwarz, apply smoothnness definition in Eq. (3) and finally use Young's 's inequality. Let us define A, = f(x) min f(x) and Amex max A. Dividing both sides by Met rearranging, and summing over 1, obtain,
T
L
T
T
T
1 2
(A. A
Σ
2 + L
1elloal1
+
(gr, Ex)
n
2
7
t=1
1=1
20

---

Published as a conference paper at ICLR 2022
Now, we express the term 2t 2; recursively, as function of gradient norms.
Ft It (1 az)) [Tx xzm]
= (1 at)) [Tt-1 2z-1 + (T/-11 - 11--199-11
(1 at) ) [[] aa-1)( =1-1) + (m7-1 71-1) 11-1]
(1 az)
II (1 a1)) j=
(nT -7)9a
k=
1-1 (Th 7k)9k
(1 04)
Tk
k=
(1 a4)
P
04k
(nk - 7k)
9k
Hence, by convexity of squared norm and (absolute) homogeneity of vector norms,
Okk (1/x - 7k)
| xxl12 = [1(1 - r-
gxll2
Tk
Ork (11 - )²
$ (1 -oz) 2
11911 1|
T&
0
k=1
7kk
< (1 04
T
11 1|
k
0%
Finally, we plug this in the original expression,
T
L + A+11)
T
r,
t
(1
72
1
(A.
(1
(ks)
|1ax11
17
2
17c
F
at.
1=1
k=
T
T
+
L
The Tel19:11
12
+
Et)
t=1
[=1
4
T-1
A
+1
L
aak
at
(ne -2)
11 11
111
71+1
1/
2
at
T
||
T
+
L
Σ
+
(gt,
Ee)
G
E/
||gb|] 12
1=1
A max
71
max
T-1
7111
)
+
2
ork)
Tk
7k
0n
Ie
(1.
a?
72)
llg. 1l
T
+ 2T
G3 +
1|2
+
(0r, Ex)
1=1
1=1
+ 2L
L
T
T
(me - 72) a2
T
Σ
on)
1|
+
Cge Ee)
2
Tt
of
k=t
(x)
(+))
We rearranged the summations to obtain the second inequality, used the assumption that A, < Amix for any t together with Lemma 4.1, and we telescope the first summation on the right hand side to obtain the result.
Next, we provide the proof for term (+) in Proposition 5.1.
21

---

Published as a conference paper at ICLR 2022
Proposition 5.2. We have
2 [Iog(T+ +1) if ar 1
if ar 1I
2
Σ
(1
on Dn
Pt S
Proof. First, we begin with the weighted averaging setting, i.e, 04 = 2/(1 + 1). Using the recursive definition of D, one could easily show that for any at. E (0, 1),
0
T
T
Am
Defining A, Ei=
k++1) 2
and Ag 1, we have that Og =
+ and
A
T3
[1
0.)
A
A
A
i=1
1=1
1=1
Hence, we can express term (+) as
Ea-aw)IH
I't
AA
km
A
+ 1)
T
t
1: +
k=t
2
8
T+1
2
For the uniform averaging setting with
:, for t > 1,
k
r =
0:)
k
2
Hence, again for / > 1,
T
Σ Ri=t
T
ΣE
Σ
log +1,,
Te
k=t
k=2
where the last inequality is due to that fact that integral of f(x) = 1/x over the range [1, upper bounds the summation above.
Finally, we conclude with the high probability convergence theorem for AdaGrad with averaging and RSAG,
Theorem 5.1. Let I4 be the sequence of iterates generated by AdaGrad with averaging or adaptive
RSAG. Under Assumptions 2, 6, 7, for Amar < O (A + log(T) o² log(1/5)), with probability
22

---

Published as a conference paper at ICLR 2022
1 - 8 log(T))
T
Go Amax + +3L + Log
+ ( + +3 GG)log((/0)
T
& (Amr + 3L + Llog max (1, Go2) Conx(11,''11 + GPT)) + 2Go (log(1/0)
+
VT
Proof. Again by Proposition 5.1,
1 12
Amax + 2L
L
Σ
(1
0r
ai
(n
76) o
|19e11
(Gts Et)
21TT
rt
(+*)
Both for AdaGrad with averaging and adaptive RSAG, we use weighted averaging. Moreover, due to the particular step-size choices, 7) ")t 0.7) for both methods. Combining this observation with the previous expression we get
2L
L
max
Σ
0g
T
th
2
|1
Σ (gt, Ex)
2TTr
r
k=
(+*)
We introduce the bounds in Proposition 5.2 and Proposition 4.1 for the respective marked term,
A max + 2L +L 19 + 2 (oo((//))))
1
l| + +3 + GG))log(1/))
1/
A max 3L + L Log
max(1, (1, 2o + +I= l19o113)
1/r
+ 2Go Log((1/0)// + 3(2 + GoG))o((1/)
T
< Amax 3L + Llog
max (1, 2 + Σ
19: 13
G
+
|1
1=1
+ 2Go (ogo//og(//)V// 3 GG))og((/0)
G (Amax + 3L + L log
max Go 2) + G9T)) +2Go VT
+ Go Ammx + 3I + Log
mnax(1,G77 (2T)) 3( GG)log(1/0)
where used Lemma 4.2 in the second inequality, while boundedness of St and almost boundedness gr in the last line. Dividing both sides by T, and using the same argument as in the proof of Theorem 4.2, with probability least 1 8log(T)ō,
Go Amax + 3L + Loo (max(1, GD + OTT) + 3(G² + GG))oog(18))
gr 2 <
T
T
Ô (Amax +3L + L Loog max(1, (1, Go 2 + ( 2Go (lg(1/0)
VT
23

---

Published as a conference paper at ICLR 2022
where
Amxx Ai 2L (1 log ( + +c) 1og(1111)))) + (2
+ ++T)
B NOISE ADAPTATION UNDER SUB- BUB-GAUSSIAN NOISE
In this section of the appendix, we present the proof of Theorems 4.3 and 4.4 along with the Lemmas that we will require in the proofs. We first prove a bound on Amax and then show noise-adaptive rates for AdaGrad.
B.1 HIGH PROBABILITY BOUNDS AMAX
We will argue about high probability bounds on objective sub-optimality under sub-Gaussian assump- tion. First, we will present Lemma 1 from Li & Orabona (2020), as well as our modified version of that we use in our derivations.
Lemma B.1 (Lemma from Li & Orabona (2020)). Let Zı,... Zr be martingale difference sequence (MDS) with respect to random vectors "1,... ,E and y, be a sequence of random variables which is (E1, ... Et-1) (t-1)--eeauuable. Given that E [ee((22 (2,) E.. E.-- S exp(1), for any X and (0, 1) with probability at least 5,
Σ
log(1/0)
Next, we present a slightly modified version of the above lemma. Its proof follows the same lines with Lemma B.1 up to replacing Y, with deterministic quantity, selecting a particular choice of and dealing with the MDS Z, itself rather than its square, ZZ-
Lemma B.2. Let Zi..... Zr be a martingale difference sequence (MDS) with respect to random vectors L ... .r and o² E R such that E (exp(Z//o²) E1, E-1] s 1. Then, with probability
as least
Σ Z S 0² log(1/5)
We will also make use of another relevant result (Lemma in Li & Orabona (2020)) regarding the probabilistic behavior of maximum over norms of noise vectors.
Lemma B.3 (Lemmaa in Li & Orabona (2020)). Under assumptions as in Eq. (5) and (11), let ffr,, (xx)). For 5 E (0, 1), with probability at least 1 - 5,
eeT 8
|1&.1 < 02 20
Theorem 4.3, Let be generated by AdaGrad and define A; f(x)) - min f(x). Under
sub- Gabbsiassi noise ussumption as in Eq. (11), with probability at least 36,
et
3
A Ai +3G LG + 2G 1o0-100
o² log
o² (og(1/0))
8
4G
L 1 (1+ log max {1, + 2G
el
+
20 2 log
8
Proof. Using the initial steps of the proof in the original derivation,
T
T
I T
Ar+1 $ A
nel
mh (ōc, {e) +
Σ
11
2
1=1
(C)
24

---

Published as a conference paper at ICLR 2022
Term (A) + (B): In order to deal with measurability issues, will divide term (B) into two parts:
T
T
Σ
Th Dr: Et)
=
Σ
1/ (T,, Et) + Σ
Mh- - (3).
1=1
-|- 1 (0t, Et) + 2(G + max
||5.113)
Σ
( 71)))
1515T
2m1
T/- (0t, (10, Et) +22
| mm 1S1ST
max
where we used Souchy-Schwarz together with Young's inequality to obtain inequality (1) and telescoped in the last line. Moreover, we pick 1/0 2 ? to make sure monotonicity. Without loss of generality, a natural choice would be 7/n = Go which aligns with the definition in Algorithm By Lemma B.3, with probability at least 6,
T
Te (T, Ex) S
Σ
T
Th (e,, + 2G,1 ( + o2 log
(c+
ef 8
Now, we will invoke Lemma B.1 on the term Σ Y?² = 7 with probability at least 1 - 6,
(7: Et) by setting Z, = -1h-1 (ge, Ex)
T
T
Σ (
Y + log(1/8)
1=1
3
oo
2
2
11 11 + log(1/8)
Now, summing up the expression above with term (A) and leaving & log(1 /8) aside for now,
T
T
T
3
Xo
77 1 |
2
2
Σ
no
|1
1
oo
m
|1
Go
mr
2
4
1=1
1=1
t=1
t=1
T
3
2
Σ
M
Gu Σ
m1 11 11
Go Σ (
7Z l1
4
33 2o
T
Go
Σ
+ GoG
where we used Gov < in the first inequality and added/subtracted Σ - 2 in the second inequality. Since have free variable choose, could set to A
4Gg to obtain, 30
oo 2 Σ n 12 Σ nellell S SG
Hence, summing up all the expressions together, with probability at least 26,
(T
3
(4) (B)+ s 3 G2 2G 2
o² log(1/0)
4Go
25

---

Published as a conference paper at ICLR 2022
Term (C): This term is easy to prove using online learning lemmas did previously, but introduce a slight change in order to avoid bounded stochastic gradient assumption.
L
L
Σ 11a.11)) 1(mllr))
n 19
11
-
1 log
max (1,
2
max {1, + 2 Σ |1 11? + Σ 11&.11 )
L
+ log
L
)
5
1 + log
max {1, Gb) + 2G
max
||se/1
We invoked Lemma 4.2 to obtain the first inequality. Once again via Lemma B.3, with probability at least 1 5,
T
L
eT 1 + log max (1, + + T
119el1
- 2
2 1=1
8
Finally, merging all the expression, with probability at least
35,
cT
3
1rt1 D1 3G7 G2 -2G 0² log
log
4Go
L
))))
cT
1+ log
max (1. + 2G + 20 202Tlog
2
(T (5))
T o log eT
0
D 02 202 log
+ 2² log Llog
B.2 HIGH PROBABILITY CONVERGENCE RATE
Now, we a position to prove noise-adaptive bounds.
Theorem 4,4. Let xe be generated by AdaGrad and define A, = f(x) - min f(x). Under sub-Gaussian noise assumption as in Eq. (11) and considering high probability boundedness of Amax due to Theorem 4.3, with probability at least - 56,
T
32 (Amax max + L)) + (Amax + L) (Go + Co 2log(11)))) + 80 log(1/8) 8v2 (Amax + L)
17
T
T
VT
t=1
Proof. We take off from the same step of the original analysis by defining & Vi((ee,, (V())).
Amax
T
L
1
(gt, Ex)
m
TT
2
T
T
Amaxx + L)
G
l 2 + Σ
(gr,
1=1
1=1
T
< (Amax + I.)
G2 2
(1lga 112 + 1|E.11 0² - -2)) +
(ūt, Ee)
1=1
T max {0.2 >
(1|s. 2 -22) o2)1) 1/2
T
(Amax + 7.)
Go +
2
11 1|2
OT
(e. Ee)
1=1
(+)
(x4)
26

---

Published as a conference paper at ICLR 2022
We already showed that (g), is MDS. Similarly, could show that martingale property holds for ||&e]] o².
E |1 - [1, ... _ = E ||&/| EI, -6-1-- 0² oo= 0² = 0.
Lemma B.2 immediately implies for term (+) that with probability at least - 5,
E o²) 0² log(1/6)
For term (**), we apply Lemma B.1 with Y? "3 and 1/0² to obtain with probability least 1 6, 6,
T
T
Σ
G., Ei)
|@bll + o² log((16)
Plugging these values and re-arranging.
19 2 S v2 (A + L)
Σ 11 12 (Amax L) (Go 212ogg(1))))) oV2T) a² (1/6
will conclude our proof by treating the above inequality as quadratic inequality with respect to ΣT= 1=1 1e Defining == mAxxx + 1.) (Go + /l2log(1/0) + ov2T) + o² log(1/8).
x
A + L) x 4c 50 0,
where the roots of the inequality are
4v2 (Ama max + L.) v 32 (Amax + L.) 16 (4 + L.) (Go + a /log((11))))) + oV2T) + 166 log(1/6)
2
Since x > 0 by default, we will take into account the positive root above, which yields,
2
1g 2 <
V2 max L) V (Amix + L) (Go (A + L) + o / 2lg((1/0)) + oV2T) + log(1/0)
T Σ T 2m
32 mAxxx + -)2 +88( (Amax + L) (Go + / 2log(1/8)) 802 log(11))1 8v2 (Amax + L) VT
| 1 =
T
27


Reviews:
[{"review_id": "owi4XFfkS1I", "reviewer": "Reviewer_BF1x", "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": "The paper addresses an interesting and relevant problem, and the difficulties present are significant.\nI have two main concerns about the results currently.\n\n1: Although it is true that the final result depends on the \"unknown\" $L$ and $\\sigma$, it does not have a very good dependence on these quantities. In particular, the in-expectation results for adaptive methods would be more like\n$$O\\left(\\sigma/\\sqrt{T}\\right)$$\nwhile these results are more like $$O\\left(\\left(\\sigma\\sqrt{\\log(1/\\delta)}/\\sqrt{T} + \\tilde GL/\\sqrt{T}\\right)\\right).$$ That is, when $\\sigma\\to 0$, the result does not have any asymptotic improvement. In fact, I believe a similar result is achievable with \\emph{non-adaptive} SGD using learning rate $\\eta_t = 1/\\sqrt{t}$. In this case, applying standard martingale bounds to the second display of page 5 (which is fine since the learning rate is deterministic), would yield $$1/\\sqrt{T} \\sum_{t=1}^T \\|\\bar g_t\\|^2 \\le \\Delta + \\sqrt{\\sigma^2 G^2 \\log(T)\\log(1/\\delta)} + L\\tilde G^2 \\log(T),$$ from which some rearrangement provides a similar bound. Notably, SGD also doesn't require any knowledge of the smoothness or Lipschitz parameters. Thus, unless I miss some interpretation, this result seems to be more on the line of \"the adaptive method doesn't *break* anything\" rather than \"the adaptive method is actually useful\".\n\n2: The high probability bound is a little weird, as it applies to just a sum of the gradients. What does this actually mean? For the in-expectation bounds I can actually produce an iterate that has a small gradient norm in expectation by randomly picking an iterate. Here if I randomly select an iterate I think the high-probability guarantee will be lost, so unless there is some other construction or better argument, it cannot actually provide any high-probability guarantees about any iterate. Since my feeling is that the point of the high-probability analysis is to say things about individual runs of the algorithm, this may limit the usefulness of the result. Now, this could be surmounted by simply calculating a batch stochastic gradient for each iterate as done in Ghadimi and Lan, but this seems to require a lot of gradient computations. Another alternative would be to use minibatch sizes of $\\sqrt{T}$ for $\\sqrt{T}$ iterations, but this would essentially average out all the variance and so we may possibly run into an even more extreme version of the issue in which the bounds do not obviously improve on non-adaptive methods.\n\n", "summary_of_the_paper": "This paper provides an analysis of adaptive learning rate scheme in stochastic non-convex settings. Under assumptions of smoothness and bounded stochastic gradients (a light tailed condition), it is shown that the sum of the gradient norms of the iterates of the non-convex algorithm is small.\nIn order to accomplish this, the analysis must deal with the standard difficulty for adaptive learning rates, which is that the learning rate depends on the current iterate and so makes it harder to apply standard martingale inequalities.\nThe final results include a dependence on the smoothness constant $L$ and variance $\\sigma$ which are not explicitly used in the algorithm.", "summary_of_the_review": "The paper considers and interesting and difficult problem. However, the results seem to fall short of realizing the ideal goals.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "m4KKVikC75f", "reviewer": "Reviewer_GqwP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "I believe the conclusion is meaningful and important. The writing and presentation clearly shows the main steps of reasoning. By partitioning the proof into three steps in Sec. 4.2, with their corresponding lemmas, I can easily see the ideas and pinpoint to each separate proof. \n\nI can barely find weaknesses of the paper. I have a few questions below.\n\n1. As far as I remember, the AdaGrad usually means an entrywise step size. Compared to the paper, I would rather say $\\eta_{i,t} = (G_0^2 + \\sum g_{k,i}^2)^{-1/2}$ and $x_{t+1} = x_t - diag(\\eta_{i,t}) g_t$. The diagonal matrix approximates the inversed Hessian to accelarate. Does this paper apply to that case, and will there be an acceleration if the Hessian is truly diagonal?\n\n2. I'm not quite familiar with the high probability reasoning, so it could be helpful to add in appendix a comparison with the papers in \"High probability results\" paragraph, say, what algorithms did they use, what are their result.\n\n3. I think the usual \"convergence in expectation\" result also indicates the probability. $f(x)-f(x^*)$ is lower bounded by $0$, so a small expectation $Ef(x)-f(x^*)<\\epsilon$ means that \"with probability $p$, $f(x)-f(x^*)<\\delta(p)$\". Does a standalone argument about probability benefit? ", "summary_of_the_paper": "This paper proves a high probability convergence rate for the first order algorithm, achieving the optimality of the probability and the convergence rate under this type of algorithm. ", "summary_of_the_review": "I think the contribution is meaningful and the writing is clear. If other reviewers are not doubtful about the novelty, then I'll give an accept.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QmZxEUjHZ6G", "reviewer": "Reviewer_goz1", "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": "Disclaimer: My apologies for putting this review very late, due to I have been assigned as an emergency reviewer about two days ago.\n\nstrength:\n\n- The high probability bound results provide more information than the expected convergence results (basically the variance of the optimization behaviours), while the AdaGrad method is a base for many widely used optimizers in machine learning, and therefore the topic is important to optimization community.\n- The analysis is simple and elegant, which I appreciate. The proofs are correct as far as I have checked.\n- The presentation is very clear and easy to follow.\n\nweakness:\n\n- I am concerned with the results do not tell us much information about why the AdaGrad and its variants enjoy good performance in practice. In particular,\n\n- The main results in Theorem 4.2 claims that after $T$ iterations, the averaged cumulated gradient norm is small with high probability. However, it seems this result cannot exclude a bad case of saddle points, where the gradient norm is small, while since the normalizer in Algorithm 1 is the sum of the historical gradient norm (let's say $g_1$ has its norm at $\\Theta(1)$), the AdaGrad would get stuck around the saddle points, since it will do very small updates around saddle points.\n\n- A more desirable result to explain the effectiveness of AdaGrad would be to show that AdaGrad not only converges to stationary points (which is shown in this paper) but also converges to points with good second order information (local minima rather than saddle points).\n\n- I found the sentence above Eq. (1) \"by choosing to output ... uniformly at random from the set of query points ... is bounded\" a bit confusing. Does this mean the last iteration is not guaranteed to have small gradient norm (I can imagine somehow the algorithm could have oscillation behaviour, but not sure if this is the case here)? And does this imply we need to do some post-processing after running the AdaGrad method (which to my knowledge is not the case)? If this can be turned into a more direct result of last iteration convergence result with high probability, that would be better, since as I am aware of, there are expectation convergence results for last iteration convergence.\n\nminor: Lemma 4.2: $a_i$ in the denominator should be $a_k$?", "summary_of_the_paper": "This paper proposed a new analysis for AdaGrad method in smooth and non-convex optimization, to get high probability convergence toward stationary points.\n\nBased on some assumptions (Eqs. (2), (6) and (7)), i.e., Lipschitz, bounded variance of gradient estimates, and bounded stochastic gradient, the authors analyzed Algorithm 1 (AdaGrad), which does not use any information of the quantities in the assumptions. They show that (in Theorem 4.2), with high probability, the averaged cumulative gradient norm square is converging to $0$ at order of $\\tilde{O}(\\log{(1/\\delta)}/\\sqrt{T})$. The main difficulty is to derive high probability bounds for the two quantities in Eq. (10), i.e., Propositions 4.1 and 4.2.\n\nThe authors then generalized their analysis to the generic AGD template (Algorithm 2), which recovers AdaGrad, AdaGrad with averaging, adaptive RSAG, and AcceleGrad as special cases by choosing different $\\alpha_t$, $\\eta_t$ and $\\gamma_t$ parameters. Similar high probability convergence results can be obtained for AdaGrad with averaging, and adaptive RSAG, but not for AcceleGrad.\n\n", "summary_of_the_review": "Overall, I think this work provides a neat and elegant analysis for AdaGrad and several variants. It shows that AdaGrad behaves similarly in terms of expectation convergence and with high probability convergence. However, I found the results still unsatisfactory in terms of I did not see how those results could explain the good performances achieved by AdaGrad and its variants. To my understanding, this is more like verifying and improving existing analysis to some extent but lack of providing new insights.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a high probability analysis for Adagrad for smooth non-convex optimization and shows its rate of convergence to critical points. Both rates for deterministic optimization and for stochastic optimization are provided. The main contribution of the paper is that unlike for SGD they don’t require knowledge of smoothness parameter in advance and second, they prove high probability results. 

The reviewers lean positively towards the paper. One of the reviewers comments about the comparison with SGD which has some merit. The main comparison of this paper is w.r.t. ward et al 2019 and Zhou et al 2018 both of which prove high probability results. However, both these works require prior knowledge of smoothness parameter. The other axis of comparison is w.r.t algorithms like spider by Fang et al 2018 which uses variance reduction type techniques to obtain the optimal rate for critical point (here it is 1/sqrt{T} for norm square which is T^{-1/4} for norm and spider is T^{-1/3} for norm). Of course, an argument can be made for the fact that the algorithm here is closer to what is used in practice and more importantly, the assumptions there are somewhat stronger. 

In any case, the paper still has interesting results and I am leaning towards an accept.
Decision: Accept (Poster)