Year: 2021

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 O(1/ √ 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/δ) on the probability margin δ. We present our analysis in a modular way and obtain a complementary O(1/T ) convergence rate in the deterministic setting for the same class of algorithms. 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 on probability margin δ.

text: √ 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/δ) on the probability margin δ. We present our analysis in a modular way and obtain a complementary O(1/T ) convergence rate in the deterministic setting for the same class of algorithms. 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 on probability margin δ.

heading: 1 INTRODUCTION
text: Adaptive gradient methods are a staple of machine learning (ML) in solving core problems such as
min x∈Rd
f(x) := Ez∼D [f(x; z)] , (P)
where the objective f(x) is possibly non-convex, and D is a probability distribution from which the random vector z is drawn. Problem (P) captures for instance empirical risk minimization or finite-sum minimization (Shalev-Shwartz & Ben-David, 2014) problems, where z 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 is 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 a 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 a 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 to the probabilistic nature of these methods. While there exist 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 to understand the probabilistic convergence properties of adaptive algorithms, specifically AdaGrad, while focusing on their problem parameter adaptation capabilities in the non-convex setting. In this manuscript, adaptivity refers to the ability of an algorithm to ensure convergence without requiring the knowledge of quantities such as smoothness modulus or 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 f(x) is convex in (P).
This alternative perspective to 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 smoothness modulus, nor a bound on gradient norms neither noise variance.
We summarize our contributions as follows:
1. We provide a modular and simplified high probability analysis for AdaGrad-type adaptive methods.
2. We present the first optimal high probability convergence result of the original AdaGrad algorithm for non-convex smooth problems. Concretely,
(a) we analyze a fully adaptive step-size that is oblivious to Lipschitz constant L and the noise level σ,
(b) our analysis demonstrates the best known dependence of log(1/δ) on the probability margin δ.
3. We present new adaptive versions of AdaGrad extensions that include averaging and momentum primitives, and prove similar high probability bounds for these methods as well. Concretely, we present a general adaptive template and provide complementary convergence results for different step-size regimes which individually recovers standard AdaGrad, AdaGrad with averaging and adaptive RSAG (Ghadimi & Lan, 2016).
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.

heading: 2 RELATED WORK
text: 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 a few. Simply put, such AdaGrad-type methods compute step-sizes on-the-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 convergence rates under different settings, without any modifications. For convex minimization problems, Levy et al. (2018) showed that AdaGrad attains a rate of O(1/T + σ/ √ T ) by implicitly adapting to smoothness and noise levels in the feedback; here T is the number of noisy gradient queries and σ is the noise variance. They also proposed an accelerated AdaGrad variant with scalar step-size. The latter result was extended for compactly constrained problems by (Kavis et al., 2019), by devising accelerated Mirror-Prox algorithm. Very recently, Ene et al. (2021) have further generalized the latter results by designing and analyzing a novel adaptive and accelerated AdaGrad version with per-coordinate step-sizes. Convergence properties of these universal (and some accelerated) adaptive 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 et al., 2019; Defossez et al., 2020; Alacaoglu et al., 2020a; Chen et al., 2020). The majority of the theoretical results on adaptive methods for nonconvex problems focus on their in expectation performance.
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 AdaGrad (with lag-one-behind step-size) for smooth, non-convex losses under subgaussian noise and proved O(σ √ log(T/δ)/ √ T ) rate. Under similar conditions, Zhou et al. (2018) proves convergence of order O((σ2 log(1/δ))/T + 1/ √ T ) for AdaGrad. However, both works require the knowledge of smoothness to set the step-size. Moreover, Ward et al. (2019) guarantees that AdaGrad with scalar step-size convergences at O((1/δ) log(T )/ √ T ) rate with high probability. Although their framework is oblivious to smoothness constant, their dependence of probability margin is far from optimal. More recently, under heavy-tailed noise having bounded pth moment for p ∈ (1, 2), Cutkosky & Mehta (2021) proves a rate of O(log(T/δ)/T (p−1)/(3p−2)) for clipped normalized SGD with momentum; nevertheless their method requires the knowledge of (a bound on) the behavior of the heavy tails.

heading: 3 SETUP AND PRELIMINARIES
text: As we stated in the introduction, we consider the unconstrained minimization setting min x∈Rd f(x) := Ez∼D [f(x; z)] ,
where the differentiable function f : Rd → R is a smooth and (possibly) nonconvex function. We are interested is finding a first-order -stationary point satisfying ‖∇f(xt)‖2 ≤ , where ‖·‖ denotes 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, 1T ∑T t=1 ‖∇f(xt)‖2. It immediately implies convergence in minimum gradient norm, mint∈[T ] ‖∇f(xt)‖2. Moreover, note that if we are able to bound 1T ∑T t=1 ‖∇f(xt)‖2, then by choosing to output a solution x̄T which is chosen uniformly at random from the set of query points {x1, . . . , xT }, then we ensure that E‖∇f(x̄T )‖2 := 1T ∑T t=1 ‖∇f(xt)‖2 is bounded.
A function is called G-Lipschitz continuous if it satisfies |f(x)− f(y)| ≤ G‖x− y‖, ∀x, y ∈ dom(f), (1)
which immediately implies that ‖∇f(x)‖ ≤ G, ∀x ∈ dom(f). (2)
A differentiable function is called L-smooth if it has L-Lipschitz gradient ‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖, ∀x, y ∈ dom(∇f). (3)
An equivalent characterization of smoothness is sometimes referred to as the “descent lemma” (Ward et al., 2019; Beck, 2017), i.e.,
|f(x)− f(y)− 〈∇f(y), x− y〉| ≤ L 2
2 ‖x− y‖2. (4)
Assumptions on oracle model: We denote stochastic gradients with ∇̃f(x) = ∇f(x; z), 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 [ ∇̃f(x)|x ] = ∇f(x), ∀x ∈ dom(∇f). (5)
Gradient estimates generated by a first-order oracle are said to have bounded variance if they satisfy E [ ‖∇̃f(x)−∇f(x)‖2|x ] ≤ σ2, ∀ ∈ dom(∇f). (6)
Finally, we assume that the stochastic gradient are bounded almost surely, i.e.,
‖∇̃f(x)‖ ≤ G̃, ∀x ∈ dom(∇f). (7) 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).

heading: 4 PROPOSED ANALYSIS AND ADAGRAD
text: This section introduces our proposed proof technique as well as our main theoretical results for AdaGrad with proof sketches and respective discussions for clarifying key elements of our theoretical findings. We will present a high-level overview of our simplified, modular proof strategy while proving a complementary convergence result for AdaGrad under deterministic oracles. In the sequel, we refer to the name AdaGrad as the scalar step-size variant of the algorithm (also known as AdaGrad-Norm) as we present in Algorithm 1.
Algorithm 1 AdaGrad Input: time horizon T , x1 ∈ Rd, step-size {ηt}t∈[T ], G0 > 0
1: for t = 1, ..., T do 2: Generate gt = ∇̃f(xt) 3: ηt =
1√ G20+ ∑t k=1 ‖gk‖2
4: xt+1 = xt − ηtgt 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 ] as a shorthand expression for the set {1, 2, ..., T}. We will use ∆t = f(xt) − minx∈Rd f(x) as a concise notation for objective suboptimality and ∆max = maxt∈[T+1] ∆t will denote the maximum over ∆t. In the rest of Section 4, we denote stochastic gradient of f at xt by gt = ∇̃f(xt) = ∇f(xt; zt) and its deterministic equivalent as ḡt := ∇f(xt). We also use the following notation for the noise vector ξt := gt − ḡt. 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 Õ(log(1/δ)/ √ T ) for finding an approximate stationary point. Moreover, Theorem 4.1 shows that in the deterministic case AdaGrad achieves an optimal rate of O(1/T ), thus establishing its universality.

heading: 4.1 TECHNICAL LEMMAS
text: We make use of a few technical lemmas while proving our main results, which we refer to in 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 a1, ..., an be a sequence of non-negative real numbers. Then, it holds that√√√√ n∑
i=1 ai ≤ n∑ i=1 ai√∑i k=1 ak ≤ 2 √√√√ n∑ i=1 ai
Lemma 4.2. Let a1, ..., an be a sequence of non-negative real numbers. Then, it holds that n∑ i=1 ai∑i k=1 ai ≤ 1 + log ( 1 + n∑ i=1 ai )
The next lemma is the key for achieving the high probability bounds.. Lemma 4.3 (Lemma 3 in Kakade & Tewari (2008)). Let Xt be a martingale difference sequence such that |Xt| ≤ b. Let us also define
Vart−1(Xt) = Var (Xt | X1, ..., Xt−1) = E [ X2t | X1, ..., Xt−1 ] ,
and VT = ∑T t=1 Vart−1(Xt) as the sum of variances. For δ < 1/e and T ≥ 3, it holds that
P ( T∑ t=1 Xt > max { 2 √ VT , 3b √ log(1/δ) }√ log(1/δ) ) ≤ 4 log(T )δ (8)
Please refer to first section in the appendix for the proofs of technical lemmas.

heading: 4.2 OVERVIEW OF PROPOSED ANALYSIS
text: We will start by presenting the individual steps of our proof and provide insight into its advantages. In the rest of this section, we solely focus on 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 ḡt = ∇f(xt) and gt = ∇f(xt; zt) = ḡt + ξt, the classical analysis begins with,
f(xt+1)− f(xt) ≤ −ηt‖ḡt‖2 − ηt〈ḡt, ξt〉+ Lη2t
2 ‖gt‖2.
which is due to the smoothness property in Eq. (4). Re-arranging and summing over t ∈ [T ] yields, T∑ t=1 ηt‖ḡt‖2 ≤ f(x1)− f(x∗) + T∑ t=1 −ηt〈ḡt, ξt〉+ L 2 T∑ t=1 η2t ‖gt‖2.
The main issue in this expression is the ηt〈ḡt, ξt〉 term, which creates measurability problems due to the fact hat ηt and ξt are dependent random variables. On the left hand side, the mismatch between ηt and ‖ḡt‖2 prohibits the use of technicals lemmas as we accumulate stochastic gradients for ηt. Moreover, we cannot make use of Holder-type inequalities as we deal with high probability results. Instead, we divide both sides by ηt, then sum over t and re-arrange to obtain a bound of the form,
T∑ t=1 ‖ḡt‖2 ≤ ∆1 η1 + T∑ t=2 ( 1 ηt − 1 ηt−1 ) ∆t + T∑ t=1 −〈ḡt, ξt〉+ L 2 T∑ t=1 ηt‖gt‖2
≤ ∆max ηT + T∑ t=1 −〈ḡt, ξt〉+ L 2 T∑ t=1 ηt‖gt‖2 (9)
This modification solves the two aforementioned problems, but we now need to argue about boundedness of function values, specifically the maximum distance to the optimum, ∆max. 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 a restrictive assumption to make for general smooth minimization problems and we will prove that it is bounded or at least it grows no faster than O(log(T )). As a key element of our approach, we will show that this is the case for Algorithms 1 and 2. Now, we are at a position to state an overview of our proof strategy:
1. Show that ∆max ≤ O(log(T )) with high probability or ∆max ≤ O(1) (deterministic). 2. Prove that ∑T t=1−〈ḡt, ξt〉 ≤ Õ( √ T ) with high probability using Lemma 4.3.
3. Show that L2 ∑T t=1 ηt‖gt‖2 ≤ O( √ T ) 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 a sketch of the proof, whose full version will be accessible in the appendix. Theorem 4.1. Let xt be generated by Algorithm 1 with G0 = 0 for simplicity. Then, it holds that
1
T T∑ t=1 ‖∇f(xt)‖2 ≤ O ( (∆1 + L) 2 T ) .
Proof Sketch (Theorem 4.1). Setting ḡt = ∇f(xt), deterministic counterpart of Eq. (9) becomes
T∑ t=1 ‖ḡt‖2 ≤ ∆max ηT + L 2 T∑ t=1 ηt‖ḡt‖2 ≤ (∆max + L) √√√√ T∑ t=1 ‖ḡt‖2,
where we obtain the final inequality using Lemma 4.1. Now, we show that ∆T+1 is bounded for any T . Using descent lemma and summing over t ∈ [T ],
f(xT+1)− f(x∗) ≤ f(x1)− f(x∗) + T∑ t=1 ( Lηt 2 − 1 ) ηt‖ḡt‖2
Now, define t0 = max { t ∈ [T ] | ηt > 2L } , such that ( Lηt 2 − 1 ) ≤ 0 for any t > t0. Then,
f(xT+1)− f(x∗) ≤ ∆1 + t0∑ t=1 ( Lηt 2 − 1 ) ηt‖ḡt‖2 + T∑ t=t0+1 ( Lηt 2 − 1 ) ηt‖ḡt‖2
≤ ∆1 + L
2 t0∑ t=1 η2t ‖ḡt‖2 ≤ ∆1 + L 2 ( 1 + log ( 1 + L2/4 )) ,
where we use the definition of t0 and Lemma 4.2 for the last inequality. Since this is true for any T , the bound holds for ∆max, as well. Defining X = √∑T
t=1 ‖ḡt‖2, the original expression reduces to X2 ≤ (∆max + L)X . Solving for X , plugging in the bound for ∆max and dividing by T results in
1
T T∑ t=1 ‖∇f(xt)‖2 ≤ ( ∆1 + L 2 ( 3 + log ( L2/4 )))2 T .
Remark 2. To our knowledge, the most relevant analysis was provided by Ward et al. (2019), which achieves O(log(T )/T ) convergence rate. Our new approach enables us to remove log(T ) dependence at the cost of computing the bound on ∆max.

heading: 4.3 HIGH PROBABILITY CONVERGENCE UNDER STOCHASTIC ORACLE
text: Having introduced the building blocks of our strategy, 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)
T∑ t=1
‖ḡt‖2 ≤ ∆max ηT︸ ︷︷ ︸ (∗) +
T∑ t=1
−〈ḡt, ξt〉︸ ︷︷ ︸ (∗∗)
+ L
2 T∑ t=1
ηt‖gt‖2︸ ︷︷ ︸ (∗∗∗)
(10)
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 δ < 1/e, we have
T∑ t=1 −〈ḡt, ξt〉 ≤ 2σ √ log(1/δ) √√√√ T∑ t=1 ‖ḡt‖2 + 3(G2 +GG̃)log(1/δ).
The last ingredient of the analysis is the bound on ∆t. The following proposition ensures a high probability bound of order O(log(t)) on ∆t under Algorithm 1. Proposition 4.2. Let xt be generated by AdaGrad forG0 > 0. With probability at least 1−4 log(t)δ,
∆t+1 ≤ ∆1 + 2L ( 1 + log ( max{1, G20}+ G̃2t )) +G−10 (M1 + σ 2) log(1/δ) +M2,
where M1 = 3(G2 +GG̃) and M2 = G−10 (2G 2 +GG̃).
As an immediate corollary, since the statement of Proposition 4.2 holds for any t, it holds for ∆max by definition. Hence, we have that maxt∈[T ] ∆t = ∆max ≤ O ( ∆1 + L log(T ) + σ 2 log(1/δ) )
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 xt be the sequence of iterates generated by AdaGrad. Under Assumptions 2, 6, 7, for ∆max ≤ O ( ∆1 + L log(T ) + σ 2 log(1/δ) ) , with probability at least 1− 8 log(T )δ,
1
T T∑ t=1 ‖ḡt‖2 ≤ (∆max + L)G0 + 3(G 2 +GG̃)log(1/δ) T +
(∆max + L) G̃+ 2Gσ √
log(1/δ)√ T .
Remark 3. Let the statement of Proposition 4.1 be denoted as event A and statement of Proposition 4.2 by event B. Theorem 4.2 essentially requires a lower bound for P (A ∩B). Aforementioned propositions already established that P (A) ≥ 1 − 4 log(T )δ and P (B) ≥ 1 − 4 log(T )δ. By probability axioms it holds that P (A ∩B) ≥ 1− 8 log(T )δ, which we prove in the appendix.
Proof Sketch (Theorem 4.2). Define ḡt = ∇f(xt) and gt = ∇f(xt; zt) = ḡt + ξt. By Eq. (10), T∑ t=1 ‖ḡt‖2 ≤ ∆max ηT + T∑ t=1 −〈ḡt, ξt〉+ L 2 T∑ t=1 ηt‖gt‖2.
Invoking Lemma 4.1 on the last sum and using Proposition 4.1 for the second expression, we have with probability at least 1− 4 log(T )δ T∑ t=1 ‖ḡt‖2 ≤ (∆max + L) √√√√G20 + T∑ t=1 ‖gt‖2 + 2σ √ log(1/δ) √√√√ T∑ t=1 ‖ḡt‖2 + 3(G2 +GG̃)log(1/δ)
Finally, we use the bounds on the gradient norms ‖ḡt‖ ≤ G and ‖gt‖ ≤ G̃, re-arrange the terms and divide both sides by T . Due to Proposition 4.2, with probability at least 1− 8 log(T )δ,
1
T T∑ t=1 ‖ḡt‖2 ≤ (∆max + L)G0 + 3(G 2 +GG̃)log(1/δ) T +
(∆max + L) G̃+ 2Gσ √
log(1/δ)√ T ,
where ∆max ≤ O ( ∆1 + L log(T ) + σ 2 log(1/δ) ) . We keep ∆max in the original bound due to space constraints.

heading: 5 GENERALIZATION TO AGD TEMPLATE
text: Having proven the high probability convergence for AdaGrad, we will now present an 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).
Algorithm 2 Generic AGD Template Input: Horizon T , x̃1 = x1 ∈ Rd, αt ∈ (0, 1], step-sizes {ηt}t∈[T ], {γt}t∈[T ]
1: for t = 1, ..., T do 2: x̄t = αtxt + (1− αt)x̃t 3: Set gt = ∇f(x̄t) or gt = ∇̃f(x̄t) = ∇f(xt; zt) 4: xt+1 = xt − ηtgt 5: x̃t+1 = x̄t − γtgt 6: end for 7:
This particular reformulation was recently referred to as 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 on two aspects of the algorithm; averaging parameter αt and selection of (adaptive) step-sizes ηt and γt. We could recover some well-known algorithms from this generic scheme depending on parameter choices, which we display in Table 1.
Our reason behind choosing this generic algorithm is two-fold. First, it helps us demonstrate flexibility of our simplified and modular proof technique by extending it to a much general algorithmic template. Second, as an integral element of this scheme, we wanted to study the notion of averaging (or equivalently momentum (Defazio, 2021)), which is an important primitive for several 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 noisy feedback (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 αt and step sizes ηt and γt. The averaging parameter αt has two possible forms: αt = 2/(t+ 1) for weighted averaging and αt = 1/t for uniform averaging. We take αt = 2/(t+ 1) by default in our analysis, as it is a key element in achieving acceleration in the convex setting. Let us define the AdaGrad step size once more, which we use to define ηt and γt,
η̃t = (G 2 0 + t∑ k=1 ‖gk‖2)−1/2, G0 > 0. (11)
The first instance of Algorithm 2 is the AdaGrad, i.e. xt+1 = xt − η̃tgt. Since x̃1 = x1 by initialization, we have x̄1 = x̃1 = x1. The fact that ηt = γt = η̃t implies the equivalence x̃t = xt for any t ∈ [T ], which ignores averaging step and results in a single line of update. The second instance we recover is AdaGrad with averaging, i.e.,
x̄t = αtxt + (1− αt)x̄t−1 xt+1 = xt − αtηtgt,
(12)
where ηt = η̃t and γt = 0. For the initialization x1 = x̃1, we can obtain by induction that x̃t = x̄t−1, hence the scheme above. The final scheme we will analyze is RSAG algorithm proposed by Ghadimi & Lan (2016). It selects a step size pair that satisfies γt ≈ (1 + αt)η̃t and ηt = η̃t, generating a 3-sequence algorithm as in the original form of Algorithm 2.
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, γt is always only a constant factor away from ηt. This phenomenon has an immediate connection to acceleration in the convex realm, which is of independent interest to us and we will return to that later.
Having defined instances of Algorithm 2, we 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 as before to finalize the bound.
Let us define ḡt = ∇f(x̄t) and gt = ∇f(x̄t; zt) = ḡt + ξt. Following the notation in (Ghadimi & Lan, 2016), let Γt = (1− αt)Γt−1 with Γ1 = 1. Now, we can begin with the departure point of the proof, which is due to Ghadimi & Lan (2016).
Proposition 5.1. Let xt be generated by Algorithm 2 where gt = ∇f(x̄t; zt) = ḡt + ξt and ḡt = ∇f(x̄t). Then, it holds that
T∑ t=1 ‖ḡt‖2 ≤ ∆max + 2L ηT + L 2ηT T∑ t=1 [ T∑ k=t (1− αk)Γk ] αt Γt︸ ︷︷ ︸
(∗)
(ηt − γt)2
α2t ‖gt‖2 + T∑ t=1
−〈ḡt, ξt〉︸ ︷︷ ︸ (∗∗) .
Next, we will deliver the complementary bound on term (∗) in Proposition 5.1. Proposition 5.2. Using the recursive definition of Γ, we have[
T∑ k=t (1− αk)Γk ] αt Γt ≤ { 2 if αt = 2t+1 ; log(T + 1) if αt = 1t .
Finally, we present the high probability convergence rates for AdaGrad with averaging and RSAG. Theorem 5.1. Let xt be the sequence of iterates generated by AdaGrad with averaging or adaptive RSAG. Under Assumptions 2, 6, 7, for ∆max ≤ O ( ∆1 + L log(T ) + σ 2 log(1/δ) ) , with probability 1− 8 log(T )δ,
1
T T∑ t=1 ‖ḡt‖2 ≤ G0
( ∆max + 3L+ L log ( max{1, G−20 }+ G̃2T )) + 3(G2 +GG̃)log(1/δ))
T + G̃ ( ∆max + 3L+ L log ( max{1, G−20 }+ G̃2T )) + 2Gσ √
log(1/δ) √ T
A discussion on acceleration and nonconvex analysis: AGD and its variants are able to converge at the fast rate of O(1/T 2) (Nesterov, 2003) for smooth, convex objectives, while matching the convergence rate of GD in the nonconvex landscapes. In 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 a 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 a time-scale difference of O(t) between ηt and γt, and it runs with a modified step-size of ηt =(
1 + ∑t k=1 α −2 k ‖gt‖2 )−1/2 . 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
L
2ηT T∑ t=1 η2t α4t ‖gt‖2,
where each summand is O(t4) orders of magnitude larger compared to other methods. A factor of α−2t = t
2 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.

heading: 6 CONCLUSIONS
text: 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 σ while having optimal dependence of log(1/δ) on probability margin δ. To our knowledge, this is the first such result for adaptive methods, including AdaGrad.

Review summaries:
This paper proposed a new analysis for AdaGrad method in smooth and non-convex optimization, to get high probability convergence toward stationary points.  Based 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.  The 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.  

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. In 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. The final results include a dependence on the smoothness constant $L$ and variance $\sigma$ which are not explicitly used in the algorithm.