# A theoretical guarantee for SyncRank

arXiv: https://arxiv.org/abs/2509.22766 · HTML: https://mlsanity.com/paper/2509.22766/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 19 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 8 of 8)

- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization](https://mlsanity.com/paper/1603.00211/) (2016)
- [Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization](https://mlsanity.com/paper/1504.01070/) (2015)
- [Spectral Ranking Inferences based on General Multiway Comparisons](https://mlsanity.com/paper/2308.02918/) (2023)
- [Aggregating Incomplete and Noisy Rankings](https://mlsanity.com/paper/2011.00810/) (2020)
- [Ranking with multiple types of pairwise comparisons](https://mlsanity.com/paper/2206.13580/) (2022)
- [Minimax Hypothesis Testing for the Bradley-Terry-Luce Model](https://mlsanity.com/paper/2410.08360/) (2024)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)

## Abstract (arXiv)

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.