*Bounty: 50*

*Bounty: 50*

Let $V$ be an $n$ dimensional space with sets of positive class vectors $P$ and negative class vectors $N$. The task is to find a vector $x$ such that AUC is maximized, based on ranking generated by computing distances between $x$ and $P,V$. So in a sense, $x$ is closer to $P$ than to $V$. It looks like this doesn’t have a unique solution, but I’m curious if there is a really easy explicit solution to this, or a short algorithm? Or is this NP-hard?

Surely this is a well known classical problem? One algorithm that I think works is to sample triplets $(x,p,n)$ with one positive and one negative vector and then formulate the usual triplet loss:

$$L(x,p,n) = max(0,|x-p|^2-|x-n|^2+epsilon),$$

which pushes $x$ closer to $p$ and further from $n$. I’m just hoping for something easier.