Prior Averaging and Minimax Lower Bounds

Why Average Risk Gives a Minimax Lower Bound

A minimax guarantee concerns the hardest parameter value: an estimator is judged by its largest risk over the parameter set. A prior takes a different perspective, assigning probabilities to parameter values and averaging the risk. The key connection is that an average cannot exceed the largest value being averaged. Taking the infimum over estimators then gives a lower bound on minimax risk.

The infimum matters. For one particular estimator, its average risk may be much larger than the minimax risk: a deliberately poor estimator can have enormous risk even when another estimator performs well. The useful comparison is between minimax risk and the smallest achievable prior-averaged risk, not the average risk of an arbitrary estimator.

Definition: Let \(\{P_\theta:\theta\in\Theta\}\) be a statistical model, let \(\hat\theta\) be an estimator based on the data, and let \(L(\theta,\hat\theta)\geq 0\) be a loss. Its risk is \(R(\theta,\hat\theta)=E_\theta[L(\theta,\hat\theta)]\). The minimax risk is \(R_{\mathrm{minimax}}=\inf_{\hat\theta}\sup_{\theta\in\Theta}R(\theta,\hat\theta)\). For a probability distribution \(\pi\) on \(\Theta\), the prior-averaged risk of \(\hat\theta\) is \(r(\pi,\hat\theta)=\int_\Theta R(\theta,\hat\theta)\,\pi(d\theta)\). The Bayes risk for \(\pi\) is \(r(\pi)=\inf_{\hat\theta}r(\pi,\hat\theta)\).

The Prior-Averaging Inequality

The parameter set and prior must be compatible: the prior is supported on \(\Theta\). Assume the risk is measurable as a function of \(\theta\), so its integral under \(\pi\) is defined. Nonnegative loss allows the risk and its prior average to be extended-valued. The basic inequality does not require a special form of the model or loss.

Theorem (prior-averaging lower bound): For every prior \(\pi\) supported on \(\Theta\), \(R_{\mathrm{minimax}}\geq r(\pi)\).

Proof. Fix any estimator \(\hat\theta\). Since \(R(\theta,\hat\theta)\leq \sup_{\vartheta\in\Theta}R(\vartheta,\hat\theta)\) for every \(\theta\in\Theta\), integrating both sides with respect to the probability measure \(\pi\) gives

r(\pi,\hat\theta) =\int_\Theta R(\theta,\hat\theta)\,\pi(d\theta) \leq \sup_{\vartheta\in\Theta}R(\vartheta,\hat\theta).

This holds for every estimator. Taking the infimum over estimators on both sides, with the right-hand side becoming the minimax risk, yields

\inf_{\hat\theta}r(\pi,\hat\theta) \leq \inf_{\hat\theta}\sup_{\vartheta\in\Theta}R(\vartheta,\hat\theta).

The left side is \(r(\pi)\), so \(r(\pi)\leq R_{\mathrm{minimax}}\). \(\square\)

For a finite prior with support \(\{\theta_1,\ldots,\theta_m\}\) and probabilities \(w_j\), the averaged risk is simply \(\sum_{j=1}^m w_jR(\theta_j,\hat\theta)\). The theorem says to minimize this weighted sum over estimators before using it as a minimax lower bound.

Worked Example: An Uninformative Observation and a Finite Prior

Suppose \(\Theta=\{-1,0,1\}\), the data have the same distribution at all three parameter values, and the loss is squared error. Use the prior \(\pi(-1)=1/4\), \(\pi(0)=1/2\), and \(\pi(1)=1/4\) to obtain a minimax lower bound.

Because the data distribution does not depend on \(\theta\), the observation provides no information about which parameter value holds. For any fixed estimate \(a\), its prior-averaged squared loss is

\frac14(a+1)^2+\frac12a^2+\frac14(a-1)^2 =\frac14(2a^2+2)+\frac12a^2 =a^2+\frac12.

The minimum over \(a\) is \(1/2\), attained at \(a=0\). Allowing a randomized estimator does not reduce this value: conditional on any realized estimate \(A\), the same expression is \(A^2+1/2\geq1/2\), so its expectation is also at least \(1/2\). Thus the Bayes risk is \(1/2\), and prior averaging gives \(R_{\mathrm{minimax}}\geq1/2\).

The point is not that every estimator has average risk at most the minimax risk. For example, the constant estimate \(100\) has an average risk far above \(1/2\). The lower-bound argument uses the infimum of average risk over estimators, which here equals \(1/2\).

Finite Priors Turn Estimation into Testing

A useful finite prior places mass on parameter values that are separated under the loss. An estimator that is accurate must, in particular, identify which separated value generated the data. This observation converts a lower bound for classification error into a lower bound for estimation risk.

Theorem (separated-parameter reduction): Suppose \(\theta_1,\ldots,\theta_m\) belong to a metric space with distance \(d\), and \(d(\theta_j,\theta_k)\geq\delta>0\) whenever \(j\neq k\). Suppose the loss is \(L(\theta,\hat\theta)=d(\theta,\hat\theta)^2\). Give these points prior probabilities \(w_1,\ldots,w_m\), and let \(P_e^*(\pi)\) be the smallest prior-averaged probability of incorrectly identifying the index \(j\) from the data. Then \(R_{\mathrm{minimax}}\geq(\delta^2/4)P_e^*(\pi)\).

Proof. Given any estimator \(\hat\theta\), form a classifier \(\hat J\) by choosing an index whose parameter point is nearest to \(\hat\theta\); resolve ties by choosing the smallest index. If the true index is \(j\) but \(\hat J=k\neq j\), nearest-point choice implies \(d(\hat\theta,\theta_k)\leq d(\hat\theta,\theta_j)\). The triangle inequality therefore gives

\delta\leq d(\theta_j,\theta_k) \leq d(\theta_j,\hat\theta)+d(\hat\theta,\theta_k) \leq 2d(\theta_j,\hat\theta).

Hence squared loss is at least \(\delta^2/4\) whenever the classifier errs. Averaging over the prior and data gives

\sum_{j=1}^m w_jR(\theta_j,\hat\theta) \geq \frac{\delta^2}{4}P_\pi(\hat J\neq J) \geq \frac{\delta^2}{4}P_e^*(\pi).

This inequality holds for every estimator. Taking the infimum of its left side over estimators gives a lower bound on the Bayes risk; the prior-averaging theorem then bounds minimax risk below by that Bayes risk. \(\square\)

Worked Example: Three Hypotheses and Squared-Error Estimation

Let \(\Theta=\{-1,0,1\}\), with equal prior probabilities, and observe \(Y\in\{L,R\}\). The model is

Parameter	\(P_\theta(Y=L)\)	\(P_\theta(Y=R)\)
\(-1\)	\(4/5\)	\(1/5\)
\(0\)	\(1/2\)	\(1/2\)
\(1\)	\(1/5\)	\(4/5\)

First find the best prior-averaged classification accuracy. When \(Y=L\), the joint probabilities of the three parameter values and the observation are \(4/15,1/6,1/15\), respectively. The most probable label is \(-1\), contributing \(4/15\) to the probability of correct classification. When \(Y=R\), the joint probabilities are \(1/15,1/6,4/15\); the most probable label is \(1\), contributing another \(4/15\). Thus the largest possible correct-classification probability is \(8/15\), and the smallest error probability is \(1-8/15=7/15\).

The three parameter values are separated by at least \(\delta=1\). The separated-parameter reduction therefore gives

r(\pi)\geq \frac{1^2}{4}\frac{7}{15}=\frac{7}{60}.

By prior averaging, \(R_{\mathrm{minimax}}\geq r(\pi)\geq7/60\). The infimum over estimators is essential: the displayed lower bound applies to the best attainable prior-averaged risk, not to an arbitrary estimator’s average risk.

A Binary Testing Bound

For two hypotheses, the optimal equal-prior testing error has a direct expression in terms of total variation distance. For probability measures \(P_0\) and \(P_1\), define \(\operatorname{TV}(P_0,P_1)=\sup_A|P_0(A)-P_1(A)|\), where the supremum is over measurable events.

Theorem (binary testing error): With equal prior probabilities on \(P_0\) and \(P_1\), the smallest average probability of classification error is \((1-\operatorname{TV}(P_0,P_1))/2\).

Proof. A deterministic test chooses hypothesis 1 on an event \(A\) and hypothesis 0 otherwise. Its average error probability is

\frac12P_0(A)+\frac12P_1(A^c) =\frac12\{1-[P_1(A)-P_0(A)]\}.

Minimizing over \(A\) maximizes \(P_1(A)-P_0(A)\). The supremum of this difference is \(\operatorname{TV}(P_0,P_1)\), so the infimum error is \((1-\operatorname{TV}(P_0,P_1))/2\). Randomized tests cannot improve on this value, since their error is an average of the errors from choosing hypothesis 1 with a specified probability at each observation, and the pointwise choice minimizing error is to choose the hypothesis with larger probability mass (or density). \(\square\)

Worked Example: A Bernoulli Pair

Observe one \(X\) with \(X\sim\operatorname{Bernoulli}(\theta)\), where \(\theta\) is either \(0.4\) or \(0.6\). Use equal prior probabilities and squared-error loss for estimating \(\theta\).

The two parameter values are separated by \(\delta=0.6-0.4=0.2\). On the sample space \(\{0,1\}\), the probability differences are \(P_{0.4}(X=1)-P_{0.6}(X=1)=-0.2\) and \(P_{0.4}(X=0)-P_{0.6}(X=0)=0.2\). Therefore \(\operatorname{TV}(P_{0.4},P_{0.6})=0.2\). The optimal equal-prior testing error is

\frac{1-0.2}{2}=0.4.

An estimation error lower bound follows from the separated-parameter reduction:

R_{\mathrm{minimax}} \geq \frac{(0.2)^2}{4}(0.4) =\frac{0.04}{4}(0.4) =0.004.

This is a valid lower bound for the minimax squared-error risk over \(\{0.4,0.6\}\). Its value may be conservative; the argument guarantees a lower bound, not an exact risk calculation.

Common Pitfall and Practical Use

A common mistake is to write \(R_{\mathrm{minimax}}\geq r(\pi,\hat\theta)\) for an arbitrary fixed estimator and then use a large average risk as evidence of a large minimax risk. This does not follow: minimax risk takes an infimum over estimators, and a poor estimator can have a very large average risk even in an easy problem. The valid chain is

R_{\mathrm{minimax}} =\inf_{\hat\theta}\sup_{\theta\in\Theta}R(\theta,\hat\theta) \geq \inf_{\hat\theta}\int R(\theta,\hat\theta)\,\pi(d\theta) =r(\pi).

In practice, choose a prior concentrated on parameter values that are difficult to distinguish while remaining separated under the loss. Then lower-bound the best average testing error—for two points, the total-variation formula above is often useful—and convert testing error into loss. More elaborate methods use many hypotheses, but the logic remains the same: a procedure that estimates accurately would also solve a difficult identification problem.

Check Your Understanding

Work through these questions to check the logic of prior-based lower bounds.

Why must the infimum over estimators appear when deriving a minimax bound from a prior-averaged risk?
For a finite prior with masses \(w_j\), write the prior-averaged risk as a sum.
In the separated-parameter argument, explain why a wrong nearest-point classification implies estimation error at least \(\delta/2\).
Two equally likely hypotheses have total variation distance \(0.3\). What is their smallest possible average testing error?
For squared-error loss, what factor multiplies testing error in the lower bound when the parameter points are separated by \(\delta\)?