Abstract

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 Bhatthacharyya distance evaluated on a set of
distributions considered to be the "most confusable" w.r.t. the
desired approximation accuracy. From this result we recover, inter
alia, the sample complexity of composite hypothesis testing and
distribution learning, which shows that-under the right
assumptions-our arguments may be extended to infinite hypothesis
classes as well.

-||-   _|_ _|_     /    __|__   Stefan M. Moser
[-]     --__|__   /__\    /__   Senior Scientist, ETH Zurich, Switzerland
_|_     -- --|-    _     /  /   Adjunct Professor, National Yang Ming Chiao Tung University, Taiwan
/ \     []  \|    |_|   / \/    Web: https://moser-isi.ethz.ch/

Last modified: Thu Jan 23 05:34:15 UTC 2025