Optimal Algorithms for Mean Estimation under Local Differential Privacy
  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.
