A fast algorithm for learning large scale preference relations

We consider the problem of learning the rank-ing function that maximizes a generalization
of the Wilcoxon-Mann-Whitney statistic on
training data. Relying on an ϵ-exact approx-
imation for the error-function, we reduce the
computational complexity of each iteration
of a conjugate gradient algorithm for learn-
ing ranking functions from O(m2), to O(m),
where m is the size of the training data.
Experiments on public benchmarks for ordi-
nal regression and collaborative filtering show
that the proposed algorithm is as accurate as
the best available methods in terms of rank-
ing accuracy, when trained on the same data,
and is several orders of magnitude faster.