{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T16:58:19Z","timestamp":1791478699617,"version":"4.3.4"},"reference-count":49,"publisher":"Institute of Mathematical Statistics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2019,8,1]]},"abstract":"<jats:p>This paper is concerned with the problem of top-$K$ ranking from pairwise comparisons. Given a collection of $n$ items and a few pairwise comparisons across them, one wishes to identify the set of $K$ items that receive the highest ranks. To tackle this problem, we adopt the logistic parametric model\u2014the Bradley\u2013Terry\u2013Luce model, where each item is assigned a latent preference score, and where the outcome of each pairwise comparison depends solely on the relative scores of the two items involved. Recent works have made significant progress toward characterizing the performance (e.g., the mean square error for estimating the scores) of several classical methods, including the spectral method and the maximum likelihood estimator (MLE). However, where they stand regarding top-$K$ ranking remains unsettled. We demonstrate that under a natural random sampling model, the spectral method alone, or the regularized MLE alone, is minimax optimal in terms of the sample complexity\u2014the number of paired comparisons needed to ensure exact top-$K$ identification, for the fixed dynamic range regime. This is accomplished via optimal control of the entrywise error of the score estimates. We complement our theoretical studies by numerical experiments, confirming that both methods yield low entrywise errors for estimating the underlying scores. Our theory is established via a novel leave-one-out trick, which proves effective for analyzing both iterative and noniterative procedures. Along the way, we derive an elementary eigenvector perturbation bound for probability transition matrices, which parallels the Davis\u2013Kahan $\\mathop{\\mathrm{sin}}\\nolimits \\Theta $ theorem for symmetric matrices. This also allows us to close the gap between the $\\ell_{2}$ error upper bound for the spectral method and the minimax lower limit.<\/jats:p>","DOI":"10.1214\/18-aos1745","type":"journal-article","created":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T04:04:54Z","timestamp":1558411494000},"page":"2204-2235","source":"Crossref","is-referenced-by-count":72,"title":["Spectral method and regularized MLE are both optimal for top-$K$ ranking"],"prefix":"10.1214","volume":"47","author":[{"given":"Yuxin","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianqing","family":"Fan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cong","family":"Ma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kaizheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"42","doi-asserted-by":"publisher","unstructured":"Rohe, K., Chatterjee, S. and Yu, B. (2011). Spectral clustering and the high-dimensional stochastic blockmodel. <i>Ann. Statist.<\/i> <b>39<\/b> 1878\u20131915.","DOI":"10.1214\/11-AOS887"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Hunter, D. R. (2004). MM algorithms for generalized Bradley\u2013Terry models. <i>Ann. Statist.<\/i> <b>32<\/b> 384\u2013406.","DOI":"10.1214\/aos\/1079120141"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs. I. The method of paired comparisons. <i>Biometrika<\/i> <b>39<\/b> 324\u2013345.","DOI":"10.1093\/biomet\/39.3-4.324"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Ford, L. R. Jr. (1957). Solution of a ranking problem from binary comparisons. <i>Amer. Math. Monthly<\/i> <b>64<\/b> 28\u201333.","DOI":"10.2307\/2308513"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Davis, C. and Kahan, W. M. (1970). The rotation of eigenvectors by a perturbation. III. <i>SIAM J. Numer. Anal.<\/i> <b>7<\/b> 1\u201346.","DOI":"10.1137\/0707001"},{"key":"30","unstructured":"Keshavan, R. H., Montanari, A. and Oh, S. (2010). Matrix completion from noisy entries. <i>J. Mach. Learn. Res.<\/i> <b>11<\/b> 2057\u20132078."},{"key":"16","doi-asserted-by":"crossref","unstructured":"Chung, F. R. K. (1997). <i>Spectral Graph Theory. CBMS Regional Conference Series in Mathematics<\/i> <b>92<\/b>. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the Amer. Math. Soc., Providence, RI.","DOI":"10.1090\/cbms\/092"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Tropp, J. A. (2015). An introduction to matrix concentration inequalities. <i>Found. Trends Mach. Learn.<\/i> <b>8<\/b> 1\u2013230.","DOI":"10.1561\/2200000048"},{"key":"1","unstructured":"Abbe, E., Fan, J., Wang, K. and Zhong, Y. (2017). Entrywise eigenvector analysis of random matrices with low expected rank. ArXiv preprint. Available at <a href=\"ArXiv:1709.09565\">ArXiv:1709.09565<\/a>."},{"key":"3","doi-asserted-by":"crossref","unstructured":"Ammar, A. and Shah, D. (2011). Ranking: Compare, don\u2019t score. In 2011 49<i>th Annual Allerton Conference on Communication<\/i>, <i>Control<\/i>, <i>and Computing<\/i> (<i>Allerton<\/i>) 776\u2013783. <a href=\"DOI:10.1109\/Allerton.2011.6120246\">DOI:10.1109\/Allerton.2011.6120246<\/a>.","DOI":"10.1109\/Allerton.2011.6120246"},{"key":"4","doi-asserted-by":"crossref","unstructured":"Ammar, A. and Shah, D. (2012). Efficient rank aggregation using partial data. In <i>SIGMETRICS<\/i> <b>40<\/b> 355\u2013366. ACM, New York.","DOI":"10.1145\/2318857.2254799"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Bubeck, S. (2015). Convex optimization: Algorithms and complexity. <i>Found. Trends Mach. Learn.<\/i> <b>8<\/b> 231\u2013357.","DOI":"10.1561\/2200000050"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Chen, Y. and Cand\u00e8s, E. J. (2017). Solving random quadratic systems of equations is nearly as easy as solving linear systems. <i>Comm. Pure Appl. Math.<\/i> <b>70<\/b> 822\u2013883.","DOI":"10.1002\/cpa.21638"},{"key":"14","unstructured":"Chen, Y., Chi, Y., Fan, J. and Ma, C. (2018). Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Available at <a href=\"ArXiv:1803.07726\">ArXiv:1803.07726<\/a>."},{"key":"15","doi-asserted-by":"crossref","unstructured":"Chen, Y., Fan, J., Ma, C. and Wang, K. (2019). Supplement to \u201cSpectral method and regularized MLE are both optimal for top-$K$ ranking.\u201d <a href=\"DOI:10.1214\/18-AOS1745SUPP\">DOI:10.1214\/18-AOS1745SUPP<\/a>.","DOI":"10.1214\/18-AOS1745SUPP"},{"key":"19","doi-asserted-by":"publisher","unstructured":"El Karoui, N. (2018). On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. <i>Probab. Theory Related Fields<\/i> <b>170<\/b> 95\u2013175.","DOI":"10.1007\/s00440-016-0754-9"},{"key":"20","unstructured":"Eldridge, J., Belkin, M. and Wang, Y. (2017). Unperturbed: Spectral analysis beyond Davis\u2013Kahan. ArXiv preprint. Available at <a href=\"ArXiv:1706.06516\">ArXiv:1706.06516<\/a>."},{"key":"21","unstructured":"Fan, J., Wang, W. and Zhong, Y. (2018). An $\\ell _{\\infty}$ eigenvector perturbation bound and its application. <i>J. Mach. Learn. Res.<\/i> <b>18<\/b> 1\u201342."},{"key":"24","unstructured":"Heckel, R., Shah, N. B., Ramchandran, K. and Wainwright, M. J. (2016). Active ranking from pairwise comparisons and when parametric assumptions don\u2019t help. ArXiv preprint. Available at <a href=\"ArXiv:1606.08842\">ArXiv:1606.08842<\/a>."},{"key":"27","unstructured":"Jang, M., Kim, S., Suh, C. and Oh, S. (2016). Top-$K$ ranking from pairwise comparisons: When spectral ranking is optimal. ArXiv preprint. Available at <a href=\"arXiv:1603.04153\">arXiv:1603.04153<\/a>."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Javanmard, A. and Montanari, A. (2018). Debiasing the lasso: Optimal sample size for Gaussian designs. <i>Ann. Statist.<\/i> <b>46<\/b> 2593\u20132622.","DOI":"10.1214\/17-AOS1630"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Jiang, X., Lim, L.-H., Yao, Y. and Ye, Y. (2011). Statistical ranking and combinatorial Hodge theory. <i>Math. Program.<\/i> <b>127<\/b> 203\u2013244.","DOI":"10.1007\/s10107-010-0419-x"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Koltchinskii, V. and Lounici, K. (2016). Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance. <i>Ann. Inst. Henri Poincar\u00e9 Probab. Stat.<\/i> <b>52<\/b> 1976\u20132013.","DOI":"10.1214\/15-AIHP705"},{"key":"32","doi-asserted-by":"crossref","unstructured":"Koltchinskii, V. and Xia, D. (2016). Perturbation of linear forms of singular vectors under Gaussian noise. In <i>High Dimensional Probability VII. Progress in Probability<\/i> <b>71<\/b> 397\u2013423. Springer, Cham.","DOI":"10.1007\/978-3-319-40519-3_18"},{"key":"33","unstructured":"Lu, Y. and Negahban, S. N. (2014). Individualized rank aggregation using nuclear norm regularization. ArXiv preprint. Available at <a href=\"ArXiv:1410.0860\">ArXiv:1410.0860<\/a>."},{"key":"35","doi-asserted-by":"publisher","unstructured":"Ma, C., Wang, K., Chi, Y. and Chen, Y. (2017). Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution. ArXiv preprint. Available at <a href=\"ArXiv:1711.10467\">ArXiv:1711.10467<\/a>.","DOI":"10.1007\/s10208-019-09429-9"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Negahban, S., Oh, S. and Shah, D. (2017). Rank centrality: Ranking from pairwise comparisons. <i>Oper. Res.<\/i> <b>65<\/b> 266\u2013287.","DOI":"10.1287\/opre.2016.1534"},{"key":"38","unstructured":"Negahban, S., Oh, S., Thekumparampil, K. K. and Xu, J. (2017). Learning from comparisons and choices. ArXiv preprint. Available at <a href=\"ArXiv:1704.07228\">ArXiv:1704.07228<\/a>."},{"key":"39","unstructured":"Pananjady, A., Mao, C., Muthukumar, V., Wainwright, M. J. and Courtade, T. A. (2017). Worst-case vs average-case design for estimation from fixed pairwise comparisons. ArXiv preprint. Available at <a href=\"ArXiv:1707.06217\">ArXiv:1707.06217<\/a>."},{"key":"43","unstructured":"Shah, N. B. and Wainwright, M. J. (2015). Simple, robust and optimal ranking from pairwise comparisons. ArXiv preprint. Available at <a href=\"arXiv:1512.08949\">arXiv:1512.08949<\/a>."},{"key":"44","doi-asserted-by":"publisher","unstructured":"Shah, N. B., Balakrishnan, S., Guntuboyina, A. and Wainwright, M. J. (2017). Stochastically transitive models for pairwise comparisons: Statistical and computational issues. <i>IEEE Trans. Inform. Theory<\/i> <b>63<\/b> 934\u2013959.","DOI":"10.1109\/TIT.2016.2634418"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Suh, C., Tan, V. Y. F. and Zhao, R. (2017). Adversarial top-$K$ ranking. <i>IEEE Trans. Inform. Theory<\/i> <b>63<\/b> 2201\u20132225.","DOI":"10.1109\/TIT.2017.2659660"},{"key":"47","unstructured":"Sur, P., Chen, Y. and Cand\u00e8s, E. J. (2017). The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square. ArXiv preprint. Available at <a href=\"ArXiv:1706.01191\">ArXiv:1706.01191<\/a>."},{"key":"49","doi-asserted-by":"publisher","unstructured":"Zhong, Y. and Boumal, N. (2017). Near-optimal bounds for phase synchronization. Available at <a href=\"arXiv:1703.06605\">arXiv:1703.06605<\/a>.","DOI":"10.1137\/17M1122025"},{"key":"2","unstructured":"Agarwal, A., Agarwal, S., Assadi, S. and Khanna, S. (2017). Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In <i>Conference on Learning Theory<\/i> 39\u201375."},{"key":"5","doi-asserted-by":"crossref","unstructured":"Baltrunas, L., Makcinskas, T. and Ricci, F. (2010). Group recommendations with rank aggregation and collaborative filtering. In <i>Proceedings of the Fourth ACM Conference on Recommender Systems. RecSys \u2019<\/i>10 119\u2013126. ACM, New York.","DOI":"10.1145\/1864708.1864733"},{"key":"8","unstructured":"Busa-Fekete, R., Sz\u00f6r\u00e9nyi, B., Weng, P., Cheng, W. and H\u00fcllermeier, E. (2013). Top-$k$ selection based on adaptive sampling of noisy preferences. In <i>International Conference on Machine Learning<\/i>."},{"key":"9","doi-asserted-by":"publisher","unstructured":"Chen, Y. and Candes, E. (2016). The projected power method: An efficient algorithm for joint alignment from pairwise differences. <i>Comm. Pure Appl. Math.<\/i> To appear.","DOI":"10.1002\/cpa.21760"},{"key":"11","unstructured":"Chen, Y. and Suh, C. (2015). Spectral MLE: Top-$K$ rank aggregation from pairwise comparisons. In <i>International Conference on Machine Learning<\/i> 371\u2013380."},{"key":"12","doi-asserted-by":"crossref","unstructured":"Chen, X., Bennett, P. N., Collins-Thompson, K. and Horvitz, E. (2013). Pairwise ranking aggregation in a crowdsourced setting. In <i>ACM International Conference on Web Search and Data Mining<\/i> 193\u2013202. ACM, New York.","DOI":"10.1145\/2433396.2433420"},{"key":"13","doi-asserted-by":"crossref","unstructured":"Chen, X., Gopi, S., Mao, J. and Schneider, J. (2017). Competitive analysis of the top-$K$ ranking problem. In <i>Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms<\/i> 1245\u20131264. SIAM, Philadelphia, PA.","DOI":"10.1137\/1.9781611974782.81"},{"key":"18","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kumar, R., Naor, M. and Sivakumar, D. (2001). Rank aggregation methods for the Web. In <i>International Conference on World Wide Web<\/i> 613\u2013622.","DOI":"10.1145\/371920.372165"},{"key":"23","unstructured":"Hajek, B., Oh, S. and Xu, J. (2014). Minimax-optimal inference from partial rankings. In <i>Neural Information Processing Systems<\/i> 1475\u20131483."},{"key":"26","unstructured":"Jamieson, K. G. and Nowak, R. D. (2011). Active ranking using pairwise comparisons. In <i>Neural Information Processing Systems<\/i> 2240\u20132248."},{"key":"34","unstructured":"Luce, R. D. (1959). <i>Individual Choice Behavior<\/i>: <i>A Theoretical Analysis<\/i>. Wiley, New York; Chapman &amp; Hall, London."},{"key":"36","unstructured":"Masse, K. (1997). Statistical models applied to the rating of sports teams. Technical Report, Bluefield College, Bluefield, VA."},{"key":"40","unstructured":"Rajkumar, A. and Agarwal, S. (2014). A statistical convergence perspective of algorithms for rank aggregation from pairwise data. In <i>International Conference on Machine Learning<\/i> I-118\u2013I-126."},{"key":"41","unstructured":"Rajkumar, A. and Agarwal, S. (2016). When can we rank well from comparisons of $O(n\\log n)$ non-actively chosen pairs? In <i>Conference on Learning Theory<\/i> 1376\u20131401."},{"key":"45","unstructured":"Soufiani, H. A., Chen, W. Z., Parkes, D. C. and Xia, L. (2013). Generalized method-of-moments for rank aggregation. In <i>Proceedings of the<\/i> 26<i>th International Conference on Neural Information Processing Systems. NIPS\u2019<\/i>13 2706\u20132714."}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1558425643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T16:35:20Z","timestamp":1791477320000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-47\/issue-4\/Spectral-method-and-regularized-MLE-are-both-optimal-for-top\/10.1214\/18-AOS1745.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,1]]},"references-count":49,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,8,1]]}},"URL":"https:\/\/doi.org\/10.1214\/18-aos1745","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,1]]}}}