| |
|
| |
|
Robert Kleinberg
University of California, Berkeley
Learning an Admission Threshold
June 5, 2006 11:00am
Abstract:
We will present algorithms for a class of online learning problems in which the function to be learned satisfies a monotonicity constraint. A prototypical example is the following problem. Suppose you are presented with a list of n tests, whose success probabilities form a monotonically increasing sequence. Other than this monotonicity property, you have no knowledge of the success probabilities of the tests. You must perform a sequence of experiments, each consisting of choosing one of the n tests and observing the outcome of a Bernoulli trial with the corresponding success probability. The goal is to identify the test which is closest to having a specified success probability, using as few experiments as possible. (This can be regarded as a binary search problem with noisy feedback.) We present algorithms which match the information-theoretic lower bound, up to a constant factor, for this problem and some related search problems.
This is joint work with Richard Karp.
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.