Timezone: »

 
Poster
The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference
Hao Lu · Yuan Cao · Junwei Lu · Han Liu · Zhaoran Wang

Fri Jul 13 09:15 AM -- 12:00 PM (PDT) @ Hall B #23
in Posters Fri »

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.

[ PDF] 

Author Information

Hao Lu (Princeton University)
Yuan Cao (Princeton University)
Junwei Lu
Han Liu (Princeton University)
Zhaoran Wang (Northwestern U)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors