  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 \textit{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.
