Online Program Home
  My Program

Abstract Details

Activity Number: 272 - Modern Statistical Inference
Type: Invited
Date/Time: Tuesday, August 1, 2017 : 8:30 AM to 10:20 AM
Sponsor: IMS
Abstract #322354
Title: Optimal hypothesis testing for stochastic block models with growing degrees
Author(s): Debapratim Banerjee and Zongming Ma*
Companies: University of Pennsylvania and University of Pennsylvania
Keywords: polynomial time algorithm ; likelihood ratio test ; stochastic block models
Abstract:

In this talk, we discuss optimal hypothesis testing for distinguishing a stochastic block model from an Erdos-Renyi random graph. We derive central limit theorems for a collection of linear spectral statistics under both the null and local alternatives. In addition, we show that linear spectral statistics based on Chebyshev polynomials can be used to approximate signed cycles of growing lengths which in turn determine the likelihood ratio test asymptotically when the graph size and the average degree grow to infinity together. Therefore, one achieves sharp asymptotic optimal power of the testing problem within polynomial time complexity.


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

Back to the full JSM 2017 program

 
 
Copyright © American Statistical Association