Improved Space Bounds for Learning with Experts
This work addresses space-efficient learning for scenarios with limited memory, representing an incremental improvement over recent results.
The paper tackles the problem of online learning with expert advice under space constraints, achieving an improved regret bound of $ ilde{O}(n^2 T^{1/(1+\delta)})$ compared to prior work, which approaches $ ilde{O}_n(\sqrt{T})$ as $\delta ightarrow 1$.
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.