| Andrew Drucker |
| Tue 17 Mar 2015, 16:00 - 17:00 |
| Informatics Forum (IF-4.31/4.33) |
If you have a question about this talk, please contact: Rik Sarkar (rsarkar)
Speaker: Andrew Drucker, University of Edinburgh
Title: Confident predictions against an adversary
Venue: Tuesday March 17, 16:00, Room IF 4.31/4.33
Confident predictions against an adversary
Andrew Drucker
Abstract: We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that quite limited assumptions about x allow one to make nontrivial predictions about unseen bits.
Our main focus is the task of predicting a single 0 from among the bits of x, at a time of our choosing. This models various situations in which we must perform an action of fixed duration, and must predict a "safe" time to perform it. We give a randomized algorithm that succeeds (with high probability) against any sequence x whose 1s are sufficiently sparse in the limit. Subject to this mild condition, the sequence need not be generated according to a known probabilistic model, but may be chosen adversarially.
Reference:
[A. Drucker, High-confidence predictions under adversarial uncertainty. ITCS'12/TOCT'13]