mlsanityData to 14 Oct 2026

Optimal Differentially Private Ranking from Pairwise Comparisons

arXiv 2507.09388 ↗First posted 12 Jul 2025math.ST stat.ME stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

Data privacy is a central concern in many applications involving ranking from incomplete and noisy pairwise comparisons, such as recommendation systems, educational assessments, and opinion surveys on sensitive topics. In this work, we propose differentially private algorithms for ranking based on pairwise comparisons. Specifically, we develop and analyze ranking methods under two privacy notions: edge differential privacy, which protects the confidentiality of individual comparison outcomes, and individual differential privacy, which safeguards potentially many comparisons contributed by a single individual. Our algorithms--including a perturbed maximum likelihood estimator and a noisy count-based method--are shown to achieve minimax optimal rates of convergence under the respective privacy constraints. We further demonstrate the practical effectiveness of our methods through experiments on both simulated and real-world data.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 24 of its 53 references that are in the map. First posted on arXiv 12 Jul 2025.

Builds on

24 of 53 references.

References · 24

  1. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  2. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  3. 2018Privately Learning High-Dimensional Distributionscited by 104
  4. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  5. 2015Simple, Robust and Optimal Ranking from Pairwise Comparisonscited by 70
  6. 2015Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependencecited by 61
  7. 2015Between Pure and Approximate Differential Privacycited by 56
  8. 2020Differentially Private Assouad, Fano, and Le Camcited by 55
  9. 2017Spectral Method and Regularized MLE Are Both Optimal for Top-K Rankingcited by 47
  10. 2015Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisonscited by 34
  11. 2017Tight Lower Bounds for Differentially Private Selectioncited by 34
  12. 2015Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issuescited by 32
12 more
  1. 2018The Structure of Optimal Private Tests for Simple Hypothesescited by 26
  2. 2017Differentially Private Testing of Identity and Closeness of Discrete Distributionscited by 25
  3. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  4. 2021Oneshot Differentially Private Top-k Selectioncited by 16
  5. 2020The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Boundscited by 15
  6. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 10
  7. 2014The Application of Differential Privacy for Rank Aggregation: Privacy and Accuracycited by 6
  8. 2016Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisonscited by 6
  9. 2016Competitive analysis of the top-K ranking problemcited by 6
  10. 2019Private Rank Aggregation under Local Differential Privacycited by 5
  11. 2022Distributed Differentially Private Ranking Aggregationcited by 3
  12. 2025Differential Privacy Meets Invariant Statistics: Some Conundrums in Quantifying Trade-Offscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Privacy utility trade offs for parameter estimation in degree heterogeneous higher order networkscited by 0