A theoretical guarantee for SyncRank

• URL: http://arxiv.org/abs/2509.22766v1
• Date: Fri, 26 Sep 2025 16:45:06 GMT
• Title: A theoretical guarantee for SyncRank
• Authors: Yang Rao,
• Abstract summary: We present a theoretical and empirical analysis of the SyncRank algorithm for recovering a global ranking from noisy pairwise comparisons.<n>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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• RI-Loss: A Learnable Residual-Informed Loss for Time Series Forecasting [13.117430904377905]
  Time series forecasting relies on predicting future values from historical data.<n>MSE has two fundamental weaknesses: its point-wise error fails to capture temporal relationships, and it does not account for inherent noise in the data.<n>We introduce the Residual-Informed Loss (RI-Loss), a novel objective function based on the Hilbert-Schmidt Independence Criterion (HSIC)
  arXiv  Detail & Related papers  (2025-11-13T09:36:00Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Bit-Level Discrete Diffusion with Markov Probabilistic Models: An Improved Framework with Sharp Convergence Bounds under Minimal Assumptions [14.04623086233189]
  We introduce Discrete Markov Probabilistic Models (DMPMs) for discrete data generation.<n>DMPMs operates in discrete bit space, where the noising process is a continuous-time Markov chain that flips labels uniformly at random.<n>This work bridges theoretical foundations and practical applications, advancing the development of effective and theoretically grounded discrete generative models.
  arXiv  Detail & Related papers  (2025-02-11T20:36:23Z)
• Stochastic Gradient Descent Revisited [0.0]
  gradient descent (SGD) has been a go-to algorithm for non gradient convergence problems in machine learning.<n>This paper presents a full scope convergence theory and provides rates and complexities.
  arXiv  Detail & Related papers  (2024-12-08T21:15:08Z)
• Regression with Label Differential Privacy [64.21020761920322]
  We derive a label DP randomization mechanism that is optimal under a given regression loss function. We prove that the optimal mechanism takes the form of a "randomized response on bins"
  arXiv  Detail & Related papers  (2022-12-12T17:41:32Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Label Ranking through Nonparametric Regression [5.994412766684843]
  Label Ranking corresponds to the problem of learning a hypothesis that maps features to rankings over a finite set of labels. We introduce a generative model for Label Ranking, in noiseless and noisy nonparametric regression settings. We complement our theoretical contributions with experiments, aiming to understand how the input regression noise affects the observed output.
  arXiv  Detail & Related papers  (2021-11-04T10:59:46Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  We optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance.
  arXiv  Detail & Related papers  (2021-10-26T15:02:27Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)
• Statistical optimality and stability of tangent transform algorithms in logit models [6.9827388859232045]
  We provide conditions on the data generating process to derive non-asymptotic upper bounds to the risk incurred by the logistical optima. In particular, we establish local variation of the algorithm without any assumptions on the data-generating process. We explore a special case involving a semi-orthogonal design under which a global convergence is obtained.
  arXiv  Detail & Related papers  (2020-10-25T05:15:13Z)
• Consistency of Anchor-based Spectral Clustering [0.0]
  Anchor-based techniques reduce the computational complexity of spectral clustering algorithms. We show that it is amenable to rigorous analysis, as well as being effective in practice. We find that it is competitive with the state-of-the-art LSC method of Chen and Cai.
  arXiv  Detail & Related papers  (2020-06-24T18:34:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.