Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

• URL: http://arxiv.org/abs/2605.23854v1
• Date: Fri, 22 May 2026 17:08:07 GMT
• Title: Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries
• Abstract summary: We investigate the entry-wise error of spectral algorithms against a semi-random adversary.<n>We show that performance approaching that of uniformly sampled graphs can be recovered by appropriately reweighting the observed edges.
• Score: 11.014454221295795
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bradley-Terry-Luce (BTL) model estimation is a well-established strategy to rank a collection of items given a dataset of pairwise comparisons. Although the theoretical performance of BTL estimation methods, such as spectral and maximum likelihood estimation, is well studied in the regime of uniformly sampled graphs, generalizing such results to a wider class of random graphs has proved challenging. In this work, we investigate the entry-wise error of spectral algorithms against a semi-random adversary that can arbitrarily boost the sampling probabilities of certain edges. We find that the performance of the unweighted spectral method is heavily dependent on the spectral properties of the generated graph. Furthermore, we show that asymptotic performance approaching that of uniformly sampled graphs can be recovered by appropriately reweighting the observed edges to counteract the adversary and restore the spectral gap. Finally, we provide numerical simulations that support our theoretical findings.

Related papers

• Asymptotic Theory for Graphical SLOPE: Precision Estimation and Pattern Convergence [2.5407895016635127]
  This paper studies Graphical SLOPE for precision matrix estimation.<n>In a fixed-dimensional regime, we establish that the root-$n$ scaled estimation error converges to the unique minimizer of a strictly convex optimization problem.<n>We also establish convergence of the induced SLOPE pattern, thereby obtaining an characterization of the clustering structure selected by the estimator.
  arXiv  Detail & Related papers  (2026-04-14T14:10:56Z)
• SIGMA: Scalable Spectral Insights for LLM Collapse [51.863164847253366]
  We introduce SIGMA (Spectral Inequalities for Gram Matrix Analysis), a unified framework for model collapse.<n>By utilizing benchmarks that deriving and deterministic bounds on the matrix's spectrum, SIGMA provides a mathematically grounded metric to track the contraction of the representation space.<n>We demonstrate that SIGMA effectively captures the transition towards states, offering both theoretical insights into the mechanics of collapse.
  arXiv  Detail & Related papers  (2026-01-06T19:47:11Z)
• Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise [3.582937960220228]
  We study the computational optimality of a spectral algorithm for a low-rank signal matrix corrupted by additive i.i.d.<n>We do not assume that the variance profile has a block structure, and suggest that the same spectral algorithm might remain optimal for quite general profiles.
  arXiv  Detail & Related papers  (2025-10-09T17:53:59Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Spectral Ranking Inferences based on General Multiway Comparisons [7.222667862159246]
  We show that a two-step spectral method can achieve the same vanilla efficiency as the Maximum Likelihood Estor. It is noteworthy that this is the first time effective two-sample rank testing methods have been proposed.
  arXiv  Detail & Related papers  (2023-08-05T16:31:32Z)
• Spectral Feature Augmentation for Graph Contrastive Learning and Beyond [64.78221638149276]
  We present a novel spectral feature argumentation for contrastive learning on graphs (and images) For each data view, we estimate a low-rank approximation per feature map and subtract that approximation from the map to obtain its complement. This is achieved by the proposed herein incomplete power iteration, a non-standard power regime which enjoys two valuable byproducts (under mere one or two iterations) Experiments on graph/image datasets show that our spectral feature augmentation outperforms baselines.
  arXiv  Detail & Related papers  (2022-12-02T08:48:11Z)
• Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models [31.58736590532443]
  We consider the problem of estimating two statistically independent signals in a mixed generalized linear model. Our characterization exploits a mix of tools from random matrices, free probability and the theory of approximate message passing algorithms.
  arXiv  Detail & Related papers  (2022-11-21T11:35:25Z)
• Spectral Decomposition Representation for Reinforcement Learning [100.0424588013549]
  We propose an alternative spectral method, Spectral Decomposition Representation (SPEDER), that extracts a state-action abstraction from the dynamics without inducing spurious dependence on the data collection policy. A theoretical analysis establishes the sample efficiency of the proposed algorithm in both the online and offline settings. An experimental investigation demonstrates superior performance over current state-of-the-art algorithms across several benchmarks.
  arXiv  Detail & Related papers  (2022-08-19T19:01:30Z)
• Spectral learning of multivariate extremes [0.0]
  We propose a spectral clustering algorithm for analyzing the dependence structure of multivariate extremes. Our work studies the theoretical performance of spectral clustering based on a random $k-nearest neighbor graph constructed from an extremal sample. We propose a simple consistent estimation strategy for learning the angular measure.
  arXiv  Detail & Related papers  (2021-11-15T14:33:06Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)

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.