Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows”
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(x1, x2,..., xn) = Viεs[sup...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86204 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826200278743908352 |
|---|---|
| author | Demaine, Erik D. Zadimoghaddam, Morteza |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Zadimoghaddam, Morteza |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 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(x1, x2,..., xn) = Viεs[superscript xi], 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/ε)[superscript 2O(1/ε)] times, which is linear for any constant ε > 0 and polynomial for some ε = c/lg lg n. Furthermore, we show how to make 0 (n [log log n over log n]) mistakes while answering “I don't know” O(n[superscript 2] 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 1/3n 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[superscript 2]) 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”. The running time of our algorithms (per answer) are (1/ε)[superscript 2O(1/ε)] n and Õ(n[superscript 3]), respectively, whereas the first previous algorithm mentioned above makes many mistakes, and the second one requires Θ(2[superscript n]) 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[superscript 1/ε]) which is super polynomial for any non-constant ε. |
| first_indexed | 2024-09-23T11:34:02Z |
| format | Article |
| id | mit-1721.1/86204 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:34:02Z |
| publishDate | 2014 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/862042022-09-27T20:22:30Z Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows” Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms Demaine, Erik D. Zadimoghaddam, Morteza Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Zadimoghaddam, Morteza 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(x1, x2,..., xn) = Viεs[superscript xi], 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/ε)[superscript 2O(1/ε)] times, which is linear for any constant ε > 0 and polynomial for some ε = c/lg lg n. Furthermore, we show how to make 0 (n [log log n over log n]) mistakes while answering “I don't know” O(n[superscript 2] 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 1/3n 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[superscript 2]) 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”. The running time of our algorithms (per answer) are (1/ε)[superscript 2O(1/ε)] n and Õ(n[superscript 3]), respectively, whereas the first previous algorithm mentioned above makes many mistakes, and the second one requires Θ(2[superscript n]) 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[superscript 1/ε]) which is super polynomial for any non-constant ε. 2014-04-17T18:45:30Z 2014-04-17T18:45:30Z 2013-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-61197-251-1 978-1-61197-310-5 http://hdl.handle.net/1721.1/86204 Demaine, Erik D., and Morteza Zadimoghaddam. “Learning Disjunctions: Near-Optimal Trade-Off Between Mistakes and ‘I Don’t Knows.’” Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (January 6, 2013): 1369–1379. © 2014 SIAM https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1137/1.9781611973105.99 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Demaine, Erik D. Zadimoghaddam, Morteza Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows” |
| title | Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows” |
| title_full | Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows” |
| title_fullStr | Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows” |
| title_full_unstemmed | Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows” |
| title_short | Learning Disjunctions: Near-Optimal Trade-off between Mistakes and “I Don't Knows” |
| title_sort | learning disjunctions near optimal trade off between mistakes and i don t knows |
| url | http://hdl.handle.net/1721.1/86204 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd learningdisjunctionsnearoptimaltradeoffbetweenmistakesandidontknows AT zadimoghaddammorteza learningdisjunctionsnearoptimaltradeoffbetweenmistakesandidontknows AT demaineerikd proceedingsofthetwentyfourthannualacmsiamsymposiumondiscretealgorithms AT zadimoghaddammorteza proceedingsofthetwentyfourthannualacmsiamsymposiumondiscretealgorithms |