Optimal Allocation and Volume under Surface

1 Introduction

• Principled criteria for evaluating multi-class classifiers remain lacking, and VUS meaning for classifications without ranked classes has not been examined.The paper provides an explicit formulation, estimators, and inference procedures for volume under ROC surfaces with K ≥2 classes.Source: §1 · pp. 1–2
• The convex body beneath the ROC surface is an Aumann expectation of a random polytope, enabling a mixed-volume calculation.For independent feature draws, the method uses Minkowski mixed volumes.Source: §1 · p. 2
• Unlike prior set-identification work, the parameter of interest here is the volume functional of certain sets rather than the sets themselves.The paper describes this as a distinction from work on identification regions formed through Aumann expectations.Source: §1 · p. 2
• The proposed DML estimator converges at essentially the 1/√n rate and has an asymptotically linear representation.The paper also proposes cross-validation for Kth-order U-statistics to achieve estimation efficiency.Source: §1 · p. 2
• The volume method also applies to projected critical-function sets, including feasible-error sets and a generalized Gini coefficient.In these applications, set volumes measure informativeness and inequality, respectively.Source: §1 · pp. 2–3

2 Volume under the Receiver Operating Characteristic Surface

• The ROC body collects accuracy requirements generated by allocation rules using observed features.The section treats this body as the region below the ROC frontier.Source: §2 · p. 3
• An Aumann representation combined with mixed-volume methods gives an explicit formula for the ROC-body volume.The formula expresses the volume through an expected maximum over class assignments and permits calculation without reconstructing the frontier.Source: §2 · p. 3
• The framework is compared with a Lagrangian approach and relates volume to the information observed features provide about class labels.The section presents this as an interpretation of what the volume reflects.Source: §2 · p. 3

2.1 Allocation rules and the ROC body

• A randomized allocation rule uses observed features and assigns class k with probability ϕk(X).The rule is a measurable map from the feature space to the probability simplex.Source: §2.1 · p. 4
• The class-k true-positive rate is the probability of assigning an observation to class k conditional on its true class being k.For a rule ϕ, it is defined as Tk(ϕ) = E[ϕk(X) | C = k].Source: §2.1 · p. 4
• The upper ROC frontier gives the greatest class-1 rate achievable for each feasible set of minimum true-positive-rate requirements for classes 2 through K.The ROC body is the region below that frontier and corresponds to feasible nonnegative requirement vectors.Source: §2.1 · pp. 4–5

2.2 Aumann representations of the ROC body

• Γ is the set of true-positive-rate vectors obtained as allocation rules vary.Aumann integration represents it using expectations of measurable selections of the pointwise integrand sets.Source: §2.2 · pp. 5, 7
• H is downward closed: any nonnegative requirement vector coordinatewise below a feasible vector is also feasible.The allocation rule that meets the larger vector also meets every smaller requirement.Source: §2.2 · p. 5
• For each requirement vector t, the upper ROC frontier records the largest first-class rate among vectors with rates at least t in classes 2 through K.In the two-class illustration, Panel (a) selects the highest point with T2(ϕ) ≥ t2, and Panel (b) traces those maxima over [0, 1].Source: §2.2 · p. 5, Figure 1 · p. 6
• Γ = EA[F(X)], and the Aumann representation establishes that Γ is compact and convex.The result applies because the set-valued function F is measurable, integrably bounded, and has nonempty compact convex values.Source: §2.2 · p. 7

Proposition 2.8. For the set-valued function F in (8),

• Γ is compact and convex, contains the coordinate simplex ΔK−1, and the constrained maximum defining β1(t) is attained by an allocation rule.Thus an optimal allocation rule exists for every t, so the upper ROC frontier is well defined.Source: Proposition 2.8. For the set-valued… · pp. 8, 10

The simplices D(x) are all contained in the same fixed simplex,

• The coordinate simplex D(x) is the convex hull of the origin and the class-density-ratio coordinate vectors; the origin represents unused allocation probability.Its measurable selections correspond to the nonnegative measurable allocation functions used to represent H.Source: Proposition 2.8. For the set-valued… · p. 11, The simplices D(x) are all contained… · p. 13
• The Aumann representation of H implies that H is compact and convex.The simplices D(x) are contained in a common fixed simplex, supporting the required integrability condition.Source: The simplices D(x) are all contained… · pp. 12–13

Proposition 2.12. The ROC body H satisfies

• 1/K! ≤ VolK(H) ≤ 1, with H a compact convex set having nonempty interior.The lower and upper bounds follow from containing the coordinate simplex and lying within the unit cube.Source: Proposition 2.12. The ROC body H… · p. 14
• VolK(H) = 1/K! in the uninformative case where P1 = · · · = PK.Here the class density ratios are all 1, so H is the coordinate simplex.Source: Proposition 2.12. The ROC body H… · p. 14
• VolK(H) = 1 in the perfectly informative case, where an allocation rule achieves T(ϕ) = (1, . . . , 1).The ROC body is then the unit cube [0, 1]K.Source: Proposition 2.12. The ROC body H… · p. 14

2.3 Minkowski sums, mixed volume and Hausdorff distance

• For compact convex sets, mixed volume is defined by polarization and determines the volume polynomial of weighted Minkowski sums.The Minkowski volume theorem applies to nonempty compact convex sets and nonnegative weights.Source: §2.3 · p. 15

Consider the two-dimensional coordinate simplices

• A weighted Minkowski sum of two coordinate simplices decomposes into translated copies of the scaled simplices and a rectangle.The rectangle has side lengths 3λ1/2 and 3λ2/2 and contributes the term involving both weights.Source: Consider the two-dimensional… · p. 16, areas gives · p. 16

areas gives

• The two-dimensional area terms combine into 8λ2_1 + 9/4λ1λ2 + 3/8λ2_2.The cross-weight term comes from the rectangle in the decomposition.Source: areas gives · p. 16

For these two-dimensional arguments, Definition 2.13 gives

• In two dimensions, the mixed volume of A1 and A2 equals Vol2(A1 + A2) − Vol2(A1) − Vol2(A2), and the same form applies to nonempty polytopes, including segments and points.The mixed volume is symmetric in its two arguments.Source: For these two-dimensional arguments,… · p. 16, areas gives · p. 16

• Hausdorff convergence of nonempty compact convex sets implies convergence of their volume.Source: In Figure 2(b), the blue and orange… · p. 17
• For fixed weights, weighted Minkowski sums approach one another as each component set approaches in Hausdorff distance.Source: In Figure 2(b), the blue and orange… · p. 17
• Mixed volume is continuous when each nonempty compact convex set in its arguments converges in Hausdorff distance.The proof uses volume convergence and the polarization formula, a finite linear combination of volumes.Source: In Figure 2(b), the blue and orange… · pp. 17–18
• Since every nonempty compact convex set can be approximated by polytopes, its mixed volume can be approximated by mixed volumes of those polytopes.Source: In Figure 2(b), the blue and orange… · p. 18

1. Symmetry and nonnegativity. The function V is symmetric in its arguments and satisfies

• V is symmetric, nonnegative, and monotone under set inclusion; it is linear in each argument and V(A, …, A) = VolK(A).Source: §1 · p. 18

2.4 Computing the volume of the ROC body

• VolK(H) equals the expected mixed volume of K independent copies of the random coordinate simplex D(X).Source: §2.4 · p. 24

the ROC body H,

• For coordinate simplices D(x1), …, D(xK), the mixed volume is the maximum permutation product of coordinate lengths divided by K!.Source: §2.4 · p. 25
• A doubly stochastic assignment formulation and its dual yield matching lower and upper bounds for the mixed volume.The dual constraints construct scaled coordinate simplices containing the original simplices; monotonicity and homogeneity of mixed volume give the upper bound.Source: the ROC body H · pp. 27, 29

in Figure 2(b) gives a gray rectangle of area

• For K = 2, the two permutation products yield rectangle areas 9/4 and 1/4, with 9/4 matching the mixed-volume maximum.Source: in Figure 2(b) gives a gray rectangle… · pp. 30–31, Figure 3 · p. 31

the ROC body H,

• The ROC volume is the expectation of the largest permutation product of density ratios, divided by K!.The Aumann representation turns the body’s volume into an expected mixed volume, which the coordinate-simplex formula evaluates without first reconstructing the ROC frontier.Source: in Figure 2(b) gives a gray rectangle… · p. 31

in Figure 2(b) gives a gray rectangle of area

• The method computes the volume of the entire ROC body without first reconstructing its frontier, leaving a finite assignment problem and an expectation.For each tuple, the assignment uses the K^2 density-ratio values q_k(x_r).Source: in Figure 2(b) gives a gray rectangle… · p. 32
• Choosing the most likely class assignment maximizes the probability of recovering all labels, and that optimal probability equals VolK(H).The setup draws one observation independently from each class, randomly orders them, and hides their labels.Source: in Figure 2(b) gives a gray rectangle… · p. 32
• With no feature information, VolK(H) = 1/K!; with perfect identification, VolK(H) = 1, and the excess over 1/K! measures the recovery improvement from features.Source: in Figure 2(b) gives a gray rectangle… · pp. 32–33

which is the conventional AUC formula.3

• For K=2, the volume is an expectation of the larger posterior-probability product, giving the conventional binary ROC AUC formula.Ties cannot be omitted when the posterior probability distribution has a discrete component.Source: in Figure 2(b) gives a gray rectangle… · p. 33, which is the conventional AUC formula.3 · p. 33

3.1 Neyman orthogonality

• Neyman orthogonality and sample splitting yield an asymptotically efficient double/debiased estimator for the population VUS.Source: §3.1 · p. 34

3.1.1 Double/debiased estimator

• The estimator uses a symmetrized U-statistic score whose candidate probabilities select a permutation while observed class labels evaluate it, preserving expectation θ0.Source: §3.1.1 · pp. 35–36

3.1.2 Assignment margin assumptions

• Assignment-margin conditions require first-step consistency, stability of exact ties, and a pairwise assignment margin; the margin condition may fail with countably infinite discrete support.Source: §3.1.2 · pp. 37–39

Consequently,

• The threshold t is used only to split the proof and does not enter the estimator or assignment algorithm.Source: Consequently · p. 41

3.1.3 Assignment regret

• Switching from the tie-broken oracle to another true co-maximizer gives zero population regret, so exact ties do not contribute to the population residual.Source: §3.1.3 · p. 41

For the supremum norm,

• The supremum-norm argument splits pairwise contrasts into small-margin and large-error cases, then sums the resulting bounds over finitely many pairs.The proof conditions on the training sample and uses a small-margin/large-margin decomposition.Source: For the supremum norm · p. 42

Corollary 3.6. For some s ∈(1, ∞), suppose

• For s = 2 and β = 1, the rate condition requires δ2,n = oP(n^-3/8), while a hard margin yields the familiar oP(n^-1/4) L2 requirement.Source: Corollary 3.6. For some s ∈(1, ∞),… · p. 43

respect to Tn and independent of the evaluation sample. Then

• A fixed-degree symmetric square-integrable kernel independent of the evaluation sample has variance bounded using a constant that depends only on its degree.Source: Lemma 3.7. Under the preceding… · p. 43, respect to Tn and independent of the… · p. 44

or suppose (68) holds. Then

• The residual argument combines a margin bound, which makes the conditional population residual negligible at the root-n scale, with comparison consistency, which makes the estimated-kernel difference vanish in conditional second moment.Source: or suppose (68) holds. Then · p. 44
• Under Proposition 3.9’s conditions and a nondegenerate first projection, Theorem 3.11 gives an asymptotic normality result for the estimator.The proof invokes the central limit theorem after replacing the oracle kernel with the estimated kernel.Source: or suppose (68) holds. Then · p. 44, Consequently · p. 45

Consequently,

• The variance-estimation procedure defines a leave-one-out projection estimate; the proof uses it to establish the stated variance result.The supplied passages do not provide the estimate’s formula or the result’s full statement.Source: Consequently · p. 46, If the root-n rate condition of… · p. 47

If the root-n rate condition of Theorem 3.11 also holds, then

• The exact-tie-broken robust estimator needs no assignment tolerance, permits exact co-optimal ties under a stable deterministic convention, and uses the first-step score through the exact maximum.The cited summary also identifies a pairwise margin assumption and a product perturbation bound in its residual estimate.Source: If the root-n rate condition of… · p. 47

3.2 Sample splitting

• The Kth-order sample-splitting scheme forms a cross-validation VUS estimate by weighted-averaging fold estimates over cells with nonempty test and training sets; the section’s properties apply to it.The scheme is described as not balanced.Source: §3.2 · pp. 48–49
• Theorem 3.11 also holds with bθcv,n replacing bθn, and weighted averaging across cell estimates accounts for differing numbers of K-tuples per cell.Source: §3.2 · p. 50
• An alternative double/debiased cross-validation estimator constructs one moment condition throughout the Kth-order U-statistic using the entire sample.For each fold, it uses the corresponding training and test sets, with the nuisance function estimated on the training set.Source: §3.2 · p. 50
• When different cell interval collections yield the same union and training set, storing and retrieving trained models avoids redundant training and reduces computation time.Source: §3.2 · p. 50

4.1 Aumann expectation of random segments

• Aumann expectations of random segments are compact, convex zonoids, and their volumes admit an expected mixed-volume representation.Integrable selections of [0,a(x)] correspond to measurable allocation rules assigning probabilities to its endpoints; finite-valued approximations yield the zonoid limit.Source: §4.1 · pp. 51, 52, 55

Proposition 4.5. Under the assumptions above,

• Vol_K(E_A[D_a(X)]) = K!E_P^K[|det(a(X_1),…,a(X_K))|]|, giving the segment Aumann expectation’s volume as an expected absolute determinant.The expectations are finite, including when the Aumann expectation has zero K-dimensional volume.Source: Proposition 4.5. Under the assumptions… · p. 55, §4.1 · p. 55

4.2 Feasible error set in fairness-accuracy algorithm design

• For binary decisions, the section characterizes attainable group-loss vectors and computes the group-loss set’s volume under fairness–accuracy preferences.The setup has at least two groups with positive population shares; preferences favor lower errors across groups and lower disparity, with at least one strict improvement.Source: §4.2 · p. 56
• The feasible group-error set satisfies T0 − Γ = E_A[[0, γ(X)]], allowing its volume to be evaluated by applying Proposition 4.5 in dimension G.Here γ_g(x) = q_g(x)[ℓ_g(1, x) − ℓ_g(2, x)].Source: §4.2 · p. 57

For independent X1, . . . , XG ∼P,

• The expectations in the feasible-error-set representation are finite, including when Γ has zero G-dimensional volume.Source: For independent X1, . . . , XG ∼P · p. 57

The feasible welfare-share set has volume

• The feasible welfare-share set has population-share bounds 1 − R(1 − t) ≤ t0 ≤ R(t) for jointly feasible welfare shares t.The lower bound is attained by selecting the complement of a population attaining R(1 − t); for (0.20, 0.30), the example gives a minimum share of 0.10.Source: §4.3 · p. 60

4.3 Gini coefficients and Lorenz volumes

• For K welfare measures, the multivariate Gini coefficient is the normalized Lorenz volume, and Proposition 4.5 evaluates both volumes in dimensions K + 1 and K.When K = 1, the construction recovers the ordinary income Gini coefficient.Source: §4.3 · pp. 59, 61

The feasible welfare-share set has volume

• A larger index means a wider average gap between attainable population shares holding the same welfare shares, capturing inequality across population sizes; for income alone it is the ordinary Gini coefficient, while multiple welfare variables yield joint welfare concentration.The index averages the difference R(t) + R(1 − t) − 1 uniformly over the feasible welfare-share set using K-dimensional volume.Source: The feasible welfare-share set has… · p. 61

Expanding the determinant in (107) and substituting the normalized incomes gives

• The Lorenz-curve connection uses the normalized-income quantile Q: the poorest population share p holds income share L(p), with L(1) = 1.For U uniform on (0, 1), Q(U) has the same distribution as normalized income.Source: Expanding the determinant in (107) and… · p. 62

X2 gives

• Symmetry and integration by parts derive the income identity, and the argument also applies to income distributions with atoms.The geometric interpretation compares the smallest attainable income share L(p) with the largest, 1 − L(1 − p).Source: X2 gives · p. 62

In the last line, the substitution u = 1 −p gives

• Substituting u = 1 − p in the last line gives the Gini coefficient in (97).Source: In the last line, the substitution u =… · p. 62

5 Conclusion

• A random-polytope method calculates population VUS using Minkowski mixed volumes and applies to data-generating processes with atoms or singular components.The method is based on convex geometry.Source: §5 · p. 63
• The population VUS takes the form of an expectation of a symmetric U-statistic kernel.The framework addresses the lack of a widely accepted multiclass counterpart to the prominent binary AUC measure.Source: §5 · p. 63
• The paper proposes a double/debiased machine-learning U-statistic estimator of VUS, derives its asymptotic properties, and develops asymptotically valid inference.Source: §5 · p. 63
• The volume method also applies to other projected critical-function sets, including feasible error sets across predefined groups and a generalized multivariate Gini coefficient.Source: §5 · p. 63