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

Summary

The authors consider the problem of high dimensional mean estimation with communication and privacy constraints. For federated learning or distributed SGD, model updates must be communicated to central server, but as models become much larger this can be a bottleneck within the computation. As a result, previous works has considered the setting in which there is a restriction on the number of bits that can be communicated, which the authors also follow. Furthermore, the authors consider the differentially private setting adding another constraint. This setting was also considered in previous work, some of which achieved optimality up to constant factors. The authors improve upon that work and achieve exact optimality and this theoretical improvement is backed by their empirical experiments.

Strengths

Improves upon previous work for a reasonably well-studied problem and achieve optimal tradeoff between communication-privacy-utility and further show how the previous work are special cases in their method.

Weaknesses

Minor gripe that some of the notation could have been expanded upon more clearly (for example: P_U-almost) but can understand that page limits can add difficulty.

Questions

None

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors adequately addressed the limitations

Summary

The paper studies the distributed mean estimation (DME) problem with communication & privacy constraints. The goal is to construct an unbiased estimate of a unit vector $v$ using $b$-bits that minimizes the mean squared error and provides $\epsilon$-LDP. It is well known that any scheme achieving the above communication will have to quantize the unit sphere using $M=2^b$ points. Further, to achieve $\epsilon$-LDP, a particular quantization point is chosen and returned according to an appropriate distribution. The main contribution of this work is characterizing DME schemes that achieve optimal error in the presence of a communication budget and privacy constraints. The authors show that a random set of points generated using a rotationally symmetric distribution will achieve the optimal error. The intuition is that such a point set will be maximally separated and will most efficiently cover the sphere. $\epsilon$-LDP is achieved using a randomized response mechanism.

Strengths

- Presents a DME scheme under exact communication constraints instead of asymptotic error bounds that are optimal. - The idea of treating the k-nearest codewords equally instead of just the closest seems to provide improvements over the prior works. This clean trick can be of independent interest.

Weaknesses

- The work provides sufficient conditions for a DME scheme to be optimal, i.e., an optimal scheme has a particular canonical setup. These conditions are not necessary, and not all schemes satisfying the canonical setup achieve optimal error. - Either some proofs have (probably fixable) errors, or I have misunderstood. So at least rephrasing or an elaborate explanation is required. Details are provided in the next section (Questions)

Questions

1) As mentioned in the paper, the prior works of SQKR, MMRC, and FT21 can be seen as specific instantiations of random codebooks. Could it be possible that their schemes are exact-optimal as well and satisfy the conditions mentioned in this work? While a discussion is provided, can you comment on what condition is not met by each of these that confirms that they are not exact-optimal? 2) Line 217-220 leading to Eq 29 needs further justification. Intuitively, this holds if the k points are equidistant, but I am not sure why the k-nearest neighbors will give an unbiased estimate. In the current manuscript, this is just a statement and not a formal proof of the fact that "k-closest encoding consistently yields an unbiased scheme for any rotationally symmetric codebook." Further, it would be good to mention that for a rotationally symmetric codebook, the $\sum_m U_m = 0$. 3) Proof of Lemma 3.7 - What is top-k set? I am assuming it is the set of k-nearest neighbors to random a in s^M Should the summation have only $s_m$ and not $a^Ts_m $? Typo in eq 94 - the second summation should be over s_i. Eq 96 shows that you get an unbiased estimate of $e_1$ and not $a$. Also, other coordinates cannot be ignored. $r_k$ value is roughly $M$, so the error of the RRSC scheme will be $\sim M^2$. So for $M = d$, there is an error of $d^2$ which is higher than the order optimal ones $(O(d/\log d))$ for the same amount of allowed communication. A brief clarification on this would be great. 4) For the shared randomness setup, will the server/nodes have to regenerate the codebook for each invocation of the algorithm? 5) Some suggestions to improve the readability in my opinion would be: - Fix errors in proofs or provide better justifications - In Equation 26 the probability of choosing the k+1-th closest codeword is zero if k is an integer. This seems to be inconsistent with Algorithm 1, and the analysis that follows in Section 3.4 - Clarify what the `=' in Def 3.3 means. It can be confusing to think that the two codebooks are equal (permutations of each other) rather than their distributions being identical.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This paper studies the mean estimation problem under communication and local differential privacy constraints in the non-asymptotic (exact optimal) setting, and proposed a randomization mechanism that satisfies the identified necessary property of the exact optimality.

Strengths

1. The authors proved a necessary condition that the codebook-generating distribution needs to be rotationally symmetric. 2. The authors further proposed the first exact optimality algorithm Random Rotating Simplex Coding (RRSC) that matches the necessary condition. 3. Empirical results in the paper showed that the proposed RRSC outperforms the state-of-art benchmarks (order-optimal) for the task. 4. The authors proposed interesting conjectures and clear future directions based on the design and properties of the algorithm.

Weaknesses

1. line 177, "an random" to "a random" 2. The design of k-closest encoding and Theorem 3.6 (along with its proof in the Appendix) lacks the intuition on k, which seems to be valuable to explore both theoretically and empirically (as stated in the conjecture).

Questions

For the choice of $k$, in the experiments are to minimize $C_k$ based on different $k$'s. How can such choice of $k$ guarantees the requirement in Theorem 3.6 (and its proof)?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Lack of intuition on k as described in weakness.

Summary

This paper focuses on the problem of distributed mean estimation under local differential privacy (DP) and communication constraints, with shared randomness between users and the server. Previous works either achieve exact optimal mean squared error (MSE) using $O(d)$ bits or achieve order-optimal MSE with a large constant using $O(\varepsilon)$ bits. In this paper, the authors aim to tackle the same problem under shared randomness, aiming for both exact optimal MSE and communication efficiency. The proposed solution approaches the problem as a lossy compression problem. The authors demonstrate that the optimal scheme can be represented by a codebook through random coding. Additionally, they establish that the exact-optimal codebook-generating distribution must be rotationally symmetric. Empirically, the authors demonstrate that the proposed methods outperform existing approaches.

Strengths

1. This paper is very technical. The paper is clearly written and lays out its contributions succinctly. 2. The proposed framework achieves exact optimality in terms of both MSE and communication efficiency.

Weaknesses

It would be better if the authors could discuss why shared randomness is necessary to achieve exact optimality.

Questions

See weaknesses

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The limitations are discussed. This paper does not have a negative societal impact

Summary

This work considers the problem of distributed mean estimation and aims to obtain "exact optimal" estimators under communication, (local) differential privacy and utility constraints. Exact optimality here means that instead of focusing on the order of complexity, the focus is also on the constants as well. Prior work either focused on "order optimality" or were exactly optimal for privacy and utility but only order optimal [Feldman-Talwar'11], [Shah-Chen-Balle-Kairouz-Theis'22]. This work achieves exact optimality through a k-closest encoding and a randomly generated codebook shared between the server and users.

Strengths

They obtain exact optimality for privacy-utility-communication tradeoffs of mean estimation under l_2 norm error. This improves upon prior work that could only obtain order optimality or exact optimality but only for some parameters. Their work unifies the framework that existed in prior work [Feldman-Talwar'11], [Shah-Chen-Balle-Kairouz-Theis'22]. Their experiments show significant improvement in communication budget required compared to the previous work, especially in the setting where the number of bits is small. The theorem regarding optimality of rotationally symmetric shared random codebooks could be of independent interest.

Weaknesses

There is no "main theorem" that sums up the results in the main results section for mean estimation, and I think it's necessary to include such a theorem. I think exact optimality compared to order optimality is a more niche setting. That being said, that's not necessarily a weakness, and it could be impactful in practice.

Questions

I think part of the paragraph **unified framework** in the discussion section could be mentioned in the related work section as well. As mentioned in the previous section a main theorem that clearly states the trade offs this work obtain for mean estimation should be included. The score currently given is assuming that such a theorem will be included.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors have adequately addressed the limitations of their work.

Thank you for your response to our rebuttal.

We thank the reviewer for their time reading our rebuttal.

Thank you for your response to our rebuttal.

We thank the reviewer for their time evaluating our manuscript and reading our rebuttal.