Tracking the Best Expert.
We generalize the recent relative loss bounds for on-line algorithms where the additional loss of the algorithm on the whole sequence of examples over the loss of the best expert is bounded. The generalization allows the sequence to be partitioned into segments, and the goal is to bound the additional loss of the algorithm over the sum of the losses of the best experts for each segment. This is to model situations in which the examples change and different experts are best for certain segments of the sequence of examples. In the single segment case, the additional loss is proportional to log n, where n is the number of experts and the constant of proportionality depends on the loss function. Our algorithms do not produce the best partition; however the loss bound shows that our predictions are close to those of the best partition. When the number of segments is k+1 and the sequence is of length &ell;, we can bound the additional loss of our algorithm over the best partition by O(k \log n+k \log(&ell;/k)). For the case when the loss per trial is bounded by one, we obtain an algorithm whose additional loss over the loss of the best partition is independent of the length of the sequence. The additional loss becomes O(k\log n+ k \log(L/k)), where L is the loss of the best partitionwith k+1 segments. Our algorithms for tracking the predictions of the best expert aresimple adaptations of Vovk's original algorithm for the single best expert case. As in the original algorithms, we keep one weight per expert, and spend O(1) time per weight in each trial.
Introduction
Consider the following on-line learning model. The learning occurs in a series of
trials labeled In each trial t the goal is to predict the outcome y t 2 [0; 1]
which is received at the end of the trial. At the beginning of trial t, the algorithm
receives an n-tuple x t . The element x t;i 2 [0; 1] of the n-tuple x t represents the
prediction of an expert E i of the value of the outcome y t on trial t. The algorithm
then produces a prediction -
based on the current expert prediction tuple x t , and
on past predictions and outcomes. At the end of the trial, the algorithm receives the
outcome y t . The algorithm then incurs a loss measuring the discrepancy between
the prediction -
y t and the outcome y t . Similarly, each expert incurs a loss as well.
A possible goal is to minimize the total loss of the algorithm over all ' trials on
an arbitrary sequence of instance outcome pairs (such pairs are called examples).
Since we make no assumptions about the relationship between the prediction of
experts and the outcome (y t ), there is always some sequence of y t that is
* The authors were supported by NSF grant CCR-9700201. An extended abstract appeared in
(Herbster & Warmuth, 1995)
M. HERBSTER AND M. K. WARMUTH
"far away" from the predictions - y t of any particular algorithm. Thus, minimizing
the total loss over an arbitrary sequence of examples is an unreasonable goal. A
refined relativized goal is to minimize the additional loss of the algorithm over the
loss of the best expert on the whole sequence. If all experts have large loss then
this goal might actually be easy to achieve, since for all algorithms the additional
loss over the loss of the best expert may then be small. However, if at least one
expert predicts well, then the algorithm must "learn" this quickly and produce
predictions which are "close" to the predictions of the best expert in the sense that
the additional loss of the algorithm over the loss of the best expert is bounded.
This expert framework might be used in various settings. For example, the experts
might predict the chance of rain or the likelihood that the stock market will rise or
fall. Another setting is that the experts might themselves be various sub-algorithms
for recognizing particular patterns. The "master" algorithm that combines the
experts' predictions does not need to know the particular problem domain. It simply
keeps one weight per expert, representing the belief in the expert's prediction, and
then decreases the weight as a function of the loss of the expert.
Previous work of Vovk (Vovk, 1998) and others (Littlestone & Warmuth, 1994;
Haussler, Kivinen & Warmuth, 1998) has produced an algorithm for which there
is an upper bound on the additional loss of the algorithm over the loss of the best
expert. Algorithms that compare against the loss of the best expert are called
Static-expert algorithms in this paper. The additional loss bounds for these
algorithms have the form c ln n for a large class of loss functions, where c is a
constant which only depends on the loss function L, and n is the number of experts.
This class of loss functions contains essentially all common loss functions except for
the absolute loss and the discrete loss 1 (counting prediction mistakes), which are
treated as special cases (Littlestone & Warmuth, 1994; Vovk, 1995; Cesa-Bianchi,
Freund, Haussler, Helmbold, Schapire & Warmuth, 1997). For example, if the loss
function is the square or relative entropy loss, then
respectively
(see Section 2 for definitions of the loss functions).
In the paper we consider a modification of the above goal introduced by Littlestone
and Warmuth (Littlestone & Warmuth, 1994), in which the sequence of examples is
subdivided into k segments of arbitrary length and distribution. Each segment
has an associated expert. The sequence of segments and its associated sequence of
experts is called a partition. The loss of a partition is the sum of the total losses
of the experts associated with each segment. The best partition of size k is the
partition with k segments that has the smallest loss. The modified goal is to
perform well relative to the best partition of size k. This goal is to model real life
situations where the "nature" of the examples might change and a different expert
produces better predictions. For example, the patterns might change and different
sub-algorithms may predict better for different segments of the on-line sequence
of patterns. We seek to design master algorithms that "track" the performance of
the best sequence of experts in the sense that they incur small additional loss over
the best partition of size k. If the whole sequence of examples was given ahead of
time, then one could compute the best partition of a certain size and the associated
experts using dynamic programming. Our algorithms get the examples on-line and
never produce the best partition. Even so, we are able to bound the additional loss
over the best off-line partition for an arbitrary sequence of examples.
When there are ' trials, k experts, there are
distinct partitions. We can immediately get a good bound for this problem by
expanding the set of n experts into
experts." Each partition-expert represents a single partition of the trial sequence,
and predicts on each trial as the expert associated with the segment which contains
the current trial. Thus, using the Static-expert algorithm we obtain a bound
of c ln
of the additional loss of the
algorithm over the loss of the best partition. There are two problems: first, the
algorithm is inefficient, since the number of partition-experts is exponential in the
number of partitions; and second, the bound on the additional loss grows with the
sequence length.
We were able to overcome both problems. Instead of keeping one weight for
the exponentially many partitions, we can get away with keeping only one weight
per expert, as done in the Static-expert algorithm. So the "tracking" of the
predictions of the best partition is essentially for free. If there are n sub-algorithms
or experts whose predictions we want to combine, then as in the Static-expert
algorithm the new master algorithm takes only O(n) additional time per trial over
the time required for simulating the n sub-algorithms.
We develop two main algorithms: the Fixed-share Algorithm, and the Variable-
share Algorithm. Both of these are based on the Static-expert algorithms which
maintain a weight of the form e \GammajT i for each expert (cf. Littlestone & Warmuth,
1994; Vovk, 1995), where T i is total past loss of the expert i in past trials. In
each trial the master algorithm combines the experts' predictions using the current
weights of the experts. When the outcome of the trial is received, we multiply the
weight of every expert i by e \GammajL i , where L i is the loss of expert i in the current
trial. We call this update of the weights the Loss Update.
We modify the Static-expert Algorithm by adding an additional update to
obtain our algorithms. Since in our model the best expert may shift over a series of
trials, we cannot simply use weights of the form e \GammajT i , because before an expert is
optimal for a segment its loss in prior segments may be arbitrarily large, and thus
its weight may become arbitrarily small. So we need to modify the Static-expert
Algorithm so that small weights can be recovered quickly.
For this reason, each expert "shares" a portion of its weight with the other experts
after the Loss Update; we call this the Share Update. Both the Fixed-share and
Variable-share Algorithm first do the Loss Update followed by a Share Update,
which differs for each algorithm. In a Share Update, a fraction of each experts'
weight is added to the weight of each other expert. In the Fixed-share Algorithm
the experts share a fixed fraction of their weights with each other. This guarantees
that the ratio of the weight of any expert to the total weight of all the experts
may be bounded from below. Different forms of lower bounding the weights have
been used by the Wml algorithm and in the companion paper for learning shifting
disjunctions (Auer & Warmuth, 1998) that appears in this journal issue. The latter
two methods have been applied to learning problems where the loss is the discrete
4 M. HERBSTER AND M. K. WARMUTH
loss (i.e. counting mistakes). In contrast our methods work for the same general
class of continuous loss functions that the Static-expert algorithms can handle
(Vovk, 1998; Haussler et al., 1998). This class includes all common loss functions
such as the square loss, the relative entropy loss, and the hellinger loss. For this
class there are tight bounds on the additional loss (Haussler et al., 1998) of the
algorithm over the loss of the best expert (i.e., the non-shifting case). The Fixed-
share Algorithm obtains the additional loss of O(c[(k+1) log n+k log '
k +k]), which
is essentially the same as the sketched algorithm that uses the Static-expert
algorithm with exponentially many partition-experts. The salient feature of the
Fixed-share Algorithm is that it still uses O(1) time per expert per trial. However,
this algorithm's additional loss still depends on the length of the sequence. Our
lower bounds give some partial evidence that this seems to be unavoidable for loss
functions for which the loss in a single trial can be unbounded (such as for the
relative entropy loss). For the case when the loss in a particular trial is at most one
(such as for the square loss), we develop a second algorithm called the Variable-
share Algorithm. This algorithm obtains bounds on the additional loss that are
independent of the length of the sequence. It also shares weights after the Loss
Update; however, the amount each expert shares now is commensurate with the
loss of the expert in the current trial. In particular, when an expert has no loss, it
does not share any weight.
Both versions of our Share Update are trivial to implement and cost a constant
amount of time for each of the n weights. Although the algorithms are easy to
describe, proving the additional loss bounds takes some care. We believe that our
techniques constitute a practical method for tracking the predictions of the best
expert with provable worst-case additional loss bounds. The essential ingredient for
our success in a non-stationary setting, seems to be an algorithm for the stationary
setting with a multiplicative weight update whose loss bound grows logarithmically
with the dimension of the problem. Besides Vovk's Aggregating Algorithm
(Vovk, 1998) and the Weighted Majority Algorithm (Littlestone & Warmuth,
1994), which only use the Loss Update, and are the basis of this work, a number
of such algorithms have been developed. Examples are algorithms for learning
linear threshold functions (Littlestone, 1988; Littlestone, 1989), and algorithms
whose additional loss bound over the loss of the best linear combination of experts
or sigmoided linear combination of experts is bounded (Kivinen & Warmuth,
1997; Helmbold, Kivinen & Warmuth, 1995). Significant progress has recently been
achieved for other non-stationary settings building on the techniques developed in
this paper (see discussion in the Conclusion Section).
The paper is outlined as follows. After some preliminaries (Section 2), we present
the algorithms (Section 3), and give the basic proof techniques (Section 4). Sections
5 and 6 contain the detailed proofs for the Fixed-share and Variable-
share algorithms, respectively. The absolute loss is treated as a special case in
Section 7. Section 8 discusses a subtle but powerful generalization of the Variable-
share Algorithm, called the Proximity-variable-share Algorithm. The generalization
leads to improved bounds for the case when best expert of the next
segment is always likely to be "close" to the previous expert. Some preliminary
lower bounds are given in Section 9. Simulation results on artificial data that exemplify
our methods are given in Section 10. Finally, in Section 11 we conclude
with a discussion of recent work. The casual reader who might not be interested in
the detailed proofs is recommended to read the sections containing the preliminaries
(Section 2), the algorithms (Section 3) and the simulations (Section 10).
2. Preliminaries
Let ' denote the number of trials and n denote the number of experts labeled
When convenient we simply refer to an expert by its index; thus
"expert i" refers to expert E i . The prediction of all n experts in trial t is referred
to by the prediction tuple x t , while the prediction of expert i on trial t is denoted
by x t;i : These experts may be viewed as oracles external to the algorithm, and thus
may represent the predictions of a neural net, a decision tree, a physical sensor or
perhaps even of a human expert. The outcome of a trial t is y t , while the prediction
of the algorithm in trial t is - y t . The instance-outcome pair called the t-th
example. In this paper the outcomes, the expert predictions and the predictions of
the algorithm are all in [0; 1]. Throughout this paper S always denotes an arbitrary
sequence of examples, i.e. any sequence of elements from [0; 1] n \Theta [0; 1] of any length
'. A loss function L(p; q) is a function We consider four
loss functions in this paper: the square, the relative entropy, the hellinger, and the
absolute loss:
ent (p;
hel (p;
On trial t the loss of the algorithm A is L(y
Similarly, the loss of expert i
on trial t is L(y t ; x t;i ). We call a subsequence of contiguous trials a segment. The
notation non-negative integers t - t 0 denotes a segment starting on trial
number t and ending on the trial t 0 . Rounded parens are used if the ending trial
is not included in the segment. For the current sequence S we abbreviate the loss
of expert i on the segment [t::t 0 ) by L([t::t 0
The loss of the
algorithm A over the whole trial sequence S is defined as L(S;
We are now ready to give the main definition of this paper that is used for
scenarios in which the best expert changes over time. Informally a k-partition
slices a sequence into k segments with an expert being associated with each
segment. Formally, a k-partition, denoted by P ';n;k;t;e (S), consists of three positive
integers '; n; k; and two tuples t and e of positive integers. The number ' is the
length of the trial sequence S, n is the size of the expert pool, and k is number of
target shifts '). The tuple t has k elements
and Each t i refers to one of the ' trials, and by convention we use
1: The tuple t divides the trial sequence S into
6 M. HERBSTER AND M. K. WARMUTH
Parameters:
Initialization: Initialize the weights to w s
t;i . Predict with
Loss Update: After receiving the tth outcome y t ,
Share Updates of all three algorithms:
Static-expert
t;i "no Share Update"
Fixed-share (4)
Variable-share (5)

Figure

1. The Static-expert, Fixed-share, and Variable-share algorithms
called the ith segment. The
0th segment is also referred to as the initial segment. The tuple e has k+1 elements
. The element e i denotes the
expert which is associated with the ith segment [t i ::t i+1 ). The loss of a given
k-partition for loss function L and trial sequence S is
3. The Algorithms
There are four algorithms considered in this paper - Static-expert, Fixed-
share, Variable-share and Proximity-variable-share. The first three are
summarized in Figure 1. The Proximity-variable-share Algorithm is a generalization
of the Variable-share Algorithm; this algorithm is given in Figure 3.
The discussion of this generalization is deferred to Section 8. For all algorithms the
learning process proceeds in trials, where t - 1 denotes the trial number. The algo-
rithms maintain one positive weight per expert. The weight w s
t;i (or its normalized
version v s
should be thought of as a measurement of the algorithm's belief in the
quality of the ith expert's predictions at the start of trial t. The weight of each
expert is initialized to 1=n.
The algorithms have the following three parameters: j; c and ff. The parameter
j is a learning rate quantifying how drastic the first update will be. The parameter
c will be set to 1=j for most loss functions. (The absolute loss is an exception
treated separately in Section 7.) The parameter ff quantifies the rate of shifting
that is expected to occur. The Fixed-share Algorithm is designed for potentially
unbounded loss functions, such as the relative entropy loss. The Variable-share
Algorithm assumes that the loss per trial lies in [0; 1]. For the Fixed-share Al-
gorithm, ff is the rate of shifting per trial. Thus, if five shifts are expected in a
1000 trial sequence, then 1=200. For the Variable-share Algorithm, ff is
approximately the rate of shifting per unit of loss of the best partition. That is, if
five shifts are expected to occur in a partition with a total loss of 80, then ff - 1=16.
The tunings of the parameters j and c are considered in greater depth in Section 4,
and for ff in sections 5 and 6. Finally, the Static-expert Algorithm does not use
the parameter ff since it assumes that no shifting occurs.
In each trial t the algorithm receives an instance summarizing the predictions of
the n experts x t . The algorithm then plugs the current instance x t and normalized
weights v t into the prediction function pred(v; x) in order to produce a prediction
y t . In the simplest case, the algorithm predicts with the weighted mean of the
experts' predictions, i.e., pred(v; more sophisticated prediction
function introduced by Vovk (Vovk, 1998) will be discussed in Section 4. After
predicting, the algorithm performs two update steps. The first update is the Loss
Update; the second is the Share Update.
In the Loss Update the weight of expert i is multiplied by e \GammajL i , where L i is the
loss of the i-th expert in the current trial. Thus, no update occurs when L
The learning rate j intensifies the effect of this update. We use w m
t;i to denote
the weights in the middle of the two updates. These weights will be referred to
as intermediate weights. The Share Update for the Static-expert Algorithm is
vacuous. However, for the other algorithms the Share Update is crucial. We briefly
argue for the necessity of the share updates in the non-stationary setting, and then
give an intuitive description of how they function.
When we move from predicting as well as the best expert to predicting as well as
a sequence of experts, the Loss Update is no longer appropriate as the sole update.
Assume we have two experts and two segments. In the first segment Expert 1 has
small loss and Expert 2 a large loss. The roles are reversed for the second segment.
By the end of the first segment, the Loss Update has caused the weight of Expert 2
to be almost zero. However, during the second segment the predictions of Expert 2
are important, and its weight needs to be recovered quickly. The share updates
make sure that this is possible. The simulation in Section 10 furthers the intuition
for why the share updates are needed. The two share updates are summarized
8 M. HERBSTER AND M. K. WARMUTH
below. A straightforward implementation costs O(n) time per expert per trial:
Fixed-share: w s
ff
Variable-share: w s
In contrast, the implementations in Figure 1, that use the intermediate variable
"pool" cost O(1) time per expert per trial. After the Loss Update, every expert
"shares" a fraction of its weight equally with every other expert. The received
weight enables an expert to recover its weights quickly relative to the other experts.
In the Fixed-share Update (6) each expert shares a fraction of ff of its weight in
each trial. If one expert is perfect for a long segment, this type of sharing is not
optimal, since the perfect expert keeps on sharing weight with possible non-perfect
experts. The Variable-share Update (7) is more sophisticated: roughly, an expert
shares weight when its loss is large. A perfect expert doesn't share, and if all other
experts have high loss, it will eventually collect all the weight. However, when a
perfect expert starts to incur high loss, it will rapidly begin to share its weight with
the other experts, allowing a now good expert with previously small relative weight
to recover quickly. As discussed above the parameter ff is the shifting rate.
In the introduction we discussed an algorithm that uses exponentially many static
experts, one for each partition. Our goal was to achieve bounds close to those of
this inefficient algorithm by using only n weights. The bounds we obtain for our
share algorithms are only slightly weaker than the partition-expert algorithm and
gracefully degrade when neither the length of the sequence ' nor the number of
shifts k are known in advance.
4. Prediction Functions and Proof Techniques
We consider two choices of prediction functions. The simplest prediction is the
weighted mean (Warmuth, 1997):
pred wmean (v;
A more sophisticated prediction function giving slightly better bounds was introduced
by Vovk (Vovk, 1998; Haussler et al., 1998). Define L 0
z). Both of these functions must be monotone. Let L \Gamma1
1 (z) denote the inverses of L 0 (z) and L 1 (z). Vovk's prediction is now defined in
two steps by
pred Vovk (v;
Loss c values: (j = 1=c)
Functions: pred wmean (v; x) pred Vovk (v; x)
ent (p;
hel (p; q) 1 1=
Figure

2. (c; 1=c)-realizability: c values for loss and prediction function pairings.
The following definition is a technical condition on the relation between the prediction
function pred(v; x), the loss function L, and the constants c and j.
et al., 1998; Vovk, 1998) A loss function L and prediction
function pred are (c; j)-realizable for the constants c and j if
for all
of total weight 1.
We consider four loss functions in this paper: the square, the relative entropy,
the hellinger, and the absolute loss (see Section 2). However, the algorithms are
not limited to these loss functions. The techniques in (Vovk, 1998; Haussler et
al., 1998; Warmuth, 1997) can determine the constants c and j for a wide class
of loss functions. The algorithm is also easy to adapt for classification by using
the majority vote (Littlestone & Warmuth, 1994) for the prediction function, and
counting mistakes for the loss. In a practical application, no worst-case loss bounds
may be provable for the given loss function. However, the share updates may still
be useful. For an interesting application to the prediction of disk idle time see the
work of Helmbold et al. (Helmbold, Long & Sherrod, 1996).
The square, relative entropy and hellinger losses are (c; j)-realizable for both
pred wmean and pred Vovk with (j = 1=c). The values of c (and hence of
the two prediction functions are summarized in Figure 2. Since the absolute loss
has more complex bounds, we treat it in a section of its own. A smaller value of
c leads to a smaller loss bound (see Lemma 1). The c values for pred Vovk (cf.
column two of Figure 2) are optimal for a large class of loss functions (Haussler et
al., 1998).
The proof of the loss bounds for each of the algorithms is based on the following
lemma. The lemma embodies a key feature of the algorithms: the prediction is
done such that the loss incurred by the algorithm is tempered by a corresponding
change in total weight. This lemma gives the same inequality as the lemmas used
in (Vovk, 1998; Haussler et al., 1998). The proof here is essentially the same, since
the share updates do not change the total weight W
t;i .
Haussler et al., 1998) For any sequence of examples
S and for any expert i, the total loss of the master algorithms in Figure 1 may be
M. HERBSTER AND M. K. WARMUTH
bounded by
when the loss function L and prediction function pred is (c; j)-realizable (cf. Definition
1 and Figure 2).
Proof: Since L and pred are (c; j)-realizable, we have by Definition 1 that
Since the share updates do not change, the total weight
t;i is
W t+1 . This implies that
Hence, since W
So far we have used the same basic technique as in (Littlestone & Warmuth, 1994;
Vovk, 1995; Cesa-Bianchi et al., 1997; Haussler et al., 1998), i.e., c ln W t becomes
the potential function in an amortized analysis. In the static expert case (when
1=c) the final weights have the form w s
=n. Thus the above
lemma leads to the bound
relating the loss of the algorithm to the loss of any static expert.
The share updates make it much more difficult to lower bound the final weights.
Intuitively, there has to be sufficient sharing so that the weights can recover quickly.
However, there should not be too much sharing, so that the final weights are not
too low. In the following sections we bound final weights of individual experts
in terms of the loss of a partition. The loss of any partition (L(P ';n;k;t;e (S))) is
just the sum of the sequence of losses defined by the sequence of experts in the
partition. When an expert accumulates loss over a segment, we bound its weight
using Lemma 2 for the Fixed-share Algorithm and Lemma 7 for the Variable-
share Algorithm. Since a partition is composed of distinct segments, we must also
quantify how the weight is transferred from the expert associated with a segment
to the expert associated with the following segment; this is done with Lemma 3 for
the Fixed-share Algorithm and Lemma 8 for the Variable-share Algorithm.
The lower bounds on the weights are then combined with Lemma 1 to bound the
total loss of the Fixed-share Algorithm (Theorem 1) and the Variable-share
Algorithm (Theorem 2).
5. Fixed-share Analysis
This algorithm works for unbounded loss functions, but its total additional loss
grows with the length of the sequence.
Lemma 2 For any sequence of examples S the intermediate weight of expert i on
trial t 0 is at least e \GammajL([t::t 0 ];i) times the weight of expert i at the start
of trial t, where t - t 0 . Formally we have
Proof: The combined Loss and Fixed-share Update (Equation (6)) can be rewritten
as
Then if we drop the additive term produced by the Share Update, we have
We apply the above iteratively on the trials [t::t 0 ). Since we are bounding w m
weights in trial t 0 after the Loss Update), the weight on trial t 0 is only reduced by
a factor of e \GammajL(y t 0 ;x t 0 ;i ) . Therefore we have
Y
r=t
By simple algebra and the definition of L([a::b]; i) the bound of the lemma follows.
Lemma 3 For any sequence of examples S, the weight of an expert i at the start
of trial 1 is at least ff
times the intermediate weight of any other expert j on
trial t.
Proof: Expanding the Fixed-share Update (4) we have
Thus w s
ff
and we are done.
We can now bound the additional loss.
M. HERBSTER AND M. K. WARMUTH
Theorem 1 Let S be any sequence of examples and let L and pred be (c; j)-
realizable. Then for any k-shift sequence partition P ';n;k;t;e (S) the total loss of the
Fixed-share Algorithm with parameter ff satisfies
Proof: Recall that e k is the expert of the last segment. By Lemma 1, with
we have
We bound w s
'+1;ek by noting that it "follows" the weight in an arbitrary partition.
This is expressed in the following telescoping product:
Y
Thus, applying lemmas 3 and 2, we have
Y
The final term w s
equals one, since we do not apply the Share Update on
the final trial; therefore by the definition of L(P ';n;k;t;e (S)), we have
e \GammajL(P ';n;k;t;e
We then substitute the above bound on w s
'+1;ek into (16) and simplify to obtain (15).
The bound of Theorem 1 holds for all k, and there is a tradeoff between the terms
ck ln n and cjL(P ';n;k;t;e (S)); i.e., when k is small the ck ln n term is small and the
cjL(P ';n;k;t;e (S)) term is large, and vice-versa. The optimal choice of ff (obtained
by differentiating the bound of Theorem 1) is ff
. The following corollary
rewrites the bound of Theorem 1 in terms of the optimal parameter choice ff   . The
corollary gives an interpretation of the theorem's bound in terms of code length.
We introduce the following notation. Let
1\Gammap be the
binary entropy measured in nats, and
1\Gammaq be the binary
relative entropy in nats. 2
Corollary 1 Let S be any sequence of examples and let L and pred be (c; j)-
realizable. Then for any k-shift sequence partition P ';n;k;t;e (S) the total loss of the
Fixed-share Algorithm with parameter ff satisfies
ck
where ff
. When
, then this bound becomes
For the interpretation of the bound we ignore the constants c, j and the difference
between nats and bits. The terms ln n and k ln(n \Gamma 1) account for encoding the
experts of the partition: log n bits for the initial expert and log(n \Gamma 1) bits
for each expert thereafter. Finally, we need to encode where the k shifts occur (the
inner boundaries of the partition). If ff   is interpreted as the probability that a shift
occurs on any of the '\Gamma1 trials, then the term ('\Gamma1) [H(ff   ) +D(ff   kff)] corresponds
to the expected optimal code length (see Chapter 5 of (Cover & Thomas, 1991))
if we code the shifts with the estimate ff instead of the true probability ff   . This
bound is thus an example of the close similarity between prediction and coding as
brought out by many papers (e.g. (Feder, Merhav & Gutman, 1992)).
Note that the ff that minimizes the bound of Theorem 1 depends on k and ' which
are unknown to the learner. In practice a good choice of ff may be determined
experimentally. However, if we have an upper bound on ' and a lower bound on k
we may tune ff in terms of these bounds.
Corollary 2 Let S be any sequence of examples and -
' and -
k be any positive
integers such that -
1. Then by setting
1), the loss of the Fixed-
share Algorithm can be bounded by
where P ';n;k;t;e (S) is any partition of S such that ' -
' and k - k.
Proof: Recall the loss bound given in Theorem 1. By setting
, we have
We now separate out the term
apply the inequality
The last inequality follows from the condition that ' -
' and -
We obtain the
bound of the corollary by replacing
in Equation (20) by
its upper bound - k. 3
14 M. HERBSTER AND M. K. WARMUTH
6. Variable-share analysis
The Variable-share algorithm assumes that the loss of each expert per trial lies
in [0; 1]. Hence the Variable-share Algorithm works in combination with the
square, hellinger, or absolute loss functions but not with the relative entropy loss
function. The Variable-share Algorithm has an upper bound on the additional
loss of the algorithm which is independent of the length of the trial sequence. We
will abbreviate w s
t;i with w t;i , since in this section we will not need to refer to the
weight of an expert in the middle of a trial. We first give two technical lemmas
that follow from convexity in r of fi r .
c). Applying the first inequality of Lemma 4 to the
RHS we have c + db d - b 1\Gammac , and thus
Lemma 6 At the beginning of trial t +1, we may lower bound the weight of expert i
by either Expression (a) or Expression (b), where j is any expert different from i:
ae w t;i e \GammajL(y t ;x t;i
Proof: Expanding the Loss Update and the Variable-share Update for a trial (cf.
(7)) we have
Expression (a) is obtained by dropping the summation term. For Expression (b) we
drop all but one summand of the second term: w
.
We then apply Lemma 4 and obtain (b).
Lemma 7 The weight of expert i from the start of trial t to the start of trial t 0 ,
reduced by no more than a factor of [e \Gammaj
\Theta
Proof: From Lemma 6(a), we have that on trial t the weight of expert i is reduced
as follows: w t+1;i
we apply this iteratively on the
Y
r=t
\Theta
In Lemma 6(b) we lower bound the weight transferred from expert p to expert
q in a single trial. In the next lemma we show how weight is transferred over a
sequence of trials.
Lemma 8 For any distinct experts p and q, if L([t::t 0
2, then on trial t may lower bound the weight of expert q by
- \Theta e \Gammaj
Proof: As expert p accumulates loss in trials t::t 0 , it transfers part of its weight
to the other specifically to expert q, via the Variable-share Update.
Let a i , for t - i - t 0 , denote the weight transferred by expert p to expert q in trial
i=t a i denote the total weight transferred from expert p to expert q
in trials [t::t 0 ]: The transferred weight, however, is still reduced as a function of the
loss of expert q in successive trials. By Lemma 7, the weight a i added in trial i is
reduced by a factor of [e \Gammaj
during
a i
\Theta
We lower bound each factor [e \Gammaj
by [e \Gammaj
, and thus
\Theta e \Gammaj
To complete the proof of the lemma we still need to lower bound the total transferred
weight A by w t;p ff
l i be the loss of expert p on trial i, i.e.
From our assumption, we have 1 -
2.
By direct application of Lemma 6(b), the weight a t transferred by expert p to
expert q in the first trial t of the segment is at least w t;p ff
l t e \Gammajl t . Likewise, we
apply Lemma 7 over trials [t::i) to expert p, and then apply Lemma 6(b) on trial i.
This gives us a lower bound for the transferred weights a i and the total transferred
weight A:
a
ff
a
ff
l
M. HERBSTER AND M. K. WARMUTH
We split the last sum into two terms:
ff
l
ff
We upper bound all exponents of (1 \Gamma ff) by one; we also replace the sum in the first
exponent by its upper bound,
. The substitutions
1, and then lead to an application of Lemma 5. Thus we rewrite the
above inequality as
ff
\Theta

ff
and then apply Lemma 5. This gives us
ff
The proof of the loss bound for the Variable-share Algorithm proceeds analogously
to the proof of the Fixed-share Algorithm's loss bound. In both cases
we "follow" the weight of a sequence of experts along the sequence of segments.
Within a segment we bound the weight reduction of an expert with Lemma 2 for
the Fixed-share analysis and Lemma 7 for Variable-share analysis.
When we pass from one segment to the next, we bound the weight of the expert
corresponding to the new segment by the weight of the expert in the former
segment with lemmas 3 and 8, respectively. The former lemma used for the Fixed-
share Algorithm is very simple, since in each trial each expert always shared a
fixed fraction of its weight. However, since the weight was shared on every trial,
this produced a bound dependent on sequence length. In the Variable-share
Algorithm we produce a bound independent of the length. This is accomplished
by each expert sharing weight in accordance to its loss. However, if an expert
does not accumulate significant loss, then we cannot use Lemma 8 to bound the
weight of the following expert in terms of the previous expert. Nevertheless, if
the former expert does not make significant loss in the current segment, this implies
that we may bound the current segment with the former expert by collapsing
the segments together. In other words, the collapsing of two consecutive segments
([t creates a single segment ([t which is associated with
the expert of the first segment of the original two consecutive segments. We can do
this for any segment; thus we determine our bound in terms of the related collapsed
partition whose loss is not much worse.
Lemma 9 For any partition P ';n;k;t;e (S) there exists a collapsed partition P ';n;k 0
such that for each segment (except the initial segment), the expert associated with
the prior segment incurs at least one unit of loss, and the loss on the whole sequence
of the collapsed partition exceeds the loss of the original partition by no more than
the following properties hold:
Proof: Recall that e i is the expert associated with the ith segment, which is
comprised of the trials [t i ::t i+1 If in any segment i, the loss of the expert e
associated with the prior segment (i \Gamma 1) is less than one, then we merge segment
segment i. This combined segment in the new partition is associated with
expert e i\Gamma1 . Formally in each iteration, we decrement k by one, and we delete e i and
t i from the tuples e and t. We continue until (24) holds. We bound the loss of the
collapsed partition P ';n;k 0 by noting that the loss of the new expert on the
subsumed segment is at most one. Thus per application of the transformation, the
loss increases by at most one. Thus since there are applications, we are done.
Theorem 2 4 Let S be any sequence of examples, let L and pred be (c; j)-realizable,
and let L have a [0,1] range. Then for any partition P ';n;k;t;e (S) the total loss of
the Variable-share algorithm with parameter ff satisfies
Proof: By Lemma 1 with
Let P ';n;k;t;e (S) be an arbitrary partition. For this proof we need the property
that the loss in each segment (except the initial segment), with regard to the expert
associated with the prior segment, is at least one (cf (24)). If this property does not
hold, we use Lemma 9 to replace P ';n;k;t;e (S) by a collapsed partition P ';n;k 0
for which the property does hold. If the property holds already for P ';n;k;t;e (S), then
for notational convenience we will refer to P ';n;k;t;e (S) by P ';n;k 0 Recall that
the loss of exceeds the loss of P ';n;k;t;e (S) by no more than
Since (24) holds, there exists a trial q i in the ith segment (for 1
that L([t 0
1. We now express w '+1;e 0
as
the telescoping product
Y
Applying lemmas 7 and 8 we have
ii
ff
M. HERBSTER AND M. K. WARMUTH
which simplifies to the following bound:
ff
The last inequality follows from (25). Thus if we substitute the above bound on
simplify, we obtain the bound of the theorem.
Again we cannot optimize the above upper bound as a function of ff, since k and
L(P ';n;k;t;e (S)) are not known to the learning algorithm. Below we tune ff based on
an upper bound of L(P ';n;k;t;e (S)). The same approach was used in Corollary 2. 5
Corollary 3 Let S be any sequence of examples and -
L and - k be any positive
reals. Then by setting
L , the loss of the Variable-share Algorithm can
be bounded as follows:
ck
where P ';n;k;t;e (S) is any partition such that L(P ';n;k;t;e (S)) -
L, and in addition
L.
For any partition P ';n;k;t;e (S) for which L(P ';n;k;t;e (S)) -
L, we
obtain the upper bound
ck
Proof: We proceed by upper bounding the three terms containing ff from the
bound of Theorem 2 (we use
We rewrite the above as:
We apply the identity ln(1 x and bound L(P ';n;k;t;e (S)) by -
L, giving the
following upper bound of the previous expression:
L, then -
L.
Therefore the above is upper bounded by
Using this expression to upper bound Equation (29), we obtain Equation (27).
When
L, we upper bound Equation (29) by
The first term is bounded by 1- k. The second term (2 - k+ -
is at most k ln 9
2 in the
region
thus the above is upper bounded by
We use the above expression to upper bound Equation (29). This gives us Equation
(28) and we are done.
7. Absolute Loss Analysis
The absolute loss function L abs (p; j)-realizable with both the
prediction functions pred Vovk and pred wmean ; however, cj ? 1. Thus the tuning
is more complex, and for the sake of simplicity we use the weighted mean prediction
(Littlestone & Warmuth, 1994) in this section.
Theorem 3 (Littlestone & Warmuth, 1994) For 1), the absolute
loss function L abs (p;
j)-realizable for the prediction function
pred wmean (v; x).
To obtain a slightly tighter bound we could also have used the Vee Algorithm for
the absolute loss, which is ((2
j)-realizable (Haussler et al., 1998). This
algorithm takes O(n log n) time to produce its prediction. Both the weighted mean
and the Vee prediction allow the outcomes to lie in [0; 1]. For binary outcomes with
the absolute loss, O(n) time prediction functions exist with the same realizability
criterion as the Vee prediction (Vovk, 1998; Cesa-Bianchi et al., 1997).
Unlike the (c; 1=c)-realizable loss functions discussed earlier (cf. Figure 2), the
absolute value loss does not have constant parameters, and thus it must be tuned.
In practice, the tuning of j may be produced by numerical minimization of the
upper bounds. However, we use a tuning of j produced by Freund and Schapire
Theorem 4 (Lemma 4
P and
Q.
Q), where
M. HERBSTER AND M. K. WARMUTH
We now use the above tuning in the bound for the Variable-share Algorithm
(Theorem 2).
Theorem 5 Let the loss function be the absolute loss. Let S be any sequence of
examples, and -
L and -
k be any positive reals such that k - k, L(P ';n;k;t;e (S)) -
L, and k -
L. Set the two parameters of the Variable-share algorithm ff
and j to - k
respectively, where -
k and -
k. Then the loss of the Algorithm with weighted
mean prediction can be bounded as follows:
Alternatively, let -
L and - k be any positive reals such that k - k, L(P ';n;k;t;e (S)) -
L, and k -
L. Set the two parameters of the Variable-share algorithm ff
and j to - k
respectively, where -
k and -
k. Then the loss of the Algorithm with weighted mean
prediction can be bounded as follows:
8. Proximity-variable-share Analysis
In this section we discuss the Proximity-variable-share Algorithm (see Figure
3). Recall that in the Variable-share Algorithm each expert shared a fraction
of weight dependent on its loss in each trial; that fraction is then shared
uniformly among the remaining experts. The Proximity-variable-share
Algorithm enables each expert to share non-uniformly to the other experts.
The Proximity-variable-share Update now costs O(n) per expert per trial instead
of O(1) (see Figure 3). This algorithm allows us to model situations where we have
some prior knowledge about likely pairs of consecutive experts.
Let us consider the parameters of the algorithm. The n-tuple -
contains the initial weights of the algorithm, i.e., w s
. The
Parameters:
Initialization: Initialize the weights to w s
n .
t;i . Predict with
Loss Update: After receiving the tth outcome y t ,
Proximity-variable-share Update

Figure

3. The Proximity-variable-share algorithm
second additional parameter besides j and c is a complete directed graph - of size n
without loops. The edge weight - j;k is the fraction of the weight shared by expert j
to expert k. Naturally, for any vertex, all outgoing edges must be nonnegative and
sum to one. The - 0 probability distribution is a prior for the initial expert and the
probability distribution is a prior for which expert will follow expert j. Below
is the upper bound for the Proximity-variable-share Algorithm. The Fixed-
share Algorithm could be generalized similarly to take proximity into account.
Theorem 6 Let S be any sequence of examples, let L and pred be (c; j)-realizable,
and let L have a [0,1] range. Then for any partition P ';n;k;t;e (S), the total loss of
the Proximity-variable-share Algorithm with parameter ff satisfies
Proof: We omit the proof of this bound since it is similar to the corresponding
proof of Theorem 2 for the Variable-share Algorithm: The only change is that
the 1
fractions are replaced by the corresponding - parameters.
Note that setting -
gives the previous bound for the
Variable-share Algorithm (Theorem 2). In that case the last sum is O(k ln n),
accounting for the code length of the names of the best experts (except the first
one). Using the Proximity-variable-share Algorithm we can get this last sum
to O(k) in some cases.
22 M. HERBSTER AND M. K. WARMUTH
For a simple example, assume that the processors are on a circular list and that
for the two processors of distance d from processor i, - i;i+d mod
1=d 2 . Now if the next best expert is always at most a constant away from the
previous one, then the last sum becomes O(k). Of course, other notions of closeness
and choices of the - parameters might be suitable. Note that there is a price for
decreasing the last sum: the update time is now O(n 2 ) per trial. However, if for
each expert i all arrows that end at i are labeled with the same value, then the
Share Update of the Proximity-variable-share Algorithm is still O(n).
9. Lower Bounds
The upper bounds for the Fixed-share Algorithm grow with the length of the
sequence. The additional loss of the algorithm over the loss of the best k-partition
is approximately This holds for unbounded loss functions
such as the relative entropy loss. When restricting the loss to lie in [0; 1], the
Variable-share Algorithm gives an additional loss bound of approximately
is the loss of the best k-partition and k ! L. One natural
question is whether a similar reduction is possible for unbounded loss functions. In
other words, whether for an unbounded loss function a bound of the same form is
possible with ' replaced by minf'; Lg. We give evidence to the contrary. We give
an adversary argument that forces any algorithm to make loss over
the best one-partition (for which the adversary sets In this
section we limit ourselves to giving this construction. It can easily be extended to an
adversary that forces ln(n)+ln(' \Gamma log 2 n) additional loss over the best one-partition
with n experts. By iterating the adversary, we may force
additional loss over the best k-partition. (Here we assume that log 2 (n \Gamma 1) and '
are positive integers, and '
Theorem 7 For the relative entropy loss there exists an example sequence S of
length ' with two experts such that L(P ';2;1;t;e there is a partition with a
single shift of loss 0, and furthermore, for any algorithm A,
Proof: The adversary's strategy is described in Figure 4. We use -
y t to denote
the prediction of an arbitrary learning algorithm, and L
the loss at trial t. For convenience we number the trials from
of
There are two experts; one always predicts 0 and the other always predicts 1.
The adversary returns a sequence of 0 outcomes followed by a sequence of 1 outcomes
such that neither sequence is empty. Thus, there is a single shift in the best
partition, and this partition has loss 0.
2. On trial
2 and to 1 otherwise.
(Assume without loss of generality that -
2 and thus y
3. New trial:
4. If -
'\Gammat then
5. else
Go to step 7.
then go to step 3.
7. Let y for the remaining trial(s) and exit.

Figure

4. Adversary's strategy
We now prove that L(S; thus proving the lemma. Clearly
loss of generality assume - y
. Note that the
threshold for -
y t is 1
'\Gammat . Furthermore, L ent (0; 1
and L ent (1; 1
t). Thus the conditions 4(i) and 5(i) follow. Condition 4(ii) holds by simple
induction. If a shift occurs, then Condition 5(ii) holds, since by Condition 4(ii) in
we have that
'\Gammat . Therefore, when we add L t , which
is at least ln(' \Gamma t) by Condition 5(i), we obtain Condition 5(ii) and we are done. If
Step 5 is never executed then the shift to y occurs in the last trial
Step 6 is skipped. Thus if Step 5 is never executed then
in trial (Condition 4(ii)), which is again the bound of the lemma.
We first reason that this lower bound is tight by showing that the upper bounds
of the algorithms discussed in this paper are close to the lower bound. The number
of partitions when 1). Thus we may expand the set of
experts into partition-experts as discussed in the introduction. Using
the Static-expert Algorithm with the weighted mean prediction gives an upper
bound of on the total loss of the algorithm when the loss of the
best partition is zero. This matches the above lower bound. Second, the bound of
the Fixed-share Algorithm (cf. Corollary 1) is larger than the lower bound by
'\Gamma2 ), and this additional term may be upper bounded by 1.
M. HERBSTER AND M. K. WARMUTH
total
loss
of
the
algorithms
trials
Loss of Variable Share Algorithm
Loss of Static Algorithm (Vovk)
Loss of Fix Share Algorithm
Loss of typical expert
Loss of best partition (k=3)
Variable Share Loss Bound
Fix Share Loss Bound

Figure

5. Loss of the Variable-share Algorithm vs the Static-expert Algorithm
scaled
weights

Figure

6. Relative Weights of the Variable-share Algorithm
10. Simulation Results
In this section we discuss some simulations on artificial data. These simulations are
mainly meant to provide a visualization of how our algorithms track the predictions
of the best expert and should not be seen as empirical evidence of the practical
usefulness of the algorithms. We believe that the merits of our algorithms are
more clearly reflected in the strong upper bounds we prove in the theorems of
8000.10.30.50.70.9scaled
weights
trials
Vovk Relative Weights

Figure

7. Relative Weights of the Static-expert Algorithm
the earlier sections. Simulations only show the loss of an algorithm for a typical
sequence of examples. The bounds of this paper are worst-case bounds that hold
even for adversarially-generated sequences of examples. Surprisingly, the losses
of the algorithms in the simulations with random sequences are very close to the
corresponding worst-case bounds which we have proven in this paper. Thus our
simulations show that our loss bounds are tight for some sequences.
We compared the performance of the Static-expert Algorithm to the two Share
algorithms in the following setting. We chose to use the square loss as our loss
function, because of its widespread use and because the task of tuning the learning
rate for this loss function is simple. We used the Vovk prediction function (cf.
Equation 9), and we chose accordance with Figure 2. We
considered a sequence of 800 trials with four distinct segments, beginning at trials
1, 201, 401, and 601. On each trial the outcome (y t ) was 0. The prediction tuple
contained the predictions of 64 experts. When we generated the predictions of
the 64 experts, we chose a different expert as the best one for each segment. The
best experts always have an expected loss of 1=120 per trial. The other 63 experts
have an expected loss of 1=12 per trial. At the end of each segment a new "best
expert" was chosen. Since the outcome was always 0, we generated these expected
losses by sampling predictions from a uniform random distribution on (0; 1
for the "typical" and "best" experts, respectively. Thus the expected
loss for the best 6 partition, denoted by the segment boundaries above, is 800
with a variance of oe 2 - :044. The actual loss of the best partition in the particular
simulation used for the plots was 6:47. For the Fixed-share Algorithm we tuned
f based on the values of
using the ff f
26 M. HERBSTER AND M. K. WARMUTH
tuning suggested in Corollary 1. For the Variable-share Algorithm we tuned ff v
based on the values of
using the ff v
tuning suggested in Corollary 3. Using theorems 1 and 2 we calculated a worst case
upper bound on the loss of the Fixed-share Algorithm and the Variable-share
Algorithm of 24:89 and 21:50, respectively (see "\Theta" and "+" marks in Figure 5).
The simulations on artificial data show that our worst-case bounds are rather tight
even on this very simple artificial data.
There are many heuristics for finding a suitable tuning. We used the tunings
prescribed by our theorem, but noticed that for these types of simulations the
results are relatively insensitive to the tuning of ff. For example, in calculating
ff v for the Variable-share Algorithm when -
was overestimated by 10 standard
deviations, the loss bound for our algorithm increased by only 0:02, while the actual
loss of the algorithm in the simulation increased by 0:17.
In

Figure

5, we have plotted the loss of the Static-expert Algorithm versus the
loss of the two Share algorithms. Examination of the figure shows that on the first
segment the Static-expert Algorithm performed comparably to the Share algo-
rithms. However, on the remaining three segments, the Static-expert Algorithm
performed poorly, in that its loss is essentially as bad as the loss of a "typical" expert
(the slope of the total loss of a typical expert and the Static-expert Algorithm
is essentially the same for the later segments). The Share algorithms performed
poorly at the beginning of a new segment; however, they quickly "learned" the new
"best" expert for the current segment. The Share algorithms' loss plateaued to
almost the same slope as the slope of the total loss of the best expert. The two
Share algorithms had the same qualitative behavior, even though the Fixed-share
Algorithm incurred approximately 10% additional loss over the Variable-share
Algorithm. In our simulations we tried learning rates j slightly smaller than two,
and verified that even with other choices for the learning rates, the total loss of the
Static-expert algorithm does not improve significantly.
In

Figures

6 and 7, we plotted the weights of the normalized weight vector w t
that is maintained by the Variable-share Algorithm and the Static-expert
Algorithm over the trial sequence. In Figure 6, we see that the Variable-share
Algorithm shifts the relative weights rapidly. During the latter part of each segment,
the relative weight of the best expert is almost one (the corresponding plot of the
Fixed-share Algorithm is similar). On the other hand, we see in Figure 7 that the
Static-expert Algorithm also "learned" the best expert for segment 1. However,
the Static-expert Algorithm is unable to shift the relative weight sufficiently
quickly, i.e. it takes the length of the second segment to partially "unlearn" the best
expert of the first segment. The relative weights of the best experts for segments
one and two essentially perform a "random walk" during the third segment. In
the final segment, the relative weight of the best expert for segment three also
performs a "random walk." In summary, we see these simulations as evidence that
the Fixed-share and Variable-share Updates are necessary to track shifting experts.
11. Conclusion
In this paper, we essentially gave a reduction for any multiplicative update algorithm
that works well compared to the best expert for arbitrary segments of
examples, to an algorithm that works well compared to the best partition, i.e. a
concatenation of segments. Two types of share updates were analyzed. The Fixed-
share Algorithm works well when the loss function can be unbounded, and the
Variable-share Algorithm is suitable for the case when the range of the loss lies
in [0,1]. The first method is essentially the same as the one used in the Wml algorithm
of (Littlestone & Warmuth, 1994) and a recent alternate developed in (Auer
Warmuth, 1998) for learning shifting disjunctions. When the loss is the discrete
loss (as in classification problems), then these methods are simple and effective if
the algorithm only updates after a mistake occurs (i.e., conservative updates). Our
second method, the Variable-share Update, is more sophisticated. In particular, if
one expert predicts perfectly for a while, then it can collect all the weight. However,
if this expert is starting to incur large loss, then it shares weight with the other
experts, helping the next best expert to recover its weight from zero.
The methods presented here and in (Littlestone &Warmuth, 1994) have inspired a
number of recent papers. Auer and Warmuth (1998) adapted the Winnow algorithm
to learn shifting disjunctions. Comparing against the best shifting disjunction is
more complicated than comparing against the best expert. However, since this is a
classification problem a simple Sharing Update similar to the Fixed-share Update is
sufficient. Our focus in this paper was to track the prediction of the best expert for
the same class of loss functions for which the original Static-expert Algorithm
of Vovk was developed (Vovk, 1998; Haussler et al., 1998).
Our share updates have been applied experimentally for predicting disk idle times
(Helmbold et al., 1996) and for the on-line management of investment portfolios
(Singer, 1997). In addition, a reduction has been shown between expert and metrical
task systems algorithms (Blum & Burch, 1997). The Share Update has been
used successfully in the new domain of metrical task systems. A natural probabilistic
interpretation of the Share algorithms has recently been given in (Vovk,
1997).
In any particular application of the Share algorithms, it is necessary to consider
how to choose the parameter ff. Theoretical techniques exist for the Fixed-share
Algorithm for eliminating the need to choose the value of ff ahead of time. One
method for tuning parameters (among other things) is the "specialist" framework
of (Freund, Schapire, Singer & Warmuth, 1997), even though the bounds produced
this way are not always optimal. Another method incorporates a prior distribution
on all possible values of ff. For the sake of simplicity we have not discussed these
methods (Herbster, 1997; Vovk, 1997; Singer, 1997) in this paper.
28 M. HERBSTER AND M. K. WARMUTH

Acknowledgments

We would like to thank Peter Auer, Phillip Long, Robert Schapire, and Volodya
Vovk for valuable discussions. We also thank the anonymous referees for their
helpful comments.
Notes
1. The discrete loss is defined to be
ae
2. Note that Lent (p; q). We use the D(pkq) notation here as is customary in information
theory.
3. If we replace the assumption that k - k by 2 - k - ', we obtain a bound where the final term c - k
is replaced by 2c - k:
4. Vovk has recently proved a sharper bound for this algorithm (Vovk, 1997):
ff
5. Unlike Corollary 2 we do not need a lower bound on k.
6. We call the partition described by the segment boundaries 1, 201, 401, and 601, the best
partition with respect to the tradeoff between k and L(P ';n;k;t;e (S)), as expressed implicitly
in Theorem 2.



--R

Tracking the best disjunction.


How to use expert advice.
Elements of Information Theory.
Universal prediction of individual sequences.
IEEE Transactions on Information Theory
A decision-theoretic generalization of on-line learning and an application to boosting
Using and combining predictors that specialize.
Sequential prediction of individual sequences under general loss functions.


A dynamic disk spin-down technique for mobile computing
Tracking the best expert II.

Additive versus exponentiated gradient updates for linear prediction.
Learning when irrelevant attributes abound: A new linear-threshold algorithm
Mistake Bounds and Logarithmic Linear-threshold Learning Algorithms
PhD thesis
The weighted majority algorithm.
Towards realistic and competitive portfolio selection algorithms.
A game of prediction with expert advice.
Derandomizing stochastic prediction strategies.
Predicting with the dot-product in the experts framework
--TR

--CTR
Atsuyoshi Nakamura, Learning specialist decision lists, Proceedings of the twelfth annual conference on Computational learning theory, p.215-225, July 07-09, 1999, Santa Cruz, California, United States
Jeremy Z. Kolter , Marcus A. Maloof, Using additive expert ensembles to cope with concept drift, Proceedings of the 22nd international conference on Machine learning, p.449-456, August 07-11, 2005, Bonn, Germany
V. Vovk, Probability theory for the Brier game, Theoretical Computer Science, v.261 n.1, p.57-79, 06/17/2001
Peter Auer , Manfred K. Warmuth, Tracking the Best Disjunction, Machine Learning, v.32 n.2, p.127-150, Aug. 1998
Olivier Bousquet , Manfred K. Warmuth, Tracking a small set of experts by mixing past posteriors, The Journal of Machine Learning Research, 3, 3/1/2003
Avrim Blum , Carl Burch, On-line Learning and the Metrical Task System Problem, Machine Learning, v.39 n.1, p.35-58, April 2000
Chris Mesterharm, Tracking linear-threshold concepts with Winnow, The Journal of Machine Learning Research, 4, 12/1/2003
Peter Auer, Using confidence bounds for exploitation-exploration trade-offs, The Journal of Machine Learning Research, 3, 3/1/2003
Giovanni Cavallanti , Nicol Cesa-Bianchi , Claudio Gentile, Tracking the best hyperplane with a simple budget Perceptron, Machine Learning, v.69 n.2-3, p.143-167, December  2007
Marco Barreno , Blaine Nelson , Russell Sears , Anthony D. Joseph , J. D. Tygar, Can machine learning be secure?, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
Wei Yan , Christopher D. Clack, Diverse committees vote for dependable profits, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
Mark Herbster , Manfred K. Warmuth, Tracking the best regressor, Proceedings of the eleventh annual conference on Computational learning theory, p.24-31, July 24-26, 1998, Madison, Wisconsin, United States
Claudio Gentile, The Robustness of the p-Norm Algorithms, Machine Learning, v.53 n.3, p.265-299, December
Mark Herbster , Manfred K. Warmuth, Tracking the best linear predictor, The Journal of Machine Learning Research, 1, p.281-309, 9/1/2001
Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007
experts;multiplicative updates;shifting;amortized analysis;on-line learning