Multi-Message Shuffled Privacy in Federated Learning

We study the distributed mean estimation (DME) problem under privacy and communication constraints in the local differential privacy (LDP) and multi-message shuffled (MMS) privacy frameworks. The DME has wide applications in both federated learning and analytics. We propose a communicationefficient and differentially private algorithm for DME of bounded ℓ2-norm and ℓ∞-norm vectors. We analyze our proposed DME schemes showing that our algorithms have orderoptimal privacy-communication-performance trade-offs. Our algorithms are designed by giving unequal privacy assignments at different resolutions of the vector (through binary expansion) and appropriately combining it with coordinate sampling. These results are directly applied to give guarantees on private federated learning algorithms. We also numerically evaluate the performance of our private DME algorithms.