Ravi Kannan (Microsoft Research India)
Classical hypothesis testing seeks to decide whether given data is signal or noise. Likelihood ratio (LR) tests are known to minimize the probability of false positive (FP) for any given probability of false negative (FN).
We consider data which is either all noise - Eg. drawn from a standard Gaussian N(0,1) - or mostly noise with a weak signal - Eg. drawn from a Gaussian mixture: (epsilon) N(\mu,1) + (1-epsilon)N(0,1). We seek tests for which both FP and FN go to zero as the number of iid samples goes to infinity. We show essentially that ideal tests exist if the chi-squared distance between signal and noise is higher than a certain threshold.
Interestingly, it turns out that the best tests do not use LR, but a related, yet different quantity.
The proofs are simple and the result is work in progress. The talk will describe things from first principles.
Joint Work with Richard Karp.