Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: This paper studies the problem of mean estimation of n vectors in R^d in a distributed setting. There are n machines. Each has one data point, a vector x_v. The goal is to compute the mean of x_v’s for v = 1, …, n with as few bits of communication as possible. 
Their main contribution is using a new quantization method by exploiting the structure of Lattices. The idea is that each machine randomly assigns its point to a nearby lattice point. Then, the lattice point can be expressed by a few bits. While two points might be assigned to the same bit strings (since the lattice has infinitely many points), the hope is that these points are far apart from each other.
Furthermore, we need to ensure that other machines could decode the bit string and obtain the same lattice point again and use this point to compute the average. Thus, another machine would interpret the bit string as a close-by lattice point. Note that since we assume some guarantees that all the x_v's are close to each, it suffices that a machine selects the closest lattice point that its description would match the bit string. 
Experimental evaluation is also provided.

Overall evaluation: The authors consider an essential problem and use an interesting idea to solve it. Adding more discussion and literature review might help improve the paper. The writeup could be improved as well.

Major comments:
- It would be beneficial if the authors discuss and compare the following straightforward approach: We can use a previously known algorithm and allow the machines to obtain a potentially inaccurate estimate of the mean, say \hat \mu. Then, we can run the algorithm again. This time vectors being x_v - \hat \mu. In this step, we bring down the points closer to the center. Thus, the accuracy increases over time. We can repeat this process several times until we achieve the desired accuracy.

- It might be worth looking at a series of papers that studied the mean estimation of random vectors in a non-distributed setting. They mainly focus on the tail behavior of the estimate. They use different estimates other than average, such as the median of means. See “On the estimation of the mean of a random vector” and more recent papers that cited this one.

Minor comments:
- It is unclear from the main text which convex hull is picked. Maybe it worth discussing some high-level explanations in the main text as well.  
- Bottom of page 4: Using Chebyshev’s inequality would only guarantee that a constant fraction of points is within distance O(\sigma \sqrt{n}).
- Abstract, Line 3: where \mu is defined, “\n” is missing.
- Page 2, last paragraph: “thanto” -> other than the
- Page 7, Line 1: O(\sigma^2) -> Shouldn’t be O(\sigma^2/n)?
review_title: Reviewer2

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper considers a particular setting of distributed mean estimation problem, where each party has a vector of potentially large $l_2$ norm, yet this vectors are fairly close to each other. The goal is to communicate as few bits as possible and estimate the mean of the vectors. Previous approaches had the dependence on the size of the ball containing all the vectors, which gives bad bounds if vectors are long (but close to each other).

The idea is to decompose each vectors into a convex hull of points in some lattice, then probabilistically round to one of these points, hash lattice points down to a short string and communicate this string. This allows to recover the points we rounded to for each party and thus estimate the mean.

In order for the communication to be efficient, the cover radius and packing radius should be within $O(1)$ from each other. For $\ell_2$ norm, this is achievable for random lattices, however such lattices are computationally intractable. The authors notice that we can reduce the original mean estimation problem to the $\ell_\infty$ case (incurring the logarithmic loss in the accuracy) and then simply use the cubic lattice.

Overall, I think the result is fairly interesting. None of the techniques are amazingly new (lattice quantization was used before in various context, e.g., locality-sensitive hashing, quantization + hashing down to a short string is a fairly standard idea as well, reduction from $\ell_2$ to $\ell_\infty$ for mean estimation was also used before as well, for, e.g., statistical queries), but I like the clean end result.

One particular request I have is to describe the computationally simple algorithm via the reduction to $\ell_\infty$ directly, not using lattices, since it's much simpler this way (it would be random rotation followed by rounding and hashing).
review_title: Nice to know result, which solves a particular (one may say pathological) case of an important problem, no groundbreaking techniques

final_score: rating: 7: Good paper, accept
review_content: The paper studies the distributed mean estimation problem where $N$ machines (each holding 1 value $x_u$) wish to compute the mean of all $N$ values.
Along with values $x_u$, each machine receives a common value $y$. This value $y$ upper-bounds $\|x_u - x_v\|$ over all machines $v$. The parameter $y^2$ is called the input variance.
The authors propose a lattice-based algorithm whose quantization parameter allows a trade-off between numbers of bits needed to be communicated and the output variance of the estimated mean. One crucial contribution of the paper is that it provides guarantees with respect to input variance instead of input norm (which can be large if the inputs do not have 0 mean).


The paper is well-written. It has a clear description of the problem and provides a natural motivation. It also gives a great overview of prior work. The main idea of the algorithm is also explained in a clear way.

This work studies a basic and important problem in distributed computation. It combines and proposes several interesting ideas. I especially like the idea of lattice-based quantization and using local information, i.e., $x_v$, together with y to perform decoding.

The paper says:
-- "By choosing the leader randomly we can obtain tight bounds in expectation on the number of communication bits used per machine, and by using a more balanced communication structure such as a binary tree we can extend these bounds in expectation to hold with certainty."
Although not very crucial for this work, one should note here that using a binary tree structure would increase the number of rounds (or the communication time) by a $\log n$ factor until the final result is obtained.

Algorithms 3 and 4 perform communication setup, i.e., electing a leader or making a binary-tree like communication network. What is the communication cost of these? Is it accounted for anywhere?


Page 17, Lemma 20:
Lemma 20 implies that there EXISTS a good coloring. But why is it easy to obtain one for us to use in Algorithm 5?

--- Experiments ---
The fonts in plots are too small.
The experiments are performed only for $n=2$. It seems to be a very limiting setup. It would be nice to show experiments for larger $n$. Given that this is mainly a theoretical work, having such experiments is not a major downside, but they are also not very expressive.
Among Figures 1, 2 and 3, in only one plot the x-axis starts from 10, but in the rest from 0. Would be nice to be consistent.



--- Other comments ---

Page 1, Line 3: Should $\mu = \sum_v x_v$ be $\mu = 1/n \cdot \sum_v x_v$?

Page 2: "thanto the origin" -> "than to the origin"

Page 4, Line 5 of 2nd paragraph of Section 2.1: Is there a typo in "By choosing an appropriate of lattices"?

Page 5, first line: Would be nice to emphasize that this is a probabilistic process as $z$ is actually sampled from the linear representation of $x_u$. 

Page 5, last line of statement of Theorem 1:
Should $\| z - x_u \| = O(\varepsilon)$ be $\| z - x_v \| = O(\varepsilon)$?

Page 12, 3rd line of 2nd paragraph of section A.1: Should $c_i(\lambda) = \alpha_i mod q$ be $(c_q(\lambda))_i = \alpha_i mod q$?

Page 12, 4th and 5th lines of 2nd paragraph of section A.1: $c(\lambda)$ should be $c_q(\lambda)$?

Appendix F:
There is a sentence saying:
-- "In this section we show an extension to the quantization scheme (and thereby also Algorithm 3) allowing us to use a sublinear (in d)"
But in Theorem 27, the bound is O(d log(1+q)). I do not understand why this is sublinear in d. Why does it make sense to make q=o(1)? Shouldn't q be at least a constant?
review_title: A result on the distributed mean estimation problem among N machines parametrized by input variance instead of input norm.

final_score: rating: 7: Good paper, accept
review_content: The paper considers distributed mean estimation in two variations (mean estimation and variance reduction), applicable for instance in distributed learning where several machines needs to figure out the mean of their locally computed gradients.

The paper measures the quality of an estimator in terms of the input variance, where earlier work has implicitly assumed that the input across the machines had mean zero, and instead measured quality in terms of the inputs
In that sense the approach takes in this paper generalizes previous work. 

The authors provide matching upper and lower bounds for the the two problems considered, as well as a practical implementation of the general form of algorithms presented. Finally, experiments back up the quality of the approach considered.

Pros:
- I think the definition of the problems is natural and clean and the right one to consider (instead of assuming zero centered inputs).
- The approach makes application of these algorithms much simpler as the zero mean assumption is removed and does not need to be handled separately
- The general latticed based algorithms are natural and very reasonable.
- The efficient algorithm instantiation of the general approach is nice.
- It is great that the authors provide matching upper and lower bounds and in general the works seems very thorough.
- The experiments show the applicability of the general approach.

Cons:
- The actual algorithm used does not match the optimal bounds given.
- Given the nature of the problem the constants may be relevant instead of using O notation in particular in the actual algorithm presented and used in experiments.

The cons i have listed i think are all small and overall i think this is a good paper as it provides a clean practically applicable version of the problem, the bounds shown are tight and an actual new algorithm is provided and shown to have good practical qualities.

Question.
Definition 9, the packing radius. Maybe i misunderstand. Is it supposed to be the smallest r such that  two balls of radius r centered around any two different lattices points do not intersect? Because that is not what i read from the definition, but that is used in the proofs.

review_title: Clean Distributed Mean Estimation approach

Meta-review: This paper presents a new algorithm for distributed multivariate mean estimation. This method performs significantly better than previous approaches when the input vectors have large norm but are relatively close to each other. The approach relies on lattices and randomized rounding. The approach is evaluated experimentally as well. Overall, there is consensus among the reviewers that this work solves a clean problem using non-trivial ideas. I recommend accepting the paper.
Decision: Accept (Poster)