Why Uniform Risk Errors Matter
In approximate minimax analysis, a risk function may be replaced by an approximation: a truncated risk, a risk evaluated on a finite parameter set, or a risk computed under an approximate model. The important question here is narrow and quantitative: if every rule’s risk at every parameter changes by at most a fixed amount, how much can the minimax value and the performance of a candidate rule change?
The word every is essential. A bound that holds uniformly over decision rules and parameter values controls the infimum over rules as well as the supremum over parameters. A bound that holds only for one selected rule generally does not control the minimax value.
Throughout, take \(\delta\geq 0\), and assume the maximum risks and minimax values under discussion are finite. The rule class and parameter space are the same for both risk families. These conditions avoid comparisons such as \(\infty-\infty\) and ensure that the two minimax problems are genuinely comparable.
Stability of a Rule’s Maximum Risk
The first consequence is pointwise in the decision rule: the largest risk of any fixed rule can change by no more than \(\delta\). This conclusion does not require that the supremum over \(\Theta\) be attained.
Proof. The uniform bound gives \(R_\theta(d)-\delta\leq\widetilde R_\theta(d)\leq R_\theta(d)+\delta\) for every \(\theta\). Taking suprema in the two inequalities yields \(M(d)-\delta\leq\widetilde M(d)\leq M(d)+\delta\). The displayed result follows. \(\square\)
Worked Example: Maximum Risk Under a Finite Perturbation
Consider two parameters, \(\theta_1,\theta_2\), and two available rules, \(A,B\). Suppose the risks are given by the following table; each entry is the risk of the rule in that row at the parameter in that column.
| Rule | \(\theta_1\) | \(\theta_2\) |
|---|---|---|
| \(A\) | 0 | 2 |
| \(B\) | 2 | 0 |
The maximum risks are \(M(A)=\max(0,2)=2\) and \(M(B)=\max(2,0)=2\). Now suppose the perturbed risks are \(\widetilde R(A)=(0.2,2.1)\) and \(\widetilde R(B)=(1.9,0.2)\), with coordinates ordered as \((\theta_1,\theta_2)\). The largest absolute entrywise change is \(0.2\), so this is a uniform \(0.2\)-perturbation over the two rules and parameters.
The perturbed maximum risks are \(\widetilde M(A)=\max(0.2,2.1)=2.1\) and \(\widetilde M(B)=\max(1.9,0.2)=1.9\). Thus the change is \(0.1\) for \(A\) and \(0.1\) for \(B\), each no larger than \(\delta=0.2\), as the theorem requires.
Stability of the Minimax Value
Since every rule’s maximum risk changes by at most \(\delta\), taking an infimum over the same rule class preserves the same error bound. In particular, this is a bound on the values themselves, not a claim that the rules attaining or nearly attaining those values are close to each other.
Proof. The preceding theorem gives \(M(d)-\delta\leq\widetilde M(d)\leq M(d)+\delta\) for every \(d\in\mathcal D\). Taking infima over \(d\) gives
By the definitions of \(V\) and \(\widetilde V\), this is \(V-\delta\leq\widetilde V\leq V+\delta\), which proves the claim. \(\square\)
The proof uses no assumption that a minimax rule exists. Infima may fail to be attained: the inequalities still hold because they apply to every rule before the infimum is taken.
Worked Example: A Candidate Rule Can Lose \(2\delta\) in Relative Performance
Let \(\Theta=\{\theta_1,\theta_2\}\), and suppose there are two available rules \(A,B\), with baseline and perturbed risks as follows.
| Rule | Baseline risks \((\theta_1,\theta_2)\) | Perturbed risks \((\theta_1,\theta_2)\) |
|---|---|---|
| \(A\) | \((1,4)\) | \((1.1,4.1)\) |
| \(B\) | \((4,1)\) | \((3.9,1.1)\) |
The largest change in any entry is \(\delta=0.1\). Under the baseline risks, \(M(A)=4\), \(M(B)=4\), and \(V=4\). Under the perturbed risks, \(\widetilde M(A)=4.1\), \(\widetilde M(B)=3.9\), and \(\widetilde V=3.9\). Rule \(A\), which was minimax under the baseline risks, is now \(4.1-3.9=0.2=2\delta\) above the perturbed minimax value. Thus the factor \(2\) in the transfer bound below cannot generally be removed.
Transferring Approximate Minimax Guarantees
A rule is \(\varepsilon\)-minimax under a risk family if its maximum risk is at most \(\varepsilon\) above that family’s minimax value. Uniform perturbation gives a direct guarantee for using such a candidate rule with the other risk family.
Proof. By the maximum-risk bound, \(\widetilde M(d)\leq M(d)+\delta\). The assumed approximate minimax property then gives \(\widetilde M(d)\leq V+\varepsilon+\delta\). The value bound implies \(V\leq\widetilde V+\delta\). Combining the inequalities yields \(\widetilde M(d)\leq\widetilde V+\varepsilon+2\delta\). Interchanging \(R\) and \(\widetilde R\) proves the reverse-direction statement. \(\square\)
The two contributions of \(\delta\) have different sources: the candidate rule’s maximum risk can increase by \(\delta\), while the perturbed minimax value can decrease by \(\delta\). The finite table above realizes both changes at once. In practice, if a numerical or truncated problem produces an \(\varepsilon\)-minimax rule and a uniform error bound \(\delta\) is available, this theorem turns that rule into an \((\varepsilon+2\delta)\)-minimax rule for the baseline risk.
Worked Example: Using a Computed Rule With the Baseline Risk
Suppose a numerical approximation gives \(\widetilde V=5.0\), and a computed rule \(d\) satisfies \(\widetilde M(d)=5.3\). It is therefore \(0.3\)-minimax for the perturbed risk, since \(5.3-5.0=0.3\). Suppose also that the uniform risk error is at most \(\delta=0.05\).
The value bound gives \(V\geq\widetilde V-\delta=4.95\), while the rule-specific bound gives \(M(d)\leq\widetilde M(d)+\delta=5.35\). For the relative guarantee, use the transfer theorem: \(M(d)\leq V+0.3+2(0.05)=V+0.4\). Thus the computed rule is at most \(0.4\)-minimax under the baseline risk. The conclusion is a bound relative to the unknown baseline value, not an assertion that \(M(d)=5.35\) or \(V=4.95\).
Value Stability Does Not Mean Rule Convergence
A small change in the minimax value says nothing by itself about whether minimax rules, or approximate minimax rules, are close as decision rules. The rule class may contain distinct rules with exactly the same risk; alternatively, different risk landscapes may have different near-minimizers even when their minimax values are nearly identical. Risk and value bounds are numerical performance statements, not compactness or uniqueness results about rules.
Worked Example: Alternating Exact Minimax Rules
Let the parameter space be \(\Theta=\{0\}\), let the observation be constant, and let the allowed actions be \(\mathcal A=\{-1,1\}\). Use squared-error loss \(L(\theta,a)=(a-\theta)^2\), and restrict the rule class to the two constant rules \(d_-(x)=-1\) and \(d_+(x)=1\). There is no uncertainty in the observation, so their risks are \(R_0(d_-) =(-1-0)^2=1\) and \(R_0(d_+)=(1-0)^2=1\). Consequently, \(M(d_-)=M(d_+)=1\) and \(V=1\).
Define a sequence by \(d_n=d_-\) for even \(n\) and \(d_n=d_+\) for odd \(n\). Every \(d_n\) is an exact minimax rule, and its risk is identically 1. Nevertheless, the actions selected by this sequence alternate between \(-1\) and \(1\), so the sequence does not converge pointwise as a sequence of rules. Even zero perturbation and exact minimaxity therefore do not force rule convergence.
There is a useful, weaker asymptotic conclusion. Suppose a fixed baseline risk \(R\) is compared with risk families \(R^{(n)}\) on the same \(\mathcal D\) and \(\Theta\), with uniform bounds \(\sup_{d,\theta}|R^{(n)}_\theta(d)-R_\theta(d)|\leq\delta_n\), where \(\delta_n\to0\). Let \(V_n\) be the minimax value for \(R^{(n)}\), and suppose \(d_n\) is \(\varepsilon_n\)-minimax for \(R^{(n)}\), where \(\varepsilon_n\to0\). The value bound gives \(|V_n-V|\leq\delta_n\), hence \(V_n\to V\). Applying the transfer theorem gives
Thus the baseline maximum risks of the candidate rules approach the minimax value in the sense that \(M(d_n)-V\leq\varepsilon_n+2\delta_n\to0\). This does not establish convergence of \(d_n\) to a rule. Such a conclusion would require additional structure and a specified notion of convergence; it does not follow from uniform risk control alone.
Common Mistake: Controlling Only One Rule
A tempting but invalid argument is: “The risk of my chosen candidate changed by at most \(\delta\), so the minimax value changed by at most \(\delta\).” The first clause bounds that candidate’s maximum risk. The minimax value, however, is an infimum over the entire rule class; a different rule may have changed substantially.
For example, take a one-parameter problem with two rules \(A,B\), so each rule has one risk value. Let the baseline risks be \(R(A)=100\) and \(R(B)=100\), and the perturbed risks be \(\widetilde R(A)=100\) and \(\widetilde R(B)=0\). The risk of candidate \(A\) has not changed at all, but \(V=100\) and \(\widetilde V=0\). There is no contradiction: the perturbation is not uniform over the rule class. A minimax-value guarantee requires the stated bound over every rule and every parameter.
Check Your Understanding
Use the definitions and bounds above to answer these questions.
- Why must a uniform perturbation bound cover all rules, rather than only the proposed candidate, to guarantee stability of the minimax value?
- If \(\delta=0.04\) and a rule is \(0.1\)-minimax under the baseline risk, what is its guaranteed minimax error under the perturbed risk?
- Which two changes account for the \(2\delta\) term in the candidate-rule guarantee?
- Can the minimax value converge while a selected sequence of minimax rules fails to converge? Explain using the alternating-rule example.
- If the perturbation bounds are \(\delta_n\to0\) and the candidate errors are \(\varepsilon_n\to0\), what does the transfer theorem imply about \(M(d_n)-V\)? What does it not imply?