Why Expanding Parameter Sets Need Error Control
A common strategy in minimax analysis is to solve a sequence of problems on increasingly large subsets of the parameter space. Each restricted problem may be easier than the full problem. But two approximations are involved: the restricted parameter set omits part of the space, and the risk used in the restricted problem may itself be approximate. To use the resulting rules responsibly, we need to measure these errors separately.
The central distinction is between risk approximation error, which compares two risk functions on the same restricted parameter set, and exhaustion error, which measures how much risk may be missed by restricting the parameter set. A bound on the first does not by itself control the second.
Restricted and Full Minimax Values
Let \(\mathcal D\) be a fixed, nonempty class of decision rules, and let \(\Theta\) be the parameter space. For each \(\delta\in\mathcal D\), write \(R(\theta,\delta)\) for its risk at parameter \(\theta\). Suppose the parameter sets satisfy \(\Theta_m\subseteq\Theta_{m+1}\) and \(\bigcup_{m=1}^{\infty}\Theta_m=\Theta\). Define the maximum risks and minimax values by
Here “maximum risk” means supremum risk; the supremum need not be attained. Assume the minimax values under discussion are finite. Since \(\Theta_m\subseteq\Theta\), every rule satisfies \(M_m(\delta)\le M(\delta)\), and therefore \(V_m\le V\). Also, \(M_m(\delta)\) is nondecreasing in \(m\) for each fixed rule, so \(V_m\) is nondecreasing. These facts give \(V_m\le V\), but do not alone prove that \(V_m\) converges to \(V\).
A Convergence Theorem with Two Error Terms
Now suppose that on \(\Theta_m\) we use an approximate risk \(\widetilde R_m(\theta,\delta)\). Its restricted maximum risk and minimax value are
The following result states what is needed for convergence and gives a direct error guarantee for rules chosen from the approximate problems.
Proof. The set inclusion gives \(V_m\le V\). The exhaustion bound implies, for every rule,
Taking infima over the same class \(\mathcal D\) gives \(V\le V_m+\tau_m\). Together these inequalities yield \(0\le V-V_m\le\tau_m\).
The uniform risk approximation implies
Taking infima in both inequalities gives \(V_m-\eta_m\le\widetilde V_m\le V_m+\eta_m\), hence \(|\widetilde V_m-V_m|\le\eta_m\). The triangle inequality now gives \(|\widetilde V_m-V|\le\eta_m+\tau_m\).
Finally, apply the risk approximation and the assumed near-optimality of \(\delta_m\), then use the exhaustion bound:
By definition, a rule whose full maximum risk is at most \(V+\varepsilon\) is \(\varepsilon\)-minimax. The stated error guarantee follows. Since \(0\le V-V_m\le\tau_m\), \(\tau_m\to0\) implies \(V_m\to V\); the bound on \(\widetilde V_m\) gives its convergence as well. \(\square\)
Worked Examples
Worked Example: Exact Convergence in a Squared-Error Decision Problem
Let \(\Theta=\{1,2,\ldots\}\), let the decision be \(a\in[0,1]\), and define the risk \(R(\theta,a)=(a-p_\theta)^2\), where \(p_\theta=1-1/\theta\). Take \(\Theta_m=\{1,\ldots,m\}\). Find the restricted and full minimax values, and verify an exhaustion bound.
For \(\theta\le m\), \(p_\theta\) ranges from \(0\) to \(b_m=1-1/m\). For any \(a\in[0,1]\), the largest squared distance over this interval occurs at an endpoint, so
The maximum is minimized when the two endpoint risks are equal: \(a^2=(b_m-a)^2\). Since \(0\le a\le b_m\), this gives \(a=b_m/2\), and
Over the full space, \(p_\theta\) approaches \(1\) as \(\theta\) increases, while \(p_1=0\). Thus \(M(a)=\max\{a^2,(1-a)^2\}\); the infimum occurs at \(a=1/2\), giving \(V=1/4\). Consequently \(V_m\to V\), with the exact gap
For any \(\theta>m\), \(0\le p_\theta-b_m<1/m\). Since \(a,p_\theta,b_m\in[0,1]\),
The point \(p_m=b_m\) is included in the restricted set. Therefore every omitted risk is at most \(M_m(a)+2/m\), so the uniform exhaustion bound holds with \(\tau_m=2/m\). This bound is valid, although the exact value gap above is sharper.
Worked Example: Carrying Approximation Error Into a Rule Guarantee
Use the preceding decision problem at \(m=4\). Then \(b_4=3/4\), the restricted minimizer is \(a_4=3/8\), and \(V_4=9/64=0.140625\). Suppose the approximate risk is \(\widetilde R_4(\theta,a)=R(\theta,a)+a/80\).
Because \(0\le a\le1\), the difference between the risks is at most \(1/80=0.0125\), so \(\eta_4=0.0125\). The theorem gives
Choose an approximate minimizer \(\delta_4\) satisfying \(\widetilde M_4(\delta_4)\le\widetilde V_4+0.01\); such a rule exists by the definition of an infimum. The exhaustion bound gives \(\tau_4=2/4=0.5\). Applying the proof’s inequalities in order,
The full minimax value is \(V=0.25\), so this calculation certifies that the selected rule is \(0.425625\)-minimax. The general theorem gives the slightly looser bound \(0.01+2(0.0125)+0.5=0.535\) on its excess risk: it uses \(V\) in place of the known, smaller \(V_4\) at the last step. The two contributions from \(\eta_4\) have distinct roles: one transfers the approximate rule’s risk back to the true restricted risk, and one relates the approximate minimax value to \(V_4\).
Worked Example: A Nonvanishing Approximation Error Leaves a Value Gap
Let \(\Theta=\{0\}\), let \(a\in[0,1]\), and set \(R(0,a)=a^2\). For every \(m\), use \(\Theta_m=\Theta\), but approximate the risk by \(\widetilde R_m(0,a)=a^2+0.1\). Compute both minimax values.
The true minimax value is \(V=0\), attained at \(a=0\), because \(\inf_{a\in[0,1]}a^2=0\). The approximate minimax value is \(\widetilde V_m=0.1\) for every \(m\), since \(\inf_{a\in[0,1]}(a^2+0.1)=0.1\). Here the exhaustion error is zero, but the uniform approximation error is \(0.1\), not a sequence tending to zero. Thus the approximate values do not converge to the true value. Even with no omitted parameter values, a persistent risk-approximation error can persist in the minimax value.
Using the Bounds and Avoiding a Common Mistake
The theorem is useful when a difficult full minimax problem is replaced by a sequence of manageable restricted problems. It supplies a bookkeeping rule: first bound how much the approximate risk changes the restricted value, then bound how much the restriction changes the full value. To certify a rule, also include its optimization tolerance \(\alpha_m\). If those three errors vanish, the values converge and the selected rules become minimax in the approximate sense.
The uniform exhaustion hypothesis can be strong. It requires control over the full maximum risk relative to the restricted one for every rule. For a particular sequence of selected rules, it is enough to verify the weaker, rule-specific inequality \(M(\delta_m)\le M_m(\delta_m)+\tau_m\); the same rule-bound proof then applies. But such a sequence-specific condition alone does not establish the theorem’s value-convergence claim for the entire decision class.
Common mistake: “The sets \(\Theta_m\) increase to \(\Theta\), so the restricted minimax values must converge to the full minimax value.” The inclusion argument proves only that \(V_m\) increases and remains below \(V\). It does not give an upper bound on \(V-V_m\). The correction is to establish an exhaustion bound (or an appropriate bound for the candidate rules) and make its error tend to zero. Likewise, a uniform approximation bound that does not vanish can leave a persistent gap, as the preceding example shows.
Check Your Understanding
Use the definitions and bounds above to answer the following.
- Why does \(\Theta_m\subseteq\Theta_{m+1}\) imply \(V_m\le V_{m+1}\), but not by itself imply \(V_m\to V\)?
- State the uniform risk approximation condition that yields \(|\widetilde V_m-V_m|\le\eta_m\).
- If \(\tau_m\to0\), what two inequalities bound \(V-V_m\)?
- In the squared-error example, verify the value of \(V_3\) and the exact gap \(V-V_3\).
- For an approximate restricted rule, identify the separate roles of \(\alpha_m\), \(\eta_m\), and \(\tau_m\) in the full excess-risk bound.