The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference

Hao Lu, Yuan Cao, Zhuoran Yang, Junwei Lu, Han Liu, Zhaoran Wang
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3247-3256, 2018.

Abstract

We study the hypothesis testing problem of inferring the existence of combinatorial structures in undirected graphical models. Although there exist extensive studies on the information-theoretic limits of this problem, it remains largely unexplored whether such limits can be attained by efficient algorithms. In this paper, we quantify the minimum computational complexity required to attain the information-theoretic limits based on an oracle computational model. We prove that, for testing common combinatorial structures, such as clique, nearest neighbor graph and perfect matching, against an empty graph, or large clique against small clique, the information-theoretic limits are provably unachievable by tractable algorithms in general. More importantly, we define structural quantities called the weak and strong edge densities, which offer deep insight into the existence of such computational-statistical tradeoffs. To the best of our knowledge, our characterization is the first to identify and explain the fundamental tradeoffs between statistics and computation for combinatorial inference problems in undirected graphical models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-lu18a, title = {The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference}, author = {Lu, Hao and Cao, Yuan and Yang, Zhuoran and Lu, Junwei and Liu, Han and Wang, Zhaoran}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3247--3256}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/lu18a/lu18a.pdf}, url = {https://proceedings.mlr.press/v80/lu18a.html}, abstract = {We study the hypothesis testing problem of inferring the existence of combinatorial structures in undirected graphical models. Although there exist extensive studies on the information-theoretic limits of this problem, it remains largely unexplored whether such limits can be attained by efficient algorithms. In this paper, we quantify the minimum computational complexity required to attain the information-theoretic limits based on an oracle computational model. We prove that, for testing common combinatorial structures, such as clique, nearest neighbor graph and perfect matching, against an empty graph, or large clique against small clique, the information-theoretic limits are provably unachievable by tractable algorithms in general. More importantly, we define structural quantities called the weak and strong edge densities, which offer deep insight into the existence of such computational-statistical tradeoffs. To the best of our knowledge, our characterization is the first to identify and explain the fundamental tradeoffs between statistics and computation for combinatorial inference problems in undirected graphical models.} }
Endnote
%0 Conference Paper %T The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference %A Hao Lu %A Yuan Cao %A Zhuoran Yang %A Junwei Lu %A Han Liu %A Zhaoran Wang %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-lu18a %I PMLR %P 3247--3256 %U https://proceedings.mlr.press/v80/lu18a.html %V 80 %X We study the hypothesis testing problem of inferring the existence of combinatorial structures in undirected graphical models. Although there exist extensive studies on the information-theoretic limits of this problem, it remains largely unexplored whether such limits can be attained by efficient algorithms. In this paper, we quantify the minimum computational complexity required to attain the information-theoretic limits based on an oracle computational model. We prove that, for testing common combinatorial structures, such as clique, nearest neighbor graph and perfect matching, against an empty graph, or large clique against small clique, the information-theoretic limits are provably unachievable by tractable algorithms in general. More importantly, we define structural quantities called the weak and strong edge densities, which offer deep insight into the existence of such computational-statistical tradeoffs. To the best of our knowledge, our characterization is the first to identify and explain the fundamental tradeoffs between statistics and computation for combinatorial inference problems in undirected graphical models.
APA
Lu, H., Cao, Y., Yang, Z., Lu, J., Liu, H. & Wang, Z.. (2018). The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3247-3256 Available from https://proceedings.mlr.press/v80/lu18a.html.

Related Material