Many real systems do not classify items so much as queue them. A fraud team reviews the top few hundred flagged transactions per day. A retention team calls a limited number of at-risk customers. A clinic escalates a limited number of patients across severity tiers. In each case the items differ by category, and they also differ individually in how much is at stake: a \$10,000 fraud versus a \$5 one, a high-value customer versus a marginal one. Two research communities have each solved half of this problem. Example-dependent cost-sensitive learning trains models that respect per-item stakes, but only through pointwise losses and per-item thresholds. Multi-class AUC optimization trains models to order items well across many classes, but it treats every misordered pair as equally bad. Neither one trains a model to produce a good queue when stakes vary item by item and are not known when the model makes its prediction.
This note proposes one specific bridge. Suppose the review budget is unknown and we average over all budgets the value captured at the top of the queue. Then the shortfall from the ideal queue equals a sum over misordered pairs of items, each pair weighted by the difference in their realized stakes. That pairwise weight cannot be split into a weight on each item separately. This is exactly what separates the objective from sample reweighting, and it is why existing multi-class AUC losses, reweighted or not, optimize the wrong quantity. We call the resulting metric and loss Stake-Differential AUC. We give a near-linear-time algorithm for it, ask when its pairwise surrogate is consistent, and run a deliberately adversarial empirical study against the simple pointwise alternatives a reviewer would reach for first.
Core Claim
Let each training item $i$ have features $x_i$, a tier or class $y_i \in \{1,\dots,K\}$, and a realized stake $a_i \ge 0$, so its realized value is $v_i = u_{y_i} a_i$, where $u_k$ is a per-tier multiplier (for example, zero for "legitimate" and positive, increasing weights for the fraud or severity tiers). A scoring function $s$ induces a queue. Averaged uniformly over every capacity $k = 1,\dots,N$, the value captured in the top $k$ falls short of the ideal queue by exactly
$$\mathrm{Regret}(s) = \frac{1}{N}\sum_{i,j:\, v_i > v_j} (v_i - v_j)\,\mathbf{1}[s(x_j) > s(x_i)].$$
This follows from writing the total captured value as $\sum_i v_i(N - r_i + 1)$, where $r_i$ is item $i$'s rank, and undoing inversions one adjacent swap at a time. Three consequences drive the proposal.
First, the weight $|v_i - v_j|$ is non-separable. This matters because products or sums of per-item weights, $w_i w_j$ or $w_i + w_j$, factor exactly through the algebra that Learning with Multiclass AUC: Theory and Algorithms uses to obtain linear-time training. Such weights are therefore mathematically identical to reweighting samples before running that method. A "cost-weighted multi-class AUC" built on separable weights is not a new objective, and we want to say so explicitly.
Second, the regret also counts pairs within a tier: two frauds of different size, or two late-stage patients of different urgency. The uniform one-vs-one M metric of Yang et al. ignores these pairs entirely. The M metric is recovered from our objective only when stakes are constant within each tier and cross-tier pairs are re-normalized per class pair. So the existing metric is a special case, and we can measure how much value it leaves on the table.
Third, the queue that minimizes regret sorts items by the expected value $\mathbb{E}[v \mid x]$. This is what makes the hard case well-defined. When the stake $a_i$ is observed at prediction time, the classical answer of Zadrozny & Elkan (estimate the class probability and multiply by the stake) is already nearly optimal. Our method should not be expected to beat it there. The proposal targets the regime where the stake is realized only later, such as trading profit, customer lifetime value, or song popularity. There a model must learn to rank by a quantity it never directly observes at prediction time.
Research Program
The algorithmic piece is a pairwise surrogate that keeps the speed of unweighted multi-class AUC training. With the exponential surrogate, the training loss is
$$L(s) = \sum_{i,j:\, v_i > v_j} (v_i - v_j)\, e^{-(s_i - s_j)} = \sum_i e^{-s_i}\Big( v_i \sum_{j:\, v_j < v_i} e^{s_j} - \sum_{j:\, v_j < v_i} v_j e^{s_j} \Big),$$
where $s_i = s(x_i)$. After sorting a mini-batch by realized value, both inner sums are running prefix sums, so the loss and its gradient cost $O(N \log N)$ rather than $O(N^2)$. We will derive the matching prefix-sum forms for the squared surrogate, and a sorted dynamic program for the hinge surrogate, mirroring the three accelerations in Yang et al. The approach to ties follows Liu et al., whose decomposition gives unbiased estimates of three-class ROC volume in $O(N \log N)$ under ties. We will use it to evaluate the metric exactly when many items share a stake, such as many \$0 legitimate transactions.
The theoretical piece is a consistency question that the file shows is open. Yang et al. prove that pairwise surrogates are consistent for the uniform M metric. Hepburn et al. prove properness for pointwise example-dependent Bregman losses. Neither result covers pairwise weights that depend on realized, noisy stakes. For a single pair, the exponential surrogate's minimizer sets $s_i - s_j$ to half the log ratio of $\mathbb{E}[(v_i - v_j)_+]$ to $\mathbb{E}[(v_j - v_i)_+]$. That ratio has the right sign, but one function $s$ need not satisfy all pairs at once, so the population minimizer may fail to sort by $\mathbb{E}[v \mid x]$. We will characterize the conditions under which it does, for example when the stake distribution given $x$ is a location or scale family. Where consistency fails, we will test a fallback: parameterize the score as a monotone function of a predicted expected value and train it with the pairwise loss.
The heavy-tail question gets explicit treatment. Scott (2011) shows that surrogate regret bounds for example-dependent costs weaken when costs are heavy-tailed. Pairwise differences inherit the tail, so we will study capping or quantile-transforming the stakes inside the weight. We will report how much regret on the uncapped metric each choice gives up.
Baselines
The naive reference point is a softmax cross-entropy classifier whose queue is ordered by the predicted probability-weighted tier multiplier $\sum_k u_k \hat P(y=k \mid x)$, ignoring stakes entirely. This shows how much any stake modeling buys. The model is trained with the same backbone, data split, and tuning budget as every other method.
The strongest pointwise competitor is plug-in expected value. It combines cross-entropy class probabilities with a separately trained stake regressor and multiplies the two. In the observed-stake setting it multiplies by the observed stake instead, which is the Bayes Minimum Risk rule. Correa Bahnsen et al. (2014) report that their integrated cost-sensitive logistic regression beats this kind of post-processing by nearly 3 points of savings on the Kaggle Credit data (54.41% savings). That result concerns binary decisions, not queues, so we treat plug-in as the method to beat rather than as already beaten.
The second strong competitor is direct value regression, which fits $\mathbb{E}[v \mid x]$ with squared or Huber loss. It is consistent for our metric by the third consequence above, so it is the most dangerous baseline. It receives a tuning budget equal to ours over loss type, Huber scale, and target transform.
The strongest existing ranking method is the accelerated exponential multi-class AUC loss of Yang et al., which reports 84.87% M metric on iNaturalist2017 against 66.84% for cross-entropy. We run it both unweighted and with per-sample stake weights. The weighted version is exactly the separable-weight special case.
The strongest existing cost-sensitive pointwise method is the example-dependent Bregman loss of Hepburn et al., which reports total test cost 2.06 against 6.85 for cross-entropy on German Credit and 556.19 on the Million Song Dataset. On binary Jane Street we also run SACCL from Weighted ROC Curve in Cost Space. It reports profit 6526 against 4955 for binary cross-entropy, and this is the reported number for the strongest baseline on that benchmark. We replicate its profit protocol before adding our own metric.
Two ablations isolate the key ingredient. The first swaps our differential weight $|v_i - v_j|$ for the separable weights $v_i + v_j$ and $v_i v_j$ inside an otherwise identical pipeline. The second drops within-tier pairs. Beating a baseline means a lower regret normalized against the ideal queue on held-out data, with the gap exceeding the across-seed spread over five seeds and holding at the operationally relevant budgets (top 1% and 5%) as well as on the budget average.
Why not just…?
Why not just train a cross-entropy classifier and apply the Bayes Minimum Risk rule with the item's cost? When the stake is observed at prediction time, this is essentially right, and we expect it to tie our method. The study includes that regime precisely to confirm this rather than hide it. When the stake is realized later, the rule needs a stake prediction, and the product of two separately fit models is not trained against the queue. Yang et al. also document that cross-entropy probabilities on rare classes are poorly ordered: the 66.84% versus 84.87% M metric gap on iNaturalist2017. The plug-in baseline in our experiments tests directly whether that miscalibration costs value once stakes enter.
Why not just reweight samples by their stakes and run existing multi-class AUC optimization? Our derivation shows this optimizes the separable-weight objective, not the capacity-averaged value. It also ignores within-tier pairs. Petrides & Verbeke (2022) note that it is often unclear how record-dependent costs can enter ensemble updates through sample weights alone, which is consistent with this view. The weight-swap ablation settles the question empirically. If product weights match differential weights on held-out regret, the non-separability argument has no practical force and we will report that.
Why not just apply Frank & Hall decomposition with cost-sensitive binary classifiers? Fürnkranz et al. (2009) show the decomposition ranks well across 25 ordinal datasets. However, pooling tiers into "above $k$" meta-classes leaves the per-item cost of each binary subproblem ill-defined, and stakes within a tier play no role in the summed score. We include a version that weights each binary subproblem by item stake and expect it to lose mainly on within-tier ordering.
Why not just regress expected value directly? This is the real threat, since it is pointwise, simple, and consistent for the same target. Our bet is that under heavy-tailed, partly unpredictable stakes, a squared-loss regressor spends its capacity on fitting the size of extreme outliers, while a pairwise loss needs only their order relative to the rest of the queue. If tuned Huber regression matches our method across the heavy-tail sweep, the contribution narrows to the metric, its decomposition, and the fast exact evaluator, and the note will say so.
Proposed Experiments
The first experiment is a controlled sweep that decides the main question. We take CIFAR-100-Imb and iNaturalist2017, the benchmarks of Yang et al., group classes into $K = 4$ severity tiers, and attach synthetic stakes that are only partly predictable from the image: a log-normal stake whose mean depends on a held-out attribute and whose tail index we vary. Because the true $\mathbb{E}[v \mid x]$ is known by construction, we can measure regret against the exact optimum. The decisive output is a curve of regret gap versus tail heaviness for our method, value regression, plug-in, and reweighted Yang. The hypothesis is falsified if the gap does not grow with the tail.
The second experiment uses real stakes that are unknown at prediction time. On Jane Street Market Prediction, realized trade return is the stake. We first reproduce the profit protocol of Shao et al., then define tiers by return sign and magnitude and report capacity-averaged value. On the Million Song Dataset's 13 genres with popularity as the stake, following Hepburn et al., the decisive check is whether we lower total cost below the reported 556.19 while also improving within-genre ordering. On TV Cable churn, customer lifetime value plays the stake, following Correa Bahnsen et al. (2015b), whose cost-sensitive tree reports €153,237 savings against €24,629 for a standard random forest.
The third experiment uses stakes that are observed at prediction time, as a control. On German Credit (loan amount) and the 0.17%-fraud credit card data with transaction amounts, we expect plug-in to tie or win. An unexpected win for our method there would point to probability miscalibration rather than ranking structure, and we will diagnose which.
Throughout, we report the uniform M metric alongside our regret. This makes visible any case where higher M metric coincides with worse value, which is the clearest single demonstration that uniform pairwise AUC and stake-aware queueing pull in different directions. We also time the prefix-sum loss against the naive pairwise loss on iNaturalist2017 to confirm the near-linear scaling holds in practice.
References
- Learning With Multiclass AUC: Theory and Algorithms
- Learning and making decisions when costs and probabilities are both unknown
- Fast and Unbiased Estimation of Volume Under Ordered Three-Class ROC Surface (VUS) With Continuous or Discrete Measurements
- Proper Losses for Learning with Example-Dependent Costs
- Surrogate losses and regret bounds for cost-sensitive classification with example-dependent costs
- Example-Dependent Cost-Sensitive Logistic Regression for Credit Scoring
- Weighted ROC Curve in Cost Space: Extending AUC to Cost-Sensitive Learning
- Cost-sensitive ensemble learning: a unifying framework
- Binary Decomposition Methods for Multipartite Ranking
- A novel cost-sensitive framework for customer churn predictive modeling