# Optimizing ROC Curves with a Sort-Based Surrogate Loss Function for Binary
Classification and Changepoint Detection

Jonathan Hillman and
Toby Dylan Hocking —<EMAIL_ADDRESS>
###### Abstract

Receiver Operating Characteristic (ROC) curves are plots of true positive rate
versus false positive rate which are useful for evaluating binary
classification models, but difficult to use for learning since the Area Under
the Curve (AUC) is non-convex. ROC curves can also be used in other problems
that have false positive and true positive rates such as changepoint
detection. We show that in this more general context, the ROC curve can have
loops, points with highly sub-optimal error rates, and AUC greater than one.
This observation motivates a new optimization objective: rather than
maximizing the AUC, we would like a monotonic ROC curve with AUC=1 that avoids
points with large values for Min(FP,FN). We propose a convex relaxation of
this objective that results in a new surrogate loss function called the AUM,
short for Area Under Min(FP, FN). Whereas previous loss functions are based on
summing over all labeled examples or pairs, the AUM requires a sort and a sum
over the sequence of points on the ROC curve. We show that AUM directional
derivatives can be efficiently computed and used in a gradient descent
learning algorithm. In our empirical study of supervised binary classification
and changepoint detection problems, we show that our new AUM minimization
learning algorithm results in improved AUC and comparable speed relative to
previous baselines.

##  1 Introduction

In supervised machine learning problems such as binary classification and
changepoint detection, the goal is to learn a function for accurately
predicting presence or absence of a class label. In binary classification
there is a prediction for each example; in changepoint detection there is a
prediction (change or not) in between each data point in a sequence. There are
numerous ways to analyze prediction performance, but the simplest way is to
calculate accuracy, which is the number or proportion of correctly classified
labels. However using accuracy as the evaluation metric can be problematic for
data sets with imbalanced labels or for which the desired weighting of the
labels is unknown (Cortes and Mohri, 2004; Menon et al., 2013).

A popular approach for comparing models in this context is by analyzing their
Receiver Operating Characteristic (ROC) curves, which are plots of True
Positive Rate (TPR) versus False Positive Rate (FPR) that have long been used
in the signal processing literature (Egan and Egan, 1975). For data with $n$
labeled examples, most algorithms compute a predicted value
$\hat{y}_{i}\in\mathbb{R}$ for each labeled example $i\in\\{1,\dots,n\\}$. In
binary classification the predicted value $\hat{y}_{i}$ is then compared to
the threshold of zero to classify the example as either positive or negative.
True positives are examples $i$ with positive labels and positive predictions,
whereas false positives are examples $i$ with negative labels and positive
predictions. A vector of predicted values
$\mathbf{\hat{y}}=[\hat{y}_{1}\cdots\hat{y}_{n}]^{\intercal}\in\mathbb{R}^{n}$,
one element for each labeled example $i$, can be mapped to a single (FPR,TPR)
point in ROC space. The different points on the ROC curve are obtained by
adding a real-valued constant $c\in\mathbb{R}$ to each prediction in that
vector, $\mathbf{\hat{y}}+c$. Large constants $c$ result in FPR=TPR=1 and
small constants result in FPR=TPR=0. Therefore the Area Under the Curve (AUC)
is an evaluation metric which accounts for all possible constants or
possibilities for thresholding the prediction vector. In binary
classification, a perfect model has an AUC of 1, a constant model has an AUC
of 0.5, and the minimum AUC is 0.

Figure 1: Example labeled changepoint detection data for which the FN function
is non-monotonic. Left: a data sequence (black dots) with one label (grey
rectangle) in which there should be exactly one predicted changepoint (false
negative for no changes when segments=3, false positive for two changes when
segments=15). Right: selected number of segments (top) and number of label
errors (bottom) as a function of predicted values, with vertical violet lines
indicating the models shown on the left, and vertical black lines for
breakpoints in the error functions ($v$ for predicted value,
$\Delta\text{FP},\Delta\text{FN}$ for changes in error functions at that
value).

When AUC is used as the evaluation metric in machine learning, the best
algorithm is typically defined as the one that maximizes test AUC. In such
experiments, we would also like to use the AUC as the objective function for
training the model (under the assumption that if the train and test sets are
similar, maximizing train AUC should result in maximizing test AUC). However,
since the AUC is a piecewise constant function of the predicted values, its
gradient is zero almost everywhere, and it is therefore impossible to directly
optimize using gradient descent algorithms.

In addition to studying binary classification, we also study supervised
changepoint detection, in which we can also compute FPR and TPR. For binary
classification, we can compute a prediction vector which maximizes AUC in the
same way as maximizing accuracy — predict a positive value for each positive
label, and a negative value for each negative label. For changepoint
detection, it is also trivial to compute a prediction vector that maximizes
accuracy, but it can be non-trivial to compute a prediction vector that
maximizes AUC. The previous observations motivate this paper, which explores a
new loss function and corresponding learning algorithm which we empirically
show results in AUC maximization.

###  1.1 Contributions and organization

Our main contribution is the AUM, which is a new surrogate loss function
defined as the Area Under the Minimum of false positive and false negative
counts as a function of the prediction threshold. Whereas previously proposed
loss functions for binary classification can be interpreted as convex
surrogates of the zero-one loss (summed over examples) or Mann-Whitney
statistic (summed over pairs of examples), our proposed AUM loss is an L1
relaxation of the total Min(FP,FN) (summed over points on the ROC curve, or
distinct intervals of prediction thresholds).

In Section 2 we give precise definitions of the AUC and our new AUM loss
function. In Section 3 we give an efficient algorithm for computing
directional derivatives of the AUM with respect to predicted values, which we
propose using in gradient descent learning algorithms. In Section 4 we provide
an empirical study of supervised binary classification and changepoint
detection problems, showing that minimizing the AUM corresponds to maximizing
the AUC (with respect to train and test sets). Section 5 concludes with a
discussion of the significance and novelty of our findings.

###  1.2 Related work

#### Evaluating learned binary classification models.

ROC curve analysis is a classical evaluation technique with origins in the
signal processing literature (Egan and Egan, 1975). Provost and Fawcett (1997)
introduced a ROC convex hull method for evaluation. Ling et al. (2003) provide
a proof of AUC consistency, whereas Hand (2009) showed that it is incoherent
with respect to classification costs, and proposed the “H measure” as an
alternative. Martínez-Camblor et al. (2017) proposed a generalization to
predicted values which have a non-monotone relationship with the desired class
label.

#### Margin losses for binary classification.

Margin losses can be interpreted as weighted convex surrogates of the zero-one
loss, summed over all examples. Ferri et al. (2002); Cortes and Mohri (2004)
proposed expressions for the expected value and the variance of the AUC for a
fixed error rate, in an attempt to maximize the AUC with different nonlinear
algorithms. Wang et al. (2015) incorporated unlabeled data to make an
unsupervised AUC maximization algorithm. Other algorithms have been proposed
to obtain approximations of the global AUC value (Rakotomamonjy, 2004;
Herschtal and Raskutti, 2004; Herschtal et al., 2006; Calders and Jaroszewicz,
2007). Han and Zhao (2010) proposed an active learning algorithm for computing
a linear model that maximizes the AUC. Zhao et al. (2011) implemented an
online learning algorithm that maximizes the AUC. Menon et al. (2013) analyzed
statistical consistency under class imbalance, using a mean of true positive
and true negative rates. Scott (2012) studied calibration for margin-based
losses for binary classification.

#### Pairwise losses for binary classification.

Bamber (1975) is credited as the first to prove the equivalence of the ROC-AUC
and the Mann-Whitney test statistic (Mann and Whitney, 1947). This equivalence
has led many authors to propose algorithms based on loss functions that are
convex surrogates of the Mann-Whitney statistic. Yan et al. (2003) proposed a
global approximation of AUC which was then used in several other algorithms.
For example, Castro and Braga (2008) used that approxmation to propose the
AUCtron algorithm which learns a linear model. Joachims (2005) proposed a
quadratic time support vector machine algorithm for AUC maximization based on
a pairwise loss function, and Freund et al. (2003) proposed a similar approach
based on boosting. Narasimhan and Agarwal (2013) extended this approach to the
partial AUC, which is defined as the area under the curve between two false
positive rates (not necessarily 0 and 1). Kotlowski et al. (2011) analyze how
much risk and regret is increased for balanced margin-based losses, compared
with pairwise losses. Rudin et al. (2005) showed that in some cases margin-
based losses yield the same solution as a pairwise loss. For stochastic
optimization of the AUC, Ying et al. (2016) proposed solving a saddle point
problem involving a pairwise square loss, and Yuan et al. (2020) proposed to
extend this approach to the squared hinge loss.

#### Changepoint detection.

There are many algorithms for unsupervised changepoint detection
(Aminikhanghahi and Cook, 2017; van den Burg and Williams, 2020). In
supervised changepoint detection, learning is often limited to grid search
(Hocking et al., 2013, 2016; Liehrmann et al., 2021). More sophisticated
learning algorithms use linear models and non-linear decision trees that
minimize convex surrogates of the label error (Rigaill et al., 2013; Hocking
et al., 2014, 2015; Drouin et al., 2017; Hocking and Bourque, 2020). ROC
curves and AUC are used to evaluate prediction accuracy of learned penalty
functions (Maidstone et al., 2016; Hocking et al., 2020).

Figure 2: Synthetic example showing how non-monotonic total FP/FN functions
(left) can result in a looping ROC curve (right). The q values are indices in
the sequence of points on the ROC curve (and corresponding intervals of the
FP/FN functions). Left: the AUM (grey area) is defined as the area under the
minimum of total FP and FN functions,
$M_{\mathbf{\hat{y}}}(t)=\min\\{\text{FPT}_{\mathbf{\hat{y}}}(t),\text{FNT}_{\mathbf{\hat{y}}}(t)\\}$.
For each interval $q\in\\{1,\dots,7\\}$ of constant total error, the
$\tau(\mathbf{\hat{y}})_{q}$ is the largest threshold in that interval. Right:
$\text{AUC}\geq 1$ due to the loop which results in double counting the dark
grey area (but single counting the red area which is positive counted twice
and negative counted once).

##  2 Models and Definitions

We begin by reviewing supervised binary classification and changepoint
detection, then give definitions for AUC and the new AUM loss function.

###  2.1 Review of supervised binary classification

In supervised binary classification we are given a set of $n$ labeled training
examples, $\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$ where
$\mathbf{x}_{i}\in\mathbb{R}^{p}$ is an input feature vector for one example
and $y_{i}\in\\{-1,1\\}$ is a binary output/label. The goal of binary
classification is to learn a function $f:\mathbb{R}^{p}\rightarrow\mathbb{R}$
which is used to compute real-valued predictions
$\hat{y}_{i}=f(\mathbf{x}_{i})$ with the same sign as the corresponding label
$y_{i}$. Margin-based learning algorithms such as logistic regression and
support vector machines involve minimizing a convex surrogate loss function
$\ell:\mathbb{R}\rightarrow\mathbb{R}$, summed over all training examples:

$\mathcal{L}(f)=\sum_{i=1}^{n}\ell[y_{i}f(\mathbf{x}_{i})].$ (1)

Large margin values $y_{i}f(\mathbf{x}_{i})>0$ yield correct predictions,
whereas small values $y_{i}f(\mathbf{x}_{i})<0$ yield incorrect predictions.
Pairwise loss functions involve minimizing a convex loss summed over all pairs
of positive and negative examples,

$\mathcal{L}(f)=\sum_{i:y_{i}=-1}\
\sum_{j:y_{j}=1}\ell[f(\mathbf{x}_{j})-f(\mathbf{x}_{i})].$ (2)

Large pairwise difference values $f(\mathbf{x}_{j})-f(\mathbf{x}_{i})>0$ yield
correctly ranked pairs, whereas small pairwise difference values
$f(\mathbf{x}_{j})-f(\mathbf{x}_{i})<0$ yield incorrectly ranked pairs.
Typical choices for the convex surrogate loss function $\ell(z)$ include
logistic $\log[1+\exp(-z)]$, linear hinge $(1-z)_{+}$, and squared hinge
$(1-z)^{2}_{+}$, where $(\cdot)_{+}$ is the positive part function. After a
function $f$ has been learned using the training data, it can be evaluated by
computing non-convex evaluation metrics such as the zero-one loss or the AUC
with respect to a held-out test set.

###  2.2 Review of supervised changepoint detection

Here we give a brief overview of supervised changepoint detection; for details
see (Rigaill et al., 2013). We assume for each labeled training example
$i\in\\{1,\dots,n\\}$ there is a corresponding data sequence vector
$\mathbf{z}_{i}$ and label set $L_{i}$. For example in Figure 1 we show a data
sequence $\mathbf{z}_{i}$ with a label set $L_{i}$ that contains one positive
label (grey region in which there should be exactly one predicted
changepoint). Dynamic programming algorithms can be used on the data sequence
$\mathbf{z}_{i}$ to compute a path of optimal changepoint models
$\mathbf{\hat{m}}^{k}_{i}$ for different model sizes $k\in\\{1,2,\dots\\}$
(Maidstone et al., 2016). For example in Figure 1 (left) we show four models
in the path (with $k=2,3,4,15$ segments). The label set $L_{i}$ can be used to
compute the number of false positive and false negative labels with respect to
any predicted set of changepoints (false positives for too many changepoints,
false negatives for not enough changepoints). Each example $i$ also has a
model selection function
$k^{*}_{i}:\mathbb{R}^{+}_{0}\rightarrow\\{1,2,\dots\\}$ which maps a non-
negative penalty value $\hat{\lambda}_{i}$ to a selected model size
$k^{*}_{i}(\hat{\lambda}_{i})$ (Figure 1, right bottom). We assume there is a
fixed feature map $\phi$ which can be used to compute a feature vector
$\mathbf{x}_{i}=\phi(\mathbf{z}_{i})\in\mathbb{R}^{p}$ for each labeled
example.

We want to learn a function $f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ which
inputs a feature vector and outputs a real-valued prediction that is used as a
negative log penalty value, $f(\mathbf{x}_{i})=-\log\hat{\lambda}_{i}$. The
goal is to predict model sizes $k^{*}_{i}(\hat{\lambda}_{i})$ that result in
minimal label errors. Since the label error function is non-convex like the
zero-one loss in binary classification (Figure 1, right top), previous
learning algorithms instead use the gradient with respect to a convex
surrogate such as a hinge loss (Rigaill et al., 2013; Drouin et al., 2017) or
a censored regression loss (Barnwal et al., 2020).

###  2.3 Definition of false positive and negative functions

In this paper, we assume the following general learning context in which
supervised binary classification and changepoint detection are specific
examples. For each labeled training example $i$, we have one or more labels
such that there are at most $\text{FNP}_{i}\in\mathbb{Z}_{+}=\\{0,1,\dots\\}$
false negatives possible and $\text{FPP}_{i}\in\mathbb{Z}_{+}$ false positives
possible. Given a real-valued prediction
$\hat{y}_{i}=f(\mathbf{x}_{i})\in\mathbb{R}$, we can use the labels to compute
the number of predicted false positives
$\text{FP}_{i}(\hat{y}_{i})\in\\{0,\dots,\text{FPP}_{i}\\}$ and false
negatives $\text{FN}_{i}(\hat{y}_{i})\in\\{0,\dots,\text{FNP}_{i}\\}$. The
$\text{FP}_{i},\text{FN}_{i}$ functions return the number of false positive
and false negative labels for a given predicted value $\hat{y}_{i}$.

#### Exact representation using breakpoints.

By convention we assume that the $\text{FP}_{i},\text{FN}_{i}$ functions are
piecewise constant and right continuous; that the $\text{FP}_{i}$ functions
start at zero, $\lim_{x\rightarrow-\infty}\text{FP}_{i}(x)=0$; and the
$\text{FN}_{i}$ functions end at zero,
$\lim_{x\rightarrow\infty}\text{FN}_{i}(x)=0$. These assumptions ensure that
(1) our proposed AUM loss function will always be finite, and (2) it can be
computed efficiently by representing the error functions exactly using a
finite set of breakpoints. For each breakpoint tuple
$(v,\Delta\text{FP},\Delta\text{FN})$, $v\in\mathbb{R}$ is a predicted value
threshold where there are changes $\Delta\text{FP},\Delta\text{FN}$
(discontinuity) in the error functions, $\text{FP}_{i}(v)-\lim_{x\rightarrow
v^{-}}\text{FP}_{i}(x)=\Delta\text{FP}$ and similar for FN. For example, in
Figure 1 the error functions can be exactly represented by a set of four such
breakpoints. These breakpoints will be used when computing our proposed loss
function and learning algorithm.

#### Case of binary classification.

In the case of binary classification, for all positive examples $i:y_{i}=1$ we
have $\text{FPP}_{i}=0$, $\text{FNP}_{i}=1$, $\text{FP}_{i}(\hat{y})=0$,
$\text{FN}_{i}(\hat{y})=I(\hat{y}<0)$, where $I$ is the indicator function
(outputs 1 if argument is true, 0 otherwise). For all negative examples
$i:y_{i}=-1$, $\text{FPP}_{i}=1$, $\text{FNP}_{i}=0$,
$\text{FP}_{i}(\hat{y})=I(\hat{y}\geq 0)$, $\text{FN}_{i}(\hat{y})=0$. Note
that $\text{FP}_{i}$ is either constant/zero (for positive examples) or non-
decreasing (for negative examples), and $\text{FN}_{i}$ is either
constant/zero (for negative examples) or non-increasing (for positive
examples). Since the prediction threshold is always zero in binary
classification, these functions can be exactly represented by the breakpoint
$(v=0,\Delta\text{FP}=0,\Delta\text{FN}=-1)$ for all positive examples, and
$(v=0,\Delta\text{FP}=1,\Delta\text{FN}=0)$ for all negative examples.

#### Case of changepoint detection.

In changepoint detection, we have more general $\text{FP}_{i}$ and
$\text{FN}_{i}$ functions that can be non-monotonic, with arbitrary thresholds
$v$ that can be computed in advance of learning $f$. For example, in Figure 1,
we show a data sequence with one positive label (in which there should be
exactly one predicted changepoint). Predicting no changepoint in this label
results in a false negative, and predicting two changepoints in this label
results in a false positive. Therefore, we have
$\text{FPP}_{i}=\text{FNP}_{i}=1$ for this particular example $i$; the false
positive function is non-decreasing, $\text{FP}_{i}(\hat{y}_{i})\approx
I(\hat{y}_{i}\geq 3.001)$, and the false negative function is not monotonic,
$\text{FN}_{i}(\hat{y}_{i})\approx
I[\hat{y}_{i}\in(\infty,-1.929)\cup(-1.388,-1.136)]$. When the false negative
function is non-monotonic, the true positive rate is also non-monotonic (the
ROC curve can move down as well as up when prediction constant is increased).
Given a pre-computed path of changepoint models with loss/size values, the
exact breakpoints $(v,\Delta\text{FP},\Delta\text{FN})$ in such error
functions can be efficiently computed using a linear time algorithm (Hocking
and Vargovich, 2020).

Figure 3: Real data example showing that it is possible to have AUC greater
than one. Left: error functions for two labeled examples in a real changepoint
detection data set. Right: AUC, AUM, and SM values as a function of the
difference in predicted values between the two labeled examples. When the
difference is around 5, we have AUC=2. The AUC and SM are piecewise constant
functions of the predicted values, whereas the AUM is a continuous piecewise
linear function. At differentiable points, AUM=0 implies AUC=1 (but the
converse is false).

###  2.4 Definition of ROC curve and AUC

In this section, we show how the previously defined functions can be used to
define the ROC curve and the AUC. Given a vector of predictions
$\mathbf{\hat{y}}\in\mathbb{R}^{n}$, and a constant $c\in\mathbb{R}$ added to
that vector, we define the False Positive Total (FPT) and False Negative Total
(FNT) functions as

$\displaystyle\text{FPT}_{\mathbf{\hat{y}}}(c)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\text{FP}_{i}(\hat{y}_{i}+c),$ (3)
$\displaystyle\text{FNT}_{\mathbf{\hat{y}}}(c)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\text{FN}_{i}(\hat{y}_{i}+c).$ (4)

The corresponding False Positive Rate (FPR) and True Positive Rate (TPR)
functions are

$\displaystyle\text{FPR}_{\mathbf{\hat{y}}}(c)$ $\displaystyle=$
$\displaystyle\frac{1}{\sum_{i=1}^{n}\text{FPP}_{i}}\text{FPT}_{\mathbf{\hat{y}}}(c),$
(5) $\displaystyle\text{TPR}_{\mathbf{\hat{y}}}(c)$ $\displaystyle=$
$\displaystyle
1-\frac{1}{\sum_{i=1}^{n}\text{FNP}_{i}}\text{FNT}_{\mathbf{\hat{y}}}(c).$ (6)

The ROC curve for a given prediction vector $\mathbf{\hat{y}}$ is the plot of
$\text{TPR}_{\mathbf{\hat{y}}}(c)$ versus $\text{FPR}_{\mathbf{\hat{y}}}(c)$
as the constant $c$ is varied from $-\infty$ to $\infty$. The AUC is the
integral,

$\text{AUC}(\mathbf{\hat{y}})=\int\text{TPR}_{\mathbf{\hat{y}}}(c)d\,\text{FPR}_{\mathbf{\hat{y}}}(c).$
(7)

Assuming the $\text{FPT}_{\mathbf{\hat{y}}}(c)$ and
$\text{FNT}_{\mathbf{\hat{y}}}(c)$ functions are piecewise constant (as in
binary classification and changepoint detection) then the ROC curve can be
described as a sequence of $Q$ points
$\\{(\text{fpr}(\mathbf{\hat{y}})_{q},\text{tpr}(\mathbf{\hat{y}})_{q})\\}_{q=1}^{Q}$
in ROC space (note that this sequence of points depends on the predicted
values $\mathbf{\hat{y}}$). The first point $q=1$ corresponds to prediction
threshold $t=-\infty$ which results in TPR=0 and FPR=0; the last point $q=Q$
is for $t=\infty$ which results in TPR=1 and FPR=1 (Figure 2). The AUC can be
computed using this sequence,

$\text{AUC}(\mathbf{\hat{y}})=\sum_{q=2}^{Q}(\text{fpr}(\mathbf{\hat{y}})_{q}-\text{fpr}(\mathbf{\hat{y}})_{q-1})(\text{tpr}(\mathbf{\hat{y}})_{q-1}+\text{tpr}(\mathbf{\hat{y}})_{q})/2.$
(8)

In binary classification we have
$\text{fpr}(\mathbf{\hat{y}})_{q-1}\leq\text{fpr}(\mathbf{\hat{y}})_{q}$ which
means while tracing the ROC curve there are no moves to the left, and all the
terms in the sum above are positive. In fact this is also true of changepoint
detection problems for which all the $\text{FP}_{i}$ functions are non-
decreasing. In these cases the ROC curve is monotonic, with
$\text{AUC}(\mathbf{\hat{y}})\in[0,1]$ for any predicted values
$\mathbf{\hat{y}}$.

###  2.5 Looping curves motivate optimizing ROC points instead of AUC

If some of the $\text{FP}_{i}$ functions are not monotonic, then it is
possible to have
$\text{fpr}(\mathbf{\hat{y}})_{q-1}>\text{fpr}(\mathbf{\hat{y}})_{q}$ which
results in negative terms in the AUC equation (8). Furthermore if some of the
$\text{FN}_{i}$ functions are not monotonic, then the ROC curve can contain
loops which double count some area in ROC space. For a simple synthetic
example, consider the FP/FN functions and corresponding ROC curves in Figure
2. In this example, the ROC curve has area $\approx 1.22$ because it contains
a loop which double-counts a large portion of ROC space. This looping implies
existence of ROC points $q$ which are highly sub-optimal in terms of TPR
and/or FPR (for example, $q\in\\{2,3,4,5\\}$ in Figure 2). By “sub-optimal” we
mean ROC points that occur more toward the bottom right of ROC space, where
both FP and FN are large, as is $\min\\{\text{FP},\text{FN}\\}$. Thus we
observe an association between looping ROC curves, large AUC, and existence of
some thresholds with highly sub-optimal error rates.

Although this seems like a rare phenomenon, we have seen this occur in real
data. For example, in Figure 1 it is clearly possible to have error functions
which are non-monotonic. Furthermore, in Figure 3 (left) we show error curves
for two labeled examples from another real changepoint detection data set. One
example has a positive label that results in a non-monotonic false negative
function, and the other example has a negative label that results in a non-
monotonic false positive function. When the predicted value for the negative
example is about 5 greater than the predicted value for the positive example,
we observe AUC=2 (Figure 3, right). This is the result of a loop in ROC space,
indicating that there is some prediction threshold that results in
(FPR=1,TPR=0) which corresponds to 100% error and 0% accuracy. Therefore,
maximizing the AUC may not be a desirable optimization objective, because it
can result in ROC curves with loops and points in the lower right, with large
$\min\\{\text{FP},\text{FN}\\}$ values. Instead, we propose as an optimization
objective to minimize the total $\min\\{\text{FP},\text{FN}\\}$ over all ROC
points. This objective means that ideal ROC points would be moved away from
the lower right, toward the upper left, with the best case being a monotonic
ROC curve with AUC=1. We formalize this idea in the next section, and provide
a new surrogate loss function for this objective.

###  2.6 Proposed surrogate loss function (AUM)

In this section we propose the AUM loss function, which is short for Area
Under Min(FP,FN). The intuition behind the AUM is that we want to minimize the
number of prediction thresholds that result in large error rates. To formally
define the AUM we must first define the minimum of total false positives and
false negatives,

$M_{\mathbf{\hat{y}}}(c)=\min\\{\text{FPT}_{\mathbf{\hat{y}}}(c),\text{FNT}_{\mathbf{\hat{y}}}(c)\\}.$
(9)

Then we define the AUM as

$\text{AUM}(\mathbf{\hat{y}})=\int_{-\infty}^{\infty}M_{\mathbf{\hat{y}}}(c)\,dc.$
(10)

In summary, we compute AUM by integrating the $M$ function over all possible
constants $c\in\mathbb{R}$. Geometrically, this corresponds to the area under
the minimum of total false positive and false negative functions (Figure 2,
left).

###  2.7 Interpretation as L1 relaxation of total Min(FP,FN) over ROC points

Computing the AUM is similar to the AUC, in that we must compute
error/accuracy rates for each possible prediction threshold. First let
$\\{(\text{fpt}(\mathbf{\hat{y}})_{q},\text{fnt}(\mathbf{\hat{y}})_{q},\tau(\mathbf{\hat{y}})_{q})\\}_{q=1}^{Q}$
be a sequence of $Q$ tuples, each of which corresponds to a point on the ROC
curve (Figure 2, right). The fpt/fnt are false positive/negative totals
whereas $\tau$ are values such there is a change/threshold at
$M_{\mathbf{\hat{y}}}(\tau)$. As shown in Figure 2 we assume these values are
increasing,
$-\infty=\tau(\mathbf{\hat{y}})_{0}<\cdots<\tau(\mathbf{\hat{y}})_{Q}=\infty$.
For each $q\in\\{1,\dots,Q\\}$ there is a corresponding interval of values $c$
between $\tau(\mathbf{\hat{y}})_{q-1}$ and $\tau(\mathbf{\hat{y}})_{q}$ such
that $\text{FPT}_{\mathbf{\hat{y}}}(c)=\text{fpt}(\mathbf{\hat{y}})_{q}+t$ and
$\text{FNT}_{\mathbf{\hat{y}}}(c)=\text{fnt}(\mathbf{\hat{y}})_{q}+t$ for all
$c\in(\tau(\mathbf{\hat{y}})_{q-1},\tau(\mathbf{\hat{y}})_{q})$ (Figure 2,
left). Then we define
$m(\mathbf{\hat{y}})_{q}=\min\\{\text{fpt}(\mathbf{\hat{y}})_{q},\,\text{fnt}(\mathbf{\hat{y}})_{q}\\}$
and so since $m(\mathbf{\hat{y}})_{1}=m(\mathbf{\hat{y}})_{Q}=0$ the area
under those intervals is zero, and the AUM can be computed by summing over all
of the other intervals,

$\text{AUM}(\mathbf{\hat{y}})=\sum_{q=2}^{Q-1}[\tau(\mathbf{\hat{y}})_{q}-\tau(\mathbf{\hat{y}})_{q-1}]m(\mathbf{\hat{y}})_{q}.$
(11)

For example, in Figure 2 there are $Q=7$ tuples (points on the ROC curve),
five of which result in a positive AUM value, resulting in a total AUM is 75.

The AUM can be interpreted as an L1 relaxation of the following non-convex Sum
of Min(FP,FN) function,

$\text{SM}(\mathbf{\hat{y}})=\sum_{q=2}^{Q-1}I[\tau(\mathbf{\hat{y}})_{q}\neq\tau(\mathbf{\hat{y}})_{q-1}]m(\mathbf{\hat{y}})_{q}=\sum_{q:\tau(\mathbf{\hat{y}})_{q}\neq\tau(\mathbf{\hat{y}})_{q-1}}m(\mathbf{\hat{y}})_{q}.$
(12)

The difference is that the L1 norm of
$\tau(\mathbf{\hat{y}})_{q}-\tau(\mathbf{\hat{y}})_{q-1}$ in (11) has been
changed to the L0 pseudo-norm in (12). The indicator function $I$ takes values
in zero and one, which means the SM is the sum of $m(\mathbf{\hat{y}})_{q}$
values over all distinct ROC points $q$. Geometrically, the SM function
measures total distance of distinct points on the ROC curve from the left
(FPR=0) or top (TPR=1, FNR=0) of ROC space. A visualization of the piecewise
constant SM loss as a function of the predicted values $\hat{y}_{i}$ shows
that the AUM is indeed a continuous relaxation that is differentiable almost
everywhere (Figure 3, right).

###  2.8 Properties of AUM

A few interesting properties of the AUM should be immediately apparent.

Finite.

Since $\text{FP}_{i}(-\infty)=0$ and $\text{FN}_{i}(\infty)=0$ for all $i$ (by
assumption), we have $M(\mathbf{\hat{y}}\pm\infty)=0$, which means the AUM
integral (10) is finite, $\text{AUM}(\mathbf{\hat{y}})<\infty$.

Non-negative.

Since the label error is never negative, the AUM integral is never negative,
$\text{AUM}(\mathbf{\hat{y}})\geq 0$.

Convexity.

If all of the $\text{FP}_{i}$ and $\text{FN}_{i}$ functions are monotonic,
then the AUM is convex.

Other properties.

The AUM is continuous, piecewise linear, and differentiable almost everywhere.

It can be seen that non-differentiable points in the AUM coincide with
discontinuities in AUC (Figure 3, right). Furthermore at differentiable
points, if $\text{AUM}(\mathbf{\hat{y}})=0$ then
$\text{AUC}(\mathbf{\hat{y}})=1$; the converse is clearly false, however
(Figure 3, right). In this figure it can also be seen that for all predictions
with maximal AUC=2, we have $\text{AUM}>0$, which means there are some
prediction thresholds which result in FP=FN=1. This observation suggests that
instead of maximizing AUC, it may be preferable to minimize AUM as a surrogate
loss, to obtain AUC=1. We therefore propose an AUM gradient descent learning
algorithm in the next section.

##  3 Algorithms

In this section we propose algorithms for computing the AUM and its gradient,
and for learning a linear model.

###  3.1 Details of AUM computation

In previous sections we have assumed that a sequence of $Q$ points on the ROC
curve (or equivalently intervals of FP/FN functions) can be computed, and in
this section we explain how to do that. Recall from Section 2.3 that the
$\text{FP}_{i},\text{FN}_{i}$ functions have an exact representation in terms
of breakpoints. Let there be a total of $B$ breakpoints in the error functions
over all $n$ labeled training examples, where each breakpoint
$b\in\\{1,\dots,B\\}$ is represented by the tuple
$(v_{b},\Delta\text{FP}_{b},\Delta\text{FN}_{b},\mathcal{I}_{b})$. The
$\mathcal{I}_{b}\in\\{1,\dots,n\\}$ is an example index, so there are changes
$\Delta\text{FP}_{b},\Delta\text{FN}_{b}$ at predicted value
$v_{b}\in\mathbb{R}$ in the error functions
$\text{FP}_{\mathcal{I}_{b}},\text{FN}_{\mathcal{I}_{b}}$ (Figure 1). For
example in binary classification, there are $B=n$ breakpoints (same as the
number of labeled training examples); for each breakpoint
$b\in\\{1,\dots,B\\}$ we have $v_{b}=0$ and $\mathcal{I}_{b}=b$. For
breakpoints $b$ with positive labels $y_{b}=1$ we have
$\Delta\text{FP}=0,\Delta\text{FN}=-1$, and for negative labels $y_{b}=-1$ we
have $\Delta\text{FP}=1,\Delta\text{FN}=0$. In changepoint detection we have
more general error functions, which may have more than one breakpoint per
example. For example the labeled data sequence shown in Figure 1 is a single
labeled training example $i$ with error functions that can be represented by
four breakpoints $b$ with the same $\mathcal{I}_{b}=i$ value.

Given a prediction vector
$\mathbf{\hat{y}}=[\hat{y}_{1}\cdots\hat{y}_{n}]^{\intercal}\in\mathbb{R}^{n}$
we can compute a prediction threshold $t_{b}=v_{b}-\hat{y}_{\mathcal{I}_{b}}$
for each breakpoint $b\in\\{1,\dots,B\\}$. The prediction thresholds
$t\in\\{t_{1},\dots,t_{B}\\}$ are where there are changes in the total error
functions $\text{FPT}_{\mathbf{\hat{y}}}(t),\text{FNT}_{\mathbf{\hat{y}}}(t)$
defined in equations (3–4). These functions can be exactly represented by the
sequences of $b\in\\{1,\dots,B\\}$ error values

$\displaystyle\underline{\text{FP}}_{b}$ $\displaystyle=$
$\displaystyle\sum_{j:t_{j}<t_{b}}\Delta\text{FP}_{j},$ (13)
$\displaystyle\overline{\text{FP}}_{b}$ $\displaystyle=$
$\displaystyle\sum_{j:t_{j}\leq t_{b}}\Delta\text{FP}_{j},$ (14)
$\displaystyle\underline{\text{FN}}_{b}$ $\displaystyle=$
$\displaystyle\sum_{j:t_{j}\geq t_{b}}-\Delta\text{FN}_{j},$ (15)
$\displaystyle\overline{\text{FN}}_{b}$ $\displaystyle=$
$\displaystyle\sum_{j:t_{j}>t_{b}}-\Delta\text{FN}_{j}.$ (16)

The $\underline{\text{FP}}_{b},\underline{\text{FN}}_{b}$ are the error values
before the threshold $t_{b}$, whereas
$\overline{\text{FP}}_{b},\overline{\text{FN}}_{b}$ are the error values after
the threshold. We sort the breakpoints by threshold, yielding a permutation
$\\{s_{1},\dots,s_{B}\\}$ of the indices $\\{1,\dots,B\\}$ such that for every
$q\in\\{2,\dots,B\\}$ we have $t_{s_{q-1}}\leq t_{s_{q}}$. All of the error
values
$\underline{\text{FP}}_{b},\overline{\text{FP}}_{b},\underline{\text{FN}}_{b},\overline{\text{FN}}_{b}$,
for every $b\in\\{1,\dots,B\\}$, can then be computed via a modified
cumulative sum (starting with $\underline{\text{FP}}_{1}=0$ and
$\overline{\text{FN}}_{B}=0$). In terms of the notation of Section 2.7, we
have $Q=B+1$ points (not necessarily unique) on the ROC curve such that
$\tau(\mathbf{\hat{y}})_{q}=t_{s_{q}}$ and
$m(\mathbf{\hat{y}})_{q}=\min\\{\underline{\text{FP}}_{s_{q}},\underline{\text{FN}}_{s_{q}}\\}=\min\\{\overline{\text{FP}}_{s_{q-1}},\overline{\text{FN}}_{s_{q-1}}\\}$.
The AUM can then be computed via

$\displaystyle\text{AUM}(\mathbf{\hat{y}})$ $\displaystyle=$
$\displaystyle\sum_{q=2}^{B}(t_{s_{q}}-t_{s_{q-1}})\min\\{\overline{\text{FP}}_{s_{q-1}},\overline{\text{FN}}_{s_{q-1}}\\},$
(17) $\displaystyle=$
$\displaystyle\sum_{q=2}^{B}(t_{s_{q}}-t_{s_{q-1}})\min\\{\underline{\text{FP}}_{s_{q}},\underline{\text{FN}}_{s_{q}}\\}.$
(18)

The equations above state that the AUM can be computed by multiplying each
threshold difference $t_{s_{q}}-t_{s_{q-1}}$ by the minimum below breakpoint
$s_{q}$ (18) or above breakpoint $s_{q-1}$ (17). Since the slowest operation
is the sort, the overall time complexity for computing the AUM is $O(B\log
B)$.

Algorithm 1 AUM and Directional Derivatives

1:Input: Predictions $\mathbf{\hat{y}}\in\mathbb{R}^{n}$, breakpoints in error
functions $v_{b},\Delta\text{FP}_{b},\Delta\text{FN}_{b},\mathcal{I}_{b}$ for
all $b\in\\{1,\dots,B\\}$.

2:Initialize to zero the $\text{AUM}\in\mathbb{R}$ and directional derivative
matrix $\mathbf{D}\in\mathbb{R}^{n\times 2}$.

3:$t_{b}\leftarrow v_{b}-\hat{y}_{\mathcal{I}_{b}}$ for all $b$.

4:$s_{1},\dots,s_{B}\leftarrow\textsc{SortedIndices}(t_{1},\dots,t_{B}).$

5:Compute
$\underline{\text{FP}}_{b},\overline{\text{FP}}_{b},\underline{\text{FN}}_{b},\overline{\text{FN}}_{b}$
for all $b$ using $s_{1},\dots,s_{B}$ and (13–16).

6:for $b\in\\{2,\dots,B\\}$ do

7: $\text{AUM}\text{ +=
}(t_{s_{b}}-t_{s_{b-1}})\min\\{\underline{\text{FP}}_{b},\overline{\text{FN}}_{b}\\}$.

8:for $b\in\\{1,\dots,B\\}$ do

9: $D_{\mathcal{I}_{b},1}\text{ +=
}\min\\{\overline{\text{FP}}_{b},\overline{\text{FN}}_{b}\\}-\min\\{\overline{\text{FP}}_{b}-\Delta\text{FP}_{b},\overline{\text{FN}}_{b}-\Delta\text{FN}_{b}\\}$

10: $D_{\mathcal{I}_{b},2}\text{ +=
}\min\\{\underline{\text{FP}}_{b}+\Delta\text{FP}_{b},\underline{\text{FN}}_{b}+\Delta\text{FN}_{b}\\}-\min\\{\underline{\text{FP}}_{b},\underline{\text{FN}}_{b}\\}$

11:Output: AUM and matrix $\mathbf{D}$ of directional derivatives.

###  3.2 Gradient computation

First we note that the AUM function is not differentiable everywhere, so the
gradient is not defined everywhere (e.g., orange dots in Figure 3, right).
Second we note that the AUM function can be non-convex, in which case the sub-
differential from convex analysis is not defined (Rockafellar, 1970). Instead,
we propose an algorithm for computing the AUM directional derivatives, which
are defined everywhere. We recall the general definition of a directional
derivative.

######  Definition 1.

Given vectors $\mathbf{x},\mathbf{v}\in\mathbb{R}^{n}$ and a function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$, the directional derivative of $f$ at
$\mathbf{x}$ in the direction of $\mathbf{v}$ is the function
$\nabla_{\mathbf{v}}f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ given by

$\nabla_{\mathbf{v}}f(\mathbf{x})=\lim_{h\rightarrow
0}\frac{f(\mathbf{x}+h\mathbf{v})-f(\mathbf{x})}{h}.$ (19)

We would like to compute $\nabla_{\mathbf{v}}\text{AUM}(\mathbf{\hat{y}})$,
for a set of directions $\mathbf{v}$. We are interested in computing the
directional derivative along a single dimension $i\in\\{1,\dots,n\\}$, in
either the negative or positive direction, which correspond to using direction
vectors $\mathbf{v}$ with $-1$ or 1 at the $i$-th position, and zeros at each
other position,

$\displaystyle\mathbf{v}(-1,i)$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{ccccc}0&\cdots&-1&\cdots&0\end{array}\right]^{\intercal},$
(21) $\displaystyle\mathbf{v}(1,i)$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{ccccc}0&\cdots&1&\cdots&0\end{array}\right]^{\intercal}.$
(23)

The intuition of these direction vectors is that each will give us the rate of
change of AUM, if a single prediction $i$ is either increased or decreased. We
propose an algorithm for efficiently computing the following $n\times 2$
matrix of directional derivatives,

$\mathbf{D}_{f}(\mathbf{x})=\left[\begin{array}[]{ccc}\nabla_{\mathbf{v}(-1,1)}f(\mathbf{x})&\cdots&\nabla_{\mathbf{v}(-1,n)}f(\mathbf{x})\\\
\nabla_{\mathbf{v}(1,1)}f(\mathbf{x})&\cdots&\nabla_{\mathbf{v}(1,n)}f(\mathbf{x})\end{array}\right]^{\intercal}.$
(24)

We will compute $\mathbf{D}_{\text{AUM}}(\mathbf{\hat{y}})$, which is the
matrix of directional derivatives for a given prediction vector. If we have
equality of elements of all rows of this matrix, i.e.,
$\nabla_{\mathbf{v}(-1,i)}\text{AUM}(\mathbf{\hat{y}})=\nabla_{\mathbf{v}(1,i)}\text{AUM}(\mathbf{\hat{y}})$
for all $i$, then the gradient does exist at $\mathbf{\hat{y}}$ and is equal
to that value. The following theorem shows how to compute the elements of this
matrix.

######  Theorem 1.

The AUM directional derivatives for a particular example $i\in\\{1,\dots,n\\}$
can be computed using the following equations.

$\displaystyle\nabla_{\mathbf{v}(-1,i)}\text{AUM}(\mathbf{\hat{y}})$
$\displaystyle=$
$\displaystyle\sum_{b:\mathcal{I}_{b}=i}\min\\{\overline{\text{FP}}_{b},\overline{\text{FN}}_{b}\\}-\min\\{\overline{\text{FP}}_{b}-\Delta\text{FP}_{b},\overline{\text{FN}}_{b}-\Delta\text{FN}_{b}\\},$
(25) $\displaystyle\nabla_{\mathbf{v}(1,i)}\text{AUM}(\mathbf{\hat{y}})$
$\displaystyle=$
$\displaystyle\sum_{b:\mathcal{I}_{b}=i}\min\\{\underline{\text{FP}}_{b}+\Delta\text{FP}_{b},\underline{\text{FN}}_{b}+\Delta\text{FN}_{b}\\}-\min\\{\underline{\text{FP}}_{b},\underline{\text{FN}}_{b}\\}.$
(26)

###### Proof.

We can compute AUM using either (17) or (18). To compute a directional
derivative we need to evaluate
$\text{AUM}[\mathbf{\hat{y}}+h\mathbf{v}(d,i)]$. To do that we must use (17)
if $d=-1$ and (18) if $d=1$. First consider the case of $d=1$, if
$t_{s_{q-1}}=t_{s_{q}}$, and $\mathcal{I}_{s_{q-1}}=i$. In that case the
analogous term in $\text{AUM}[\mathbf{\hat{y}}+h\mathbf{v}(d,i)]$ will have
$v_{s_{q-1}}-\hat{y}_{s_{q-1}}-h<v_{s_{q}}-\hat{y}_{s_{q}}$. Then the min in
the corresponding term must be
$\min\\{\underline{\text{FP}}_{s_{b-1}}+\Delta\text{FP}_{b-1},\underline{\text{FN}}_{s_{b-1}}+\Delta\text{FP}_{b-1}\\}$
and so

$\displaystyle\nabla_{\mathbf{v}(1,i)}\text{AUM}(\mathbf{\hat{y}})$
$\displaystyle=$
$\displaystyle\sum_{b=2}^{B}\left(I[\mathcal{I}_{s_{b-1}}=i]-I[\mathcal{I}_{s_{b}}=i]\right)\min\\{\underline{\text{FP}}_{s_{b-1}}+\Delta\text{FP}_{s_{b-1}},\underline{\text{FN}}_{s_{b-1}}+\Delta\text{FP}_{s_{b-1}}\\},$
(29) $\displaystyle=$
$\displaystyle\sum_{b=2}^{B}I[\mathcal{I}_{s_{b-1}}=i]\min\\{\underline{\text{FP}}_{s_{b-1}}+\Delta\text{FP}_{s_{b-1}},\underline{\text{FN}}_{s_{b-1}}+\Delta\text{FP}_{s_{b-1}}\\}$
$\displaystyle-\sum_{b=2}^{B}I[\mathcal{I}_{s_{b}}=i]\min\\{\underline{\text{FP}}_{s_{b-1}}+\Delta\text{FP}_{s_{b-1}},\underline{\text{FN}}_{s_{b-1}}+\Delta\text{FP}_{s_{b-1}}\\},$
$\displaystyle=$
$\displaystyle\sum_{b=1}^{B}I[\mathcal{I}_{s_{b}}=i]\min\\{\underline{\text{FP}}_{s_{b}}+\Delta\text{FP}_{s_{b}},\underline{\text{FN}}_{s_{b}}+\Delta\text{FP}_{s_{b}}\\}$
$\displaystyle-\sum_{b=1}^{B}I[\mathcal{I}_{s_{b}}=i]\min\\{\underline{\text{FP}}_{s_{b}},\underline{\text{FN}}_{s_{b}}\\}.$

The first equality comes from the definition of the directional derivative,
the second distributes the min, and the third re-writes some of the $b-1$
indices as $b$. The sum can be extended to start at $b=1$ since
$\underline{\text{FP}}_{s_{1}}=0$ (the first min is zero). Finally, re-writing
the sums and removing the indicator functions obtains the desired result. The
proof for the case of $d=-1$ is analogous. ∎

Figure 4: In a real changepoint detection problem with $n=54$ labeled
examples, minimizing the AUM tends to increase train AUC and label error
rates. Left: we used AUM gradient descent on the $n$-vector of predicted
values $\mathbf{\hat{y}}$ in the train set (initial predictions chosen by
minimizing label errors for each example). Decreases in AUM happen during the
same iterations as increases in AUC and label error rates. Middle: ROC curves
before and after using AUM gradient descent on the $n$-vector of predicted
values (dot shows a point on each ROC curve with minimum label errors). Right:
optimizing the $p$-vector of weights in a linear model ($p=27$ features,
initial weights minimize an un-regularized squared hinge loss summed over
labeled examples). Note that AUC=0.85 is unchanged by the optimization but AUM
decreases and error rate increases.

###  3.3 Pseudocode and complexity analysis

We propose to compute the matrix of directional derivatives using Algorithm 1
which inputs a prediction vector $\mathbf{\hat{y}}\in\mathbb{R}^{n}$ and an
exact description of the error functions in terms of breakpoints
$v_{b},\Delta\text{FP}_{b},\Delta\text{FN}_{b},\mathcal{I}_{b}$. The first
step is to compute thresholds $t_{b}=v_{b}-\hat{y}_{\mathcal{I}_{b}}$ in the
total error functions (line 3) which are then sorted (line 4). The sorted
indices are then used to compute modified cumulative sums of false positives
and false negatives,
$\underline{\text{FP}}_{b},\overline{\text{FP}}_{b},\underline{\text{FN}}_{b},\overline{\text{FN}}_{b}$,
for each breakpoint $b$ (line 5). Note that for FP we start with
$\underline{\text{FP}}_{1}=0$ and add in the forward direction, whereas for FN
we start with $\overline{\text{FN}}_{B}=0$ and subtract in the reverse
direction. Each iteration of the for loop over intervals of threshold values
(line 6) adds to the AUM (line 7). Each iteration of the for loop over
breakpoints $b$ (line 8) adds to row $\mathcal{I}_{b}$ of the directional
derivative matrix. The first column stores the derivative in the negative
direction (line 9) and the second column stores the derivative in the positive
direction (line 10). The time complexity of Algorithm 1 is log-linear $O(B\log
B)$ because of the sort (line 4). Since there is at least one breakpoint in
each of the $n$ example-specific error functions, the total number of
breakpoints $B\geq n$. Therefore, computing the AUM and its directional
derivatives is $O(n\log n)$, asymptotically slower than $O(n)$ margin-based
loss functions by a log factor.

###  3.4 Gradient descent algorithm for predicted values

We propose gradient descent optimization algorithms that use the AUM
directional derivatives computed using Theorem 1 and Algorithm 1. First to
study how minimizing the train AUM affects the train AUC, we propose to
optimize the $n$-vector of predictions $\mathbf{\hat{y}}$. When the AUM is
non-convex, the initialization of the algorithm is important. Therefore when
optimizing the vector of predictions, we propose initializing each
$\hat{y}_{i}$ to a value with minimum label errors,

$\hat{y}_{i}^{(0)}=\operatorname*{arg\,min}_{x}\text{FP}_{i}(x)+\text{FN}_{i}(x).$
(30)

After initialization we need to compute a descent direction; typically the
negative gradient is used. Recall that since the AUM has non-differentiable
points, the gradient is not defined at these points. The “gradient” we propose
to use is the mean of the two columns of the directional derivative matrix,
$\mathbf{\bar{D}}_{\text{AUM}}(\mathbf{\hat{y}})\in\mathbb{R}^{n}$, with each
element $i\in\\{1,\dots,n\\}$ of this vector defined as
$[\nabla_{\mathbf{v}(-1,i)}\text{AUM}(\mathbf{\hat{y}})+\nabla_{\mathbf{v}(1,i)}\text{AUM}(\mathbf{\hat{y}})]/2$.
When running our gradient descent algorithm, we have observed that it
empirically almost always stays at differentiable points (i.e., columns of
directional derivative matrix are equal). However, we have observed a few
cases where the gradient descent algorithm visits non-differentiable points,
for which there is at least one row in the directional derivative matrix with
entries that are not equal. Examples of such directional derivative rows
$[\nabla_{\mathbf{v}(-1,i)}\text{AUM}(\mathbf{\hat{y}}),\nabla_{\mathbf{v}(1,i)}\text{AUM}(\mathbf{\hat{y}})]$
that we have observed include $[-0.0019,-0.0011]$ and $[-0.0006,0]$, both of
which indicate that the loss would increase if the predicted value is
decreased. We also perform line search via grid search in order to obtain a
step size $\alpha^{(j)}$ which results in the largest decrease in AUM. Also
let $\beta^{(j)}$ be an intercept or threshold with minimal error after taking
the line search step (it only affects the label error/accuracy and not the
AUM). Note that this intercept can be efficiently computed at the same time as
the AUM and its directional derivative matrix, by a simple linear scan over
all thresholds. We then perform gradient descent updates for each iteration
$j\in\\{0,1,\dots\\}$ via

$\mathbf{\hat{y}}^{(j+1)}=\mathbf{\hat{y}}^{(j)}-\alpha^{(j)}\mathbf{\bar{D}}_{\text{AUM}}(\mathbf{\hat{y}}^{(j)})+\beta^{(j)}.$
(31)

Figure 5:  Linear model which minimizes AUM via gradient descent results in
maximizing AUC on held-out test data. Algorithm (y axis) shows how number of
iterations was chosen, by minimizing validtion AUM, maximizing validation AUC,
or taking the initial iteration. Each of five columns from left to right shows
results for four random seeds on a given data set and test fold (n,p=number of
examples and features for that entire data set).

###  3.5 Gradient descent algorithm for linear model

In the context of making predictions on a held-out test set, we consider a
linear model $f(\mathbf{x})=\mathbf{w}^{\intercal}\mathbf{x}+\beta$
parameterized by a weight vector $\mathbf{w}\in\mathbb{R}^{p}$ to optimize via
gradient descent, and an intercept $\beta\in\mathbb{R}$ optimized via a linear
scan to find a threshold with minimum label error. Let
$\mathbf{X}\in\mathbb{R}^{n\times p}$ be the feature/input matrix, so
$\mathbf{X}\mathbf{w}+\beta\in\mathbb{R}^{n}$ is the vector of predicted
values on the train set. We consider an intialization $\mathbf{w}^{(0)}$ based
on minimizing a convex squared hinge loss with L1 regularization (Rigaill et
al., 2013). This convex loss function has a minimum for each example at
predicted values that achieve minimum label errors, so we expect this
initialization to have large accuracy but not necessarily large AUC. Again let
$\alpha^{(j)}$ be the line search step size, and let $\beta^{(j)}$ be an
intercept with minimal train error. We perform gradient descent for each
iteration $j\in\\{0,1,\dots\\}$ via

$\mathbf{w}^{(j+1)}=\mathbf{w}^{(j)}-\alpha^{(j)}\mathbf{X}^{\intercal}\mathbf{\bar{D}}_{\text{AUM}}(\mathbf{X}\mathbf{w}^{(j)}+\beta^{(j)}).$
(32)

To regularize the model for the experiments in this paper, we use early
stopping (number of iterations chosen by minimizing AUM or maximizing AUC with
respect to a held-out validation set).

##  4 Empirical Results

We empirically study AUM minimization in the context of binary classification
and changepoint detection problems. Our goal is to demonstrate that AUM
minimization can result in AUC maximization with respect to train and test
data.

###  4.1 AUM gradient descent optimizes train AUC

In this experiment our goal was to demonstrate that minimizing the AUM results
in maximizing the AUC in the train set. We used the chipseq data (a benchmark
for labeled changepoint detection) from the UCI repository (Asuncion and
Newman, 2007), treating each (set.name, fold) as a different train set, with
pre-processing as previously described.111 github.com/tdhock/feature-learning-
benchmark In brief, for each labeled example, changepoint models were computed
for a range of penalty values, which resulted in models with a range of
changepoints (some with few changepoints, others with many). Then the label
error rate for each model was computed, along with a penalty
$\hat{\lambda}_{i}$ which resulted in minimum label errors for each labeled
example $i$. Finally these penalty values were used as the initial prediction
vector
$\mathbf{\hat{y}}=[-\log\hat{\lambda}_{1}\cdots-\log\hat{\lambda}_{n}]$, which
was used as the optimization variable in an AUM gradient descent algorithm. A
line search was used for the step size so that the AUM was guaranteed to
decrease at each iteration. Overall there were 68 different train sets with
the number of labeled examples ranging from $n=7$ to 1011, and the total
number of breakpoints in error functions ranging from $B=47$ to 3104.

We expected that by using the predicted values directly as the optimization
variable in gradient descent, we should be able to obtain ROC curves that were
significantly different from the initialization (hopefully with larger AUC,
even though the initialization came from minimizing the label error
independently for each example). In a small number of train sets we observed
that the optimization resulted in little or no change to both AUM and AUC;
this happened when the initialization was close to or at a stationary point of
the AUM (for example, when AUM=0 and AUC=1). However in most of the train sets
we observed that minimizing the AUM results in increased AUC (on the train
set).

In one representative train set (H3K4me3_XJ_immune fold 4 which has $n=54$
labeled examples with a total of $B=347$ breakpoints in error functions), we
observed that the AUC and label error rate increases during the same
iterations that the AUM decreases (Figure 4, left). Before optimization the
ROC curve was highly non-monotonic with a sharp point in the upper left
corner; after AUM optimization the ROC curve became more regular with
increased area (Figure 4, middle). This result suggests that AUM gradient
descent can be used to maximize the AUC, although the label error rate also
increases.

We performed a second experiment, this time optimizing $p=27$ weights in a
linear model parameter vector which was used to compute a prediction for each
of the $n=54$ labeled examples. The weights were initialized by using a
gradient descent algorithm to minimize an un-regularized squared hinge loss
that is a convex relaxation of the label error (Rigaill et al., 2013). We
expected the constraints of the linear model to reduce the accuracy with
respect to the previous experiment (direct optimization of predicted values).
We observed that after optimizing the weights using AUM gradient descent, the
train AUC remained the same, but the train error rate increased (Figure 4,
right). This experiment shows that the constraints of a linear model can
prevent AUM minimization from resulting in AUC maximization (even in a data
set for which it is possible to achieve larger AUC values).

Figure 6:  Test AUC in binary classification (images of 0/1 digits). Fixed
test set with balanced classes (50% positive, 50% negative labels), and three
train sets with different class imbalance (1%, 5%, 50% positive labels). Left
(a): AUM count is more accurate than AUM rate. Right (b): AUM count is at
least as accurate as baselines, and sometimes more accurate.

###  4.2 Test AUM and AUC in changepoint problems

In these experiments, the goal was to demonstrate that test AUC correlates
with test AUM using our proposed linear model based on AUM minimization. We
considered supervised changepoint detection data sets from a public
repository.222github.com/tdhock/neuroblastoma-data It included pre-defined
fold IDs that we used to define train/test splits over labeled examples of
changepoint detection problems. In the five train sets that we analyzed
(Figure 5), the number of labeled examples ranged from $n=216$ to 3322, the
number of features from $p=26$ to 117, and the total number of error function
breakpoints from $B=1275$ to 7732. As explained in Section 3.5, our
initialization and baseline was a linear model learned via gradient descent on
a convex squared hinge loss with L1 regularization (Rigaill et al., 2013). To
determine the extent to which the result depends on random initialization, we
used four different seeds to select four different initial models. Some of the
random seeds resulted in the same initial weights, despite having different
seeds.

For each train set and random seed we used AUM gradient descent and selected
the number of iterations via 4-fold cross-validation (take mean validation
AUC/AUM over folds, then select iterations by maximizing AUC or minimizing
AUM). In general we observed that both methods for selecting the number of
iterations resulted in increased test AUC and decreased test AUM (middle three
panels of Figure 5). However for some data the AUM gradient descent did not
improve over the initialization (left and right panels). This can be explained
because some splits had very different train and test sets (left) or the
selected number of gradient descent iterations was zero (right). Overall these
real data experiments indicate that AUM minimization often results in AUC
maximization on held-out test data.

Figure 7:  Speed comparison, time to compute gradient of various loss
functions for data sets with variable number $n$ of labeled examples. Left:
for binary classification our timings suggest that AUM is $O(n\log n)$, faster
than a $O(n^{2})$ squared hinge loss summed over all pairs of
positive/negative examples, and slower than $O(n)$ Logistic loss summed over
all labeled examples. Right: for changepoint detection problems we observed
that AUM is asymptotically similar to, but slower than, a squared hinge loss
summed over labeled examples.

###  4.3 Test AUC in binary classification

The goal in this section was to study the accuracy of our proposed AUM loss
function in unbalanced binary classification problems. Our experiment used the
zip.train and zip.test image classification
data333https://web.stanford.edu/~hastie/ElemStatLearn/ from (Hastie et al.,
2009). Each input is a $16\times 16$ image which is represented by a vector
$x\in\mathbb{[}-1,1]^{256}$. There are 10 classes (one for each digit), but we
only used two classes (0/1) in order to study binary classification. For both
the zip.train and zip.test files, we discarded some $y_{i}=0$ labels in order
to obtain sets with equal numbers of positive and negative labels (total 2010
in train, 528 in test). Then we generated 10 different train sets by randomly
selecting 1000 examples with a class balance in $\\{1\%,5\%,50\%\\}$. The goal
is to learn from the unbalanced train set data and then provide accurate
predictions (as measured by AUC) on the balanced test set. The learning
algorithms that we considered in our comparison were all based on gradient
descent with constant step size and early stopping regularization. The step
size and number of iterations hyper-parameters were chosen using grid search
on a held-out validation set. Since AUM is a full gradient method (not
stochastic), we compared with several other loss functions using the full
gradient method.

In our first comparison we wanted to understand if it is beneficial to
normalize the AUM (use relative error rates rather than absolute error
counts). In equations (10–11) we defined the AUM as the area under the minimum
of false positive and false negative _counts_ , but we could instead use
_rates_. To compute AUM using rates, we need only change FPT/FNT functions in
the minimum function (9) to FPR/FNR. In Figure 6 we refer to this variant as
_AUM.rate_ , and the original version as _AUM.count_. It is clear from Figure
6(a) that the _AUM.count_ loss function variant has consistently larger test
AUC than _AUM.rate_. The advantage of _AUM.count_ becomes greater as the class
imbalance is increased. For example, with no class imbalance median test AUC
for _AUM.count_ is 0.9993 and for _AUM.rate_ is 0.9979 ($p=0.03$ in one-sided
$t_{9}$-test); for large class imbalance with 1% positive labels median test
AUC for _AUM.count_ is 0.9979 and for _AUM.rate_ is 0.9928 ($p=0.004$). These
results suggest that it is not beneficial to normalize the AUM, and it is more
accurate to simply minimize the absolute min(FP,FN) counts.

In our second comparison we wanted to compare AUM optimization to standard
baseline loss functions for binary classification. As a baseline for margin
loss functions (summed over labeled examples), we used a weighted version of
the logistic loss $w_{i}\log[1+\exp(y_{i}f(\mathbf{x}_{i}))]$. The weights
$w_{i}\in\mathbb{R}$ are defined in order to ensure that the sum of weights
over all negative/positive examples is the same (Menon et al., 2013). The
total number of positive examples is $N_{1}=|\\{i:y_{i}=1\\}|$ and negative
examples is $N_{-1}=|\\{i:y_{i}=-1\\}|$; the weights are therefore
$w_{i}=1/N_{y_{i}}$. For example when the class balance is 10%, there are
$N_{1}=100$ positive examples and $N_{-1}=900$ negative examples. Each
positive example $i$ has a weight of $w_{i}=1/100$, and each negative example
$i$ has a weight of $w_{i}=1/900$. The total weight over each class
$y\in\\{1,-1\\}$ is $\sum_{i:y_{i}=y}w_{i}=1$, which makes both classes
equally important in the loss function. As a baseline for pairwise loss
functions (summed over all pairs of positive $y_{j}=1$ and negative $y_{i}=-1$
examples), we used a squared hinge loss,
$[1-f(\mathbf{x}_{j})+f(\mathbf{x}_{i})]_{+}^{2}$. Both baselines were chosen
because they are supposed to maximize AUC (rather than the accuracy rate). We
observed in Figure 6(b) that the learning algorithm using the AUM loss had
test AUC values consistently better than or competitive with the baselines.
The AUM loss had median test AUC that was consistently larger than the
weighted logistic loss, with the largest difference for 1% positive labels
(AUM=0.9979, logistic=0.9950, $p<0.06$). There were smaller differences in
median test AUC between the AUM loss and the squared hinge all pairs loss,
with the largest difference for balanced labels (AUM=0.9993, pairs=0.9991,
$p<0.19$). Overall these experiments demonstrate that the AUM loss is highly
competitive with the baseline loss functions, even when the train data set has
large class imbalance.

###  4.4 Speed comparison

The goal of this section is to show that AUM gradient computation has
comparable speed to existing loss functions. Since the AUM is a full gradient
algorithm (computes gradient with respect to full training set), we compared
to other full gradient methods (no stochastic / minibatch methods). In the
case of binary classification, we compared the gradients of three loss
functions, as shown in (Figure 7, left): squared hinge all pairs $O(n^{2})$,
AUM $O(n\log n)$, and logistic $O(n)$. For a fixed budget of computation time
(1 second), the gradient of the AUM loss can be computed for much larger
problems ($n=$ millions) than the naïve square hinge all pairs approach ($n=$
thousands). Although the gradient for the AUM has a slower asymptotic runtime
than logistic loss, an AUM-based model creates substantially better test data
AUC, especially with imbalanced datasets.

We also did a speed test in the context of real changepoint detection
problems, by comparing the AUM to a squared hinge loss summed over each of the
$n$ labeled examples (Rigaill et al., 2013). We observed that the AUM gradient
is slower than the squared hinge loss in terms of asymptotic complexity
(Figure 7, right). For example we observed about 10ms for AUM versus 1ms for
the squared hinge for about $n\approx 5000$ examples with approximately 5
breakpoints in each example-specific error function. Overall these data show
that the AUM has comparable speed to previously proposed loss functions for
AUC optimization in binary classification, and changepoint detection.

##  5 Discussion and conclusions

In this paper we proposed the new AUM loss function which can be used in the
context of prediction problems with false positive/negative rates such as in
supervised binary classification and changepoint detection. We showed that the
AUM can be interpreted as an L1 relaxation of a loss function that sums the
min(FP,FN) rate over all distinct points on the ROC curve. Minimizing the AUM
therefore encourages the points on the ROC curve to be in the upper left of
the (FPR,TPR) space. We proposed a new algorithm for efficiently computing the
AUM and its directional derivatives. For $n$ labeled training examples and $B$
total breakpoints in all error functions, our algorithm for computing the
$n\times 2$ directional derivative matrix is $O(B\log B)$ time, which is much
faster than previous $O(n^{2})$ full gradient approaches that naïvely sum over
all pairs of positive and negative examples.

In our empirical comparisons with several baseline full gradient algorithms,
we observed comparable or better test AUC using our proposed method. We have
shown that in binary classification, the AUM loss often out-performs baseline
margin and pairwise losses (especially with un-balanced labels in the training
data). We observed that in changepoint detection problems with non-monotonic
FP/FN functions, there is a tradeoff between AUC and accuracy that does not
exist in binary classification problems. If maximizing accuracy with respect
to the labels is important, we can use existing convex loss functions which
are surrogates to minimizing label error rates (Rigaill et al., 2013). If
maximizing AUC is important, then we can minimize our new AUM loss function
which we have shown empirically results in AUC maximization (but lower
accuracy). This tradeoff between AUC and accuracy means that the max accuracy
model results in a highly non-monotonic ROC curve with many sub-optimal
points, whereas the max AUC model has a more regular ROC curve (Figure 4).
Overall our empirical results indicate that the AUM is a useful surrogate loss
function for optimizing ROC curves.

For future work, we have already started exploring the connection between AUM
and other AUC relaxations, in order to create new AUC optimization algorithms.
In fact, using an L1 relaxation pairwise loss (hinge with margin of zero) is
quite similar to our approach (AUM integrates the min of FP and FN over all
thresholds, whereas pairwise loss integrates the product). This suggests that
it should be possible to compute the full gradient for a pairwise loss in log-
linear time, so we are currently exploring a new algorithm based on that idea.
Additionally, we would like to consider several variants of our new AUM loss
function. In this work we proposed a full gradient algorithm (takes a step
defined by all training examples), and we would additionally like to explore a
batch variant (takes a step defined by a subset of training examples).
Although that would be non-trivial since the AUM is not separable over
training examples, it would be interesting to compare a batch variant with
recent work on stochastic gradient methods for AUC optimization (Ying et al.,
2016). Finally our current algorithm used either constant step size or a grid
search, but a faster learning algorithm could potentially be obtained by
exploiting the piecewise linear nature of the AUM during the step size
computation.

#### Author statement.

The authors declare that they have no conflict of interest. TDH contributed to
the conception of ideas, proving theorems, implementing the algorithms, making
figures, writing and revising the text. JH contributed to analysis of data,
creation of figures, writing and revising the text.

#### Reproducible Research Statement.

All of the software and data required to make the figures in this paper can be
downloaded from https://github.com/tdhock/max-generalized-auc. An R package
with C/C++ code that implements Algorithm 1 is available at
https://github.com/tdhock/aum.

## References

  * Aminikhanghahi and Cook (2017) S. Aminikhanghahi and D. J. Cook.  A survey of methods for time series change point detection.  _Knowledge and information systems_ , 51(2):339–367, 2017.
  * Asuncion and Newman (2007) A. Asuncion and D. Newman.  UCI machine learning repository, 2007.
  * Bamber (1975) D. Bamber.  The area above the ordinal dominance graph and the area below the receiver operating characteristic graph.  _Journal of mathematical psychology_ , 12(4):387–415, 1975.
  * Barnwal et al. (2020) A. Barnwal, H. Cho, and T. Hocking.  Survival regression with accelerated failure time model in xgboost.  Preprint arXiv:2006.04920, 2020.
  * Calders and Jaroszewicz (2007) T. Calders and S. Jaroszewicz.  Efficient AUC optimization for classification.  In _European Conference on Principles of Data Mining and Knowledge Discovery_ , pages 42–53. Springer, 2007.
  * Castro and Braga (2008) C. L. Castro and A. P. Braga.  Optimization of the area under the ROC curve.  In _2008 10th Brazilian Symposium on Neural Networks_ , pages 141–146. IEEE, 2008.
  * Cortes and Mohri (2004) C. Cortes and M. Mohri.  AUC optimization vs. error rate minimization.  _Advances in neural information processing systems_ , 16(16):313–320, 2004.
  * Drouin et al. (2017) A. Drouin, T. Hocking, and F. Laviolette.  Maximum margin interval trees.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems 30_ , pages 4947–4956. Curran Associates, Inc., 2017.
  * Egan and Egan (1975) J. P. Egan and J. P. Egan.  _Signal detection theory and ROC-analysis_.  Academic press, 1975.
  * Ferri et al. (2002) C. Ferri, P. Flach, and J. Hernández-Orallo.  Learning decision trees using the area under the ROC curve.  In _ICML_ , volume 2, pages 139–146, 2002.
  * Freund et al. (2003) Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer.  An efficient boosting algorithm for combining preferences.  _Journal of machine learning research_ , 4(Nov):933–969, 2003.
  * Han and Zhao (2010) G. Han and C. Zhao.  AUC maximization linear classifier based on active learning and its application.  _Neurocomputing_ , 73(7):1272 – 1280, 2010.  ISSN 0925-2312.  Advances in Computational Intelligence and Learning.
  * Hand (2009) D. J. Hand.  Measuring classifier performance: a coherent alternative to the area under the roc curve.  _Machine learning_ , 77(1):103–123, 2009.
  * Hastie et al. (2009) T. Hastie, R. Tibshirani, and J. Friedman.  _The elements of statistical learning_.  Springer Series in Statistics. Springer, Springer Science+Business Media, LLC, 233 Spring Street, New York NY 10013, USA, second edition, 2009.
  * Herschtal and Raskutti (2004) A. Herschtal and B. Raskutti.  Optimising area under the ROC curve using gradient descent.  In _Proceedings of the twenty-first international conference on Machine learning_ , page 49, 2004.
  * Herschtal et al. (2006) A. Herschtal, B. Raskutti, and P. K. Campbell.  Area under ROC optimisation using a ramp approximation.  In _Proceedings of the 2006 SIAM International Conference on Data Mining_ , pages 1–11. SIAM, 2006.
  * Hocking and Vargovich (2020) T. Hocking and J. Vargovich.  Linear time dynamic programming for the exact path of optimal models selected from a finite set.  arXiv:2003.02808, 2020.
  * Hocking et al. (2014) T. Hocking, V. Boeva, G. Rigaill, G. Schleiermacher, I. Janoueix-Lerosey, O. Delattre, W. Richer, F. Bourdeaut, M. Suguro, M. Seto, F. Bach, and J. Vert.  Seganndb: interactive web-based genomic segmentation.  _Bioinformatics_ , 30(11):1539–46, 2014.
  * Hocking and Bourque (2020) T. D. Hocking and G. Bourque.  Machine Learning Algorithms for Simultaneous Supervised Detection of Peaks in Multiple Samples and Cell Types.  In _Proc. Pacific Symposium on Biocomputing_ , volume 25, pages 367–378, 2020.
  * Hocking et al. (2013) T. D. Hocking, G. Schleiermacher, I. Janoueix-Lerosey, V. Boeva, J. Cappo, O. Delattre, F. Bach, and J.-P. Vert.  Learning smoothing models of copy number profiles using breakpoint annotations.  _BMC Bioinformatics_ , 14(164), May 2013.
  * Hocking et al. (2015) T. D. Hocking, G. Rigaill, and G. Bourque.  PeakSeg: constrained optimal segmentation and supervised penalty learning for peak detection in count data.  In _Proc. 32nd ICML_ , pages 324–332, 2015.
  * Hocking et al. (2016) T. D. Hocking, P. Goerner-Potvin, A. Morin, X. Shao, T. Pastinen, and G. Bourque.  Optimizing ChIP-seq peak detectors using visual labels and supervised machine learning.  _Bioinformatics_ , 33(4):491–499, 11 2016.  ISSN 1367-4803.
  * Hocking et al. (2020) T. D. Hocking, G. Rigaill, P. Fearnhead, and G. Bourque.  Constrained Dynamic Programming and Supervised Penalty Learning Algorithms for Peak Detection in Genomic Data.  _Journal of Machine Learning Research_ , 21(87):1–40, 2020.
  * Joachims (2005) T. Joachims.  A support vector method for multivariate performance measures.  In _Proceedings of the 22nd international conference on Machine learning_ , pages 377–384, 2005.
  * Kotlowski et al. (2011) W. Kotlowski, K. Dembczynski, and E. Huellermeier.  Bipartite ranking through minimization of univariate loss.  In _ICML_ , 2011.
  * Liehrmann et al. (2021) A. Liehrmann, G. Rigaill, and T. D. Hocking.  Increased peak detection accuracy in over-dispersed ChIP-seq data with supervised segmentation models.  _BMC Bioinformatics_ , 22(323), 2021.
  * Ling et al. (2003) C. X. Ling, J. Huang, H. Zhang, et al.  Auc: a statistically consistent and more discriminating measure than accuracy.  In _Ijcai_ , volume 3, pages 519–524, 2003.
  * Maidstone et al. (2016) R. Maidstone, T. Hocking, G. Rigaill, and P. Fearnhead.  On optimal multiple changepoint algorithms for large data.  _Statistics and Computing_ , pages 1–15, 2016.  ISSN 1573-1375.
  * Mann and Whitney (1947) H. B. Mann and D. R. Whitney.  On a test of whether one of two random variables is stochastically larger than the other.  _The annals of mathematical statistics_ , pages 50–60, 1947.
  * Martínez-Camblor et al. (2017) P. Martínez-Camblor, N. Corral, C. Rey, J. Pascual, and E. Cernuda-Morollón.  Receiver operating characteristic curve generalization for non-monotone relationships.  _Statistical methods in medical research_ , 26(1):113–123, 2017.
  * Menon et al. (2013) A. Menon, H. Narasimhan, S. Agarwal, and S. Chawla.  On the statistical consistency of algorithms for binary classification under class imbalance.  In S. Dasgupta and D. McAllester, editors, _Proceedings of the 30th International Conference on Machine Learning_ , volume 28 of _Proceedings of Machine Learning Research_ , pages 603–611, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.  URL http://proceedings.mlr.press/v28/menon13a.html.
  * Narasimhan and Agarwal (2013) H. Narasimhan and S. Agarwal.  A structural svm based approach for optimizing partial auc.  In _International Conference on Machine Learning_ , pages 516–524. PMLR, 2013.
  * Provost and Fawcett (1997) F. Provost and T. Fawcett.  Analysis and visualization of classifier performance with nonuniform class and cost distributions.  In _Proceedings of AAAI-97 Workshop on AI Approaches to Fraud Detection & Risk Management_, pages 57–63, 1997.
  * Rakotomamonjy (2004) A. Rakotomamonjy.  Optimizing area under ROC curve with SVMs.  In _ROCAI_ , pages 71–80, 2004.
  * Rigaill et al. (2013) G. Rigaill, T. Hocking, J.-P. Vert, and F. Bach.  Learning sparse penalties for change-point detection using max margin interval regression.  In _Proc. 30th ICML_ , pages 172–180, 2013.
  * Rockafellar (1970) R. T. Rockafellar.  _Convex analysis_.  Princeton Mathematical Series. Princeton University Press, Princeton, N. J., 1970.
  * Rudin et al. (2005) C. Rudin, C. Cortes, M. Mohri, and R. E. Schapire.  Margin-based ranking meets boosting in the middle.  In _International Conference on Computational Learning Theory_ , pages 63–78. Springer, 2005.
  * Scott (2012) C. Scott.  Calibrated asymmetric surrogate losses.  _Electronic Journal of Statistics_ , 6(none):958 – 992, 2012.  doi: 10.1214/12-EJS699.  URL https://doi.org/10.1214/12-EJS699.
  * van den Burg and Williams (2020) G. J. van den Burg and C. K. Williams.  An evaluation of change point detection algorithms.  _arXiv preprint arXiv:2003.06222_ , 2020.
  * Wang et al. (2015) S. Wang, D. Li, N. Petrick, B. Sahiner, M. G. Linguraru, and R. M. Summers.  Optimizing area under the roc curve using semi-supervised learning.  _Pattern recognition_ , 48(1):276–287, 2015.
  * Yan et al. (2003) L. Yan, R. H. Dodier, M. Mozer, and R. H. Wolniewicz.  Optimizing classifier performance via an approximation to the Wilcoxon-Mann-Whitney statistic.  In _Proceedings of the 20th international conference on machine learning (icml-03)_ , pages 848–855, 2003.
  * Ying et al. (2016) Y. Ying, L. Wen, and S. Lyu.  Stochastic online auc maximization.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , pages 451–459, 2016.
  * Yuan et al. (2020) Z. Yuan, Y. Yan, M. Sonka, and T. Yang.  Robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification.  Preprint arXiv:2012.03173, 2020.
  * Zhao et al. (2011) P. Zhao, S. C. Hoi, R. Jin, and T. Yang.  Online AUC maximization.  In _28th international conference on machine learning_ , 2011.