Skip navigation
Please use this identifier to cite or link to this item:
Title: Structure Detection in High Dimensional Graphical Models
Authors: Cao, Yuan
Advisors: Liu, Han
E, Weinan
Contributors: Applied and Computational Mathematics Department
Subjects: Statistics
Issue Date: 2018
Publisher: Princeton, NJ : Princeton University
Abstract: Graphical models are powerful tools to study the dependency structures among random variables. In this thesis, we study structure detection problems in high dimensional graphical models. Given independent samples generated from a graphical model, the goal of structure detection is to distinguish whether the underlying graph is empty, or contains a subgraph of a certain structure. In the first part of the thesis, we study the information-theoretic limits of structure detection problems in high temperature ferromagnetic (positive interaction only) Ising models. First, based on the high temperature expansion of Ising models, we derive a general information-theoretic lower bound for arbitrary alternative hypothesis. We then propose a general framework of linear tests on the sample covariance matrix that matches our minimax lower bounds. Our results reveal that a key quantity called graph arboricity drives the testability of the problem. In the second part of the thesis, we discuss the computational limits of structure detection problems. First, based on a computational hardness conjecture of sparse principal component analysis, we prove that, unless the signal is strong enough, no polynomial time linear tests on the sample covariance matrix are capable of testing this problem. We also give another computational lower bound based on the oracle computational model, where the computational complexity is measured by the times an algorithm queries an oracle. Our results show that, for problems with high graph arboricity, the information-theoretic limits are unachievable by tractable algorithms. In the third part of the thesis, we propose a unified framework to quantify local and global inferential uncertainty for high dimensional nonparanormal graphical models. In particular, we consider the problems of testing the presence of a single edge and constructing a uniform confidence subgraph. We develop pseudo likelihood based score and Wald tests to eliminate the unknown nuisance transformations. A U-statistic multiplier bootstrap method is then proposed to construct the confidence subgraph.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Cao_princeton_0181D_12784.pdf1.15 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.