Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

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

Chen Wang (Rutgers)

Location:  Core 301
Date & time: Wednesday, 11 March 2020 at 11:00AM - 12:00PM


Abstract: Consider the following abstract coin tossing problem: Given a set of n coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time.

Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. We will present an algorithm for this problem that simultaneously achieve asymptotically optimal sample complexity and space complexity which turns out to be surprisingly small. Furthermore, we extend our results to the problem of finding the k most biased coins as well as other exploration problems such as finding top-k elements using noisy comparisons or finding an ?-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.

Join work with Sepehr Assadi.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.