Summary and Contributions: This paper studies fundamental problems of frequency estimation, distribution estimation, and mean estimation under local differential privacy. While these problems have been studied extensively, the prior work rarely ponders on the amount of communication (both from server in terms of common randomness and from the users). Bassily and Smith showed that using common randomness from the server, any LDP scheme can be converted into a one-bit communication scheme from each user. However, the necessity of common randomness was unclear, and so was the question of how much of it is needed? Acharya and Sun ([1] of the paper) showed that without common randomness for epsilon<1, one bit communication is enough to achieve optimal distribution estimation under L1 distance, and that it is impossible to do so for frequency estimation. However, for epsilon>1, the problem was not considered. This paper shows that as the value of epsilon changes, there are some interesting trade-offs that happen between sample complexity and the number of bits of communication per player. For example, for distribution estimation, they show that one bit protocols are not optimal for large epsilon, and one can actually use the additional communication in order to reduce the sample complexity of estimation. For the problem of frequency estimation, they show that as epsilon increases, the error can be reduced for larger epsilon. They also show a similar result for the problem of mean estimation, where the goal is to estimate the mean of vectors that are held at the users. This shows the wide range of the problems to which their arguments can generalize. In a nutshell, this paper shows that there is a trade-off between epsilon and communication for a given number of samples and error requirement. This result however is to be expected since with eps=log k communication is the only bottleneck that remains. The algorithms are simple, and are modifications to the previous approaches using Hadamard matrices. The approach has a potential of generalizing to other problems under LDP, a question that could be interesting to explore. The writing of the paper is clear in general, but perhaps the authors can provide some intuition as to why such a trade-off exists between epsilon and communication. ———————- Post rebuttal: I have read the author response and am updating my score accordingly.
Strengths: See above.
Weaknesses: See above.
Correctness: They look correct.
Clarity: Well written
Relation to Prior Work: Reasonably well discussed.
Reproducibility: Yes
Additional Feedback:
Summary and Contributions: This paper studies several of the most basic problems in distributed statistical estimation: 1) frequency estimation, where the goal is to approximate the histogram of users' categorical data, 2) distribution estimation, which is similar to the above, but where users have i.i.d. samples from an unknown distribution and the goal is to approximate that distribution, and 3) mean estimation, where user data comes from a unit ball and the goal is to estimate the mean. These problems have been studied under various constraints on how data is communicated from individuals to an aggregator, including local privacy and limited communication, with tight upper and lower bounds known for each of those restrictions separately. This paper studies these problems under simultaneous privacy and communication constraints. That is, it aims to understand the optimal estimation error for communication-constrained locally private protocols. It gives asymptotically optimal protocols for each of these settings (under l_1, l_2, and l_infinity error for 1), l_2 and l_infinity error for 2), and l_2 error for 3)), and hold for the full range of privacy and communication parameters. Moreover, these protocols show that the less stringent of the privacy or communication requirement can be achieved for free, with no asymptotic increase in error. The new protocols for frequency and distribution estimation refine the "Hadamard response" algorithm from prior work. Hadamard response enables accurate frequency estimation for small epsilon with one bit of communication. The new protocol uses the recursive structure of Hadamard matrices to simultaneously increase communication and privacy loss, getting an optimal tradeoff for large epsilon. The new protocol for mean estimation uses a randomized response based on Kashin's encoding, which to my knowledge is novel in this line of work.
Strengths: This work considers some of the most basic problems in a very active area of research. It unifies a number of prior results and shows how to make them work for a full range of parameters, using clean new ideas. The results present a clear conceptual message, that at least in the settings considered, the less restrictive of privacy or low-communication can be had for free.
Weaknesses: The concrete new results concern the large epsilon (low privacy) regime where eps > 1. This is not such a desirable setting (which, in part, explains why it's been less explored in prior theoretical work); nevertheless, it is frequently used in applications.
Correctness: I did not review the proofs in detail, but the exposition of the techniques make the results appear to be correct.
Clarity: The paper is generally well-written. The tables do not do a great job of communicating which results are new and which ones follow from prior work, e.g., the Table 1 entry on Theorem 2.1. for heavy hitters. What do the blue and red backgrounds mean in Table 2?
Relation to Prior Work: There is an extensive literature on these problems from a number of different communities, and the discussion of related work seems to hit most of it. Something that is not clear is what results on mean estimations follow from (some version of) Duchi-Jordan-Wainwright. They consider mean estimation in the unit ball under minimax l_2 error, which should already have some implication for this problem.
Reproducibility: Yes
Additional Feedback: Is there an obstacle to getting a tight upper bound for distribution estimation under l_infinity error as well? EDIT: Thanks to the authors for their feedback. It confirms my thoughts about the paper and I'd be happy to see it accepted.
Summary and Contributions: This paper studies the problems of frequency estimation and mean estimation under both privacy constraint and communication constraint, and proposes mechanisms that simultaneously achieve optimal privacy and communication efficiency using public randomness.
Strengths: For frequency estimation and mean estimation under LDP, the authors design optimal schemes using public randomness in terms of the trade-off between the communication cost and the accuracy. For distribution estimation under LDP, the authors show that private randomness suffices.
Weaknesses: I have doubts about the theoretical claims in this paper, especially on the lower bound, since [8] has shown that in the public coin model, every LDP protocol can be transformed so that each user sends only one bit to the central server with almost no loss in performance. Thus when using public randomness, the communication budget will not incur an accuracy loss for any LDP protocol by using the transformation in [8]. This is also discussed in [1], and therefore the authors of [1] study the converse question: Is public randomness necessary to reduce communication from users under LDP. ======== after reading the authors' response I upgrade the score to 6, as the result in [8] only applies to O(1) epsilon and this paper can complement it.
Correctness: See comments in the section of Weaknesses.
Clarity: This paper is well written and structurally clear.
Relation to Prior Work: This paper improves the error for the problem of mean estimation compared with the existing works under the same privacy budget and communication budget, and generalizes the achievability to arbitrary privacy budget and communication budget for the problem of frequency estimation.
Reproducibility: Yes
Additional Feedback:
Summary and Contributions: This paper studies the limits on accuracy for a given privacy and communication budgets. The recursive Hadamard response (RHR) is presented for frequency estimation, where the estimation error decays while the privacy and communication budgets increase. In turn, from the RHR, a scheme for distribution estimation is proposed which requires less communication for the same accuracy and privacy levels in literature. Moreover, this paper also presents a scheme for mean estimation, which is based on the Kashin's sampling. ------------ Post rebuttal: I have read the author response, the authors have addressed my comments, and I stick to my score.
Strengths: The paper presents a novel idea which bridges the gap between the privacy constraints and the communication budget and achieves the same levels of privacy for lower communication cost. The given claims are supported and proven. The work is very significant to the NeurIPS audience.
Weaknesses: I think it would benefit the paper and the readers to discuss the shared randomness in more detail, since it is public. It would be good to discuss how and why this is added and how it affects privacy.
Correctness: The claims in this paper are correct. The paper satisfies its claims and gives sufficient proofs, explanations, and experimental results.
Clarity: The paper is in general well written, with some minor typos, like for example: - On page 2, section 1.1, "as follows" not "as follow" - On page 5, second paragraph, "optimality" not "optimility" It would be good to proofread the paper for similar typos. Moreover, the way tables 2 and 3 are places, it is hard to read the captions, maybe separate the two tables, or make them as subtables with more distance between them.
Relation to Prior Work: The relation of this work to the literature is discussed clearly and well.
Reproducibility: Yes
Additional Feedback: