Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers

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.

heading: 1 Introduction
text: We focus on 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 selected distribution. The learner’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 as possible—and 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. A non-exhaustive list
∗Equal contribution authors.
35th Conference on Neural Information Processing Systems (NeurIPS 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 [FS97] 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 semi-adversarial paradigm, which defines a spectrum of constraints on the permissible data distributions between stochastic and adversarial. The concept of -quantile regret was introduced by Chaudhuri, Freund, and Hsu [CFH09], in which the player competes against the b Nc 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 √ (T + (logN)2)(1 + log(1/ )).
Later algorithms improved it to √ T (1 + log(1/ )) [CV10; OP16], removing the dependency on N . The semi-adversarial paradigm considers constraining the adversary’s choice of data distributions, which was first motivated by Rakhlin, Sridharan, and Tewari [RST11]. 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-the-regularized-leader (FTRL) algorithm with new root-logarithmic 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 so without using the additive normalization step of previous algorithms [CL06, Section 2.1]. We achieve root-KL 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-adversarial paradigm, we improve the dependence on the number of experts in the regret bound, obtaining uniformly improved upper bounds over previous work.
We achieve the above results through a novel local-norm analysis of FTRL with linearly decomposable regularizers on general (possibly uncountable) expert spaces. We use this analysis in conjunction with basic conditions on the first and second derivatives to design and analyze the root-logarithmic regularizers. We believe that this approach is fundamentally different from existing ones and could lead to further advances in obtaining optimal algorithms. In fact, there exist results stating if a 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, Thm 9]). However, it is not clear how to design such a function in practice. In contrast, our general FTRL bound reduces the choice of regularizer to a 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] first discussed the fact that the -quantile regret corresponds to the KL divergence between a uniform prior and the uniform mixture of the top b Nc competitors, and such KL bounds have consequently quickly followed quantile regret bounds. Luo and Schapire [LS14; LS15] provided a variant of NormalHedge along with a data-dependent KL regret bound at the cost of an additional log T 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 a reduction to optimal 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 to 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 χ2-divergence) 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 Kotłowski [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 full-information setting [LWZ18].
The best known asymptotic lower bound for learning with expert advice is by Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire, and Warmuth [C+97], while a finite-time lower bound that asymptotically 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 a lower bound on the regret of learning with two experts based on the KL divergence against some prior.

heading: 2 Notation
text: 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 simultaneously. Let (Θ,Σ) be a measurable space, M∞(Θ,Σ) and M(Θ,Σ) denote the collection of finite and probability measures respectively, and ν ∈ M∞(Θ,Σ) be arbitrary. A measure q ∈ M∞(Θ,Σ) is absolutely continuous with respect to ν (denoted q ν) if q(A) = 0 for all A ∈ Σ such that ν(A) = 0. LetMν(Θ,Σ) = {q ∈ M(Θ,Σ) : q ν} be the set of probability measures that are absolutely continuous with respect to ν. For any integer N , let [N ] = {1, . . . , N}, and simp([N ]) = {p ∈ [0, 1]N : ∑N i=1 pi = 1}. Let R+ = [0,∞) and R++ = (0,∞), and define M ≡M((Θ,Σ), (R,R)) to be the space of measurable functions from (Θ,Σ) to (R,R), whereR is the Borel σ-field on R. Define sets of bounded measurable functions
L∞ = {` ∈M : sup θ∈Θ |`(θ)|<∞} and L∞[0,1] = {` ∈M : 0 ≤ ` ≤ 1},
sets of integrable functions L1(ν) = {x ∈M : ∫ |x(θ)| ν(dθ) <∞} and L1+(ν) = {x ∈ L1(ν) : x ≥ 0},
and the set of Radon–Nikodym derivatives (w.r.t. ν) of probability measures X (ν) = {x ∈ L1+(ν) : ∫ x(θ)ν(dθ) = 1}.
For every x ∈ X (ν), let ν(x) ∈ Mν(Θ,Σ) denote the unique probability measure satisfying dν(x)/dν = x. For every x, z ∈ L∞, let Conv(x, z) = {αx + (1− α)z : α ∈ [0, 1]} denote their convex hull. For every ` ∈ L∞ and x ∈ L1(ν), define
〈`, x〉ν = ∫ `(θ)x(θ)ν(dθ).
Prediction with expert advice We consider the following setting of online linear optimization. For each round t ∈ [T ], the player selects µt ∈ M(Θ,Σ) based only upon information available prior to round t, and then observes `t ∈ L∞. Performance is measured using the regret against some probability measure q ∈M(Θ,Σ), which is defined by
RT (q) = T∑ t=1 Eθ∼µt [`t(θ)]− T∑ t=1 Eθ∼q [`t(θ)] .
The player’s goal is to select µt so that the cumulative loss is not much larger than that of the average loss of an expert under q, and consequently to have small regret.
The elements of Θ can be regarded as experts for some prediction problem, and the learner aggregates the predictions of the experts by selecting an expert at random according to µt at round t. For concreteness, note that the usual prediction with expert advice setting for N experts corresponds to M(Θ,Σ) = simp([N ]). 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.
Follow-the-regularized-leader Let R = R ∪ {+∞}. Follow-the-regularized-leader (FTRL) [S07; AHR08; HK10] forms a broad class of algorithms for online convex optimization. For a finite measure ν ∈M∞(Θ,Σ) and a sequence of regularizers (ψt : X (ν)→ R )t∈[T ], (ψt)t∈[T ]-regularized FTRL is defined by selecting µt+1 = ν(xt+1) using
xt+1 ∈ arg min x∈X (ν) {〈Lt, x〉ν + ψt+1(x)}, (1)
where L0 = 0 and Lt = ∑t s=1 `s.
As mentioned above, a classical algorithm for prediction with expert advice on a finite class of N experts is Hedge. While originally analyzed using potential functions, Hedge also corresponds to FTRL where ν is the counting measure and ψt(·) = −η−1t H(·) for the Shannon entropy H(x) =∑ i∈[N ] x(i) log(1/x(i)) with any sequence of regularizer scalings (ηt)t∈N ⊆ R++.
Depending on whether the space is continuous or discrete, the range of elements of X (ν) will change, and consequently also the minimal domain on which regularizers must be defined. Let ν = inf {ν(A) : A ∈ Σ, ν(A) > 0}, and let S(ν) = [0, 1/ν] if ν > 0 and R+ otherwise. By definition, ν({θ ∈ Θ : x(θ) ∈ S(ν)}) = 1 for all x ∈ X (ν). Concretely, when ν is counting measure then S(ν) = [0, 1], when ν is uniform on [N ] then S(ν) = [0, N ], and when ν is a continuous distribution then S(ν) = R+. In this work, we consider linearly decomposable regularizers of the form ψt(x) = η−1t Ψ ν f (x), where
Ψνf (x) =
∫ f(x(θ))ν(dθ) (2)
for some f : S(ν)→ R. We refer to the algorithm that selects µt+1 using Eq. (1) with a regularizer of the form in Eq. (2) as Ψνf -regularized FTRL with regularizer scaling ηt.

heading: 3 Applications of FTRL with linearly decomposable regularizers
text: In Section 5, we provide a general analysis of FTRL with linearly decomposable regularizers for arbitrary f . First, we motivate such a 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 ν ∈M(Θ,Σ) and f : R+ → R satisfies:
1. f(1) = 0; 2. f is twice continuously differentiable, f ′′ > 0 on R++, and f ′′(0+) > 0; 3. either f or 1/f ′′ is increasing on R++; 4. there exist c1, c2 > 0 such that f ′′ · (f + c1) ≥ c2.
For any sequence (`t)t∈N ⊆ L∞[0,1], q ∈Mν(Θ,Σ), and T , Ψ ν f -regularized FTRL with regularizer scaling ηt = √ c2/t achieves
RT (q) ≤ √
T+1 c2 Ψνf (dq/dν) + c1√ c2
√ T .
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, in addition to the assumptions of Corollary 1, there exist k1 ∈ R and k2 ∈ R+ with f(x) ≤ k1 + k2x √ log(1 + x), then
RT (q) ≤ √
T+1 c2
( k1 + k2 √ 1 + KL (q ‖ π) ) + c1√c2 √ T .
Under different conditions on f , we also derive variance bounds with respect to the (intermediate) predictive distributions, similar to AdaHedge [v+11] and AdaFTRL [OP15b], or with respect to a “prior”, as in [A21]. We state the conditions on the regularizer and the corresponding regret bounds in the following corollary. Corollary 3. Suppose ν ∈M∞(Θ,Σ) and f : S(ν)→ R satisfies:
1. f(1/ν(Θ)) ≥ 0; 2. f is twice continuously differentiable, f ′′ > 0 on interior(S(ν)), and f ′′(0+) > 0.
For any sequence (`t)t∈N ⊆ L∞[0,1], q ∈Mν(Θ,Σ), and T , Ψ ν f -regularized FTRL achieves 1. If 1/f ′′(x) ≤ Cx, ηt+1 = (C[1/2 + ∑t−1 s=1 Varθ∼ν(ẑs+1) `s(θ)]) −1/2 gives
RT (q) ≤ [Ψνf (dq/dν) + 1] √ C[1/2 + ∑T t=1 Varθ∼ν(ẑt+1) `t(θ)].
2. If 1/f ′′ ≤ C, ηt+1 = (C ν(Θ)[1/4 + ∑t s=1 Varθ∼ν `s(θ)]) −1/2 for ν = ν/ν(Θ) gives
RT (q) ≤ [Ψνf (dq/dν) + 1] √ C ν(Θ)[1/4 + ∑T t=1 Varθ∼ν `t(θ)].

heading: 3.1 Examples of f -divergence FTRL
text: We now apply all three of these corollaries to more concrete choices of f . Note that in the setting of Corollary 1, since ν is a probability distribution and f is convex with f(1) = 0, the regularizer corresponds to an f -divergence, which we denote by Ψνf (dq/dν) = Df (q‖ ν) for any q ∈ Mν(Θ,Σ). In this case, we call ν a prior and refer to 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 root-logarithmic 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 1 in 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) = x log x, which satisfies Df ( ·‖π) = KL (· ‖ π) for any π ∈M(Θ,Σ). This choice satisfies the assumptions of Corollary 1 with c1 = 1 + 1/e and c2 = 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 3 with C = 1 to obtain
RT (q) ≤ [ KL (q ‖ ν) + 1 ]√ 1/2 + ∑T t=1 Varθ∼ν(ẑt+1) `t(θ).
Further, by Lemma 1, f -divergence FTRL with regularizer scaling ηt+1 recovers the familiar formula
xt+1(θ) = exp(−ηt+1Lt(θ))∫
exp(−ηt+1Lt(ϑ))ν(dϑ) . /
Example 2 (χ2-divergence). 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 χ2-divergence, corresponding to f(x) = x2 − 1. This f clearly satisfies the conditions of Corollary 1 with c1 = c2 = 2, so we match the optimized bound of Alquier [A21, Corollary 2.4] with
RT (q) ≤ √ T χ2(q ‖ ν) + √ 2T .
Further, the conditions of Corollary 3 are satisfied with C = 1/2, so we obtain the novel, potentially much smaller variance bound (without requiring advance knowledge of the variances)
RT (q) ≤ 1√2 [ χ2(q ‖ ν) + 1 ]√ 1/4 + ∑T t=1 Varθ∼ν `t(θ) .
By Lemma 1, the χ2-divergence FTRL solution with regularizer scaling ηt+1 is
xt+1(θ) = 1 2 ( k∗t+1 − ηt+1Lt(θ) ) +
where k∗t+1 ∈ R solves ∫ [ 12 (k ∗ t+1 − ηt+1Lt(θ))+]ν(dθ) = 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 Corollary 2 abNormal. One such example is f(x) = ∫ x 1 √ 2 log(1 + s) ds, which satisfies the conditions
of Corollary 1 with c1 = 2 and c2 = 1/ √
2 since f is increasing, and satisfies the conditions of Corollary 2 with k1 = 0 and k2 = √ 2. Thus, we obtain
RT (q) ≤ 2 √ (T + 1)(1 + KL (q ‖ ν)) + √ 8T .
The f -divergence FTRL solution with regularizer scaling ηt+1 is given by xt+1(θ) = exp {( k∗t+1 − ηt+1Lt(θ) )2 + /2 } − 1,
where k∗t+1 ∈ R solves ∫ [exp{ ( k∗t+1 − ηt+1Lt(θ) )2 + /2} − 1]ν(dθ) = 1. Note that this formula is heuristically similar to NormalHedge when |Θ| = N , which assigns weights to experts according to
wt(i) ∝ [∑t−1s=1 〈`s, ws〉 − Lt−1(i)]+ exp ( [ ∑t−1 s=1 〈`s, ws〉 − Lt−1(i)] 2 + /2ct−1 ) ,
where ct−1 solves ∑ i∈[N ] exp([ ∑t−1 s=1 〈`s, ws〉 − Lt−1(i)] 2 + /2ct−1) = eN . /

heading: 3.2 Lower bound for quantile regret
text: Bounds for quantile regret and KL regret can be related by observing a) that for δ(i ) denoting a point-mass on the i th best expert with respect to LT ,
RT (δ(i )) ≤ RT (u ),
where = i /N and u = 1i ∑i j=1 δ(j) is the uniform distribution over the top i experts, and b) that KL (u ‖ Unif([N ])) = log(1/ ). Thus, KL upper bounds are also upper bounds on quantile regret and quantile regret lower bounds are also lower bounds on certain KL regrets. With this in mind, we provide the first general lower bound for quantile regret on N experts. Our lower bound is matching (up to lower order terms) the leading term in our upper bound for quantile regret achieved by abNormal (Example 3) when ν is uniform on [N ] and q is uniform on only the top quantile of experts, establishing the minimax rate of quantile regret as √ T log(1/ ).
Theorem 1. For all N ∈ N there exists a probability distribution p on [0, 1]N such that for any sequence of player predictions (wt)t∈N ⊆ simp([N ]), i ∈ {1, . . . , bN/4c}, and T ∈ N,
E`1:T∼p⊗TRT (δ(i )) ≥ √ (T/2) (log(1/ )− 2 log 2 + 1/π)− √ 2/π − 2 logN − log 2,
where δ(i ) is the point-mass on the i th best expert with respect to LT and = i /N .

heading: 3.3 Intuition for f -divergence FTRL in the KL regret paradigm
text: 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 -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 inequality to imply Df ( ·‖ ·) . √ KL (· ‖ ·). That it is possible to satisfy both of these conditions simultaneously is the crucial observation that enables our result. All regularizers to which both Corollaries 1 and 2 apply are essentially equivalent to f(x) =∫ x 1 √ 2 log(1 + s)ds, meaning they have the same asymptotic growth rate. To see this, first observe that this f has the minimum amount of curvature needed to satisfy f ′′ · (f + c1) ≥ c2 since (x √ log x) · (x √
log x)′′ is asymptotically constant. Second, this f has the largest asymptotic growth rate that still satisfies f(x) ≤ k1 + k2x √ log(1 + x). These two facts together constrain the shape of f to the root-logarithmic choice.

heading: 4 Semi-adversarial regret bounds
text: We now turn to a another perspective on prediction with expert advice for which FTRL with linearly decomposable regularizers is optimal. The semi-adversarial paradigm (introduced by [BNR20]) consists of a family of constraints on the adversary’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 an unknown time-homogeneous convex constraint on the adversary’s choice of loss distribution, which is formally represented by a convex set of probability distributions on L∞[0,1], denoted byD. At each round t, the adversary is free to select any distribution from D to sample `t from. Note that when D is the set of all probability distributions, the worst-case adversarial setting is recovered, and when D is a singleton, the stochastic setting is recovered. In this section, we describe a new FTRL algorithm (FTRL-CARL) that achieves minimax optimal expected regret without requiring knowledge of D in advance.

heading: 4.1 Adaptive minimax optimality
text: Minimax regret in the semi-adversarial paradigm is quantified using a few key objects that summarize D. The first is the collection of effective stochastic gaps, defined for each expert i ∈ [N ] by
∆i = inf p∈D max i′∈[N ]
E`∼p [`(i)− `(i′)] .
Using these, Bilodeau, Negrea, and Roy [BNR20] define the stochastic gap
∆0 = min {∆i : i ∈ [N ] ,∆i > 0} .
The second object Bilodeau, Negrea, and Roy [BNR20] define is the set of effective experts, which is a subset of [N ] defined by I0 = {i ∈ [N ] : ∆i = 0} . 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 N0 = |I0|. In this paradigm, the goal is to compete against the best expert. Letting δi denote a point-mass on expert i, for notational simplicity we set RT ≡ maxi∈[N ]RT (δi). 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 D in advance. To characterize this, we say an algorithm (which only has knowledge of N in advance) is adaptively minimax optimal if there exists a constant C such that, for all N and (N0,∆0) pairs, the expected regret of the algorithm is within a factor of C from the minimax regret had the algorithm had access to (N0,∆0) in advance, for sufficiently large T (where sufficiently large may depend on N , N0, and ∆0). For a precise mathematical formulation of this concept, see Section 3.1 of Bilodeau, Negrea, and Roy [BNR20].
When N0 = 1, Proposition 4 of Mourtada and Gaïffas [MG19] shows that the minimax regret is of order no smaller than (logN)/∆0, and when N0 > 1, Theorem 2 of Bilodeau, Negrea, and Roy [BNR20] shows that the minimax regret is of order no smaller than √ T logN0. Bilodeau, Negrea, and Roy [BNR20] prove that Hedge is not adaptively minimax optimal in the semi-adversarial paradigm, and their argument applies to other similar Hedge-based algorithms, such as prod [CMS07], AdaHedge [v+11], and Adapt-ML-Prod [GSv14]. Further, they provide an algorithm that achieves
ERT . √ T logN0 + I[N0 = 1] logN
∆0 + I[N0 > 1]
(logN)3/2
∆0 . (3)
Since I[N0 > 1](logN)3/2∆−10 is lower order when N0 > 1, this algorithm is adaptively minimax optimal. We now present a new algorithm, FTRL-CARL, which is also adaptively minimax optimal and achieves a better regret bound for small T .

heading: 4.2 Semi-adversarial regret bound for FTRL-CARL
text: Let hC : [0, 1]→ R be given by
hC(x) =
{ x √ 2 log(1/x)− √
π 2 erf
(√ log(1/x) ) + x(N − 1) √ π 2 x ∈ (0, 1]
− √ π/2 x = 0,
set HC(w) = ∑ i∈[N ] hC(w(i)), and define FTRL-CARL to be FTRL with ν defined as counting measure, regularizer Ψν−hC (w) = −HC(w), and regularizer scaling ηt = 2/ √ t. Note that this corresponds to FTRL with a linearly decomposable regularizer, and an intuitive explanation for this choice of regularizer can be found in Subsection 4.3. We then have the following regret bound for FTRL-CARL, which removes the term I[N0 > 1](logN)3/2∆−10 from Eq. (3). Corollary 4. For any time-homogeneous convex constraint D, FTRL-CARL achieves: For all T ,
ERT ≤ √ 2T logN,
and if T > 8(logN0)∆−20 ,
ERT ≤ √ 2T logN0 + 25 logN
∆0 .
Corollary 4 follows from Theorem 3 in Appendix D, which is a more refined regret bound.

heading: 4.3 Intuition for FTRL-CARL in the semi-adversarial paradigm
text: 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
ηt & √
(logN)/t, and matching lower bounds for the adversarial setting suggest this regularizer scaling constraint is actually necessary for optimal performance. Such a 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 ηt & √ (logN0)/t. This smaller regularizer scaling applied to the effective experts is necessary to incur asymptotically√ T logN0 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, it would be ideal to have expert-specific regularizer scalings of size√ (logN0)/t for the effective experts and √ (logN)/t for the ineffective experts. Since the effective experts will have weights on the order of 1/N0 and the ineffective experts will have weights smaller than 1/N , the expert-specific regularizer scaling ηt(i) = c √ log(1/wt(i))/t may plausibly achieve the desired behaviour.
The weights of Hedge are defined by the equation log(1/wt(i)) = ηt(Lt−1(i) + λt), where λt is chosen to ensure the weights are normalized. Replacing ηt with our heuristic yields log(1/wt(i)) = c √
log(1/wt(i))/t (Lt−1(i) + λt), which can be rearranged to obtain√ log(1/wt(i)) =
c√ t (Lt−1(i) + λt).
By Lemma 1, this is exactly the formula for the weights produced with FTRL for the regularizer −HC and regularizer scaling ηt = c/ √ t.
As Theorem 3 shows, our modification to the Hedge algorithm is sufficient to yield semi-adversarial regret bounds with expected regret contribution of size (logN)/∆0 from the ineffective experts, improving on the order of the regret bound for FTRL-CARE when N0 > 1.

heading: 5 FTRL analysis for general expert spaces
text: Finally, we analyze the general performance of FTRL with a linearly decomposable regularizer. First, Lemma 1 provides a closed-form expression for the FTRL solution on general spaces. Specifically, it 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. It 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-KL 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 ν ∈M∞(Θ,Σ) be fixed and arbitrary.

heading: 5.1 Computing FTRL with linearly decomposable regularizers
text: For continuously differentiable f : S(ν)→ R, let mf ′ = infx∈S(ν) f ′(x), Mf ′ = supx∈S(ν) f ′(x), and τf ′(y) = max(min(y,Mf ′),mf ′). We focus on the setting where f ′ is strictly increasing, and thus τf ′(y) truncates its argument to the domain of [f ′]−1. Lemma 1. Suppose f : S(ν) → R is twice continuously differentiable with f ′′ > 0 on interior(S(ν)) and f ′′(0+) > 0. For any L ∈ L∞ and η > 0,
x∗(θ) = [f ′]−1(τf ′(−ηL(θ) + k∗))
satisfies x∗ ∈ arg minx∈X (ν){〈L, x〉ν + η−1Ψνf (x)}, where k∗ ∈ R solves∫ [f ′]−1 (τf ′(−ηL(θ) + k∗)) ν(dθ) = 1. (4)
Further, this solution is unique up to modification on a set of ν-measure 0.
For finite expert classes, solving the normalizing equation provided by Lemma 1 to a given precision is essentially the same difficulty as normalizing the weights for the classical Hedge algorithm. For
example, for FTRL-CARL the range of the normalizing constant scales with logN , and solving this using the bisection method would require only O(log logN) 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 a finite N . In this setting, solving the FTRL normalizing equation is 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 an interesting question for future work.

heading: 5.2 Choosing f to obtain specific regret bounds
text: In order to state our generic decomposition for the regret of FTRL algorithms on abstract spaces, we rely on the definition of the one-dimensional Bregman divergence, which is defined for any continuously differentiable, strictly convex f : R→ R by
Bf (x; y) = f(x)− f(y)− f ′(y)(x− y).
Theorem 2. Suppose f : S(ν) → R is twice continuously differentiable with f ′′ > 0 on interior(S(ν)) and f ′′(0+) > 0. For all sequences (`t)t∈N ⊆ L∞ and (mt)t∈N ⊆ R, there exist ẑt+1 ∈ Conv(xt, xt+1) and z̃t+1 ∈ Conv(xt, x̃t+1) such that for all q ∈ Mν(Θ,Σ), (zt+1)t∈N ∈ {(ẑt+1)t∈N, (z̃t+1)t∈N}, and T , Ψνf -regularized FTRL achieves
RT (q) ≤ 1
ηT+1 Ψνf
( dq
dν ) − 1 η1 min x∈X (ν) Ψνf (x)
+ T∑ t=1 [∫ ηt 2 (`t(θ)−mt)2 f ′′(zt+1(θ)) ν(dθ)− ( 1 ηt+1 − 1 ηt ) Ψνf (xt+1) ] ,
(5)
where
x̃t+1 ∈ arg min x∈L1+(ν)
{ 〈`t −mt1, x〉ν + 1
ηt
∫ Bf (x(θ);xt(θ))ν(dθ) } .
Further, if infθ∈Θ `t(θ) ≥ mt, then z̃t+1 ≤ xt pointwise.
Theorem 2 is a general result that can be used to prove regret bounds for a variety of settings under the general FTRL framework we describe, as we have already done in Sections 3 and 4. Furthermore, we highlight that the functional form of Theorem 2 makes it clear how to select the regularizers for both the quantile regret and semi-adversarial paradigms. Specifically, in the former, the terms in summation in Eq. (5) are balanced to cancel, while in 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 · f ′′ = ±1. (6)
Since the generic bound we obtain in Theorem 2 yields components based upon integrals of both f and 1/f ′′, balancing these terms without free tuning parameters requires Eq. (6) to approximately hold. Heuristically, trying to balance these terms with tuning parameters rather than by the choice of f seems to lead to non-adaptive or non-uniform bounds. Hedge provides an 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 a 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.

heading: 5.3 Applications of root-KL regret bounds for continuous experts
text: 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 to measure regret against is the posterior distribution π̂T 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 π̂T plus an excess regret of the order √ T KL (π̂T ‖ π). This excess loss is smaller than T + KL (π̂T ‖ π), which is the best available bound for excess loss when predicting according to the posterior π̂t at each round t ∈ [T ], and smaller than √ T KL (π̂T ‖ π), 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 (π̂T ‖ π). These worse excess loss bounds follow from the analysis contained in Zhang [Z06], although he only compares against the “true” data-generating parameter.
Model selection using f -divergence FTRL Extending the interpretation of Orabona and Pál [OP16] by Foster, Krishnamurthy, and Luo [FKL20] to countable union model classes, we can consider an infinite sequence of disjoint finite expert classes (note any nested sequence can be made disjoint), Θ1,Θ2, . . . , and let Θ = ⋃ m≥1 Θm. Assigning to Θ the prior π(θ) ∝ 1 m2|Θm| for each θ ∈ Θm, we recover the following regret bound for f -divergence FTRL with regularizer scaling ηt ∝ 1/ √ t from Corollary 2:
RT (δθ) ≤ O (√ T (log |Θm|+ logm) ) for all θ ∈ Θm and all m ∈ N.

heading: 6 Limitations
text: 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; MVZ21], although it remains a 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]. It is at least as costly as finding the normalizing constant for a 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(x), one evaluation of that equation is sufficient, but in general finding the root of Eq. (4) to a fixed precision will take a number of evaluations depending on the desired precision and the range of possible values, and so FTRL with a 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 a general f , and that line of inquiry may lead to novel, efficient, and high-performance learning algorithms.
A final limitation is that we do not obtain variance bounds together with uniform root-KL bounds, although our approach leads to both separately (Corollary 3 and Corollary 2), so we are optimistic our 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 a stipend provided by the Charles Simonyi Endowment. We thank Mufan Li and Mahdi Haghifam for helpful feedback on early drafts.

Review summaries:
This paper considers the problem of prediction with expert advice, and focuses on quantile regret bounds that depend on the comparator distribution and semi-adversarial paradigm, which is an intermediate setting between stochastic one and adversarial one. In the paper, minimax optimal regret bounds for both paradigms are shown. This bound is achieved by follow-the-regularized-leader (FTRL) algorithm with a newly designed root-logarithmic regularizers.

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.

The paper studies Follow the Regularised Leader algorithms for the Hedge settings.  The 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.  Then 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).  The paper presents FTRL-CARL and obtains a performance bound on it in terms of effective stochastic gaps.  Then the paper discusses bounds in terms of f-divergence and obtains a lower bound matching upper bounds.

This paper studies the classic expert problem and focuses on developing  parameter-free algorithms with two specific guarantees: 1) better regret  bounds for the semi-adversarial paradigm proposed by Bilodeau et al. 20;  2) a KL-type regret bound similar to that achieved by NormalHedge  (Chaudhuri et al. 09) and other variants, possibly for an uncountable  set of experts. The authors achieve these two goals using the standard  FTRL framework with two new root-logarithmic regularizers, inspired by  their general analysis that requires some specific properties of the  regularizer. A matching lower bound for the KL-type regret is also  provided.