Fred Zhang "Online prediction in sub-linear space"
- Event Type
- Seminar/Symposium
- Sponsor
- Illinois Computer Science
- Location
- 3401 Siebel Center for Computer Science
- Virtual
- Join online
- Date
- Apr 17, 2023 11:00 am
- Speaker
- Fred Zhang, UC Berkeley
- Contact
- Candice Steidinger
- steidin2@illinois.edu
- Views
- 87
- Originating Calendar
- Siebel School Speakers Calendar
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