CSAIL Event Calendar

[A&C Seminar] Learning Disjunctions: Near-Optimal Trade-off Between Mistakes and "I Don't Know"s

We develop polynomial-time online algorithms for learning disjunctions. In this model, we are given an online adversarial sequence of inputs for an unknown disjunction function of the form f(x_1, x_2, ..., x_n) = OR_{i \in S} x_i , and for each such input, we must guess "true", "false", or "I don't know". On the algorithm side, we show how make at most \epsilon n mistakes while answering "I don't know" at most (1/\epsilon)^{2^{O(1/\epsilon)}} n times. Furthermore, we show how to make O(nlog(log(n))/log(n)) mistakes while answering "I don't know" O(n^2 log(log(n))) times. We also show that any algorithm making o(n/log(n)) mistakes must answer "I don't know" a superpolynomial number of times.

This is a joint work with Erik Demaine.

See other events happening in January 2013