Reduction from Estimation to Hypothesis Testing

Why Estimation Can Be Reduced to Testing

A lower bound for estimation can be difficult to obtain directly: an estimator may take values in a large or even infinite-dimensional space. A useful first step is to select just two possible targets that are far apart. If an estimator is accurate, its output should indicate which target generated the data. This turns estimation into a binary testing problem, and any mistakes in that test must be paid for as estimation error.

The key ingredient is separation under a metric. The argument does not require the estimator to be optimal, nor does it require the induced test to be the best possible test. It only uses the fact that an estimate closer to the wrong target cannot be too close to the true target.

Setup and Definitions

Definition: Let $(\mathcal{Z},\mathcal{A})$ be the data space, and suppose the data have distribution $P_\theta$ when the parameter is $\theta$. Let the object to be estimated be $\eta(\theta)$ in a metric space $(\mathcal{H},d)$. An estimator $\hat{\eta}$ is a measurable map from the data space to $\mathcal{H}$. Its metric risk at $\theta$ is $R_\theta(\hat{\eta})=E_\theta[d(\hat{\eta},\eta(\theta))]$, when this expectation is defined. A test between two parameter values $\theta_0,\theta_1$ is a measurable map $\phi:\mathcal{Z}\to\{0,1\}$, where $\phi=0$ selects $\theta_0$ and $\phi=1$ selects $\theta_1$.

Choose two parameter values and write $\eta_0=\eta(\theta_0)$ and $\eta_1=\eta(\theta_1)$. Their separation is $\Delta=d(\eta_0,\eta_1)$. The reduction is useful when $\Delta>0$: if the targets coincide, they cannot distinguish the two estimation tasks in the metric being studied.

From any estimator, construct a test by selecting whichever of the two targets is closer to its output, and break ties in favor of $\theta_0$:

\phi_{\hat{\eta}}(z)= \begin{cases} 1, & d(\hat{\eta}(z),\eta_1)<d(\hat{\eta}(z),\eta_0),\\ 0, & d(\hat{\eta}(z),\eta_1)\ge d(\hat{\eta}(z),\eta_0). \end{cases}

This is a measurable test: for a fixed target, distance from the estimator output is a measurable real-valued function, and comparing two such functions defines a measurable event. The tie rule makes the test unambiguous.

The Basic Reduction

Theorem: Suppose $d$ is a metric, $\Delta=d(\eta_0,\eta_1)>0$, and $\hat{\eta}$ is a measurable estimator. For the test $\phi_{\hat{\eta}}$ defined above, $$ \max\{R_{\theta_0}(\hat{\eta}),R_{\theta_1}(\hat{\eta})\} \ge \frac{\Delta}{4}\left\{P_{\theta_0}(\phi_{\hat{\eta}}=1)+P_{\theta_1}(\phi_{\hat{\eta}}=0)\right\}. $$

The two probabilities in braces are the test’s error probabilities under the two possible parameter values. To prove the result, first compare the estimation loss pointwise with the indicator of a testing error.

If $\theta=\theta_0$ and the test errs, then $\phi_{\hat{\eta}}=1$, so $d(\hat{\eta},\eta_1)<d(\hat{\eta},\eta_0)$. The triangle inequality gives $\Delta\le d(\hat{\eta},\eta_0)+d(\hat{\eta},\eta_1)<2d(\hat{\eta},\eta_0)$. Thus the estimation loss is at least $\Delta/2$. If $\theta=\theta_1$ and the test errs, then $\phi_{\hat{\eta}}=0$, so $d(\hat{\eta},\eta_0)\le d(\hat{\eta},\eta_1)$. Consequently, $\Delta\le d(\hat{\eta},\eta_0)+d(\hat{\eta},\eta_1)\le 2d(\hat{\eta},\eta_1)$. The pointwise inequalities in both cases are therefore

d(\hat{\eta},\eta_i)\ge \frac{\Delta}{2}\, \mathbf{1}\{\phi_{\hat{\eta}}\ne i\},\qquad i\in\{0,1\}.

Taking expectation under each corresponding distribution and adding yields $R_{\theta_0}(\hat{\eta})+R_{\theta_1}(\hat{\eta})\ge \frac{\Delta}{2}\{P_{\theta_0}(\phi_{\hat{\eta}}=1)+P_{\theta_1}(\phi_{\hat{\eta}}=0)\}$. The maximum of two nonnegative numbers is at least half their sum, proving the theorem. $\square$

The factor $1/4$ comes from two steps: an error forces loss at least $\Delta/2$, and the larger of two risks is at least half their sum. The theorem is valid even if a risk is infinite; in that case the claimed lower bound is immediate.

Squared Metric Loss and a Minimax Consequence

The same pointwise argument also yields a bound when the loss is squared distance. Squaring the nonnegative inequality on a testing error gives $d(\hat{\eta},\eta_i)^2\ge (\Delta^2/4)\mathbf{1}\{\phi_{\hat{\eta}}\ne i\}$. Thus, if the squared risks are defined,

Corollary: For squared metric loss, $$ \max_{i\in\{0,1\}}E_{\theta_i}[d(\hat{\eta},\eta_i)^2] \ge \frac{\Delta^2}{8}\left\{P_{\theta_0}(\phi_{\hat{\eta}}=1)+P_{\theta_1}(\phi_{\hat{\eta}}=0)\right\}. $$

There is also a useful way to state the implication without committing to the estimator-induced test. Let $e_*=\inf_{\phi}\{P_{\theta_0}(\phi=1)+P_{\theta_1}(\phi=0)\}$, where the infimum is over all measurable tests on the same data. The induced test is one candidate in this set, so its sum of error probabilities is at least $e_*$. It follows that every estimator satisfies $\max_i R_{\theta_i}(\hat{\eta})\ge \Delta e_*/4$. If the parameter space contains both selected values, the supremum risk over the full space is at least this maximum; taking the infimum over estimators preserves the lower bound. This is the basic route from a testing difficulty to a minimax estimation lower bound. No formula for $e_*$ is needed for the reduction itself.

Worked Applications

Worked Example: Estimating a Bernoulli Probability

Observe one $X\sim\operatorname{Bernoulli}(p)$, and estimate $p$ by $\hat p=X$ under absolute-error loss. Compare $p_0=0.25$ and $p_1=0.75$. The target distance is $\Delta=|0.75-0.25|=0.5$.

The estimator is closer to $0.25$ when $X=0$, and closer to $0.75$ when $X=1$. Therefore the induced test selects $p_1$ exactly when $X=1$. Its errors are $P_{p_0}(\phi_{\hat p}=1)=0.25$ and $P_{p_1}(\phi_{\hat p}=0)=1-0.75=0.25$.

The reduction gives $\max\{R_{p_0}(\hat p),R_{p_1}(\hat p)\}\ge (0.5/4)(0.25+0.25)=0.0625$. For a direct check, at $p_0$ the absolute error is $0.25$ when $X=0$ and $0.75$ when $X=1$, so $R_{p_0}=0.75(0.25)+0.25(0.75)=0.375$. At $p_1$, the corresponding calculation is $R_{p_1}=0.25(0.75)+0.75(0.25)=0.375$. The bound is valid, though conservative.

Worked Example: A Two-Point Scalar Estimation Problem

Let the unknown target be either $\theta_0=0$ or $\theta_1=2$, with absolute-error loss. The observation $Z$ takes values $L,R$, with $P_0(R)=0.2$, $P_0(L)=0.8$, $P_2(L)=0.2$, and $P_2(R)=0.8$. Use the estimator $\hat\theta=0$ when $Z=L$ and $\hat\theta=2$ when $Z=R$.

The separation is $\Delta=|2-0|=2$, and the induced nearest-target test selects $2$ exactly when $Z=R$. Its error probabilities are $P_0(R)=0.2$ and $P_2(L)=0.2$, with sum $0.4$. The theorem therefore gives $\max\{R_0,R_2\}\ge (2/4)(0.4)=0.2$.

Under target $0$, the estimator has error $0$ on $L$ and error $2$ on $R$, so $R_0=0.8(0)+0.2(2)=0.4$. Under target $2$, it has error $2$ on $L$ and $0$ on $R$, so $R_2=0.2(2)+0.8(0)=0.4$. Both risks exceed the lower bound.

Worked Example: Function Estimation in a Genuine Metric Space

Consider the space $C[0,1]$ of continuous real-valued functions on $[0,1]$, with $d(f,g)=\{\int_0^1(f(x)-g(x))^2\,dx\}^{1/2}$. This is a metric on $C[0,1]$: if the integral is zero, continuity implies $f-g$ must be zero everywhere. Indeed, if it were nonzero at any point, continuity would make its absolute value bounded away from zero on a neighborhood (or a one-sided neighborhood at an endpoint), forcing a positive integral.

Suppose the two possible targets are the constant functions $f_0(x)=0$ and $f_1(x)=1$. Their distance is $d(f_0,f_1)=\{\int_0^1 1\,dx\}^{1/2}=1$. The data $W$ take values $0,1$, with $P_{f_0}(W=1)=0.1$ and $P_{f_1}(W=1)=0.7$. Let the estimator output $f_0$ if $W=0$ and $f_1$ if $W=1$.

The nearest-target test selects $f_1$ when $W=1$. Its errors are $0.1$ under $f_0$ and $P_{f_1}(W=0)=0.3$ under $f_1$. The theorem gives maximum expected metric loss at least $(1/4)(0.1+0.3)=0.1$. The actual metric loss is $1$ exactly when the estimator selects the wrong constant function, and is $0$ otherwise. Hence the risks are $R_{f_0}=0.1$ and $R_{f_1}=0.3$, confirming the bound.

Interpretation and a Common Pitfall

The reduction is useful because it separates an estimation problem into two tasks. First, choose two targets with known positive metric separation. Then, study how hard it is to distinguish the distributions that produce those targets. If every test has a substantial error probability, the theorem forces a substantial estimation risk for at least one of the two targets.

Pitfall: treating the nearest-target test as optimal. The construction only provides a test derived from the estimator. It does not say that this test minimizes testing error. The correct reasoning is that its error sum is at least the infimum over all tests, which is enough to obtain a lower bound.
Pitfall: using a distance that is not actually a metric on the stated space. For example, an integral distance can assign zero distance to distinct functions that differ only on a set of measure zero. One must identify functions equal almost everywhere or choose a function class, such as $C[0,1]$, on which the distance separates distinct elements.
Pitfall: dropping one of the two error probabilities. The risk bound involves the sum of the error probability under $\theta_0$ and the error probability under $\theta_1$. Each is evaluated under its own distribution.

The constants in the result come directly from metric separation and averaging the two risks; they do not assert that the bound is sharp for a particular estimator. The central conclusion is structural: reliable estimation of separated targets would yield a reliable test, so difficulty in testing imposes a limit on estimation.

Check Your Understanding

Use the nearest-target construction and the risk inequalities to answer the following.

For targets separated by $\Delta=3$, an estimator-induced test has error probabilities $0.1$ and $0.3$. What lower bound follows for the larger of the two expected metric risks?
Why does the tie rule matter for defining the induced test, and why does either fixed tie rule preserve the reduction?
What changes in the bound when the loss is squared metric distance?
Explain why the estimator-induced test need not be optimal for the minimax lower-bound argument to work.
Why is the integral distance in the function example a metric on continuous functions but not necessarily on all pointwise-defined functions?