Online Prediction in Sub-linear Space
Online Prediction in Sub-linear Space
复制标题
DOI：
10.48550/arxiv.2207.07974
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Binghui Peng;Fred Zhang
中科院分区：
文献类型：
--
作者：
Binghui Peng;Fred Zhang
我们提供了第一个次线性空间和次线性后悔算法，用于在线学习，并提供了专家建议（针对一个不经意的对手），解决了Srinivas，Woodruff，Xu和Zhou最近提出的一个悬而未决的问题（STOC 2022）。我们还证明了遗忘和（强）自适应对手之间的分离证明了一个线性记忆下界的任何次线性后悔算法对自适应对手。我们的算法是基于一个新的池选择过程，绕过传统的智慧的领导者选择在线学习，和一个通用的减少，转换任何弱次线性后悔$o（T）$算法到$T^{1-\alpha}$后悔算法，这可能是独立的利益。我们的下界利用零和游戏中的无悔学习和均衡计算的连接，从而证明了一个强大的下界对自适应对手。
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-\alpha}$ 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.