The search functionality is under construction.

The search functionality is under construction.

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*((ln^{6}*N*/ε^{2}*N*)^{1/2α}) error without knowledge of α and the error rate is near-optimal in the sense that any mechanism incurs Ω((1/ε^{2}*N*)^{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

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.

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*((ln^{6}*N*/ε^{2}*N*)^{1/2α}) error without knowledge of α and the error rate is near-optimal in the sense that any mechanism incurs Ω((1/ε^{2}*N*)^{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*((ln^{6}*N*/ε^{2}*N*)^{1/2α}) error without knowledge of α and the error rate is near-optimal in the sense that any mechanism incurs Ω((1/ε^{2}*N*)^{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*((ln^{6}*N*/ε^{2}*N*)^{1/2α}) error without knowledge of α and the error rate is near-optimal in the sense that any mechanism incurs Ω((1/ε^{2}*N*)^{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 -