Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers
Authors: Jeffrey Negrea
Blair Bilodeau
Nicolò Campolongo
Francesco Orabona
Daniel M. Roy
Venue: NeurIPS 2021 Poster (2021)
Keywords: online learning
prediction with expert advice
quantile regret
semi-adversarial
adaptive online learning
FTRL
regularized learning
f-divergence
aggregation
generalized Bayes
online variational inference

Abstract: Quantile (and, more generally, KL) regret bounds, such as those achieved by NormalHedge (Chaudhuri, Freund, and Hsu 2009) and its variants, relax the goal of competing against the best individual expert to only competing against a majority of experts on adversarial data. More recently, the semi-adversarial paradigm (Bilodeau, Negrea, and Roy 2020) provides an alternative relaxation of adversarial online learning by considering data that may be neither fully adversarial nor stochastic (I.I.D.).  We achieve the minimax optimal regret in both paradigms using FTRL with separate, novel, root-logarithmic regularizers, both of which can be interpreted as yielding variants of NormalHedge. We extend existing KL regret upper bounds, which hold uniformly over target distributions, to possibly uncountable expert classes with arbitrary priors; provide the first full-information lower bounds for quantile regret on finite expert classes (which are tight); and provide an adaptively minimax optimal algorithm for the semi-adversarial paradigm that adapts to the true, unknown constraint faster, leading to uniformly improved regret bounds over existing methods.

Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers
Jeffrey Negrea"
Blair Bilodeau"
University of Toronto
University of Toronto
jeffrey negrea@mail utoronto.ca
blair. biwodeaummaall.........aa utoronto.com
Nicolò Campolongo
Francesco Orabona
Spanflug Technologies GmbH nico. campolongoo@spanflug de
Boston University
francesco@orabona.com
Daniel M. Roy
University of Toronto daniel. row..i...oooooooooooooo
Abstract
Quantile (and, more generally, KL) regret bounds, such as those achieved by NormalHedge (Chaudhuri, Freund, and Hsu 2009) and its variants, relax the goal of competing against the best individual expert to only competing against a majority of experts on adversarial data. More recently, the semi-adversarial paradigm (Bilodeau, Negrea, and Roy 2020) provides an alternative relaxation of adversarial online learning by considering data that may neither fully adversarial nor stochastic (i.i.d.). We achieve the minimax optimal regret in both paradigms using FTRL with separate, novel, root-logarithmic regularizers, both which can be interpreted as yielding variants of Normalledge. We extend existing KL regret upper bounds, which hold uniformly over target distributions, to possibly uncountable expert classes with arbitrary priors; provide the first full-information lower bounds for quantile regret on finite expert classes (which are tight); and provide adaptively minimax optimal algorithm for the semi-adversariie paradigm that adapts to the true, unknown constraint faster, leading to uniformly improved regret bounds over existing methods.
Introduction
We focus the setting of learning with expert advice [V90; LW94], where in each round the learner selects a probability distribution over experts, observes the loss of each expert, and incurs the average loss of the experts under the learner's 's selected distribution. The learner's 's objective is to minimize regret against some mixture of the experts, which is the difference between their cumulative loss and the cumulative loss of the expert mixture over T rounds.
The classical "worst-case" online learning paradigm assumes that the losses are adversarial that is, they are chosen to make the learner perform as poorly possible-ane demands that the learner competes against the best-performing expert. However, there are many real-world settings where this assumption is too pessimistic, and consequently we focus on designing algorithms with provable guarantees that adapt to easier notions of both data and performance measures. non-exhaustive list
'Equal contribution authors.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of work on "easy data" includes Freund and Schapire [FS97]. Cesa-Bianchi, Mansour, and Stoltz [CMS07], van Erven, Grünwald, Koolen, and de Rooij [v+11], and Gaillard, Stoltz, and van Erven [GSv14], all of which use variants of the Hedge algorithm [F$97] to obtain regret bounds in terms of data-dependent quantities. Ideally, such quantities are small when the data are "easy" to predict.
In this work, we focus on two paradigms beyond the classical worst-case: first, we consider relaxing the performance measure to quantile (KL) regret, which measures the ability of an algorithm to compete against an unknown mixture of the experts that potentially performs worse than a point-mass on the single best expert, and second, we consider regret within the adversarvaa paradigm. which defnes spectrum of constraints on the permissible data distributions between stochastic and adversarial. The concept of e-quantile regret was introduced by Chaudhuri, Freund, and Hsu [CFH09], in which the player competes against the [eN] best experts (out of N total) rather than the single best. The authors demonstrated empirically that Hedge does poorly in this paradigm, and introduced a new algorithm NormalHedge with an upper bound on quantile regret of VT + (log (1) + log(1/c) (1/c)..
Later algorithms improved it to /T(1 + +oog(log/1// [og(1 [CV10; OP16), removing the dependency on N. The semi-adversarial paradigm considers constraining the adversary's 's choice of data distributions. which was first motivated by Rakhlin, Sridharan, and Tewari [RSTI1]. Bilodeau, Negrea, and Roy [BNR20] extended this idea, defining adaptive minimax regret with respect to such constraints and providing an efficient algorithm with corresponding regret bounds.
Contributions While the best known algorithms for the above two paradigms are intrinsically different, we show that the follow- hhwlowtth--rguulrizeddlleeeee leaderr (FTRL) algorithm with new rogarlogari regularizers achieves minimax optimal performance for both quantile and semi-adversarial regret. First, we provide the first FTRL. algorithm with minimax optimal quantile regret guarantees, and do without using the additive normalization step of previous algorithms [CI066, Section 2. We achieve ko bounds that hold uniformly over target distributions on (possibly uncountable) expert classes with arbitrary priors, and reduce to the optimal quantile regret for discrete uniform priors. Moreover, we prove matching lower bounds for quantile regret with finite expert classes, demonstrating the optimality of known upper bounds (including our own) for the first time, Finally, in the semi-adversee bound, obtaining uniformly improved upper bounds over previous work.
paradigm, we improve the dependence on the number of experts in the regret
We achieve the above results through a novel local-norm analysis of FTRL with linearly decomposable regularizers on general (possibly uncountable) expert spaces. We this analysis in conjunction with basic conditions on the first and second derivatives to design and analyze the logt-logari regularizers. We believe that this approach fundamentally different from existing ones and could lead to further advances in obtaining optimal algorithms. In fact, there exist results stating if regret bound is achievable by some algorithm, then that same bound is nearly achievable by mirror descent with some potential function (see, e.g., Srebro, Sridharan, and Tewari [SST11, 1, Thm 9J). However, it not clear how to design such a function in practice. In contrast, our general FTRL bound reduces the choice of regularizer to single univariate function, and clarifies how fundamental properties of this function lead to trade-offs in the regret bound.
Related Work Chernov and Vovk [CV10) 10] first discussed the fact that the e-quantile regret corre- sponds to the KI. divergence between uniform prior and the uniform mixture of the top [eN] competitors, and such KL bounds have consequently quickly followed quantile regret bounds. Luo and Schapire [LS14; LS15] provided a variant of NormalHedge along with data-dependent KL regret bound at the cost of an additional log factor; a similar but even tighter result was obtained by Koolen and van Erven [Kv15]. Orabona and Pál [OP16] showed that these algorithms can be obtained with reduction to optimal coin- coin- betting online algorithms, yet none of them can be reduced to an FTRL algorithm. Independently, Harvey, Liaw, Perkins, and Randhawa [H+20] proved that a similar strategy allows one to achieve the optimal anytime regret for the setting with N 2 experts.
The first alternative additively normalized algorithms in the (bandit) learning with experts setting was the INF algorithm [AB09], which was later recast as online mirror descent [ABL11]] Alquier [A21] also did not use additive normalization, and first introduced FTRL with f-divergences (focusing on the x² =dvdeeergeccc) along with regret bounds for continuous distributions with certain unbounded loss functions. For the specific case of Hedge (and its online mirror descent analogue), an analysis on continuous spaces was given by Krichene, Balandat, Tomlin, and Bayen [K+15] and then more generally by van der Hoeven, van Erven, and Kotlowski [vvK18], while a coarser analysis for f- divergences was given by Alquier [A21]. Finally, choosing regularizers that are tuned to minimize

---

regret for specific tasks has recently led to advances in the online learning literature, both with bandit feedback [A+17; WL18; F+16] and in the hull-information setting [LW218].
The best known asymptotic lower bound for learning with expert advice is by Cesa-Bianche Bina-B,nnch, Freund, Haussler, Helmbold, Schapire, and Warmuth [C+97], while finite-time lower bound that asymptoti- cally matches the leading constant was proved by Orabona and Pál [OP15a], We are not aware of lower bounds for the quantile regret, with the notable exception of Koolen [K13], who proved lower bound on the regret of learning with two experts based on the KL divergence against some prior.
2 Notation
To analyze FTRL beyond the finite setting requires some more care, and we rely on the language
of measure theory to handle finite and uncountable expert classes simultancously. Let (6, ))
be measurable space, (0, Σ) and M(O, Σ) denote the collection of finite and probability measures respectively, and v E R (+, Σ) be arbitrary. A measure 9 E (M, Σ) is absolutely continuous with respect v (denoted q < v) if (A)
for all A Σ such that v(4) 0. Let (M, Σ) = {q E M(@, Σ) 1g & v) be the set of probability measures that are absolutely continuous with respect to v. For any integer N, let [N] = (1...., N). and simp ([N)
{o E
[0, 1.,1j=; Σi= = 13. Let R, = =00 [0, o)) and 1 (0, xc). and define M = M(((), Σ), (IR R))
to be the space of measurable functions from (0, Σ) to (IR, R), where R is the Borel a- on IR
Define sets of bounded measurable functions
- = {E E M: suple(0)]<< oo} and C60111 = (e E M: OsesI,,
AE
sets of integrable functions
C¹ (²)) = for E M: f (z) v(d0) < oo} and C) = (- e (v) : a 220),
and the set of Radon Nikoodym derivatives (w.rt. v) of probability measures
X(v) fo (v): =0)))(d))) 1}.
For every x E X(v), let v()) E (M, Σ) denote the unique probability measure satisfying dul=)/du = x. For every 8, E L let Conv (2, 2) = {ax + (1 - a)= : a E [0, 1]] denote their convex hull. For every & E L and x E (v), define
(e, x)2, / ((0))(0)(((0).
Prediction with expert advice We consider the following setting of online linear optimization. For each round E [T], the player selects E MMO, Σ) based only upon information available prior to round f, and then observes l _ Performance measured using the regrer against some probability measure q M(O, E). which is defined by
T RT(g)) = Σ Bo-ai [L((0)) - Σ Es-a [e(( t=1
1=1
The player's 's goal is to select f4 that the cumulative loss is not much larger than that of the average loss of an expert under g, and consequently to have small regret.
The elements of θ can be regarded experts for some prediction problem, and the learner aggregates the predictions of the experts by selecting an expert at random according to μr at round I. For concreteness, note that the usual prediction with expert advice setting for N experts corresponds to M(O, >) = sim]([ Note that, for any convex loss, applying online linear optimization to the gradients of the losses provides an upper bound on the performance of online convex optimization.
Let R = R {+2)). Follow-theregllarzzeedeeeeer (FTRL) [S07; AHRO8; HK 10] forms a broad class of algorithms for online convex optimization. For finite measure E R (,, Σ) and sequence of regularizers (th, X(v) + H kejr, (1h (We))err-reguuaan FTRL
wwwp--theerguulaizzee-eeeeee
is defined by selecting Pt+1 (((411) using
Tt+1 E arg fogminf(Ler (Li, x)₂ + (x+1 =EX((v)
(1)
3

---

where Lo = 0 and L, = E
As mentioned above, classical algorithm for prediction with expert advice finite class of N experts is Hedge. While originally analyzed using potential functions, Hedge also corresponds to FTRL where v is the counting measure and vx((.) = -% (-) for the Shannon entropy H (z) =
EiEINT x (i) (o)( with any sequence of regularizer scalings (Ne)EN S RR++.
Depending whether the space is continuous or discrete, the range of elements of ((v) will change, and consequently also the minimal domain on which regularizers must be defined. Let inf {A(A) A e Σ, (A) > 0}, and let S(v) [0, 1/2] if definition, 0(0 E θ =00) E S(v))) = for all x E (V)..
and R+ otherwise. By
Concretely, when is counting measure then S(v) - 00, 1]. when is uniform on [N] then S(v) NJ, and when v is a continuous distribution then S(v) = 4. In this work, we consider linearly
decomposable regularizers of the form the (2)) 1 1/6 V (ar), where
vy (I) = / f(x (()())))(
for some f : :S()) + R. We refer to the algorithm that selects p++1 using Eq. (1) with a regularizer of the form in Eq. (2) as V vyyreaguari FTRL with regularizer scaling f,c-
3 Applications of FTRL with linearly decomposable regularizers
In Section 5, we provide a general analysis of FTRL with linearly decomposable regularizers for arbitrary f. First, we motivate such general analysis by demonstrating the benefits of studying choices of f beyond traditional FTRL regularizers with multiple examples, including quantile regret. To do so, we state the following corollaries of our general FTRL regret bound (Theorem 2 in Section 5) that achieve "root-KL" and variance bounds respectively. Proofs are deferred to Appendix B.
Corollary 1. Suppose v E MM(OE)) Σ) and f R4 IR satisfies:
1. [(1==0:
2. f is twice continuously differentiable, f" > 0 on R4+, and f" 0:
3. either f or 1/ is increasing on R R4+:
4. there exist C1, C2
> 0 such that f" (f c1) c2.
For any sequence (C)) S CTo 9 (,, E), and T, wy-regularized FTRL with regularizer scaling Tpe /o2/t achieves
Rr S T+1 (dg//dv) - 91 VT
The regret bound above can be easily turned into a uniform root-KL bound under the following additional assumption (the result follows from Lemma 3 in Appendix B).
Corollary 2. If, addition to the assumptions of Corollary I, there exist k E R and ko E R4 with
f(x) S ki + kaæ Alg(1 + x), then
Rr(9) S
T+1 02
+ VT. Vez
Under different conditions on f. we also derive variance bounds with respect to the (intermediate) predictive distributions, similar AdaHedge [v+11] and AdaFTRL [OP15b], or with respect to "prior", as in [A21]. We state the conditions on the regularizer and the corresponding regret bounds in the following corollary.
Corollary 3. Suppose v E (O, and f S(V) - IR satisfies:
1. f(1/v(0)) 2 0:
2. f is twice continuously differentiable, f" 0 on interior(S(v)), and f0(++) 0.
For any sequence (Ee)EN S &. 9 (M, E), and T, Vi-regularized FTRL achieves
1. ( S Cr, M+41 (C(1/2 + E Varg (,(0)) 1/2 gives
Rr(g)= I (d)(dg/dv) + 11v C11/2 ΣT Varowalten (0).

---

2. 1f1/1" S.C Th+1 (Cu(0))144 Ei= Vara (,(0))) 1/2 for v -vju(O) gives
B /V/ + 1I Cu]))//11 + + Vargwa (x))
3.1 Examples of f-divergence FTRL
We now apply all three of these corollaries to more concrete choices of f. Note that in the setting of Corollary I, since v is a probability distribution and f is convex with f(1) = 0, the regularizer corre- sponds to an f-divergence, which we denote by V (dq//d)) = Dj (gll v) for any a E (M, E). In this case, we call a prior and refer the algorithm as f-divergence FTRL. To demonstrate the utility of Corollary 1, we now show how our result recovers the classical analysis for Hedge and applies to our new mot--logartthmic regularizer, both examples of f-divergence FTRL. We also use our general expression for the solution to FTRL with linearly decomposable regularizers, given by Lemma Section 5, to obtain explicit, novel expressions for some solutions of f-divergence FTRL.
Example 1 (Hedge). The regularizer corresponding to Hedge (and the Gibbs posterior from Bayesian inference) is given by f(x)
log æ, which satisfies D (-1 TT) KL (- α for any MMO, 2)). This choice satisfies the assumptions of Corollary with C1 = 1 + 1/ce and = 1, since 1/ f" is increasing, but does not satisfy the conditions of Corollary 2. Thus, we do not obtain uniform root-KL. bounds for Hedge: we conjecture this is in fact a limitation of Hedge and not merely an artifact of our analysis. We can, however, apply Corollary with 1 obtain
RT(g) < (LL(a v) +)+11 +1 1/2++ / Et= (a (e()).
Further, by Lemma 1, I-divergence FTRL. with regularizer scaling qe+1 recovers the familiar formula
exp(-7h+1 (0))
Fe+ (0) I Texp(- (O))((a)
Example 2 diveererge. Alquier [A21] analyzed f-divergence FTRL with constant regularizer scalings, obtaining variance bounds (Theorem 2.1) )) that require knowledge of the variance to tune the regularizer scaling. He specifically focused on the KL-divergence, covered by the previous example, and the x2 -ddivergence, corresponding f(x) = =x² -1 This clearly sutisfies the conditions of Corollary with C1 = 62 = 2, so we match the optimized bound of Alquier [A21, Corvllary 2.4] with
RT(g) S VT x² v) VTT
Further, the conditions of Corollary are satisfied with C = 1/2, so we obtain the novel, potentially much smaller variance bound (without requiring advance knowledge of the variances)
RT(g)= S 1/ (0 + 1] 11/4+ E Varg (x(
By Lemma 1, the x diveergen solution with regularizer scaling q++1 is
(0) (k 7411
where ki+1 E IR solves [ Th+ T L.)) = 1, which matches the formula obtained by Alquier [A21, Example 3.2].
Example 3 (abNormal). We call f-divergence FTRL with any f satisfying the conditions of Corol- lary 2 abNormal. One such example is f(x) = S v2 [og( 8) ds, which satisfies the conditions of Corollary I with 2 and Corollary 2 with k 0 and l2 22 Thus, we obtain
1/v2 since f is increasing, and satisfies the conditions of
Rr(g)= < 2/ (T +T 1)(1 KL (q v)) V8T
The f-divergence FTRL solution with regularizer scaling 7 is given by
x1)1 = exp (ki+1 - M1+1 T. (0)) /2
where ki+1 E R solves [(exp (kit1 Th- T=-L:
/2] 1]v(d0) 1. Note that this formula is heuristically similar to NormalHedge when ( = N, which assigns weights to experts according to
wr(1) α EE= (Cs, wa) - I exp | (ls, wa) (1) ( 120-11)
where Ca-1 solves EiE(N exp([>>=) (fo, wa) LL-1 10)] /2c,-1) =eN.
5

---

3.2 Lower bound for quantile regret
Bounds for quantile regret and KL regret can be related by observing a) that for 6(. denoting a point-mass on the i,th best expert with respect to LT,
RT())))) S Rr(ue),
where c = i./N and u, = 1 that KL (ue || Unif([ = log(1/c). Thus, KL upper bounds are also upper bounds on quantile regret and quantile regret lower bounds are also lower bounds certain KI. regrets. With this in mind, we provide the first general lower bound for quantile regret on experts. Our lower bound is matching (up lower order terms) the leading term in our upper bound for quantile regret achieved by abNormal (Example 3) when v is uniform on [N] and is uniform on only the top quantile of experts, establishing the minimax rate of quantile regret as log(/e)).
66) is the uniform distribution over the top ig experts, and b)
Theorem 1. For all N E N there exists probability distribution p on 10, 1J such that for any sequence of player predictions (w:)teN C simp([N]), ic E (1...., [/ and T E N,
EapT (r(( 2 (T/2)) (log(1/e) 2 log +/ 22 2 log N log
where ((5.) is the point-mass on the i,th best expert with respect to Lr and c = i./N.
3.3 Intuition for f-divergence FTRL in the KL regret paradigm
The conditions on f in Corollary 1 are essentially the minimal conditions needed for the summation terms in Theorem 2 to cancel with each other regardless of the actual losses. Intuitively, to achieve f-divergence regret bounds with f f-divergence FTRL using the bound of Theorem 2, these terms must cancel so that there is no dependence in the final bound on the regularity of the distributions actually selected by the algorithm. The condition on f in Corollary 2 is essentially the minimal condition needed for Jensen's 's inequality to imply D, (-11.) X (- -). That it is possible to satisfy both of these conditions simultancously is the crucial observation that enables our result.
All regularizers to which both Corollaries and 2 apply are essentially equivalent to f(x) J 2 log(1 + s)ds, meaning they have the same asymptotic growth rate. To this, first observe that this f has the minimum amount of curvature needed to satisfy f" (f + c1) 02 since (zvloggz) x)- (I /ooloog xz)" is asymptotically constant. Second, this f has the largest asymptotic growth rate that still satisfies f((x) < ki + /log/ + æ). These two facts together constrain the shape of the roga-logaii choice.
4 Semi-adversarial regret bounds
We now turn to another perspective on prediction with expert advice for which FTRL with linearly decomposable regularizers is optimal. The aani-adversarial paradigm (introduced by [BNR20]) consists of family of constraints the adversary's 's choice of loss distribution, and the goal of the player is to learn as well as possible for the true constraint without having to know the constraint in advance. More precisely, the setting is characterized by unknown time-homogeneous conver constraint on the adversary's 's choice of loss distribution, which formally represented by a convex set of probability distributions on 11. denoted by D. At each round t, the adversary is free to select any distribution from D sample e, from.. Note that when the worst-case adversarial setting is recovered, and when DD is a singleton, the stochastic setting is recovered. In this section, we describe new FTRL algorithm (FTRL-CARL) that achieves minimax optimal expected regret without requiring knowledge of D in advance.
the set of all probability distributions,
4.1 Adaptive minimax optimality
Minimax regret in the semi-adversartis paradigm is quantified using few key objects that summarize D. The first is the collection of effective stochastic gaps, defined for each expert i E [N] by
A inf max Ee-p [E(1) - {((').
PED F'E[N]

---

Using these, Bilodeau, Negrea, and Roy [BNR20] define the stochastic gap
A = min (A, e [M] A; > 0}.
The second object Bilodeau, Negrea, and Roy [BNR20] define is the set of effective experts, which is subset of [N] defined by
Io = f [N]
=3
This is the set of all experts who are optimal in expectation for some element of D (or possibly in the limit along some sequence in D). The number of effective experts is then No [Zol-
In this paradigm, the goal is to compete against the best expert. Letting 6, denote point-mast on expert i, for notational simplicity we set RT [ Rō; Further, although the player does not expect to have knowledge of 'D in advance, the goal is to develop methods that do as well as they possibly could have if they had access to properties of in advance. To characterize this, we say an algorithm (which only has knowledge of N in advance) is adaptively minimax optimal if there exists constant C' such that, for all N and (No; Ao) pairs, the expected regret of the algorithm within a factor of C' from the minimax regret had the algorithm had access to ( (No, An) in advance, for sufficiently large T (where sufficiently large may depend on N, No. and Ap). For precise mathematical formulation of this concept, see Section 3.1 of Bilodeau, Negrea, and Roy [BNR20].
When No 1, Proposition of Mourtada and Gaïffas [MG19] shows that the minimax regret is of order no smaller than (log / and when No > 1, Theorem of Bilodeau, Negrea, and Roy [BNR20] shows that the minimax regret is of order no smaller than / log Ng. Bilodeau, Negrea, and Roy [BNR20] prove that Hedge is not adaptively minimax optimal in the semi-ad paradigm, and their argument applies to other similar Hedge-based algorithms, such as prod [CMS07]. AdaHedge [v+11], 1J. and Adapt-ML-PProd (GSv14). Further, they provide an algorithm that achieves
ERT & Tlog No T[N, =1] log N
I[No 1] (log N)3/2 Do
(3)
Ao
Since N[ 1](log N)3/2277 lower order when No > 1, this algorithm is adaptively minimax optimal. We now present a new algorithm, FIRL-CARI, which is also adaptively minimax optimal and achieves a better regret bound for small T.
4.2 Semi-adversarial regret bound for FTRI-CARI
Let he [0, 1] + R be given by
ho(x)= x 1 log(1/zr) / erf (Vlog(1/z)) +x(N 1) x (0.
1T/22
==
set Hc(w) = EiEnN li(w(()), and define FTRL-CARL be FTRL with v defined as counting measure, regularizer V/ (w) He(w), and regularizer scaling 1) 2/vl. Note that this corresponds to FTRL with a linearly decomposable regularizer, and an intuitive explanation for this choice of regularizer can be found Subsection 4.3. We then have the following regret bound for FTRL-CARL, which removes the term I[N, [] 3)3/2 A from Eq. (3).
Corollary 4. For any time-homogeneone convex constraint D, FTRL-CARL achieves:
For all T,
ER S 2T log N,
and ifT 8(log 2
ER, S / 2T No + 25 log N A
Corollary 4 follows from Theorem 3 in Appendix D, which is more refined regret bound.
4.3 Intuition for FTRL-CARL in the semi-adversarial paradigm
The CARL. regularizer can be motivated by the following intuition from the Hedge algorithm. For i.i.d. losses, the upper bounds for Hedge [Theorem 2, MG19] are only optimal with regularizer scaling
7

---

Z (log / and matching lower bounds for the adversarial setting suggest this regularizer scaling constraint is actually necessary for optimal performance. Such regularizer scaling ensures that the weights of each suboptimal (in expectation) expert decay fast enough. In the semi-adversarial paradigm with more than one effective expert, FTRL-CARE (of [BNR20]) can be interpreted as Hedge with an adaptive regularizer scaling that asymptotically satisfies 1)t Z / (log No)/t. This smaller regularizer scaling applied to the effective experts is necessary to incur asymptotically VTlog No regret. However, since this regularizer scaling is smaller, when there are two or more effective experts the weights assigned to the ineffective experts seemingly are slightly too large.
To rectify this, heuristically, would be ideal have expert-speciff regularizer scalings of size Vllo No)/t for the effective experts and /log N)/t for the ineffective experts. Since the effective experts will have weights on the order of 1/No and the ineffective experts will have weights smaller than 1/M, the expert-specific regularizer scaling n), (i) log(1//w (i))/t may plausibly achieve the desired behaviour.
The weights of Hedge are defined by the equation (og(1/,;(()) = m/ ( + Ae), where X is chosen to ensure the weights are normalized. Replacing 7) with our heuristic yields log(1 //)((i) e/ [og(1/ (i))/ (1) + Xe), which can be rearranged obtain
Vlog( (/)))(()) Sr (1) + +x).
By Lemma 1, this is exactly the formula for the weights produced with FTRL for the regularizer - He and regularizer scaling 7/- = c/ etv
As Theorem 3 shows, our modification to the Hedge algorithm is sufficient to yield semi-adversarial regret bounds with expected regret contribution of size (log / from the ineffective experts, improving the order of the regret bound for FTRL-CARE when No > 1.
5 FTRL analysis for general expert spaces
Finally, we analyze the general performance of FTRL with a linearly decomposable regularizer. First, Lemma provides a closed-form expression for the FTRL solution on general spaces. Specifically, reduces solving the FTRL optimization problem of Eq. (2) to finding a root of a one-dimensional equation (Eq. (4)), rather than solving a complex, possibly infinite dimensional, optimization problem. Second, Theorem 2 provides our fundamental regret bound for FTRL with such regularizers, which we have used to obtain the results in Sections 3 and 4. generalizes the well-known results involving local norms from the finite dimensional case [AR09; ZS19 O19]. and retains an additional summation term (usually uniformly bounded in FTRL analyses) that is crucial both for tight root-KI -LL- regret bounds and for tight bounds in the semi-adversarial paradigm. All results in this section are proved in Appendix A. For the remainder of this section, let v E M Σ) be fixed and arbitrary.
5.1 Computing FTRL with linearly decomposable regularizers
For continuously differentiable S(v) + I., let my inf infzes(v) f'(x), My supres(s) f'(x). and Ty: (v) max(min(y,, M, my We focus the setting where f' is strictly increasing, and thus (v) truncates its argument to the domain of [5]-1.
Lemma 1. Suppose f S(v) + R is twice continuously differentiable with fr > 0 on interior(S(v)) and (0())) O. For any L E 0 and 1)
x0 = (T
+*))
satisfies x² E air (x) (LL x)2 + (z))), where kn E solves
f fIM (T v(d0) 1.
Further, this solution is unique up to modification on set of v-measure O.
For finite expert classes, solving the normalizing equation provided by Lemma 1 to given precision is essentially the same difficulty normalizing the weights for the classical Hedge algorithm. For
8

---

example, for FTRL-CARL the range of the normalizing constant scales with log N, and solving this using the bisection method would require only (loo log .) times more computation than normalizing Hedge. For uncountable expert classes, many of the general algorithms for prediction with expert advice from previous work are not easily modified to apply, and the standard analyses of regret bounds rely heavily on finite N. In this setting, solving the FTRL normalizing equation essentially as difficult as normalizing the posterior distribution for Bayesian inference. That is, often computationally intractable, yet regularly studied for its theoretical properties. Extending approximation techniques for Bayesian inference to approximate the solution to this optimization problem is interesting question for future work.
5.2 Choosing obtain specific regret bounds
In order to state our generic decomposition for the regret of FTRL algorithms on abstract spaces, rely on the definition of the one-dimensional Bregman divergence, which is defined for any continuously differentiable, strictly convex f E - IR by
By(r;u) = f(x) f(v) f')((x
Theorem 2. Suppose / S(v) + R is twice continuously differentiable with f" > 0 on interior(S(v)) and (0(++) > O. For all sequences (l1)tn S. f and (me)xen C IR, there exist Er+1 E Conv( T(+1) and žet1 E Conv (n, such that for all a E M,) (Z141)EEN E {(B++1)EEN (2441)ENN) and T. V rfggullarrzzed FTRL achieves
1 Vi or+1
(g
(g) S
min (x)
dv
1h =EX(M)
(5)
ni (l((0) - m2)
-(11 1
wy (y((r+t)
2 (*( (0)) v(d0)
m/)
M1+1
where
3it1 E arg min (Ee 1, x)x 17.
1
B,(x(0):.,())<((())
xEL
Further, if if ((()) 2 my, then 2411 S Tt pointwise.
Theorem is a general result that can be used prove regret bounds for variety of settings under the general FTRL framework we describe, as we have already done in Sections 3 and 4. Furthermore, highlight that the functional form of Theorem 2 makes it clear how select the regularizers for both the quantile regret and aami-adversaria paradigms. Specifically, in the former, the terms in summation Eq. (5) are balanced to cancel, while the latter, the terms in summation in Eq. (5) are balanced to contribute the same order to the regret. These two cases correspond to the relationship
f -
Since the generic bound we obtain in Theorem yields components based upon integrals of both f and f/ balancing these terms without free tuning parameters requires Eq. (6) approximately hold. Heuristically, trying to balance these terms with tuning parameters rather than by the choice of seems to lead to non-adaptive or non-uniform bounds. Hedge provides example of this for both the semi-adversarial and KL regret cases. In the semi-adversarial paradigm, Bilodeau, Negrea, and Roy [BNR20] showed that Hedge cannot be tuned in way that is minimax optimal and agnostic to the semi-adversarial constraint that prevails. Similarly, without tuning the regularizer scaling to be dependent on the comparator distribution (equivalently. the quantile of interest), KL (and quantile) regret bounds for Hedge are suboptimal.
5.3 Applications of root-KL. regret bounds for continuous experts
We now briefly discuss two applications that highlight the immediate benefits of our general analysis (and consequently results of Section 3) applying beyond finite expert spaces.

---

Predicting as well as the terminal posterior using f-divergence FTRL A reasonable choice of distribution measure regret against the posterior distribution मि after having seen T rounds of data. A consequence of Corollaries 1 and 2 is that, for bounded log-likelihoods, the total loss incurred by making predictions according to f-divergence FTRL. for suitable f is bounded by the loss incurred by the terminal posterior स plus an excess regret of the order /TKL ( || .T.. This excess loss is smaller than T + KL (fr x). which is the best available bound for excess loss when predicting according to the posterior it at each round E [T'. and smaller than vT KL (ft x), which is the best available bound for the excess loss when predicting with Hedge if it is not tuned with a priori knowledge of KL (#r || TT) These worse excess loss bounds follow from the analysis contained in Zhang [206], although he only compares against the "true" data- getta-generatng parameter.
Extending the interpretation of Orabona and Pál [OP16] by Foster, Krishnamurthy, and Luo [FKI.20] to countable union model classes, we can consider infinite sequence of disjoint finite expert classes (note any nested sequence can be made disjoint), 11, o and let θ = Um21 mm Assigning to & the prior π (f) x n for each 0 E Om. we recover the following regret bound for f-divergence FTRL with regularizer scaling T oc 1/v from Corollary 2:
Model selection using f-divergence FTRL
(50 So 20 (vT(log 00ml + llggm) for all 6 E Om and all m E N.
Limitations
One limitation of our results, which is common in the online learning literature, is that they only apply to bounded losses. The extension of learning theory to unbounded losses has seen increased interest in recent years [GM20; A21; MVZ21J, although it remains major open problem to achieve guarantees for arbitrary losses. In particular, log loss for many nonparametric learners is not covered by the current unbounded loss literature, and will have important implications in statistical learning and density estimation when resolved.
A second limitation of our work is that finding the implicit normalizing constant-k" in Lemma 1-is computationally difficult, as was also observed by Alquier [A21]. is at least as costly as finding the normalizing constant for Bayesian posterior (or running Hedge), which corresponds to one evaluation of the left-hand side of Eq. (4). For Hedge, where f (x) = x log(z), one evaluation of that of Eq. (4) to fixed precision will take number of evaluations depending on the desired precision and the range of possible values, and so FTRL with general f will be that marginally more computationally expensive than Hedge. Variational approaches for Bayesian inference, which avoid direct normalization of the posterior, may also be applicable for FTRL with general f. and that line of inquiry may lead novel, efficient, and high-performance learning algorithms.
equation is sufficient, but in general finding the root
A final limitation is that we do not obtain variance bounds together with uniform ro bounds, although our approach leads to both separately (Corollary and Corollary 2), so we are optimistic techniques can lead to such bounds, which would resolve multiple open problems.
Acknowledgments and Disclosure of Funding
JN is supported by an NSERC Vanier Canada Graduate Scholarship and the Vector Institute. BB is supported by an NSERC Canada Graduate Scholarship and the Vector Institute. FO is partly supported by the National Science Foundation under grants no. 1908111 "AF: Small: Collaborative Research: New Representations for Learning Algorithms and Secure Computation" and no. 2046096 "CAREER: Parameter-free Optimization Algorithms for Machine Learning.. DMR is supported in part by an NSERC Discovery Grant, an Ontario Early Researcher Award, and stipend provided by the Charles Simonyi Endowment, We thank Mufan Li and Mahdi Haghifam for helpful feedback on early drafts.
10

---

References
[A+17]
A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire. "Corralling a Band of Bandit Algorithms". In: Proceedings of the 30th Conference on Learning Theory. 2017.
[A21]
P. Alquier. Moon-Exxonentially Weighted Aggregation: Regret Bounds for Unbounded Loss Functions". In: Proceedings of the 38th International Conference on Machine Learning. 2021.
[AB09]
J.-Y. Audibert and S. Bubeck. "Minimax Policies for Adversarial and Stochastic Bandits". In: Proceedings of the 22nd Conference on Learning Theory. 2009.
[ABLII] J.-Y. Audibert, S. Bubeck, and G. Lugosi. "Minimax Policies for Combinatorial Predic-
tion Games". In: Proceedings of the 24th Conference on Learning Theory. 2011.
[AC65]
M. M. Ali and L. K. Chan. "Some Bounds for Expected Values of Order Statistics". Annals of Mathematical Statistics 36.3 (1965), pp. 1055-1057.
[AHR08]
J. D. Abernethy, E. Hazan, and A. Rakhlin. "Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization", In: Proceedings of the 21st Conference Learning Theory. 2008
[AR09]
J. D. Abernethy and A. Rakhlin. "Beating the Adaptive Bandit with High Probability". In: Proceedings of the 22nd Conference on Learning Theory. 2009.
[B42]
W. Birnbaum. "An Inequality for Mill's Ratio". Annals of Mathematical Statistics
13.2 (1942), pp. 245-246.
[B60]
H. Bauer. "Minimalstellen matik 11 11.1 (1960), pp. 200-205.
Funktionen und Extremalpunkte. "l"hArchiv der Mathe-
[BM89]
J. Bretagnolle and P. Massart. "Hungarian Constructions from the Nonasymptotic View- point". Annals of Probability 17.1 (1989), pp. 239-256.
[BNR20]
B. Bilodeau, J. Negrea, and D. M. Roy. Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization. arXiv:2007.0653 2020,
[C+97]
N. Cesa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold, R. E. Schapire, and M. K. Warmuth. "How to Use Expert Advice". Journal of the ACM 44.3 (1997), pp. 427-485. K. Chaudhuri, Y. Freund, and D. J. Hsu. "A Parameter-Fre Hedging Algorithm". In: Advances in Neural Information Processing Systems 22. 2009.
[CFH09]
[CL06]
N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge: Cam- bridge University Press, 2006.
[CMS07] N. Cesa-Bianchi, Y. Mansour, and G. Stoltz. "Improved Second-Order Bounds for Prediction with Expert Advice". Machine Learning 66.2 (2007), pp. 321-352.
[CV10]
A. Chernov and V. G. Vovk. "Prediction with Advice of Unknown Number of Experts". In: Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence. 2010.
[d+14]
S. de Rooij, T. van Erven, P. D. Grünwald, and W. M. Koolen. "Follow the Leader If You Can, Hedge If You Must". Journal of Machine Learning Research 15.37 (2014),
pp. 1281-1316.
[F+16]
D. J. Foster, Z. Li, T. Lykouris. K. Sridharan, and É. Tardos. "Learning in Games: Ro- bustness of Fast Convergence". In: Advances in Neural Information Processing Systems
30. 2016.
[FKL20]
D. J. Foster, A. Krishnamurthy, and H. Luo. "Open Problem: Model Selection for Contextual Bandits". In: Proceedings of the 33rd Conference Learning Theory. 2020. Generalization of On-Line Learning
[FS97]
Y. Freund and R. Schapire. "A and an Application to Boosting". Journal of Computer and System Sciences 55.1 (1997), pp. 119-139.
[GM20]
P. D. Grünwald and N. A. Mehta. "Fast Rates for General Unbounded Loss Functions: From ERM to Generalized Bayes".Jae .Journal of Machine Learning Research 21.56 (2020),
pp. 1-80.
[GSv14]
P. Gaillard, G. Stoltz, and T. van Erven. "A Second- Order Bound with Excess Losses".
In: Proceedings of the 27th Conference on Learning Theory. 2014.
[H+20]
N. J. A. Harvey, C. Liaw, E. Perkins, and S. Randhawa. "Optimal Anytime Regret with Two Experts". In: Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science. 2020.

---

[HK10]
E. Hazan and S. Kale. "Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs". Machine Learning 80.2 (2010), Pp. 165-188.
[K+15]
W. Krichene, M. Balandat, C. Tomlin, and A. Bayen. "The Hedge Algorithm on Continuum". In: In:PProces Proceedings of the 32nd International Conference on Machine Learning. 2015.
[K13]
W. Koolen. "The Pareto Regret Frontier". In: Advances in Neural Information Pro- cessing Systems 26. 2013.
[Kv15]
W. M. Koolen and T. van Erven. "Second-Order Quantile Methods for Experts and Combinatorial Games". In: Proceedings of the 28th Conference on Learning Theory. 2015.
[L69]
D. G. Luenberger. Optimization by Vector Space Methods. Wiley, 1969.
[LS14]
H. Luo and R. E. Schapire. "A Drifting-Gand Games Analysis for Online Learning and Applications to Boosting". In: Advances in Neural Information Processing Systems 27. 2014.
[LS115]
H. Luo and R. E. Schapire. " "Achieving All with Parameters: Adanormalhedge". In: Proceedings of the 28th Conference on Learning Theory. 2015. N. Littlestone and M. K. Warmuth. "The Weighted Majority Algorithm". Information
[LW94]
and Compulation 108.2 (1994), pp. 212-261.
[LWZ18]
Luo. C.-Y. Wei, and K. Zheng. "Efficient Online Portfolio with Logarithmic Regret". In: Advances in Neural Information Processing Systems 32. 2018.
[MG19]
J. Mourtada and S. Gaïffas. "On the Optimality of the Hedge Algorithm in the Stochastic Regime." Journal of Machine Learning Research 20.83 (2019), pp. 1-28.
[MV221] J. Mourtada, Vaškevičius, and N. Zhivotovskiy. Distribution-Free Robust Linear Regression. MrXiv:2102.12919, 2021.
[O19]
F. Orabona. A Modern Introduction to Online Learning.
2019. F. Orabona and D. Pál. Optimal Non-Asymptotic Lower Bound on the Minimax Regret of Learning with Expert Advice. arXiv:15 11.02167.. 2015.
[OP15a]
[OP15b]
F. Orabona and D. Pál. "Scale-Free Algorithms for Online Linear Optimization". In: Proceedings of the 26th International Conference on Algorithmicc Learning Theory. 2015. F. Orabona and D. Pál. "Coin Betting and Parameter-Free Online Learning.. In: Advances in Neural Information Processing Systems 29. 2016.
[OP16]
[RST11]
A. Rakhlin, K. Sridharan, and A. Tewari. "Online Learning: Stochastic, Constrained, and Smoothed adversaries". In: Advances in Neural Information Processing Systems 25. 2011.
[S07]
S. Shalev-Shwartz. "Online Learning: Theory, Algorithms, and Applications". PhD thesis.
The Hebrew University, 2007.
[SST11]
N. Srebro, K. Sridharan, and A. Tewari. "On the Universality of Online Mirror Descent".
In: Advances in Neural Information Processing Systems 24. 2011.
[v+11]
T. van Erven, P. D. Grünwald, W. M. Koolen, and S. de Rooij. "Adaptive Hedge". In:
Advances Neural Information Processing Systems 25. 2011.
[V90]
V. G. Vovk. " "Agrregating Strategies". In: Proceedings of 3rd Workshop on Computational
Learning Theory. 1990.
[vvK18]
D. van der Hoeven, T. van Erven, and W. Kotlowski. "The Many Faces of Exponential Weights in Online Learning". In: Proceedings of the 31st Conference On Learning Theory. 2018.
[WL18]
C.-Y. Wei and H. Luo. "More Adaptive Algorithms for Adversarial Bandits". In: Pro- ceedings of the 31st Conference On Learning Theory. 2018
[Z06]
T. Zhang. cefformation-Theoreee Upper and Lower Bounds for Statistical Estimation".
IEEE Transactions on Information Theory 52.4 (2006), pp. 1307-1321.
[ZS19]
J. Zimmert and Y. Scldin. "An Optimal Algorithm for Stochastic and Adversarial Ban- dits". In: The 22nd International Conference on Artificial Intelligence and Statistics. 2019.
Checklist
1. For all authors...
12

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [No] We do not
any negative societal impacts of these theoretical results.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See appendices.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A] All the experiments are deterministic
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] All computations were done on CPU on a personal laptop computer.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "sK5CaOSt3Lf", "reviewer": "Reviewer_o5hQ", "summary": "The paper studies Follow the Regularised Leader algorithms for the Hedge settings.\n\nThe paper starts with an overview of FTRL in adversarial settings. A frighteningly general setup is described and Theorem 1 for the adversarial regret is obtained. It is claimed that the theorem allows one to obtain bounds similar to some known bounds from the literature.\n\nThen the semi-adversarial settings are discussed (the definition of semi-adversarial covers the adversarial settings on one end of the spectrum and purely stochastic on another).\n\nThe paper presents FTRL-CARL and obtains a performance bound on it in terms of effective stochastic gaps.\n\nThen the paper discusses bounds in terms of f-divergence and obtains a lower bound matching upper bounds.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is not very kind to the reader and the presentation is often very formal. For example, I understand the most important results were obtained for the case of finitely many experts. Was it really necessary to introduce the general framework with Radon-Nikodym derivatives?\n\nIt is hard for me to appreciate the importance of CARL bounds as the concept of effective stochastic gaps is not clear to me. Why are they important and how do they characterise the distribution class? \n\nThe matching lower bound is something I can understand and appreciate and find very important.\n\nFinally, I can't help thinking that discussing semi-stochastic settings and f-divergence bounds in one paper is somewhat artificial.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Yc_aeMxflsV", "reviewer": "Reviewer_6vq4", "summary": "This paper considers the problem of prediction with expert advice,\nand focuses on quantile regret bounds that depend on the comparator distribution\nand semi-adversarial paradigm,\nwhich is an intermediate setting between stochastic one and adversarial one.\nIn the paper,\nminimax optimal regret bounds for both paradigms are shown.\nThis bound is achieved by follow-the-regularized-leader (FTRL) algorithm with a newly designed root-logarithmic regularizers.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \n\nThe originality of the contributions in the semi-adversarial paradigm seems somewhat limited.\nThe method of analysis appears to be almost the same as that in this literature [BNR20],\nin which the semi-adversarial paradigm has been introduced.\nIn addition, the semi-adversarial setting with $N_0 = 1$ has already been treated in [GSv14] (as Assumption 1 in [GSv14] holds), and it has already been proved that an upper bound of $O(\\log N / \\Delta_0)$ can be achieved in this case.\nWe would like to note that the semi-adversarial setting is also a special case of adversarial regimes with a self-bounding constraint in [ZS21].\n\nQuality:\n\nAs far as I can see, no technical errors have been found.\nI think the authors are careful and honest about evaluating both the strengths and weaknesses of their work.\n\nClarity:\n\nThe technical part is clearly described.\nHowever,\nthe comparison with existing studies is not very clear.\nIn particular,\nI did not know if the proposed algorithm was more effective than the standard Hedge algorithm (in [MG19]) and algorithms with second-order regret bounds (in [GSv14], [CMS07])\nin semi-adversarial paradigm.\n\nSignificance:\n\nThe theoretical results on quantile regrets will have a certain impact.\nIn particular, as far as I know, this is the first time that a lower bound for for quantile regret on finite expert classes has been given.\nCompared to this, the impact of the results on semi-adversarial setting seem to be somewhat limited, for the reasons mentioned above.\n\n\n\n[ZS21]: Zimmert, J., & Seldin, Y. (2021). Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits. J. Mach. Learn. Res., 22, 28-1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think limitations and societal impact have been well discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SX3zrahD35", "reviewer": "Reviewer_syJt", "summary": "In this paper, the authors tackle the problem of obtaining low semi-adversarial and quantile regret for the problem of prediction with expert advice with possibly uncountably many experts. To this end they develop a general technique to obtain methods for the problem based on the (measure-theoretical) FTRL meta-algorithm. They show that appropriate choices of regularizers can yield algorithms for the semi-adversarial (with improved dependency on the number of experts) and quantile settings (asymptotically matching state of the art). Finally, they give a lower-bound on the quantile regret, showing that their results are minimax optimal.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n\n- The technique used (FTRL with uncountably many experts and a clever general technique to pick regularizers) is elegant, general, and effective;\n- The lower-bound for the quantile setting, although not very well advertised, is a solid contribution to the field;\n\n# Weakenesses\n\n- The presentation of the paper is not optimal: it is at times hard to follow, some technical statements do not give much information to the reader, and the lack of examples (or at least their bad distribution through the paper) makes it hard to properly interpret some results.\n- The measure theoretical generality is interesting, but the paper lacks a discussion of why such generality is actually worth the effort;\n- The theoretical improvements on the regret seem marginal (although the experiments show that the improvements can be substantial even for a small number of experts). This by itself is not a serious weakness (incremental research can still be good and is important), but the lack of discussion on the interpretation of the result makes this weigh negatively in the paper. They seem to claim sometimes that their semi-adversarial regret bounds (Thm 2) are minimax optimal, but it is not clear if it is true;\n- There is a \"hidden\" section: there are experiments in the appendix, but they are never mentioned in the main paper. And the big difference between the FTRL-CARL and previous algorithms is poorly discussed;\n\n# Summary of the decision\n\n To fix some of the weaknesses the authors need to change a lot on the paper. Although I believe there are interesting contributions in the paper, it would deserve another round of reviews after the proposed changes, so I don't think it can be fixed for the camera-ready deadline. Of course, this decision is not necessarily final and can be changed based on the authors' response.\n\n# Detailed discussion\n\nI really enjoyed the techniques used, but I had a hard time going through the paper. The two main aspects that make the paper hard to read are the lack of well-placed examples and the lack of discussions of the results. For example, on section 2 it would have been great to see that we can get the Shannon entropy in eq. (1) (this is done only by the end of the paper). Also, the paper has almost no examples that exploit the measure-theoretical generality, so it is not clear why the authors go through this route. Even if the reason is purely theoretical novelty and generality, I feel this should have been better discussed.\n\nOne section that was poorly discussed was section 3, which apparently should be one of the main sections of the paper. Lemma 1 and Theorem 1 are hardly interpretable and the authors do not have any discussion trying to interpret these statements. For example, it is not clear how hard the iterate given by Lemma 1 is to compute! (The authors do claim that is a \"simple task of finding the root of a 1-dimensional equation\", but in the *last* section of the paper finally say it is hard to compute it. It then makes the reader wonder how useful these techniques really are. I still think these are very valuable, even if sometimes only theoretically, but the lack of up-front discussion makes the results very confusing, and leaving mention of hardness only to the end is fishy).   As another example, it is really hard to interpret the second summation in Theorem 1 and the authors do not try to explain when the summation can be reasonably bounded. In fact, nowhere in the main body of paper the authors actually use Theorem 1 (and hardly use Lemma 1), so these could have been easily deferred to the appendix, leaving more space for discussion.\n\nFor the semi-adversarial regret bounds on section 4.1, the case $T > T_0$ could have been deferred to the appendix (it could have been at least stated in a simplified way probably). It takes a lot of valuable space and there is little to no information we can obtain from it. Certainly seeing how the derivation of simpler bounds such as the one on Pg. 5 or on remark 1 follow from these general bound would help, but as it is it just takes valuable space from the authors. As an example of what could have been discussed, the regret bound for $T \\leq T_0$ has no dependence on $\\Delta_0$ or the additional $\\log N$ term. Could this explain the excellent performance seen in the experiments? Also, it is not totally clear when $T_0$ is big or small, making it harder to understand when the first tighter bound holds. Also, although the authors do discuss some of the intuition behind $h_C$, it would have been great to know that it is a by-product of Lemma 1 from the start.\n\nFor root KL and quantile regret bounds, it is again hard to interpret the results. Corollary 2 is the main regret bounds but it is really hard to know what are some reasonable choices of $f$ so that constants $k_1$ and $k_2$ exist. A formal statement of the $\\epsilon$-regret bounds the authors can get from Corollary 2 would have been extremely helpful. The lower-bound is a solid and good contribution, but it is hard for the reader to see if Corollary 2 indeed yields minimax optimal $\\epsilon$-regret. Maybe this is exactly the point of Example 3, but the authors do not make it clear.\n\nIn fact, the examples from section 4.2.3 would have been extremely helpful earlier in the paper (even with the instantiations of the regret bounds deferred to the end). I strongly suggest bringing some of these examples earlier in the paper. Even in the examples some parts are not well explained (on example 2 it is not clear when/if $k_{t+1}^*$ is efficiently computable, and in fact it seems it can be relatively hard to compute). \n\nFinally, the experiments section is hidden and I found it out almost by accident. Even being in the appendix (and thus, not bounded by space), this sections still lacks discussion of the results. It is not clear why the difference of FTRL-CARL is so big if compared to META-CARE. Like I mentioned, it might be because of the case $T \\leq T_0$ or even better constants, but the authors do not discuss these aspects.\n\n# Comments Post Rebuttal\n\nThe authors provided concrete changes (with thorough discussion) that will improve the presentation. Furthermore, they showed I had misunderstood the contribution of one of the results, and the committee discussion helped me better appreciate the results, so I'm increasing my score to 7.\n\nI still think the papers deserves and needs a better presentation, even more so for NeurIPS' wide audience. I again encourage the authors to apply the proposed changes and use the extra space to aid in the papers readability and to help the reader understand each of the results (some results are hard to parse for an outsider like me).\n\nAnd thanks a lot for the authors for the very solid and thorough rebuttals! ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Dyq3aROQEFu", "reviewer": "Reviewer_FaPw", "summary": "This paper studies the classic expert problem and focuses on developing \nparameter-free algorithms with two specific guarantees: 1) better regret \nbounds for the semi-adversarial paradigm proposed by Bilodeau et al. 20; \n2) a KL-type regret bound similar to that achieved by NormalHedge \n(Chaudhuri et al. 09) and other variants, possibly for an uncountable \nset of experts. The authors achieve these two goals using the standard \nFTRL framework with two new root-logarithmic regularizers, inspired by \ntheir general analysis that requires some specific properties of the \nregularizer. A matching lower bound for the KL-type regret is also \nprovided. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall this paper makes solid contributions to a fundamental problem, \nand I support acceptance. What I particularly like is achieving the \nKL-type regret with an FTRL approach, different from all existing \nalgorithms (NormalHedge, AdaNormalHege, Squint, Coin-betting, etc.). I \nbelieve at least several researchers have tried to do so but failed. \n\nHowever, I do have some concerns and questions:\n\n1) In the semi-adversarial case, what happens when \\Delta_0 is very tiny \n(or \\Delta_i is simply 0 for every i)? Does FTRL-CARL insure some \n\"safety\" guarantee (ideally \\sqrt{T\\ln N}) always, besides the guarantee \nstated in Thm 2? \n\n2) Although achieving KL-type regret with yet another algorithm is nice, \nthe guarantee in Corollary 2 is in fact strictly worse than that of \nAdaNormalHedge (Luo and Schapire 15) and Squint (Koolen and van Erven \n15), in the sense that the latter not only achieve the KL bound, but \nalso some data-dependent bounds which have some nice implications. In \nfact, one implication is exactly an logarithmic bound for the stochastic \nsetting or more generally logarithmic bound plus \\sqrt{C} regret for a \ncorrupted stochastic setting with C being the amount of corruption (this \nlast result is not stated formally in these papers but the derivation is \nstraightforward; one can see some examples in the bandit setting such as \n[1]). In fact, I personally think the corrupted setting is more natural \nthan the semi-adversarial setting considered in this work as an \nintermediate setting between the stochastic case and the adversarial \ncase. From this perspective, AdaNormalHedge and Squint appear to be much \nmore appealing. In fact, there are also recent improvements over these \nworks as well, such as [2]. \n\n\nOn writing:\nThe paper is generally well-written, but I have some comments below.\n\n1) While I appreciate presenting the result in the most general form \nusing measure theory language, this also makes the results hard to \ninterpret in most places. I would prefer presenting the finite case in \nthe main text and deferring the general case to the appendix. The \nsemi-adversarial results also seem to be specific to the finite case \nanyway? (BTW if this is true it should be mentioned at the beginning of \nSec 4.1.) \n\n2) More explanations after some of the theorems/lemmas (such as Thm 1) \nwould be very helpful.\n\n3) I wonder whether the proposed algorithms are really that similar to \nNormalHedge (which the author claim). Looking at their update rules, I \nwould only say that they are somewhat connected (maybe I am just not \nseeing the deeper connections).\n\n\n[1] Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm \nfor stochastic and adversarial bandits. JMLR 2021.\n\n[2] Liyu Chen, Haipeng Luo, and Chen-Yu Wei. Impossible Tuning Made \nPossible: A New Expert Algorithm and Its Applications. COLT 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A. This is mostly a theoretical work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously support acceptance of the paper. The writing of the paper requires improvement and I hope that the authors will implement changes promised to the reviewers.
Decision: Accept (Poster)