Approximate Hypothesis Testing

Nicolas Le Gouic¹; Robert Graczyk²; Stefan Moser³

We establish the sample complexity of Approximate Hypothesis Testing (AHT): Unlike in classical hypothesis testing, here we are only required to approximate the sample-generating distribution rather than determine it exactly.On finite hypothesis classes, we establish that the AHT sample complexity scales inversely with the multivariate Bhattacharyya distance (3) evaluated on a set of distributions considered to be the "most confusable" w.r.t. the desired approximation accuracy.

1 LTCI, Télécom Paris, Institut Polytechnique de Paris, France
2 RhySearch, Digital Innovation Lab, Werdenbergstrasse 4, 9470 Buchs, Switzerland
3 Signal and Information Processing Laboratory, ETH Zurich, Zurich, Switzerland

Download Publication