Local differential privacy (LDP) can provide each user with strong privacy guarantees under untrusted data curators while ensuring accurate statistics derived from privatized data. Due to its powerfulness, LDP has been widely adopted to protect privacy in various tasks (e.g., heavy hitters discovery, probability estimation) and systems (e.g., Google Chrome, Apple iOS). Although @math -LDP has been proposed for many years, the more general notion of @math -LDP has only been studied in very few papers, which mainly consider mean estimation for numeric data. Besides, prior solutions achieve @math -LDP by leveraging Gaussian mechanism, which leads to low accuracy of the aggregated results. In this paper, we propose novel mechanisms that achieve @math -LDP with high utility in data analytics and machine learning. Specifically, we first design @math -LDP algorithms for collecting multi-dimensional numeric data, which can ensure higher accuracy than the optimal Gaussian mechanism while guaranteeing strong privacy for each user. Then, we investigate different local protocols for categorical attributes under @math -LDP. Furthermore, we conduct theoretical analysis on the error bound and variance of the proposed algorithms. Experimental results on real and synthetic datasets demonstrate the high data utility of our proposed algorithms on both simple data statistics and complex machine learning models.
In the setting of @math -LDP , Gaboardi @cite_23 have investigated the upper and lower error bounds of mean estimation when protecting privacy by adding Gaussian noise. Afterward, Joseph @cite_60 further provided a smaller lower bound of mean estimation than Gaboardi @cite_23 . As for heavy hitter discovery problem, Bun @cite_53 have focused on the transformation of approximate local private protocol ( @math -LDP ) into a pure local private protocol ( @math -LDP ). Moreover, under the constraint of @math -LDP , Bassily @cite_34 proposed algorithms for estimating a set of linear queries in both offline setting and adaptive setting and analyzed the accuracy bound of the proposed algorithms. So far, the above mechanisms under @math -LDP are all achieved by the classical Gaussian mechanism @cite_32 , which yields low accuracies of the estimation results. Thus, the goal of this paper is to investigate the mechanisms which can achieve @math -LDP with higher accuracies on estimation results.
@cite_60 @cite_53 @cite_32 @cite_23 @cite_34
2900759811 2963424903 2610910029 2952957879 2895165641
We study a basic private estimation problem: each of @math users draws a single i.i.d. sample from an unknown Gaussian distribution, and the goal is to estimate the mean of this Gaussian distribution while satisfying local differential privacy for each user. Informally, local differential privacy requires that each data point is individually and independently privatized before it is passed to a learning algorithm. Locally private Gaussian estimation is therefore difficult because the data domain is unbounded: users may draw arbitrarily different inputs, but local differential privacy nonetheless mandates that different users have (worst-case) similar privatized output distributions. We provide both adaptive two-round solutions and nonadaptive one-round solutions for locally private Gaussian estimation. We then partially match these upper bounds with an information-theoretic lower bound. This lower bound shows that our accuracy guarantees are tight up to logarithmic factors for all sequentially interactive @math -locally private protocols. We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates which depend optimally on the number of users, the size of the domain, and the privacy parameter, but depend sub-optimally on the failure probability. We strengthen existing lower bounds on the error to incorporate the failure probability, and show that our new upper bound is tight with respect to this parameter as well. Our lower bound is based on a new understanding of the structure of locally private protocols. We further develop these ideas to obtain the following general results beyond heavy hitters. (1) Advanced Grouposition: In the local model, group privacy for k users degrades proportionally to root k, instead of linearly in k as in the central model. Stronger group privacy yields improved max-information guarantees, as well as stronger lower bounds (via "packing arguments"), over the central model. (2) Building on a transformation of Bassily and Smith (STOC 2015), we give a generic transformation from any non-interactive approximate-private local protocol into a pure-private local protocol. Again in contrast with the central model, this shows that we cannot obtain more accurate algorithms by moving from pure to approximate local privacy. In this work we provide efficient distributed protocols for generating shares of random noise, secure against malicious participants. The purpose of the noise generation is to create a distributed implementation of the privacy-preserving statistical databases described in recent papers [14,4,13]. In these databases, privacy is obtained by perturbing the true answer to a database query by the addition of a small amount of Gaussian or exponentially distributed random noise. The computational power of even a simple form of these databases, when the query is just of the form Σ i f(d i ), that is, the sum over all rows i in the database of a function f applied to the data in row i, has been demonstrated in [4]. A distributed implementation eliminates the need for a trusted database administrator. The results for noise generation are of independent interest. The generation of Gaussian noise introduces a technique for distributing shares of many unbiased coins with fewer executions of verifiable secret sharing than would be needed using previous approaches (reduced by a factor of n). The generation of exponentially distributed noise uses two shallow circuits: one for generating many arbitrarily but identically biased coins at an amortized cost of two unbiased random bits apiece, independent of the bias, and the other to combine bits of appropriate biases to obtain an exponential distribution. This work provides tight upper- and lower-bounds for the problem of mean estimation under @math -differential privacy in the local model, when the input is composed of @math i.i.d. drawn samples from a normal distribution with variance @math . Our algorithms result in a @math -confidence interval for the underlying distribution's mean @math of length @math . In addition, our algorithms leverage binary search using local differential privacy for quantile estimation, a result which may be of separate interest. Moreover, we prove a matching lower-bound (up to poly-log factors), showing that any one-shot (each individual is presented with a single query) local differentially private algorithm must return an interval of length @math . We study the problem of estimating a set of @math linear queries with respect to some unknown distribution @math over a domain @math based on a sensitive data set of @math individuals under the constraint of local differential privacy. This problem subsumes a wide range of estimation tasks, e.g., distribution estimation and @math -dimensional mean estimation. We provide new algorithms for both the offline (non-adaptive) and adaptive versions of this problem. In the offline setting, the set of queries are fixed before the algorithm starts. In the regime where @math , our algorithms attain @math estimation error that is independent of @math , and is tight up to a factor of @math . For the special case of distribution estimation, we show that projecting the output estimate of an algorithm due to [ 2018] on the probability simplex yields an @math error that depends only sub-logarithmically on @math in the regime where @math . These results show the possibility of accurate estimation of linear queries in the high-dimensional settings under the @math error criterion. In the adaptive setting, the queries are generated over @math rounds; one query at a time. In each round, a query can be chosen adaptively based on all the history of previous queries and answers. We give an algorithm for this problem with optimal @math estimation error (worst error in the estimated values for the queries w.r.t. the data distribution). Our bound matches a lower bound on the @math error for the offline version of this problem [ 2013].