Dive into a 24-minute conference talk exploring streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits with limited memory. Learn about the naive algorithm, median elimination, and sample complexity before delving into the streaming coin tossing problem. Discover how this perspective twist relates to memory limitations and compare it with the naive approach. Explore noisy comparisons and multi-armed bandits, understanding key concepts and notations. Gain insights into budgeting techniques and analyze the GAME-OF-COINS algorithm. Conclude with an overview of the Top-k Coins Algorithm and a comprehensive summary of the presented concepts.
Exploration with Limited Memory - Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
A Naive Algorithm
Median Elimination (Even-Dar et al., 2002, 2006)
Sample Complexity
A twist on perspective: Memory
Streaming Coin Tossing Problem
Comparison with the Naive Algorithm
Motivating Question
First Attempt: Proof Sketch
Noisy Comparisons and Multi-Armed Bandits
Concepts and Notations
First Idea
Main Idea: Budgeting
Analysis: GAME-OF-COINS
Top-k Coins Algorithm
Conclusion and Summary
Taught by
Association for Computing Machinery (ACM)
