What Completeness Requires
Admissibility asks whether a particular rule can be improved upon. Completeness asks a class-level question: can every rule in the decision problem be replaced by a rule from the proposed class without increasing risk at any parameter value? The word every matters. A class may contain excellent rules and still fail to be complete because it cannot replace even one rule in the ambient problem.
The comparison is made across the whole parameter space, not at a single selected parameter or under an average of risks. This tutorial focuses on finite decision problems, where the risk of each rule can be listed and compared directly.
The ambient class is part of the definition. A class can be complete relative to one restricted collection of rules but not relative to a larger collection. The risk function, and hence the pointwise comparisons, also depend on the model and loss function.
Risk Vectors in Finite Problems
Suppose the parameter space is finite, \(\Theta=\{\theta_1,\ldots,\theta_k\}\). Each rule \(\delta\) can then be summarized by its risk vector \(\bigl(R(\theta_1,\delta),\ldots,R(\theta_k,\delta)\bigr)\). A rule weakly replaces another exactly when every coordinate of its risk vector is no larger. Replacing rules by their risk vectors makes the completeness test finite whenever the ambient class of rules is finite.
In a finite observation space with finitely many actions, the deterministic decision rules form a finite class: each rule assigns one of the available actions to each possible observation. If the sampling distributions and losses are specified, the risk of each such rule is obtained by averaging its loss over the observation distribution at each parameter value.
Worked Example: Testing a Class Against a Risk Table
Suppose an ambient problem has four rules with risks at two parameter values as follows. Consider whether \(\mathcal C=\{A,B\}\) is complete.
| Rule | \(R(\theta_1,\delta)\) | \(R(\theta_2,\delta)\) |
|---|---|---|
| A | 1 | 4 |
| B | 3 | 2 |
| C | 4 | 5 |
| D | 2 | 4 |
For rule \(A\), the class can select \(A\) itself, giving equality at both parameter values. For \(B\), it can select \(B\) itself. For \(C\), rule \(A\) has risks \(1\leq4\) and \(4\leq5\), so \(A\) weakly replaces \(C\). For \(D\), \(A\) has risks \(1\leq2\) and \(4=4\), so it weakly replaces \(D\). Every rule in the ambient class therefore has a weakly no-worse representative in \(\mathcal C\), and \(\mathcal C\) is complete.
Now consider the smaller class \(\{A\}\). It cannot replace \(B\), because \(A\)'s risk at \(\theta_2\) is \(4\), which exceeds \(B\)'s risk \(2\). Thus \(\{A\}\) is not complete, even though it replaces \(C\) and \(D\). Completeness is not a claim that a class replaces most rules; it must replace all of them.
Calculating Risks Before Comparing Classes
When risks are not already tabulated, calculate them from the model and loss. For a finite observation space \(\mathcal X\), a deterministic rule \(\delta\), and loss \(L(\theta,a)\), the risk is $$ R(\theta,\delta)=\sum_{x\in\mathcal X}P_\theta(X=x)L\bigl(\theta,\delta(x)\bigr). $$ This is an expectation over the possible observations under the specified parameter value. The risk comparison must then be checked separately at each parameter value.
Worked Example: Completeness in a Binary Classification Problem
Let \(\Theta=\{0,1\}\), let \(X\in\{0,1\}\), and suppose \(P_0(X=1)=0.2\) and \(P_1(X=1)=0.8\). There are two actions, \(a_0\) and \(a_1\), with loss 0 for choosing the action indexed by the true parameter and loss 1 otherwise. There are exactly four deterministic rules, corresponding to the four possible assignments of actions to \(X=0\) and \(X=1\).
Let \(\delta_{\mathrm{match}}\) choose \(a_0\) at \(X=0\) and \(a_1\) at \(X=1\). At \(\theta=0\), it errs only when \(X=1\), so \(R(0,\delta_{\mathrm{match}})=P_0(X=1)=0.2\). At \(\theta=1\), it errs only when \(X=0\), so \(R(1,\delta_{\mathrm{match}})=P_1(X=0)=1-0.8=0.2\). Its risk vector is \((0.2,0.2)\).
The constant rule \(\delta_0\), which always chooses \(a_0\), has risk 0 at \(\theta=0\) and risk 1 at \(\theta=1\), so its vector is \((0,1)\). The constant rule \(\delta_1\), which always chooses \(a_1\), has vector \((1,0)\). The remaining rule chooses \(a_1\) at \(X=0\) and \(a_0\) at \(X=1\). It errs at \(\theta=0\) when \(X=0\), with probability \(0.8\), and at \(\theta=1\) when \(X=1\), also with probability \(0.8\). Its vector is \((0.8,0.8)\).
The first three vectors, \((0.2,0.2)\), \((0,1)\), and \((1,0)\), are pairwise incomparable: for each pair, one vector has a smaller coordinate and a larger coordinate. Each is also no larger than neither of the other two. But \((0.2,0.2)\leq(0.8,0.8)\) in both coordinates, so \(\delta_{\mathrm{match}}\) replaces the remaining rule. Consequently, the class consisting of \(\delta_{\mathrm{match}},\delta_0,\delta_1\) is complete. The singleton class containing only \(\delta_{\mathrm{match}}\) is not: its risk at \(\theta=0\) exceeds \(\delta_0\)'s, and its risk at \(\theta=1\) exceeds \(\delta_1\)'s.
A Finite Criterion for Completeness
A risk vector is called minimal among an attainable set of risk vectors if no attainable vector is no larger in every coordinate and strictly smaller in at least one coordinate. Minimality concerns the risk vectors in the specified ambient problem; it does not mean that the vector is smallest at each coordinate separately.
Proof. Write \(r(\delta)=\bigl(R(\theta_1,\delta),\ldots,R(\theta_k,\delta)\bigr)\). By the definition of completeness, for every \(\delta\in\mathcal D\) there must be a \(\delta'\in\mathcal C\) such that \(R(\theta_i,\delta')\leq R(\theta_i,\delta)\) for every index \(i\). These inequalities are exactly the coordinatewise comparison \(r(\delta')\leq r(\delta)\). This proves the first statement in both directions.
For the final statement, start with any attainable risk vector \(r\). If it is not minimal, some attainable vector is no larger in every coordinate and strictly smaller in at least one. Replace \(r\) by that vector and repeat whenever the current vector is not minimal. Each replacement moves to a distinct vector, because at least one coordinate strictly decreases. There are only finitely many attainable vectors, so this process must terminate at a minimal vector \(m\), with \(m\leq r\) coordinatewise. By assumption, some rule in \(\mathcal C\) has risk vector \(m\). That rule weakly replaces the rule with risk vector \(r\). Since this applies to every attainable \(r\), the first statement implies that \(\mathcal C\) is complete. \(\square\)
Worked Example: A Complete Class From Minimal Risk Vectors
Consider a finite problem with three parameter values and five deterministic rules. Suppose their risk vectors are \(r_1=(0,2,2)\), \(r_2=(2,0,2)\), \(r_3=(2,2,0)\), \(r_4=(1,1,1)\), and \(r_5=(3,3,3)\). These vectors can, for example, be realized in a no-observation problem by taking the five rules to be five actions and using the displayed entries as their losses at the three parameter values.
The first four vectors are minimal. For \(r_1\), for instance, each of \(r_2,r_3,r_4\) has at least one coordinate greater than the corresponding coordinate of \(r_1\), so none weakly replaces it; the same coordinate check shows that none of the other first four vectors weakly replaces \(r_2,r_3,\) or \(r_4\). In contrast, \(r_1=(0,2,2)\leq(3,3,3)=r_5\), so rule 1 replaces rule 5.
It follows that the class containing rules 1 through 4 is complete: it contains each minimal risk vector, and rule 1 replaces the only remaining rule. Omitting rule 4 makes the class incomplete. Each of rules 1, 2, and 3 has a coordinate equal to 2 where \(r_4\) has 1, so none weakly replaces rule 4. Rule 5 also cannot replace rule 4, since all its coordinates are 3. This example shows why a class generally needs representatives of all the minimal risk vectors, not just a rule that performs well on average across parameter values.
Common Pitfall: Checking Only One Parameter or One Summary
A tempting but incorrect argument is: “Rule \(A\) has lower risk than rule \(B\) at \(\theta_1\), so \(A\) replaces \(B\).” Pointwise replacement requires the inequality at every parameter value. In the binary classification example, \(\delta_0\) has lower risk than \(\delta_{\mathrm{match}}\) at \(\theta=0\), since \(0<0.2\), but has higher risk at \(\theta=1\), since \(1>0.2\). It therefore does not replace \(\delta_{\mathrm{match}}\).
A second error is to compare average risks under an arbitrarily chosen weighting of parameter values and treat the result as a completeness test. Such an average can rank rules, but it does not establish the coordinatewise inequalities in the definition. The correct procedure is to list the risks at each parameter value, test all coordinates, and repeat the test for every ambient rule.
Check Your Understanding
Use coordinatewise risk comparisons to answer each question.
- A class contains rules with risk vectors \((1,3)\) and \((3,1)\). Does it weakly replace a rule with risk vector \((2,2)\)? Explain.
- In the binary classification example, why does the rule with risk vector \((0.8,0.8)\) not need its own representative in a complete class?
- Can a class be complete if it contains only one rule? State the risk-vector condition that would make this possible.
- Why does checking that a candidate rule has lower risk at one parameter value not establish that it replaces another rule?
- In a finite problem, explain why repeatedly replacing a nonminimal risk vector by a strictly smaller attainable vector must eventually stop.