Many decisions involve more than two choices and stakes that differ for every case. A fraud system might approve, send to review, or block each transaction. A clinical triage system might send each patient home, admit them, or escalate their care. Two quantities shape each decision. The first is the example's own stake: the dollar amount at risk, or the severity of missing this patient. The second is an exchange rate between that stake and the fixed cost of acting, such as the cost of an analyst's minute or a bed. That exchange rate is rarely known when the model is trained. Ranking metrics such as the multi-class area under the ROC curve (AUC: the probability that the model scores a randomly chosen case of one class above a case of another) are popular precisely because they hedge over unknown operating points. But they treat every example as equally important. Example-dependent cost-sensitive learning, which assigns each training example its own cost matrix, has the opposite problem: it assumes the exact costs are known and fixed.
This note proposes a training loss and a matching evaluation metric that sit between these two extremes. Each example carries a family of cost matrices indexed by the unknown exchange rate. The loss is the expected cost of the decision the model would make, averaged over a plausible range of exchange rates. For the K actions, the cost of each action is linear in the exchange rate, so this average can be computed exactly and differentiated in O(K log K) time per example. The method uses a lower-envelope computation, the multi-class, per-example analogue of the convex-hull trick behind the VOROS metric. In two sentences: AUC hedges over unknown thresholds but ignores per-example stakes, while example-dependent costs respect stakes but assume a single known threshold. We build a proper loss that does both, and we test whether it beats the obvious recipe of training a calibrated model and applying the cost-sensitive Bayes rule at test time.
Core Claim
Each example $i$ has a nonnegative stake $z_i$, for example a transaction amount. Its cost of taking action $k$ when the true class is $j$ is $C_i(\theta)_{jk} = A_{jk} + \theta z_i B_{jk}$. Here $A$ holds fixed handling costs (review or block costs), $B$ says how the stake enters each error, and $\theta$ is the unknown exchange rate with density $\pi$ on a range elicited from the domain. Given predicted class probabilities $p$, the plug-in action at rate $\theta$ is $a_p(\theta) = \arg\min_k \sum_j p_j C_i(\theta)_{jk}$. We train with
$$\ell_i(p, y) = \int C_i(\theta)_{y,\, a_p(\theta)}\, \pi(\theta)\, d\theta ,$$
the cost actually paid on example $i$, averaged over exchange rates.
Three properties make this loss worth studying.
It is proper. Under any true class distribution $q$, reporting $p=q$ selects the Bayes action at every $\theta$. No other report can do better, so the loss never rewards distorted probabilities.
It is exactly computable. For a fixed $p$, the expected cost of each action is a line in $\theta$. The plug-in action therefore switches at most $K-1$ times along the $\theta$ range, at points given by the lower envelope of $K$ lines. The integral is a finite sum over envelope segments.
It is differentiable almost everywhere. For any single $\theta$, the cost is a step function of $p$. After integration, though, the switch points move continuously with $p$. The gradient flows through those switch locations.
The loss spends the model's accuracy where decisions actually change for that particular example. It ignores probability errors that would not flip any action within the plausible range. That is the key difference from weighting cross-entropy by the stake, which demands accuracy everywhere on high-stake examples.
The same quantity, averaged over a test set and normalized between a trivial policy and an oracle, gives an evaluation metric. We call it the stake-integrated cost volume. It extends VOROS, a binary metric that integrates classifier quality over a scalar cost axis, in the two directions its authors list as open: more than two classes, and costs that vary per instance.
Position Relative to Prior Work
Four papers motivate the gap.
VOROS and Partial VOROS lift ROC analysis into a 3D space with a cost axis, and Partial VOROS adds precision and capacity constraints. Both are binary, class-level, evaluation-only metrics. VOROS also shows the metric matters for model selection: on Dal Pozzolo fraud, a model with AUROC 79.5% beats one with 85.3% once costs are accounted for. We keep the idea of integrating over the cost axis but make it per-example, multi-class, and trainable.
Weighted ROC in cost space does train against sampled costs. It uses a bilevel optimization with kernel-smoothed thresholds and reports profit 6526 versus 4955 for binary cross-entropy on Jane Street. However, it is binary, its costs are global rather than tied to examples, and it pays a substantial bilevel overhead. Our exact envelope computation needs no inner optimization loop and no smoothing bandwidth.
Wang et al. found that the classifier with the highest multi-class AUC achieved the lowest cost on 22 of 26 UCI datasets under uncertain class-level cost matrices. After Platt scaling, they report a Spearman correlation of −0.80 between multi-class AUC and cost. That is the strongest evidence that ranking metrics are a good hedge. We test whether it survives once costs vary per example.
Two papers supply the method's ingredients and its warning signs. Hepburn et al. build proper losses tailored to each example's exact cost matrix. They report total cost 2.06 versus 6.85 for cross-entropy on German Credit, and 556.19 on the 13-genre Million Song task. However, sharpening their loss toward the true step-function cost makes it non-convex and hard to optimize. Our loss targets a band of exchange rates rather than a point. We expect the integral over $\theta$ to supply the smoothing that their tuning parameter supplies artificially. Scott shows that surrogate regret bounds for example-dependent costs weaken under heavy-tailed costs, so we treat per-example normalization of $z_i$ as a design variable rather than an afterthought.
Mao et al. prove that in restricted model classes, the optimal decision boundary for a cost-weighted objective can have a different orientation from the probability-estimation optimum. This is our main theoretical reason to expect any gain over plug-in decisions. It also predicts where the gain should vanish: in highly flexible models.
The multi-class ranking literature constrains the design. Clémençon et al. show that decomposing a K-class ranking problem into adjacent two-class problems is optimal only under a monotone likelihood ratio condition, and that aggregating the pieces is NP-hard. Narasimhan et al. explain why pair- and tuple-based metrics resist mini-batch training. We therefore deliberately choose a loss that decomposes over single examples, as Kotlowski et al. and Agarwal showed is possible for binary AUC through strongly proper losses. We do not attempt pairwise or volume-under-surface optimization.
Research Program
The first component is the metric and its estimator. We will implement the stake-integrated cost volume with exact envelope integration. We will verify that with two classes and constant stakes it reproduces the model ordering given by VOROS on the Wisconsin and Dal Pozzolo examples reported in VOROS. We will also characterize the regime where $\pi$ is wide and stakes are constant. In that regime we hypothesize that the metric's model rankings agree with multi-class AUC, which would recover Wang et al.'s finding as a special case. The metric would then interpolate between ranking-style hedging and point-cost evaluation.
The second component is the loss. We will derive the gradient through envelope switch points and implement it as a drop-in training objective for linear models, small multilayer networks, and gradient-boosted trees (boosting uses the per-example gradient directly). Two optimization issues will be studied explicitly. First, when $\pi$ is narrow, the loss is flat in directions that do not affect decisions. We will test mixing in a small cross-entropy term to restore strict properness. Second, for heavy-tailed stakes, we will compare raw $z_i$, log-scaled $z_i$, and per-example normalization by the cost range.
The third component is theory. We aim to bound the stake-integrated regret of a model by its excess loss under our objective; by construction this bound is an equality in expectation. More substantively, we aim to give a lower bound on the gap to plug-in cross-entropy in linear model classes, extending the orientation argument of Mao et al. to K actions with example-specific cost lines. If that bound turns out to require assumptions that do not hold in our datasets, we will report that rather than generalize from the synthetic case.
Baselines
Naive reference. Multi-class cross-entropy trained without costs, followed by the example-dependent Bayes decision rule at the test-time exchange rate. This is the recipe of Zadrozny and Elkan applied with exact per-example costs. It is the do-nothing point and, for flexible models, possibly the hardest to beat. It will be trained with the same architecture, the same early-stopping budget, and the same hyperparameter search size as our method. Its probabilities will be temperature- or Platt-calibrated on a validation split, so any gain cannot be attributed to calibration alone.
Stake-weighted cross-entropy. Each example's cross-entropy is weighted by its stake (or a normalized version), the pointwise form of the cost-proportionate reductions surveyed by Petrides and Verbeke. This is the ablation that isolates our key ingredient. It uses exactly the same stake information as our loss but spreads accuracy over the whole probability range rather than over the decision band implied by $\pi$. Beating it is the result that shows the integral over exchange rates matters, not just knowing the stakes.
Example-dependent Bregman divergence (EDBD). The method of Hepburn et al., run at the midpoint of the $\theta$ range with its smoothness parameter tuned on the same budget. It is the strongest existing method for multi-class example-dependent costs. The reported numbers to match are total cost 556.19 on the Million Song Dataset and 2.06 on German Credit. We will rerun EDBD under our splits instead of comparing to these numbers directly. On algorithm selection, the reference is the pairwise cost-sensitive random forest of Mac Aodha and Brostow, with reported descriptor-matching precision 0.5878 and a 10% end-point-error reduction on optical flow. We will use our loss inside gradient-boosted trees for the comparison.
Multi-class AUC optimization with calibration. Following Wang et al., we optimize multi-class AUC and then apply Platt scaling and the per-example Bayes rule. This represents the ranking side of the intersection.
Across all methods, beating a baseline means a lower mean stake-integrated cost volume over five seeds, with a paired bootstrap interval excluding zero. We also require no loss in held-out cost when the true exchange rate is drawn from outside the training range.
Why not just…?
Why not just train a calibrated classifier and apply the example-dependent Bayes rule? This is the real threat. With unlimited capacity and data, a calibrated model plus the Bayes rule is optimal for every $\theta$ and every stake, and our loss has nothing to add. The argument for our approach rests on restricted capacity and finite data. Following Mao et al., the best restricted model for decisions need not be the best probability estimator. Hepburn et al.'s 2.06 versus 6.85 on German Credit suggests the gap can be large in practice, though their cross-entropy baseline was not paired with the Bayes rule in the same way. We will settle this with a capacity sweep from linear models to large boosted ensembles. If the gap closes at moderate capacity on real data, we will say plainly that the contribution is the metric plus a method for small or constrained models.
Why not just weight cross-entropy by each example's stake? Weighting tells the model which examples matter but not which probability errors matter. A high-stake transaction whose fraud probability is 0.9 versus 0.95 rarely changes the action, yet weighted cross-entropy still pays heavily for that error. The ablation baseline above tests this directly. We expect the difference to show up most where stakes are heavy-tailed. Scott predicts that weighting by raw stakes inflates variance in exactly that regime.
Why not just optimize multi-class AUC and calibrate, as Wang et al. recommend? Monotone calibration preserves the model's ordering of examples. Once stakes differ, the right decision for a high-stake example and a low-stake example with the same probability differs, and a ranking metric that ignores stakes cannot reward getting that right. VOROS already shows AUROC choosing the wrong binary model under skewed costs. Our replication of Wang et al.'s correlation analysis with per-example costs will show whether the −0.80 correlation degrades. If it does not, multi-class AUC remains a fine proxy and our metric is unnecessary for model selection.
Why not just use EDBD at a point estimate of the exchange rate? If the deployment rate is known, EDBD targets the right quantity. The question is robustness when the rate is misjudged, and optimization stability, since its sharpened form is non-convex. Our training-range versus shifted-range experiment measures the first. Training-curve variance across seeds measures the second.
Proposed Experiments
The datasets fall into three tiers.
Genuinely multi-class with example-dependent costs. The 13-genre Million Song task with popularity as the stake, as in Hepburn et al.. The descriptor-matching and optical-flow algorithm-selection tasks of Mac Aodha and Brostow, where each example's per-candidate performance scores define its cost row directly.
Binary sanity checks with stakes. German Credit with its instance financial costs, and KDD Cup 1998 donations, where the stake is the donation and the fixed cost is postage. No reported result was found on Lacuna for any method on KDD Cup 1998.
Semi-synthetic. The 26 UCI multi-class datasets of Wang et al. and the three-class Cardiotocography data, with stakes drawn from light- and heavy-tailed distributions. Some stakes will be independent of the features and some correlated with them, so we know when stakes carry information the model could exploit. On Cardiotocography the best reported ranking quality is VUS 0.8959 for aggregated RankBoost Clémençon et al.; we will report VUS alongside cost to show where the two disagree.
Three checks decide the proposal.
Capacity sweep against calibrated plug-in. If our loss shows no significant advantage over calibrated cross-entropy plus the Bayes rule at any capacity on the real stake datasets, the training contribution fails.
Ablation against stake-weighted cross-entropy. It must show a gain that grows with stake tail weight; otherwise the exchange-rate integral is decoration.
Rate-shift test. Models trained with one range for $\pi$ are evaluated when the true exchange rate lies inside, at the edge of, and outside that range. This should show our loss degrading more gracefully than point-cost EDBD.
Alongside these checks, the replication of Wang et al.'s correlation study under per-example costs will tell us whether the new metric is needed at all. If standard multi-class AUC still tracks cost well, the metric adds little and the case for this work rests on the training results alone.
References
- The VOROS: Lifting ROC Curves to 3D to Summarize Unbalanced Classifier Performance
- Partial VOROS: A Cost-aware Performance Metric for Binary Classifiers with Precision and Capacity Constraints
- Weighted ROC Curve in Cost Space: Extending AUC to Cost-Sensitive Learning
- An Empirical Study of MAUC in Multi-class Problems with Uncertain Cost Matrices
- Proper Losses for Learning with Example-Dependent Costs
- Surrogate losses and regret bounds for cost-sensitive classification with example-dependent costs
- Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
- Ranking data with ordinal labels: optimality and pairwise aggregation
- Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
- Bipartite Ranking through Minimization of Univariate Loss
- Surrogate Regret Bounds for the Area Under the ROC Curve via Strongly Proper Losses
- Learning and making decisions when costs and probabilities are both unknown
- Cost-sensitive ensemble learning: a unifying framework
- Revisiting Example Dependent Cost-Sensitive Learning with Decision Trees