When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses
Authors: Antoine Moulin
Emmanuel Esposito
Dirk van der Hoeven
Venue: NeurIPS 2025 poster ()
Keywords: prediction with expert advice
adaptive algorithms
regret minimization
Primary area: reinforcement_learning

Abstract: We consider the problem setting of prediction with expert advice with possibly heavy-tailed losses, i.e., the only assumption on the losses is an upper bound on their second moments, denoted by $\theta$. We develop adaptive algorithms that do not require any prior knowledge about the range or the second moment of the losses. Existing adaptive algorithms have what is typically considered a lower-order term in their regret guarantees. We show that this lower-order term, which is often the maximum of the losses, can actually dominate the regret bound in our setting. Specifically, we show that even with small constant $\theta$, this lower-order term can scale as $\sqrt{KT}$, where $K$ is the number of experts and $T$ is the time horizon. We propose adaptive algorithms with improved regret bounds that avoid the dependence on such a lower-order term and guarantee $\mathcal{O}(\sqrt{\theta T\log(K)})$ regret in the worst case, and $\mathcal{O}(\theta \log(KT)/\Delta_{\min})$ regret when the losses are sampled i.i.d. from some fixed distribution, where $\Delta_{\min}$ is the difference between the mean losses of the second best expert and the best expert. Additionally, when the loss function is the squared loss, our algorithm also guarantees improved regret bounds over prior results.

When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses
Antoine Moulin' Universitat Pompeu Fabra antoine mowuin@upf.....mm edu
Emmanuel Esposito" Università degli Studi di Milano
emmanuel oerraaeee...mmaaeeeeeseess..oo..
Dirk van der Hoeven
Leiden University
darketiizkandeerooeeen.cm com
Abstract
We consider the problem setting of prediction with expert advice with possibly heavy-tailed losses, i.c. the only assumption the losses is upper bound their second moments, denoted by We develop adaptive algorithms that do not require any prior knowledge about the range the second moment of the losses. Existing adaptive algorithms have what typically considered a lower-order term in their regret guarantees. We show that this lower-order term, which is often the maximum the losses, can actually dominate the regret bound in our setting. Specifically, we show that even with small constant 8, this lower-order term can scale as / KT, where K is the number of experts and 7' is the time horizon. We propose adaptive algorithms with improved regret bounds that avoid the dependence on such a lower-order term and guarantee (VV ((g(K) regret in the worst case, and O log( (XT))Amin)) regret when the losses sampled i.i.d. from some fixed distribution, where Amin is the difference between the mean losses of the second best expert and the best expert. Additionally, when the loss function is the squared loss, our algorithm also guarantees improved regret bounds over prior results.
Introduction
We study the problem of prediction with expert advice [Vovk, 1990, Littlestone and Warmuth, 1994], a sequential decision makinng setting over T rounds where each round & goes as follows. The learner selects probability distribution p: some loss fp.) IR, and subsequently observes the loss function fr: P + R. The goal in this problem, also known more briefly as the experts setting, to control the (pseudo-)regret
{p R p(i) 2 0, (pe, 1) 1} over K experts, suffers
T Σ (o)
RT max Per (ex) max KE(K]
FE[K]
where the expectation is with respect to the randomness in (ft) and e; E P is the i-th standard basis vector. The pseudo-regret measures the expected difference between the learner's cumulative loss and that of the best expert in hindsight. Throughout the paper, we assume that either the losses the oulcomes are heavy tailed, and provide concrete answer the concluding remarks of Mhammedi et al. [2019] that highlight the challenge of dealing with infrequent large values in the full- information setting. Such conditions arise in various practical settings involving noisy data,
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

outliers, or mechanisms like those in local differential privacy [Van der Hoeven, 2019]. Further motivations for our setting can be found in financial markets [Bradley and Taqqu, 2003], electricity forecasting [Li and Jones, 2019, Devaine et al., 2013], and predicting views on articles or videos (see. egg., Cha
Cha et al. [2007]).
A primary goal of this paper is to develop algorithms that achieve sub-linear regret without prior knowledge of a bound on the second moment of the losses, outcomes, or range of the losses maX Ifr (p)]. We will refer to such algorithms as loss-range adaptive algorithms. Crucially, unlike the related multi-armed bandit problem, where adaptivity to an unknown second moment is generally impossible without further assumptions [Genalti et al., 2024], we demonstrate this achievable in the experts setting. Our second goal to aim for algorithms that exhibit strong guarantees both in worst-case scenarios and in more benign stochastic environments, often referred to as best-of-bouth both-worlds guarantees.
While several aas--rane adaptive algorithms exist for linear losses, ft (p) ( (p. = =E (()) for some RK they are not designed handle heavy-tailed losses [Blackwell, 1956, Cesa- Bianchi et al., 2007, De Rooij et al., 2014, Orabona and Pál, 2015, Mhammedi et al., 2019]. Standard algorithms achieve O (M /Tlog K) regret for losses bounded as max,,; (1)] I M. However, the losses are drawn from some distribution supported on R and such that max,, (1) S
for some 0 > 0, the regret guarantees of existing algorithms can degrade to ( which is exponentially worse in K. The issue lies in what prior work consider a lower-order term, namely max,,, (+)]. Indeed, while this term is innocuous for bounded losses, we demonstrate that for heavy-tailed losses with second moment & (1), it can be large as D ((VKT). thereby becoming the dominant factor in the regret bound.
This paper introduces adaptive algorithms that overcome this limitation. Specifically:
1. For linear losses, under Assumption 2.1, Algorithm 2 achieves O(vOT (0TToo(()) K)) worst-case regret, effectively removing the detrimental vK dependency.
2. Under Assumption 2. Algorithm achieves (( (OTTT log(KT)) worst-case regret, while also providing O(0 log( (KT))) / regret in self-bounded environments (Assumption 2.3), where Amin is the gap in expected loss between the two best experts. This contrasts with prior algorithms whose guarantees would still be hampered by the ((VKT) term.
3. For the squared loss, ft (p) = ((p, z.) - yr)", where expert predictions Zz.i are bounded by Y and the second moment of the outcomes yt is bounded by a, Algorithm achieves a regret of O ((Y2 2 - σ) log (K)), avoiding a O (T) regret that can arise for heavy-tailed outcomes.
The remainder of the paper is structured follows: Section 2 presents the problem settings and our main results. Section 3 discusses related work in more detail. In Section 4, we establish why terms previously considered "lower-order" become dominant under heavy-tailed losses for existing algorithms. Section 5 presents our algorithms and sketches their regret analyses, highlighting the techniques used cireumvent the challenges posed by the lack of control over the range of losses. We conclude with a discussion of future work in Section 6.
2 Preliminaries and Results
We consider two settings. The first, sometimes referred to as the "Hedge setting" [Littlestone and Warmuth, 1994], can be seen as special case of the experts setting [Vovk, 1990] with linear losses. In the second, we consider quadratic losses. Throughout the paper, we assume K, T 2 without loss of generality.
2.1 Hedge Setting
In this section, each round t .......22 T, goes as follows: the learner issues Pt E P, suffers loss (pt, li), and then observes & I2 Let E, [ = E F.). where F, is the sigma-field generated by the history (fi,..., ., 4-11) up to round f. We will use the following assumption in the Hedge setting.
Assumption 2.1 (finite second moments). There exists scalar 0 R such that E, [6 (1) < 0 for any E [T] and any e [K].

---

This assumption is more general than the standard bounded losses assumption: if [e(( S M for all i [K]. E [T', then Assumption 2.1 is satisfied with 0 M². We do not assume know 8, which is the central algorithmic challenge in the Hedge setting. One of our main results is the following.
Theorem 2.2. Consider the Hedge setting and suppose Assumption 2. holds. Then, there exists an algorithm that, without prior information on the losses, guarantees that R = (v log(K))
This is achieved by Algorithm 2, which we discuss later Section 5.2. The proof can be found in Appendix C. While such a result seems expected, we found that loss-range adaptive algorithms in the literature can only guarantee (og(Koog(K + VKT) regret. We detail prior results in Section and their issues in Section 4.
The following assumption allows us to obtain better regret bounds.
Assumption 2.3.
There exist Amiu. C > 0 and a unique = arg min ET= 4(ii) such
that R 2 R Σ (1 (t*)) C.
This is known as a self-bounded environment [Zimmert and Seldin, 2021] and has been studied in the Hedge setting by Amir et al. [2020]. An example setting in which Assumption 2.3 is satisfied is when the losses of the experts are sampled identically and independently from a fixed distribution, which case C = O. To see why, denote by A; = B((+(t) - (i')) and by Amin mi] A, We have that
T Σ
T
R = E
Σ 1=1 1n66
2E
(c) min = iyli
Σ
Σ
Σ (o-pp((t)) Amin
and Assumption 2.3 is satisfied. We have the following result under Assumption 2.3.
Theorem 2.4. Consider the Hedge setting and suppose Assumption 2.1 holds. Then, there exists an algorithm that, without prior information the losses, guarantees R2 (ooolo (og(TT())) Furthermore, if Assumption 2.3 also holds, then the same algorithm simultaneously guarantees
Rr = (log(KT)
C6 (KT(
Amin
This is achieved by Algorithm 1, which we discuss in Section 5.1 together with sketch of the proof. We provide full proof in Appendix B.
2.2 Quadratic Losses
Here introduce second setting we consider. In each round t [T], the learner observes the expert predictions (ZK)));((K) issues a prediction z, = (p,, 21). suffers the quadratic loss fe (pt)
(z: - 2 and then observes y,- We have the following result.
Theorem 2.5. Consider quadratic losses and suppose that max,, [zr,il S Y and max; E, [ S Then there exists algorithm such that Rt O ((Y² + o) log (KT))
We prove this result Appendix D. sketch of the proof is provided in Section 5.3. Our analysis could also be extended to strongly convex losses. We leave this extension for future work.
Notation. For any gret, (i) = r. ( and 0g = ΣK (1) be the variance of & (Ir with Ie ~ Pt- Fur- thermore, let Vy ΣT T. (i) Σtn ve()), Mr E [ax Ir, (i)].. and
[T]. e [K]. let re (i) (p),4) lg (i) be the instantaneous re-
LT E [maxxe]rr,=eik]]] && (i)] Finally, we denote by arg min E ΣT & (i) the best expert in hindsight.
3 Related Work
There are several loss-range adaptive algorithms in the Hedge setting. summary can be found in Table 1. Perhaps the most well-known loss-range adaptive algorithm is the exponential weights

---

Assumption 2.1
Assumptions 2.1 and 2.3 with C' 0
Cesa-Bianchi et al. [2007]; De Rooij al. [2014]
(oglog(() K) + Mr
0 Olog (4) min + MT
Mhammedi et al. [2019]
(K) + Mr
0 (log(K) min + Mr
Algorithm (Ours)
VOTlog(KT)
log((T)) KTT v /T log( K)
Algorithm 2 (Ours)
v VoTlog(K) K)
Table 1: An overview of the most relevant loss-range adaptive algorithms in the literature, ignoring constants. Some of the results in the middle column follow from an application of Jensen's 's inequality.
algorithm [Vovk, 1990, Littlestone and Warmuth, 1994, Cesa- Bianchi et al., 1997] combined with the doubling trick [Auer al., 1995]. This combination leads to O (L (K)) regret bound. Cesa-Bianchi et al. [2007] provide a refined version of the exponential weights algorithm com- bined with a refined doubling trick to obtain a O E VT log (K) + My log (K) regret bound. De Rooij et al. [2014] also prove the same regret bound for an algorithm based on the exponential weights algorithm, with the added benefit that their algorithm does not use restarts to achieve this result. Orabona and Pál [2015] provide generic analysis of follow the regularized leader and online mirror descent that, under mild assumptions on the regularizer, leads to loss-range adaptive algorithms which guarantee that the regret is at most (E VV E. max, (+))² ). but this can be trivially seen to be at least Mr. Mhammedi et al. [2019] provide loss-range adaptive version of Squint [Koolen and Van Er- ven, 2015], which guarantees a regret bound scaling as (B V (i*) log (K) + Mr log (K)). Flaspohler et al. [2021] show that regret matching [Blackwell, 1956, Hart and Mas-Colell, 2000] and regret matching+ [TTammelin et al., 2015] are both loss-range adaptive algorithm, but unfortunately with unsatisfactory regret bounds. Under Assumption 2.1, Wintenberger [2024] provides a loss-range Σ
adaptive algorithm with O (log (K) VOT L
K 1=
log [
+
max, re(611 )
regret, where M4,5 is
mys
the first non-null observation of Ir (i) Unfortunately, it is not clear how to control maxe (ra()) as Me, can be made arbitrarily close to 0 by an adversary.
Orseau and Hutter [2024], Cutkosky [2019] provide generic templates to make most Hedge algorithms loss-range adaptive, the cost of a My term in the regret bound. Orseau and Hutter [2024] make use of the following observation: if the algorithm makes too extreme of an update it might never recover. Therefore, it is sometimes better ignore certain losses. Cutkosky [2019] observed that can always guarantee that the algorithm does not make such an extreme update by feeding the algorithm slightly shrunken losses, technique also employed by Mhammedi et al. [2019], Mhammedi [2022]. Specifically, they feed the algorithm the losses
E, (1) = & (1) min max,5]t-1],jEjk1 le. 01 max 14, (f)
max le, (i)
& (1)
max,e(().E((x]] (e, (f)l
This ensures the range of the losses we feed to the algorithm is known before choosing pt- The cost for using e, rather than le in the algorithm is minor at first sight:
T K
T K
max ((,()))
(e(() - to(1)
Σ
max,e(()jE((K] (i)l
1=1
1=
((,C)))) (
Σ max
(0(00 max. 1] [(([
max,e]]]Je[[]] [e(2)
max KE[T],E[[K]
(e(()))
However, this term can be prohibitively large as we will show in Section 4. Instead, we adapt and combine the ideas of Cutkosky [2019], Orseau and Hutter [2024]. We develop a coordinate- wise version of the clipping technique of Cutkosky [2019]. Unfortunately, this is not sufficient for our needs and we need combine with a coordinate-wise version of the null-updates of Orseau and Hutter [2024] and the multi-scale entropic regularizer of Bubeck et al. [2019] to guarantee satisfactory regret bound. Gökcesu and Kozat [2022] also claim to provide loss-range adaptive algorithms, but two of their results seem to contain mistakes. We provide details in Appendix E.

---

Scale-free algorithms. A related but different objective is obtaining scale-free or equivalently scale-invariant algorithms. An algorithm is said to be scale-free if the predictions of the algorithm do not change if the sequence of losses is multiplied by positive constant. While scale-free algorithms are loss-range adaptive the converse is not necessarily true. Mhammedi [2022] provide a generic wrapper to make any algorithm scale-free, under some mild assumptions on the algorithm. However, this comes at the cost of an additive Mr. The algorithms of De Rooij et al. [2014], Orabona and Pál [2015] are known to be scale-free. Unfortunately, it is not clear whether our algorithms are also scale-free.
Adaptive algorithms for bounded losses. we assume that losses are bounded, e.g., (x) E [0. 1]. then there are several works that provide wof-ooft-wwoottte results. Gaillard et al. [2014], Koolen et al. [2016] show that so-called second-order bounds simultaneously guarantee
T K
regret without further assumptions on the loss and O (log / Amin) regret under Assumption 2.3 with C' 0. This also implies that the results of
et al. [2007], De Rooij al. [2014], Koolen and Van Erven [2015], Chen et al. [2021] all lead to small regret under Assumption 2.3 with
C' = 0 while also being robust to more difficult environments. Mourtada and Gaïffas [2019] show that the exponential weights algorithm with a decreasing learning rate guarantees O (log K) Amin)
regret under Assumption 2.3 with C = 1 while simultancously guaranteeing O (vT log K) regret in the worst case. The only work that we are aware of that treats Assumption 2.3 with C' > is by Amir et al. [2020]. who show that the exponential weights algorithm with decreasing learning rate guarantees Ollog(A (K) + C) regret.
Online learning with heavy-tailed losses. To the best of our knowledge, we are the first to consider heavy tailed losses in the expert setting, A related setting is studied by Bubeck et al. [2013], who introduce the multi-armed bandits with heavy tails setting. The main difference with our setting is that the learner only gets to see the loss for the chosen action each round, which significantly reduces the amount of available feedback to the learner. Remarkably, without further assumptions, one cannot adapt 0, shown by Genalti al. [2024]. However, under some additional assumptions the loss, it is possible to adapt to 9 with bandit feedback [Lee et al., 2020, Ashutosh et al., 2021, Huang et al., 2022, Genalti et al., 2024, Chen et al., 2025].
4 Lower-Order Terms with Unbounded Losses
In this section, we show that what have been considered lower-order terms in the literature may actually dominate regret bounds.
4.1 Lower-Order Terms in the Hedge Setting
We provide three results that imply that if a regret bound contains Mr or Lr, then this "lower-order term" can dominate the regret bound. We rely on the following observation, proved in Appendix A.
Lemma 4.1. Fix any n E N (0). Let XI...., Xn be non-negative i.i.d. random variables such that
0
w.p. 1 w.p. n
X,
V
for each [n). Then, E[X3] for any [r) and bvn Elmma(X1,...... [.,,].,,,,]]]] vn.
While the distribution in Lemma 4.1 might appear unnatural, the Fréchet distribution, which is often used economics, satisfies similar properties as the distribution of Lemma 4.1; see Lemma A. in Appendix A. Lemma 4.1 immediately leads to the following result.
Proposition 4.2. There exists distribution for fi...., lr that satisfies Assumption 2./ with 0 = 4
such that L 2 VKT.
Proof. Simply choose (1) = Hr, + Ee, where Pt, E [0, 1] is chosen arbitrarily, Eτ,i is a Rademacher random variable, and ε,, follow the distribution specified in Lemma 4.1 with KT. Then, Lemma 4.1 provides the result after using E, [e)( < 24²,, + 2 E. < 4.
5

---

In the worst case, Proposition 4.2 implies that any algorithm with regret bound of the form RT S +VTT log() + LT will be dominated by Ly for large enough K. Existing algorithms sometimes have a Mr 2L. term the regret instead. It is natural question whether Mr can be small enough. The following proposition shows that Mr, like Lr, can be prohibitively large.
Proposition 4.3. Suppose one can guarantee bound RT S B3 + My, with 137 2 0. There exists distribution with 0 = 3 such that Bj- + MT 2 B1 + 16 KT - 1.
The proof of Proposition 4.3 can be found in Appendix A. While Proposition 4.3 shows that any regret bound with a term My is ((vKT). Theorem 2.2 guarantees that Algorithm 2 achieves Rr ( AT lo)( For loss sequences that satisfy Assumption 2.3, the situation is even more dire, as one then hopes to guarantee ( log K)/ m/n)))) regret. Proposition 4.3 shows that if one has regret bound of the form 0 log(()) log(K)/A / min + My, in the worst case this bound is ( In regret bound, which is exponentially better in K and T. Since these results only affect upper bounds on the regret, one can ask whether existing algorithms could benefit from more careful analysis. We do not think this is possible for existing algorithms and sketch an argument in Appendix A. Furthermore, to illustrate their failure modes, we compare empirically those algorithms with the ones we introduce in Section 5 in Appendix F.
contrast, in Theorem 2.4 we provide a ( log( /'T)
4.2 Lower-Order Terms for the Squared Loss
Since the squared loss is exp-concave (or mixable), appealing approach is use exponential weights with a suitable learning rate to obtain a regret bound that is seemingly independent of T. Indeed, simple calculation shows that the function g+(+) (y+ .)² is (2 maxx,,(Zz, y;) )
exp-concave. If one knows max,,; (Zi,) y this would lead to the following bound [Vovk, 1990];
Rr s 2og (K)
max (Zi.3 -v)) t,2
(1)
However, the max,,i (Zr, - 3² factor might lead to a poor guarantee. Suppose that |2,, S Y and that E [u]] < < 0o. If yt = p + fee,, where |pa] S 1, & is a Rademacher random variable, and e, follows the distribution specified in Lemma 4.1 with n T, then
E max (Ze.i -v1)²
2 E max vi 2Y [v]]
2 max [vl]
-2 max [el]
2 E max [=a|]
2(Y + 1) + max [ 1=a1)
2 1 T + 1)VT
which can be excessively large. Even more so, one would need to know (a., - )²)² to obtain the regret bound in Equation (1). The results of Wintenberger [2017] (see also Van der Hoeven et al. [2022] imply that the algorithm of Mhammedi et al. [2019], designed for the Hedge setting, applied
to the losses (i) 2 (Z. y/) would lead to bound of order
Ry o ((r² 2 + f E max iz yell) log(K))
The E E/max |2 yel] term can also be problematic. Indeed, if yt 14 E,s,, where μ4 E [-1,1], & is Rademacher random variable, and E, follows the distribution specified by in Lemma 4.1 with n KT, then E [max j val] 2 E max, [ Y J Y Thus, if Y 2 2 then y + + E max, jz, - yel] 2 ( VT). On the other hand, for the same yt. Theorem 2.5 implies that Algorithm guarantees a regret bound of order (4 +4+77 2²) log()o))))))
5 Algorithms
In this section, we present two types of algorithms and provide a sketch for their regret analysis. The first algorithm, called Lo0T-Free OMD (Lower-Order Term Free), is an instance of Online Mirror Descent (OMD), whereas the second, called LoOT-Free FTRL, an instance of Follow The Regularized Leader (FTRL). Both algorithms run clipped versions of the instantaneous regrets,

---

Algorithm LoOT-Free OMD
Inputs: Number of experts K 2, truncation parameter (0, 1J, learning rate 3 > Initialize: P1 (i) 5 1/K for all i E [K].
for tort=1,.. 1,... do
Predict pt, incur loss (pt. Eg) and observe 4, Set r (1) ー (pt, & (i) for all E [K].
Set 1/ (1) + Tı (i)² for all i E [K], and 8p < Pt=)
if E. 8, > 0 then
Set T/t, +- max Eest Ga Ense Us (i))-1/2 for all i E [K].
Set & (i) + rr (1) (1r (i) 1/m,.) for all i [K].
Set p++1 f arg min pEP. (p, Ei) + Dr (pllpt).
end if'
end for
but could obtain similar worst-case guarantees by running the algorithms clipped versions of the losses.
Before we describe the algorithms in more detail, we first need some definitions. For any t E [7]. let " E R be a vector of learning rates and th x E 20 + (Diag (vt') x, log > be the regularizer, where y= 1 is the coordinate-win inverse, log y is the coordinate wise logarithm, and Diag(y) is the diagonal matrix with diagonal entries y1...., ,......./K. 3K for any y E K Note that, for any x E I the fogx+1; -1 Consider also its Bregman divergence, I and y E R as Dr (=lly) ti (x) the (v) (Vor (v) x v)
gradient of th, is given by V (x) = Diag (ne defined for any
Σ 75. xy log di x; + 3/1 Finally, denote by Pa (p E P min; ps 2 a/ K} the probability simplex truncated by a/ K, for any a [0, 1].
5.1
OMD-based Algorithm
The main challenge in designing an algorithm for losses for which you do not know the range comes
from proving the stability of the algorithm, which say that pe (i) Pt+1 (i). An analysis based on strong convexity circumvents this challenge. Orabona and Pál [2015] show that if the regularizer ò is
strongly convex with respect to some norm || |]. the regret can be O //maxxep x(p) Σ 11
where || ||+ is the dual norm. However, if one uses the (shifted) negative Shannon entropy as Φ.
this will lead to Of (og(() EL ||4 bound, which is OVVKT) in the worst case. A more careful analysis that avoids strong convexity arguments can be found in De Rooij et al. [2014], but unfortunately this analysis does not avoid problematic lower-order term. To avoid such issues, we make use of the multi-scale entropic regularizer of Bubeck et al. [2019]. If the range of the losses is known a-priori, Bubeck al. [2019] show that for bounded losses and known max, (i)] the regret against expert i then scales as E [max, it is not clear how to prove that the algorithm is stable without a-priori uniform bound on the losses, nor is such a regret bound sufficiently small. Instead, we carefully clip the losses when they excessively large. Combining these ideas leads to the following guarantee for Algorithm I with T and B Vlo((TT):
lolgl (K). However, this alone is not sufficient, as
T Rr(ey) = =I (i((t) (m()===0 (0())=((ViB((TT) (Vr + Vr (it))
Notice that the above upper bound holds with probability one for any sequence of losses and, in turn, leads to the guarantees of Theorem 2.4. A full proof of the above result can be found in Appendix B. Here we provide some intuition.
Proof sketch of Theorem 2.4. First, observe that Algorithm is an instance of OMD adopting the time- vireinarying regularizer v with some additional tricks. We only update Pt if Σ Ease 6. > 0. The only
7

---

case where this is not true is if in all rounds up to and including round f. re(i) 0 for all i E [K], in which case we can simply ignore these rounds in the analysis. From standard OMD analysis (see for example Orabona [2025]), we know that we run OMD on losses &,, for any fixed j E [K],
T ((r, E.) - -((() = o ( (og((Ko) 2m11
K ΣΣ
T
Σ
The Tr. (.Z0))))))))
Tr
At this point, we face our main challenge. We would like to show that pe(t) (i). To do so, we would need to show that ( S 1. We force this to be true by simply setting (i) = if (rr(1) > nh. and (x()) -re(t) otherwise. Of course, there is price to pay for clipping the losses, but this price is negligible:
where pr(1) - (r)
(101)) - (-r((0) = (ne(t) --()) [mx(0)
>
(n((0)> ne. ) sm.ort)) (3) T), Inx(1)
1
re(1))
s
Thus, after noting that l, and - only differ from constant, we have that the regret against expert E(=r((r,& (()r, - (()) = (
((pt. -rr) - (-rr()))) and we can replace -r by the truncated
losses le by paying the cost shown in Equation (3) and use the guarantee from OMD
Σ (p) ex()) 0
Σ (prs (.) -a()) + Σ (n + Σ pl(mmmm))))
=0
log(K/or (K/o)
T Σ (e (m..er
Σ Ep0l0n Iml0maarr)) i=1
K
1/7.j
After controlling the sum by using the definition of ve, the bound in Equation (2) follows
K
Σ veli) t=1 Vv.
+ Σ pm.mm.m)))) S
+
S 44
VV.
1=1
where the first inequality follows from the definition of Ve, and the second follows from, for example, Lemma 4.13 in Orabona [2025].
Regarding computational aspects, note the optimization problem defining P++1 is done on a truncated simplex, thus it does not have closed-form solution but can be computed efficiently with a line-search as done by Chen et al. [2021].
5.2 FTRL-based Algorithm
Taking some ideas from the previous OMD-based algorithm, we derive an instantiation of FTRL described by Algorithm 2. For FTRL a similar clipping of the losses to resolve the same issues that follow from the lack of any prior knowledge of the loss range. However, the FTRL framework has some fundamental differences compared to OMD, which in turn require further adjustments. To understand these differences, we will sketch the proof of Theorem 2.2 below, whose result is obtained by Algorithm with 3= Vlog(As (K). The detailed proof of Theorem 2.2 can be found in Appendix Here we provide the main ideas. We actually prove a stronger regret guarantee than provided in Theorem 2.2:
once more the multi-scale entropic regularizer vi and
Rr(e+)= = -n((') - ( (V++)
T
(b())))
Vi((t))
+
K vr(())
1
Σ
K
(4)
1=1
which then implies the statement of Theorem 2.2.
To prove this regret bound we make use of the standard FTRL amalysis (e.g., see Orabona [2025]) with some additional tricks. Note that, differently from Algorithm 1, we replace the multi-scale entropic regularizer 4/. with its Bregman divergence. This is to ensure the monotonicity of the regularizer, i.e., ( 2 (x) for all x E P. This monotonicity is necessary for the proof of the FTRL. regret bound. The fact that we use the Bregman divergence generated by ti rather than dh directly

---

Algorithm 2 Looe-Free FTRL
Inputs: Number of experts K > 2. learning rate coefficient B 0.
Initialize: p1 (1) < 1/K and (i) < 0 for all i E [K].
f
do Predict pt. incur loss (pc. EE) and observe 4.
Set (i) (pt, Eg) ((() for all i [K].
Set (i) - (1) for all i E [K].
Set 82 + - (1)))
if) E.ge 84 > 0 then
1/2
Set (1) + max
Eest Uo (s) (i(1))
for all e [K].
Set 1/., - //b,(i) for all i E [K].
Set (1) (i) b((3)
110 (Irx(i) s 1 1/mes) for all E [K].
Set Pr+1 arg min Eeso (p. E.) De(pllp1).
end if' end for
as the regularizer also allows us to avoid the log(T) term of the OMD regret bound, at the cost of a R Σ - (i) term in the regret. While this term is prohibitively big when we try to obtain improved regret bounds under Assumption 2.3, in expectation this term scales O(VOT) under Assumption 2.1, thus preserving the desired final bound.
Proof sketch of Theorem 2.2. Since the pe in Algorithm comes from instance of FTRL over the losses 4, we can apply a standard FTRL bound (for example, Lemma 7.16 of Orabona [2025]) to see that, for any fixed [K].
T
log K MT.
K
T
((pr,
2.) - [+()
(5)
K
where Pi(1) = Dc (i) exp( E. Here we reach the main challenge of adapting FTRL to our setting. The third term illustrates crucial differences compared to OMD: the learning rate fh- instead of M/, appears as a multiplicative factor and in the definition of p.. We resolve this issue by rescaling the loss (i) by a factor b, (i)/ (+) (t) in the definition of (i). Still, this rescaled loss can be too big, which is why we also clip the loss when necessary. Specifically, the clipping with
rescaling factor ensures, by the definitions of (i() and T), that ( < (it-(())
b,(1) T (.)))
1h (i) and, similarly, that (7 < 1. Thus, we can bound the third term on the right hand
side of Equation (5) by O (T 11 E (i)) which we already know how to control from the analysis of Algorithm
Another consequence of the new definition of is that it increases the cost of clipping the losses. In comparison to Equation (3), it now additionally presents terms
(nr( (1 bz=)(1) 1 (I2((0) (x)
7h.2
T)t
but the sums involving them are also nicely behaved. Combining all these observations leads to Equation (4).
While the optimization problem suggests P: given by a softmax function, the coordinate-dependent learning rate prevents from computing the normalization constant in closed-form (see Appendix C. for details). However, we can still compute efficiently with line-search in Algorithm from Bubeck et al. [2019].

---

5.3 Algorithm for the Squared Loss
The algorithm we use for the squared loss, Algorithm can be found in Appendix D. It is exactly the same Algorithm 1, but then run the losses
4 Z (z: yrd
(Zt,i - yr)²
where (pes z). The inspiration from this surrogate loss comes from two inequalities for the squared loss:
(a (a-y)² y)² (b y)² 2(y 2) a) (a 6)2
a+ 2 (a- y)
y/ 2 2 + (b y)² (a 6)²
2
By carefully applying these inequalities we find that, for any fixed j E [K].
2t y1)² (Ze. - -Vx)))
Σ pc(1) (z. - 2,)2
(Zr,) 2z)²
(1)60)-000
8
2
The negative quadratics on the right gigt-hand-side of the equation above allow prove the regret bound of Theorem 2.5. We show that, for any fixed j E [K].
T
K pr(i)
(Ze,i
8 + )1)
2,)2
(2t.j 2,)2
Rr(e,)= = O V log( + vo((i)
- E
Σ
2
= - + log(KT))
detailed proof be found in Appendix D.
6
Future Work
One direction to explore is whether the log(T) factor in Theorem 2.4 is necessary to obtain best-of- both-worlds guarantees. Potentially, an improved analysis of the FTRL algorithm will do the trick, as know that OMD be inferior to FTRL [Amir al., 2020]. While understand how obtain best-of-both-worrke guarantees for FTRL with bounded losses [Mourtada and Gaïffas, 2019, Amir al., 2020], it is unclear how adapt these analyses to our setting. Another interesting direction is to see whether the ideas in Section 5.3 can be extended to strongly convex and exp-concave losses. We believe that the former is relatively straightforward. but the latter might be highly challenging. Another relatively straightforward extension could be to adapt to any moment of the loss, i.e., adapt for some a 1, without the prior knowledge of or an upper bound for E, ())
E, (1) [x]
Acknowledgements
EE acknowledges the financial support from the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEÜ program within the PNRR-PE-AL AI scheme (M4C2, investment 1.3, research and innovation action
line Artificial Intelligence), the EU Horizon CL4-2022-HUMAN under grant agreement 101 120237, project ELIAS (European Lighthouse of AI for Sustainability). and the One Health Action Hub, University Task Force for the resilience of territorial ecosystems, funded by Università degli Studi di Milano (PSR 2021-GSA-A -SA--Ln-n 6). AM has received funding from the European Research Council (ERC), under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 950180). This work was partially done while DvdH was at the University of Amsterdam supported by Netherlands Organization for Scientific Research (NWO), grant number VI. 192.095.
10

---

References
Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33:14315-14325, 2020.
Kumar Ashutosh, Jayakrishnan Nair, Anmol Kagrecha, and Krishna Jagannathan. Bandit algorithms: Letting go of logarithmic regret for statistical robustness. In International Conference Artificial Intelligence and Statistics, pages 622-630. PMLR, 2021.
Peter Auer, Nicolò Cesa- BianchB Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th Annual Goundations of Computer Science, pages 322-331. IEEE, 1995.
David Blackwell. An analog of the minimax theorem for vector payofts. Pacific Journal of Mathe- matics, 6(1):1-8, 1956.
Brendan O Bradley and Murad Taqqu. Financial risk and heavy tails. Handbook of heavy tailed distributions in finance, pages 35-103. Elsevier, 2003.
Sébastien Bubeck, Nicolò Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transac- tions on Information Theory, 59(11):71117711) 2013.
Sébastien Bubeck, Nikhil R Devanur, Zhiyi Huang, and Rad Niazadeh. Multi-scale online learning: Theory and applications to online auctions and pricing. Journal of Machine Learning Research, 20 (62):1-37, 2019.
Nicold Cesa-Biane Bianch, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to expert advice. J. ACM, 44(3), 1997. doi: 10. 10.1145/258128 258179.
Nicolò Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice. Machine Learning, 66:321-352, 2007.
Meeyoung Cha. Haewoon Kwak, Pablo Rodriguez. Yong- Yeol Ahn, and Sue Moon. tube, you tube, everybody tubes: analyzing the world's s largest user generated content video system. In Proceedings of the 7th ACM SIGCOMM conference Internet measurement, pages 1-14, 2007.
Gong Chen and Mare Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538-5)) 543,3, 1993.
Liyu Chen, Haipeng Luo, and Chen-Yo Yu Wei. Impossible tuning made possible: new expert algorithm and its applications. In Conference Learning Theory, pages 1216-1259, 2021.
Yu Chen, Jiatai Huang, Yan Dai, and Longbo Huang. uniINF: Best-of-both-worlds algorithm for parameter-free heavy-tailed MABs. arXiv preprint arXiv:2410.0322842,, 2025.
Ashok Cutkosky. Artificial constraints and hints for unbounded online learning. In Proceedings of the Thirty-Second Conference on Learning Theory, volume 99, pages 874-894, 25-28 Jun 2019.
Marie Devaine, Pierre Gaillard, Yannig Goude, and Gilles Stoltz. Forecasting electricity consumption by aggregating specialized experts: A review of the sequential aggregation of specialized experts, with application to slovakian and french country-wide one-day-ahead (half-) hourly predictions. Machine Learning, 90(2):231-26)) 2013.
Genevieve E. Flaspohler, Francesco Orabona, Judah Cohen, Soukayna Mouatadid, Miruna Oprescu, Paulo Orenstein, and Lester Mackey. Online learning with optimism and delay. In International Conference Machine Learning, pages 3363-3377 PMLR, 2021.
Maurice Fréchet. Sur la loi de probabilité de l'écart maximum. Ann. de la Soc. Polonaise de Math., 1927.
Pierre Gaillard, Gilles Stoltz, and Tim van Erven. second-order bound with excess losses. In Conference Learning Theory, pages 176-196, 2014.

---

Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. (s, addaptive regret minimization in heavy-tailed bandits. In Conference on Learning Theory, volume 247, pages 1882-1915, 2024.
Hakan Gökcesu and Suleyman Serdar Kozat. Optimal tracking in prediction with expert advice. arXiv preprint 033000 2022.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 2000.
Dirk van der Hoeven. User-specified local differential privacy in unconstrained adaptive online learning. Advances in Neural Information Processing Systems, 32, 2019.
Dirk van der Hoeven, Nikita Zhivotovskiy, and Nicolò DesanBBancchi. A regret-variance trade-off in online learning. In Advances in Neural Information Processing Systems, volume 35, pages 35188-380 88-355000, 2022.
Jiata Huang, Yan Dai, and Longbo Huang. Adaptive best-of-bott-worldd algorithm for heavy-tailed multi-armed bandits. In International Conference Machine Learming, pages 9173-9200. PMLR, 2022.
Wouter M. Koolen and Tim van Erven. Second-order quantile methods for experts and combinatorial games. In Conference on Learning Theory, pages 1155-1175, 2015.
Wouter M. Koolen, Peter Grünwald, and Tim van Erven. Combining adversarial guarantees and stochastic fast rates in online learning, Advances in Neural Information Processing Systems, 29, 2016.
Kyungjae Lee, Hongjun Yang. Sungbin Lim, and Songhwai Oh. Optimal algorithms for stochastic multi-armed bandits with heavy tailed rewards. Advances in Neural Information Processing Systems, 33:8452-8466 8462, 2020.
Yun and Ben Jones. The use of extreme value theory for forecasting long-term substation maximum electricity demand. IEEE Transuctions on Power Systems, 35(1):128-139, 2019.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and Computation, 108(2):112-661, 1994.
Zakaria Mhammedi. Efficient projection-free online convex optimization with membership oracle. In Conference on Learning Theory, pages 53 5314-5390. PMLR, 2022.
Zakaria Mhammedi, Wouter M. Koolen, and Tim van Erven. Lipschitz adaptivity with multiple learning rates in online learning. In Conference on Learning Theory, pages 2490-2511, 2019.
Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the Hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019..
Gangadharan Muraleedharan, Carlos G. Soares, and Cláudia Lucas. Characteristic and moment generating functions of generalised extreme value distribution (gev). Sea level rise, coastal engineering, shorelines and tides, pages 269-276. 2011.
Francesco Orabona. modern introduction to online learning. arXiv preprint crXiv:1912.13221337 2025.
Francesco Orabona and Dávid Pál. Scale-free algorithms for online linear optimization. In Interna- tional Conference on Algorithmic Learning Theory, pages 287-301. Springer, 2015.
Laurent Orseau and Mareus Hutter. Isotuning with applications scale-free online learning. arXiv 2024.
preprint
Steven de Rooij. Tim van Erven, Peter D. Grünwald, and Wouter M. Koolen. Follow the Leader if you can, Hedge if you must. Journal of Machine Learning Research, 15:1281-1316, 2014.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold'em. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
12

---

Volodimir G. Vovk. Aggregating strategies. In Proceedings of the 3rd Annual Workshop on Computa- tional Learning Theory, 1990.
Olivier Wintenberger. Optimal learning with Bernstein online aggregation. Machine Learning, 106 (1):119141, 2017.
Olivier Wintenberger. Stochastic online convex optimization. application to probabilistic time series forecasting. Electronic Journal of Statistics, (8(1):429-466 464, 2024.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49, 2021.
13

---

Appendix Contents
A Technical Results for Section 4
14
A.1 Proof of Lemma 4.1
14
A.2 Remarks Fréchet Distributions
14
A.3 Proof of Proposition 4.3
15
A.4 Discussion on analyses of existing algorithms
16
Regret Analysis for Online Mirror Descent
17
B.1 Adversarial Environments..
17
B.2 Self-Bounded Environments
23
C Regret Analysis for Follow The Regularized Leader
25
C.1 Computing the Update in Algorithm 2
30
D Technical Results for Section 5.3
30
D.I Proof of Theorem 2.5
30
Comparison with Gökcesu and Kozat [2022]
34
Details on the Experiments
35
A Technical Results for Section 4
In Section 4, we discussed lower bounds for the lower-order terms. These lower bounds are achieved by adopting specific binary random variables in the construction of the losses. This is shown in Lemma 4.1 and its proof is provided in what follows.
A.1 Proof of Lemma 4.1
Proof of Lemma 4.1. The fact that E[X]] = 1 follows by immediate calculation after observing that each X, is binary random variable. By independence, also have that E [maxje[]]] X,]
vn(1 (1- 1)) The result now follows from observing that 1/2 (1 4)" < 1, where S exp(-z).
used the inequality
A.2 Remarks on Fréchet Distributions
Here, now discuss another family of random variables that guarantee similar properties. This family is that of Fréchet distributions [Fréchet, 1927]-see see also Muraleedharan et al. [2011] I] for reference.
We denote by Fréchet(a, s, m) the Fréchet distribution whose parameters are the shape parameter > 0, the scale parameter > 0, and the location (of the minimum) parameter R. Its cumulative distribution function (CDF)
m
P(X < exp
for m. where X Fréchet(a, s, m). If 1, its expected value corresponds E[X] + sI(1 1/a.,, where I(2) -000 : exp(-t)dt for >> 0 is the Gamma function.
Lemma A.1. Fix any n E N (0). Let XI...., Xn ~ Fréchet(a, s, 0) be i.i.d. random variables with > 1 and s > 0. Then, for any < and any E [n).
E| E[x,1 = r
14

---

Furthermore,
Ilmax(XI,..... .n]] = n // (1-2)
Proof. All results standard. Here provide explicit calculations for completeness. First, observe that for any ~ Fréchet(a, s, 0) we have that
(x S xx)= =P =P = = exp (- x11//
(-( 8
I
-a/3
exp
showing that X (rrccht((a//o) (a/ 0). As a consequence, E s T since 0/ >
Second, let Y max ..... Xn) and 0. By independence, one has
P(Y S 5 =
n 6EIn]
[X, S 3}
II P(X, $
jEImi
II jE
exp
- (w//)
exp (- (n//a/
(-(ntaa))
which means that Y Fréchet(a, /////,00 s)). Since a > 1, its expectation is thus E[Y] n/ sT (1 - 1/a).
Keeping the results from the lemma above in mind, we can consider more specific case where the Fréchet random variables have scale = and a Then, for n KT and ,3 2, we clearly have that their second moment equals [(1 2/a),, whereas the expectation of their maximum corresponds to (KT))/aT(1 1/a). This shows that the i.i.d. Fréchet random variables as described above behave somewhat similarly to the random variables of Lemma 4. we employed in our lower bounds.
Moving back the original construction from Lemma 4.1, we can adopt it to prove the main lower bound on any regret guarantee containing the Mr term (or a constant fraction of it). This result from Section is stated in Proposition 4.3 and here we provide its proof.
A.3 Proof of Proposition 4.3
Proof. Let (i) = Pr,i + Er,iSt,i, where μr, E [-,, &,, is sampled from a Rademacher dis- tribution, and ετ, is sampled from the distribution specified in Lemma 4.1 with KT. Let El= H4.K = 0 and let DT M4, > 0 for i + K. By assumption, we have that
T K
T K
((()) (((K) -((k))
[ra(0]]
RT = E
=E E
((())(()) < B +
max
[E[T)
15

---

Observe that
I
max [E(T)
[r((t)
=R
max [E(T]]
(e(1) - (pt, f
E
max [E(T)
(le(()) [((K) (6.(KK))))))))))))()))) - (pe, b:)1
(reverse triangle inequality)
(16((0) 4(K) - (x((K))]
E
max [E|
E
max [E(
(e(1) - 6((K)) - -E
max
Ira [rx(
[E(T)))E[K
> E [E(T]
max
(1e(00) -11
E
Ine(t)
[E(T))E[[]
(reverse triangle inequality)
2 E
max
(e(1i]
IE
max lee [e((K) [E(TT]
-
max [E(T].i[[K]
lr:(0)]
[E((T),EE[K]
E
max [E(T],JE[K]
JE
max [E(T]
E
max [E(T),
[ra(t)] - 2.
By carefully using the properties of the random variables εs,5 from Lemma 4.1, we have that
E
max [E[T]
2 (1-
VKT
as well as
VKT
(1-
1-
T V
max [E[T]]
S
KT
K
for any fixed j E [K], where the last inequality follows from the fact that (1 x) 2 næ for all
S and all 1. Therefore, by rearranging the terms in the previous inequality we obtain
E
max [E)
|r((0]
VT
(11-)
)
1 1
KT
VK
16
where the last inequality holds for any K 2 2. Hence, we immediately have that
B + E
max [E[T),E([]]
In((0] 2 Bj + 16
VKT 1.
Finally, we have
Ee(((1)7]] = 14, + 2pt, Ee(e,,]] + E.[e2, 2 22, = 2
33 VKT
since K,T 2 2, which concludes the proof.
A.4
Discussion analyses of existing algorithms
Our results from Section 4 show that the lower-order terms are a problematic component of the regret bounds of cxisting algorithms. In particular, have shown that the lower-order terms can be larger than the ideal /0T log K in the case heavy-tailed losses with bounded second moments. It is important to note that general argument does not depend on the specific algorithm consider, but rather on regret bounds involving terms such as Ly or My. Hence, generally speaking, one may believe that the presence of Ly or My in the regret guarantees could be artefact of a loose analysis. However, here we show that this is not the case for most existing algorithms.
To illustrate, let consider a simplified view that captures the essential mechanism. The algorithms in Table are effectively sophisticated modifications of the exponential weights (EW) algorithm designed to adapt to HT m [i)(... Their sampling distributions are of the form pc(i) oc
16

---

exp(-n4((()), where we assume a fixed learning 1) > 0 for simplicity. A crucial aspect of these adaptive algorithms is choosing learning rate related to Hr, often resembling min(a, a, Hy }. where a > 0 represents some cap and where we assume that Hr is known. Their choice ensures the control of terms like log [ex_,, analysis of EW-based algorithms.
which an essential component in any regret
Now, we construct sequence of losses for which the regret of such algorithm is always least E|log( 4/3) Suppose K 2 5 and let ((( = 1 + Et for each E [K 11. where Et, follows the same distribution in Lemma 4.1; for action K, we instead choose ((KK) 0. By Jensen's inequality and the definition of pt. we have that
T
RT
E
Pc.
CT)
T
2 E
log (Bipp [exp(-n)e
K
T
E
log( RK)
log
Σ 1=1
cxp
-17
" (0)
1
"7
1=1
2 E
log( K)
- log [1 + (K -
1
exp (T]
17
where the last inequality is due to the definition of (t). is safe to assume that n7T < 1, as otherwise would obtain vacuous upper bound from the standard EW analysis. Therefore, we have that
Rr 2
(K)
log (1 + (K-
1.5-191 1)/2)
77
2
log K)
log (3(K-11)) (-KK-1)66 1)/4)
77
2
log(4/3)
2 LT log(4/3),
where the last inequality follows from the definitions of and Ly = E[Hr]. This suggests the regret lower bounded by a term proportional to the maximum loss range. For algorithms like Squint that run EW on the surrogate losses like (2) - (i)) similar but slightly more involved argument can be made. Consequently, the Lr (or Mr) term appears to be unavoidable in the regret of these algorithms.
Similarly, regarding Section 4.2, the existing algorithms for the squared loss setting are also fundamen- tally related to EW, adapted to quadratic losses. Their learning rates are typically dependent on the range max, iz. ya| in a manner analogous the dependence on l/T described above. Therefore, we believe a similar limitation applies, making it unlikely that a different analysis of previous algorithms could circumvent the dependence on lower-order terms in their regret.
B Regret Analysis for Online Mirror Descent
In Algorithm we only update pt if E Eese Te > 0. The only case where this is not true is if in all rounds up and including round t, rt( 0 for all i E [K], in which case we can simply ignore these rounds in the analysis, which is what we do: throughout this section we assume that ह > without loss of generality.
B.1 Adversarial Environments
We now analyze the regret incurred by Algorithm for adversarial and self-bounded environments. We start by reminding standard lemma.
17

---

Lemma B.1 (3- (3-point identity. Chen and Teboulle, 1993). Let X C IR be non-empry convex set,
v: x R be strictly convex and differentiable on int (X) + and By be the associated Bregman
divergence. Then for any E X and any y, 2 E int (X), the following holds
By (x. v) By (x, =) By (z. v) + (x - V (2) Va
We then have the following result about the regret of Algorithm 1. Theorem B.2. Consider Algorithm I run with parameters (0,1] and 3 > 0. Then, with probability one, for any i E [K] we have
Σ (p lc)
< (VaT + +53+ + log (K/a)
Σ 8z + (VaT
log (K/a)
+ 28
Σ
T
Up (i*)
3
3
Furthermore, setting a = + and 3 = Vlog (KT) gives
(1 (Vroc (KT)) (KT)
T
T
(p: ec+ ex, ())==
Ut
0t (i+)
Proof. Let 1* E [K] be our point-mass comparator, let & = -re for any E [T], and recall that
Pa = E EPEP: :Pp p 2 K 11] is the truncated probability simplex, for any a > 0. Define truncr = Et E,) to denote the cost of truncating the losses for any x E k and, by convention, let truncr(Pi.r) ΣTT (pe, le Ee) where Pı.T (PI..... PT). Moreover, define RT((g)
Et q, (i) for any q E P. We consider the following regret decomposition:
T
T
Σ (pt ex. (1)
Σ
Pt Cir 4-
-Te)
Σ
Pt Ci Es
t=1
Pr eir, Eo
Pt Cir Ee
=truncr (pirr truncr (-E.)
=x((
where we added constant vector (pe, Ee) 1 = =1 4--4 Ee to le at each term of the first sum in the second equality because, for any I, both P: and e;- are probability distributions and thus (p. ex, e 1) = 0 for any E IR. The first term is just the cost of truncating the losses, and the second is just regret of OMD on the truncated losses. We start with the latter.
Step 1: control the regret of OMD. Fix any t E [T]. Note that by the first-order optimality condition of P++1 have, for any u Pa.
i + Vel (p+11) Vih (pt). Pc+1 2 0.
Following a simple sequence of derivations also referred to as the 3-point identity (see Lemma B. the inequality above be rewritten as
T po (Dr (ullpe+i) + Dr (petillps) - Dr (ullpx)) 2 0.
(6)
This inequality cannot applied to Ry (ex+) since eg does not belong to Pa. Instead, we use mixture of ex- and the uniform distribution, u. (1 a) + - E Pa. and notice that by
18

---

definition of un- and a triangle inequality
T
Rr (ex+ - Rr (us=) =
Σ
-ir Cir 4s)
1=1
1 C Σ Pt
(definition of u.-)
K
K
T + 0 Σ
< 8
Ee
(1)
(
K
Next, following up with Sauchy-Schwarz inequality,
K
T
Ri (es+) - Rr (ux+) 5
1
T
(1) + +01
T T le (1t)²²
K
T
K
S
le (1)² + +av
TT) r Le (1-)²
(Jensen's 's inequality)
T K
T
S
aT
Σ
Σ
Pc (1) (1) + ta
T Σ
le (17)
(p= E Pa)
t=
1=1
T
Vaa
+
Σ v
(i+)
(Cauchy-Schwarz, 23 S P)
Therefore, focus on bounding Ry (u From Equation (6), we have
Ry (ux.) S Σ - De (pe41 (pd) + De (ux-llpe) Do (u Ilpe+))).
The first difference within the sum can be analyzed with local norms arguments [Orabona, 2025, Section 6.5]. However, we do not have control over the range the losses, thus we cannot use the standard arguments and instead resort to specific learning rates to account for this. On the other hand, the second difference is almost a telescoping sum and requires a more careful analysis for the same reason. We start with the first. Denote p++1 = arg min (p, E, minimizer of the unconstrained optimization problem, and note that for any i [K], Pt41 (1) Pe (1) exp -e (i) < 3pt (i), where the inequality holds by definition of the losses which satisfy t, (1) S T
D. (wllpee) the
1. Since the function the is twice differentiable on RK by Taylor's 's theorem there exists 2x E [Pe, 11+ such that D, (1tt) 1/ 11A - pell Therefore, the first difference in the inequality above becomes, for any t E [2'.
(p: -e) - Dr (1xx) S Pt - Pr41, T.)
- Dr (Pt+1llpe)
(optimality of Pr+1) (Taylor's theorem)
Pt pet1, [.)
2 llée. Pell pella
1
$ max
{
(I) Ei)
1
||
}
RER
2
(V(((()))
19

---

where the last step follows from the Fenchel- Young inequality applied to the convex function Illlll Noting that 1/ (z+) = Diag (nh O 2+) -1 we further have
(p: P -1) Dr (pc+allp)) -
n (1)
K
-
nrPii (1) (1)&(() (1)
(2t $ 3pt)
2
3,
(2) Ea (1)
(definition of m))
2
1=1
maxx
Σ
Us. Σ. Us (0)
33
( P.).
ΣE
===1
U,
Summing up for all / (7], we obtain
T
T
T
Pt - PI-11..)) - Dr (Pc+1llpd) -
38
0
S
38
Σ
T2:
2
1=1
Σ
s==
-=1
where the inequality follows from, egg., Orabona [2025, Lemma 4.13). Moving on to the second difference, we have
(De (pd)) De (ux- (lPe41))
Dr (u--llpt) Dr (ui. (|pT+1) +
(Dr (ui. ((p)) - Dr (ui (p(+1))
T
= =1 (u:llpp) - DT (wi- IIPT+1) +
Σ
(De (ux- (1p)) D. (uc- lIp:))
2=
$ Di (up ((pp) + Σ (De (urllp)) - Di-1 (ux+))p:))
where the second equality is due to telescopic sum, and the last inequality is because Dr (ug- 11) 2 0. The sum above is given by
T
(De (l:)) De-1 1 (Mg llpe))
T
K
1
Us (t)
U/- (1) log
- up- (1) + Pe (i)
T/ T/-1,
(i)
1=2
im
T
K
1
1
Uqa (t)
M--1.1/ )
(2) log
+ Pt (i)
nt,i
Pi (i)
1=2 8m
20

---

where the inequality is due to having 71 S 1,1 and Ui. (t) 2 0 for any i and any t. Since E Pa. we have for any + 2n that (a)(()
I 1, i.e., log
Me- (i)
S 0. Thus,
Pr(3)
T
(Dr (uir l(pe) De-1 (u,. lpr))
T
T K
Up-
1
ui
(i")log
log
pt (i)
T/ 111-1,3"
Pr (i+)
7/t-1,3
1=2
1=2 ==1
log
(K/a)
T
1
1
Pt (i),
1/-1,
t=1
i=1
2 k. and m7 0 for the first sum and added the non- negative term for t = 1 in the second sum. For the remaining sum, notice that for any t,i, we have 1
where we used ui- (i*) I 1, Pt (i*)
7. = T,, oF. ne m-14) I nus nP,0
due to n7, I 7h-1,5 Using the
definition of the learning rates, we get
1
1
1
S Mt.i
n-111
7/-
max
Ense Us. Exse
Uss (i) max EEeee Us. Ence Us (i)
Vymax max Eese Us. Eose Uo (i)}
max (02,
B max Ense Do Ense Uo (i)
01 + 14 (i)
(8)
B
Σ
Ee U6
Therefore, adding everything up
1
0. 24 (t)
Pr
(i)
Pt (i)
1h,1
T/--1,
Σ. 8.
t=1 i=1
2 T
02
(pc P, definition E,)
3
Eest
t=1
T
where the last inequality follows again from Orabona [2025, Lemma 4.13), Putting it back into the previous inequality, we get
Σ (D. (ux))pp)) - D2-1 (u4. (lpe)) <
T
log (K/a)
4
T
3
1=1
log (K/a)
T'
T
Ut
(i+)
+
Tt
+
1t
B
3
Finally, the regret incurred by OMD on the truncated losses is bounded by
Rr (er) s (VaT 33 + 4+ log (K/a)
Σ 0e + (VaT+
log (K/a)
Σ
(it).
3
3
21

---

Step 2: control the cost of truncation.
We have
T
K
truncr (PI.T) =
Pr (1) (1) 21)
Pe (1) ((2())))(((00)) (1) n,,i)
(definition of 2,
Pe (i) 4 (1) (1)
1 144 (1) nE.
(pe 2 0)
T K
Pe (1) m.)
==
Plugging the definition of the learning rates T/e obtain
E, (i)
truncy (PI.T) S
3
Pr (i)
(definition of m))
1=1
max
ESm s=1 Us Ex v/a (i)
T
K
Pt (1) & (1)²
< 8
1=1
==
Us
T
11
1=1
===1 0
S
2/
Vt
where the last inequality follows from Orabona [2025, Lemma 4.13). Likewise,
T
truncr (-exx) s 23
Σ Up
(i*)
Overall, our regret is bounded by
T
(pr
Ri)
1=1
VVT + 53
4 + log (K/a)
T Σ 0z + (VoT= + log (K/a)
+ 28
Σ
us (it)
3
3
Theorem B.2 is more general result and it is indeed stronger than what originally stated in Theorem 2.4. In particular, we are able to show that the former result implies the latter under Assumption 2.1. This is illustrated by the following corollary.
Corollary B.3. Suppose Assumption 2.1 holds. Then, Algorithm with 1 and B Vlog(KT) guarantees
R7 = (VOT
Proof. Recall that, by Theorem B.2, Algorithm I with and B (K) already guarantees
[x)= 0 (1 (1og(KT)
T
T'
T
(p. - eie, (.) =
02 + Σ
Σ vz v(( 1=1
(9)
22

---

for any sequence of losses. Now, focus on the 8n and 2t(2) terms. First, for any E [K], we can observe that u, (i) satisfies
27
[, E,
((()) Σ P.()).
(definition of v,(1))
E
Σ po(i) (E((1) -(0)
$ E
((()){e(())ed00)) Ec(i))
(Jensen's inequality)
s (2B,(((1)) +2E,
Σ P((G)G)²
(using (a -b)² S 2a² + 2b and Pt P)
- +2
> p(()) E. [40)
40
where the last inequality follows by Assumption 2.1 and the fact that Pt E P. Then, we can move to & and notice that, by its definition, it satisfies
K
E, [ E.
Σ
(10)))))))
Σ Eplooaa ) ==1
K
E,
Σ Po(
Ec(i)
(definition of ot()))
E,
Σ (0)))
(using V[X] E
Σ (1) E. [10
1=1
50.
where the last inequality holds by both Assumption 2.1 and the fact that Pt P.
At this point, we can observe that Rr max;<<[]] E[ - e,+, 4,}, i.e., corresponds to the expected value of the left-hand side of Equation (9). We can then focus the expected value of its right-hand hand side (ignoring constant factors) and, by applying Jensen's 's inequality with respect to the square root and the tower rule of expectation, infer that
T
T
E
log(KT) KT)
Σ
(Te + vz((*))
s log(K") E
Σ
ER [it] + E. [ix()*)))
s /5T (og(T))(TT)
This concludes the proof.
L
B.2 Self-Bounded Environments
In this section, we provide a regret bound for self-bounded environments defined in Zimmert and Seldin [2021].
23

---

Theorem B.4. Let Assumption 2.1, 2.3 hold, and consider Algorithm I run with parameters o E (0, 1).
O. We denote C3 (K,T) 2/ 73
++2log(K/or
Then, we have
16 (6C (Cs(KTTVvCC
iC
16Ca(K,TY''
E [ S
Ami 8Ca(K,TivBC
Vamin
mmi
otherwise
Vog (KT) gives C3 (K, - -
Furthermore, setting and B
and (6CT(K
3600 ( 120
log K
if
E [
Amin
Amin
Amio
120
(TT
otherwise
Amin
Proof. From Jensen's 's inequality applied to the regret bound proven for adversarial environments in Theorem B.2, we have
27 (
E E| (e &C
E
(i)
4
Σ Pi
1=1
i=1
T Σ
K Σ j=1
(2K,7)
E
&
(1*)
Pr ()
where Ci (K,T) VTT + 5, 4+oog(K/o) and C2 (K,T) voT log(K/o) 233 Observe 8
that for any E [T'. the expectation in the first term a variance that can be bounded by the second moment (V [X] [x3] for any random variable X)
K
K (e(1) - P ()4()) -10
E,
Σ Pe (i)
5=1
27
E,
Σ Pt (i) (4)(0) (.)))))()))) Σ Pt (1))0))))00))
E,
Σ Ex
Pe (i) (fe (i) l, (i²))²
Further, using the inequality (a 8)2 2 (a² + b) for any a, E I,
K
K
E,
Σ
Pc
(1)
(1) - Σ Pt (0)66)
< 2E,,
Σ Pc (i) (4e(0)++4660))) inffa*
< 40 (1 Pt (i*))
where the last inequality is by Assumption 2.1 and (pc. n1 1. Likewise, for the second term have by Jensen's 's inequality
4a
-
Pe ())
S E,
Σ -2()6())--()
1=1
En( (20)0((+400))7)
2E,
< 40
Pt (i))
24

---

where the last inequality is again by Assumption 2.1 and (p..1) = 1. Denote Amin min As,
and C3 (K, T) C₁ (K, 7) + C2 (), Combining the above and Assumption 2.3, we find that
for any À E (0, 1],
E R
= (1 + X) E RTi AE [R
s (1 - C3
E Σ (1 pe (it)
AAmin E
Σ p ((9)
Ac
T
4 C3 (K, o
Ca
Σ (1 pe ((+))
AA
Σ (1 (1-
+ +
Using the inequality of arithmetic and geometric means, i.e. labl = inf,>0
a²
2か
27
?
4 + A) C3 (K,T)²
T
E [T = inf 7>0
+ t
Σ
(1 Pe (i-))
7
AAmin
(1 -1-pu Pt (i')
+ +XC
1=1
(1 + A)²²
C3 (K,T)²0
+ +C
A
16C (K,T)²0 +xC,
Ammin
where the first inequality is by taking 7 = Ammin and the second by S 2. In particular,
{I, VAmiaa
TTVe
setting À min
gives
16 (K, 2 max
VmminC
} min
{ Amin C
{1, 4Ca (K, v0
[T]
C
Amin
4C's (K, T) v0
16 Ca (K, 0
8Ca (K,T) VOC
Amin
Vmmin
If C >
(6,7)) then A =
4C,(K,T)vO and the previous inequality can be improved to VAmia
Amin
8 8 (K, vOC
E [ < VA min
Recall that C3 (K,7) = 2T + 7B + 4+2 4+2log(K/o) k/o) Setting a 1 and 3 Vlog(KT) gives
B
C3 (K,T) < 6 9 log (KT) S 15 Tog (KT) since log (KT) 2 Finally, we obtain
3600 (oT()e KT) 120
if C
(6C,(K
E RT <
Amin
Amiu
Ania
120
(T
otherwise
Amin
In the special case of stochastic environment, C = 0 thus we set X = 1 and obtain E [Rr] (og(
C Regret Analysis for Follow The Regularized Leader
In Algorithm 2 we only update the prediction if Σ e51 > 0. The only case where this is not true is if in all rounds up to and including round 4, ri()) = 0 for all E [K], meaning that the cumulative regret up to round is null. In this case, we can simply ignore these rounds in the regret analysis, which is what we do: throughout this section we assume that 2 0 without loss of generality.
25

---

Theorem C.1. Consider Algorithm 2 with parameter 3 > O, providing predictions pr, ....... Pr E P over a sequence of losses E,,..., Cy. Then, with probability one, for any E [K] we have
pt e2)
log(K)
T
5 5 log(K)
T
K
23
Σ ve(i+) +
+ 53
Σ
03
Σ
ve(1)
B
Furthermore, setting B = Vlog(K) (K gives
(1 (LOOCL))
T
K
(pt ev, le) = O
Σ 1=1
1t
+
Σ
vo(
Σ
1=1
t=1
i=1
1=1
Proof. Let i" E [K] be our point-mass comparator and let & -re for any t E [T]. First, observe that the regret can be equivalently rewritten as
Σ (p:- bx,
Σ (p, t=1
this follows from the fact that replacing & with & only leads to a difference (pr - e,, -
(Pt E c 1) = (Pt, c 1) - (e c 1)- = c-cco c = for the constant = (pe, Li), by definition of 4. As in the proof of Theorem B.2, we take the same definitions of truncy and Ry, and consider the following regret decomposition:
T
T
E 1=1
ei) = (p. P er. 4 -
+
Pt ci., c,, E.)
-tuunerr (PI:) +truner(-e..)
= (e,))
where the first term the cost of truncating the losses, and the second is the regret FTRL on the truncated losses f Ey. Let us first focus on the former term.
Before proceed, one final remark is in order. Recall that Algorithm performs predictions defined such that
Σ (p. + Dz-1(pllpo)
Pt = arg min PEP
for any > 1, where 1 E P is the uniform distribution, while Observe that we can define 1/o.; = B/ (never used nor set by Algorithm 2) for any E [K] and, thus, we can equivalently denote P1
E arg min Do(plipo)
PEP
- p(t) + po(i)) is minimized at Po. We remark that, while this step appears to require knowledge of e before computing the prediction Pr, it is only part of the analysis and not algorithmically performed.
because Do(plipo) = JT ΣK (p(1)
Step I: control the cost of truncation.
We can begin by focusing on truncy (Pi.). Observe that
(runcy(PI.T)
Pc. Ea 2,)
K
(()) Tc(0)
K
[0(00] (1- by b1-1(1)) (16(0) m.
- + |0(00 1 (100)> m 1
())
(1)
26

---

where the last equality follows by definition of (1), after observing that bi-1(1) S be(i). Now, by using the definitions of (i) and Th, observe that
K Σ p(()) ((() (1- b(-1(0) ) = )
bi(i)
ne,
K
[((ii) (i)
(be(t) b0) (12(00) = m. nnd)
pr())
K
me, |e(0))
(1-11)
(1((0)) $ 1
m=128/
77.s
K
1
1
(i)
Me,
1/-1,1
1=1
20
Bv
Σ
E.st Us
for 1. >>> 1, where the last inequality holds by Equation (8) given that the learning rates , have the same definition; the same bound holds similarly for t = 1 by observing that bo (i) = 0 and, hence, we have
(1(1)11((111 (1)
1 n1.1
1
(t) m max 01 v2(1)}
B
K
1
201
261
$
pz (1()) ma (1) =
<
3
B
/ 01
where the second step follows by Jensen's inequality, At the same time, we have that
Σ px( (2(1)) 1 (1((0)
K
1
1
Σ
K
(i
(1))
(16(00)
> 1
nh
1/1
K
(i)
30r
We can therefore combine the above inequalities and, together with Orabona [2025, Lemma 4.13]. obtain that
T
2 B
2
truncr(pI.T) <
B
2
3
Σ
E.se Us
t=1
Similarly, we can see that (runcr((ee)) similarly satisfies
Bruncr(-ex.) = Σ
Cxe , Ea {,)
T
(((it) - (((0))
[(6((7)] (1 bi-)
1 (1((7))] < - + |<(07) 1 (12((77) >
ne.3 )
bi(*))
27

---

Using similar calculations as before, it follows that
Ee(tt) (1 b)-1(;))) [E(00)]
)
1
1
T
(bi(t")
b--1(1")) =
n1,6"
1
1
T
T
0g
+
vr(i))
3
where we used the subadditivity of the square root in the last inequality, and also that
nh (()))² S ve(i²)
T
Σ (0)))((E)))) "
2,
Σ ve(i))
Es (it)
where the last inequality follows again by Orabona [2025, Lemma 4.13]. Hence, we similarly conclude that
T
1
1
truncr(-et.)
Σ
Ut 23
Σ vo(i))
B
3
t=1
which implies that the total cost for truncating the losses is bounded from above as
T Σ vr(t))
5 28 +
trunct(Pi:r) + truncr(-ess) S
Σ T=1
8e +
23
+
3
Step 2: control the regret of FTRL. Let now focus the latter term in the regret decomposition, that is, the regret of FTRL on the losses E1,...,,y lr. Consider any E (T] and define
Pe+1 = arg min {p, (p. + D.-1(plpp))
PERK
Note that for any E [K], (1) (1) exp( (m)-1,((6(1)) (1p( by construction of &, which such that
Th- 1 1o (1) 11 (i)
be
1 (1)(1)
S 1) This [1)) (1)(1)
S
b
nh.s
for any i E [K] and t > 1. while it immediately holds for t 1 since (i) 0 for any i.
Let for = (-1po)))))) be the regularizer used in the FTRL update. Observe that şr non-negative and twice-differentiable with Hessian having inverse (V)))(x)))
Diag( @ x)), and that (()1(()) (z) for all x E I Then, by standard results FTRL with time-varying regularizers pa....,rr4. (e.g., see Orabona [2025, Lemma 7.16)), we obtain
T
Rr(er) S (er+)(er))
+ 2
Σ
&
(10)
for some point z on the line segment between p: and 1 this also follows by the monotonicity
of spt, i.e., Spe (p(41) S 1 The point 2; is such that 2,( S max (p)(1), Pe+1 (i)) S (1)
for all i e [K]. Therefore, given the definition of the local norm, the second term of Equation (10)
28

---

satisfies
T
T
1
&
(1)
2
(V2
2
1=1
3
(using =x(1) 3pp(t))
3
b (1)²
(using [2((1) S
be_ (1))
(x)
by(
38
(1)
Σ
(c()),((1)
(definition of т 1)+)
2
(1)2
38
(1)))
(using b._ (i) S by (1))
2
(i)
38
(definition of (i) and ūx)
S5 U3
33
Σ
Vt
where the last inequality follows again by Orabona [2025, Lemma 4.13). On the other hand, the first term Equation (10) is such that
log(K)
117,i-
K
1T,
log(K)
-1
T
T
1
T
1
K
1
T
Σ
ve((t)
+
Σ 1=1
Up
+
U1
(
8
3
8
K
(=1
1=1
im
log(K) -
Uz (i+)
log(K)
+
1
Σ
Up
(i)
B
K
Combining all the above results together leads to
(Pt - es,, ke)
< (og(K) 2,3
T Σ
5 55+ log(K) + 53
T
(i))
B
1=1
We can now show that Theorem C.1 suffices to prove one of our main claims from Theorem 2.2. This demonstrated by the following result.
Corollary C.2. Suppose Assumption 2.1 holds. Then, Algorithm with Vlog(K) guarantees
RT RT = 0 0 (VoTlog(K)
Proof. Recall that, by Theorem C. Algorithm 2 with B Vlg((K K) guarantees
(1 (og((K)
T
T
T.
K
T (1I)
Σ (pt - c;,, (x) =
Σ
0 +
Σ ve((t)
+ K
(i)
29

---

for any sequence of losses. Additionally, in a similar way as in the proof of Corollary B.3, we have that E, [by] < 0 and that E, [v,()) v 40 for any i [K], under Assumption 2.1.
We can analogously observe that Ry = = E[
cg {a)] or, in other words, that Pr
essentially corresponds the expectation of the left-hand side of Equation (11). Then, we consider
the expectation of its right-hand side and, by applying Jensen's 's inequality with respect to the square root and the tower rule of expectation, we can finally show that
K
E
log K)
(Je + ve(
+
(i)
K
t=1
log(K)) E
Σ (E [o.] B (i)())
E
[x(oa(i)]
K
==
Cv OT log(K)
for some constant C > 0. This concludes the proof.
C.1 Computing the Update in Algorithm 2
We briefly discuss the update defining P(+1 in Algorithm 2. For any 7) E IR consider optimiza- tion problem of the form pnP (p, L) D (pll4), where gK . P, and
D (pllg) = Σ 1=1
K
1
p())
log
(
p (2) (1)
Tr
As the probability simplex is compact and the mapping + (p. I.) D (pllg) is continuous, the infimum is attained at some p" P. The Lagrangian L (p, A) of the optimization problem is defined for p E RK and À R as
K Σ m
(1) (i)
L A) = (p.
(1)
log
(() 900)
+ +) 1).
For any j [K], differentiate with respect to p (j) to get
dC
1 "
p(j) (
1
p(j)
Öp (j) (p. T.
log
+ T. +
log
9 (j)
Setting it to zero, get
p" (1) = 7 (-p
(Z) + Al)
One then wants to find the value of À by enforcing the constraint p², namely (p', 1) = 1. which gives the following condition:
K
Σ
AJ)
1. =1
If the learning rate did not depend on the coordinate, we could take the term that depends on À out of the sum get closed-form solution. Plugging back into p* would give a softmax distribution, but this is not possible here. Instead, one can efficiently compute the normalization constant À with line-search.
D Technical Results for Section 5.3
D.1 Proof of Theorem 2.5
Proof. We start with some useful inequalities. Let a, b, ye E IR and let 2 = - for any E [T]. By the 2-strong convexity of the function I + (x yx)) we have
a a
2
(a (a)b)² b)²
V1
s (a - vr) + 2 (b yz)
(12)
2
2
8
30

---

Algorithm 3 LoOT-Free OMD for the Squared Loss
Inputs: Number of experts K 2 minimum mass coefficient a E (0, 1], learning rate coefficient
8 > O.
Initialize: p1 (i) t 1/K for all i E [K].
fort = ,,..., do
Receive Z₁,i for all E [K].
Set Ee f- EE=1 Pc(i)
Observe yt-
Set (i) + (2r,((z(- - y1) + (zz,s )²)
Set rt (i) <- ((x,Pe) - le (i) for all i E [K].
Set U2 (1) re())2 for all i [K].
Set Ug < Ei (o()
Set 1/,,5 < B max { Eoge Us Esge (0( 1/2
for all i E [K].
Set &g (i) f- -ra (i) (Ir (i)l S 1/n.a) for all e [K].
Set p1+1 - arg min (p, 4,) + De (plppt).
end for
Furthermore, also have that (a - y1 (b - y=)² (y== a) (b a) - (a b)? sometimes referred to as a polarization identity (here, for the Euclidean norm on R). Moving to the regret analysis, let us denote i" arg [in E E (ye ==.) Splitting the sum in halves and rearranging the terms using that p. is probability distribution over [K] the loss of the learner at time can be bounded from above as
1
2
(z. - -y0)² =
Pt:
Z1
+ 21 - Yt
2
2
2
Σ Pt (i)
Zt,i + 21
Yt
K
1 + 2t
2
Pc (f)
21,1
112
2
2
where the inequality follows from Jensen's inequality. Applying Equation (12) for any i E [K] with Ze,i and b- 2g, and again using (Pe, 1) = 1, we further get
K
(2. (Z.-v.)²
Pc (i) (Zr,i - -y0) + 2 (z: - yy)²
Pt (i) (Zr,i - Zz)²
2
1=1
K
Pe (i) (Zt, - -2) + 2
(Z: - -20
(Ze.s" - yc)
2
2
1=1
(0)
Pt (i) (Zz.) z,)² + (Zi,5 y1) (Zz,5* - y2
Using the polarization identity on (0) with Z; and Z2,3 leads
K
ū - 22, 2 -
Σ Pe (i) (Zz.; - y2 + (y - Z:) (Zi, =z)) -2))- -
2 (Z: 21,5-) )
2
K
Pt. (i) (zz,s 21)² + (Zz, - ye)²
2 (Zt,5- y2)
8 1
31

---

We recall that Algorithm 3 uses the loss & (1) Rearranging the first two terms in the upper bound. we have
2 (zr,i v13² + Ze,i (Z. - ve) for any i E [K].
1
1
22 -z)²² S (pe, be) Zt,t" (z: yt)
(zc 21,t))
2
(4)
K
Pe (i) (Zt,s - 21)² + (Z),5- - y11
2 (2 - y6) 2
8 1=1
(pr, (x) - (e()t) 1 (zt - ke,60)²
(using (+) + - (e(+t)
K
Pr (i) (Zt,3 -ze)² + (Zz,5* - ye)
1=1
At this point, we can move the last term in the right-hand side to the left-hand side obtain
k
1
(z. - yz)) - (2,,i- - -2)²² s ((pr. E2) - (i²) - 2 [2t Ze,i )²
(i) (Zz,i - zz)² (13)
Pr
Now, from Theorem B.2 with = 7 and B = Vlog (KT) we have
E ( S 11 log (KT)
Σ +
Σ vo (it)
(14)
We continue by bounding ü; = - e, the square inside the sum can be bounded, for any E [K]. by
i== Pe (i) (fe (1) {pt, (2)) from above. By definition of the loss
(Ce (i) (pe, (0) = ( (Ze,5 vi)² - (pr. (ze - Ye 1)²}| + (Zz,s - (x,) (Z: - y1)
2
S [(z.. - 2,) (Ze- - (x))
+ 2 (Zz,, y1)² - (pe, per (z: - yr 1)
1)²) )/² (15)
where we used the inequality (a (a+ + 6)2 < 2a² + 262 for any a, b E IR. Plugging it into the definition of 0e this gives
K Pr (Zr - -v:)²
0. S 2 (Z. y1
Pc (i) [Ze,i zn]
Pc (i)
(Ze, 2²
Σ
We continue by bounding from above the second term on the right-hand side, The difference inside the square can be equivalently rewritten as
K
(ze,- v² 22))-
Σ 1=1
Pc (i) (Ze.s - =2
-l(ze) - 2i) - -yy-
- zz)1² -z,)1= -
Pt (j) [[ze,] - 2,) - (yr - zz:)
-z)-
1=1
=(Zr, - )²)² - 2 (y)e- 2②) (Zr.s - 2+) + (y:= =z²² Σ
Pt. (j) (Zr.i zz)²
j=1
K
+ 2+,) Σ
Pt. (f) (zr.) - -z,) - (ye - =,,²
(Pp, 1) = 1)
1=1
k
=(2r, 22)² (y) zi) (Zz,3 21)
Σ
Pt (J) (zt.5 - -zz)²
(16)
j=1
32

---

where the last equality is by definition of ž,. We plug it back in the sum above, and using again the inequality (a + b)2 s 2a² + 2b we get
K
K
(z - y1) Σ Pt (i)
(Z0,5-1))
Σ
Pt (1) (z).) - y0)
1=1
K Pc (i) (Zt,i "1)²
2
Pt (i)
2 2(v k.) (2t,3 x,)
Σ pt (2+. xz)²
Expanding the square in the second term, we get that the cross-product is equal to zero by definition of Z₁, thus
2
K
K
Σ (i)
(Ze,1 y1)²
Σ
Pe
(Zr,) v1)²
1=1
==1
2 Pt
< 2
Σ Pc (i) (Zt,t zz)² +8 (ye- ze)
Σ Pc (z), (21,1- zz)² +
Σ
(i) (Zt.) - 2,)
1=1
where we used (pe, 1) Using Jensen's inequality,
2
K
(i)
(Zt,i y1)²
Pt (i) (Zt.j 11)²
< 4
Ps (i) (Zi. 21)* + 8 (ye 2.)²
Σ
Pe (i) (Ze,5 z,)²
i=1
Plugging it back into the upper-bound on Ü. we obtain
S 6 (7, y1) Pa (1) [2e, 2,1²
+ 2 >
pe (i) (ze,i =,e²²
Using E. [v?] S a and | S Y. we find that
K
E, [+]] (20Y² 12x) Σ
Pa (i) (Zz,; 2,)²
(17)
We now bound et (i) for any given E [K]. As with Gr Equation (15) gives
2
K
(e) (i) - (p., (p:;,))) s (2. v1)² (zr.5 2x)² 2 (2., v1)² - Σ Pc (z) n1)²
Reusing Equation (16), we can write the second term on the right-hand-side as
(21,3 yz)² Σ /=1
Pt (j) (Zt.j y1)²
= -(mn. - -2,)2 2 (y:- - 2z) (Ze,s 21)
K
Σ
Pt (21.s zz)2
3=1
2
K
3 (Ze,) -z)² +
66 2
z1)²| (Zr, - Zz)²² +3 2
Σ
Pt (i) (Ze.5 =z²²²
< 3 (21, 2,)² + (yr 20)² (21,1 zz)² +3
max (zr,k 2z)3
Σ
Pt (i) (Zt.j 22)
KE[K]
1=1
33

---

where the first inequality follows from (a+ (++ c)² < 3a + 3b² + 3c² valid for any a, b, c E R and
the second inequality follows from Jensen's inequality. Thus, using By [v?] S a and | s Y, we find that
K
Ee [vr (4) < (161² + 100) (2t.; - z1)² + 68
Σ Pt (i) (Z.. - 2,)²
(18)
Consider now any y > O. By using the bounds on R2 [16 (7) and E. [Vo]. together with Equations (13) and (14), we finally find that
T Σ
(z4- - 21)² (21,5- -20)2) ))
S
E
11 v log (KT)
Σ 8s
Σ Ue (it)
k
E
k,)²²
1
Σ
Pt (i) (Ze.) 2z)²
(Equations (13) and (14))
8
E
11 2 log (KT)
Σ
Ut
Up (it)
t=1
K
1
E
[21,5"
z=)² +
Σ
Ps (j) (Ze,) z,1²²
8
j=1
121 log (KT)
K
Zt.1- - zz)² + Σ
Pt (j) (Zi.) - zz)²
2
,=1
T
T K
+ E
(8Y2 + 50)
Σ
(Ze,5" - 2,)² 2 + (13Y² + +60)
Σ 1=1 i=1
Pr. (1) (Ze, - 2,)2
121 log (KT)
k
E
(Z1,i* - 2z)² +
Pr. (j) (Zr.j - Zz:2
2
8
(=1
j=1
T
T K
1
+7 (10442++ + 48o)
E
(Z, - 2,)2+
Pe (i) (Zz.) 2,)
2
1=1
=C o)) log (KT)
for a sufficiently large constant C > 0, where the third inequality follows from Equations (17) and (18) together with the fact that vab = inlz>0 27 a + Ibb for any a, b 2 0, whereas the last inequality follows by the choice of = (104Y 48o) This completes the proof.
E Comparison with Gökcesu and Kozat [2022]
In this section, we provide further details about the comparison with Gökcesu and Kozat [2022]. The first regret guarantees we compare against are those provided by their Theorem IV.7 and Theorem V.2. One may immediately observe that those regret bounds present an additive term Er (multiplied by logarithmic factor) equivalent to our My max,, (1)], for which we already prove that the /KT lower bound holds even with i.i.d. losses.
Hence, the main comparison is mainly with respect to Corollary IV.8 and Corollary V.3 in Gökcesu and Kozat [2022]. The proof of Corollary IV.8 and Corollary V.3 rely on their Lemma IV.1, which requires that, in the notation of Gökcesu and Kozat [2022], My 44,m Hel < 1 for all t and all m
34

---

Figure 1: Results of experiments with heavy-tailed losses.
lostOMD loLtFTRL
Adalledge
mean loss over rapesttonns
EW Squint
500
-500
500
1000
1500
2000
2500
Figure Results of experiments with heavy-tailed losses. Dotted lines represent mean one standard deviation.
lontOMD
mean loss (+- suz) over 40 repettores
lootF TRL AdaHlddge
W Squint
500
-500
500
1000
1500
2000
2500
for Equation (b) in the proof of Lemma IV.1 to be true. However, with the learning rates given in Corollary IV.8 and Corollary V.3, Th 1e,4 Hel < does not hold. Corollary IV.8 they choose
Me Eu which with μa minm la.m for with 4,m 0 m K and
1i,x = 1. can be seen to lead to ne Ie. Mel V 1. With Corollary V.3, we run into a similar
issue. We do not see way to fix these issues.
F Details on the Experiments
In this section we provide details on the experiments. All experiments were run on Macbook Air with 8GB of RAM and an Apple M2 processor. We ran two sets of experiments, and the experiments each set were run for K (15, 25, ... 135). For each instance we set 20K.
In the first set of experiments the losses mimic the construction we used in Section 4. The expert losses were equal (i) 1li + 1) + Er,i, where ε, L,, with G,, Rademacher random variable and
w.p. 1/T
X1,4
KT
w.p. 1/T
35

---

Figure 3: Results of experiments with con-heavy-tailes losses.
lostOMD lootFTR Adalledge
mazan loss over rapetttons
EW Squint
500
1000
1500
2000
2500
Figure 4: Results of experiments with non-heavy-tailed losses. Dotted lines represent mean one standard deviation.
lool
mean locs (+- stdl over 40 repettiors
lootf TRL
AdaH
Squint
500
1000
1500
2000
2500
In the second of experiments similar construction, where the losses equal to (e(i) 1i + 1] st, where Er,s Xe, with St,s Rademacher random variable and
5 w.p. 1 1/7
X 2 w.p. 1/T
The algorithms we implemented were Squint with the improper prior [Koolen and Van Erven, 2015], AdaHedge [De Rooij et al., 2014], and an instance of Exponential Weights (EW) algorithm akin to the algorithm of [Cesa-Bianche et al., 2007]. Specifically, we ran the FTRL version of exponential weights on the instantaneous regrets with learning rate тソ- min!
E.se Pt J. We gave this instance of EW the maximum loss, otherwise it would not provide any guarantees. We could have also opted for doubling trick, but this known to deteriorate performance. Likewise, we gave Squint the value of max,, (i)), as this is required parameter for Squint. The algorithm of [Mhammedi et al., 2019) could have instead been used to learn max,,; [i) online, but seeing that similar idea as the doubling trick is part of their algorithm, suspect this would only deteriorate performance.
log(K)
maxe, [P( [P
In the first set of experiments expect Squint, AdaHedge, and EW to perform poorly due to the issues described in Section 4, the second set of experiments we expect similar behaviour from all algorithms.
36

---

As can be seen from the results in Figure I, algorithms not tailored to adapt to @ fare considerably worse in the heavy-tailed loss setting we consider. We therefore conclude that the lower-order terms in the regret bounds of these algorithms are not artefact of the analysis, but rather represent the problematic behaviour of these algorithms in the face of heavy-tailed losses.
The results for the second set of experiments is similarly as expected with one exception: the performance of Squint. Squint fares considerably worse than the other algorithms. However, upon inspection, it seems that the performance of Squint is still below what is predicted by theory. The regret bound of Squint contains 15 log(1 (22 + log(T + 1])) term, which for the smallest values of K, T is slightly larger than 71.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See theorems in Section 2 and lower bounds in Section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
38

---

Justification:
Results and assumptions are clearly stated in the main text. Proofs are provided
in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We clearly describe the experiments and how we chose the parameters of the relevant algorithms in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
39

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The data is simulated. The code simulate the data is included in the supple- mentary material. The implementations of the algorithms is included in the supplementary material as well.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/ cublic/guides/Cne aublic//uudeesDddeeettniisssssss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cttppblic/guiceeeeeceeococc wwtcc//guuis//ee wttpggdddeeeeeeeemiiiiiieeeeeeee srndeeuumisssooPoolo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We clearly describe the experiments in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The guarantees in the paper are on the average performance, hence we only report the average behaviour.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
40

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
is described Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics ittpppp/l/ l
Answer:
[Yes]
Justification: This work being primarily theoretical, it does raise any ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is mainly theoretical and does not have any direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
41

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is mainly a theoretical paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use any existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twwode.cooo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
42

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
The experimental details are provided in the appendix.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
43

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: wtt.urips.ec/oooeeeeeeeeeeeeeeee /LLM) for what should or should not be described.
44


Reviews:
[{"review_id": "0zySOanu3G", "reviewer": "Reviewer_QACD", "summary": "This paper provides algorithms for prediction with expert advice with heavy tailed losses (for the conditional distribution of each instance given the history). It correctly points out a critical flaw in applying standard scale-adaptive methods to the case of conditionally heavy tails (that the random variations form sampling will dominate the regret giving $\\sqrt{NT}$ bounds instead of $\\sqrt{\\theta T\\log N}$ when the scale^2 is $\\theta$). The paper provides new algorithms which depend on second moments rather than expected maxima, and hence are better order. The algorithms are variants of hedge/exponential weights, instantiated as OMD or FTRL respectively, with different learning rates per expert (given by a diagonal weight matrix). The weights are updated in a way similar to other adaptive methods, but using clipped losses to \"truncate\" the heavy tails.", "questions": "-", "limitations": "-", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper is well written, clearly identifies and resolves a relevant problem, and provides practical guidance.", "was_revised": true, "final_justification": "i am still in favour of accepting. i maintain my score", "rebuttal": "Thank you for taking the time to review our paper and for the positive feedback. We are glad you found our paper well-written and recognized the relevance of our contributions. We are available to answer any questions that may arise during the discussion period."}, {"review_id": "RoPAvdnSAh", "reviewer": "Reviewer_fiH4", "summary": "This paper studied online learning with expert advice with $K$ experts and $T$ days. The simplest form of the problem is for the loss function to be bounded by $[0,1]$ so that we could obtain $O(\\sqrt{KT})$ worst-case optimal regret. This paper considered the more general setting of general loss functions with “adaptive” losses, i.e., regret bounds in the form of the instance-dependent parameters. On this front, if we know $\\max_{t,i}\\ell^{t}(i)\\leq M$, it is possible to obtain $O(M\\sqrt{T \\log K})$ regret. This paper instead asked about what will happen if we instead know the second-order moment, i.e., $\\mathbb{E}[(\\ell^{t}(i))^2]\\leq \\theta$. Here, the algorithm does not necessarily know the value of $\\theta$ in advance.\n\nThe paper started by showing an example when $\\theta=O(1)$ but algorithm that adaptive to $\\max_{t,i}\\ell^{t}(i)$ could only result in $\\Omega(\\sqrt{KT})$ regret. Then, the paper designed an algorithm that achieves $O(\\sqrt{\\theta T \\log{K}})$ regret when $\\mathbb{E}[(\\ell^{t}(i))^2]$ is bounded by $\\theta$. Additionally. For instances that satisfy a “self-bounded environment” assumption, the paper designed an “instance-sensitive” type of algorithm that achieves $O(\\theta \\log(KT)/\\Delta_{\\text{min}})$ regret. Finally, for the square loss with the expert losses bounded by $Y$ and second moment bounded by $\\sigma$, the paper achieved $O(\\log{K}\\cdot (Y^2 + \\sigma))$ regret.\n\nThe main technique of the paper focuses on removing the $M_T = \\mathbb{E}[max_{t,i}|r_t|]= \\mathbb{E}[max_{t,i}|p_t^{T} \\ell^{t} - \\ell^{t}(i)|]$. The paper has shown that almost all existing algorithms would lead to this additive term when only the guarantees on the second-order moments are provided. To avoid this term, the main idea of the algorithm appears to be the adoption of the multi-scale entropic regularizer (BDHN [JMLR’19]) and the clipping of the loss when the variance of the algorithm is high. The paper then showed that the additional cost induced by cost clipping is tolerable (Equation (3)). Due to time constraints and my experience with the literature, I did not check the proof.", "questions": "I do not have additional questions. Do the authors have responses to the weaknesses I flagged?", "limitations": "N/A, this is a theoretical work about online learning, and I do not see any immediate societal impacts.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "In my opinion, the paper is generally well-written, and the main conceptual message is clearly articulated: in the bandit setting, one cannot adapt to the parameter $\\theta$, while in the full-information expert setting, we could achieve $O(\\sqrt{\\theta T \\log{K}})$ regret without knowing $\\theta$ a priori. The bounds in related work were also thoroughly discussed. \n\nThe technical part of the paper was written reasonably well. I’m not very familiar with the adaptive algorithm in the expert/bandit settings, but I could nevertheless follow the argument used in section 4. The techniques become harder to follow in section 5, partly due to the fact that I’m not very familiar with the existing techniques in the literature (for adaptive regrets). \nThe proof sketch gave a nice high-level framework, but the parameters are still quite involved. \n\nOn the flip side, I think the paper could have done a better job of motivating the setting from a *practical* perspective. From the paper, it is not very clear in what application scenarios we would have bounded second-order moments. I’m OK with this for a mostly theoretical paper, but for this conference, having better practical motivations will definitely be more helpful.\n\nThe above point is also related to the significance of the results. I personally believe the separation between the expert vs. bandit case is of good conceptual significance. However, since I’m not very familiar with the literature, I’ll see what my colleagues have to say about the significance.\n\nThe paper does not contain experiments. Again, I'm personally OK with this since this is a theoretical work. However, I do want to flag this for the AC in case that is part of their decision.\n\nOverall, I will be happy to see the paper get accepted, but I cannot give a firm verdict about the significance and the practical aspect. I also did not get a time to carefully check the proof, so I can only give a weak supportive opinion.\n\n====== Post Rebuttal ======\nThe author pointed out that their paper does contain experiments, which I missed during the initial review. I looked into that section and found that although the settings are limited, experimental results have demonstrated the better performance of their algorithms in the heavy-tail settings. \n\nI've increased my confidence score to reflect this discussion. However, since I'm not very familiar with the existing techniques, I still cannot give a higher score to \"champion\" for the paper.", "was_revised": true, "final_justification": "====== Post Rebuttal ======\nThe author pointed out that their paper does contain experiments, which I missed during the initial review. I looked into that section and found that although the settings are limited, experimental results have demonstrated the better performance of their algorithms in the heavy-tail settings. \n\nI've increased my confidence score to reflect this discussion. However, since I'm not very familiar with the existing techniques, I still cannot give a higher score to \"champion\" for the paper.", "rebuttal": "Thank you for taking the time to review our paper and for your positive feedback. We are pleased you found the paper well-written and conceptually relevant. We address the flagged weaknesses below.\n\n**Regarding the experimental evaluation**. We would like to clarify that we did include experiments in Appendix F (pages 32-34). These experiments empirically validate our theoretical claims by comparing our proposed algorithms (LoOT-Free OMD and FTRL) against several established baselines on synthetic heavy-tailed data. The results, shown in Figures 1 and 2, illustrate the failure modes of existing methods that our work addresses, confirming the practical implications of our analysis.\n\n**Regarding practical motivation**. Thank you for this suggestion. While our work is primarily theoretical, the assumption of heavy-tailed losses is motivated by several real-world scenarios where data is prone to infrequent, large-magnitude events. For instance:\n\n- _Financial markets_: Asset returns are widely recognized as being heavy-tailed (see, e.g., [1]). Our framework can be applied to problems like online portfolio selection, where an investor aggregates the advice of different financial experts or trading strategies, and the daily losses (or negative returns) can exhibit large fluctuations.\n\n- _Energy forecasting_: Forecasting electricity prices or demand is another key application. For instance, Li and Jones [2] observe that time series often feature sudden, large spikes due to unpredictable events (e.g., power plant outages, extreme weather). Aggregating different forecasting models as experts is a common approach in this domain [3].\n\n- _Online media and e-commerce_: The popularity of items like news articles, videos, or products often follows a power-law distribution. In applications like ad placement or content recommendation, where the goal is to predict engagement, the observed outcomes (e.g., clicks, views, sales) can be heavy-tailed (see, e.g., [4]).\n\nWe will incorporate these examples in the final version of the paper to better motivate our contributions. We hope these clarifications address your concerns and are grateful for your supportive assessment.\n\n**References**\n\n[1] Bradley, B. O., and Taqqu, M. S. (2003). Financial risk and heavy tails. In Handbook of heavy tailed distributions in finance (pp. 35-103). North-Holland.\n\n[2] Li, Y., and Jones, B. (2019). The use of extreme value theory for forecasting long-term substation maximum electricity demand. IEEE Transactions on Power Systems, 35(1), 128-139.\n\n[3] Devaine, M., Gaillard, P., Goude, Y., and Stoltz, G. (2013). Forecasting electricity consumption by aggregating specialized experts: A review of the sequential aggregation of specialized experts, with an application to Slovakian and French country-wide one-day-ahead (half-) hourly predictions. Machine Learning, 90(2), 231-260.\n\n[4] Cha, M., Kwak, H., Rodriguez, P., Ahn, Y. Y., and Moon, S. (2007, October). I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system. In Proceedings of the 7th ACM SIGCOMM Conference on Internet measurement (pp. 1-14)."}, {"review_id": "ZPStM95SYf", "reviewer": "Reviewer_ke8c", "summary": "This paper studies the experts problem when the losses are \"heavy tailed\", i.e., when the second moment of the losses are bounded above by an (unknown) constant $ \\theta $. The authors show that existing algorithms have lower-order terms that can make the regret as large $ \\sqrt{K T} $. The authors develop algorithms whose regret is at most $ O (\\sqrt{ \\theta T \\log (K)}) $. They also show improved results under more restricted settings. Their algorithms are online mirror descent and follow-the-regularized-leader, using clipped versions of instantaneous regret as the loss and using empirical variance-based entropy regularization.", "questions": "1. When you discuss Algorithm 2, Line 283 says that \"Note that, differently from Algorithm 1, we replace the multi-scale entropic regularizer $\\psi_t $ with its Bregman divergence.\" This is not clear from the main text because Algorithm 2 is only presented in the appendix. Could you elaborate on this point? I looked at the algorithm in the appendix and did not quite understand what you mean.\n\n2. Is it fair to say that choosing $ \\eta_{t,i} $ as a function of the empirical variance and second moment of the instantaneous regret is the key to obtaining your result and constitutes the core novelty of your contribution? I can see that the definition of $ \\eta_{t,i} $ helps algebraically in the equation after Line 266. However, can you provide some more intuition behind the definition of $ \\eta_{t,i} $?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* The authors study an important problem, namely, achieving sublinear regret in the experts problem under heavy-tailed losses, which can occur in many real-world scenarios.\n* The core novelty of their contributions is an adaptation of the multi-scale entropy regularization of Bubeck et al. (2019): the authors use time-varying (and expert-varying as in Bubeck et al.) scales ( $ \\eta_{t,i} $ ), set the scale to a function of the observed variance and second moment of the instantaneous regret, and perform clipping per expert.\n* Section 4 provides concrete examples showing lower-order terms can be large and the authors do so by using a simple construction.\n\nWeaknesses:\n* My main concern about the paper is its clarity. While the paper is well written overall, the writing is a bit sloppy in some places.\n    * Lines 47-56 and the sentences following Theorems 2.2 and 2.4 seem to have the algorithms switched. For instance, line 47 says that Algorithm 1 achieves $ O (\\sqrt{ \\theta T \\log (K)}) $ worst-case regret. However, Line 78 (following Theorem 2.2) says this bound is achieved by Algorithm 2.\n    * The abstract says that logarithmic regret is achieved under a separation assumption and i.i.d. losses. However, the main text and the appendix do not make the assumption of i.i.d. losses to achieve logarithmic regret.\n    * The authors refer to three algorithms in the main text for their regret bound results. However, they only present one of them in the main text. It is hard to follow their discussion that references the algorithm design when they don't present those algorithms in the main text.\n    * Related to the previous point, in Section 5.2 when the authors discuss Algorithm 2, Line 283 says that \"Note that, differently from Algorithm 1, we replace the multi-scale entropic regularizer $\\psi_t $ with its Bregman divergence.\" This is not clear from the main text because Algorithm 2 is only presented in the appendix. Question to the authors: Could you elaborate on this point? I looked at the algorithm in the appendix and did not quite understand what you mean.\n* Another weakness is novelty. The core novelty of the contribution, described above, is also a bit of a weakness: the authors combine existing ideas of clipping and multi-scale entropy regularization. (The authors do make the scale data dependent by using empirical second moments.)", "was_revised": true, "final_justification": "I am satisfied with the authors' response and I have raised my score. I would like the authors to address the issues around clarity and algorithm presentation in the final version. I would also encourage them to include part of their answer to Q2 in their paper - it might be helpful for readers!", "rebuttal": "We sincerely thank you for your detailed and constructive feedback. We are glad you found the problem important and our analysis insightful. We address the points you raised below.\n\n**(W.1.1, W.1.3) Regarding the typos and algorithm presentation**. Thank you for pointing out unclear points and typos. We will fix these in the next version and take advantage of the additional content page to include the algorithms in the main body to improve readability.\n\n**(W.1.2) Regarding the i.i.d. assumption in the abstract**. Our use of \"i.i.d. losses\" in the abstract was intended as a simple, concrete example of a scenario satisfying our more general assumption Assumption 2.3 (self-bounded environment). If losses are i.i.d. and there is a unique best expert $i^\\star$, the gap to any other expert $i$, $\\Delta_i$, is positive and lower-bounded by $\\Delta_{\\min}$. This implies Assumption 2.3 with a constant $C = 0$, since the regret satisfies\n$$R_T = \\mathbb{E} \\left[ \\sum_{t=1}^T \\sum_{i \\neq i^\\star} p_t(i) \\Delta_i \\right] \\geq \\mathbb{E} \\left[ \\sum_{t=1}^T \\sum_{i \\neq i^\\star} p_t(i) \\Delta_{\\min} \\right] = \\mathbb{E} \\left[ \\sum_{t=1}^T (1 - p_t(i^\\star)) \\Delta_{\\min} \\right].$$\nWe will clarify that Assumption 2.3 is more general and covers non-i.i.d. settings (see, e.g., [1, 2]). See also our answer to Reviewer XFbG for a related discussion.\n\n**(W.1.4, Q.1) Regarding the regularizer in Algorithm 2**. The reason for using the Bregman divergence $\\varphi_t(\\cdot) = D_t(\\cdot \\| p_1)$ rather than the multi-scale entropy $\\psi_t$ for Algorithm 2 is essentially because we wanted a simplification in the analysis. The Bregman divergence is non-negative, which allows us to simplify some steps in the analysis that involve the decreasing learning rates $\\eta_{t,i}$. As we comment at lines 282-290, using the Bregman divergence also guarantees monotonicity over $t$, which makes the FTRL analysis simpler by allowing us to remove the typical sum $\\sum_t(\\varphi_{t}(p_{t+1})-\\varphi_{t+1}(p_{t+1})) \\le 0$ from the stability term. On the other hand, monotonicity is not guaranteed for the multi-scale entropic regularizer $\\psi_t$, and thus one would need to carefully analyze the corresponding sum $\\sum_t(\\psi_{t}(p_{t+1})-\\psi_{t+1}(p_{t+1}))$ from the stability term of FTRL. We think that the analysis, although slightly more involved, could also lead to a meaningful result in our setting. However, due to the fact that the learning rates we employ depend on $i$ too, this could require the algorithm to tune the learning rates $\\eta_{t,i}$ in a slightly different way than currently done by Algorithm 2.\n\n**(W.2, Q.2) Regarding the novelty**. While the ideas we use appear in some form or another in the literature, it is important to note that, as they appear in previous work, they still lead to the lower-order term that can force the regret bound to scale as $\\sqrt{K T}$. For example, applying the clipping as proposed by Cutkosky [3] or Orseau and Hutter [4] also leads to the lower-order terms (see lines 126-135). Only when we overhaul these ideas and carefully combine them are we able to avoid the problematic lower-order term.\n\n**(Q2) On the choice of the learning rates $\\eta_{t, i}$**. Central to our results is not just the choice of the learning rates $\\eta_{t, i}$ but also the clipping we use. At a high level, the choice of learning rate $\\eta_{t, i}$ is driven by the need for stability in the analysis. For entropy-regularized OMD/FTRL, the term in the exponent must remain small, e.g. $|\\eta_{t, i} \\ell_t(i)| \\leq 1$, to ensure the quadratic $1 - x + x^2$ is a good approximation of the exponential $\\exp(-x)$, where we take $x = \\eta_{t, i} \\ell_t(i)$ (see, e.g., Section 11.4 of [5] for an argument specific to the Exponential Weights algorithm with rewards, which can be similarly extended to losses and entropy-regularized OMD/FTRL). A standard way to achieve this is to choose a global learning rate $\\eta_t \\propto 1 / \\max_{s \\leq t, j} |\\ell_s(j)|$. However, this is too conservative: a single large loss from one expert makes the learning rate small for *all* experts, causing the problematic $\\sqrt{K T}$ regret. This justifies setting the learning rate for each expert individually, based on their own observed history. We refer to Appendix A.3 for further details on the caveat of choosing a global learning rate.\n\nThe clipping mechanism is then linked to this choice of individual learning rates. For expert $i$ at time $t$, it is set to $1 / \\eta_{t, i}$ and acts as follows. If an expert has been stable (i.e., low cumulative variance), its learning rate $\\eta_{t, i}$ is large, making the clipping threshold $1 / \\eta_{t, i}$ small. The algorithm becomes sensitive and clips even moderate losses, as they would appear as outliers for that expert. Conversely, if an expert has a high cumulative variance, its learning rate $\\eta_{t, i}$ is small, making the threshold $1 / \\eta_{t, i}$ large and the algorithm will tolerate larger losses since they are expected.\n\nWe will revise the paper to incorporate these clarifications. Thank you again for your thoughtful review.\n\n**References**\n\n[1] Zimmert, J., and Seldin, Y. (2021). Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28), 1-49.\n\n[2] Amir, I., Attias, I., Koren, T., Mansour, Y., and Livni, R. (2020). Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 14315-14325.\n\n[3] Cutkosky, A. (2019). Artificial constraints and hints for unbounded online learning. In Conference on Learning Theory (pp. 874-894). PMLR.\n\n[4] Orseau, L., and Hutter, M. (2021). Isotuning with applications to scale-free online learning. arXiv preprint arXiv:2112.14586.\n\n[5] Lattimore, T., and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press."}, {"review_id": "YffXfqhg8d", "reviewer": "Reviewer_XFbG", "summary": "This paper addresses the problem of prediction with expert advice under the assumption that losses are heavy-tailed but have bounded second moments. The authors develop adaptive algorithms that improve the dependence on the number of experts from the usual $\\sqrt{K}$ to $\\sqrt{\\log K}$ in the regret bound, under appropriate assumptions. They consider both the standard linear (Hedge) setting and a quadratic loss variant, providing adaptive algorithms based on Online Mirror Descent (OMD) and Follow-The-Regularized-Leader (FTRL).", "questions": "1. Do the authors have insight into potential lower bounds for these settings? For example, do known adversarial lower bounds apply here, given that bounded adversarial losses would satisfy Assumption 2.1? If so, can the optimality of established rates be discussed?\n\n2. Are the values on $Y$-axis of the plots regret?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The expert setting with heavy-tailed losses is relevant in practical scenarios involving outliers, noise, or mechanisms like local differential privacy. The paper makes an insightful observation that terms traditionally treated as lower-order can, in fact, dominate the regret when only second-moment bounds are available.\n\nFrom a technical standpoint, the paper is solid. The proposed algorithms are interesting variants of OMD and FTRL, and the analysis appears to be non-trivial. The authors also support their claims with synthetic experiments.\n\nMy main concern lies in the lack of discussion around the motivation and interpretability of the assumptions. For instance, Assumption 2.3 is introduced without much explanation. It would be helpful to include an intuitive explanation of $\\Delta_{\\min}$ and $C$, and how these constants behave under different distributions. Can $C$ grow with $T$, or is it typically constant for distributions with bounded second moments? A discussion akin to Section 4, which provided insight into why certain terms dominate, could help clarify the meaning and implications of these parameters.\n\nSimilarly, Section 2.2 introduces a quadratic loss model, but it is not clear why this setting is interesting or whether it arises naturally in known applications. Is it connected to scalar regression, or is there prior literature studying this variant? A brief contextualization would help establish its relevance.\n\nOverall, the paper is technically strong and contributes important insights to the literature on adaptive online learning under heavy-tailed losses. However, additional exposition around the assumptions and modeling choices would strengthen the presentation.", "was_revised": true, "final_justification": "I have initial concerns about the motivation for the problem. However, the authors have addressed my concerns and I am happy with the current score.", "rebuttal": "Thank you for taking the time to review our paper, for the positive feedback, and for recognizing our technical work. We address your points below.\n\n**Regarding the interpretability of Assumption 2.3**. This assumption is intended to model environments that are not fully adversarial but have some underlying stochastic structure. Intuitively, $\\Delta_{\\min}$ represents the minimum performance gap between the best expert and any other expert, and the constant $C$ acts as a \"corruption\" budget, allowing for some adversarial deviations from this stochastic structure. In a purely i.i.d. setting, we would have $C = 0$. The question of whether $C$ can grow with $T$ or $K$ is a good one: In the literature (e.g., [5, 6]), $C$ is typically assumed to be a constant. However, like the algorithm of Zimmert and Seldin [5], our algorithm can also tolerate corruptions that are at most logarithmic and still have meaningful guarantees. To the best of our knowledge, it is an open problem whether it is possible to tolerate a linear amount of corruption (see, e.g., Section 5.2 of [5]). See also our answer to Reviewer ke8c for additional details on Assumption 2.3.\n\n**Regarding the motivation for the heavy-tailed setting**. We refer to our answer to Reviewer fiH4 for a few motivating examples.\n\n**Regarding the squared loss**. Indeed, our main motivation lies in scalar regression. This framework enables us to generalize the classical results of Vovk [1] to the more challenging setting where the outcomes $y_t$ can be heavy-tailed. This is an important setting with many applications, such as regression under heavy-tailed distributions, a topic surveyed by Lugosi and Mendelson [2, Section 5]. When we have different models to use but do not know which one is the best, our algorithm can learn (online) to perform nearly as well as this single best model, all without restrictive assumptions on problem parameters like knowledge of $\\theta$.\n\n**(Q1) Regarding the lower bounds**. Yes, this is a great question. The standard adversarial lower bounds for the experts problem apply directly to our setting because, as you pointed out, the setting with bounded losses is a special case of our Assumption 2.1. Therefore, the $\\Omega(\\sqrt{T \\log K})$ lower bound (see, e.g., Theorem 3.6 from Cesa-Bianchi and Lugosi [3], or Theorem 3.22 from  Haussler et al. [4]) holds. This implies that our regret bound of $\\mathcal{O}(\\sqrt{\\theta T \\log K})$ for the FTRL algorithm is optimal in both $T$ and $K$, and note we have $\\theta \\leq M^2$ (under Assumption 2.1).\n\n**(Q2) Regarding the plots**. The $Y$-axis in the plots represents the mean ($\\pm$std) cumulative loss over 40 repetitions of the experiments. In this case, by definition of the losses (see Appendix F), they are equivalent to the regrets.\n\nWe will add more clarifications in the next revision. Thank you again for your thoughtful feedback.\n\n**References**\n\n[1] Vovk, V. (2001). Competitive on‐line statistics. International Statistical Review, 69(2), 213-248.\n\n[2] Lugosi, G., and Mendelson, S. (2019). Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19, 1145-1190.\n\n[3] Cesa-Bianchi, N., and Lugosi, G. (2006). Prediction, learning, and games. Cambridge University Press.\n\n[4] Haussler, D., Kivinen, J., and Warmuth, M. K. (1998). Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 44(5), 1906-1925.\n\n[5] Zimmert, J., and Seldin, Y. (2021). Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28), 1-49.\n\n[6] Amir, I., Attias, I., Koren, T., Mansour, Y., and Livni, R. (2020). Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 14315-14325."}]

Author rebuttal:

Meta-review: This paper studies algorithms for prediction with expert advice with heavy-tailed losses, noting that standard methods fail for conditionally heavy tails due to lower-order terms dominating the overall loss due to large variances from sampling. The paper instead achieves the optimal regret bounds by incorporating multi-scale entropic regularizers and clipping the loss when the variance of the algorithm is high. All reviewers agree that the paper clearly articulates the motivation for studying heavy-tailed losses and that the corresponding algorithmic guarantees given in this paper are valuable. 

Nevertheless, reviewer feedback pointed out several points that could further strengthen the potential impact of the paper; I encourage the authors to take these points into consideration.
Decision: Accept (poster)