Interval Mean Estimation Under (ε,δ)-Local Differential Privacy

Local differential privacy (LDP) techniques obviate the need for trust in the data collector, as they provide robust privacy guarantees against untrusted data managers while simultaneously preserving the accuracy of statistical information derived from the privatized data. As a result, these methods have garnered considerable interest and research efforts. In particular, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(\varepsilon,\delta)$ </tex-math></inline-formula>-LDP schemes have been utilized across a range of statistical tasks. Nonetheless, existing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(\varepsilon,\delta)$ </tex-math></inline-formula>-LDP mechanisms for mean estimation suffer from challenges such as elevated estimation errors and diminished data utility. To address this problem, we propose two novel <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(\varepsilon,\delta)$ </tex-math></inline-formula>-LDP algorithms for mean estimation. Specifically, we design a one-dimensional piecewise mean estimation algorithm, which perturbs the input data into intervals, thereby reducing noise addition and enhancing both accuracy and efficiency. Building on this foundation, we extend our approach to multi-dimensional data, resulting in a multi-dimensional piecewise mean estimation algorithm. Furthermore, we conduct a theoretical analysis to derive both the variance and error bounds for the proposed algorithms. Extensive experiments conducted on real datasets demonstrate the high practicality of our algorithms for data statistical tasks, showing significant improvements in data utility.