complexity of the maximum rank correlation

Question

Given two sets of vectors of dimension $p$, $x_1,\ldots,x_m$ and $y_1,\ldots,y_n$, The Maximum Rank Correlation estimator is the vector $\beta$ given by $$\arg\max_{b\in\mathbb{R}^p}\sum_{i=1}^m\sum_{j=1}^n 1(b^t x < b^t y).$$ According to this old post, the fastest algorithms to compute $\beta$ run in $n^2\log(n)$ time. However, a 2020 paper uses mixed integer programming to compute beta, noting that "MIP is still an NP(non-deterministic polynomial-time)-hard problem". Perhaps in saying that the fastest algorithms run in $n^2\log(n)$ time the old stackexchange post was referring to an algorithm for an approximate, not necessarily global solution. For example, the paper cited in the answer to the old stackexchange post, Wang 2007, does not necessarily compute the argmax: "the [Nelder-Mead] algorithm and the proposed IMO algorithm share one common limitation. That is there exists no solid theory, which can guarantee the maximizer identified by either of them is indeed the global maximizer. In fact, they are very likely to be just a local maximizer."

What is in fact the complexity in the numbers $m,n$ of the input vectors, of computing $\beta$, and is it related to some other better studied problem? I posted a related question on the statistics Stackexchange a few day ago but didn't get any replies.

Answer 1

I believe the problem is likely NP-hard and thus the complexity is likely super-polynomial.

The problem is roughly equivalent to finding a linear classifier with maximum accuracy, i.e., minimizing the 0-1 loss. (The difference is the latter chooses a threshold for prediction and counts the number of correct predictions, examining each single sample in isolation, whereas your objective function looks at correct relationships between pairs of samples.) Finding a linear classifier that minimizes the 0-1 loss is known to be NP-hard.

An ILP is a reasonable approach if you need the exact global optimum. In the worst case you can expect its asymptotic running time to be exponential. In practice, asymptotic worst-case complexity is not likely to be a useful measure, if you want to use that in practice; instead, it is probably more effective to empirically measure performance on typical problem instances.

In classification, a standard trick is to substitute some other loss (e.g., the hinge loss) in place of the 0-1 loss and then optimize that. That isn't necessarily the optimal solution for your original objective function, but it often leads to a "pretty good" solution. You could also try that, assuming it's not critical to have the exact optimum, and instead you want a more efficient algorithm.

I couldn't find the papers you are referring to that discuss a $O(n^2 \log n)$ time algorithm (links are broken or the papers are paywalled) but I presume the approaches you cite don't give a global optimal solution to the problem. That seems consistent with the discussion of related work in the 2020 paper, e.g., with prior methods, "we are not sure whether the current solution is the global optimum", "the fundamental local solution issue still remains", etc.