NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID: 3435 Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation

This paper provides order-optimal results for distributed mean estimation when the vectors are sparse. With matching upper and lower bounds, the results form a nice and fairly complete story. In terms of techniques, however, the achievable scheme doesn't really require any "new tricks": in a sense the message of the paper is that an appropriately chosen uniform coordinate-wise quantizer is the right thing to do. The reviewers have made several suggestions that could improve the paper, in particular with respect to describing the results and the experiments. A bit more careful accounting of the rounds of communication would avoid confusion. With those changes the paper would be very solid. Since the scheme is not so baroque, I would encourage the authors to make their paper inviting to those outside the area (e.g. practitioners) since simple schemes that provably work are often quite welcome.