On Computing Pairwise Statistics with Local Differential Privacy
Abstract
We study the problem of computing pairwise statistics, i.e., ones of the form $\binom{n}{2}^{-1} \sum_{i \ne j} f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $\tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries.
Cite
Text
Ghazi et al. "On Computing Pairwise Statistics with Local Differential Privacy." Neural Information Processing Systems, 2023.Markdown
[Ghazi et al. "On Computing Pairwise Statistics with Local Differential Privacy." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/ghazi2023neurips-computing/)BibTeX
@inproceedings{ghazi2023neurips-computing,
title = {{On Computing Pairwise Statistics with Local Differential Privacy}},
author = {Ghazi, Badih and Kamath, Pritish and Kumar, Ravi and Manurangsi, Pasin and Sealfon, Adam},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/ghazi2023neurips-computing/}
}