TY - GEN

T1 - The edge density barrier

T2 - 35th International Conference on Machine Learning, ICML 2018

AU - Lu, Hao

AU - Cao, Yuan

AU - Lu, Junwei

AU - Liu, Han

AU - Wang, Zhaoran

N1 - Publisher Copyright:
© Copyright 2018 by the author(s).

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85057266383&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057266383&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85057266383

T3 - 35th International Conference on Machine Learning, ICML 2018

SP - 5119

EP - 5148

BT - 35th International Conference on Machine Learning, ICML 2018

A2 - Dy, Jennifer

A2 - Krause, Andreas

PB - International Machine Learning Society (IMLS)

Y2 - 10 July 2018 through 15 July 2018

ER -