Title: Phase Transitions in Approximate Ranking,
Abstract: We study the problem of approximate ranking from observations of pairwise
interactions. The goal is to estimate the underlying ranks of $n$ objects from
data through interactions of comparison or collaboration. Under a general
framework of approximate ranking models, we characterize the exact optimal
statistical error rates of estimating the underlying ranks. We discover
important phase transition boundaries of the optimal error rates. Depending on
the value of the signal-to-noise ratio (SNR) parameter, the optimal rate, as a
function of SNR, is either trivial, polynomial, exponential or zero. The four
corresponding regimes thus have completely different error behaviors. To the
best of our knowledge, this phenomenon, especially the phase transition between
the polynomial and the exponential rates, has not been discovered before.