In cost-sensitive classification, we have a confusion (or cost) matrix $C$, where $C(i,j)$ is the cost incurred for predicting label $i$ when nature specifies $j$. The costs are non-negative, but no other restriction (such as symmetry) need be imposed. In the classic setting (PAC and its multiclass generalization), $C(i,j)=1[i\neq j]$.

The notion of Bayes-consistency carries over naturally to the cost-sensitive setting. For any joint distribution $P$ over the instances $\mathcal{X}$ and labels $\mathcal{Y}$, we define the risk of a predictor $f:\mathcal{X}\to \mathcal{Y}$ as $$ R(f)= \mathbb{E}_{(X,Y)\sim P} C(f(X),Y). $$ Letting $f^*$ be a minimizer of $R(\cdot)$ over all measurable $f$, we define the Bayes-optimal risk as $R^*:=R(f^*)$.

Question: What is known about Bayes-consistent classification in the cost-sensitive setting? For example, when $\mathcal{X}$ is a metric space and $C(i,j)=1[i\neq j]$, various nearest-neighbor methods are known to be strongly Bayes-consistent. Is anything known about other cost matrices?


1 Answer 1


I'm not sure if this is what you're looking for, but people have studied consistency of surrogate risk minimization. There, we define a surrogate loss function $L$ and a link $\psi$. We first minimize surrogate loss on our dataset, yielding some surrogate hypothesis $h$. Then we define $f(x) = \psi(h(x))$. This procedure is roughly consistent if, as data $\to \infty$, we have $f \to f^*$.

The question is, given e.g. $C$, what are some nice, consistent surrogate losses? Example: for binary $0-1$ loss, one can use hinge loss or logistic loss as a surrogate, and one can show this is consistent as long as the hypothesis class is rich enough.

Tewari and Bartlett (2007) study multiclass classification, but I think not cost-sensitive, and relate consistency to calibration. A more recent work is Agarwal and Agarwal (2015), which has some more references.

[1] Tewari, Bartlett. On the Consistency of Multiclass Classification Methods. JMLR 2007. https://www.jmlr.org/papers/volume8/tewari07a/tewari07a.pdf

[2] A. Agarwal, S. Agarwal. On consistent surrogate risk minimization and property elicitation. COLT 2015. http://proceedings.mlr.press/v40/Agarwal15.pdf

  • $\begingroup$ Thanks, @usul! I should read these carefully, but they all deal with the case where the labels are "atomic" -- i.e., have no cost/metric structure? $\endgroup$
    – Aryeh
    Commented Mar 24, 2021 at 21:40
  • $\begingroup$ @Aryeh I think that's correct for Tewari and Bartlett, but Agarwal and Agarwal consider a general (finite-dimensional) "loss matrix" where predicting $t$ when the true label is $y$ gives loss $L(y,t)$. $\endgroup$
    – usul
    Commented Mar 25, 2021 at 1:41
  • $\begingroup$ Great -- I'll accept it, and hopefully others will add further references that come up. $\endgroup$
    – Aryeh
    Commented Mar 25, 2021 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.