Optimal Algorithms for Mean Estimation under Local Differential Privacy
This work addresses the practical performance gap in local differential privacy for mean estimation, which is incremental as it optimizes existing methods rather than introducing a new paradigm.
The paper tackles the problem of designing locally differentially private mean estimation protocols with minimal variance, showing that an optimized version of PrivUnit achieves optimal variance among a large family of randomizers and introducing a Gaussian-based variant for better analysis and numerical estimation of error constants.
We study the problem of mean estimation of $\ell_2$-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the asymptotically optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the protocol with the smallest variance. We show that PrivUnit (Bhowmick et al. 2018) with optimized parameters achieves the optimal variance among a large family of locally private randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.