From Testing Error to Sample-Size Rates

From Indistinguishable Models to Sample-Size Rates

A testing lower bound says that two statistical models cannot be reliably distinguished when their distributions are sufficiently close. An estimation lower bound follows when the parameter values for those models are far enough apart: an estimator that is accurate for both would also provide a way to distinguish them. To obtain a rate as a function of sample size, one more step is essential: account for how the distance between the data distributions changes when the sample contains $n$ observations.

For independent observations from the same model, Kullback–Leibler divergence adds across observations. Thus, a fixed per-observation divergence generally becomes $n$ times as large for the full sample. To keep two alternatives difficult to distinguish as $n$ grows, their parameter separation must typically shrink. When the per-observation divergence is quadratic in separation, this leads to separation of order $n^{-1/2}$, and squared-error risk of order $n^{-1}$.

Definition: Let $\{P_\theta:\theta\in\Theta\}$ be a statistical model, and let $d$ be a metric on $\Theta$. For a loss $d(\hat\theta,\theta)^s$, where $s>0$, the minimax risk at sample size $n$ is $$ R_n=\inf_{\hat\theta}\sup_{\theta\in\Theta}E_\theta\!\left[d(\hat\theta,\theta)^s\right]. $$ The infimum is over measurable estimators based on the $n$ observations. When observations are independent with common distribution $P_\theta$, their joint distribution is denoted $P_\theta^n$.

The Two-Point Bound and Its Sample-Size Form

For two parameter values $\theta_0,\theta_1$, write $\Delta=d(\theta_0,\theta_1)$. Total variation distance is defined by $$ \operatorname{TV}(P,Q)=\sup_A |P(A)-Q(A)|. $$ For two hypotheses given equal prior probability, the smallest possible average probability of testing error is $(1-\operatorname{TV}(P,Q))/2$. A close pair of distributions therefore forces a positive testing error.

Theorem: Suppose $d$ is a metric, $s>0$, and the two distributions $P_{\theta_0}^n$ and $P_{\theta_1}^n$ are defined on the observation space. Then $$ R_n\geq \left(\frac{\Delta}{2}\right)^s \frac{1-\operatorname{TV}(P_{\theta_0}^n,P_{\theta_1}^n)}{2}. $$ If the one-observation distributions are dominated and have finite Kullback–Leibler divergence, then $$ \operatorname{TV}(P_{\theta_0}^n,P_{\theta_1}^n) \leq \sqrt{\frac{n\,\operatorname{KL}(P_{\theta_0}\Vert P_{\theta_1})}{2}}, $$ where $\operatorname{KL}(P\Vert Q)=\int \log(dP/dQ)\,dP$.

Proof. Given any estimator $\hat\theta$, define a test that selects whichever of $\theta_0,\theta_1$ is closer to $\hat\theta$, breaking ties in a fixed way. If this test selects the wrong parameter, the triangle inequality implies that the estimator is at least $\Delta/2$ from the true parameter. For example, if the true value is $\theta_0$ but the test selects $\theta_1$, then $d(\hat\theta,\theta_1)\leq d(\hat\theta,\theta_0)$, so $$ \Delta\leq d(\theta_0,\hat\theta)+d(\hat\theta,\theta_1) \leq 2d(\theta_0,\hat\theta). $$ The same argument applies when $\theta_1$ is true. Consequently, the average risk under the two equally weighted hypotheses is at least $(\Delta/2)^s$ times the test’s average error. The maximum risk over the two parameters is no smaller than this average. Every such test has average error at least $(1-\operatorname{TV}(P_{\theta_0}^n,P_{\theta_1}^n))/2$. Taking the infimum over estimators proves the first inequality.

For independent observations with densities $p_0,p_1$, the joint densities are products. Taking the logarithm of their ratio gives a sum, and expectation under $P_{\theta_0}^n$ gives $$ \operatorname{KL}(P_{\theta_0}^n\Vert P_{\theta_1}^n) =E_{\theta_0}\!\left[\sum_{i=1}^n\log\frac{p_0(X_i)}{p_1(X_i)}\right] =n\operatorname{KL}(P_{\theta_0}\Vert P_{\theta_1}). $$ The finite-divergence condition makes these expectations well defined. Pinsker’s inequality, $\operatorname{TV}(P,Q)\leq\sqrt{\operatorname{KL}(P\Vert Q)/2}$, applied to the product distributions proves the second inequality. $\square$

This bound gives a useful rate calculation. Suppose a pair at separation $\Delta$ has one-observation divergence at most $C\Delta^\alpha$, for constants $C>0$ and $\alpha>0$. If the parameter space contains a pair with $\Delta=c n^{-1/\alpha}$, then its product divergence is at most $C c^\alpha$. Choosing $c$ small enough keeps the total variation bound below a fixed constant less than one. The two-point theorem then yields risk of order at least $$ \Delta^s\asymp n^{-s/\alpha}. $$ This is a conditional rate calculation, not a universal guarantee: the model must contain the required alternatives, and the divergence bound must hold for them. In the common quadratic case $\alpha=2$, separation is of order $n^{-1/2}$; squared-error risk, with $s=2$, is of order $n^{-1}$.

Worked Examples

Worked Example: Gaussian Location with Known Variance

Suppose $X_1,\ldots,X_n$ are independent with $X_i\sim N(\theta,\sigma^2)$, where $\sigma>0$ is known and $\Theta=[0,\sigma]$. Find a squared-error minimax lower bound using two parameter values.

Take $\theta_0=0$ and $\theta_1=\delta=\sigma/(2\sqrt n)$. Since $n\geq1$, these values belong to $[0,\sigma]$. The divergence between two normal distributions with the same variance is $$ \operatorname{KL}\!\left(N(\theta_0,\sigma^2)\Vert N(\theta_1,\sigma^2)\right) =\frac{(\theta_0-\theta_1)^2}{2\sigma^2} =\frac{\delta^2}{2\sigma^2}. $$ For the full sample, this is $n\delta^2/(2\sigma^2)=1/8$. Pinsker’s inequality therefore gives total variation at most $\sqrt{1/16}=1/4$. The average testing error is at least $(1-1/4)/2=3/8$.

For squared-error loss, a testing error forces estimation error of at least $\delta/2$, so $$ R_n\geq \left(\frac{\delta}{2}\right)^2\frac{3}{8} =\frac{3\delta^2}{32} =\frac{3\sigma^2}{128n}. $$ The separation shrinks as $n^{-1/2}$, while the resulting squared-error risk lower bound shrinks as $n^{-1}$.

Worked Example: Bernoulli Probabilities Near One Half

Let $X_1,\ldots,X_n$ be independent Bernoulli observations with unknown success probability $p\in[1/2,3/4]$. Show that squared-error minimax risk is at least a constant times $1/n$.

Use $p_0=1/2$ and $p_1=1/2+\delta$, where $\delta=1/(8\sqrt n)$. Both values are in the parameter space. For distributions $P,Q$ on a finite set, $\operatorname{KL}(P\Vert Q)\leq\chi^2(P,Q)$, where $\chi^2(P,Q)=\sum_x(P(x)-Q(x))^2/Q(x)$. Indeed, $\log u\leq u-1$ implies $$ \operatorname{KL}(P\Vert Q) \leq\sum_x P(x)\left(\frac{P(x)}{Q(x)}-1\right) =\sum_x\frac{(P(x)-Q(x))^2}{Q(x)}. $$ For the two Bernoulli distributions, this gives $$ \operatorname{KL}(P_{p_0}\Vert P_{p_1}) \leq \frac{\delta^2}{p_1(1-p_1)} =\frac{\delta^2}{1/4-\delta^2} \leq \frac{16}{3}\delta^2, $$ because $\delta\leq1/8<1/4$, so $1/4-\delta^2\geq3/16$. The $n$-observation divergence is therefore at most $$ n\frac{16}{3}\delta^2=\frac{1}{12}. $$ Pinsker’s inequality bounds total variation by $\sqrt{1/24}<1/4$; hence average testing error is at least $3/8$. Applying the two-point bound with separation $\delta$ and $s=2$, $$ R_n\geq\frac{\delta^2}{4}\frac{3}{8} =\frac{3}{2048n}. $$ Thus the lower bound has the $n^{-1}$ squared-error rate, even though its numerical constant differs from the Gaussian example.

Worked Example: Fano’s Inequality and the Number of Hypotheses

Let $M=4$, let $d\geq3$, and consider $n$ independent observations from $N(\mu,\sigma^2 I_d)$, where the parameter set consists of four vertices $\mu_1,\ldots,\mu_4$ of a centered regular simplex of side length $\Delta$. Obtain a squared Euclidean risk lower bound.

For a centered regular simplex, $\|\mu_j\|^2=\Delta^2(M-1)/(2M)$. With $M=4$, each squared norm is $3\Delta^2/8$. Compare each sampling distribution with the reference distribution $Q=N(0,\sigma^2 I_d)^{\,n}$. The Gaussian divergence formula gives $$ \operatorname{KL}(P_{\mu_j}^n\Vert Q) =\frac{n\|\mu_j\|^2}{2\sigma^2} =\frac{3n\Delta^2}{16\sigma^2}. $$ Choose $\Delta^2=4\sigma^2\log(4)/(3n)$. Then each divergence to $Q$ is $\log(4)/4$.

For a uniformly chosen index $J\in\{1,2,3,4\}$, Fano’s inequality gives classification error at least $1-(I(J;X)+\log 2)/\log 4$. The mutual information is at most the average divergence to any reference distribution, so $I(J;X)\leq\log(4)/4$. Therefore the classification error is at least $$ 1-\frac{\log(4)/4+\log 2}{\log 4}=\frac{1}{4}. $$ Classifying an estimator by its nearest simplex vertex can be wrong only if its Euclidean estimation error is at least $\Delta/2$. The average squared risk, and hence the maximum risk over the four vertices, is at least $$ \left(\frac{\Delta}{2}\right)^2\frac{1}{4} =\frac{\Delta^2}{16} =\frac{\sigma^2\log(4)}{12n}. $$ Here the number of hypotheses affects the choice of separation through $\log M$; for this fixed $M$, the resulting lower bound again scales as $1/n$.

Common Pitfall: Forgetting to Scale the Divergence

A common mistake is to choose a parameter separation that makes the divergence for one observation small, then use that same divergence as though it described the whole sample. For independent observations, the sample divergence is $n$ times the one-observation divergence. A separation fixed as $n$ grows can therefore become easy to distinguish, even if it initially looked small.

The correction is to calculate the product divergence before choosing the separation. In the quadratic case, the requirement is typically $nC\Delta^2\leq c$ for a suitably small constant $c$. Solving this inequality gives $\Delta\leq\sqrt{c/(Cn)}$. Substituting this sample-size-dependent separation into the loss produces the rate. The calculation also depends on using a pair contained in the parameter space; a formal separation outside that space gives no lower bound for the stated problem.

Key takeaway: A testing bound becomes a sample-size risk rate through three explicit steps: relate testing error to estimation loss, compute how divergence accumulates across observations, and choose parameter separation so the full-sample testing error remains bounded away from zero.

Check Your Understanding

For each question, track both the separation and the loss exponent.

If one-observation divergence is bounded by $C\Delta^2$, what separation keeps the full-sample divergence bounded as $n$ increases?
For loss $d(\hat\theta,\theta)^4$ and a quadratic divergence bound, what sample-size rate follows from a two-point argument?
In the Gaussian location example, why is the separation allowed to depend on $n$?
What is the average testing error lower bound when total variation is at most $1/3$?
Why does a small one-observation divergence alone not guarantee that two models remain hard to distinguish from a sample of size $n$?

From Testing Error to Sample-Size Rates

What You'll Learn