HyperMean: Effective Multidimensional Mean Estimation with Local Differential Privacy

Multidimensional mean estimation with local differential privacy (LDP) extracts the numerical features from groups while protecting users’ personal information without relying on a trusted server. However, the increase of dimensionality would lead to a deficiency in the allocable privacy budget, resulting in excessive accuracy loss. To solve this problem, we propose HyperMean, an effective privacy-preserving mean estimation mechanism for multidimensional data whose accuracy is at least no worse (and better in most cases) than existing solutions. We first design a multidimensional staircase function to obfuscate users’ data, significantly reducing the output variance. Second, an adaptive dimensionality reduction is performed on users’ data to allocate the privacy budget to some focused dimensions. Finally, the server averages all users’ obfuscated outputs to obtain an unbiased estimate of the mean results. Theoretical analysis reveals that HyperMean effectively reduces the worst-case variance of multidimensional mean estimation under LDP while maintaining low computational complexity. Experiments on both simulated and real-world datasets show that HyperMean outperforms existing multidimensional mean estimation mechanisms in terms of aggregated error.