Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Morteza Zadimoghaddam, “Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Know's””, in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, Louisiana, January 6–8, 2013, pages 1369–1379.

Abstract:

We develop polynomial-time online algorithms for learning disjunctions while trading off between the number of mistakes and the number of “I don't know” answers. In this model, we are given an online adversarial sequence of inputs for an unknown function of the form f(x₁, x₂, …, x_n) = ∨_i ∈ S x_i, and for each such input, we must guess “true”, “false”, or “I don't know”, after which we find out the correct output for that input. On the algorithm side, we show how to make at most ε n mistakes while answering “I don't know” at most (1/ε)^2O(1/ε) n times, which is linear for any constant ε > 0 and polynomial for some ε = c / lg lg n. Furthermore, we show how to make O(n log log n / log n) mistakes while answering “I don't know” O(n² log log n) times. On the lower bound side, we show that any algorithm making o(n / log n) mistakes must answer “I don't know” a superpolynomial number of times. By contrast, no previous lower bounds were known, and the best previous algorithms (by Sayedi et al. who introduced the model) either make at most n/3 mistakes while answering “I don't know” O(n) times with linear running time per answer, or make O(n / log n) mistakes while answering “I don't know” O(n²) times with exponential running time per answer. Our lower bound establishes optimality of the latter mistake bound, assuming a polynomial number of “I don't know”s. The running time of our algorithms (per answer) are (1/ε)^2O(1/ε) n and Õ(n³), respectively, whereas the first previous algorithm mentioned above makes many mistakes, and the second one requires Θ(2ⁿ) time per answer. The only previous polynomial-time algorithm with reasonable number of mistakes achieves a mistake bound of ε n and an “I don't know” bound of O(n^1/ε) which is super polynomial for any non-constant ε.

Comments:

This paper is also available from SIAM.

Availability:

The paper is available in PostScript (702k), gzipped PostScript (340k), and PDF (374k).

See information on file formats.

[Google Scholar search]