Title: Efficient tracking of a growing number of experts,
Abstract: We consider a variation on the problem of prediction with expert advice,
where new forecasters that were unknown until then may appear at each round. As
often in prediction with expert advice, designing an algorithm that achieves
near-optimal regret guarantees is straightforward, using aggregation of
experts. However, when the comparison class is sufficiently rich, for instance
when the best expert and the set of experts itself changes over time, such
strategies naively require to maintain a prohibitive number of weights
(typically exponential with the time horizon). By contrast, designing
strategies that both achieve a near-optimal regret and maintain a reasonable
number of weights is highly non-trivial. We consider three increasingly
challenging objectives (simple regret, shifting regret and sparse shifting
regret) that extend existing notions defined for a fixed expert ensemble; in
each case, we design strategies that achieve tight regret bounds, adaptive to
the parameters of the comparison class, while being computationally
inexpensive. Moreover, our algorithms are anytime, agnostic to the number of
incoming experts and completely parameter-free. Such remarkable results are
made possible thanks to two simple but highly effective recipes: first the
"abstention trick" that comes from the specialist framework and enables to
handle the least challenging notions of regret, but is limited when addressing
more sophisticated objectives. Second, the "muting trick" that we introduce to
give more flexibility. We show how to combine these two tricks in order to
handle the most challenging class of comparison strategies.