Proof Workshop: Reduction by Convexity and Domination

Why Convexity Gives a Class-Reduction Argument

Suppose risk is evaluated at a finite collection of parameter values. Each decision rule can then be represented by a vector whose coordinates are its risks at those values. A randomized rule formed by mixing other rules has the corresponding mixture of their risk vectors. This turns class reduction into a geometric question: which vectors in the convexified risk set can be improved in every coordinate, and which vectors suffice to cover the rest?

The central conclusion is precise but limited. Under compactness, every attainable vector is coordinatewise at least as large as some undominated vector. Keeping representatives for the undominated vectors therefore preserves a replacement for every risk vector in the original convexified class. This does not, by itself, say that finitely many representatives suffice or that they can be chosen from a nonrandomized class.

Risk Vectors and Convexification

Let the parameter set under consideration be \(\{\theta_1,\ldots,\theta_m\}\), where \(m\) is a positive integer. For a decision rule \(\delta\), its finite risk vector is \(r(\delta)=(R(\theta_1,\delta),\ldots,R(\theta_m,\delta))\in\mathbb{R}^m\). The coordinates record risk at the selected parameter values; they are not a single average of those risks.

A randomized mixture selects one of a finite collection of rules independently of the data, using fixed probabilities. Its risk at each parameter value is the same probability-weighted average of the component rules’ risks. Thus, for rules \(\delta_1,\ldots,\delta_k\) and probabilities \(\lambda_i\geq0\) with \(\sum_{i=1}^k\lambda_i=1\), the mixture has risk vector \(\sum_{i=1}^k\lambda_i r(\delta_i)\).

Indeed, the set of mixing weights \(\{(\lambda_1,\ldots,\lambda_k):\lambda_i\geq0,\ \sum_i\lambda_i=1\}\) is the compact probability simplex in \(\mathbb{R}^k\). The map taking the weights to \(\sum_i\lambda_i r(\delta_i)\) is continuous, so its image \(C\) is compact. The formula for mixture risks shows that every mixture yields a point in this image, and the definition of randomized mixture shows that each point in the image is attainable. This argument is useful because the replacement result below requires an attained minimum, not just an infimum.

The Compact Risk-Set Replacement Theorem

The theorem uses compactness to attain a minimum on the part of \(C\) that can replace \(x\). Convexity is not needed for this particular replacement step; it matters earlier when randomized mixtures are used to create the risk set. The proof also explains why the replacement is undominated in the whole set, rather than merely locally improved.

Proof. Fix \(x\in C\), and define \(C_x=\{z\in C:z_j\leq x_j\text{ for all }j\}\). This set is nonempty because \(x\in C_x\). It is closed in \(C\), since each condition \(z_j\leq x_j\) defines a closed subset of \(\mathbb{R}^m\). Hence \(C_x\) is compact. The continuous function \(s(z)=\sum_{j=1}^m z_j\) attains a minimum on \(C_x\); choose a minimizer \(y\in C_x\).

Suppose, for contradiction, that some \(w\in C\) strictly dominates \(y\). Then \(w_j\leq y_j\leq x_j\) for every \(j\), so \(w\in C_x\). Because \(w\neq y\) and all its coordinates are no greater, at least one coordinate is strictly smaller; therefore \(\sum_j w_j<\sum_j y_j\). This contradicts the minimality of \(y\) on \(C_x\). Thus \(y\) is undominated in \(C\), and \(y_j\leq x_j\) for each coordinate by the definition of \(C_x\). \(\square\)

From Vectors Back to Decision Rules

Let \(\mathcal{D}\) be a class of rules whose risk vectors form \(C\), and suppose every vector in \(C\) is represented by at least one rule in \(\mathcal{D}\). Retain the rules whose risk vectors are undominated in \(C\). The theorem says that, for every \(\delta\in\mathcal{D}\), there is a retained rule \(\delta^\star\) satisfying \(R(\theta_j,\delta^\star)\leq R(\theta_j,\delta)\) for all \(j=1,\ldots,m\). Thus the retained rules form a risk-covering class on these parameter values.

When \(C\) is the convex hull of finitely many original risk vectors, every point in \(C\) is represented by a randomized mixture of the original rules. The theorem’s replacement therefore has a rule representation if those mixtures are included in \(\mathcal{D}\). It need not be one of the original deterministic rules. A claim that a deterministic replacement always exists would require an additional result or assumption; convex geometry alone does not establish it.

What the Reduction Does—and Does Not—Guarantee

The reduction matters because it separates two tasks. Convexification identifies risks achievable by randomization; coordinatewise comparison then discards risks for which a no-worse alternative exists. The theorem guarantees that an undominated replacement is attained, rather than merely approached, provided the risk set is compact. For finitely many initial risk vectors, the convex hull supplies that compactness automatically.

The set of undominated vectors need not be finite. For example, if \(C\) is the line segment joining \((0,1)\) and \((1,0)\) in \(\mathbb{R}^2\), every point \((t,1-t)\), \(0\leq t\leq1\), is undominated: decreasing one coordinate along the segment increases the other. The theorem gives risk coverage by the undominated set, not necessarily by a finite list of representatives.

A related pitfall is to minimize the sum of all risk coordinates over all of \(C\) and call the minimizer a complete representative. That procedure may find an undominated vector, but it need not find a replacement for every other vector. For instance, in the preceding segment, \((1/2,1/2)\) minimizes the coordinate sum, while neither endpoint is dominated by it. The theorem avoids this error by minimizing the sum only among vectors already constrained to be no greater than the particular \(x\) being replaced.