A theoretical guarantee for SyncRank
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Rank Aggregation for Course Sequence Discovery
In this work, we adapt the rank aggregation framework for the discovery of optimal course sequences at the university level. Each student provides a partial ranking of the courses taken throughout his or her undergraduat…
Unsupervised Object Detection with Theoretical Guarantees
Unsupervised object detection using deep neural networks is typically a difficult problem with few to no guarantees about the learned representation. In this work we present the first unsupervised object detection method…
DecoderObjectobject-detectionObject Detection+1Denoising guarantees for optimized sampling schemes in compressed sensing
Compressed sensing with subsampled unitary matrices benefits from \emph{optimized} sampling schemes, which feature improved theoretical guarantees and empirical performance relative to uniform subsampling. We provide, in…
compressed sensingDenoisingMachine Learning with Guarantees using Descriptive Complexity and SMT Solvers
Machine learning is a thriving part of computer science. There are many efficient approaches to machine learning that do not provide strong theoretical guarantees, and a beautiful general learning theory. Unfortunately, …
BIG-bench Machine LearningBoard GamesDescriptiveLearning TheoryAlgorithms for ridge estimation with convergence guarantees
The extraction of filamentary structure from a point cloud is discussed. The filaments are modeled as ridge lines or higher dimensional ridges of an underlying density. We propose two novel algorithms, and provide theore…