<p>I'm not sure if this is what you're looking for, but people have studied consistency of <em>surrogate risk minimization</em>. There, we define a surrogate loss function <span class="math-container">$L$</span> and a link <span class="math-container">$\psi$</span>. We first minimize surrogate loss on our dataset, yielding some surrogate hypothesis <span class="math-container">$h$</span>. Then we define <span class="math-container">$f(x) = \psi(h(x))$</span>. This procedure is roughly consistent if, as data <span class="math-container">$\to \infty$</span>, we have <span class="math-container">$f \to f^*$</span>.</p>
<p>The question is, given e.g. <span class="math-container">$C$</span>, what are some nice, consistent surrogate losses? Example: for binary <span class="math-container">$0-1$</span> 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.</p>
<p>Tewari and Bartlett (2007) study multiclass classification, but I think not cost-sensitive, and relate consistency to <em>calibration</em>. A more recent work is Agarwal and Agarwal (2015), which has some more references.</p>
<p>[1] Tewari, Bartlett. <em>On the Consistency of Multiclass Classification Methods.</em> JMLR 2007. <a href="https://www.jmlr.org/papers/volume8/tewari07a/tewari07a.pdf" rel="nofollow noreferrer">https://www.jmlr.org/papers/volume8/tewari07a/tewari07a.pdf</a></p>
<p>[2] A. Agarwal, S. Agarwal. <em>On consistent surrogate risk minimization and property elicitation.</em> COLT 2015. <a href="http://proceedings.mlr.press/v40/Agarwal15.pdf" rel="nofollow noreferrer">http://proceedings.mlr.press/v40/Agarwal15.pdf</a></p>

CC BY-SA 4.0
2021-03-24T21:40:20.013Z
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?
Aryeh
CC BY-SA 4.0
2021-03-25T01:41:00.887Z
@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)$.
usul
CC BY-SA 4.0
2021-03-25T08:38:40.793Z
Great -- I'll accept it, and hopefully others will add further references that come up.
Aryeh
CC BY-SA 4.0
2021-03-24T16:02:36.187Z
2021-03-24T16:02:36.187Z
usul
<p>In cost-sensitive classification,
we have a confusion (or cost) matrix
<span class="math-container">$C$</span>, where <span class="math-container">$C(i,j)$</span> is the cost incurred
for predicting label <span class="math-container">$i$</span> when nature
specifies <span class="math-container">$j$</span>. The costs are non-negative,
but no other restriction (such as symmetry) need be imposed. In the classic setting
(PAC and its multiclass generalization),
<span class="math-container">$C(i,j)=1[i\neq j]$</span>.</p>
<p>The notion of Bayes-consistency carries
over naturally to the cost-sensitive setting. For any joint distribution
<span class="math-container">$P$</span>
over the instances
<span class="math-container">$\mathcal{X}$</span>
and labels
<span class="math-container">$\mathcal{Y}$</span>,
we define the risk of a predictor
<span class="math-container">$f:\mathcal{X}\to \mathcal{Y}$</span>
as
<span class="math-container">$$
R(f)=
\mathbb{E}_{(X,Y)\sim P}
C(f(X),Y).
$$</span>
Letting <span class="math-container">$f^*$</span> be a minimizer of
<span class="math-container">$R(\cdot)$</span> over all measurable <span class="math-container">$f$</span>,
we define the Bayes-optimal risk as
<span class="math-container">$R^*:=R(f^*)$</span>.</p>
<p>Question: What is known about Bayes-consistent classification in the cost-sensitive setting? For example,
when <span class="math-container">$\mathcal{X}$</span> is a metric space
and <span class="math-container">$C(i,j)=1[i\neq j]$</span>, various nearest-neighbor methods are known to be strongly Bayes-consistent. Is anything known about other cost matrices?</p>

<machine-learning><lg.learning><online-learning>
Bayes-consistent cost-sensitive classification
Aryeh
# Bayes-consistent cost-sensitive classification

(Asked by: username_0 on 2021-03-22)

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?

**Tags:** machine-learning, lg.learning, online-learning

---

## 1 answers

### Answer by username_1 on 2021-03-24. Score: 2 | Accepted answer

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>

> **Comments:**
> **username_0**: 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?  
> **username_1**: @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)$.  
> **username_0**: Great -- I'll accept it, and hopefully others will add further references that come up.  

---

