Parameter-free Regret in High Probability with Heavy Tails
Authors: Jiujia Zhang
Ashok Cutkosky
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online learning
Parameter-free
Online Convex Optimization
Heavy tails
Regularization

Abstract: We present new algorithms for online convex optimization over unbounded domains that obtain parameter-free regret in high-probability given access only to potentially heavy-tailed subgradient estimates. Previous work in unbounded domains con- siders only in-expectation results for sub-exponential subgradients. Unlike in the bounded domain case, we cannot rely on straight-forward martingale concentration due to exponentially large iterates produced by the algorithm. We develop new regularization techniques to overcome these problems. Overall, with probability at most δ, for all comparators u our algorithm achieves regret O ̃(∥u∥T 1/p log(1/δ)) for subgradients with bounded pth moments for some p ∈ (1, 2].

Parameter-free Regret in High Probability with Heavy Tails
Jiujia Zhang Electrical and Computer Engineering
Ashok Cutkosky
Electrical and Computer Engineering
Boston University jiujia i @bu. @b...uuuuue. edd
Boston University ashok@cutkose com
Abstract
We present new algorithms for online convex optimization over unbounded domains that obtain parameter-free regret in high-probability given access only to potentially heavy-tailed subgradient estimates. Previous work unbounded domains con- siders only in- in-execcaation results for sub- sub-exponential subgradients. Unlike in the bounded domain case, we cannot rely on straight-forwe forward martingale concentration due to exponentially large iterates produced by the algorithm. We develop new regularization techniques to overcome these problems. Overall, with probability most 6, for all comparators our algorithm achieves regret O[[uu||T!/ log(1/8)) for subgradients with bounded tt moments for some p (1,2).
Introduction
In this paper, we consider the problem online learning with convex losses, also called online convex optimization, with heavy-tailed stochastic subgradients. In the classical online convex optimization setting, given a convex set W, learning algorithm must repeatedly output a vector w, E W, and then observe convex loss function 4, W -> R and incur loss of (w,)). After T such rounds, the algorithm's 's quality is measured by the regret with respect to a fixed competitor u E W:
T
T
( = Σ ((w.)) - Σ (u)
1=1
1=1
Online convex optimization is widely applicable, and has been used to design popular stochastic optimization algorithms (Duchi al. 2010a Kingma and Ba 2014 Reddi al. 2018). ) for control
of linear dynamical systems [Agaraal et all 2019), or even building concentration inequalities [Vovk]
2007 Waudby-Smith and Ramdas 2020 Orabona and Jun 2021
popular approach to this problem reduces it to online linear optimization (OLO): if g: subgradient of & at wt, then Rr (u) < Ei= (gr, W, u) so that it suffices to design an algorithm that considers only linear losses
(gt; w). Then, by assuming that the domain W has some finite diameter D, standard arguments show that online gradient descent [Zinkevich] (003) and its variants
achieve (u) < ((DTT) for all u E W. See the excellent books Besa--Bannchi and Lugosi 2006). Shalev-Shwartz [201]] Hazan 2019) Orabona 2019 for more detail.
Deviating from the classical setting, we study the more difficult case in which, (1) the domain W may have infinite diameter (such W = Rdd,, and (2) instead of observing the loss f, the algorithm is presented only with a potentially heavy-tailed stochastic subgradient estimate g: with Elg./wa we] E de, (w.).. Our goal is develop algorithms that, with high probability, obtain essentially the same regret bound that would be achievable even if the full information was available.
Considering only the setting of infinite diameter W with exact subgradients E (w.),, past work has achieved bounds of the form (u) Ō + ||u|| VT) for all u E W simultancously for any
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Orabona and Pál Chen et al. As such algorithms do not require knowledge of the norm | that is usually used to specify a learning rate for gradient descent, we will call them parameter-free. Note that such algorithms typically guarantee constant (0), which is not achieved by any known form of gradient descent.
user- user- seer-specifie directly generalizing the O(DVT) rate available when D < 0o
2016
Cutkosky and Orabona, 2018 Foster al., 2017 Mhammedi and Koolen C
2021
While parameter-free algorithms appear to fully generalize the finite-diameter case, they fall short when is stochastic subgradient estimate. In particular, lower-bounds suggest that parameter-free algorithms must require Lipschitz& & [Cutkosky and Boahen 2017). which means that care must be taken when using ge with unbounded noise as this may make 2, "appear" to be non-Lipschitz. In the case of -ub-exponential ge. ge.Dun and Orabonal 2019), vvnn der Hoeven 2019) provide parameter- free algorithms that achieve (u)) S O( + (ullTT), but these techniques do not easily extend to heavy-tailed g: or to high-probabilityy bounds. The high-pre sroh-probbbility statement is particularly elusive (even with sub-exponential g:) because standard martingale concentration approaches appear to fail spectacularly. This failure may be counterintuitive: for finite diameter W, one can observe that (g. E gr), W, - uj forms a martingale difference sequence with variance determined by [[,, ull < D. which allows for relatively straightforward high-probability bounds. However, parameter- free algorithms typically exhibit exponentially growing || |/ell in order to compete with all possible scales of |ulll, which appears to stymie such arguments.
Our work overcomes these issues. Requiring only that g: have a bounded pth moment for some p (1, we devise new algorithm whose regret with probability at least 1 - 8 is ( S Ō(e+ u T log(1/ (1/8)) for all u simultancously. The T2/P dependency is unimprovable Bubeck et al. [213), Vural et al. [2022]. Moreover, we achieve these results simply by adding novel and the losses l, in way that converts any parameter- algorithm with sufficiently small regret into one with the desired high probability guarantee.
carefully designed regularizers
Motivation: High- bighh-probability analysis is appealing since it provides confidence guarantee for an algorithm over a single run. This is crucially important in the online setting in which we must make irrevocable decisions. is also important in the standard stochastic optimization setting encountered throughout machine learning as it ensures that even a single potentially very expensive training run will produce good result. (See Harvey al. 2019) Li and Orabona (2020). |Madden al.) 20200] Kavis et al. [2022] for more discussion on the importance of high-probability bounds.) This goal naturally synergizes with the overall objective of parameter-free algorithms, which attempt to provide the best-tuned performance after a single pass over the data. In addition, we consider the presence of heavy-tailed stochastic gradients. which are empirically observed in large neural network architectures Zhang et al. [2020). Zhou et al. [2220]
Contribution and Organization: After formally introducing and discussing our setup in Sections 2
we then proceed to conduct an initial analysis for the 1-D case W = IR in 3 First (Section we introduce a parameter-free algorithm for sub-exponential that achieves regret Ö(E + |u[v/] in high probability. This already improves significantly on prior work, and is accomplished by introducing a novel regularizer that "cancels" some unbounded martingale concentration terms, technique that may have wider application. Secondly (Section 5 we extend to heavy-tailed ge by employing clipping, which has been used in prior work on optimization [Bubeck et al. 2013) Gorbunov et al., 2020, Zhang et al., 2020 Cutkosky and Mehta 2021] to convert heavy-tailed estimates into sub- exponential ones. This clipping introduces some bias that must be carefully offset by yet another novel regularization (which may again be of independent interest) in order to yield our final Ö(E + /u[ parameter-free regret guarantee. Finally (Section we extend arbitrary dimensions via the reduction from Cutkosky and Orabona 2018
2 Preliminaries
Our algorithms interact with an adversary in which for t 1...T the algorithm first outputs a vector w, E W for W a convex subset of some real Hilbert space, and then the adversary chooses a convex and G-Lipschitz loss function & : W + R and a distribution P. such that for ge ~ P,, Elg.] E ae, (w:) and Ellg: - Egg(l1)) < aP for some E (1, 2). The algorithm then observes a random sample g: ~ Pt. After t rounds, we compute the regret, which is a function
(u) = Ei= ((w,)- - (u). Our goal is to guarantee Rr( S e + (([u)]]T//)) for all simultancously with high probability.
2

---

Throughout this paper we will employ the notion of mub-exponential random sequence:
Definition 1. Suppose {X,} J is a sequence of random variables adapted to a filtration Fe such that {Xt, Fi) is martingale difference sequence. Further, suppose {or, ba] are random variables such that ot, by are both -r-e-mmuuurable for all L. Then, {Xt, Fe} is for, by} sub-exponential if
B(cxp(XX.)FF-11 exp(X2o7/2)
almost everywhere for all Ft- 11-1meaaurrblle satisfying < 1/b.-
We drop the subscript when have uniform (not time-varying) sub-exponential parameters (o, b)- We use bold font (g:) ) to refer to vectors and normal font (gt) to refer to scalars. Occasionally, we abuse notation to write (&g(w;) for an arbitrary element (w,))
We present results using O() to hide constant factors, and (-)) to hide log factors (such some power of log 7 dependence) in the main text, the exact results are left at the last line of the proof for interested readers.
Finally, observe that by the wwwnsstrannedtt-oosttrriiii conversion of Cutkosky and Orabonal 2018 need only consider the case that W is entire vector space. By solving the problem for this case, the reduction implics a nigh-probabillin regret algorithm for any convex W.
Challenges
A reader experienced with high probability bounds in online optimization may suspect that one could apply fairly standard approaches such as gradient clipping and martingale concentration to easily achieve high probability bounds with heavy tails. While such techniques do appear in our development, the story is far from straightforward. In this section, we will outline these non-intuitive difficulties. For a further discussion, see Section 3 of Jun and Orabonal (2019)
For simplicity, consider wi E R. Before attempting a high probability bound, one may try to derive regret bound in expectation with heavy-tailed (or even light-tailed) gradient 9: via the following calculation:
E. (( (w)) = Ee(mx) Es(u)
Σ E Kot w. ui] + Σ E (Vle(w:) - gt, W2 u))
The second sum from above vanishes, so is tempted to send gr. directly some existing parameter- free algorithm to obtain low regret. Unfortunately, most parameter-free free algorithms require uniform bound on [9:1 even single bound-violating dr could be catastrophic [Cutkosky and Boahen 2017]. With heavy-tailed St. we are quite likely to encounter such a bound-violating St. for any reasonable uniform bound. In fact, the issue is difficult even for light-tailed gr, described in detail by Jun and Orabonal 2019
A natural approach to overcome this uniform bound issue is to incorporate some form of clipping, commonly used technique controlling for heavy-tailed subgradients. The clipped subgradient ge defined below with positive clipping parameter as:
9t min(T, (g:l)
g.
9.
If we run algorithms on uniformly bounded 9r instead, the expected regret can now be written as:
T
T
T
[[(r((u) < E Krc. we - u)]
Σ
+
E (E - Gr, we 4i]
E (VV - E[or], we u)]
parameter-frce regret
martingale concentration?
(1)
Since lpx| T, the first term can fact be controlled for appropriate t at a rate of Ò + (ulvT)
using sufficiently advanced parameter-free algorithms (e.g. Cutkkoky and Orabona 2018 ). However,
now bias accumulates in the last term, which difficult bound due to the dependency on wy- On the surface, understanding this dependency appears to require detailed (and difficult) analysis of the
3

---

dynamics of the parameter-free algorithm. In fact, from naive inspection of the updates for standard parameter-free algorithms, one expects that |nm] could actually grow exponentially fast in t, leading to very large bias term.
Finally, disregarding these challenges faced even in expectation, derive a high-probabillity bound the natural approach is to bound the middle sum in ① via some martingale concentration argument. Unfortunately, the variance process for this martingale depends on Wy just like the bias term. In fact, this issue appears even if the original Or already have bounded norm, which is the most extreme version of light tails! Thus, we again appear to encounter a need for small w,, which may instead grow exponentially. In summary, the unbounded nature of w, makes dealing with any kind of stochasticity in the Si very difficult. In this work we will develop techniques based on regularization that intuitively force the wa to behave well, eventually enabling our high- prtttbioobbbtyyy regret bounds.
4 Bounded Sub-exponential Noise via Cancellation
In this section, we describe how to obtain regret bound in high probability for stochastic subgradients Ii for which E Eggg]] S o² and |ge| < b for some a and b (in particular, dr exhibits (a, 4b) sub- exponential noise). We focus on the 1-dimensional case with W = R. The extension to more general W is covered in Section Our method involves two coordinated techniques. First, we introduce carefully designed regularizer dht such that any algorithm that achieves low regret with respect to the losses w + g.w + (w) will automatically ensure low regret with high probability on the original losses 4. Unfortunately, th1 is not Lipschitz and so it is still not obvious how to obtain low regret. We overcome this final issue by an "implicit" modification of the optimistic parameter-fre algorithm of Cutkosky 2019]. Our overall goal a regret bound of Rr (u) S Ö( [ul + G) + blul) for all u with high probability. Note that with this bound, can be O(vT) before it becomes a significant factor in the regret.
Let us proceed to sketch the first (and most critical) part of this procedure: Define e, V(g(w,) 9t- so that e, captures the "noise" in the gradient estimate 9t. In this section, we assume that E, is (o, 4b) sub-exponential for all t for some given o, b and [gc| S b. Then we can write:
T
T
T
T
RT(
S
Vle (w,), We - u)
Σ
(gt,
Wi - u) + Σ (es wi)
(an u) [=]
tm
T (g, We ---
+
Σ Gewe + |ul
"noise term", NoISE
Now, the natural strategy is to run an OLO algorithm A on the observed Jt, which will obtain some regret (u) = =I= (9t, wi- u). and then show that the remaining NOISE terms are small. To this end, from sub-exponential martingale concentration, we might hope to show that with probability 1 5, we have an identity similar to:
T
NOISE S a
Σ : log(1/6) + bmax we (log(11)) + (1/g///)))))/)) + lulblog(1/8)
The dependency of [u] above appears to be relatively innocuous as it only contributes O(uu + ju(b) to the regret. The wy wy-dependent term is more difficult as it involves dependency on the algorithm A. This captures the complexity of our unbounded setting: in a bounded domain, the situation is far simpler as we can uniformly bound |wy| < D, ideally leaving us with an Ō(DVT) bound overall.
Unfortunately, in the unconstrained case, |wy| could grow exponentially (wull ~ 2-) even when is very small, so we cannot rely on a uniform bound. In fact, even in the finite-diameter case, if we wish to guarantee (O) S <, the bound |w,| < D is still too coarse. The resolution is to instead feed the algorithm A a regularized loss (w) = (gt, w) + ve(w), where vi2 will "cancel" the we dependency in the martingale concentration. That is, now define RT(()) = =-=(((w ke(we) - (u)

---

and rearrange:
r
Ot wh u) RV
(vee))))) +
Σ (u)
(3)
t=1
And now combine equations
and 3
RT(u)= S RT(
(w))
(b(()) NOISE
T
I R to
Σ
w/ log(1/6) + bax way (1/5)
Σ (r()))))
T
/ (log(11)) + lulblog(1/8) + Σ (u)
(4)
From this, we can read off the desired properties of s/e (1) the should be large enough that Eim (w() 2 o oVEr w 11/(1 + max, |my, log(1/8), (2) the should be small enough that E.= (u) < O()ulVT), and (3) the should be such that (²) Ō(E + lulvT) for an appropriate algorithm A. If we can exhibit the satisfying all three properties, we will have developed a regret bound of Ō + |u| VT) in high probability.
It turns out that the modified Huber loss (x(w) defined in equation 5 and 6 with appropriately chosen constants 61, C2 PI, P2, 01, 02 satisfies criterion (1) and (2).
c (plu) (p 1) (E |w, +
[w]
|
Te(w;; c, on) =
(5)
c/wll (: lw, #+a5)1-1/p1
w
[
(w) reww; c1, PI, a1) + re 02 P2.
(6)
Let us take a moment to gain some intuition for these functions and th. First, observe that Ta always continuously differentiable, and that r; 's definition requires knowledge of wy. This is acceptable because online learning algorithms must be able to handle even adaptively chosen losses. In particular, consider the p = case, re(w;; c, 2, a) for some positive constants and a. We plot this function in Figure D where one can see that T, grows quadratically for |w] < |wy/. but grows only linearly afterwards so that r is Lipschitz.
Eventually, in Lemma 1 we will show that this func- tions satisfies
20-
2, 2 c
Σ m
00N.1 ddw.1.2.3 2.33
15
1.0
Σ t=1
Ö(uVT)
that for appropriate choice of and re e, will cancel the O O(VE"" wf) mar- tingale concentration term while not adding too much to the regret it satisfies criteria (1) and (2). The lower-bound follows from the standard inequality Va+bb + b I Va + Jatz since ru(w)) =
80
30
Figure 1: (w; 1, 22 1) when Σ wp
and We = 2. The dashed line has slope bwy
cp (E | (+a)) T/F+ so that r; is quadratic for |wl| < |w.] and linear otherwise. Notice that We is constant used to define r it is the argument of the function.
The upper-bound is more subtle,
/a w² and involves the piece-wise definition. For simplic- ity, suppose it were true that either |wy| < |u| for all or wel Ju| for all t. In the former case,
5

---

((()) 0 as O(uulT)). In the latter case, have /a2 w
[u
Diz which via algebraic manipulation can be bounded
leel
O(IulvT) so Va=+zu
Iu
that both cases result in the desired bound on Σi=1 re(u). The general setting handled by parti- tioning the sum into two sets depending on whether |wel S lu]. In order to cancel the max, [wy] term the martingale concentration, we employ p = log This choice is motivated by the observation that |lol T E [||v exp(1)llvlla for all RlogT. With this identity in hand, the argument is very similar to the = case.
The correct values for the constants are provided in Theorem Again, at high level, the important constants are P1 and P2- With P1 = 2. we allow E, re(we; = 2) to cancel out the VE, w martingale concentration term, while with p2 log >, (r log T) cancels that max, [wy)
term.
It remains show that the also allows for small (2) and satisfies criterion (3). Unfortunately, our setting for 02 in the definition of th is Ó(), which means that the is O(b)-Lipschitz. Since we wish to allow for = O(VT), this means that we cannot simply let A linearize vi and apply an arbitrary OLO algorithm. Instead, we must exploit the fact that th is known before 9: is revealed. That is, algorithm A is chosen to exploit the structure composite loss (w). Intuitively, the regret of a composite loss should depend only on the non- non-composite şa terms (as in e.g. Duchi et al. (0100)). Our situation is slightly more complicated vi, depends w, well, but nevertheless achieve the desired result via a modification of the parameter-free optimistic reduction in Cutkosky [2019]. For technical reasons, this algorithm still requires |ge| S b with probability 1, but obtains regret only RA (u) S Ō(c + T [b. This technical limitation is lifted the following section.
We display the method as Algorithm | which provides a regularization that cancels the | dependent part of the NOISE term in 7 also allows us to control RZA( (u) to order Ō + lulo + b/ul) by taking account into the predictable structure of regularizer the (w)) The algorithm requires black-box access to two base online learning algorithms, which we denote Aj and A2 with domains (-00, o0) and [0, oo) respectively. These can be any algorithms that obtain so-called "second-order" parameter- free regret bounds, such as available in Cutkosky and Orabona (2018). van der Hoeven (2019),
Kempka et [2199, Mhammedi and Koolen 2020). Roughly speaking, the role of A to provide an initial candidate ouput that is then "corrected" by Az using the regularization to obtain the final
W/.
Following the intuition previously outlined in this section, We first provide a deterministic regret guarantee on the quantity (w) = D (ww) - (u) as an intermediate result (Theorem 2). Then, we provide the analysis of the full procedure of Algorithm for the final high probability result (Theorem 3. Missing proof' are provided in the Appendix and
Algorithm 1 Sub-exponential Noisy Gradients with Optimistic Online Learning
Require: Elg.] [e, 19el < b, Elgg [wm] < 6² almost surely. Two online learning algorithms (e.g. copies Algorithm from Cutkosky and Orabonal 2018) labelled as A1, with domains R and R>o respectively. Time horizon T. 0 1.
1: Initialize:
Constants (21, P1, 01, 022 from Theorem
> for defining th in equation d
= =1p1 C1P1 + 02P2 2: for /= 1 to 7 do
3:
Receive x/ from AI, 3/c from A
4:
Rescale z; = 2//(b= + H), y1 ///(H(H H)) Solve for wy: We It y/ (w))
5:
The solution exists by Lemma
6:
Play We to, suffer loss (e(w))
7:
Receive de with E[g.] (w:)
8:
Compute (b)(w) Tr (1,, a1) + rr C2, 02) and (w)e) b equations
P1, Send (gt + (u)a(w,))((b H) A1
9:
10: Send -g. + Vi, H) to A2
11:
end for

---

Theorem 2. Suppose A1 ensure that given some e > 0 and sequence or with leel - 1:
Σ 1ep1 (1 (1+ log
[uppte (Luf c
Ju[TC
E we, W/ u) S S Alul,
+B
Blu] log
+
for all u for some positive constants A, B, C, and that Ag obtains the same guarantee for all 2 for lgel S b, (Vbr(w))) S H, we have the following guarantee from Algorithm 7
R+( S O c+ jul (1 max 0. 0.>
T
- 1 (V,(()))) + (b H) log T
Although this Theorem is rather technical, the overall message is not too complicated. If we ignore the negative Veh (w, u2) terms, the bound simply says that the regret on the "composite" loss (9t, u) + (w)) only increases with the apriori-unknown unknown 9t. and not with V (we). With this result, we can formalize the intuition in this section provide the following high probability regret bound:
Theorem 3. Suppose {9i} are stochastic subgradients such that T[gol de, (we). lool b and Elg w/] < o² almost surely for all t. Set the following constants for Ve shown in equation for any 0 < 8 <
0,
6 = 20 log
32 [log (2T+1) 2]²),
02 32b log
224 [log (1 22 + +2]²),
P1 = 2,
P2 = log T,
a1 = c/c1,
a2 = ea (4b(b + H))
where H = cIP + e2p2, [vpe(w))) S H. Then, with probability at least 1 ô, algorithm guarantees
RT( s 2 clog 8 + lu |u|blog 8 + lu l T log
Note that this result is already of interest: prior work parameter- free algorithms with sub- exponential noise only achieve in-expectation rather than high probability results. Of course, there is a caveat: our bound requires that I9:1 be uniformly bounded by b. Even though b could be large as vT. this still a mild restriction. In the next section, we remove both this restriction as well as the light tail assumption all together.
5 Heavy tails via Truncation
In this section, we aim to give a high probability bound for heavy-tailed stochastic gradients gi. Our approach builds on Section by incorporating gradient clipping with clipping parameter 7 E R-
g
ge
min(T, lg: (g:l))
g+
We continue to consider a 1-dimensional problem in this section, replacing the norm ||. with absolute value | and g. with gt- The key insight is that the clipped ÿt satisfies [[]]] < 2P 2 GP) and of course lgel < r. Hence, a high probability bound could be obtained by feeding ÿe into Algorithm M from Section
Let formally quantify the effect of this clipping:
RT(u)= W(Ve(w))
Σ (Vl(w.) Elqr], w. u) Σ (Elrr), we u)
bias
Section S
Without clipping, we would have [[g. Vee(w,) and so if we were satisfied with an in-expectation result, the first sum above would vanish. However, with clipping, the first sum actually represents some "bias" that must be controlled even obtain an in-expectation result, let alone high probability. strategy analogous at a high level to the
We control this bias using one developed in Section E although technically quite distinct. After dealing with the bias, must
7

---

handle the second sum. Fortunately, since Åe is sub-exponential. bounding the second sum in high probability is precisely the problem solved Section We introduce the analysis in two elementary steps. For the purpose of bias cancellation, we define linearized loss (ww with regularization function ((w)
(ww)) = (E[g.). w) + ((w),
((w) (oP + GG)]w///D--
(8)
the regret in equation can be re-written as
T
(Vl((w)) - Elg.) wi u) )(w)) + d(u))
Σ (c)))
bins cancellation
Soction !
We will be able to show that the wy-dependent terms of the first summation and so can be dropped. This leaves only the u-dependent terms, which for appropriate choice will be (pw)
negative number
Note that at this point, if we were satisfied with an in expectation bound for heavy-tailed subgradient estimates (which would already be an interesting new result), we would not require the techniques of Section 4 we could instead define (ww = (ge. w) + vi(w,, so that the last sum equal to 21=1 (wxr) - (u) in expectation. Then, since |6, (w,)) I - O()) with probability 1, we can control
E. (wv) (u) using a parameter-fres free algorithm obtaining regret Ó(Iu) v EE= [V2
r|ul) to bound the total expected regret, yielding a simple way to recover prior work on expected regret with sub-exponential subgradients (up logs). while extending the results to heavy-tailed subgradients.
However, since do aim for high probability bound, need be careful with the second summation. Fortunately, given that Ôr sub-exponential and bounded, and Vo w,, is deterministic. we can supply ğ: + Ve(w,) Algorithm and then bound the sum in high probability by Theorem We formalize the procedure as Algorithm 2 and its guarantee is stated in Theorem The exact regrel guarantee (including constants) can be found in Appendix
Algorithm 2 Gradient clipping for (a, G) - tailed gradients
Require: Efg+] = (we)), |B [[[g:]] < G, 1l1g [[ S Oº for some E (1, Time horizon
T. gradient clipping parameter
1: Initialize Algorithm [siig the parameters of Theorem S
2: for 1 to 7' do
3: Receive from Algorithm |
4: Suffer loss & (w;), receive St
5: Truncate 9r = St. min(r, (9el).
6:
Compute = It + Vor
> ((w) is defined in 8 [. E (ww).
7: Send dr to Algorithm as 1hh subgradient.
8:
end for
Theorem Suppose {ge} are heavy-tailed stochastic gradient such that R[gg] E (wx) [R[g]] <
G. Ellg - E[gg]| < oB for some P E (1,2]. If we set 7 = (1/P(ap + GD)1/p then with probability at least 5, Algorithm guarantees:
Rr(u) Ō clog 1 |u/TT Gog log 8
T |u[T
log
Theorem suggests regret with heavy-tailed gradients Je has dependence of Ö(T1/P), which is optimal Bubeck et al.) 2013, Vural et al. 2022
Dimension-free Extension
So far, we have only considered I-dimensional problems. In this section, we demonstrate the extension to dimension-free, which is achieved by using reduction from Cutkosky and Orabonal 20188. The

---

original reduction extends a 1-dimensional algorithm to a dimension-fred one by dissecting the problem into a "magnitude" and "direction" learner. The direction learner a constrained OLO algorithm And which outputs vector V, with ||v=l| S in response to gi...... 1t--1, while the magnitude learner is an unconstrained OLO algorithm And which outputs E R in response to (g), vI).... Vt- The output of the entire algorithm W, Vy Suppose And and And have regret guarantee of Ry (u) and Rnd(u), respectively. Then regret of the dimension-free reduction is bounded by (u) S ||u|] ( (u/llull) + RF (I]ul). Thus, in order to apply this reduction we need to exhibit A and And that achieves low regret on heavy-tailed losses. For the magnitude learner A we use can use the 1d Algorithm that we just developed. The remaining question is how develop direction learner that can handle heavy-tailed subgradients. Fortunately, this is much easier since the direction learner is constrained to the unit ball.
To build this direction learner, we again apply subgradient clipping, and feed the clipped subgradients the standard FTRL. algorithm with quadratic regularizer (i.e. "lazy" online gradient descent). This procedure is described in Algorithm E Note there is no regularization implemented in Algorithm| although g. induces bias. This because And runs on the unit ball, careful tuning of T is sufficient to control the bias concrete demonstration of how much more intricate the unconstrained case is! Finally, the full dimension- free reduction is displayed guarantee stated in Theorem S
Algorithm with its high probability The details are presented in Appendix
Algorithm 3 Unit Ball Gradient clipping with FTRL
Require: time horizon T, gradient clipping parameter т, regularizer weight !]
Set 17 y= 1/T
2: for t= to do
3:
Compute V, argmin ş1 Σ (B:, v) 2n |
4:
Output Vr, receive gradient ge
5: Set g: = _i_
T min(1 T, [lg:])
6: end for
Algorithm 4 Dimension-Fne free Gradient clipping for (o, G) Heavy-tailed gradients
Require: Subgradients tt moment bound oP, time horizon T, Set Algorithm Set 0id (a 2GP))/p and Tid = ( G /P) / 3G
as Ald And
2: Initialize ld with parameters <- Øid and t- Tid
3: Initialize And with parameters a a and T //)
4: for ==== 1 to T do
5: Receive 2, E E from Add
6: Receive E Rd [|v: < from nnd
7: Play output W, V,V,
8: Suffer loss & W.), receive gradients g:
9: Send gr (gr, Vr) as the thh gradient to .
10: Send g: as the th gradient to And
11:
end for
Theorem 5. Suppose that for all t, {gr} are heavy-tailed stochastic subgradients satisfying E E'gel e
(w.) || Elg.]ll < G and El [] S a² for some p E (1,2), 2). Then, with probability at least 1 - 8, Algorithm guarantees
(T(u) - ((w)) (c(u) S
1 x + || G) log log e elog
T
|u|
Complexity Analysis:
Algorithm requires (dd) space, also requires O(d) time for all operations 5). This can be solved via binary search
except solving the fixed-point equation in Algorithm (line to arbitrary precision 6o for an overall complexity of O(d log(1/eo)) This is essentially O(d) in practice for any d > 64.

---

7 Conclusion
We have presented a framework for building parameter- free algorithms that achieve high probability regret bounds for heavy-tailed subgradient estimates. This improves upon prior work in several ways: high probability bounds were previously unavailable even for the restricted setting of bounded subgradient estimates, while even in-expectation bounds were previously unavailable for heavy-tail subgradients. Our development required two new techniques: first, we described a regularization scheme that effectively "cancels" potentially problematic sterate-dependent variance terms arising in standard martingale concentration arguments. This allows for high probability bounds with bounded sub-exponential estimates, and we hope may be of use in other scenarios where the iterates appear in variance calculations. The second combines clipping with another new regularization scheme that "cancels" another problematic ilerate-dependent bias term. On its own, this technique actually can be used to recover in-expectation bounds for heavy-tailed estimates.
Limitations: Our algorithm has several limitations that suggest open questions: first, our two regularization schemes each introduce potentially suboptimal logarithmic factors. The first one introduces higher logarithmic dependence on T. while the second introduces a higher logarithmic dependence on ||u|| because the optimal clipping parameter т depends on log([[u]] ). Beyond this, algorithms require knowledge of the parameters and т. Adapting to unknown value of even one of these parameters remains challenging problem.
References
N. Agarwal, B. Bullins, E. Hazan, S. Kakade, and K. Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111-119. PMLR, 2019.
A. Balsubramani. Sharp finite-time iterated-logarithm martingale concentration. arXiv preprint 140.:2940,.2669, 2014.
S. Bubeck, N. Cesa-Bianchi, and G. Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(1 1):7711 2013.
N. Desa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
L. Chen, H. Luo, and C.-Y. Wei. Impossible tuning made possible: A new expert algorithm and its applications. Conference on Learning Theory, pages 1216-1259, PMLR, 2021.
A. Cutkosky. Algorithms and Lower Bounds for Parameter-free Online Learning. PhD thesis, Stanford University, 2018
A. Cutkosky. Combining online learning guarantees. In Proceedings of the Thirty-Second Conference on Learning Theory, pages 895-913, 2019.
A. Cutkosky and K. Boahen. Online learning without prior information. In Conference on Learning Theory, pages 643-677, 677,, 2017.
A. Cutkosky and H. Mehta.
bounds for non-convex stochastic optimization with heavy tails. In Proceedings of the 35st International Conference on Neural Information Processing Systems, pages 4895, 2021.
A. Cutkosky and F. Orabona. Black-box reductions for parameter-fie free online learning in banach spaces. In Conference On Learning Theory, pages 1493-1529, 2018.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Conference on Learning Theory (COLT), pages 257-269, 2010a.
C. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. In COLT, volume 10, pages 14-26. Citeseer, 2010b.
D. J. Foster, Kale, M. Mohri, and K. Sridharan. Parameter-free online learning via model selection.
In Advances in Neural Information Processing Systems, pages 6020-6036, 2017.
10

---

E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042- 15053, 2020.
J. Harvey, C. Liaw, and S. Randhawa. Simple and optimal higb-lrobability bounds for strongly- convex stochastic gradient descent. arXiv preprint arXiv:1909.0008 2019.
E. Hazan. Introduction to online convex optimization. arXiv preprint arXiv: 190.00990900007,200000
S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Anmals of Statistics, 49(2):105-11000, 2021.
K.-S. Jun and F. Orabona. Parameter-free online convex optimization with sub-ex sub-exponential noise. In Conference on Learning Theory, pages 1802-1823. PMLR, 2019.
A. Kavis. K. Y. Levy, and V. Cevher. High probability bounds for class of nonconvex algorithms with adagrad stepsize. arXiv preprint arXiv:2204.0m 02833, 2022.
M. Kempka, W. Kotlowski, and M. K. Warmuth. Adaptive scale-invariant online algorithms for learning linear models. In International Conference Machine Learning, pages 3321-3330, 2019.
D. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.698,, 2014.
X. Li and Orabona. A high probability analysis of adaptive sgd with momentum. Workshop on Beyond First Order Methods in ML Systems at ICML 20, 2020.
L. Madden, Dall' Anese, and S. Becker. High probability convergence bounds for stochastic gradient descent assuming the polyak-lojasiewics inequality. arXiv preprint wxXiv:2006.06610 2020.
Z. Mhammedi and W. M. Koolen. Lipschitz and comparator-nom adaptivity in online learning. Conference on Learning Theory, pages 2858-2887, 2020.
Orabona. A modern introduction to online learning. arXiv preprint
2019.
Orabona and K.-S. Jun. Tight concentrations and confidence sequences from the regret of universal portfolio. arXiv preprint arXiv:2110.14000 2021.
Orabona and Pál. Coin betting and parameter-free online learning. D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 577-585.
Curran Associates, Inc., 2016.
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
S. Shalav-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Tropp. Freedman's 's inequality for matrix martingales. Electronic Communications in Probability, 16:262-270, 2011.
D. der Hoeven. User-specified local differential privacy in unconstrained adaptive online learning. In Advances in Neural Information Processing Systems, pages 14103-14112. 12,, 2019.
J. Ville. Etude critique de la notion de collectif, gallhier-villars, paris, 1939. Monographies des Probabilités. Calcul des Probabilités et ses Applications, 1939.
V. Vovk. Hoeffding's inequality in game-theoretic probability. arXiv preprint arXiv:0708.2500 2007.
N. M. Vural, L. Yu, K. Balasubramanian, S. Volgushev, and M. A. Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. arXiv preprint 11632,, 2022.

---

I. Waudby-Smith and A. Ramdas. Estimating means of bounded random variables by betting. arXiv preprint arXiv:2010.09686, 2020.
Zhang, S. Karimireddy, Veit, S. Kim, Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33: 15383-15393, 2020.
Zhou, J. Feng, C. Ma, C. Xiong, S. C. H. Hoi, et al. Towards theoretically understanding why sgd generalizes better than adam in deep learning. Advances in Neural Information Processing Systems, 33:21285-21226, 2020.
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pages 928-
936, 2003.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No] or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] This work considers a purely mathematical investigation of concentration of regret, and we do not envision any negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
12

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' roure using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "rRWCcyaB1u", "reviewer": "Reviewer_WCJh", "summary": "The authors consider online convex optimization over unbounded domains with potentially heavy-tailed subgradient estimates as feedback. Precisely they assume that the p-th(\\in(1,2]) moment of the subgradient is bounded. They propose an algorithm that with high probability has regret against any fixed comparator u of order O(|u|\\sqrt{T}) where T is the horizon. Furthermore, the algorithm is parameter-free in the sense that it does not need to know the norm |u|. This algorithm relies on two novel regularizers that share similarities with the Huber loss. One to deal with the fact that the domain is unbounded and the other to handle the heavy-tailed subgradient.\n", "questions": "Specific comments: \n\n-L30: Since at since point the role of \\epsilon is not clear why not hide it in the \\tilde{O} notation?\n\n-L81: log factors with respect to which quantities of the problem, i.e. not log factor of exp(T) ?\n\n-L128: G is not defined?\n\n-L199: At this point it is not completely clear why you need two algorithms \\cA_1 and \\cA_2.\n\n-L201: Maybe you should give at least one of these algorithm in then appendix.\n\n-L208: Does the result holds with probability one?\n\n-L266: g_1\n\n-L281: Algorithm 3, Require, g_t instead of \\hat{g}_t?\n\n-L284: Can you discuss how the obtained bound mathc or not the lower bound you mention in the introduction? Can you also provide the overall time/space complexity of Algorithm 4?\n\n-L427: Theorem 1 and a dot is missing. \n\n-L428: R instead of \\mathbb{R}\n\n-L429: parenthesis and the statement of the lemma is not very clear.\n\n-L432: punctuation of the equations is missing.\n\n-L435: * not at the right place.\n\n-L444: What is \\bar{G}?\n\n-L459: Can you detail how you applied Lemma 7 (choice of G and \\bar{G}?\n\n-L462: inf over y^\\star is missing.\n\n-L466, below: it seems that the term |A|^2uH[...] is repeated.\n\n-L470: The first sentence is not clear.\n\n-L483: The capital for Theorem, Section, Algorithm, Appendix is a bit inconsistent. \n\n-L542: w_t^2\\epsilon_t^2", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Contributions:\n-parameter-free algorithm for (1D) supexponential stochastic subgradient estimate, novelty: medium, relevance: high.\n-parameter-free algorithm for heavy-tailed stochastic subgradient estimate, novelty: medium, relevance: high.\n\nThe paper is well-written, and the intuition, in particular, is clearly described. Maybe a small description of the role of \\cA_1 and \\cA_2 in Algorithm 1 could make the presentation clearer. The proofs seem correct. I did not read the appendix C, D, E. Note that the writing in the appendix could be improved, see specific comments. The considered setting and the obtained results may look a bit incremental but I think that the new regularizers and the associated analyses developed to overcome the technical difficulties are a valuable contribution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gnxMffoUkNu", "reviewer": "Reviewer_Wska", "summary": "The paper studies online convex optimization over unbounded domains and aims to provide a high-probability regret bound given access to only potentially heavy-tailed gradient information. Towards this end, the authors propose several interesting ideas to overcome the anti-concentration issue due to the heavy-tailed noise. The basic idea is to add some regularization to cancel additional term introduced by the heavy-tailed gradient. The results are new and the techniques are interesting.", "questions": "no", "limitations": "see comments in Strengths And Weaknesses", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is generally of good quality, including the writing and presentation logic. The results for unbounded online convex optimization are new, to the best of my knowledge. I have two concerns as stated below.\n\n1) It is acknowledged that heavy-tailed issues and parameter-free bounds are interesting to the community. But does it have practical appeals when combining the two? The authors are encouraged to motivate their paper with a concrete and practical example in real applications, such that the readers will be more convinced to believe that we indeed need to pay some effort to study this problem. The current paper presentation does not consider this, which makes the reader think of \"creating\" this problem to solve.\n\n2) The solution for this problem is kind of simple. I am not saying that simplicity is a drawback, but some discussions on whether the idea can be applied in broader applications/theoretical problems would strengthen the technical contribution. Additionally, the paper lacks discussions on the computational complexity -- for example, step 5 in Algorithm 1 is like a fixed-point equation, how to solve it in an efficient way? what's the overall computational complexity? All those stuff should be discussed in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "btQG3oK4Clx", "reviewer": "Reviewer_tcgd", "summary": "This paper proposes new algorithms for online convex optimization over unbounded domains. The authors provide a parameter-free regret in high probability with heavy tails. First, they introduce a parameter-free algorithm for sub-exponential $g_t$ that achieves regret $O(\\epsilon+|u|\\sqrt{T})$ in high probability. Then, they extend to heavy-tailed $g_t$ by employing clipping on the heavy-tail. Last, they extend the algorithms to arbitrary dimensions.\n\n", "questions": " Is this possible to set a appropriate $\\tau$ even if we did not have any information about $\\sigma$?", "limitations": " 1. Same as weakness #3, $\\tau$ may not be known, which could be a challenge when we run the algorithm 2.\n 2. Two regularization functions introduce suboptimal logarithmic factors: The first one introduces a higher logarithmic dependence on T, and the second introduces a higher logarithmic dependence on |u|.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The authors present a framework for building parameter-free algorithms that achieve high probability regret bounds for heavy-tailed subgradient estimates: high probability bounds were previously unavailable even for the restricted setting of bounded subgradient estimates.\n2. They use Huber loss to construct a regularizer to ensure that it achieves low regret with a high probability in Section 4, and define another regularization function (from clipped $\\hat{g}_t$) for the purpose of bias cancellation in Section 5. \n3. They also extend the work to arbitrary dimensions. \n\nWeaknesses:\n1. The paper needs proof reading: For example: In page 2 contribution and Organization: We introduce a parameter-free algorithm for supexponential->sub-exponential.... ;  \"Secondly, we extend to heavy tailed \"..-> heavy-tailed \n2. In Section 4,   $|g_t|\\leq b$ is mentioned. Note that, this b is $O(\\sqrt{T})$. It is better to use $b_t$ because $b$ is used for constant value.\n3. In theorem 4, $\\tau$ may be unknown because it needs the knowledge of $\\sigma$. Algorithm 2 could not achieve Thm 4's regret bound if we do not know $\\tau$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept