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 mean difference, etc. We give several novel algorithms for the problem, leveraging techniques from DP algorithms for linear queries.
