Stability of Least-Favorable Priors Under Loss Perturbations

Why Stability Needs More Than a Small Perturbation

In a finite decision problem, a small change in the loss function changes the entries of the risk matrix. Some consequences are automatically controlled: the Bayes risk and its maximum cannot change much. Other consequences are not automatic. A least-favorable prior can move substantially when the maximum is flat or nearly flat, and a rule that certifies minimaxity before perturbation may cease to do so afterward.

The key distinction is between stability of values and stability of optimizers. This tutorial makes that distinction quantitative, then gives conditions under which maximizing prior weights and Bayes rules do remain stable.

Finite Risk Matrices and Perturbations

Suppose the parameter space is \(\{\theta_1,\ldots,\theta_m\}\), and consider \(k\) available decision rules. The rules may include randomized rules. Write \(R_{ij}\) for the risk of rule \(i\) at parameter value \(\theta_j\). A prior is a vector \(\pi=(\pi_1,\ldots,\pi_m)\) in the probability simplex \(\Delta_m=\{\pi:\pi_j\geq 0,\ \sum_j\pi_j=1\}\). Its Bayes risk is the smallest prior-averaged risk among the available rules:

B_R(\pi)=\min_{1\leq i\leq k}\sum_{j=1}^m \pi_j R_{ij}.

A prior maximizing \(B_R(\pi)\) is called least favorable. When the rules include all randomized mixtures of finitely many pure rules, the minimum can still be taken over the pure rules: a mixture's average risk is a weighted average of the pure rules' average risks and cannot be smaller than their minimum.

Definition: Two risk matrices \(R\) and \(\widetilde R\) are within \(\delta\) in entrywise distance if \(\max_{i,j}|R_{ij}-\widetilde R_{ij}|\leq\delta\). If the sampling model is unchanged and every loss value changes by at most \(\delta\), then the risks are within \(\delta\), because taking an expectation cannot increase a uniform bound on absolute differences.

This matrix formulation applies whether the entries are given directly or calculated as expectations of losses. The stability conclusions below concern the finite risks; they do not require a particular distributional model.

Worked Example: A Unique Least-Favorable Prior Moves Smoothly

Consider two parameter values and two rules, with risk rows \((0,4)\) and \((3,0)\). Let \(p=\pi_1\), so \(\pi_2=1-p\). The prior risks of the two rules are \(4(1-p)\) and \(3p\), and hence \(B_R(p)=\min\{4(1-p),3p\}\). The first expression decreases and the second increases. They are equal when \(4-4p=3p\), or \(p=4/7\). The maximum Bayes risk is \(12/7\).

Now increase the second entry of the first row from \(4\) to \(4.1\). The new Bayes risk is \(B_{\widetilde R}(p)=\min\{4.1(1-p),3p\}\). The crossing is \(4.1-4.1p=3p\), so \(p=4.1/7.1=41/71\). The new maximum is \(3(41/71)=123/71\).

The prior changes by \(41/71-4/7=3/497\), about \(0.00604\). At the new least-favorable prior both pure rules are Bayes. Mix them by assigning probability \(q=3/7.1=30/71\) to the first rule. The mixture's risk at \(\theta_1\) is \(3(1-q)=123/71\), and its risk at \(\theta_2\) is \(4.1q=123/71\). Thus it has constant risk equal to the new Bayes value, providing an exact minimax certificate for the perturbed matrix.

What Is Always Stable: Bayes and Maximum Values

Theorem: If \(\max_{i,j}|R_{ij}-\widetilde R_{ij}|\leq\delta\), then for every prior \(\pi\), \(|B_R(\pi)-B_{\widetilde R}(\pi)|\leq\delta\). Consequently, if \(V_R=\max_{\pi\in\Delta_m}B_R(\pi)\) and \(V_{\widetilde R}=\max_{\pi\in\Delta_m}B_{\widetilde R}(\pi)\), then \(|V_R-V_{\widetilde R}|\leq\delta\).

Proof. For each rule \(i\) and prior \(\pi\), the difference between its prior risks is bounded by \[ \left|\sum_j\pi_jR_{ij}-\sum_j\pi_j\widetilde R_{ij}\right| \leq\sum_j\pi_j|R_{ij}-\widetilde R_{ij}| \leq\delta. \] If two finite lists of numbers differ coordinatewise by at most \(\delta\), their minima differ by at most \(\delta\): each entry of either list is at least the corresponding entry of the other list minus \(\delta\), and taking minima preserves that inequality in both directions. Applying this fact to the prior risks gives the asserted bound on Bayes risk. In particular, \(B_R(\pi)\leq B_{\widetilde R}(\pi)+\delta\) for every \(\pi\). Maximizing yields \(V_R\leq V_{\widetilde R}+\delta\); reversing the roles yields \(V_{\widetilde R}\leq V_R+\delta\). Therefore \(|V_R-V_{\widetilde R}|\leq\delta\). \(\square\)

The theorem controls the optimal value, not the location of its maximizer. A useful location bound needs an additional condition on how quickly the original Bayes risk falls away from its maximum.

Theorem: Let \(\pi^*\) maximize \(B_R\). Suppose there is a constant \(c>0\) such that \(B_R(\pi^*)-B_R(\pi)\geq c\|\pi-\pi^*\|_1\) for every \(\pi\in\Delta_m\). If \(\widetilde\pi\) maximizes \(B_{\widetilde R}\) and the matrices are within \(\delta\), then \(\|\widetilde\pi-\pi^*\|_1\leq 2\delta/c\).

Proof. Since \(\widetilde\pi\) maximizes the perturbed Bayes risk, \(B_{\widetilde R}(\pi^*)\leq B_{\widetilde R}(\widetilde\pi)\). The value bound already proved gives \[ B_R(\pi^*)\leq B_{\widetilde R}(\pi^*)+\delta \leq B_{\widetilde R}(\widetilde\pi)+\delta \leq B_R(\widetilde\pi)+2\delta. \] Thus \(B_R(\pi^*)-B_R(\widetilde\pi)\leq2\delta\). Combining this with the assumed growth condition gives \(c\|\widetilde\pi-\pi^*\|_1\leq2\delta\), as required. \(\square\)

The growth condition is substantive: it says the maximum is isolated with a definite drop in every direction away from \(\pi^*\). A unique maximum alone need not provide a useful linear bound; a nearly flat peak can allow a comparatively large movement under a small perturbation.

Worked Example: A Flat Maximum Does Not Select a Stable Prior

With two parameter values, consider three risk rows \((0,1)\), \((1,0)\), and \((0.4,0.4)\). For \(p=\pi_1\), their prior risks are \(1-p\), \(p\), and \(0.4\), so \(B_R(p)=\min\{1-p,p,0.4\}\). Its maximum is \(0.4\), attained at every \(p\in[0.4,0.6]\). The original problem therefore has no unique maximizing prior to track.

Now perturb the third row to \((0.4+\varepsilon,0.4-\varepsilon)\), where \(0<\varepsilon<0.1\). Its prior risk is \(0.4+\varepsilon(2p-1)\), an increasing function of \(p\). The perturbed Bayes risk is the minimum of this line, \(p\), and \(1-p\). The increasing line meets \(1-p\) at \(p^*=(0.6+\varepsilon)/(1+2\varepsilon)\). This point lies between \(0.5\) and \(0.6\): the first inequality follows from \(0.1>0\), and the second from \(\varepsilon<0.1\). At the crossing the line is below \(p\), since its value is \(1-p^*<p^*\). For smaller \(p\), the Bayes risk is at most the increasing line and is strictly below its value at the crossing; for larger \(p\), it is at most \(1-p\), which strictly decreases. Hence \(p^*\) is the unique perturbed maximizer.

As \(\varepsilon\) tends to zero, this selected maximizer tends to \(0.6\), but the unperturbed maximizing set contains every point from \(0.4\) to \(0.6\). A small change resolves the original nonuniqueness; it does not make an arbitrary prior chosen from that interval intrinsically stable.

Bayes-Rule Stability Depends on a Risk Margin

For a fixed prior, a uniquely best rule is stable if its advantage over every competitor is larger than the perturbation can erase. This advantage is its risk margin.

Theorem: Fix a prior \(\pi\). Suppose rule \(i\) is the unique Bayes rule and \(\sum_j\pi_jR_{hj}-\sum_j\pi_jR_{ij}\geq\gamma>0\) for every \(h\ne i\). If the risk matrices are within \(\delta\) and \(\gamma>2\delta\), rule \(i\) remains the unique Bayes rule under \(\widetilde R\).

Proof. Each rule's prior risk changes by at most \(\delta\). Therefore, for any \(h\ne i\), the perturbed risk difference between \(h\) and \(i\) is at least \[ \left(\sum_j\pi_jR_{hj}-\sum_j\pi_jR_{ij}\right)-2\delta \geq\gamma-2\delta>0. \] Every competitor still has strictly greater prior risk, so \(i\) remains the unique Bayes rule. \(\square\)

If the prior changes as well, the margin must also absorb the effect of that change. For example, if every original risk entry has absolute value at most \(M\), then changing the prior from \(\pi\) to \(\widetilde\pi\) changes any rule's prior risk by at most \(M\|\pi-\widetilde\pi\|_1\). The difference between two rules' risks can consequently change by at most \(2M\|\pi-\widetilde\pi\|_1\), in addition to the \(2\delta\) allowance for matrix perturbation. Thus a margin greater than \(2\delta+2M\|\pi-\widetilde\pi\|_1\) suffices to preserve the unique Bayes rule.

Worked Example: A Former Minimax Certificate Can Fail

Take two rules with risk rows \((0,2)\) and \((2,0)\). At prior \(p=1/2\), both are Bayes and have Bayes risk \(1\). Their equal mixture has risk vector \((1,1)\), so its maximum risk is \(1\). No rule can have maximum risk below the Bayes risk at \(p=1/2\): its maximum risk is at least its prior average. The mixture therefore certifies minimaxity.

Increase the second entry of the first row to \(2+\varepsilon\), with \(\varepsilon>0\). The two prior risks are \((2+\varepsilon)(1-p)\) and \(2p\). Their crossing gives the new least-favorable prior \(p^*=(2+\varepsilon)/(4+\varepsilon)\), and the Bayes value is \(2(2+\varepsilon)/(4+\varepsilon)=1+\varepsilon/(4+\varepsilon)\).

The old equal mixture now has risk vector \((1,1+\varepsilon/2)\). Its maximum risk exceeds the new Bayes value because \[ \frac{\varepsilon}{2}-\frac{\varepsilon}{4+\varepsilon} =\frac{\varepsilon(2+\varepsilon)}{2(4+\varepsilon)}>0. \] It is no longer a minimax certificate. Instead, mix the first rule with probability \(q=2/(4+\varepsilon)\). The two state risks are \(2(1-q)=2(2+\varepsilon)/(4+\varepsilon)\) and \((2+\varepsilon)q=2(2+\varepsilon)/(4+\varepsilon)\). This recomputed mixture has constant risk equal to the new Bayes value.

What Makes a Minimax Certificate Exact?

For a finite set of parameter values, a prior and a rule give a direct certificate when the rule is Bayes for that prior and its largest coordinate risk is no greater than the prior's Bayes risk. Here is why those two checks suffice. For any rule, its maximum coordinate risk is at least its average under any prior, and that average is at least the Bayes risk. Thus the prior Bayes risk is a lower bound on the minimax value. If a Bayes rule has every coordinate risk at most that same lower bound, it supplies a matching upper bound.

Key takeaway: A small perturbation always controls the Bayes-risk and minimax-value changes, but it does not automatically preserve a least-favorable prior, a Bayes rule, or an exact minimax certificate. Check a prior's separation from other maximizers, a rule's risk margin, and the perturbed rule's coordinate risks.

A frequent mistake is to argue that a certificate remains valid because all risks changed by at most \(\delta\). That only bounds the new risks; it does not show that the candidate rule's largest risk is at most the new Bayes lower bound. The worked example shows the gap explicitly. After perturbation, recompute the relevant Bayes risk and verify the coordinatewise upper bound rather than relying on approximate closeness.

Check Your Understanding

Use the finite risk-matrix framework to answer the following.

If every entry of a risk matrix changes by at most \(\delta\), what bound follows for the change in Bayes risk at a fixed prior? Why does the same bound hold for the maximum Bayes risk?
Why does uniqueness of a least-favorable prior, by itself, not guarantee a useful quantitative bound on how far it moves after perturbation?
A Bayes rule has prior-risk margin \(\gamma\) over every competitor. What condition on an entrywise perturbation bound \(\delta\) guarantees that it remains uniquely Bayes at the same prior?
In the flat-maximum example, describe the unperturbed maximizing set and the perturbed maximizing prior.
State the two checks that make a prior and a rule an exact finite minimax certificate, and explain why a small perturbation does not automatically preserve them.