提出同步排序的理论保证，证明在特定噪声下可精确恢复排名。
A theoretical guarantee for SyncRank
- 用复数向量建模排名，通过半定规划求解
- 噪声低于 O(sqrt(n/log n)) 时可高概率精确恢复
- 适用于需要可靠排序的场景，如评测系统
我们对 SyncRank 算法进行了理论与实验分析，该算法旨在从有噪声的成对比较中恢复全局排名。通过采用一种复数数据模型，将真实排名编码在单位模长向量的相位中，我们为对应的半定规划（SDP）松弛建立了精确的非渐近恢复保证。主要定理刻画了一个临界噪声阈值——其量级为 sigma = O(sqrt(n / log n))——在此阈值以下，SyncRank 能以高概率实现精确排名恢复。在该模型下的大量实验验证了理论预测，并展示了算法在不同问题规模和噪声环境下的鲁棒性。
原文摘要 · Abstract (English)
We present a theoretical and empirical analysis of the SyncRank algorithm for recovering a global ranking from noisy pairwise comparisons. By adopting a complex-valued data model where the true ranking is encoded in the phases of a unit-modulus vector, we establish a sharp non-asymptotic recovery guarantee for the associated semidefinite programming (SDP) relaxation. Our main theorem characterizes a critical noise threshold - scaling as sigma = O(sqrt(n / log n)) - below which SyncRank achieves exact ranking recovery with high probability. Extensive experiments under this model confirm the theoretical predictions and demonstrate the algorithm's robustness across varying problem sizes and noise regimes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。