Online Program Home
My Program

Abstract Details

Activity Number: 182
Type: Contributed
Date/Time: Monday, August 1, 2016 : 10:30 AM to 12:20 PM
Sponsor: IMS
Abstract #319838
Title: Structure Testing for Sparse High-Dimensional Graphical Models: Lower Bounds and Algorithms
Author(s): Matey Neykov* and Junwei Lu and Han Liu
Companies: Princeton and Princeton and Princeton
Keywords: Graph Structure Testing ; Minimax Testing ; Multiplier Bootstrap ; Multiple Hypothesis Testing ; Post-Regularization Inference

We present a novel method for obtaining lower bounds on the minimal signal strength required to asymptotically distinguish (in a minimax sense) Gaussian graphical models whose graph structures are separable by a single edge. The proposed strategy bypasses lengthy calculations by reducing the problem to an exercise of counting closed walks on a given graph. We apply our lower bound technique to obtain signal strength limitations in various testing problems including connectivity detection and cycles detection, and self-avoiding path length testing. In addition, we provide computationally tractable algorithms which can provably handle such structure testing problems optimally up to a scalar multiplier, whenever we are given a high-dimensional sufficiently sparse graphical model. Finally, we propose a generalization of our lower bound strategy, capable of addressing problems whose graphical structures may differ in multi-edged sets. Using this lower bound we analyze the signal strength required to test whether the graph at hand contains a sparse star subgraph, in addition to a sparse clique detection example.

Authors who are presenting talks have a * after their name.

Back to the full JSM 2016 program

Copyright © American Statistical Association