




















We give improved tradeoffs between space and regret for the online learning with expert advice problem over $T$ days with $n$ experts. Given a space budget of $n^δ$ for $δ\in (0,1)$, we provide an algorithm achieving regret $\tilde{O}(n^2 T^{1/(1+δ)})$, improving upon the regret bound $\tilde{O}(n^2 T^{2/(2+δ)})$ in the recent work of [PZ23]. The improvement is particularly salient in the regime $δ\rightarrow 1$ where the regret of our algorithm approaches $\tilde{O}_n(\sqrt{T})$, matching the $T$ dependence in the standard online setting without space restrictions.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。