Document Open Access Logo

Improving and Extending the Testing of Distributions for Shape-Restricted Properties

Authors Eldar Fischer, Oded Lachish, Yadu Vasudev

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.31.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Eldar Fischer
Oded Lachish
Yadu Vasudev

Cite As Get BibTex

Eldar Fischer, Oded Lachish, and Yadu Vasudev. Improving and Extending the Testing of Distributions for Shape-Restricted Properties. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.31

Abstract

Distribution testing deals with what information can be deduced about an unknown distribution over {1,...,n}, where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended conditional sampling model, the algorithm is also allowed to obtain samples from the restriction of the original distribution on subsets of {1,...,n}.
  
In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified several previous results, and showed that for any property of distributions satisfying a "decomposability" criterion, there exists an algorithm (in the basic model) that can distinguish with high probability distributions satisfying the property from distributions that are far from it in variation distance.
  
We present here a more efficient yet simpler algorithm for the basic model, as well as very efficient algorithms for the conditional model, which until now was not investigated under the umbrella of decomposable properties. Additionally, we provide an algorithm for the conditional model that handles a much larger class of properties.
  
Our core mechanism is a way of efficiently producing an interval-partition of {1,...,n} that satisfies a "fine-grain" quality. We show that with such a partition at hand we can directly move forward with testing individual intervals, instead of first searching for the "correct" partition of {1,...,n}.

Subject Classification

Keywords
  • conditional sampling
  • distribution testing
  • property testing
  • statistics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A chasm between identity and equivalence testing with conditional queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, pages 449-466, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.449.
  2. Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 3591-3599, 2015. Google Scholar
  3. Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC'07, pages 496-505. ACM, 2007. URL: http://dx.doi.org/10.1145/1250790.1250863.
  4. Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 442-451, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959920.
  5. Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that distributions are close. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 259-269. IEEE Computer Society, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892113.
  6. Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 381-390. ACM, 2004. URL: http://dx.doi.org/10.1145/1007352.1007414.
  7. Clément L. Canonne. A survey on distribution testing: Your data is big. but is it blue? Electronic Colloquium on Computational Complexity (ECCC), 22:63, 2015. Google Scholar
  8. Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing shape restrictions of discrete distributions. CoRR, abs/1507.03558, 2015. Google Scholar
  9. Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing probability distributions using conditional samples. SIAM J. Comput., 44(3):540-616, 2015. URL: http://dx.doi.org/10.1137/130945508.
  10. Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. In Innovations in Theoretical Computer Science, ITCS'13, Berkeley, CA, USA, January 9-12, 2013, pages 561-580, 2013. URL: http://dx.doi.org/10.1145/2422436.2422497.
  11. Ilias Diakonikolas. Learning structured distributions. Handbook of Big Data, page 267, 2016. Google Scholar
  12. Ilias Diakonikolas and Daniel M. Kane. A new approach for testing properties of discrete distributions. CoRR, abs/1601.05557, 2016. Google Scholar
  13. Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan. Testing for concise representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 549-558, 2007. URL: http://dx.doi.org/10.1109/FOCS.2007.70.
  14. Eldar Fischer, Oded Lachish, and Yadu Vasudev. Improving and extending the testing of distributions for shape-restricted properties. CoRR, abs/1609.06736, 2016. URL: http://arxiv.org/abs/1609.06736.
  15. Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Electronic Colloquium on Computational Complexity (ECCC), 7(20), 2000. Google Scholar
  16. Piotr Indyk, Reut Levi, and Ronitt Rubinfeld. Approximating and testing k-histogram distributions in sub-linear time. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 15-22, 2012. URL: http://dx.doi.org/10.1145/2213556.2213561.
  17. Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory, 54(10):4750-4755, 2008. Google Scholar
  18. Rocco A. Servedio. Testing by implicit learning: A brief survey. In Property Testing - Current Research and Surveys [outgrow of a workshop at the Institute for Computer Science (ITCS) at Tsinghua University, January 2010], pages 197-210, 2010. URL: http://dx.doi.org/10.1007/978-3-642-16367-8_11.
  19. Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 51-60, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.14.
  20. Paul Valiant. Testing symmetric properties of distributions. SIAM J. Comput., 40(6):1927-1968, 2011. URL: http://dx.doi.org/10.1137/080734066.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact