2
$\begingroup$

In the context of statistical estimation or distribution testing, Le Cam's method is a way to prove lower bounds on the minimax sample complexity ([1,2,3,4], further details below). My question is: for the special case of distribution identity testing (see below), under what conditions is the lower bound obtained via Le Cam's method tight? (i.e., equal to the minimax sample complexity up to constant factors.)

Distribution Identity Testing

Let $D$ be a distribution over a finite set $\Omega$ and fix $\varepsilon \in (0,1)$. A tester for $D$ is a (possibly randomized) algorithm $T$ that takes i.i.d. samples $X_1,\dots,X_n$ from an unknown distribution $Q$ over $\Omega$, and outputs either "$Q = D$" or "$Q \in \mathcal{B}$" where $\mathcal{B} = \{P: ~ \mathrm{d}_\mathsf{TV}(P, D) \geq \varepsilon\}$ and $\mathrm{d}_\mathsf{TV}$ denotes total variation distance.

The minimax sample complexity for $D$ is the minimal $n \in \mathbb{N}$ such that $$\inf_{T} \sup_{Q \in \{D \} \cup \mathcal{B}} \mathbb{P}_{X \sim Q^n}\left[T(X_1,\dots,X_n) \text{ fails}\right] \leq 1/3.$$

Le Cam's Method

For the special case of distribution identity testing, Le Cam's method boils down to the following inequality:

$$\inf_{T} \sup_{Q \in \{D \} \cup \mathcal{B}} \mathbb{P}\left[T(X_1,\dots,X_n) \text{ fails}\right] \geq \frac{1}{2}\left(1-\inf _{Q \in \operatorname{conv_n}\left(\mathcal{B}\right)} \mathrm{d}_{\mathrm{TV}}\left(D^n, Q\right)\right),$$ where $\operatorname{conv_n}\left(\mathcal{B}\right)$ is the convex hull of $\{Q^n: ~ Q \in \mathcal{B}\}$.

What I Know So Far

  • At least in some cases, Le Cam's bound is tight. For example, [2] mentions that it gives a tight lower bound for uniformity testing (the case where $D$ is the uniform distribution on $\Omega$).

  • From von Neumann's minimax theorem, $$\inf_{T} \sup_{Q \in \{D \} \cup \mathcal{B}} \mathbb{P}\left[T(X_1,\dots,X_n) \text{ fails}\right] = \\ ~~~~~~~~~~~~~~~~~~~ \sup_{Q \in \operatorname{conv_n}\left(\{D \} \cup \mathcal{B}\right)} \inf_{T} \: \mathbb{P}_{X \sim Q}\left[T(X_1,\dots,X_n) \text{ fails}\right].$$ It looks to me as if the right hand side here is somewhat related to Le Cam's lower bound, but it's not obvious to me when they would be equal.

  • These papers [5,6] give some conditions for the bound to be tight, but they are fairly general and I'm not sure I fully understand them.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .