# Does it pay to optimize AUC?

Baojian Zhou1, Steven Skiena2

###### Abstract

The Area Under the ROC Curve (AUC) is an important model metric for evaluating
binary classifiers, and many algorithms have been proposed to optimize AUC
approximately. It raises the question of whether the generally insignificant
gains observed by previous studies are due to inherent limitations of the
metric or the inadequate quality of optimization.

To better understand the value of optimizing for AUC, we present an efficient
algorithm, namely AUC-opt, to find the provably optimal AUC linear classifier
in $\mathbb{R}^{2}$, which runs in $\mathcal{O}(n_{+}n_{-}\log(n_{+}n_{-}))$
where $n_{+}$ and $n_{-}$ are the number of positive and negative samples
respectively. Furthermore, it can be naturally extended to $\mathbb{R}^{d}$ in
$\mathcal{O}((n_{+}n_{-})^{d-1}\log(n_{+}n_{-}))$ by calling AUC-opt in lower-
dimensional spaces recursively. We prove the problem is NP-complete when $d$
is not fixed, reducing from the open hemisphere problem.

Experiments show that compared with other methods, AUC-opt achieves
statistically significant improvements on between 17 to 40 in $\mathbb{R}^{2}$
and between 4 to 42 in $\mathbb{R}^{3}$ of 50 t-SNE training datasets.
However, generally the gain proves insignificant on most testing datasets
compared to the best standard classifiers. Similar observations are found for
nonlinear AUC methods under real-world datasets.

##  1 Introduction

The Area Under the ROC Curve (AUC) (Hanley and McNeil 1982) is an important
model evaluation metric that can be applied to a wide range of learning tasks
such as binary classification (Bradley 1997), bipartite ranking (Freund et al.
2003), and recently fairness learning (Kallus and Zhou 2019; Vogel et al.
2021). It is a generally more reliable quality measure than the accuracy when
the dataset is highly imbalanced, which often is the case in real-world
problems. Multiple studies (Cortes and Mohri 2004; Joachims 2005) argue that
optimizing classifiers for AUC may result in better classifiers than
minimizing error rates.

A wide variety of algorithms (Provost and Fawcett 2001; Ferri, Flach, and
Hernández-Orallo 2002; Yan et al. 2003; Cortes and Mohri 2004; Rakotomamonjy
2004; Herschtal and Raskutti 2004; Brefeld and Scheffer 2005; Joachims 2005;
Calders and Jaroszewicz 2007; Qin, Liu, and Li 2010; Le et al. 2010; Zhao et
al. 2011; Gao et al. 2013; Ying, Wen, and Lyu 2016; Eban et al. 2017; Liu et
al. 2020) have been proposed to optimize AUC approximately under different
learning settings. Typically, these methods relax the original nonconvex
nondifferentiable objective to either convex or differentiable. Despite these
advances, there exists no strong evidence that these algorithms generally
perform better than standard classifiers. Empirical observations
(Rakotomamonjy 2004; Joachims 2005) from previous indicate generally minor and
statistically insignificant gains on particular datasets. This vagueness makes
the question whether the observed results are due to the inherent limitations
of the metric or the inadequate quality of optimization.

To better understand the virtues of optimizing for AUC, we investigate it from
both computational and algorithmic viewpoints. Although AUC optimization is
often reported to be NP-hard for linear hypothesis classes (Gao et al. 2013;
Gao and Zhou 2015; Gultekin et al. 2020), we show that it is polynomial-time
solvable if the data dimension $d$ is fixed. We also prove that it is NP-
complete if $d$ is not fixed in advance. The key idea of our proof is a
reduction from the open hemisphere problem (Johnson and Preparata 1978).

With the hope of polynomial-time solvable of linear classifiers, we present an
efficient algorithm, namely AUC-opt, that can provably optimize AUC in
$\mathbb{R}^{2}$. A key observation is that given any $n$ training samples on
the plane, the number of “interesting” classifiers is at most
$\mathcal{O}\left(n_{+}n_{-}\right)$ where $n_{+}$ and $n_{-}$ are the number
of positive and negative samples respectively. Inspired by the idea of the
topological sweep (Edelsbrunner and Guibas 1989), we calculate the AUC for the
“minimal” slope once and then iterate through all other slopes by an ascending
order using only constant update-time per iteration, yielding an
$\mathcal{O}(n_{+}n_{-}\log n)$ algorithm. Furthermore, our method can be
naturally extended to $\mathbb{R}^{d}$ in
$\mathcal{O}((n_{+}n_{-})^{d-1}\log(n))$ by calling AUC-opt in low-dimensional
spaces recursively. This algorithm as an exponential depends on $d$ and hence
will be impractical on large real-world datasets where samples are usually
high-dimensional. Our goal here is not a general-purpose algorithm but to
address whether the observed limitations of previous AUC optimizers result
from inadequate optimization of a convex function or are an inherent result of
the AUC objective criteria. Doing such experiments requires the exact
optimization of AUC-opt, even if we are limited to small data sets in low
dimensions.

Figure 1: The popular AUC classifier SVM-Perf (Joachims 2005) fails to find a
decent AUC separator on an adversarial example (left), performing similar to
Logistic Regression (LR). The corresponding ROC curves and AUC scores (right)
for these and our AUC-opt, which beats SVM-Perf and LR by a large margin.

Fig. 1 presents a toy example as an illustration where there are significant
improvements. To further validate AUC-opt, we conduct experiments on 50 real-
world datasets projected onto both $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$ by
using t-SNE (Maaten and Hinton 2008). Experiments comparing AUC-opt against
seven linear classifiers show that AUC-opt achieves statistically significant
improvements on between 17 to 40 of 50 t-SNE datasets at the training stage.
To summarize, our main contributions are:

  * •

For the first time, we prove the linear AUC optimization problem is NP-
complete when $n$ and $d$ are arbitrary but polynomial-time solvable for fixed
$d$. A key to our proof is a reduction of the open hemisphere problem.
Although NP-hard of the problem was often reported, we have not identified
proof in the literature.

  * •

We then present AUC-opt, to find the provably optimal AUC linear classifier in
$\mathbb{R}^{2}$. It runs in $\mathcal{O}(n_{+}n_{-}\log(n_{+}n_{-}))$, which
is optimal under the algebraic computation tree model (Ben-Or 1983). It can be
naturally extended to $\mathbb{R}^{d}$ in
$\mathcal{O}((n_{+}n_{-})^{d-1}\log(n_{+}n_{-}))$ by decomposing original
problem into same subproblems of lower dimensional spaces and calling AUC-opt
recursively.

  * •

Experiments comparing AUC-opt against seven other classification methods show
that AUC-opt achieves significant improvements on between 17 to 40 in
$\mathbb{R}^{2}$ and on between 4 to 42 in $\mathbb{R}^{3}$ of 50 t-SNE
training datasets. But generally, the gain proves insignificant on most
testing datasets compared to the best standard classifiers. Empirical results
suggest that approximate AUC classifiers have space to improve.

  * •

Similarly, empirical findings on nonlinear classifiers further suggest that
the partial loss of significance of approximate AUC optimizers may be due to
imperfect approximation, thus having space to improve current approximate
algorithms.

### Related Work

AUC optimization. In the seminal work, Cortes and Mohri (2004) shows that AUC
is monotonically increasing with respect to the accuracy and is equal to the
accuracy when $n_{+}=n_{-}$. Yet, because the variance is not zero, optimizing
directly for AUC may still yield better AUC values than that of standard
classifiers. Many AUC optimization methods have been proposed over past years
(Yan et al. 2003; Herschtal and Raskutti 2004; Brefeld and Scheffer 2005;
Joachims 2005; Rakotomamonjy 2004; Calders and Jaroszewicz 2007; Ying, Wen,
and Lyu 2016; Yang and Ying 2022). These approaches all focus on approximation
due to the nonconvex and nondifferentiable of the AUC objective. To avoid
this, Yan et al. (2003) propose to replace the 0-1 objective by a sum of
differentiable sigmoid so that a gradient descent-based method can be applied.
Joachims (2005) relaxes the problem to a convex one so that SVM can be used
(see also (Rakotomamonjy 2004; Brefeld and Scheffer 2005)). A study of
Rakotomamonjy (2004) indicates that optimizing SVM objective is also attend to
optimize AUC (Rakotomamonjy 2004; Steck 2007). More recently, methods for
optimizing AUC are studied under the online learning setting (Zhao et al.
2011; Gao et al. 2013; Ying, Wen, and Lyu 2016; Liu et al. 2018). However,
performance gains are insignificant found in these studies, and there is a
lack of comparison between AUC optimizers and standard methods. Different from
these previous works, our goal is to optimize AUC score without approximation.

Bipartite ranking. The AUC optimization is closely related with the bipartite
ranking problem (Freund et al. 2003; Le et al. 2010; Qin, Liu, and Li 2010;
Rudin and Wang 2018) where minimizing the pairwise misranking error is
equivalent to maximize the AUC score. For example, RankBoost (Freund et al.
2003), a popular ranking algorithm, implicitly optimizes AUC as proved in
(Cortes and Mohri 2004). Kotłowski, Dembczyński, and Hüllermeier (2011)
consider maximizing AUC as a minimization of the rank loss. Recently, Rudin
and Wang (2018) propose to directly optimize rank statistics by using mixed-
integer programming. More works can be found in Menon and Williamson (2016)
and references therein.

Computational complexity results. Although NP-hard of the problem is often
cited as folklore (Gao et al. 2013; Gao and Zhou 2015; Gultekin et al. 2020),
we have not identified proof in the literature. Several NP-hardness results
have previously been shown for both classifications of 0-1 loss and ranking
(Feldman et al. 2012; Ben-David, Eiron, and Long 2003; Cohen, Schapire, and
Singer 1998). Cohen, Schapire, and Singer (1998) show that finding the optimal
ranking is NP-complete. Although Joachims (2005) shows that the AUC
optimization can be reformulated as a classification problem, a proof of NP-
hardness from it does not seem to follow naturally. Instead, we prove the NP-
hardness by the reduction from the open hemisphere problem.

### Paper outline and notations

The remainder of this paper is organized as follows. We first present
preliminaries in §2. The proof of NP-hardness of AUC optimization is given in
§3. AUC-opt and its generalization to high-dimensional space are given in §4.
We empirically evaluate AUC-opt and then make our conclusion in §5 and §6,
respectively. Throughout this paper, we restrict our attention to optimize AUC
in a linear hypothesis class $\mathcal{H}$ i.e.
$\bm{f}\in\mathcal{H}:=\\{\bm{w}:\bm{w}\in\mathbb{R}^{d}\\}$. Given a set of
$n$ training examples
$\mathcal{D}:=\\{(\bm{x}_{i},y_{i}):i\in\left\\{1,2,\ldots,n\right\\}\\}$
where $\bm{x}_{i}\in\mathbb{R}^{d}$ and $y_{i}\in\\{\pm 1\\}$, we rewrite
$\mathcal{D}$ as a union of $\mathcal{D}_{+}$ and $\mathcal{D}_{-}$ where
$\mathcal{D}_{+}$ is the set of positive samples written as
$\\{(\bm{x}_{1}^{+},y_{1}^{+}),\ldots,(\bm{x}_{n_{+}}^{+},y_{n_{+}}^{+})\\}$
and $\mathcal{D}_{-}$ is the set of negative samples written as
$\\{(\bm{x}_{1}^{-},y_{1}^{-}),\ldots,(\bm{x}_{n_{-}}^{-},y_{n_{-}}^{-})\\}$,
respectively. Clearly, $n=n_{+}+n_{-}$ and
$\mathcal{D}=\mathcal{D}_{+}\cup\mathcal{D}_{-}$. $x_{ij}$ is denoted as
$j$-th entry of vector $\bm{x}_{i}$, i.e.
$\bm{x}_{i}=[x_{i1},x_{i1},\ldots,x_{id}]^{\top}$.

##  2 Preliminaries

We first review the definition of AUC statistic and give the problem
formulation under linear hypothesis $\mathcal{H}$. We discuss that the problem
is efficiently solvable when $\mathcal{D}$ is separable.

######  Definition 1 (AUC Statistic (Clémençon et al. 2008)).

Let $(X,Y)$ and $(X^{\prime},Y^{\prime})$ be two pairs of random variables in
$\mathbb{R}^{d}\times\\{\pm 1\\}$ following the same unknown distribution.
Denote the probability of an event $A$ condition on $\\{Y=1,Y^{\prime}=-1\\}$
as $\mathbb{P}\\{A|Y=1,Y^{\prime}=-1\\}$. Given a score function
$\bm{f}:\mathbb{R}^{d}\mapsto\mathbb{R}$, the AUC statistic is

$\operatorname{AUC}(\bm{f}):=\mathbb{P}\\{\bm{f}(X)>\bm{f}(X^{\prime})|Y=1,Y^{\prime}=-1\\}.$

Statistically, $\operatorname{AUC}(\bm{f})$ is the probability that a randomly
chosen positive sample is ranked by $\bm{f}$ higher than a randomly chosen
negative one (tie-breaks lexicographically). It is equivalent to the Wilcoxon
statistic (Hanley and McNeil 1982). Given $\mathcal{D}$, our linear AUC
optimization is empirically defined as the following.

######  Problem 1 (Linear AUC Optimization (LAO)).

Given the dataset $\mathcal{D}$ and the hypothesis class
$\mathcal{H}:=\\{\bm{w}:\bm{w}\in\mathbb{R}^{d}\\}$, the LAO problem is to
find a $\bm{w}\in\mathcal{H}$ such that the empirical AUC score is maximized,
that is

$(\textit{LAO})\quad\bm{w}^{\star}\in\operatorname*{arg\,max}_{\bm{w}\in\mathcal{H}}\sum_{i=1}^{n_{+}}\sum_{j=1}^{n_{-}}\frac{{\bm{1}}[\bm{w}^{\top}\bm{x}_{i}^{+}>\bm{w}^{\top}\bm{x}_{j}^{-}]}{n_{+}n_{-}},$
(1)

where the indicator ${\bm{1}}[A]=1$ if $A$ is true 0 otherwise.

Due to the non-convexity of 0-1 loss in LAO, directly optimizing (1) is
challenging. Notice that $\bm{w}^{\star}$ is not unique as
$p+\alpha\bm{w}^{\star}$ with $\alpha>0$ and $p\in\mathbb{R}$ is always an
optimizer. Although (1) is hard to optimize, if $\mathcal{D}$ is linearly
separable, that is, there exists a $\bm{w}$ such that for any
$(\bm{x}_{i}^{+},y_{i}^{+})\in\mathcal{D}_{+}$,
$\left\langle\bm{w},\bm{x}_{i}^{+}\right\rangle\geq 0$ and for any
$(\bm{x}_{j}^{-},y_{j}^{-})\in\mathcal{D}_{-}$,
$\left\langle\bm{w},\bm{x}_{j}^{-}\right\rangle<0$, then one can always find a
$\bm{w}$ such that $\operatorname{AUC}(\bm{w})=1$ in polynomial-time (Elizondo
2006; Yogananda, Murty, and Gopal 2007) by using Perceptron (Freund and
Schapire 1999) or linear programming techniques. For example, the worst time
complexity of an iterative reduction algorithm is $\mathcal{O}(nr^{3})$ where
$r\leq\min(n,d+1)$ (Elizondo 2006). In the rest of this paper, we assume
$\mathcal{D}$ is not linearly separable.

Although previous studies have claimed the NP-hardness of LAO (Gao et al.
2013; Gao and Zhou 2015; Gultekin et al. 2020), no previous literature proves
it even for the linear classifier case. It motivates us to prove the NP-
hardness under the linear hypothesis.

##  3 NP-hardness of LAO

This section proves the LAO problem under the linear hypothesis is NP-complete
if $n$ and $d$ are not fixed but polynomial-time solvable when $d$ is fixed.
We first introduce the open hemisphere problem and then prove the NP-complete
by a reduction from it.

######  Definition 2 (Open hemisphere).

Given the unit sphere
$\mathcal{S}^{d-1}:=\\{\bm{s}\in\mathbb{R}^{d}:\|\bm{s}\|_{2}=1\\}$, the open
hemisphere of $\bm{w}$ is defined as a set
$\\{\bm{s}\in\mathcal{S}^{d-1}:\left\langle\bm{w},\bm{s}\right\rangle>0\\}$.

######  Problem 2 (Open hemisphere problem (Johnson and Preparata 1978)).

Let $\mathcal{K}:=\\{\bm{s}_{1},\bm{s}_{2},\ldots,\bm{s}_{t}\\}$ be a subset
of $\mathbb{Q}^{d}\cap\mathcal{S}^{d-1}$ where $\mathbb{Q}$ is the set of
rationals. The open hemisphere problem is to find an open hemisphere such that
it contains a largest subset of $\mathcal{K}$, that is,

$\operatorname*{arg\,max}_{\bm{w}\in\mathbb{R}^{d}}|\\{\bm{s}_{i}\in\mathcal{K}:\left\langle\bm{w},\bm{s}_{i}\right\rangle>0\\}|.$

To ease our analysis, we formulate the open hemisphere problem as a
feasibility problem. Given positive integers $d$, $m$ and a set $\mathcal{K}$,
does there exist a hyperplane $\bm{w}$ such that at least $m$ inequalities are
satisfied, that is,

$(\textit{OH})\qquad|\\{\bm{s}_{i}\in\mathcal{K}:\left\langle\bm{w},\bm{s}_{i}\right\rangle>0\\}|\geq
m\ ?$ (2)

######  Lemma 1 (NP-complete of OH (Johnson and Preparata 1978)).

Given positive $d$, $n$, $m$, and
$\mathcal{K}\subseteq\mathbb{Q}^{d}\cap\mathcal{S}^{d-1}$, the feasibility of
OH problem defined in (2) is NP-complete when both $n$ and $d$ are not fixed.

The above lemma shows the fact that OH is NP-complete. Based on this lemma, we
have the following main theorem.

######  Theorem 1 (NP-complete of LAO).

Consider the linear AUC optimization problem defined in Problem 1, if
$\mathcal{D}$ is not linear separable, LAO is NP-complete when both $n$ and
$d$ are arbitrary.

Before proving Thm. 1, we first reformulate the LAO problem as a feasibility
problem and then show this feasibility problem is NP-complete.

######  Problem 3 (The feasibility problem of LAO).

Given a finite dataset $\mathcal{D}$, a set of linear classifiers
$\mathcal{H}$, and positive integers $d,t$ as an input, the feasibility
problem of LAO is to ask, does there exist $\bm{w}\in\mathcal{H}$ such that

$\sum_{i=1}^{n_{+}}\sum_{j=1}^{n_{-}}{\bm{1}}[\bm{w}^{\top}\bm{x}_{i}^{+}>\bm{w}^{\top}\bm{x}_{j}^{-}]\geq
t\ ?$ (3)

Proof Sketch.111A detailed proof is in the supplementary. Without loss of
generality, let us assume the problem in $\mathbb{Q}^{d}$. To prove the NP-
complete, we only need to show that the feasibility of LAO defined in Problem
3 is both in NP and is NP-hard by a reduction from OH. First of all, Problem 3
is in NP. Given any $\bm{w}\in\mathcal{H}$, one can find a polynomial-time
verifier such that it finishes in $\mathcal{O}(n_{p}n_{q}d)$ time, and each
certificate has a polynomial length for the input.

To show Problem 3 is NP-hard, given any instance of the OH problem, the goal
is to prove that an instance of (3) can solve it. To do this, we construct the
training dataset $\mathcal{D}$ so that an instance of Problem 3 can be
defined. Notice that one can rewrite vectors in $\mathcal{K}$ and construct
new vectors $\bm{x}_{i}^{+}$ and $\bm{x}_{1}^{-}$ as the following

$\displaystyle\bm{s}_{1}=\underbrace{(\bm{s}_{1}+\bm{x}_{1}^{-})}_{\bm{x}_{1}^{+}}-\bm{x}_{1}^{-},\ldots,\bm{s}_{t}=\underbrace{(\bm{s}_{t}+\bm{x}_{1}^{-})}_{\bm{x}_{t}^{+}}-\bm{x}_{1}^{-}.$
(4)

The set of training labels is constructed such that
$y_{1}^{+},y_{2}^{+},\ldots,y_{t}^{+}$ are all ones and $y_{1}^{-}=-1$.
Combining it with equations in (4) provides a dataset
$\mathcal{D}=\\{(\bm{x}_{1}^{+},y_{1}^{+}),\ldots,(\bm{x}_{t}^{+},y_{t}^{+}),(\bm{x}_{1}^{-},y_{1}^{-})\\}$.
The left two figures illustrate this reduction where the top figure is a
sphere, and each positive sign represents $\bm{s}_{i}$ while the negative sign
is $\bm{x}_{1}^{-}=\bm{0}$. The sphere contains 14 points, which correspond to
14 inequalities of the left-hand side of (3). The normal $\bm{w}$ defines a
hyperplane which corresponds to $t=8$ of the right-hand side of (3). The
bottom figure shows an AUC curve where TPR and FPR are true positive rate and
false positive rate, respectively. It indicates that there exists $\bm{w}$
such that the number of inequalities that can be satisfied is at least $m$.
This transformation and checking procedure can be done in polynomial-time.
Therefore, any answer of the instance of LAO is affirmative if and only if the
instance of OH is affirmative; hence, the problem is NP-hard. $\blacksquare$

##  4 Proposed methods for LAO

In this section, we first present a trivial method in $\mathbb{R}^{2}$ and
then propose AUC-opt inspiring from topological sweeping. We then extend AUC-
opt to $\mathbb{R}^{d}$ by projecting high-dimensional problems into low-
dimensional ones.

### A trivial method

Notice that every pair of training samples defines a supporting line that
separates the rest training samples, and the number of these interesting lines
are at most $\mathcal{O}(n^{2})$. Given any two sample
$\bm{x}_{i}:=[x_{i1},x_{i2}]^{\top}$ and $\bm{x}_{j}:=[x_{j1},x_{j2}]^{\top}$,
the slope of the line defined by $\bm{x}_{i}$ and $\bm{x}_{j}$ is
$m=-(x_{i2}-x_{j2})/(x_{i1}-x_{j1})$. Hence, one can find an algorithm runs in
$\mathcal{O}(n^{3}\log n)$ and takes $\mathcal{O}(n^{2})$ space by using the
following two steps: 1) identify all $n(n-1)$ slopes $m$; and 2) for each
slope $m$, let $\bm{w}:=[m,1]^{\top}$ and then calculate
$\operatorname{AUC}(\bm{w})$ by using an $\mathcal{O}(n\log n)$ algorithm
(Fawcett 2006). $\bm{w}^{\star}$ is the one that gives the highest
$\operatorname{AUC}(\bm{w})$ value.

### AUC-opt

However, the above trivial method can be significantly improved. There are two
successive algorithmic improvements needed. The first is that the number of
interesting slopes is at most $\mathcal{O}(n_{+}n_{-})$ by noticing that
training pairs with the same labels are not interesting. The second
improvement is inspired by the topological sweep (Edelsbrunner and Guibas
1989) that we can save $n$ running time by sorting all slopes once; that is,
we only need to calculate the AUC score once for the minimal slope and then
sweep over all the rest of the slopes in ascending order.

Algorithm 1 $[\operatorname{AUC}_{\operatorname{opt}},\bm{w}]=$AUC-
opt($\mathcal{D}$)

1: $S=\\{\\}$ $\triangleright$ Initialize a slope set

2: for $(i,j)\in\\{1,\ldots,n_{+}\\}\times\\{1,\ldots,n_{-}\\}$ do

3: $m=-(x_{i2}^{+}-x_{j2}^{-})/(x_{i1}^{+}-x_{j1}^{-})$ $\triangleright$
Calculate a slope

4: $S=S\cup\\{(m,i,j)\\}$

5: end for

6: Let
$\epsilon<\min_{(i,j)\neq(i^{\prime},j^{\prime})}\left|\frac{x_{i2}-x_{j2}}{x_{i1}-x_{j1}}-\frac{x_{i^{\prime}2}-x_{j^{\prime}2}}{x_{i^{\prime}1}-x_{j^{\prime}1}}\right|$
be a positive constant smaller than the minimal difference between any two
slopes.

7: Let $\min(S)=\min\\{m|(m,i,j)\in S\\}$

8: $\bm{w}=[\min(S)-1,1]^{\top}$

9: $\operatorname{AUC}_{\operatorname{cur}}=\operatorname{AUC}(\bm{w})$
$\triangleright$ Algo. 1 in Fawcett (2006)

10:
$\operatorname{AUC}_{\operatorname{opt}}=\operatorname{AUC}_{\operatorname{cur}}$

11: for $(m,i,j)\in\text{sort}(S)$ do

12:
$c_{1}=0,c_{2}=0,\bm{u}=[m-\epsilon,1]^{\top},\bm{v}=[m+\epsilon,1]^{\top}$

13: if $\bm{u}^{\top}\bm{x}_{i}^{+}>\bm{u}^{\top}\bm{x}_{j}^{-}$ then
$c_{1}=1$

14: if $\bm{v}^{\top}\bm{x}_{i}^{+}>\bm{v}^{\top}\bm{x}_{j}^{-}$ then
$c_{2}=1$

15:
$\operatorname{AUC}_{\operatorname{cur}}=\operatorname{AUC}_{\operatorname{cur}}+(c_{2}-c_{1})/(n_{+}n_{-})$

16: if
$\operatorname{AUC}_{\operatorname{opt}}<\operatorname{AUC}_{\operatorname{cur}}$
then

17:
$\operatorname{AUC}_{\operatorname{opt}}=\operatorname{AUC}_{\operatorname{cur}}$,
$\bm{w}=[m+\epsilon,1]^{\top}$

18: end if

19: if
$\operatorname{AUC}_{\operatorname{opt}}<1-\operatorname{AUC}_{\operatorname{cur}}$
then

20:
$\operatorname{AUC}_{\operatorname{opt}}=1-\operatorname{AUC}_{\operatorname{cur}}$,
$\bm{w}=[-m-\epsilon,-1]^{\top}$

21: end if

22: end for

The description of AUC-opt is presented in Algo. 1. There are three main
steps: 1) to obtain all possible slopes and store into $S$ (L1 to L5); 2) to
calculate the AUC score of the minimal slope (L7 to L9); and 3) to update
$\bm{w}$ and its AUC score (L10 to L21). The critical part is the update rules
of sweeping $\bm{w}$. More specifically, at each iteration (from L10 to L21),
the change of AUC score is from $\\{0,\pm 1/(n_{+}n_{-})\\}$ by “sweeping”
$\bm{w}$ (L10 - L13). We illustrate this procedure on the upper right figure
where red plus signs are positives while blue bar signs are negatives. Let
$\bm{w}=[s,1]^{\top},\bm{w}_{-}=[s-\epsilon,1]^{\top}$, and
$\bm{w}_{+}=[s+\epsilon,1]^{\top}$. The increase of slope from $\bm{w}_{-}$ to
$\bm{w}_{+}$ only changes the ordering of two samples which corresponds to a
magnitude change of $|1/(n_{+}n_{-})|$ for $\operatorname{AUC}(\bm{w})$. The
following theorem shows $\bm{w}$ returned by Algo. 1 is optimal.

######  Theorem 2.

Given the dataset
$\mathcal{D}:=\\{(\bm{x}_{i},y_{i}):i\in\left\\{1,2,\ldots,n\right\\}\\}$
where $\bm{x}_{i}\in\mathbb{R}^{2}$ and $y_{i}\in\\{\pm 1\\}$ and a collection
of linear separators $\mathcal{H}:=\\{\bm{w}:\bm{w}\in\mathbb{R}^{2}\\}$. The
proposed $\operatorname{AUC}$-$\operatorname{opt}$, solves the LAO problem (1)
in $\mathcal{O}(n_{+}n_{-}\log(n_{+}n_{-}))$. This time complexity is tight
under the algebraic computation tree model.

###### Proof.

We first show that $\bm{w}$ returned by AUC-opt is optimal. The key of our
proof is to show that Algo. 1 iterates all possible AUC scores given by
noticing that all slopes of lines between two consecutive slopes give the same
AUC score.

Let $\bm{w}=[w_{1},w_{2}]^{\top}$ be any line in $\mathbb{R}^{2}$. We assume
that $\bm{w}$ is a normal vector of two training samples
$\bm{x}_{i}^{+},\bm{x}_{j}^{-}$, that is, $\bm{w}$ is given by
$\langle\bm{w},\bm{x}_{i}^{+}-\bm{x}_{j}^{-}\rangle=0$. The slopes of these
normal vectors on $\mathbb{R}^{2}$ can be calculated. Let the collection of
all such slopes be
$\mathcal{S}:=\left\\{-(x_{i2}^{+}-x_{j2}^{-})/(x_{i1}^{+}-x_{j1}^{-}):\bm{x}_{i}^{+},\bm{x}_{j}^{-}\in\mathcal{D}\right\\}$.
Sort the collection of slopes $\mathcal{S}$ and $\mathbb{R}^{2}$ has been
partitioned into $n_{+}n_{-}+1$ parts.

We consider two consecutive slopes in the sorted $\mathcal{S}$ more carefully.
Let us denote two consecutive sorted slopes as $s_{1}$ and $s_{2}$ which
associated with two pairs $(\bm{x}_{i}^{+},\bm{x}_{j}^{-})$ and
$(\bm{x}_{{i^{\prime}}}^{+},\bm{x}_{{j^{\prime}}}^{-})$, respectively. We only
need to show that $\forall s\in(s_{1},s_{2}),[s,1]^{\top}$ has identical AUC
score. To do so, all we need to do is to show that given any
$\bm{x}_{i}^{+},\bm{x}_{j}^{-}$, $\bm{w}$ scores
$\bm{x}_{i}^{+},\bm{x}_{j}^{-}$ as a same ordering. In other words, given any
$\bm{w}:=\\{[s,1]^{\top}:s\in(s_{1},s_{2})\\}$, the quantity
$\bm{x}_{i}^{\top}\bm{w}-\bm{x}_{j}^{\top}\bm{w}$ always has same sign. In the
rest proof, we show this by carefully constructing a quantity function
$s(\lambda)$ as the following

$s(\lambda):=-\frac{x_{i2}^{+}-x_{j2}^{-}}{x_{i1}^{+}-x_{j1}^{-}}\lambda-\frac{x_{{i2}^{\prime}}^{+}-x_{{j2}^{\prime}}^{-}}{x_{{i1}^{\prime}}^{+}-x_{{j1}^{\prime}}^{-}}(1-\lambda),$

where $\lambda\in(0,1)$.

We need to study the monotonicity of $s(\lambda)$, we define another function
$h(\lambda):=s(\lambda)\left(x_{i1}-x_{j1}\right)+x_{i2}-x_{j2}$. Clearly,
$h(\lambda)$ is non-decreasing function by noticing that
$h^{\prime}(\lambda)=s_{2}-s_{1}\geq 0$. We just need to show $h(\lambda)$
never vanishes at $\lambda\in(0,1)$. Assume that we have $h(\lambda)=0$, then
we have $s(\lambda)=-(x_{i2}-x_{j2})/(x_{i1}-x_{j1})$. It makes a
contradiction since there is no existing slope between $s_{1}$ and $s_{2}$.
Similarly, one can show that for any two consecutive slopes $s_{1},s_{2}$,
$\forall s\in(s_{1},s_{2}),\bm{w}:=[-s,-1]^{\top}$, also defines the same AUC
score. Since Algo. 1 iterates all such lines, the best AUC score of $\bm{w}$
returned by AUC-opt is indeed optimal.

AUC-opt finishes in $\mathcal{O}(n_{+}n_{-}\log(n_{+}n_{-}))$ since the time
complexity is dominated by sorting all $n_{+}n_{-}$ slopes (L10). The
tightness of time complexity follows by Lemma 3.6.16 of Lee and Preparata
(1984). ∎

### Generalization to $\mathbb{R}^{d}$

When problem dimension $d\geq 3$, inspired from Johnson and Preparata (1978),
the general idea of solving high-dimensional LAO problem is that one can
decompose the original $d$ dimensional problem into several $d-1$ subproblems.
Notice that each hyperplane $H(\bm{u})$ uniquely defines an interesting
subspace, and there are at most $n_{+}n_{-}$ such subspaces. We project points
onto $H(\bm{u})$ and then solve problem in $d-1$ dimensional subspace
(changing the number of coordinates from $d$ to $d-1$), recursively.
Specifically, let the projection be defined as
$\bm{P}(\bm{x}):=\bm{x}-(\bm{x}^{\top}\cdot\bm{u}/\|\bm{u}\|^{2})\cdot\bm{u}$
where $\bm{u}$ is the normal vector of $H(\bm{u})$. The critical property of
$\bm{P}$ is that for any $\bm{x}\in H(\bm{u})$,
$\bm{x}^{\top}\bm{P}(\bm{x}_{i}^{+}-\bm{x}_{j}^{-})=\bm{x}^{\top}(\bm{x}_{i}^{+}-\bm{x}_{j}^{-})$.
Therefore, the inner products of training samples with $\bm{w}$ are the same
as those of projected training samples.

Due to this inevitable recursion, the number of interesting hyperplanes
exponentially depends upon $d$; hence time complexity of AUC-opt in
$\mathbb{R}^{d}$ is
$\mathcal{O}\left((n_{p}n_{q})^{d-1}\log(n_{p}n_{q})\right)$. We summarize
this recursive procedure in Algo. 2. Due to the space limitation, detailed
algorithm description is in the supplementary.

Algorithm 2 $[\operatorname{AUC}_{\operatorname{opt}},\bm{w}]=$AUC-
opt($\mathcal{D},d$)

1:
$\mathcal{K}=\\{(\bm{x}_{i}^{+}-\bm{x}_{j}^{-}):i\in\\{1,\ldots,n_{+}\\},j\in\\{1,\ldots,n_{-}\\}\\}$

2: if d=2 then

3: return $\operatorname{AUC}_{cur},\bm{w}^{\prime}=\operatorname{AUC-
opt}(\mathcal{D})$ $\triangleright$ call Algo. 1

4: end if

5: for $\bm{u}\in\mathcal{K}$ do

6:
$\mathcal{P}=\left\\{\left(\bm{x}-\frac{\bm{x}^{\top}\cdot\bm{u}}{\|\bm{u}\|^{2}}\cdot\bm{u},y\right):(\bm{x},y)\in\mathcal{D}\right\\}$
$\triangleright$ project points of $\mathcal{D}$ onto the hyperplane defined
by $\bm{u}$.

7: $\mathcal{P}^{\prime}=\operatorname{change\\_coordinates}(\mathcal{P})$
$\triangleright$ change coordinates so that points are presented in $d-1$
coordinates.

8: $\operatorname{AUC}_{cur},\bm{w}^{\prime}=\operatorname{AUC-
opt}(\mathcal{P}^{\prime},d-1)$

9: $\bm{w}=\operatorname{change\\_coordinates}(\bm{w}^{\prime})$
$\triangleright$ change $d-1$ coordinates of $\bm{w}^{\prime}$ back to $d$
coordinates.

10: if
$\operatorname{AUC}_{\operatorname{opt}}<\operatorname{AUC}_{\operatorname{cur}}$
then

11: $\bm{w}^{\star}=\bm{w}$,
$\operatorname{AUC}_{\operatorname{opt}}=\operatorname{AUC}_{\operatorname{cur}}$

12: end if

13: end for

######  Theorem 3.

Given the dataset
$\mathcal{D}:=\\{(\bm{x}_{i},y_{i}):i\in\left\\{1,2,\ldots,n\right\\}\\}$
where $\bm{x}_{i}\in\mathbb{R}^{d}$ and $y_{i}\in\\{\pm 1\\}$ and a collection
of linear separators $\mathcal{H}:=\\{\bm{w}:\bm{w}\in\mathbb{R}^{d}\\}$.
There exists an algorithm solves the LAO problem (1) exactly in
$\mathcal{O}\left((n_{+}n_{-})^{d-1}\log(n_{+}n_{-})\right)$.

###### Proof.

The proof is in the supplementary. ∎

Table 1: The comparison of AUC scores over 200 trials of 50 t-SNE datasets on both $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$. Each cell (I,J) means the number of datasets where method I is significantly better than method J by using t-test with a significance level of 5%. Numbers in the red region are results of AUC optimizers better than standard classifiers, while numbers in the blue region are the reverse. |  |  SVM |  B-SVM |  LR |  B-LR |  SVM-Perf |  SPAUC |  SPAM |  AUC-opt |  SVM |  B-SVM |  LR |  B-LR |  SVM-Perf |  SPAUC |  SPAM |  AUC-opt
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
|  | Significance t-test ($\alpha=0.05$) on training | Significance t-test ($\alpha=0.05$) on testing
|  SVM |  - |  0 |  1 |  1 |  3 |  0 |  1 |  0 |  - |  0 |  0 |  0 |  3 |  0 |  1 |  1
|  B-SVM |  30 |  - |  7 |  4 |  27 |  3 |  3 |  0 |  31 |  - |  7 |  4 |  23 |  3 |  3 |  1
|  LR |  31 |  11 |  - |  2 |  27 |  2 |  5 |  0 |  32 |  14 |  - |  2 |  26 |  2 |  5 |  2
|  B-LR |  32 |  15 |  6 |  - |  30 |  2 |  4 |  0 |  33 |  16 |  6 |  - |  29 |  3 |  4 |  2
$d=2$ |  SVM-Perf |  16 |  2 |  0 |  0 |  - |  0 |  1 |  0 |  16 |  2 |  0 |  1 |  - |  1 |  2 |  2
|  SPAUC |  31 |  14 |  8 |  2 |  28 |  - |  2 |  0 |  29 |  12 |  7 |  3 |  26 |  - |  4 |  2
|  SPAM |  33 |  10 |  9 |  3 |  29 |  1 |  - |  0 |  32 |  11 |  6 |  3 |  26 |  1 |  - |  2
|  AUC-opt |  40 |  29 |  20 |  17 |  40 |  21 |  26 |  - |  34 |  18 |  15 |  11 |  31 |  13 |  17 |  -
|  SVM |  - |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  - |  0 |  0 |  0 |  1 |  1 |  0 |  1
|  B-SVM |  25 |  - |  0 |  0 |  24 |  0 |  0 |  0 |  24 |  - |  1 |  1 |  20 |  4 |  3 |  3
|  LR |  34 |  6 |  - |  0 |  32 |  5 |  7 |  0 |  38 |  14 |  - |  1 |  34 |  10 |  12 |  8
|  B-LR |  34 |  6 |  0 |  - |  32 |  7 |  9 |  0 |  36 |  12 |  0 |  - |  33 |  9 |  11 |  6
$d=3$ |  SVM-Perf |  1 |  0 |  0 |  0 |  - |  0 |  0 |  0 |  1 |  0 |  0 |  0 |  - |  1 |  2 |  3
|  SPAUC |  24 |  0 |  0 |  0 |  27 |  - |  0 |  0 |  24 |  3 |  0 |  1 |  22 |  - |  1 |  3
|  SPAM |  26 |  0 |  0 |  0 |  23 |  0 |  - |  0 |  25 |  2 |  0 |  0 |  21 |  2 |  - |  2
|  AUC-opt |  42 |  31 |  6 |  4 |  41 |  27 |  33 |  - |  32 |  15 |  2 |  2 |  32 |  9 |  10 |  -

##  5 Experiments

We evaluate AUC-opt on both $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$ by using
t-SNE datasets. To confirm that AUC-opt produces the best possible linear AUC
classifiers, we compare it with 7 other classifiers on the binary
classification task at the training and testing stage. Furthermore, we compare
the approximate AUC methods with other standard methods for nonlinear
classifiers. More results and experimental details, including data collection,
baseline description, and parameter tuning, are in the supplementary.222Our
code can be found in https://github.com/baojian/auc-opt

### Datasets and experimental setup

#### Datasets.

We collect 50 real-world datasets where the positive ratio ($n_{p}/n$) of most
datasets are $\leq 0.1$. These highly imbalanced datasets make optimizing AUC
problem meaningful. To generate 2 and 3 dimensional samples, we project
samples of these datasets onto $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$
respectively using t-SNE (Maaten and Hinton 2008) so that class patterns are
conserved. Models use projected points as training samples while keep labels
unchanged.

Experimental setup. For each dataset, 50% samples are for training and the
rest for testing. All parameters are tuned by 5-fold cross-validation. Each
dataset is randomly shuffled 200 times, and the reported results are averaged
on 200 trials. All methods have been tested on servers with Intel(R) Xeon(R)
CPU (2.30GHz) 64 cores and 187G memory. For all methods that involve
randomness, the random state has been fixed for the purpose of
reproducibility.

Baselines. We consider the following baseline classifiers: 1) Logistic
Regression (LR); 2) B-LR. Balanced Logistic Regression (B-LR). We adjust
weights of samples inversely proportional to class frequencies so that it can
have better performance on imbalanced datasets; 3) Support-vector Machine
(SVM); 4) B-SVM. The balanced SVM (B-SVM) uses the same strategy as B-LR; 5)
SVM-Perf. The SVM-Perf algorithm is proposed in Joachims (2005) where the goal
is to minimize the AUC loss by using SVM-based method; 6) SPAUC. The
Stochastic Proximal AUC (SPAUC) maximization algorithm is proposed in Lei and
Ying (2019); 7) SPAM. The Stochastic Proximal AUC Maximization (SPAM)
algorithm is proposed in Natole, Ying, and Lyu (2018).

### Results on t-SNE datasets

Table 2: The comparison of testing AUC scores of 50 real-world datasets. The settings are the same as in Table 1. |  SVM |  B-SVM |  LR |  B-LR |  RF |  B-RF |  GB |  SVM-RBF |  B-SVM-RBF |  RankBoost |  AdaBoost |  SPAM |  SPAUC |  SVM-Perf |  Average
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
SVM |  - |  4 |  2 |  3 |  10 |  9 |  15 |  19 |  8 |  15 |  17 |  29 |  30 |  3 |  12.62
B-SVM |  22 |  - |  6 |  4 |  15 |  12 |  18 |  21 |  12 |  15 |  19 |  36 |  38 |  20 |  18.31
LR |  31 |  21 |  - |  5 |  17 |  14 |  19 |  23 |  14 |  18 |  20 |  38 |  38 |  29 |  22.08
B-LR |  31 |  23 |  8 |  - |  17 |  14 |  19 |  23 |  14 |  19 |  21 |  37 |  37 |  28 |  22.38
RF |  34 |  30 |  31 |  31 |  - |  6 |  34 |  29 |  19 |  34 |  38 |  39 |  37 |  34 |  30.46
B-RF |  36 |  33 |  31 |  31 |  19 |  - |  33 |  32 |  19 |  35 |  37 |  38 |  36 |  35 |  31.92
GB |  31 |  29 |  29 |  29 |  12 |  13 |  - |  25 |  17 |  26 |  30 |  36 |  38 |  32 |  26.69
SVM-RBF |  27 |  26 |  26 |  27 |  16 |  15 |  21 |  - |  6 |  23 |  23 |  30 |  31 |  27 |  22.92
B-SVM-RBF |  36 |  32 |  32 |  32 |  24 |  22 |  29 |  20 |  - |  31 |  33 |  39 |  38 |  37 |  31.15
RankBoost |  32 |  31 |  29 |  29 |  9 |  8 |  16 |  24 |  13 |  - |  35 |  38 |  38 |  33 |  25.77
AdaBoost |  31 |  29 |  26 |  27 |  7 |  8 |  9 |  22 |  12 |  3 |  - |  37 |  35 |  31 |  21.31
SPAM |  13 |  4 |  2 |  2 |  7 |  7 |  12 |  18 |  7 |  8 |  12 |  - |  27 |  15 |  10.31
SPAUC |  6 |  3 |  2 |  1 |  9 |  7 |  10 |  17 |  7 |  10 |  10 |  10 |  - |  8 |  7.69
SVM-Perf |  3 |  10 |  4 |  5 |  9 |  8 |  15 |  16 |  7 |  13 |  16 |  25 |  28 |  - |  12.23

(a) Mean of training AUC

(b) Mean of testing AUC

(c) Variance of training AUC

(d) Variance of testing AUC

Figure 2: Mean and Variance of AUC scores of eight classifiers over 50 t-SNE
datasets in $\mathbb{R}^{2}$.

Comparison of AUC scores. Table 1 presents the comparison of AUC scores
calculated on both training and testing datasets in $\mathbb{R}^{2}$ and
$\mathbb{R}^{3}$. To compare AUC scores from different methods, for the method
I and J on a specific dataset, we calculate whether I is significantly better
than J in a statistical sense. Important observations are: 1) AUC-opt achieves
more significant gains over standard classifiers than the approximate AUC
optimizers on the training stage. It confirms that gaps between AUC-opt and
other approximate AUC optimizers are significant on some datasets; 2) Compared
with SVM and LR, balanced versions of SVM (B-SVM) and LR (B-LR) have better
performance. We see that the simple weighting strategy improves the
performance by adjusting the weights on training samples;333The balanced
version of a classifier is that a class weight has been added for each sample.
Specifically, weight $n/(2*n_{p})$ is for each positive sample while weight
$n/(2*n_{q})$ is for each negative sample. and 3) Compared with the best
standard classifier B-LR, AUC-opt produces significant gains on 17 training
datasets while reduced to 11 on testing datasets. It is worse in
$\mathbb{R}^{3}$. This degradation happens mainly because results of B-LR are
tuned by adding regularization hence better generalization ability, while AUC-
opt does not. With regularization, B-LR has better generalization performance
on testing datasets but regularization is not taking into consideration in our
method. Under $\mathbb{R}^{3}$, AUC-opt only beats 4 datasets over B-LR, the
best classifier. It means that the gain proves insignificant on most datasets.

We also report the mean with the Friedman Rank and variance of AUC scores in
Fig. 2. The Friedman Rank and averaged AUC scores shown in Fig. 2 (a) and (b)
present that superiority of AUC-opt on optimizing AUC score. Variances of AUC
shown in (c) and (d) indicate that 0-1 objective optimization (AUC-opt) is
more robust, while SVMs are not. Yet, the performance of SVM-Perf is better
than SVM but not B-SVM.

Method |  Run Time
---|---
SVM |  0.1918 $\displaystyle\pm$ 0.4667
B-SVM |  0.2862 $\displaystyle\pm$0.5205
LR |  0.0785 $\displaystyle\pm$ 0.0489
B-LR |  0.0781 $\displaystyle\pm$0.0491
SPAM |  3.3675 $\displaystyle\pm$ 6.6170
SPAUC |  3.3826 $\displaystyle\pm$ 6.7024
SVM-Perf |  8.9185 $\displaystyle\pm$ 14.691
AUC-opt |  3.7073 $\displaystyle\pm$ 7.4934

Run time. The left table shows the comparison of the averaged run time (in
seconds) over all datasets. The run time of AUC optimizers is slower than
standard classifiers. This is because the objective of AUC optimizers is the
sum of the loss of training example pairs, which makes them
$\mathcal{O}(n^{2})$ per batch while AUC-opt uses less on average compared
with SVM-Perf.

Comparison of other metrics. As presented in our supplementary, an interesting
observation is that AUC optimizers obtain better performance on balanced
accuracy and F1-score than the more traditional classifiers. Results are
consistent with the findings shown in Narasimhan and Agarwal (2013) where an
AUC optimizer is a good way to construct a good balanced classifier. The
performance of LR is good on AUC, but not on balanced accuracy and F1 score.

### Results on real-world datasets

We test both the approximate AUC optimizers and the standard classification
methods on 50 real-world datasets. The AUC scores on testing are reported in
Table 2. First, Balanced Random Forest (B-RF) and Balanced SVM-RBF (B-SVM-RBF)
prove the best overall on testing AUC scores. It wins 31.92 and 31.15 datasets
on average respectively. This performance is consistent with findings shown in
both Fernández-Delgado et al. (2014) and Couronné, Probst, and Boulesteix
(2018). Furthermore, a relationship between RF and LR has been studied in
Couronné, Probst, and Boulesteix (2018) where it has been shown that RF can
obtain much higher AUC scores compared with LR. Boosting-based methods such as
AdaBoost444We treat AdaBoost as the AUC-based method because theoretical
finding indicates that AdaBoost is equivalent to RankBoost. and Gradient Boost
(GB) also work well.

RankBoost is inferior to RF and B-RF, winning on only 9 and 8 datasets,
respectively. The performance of AdaBoost and RankBoost prove competitive with
each other. This has been theoretically justified in Rudin and Schapire
(2009). However, interestingly, RankBoost still outperforms AdaBoost over 35
datasets in the testing stage. Gradient Boost (GB) wins more datasets than
RankBoost. Generally speaking, two nonlinear AUC optimizers are inferior to
these popular nonlinear standard classifiers. This clearly suggests that
approximate AUC optimizers may not lead to the best AUC performance, hence
having space to improve. All linear methods lose on average to non-linear
ones.

##  6 Conclusion and future work

Our complexity results show linear AUC optimization is NP-complete via
reduction to the open hemisphere problem. It remains interesting to prove the
hardness results for other hypothesis classes mentioned in Ben-David, Eiron,
and Long (2003). We then present an optimal method AUC-opt that is both time
and space-efficient for optimizing AUC in $\mathbb{R}^{2}$. We demonstrate
that it can be naturally extended to $\mathbb{R}^{d}$ with a total cost
$\mathbb{O}((n_{+}n_{-})^{d-1}\log(n_{+}n_{-}))$. Our empirical results
suggest that to justify the objective to optimize AUC, more effort may be
needed to improve the optimization quality of AUC optimizers.

AUC-opt is impractical for real-world datasets since the time complexity is
exponentially getting worse with the dimension $d$. However, it remains
interesting to see whether more efficient algorithms exist for higher but
still moderate dimensionality. One potential direction is to use branch and
bound as explored in Nguyen and Sanner (2013). It is also interesting to
compare our method with Rudin and Wang (2018), a recently proposed method that
directly optimizes a rerank statistic.

##  7 Acknowledgments

The authors would like to thank anonymous reviewers for their valuable
comments. The work of Baojian Zhou is partially supported by startup funding
from Fudan University. Steven Skiena was partially supported by NSF grants
IIS-1926781, IIS-1927227, IIS-1546113, OAC-191952, and a New York State Empire
Innovation grant.

## References

  * Ben-David, Eiron, and Long (2003) Ben-David, S.; Eiron, N.; and Long, P. M. 2003.  On the difficulty of approximately maximizing agreements.  _Journal of Computer and System Sciences_ , 66(3): 496–514.
  * Ben-Or (1983) Ben-Or, M. 1983.  Lower bounds for algebraic computation trees.  In _Proceedings of the 15th Annual ACM Symposium on Theory of Computing_ , 80–86.
  * Bradley (1997) Bradley, A. P. 1997.  The use of the area under the ROC curve in the evaluation of machine learning algorithms.  _Pattern Recognition_ , 30(7): 1145–1159.
  * Brefeld and Scheffer (2005) Brefeld, U.; and Scheffer, T. 2005.  AUC maximizing support vector learning.  In _Proceedings of the ICML 2005 workshop on ROC Analysis in Machine Learning_.
  * Breiman (2001) Breiman, L. 2001.  Random forests.  _Machine learning_ , 45(1): 5–32.
  * Calders and Jaroszewicz (2007) Calders, T.; and Jaroszewicz, S. 2007.  Efficient AUC optimization for classification.  In _European Conference on Principles of Data Mining and Knowledge Discovery_ , 42–53. Springer.
  * Chang and Lin (2011) Chang, C.-C.; and Lin, C.-J. 2011.  LIBSVM: A library for support vector machines.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 2(3): 1–27.
  * Clémençon et al. (2008) Clémençon, S.; Lugosi, G.; Vayatis, N.; et al. 2008.  Ranking and empirical minimization of U-statistics.  _The Annals of Statistics_ , 36(2): 844–874.
  * Cohen, Schapire, and Singer (1998) Cohen, W. W.; Schapire, R. E.; and Singer, Y. 1998.  Learning to order things.  In _NIPS_ , 451–457.
  * Cortes and Mohri (2004) Cortes, C.; and Mohri, M. 2004.  AUC optimization vs. error rate minimization.  In _NIPS_ , 313–320.
  * Cortes and Vapnik (1995) Cortes, C.; and Vapnik, V. 1995.  Support-vector networks.  _Machine Learning_ , 20(3): 273–297.
  * Couronné, Probst, and Boulesteix (2018) Couronné, R.; Probst, P.; and Boulesteix, A.-L. 2018.  Random forest versus logistic regression: a large-scale benchmark experiment.  _BMC Bioinformatics_ , 19(1): 270.
  * Dobkin and Reiss (1980) Dobkin, D. P.; and Reiss, S. P. 1980.  The complexity of linear programming.  _Theoretical Computer Science_ , 11(1): 1–18.
  * Dua and Graff (2017) Dua, D.; and Graff, C. 2017.  UCI Machine Learning Repository.
  * Eban et al. (2017) Eban, E.; Schain, M.; Mackey, A.; Gordon, A.; Rifkin, R.; and Elidan, G. 2017.  Scalable Learning of Non-Decomposable Objectives.  In _Artificial Intelligence and Statistics_ , 832–840.
  * Edelsbrunner and Guibas (1989) Edelsbrunner, H.; and Guibas, L. J. 1989.  Topologically sweeping an arrangement.  _Journal of Computer and System Sciences_ , 38(1): 165–194.
  * Elizondo (2006) Elizondo, D. 2006.  The linear separability problem: Some testing methods.  _IEEE Transactions on Neural Networks_ , 17(2): 330–344.
  * Fawcett (2006) Fawcett, T. 2006.  An introduction to ROC analysis.  _Pattern Recognition Letters_ , 27(8): 861–874.
  * Feldman et al. (2012) Feldman, V.; Guruswami, V.; Raghavendra, P.; and Wu, Y. 2012.  Agnostic learning of monomials by halfspaces is hard.  _SIAM Journal on Computing_ , 41(6): 1558–1590.
  * Fernández-Delgado et al. (2014) Fernández-Delgado, M.; Cernadas, E.; Barro, S.; and Amorim, D. 2014.  Do we need hundreds of classifiers to solve real world classification problems?  _JMLR_ , 3133–3181.
  * Ferri, Flach, and Hernández-Orallo (2002) Ferri, C.; Flach, P. A.; and Hernández-Orallo, J. 2002.  Learning Decision Trees Using the Area Under the ROC Curve.  In _ICML_ , 139–146.
  * Freund et al. (2003) Freund, Y.; Iyer, R.; Schapire, R. E.; and Singer, Y. 2003.  An efficient boosting algorithm for combining preferences.  _JMLR_ , 933–969.
  * Freund and Schapire (1995) Freund, Y.; and Schapire, R. E. 1995.  A desicion-theoretic generalization of on-line learning and an application to boosting.  In _European Conference on Computational Learning Theory_ , 23–37. Springer.
  * Freund and Schapire (1999) Freund, Y.; and Schapire, R. E. 1999.  Large margin classification using the perceptron algorithm.  _Machine Learning_ , 37(3): 277–296.
  * Gao et al. (2013) Gao, W.; Jin, R.; Zhu, S.; and Zhou, Z.-H. 2013.  One-pass AUC optimization.  In _ICML_ , 906–914.
  * Gao and Zhou (2015) Gao, W.; and Zhou, Z.-H. 2015.  On the consistency of AUC pairwise optimization.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 939–945.
  * Gultekin et al. (2020) Gultekin, S.; Saha, A.; Ratnaparkhi, A.; and Paisley, J. 2020.  MBA: mini-batch AUC optimization.  _IEEE Transactions on Neural Networks and Learning Systems_.
  * Hanley and McNeil (1982) Hanley, J. A.; and McNeil, B. J. 1982.  The meaning and use of the area under a receiver operating characteristic (ROC) curve.  _Radiology_ , 143(1): 29–36.
  * Herschtal and Raskutti (2004) Herschtal, A.; and Raskutti, B. 2004.  Optimising area under the ROC curve using gradient descent.  In _ICML_ , 49.
  * Ho and Zimmerman (2006) Ho, C.; and Zimmerman, S. 2006.  On the number of regions in an m-dimensional space cut by n hyperplanes.  _Australian Mathematical Society Gazette_ , 33(4): 260.
  * Joachims (2005) Joachims, T. 2005.  A support vector method for multivariate performance measures.  In _ICML_ , 377–384.
  * Johnson and Preparata (1978) Johnson, D. S.; and Preparata, F. P. 1978.  The densest hemisphere problem.  _Theoretical Computer Science_ , 6(1): 93–107.
  * Kallus and Zhou (2019) Kallus, N.; and Zhou, A. 2019.  The fairness of risk scores beyond classification: Bipartite ranking and the xAUC metric.  In _NIPS_ , 3433–3443.
  * Kotłowski, Dembczyński, and Hüllermeier (2011) Kotłowski, W.; Dembczyński, K.; and Hüllermeier, E. 2011.  Bipartite ranking through minimization of univariate loss.  In _ICML_ , 1113–1120.
  * Le et al. (2010) Le, Q. V.; Smola, A.; Chapelle, O.; and Teo, C. H. 2010.  Optimization of ranking measures.  _JMLR_ , 1(2999): 1–48.
  * Lee and Preparata (1984) Lee, D.-T.; and Preparata, F. P. 1984.  Computational geometry? a survey.  _IEEE Transactions on Computers_ , 1072–1101.
  * Lei and Ying (2019) Lei, Y.; and Ying, Y. 2019.  Stochastic Proximal AUC Maximization.  _arXiv preprint arXiv:1906.06053_.
  * Lemaître, Nogueira, and Aridas (2017) Lemaître, G.; Nogueira, F.; and Aridas, C. K. 2017.  Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning.  _JMLR_ , 18(17): 1–5.
  * Liu et al. (2020) Liu, M.; Yuan, Z.; Ying, Y.; and Yang, T. 2020.  Stochastic auc maximization with deep neural networks.  In _International Conference on Learning Representations (ICLR)_.
  * Liu et al. (2018) Liu, M.; Zhang, X.; Chen, Z.; Wang, X.; and Yang, T. 2018.  Fast Stochastic AUC Maximization with $O(1/n)$-Convergence Rate.  In _ICML_ , 3189–3197.
  * Maaten and Hinton (2008) Maaten, L. v. d.; and Hinton, G. 2008.  Visualizing data using t-SNE.  _JMLR_ , 2579–2605.
  * Menon and Williamson (2016) Menon, A. K.; and Williamson, R. C. 2016.  Bipartite Ranking: a Risk-Theoretic Perspective.  _JMLR_ , 17(195): 1–102.
  * Narasimhan and Agarwal (2013) Narasimhan, H.; and Agarwal, S. 2013.  On the relationship between binary classification, bipartite ranking, and binary class probability estimation.  In _NIPS_ , 2913–2921.
  * Natole, Ying, and Lyu (2018) Natole, M.; Ying, Y.; and Lyu, S. 2018.  Stochastic proximal algorithms for AUC maximization.  In _ICML_ , 3710–3719.
  * Nelder and Wedderburn (1972) Nelder, J. A.; and Wedderburn, R. W. 1972.  Generalized linear models.  _Journal of the Royal Statistical Society: Series A (General)_ , 135(3): 370–384.
  * Nguyen and Sanner (2013) Nguyen, T. T.; and Sanner, S. 2013.  Algorithms for direct 0-1 loss optimization in binary classification.  In _ICML_ , 1085–1093.
  * Oshiro, Perez, and Baranauskas (2012) Oshiro, T. M.; Perez, P. S.; and Baranauskas, J. A. 2012.  How many trees in a random forest?  In _International Workshop on Machine Learning and Data Mining in Pattern Recognition_ , 154–168. Springer.
  * Pedregosa et al. (2011) Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; and Duchesnay, E. 2011.  Scikit-learn: Machine Learning in Python.  _JMLR_ , 12: 2825–2830.
  * Probst and Boulesteix (2017) Probst, P.; and Boulesteix, A.-L. 2017.  To tune or not to tune the number of trees in random forest.  _JMLR_ , 18(1): 6673–6690.
  * Provost and Fawcett (2001) Provost, F.; and Fawcett, T. 2001.  Robust classification for imprecise environments.  _Machine Learning_ , 42(3): 203–231.
  * Qin, Liu, and Li (2010) Qin, T.; Liu, T.-Y.; and Li, H. 2010.  A general approximation framework for direct optimization of information retrieval measures.  _Information retrieval_ , 13(4): 375–397.
  * Rakotomamonjy (2004) Rakotomamonjy, A. 2004.  Optimizing AUC with support vector machine.  In _European Conference on Artificial Intelligence Workshop on ROC Curve and AI_ , 469–478.
  * Rudin and Schapire (2009) Rudin, C.; and Schapire, R. E. 2009.  Margin-based ranking and an equivalence between AdaBoost and RankBoost.  _JMLR_ , 2193–2232.
  * Rudin and Wang (2018) Rudin, C.; and Wang, Y. 2018.  Direct Learning to Rank And Rerank.  In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , volume 84, 775–783. PMLR.
  * Steck (2007) Steck, H. 2007.  Hinge rank loss and the area under the ROC curve.  In _European Conference on Machine Learning_ , 347–358. Springer.
  * Vogel et al. (2021) Vogel, R.; Bellet, A.; Clémen, S.; et al. 2021.  Learning Fair Scoring Functions: Bipartite Ranking under ROC-based Fairness Constraints.  In _International Conference on Artificial Intelligence and Statistics_ , 784–792. PMLR.
  * Yan et al. (2003) Yan, L.; Dodier, R. H.; Mozer, M.; and Wolniewicz, R. H. 2003.  Optimizing classifier performance via an approximation to the Wilcoxon-Mann-Whitney statistic.  In _ICML_ , 848–855.
  * Yang and Ying (2022) Yang, T.; and Ying, Y. 2022.  AUC maximization in the era of big data and AI: A survey.  _ACM Computing Surveys (CSUR)_.
  * Ying, Wen, and Lyu (2016) Ying, Y.; Wen, L.; and Lyu, S. 2016.  Stochastic online AUC maximization.  In _NIPS_ , 451–459.
  * Yogananda, Murty, and Gopal (2007) Yogananda, A.; Murty, M. N.; and Gopal, L. 2007.  A fast linear separability test by projection of positive points on subspaces.  In _Proceedings of the 24th International Conference on Machine Learning (ICML-07)_ , 713–720.
  * Zhao et al. (2011) Zhao, P.; Hoi, S. C.; Jin, R.; and Yang, T. 2011.  Online AUC maximization.  In _ICML_ , 233–240.

Does it pay to optimize AUC? — Supplementary Materials

#### Supplementary Outline.

§A presents the detailed proof of Theorem 1. Our generalization algorithm,
namely AUC-opt$(\mathcal{D},d)$ on $\mathbb{R}^{d}$ and its time complexity
analysis are in §B. Baseline methods including their parameter tunings are
presented in §C. Datasets and more experimental results are given in §D and
§5, respectively.

##  Appendix A The proof of Theorem 1

Recall that we have the following LAO problem and the theorem of its NP-
completeness.

######  Problem 4 (Linear AUC Optimization (LAO)).

Given the dataset $\mathcal{D}$ and the hypothesis class
$\mathcal{H}:=\\{\bm{w}:\bm{w}\in\mathbb{R}^{d}\\}$, the LAO problem is to
find a $\bm{w}\in\mathcal{H}$ such that the empirical AUC score is maximized,
that is

$(\textit{LAO})\quad\bm{w}^{\star}\in\operatorname*{arg\,max}_{\bm{w}\in\mathcal{H}}\sum_{i=1}^{n_{+}}\sum_{j=1}^{n_{-}}\frac{{\bm{1}}\left[\bm{w}^{\top}\bm{x}_{i}^{+}>\bm{w}^{\top}\bm{x}_{j}^{-}\right]}{n_{+}n_{-}},$
(5)

where the indicator ${\bm{1}}\left[A\right]=1$ if $A$ is true 0 otherwise.

######  Theorem 4 (NP-complete of LAO).

Consider the linear AUC optimization problem defined in Problem 1, if
$\mathcal{D}$ is not linearly separable, LAO is NP-complete when both $n$ and
$d$ are arbitrary.

To prove the NP-completeness, we reformulate the LAO problem to its
feasibility problem and then prove its NP-completeness. Before we prove
Theorem 1, let us introduce the spherical separation problem and a
corresponding lemma, which shows that the spherical separation problem is in
NP.

######  Problem 5 (Spherical Separation (SS)).

Given two sets of points
$\mathcal{U}:=\\{\bm{u}_{1},\bm{u}_{2},\ldots,\bm{u}_{n}\\}\subseteq\mathcal{S}^{d-1}\cap\mathbb{R}^{d}$
and
$\mathcal{V}:=\\{\bm{v}_{1},\bm{v}_{2},\ldots,\bm{v}_{m}\\}\subseteq\mathcal{S}^{d-1}\cap\mathbb{R}^{d}$.
Does there exist a hyperplane $\bm{w}^{\prime}$ such that $\mathcal{U}$ is
separable from $\mathcal{V}$?

######  Lemma 2 ((Dobkin and Reiss 1980)).

SS problem defined above is in NP, i.e., SS $\in$ NP.

###### Proof.

Without loss of the generality, let us consider the LAO problem in
$\mathcal{H}:=\mathbb{Q}^{d}$. Our first step is to reformulate the LAO
problem as a feasibility problem (F-LAO) shown in Equation (6). The goal is to
prove this feasibility problem is NP-complete. It has two steps: 1) to show
F-LAO is in NP (i.e., nondeterministic polynomial-time); and 2) to prove F-LAO
is NP-hard.

Feasibility problem of LAO (F-LAO)  Input: Given a finite dataset
$\mathcal{D}$ and a set of linear functions $\mathcal{H}$ and positive
integers $d,t$. Question: Does there exist $\bm{w}\in\mathcal{H}$ such that
$\sum_{i=1}^{n_{+}}\sum_{j=1}^{n_{-}}{\bm{1}}\left[\bm{w}^{\top}\bm{x}_{i}>\bm{w}^{\top}\bm{x}_{j}\right]\geq
t\ ?$ (6)

Figure 3: Left: An instance of OH. Right: the AUC curve of an instance of LAO.

#### Claim 1: F-LAO is in NP.

To prove it is in NP, we need to show that 1) there exists an algorithm
(verifier) verifying certificates in polynomial time; and 2) the certificate
length is polynomial in the input size. For the first step, given any
$\bm{w}\in\mathcal{H}$, one can find a polynomial-time verifier such that it
finishes in $\mathcal{O}(n_{p}n_{q}d)$ time. To do so, we propose a
polynomial-time verifier presented as in Algo. 3, which finishes in
polynomial-time, i.e. $\mathcal{O}(n_{p}n_{q}d)$. The rest is to show the
certificate $\bm{w}$ could be encoded in polynomial with respect to the input
size. All we need to do is to show that there exists another solution
$\bm{w}^{\prime}$ such that $\bm{w}^{\prime}$ could be encoded in polynomial
with respect to the input size. Let
$\mathcal{U}:=\\{\bm{x}_{i}^{+}:{\bm{w}^{\prime}}^{\top}\bm{x}_{i}^{+}>{\bm{w}^{\prime}}^{\top}\bm{x}_{j}^{-}\\}$
and
$\mathcal{V}:=\\{\bm{x}_{j}^{-}:{\bm{w}^{\prime}}^{\top}\bm{x}_{i}^{+}<={\bm{w}^{\prime}}^{\top}\bm{x}_{j}^{-}\\}$.
To find such $\bm{w}^{\prime}$ is equivalent to solve SS shown in Problem 5.
By Lemma 2 and the definition of $\mathcal{U}$, $\mathcal{V}$, we see that
such $\bm{w}^{\prime}$ can be encoded in polynomial length with respect to the
input since SS problem is in NP. Therefore, $\bm{w}=\bm{w}^{\prime}$ can also
be encoded in polynomial.

Input:  $\mathcal{D},d,t$ and the certificate $\bm{w}$

Algorithm 3 Verifier$(\left\langle\mathcal{D},d,t\right\rangle,\bm{w})$

1: $c\leftarrow 0$ $\triangleright$ The counter of the number of inequalities

2: for $(i,j)\in\\{1,\ldots,n_{+}\\}\times\\{1,\ldots,n_{-}\\}$ do

3: if $\bm{w}^{\top}\bm{x}_{i}^{+}>\bm{w}^{\top}\bm{x}_{j}^{-}$ then

4: $c\leftarrow c+1$

5: if $c\geq t$ then

6: Return  True

7: end if

8: end if

9: end for

10: Return  False

#### Claim 2: F-LAO is NP-hard.

We need to show that given any instance of an OH problem, it can be solved by
an instance of LAO problem. To do this, we show that any instance of the OH
problem can be transformed into an instance of the feasibility problem defined
in (6). First of all, we need to construct a training dataset $\mathcal{D}$ so
that an instance of Problem (1) can be defined. Notice that we can rewrite
vectors in $\mathcal{D}$ and construct new vectors $\bm{x}_{i}^{+}$ and
$\bm{x}_{1}^{-}$ as the following

$\displaystyle\bm{s}_{1}=\underbrace{(\bm{s}_{1}+\bm{x}_{1}^{-})}_{\bm{x}_{1}^{+}}-\bm{x}_{1}^{-},\bm{s}_{2}=\underbrace{(\bm{s}_{2}+\bm{x}_{1}^{-})}_{\bm{x}_{2}^{+}}-\bm{x}_{1}^{-},\ldots,\bm{s}_{t}=\underbrace{(\bm{s}_{t}+\bm{x}_{1}^{-})}_{\bm{x}_{t}^{+}}-\bm{x}_{1}^{-}.$

We construct the training labels such that
$y_{1}^{+},y_{2}^{+},\ldots,y_{t}^{+}$ are 1, and $y_{1}^{-}=-1$, then the
constructed
$\mathcal{D}:=\\{(\bm{x}_{1}^{+},y_{1}^{+}),\ldots,(\bm{x}_{t}^{+},y_{t}^{+}),(\bm{x}_{1}^{-},y_{1}^{-})\\}$.
Fig. 3 illustrates this correspondence where each positive sign is
$\bm{s}_{i}$, and the negative sign is $\bm{x}_{1}^{-}=\bm{0}$. The OH problem
has 14 inequalities shown on the left while the normal vector $\bm{w}$ defines
a hyperplane which corresponds to
$\sum_{i=1}^{n_{+}}\sum_{j=1}^{n_{-}}{\bm{1}}[\bm{w}^{\top}\bm{x}_{i}^{+}>\bm{w}^{\top}\bm{x}_{j}^{-}]=8$
as shown on the right of Fig. 3. To check whether there exists $\bm{w}$ so
that the number of inequalities can be satisfied is at least $m$, one only
needs to check whether there exists a $\bm{w}$ and $t=m$ such that (6) is
satisfied. This transformation can be done in polynomial time. Thus any
solution of this instance of the LAO problem defined by $\mathcal{D}$ is a
solution of OH. Therefore, the feasibility problem is NP-hard. ∎

#### The implementation of AUC-opt on $\mathbb{R}^{2}$.

We implemented AUC-opt by using C11 with a Python-3.7 wrapper. As described in
Algorithm 1, AUC-opt has a parameter $\epsilon$. This parameter is a small
enough constant so that it is smaller than the minimal difference between any
two consecutive slopes; that is, $\epsilon$ satisfies

$\epsilon<\min_{(i,j)\neq(i^{\prime},j^{\prime})}\left|\frac{x_{i2}-x_{j2}}{x_{i1}-x_{j1}}-\frac{x_{i^{\prime}2}-x_{j^{\prime}2}}{x_{i^{\prime}1}-x_{j^{\prime}1}}\right|.$

In our implementation, we dynamically set it as the half of the difference
between any two consecutive slopes. In other words, we sort the slope by
ascending order, $\ldots,s_{i},s_{i+1},\ldots$ where each
$\epsilon_{i}=(s_{i+1}-s_{i})/2$.

##  Appendix B Generalization to $\mathbb{R}^{d}$: AUC-opt$(\mathcal{D},d)$

The idea of projecting the original problem into lower-dimensional subproblems
is mainly inspired by Johnson and Preparata (1978). To simplify our problem,
we can map pair of points $(\bm{x}_{i}^{+},\bm{x}_{j}^{-})$ onto sphere
$\mathcal{S}^{d-1}$. Let us consider the function
$f_{i,j}(\bm{w}):=\bm{w}^{\top}(\bm{x}_{i}^{+}-\bm{x}_{j}^{-})/\|\bm{x}_{i}^{+}-\bm{x}_{j}^{-}\|_{2}$.555Notice
that any pair of points such that $\bm{x}_{i}^{+}=\bm{x}_{j}^{-}$ is not
interesting since it never contributes to the AUC score. Here we assume
$\bm{x}_{i}^{+}\neq\bm{x}_{j}^{-}$ for $i=1,2,\ldots,n_{+}$ and
$j=1,2,\ldots,n_{-}$. Our goal is essentially to find such $\bm{w}$ so that as
many $f_{i,j}>0$ as possible. Define such nonzero points
$\bm{p}_{t}:=(\bm{x}_{i}^{+}-\bm{x}_{j}^{-})/\|\bm{x}_{i}^{+}-\bm{x}_{j}^{-}\|_{2}$
where $t=1,2,\ldots,n_{+}n_{-}$. Our LAO problem can be reformulated as the
following problem:

Given a set of nonzero points
$\mathcal{K}:=\\{\bm{p}_{t}:\bm{p}_{t},t=1,2,\ldots,n_{+}n_{-}\\}$ on
$\mathcal{S}^{d-1}$, find a hyperplane $\bm{w}$ crossing the origin so that
$\sum_{t=1}^{n_{+}n_{-}}{\bm{1}}\left[\bm{w}^{\top}\cdot\bm{p}_{t}>0\right]$
is maximized.

Follow the idea of finding densest hemisphere from (Johnson and Preparata
1978), let the hyperplane crossing the origin defined by $\bm{p}_{t}$ as
$H_{t}:=\\{\bm{x}:\bm{x}^{\top}\cdot\bm{p}_{t}=0,\bm{x}\in\mathbb{R}^{d}\\}$.
It is enough to consider $\bm{w}\in\cup_{t=1,\ldots,n_{+}n_{-}}H_{t}$ since
$H_{t}$ divides $\mathbb{R}^{d}$ into at most $2\left[{n-1\choose
0},{n-1\choose 1},\ldots,{n-1\choose d-1}\right]$ cones (Ho and Zimmerman
2006) and each cone defines an equivilent class.666For any $\bm{x}$ and
$\bm{y}$ in the same cone, we have
$\sum_{t=1}^{n_{+}n_{-}}{\bm{1}}\left[\bm{x}^{\top}\cdot\bm{p}_{t}>0\right]=\sum_{t=1}^{n_{+}n_{-}}{\bm{1}}\left[\bm{y}^{\top}\cdot\bm{p}_{t}>0\right]$.
Let $\bm{w}^{\prime}$ be a point on the face of a specific cone such that the
AUC score is maximized. Since $\bm{w}^{\prime}$ is on the face,
$\bm{w}^{\prime}$ must be on a specific hyperplane $H_{t^{\prime}}$.
Therefore, it is enough to iterate all such hyperplane and solving the problem
recursively on these hyperplanes. Specifically, we project points onto
$H_{t^{\prime}}$ and then solve problem in $d-1$ dimensional subspace
(changing the number of coordinates from $d$ to $d-1$). Let the projection be
defined as
$\bm{P}(\bm{x}):=\bm{x}-(\bm{x}^{\top}\cdot\bm{u}/\|\bm{u}\|^{2})\cdot\bm{u}$
where $\bm{u}$ is the normal vector. The critical property of $\bm{P}$ is that
for any $\bm{x}\in H(\bm{u})$,
$\bm{x}^{\top}\bm{P}(\bm{p}_{t})=\bm{x}^{\top}\cdot\bm{p}_{t}$. Therefore, the
inner products of $\bm{p}_{t}$ with $\bm{x}$ are the same as those of
projected ones. We summarize the proposed method as in Algo. 2. This recursive
procedure projects points onto subspaces until the dimension reduces to 2.

Algorithm 4 $[\operatorname{AUC}_{\operatorname{opt}},\bm{w}^{\star}]=$AUC-
opt($\mathcal{D},d$)

1:
$\mathcal{K}=\\{(\bm{x}_{i}^{+}-\bm{x}_{j}^{-}):i\in\\{1,\ldots,n_{+}\\},j\in\\{1,\ldots,n_{-}\\}\\}$

2: if d=2 then

3: return $\operatorname{AUC}_{cur},\bm{w}^{\prime}=\operatorname{AUC-
opt}(\mathcal{D})$ $\triangleright$ call AUC-opt

4: end if

5: for $\bm{u}\in\mathcal{K}$ do

6:
$\mathcal{P}=\left\\{\left(\bm{x}-\frac{\bm{x}^{\top}\cdot\bm{u}}{\|\bm{u}\|^{2}}\cdot\bm{u},y\right):(\bm{x},y)\in\mathcal{D}\right\\}$
$\triangleright$ project points of $\mathcal{D}$ onto the hyperplane defined
by $\bm{u}$.

7:
$\mathcal{P}^{\prime}=\operatorname{change\\_coordinates}(\bm{u},\mathcal{P})$
$\triangleright$ change coordinates so that points are presented in $d-1$
coordinates.

8: $\operatorname{AUC}_{cur},\bm{w}^{\prime}=\operatorname{AUC-
opt}(\mathcal{P}^{\prime},d-1)$

9: $\bm{w}=\operatorname{change\\_coordinates\\_back}(\bm{u},\bm{w}^{\prime})$
$\triangleright$ change $d-1$ coordinates of $\bm{w}^{\prime}$ back to $d$
coordinates.

10: if
$\operatorname{AUC}_{\operatorname{opt}}<\operatorname{AUC}_{\operatorname{cur}}$
then

11: $\bm{w}^{\star}=\bm{w}$,
$\operatorname{AUC}_{\operatorname{opt}}=\operatorname{AUC}_{\operatorname{cur}}$

12: end if

13: end for

14: procedure
$\mathcal{P}^{\prime}=\text{change\\_coordinates}(\bm{u},{\mathcal{P}})$

15: $\mathcal{P}^{\prime}=\\{\\}$

16: for $\bm{p}\in\mathcal{P}$ do

17: find unit vectors $\bm{u}_{1},\bm{u}_{2},\ldots,\bm{u}_{d-1}$ such that
$\bm{u}_{i}^{\top}\bm{u}=0$.

18:
$\mathcal{P}^{\prime}=\mathcal{P}^{\prime}\cup[\bm{p}^{\top}\bm{u}_{1},\bm{p}^{\top}\bm{u}_{2},\ldots,\bm{p}^{\top}\bm{u}_{d-1}]^{\top}$

19: end for

20: Return $\mathcal{P}^{\prime}$

21: procedure
$\bm{w}=\text{change\\_coordinates\\_back}(\bm{u},\bm{w}^{\prime})$

22: let
$\bm{w}^{\prime}=[w_{1}^{\prime},w_{2}^{\prime},\ldots,w_{d-1}^{\prime}]^{\top}$

23: find unit vectors $\bm{u}_{1},\bm{u}_{2},\ldots,\bm{u}_{d-1}$ such that
$\bm{u}_{i}^{\top}\bm{u}=0$.

24: $\bm{w}=w_{1}^{\prime}\bm{u}_{1}+w_{2}^{\prime}\bm{u}_{2}+\ldots
w_{d-1}^{\prime}\bm{u}_{d-1}$

25: Return $\bm{w}$

######  Theorem 5 (Time complexity of AUC-opt($\mathcal{D},d$)).

Given the dataset
$\mathcal{D}:=\\{(\bm{x}_{i},y_{i}):i\in\left\\{1,2,\ldots,n\right\\}\\}$
where $\bm{x}_{i}\in\mathbb{R}^{d}$ and $y_{i}\in\\{\pm 1\\}$ and a collection
of linear separators $\mathcal{H}:=\\{\bm{w}:\bm{w}\in\mathbb{R}^{d}\\}$.
There exists an algorithm solves the LAO problem (1) in
$\mathcal{O}\left((n_{+}n_{-})^{d-1}\log(n_{+}n_{-})\right)$.

###### Proof.

The correctness of the proposed algorithm has been described above. The main
loop of Algo. 2 has $|\mathcal{K}|=n_{+}n_{-}$ iterations in total where each
iteration complexity is the total complexity of AUC-
opt($\mathcal{P}^{\prime},d-1$). Clearly, the total run time of AUC-
opt($\mathcal{P}^{\prime},d$) is
$\mathcal{O}((n_{+}n_{-})\cdot(n_{+}n_{-})\cdots(n_{+}n_{-})\log(n_{+}n_{-}))=\mathcal{O}\left((n_{+}n_{-})^{d-1}\log(n_{+}n_{-})\right)$.
∎

######  Remark 1.

Our method essentially follows the idea of (Johnson and Preparata 1978) where
we map interesting points $(\bm{x}_{i}^{+}-\bm{x}_{j}^{-})$ onto the sphere
$\mathcal{S}^{d-1}$ and then solve the problem recursively. However, at the
lowest level $d=2$, we call AUC-opt to obtain the best classifier for getting
the best AUC score.

##  Appendix C Descriptions of baseline methods

#### Random Forest (RF).

For each specific Random Forest (RF) classifier (Breiman 2001), there are two
important parameters: 1) the number of trees; and 2) the number of features.
Two common strategies are used to choose the number of features: 1) the number
of trees is set to $\log(d)+1$ and 2) the number of features is set to
$\sqrt{d}$ where we choose $\sqrt{d}$. The number of tree chosen in our
experiments are from $\\{10,50,100,150,200,300,400,500\\}$. Notice that the
number of trees does not necessarily increase the AUC score as reported in
(Oshiro, Perez, and Baranauskas 2012). Both (Oshiro, Perez, and Baranauskas
2012) and (Probst and Boulesteix 2017) show that the performance of AUC score
has no big gain after 128 trees. We use the implementation of RF from the
sklearn package (Pedregosa et al. 2011).

#### Balanced RF (B-RF).

B-RF is an RF classifier where the class weight is set to be “balanced” while
the other parameter setting is the same as RF’s.

#### RankBoost.

The RankBoost algorithm is proposed in Freund et al. (2003). There are
different strategies for selecting weak learners. As suggested in Cortes and
Mohri (2004), we choose the third method for selecting the weak learners.
Because there are no missing values in our datasets, the parameter
$q_{\text{def}}$ of weak learners defined is set to $0$. The only parameter
for RankBoost is the number of iterations which is tuned from
$\\{10,50,100,200,300,500,800,1000\\}$. We implement RankBoost in C11 language
with a Python-3.7 wrapper.

#### AdaBoost.

The AdaBoost method (Freund and Schapire 1995) has one important parameter
which is the maximum number of estimators at which boosting is terminated.
Specifically, this parameter is chosen from
$\\{2,3,4,5,6,10,50,100,150,200\\}$ while the default parameter is 50.

#### Logistic Regression (LR).

For the logistic regression classifier (Nelder and Wedderburn 1972), there is
an $\ell_{2}$ regularization parameter. We did not select $\ell_{1}$
regularization is because, in almost all of the datasets, the number of
training samples is much larger than the data dimension. Hence, the models are
assumed to be dense. The parameter space we tried is from
$c\in\left[10^{-6},10^{6}\right]$ by using 5-fold cross-validation.

#### Balanced LR (B-LR).

B-LR is the LR classifier when the class weight is set to be “balanced”.

#### Support Vector Machine (SVM).

For the Support Vector Machine (SVM) classifier (Cortes and Vapnik 1995), we
use the standard setting of linear SVM where the parameter of
$\ell_{2}$-regularization has been tuned from $c\in[10^{-6},10^{6}]$.

#### Balanced SVM (B-SVM).

B-SVM is the SVM classifier when the class weight is set to be “balanced”.

#### Gradient Boosting (GB).

The GB algorithm is an additive model where a single regression tree is
induced. Similar to AdaBoost, we tune the number of estimators from
$\\{10,50,100,200,300,500,800,1000\\}$.

#### SVM with Radial Basis Function kernel (SVM-RBF).

The SVM-RBF classifier is the support vector classification method using the
nonlinear kernel, namely the Radial Basis Function (RBF) kernel. The parameter
$c$ is tuned from $[10^{-6},10^{6}]$. The degree is set to a default value of
3.

#### Balanced SVM-RBF.

B-SVM-RBF is the SVM-RBF classifier when the class weight is set to be
“balanced”.

#### SVM-Perf.

The SVM-Perf method is proposed in Joachims (2005) where the goal is to
minimize the AUC loss by using the SVM-based method. We downloaded the code
from http://www.cs.cornell.edu/people/tj/svm˙light/svm˙perf.html. The
parameter $c$ is tuned from $[2^{-20},2^{11}]$. Other parameters are set to
default values.

#### Stochastic Proximal AUC maximization (SPAUC).

The SPAUC maximization algorithm is proposed in Lei and Ying (2019). SPAUC has
two parameters: 1) The learning rate $\eta_{t}:=2/(\mu t+1)$, which involves a
parameter $\mu$ where it is tuned from $\mu\in[10^{-7},10^{-2.5}]$ as
suggested in the paper; and 2) We use the $\ell^{2}$-norm as the
regularization where the regularization parameter is tuned from
$[10^{-5},10^{5}]$. The maximal number of epochs is fixed to 100. The Python
interface of the SPAUC algorithm is as the following. We implemented SPAUC by
using C11 with a Python-3.7 wrapper.

#### SPAM.

The Stochastic Proximal AUC Maximization (SPAM) algorithm is proposed in
Natole, Ying, and Lyu (2018). We use $\ell_{2}$ regularization where the
regularization parameter is tuned from $[10^{-5},10^{5}]$ as suggested in the
paper. Since there exists a constant coefficient $c$ over the learning rate,
i.e. $c/\sqrt{t}$, we tune it from $[1,100]$. The maximal number of epochs is
fixed to 100. The interface of SPAM is as the following. We implemented SPAM
by using C11 with a Python-3.7 wrapper.

##  Appendix D Datasets

Table 3: Binary classification datasets. Datasets are collected from Lemaître, Nogueira, and Aridas (2017); Chang and Lin (2011); Dua and Graff (2017). For dataset x[y] in each dataset name column, x is a multi-classification dataset. For such dataset, x[y] means samples of label y will be treated as positive samples otherwise negative samples. dataset name |  $n$ |  $d$ |  $\displaystyle n_{p}/n$ |  dataset name |  $n$ |  $d$ |  $\displaystyle n_{p}/n$
---|---|---|---|---|---|---|---
splice |  3175 |  60 |  0.5191 |  vowel[hid] |  990 |  10 |  0.0909
mushrooms |  8124 |  112 |  0.4820 |  spectrometer |  531 |  93 |  0.0847
banana |  5300 |  2 |  0.4483 |  cardio[3] |  2126 |  21 |  0.0828
australian |  690 |  14 |  0.4449 |  car-eval[34] |  1728 |  21 |  0.0775
spambase |  4601 |  57 |  0.3940 |  isolet |  7797 |  617 |  0.0770
ionosphere |  351 |  34 |  0.3590 |  us-crime |  1994 |  100 |  0.0752
fourclass |  862 |  24 |  0.3561 |  yeast[ml8] |  2417 |  103 |  0.0736
breast-cancer |  683 |  10 |  0.3499 |  scene |  2407 |  294 |  0.0735
pima |  768 |  8 |  0.3490 |  libras-move |  360 |  90 |  0.0667
yeast[cyt] |  1484 |  8 |  0.3120 |  seismic |  2584 |  24 |  0.0658
german |  1000 |  24 |  0.3000 |  thyroid-sick |  3772 |  52 |  0.0612
svmguide3 |  1284 |  22 |  0.2625 |  coil-2000 |  9822 |  85 |  0.0597
vehicle[bus] |  846 |  18 |  0.2577 |  arrhythmia[06] |  452 |  278 |  0.0553
vehicle[saab] |  846 |  18 |  0.2565 |  solar-flare[m0] |  1389 |  32 |  0.0490
vehicle[van] |  846 |  18 |  0.2352 |  oil |  937 |  49 |  0.0438
spectf |  267 |  44 |  0.2060 |  letter[a] |  20000 |  16 |  0.0394
ecoli[imu] |  336 |  7 |  0.1042 |  car-eval[4] |  1728 |  21 |  0.0376
pen-digits[0] |  10992 |  16 |  0.1040 |  wine-quality |  4898 |  11 |  0.0374
page-blocks |  5473 |  10 |  0.1023 |  letter[z] |  20000 |  16 |  0.0367
opt-digits[0] |  5620 |  64 |  0.0986 |  yeast[me2] |  1484 |  8 |  0.0344
opt-digits[8] |  5620 |  64 |  0.0986 |  yeast[me1] |  1484 |  8 |  0.0296
satimage[4] |  6435 |  36 |  0.0973 |  ozone-level |  2536 |  72 |  0.0288
pen-digits[5] |  10992 |  16 |  0.0960 |  w7a |  34780 |  300 |  0.0282
abalone[7] |  4177 |  10 |  0.0936 |  mammography |  11183 |  6 |  0.0232
sick-euthyroid |  3163 |  42 |  0.0926 |  abalone[19] |  4177 |  10 |  0.0077

Figure 4: Balanced accuracies (Left) and F1 scores (Right) as a function of
classifiers on testing datasets.

#### Real-world datasets.

Table 3 lists 50 datasets where they are ordered by imbalanced-ratio
$\gamma:=n_{p}/n$. All datasets are shuffling 200 times. For each time of the
shuffling, 50% of samples are used for training and the rest are used for
testing. All dataset samples have been standardized. Specifically, for each
dataset, training and testing samples are standardized by the mean and
standard deviation of training samples.

#### Synthetic datasets using t-SNE.

We project 50 datasets onto both $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$ using
t-SNE (Maaten and Hinton 2008) so that class patterns are conserved. Projected
points will be used as training and testing samples while keep labels
unchanged. We use a sklearn implementation of t-SNE. The parameter of
perplexity is set to 50 as suggested while all other parameters are set to
default values. For the simulation datasets in $\mathbb{R}^{3}$, we restricted
the number of training samples within $(n_{+}n_{-}=2000)$ to make our
experiments fast.

Figure 5: Variance of balanced accuracies (Left) and F1 scores (Right) as a function of dataset on testing datasets. Table 4: The averaged run time of all classifiers on training stage over all 50 datasets in $\mathbb{R}^{2}$. Method |  Run Time (mean$\pm$std) |  Method |  Run Time (mean$\pm$std)
---|---|---|---
SVM |  0.2186$\pm$0.2825 |  RF |  2.9737$\pm$2.5581
B-SVM |  0.1830$\pm$0.1811 |  B-RF |  2.8366$\pm$2.3977
LR |  0.1337$\pm$0.1318 |  GB |  3.4728$\pm$6.4346
B-LR |  0.1345$\pm$0.1357 |  SVM-RBF |  3.3854$\pm$17.070
SPAM |  3.1661$\pm$7.1141 |  B-SVM-RBF |  2.1731$\pm$9.1415
SPAUC |  3.1996$\pm$7.1521 |  RankBoost |  3.9690$\pm$10.169
SVM-Perf |  7.0858$\pm$9.3885 |  AdaBoost |  2.1076$\pm$2.2173

##  Appendix E More experimental results

#### Variances of balanced accuracy and F1 score.

Fig. 4 presents the balanced accuracy and F1-score on testing datasets. Fig. 5
illustrates the variance of balanced accuracies and F1 scores of 8 linear
methods over 50 t-SNE datasets. The overall performance of these two metrics
are consistent with the variance of AUC scores. However, the LR and B-LR have
higher variances on balanced accuracies and F1 scores than on AUC scores. This
may suggest decision functions of LR and B-LR needs to be calibrated.

#### Comparisons of training AUC scores.

Table 5 presents the comparison of training AUC scores over 200 trials of 50
real-world datasets. The performance is roughly consistent with results in the
testing stage where the nonlinear methods are significantly better than linear
methods. The balance weight strategy is clearly improving the linear methods
such as SVM and LR but has no improvement for nonlinear methods.

Table 5: The comparison of training AUC scores over 200 trials of 50 real-world datasets. The value of each cell (I,J) means the number of datasets where method I is significantly better than method J by using a t-test with a significance level of 5%. Numbers in red region are the results of AUC optimizers better than standard classifiers, while numbers in blue region are the reverse. |  SVM |  B-SVM |  LR |  B-LR |  RF |  B-RF |  GB |  SVM-RBF |  B-SVM-RBF |  RankBoost |  AdaBoost |  SPAM |  SPAUC |  SVM-Perf |  Average
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
SVM |  - |  2 |  0 |  0 |  0 |  0 |  0 |  4 |  3 |  0 |  2 |  26 |  37 |  4 |  6.0
B-SVM |  29 |  - |  6 |  0 |  0 |  0 |  0 |  4 |  3 |  1 |  2 |  37 |  42 |  30 |  11.85
LR |  41 |  23 |  - |  4 |  0 |  0 |  0 |  4 |  3 |  1 |  3 |  43 |  43 |  43 |  16.0
B-LR |  42 |  31 |  13 |  - |  0 |  0 |  0 |  4 |  3 |  1 |  3 |  43 |  44 |  43 |  17.46
RF |  50 |  50 |  50 |  50 |  - |  5 |  32 |  47 |  42 |  45 |  48 |  50 |  49 |  50 |  43.69
B-RF |  50 |  50 |  50 |  50 |  2 |  - |  32 |  46 |  41 |  45 |  48 |  50 |  49 |  50 |  43.31
GB |  50 |  50 |  50 |  50 |  1 |  1 |  - |  37 |  41 |  46 |  47 |  50 |  49 |  50 |  40.15
SVM-RBF |  45 |  45 |  44 |  44 |  0 |  0 |  6 |  - |  15 |  21 |  30 |  45 |  44 |  45 |  29.54
B-SVM-RBF |  47 |  47 |  46 |  46 |  0 |  0 |  3 |  13 |  - |  17 |  27 |  47 |  46 |  47 |  29.69
RankBoost |  49 |  49 |  46 |  49 |  1 |  1 |  0 |  22 |  26 |  - |  41 |  50 |  49 |  50 |  33.31
AdaBoost |  48 |  46 |  45 |  43 |  0 |  0 |  0 |  11 |  17 |  1 |  - |  50 |  48 |  49 |  27.54
SPAM |  12 |  1 |  2 |  0 |  0 |  0 |  0 |  4 |  3 |  0 |  0 |  - |  35 |  15 |  5.54
SPAUC |  4 |  0 |  1 |  0 |  0 |  0 |  0 |  3 |  3 |  0 |  1 |  6 |  - |  6 |  1.85
SVM-PL |  6 |  8 |  0 |  0 |  0 |  0 |  0 |  2 |  1 |  0 |  1 |  25 |  37 |  - |  6.15

#### Averaged run time over all datasets.

Table 4 shows the averaged run time over all 50 real-world datasets. Although
different methods may be implemented by using different programming languages,
it is clear that these nonlinear methods are much slower than linear methods.
Furthermore, the AUC approximate optimizers are generally slower than standard
classifiers. This is simply due to the loss of AUC is quadratic with respect
to the number of training samples.