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.