Online learning with expert advice is a fundamental problem of sequential prediction. In this problem, the algorithm has access to a set of $n$ "experts" who make predictions on each day. The goal on each day is to process these predictions, and make a prediction with the minimum cost. After making a prediction, the algorithm sees the actual outcome on that day, updates its state, and then moves on to the next day. An algorithm is judged by how well it does compared to the best expert in the set. The classical algorithm for this problem is the multiplicative weights algorithm. However, every application, to our knowledge, relies on storing weights for every expert, and uses $\Omega(n)$ memory. There is little work on understanding the memory required to solve the online learning with expert advice problem, or run standard sequential prediction algorithms, in natural streaming models, which is especially important when the number of experts, as well as the number of days on which the experts make predictions, is large. We initiate the study of the learning with expert advice problem in the streaming setting, and show lower and upper bounds. Our lower bound for i.i.d., random order, and adversarial order streams uses a reduction to a custom-built problem using a novel masking technique, to show a smooth trade-off for regret versus memory. Our upper bounds show novel ways to run standard sequential prediction algorithms in rounds on small "pools" of experts, thus reducing the necessary memory. For random-order streams, we show that our upper bound is tight up to low order terms. We hope that these results and techniques will have broad applications in online learning, and can inspire algorithms based on standard sequential prediction techniques, like multiplicative weights, for a wide range of other problems in the memory-constrained setting.
翻译:通过专家咨询在线学习是连续预测的根本问题。 在这个问题中, 算法可以获取每天作出预测的一组美元“ 专家” 。 每天的目标是处理这些预测, 并以最低成本进行预测。 在作出预测后, 算法会看到当日的实际结果, 更新其状态, 然后继续到第二天。 算法会根据它与集中最佳专家相比的成绩来判断。 这个问题的典型算法是多复制加权算法。 但是, 每一个应用程序, 根据我们的知识, 都依赖于每个专家的存储权重, 并使用 $\ omega (n) 内存 。 在理解用专家咨询问题解决在线学习所需的记忆, 或者在自然流模型中运行标准的序列预测算算法。 当专家人数和专家作出类似预测的天数都很大的时候, 我们开始研究流中的专家建议的结果, 并且显示更低和上层的内存。 因此, 我们的内存和上层的内存技术将显示一个更低的顺序。