Phase Transitions in Approximate Ranking
This work addresses the fundamental challenge of approximate ranking for statisticians and machine learning practitioners, providing theoretical insights into error behavior transitions, but it is incremental as it builds on existing ranking models.
The paper tackles the problem of estimating ranks from pairwise interaction data, characterizing the exact optimal statistical error rates and discovering phase transition boundaries in these rates based on the signal-to-noise ratio, with regimes showing trivial, polynomial, exponential, or zero error behaviors.
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.