Steven De Rooij
email: steven.de.rooij@gmail.com

Tim Van Erven

Peter D Grünwald

Wouter M Koolen
email: wmkoolen@cwi.nl

Follow the Leader If You Can, Hedge If You Must

Keywords: Hedge, Learning Rate, Mixability, Online Learning, Prediction with Expert Advice

, yielding improved worst-case guarantees. By interleaving AdaHedge and FTL, FlipFlop achieves regret within a constant factor of the FTL regret, without sacrificing AdaHedge's worst-case guarantees. AdaHedge and FlipFlop do not need to know the range of the losses in advance; moreover, unlike earlier methods, both have the intuitive property that the issued weights are invariant under rescaling and translation of the losses. The losses are also allowed to be negative, in which case they may be interpreted as gains.

Introduction

We consider sequential prediction in the general framework of Decision Theoretic Online Learning (DTOL) or the Hedge setting [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF], which is a variant of prediction with expert advice [START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Vovk | A game of prediction with expert advice[END_REF][START_REF] Cesa | Prediction, learning, and games[END_REF]. Our goal is to develop a sequential prediction algorithm that performs well not only on adversarial data, which is the scenario most studies worry about, but also when the data are easy, as is often the case in practice. Specifically, with adversarial data, the worst-case regret (defined below) for any algorithm is Ω( √ T ), where T is the number of predictions to be made. Algorithms such as Hedge, which have been designed to achieve this lower bound, typically continue to suffer regret of order √ T , even for easy data, where c 2013 Steven de Rooij, Tim van Erven, Peter D. Grünwald and Wouter M. Koolen.

the regret of the more intuitive but less robust Follow-the-Leader (FTL) algorithm (also defined below) is bounded. Here, we present the first algorithm which, up to constant factors, provably achieves both the regret lower bound in the worst case, and a regret not exceeding that of FTL. Below, we first describe the Hedge setting. Then we introduce FTL, discuss sophisticated versions of Hedge from the literature, and give an overview of the results and contents of this paper.

Overview

In the Hedge setting, prediction proceeds in rounds. At the start of each round t = 1, 2, . . ., a learner has to decide on a weight vector w t = (w t,1 , . . . , w t,K ) ∈ R K over K "experts". Each weight w t,k is required to be nonnegative, and the sum of the weights should be 1. Nature then reveals a K-dimensional vector containing the losses of the experts ℓ t = (ℓ t,1 , . . . , ℓ t,K ) ∈ R K . Learner's loss is the dot product h t = w t • ℓ t , which can be interpreted as the expected loss if Learner uses a mixed strategy and chooses expert k with probability w t,k . We denote aggregates of per-trial quantities by their capital letter, and vectors are in bold face. Thus, L t,k = ℓ 1,k + . . . + ℓ t,k denotes the cumulative loss of expert k after t rounds, and H t = h 1 + . . . + h t is Learner's cumulative loss (the Hedge loss).

Learner's performance is evaluated in terms of her regret, which is the difference between her cumulative loss and the cumulative loss of the best expert:

R t = H t -L * t ,
where

L * t = min k L t,k .
We will always analyse the regret after an arbitrary number of rounds T . We will omit the subscript T for aggregate quantities such as L * T or R T wherever this does not cause confusion.

A simple and intuitive strategy for the Hedge setting is Follow-the-Leader (FTL), which puts all weight on the expert(s) with the smallest loss so far. More precisely, we will define the weights w t for FTL to be uniform on the set of leaders {k | L t-1,k = L * t-1 }, which is often just a singleton. FTL works very well in many circumstances, for example in stochastic scenarios where the losses are independent and identically distributed (i.i.d.). In particular, the regret for Follow-the-Leader is bounded by the number of times the leader is overtaken by another expert (Lemma 10), which in the i.i.d. case almost surely happens only a finite number of times (by the uniform law of large numbers), provided the mean loss of the best expert is smaller than the mean loss of the other experts. As demonstrated by the experiments in Section 5, many more sophisticated algorithms can perform significantly worse than FTL.

The problem with FTL is that it breaks down badly when the data are antagonistic. For example, if one out of two experts incurs losses 1 2 , 0, 1, 0, . . . while the other incurs opposite losses 0, 1, 0, 1, . . ., the regret for FTL at time T is about T /2 (this scenario is further discussed in Section 5.1). This has prompted the development of a multitude of alternative algorithms that provide better worst-case regret guarantees.

The seminal strategy for the learner is called Hedge (Freund andSchapire, 1997, 1999). Its performance crucially depends on a parameter η called the learning rate. Hedge can be interpreted as a generalisation of FTL, which is recovered in the limit for η → ∞. In many analyses, the learning rate is changed from infinity to a lower value that optimizes some upper bound on the regret. Doing so requires precognition of the number of rounds of the game, or of some property of the data such as the eventual loss of the best expert L * . Provided that the relevant statistic is monotonically nondecreasing in t (such as L * t ), a simple way to address this issue is the so-called doubling trick: setting a budget on the statistic, and restarting the algorithm with a double budget when the budget is depleted [START_REF] Cesa | Prediction, learning, and games[END_REF][START_REF] Cesa-Bianchi | How to use expert advice[END_REF][START_REF] Hazan | Extracting certainty from uncertainty: Regret bounded by variation in costs[END_REF]; η can then be optimised for each individual block in terms of the budget. Better bounds, but harder analyses, are typically obtained if the learning rate is adjusted each round based on previous observations, see e.g. [START_REF] Cesa | Prediction, learning, and games[END_REF][START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF].

The Hedge strategy presented by [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF] is a sophisticated example of such adaptive tuning. The relevant algorithm, which we refer to as CBMS, is defined in ( 16) in Section 4.2 of their paper. To discuss its guarantees, we need the following notation. Let ℓ - t = min k ℓ t,k and ℓ + t = max k ℓ t,k denote the smallest and largest loss in round t, and let L - t = ℓ - 1 + . . . + ℓ - t and L + t = ℓ + 1 + . . . + ℓ + t denote the cumulative minimum and maximum loss respectively. Further let s t = ℓ + tℓ - t denote the loss range in trial t and let S t = max{s 1 , . . . , s t } denote the largest loss range after t trials. Then, without prior knowledge of any property of the data, including T , S and L * , the CBMS strategy achieves regret bounded by 1 R CBMS ≤ 4 (L * -L -)(L -+ ST -L * ) T ln K + lower order terms (1) (Cesa-Bianchi et al., 2007, Corollary 3). Hence, in the worst case L * = L -+ ST /2 and the bound is of order S √ T , but when the loss of the best expert L * ∈ [L -, L -+ ST ] is close to either boundary the guarantees are much stronger.

The contributions of this work are twofold: first, in Section 2, we develop AdaHedge, which is a refinement of the CBMS strategy. A (very) preliminary version of this strategy was presented at NIPS [START_REF] Van Erven | Adaptive hedge[END_REF]. Like CMBS, AdaHedge is completely parameterless and tunes the learning rate in terms of a direct measure of past performance. We derive an improved worst-case bound of the following form. Again without any assumptions, we have

R ah ≤ 2 S (L * -L -)(L + -L * ) L + -L - ln K + lower order terms (2)
(see Theorem 8). The parabola under the square root is always smaller than or equal to its CMBS counterpart (since

L + ≤ L -+ ST ); it expresses that the regret is small if L * ∈ [L -, L +
] is close to either boundary. It is maximized in L * at the mid-point between L -and L + , and in this case we recover the worst-case bound of order S √ T . Like (1), the regret bound (2) is "fundamental", which means that it is invariant under translation of the losses and proportional to their scale. Moreover, not only AdaHedge's regret bound is fundamental: the weights issued by the algorithm are themselves invariant under translation and scaling (see Section 4). The CBMS algorithm and AdaHedge are insensitive to trials in which all experts suffer the same loss, a natural property we call "timelessness". An attractive feature of the new bound (2) is that it expresses this property. A more detailed discussion appears below Theorem 8.

Our second contribution is to develop a second algorithm, called FlipFlop, that retains the worst-case bound (2) (up to a constant factor), but has even better guarantees for easy data: its performance is never substantially worse than that of Follow-the-Leader. At first glance, this may seem trivial to accomplish: simply take both FTL and AdaHedge, and combine the two by using FTL or Hedge recursively. To see why such approaches do not work, suppose that FTL achieves regret R ftl , while AdaHedge achieves regret R ah . We would only be able to prove that the regret of the combined strategy compared to the best original expert satisfies R c ≤ min{R ftl , R ah } + G c , where G c is the worst-case regret guarantee for the combination method, e.g. ( 1). In general, either R ftl or R ah may be close to zero, while at the same time the regret of the combination method, or at least its bound G c , is proportional to √ T . That is, the overhead of the combination method will dominate the regret!

The FlipFlop approach we describe in Section 3 circumvents this by alternating between Following the Leader and using AdaHedge in a carefully specified way. For this strategy we can guarantee

R ff = O(min{R ftl , G ah }),
where G ah is the regret guarantee for AdaHedge; Theorem 15 provides a precise statement. Thus, FlipFlop is the first algorithm that provably combines the benefits of Follow-the-Leader with robust behaviour for antagonistic data.

A key concept in the design and analysis of our algorithms is what we call the mixability gap, introduced in Section 2.1. This quantity also appears in earlier works, and seems to be of fundamental importance in both the current Hedge setting as well as in stochastic settings. We elaborate on this in Section 6.2 where we provide the big picture underlying this research and we briefly indicate how it relates to practical work such as [START_REF] Devaine | Forecasting electricity consumption by aggregating specialized experts; a review of the sequential aggregation of specialized experts, with an application to Slovakian and French country-wide one-dayahead (half-)hourly predictions[END_REF].

Related Work

As mentioned, AdaHedge is a refinement of the strategy analysed by [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF], which is itself more sophisticated than most earlier approaches, with two notable exceptions. First, [START_REF] Chaudhuri | A parameter-free hedging algorithm[END_REF] describe a strategy called NormalHedge that can efficiently compete with the best ǫ-quantile of experts; their bound is incomparable with the bounds for CBMS and for AdaHedge. Second, by modifying the weights, and tuning the learning rate in terms of the cumulative empirical variance of the losses of the best expert, [START_REF] Hazan | Extracting certainty from uncertainty: Regret bounded by variation in costs[END_REF] are able to obtain a bound that dominates our worstcase result (2) (up to a multiplicative constant). As demonstrated by the experiments in Section 5, their method does not achieve the benefits of FTL, however. In Section 5 we also discuss the performance of NormalHedge and the algorithm by Hazan and Kale compared to AdaHedge and FlipFlop.

Other Approaches Other approaches to sequential prediction include defensive forecasting [START_REF] Vovk | Defensive forecasting[END_REF], and Following the Perturbed Leader [START_REF] Kalai | Efficient algorithms for online decision[END_REF].

These radically different approaches also allow competing with the best ǫ-quantile, see [START_REF] Alexey | Prediction with advice of unknown number of experts[END_REF] and [START_REF] Hutter | Adaptive online prediction by following the perturbed leader[END_REF]; the latter article also considers nonuniform weights on the experts.

The "safe MDL" and "safe Bayesian" algorithms by [START_REF] Grünwald | Safe learning: bridging the gap between Bayes, MDL and statistical learning theory via empirical convexity[END_REF][START_REF] Grünwald | The safe Bayesian: learning the learning rate via the mixability gap[END_REF] share the present work's focus on the mixability gap as a crucial part of the analysis, but are concerned with the stochastic setting where losses are not adversarial but i.i.d. FlipFlop, safe MDL and safe Bayes can all be interpreted as methods that attempt to choose a learning rate η that keeps the mixability gap small (or, equivalently, that keeps the Bayesian posterior or Hedge weights "concentrated").

Outline

In the next section we present and analyse AdaHedge and compare its worst-case regret bound to existing results, in particular the bound for CBMS. Then, in Section 3, we build on AdaHedge to develop the FlipFlop strategy. The analysis closely parallels that of AdaHedge, but with extra complications at each of the steps. In Section 4 we show that both algorithms have the property that their behaviour does not change under translation and scaling of the losses. We further illustrate the relationship between the learning rate and the regret, and compare AdaHedge and FlipFlop to existing methods, in experiments with artificial data in Section 5. Finally, Section 6 contains a discussion, with ambitious suggestions for future work.

AdaHedge

In this section, we present and analyse the AdaHedge strategy. To introduce our notation and proof strategy, we start with the simplest possible analysis of vanilla Hedge, and then move on to refine it for AdaHedge.

Basic Hedge Analysis for Constant Learning Rate

Following [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF], we define the Hedge or exponential weights strategy as the choice of weights

w t,k = w 1,k e -ηL t-1,k Z t , (3)
where

w 1 = (1/K, . . . , 1/K) is the uniform distribution, Z t = w 1 • e -ηL
m t = - 1 η ln(w t • e -ηℓt ), (4)
which accumulates to M t = m 1 + . . . + m t . This approximation is a standard tool in the literature. For example, the mix loss m t corresponds to the loss of [START_REF] Vovk | A game of prediction with expert advice[END_REF][START_REF] Vovk | Competitive on-line statistics[END_REF] Aggregating Pseudo Algorithm, and tracking the evolution of -m t is a crucial ingredient in the proof of Theorem 2.2 of [START_REF] Cesa | Prediction, learning, and games[END_REF].

The definitions may be extended to η = ∞ by letting η tend to ∞. We then find that w t becomes a uniform distribution on the set of experts {k | L t-1,k = L * t-1 } that have incurred smallest cumulative loss before time t. That is, Hedge with η = ∞ reduces to Follow-the-Leader, where in case of ties the weights are distributed uniformly. The limiting value for the mix loss is m t = L * t -L * t-1 . In our approximation of the Hedge loss h t by the mix loss m t , we call the approximation error δ t = h tm t the mixability gap. Bounding this quantity is a standard part of the analysis of Hedge-type algorithms (see, for example, Lemma 4 of [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF]) and it also appears to be a fundamental notion in sequential prediction even when only socalled mixable losses are considered [START_REF] Grünwald | Safe learning: bridging the gap between Bayes, MDL and statistical learning theory via empirical convexity[END_REF][START_REF] Grünwald | The safe Bayesian: learning the learning rate via the mixability gap[END_REF]; see also Section 6.2. We let ∆ t = δ 1 + . . . + δ t denote the cumulative mixability gap, so that the regret for Hedge may be decomposed as

R = H -L * = M -L * + ∆. ( 5
)
Here M -L * may be thought of as the regret under the mix loss and ∆ is the cumulative approximation error when approximating the Hedge loss by the mix loss. Throughout the paper, our proof strategy will be to analyse these two contributions to the regret, M -L * and ∆, separately.

The following lemma, which is proved in Appendix A, collects a few basic properties of the mix loss:

Lemma 1 (Mix Loss with Constant Learning Rate) For any learning rate η ∈ (0, ∞]

1. ℓ - t ≤ m t ≤ h t ≤ ℓ + t , so that 0 ≤ δ t ≤ s t .

Cumulative mix loss telescopes: M

=    -1 η ln w 1 • e -ηL for η < ∞, L * for η = ∞.
3. Cumulative mix loss approximates the loss of the best expert:

L * ≤ M ≤ L * + ln K η .
4. The cumulative mix loss M is nonincreasing in η.

In order to obtain a bound for Hedge, one can use the following well-known bound on the mixability gap, which is obtained using Hoeffding's bound on the cumulant generating function (Cesa-Bianchi and Lugosi, 2006, Lemma A.1):

δ t ≤ η 8 s 2 t , (6)
from which ∆ ≤ S 2 T η/8, where (as in the introduction) S t = max{s 1 , . . . , s t } is the maximum loss range in the first t rounds. Together with the bound M -L * ≤ ln(K)/η from mix loss property #3 this leads to

R = (M -L * ) + ∆ ≤ ln K η + ηS 2 T 8 . ( 7
)
The bound is optimized for η = 8 ln(K)/(S 2 T ), which equalizes the two terms. This leads to a bound on the regret of S T ln(K)/2, matching the lower bound on worst-case regret from the textbook by Cesa-Bianchi and Lugosi (2006, Section 3.7). We can use this tuned learning rate if the time horizon T is known in advance. To deal with the situation where T is unknown, the doubling trick can be used, at the cost of a worse constant factor in the leading term of the regret bound.

In the remainder of this section, we introduce a completely parameterless algorithm called AdaHedge. We then refine the steps of the analysis above to obtain a better regret bound.

AdaHedge Analysis

In the previous section, we split the regret for Hedge into two parts: M -L * and ∆, and we obtained a bound for both. The learning rate η was then tuned to equalise these two bounds. The main distinction between AdaHedge and other Hedge approaches is that AdaHedge does not consider an upper bound on ∆ in order to obtain this balance: instead it aims to equalize ∆ and ln(K)/η. As the cumulative mixability gap ∆ t is nondecreasing in t (by mix loss property #1) and can be observed on-line, it is possible to adapt the learning rate directly based on ∆ t .

Perhaps the easiest way to achieve this is by using the doubling trick: each subsequent block uses half the learning rate of the previous block, and a new block is started as soon as the observed cumulative mixability gap ∆ t exceeds the bound on the mix loss ln(K)/η, which ensures these two quantities are equal at the end of each block. This is the approach taken in an earlier version of AdaHedge [START_REF] Van Erven | Adaptive hedge[END_REF]. However, we can achieve the same goal much more elegantly, by decreasing the learning rate with time according to

η ah t = ln K ∆ ah t-1 (8)
(where ∆ ah 0 = 0, so that η ah 1 = ∞). Note that the AdaHedge learning rate does not involve the end time T or any other unobserved properties of the data; all subsequent analysis is therefore valid for all T simultaneously. The definitions (3) and (4) of the weights and the mix loss are modified to use this new learning rate:

w ah t,k = w ah 1,k e -η ah t L t-1,k w ah 1 • e -η ah t L t-1 and m ah t = - 1 η ah t ln(w ah t • e -η ah t ℓt ), (9)
with w ah 1 = (1/K, . . . , 1/K) uniform. Note that the multiplicative update rule for the weights no longer applies when the learning rate varies with t; the last three results of Lemma 1 are also no longer valid. Later we will also consider other algorithms to determine variable learning rates; to avoid confusion the considered algorithm is always specified in the superscript in our notation. See Table 1 for reference. From now on, AdaHedge will be defined as the Hedge algorithm with learning rate defined by (8). For concreteness, a matlab implementation appears in Figure 1.

Our learning rate is similar to that of [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF], but it is less pessimistic as it is based on the mixability gap ∆ t itself rather than its bound, and as such may Single round quantities for trial t:

ℓ t Loss vector ℓ - t = min k ℓ t,k , ℓ + t = max k ℓ t,k
Min and max loss

s t = ℓ + t -ℓ - t
Loss range

w alg t = e -η alg t •L t-1 / k e -η alg t L t-1,k
Weights played

h alg t = w alg t • ℓ t Hedge loss m alg t = -1 η alg t ln w alg t • e -η alg t ℓt
Mix loss

δ alg t = h alg t -m alg t Mixability gap v alg t = Var k∼w alg t [ℓ t,k ]
Loss variance

Aggregate quantities after t rounds:

(The final time T is omitted from the subscript where possible, e.g.

L * = L * T ) L t , L - t , L + t , H alg t , M alg t , ∆ alg t , V alg t t τ =1 of ℓ τ , ℓ - τ , ℓ + τ , h alg τ , m alg τ , δ alg τ , v alg τ S t = max{s 1 , . . . , s t } Maximum loss range L * t = min k L t,k
Cumulative loss of the best expert

R alg t = H alg t -L * t Regret
Algorithms (the "alg" in the superscript above):

(η) Hedge with fixed learning rate η ah AdaHedge, defined by ( 8) ftl Follow-the-Leader (η ftl = ∞) ff FlipFlop, defined by ( 17)

Table 1: Notation exploit easy sequences of losses more aggressively. Moreover our tuning of the learning rate simplifies the analysis, leading to tighter results; the essential new technical ingredients appear as Lemmas 3, 5 and 7 below. We analyse the regret for AdaHedge like we did for a fixed learning rate in the previous section: we again consider M ah -L * and ∆ ah separately. This time, both legs of the analysis become slightly more involved. Luckily, a good bound can still be obtained with only a small amount of work. First we show that the mix loss is bounded by the mix loss we would have incurred if we would have used the final learning rate η ah T all along:

Lemma 2 Let dec be any strategy for choosing the learning rate such that η 1 ≥ η 2 ≥ . . . Then the cumulative mix loss for dec does not exceed the cumulative mix loss for the strategy that uses the last learning rate η T from the start:

M dec ≤ M (η T ) .
This lemma was first proved in its current form by Kalnishkan and Vyugin (2005, Lemma 3), and an essentially equivalent bound was introduced by [START_REF] Györfi | Sequential prediction of unbounded stationary time series[END_REF] in the proof of their Lemma 1. Related techniques for dealing with time-varying learning rates go back to [START_REF] Auer | Adaptive and self-confident on-line learning algorithms[END_REF].

M dec T = T t=1 m dec t = T t=1 M (ηt) t -M (ηt) t-1 ≤ T t=1 M (ηt) t -M (η t-1 ) t-1 = M (η T ) T
, which was to be shown.

We can now show that the two contributions to the regret are still balanced.

Lemma 3 The AdaHedge regret is R ah = M ah -L * + ∆ ah ≤ 2∆ ah .
Proof As δ ah t ≥ 0 for all t (by mix loss property #1), the cumulative mixability gap ∆ ah t is nondecreasing. Consequently, the AdaHedge learning rate η ah t as defined in ( 8) is nonincreasing in t. Thus Lemma 2 applies to M ah ; together with mix loss property #3 and ( 8) this yields

M ah ≤ M (η ah T ) ≤ L * + ln K η ah T = L * + ∆ ah T -1 ≤ L * + ∆ ah T .
Substitution into the trivial decomposition R ah = M ah -L * + ∆ ah yields the result.

The remaining task is to establish a bound on ∆ ah . As before, we start with a bound on the mixability gap in a single round, but rather than (6), we use Bernstein's bound on the mixability gap in a single round to obtain a result that is expressed in terms of the variance of the losses,

v ah t = Var k∼w ah t [ℓ t,k ] = k w ah t,k (ℓ t,k -h ah t ) 2 .
Lemma 4 (Bernstein's Bound) Let η t = η alg t ∈ (0, ∞) denote the finite learning rate chosen for round t by any algorithm "alg". The mixability gap δ alg t satisfies

δ alg t ≤ g(s t η t ) s t v alg t , where g(x) = e x -x -1 x . ( 10
)
Further, v alg t ≤ (ℓ + t -h alg t )(h alg t -ℓ - t ) ≤ s 2 t /4.
Proof This is Bernstein's bound (Cesa-Bianchi and Lugosi, 2006, Lemma A.5) on the cumulant generating function, applied to the random variable

(ℓ t,k -ℓ - t )/s t ∈ [0, 1] with k distributed according to w alg t .
Bernstein's bound is more sophisticated than Hoeffding's bound ( 6), because it expresses that the mixability gap δ t is small not only when η t is small, but also when all experts have approximately the same loss, or when the weights w t are concentrated on a single expert.

The next step is to use Bernstein's inequality to obtain a bound on the cumulative mixability gap ∆ ah . In the analysis of [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF] this is achieved by first applying Bernstein's bound for each individual round, and then using a telescoping argument to obtain a bound on the sum. With our learning rate (8) it is convenient to reverse these steps: we first telescope, which can now be done with equality, and subsequently apply Bernstein's inequality in a stricter way.

Lemma 5 AdaHedge's cumulative mixability gap satisfies

∆ ah 2 ≤ V ah ln K + ( 2 3 ln K + 1)S∆ ah .
Proof In this proof we will omit the superscript "ah". Using the definition of the learning rate (8) and δ t ≤ s t (from mix loss property #1), we get

∆ 2 = T t=1 ∆ 2 t -∆ 2 t-1 = t (∆ t-1 + δ t ) 2 -∆ 2 t-1 = t 2δ t ∆ t-1 + δ 2 t = t 2δ t ln K η t + δ 2 t ≤ t 2δ t ln K η t + s t δ t ≤ 2 ln K t δ t η t + S∆. ( 11
)
The inequalities in this equation replace a δ t term by S, which is of no concern: the resulting term S∆ adds at most 2S to the regret bound. We will now show

δ t η t ≤ 1 2 v t + 1 3 s t δ t . ( 12
)
This supersedes the bound δ t /η t ≤ (e -2)v t for η t ≤ 1 used by [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF]. Even though at first sight circular, the form (12) has two major advantages. First, inclusion of the overhead 1 3 s t δ t will only affect smaller order terms of the regret, but admits a reduction of the leading constant to the optimal factor 1 2 . This gain directly percolates to our regret bounds below. Second, (12) holds for unbounded η t , which simplifies tuning considerably.

First note that ( 12) is clearly valid if η t = ∞. Assuming that η t is finite, we can obtain this result by rewriting Bernstein's bound (10) as follows:

1 2 v t ≥ δ t • s t 2g(s t η t ) = δ t η t -s t f (s t η t )δ t , where f (x) = e x -1 2 x 2 -x -1 xe x -x 2 -x .
Remains to show that f (x) ≤ 1/3 for all x ≥ 0. After rearranging, we find this to be the case if (3x)e x ≤ 1 2 x 2 + 2x + 3. Taylor expansion of the left-hand side around zero reveals that (3x)e x = 1 2 x 2 + 2x + 3 -1 6 x 3 ue u for some 0 ≤ u ≤ x, from which the result follows. The proof is completed by plugging ( 12) into ( 11) and finally relaxing s t ≤ S.

Combination of these results yields the following natural regret bound, analogous to Theorem 5 of [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF].

Theorem 6 AdaHedge's regret is bounded by

R ah ≤ 2 √ V ah ln K + S( 4 3 ln K + 2).
Proof Lemma 5 is of the form

(∆ ah ) 2 ≤ a + b∆ ah , ( 13
)
with a and b nonnegative numbers. Solving for ∆ ah then gives

∆ ah ≤ 1 2 b + 1 2 b 2 + 4a ≤ 1 2 b + 1 2 ( √ b 2 + √ 4a) = √ a + b, which by Lemma 3 implies that R ah ≤ 2 √ a + 2b. ( 14
)
Plugging in the values a = V ah ln K and b = S( 2 3 ln K + 1) from Lemma 5 completes the proof.

This first regret bound for AdaHedge is difficult to interpret, because the cumulative loss variance V ah depends on the actions of the AdaHedge strategy itself (through the weights w ah t ). Below, we will derive a regret bound for AdaHedge that depends only on the data. However, AdaHedge has one important property that is captured by this first result that is no longer expressed by the worst-case bound we will derive below. Namely, if the data are easy in the sense that there is a clear best expert, say k * , then the weights played by AdaHedge will concentrate on that expert. If w ah t,k * → 1 as t increases, then the loss variance must decrease: v ah t → 0. Thus, Theorem 6 suggests that the AdaHedge regret may be bounded if the weights concentrate on the best expert sufficiently quickly. This indeed turns out to be the case: we can prove that the regret is bounded for the stochastic setting where the loss vectors ℓ t are independent, and E[L t,k * -L t,k ] = Ω(t β ) for all k = k * and any β > 1/2. This is an important feature of AdaHedge when it is used as a stand-alone algorithm, and we provide a proof for the previous version of the strategy in [START_REF] Van Erven | Adaptive hedge[END_REF]. See Section 5.4 for an example of concentration of the AdaHedge weights. Here we will not pursue this further, because the Follow-the-Leader strategy also incurs bounded loss in that case; we rather focus attention on how to successfully compete with FTL in Section 3.

We now proceed to derive a bound that depends only on the data, using an approach similar to the one taken by [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF]. We first bound the cumulative loss variance as follows:

Lemma 7 Assume L * ≤ H. The cumulative loss variance for AdaHedge satisfies

V ah ≤ S (L + -L * )(L * -L -) L + -L - + 2S∆.
In the degenerate case L -= L + the fraction reads 0/0, but since we then have V ah = 0, from here on we define the ratio to be zero in that case, which is also its limiting value.

Proof We omit all "ah" superscripts. By Lemma 4 we have

v t ≤ (ℓ + t -h t )(h t -ℓ - t ). Now V = T t=1 v t ≤ t (ℓ + t -h t )(h t -ℓ - t ) ≤ S t (ℓ + t -h t )(h t -ℓ - t ) s t = ST t 1 T (ℓ + t -h t )(h t -ℓ - t ) s t ≤ S (L + -H)(H -L -) L + -L - , ( 15
)
where the last inequality is an instance of Jensen's inequality applied to the function B defined on the domain x ≤ y ≤ z by B(x, y, z) = (zy)(yx)/(zx) for x < z and B(x, y, z) = 0 for x = z to ensure continuity. To verify that B is jointly concave, we will show that the Hessian is negative semi-definite on the interior x < y < z. Concavity on the whole domain then follows from continuity. The Hessian, which turns out to be the rank one matrix

∇ 2 B(x, y, z) = - 2 (z -x) 3    z -y x -z y -x       z -y x -z y -x    ⊺ ,
is negative semi-definite since it is a negative scaling of a positive outer product.

Subsequently using H ≥ L * (by assumption) and H ≤ L * + 2∆ (by Lemma 3) yields

(L + -H)(H -L -) L + -L - ≤ (L + -L * )(L * + 2∆ -L -) L + -L - ≤ (L + -L * )(L * -L -) L + -L - + 2∆
as desired.

This can be combined with Lemmas 5 and 3 to obtain our first main result:

Theorem 8 (AdaHedge Worst-Case Regret Bound) AdaHedge's regret is bounded by

R ah ≤ 2 S (L + -L * )(L * -L -) L + -L - ln K + S( 16 3 ln K + 2). ( 16
)
Proof If H ah < L * , then R ah < 0 and the result is clearly valid. But if H ah ≥ L * , we can bound V ah using Lemma 7 and plug the result into Lemma 5 to get an inequality of the form (13) with a = S(L + -L * )(L * -L -)/(L + -L -) and b = S( 8 3 ln K + 1). Following the steps of the proof of Theorem 6 with these modified values for a and b we arrive at the desired result. This bound has several useful properties:

1. It is always smaller than the CBMS bound (1), with a leading constant that has been reduced from the previously best-known value of 2.63 to 2. To see this, note that (16) increases to (1) if we replace L + by the upper bound L -+ ST . It can be substantially stronger than (1) if the range of the losses s t is highly variable.

2. The bound is "fundamental", a concept discussed in detail by [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF]: it is invariant to translations of the losses and proportional to their scale. It is therefore valid for arbitrary loss ranges, regardless of sign. In fact, not just the bound, but AdaHedge itself is fundamental in this sense: see Section 4 for a discussion and proof.

3. The regret is small when the best expert either has a very low loss, or a very high loss.

The latter is important if the algorithm is to be used for a scenario in which we are provided with a sequence of gain vectors g t rather than losses: we can transform these gains into losses using ℓ t = -g t , and then run AdaHedge. The bound then implies that we incur small regret if the best expert has very small cumulative gain relative to the minimum gain.

4. The bound is not dependent on the number of trials but only on the losses; it is a "timeless" bound as discussed below.

What are Timeless Bounds?

All bounds presented for AdaHedge (and FlipFlop) are "timeless". We call a regret bound timeless if it does not change under insertion of additional trials where all experts are assigned the same loss. Intuitively, the prediction task does not become more difficult if nature should insert same-loss trials. Since these trials do nothing to differentiate between the experts, they can safely be ignored by the learner without affecting her regret; in fact, many Hedge strategies, including Hedge with a fixed learning rate, FTL, AdaHedge and CBMS already have the property that their future behaviour does not change under such insertions: they are robust against such time dilation. If any strategy does not have this property by itself, it can easily be modified to ignore equal-loss trials.

It is easy to imagine practical scenarios where this robustness property would be important. For example, suppose you hire a number of experts who continually monitor the assets in your portfolio. Usually they do not recommend any changes, but occasionally, when they see a rare opportunity or receive subtle warning signs, they may urge you to trade, resulting in a potentially very large gain or loss. It seems only beneficial to poll the experts often, and there is no reason why the many resulting equal-loss trials should complicate the learning task.

The oldest bounds for Hedge scale with √ T or √ L * , and are thus not timeless. From the results above we can obtain fundamental and timeless variants with, for parameterless algorithms, the best known leading constants (the first item below follows Corollary 1 of [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF]):

Corollary 9 The AdaHedge regret satisfies the following inequalities: 163 ln K + 2) (symmetric bound, useful for gains).

R ah ≤ T t=1 s 2 t ln K + S( 4 3 ln K + 2); (analogue of traditional T -based bounds), R ah ≤ 2 S(L * -L -) ln K + S( 16 3 ln K + 2) (analogue of traditional L * -based bounds), R ah ≤ 2 S(L + -L * ) ln K + S(
Proof We could get a bound that depends only on the loss ranges s t by substituting the worst case L * = (L + + L -)/2 into Theorem 8, but a sharper result is obtained by plugging the inequality v t ≤ s 2 t /4 from Lemma 4 directly into Theorem 6. This yields the first item above. The other two inequalities follow easily from Theorem 8.

In the next section, we show how we can compete with FTL while at the same time maintaining all these worst-case guarantees up to a constant factor.

FlipFlop

AdaHedge balances the cumulative mixability gap ∆ ah and the mix loss regret M ah -L * by reducing η ah t as necessary. But, as we observed previously, if the data are not hopelessly adversarial we might not need to worry about the mixability gap: as Lemma 4 expresses, δ ah t is also small if the variance v ah t of the loss under the weights w ah t,k is small, which is the case if the weight on the best expert max k w ah t,k becomes close to one. AdaHedge is able to exploit such a lucky scenario to an extent: as explained in the discussion that follows Theorem 6, if the weight of the best expert goes to one quickly, AdaHedge will have a small cumulative mixability gap, and therefore, by Lemma 3, a small regret. This happens, for example, in the stochastic setting with independent, identically distributed losses, when a single expert has the smallest expected loss. Similarly, in the experiment of Section 5.4, the AdaHedge weights concentrate sufficiently quickly for the regret to be bounded.

There is the potential for a nasty feedback loop, however. Suppose there are a small number of difficult early trials, during which the cumulative mixability gap increases relatively quickly. AdaHedge responds by reducing the learning rate (8), with the effect that the weights on the experts become more uniform. As a consequence, the mixability gap in future trials may be larger than what it would have been if the learning rate had stayed high, leading to further unnecessary reductions of the learning rate, and so on. The end result may be that AdaHedge behaves as if the data are difficult and incurs substantial regret, even in cases where the regret of Hedge with a fixed high learning rate, or of Followthe-Leader, is bounded! Precisely this phenomenon occurs in the experiment in Section 5.2 below: AdaHedge's regret is close to the worst-case bound, whereas FTL hardly incurs any regret at all. It appears, then, that we must either hope that the data are easy enough that we can make the weights concentrate quickly on a single expert, by not reducing the learning rate at all; or we fear the worst and reduce the learning rate as much as we need to be able to provide good guarantees. We cannot really interpolate between these two extremes: an intermediate learning rate may not yield small regret in favourable cases and may at the same time destroy any performance guarantees in the worst case.

It is unclear a priori whether we can get away with keeping the learning rate high, or that it is wiser to play it safe using AdaHedge. The most extreme case of keeping the learning rate high, is the limit as η tends to ∞, for which Hedge reduces to Follow-the-Leader. In this section we work out a strategy that combines the advantages of FTL and AdaHedge: it retains AdaHedge's worst-case guarantees up to a constant factor, but its regret is also bounded by a constant times the regret of FTL (Theorem 15). Perhaps surprisingly, this is not easy to achieve. To see why, imagine a scenario where the average loss of the best expert is substantial, whereas the regret of either Follow-the-Leader or AdaHedge, is small. Since our combination has to guarantee a similarly small regret, it has only a very limited margin for error. We cannot, for example, simply combine the two algorithms by recursively plugging them into Hedge with a fixed learning rate, or into AdaHedge: the performance guarantees we have for those methods of combination are too weak. Even if both FTL and AdaHedge yield small regret on the original problem, choosing the actions of FTL for some rounds and those of AdaHedge for the other rounds may fail if we do it naively, because the regret is not necessarily increasing, and we may end up picking each algorithm precisely in those rounds where the other one is better.

Luckily, alternating between the optimistic FTL strategy and the worst-case-proof Ada-Hedge does turn out to be possible if we do it in a careful way. In this section we explain the appropriate strategy, called FlipFlop (superscript: "ff"), and show that it combines the desirable properties of both FTL and AdaHedge.

Exploiting Easy Data by Following the Leader

We first investigate the potential benefits of FTL over AdaHedge. Lemma 10 below identifies the circumstances under which FTL will perform well, which is when the number of leader changes is small. It also shows that the regret for FTL is equal to its cumulative mixability gap when FTL is interpreted as a Hedge strategy with infinite learning rate.

Lemma 10 Let c t be an indicator for a leader change at time t: define c t = 1 if there exists an expert k such that L t-1,k = L * t-1 while L t,k = L * t , and c t = 0 otherwise. Let C t = c 1 + . . . + c t be the cumulative number of leader changes. Then the FTL regret satisfies

R ftl = ∆ (∞) ≤ S C.
Proof We have M (∞) = L * by mix loss property #3, and consequently

R ftl = ∆ (∞) + M (∞) -L * = ∆ (∞) .
To bound ∆ (∞) , notice that, for any t such that c t = 0, all leaders remained leaders and incurred identical loss. It follows that m

(∞) t = L * t -L * t-1 = h (∞) t and hence δ (∞) t = 0. By bounding δ (∞) t
≤ S for all other t we obtain

∆ (∞) = T t=1 δ (∞) t = t : ct=1 δ (∞) t ≤ t : ct=1 S = S C, as required.
We see that the regret for FTL is bounded by the number of leader changes. This quantity is both fundamental and timeless. It is a natural measure of the difficulty of the problem, because it remains small whenever a single expert makes the best predictions on average, even in the scenario described above, in which AdaHedge gets caught in a feedback loop. One example where FTL outperforms AdaHedge is when the losses for two experts are (1, 0) on the first round, and keep alternating according to (1, 0), (0, 1), (1, 0), . . . for the remainder of the rounds. Then the FTL regret is only 1/2, whereas AdaHedge's performance is close to the worst-case bound (because its weights w ah t converge to (1/2, 1/2), for which the bound (6) on the mixability gap is tight). This scenario is illustrated further in the experiments, Section 5.2.

FlipFlop

FlipFlop is a Hedge strategy in the sense that it uses exponential weights defined by ( 9), but the learning rate η ff t now alternates between infinity, such that the algorithm behaves like FTL, and the AdaHedge value, which decreases as a function of the mixability gap accumulated over the rounds where AdaHedge is used. In Definition 11 below, we will specify the "flip" regime R t , which is the subset of times {1, . . . , t} where we follow the leader by using an infinite learning rate, and the "flop" regime R t = {1, . . . , t} \ R t , which is the set of times where the learning rate is determined by AdaHedge (mnemonic: the position of the bar refers to the value of the learning rate). We accumulate the mixability gap, the mix loss and the variance for these two regimes separately:

∆ t = τ ∈Rt δ ff τ ; M t = τ ∈Rt m ff τ ; (flip) ∆ t = τ ∈R t δ ff τ ; M t = τ ∈R t m ff τ ; V t = τ ∈R t v ff τ . (flop)
We also change the learning rate from its definition for AdaHedge in (8) to the following, which differentiates between the two regimes of the strategy:

η ff t = η flip t if t ∈ R t , η flop t if t ∈ R t ,
where

η flip t = η ftl t = ∞ and η flop t = ln K ∆ t-1 . ( 17
)
Like for AdaHedge, η flop t = ∞ as long as ∆ t-1 = 0, which now happens for all t such that R t-1 = ∅. Note that while the learning rates are defined separately for the two regimes, the exponential weights (9) of the experts are still always determined using the cumulative losses L t,k over all rounds. We also point out that, for rounds t ∈ R, the learning rate η ff t = η flop t is not equal to η ah t , because it uses ∆ t-1 instead of ∆ ah t-1 . For this reason, the FlipFlop regret may be either better or worse than the AdaHedge regret; our results below only preserve the regret bound up to a constant factor. In contrast, we do compete with the actual regret of FTL.

It remains to define the "flip" regime R t and the "flop" regime R t , which we will do by specifying the times at which to switch from one to the other. FlipFlop starts optimistically, with an epoch of the "flip" regime, which means it follows the leader, until ∆ t becomes too large compared to ∆ t . At that point it switches to an epoch of the "flop" regime, and keeps using η flop t until ∆ t becomes too large compared to ∆ t . Then the process repeats with the next epochs of the "flip" and "flop" regimes. The regimes are determined as follows:

Definition 11 (FlipFlop's Regimes) Let ϕ > 1 and α > 0 be parameters of the algorithm. Then

• FlipFlop starts in the "flip" regime. This completes the definition of the FlipFlop strategy. See Figure 2 for a matlab implementation.

The analysis proceeds much like the analysis for AdaHedge. We first show that, analogously to Lemma 3, the FlipFlop regret can be bounded in terms of the cumulative mixability gap; in fact, we can use the smallest cumulative mixability gap that we encountered in either of the two regimes, at the cost of slightly increased constant factors. This is the fundamental building block in our FlipFlop analysis. We then proceed to develop analogues of Lemmas 5 and 7, whose proofs do not have to be changed much to apply to FlipFlop. Finally, all these results are combined to bound the regret of FlipFlop in Theorem 15, which, after Theorem 8, is the second main result of this paper.

Lemma 12 (FlipFlop version of Lemma 3)

The following two bounds hold simultaneously for the regret of the FlipFlop strategy with parameters ϕ > 1 and α > 0:

R ff ≤ ϕα ϕ -1 + 2α + 1 ∆ + Sα ϕ ϕ -1 + 2 ; (18) R ff ≤ ϕ ϕ -1 + ϕ α + 2 ∆ + S ϕ α . ( 19
)
Proof The regret can be decomposed as

R ff = H ff -L * = ∆ + ∆ + M + M -L * . ( 20
)
Our first step will be to bound the mix loss M + M in terms of the mix loss M flop of the auxiliary strategy that uses η flop t for all t. As η flop t is nonincreasing, we can then apply Lemma 2 and mix loss property #3 to further bound

M flop ≤ M (η flop T ) ≤ L * + ln K η flop = L * + ∆ T -1 ≤ L * + ∆. ( 21
)
Let 0 = u 1 < u 2 < . . . < u b < T denote the times just before the epochs of the "flip" regime begin, i.e. round u i + 1 is the first round in the i-th "flip" epoch. Similarly let 0 < v 1 < . . . < v b ≤ T denote the times just before the epochs of the "flop" regime begin, where we artificially define v b = T if the algorithm is in the "flip" regime after T rounds. These definitions ensure that we always have u b < v b ≤ T . For the mix loss in the "flop" regime we have

M = (M flop u 2 -M flop v 1 ) + (M flop u 3 -M flop v 2 ) + . . . + (M flop u b -M flop v b-1 ) + (M flop -M flop v b ). ( 22
)
Let us temporarily write η t = η flop t to avoid double superscripts. For the "flip" regime, the properties in Lemma 1, together with the observation that η flop t does not change during the "flip" regime, give

M = b i=1 M (∞) v i -M (∞) u i = b i=1 M (∞) v i -L * u i ≤ b i=1 M (ηv i ) v i -L * u i ≤ b i=1 M (ηv i ) v i -M (ηv i ) u i + ln K η v i = b i=1 M flop v i -M flop u i + ln K η u i +1 = M flop v 1 -M flop u 1 + M flop v 2 -M flop u 2 + . . . + M flop v b -M flop u b + b i=1 ∆ u i . ( 23
)
From the definition of the regime changes (Definition 11), we know the value of ∆ u i very accurately at the time u i of a change from a "flop" to a "flip" regime:

∆ u i > α∆ u i = α∆ v i-1 > ϕ∆ v i-1 = ϕ∆ u i-1 .
By unrolling from low to high i, we see that

b i=1 ∆ u i ≤ b i=1 ϕ 1-i ∆ u b ≤ ∞ i=1 ϕ 1-i ∆ u b = ϕ ϕ -1 ∆ u b .
Adding up ( 22) and ( 23), we therefore find that the total mix loss is bounded by

M + M ≤ M flop + b i=1 ∆ u i ≤ M flop + ϕ ϕ -1 ∆ u b ≤ L * + ϕ ϕ -1 + 1 ∆, ( 24
)
where the last inequality uses ( 21). Combination with (20) yields

R ff ≤ ϕ ϕ -1 + 2 ∆ + ∆. ( 25
)
Our next goal is to relate ∆ and ∆: by construction of the regimes, they are always within a constant factor of each other. First, suppose that after T trials we are in the bth epoch of the "flip" regime, that is, we will behave like FTL in round T + 1. In this state, we know from Definition 11 that ∆ is stuck at the value that prompted the start of the current epoch; this pinpoints its value up to S. At the same time, we know that ∆ is large enough to have prompted the start of the (b -1)st flop epoch, but not large enough to trigger the next regime change. From this we can deduce the following bounds:

(∆ -S)/α ≤ ∆ ≤ ϕ α ∆.
On the other hand, if after T rounds we are in the bth epoch of the "flop" regime, then a similar reasoning yields

α ϕ (∆ -S) ≤ ∆ ≤ α∆.
In both cases, it follows that ∆ < α∆ + Sα;

∆ < ϕ α ∆ + S ϕ α .
The two bounds of the lemma are obtained by plugging first one, then the other of these bounds into (25).

The "flop" cumulative mixability gap ∆ is related, as before, to the variance of the losses.

Lemma 13 (FlipFlop version of Lemma 5)

The cumulative mixability gap for the "flop" regime is bounded by the cumulative variance of the losses for the "flop" regime:

∆ 2 ≤ V ln K + ( 2 3 ln K + 1)S∆. ( 26
)
Proof The proof is analogous to the proof of Lemma 5, with ∆ instead of ∆ ah , V instead of V ah , and using η t = η flop t = ln(K)/∆ t-1 instead of η t = η ah t = ln(K)/∆ ah t-1 . Furthermore, we only need to sum over the rounds R in the "flop" regime, because ∆ does not change during the "flip" regime.

As it is straight-forward to prove an analogue of Theorem 6 for FlipFlop by solving the quadratic inequality in (26), we proceed directly towards establishing an analogue of Theorem 8. The following lemma provides the equivalent of Lemma 7 for FlipFlop. It can probably be strengthened to improve the lower order terms; we provide the version that is easiest to prove.

Lemma 14 (FlipFlop version of Lemma 7) Suppose H ff ≥ L * . The cumulative loss variance for FlipFlop with parameters ϕ > 1 and α > 0 satisfies

V ≤ S (L + -L * )(L * -L -) L + -L - + ϕ ϕ -1 + ϕ α + 2 S∆ + S 2 ϕ α .
Proof The sum of variances satisfies

V = t∈R v ff t ≤ T t=1 v ff t ≤ S (L + -H ff )(H ff -L -) L + -L - ,
where the first inequality simply includes the variances for FTL rounds (which are often all zero), and the second follows from the same reasoning as employed in (15). Subsequently using L * ≤ H ff (by assumption) and, from Lemma 12, H ff ≤ L * + γ, where γ denotes the right hand side of the bound (19), we find

V ≤ S (L + -L * )(L * + γ -L -) L + -L - ≤ S (L + -L * )(L * -L -) L + -L - + Sγ,
which was to be shown.

Combining Lemmas 12, 13 and 14, we obtain our second main result:

Theorem 15 (FlipFlop Regret Bound) The regret for FlipFlop with doubling parameters ϕ > 1 and α > 0 simultaneously satisfies the two bounds

R ff ≤ ϕα ϕ -1 + 2α + 1 R ftl + Sα ϕ ϕ -1 + 2 , R ff ≤ c 1 S (L + -L * )(L * -L -) L + -L - ln K + Sc 1 (c 1 + 2 3 ) ln K + c 2 ln K + 1 + Sc 2 ,
where

c 1 = ϕ ϕ -1 + ϕ α + 2 and c 2 = ϕ α .
This shows that, up to a multiplicative factor in the regret, FlipFlop is always as good as the best of Follow-the-Leader and AdaHedge's bound from Theorem 8. Of course, if AdaHedge significantly outperforms its bound, it is not guaranteed that FlipFlop will outperform the bound in the same way.

In the experiments in Section 5 we demonstrate that the multiplicative factor is not just an artifact of the analysis, but can actually be observed on simulated data. Proof From Lemma 10, we know that ∆ ≤ ∆ (∞) = R ftl . Substitution in (18) of Lemma 12 yields the first inequality.

For the second inequality, note that L * > H ff means the regret is negative, in which case the result is clearly valid. We may therefore assume w.l.o.g. that L * ≤ H ff and apply Lemma 14. Combination with Lemma 13 yields

∆ 2 ≤ V ln K + ( 2 3 ln K + 1)S∆ ≤ S (L + -L * )(L * -L -) L + -L - ln K + c 2 S 2 ln K + c 3 S∆,
where c 3 = (c 1 + 2 3 ) ln K + 1. We now solve this quadratic inequality as in ( 13) and relax it using

√ a + b ≤ √ a + √ b for nonnegative numbers a, b to obtain ∆ ≤ S (L + -L * )(L * -L -) L + -L - ln K + c 2 S 2 ln K + Sc 3 ≤ S (L + -L * )(L * -L -) L + -L - ln K + S c 2 ln K + c 3 .
In combination with Lemma 12, this yields the second bound of the theorem.

Finally, we propose to select the parameter values that minimize the constant factor in front of the leading terms of these regret bounds.

Corollary 16

The parameter values ϕ * = 2.37 and α * = 1.243 approximately minimize the worst of the two leading factors in the bounds of Theorem 15. The regret for FlipFlop with these parameters is simultaneously bounded by

R ff ≤ 5.64R ftl + 4.64S, R ff ≤ 5.64 S (L + -L * )(L * -L -) L + -L - ln K + S 35.53 ln K + 7.78 √ ln K + 7.54 .
Proof The leading factors f (ϕ, α) = ϕα ϕ-1 + 2α + 1 and g(ϕ, α) = ϕ ϕ-1 + ϕ α + 2 are respectively increasing and decreasing in α. They are equalized for α(ϕ) = 2ϕ -1 + 12ϕ 3 -16ϕ 2 + 4ϕ + 1 /(6ϕ -4). The analytic solution for the minimum of f (ϕ, α(ϕ)) in ϕ is too long to reproduce here, but it is approximately equal to ϕ * = 2.37, at which point α(ϕ * ) ≈ 1.243.

Invariance to Rescaling and Translation

A common simplifying assumption made in the literature is that the losses ℓ t,k are translated and normalised to take values in the interval [0, 1]. However, doing so requires a priori knowledge of the range of the losses. One would therefore prefer algorithms that do not require the losses to be normalised. As discussed by [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF], the regret bounds for such algorithms should not change when losses are translated (because this does not change the regret) and should scale by σ when the losses are scaled by a factor σ > 0 (because the regret scales by σ). They call such regret bounds fundamental and show that most of the methods they introduce satisfy such fundamental bounds.

Here we go even further: it is not just our bounds that are fundamental, but also our algorithms, which do not change their output weights if the losses are scaled or translated.

Theorem 17 Both AdaHedge and FlipFlop are invariant to translation and rescaling of the losses. Starting with losses ℓ 1 , . . . , ℓ T , obtain rescaled, translated losses ℓ ′ 1 , . . . , ℓ ′ T by picking any σ > 0 and arbitrary reals τ 1 , . . . , τ T , and setting ℓ ′ t,k = σℓ t,k + τ t for t = 1, . . . , T and k = 1, . . . , K. Both AdaHedge and FlipFlop issue the exact same sequence of weights w ′ t = w t on ℓ ′ t as they do on ℓ t . Proof We annotate any quantity with a prime to denote that it is defined with respect to the losses ℓ ′ t . We omit the algorithm name from the superscript. First consider AdaHedge. We will prove the following relations by induction on t:

∆ ′ t-1 = σ∆ t-1 ; η ′ t = η t σ ; w ′ t = w t . ( 27
)
For t = 1, these are valid since ∆ ′ 0 = σ∆ 0 = 0, η ′ 1 = η 1 /σ = ∞, and w ′ 1 = w 1 are uniform. Now assume towards induction that ( 27) is valid for some t ∈ {1, . . . , T }. We can then compute the following values from their definition:

h ′ t = w ′ t • ℓ ′ t = σh t + τ t ; m ′ t = -(1/η ′ t ) ln(w ′ t • e -η ′ t ℓ ′ t ) = σm t + τ t ; δ ′ t = h ′ t -m ′ t = σ(h t -m t ) = σδ t .
Thus, the mixability gaps are also related by the scale factor σ. From there we can reestablish the induction hypothesis for the next round: we have ∆ ′ t = ∆ ′ t-1 + δ ′ t = σ∆ t-1 + σδ t = σ∆ t , and η ′ t+1 = ln(K)/∆ ′ t = η t+1 /σ. For the weights we get w ′ t+1 ∝ e -η ′ t+1 •L ′ t = e -(η t+1 /σ)•(σLt) ∝ w t+1 , which means the two must be equal since both sum to one. Thus the relations of (27) are also valid for time t + 1, proving the result for AdaHedge.

For FlipFlop, if we assume regime changes occur at the same times for ℓ ′ and ℓ, then similar reasoning reveals ∆

t ′ = σ∆ t ; ∆ ′ t = σ∆ t , η ′ flip t = η flip t /σ = ∞, η ′ flop t = η flop t /σ
, and w ′ t = w t . Remains to check that the regime changes do indeed occur at the same times. Note that in Definition 11, the "flop" regime is started when ∆ t ′ > (ϕ/α)∆ ′ t , which is equivalent to testing ∆ t > (ϕ/α)∆ t since both sides of the inequality are scaled by σ. Similarly, the "flip" regime starts when ∆ ′ t > α∆ t ′ , which is equivalent to the test ∆ t > α∆ t .

Experiments

We performed four experiments on artificial data, designed to clarify how the learning rate determines performance in a variety of Hedge algorithms. These experiments are designed to illustrate as clearly as possible the intricacies involved in the central question of this paper: whether to use a high learning rate (by following the leader) or to play it safe by using a smaller learning rate instead. Rather than mimic real-world data, on which high learning rates often seem to work well [START_REF] Devaine | Forecasting electricity consumption by aggregating specialized experts; a review of the sequential aggregation of specialized experts, with an application to Slovakian and French country-wide one-dayahead (half-)hourly predictions[END_REF], we vary the main factor that appears to drive the best choice of learning rate: the difference in cumulative loss between the experts. We have kept the experiments as simple as possible: the data are deterministic, and involve two experts. In each case, the data consist of one initial hand-crafted loss vector ℓ 1 , followed by a sequence of loss vectors ℓ 2 , . . ., ℓ T , which are either (0, 1) or (1, 0). For each experiment ξ ∈ {1, 2, 3, 4}, we want the cumulative loss difference L t,1 -L t,2 between the experts to follow a target f ξ (t), which will be a continuous, nondecreasing function of t. As the losses are binary, we cannot make L t,1 -L t,2 exactly equal to the target f ξ (t), but after the initial loss ℓ 1 , we choose every subsequent loss vector such that it brings L t,1 -L t,2 as close as possible to f ξ (t). All functions f ξ change slowly enough that |L t,1 -L t,2f ξ (t)| ≤ 1 for all t.

For each experiment, we let the number of trials be T = 1000, and we first plot the regret R (η) of the Hedge algorithm as a function of the fixed learning rate η. We subsequently plot the regret R alg t as a function of t = 1, . . . , T , for each of the following algorithms "alg":

1. Follow-the-Leader (Hedge with learning rate ∞)

2. Hedge with fixed learning rate η = 1 3. Hedge with the learning rate that optimizes the worst-case bound (7), which equals η = 8 ln(K)/(S 2 T ) ≈ 0.0745; we will call this algorithm "safe Hedge" for brevity.

4. AdaHedge 5. FlipFlop, with parameters ϕ * = 2.37 and α * = 1.243 as in Corollary 16

6. Hazan and Kale's 2008 algorithm, using the fixed learning rate that optimises the bound provided in their paper 7. NormalHedge, described by [START_REF] Chaudhuri | A parameter-free hedging algorithm[END_REF] Note that the safe Hedge strategy (the third item above) can only be used in practice if the horizon T is known in advance. Hazan and Kale's algorithm (the sixth item) additionally requires precognition of the empirical variance of the sequence of losses of the best expert up until T , which is not available in practice, but which we are supplying anyway. We include algorithms 6 and 7 because, as explained in Section 1.2, they are the state of the art in Hedge-style algorithms. Like AdaHedge, Hazan and Kale's algorithm is a refinement of the CBMS strategy described by [START_REF] Cesa-Bianchi | Improved second-order bounds for prediction with expert advice[END_REF]. They modify the definition of the weights in the Hedge algorithm to include second-order terms; the resulting bound is never more than a constant factor worse than the bounds (1) for CBMS and ( 16) for AdaHedge, but for some easy data it can be substantially better. For this reason it is a natural performance target for AdaHedge.

The bounds for CBMS and AdaHedge are incomparible with the bound for Normal-Hedge, being better for some, worse for other data. The reason we include it in the experiments is because, compared to the other methods, its performance in practice turns out to be excellent. We do not know whether there are data sequences on which FlipFlop significantly outperforms NormalHedge, nor whether there is a theoretical reason for this good performance, as the NormalHedge bound [START_REF] Chaudhuri | A parameter-free hedging algorithm[END_REF] is not tight for our experiments.

the start of the sequence, it is now viable to reduce the regret by using a very high learning rate. In particular, since there are no leader changes after the first round, FTL incurs a regret of only 1/2.

As in the first experiment, the regret increases linearly in t for every fixed η (provided it is less than ∞); but now the constant of linearity is large only for learning rates close to 1. Once FlipFlop enters the FTL regime for the second time, it stays there indefinitely, which results in bounded regret. After this small change in the setup compared to the previous experiment, NormalHedge also suddenly adapts very well to the data. The behaviour of the other algorithms is very similar to the first experiment: their regret grows without bound.

Experiment 3. Weights do not concentrate in AdaHedge

The third experiment uses ℓ 1 = (1, 0), and f 3 (t) = t 0.4 . The first few loss vectors are the same as in the previous experiment, but every now and then there are two loss vectors (1, 0) in a row, so that the first expert gradually falls behind the second in terms of performance. By t = T = 1000, the first expert has accumulated 508 loss, while the second expert has only 492.

For any fixed learning rate η, the weights used by Hedge now concentrate on the second expert. We know from Lemma 4 that the mixability gap in any round t is bounded by a constant times the variance of the loss under the weights played by the algorithm; as these weights concentrate on the second expert, this variance must go to zero. One can show that this happens quickly enough for the cumulative mixability gap to be bounded for any fixed η that does not vary with t or depend on T . From (5) we have

R (η) = M -L * + ∆ (η) ≤ ln K η + bounded = bounded.
So in this scenario, as long as the learning rate is kept fixed, we will eventually learn the identity of the best expert. However, if the learning rate is very small, this will happen so slowly that the weights still have not converged by t = 1000. Even worse, the top graph in Figure 5 shows that for intermediate values of the learning rate, not only do the weights fail to converge on the second expert sufficiently quickly, but they are sensitive enough to the alternation of the loss vectors to increase the overhead incurred each round.

For this experiment, it really pays to use a large learning rate rather than a safe small one. Thus FTL, Hedge with η = 1, FlipFlop and NormalHedge perform excellently, while safe Hedge, AdaHedge and Hazan and Kale's algorithm incur a substantial overhead. Extrapolating the trend in the graph, it appears that the overhead of these algorithms is not bounded. This is possible because the three algorithms with poor performance use a learning rate that decreases as a function of t. As a concequence the used learning rate may remain too small for the weights to concentrate. For the case of AdaHedge, this is an example of the "nasty feedback loop" described in Section 3.

Experiment 4. Weights do concentrate in AdaHedge

The fourth and last experiment uses ℓ 1 = (1, 0), and f 4 (t) = t 0.6 . The losses are comparable to those of the third experiment, but the performance gap between the two experts is somewhat larger. By t = T = 1000, the two experts have loss 532 and 468, respectively. It is now so easy to determine which of the experts is better that the top graph in Figure 6 is nonincreasing: the larger the learning rate, the better.

The algorithms that managed to keep their regret bounded in the previous experiment obviously still perform very well, but it is clearly visible that AdaHedge now achieves the same. As discussed below Theorem 6, this happens because the weight concentrates on the second expert quickly enough that AdaHedge's regret is bounded in this setting. The crucial difference with the previous experiment is that now we have f ξ (t) = t β with β > 1/2. Thus, while the previous experiment shows that AdaHedge can be tricked into reducing the learning rate while it would be better not to do so, the present experiment shows that on the other hand, sometimes AdaHedge does adapt really nicely to easy data, in contrast to algorithms that are tuned in terms of a worst-case bound.

Discussion and Conclusion

The main contributions of this work are twofold. First, we develop a new hedging algorithm called AdaHedge. The analysis simplifies existing results and we obtain improved bounds (Theorems 6 and 8). Moreover, AdaHedge is "fundamental" in the sense that its weights are invariant under translation and scaling of the losses (Section 4) and its bounds are "timeless" in the sense that they do not degenerate when rounds are inserted in which all experts incur the same loss. Second, we explain in detail why it is difficult to tune the learning rate such that good performance is obtained both for easy and for hard data, and we address the issue by developing the FlipFlop algorithm. FlipFlop never performs much worse than the Follow-the-Leader strategy, which works very well on easy data (Lemma 10), but it also retains a worst-case bound similar to the bound for AdaHedge (Theorem 15). As such, this work may be seen as solving a special case of a more general question: can we compete with Hedge for any fixed learning rate? We will now briefly discuss this question and then place our work in a broader context, which provides an ambitious agenda for future work.

General Question: Competing with Hedge for any fixed learning rate

Up to multiplicative constants, FlipFlop is at least as good as FTL and as (the bound for) AdaHedge. These two algorithms represent two extremes of choosing the learning rate η t in Hedge: FTL takes η t = ∞ to exploit easy data, whereas AdaHedge decreases η t with t to protect against the worst case. It is now natural to ask whether we can design a "Universal Hedge" algorithm that can compete with Hedge with any fixed learning rate η ∈ (0, ∞]. That is, for all T , the regret up to time T of Universal Hedge should be within a constant factor C of the regret incurred by Hedge run with the fixed η that minimizes the Hedge loss H (η) . This appears to be a difficult question, and maybe such an algorithm does not even exist. Yet, even partial results (such as an algorithm that competes with η ∈ [ ln(K)/(S 2 T ), ∞] or with a factor C that increases slowly, say, logarithmically, in T ) would already be of significant interest.

In this regard, it is interesting to note that, in practice, the learning rates chosen by sophisticated versions of Hedge do not always perform very well; higher learning rates often do better. This is noted by [START_REF] Devaine | Forecasting electricity consumption by aggregating specialized experts; a review of the sequential aggregation of specialized experts, with an application to Slovakian and French country-wide one-dayahead (half-)hourly predictions[END_REF], who resolve the issue by adapting the learning rate sequentially in an ad-hoc fashion, which works well in their application, but for which they can provide no guarantees. A Universal Hedge algorithm would adapt to the learning rate that is optimal with hindsight. FlipFlop is a first step in this direction. Indeed, it already has some of the properties of such an ideal algorithm: under some conditions we can show that if Hedge achieves bounded regret using any learning rate, then FTL, and therefore FlipFlop, also achieves bounded regret:

Theorem 18 Fix any η > 0. For K = 2 experts with losses in {0, 1} we have

R (η) is bounded ⇒ R ftl is bounded ⇒ R ff is bounded.
The proof is in Appendix B. While the second implication remains valid for more experts and other losses, we currently do not know if the first implication continues to hold as well.

The Big Picture

Broadly speaking, a "learning rate" is any single scalar parameter controlling the relative weight of the data and a prior regularization term in a learning task. Such learning rates pop up in batch settings as diverse as L 1 /L 2 -regularized regression such as Lasso and Ridge, standard Bayesian nonparametric and PAC-Bayesian inference [START_REF] Zhang | Information theoretical upper and lower bounds for statistical estimation[END_REF][START_REF] Audibert | PAC-Bayesian statistical learning theory[END_REF][START_REF] Catoni | PAC-Bayesian Supervised Classification[END_REF], and -as in this paper-in sequential prediction. All the applications just mentioned can formally be seen as variants of Bayesian inference -Bayesian MAP in Lasso and Ridge, randomized drawing from the posterior ("Gibbs sampling") in the PAC-Bayesian setting and in the Hedge setting. Moreover, in each of these applications, selecting the appropriate learning rate is nontrivial: simply adding the learning rate as another parameter and putting a Bayesian prior on it can lead to very bad results [START_REF] Grünwald | Suboptimal behavior of Bayes and MDL in classification under misspecification[END_REF]. An ideal method for adapting the learning rate would work in all such applications. In addition to the FlipFlop algorithm described here, we currently have methods that are guaranteed to work for several PAC-Bayesian style stochastic settings [START_REF] Grünwald | Safe learning: bridging the gap between Bayes, MDL and statistical learning theory via empirical convexity[END_REF][START_REF] Grünwald | The safe Bayesian: learning the learning rate via the mixability gap[END_REF]. It is encouraging that all these methods are based on the same, apparently fundamental, quantity, the mixability gap as defined before Lemma 1: they all employ different techniques to ensure a learning rate under which the posterior is concentrated and hence the mixability gap is small. This gives some hope that the approach can be taken even further. To give but one example, the "Safe Bayesian" method of [START_REF] Grünwald | The safe Bayesian: learning the learning rate via the mixability gap[END_REF] uses essentially the same technique as [START_REF] Devaine | Forecasting electricity consumption by aggregating specialized experts; a review of the sequential aggregation of specialized experts, with an application to Slovakian and French country-wide one-dayahead (half-)hourly predictions[END_REF], with an additional online-to-batch conversion step. [START_REF] Grünwald | The safe Bayesian: learning the learning rate via the mixability gap[END_REF] proves that this approach adapts to the optimal learning rate in an i.i.d. stochastic setting with arbitrary (countably or uncountably infinite) sets of "experts" (predictors); in contrast, AdaHedge and FlipFlop in the form presented in this paper are suitable for a worst-case setting with a finite set of experts. This raises, of course, the question of whether either the Safe Bayesian method can be extended to the worst-case setting (which would imply formal guarantees for the method of [START_REF] Devaine | Forecasting electricity consumption by aggregating specialized experts; a review of the sequential aggregation of specialized experts, with an application to Slovakian and French country-wide one-dayahead (half-)hourly predictions[END_REF]), or the FlipFlop algorithm can be extended to the setting with infinitely many experts.

Thus, we have two major, interrelated questions for future work: first, as explained in Section 6.1, we would like to be able to compete with all η in some set that contains a whole range rather than just two values. Second, we would like to compete with the best η in a setting with a countably infinite or even uncountable number of experts equipped with an arbitrary prior distribution.

A third question for future work is whether our methods can be extended beyond the standard worst-case Hedge setting and the stochastic i.i.d. setting. A particularly intriguing (and, as initial research suggests, nontrivial) question is whether AdaHedge and FlipFlop can be adapted to settings with limited feedback such as the adversarial bandit setting [START_REF] Cesa | Prediction, learning, and games[END_REF]. We would also like to extend our approach to the Hedgebased strategies for combinatorial decision domains like Component Hedge by [START_REF] Wouter | Hedging structured concepts[END_REF], and for matrix-valued predictions like those by [START_REF] Tsuda | Matrix exponentiated gradient updates for on-line learning and bregman projection[END_REF].

Follow

  Figure 1: Numerically robust matlab implementation of AdaHedge

%

  Returns the losses of FlipFlop % l(t,k) is the loss of expert k at time t; phi > 1 and alpha > 0 are parameters function h = flipflop(l, alpha, phi) M] = mix(eta, L); delta = max(0, h(t)-(M-Mprev)); Delta(regime) = Delta(regime) + delta; if Delta(regime) > scale(regime) * Delta(3-regime) regime = 3-regime; end end end

Figure 2 :

 2 Figure 2: FlipFlop, with new ingredients in boldface

Figure 3 :Figure 4 :Figure 5 :Figure 6 :

 3456 Figure 3: Hedge regret for Experiment 1 (FTL worst-case)

  Hedge in round t is h t = w t • ℓ t , the cumulative Hedge loss is H t = h 1 + . . . + h t , and our goal is to obtain a good bound on H T . To this end, it turns out to be technically convenient to approximate h t by the mix loss

	t-1 is a normalizing
	constant, and η ∈ (0, ∞) is a parameter of the algorithm called the learning rate. If η = 1 and one imagines L t-1,k to be the negative log-likelihood of a sequence of observations, then
	w t,k is the Bayesian posterior probability of expert k and Z t is the marginal likelihood of
	the observations. Like in Bayesian inference, the weights are updated multiplicatively, i.e.
	w t+1,k ∝ w t,k e -ηℓ t,k . The loss incurred by

•

  If t is the earliest time since the start of a "flip" epoch where ∆ t > (ϕ/α)∆ t , then the transition to the subsequent "flop" epoch occurs between rounds t and t + 1. (Recall that during "flip" epochs ∆ t increases in t whereas ∆ t is constant.) • Vice versa, if t is the earliest time since the start of a "flop" epoch where ∆ t > α∆ t , then the transition to the subsequent "flip" epoch occurs between rounds t and t + 1.

Acknowledgments

We would like to thank Wojciech Kotłowski, Gilles Stoltz and two anonymous referees for critical feedback. This work was supported in part by the IST Programme of the European

To reduce clutter, we omit results for CBMS; its behaviour is very similar to that of AdaHedge. Below we provide an exact description of each experiment, and discuss the results.

Experiment 1. Worst case for FTL

The experiment is defined by ℓ 1 = ( 1 2 0), and f 1 (t) = 0. This yields the following losses:

These data are the worst case for FTL: each round, the leader incurs loss one, while each of the two individual experts only receives a loss once every two rounds. Thus, the FTL regret increases by one every two rounds and ends up around 500. For any learning rate η, the weights used by the Hedge algorithm are repeated every two rounds, so the regret H t -L * t increases by the same amount every two rounds: the regret increases linearly in t for every fixed η that does not vary with t. However, the constant of proportionality can be reduced greatly by reducing the value of η, as the top graph in Figure 3 shows: for T = 1000, the regret becomes negligible for any η less than about 0.01. Thus, in this experiment, a learning algorithm must reduce the learning rate to shield itself from incurring an excessive overhead.

The bottom graph in Figure 3 shows the expected breakdown of the FTL algorithm; Hedge with fixed learning rate η = 1 also performs quite badly. When η is reduced to the value that optimises the worst-case bound, the regret becomes competitive with that of the other algorithms. Note that Hazan and Kale's algorithm has the best performance; this is because its learning rate is tuned in relation to the bound proved in the paper, which has a relatively large constant in front of the leading term. As a consequence the algorithm always uses a relatively small learning rate, which turns out to be helpful in this case but harmful in later experiments.

FlipFlop behaves as theory suggests it should: its regret increases alternately like the regret of AdaHedge and the regret of FTL. The latter performs horribly, so during those intervals the regret increases quickly, on the other hand the FTL intervals are relatively short-lived so in the end they do not harm the regret by more than a constant factor.

The NormalHedge algorithm still has acceptable performance, although its regret is relatively large in this experiment; we have no explanation for this but in fairness we do observe good performance of NormalHedge in the other three experiments as well as in numerous further unreported simulations.

Experiment 2. Best case for FTL

The second experiment is defined by ℓ 1 = (1, 0) and f 2 (t) = 3/2. This leads to the sequence of losses

in which the loss vectors are alternating for t ≥ 2. These data look very similar to the first experiment, but as the top graph in Figure 4 illustrates, because of the small changes at Community, under the PASCAL Network of Excellence, IST-2002-506778 and by NWO Rubicon grants 680-50-1010 and 680-50-1112.

Appendix A. Proof of Lemma 1

The result for η = ∞ follows from η < ∞ as a limiting case, so we may assume without loss of generality that η < ∞. Then m t ≤ h t is obtained by using Jensen's inequality to move the logarithm inside the expectation, and m t ≥ ℓ - t and h t ≤ ℓ + t follow by bounding all losses by their minimal and maximal values, respectively. The next two items are analogues of similar basic results in Bayesian probability. Item 2 generalizes the chain rule of probability Pr(x 1 , . . . , x T ) = T t=1 Pr(x t | x 1 , . . . , x t-1 ):

For the third item, use item 2 to write

The lower bound is obtained by bounding all L T,k from below by L * ; for the upper bound we drop all terms in the sum except for the term corresponding to the best expert and use w 1,k = 1/K. For the last item, let 0 < η < γ be any two learning rates. Then Jensen's inequality gives

This completes the proof.

Appendix B. Proof of Theorem 18

The second implication follows from Theorem 15, so we only need to prove the first implication. To this end, consider any infinite sequence of losses on which FTL has unbounded regret. We will argue that Hedge with fixed η must have unbounded regret as well.

Our argument is based on finding an infinite subsequence of the losses on which (a) the regret for Hedge with fixed η is at most as large as on the original sequence of losses; and (b) the regret for Hedge is infinite.

To construct this subsequence, first remove all trials t such that ℓ t,1 = ℓ t,2 (that is, both experts suffer the same loss), as these trials do not change the regret of either FTL or Hedge, nor their behaviour on any of the other rounds.

Next, we will selectively remove certain local extrema. We call a pair of two consecutive trials (t, t + 1) a local extremum if the losses in these trials are opposite: either ℓ t = (0, 1) and ℓ t+1 = (1, 0) or vice versa. Removing any local extremum will only decrease the regret for Hedge, as may be seen as follows.

We observe that removing a local extremum will not change the cumulative losses of the experts or the behaviour of Hedge on other rounds, so it suffices to consider only the regret incurred on rounds t and t + 1 themselves. By symmetry it is further sufficient to consider the case that ℓ t = (0, 1) and ℓ t+1 = (1, 0). Then, over trials t and t + 1, the individual experts both suffer loss 1, and for Hedge the loss is h t + h t+1 = w t • ℓ t + w t+1 • ℓ t+1 = w t,2 + w t+1,1 . Now, since the loss received by expert 1 in round t was less than that of expert 2, some weight shifts to the first expert: we must have w t+1,1 > w t,1 . Substitution gives h t + h t+1 > w t,1 + w t,2 = 1. Thus, Hedge suffers more loss in these two rounds than whichever expert turns out to be best in hindsight, and it follows that removing trials t and t + 1 will only decrease its regret (by an amount that depends only on η).

We proceed to select the local extrema to remove. To this end, let d t = L t,2 -L t,1 denote the difference in cumulative loss between the experts after t trials, and observe that removal of a local extremum at (t, t + 1) will simply remove the elements d t and d t+1 from the sequence d 1 , d 2 , . . . while leaving the other elements of the sequence unchanged. We will remove local extrema in a way that leads to an infinite subsequence of losses such that

In this subsequence, every two consecutive trials still constitute a local extremum, on which Hedge incurs a certain fixed positive regret. Consequently, the Hedge regret R t grows linearly in t and is therefore unbounded.

If the losses already satisfy (28), we are done. If not, then observe that there can only be a leader change at time t + 1 in the sense of Lemma 10 when d t = 0. Since the FTL regret is bounded by the number of leader changes (Lemma 10), and since FTL was assumed to have infinite regret, there must therefore be an infinite number of trials t such that d t = 0. We will remove local extrema in a way that preserves this property. In addition, we must have |d t+1d t | = 1 for all t, because d t+1 = d t would imply that ℓ t+1,1 = ℓ t+1,2 and we have already removed such trials. This second property is automatically preserved regardless of which trials we remove.

If the losses do not yet satisfy (28), there must be a first trial u with |d u | ≥ 2. Since there are infinitely many t with d t = 0, there must then also be a first trial w > u with d w = 0. Now choose any v ∈ [u, w) so that |d v | = max t∈ [u,w] |d t | maximizes the discrepancy between the cumulative losses of the experts. Since v attains the maximum and |d t+1d t | = 1 for all t as mentioned above, we have |d v+1 | = |d v | -1, so that (v, v + 1) must be a local extremum, and this is the local extremum we remove. Since |d v | ≥ |d u | ≥ 2, we also have |d v+1 | ≥ 1, so that this does not remove any of the trials in which d t = 0. Repetition of this process will eventually lead to v = u, so that trial u is removed. Given any T , the process may therefore be repeated until |d t | ≤ 1 for all t ≤ T . As |d t+1d t | = 1 for all t, we then match (28) for the first T trials. Hence by letting T go to infinity we obtain the desired result.


Eva Banik
email: ebanik@comp-ling.com

Claire Gardent
email: claire.gardent@loria.fr

Eric Kow

The KBGen Challenge

Introduction

The KBGen 2013 natural language generation challenge1 was intended to survey and compare the performance of various systems which perform tasks in the content realization stage of generation [START_REF] Banik | Kbgen text generation from knowledge bases as a new shared task[END_REF]. Given a set of relations which form a coherent unit, the task is to generate complex sentences which are grammatical and fluent in English. The relations for this year's challenge were selected from the AURA knowledge base (KB) [START_REF] Gunning | Project halo update -progress toward digital aristotle[END_REF]. In this paper we give an overview of the KB, describe our methodology for selecting sets of relations from the KB to provide input-output pairs for the challenge, and give details of the development and test data set that was provided to participating teams. Three teams have submitted system outputs for this year's challenge. In this paper we show BLEU and NIST scores for outputs generated by the teams. The full results of our evaluation, including human judgements, as well as the development and test data set are available at http://www.kbgen.org.

The AURA Knowledge Base

The AURA knowledge base [START_REF] Gunning | Project halo update -progress toward digital aristotle[END_REF] encodes information from a biology textbook [START_REF] Reece | Campbell Biology[END_REF]. It was developed to support a question answering system, to help students understand biological concepts by allowing them to ask questions about the material while reading the textbook. AURA is a frame-based KB which encodes events, the entities that participate in events, properties, and roles that the entities play in an event. The relations in the KB include relations between these types, including event-to-entity, event-to-event, event-to-property, entity-to-property. The KB is built on top of the CLIB generic library of concepts [START_REF] Barker | A library of generic concepts for composing knowledgebases[END_REF]. As part of the encoding process, concepts in CLIB are specialized and/or combined to encode biology-specific information. AURA is organized into a set of concept maps, where each concept map corresponds to a biological entity or process. The KB was encoded by biology teachers and contains around 5,000 concept maps. It is available for download for academic purposes in various formats including OWL2 .

The Content Selection Process for

KBGen 2012

The input provided to the participants consisted of a set of content units extracted from the KB, and a sentence corresponding to each content unit. The content units were semi-automatically selected from AURA such that:

• the set of relations in each content unit formed a connected graph

• each content unit can be verbalised by a single, possibly complex sentence which is grammatical and meaningful

• the set of content units contain as many different relations and concepts of different semantic types (events, entities, properties, etc) as possible.

To produce these inputs we first asked biology teachers to provide coherent content units using the AURA graphical interface. The basic assumption behind this approach was that, since every content unit can be expressed by a coherent sentence, each set of relations will exhibit a "coherence pattern". We then created a search space of candidate content units by extracting patterns from the KB which were similar to the patterns given by the biologists. Finally, we manually selected coherent content units.

Figure 1: " A hydrophobic compound attaches to a carrier protein at a region called the binding site."

Manual Selection of Content Units

In the first step of our process, biology teachers manually selected parts of concept maps which represented educationally useful information for biology students by searching for specific concepts in AURA's graph-based user interface. For each content unit they wrote a sentence verbalising the selected relations (Fig. 1). The biology teachers who identified these coherent, sentencesized chunks of information were familiar with the encoding practices in AURA, the underlying biology textbook, and had experience with the Inquire e-book application [START_REF] Spaulding | Inquire for iPad: Bringing question-answering AI into the classroom[END_REF] which displays educationally useful content from the KB.

From Graphs to Queries

In the second step, the graphical representations produced by the biologists were manually translated to specific knowledge base queries which were run in AURA to retrieve the instances satisfying the queries. Queries consist of two parts: a set of triples whose domain and range are variables, and a set of instance-of triples stating type constraints on the variables. The graph shown in Figure 1 was translated to the following query:

Type constraints:

(?CP instance-of Carrier-Protein) (?A instance-of Attach) (?BS instance-of Binding-Site) (?HP instance-of Hydrophilic-Compound)

Relation constraints:

(?A object ?HP) (?A base ?CP) (?A site ?BS) (?CP has-region ?BS)

From Queries to Generalized Query Patterns

After checking that it returns an answer, each query was generalized to a query pattern in order to find other queries which involved different concepts and relations, but still exhibited the same general coherence pattern. To derive generalized query patterns, specific queries were modified in two ways: 1) by removing type constraints on concepts, and 2) by replacing specific relations with generalized relation types.

Removing type constraints

Manually specified queries were extended by removing type constraints on variables. In the above example, types were generalised to Event or Entity:

(?CP instance-of Entity) (?A instance-of Event) (?BS instance-of Entity) (?HP instance-of Entity)

Other generalized types we used from the ontology were Property-Values and Roles.

Generalizing relations

Each query was generalized by defining equivalence classes over semantically similar relations and replacing the specific relation in the query with its equivalence class. The basic assumption behind this was that if a set of relations is coherent, we should be able to replace a relation with another, semantically similar relation in the set, and still have a coherent content unit. For example, whether two entities are connected by has-part or has-region is unlikely to make a difference to the coherence of a content unit.

Following this approach we identified groups of semantically similar relations within each relation type (Event-to-Event, Event-to-Entity, etc). The equivalence classes over relations were straightforwardly derived from distinctions made in CLIB [START_REF] Barker | A library of generic concepts for composing knowledgebases[END_REF], the upper ontology and library of general concepts that AURA is built on, although there was some manual fine-tuning required to exclude relations which were not reliably encoded in the KB. For example, we divided Entity-to-Entity relations into three categories, based on whether they had a spatial or meronymic sense, or expressed a specific relation between two chemicals: en2en-spatial: abuts is-above is-along is-at isinside is-opposite is-outside is-over location is-across is-on is-parallel-to is-perpendicularto is-under is-between is-facing is-below isbeside is-near en2en-part: possesses has-part has-region encloses has-basic-structural-unit hasstructural-part has-functional-part en2en-chemical: has-solute has-solvent hasatom has-ion has-oxidized-form hasreduced-form has-isomer

Here the distinction between spatial relations and meronymic relations was given by CLIB. Relations in the third group were specific to our domain and added during the process of encoding.

Event-to-entity relations were divided into "aux-participant" relations, which express the spatial orientation of an event, and "core-participant" relations which describe ways in which entities participate in the event. Here we used the categories of spatial relations and "participant" refrom CLIB. Our terminology reflects the fact that entities connected to an event by a core-participant relation are typically expressed as obligatory arguments of the verb in a sentence, whereas aux-participants would be expressed as optional modifiers: core-participants: agent object donor base instrument raw-material recipient result aux-participants: away-from destination origin path site toward With these definitions, the specific query illustrated above in section 3.2 was translated to the following query pattern:

(?A core-participant ?X) (?A core-participant ?CP) (?A aux-participant ?BS) (?CP en2en-part ?BS)

From Query Results to Content Units

Query patterns were expanded by producing all valid instantiations of the pattern in order to create a search space of candidate content units, and we ran each expanded query in AURA. The last step was filtering the results returned by satisfiable queries to obtain content units which can be verbalised in a single sentence. We used the following selection criteria to do this:

• A meaningful and grammatical sentence could be formed by verbalising all concepts, relations and properties present in the query result. • The set of content units should be as varied as possible. In particular, we did not keep a content unit if another very similar content unit was present in the selected units. For instance, if two content units contain identical relations (modulo concept labels), only one of these two units would be kept.

Given the pattern shown in Fig. 1 for instance, we obtained 27 coherent content units. Each content unit was verbalized as a sentence to provide development data for the content realization challenge. The following sentences illustrate the variation in the resulting content units:

-Polymers are digested in the lysosomes of eukaryotic cells. -Mucus is secreted in the alimentary canal of earthworms. -Lysosomal enzymes digest proteins and polymers at the lysosome of a eukaryotic cell. -A chemical is attached to the active site of a protein enzyme with an ionic bond. -An enzyme substrate complex is formed when a chemical attaches to the active site of a protein enzyme with a hydrogen bond. -Starch is stored in the lateral root of carrots.

Development Data Set

The development data set provided to participants contained 207 input-output pairs. These inputs were based on 19 different coherence patterns. Fig. 2 shows an input-output pair based on the pattern illustrated above. We also provided two lexicons: a lexicon for events which gave a mapping from events to verbs, their inflected forms and nominalizations and a lexicon for entities, which provided a noun and its plural form. The relevant entries in these lexicons for the input in Fig. 2 were:

Secretion,secretes,secrete,secreted,secretion Mucus, mucus, mucus Earthworm,earthworm,earthworms Alimentary-Canal,alimentary canal,alimentary canals

Test Set

Our test data set contained 72 inputs in the same format (and corresponding lexical resources as above), which were divided into three categories:

(1) seen patterns, seen relations: inputs that have exactly the same relations as some of the inputs in the development data set, but different concepts (2) seen patterns, unseen relations: these inputs are derived from patterns in the development data set. They have similar structure, but contain slightly different combinations of relations.

(3) unseen patterns: inputs extracted from a previously unused pattern, containing combinations of relations not seen in the development data set.

Evaluation

Participants submitted two sets of outputs:

(1) outputs generated by their system as is (modulo including the lexicon provided in the test data set) (2) outputs generated 6 days later, during which time teams had a chance to make improvements. Each team was allowed to submit a set of 5 ranked outputs for each input. We have evaluated all of the submitted outputs using BLEU and NIST scores and we are currently in the process of collecting human judgements for the final system outputs that were ranked first. Table 1 shows the overall results of automatic evaluation on both the initial and final data sets for our three teams3 , as well as the coverage of the individual systems over the 72 test inputs. More detail including the full results of our evaluation can be found at http: //www.kbgen.org, along with a link to download

Figure 2 :

 2 Figure 2: Input for the sentence "Mucus is secreted in the alimentary canal of earthworms."

Table 1 :

 1 BLEU and NIST scores of initial and final system outputs. The digit behind the team names refer to the output rank the development and test data set used in the challenge, and more information about AURA and related resources.

		NIST BLEU coverage
	HUMAN-1 10.0098 1.0000	100%
	UDEL-final-1	5.9749 0.3577	97%
	UDEL-initial-1	5.6030 0.3165	100%
	LOR-final-1	4.8569 0.3053	84%
	LOR-final-3	4.7238 0.2993	100%
	LOR-final-2	4.6711 0.2945	100%
	LOR-final-5	4.5720 0.2812	100%
	LOR-final-4	4.4889 0.2781	100%
	IMS-final-2	3.9649 0.1107	100%
	IMS-final-4	3.8813 0.1140	100%
	IMS-final-1	3.8670 0.1111	100%
	IMS-final-3	3.7765 0.1023	100%
	IMS-initial-2	3.6726 0.1117	100%
	IMS-initial-3	3.6608 0.1181	100%
	IMS-initial-1	3.6384 0.1173	100%
	IMS-initial-4	3.5817 0.1075	100%
	LOR-initial-1	0.1206 0.0822	30%
	LOR-initial-3	0.1091 0.0751	100%
	LOR-initial-4	0.0971 0.0732	100%
	LOR-initial-2	0.0948 0.0757	100%
	LOR-initial-5	0.0881 0.0714	100%

http://www.kbgen.org

http://www.ai.sri.com/halo/ halobook2010/exported-kb/biokb.html

IMS: Stuttgart University Institute for Computational Language Processing, LOR: LORIA, University of Nancy, UDEL: University of Delaware, Computer and Information Science Department

The work reported in this paper was supported by funding from Vulcan, Inc.