Testing Probability Distributions Underlying Aggregated Data
In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution D over [n]. More precisely, we consider both the dual and cumu...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101001 https://orcid.org/0000-0002-4353-7639 |
| _version_ | 1826207961895141376 |
|---|---|
| author | Canonne, Clement Rubinfeld, Ronitt |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Canonne, Clement Rubinfeld, Ronitt |
| author_sort | Canonne, Clement |
| collection | MIT |
| description | In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution D over [n]. More precisely, we consider both the dual and cumulative dual access models, in which the algorithm A can both sample from D and respectively, for any i ∈ [n],
query the probability mass D(i) (query access); or
get the total mass of {1,…,i}, i.e. ∑[i over j=1] D(j) (cumulative access)
In these two models, we bypass the strong lower bounds established in both of the previously studied sampling and query oracle settings for a number of problems, giving constant-query algorithms for most of them. Finally, we show that while the testing algorithms can be in most cases strictly more efficient, some tasks remain hard even with this additional power. |
| first_indexed | 2024-09-23T13:57:41Z |
| format | Article |
| id | mit-1721.1/101001 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:57:41Z |
| publishDate | 2016 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1010012022-10-01T18:18:07Z Testing Probability Distributions Underlying Aggregated Data Canonne, Clement Rubinfeld, Ronitt Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Rubinfeld, Ronitt In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution D over [n]. More precisely, we consider both the dual and cumulative dual access models, in which the algorithm A can both sample from D and respectively, for any i ∈ [n], query the probability mass D(i) (query access); or get the total mass of {1,…,i}, i.e. ∑[i over j=1] D(j) (cumulative access) In these two models, we bypass the strong lower bounds established in both of the previously studied sampling and query oracle settings for a number of problems, giving constant-query algorithms for most of them. Finally, we show that while the testing algorithms can be in most cases strictly more efficient, some tasks remain hard even with this additional power. National Science Foundation (U.S.) (Grant CCF-1217423) National Science Foundation (U.S.) (Grant CCF-1065125) 2016-01-27T16:55:34Z 2016-01-27T16:55:34Z 2014 Article http://purl.org/eprint/type/ConferencePaper 978-3-662-43947-0 978-3-662-43948-7 0302-9743 1611-3349 http://hdl.handle.net/1721.1/101001 Canonne, Clement, and Ronitt Rubinfeld. “Testing Probability Distributions Underlying Aggregated Data.” Lecture Notes in Computer Science (2014): 283–295. https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.1007/978-3-662-43948-7_24 Automata, Languages, and Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Canonne, Clement Rubinfeld, Ronitt Testing Probability Distributions Underlying Aggregated Data |
| title | Testing Probability Distributions Underlying Aggregated Data |
| title_full | Testing Probability Distributions Underlying Aggregated Data |
| title_fullStr | Testing Probability Distributions Underlying Aggregated Data |
| title_full_unstemmed | Testing Probability Distributions Underlying Aggregated Data |
| title_short | Testing Probability Distributions Underlying Aggregated Data |
| title_sort | testing probability distributions underlying aggregated data |
| url | http://hdl.handle.net/1721.1/101001 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT canonneclement testingprobabilitydistributionsunderlyingaggregateddata AT rubinfeldronitt testingprobabilitydistributionsunderlyingaggregateddata |