Document Open Access Logo

Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples

Authors Ronitt Rubinfeld, Arsen Vasilyan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.28.pdf
  • Filesize: 0.65 MB
  • 34 pages

Document Identifiers

Author Details

Ronitt Rubinfeld
  • CSAIL at MIT, Cambridge, MA, USA
  • Blavatnik School of Computer Science at Tel Aviv University, Israel
Arsen Vasilyan
  • CSAIL at MIT, Cambridge, MA, USA

Funding

  • Rubinfeld, Ronitt: FinTech@CSAIL, MIT-IBM Watson AI Lab and Research Collaboration Agreement No. W1771646, and NSF Award Numbers: CCF-1650733, CCF-1740751, CCF-1733808, and IIS-1741137
  • Vasilyan, Arsen: NSF grant IIS-1741137, EECS SuperUROP program

Cite As Get BibTex

Ronitt Rubinfeld and Arsen Vasilyan. Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 28:1-28:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.28

Abstract

A probability distribution over the Boolean cube is monotone if flipping the value of a coordinate from zero to one can only increase the probability of an element. Given samples of an unknown monotone distribution over the Boolean cube, we give (to our knowledge) the first algorithm that learns an approximation of the distribution in statistical distance using a number of samples that is sublinear in the domain.
To do this, we develop a structural lemma describing monotone probability distributions. The structural lemma has further implications to the sample complexity of basic testing tasks for analyzing monotone probability distributions over the Boolean cube: We use it to give nontrivial upper bounds on the tasks of estimating the distance of a monotone distribution to uniform and of estimating the support size of a monotone distribution. In the setting of monotone probability distributions over the Boolean cube, our algorithms are the first to have sample complexity lower than known lower bounds for the same testing tasks on arbitrary (not necessarily monotone) probability distributions. 
One further consequence of our learning algorithm is an improved sample complexity for the task of testing whether a distribution on the Boolean cube is monotone.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Theory of computation
Keywords
  • Learning distributions
  • monotone probability distributions
  • estimating support size

Metrics

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

References

  1. Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal Testing for Properties of Distributions. In 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. URL: http://papers.nips.cc/paper/5839-optimal-testing-for-properties-of-distributions.
  2. Michal Adamaszek, Artur Czumaj, and Christian Sohler. Testing Monotone Continuous Distributions on High-dimensional Real Cubes. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 56-65, 2010. URL: https://doi.org/10.1137/1.9781611973075.6.
  3. Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. Towards Testing Monotonicity of Distributions Over General Posets. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 34-82, 2019. URL: http://proceedings.mlr.press/v99/aliakbarpour19a.html.
  4. Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 381-390. ACM, 2004. Google Scholar
  5. Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant. Testing monotonicity of distributions over general partial orders. In ICS, pages 239-252, 2011. Google Scholar
  6. Lucien Birgé et al. Estimating a density under order restrictions: Nonasymptotic minimax risk. The Annals of Statistics, 15(3):995-1012, 1987. Google Scholar
  7. Eric Blais, Johan Håstad, Rocco A Servedio, and Li-Yang Tan. On DNF approximators for monotone boolean functions. In International Colloquium on Automata, Languages, and Programming, pages 235-246. Springer, 2014. Google Scholar
  8. Clément L Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing shape restrictions of discrete distributions. Theory of Computing Systems, 62(1):4-62, 2018. Google Scholar
  9. Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Testing Bayesian Networks. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 370-448, 2017. URL: http://proceedings.mlr.press/v65/canonne17a.html.
  10. Siu-On Chan, Ilias Diakonikolas, Rocco A Servedio, and Xiaorui Sun. Learning mixtures of structured distributions over discrete domains. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1380-1394. Society for Industrial and Applied Mathematics, 2013. Google Scholar
  11. Siu-on Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal Algorithms for Testing Closeness of Discrete Distributions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1193-1203, 2014. URL: https://doi.org/10.1137/1.9781611973402.88.
  12. Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning k-Modal Distributions via Testing. Theory of Computing, 10:535-570, 2014. URL: https://doi.org/10.4086/toc.2014.v010a020.
  13. Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning Poisson Binomial Distributions. Algorithmica, 72(1):316-357, 2015. URL: https://doi.org/10.1007/s00453-015-9971-3.
  14. Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, and Paul Valiant. Testing k-Modal Distributions: Optimal Algorithms via Reductions. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1833-1852, 2013. URL: https://doi.org/10.1137/1.9781611973105.131.
  15. Constantinos Daskalakis and Gautam Kamath. Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians. In Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, pages 1183-1213, 2014. Google Scholar
  16. Constantinos Daskalakis, Gautam Kamath, and Christos Tzamos. On the Structure, Covering, and Learning of Poisson Multinomial Distributions. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1203-1217, 2015. URL: https://doi.org/10.1109/FOCS.2015.77.
  17. Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-Based Testers are Optimal for Uniformity and Closeness. Chicago J. Theor. Comput. Sci., 2019, 2019. URL: http://cjtcs.cs.uchicago.edu/articles/2019/1/contents.html.
  18. Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin. Testing identity of structured distributions. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1841-1854. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  19. Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Efficient robust proper learning of log-concave distributions. arXiv preprint, 2016. URL: http://arxiv.org/abs/1606.03077.
  20. Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Optimal learning via the fourier transform for sums of independent integer random variables. In Conference on Learning Theory, pages 831-849, 2016. Google Scholar
  21. Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Properly learning poisson binomial distributions in almost polynomial time. In Conference on Learning Theory, pages 850-878, 2016. Google Scholar
  22. Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt. Fast and sample near-optimal algorithms for learning multidimensional histograms. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.08513.
  23. Rong Ge, Qingqing Huang, and Sham M. Kakade. Learning Mixtures of Gaussians in High Dimensions. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 761-770, 2015. URL: https://doi.org/10.1145/2746539.2746616.
  24. 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-SIGAI symposium on Principles of Database Systems, pages 15-22. ACM, 2012. Google Scholar
  25. Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two Gaussians. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 553-562, 2010. URL: https://doi.org/10.1145/1806689.1806765.
  26. 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
  27. Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM Journal on Computing, 39(3):813-842, 2009. Google Scholar
  28. Oded Regev and Aravindan Vijayaraghavan. On Learning Mixtures of Well-Separated Gaussians. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 85-96, 2017. URL: https://doi.org/10.1109/FOCS.2017.17.
  29. Ronitt Rubinfeld and Rocco A Servedio. Testing monotone high-dimensional distributions. Random Structures & Algorithms, 34(1):24-44, 2009. Google Scholar
  30. Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new CLTs. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 685-694. ACM, 2011. Google Scholar
  31. Gregory Valiant and Paul Valiant. The power of linear estimators. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 403-412. IEEE, 2011. Google Scholar
  32. Paul Valiant. Testing symmetric properties of distributions. SIAM Journal on Computing, 40(6):1927-1968, 2011. Google Scholar
  33. Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6):3702-3720, 2016. Google Scholar
  34. Yihong Wu, Pengkun Yang, et al. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. The Annals of Statistics, 47(2):857-883, 2019. Google Scholar
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