Learning from End User Data with Shuffled Differential Privacy over Kernel Densities

We thank you for the review.

How is the proposed method compared with central DP in terms of theoretical guarantees? Would this be aligned with the empirical comparison as shown in the experiment section?

Under $(\varepsilon,\delta)$-DP, the central DP KDE error is $O(\sqrt{\log(1/\delta)}/(\varepsilon n))$. In our shuffled DP KDE results, 3NB has the same error asymptotically (this is the statement of Theorem 3.3), while RR has error larger by another factor of $\sqrt{\log(1/\delta)}$ (with the gain of smaller communication cost than 3NB). Under pure $\varepsilon$-DP, the central DP KDE error is $O(1/\sqrt{\varepsilon n})$, and our shuffled DP result with Pure has the same error asymptotically. These results align with the experimental section, where all the tested DP methods (central and shuffled) converge to the accuracy of exact DP once $\varepsilon$ and $n$ are large enough.

Another popular framework is to leverage secure multiparty computation (MPC)

DP and MPC handle different goals in data protection, and are often used together, especially in shuffled DP – where the shuffler, which is considered “trusted” in the shuffled DP model, is implemented by MPC to achieve this trustworthiness. For example, the paper [1] you mention is referenced in Kairouz et al., 2021a;b as a possible implementation of the shuffler.

In general, MPC protects the computation process, while DP protects the computation’s output. Take bitsum as an example: each of $n$ users in a communication network holds a private bit, and they want to compute and release the sum, without leaking information about their individual bits.

• They could send their bits to the analyzer, who would compute the sum and add Laplace noise to ensure DP. The output is DP, but an adversary who eavesdropped on the communication has learned all the individual bits anyway. This is DP without MPC.
• They could use MPC to compute and release the exact sum. MPC ensures that the eavesdropping adversary has learned nothing from the communication except for the intended output, i.e., the sum. But the sum itself is not private, since as a deterministic function of the inputs, it may leak information about individual bits (for example, the adversary now knows whether all users had zero bits or not, which violates DP). This is MPC without DP.
• They could first locally add noise to their bits (say, flip them with some probability, as in RR), then use MPC to compute and release the sum of the noisy bits. This is essentially the shuffled DP model. If the local noise is chosen such that the sum of noisy bits is DP — which is what shuffled DP bitsum protocols are formally designed to achieve — then the adversary has learned nothing (up to the $\varepsilon$ privacy budget of DP) from neither the communication nor the output. This is the combination of DP and MPC.

Thus, the shuffled DP model can be understood as an abstraction of the MPC portion of the protocol into a “trusted shuffler”, or alternatively, as an abstraction of an MPC protocol with a DP guarantee on its output. MPC in this discussion can be replaced with other notions of secure computation (which protect the “process”).

Bit-width is introduced in line 239-240. What is the exact definition of it?

For a shuffled DP protocol $\Pi$, the bitwidth $\ell=\ell(\Pi)$ is defined as the number of bits in the binary representation of each of its numerical values. We distinguish here between numerical values, which are ones used for arithmetic computations, and non-numerical values (like user IDs or enumerative indices, which are often written as integers for convenience, but need not be involved in arithmetics). It is possible that $\ell=\infty$ (say, if $\Pi$ uses real numbers in messages).

The reason this parameter was introduced and bounded in prior work on shuffled DP is that in practice, the shuffler is often implemented with MPC using modular arithmetics (the paper [1] you cited is an example). To enable this, $\ell$ must be finite. Furthermore, since the arithmetics in MPC is modulo $2^\ell$, the practical running time scales exponentially with the bit-width, and therefore it is important to control. Our DP KDE protocols have bit-width 1, as all the numerical values they communicate in messages are integers of magnitude 1.

We thank you for the review.

On the distinction between classification and class decoding

Perhaps the clearest way to see the distinction, is to consider class decoding without classification at all. Suppose the users have unlabeled private texts, with some prevalent topical theme unknown to the learner, say, films. Not all texts need to be about films, but suppose most are. The analyzer learns a DP KDE representation $\widetilde K$ of the embedded texts. Note that there is no classification component, since there is only “one class”. The analyzer never sees labeled negative examples, and is never told about any text whether it belongs to the topical theme or not. The setting is completely unsupervised.

Still, by class decoding, the analyzer will give the highest scores to dictionary terms like “biopic, movie, screenplay”, and can discern the topical theme of the user texts from the private representation $\tilde K$.

This is generally expected if $\tilde K$ was a non-private KDE estimate, and also if $\tilde K$ was learned under central DP, since in both those cases the learner constructs $\tilde K$ from plain unprotected texts (or their embeddings), and she would naturally incorporate their prevalent themes into the $\widetilde K$. Simply put, she learns their content by just reading them. The difference we wish to highlight is that in the shuffled DP setting, the learner achieves this without seeing any unprotected text, in the strong sense that she provably (by DP) cannot glean substantial information about any of the texts. In a sense, she can tell what the texts are generally about without reading any of them. This is, of course, made possible because each privatized text does leak “a little bit” of its content (within the privacy budget), and if sufficiently many of them are topically consistent, the shuffled DP KDE mechanism detects and expresses the accumulated topical signal.

Experimental details: please specify how all hyperparameters have been set, how many seeds you used etc. Also, please add some error metrics (sem, std or similar) to the results.

The only hyperparameter is the number of repetitions/features $I$ in the protocol (line 221), which we set to $d$ (the embedding dimensions) for the most direct comparison with the non-private KDE baseline (which just uses the $d$ original embedding features). The shaded regions around the curves in the plots show the std over 5 random seeds.

How much utility do the noisy counts via LDP cost? Please add an ablation study (at least for some experimental setting)

We have added this to the uploaded version, please see Tables 2-5 on pages 25-26.

in what sense the bit-width 1 is optimal (e.g. communication, utility, both)?

We give the definition of bitwidth in an answer to Nw6K, who raised a similar question. The role of bit-width is to ensure that the secure aggregation part of the protocol (which is abstracted as the shuffler) can be made practically efficient. It may generally degrade communication and utility as follows: The communication clearly grows with the bit-width (though it is not governed by it, as it also grows with the non-numerical values in protocol). As for utility, since large or infinite bit-width may make the protocol infeasible or impossible, it is common to cap the bit-width by truncating the numerical values in the protocol to a lower bit precision. This creates another source of error (rounding errors), degrading utility. The best possible bit-width 1, which our protocol attains, has no degrading impact on neither the communication nor the utility.

Please add an additional step after line 913 to be clearer on the proof.

We have expanded this in the uploaded version (it is now line 918).

there are some proposed DP-kNN methods

We suppose you mean the line of work [A,B,C]. While they use the kNN terminology as motivation, the problem they actually solve is not nearest neighbor search (NNS), but near neighbor counting (which they use as a DP stand-in of NNS, not unlike how we use KDE). The near neighbor counting problem (NNC) is the following: given a dataset $X\subset\mathbb R^d$ and a scale parameter $r>0$, build a data structure that given a query $y\in\mathbb R^d$, reports the number of points in $X$ at distance at most $r$ from $y$. We will denote this number by $|B_X(y;r)|$. In DP NNC, which these papers solve, the goal is for the data structure to report private estimates of $|B_X(y;r)|$.

NNC is very close to KDE, in fact (if we normalize the counts by $|X|$) it is a special case of KDE, with the “step kernel” $\mathrm{\mathbf{k}}_r(x,y)=1$ if $\lVert x-y\rVert_2\leq r$ and $\mathrm{\mathbf{k_r}}(x,y)=0$ otherwise. $r$ plays the same role bandwidth plays in kernels.

Let us explain why this line of work is not suitable for our goals. We focus on [C], which is the SOTA for high dimensions. First, in terms of accuracy, they are unable to estimate $|B_X(y;r)|$ privately with additive error. Instead, they introduce another approximation parameter $c>0$, and their central DP mechanism reports a count between $|B_X(y;r)|$ and $|B_X(y;cr)|$, with additive error that grows like $n^{O(1/c^2)}/\varepsilon$. Formally, the normalized count is guaranteed to be between $\tfrac1n|B_X(y;r)| - 1/\varepsilon n^{1-O(1/c^2)}$ and $\tfrac1n|B_X(y;cr)| + 1/\varepsilon n^{1-O(1/c^2)}$ (suppressing some low order terms). Note that the decay rate of the additive errors is worse than linear in $n$. In comparison, for Gaussian KDE (even with shuffled DP) we get a true additive approximation, and with linear error decay rate $1/\varepsilon n$.

Second, in terms of efficiency, their mechanism seems infeasible for shuffled DP. It maintains $n^{\ln\ln n}$ counters (corresponding to nodes of a $T$-ary tree of depth $K$, where $K,T\sim\ln n$). In their central DP setting, to achieve efficiency, they round all small counters to zero, and realize only the non-zero counters, of which there are at most $\widetilde O(n)$. But with shuffled DP, each user would have to participate in a summation protocol for each of the $n^{\ln\ln n}$ counters (the users cannot know ahead of time which counters would end up small), leading to infeasible (worse than any polynomial) running time and communication per user.

[A] Gursoy, M.E., Inan, A., Nergiz, M.E. and Saygin, Y., Differentially private nearest neighbor classification. Data Mining and Knowledge Discovery, 2017.

[B] Zhu, Y., Yu, X., Chandraker, M. and Wang, Y.X., Private-knn: Practical differential privacy for computer vision. CVPR 2020.

[C] Andoni, A., Indyk, P., Mahabadi, S. and Narayanan, S., Differentially private approximate near neighbor counting in high dimensions. NeurIPS 2023

We thank you for the review.

I would imagine that the theoretical bounds on the supRMSE in Theorem 3.2 are quite loose. Would it be possible to add a comparison of the theoretical bounds alongside the empirically realized errors in KDE ?

We have added a comparison in the uploaded version (Figure 5, page 24). The looseness of the theoretical error bound depends on the data: for some datasets it is quite tight, while for others it is rather pessimistic.

I don't see the bounds in Theorem 3.2 accounting for the variance in the LSQ?

The variance comes into play in the dependence of the supRMSE on $R,S$ in Theorem 3.2, which is $SR^2/\sqrt{I}$ over $I$ repetitions. The reason is largely that this is the standard deviation of averaging $I$ i.i.d repetitions of a random variable bounded in an interval of length $SR^2$. The random variable here is $\tfrac1n\sum_{i=1}^nf(x))^Tg(y)$ for a sample $(f,g)\sim\mathcal Q$, and it is bounded in $[-SR^2,SR^2]$ because the inner product has $S$ non-zero summands due to sparsity, each a product of two numbers in $[-R,R]$ (the corresponding entries of $f$ and of $g$). In the proof, this is happening in Section A.1.4, particularly Claim A.4 and the bound after it.

I am surprised that for the IP kernel, it is better to go with the $(1,\sqrt d,1)$-LSQ instead of the naive $(d,1,d)$-LSQ. While the latter has additional dimension, it is no variance

In the shuffled DP KDE protocol, apart from the randomness of sampling from the LSQ family, there is another source of randomness, due to discretization (which is necessary for bounding the bit-width). Since the random discretization error also yields the same $SR^2/\sqrt{I}$ dependence on $R,S$, the mechanism incurs this error even if the LSQ family is random-free. Technically, in the proof, this would make the expectations in Claim A.2 and in Section A.1.4 be over only $\{b_{ij}^{(u)}\}$ (the randomness of discretization), and not also over $(f_i,g_i)$ (the randomness of LSQ) as they are currently, but otherwise the arguments and the bounds they yield remain the same. Without discretization (for example in central DP), you are correct that the random-free family would lead to lower KDE error. However, the resulting mechanism would not be implementable with shuffled DP.

Under shuffled DP, since with both the $(d,1,d)$-LSQ and $(1,\sqrt{d},1)$-LSQ for IP we have $SR^2=d$, the error in both cases is similar. The advantage of the $(1,\sqrt{d},1)$-LSQ is its much smaller $Q$, which doesn’t affect the error to privacy trade-off, but allows better control of the running times and the communication cost.

We have added to the uploaded version a comparison of the KDE error of these two LSQs for the IP kernel (Figure 6, page 24). The results indicate that their empirical error is very similar.

We thank you for the review.

what is the main difficulty in applying to kernel density estimation

Let us highlight the difficulties. Generally, it is not the case that every central DP mechanism can be turned into shuffled DP by replacing its summation operations with shuffled DP sum protocols. Rather, this depends on the specific mechanism. The two main barriers are,

• While central DP mechanisms use explicit noise distributions (like Gaussian or Laplace noise), these distributions are generally not realizable with shuffled DP summation protocols. These protocols yield different noise distributions, which are mostly given non-explicitly, but only as a single statistic (like the RMSE). The mechanism needs to be re-designed and re-proven under those more difficult distributions, and this generally may be difficult or impossible, depending on how the central mechanism utilizes specific properties of its original explicit distributions.
• Shuffled DP sums force errors to be introduced at every summation operation, unlike the central mechanism, which can compute exact sums and introduce noise at other more convenient stages in the mechanism. This creates a new source of error, which accumulates in a way that depends on how the specific central mechanism combines the sums, and needs to be controlled and bounded in order to prove a utility guarantee under shuffled DP.

This is why we have to “open the black-box”, and re-analyze the DP KDE mechanism from first principles in Theorem 3.2, rather than using the existing results from central DP. The proof yields a utility guarantee from much weaker conditions than the central case.

Concretely, in the central DP KDE setting (Wagner et al., 2023), once the notion of LSQ is introduced, the mechanism itself amounts to the basic Laplace mechanism over the LSQ features. This mechanism has known subexponential noise behavior and a built-in utility guarantee in terms of the $\ell_1$-sensitivity. In the shuffled DP case, no such generic off-the-shelf mechanism is available, and the analysis of Theorem 3.2 proves an alternative result specifically for KDE, by analyzing moments of the unspecified distribution of noise that accumulates from bitsums and discretization through the LSQ computation.

Discretization (from real shuffled DP sums to bitsums) is a third source of difficulty, which is necessary to control the bit-width of the mechanism (a notion that does not exist in central DP). In the central KDE mechanism, the LSQ features $f(x)$ (for a given pair $(f,g)\sim\mathcal Q$) are a function of the data point $x$. Under our randomized discretization, they are the result of a randomized computation (thus, two users with the same input and same $f$ would still produce different features). This randomness introduces another source of error that does not exist in the central setting, and needs to be controlled throughout the proof of Theorem 3.2.

As a “negative example”, please see the discussion of DP NNC in the answer to 3tVM. This is a problem related to DP KDE, whose existing central DP mechanism seems non-adaptable to shuffled DP, for (some of) the above reasons, even though all its summation operations are bitsums.

The authors claimed that there is no need to optimize the bandwidth for the Gaussian kernel. However, by shrinking the dataset by some factor, one can equivalently view this as changing the bandwidth. Thus, this claim may not be justified.

This setting of bandwidth is based on the vectors being normalized to unit length (this was stated in line 346, and in the uploaded version we also clarify this in the context of the bandwidth setting as well). You are correct that if the data is scaled, the bandwidth should be scaled accordingly.

Paper title revised, as per the meta-review recommendation. Thank you for the feedback.