Improved Space Bounds for Learning with Experts

03/02/2023

∙

by   Anders Aamand, et al.

∙

0

∙

share

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 δ∈ (0,1), we provide an algorithm achieving regret Õ(n^2 T^1/(1+δ)), improving upon the regret bound Õ(n^2 T^2/(2+δ)) in the recent work of [PZ23]. The improvement is particularly salient in the regime δ→ 1 where the regret of our algorithm approaches Õ_n(√(T)), matching the T dependence in the standard online setting without space restrictions.