Главная
Study mode:
on
1
Intro
2
A Naive Algorithm
3
Median Elimination (Even-Dar et al., 2002, 2006)
4
Sample Complexity
5
A twist on perspective: Memory
6
Streaming Coin Tossing Problem
7
Comparison with the Naive Algorithm
8
Motivating Question
9
First Attempt: Proof Sketch
10
Noisy Comparisons and Multi-Armed Bandits
11
Concepts and Notations
12
First Idea
13
Main Idea: Budgeting
14
Analysis: GAME-OF-COINS
15
Top-k Coins Algorithm
16
Conclusion and Summary
Description:
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)
Add to list