Big data on the rise? Testing monotonicity of distributions. (English) Zbl 1441.68281
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 294-305 (2015).
Summary: The field of property testing of probability distributions, or distribution testing, aims to provide fast and (most likely) correct answers to questions pertaining to specific aspects of very large datasets. In this work, we consider a property of particular interest, monotonicity of distributions. We focus on the complexity of monotonicity testing across different models of access to the distributions
[the author et al., SIAM J. Comput. 44, No. 3, 540–616 (2015; Zbl 1328.68293); the author and R. Rubinfeld, Lect. Notes Comput. Sci. 8572, 283–295 (2014; Zbl 1409.68326); S. Chakraborty et al., in: Proceedings of the 4th conference on innovations in theoretical computer science, ITCS’13. New York, NY: Association for Computing Machinery (ACM). 561–580 (2013; Zbl 1362.68288); R. Rubinfeld and R. A. Servedio, Random Struct. Algorithms 34, No. 1, 24–44 (2009; Zbl 1165.62037)];
and obtain results in these new settings that differ significantly (and somewhat surprisingly) from the known bounds in the standard sampling model
[T. Batu et al., in: Proceedings of the 36th annual ACM symposium on theory of computing, STOC’04. New York, NY: ACM Press. 381–390 (2004; Zbl 1192.68345)].
For the entire collection see [Zbl 1316.68014].
For the entire collection see [Zbl 1316.68014].
MSC:
| 68W20 | Randomized algorithms |
| 62R07 | Statistical aspects of big data and data science |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Batu, T., Kumar, R., Rubinfeld, R.: Sublinear algorithms for testing monotone and unimodal distributions. In: Proceedings of STOC, pp. 381-390. ACM, New York (2004) · Zbl 1192.68345 |
| [2] | Birgé, L., On the risk of histograms for estimating decreasing densities, The Annals of Statistics, 15, 3, 1013-1022 (1987) · Zbl 0646.62033 · doi:10.1214/aos/1176350489 |
| [3] | Canonne, C.L.: A Survey on Distribution Testing: Your Data is Big. But is it Blue? Electronic Colloquium on Computational Complexity (ECCC) 22, 63 (2015) |
| [4] | Canonne, C.L.: Big Data on the Rise: Testing monotonicity of distributions. ArXiV:abs/1501.06783 (2015) · Zbl 1441.68281 |
| [5] | Canonne, C.L., Ron, D., Servedio, R.A.: Testing probability distributions using conditional samples. ArXiV:abs/1211.2664, November 2012 · Zbl 1328.68293 |
| [6] | Canonne, C.L., Ron, D., Servedio, R.A.: Testing equivalence between distributions using conditional samples. In: Proceedings of SODA, pp. 1174-1192. SIAM (2014), see also [5] (full version) · Zbl 1421.68183 |
| [7] | Canonne, C.L., Rubinfeld, R.: Testing probability distributions underlying aggregated data. In: Proceedings of ICALP, pp. 283-295 (2014) · Zbl 1409.68326 |
| [8] | Chakraborty, S., Fischer, E., Goldhirsh, Y., Matsliah, A.: On the power of conditional samples in distribution testing. In: Proceedings of ITCS, pp. 561-580. ACM, New York (2013) · Zbl 1362.68288 |
| [9] | Daskalakis, C., Diakonikolas, I., Servedio, R.A.: Learning \(k\)-modal distributions via testing. In: Proceedings of SODA, pp. 1371-1385. SIAM (2012) · Zbl 1421.68091 |
| [10] | Daskalakis, C., Diakonikolas, I., Servedio, R.A., Valiant, G., Valiant, P.: Testing \(k\)-modal distributions: Optimal algorithms via reductions. In: Proceedings of SODA, pp. 1833-1852. SIAM (2013) · Zbl 1421.68187 |
| [11] | Fischer, E., The art of uninformed decisions: A primer to property testing, BEATCS, 75, 97-126 (2001) · Zbl 1024.68045 |
| [12] | Goldreich, O., Property Testing: Current Research and Surveys (2010), Heidelberg: Springer, Heidelberg · Zbl 1197.68012 |
| [13] | Goldreich, O., Ron, D.: On testing expansion in bounded-degree graphs. Technical report, TR00-020, Electronic Colloquium on Computational Complexity (ECCC) (2000) |
| [14] | Guha, S., McGregor, A., Venkatasubramanian, S.: Streaming and sublinear approximation of entropy and information distances. In: Proceedings of SODA, pp. 733-742. SIAM, Philadelphia (2006) · Zbl 1192.94075 |
| [15] | Paninski, L., A coincidence-based test for uniformity given very sparsely sampled discrete data, IEEE Transactions on Information Theory, 54, 10, 4750-4755 (2008) · Zbl 1322.62082 · doi:10.1109/TIT.2008.928987 |
| [16] | Pearson, K.: Contributions to the Mathematical Theory of Evolution. Philosophical Transactions of the Royal Society of London. (A.) 185, 71-110 (1894) · JFM 25.0347.02 |
| [17] | Ron, D., Property Testing: A Learning Theory Perspective, Foundations and Trends in Machine Learning, 1, 3, 307-402 (2008) · doi:10.1561/2200000004 |
| [18] | Ron, D., Algorithmic and analysis techniques in property testing, Foundations and Trends in Theoretical Computer Science, 5, 73-205 (2010) · Zbl 1184.68610 · doi:10.1561/0400000029 |
| [19] | Rubinfeld, R., Taming Big Probability Distributions, XRDS, 19, 1, 24-28 (2012) · doi:10.1145/2331042.2331052 |
| [20] | Rubinfeld, R.; Servedio, RA, Testing monotone high-dimensional distributions, Random Structures and Algorithms, 34, 1, 24-44 (2009) · Zbl 1165.62037 · doi:10.1002/rsa.20247 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
