Extreme Risk Vectors in Convex Class Reduction

Why Vertices Matter in a Convex Risk Set

In a finite decision problem, randomized rules can combine the risks of deterministic rules. This turns the set of attainable risk vectors into a convex polytope. Its vertices matter because every attainable risk vector is a convex combination of them: deterministic rules whose risk vectors are not vertices can be removed without changing that convex set. But this geometric reduction has limits. A vertex need not be undominated, and a mixture of vertex rules need not itself be a single deterministic rule.

Assume there are finitely many parameter values \(\theta_1,\ldots,\theta_m\), finitely many observations and actions, and finite losses. For a rule \(\delta\), write its risk vector as \(r(\delta)=(R(\theta_1,\delta),\ldots,R(\theta_m,\delta))\in\mathbb{R}^m\). There are finitely many deterministic rules; denote their risk vectors by \(r_1,\ldots,r_k\), allowing repeated vectors if different rules have the same risks. A randomized mixture chooses one of these rules with probabilities \(\lambda_1,\ldots,\lambda_k\), independently of the observation. Since expected loss is linear in this mixing distribution, its risk vector is \(\sum_j\lambda_jr_j\).

Definition: The convex hull of the deterministic risk vectors is \(C=\operatorname{conv}\{r_1,\ldots,r_k\}\), the set of their convex combinations. A point \(x\in C\) is an extreme point (or vertex) of \(C\) if, whenever \(x=ty+(1-t)z\) for \(y,z\in C\) and \(0<t<1\), it follows that \(y=z=x\). An exposed face of \(C\) is the set of minimizers of a nonzero linear functional over \(C\): for some \(w\in\mathbb{R}^m\setminus\{0\}\), \(F_w=\{x\in C:w\cdot x=\min_{y\in C}w\cdot y\}\).

An extreme point cannot be made by mixing two different attainable risk vectors. An exposed face records all risk vectors tied for a particular weighted-risk criterion. These are related but distinct ideas: a face can contain many points, including points that are not extreme.

What Extremality Says About a Mixture

There is an important asymmetry in the test for extremality. If a specified convex representation of \(x\) uses an extreme point, every positively weighted generator in that representation must equal \(x\). The converse does not follow from checking just one representation: another representation might express \(x\) as a mixture of different points.

Theorem: If \(x=\sum_{j=1}^k\lambda_jr_j\), where \(\lambda_j\geq0\), \(\sum_j\lambda_j=1\), and \(x\) is extreme in \(C\), then \(r_j=x\) for every \(j\) with \(\lambda_j>0\). Conversely, \(x\) is extreme if and only if every convex representation of \(x\) by the generators \(r_1,\ldots,r_k\) has all its positively weighted generators equal to \(x\).

Proof. For the first claim, choose an index \(j\) with \(\lambda_j>0\). If \(\lambda_j=1\), the representation gives \(r_j=x\). If \(0<\lambda_j<1\), set \(y=(1-\lambda_j)^{-1}\sum_{\ell\ne j}\lambda_\ell r_\ell\). The remaining weights, after division by \(1-\lambda_j\), sum to one, so \(y\in C\), and \(x=\lambda_jr_j+(1-\lambda_j)y\). Extremality implies \(r_j=y=x\). This applies to every positively weighted index.

For the converse, suppose every convex representation of \(x\) by the generators has only \(x\) among its positively weighted generators. If \(x=ty+(1-t)z\) for \(y,z\in C\) and \(0<t<1\), express \(y\) and \(z\) as convex combinations of the \(r_j\). Substituting these combinations gives a convex representation of \(x\) by the generators. Every generator with positive resulting weight must equal \(x\). Therefore both \(y\) and \(z\), which are themselves convex combinations using only generators equal to \(x\), equal \(x\). Thus \(x\) is extreme. \(\square\)

Worked Example: Why One Representation Is Not Enough

Let the risk vectors be \(r_1=(0,1)\), \(r_2=(1,1)\), and \(r_3=(2,1)\). The convex hull is the horizontal line segment from \((0,1)\) to \((2,1)\). The vector \(x=(1,1)\) has a representation that puts weight one on \(r_2\). In this specified representation, its only positively weighted generator equals \(x\).

Nevertheless, \(x\) is not extreme: it also has the representation \(x=\tfrac12r_1+\tfrac12r_3=\tfrac12(0,1)+\tfrac12(2,1)=(1,1)\). This is why the condition in the converse must apply to every convex representation, not merely one selected representation. By contrast, the endpoints are extreme: any convex combination of these three vectors equal to \((0,1)\) must put all its weight on \((0,1)\), and the corresponding statement holds for \((2,1)\).

Removing Redundant Generators

A deterministic rule is redundant for the randomized risk set if its risk vector can be removed from the list of generators without changing \(C\). In a finite convex hull, the distinct vertices are sufficient generators. In particular, if a listed risk vector is not extreme, it can be expressed as a convex combination of the other listed vectors and can be deleted.

Theorem: For a finite list of risk vectors, each non-extreme listed vector is a convex combination of the other listed vectors. Consequently, removing all non-extreme vectors leaves the same convex hull. The remaining distinct vectors are exactly the vertices of \(C\).

Proof. Let \(r_i\) be a listed vector that is not extreme. Then \(r_i=ty+(1-t)z\) for distinct \(y,z\in C\) and \(0<t<1\). Write \(y=\sum_j a_jr_j\) and \(z=\sum_j b_jr_j\), with nonnegative coefficients in each representation summing to one. Substitution gives \(r_i=c r_i+\sum_{j\ne i}d_jr_j\), where \(c=ta_i+(1-t)b_i\) and \(d_j=ta_j+(1-t)b_j\). If \(c=1\), all the other coefficients in both representations must be zero; that would give \(y=z=r_i\), contrary to their being distinct. Hence \(c<1\). Rearranging and dividing by \(1-c\) expresses \(r_i\) as a convex combination of the other listed vectors. Removing it therefore leaves the hull unchanged. Repeating this finite deletion removes every non-extreme listed vector. Every vertex of \(C\) must be on the original list, by the extremality result above, and a vertex cannot be removed by this argument. Thus the remaining distinct vectors are exactly the vertices. \(\square\)

Worked Example: A Risk-Preserving Reduction

Consider three parameter values and four deterministic rules with risk vectors \(A=(0,4,2)\), \(B=(2,1,2)\), \(C=(4,0,2)\), and \(D=(2,2,2)\). The vector \(D\) is the midpoint of \(A\) and \(C\): \[ D=\tfrac12A+\tfrac12C =\tfrac12(0,4,2)+\tfrac12(4,0,2) =(2,2,2). \] Thus \(D\) is not extreme and can be deleted without changing the randomized risk set. Rule \(D\) is not useless in the sense that its risk is unattainable after deletion: randomizing equally between rules \(A\) and \(C\) attains exactly the same risk vector.

The remaining vectors \(A,B,C\) are vertices. For example, every vector in their convex hull has third coordinate 2. In the first two coordinates, \(A,B,C\) are not collinear: the slopes from \(A\) to \(B\) and from \(B\) to \(C\) are \(-3/2\) and \(-1/2\). Each is therefore a vertex of their triangle. The reduction preserves every attainable risk vector, but it does not claim that the deleted deterministic rule is replaced by one deterministic vertex rule; its exact replacement here is a randomized mixture.

Exposed Faces and Weighted-Risk Criteria

A linear functional selects the part of the risk polytope that is best for its particular weighting of parameter-specific risks. For a finite generator list, the exposed face has a direct description: retain exactly the generators that attain the smallest weighted risk. Any mixture whose risk lies on that face can use only those minimizing generators.

Theorem: Let \(w\ne0\), let \(m_w=\min_j w\cdot r_j\), and define \(I_w=\{j:w\cdot r_j=m_w\}\). Then \(F_w=\operatorname{conv}\{r_j:j\in I_w\}\). If a mixture \(x=\sum_j\lambda_jr_j\) belongs to \(F_w\), every \(j\) with \(\lambda_j>0\) belongs to \(I_w\).

Proof. Every point of \(C\) is a convex combination of the \(r_j\), and \(w\cdot r_j\geq m_w\) for each \(j\). If \(x=\sum_j\lambda_jr_j\) lies in \(F_w\), then \(0=w\cdot x-m_w=\sum_j\lambda_j(w\cdot r_j-m_w)\). Every summand is nonnegative. A positively weighted summand must therefore be zero, so its generator lies in the minimizing set \(I_w\). This proves that \(F_w\) is contained in the stated convex hull. Conversely, any convex combination of generators in \(I_w\) has weighted risk \(m_w\), so it belongs to \(F_w\). \(\square\)

Worked Example: Finding a Weighted-Risk Face

Return to \(A=(0,4,2)\), \(B=(2,1,2)\), \(C=(4,0,2)\), and \(D=(2,2,2)\). Take \(w=(1,1,0)\), so the criterion is the sum of the first two risks. The weighted risks are \(w\cdot A=4\), \(w\cdot B=3\), \(w\cdot C=4\), and \(w\cdot D=4\). The minimum is 3, attained only by \(B\); consequently \(F_w=\{B\}\). No mixture involving \(A,C,\) or \(D\) with positive probability can have weighted risk 3.

Now take \(w=(0,0,1)\). Every listed vector has weighted risk 2, so the exposed face is all of \(C\). This criterion distinguishes none of the rules because it ignores the first two coordinates. In this example the weight vector is nonzero, as required, even though two of its coordinates are zero.

Extremality Is Not Admissibility

The vertices are the irreducible generators of the convex risk set, but vertex status alone does not establish that a rule is admissible. A risk vector \(s\) dominates \(r\) when \(s_i\leq r_i\) in every coordinate and \(s_i<r_i\) in at least one. A vertex can still be dominated by another attainable vector. Conversely, a weighted-risk minimizer need not be a vertex if the exposed face contains multiple points.

When every coordinate of \(w\) is strictly positive, any vector \(r\in F_w\) is undominated in \(C\). Indeed, if \(s_i\leq r_i\) for all \(i\) with a strict inequality in at least one coordinate, then \(w\cdot s<w\cdot r\), contradicting that \(r\) minimizes \(w\cdot x\) over \(C\). This is a sufficient geometric guarantee of undominated risk for that criterion. If some weights are zero, a strict improvement in a zero-weight coordinate may leave the weighted risk unchanged, so this argument no longer establishes undominatedness across all coordinates.

Worked Example: An Extreme Vector That Is Dominated

Let \(P=(1,3)\), \(Q=(3,1)\), and \(T=(4,4)\). These three points are not collinear, so each is a vertex of their triangular convex hull. In particular, \(T\) cannot be represented as a mixture of \(P\) and \(Q\): every such mixture has coordinate sum 4, whereas \(T\) has coordinate sum 8. Yet \(P\) dominates \(T\), since \(1<4\) and \(3<4\). Thus \(T\) is extreme but dominated.

The positive weighted criterion \(w=(1,1)\) has weighted risks \(4,4,\) and \(8\) at \(P,Q,\) and \(T\), respectively. Its exposed face is the segment \(\operatorname{conv}\{P,Q\}\), and \(T\) is not on it. This example shows why vertex status is a statement about convex representation, not a standalone claim about decision-theoretic admissibility.

Using Vertices in Class Reduction

For a finite problem with randomization allowed, one representative rule for each distinct vertex risk vector is enough to generate the entire attainable risk set by mixing. This is a risk-preserving reduction: every original randomized risk remains attainable in the reduced randomized class, and every risk in the reduced class was already attainable. A rule with a non-vertex risk can be dropped because its risk is reproduced by a mixture of the retained vertex representatives.

This conclusion is deliberately about the convex risk set. It does not say that a class containing only the deterministic vertex rules can attain every interior risk without randomization. Nor does it say that each removed rule is dominated by one retained rule. The replacement can require a mixture, and its role is to preserve risks rather than to establish a coordinatewise improvement.

Key takeaway: Vertices are the minimal generators of a finite convex risk set; exposed faces identify the generators tied under a chosen linear risk criterion. Use them to reduce a randomized class without changing its attainable risks, but assess domination separately.

Check Your Understanding

Work through each question using the definitions and results above.

If \(x\) is extreme and has a specified convex representation by listed risk vectors, what must be true of each positively weighted vector?
Why does a single representation in which all positively weighted generators equal \(x\) fail to prove that \(x\) is extreme?
In a finite convex risk set, why can a non-extreme listed risk vector be removed without changing the convex hull?
For a nonzero weight vector \(w\), which generators can have positive weights in a mixture whose risk lies on \(F_w\)?
Why does a strictly positive weighted-risk minimizer have undominated risk, and why can that argument fail when some weights are zero?
What does a vertex-based reduction preserve, and what does it not claim about deterministic replacement or domination?