Grainger College of Engineering Seminars & Speakers

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