OPTT: Optimal Piecewise Transformation Technique for Analyzing Numerical Data under Local Differential Privacy
This work addresses privacy-preserving data analysis for applications requiring local differential privacy, offering incremental improvements in variance optimization for numerical data.
The paper tackles the problem of analyzing numerical data under local differential privacy by proposing a principled framework for piecewise transformation techniques (PTTs), showing that many PTTs are asymptotically optimal for mean estimation and can achieve theoretical lower bounds on variance, with some outperforming existing methods like Duchi's scheme in worst-case variance scenarios.
Privacy preserving data analysis (PPDA) has received increasing attention due to a great variety of applications. Local differential privacy (LDP), as an emerging standard that is suitable for PPDA, has been widely deployed into various real-world scenarios to analyze massive data while protecting against many forms of privacy breach. In this study, we are mainly concerned with piecewise transformation technique (PTT) for analyzing numerical data under local differential privacy. We provide a principled framework for PTT in the context of LDP, based on which PTT is studied systematically. As a result, we show that (1) many members in PTTs are asymptotically optimal when used to obtain an unbiased estimator for mean of numerical data, and (2) for a given privacy budget, there is PTT that reaches the theoretical low bound with respect to variance. Next, we prove by studying two classes of PTTs in detail that (1) there do not exist optimal PTTs compared to the well-used technique, i.e., Duchi's scheme, in terms of the consistency noisy variance, (2) on the other hand, one has the ability to find a great number of PTTs that are consistently more optimal than the latter with regard to the worst-case noisy variance, which is never reported so far. When we are restricted to consider only the high privacy level, enough PTTs turn out to be optimal than the well-known Laplace mechanism. Lastly, we prove that for a family of PTTs, the correspondingly theoretical low bound of noisy variance follows $O(ε^{-2})$ when considering the high privacy level.