Learning from End User Data with Shuffled Differential Privacy over Kernel Densities
Authors: Tal Wagner
Venue: ICLR 2025 Spotlight (2025)
Keywords: differential privacy
shuffled differential privacy
kernel density estimation
kde
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We present a method for collecting and learning a classifier from private data distributed across end users, via kernel density estimates in the shuffled DP model.

Abstract: We study a setting of collecting and learning from private data distributed across end users.
In the shuffled model of differential privacy, the end users partially protect their data locally before sharing it, and their data is also anonymized during its collection to enhance privacy. 
This model has recently become a prominent alternative to central DP, which requires full trust in a central data curator, and local DP, where fully local data protection takes a steep toll on downstream accuracy. 

Our main technical result is a shuffled DP protocol for privately estimating the kernel density function of a distributed dataset, with accuracy essentially matching central DP. 
We use it to privately learn a classifier from the end user data, by learning a private density function per class. 
Moreover, we show that the density function itself can recover the semantic content of its class, despite having been learned in the absence of any unprotected data. 
Our experiments show the favorable downstream performance of our approach, and highlight key downstream considerations and trade-offs in a practical ML deployment of shuffled DP.

Published as a conference paper at ICLR 2025
LEARNING FROM END USER DATA WITH SHUFFLED DIFFERENTIAL PRIVACY OVER KERNEL DENSITIES
Tal Wagner
The Blavatnik School of Computer Science and Al Tel-Aviv University
t www.awregggaaaa.mmmmm com
ABSTRACT
We study a setting of collecting and learning from private data distributed across end users. In the shuffled model of differential privacy, the end users partially pro- tect their data locally before sharing it, and their data is also anonymized during its collection enhance privacy. This model has recently become a prominent al- ternative to central DP, which requires full trust in central data curator, and local DP, where fully local data protection takes a steep toll on downstream accuracy. Our main technical result is a shuffled DP protocol for privately estimating the kernel density function of distributed dataset, with accuracy essentially match- ing central DP. We use to privately learn a classifier from the end user data, by learning a private density function per class. Moreover, we show that the density function itself can recover the semantic content of its class, despite having been learned in the absence of any unprotected data. Our experiments show the fa- vorable downstream performance of our approach, and highlight key downstream considerations and trade-offs in a practical ML deployment of shuffled DP.
INTRODUCTION
Collecting statistics on end user data is commonly required in data analytics and machine learning. As it could leak private user information, privacy guarantees need to be incorporated into the data collection pipeline. Differential Privacy (DP) (Dwork et al., 2006) currently serves as the gold standard for privacy in machine learning. Most of its success has been in the central DP model, where a centralized data curator holds the private data of all the users and is charged with protecting their privacy. However, this model does not address how to collect the data from end users in the first place. The local DP model (Kasiviswanathar et al., 2011), where end users protect the privacy of their data locally before sharing it, is often used for private data collection (Erlingsson et al., 2014; Ding et al., 2017; Apple, 2017). However, compared to central DP, local DP often comes steep price of degraded accuracy in downstream uses of the collected data.
The shuffled DP model (Bittau al., 2017; Cheu al., 2019; Brlingsson al., 2019) has recently emerged as a prominent intermediate alternative. In this model, the users partially protect their data locally, and then entrust centralized authority-called the "shuffler"" shuffling (or anonymizing) the data from all participating users. Data collection protocols in this model are designed so that the composition of shuffling over local user computations rigorously en- sures DP. The appeal of shuffled DP lies in the convergence of theoretical and practical properties: mathematically, recent work has proved that shuffling can boost the accuracy of local DP to levels that may reach those of central DP (Erlingsson et al., 2019; Balle et al., 2019b; 2020b; Koskela et al., 2021; Girgis et al., 2021c; Feldman et al., 2022; 2023; Zhou & Shi, 2022). At the same time, the strictly limited functionality of the shuffler lends itself to realistic secure implementations, and a trusted shuffler can be implemented using techniques from secure computation and cryptog- raphy, like mixnets, onion routing, trusted execution environments (TEEs), and secure aggregation (SecAgg) (Ishai et al., 2006; Bittau et al., 2017; Gordon et al., 2022; Kairouz et al., 2021a;b).
the single operation of
There is by now dell-developed body of work basic operations under shuffled DP, primarily summation (see Section 2.2). Work on machine learning has mostly focused on iterative settings (see Section 2.4), where distributed parties contribute local computations on their sensitive data, like

---

Published as a conference paper at ICLR 2025
gradients, over multiple rounds of shuffled DP communication. This is compatible with distributed (or federated) training scenarios, in which a known set of parties collaborate in a training process that unfolds over time, typically with each contributing local dataset and local computational resources (say, for computing local gradients). For example, the parties could be local branches of a large corporation (e.g., bank), each holding the private data of multiple local customers.
Unfortunately, this is incompatible with data collection scenarios, where a "snapshot" of user data is collected in one shot from a pool of uncommitted users who hold single training point (their own private data), which they may opt in or out of sharing, and who do not participate computationally in the training process beyond possibly contributing their data. For example, the users could be end customers of smartphone app. prompted to privately share statistics about their app activity.
In this work, we study the data collection scenario under shuffled DP. We propose a private learning approach which can intuitively be seen as a shuffled DP analog of a nearest neighbor (kNN) clas- sifier. A distributed training set of sensitive labeled data privately collected from users, and like in KNN, subsequent test points are classified according to the most similar training examples. Since using a small number of neighbors in classification may violate their privacy, our classifier uses ker- nel density estimation (KDE) as a "smooth" alternative to KNN, which can be realized with shuffled DP. It thus labels test points as the class where their privately estimated density is maximized.
Moreover, our classifier produces function representation of each class. We show this representa- tion can be used to recover the semantics of the class-for example, a list of terms that captures the topic of class in textual from the class before privacy was imposed. We refer to this as private class decoding.
though the learner did not observe any unprotected text record
Our results. Formally, we consider the following learning setting. Training data is distributed across n users, each holding a single private training point (ar, c). where x E IRd is a feature vector and [m] is class label. The learner collects data from the users through shuffled DP, and uses them to construct a classifier, which can then be used to classify feature vectors E R from an unlabeled test set. The classifier itself needs to be private w.r.t. the collected dataset; this enables labeling an unbounded number of test points without additional loss of privacy.
To address this setting, our main theoretical result is shuffled DP protocol for KDE estimation, that learns a private KDE function from distributed user data, which can then be used to estimate densities of test points. The utility guarantee is given in terms of the supremum mean squared error over all test points in Rd. so that test points need not be known to the protocol in advance. The proof goes through reduction to binary summation (abbrev. hitsum), which is among the most well-studied problems in shuffled DP, with a variety of available protocols to employ.
Experimentally, we evaluate our method with various combinations of kernels and bitsum protocols, yielding different trade-off's between privacy, accuracy and communication, and highlighting key downstream considerations for shuffled DP compared to central DP and local DP baselines.
2 BACKGROUND AND PRELIMINARIES
2.1 CENTRAL, LOCAL AND SHUFFLED DP
We review models of differential privacy. Let X' be universe of data elements. A dataset is an n- tuple X E X Two datasets X, X' are called neighboring if they differ on at most one coordinate. A randomized algorithm M, that maps input dataset to output from a range of outputs T, is (e, 6DDP if for every pair of neighboring datasets X, X' and every T C T, it satisfies
Px|M(X) E TI e Pr(M((X) E +
(1)
In central DP, single data curator holds dataset X X containing the data of n users, with each coordinate in the n-tuple X representing a user. The curator runs M and releases its output.
In local DP, each user holds her own data element, on which she runs M locally, and releases its output. Here, M operates on a single data element (or 1-tuple), and needs to satisfy eq. (1) for every X' E X' (every pair of single elements is neighboring). A central analyzer collects the already "privatized" outputs from all users and performs an aggregate computation. In this model, there is trusted central party at all, yielding a stronger form of privacy, albeit the cost of accuracy.
2

---

Published as a conference paper at ICLR 2025
The shuffled DP model (Bittau et al., 2017; Cheu et al., 2019; Erlingsson et al., 2019) bridges the central and local DP models, by introducing a limited trusted central party party-called called a "shuffler" whose only function is to anonymize (or randomly permute) the users' outputs before they shown to the analyzer. The analyzer is considered untrusted, simialrly to local DP and unlike central DP. Formally, shuffled DP protocol IT consists of three randomized algorithms πT (TT,, ITş, ATA):
Randomizer R, which maps a single element from X to some sequence of messages. Each user runs A locally on her data element, and forwards the output messages to the shuffler.
Shuffler IIs. which collects the messages from all users and forwards them to the analyzer in uniformly random order (thus, intuitively, removing sender identities).
Analyzer AI which receives the permuted messages from the shuffler and outputs the result of an aggregate computation.
The protocol is (s, 6D in the shuffled DP model if the output of Ilg satisfies eq. (1) (i.e., it holds with MX) == (s (X))). Due to the DP post-processing property (Dwork et al., 2014), the output of A is (e, DDP as well. The parties in the protocol also have access to a source of shared public randomness, which is considered publicly known, and thus cannot be exploited to compromise privacy (see Kairouz et al. (2021a)).
2.2 BITSUM PROTOCOLS IN THE SHUFFLED DP MODEL.
Binary summation, which we refer to throughout as bitsum, is a fundamental and well-studied prob- lem in DP, and particularly in shuffled DP. Each of n users holds a private bit X, (), and the goal is to compute DP estimate of the sum S = Di Biml X, The accuracy of a randomized estimate SS is often quantified by its root mean squared error (RMSE), (E((S 5)2))1/2.
A long line of work on shuffled DP bitsums (Cheu et al., 2019; Cheu & Yan, 2021; Ghazi et al., 2020b;a; 2021b; 2023) had yielded protocols whose RMSE essentially matches central DP, and is significantly better than local DP, along with additional desirable properties, like low communication and pure DP (i.e., 8 = 0). We will use these protocols as black-boxes and not require familiarity with their details. For completeness and intuition, we describe how they work in Appendix B.
2.3 PRIVATE KERNEL DENSITY ESTIMATION
Let k : Rd x Rd + R be a kernel, such as the Gaussian kernel k(x,v) v) = exp( - vll.). The kernel density estimation (KDE) map K DExx Rd + IR, associated with multiset X Rd of size n, is defined as K (D)x(y) = - x k(r,,).
Numerous works studied KDE in the central DP model (Hall et al., 2013; Wang et al., 2016; Alda & Rubinstein, 2017; Coleman & Shrivastava, 2021; Wagner et al., 2023; Backurs et al., 2024), mostly setting known as function release. In this setting, the data curator holds all of X, and her goal is to release a function description K--) which DP w.r.t. X, such that K K(y) an accurate estimate of K KDFx (v) for every y E Rd. We will adapt this problem to the shuffled DP model in Definition 3.1. Our approach to this problem will use the following notion of locality- sensitive quantization (LSQ), recently introduced in Wagner et al. (2023) for KDE in the central DP model.
O. Let Q be distribution over pairs of functions f. IRd + [-R, RR, R We say that Q is a 8-approximate (Q, R, S)-localyty sensitive quantization (abbrev. LSQ) family for the kernel k, the following are satisfied for all x, y E Rd:
Definition 2.1 (Wagner et al. (2023)). Let S.B
1k(x,))- (())) g(v)]] S
[[() and g(y) have euch at most S non-zero coordinates.
If this holds, then k is (-approximate R2 SY-LSQabee If O, then k is (Q, R, S)-SSable....
For example, Wagner et al. (2023) observed that the Gaussian kernel is (1, 22, 1)-LSaable by ran- dom Fourier features (Rahimi & Recht, 2007), and the Laplacian and exponential kemnlss are 3- approximate (O(B-1), 1)-LSQable for all B > 0 by locality sensitive hashing (Indyk & Motwani, 1998). They proved that LSQable kernels admit efficient KDE mechanisms in the central DP model. We will prove an analogous result for shuffled DP. While we draw on ideas from their central DP mechanism, our proofs will be different and self-contained.
3

---

Published as a conference paper at ICLR 2025
2.4 ADDITIONAL RELATED WORK
Prior work on machine learning with shuffled DP has mostly focused on two iterative learning set- tings: distributed and federated model training (Cheu al., 2021; Girgis et al., b021b;a; Liu et al., 2021; Kairouz et al., 2021a), where users share privately computed gradients; and multi-armed and contextual bandits (Tenenbaum et al., 2021; Chowdhury & Zhou, 2022; Zhou & Chowdhury, 2023; Tenenbaum et al., 2023), where users share private contexts and rewards. The main difference from our setting is their iterative nature, in which the users communicate with the analyzer over multiple rounds of shuffled DP protocol. Of these, Tenenbaum et al. (2021) is somewhat akin to us in that they also reduce their problem to bitsums, although their case the connection more direct as they assume binary rewards in their multi-armed bandits problem.
Beyond bitsums, there has been much work on shuffled DP protocols for integer and real summation (Cheu et al., 2019; Cheu & Zhilyaev, 2022; Balle et al., 2019b;a; 2020a; Ghazi et al., 2020b;a; 2021b; Balcer et al., 2021) and other basic operations (Balcer Cheu, 2019; Ghazi et al., 2019; 2021a; Chen et al., 2020a; Chang et al., 2021; Scott et al., 2021; Tenenbaum et al., 2023), We discuss real summation in the context of our work in more detail in Appendix B.2.
Outside shuffled DP, relevant work in the central DP model is Backurs al. (2024), who also suggested a classifier that maximizes the privately computed similarity to a class. They presented results for the (I0AR-10 dataset by measuring distances class means. Our experiments in Sec- tion 4 include the same data in a distributed setup, evaluated with our shuffled DP protocol.
3 DATA COLLECTION AND CLASSIFICATION WITH SHUFFLED DP
In this section we present our private data collection and learning protocol. In Section 3.1, we dis- cuss certain practical considerations with shuffled DP, that would inform the design of our method. In Section 3.2, we give our shuffled DP result for KDE, which is the main building block in our classifier. In Section 3.3, we use it to privately learn classifier from collected user data.
3.1 PRACTICAL CONSIDERATIONS WITH SHUFFLED DP
User counts. A key limitation of shuffled DP is that protocols are required to know in advance the number of participating users n. Technically, the noise added by each local randomizer IT generally decreases with n. This is crucial for boosted accuracy, albeit if some users drop out, the protocol fails to meet its DP guarantee for the remaining users. This limitation may be acceptable in the distributed training scenario from Section 1, where predetermined group of parties is expected to collaborate on training and reliably execute the protocol. However, in our data collection scenario, would make less sense to assume that the number of participating users is known in advance. We will therefore designate a preliminary communication round for allowing users to opt into participation.
Privacy threat models. There are several possible places to impose DP in an ML pipeline. Pono- mareva et al. (2023) outline three options, from the most stringent to most lenient form of privacy: imput/data-level DP, where the adversary has access the data used train the ML model; model- level DP, where the adversary has full access to the weights of the trained model; and prediction- level DP, where the adversary has access only to model outputs when presented with test points.
We will consider the first two of these options, adapted to shuffled DP. Input/data-level DP means the adversary sees all communication sent to the analyzer (equivalently, the analyzer itself is the adver- sary). Note that communication from the users to the shuffler is never exposed (that would void the premise of shuffled DP); practice, this line of communication implemented cry cryptagraphically. exploiting on the restricted nature of the shuffler (Kairouz et al., 2021a). However, the adversary can see all communication between the shuffler and the analyzer, as well as all direct communication (if any) between the users and the analyzer. We refer to this as the communication- model-level DP, a weaker adversary sees only the trained model released by the analyzer after the protocol execution is complete; we refer to this the model-threat model. These threat models are typically not differentiated in prior work on shuffled DP, since they often coincide; however, in our case, the trained model would leak less privacy than the communication used to learn it.
model. In
4

---

Published as a conference paper at ICLR 2025
Algorithm 1: Shuffled DP KDE protocol from bitsums
Global initialization // all data here is public
Analyzer // runs after the shuffler
input: shuffled DP bitsum protocol II;
input: shuffled sequence of messages
(Q, RS-LSQ family Q; integer
from
1>
for (i,j) E [T] x [Q] do
for .....,, do
L T ij t empty sequence
(Ji, 9t) <- indepennden sample from Ω // uusnn shared/public randonness
for message (7, (i.j)) in I' do
for j 1,...,... do
L append 7 to F
iT < independent instance of
for (i.j) [4] x [Q] do
publish: gi) for all i....., Randomizer // each user runs this locally with
Big +- run the analyzer Uy on Pig
Fij < (2B:; n)
private randonness
publish: Fig for i,
input: private data point E IRd
for (i, [ x Q do by < (ernoulli(005() + (fa(z)))
KDE Query // runs on the analyzer's
published output arbitrarily many times
Fg + run the randomizer of Hhy on by
input: query point E Rd
for message 7 in L'j do
return: 77 Ei E Poj (9:(1)),
send (7, (i.j)) to the shuffler
Bit-width and discretization. Kairouz et al. (2021a) emphasize that in practice, the shuffler imple- mentation often requires modular arithmetics for cryptographic secure aggregation. Therefore, the shuffled DP protocol's numerical values must be discretized, and its bit precision (called bit-width) needs to be explicitly bounded. Neglecting to account for the bit-width may lead to impractical communication costs and to larger errors (due discretization) than real-valued analysis predicts. We will therefore incorporate discretization into our protocol and account for it in the error analysis.
3.2 SHUFFLED DP KDE FROM BITSUM PROTOCOLS
We now present the theoretical backbone of our private learning approach, shuffled DP protocol for KDE. We start by defining the KDE problem in the shuffled DP model.
Definition 3.1 (shuffled DP KDE). In the shuffled DP KDE problem, a dataset points in R is distributed across users, one point per user. The goal is to devise shuffled DP protocol HKDE in which the analyzer releases function description K()), required to be (s, 8DD w.t.. X. The supremum root mean square error (abbrev. SupRMSE) of the protocol is defined as
(R') of
EE ((())KDEX(())
SupRMSE([IKDE) == sup yERd
Our main technical result is the following theorem, which is reduction from KDE to bitsum pro- tocols in the shuffled DP model, for kernels with the LSQ property defined in Definition 2.1. The resulting shuffled DP KDE protocol given Algorithm I.
Theorem 3.2. Let k be (-approximate (Q, R. S)-LSQable kernel (cf. Definition 2.1). Suppose have an unbiased (Eo, ) bitsum protocol 11 in the shuffled DP model, with RMSE En, Then, for every 8' > 0 and integer the communication-threea model, where (e -1) + 2
0, Algorithmm 1 is shuffled DP KDE protocol, which is (c, DDP in
In(1/8") and 8 TS6 + with supRMSE /4 + 16R (S (En/n)²). The protocol has optimal bit-width 1.
Note that E, 8 take the familiar "advanced composition" form (Dwork et al., 2014) of instances of an (Eo,S, DD mechanism. The proof of Theorem 3.2 goes by showing that the LSQ coordinates can be discretized essentially without loss of accuracy, and invoking the bitsum protocol the dis- cretized coordinates, using a careful probabilistic analysis to bound the overall suPRMSE from their individual RMSEs. It is given in full in Appendix A. Appendix A.1.7 also discusses additional variants of Theorem 3.2, for bitsum protocols whose error guarantee is given in other terms than the RMSE (like Cheu al. (2019)), or that achieve pure DP (like Ghazi et al. (2020a; 2023)).
5

---

Published as a conference paper at ICLR 2025
As concrete instantiation of Theorem 3.2, get the following result for the Gaussian kernel, by plugging the shuffled DP protocol from Ghazi et al. (2020b) as the bitsum protocol, and random Fourier features (Rahimi & Recht, 2007) the LSQ family. The proof is in Appendix A.2. For completeness, the protocol for this special case is fully detailed in Algorithm 2 in the appendix.
Theorem 3.3 (shuffled DP Gaussian KDE). There are constants C, C' > O such that the following holds. Let & E (0,1) 1) and e I (olo((/8)) For every a 2 C' C'vion (Log(1) (1/))////))))))))) there is an (c, 6 model) with
Gaussian KDE protocol in the shuffled DP model (under the communication- users and imputs from IRd, which has: supRMSE a, user running time (di(O(d/a)) O(d+1/a²)) expected communication of ((1/2²) bits per user, expected analyzer running time O(n/a²). KDE query time min(O(d/a²), O(d + 1/a²)), and optimal bit-width 1.
3.3 PRIVATE LEARNING, CLASSIFICATION AND CLASS DECODING
We now describe our private learning approach for classification and class decoding. Recall that each user holds a private data point E IRd and a corresponding label E [m]]
Learning. The learner will aim to learn a KDE function representation per class, using the shuffled DP protocol from Theorem 3.2. As discussed in Section 3. I, this requires knowing in advance the number of participating users per class. We therefore start with a preliminary communication round designated to privately obtain these counts. This could be done with an off-the-shelf shuffled DP histogram protocol (e.g.. Ghazi et al. (2020b)); however, this again requires prior knowledge of the total number of users. To avoid this chicken-and-eg preliminary communication round. is stronger form of privacy that requires no prior knowledge, and its accuracy, while degraded, is still sufficient for the simple task of private user counts.
issue, we will use vanilla local DP for the
Formally, let Eo, dg, Elh 0 be privacy parameters. Learning proceeds follows. First, each user locally protects her label e and publishes a privatized label é, using m-ary randomized response (Kairouz et al., 2014; 2016). Thus, è is set to with probability d / (e uniformly random label from [m] \ {e} otherwise. This ensures that č is SDn-DP, without shuflling.
m), and to
Based on the published labels, the learner groups the users into their reported classes, and publishes the count of users 74 in each reported class ē E [m]] These counts are DD by post-processing. and thus safe to publish. The users in each reported class then execute the shuffled DP KDE protocol in Algorithm 1, using Eo, 6g as the privacy parameters for each instance of the bitsum protocol II. The learner acts as the analyzer all these protocols, and through them learns an approximate KDE function (-) for each label e E [ma]. From Theorem 3.2 and from basic DP composition, we have the following privacy guarantee:
Corollary 3.4. The above learning protocol is (E, 8) in the model-threat model, and (E+ 5)- DP in the communication-lie model, where e, 8 are given by So, ôn as stated in Theorem 3.2.
Classification. The learner classifies a test point y E Rdd the class where its private density estimate is maximized, namely as cy = lm class (HDC) classifier. It can be viewed generalizing the k-nearest neighbor (kNN) classifier, where the density of w.r.t. class is measured by the number of its k-nearest neighbors labeled e, and of the nearest class center (NCC) classifier (Papyan et al., 2020), where the density is measured by the distance between to the mean of all data points labeled c. Note that the kNN classifier is incompatible with DP, since its output relies on a small number of training points, while the NCC classifier is special case of HDC, which we include in the experiments in the next section.
We refer to this as the highest density
Private class decoding. To illustrate class decoding, Suppose that the data points are embeddings of text documents (even though the notion extends to other data modalities as well). Let V C IR be a fixed public "vocabulary". say the embeddings of all words in an English dictionary. To "decode" a class c, the learner returns the top few vocabulary words v E V that maximize (v). The goal is for those words capture and convey the semantic meanings of texts from class c.
To underline the distinction between classification and class decoding: classification relies on the ability of the collection of functions {Ke)ce to produce meaningfully rankable scores over the different classes for fixed input y E Rd; class decoding relies on the ability of each fixed function K, produce meaningfully rankable scores over large collection of inputs V C IRd. In general,

---

Published as a conference paper at ICLR 2025
expect learned representation of a class to encompass its semantic meaning and to be decodable. The particular challenge in shuffled DP is that the representation was learned without observing any raw training example from the class, i.e,, prior to imposing differential privacy the training data.
4 EXPERIMENTS
We evaluate our method with several combinations of kernels and bitsum protocols. Our code is enclosed in the supplementary material and available online.
Datasets. We use three textual datasets and one image dataset:
DBPedia-14 14 (Zhang et al., 2015): Text documents containing summaries of Wikipedia articles. Training examples: 560K, test examples: 70K, classes: 14, task: topic classification.
AG news (Zhang et al., 2015): Text documents containing news articles. Training examples:
120K, test examples: 7.6K, classes: task: topie classification.
SST2 (Socher et al., 2013): Sentences extracted from movie reviews. Training examples: 67.3K,
test examples: 1.82K, classes: 2, task: sentiment classification (positive/negative).
CIFAR-10 (Krizhevsky, 2009): Images from different object categories. Training examples: 50K, test examples: 10K, classes: 10, task: depicted object classification.
The datasets are embedded in IR using standard pretrained models. The textual datasets are embed- "all-ae-p
ded into 768 dimensions with the 2019). CIFAR-10 is embedded into 6144 dimensions with the SimCLR "r152.3x_ski model (Chen et al., 2020b), pre-trained on Imagenet (these are the same embeddings used in Backurs et al. (2024) for their central DP experiment). All embedding vectors that the datasets are not included in the pretraining set of the respective embedding models used to embed them, ensuring that the pretraining set does not leak privacy in our experiments.
model (Reimers & Gurevych,
normalized to unit length. We note
Kernels. We experiment with two kernels that fit into the framework of Theorem 3.2:
k(x; v) exp(-Il= 3112) As noted in Section 2.3, (1, v2, 1)-LSQable by letting the functions in Q be random Fourier features, leading to Theorem 3.3.
Gaussian:
IP: The inner product kernel k(x. v) = x²T y. Since our embeddings are normalized, it is trivially (d, 1, d)--SSQbble. It is also (1, vd, 1)-LSQable by standard dimensionality reduction arguments (see Appendix A.3), which leads to better parameters in Theorem 3.2, Note that for a subset X' of training points, the IP KDE at y [XT ΣzExy y y" (xX Σ Ezex z). Thus, the HDC classifier labels y by the most similar class mean, as the NCC classifier discussed in Section 3.3.
To equalize the computational costs of the two kernels, we set number repetitions / in Algo- rithm I to d (the embedding dimension). Since the embeddings have unit length, there is no need to clip the vectors at a hyperparameter (as in Kairouz et al. (2021a); Backurs et al. (2024)) for the IP kernel, nor to optimize bandwidth for the Gaussian kernel (it is just set to 1).
Bitsum protocols. We use three shuffled DP bitsum protocols from the literature, each optimal in a different measure efficiency, accuracy and privacy, respectively (see also Appendix B.
RR: The classical randomized response protocol, as adapted to shuffled DP by Cheu al. (2019).
This protocol has optimal communication efficiency of a single one-bit message per user.'
3NB: The correlated noise protocol of Ghazi et al. (2020b), which has asymptotically optimal accuracy. We call it 3NB since it relies on three samples from negative binomial distribution.?
Pure: The pure DP (5 = 0) protocol of Ghazi et al. (2023). The other protocols use 0.3
Privacy parameters. We follow the guidelines given in Ponomareva et al. (2023), who cite current machine learning deployments of DP as using E generally between
15, and advocate for g < 10 as an acceptable privacy regime. We use E E (0, 10) to protect the training point E R2 with (s, -h-ufffe DP, and EIP E (3. 5, 7, 10) to protect the label e E [m]] with (Eıb), Oo-la DP. We use 5 10-6 for DBPedia-1e 14 and AG news, and 8 = 10-5 for SST2 and CIFAR-10, accounting for the
See Section 4.2 for detailed discussion communication costs.
"See 1/1, the, a/s in Algorithm in the appendix.
"To maintain purity in Algorithm I when composing instances of Pure, they are composed with "basic" (pure) rather than "advanced" (approximate) DP composition (Dwork et al., 2014). See Appendix A.1.7.
7

---

Published as a conference paper at ICLR 2025
1.0
DEpedia-14 14 with RR
1.0
DBoodia- 14 with 3NB
1.0
DBpedio 14 with Pure
0.6
9503800
0.6
aecurncy
0.6
0.4
0.4
0.4
0.2
02
0.2
2
10
2
10
2
10
epellon
speloo
epelion
AG FR
with 3MB
with Pure
0.8
0.8
0.8
0.6
8000005
0.6
0.6
0.4
0.4
0.0
0.0
0.0
2
10
2
10
2
10
opailon
apailon
opsilon
1.0
38T2 with 3NB
88T2 with Pure
0.6
0.8
0.8
0.6
0.6
0.6
0.2
02
0.2
0.0
0.0
0.0
10
opailan
spailon
opsiion
1.0
CIA-R-1 13 with IX
1.0
CIEAR-11 with 3NB
1.0
CIFAR 10 with Pure
0.8
0.4
0.4
0.4
0.2
02
0.2
0.0
10
10
10
opsilon
IP kernel, shuffled DP
IP kernel, central DP
kernel, no privacy
Gaussian kemel,, shuffled DP
Gaussian kernel, central DP
Gaussian kernel, no privacy
Figure 1: Classification results with Sab] = 5
different dataset sizes. For RR and 3NB, the å "budget" in Theorem 3.2 is split equally between the advanced composition parameter 8' and the total IQ8, term of the bitsum protocol instances.
4.1 PRIVATE CLASSIFICATION RESULTS
We evaluate the HDC classification accuracy for each combination of kernel and bitsum protocol, Gaussian, IP) x (RR, 3NB, Pure), on each the dataset. Figure I shows results for Ema = 5 (solid lines). Results for other values of EιbI are similar and appear in the appendix (Figures 5 to 8).
As points of reference, we include the following two baselines for each kerne::
(e, 8)-eentaal DP (dotted lines): HDC with the bitsum protocols in Algorithm I replaced by the standard Gaussian DP mechanism (see Section A in Dwork et al. (2014)).
No privacy (dash-dot lines): HDC with the bitsum protocols replaced by exact summation.
In the appendix (Figure 4), we also include an ablation against local DP baseline.
8

---

Published as a conference paper at ICLR 2025
365
2MB
6R
101
000 Am
spalee
Figure Empirical communication
dipeda
**-Eentrll
Sruftlee----8
spule
bodian
Figure 3: Gaussian KDE accuracy
The results exhibit consistent behavior. Without privacy, the IP kernel outperforms the Gaussian kernel in all settings. This corroborates the known effectiveness of the NCC classifier neural embeddings (see Papyan et al. (2020)). Moreover, central DP closely matches the corresponding non-DP downstream accuracy already at small values of e, which corroborates similar empirical finding reported in Backurs et al. (2024).
Under shuffled DP, however, this behavior varies in different settings. The Gaussian kernel is more resilient to errors than IP, and thus matches its central DP and non-DP HDC performance at broader parameter regimes. As result, it often achieves better overall accuracy than IP, even though its baseline (non-DP) accuracy is lower. This phenomenon is more expressed the more error-prone the setting is both with lower privacy budgets (lower e), and when the bitsum protocol is less optimized for accuracy (i.e., RR and Pure vs. 3NB). The upshot is that the shuffled DP model, due its more delicate interplay between communication, privacy and accuracy compared the central DP and non-DP settings, may require different and more error-resilient mechanisms for better downstream performance, particularly under tighter privacy and communication constraints.
4.2 COMMUNICATION COST
The communication cost of our learning protocol depends on that of the bitsum protocol used within Specifically, for both the Gaussian and IP kernels, the communication cost as follows:
With RR: each user sends exactly messages.
With 3NB: the number of messages sent by each user is random variable (different per user), with expectation (1 +1+ ol))dd. (The o(1) term vanishes as either n or grows.)
With Pure: the number of messages sent by each user is random variable (different per user), with expectation (dd log(n)/Eo).
With all three protocols, each message is of size [log + bits.
Figure displays the empirical number of messages on each dataset, for RR (whose communication is constant, as per above) and 3NB (whose communication is random variable). Note while the cost of 3NB asymptotically near-similar RR, in practice its cost can be few times larger, which may be significant in applications. Pure sends orders of magnitude more messages (as per above), which may render impractical tight communication settings, and cannot fit the same plots.
4.3 PRIVATE KDE RESULTS
We also directly evaluate Theorem 3.3 for the standalone task of private Gaussian KDE (without subsequent classification). The results are shown in Figure 3, with accuracy measured over 1K random queries from the query of each dataset. They show that the KDE error generally tracks with the downstream classification accuracy reported above, with 3NB being the most accurate variant with error vanishing nearly as fast as central DP, followed by RR and Pure.

---

Published as a conference paper at ICLR 2025
Table 1: Private class decoding results with E R 3.2 and ebb
Dataset
Class
Bitsum Gaussian KDE class decoding
IP KDE class decoding
DBPedia-14
RR
venders, gencorp. servicers molycopp, newsoorp, mediucurp
liresign, wnews,
Company
3NB
alicurp, interactivecurp attobaees escorp. companies
Pure
ameritech, alicorp, newsoorp
biopie, movie, screenplay
kaptai, kakhi, kaloi
Film
3NB
fimography, vanya, ghestbusters
movic, fimogrrpphy. screenplay movie, film. filmmakers
Pure
filme, movie, videodrome
RR
vizner, runnemups, dietrichson
ongeri, grandi, zarale semifinalists, championship, standings chauci, teammates, nith
AG news
Sports
BNB
injury, semifinalisss, finalists pensford, rematchos, undefeated
Pure
RR
repurchases, downtrend, equitywatch
sneed, timesnews, ansiousness stackholders, nasdaq, marketwatchoom merger, divestiture, stocKholders
Business
3NB
enrononline, investeurp, comcorp
Pure
corporations. comsolitations. consolidated
beguile, inception, shallow melodrama, rawness, blandness
manipulating, uncouple, dissccts comedy, tastelessness, uneasiness absurdities, chastisement, absurdity
SS12
Negative
3NB
Pure
chumminess, meaningfulness, mooiness
kindliness, pleasantness, entertaining
enjoyments, academic, amusements salaciousness, theatricality, memorability exorcisms, fairytales, revisiting
Positive
3NB
salacious, movie, mujestic spiritedness, spirited, perspicacions
Pure
4.4 PRIVATE CLASS DECODING RESULTS
We perform class decoding, as described in Section 3.3, on the three textual datasets. As the public vocabulary V we use GloVe 6B (Pennington et al., 2014), consisting of 400K words extracted from public sources. Rather than using the embeddings from Pennington et al. (2014), we embed the terms in gd with the same pre-trained SentenceBERT model used to embed the datasets. Then, for each class E [m]] of each dataset, we rank all vocabulary terms according to their density as reported by the function (-(-) privately learned by our shuffled KDE protocol for that class, and report the top-3 scoring terms. We repeat this for every combination of kernel and bitsum protocol.
We make no attempt at quantifying a measure of class decoding performance, since semantic re- latedness is inherently somewhat subjective, and may furthermore depend on external knowledge (for example, when the "artist" or "athlete" classes are decoded into names of specific artists or athletes). Rather, our goal in this experiment to is gain qualitative insight into what the shuffled DP KDE protocol succeeds in learning, despite its lack of access to unprotected training examples, and to complement the quantitative classification accuracy results.
Table I includes decoding results with e 3.2 and EIbI = (the values are slightly different across the datasets and bitsum protocols, due to the use of different values and composition theorems, as detailed earlier in this section). It only includes some classes from each dataset, due to space limits; results for all classes, and for other values of E, are in the appendix.
Qualitatively, in settings where classification accuracy is nontrivial (per Figure 1), the class decod- ing results in Table 1 also yield vocabulary words that aligned with the topic of the class. This demonstrates that the class representations learned by shuffled DP KDE protocol capture the seman- tic meaning of the classes, and preserve the ability rank not only inter-class similarities (as needed for classification), but also intra-class similarities (as needed for decoding a specific class).
CONCLUSION
We showed how to use shuffled DP for "one-shot" data collection and learning from an undeter- mined pool of uncommitted end users, in contrast to prior work on ML with shuffled DP, which mostly focused on collaborative distributed training across committed parties over time. Due to the desirable accuracy of shuffled DP, our method is able to learn intricate data semantics while ad- hering to a distributed notion of privacy. Our experimental results highlight practical downstream considerations related to the delicate interplay between privacy, accuracy and communication cost.
Future work would explore further ways to deploy shuffled DP in ML pipelines, and extend to more challenging settings, such as privately and continuously monitoring end user data over time.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank the anonymous reviewers for helpful feedback. Work supported by Len Blavatnik and the Blavatnik Family foundation and by an Alon Scholarship of the Israeli Council for Higher Education. Author also with Amazon. This work associated with Amazon.
REFERENCES
Nir Ailon and Bernard Chazelle. The fast johnson johnson-lindenstraue transform and approximate nearest neighbors. SIAM Journal computing, 39(1):30--322, 2009.
Francesco Alda and Benjamin IP Rubinstein. The bernstein mechanism: Function release under differential privacy. In Thirty-First AAAI Conference on Artificial Intelligence. 2017.
Differential Privacy
Team URL
at Apple. http://aannnneeeaaaeeea hwp.arannnnn.apll........ apple. cwt. com/research/ https:/
Learning with privacy scale.
2017.
Arturs Backurs, Zinan Lin, Sepideh Mahabadi, Sandeep Silwal, and Jakub Tarnawski. Efficiently computing similarities to private datasets. International Conference on Learning Representa- lions (ICLR), 2024.
Victor Balcer and Albert Cheu. Separating local shuffled differential privacy via histograms. arXiv preprint 11X669191.00887, 2019.
Victor Balcer, Albert Cheu, Matthew Joseph, and Jieming Mao. Connecting robust shuffle privacy and pan-privacy. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2384-2403, SIAM, 2021.
Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim. Improved summation from shuffling. arXiv preprint arXiv: 1909. /225,, 2019a.
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket the shuffle model. -RRYPPO In Advances in Cryptology CRYPTO 2019: 39th Annual International Cryptology Conference,
Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part 39, pp. 638-667. Springer, 2019b.
Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim. Private summation in the multi-message shuffle model. In Proceedings of the 2020 ACM SIGSAC Conference Computer and Commu- nications Security, pp. 657-676, 2020a.
Borja Balle, Peter Kairouz, Brendan McMahan, Om Thakkar, and Abhradeep Guha Thakurta. Pri- vacy amplification via random check-ins. Advances in Neural Information Processing Systems, 33:4623 4634, 2020b.
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics the crowd. In Proceedings of the 26th symposium on operating systems principles, pp. 441-459, 2017.
Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. In International Conference Machine Learning, pp. 1441-1451. PMIR, 2021.
Lijie Chen, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On distributed differential privacy and counting distinct elements. arXiv preprint 2094440009.0904 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pp. 1597-1607. PMLR, 2020b.
Albert Cheu and Chao Yan. Pure differential privacy from secure intermediaries. arXiv preprint arXiv:2/12. 2021.
11

---

Published as a conference paper at ICLR 2025
Albert Cheu and Maxim Zhilyaev. Differentially private histograms in the shuffle model from fake users. In 2022 IEEE Symposium on Security and Privacy (SP). pp. 440-457. IEEE, 2022.
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed dif- ferential privacy via shuffling. In Advances in Crypology-EUROCRKKE EUROCRYPT 2019: 38th Annual In- ternational Conference on the Theory and Applications of Cryptographic Techniques. Darmstadt, Germany, May 19-23, 2019, Proceedings, Part 38, pp. 375-403. Springer, 2019.
Albert Cheu, Matthew Joseph, Jieming Mao, and Binghui Peng. Shuffle private stochastic convex optimization. arXiv preprint wrXvv2206.09900 2021.
Sayak Ray Chowdhury and Xingyu Zhou. Shuffle private linear contextual bandits, arXiv preprint arXiv:2202.05567, 2022.
Benjamin Coleman and Anshumali Shrivastava. In Proceedings of the ACM SIGSAC Conference Computer and Communications Security (CCS), pp. 3252-3265, 2021.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Ad- vances Neural Information Processing Systems, 30, 2017.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference (TCC), pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trendso Theoretical Computer Science, 9(3-4):211 (0:-4:2111407 1077 2014.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1067, 2014.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pp. 2468-2479. SIAM, 2019.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 954-964. IEEE, 2022.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for rényi and approximate differential privacy. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4966-4981. SIAM, 2023.
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. Private heavy hitters and range queries in the shuffled model. arXiv preprint 190iv:190..113:3 2019.
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Ameya Vel- ingker. Pure differentially private summation from anonymous messages. arXiv preprint arXiv:2002.01919, 2020a.
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. Private counting from anonymous messages: Neti-optimal accuracy with vanishing communication overhead. In International Con- ference Machine Learning, pp. 3505-3514 PMLR, 2020b.
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages: Frequency estimation and selection in the shuffle model of differential privacy. In Annual International Conference on the Theory and Applications of Cryp- tographic Techniques, pp. 463-488. Springer, 2021a.
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, and Amer Sinha. Differentially pri- vate aggregation in the shuffle model: Almost central accuracy in almost a single message. In International Conference Machine Learning, pp. 3602-37011 PMLR, 2021b.
12

---

Published as a conference paper at ICLR 2025
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Pure-dp aggregation in the shuffle model: Error- optimal and communication-efficae arXiv preprint arXiv:2305.176624 2023.
Antonious Girgis, Deepesh Data, and Suhas Diggavi. Renyi differential privacy of the subsampled shuffle model in distributed learning. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp. 29181-29192. Curran Associates, Inc., 2021a. URL https: http:////oooedd/eeeeeee neurips cc wwtpppppppppeeeeeeeee _f http://4c222221111a1224241eaaaaa
Antonious Girgis, Deepesh Data, Suhas Diggavi. Peter Kairouz, and Ananda Theertha Suresh. Shuf- fled model of differential privacy in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 2521-2529 PMLR, 2021b.
Antonious M Girgis, Deepesh Data, Suhas Diggavi, Ananda Theertha Suresh, and Peter Kairouz. On the renyi differential privacy of the shuffle model. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pp. 2321-2341, 2021c.
Dov Gordon, Jonathan Katz, Mingyu Liang, and Jiayu Xu. Spreading the privacy blanket: Dif- ferentially oblivious shuffling for differential privacy. In International Conference Applied Cryptography and Network Security, pp. 501-520. Springer, 2022.
Slawomir Goryczka and Li Xiong- A comprehensive comparison of multiparty secure additions with differential privacy. IEEE transactions on dependable and secure computing, 14(5):463- 477, 2015.
Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and func- tional data. Journal of Machine Learning Research, 14(Feb):703-722 2013.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613, 1998.
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography from anonymity. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS (FOCS'06), pp. 239- 248. IEEE, 2006.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27, 2014.
Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under local privacy. In International Conference on Machine Learning, pp. 1436-2444 PMLR, 2016.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning, PMLR, 2021a.
pp.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and trends@ in machine learning, 14(1-2):1-210, 2021b.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
Antti Koskela, Mikko A Heikkilä, and Antti Honkela. Tight accounting in the shuffle model of differential privacy. In NeurlPS 202/ Workshop Privacy in Machine Learning, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009,
Ruixuan Liu, Yang Cao, Hong Chen, Ruoyang Guo, and Masatoshi Yoshikawa. Flame: Differen- tially private federated learning in the shuffle model. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8688-8696, 2021.
13

---

Published as a conference paper at ICLR 2025
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 14652-246633 2020.
Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). pp. 1532-1543, 2014.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy mi: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113-1221 13-1201, 2023.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. arXiv preprint arXiv: /908. 10084, 2019.
Mary Scott, Graham Cormode, and Carsten Maple. Applying the shuffle model of differential pri- vacy to vector aggregation. arXiv preprint arXiv:2112 054664 2021.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning. Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631-1642, Seattle, Washington, USA, October 2013. Association for Computa- tional Linguistics. URL https::////.. /wwp://wwwww///////////////wwo aclweb. org/ att.aooooooooo 1170.
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private multi- armed bandits in the shuffle model. Advances in Neural Information Processing Systems, 34:
24956-24967, 2021.
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Concurrent shuffle differen- tial privacy under continual observation. In International Conference Machine Learning, pp- 33961-33982. PMLR, 2023.
Tal Wagner, Yonatan Naamad, and Nina Mishra. Fast private kernel density estimation via locality sensitive quantization. In International Conference on Machine Learning (ICML), pp. 35339- 35367. PMLR, 2023.
Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang. Differentially private data releasing for smooth queries. Journal of Machine Learning Research, 17(51):1-42, 2016.
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, 1965.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gareett (eds.), Advances in Neural Information Processing Systems, volume 28, 2015. URL
www.inngg..uuursss nwwrips....... wttpssscccppppppee .df.
Mingxun Zhou and Elaine Shi. The power of the differentially oblivious shuffle in distributed privacy mechanisms. Cryptology ePrint Archive, 2022.
Xingyu Zhou and Sayak Ray Chowdhury. On differentially private federated linear contextual ban- dits. arXiv preprint 13X1v22302.13955, 2023.
14

---

Published as a conference paper at ICLR 2025
A PROOFS
A. PROOF OF THEOREM 3.2
We restate the theorem for convenience:
Theorem A.1 (Theorem 3.2, restated). Let k be B-approximate (Q, R. Sy-LSQable kernel (cf. Def- inition 2. 1). Suppose we have an unbiased (Eo, 5D) bitsum protocol IT in the shuffled DP model, with RMSE En- Then, for every 8' > and integer O, Algorithm is shuffled DP KDE protocol, which is (e, DDD in the communication-trre / 1n(1//0 in(1/8)) and ô = IS50 + 8', with supRMSE / 16 (Eu/n)3)). The protocol has optimal bit-width
model, where E = EnS(e -1)1 +
The proof proceeds in three steps: (i) discretize the LSQ coordinates of f((x) locally at each user from [-R, R] to {-R, R), using randomized rounding to maintain the LSQ property; (ii) use the bitsum protocol to estimate the sum of each discretized coordinate (with shifting and scaling to turn bitsums into + -[-sums); (iii) use the LSQ property together with the RMSE bound of the given bitsum protocol to bound the total error of any output KDE estimate.
A.1.1 DISCRETIZATION
We will index the users in the protocol by I,..., Fix i [I]. Let (fr. be the pair sampled from Q in the global initialization step of Algorithm 1, and recall that fi.9: : Rd - [-R, R2) Consider user the user samples byj (ernoulli(f((t.)) + Rt/220 22) using private randomness, independently of the other users and of the other coordinates. To refer local samples of different users, in this proof
[n] with input In E TR.. In the randomizer of Algorithm 1, for every j E [Q).
we will denote bij by b
Define f!!)) E [ by letting figi) = =(2b()) R) for every j.
Claim A.2. For every E [4], u [n]] and y R2d
( (( k(I,w) S 3,
where the expectation over both the sampling of (Ji; 96) ~ 2 in the global initialization part and the sampling of (b j e [Q]] in the randomizer part of Algorithm 1.
Proof. It is immediate check that 1 (()) 1 [i] Si(#u)g for every j. hence,
B ((aa))
( 9:(v)] = B(rro)) (Biogg) (1 g(()) (Fr.0)]
B(roo) ([(x)"(:(())
and the claim follows from the LSQ property (Definition 2.1).
A.1.2 INSTANCES OF THE BITSUM PROTOCOL
Fix (i.j) E [2] x [Q). Let - Jij and Byj = (w) The shuffled DP protocol in Algorithm executes an independent instance of the given shuffled DP bitsum protocol to estimate Big. and this estimate denoted by B.j in the analyzer in Algorithm I. We will denote this instance of II by I1gj. Recall that II is an unbiased bitsum protocol and has RMSE En. Since Bıj itself is a random variable determined by the sampling of (fr.ge) ~ Q and on the local randomized rounding by the users, conditioning these, we have
7(0)
En., [B, Bi₃ g.). Biyl and
Em, BB,
Biy (f..9:)) Byy = E
The analyzer computes and publishes Fry (2Biz. n. Considering this as estimate of Fij, we denote
Fng = Fij F.g.
15

---

Published as a conference paper at ICLR 2025
Claim A.3. [Ei (fr. Big independent random variables, and each satisfies
En., Eg (fi, Bayl and En., Enyl (ir B.g] (2R E
Proof. Probabilistic independence holds since we use independent randomness in the instance II; of for different pairs i.j. For the first and second moments, recall that f(() = (20))) 1)R for every user u, which implies Fij = (2B., n)R R when summing over the users. Also recall from above that Fij- (2 R.. Thus,
En., Eg (fis 9:), Bul = En,,
Fij - Fij (fr. 91). Bis)
= EEtly (2Bij - n n)R (2B.j - -n)R (fi, 9:), Bis)
2R ET,, [Bis Búj (firgi), Bes
= 0,
and
Eng |Eg1 2 (f), Big]
= EEt,y
Fij -Fis (fi, Big)
|22 -n)R - (2Brg -n)R 2
-En,
1 (fr. Bis
Bij - Bij 2
=2RR)² Bui
(firgi), Big
-2R E11)
A.1.3 BOUNDING THE SUPRMSE
To bound the SupRMSE of Algorithm 1, fix y E RR.. The KDE query part of the protocol uses the analyzer's published output to estimate KDEx (y) by + El= E Fo)ge(v). We now bound the RMSE of this estimate. Substituting Ei = Fi5 Fej. we have
E
KDEX (1)
F Figh(() (v),
nl 1=1
1 Q Σ
KDEx(v) nI
Fugg
+
Enggs()
nI
1=1
i=1 j=1
1 Q Σ
2
< 2F
KDEx(1) nī
Pog.(())
+
Σ
Engg(
(2)
nJ
1=1
1=1
We handle the two summands in turn.
16

---

Published as a conference paper at ICLR 2025
A.1.4 FIRST SUMMAND: DISCRETIZED LSQ APPROXIMATION ERROR
For every i, let P. E RR denote the vector with coordinates Piy. Recalling that F.j Eu=1 P00
we have F; Ex= J. We can thus write,
E KDEx(1) nl
(y) =E
KDEX(V)
Σ F. aily)
ml
19 (3)
1 E
1 FT (Ta(()) KDEx(v)
1
n
Denote the random variables,
Z, := KDEx(1) FT
1
T
and for every u E [n].
Zi = k(F v) ( 9))
Observe that Z, = - Ze and that the rightmost side of Equation (3) is EE Σ 2.13
Due to the probabilistic independence of samples for different values E [T], we can expand this as
E
Σ
+
[6[2]]
1=1
Σ
B|Z
Σ
||Z |B|2,11
(4)
i= t
Claim A.4. For every we have [R[Z,]| < B and B S (B + 2R
Proof. For the first bound in the claim, observe that Claim A.2 can be rewritten as |B[Z,,u]| S for every i, u. Since Z; = 1 Σ Zi.,, we get [E[2,]| s 1 Σn Z| S B.
For the second bound in the claim, recall that by Definition 2.1, for every supported function pair (f.g) in the LSQ family Q, and every x, E Rd we have that f(x) and g have coordinates in I-R, R). and have at most non-zero coordinates each. Thus, If g(y)l S R By re- calling that z(w) was generated from f((x)) by rounding its coordinates to {-R, R}. this implies in particular that " (v)) < R for every u. Moreover, since by Definition 2.1 we have |k y) - gb)] s 3, this also implies that [k v)1 R B. Therefore, unconditionally.
7x| S
17
k(Fu, v) (F( dc(u))
(Ik(z,, v)1 + (F (a(vi)
5 33+228s.
which implies in particular E[4 < 2
17

---

Published as a conference paper at ICLR 2025
We now have,
E
Σ KDEx(1)
Fugh(uly
nd.
1=1
127
1 F. gi(())
KDEx(1)
Equation (3)
n
Z
definition of Z,
1
$ 72
Σ B
ΣΣ
[B[2,]1 -B[Z,]]
Equation (4)
2m1 Pt
12 (T(B 22 + 1(T-1)83)
Claim A.4
S2
2.3
This is our bound for the first summand Equation (2).
A.1.5 SECOND SUMMAND: TOTAL BITSUM PROTOCOL. ERROR
For E [7], let Y; be the random variable
Y (y)g
Note that the second summand in Equation (2) equals (E() Y)
By Claim A.3, (Eg (fi, gi), Big k&s are independent random variables. Each Y. when conditioned on (fe,g:), (Bigheeqq is a linear combination a subset of these random variables and the subsets are disjoint for * V, hence (Y; (fi,9), (Bs))se are also independent random variables. Furthermore, for every [T] we have
Rnnyyettt [% (f4.)))) (Ba) B
Fugh(y)s | (fv.9); (Bg)selq)
9e (,),, [Ei (fi, Bil
1=1
0,
and
Eenahee [V? |
(fr.9)). [By)se]] Equ
Σ F (1.
( [E] I (fr.))), Bu]
==1
Σ (((
1=1
18

---

Published as a conference paper at ICLR 2025
Eiyl 2 I (fr, 9:), = (2R En) from Claim A.3. Since by Definition 2.1 ge(y) has at most non-zero entries and each bounded in absolute value by R
having used Em,, [Ey (fi, (.), = and Bn,,
E Auggsae [X/] (fi,gt), (Bishesa S 4SR* En.
Therefore.
ΣΣ Yi (Vi,gi), Byleemeee
Σ E Emshea [V?
(Bybeal
T 4SR* Eh-
Now we can bound the second summand in Equation (2)
I
E
Σ
Yi
p
11=
2
E (((i:a))):)))eeeeee
Bimabemeesa
Σr²
1 (ff.g))) Byyhennee)
n²12
8SR n²I
A.1.6 FINISHING THE PROOF OF THEOREM 3.2
Accuracy: By putting together the bounds on both summands in Equation (2), we get that the RMSE of estimating K KDEx (y) is at most
4,22 1684s
SS+
Since this holds for every y RRd
n
this is a bound on the supRMSE.
for every i [7] and j [Q], let Oij denote the output of the shuffler in protocol instance Hiy. The fact that IT is an instance of the (Eo, 5e) J-P protocol II means (by the definition of the shuffled DP model) that Oiy is (Eo, 6 w.r.t. the collection of user inputs.
Privacy:
First, fix i E [7]. Recall the sparsity property of LSQ (Definition 2.1), namely that each fę has at most non-zero entries per user. This means that if the input of one user is omitted from the dataset, the inputs of most S of the Q protocols {II, are changed. Since these protocol instances use independent randomness, then by standard ("basic") DP composition arguments (Dwork et al., 2014), the collection { is (soS, SDP. In other words, the protocol V, obtained by com- posing the protocols {1l, } is ( SD in the shuffled model (see Cheu et al. (2019) for the definition of protocol composition in the shuffled DP model).
Now, by "advanced" composition for shuffled DP protocols (Lemma 3.6 in Cheu et al. (2019)) over
the protocols ),, we get that the collection of shuffler outputs {O,, : (i. E [4] x [Q] is (e, 6)-DP, with E, 8 as stated in Theorem 3.2. Since the analyzer in Algorithm is post-processing of these shuffler outputs, the protocol Algorithm is (e, 8DD in the shuffled model.
The computational parameters of Algorithm is straightforward to calculate from those of the bitsum protocol II and the LSQ family Q: the global initialization samples I pairs (fe, 9:) from Q; each user evaluates fz( on her input z for every i; the users, the shuffler and the analyzer perform IQ instances II, thus incurring /Q times its computational and communication cost; the the final KDE evaluation part evaluates yi the query for every E [Z].
Efficiency:
A.1.7 VARIANTS OF THEOREM 3.2
The foregoing proof of Theorem 3.2 can be adapted in various ways to accommodate bitsum proto- cols with different properties than those stated in the theorem. For example,
19

---

Published as a conference paper at ICLR 2025
Algorithm 2: Shuffled DP Gaussian KDE protocol, based on either RR or 3NB bitsum protocol
Global initialization // all data here is public
Analyzer // runs after the shuffler; analyzer the same for both RR and 3NB bitsum protocols
input: integer >> O; parameters for RR bitsum: PRR (0,1); parameters for 3NB bitsum: "r,',P,H >
input: shuffled sequence messages from
for i = -..... .......I............... do
// i..d. samples using shared/public
for 1,..., do
randomness:
B₁ 5-0 0
We ((0, Ta) // d-dim normal
for message (7, 1)
I do
3 Uniform((0 2T)
L B, - B, +
publish: wi and 3g for all
for l....... do
Randomizer // each user runs this locally with
L F. + 2B, n2
private randomness
input: private data point x E RRd
publish: F; for all
for i = l...., do
KDE Query // runs on the analyzer's published output arbitrarily many times
P < cos( 2ff + 3.) ~ BBBrnoulli(( if bitsum protocol is RR then by + flip with probability pRR send (b,, i) to the shuffler
/2)
input: query point y Rd
return: DΣ F. :coss( cos(Vowu y/ B.)
if bitsum protocol is 3NB then
u11 Nogative
1/2 VegativeBinomiall (r', for j 1, I...., b; + 1/1 + the do
1/3
send (1, i) to the shuffler
for j 1, 1,... 122 + 3/3 do
send (-1, i) to the shuffler
If the accuracy guarantee of IT is given in terms of absolute error rather than RMSE (as in Cheu et al. (2019)), the proof be repeated with bounding the supremum absolute error of Algo- rithm instead of its supRMSE (this yields a very similar and somewhat simpler version of the proof given above).
If II has a pure DP guarantee, the advanced composition step in the privacy analysis from Ap- pendix 1. can be replaced by standard pure composition, resulting in s = TSeo (compare this to VISEo in Theorem 3.2) and 6 = 0. In the analogous instantiation of Theorem 3.3, the lower bound on the error changes from /log(1/0)/(e))
to 1/ 1/ven.
If IT is not unbiased, the proof (specifically Appendix 1.5.5) be slightly modified to accom- modate its bias, resulting in a corresponding term in the final supRMSE bound.
A.2 PROOF OF THEOREM 3.3
We restate Theorem 3.3 and prove corollary of Theorem 3.2. The corresponding protocol for Gaussian KDE is Algorithm with the choice of 3NB the bitsum protocol."
Theorem A.5 (Theorem 3.3, restated). There are constants C, C' > O such that the following holds. Let 8 E (0, 1) and E < (loog(18)). For every 2 C" (oo/(///)//////) there is an (s, (E.5)-DP Gaussian KDE protocol in the shuffled DP model (under the communication threat model) with users and inputs from IRd, which has: supRMSE a, user running time min(O(d/a)) Ö(d+ 1/a²)), expected communication of (1/02) bits per user, expected analyzer running time O(n/a²), KDE query time (ii(OOdd/e (d / + 1/a²)), and optimal bit-width 1.
FFor completeness, Algorithm 2 also specifies how to use RR as the hitsum protocol. The flip probability PAR should be set according Lemma 4.8 in Chen al. (2020a).
20

---

Published as a conference paper at ICLR 2025
Proof. Recall that the Gaussian kernel has LSQ family with 8 0, Q = R /2 by random Fourier features. For clarity, we mostly suppress constants in this proof. For the given E, 6, a in Theorem 3.3, we set the parameters in Theorem 3.2 as follows:
60 /Tlog(1/8) 60
2T 8' = 6/2.
Privacy: It can be easily checked that plugging the above setting of parameters into the composed privacy parameters in Theorem 3.2 yields an ODDP) guarantee in the shuffled model, provided that the given bitsum protocol II is (Eo. 60)
To this end, we the 3NB bitsum protocol from Ghazi et al. (2020b) II, since it has near- near-optimal
accuracy with low communication overhead. 3NB has four parameters r, rr, P: (see Algorithm 2) that Ghazi et al. (2020b) show how set to ensure the protocol is (co, 5g) - in the shuffled model. Namely, they prove that setting = 1/n, = e -0.99c0 r' = 3(1 + log(2e..99ea ( p' =
e (ea; -DP.
guarantees 3NB is ((60))-PP and the constants can be scaled so it
Accuracy: The 3NB protocol unbiased and has RMSE ((1/5u) = =((/oog(/5)(((e)) Plug- ging this into the supRMSE in Theorem 3.2, we get supRMSE O (Va2(1 log(1/))/(nnn) in Algorithm 2. By the bound and we can scale the constants to get supRMSE a.
in the statement of Theorem 3.3, this supRMSE is at most O(a),
Efficiency: We recall that in the 3NB protocol from Ghazi al. (2020b), each user runs in O(1) time and sends an expected nunber of + o(1) messages of 0(1) bits each, which the analyzer iterates over in time O(n). Since we have I ((1/a²) instances of this protocol, each message needs to include ([log(1/a)) additional bits to identify which protocol instance it belongs to, yielding Ologg( (a//a)/////a /a) expected bits of communication per user, and expected analyzer running time O(n/a²).
Each user also needs to compute the inner product w/ x for every i E [7]. Similarly, the KDE query algorithm needs compute wp' y for every i E [7]. This takes time (d)) per inner product, for total of (dd) = (d/a²) time. If d > 1/a², this time bound can be improved by using the faster preprocessing result of Backurs et al. (2024), who showed that one can first do a random projection of x (for each user input æ) and y (for each KDE query y) onto Ologg (1/a)/a²) dimensions, and thus only distort the final DP KDE error up to a multiplicative constant (that can again be scaled).
As shown by Backurs et al. (2024), the random projection can be done time Ö(d + 1/a²) by the fast
transform (Ailon & Chazelle, 2009), and then each of the O(1/a²)
inner products takes time Ó(1/a?), for total of Ö(d+ 1/a²)) time per user and per KDE query. 0
A.3 INNER PRODUCT LSQ
The inner product kernel k(æ, y) = of y is trivially (d, 1, LL-Saabeee for unit length embeddings, by letting the LSQ family include single pair of functions (f.g) such that both are the identity over Rdd We now observe it also (1, vd, 1)-LSQable. This allows better control over the privacy parameters and computational cost of the protocol in Theorem 3.2, since they depend on the parameters S and Q (respectively) of the (Q, R, LSQ family.
To sample a pair (f.g) Q, we sample vector (o1,...,oa) ..) E (-1, of uniformly random signs, and let both f and be the function Idd + that maps x (z.,..., x1;) to E o,n, is straightforward to check that (xf [v])] = x y for every x, y E Rd. To determine the upper bound R on the only coordinate of f(z), we observe, lf(z) = Ed o,a. & || S Vdll=l2 = Vd, since is unit length (in Fuclidean norm).
21

---

Published as a conference paper at ICLR 2025
B MORE ON SHUFFLED DP SUMMATION
B.1 BITSUM PROTOCOLS
In this section we describe some common techniques behind shuffled DP bitsum protocols, including the ones we use in our experiments (RR, 3NB and Pure).
One bitsum protocol is the classical randomized response (RR) (Warner, 1965): each user locally flips her bit 6, with some probability, and sends the resulting bit to the shuffler. The analyzer received the anonymized received bits from the shuffler, and simply releases their sum. While originally introduced for local DP, Cheu et al. (2019) showed that in the shuffled DP model, the flip probability can be significantly smaller, leading to much better accuracy.
Another popular technique for shuffled DP bitsums, which is the one underlying 3NB and Pure. is noise divisibility (Goryezka & Xiong, 2015; Balle et al., 2019b; 2020a; Ghazi et al., 2020h;a; 202 1b; Kairouz et al., 2021a). Each user i locally adds noise V4, sampled from a distribution carefully chosen so that the aggregate noise E; V2 from all users, after shuffling, is distributed in a way that ensures central DP. Thus, the shuffled DP protocol simulates central DP, by having each user contribute piece of the total "divisible" requisite noise.
To be concrete, we describe the single-distribution protocol from Ghazi et al. (2020b). In this pro- tocol, each user i samples a non-negative integer noise random variable 1/, and sends to the shuffler stream of 6; + v4 identical content-less messages (where b, is user i's private bit). The analyzer receives the unified streams of messages from all users after shuffling. Since the messages are iddn- tical and now stripped of both content and sender identities, the only information they convey is their count >, (b; + v1), which is released as the bitsum estimate. This equals the true bitsum E plus a total noise of Σ; Vi. Thus, to ensure shuffled DP, it suffices for the 148 to be such that their sum Σ, is distributed in way that ensures central DP for Σ, bj. Ghazi et al. (2020b) show this can be achieved by either a Poisson or negative binomial distribution. The 3NB and Pure bitsum protocols are more involved applications of this basic technique, designed to achieve better accuracy, lower communication cost, and (in the case of Pure) a pure DP guarantee.
B.2 BITSUMS VS. REAL SUMS
As mentioned in Section 2.4, there is also ample work on shuffled DP protocol for real number summation (abbrev. realsum), where each user holds an input number in a bounded range (say, []1, In this appendix we expand on the choice to base our approach on bitsum rather than realsum protocols. The answer has two parts: (1) why there is little potential gain in real summation, (2) why there is substantial advatnage in bit summation.
Little gain in realsums. Ostensibly, Algorithm I and Theorem 3.2 could have used realsum in- stead of bitsum protocols, obviating the need to discretizate the LSQ coordinates with randomized rounding. When summing l real numbers in [-1, 1], discretization with randomized rounding gen- erally leads Hoeffding-like error of order VE, which our protocol incurs. There are parameter regimes where shuffled DP realsum protocols are more accurate than bitsum protocols, avoiding this Hoeffding- like error, and thus may seem like an avenue improve Theorem 3.2.
However, this is in fact not the case. In our protocol, summation serves as a subroutine. The true sum not the target quantity; rather, the true sum is a random variable (sampled according to the LSQ family), which only approximates the target quantity against which error is measured (the true KDE). This LSQ approximation already incurs the Hoeffding- like error (it is "built-into" LSQ). Thus, if the discretized bitsums were to be replaced with a shuffled DP realsum protocol, the final KDE error would still be dominated by the Hoeffding-like low-order terms. Improving the final KDE error asymptotically, if this is indeed possible, would require a different approach than LSQ to private KDE, and we are currently not aware of a way to improve the KDE error in the shuffled DP model.
error, and any improvement would be restricted to
Advangate of bitsums. At the same time, discretization has its own important advantages in shuffled DP and distributed learning. This was discussed in Section 3.1. To recap, in practical applications of shuffled DP, numerical values need to be discretized, and their bit-width bounded, in order to properly control their accuracy and communication cost. This among the main motivations of
22

---

Published as a conference paper at ICLR 2025
Kairouz et al. (2021a) in developing their Distributed Discrete Gaussian (DDG) protocol for shuffled DP realsum, rather than using prior protocols for this task. The DDG facilitates bounding the bit- width (though it is not low as 1), and its emrrr analysis accounts for discretization errors. Our approach, which does not need to solve generic real summation, but only the specific case of KDE, attains the optimal bit-width of 1 by using binary discretization followed by bit summation, and our error analysis too accounts for the discretization error.
C FULL EXPERIMENTAL RESULTS
Ablation: Local DP. Figure 4 displays a comparison of our shuffled DP method with local DP. The local DP baseline is obtained by taking our private KDE protocol (Theorem 3.2), and replacing the shuffled DP bitsum with classical randomized response, which satisfies local DP. For the most direct comparison, the local DP plots are displayed compared to the RR plots (i.e., the leftmost column) in Figure 1.
We recall that the difference between the methods is that in classical local DP RR (the dashed lines in the plot) (Warner, 1965), each user locally flips her bit with probability that depends on the desired privacy parameter e, but is independent of the overall number of user in the protocol (local DP RR makes no assumptions on other participating users). In contrast, in shuffled DP RR (the solid plots) (Cheu al., 2019), each user flips her bit with probability that depends both on E and on the total number of participating user n; the larger is, the smaller the flip probability needs to be, since in shuffled DP, the user assumes her bit would also be anonymized and "hidden" among the bits received from the other n 1 users.
The results in Figure 4 show that as expected, shuffled DP attains considerably higher downstream accuracy than local DP.
Ablation: Effect of Eibl Tables 2 to show the effect of varying Fibl on various settings on the four datasets, respectively.
Additional parameter settings. Figures 5 to display private classification accuracy results for
ēTbl 10, 7, 5,3, respectively (Figure 7 repeats Figure from the main paper for convenience).
Tables to 8 present private class decoding results with ē1b1 = 5 and & R 5.7, 4.4, 3.2 respectively (Table 8 is the full version of Table from the main paper).
dbpedia 14
ag news
16
cifar 10
10
kamme shufted
privacy
kemml
Gasssian kemee shuffled privacy
Figure 4: Classification accuracy comparison with a local DP baseline (overlaid on the shuffled DP RR plots with EIb = 5, from the leftmost column in Figure 1).
23

---

Published as a conference paper at ICLR 2025
Table 2: Effect of ειи accuracy, DBPedia-14,
% Classification accuracy (dsstd) with Enar
Kernel
Bitsum
xc
2
75.5
76.1
73.6
57.1
15.2
RR
4.5
79.7+1.3
79.3
76.1
61.922.
15.
RR
79.5
79.1
77.4
63.6
17.6.0.7
Gaussian
3NB
2
79.2#1.8
79.6+1.8
79.4.0.s
65.0=1.0
15.8+10
3NB
4.5
80.3
78.4+0.9
76.9
64.721.3
15.9
3NB
7
80.0
79.1
77.520.
65.2=21
17.0.1.9
RR
2
27.0
27.31449
23.021.8
15.4216
7.821.2
RR
4.5
50.5
51.3+1.6
46.2+3.1
30.022.8
10.722.0
RR
7
65.412.11
66.7+2.0
63.0
45.2a3.3
12.0
IP
3NB
2
92.7
92.8+
92.5
91.0a0.4
58.9+1.4
3NB
4.5
93.1
93.1
93.1
92.5g0.3
72.2
3NB
7
93.1
93.1
93.1
92.6=u.2
72.9
Table 3: Effeet of eыu on accuracy, AG News.
% Classification accuracy (#std) with ens:
Kernel
Bitsum
Oc
2
60.5
60.4+2.
61.720.8
57.2224
36.3222
RR
4.5
66.8
66.7+1.7
66.8+1.4
61.822.
37.1
RR
67.710.8
67.911.6
67.941.4
62.922.7
40.7
Gaussian
3NB
2
68.2
69.5
67.0
63.422.3
11.720.9
3NB
4.5
68.741.1
69.1
68.5
63.3
41.042.6
3NB
7
67.8
68.2
68.7+1.3
62.8a1.7
40.5
RR
2
30.3
33.5
35.7
31.122.0
25.4+3.
RR
4.5
45.543.7
41.4+6.1
42.2+7.6
43.6
28.946.b
RR
7
50.5+s.7
48.8
50.944.4
41.923.9
31.523.3
IP
3NB
2
81.910.1
84.910.3
85.020.5
84.120.8
73.9
3NB
4.5
85.940.4
85.9+0.4
85. 35.62..3
85.620.2
79.5
3NB
7
86.2
86.1
85.9
85.9
79.9
24

---

Published as a conference paper at ICLR 2025
Table 4: Effect of eu on accuracy, SST2.
% Classification accuracy (dist) with Emar
Kernel
Bitsum
Oc
2
68.2
66.7
69.0
69.1
61.223.7
RR
4.5
70.0+4.0
72.8
70.3
71.4227
57.9 57.9
RR
73.1
74.3
72.9
72.1
61.9.18
Gaussian
3NB
2
72.6#1.1
71.8+4..1
71.1
70.8
64.6.2.4
3NB
4.5
71.523.7
74.1+2.0
72.2
71.5g2.
61.124.6
3NB
7
70.0
70.9
72.7+2.8
71.1
63.6a2.4
RR
2
27.0
27.314.9
23.021.8
15.4218
7.821.2
RR
4.5
50.5
51.3+1.6
46.2+3.1
30.022.8
10.7.2.0
RR
7
65.412.1
66.712.0
63.0
45.2a3.3
12.0
IP
3NB
2
92.7100.1
92.8+0.2
92.5
91.0a0.4
58.9+1.4
3NB
4.5
93.1
93.1
93.1
92.5go.3
72.2
3NB
7
93.1
93.1
93.1
92.6=u.2
72.9
Table 5: Effect of eu on accuracy, CIFAR-10
% Classification accuracy (#std) with ens:
Kernel
Bitsum
Oc
5
1.5
24.121.8
21.621.6
21.421.6
16.9a24
11.620.6
RR
3
34.8
34.0+2.4
36. 36.1
27.5 27.5
11.3+1.
RR
4.7
46.710.3
45.2+2.1
44.3
36.822.0
16.721.3
Gaussian
3NB
1.5
73.4+1.0
71.312.
72.9
67.8
39.3
3NB
3
73. 73.1
72.2+1.5
71.942.2
67.7.1.2
42.843.5
3NB
4.7
71.51177
73.3+1.6
72.8
70.4
40.8
RR
1.5
11.4216
10.7+1.4
10.6g2.1
12.0
10.3
RR
3
11.1
9.1+20
10.641.9
9.3
10.041.
RR
4.7
12.0+1.7
8.6.1.8
10.7+1.8
8,7
9.8
IP
3NB
1.5
18.8
19.610.9
17.943.8
13.8
12.3
3NB
30.444.0
28.7+2.4
26.6 36.646.1
24.4=2.
12,2+2.1
3NB
4.7
36.847.8
37.1
37.8
25.3
13.2+3.8
25

---

Published as a conference paper at ICLR 2025
DOpedia-16 14 with RR
DOoedia 14 with 3NB
DEpedia- 14 with Pure
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.0
0.0
0.0
2
10
opailon
apailon
spallon
1.0
AG news RR
1.0
news with
1.0
AC news with Pure
0.8
0.8
sccuracy
accurayy
02
0.2
0.0
0.0
0.0
epellon
epsilon
epellon
1.0
S8T2 with
1.0
SST2 with SNB
1.0
38T2 Pure
accuracy
accurscy
0.2
02
0.2
0.0
0.0
0.0
epellon
epsilon
epellon
1.0
CIFAR-10
1.0
CIFAR-10 with 3NB
1.0
CIFAR-10
accuracy
accurscy
0.2
0.2
0.2
0.0
0.0
0.0
epelion
epsilon
epellon
IP kernel, shuffled DP
IP kernel, central DP
IP kernel, no privacy
Gaussian kernel, shuffled DP
Gaussian kernel, central DP
Gaussian kernel, no privacy
Figure 5: Classification results with EIbl 10
26

---

Published as a conference paper at ICLR 2025
DOpedia-16 14 with RR
DOoedia 14 with 3NB
DEpedia 14 with Pure
1.0
1.0
1.0
0.8
0.8
0.8
ecouracy
0.6
scouracy
0.0
0.0
0.0
2
10
opailon
apailon
spallon
1.0
AG news RR
1.0
news with
1.0
AC news with Pure
0.8
0.8
sccuracy
accurayy
0.4
0.2
022
0.2
0.00
0.0
0.0
epellon
epsilon
epellon
1.0
S8T2 with
1.0
SST2 with SNB
1.0
38T2 Pure
0.8
accuracy
accurscy
0.2
02
0.2
0.0
0.0
0.0
epellon
epsilon
epellin
1.0
CIFAR-10
1.0
CIFAR-10 with 3NB
1.0
CIFAR-10
0.8
eccuracy
accurccy
0.4
0.2
0.2
0.2
0.0
0.0
0.0
epelion
epsilon
epellon
IP kernel, shuffled DP
IP kernel, central DP
IP kernel, no privacy
Gaussian kernel, shuffled DP
Gaussian kernel, central DP
Gaussian kernel, no privacy
Figure 6: Classification results with EIbl 7
27

---

Published as a conference paper at ICLR 2025
DOpecia-1e 14 with RR
DOoedia 14 with 3NB
DEpedia 14 with Pure
1.0
1.0
1.0
0.8
0.8
0.8
scouracy
0.0
0.0
0.0
2
10
opailon
apailon
spallon
1.0
news RR
1.0
news
1.0
AC news with Pure
0.8
0.8
accuracy
accurscy
0.2
022
0.2
0.0
0.0
0.0
epellon
epsilon
epellon
1.0
S8T2 with
1.0
SST2 with SNB
1.0
38T2 Pure
accuracy
accrrsy
02
0.2
0.0
0.0
0.0
epallon
epsilon
epellon
1.0
CIFAR-10
1.0
CIFAR-10 with 3NB
1.0
CIFAR-10
accuracy
accurscy
0.2
0.2
0.2
0.0
0.0
0.0
epelion
epsilon
epellon
IP kernel, shuffled DP
IP kernel, central DP
IP kernel, no privacy
Gaussian kernel, shuffled DP
Gaussian kernel, central DP
Gaussian kernel, no privacy
Figure 7: Classification results with EIbI = 5 (this is a copy of Figure/ 1 for convenience)
28

---

Published as a conference paper at ICLR 2025
DOpedia-1e 14 with RR
DBoedia 14 with 3NB
D0pedia 14 with Pure
1.0
1.0
1.0
0.8
0.8
0.8
acouracy
scouracy
0.0
0.0
0.0
2
10
opailon
apailon
spallon
1.0
AG news RR
1.0
news with
1.0
AC news with Pure
0.8
0.8
sccuray
accurscy
0.
0.2
022
0.2
0.0
0.0
0.0
epellon
epsilon
epellon
1.0
S8T2 with
1.0
SST2 with SNB
1.0
38T2 Pure
0.8
accuracy
accursyy
0.2
02
0.2
0.0
0.0
0.0
epellon
epsilon
epellin
1.0
CIFAR-10
1.0
CIFAR-10 with 3NB
1.0
CIFAR-10
0.8
80000000
accuracy
accurscy
0.4
0.2
0.2
0.2
0.0
0.0
0.0
epelion
epsilon
epellon
IP kernel, shuffled DP
IP kernel, central DP
IP kernel, no privacy
Gaussian kernel, shuffled DP
Gaussian kernel, central DP
Gaussian kernel, no privacy
Figure 8: Classification results with EIbl 3
29

---

Published as a conference paper at ICLR 2025
Table 6: Private class decoding results with 61b1 = 5 and E = 5.7
Dataset
Class
Gaussian KDE class decoding
KDE class decoding
RR
scacosp, gencorp, southcorp
xuande, xinmi, xue companys. railcopp, interactivecorr companys, companics, nokincorp
Company
3NB
europacurp, telekommmikasi, southcorp
Pure
storebrand, railcorp, onbancorp
RR
mandolinist, bosacki, cufounder author, novelist, writer raymonde, bertogliati, bonifassi
ricketson, attributor, vijayendra author, musician, bingraphically author, roberthoudin, musician
Artist
3NB
Pure
DBPodia-14
Office
RR
legi sator, politician, mulroney miniserrresident, legislator, pastpresident legislator, reclections, scnatorial
cabinetmaker, chatham, provost ministerpresident, legislator, congressperson ministerpresident govemorsgeueral, legislator
holder
3NB
Pure
proctorville, connellsville, fargomoorhead
seethihwwlhehnmsuiseeiitt nordwestmecklen-
Building
burg. brandenbughhyyeuch
3NB
galehouse, hyannisport, beaconhouse hendquarters, northcote, northvale
churchville, reisterstown, jeffersontowa holyroodhouse,, reisterstown, besconhouse
Pure
szewezenko, przodkowe, wodiczko khuzistan, wojeiechowice, szuzawrica kleveland, kurdamir, diyarhakir
manasse, jeram, esfahan
Village
3NB
khuirabad, kyrghyzsiam, kishanganj kyrghysstan, khairahad, yusefahad
Pure
RR
araucariaccac, rubiaceac, araecac celastraceae, rubiaceae, cactacene
succulents, cunoniaceac, chactophoracese chenopodiaceae. chactophoraoese, araucari-
Plant
3NB
accac
Pure
sapindaceae, violaccac, chenopodiaceae
cheaopodiaceac, loranthaccac, gesneriaceae
screenplay, movie, lilmore toyland, musketeers, imdb
dishomoringg dishunor, inglorious movie, screenplay, hiopie movie, sicario, screenplay
Film
3NB
Pure
screenplay, casablanca, filmmakers
Educational institution
RR
schoolcollege, secondarysschol, boardingschool bryancollege, beardingschool, schoolship beardingschool, publicschool, alischool
humboldduniversitt everetts, aleksandrw
SNB
schoolcollege, boardingschool, polytechnic schoolcollege, boardingschool, polytechnic
Pure
RR
ajanovic, jovanovski, miloevi
bohuslav, denverbased, petersen
Athlese
3NB
sportsperson, gillenwater, Khairuddia
sportsperson, footballer. handballer laliashvil.. jamalullsil, Footballer
Pure
alifireako, kovalenko, ilyushenko
Mean
RR
warship, troopships, airerafts fleetness, warship, shipmasters warship, hattleships, sailed
curtisswright, pilotless
of
3NB
warship. frigate, torpedobout warship, landeruiser, torpedohoat
transport
Pure
beringen, freshwater, merideth
bemardini, intermountain, varangians
Natural place
NNB
villeurbanne, riverina. curwensville
river. danube, rivermaya floodplain. river, rivermaya
Pure
fergushill, danube, waldenburg
RR
coraiidacc cacciliddac, cicadellidae
columbellidae, marginellidae, caractacus
Animal
3NB
carangidac, fasciolariidae. scolopacidae
leiothrichidae, marginellidae, phasianellddae dendrobstidae, mangaiitidae, calostomidae
Pure
coscinellidae, coraciidae, cardinalidae
RR
discography, vocals, stereophonies album, instrumentals, tracklist discography, pledgemusicc vacals
album, korn, groupie
Album
3NB
album, discography, tracklist alhum, discography. allmusic
Pure
biographics, storybook, author
booksurge, huilai, huizbou nonfiction, author, biographies nonfiction, author, bibliography
Written
NNR
hihliography, hingraphies, autohiograhhy wittgenstcin werman, fangoria
work
Pure
RR
winningest, standings, playoff buels, kurkjian, darrington gallardo, unfit, basketball
mocolm, mecartt, inconclusive playoff, championship, standings playolf. postscasion runsgriffey
Sports
SNB
AG news
Pure
RR
theha, buybacks, kulikowski retrials, clawbacks. revaluation masday, exxommobil, exxon
surcharging, nonbazardous, surcharges
Business
3NB
nasdaq, carea, divestiures masdaq, divestitures, nyse
Pure
RR
terrorist, hombings, ilghazi hostages, baghdadi, nabsa queda, imquild, antifur
ppas, atpranking, deng terorists, militants, queda queda, ceasefire, intifadas
World
3NB
Pure
ibm, loango, launchpads microsoft, viacom, proty edgeware, prokimity. shareware
ough, iebe, oul microsoft, ibm, Jucentiech ibm, infotrends, suntec
Sci/Toch
3NB
Pure
RR
overstating, drcadful, awfulness derailments, vagueness, breakage perversities, sontimcntalism, overthinking
gameplay, tactics, underplaying blandness, dramaturgy, comedy tragody. blandness, melodrama
SST2
Negative
3NB
Pure
RR
fervor, pheasmenom, pageaniry cinema, screemplays, films majestically, dramatization, shrewdness
embeddable. imbedding, embed evocative, salaciousness, theatricality memorability, evocative, masterpieces
Positive
3NB
Pure
30

---

Published as a conference paper at ICLR 2025
Table 7: Private class decoding results with 61bl 5 and e 4.4
Dataset
Class
Bitsum Gaussinn KDE class decoding
IP KDE class decoding
RR
companys, manufacturera comcorp manufactories, subsidiaries, originatons railcorp, companys. comapny
airgroup, acrosystems, bluepoint companys. railoorp, baycorp companys. companies, manufactories
Company
3NB
Pure
RR
singer, musician, halladeer, musician, artiste author, artist, composers
auditioner, surinder
Artist
3NB
author, musician, novelist author, biographically, musicion
Pure
DBPedia-14
meclelland, mclellan, dreiberg representant, representan, representantes
janetta, janette, jadakiss junetta.janette,
holder
Office
SNB
legislator, ministerpresident, congressperson politician, miniserrpesideet, liberhan
Pure
bashiruddia, ministerpeaident. lazarescu
RR
woodville, marksville, douglassville
potect, hocutt, chestnutt churchville, chapeltown, beaconbouse holyroodhouse, Tenchurch, charleswoed
Building
3NB
stationhouse, randallstown. dovercourt
Pure
beadquaterr, hyatisville, weaverville
RR
krakowiak, krzynowoga, lubliniec
kieslowski, radiolocation, blenkiron
Village
3NB
kyrghyzstan, khazsksian, diyarbukir
kylahy khairabud, khuzistan khuzestan, kyrghysstan, diyarbakir
Pure
taleyarkhan, voivodeship, mieszkowice
RR
saxifrigaccae, loranthaceae, sapotaeene
lauraceac, loganincene, annonaceae chcaopodiaceas, araucariaccae, loranthaccae cupressaceae, rubiaceae, chactophoraceue
Plant
3NB
orobanchaccac, mycenaceac, bromeliaceae
Pure
chenopodiaceae, podocarpaceae, cactacrue
biopic, imdb, sereenplay biopic, movie, silmarillion biopic, cinemax, films
dollywood, iscroku, rakotomanana
Film
3NB
movie, screenplay, biopic
Pure
movie, sicario, biopic
Educational institution
RR
ucda, madrassa, polytechnic
write, reflectometry, chathams schoolcollege, boardingschoo,, polytechnic schoolcollege, hoardingschool, publicschool
3NB
schoolcollege, polytechnic, fachhochschule eduniversal, universits, universitat
Pure
RR
borgne, romanowski, brzezinski Ialiashvili, gianluigi, pirla pejacvi, milanovic, tomashova
sobolewski, khatemi, wlosowicz
Athlete
3NR
sportsperson, handhaller, ivanovic konasheukov, laliashvili, kalynychenkoo
Pure
Mean
battlestips, navymarine, landeruiser spitlires, troopships, maersk warship, frigate, tespedo
pinezhsky, pisetsky, ilyinsky warship, landeruiser, frigatle warship. frigate. landcruiser
of
3NB
transport
Pure
RR
kranchanka, gancelm, kotomowaka danube, tributary, vilfredo soligonsk, vassilakis, nordgau
halethorpe, mupplethorpe, chloropuschia river. rivermaya, rivervale floodplain, darube, river
Natural
SNB
place
Pure
RR
coraciidae, glareolidae, phyllostomidee paludomidae, acrolepiidac. discodorididae marginellidae. riodinidac, orthogoninnee
molluse, motacillidae, molluscan leiothrichidac, marginellidae, eatostomidac mantellidae, catostomidae, coraciidac
Animal
SNB
Pure
RR
albom, vanilli, europop allmusic, remixes, remixed bousemusic, tracklist, musicology
melancholy, poctien, majra
Album
3NB
album, discography, allmusic album, discography, tracklist
Pure
booknotes, pulitzerprize, apocryphally novelistic, magazine, novelist authorites, noveletie, novelisa
temors, sarkies, dementyeva nonfiction, author, novelist
Written
NNB
work
Pure
nonfiction, bibliography, author
RR
lese, playolf, sportschameel chssporissom, hof, injuries byrd, garvin, doq
eddard. frankenfish, paconian playolT, semifinalists, championship injury, guardino, tiedown
Sports
3NB
AG news
Pure
RR
gencorp. walkout, comstock opec, sirri, toyola
citywest, opson, arkwright nasdag, stockholders, divestitures outbids, stockpiling, outselling
Business
3NB
Pure
nonactors, goldcorp, archconfraternity
collusion, dahle, kejie
yawner, oswalt, russ
World
3NB
sslamiah, taliban, hurghada bomb, nomination, warmongering
hamas, queda, talihan haghdadi, occupiers, militants
Pure
RR
haidu, microsofl, lencent ibm, httpawwddinleechnyslrooo computer- ware
multicamera, intercambio, videoconfereeccss micmsoft, ihm, lucenttech
Sci/Tech
3NB
Pure
infotrends, infogear
redesigns, ibm, lucenttech
portnyyal, dreariness, bleakness murkiness, unexciting, vapidity dramaturgy, portrayals, dramatising
ropeated, twicetobeat, ringed
SST2
Negative
3NB
comedy, dramaturgy, dramaturgical uopleasantriss unplcasantness, deadness
Pure
RR
reworded, comedies, critiques
rastignac, ruderman, gritshuuk masterpieces, salaciousness, evocative vividness, evocative, presence
Positive
3NB
memorabllity, rausing, miserables intiative, artistical, sereenplays
Pure
31

---

Published as a conference paper at ICLR 2025
Table 8: Private class decoding results with EIbl = and E Ro 3.2 (full version of Table 1)
Dataset
Class
Bitsum Gaussian KDE class decoding
IP KDE class decoding
vendors, gencorp, servicers molycorp, newscorp. mediacorp
firesign, wnews, companys. alicerp, interactivecoep alibahncom, oscorp, companies
Company
3NB
Pure
ameritech, alicorp. newseorp
RR
author, aristizabal, levesongower
catalani, macki, bacashibua author, musician, roberthoatin musician, artist, jacquesfranoi
Artist
3NB
artist lyricists, musician author, originator, mikhaylovsky
Pure
DBPodia-14
RR
louislegrand, legislator, lawmaker
sulphide, exclude, sulked ministerpresiennt legislator, congressperson ministerpresident politician, polian
Office
3NB
patiashvili, kumaritashvll, bingraphers
holder
Pure
polinard, bobrzaski, politicion
RR
reisterstown, henenson, hellertown
opened, mastered, poegaslavonia beaconhouse, manorville, reisterstown hyattsville, roxboro. reisterstowa
Building
3NB
frenchtown, brookeville, kenansville
Pure
buningtonwhiitlley wrightstown, randallstown
lalganj, baltampur, manikganj
baluchestam, jugiellonia, nidierdlaee
Village
3NB
pazarizhik, trintzuntzan, khuzzistan
kyrghysstan, kalinske, kalinski
Pure
poniewozik, mieszkowice, czerniewice
kazemabad, diyarbukkr, khonamabud
RR
chaetophoracene, gentianaceae, ritaceae
chilensis, surinamensis, tampines chenopodiaceae, armucarincene, loranthncene chactophoraceae. obenopodiacsse. araucari- aceae
Plant
BNB
cupressaceae, chactophoracene, podocarpacene aselopiadaceae, cupressaccac, gentianaceac
Pure
RR
biopic, movic, sereenplay
kaptai, kakhi, kaloi movie, lilmography, screenplay movie, film, filmmakers
Film
3NB
filmography, vanya, ghostbusters filme, movie, videodrome
Pure
RR
schoolcollege, boardingschool, allschool
eastern, marykane, kbe schoolcollege, boardingschool, polytechnic schoolcollege, publicschool, boardingschool
Educational institution
3NB bourdingschool, schoolcollege, publicschool
Pure
schoolcollege, polytechnic, quchool
RR
kovaleski, kacssmano, miroshnichenko fahianski, tamowski, hocherski rightfieldrr leftfielder, konashenkov
torstensson, torstenson, torlakson
Athlete
3NR
sportsperoon, laliashvili, konashenkov lukasicwicz, sportsperson, marcinkiewicz
Pure
Mean
warship, Inigute, steamships landeruiser, warship, landships battlecruiser, warship. hmso
latrodectus, lasx, herx
of
3NB
warship, frigate, landcruiser warship. landeruiser, connaught
transport
Pure
Natural place
RR
3NB
langenlonsheim, nardwestteckklenuurg schwe- infurt
tributary, riverina, river
himota, miercoles, mieniras rivermaya, river, danuhe
Pure
riverbeds, azkoitia, zaporozhian
lakernotes, river, riverina
carangidac, eneciliidac, arctiidac
taricani, tardio, kambona marginellidee, limonisdac, catostemidac caeciliduee heliozelidue, lasiocampidae
Animal
3NB
leiothrichidae, colooptera, acrolepiidee coracidaae, poeciliddae, acrolepiidae
Pure
RR
discography, sevenfold, album
readster. approximant, pantocrator album, discographyy alliusic album, decemberists,, song
Album
3NB
discography, album, allmusic discography, album, allmusic
Pure
Written
RR
nonfiction, encyclopodin, nonfictional author, magazine, novelist reganbooks, novelettes, fourbook
sociolinguist, besc, sociolegal
3NB
nonfiction, author, biographies synopsis, nonfiction, biographies
work
Pure
vizner, nunnerups, dietrichson injury, semifinalits, finalists pensford, rematches, undefeated
ongeri, grandi, zarale semifinalists, championship. standings chauci, teammares, nith
S pports
NNB
AG
Pure
RR
repurchass,, downtrend, equitywatch eurononline, investcorp, comcorp
sneed, timesnews, anxiousness stockholders, nasdaq, marketwatcheom merger, divestiture, stockholders
Business
3NB
Pure
corporations, comsoldations, consolidated
RR
iragi, hamas, darfur hezbollah, hamas, iraqstid
tym, asg, Iyo
World
NNB
hamas, terrorists, baghdadi shankir, burriculing, samarians
Pure
kulayev, queda, yanukovych
RR
snopes, cyberworks, hacktivists
meanings, collegefioottllnewssoo, multipolar- ity
Sci/Toch
3NB
ibm, thermedics, flextech feedbackss, company wide, eurogroup
microsoft, ibm, accenture movedtech, techcrunch, swindlers
Pure
RR
beguile, inception, shallow melodrama, rawness, blandness chumminess, meaningfulness, mootness
manipulating, uncouple, dissects comedy, tastelessness, uncasiness absurdities, chastisement, absurdity
SST2
Negative
3NB
Pure
kindliness, pleasantness, entertaining salacious, movie, majestic spiritedness, spirited, perspicacious
enjoyments, academie, anusements salacionsness, theatricality, memorahility exorcisms, fairytales, revisiting
Positive
3NB
Pure
32


Reviews:
[{"review_id": "vEQgpp3Jmb", "reviewer": "Reviewer_A2xf", "summary": "This paper studies kernel density estimation (KDE) under shuffle DP, which is suitable for the setting where users do not persistently participate in training. The authors prove convergence for Gaussian kernel and test their algorithm on various datasets.", "questions": "How can the algorithm adapt to new users joining in and we need to update the kernel density?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Kernel density estimation is an important machine learning problem, and shuffle DP is an important intermediate privacy model between local and central DP.\n2. The authors conducted extensive experiments on various datasets.", "weaknesses": "1. The algorithm proposed in this work mainly seems like an application of bitsum algorithm. The authors should highlight the novelty in either the algorithm design or theoretical analysis. For example, what is the main difficulty in applying to kernel density estimation\n2. The algorithm does not demonstrate a consistent good performance. The performance is bad for inner product kernel and shuffle-DP algorithms other than 3NB (Bhadi et.al. 2020).\n3. 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.\n\n======= Update =======\nIncreased my score to 6 after the author's response.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fc08DBEpQr", "reviewer": "Reviewer_133G", "summary": "This paper proposes a new method to perform kernel density estimation (KDE) under Shuffle model of differential privacy (Shuffle-DP).\n\nThe KDE problem is as follows: Given datapoints $X = (x_1, \\ldots, x_n)$ and a query point $y$ (all points in $\\mathbb{R}^d$), the goal is to compute $\\mathrm{KDE}\\_X(y) := \\frac1n \\sum\\_{i=1}^n \\mathbf{k}(x\\_i, y)$ for a given kernel $\\mathbf{k}$.\n\nThe Shuffle-DP is the setting where messages from the users are sent to a shuffler that randomly permutes all received messages before sending it to the analyst, and it is required that the multi-set of messages received by the analyst satisfies differential privacy.\nVarious Shuffle-DP mechanisms are known in literature for computing \"Bit-sums\", wherein, each user holds a single bit $x_i \\in \\{0, 1\\}$ and the goal is to estimate their sum $\\sum_i x_i$.\n\nThe main technique in this paper is to reduce the problem of KDE to Bit-sums, for kernels $\\mathbf{k}$ that admit \"(approximate) locality sensitive quantization (LSQ)\". This means that there is a distribution $\\mathcal{Q}$ over pairs of functions $(f, g)$ each mapping $\\mathbb{R}^d \\to [-R, R]^Q$ such that $\\mathbb{E}_{(f, g) \\sim \\mathcal{Q}} [f(x)^T g(y)]$ is equal to (or closely approximates) $\\mathbf{k}(x, y)$ for all $x, y \\in \\mathbb{R}^d$.\n\nThus, given access to $f_i(x_j)$ for $i \\in \\{1, \\ldots, I\\}$ and all $x_j \\in X$, one can approximate $\\mathbf{k}(x, y)$ as $\\frac1I \\sum\\_{i=1}^I \\sum\\_{x \\in X} f\\_i(x)^T g\\_i(y)$.\n\nFinally, the $f_i(x_j)$ themselves are estimated by reducing to \"Bit-sums\" through randomized rounding.\n\nFinally it is standard to use KDE for solving classification tasks, by performing a KDE on examples of each class, and on given query point $y$, return the class with the largest kernel density estimate.\n\nThe paper provides bounds on the communication cost and root-mean-squared-error (worst case over all query points $y$).\n\nThe paper also provides experimental evaluation on three textual datasets (two on topic classification, one on sentiment classification) and an image classification dataset (CIFAR-10), and evaluates the performance of two kernels (Gaussian kernel and Inner Product kernel) in three regimes: (i) without privacy, (ii) central DP and (iii) shuffled DP.", "questions": "I would imagine that the theoretical bounds on the $\\mathrm{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 ?\n\nFor example, 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, whereas the former has a large variance, even if it is $1$ dimensional. But I don't see the bounds in Theorem 3.2 accounting for the variance in the LSQ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a novel application of Bit-sums in Shuffle-DP to the problem of Kernel Density Estimation. The idea is simple and easy to implement. The paper has rigorous theoretical bounds on the error.\n\nOverall the paper is well written and easy to read.", "weaknesses": "This is not particularly a \"weakness\", but the approach in the paper is limited to kernels that admit good locality sensitive quantization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IlnFso2kHL", "reviewer": "Reviewer_3tVM", "summary": "The paper focuses on learning a kernel density estimator (KDE) under shuffled differential privacy (SDP), while the learned KDEs are used for a downstream classification task. The proposed method first estimates noisy class counts under local DP, and then learns KDE for each class using the noisy counts (and the corresponding class assignments) for calibrating SDP noise level. The method for estimating KDE is based on the notion of locality-sensitive quantization (LSQ), which also allows the authors to prove general as well as more specific utility bounds (e.g. for Gaussian kernel with random Fourier features). The authors experimentally demonstrate their proposed method on several data sets using various existing SDP summation protocols together with Gaussian and inner product kernels.", "questions": "## Update after the discussion:\n\nThe authors have mostly responded well to all my expressed concerns; I still have some minor disagreements, e.g., over the class decoding, but these are minor points and should not prevent accepting the paper. I have increased my score accordingly.\n\n## Original questions:\n\nIn decreasing order of importance:\n\n1) On the distinction between classification and class decoding, e.g. lines 315-27, 526-29: I am not sure how meaningful this difference actually is; I would expect that to be able to classify examples well, the KDE $\\tilde K_c$ for any given class $c \\in [m]$  should give higher scores than any other KDE for that class. This seems pretty much the same things as any given KDE $\\tilde K_c$ being able to give high scores for inputs from the matching class $c$ and lower scores to inputs from any other class. Whether or not this matches what humans would consider to be semantically relevant for the classes seems like quite a fuzzy claim.\n\n2) 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.\n\n3) How much utility do the noisy counts via LDP cost? Please add an ablation study (at least for some experimental setting) using the actual true counts and comparing to the proposed full method with LDP counts (using same noise levels for the shuffle protocol).\n\n4) Thms 3.2, 3.3: please clarify in what sense the bit-width 1 is optimal (e.g. communication, utility, both)?\n\n5) Lines 312-14: there are some proposed DP-kNN methods, so this claim does not seem to be true (although I haven not read the said papers in detail).\n\n6) Please add an additional step after line 913 to be clearer on the proof.\n\n## Minor typos, comments etc. \n\nI do not expect any acknowledgement or comment on these, just fix when appropriate:\n* typos: lines 109-110, 775-76, 1063-64, 1139-40, 1160-61\n* Why suppress eq numbers? Would be more straightforward to ref these using numbers instead of lines.\n* To make the result figures more readily interpretable, it would be good to add some more basic info to the captions (e.g. $\\delta$, how many repeats).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "i) The proposed method seems to be interesting and novel in the SDP setting.\n\nii) The paper is mostly well-written and nice to read, with no obvious major oversights.\n\niii) The code is included with the submission (at least partly; e.g., as there is no requirements.txt or equivalent, getting the code to run would take some amount of effort).", "weaknesses": "i) While the stated goal is to do learning in a \"single-shot\" manner, i.e., without clients participating (iteratively) in training beyond just choosing to send their data, the proposed approach still involves 2 communication rounds (getting noisy counts for the classes, then running the KDE protocol with noisy class sizes) and a non-trivial amount of compute spend on client-side (run some pretrained model as feature-extractor, run Alg.1 with given hypers).\n\nii) See comments below for some additional specific concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TtOEj81tQ4", "reviewer": "Reviewer_Nw6K", "summary": "This paper studies private kernel density estimation and the privacy at the user end is considered. The methodology is with the protocol of the shuffled-DP: each user first randomize her own data and then a shuffler will collect the randomized messages from all users and shuffle them in a random order. The basic module is the bitsum in the shuffled DP where each user has one bit and the set of bit after shuffling keeps well the sum of all bits. The main algorithm is designed to call this module towards the private kernel estimation. The paper provides the theoretical guarantee for the algorithm. In the experiment, the proposed algorithm under shuffled-DP is compared with the algorithm at central-DP in two downstream tasks classification and class decoding.", "questions": "Please see the weaknesses section. Moreover, I have some questions of some mentioned concepts:\n1. Bit-width is introduced in line 239-240. What is the exact definition of it? In the theorem, \"the protocol has optimal bit-width 1\" is stated; what does this mean?\n2. $S$ is introduced in Definition 2 as a property to describe the kernel. It does not appear in the algorithm's description but seems to be an important factor for the theoretical guarantees, which occurs in both DP's guarantee and the utility upper bound. Could you explain what role $S$ plays to bring these effects on the theoretical results?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The flow of the writing and the clarity are great. The background such as the framework of shuffled DP is mostly well-introduced; I do have questions for some concepts (see the question section), but they are not influencing my overall understanding for the method.\n2. The analysis of proposed algorithm seems solid as presented in theorem 3.2 and theorem 3.3.\n3. The empirical evaluation is systematic. It is located to two downstream tasks of the private kernel estimation.", "weaknesses": "As this paper is the first paper (to my best knowledge) to study private kernel estimation with the shuffled DP protocol, I think more comparison with other settings can enhance the understanding what role shuffled DP plays. In details:\n1. 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?\n2. Another popular framework is to leverage secure multiparty computation (MPC) to compute sums of values from each user [1]. What is the advantage and limitations between these two framework in terms of utility and communication cost?\n\n[1] Bonawitz, Keith, et al. \"Practical secure aggregation for privacy-preserving machine learning.\" proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)