When:
Thursday, April 20, 2023
4:00 PM - 5:00 PM CT
Where: Technological Institute, M152, 2145 Sheridan Road, Evanston, IL 60208 map it
Audience: Faculty/Staff - Student - Post Docs/Docs - Graduate Students
Contact:
Xiaolin Wang
Group: Department of Computer Science (CS)
Category: Academic
Thursday / Theory Seminar
April 20th /4:00 PM
Tech M152
Title: Online prediction in sub-linear space
Speaker: Fred Zhang
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).
Biography:
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.