Algorithms with Prediction

Explore the intersection of machine learning and algorithm design in this 30-minute lecture by Michael Mitzenmacher from Harvard University. Delve into the concept of algorithms with prediction, starting with a motivating example of search costs and the price of misprediction. Examine main results for standard queues, including known and predicted service times. Discover high-level messages and results for single-bit predictions. Investigate online problems such as caching with predictions and frequency estimation. Learn about Learned Bloom Filters and their improved setups, including partitioned versions. Gain insights into the theoretical framework and experimental results. Conclude with a summary and exploration of related themes like advice and beyond worst-case analysis, leaving you with plenty of questions to ponder.

Motivating Example: Search
Search Costs
Price of Misprediction
Main Result for Standard Queues
Known Service Times
Predicted Service Times
High Level Messages
Results for Single Bit Predictions
Online Problems : Caching
Caching with Predictions Lykouris-Vassil
Frequency Estimation with Predictions
Learned Bloom Filters
Learned Bloom Filter: Improved Setup
Partitioned Learned Bloom Filter
Theoretical Framework
Experimental Results
Summary
Related Themes: Advice
Related Themes: Beyond Worst Case Anal
Lots of Questions