The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Nous étudions un problème de recherche du minimum, dans lequel chaque utilisateur a une valeur réelle, et nous voulons estimer le minimum de ces valeurs sous la contrainte de confidentialité différentielle locale. Nous révélons que ce problème est fondamentalement difficile et que nous ne pouvons pas construire un mécanisme cohérent dans le pire des cas. Au lieu de considérer le pire des cas, nous visons à construire un mécanisme privé dont le taux d’erreur s’adapte à la facilité d’estimation du minimum. Pour mesurer la simplicité, nous introduisons un paramètre α qui caractérise la densité de la queue du côté minimum de la distribution des données utilisateur. En conséquence, nous révélons que le mécanisme peut atteindre O((ln6N/ ε2N)1/2α) erreur sans connaissance de α et le taux d’erreur est presque optimal dans le sens où tout mécanisme encourt Ω((1/ε2N)1/2α) erreur. De plus, nous démontrons que notre mécanisme surpasse un mécanisme naïf par des évaluations empiriques sur des ensembles de données synthétiques. En outre, nous avons mené des expériences sur l'ensemble de données MovieLens et un ensemble de données d'historique d'achat et démontrons que notre algorithme atteint Õ((1/N)1/2α) erreur de manière adaptative à α.
Kazuto FUKUCHI
University of Tsukuba,RIKEN
Chia-Mu YU
National Yang Ming Chiao Tung University
Jun SAKUMA
University of Tsukuba,RIKEN
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.
Copier
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
Copier
@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},}
Copier
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 -