Improved Regret Bounds for Tracking Experts with Memory
Authors: James Robinson
Mark Herbster
Venue: NeurIPS 2021 Poster (2021)
Keywords: online learning
prediction with expert advice

Abstract: We address the problem of sequential prediction with expert advice in a non-stationary environment with long-term memory guarantees in the sense of Bousquet and Warmuth [4]. We give a linear-time algorithm that improves on the best known regret bound [27]. This algorithm incorporates a relative entropy projection step. This projection is advantageous over previous weight-sharing approaches in that weight updates may come with implicit costs as in for example portfolio optimization. We give an algorithm to compute this projection step in linear time, which may be of independent interest.

Improved Regret Bounds for Tracking Experts with Memory
James Robinson
Mark Herbster
Department of Computer Science University College London London
Department of Computer Science University College London London
United Kingdom
United Kingdom
robinson@cs..... ucl. ac .c.uk .uk
www.seerrrrrss...mmm ucl ac uk
Abstract
We address the problem of sequential prediction with expert advice in non- stationary environment with long-term memory guarantees sense of Bousquet and Warmuth [4]. We give linear-time algorithm that improves the best known regret bounds [27]. This algorithm incorporates a relative entropy projection previous weight-sharing approaches in that weight updates may come with implicit costs as for example portfolio optimization. We give algorithm to compute this projection step in linear time, which may be of independent interest.
step. This projection is advantageous
Introduction
We consider the classic problem of online prediction with expert advice [35 in non-stationary environment. In this model nature sequentially generates outcomes which the learner attempts to predict. Before making each prediction, the learner listens a set of n experts who each make their own predictions. The learner bases its prediction on the advice of the experts. After the prediction is made and the true outcome is revealed by nature, the accuracies the learner's 's prediction and the expert predictions are measured by a loss function. The learner receives information on all expert losses on each trial. We make no distributional assumptions about the outcomes generated, indeed nature may be assumed to be adversarial. The goal of the learner is to predict well relative to predetermined comparison class of predictors, in this case the set of experts themselves. Unlike the standard regret model, where the learner's 's performance is compared to the single best predictor in hindsight, our aim for the learner to predict well relative to sequence of comparison predictors. That is, "switches" occur in the data sequence and different experts are assumed to predict well at different times.
In this work our focus is on the case when this sequence consists of few unique predictors relative the number of switches. Thus most switches return to a previously "good" expert, and a learner that can exploit this fact by "remembering" the past can adapt more quickly than a learner who has no memory and must re-learn the experts after every switch. The problem of switching with memory in online learning is part of much broader and fundamental problem in machine learning: how system can adapt to new information yet retain knowledge the past. This is an area of research in many fields, including for example, catastrophic forgetting in artificial neural networks [1]36].
Contributions. this paper we present an O(n)-time per trial projection- algorithm for which prove the best known regret bound for tracking experts with memory. Our projection-based algorithm is intimately related to a more traditional "weight-sharing" algorithm, which we show is new method for Mixing Past Posteriors (MPP) We show that surprisingly this method
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

corresponds to the algorithm with the previous best known regret bound for this problem 127. We also give an efficient (nn)-imme algorithm for computing exact relative entropy projection onto a simplex with non-uniform (lower) box constraints. Finally, we provide a guarantee which favors projection-base updates over weight-sharing updates when updating weights may incur costs.
The paper is organized as follows. We first introduce the model and discuss related work, giving a detailed overview of the previous results on which we improve. In Section [ we give our main results, regret bound which holds for two algorithms, and an algorithm to compute relative entropy projection with non-uniform lower box constraints in linear time, In Section Te derive a new "geometric-decay" method for MPP, and show the correspondence to the current best known algorithm [27]. We give few concluding remarks in Section All proofs are contained in the appendices.
1.1 Preliminaries
We first introduce notation. Let An == {u E 00, 1] ||u||| = 11 be the (n - 1)-dimensional probability simplex. Let Ag == {u E [0, a) ||u|| a} be scaled simplex. Let 1 denote the vector (1.....1) 1) and 0 denote the vector (O.....0) 0). Let e, denote the 8th standard basis vec- tor. We define Du, w) : Σi= u, log ae to be the relative entropy between u and w. We w.
denote component-wist wise multiplication as u O w == (4y (UIw)..... w,). For p E [0, 1] we de- fine H(p) == pplp (1 p) In - p) to be the binary entropy of p, using the convention that 0 0ln = O. We define to be the relative interior of the set S. For any positive integer n we define [n] : f1....,,t n). We overload notation such that [pred is equal to 1 if the predicate pred is true and 0 otherwise. For two vectors a and B we say a 3 B iff o; S 3g for all 1, I...., n.
Background
In sequential prediction with expert advice nature generates elements from an outcome space, y while the predictions of the learner and the experts are elements from a prediction space, D (e.g., we may have y = {0, 1} and D [0, 1)). Given non-negative loss function { D x ) - [0, oo). learning proceeds in trials. On each trial / = 1,..., T: 1) the learner receives the expert predictions x.' E D", 2) the learner makes a prediction j E DD, 3) nature reveals the true label y' E V, and 4) the learner suffers loss 8x == É(O²; y²) and expert i suffers loss E := l(a, y²) for consider in this paper is a weight vector, w An. where wi can be interpreted as the algorithm's is confidence in expert i on trial t. The learner uses prediction function pred A,, x D -> D to generate its prediction ÿ pred (w', x²) on trial t. A classic example is to predict with the weighted average of the expert predictions, that is. pred w", x²) w² x², although for some loss functions improved bounds different prediction functions (see e.g., (47). In this paper we assume (c, 77) -eerelizzabili of and pred [4] [8] 45.. That is, there exists constants 1] > O such that for all w A.. x D", and y V. ((pred (w, x), v) S -cIn Σ Wse (d(())))) This includes 1/exx-concave losses when pred (w", x²) w' x² and
i = ...... Common to the algorithms
obtained with
7' For simplicity we present regret bound guarantees that assume (c, -realiizabili that is en) = 1. This includes the log loss with e = 1, and the square loss with e when D y' = [0. 1]. The absolute loss is not (c. realizabee Generalizing our bounds to the Hedge setting [33 is straightforward. For any comparison sequence of experts
irr i1, .,,..... ir E [ri] the regret of the learner with respect to this sequence is defined as
T
R(iT.)
We consider and derive algorithms which belong to the family of "exponential weights" (EW) algorithms (see e.g., [25 35 After receiving the expert losses the EW algorithm applies the following incremental loss update to the expert weights,
- 79!
(1)
Σ/=1 wse 95
Static setting. In the static setting the learner competes against single expert (i.e., i iT). For the static setting the EW algorithm sets w11 = ui for the next trial, and for (c, reealzabbee losses and prediction functions achieves static regret bound of R(i..) S clun.
=

---

Switching, In the switching (without memory) setting the learner competes against a sequence of experts ",..... èT with & := - [i * i switches. The well-known Fixed-Shar algorithm 22 solves the switching problem with the update
1 = (1 (1-a) +a=
w
by forcing each expert to "share" a fraction of its weight uniformly with all experts The update is parameterized by a "switching" parameter, [0, 1]. With an optimally-tume a T-I the regret with respect to the best sequence of experts with switches is
R(ii:) S 5e 1))mn (T- 1)H T 1)
s kln
T 1 + +k)
k
Switching with memory. Freund 12] gave an open problem to improve on the regret bound (3)
when the comparison sequence of experts comprised small pool of size m == | fiel < Using counting arguments Freund gave exponential -time algorithm with the information-theoree
ideal regret bound of R(ir.) & clm ((T) (T-1 mm 1)*), which is upper-bounded by
m Ia kln T-1 + (k- 1) In + l: +
(4)
The first efficient algorithm solving Freund's problem was presented in the seminal paper [4] This work introduced the notion of a mixing scheme, which a distribution 7+1 with support (0.....(). Given y the algorithm's 's update on each trial is the mixture over all past weight vectors,
W
++ 2
(5)
q=0
where w := 11, and 7 := 1. Intuitively, by mixing all "past posteriors" (MPP) the weights of previously well-performing experts can be prevented from vanishing and recover quickly. An efficient mixing scheme requiring (nn)-time per trial is the "uniform" mixing scheme given by 7 1 and f+1 a for 0 S q < t. A better regret bound was proved with a "decaying" mixing scheme, given by
= 0
(6)
<t.
(1-2)" Ze
where Z, ==E ((-g)= normalizing factor, and p 2 0. With a tuning of - and p =
this mixing scheme achieves regret bound of
T --1 &
R(h1:) S In 2 In
+ k - +)++ +n
It appeared that to achieve the best regret bounds, the mixing scheme needed to decay towards the past. Unfortunately, computing (6) exactly requires the storage all past weights, at cost of (it))-time and space per trial. Observe that these schemes set 7t 1-a, where typically a is small, since intuitively switches are assumed to happen infrequently. All updates using such schemes are of the form
w [+1 = (1 -a)i'' + ovv"
(8)
where o' E A, is a function of the past weights ri ...,, -i We will refer to (8) as the generalized share update (see (7]). Fixed-Share special case when v' = 1 for all 1. This generalized share update features heavily in this paper.
For decade it remained an open problem to give the MPP update Bayesian interpretation. This was finally solved in [27] with the use of partition specialists. Here on each trial f, specialist
'Technically in the original Fixed-Share update each expert shares weight to all other experts, i.c., w/t (1 a.ii + ti.. The two updates achieve essentially the same regret bound and equivalent up to a scaling of a. 7 is simplitied upper bound of the bound given in 4 Corollary 9]. using In (1 S
3

---

(first introduced in (14) is either awake and predicts in accordance with a prescribed base expert, or is asleep and abstains from predicting. For n base experts and finite time horizon T there are m2 partition specialists. For Freund's problem an assembly of m partition specialists can predict exactly as the comparison sequence of experts. The Bayesian interpretation of the MPP update given in [27] Theorem 2] was simple: to define a mixing scheme y was to induce a prior over this set of partition specialists. The authors of [27] proposed a simple Markov chain prior over the set of partition specialists, giving efficient ((n) per trial algorithm with the regret bound
1 m
+ (T 1)24 T- -- + (m 1)(T 1)7 (m - 1)(T 1)
k
R(ii.)) Se
m In m
+ +m7
T 1
Sc m mn 2k In
+ (k- m + 1) In m + 2(k+
(10)
k
which is currently the best known regret bound for Freund's problem. In this work we improve on the bound (9) for tracking experts with memory (Theorem D. We also show that in fact this Markov prior on partition specialists corresponds to a geometrically-decayie
mixing scheme for MPP (Proposition 4.. The regret bounds discussed in this paper all rely on optimally tuning one or more parameters, which in practice are usually unknown, and this is true for our regret bound.
Adaptive online learning algorithms with memory have been shown to have better empirical per- formance than those without memory [5), and to be effective in real-world applications such as intrusion detection systems 33) While considerable research has been done on switching with memory in online learning (see e.g., 4 20
there remain several open problems. Firstly, there remains gap between the best known regret bound for an efficient algorithm and the information-theoretie ideal bound (4). Present in both bounds (7) and (10) is the factor of 2 in the
21 27
second term, which does not appear in (4) In 27 this was interpreted as the cost of co-ordination between specialists, essentially one "pays" twice per switch as one specialist falls asleep and another awakens. In this paper we make progress towards closing this gap by avoiding such additional costs the first time each expert is learned by the algorithm. That is, we pay to remember but not to learn.
Secondly, unless is very large the current best known bound (9) beats Fixed-Share's bound (3) only when m < k, but suffers when m is even a moderate fraction of k. A natural question is can we improve on Fixed-Share when we relax the assumption that < k, and only few members of sequence of experts need remembering (consider for instance, m > k/2/? In this paper we prove regret bound that is not only tighter than (9) for all m. but for sufficiently large n improves on Fixed-Share for all m < k. In Figure this behavior is shown for several existing regret bounds and our regret bound.
Our regret bound will hold for two algorithms; one utilizes a weight- shariig update in the sense of (8. and the other utilizes a projection update. Why should we consider projections? Consider for example a large model consisting of many weights, and to update these weights costs time and/or money. Alternatively consider the application of regret-bounded adaptive algorithms in online portfolio selection (see e.g., B2) (4 Here each "expert" corresponds to a single stock and the weight vector w' corresponds to (normalized) portfolio. If E; is the negative log return of stock after day t, then the loss function é := In Σ._ w/e-t is the negative log return of the portfolio. This loss is (1, 1)-rellizable by definition (although there is no prediction function (I), and the daily price changes in the market naturally induce the "loss update" (I) by updating the portfolio weights. The algorithm's 's secondary update (projection or weight-sharing requires the investor to then actively buy/sell to re- balance the portfolio after each trading period, but doing so may incur transaction costs proportional to the amount bought sold (see e.g.. (2] 32 ). In Section 3.3 we motivate the use of projections over weight-shan -harrig in this context, proving that projections are strictly more "efficient".
Online portfolio selection with transaction costs is active area of research 9 30 32 33
2.1 Related work
Switching (without memory) in online learning was first introduced in [35] (see also the earlier 34 and independently in the context of universal coding in (3)), and extended with the Fixed-Share algorithm [23]. An extensive literature has built on these works, including but not limited to [
7 8
16.
7
1 22
42 49 Relevant to this work are the results for switching with 27 29 49]. The first was the seminal work of [.]. The best known result given
24
27 29
38
memory 4
21
in [27] which we improve on. In
[9] reduction of switching with memory to switching without

---

12
Regret bound (x x)
MPP (decaying scheme)
MPP (uniform schemn)
Partition Specialists (Markov prior)
10
Fixod-Share Share
PoDSS- / Share-O
8
6
(k+
2
10
20
30
40
Figure 1: A comparison of the regret bounds discussed in this paper for m E [2, k+ with n= 500000, 40 and 4000, Fixed-Share Share'' bound constant with respect to m. In this case previous "memory" bounds (blue & yellow) are much worse than Fixed-Share for larger values of m while our bound (red) improves on Fixed-Share for all m 2 k].
memory is given, although with a slightly worse regret bound than 4 Related to the experts model is the bandits setting, which was addressed in the memory setting in 49
In 7 a unified analysis of both Fixed-Share and MPP was given in the context of online convex optimization. They observed the generalized share update (8) and slightly improved the bounds of [4]. Adaptive regret [1 [ 19, 335 has been used to prove regret bounds for switching but unfortunately does not generalize to the memory setting. This paper primarily builds the work of [4] with new geometrically- decalyin mixing scheme, and on [24] with a new relative entropy projection algorithm. Related to the problem of prediction with expert advice is that of universal coding in information for a discussion). Similarly, related to the problem tracking experts with memory the problem of universal coding for switching sources with repeating statistics (see and references therein).
theory (see e.g., [28 37 48
e.g.,
3 Projection onto dynamic sets (PoDS)
In this section give relative entropy projection- based algorithm for tracking experts with memory. We show how the projection update used by this algorithm is intimately related to the generalized share update (8). In the following subsection propose specific update rule for our algorithm for which we improve on the best known regret bound for this problem.
Given non-empty set C C An and a point ur E ri An we define
P(w; C) arg min Duu, w) aEC
to the projection with respect to the relative entropy w onto (6) Such projections were first introduced for switching (without memory) in online learning in [24, in which after every trial
the weight vector ui projected onto = [ 1]" An, that is, the simplex with uniform box
constraints. For prediction with expert advice this projection algorithm has the regret bound (3)
(see (7]). Indeed, we will refer to w = P(wi;; [ "_,1]" 1ir1i"'A A.)) as the "projection analogue" of (2) For tracking experts with memory each trial, such that each weight does not fall below a certain threshold that is learned for each expert.
algorithm will instead project onto set C that is updated on
Given 3 E (0, 1)" such that || < 1, let
C(B) {ø E A., :2; 2 B, 1...,n
be a subset the simplex which convex and non-empty. Given w A.. intuitively P(w; C(9)) is the projection of w onto the simplex with (non (non-uniform) lower box constraints B. Relative entropy projection updates for tracking experts with memory were first suggested in [4] Section 5.2]. The authors observed that for any MPP mixing scheme ri+1, the update (5) can be replaced with
+1
P(w' (w An 7
++1 2 .g O, o,...,t),,
(11)
5

---

and achieve the same regret bound. We build on this concept in this paper. Observe that for any
choice of y the set {w E A. w = 1/ ri. q = O....,t) corresponds to the set ((3) where
B = max
2 wi
+++
(i (i= (i=1,...,1))
(12)
05
In this work we give an algorithm compute the projection P(w: C())) exactly for any C(B) in ((n) time (Algorithm 3). With this algorithm and the mapping (12), one immediately obtains the
projection analogue of MPP for any mixing scheme y at essentially no additional computational cost. We point out however that for arbitrary mixing schemes computing B from (12) takes (nt)- time on trial t. improving only when some structure of the scheme can be exploited. We therefore propose the following method of Projection onto Dynamic Sets ("PoDS") for tracking experts with memory efficiently.
Just as (8) generalizes the Fixed-Share update (2), we propose PoDS as the analogous generalization of the update w'+1 P(b'; (())) (the projection analogue of Fixed-Share). PoDS maintains a vector 3 E A% and on each trial updates the weights by setting w*+1 = P2 C((")) Intuitively PoDS is the projection analogue of (8) with ( corresponding simply to ov'". In some cases 3 3"=av)
for all (e.g., for Fixed-Share, but general equality may not hold since 3 and v² can be functions of past weights, which may differ for weight-sharing and projection algorithms. Recall that (8) encapsulates all MPP mixing schemes that set y! = =1-a. PoDS implicitly captures the projection analogue of all such mixing schemes. This simple formulation of PoDS allows us to define new updates, which will correspond to new mixing schemes. In the following section we give a simple update for PoDS and improve on the best known regret bound. In Section 3.2 and the efficient computation of the projection P C(3)).
we discuss Algorithm
3.1 A simple update rule for PoDS
We now suggest a simple update rule for 3 in PoDS for tracking experts with memory. The regret bound for this algorithm is given in Theorem (see Figure 1.. We first set = to be uniform, and with a parameter 0 = < 1 update 3 on subsequent trials by setting
g
(1 - 0) + towb'.
(13)
We refer to PoDS with this update as PoDS-A. Intuitively the constraint vector 3 is updated in (13
by mixing in a small amount of the current weight vector, w'' scaled such that || a. If expert i predicted well in the past, then its constraint 3 will be relatively large, preventing the weight from vanishing even if that expert suffers large losses locally. Using Algorithm 3 in its projection step, PoDS-0 / has (nz per-trial time complexity.
As discussed, the vector , of PoDS is conceptually equivalent to the vector av' of the general- ized share update (8) If PoDS has a simple update rule such as (13) then it is straightforward to recover the weight-sharing equivalent by simply "pretending" equality holds on all trials. We now do this for PoDS-0. Clearly we have v.
n: and if 3 = ov and g3++1 = av*+1, then w - = (1--)) + fw' = (1 11--0 00' + Or.'. This then leads to an efficient sharing algo- rithm, which we call Share-6. In Section 4 we show this algorithm is in fact new MPP mixing scheme, which surprisingly corresponds to the previous best known algorithm for this problem. Both PoDS-0 and Share-f use the same parameters (ox and 0), differing only in the final update (see T&2).
Algorithms 1&2).
In the following theorem we give the regret bound which holds for both PoDS-0 and Share-0.
Theorem 1. For any comparison sequence i1, i1,...: ir containing i switches and consisting of m k-m+1 unique experts from set of size n, a = T-i and A (m-1)(T-2)- the regret of both PoDS-8 and Share-O with any prediction function and loss function which are (c, 1 --erelizaable is
k
R(iIT) S e mnn + +(T -1)7
1)7d
(
ho - (m (m-1)(T--) - 2)H
(m 1) 23 )
k - m +1
(14)
The regret bound (44 is at least c(m- 1) In T-1 11-m++1)1 F- tighter than the currently best known bound Thus if m & k then the improvement is RJ cm In T. and as m m-+ k+1 then the improvement is x ck In Additionally note that if k+ 1 (i.c., every switch track
&

---

Algorithms 1&2 PoDS-0 Share-0
Algorithm 3 P(w: ((3) in (n) time
Input: n > 0. _ > 0, a [0, 11. 0 [0,
Input: w A.;
: B E (0. 1)" s.t. ||||| S
Output: w' = C(ww;
& PoDS-0
1: init: W<-[n]; r=] w
1. Sw + 0: S3
1: init: w
+ 3
x /
g
while W do do
Share-O
3: ot *4-median(() (r;
W))
1: init: w² :,: -
4:
C+ W: i < o}
5:
LBt-L Br; Lw + L Liel Wi
b PoDS-O & Share-0
6:
W: M+ :ir = o)
2: for 1 to T do
7:
M3+ Eiem Bi; M 4 <EE--ie LiEM W/
3: receive x' D
H WiEWi o}
4: predict j' = pred(w", x²))
9:
At 1-Sw-
1-3--h
5: receive 1/' E y
6: for itrit1 to do
10:
io then
w/e-
11:
Sw 4 Sw Law + M
7:
iif t
Ej= m3e 2e
12:
Sg Sg + La + M9
13:
il 0 then
PoDS-0
14:
Φ min (rr : r, > 0, [n|])
8:
w w+ +- - :(i'' C((
(15)
15:
W H.
9:
g + (1 3) + Ocai"
16:
else
Share-A
17:
W
8:
wL11 + (1 a' + av
(16)
18:
A
Sw
B Awi
r: < Φ
9:
y 1+ t (1 - 0) + +ru"
(17)
19:
Vi
,....,77
w/
r 2
new expert) the optimal tuning of 0 is zero, and PoDS-0 reduces to setting 3 = a on every trial. That is, we recover the projection analogue of Fixed-Share. This also reflected the regret bound since 14 reduces to B). Since x²)()) ) S y In (+) + the regret bound (14) is upper-bounde by
R(hrr) Se mn T-1 +k--++1)ln k-m+1 +(k 11--m++1)) In (m-1)+2k m +
T-2
k
Comparing this to I0). we see that instead of paying cn T-1 twice on every switch, we pay cln T-1 once per switch and cln T-2 Unlike previous results for tracking experts with memory, PoDS-6 and its regret bound (14) smoothly interpolate between the two switching settings. That is, it is capable of exploiting memory when necessary and on the other hand does not suffer when memory is not necessary (see Figure]]
4 k-m+I for every switch we remember an old expert (k: - m + times).
3.2 Computing ((3))
Before we consider PoDS-0 and Share-O further, we briefly discuss the computation of the projection P(w; C(B)). In 24 the authors showed that computing relative entropy projection onto the simplex with uniform box constraints is non-trivial, but gave an algorithm to compute in O(n) time. We give generalization of their algorithm to compute P(w; C(B)) exactly for any non-empty set C(B) in O(n) time. As far as we are aware our method to compute exact relative entropy projection onto the simplex with non-uniform (lower) box constraints in linear time is the first, and may be of independent interest (see e.g., (31).
We first develop intuition by sketching out the form that P(w; C(B)) must take, and then describe how Algorithm 3 computes this projection efficiently. This stated formally in Theorem 2 the proof of which is given in Appendix B, Firstly consider the case that w E C(3). then trivially [6] For the case that w & C(B3) this implies that the set {i E [n] w/ < 3&} is non- moo--empty. For each index i this set the projection of to onto C(33 must set the component w; to its corresponding constraint value B. The remaining components are then normalized, such that Σ w; 1. However, doing so may cause one (or more) of these components w/ to drop below constraint By. In Appendix B prove that the projection algorithm must find the set of components V of least cardinality to set to
P(w: P(w: w, due to the non- negatiiiiyy of D(u, w) and the fact that D(u, w) iff
7

---

their constraint values such that when the remaining components are normalized, no component lies below its constraint, and that this can be done in linear time.
Consider the following inefficient approach to finding W. Given w and C(3), let r = w @ 1 be a 'ratio vector". First sort r in ascending order, and then sort w and 3 according to the ordering of r. r 2 1 then = 0 and we are done (= w E C(G)). Otherwise for each a = I....... n: 1) let the candidate set V = [a]. 2) let w' w except for each i V set u/ = 8, 3) re-normalize the remaining components of w', and 4) let r' = ur 8 The set V is then the candidate set
3
V of least cardinality such that r' = This approach requires sorting r and therefore even an efficient implementation takes (n log time. Algorithm 3 finds y without having to sort v. It instead specifies V' uniquely with a threshold, ø, such that v = {i r.; < Φ). Algorithm 3 finds through repeatedly bisecting the set W = [n] by finding the median of the set {ri WT (which can be done in (([W]) time [3]), and efficiently testing this value as the candidate threshold on each iteration. The smallest valid threshold then specifies the set V. The following theorem states the time complexity of the algorithm and the form of the projection, which used in the proof of Theorem 1 (the proof of Theorem is in Appendix B where we also give a more detailed description of Algorithm 3)
Theorem 2. For any E (0, 1)" such that [| S 1, and for any w ri A.. letp = P(w; C(B)), where C(3) = (æ E An 24 2 Be, i 1, ...... n... Then p is such that for all i = 1.....
P. max B1: 1- Σ
EjevP B3 Wi
(18)
I- EjE Wj
where V/ = {i [n] : Ps B.). Furthermore, Algorithm computes p in O(n) time.
3.3 Projection vs. sharing in online learning
We now briefly consider the two types of updates discussed in this paper (projection and weight- sharing) when updating weights may incur costs. Recall the motivating example introduced in Section was in online portfolio selection with transaction costs. It is straightforward to show that in this model transaction costs are proportional to the f--ormm of the difference in the weight vectors before and after re-balancing. In Theorem 3 we give result which in this context guarantees the "cost" of projecting is less than that of weight-sharing.
To compare the update of PoDS and the generalized share update 8 we must consider for a set of weights ui, the point P(ab'; and the point (1 a)w² " ae.. However these points depend on 3r and v² respectively, which may themselves be functions of previous weight vectors ui ....... - compare the two updates equally we therefore assume that the current weights are the same (i.e., they must both update the same weights w and additionally that 3 = av'. The following theorem states that under mild conditions, PoDS is strictly less "expensive" than its weight-sharing counterpart.
which as discussed are generally not the same for each of the two algorithms. To
Theorem 3. Let 0 < < 1. Then for any E ri An let ß av, for any E ri A, such that w F v. let 5(w, v) == (1 a) + av. Then,
[i C(B)) - wil1 < S[ v) wl
Thus if one has to pay to update weights, projection is the economical choice.
4 A goomerically-deeainng mixing scheme for MPP
In this section we look more closely at Share-9. We show that it is in fact new type of decaying MPP mixing scheme which corresponds to the partition specialist algorithm with Markov prior.
Recall that the previous best known mixing scheme for MPP is the decaying scheme (6) Observe that in (6) the decay (with the "distance" to the current trial f) follows a power-law, and that computing (6) exactly takes (nt) time per trial. We now derive an explicit MPP mixing scheme from the updates (16) and (17) of Share-0. Observe that if we define vh := 1. then an iterative
expansion of (17 on any trial gives v' = Σt= g -00 from which (16) implics
8

---

w = -1-a) + too'
= =Eq= 79
x 2t, 2 where
1 1
q=t
1+1 0(1 0) 0
15 <t
(19)
4
(1 0)
9 -= 0.
Note that (99 is a valid mixing scheme since for all t, En= Th 1. The Share-O update is therefore a new kind of decaying mixing scheme. In this new scheme the decay is geometric, and can therefore be computed efficiently, requiring only (n) time and space per trial as we have shown. Furthermore MPP with this scheme has the improved regret bound (14).
Another interesting difference between the decaying schemes (19) and (6) is that when 0 is small then (19) keeps 26+1 relatively large initially and slowly decays this value as increases. Intuitively by heavily weighting the initial uniform vector ui on each trial early on, the algorithm can "pick up" the weights of new experts easily. Finally as in the case of PoDS-6, if m = k + 1, then with the optimal tuning of 0, this update reduces the Fixed-Share update (2).
Revisiting partition specialists. We now turn our attention to the previous best known result for tracking experts with memory (the partition specialists algorithm with a Markov prior [27
For sleep/wake patterns (X1 (XI..-X7 XT) the Markov prior is Markov chain on states (w,s). defined by the initial distribution = (TT.. πz) and transition probabilities Pty := P(x++1 = =]lx= i) for i,j {w, s}. The algorithm with these inputs efficiently collapses one weight per specialist down to two weights per expert. These two weight vectors, which we denote a and 8t, represent the total weight of all awake and sleeping specialists associated with each expert, respectively. Note that the vectors a₂ and 8t are not in A,, but rather the vector (a,, s;) A2n and the "awake vector" d gets normalized upon prediction. The weights are initialized by setting a1 = Tw n²
The and 81 = n. n'
update of these weights after receiving the true label y' is given by
1+1 a1 de- dee 1a))
afe- 12 Σj= ase ndy + Pasof
Paru
P PswS
and
[+1
Pws
Σラ= u'e-
for .,..., Recall that the authors of (27 proved that an MPP mixing scheme implicitly induces a prior over partition specialists. The following states that the Markov prior is induced by (19). Proposition 4. Let O prior parameterized with Psw- = 0, Pws = a, Tw
1, and 0 0 < Then the partition specialists algorithm with Markov a is equivalent to Share-O 8 and Ti a40 a40
parameterized with a and 0.
The proof (given in Appendix E amounts to showing for all that a w and v.. The Markov prior on partition specialists therefore corresponds to a cemeetiiaall-decayiiee MPP mixing scheme! Note however that we have proved a tighter regret bound for this algorithm Theorem [
Discussion
We gave an efficient projection-basee based algorithm for tracking experts with memory for which we proved the best known regret bound. We also gave an algorithm to compute relative entropy projection onto the simplex with non- non-uniform (lower) box constraints exactly in ((n) time, which may be of independent interest. We showed that the weight-sharing equivalent our projection-based algorithm is in fact a crometrically-decayinn mixing scheme for Mixing Pasl Posteriors
4 Furthermore we showed that this mixing scheme corresponds exactly to the previous best known result (the partition specialists algorithm with Markov prior (27)) and we therefore improved on their bound. We proved a guarantee favoring projection updates over weight-sharin such in online portfolio selection with proportional transaction costs. We are currently applying PoDS-0 to this problem. primarily extending the work of [44] in the sense of incorporating both the assumption of ""meory"" and transaction costs.
when updating weights may incur costs,
In this work we focused on proving good regret bounds, which naturally required rerimalll-tunne parameters. A limitation of our work is that in practice the optimal parameters are unknown. This is
'n 27 the algorithm is presented in terms of probabilities with the log loss. Here we give the update generalized to (c, 1)) realizalee losses.

---

common issue in online learning, and one may employ standard techniques to address this such as the "doubling trick", by using Bayesian mixture over parameters [46]. For prominent recent result in this area see [26).
Ethical considerations. While the scope of applicability of online learning algorithms is wide, this research in beuued-bounded online learning is foundational in nature and we therefore cannot foresee the extent of any societal impacts (positive or negative) this research may have.
Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their feedback, insights, and discus- sion. The authors would also like thank Dmitry Adamskiy for valuable discussions. This work was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/N509577/1.
References
[1] D. Adamskiy, W. M. Koolen, A. Chernov, and V. Vovk. A closer look adaptive regret. The Journal of Machine Learning Research, 17(1):706-726, 2016.
[2] A. Blum and A. Kalai. Universal portfolios with and without transaction costs. Machine Learning, 35(3):193322) 1999.
[3] M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. J. Comput. Syst. Sci., (4)):48-461, 1973.
[4] O. Bousquet and M. K. Warmuth. Tracking a small set of experts by mixing past posteriors. Journal of Machine Leurning Research, 3NNvv):333339 2002.
[5] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[6] L. M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217 1967.
[7] N. Cesa- Basa-Bianchi, P. Gaillard, G. Lugosi, and G. Stoltz. Mirror descent meets fixed share (and feels no regret). In Conference on Neural Information Processing Systems, volume 2, pages 989-997 2012.
[8] A. Daniely, A. Gonen, and S. Shalev-Shwartz. Strongly adaptive online learning. In Interna- tional Conference on Machine Learning, pages 1405-1411. PMLR, 2015.
[9] Das, N. Johnson, and A. Banerjee. Online lazy updates for portfolio selection with transaction costs. In AAAI. Citeseer, 2013.
[10] R. W. Floyd and R. L. Rivest, Expected time bounds for selection. Communications of the ACM, 18(3)116--772, 1975.
[11] R. M. French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, (44):228-333 1999.
[12] Y. Freund. Private Communication, 2000. Also posted on htttt::::ww..e.rnnni.a -theor org/
[13] Y. Freund and R. E. Schapire. A decision-theoretie generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-13) 1997.
[14] Y. Freund, R. E. Schapire, Y. Singer, and M. K. Warmuth. Using and combining predictors that specialize. In Proceedings of the twenty-ninth annual ACM symposium Theory of computing, pages 334-343, 1997.
[15] R. Gramacy, M. K. Warmuth, Brandt, and I. Ari. Adaptive caching by refetching. Advances in Neural Information Processing Systems, 15:1489-1496, 2002.
10

---

[16] A. György, T. Linder, and G. Lugosi. Tracking the best of many experts. In International Conference on Computational Learning Theory, pages 204-216. Springer, 2005.
[17] A. Gyorgy, Linder, and G. Lugosi. Efficient tracking of large classes of experts. IEEE Transactions on Information Theory, (8(11):6709-6777 6725, 2012.
[18] D. Haussler, J. Kivinen, and M. K. Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 1465)1900-1125, 1998.
[19] E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th annual international conference on machine learning, pages 393-400, 2009.
[20] M. Herbster, S. Pasteris, and M. Pontil. Predicting a switching sequence of graph labelings. J. 2015.
Mach. Learn. Res.,
[21] M. Herbster, S. Pasteris, and L. Tse. Online multitask learning with long-term memory. In Advances in Neural Information Processing Systems, volume 33, pages 17779-17791, 2020.
[22] M. Herbster and Robinson. Online prediction of switching graph labelings with cluster specialists. In Advances in Neural Information Processing Systems, volume 32, 2019.
[23] M. Herbster and M. K. Warmuth. Tracking the best expert. Machine learning, 32(2):151-178, 1998.
[24] M. Herbster and M. K. Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, 1(Sep):281-302 2001.
[25] D. Hoeven, T. Erven, and W. Kottowski. The many faces of exponential weights in online learning. In Conference On Learning Theory, pages 2067-2092. PMLR, 2018.
[26] K.-S. Jun, F. Orabona, S. Wright, and R. Willett. Improved strongly adaptive online learning using coin betting. In Artificial Intelligence and Statistics, pages 943-95 1111951. PMLR, 2017.
[27] W. M. Koolen, D. Adamskiy, and M. K. Warmuth. Putting bayes to sleep. In NIPS, pages 135-143, 2012.
[28] W. M. Koolen and S. de Rooij. Universal codes from switching strategies. IEEE Transactions on Information Theory, 59(1 (0(11):7768-118 2013.
[29] W. M. Koolen and van Erven. Freezing and sleeping: Tracking experts that learn by evolving past posteriors. CoRR, abs/ (bbs/1008,445,, 2010.
[30] S. S. Kozat and A. C. Singer. Universal switching portfolios under transaction costs. In 2008 IFFE International Conference on Acoustics, Speech and Signal Processing, pages 5404-5407. IEEE, 2008.
[31] W. Krichene, S. Krichene, and A. Bayen. Efficient bregman projections onto the simplex. In 2015 54th IEEE Conference on Decision and Control (CDC), pages 3291-3298. IEEE, 2015.
[32] B. Li and S. C. Hoi. Online portfolio selection: A survey, ACM Computing Surveys (CSUR), 46(3):1-36, 2014.
[33] B. Li, Wang, D. Huang, and S. C. Hoi. Transaction cost optimization for online portfolio selection. Quantitative Finance, 18(8):1411-1222 2018.
[34] N. Littlestone and M. Warmuth. The weighted majority algorithm. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 256-261, 1989.
[35] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and computation, (0:(2))1 1994.
[36] M. McCloskey and N. J. Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. Psychology of learning and motivation, volume 24, pages 109-165. Elsevier, 1989.
11

---

[37] N. Merhav and M. Feder. Universal prediction. JEEE Transactions on Information Theory, 44(6):2124-2147, 1998.
[38] Mourtada and O.-A. Maillard. Efficient tracking of growing number of experts. In International Conference Algorithmic Learning Theory, pages 517-539. PMLR, 2017.
[39] H. T. Nguyen and K. Franke. Adaptive intrusion detection system via online machine learning. In 2012 12th International Conference on Hybrid Intelligent Systems (HIS), pages 271-277. IEEE, 2012.
[40] G. I. Shamir. On asymptotically optimal sequential lossless coding for memoryless switching sources. In Proceedings IEEE International Symposium on Information Theory, page 124. IEEE, 2002.
[41] G. Shamir and D. Costello. Universal lossless coding for sources with repeating statistics. IEEE transactions information theory,
2004.
[42] D. Sharma, M.-F. Balcan, and T. Dick. Learning piecewise lipschitz functions in changing environments. In International Conference on Artificial Intelligence and Statistics, pages 3567-3577. PMLR, 2020.
[43] Y. M. Shtarkov. Switching discrete sources and its universal encoding. Probl. Inform. Transm., 28(3):95-111, 1992.
[44] Y. Singer. Switching portfolios. International Journal of Neural Systems, 8004):445455, 1997.
[45] V. Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences, 16(2):153-173, 1998.
[46] V. Vovk. Derandomizing stochastic prediction strategies. Muchine Learning, 35(3):247-282. 1999.
[47] V. G. Vovk. Aggregating strategies. Proc. Computational Learning Theory, 1990, 1990.
[48] Q Xie and A. Barron. Asymptotic minimax regret for data compression, gambling, and prediction. IEEE Transactions on Information Theory, 46(2):431-445, 2000.
[49] K. Zheng, H. Luo, I. Diakonikolas, and L. Wang. Equipping experts/bandits with long-term memory. In Advances Neural Information Processing Systems, volume 32, 2019.
12


Reviews:
[{"review_id": "GrVrbnWq9Q", "reviewer": "Reviewer_ETi1", "summary": "The setting in the paper is the one of prediction with expert advice in a non-stationary environment - the learner competes against a sequence of switching experts [This setting was introduced by Bousquet and Warmuth, 2002].\nThe authors propose an algorithm that improves upon previously known regret bounds.\nThe main novelty is incorporating a relative entropy projection step onto a simplex. This projection step can be computed in linear time (of the number of experts).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Significance: The paper discusses fundamental questions in Online Learning. \nThe suggested algorithm improves upon previous results while introducing new techniques that seem to be useful in other contexts as well.\n\nClarity and relation to prior work: The paper is very clear and easy to follow. \nThe authors described thoroughly previous results and their connection to their paper.\n\nQuestion: who is H in (3) and (9)?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "94tdQ_Vl5hb", "reviewer": "Reviewer_i3gM", "summary": "This paper studies a specific setting for the online expert tracking problem: the expert comparison sequence consists of a few unique experts relative to the number of switches. \nIn order to solve this problem, the author/s proposes new algorithm to keep track of the lower box constraints \\beta (the similar fixed share parameter for the non-projection variant) for each expert with Markov chain update. To solve the lower box constraint projection, it also proposes a O(n)-time per trial projection-based algorithm for the n experts. All the proposed algorithms are based on prior works on the same problem setup.\nThe performance guarantee of the proposed algorithm could further improve the current best-known efficient algorithm by a constant number.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and easy to read. The main concerns I have are about originality and result' significance.\n\n1. The contribution for the linear-time projection algorithm 3. As the paper points out, it is based on the prior work when the box constraint lower bound is universal over different experts. But for this paper's algorithm, it needs to have different lower bounds for different experts. Algorithm 3 modifies the prior work and solve this problem. But the difficulty of it is debatable. Also, I don't see any new insights from Algorithm 3 as well.\n\n2. The contribution for the Algorithm 1&2. As pointed out in the paper, this algorithm is based on prior works ideas in Eq.(12) and the partition specialists Markov chain update in [26]. The update rule in Algorithm 1&2 step 9 seems to be from the [26]'s Markov chain update and just generalizes the chain update. Because the original inefficient algorithm from [4] has the observations of Eq.(12) (which is the kind of box constraint projection), and the follow-up work [26] proposed an efficient algorithm with the Markov chain update (which is the Markov chain update rule idea for Algorithm 1&2 step 9). Based on the above arguments, there is no surprise that the algorithm 1&2 could have a mixing scheme MPP explanation in Section 4.\n\n3. The comparison in Figure 1 is unfair. For the result in this paper, it depends on the tuning parameters m (the number of unique experts) and the k (the number of switches). And this paper's result in Figure 1 depends on this prior knowledge, while the prior work [26] does not need such information, which explains the reason to have increasing values for MPP and Partition Specialists. In other words, this paper's claim on having better theoretical results out of the range m<<k is not accurate. If we only consider the m<<k case, the theoretical improvement is really minimal, only a constant term improvement.\n\n=========== After rebuttal ================\nThanks the author/s for the detailed explanation on my initial reviews.\n\nAfter checking the work [26] more carefully, I agree with the author/s that the comparison in Figure 1 is fair.\n\nHowever, for Algorithm 3's contribution on the efficient linear-time projection, I am not convinced that its contribution is significant enough given the prior work's efficient algorithm.\n\nFor my second concern on Algorithm 1&2 and the reply from the author/s, I totally agree that Algorithm 1&2 are not directly from [26]. Although we could put the correspondence between P (P_ww, P_ws, P_sw, P_ss) from [26] and \\theta, \\alpha from this paper, and we will at least achieve the performance guarantee from [26], the paper's contribution about the revelation of the Markov prior over partition specialists corresponding to a geometrically-decaying mixing scheme is not trivial.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "4AEkbWNjpjC", "reviewer": "Reviewer_SYb7", "summary": "For the setting of non-stochastic switching experts with memory, an explicit Mixing Past Posteriors formulation of the SOTA efficient algorithm is provided together with an improved regret bound, which also applies to relatively large number of switching experts. \nThis is achieved by introducing an efficient projection-based algorithm for this setting and an efficient algorithm for computing projections onto an entry-wise lower-constrained simplex. The MPP equivalent of the proposed projection-based algorithm is shown to correspond to the (Bayesian) SOTA through a Bayesian interpretation.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The significance of the paper is mainly in introducing the first efficient MPP algorithm to match (actually improve) the state of the art regret bound for the setting of switching experts with memory. It also introduces an efficient algorithm for computing exact relative-entropy projections into entry-wise non-uniform lower-constrained simplex, that is then used as part of an new efficient projection-based algorithm for the setting, achieving (actually improving) the SOTA regret bound. The paper also suggests (Theorem 4) the advantage of the projections-based algorithm over the MPP variant for settings with switching costs.\n\nThe presentation of the material is clear and the paper is easy to follow. Relevant references are provided and the contributions of the paper over the state of the art and related results from relevant domains are explicitly stated. I do have a couple of comments/questions nevertheless:\n\n1) To assess the significance of the improvement in the regret bound (the discussion around line 250) it would be helpful to also refer to a relevant lower bound on the achievable regret.\n2) The way I see the flow of ideas in the paper, it is first established that for a projections-based algorithm to be efficient two elements are needed - an efficient computation of the projection, and an efficient computation of $\\beta_i$ (line 176). The paper then proceeds to implement an efficient projections-based scheme, and its (efficient) MPP equivalent (section 4) having an explicit formulation of the $\\gamma$ updates. My question is going back to (12), and comparing it to the PoDS-$\\theta$ rule (15).  This should 'close the loop' in  a sense, providing an efficient formulation of a solution to (12) (which is impossible in general) for the structure introduced by the  PoDS-$\\theta$ algorithm, and using the explicit form of (20).\n\nFinally, a few suggestions/typos: \nTypo: replace $v_i$ in line 67.\nClarify what is meant by \"absolute loss\" in line 70.\nShould be $\\ln nT$ in line 79.\nInclude $k=40$ in the plot of Figure 1, not only at the caption.\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Following our discussion, the reviewers and I all agree that this is a well-written paper that makes a solid contribution (albeit on a somewhat niche problem) and the techniques are interesting and would be of interest to the community.  I encourage the authors to further clarify the relation to prior work in their final version, in terms of improvements and techniques, paying particular attention to comments by Reviewer i3gM.

Decision: Accept (Poster)