Locally Differentially Private Minimum Finding
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((ln6N/ε2N)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 α.
- Publication
- IEICE TRANSACTIONS on Information 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
Authors
Kazuto FUKUCHI
University of Tsukuba,RIKEN
Chia-Mu YU
National Yang Ming Chiao Tung University
Jun SAKUMA
University of Tsukuba,RIKEN
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuto FUKUCHI, Chia-Mu YU, Jun SAKUMA, "Locally Differentially Private Minimum Finding" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 8, pp. 1418-1430, August 2022, doi: 10.1587/transinf.2021EDP7187.
Abstract: 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((ln6N/ε2N)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 α.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7187/_p
Copy
@ARTICLE{e105-d_8_1418,
author={Kazuto FUKUCHI, Chia-Mu YU, Jun SAKUMA, },
journal={IEICE TRANSACTIONS on Information},
title={Locally Differentially Private Minimum Finding},
year={2022},
volume={E105-D},
number={8},
pages={1418-1430},
abstract={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((ln6N/ε2N)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 α.},
keywords={},
doi={10.1587/transinf.2021EDP7187},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - Locally Differentially Private Minimum Finding
T2 - IEICE TRANSACTIONS on Information
SP - 1418
EP - 1430
AU - Kazuto FUKUCHI
AU - Chia-Mu YU
AU - Jun SAKUMA
PY - 2022
DO - 10.1587/transinf.2021EDP7187
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2022
AB - 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((ln6N/ε2N)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 α.
ER -
English
