Abstract: Pearson's chi-squared test, from 1900, is the standard statistical tool for "hypothesis testing on distributions": namely, given samples from an unknown distribution Q that may or may not equal a hypothesis distribution P, we want to return "yes" if P=Q and "no" if P is far from Q. While the chi-squared test is easy to use, it has been known for a while that it is not "data efficient", it does not make the best use of its data. Precisely, for accuracy epsilon and confidence delta, and given n samples from the unknown distribution Q, a good tester will return "yes" with probability >1-delta when P=Q, and "no" with probability >1-delta when |P-Q|>epsilon. The challenge is to find a good tester with the *best* tradeoff between epsilon, delta, and n.
We introduce a new (linear) tester, which we hope will replace the chi-squared tester in practical use. This tester aims to be 1+o(1) optimal, in that the number of samples n needed by the tester is within 1+o(1) factor of the samples needed by *any* tester, even non-linear testers (for the setting: accuracy epsilon, confidence delta, and hypothesis P). This talk will intuitively introduce a non-convex optimization framework that finds the linear tester with optimal Chernoff bounds on its performance; we then show how minimax and duality results allow us to transform this optimum into matching lower bounds.
This is joint work with Trung Dang and Hongao Wang.