Pith. sign in

REVIEW 4 major objections 5 minor 56 references

Optimal Differentially Private Ranking from Pairwise Comparisons

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Adding calibrated noise to win counts achieves the exact minimax rate for private ranking from pairwise comparisons.

desk verdict The upper-bound half is solid and worth publishing; the exact-recovery lower bound collapses at m=0, so the minimax optimality claim is currently unsupported. read the letter →

arxiv 2507.09388 v1 pith:PUYKYFOZ submitted 2025-07-12 math.ST stat.MEstat.MLstat.TH

T. Tony Cai , Abhinav Chakraborty , Yichen Wang This is my paper · ORCID
classification math.STstat.MEstat.MLstat.TH MSC 62F0762C2062G05
keywords differentialprivacyrankingpairwisecomparisonsBradley-Terry-Lucemodelminimaxoptimalitytop-kselectionLaplacemechanismentrywiseestimation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks a sharp question: if pairwise comparison outcomes must be kept differentially private, how accurately can the true ranking still be recovered? It answers that question with exact minimax thresholds for two privacy notions. Under edge DP, which hides any single comparison, top-k recovery is possible exactly when the gap between the k-th and (k+1)-th average win probabilities exceeds $C(\sqrt{\log n/(np)} + \log n/(np\varepsilon))$; under individual DP, which hides all comparisons of one user, the threshold becomes $C(\sqrt{n\log n/m} + n\log n/(m\varepsilon))$. Both thresholds are achieved by simple Laplace-noised counting algorithms and are shown to be unavoidable by matching lower bounds. In the parametric Bradley-Terry-Luce model, a perturbed maximum likelihood estimator attains the same entrywise rate and is minimax optimal. If correct, the results mean no privacy-preserving ranking method can do better, and the privacy loss is exactly quantified.

What carries the argument

The central machinery is the Laplace mechanism applied twice: to per-item win counts for the nonparametric top-k estimator, and to the objective function of the MLE for parametric estimation. The accuracy analysis rests on a leave-one-out induction that controls entrywise errors of the perturbed optimizer, while the lower bounds use an entrywise adaptation of the score attack—a technique that compares an estimator's score across adjacent data sets—and a differentially private Fano inequality used to build packing arguments for top-k selection.

What would settle it

Run the individual-DP experiment with $n=300$ items, $m=1000$ users, and per-user comparison counts $L$ drawn from a Poisson(5) distribution; if an algorithm that adds Laplace noise at scale $\max_i L_i/\varepsilon$ succeeds at the claimed threshold while the fixed-$L$ noisy-count algorithm fails, the fixed-$L$ assumption is load-bearing.

Watch

Extended reading notes

Core claim

The paper establishes that the minimax threshold for recovering the top-k set under edge differential privacy is $\sqrt{\log n/(np)} + \log n/(np\varepsilon)$, and under individual differential privacy is $\sqrt{n\log n/m} + n\log n/(m\varepsilon)$; Theorems 2.3, 2.4, 3.3 and 3.4 show these thresholds are simultaneously sufficient and necessary for any $(\varepsilon,\delta)$-differentially private algorithm. The upper bounds are achieved by ranking items according to Laplace-perturbed win counts, and in the parametric setting by a perturbed MLE whose $\ell_\infty$ rate matches the same threshold. The lower bounds hold even when the comparison probabilities are restricted to a parametric form, which closes the $O(\log n)$ gap between the parametric upper and lower bounds and makes the perturbed MLE minimax optimal for estimating latent scores.

Load-bearing premise

The sharp rates rely on a balanced sampling model: the edge-DP results assume a random comparison graph with known edge probability $p$, and the individual-DP results assume every user contributes exactly $L$ uniformly random pairs; outside these schemes the claimed minimax thresholds are not shown to hold.

Editorial extensions

If this is right

  • No differentially private algorithm can recover the true top-k set with high probability when the gap $\tau_{(k)}-\tau_{(k+1)}$ falls below the edge-DP threshold, so the noisy-count method cannot be improved in rate.
  • Under individual DP, increasing the number of items $n$ makes private ranking harder because the threshold grows with $n$, whereas under edge DP larger $n$ helps; this reverses the usual non-private intuition.
  • The perturbed MLE's $\ell_\infty$ rate matches the nonparametric top-k threshold, so privately estimating latent scores is no harder in rate than directly selecting the top-k set.
  • Because the proposed algorithms satisfy pure $(\varepsilon,0)$-DP, the minimax rate for approximate $(\varepsilon,\delta)$-DP is no better than for pure DP in this ranking problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural testable extension would replace the fixed per-user comparison count $L$ with a random or user-dependent count; the rate would plausibly depend on the maximum $L$ across users rather than the mean, which the current theorems do not cover.
  • The entrywise score-attack bound is likely reusable for other private estimation problems that target $\ell_\infty$ or entrywise accuracy, such as private network estimation or private matrix completion.
  • The identical privacy cost term across parametric and nonparametric settings suggests the privacy term $\log n/(np\varepsilon)$ is a fundamental selection cost for private top-k under graph sampling, so one might expect it to reappear in other graph-based private selection problems.
  • The real-data experiments indicate that moderate privacy levels around $\varepsilon=2.5$ already track non-private ranks closely on small item sets; this is an empirical observation rather than a theorem, but it offers a practical starting point for choosing $\varepsilon$ in survey settings.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. This paper studies differentially private ranking from pairwise comparisons under two adjacency notions: edge DP (protecting one comparison/edge) and individual DP (protecting all L comparisons of one user). The authors propose a Laplace-perturbed count algorithm for nonparametric top-k recovery and an objective-perturbed MLE for the parametric BTL-type model. The main theoretical claims are minimax rates: under edge DP, separation |τ(k)-τ(k+1)| ≳ sqrt(log n/(np)) + log n/(npε) is sufficient and necessary for top-k recovery, and the perturbed MLE achieves the corresponding ℓ∞ rate; under individual DP, the analogous thresholds are sqrt(n log n/m) + n log n/(mε). Numerical experiments on simulated and two real datasets are reported. The proofs are in a long appendix; the upper-bound arguments follow the leave-one-out analysis of Chen et al. (2019), and the lower-bound arguments adapt score attacks and DP-Fano inequalities.

Significance. If the results are fully established, the paper would provide a fairly complete picture of the minimax cost of privacy for pairwise-comparison ranking, including the interesting contrast that edge-DP rates improve with n while individual-DP rates degrade with n. The upper-bound proofs are detailed and the algorithms are simple and practical, with explicit O(n^-5) failure bounds; the numerical comparison against the one-shot method of Qiao et al. is a useful addition. The paper also makes a methodological contribution by extending objective perturbation to entrywise (ℓ∞) analysis and by adapting score attacks to entrywise lower bounds. However, the exact-recovery lower-bound proofs contain a genuine collapse in the Fano construction, and the individual-DP count mechanism's privacy guarantee is off by a factor of two, so the advertised optimality claims are not currently established.

major comments (4)
  1. [Theorem 2.4, Section A.7.1; Theorem 3.4, Section B.5] The exact-recovery specializations 'Setting m=0 in Theorem 2.4' and 'exact recovery (u=0)' are not supported by the proofs as written. In A.7.1 the Fano packing has M = exp((9/10)ν1ν2 m log n) hypotheses; at m=0 this gives M=1, so the DP-Fano bound in Theorem A.1 contains the factor (M−1)/e^{10εD}=0 and cannot yield (2.12). The same collapse occurs in B.5 at u=0. The fallback of applying Theorem 2.4 with m=1 would impose δ < c0 ε/(log n · n^{10}), which excludes the δ ≲ n^{-1} regime claimed for approximate DP. Consequently Corollary 2.2's necessity, Remark 1's claim that the O(log n) gap is closed, and Theorem 3.2's lower bound (which depends on the rank-recovery lower bound) are not established in the exact-recovery case.
  2. [Section 3.3, Algorithm 3] Algorithm 3 is claimed to be (ε,0)-DP by the Laplace mechanism because 'replacing one user's L comparisons can change each Ni by at most L'. This is the ℓ∞ sensitivity, not the ℓ1 sensitivity of the count vector. A single user may compare the same pair L times and all L outcomes may flip, changing (Na, Nb) by (−L, +L), so the ℓ1 sensitivity of the query is 2L. The standard Laplace mechanism therefore requires noise scale 2L/ε, not L/ε; with scale L/ε the mechanism is only 2ε-DP. This does not change the rate in Theorem 3.3, but the stated privacy guarantee is incorrect.
  3. [Appendix A.1, proof of Proposition 2.1] In the proof of Proposition 2.1, the density of eθ is written as (2λ)^{-n} exp(−∥∇R(t;y)∥1/λ) |det(∂∇R(t;y)/∂t)|^{-1}. The change of variables from w to θ gives the Jacobian |det(∂∇R/∂t)| to the first power, not the −1 power. As printed, the subsequent density ratio f_eθ(y)(t)/f_eθ(y')(t) would be the reciprocal of the expression used, and the determinant bound would not follow. The ratio written immediately afterwards uses the correct +1 Jacobian, so this appears to be a typo, but it must be corrected for the proof to be valid.
  4. [Section B.3, proof of Theorem 3.2] The proof of Theorem 3.2 is only a sketch and is not a valid reduction as written. It defines rn as the 'minimax separation rate for top-K recovery' and asserts without proof that two parameter vectors differing in one gap of size 100an force any estimator with ℓ∞ error ≤ 10an to recover the top-K set with probability 0.9; it also does not ensure the constructed vectors satisfy the global constraint ∥θ∥∞≤1 or that all other gaps are large. Since Theorem 3.2 is a central claimed lower bound, this argument needs to be written out, and it also depends on the exact-recovery lower bound flagged in the first comment.
minor comments (5)
  1. [Notation, Sections 2 and 3] The symbol m is used for the tolerance in Section 2 and for the number of users in Section 3; this overloaded notation makes statements such as 'Setting m=0 in Theorem 2.4' easy to confuse with the individual-DP user count.
  2. [Section B.5] In the proof of Theorem 3.4, the formulas 'M = e^{9/10ν1ν2m log n}' and 'dH(S^a_j, S^b_j) > 4m' use m where the tolerance u is meant; this appears to be a copy-paste error.
  3. [Appendix A.2.1 and A.2.2] The text refers to 'Proposition 2.5' where the intended reference appears to be Proposition 2.2; please check all such cross-references.
  4. [Section 2.3.2] The definitions of eΘ(k,m,2c) before Theorem 2.4 and the statement of Theorem 2.4 use different constants (2c versus c); the proof would be clearer if the same symbol were used throughout.
  5. [Section 4] Several figures have garbled axis labels in the text version (for example, 'log relative L error'), which makes them hard to read; please replace them with high-resolution renderings.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's minimax upper and lower bounds are derived from explicit DP mechanisms and standard external Fano/score constructions, not from the statements being proved.

full rationale

The claimed optimality results are not assumed as inputs. The upper bounds are constructive: Algorithm 1's perturbed MLE is shown to be (ε,0)-DP by an objective-perturbation density ratio (Prop. 2.1) and its ℓ∞ rate is obtained by a leave-one-out induction (Prop. 2.2, sketched in Sec. A.2), while Algorithms 2 and 3 are analyzed directly via Bernstein/Chernoff bounds (Thms. 2.3 and 3.3). The lower bounds use the DP-Fano inequality (Theorem A.1), the packing construction of Shah-Wainwright [45], and a re-derived entrywise score attack (Props. 2.3-2.4); none of these is replaced by a statement equivalent to the target theorem. Self-citations — to the supplement [10] for proof details and to [13] for the score-attack technique — are not load-bearing: the body contains the proofs or proof skeletons, and [13] supplies a technique rather than the ranking optimality claim. The individual-DP fixed-L assumption is an acknowledged scope limitation, not a circular input. A gap in the exact-recovery case of the Fano construction (m=0 or u=0 makes M=1 and the private term vanish) is a correctness issue in the lower-bound argument, not a circular reduction: the upper bounds and the non-private lower bound stand independently.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central claims rest on a few model assumptions (link regularity, balanced random sampling, bounded scores) and one implementer-chosen constant c0. The noise scales are determined by the privacy parameter. No new entities are postulated.

free parameters (2)
  • Regularization constant c0 in γ = c0 sqrt(np log n) = not specified; theory requires a sufficiently large absolute constant
    Algorithm 1 and Theorem 2.1 set γ = c0 sqrt(np log n). The paper never gives a concrete value, so the algorithm as stated depends on an implementer-chosen constant. This constant affects the privacy-utility tradeoff in practice.
  • Noise scale λ = 8κ1/ε for the edge DP perturbed MLE = 8κ1/ε
    λ is prescribed by the privacy parameter ε and the link-function constant κ1, so it is not fitted to data, but it is a design choice that must be computed from the model.
assumptions (6)
  • domain assumption Link function F satisfies (A0): strictly increasing and F(x) = 1 - F(-x)
    Used throughout Section 2.2 to define the parametric model and to construct the parametric lower bound in Theorem 2.4.
  • domain assumption Link function satisfies (A1): sup_x F'(x)/(F(x)(1-F(x))) < κ1
    Controls the gradient sensitivity of the negative log-likelihood, used in Proposition 2.1's privacy proof and in the score attack lower bound.
  • domain assumption Link function satisfies (A2): second derivative of -log F is positive with upper and lower bounds
    Ensures strong convexity and the Hessian ratio bounds needed for the leave-one-out analysis in Proposition 2.2.
  • domain assumption Comparison graph is Erdős-Rényi G(n,p) with known p (edge DP) or each user draws L pairs uniformly at random (individual DP)
    The density of comparisons is the backbone of all rate computations; optimality is stated only under this balanced sampling scheme (Sections 2.1 and 3.1).
  • domain assumption Parameter space Θ = {θ in R^n : ||θ||_∞ ≤ 1} and the centering 1^T θ* = 0
    Boundedness is needed for the lower bound priors and for the equivalence |τ(k) - τ(k+1)| ≍ |θ*(k) - θ*(k+1)| used in Remark 1.
  • standard math The hypothesis construction of Shah-Wainwright [45] exists under 2m ≤ (1+ν2)^{-1} min{n^{1-ν1}, k, n-k}
    Borrowed as a black box to build separated top-k sets with controlled KL/TV distances in Theorems 2.4 and 3.4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Differentially Private Ranking from Pairwise Comparisons." pith.science (2026). https://pith.science/paper/PUYKYFOZ

@misc{pith2026250709388,
  author       = {Pith},
  title        = {Pith review of: Optimal Differentially Private Ranking from Pairwise Comparisons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PUYKYFOZ}},
  note         = {Machine review of arXiv:2507.09388}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2507.09388 by the authors.

Figure 1
Figure 1. Edge DP estimation errors versus the number of items [PITH_FULL_IMAGE:figures/full_fig_p024_1.png] view at source ↗
Figure 2
Figure 2. Edge DP estimation errors versus the edge probability [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗
Figure 3
Figure 3. Edge DP errors versus the privacy parameter [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Relative Hamming errors of our algorithms and the one-shot algorithm in [ [PITH_FULL_IMAGE:figures/full_fig_p026_4.png]
Figure 5
Figure 5. Figure 5: Individual DP errors versus the number of items [PITH_FULL_IMAGE:figures/full_fig_p027_5.png]
Figure 6
Figure 6. Figure 6: Individual DP errors versus the number of individuals [PITH_FULL_IMAGE:figures/full_fig_p027_6.png]
Figure 7
Figure 7. Figure 7: Individual DP errors versus the privacy level [PITH_FULL_IMAGE:figures/full_fig_p028_7.png]
Figure 8
Figure 8. Figure 8: Mean rank difference versus ε. Left: CEMS data. Right: immigration data. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 50 canonical work pages

  1. [10]

    optimal differentially private ranking from pairwise comparisons

    T. T. Cai, A. Chakraborty, and Y. Wang. Supplement to “optimal differentially private ranking from pairwise comparisons”, 2023. Supplemental Material

    work page 2023

  2. [1]

    Acharya, Z

    J. Acharya, Z. Sun, and H. Zhang. Differentially private testing of identity and closeness of discrete distributions. In Adv. Neural Inf. Process. Syst. , pages 6878–6891, 2018

    work page 2018

  3. [2]

    Acharya, Z

    J. Acharya, Z. Sun, and H. Zhang. Differentially private Assouad, Fano, and Le Cam. In Algorithmic Learning Theory, pages 48–78. PMLR, 2021

    work page 2021

  4. [3]

    Bailie, R

    J. Bailie, R. Gong, and X.-L. Meng. A refreshment stirred, not shaken (iii): Can swapping be differentially private? In R. Gong, V. J. Hotz, and I. M. Schmutte, editors, Data Privacy Pro- tection and the Conduct of Applied Research: Methods, Approaches and Their Consequences . University of Chicago Press, May 2025

    work page 2025

  5. [4]

    Balakrishnan and S

    S. Balakrishnan and S. Chopra. Two of a kind or the ratings game? adaptive pairwise preferences and latent factor models. Frontiers of Computer Science , 6(2):197–208, 2012

    work page 2012

  6. [5]

    R. F. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv:1412.4451 , 2014

    arXiv 2014

  7. [6]

    Bassily, V

    R. Bassily, V. Feldman, K. Talwar, and A. G. Thakurta. Private stochastic convex optimiza- tion with optimal rates. In Adv. Neural Inf. Process. Syst. , pages 11282–11291, 2019

    work page 2019

  8. [7]

    Bassily, A

    R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algo- rithms and tight error bounds. In FOCS 2014, pages 464–473. IEEE, 2014

    work page 2014

Show all 56 references
  1. [8]

    R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952

    1952

  2. [9]

    M. Bun, J. Ullman, and S. Vadhan. Fingerprinting codes and the price of approximate differential privacy. In STOC 2014 , pages 1–10. ACM, 2014

    2014

  3. [11]

    T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy in generalized linear models: Algo- rithms and minimax lower bounds. arXiv preprint arXiv:2011.03900 , 2020

    2011 arXiv

  4. [12]

    T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy: Optimal rates of convergence for 73 parameter estimation with differential privacy. The Annals of Statistics , 49(5):2825–2850, 2021

    2021

  5. [13]

    T. T. Cai, Y. Wang, and L. Zhang. Score attack: A lower bound technique for optimal differentially private learning. arXiv preprint arXiv:2303.07152 , 2023

    2023 arXiv

  6. [14]

    C. L. Canonne, G. Kamath, A. McMillan, A. Smith, and J. Ullman. The structure of optimal private tests for simple hypotheses. arXiv preprint arXiv:1811.11148 , 2018

    2018 arXiv

  7. [15]

    Chaudhuri and C

    K. Chaudhuri and C. Monteleoni. Privacy-preserving logistic regression. In Adv. Neural Inf. Process. Syst., pages 289–296, 2009

    2009

  8. [16]

    Chaudhuri, C

    K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research , 12(Mar):1069–1109, 2011

    2011

  9. [17]

    X. Chen, S. Gopi, J. Mao, and J. Schneider. Competitive analysis of the top- k ranking problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1245–1264. SIAM, 2017

    2017

  10. [18]

    Y. Chen, J. Fan, C. Ma, and K. Wang. Spectral method and regularized mle are both optimal for top-k ranking. Ann. Statist., 47(4):2204, 2019

    2019

  11. [19]

    Chen and C

    Y. Chen and C. Suh. Spectral mle: Top- k rank aggregation from pairwise comparisons. In ICML 2015 , pages 371–380. PMLR, 2015

    2015

  12. [20]

    Desfontaines

    D. Desfontaines. A list of real-world uses of differential privacy. https://desfontain. es/blog/real-world-differential-privacy.html , 2021. Ted is writing things (personal blog)

    2021

  13. [21]

    Dittrich, R

    R. Dittrich, R. Hatzinger, and W. Katzenbeisser. Modelling the effect of subject-specific covariates in paired comparison studies with an application to university rankings. J. R. Statist. Soc. C , 47(4):511–525, 1998

    1998

  14. [22]

    Dwork, K

    C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages 486–503. Springer, 2006. 74

    2006

  15. [23]

    Dwork, F

    C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC 2006 , pages 265–284. Springer, 2006

    2006

  16. [24]

    Dwork and A

    C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science , 9(3–4):211–407, 2014

    2014

  17. [25]

    Dwork, A

    C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan. Robust traceability from trace amounts. In FOCS 2015, pages 650–669. IEEE, 2015

    2015

  18. [26]

    Dwork, K

    C. Dwork, K. Talwar, A. Thakurta, and L. Zhang. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In STOC 2014 , pages 11–20. ACM, 2014

    2014

  19. [27]

    L. R. Ford Jr. Solution of a ranking problem from binary comparisons. The American Mathematical Monthly, 64(8P2):28–33, 1957

    1957

  20. [28]

    M. Hay, L. Elagina, and G. Miklau. Differentially private rank aggregation. In Proceedings of the 2017 SIAM International Conference on Data Mining , pages 669–677. SIAM, 2017

    2017

  21. [29]

    Heldsinger and S

    S. Heldsinger and S. Humphry. Using the method of pairwise comparison to obtain reliable teacher assessments. The Australian Educational Researcher, 37(2):1–19, 2010

    2010

  22. [30]

    Kamath, J

    G. Kamath, J. Li, V. Singhal, and J. Ullman. Privately learning high-dimensional distribu- tions. arXiv preprint arXiv:1805.00216 , 2018

    2018 arXiv

  23. [31]

    Karwa and S

    V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03908, 2017

    2017 arXiv

  24. [32]

    S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography Conference , pages 457–476. Springer, 2013

    2013

  25. [33]

    Kifer, A

    D. Kifer, A. Smith, and A. Thakurta. Private convex empirical risk minimization and high- dimensional regression. In COLT 2012, pages 25.1–25.40, 2012

    2012

  26. [34]

    S. Lang. Real and Functional Analysis , volume 142. Springer Science & Business Media, 2012

    2012

  27. [35]

    J. Lei. Differentially private M-estimators. In NeurIPS 2011 , pages 361–369, 2011. 75

    2011

  28. [36]

    R. D. Luce. Individual Choice Behavior. John Wiley, 1959

    1959

  29. [37]

    Negahban, S

    S. Negahban, S. Oh, and D. Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1):266–287, 2017

    2017

  30. [38]

    Nissim, S

    K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 75–84, 2007

    2007

  31. [39]

    Pananjady, C

    A. Pananjady, C. Mao, V. Muthukumar, M. J. Wainwright, and T. A. Courtade. Worst-case versus average-case design for estimation from partial pairwise comparisons. Ann. Statist. , 48(2):1072–1097, 2020

    2020

  32. [40]

    G. Qiao, W. Su, and L. Zhang. Oneshot differentially private top-k selection. In International Conference on Machine Learning , pages 8672–8681. PMLR, 2021

    2021

  33. [41]

    Rajkumar and S

    A. Rajkumar and S. Agarwal. A statistical convergence perspective of algorithms for rank aggregation from pairwise data. In ICML 2014 , pages 118–126. PMLR, 2014

    2014

  34. [42]

    N. Shah, S. Balakrishnan, J. Bradley, A. Parekh, K. Ramchandran, and M. Wainwright. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. In Artificial Intelligence and Statistics , pages 856–865. PMLR, 2015

    2015

  35. [43]

    N. Shah, S. Balakrishnan, A. Guntuboyina, and M. Wainwright. Stochastically transitive models for pairwise comparisons: Statistical and computational issues. In ICML 2016, pages 11–20. PMLR, 2016

    2016

  36. [44]

    N. B. Shah, S. Balakrishnan, and M. J. Wainwright. Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons. IEEE Trans. Inf. Theory , 65(8):4854–4874, 2019

    2019

  37. [45]

    N. B. Shah and M. J. Wainwright. Simple, robust and optimal ranking from pairwise com- parisons. J. Mach. Learn. Res. , 18(1):7246–7283, 2017

    2017

  38. [46]

    Shang, T

    S. Shang, T. Wang, P. Cuff, and S. Kulkarni. The application of differential privacy for rank aggregation: Privacy and accuracy. In 17th International Conference on Information Fusion (FUSION), pages 1–7. IEEE, 2014. 76

    2014

  39. [47]

    B. Song, Q. Lan, Y. Li, and G. Li. Distributed differentially private ranking aggregation. arXiv preprint arXiv:2202.03388 , 2022

    2022 arXiv

  40. [48]

    Steinke and J

    T. Steinke and J. Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality , 7(2), 2017

    2017

  41. [49]

    Steinke and J

    T. Steinke and J. Ullman. Tight lower bounds for differentially private selection. In FOCS 2017, pages 552–563. IEEE, 2017

    2017

  42. [50]

    L. L. Thurstone. A law of comparative judgment. Psychol. Rev., 34(4):273, 1927

    1927

  43. [51]

    J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of compu- tational mathematics , 12:389–434, 2012

    2012

  44. [52]

    Vershynin

    R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  45. [53]

    Wasserman and S

    L. Wasserman and S. Zhou. A statistical framework for differential privacy. J. Am. Stat. Assoc., 105(489):375–389, 2010

    2010

  46. [54]

    Wauthier, M

    F. Wauthier, M. Jordan, and N. Jojic. Efficient ranking from pairwise comparisons. In ICML 2013, pages 109–117. PMLR, 2013

    2013

  47. [55]

    Weber and R

    D. Weber and R. Hatzinger. A novel approach for modelling paired comparisons data with non-ignorable missing values on student’s attitudes towards foreigners. Data Analysis Bul- letin, 12:11–22, 2011

    2011

  48. [56]

    Z. Yan, G. Li, and J. Liu. Private rank aggregation under local differential privacy. Interna- tional Journal of Intelligent Systems , 35(10):1492–1519, 2020. 77

    2020

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.