Approximate Hypothesis Testing

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.