Personalized Privacy Amplification via Importance Sampling
Authors: Dominik Fay
Sebastian Mair
Jens Sjölund
Venue: Accepted by TMLR ()

Abstract: For scalable machine learning on large data sets, subsampling a representative subset is a common approach for efficient model training.
This is often achieved through importance sampling, whereby informative data points are sampled more frequently.
In this paper, we examine the privacy properties of importance sampling, focusing on an individualized privacy analysis.
We find that, in importance sampling, privacy is well aligned with utility but at odds with sample size.
Based on this insight, we propose two approaches for constructing sampling distributions: one that optimizes the privacy-efficiency trade-off; and one based on a utility guarantee in the form of coresets.
We evaluate both approaches empirically in terms of privacy, efficiency, and accuracy on the differentially private $k$-means problem.
We observe that both approaches yield similar outcomes and consistently outperform uniform sampling across a wide range of data sets.
Our code is available on GitHub.

Published in Transactions on Machine Learning Research (12/2024)
Personalized Privacy Amplification via Importance Sampling
Dominik Fay
domminakk@kthh..e
Elekta and KTH Royal Institute of Technology, Stockholm, Sweden
Sebastian Mair
sebastian. mair@lairlle..
Linköping University and Uppsala University, Sweden
Jens Sjölund
jens.sjolunddHL wu.se
Uppsala University, Sweden
Reviewed on OpenReview: https: // openrevieww net/ forun? id= Ix2cR89245
Abstract
For scalable machine learning large data sets, subsampling represcntative subset is common approach for efficient model training. This is often achieved through importance sampling, whereby informative data points are sampled more frequently. In this paper, we examine the privacy properties of importance sampling, focusing on an individualized privacy analysis. We find that, in importance sampling, privacy is well aligned with utility but at odds with sample size. Based on this insight, we propose two approaches for ructingg sampling distributions: one that optimizes the privacy-cfficiency trade-off; and one based on utility guarantee in the form of coresets. We evaluate both approaches empirically in terms of privacy, efficiency, and accuracy the differentially private k-means problem. We observe that both approaches yield similar outcomes and consistently outperform uniform sampling across a wide range of data sets. Our code is available on GitHub
1 Introduction
When deploying machine learning models in practice, two central challenges are scalability, i.e., the compulationally efficient. handling of large data sets, and the protection of user privacy. common approach to the former challenge is subsampling, i.e., performing demanding computations only on a subset of the data, see, e.g., Alain al.] (2016); Katharopoulos tool that can reduce the variance of the subsampled estimator. It assigns higher sampling probabilities data points that more informative for the task at hand while keeping the estimate unbiased. For instance, importance sampling is commonly used to construct coresets, that is, subsets whose loss function value is provably close to the loss for the full data set, see, e.g., [achem el al. (2018). For the latter challenge, differential privacy (Dwork et al.) 2006bb offers a framework for publishing trained models in a way that respects the individual privacy of every user.
Fleuret (2018). Here, importance sampling a powerful
Differential privacy and subsampling are related via the concept of privacy amplisication by subsampling Kasiviswanathan al.) 2008 Balle al.) 2018), which states, loosely speaking, that subsampling with probability improves the privacy parameter of subsequently factor of approximately p. A typical application of this result involves re-scaling the query by factor of 1/p to eliminate the sampling bias, thereby approximately canceling out the privacy gains, but keeping the efficiency gain. It forms the foundation for many practical applications of differential privacy, such as differentially private stochastic gradient descent (Bassily et al. 2014 Abadi et al. 2016).
differentially private algorithm by
So far, privacy amplification has been predominantly used with uniform sampling (Steinke 2022 Although the potential of data-dependent sampling for reducing sampling variance is well understood (e.g., Robert
cerrrrannneeaaannngg sampling

---

Published in Transactions on Machine Learning Research (12/2024)
Privacy-optimal
Coreset-based
Uniform
4000
3000
Individual privacy lass
2000
PC
1000
1000
2000
-2000
2000
4000
-2000
2000
4000
-2000 D
2000
4000
PC
Figure 1: Illustration of three subsampling strategies for the learning task of k-means clustering on the Song data set. We show a scatter plot of the first two principal components the sampled points. The marker size is proportional to the importance weight, while the color represents the individual privacy loss before sampling. Left: Our privacy-constrannot sampling selects data points with higher individual privacy loss more frequently and with lower weight. Middle: Coreset-based sampling selects data points based on their potential impact. the objective function. Right: Uniform sampling selects data points with equal probability.
& Casella (2055) ) it has largely remained untapped in differential privacy because its privacy benefits have not been as clear (Bun et al.) 2022 Drechsler & Bailie, 2024). A longstanding objection to data-dependent sampling is that the privacy amplification factor scales with the maximum sampling probability when applied to heterogeneous probabilities, leading to worse privacy than uniform sampling when controlling for sample size. Recently, Bun et al. (0022) confirmed that this also holds for cegabiliyyproportionnn
sampling sampling strategy closcly related to importance sampling and further noted that additional privacy leakage may arise from data points inftuencing other data points' sampling probabilities.
We find that these challenges can be addressed with an appropriate sampling schome and an individualized privacy analysis incorporating more information than previous work. We propose Poisson importance sampling, defined as sampling each data point independently with probability that depends only on the data point itself and weighting the point by the reciprocal of the probability. In this setting, we conduct privacy analysis that explicitly considers the individual privacy loss of each data point when sampled with specific weight and probability. Our analysis reveals that, in importance sampling, privacy is typically not at odds with utility but with sample size. This is for two reasons: (i) the most informative points typically have the highost privacy loss, and (ii) when importance weights are accounted for, decreasing the sampling probability typically increases the privacy loss. Perhaps counterintuitively, we conclude that we should assign high sampling probabilities data points with high privacy loss to have good privacy and good utility.
At first, statement (ii) might seem to suggest that we should reject weighted sampling altogether because there is no privacy gain. However, this is misleading because the statement applies even more to the widely used uniform sampling when weights are accounted for. Indeed, we find that importance sampling is superior to uniform sampling in terms of mitigating the impact on privacy and utility. By including sampling weights into the framework of privacy amplification, we make this effect explicit and highlight that the primary purpose of subsampling (whether uniform or data-dependent) to improve the efficiency of the mechanism, not its privacy-utility trade-off.
Based on this insight, we derive two specific approaches for constructing importance sampling distributions for given mechanism.
Our first approach navigates the aforementioned adverse relationship between privacy and sample size by minimizing the expected sample size subject a worst-case privacy constraint. This approach effectively equalizes the individual privacy losses of the mechanism. We call this approach privacy- constrained sampling. It applies to any differentially private mechanism whose individual privacy
2

---

Published in Transactions on Machine Learning Research (12/2024)
loss profile is known. We provide an efficient algorithm that optimizes the sampling probabilities numerically.
Our second approach is based on the concept of corescts, which are small, representative subsets that come with strong utility guaranlees in the form of a confidence interval around the loss function value of the full data set. We derive the privacy properties of a coresct-based sampling distribution when used in conjunction with differentially private k-means clustering.
The two approaches are visualized in Figure | alongside uniform sampling. The figure shows that the privacy-constranne weights are highly correlated to the utility-based coreset weights, supporting the intuition that privacy and utility are well aligned in importance sampling.
We empirically evaluate the proposed approaches on the task of differentially private k-means clustering. We compare them to uniform sampling in terms of efficiency, privacy, and accuracy on eight different data sets of varying sizes (cf. Table [ We find that both of our approaches consistently provide better utility for a given sample size and privacy budget than uniform sampling on all data sets. We find meaningful privacy-utility improvements even in the medium-to-low privacy regime where uniform sampling typically fails to do so. One practical implication is that importance sampling can be used effectively to subsample the data set once at the beginning of the computation, while uniform subsampling typically requires repeated subsampling at each iteration.
2 Preliminaries
We begin by stating the necessary concepts that also introduce the notation used in this paper. We denote by X' C Rd the set of all possible data points. A data set D E X is a finite subset of X. We use (r) = fx E Rd ||* I r} to refer to the f--norm ball of radius r in d dimensions. When the dimension is clear from context, we omit the subscript d and write By(r).
Differential Privacy. Differential privacy (DP) is a formal notion of privacy stating that the output of a data processing method should be robust, in a probabilistic sense, to changes the data set that affect individual data points. It was introduced by Dwork et al. (2006b) and has since become standard tool for privacy-preserving data analysis (Ji ct al., 2014). The notion of robustness is qualified by parameter 2 0 that relates to the error rale of any adversary that tries to infer whether particular data point is present in the data set (Kairouz et al. 2015 Dong et al. 2019). Differential privacy is based on the formal notion of indistinguussaaiiitty
Definition (<inndisinggishaalltt)). Let c < 0. Two distributions P,Q on a space y are e-indistinguishable if P(Y) S QYY and Q(Y) S P(Y) for all measurable Y y.
Definition 2 (e-DP). A randomized mechanism M: X* y is said to be e-differentially private (e-DP) if, for all neighboring data sets D,D' D' E X", the distributions of MMD) and M(D') are cindistinguishable. Two data sets D, D' are neighboring if DD = D' [x} or D' = -D (x) for some x X
Formally, we consider a randomized mechanism as a mapping from a data set to a random variable. Differential privacy satisfics several convenient analytical properties, including closedness under post-processing (Dwork
2006b), composition (Dwork et al. 2006b 2010 Kairouz et al. 2015), and sampling (Kasiviswanathan et al.
et al.
2008 Balle et al. 2018). The latter is called privacy amplification by subsampling.
Proposition 3 (Privacy Amplification by Subsampling). Let D be a data set of size n, S be a subset of D where every x has a constant probability p of being independently sampled, i.e., g(x) = p E (0, 1), and M be an e-DP mechanism. Then, M(S) satisfies e'DP for e' = log(1 + (exp(e)
In the case of heterogencous sampling probabilities Pi....,Pa. the privacy amplification scales with max; instead of p. It is important to note that this only provides meaningful privacy amplification if e is sufficiently small. For 6 > 1, we only have e' ~ e- log(1/p)
Personalized Differential Privacy. In many applications, the privacy loss of a mechanism not uniform across the data set. This heterogeneity can be captured by the notion of personalized differential privacy (PDP) (Jorgensen et al. 2015: Ebadi et al. 2015 Alaggan et al. 2016)
3

---

Published in Transactions on Machine Learning Research (12/2024)
Definition 4 (Personalized differential privacy). Let e: X - Rzo. A mechanism M: x - y' is said to satisfy e-personalized differential privacy (t-PPP) it, for all data sets D and differing points x E X, the distributions of M(D) and M(DU(x}) are e(x) (ix---iddiiinnuuihaable We call the function e(-) a PDP profile of M.
Importance Sampling. In learning problems, the (weighted) objective function that we optimize is often a sum over per-point losses, i.e., ΦD = ExeD w(x)((x). Here, we lypically have w(x) = 1 Vx E D for the full data D. Uniformly subsampling a data set yields an unbiased estimation of the mean. A common way to improve upon uniform sampling to skew the sampling towards important data points while retaining an unbiased estimate of the objective function. Let q be an importance sampling distribution on D which we use to sample a subset 8 of m < n points and weight them with w(x) (mq(x))- Then, the estimation of the objective function is unbiased, i.e., Eslos] ØD.
3 Privacy Amplification via Importance Sampling
This section presents our framework for importance sampling with differential privacy. In Section 3.1 we introduce the notion of Poisson importance sampling and state and discuss its general privacy properties. Sec- tion 3.2) presents our first approach for deriving importance sampling distributions, namely privacy- conayyy-onstrainedd sampling. Finally, in Scction 3.3 we give a numorical example that illustrates the aforementioned results and compares them to uniform subsampling for the Laplace mechanism. We defer all proofs to Appendix
3.1 General Sampling Distributions
We begin by roduciigg Poisson importance sampling, which is the sampling stralegy we use throughout the paper. It is a weighted version of the Poisson sampling strategy described in Proposition 3
Definition 5 (Poisson Importance Sampling). Let q: X' + [0, 1] be a function, and D = (x,,..., x,,, S X be a data set. A Poisson importance sampler for is a randomized mechanism S, = {(w,, x,) | 1/s = 1}, where w; = 1/q((x) are weights and M1.... "h are independent Bernoulli variables with parameters pt = (x)))
By having each probability (xx)) depend only on the data point x, itself and keeping the selection events independent, we ensure that the influence of any single data point on the sample small. It is important to note that the function definition of g must be dala-independent and considered public information, s.e., fixed before observing the data set, while the specific probabilities {9(x,))²= evaluated Note also that Poisson importance sampling outputs a weighted data set. We intend for the subsequent mechanism to use these weights to offset the sampling bias, e.g., by using a weighted sum when the goal is to estimate a population sum. However, note that our formal privacy results also apply to biased mechanisms.
the data set are not published.
In order to characterize the privacy properties of Poisson importance sampling, we analyze the impact of the sampling probability jointly with the data point's individual privacy loss in the base mechanism. For this reason, we express our results within PDP, which is in contrast to previous characterizations of data-dependent sampling (e.g., Bun et al. (2022)) Our first result describes the general case of an arbitrary PDP mechanism subsampled with an arbitrary importance sampling distribution.
Theorem 6 (Amplification by Importance Sampling). Let M: [1, [1, x X - y be an e-PDP mechanásm that operates on weighted data sets, q: X' + [0.1] be a function, and S.(.) be Poisson importance sampler for q. The mechanism M M o Sy satisfies PDP with
(xx) -log + ((x)(((( ((xx)(<(xx))1)).
-1)). where w
1 (xx)
(1)
The sampled PDP profile in Equation 1 closely resembles the privacy amplification result for uniform sampling (Proposition 3) with the important distinction that e(w, x) depends on a weight w and a data point x. This relatively small change has important implications for the trade-offs between privacy, efficiency, and accuracy. In general, it is no longer obvious whether the privacy loss increases or docreases as a function of the sampling probability. However, we show in Appendix A that, for an important class of PDP profiles, the sampled PDP profile decreasing in (x). This class is important because it includes PDP profiles that.
4

---

Published in Transactions on Machine Learning Research (12/2024)
are linear in W. In the context of importance sampling, we argue that all mechanisms of interest linear in w, because linearity follows from simple invariance condition: we should expect mechanism to treat a weighted data point (w,x, x) the same as if it were w distinct data points of value x, each with weight 1. For (generalized) linear queries, this invariance coincides with unbiasodness and thus agrecs with the intuitive purpose of an importance weight. this invariance holds, the PDP profile linear w due to group privacy.
From the above discussion, we conclude that a good sampling distribution should assign high probabilitiee to informative data points in order to achieve good privacy and utility. Hence, the privacy-utilit--effiinn trilemma reduces to dilemmaa between efficiency the one hand; and privacy and utility the other. This suggests two natural approaches to constructing sampling distributions: one that optimizes the privacy-effiiency trade-off and one that optimizes the utility-efficiency trade-ofT. We explore the first. approach in Section 3.2 and the second approach in Section
3.2 Sampling with optimal privacy-efficiency trade-off
We now describe how to construct sampling distribution that achieves given e-DP guarantee with minimal expected sample size. The motivation for this is twofold. First, as we have seen in the previous subsection, sample size is the primary limiting factor to privacy in importance sampling and additionally serves as the primary indicator of efficiency. Secondly, by imposing a constant PDP bound as constraint we can ensure that the subsampled mechanism satisfies e-DP by design. This is not obvious from Theorem as the resulting PDP profile may be unbounded.
Minimizing the expected sample size subject to a given eDD constraint can be described as the following optimization problem.
Problem 7 (Privacy-consee constriconst sampling). For a PDP profile c: (1, x X + R20, target privacy guaran- lee e*, and a dala set D C X of size n, we define the oplimizalion problem for privacg--constrinee sampling as
minimize Wi
Σ
(2a)
(oluxxx))))
subject to log 1 wi
Sc
for all i,
(2b)
wi 1,
for all i.
(2c)
The constraint in Equation 2bb captures the requirement that 1a should be bounded by e* for all X, and the constraint in Equation (2c) ensures that 1/w; is probability. When the PDP profile is linear in w, the problem can be solved with standard convex optimization techniques. Below, we provide a more general result. that guarantees a unique solution and an efficient algorithm for a broad class of (possibly) nonconvex PDP profiles. In order to guarantee a unique solution, we require the following mild regularity conditions. Assumption 8. For all x E X, e² 2 x(1,x).
Assumption 9, For all x E X, there is constant ux 2 such that e(w, > log(1 + w(e -))) for all
w 2 xx
Assumption S ensures that the feasible region is non-empty, because wi w2 w. always satisfies the constraints, while Assumption g essentially states that, asymptotically, e should grow at least logarith- mically fast with to, ensuring that the feasible region is bounded. Formally, our existence result as follows.
Theorem 10.
Let Assumptions S and 9 be satisfied. There is data set- ieddidepenndnt function w: X + [1, oc), such that, for all data sets D E X", Problem 7 has a unique solution w* (D) = (wi (D),... ..... w (D)) of the form (D) = w(xx). Furthermore, let M be a mechanism that admits the PDP profile and S, be a Poisson importance sompler for q(x) = 1/w(x). Then, M o Sg satisfies DD-
The fact that the weights are of the form (D) w(x;) is important for privacy. It ensures that the probability map q(-) is only a function of x, and not of the remainder of the data set, which is a requirement for Poisson importance sampling.
5

---

Published in Transactions on Machine Learning Research (12/2024)
Note also that, with privacy-constratned sampling, can achieve some sampling "for free": if the base mechanism satisfies e-PP and we choose e" then the sampled mechanism also satisfies e-PP while operating on smaller sample.
Next, in Algorithm ! we describe an efficient algorithm to solve privacy-constraing sampling. We reduce Problem 7 to a scalar root-finding problem and solve it via bisection. Since the sampled PDP profile might have many roots, we require an additional assumption in order to identify which root optimal. We introduce As- sumption 11
which is slightly stronger than Assumption [] but still permits variety of nonconvex PDP profiles.
Assumption 11. The function e(w, x) is differentiable w.r.t. and exp e is St-only convex in w for all x.
Algorithm Optimization for privacy-constrained importance weights
1: Input: Data set D = (xi...., Xn), target privacy guarantee e* > 0, PDP profile its derivative e' with respect to w, and strong convexity constants #1.... Output: Importance weights w Wn
for =......,. do Define 9:(w) = (e -1) 11)
in < min(e=(Lxx)) + p:/2, c((1, )(te((ix + +1 b + -(2eee 0.)/us +1
if (1,, x,) = and (1, < then
8:
Wi + Bisect gi with initial bracket (1, b;]
9:
else
10:
+ Bisect gi with initial bracket [1, bj]
11: end if
12:
end for
As the following proposition shows, Algorithm solves Problem using only few evaluations of e(w, x). We note that faster solutions are possible, e.g., via Newton's 's method, but have found bisection to be sulficiently fast in our experiments (see Section 5
Proposition 12. Let Assumptions and 11 be satisfied. Algorithm 1 solves Problem 7 up to accuracy a with al most ExED log, [ee - Tx) [apx)) coaluations of e(w, x), where e'w,, x) = 0/3w e(w, x) and Ux = min + Mx/2, (((,,x)e(lxx) + +1}.
3.3 Importance sampling for the Laplace mechanism
We conclude this section with simple numerical example for Theorems 6 and 10 illustrate that (1) privacy and utility well-aligned goals in importance sampling and (ii) uniform sampling is highly suboptimal even for very fundamental mechanisms. For this purpose, generate synthetic data on which we run a Laplacian sum mechanism and compare privacy-constrained sampling to uniform sampling as well as to an idealized benchmark in terms of privacy and variance at fixed expected sample size.
Let D / be data set and I C (I. a subset indices. We consider the Laplacian weighted ((w;,;;)iee x;) is weighted subset of D and is standard Laplace distributed. The PDP profile of MIws is given by eLws(w, x) = w||x||1- When D is obtained by Poisson importance sampling S, from D, then the mechanism Miws Sp has variance
sum mechanism Miws(D) + Eiez wix, as example, where H = [(w,,
Var Miws((), = Σ
g(xx) 1) [xx1]
in the j-th dimension, where the randomness over both the noise and the sampling. We compare three sampling strategies: uniform sampling qumi((x) m/n, privacy-constrainee sampling qpriv according Theorem 10 and an idealized benchmark which we call variance-optimal sampling yar, defined the

---

Published in Transactions on Machine Learning Research (12/2024)
x
privacy-constrained
variance-optimal
uniform
300
100
250
200
w(x)
MSE
150
60
100
40
50
2
10a
|
max. PDP loss
Figure 2: Comparison of sampling strategics for the Laplace sum mechanism. Left: for each data point. Each marker in the plot represents one data point. The points are ordered by their no-oom Right: Estimation error for varying noise scales. Lower is better. The horizontal axis is the maximum PDP loss over the data set.
The importance weight
solution to the following optimization problem:
minimize
Var [LWw((Ds]] subject to Σ (xx) m.
The variance-optimal distribution serves as a lower bound on the variance achievable by any DP sampling distribution. does not satisfy e-DP itself, as it requires oracle access to the data set. As we show below, the privacy-constraineel distribution achieves performance close to variance-optimal while also satisfying e-DP.
We generate n 1000 points from an isotropic multivariate normal distribution in 10 dimensions with variance σ² 1/d in each dimension. First, visualize the importance weights wxx)) for each sampling strategy. For this, we fix target sample size at m = sampling strategy that achieve the target sample size in expectation. The results are shown in Figure 2 (left). Remarkably, the privacy-constrained weights and the variance-optimal weights are almost identical.
19 19 and compute the weights w(x,) for each
Next, we compare mean-squared error (MSE) and privacy loss of the sampling strategies at different privacy levels. For this, we vary the noise scale b of the Laplace mechanism over coarse grid in [3, 3000). For each b, we fix the expected sample size my by computing the privacy-constraanne weights. Then, we compute the corresponding weights for the other two sampling strategies such that they achieve m, in expectation. We then compute the individual PDP losses vxxx;) for each sampling strategy and obtain their respective maximum over the data set. Finally, we compute the MSE between the quantities Σx.e X; and Miwss of each sampling strategy by averaging over 1000 independent runs. The resulting PDP losses and MSEs in Figure (right) show substantial improvements of crostay- sampling over uniform sampling.
4 Importance Sampling for DP k- m-mans
In this section, we apply our results on privacy amplification for importance sampling to the diffcrentially private k-means problem. We define a weighted version of the DP-Lloyd algorithm, and analyze its PDP profile. Then, derive the required constants for the constriind distribution and establish privacy
guarantee for coresct-based sampling distribution. All proofs are deferred to Appendix D
Differentially Private k-means Clustering. Given a data set D as introduced before, the goal of k-means clustering is to find set of E N cluster centers C (c....., cx} that minimize the distance the data points to their closest cluster center. The objective function given as @D(C) = Σn ((x,CC) where d(.,)) is the distance of point x its closest cluster center Cý, which is d(x,C) miny || -c,1.. The standard approach of solving the k-means problem is Lloyd's algorithm (Loodd 1982) Tt starts by initializing the cluster
7

---

Published in Transactions on Machine Learning Research (12/2024)
centers C and then alternates between two steps. First, given the current cluster centers C, it computes the cluster assignments Cj {x: j arg minj ||x; ) for every j = ......k k. Second, it updates all cluster centers to be the mcan of their cluster C; = |2, Exec, x. Those two steps iterated until convergence.
The standard way to make Lloyd's algorithm differentially private to add appropriately scaled noise to both steps of the algorithm. Gaussian noise has been suggested (Blum et al. 2005), resulting (e, 0)-DP and Laplace noise has been suggested (Su et al. 2016 2017) for & geometry, resulting in c-DP. Here, we give a generalized version based on the exponential mechanism (MeSherry & Talwar 2007) that guarantees e-PP for any lo geometry. We refer to it as DP- -loydoyd. Let & E R be a random vector whose entrics independently follow a zero mean Laplace distribution with scale Beount > 0. Furthermore, let Çi...., S& E R be independent random vectors, each drawn from the density p(() & exp( (-1ssl/p// Baum). The cluster centers are then updated as follows:
-i 1c1
+ Σ
x
for j = 1.2....,
xEC;
Assuming the points have bounded f--norm, i.e.; X = (r)r) for some r > O, then DP-Lloyd preserves e-DP with c c= (r/Bsum + 1/oommt) after T itcrations.
Weighted DP Lloyd's Algorithm. In order to apply importance subsampling to k-means, first define weighted version of DP-Lloyd. Each iteration of DP-Lloyd consists of a counting query and sum query, which generalize naturally to the weighted scenario. Specifically, for a weighted data set S = {(w;, x;) we define the update step to be
C Ej + E(mx)ec w
G
Σ wx
for j = 1,2,...,k
(W)x)C,,
We summarize this in Algorithm 2 which can be found in Appendix D This approach admits the following PDP profile which generalizes naturally from the e-DP guarantee of DP-Lloyd. Proposition 13. The weighted DP Lloyd algorithm (Algorithm 2
satisfies the PDP profile
(L, = 10==(22 Brount
|xx|| Baum
Tw.
(3)
Privacy-constrainned sampling. In order to compute the privacy-constrannct weights via Algorithm need the strong convexity constant of ELooyd, which is readily obtaincd via the socond derivative:
we
8² exp exp(eLLoya (w, x)) 2 T
|x||e
((
|x|1p] )
exp
(oomne
p.
(4)
Le
Beount
Baum
3rum
Besides the privacy- constrained distribution, we also consider a coreset- coreset-based sampling distribution. Before doing so, first introduce the idea of a coreset.
Coresets for k-means. A coreset is weighted subset S C D of the full data set D with cardinality m < n, on which a model performs provably competitive when compared to the performance of the model on D. Since we are now dealing with weighted data sets, we define the weighted objective of k-means to be eD(C)= = ExeD w(x)d(xxC), where wxx) 2 are the non-negative weights. In this paper, we use a sampling distribution inspired by a lightweight. coreset construction as introduced by Bachem al.] (2018).
Definition 14 (Lightweight, coreset). Let 0, k N, and D x be set of points with mean x. A weighted set S is a (s, lightttttt coreset of the data D if for any C C Rd of cardinality at most k we have (pp(C)=s(CC) < _ (C) + ((x})
Note that the definition holds for any choice of cluster centers Bachem et al. 2018 propose the sampling d(x,x)
distribution g(x) 1/2 1 En x(x,x) and assign each sampled point the weight (mg(x))-11 This is a mixture distribution of a uniform and data-dependent part. Note that by using these weights, (s(C) yields an unbiased estimator of @C(C). The following theorem shows that this sampling distribution yields a wight coreset with high probability.
8

---

Published in Transactions on Machine Learning Research (12/2024)
Theorem 15 (Bachem et al. (2018) ). Let > 0, (0, k E N, D be set of points in X, and S be the sompled subset according to q with a sample size m of al least m 2 kddngg llogg--lo-- A where e >> 0 is a constant.
Then, with probability of at least 1 1- A, S is an k) (tlllllgghhggghttooooo..o.. coresst of D.
Corcset-based sampling distribution. We adapt the sampling distribution from Theorem 15 to the Poisson sampling setting and propose g(x) a (1 X) m where < n is the expected subsample size and & = Σm= ||x:112 is the average squared f--norm. To ensure proper probabilities, it is necessary to constrain the subsampling size to S nx Compared to [aache el. al. (2018), there are three changes: (i) the change to a Poisson sampling setting, (ii) the assumption that the data set X' is centered, and (iii) the introduction of À E [o, 1] which yields a uniform sampler for the choice of X = 1.
ax
We compute the e-DP guarantee for DP Lloyd's algorithm with coreset- based sampling as follows. We apply Theorem [0 to the PDP profile derived in Proposition 13 and the coreset- based sampling distribution. For positive constants a, b, s,t O, this yields a ei-PDP guarantee of the form
(x) = log 1+
a +||x|| 12
-1) (b+ + +
eep
-
(5)
b + s X
In order to derive an e-DP guarantee, we need to bound (x) over the domain of x E (r)... We observe that (xx) depends on x only through ||x[|2. Therefore, we can bound (x) numerically by maximizing it over the domain |x||2 E [0, via grid search. The maximum always exists because and s are strictly positive.
5 Experiments
We now evaluate our proposed sampling approaches (coreset- based and privacy-constraiieel) on the task of k-means clustering where we are interested in three objectives: privacy, efficiency, and accuracy. The point of the experiments is to investigate whether our proposed sampling strategies lead to improvements in terms of the three objectives when compared to uniform sampling. Our mcasure for efficiency is the subsample size produced by the sampling strategy. This is because Lloyd's algorithm scales linearly in (for fixed & and T) and the computing time of the sampling itself is negligible in comparison. We measure accuracy via the k-means objective evaluated on the full data set and privacy as the cDD guarantee of the sampled mechanism.
Data. We use the following eight real-world data sets: Covertype (Backkard & Dean
1999) (n = 581,012, [Chang & Lin
d d= d=54), FMA Defferrard al. 2017) (n 106,574, d = 518), Ijenn
2001 (n 49,990,
d= 22) Cattali Ioneseu 2011 Ionescu et al. 2014) (n 35,832, d 48), RNA
n 145,751, d 74), MiniBooNN NE Dua & Graff
2017) (n 130 064, d 50), Pose 5
2006 (n 488,565, Uzilov et al.
d d= 8), and Song (Berein-Maheeux et al. 2011 (n 515,345, d = 90).
We pre-process the data sets to ensure each data point has bounded 62-norm. Following the common approach in differential privacy to bound contributions at a quantile (Abadi et al.] 2016 Geyer et al. 2017 Amin et al. 2019), we set the f2 cut-off point r to the 97.5 percentile and discard the points whose norm exceeds r. Moreover, we center each data set since this a preroquisite for the coresct-based sampling distribution, see Scction 4
Setup. The specific task we consider is k-means for which we use the weighted version of DP-Lloyd. We fix the number of iterations of Dl-Lloyd to T 10 and the number of clusters to A = 25. The scale parameters are set to Brum
/ Tr V 2p and Aeount = 2/4dp2/sum,, where p 0.225 suggested by Su et al. (016)). Here, B is a constant controlling the noise scales that we select to achieve specific target epsilon C' E (0.5, 1,3, 10, 30, 100, 300, 1000.0} for a given (expected) subsample size m and vice versa.
We evaluate the following three different importance samplers and use various sample sizes, i.e., m E [3000, 75000), depending on the data set. For the coreset-based (core) sampling, the sampling distribution is Jcore (x) m + (1 >)
where set x 1.- The uniform (unif) sampling uses quuit(x) m/n. Note
https: /ttpps//github... com/mdeff/tmo.
httpp://kwes www.::ccee..... .nu. edu, http:////wlllaalooooooo///aaaaaa
http://osmot.ct www.eac.c.coocl.cc.. htt.::/cwwwccdcceeea/aasettttee. html
http://viiiion www.iiaaaa.aaaaaaaa haaperrr//maaannnmm waw.mamnn...e/caallagee...oo

---

Published in Transactions on Machine Learning Research (12/2024)
KDD-Protein m=5000
RNA
Song
Covertype m=5000
1e6
m=5000
1e6
m=5000
1e6
7
10000
Obi func. on all data
6
8000
5
6000
5
4-
2
4000
3
4
2000
2
3
0
1e6
m=10000
m=00000
1e6
m=20000
1e6
m=
5000
unlt
3.0
Obj. func. on all data
core
4000
5
opt
5
4
3000
unif
2000
4
3-
1.0
2
1000
3
0.5
0
1e6
1=15000
m 50000
1e6
5=0000
1e6
7500000
func. all data
6
2.5
3000
5
2.0
4
2000
1.5
3
1.0
1000
0.5
10a
10
6 10
10
10a
10
10?
10a
10c
101
102
10a
10a
10:
10
10
8
E
Figure 3: The trade-off between the privacy parameter and the total cost. of DP-Lloyd KDD-Protein, RNA, Song, and Covertype data. Non-private counterparts (e oo) are shown for reference. Lower is better on both axes. The c-axis is in log-scale.
that it is the same 9 as in core but with À 1. For the privacy-constrained (opt) sampling, we compute (priv (x) numerically via Algorithm [ for the target c* (r/Ssum + 1/ ccomm)) )T using the strong convexity constant from Equation 4
Due to the stochasticity in the subsampling process and the noises within DP-Lloyd, we repeat each experiment 50 times with different seeds and report on median performances. addition, we depict the 75% and 25% quartiles. Note that the weighted version of DP-Lloyd only used when learning the cluster centers, f.e., not for evaluation. Furthermore, we initialize the cluster centers as random data points. For all sampling-baso approaches, we re-compute the objective function (cost) on all data after running DP-Lloyd on the sampled subset and report the total cost scaled by the number of data points n -1
The cod is implemented in Python using numpy Harris et al. 2020). Algorithm is implemented in Rust. All experiments run on a dual AMD Epyc machine with 2 x 64 cores with 2.25 GHz and 2 TiB of memory.
Results. We first evaluate the trade-off between the privacy parameter e and the total cost DP-Lloyd. Figure depicts the results for KDD-Protein, RNA, Song, and Covertype. Within the figure, each column
10

---

Published in Transactions on Machine Learning Research (12/2024)
KDD-Protein 3.3
RNA 8330
Song 8=3.0
Covertype 8=3.0
1e6
1e6
1e6
6.5
6000
Obj. func. on all data
3.0
6
6.0
4000
5.5
5
2.0
5.0
4
2000
4.5
1.5
4.0
1.0
1e6
E=100.0
E=100.0
1e6
E=100.0
1e6
E=100.0
Obj func. on all data
1000
unif
5.0
2.0
care
800
1.5
opt
4.0
3-
600
full
1.0
3.5
400
2-
3.0
200
5000
10000
15000
5000
25000
50000
5000
25000
50000
5000 25000 50000 75000
Subsample size m
Subsample size m
Subsample size m
Subsample size m
Figure 4: The trade-off between subsample size m and the total cost of DP-Lloyd for fixed privacy parameters E {3, 100} on KDD-Protein, RNA, Song, and Covertype data. The performance of DP-Lloyd on the full data is shown for reference. Lower better on both axes.
corresponds to a data set and the rows show different subsampling sizes m. The curves are obtained by subsampling m data points and training DP-Lloyd on the obtained subset for which we vary B and re-compute the total cost, i.e., the cost evaluated on all data, Thus, we see the performance DP-Lloyd as a function of the privacy parameter c. Note that the r-axis is in log-scale, shared column- wiie, and that the optimal location is the bottom left since it yields a low cost and low privacy parameter. Additional results on Ijennl, Pose, MiniBooNE, and FMA are shown in Figure D in Appendix B The performance of uniform subsample of the data set of size m (unif, blue line) always yields the worst results. Our first proposed subsampling strategy core (green line) consistently outperforms unif as it yields a better cost-e-parameter trade-off. The other proposed sampler opt (yellow line) usually performs on-par or slightly better than core. Note that the privacy-constrained sampling strategy opt only optimizes two out of three objectives: privacy and efficiency but not accuracy. Although privacy and accuracy are often well aligned in this problem, there is no formal guarantee on the accuracy. In particular, the degree of alignment between privacy and accuracy depends the specific mechanism and data set used. This is why its cost is not necessarily smaller than for core. Additionally, we show the non-private versions of unif and core (mostly overlapping) that correspond to the choice of 6 0o a reference. Note that the performance converges to the non-private version as we increase e. Note also that, as - 0, the cost approaches but stays below that of performing no learning at all. This can be seen by comparison to the column of Table 1: when the cluster centers are initialized to zero, the cost is precisely ã, i.e., the average squared f2 norm. The main take-away is that both our proposed sampling strategies consistently yield a botter tradc-off between the privacy parameter c and the total cost of (DP-)k-means than unif.
Next, evaluate the performance of the subsampling strategies functions of the subsample size m, i.e., the trade-off between sample size m and the total cost of DP-Lloyd. For this scenario, we fix the privacy budget to either = 3 or e = 100. Figure f depicts the results for the data sets KDD-Protein, RNA, Song, and Covertype. As expected, the total cost decreases as we increase the subsample size m. Moreover, we can see that unif (blue line) - once again performs consistently worst. In contrast, the corcsct-inspired sampling core (green line) and sampling using wrivacy-constrained weights opt (yellow line) yields lower total cost for the same m and For reference, we also include the performance of DP-Lloyd using the same
11

---

Published in Transactions on Machine Learning Research (12/2024)
Covertype m=20000
unif
30
Total relative computation time (%6
|jcnnl
Total relative computation time (%6]
24
Relative subset size (9)
20
FMA
KDD-Protein
15
Covertype
10
-10
Relebve
5
Weight computation
Subset sampling
DP-Jloyd
10000
20000
30000
40000
50000
Subsample size
unif
Figure 5: Left: Total relative computation times (left y-axis) and relative subset sizes (right y-axis) as functions of subsample sizes m for five data sets. Right: Relative computation times decomposed in weight computation, sampling, and DP-Lloyd for the Covertype data and a subsample size of m=20,,00.
privacy parameter but all data, i.e. without any subsampling, black line (full). Unsurprisingl, the total cost of the subsampling methods approaches the total cost of full as approaches n. Note that this happens faster for our subsampling methods than for unif.
Lastly, we measure the computation times of the different sampling strategies to confirm that they are short relative the computation time of Dl-Lloyd. This supplements the iteration complexity analysis from Proposition [2 Figure (left) shows the total relative computation times (left y-axis), i.e. the time (i) compute the weights, (ii) subsample the data set, and (iii) compute DP-Lloyd for various subset sizes m, relative to computing DP-Lloyd all data using = 3.0 for five data sets. Each line in the figure refers to a combination of data set and sampling strategy. In addition, we show the fraction m//ndtt (right y-axis) per data set as a black dotted line. To improve readability, we omit Min Song and RNA from the plot because they overlap with the lincs of other data sets. For completeness, we show the numbers tabular form in Appendix C for all data sets. A sampling strategy can be considered elficient its relative vertical offset from the black dotted line is small. This the case for all data sets and sampling strategies. Additionally, Figure 5 (right) depicts the dccomposed computation times for the Covertype data set and subsample size of m0200000. We can see that the time needed to subsample the data set (violet) is negligible and that the time DP-Lloyd takes (green) is almost static. For this data set, the weight computation (blue) for the opt weight computation takes significantly more time than for unif and core. However, the difference is small relative to the runtime DP-Lloyd on all data. Specifically, a subset size of m=20,000 amounts to approximately 3.5% of the Covertype data set. Using the opt subsampling strategy takes slightly more than 4% of the time DP-Lloyd takes on the full data set.
6 Related Work
The notion personalized differential privacy introduced by Jorgensen et al. (0015) and Ebadi al. (2015). as well as by Alaggan et al. (2016) under the name of heterogencous differential privacy. In Jorgenson et al. (2015), the privacy parameter associated with a user, while is associated with the value of a data point in the work of [Ebadi et al. (2015) and ours. Jorgensen et al. (2015) achieve personalized DP by subsampling the data with heterogencous probabilities, but without accounting for the bias introduced by the heterogeneity. Moreover, this privacy analysis is loose as it does not exploit the inherent heterogeneity of the original mechanism's privacy guarantee.
Recently, there has been renewed interest in PDP due to its connection to individual privacy accounting and fully adaptive composition (Feldman & Zrnic 2021; Koskela al. 20023 Yu et al. (002).. In this context, privacy filters have been proposed means to answer more queries about data set by redueing
12

---

Published in Transactions on Machine Learning Research (12/2024)
PDP guarantee its worst-case counterpart. Analogously, our srivacy-constrainee importance sampling distribution can be used to subsample data set by reducing PDP guarantee to its worst-case counterpart.
The idea of using importance sampling for differential privacy is not entirely new. Wei et al. 2022 propose a differentially private importance sampler for the mini-batch selection in differentially private stochastic gradient descent. Their sampling distribution resembles the variance-optimal distribution we display Figure 2 The major drawback of this distribution is its intractabilityy it requires us know the quantity conssyyconstrained distribution is very close to the
want to compute in the first place. Note that variance-optimal distribution while being efficient to compute. Moreover, their privacy analysis is restricted to the Gaussian mechanism and does not generalize to general DP or Rényi-DP mechanisms, because it is based on Mironov et al. 2019)'s ' analysis of the subsampled Gaussian mechanism.
The first differentially private version k-means is introduced by Blum et al. 2005). They propose the Sub-Lincar Queries (SuLQ) framework, which, for k-mcans, uses a noisy (Gaussian) estimate of the number of points per cluster and noisy sur of distances. This is also reported by [Su al. (2016) 2017) which
extend the analysis. Other variants of differentially private k-means were proposed, e.g. by Balcan et al.
(2017]
Huang & Liu (2018); [Stemmer & Kaplan (2018) Sheehhne et al. (2020); Ghazi et al. (2020 Nguyen
ct al. 20210; Cohen-Addad et al. 2022).
7
Conclusion
We introduced and analyzed Poisson importance sampling for subsampling differentially private mechanisms. We observed that, for typical mechanisms, privacy is well aligned with utility and at odds with sample size. Based on this insight, we proposed two importance sampling distributions: one that navigates the trade-off between privacy and sample size and another based on coresets which have strong utility guarantees. The empirical results suggest that both strategies have stronger privacy and utility than uniform sampling at any given sample size.
Promising directions for future work include extensions 8)P or Rényi-DP as well as establishing formal utility guarantees via coresets. For the latter, recent work on confidence intervals for stratified sampling (Lin) et al. 2024h might serve starting point. Moreover, Poisson importance sampling is directly applicable to streaming setting, because it considers each data point separately. This provides an opportunity to improve efficiency further. In federated learning, Poisson importance sampling might be used to improve client selection (Zhang et al. 2024). Additionally, its connection to fairness could be explored where importance sampling can be used to mitigate bias (Wang et al., 2023).
Acknowledgements
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. This research has been carried out as part of the Vinnova Competence Center for Trustworthy Edge Computing Systems and Applications at KTH Royal Institute of Technology.
References
Martín Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Tlya Mironov, Kunal Talwar, and Li Zhang Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Commanications Security, pp.
ACM, 2016.
Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec. Heterogeneous differential privacy. Journal of Privacy and Confidentiality, 7(2). 2016.
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. In International Conference on Learning Representations 2016.
13

---

Published in Transactions on Machine Learning Research (12/2024)
Kareem Amin, Alex Kulesza, Andres Muñoz, and Sergei Vassilvtiskii. Bounding user contributions: A bias- variance trade-off in differential privacy. In International Conference on Machine Learning, pp. PMLR, 2019.
Olivier Bachem, Mario Lucie, and Andreas Krause. Scalable k-means clustering via lightweight coresets. Tn Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1119-112. ACM, 2018.
Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differentially private clustering in nigh-dimensional euclidean spaces. In International Conference on Machine Learning, pp. 322-331. PMTR, 2017.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, volume 31, 2018.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science, pp. 464 473. IEEE, 2014.
Thierry Bertin-Mahicux, Danicl P.W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. Proceedings of the 12th International Conference on Music Information Retrieval, 2011.
Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Compulers and Electronics in Agriculture, 24(3):131-155 151, 1999.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the founth ACM JJGMODSSIGACT-SIGARI symposium on Principles of Database Systems, pp. 128 138, 2005.
Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan, and Jayshree Sarathy. Controlling privacy loss in sampling schemes: An analysis of stratified and cluster sampling. In 3rd Symposium Foundalions of Responsible Computing, FORC 2022, June 6-8, 2022, Cambridge, MA, USA, volume 218 of LIPIcs, pp. 1:1-1:24. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2022.
Cristian Sminchisescu Catalin lonescu, Fuxin Li. Latent structured models for human pose estimation. In International Conference on Computer Vision, pp. 2220-2227, 2011.
Chih-chung Chang and Chih-Jen Lin. LJCNN 2001 challenge: Generalization ability and text decoding. In Proceedings of International Joint Conference on Neural Networks, volume 2, pp. 1031-1036. IEEE, 2001.
Vincent Addan, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong, Near- optimal private and scalable k-clustering. In Advances in Neural Information Processing Systems, volume 35, pp. 10462-10411 2022.
Michaël Defferrard, Kirell Benzi, Pierre Vandergheynst, and Xavier Bresson. FMA: A dataset for music analysis. In 18th International Society for Music Information Retrieval Conference (ISMIR), 2017.
Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. CoRR, abs/ hbss1995.00383, 2019.
Jörg Drechsler and James Bailie. The complexities of differential privacy for survey data. Technical report, National Bureau of Economic Research, 2024.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htsp://archiiv..cce..dd..
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributod noise generation. In Advonces in Cryptology- Craptolay-EUROCCYY EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486-503. Springer, 2006a.
14

---

Published in Transactions on Machine Learning Research (12/2024)
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryplography: Third Theory of Cryplography Conference, pp. 265-284, Springer, 2006b.
Cyuthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundalions of Computer Science, pp. 51 60. IEEE Computer Sociely, 2010.
Hamid Ebadi, David Sands, and Gerardo Schneider. Differential privacy: Now it's gelting personal. In Sriram K. Rajamani and David Walker (eds.), Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 69-81. ACM, 2015.
Vitaly Feldman and Tijana Zrmic. Individual privacy accounting via a Rényi filter. In Advances in Neural Information Processing Systems, volume 34, pp. 18080-28011) 2021.
Robin C. Geyer, Tassilo Klein, and Moin Nabi. Differentallly private federated learning: A client level perspective. CoRR, abs/1712.07557,, 2017.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation
ratios. In Advances in Neural Information Processing Systems, volume 33, pp. 4040-4054, 2020.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchast Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 385(7825): 357- 362, 2020.
Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering, In Proceedings of the 37th ACM SIGMOD-STGACCTSSTAA Symposium on Principles of Database Systems, pp. 395-408, 2018.
Catalin Ionescu, Dragos Papava, Vlad Olaru, and Cristian Sminchisescu. Human3.6M: Large Scale Datasets and Predictive Methods for 3D Human Sensing in Natural Environments. IEFE Transactions on Pattern Analysis and Machine Intelligence, 2014.
Zhanglong Ji, Zachary C Lipton, and Charles Elkan. Differential privacy and machine learning: a survey and review. ar Xie preprind 11 7584, 2014.
Zach Jorgensen, Ting Yu, and Graham Cormode. Conservative or liberal? personalized differential privacy. In Johannes Gehrke, Wolfgang Lehner, Kyuseok Shim, Sang Kyun Cha, and Guy M. Lohman (eds.), 31st IEEE International Conference on Data Engineering, pp. 1023 1034. IEEE Computer Society, 2015.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International Conference on Machine Learning, pp. 1376- 1385. PMLR, 2015.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? In 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 531-540. IEEE Computer Society, 2008
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International Conference on Machine Learning, pp. 2525 25344. PMLR, 2018.
Antti Koskela, Marlon Tobaben, and Antti Honkela. Individual privacy accounting with Gaussian differential privacy. In The Eleventh International Conference on Learning Representations, 2023.
Shurong Lin, Mark Bun, Marco Gaboardi, Eric D Kolaczyk, and Adam Smith. Differentially private confidence intervals for proportions under stratified random sampling. Electronic Journal of Statistics, 18(1):1455-144) 1494, 2024.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Stuart Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129-177, 1982.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium Foundations of Computer Science (FOCS), pp- 94-103. IEEE Computer Society, 2007.
Nya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled Gaussian mechanism. ArXie, abs/1908.1055 2019.
Huy I. Nguyen, Anamay Chaturvedi, and Eric 7 Xu. Differentially private k-means via exponential mechanism and max cover. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9101 9108, 2021.
Christian P. Robert and George Casella. Monte carlo statistical methods. Technometrics, 47:243 243, 2005.
Moshe Shechner, Or Sheffet, and Uri Stemmer. Private k-means clustering with stability assumptions. Artificial Intelligence and Statistics, pp. 2518 2528. PMLR, 2020.
Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint Xii:2220000057 2022.
Uri Stemmer and Haim Kaplan. Differentially private k-means with constant multiplicative error. In Advances in Neural Information Processing Systems, volume 31, 2018.
Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. Differentially private k-means clustering. In Proceedings of the Sirth ACM Conference on Data and Application Security and Privacy, pp. 26 37, 2016.
Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, Min Lyu, and Hongxia Jin. Differcntially private k-means clustering and hybrid approach to private optimization. ACM Transactions on Privacy and Securily, (4):1-33, 2017.
Andrew V Uzilov, Joshua M Keegan, and David H Mathews. Detection of non-coding rmas on the basis of predicted secondary structure formation free energy change. BMC Bioinformatics, 7(1):1-30, 2006.
Rui Wang, Pengyu Cheng, and Ricardo Henao. Toward fairness in text generation via mutual information minimization based on importance sampling. In International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain, pp. 4473-4485. PMLR, 2023.
Jianxin Wei, Ergute Bao, Xiaokui Xiao, and Yin Yang. Dpis: An enhanced mechanism for differentially private sgd with importance sampling. In Proceedings of the 2022 ACM SIGSAC Conference Computer and Communications Security, pp. 2885-2899, 2022.
Da Yu, Gautam Kamath, Janardhan Kulkarni, Tie- Liu, Jian Yin, and Huishuai Zhang. Individual privacy accounting for differentially private stochastic gradient descent. Transoctions on Machine Learning Research, 2023.
Jiaojiao Zhang, Dominik Fay, and Mikael Johansson. Dynamic privacy allocation for locally differentially privale lederated learning with composite objectives. In ICASSP 2024 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 9461 9465, 2024.
16

---

Published in Transactions on Machine Learning Research (12/2024)
Appendix
Section discusses sufficient. conditions under which importance sampling does does not improve privacy.
Section includes experimental results on additional data sets.
Section contains details on the computation time measurementts.
Section contains the proofs for Theorem Proposition 12 and Proposition
13 Moreover, it which describes the weighted version of DP Lloyd.
contains A Imorithm
2
A Can sampling improve privacy?
We have pointed out in Section 3 that, in importance sampling, the privacy loss is not necessarily reduced by decreasing the sampling probability. In this section, we make this statement more precise and provide formal conditions on the PDP profile under which weighted sampling does or does not improve privacy when reweighting is accounted for.
First, note that any mechanism M that simply ignores the weights {w:).- has a weighted PDP profile e(w, x) that is constant in w. In this case, Theorem reduces to the established amplification by subsampling result (Proposition 3), which indeed implies that .M satisfies a stronger privacy guarantee than M. This is possible because such a mechanism is not invariant under splitting weighted point (w,x) into unweighted points {11,) The following proposition provides a more general sufficient condition under which M satisfics a stronger privacy guarantee than M.
Proposition 16. Let M X" x [1, + an c-PDP mechanism, M its unweighted counterpart defined M({x,)=z)) M([(1, x=))==), and ē(x) = e(1,x) be the PDP profile of M. Furthermore, let Then, there is a Poisson importance sampler 5(-) for which the following holds. Let up be the PDP profile of M o S implied by Theorem 6 For any x E X, if
be differentiable in w and <(,,x) = =dc(w,x)/e
x11 <-- -((lxx, then (xx) < E(x).
Proof. Let x E X' be any data point for which (1, < < <1-e- e(1xxx the selection probability (xx) and show that it increasing at q(x) = We write (x) to make the dependence on q(x) explicit and define w(w) exp((11/mxx))
holds. We treat (xx) as a function of
We have
(1) (l(1)) dw
(c'(1, ((11) -1) +1 < <1x() ((1 - e1-e-elte -((lxx) - 11) + =0,
and, hence, degg(t) (x)/dq(x) > at q(x) = 1. As a result, there is a probability ((x) < 1 such that 19(x)) (x) w (x) Z(x).
Consequently, if the condition x((1 < x1-e e1(x-)((x) holds in neighborhood around the maximizer x* arg max ē(x), then M satisfies DP with strictly smaller privacy parameter than M.
However, for the following important class of mechanisms, M cannot satisfy a stronger privacy guarantee than M.
Proposition 17. Let M, M, e, é', and as in Proposition 16 S(-) be any Poisson importance sampler, db be the PDP profile of MoS S implied by Theorem and X. If c(w, x) S wd x) for all w > 1, then (xx) 2 ((x).
the core idea is treat ((x) as a function of the selection probability q(x). We we'ww, show that (x) non-increasing in q(x) if the condition e(w, x) we'l (w, x) is satisfied for all wc
Proof. As in Proposition 16
17

---

Published in Transactions on Machine Learning Research (12/2024)
Let ((x) be the selection probability of x under S. We write d (x) to make the dependence on g(x) explicit.
Let X' be arbitrary but fixed and define w(w) = exp(111 (x)) 1. We have
dw(w) dw
ex(wxx) (we'Ew (w, x) - 1) +1
w²
ed(wxx) (e(w, x) 1) +1
W
(c(w, x) + 1)(c(w x)) - 1) +1
(ww, x)2
w²
0,
where we used the assumption c(w,x) x) S wwc(w,, x) in the first incquality and the fact that e² 2 2 in the second inequality. As a result, w is minimized at w and, hence, th is minimized at g(x) = 1. To complete the proof, observe that (x) ē(x) for g(x)= =.
2 + 1 for all
For instance, the condition <(w, x) S ww'(w, x) is satisfied everywhere by any profile of the form e(w, x) fx))w, where p 2 and f is any non-negative function that does not depend on w. This includes any mechanism that is invariant under splitting weighted point (w,x) x) into w unweighted points {(1,x)) since group privacy implies linear PDP profile in this case. All mechanisms considered in this paper satisfy this invariance.
It is important to note that, even in case where we cannot hope to improve upon the original mechanism, it is still possible to obtain a stronger privacy amplification than with uniform subsampling at the same sampling rate. Indeed, the uniform distribution is never optimal unless the PDP profile of the original mechanism constant.
18

---

Published in Transactions on Machine Learning Research (12/2024)
B Results on the Remaining Data Sets
Table 1: Information on the data sets. Remember that n, d, and I denote the sample size, dimensionality,
largest fo-mo and average squared 2--norm, respectively.
Data Set
(after outlier removal)
d
T
T
Main Paper
KDD-Protein
142,107
74
8020.65
7031359.55
RNA
476,350
8
420.67
24902.47
Song
502,461
90
75
6769375.49
Covertype
566,486
54
4489.17
3839798.28 28
Appendix
Ijennl
48,740
22
1.51
1.26
Pose
34,936
48
2250.64
1249739.50
MiniBooNE
126,812
50
2213.05
295947.13 13
FMA
103,909
518
6020.23
5838871.8
Figure 0 depicts the results for the remaining data sets Ijenn1, Pose, MiniBooNE, and FMA. Note that those data sets are smaller in lerms of the number of data points as the data sels shown in Figure 3 see Table | As seen in Figure O we can observe the smallest difference among the subsampling strategies across all data sets occurs for Ijenn1, especially for the m=15,000 case. All subsampling strategies behave alike, except for the m=10,000 case where unif worse than core and opt. On Pose, MiniBooNE, and FMA, our subsampling strategies consistently outperform unif. Tn addition, Figure depicts deppicts the cost-sample-size-m ratios for the remaining data sets Ijennl, Pose, MiniBooNE, and FMA for fixed privacy budgets of = 3 and 100. Once again, the only data set in which no clear improvement is visible is Ijennl.
19

---

Published in Transactions on Machine Learning Research (12/2024)
|icnn1
MiniBooNE
m=5000
m=3000
m=4000
m=5000
Obl func. on all data
0.24
unif
250000
core
1.0
200000
opt
0.22
0.8
150000
core
100000
50000
0.1
m=10000
1e6
5=5000
m=5000
1e6
m=10000
0.23
Obi func. on all data
0.22
0.21
0.8
0.19
50000
0.18
0.4
m=15000
1e6
m=8000
m=7000
1e6
m=15000
0.22
Ooj func. on all data
0.21
1.0
200000
150000
100000
0.19
50000
0.18
0.4
10
10
Figure The trade-off between the privacy parameter e and the total cost of DP-Lloyd on Ijennl, Pose, MiniBooNE, and FMA data. Non-private counterparts (e = 20) are shown for reference. Lower is better on both axes. The e-axis is in log-scale.
20

---

Published in Transactions on Machine Learning Research (12/2024)
Ijcnn1
Pose
MiniBooNE
FMA E=3.0
E=3.0
1e6
6=3.0
E=3.0
Obj. func. on all data
0.22
unt
250000
1.10
0.21
200000
1.05
5.0
0.20
full
150000
1.00
4.5
0.19
0.95
100000
E=100.0
E 1-000.0
E=100.0
E=100.0
0.205
900000
140000
4.0
Obj. func. on all data
120000
3.5
100000
0.195
3.0
80000
0.190
700000
2.5
0.185
600000
40000
2.0
20000
4000
4000
10000
15000
Subsample size
Subsample size
Subsample size
Subsample size
Figure 7: The trade-off between sample size m and the total cost DP-Lloyd for fixed privacy parameters E {3, 100) on Ijennl, Pose, MiniBooNE, and FMA. The performance of DP-Lloyd on the full data is shown for reference. Lower is better on both axes.
21

---

Published in Transactions on Machine Learning Research (12/2024)
C
Detailed Timing Results
Table 2: The exact numbers of Figure 5 for the first four data sets. Times are in seconds.
Data Set
Sampling
fweiglat
fsamptiug
Doo-
frotal
rel. tot. time [%]
[%]]
KDD-Protein
full
10
15.69
15.69
100
100
KDD-Protein
unif
5000
0.0005
0,0026
0.54
0.55
3.19
3.52
KDD-Protein
unif
10.000
0.0004
0.0029
1.09
1.10
6.99
7.04
KDD-Protein
unif
15,000
0.0004
0.0035
1.69
1.69
10.79
10.56
KDD-Protein
unif
20,000
0.0001
0.0042
2.20
2.20
14.04
14.07
CDD-Protehl
coTe
5000
0.0198
0.0025
0.55
0.57
3.64
3.52
KDD-Protein
core
10,000
0.0187
0.0030
1.09
1.11
7.10
7.04
KDD-Protein
co0e
15,000
0.0182
0.0034
1.66
1.69
10.75
10.56
KDD- Protein
come
20,000
0.0185
0.0040
2,22
2.24
14.29
14.07
KDD-Protein
opt
5000
0.1112
0.0023
0.53
0.65
4.12
3.52
KDD-Protein
opt 10,000
0.1076
0.0031
1.10
1.21
7.72
7.04
ProPPiotein
opt 15,000
0.1134
0.0034
1.64
1.76
11.22
10.56
KDD-Protein
opt 20,000
0.1051
0.0039
2.20
2.31
14.73
1/100
RNA
full 5000
12
42.24
42.24
100
100
RNA
unif
0.0004
0.0051
0.44
1.04
RNA
mnif
10,000
0.0006
0.0056
0.88
0.88
2.09
2.10
RNA
unif
15.000
0.0005
0.0060
1.32
1.32
3.14
3.15
RNA
unif
20,000
0.0006
0.0064
1.73
1.74
4.12
4,20
RNA
unif
50,000
0,0005
0,0082
4.35
4.36
10.33
10.50
RNA
coTE
5000
0.0153
0.0051
0.44
0.46
1.08
1.05
RNA
core
10,000
0.0149
0.0057
0.87
0.89
2.12
2.10
RNA
co0e
15,000
0.0136
0.0061
1.33
1.35
3.19
3.15
RNA
core
20,000
0.0153
0.0066
1.74
1.76
4.18
4.20
RNA
core
50,000
0.0160
0.0080
1.34
4.37
10.34
10.50
RNA
opt
5000
0.3955
0.0051
0.44
0.84
1.98
1.05
RNA
opt
10,000
0.3865
0.0055
0.88
1.27
3.02
2.10
RNA
opt
15,000
0.3817
0,0061
1.30
1.69
3.99
3.15
RNA
opt
20,000
0.3776
0.0066
1.73
2.12
5.01
4,20
RNA
opt 50,000
0.3376
0.0085
4,40
4.77
11.28
10.50
Song
full
10
59.47
59.47
100
100
Song
unif
5000
0.0016
0.0074
0.56
0.57
0.96
1.00
Song
unif
10,000
0.0018
0,0077
1.14
1.15
1.94
1.99
Song
unif
15,000
0.0017
0.0077
1.76
1.77
2.97
2.99
Song
unif
20,000
0.0015
0.0084
2.29
2.30
3.86
3.98
Song
unif
50,000
0.0017
0.0146
5.75
5.77
9.70
9.95
Song
core
5000
0.0748
0.0067
0.56
0.64
1.08
1.00
Song
core
10,000
0.0774
0.0076
1.15
1.24
2.08
1.99
Song
come
15,000
0.0765
0.0084
1.74
1.82
3.06
2.99
Song
core
20,000
0.0750
0.0091
2,31
2.39
4.03
3.98
Song
coTe
50.000
0.0780
0.0145
5.80
5.80
9.90
9.95
Song
opt
5000
0.4353
0.00G3
0.57
1.69
1.00
Song
opt
10,000
0.4020
0.0075
1.16
1.57
2.64
1.99
Song
opt
15.000
01.4073
0.0083
1.73
2.15
3.61
2.99
Song opt
20,000
0.3945
0.0088
2.31
2.71
4.56
3.98
Song opt 50,000
0.3789
0.0146
5,85
6.25
10.51
9.95
Covertype full 5000
59.91
59.91
100
100
Covertype unif
0.0013
0.0062
0.52
0.53
0.88
0.88
Covertype unf
10,000
0.0019
0.0070
1.05
1.06
1.76
1.77
Covertype
unif
15,000
0.0018
0.0077
1.56
1.57
2.63
2.65
Covertype
unif
20,000
0.0014
0.0082
2.15
2.16
3.61
3.53
Covertype
mnif
50,000
0.0014
0.0115
5.34
5.35
8.93
8.83
Coverlype
core
5000
0.0558
0.0062
0.52
0.58
0.97
0.88
Covertype
core
10,000
0.0567
0.0068
1.05
1.11
1.86
1.77
Covertype
come
15.000
0.0563
0.0076
1.57
1.633
2.72
2.65
Coverlype
core
20,000
0.0569
0.0082
2.10
2.17
3.62
3.53
Covertype
50,000
0.0567
0.0115
5.28
5.31
8.92
8.83
Covertype
opt
5000
01.6684
0.0063
0.53
1.00
1.67
0.88
Covertype
opt 10,000
0.4614
0.0069
1.07
1.51
2.57
1.77
Covertype
opt
15,000
0.4440
0.0077
1.58
2.03
3.38
2.65
Covertype
opt 20,000
0.4404
0.0082
2.13
2.57
4.30
3.53
Covertype
opt
50,000
0.1237
0.0115
5.28
5.71
9.54
8.83
22

---

Published in Transactions on Machine Learning Research (12/2024)
Table The exact numbers of Figure 5 for the last four data sets. Times are in seconds.
Data Set
Sampling
fwstiit
fammping
frotal
rel. tol. timre [9]
[96]
Ijenal
fill
4.88
4.68
100
100
[jemt
unif
3000
0.0001
0.00018
0.29
6.16
[jendl
unif
4000
0.0001
0.0008
0.35
0.38
8.15
8.21
Ijemml
Ijeml
unif
6000
0.0001
0.0010
0.58
0.58
12:33
12.31
Ijennl
1000
0.0001
0.0011
0.67
14.38
14.36
[jennl
unif
10,000
0.0001
0. 0.0012
0.96
0.95
20.26
20.02
Ijenal
unif
15,000
0.0001
0.0015
1.43
1.43
30.55
30.78
Tjenn
unif
0.0002
1.92
41.13
Ijenal
core
3000
0.0022
0.0008
0.30
0.30
6.37
6.16
Ijemm
Ijemal
core
5000
0.0026
0.0009
0.48
0.48
10.33
10.26
Ijenn]
core
6000
0.0021
0.0010
0.57
0.58
12:31
[jenal
7000
0.0021
O. 0.0013
0.69
0.70
14.86
14.36
Ijemal
core
10,000
0.0022
0,0012
0.96
0.96
20.19
20.52
Ijenal
15,000
0.0021
0.0015
1.46
1.47
31.36
30.78
[Jenal
com
20,001
0.0022
0.0017
1.93
1.544
41.40
41.03
Ijenal upl
0.0347
Ijemal
opt
4000
0.0311
0.0008
0.39
0.42
9,03
8.21
Ijemal opt
5000
0.0340
11.02
[jenni opt
6000
0.0338
0.0000
0.58
0.62
13.23
12.31
[jenal opt
7000
0.0331
0.0010
0.67
0.70
15.01
14.36
Ijenal opt
10,000
0.0329
0,0012
0,95
0.95
20.99
20.52
Ijenal opt 15,000
0.0318
0.0015
1.43
1.47
31.36
30.78
Ijenal opt
20,000
0.0319
0.0017
1.91
1.94
41.51
41.03
Pose
full
3.59
3.59
100
100
0.0801
Pose
unif
4000
0.0001
0.0008
0.41
0.41
11:35
11.45
Pose
unif
5000
0.0001
0,0009
0.51
0.51
14.15
14.31
Pose
unif
6000
0.0061
0.0010
0.62
0.62
17.19
17.17
Pose:
unif
7000
0.0001
0.0011
0.72
0.72
20.04
20.04
Pose
Pose
core
3000
0.0029
0.0007
0.31
0.31
8.65
8.59
Pose
0.0026
0,40
11.37
Posc
core
5000
0.0026
0.0009
0.50
0.51
14.15
14.31
Powe
core
6000
0.0025
0.0010
0.61
0.61
17.02
17.17
Pose
7000
0.0026
O. 0.0011
0.72
0.73
20.21
20.01
Pose
core
8000
0.0028
0.0011
0.8L
0.81
22.65 68
22.90
Pose
opt
3000
0.0257
0.0008
0.31
0.33
9.30
Pose
opt
4000
0.0265
0.0009
0.41
0.44
12.24
11.45
Pose
opt
Pose
opt
6000
0.0252
0.0010
0.60
0.63
17.46
17.17
Pose
opt
7000
0.0247
0.0011
20.59
20.04
Posn
8000
0.0245
0.0011
0.80
0.83
23.05
22.90
ManiBoNN
full
13.16
13.16
100
100
MiniBooNE
unif
4000
0.0864
0,0019
0.41
0.41
3.12
3.15
MiniBooNe
unif
5000
0.0064
0.0021
0.51
0.51
3.91
3.94
MinBBoNN
0.0004
MiniBooNE
unif
7000
0.0004
0.0025
0.72
0.72
5.18
5.52
MiniBooNE
0.0122
ManBBoNE
5000
0.0127
0. 000022
0.52
0.51
4,08
3.94
MiniBooNE
core
6000
0.0128
0.0022
0.62
0.64
4.85
4.73
MiniBooNE
7000
0.0129
0.0030
0.73
0.75
5.69
5.52
ManiBoNN
opt
4000
0.1000
0.0019
0.41
0.51
3.88
3.15
MinBBoNN
opt
MiniBooNE
opt
6000
0,0000
0.0023
0.61
0.71
5,39
4.73
MiniBooNE
opt
7000
FMA
full
26.65
26. 46
100
100
FMA
unif
5000
0.0002
0.0010
1.27
1.28
4.79
4.81
FMA
unif
10,000
0.0002
0,0068
2.56
2.57
9.63
9.62
FMA
unif
15,000
0.0002
0.0145
3.56
3.88
14.55
14.44
FMA
5000
0.0798
0.0040
FMA
core
10,000
0.0798
0.0112
2.66
2.75
10.31
9.62
15,000
14.87
FMA
opt 5000
0.0755
0.0041
1.27
1.35
5.06
4.81
opt 10,000
0.0760
0.0069
2.53
9.62
FMA
15,000
0.0754
0.0124
3.88
3.97
14.89
14.44
23

---

Published in Transactions on Machine Learning Research (12/2024)
D Proofs
This section contains the proofs of all our theoretical results. For completeness, we do not only restate the theorems and propositions, but also the used algorithms, assumptions, and problems.
D.1 Theorem 6
Theorem (Amplification by Importance Sampling). Let M: [1,00) X + be an e-PDP mechanism that operates on weighted data sets, q: X - [0, a function, and S.(.) be Poisson importance sampler for q. The mechanism M = Mo Sg satisfies PDPDP with
(x) log q(x)) (ellux) -1)) where
1 g(x)
(1)
Proof. The proof is analogous to the proof of the regular privacy amplification theorem with 6 = 0, see, e.g.,
Steinke 20022 Theorem 29). Let A be any mcasurable subset from the probability space of M(D). We begin
by defining the functions P(Z)= Pr M(D) (D)) = z) and (z(Z) Pr M(D') E A S, z
Let D D' for some x E X. Note that
Pr Mr[M(D) E A (P)(S q(x)) x E S2(D)) + (1 (00g(()))(P((((())) S2(D)).
(6)
We can analyze the events (D) and & (D) separately as follows. Conditioned the event x & (D), the distributions of (D) and Sq (D') are identical since all selection events 7 are independent:
E(P(S,(D) x & S2( = E(P(S,(D')) x & E[
(7)
On the other hand, conditioned on the event Sy(D), the sets SD and S,(D) {x} are neighboring, and the distributions of (D, \ (x) and (D')') are identical. We can use the PDP profile to bound
E[P(S,(D)) x E (D) < E <(1/g(x)) P'(S,(D))) x S,S)
(8)
x0 E''
Plugging Equations 7 and S
into Equation
yields
Pr M(D) e A
s (1 - (x-x(()))PPPPs(0000 ((x) hwgp:///sp00000g0/0uu///ooooooo0
= (1+ -1)
= (1 (1+ (///0))) Pr(-)) eA].
An identical argument shows that
Pr [r[M EA 1 1 Pr Pr[M e eA].
24

---

Published in Transactions on Machine Learning Research (12/2024)
D.2 Theorem 10
Problem 7 (Privacy-constrained sampling). For PDP profile e: [1, X + R20; larget privacy guaran- tee e", and a data set D - X' of size n, we define the optimization problem for privacy-com constrainn sampling as
minimize Wi
(2a)
W
( (e(mxx))) 11) SE*
subject to
log 1
for all i,
(2b)
Wi
12 1,
for all i.
(2c)
Assumption 8. For all x E X, et (1,x).
Assumption 9. For all x E X, there constant Ux 2 such that e(w, x) > log(1 wle 1)) for all
w 2 lx-
Assumption 11. The function e(w, x) differentiable w.r.t. and exp e -t-otryn convex in w for all
Algorithm 3.2 Optimization for privacy-consttriined importance weights
1: Input: Data set D = .x....., Xn,, target privacy guarantee e* > 0, PDP profile e, its derivative with respect to w, and strong convexity constants ; Output: Importance weights w Wn
for i= l......, do Define 9:(w) (er(vxx))) -1) (6 1) in < minfe + 14/2, c((1, ((1,,,))((xx))) + +1 b < 2(c - 0.)/uu +1 and c'(1, x:) < then Wi + Bisect gi with initial bracket (1, b:]
if (11, x;)= =
8:
else
10:
- Bisect with initial bracket [1, b,]
11: end if
12:
end for
Theorem 10. Let Assumptions 8 and be satisfied. There is data set- let-independent function X - [1, oo), such that, for all data sets D E X"; Problem 0 has a unique solution w" (D) (wi (D),... w (D) of the form (D) = w(x:). Farthermore, lel M be a mechanism that admils the PDP profile and S be Poisson importance sompler for =
= 1/w((x). Then, M o Sg satisfies -DP
Proof. Since the objective is additiiee over w; and each constraint only affects one wi, we can consider each iy separately. An equivalent formulation of the problem is
maximize w0
W/
subject to log 1+ (cllux;x)) - -1) s
1 wi
Wa 2 1.
Assumption 8 guaraatees that the feasible region is non-emply and Assumption g guarantees that it is bounded. Since the objective is strictly monotonic, the solution must be unique.
7
D.3 Proposition 12
Proposition 12. Let Assumptions and 11 be satisfied. Algorithm I solves Problem 7 up to accuracy
with at most ExED logz (ee Ux)/ (aflx)] evaluations of c(w, x), where c'wwx) 0/0w c(w,x) and ix min (11x))) + px/2, c'(1, (1)))))e(Lx)) + 1}.
25

---

Published in Transactions on Machine Learning Research (12/2024)
Before beginning the proof, state the definition of strong convexity for completeness.
Definition 18 (Strong convexity). Let > 0. A differentiable function f : IR + R is p-strongly convex if
f(v) 2 f(u) + Vo(u) - u) + 1 - - for all u, u, R"
(9)
Proof of Proposition 12 First, we show that Assumption find value oi for each such that all w; 2 v are infeasible. For some fixed i, define g(w) e(w, xx) and g' (w) (ww). We apply the strong convexity condition from Equation
11 implics Assumption That is, we want
9 to exp opoog g at u 1 and v wi
es(w) 2 e0(1) + g((1)eol)) (w - 1) + M w
1
2
W - 2 2 w + ( - ((())
1 (w(w
+ 1
) -
+ g ('())e(()) m
-
2
w
1
(16) -1) 2 byw' + bow b-1w-
w
for appropriately defined constants b,, by, and 1-1. We neod to distinguish two cases, based on the sign of
b-1.
Case 1: b_1 < O. this case, we have 1_1== 1 2 b-1 for all 2 1. A sufficient condition for infeasibility is
b bo b-1 2 e- -1
c²¹
bo
b-1
w 2
b1
(1(1) + 11/2
w 2
112
e² - coll) - 11/22 +1)
2 2
Case 2: 6-1 2 0. In this case, we have b-w 2 0. Analogously to Case 1, the condition for infeasibility is
by bo
2 6t
ee¹
-1 1 bo b1
w
ee
g (1)) +
11/2
e=
-1 g((1)ea(1)
+ +1).
w
We can summarize the two cases by defining
1/ e U, ==(("==
f -+++1)
+1).
where 6 = min minfeet) ((o))) + 1 2' ((1))0()+)) +1}
Then, Vs is the desired constant for Assumption 9
Having established that the optimal solution w is in the interval [1, Us], it remains to show that can be found via bisection search. Bisection finds a solution to
1 (alw) -1) E", w
log 1
or, equivalently,
(ww) wo uee"-11 1.
(10)
26

---

Published in Transactions on Machine Learning Research (12/2024)
Since the left hand-side of Equation 10 is strongly convex and the right hand-side is linear, there can be at most two solutions to the equality. We distinguish two cases.
Case 1: 9(1) = E- and g((1) < <1-e-9(1) In this case, there is a neighborhood around w in which we have ea(w)) "(e" -1) + 1. This implies that there are two solutions to Equation (10 one at w = and one in w E (1, v.]. The latter the desired solution.
Case 2: (1) < or g((1) 2 1--e--e 9 In this case, either condition guarantees that there is exactly one solution to Equation (10 in E [1] With the first condition, it follows from the convexity of exp og If the first condition is not met but the second one is, then we have co(w) 2 w(e" -1) + for all w 2 1. Then, the uniqueness follows from strong convexity.
The two cases are implemented by the if-condition in Algorithm
!
Algorithm Weighted DP Lloyd's algorithm
Input: Weighted data set S [w,, x,)) initial cluster centers C, number of iterations T,, noise scales
Ssum: Scount
Output: Cluster centers Ci....,Ck
for 1= 1,...,7 do
Compute cluster assignments Ci...., Ck, where C₁ {xi 1 arg miny ||x; cy ||]
for == j= l,.... do
Sample Ey ~ Lap(O, Bcount)
Sample {j from the density proportional to exp(-Ils) (sum)
Update Cý
(5) Σ (wxx)Ec, wx
tiwiee,
end for end for
D.4 Proposition 13
Algorithm 2 summarizes the weighted version of differentially private Lloyd's algorithm as introduced in Section 4.
Proposition 13. The weighted DP Lloyd algorithm (Algorithm satisfies the PDP profile
|x|12 Bram
(Loyd (10, x) =
Two.
(3)
3count
Proof. The weighted DP-Lloyd algorithm consists of T' weighted sum mechanisms and T' weighted count mechanisms. The weighted sum mechanism exponential mechanism while the weighted count mechanism uses Laplace noise. We first derive the PDP profile for general exponential mechanism and then reduce the two special cases to the general case.
Let. D = (ww, x= U ((wo, xo)} and D' = ((w,, x;) denote neighboring data sets. Let M(D) a mechanism taking values in IRd, distributed according to the probability density function f(y) & xxp(=kd(y, g (D)) where & > 0, d(-,)) :) a metric on Rd and g [1, x X' - y is a function where ) C Rdd In order to bound the privacy loss of M, require that the influence on of any single weighted point (wo, Xo) be bounded. Specifically,
require that there exist. a function A X Rzo such that
d(g(D).g(D')) I Axx)) for all neighboring D, D' differing in (wo,xo).
(11)
27

---

Published in Transactions on Machine Learning Research (12/2024)
Given these prerequisites, can see that the PDP profile of M is bounded
f(y)
h (d(v,)(D)) d(v.g(D')) log fee
dy
log
f'(v)
Sg exp( - d(y, (D)))) dy
S (d((y.g(D))) g(D)) - o(y))
s (ddgg()) (x))
The first inequality follows bocause the two integrals are identical due translation invariance (note that the integrals are over all of IR.). The second inequality follows from the triangle inequality for the metric d. The third inequality follows from Equation [1].
Having established the general case, we apply it to the two submechanisms that constitute the weighted DP-Lloyd algorithm.
The weighted sum mechanism is an exponential mechanism for g(D) -' wx and d(y, 3/) lly v'Ilp for some p > 0 and k 1/5aum- The scnsitivity function is Axx) |x||p because
Mg l|wo xollp = wo |xxolx-
Thus, [log fog) &
The weighted count mechanism is an exponential mechanism for g = ((x)) and d(y, v/) ly - y'l and 1/Bouunt. The sensitivity function is A(x) because
d(g(D),s(D') /w0l Wg-
Thus, [log fog)f S wo/ Bcount.
The result now follows by adaptive composition over the T iterations of the algorithm.
28


Reviews:
[{"review_id": "v7up8WZAGm", "reviewer": "Reviewer_5tAQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The use of importance sampling for DP mechanisms addresses a significant problem.\n- The paper explores a natural application of importance sampling in DP, i.e., the DP k-means clustering.\n- The experimental results provide promising evidence, demonstrating the benefits of using importance sampling over trivial uniform sampling in relevant scenarios.\n\n\n**Weaknesses:**\n- The study is largely confined to the $\\epsilon$-PDP framework, limiting its applicability to other widely adopted notions of differential privacy (including the technically more interesting ones). Moreover, given that the work builds upon the $\\epsilon$-PDP framework, some of the subsequent derivations appear relatively straightforward.\n- The overall presentation could benefit from improvements. Stronger logical connections between key points, more intuitive motivation to enhance understanding, and clearer descriptions of the experimental results would significantly improve the paper. Additionally, several confusing sections are noted below that could be clarified further.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of importance sampling within the framework $\\epsilon$-PDP (Personalized differential privacy). \nSpecifically, this paper proposed a subsampling algorithm towards optimizing the expected sampled size (mimicking the efficiency objective) for a given PDP algorithm $M$, while bounding the subsampled algorithm $M\\circ S_q$ to maintain a privacy guarantee under $\\epsilon^⋆-$DP. \n\nFurthermore, the paper explores the application of importance sampling to the differentially private k-means clustering problem and introduce a coreset-based sampling scheme. \n\nExperimental results demonstrate that importance sampling can generally improve the utility-/efficiency- privacy trade-off compared to uniform sampling.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The objective defined in Eq. (2a) would be more accurately described as \"efficiency-optimal\" rather than \"privacy-optimal\" sampling.\n\n- The experimental setup in Section 3.3 could be clarified further. It would be helpful to explicitly state the $\\epsilon(w_i, x_i)$  function used in the experiment. Additionally, providing the formula for the MSE visualized in Figure 2 would improve clarity.\n\n- In Figure 2 (right), the MSE achieved by variance-optimal sampling appears to outperform the proposed “privacy-optimal” approach. It would be insightful to explain the rationale for not always using variance-optimal sampling and to highlight the principled advantages of the proposed importance sampling method.\n\n- Page 22, Equation (6): It seems that the multipliers for the first and second terms may need to be $q(x)$ and $(1-q(x))$ instead of $(1-q(x))$ and $q(x)$.\n\n- Page 23, Theorem 10:\nThe statement: “Assumption 8 guarantees that the feasible region is bounded, and Assumption 9 guarantees that it is non-empty. Since the objective is strictly monotonic, the solution must be unique.”\nshould be corrected to:\n“Assumption 8 ensures the feasible region is non-empty, and Assumption 9 guarantees it is bounded.”\n\n\n- Page 24, Proof of Proposition 12: For consistency, the notation $\\mu_i$​ should be changed to $\\mu$.", "broader_impact_concerns": "Since this paper focuses on a rigorous privacy guarantee framework and the experiments are conducted on standard public datasets,  I do not identify any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1V6pJkscey", "reviewer": "Reviewer_HJwH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The work provides interesting insights into how a higher expected sample size may worsen overall privacy loss when individual privacy losses are known. \n2. Similarly, the synergy b/w informativeness and high-privacy loss is a valuable tool that is intuitive but it was useful to have actual numerical examples to verify the same.\n3. Designing individual sampling weights with privacy in mind is a broad enough problem that deserves attention in several learning techniques and can be quite valuable.\n4. Overall presentation and empirical results look good.\n\nWeaknesses:\n1. From Algorithm 1, it's unclear how the privacy of the weights is maintained (since they depend on the training dataset/dataset's privacy which may leak some information about the data). Adding exact details here would be useful\n2. From the optimization problem, it makes sense that having a lower expected sample size is good based on the sampling weights. But there seems to be some confusion here. a) I think a larger population size is still desired, and I believe in the current writeup it seems that we may want the total sample size to be small. Adding some clarification here will be good. b) From a hypothetical point of view, how does problem 7 handle the following case? Suppose, a single point is significantly more informative than others (and the final probabilities are 0.99 for the one point, v/s 1e-3 for the rest) then will the same point get chosen each time with high probability? (this is probably more applicable to something like an SGD problem v/s k-means).\n3. What is the applicability of the problem setting in 7 to problems other than K-means? It would be nice to get some insights here.\n4. For the user-DP or local-DP scenario, how can algorithm 1 be modified? Wherein the privacy costs for each sample may be unknown or need to be disclosed under DP as well.\n5. Curious, if without privacy guardrails, only the most informative samples are chosen then can we observe better utility? This could be similar to the coreset setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This article studies the relationship b/w privacy, utility, and importance (or informativeness of samples) to understand how important sampling may help improve privacy guarantees. The primary insight by the authors is that leveraging the most informative samples (which generally have high individual privacy loss) will not only lead to better utility (expected) but rather will also provide better privacy protection and thus these samples need to be chosen more often. Directly and counterintuitively, this implies that a smaller expected number of samples is often preferred (the most informative samples) to achieve good utility and privacy.\n\nAfter setting up an appropriate optimization problem for minimizing the expected sample size (by optimizing for the sampling weights) over the individual privacy profiles, the authors provide an algorithm for achieving the same. Furthermore, empirical results for the k-means problem verify the solution proposed. Overall, this work provides valuable insights into the synergy between individual privacy and importance sampling", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The changes requested are mainly on the presentation of the sample size results. Please refer to the weaknesses section and provide some more details on how the sample size is different compared to traditional sampling (mainly on population size, and privacy when the same sample is chosen more often than others).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cAmuIE7iaR", "reviewer": "Reviewer_dK8Z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe work is well written and well-motivated. The methods are (to the best of my knowledge) sound (conditional on some clarifications I requested below) and are definitely of interest to the TMLR readers as well as a privacy research community. I particularly like the split of the privacy-utility into a privacy-utility-efficiency discussion, making this more of a relevant discussion to settings such as distributed ML.\n\nWeaknesses:\n\nThe concept of poisson sampling for privacy amplification is hardly new and has been thoroughly explored in prior works and dp frameworks (e.g. dp-transformers or opacus to name a few), I am not sure exactly what is the reader meant to gain as the main message of the work? That you can also have importance sampling with poisson which is more efficient? Or that it produces a better PDP profile? The actual value of the contributions is a bit lost on me here. \n\nFurther to my comment on efficiency-utility: I am actually struggling to see the practical difference between the terms (i.e. higher efficiency means that the utility of a ML model is higher and vice versa) and am not convinced that this part of the manuscript explains the interplay well/correctly. Particularly with respect to samples which have a higher privacy loss (as these are likely to be 'memorised' by the model) and samples of high utility are often those that are both important and useful to the model. Can you elaborate on this, because I do not see straightaway what the trade-off is here between utility and efficiency? And, hence, I would have also expected them to have an identical/similar privacy trade-off too.\n\nThis is more of a clarification than a weakness: if one starts weighting the selection of each sample differently, this would mean that the actual privacy loss of individuals in the dataset would be very different (and it may even occur that some of them go over the privacy budget), how is this accounted for in this framework? Or am I missing something here? \n\nQuestions:\n\nIs there a principled way to reason over m? In some of your experiments its arbitrarily set to 19, in others searched over a list. Can this quantity be chosen (somewhat) reasonably without the extensive knowledge of the underlying dataset or obtaining data-related statistics?\n\nI assume that this is only true for real independent variables and settings (i.e. the sampling is unlikely to have meaningful interpretation in deep learning models or in time-series datasets, for instance?)\n\nWhen discussing the epsilon level of k-means from a 2-step process, how are the budgets composed across them?\n\nAre the reported privacy losses expected to be very different across samples? \n\nI did not fully understand this phrase: 'Notably, with privacy-optimal sampling, we can achieve some sampling “for free” by assigning a\nsampling probability of 1 to the data point(s) with the highest privacy loss and probabilities less\nthan 1 to the remaining points.' Could you elaborate on why exactly is this the case?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a novel framework for importance sampling in the context of personalised differential privacy. Here the privacy-utility-efficiency tradeoff is explored and two approaches are proposed: one based on the privacy-optimal sampling and one based on the concept of coresets. The work demonstrates the results both theoretically and empirically (k-means clustering) on a number of datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "For k-means there are no results with epsilons of 0 and infinity, meaning that the other ones are more difficult to contextualise, I would encourage the authors to add these.\n\nText-based changes:\n\nThere is not enough explanation for how to interpret figure 3, it could benefit from a simplified summary.\n\nExplain the interplay between utility and efficiency in a broader setting.\n\nAdd concrete explanation for the broader context of the work's contributions.\n\nYour figures 3 and 4 are difficult to interpret for people with red-green colorblindness. You should change these.\n\nOverall (given the broad community of TMLR), I believe this work is of interest and of relevance. I have checked the majority of the theorems, but have not gone into the proofs in the appendix in more detail, so these seem sound to me.\n\nSo in general, provided the authors can respond to questions and concerns well and no other fundamental issues are raised by the reviewers, I would lean towards acceptance.", "broader_impact_concerns": "No specific concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously agreed that the paper is worth of publication so the decision is clear. I also think the results of Section 3, including the optimization based approach of Section 3.2, are very interesting. 
Comment: you mention in the conclusions that "Promising directions for future work include extensions to $(\varepsilon,\delta)$-DP or R\'enyi-DP...", however no details on possible RDP aspects are givne. Perhaps the RDP-filtering analysis by Feldman and Zrnic could be quite directly used to get similar results for RDP? If you think so, feel free to add a sentence or two, though this is not necessary.
Decision: Accept (poster)