Abstract:
We design the first sub-linear memory algorithm for online learning with expert advice, arguably the most basic question in online and sequential decision making. This problem is solved classically by the well-known multiplicative weights update method, which achieves optimal regret but suffers a linear space complexity. We show how to bypass this barrier. In this talk, I will discuss the main techniques, recent followup works, and many open directions.
Based on joint work with Binghui Peng. SODA '23. https://arxiv.org/abs/2207.07974
