Learning k-modal distributions via testing
© 2014 Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. A k-modal probability distribution over the discrete domain {1;……,n} is one whose histogram has at most k “peaks” and “valleys.” Such distributions are natural generalizations of monotone (k = 0) and unimodal (k = 1) probabil...
| Main Authors: | , , |
|---|---|
| Andre forfattere: | |
| Format: | Article |
| Sprog: | English |
| Udgivet: |
Theory of Computing Exchange
2022
|
| Online adgang: | https://hdl.handle.net/1721.1/143115 |
| _version_ | 1826201805462175744 |
|---|---|
| author | Daskalakis, C Diakonikolas, I Servedio, RA |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Daskalakis, C Diakonikolas, I Servedio, RA |
| author_sort | Daskalakis, C |
| collection | MIT |
| description | © 2014 Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. A k-modal probability distribution over the discrete domain {1;……,n} is one whose histogram has at most k “peaks” and “valleys.” Such distributions are natural generalizations of monotone (k = 0) and unimodal (k = 1) probability distributions, which have been intensively studied in probability theory and statistics. In this paper we consider the problem of learning (i. e., performing density estimation of) an unknown k-modal distribution with respect to the L1 distance. The learning algorithm is given access to independent samples drawn from an unknown k-modal distribution p, and it must output a hypothesis distribution bp such that with high probability the total variation distance between p and bp is at most e. Our main goal is to obtain computationally efficient algorithms for this problem that use (close to) an information-theoretically optimal number of samples. We give an efficient algorithm for this problem that runs in time poly(k; log(n),1/ε). For k ≤ Õ(logn), the number of samples used by our algorithm is very close (within an Õ(log(1/ε) factor) to being information-theoretically optimal. Prior to this work computationally efficient algorithms were known only for the cases k = 0;1 (Birgé 1987, 1997). A novel feature of our approach is that our learning algorithm crucially uses a new algorithm for property testing of probability distributions as a key subroutine. The learning algorithm uses the property tester to efficiently decompose the k-modal distribution into k (near-)monotone distributions, which are easier to learn. |
| first_indexed | 2024-09-23T11:57:11Z |
| format | Article |
| id | mit-1721.1/143115 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:57:11Z |
| publishDate | 2022 |
| publisher | Theory of Computing Exchange |
| record_format | dspace |
| spelling | mit-1721.1/1431152023-08-11T18:06:21Z Learning k-modal distributions via testing Daskalakis, C Diakonikolas, I Servedio, RA Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2014 Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. A k-modal probability distribution over the discrete domain {1;……,n} is one whose histogram has at most k “peaks” and “valleys.” Such distributions are natural generalizations of monotone (k = 0) and unimodal (k = 1) probability distributions, which have been intensively studied in probability theory and statistics. In this paper we consider the problem of learning (i. e., performing density estimation of) an unknown k-modal distribution with respect to the L1 distance. The learning algorithm is given access to independent samples drawn from an unknown k-modal distribution p, and it must output a hypothesis distribution bp such that with high probability the total variation distance between p and bp is at most e. Our main goal is to obtain computationally efficient algorithms for this problem that use (close to) an information-theoretically optimal number of samples. We give an efficient algorithm for this problem that runs in time poly(k; log(n),1/ε). For k ≤ Õ(logn), the number of samples used by our algorithm is very close (within an Õ(log(1/ε) factor) to being information-theoretically optimal. Prior to this work computationally efficient algorithms were known only for the cases k = 0;1 (Birgé 1987, 1997). A novel feature of our approach is that our learning algorithm crucially uses a new algorithm for property testing of probability distributions as a key subroutine. The learning algorithm uses the property tester to efficiently decompose the k-modal distribution into k (near-)monotone distributions, which are easier to learn. 2022-06-14T13:19:32Z 2022-06-14T13:19:32Z 2014-12-31 2022-06-14T12:25:57Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143115 Daskalakis, C, Diakonikolas, I and Servedio, RA. 2014. "Learning k-modal distributions via testing." Theory of Computing, 10 (1). en 10.4086/toc.2014.v010a020 Theory of Computing Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Theory of Computing Exchange Theory of Computing |
| spellingShingle | Daskalakis, C Diakonikolas, I Servedio, RA Learning k-modal distributions via testing |
| title | Learning k-modal distributions via testing |
| title_full | Learning k-modal distributions via testing |
| title_fullStr | Learning k-modal distributions via testing |
| title_full_unstemmed | Learning k-modal distributions via testing |
| title_short | Learning k-modal distributions via testing |
| title_sort | learning k modal distributions via testing |
| url | https://hdl.handle.net/1721.1/143115 |
| work_keys_str_mv | AT daskalakisc learningkmodaldistributionsviatesting AT diakonikolasi learningkmodaldistributionsviatesting AT servediora learningkmodaldistributionsviatesting |