# complexity of the maximum rank correlation

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.

• What exactly is the problem statement? Please edit your post to state precisely what problem you want solved. Do you want the global optimum for $\beta$? If so talking about estimators is confusing. Or do you want an estimate/approximation to the global optimum? Or do you want a local optimum? Or an algorithm that will often be good-enough in practice? Each of those alternatives (other than the global optimum) has follow-up questions to define what precisely that means.
– D.W.
Jul 24, 2023 at 17:40
• The "old post" you link to has citations to two papers -- have you read them? Can you summarize them and their relevance? We expect you to do that kind of research before asking and to provide that background for readers.
– D.W.
Jul 24, 2023 at 17:40
• @D.W. I made some clarifications and added the relevant information from the (relevant) cited paper in the old stackexchange post. Jul 24, 2023 at 18:24

## 1 Answer

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.

• On your last sentence, for the 2020 paper (giving the global solution using MIP) I linked to arxiv Jul 24, 2023 at 18:46
• @kara890, see revised answer. I wasn't referring to that paper.
– D.W.
Jul 24, 2023 at 18:58