Detta dokument handlar om problemet med top-K rankning från parvisa jämförelser. Med tanke på en samling n objekt och några parvis binära jämförelser över dem, vill man identifiera uppsättningen av K objekt som får de högsta leden. För att ta itu med detta problem antar vi den logistiska parametriska modellen Bradley-Terry-Luce-modellen, där varje objekt tilldelas en latent preferenspoäng, och där resultatet av varje parvis jämförelse enbart beror på de relativa poängen av de två berörda punkterna. Den senaste tidens arbeten har gjort betydande framsteg när det gäller att karakterisera resultaten (t.ex. Det genomsnittliga kvadratfelet för skattning av poängen) för flera klassiska metoder, inklusive spektralmetoden och den maximala sannolikheten för uppskattning (MLE). Men där de står när det gäller top-K rankning är fortfarande osäkert. Vi visar att under en slumpmässig provtagning modell, spektralmetoden ensam, eller den legaliserade MLE ensam, är minimax optimal när det gäller provet komplexitet-antalet parade jämförelser som behövs för att säkerställa exakt top-K identifiering. Detta sker genom optimal kontroll av det ingångsvisa felet i poänguppskattningarna. Vi kompletterar våra teoretiska studier med numeriska experiment som bekräftar att båda metoderna ger låga ingångsfel för att uppskatta de underliggande poängen. Vår teori är etablerad baserat på en ny leave-one-out trick, som visar sig vara effektivt för att analysera både iterativ och icke-iterativ optimering. Längs vägen, vi härleda en elementär eigenvector perturbation bundet för sannolikhetsövergång matriser, som paralleller Davis-Kahan sin  på teorem för symmetriska matriser. Detta gör att vi kan stänga gapet mellan 2 fel övre gräns för spektralmetoden och minimax nedre gräns.
Den ∞ som är bunden till en legaliserad MLE analyseras i REF.
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
{'venue': 'Annals of Statististics, Volume 47, Number 4 (2019), 2204-2235', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Medicine']}