Fast Optimal Locally Private Mean Estimation via Random Projections

Summary

This paper presents an efficient distributed mean estimation framework, which first reduces local data dimension using (different) random projections and then applies an existing private processor (Asi et al [7]) on the projected data before sending them to the server. Further speedups of the framework are also presented, using a more efficient projection matrix and correlated sampling. Utility bounds of the framework and its speedups are derived, and experimental results on both synthesis and real-world data sets are presented.

Strengths

[1] Accelerating private distributed mean estimation is a useful topic. [2] The paper (especially, narrative) is beautifully written. [3] Utility bounds are derived.

Weaknesses

[1] Novelty of the proposed framework is a bit limited, as it basically applies random projection (in a non-traditional but still considerably straightforward way) on PrivUnitG (Asi et al [7]) to speed up the latter. [2] Comparison of efficiency to the naive PrivUnitG in Table 2 is missing and should be added. Importantly, I suspect the proposed framework does not significantly improve over PrivUnitG, because it simply applies PrivUniteG on fewer features -- this is partly evidenced in the experimental results (Figure 3), where PrivUnitG appears more efficient. [3] There is a potential error in the proof of Theorem 1 that may make the result invalid. In line 486 (supplementary), equation (i) is argued to follow because $E[\hat{u}] = u$, but such argument does not make sense to me. Consider a simple case when n = 1, then the equation basically argues $E[||A + B||_2^2] = E[||A||_2^2] + E[||B||_2^2]$. I don't see how this can fly... Can authors elaborate? ---------- Update ---------- I've read the author responses and my concerns [2][3] are well-addressed. I have raised my score accordingly.

Questions

Could authors respond to my comments [3] and [2] in the Weakness section?

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

NA

Summary

The paper introduces a fast algorithm for private mean estimation under communication constraints. The proposed scheme primarily relies on random projection, and the algorithm enhances speed through the utilization of Hadamard matrix and sampling techniques.

Strengths

- Theorem 1 offers a theoretical analysis of the utility achieved when random projection is employed. - It is intriguing to observe that the combination of SRHT (Hadamard matrix + Rademacher diagonal matrix) achieves results close to the optimal. - The idea of enhancing performance through correlated sampling appears to be a compelling approach.

Weaknesses

1. I believe the current work primarily focuses on the tradeoff between utility and complexity, where the communication budget is relatively higher compared to other algorithms like SQKR. For instance, SQKR has a communication budget of epsilon (~10), while the proposed scheme has k on the order of 10^2 to 10^3 (the communication budget k\log^2 d is even larger). 2. In Figure 1, comparing the proposed scheme with a communication budget of k\log^2 d to SQKR with a communication budget of epsilon may appear unfair (despite being the optimal choices for their respective algorithms). To properly compare with SQKR, I suggest the authors provide two separate figures: one with a communication budget of k and another with a communication budget of k\log^2 d.

Questions

- Could you please specify the exact value of k used in Figure 1? - As both SQKR and the current work utilize Kashin's representation, which can be approximated using an orthogonal matrix, it might be worth exploring the possibility of a unified framework that encompasses both algorithms. - Does the LDP constraint automatically hold due to the inclusion of PrivUnit in the projected space? Even in correlated sampling?

Rating

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

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Although the proposed work is impressive in terms of complexity, the communication budget is order-wise suboptimal compared to previous work (e.g., SQKR).

Summary

The paper studies the problem of locally private mean estimation, and design algorithms with optimal (upto $1+o(1)$ factor) error with better communication complexity and runtime. The key idea behind improved communication complexity and runtime is (a certain) random projection based pre-processing step.

Strengths

1. The problem of private mean estimation is an important problem in itself and moreover, a lot of interest is also derived from its application to federated learning. Hence, there has been a lot of work recently on devising "better" algorithms for it in various settings. The paper identifies gaps in our understanding of the problem, mainly on obtaining optimal error with better communication complexity and runtime, and make solid contributions towards them. 2. The paper is written well. Instead of presenting the final result first, it gradually builds towards conveying the challenges and key ideas. 3. The experiments are encouraging, testing various aspects and comparison with many known methods. Further, the experiments section is well-organized and outlined.

Weaknesses

1. The underlying key technique -- random-projection to smaller dimensions -- is simple and has been used in the prior works for this problem (albeit without the privUnit). Further, even improvements gained via Subsampled Randomized Hadamard Transform follow standard ideas used in prior works. I encourage the authors to highlight if there are significant differences between this paper and the prior works. 2. While I enjoyed reading Section 2 where the authors gradually build towards the main results and various instantiations, I found Section 3 to be short. It does not provide intuition on how correlated sample is beneficial. Similarly, Remark 2 references unbiased versions of the proposed procedures, deferred to Appendix A. I encourage the authors to expand on these, if possible. Minor: Table 2 referenced is missing in the main text.

Questions

Please respond to the weaknesses. Another simple questions is: why not use same $W$ in every client? Then the server won't have apply the inverse transformation (matrix multiplication) for each client. Is there some fundamental reason this isn't done?

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

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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The paper focuses on obtaining optimal (upto upto $1+o(1)$ factor) error for worst-case instances (minimax risk). Consequently, methods which achieve optimal error but with (large) constant factor are deemed inferior. However, in practice, the instances are usually not worst-case but are rather structured (eg: sparse) and therein non-optimal methods may fare better (unlesss there is something fundamental about the achieving worse error regardless of the instance). Therefore, more instance-specific guarantees may be needed to reflect improvement in practice. This is not to say that worst-case error (which is studied in this paper) isn't interesting and important.

Summary

The paper considers the problem of performing mean estimation for worst-case data under local differential privacy. The precise setting considered involves $n$ users, each of whom has one data vector $v_i$ (which, without loss of generality, can be assumed to exist within the unit ball). The users must privatize their data and send them to a central server which tries to estimate $\frac{1}{n} \sum_i v_i$ as accurately as possible using the privatized data. The older work of Asi et. al. showed that the PrivUnit algorithm of Bhowmick et. al. attains the optimal error rate among all unbiased estimators. However, implementing that approach leads to concerns regarding the number of bits that need to be exchanged, as well as the runtime, both from the perspective of the clients and the server. The present work tries to address these concerns by using an approach relying on random projections. In particular, the users embed their data into a low-dimensional sub-space of the original space and privatize the resulting vectors. This results in a significantly smaller number of bits being exchanged, thus addressing the issue of potential constraints in communication. In greater detail, the authors give two different algorithms, both of which fit into the above framework. The first algorithm involves each user randomly sampling their own projection matrix, which they must communicate to the server. On the other hand, the second algorithm involves the server choosing a matrix which they communicate to the clients, and then each client has to transform the matrix using their own sampling matrix. For both approaches, the overhead in the error is small ($1 + o(1)$ specifically), while the latter approach manages to significantly reduce not just the communication between servers, but also the runtime for both the clients and the server. The theoretical results are complemented by experiments which support them.

Strengths

The paper is very well written and gives a complete picture, covering both theoretical aspects and empirical evaluation. Additionally, the coverage of the prior work in the introduction is quite thorough, so the results are clearly positioned within the overall literature. Considering the computational aspects (in addition to the statistical ones) of performing mean estimation under local differential privacy is a very well motivated question, which the paper does a good job of addressing by giving algorithms that have significant improvements compared to prior work. For that reason, I believe that it is of interest to the NeurIPS community.

Weaknesses

No obvious weaknesses.

Questions

No questions.

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

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

No obvious negative societal impact.

Response by Reviewer

Dear authors, Thank you for clarifying the proof of Theorem 1 and efficiency comparison with PrivUnitG. My concerns on these two issues are well addressed. In line 486, it might be helpful to indicate what the expectation is with respect to, e.g., $W_i$'s and $\hat{u}_i$'s. Regarding novelty, I agree the theorectical analysis has challenges, but still think the proposed technique resembles its non-private counterpart to a great extent -- but perhaps it is common in DP-related research. Anyway, I've raised my score.

Thanks!

I thank the authors for their detailed response and clarifications. I am still positive about the paper, and will keep my score.