COMBINATORIAL INFERENCE FOR GRAPHICAL MODELS

• 成果类型: Article
• 署名作者: Neykov, Matey; Lu, Junwei; Liu, Han
• 署名单位: Carnegie Mellon University; Princeton University; Northwestern University; Northwestern University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/17-AOS1650
• 发表日期: 2019
• 页码: 795-827
• 关键词: false discovery rate; COVARIANCE ESTIMATION; confidence-intervals; principal-components; Minimax Rates; CONVERGENCE

摘要

We propose a new family of combinatorial inference problems for graphical models. Unlike classical statistical inference where the main interest is point estimation or parameter testing, combinatorial inference aims at testing the global structure of the underlying graph. Examples include testing the graph connectivity, the presence of a cycle of certain size, or the maximum degree of the graph. To begin with, we study the information-theoretic limits of a large family of combinatorial inference problems. We propose new concepts including structural packing and buffer entropies to characterize how the complexity of combinatorial graph structures impacts the corresponding minimax lower bounds. On the other hand, we propose a family of novel and practical structural testing algorithms to match the lower bounds. We provide numerical results on both synthetic graphical models and brain networks to illustrate the usefulness of these proposed methods.