Online Prediction in Sub-linear Space

Channel:
United States Google TechTalks
Subscribers:
348,000
Published on ● Video Link: https://www.youtube.com/watch?v=7YiSSyOzMsI


Duration: 59:32
542 views
13

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.



Other Videos By Google TechTalks


2023-07-032023 Blockly Developer Summit Day 1-8: Blocks in Docs
2023-07-032023 Blockly Developer Summit Day 2-16: Curriculum Development Panel Discussion
2023-07-032023 Blockly Developer Summit DAY 1-6: Generative Block Programming in MIT App Inventor
2023-07-032023 Blockly Developer Summit Day 2-11: Onboarding New Users
2023-07-032023 Blockly Developer Summit Day 2-15: Thoughts on Bidirectional Text to Blocks to Text
2023-07-032023 Blockly Developer Summit Day 2-6: Code.org - Sprite Lab
2023-07-032023 Blockly Developers Summit Day 1-1: Welcome
2023-07-032023 Blockly Developer Summit Day 2-7: How to Convince Teachers to Teach Coding
2023-06-29A Constant Factor Prophet Inequality for Online Combinatorial Auctions
2023-06-21Open Problems in Mechanistic Interpretability: A Whirlwind Tour
2023-06-11Online Prediction in Sub-linear Space
2023-06-06Accelerating Transformers via Kernel Density Estimation Insu Han
2023-06-06Differentially Private Synthetic Data via Foundation Model APIs
2023-06-05Foundation Models and Fair Use
2023-05-30Differentially Private Online to Batch
2023-05-30Differentially Private Diffusion Models Generate Useful Synthetic Images
2023-05-30Improving the Privacy Utility Tradeoff in Differentially Private Machine Learning with Public Data
2023-05-30Randomized Approach for Tight Privacy Accounting
2023-05-30Almost Tight Error Bounds on Differentially Private Continual Counting
2023-05-30EIFFeL: Ensuring Integrity for Federated Learning
2023-05-30Differentially Private Diffusion Models