Partial recovery for top-k ranking: Optimality of MLE and SubOptimality of the spectral method
前 k 名排序的部分恢复：极大似然最优性与谱方法的次优性AI 解读 ↓
← 返回论文列表与筛选
阅读说明
本页整理公开书目信息，不生成学术质量评分。AI 解读根据题名及所注明的摘要或原文片段生成，未完成全文核验，可能有误；具体假设、证明与结论请核对原文。摘要保留来源文本，未经模型改写。
DOI 首次登记不等于接收或发表日期。部分更正、评论等条目没有独立摘要；缺少可靠材料时保留待补状态。
引用量采用 OpenAlex 单条关联记录，不合计多个记录；关联记录可能包含正式发表版本，不等于此版本单独引用。缺失不视为零，引用指标不代表论文质量。
关注作者按书目中的完整姓名匹配，同名和姓名变体需人工辨别。相关论文先按共享细分方向和具体方法排列，再参考通用方法与发表日期。
分类依据与纠错
AI 根据所提供的论文材料归类：摘要研究统计排序与集合恢复，虽使用 BTL 模型，但未明确讨论离散选择或经济网络问题。
反馈分类问题
正在核对关联版本…
代码、数据与补充材料
正在核对对应版本的资源…
关注这篇论文的作者
前 k 名排序的部分恢复：极大似然最优性与谱方法的次优性
- 研究问题
- 在 BTL 模型生成的部分成对比较数据中，识别前 k 名集合的错误比例能达到何种界限，完全恢复需要多强的信号？
- 方法与思路
- 作者以归一化 Hamming 损失推导部分恢复的极小极大率，并分析完全恢复的信噪比条件，比较极大似然与谱方法。
- 材料陈述的贡献
- 摘要称，极大似然估计同时达到最优部分与完全恢复，谱方法一般次优；作者还分析不加惩罚或正则化的极大似然估计。
- 阅读关注点
- 应核对比较数据的观测机制、信噪比定义、部分恢复误差界，以及两种方法在完全恢复样本复杂度常数上的差异。
- 阅读边界
- 所据 OpenAlex 索引摘要未注明稿件版本；观测条件、信号范围与常数未列出，不能将模型内最优性推广到任意排序数据。
原文摘要
Given partially observed pairwise comparison data generated by the Bradley–Terry–Luce (BTL) model, we study the problem of top-k ranking. That is, to optimally identify the set of top-k players. We derive the minimax rate with respect to a normalized Hamming loss. This provides the first result in the literature that characterizes the partial recovery error in terms of the proportion of mistakes for top-k ranking. We also derive the optimal signal to noise ratio condition for the exact recovery of the top-k set. 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 suboptimal. Our results complement the recent work (Ann. Statist. 47 (2019) 2204–2235) that shows both the MLE and the spectral method achieve the optimal sample complexity for exact recovery. It turns out the leading constants of the sample complexity are different for the two algorithms. Another contribution that may be of independent interest is the analysis of the MLE without any penalty or regularization for the BTL model. This closes an important gap between theory and practice in the literature of ranking.