  Distributed Mean Estimation (DME), in which $n$ clients communicate vectors
to a parameter server that estimates their average, is a fundamental building
block in communication-efficient federated learning. In this paper, we improve
on previous DME techniques that achieve the optimal $O(1/n)$ Normalized Mean
Squared Error (NMSE) guarantee by asymptotically improving the complexity for
either encoding or decoding (or both). To achieve this, we formalize the
problem in a novel way that allows us to use off-the-shelf mathematical solvers
to design the quantization.
