3.7 Minimax Estimation

1 Definition

The idea is to minimize the worst-case risk $\underset{δ}{minimize} sup_{θ} R (θ; δ) .$

Minimax Risk

The minimum achievable sup-risk is called the minimax risk of the estimation problem $r^{*} = inf_{δ} sup_{θ} R (θ; δ) .$
An estimator $δ^{*}$ is called minimax if it achieves the minimax risk: $r^{*} = sup_{θ} R (θ; δ^{*}) .$

Game theory interpretation:

Analyst chooses estimator $δ$ .
Nature chooses parameter $θ$ to maximize the risk.

Nature chooses $θ$ adversarially, not $X$ .

Compare to Bayes estimator ("maximin" game):

Nature chooses prior $Λ$ .
Analyst chooses estimator to minimize the average risk.

2 Least Favorable Priors

The key observation is: average-case risk $\leq$ worst-case risk. So for any proper prior $Λ$ : $r_{Λ} = \underset{Bayes}{\underset{⏟}{inf_{δ} \int R (θ; δ) d Λ (θ)}} \leq \underset{minimax}{\underset{⏟}{inf_{δ} sup_{θ} R (θ; δ)}} = r^{*} .$
Prior $Λ^{*}$ is least favorable if it gives best lower bound, i.e. $r_{Λ^{*}} = sup_{Λ} r_{Λ}$ .
For any $Λ$ , $r_{Λ} \leq r_{Λ^{*}} \leq r^{*} \leq sup_{θ} R (θ; δ) .$

Theorem

Suppose $Λ$ is a prior, with Bayes estimator $δ_{Λ}$ . If $r_{Λ} = sup_{θ} R (θ; δ_{Λ})$ , then

$δ_{Λ}$ is minimax.
If $δ_{Λ}$ is unique Bayes (up to a.s.) for $Λ$ , it is unique minimax.
$Λ$ is least favorable.

Proof

For any other $δ$ , $\begin{aligned} sup_{θ} R (θ; δ) & \geq \int R (θ; δ) d Λ (θ) \\ (*) & \geq \int R (θ; δ_{Λ}) d Λ (θ) \\ = r_{Λ} = sup_{θ} R (θ; δ_{Λ}) . \end{aligned}$
(last equality is by assumption) So $δ_{Λ}$ is minimax risk, $δ_{Λ}$ is minimax estimator.
Replace $\geq$ with $>$ in (*).
For any other prior $\tilde{Λ}$ , $\begin{aligned} r_{\tilde{Λ}} & = inf_{δ} \int R (θ; δ) d \tilde{Λ} (θ) \\ \leq \int R (θ; δ_{Λ}) d \tilde{Λ} (θ) \\ \geq sup_{θ} R (θ; δ_{Λ}) = r_{Λ} . \end{aligned}$

So when is average risk = sup risk?
This is true if

$R (θ; δ_{Λ})$ is constant.
$Λ ({θ : R (θ; δ_{Λ}) = max_{ζ} R (ζ; δ_{Λ})}) = 1$ .

Example (Binomial)

$X \sim Binomial (n, θ)$ , estimate $θ$ w.r.t square error.
Try $Beta (α, β)$ . Hope to get one with constant risk. Recall this example, we have $δ_{α, β} = \frac{α + X}{α + β + n}$ . Try $α = β$ (symmetric), then $\begin{aligned} MSE (θ; δ_{α, α}) & = {(\frac{α + θ n}{2 α + n} - θ)}^{2} + (2 α + n)^{- 2} {Var}_{θ} (X) \\ = (2 α + n)^{- 2} [α^{2} (1 - 2 θ)^{2} + n θ (1 - θ)] \\ = (2 α + n)^{- 2} [(4 α^{2} - n) θ^{2} - (4 α^{2} - n) θ + α^{2}] \\ = \frac{n}{4 (n + \sqrt{n})^{2}} = \frac{1}{4 (\sqrt{n} + 1)^{2}} . \end{aligned}$ Here we pick $α^{*} = \frac{\sqrt{n}}{2}$ . So $δ^{*} (X) = \frac{\frac{\sqrt{n}}{2} + X}{\sqrt{n} + n}, r^{*} = \frac{1}{4 (\sqrt{n} + 1)^{2}}$ , $Λ^{*} = Beta (\frac{\sqrt{n}}{2}, \frac{\sqrt{n}}{2}) \propto_{θ} θ^{\frac{\sqrt{n}}{2} - 1} (1 - θ)^{\frac{\sqrt{n}}{2} - 1}$ . This is concentrated at $θ = \frac{1}{2}$ .

2.1 Least Favorable Prior Sequence

Sometimes there is no least favorable prior. Like $X \sim N (θ, 1)$ .

Lease Favorable Prior Sequence

A sequence $Λ_{1}, Λ_{2}, \dots$ is least favorable if $r_{Λ_{n}} \to sup_{Λ} r_{Λ}$ .

Theorem

$Λ_{1}, Λ_{2}, \dots$ is a prior sequence, and $δ$ satisfies $sup_{θ} R (θ; δ) = lim_{n \to \infty} r_{Λ_{n}}$ . Then

$δ$ is minimax.
$Λ_{1}, Λ_{2}, \dots$ is least favorable.

Proof

For another $\tilde{δ}$ , $\forall n$ , $\begin{aligned} sup_{θ} R (θ; \tilde{δ}) \geq \int R (θ; \tilde{δ}) d Λ_{n} (θ) \geq r_{Λ_{n}} \\ \Rightarrow & sup_{θ} R (θ; \tilde{δ}) \geq sup_{n} r_{Λ_{n}} \geq lim_{n \to \infty} r_{Λ_{n}} = sup_{θ} R (θ; δ) . \end{aligned}$
For prior $Λ$ , $\begin{aligned} r_{Λ} & = inf_{δ} \int R (θ; δ) d Λ (θ) \leq \int R (θ; δ) d Λ (θ) \\ \leq sup_{θ} R (θ; δ) = lim_{n \to \infty} r_{Λ_{n}} . \end{aligned}$

Example

$X \sim N_{d} (θ, I_{d})$ . Estimate $θ$ , using MSE. $δ_{0} (X) = X$ is unbiased, with MSE $d$ .
Try prior $Λ_{n} : θ_{i} \overset{i . i . d}{\sim} N (0, n)$ , then $δ_{Λ_{n}} (X) = (1 - ζ) X$ . So $MSE (θ; δ_{Λ_{n}}) = ζ^{2} | | θ | |^{2} + (1 - ζ)^{2} d .$ So $\begin{aligned} r_{Λ_{n}} & = E [MSE (θ)] = ζ^{2} n d + (1 - ζ)^{2} d \\ = d (\frac{n}{(1 + n)^{2}} + \frac{n^{2}}{(1 + n)^{2}}) \to d . \end{aligned}$
So $Λ_{1}, Λ_{2}, \dots$ is least favorable. $δ_{0} (X)$ is minimax. $r^{*} = d$ .

3 Bounding Minimax Risk

Our theorem gives an idea of how to bound $r^{*}$ for a problem:

Upper bound: if $δ$ is any estimator then $r^{*} \leq sup_{θ} R (θ; δ)$ . ("=" if $δ$ is minimax)
Lower bound: if $Λ$ is any prior then $r^{*} \geq \int R (θ; δ_{Λ}) d Λ (θ)$ . ("=" if $Λ$ is least favorable).

Minimax estimators are very hard to find but minimax bounds are often used in statistics theory to characterize hardness (especially lower bound).

Example

Propose practical estimator $δ$ , find $Λ$ for which $r_{Λ}$ is close to $sup_{θ} R (θ; δ)$ . (or same rate, or converges asymptotically) Conclude $δ$ can't be improved "much".
Quantify hardness of a problem by its minimax rate in some asymptotic regime.
Caveat: a problem might be easy throughout most of parameter space but very hard in some bizarre corner you never encounter in practice.