Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation

We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed order-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), exact optimality (in the non-asymptotic setting) still has not been achieved. In this work, we take a step towards characterizing the exact-optimal approach in the presence of shared randomness (a random variable shared between the server and the user) and identify several conditions for exact optimality. We prove that one of the conditions is to utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is a randomly rotated simplex -satisfying the properties of the exact-optimal codebook. The proposed mechanism is based on a k-closest encoding which we prove to be exact-optimal for the randomly rotated simplex codebook. Another important consideration in the applications of mean estimation is the communication cost during user data collection. For instance, in federated learning, clients need to send overparameterized machine learning models at every round, which becomes a significant bottleneck due to limited resources and bandwidth available to the clients [22, 25, 28] . This has motivated extensive research on