Locally Differentially Private Minimum Finding

Kazuto FUKUCHI
Chia-Mu YU
Jun SAKUMA

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E105-D    No.8    pp.1418-1430
Publication Date: 2022/08/01
Publicized: 2022/05/11
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2021EDP7187
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword: 
privacy,  local differential privacy,  minimum finding,  estimation error analysis,  heavy-tailed distributions,  

Full Text: PDF(1.5MB)>>
Buy this Article



Summary: 
We investigate a problem of finding the minimum, in which each user has a real value, and we want to estimate the minimum of these values under the local differential privacy constraint. We reveal that this problem is fundamentally difficult, and we cannot construct a consistent mechanism in the worst case. Instead of considering the worst case, we aim to construct a private mechanism whose error rate is adaptive to the easiness of estimation of the minimum. As a measure of easiness, we introduce a parameter α that characterizes the fatness of the minimum-side tail of the user data distribution. As a result, we reveal that the mechanism can achieve O((ln6N2N)1/2α) error without knowledge of α and the error rate is near-optimal in the sense that any mechanism incurs Ω((1/ε2N)1/2α) error. Furthermore, we demonstrate that our mechanism outperforms a naive mechanism by empirical evaluations on synthetic datasets. Also, we conducted experiments on the MovieLens dataset and a purchase history dataset and demonstrate that our algorithm achieves Õ((1/N)1/2α) error adaptively to α.


open access publishing via