论文标题
子线性空间中的在线预测
Online Prediction in Sub-linear Space
论文作者
论文摘要
我们提供了第一个以专家建议（反对遗忘的对手）为在线学习的第一个亚线性空间和子线性遗憾算法，并解决了Srinivas，Woodruff，Xu和Zhou最近提出的一个公开问题（STOC 2022）。我们还通过证明对自适应对手的任何子线性遗憾算法的线性记忆下限，证明了遗忘和（强）适应对手之间的分离。我们的算法是基于一种新颖的池选择程序，该程序绕过了传统的在线学习领导者选择的智慧，并将任何弱的次线性遗憾$ O（t）$算法转化为$ t^{1-α} $遗憾算法，这可能是独立的，这可能是独立的。我们的下边界利用了零和游戏中无需重新学习和平衡计算的连接，从而证明了与自适应对手相对于自适应对手的强大下限。
We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC 2022). We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary. Our algorithm is based on a novel pool selection procedure that bypasses the traditional wisdom of leader selection for online learning, and a generic reduction that transforms any weakly sub-linear regret $o(T)$ algorithm to $T^{1-α}$ regret algorithm, which may be of independent interest. Our lower bound utilizes the connection of no-regret learning and equilibrium computation in zero-sum games, leading to a proof of a strong lower bound against an adaptive adversary.
