Rank, Ranking and Phase Transition

The thesis consists of three topics. The first two topics are both about ranking under the Bradley-Terry-Luce (BTL) model. We first study the problem of top-$k$ ranking, which is to optimally identify the set of top-$k$ players. We derive the minimax rate with respect to a normalized Hamming loss. The maximum likelihood estimator (MLE) is shown to achieve both optimal partial recovery and optimal exact recovery. On the other hand, we show another popular algorithm, the spectral method, is in general sub-optimal. Then we come to the problem of full ranking, which needs to provide the full rank of all players instead of just the top $k$. The minimax rate of this ranking problem is derived with respect to the Kendall's tau distance. The minimax rate of full ranking under this loss exhibits a phase transition between an exponential rate and a polynomial rate depending on the magnitude of the signal-to-noise ratio of the problem. To achieve the minimax rate, we propose a divide-and-conquer ranking algorithm that first divides the $n$ players into groups of similar skills and then computes local MLE within each group. The third topic, instead, is about rank, where a Bayesian method for low-rank matrix estimation is proposed. We also explore the possibility of rank adaptation by proposing a rank adaptive prior and have some preliminary results for the special case when the underlying signal is of rank 1.