Hypothesis Testing with Sparse Samples: Test Synthesis & Analysis via Generalized Error Exponents

Dayu Huang

Dayu Huang PhD candidate at the University of Illinois (defended Nov. 2012.. and passed!)

Abstract:

This talk provides a survey of new tools for hypothesis testing subject to a relatively small number of observations. Complexity of the model is captured by the size of the observation alphabet, denoted m. The number of observations is denoted n. A suitable setting for analysis is based on a high-dimensional model in which both n and m tend to infinity, and n=o(m). In this setting, a new performance criterion is introduced that generalizes the classical error exponent of Chernoff & Hoeffding. This leads to new statistical tests, and analytical tools to evaluate them. New insights are obtained that are not available from other asymptotic settings, such as the Central Limit Theorem. The following three key results will be explored in the special case of the goodness of fit problem: (i) The best achievable probability of error Pe decays as, log(Pe) ~ - J n2/m (ii) A coincidence-based test (motivated by the birthday paradox) is shown to be asymptotically optimal. (iii) The Pearson's chi-square test is not optimal in this setting, since the generalized error exponent is zero. (iv) This performance criterion inspires a new test that is effective under more general settings than the coincidence-based test. This talk is based on joint work with Sean Meyn.

Date:

October 12, 2012

Time:

1:00pm- 2:00pm

Room:

234 Larsen

Links:

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer