Sum Estimation under Personalized Local Differential Privacy

Reply to Question #1:

In our protocol, we consider $t= \log \left( \sqrt{\frac{\rho_{\max} }{\rho_{\min}}} B \right)$ thresholds and wants to find the best among them, which requires releasing all the $t$ results and thus we have to divide privacy into $t$ parts.

If we opt not to report each threshold and instead randomly select one, we can save privacy by a factor of $t$. However, the risk of choosing a suboptimal threshold can result in significant overhead, ultimately becoming the dominating factor.

Consider the data in Example 1.1, our radius protocol achieves an error of $O(n^{4\over 3}\log (nB))$ with constant probability. However, if we randomly choose a threshold, the error is likely to exceed $(nB)^{2\over 3}$ with constant probability, which is considerably larger in general.

Reply to Question #2 and Weakness #1:

We agree that the LDP model introduces larger noise compared to other DP models. However, because of its simplicity, both the research community and the industry [B] have invested a lot of effort in studying LDP, and this work is therefore important to NeurIPS to fully understand what can (and what cannot) be achieved under this model. In particular, the sum estimation problem under LDP has been extensively studied as a foundational problem [C,D,references in the paper].

You are right that secure computation can often reduce the noise, by using cryptographic techniques to hide some intermediate results against a computationally bounded adversary, at the expense of higher computation/communication cost and implementation complexity. On the other hand, an LDP protocol reveals all intermediate results to a computationally unbounded adversary. This two approaches are in some sense orthogonal and can be often combined [E], yielding a trade-off between cost and noise. This is a promising direction to combine our LDP protocol with secure computation.

However, our technique cannot be applied to the shuffle model. The key reason is that differing privacy parameters among users negate the`hiding among the crowd' effect, which is essential for the utility amplification of the shuffle model.

[B] Cormode, Graham, et al. "Privacy at scale: Local differential privacy in practice." Proceedings of the 2018 international conference on management of data. 2018.

[C] Liu, Junxu, et al. "Cross-silo federated learning with record-level personalized differential privacy." Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024.

[D] Duchi, John, and Ryan Rogers. "Lower bounds for locally private estimation via communication complexity." Conference on Learning Theory. PMLR, 2019.

[E] Kairouz, Peter, Ziyu Liu, and Thomas Steinke. "The distributed discrete gaussian mechanism for federated learning with secure aggregation." International Conference on Machine Learning. PMLR, 2021.

Reply to Question #3:

The exponential mechanism (EM) requires computing a utility score (which depends on users' private data) for each possible output. In the central model, this score can be directly computed by the central server.

However, in the local DP model, calculating utility scores necessitates interactions between users. Consequently, the computed utility scores must include DP noise. This makes EM meaningless in the LDP model since its utility guarantee is highly sensitive to the accuracy of the utility scores. To the best of our knowledge, no prior work has successfully applied the exponential mechanism in the local DP model.

Reply to Question #1:

We agree that doing a theoretical comparison under some common distributions can complement our experimental observations.

We have done some analyses on 1D data for the following two distributions (please let us know if you are interested in other distributions):

(1) Uniform data in the range $[0,n]$. (2) Gaussian data with mean $n$ and variance $O(n)$.

Under the same privacy specification as in our experiments (say, 5% privacy parameters are uniform in $[\frac{1}{n}, 1]$ while the remaining are uniform in $[1, 100]$). We can show that, for both data distributions, the error of the naive optimal protocol is $O(n^2)$ while our radius-dependent protocol has error $\widetilde{O}(n^{5/3})$. For Gaussian data, our diameter-dependent protocol further reduces the error to $\widetilde{O}(n^{3\over 2})$ because the data is clustered away from the origin.

From these observations, it is evident that for common real-world data distributions, our methods outperform the naive optimal protocol. Furthermore, the performance gap becomes even more pronounced as the data becomes more concentrated.

Finally, we would like to emphasize that the naive optimal protocol assumes that the optimal truncation threshold is given, which is not easy to obtain under privacy constraints.

Reply to Question #2:

Please see our response to Reviewer #1 Q1.

Reply to Question #3:

We agree. We'll rewrite our diameter-dependent protocol using the algorithm environment to improve clarity.

Reply to Weakness #1:

The shift-and-truncate framework in [18] is a standard approach for addressing the sum estimation problem, which is not the focus or contribution of our work.

In this paper, we consider the personalized local DP setting, where the error depends on both users' data and users' privacy. The main challenge lies in determining how to perform truncation in a way that balances the effects of these two factors.

To address this, we propose a novel searching strategy that optimizes over both dimensions simultaneously by considering the noise scale $s$. In contrast, [18] relies on a pre-computed quantile for truncation and does not involve any optimization procedures.

Furthermore, the method in [18] cannot be extended to our setting because the target quantile (and thus the truncation threshold) cannot be computed while adhering to the personalized DP requirements. A comparable baseline is the naive optimal protocol used in our experiments, which assumes we already know (in a non-private manner) the optimal truncation threshold. Even with this unrealistic advantage, the naive optimal protocol is outperformed by our approach, highlighting the effectiveness and significance of our new strategy.

Reply to Weakness #3:

We sincerely apologize for our oversight. A minor change was made to the paper shortly before the submission deadline, and we did not realize it caused the paper to exceed the 9-page limit. We'll definitely fix this problem and hope this will not be the reason for rejection. Thanks!

Reply to Question #1:

Thanks for the comment. As we have explained in our response to Weakness #1, the main idea and contribution of this paper lie in the proposed searching strategy that considers $\mathbf{I}(u)$ and $\Phi(u)$ simultaneously. That's why the truncation threshold is of the form $\tau_i(u) =s_i \sqrt{2\Phi(u)} = 2^{i}\sqrt{\frac{ \Phi(u) }{\rho_{\max}}}$. We will emphasize the core contributions of our work and provide additional explanations to clarify the insights behind them.

Reply to Question #1:

We agree that optimality is an important theoretical question to consider. However, the answer is quite nuanced, depending on the precise notion of optimality.

Worst-case optimality: Consider a particular user $u$, and the following instances the user may have: $(B,0,...,0), (0,B,...,0),..., (0,0,...,B)$. Since LDP requires all of them to be $\Phi(u)$-indistinguishable, the user must injects a noise of scale $\Omega(\frac{B}{\sqrt{\Phi(u)}})$ on each coordinate (this can be formalized by standard lower bound arguments). Thus the worst-case error for the sum of all users' data is $\Omega(B\sqrt{d\cdot\sum_{i=1}^n \frac{1}{\Phi(u_i)} })$. Our algorithms incur an error no more than this on any instance, so it is worst-case optimal. However, this bound can also be achieved by a trivial mechanism that simply adds an $O(\frac{B}{\sqrt{\Phi(u)}})$ Gaussian noise on each coordinate, which is very large on typical instances. So worst-case optimality is not very meaningful, either theoretically or practically.

A much stronger notion of optimality is instance optimality. However, for any instance $\mathbf{I}$, there always exists a trivial mechanism $M(\cdot) \equiv \mathrm{Sum}(\mathbf{I})$ that achieves 0 error on this instance (while incurs large errors on other instances). This means that instance optimality is unattainable.

Several prior works [13,18,A] has then introduced various relaxed notions of instance optimality, but they have not considered the personalized LDP model. It would be an interesting direction to first extend these optimality notions to this model, and then see if our protocols are optimal with respect to any of them.

[A] Dick, Travis, et al. "Subset-based instance optimality in private estimation." International Conference on Machine Learning. PMLR, 2023.