Conceptio › Archive › arXiv CS

arXiv CSopen access

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Zijian Liu 1

arXiv:2605.18694v1 [math.OC] 18 May 2026

Abstract

when training attention-based models (Vaswani et al., 2017; Zhang et al., 2020b; Ahn et al., 2024). More concretely, it refers to the gradient noise (i.e., the difference between the stochastic gradient and the true gradient) having only a finite p-th moment for some p ∈ (1, 2], rather than satisfying the classical finite-variance condition (i.e., p = 2) commonly adopted in the stochastic optimization literature (Bottou et al., 2018; Lan, 2020).

Many tasks in modern machine learning are observed to involve heavy-tailed gradient noise during the optimization process. To manage this realistic and challenging setting, new mechanisms, such as gradient clipping and gradient normalization, have been introduced to ensure the convergence of first-order algorithms. However, adaptive gradient methods, a famous class of modern optimizers that includes popular Adam and AdamW, often perform well even without any extra operations mentioned above. It is therefore natural to ask whether adaptive gradient methods can converge under heavy-tailed noise without any algorithmic changes. In this work, we take the first step toward answering this question by investigating a special case, AdaGrad, the origin of adaptive gradient methods. We provide the first provable convergence rate for AdaGrad in non-convex optimization when the tail index p satisfies 4/3 < p ≤ 2. Notably, this result is achieved without requiring any prior knowledge of p and is hence adaptive to the tail index. In addition, we develop an algorithm-dependent lower bound, suggesting that the existing minimax rate for heavy-tailed optimization is not attainable by AdaGrad. Lastly, we consider AdaGrad-Norm, a popular variant of AdaGrad in theoretical studies, and show an improved rate that holds for any 1 < p ≤ 2 under an extra mild assumption.

For first-order methods, two approaches are known to guarantee provable convergence in non-convex optimization under heavy-tailed noise. One way is based on gradient clipping (i.e., Clipped Stochastic Gradient Descent (Clipped SGD)), which artificially limits the norm of the stochastic gradient within a user-specific threshold (Zhang et al., 2020b; Liu et al., 2023c; Sadiev et al., 2023; Nguyen et al., 2023). The other kind relies on gradient normalization, as recently discovered by Hübler et al. (2025); Liu & Zhou (2025); Sun et al. (2025), who show that the normalization mechanism in Normalized Stochastic Gradient Descent (with Momentum) (NSGD(M)) (Nesterov, 1984; Cutkosky & Mehta, 2020) can also successfully tackle heavy-tailed noise. Interestingly, Hübler et al. (2025); Liu & Zhou (2025) also provided a convergence rate achieved without any prior knowledge of problem-dependent parameters, which is the first in the literature. In particular, the feature of not requiring any information on the tail index p highlights a key advantage of using NSGD(M). Despite the progress, an important gap still remains between theory and practice. Specifically, the above results cannot cover a well-known class of algorithms widely used in practice, namely, adaptive gradient methods, whose empirical effectiveness has been repeatedly demonstrated in the training of neural networks, including large language models. This class includes AdaGrad, introduced in two pioneering works (McMahan & Streeter, 2010; Duchi et al., 2011), followed by RMSProp (Tieleman et al., 2012), then more practical algorithms nowadays, such as Adam (Kingma & Ba, 2014) and AdamW (Loshchilov & Hutter, 2019), along with many further variants. In other words, the reason for the strong performance of adaptive gradient methods under heavy-tailed noise remains largely unclear and warrants further exploration.

1. Introduction The heavy-tailed phenomenon has been widely observed in the optimization process for modern machine learning tasks across various domains (Simsekli et al., 2019; Garg et al., 2021; Battash et al., 2024), and is particularly prevalent 1 Stern School of Business, New York University. Correspondence to: Zijian Liu <[email protected]>.

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

To the best of our knowledge, only one recent work by Chezhegov et al. (2025) studies AdaGrad- and Adam-based methods under heavy-tailed noise. However, their work has some limitations that we will discuss below.

cations, nonstandard assumptions, or prior knowledge of problem-dependent parameters, thereby (partially) confirming the question asked earlier. • In Theorem 3.3, we establish the first algorithmdependent lower bound for AdaGrad in heavy-tailed non-convex optimization, explicitly capturing the dependence on the input learning rate. Our result suggests that the existing minimax rate for heavy-tailed non-convex optimization (Zhang et al., 2020b; Liu & Zhou, 2025; Liu, 2026) is generally not attainable by AdaGrad. Even in the special case of p = 2, our bound also improves upon the existing lower bound for AdaGrad proved by Jiang et al. (2025).

First and foremost, the main results presented in Chezhegov et al. (2025) are established for delayed adaptive gradient algorithms introduced by Li & Orabona (2019), in which the stepsize constructed at the t-th iteration depends only on stochastic gradients up to time t − 1, rather than time t. It is known that the delayed variant requires a different style of theoretical analysis, since it makes the stepsize and the stochastic gradient conditionally independent. Moreover, this modification is rarely implemented in practice. Consequently, the applicability of their theoretical guarantees to practical algorithms is limited, leaving the gap open.

Moreover, we study AdaGrad-Norm (Ward et al., 2019), a popular variant of AdaGrad in theoretical research.

Next, Theorem 3.3 in Chezhegov et al. (2025) is the only result in their work not for the delayed setting. However, it still cannot directly apply to AdaGrad and Adam, as the algorithms considered there do not employ the coordinate-wise update and additionally require gradient clipping. Moreover, from a theoretical perspective, their Theorem 3.3 has two shortcomings. One is the extra assumption of boundedness for objective functions, which is stronger than the standard lower boundedness condition in the non-convex optimization literature, thereby reducing the generality. The other is requiring the value of problem-dependent parameters (e.g., the tail index p) as inputs to ensure convergence, contradicting the original purpose of adaptive gradient methods.

• In Theorem 4.2, we prove that AdaGrad-Norm conp−1 verges at a rate of O(1/T 2p ) under the additional assumption of bounded objectives, as considered in Chezhegov et al. (2025). This rate never becomes vacuous for any p ∈ (1, 2] and also does not require any prior information on problem-dependent parameters. • In Theorem C.1, we further provide an upper bound 3p−4 of Õ(1/T 4p ) for AdaGrad-Norm without the extra boundedness assumption, matching the rate for AdaGrad in terms of T in the same setting.

Therefore, Chezhegov et al. (2025) cannot fully explain the empirical success of adaptive gradient methods under heavytailed noise, leaving a large room for further improvement.

Finally, in Section 5, we also discuss the limitations of our work and outline possible future directions.

Motivated by the above discussion, we are naturally led to the following question:

1.2. Related Work We first review the literature on adaptive gradient methods.

Can adaptive gradient methods converge under heavy-tailed noise in non-convex optimization, without any algorithmic modifications, nonstandard assumptions, or prior knowledge of problem-dependent parameters?

Adaptive gradient methods. The study of adaptive gradient methods traces back to two pioneering works (McMahan & Streeter, 2010; Duchi et al., 2011), independently introducing the first adaptive gradient method AdaGrad. Later on, RMSProp, a combination of AdaGrad and the mean square estimation technique, was proposed by Tieleman et al. (2012). By further incorporating momentum into RMSProp, Adam was developed in the seminal work of Kingma & Ba (2014). Furthermore, Loshchilov & Hutter (2019) introduced decoupled weight decay into Adam, resulting in a new algorithm now known as AdamW. In addition to these methods, numerous variants exist in the literature, for example, AMSGrad (Reddi et al., 2018) and Adafactor (Shazeer & Stern, 2018).

1.1. Our Contributions In this work, we take the first step toward answering the above question through a case study of AdaGrad, the origin of adaptive gradient methods, and make the following contributions: • In Theorem 3.1, we show that AdaGrad provably con3p−4 verges at a rate of Õ(1/T 4p ) after T iterations under heavy-tailed noise in non-convex optimization, which is meaningful when p ∈ (4/3, 2]. To the best of our knowledge, this result provides the first theoretical justification for the convergence of AdaGrad in the heavy-tailed setting, without any algorithmic modifi-

Although many adaptive gradient methods were originally designed to guarantee sublinear regret in online convex optimization (e.g., AdaGrad and Adam), they have been 2

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad p−1

observed to perform well across a wide range of modern machine learning tasks, which are however typically nonconvex. As far as we know, Ward et al. (2019) established the first provable rate for AdaGrad-Norm (a simple variant of AdaGrad), serving as a cornerstone of theoretical studies for adaptive gradient methods in non-convex optimization. Subsequently, a large body of work has developed comprehensive studies of the convergence theory for different adaptive gradient methods, including AdaGrad, RMSProp, Adam, and AdamW (or their variants), in both deterministic and stochastic non-convex optimization (Zaheer et al., 2018; De et al., 2018; Zou et al., 2019; Shi et al., 2021; Défossez et al., 2022; Kavis et al., 2022; Faw et al., 2022; Zhang et al., 2022; Faw et al., 2023; Liu et al., 2023b; Attia & Koren, 2023; YANG et al., 2023; Wang et al., 2023a;b; 2024; Hong & Lin, 2024; Liu et al., 2025; Jiang et al., 2025; Zhang et al., 2025; Li et al., 2025). However, under the classical finite-variance assumption (or similar conditions), the existing theory does not reflect a substantial advantage of adaptive gradient methods over SGD, as they share the same 1 convergence rate Õ(1/T 4 ) in terms of the time horizon T to find a stationary point.

achieve the optimal rate of O(1/T 3p−2 ) when prior information about the problem is available. Moreover, Hübler et al. (2025); Liu & Zhou (2025) also prove that NSGD(M) p−1 can converge at a rate of O(1/T 2p ) without any prior information. Lower bound under heavy-tailed noise. For non-convex optimization under heavy-tailed noise, to find an ϵ-stationary point in expectation, any (possibly randomized) algorithm 3p−2 p must query at least Ω(∆Lϵ−2 + ∆Lσ p−1 ϵ− p−1 ) stochastic gradients (Zhang et al., 2020b; Liu & Zhou, 2025; Liu, 2026), where p ∈ (1, 2] is the tail index, ∆ denotes the initial function value gap, L > 0 is the smoothness parameter, and σ ≥ 0 characterizes the noise level. However, the algorithm (e.g., Clipped SGD) that can achieve this minimax lower bound often requires prior knowledge of all these parameters, which is usually not practical. Recently, Hübler et al. (2025) establishes the first algorithmdependent lower bound for NSGD in one-dimensional optimization that captures the dependence on the stepsize and batch size when problem-dependent parameters are unknown in advance. In particular, their result can be sim2p 2p plified to an Ω((∆4 + L4 )ϵ−4 + σ p−1 ϵ− p−1 ) lower bound for NSGD when no prior information is available.

As for lower bounds of adaptive gradient methods, the only result we are aware of is for AdaGrad1 under p = 2 given by Jiang et al. (2025), which establishes a complexity lower bound of Ω((∆Lϵ−2 + ∆Lσ 2 ϵ−4 ) ln(∆Lϵ−2 ))2 to find an ϵ-stationary point, where ∆ denotes the initial function value gap, L > 0 is the smoothness parameter, and σ ≥ 0 characterizes the noise level. This bound is larger than the minimax rate for stochastic non-convex optimization under the finite-variance condition (Arjevani et al., 2023). However, it is not algorithm-dependent, since it fails to capture the dependence on the input learning rate.

2. Preliminary Notation. In this paper, scalars and vectors are denoted by regular and bold fonts, respectively. N is the set of natural numbers (excluding 0). [n] ≜ {1, . . . , n} , ∀n ∈ N. ⌈·⌉ is the ceiling function. For a > 1, we denote by ā the conjugate of a (i.e., a1 + ā1 = 1). Rd>0 (resp. Rd≥0 ) is the set of vectors in Rd whose coordinates are all positive (resp. non-negative). Given Λ ∈ Rd>0 , its induced Pd inner product p and norm are ⟨x, y⟩Λ ≜ i=1 xi Λi y i and ∥x∥Λ ≜ ⟨x, x⟩Λ , respectively. In addition, we use the xi following shorthands (xy)i ≜ xi y i , x2 ≜ xx, ( x y )i ≜ y i , √ √ and ( z)i = z i for any i ∈ [d] and x, y ∈ Rd , z ∈ Rd≥0 . Given a differentiable function h, ∇i h is the partial derivative w.r.t. the i-th coordinate.

Next, we provide a basic background on smooth non-convex optimization under heavy-tailed noise. Upper bound under heavy-tailed noise. For clippingbased algorithms (e.g., Clipped SGD), several works have p−1 established the optimal convergence rate O(1/T 3p−2 ) (or p−1 Õ(1/T 3p−2 )) in both expectation and high probability (Zhang et al., 2020b; Cutkosky & Mehta, 2021; Liu et al., 2023c; Nguyen et al., 2023). Such rates are always derived based on the prior value of problem-dependent parameters, in particular, the tail index p. Recent works (Hübler et al., 2025; Liu & Zhou, 2025; Sun et al., 2025) further show that the normalization-based method (i.e., NSGD(M)) can also

Objective.

This work studies the optimization problem min f (x),

x∈Rd

where f : Rd → R is differentiable and possibly nonconvex. Since finding a global optimal solution can be computationally intractable, we shift the focus to minimizing ∥∇f (x)∥ as in the non-convex optimization literature.

1 For AdaGrad, Crawshaw & Liu (2025) also proved a lower bound result that is not directly comparable to Jiang et al. (2025) due to a different setting. 2 For convenience, we only state their result in the onedimensional case. Jiang et al. (2025) also established a lower bound in the high-dimensional case.

Assumptions. We first make the following assumptions. Assumption 2.1 (Lower boundedness). The objective satisfies f⋆ ≜ inf x∈Rd f (x) > −∞. 3

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Algorithm 1 AdaGrad (McMahan & Streeter, 2010; Duchi et al., 2011) Input: initial point x1 ∈ Rd , learning rate γ > 0, hyperparameter λ > 0 Initialization: v 0 = 0 for t = 1 to T do v t = v t−1 + g 2t xt+1 = xt − λ+γ√vt g t end for Assumption 2.2 (Smoothness). ∃L ∈ Rd>0 such that 2 |f (x) − f (y) − ⟨∇f (y), x − y⟩| ≤ 12 ∥x − y∥L for any d x, y ∈ R , or equivalently, ∥∇f (x) − ∇f (y)∥1/L ≤ ∥x − y∥L for any x, y ∈ Rd .

3. AdaGrad under Heavy-Tailed Noise The optimizer focused on in this work, AdaGrad, is described in Algorithm 1. AdaGrad was independently introduced in two pioneering works by McMahan & Streeter (2010) and Duchi et al. (2011). The key mechanism of AdaGrad is to dynamically adjust the stepsize, i.e., λ+γ√vt , based on all stochastic gradient information up to the current iteration in a coordinate-wise manner.

Assumption 2.1 is standard in the literature. Assumption 2.2 is the coordinate-wise counterpart of the classical smoothness condition. This kind of fine-grained smoothness has been studied before, for example, in Bernstein et al. (2018; 2019); Liu et al. (2023a); Jiang et al. (2025); Liu et al. (2025).

3.1. Upper Bound We present the first provable upper bound for AdaGrad under heavy-tailed noise in the following Theorem 3.1, the proof of which is deferred to Appendix A.

Since we consider stochastic optimization, given a point xt ∈ Rd at the t-th iteration, g t hereinafter denotes the stochastic gradient queried at xt . Ft ≜ σ (g 1 , . . . , g t ) is the natural filtration, and Et [·] ≜ E [· | Ft ] represents the conditional expectation given Ft .

Theorem 3.1. Under Assumptions 2.1, 2.2, 2.3, and 2.4, let ∆ ≜ f (x1 ) − f⋆ , then for any γ > 0 and λ > 0, AdaGrad (Algorithm 1) guarantees " # T 1X E ∥∇f (xt )∥1 T t=1 ! p √ B ∥σ∥1 C ∥σ∥1 C ∥σ∥1 A ≤O √ + + + , p−1 p−1 3p−4 T T p T 2p T 4p

Our analysis also relies on the next two assumptions. Assumption 2.3 (Unbiased gradient). The stochastic gradient satisfies Et−1 [g t ] = ∇f (xt ). Assumption 2.4 (Heavy-tailed noise). ∃p ∈ (1, 2] and σ ∈ p Rd≥0 such that Et−1 ξ t,i ≤ σ pi , ∀i ∈ [d], where ξ t,i ≜ g t,i − ∇i f (xt ). Remark 2.5. Our proof strategy still works when replacing pi Assumption 2.4 with a weaker version: Et−1 ξ t,i ≤ σ pi i , ∀i ∈ [d], where pi ∈ (1, 2] can take different values for different coordinates. However, to make the work more concise, we keep the current simpler version.

where A ≜ dλ + ∆ γ + γ ∥L∥1 ln KT , B ≜

∆ γ

1 1 p̄ + 2

KT , and KT is in the order γ ∥L∥1 ln KT , C ≜ ln of poly(T, ∥L∥1 , ∥L∥∞ , ∥σ∥∞ , ∥∇f (x1 )∥∞ , γ, 1/λ). Remark 3.2. For the precise definition of KT , we refer the reader to Theorem A.1.

Assumption 2.3 is a common condition in stochastic optimization. Assumption 2.4 appears in Chezhegov et al. (2025) and differs slightly from the popular one for heavytailed noise in the literature, which typically takes the form p of Et−1 [∥ξ∥2 ] ≤ σ p for some σ ≥ 0. It can be interpreted as a coordinate-wise version of heavy-tailed noise, which is natural in our setting since AdaGrad employs a coordinate-specific update rule. Moreover, Assumption 2.4 also generalizes the coordinate-wise finite-variance assumption considered in prior works (Bernstein et al., 2018; 2019; Jiang et al., 2025; Liu et al., 2025; Li et al., 2025). Remark 2.6. A seemingly similar condition to Assumption 2.4, but in fact fundamentally different, is Assumption 2 in Zhang et al. (2020b), where each coordinate of the stochastic gradient g t,i is assumed to have a finite p-th moment, rather than each coordinate of the noise ξ t,i .

To the best of our knowledge, Theorem 3.1 provides the first convergence rate for AdaGrad under heavy-tailed noise when the tail index p lies in the regime (4/3, 2]. Remarkably, this result holds under the standard assumptions without requiring any algorithmic modifications or prior knowledge of problem-dependent parameters. In contrast, the minimax p−1 rate Θ(1/T 3p−2 ) in the literature has been achieved only when problem-dependent parameters, particularly the value of p, are assumed to be known. The important feature of Theorem 3.1 is its adaptivity. First, it is adaptive to the tail index p. In other words, AdaGrad can automatically adapt to the largest admissible value of p without any tuning. In particular, in the boundary case 1 p = 2, Theorem 3.1 recovers the well-known Õ(1/T 4 ) 4

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

3.2. Algorithm-Dependent Lower Bound

rate of AdaGrad, matching existing results in the literature (Wang et al., 2023b; Jiang et al., 2025). Next, the convergence rate is also adaptive to the noise level ∥σ∥1 , as in the existing analysis of AdaGrad under p = 2. More precisely, 1 Theorem 3.1 recovers the best possible rate Õ(1/T 2 ) in the noiseless case when σ = 0 (or ∥σ∥1 is sufficiently small to be negligible). In summary, Theorem 3.1 is the first time demonstrating that AdaGrad is simultaneously adaptive to both the tail index p and the noise level ∥σ∥1 .

In this subsection, we provide the first algorithm-dependent lower bound for AdaGrad under heavy-tailed non-convex optimization. Theorem 3.3. Let d = 1, for any √ given ∆ > 0, L > 0, p ∈ (1, 2], σ ≥ 0, 0 < ϵ ≤ 2∆L, x1 ∈ R, γ > 0, there exists a function f : R → R associated with a stochastic gradient oracle g satisfying Assumptions 2.1 (and also f (x1 ) − inf x∈R f (x) ≤ ∆), 2.2 (with parameter L), 2.3, and 2.4 (with parameters p and σ). Moreover, if using AdaGrad (Algorithm 1), with initial point x1 , learning rate γ, and hyperparameter λ = 0, to optimize f by interacting with g, one must use at least 2 p   2 ∆ 2 2 2 γL ∆ 2 2 2 γL + γ L ln ( ) σ p−1 2 + γ L ln ( ) γ ϵ γ2 ϵ  + Ω 3p−2 ϵ2 ϵ p−1

Therefore, we would like to highlight that, as far as we know, this is the first concrete theoretical evidence supporting the advantage of adaptive gradient methods over SGD under heavy-tailed noise. Novel technique in the analysis. Now, we discuss the novel part of our proof. Following the literature on AdaGrad, our analysis also employs a proxy stepsize proposed by Ward et al. (2019) (also known as decorrelated stepsize (Faw et al., 2022)), i.e., a vector wt ∈ Rd≥0 that is predictable (in other words, wt ∈ Ft−1 ) to approximate v t . As far as we know, there are typically two choices for wt in the literature. One is to set wt ≜ v t−1 + (∇f (xt ))2 + σ 2 (Ward et al., 2019). The other is to set wt ≜ v t−1 (Wang et al., 2023b).

iterations to make E enough ϵ.

wt ≜ v t−1 + (∇f (xt ))2 + c2 ,

ci ≜

≤ O(ϵ) for small

To better understand Theorem 3.3, let us first consider p = 2, corresponding to the finite-variance setting. In this case, Theorem 3.3 degenerates to 2   2 ∆ 2 2 2 γL ∆ 2 2 2 γL σ2 2 + γ L ln ( ϵ ) + γ L ln ( ) 2 γ γ ϵ . + Ω ϵ2 ϵ4

−1

′ t=1 |f (xt )|

Theorem 3.3 provides the first algorithm-dependent lower bound for AdaGrad in the case d = 1, explicitly capturing the dependence on the input learning rate.

where c ∈ Rd≥0 is a free parameter that can be determined at the end of the proof. Though this extension seems simple, it is in fact critical to the analysis. If one simply picks c = σ as in many existing works (e.g., Jiang et al. (2025)), the best 2p−3 possible rate we can derive is in the order of Õ(1/T 2p ), 3p−4 which is always worse than the rate Õ(1/T 4p ) given in Theorem 3.1. Instead, in our proof, we pick 1

Remark 3.4. The requirement of λ = 0 is only for simplicity. See Theorem B.1 for the full version that allows λ ≥ 0. Remark 3.5. For simplicity, we restrict our attention to the case d = 1. Following the proof of Theorem 4 in Jiang et al. (2025), Theorem 3.3 can be extended to the highdimensional setting.

The technical contribution of our analysis is to further generalize the first kind of proxy stepsize. Concretely, we set

σ i T 2 − p̄

h P T 1

, ∀i ∈ [d] ,

2 p̄ DT,i

We claim that the above bound improves upon the existing one-dimensional lower bound ! ∆L 2 ∆L ln( ∆L ) ∆Lσ ln( ) 2 2 ϵ ϵ Ω + ϵ2 ϵ4

where 

σi T  DT,i ≜ 2 ln  1 + 

1 p

q P



√

 . 

T 2 t=1 (∇i f (xt ))

λ/ 2

established by Jiang et al. (2025) (see their Lemma 16). Indeed, note that ∆2 γL inf 2 + γ 2 L2 ln2 γ>0 γ ϵ ∆L 1 2η∆L ∆L 2∆L = inf + η ln2 ≥ ln , η>0 2 η ϵ2 2 ϵ2 p where we substitute γ = 2η∆/L in the first step and apply Lemma B.5 in the second step. Therefore, our lower

This choice turns out to be the key to obtaining the rate 3p−4 Õ(1/T 4p ) stated in Theorem 3.1. In particular, our choice of c degenerates to σ when p = 2, p since 12 − p̄1 = 0 due to p̄ = p−1 = 2, meaning that our wt naturally recovers the popular proxy stepsize wt = v t−1 + (∇f (xt ))2 + σ 2 in the classical finite-variance situation. Thus, our technique is indeed a novel generalization. For more details of this technique, see Appendix A. 5

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Algorithm 2 AdaGrad-Norm (Ward et al., 2019) Input: initial point x1 ∈ Rd , learning rate γ > 0, hyperparameter λ > 0 Initialization: v0 = 0 for t = 1 to T do 2 vt = vt−1 + ∥g t ∥2 γ√ xt+1 = xt − λ+ vt g t end for 4.1. A Faster Upper Bound

bound for AdaGrad is strictly more refined than the bestknown one in the literature.

Theorem 4.2. Under Assumptions 2.1, 2.2, 2.3, and 2.4, suppose f ⋆ ≜ supx∈Rd f (x) < +∞, let ∆⋆ ≜ f ⋆ − f⋆ , then for any γ > 0 and λ > 0, AdaGrad-Norm (Algorithm 2) guarantees q   " # T B ∥σ∥p 1X A , E ∥∇f (xt )∥2 ≤ O  √ + p−1 T t=1 T T 2p

For general p ∈ (1, 2], Theorem 3.3 is saying that, without any prior information on ∆ and L, AdaGrad isimpossip

ble to attain the minimax rate Ω

∆L ∆Lσ p−1 3p−2 ϵ2 + ϵ p−1

(Zhang

et al., 2020b; Liu & Zhou, 2025; Liu, 2026) for non-convex optimization under heavy-tailed noise. Moreover, even if ∆ and L are known, Theorem 3.3 indicates that an extra polylogarithmic factor is also unavoidable for AdaGrad. These two facts together reveal some fundamental limitations of AdaGrad.

where A ≜

λ∆⋆ ∆⋆ ∆⋆ γ + γ +γ ∥L∥∞ and B ≜ γ +γ ∥L∥∞ .

Remark h P 4.3. In fact, i we can prove a bound using T 2 E T1 t=1 ∥∇f (xt )∥2 as a stricter convergence metric (see (5) later). Remark 4.4. Without additionally assuming an upper boundedness on the objective function, we can still show that 3p−4 AdaGrad-Norm converges at a rate of Õ(1/T 4p ), in the same order as Theorem 3.1. The interested reader could refer to Theorem C.1 in Appendix C for details.

Since the proof is rather technical, we provide only a brief overview here and refer the interested reader to Appendix B for the analysis. Our proof builds upon the framework developed in Jiang et al. (2025) and Hübler et al. (2025). Concretely, we show that for a certain stochastic gradient oracle, one can construct a function parameterized by the learning rate γ such that, with constant probability, f ′ (xt ) ≥ Ω(ϵ) for any t ∈ [T ] if T is smaller than a threshold that also depends on γ. As a consequence, we derive an algorithmdependent lower bound that explicitly captures the dependence on the input learning rate.

The key result in this section is Theorem 4.2, stating a faster rate for AdaGrad-Norm under an extra assumption of bounded objectives, which has also been considered in the existing literature on adaptive gradient methods (e.g., Levy et al. (2021); Chezhegov et al. (2025)).

Finally, we suspect that our lower bound is not tight in ϵ. Improving it could be an interesting task that we hope will be addressed in the future.

Before moving on, we would like to discuss Theorem 4.2 p−1 further. First, it gives a faster rate O(1/T 2p ) without any extra polylogarithmic terms, which never becomes vacuous for any p ∈ (1, 2], significantly improving upon Theorem 3.1. Moreover, similar to Theorem 3.1, it still adapts to the tail index p and the noise level ∥σ∥p 3 , reflecting the power of adaptive gradient methods. More interestingly, this p−1 result perfectly matches the best-known rate O(1/T 2p ) achieved by NSGD(M) in the case where problem-dependent parameters are unknown in advance (Hübler et al., 2025; Liu & Zhou, 2025).

4. AdaGrad-Norm Can be Faster, Conditionally In this section, we consider a variant of AdaGrad, namely AdaGrad-Norm (Algorithm 2). Unlike AdaGrad, AdaGrad-Norm no longer maintains a coordinate-wise update rule. Instead, its stepsize is now a scalar and is constructed based on the accumulated squared norm of the stochastic gradients in history. Although AdaGrad-Norm is not widely implemented in practice, it is popular in theoretical studies due to its simplicity.

Finally, we would like to comment that, even under the assumption of bounded objective functions, it is unclear to p−1 us whether AdaGrad can achieve the rate O(1/T 2p ), since

Remark 4.1. Our analysis of AdaGrad-Norm still applies under the common norm-based heavy-tailed assumption, p i.e., Et−1 [∥ξ t ∥2 ] ≤ σ p for some σ ≥ 0. However, to avoid introducing more assumptions, we still consider the coordinate-wise Assumption 2.4 in the analysis of AdaGrad-Norm.

Note that the change from ∥σ∥1 in Theorem 3.1 to ∥σ∥p in Theorem 4.2 is reasonable and can be expected, since we are using the 2-norm as the convergence metric.

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

the proof strategy of Theorem 4.2 is specifically designed for AdaGrad-Norm (see Remark 4.5).

noise and achieves an optimal regret bound without knowing p. Inspired by Liu (2026), we are able to present the following analysis.

4.2. Theoretical Analysis We sum (1) from t = 1 to T to have

In this subsection, we aim to prove Theorem 4.2. Our proof is strongly inspired by the recent work of Liu (2026), which shows that AdaGrad-Norm guarantees an optimal regret bound in online convex optimization under heavy-tailed noise, even without knowing p. Although the problems studied are quite different, one will see that the underlying ideas and proof strategies are closely related (see Remark 4.6).

" T X t=1

≤E

" T # X f (xt ) − f (xt+1 ) γt

t=1

" T # X ∥L∥∞ 2 γt ∥g t ∥2 . + E 2 t=1 (2)

Proof of Theorem 4.2. In the following proof, let us denote the stepsize in AdaGrad-Norm by γt ≜ λ+γ√vt , ∀t ∈ N.

Observe that T X f (xt ) − f (xt+1 )

We start with Assumption 2.2 and use the update rule of AdaGrad-Norm to obtain

γt

t=1 2

∥xt+1 − xt ∥L 2 2 γt2 ∥g t ∥L = f (xt ) − γt ⟨∇f (xt ), g t ⟩ + 2 2 2 γ ∥L∥∞ ∥g t ∥2 . ≤ f (xt ) − γt ⟨∇f (xt ), g t ⟩ + t 2

f (xt+1 ) ≤ f (xt ) + ⟨∇f (xt ), xt+1 − xt ⟩ +

Divide both sides of the above inequality by γt and rearrange terms to have

f (xT +1 ) − f⋆ f (x1 ) − f⋆ − γ1 γT T −1 X 1 1 + − (f (xt+1 ) − f⋆ ) γ γ t+1 t t=1 T −1 1 f (x1 ) − f⋆ X 1 ≤ + − (f (xt+1 ) − f⋆ ) γ1 γt+1 γt t=1

(a) ∆

≤

⟨∇f (xt ), g t ⟩ ≤

# 2 ∥∇f (xt )∥2

f (xt ) − f (xt+1 ) γt ∥L∥∞ ∥g t ∥2 , + γt 2

⋆

γT

λ∆⋆ ∆⋆ √ + vT , γ γ

(3)

where (a) is due to 1 1 ≤ , γt γt+1

which implies the following inequality after taking expectations on both sides (due to Assumption 2.3), h i 2 E ∥∇f (xt )∥2 i h ∥L∥ E γ ∥g ∥2 t t 2 ∞ f (xt ) − f (xt+1 ) . (1) ≤E + γt 2

f ≤ f ⋆,

∆⋆ = f ⋆ − f ⋆ .

Moreover, we note that 2

γ ∥g ∥ γ ∥g t ∥2 √ ≤√ 2 t 2 λ + vt λ + vt p p λ2 + vt − λ2 + vt−1 ≤ 2γ

γt ∥g t ∥2 =

Remark 4.5. The above derivation cannot be applied to AdaGrad due to the coordinate-wise stepsize in it. ⇒

Remark 4.6. The reader familiar with the online convex optimization literature, and in particular with the regret analysis of AdaGrad-Norm, may notice that (1) is closely related to the standard inequality characterizing single-step progress, if recognizing f (xt ) − f⋆ as a notion of “distance”. Therefore, under the boundedness assumption on the objective hP i T 2 function, one may expect that E ∥∇f (x )∥ t 2 grows t=1 sublinearly in T .

T X

γt ∥g t ∥2 ≤ 2γ

p √ λ2 + vT − λ ≤ 2γ vT . (4)

t=1

PT 2 To ease the notation, we write uT = t=1 ∥∇f (xt )∥2 . Plug (3) and (4) back into (2) to obtain √ λ∆⋆ ∆⋆ E [uT ] ≤ + + γ ∥L∥∞ E [ vT ] γ γ (b) λ∆ √ 1 √ ∆⋆ ⋆ + 2 + γ ∥L∥∞ ∥σ∥p T p + E [ uT ] ≤ γ γ (c) λ∆ p √ 1 ∆⋆ ⋆ ≤ + 2 + γ ∥L∥∞ ∥σ∥p T p + E [uT ] , γ γ

However, the classical regret bound for AdaGrad-Norm is proved in the deterministic setting (or under finite-variance noise). Thanks to recent progress by Liu (2026), which has proved that AdaGrad-Norm is also robust to heavy-tailed 7

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

where the last step is by applying ∥·∥2 ≤ ∥·∥p twice when p ∈ [1, 2], i.e., v v ! p1 u t u t t uX uX X 2 2 p t ∥ξ s ∥2 ≤ t ∥ξ s ∥p ≤ ∥ξ s ∥p .

where (b) holds by Lemma 4.7 and (c) is due to Hölder’s inequality. Note that by AM-GM inequality p √ ∆⋆ 2 E [uT ] + γ ∥L∥∞ γ 2 ∆⋆ E [uT ] ≤ + γ ∥L∥∞ + . γ 2 PT 2 Next, we rearrange terms, plug in uT = t=1 ∥∇f (xt )∥2 , and divide both sides by T to obtain " # 2 T B ∥σ∥p 1X A 2 E , (5) ∥∇f (xt )∥2 ≤ O + p−1 T t=1 T T p q ∆⋆ ∆⋆ ⋆ where A = λ∆ γ + γ +γ ∥L∥∞ and B = γ +γ ∥L∥∞ are defined in the statement of Theorem 4.2.

s=1

" t d #! p1 XX √ √ √ p + E 2ut E [ vt ] ≤ 2 E ξ s,i ≤

√

2ut ,

Limitations. This study has two main limitations. First, the derived upper bound for AdaGrad becomes vacuous when p ∈ (1, 4/3]. Second, the algorithm-dependent lower bound does not significantly improve upon the minimax rate in terms of ϵ. Determining whether these upper and lower bounds are both loose, or whether one of them is in fact tight, is an important direction for future research.

s=1

Future Work. Several promising directions remain open for future investigation. For example, it is worthwhile to study whether more widely implemented adaptive gradient methods (e.g., Adam and AdamW) can converge under heavytailed noise and to characterize their limitations, thereby helping to demystify their strong performance in practice. Another direction is to analyze the convergence behavior of adaptive gradient methods under both heavy-tailed noise and other more realistic assumptions, such as the generalized smoothness condition proposed by Zhang et al. (2020a).

s=1

v u t u X √ 2 ≤ t2 ∥ξ s ∥2 + 2ut s=1

2 ∥σ∥p t p + E

Conclusion. This work makes the first attempt to understand whether AdaGrad, the origin of adaptive gradient methods, can converge in non-convex optimization under heavy-tailed noise. We partially address this question by establishing the first convergence rate for AdaGrad when the tail index p lies in the range (4/3, 2]. Importantly, the obtained rate adapts to the tail index and the noise level simultaneously. Moreover, we derive an algorithm-dependent lower bound for AdaGrad in the same setting when d = 1, suggesting that the existing minimax rate for heavy-tailed non-convex optimization is not attainable by AdaGrad. In addition, we show that AdaGrad-Norm, a popular variant of AdaGrad in theoretical studies, can achieve a faster rate for all p ∈ (1, 2] when the objective function is bounded. We believe these results shed new light on the empirical success of adaptive gradient methods.

v u t t u X X 2 2 ≤ t2 ∥ξ s ∥2 + 2 ∥∇f (xs )∥2

≤

s=1 i=1

5. Conclusion, Limitations, and Future Work

Proof. By the definition of vt , we have v v u t u t uX uX √ 2 2 t vt = ∥g s ∥2 = t ∥ξ s + ∇f (xs )∥2

t X d X

√

p where the last step is due to E ξ s,i ≤ σ pi , ∀s ∈ [t] , i ∈ [d] by Assumption 2.4.

The above proof relies on the following lemma, which shows √ 1 that the term E vt can be upper bounded by ∥σ∥p t p and √ E ut for any p ∈ [1, 2]. Essentially the same observation was also made in Liu (2026). Lemma 4.7. Under Assumption 2.4, for any t ∈ N, AdaGrad-Norm (Algorithm 2) guarantees √ √ 1 √ E [ vt ] ≤ 2 ∥σ∥p t p + E 2ut , Pt 2 where ut ≜ s=1 ∥∇f (xs )∥2 , ∀t ∈N.

√

s=1

Finally, by Hölder’s inequality, we conclude that

Finally, we can apply the following inequality to recover Theorem 4.2,  v # " u T T u1 X X 1 2 ∥∇f (xt )∥2 ≤ E t ∥∇f (xt )∥2  E T t=1 T t=1 q v "   # u T B ∥σ∥p u X (5) A 1 2 , ≤tE ∥∇f (xt )∥2 ≤ O  √ + p−1 T t=1 T T 2p √ where the first step holds by the concavity of x and the second step is due to Hölder’s inequality.

s=1

! p1 ξ s,i

√

2ut ,

s=1 i=1

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Acknowledgements

tion efficient and fault tolerant. In International Conference on Learning Representations, 2019. URL https: //openreview.net/forum?id=BJxhijAcY7.

The author thanks the anonymous reviewers for their valuable feedback.

Bottou, L., Curtis, F. E., and Nocedal, J. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018. doi: 10.1137/16M1080173. URL https://doi.org/10.1137/16M1080173.

Impact Statement This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

Chezhegov, S., Yaroslav, K., Semenov, A., Beznosikov, A., Gasnikov, A., Horváth, S., Takáč, M., and Gorbunov, E. Clipping improves Adam-norm and AdaGradnorm when the noise is heavy-tailed. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., Berkenkamp, F., Maharaj, T., Wagstaff, K., and Zhu, J. (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 10269–10333. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/ v267/chezhegov25a.html.

References Ahn, K., Cheng, X., Song, M., Yun, C., Jadbabaie, A., and Sra, S. Linear attention is (maybe) all you need (to understand transformer optimization). In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum? id=0uI5415ry7.

Crawshaw, M. and Liu, M. Complexity lower bounds of adaptive gradient algorithms for non-convex stochastic optimization under relaxed smoothness. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum? id=ZjOXuAfS6l.

Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1-2):165–214, 2023. Attia, A. and Koren, T. SGD with AdaGrad stepsizes: Full adaptivity with high probability to unknown parameters, unbounded gradients and affine variance. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 1147–1171. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/ v202/attia23a.html.

Cutkosky, A. and Mehta, H. Momentum improves normalized SGD. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2260–2268. PMLR, 13–18 Jul 2020. URL https://proceedings.mlr.press/ v119/cutkosky20b.html. Cutkosky, A. and Mehta, H. High-probability bounds for non-convex stochastic optimization with heavy tails. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4883–4895. Curran Associates, Inc., 2021. URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ 26901debb30ea03f0aa833c9de6b81e9Paper.pdf.

Battash, B., Wolf, L., and Lindenbaum, O. Revisiting the noise model of stochastic gradient descent. In Dasgupta, S., Mandt, S., and Li, Y. (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4780–4788. PMLR, 02–04 May 2024. URL https://proceedings.mlr.press/ v238/battash24a.html. Bernstein, J., Wang, Y.-X., Azizzadenesheli, K., and Anandkumar, A. signSGD: Compressed optimisation for nonconvex problems. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 560–569. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/ bernstein18a.html.

De, S., Mukherjee, A., and Ullah, E. Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison to nesterov acceleration. arXiv preprint arXiv:1807.06766, 2018. Défossez, A., Bottou, L., Bach, F., and Usunier, N. A simple convergence proof of adam and adagrad. Transactions on Machine Learning Research, 2022. ISSN 28358856. URL https://openreview.net/forum? id=ZPQhzTSWA7.

Bernstein, J., Zhao, J., Azizzadenesheli, K., and Anandkumar, A. signSGD with majority vote is communica9

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12 (61):2121–2159, 2011. URL http://jmlr.org/ papers/v12/duchi11a.html.

Jiang, R., Maladkar, D., and Mokhtari, A. Provable complexity improvement of adagrad over sgd: Upper and lower bounds in stochastic non-convex optimization. In Haghtalab, N. and Moitra, A. (eds.), Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 3124–3158. PMLR, 30 Jun–04 Jul 2025. URL https://proceedings.mlr.press/ v291/jiang25c.html.

Faw, M., Tziotis, I., Caramanis, C., Mokhtari, A., Shakkottai, S., and Ward, R. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 313–355. PMLR, 02–05 Jul 2022. URL https://proceedings.mlr.press/ v178/faw22a.html.

Kavis, A., Levy, K. Y., and Cevher, V. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. In International Conference on Learning Representations, 2022. URL https://openreview. net/forum?id=dSw0QtRMJkO. Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.

Faw, M., Rout, L., Caramanis, C., and Shakkottai, S. Beyond uniform smoothness: A stopped analysis of adaptive sgd. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 89–160. PMLR, 12–15 Jul 2023. URL https://proceedings.mlr.press/ v195/faw23a.html.

Lan, G. First-order and stochastic optimization methods for machine learning. Springer, 2020.

Garg, S., Zhanson, J., Parisotto, E., Prasad, A., Kolter, Z., Lipton, Z., Balakrishnan, S., Salakhutdinov, R., and Ravikumar, P. On proximal policy optimization’s heavytailed gradients. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3610–3619. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/ v139/garg21b.html. Hong, Y. and Lin, J. On convergence of adam for stochastic optimization under relaxed assumptions. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 10827–10877. Curran Associates, Inc., 2024. doi: 10.52202/079017-0346. URL https://proceedings.neurips. cc/paper_files/paper/2024/file/ 14bb27f680bee45d83bc769738e7f9b5Paper-Conference.pdf.

Levy, K., Kavis, A., and Cevher, V. Storm+: Fully adaptive sgd with recursive momentum for nonconvex optimization. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 20571–20582. Curran Associates, Inc., 2021. URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ ac10ff1941c540cd87c107330996f4f6Paper.pdf. √ Li, H., Dong, Y., and Lin, Z. On the o( d/t1/4 ) convergence rate of rmsprop and its momentum extension measured by ℓ1 norm. Journal of Machine Learning Research, 26(131):1–25, 2025. URL http://jmlr. org/papers/v26/24-0523.html. Li, X. and Orabona, F. On the convergence of stochastic gradient descent with adaptive stepsizes. In Chaudhuri, K. and Sugiyama, M. (eds.), Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 983–992. PMLR, 16– 18 Apr 2019. URL https://proceedings.mlr. press/v89/li19c.html. Liu, Y., Pan, R., and Zhang, T. Adagrad under anisotropic smoothness. In The Thirteenth International Conference on Learning Representations, 2025. URL https:// openreview.net/forum?id=4GT9uTsAJE.

Hübler, F., Fatkhullin, I., and He, N. From gradient clipping to normalization for heavy tailed sgd. In Li, Y., Mandt, S., Agrawal, S., and Khan, E. (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 2413–2421. PMLR, 03–05 May 2025. URL https://proceedings.mlr.press/ v258/hubler25a.html.

Liu, Z. Online convex optimization with heavy tails: Old algorithms, new regrets, and applications. In Telgarsky, M. and Ullman, J. (eds.), Proceedings of The 37th International Conference on Algorithmic 10

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Learning Theory, volume 313 of Proceedings of Machine Learning Research, pp. 1–47. PMLR, 23–26 Feb 2026. URL https://proceedings.mlr.press/ v313/liu26a.html.

in Neural Information Processing Systems, volume 36, pp. 24191–24222. Curran Associates, Inc., 2023. URL https://proceedings.neurips. cc/paper_files/paper/2023/file/ 4c454d34f3a4c8d6b4ca85a918e5d7baPaper-Conference.pdf.

Liu, Z. and Zhou, Z. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. In The Thirteenth International Conference on Learning Representations, 2025. URL https: //openreview.net/forum?id=NKotdPUc3L.

Reddi, S. J., Kale, S., and Kumar, S. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. URL https: //openreview.net/forum?id=ryQu7f-RZ.

Liu, Z., Nguyen, T. D., Ene, A., and Nguyen, H. On the convergence of adagrad(norm) on Rd : Beyond convexity, non-asymptotic rate and acceleration. In The Eleventh International Conference on Learning Representations, 2023a. URL https://openreview.net/forum? id=ULnHxczCBaE. Liu, Z., Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. High probability convergence of stochastic gradient methods. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 21884–21914. PMLR, 23– 29 Jul 2023b. URL https://proceedings.mlr. press/v202/liu23aa.html. Liu, Z., Zhang, J., and Zhou, Z. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 2266–2290. PMLR, 12– 15 Jul 2023c. URL https://proceedings.mlr. press/v195/liu23c.html. Loshchilov, I. and Hutter, F. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL https://openreview. net/forum?id=Bkg6RiCqY7. McMahan, H. B. and Streeter, M. J. Adaptive bound optimization for online convex optimization. In Conference on Learning Theory (COLT), pp. 244–256. Omnipress, 2010.

Sadiev, A., Danilova, M., Gorbunov, E., Horváth, S., Gidel, G., Dvurechensky, P., Gasnikov, A., and Richtárik, P. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 29563–29648. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/ v202/sadiev23a.html. Shazeer, N. and Stern, M. Adafactor: Adaptive learning rates with sublinear memory cost. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4596–4604. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr. press/v80/shazeer18a.html. Shi, N., Li, D., Hong, M., and Sun, R. RMSprop converges with proper hyper-parameter. In International Conference on Learning Representations, 2021. URL https:// openreview.net/forum?id=3UDSdyIcBDA. Simsekli, U., Sagun, L., and Gurbuzbalaban, M. A tailindex analysis of stochastic gradient noise in deep neural networks. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5827–5837. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/ v97/simsekli19a.html. Sun, T., Liu, X., and Yuan, K. Revisiting gradient normalization and clipping for nonconvex sgd under heavytailed noise: Necessity, sufficiency, and acceleration. Journal of Machine Learning Research, 26(237):1–42, 2025. URL http://jmlr.org/papers/v26/241991.html.

Nesterov, Y. E. Minimization methods for nonsmooth convex and quasiconvex functions. Matekon, 29(3):519–531, 1984. Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances

Tieleman, T., Hinton, G., et al. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4 (2):26–31, 2012. 11

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. Attention is all you need. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://proceedings.neurips. cc/paper_files/paper/2017/file/ 3f5ee243547dee91fbd053c1c4a845aaPaper.pdf. Wang, B., Fu, J., Zhang, H., Zheng, N., and Chen, W. Closing the gap between the upper bound and lower bound of adam's iteration complexity. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 39006–39032. Curran Associates, Inc., 2023a. URL https://proceedings.neurips. cc/paper_files/paper/2023/file/ 7ac19fdcdf4f311f3e3ef2e7ef4784d7Paper-Conference.pdf. Wang, B., Zhang, H., Ma, Z., and Chen, W. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 161–190. PMLR, 12– 15 Jul 2023b. URL https://proceedings.mlr. press/v195/wang23a.html. Wang, B., Zhang, Y., Zhang, H., Meng, Q., Sun, R., Ma, Z.-M., Liu, T.-Y., Luo, Z.-Q., and Chen, W. Provable adaptivity of adam under non-uniform smoothness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, pp. 2960–2969, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400704901. doi: 10. 1145/3637528.3671718. URL https://doi.org/ 10.1145/3637528.3671718.

volume 36, pp. 74257–74288. Curran Associates, Inc., 2023. URL https://proceedings.neurips. cc/paper_files/paper/2023/file/ eb1a323fa10d4102ff13422476a744ffPaper-Conference.pdf. Zaheer, M., Reddi, S., Sachan, D., Kale, S., and Kumar, S. Adaptive methods for nonconvex optimization. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips. cc/paper_files/paper/2018/file/ 90365351ccc7437a1309dc64e4db32a3Paper.pdf. Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020a. URL https: //openreview.net/forum?id=BJgnXpVYwS. Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. Why are adaptive methods good for attention models? In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15383–15393. Curran Associates, Inc., 2020b. URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ b05b57f6add810d3b7490866d74c0053Paper.pdf. Zhang, Q., Zhou, Y., and Zou, S. Convergence guarantees for RMSProp and adam in generalized-smooth nonconvex optimization with affine noise variance. Transactions on Machine Learning Research, 2025. ISSN 28358856. URL https://openreview.net/forum? id=QIzRdjIWnS.

Ward, R., Wu, X., and Bottou, L. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6677–6686. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/ ward19a.html.

Zhang, Y., Chen, C., Shi, N., Sun, R., and Luo, Z.-Q. Adam can converge without any modification on update rules. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 28386–28399. Curran Associates, Inc., 2022. URL https://proceedings.neurips. cc/paper_files/paper/2022/file/ b6260ae5566442da053e5ab5d691067aPaper-Conference.pdf.

YANG, J., Li, X., Fatkhullin, I., and He, N. Two sides of one coin: the limits of untuned sgd and the power of adaptive methods. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems,

Zou, F., Shen, L., Jie, Z., Zhang, W., and Liu, W. A sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019. 12

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

A. Upper Bound for AdaGrad This section provides the full statement of Theorem 3.1 and its proof. A.1. Full Theorem and Its Proof Theorem A.1 (Full statement of Theorem 3.1). Under Assumptions 2.1, 2.2, 2.3, and 2.4, let ∆ ≜ f (x1 ) − f⋆ , then for any γ > 0 and λ > 0, AdaGrad (Algorithm 1) guarantees " # 1 1 T dλ + ∆ ∥σ∥1 ln p̄ + 2 KT 1X γ + γ ∥L∥1 ln KT √ ∥∇f (xt )∥1 ≤O + E p−1 T t=1 T T p r  ∆ 1 1 + γ ∥L∥ ln K ∥σ∥ T 1 1 γ ∥σ∥1 ln 2p̄ + 4 KT  , + + p−1 3p−4  T 2p T 4p √

where KT = 1 +

2∥σ∥∞ T p +2∥∇f (x1 )∥∞ T 2 +2γ λ

√

∥L∥1 ∥L∥∞ T 2

is introduced in Lemma A.5.

Proof. In the following proof, let 1

σ i T 2 − p̄

ci ≜

−1

, ∀i ∈ [d] ,

(6)

2 p̄ DT,i

where

√ DT,i ≜ 2 ln 1 +

By Lemma A.5, we have

2σ i T p + E λ

2uT,i

! , ∀i ∈ [d] .

h v T,i i E ln 1 + 2 ≤ DT,i ≤ 2 ln KT . λ

(7)

(8)

We sum up the inequality in Lemma A.2 (with c defined in (6)) from t = 1 to T and use f (x1 )−f (xT +1 ) ≤ ∆ (Assumption 2.1) to have " T X (∇f (xt ))2 γ E √ 2 λ + wt t=1

g 2t,i E 2 λ + v t,i

#! p̄2

" # T g 2t,i γLi X ≤∆+γ E 2 +γ ci + c 2 λ + v t,i t=1 i=1 i t=1 i=1 d d h X X (a) γLi σ 2i 1− p̄2 h v T,i i v T,i i p̄2 ci + ≤ ∆+γ +γ E ln 1 + 2 T E ln 1 + 2 c λ 2 λ i=1 i i=1 d 2 X (8) σ i 1− p̄2 p̄2 T DT,i + ci DT,i + γ 2 ∥L∥1 ln KT ≤ ∆+γ ci i=1 d T X σ2 X

(6)

= ∆ + 2γ

d X

p̄ 2 σ i T 2 − p̄ DT,i + γ 2 ∥L∥1 ln KT

i=1 (8)

≤ ∆+2

1 3 p̄ + 2

γ ∥σ∥1 T 2 − p̄ ln p̄ + 2 KT + γ 2 ∥L∥1 ln KT

(b)

= ∆ + 4γ ∥σ∥1 T p − 2 ln p̄ + 2 KT + γ 2 ∥L∥1 ln KT ,

where (a) is by applying Lemma A.3 with q = p̄2 and q = 1 and (b) is due to p̄1 ≤ 12 and 12 − p̄1 = p1 − 12 . Divide both sides of the above inequality by γ2 to obtain " T X (∇f (xt ))2 E √ λ + wt t=1

# ≤ 1

1 1 1 1 2∆ + 2γ ∥L∥1 ln KT + 8 ∥σ∥1 T p − 2 ln p̄ + 2 KT . γ

(9)

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Next, recall that ut,i =

√

2 s=1 (∇i f (xs )) , ∀t ∈ N (introduced in Lemma A.4), we hence have

uT,i

p × λ + v T,i + uT,i + c2i λ + v T,i + uT,i + c2i v " # u q (c) u uT,i 2 t p ≤ E v + u + c E λ + T,i T,i i λ + v T,i + uT,i + c2i v " # u T q u X (∇i f (xt ))2 t ≤ E E λ + v T,i + uT,i + c2i √ λ + wt,i t=1 v " # u T X (d) u √ √ √ 1 (∇i f (xt ))2 t λ + ci + 2σ i T p + 3E uT,i ≤ E √ λ + wt,i t=1 v  u " # T u X √ √ 1 1 1 σi (∇i f (xt ))2  (6) u √ λ + 1 − 1 T 2 − p̄ + 2σ i T p + 3E uT,i , = tE √ λ + w 2 p̄ t,i DT,i t=1

uT,i = E

(10)

where (c) is by Hölder’s inequality and (d) follows similar steps to proving Lemma A.4. Now, we consider two cases: Case 1.

DT,i ≥ 1: in this case, we have σi

1 1 2 − p̄

T 2 − p̄ ≤ σ i T 2 − p̄ = σ i T p − 2 ≤ σ i T p ,

DT,i which implies that

Case 2.

√

v " # u T X √ √ √ (10) u 1 (∇i f (xt ))2 t uT,i ≤ E λ + 1 + 2 σ i T p + 3E uT,i . √ λ + wt,i t=1

DT,i < 1: in this case, we have √ (7)

1 > DT,i = 2 ln 1 +

2σ i T p + E λ

2uT,i

! ,

which implies that E

√

uT,i ≤ σ i T

1 p

√

uT,i ≤

e−1 √ λ. 2

Therefore, we always have

√

uT,i

v " # u √ T u X √ √ √ 1 (∇i f (xt ))2 e−1 t p ≤ E λ + 1 + 2 σ i T + 3E uT,i + √ λ. √ λ + wt,i 2 t=1 14

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Sum up the above inequality for all i ∈ [d] to have v " # " d # √ T d u u X X√ X √ √ √ 1 (∇i f (xt ))2 e−1 t p λ + 1 + 2 σ i T + 3E uT,i + √ dλ E uT,i ≤ E √ λ + wt,i 2 t=1 i=1 i=1 v " d #! #! √ " T u d X√ X (∇i f (xt ))2 (e) u X √ √ 1 e−1 t p dλ + 1 + 2 ∥σ∥1 T + 3E uT,i + √ dλ ≤ E √ λ + wt,i 2 t=1 i=1 i=1 v " # " d #! √ u T u X X√ √ √ 1 e−1 (∇f (xt ))2 t p dλ + 1 + 2 ∥σ∥1 T + 3E = E uT,i + √ dλ √ λ + wt 1 2 t=1 i=1 v   # u " T # " d # " T u X (∇f (xt ))2 X√ X (∇f (xt ))2 1 t  + E ∥σ∥1 T p  , (11) ⇒E uT,i ≤ O dλ + E √ √ λ + wt 1 λ + wt 1 t=1 t=1 i=1 where (e) is due to Cauchy-Schwarz inequality. Now, we combine (9) and (11) to obtain " d # X√ 1 1 1 1 ∆ E uT,i ≤O dλ + + γ ∥L∥1 ln KT + ∥σ∥1 T p − 2 ln p̄ + 2 KT γ i=1 s ! 1 1 1 ∆ + 12 − 12 p̄ p p + γ ∥L∥1 ln KT + ∥σ∥1 T ln . + KT ∥σ∥1 T γ Lastly, we observe that d X √ i=1

v Pd PT PT T d u uX X ∥∇f (xt )∥1 i=1 t=1 |∇i f (xt )| t 2 √ (∇i f (xt )) ≥ = t=1 √ , uT,i = T T t=1 i=1

which gives us # T 1X ∥∇f (xt )∥1 ≤O E T t=1 "

dλ + ∆ ∥σ∥1 ln p̄ + 2 KT γ + γ ∥L∥1 ln KT √ + p−1 T T p r  ∆ 1 1 γ + γ ∥L∥1 ln KT ∥σ∥1 ∥σ∥1 ln 2p̄ + 4 KT  . + + p−1 3p−4  T 2p T 4p

A.2. Helpful Lemmas To prove Theorem A.1, we require the following four lemmas. Before presenting them, we recall a key ingredient in our analysis, the generalized proxy stepsize, defined as follows wt ≜ v t−1 + (∇f (xt ))2 + c2 ∈ Ft−1 , where c ∈ Rd≥0 is a free parameter that will be specified in the final proof. As discussed in Section 3, it plays a crucial role in establishing the final convergence rate. We are now ready to give the first result, Lemma A.2, which characterizes the per-iteration progress of AdaGrad. Lemma A.2. Under Assumptions 2.2, 2.3, and 2.4, for any c ∈ Rd≥0 and t ∈ N, AdaGrad (Algorithm 1) guarantees γ E 2

(∇f (xt ))2 √ λ + wt

≤ E [f (xt ) − f (xt+1 )] + γ 1

d X σ2 i

i=1

ci 15

g 2t,i E 2 λ + v t,i

#! p̄2 +γ

d X i=1

γLi ci + 2

" E

# g 2t,i . λ2 + v t,i

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Proof. We start with Assumption 2.2 and use the update rule of AdaGrad to obtain 2

∥xt+1 − xt ∥L f (xt+1 ) ≤ f (xt ) + ⟨∇f (xt ), xt+1 − xt ⟩ + 2 2 gt gt γ2 = f (xt ) − γ ∇f (xt ), + √ √ λ + vt 2 λ + vt L gt Lg 2t γ2 ≤ f (xt ) − γ ∇f (xt ), + √ λ + vt 2 λ2 + v t 1 gt gt gt γ2 = f (xt ) − γ ∇f (xt ), + γ ∇f (xt ), − + √ √ √ λ + wt λ + wt λ + vt 2

Lg 2t 2 λ +v

. t

Take conditional expectations on both sides of the above inequality to obtain Et−1 [f (xt+1 )] (∇f (xt ))2 ≤f (xt ) − γ √ λ + wt =f (xt ) − γ

(∇f (xt ))2 √ λ + wt

Lg 2t λ2 + v t 1 1 " # d d X Li g 2t,i ∇i f (xt )g t,i ∇i f (xt )g t,i γ2 X +γ Et−1 − + Et−1 , √ √ λ + wt,i λ + v t,i 2 i=1 λ2 + v t,i 1 i=1 + γEt−1 ∇f (xt ),

gt gt − √ √ λ + wt λ + vt

γ2 + Et−1 2

(12)

where the first step is by Et−1 [g t ] Assumption 2.3 ∇f (xt ) (∇f (xt ))2 gt xt ,wt ∈Ft−1 Et−1 ∇f (xt ), = ∇f (xt ), = ∇f (xt ), = √ √ √ √ λ + wt λ + wt λ + wt λ + wt

. 1

For any fixed coordinate i ∈ [d], we can bound # " g 2t,i − (∇i f (xt ))2 − c2i ∇i f (xt )g t,i ∇i f (xt )g t,i ∇i f (xt )g t,i Et−1 − = Et−1 √ √ √ √ √ √ λ + wt,i λ + v t,i (λ + wt,i )(λ + v t,i )( wt,i + v t,i ) # " (g t,i + ∇i f (xt ))ξ t,i ∇i f (xt )g t,i −c2i ∇i f (xt )g t,i =Et−1 + Et−1 √ √ √ √ √ √ √ √ (λ + wt,i )(λ + v t,i )( wt,i + v t,i ) (λ + wt,i )(λ + v t,i )( wt,i + v t,i ) " # " # g t,i + |∇i f (xt )| ξ t,i |∇i f (xt )| g t,i c2i |∇i f (xt )| g t,i ≤Et−1 + Et−1 √ √ √ √ √ √ √ √ (λ + wt,i )(λ + v t,i )( wt,i + v t,i ) (λ + wt,i )(λ + v t,i )( wt,i + v t,i ) # " # " (a) ci |∇i f (xt )| g t,i ξ t,i |∇i f (xt )| g t,i + Et−1 ≤ Et−1 √ √ √ √ (λ + wt,i )(λ + v t,i ) (λ + wt,i )(λ + v t,i ) " # " #! (b) |∇ f (x )| ξ t,i g t,i ci g t,i i t ≤ Et−1 + Et−1 √ √ √ λ + wt,i λ + v t,i λ + v t,i  " #!2 " #!2  (c) (∇ f (x ))2 ξ g c g 1 i i t t,i t,i t,i  Et−1 , + + Et−1 (13) ≤ √ √ √ √ 2(λ + wt,i ) λ + wt,i λ + v t,i λ + v t,i √

√

i f (xt )| √ v t,i , (b) is from |∇ ∈ Ft−1 , and λ+ wt,i ci |g t,i | |ξt,i√ ||gt,i | (∇i f (xt ))2 2 √ (c) holds by AM-GM inequality, i.e., |∇i f (xt )| X ≤ + X for X = Et−1 λ+ vt,i and Et−1 λ+ vt,i , 4

where (a) is due to g t,i + |∇i f (xt )| ≤

wt,i +

v t,i and ci ≤

wt,i +

respectively. Next, we apply Hölder’s inequality to get " #!2 " #! p̄2 p̄ 2 ξ t,i g t,i g t,i p p Et−1 ≤ Et−1 ξ t,i Et−1 √ √ λ + v t,i (λ + v t,i )p̄   " #! p̄2 ! p̄2  p̄2 p̄ 2 Assumption 2.4 g g t,i t,i  , ≤ σ 2i Et−1 ≤ σ 2i Et−1  2 √ (λ + v t,i )p̄ λ + v t,i 16

(14)

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

and " Et−1

ci g t,i √ λ + v t,i

#!2

" ≤ Et−1

c2i g 2t,i √ (λ + v t,i )2

" ≤ Et−1

# c2i g 2t,i . λ2 + v t,i

(15)

Plug (14) and (15) into (13) to obtain ∇i f (xt )g t,i ∇i f (xt )g t,i Et−1 − √ √ λ + wt,i λ + v t,i   ! p̄2  p̄2 # " 2 2 2 2 g g 2t,i (∇i f (xt )) σi c t,i i Et−1   + ≤ + Et−1 √ √ √ 2(λ + wt,i ) λ + wt,i λ2 + v t,i λ + wt,i λ2 + v t,i "

(∇i f (xt ))2 σ2 ≤ + i √ 2(λ + wt,i ) ci where the last step is by λ +

√

Et−1

g 2t,i λ2 + v t,i

#! p̄2

" + ci Et−1

# g 2t,i , λ2 + v t,i

(16)

t,i ≤ 1, and p̄2 ≥ 1. wt,i ≥ ci , λ2 +v t,i

We combine (12) and (16) to have " #! p̄2 d X g 2t,i σ 2i γ (∇f (xt ))2 +γ Et−1 Et−1 [f (xt+1 )] ≤f (xt ) − √ 2 λ + wt 1 c λ2 + v t,i i=1 i " # d X g 2t,i γLi Et−1 +γ ci + . 2 λ2 + v t,i i=1 Taking expectations on both sides and rearranging terms, we know γ E 2

(∇f (xt )) √ λ + wt



i E  Et−1 c i i=1 # " d X g 2t,i γLi E 2 +γ ci + . 2 λ + v t,i i=1

≤E [f (xt ) − f (xt+1 )] + γ 1

d X σ2

g 2t,i λ2 + v t,i

#! p̄2  

Finally, noticing that p̄2 ≥ 1, we hence can invoke Hölder’s inequality again to have, for any i ∈ [d],  E  Et−1

g 2t,i 2 λ + v t,i

#! p̄2  ≤

E Et−1

g 2t,i 2 λ + v t,i

##! p̄2

g 2t,i E 2 λ + v t,i

#! p̄2 ,

which leads us to the desired result. Lemma A.3 can be viewed as a generalization of the existing inequality in the literature (see, e.g., Ward et al. (2019)) from q = 1 to any q ∈ [0, 1]. Lemma A.3. For any T ∈ N, i ∈ [d], and q ∈ [0, 1], AdaGrad (Algorithm 1) guarantees " #!q T h X g 2t,i v T,i iq E 2 ≤ T 1−q E ln 1 + 2 . λ + v t,i λ t=1 Proof. By the concavity of xq (since q ∈ [0, 1]), we have " #!q T g 2t,i 1X E 2 ≤ T t=1 λ + v t,i 17

" #!q T g 2t,i 1X E 2 , T t=1 λ + v t,i

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

which implies that "

T X

g 2t,i E 2 λ + v t,i

t=1

#!q " T #!q X g 2t,i λ2 + v t−1,i 1−q =T E E 1− 2 λ2 + v t,i λ + v t,i t=1 t=1 " T #!q h X v T,i iq λ2 + v t,i 1−q E ln 1 + E ln = T , λ2 + v t−1,i λ2 t=1

#!q ≤T

" T X

1−q

(a)

≤ T 1−q

where (a) is due to 1 − x−1 ≤ ln x, ∀x > 0. The next Lemma A.4 is the coordinate-wise version of Lemma 4.7. Lemma A.4. Under Assumption 2.4, for any t ∈ N and i ∈ [d], AdaGrad (Algorithm 1) guarantees E where ut,i ≜

√

p √ 1 v t,i ≤ 2σ i t p + E 2ut,i ,

2 s=1 (∇i f (xs )) , ∀t ∈ N.

Proof. By the definition of v t,i , we have v v v u t u t u t t u u u X X X X √ t t 2 (∇i f (xs ))2 v t,i = g s,i = (ξ s,i + ∇i f (xs ))2 ≤ t2 ξ 2s,i + 2 s=1

s=1

v ! p1 u t t u X √ X p p p 2 ≤ t2 ξ s,i + 2ut,i ≤ 2 + 2ut,i , ξ s,i s=1

s=1

where the last step is due to ∥·∥2 ≤ ∥·∥p when p ∈ [1, 2]. By Hölder’s inequality, we conclude

√

v t,i ≤

√

2 E

" t X

#! p1 ξ s,i

2ut,i

Assumption 2.4 √ p 1 ≤ 2σ i t p + E 2ut,i .

s=1

Finally, we prove Lemma A.5, which is also inspired by Ward et al. (2019). Lemma A.5. Under Assumptions 2.2 and 2.4, for any i ∈ [d], AdaGrad (Algorithm 1) guarantees √ p ! 1 h 2σ i T p + E 2uT,i v T,i i ≤ 2 ln 1 + ≤ 2 ln KT , E ln 1 + 2 λ λ √

where KT ≜ 1 +

2∥σ∥∞ T p +2∥∇f (x1 )∥∞ T 2 +2γ λ

√

∥L∥1 ∥L∥∞ T 2

Proof. Note that √ ! r √ v T,i E v T,i v T,i i v T,i E ln 1 + 2 = 2E ln 1+ 2 ≤ 2E ln 1 + ≤ 2 ln 1 + , λ λ λ λ h

where the last step is due to the concavity of ln x. Next, we invoke Lemma A.4 to obtain √ p 1 h 2σ i T p + E 2uT,i v T,i i E ln 1 + 2 ≤ 2 ln 1 + λ λ 18

! .

(17)

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Moreover, under Assumption 2.2, we have almost surely, for any t ∈ [T ],

|∇i f (xt ) − ∇i f (x1 )| ≤

t−1 p p p X Li ∥∇f (xt ) − ∇f (x1 )∥1/L ≤ Li ∥xt − x1 ∥L ≤ Li ∥xs+1 − xs ∥L s=1

t−1 X

t−1 u d X uX

p Lj g 2s,j γ t = γ Li √ gs √ λ + vs (λ + v s,j )2 L s=1 s=1 j=1 v t−1 u d q p X uX t ≤ γ Li Lj = γ Li ∥L∥1 (t − 1)

p Li

s=1

j=1

⇒ |∇i f (xt )| ≤ |∇i f (x1 )| + γ

Li ∥L∥1 (t − 1).

Hence, there is almost surely v v u T u T 2 q u u X X p t t 2 (∇i f (xt )) ≤ 2 |∇i f (x1 )| + γ Li ∥L∥1 (t − 1) 2uT,i = 2 t=1

t=1

v u T T uX X 2 |∇i f (x1 )| + γ 2 Li ∥L∥1 (t − 1)2 ≤ 2t t=1

t=1 1 2

≤ 2 |∇i f (x1 )| T + 2γ

Li ∥L∥1 T 2 .

(18)

Finally, we plug (18) back into (17) to have √ 2 ln 1 + √ ≤2 ln 1 + √ ≤2 ln 1 +

2σ i T p + E λ

p ! 2uT,i

2σ i T p + 2 |∇i f (x1 )| T 2 + 2γ λ 1

Li ∥L∥1 T 2

2 ∥σ∥∞ T p + 2 ∥∇f (x1 )∥∞ T 2 + 2γ λ

∥L∥1 ∥L∥∞ T 2

! = 2 ln KT .

B. Algorithm-Dependent Lower Bound for AdaGrad This section provides the full statement of Theorem 3.3 and its proof. B.1. Full Theorem and Its Proof √ Theorem B.1 (Full statement of Theorem 3.3). Let d = 1, for any given ∆ > 0, L > 0, p ∈ (1, 2], σ ≥ 0, 0 < ϵ ≤ 2∆L, x1 ∈ R, γ > 0, λ ≥ 0 satisfying λ = 0 when σ = 0, there exists a function f : R → R associated with a function g : R × {0, 1} → R and a Bernoulli distribution P on {0, 1} satisfying 1. f (x1 ) − inf x∈R f (x) ≤ ∆ and f is L-smooth; p 2. Er∼P [g(x; r)] = f ′ (x) and Er∼P |g(x; r) − f ′ (x)| ≤ σ p . 19

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Moreover, if using AdaGrad (Algorithm 1), with initial point x1 , learning rate γ, and hyperparameter λ, to optimize f by interacting with g (i.e., gt = g(xt ; rt ) where rt ∼ P is independent of the history), one must use at least   p p p p − − p γL(1+σ p−1 ϵ p−1 ) γL(1+σ p−1 ϵ p−1 ) 2 2 2 2 2 2 2 2 2 2 p−1 ∆ /γ + γ L ln λ∆/γ + ∆ /γ + γ L ln σ p p p p − −   λ+ϵ(1+σ p−1 ϵ p−1 ) λ+ϵ(1+σ p−1 ϵ p−1 )  + Ω 3p−2   2 ϵ p−1 ϵ

iterations to make E

h P T 1 T

i ′ |f (x )| < 2ϵ for small enough ϵ (see (28) for the precise condition on ϵ). t t=1

Remark B.2. The technical condition λ = 0 when σ = 0 is imposed to ensure that the second and third inequalities in (28) hold in the deterministic case. In fact, it suffices to require λ ≤ O(ϵ) when σ = 0, but we set λ = 0 for simplicity. Proof. In the proof, we write q≜ 1 + p−1 4

Moreover, let

1 2σ p p−1 ϵ

∈ [0, 1] .

(19)

γ √ , t ϵ +

δt ≜ λq

(20)

and ( T⋆ ≜ inf

T X

LX 2 ϵ2 T ∈N:∆−ϵ δt + δt < 4 t=1 2L t=1

) .

Now, let us consider the function f constructed in Lemma B.3 and the following function g : R × {0, 1} → R, ( f ′ (x) x∈ / {y1 , . . . , yT⋆ } g(x; r) = r ′ , q f (x) x ∈ {y1 , . . . , yT⋆ } where we recall that yt = x1 +

(21)

(22)

Pt−1

s=1 δs , ∀t ∈ [T⋆ ] is introduced in Lemma B.3 satisfying

f ′ (yt ) = −ϵ, ∀t ∈ [T⋆ ] .

(23)

According to Lemma B.3, we know f (x1 ) − inf f (x) ≤ ∆

and

x∈R

f is L-smooth.

Next, let P be the Bernoulli distribution with the parameter q given in (19), i.e., P [r = 0] = 1 − q One can find that Er∼P [g(x; r)] x ∈ {y1 , . . . , yT⋆ }, we know

(22),(24)

and

P [r = 1] = q.

(24)

p (22) f ′ (x) and Er∼P |g(x; r) − f ′ (x)| = 0 ≤ σ p if x ∈ / {y1 , . . . , yT⋆ }. If

p f ′ (x) q p−1 + (1 − q)p−1 p (23) p (22),(24) p Er∼P |g(x; r) − f ′ (x)| = |f ′ (x)| (1 − q) + − f ′ (x) q = (1 − q) ϵ q q p−1 (a) 22−p ϵp (b) 1 − q p−1 22−p ϵp (19) p ≤ (1 − q) p−1 ≤ = σ , q (p − 1) q p−1

where (a) is by q p−1

1−q p−1

p−1

+(1−q)p−1 2

1 ≤ 2p−1 due to the concavity of xp−1 (since p − 1 ∈ (0, 1]) and (b) holds by 1 − q ≤

, ∀q ∈ [0, 1] , p ∈ (1, 2]. Therefore, we know Er∼P [g(x; r)] = f ′ (x)

and

p Er∼P |g(x; r) − f ′ (x)| ≤ σ p . 20

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Suppose one runs AdaGrad to optimize f by interacting with g. Let us define

Rt ≜

t X

rt , ∀t ∈ N

ET ≜ {RT ≤ T⋆ − 1} , ∀T ∈ N.

and

(25)

s=1

Given T ∈ N, for any sample path in ET , we use induction to show {x1 , . . . , xt } ⊆ {y1 , . . . , yT⋆ } , ∀t ∈ [T ] .

(26)

For t = 1, (26) is true since y1 = x1 . Suppose (26) holds for some t ≤ T − 1, then we know gs = g(xs ; rs )

(22),(23),(26)

−

rs ϵ, ∀s ∈ [t] , q

which implies that vs =

s X

gℓ2 =

ℓ=1

ϵ2 X 2 ϵ2 X (25) ϵ2 rℓ = 2 rℓ = 2 Rs , ∀s ∈ [t] . 2 q q q

Therefore, by the update rule of AdaGrad, Rt t t X X X γ γrs (20) δs ∈ {y1 , . . . , yT⋆ } , δRs rs = x1 + xt+1 = x1 − = x1 + √ gs = x1 + √ λq λ + vs Rs s=1 s=1 s=1 ϵ + s=1 t X

where the last step is due to Rt ≤ RT ≤ T⋆ − 1 and yt = x1 +

Pt−1

s=1 δs , ∀t ∈ [T⋆ ]. Thus, the induction is complete.

If T ≤ T⋆2q−1 , by Markov’s inequality, we have P [RT > 2qT ] ≤

1 1 E [RT ] = ⇒ P [ET ] ≥ P [RT ≤ 2qT ] ≥ , 2qT 2 2

which implies that # " # T T ϵ 1X ′ 1X ′ |f (xt )| ≥ E |f (xt )| | ET P [ET ] ≥ , E T t=1 T t=1 2 "

′ where the last step is due to |f ′ (xt )| h= ϵ, ∀t ∈ [T ] since i {x1 , . . . , xT } ⊆ {y1 , . . . , yT⋆ } (see (26)) and |f (yt )| = ϵ, ∀t ∈ P T [T⋆ ] (see (23)). Therefore, to make E T1 t=1 |f ′ (xt )| < 2ϵ , one must have

T >

T⋆ − 1 . 2q

(27)

Finally, let us assume ϵ is small enough to satisfy4

ϵ≤

√

∆L,

ln 1 +

1 2

( λq ϵ ) +1

≥ 16ϵ γL ,

16ϵ γL

λq ϵ

ln c +1≤ √ , 2c

(28)

2 1 The first condition is trivial to satisfy. To make the second one hold, since ln(1+ x1 ) ≥ x+1 , it suffices to ensure that 16ϵ ( λq +2) ≤ γL ϵ 1, which is possible when ϵ is small enough due to the definition of q (see (19)). The third one is also true when ϵ is small enough by the definition of q. 4

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

where c ∈ [3.92, 3.93] is the unique positive solution to 2c = (1 + c) ln(1 + c). Note that     T T  2 X 2  X 1 γ L 1 ϵ (20),(21) T⋆ = inf T ∈ N : ∆ − ϵγ √ + < λq  4 t=1 λq √ 2 2L  t   t=1 ϵ + t ϵ +     T T   X (28) 1 1 γ2L X ∆ − ϵγ < 0 + ≥ inf T ∈ N : √ λq   2 4 t=1 λq √ 2 t   t=1 ϵ + t ϵ +     T T   X X ∆ γL 1 1 . = inf T ∈ N : + < √ λq  2γϵ 4ϵ t=1 λq √ 2 t   t=1 ϵ + + t ϵ Moreover, we observe that T X

1 √ ≤ λq t t=1 ϵ +

Z T

Z T +1

T X t=1

√ 2 ≥ λq + t ϵ

dt √ ≤ λq t ϵ +

Z T 0

dt r 2

dt √ 2 ≥ λq + t ϵ

λq ϵ

s =2 +t

Z T +1 1

dt 2

λq ϵ

2 +T −

2λq , ϵ

ln 1 + = +t

T 2

( λq ϵ ) +1 , 2

which together imply that     s   2  T ∆ γL  λq 2λq   + ln 1 + 2 T⋆ ≥ inf T ∈ N : +T − <2  2γϵ 8ϵ ϵ ϵ  λq   + 1 ϵ !   ( ) r   ln 1+ λqT 2   2 (√ϵ ) +1 λq λq ∆ 16ϵ inf T ∈ N : 4γϵ < + T − < + inf T ∈ N : ϵ ϵ γL  T    ≥ 2 !' & l m 2 λ∆q γ 2 L2 ∆2 q γL 2 2γϵ2 + 16γ 2 ϵ2 + 64ϵ2 ln 8ϵ ( λq ϵ ) +1 ≥ , 2

(29)

where the last step is due to (28) and Lemma B.4. Therefore, we obtain   γL 2 2 2 2 2 ∆ /γ + γ L ln (27),(29) λq+ϵ λ∆  T ≥ Ω 2 + γϵ ϵ2 q   p p p p − − p γL(1+σ p−1 ϵ p−1 ) γL(1+σ p−1 ϵ p−1 ) 2 2 2 2 2 2 2 2 2 2 p−1 λ∆/γ + ∆ /γ + γ L ln σ ∆ /γ + γ L ln p p p p − −   (19) λ+ϵ(1+σ p−1 ϵ p−1 ) λ+ϵ(1+σ p−1 ϵ p−1 ) . = Ω + 3p−2   2 ϵ ϵ p−1

B.2. Helpful Lemmas We provide three technical lemmas used in proving the algorithm-dependent lower bound for AdaGrad. We first prove Lemma B.3, which is essentially Lemma 20 of Hübler et al. (2025) (see also Lemma 15 of Jiang et al. (2025)). 22

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Lemma B.3. Given ∆ > 0, L > 0, 0 < ϵ ≤ ( T⋆ ≜ inf and yt ≜ x1 +

√

∞

2∆L, x1 ∈ R, and a nonnegative sequence {δt }t=1 , let T X

LX 2 ϵ2 T ∈N:∆−ϵ δt + δt < 4 t=1 2L t=1

) ,

Pt−1

s=1 δs , ∀t ∈ [T⋆ ], then there exists a function f : R → R such that:

f (x1 ) − inf f (x) ≤ ∆; x∈R

f ′ (yt ) = −ϵ, ∀t ∈ [T⋆ ] .

f is L-smooth;

Proof. For any δ ≥ 0, let ( gδ (x) ≜

−ϵ + Lx x ∈ [0, δ/2] . −ϵ + Lδ − Lx x ∈ (δ/2, δ]

Now, we introduce   x < y1 −ϵ f ′ (x) ≜ gδt (x − yt ) x ∈ [yt , yt+1 ) , t ∈ [T⋆ − 1] ,   −ϵ + L(x − yT⋆ ) x ≥ yT⋆ and

Z x f (x) ≜ ∆ +

f ′ (z)dz.

y1 ′

Note that f is L-smooth and satisfies f (yRt ) = −ϵ, ∀t ∈ [T⋆ ] by its definition. Thus, we only need to verify f (x1 ) − x inf x∈R f (x) ≤ ∆. Note that f (x1 ) = ∆ + y11 f ′ (z)dz = ∆ due to y1 = x1 , it remains to show inf x∈R f (x) ≥ 0. First, we can find that f (x) = ∆ + ϵ(y1 − x), ∀x < y1 ⇒ inf f (x) = f (y1 ). x<y1

Next, given t ∈ [T⋆ − 1], we can find that o n ( ϵ2 min f (yt ) − 2L , f (yt+1 ) inf f (x) = x∈[yt ,yt+1 ) f (yt+1 )

δt ϵ 2 ≥ L δt ϵ 2 < L

ϵ2 , f (yt+1 ) . ≥ min f (yt ) − 2L

Finally, we know inf f (x) = f (yT⋆ + ϵ/L) = f (yT⋆ ) −

x≥yT⋆

ϵ2 . 2L

The above three results together imply that inf f (x) ≥ min f (yt ) −

x∈R

t∈[T⋆ ]

ϵ2 . 2L

Now, we compute f (yt ) = ∆ +

t−1 Z ys+1 X s=1

gδs (z − ys )dz = ∆ − ϵ

t−1 X s=1

t−1

δs +

LX 2 δ , ∀t ∈ [T⋆ ] , 4 s=1 s

which implies that, by the definition of T⋆ , min f (yt ) −

t∈[T⋆ ]

t−1 t−1 X ϵ2 LX 2 ϵ2 = min ∆ − ϵ δs + δs − ≥ 0. 2L t∈[T⋆ ] 4 s=1 2L s=1

Next, Lemma B.4 provides a lower bound for an important quantity used in the proof of Theorem B.1. 23

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Lemma B.4. Let c ∈ unique positive solution to 2c = (1 + c) ln(1 + c), given A > 0 and B ≥ 1 [3.92, 3.93]√denote lnthe c satisfying ln 1 + B1 ≥ A and A B ≤ √ , we have 2c ( inf

Proof. Let h(x) ≜

T ln 1 + B √ T ∈N: T

)

4 2 ln ≥ A2

2 √

A B

x ln(1+ B ) √ for x ≥ 0. We have x

′

h (x) =

B −

x x 1+ B ln 1 + B 3

2x 2 (B + x)

x x 1 We can find h′ (x) ≥ 0 ⇔ 2x B − 1 + B ln 1 + B ≥ 0 ⇔ x ∈ [0, cB]. Therefore, h(T ) ≥ h(1) = ln 1 + B ≥ A when T ∈ [⌊cB⌋], implying that ( ) ( ) T T ln 1 + B ln 1 + B √ √ inf T ∈ N : < A = inf ⌊cB⌋ + 1 ≤ T ∈ N : <A T T ) ( T ln B <A ≥ inf ⌊cB⌋ + 1 ≤ T ∈ N : √ T ( √ √ ! √ ) A T A T A B = inf ⌊cB⌋ + 1 ≤ T ∈ N : − exp − >− . 2 2 2 Now, we redefine h(x) ≜ −x exp(−x) for x ≥ 0. Note that h′ (x) = exp(−x)(x − 1) ⇒ minx≥0 h(x) = h(1) = − 1e . Next, we observe that ! ! p p √ p √ A ⌊cB⌋ + 1 A ⌊cB⌋ + 1 A B h ≤− ⇔ ⌊cB⌋ + 1 ≥ B exp , 2 2 2 which holds due to √

ln c

A B≤ √2c √ p √ ⌊cB⌋ + 1 ≥ cB B exp ≥

! √ A 2cB cB≥⌊cB⌋≥1 √ ≥ B exp 2

⌊cB⌋ + 1 2

! .

Hence,

√ √ ! √ ) A T A T A B inf ⌊cB⌋ + 1 ≤ T ∈ N : − exp − >− ≥ ⌈Troot ⌉ , 2 2 2 √ √ √ where Troot ∈ R is the unique solution of h A 2 T = − A 2 B that guarantees A 2Troot > 1. More precisely, let W−1 be the Lambert W function, we have " √ !#2 √ ! √ A B A Troot A B 4 = −W−1 − ⇔ Troot = 2 −W−1 − . 2 2 A 2 (

Finally, we apply the standard inequality −W−1 (−x) ≥ ln x1 to conclude. Lastly, we prove Lemma B.5, which can help us further lower bound the algorithm-dependent lower bound. Lemma B.5. Given A ≥ 1, then inf η>0 η1 + η ln2 (Aη) ≥ ln A. Proof. Let h(η) ≜ η1 + η ln2 (Aη), ∀η > 0. We can find 1 h′ (η) = − 2 + ln2 (Aη) + 2 ln(Aη) η 24

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

and 2 1 + η 2 ln η + η 2 2 1 + 2η 2 − η 2 1 + η 2 ln(Aη) + η 2 h (η) = ≥ ≥ > 0. η3 η3 η3 ′′

Therefore, h′ (η) is increasing, implying that h′ (η) = 0 has a unique solution η⋆ > 0 as the minimizer of h(η), since h′ (1/A) < 0. Let us denote by λ⋆ ≜ ln(Aη⋆ ). Then we have ′

h (η⋆ ) = 0 ⇔ λ2⋆ + 2λ⋆ =

2 exp (λ⋆ ) λ2⋆ + λ⋆ 1 2 ⇒ h(η⋆ ) = 2η⋆ λ⋆ + λ⋆ = . η⋆2 A

One more step, observe that λ⋆ = ln(Aη⋆ ) ⇔ A = exp (λ⋆ ) /η⋆ = exp (λ⋆ ) which implies that λ⋆ > 0 (if not, then λ⋆ ≤ −2 ⇒ A = exp (λ⋆ )

λ2⋆ + 2λ⋆ ,

p λ2⋆ + 2λ⋆ < 1, contradicting A ≥ 1).

Now, we know λ⋆ > 0,

h(η⋆ ) = 2 (λ⋆ + 1)

λ⋆ λ⋆ +2 ,

ln A = λ⋆ + ln

λ2⋆ + 2λ⋆ .

As one can check, there is ln A ≤ λ⋆ +

r λ2⋆ + 2λ⋆ − 1 ≤ 2 (λ⋆ + 1)

λ⋆ , ∀λ⋆ > 0, λ⋆ + 2

which implies what we want.

C. Another Upper Bound for AdaGrad-Norm In this section, we provide another upper bound for AdaGrad-Norm, given in Theorem C.1. Unlike Theorem 4.2, this bound 3p−4 does not require the objective function to be bounded. However, it is only in the order of Õ(1/T 4p ) as a trade-off (same as Theorem A.1 for AdaGrad), which becomes vacuous when p ∈ (1, 4/3]. C.1. Theorem and Its Proof Theorem C.1. Under Assumptions 2.1, 2.2, 2.3, and 2.4, let ∆ ≜ f (x1 )−f⋆ , then for any γ > 0 and λ > 0, AdaGrad-Norm (Algorithm 2) guarantees # T 1X E ∥∇f (xt )∥2 ≤O T t=1 "

√

where KT = 1 +

λ+ ∆ ∥σ∥p ln p̄ + 2 KT γ + γ ∥L∥∞ ln KT √ + p−1 T T p r  ∆ 1 1 + γ ∥L∥ ln K ∥σ∥ + T ∞ p γ ∥σ∥p ln 2p̄ 4 KT  , + + p−1 3p−4  T 2p T 4p 3

2∥σ∥p T p +2∥∇f (x1 )∥2 T 2 +2γ∥L∥∞ T 2 λ

is introduced in Lemma C.5. √

√

1 1 1 −1 2∥σ∥p T p +E[ 2uT ] Proof. Equipped with Lemmas C.2 (choose c ≜ ∥σ∥p T 2 − p̄ /DT2 p̄ for DT ≜ 2 ln(1 + ) when λ invoking it), C.3, C.4, and C.5, the proof of Theorem C.1 follows essentially the same way as proving Theorem A.1, which is omitted here to save space.

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

C.2. Helpful Lemmas This subsection provides all necessary lemmas to prove Theorem C.1. The following four lemmas correspond to Lemmas A.2, A.3, A.4, and A.5 under the ℓ2 geometry. Their proofs do not involve new techniques, except that wt is now defined as follows 2 wt ≜ vt−1 + ∥∇f (xt )∥2 + c2 ∈ Ft−1 , ∀t ∈ N, where c ≥ 0 can be an arbitrary constant and will be determined in the proof of Theorem C.1. Lemma C.2. Under Assumptions 2.2, 2.3, and 2.4, for any c ≥ 0 and t ∈ N, AdaGrad-Norm (Algorithm 2) guarantees " # 2 2 ∥σ∥p ∥∇f (xt )∥2 γ E ≤ E [f (xt ) − f (xt+1 )] + γ √ 2 λ + wt c

∥g ∥ E 2 t 2 λ + vt

#! p̄2

γ ∥L∥∞ +γ c+ 2

# " 2 ∥g t ∥2 E 2 . λ + vt

Proof. We start with Assumption 2.2 and use the update rule of AdaGrad-Norm to obtain 2

∥xt+1 − xt ∥L f (xt+1 ) ≤ f (xt ) + ⟨∇f (xt ), xt+1 − xt ⟩ + 2 2 γ 2 ∥g t ∥L gt = f (xt ) − γ ∇f (xt ), + √ √ 2 λ + vt 2(λ + vt ) 2 γ 2 ∥L∥∞ ∥g t ∥2 gt ≤ f (xt ) − γ ∇f (xt ), + √ λ + vt 2(λ2 + vt ) 2 γ 2 ∥L∥∞ ∥g t ∥2 gt gt gt = f (xt ) − γ ∇f (xt ), . + γ ∇f (xt ), + √ √ − √ λ + wt λ + wt λ + vt 2(λ2 + vt ) Take conditional expectations on both sides of the above inequality and use 2 Et−1 [g t ] Assumption 2.3 ∥∇f (xt )∥2 gt xt ,wt ∈Ft−1 Et−1 ∇f (xt ), = ∇f (xt ), = √ √ √ λ + wt λ + wt λ + wt to obtain " # 2 2 ∥g t ∥2 ∥∇f (xt )∥2 γ 2 ∥L∥∞ Et−1 Et−1 [f (xt+1 )] ≤f (xt ) − γ + √ λ + wt 2 λ2 + v t gt gt + γEt−1 ∇f (xt ), . √ − √ λ + wt λ + vt Now, we can bound gt gt Et−1 ∇f (xt ), √ − √ λ + wt λ + vt 1 1 ≤Et−1 ∥∇f (xt )∥2 ∥g t ∥2 − √ √ λ + wt λ + vt   2 2 2 ∥g ∥ ∥g ∥ − ∥∇f (x )∥ − c t t t 2 2 2 (a) ∥∇f (xt )∥2  = Et−1  √ √ √ √ λ + wt (λ + vt )( wt + vt ) ∥∇f (xt )∥2 (∥g t ∥2 + ∥∇f (xt )∥2 ) ∥ξt ∥2 ∥g t ∥2 c2 ∥g t ∥2 ≤ Et−1 + Et−1 √ √ √ √ √ √ √ λ + wt (λ + vt )( wt + vt ) (λ + vt )( wt + vt ) (b) ∥∇f (x )∥ ∥ξ t ∥2 ∥g t ∥2 c ∥g t ∥2 t + Et−1 ≤ √ 2 Et−1 √ √ λ + wt λ + vt λ + vt 2 2 ! 2 (c) ∥∇f (x )∥ c ∥g t ∥2 ∥ξ t ∥2 ∥g t ∥2 1 t 2 ≤ + Et−1 + Et−1 , √ √ √ √ 2(λ + wt ) λ + wt λ + vt λ + vt 26

(30)

(31)

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

√ √ √ √ ∥∇f (xt )∥2 √ wt + vt and c ≤ wt + vt , and (c) holds by λ+ wt ∈ Ft−1 , (b) is due to ∥g t ∥2 + ∥∇f (xt )∥2 ≤ h h i i ∥ξt ∥2 ∥g t ∥2 c∥g ∥ ∥∇f (xt )∥22 √ AM-GM inequality, i.e., ∥∇f (xt )∥2 X ≤ and Et−1 λ+√t v2t , respectively. + X 2 for X = Et−1 4 λ+ vt where (a) is by

Next, we apply Hölder’s inequality to get #! p̄2 p̄ ∥g ∥ p t 2 ≤ (Et−1 [∥ξ t ∥2 ]) Et−1 Et−1 √ (λ + vt )p̄   " #! p̄2 ! p̄2  p̄2 p̄ 2 ∥·∥2 ≤∥·∥p ,Assumption 2.4 ∥g ∥ ∥g ∥ 2 2 t 2  , ≤ ∥σ∥p Et−1 ≤ ∥σ∥p Et−1  2 t 2 √ (λ + vt )p̄ λ + vt

and

∥ξ t ∥2 ∥g t ∥2 √ λ + vt

2 p

" # # " 2 2 2 c2 ∥g t ∥2 c ∥g t ∥2 c2 ∥g t ∥2 ≤ Et−1 ≤ Et−1 . Et−1 √ √ λ + vt (λ + vt )2 λ2 + v t

(32)

(33)

Plug (32) and (33) into (31) to obtain Et−1 ∇f (xt ),

gt gt √ − √ λ + wt λ + vt   ! p̄2  p̄2 # " 2 2 2 2 2 ∥σ∥ ∥∇f (xt )∥2 ∥g ∥ ∥g ∥ c p t t 2 2  + ≤ + √ √ Et−1  2 √ Et−1 2(λ + wt ) λ + wt λ + vt λ + wt λ2 + vt 2

∥σ∥p ∥∇f (xt )∥2 ≤ + √ 2(λ + wt ) c where the last step is by λ +

√

" Et−1

∥g t ∥2 λ2 + v t

#! p̄2

" + cEt−1

# 2 ∥g t ∥2 , λ2 + v t

(34)

∥g ∥2

t 2 ≤ 1, and p̄2 ≥ 1. wt ≥ c, λ2 +v t

We combine (30) and (34) to have 2

∥σ∥p γ ∥∇f (xt )∥2 Et−1 [f (xt+1 )] ≤ f (xt ) − +γ √ 2(λ + wt ) c

" Et−1

∥g t ∥2 λ2 + vt

#! p̄2

γ ∥L∥∞ +γ c+ 2

Et−1

# 2 ∥g t ∥2 . λ2 + v t

Taking expectations on both sides and rearranging terms, we know  " # " #! p̄2  # " 2 2 2 2 ∥σ∥p ∥∇f (xt )∥2 ∥g ∥ ∥g ∥ γ ∥L∥ γ t 2 ∞ +γ c+ E ≤ E [f (xt ) − f (xt+1 )] + γ E  Et−1 E 2 t 2 . √ 2 λ + wt c λ2 + v t 2 λ + vt Finally, noticing that p̄2 ≥ 1, we hence can invoke Hölder’s inequality again to have  " #! p̄2  " " ##! p̄2 " #! p̄2 2 2 2 ∥g ∥ ∥g ∥ ∥g ∥ t 2 t 2  ≤ E Et−1 E  Et−1 = E 2 t 2 , λ2 + vt λ2 + v t λ + vt which leads us to the desired result. Lemma C.3. For any T ∈ N and q ∈ [0, 1], AdaGrad-Norm (Algorithm 2) guarantees " #!q T 2 h X ∥g t ∥2 vT iq E 2 ≤ T 1−q E ln 1 + 2 . λ + vt λ t=1 Proof. By the concavity of xq (since q ∈ [0, 1]), we have " #!q T 2 ∥g t ∥2 1X E 2 ≤ T t=1 λ + vt 27

" #!q T 2 ∥g t ∥2 1X E 2 , T t=1 λ + vt

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

which implies that T X t=1

∥g ∥ E 2 t 2 λ + vt

#!q ≤T

1−q

" T #!q X ∥g ∥2 t 2

1−q

≤ T 1−q

λ2 + vt−1 E 1− 2 λ + vt t=1

#!q

=T λ2 + v t " T #!q h X λ2 + vt vT iq E ln = T 1−q E ln 1 + 2 , 2 λ + vt−1 λ t=1

t=1

(a)

" T X

where (a) is due to 1 − x−1 ≤ ln x, ∀x > 0. Lemma C.4 (Restatement of Lemma 4.7). Under Assumption 2.4, for any t ∈ N, AdaGrad-Norm (Algorithm 2) guarantees √ √ 1 √ E [ vt ] ≤ 2 ∥σ∥p t p + E 2ut , Pt 2 where ut ≜ s=1 ∥∇f (xs )∥2 , ∀t ∈N. Lemma C.5. Under Assumptions 2.2 and 2.4, AdaGrad-Norm (Algorithm 2) guarantees √ √ ! 1 h 2 ∥σ∥p T p + E 2uT vT i ≤ 2 ln 1 + ≤ 2 ln KT , E ln 1 + 2 λ λ √

where KT ≜ 1 +

2∥σ∥p T p +2∥∇f (x1 )∥2 T 2 +2γ∥L∥∞ T 2 . λ

Proof. Note that √ ! r √ h E vT vT vT i vT E ln 1 + 2 1+ 2 ≤ 2E ln 1 + ≤ 2 ln 1 + , = 2E ln λ λ λ λ where the last step is due to the concavity of ln x. Next, we invoke Lemma C.4 to obtain √ √ ! 1 h 2 ∥σ∥p T p + E 2uT vT i E ln 1 + 2 . ≤ 2 ln 1 + λ λ

(35)

Moreover, under Assumption 2.2, we have almost surely, for any t ∈ [T ], ∥∇f (xt ) − ∇f (x1 )∥1/L ≤ ∥xt − x1 ∥L ≤

t−1 X

∥xs+1 − xs ∥L

s=1

t−1 t−1 q q X X γ ∥g s ∥L γ ∥L∥∞ = γ ∥L∥∞ (t − 1) √ ≤ λ + vs s=1 s=1

⇒ ∥∇f (xt ) − ∇f (x1 )∥ ≤ γ ∥L∥∞ (t − 1). Hence, there is almost surely v v u T u T u u X X √ 2 2 t 2uT = 2 ∥∇f (xt )∥2 ≤ t2 (∥∇f (x1 )∥2 + γ ∥L∥∞ (t − 1)) t=1

t=1

v u T T uX X 2 2 ≤ 2t ∥∇f (x1 )∥2 + γ 2 ∥L∥∞ (t − 1)2 t=1

t=1 1 2

≤ 2 ∥∇f (x1 )∥2 T + 2γ ∥L∥∞ T 2 .

(36)

Finally, we plug (36) back into (35) to have ! √ √ √ ! 1 1 1 3 2 ∥σ∥p T p + E 2uT 2 ∥σ∥p T p + 2 ∥∇f (x1 )∥2 T 2 + 2γ ∥L∥∞ T 2 ≤ 2 ln 1 + = 2 ln KT . 2 ln 1 + λ λ

Record · ID 200482 · SHA-256 9c36bcf8ef607e73
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.