Online Prediction in Sub-linear Space

A Google TechTalk, presented by Fred Zhang, 2023/06/06 Google Algorithms Seminar. 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. Joint work with Binghui Peng (https://arxiv.org/abs/2207.07974, SODA 23). About the speaker: Fred Zhang is a fifth-year PhD student in the theory group at Berkeley, advised by Jelani Nelson. He is broadly interested in algorithmic questions in learning and statistics.