Locally Differentially Private Minimum Finding
This work addresses privacy-preserving data analysis for applications like recommendation systems, but it is incremental as it builds on existing differential privacy frameworks with a focus on adaptive error rates.
The paper tackles the problem of estimating the minimum value from user data under local differential privacy constraints, revealing that consistent worst-case mechanisms are impossible and proposing an adaptive mechanism that achieves an error rate of O((ln^6N/ε^2N)^{1/2α}), which is near-optimal compared to a lower bound of Ω((1/ε^2N)^{1/2α}).
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 mechanism that is consistent 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^6N/ε^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 $\tilde{O}((1/N)^{1/2α})$ error adaptively to $α$.