English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Given partially observed pairwise comparison data generated by theBradley-Terry-Luce (BTL) model, we study the problem of top-$k$ ranking. Thatis, to optimally identify the set of top-$k$ players. We derive the minimaxrate with respect to a normalized Hamming loss. This provides the first resultin the literature that characterizes the partial recovery error in terms of theproportion of mistakes for top-$k$ ranking. We also derive the optimal signalto noise ratio condition for the exact recovery of the top-$k$ set. The maximumlikelihood estimator (MLE) is shown to achieve both optimal partial recoveryand optimal exact recovery. On the other hand, we show another popularalgorithm, the spectral method, is in general sub-optimal. Our resultscomplement the recent work by Chen et al. (2019) that shows both the MLE andthe spectral method achieve the optimal sample complexity for exact recovery.It turns out the leading constants of the sample complexity are different forthe two algorithms. Another contribution that may be of independent interest isthe analysis of the MLE without any penalty or regularization for the BTLmodel. This closes an important gap between theory and practice in theliterature of ranking.

Partial Recovery for Top-$k$ Ranking: Optimality of MLE and Sub-Optimality of Spectral Method