Distributed Mean Estimation for Multi-Message Shuffled Privacy

In this paper, we study distributed mean estimation (DME) under privacy and communication constraints in the multi-message shuffle model. We propose communication-efficient algorithms for privately estimating the mean of bound $\ell_2$-norm and $\ell_{\infty}$-norm norm vectors. Our algorithms are designed by giving unequal privacy at different resolutions of the vector (through binary expansion) and appropriately combining it with co-ordinate sampling. We show that our proposed algorithms achieve order-optimal privacy-communication-performance trade-offs.