Bipartite Ranking Bounds.pdf

The bipartite ranking problem involves ranking "positive" inputs higher than "negative" ones. A widely used performance metric is the Wilcoxon-Mann-Whitney statistic. The pairwise squared loss is a consistent estimator of AUC and is widely preferred.

Algorithms

Two algorithms are considered:

1. Batch Bipartite Ranking (BBR): minimizes the empirical risk based on all pairs available in the sample set.
2. Low Cost Bipartite Ranking (LCBR): subsamples pairs uniformly at random with replacement to reduce the sample cost.

Theoretical Analysis

A new theoretical analysis of BBR is provided, and a risk bound is derived based on the metric entropy of the parameter space. The main result is:

Theorem 1: A risk bound for BBR is derived, which depends on the label skew, the metric entropy of the parameter space, and the sample size.

Low Cost Bipartite Ranking (LCBR)

The subsample size required for LCBR to be competitive with BBR is analyzed. The proof utilizes matrix and vector concentration inequalities, and the result shows that the subsample size does not have a quadratic dependence on the sample size.

Experimental Results

Experimental results show significant speed gain against the batch algorithm, as well as competitive performance against state-of-the-art bipartite ranking algorithms on real datasets.

Assumptions

The input domain is assumed to be compact, and the domain of ranking functions is assumed to be compact, with a norm bound imposed on the individual features. The results apply to the most general case where the covariance matrices are positive semi-definite.