Computational and Statistical Tradeoffs in Inferring Combinatorial Structures of Ising Model

Ying Jin, Zhaoran Wang, Junwei Lu
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:4901-4910, 2020.

Abstract

We study the computational and statistical tradeoffs in inferring combinatorial structures of high dimensional simple zero-field ferromagnetic Ising model. Under the framework of oracle computational model where an algorithm interacts with an oracle that discourses a randomized version of truth, we characterize the computational lower bounds of learning combinatorial structures in polynomial time, under which no algorithms within polynomial-time can distinguish between graphs with and without certain structures. This hardness of learning with limited computational budget is shown to be characterized by a novel quantity called vertex overlap ratio. Such quantity is universally valid for many specific graph structures including cliques and nearest neighbors. On the other side, we attain the optimal rates for testing these structures against empty graph by proposing the quadratic testing statistics to match the lower bounds. We also investigate the relationship between computational bounds and information-theoretic bounds for such problems, and found gaps between the two boundaries in inferring some particular structures, especially for those with dense edges.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-jin20g, title = {Computational and Statistical Tradeoffs in Inferring Combinatorial Structures of Ising Model}, author = {Jin, Ying and Wang, Zhaoran and Lu, Junwei}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {4901--4910}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/jin20g/jin20g.pdf}, url = {https://proceedings.mlr.press/v119/jin20g.html}, abstract = {We study the computational and statistical tradeoffs in inferring combinatorial structures of high dimensional simple zero-field ferromagnetic Ising model. Under the framework of oracle computational model where an algorithm interacts with an oracle that discourses a randomized version of truth, we characterize the computational lower bounds of learning combinatorial structures in polynomial time, under which no algorithms within polynomial-time can distinguish between graphs with and without certain structures. This hardness of learning with limited computational budget is shown to be characterized by a novel quantity called vertex overlap ratio. Such quantity is universally valid for many specific graph structures including cliques and nearest neighbors. On the other side, we attain the optimal rates for testing these structures against empty graph by proposing the quadratic testing statistics to match the lower bounds. We also investigate the relationship between computational bounds and information-theoretic bounds for such problems, and found gaps between the two boundaries in inferring some particular structures, especially for those with dense edges.} }
Endnote
%0 Conference Paper %T Computational and Statistical Tradeoffs in Inferring Combinatorial Structures of Ising Model %A Ying Jin %A Zhaoran Wang %A Junwei Lu %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-jin20g %I PMLR %P 4901--4910 %U https://proceedings.mlr.press/v119/jin20g.html %V 119 %X We study the computational and statistical tradeoffs in inferring combinatorial structures of high dimensional simple zero-field ferromagnetic Ising model. Under the framework of oracle computational model where an algorithm interacts with an oracle that discourses a randomized version of truth, we characterize the computational lower bounds of learning combinatorial structures in polynomial time, under which no algorithms within polynomial-time can distinguish between graphs with and without certain structures. This hardness of learning with limited computational budget is shown to be characterized by a novel quantity called vertex overlap ratio. Such quantity is universally valid for many specific graph structures including cliques and nearest neighbors. On the other side, we attain the optimal rates for testing these structures against empty graph by proposing the quadratic testing statistics to match the lower bounds. We also investigate the relationship between computational bounds and information-theoretic bounds for such problems, and found gaps between the two boundaries in inferring some particular structures, especially for those with dense edges.
APA
Jin, Y., Wang, Z. & Lu, J.. (2020). Computational and Statistical Tradeoffs in Inferring Combinatorial Structures of Ising Model. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:4901-4910 Available from https://proceedings.mlr.press/v119/jin20g.html.

Related Material