Towards Testing Monotonicity of Distributions Over General Posets

Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:34-82, 2019.

Abstract

In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is {\em monotone} if, for any pair of domain elements $x$ and $y$ such that $x \preceq y$, $p(x) \leq p(y)$. To understand the sample complexity of this problem, we introduce a new property called \emph{bigness} over a finite domain, where the distribution is $T$-big if the minimum probability for any domain element is at least $T$. We establish a lower bound of $\Omega(n/\log n)$ for testing bigness of distributions on domains of size $n$. We then build on these lower bounds to give $\Omega(n/\log{n})$ lower bounds for testing monotonicity over a matching poset of size $n$ and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-aliakbarpour19a, title = {Towards Testing Monotonicity of Distributions Over General Posets}, author = {Aliakbarpour, Maryam and Gouleakis, Themis and Peebles, John and Rubinfeld, Ronitt and Yodpinyanee, Anak}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {34--82}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/aliakbarpour19a/aliakbarpour19a.pdf}, url = {https://proceedings.mlr.press/v99/aliakbarpour19a.html}, abstract = {In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is {\em monotone} if, for any pair of domain elements $x$ and $y$ such that $x \preceq y$, $p(x) \leq p(y)$. To understand the sample complexity of this problem, we introduce a new property called \emph{bigness} over a finite domain, where the distribution is $T$-big if the minimum probability for any domain element is at least $T$. We establish a lower bound of $\Omega(n/\log n)$ for testing bigness of distributions on domains of size $n$. We then build on these lower bounds to give $\Omega(n/\log{n})$ lower bounds for testing monotonicity over a matching poset of size $n$ and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem. } }
Endnote
%0 Conference Paper %T Towards Testing Monotonicity of Distributions Over General Posets %A Maryam Aliakbarpour %A Themis Gouleakis %A John Peebles %A Ronitt Rubinfeld %A Anak Yodpinyanee %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-aliakbarpour19a %I PMLR %P 34--82 %U https://proceedings.mlr.press/v99/aliakbarpour19a.html %V 99 %X In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is {\em monotone} if, for any pair of domain elements $x$ and $y$ such that $x \preceq y$, $p(x) \leq p(y)$. To understand the sample complexity of this problem, we introduce a new property called \emph{bigness} over a finite domain, where the distribution is $T$-big if the minimum probability for any domain element is at least $T$. We establish a lower bound of $\Omega(n/\log n)$ for testing bigness of distributions on domains of size $n$. We then build on these lower bounds to give $\Omega(n/\log{n})$ lower bounds for testing monotonicity over a matching poset of size $n$ and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem.
APA
Aliakbarpour, M., Gouleakis, T., Peebles, J., Rubinfeld, R. & Yodpinyanee, A.. (2019). Towards Testing Monotonicity of Distributions Over General Posets. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:34-82 Available from https://proceedings.mlr.press/v99/aliakbarpour19a.html.

Related Material