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 z 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 se 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-tin -tmm 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) + tao'
= =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 beuudd-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 -theorrrrrnnnntrryyyyyy 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": "vSGBrhgGBKj", "reviewer": "Reviewer_gqjS", "summary": "The paper studies improving regret bounds for memory tracking experts.  There are n experts for a learning task of T examples, out of which only m << n experts are useful.  The examples switch between different populations of examples k << T times, and are assumed to stay a sufficient time in each population segment.  Since m << k, experts are revisited, and the goal is to take advantage of the knowledge that experts are reused to reduce the regret.\n\nThe paper proposes following on prior work to learn weights for the different experts, and use non-fixed generalized share updates to share portions of weights assigned to an expert with other experts at subsequent rounds.  The amount of sharing is key to reducing regret.  Instead of directly following a generalized share update path, the approach update shares by the prediction quality of the expert, and then projecting the sharing weight vector to a subspace of the probability simplex such that shares do not fall below a dynamically updated threshold.\n\nUpper bounds, claimed to be stronger than previous works, are then derived for the regret of the method, specifically lowering an extra O(log(T/k)) term per switch that is present in previous bounds.  This term is lowered to include only k - m terms instead of k, eliminating the cost of the first occurrence of each expert (with some second order correction).\n\nThe paper then goes on to show that the approach used can actually be mapped to a slightly different share update method but with the same regret upper bounds, which is a special case of the generalized share update rule.  The latter is then shown to also be a special case of a Bayesian mixing scheme that uses a geometric distribution.  It concludes that because of that, the bounds in this paper also apply to the Bayesian approach in Koolen et. al. 2012.\n\nIn addition, the paper presents a low complexity projection method from an unconstrained probability simplex to one in which the probabilities are constrained from below, to be used for the projection step of the proposed projection algorithm.  It then asserts that if adapting weights as proposed for mixing the experts’ advice costs proportionally to the L1 distance between the weights before and after the adaptation, the projection method is advantageous to the other derived approaches.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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 addresses an interesting problem and is nicely written. The introduction gives a very good overview of the problem area, and positions the paper very well for the technical part.\n\nWhile I would like to see this work published, if correct, I have several concerns about the actual results and their correctness.  I will appreciate it if the authors can address and clarify these comments, before I can recommend publication.  There are several other major points that I would like to see corrected before recommending for publication.  I am happy to iterate with the authors during the open review process to verify these comments are addressed.  Given these current concerns, I give a do not accept score.  However, if these issues are addressed, I’ll be happy to improve my score.\n\nTheorem 3: It is not clear to me at this point that the proof covers all situations. For example, suppose we have m experts out of which only one is active for the first O(T) rounds.  All the remaining m-1 experts achieve very large losses during those rounds and also, each of these m-1 experts incurs very large loss on examples that another expert in the set achieves low loss.  Then, only in the last examples constituting the remaining k segments, the m-1 remaining experts become active.  It seems that in such a case each of the m-1 remaining experts will start with a weight that is (1-theta)^{O(T)} x alpha/n.  Since theta = O(k/T), wouldn’t this yield a term of O(km) in the bound, which, assuming m is omega(1), is larger than the order of the bound?  (This will not change if m << k, and is independent of whether some of these experts will reoccur in the last k segments).\n\nTheorem 4: The paper concludes that the projection algorithm is better for minimizing rebalancing costs due to this theorem.  Is that a direct result of the lower limits not moving?  However, in the projection algorithm they do actually move, and then Theorem 4 may not apply to the algorithm.\n\nThe paper should state when it is at all useful to use the proposed approach earlier and more clearly.  While the combinatorial bound shows advantages over fixed share whenever m < n, the extra O((k-m) log(T/k)) regret of the proposed method makes it clearly inferior to fixed share if T/k > n and m = o(k).  Figure 1 does not cover cases like this.\n\nDoes the heuristic in the paragraph starting in line 199 really guarantee minimization of the divergence?  This should be proved.\n\nThe paper does not mention a large body of literature from information theory that is directly related to the problem of tracking experts, and presents bounds on cost of switches as well as algorithms that are very related to those of expert tracking.  These papers should be cited and mentioned in the presentation of the problem.  Below is a partial list of relevant papers (the first and the last 2 are specifically relevant to recurring experts).  There are additional references in the listed papers below that are relevant.\n\nY. M. Shtarkov, “Switching discrete sources and its universal encoding,” Probl. Inform. Transm., vol. 28, no. 3, pp. 95–111, July-Sept. 1992\n\nN. Merhav, “On the minimum description length principle for sources with piecewise constant parameters,” IEEE Trans. Inform. Theory, vol. 39, pp. 1962–1967, Nov. 1993.\n\nF. M. J. Willems, “Coding for a binary independent piecewise-identically-distributed source,” IEEE Trans. Inform. Theory, vol. 42, pp. 2210–2217, Nov. 1996\n\nG. I. Shamir and N. Merhav, “Low complexity sequential lossless coding for piecewise stationary memoryless sources,” IEEE Trans. Inform. Theory, vol. 45, pp. 1498–1519, July 1999\n\nG. I. Shamir, “On Asymptotically Optimal Sequential Lossless Coding for Memoryless\nSwitching Sources”, ISIT 2002.\n\nG. I. Shamir and D. J. Costello, “Universal lossless coding for sources with repeating statistics”, IEEE Trans. Inform. Theory, vol. 50, pp. 1620-1634, Aug. 2004\n\nMinor issues:\n\nFor this approach (and the ones it is based on) to work, one needs to know T, k, m in advance - this should be mentioned in the introduction.\n\nLine 129 - the paper implies that the m log n term is paid to remember, not to learn.  However, this seems inconsistent with the combinatorial bound, where this term comes from choosing which m out of the n experts are the ones whose advice are used.\n\nLine 150 - The idea mentioned here was first introduced in Shtarkov’s paper above.\n\nThere is use of v^t and tilde{v}^t - it is not clear how they differ.\n\nTo introduce PoDS in Section 3, it would help to add one intuition sentence saying something like: the algorithm projects the weights such that they don’t go below a certain threshold that was learned for each expert.\n\nIt would be better to change the order of Theorems 1 and 3.  First, Alg. 1&2 should be presented, stating the use of the projection result described later.  Then, Theorem 3 should be stated.  Then, Alg. 3 should be discussed and then Theorem 3.  The current structure is confusing and breaks the flow for a reader.  Also, Theorem 3 is the more important one for the results, and the flow of the paper should lead to it before talking about supplementary results like Theorem 1.\n\nLine 210 - it would be better to use a different character from k, that is already used for the number of switches.\n", "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": "5"}, "extra_text": {}}, {"review_id": "ms33ohv7022", "reviewer": "Reviewer_t33Y", "summary": "The paper give two improved algorithm for the expert advice setting with long term memory guarantees.\nBoth achieve a regret bound that is slightly better than the best previous algorithm given in [26].\nThe first algorithm is of the Mixing Past Posterior type and is particularly simple.\nThe second uses a generalized relative entropy projection algorithm that is also interesting.", "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": "+ Well written paper. Lots of intuition given throughout. Some further suggestions are given below.\nDefinitely interesting because the simple MPP version achieves the improved bound. \nThe projection version of the algorithm gives further intuition why the new MPP algorithm works.\n- A bit specialized and it could be argued that the improvements are not significant enough.\nHowever this is chasing an NP-complete problem. May be complementing the paper with NP hardness results\nand exactly quantifying the gap would be helpful.\n\nOverall rating: 6.5\n\n\nDetailed comments:\n\nLine 5 of intro: Add \"the\" before \"learner\".\n\nPage 2, line -7: No! I don't think that generalizing this to the Hedge setting is trivial, because\neach segment of a partition requires a different optimized learning rate that depend on\nthe loss of the best in that segment.\nAdjusting Hedge to the long-term memory setting is thus challenging it seems already for the Fixed Share Setting.\n\nPage 3, before (3): Give the alpha that achieves (3).\n\nPage 3, after (7): Which gamma achieves the better bound and how much is the improvment?\n\nPage 5, section 3: Projections also have been used to cap weights from above instead of below.\n\nPage 7, line 7 of alg. 1/2: the dot over w is too small. Suggest to use a hat.\n\nSection 3: You use a worst-case linear median algorithm. Those algorithms are complex divide and conquer\nalgorithm that have a high constant.\nBut there is a simple randomized median finding algorithm with average time complexity O(n) that is\nquite practical! Suggest to mention that algorithm as well.\n\nAlso I suggest to look at this paper: \nEfficient Projections onto the L1-Ball for Learning in High Dimensions by Duchi, Shalev-Shwartz, Singer and Chandra.\n\nThey do Euclidean projections, but the don't have the worst case O(n) algorithm it seems. Your techniques will probably lead to\nan O(n) w.c. algorithm as well for the Euclidean projection case when the ranges are non-uniform.\n\nPage 8, line 255: When k>>m, then the additional cost per switch is again c ln T/k.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Basic research. No direct societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N/a.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "jX9mMPruKdj", "reviewer": "Reviewer_AJRz", "summary": "This paper considers the problem of tracking the best expert with long-term memory. This corresponds to prediction with (n) expert advice in which the learner's performance is compared to sequences of experts that may switch k times between a few (m) experts only. The authors consider two related algorithms: one introduced by Bousquet and Warmuth (2002), which mixes past posteriors (MPP), and one which is based on projections with respect to the relative entropy. For well-chosen parameters and for a well-chosen newly introduced mixing scheme, they improve for both algorithms the best existing (efficient) upper-bound for this problem by a factor of 2. This closes the gap with respect to the best non-efficient algorithm. \n\nThey provide also a linear-time method to compute projections (with respect to the relative entropy) on the simplex with lower box constraints. This allows their algorithms to require only O(n) per-round computation where n is the number of experts.", "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": "\nOn the positive side:\n- I found the paper very well written and enjoyable to read. Besides the technical contributions, I believe that this paper would provide a good introduction to the problem of tracking the best expert with memory. The proposed algorithms, proofs, and regret bounds are clean and easy to follow. \n- The efficient projection algorithm with respect to the relative entropy could be of independent interest for the community. \n- The regret upper-bound improves the known no-memory regret bound of fixed share whenever m<k. This shows that memory is always useful which was not the case for previous bounds that required m significantly smaller than k. \n\n\nOn the negative side:\n- We could say that the contribution is somewhat limited and that the problem of improving the existing limits by a small constant factor is of interest only to a niche of the community. \n- The method requires the beforehand knowledge of unknown parameters: number of switches (k), number of experts used in the memory (m), horizon (T). If I agree that T can be tuned by a doubling trick this is more complicated for k and m. I know that k can be tuned by using sleeping experts techniques. Is it also the case for m?\n- I agree that the contribution is mostly theoretical but some simulations could illustrate if there are practical differences between the two schemes (projections vs MPP) and if this factor 2 really makes a difference in real life.\n\n\nOther comments:\n- Is the regret bound also always better than the one of fixed-share when m<n? A figure similar to Figure 1 with n instead of k might be interesting. \n- I didn't find the last paragraph before section 2.1 that motivates the use of projection very clear. I understand that there is more detail later but at that point, I had no idea why these examples motivated the use of projection.\n- What is the advantage of using (c,1/c)-realizability with respect to exp-concavity? The latter seems more common.\n\nMinor comments:\n- State that (3) is for a well-chosen alpha.\n- line 70: square loss has c=1/2 only if the prediction and output domains are [0,1]", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "F9PnV01yG2N", "reviewer": "Reviewer_dt3a", "summary": "This paper studies 'prediction with expert advice' in a non-stationary environment where the best expert is switching. The main contribution is an improved regret bound in the 'memory' setting (where a small number of experts is optimal), which is achieved with an efficient algorithm (in fact two variants are proposed). The algorithm is linear in the number of experts and the improvement compared to the best previous efficient algorithm is a factor two in one term of the regret bound, almost matching the best bound for a non-efficient algorithm. Further, the authors introduce a generalized algorithm for computing the projection of w.r.t. the relative entropy in linear time, and give a Bayesian interpretation of the Share-theta algorithm.", "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": "Originality:\nThe paper introduce several new ideas, including the efficient computation of the relative entropy projection, and the improved regret bounds for PoDS-theta and Share-theta, and the connection between Share-theta and the MPP approach. I liked the detailed introduction and comparison to previous work.\n\nQuality and Clarity:\nGenerally, the paper is very well written and organized. The improvement on the regret bound however seems rather marginal. It would be good to know if the improvement translates to better empirical performance. Please also clarify if (3) is a lower bound, or simply the best known upper bound. The reduced switching cost of the projection-based approach is an interesting observation. Also the appendix is quite polished and I did not identify any problems with the proofs.\n \nSignificance:\nThis paper makes an important contribution to the online learning literature.\n\n[edit]\nThank you for the detailed responses. I prefer to keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As stated also by the authors, one big limitation of the method is that the algorithm needs to be tune using the 'k', 'm' and 'T' parameters. In practice, these are almost always unknown and one would hope to pay a little or no penalty for adaptivity. I would encourage the authors to discuss this point in more detail, and state if there are known techniques to make the algorithm more adaptive (I am aware of the doubling trick, but this seems highly non-trivial to apply here, since doubling usually only avoids the knowledge on the horizon on a sqrt{T} regret bound).\n\nFinally, in my opinion it is a pity that papers (including this one) on online learning rarely include empirical evaluations. The worry is that by only optimizing the theoretical regret bounds, the algorithms are biased to perform well on the worst-case instances, but perhaps unfavorably on average cases or real-world examples.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "058vW5iAaE", "reviewer": "Reviewer_GNro", "summary": "This paper studies the tracking experts with memory problem, and proposes a new algorithm with improved regret bound and linear computational complexities wrt the number of experts. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written in general, and the proposed method is novel, which enjoys an improved regret bound with respect to [26], and share the same computational costs. The technique for doing relative entropy projection in linear time is also interesting. I have the following questions:\n\n1.\tFrom the discussion under Theorem 3, it seems that the *order* of regret bound is only improved by constant factors (eq. (10) vs Line 253, $c\\ln{\\frac{T-1}{k}}$ to $c\\ln{\\frac{T-2}{k-m+1}}$). Could the authors add more discussions on the significance of the results? \n2.\tCan the authors compare the computational complexities of the proposed algorithms with existing methods?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The questions about the limitations of the proposed methods are discussed in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have agreed that the presented results are novel, the paper is nicely written, and contains good ideas. On the other hand, the paper is probably only interesting to a small part of the community, providing a little improvement to a well-studied problem, and the algorithm also needs to know the problem parameters in advance. Nevertheless, the positives outweigh the negatives, hence I recommend acceptance.
Decision: Accept (Poster)