Robert Graczyk

Associate Professor of Information Theory

Current Projects

Approximate Hypothesis Testing

In Approximate Hypothesis Testing (AHT), the goal is to estimate an unknown distribution $P$ based on observed IID samples $bold(X) = (X_1, ..., X_n)$. Unlike in classical hypothesis testing, the estimate need not be exact—it suffices to produce some $hat(P)$ that is "close" to the sample-generating distribution $P$. Together with my doctoral student Nicolas Le Gouic, we establish the sample complexity of AHT, i.e., the smallest number of samples required to reliably produce such $hat(P)$.

Problem Statement. Consider $n$ samples $bold(X) = (X_1, ..., X_n) in cal(X)^n$ that are IID according to a distribution $P$ only known to reside in a finite hypothesis class $cal(H)$. Based on $bold(X)$, we seek to produce an estimate $hat(P)$—not necessarily in $cal(H)$!—that is $epsilon$-close to $P$ as measured by some distance $d: cal(P)(cal(X)) times cal(P)(cal(X)) -> RR_(>= 0)$. Our aim is to determine the smallest number of samples $n_"AHT"$ that are required to produce such an estimate $hat(P)$ with probability at least $1 - delta$ for every sample-generating distribution $P$. We refer to $n_"HAT"$ as the sample complexity of AHT and formally define it as

$ #let vhide(it) = context { hide(it); h(-measure(it).width) } n_"AHT" := min_n { min_hat(P) max_(vhide(hat(P)) P in cal(H)) limits(PP)_(vhide(hat(P)) bold(X) tilde op("IID") P)[d(hat(P)(bold(X)), P) > epsilon] <=delta }. $
(1)

Clustered Hypothesis Testing. We determine $n_"HAT"$ by means of the auxililiary Clustered Hypothesis Testing (CHT) problem. In the latter, each hypothesis $P in cal(H)$ is assigned to at least one cluster $cal(C) subset.eq cal(H)$. The aim of the problem is to determine, with probability at least $1 - delta$, a cluster $cal(C)$ that contains the sample-generating distribution $P$. The sample complexity of CHT is denoted $n_"CHT"$ and formally defined as

$ #let vhide(it) = context { hide(it); h(-measure(it).width) } n_"CHT" := min_n { min_hat(cal(C)) max_(vhide(hat(cal(C))) P in cal(H)) limits(PP)_(vhide(hat(cal(C))) bold(X) tilde op("IID") P)[P in.not hat(cal(C))(bold(X))] <= delta }. $
(2)

We show that $n_"AHT" = n_"CHT"$ for a judiciously constructed cluster family $frak(C) subset.eq 2^cal(H)$.

Specifically, we construct $frak(C)$ so that the intersection of every $epsilon$-ball $cal(B)_(epsilon)(Q) := {P in cal(P)(cal(X)): d(P, Q) <= epsilon}$ with $cal(H)$ is the subset of some cluster $cal(C) in frak(C)$; this corresponds to the key fact that, in AHT, we need not distinguish between all hypotheses $P in cal(H)$. In the figure below, we present an example of a cluster family $frak(C)$ for $cal(X) = {a, b, c}$ and $cal(H) = {P_1, P_2, P_3}$, where

$ &P_1(a) = 0.15, P_1(b) = 0.17; \ &P_2(a) = 0.35, P_2(b) = 0.17; \ &P_3(a) = 0.25, P_3(b) = 0.33. $
(3)

By choosing $epsilon = 0.1$ and $d(P, Q)$ as the Euclidean distance between the first two components of $P$ and $Q$,

$ d(P, Q) := ||(P(a), P(b)) - (Q(a), Q(b))||_2, $
(4)

we obtain the cluster family $frak(C) = {C_upright("I"), C_"II", C_"III"}$ for $cal(H)$ (depicted here is its $(P(a), P(b))$-projection.)

Figure 1: Pairwise overlapping clusters.
Figure 1: Pairwise overlapping clusters.

Observe the overlap between the clusters: if the data-generating distribution was, say, $P_1$, then both $cal(C)_upright("I")$ and $cal(C)_"III"$ would constitute a correct answer in the CHT problem.

Main Result. We show that $n_"AHT"$ scales as

$ n_"AHT" prop 1/(min_(cal(B) subset.eq cal(H)) op("D")_upright("B")(cal(B))), $
(5)

where the minimum is taken over all "confusable" subsets $cal(B)$ of $cal(H)$ (in the example above, $cal(B) = cal(H) = {P_1, P_2, P_3}$; in general, we give a definition of "confusability" pertaining to the cluster family $frak(C)$), and where $op("D")_upright("B")$ denotes a new "multivariate Bhattacharyya distance":

$ op("D")_upright("B")(cal(B)) := -log(integral_(x in cal(X)) root(script(|cal(B)|), product_(P in cal(B)) dif P(x))). $
(6)

For detailed results and more examples, we shall publish a preprint shortly.