YoVDO

Exploration with Limited Memory - Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits

Offered By: Association for Computing Machinery (ACM) via YouTube

Tags

Probabilistic Methods Courses Multi-Armed Bandits Courses Sample Complexity Courses

Course Description

Overview

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.

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)

Related Courses

Probability for Computer Science
Indian Institute of Technology Kanpur via Swayam
Probabilistic Methods for Increased Robustness in Machine Learning
Alan Turing Institute via YouTube
Stochastic Weighted Matching - 1-Epsilon Approximation
IEEE via YouTube
X-Ramanujan Graphs
Simons Institute via YouTube
Advances in Applied Probability II
International Centre for Theoretical Sciences via YouTube