  We study the problem of locally private mean estimation of high-dimensional
vectors in the Euclidean ball. Existing algorithms for this problem either
incur sub-optimal error or have high communication and/or run-time complexity.
We propose a new algorithmic framework, ProjUnit, for private mean estimation
that yields algorithms that are computationally efficient, have low
communication complexity, and incur optimal error up to a $1+o(1)$-factor. Our
framework is deceptively simple: each randomizer projects its input to a random
low-dimensional subspace, normalizes the result, and then runs an optimal
algorithm such as PrivUnitG in the lower-dimensional space. In addition, we
show that, by appropriately correlating the random projection matrices across
devices, we can achieve fast server run-time. We mathematically analyze the
error of the algorithm in terms of properties of the random projections, and
study two instantiations. Lastly, our experiments for private mean estimation
and private federated learning demonstrate that our algorithms empirically
obtain nearly the same utility as optimal ones while having significantly lower
communication and computational cost.
