标题： 高效追踪不断增长的专家数量 显示英文标题

标题： Efficient tracking of a growing number of experts

摘要： 我们研究了带专家建议预测问题的一个变种，在这个变种中，每一轮都可能出现之前未知的新预测者。 正如在带专家建议的预测中经常遇到的情况一样，利用专家聚合的方法设计一个接近最优遗憾保证的算法是直接明了的。 然而，当比较类足够丰富时，例如，当最佳专家和专家集合本身随时间变化时，这种策略通常需要维护大量的权重（通常是指数级的时间范围）。 相比之下，设计既能实现接近最优遗憾又能维持合理数量权重的策略则极具挑战性。 我们考虑了三种逐渐增加难度的目标（简单遗憾、动态遗憾和稀疏动态遗憾），这些目标扩展了针对固定专家集合定义的传统概念；在每种情况下，我们都设计出了可以达到紧致遗憾界限的策略，并且这些界限能自适应地调整到比较类的参数，同时计算成本低廉。 此外，我们的算法是随时可用的，对新来的专家数量无依赖，并且完全不需要设定参数。 这些令人瞩目的成果得益于两种简单但非常有效的技巧：首先是从专家框架中引入的“弃权技巧”，它能够处理最不具挑战性的遗憾概念，但在解决更复杂的目标时受到限制。 其次是我们引入的“静音技巧”，以提供更大的灵活性。 我们展示了如何结合这两种技巧来处理最具挑战性的比较策略类别。 显示英文摘要

摘要： 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.