Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.22766 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909810341969920 |
|---|---|
| author | Rao, Yang |
| author_facet | Rao, Yang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22766 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A theoretical guarantee for SyncRank Rao, Yang Machine Learning Artificial Intelligence 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. |
| title | A theoretical guarantee for SyncRank |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2509.22766 |