Analyzing Preference Data With Local Privacy: Optimal Utility and Enhanced Robustness
Shaowei Wang, Xuandi Luo, Yuqiu Qian, Jiachun Du, Wenqing Lin, Wei Yang · IEEE Transactions on Knowledge and Data Engineering · 2022
Online service providers benefit from collecting and analyzing preference data from users, including both implicit preference data (e.g., watched videos of a user) and explicit preference data (e.g., ranking data over candidates). However, it brings ethical and legal issues of data privacy at the same time. In this paper, we study the problem of aggregating individual's preference data in the local differential privacy (LDP) setting. One naive approach is to add Laplace random noises, which however suffers from low statistical utility and is fragile to LDP-specific poisoning attacks. Therefore, we propose a novel mechanism to improve the utility and the robustness simultaneously: theadditive mechanism. The additive mechanism randomly outputs a subset of candidates with a probability proportional to their total scores. For preference data with Borda rule over$d$items, its mean squared error bound is optimized from$O(\frac{d^{5}}{n\epsilon ^{2}})$to$O(\frac{d^{4}}{n\epsilon ^{2}})$, and its maximum poisoning risk bound is reduced from$+\infty$to$O(\frac{d^{2}}{n\epsilon })$. We also theoretically investigate minimax lower bounds of$\epsilon$-LDP preference data aggregation, and prove the error rate of$O(\frac{d^{4}}{n\epsilon ^{2}})$is optimal for the Borda rule. Experimental results validate that our proposed approaches averagely reduce estimation error by 50% and are more robust to adversarial poisoning attacks.