Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise
Authors: Ta Duy Nguyen
Thien Hang Nguyen
Alina Ene
Huy Nguyen
Venue: NeurIPS 2023 spotlight (2023)
Keywords: convex optimization
non-convex optimization
high probability convergence
heavy-tailed noise
clipped stochastic gradient descent
clipped stochastic mirror descent
TL;DR: We provide optimal convergence rate in high probability for clipped gradient methods under heavy-tailed noise, closing the logarithmic suboptimality gap and addressing several open questions in this setting left by previous works.

Abstract: In this work, we study the convergence in high probability of clipped gradient methods when the noise distribution has heavy tails, i.e., with bounded $p$th moments, for some $1<p\le2$. Prior works in this setting follow the same recipe of using concentration inequalities and an inductive argument with union bound to bound the iterates across all iterations. This method results in an increase in the failure probability by a factor of $T$, where $T$ is the number of iterations. We instead propose a new analysis approach based on bounding the moment generating function of a well chosen supermartingale sequence. We improve the dependency on $T$ in the convergence guarantee for a wide range of algorithms with clipped gradients, including stochastic (accelerated) mirror descent for convex objectives and stochastic gradient descent for nonconvex objectives. Our high probability bounds achieve the optimal convergence rates and match the best currently known in-expectation bounds. Our approach naturally allows the algorithms to use time-varying step sizes and clipping parameters when the time horizon is unknown, which appears difficult or even impossible using the techniques from prior works. Furthermore, we show that in the case of clipped stochastic mirror descent, several problem constants, including the initial distance to the optimum, are not required when setting step sizes and clipping parameters.

Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise
Ta Duy Nguyen Department of Computer Science Boston University taduy@bu edu
Thien Hang Nguyen
Khoury College of Computer Sciences
Northeastern University
nguyen. thienchor edu
Alina Ene
Huy Le Nguyen
Department of Computer Science Boston University aene@bu. edu
Khoury College of Computer Sciences Northeastern University
hu www..gyannnnothhhsttmmm.mmmm edu
Abstract
In this work, we study the convergence in high probability of clipped gradient methods when the noise distribution has heavy tails, i.e., with bounded pth moments, for some I < - 2. Prior works in this setting follow the same recipe of using concentration inequalities and an inductive argument with union bound to bound the iterates across all iterations. This method results in an increase in the failure probability by a factor of T. where T the number of iterations. We instead propose new analysis approach based on bounding the moment generating function of a well chosen supermartingale sequence. We improve the dependency T in the convergence guarantee for a wide range of algorithms with clipped gradients, including stochastic (accelerated) mirror descent for convex objectives and stochastic gradient descent for nonconvex objectives. Our high probability bounds achieve the optimal convergence rates and match the best currently known in-expectation bounds. Our approach naturally allows the algorithms to use time-varying step sizes and clipping parameters when the time horizon is unknown, which appears difficult or even impossible using existing techniques from prior works. Furthermore, we show that in the case clipped stochastic mirror descent, several problem constants, including the initial distance to the optimum, are not required when setting step sizes and clipping parameters.
Introduction
Stochastic optimization is well-studied area with many applications ranging from machine learning, to operation research, numerical linear algebra and beyond. In contrast to deterministic algorithms, stochastic algorithms might fail, and pertinent question is how often does failure happen and how to increase the success rate. These questions are especially important in critical applications where failure is not tolerable, or when single run is costly in time and resources. Fortunately, the standard stochastic gradient descent (SGD) algorithm has been shown to converge with high probability under light-tailed noise distribution such sub-Gaussian distributions 23 12 27 14. III [0 [8], which gives strong guarantee on the success single runs. However, recent observations in popular deep learning applications, such training attention models BB and convolutional networks [30, reveal more challenging optimization landscape: the gradient noises follow heavy-tailed distributions, where the variance may be infinite 29 33 9 whereas
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the standard light-tailed setting assumes that all the moments are bounded. Heavy-taile gradient noises can cause algorithms like SGD to fail, and this mismatch between theory and practice has been suggested to be one of the reasons for the strong preference of adaptive methods like Adam over SGD in modern settings 33
In this work, we consider the setting of heavy-tailed noise proposed by Zhang et al., (2020) [33] where the (unbiased) gradient noise only has bounded pth moments, for some p (1. 2|. While standard SGD can fail to converge when the variance is unbounded, i.c. when p < 2. 33 show that SGD with appropriate clipping (or Clipped-SGD) converges in expectation under heavy- where the convergence rate depends on O (1) if 5 is the targeted maximum failure probability. It is more desirable, however, to obtain convergence results in high probability, where the convergence rate depends instead on O(log) 3) which gives better guarantees for single runs.
noise,
28 19 show that variants of Clipped-SGD in fact converge with high probability. This is a pleasing result, extending the earlier work by 77] for p = 2. However, there are several shortcomings of these results when compared with the corresponding bounds in the light-tailed setting. First, the clipped algorithm uses a fixed step size and a fixed clipping parameter depending on the number of iterations, which precludes results with unknown time horizons. Secondly, the convergence guarantees are worse than the light-tailed bounds by a log T factor, even for fixed step sizes and clipping parameters. These issues beg a qualitative question:
Recent follow-up works 2
Is heavy-tailed noise inherently harder than light-tailed noise?
In this work, we answer the above question for Clipped-SGID and the general clipped (accelerated) stochastic mirror descent (Clipped-SMD) algorithm. We give an improved analysis framework that not only gives tighter bounds matching the light-tailed noise setting, but also allows for step sizes and clipping parameters for unknown time horizons. Furthermore, we show that this framework is applicable to various settings, from finding minimizers of convex functions with arbitrarily large domains using (accelerated) mirror descent, to finding stationary points for non-convex functions using gradient descent.
1.1 Contributions and Techniques
Our work addresses several open questions posed by previous works including handling general domains and dealing with an unknown time horizon under heavy-tailed noise. Qualitatively, we close the logarithmic suboptimality gap and achieve the optimal rate in several settings. More specifically:
We demonstrate novel approach analyze clipped gradient methods in high probability that is general and applies to various standard settings. In the convex setting, we analyze Clipped-SMD and clipped stochastic accelerated mirror descent. In the non-convex setting, we analyze Clipped- SGD. Using our new analysis, we show that clipped methods attain time-optimal convergence in high probability for both convex and nonconvex objectives under heavy-tailed gradient noise. In the convex setting, we obtain an O
convergence rate for arbitrary (not necessarily compact)
T for accelerated Clipped-SMD, where convex domains for Clipped -MD and O ( o is the noise parameter. These rates are time-optimal and match the lower bounds in 26 31. In the nonconvex setting, we obtain the optimal convergence rate of O
3p-7 for clipped-SGD.
This bound is also time-optimal and matches the lower bound in 33 it also complements the in-expectation convergence of clipped-SGD provided by [33].
Previous works for heavy-tailed noises follow the recipe of using Freedman-type inequalities 3 as a blackbox and bound the iterates inductively for all iterations. This process incurs an additional log T dependency in the final convergence rate; in other words, the success probability goes from 1-6 to 1 Tô. The step sizes and clipping parameters of this approach depend on the time horizon T to enable the union bound and induction across all iterations in the analysis, excluding the important case when the time horizon is unknown. Our whitebox approach forgoes the aforementioned induction, not only circumventing the log T loss but also allowing for an unknown time horizon. We further show that our analysis allows for a choice of step size and clipping parameters that do not depend generally unknown parameters like the noise- poram-par a, the
2

---

to handle give new failure probability 6, and the initial distance to the optimum, all of which appear impossible using only the techniques from prior works.
Our whitebox approach analyzes the moment generating function of a well chosen martingale difference sequence to obtain tight rates for stochastic gradient methods. This approach is closest to the work of [18), which only work in the light-tailed noise setting. In contrast to the light-tailed noise setting where all the moments are well controlled, the heavy-tailed setting often requires algorithms to incorporate gradient clipping for controlling the possibly infinite moments, However, this makes the gradient estimate biased and requires more careful attention control the bias propagating through the algorithm. Naively applying the technique in [18] is not enough to handle heavy-tailed weights for
noise. Rather, will be shown in our analysis, we introduce novel history-dependee the martingale sequence that is able to cope with the propagating bias term of clipped methods for heavy-tailed noise across various settings.
1.2 Related Works
High probability convergence for light-tailed noises. Convergence in high probability of stochastic gradient algorithms has been established for sub-Gaussian noises a number of prior works, including 23
10) for convex problems with bounded domain (or bounded Bregman diameter) or with strong convexity. Other works [1] 20 16 study convergence of variants of SGD for nonconvex objectives, where they consider Gaussans and aub-Weibull noises. The most relevant to ours in this line of work is the one by [18]. where a whitebox approach is employed obtain tight rates for stochastic gradient methods in the light-tailed noise setting. However, their technique is not directly applicable in the heavy-tailed noise setting, where we need to introduce new ideas to handle the biases introduced by gradient clipping.
12
27 14
High probability convergence for noises with bounded variance and heavy tails. The design of new gradient algorithms and their analysis in the presence of heavy-tailed noises has drawn significant recent interest. Starting from the work [25] which propose Clipped
exploding gradients in recurrent neural networks, the recent works 30
29
33
9
motivation for clipped methods in the context of convolutional networks and attention deep networks that attempts to explain the dominance of adaptive methods over SGD in practical modern scenarios.
While the convergence in expectation of vanilla SGD has been extensively studied only recently has the convergence of Clipped-SGD with heavy tailed noises been closely examined. There, [3 first show the convergence in expectation of Clipped-SGD for nonconvex functions and provide matching lower bound. In the convex regime. several works with different clipping strategies for the case of p = have shown high probability convergence for smooth problems with bounded domain 22 24. smooth unconstrained problems 77. and non-smooth problems (8]. A variant of Clipped-SGID that utilizes momentum [2] has also been shown to converge with high probability for bounded pth moments gradient noise. However, the analysis in (2) requires strong assumption which implies that the true gradients are bounded, a restrictive assumption that excludes objectives like quadratic functions.
23 13 18
More recently, 28 34 give nearly-optimal convergence rates for several Clipped-SGD variants. These works follow the recipe of using Freedman-type inequalities 4 3 blackbox and bound the iterates inductively for all iterations, which incur an additional log T dependency in the final convergence rate. We show in work that existing convergence rates can be tightened up and improved. Tight lower bounds for the optimal convergence rate have been shown by [26] 31 for convex objectives and by 33 for nonconvex settings. In both cases, our paper provides optimal convergence guarantees.
In a related but different line of work, 332 show that vanilla SGD can converge with heavy tailed noise for a special type of strongly convex functions, and (31) show that stochastic mirror descent converges in expectation for a special choice of mirror maps, although only for strongly convex objectives with bounded domains.
2 Preliminaries: Assumptions and Notations
We study the problem mingex f(x) where / Rd - R and X' the domain of the problem. In the convex setting, we assume that X is convex set but not necessarily compact. We let ||-|| be an
3

---

Table 1: Previous and new results for high-iighheneee probability convergence (with fäilure probability 6) of clipped SMD SGD under heavy tailed noise: [(r) Vf(>)]
æ] S some p E (1, 2], where V (z) denotes the stochastic gradient æ for the objective f. For the convex setting, the emror bounds are for the optimality gaps Σ f(x)) f" For nonconvex setting, we bound the gradient norm 7 Ei=1 [= Here, (-) hides polylog factors. Note that, for simplicity, we do not compare against results in more specialized settings such as bounded domain bounded gradients, well as other variants of clipped SGD.
Assumptions
Convex Setting Clipped-SMD)
Non-convex Sctting (Clippe--GG)
p2
Lower bound
[1,
Previous
high-probability
Known T
28
T
28
results
Known T
T P
(Thm4.1
T T
(Thm
3.1
Our results
Unknown T
T
(.hm
δ T3--2
B.2
arbitrary norm and I|-II, be its dual norm. In the nonconvex setting, we take to be R2 and consider only the &2 norm.
2.1 Assumptions
Our paper works with the following assumptions:
(1) Existence of a minimizer: In the convex setting, we assume that there exists x² E arg min fz). We let f* = fx**).
(1') Existence lower bound, i.., f = inf f(x) -oo.
finite lower bound: the nonconvex setting, we assume that f admits a finite
(2) Unbiased estimator: We assume that our algorithm is allowed to query a stochastic first-order
oracle that returns a history- innier-independent, unbiased gradient estimator f(()) of fz(x) for any
E X. That is, conditioned on the history and the queried point æ, we have [())(z) æ| fx(r).
(3) Bounded pth moment noise: We assume that there exists
such that for some p S
and for any X, (f()) satisfies [ (=) x] S pp.
(4) L-smoothness: We consider the class of L-smooth functions: for all a,y [V]((x) V. s
Rd,
L || yll-
2.2 Gradient Clipping Operator and Notations
We introduce the gradient clipping operator and its general properties used in Clipped-SMD (Algorithm 2 and Clipped-SGD (Algorithm [ Let x; be the output iteration / of algorithm of interest. We denote by (x,) the stochastic gradient obtained by querying the gradient oracle. The elipped gradient estimate ff(x,, is taken as
f(.)) min {1
X (
f(())).
where de is the clipping parameter used iteration f. In subsequent sections, we let A, == ((x) f denote the optimal function value gap at dt. We let F, a (vf(z),.... v)(x;) be the natural filtration time t and define the following notations for the stochastic error, the deviation, and the bias of the clipped gradient estimate at time t:
(f(a))-V(())
0 = -f (f(z) E
Vz())) -V))))((m))
Note that 07t 0 = 0,. Regardless of the convexity the function f, the following lemma provides upper bounds for these quantities. These bounds can be found in prior works 77 33
19 28 for the

---

Algorithm Clipped-SGD
Parameters: initial point 21, step sizes } clipping parameters {
for = 1 to T do
1. |ل (f(())
(xs) - min
2++1 = It TJt V.())))
special case of & norm. The extension to the general norm follows in the same manner, which we omit in this work.
Lemma 2.1. For stochastic gradients A ((()) with bounded pth moment noise, the clipped gradients
f(x) satisfy the following properties:
11 [ - E (((x)) (1(())FFF-1)) Fr-1]]. S 22.
(2)
Furthermore, if fx,))l.
< Az then
||0.11_ = | V (Tx)) Fi-1 v v S -
(3)
E |0:11 E
2 [ - E. {)({))) 1 |
< 400 xe 2-p
(4)
Finally, we state a simple but important lemma that bounds the moment generating function of zero-mean bounded random variable. The proof can be found in, for example, equation (3) of (I]
Lemma 2.2. Let X be a random variable such that E [X] = 0 and |X| v R almost surely. Then 0 2
3 (2 (
E lexp (AX)) S exp (
3 Clipped Stochastic Gradient Descent for Nonconvex Functions
In this section, we study the convergence of Clipped-SGD nonconvex functions. Here, we consider the domain to be Rd equipped with the standard & norm. We first outline blackbox concentration argument to show convergence in high probability of Algorithm [ and then follow- up with more powerful whitebox approach that allows for tight high probability convergence analysis.
In the simple setting of known time horizon and without momentum for Clipped-SGD, the 5 convergence rate has not been shown before to the best of our knowledge. The recent work by (28) study this case and only give suboptimal rate of Ö(T'>1 i-P, Note that 22 19] study other variants Clipped-SGD with momentums incorporated.
Comparison to previous works.
Although 2 [9] achieve the nearly-optimal time dependency of Ō ) in the non-convex
settings, they rely on using blackbox concentration incqualities which result in a suboptimal convergence rate that also requires known time horizon.
We first present the guarantee for known time horizon via our whitebox approach in Theorem 3.1 and defer the statement for unknown T in Theorem B.2 to the Appendix.
Theorem 3.1. Assume that f satisfies Assumption (I"), (2), (3), (4). Lety max flog } 1] and
A = f(z1) f For known time horizon T, we choose d and t). such that
A = = max {
8Y VLA
T5=I 2 ;; a 30-2
A
87 VLA
T 20r4 4
3p--2
T 3p3-2
1/ : 8A Tn
min
T
2
2090
32
5

---

Then with probability at least 1 -
vf(x))) S 720 A12yy Aaxyymx max {
(LA (VIL),
87
2-30
T
1-2p 2 90LA,
3:32 2; o 3
= (T 2-2p
Remark 3.2. In comparison to the corresponding results in 28 (Theorem E.2), while our result achieves a poly T factor better rate when p 2, the dependency on log in our result contains dependency on while the result in [28] does not. That term can dominate the convergence rate in the regime when is very small and p is very close to Hence, an open question is to remove such dependency on for the log & term while still maintain the optimal rate on T'.
Now, we turn to the analysis, starting with the key Lemma 3.3 (proof in the Appendix).
Lemma 3.3. Assume that I satisfies Assumplion (1'), (2), (3), (4) and 1)t S I then all 2
T |V s S.. A + (Ln) ne) ( 8/0 + 37p
110518
2
Lan (10%1] |10" F--1) + Ln |108 11?
Fr-1
(5)
Remark 3.4. In Lemma 3.3 we decompose the RHS into appropriate terms that allow us define a martingale. This lemma helps us understand why we can achieve better convergence rate O(T O(T (for minimizing the norm squared of the gradient) in comparison to the best rate of o(T in the convex setting. We focus the error term (Vf(z)),
(Vf(x)) + (VS(=)), 0)) on the RHS of (5) Since this error contains the gradient V((x),, we leverage
some of the gain fxx))) the LHS 5 we use Cauchy-Schwarz to bound (v)( 0?) S f(xa)l 1 1101112 and use the some of the gain to absorb the first term. Then setting our
parameters A 7/ uppropriately balance the remaining terms helps us achieve the O Sp-2) rate. Contrast this to the convex setting in the next section: the mismatch between the error term that contains the distance term ||=-- and the gain term that contains the function value gap (z+) prevents from using the gain to absorb some of the error. Thus, this explains the convergence rate discrepancy between the convex case and the non-convex setting (see also Remark 4.6).
Before giving sketch of our whitebox approach, we present a sketch of a blackbox argument that gives nearly time-optimal convergence rate. This approach has an additional log T factor in the final rate but will serve as a point of comparison for our new techniques, which will close the logarithmic gap.
Blackbox approach. The key lies in the following lemma, which yields the near optimal ÖT (p convergence rate of Clipped-SGD. In this case, we assume that the clipping parameters X; and the step sizes T)t are fixed. Note that the success probability is only 1- This result uses Lemma 3.3 and Freedman's 's inequality (Theorem A.I] primarily as a blackbox to bound the error terms inductively by the initial function value gap optimality.
Lemma 3.5. For 1 S N < T + 1, let np 17, X X (the specific choices omitted here for brevity) and EN be the event that for all l = 1,...N,
k 31 10812
Lap Σ 10:1 + (Lo² - Σ (V[())) 0,) +
< A
2
Then Eyy happens with probability at least 1 1)8 for each N E T +1.
T
With the above lemma, we can obtain a optrmmltimal convergence rate. However, this rate is still suboptimal due to the use of union bounds as part of the induction proof. We now discuss an improved analysis that closes the remaining gap.
Whitebox approach. Our whitebox approach defines a novel supermartingale difference sequence Z, (shown below) and analyzes its moment generating function from first principles. The sequence is

---

designed to leverage the structure of the problem and Clipped-SGrr SGD via carefully chosen decreasing weights 2t (shown below).
+ A141 D. - 3// Tt [V((2))]l 2
|1o.11 LE E |10511 (F(-1)
Zi :
22
L12 A. 6L22 E 10:11 |F.-1]
where 2, 1= 2p maxis: V2LA. SQ₂Lai
for Qr Fi-1 2 1. We also define S, =- Ei=1 Zi Note that by selecting Pr. Qz, Tt A appropriately so that Pe and Qun X2 are constants (see for example the proof of Proposition 3.7 in the Appendix), we can ensure that the sequence 2; is decreasing.
We now present Lemma 3.6 which is the main result for controlling the above martingale, whose proof will offer insights into the main technique in this paper. The technique to prove Lemma is similar to the standard way of bounding the moment generating function in proving concentration inequalities, such as Freedman's inequality 4 3) The main challenge here is to find way to leverage the structure of Clipped-SGD and choose the suitable coefficients 2, Similarly to [18] where the authors analyze SGD with sub- Gaussinn noise, we analyze the martingale difference sequence in a "whitebox" manner. In (18), however, thanks to the light-tailed noise, the weights 2, can be chosen depending only on the problem parameters and independently of the algorithm history. On the other hand, to use Lemma 2.2 we have to make sure that 2, I 1 R. where R is an upper bound for the martingale elements. The key here is to choose 2, depending on the past iterates, and use the function value gaps A, to absorb the error incurred during the analysis. We give a proof sketch and defer the full version to the Appendix.
Lemma 3.6. For any 5 > 0, let E(6) be the event that for all 1 S k: S
k
Te [V((1))]
+2 S 21 + log
1
+
Σ
32
110%11
2
{5-1)
+
(3z LMf A. + 6L22 + Ln 13
110:11
1=1
Then Pr Pr[E((0 2 1
8.
Proof Sketch. Using Lemmas 3.3
2.2 and the condition for 22. we can show that [exp (Zt) F(-1] < 1. This then implies
E [exp (St) Fe-1] = exp (S TE [exp (2,) [i-1) S exp (S.-),,
which means (exp (8.));2 1 is a supermartingale. By Ville's inequality, we have, for all A > 1. Pr [S 2 log 8 < dE [exp (Si) < 8. In other words, with probability at least - 6, for all k: 2 1,
Σ Z S log } Plugging the definition of Z₁ we obtain the desired inequality.
We now specify the choice of т) and A The following lemma gives a general condition for the choice of 1) and Xe that gives the right convergence rate time T.
Proposition 3.7. We assume that the event E(ō) from Lemma 3.6 happens. Suppose that for some l < T, there are constants C1, C2 and C3 such that for all 1 <
1. NOn 2L S C1: 2. 1
Ince (2))²
3. ET L (2)
An < Cs: 4. [Vf((x))] < 2/2
Then for all L < 1++
Th [[((z))] + A4H1 S (VAI+2VACH)
2 1=1
for a constant 2 max
64
64
(log
1 + 600 cj
2 + 480 C,
Finally, the proof for Theorem 3.1 is a direct consequence of Proposition 3.7 details to the Appendix.
where we defer the
7

---

Algorithm 2 Clipped-SMD
Parameters: initial point 21, step sizes {ne). clipping parameters {Me), sb is 1-strongly convex wrt
||-ll fort to T do (xx)) = min
} ff(()) 1++1 = arg minsex {Th (V((a)), + Du (1r, ax)
1. [
4 Clipped Stochastic Mirror Descent for Convex Objectives
In this section, we present and analyze the Clipped Stochastic Mirror Descent algorithm (Algorithm 2) under heavy-tailed noise, with general domain and arbitrary norm.
We define the Bregman divergence (w y) - vb(x) - (bv) (Vu(y), - y), where vb Rd R is I-strongly convex differentiable function with respect to the norm ||-|| on X. We assume for convenience that dom (w) = Rd Algorithm 2 is a generalization of Clipped-SGD for convex functions to an arbitrary norm. The only difference from the standard Stochastic Mirror Descent algorithm is the use of the clipped gradient ((+) in place the true stochastic gradient v / (xee when computing the new iterate I
Prior works such as 7 only consider the setting where the global minimizer lies in X. Our algorithm and analysis does not require this restriction and instead only uses the following initial gradient estimate assumption from [22]:
(5) Initial gradient estimate: Let I1 be the initial point. We assume that we have access to an upperbound V of (z1)),,,, i.e. [ I Vi- This assumption is justified as follows. If the noise parameter defined in assumption (3) is known, we can use the procedure of [2]] to estimate [[ we take O (In (1/8)) stochastic gradient samples 21, and let gi be the geometric median of these samples; we then set V == || + 10c. It follows from (21) that | [V(())) S V1 holds with probability at least 1-5. the domain contains the global optimum x² (Vf(x*)
0)
and the initial distance ||æ x²1 is known, we have the following alternative upper bound that follows from fx(x)) and smoothness: f=1))... [(1) Vf(=*) )l. L ||=1 1=|
Convergence guarantees. We first state the convergence guarantee for this algorithm in Theorem 4.1 which works for arbitrary norm and general domain which may not include the global optimum. In this theorem, we assume that we know several problem parameters to show the main idea of our analysis. In Theorem 4.4, we remove the knowledge of the problem parameters.
Theorem 4.1. Assume that convex f satisfies Assumptions (1), (2), (3), (4) and (5). Let 7 max (log }: 1] j; Rı = V/2 ,x1) and assume that V1 is an upper bound of [V For known T, choose de and Tu such that
(207)
1/p
0:2 + VVI)
d x= max
and
R1
R1
26T
-1/P
1
(3LR1 + vi)-1
n 1
min
24
249
7
2
Then with probability at least 1 -
T+1
p-1 Σ A. 48R, max (26 - 1-1 oy : (3LR + +)) 0 (T'
Remark 4.2. This theorem shows that the convergence rate for the known time horizon case is (f. This rate is known to be optimal, matching the lower bounds shown in 22 31 The above guarantee is also adaptive to ar, i.e., when -> O, we obtain the standard (TT-1) convergence rate of deterministic mirror descent.
Remark 4.3. The term V, in the above theorem comes from the inexact estimation of / (V((m)) ll.- we assume that the global optimum lies in the domain X, we can simply select V, LRR, without using the estimation procedure, as discussed in (5).
8

---

In Theorem 4.1 we use the initial distance R1 to the optimal solution to set the step sizes and clipping parameters. This information is generally not available, but can be avoided. For example, for constrained problems where the domain radius is bounded by R, we can replace R1 in Theorem by R without change in the dependency. However, for the general problem, we present Theorem where we do not require knowledge of the constants T,a, 5 or R to set the step sizes and clipping parameters. However, we still need the mild assumption of knowing an upper bound V on [ As discussed in (5), V can be estimated with good accuracy when is known.
4.4
Theorem 4.4. Assume that convex I satisfies Assumption (1), (2), (3), (4) and (5). Let 7 =
max (log J: 1;1;; R1 = -/2 v (x*, ,11), and assume that V1 is an upper bound of [Vi(ll
We choose X and such that
(522(1 + logt)²oz) 1P :2 L Lmax|la; - x1ll + vI) Lei { and
A max
Ci
min (520(L + log logt))(2)
1/p
Les where the absolute constants 01 and are to ensure the correctness of the dimensions. Then, with probability least 8, we have
24x:
24
2 (L maxigi ||xr - x1l + Vi)
1 T+1
8
))²
200)
2
(52T(1+ 1og '0
S
R1 +
? +
max
T
Ta
3
C2
201 3
20
Lei
6 = -
4R +
L
7
2V 1:
Sketch of the analysis. In the remainder of this section, we provide sketch of the analysis for Theorem 4.1 which starts with the following lemma.
Lemma 4.5. Assume that convex f satisfies Assumption (1), (2), (3). (4) and me S म. the iterate
sequence (21))21 output by Algorithm 2 satisfies the following:
T/e A 1 < Dip (x" xx) D (x", II++1 + ne fx= Izz, 0,)) + T/e (x" 2z, 0?)
+ 2 110/11 - E 110:12 F.- + 2n1211 110:12 Fi-1] 2n 110
Remark 4.6. In contrast to Remark 3.4 there is mismatch between the gain D and the loss (x" ze. Or). Since the distance || xtel and the function value gap A, cannot be related in the general convex case, do not obtain the same rate as in the nonconvex case.
We now define the following terms for 2 1:
Ze = 2t
11: A1411 + De (021)))+)= - D (o", 22) 17 (2" - x2, - 2n 10% 10:1.
- 2n/EE 110:1122 FE-1)
3
+ 2422m E |118|112 [Fri]]
8X7
1
where 2ς
2n maxigr / 2D (a", x14 + 16Q
for a constant Q 2 1. We also define S, := Eim Zi. We have the following lemma, which is
analogous to Lemma in the nonconvex case.
Lemma 4.7. For any 8 O, let E(6) be the event that for all 1 S k SKST
A441 + zz De (x" xx411) S 21 DD (x", x1) + log + Σ
2e7l (x Iz, 02)
1=1
1=1
b:
+2
2 |108
Σ
22mm 2 +
3
2422 2
E |100 |10)111FF-11)
8X?
1=1
t=1
(6)
Then Pr [E(8)] > 1-8.

---

Algorithm 3 Clipped-ASMD
Parameters:
initial point y1 21, step sizes {ne). clipping parameters {Ae}, and mirror map ds
where & is 1-strongly convex wrt ||- For t 1 T do:
Set 0; = t+1
2
2t (1 axt) Yt + az
(x+)) - min 1, [ ((rz)
2+1 arg minzEx T (Vf(z)))) + Do (z, (z.
Mr+1 = (1 -ve) Dt + 0.
We now specify the choice of d/e and X The following proposition gives general condition for the choice of 7)t and de that gives the right convergence rate in time
Proposition 4.8. We assume that the event E()) from Lemma 4.7 happens. Suppose that for some 8 < there are constants C2, Cz. Cs, and A such that for all
Aon = Ci; 2. Et ) S SOz 3. Then for all I 182+1
2p
SCs
(
[V 2
Mi M:iii + Di ,x+1) S (Bi 8AC))²²
for max { log 1/2 + 26o 2r
Theorem follows from Proposition 4.8 Both proofs can found in the Appendix.
5 Accelerated Stochastic Mirror Descent and Extensions
In Section the Appendix, we also show the convergence and its analysis for Clipped Accelerated
Stochastic Mirror Descent (Algorithm B. We require the following additional assumption:
(5") Global minimizer: We assume that fx()) = 0.
In other words, we assume that the global minimizer lies the domain of the problem. This assumption is consistent with the works of 7 28) Our analysis readily extends to non-smooth settings, and more generally functions that satisfy f(y) - f(x) & (Vf(z). - x) + G [ly - x|| +
L ly - z||? Yy,r E X. This condition is satisfied by both Lipschitz functions (when L = 0) and 2
smooth functions (when G 0). The key step extend Lemma 4.5 The proof follows from [55 and can be found the Appendix.
6 Conclusion
In this work, we propose a new approach design and analyze various clipped gradient algorithms in the presence of heavy-tailed noise. Our analysis applies to various standard settings, including Clipped-SMD and accelerated Clipped-SMD for convex objectives with general domains and Clipped-SGi for nonconvex objectives, and gives optimal high probability rates in all settings. Our algorithms allow for setting step-sizes and clipping parameters when the time horizon and problem parameters such as the initial distance are unknown. For future work, since our algorithms have the limitation of still requiring the knowledge of parameters like L and p, it is of great interest to investigate the existence of fully-adaptive method, like Adagrad, that converges under heavy-tailed noise without requiring the knowledge of any problem parameter. Finally, it would be interesting to extend our techniques to the setting of variational incqualities under -cavydtailed noise (6).
10

---

Acknowledgement
TDN and AE were supported part by NSF CAREER grant CCF- NSF grant III- 11-19905510, and an Alfred P. Sloan Research Fellowship. THN and HN were supported by NSF CAREER grant CCF-1750716 and NSF grant 2311649.
by
References
[1] Alina Beygelzimer, John Langford. Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
[2] Ashok Cutkosky and Harsh Mchta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883- 4895, 2021.
[3] Kacha Dzhaparidze and JH Van Zanten. On bernstein-type inequalities for martingales. Stochastic processes and their applications, 93(1):109-117, 2001.
[4] David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 18, 1975.
[5] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366) 2013.
[6] Eduard Gorbunov, Marina Danilova, David Dobre, Pavel Dvurechenskii, Alexander Gasnikov, and Gauthier Gidel. Clipped stochastic methods for variational inequalities with heavy-tailed noise. Advances in Neural Information Processing Systems, 55:31319-3133 2022.
[7] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances Neural Information Processing Systems, 33:15042--50533 2020.
[8] Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, and Alexander Gasnikov. Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint 1xXiv22106.05958, 2021.
[9] Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in sgd.
In International Conference on Machine Learning, pages 3964-3975. PMLR, 2021.
[10] Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579-1613. PMLR, 2019.
[11] Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1):2489-551, 2014.
[12] Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. Advances in Neural Information Processing Systems, 21, 2008
[13] Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint 200.03200...3329, 2020.
[14] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming. 133(1):365-33) 2012.
[15] Guanghui Lan. Springer, 2020.
First-order and stochastic optimization methods for machine learning.
[16] Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. International Conference on Machine Learning, pages 12931- 12963. PMLR, 2022.
11

---

[17] Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint arXiv:2007.14294, 2020.
[18] Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Le Nguyen. High probability convergence of stochastic gradient methods. International Conference on Machine Learning, 2023.
[19] Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou. Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2302.06663, 2023.
[20] Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High probability convergence and uniform stability bounds for nonconvex stochastic gradient descent. arXiv preprint arXiv:2006.056100 2020.
[21] Stanislav Minsker. Geometric median and robust estimation banach spaces, Bernoulli, pages 2308-2335 2015.
[22] Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 1079111677 2019.
[23] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-1699 2009.
[24] Danicla A Parletta, Andrea Paudice, Massimiliano Pontil, and Saverio Salzo. High probability bounds for stochastic subgradient schemes with heavy tailed noise. arXiv preprint arXiv:2208.08567. 2022.
[25] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. CoRR, abs/1211.5063, 2(417):1, 2012.
[26] Maxim Raginsky and Alexander Rakhlin. Information complexity of black-hox convex optimization: A new look via feedback information theory. In 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 803-510. IEEE, 2009.
[27] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv: 109.5647, 2011.
(28) Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High- high-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. arXiv preprint 2302.00900, 20293
[29] Umut Şimşekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv: 1912.00012 2019.
[30] Umut Simsckli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. pages 5827-5837, 2019.
[31] Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Conference on Learning Theory, pages 65-102. PMLR, 2022.
[32] Hongjian Wang, Mert Gurbuzbalahan, Lingjiong Zhu, Umut Simsekli, and Murat Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. Advances in Neural Information Processing Systems, 34:1 34:18888 188166888777 2021.
[33] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15399 2020.
[34] Jiujia Zhang and Ashok Cutkosky. Parameter-fres regret in high probability with heavy tails. In Advances in Neural Information Processing Systems, 2022.
12

---

A Freedman's inequality
Lemma A.l (Freedman's 's inequality). Let (X1)a21 be martingale difference sequence. Assume that there exists constant > O such that [Xx] I c almost surely for all t z and define
o7 =
E
x2 X
Xx-1)...,11) Thenfor all > 0, F > 0 and T 2 1
8²
Pr
X
and Σ of S
F
2xxp
2F + 2cb/3
B Missing Proofs from Section
3
Proof of Lemma 3.3 By the smoothness of f and the update 21+1 = 2t 4/
1 fz+z)) we have
f(241))-fG
L < <VV((z)) 21)
2 | xeel ?l
17i (V)(ze). (.(()))))+))))))))){{)))))))){)) + LnZ ()(zz) |
= Th (Vf(xz)) 0, + vf(x,)) + Lin
0 + (x,))
2
Lak
|10,1' 1| Lii [x+)() )1² + Lag (VI(x)), 0z)
n/ [[:)(( 7h (v)(z)), 01) +
2
Luf
LiZ
[[+)(=)))
110.11
(Li) nn) (xx(),, 0.)
1)t 2
Laf
Taf
[V
110.11
(Lnê m) (Vf(x)), 0: + 0?)
11 2
50
Using Stuchy-Schward we have (Vf(z)). 87) S ! ff 1| + 2 ||0;1 Thus, we derive
227
Lmn
Lnn
A+11 4.5
[vf(x)))1
|1,11 + (L m) (V.(=)))
2
2
111 Lnd
[Vf(2a)]1 ?h Lnh |10911
2
2
S N
vf(x,)]1 + Lnf
|10.11 + (Ln² - ni) (V. 67)) + 1h |10811 2
2
2
< ?t
Vf(x;)]] + Luf 110111 + (Lni m. (V fxxx) 07) + (Lii + T/
|10811
2
2
N [V((,)]1 + m |10:11 + (Inξ ne) (xx)), 07) + 3re 2 |,0
2
where the third inequality is due to | < 2 || 12 + 2 |0 and the last inequality is due to
T S 1. Rearranging, adding, and subtracting E |10%| 1| Fi-1) we obtain the lemma.
Detailed proof of Lemma 3.5 We state the following simple properties of the choice of r and À in Theorem 3.1 We have
1(2) P L Sn
1
1
5 L
(8)
T < 32
13

---

TL (4(2)) X2112
A
(10)
2048
We will now prove by induction on N that Ey happens with probability least 1 (N-1)6 For
T
N 1, the event happens with probability 1. Suppose that for some N < Tr [N 2 1- (N 1)
We will prove that Pr [EN+i] 2 1 Ná
T
Since the LHS is non- non-negative, for I N, we have, under the event EN,
b S A1
(Ln)
1))
Σ (f(()))) 07) Lnj
(10811 Ey [1ee:1]]
k-1
3n
Σ 1=1
8
Lnj
E2 |10 ||
= 2A1.
2
we have that for all k S N, A S 2A,. Since the LHS of (5) non-negative, by summing over from N we have,
From the induction hypothesis and Lemma 3.3
37 (xr)), 02)
AN+1 S (1) Lnd")
09.
2
B
Luj²
110% Es [10:112]
Lnj
B2
11::11
The bounds for B and D are straightforward from Lemma 2.1 First, with probability have ||y||| < 2x. By the smoothness of f and the fact that f is bounded below, we have
[V S V2T.A.
Furthermore, when the event Fyy happens, we have
A 5 [V V2LA, SALLA S
Thus, we can apply Lemma 2.1 and obtain ||0b|| S 4aPA1-8 and E, [10011]]] S 40m
Upperbound for B. By
3 when the event Eny happens,
N
B
3n
8
2
3n
160
2-
2
2
s 24T
)
2p
X2 S 24TL (9)"xx
x272 S
34,
256
Upperbound for D.
By
when the event E happens,
N
Ln²
E 100011 < Ln² Σ 22-
< 40 X < 40LT (2) P (2m)
54
256
To bound and C, we use Freedman's inequality (Theorem A.I following random variables
We define, for t 1, the
Vf(x))
if < 24 otherwise.
Z, 0
Thus ||Z,|| / 22/LA for all t.
14

---

(-Vf(z)), we will bound Upperbound for A. Instead of bounding A Ln- E
A' (1) -nn²) Σi (Ze, 0f)). We check the conditions to apply Freedman's inequality. First
Ee [(1- Lnr²) (Ze, 0 = 0. Further, with probability 1, || 2A, and Ze S 2/L thus (1) Li²²) (Z,, 0.) (7 Lnf) [ ||0*|| S 4vT.i (n Ln)) X 4VLāmn Hence,
{(1 -ny²) (Ze; { is a bounded martingale difference sequence. Therefore, for constant a and
F to be chosen we have
N
4T 8
Pr
Σ 1=1
11
(Zz, 04)
> and Σ t=1
E4 [(1 Ln²) (Ze. 02)
S F In
a²
2xp
2F
We choose a such that
a² 2F In
/LAnnda )
2 cxx
AT 8
+
2T
which gives
4
16
4T
V VVVLAI
LAIn
+
+2
In
3
9
8
If we choose F 64LA o p p1,,, we can easily show that
741
Therefore, with
probability least 1 have
74
FA
either A' <
Σ (1 Inp²) (Z,, 03)
S 12
N
4T
or
E, ((n - Ln²) (Ze, 011)
> Fln
8
Also notice that under the event EN. have
N
Es
((1 - Lnd) (Ze, 01
N
NV
<n²
E, [|Zz||² 1100110011 I 2 LA Σ E, [1
1=1
1=1
<64LA p2 p 644, LT (2)²
47 8
(11)
Under EN. we have that Z, (a(()) for all & S N. Therefore, when E n EA happens, we have A = A' < a.
Upperbound for C. We check the conditions
apply Freedman's inequality.
First, E, Lnj² [10 - E. 10:11²
0. Further, with probability 1.
1 1.1
<
2X. thus Ln² [1 E. |1ox
< Lnp² (4X (4X2+x7)) 4X2)
8LX?12
Hence
Tap (1102)1 F, [1
is bounded martingale difference sequence. Applying Freedman's
inequality for constants and G to be chosen, we have
N [1o8i] - E, [109)12] > c and
N
Ex (LnP (1Ør)1 E, [100)1]))²
4T < G
Pr
Lij
8
1=1
c²
< 2exp
ln 4f LA2
15

---

We choose e such that
8
2 exxp
In of + 1 LX2OPC)
2T
which gives
8 +
64L 9
4T
LX
+
2G
In
3
8
If we choose G = 25 simple calculation shows that e < 27. the following event happens
7A. 48
we can show that
with probability at least
Lm Σ (10811 E6 [1091P]]
7
Ec
either Cs
48
Lnn² (10
- Eg [10011]))] 2 GIn
4T
or
Eg
8
Notice that when 2561. 2 20 PI under EN we have
Lnp² (10%11 -Ea [1er:1]])
B
NV
<8LA 7
Es Lnp (100912= Er |1o: 12] (n] S 1622>397 Σ
[10011]
4T <556L PP G GIn 8"
(12)
Therefore, when EN O Eg happens, we have C S c.
Finally, combining all the bounds for A, B, C, D using union bound and selecting À and appropriately to simplify the constants, we obtain the lemma.
Proof of Lemma 3.6
We have
E (exp
(Zi)
[1-1] exp (322 Lnj A. + 6I 2n E |100 Fe-1))
(Li? n.) (VI(I)), 03) + Lid (110:12 - E [108|] F(-1))) F--1]
E
exp
3
(LLM) mh) (x,)) 03) + Lif (102)1 | E |10812  f(=1))) 1=(=1)
exp
I
Zt
4
3
3
1 110:11 (1-1))
exp
IF
2
of
Hi
[x())) 100000110 12 Fー E
(4)
exp
Lz A E 110011
Fイ-1
+
6LL22"1 X/E
1100|11 (r-1))
= exp
(32) Lng A + .9 6L22,
11 F
{イ-1]
For
(a)
Lemma 3.3 For (b) use Lemma 2.2
Notice that
E [(Vf(=;; 0771 E ||o0 - E
| Fe-1] ]] 0,
and since ||0|||| < 2Λ, and [| S V2LA, for an L-smooth function, we have
(L - mt) (VI(x;), 03' + Luf (100)12 |10-|1² 1F-1))=)]]
16

---

22n (V Lif (1051) +E |10413 Fr-1))
2m [x + 8Li X2
S2ncie 2LA, 8LT1 x2.
Thus 2t S 21.2 For (c) we use (a + b)2 _ 2a² + 2b and E [(x - E [x1])²] s
[ For (d), we use [Vf(z)]] 2L and | || - 2A. We obtain
exp (Zi) Fi-1l S 1.
Therefore
E (exp (St)
Fi-1) =x (S R exx (2+) Fi-1] exp (S1-1)
which means (exp (5) is supermartingale. By Ville's inequality, we have, for all l:
Pr Sx log
dE (exp (S1) S 8.
In other words, with probability least
8, for all k: 2
Σ Z. S log ""
Plugging in the definition of Ze we have
1
V
(z 2,)i)
2
t=1
32t/1 ||00|²
log
k
+ Σ
(32f Lık + 61. 6122 + =L E |100112 Fr-1))
Note that we have is a decreasing sequence by construction (see the proof of Proposition 3.7 below). Hence, the LHS of the above inequality can be bounded by
LHS Σ T [V(())) + =AAR+I 21 (#k-1 2k) D
Sil [V + 11
We obtain the desired inequality.
Proof of Proposition We will prove by induction A that
[+ A < (VAI+ (VAi+
The base case 0 trivial. Suppose the statement true for all ( 5 k 5 E. Now we show for k ++1 1. Recall that
2, 2Prpd maxigt VLL + 8Q.
Let us choose
C1 21
P.
d VL
2L
17

---

CVVA Qi = 2
21.
We have
4. 2C max,si VA, 4C7VA
Now, note that (z))22 is a decreasing sequence. By the induction hypothesis maxiç VA, S
V4 + 2VAAC Hence:
2t 201 maxisk V + 407VA
2k 201 maxigı VA, + 4CRVA
20 (VAI + +2VAC) + +4C
s
2C 20IVA1 + 4C7VVA
V AVACI
22
V + 2VAC
By the choice of Xe for all t < k, [s()))] - 2/² we can apply the second part of Lemma 2.1 to obtain
|0:1| S 4 40"
E |108|1 Fe-1] S 40o X?
Thus,
1 k
The [f(x;)]] + zu Ax+1
2k
2
t=1
k Σ
S21 A1 + log
+
32
|1051
2
1=1
(32 A. + 6LL22 22 + Ln E 110011 (F-11)
(=1
20 (2)²²
2p
<2121 + log
+ +24020 20
k
(2)) xxc )
+ 40a
(3ef A. + 627 X3 + +20 Lof X?
Since
St 2, we have
86
Th
[[[[(z))] + Au+1
A1
1
1
1
2p
log
+
480 2p
M
8
26
+ 800 P
Σ
(3z 6 X2 1) LiT X3
1
xx
(a) /A 4VAC1
A 2C1 (VAI+ + +VVAC; log s
1
+ C8
b
L X?
1
VA 2VAC1
xx
3 3VVJi+2VAC;)
6
1 P
+ 800
+
+1
20 (vAI+2VA6
8Q,
t=1
18

---

A 122///VVACA + 2C1 (VAI + +AVACi log x
1
+ 4
3 +[VA++2VA0
+1 7)
:7)c,
+ 800
2C1
<A1 2 2 + 2Ci (VA1 (VAI+AVāC) +Avaci
[08g
1 60o
Cf
486 CC2C3 +4000C33
(0)
VA < + 22 A AVI + 2Ci (VAI+ +VACC)
+ AC?
8
$ (VAi + 2VAC))
For (a), we use ( p
- C2Ln and the induction hypothesis.
For (b), we use
E L xe)
P Ai12 Css and Qi 1. For (c), have
60a VA
log 5 + C7 S 8
480 C2Ca + 140rnCa < AC?
since
60oPO3 Cf
48o 2p OOO + 140oPC3
A 64 log 5 +
+
Cf
This concludes the proof.
Lemma B.1. The choices of ne and de in Theorem 3.1
satisfy the condition (1)-(3) of Proposition
3.7 for
C V
4
1
C2 OF'
A
C 20480PM
Proof. We verify for the first case. The second follows exactly the same. First, have hence
V
2T.
C1.
8VL7
4
1- JATT 3p
Since
8A, . P > 1 and
X; 2
8y VLA,
T Tpp2 P-
n:pp VA,T'S Np11
8VLY
A T 37
8y
T 3- d
8VT7
VLA
o² L
which gives
1
1
<
O2.
Lm
Xx
19

---

Finally, we have d, 2 322/2 o
77 mp-2 hence
1
T S
3208
Therefore,
VATT
T
Σ T
A
8VL
t=1 1
7 Σ
T T.
D1
64In
T
A
T
6472
A
32 647
32d 64
20480aM
Proof of Theorem 3.1 Note that 17 S
T 3p S r. We have that with probability at least 1 - 6,
16.90L7
event E(8) happens. Conditioning on this event, we verify the conditions of Proposition 3.7 We
select the following constants
VAi
A 2048oPP
C
C2
C2=
C3
= 256
4
OP'
We verify in Lemma B.1 that for these choice of constants, conditions (1)-(3) of Proposition 3.7 satisfied. Furthermore, we have
1 +
60pPC3
48o 2 + 1400PC3
64 log
+
8
Ci
1
32
A
A
A
32
64
log g
+ 60 log
+
48
+
140
8 A
2048
2048
2048
A
256y² = A. <
We only need show that, for all (xx))) <
Ay We will show this by induction. Indeed, for
the base case we have || f((i)) I V2L I
21 Suppose that it is true for all t I k. We will and the induction hypothesis
prove that [ < Agt2. By Proposition 3.7
A - (VAI+ (VAI+2VAC;) < (AI+
V 24
167
S 45A1
Thus, we get
AR+1
[ S 22T S 9
< 2
as needed. From Proposition 3.7
we have
[f(x+)]1 + AR41 454
Therefore
T [+((2)))
<
90A1 T/T
720 A mi max
8y VLA
T T 2 I 2
2-26
90
3p
20

---

Theorem B.2, Assume that f satisfies Assumption (1"), (2), (3), (4). Lery = max (log }:1} and
A1 = [(x1)- f For unknown T, we choose X and T) such that
87
26 (1 3p-2 221:2/90 (26 (20 + log t)2) 3p-2
A max
VLAI
-
VDI 2t (1 log t)²)
Then with probability at least 1
{
(VEx)
8y
8
[f((=))) S 720/ 22
(1 log T)
o
p- T Sp
T
2000 (2 + log T)²
T T5p-2 2p
32 (2 log log
3p-2
We again verify the conditions of Proposition 3.7 for the choices of my and X in Theorem B.2
Lemma B.3. The choices of nh and d in Theorem B.2 satisfy the condition (1)-(3) of Proposition
3.7 for
C1 VA
4y 2
C2 Op
C3 2048xP7
The proof utilizes the following fact:
Fact B.4. We have - 20(1+lgg1) 1.
Proof. First, we have p hence
VA 20 (1 + (ogg)))
MAVV2L
V2L
8VTn
1
C₁.
4v 4v2y
14 log (1
Since 1/
-AiT 30
p > 1 and d 2
8y VLAi
(2) + log T
12
V 2t (1 log 1)²)
5p-2
n:2p
Xp-1
8VTn
V
21 (1 log 1)²)
8
5 6 2t (1+lgg))) )
VLA
o²
L
which gives
1
P
1
<
Cz.
Lt
X
σD
21

---

Finally, we have A, 3220 (21 (1 + log 1)2)
3p-2
hence
1
A
21 (1 log ()g (1+gog))))
32n
(13)
Therefore,
T Σ
P
2-20 21 (1 (1+logt) 1ogg)))
VAi
2
L
L
3p-2
xe
8VT.Y
T
1
1
2t (1 + log logt)²)
ap-2
A
21 (1 + +og 1)2
647
1=1
T
1
A
L
(by 13
21 (1 + --oog t)² 32o0 64-2
t=1
A1
1
64n² 32dr
2t (1 + l)gt)²
1=1
A
A
(by Fact F.4)
32
64-²
2048oP7
Proof of Theorem
B.2
Note that
Ai (2t() (1 + logt)))
17
SXeVIr
21 (1 + log 1)²)
16L
1 L
Note that with Lemma B.3 verifying the conditions of Proposition 3.7 is identical to the proof of theorem 3.1 We have that with probability at least 1 8, event E(0) from 3.7 happens. We have with probability at least
[V + AKtI S 45A
Since T7 is decreasing, we have
9011 Tmp
[fx(2))) <
This means that
T
[V 720 A
{
{(>X)
8y
1-
(2 + log 7)2) 35 o
3
T
3 7 T =222 (2g1+log log T)
2 90LD,
+ log (2(++log7)²
22

---

C Missing Proofs from Section
Lemma C.I. Suppose that Tt I t and assume f satisfies Assumption (1), (2), (3) as well as the following condition
f(y) - f(x) S (Vf(z), x) + G
1/2 2
11-=21 Vy. X.
(14)
Then the iterate sequence (11) outpur by Algorithu satiisies the following:
1141 I DD (x", - D (x", xx++1) + The (er 0r) + mh (x" I,,, 0.))
+ + (10111? E |100/12 : F(-1] + 2m E 110:112 1| Fc-1] + 2n/ 110.11 + +2G2m
Proof. By condition and convexity,
(0(+1) (x*) (#141) - (xr) + (f)))((()) (a*)
condition
14
convexity
L
S (x)), - xz) + || - x141 + GGIla [| - x41l + (x,), Iz - xx")
2
I.
(Vf (x:) Je+1 )²)
||,. x++1ll 2
+ + || rt+1ll
2
(0,,,² r+41 + (V - x²) + 2/2 |ل I2t1 + || 2141ll
L
By the optimality condition, we have
no fxx1)x)) + De (2)41,21), - -xe+1) 20
and thus
Th ((()) - x²) s (VaD (I++1, x -z+1)
Note that
(V De (1141, x² - 2141) (11+2) (z)) - 2141)
= Do (x",,e) x1)) - Do 21) - Dy (a" 2142).
Thus
ni (ūf(z)), - -2²) D xz)) - D (x", r1411) - D& (1141,
$ D (x*,.;) - D (a m141) || xell?
where we have used that Du (#141, 2 |++ - xzl 2 by the strong convexity of dh. Combining the two inequalities, and using the assumption that Lmp S 1. we obtain
A.+1 + DV (x",, xz+1) - Di xz))
S 1/. (0,, x= - xe+1) + LTte ||, Fz+1 1| + Gije || - F1+1ll
1
2 | - x211
2
S Tht (Or, xz)) + 17t (Or, Ft - l++1) || - xell2 + Gn 11:r xetill
S Th (0e, x² xz) + v/2 110.13 + 2G
S nh (0) + 8%. x- - 2i) + 2n |10 2 + 2n |0:11 + 2G
This is what we want to show.
Proof of Lemma 4.7
We have
23

---

Fi-1] x exp (6x)
(xX + 2122 R [10r112 1F-11)
E
Texp (2+)
T/ (xt Ix, 0%5) + 2nξ (1081)² |100 l Fz- f(-1)))) Fr-1]
15
18
exp
3
It. 04)) + 2nF (10:1)2 - E |10:11 و =-=))) (1a1))) (5=))))))))))))))))) 26 Th (x*
exp
E
3
2 2 I|x= - -xzell E 10:11 زー-ي + 6=,,1²' B |10:113 11 f1-1))
exp
2 2
2 li ||=" - -zell + +24=/m
3 2.2 2
| F1-1))
exp
(( + 242 E 12 Fe-1)
exp
8X3
For (a), we use Lemma 4.5
For (b), we use Lemma 2.2 Notice that
(xx Fe, 07> E [100 122 E [10:11 Fr-1] 0,
]]
and since |10:11_ S 27,, we have
ne (x* - Ir. 02)) + 2n (10:112 - E [100 11 Fz-1 111
S 3/e ||=0" - xell 10, Il. + 21/ (100112 + E [100 1B Fe-1))
$ Ae 1|00 - x111 + 167/2 x
s 2 / 2D (a*, xx4) 16mz x²
Thus, 21 5
2m 2m v 2D of (x" 11, For (c), use the inequalities (a + b)2 S 2a² + 2b2 and
E (X- - [X)) 2 s E | For (d), we use the fact 110:11 I 4x, to get E |101 1, Fe-1] s
AAZE |10%112 | {c-1] For (e), we use the fact that |10 I 2A₂ and
T) ||== xell
1
2 ||æ0" -xell
21 / 2D v0 (,,,),)))
We obtain E (exp (Zz) [F-1] S 1. Therefore
E [exp (St) Fi-1] = exp (S--1) E (exp (Z,) [i-1] S (S which means (exp (5,))221 is supermartingale. By Ville's inequality, we have, for all k: 2 1
Pr Sx 2 log
< SE (exp (S1) S 8.
In other words, with probability at least - 8, for all l: 2
Σ U1 < log g.
Plugging in the definition of Z, we have
Zx77:
(z Do (x", -x"" (x))
d
k / 110011
< log
Tt7le (x"
Izz 0?)
+
1=1
1=1
24

---

k
3 2Y8
[10:11 Fmml)
220 +
+ +2427
Note that we have 2 is decreasing sequence, hence the LHS of the above inequality can be bounded by
LHS
2071 A441 + 24 D (x", xK+11) - 21 Dv (x", 21) + Σ
22k-1 - 2x De (x", .kk)
t=2
204: + 24 De (x", (x++1) 21 Dv (x", x1).
t=1
We obtain from here the desired inequality.
Proof of Proposition 4.8
We will prove by induction that on k
m: + De (x", xx+1) & (R1 + &8AC,)'
2
The base case h = 0 is trivial. We have D (x", .11
Ri 2
Suppose the statement is true for all
t < & I l. Now, we show for lo + 1. Recall that
2t
2np dr maxigr 2D (x" x.) 16Q X?
Let us choose A >
1. By the induction hypothesis, we have max;51 V 2D xz;) S
R1 + 8AA1, which implies
2TAAA (R1 8AC1) 16A 2C1 (R1 + 16AC1)
For an upperbound, since 22 (x* x1) = R1, we have:
S 2C1 (R1 8AC1))
Since 2i is a decreasing sequence, we have
Zik
Th A+11 + DD (x", S 21 Dv (x",
(,",,1)) x1) + log 5
+ Σ 2071e (x" - Ie, 02) + Σ zoTh 110.13
Σ
22eth 2 +
+
+222 X? E 1100 FF-1))
813
1=1
By the choice of d for all t < k. || f(xe)l.
de, can apply Lemma 2.1 and have
|0%|1. S 40 -PP:
E
10:11: Fr-1]
< 40o X?
Thus, we have
A4t1 + 24 Do (r*,
<z)
De (x. x
loog 1
4
Σ
2 1-p
2 (x*
32 Σ
2 o X; 2p
+ 40 Σ
3
+ 2
o223-0)
8X3
1=1
25

---

1
20 (R, +8401) 00
16Cfo2p
2p
Dx (x", x1) + log
+
8
(R + 8ACI)
Ci (Ri + 8ACI))
+ 40
O7
3
+
6C1
Σ
Ci (Ri + 8ACI)
8
CR + +AAC)²
R
1
20 CrCs
log 0
+ Co +
+ +2o
( Ri + 8AC+)
A
RR [ 8AC7)
+A,
where for the last inequality we use >x (z))² - C2 and (xt)²
2p
So (+))
"
We obtain
* D (00)011)) 20, (R1 + 16AC1)
R²
Th A+1
A
4 + 8ACF)
1A
R2 + CiRi + +AC?
+ + (CiRi + 16ACH)
2
1
< R2 + 16ACR + C
2
1
- 2 (Ri + +
Proof of Theorem 4.1 Note that our choice of 1) ensures 17
R ALR S 1.
4T. We have that with
probability least 1 o, event E(5) happens. Conditioning on this event, in 4.8 we choose
R1
C = 247'
C2 = 2608
C3 = 26T oF
We have
AcT = C1
P
T
1
<
C2
26T
Op
1=11
1m1
2p
1
A
26T
=
COs
Ax
max log 5
1 + Cs +
20 202rCo C2C
< 37 = A.
A
We only need to show that for all
[V < d
We will show this by induction. Indeed, we have
A [ 5
2
Suppose that it is true for all t < k. We prove that
A6+1
[V
By 4.8 we have
|
x²1l S v 2D (x*) S R1 8AC 2
26

---

Thus
- |IV [++(4+)
VS(x*))) + -V/00))
< Lb || =x + L ||0 +V
Ak+1
3LL + VI v 2
as needed. Therefore from Lemma 4.7 we have
A+t + (x", S 2R)
which gives
2R 48R max 266 1 p oy ; + v1)
A S
2=2
Theorem C.2. Assume that I satisfies Assumption (1), (2), (3), (4) and (5). Lety max (log 3: }]
R1 22 s (xx (1) assume that V1 an upper bound of (21))(()l For unknown T, we choose
1/p
52t (1 log logt)²
A max
232(3LR1
Vi)
and
-1/p
R1
R1
52t (1 log t)²
T1 24
min
(3LR) +V1)
247
7
Then with probability at least 1 1-
T T+1
Σ
A. < 48R max 52 2
(1 + log T) or T (3LR + V.)) Ō (r
Proof. We can follow the similar steps. Notice that (n: is a decreasing sequence. We also use Fact
B.4 to verify the second condition of Proposition 4.8 The proof is omitted.
Proof of Theorem 4.4 Note that n, I IT.
We have that with probability at least 1 8, event E()) We choose
happens. Conditioning on this event, 4.8
2n
C
C2
C3 =
A = 7
24'
26c²
52c²
C2
We verify the conditions of Proposition
4.8
den = C
T
T
1
C2
521((1 + log 1)202
260z
2p
C33
Ae
52tc2
Av
A
1 max log 8
202r
26o"C² +
1
max log
+
:
SA,
A
C2
where we have 2 < 20 x 62 < -",
Also, note that
200
09
[Vf(z))l < [ f(())ll. + +IVVf(=))l..
$ L 1| 1ll. |V < X
27

---

Therefore, from Lemma 4.7
we have
T
1
A + Do IT+1) - [8 + +AAG)²
mr
1
20
200
R1
+
2
3
02
which gives
1
2
Ri
+
7
T
2T
C2
t=2
8
+
C1
+
20
2
max
(527(1 + log 7)2()) 110 ;2
L max iST
||:
xill + +i):
Tci
3
Note that
|
xz
||2
z=|1 *1 ||0 2''l
20
2R
+
3 7
C2
which gives us the final convergence rate.
D Clipped Accelerated Stochastic Mirror Descent
In this section, we extend the analysis of Clipped-SMD the case of Clipped Accelerated Stochastic Mirror Descent (Algorithm 3). We will see that the analysis is basically the same with little modification. We present Algorithmß]the clipped version of accelerated stochastic mirror descent (see [13,, where the clipped gradient fxxe is used to update the iterates in place of the stochastic gradient fz1))
We use the following additional assumption:
(5*) Global minimizer: We assume that Vf(x)) O.
Theorem D.I. Assume that I satisfies Assumption (1), (2), (3), (4) and (5'). Let γ max {log i 1]: and R4 /2D v (x* 21).
For known T, we choose a constant and de and np such that
4(T
26T
c = max
104;
LLR
X cR cRigLoc
100 T (66T)
1/p
8
max
6(t+1) 1+1 ?
0 of
1
R1 min
{ [((++))
1+1 (26T) -1/1 0-1 f
1) 3
24y
100 T
Then with probability at least 1 -
f (3r+1) s 6max
{
(267)
p-1
For unknown T, we choose Ct. de and tt such that
4(t+1)
520(1+1og e)2
C = max 104:
7 LL
28

---

1/8
C. Ran
52t (1 log t)²
X
max
8
4(L + 1)
7
-1/0
1
R1 min
4(t + 1) 10 L
(526 + log t)2²
T) 30022
247
7
Then with probability at least 1 - d
(VT+1) - (x*) S max 10 100 (TT 44, (T (T+1)-1 (52r (1 + log 1))
? o} }
Remark D.2. One feature of the accelerated algorithm is the interpolation between the two regimes: When is large, the algorithm achieves the O T - convergence rate, which is the same as unaccelerated algorithms; however, when a sufficiently small, the algorithm achieves the accelerated O 22 rate.
We also start the analysis of accelerated stochastic mirror descent with the following lemma. Lemma D.3. Assume that f satisfies Assumption (1), (2), (3), (4) and n) S 2Lay'' the iterate satisfies the following
sequence (1z))ez outpul by Algorithm
2
The (ʃ (M(+1) - ( To (1 (1-ae) ac) ( (x*)) + D (x", 22441) Do (xt,, (z)) an
04
Smt (0",," ,x 21) + (0%,0* - -2a) + 2nd (110:112 - E |105112 Fi-1)) + 2n 110: + 27 [10:11? Fi-1
Proof of Lemma D.3 We have
f ((++1) f (x*) = f (1++1) - ( (xx) - (x²)
smoothness
convexity
L
S (Vf (Iz) Me+1 -x,) - Il - x1,1?
+ at (V/ (z:) It -x") + (1 a1) (f (x++ - f (x*))
(1 - a.) (V, (Iz), ,3 - 21) ta, (Vf 2111 - x²)
convexity
La 2
+ 2
|| - 2112 + (1- az) (f (x)) - ff(x²))
< (1 az) (f (1i) - f (xx) + (1 an) (f (zx) - f (x*))
La?
+ aa (6,, x²' - 241) + (z)( 2+1 - x² +
|| - 20l1
2
< <(1 - ax) (f (1)) f (x*)) + 1,,I"' - 2+11
La
+ (vi(zz), 2411 - x²) +
|| =z
2
By the optimality condition, we have
(n [xx))) V.D (z++1, 2) - 20
and thus
(1 ((((())) 2411 - 201)))++1-1 x²) S DV (2c+1, - -="= -z41))
Note that
( Do (2441,2),,** - -2+11) = (V (Ze+1) - (x)) - =++1)
= Dr v (x",z)) - D (2411, 2x) - -D (x", 2441).
29

---

Thus
(vf(z)), 2-11 xz) $ Di (a",,) 21) DD (z", 2241) D (264111 2x) The
1
D& (x", 2x) - D (e,,21)))
||20+1 zell
where we have used that Db (2++1, 2x) 2 \ || = by the strong convexity of v.. We have
I (w++1) - 1 (x²) S (1 - at) (ʃ (yi) - [ (x*)) + crt (0,, xx - -2+11
at D (x" 2x) d D (x" 2+11 +
[aa
att
|| - =111
2
2Tp
Dividing both sides by at and using the condition Ln S 1 we have
T (f -f (f D (x", 24+)) D (x",z)
at
(f (f(1) - f (x*)) + Ti (0c, x² - 2x) "e (1 av)
+ me 10 2t 2+11) 1 - Linaa
||2++1 zell
2
(1 an) (5 (v:)) (x*)) + qu 10,, - -2a)
at
n 110e11.
+ 2 (1 Lmaa)
1e (1 an)
(f (y:) - ff (xx)) + no (0) + 00, x²2) -2a
+ 2n 10:11= + 2n |10.12
as needed.
Similarly to the previous section, we define the following variables
Ze 2t
Th
(f (1(+1) - (x*)) ne (1-aa) at)
- (f fxx))) D& (+4) Dw (x*,z))
az
at.
T) (0%, - -2a) -21/ 110 2n 1109113 32-1)
3 8877
+=222 E [108911 [1081121Fe-11 [F-1)]
where 2t 2n maxigi 22D (x xz) + 16Qm
for constant Q 2 1. We also let S E Z, Following the same analysis in previous sections, we can obtain Lemma D.4 and Proposition D.5 for which we will omit the proofs here. The only step we need pay attention when showing Lemma D.4 is when we bound the sum
k
zilk ( (x*)) 2.7 (1 - ass) (f (vr) f (x*))-
If we assume 1--1 m1(1ai)) since 2, is a decreasing sequence and 01 = 0, we can lower bound the above sum by the last term 2all (S (yK+1) I (x*)), which gives the desired inequality.
ax
Lemma D.4. Assume that for all t 2 1, nu satisfies me-1 > me(1-a)) For any 8 > 0, let E(8) be the event that for all 1 < k T
ae11
ag T4 (f (y++1) (2*)) + 24 D (a*))
30

---

*
Dz (x",x1) + logg g
Σ
selle (x" Iz, 02) + Σ uo 110.11
220h + 8X2
3
+ +242/
E 1100 11001111--11
1=1
Then Pr( 2 8.
Finally, we state a general condition for the choice of and A which follows exactly the same as in Proposition 4.8 The proof for Theorem D. is a direct consequence of this.
Proposition D.5. We assume that the event E( from Lemma D..4 happens. Suppose that for some
S T, there are constants C1 and C2 such that for all t S
1. Xon = C₁; 2. Ei (2.)= CC: 3. (2.)
1
Sos (2.); 4. [VV[(=))) S A
Then for all t set1
The
(x")) DD (x", 2411)
1 (Ri 8.AC1)²
at
2
for 2 max { log 2/2 + 260 + 20 11
Proof of Theorem D.1 1. Note that f)t S Lor S 2lor and
12
T|-1
ac-1
8c72L L
Vo (1 or)
(1. + 1) -
8
thus Mt-1
m1(1-a))
We have that with probability at least - 8, event E(5) happens.
0111
ai
Conditioning on this event, in
4.8 We choose
R1
C = 247"
C2
C3
A 3
26g
26T
We can verify the conditions of Proposition D.5 similarly as in previous section for these choices of C1, C22 and Cz.
We will show by induction that for all 2 1. [V 11 x= II} < 2R,. max {||=a x=1l I|, [1v- x1 II,
A
and
2
For L = 1, notice that 21 = 91 21. Thus, we have
|V [|V - V\)()) S LR, S
2
Now assume that the claim holds for 1. k. By Proposition
D.5
we know that
2THx f (1++1) - (x*) ||ak+1 x²1 s 4R²
O
Furthermore
|y x² || 5 (1
ax) 11 -x x + ar || | x S 2R
[x411 - x² < (1 - a+) || xx + au || - x¹1 < 2R
For A 2 we have 0:411
2 < 1; I- = S Ā+ス < 20 and 02 < 3 30z+1 Hence,
x=2
[ < V (xx++1 - Vf(u lll |I ((y++1) - V5 I||
L || 3 1|1 v /2L (J (y)+1) - (x*))
Last1 | - 2k+1
Las
+ +2R11
ax+1
2mp
31

---

3
4L.R1 ak+1
+2
20
Rı Lo
ax+1
2
8yLB10041 + 3 2
o
3 c) P17 $ (8+ + 3/
2
16(8 + 3
(0) A141
S
2c
2
as needed. Therefore, we have
mr
( (yT+1)- (xx))) D (a", xTT+1) 2R}
or
which gives
2R 66 Laeg
ff <
'T
-axx {10*L + 16 1T) (26T) y - of.
Following the similar steps to the proof of Theorem D.1 and noticing that (c+) increasing sequence, we obtain the convergence rate.
32


Reviews:
[{"review_id": "EKHdL4O6TI", "reviewer": "Reviewer_Uh4e", "summary": "In this paper, the authors consider clipped stochastic gradient methods: clipped-SMD in convex case (in non-convex case the y consider clipped-SGD), clipped-ASMD in convex case. They provided improved high-probability convergence analysis, which has some similar steps with analysis from (Gorbunov et.al 2020, Sadiev et.al 2023). Compare to this works, the authors provided analysis in non-Euclidean setup for clipped-SMD, clipped-ASMD. Also, they explain why the proposed approach works better than the previous one. \n\n", "questions": "1.  Could you explain why $z_k$ is decreasing sequence? It is not clear to me. \n2.  About extension to non-smooth setting: How exactly could it be done? According to the proof and the final statement of the main fact about complexity, there is no constant $G$ in the final complexity. Could you comment on it?\n3. The proof via blackbox approach is supported with a lack of explanation for some details, could you provide a full proof or the citation on the same proof technique? It is similar to the proof from the paper of Sadiev et.al, 2023. \n4. Please, could you provide a small explanation for the third inequality in the last chain of inequality on page 19? \n5. For inequality (d) on page 20, you did not write any explanation. Did you forget to do it?\n\nTypos:\n1. On line 204, the first 'are' is not needed.\n2. In eq. (6), it will look better, If '(6)' is on the same row as expression. \n3. On line 430, maybe, it would be better to write 'Lemma 3.2' or 'eq. (5)' instead of 'Lemma 5'\n4. On lines 545 and 612, 'Proposition' is missed before '4.8'. \n\n", "limitations": "There are no limitations. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. A good explanation of the difference between blackbox and whitebox approaches in a detailed way.\n2. The authors provide the convergence analysis of the proposed methods in a non-euclidian setup. \n\nGenerally, the paper is well-written and has good results. ", "weaknesses": "1. There are some issues dealing with clipped-ASMD. At the beginning of the analysis, they consider a more general assumption on the smoothness of $f$. But in the end, they use only standard smoothness assumption. Also, compare to clipped-SMD, they assume that $f(x^*) = 0$.\n2. From my perspective, it would be better, if the proofs of all facts were provided in a more detailed way. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the compliments and feedback. \n\n**Regarding the weakness**: \n\nWe use the general definition to address smoothness and non-smoothness in a unified way. The proofs for the non-smooth case follows very similarly to the smooth case. We give a sketch below in response to the reviewer's second question and will add this case to the revision of the paper.\n\n**We address the reviewer's questions below**:\n\n**Regarding the sequence $z_{t}$**: \nIn Section 3, for example, we should have mentioned that we select the parameters $P_{t},Q_{t},\\eta_{t},\\lambda_{t}$ and ensure that $P_{t}\\eta_{t}\\lambda_{t}$ and $Q_{t}\\eta_{t}^{2}\\lambda_{t}^{2}$ are constants (Line 466). This guarantees that $z_{t}$ is a decreasing sequence. We will make this clear in the revision of the paper.\n\n**Regarding extension to non-smooth setting**: We can proceed similarly to the smooth case. Let $G$ be the Lipschitz constant. Starting with the basic inequality\n\n$\\eta_{t}\\Delta_{t} \\le D_\\psi(x^*,x_t)  -D\\_\\psi(x\\^*,x\\_{t+1}) $ \n\n$\\quad+\\eta_t \\langle x^*-x_t,\\theta_{t}^{u} \\rangle +\\eta_t \\langle x^*-x_t,\\theta_{t}^{b} \\rangle +\\eta_{t}^{2}G^{2}$\n\n$\\quad+2\\eta_t^2 ( ||  \\theta_{t}^{u}||\\_{*}^{2} -E[|| \\theta_{t}^{u}||\\_*^2 | F_{t-1} ] )$\n\n$\\quad+2\\eta_t^2 E[|| \\theta_{t}^{u} || \\_{*}^{2} | F_{t-1} ]+2\\eta_{t}^{2} || \\theta_{t}^{b} ||\\_*^2,$\n\nwe define\n\n$Z_{t} =z_{t}\\big(\\eta_t \\Delta_t -  D_\\psi(x^*,x_t) + D\\_\\psi(x\\^*,x\\_{t+1})$\n\n$\\quad- \\eta_t \\langle x^*-x_t,\\theta_{t}^{b} \\rangle -\\eta_{t}^{2}G^{2}$\n\n$\\quad - 2\\eta_t^2 E[|| \\theta_{t}^{u} || \\_{*}^{2} | F_{t-1} ] -2\\eta_{t}^{2} || \\theta_{t}^{b} ||\\_*^2 \\big) $\n\n$\\quad - (\\frac{3}{8\\lambda_{t}^{2}}+24z_{t}^{2}\\eta_{t}^{4}\\lambda_{t}^{2}) E[ ||  \\theta_{t}^{u}||\\_*^{2} | F_{t-1}] $\n\nwhere \n\n$z_{t}=\\frac{1}{2P_{t}\\eta_{t}\\lambda_{t}\\max_{i\\le t}\\sqrt{2D_\\psi  (x^{*},x_{i})}+16Q_{t}\\eta_{t}^{2}\\lambda_{t}^{2}} $.\n\nFor constants $c_{1}$ and $c_{2}$, in the case of known $T$, we choose \n\n$\\lambda_{t}=\\lambda=\\max \\\\{ 2G, (\\frac{26T}{\\gamma} )^{1/p}\\sigma \\\\} $\n\n$\\eta_{t}=\\eta=\\min \\\\{ \\frac{c_{2}}{G\\sqrt{T}};\\frac{c_{1}}{24\\gamma\\lambda} \\\\} =\\min \\\\{ \\frac{c_{2}}{G\\sqrt{T}};\\frac{c_{1}}{48G\\gamma};\\frac{c_{1}}{24\\gamma}\\left(\\frac{26T}{\\gamma}\\right)^{-1/p}\\sigma^{-1}\\\\} $\n\nand by similar analysis, we have \n\n$\\frac{1}{T}\\sum_{i=1}^{T}\\Delta_{i} \\le\\frac{1}{2}(R_{1}+c_{1}+2c_{2})^{2}\\max\\\\{ \\frac{G}{c_{2}\\sqrt{T}};\\frac{48G\\gamma}{c_{1}T};\\frac{24\\gamma^{\\frac{p-1}{p}}\\cdot26^{1/p}\\sigma}{c_{1}}T^{\\frac{1-p}{p}}\\\\}$.\n\n**Regarding the Blackbox proof**: The proof technique is generally similar to the approaches in Sadiev et al. (2023) and Gorbunov et al. (2020; for noise with bounded variance), so we only provide a sketch in our paper. One important note is that the existing bound in Sadiev et al. (2023) is suboptimal in $T$. In Remark 3.3, we explain the reason for this and how to make the analysis optimal. We will add in the complete analysis for the Blackbox case in our revision.\n\n**Regarding the inequality on page 19**: We use the inequality $ax-x^{2}\\le\\frac{1}{4}a^{2}$. The third inequality of the last chain on page 19 follows from combining two inequalities\n\n$\\eta_{t} \\langle \\theta_{t},x_{t}-x_{t+1} \\rangle -\\frac{1}{4} ||  x_{t+1}-x_{t} ||^{2}  \\le\\eta_{t} ||  \\theta_{t} ||\\_{*} || x_{t}-x_{t+1} ||-\\frac{1}{4} ||  x_{t+1}-x_{t} ||^{2} \\le\\eta_t^2 || \\theta_{t} ||\\_*^2$\n\n$G\\eta_{t} ||  x_{t}-x_{t+1} || -\\frac{1}{2} || x_{t+1}-x_{t} ||^{2}\t\\le 2G^{2}\\eta_{t}^{2}.$\n\n**On Page 20**, we indeed forgot to explain (d), which follows from $|| \\theta_{t}^{u}||\\_{*}^{2}\\le 4\\lambda_{t}^{2}$ (Lemma 2.1, Eq (2)). We apply this on the term $E[ ||\\theta_t^u ||_*^4 ] \\le 4\\lambda_t^2 E [||\\theta_t^u||\\_*^2]$ and obtain (d). We will add this explanation in our next revision."}, {"review_id": "rdlWQ48l7u", "reviewer": "Reviewer_QDgN", "summary": "This paper provides theoretical guarantees for clipped gradient methods in the presence of heavy-tailed gradient noise distributions, where the noise has a bounded $p$th moment for some $1 < p \\leq 2$. The convergence guarantees are established with high probability. The authors' approach distinguishes itself from previous work by deviating from the classical techniques rely on using concentration inequalities coupled with an inductive union bound argument to control the iterates across all iterations. Instead, they bound the moment generating function of a well chosen supermartingale sequence which allows them to enhance the convergence guarantees for a wide range of clipped gradient based algorithm. The authors analyze Clipped-SGD algorithm in the smooth non convex setting, Clipped-SMD and Clipped-ASMD in the smooth convex setting. Specifically the rates they obtain are time-optimal and align with the latest lower-bounds, i.e., respectively $O(T^{\\frac{2-2p}{3p-2}})$, $O(T^{\\frac{1-p}{p}})$ and $O(T^{\\frac{1-p}{p}}\\sigma + T^{-2})$.", "questions": "Q1) Is it possible to extend the \"whitebox\" technic to the analysis of the Clipped-SGD with momentum in the non-convex setting?\n\nQ2) How the studied algorithms compares practically with the parameters in the paper against existing state-of-the-art clipped gradient methods?", "limitations": "I think that the guarantees on the accelerated stochastic mirror descent algorithm should be added to the main body of the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper have a well-written and well-structured presentation. The authors stresses the importance of their work by giving many intuitions on their new proving techniques and give comparisons with related works.  The authors provide guarantees and parameter values for the three algorithms studied in the paper, both for a known time horizon $T$, and an unknown time horizon. The theoretical analysis sounds clear and easy to follow backed with insightful intuitions. The \"whitebox\" technic based on a well chosen supermatingale exhibits potential reusability for addressing other problems.", "weaknesses": "The paper appears to be quite incremental and technical lacking of substantial novel contributions. The three algorithms studied in the paper are already well-established methods, and aside from the application of the \"whitebox\" analysis technique, the convergence analysis for the algorithms follows conventional approaches commonly employed for clipped-gradient-based methods. Furthermore, the analysis of Clipped-SMD heavily depends on the hypothesis that there exists a bound $\\nabla_1$ on the gradient at the initial point i.e., $ \\lVert \\nabla f(x_1) \\rVert_* $ $ \\leq \\nabla_1$. If the optimal point $x_*$ does not lie in the domain $ \\lVert\\nabla f(x_1) \\rVert_*$  can be estimated w.h.p but requires the knowledge of $\\sigma$ which is quite restrictive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and feedbacks.\n\nAs pointed out by reviewer 2mhk, we believe that our paper makes “an important contribution to the stochastic optimization literature”. This includes:\n\n1. Achieving the optimal rates in $T$ in all considered cases, closing the upperbound and lowerbound. Especially in the nonconvex case, we improve the existing bound by $poly\\ T$ factor for $p<2$ (from $O\\left(T^{\\frac{1-p}{p}}\\right)$ in Sadiev et al. to $O\\left(T^{\\frac{2-2p}{3p-2}}\\right)$ in our case). Even if we are willing to suffer $\\log T$ factors, previous techniques only allow us to obtain $O\\left(T^{\\frac{1-p}{p}}\\right)$. Obtaining optimal bounds requires new insights and techniques.\n\n2. Providing an analysis that is applicable generally for known and unknown time horizon. Analysis for the unknown time horizon case has not been achieved before to the best of our knowledge. \n\n3. Showing an approach that works for the general domain (for SMD). Existing analysis only applies for compact or unconstrained problems.\n\nWe would like to stress that the existing approach does not seem to be able to obtain these results. \n\n**Regarding the knowledge of $\\sigma$**: We highlight that existing Clipped-SGD and Clipped-SMD algorithms generally require the knowledge of $\\sigma$ even when the domain is unconstrained and the optimal point lies in the domain. We strictly improve this and only require \\sigma when the optimal point does not lie in the domain.\n\n**Questions**:\n\nQ1) We believe that as long as a high probability analysis relies on a Freedman's type concentration inequality, it would be possible to apply the whitebox approach that to obtain tighter bounds. Clipped-SGD with momentum, such as in Cutkosky & Mehta (2021), can be proved using a Freedman's type concentration inequality, so we think it is possible to extend our techniques to this algorithm.\n\nQ2) Our new analysis of clipped gradient methods are mainly theoretically motivated, so we did not run any numerical analysis. However, we think the performance of the new parameter choices wouldn't differ too much from the state-of-the-art clipped algorithms, because the step sizes and clipping parameters are primarily obtained via hyperparameter tuning in practice."}, {"review_id": "SMUHmj97C3", "reviewer": "Reviewer_d6sm", "summary": "This paper considers the high probability guarantees for clipped stochastic gradient descent with heavy-tailed noise, in the setting of Zhang et al. (2020) where the unbiased gradient noise has finite p-th moments, where $p\\in(1,2]$. The bound obtained in the paper is time-optimal and in the non-convex case, matches the lower bound in the literature. The analysis is based on the novel whitebox approach that analyzes the generating function of a well chosen martingale difference sequence to obtain tighter rates for stochastic gradient methods.", "questions": "(1)\tOn page 3, you cited some works about high probability convergence for noises with bounded variance and heavy tails. Are there some works on unbounded variance that you can cite?\n(2)\tOn page 6, line 234, can you provide a reference to Ville’s inequality?", "limitations": "I did not see such discussions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The bound obtained in the paper is time-optimal and in the non-convex case, matches the lower bound in the literature. \n\nThe analysis has technical novelty that involves analyzing the generating function of a well chosen martingale difference sequence to obtain tighter rates for stochastic gradient methods.", "weaknesses": "In terms of weakness, I think the first weakness is that some of the model assumptions seem to be very strong. For example, it is assumed that $\\mathbb{E}[\\Vert\\hat{\\nabla}f(x)-\\nabla f(x)\\Vert_{\\ast}^{p}|x]\\leq\\sigma^{p}$. This assumption does not seem to hold in the simple setting of mini-batch. Is it possible to extend your analysis to allow the relaxation of this assumption to something like $\\mathbb{E}[\\Vert\\hat{\\nabla}f(x)-\\nabla f(x)\\Vert_{\\ast}^{p}|x]\\leq\\sigma^{p}(1+\\Vert x\\Vert^{q})$ where $q$ can be related to $p$?\n\nIn your main result, i.e. Theorem 3.1., you mainly discuss the dependence on time $T$. What you obtained is $O(T^{\\frac{2-2p}{3p-2}})$. However, there are other terms with explicit constants in your bound, and how does your bound depend on $p$? Does it have monotonic dependence on $p\\in(1,2]$ or not? It seems to me that as $p\\rightarrow 1$, the upper bound you have depends on whether $8\\gamma/\\sqrt{L\\Delta_1}}$ and $\\sigma$ are bigger than $1$ or smaller than $1$ and you will get very different results in these two cases. Is this something you expected and is there any intuition behind it?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments.\n\n**Regarding the assumption** $E [ ||\\widehat{\\nabla}f(x)-\\nabla f(x)||\\_*^p | x ]\\le\\sigma^{p}$:  \n\nThe reviewer is correct that in the small mini-batch setting, the variance may not be bounded. The assumption to the bounded $p$-th moments is a step towards relaxing the bounded variance assumption, and this is motivated by observation in practice (see Zhang et al. (2020) and our literature review). All prior works in the literature of heavy-tailed noise make this assumption. For example, this assumption is used in Gorbunov et al. (2020), for $p=2$ (the strongest case), or Zhang et al. (2020) and Sadiev et al. (2023) (the same assumption). Cutkosky & Mehta (2021) use this assumption in addition to another assumption that $E[||\\widehat{\\nabla}f(x)||\\_*^p | x ]\\le G^p$. We also think that relaxing this assumption, such as to $E[||\\widehat{\\nabla}f(x)-\\nabla f(x)||\\_*^p | x ]\\le \\sigma^{p}(1+||x||^q)$, is an important and interesting question to study in the future. \n\n**Regarding the dependency on $p$**: \n\nGenerally $p$ is treated as a fixed problem parameter, and as the reviewer suggest, the dependency on p of the constants in front is not necessarily monotonic, but depends on the regime. What we care most about  in our paper is the exponent of $T$. This is monotonic in $p$. \n\n**Questions**:\n\n1. Among the works we cited, Sadiev et al. [27] and Liu et al. [18] consider the unbounded variance case (ie, the assumption, $E [ ||\\widehat{\\nabla}f(x)-\\nabla f(x)||\\_*^p | x ]\\le\\sigma^{p}$ for $1<p\\le2$).\n\n2. Ville's inequality is a classic inequality (Ville, 1939). See, for example, the Wikipedia page for Ville's inequality and references therein. \n\nReference:\n\nVille, J. (1939), Etude Critique de la Notion de Collectif., Gauthier-Villars, Paris."}, {"review_id": "TOSELfwMco", "reviewer": "Reviewer_2mhk", "summary": "The paper addresses the problem of deriving high-probability complexity bounds for the convex and non-convex optimization problems on closed convex sets under the assumption that the noise in the stochastic gradient has bounded $p$th moment for some $1<p\\leq 2$. The key feature of the results is that they have improved dependence on the failure probability $\\delta$ in comparison to the prior works. In the convex case, the authors also consider non-Euclidean norms, Clipped Stochastic Mirror Descent, and its accelerated version. Overall, the results are good and very relevant for the community.", "questions": "1. Line 39, \"where the convergence rate depends on...\": the work [32] does not have high-probability results. Do you mean that one can get such results from the results of [32] using Markov's inequality?\n\n2. Line 165, \" The proof can be found in, for example, Lemma 1 of [16]\": It seems that the reference is not accurate (I did not find this result in the mentioned paper).\n\n3. Lines 447-448: what is $A'$?\n\n4. Line 480: what is the first case?\n\n5. I believe authors should provide the missing proofs (I mentioned them in the Weaknesses section).\n\n### Minor\n\n1. Line 204: step sizes are $\\eta_t$ are fixed $\\to$ step sizes $\\eta_t$ are fixed\n\n2. Lemma 3.4: the summation is forgotten in the third term of the main inequality.\n\n3. Line 430: should be Lemma 3.2 instead of Lemma 5\n\n4. Line 439: the second inequality holds with probability strictly smaller than $1$\n\n5. Lines 484-485, second and third rows: should be $\\lambda$ instead of $\\lambda_t$.\n\n6. Line 487: Lemma 3.6 $\\to$ Proposition 3.6\n\n7. After line 488, definitions of $C_2$ and $C_3$: should be \"$=$\" instead of \"$\\leq$\".\n\n8. After line 493: after the first inequality the square is missing.", "limitations": "The authors address the limitations of their work in detail.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Improved dependence on $\\delta$ in the convex case.** Previous works addressing similar setups provide complexity results that depend on $\\delta$ as $\\log(1/(\\varepsilon\\delta))$ while the rates derived in this work (in the convex case, for known horizon) for Clipped-SMD and Clipped-ASMD imply the complexities that are proportional to $\\log(1/\\delta)$. Although this affects only the logarithmic term, I believe it is an important contribution to the stochastic optimization literature. In particular, this requires applying the proof technique (without induction argument) that differs from the existing approaches.\n\n2. **Constrained case for Clipped-SGD and non-Euclidean prox-structure.** This works provides high-probability convergence analysis for the constrained problems for the first time without the bounded variance assumption. Moreover, it provides an extension to the non-Euclidean case. This is an important step forward.\n\n3. **Horizon-independent results.** The authors also provide results that are independent of the time horizon $T$, while the previous works explicitly use $T$ to choose the parameters of the methods.\n\n4. The paper is well-written. I did not find any serious issues in the proofs.\n", "weaknesses": "1. **Deterministic term and logarithms in the results for the non-convex case.** Although the dominating terms (that contain $\\sigma$) has optimal dependence on $T$, the deterministic term (the one that does not depend on $\\sigma$) is $O(T^{\\frac{1-2p}{3p-2}})$ that is not optimal for the deterministic case: it becomes worse when $p \\to 1$, while should be $O(T^{-1})$ as for Gradient Descent.  Such a $O(T^{-1})$ deterministic term can be achieved (e.g., see Sadiev et al. (2023)). Next, the improvement of the logarithmic factor is not that evident: while under the logarithm, there is no $T$ anymore, the power of the logarithm increases. In particular, the first term in the rate from Theorem 3.1 is proportional to $\\gamma^{\\frac{p}{p-1}} \\geq \\gamma^2$. If one wants to achieve $\\frac{1}{T}\\sum_{t=1}^T \\|\\nabla f(x_t)\\|^2 \\leq \\varepsilon$, then according to Theorem 3.1, the complexity bound will have a term proportional to $O(\\frac{\\log^{\\frac{p(3p-2)}{2p-2}}\\frac{1}{\\delta}}{\\varepsilon^{\\frac{3p-2}{2p-2}}})$. In the best case (when $p=2$), this equals to $O(\\frac{\\log^{4}\\frac{1}{\\delta}}{\\varepsilon^2})$. The corresponding term from (Sadiev et al., 2023) is $O(\\frac{\\log\\frac{1}{\\delta\\varepsilon^2}}{\\varepsilon^2})$. When both $\\delta$ and $\\varepsilon$ are small, $\\log\\frac{1}{\\delta\\varepsilon^2}$ can be much smaller than $\\log^{4}\\frac{1}{\\delta}$. I believe this should be discussed in the paper, and a fair comparison should be provided.\n\n2. **Logarithms in the horizon-independent results.** When $T$ is unknown, the results become worse by a polynomial factor of $\\log T$ that also spoils the complexity even in the convex case (and worse than for the case of known $T$ in the prior works).\n\n3. **Some parts of the proofs are not finished.** The proof of Lemma 3.4 is not finished. Next, although the result is believable, the proof of Theorem B.2 is not complete as well. The authors should at least provide a more detailed sketch explicitly pointing to the places that will be changed and how.\n\n4. **Results for the accelerated method requires $\\nabla f(x^\\ast) = 0$.** When the gradient at the solution equals zero, then the problem becomes almost an unconstrained one. (in terms of the analysis). The authors should indicate in the main text that the accelerated algorithm is analyzed under this additional assumption. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank we reviewer for pointing out the significance of our contributions and for the detailed review. \n\n**Regarding the deterministic term**: The power of T in the term is $O\\left(T^{\\frac{1-2p}{3p-2}}\\right)$. We can see that as $p\\to1$ the rate becomes precisely $O\\left(T^{-1}\\right)$, which is the rate of gradient descent.\n\n**Regarding the comparison with Sadiev et al. (2023) in the nonconvex case**: In fact, Sadiev et al. (2023) achieve a rate with a significant suboptimal dependency on $T$, namely $O\\left(T^{\\frac{1-p}{p}}\\right)$, while we achieve the optimal bound $O\\left(T^{\\frac{2-2p}{3p-2}}\\right)$. This is a $poly\\ T$ improvement for $p<2$, which vastly dominates the $\\log T $ terms arising from the higher dependence on $\\log(1/\\delta)$. The reviewer is right that our dependence on $\\log(1/\\delta)$ is slightly higher in the very small $\\delta$ regime and we will discuss this in the next revision.\n\n**For the unknown $T$**: Thank you for pointing out the gap between known $T$ and unknown $T$. We agree that removing the extra $\\log T$ for unknown $T$ is an interesting question. Indeed, this remains open even under the more restrictive sub-gaussian noise assumption instead of heavy-tailed noise.\n\n**Regarding the incomplete proofs**: We thought some of these steps can be derived similarly to other proofs in our paper or cited ones, so we left some details out for the conciseness of the paper. We will add in more details in the revision of the paper.\n\n**Regarding the accelerated algorithm**: We will add this additional assumption in the main text.\n\n**Question**:\n\n1. Line 39: Yes, we try to convey that one can obtain a probability bound from in-expectation bound using Markov inequality.\n\n2. Line 165: Indeed, the reference is not correct. The correct reference is should be Beygelzimer et al. (2011), in the proof of Theorem 1 Eq. (1)-(3).\n\n3. Lines 447-448: We define $A'$ in Line 441 as a proxy for $A$, using the variables $Z_{t}$.\n\n4. Line 480: The first case here we meant the case for known $T$. We forgot to rewrite this part when moving some of the theorems and proofs to the appendix. The proof for Lemma B1 is complete.\n\n5. We will add in the missing details for the incomplete proofs in the next revision.\n\nFinally, thank you for the attention to details and catching some typos. We will fix these in our revision.\n\nReferences:\n\nBeygelzimer, A., Langford, J., Li, L., Reyzin, L., & Schapire, R. (2011, June). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (pp. 19-26). JMLR Workshop and Conference Proceedings."}, {"review_id": "7XFZpaFo9r", "reviewer": "Reviewer_bwSN", "summary": "The author(s) proposed an improved convergence analysis of clipped gradient descent with heavey tail noise. By the improved analysis, the author(s) can either improved the logarithmic dependency of $T$ or relax the known time horizon assumption.", "questions": "- Ling 190, there is no $ \\langle \\nabla f(x_t), \\theta_t \\rangle $ in equation (5), is this a typo?", "limitations": "I do not find any nagative social impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The author(s) proposed a new analysis framework for the high-probability error bound of clipped SGD with heavy-tail noise. The analysis is different from the classic Freedman concentration analysis, and can be used in more flexible settings compared to previous analysis, e.g., unknown time horizon, the new analysis also results in slightly better dependency of $T$.\n- The writing is clear and easy to follow.\n- Related works are well-addressed to my knowledge.\n- Overall, I think this paper makes a decent contribution to the field if all other reviewers believe the proof is correct.", "weaknesses": "- It is better to include a table to compare with prior works in terms of the convegence rate and the assumptions being used. So readers can better understand the position of this work in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We will add a table in the revision of the paper. \n\nIn Line 190: The term $\\left\\langle \\nabla f(x_{t}),\\theta_{t}\\right\\rangle$  does not appear in Eq (5) because we have decompose it into $\\left\\langle \\nabla f(x_{t}),\\theta_{t}^{u}\\right\\rangle +\\left\\langle \\nabla f(x_{t}),\\theta_{t}^{b}\\right\\rangle$. We next explain how treating the term $\\left\\langle \\nabla f(x_{t}),\\theta_{t}^{b}\\right\\rangle$ more carefully can give us the optimal rate."}]

Author rebuttal:

Meta-review: All reviewers suggested acceptance and there is hence full consensus on the recommendation. I concur. There is no reason to be verbose in this metareview -- it is enough to refer to the original reviews. Congratulations on a nice paper.
Decision: Accept (spotlight)