# Privacy Amplification via Importance Sampling

Dominik Fay
KTH
Elekta
& Sebastian Mair
Uppsala University
& Jens Sjölund
Uppsala University

###### Abstract

We examine the privacy-enhancing properties of subsampling a data set via
importance sampling as a pre-processing step for differentially private
mechanisms. This extends the established _privacy amplification by
subsampling_ result to importance sampling where each data point is weighted
by the reciprocal of its selection probability. The implications for privacy
of weighting each point are not obvious. On the one hand, a lower selection
probability leads to a stronger privacy amplification. On the other hand, the
higher the weight, the stronger the influence of the point on the output of
the mechanism in the event that the point does get selected. We provide a
general result that quantifies the trade-off between these two effects. We
show that heterogeneous sampling probabilities can lead to both stronger
privacy and better utility than uniform subsampling while retaining the
subsample size. In particular, we formulate and solve the problem of privacy-
optimal sampling, that is, finding the importance weights that minimize the
expected subset size subject to a given privacy budget. Empirically, we
evaluate the privacy, efficiency, and accuracy of importance sampling-based
privacy amplification on the example of $k$-means clustering.

##  1 Introduction

When deploying machine learning models in practice, two central challenges are
the efficient handling of large data sets and the protection of user privacy.
A common approach to the former challenge is subsampling, i.e., performing
demanding computations only on a subset of the data. Here, importance sampling
can improve the efficiency of subsampling by assigning higher sampling
probabilities to data points that are more informative for the task at hand,
while still retaining an unbiased estimate. For instance, importance sampling
is commonly used to construct coresets, that is, subsets whose loss function
is provably close to the loss of the full data set, see, e.g., Bachem et al.,
(2018). For the latter challenge, differential privacy (Dwork et al., 2006b, )
offers a framework for publishing trained models in a way that respects the
individual privacy of every user. Differential privacy and subsampling are
related via the concept of _privacy amplification by subsampling_
(Kasiviswanathan et al.,, 2008; Balle et al.,, 2018), which states that
subsampling a data set can amplify the privacy guarantees of a subsequently
run differentially private algorithm. It forms the theoretical foundation for
many practical applications of differential privacy, such as differentially
private stochastic gradient descent (Bassily et al.,, 2014).

The established privacy amplification by subsampling result has two primary
caveats. First, it does not account for the dependence of the privacy cost on
the data set size. Typically, the privacy cost of a mechanism decreases with
the size of the data set. Therefore, the benefit due to privacy amplification
often cancels out with the privacy cost of evaluating the mechanism on a
smaller data set (see, e.g., Bassily et al., (2014)). Second, it is
incompatible with importance sampling, because importance sampling weights
each data point by the reciprocal of its selection probability. This weight
affects the privacy guarantees of the mechanism, which is not accounted for in
the privacy amplification result.

In this paper, we generalize the privacy amplification by subsampling result
to importance sampling by accounting for the effect of the importance weights
on the privacy cost. Moreover, we take into account that different data points
may have different impacts on the distinguishability of the output of a
mechanism. Exploiting this structure allows us to derive importance sampling
distributions that obtain substantially stronger privacy guarantees than
uniform subsampling at the same subsample size. We instantiate our theoretical
results for the example of $k$-means clustering, where we show experimentally
that importance sampling can lead to both stronger privacy and better utility
than uniform subsampling at the same subsample size.

#### Contributions.

In summary, our key contributions are as follows. (i) We present our general
amplification result that quantifies the privacy of an arbitrary mechanism
when sub-sampled via Poisson importance sampling with an arbitrary
distribution. (ii) We derive the optimal sampling distribution for any
arbitrary but fixed mechanism that minimizes the expected sample size subject
to a given privacy budget. These distributions always outperform uniform sub-
sampling. (iii) We apply our results to the problem of differentially private
$k$-means. There, we compare the privacy-optimal sampling distribution to
uniform sampling and coreset-based sampling in terms of efficiency, privacy
and accuracy.

##  2 Preliminaries

We begin by stating the necessary concepts that also introduce the notation
used in this paper. We denote by $\mathcal{X}\subseteq\mathbb{R}^{d}$ the set
of all possible data points. A data set $\mathcal{D}$ is a finite subset of
$\mathcal{X}$. We denote by
$\mathcal{B}_{d,p}(r)=\\{\mathbf{x}\in\mathbb{R}^{d}\mid\|\mathbf{x}\|_{p}\leq
r\\}$ the $p$-norm ball of radius $r$ in $d$ dimensions. When the dimension is
clear from context, we omit the subscript $d$ and write $\mathcal{B}_{p}(r)$.

#### Differential Privacy.

Differential privacy (DP) is a formal notion of privacy stating that the
output of a data processing should be robust, in a probabilistic sense, to
changes in the data set that affect individual data points. It was introduced
by Dwork et al., 2006b , and has since become a standard tool for privacy-
preserving data analysis (Ji et al.,, 2014). The notion of robustness is
qualified by two parameters $\epsilon\geq 0$ and $\delta\geq 0$ that relate to
the error rate of any adversary that tries to infer whether a 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 indistinguishability

######  Definition 1 ($(\epsilon,\delta)$-indistinguishability).

Let $\epsilon\geq 0$ and $\delta\geq 0$. Two distributions $P,Q$ on a space
$\mathcal{Y}$ are $(\epsilon,\delta)$-_indistinguishable_ if $P(Y)\leq
e^{\epsilon}Q(Y)+\delta$ and $Q(Y)\leq e^{\epsilon}P(Y)+\delta$ for all
measurable $Y\subseteq\mathcal{Y}$.

######  Definition 2 ($(\epsilon,\delta)$-DP).

A randomized mechanism $\mathcal{M}\colon\mathcal{X}\to\mathcal{Y}$ is said to
be $(\epsilon,\delta)$-_differentially private_ ($(\epsilon,\delta)$-DP) if,
for all neighboring data sets
$\mathcal{D},\mathcal{D}^{\prime}\subseteq\mathcal{X}$, the distributions of
$\mathcal{M}(\mathcal{D})$ and $\mathcal{M}(\mathcal{D}^{\prime})$ are
$(\epsilon,\delta)$-indistinguishable. For $\delta=0$ we say $\mathcal{M}$ is
$\epsilon$-DP. Two data sets $\mathcal{D},\mathcal{D}^{\prime}$ are
neighboring if $\mathcal{D}=\mathcal{D}^{\prime}\cup\\{\mathbf{x}\\}$ or
$\mathcal{D}^{\prime}=\mathcal{D}\cup\\{\mathbf{x}\\}$ for some
$\mathbf{x}\in\mathcal{X}$.

Formally, we consider a randomized mechanism as a mapping from a data set to a
random variable. Differential privacy satisfies a number of convenient
analytical properties, including closedness under post-processing (Dwork et
al., 2006b, ), composition (Dwork et al., 2006b, ; Dwork et al., 2006a, ;
Dwork et al.,, 2010; Kairouz et al.,, 2015), and sampling (Kasiviswanathan et
al.,, 2008; Balle et al.,, 2018). The latter is called _privacy amplification
by subsampling_.

######  Proposition 1 (Privacy Amplification by Subsampling).

Let $\mathcal{D}$ be a data set, $\mathcal{S}$ be a subset of $\mathcal{D}$
where every $\mathbf{x}$ has a constant probability $p$ of being independently
sampled , i.e., $q(\mathbf{x})=p\in(0,1]$, and $\mathcal{M}$ be a
$(\epsilon,\delta)$-DP mechanism. Then, $\mathcal{M}(\mathcal{S})$ satisfies
$(\epsilon^{\prime},\delta^{\prime})$-DP for
$\epsilon^{\prime}=\log\mathopen{}\mathclose{{}\left(1+\mathopen{}\mathclose{{}\left(\exp(\epsilon)-1}\right)p}\right)$
and $\delta^{\prime}=p\delta$.

In the case of heterogeneous sampling probabilities $p_{i},\ldots,p_{n}$, the
privacy amplification scales with $\max_{i}p_{i}$ instead of $p$. The result
has also been extended to fixed-size sampling (with or without replacement)
(Balle et al.,, 2018) and to Rényi differential privacy (Zhu and Wang,, 2019).

#### Importance Sampling.

In learning problems, the objective function that we optimize is often a mean
over per-point losses. Uniformly subsampling a data set yields an unbiased
estimation of the mean. A common way to improve upon uniform sampling is 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 $\mathcal{D}$ which we use to sample a subset $\mathcal{S}$ of
$m\ll n$ points and weight them with $w(\mathbf{x})=(mq(\mathbf{x}))^{-1}$.
Moreover, let
$\phi_{\mathcal{D}}=\sum_{\mathbf{x}\in\mathcal{D}}\ell(\mathbf{x})$ be the
objective function using data $\mathcal{D}$. Then, the estimation of the
objective function is unbiased, i.e.,
$\mathbb{E}_{\mathcal{S}}\mathopen{}\mathclose{{}\left[\phi_{\mathcal{S}}}\right]=\phi_{\mathcal{D}}$.

#### Differentially Private $k$-means Clustering.

Given a data set $\mathcal{D}$ as introduced before, the goal of $k$-means
clustering is to find a set of $k\in\mathbb{N}$ cluster centers
$\mathcal{C}=\\{\mathbf{c}_{1},\ldots,\mathbf{c}_{k}\\}$ that minimize the
distance of the data points to their closest cluster center. The objective
function is given as
$\phi_{\mathcal{D}}(\mathcal{C})=\sum_{i=1}^{n}d(\mathbf{x}_{i},\mathcal{C})$,
where $d(\cdot,\cdot)$ is the distance of a point $\mathbf{x}$ to its closest
cluster center $\mathbf{c}_{j}$ which is
$d(\mathbf{x},\mathcal{C})=\min_{j}\|\mathbf{x}-\mathbf{c}_{j}\|^{2}$. The
standard approach of solving the $k$-means problem is Lloyd’s algorithm
(Lloyd,, 1982). It starts by initializing the cluster centers $\mathcal{C}$
and then alternates between two steps. First, given the current cluster
centers $\mathcal{C}$, we compute the cluster assignments
$\mathcal{C}_{j}=\\{\mathbf{x}_{i}\mid
j=\operatorname*{arg\,min}_{j}\|\mathbf{x}_{i}-\mathbf{c}_{j}\|^{2}\\}$ for
every $j=1,\ldots,k$. Second, we update all cluster centers to be the mean of
their cluster
$\mathbf{c}_{j}=\frac{1}{|\mathcal{C}_{j}|}\sum_{\mathbf{x}\in\mathcal{C}_{j}}\mathbf{x}$.
Those two steps are iterated until convergence.

A generic way to make Lloyd’s algorithm differentially private is to add
appropriately scaled noise to both steps of the algorithm. This was first
suggested by Blum et al., (2005) and later refined by Su et al., (2016, 2017).
In this paper, we follow the variant of Su et al., (2016), which we refer to
as DP-Lloyd. Let $\xi\in\mathbb{R}^{k}$ be a random vector whose entries
independently follow a zero mean Laplace distribution with scale
$\beta_{\mathrm{count}}>0$. Furthermore, let
$\zeta_{1},\ldots,\zeta_{k}\in\mathbb{R}^{d}$ be random vectors whose entries
independently follow a zero mean Laplace distribution with scale
$\beta_{\mathrm{sum}}>0$. The update of the cluster centers as well as the
number of points per cluster are noisy:

$\displaystyle\mathbf{c}_{j}=\frac{1}{\xi_{j}+|\mathcal{C}_{j}|}\mathopen{}\mathclose{{}\left(\zeta_{j}+\sum_{\mathbf{x}\in\mathcal{C}_{j}}\mathbf{x}}\right).$

Assuming the points have bounded 1-norm, i.e.,
$\mathcal{X}=\mathcal{B}_{1}(r)$ for some $r>0$, DP-Lloyd preserves
$\epsilon$-DP with
$\epsilon=\mathopen{}\mathclose{{}\left(r/\beta_{\mathrm{sum}}+1/\beta_{\mathrm{count}}}\right)T$
after $T$ iterations. Su et al., (2016) suggest allocating the noise variance
across the two steps as
$\beta_{\mathrm{count}}/\beta_{\mathrm{sum}}=\sqrt[3]{4d\rho^{2}}$, where
$\rho\approx 0.225$ is an empirically derived constant.

#### Coresets for $k$-means.

A coreset is a weighted subset $\mathcal{S}\subseteq\mathcal{D}$ of the full
data set $\mathcal{D}$ with cardinality $m\ll n$, on which a model performs
provably competitive when compared to the performance of the model on
$\mathcal{D}$. Since we are now dealing with weighted data sets, we define the
weighted objective of $k$-means to
$\phi_{\mathcal{X}}(\mathcal{C})=\sum_{i=1}^{n}w_{i}d(\mathbf{x}_{i},\mathcal{C})$,
where $w_{i}\geq 0$ are the non-negative weights. In this paper, we use a
lightweight-coreset construction as introduced by Bachem et al., (2018).

######  Definition 3 (Lightweight Coreset).

Let $\varepsilon>0$, and $k\in\mathbb{N}$ and
$\mathcal{D}\subseteq\mathcal{X}$ be a set of points with mean
$\bar{\mathbf{x}}$. A weighted set $\mathcal{S}$ is a
$(\varepsilon,k)$-lightweight-coreset of the data $\mathcal{D}$ if for any
$\mathcal{C}\subseteq\mathbb{R}^{d}$ of cardinality at most $k$ we have
$|\phi_{\mathcal{D}}(\mathcal{C})-\phi_{\mathcal{S}}(\mathcal{C})|\leq\frac{\varepsilon}{2}\phi_{\mathcal{D}}(\mathcal{C})+\frac{\varepsilon}{2}\phi_{\mathcal{D}}(\\{\bar{\mathbf{x}}\\})$.

Note that the definition holds for any choice of cluster centers
$\mathcal{C}$. Bachem et al., (2018) propose the sampling distribution
$q(\mathbf{x})=\frac{1}{2}\frac{1}{n}+\frac{1}{2}\frac{d(\mathbf{x},\bar{\mathbf{x}})}{\sum_{i=1}^{n}d(\mathbf{x}_{i},\bar{\mathbf{x}})}$
and assign each sampled point $\mathbf{x}$ the weight $(mq(\mathbf{x}))^{-1}$.
This is a mixture distribution of a uniform and a data-dependent part. Note
that by using these weights, $\phi_{\mathcal{S}}(\mathcal{C})$ yields an
unbiased estimator of $\phi_{\mathcal{D}}(\mathcal{C})$. The following theorem
shows that this sampling distribution yields a lightweight-coreset with high
probability.

######  Theorem 1 (Bachem et al., (2018)).

Let $\varepsilon>0,\Delta\in(0,1)$, $k\in\mathbb{N}$, $\mathcal{D}$ be a set
of points in $\mathcal{X}$, and $\mathcal{S}$ be the sampled subset according
to $q$ with a sample size $m$ of at least $m\geq c\frac{kd\log
k-\log\Delta}{\varepsilon^{2}}$, where $c>0$ is a constant. Then, with
probability of at least $1-\Delta$, $\mathcal{S}$ is an
$(\varepsilon,k)$-lightweight-coreset of $\mathcal{D}$.

##  3 Privacy Amplification via Importance Sampling

In this section, we present our novel theoretical contributions and general
results on privacy amplification via importance sampling. We first quantify
the privacy of an arbitrary mechanism when run on a weighted subsample
obtained from an arbitrary distribution. Then, we derive the optimal sampling
distribution for any arbitrary but fixed mechanism that minimizes the expected
sample size subject to an $\epsilon$-DP constraint. All proofs of our
theoretical results are deferred to the appendix.

#### Privacy of Arbitrary Sampling Distributions.

We begin by introducing the sampling strategy we use throughout the paper. It
is a weighted version of the Poisson sampling strategy described in
Proposition 1. We refer to it as _Poisson importance sampling_.

######  Definition 4 (Poisson Importance Sampling).

Let $q\colon\mathcal{X}\to[0,1]$ be a function, and
$\mathcal{D}=\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\\}\subseteq\mathcal{X}$
be a data set. A Poisson importance sampler for $q$ is a randomized mechanism
$S_{q}(\mathcal{D})=\\{(w_{i},\mathbf{x}_{i})\mid\gamma_{i}=1\\}$, where
$w_{i}=1/q(\mathbf{x}_{i})$ are weights and $\gamma_{1},\ldots,\gamma_{n}$ are
independent Bernoulli variables with parameters $p_{i}=q(\mathbf{x}_{i})$.

The function definition of $q$ should be considered public information, i.e.,
fixed before observing the data set. Note that $q$ is not a probability
distribution over $\mathbf{x}$, but simply any function that assigns a number
between 0 and 1 to each data point. The expected sample size is
$\mathbb{E}[|S_{q}(\mathcal{D})|]=\sum_{i=1}^{n}q(\mathbf{x}_{i})$. In order
to combine such a data-dependent sampling scheme $S_{q}$ with a mechanism
$\mathcal{M}$, we also need a data-dependent privacy guarantee for
$\mathcal{M}$. For this purpose, we define the notion of a _distinguishability
profile_. It captures the inherent heterogeneity in a mechanism’s privacy
loss.

######  Definition 5 (Distinguishability Profile).

A function $\epsilon\colon\mathcal{X}\to\mathbb{R}_{\geq 0}$ is a
distinguishability profile of a mechanism $\mathcal{M}$ if, for all data sets
$\mathcal{D}\subseteq\mathcal{X}$ and differing points
$\mathbf{x}\in\mathcal{X}$, the distributions of $\mathcal{M}(\mathcal{D})$
and $\mathcal{M}(\mathcal{D}\cup\\{\mathbf{x}\\})$ are
$\epsilon(\mathbf{x})$-indistinguishable.

Since importance sampling produces weighted data sets, we also need a weighted
version of a distinguishability profile, in order to describe mechanisms that
operate on weighted data sets.

######  Definition 6 (Weighted Distinguishability Profile).

A function $\epsilon\colon[1,\infty)\times\mathcal{X}\to\mathbb{R}_{\geq 0}$
is a weighted distinguishability profile of a mechanism $\mathcal{M}$ if, for
all weighted datasets $\mathcal{S}=\\{(w_{i},\mathbf{x}_{i})\\}_{i=1}^{n}$ and
differing points $(w^{\prime},\mathbf{x}^{\prime})$, the distributions of
$\mathcal{M}(\mathcal{S})$ and
$\mathcal{M}(\mathcal{S}\cup\\{(w^{\prime},\mathbf{x}^{\prime})\\})$ are
$\epsilon(w^{\prime},\mathbf{x}^{\prime})$-indistinguishable.

We are now ready to state the first main result.

######  Theorem 2 (Amplification by Importance Sampling).

Let $\mathcal{M}$ be a mechanism that admits a weighted distinguishability
profile $\epsilon(w,\mathbf{x})$. Let $q\colon\mathcal{D}\to[0,1]$ be a
function and $S_{q}(\cdot)$ be a Poisson importance sampler for $q$. The
mechanism $\widehat{\mathcal{M}}=\mathcal{M}\circ S_{q}$ admits the
distinguishability profile

$\displaystyle\psi(\mathbf{x})=\log\mathopen{}\mathclose{{}\left(1+q(\mathbf{x})\mathopen{}\mathclose{{}\left(e^{\epsilon(w,\mathbf{x})}-1}\right)}\right),\quad\text{where}\quad
w=1/q(\mathbf{x}).$ (1)

Clearly, if a distinguishability profile $\psi$ has an upper bound
$\psi(\mathbf{x})\leq\epsilon$ for all $\mathbf{x}\in\mathcal{X}$, then the
mechanism is $\epsilon$-DP. Indeed, as we show in the next subsection, it is
always possible to construct a sampling distribution $q$ that allows the
distinguishability profile $\psi$ of $\mathcal{M}\circ S_{q}$ to be bounded.
However, when arbitrary $q$ and $\epsilon$ are given, $\psi$ might not be
bounded. For instance, consider a weighted sum with Laplace noise:
$\mathcal{M}(\mathcal{D})=\zeta+\sum_{i=1}^{n}w_{i}f(\mathbf{x}_{i})$, where
$\zeta\sim\operatorname{Lap}(0,1)$. The weighted distinguishability profile of
$\mathcal{M}$ is $\epsilon(w,\mathbf{x})=w|f(\mathbf{x})|$. For
$q(\mathbf{x})\propto|f(\mathbf{x})|^{2}$, the resulting distinguishability
profile $\psi$ diverges as $f(\mathbf{x})\to 0$.

#### When does sampling improve privacy?

A natural question to ask is whether we can expect the sampled mechanism
$\widehat{\mathcal{M}}$ to satisfy a stronger privacy guarantee than the
original mechanism $\mathcal{M}$. Trivially, any mechanism $\mathcal{M}$ that
simply ignores the weights $w_{1},\ldots,w_{n}$ has a weighted
distinguishability profile $\epsilon(w,\mathbf{x})$ that is constant in $w$.
In this case, Theorem 2 reduces to the established amplification by
subsampling result (Proposition 1), which indeed implies that
$\widehat{\mathcal{M}}$ satisfies a stronger privacy guarantee than
$\mathcal{M}$. The following proposition provides a more general condition
under which $\widehat{\mathcal{M}}$ satisfies a stronger privacy guarantee
than $\mathcal{M}$.

######  Proposition 2.

Let $\mathcal{M}$ be a mechanism that admits a weighted distinguishability
profile $\epsilon(w,\mathbf{x})$. Let $\widetilde{\mathcal{M}}$ be its
unweighted counterpart defined as
$\widetilde{\mathcal{M}}(\\{\mathbf{x}_{i}\\}_{i=1}^{n})=\mathcal{M}(\\{(1,\
\mathbf{x}_{i})\\}_{i=1}^{n})$ and
$\tilde{\epsilon}(\mathbf{x})=\epsilon(1,\mathbf{x})$ be its
distinguishability profile. Let $\epsilon$ be differentiable in $w$ and
$\epsilon^{\prime}(w,\mathbf{x})=\partial\epsilon(w,\mathbf{x})/\partial w$.
Then, there is a Poisson importance sampler $S(\cdot)$ for which the following
holds. Let $\psi$ be the distinguishability profile of $\mathcal{M}\circ S$
implied by Theorem 2. For any $\mathbf{x}\in\mathcal{X}$, if
$\epsilon^{\prime}(1,\mathbf{x})<1-e^{-\epsilon(1,\mathbf{x})}$, then
$\psi(\mathbf{x})<\tilde{\epsilon}(\mathbf{x})$.

Consequently, if the condition
$\epsilon^{\prime}(1,\mathbf{x})<1-e^{-\epsilon(1,\mathbf{x})}$ holds in a
neighborhood around the maximizer
$\mathbf{x}^{\star}=\operatorname*{arg\,max}_{\mathbf{x}\in\mathcal{X}}\tilde{\epsilon}(\mathbf{x})$,
then $\widehat{\mathcal{M}}$ satisfies DP with a strictly smaller privacy
parameter than $\mathcal{M}$. However, for the following important class of
mechanisms, $\widehat{\mathcal{M}}$ cannot satisfy a stronger privacy
guarantee than $\mathcal{M}$.

######  Proposition 3.

Let $\mathcal{M}$, $\widetilde{\mathcal{M}}$, $\epsilon$, $\epsilon^{\prime}$,
and $\tilde{\epsilon}$ be as in Proposition 2. Let $S(\cdot)$ be any Poisson
importance sampler. Let $\psi$ be the distinguishability profile of
$\mathcal{M}\circ S$ implied by Theorem 2. Let $\mathbf{x}\in\mathcal{X}$. If
$\epsilon(w,\mathbf{x})\leq w\epsilon^{\prime}(w,\mathbf{x})$ for all $w\geq
1$, then $\psi(\mathbf{x})\geq\tilde{\epsilon}(\mathbf{x})$.

For instance, the condition $\epsilon(w,\mathbf{x})\leq
w\epsilon^{\prime}(w,\mathbf{x})$ is satisfied everywhere by any profile of
the form $\epsilon(w,\mathbf{x})=f(\mathbf{x})w^{p}$, where $p\geq 1$ and $f$
is any non-negative function that does not depend on $w$. This includes the
Laplacian weighted sum mechanism discussed above, as well as the weighted DP-
Lloyd mechanism which we discuss in Section 4.

#### Privacy-optimal Sampling.

Suppose we have a target privacy guarantee $\epsilon^{\star}>0$ that we want
$\widehat{\mathcal{M}}=\mathcal{M}\circ S$ to satisfy and we know a weighted
distinguishability profile $\epsilon(w,\mathbf{x})$ of $\mathcal{M}$. What is
the smallest expected sample size $m=\sum_{i=1}^{n}q(\mathbf{x}_{i})$ we can
hope for? This can be described as an optimization problem as follows.

######  Problem 1 (Privacy-optimal sampling).

For a weighted distinguishability profile
$\epsilon\colon[1,\infty)\times\mathcal{X}\to\mathbb{R}_{\geq 0}$, a target
privacy guarantee $\epsilon^{\star}$, and a data set
$\mathcal{D}\subseteq\mathcal{X}$ of size $n$, we define the privacy-optimal
sampling problem as

$\displaystyle\min_{\mathbf{w}\in\mathbb{R}^{n}}\quad$
$\displaystyle\sum_{i=1}^{n}\frac{1}{w_{i}}$ (2a) subject to
$\displaystyle\log\mathopen{}\mathclose{{}\left(1+\frac{1}{w_{i}}\mathopen{}\mathclose{{}\left(e^{\epsilon(w_{i},\mathbf{x}_{i})}-1}\right)}\right)\leq\epsilon^{\star},$
$\displaystyle(i=1,\ldots,n),$ (2b) $\displaystyle w_{i}\geq 1,$
$\displaystyle(i=1,\ldots,n).$ (2c)

The constraint in Equation (2b) captures the requirement that $\psi$ should be
bounded by $\epsilon^{\star}$ for all $\mathbf{x}\in\mathcal{X}$, and the
constraint in Equation (2c) ensures that $1/w_{i}$ is a probability. Note
that, unless we make assumptions on the function $\epsilon$ and the target
$\epsilon^{\star}$, the problem is not guaranteed to have a solution. First,
if $\epsilon^{\star}$ is too small, the constraint in Equation (2b) might be
infeasible for some $\mathbf{x}_{i}$. Second, Equation (2b) might reach
equality infinitely often if the left hand-side oscillates, e.g., if
$\epsilon(\cdot,\mathbf{x})$ is piecewise constant. Fortunately, under mild
assumptions about $\epsilon$ and $\epsilon^{\star}$, the problem is guaranteed
to have a unique solution, and can be solved separately for each
$\mathbf{x}\in\mathcal{D}$.

######  Assumption 1.

For all $\mathbf{x}\in\mathcal{X}$,
$\epsilon^{\star}\geq\epsilon(1,\mathbf{x})$.

######  Assumption 2.

For all $\mathbf{x}\in\mathcal{X}$, there is a constant $v_{\mathbf{x}}\geq 1$
such that $\epsilon(w,\mathbf{x})>\log(1+w(e^{\epsilon^{\star}}-1))$ for all
$w\geq v_{\mathbf{x}}$.

Assumption 1 ensures that the feasible region is non-empty, because
$w_{1}=\cdots=w_{n}=1$ always satisfies the constraints, while Assumption 2
essentially states that, asymptotically, $\epsilon$ should grow at least
logarithmically fast with $w$, ensuring that the feasible region is bounded. A
simpler (but less tight) asymptotic condition would be
$\epsilon(w,\mathbf{x})>\epsilon^{\star}+\log w$. The second main result is as
follows.

######  Theorem 3.

Let Assumptions 1 and 2 be satisfied. There is a data set-independent function
$w\colon\mathcal{X}\to[1,\infty)$, such that, for all data sets
$\mathcal{D}\subseteq\mathcal{X}$, Problem 1 has a unique solution
$w^{\star}(\mathcal{D})=(w^{\star}_{1}(\mathcal{D}),\ldots,w_{n}^{\star}(\mathcal{D}))$
of the form $w_{i}^{\star}(\mathcal{D})=w(\mathbf{x}_{i})$. Furthermore, let
$\mathcal{M}$ be a mechanism that admits the distinguishability profile
$\epsilon$, and $S_{q}$ be a Poisson importance sampler for
$q(\mathbf{x})=1/w(\mathbf{x})$. Then, $\mathcal{M}\circ S_{q}$ satisfies
$\epsilon^{\star}$-DP.

Our preferred way of solving Problem 1 is to reduce it to a scalar root-
finding problem. For that, we introduce Assumption 3 which is stronger than
Assumption 2.

######  Assumption 3.

The function $\epsilon(w,\mathbf{x})$ is differentiable with respect to $w$
and the function $\exp\circ\ \epsilon$ is $\mu_{\mathbf{x}}$-strongly convex
in $w$ for all $\mathbf{x}$.

Algorithm 1 Privacy-optimal importance weights

Input: Data set $\mathcal{D}=\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\\}$,
target privacy guarantee $\epsilon^{\star}>0$, distinguishability profile
$\epsilon$, its derivative $\epsilon^{\prime}$ wrt $w$, and strong convexity
constants $\mu_{1},\ldots,\mu_{n}$

Output: Importance weights $w_{1},\ldots,w_{n}$

for $i=1,\ldots,n$ do

Define the function
$g_{i}(w)=\frac{1}{w}\mathopen{}\mathclose{{}\left(e^{\epsilon(w,\mathbf{x}_{i})}-1}\right)-\mathopen{}\mathclose{{}\left(e^{\epsilon^{\star}}-1}\right)$

$\bar{v}_{i}\leftarrow\min\\{e^{\epsilon(1,\mathbf{x}_{i})}+\mu_{i}/2,\
\epsilon^{\prime}(1,\mathbf{x}_{i})e^{\epsilon(1,\mathbf{x}_{i})}+1\\}$

$b_{i}\leftarrow 2(e^{\epsilon^{\star}}-\bar{v}_{i})/\mu_{i}+1$

if $\epsilon(1,\mathbf{x}_{i})=\epsilon^{\star}$ and
$\epsilon^{\prime}(1,\mathbf{x}_{i})<0$ then

$w_{i}\leftarrow$ Bisect $g_{i}$ with initial bracket $(1,b_{i}]$

else

$w_{i}\leftarrow$ Bisect $g_{i}$ with initial bracket $[1,b_{i}]$

end if

end for

As the following proposition shows, by using Assumptions 1 and 3, Algorithm 1
solves Problem 1 for which we can bound the number of evaluations of
$\epsilon(w,\mathbf{x})$.

######  Proposition 4.

Let Assumptions 1 and 3 be satisfied. Algorithm 1 solves Problem 1 up to
accuracy $\alpha$ with at most
$\sum_{\mathbf{x}\in\mathcal{D}}\log_{2}\lceil(e^{\epsilon^{\star}}-\bar{v}_{\mathbf{x}})/(\alpha\mu_{\mathbf{x}})\rceil$
evaluations of $\epsilon(w,\mathbf{x})$, where
$\bar{v}_{\mathbf{x}}=\min\\{{e^{\epsilon(1,\mathbf{x})}+\mu_{\mathbf{x}}/2,}\
\epsilon^{\prime}(1,\mathbf{x})e^{\epsilon(1,\mathbf{x})}+1\\}$ and
$\epsilon^{\prime}(w,\mathbf{x})=\partial/\partial w\,\epsilon(w,\mathbf{x})$.

##  4 Case Study: Differentially Private $k$-means

In this section, we apply our results on privacy amplification for importance
sampling to the DP $k$-means problem. We define a weighted version of the DP-
Lloyd algorithm, and analyze its distinguishability profile. Then, we compare
its performance experimentally to its uniformly sub-sampled counterpart. We
also compare the performance of the privacy-optimal weights to coreset-
inspired weights.

#### Weighted DP Lloyd’s Algorithm.

In order to apply importance sub-sampling to $k$-means, we first define a
weighted version of DP-Lloyd. Each iteration of DP-Lloyd consists of a
counting query and a sum query, which generalize naturally to the weighted
scenario. Specifically, for a weighted data set
$\mathcal{S}=\\{(w_{i},\mathbf{x}_{i})\\}_{i=1}^{n}$ we define the update step
to be

$\displaystyle\mathbf{c}_{j}=\frac{1}{\xi_{j}+\sum_{(w,\mathbf{x})\in\mathcal{C}_{j}}w}\mathopen{}\mathclose{{}\left(\zeta_{j}+\sum_{(w,\mathbf{x})\in\mathcal{C}_{j}}w\mathbf{x}}\right).$

Just as before, $\xi\in\mathbb{R}^{k}$ and $\zeta\in\mathbb{R}^{k\times d}$
each have iid Laplace-distributed entries with scale
$\beta_{\mathrm{count}}>0$ and $\beta_{\mathrm{sum}}>0$, respectively.

Algorithm 2 Weighted DP Lloyd’s algorithm

Input: Weighted data set $\mathcal{S}=\\{(w_{i},\mathbf{x}_{i})\\}_{i=1}^{n}$,
initial cluster centers $\mathcal{C}$, number of iterations $T$, noise scales
$\beta_{\mathrm{sum}},\beta_{\mathrm{count}}$

Output: Cluster centers $\mathbf{c}_{1},\ldots,\mathbf{c}_{k}$

for $t=1,\ldots,T$ do

Compute cluster assignments $\mathcal{C}_{1},\ldots,\mathcal{C}_{k}$, where
$\mathcal{C}_{j}=\\{\mathbf{x}_{i}\mid
j=\operatorname*{arg\,min}_{j}\|\mathbf{x}_{i}-\mathbf{c}_{j}\|^{2}\\}$

for $j=1,\ldots,k$ do

Sample $\xi_{j}\sim\operatorname{Lap}(0,\beta_{\mathrm{count}})$

Obtain $\zeta_{j}\in\mathbb{R}^{d}$ where each entry is sampled from
$\operatorname{Lap}(0,\beta_{\mathrm{count}})$

Update
$\mathbf{c}_{j}=\frac{1}{\xi_{j}+\sum_{(w,\mathbf{x})\in\mathcal{C}_{j}}w}\mathopen{}\mathclose{{}\left(\zeta_{j}+\sum_{(w,\mathbf{x})\in\mathcal{C}_{j}}w\mathbf{x}}\right)$

end for

end for

This approach is summarized in Algorithm 2 and it admits a distinguishability
profile that generalizes naturally from the $\epsilon$-DP guarantee without
sampling.

######  Proposition 5.

Algorithm 2 satisfies the weighted distinguishability profile

$\displaystyle\epsilon_{\mathrm{Lloyd}}(w,\mathbf{x})=\mathopen{}\mathclose{{}\left(\frac{1}{\beta_{\mathrm{count}}}+\frac{\|\mathbf{x}\|_{1}}{\beta_{\mathrm{sum}}}}\right)Tw.$
(3)

Note that $\epsilon_{\mathrm{Lloyd}}$ satisfies the conditions for Proposition
3. Hence, we cannot hope to improve the privacy of DP-Lloyd by using
importance sampling. We can, however, expect to obtain stronger results than
with uniform subsampling. In order to compute the privacy-optimal weights via
Algorithm 1, we need the strong convexity constant of
$\epsilon_{\mathrm{Lloyd}}$, which is readily obtained via the second
derivative:

$\displaystyle\frac{\partial^{2}}{\partial^{2}w}\exp\mathopen{}\mathclose{{}\left(\epsilon_{\mathrm{Lloyd}}(w,\mathbf{x})}\right)\geq
T^{2}\mathopen{}\mathclose{{}\left(\frac{1}{\beta_{\mathrm{count}}}+\frac{\|\mathbf{x}\|_{1}}{\beta_{\mathrm{sum}}}}\right)\exp\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(\frac{1}{\beta_{\mathrm{count}}}+\frac{\|\mathbf{x}\|_{1}}{\beta_{\mathrm{sum}}}}\right)T}\right)=:\mu.$
(4)

Besides the privacy-optimal distribution, we also consider a coreset-based
sampling distribution. We adapt the sampling distribution used in Theorem 1
slightly and propose
$q(\mathbf{x})=\lambda\frac{m}{n}+(1-\lambda)\frac{m\|\mathbf{x}\|_{1}}{n\tilde{\mathbf{x}}}$,
where $m\ll n$ is the subsample size and
$\tilde{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\|\mathbf{x}\|_{1}$ is the
average $\ell_{1}$-norm. There are three changes: (i) we assume the data set
$\mathcal{X}$ is centered, (ii) we introduce $\lambda\in[0,1]$ which yields an
uniform sampler for the choice of $\lambda=1$, and (iii) we change the
distance from $\|\cdot\|_{2}^{2}$ to $\|\cdot\|_{1}$ because the privacy of
the Laplace mechanism is based on the 1-norm. With this distribution, we have
the following $\epsilon$-DP guarantee.

######  Proposition 6.

Let $\mathcal{X}=\mathcal{B}_{1}(r)$ for some $r>0$. Let
$\mathcal{D}=\\{\mathbf{x}_{i}\\}_{i=1}^{n}\subseteq\mathcal{X}$ be a centered
data set with $\sum_{i=1}^{n}\mathbf{x}_{i}=0$, and suppose
$\tilde{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\|\mathbf{x}\|_{1}$ is known. For
any $\lambda\in[0,1]$ and $m\leq n{\tilde{\mathbf{x}}}/{r}$, let
$q(\mathbf{x})=\lambda\frac{m}{n}+(1-\lambda)\frac{m\|\mathbf{x}\|_{1}}{n\tilde{\mathbf{x}}}$.
Let $\mathcal{M}(\cdot)$ be Algorithm 2. Then,
$\mathbb{E}[|S_{q}(\mathcal{D})|]=m$ and $\mathcal{M}(S_{q}(\mathcal{D}))$
satisfies $\epsilon$-DP with

$\displaystyle\epsilon=\log\mathopen{}\mathclose{{}\left(1+\max\mathopen{}\mathclose{{}\left\\{\vartheta(A_{1},A_{2}),\
\vartheta(A_{1}^{\prime},A_{2}^{\prime})}\right\\}}\right),\quad\text{where}\quad\vartheta(u,v)=\mathopen{}\mathclose{{}\left(e^{u/v}-1}\right)v,$
(5)

and
$A_{1}=\mathopen{}\mathclose{{}\left(1/\beta_{\mathrm{count}}+r/\beta_{\mathrm{sum}}}\right)T$,
$A_{1}^{\prime}=T/\beta_{\mathrm{count}}$,
$A_{2}=m/n\mathopen{}\mathclose{{}\left(\lambda+(1-\lambda)r/\tilde{\mathbf{x}}}\right)$
and $A_{2}^{\prime}=\lambda m/n$.

Note that $A_{1}$ is simply the differential privacy guarantee of the standard
DP-Lloyd algorithm without sampling and
$A_{2}=\max_{\mathbf{x}\in\mathcal{X}}q(\mathbf{x})\leq 1$. The $\max$ in
Equation (5) arises because the distinguishability profile $\psi(\mathbf{x})$
is not necessarily monotonic in $\mathbf{x}$, but is always maximized at the
boundary of the domain, i.e., at $\|\mathbf{x}\|_{1}\in\\{0,r\\}$.

##  5 Experiments

#### Data.

We evaluate our approaches on the following real-world data sets. The _Ijcnn1_
data set was used in the IJCNN 2001 neural network
competition.111https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. It
has $n=49,990$ points in $d=22$ dimensions and we employ the same pre-
processing as Chang and Lin, (2001). _Pose_ is a subset of the Human3.6M data
(Catalin Ionescu,, 2011; Ionescu et al.,, 2014) and was used in the ECCV 2018
PoseTrack Challenge.222http://vision.imar.ro/human3.6m/challenge_open.php The
data is about 3D human pose estimation and each of the $n=35,832$ poses is
described as 3D coordinates of 16 joints. Hence, the problem is
$48$-dimensional. _MiniBooNE_ (Dua and Graff,, 2017) is a data set with
$n=130,064$ points in $d=50$ dimensions. Another data set is _KDD-Protein_
333http://osmot.cs.cornell.edu/kddcup/datasets.html, which consists of
$n=145,751$ data points in $d=74$ dimensions.

#### Setup.

The specific task we consider is $k$-means for which we use the weighted
version of DP-Lloyd as described in Algorithm 2. We fix the number of
iterations of DP-Lloyd to $T=10$ and only evaluate the setting of $k=25$
clusters. The scale parameters are set to
$\beta_{\mathrm{sum}}=\sqrt{\frac{Tr}{B}}\sqrt[3]{\frac{d}{2\rho}}$ and
$\beta_{\mathrm{count}}=\sqrt[3]{4d\rho^{2}}\beta_{\mathrm{sum}}$, where
$\rho=0.225$ and $B$ is a constant we vary between
$B\in\\{0.0001,0.001,0.01,0.1,1,3\\}$ in order to compare performance at
different privacy levels.

We set $r=\max_{i}\|\mathbf{x}_{i}\|_{1}$,
$\tilde{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\|\mathbf{x}\|_{1}$. Since
outliers cause $r$ to be large which deteriorates $\epsilon$, we first center
the data and then discard potential outliers by dropping the 2.5% of the data
points with the highest $\ell_{1}$-norms. Afterwards, we center the data
again. We evaluate the following three different importance samplers and use
various sample sizes, i.e., $m\in\\{5000,10000,20000\\}$. For the coreset-
inspired (core) sampling, the sampling distribution is
$q_{\text{core}}(\mathbf{x})=\lambda\frac{m}{n}+(1-\lambda)\frac{m\|\mathbf{x}\|_{1}}{n\tilde{\mathbf{x}}}$,
where we set $\lambda=\frac{1}{2}$. The privacy guarantee is computed via
Proposition 6. The uniform (unif) sampling uses
$q_{\text{unif}}(\mathbf{x})=m/n$ and we compute the privacy guarantee via
Proposition 6. Note that it is the same $q$ as in core but with $\lambda=1$.
For the privacy-optimal (opt) sampling, we compute
$q_{\text{priv}}(\mathbf{x})$ numerically via Algorithm 1 for the target
$\epsilon^{\star}=\mathopen{}\mathclose{{}\left(r/\beta_{\mathrm{sum}}+1/\beta_{\mathrm{count}}}\right)T$
using the strong convexity constant from Equation (4). Furthermore, we run DP-
Lloyd on the full data set.

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. In addition, we depict the 75% and 25% quartiles. Note
that the weighted version of DP-Lloyd is only used when learning the cluster
centers. For the sampling-based approaches, we re-compute the objective
function (cost) on all data after optimization and report on the total cost
scaled by the number of data points $n^{-1}$. The code is implemented in
Python using numpy (Harris et al.,, 2020). All experiments run on an Intel
Xeon machine with 28 cores with 2.60 GHz and 256 GB of memory.

Figure 1: Results on Ijcnn1, Pose, MiniBooNE, and KDD-Protein.

#### Results.

Figure 1 depicts the results. Within the figure, columns reflect the data sets
Ijcnn1, Pose, MiniBooNE, and KDD-Protein and the rows correspond to choices of
subsampling sizes $m$. The curves are obtained by varying $B$ and show the
cost of $k$-means evaluated on all data as a function of the privacy loss
$\epsilon$. Note that the $x$-axis is in log-scale, shared column-wise, and
that the optimal location is the bottom left since it yields a low cost and a
low privacy loss. The performance without subsampling is depicted as full
(blue line). Within the subsampling approaches, core (green line) consistently
outperforms unif (red line) as it yields a better cost-loss ratio. The opt
(orange line) sampler often improves upon core or performs on-par, except on
Pose data. Besides, the gap between the samplers and full closes as we
increase the subsample size $m$.

##  6 Discussion & Limitations

Ideally, our importance sampling distribution $q$ would use squared
$\ell_{2}$-norms instead of $\ell_{1}$-norms. For $\lambda=\frac{1}{2}$, we
would then have the lightweight-coreset guarantee from Theorem 1 for our
subsets. The norm change was necessary to derive a reasonable bound for the
distinguishability profile in Proposition 6. While our subsets from the
sampler core do not come with a lightweight-coreset guarantee, they perform
empirically very well due to their improved cost-$\epsilon$-loss ratio when
compared to unif. Another limitation is that we assume the data set to be
centered and that information on the norms as used in $r$ and
$\tilde{\mathbf{x}}$ is known. If unknown, those constants have to be
estimated in a suitable way.

##  7 Related work

The first differentially private version of $k$-means is introduced by Blum et
al., (2005). They propose the Sub-Linear Queries (SuLQ) framework, which, for
$k$-means, uses a noisy (Gaussian) estimate of the number of points per
cluster and a noisy sum of distances. This is also reported by Su et al.,
(2016, 2017) which extend the analysis. Other variants of differentially
private $k$-means were proposed, e.g., by Balcan et al., (2017); Huang and
Liu, (2018); Stemmer and Kaplan, (2018); Shechner et al., (2020); Ghazi et
al., (2020); Nguyen et al., (2021); Cohen-Addad et al., (2022).

Coresets are compact summaries of data sets on which learned models perform
provably competitive. Feldman et al., (2007) propose a weak coreset
construction for $k$-means clustering that samples points according to their
squared distance to the preliminary solution of an approximation. A similar
idea is proposed by Chen, (2009). Langberg and Schulman, (2010) introduce the
notion of sensitivity which measures the importance of a point for preserving
the cost over all possible solutions.

Private coresets are coresets that preserve differential privacy on their own.
Feldman et al., (2009) consider going from (non-private) coresets to private
coresets and provide an efficient algorithm to compute private coresets for
$k$-median and $k$-mean queries. A discussion regarding private coresets can
be found in Dwork, (2009). Manousakas et al., (2020) propose a Bayesian
pseudo-coreset consisting of pseudo-data, i.e., synthetic data, that fulfills
differential privacy. They consider problems such as Bayesian linear and
logistic regression. However, private and pseudo coresets are different from
our approach, which only uses sub-sampling to amplify the privacy of an
arbitrary mechanism. Related to private coresets, Ji and Elkan, (2013) release
differentially private importance weights for a public dataset. Wei et al.,
(2022) propose a differentially private variation of SGD that uses importance
sampling to reduce the sampling variance.

A differentially private selection of a certain number of _qualitative_ data
points is considered in Steinke and Ullman, (2017). Within distributed machine
learning one often faces the problem of either sharing local models or
representative data summaries (coresets). This problem is considered by Lu et
al., (2020) where they systematically compare the approaches of federated
learning and coreset-based learning in accuracy, privacy, and communication
cost. Furthermore, they propose a membership inference attack against
distributed coresets.

The concept of a distinguishability profile is somewhat related to the notions
of personalized (Jorgensen et al.,, 2015) or heterogeneous (Alaggan et al.,,
2016) privacy and local sensitivity (Nissim et al.,, 2007). In personalized DP
and heterogeneous DP, each user requires a different privacy level. Jorgensen
et al., (2015) achieve personalized DP by subsampling the data with
heterogeneous probabilities. Each user’s selection probability is chosen such
that the privacy amplification by subsampling result (Proposition 1) yields
the desired privacy level. Alaggan et al., (2016) achieve heterogeneous DP by
re-scaling the query underlying the randomized mechanism with a user-specific
factor. Both works differ in two substantial ways from our approach. First,
subsampling a data set or re-scaling the query heterogeneously generally
produces a biased estimate of the query. This bias is not accounted for in the
aforementioned works. Our approach, on the other hand, relies on importance
sampling which associates a weight with each data point, allowing the
subsequent mechanism to produce an unbiased estimate. Second, the
aforementioned works do not exploit the inherent heterogeneity of the
mechanism’s privacy guarantee. A core reason why privacy amplification by
importance sampling is powerful is that the sampling probability
$q(\mathbf{x})$ of a data point $\mathbf{x}$ can be chosen in accordance with
the distinguishability $\psi(\mathbf{x})$ it induces on the mechanism’s
output. Finally, the smooth sensitivity framework (Nissim et al.,, 2007)
introduces the notion of local sensitivity, which is a data-dependent version
of the (global) sensitivity. The local sensitivity is a function of the data
set and maximizes over all possible neighboring points $\mathbf{x}$.
Conversely, the distinguishability profile $\psi(\mathbf{x})$ is a function of
the differing point $\mathbf{x}$ and maximizes over all possible data sets.

##  8 Conclusion

We introduced privacy amplification via importance sampling. While it is
common to use data-independent random subsampling within privacy
amplification, we proposed to use a data-dependent subsampling. In this
regard, we presented general amplification results that quantify the privacy
of any arbitrary mechanism when sub-sampled via Poisson importance sampling
with any arbitrary distribution. Moreover, we derived optimal sampling
distributions for any arbitrary but fixed mechanism that minimizes the
expected sample size subject to a given privacy budget. On the example of
differentially private $k$-means clustering, we compared our privacy-optimal
sampling distribution to uniform sampling and a coreset-inspired sampling
procedure in terms of efficiency, privacy, and accuracy. On several real-world
data sets, our coreset-inspired sampling always outperformed uniform sampling
and our privacy-optimal sampling either improved upon the coreset-inspired
sampling or performed on-par.

## Acknowledgments and Disclosure of Funding

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

  * Alaggan et al., (2016) Alaggan, M., Gambs, S., and Kermarrec, A. (2016).  Heterogeneous differential privacy.  J. Priv. Confidentiality, 7(2).
  * Bachem et al., (2018) Bachem, O., Lucic, M., and Krause, A. (2018).  Scalable k-means clustering via lightweight coresets.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1119–1127. ACM.
  * Balcan et al., (2017) Balcan, M.-F., Dick, T., Liang, Y., Mou, W., and Zhang, H. (2017).  Differentially private clustering in high-dimensional euclidean spaces.  In International Conference on Machine Learning, pages 322–331. PMLR.
  * Balle et al., (2018) Balle, B., Barthe, G., and Gaboardi, M. (2018).  Privacy amplification by subsampling: Tight analyses via couplings and divergences.  In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
  * Bassily et al., (2014) Bassily, R., Smith, A., and Thakurta, A. (2014).  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464–473. IEEE.
  * Blum et al., (2005) Blum, A., Dwork, C., McSherry, F., and Nissim, K. (2005).  Practical privacy: the sulq framework.  In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 128–138.
  * Catalin Ionescu, (2011) Catalin Ionescu, Fuxin Li, C. S. (2011).  Latent structured models for human pose estimation.  In International Conference on Computer Vision.
  * Chang and Lin, (2001) Chang, C.-c. and Lin, C.-J. (2001).  IJCNN 2001 challenge: Generalization ability and text decoding.  In Proceedings of International Joint Conference on Neural Networks, volume 2, pages 1031–1036. IEEE.
  * Chen, (2009) Chen, K. (2009).  On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications.  SIAM Journal on Computing, 39(3):923–947.
  * Cohen-Addad et al., (2022) Cohen-Addad, V., Epasto, A., Mirrokni, V., Narayanan, S., and Zhong, P. (2022).  Near-optimal private and scalable $k$-clustering.  Advances in Neural Information Processing Systems, 35:10462–10475.
  * Dong et al., (2019) Dong, J., Roth, A., and Su, W. J. (2019).  Gaussian differential privacy.  CoRR, abs/1905.02383.
  * Dua and Graff, (2017) Dua, D. and Graff, C. (2017).  UCI machine learning repository.
  * Dwork, (2009) Dwork, C. (2009).  The differential privacy frontier.  In Theory of Cryptography: 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings 6, pages 496–502. Springer.
  * (14) Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. (2006a).  Our data, ourselves: Privacy via distributed noise generation.  In Vaudenay, S., editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 486–503. Springer.
  * (15) Dwork, C., McSherry, F., Nissim, K., and Smith, A. D. (2006b).  Calibrating noise to sensitivity in private data analysis.  In Halevi, S. and Rabin, T., editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer.
  * Dwork et al., (2010) Dwork, C., Rothblum, G. N., and Vadhan, S. P. (2010).  Boosting and differential privacy.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51–60. IEEE Computer Society.
  * Feldman et al., (2009) Feldman, D., Fiat, A., Kaplan, H., and Nissim, K. (2009).  Private coresets.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 361–370.
  * Feldman et al., (2007) Feldman, D., Monemizadeh, M., and Sohler, C. (2007).  A ptas for k-means clustering based on weak coresets.  In Proceedings of the twenty-third annual symposium on Computational geometry, pages 11–18.
  * Ghazi et al., (2020) Ghazi, B., Kumar, R., and Manurangsi, P. (2020).  Differentially private clustering: Tight approximation ratios.  Advances in Neural Information Processing Systems, 33:4040–4054.
  * Harris et al., (2020) Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. (2020).  Array programming with NumPy.  Nature, 585(7825):357–362.
  * Huang and Liu, (2018) Huang, Z. and Liu, J. (2018).  Optimal differentially private algorithms for k-means clustering.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 395–408.
  * Ionescu et al., (2014) Ionescu, C., Papava, D., Olaru, V., and Sminchisescu, C. (2014).  Human3.6M: Large Scale Datasets and Predictive Methods for 3D Human Sensing in Natural Environments.  IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * Ji and Elkan, (2013) Ji, Z. and Elkan, C. P. (2013).  Differential privacy based on importance weighting.  Machine Learning, 93:163–183.
  * Ji et al., (2014) Ji, Z., Lipton, Z. C., and Elkan, C. (2014).  Differential privacy and machine learning: a survey and review.  CoRR, abs/1412.7584.
  * Jorgensen et al., (2015) Jorgensen, Z., Yu, T., and Cormode, G. (2015).  Conservative or liberal? personalized differential privacy.  In Gehrke, J., Lehner, W., Shim, K., Cha, S. K., and Lohman, G. M., editors, 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015, pages 1023–1034. IEEE Computer Society.
  * Kairouz et al., (2015) Kairouz, P., Oh, S., and Viswanath, P. (2015).  The composition theorem for differential privacy.  In Bach, F. R. and Blei, D. M., editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 1376–1385. JMLR.org.
  * Kasiviswanathan et al., (2008) Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., and Smith, A. D. (2008).  What can we learn privately?  In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 531–540. IEEE Computer Society.
  * Langberg and Schulman, (2010) Langberg, M. and Schulman, L. J. (2010).  Universal $\varepsilon$-approximators for integrals.  In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 598–607. SIAM.
  * Lloyd, (1982) Lloyd, S. P. (1982).  Least squares quantization in PCM.  IEEE Trans. Inf. Theory, 28(2):129–136.
  * Lu et al., (2020) Lu, H., Liu, C., He, T., Wang, S., and Chan, K. S. (2020).  Sharing models or coresets: A study based on membership inference attack.  arXiv preprint arXiv:2007.02977.
  * Manousakas et al., (2020) Manousakas, D., Xu, Z., Mascolo, C., and Campbell, T. (2020).  Bayesian pseudocoresets.  Advances in Neural Information Processing Systems, 33:14950–14960.
  * Nguyen et al., (2021) Nguyen, H. L., Chaturvedi, A., and Xu, E. Z. (2021).  Differentially private k-means via exponential mechanism and max cover.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9101–9108.
  * Nissim et al., (2007) Nissim, K., Raskhodnikova, S., and Smith, A. D. (2007).  Smooth sensitivity and sampling in private data analysis.  In Johnson, D. S. and Feige, U., editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 75–84. ACM.
  * Shechner et al., (2020) Shechner, M., Sheffet, O., and Stemmer, U. (2020).  Private k-means clustering with stability assumptions.  In International Conference on Artificial Intelligence and Statistics, pages 2518–2528. PMLR.
  * Steinke, (2022) Steinke, T. (2022).  Composition of differential privacy & privacy amplification by subsampling.  arXiv preprint arXiv:2210.00597.
  * Steinke and Ullman, (2017) Steinke, T. and Ullman, J. (2017).  Tight lower bounds for differentially private selection.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 552–563. IEEE.
  * Stemmer and Kaplan, (2018) Stemmer, U. and Kaplan, H. (2018).  Differentially private k-means with constant multiplicative error.  Advances in Neural Information Processing Systems, 31.
  * Su et al., (2016) Su, D., Cao, J., Li, N., Bertino, E., and Jin, H. (2016).  Differentially private k-means clustering.  In Proceedings of the sixth ACM conference on data and application security and privacy, pages 26–37.
  * Su et al., (2017) Su, D., Cao, J., Li, N., Bertino, E., Lyu, M., and Jin, H. (2017).  Differentially private k-means clustering and a hybrid approach to private optimization.  ACM Transactions on Privacy and Security (TOPS), 20(4):1–33.
  * Wei et al., (2022) Wei, J., Bao, E., Xiao, X., and Yang, Y. (2022).  Dpis: An enhanced mechanism for differentially private sgd with importance sampling.  In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 2885–2899.
  * Zhu and Wang, (2019) Zhu, Y. and Wang, Y. (2019).  Poission subsampled rényi differential privacy.  In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 7634–7642. PMLR.

##  Appendix A Proofs

The appendix contains the proofs of all our theoretical results. For
completeness, we restate the theorems and propositions, as well as the
referenced assumptions and problems.

###  A.1 Theorem 2

See 2

###### Proof.

The proof is analogous to the proof of the regular privacy amplification
theorem with $\delta=0$, see, e.g., Steinke, (2022, Theorem 29). Let
$\mathcal{A}$ be any measurable subset from the probability space of
$\mathcal{M}(\mathcal{D})$. We begin by defining the functions
$P(\mathcal{Z})=\Pr\mathopen{}\mathclose{{}\left[\widehat{\mathcal{M}}(\mathcal{D})\in\mathcal{A}\mid
S_{q}(\mathcal{D})=\mathcal{Z}}\right]$ and
$P^{\prime}(\mathcal{Z})=\Pr\mathopen{}\mathclose{{}\left[\widehat{\mathcal{M}}(\mathcal{D}^{\prime})\in\mathcal{A}\mid
S_{q}(\mathcal{D}^{\prime})=\mathcal{Z}}\right]$. Let
$\mathcal{D}=\mathcal{D}^{\prime}\cup\\{\mathbf{x}\\}$ for some
$\mathbf{x}\in\mathcal{X}$. Note that

$\displaystyle\begin{split}\Pr\mathopen{}\mathclose{{}\left[\widehat{\mathcal{M}}(\mathcal{D})\in\mathcal{A}}\right]&=\mathbb{E}\mathopen{}\mathclose{{}\left[P(S_{q}(\mathcal{D}))}\right]\\\
&=(1-q(\mathbf{x}))\mathbb{E}\mathopen{}\mathclose{{}\left[P(S_{q}(\mathcal{D}))\mid\mathbf{x}\in
S_{q}(\mathcal{D})}\right]+q(\mathbf{x})\mathbb{E}\mathopen{}\mathclose{{}\left[P(S_{q}(\mathcal{D}))\mid\mathbf{x}\notin
S_{q}(\mathcal{D})}\right].\end{split}$ (6)

We can analyze the events $\mathbf{x}\in S_{q}(\mathcal{D})$ and
$\mathbf{x}\notin S_{q}(\mathcal{D})$ separately as follows. Conditioned on
the event $\mathbf{x}\notin S_{q}(\mathcal{D})$, the distributions of
$S_{q}(\mathcal{D})$ and $S_{q}(\mathcal{D}^{\prime})$ are identical since all
selection events $\gamma_{i}$ are independent:

$\displaystyle\mathbb{E}\mathopen{}\mathclose{{}\left[P(S_{q}(\mathcal{D}))\mid\mathbf{x}\notin
S_{q}(\mathcal{D})}\right]=\mathbb{E}\mathopen{}\mathclose{{}\left[P(S_{q}(\mathcal{D}^{\prime}))\mid\mathbf{x}\notin
S_{q}(\mathcal{D})}\right]=\mathbb{E}\mathopen{}\mathclose{{}\left[P^{\prime}(S_{q}(\mathcal{D}^{\prime}))}\right].$
(7)

On the other hand, conditioned on the event $\mathbf{x}\in
S_{q}(\mathcal{D})$, the sets $S_{q}(\mathcal{D})$ and
$S_{q}(\mathcal{D})\setminus\\{\mathbf{x}\\}$ are neighboring, and the
distributions of $S_{q}(\mathcal{D})\setminus\\{\mathbf{x}\\}$ and
$S_{q}(\mathcal{D}^{\prime})$ are identical. We can use the distinguishability
profile $\epsilon$ to bound

$\displaystyle\begin{split}\mathbb{E}\mathopen{}\mathclose{{}\left[P(S_{q}(\mathcal{D}))\mid\mathbf{x}\in
S_{q}(\mathcal{D})}\right]&\leq\mathbb{E}\mathopen{}\mathclose{{}\left[e^{\epsilon(1/q(\mathbf{x}),\mathbf{x})}P^{\prime}(S_{q}(\mathcal{D}^{\prime}))\mid\mathbf{x}\in
S_{q}(\mathcal{D})}\right]\\\
&=e^{\epsilon(1/q(\mathbf{x}),\mathbf{x})}\mathbb{E}\mathopen{}\mathclose{{}\left[P^{\prime}(S_{q}(\mathcal{D}^{\prime}))}\right].\end{split}$
(8)

Plugging Equations (7) and (LABEL:eq:positive-case) into Equation
(LABEL:eq:conditional-expectations) yields

$\displaystyle\Pr\mathopen{}\mathclose{{}\left[\widehat{\mathcal{M}}(\mathcal{D})\in\mathcal{A}}\right]$
$\displaystyle\leq(1-q(\mathbf{x}))\mathbb{E}\mathopen{}\mathclose{{}\left[P^{\prime}(S_{q}(\mathcal{D}^{\prime}))}\right]+q(\mathbf{x})e^{\epsilon(1/q(\mathbf{x}),\mathbf{x})}\mathbb{E}\mathopen{}\mathclose{{}\left[P^{\prime}(S_{q}(\mathcal{D}^{\prime}))}\right]$
$\displaystyle=\mathopen{}\mathclose{{}\left(1+q(\mathbf{x})\mathopen{}\mathclose{{}\left(e^{1/q(\mathbf{x})}-1}\right)}\right)\mathbb{E}\mathopen{}\mathclose{{}\left[P^{\prime}(S_{q}(\mathcal{D}^{\prime}))}\right]$
$\displaystyle=\mathopen{}\mathclose{{}\left(1+q(\mathbf{x})\mathopen{}\mathclose{{}\left(e^{1/q(\mathbf{x})}-1}\right)}\right)\Pr\mathopen{}\mathclose{{}\left[\widehat{\mathcal{M}}(\mathcal{D}^{\prime})\in\mathcal{A}}\right].$

An identical argument shows that

$\displaystyle\Pr\mathopen{}\mathclose{{}\left[\widehat{\mathcal{M}}(\mathcal{D})\in\mathcal{A}}\right]$
$\displaystyle\geq\frac{1}{1+q(\mathbf{x})\mathopen{}\mathclose{{}\left(e^{1/q(\mathbf{x})}-1}\right)}\Pr\mathopen{}\mathclose{{}\left[\widehat{\mathcal{M}}(\mathcal{D}^{\prime})\in\mathcal{A}}\right].$

∎

###  A.2 Proposition 2

See 2

###### Proof.

Let $\mathbf{x}\in\mathcal{X}$ be any data point for which
$\epsilon^{\prime}(1,\mathbf{x})<1-e^{-\epsilon(1,\mathbf{x})}$ holds. The
core idea of the proof is to treat $\psi(\mathbf{x})$ as a function of the
selection probability $q(\mathbf{x})$ and show that it is increasing at
$q(\mathbf{x})=1$. We write $\psi_{q(\mathbf{x})}(\mathbf{x})$ to make the
dependence on $q(\mathbf{x})$ explicit and define
$\omega(w)=\exp(\psi_{1/w}(\mathbf{x}))-1$. We have

$\displaystyle\frac{\mathrm{d}\omega(1)}{\mathrm{d}w}$
$\displaystyle=e^{\epsilon(1,\mathbf{x})}\mathopen{}\mathclose{{}\left(\epsilon^{\prime}(1,\mathbf{x})-1}\right)+1$
$\displaystyle<e^{\epsilon(1,\mathbf{x})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(1-e^{-\epsilon(1,\mathbf{x})}}\right)-1}\right)+1$
$\displaystyle=0,$

and, hence,
$\mathrm{d}\psi_{q(\mathbf{x})}(\mathbf{x})/\mathrm{d}q(\mathbf{x})>0$ at
$q(\mathbf{x})=1$. As a result, there is a probability $q(\mathbf{x})<1$ such
that
$\psi_{q(\mathbf{x})}(\mathbf{x})<\psi_{1}(\mathbf{x})=\tilde{\epsilon}(\mathbf{x})$.
∎

###  A.3 Proposition 3

See 3

###### Proof.

As in Proposition 2, the core idea is to treat $\psi(\mathbf{x})$ as a
function of the selection probability $q(\mathbf{x})$. We show that
$\psi(\mathbf{x})$ is non-increasing in $q(\mathbf{x})$ if the condition
$\epsilon(w,\mathbf{x})\leq w\epsilon^{\prime}(w,\mathbf{x})$ is satisfied for
all $w$.

Let $q(\mathbf{x})$ be the selection probability of $\mathbf{x}$ under $S$. We
write $\psi_{q}(\mathbf{x})$ to make the dependence on $q(\mathbf{x})$
explicit. Let $\mathbf{x}\in\mathcal{X}$ be arbitrary but fixed and define
$\omega(w)=\exp(\psi_{1/w}(\mathbf{x}))-1$. We have

$\displaystyle\frac{\mathrm{d}\omega(w)}{\mathrm{d}w}$
$\displaystyle=\frac{e^{\epsilon(w,\mathbf{x})}\mathopen{}\mathclose{{}\left(w\epsilon^{\prime}(w,\mathbf{x})-1}\right)+1}{w^{2}}$
$\displaystyle\geq\frac{e^{\epsilon(w,\mathbf{x})}\mathopen{}\mathclose{{}\left(\epsilon(w,\mathbf{x})-1}\right)+1}{w^{2}}$
$\displaystyle\geq\frac{\mathopen{}\mathclose{{}\left(\epsilon(w,\mathbf{x})+1}\right)\mathopen{}\mathclose{{}\left(\epsilon(w,\mathbf{x})-1}\right)+1}{w^{2}}$
$\displaystyle\geq\frac{\epsilon(w,\mathbf{x})^{2}}{w^{2}}$ $\displaystyle\geq
0,$

where we used the assumption $\epsilon(w,\mathbf{x})\leq
w\epsilon^{\prime}(w,\mathbf{x})$ in the first inequality and the fact that
$e^{z}\geq z+1$ for all $z\geq 0$ in the second inequality. As a result,
$\omega$ is minimized at $w=1$ and, hence, $\psi_{q}$ is minimized at
$q(\mathbf{x})=1$. To complete the proof, observe that
$\psi_{q}(\mathbf{x})=\tilde{\epsilon}(\mathbf{x})$ for $q(\mathbf{x})=1$. ∎

###  A.4 Theorem 3

See 1 See 1 See 2 See 3

See 3

###### Proof.

Since the objective is additive over $w_{i}$ and each constraint only affects
one $w_{i}$, we can consider each $w_{i}$ separately. An equivalent
formulation of the problem is

$\displaystyle\max_{w_{i}}\quad$ $\displaystyle w_{i}$ subject to
$\displaystyle\log\mathopen{}\mathclose{{}\left(1+\frac{1}{w_{i}}\mathopen{}\mathclose{{}\left(e^{\epsilon(w_{i},\mathbf{x}_{i})}-1}\right)}\right)\leq\epsilon^{\star}$
$\displaystyle w_{i}\geq 1.$

Assumption 1 guarantees that the feasible region is bounded and Assumption 2
guarantees that it is non-empty. Since the objective is strictly monotonic,
the solution must be unique. ∎

###  A.5 Proposition 4

See 4

Before beginning the proof, we state the definition of strong convexity for
completeness.

######  Definition 7 (Strong convexity).

Let $\mu>0$. A differentiable function $f:\mathbb{R}^{d}\to\mathbb{R}$ is
$\mu$-strongly convex if

$\displaystyle f(v)\geq f(u)+\nabla
f(u)^{\mkern-1.5mu\mathsf{T}}(v-u)+\frac{\mu}{2}\|v-u\|_{2}^{2}\qquad\text{for
all $u,v\in\mathbb{R}^{d}$}.$ (9)

###### Proof of Proposition 4.

First, we show that Assumption 3 implies Assumption 2. That is, we want to
find a value $v_{i}$ for each $i$ such that all $w_{i}\geq v_{i}$ are
infeasible. For some fixed $i$, define $g(w)=\epsilon(w,\mathbf{x}_{i})$ and
$g^{\prime}(w)=\frac{\mathrm{d}}{\mathrm{d}w}g(w)$. We apply the strong
convexity condition from Equation (9) to $\exp\circ\,g$ at $u=1$ and $v=w$:

$\displaystyle e^{g(w)}$ $\displaystyle\geq
e^{g(1)}+g^{\prime}(1)e^{g(1)}(w-1)+\frac{\mu_{i}}{2}\|w-1\|_{2}^{2}$
$\displaystyle\frac{1}{w}\mathopen{}\mathclose{{}\left(e^{g(w)}-1}\right)$
$\displaystyle\geq\frac{\mu}{2}w+\mathopen{}\mathclose{{}\left(e^{g(1)}-g^{\prime}(1)e^{g(1)}+\frac{\mu}{2}-1}\right)\frac{1}{w}+g^{\prime}(1)e^{g(1)}-\mu$
$\displaystyle\frac{1}{w}\mathopen{}\mathclose{{}\left(e^{g(w)}-1}\right)$
$\displaystyle\geq b_{1}w^{1}+b_{0}w^{0}+b_{-1}w^{-1}$

for appropriately defined constants $b_{1}$, $b_{0}$, and $b_{-1}$. We need to
distinguish two cases, based on the sign of $b_{-1}$.

#### Case 1: $b_{-1}<0$.

In this case, we have $b_{-1}w^{-1}\geq b_{-1}$ for all $w\geq 1$. A
sufficient condition for infeasibility is

$\displaystyle b_{1}w+b_{0}+b_{-1}$ $\displaystyle\geq e^{\epsilon^{\star}}-1$
$\displaystyle w$
$\displaystyle\geq\frac{e^{\epsilon^{\star}}-1-b_{0}-b_{-1}}{b_{1}}$
$\displaystyle w$
$\displaystyle\geq\frac{e^{\epsilon^{\star}}-e^{g(1)}+\mu/2}{\mu/2}$
$\displaystyle w$ $\displaystyle\geq
2\mathopen{}\mathclose{{}\left(\frac{e^{\epsilon^{\star}}-e^{g(1)}-\mu/2}{\mu}+1}\right).$

#### Case 2: $b_{-1}\geq 0$.

In this case, we have $b_{-1}w^{-1}\geq 0$. Analogously to Case 1, the
condition for infeasibility is

$\displaystyle b_{1}w+b_{0}$ $\displaystyle\geq e^{\epsilon^{\star}}-1$
$\displaystyle w$
$\displaystyle\geq\frac{e^{\epsilon^{\star}}-1-b_{0}}{b_{1}}$ $\displaystyle
w$
$\displaystyle\geq\frac{e^{\epsilon^{\star}}-g^{\prime}(1)e^{g(1)}+\mu-1}{\mu/2}$
$\displaystyle w$ $\displaystyle\geq
2\mathopen{}\mathclose{{}\left(\frac{e^{\epsilon^{\star}}-g^{\prime}(1)e^{g(1)}-1}{\mu}+1}\right).$

We can summarize the two cases by defining

$\displaystyle
v_{i}=2\mathopen{}\mathclose{{}\left(\frac{e^{\epsilon^{\star}}-\bar{v}_{i}}{\mu}+1}\right),\quad\text{where}\quad\bar{v}_{i}=\min\mathopen{}\mathclose{{}\left\\{e^{g(1)}+\frac{\mu}{2},\
g^{\prime}(1)e^{g(1)}+1}\right\\}.$

Then, $v_{i}$ is the desired constant for Assumption 2.

Having established that the optimal solution $w^{\star}_{i}$ is in the
interval $[1,v_{i}]$, it remains to show that it can be found via bisection
search. Bisection finds a solution to

$\displaystyle\log\mathopen{}\mathclose{{}\left(1+\frac{1}{w}\mathopen{}\mathclose{{}\left(e^{g(w)}-1}\right)}\right)=\epsilon^{\star},$

or, equivalently,

$\displaystyle
e^{g(w)}=w\mathopen{}\mathclose{{}\left(e^{\epsilon^{\star}}-1}\right)+1.$
(10)

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: $g(1)=\epsilon^{\star}$ and $g^{\prime}(1)<1-e^{-g(1)}$

In this case, there is a neighborhood around $w=1$ in which we have
$e^{g(w)}<w\mathopen{}\mathclose{{}\left(e^{\epsilon^{\star}}-1}\right)+1$.
This implies that there are two solutions to Equation (10), one at $w=1$ and
one in $w\in(1,v_{i}]$. The latter is the desired solution.

#### Case 2: $g(1)<\epsilon^{\star}$ or $g^{\prime}(1)\geq 1-e^{-g(1)}$

In this case, either condition guarantees that there is exactly one solution
to Equation (10) in $w\in[1,v_{i}]$. With the first condition, it follows from
the convexity of $\exp\circ\,g$. If the first condition is not met but the
second is, then we have $e^{g(w)}\geq
w\mathopen{}\mathclose{{}\left(e^{\epsilon^{\star}}-1}\right)+1$ for all
$w\geq 1$. Then, the uniqueness follows from strong convexity.

The two cases are implemented by the if-condition in Algorithm 1. ∎

###  A.6 Proposition 5

See 5

###### Proof.

The weighted DP-Lloyd algorithm consists of $T$ weighted sum mechanisms and
$T$ weighted count mechanisms. We analyze the weighted distinguishability
profile of each mechanism separately. Let
$\mathcal{D}=\\{(w_{i},\mathbf{x}_{i})\\}_{i=1}^{n}\cup\\{(w_{0},\mathbf{x}_{0})\\}$
and $\mathcal{D}^{\prime}=\\{(w_{i},\mathbf{x}_{i})\\}_{i=1}^{n}$ be two
neighboring data sets. Let
$\mathcal{M}_{\text{sum}}(\\{(w_{i},\mathbf{x}_{i})\\}_{i=1}^{n})=\sum_{i=1}^{n}w_{i}g(\mathbf{x}_{i})+\zeta_{\text{sum}}$
be a weighted sum mechanism for some function $g:\mathcal{X}\to\mathcal{Y}$,
where $\zeta_{\text{sum}}$ is a random vector whose entries are independently
$\text{Laplace}(0,\beta_{\text{sum}})$ distributed and $\mathcal{Y}$ is a
subset of $\mathbb{R}^{d}$. Let
$\mathcal{M}_{\text{count}}(\\{(w_{i},\mathbf{x}_{i})\\}_{i=1}^{n})=\sum_{i=1}^{n}w_{i}h(\mathbf{x}_{i})+\zeta_{\text{count}}$
be a weighted count mechanism for some function
$h:\mathcal{X}\to\\{z\in\\{0,1\\}^{k}\mid\|z\|=1\\}$, where
$\zeta_{\text{sum}}$ is a random vector whose entries are independently
$\text{Laplace}(0,\beta_{\text{sum}})$ distributed. Let $f_{\text{sum}}$ and
$f^{\prime}_{\text{sum}}$ be the probability density functions of
$\mathcal{M}_{\text{sum}}(\mathcal{D})$ and
$\mathcal{M}_{\text{sum}}(\mathcal{D}^{\prime})$, respectively. We have

$\displaystyle\mathopen{}\mathclose{{}\left|\log\frac{f_{\text{sum}}(y)}{f^{\prime}_{\text{sum}}(y)}}\right|$
$\displaystyle=\mathopen{}\mathclose{{}\left|\log\frac{\frac{1}{2\beta_{\text{sum}}}\exp\mathopen{}\mathclose{{}\left(-\|y-\sum_{i=0}^{n}w_{i}g(\mathbf{x}_{i})\|_{1}/\beta_{\mathrm{sum}}}\right)}{\frac{1}{2\beta_{\text{sum}}}\exp\mathopen{}\mathclose{{}\left(-\|y-\sum_{i=1}^{n}w_{i}g(\mathbf{x}_{i})\|_{1}/\beta_{\mathrm{sum}}}\right)}}\right|$
$\displaystyle\leq\frac{\|\sum_{i=0}^{n}w_{i}g(\mathbf{x}_{i})-\sum_{i=1}^{n}w_{i}g(\mathbf{x}_{i})\|_{1}}{\beta_{\mathrm{sum}}}$
$\displaystyle=\frac{w_{0}\|g(\mathbf{x}_{0})\|_{1}}{\beta_{\mathrm{sum}}}$

and, analogously,
$\mathopen{}\mathclose{{}\left|\log(f^{\prime}_{\text{sum}}(y)/f_{\text{sum}}(y))}\right|\leq
w_{0}\|g(\mathbf{x}_{0})\|_{1}/\beta_{\mathrm{sum}}$. Hence,
$\mathcal{M}_{\text{sum}}$ satisfies the weighted distinguishability profile
$\epsilon_{\text{sum}}(w,\mathbf{x})=w\|g(\mathbf{x})\|_{1}/\beta_{\mathrm{sum}}$.
Note that $\mathcal{M}_{\text{count}}$ is a special case of a weighted sum
mechanism where $\|h(\mathbf{x})\|_{1}=1$ for all $\mathbf{x}$, therefore it
satisfies the weighted distinguishability profile
$\epsilon_{\text{count}}(w,\mathbf{x})=w/\beta_{\mathrm{count}}$. The result
then follows by adaptive composition. ∎

###  A.7 Proposition 6

See 6

###### Proof.

In order to obtain a $\epsilon$-DP guarantee for $\widehat{\mathcal{M}}$, we
maximize its distinguishability profile $\psi(\mathbf{x})$ over the domain
$\mathbf{x}\in\mathcal{B}_{1}(r)$. The key observation is that
$e^{\psi(\mathbf{x})}-1$ is a convex function in $\|\mathbf{x}\|_{1}$, and,
hence, $\psi(\mathbf{x})$ is maximized when $\|\mathbf{x}\|_{1}$ is at one of
the endpoints of the interval $[0,r]$.

We begin by applying Theorem 3, which states that $\widehat{\mathcal{M}}$
admits the distinguishability profile

$\displaystyle\psi(\mathbf{x})=\log\mathopen{}\mathclose{{}\left(1+\mathopen{}\mathclose{{}\left(e^{\epsilon\mathopen{}\mathclose{{}\left(\frac{1}{q(\mathbf{x})},\mathbf{x}}\right)}-1}\right)q(\mathbf{x})}\right),$

where
$\epsilon(w,\mathbf{x})=\mathopen{}\mathclose{{}\left(\frac{1}{\beta_{\mathrm{count}}}+\frac{\|\mathbf{x}\|_{1}}{\beta_{\mathrm{sum}}}}\right)Tw$
and
$q(\mathbf{x})=\lambda\frac{m}{n}+(1-\lambda)\frac{m\|\mathbf{x}\|_{1}}{n\tilde{\mathbf{x}}}$.
Next, we define the function $\theta:[0,r]\to\mathbb{R}_{\geq 0}$ by

$\displaystyle\theta(z)=\mathopen{}\mathclose{{}\left(\exp\mathopen{}\mathclose{{}\left(\frac{a+tz}{b+sz}}\right)-1}\right)\mathopen{}\mathclose{{}\left(b+sz}\right),$

where $a=T/\beta_{\mathrm{count}}$, $b=\lambda m/n$,
$t=T/\beta_{\mathrm{sum}}$, and $s=(1-\lambda)m/(n\tilde{\mathbf{x}})$. We can
see that $\theta$ is convex, because its second derivative

$\displaystyle\frac{\mathrm{d}^{2}\theta(z)}{\mathrm{d}z^{2}}=\frac{(as-
bt)^{2}\exp(\frac{a+tz}{b+sz})}{(b+sz)^{3}}$

is non-negative, since $b$ and $s$ are non-negative. As a result, $\theta$ is
maximized at one of the endpoints of the interval $[0,r]$. Note that, for any
$\mathbf{x}\in\mathcal{B}_{1}(r)$, we have
$e^{\psi(\mathbf{x})}-1=\theta(\|\mathbf{x}\|_{1})$. Thus, any maximizer of
$\theta$ is also a maximizer of $\psi$. Putting all things together, we
conclude

$\displaystyle\theta(\|\mathbf{x}\|_{1})$
$\displaystyle\leq\max\mathopen{}\mathclose{{}\left\\{\theta(0),\
\theta(r)}\right\\}$ $\displaystyle\theta(\|\mathbf{x}\|_{1})$
$\displaystyle\leq\max\mathopen{}\mathclose{{}\left\\{\vartheta(a,\,b),\
\vartheta(a+tr,\,b+sr)}\right\\}$ $\displaystyle\theta(\|\mathbf{x}\|_{1})$
$\displaystyle\leq\max\mathopen{}\mathclose{{}\left\\{\vartheta(A_{1}^{\prime},\,A_{2}^{\prime}),\
\vartheta(A_{1},\,A_{2})}\right\\}$ $\displaystyle\psi(\mathbf{x})$
$\displaystyle\leq\log\mathopen{}\mathclose{{}\left(1+\max\mathopen{}\mathclose{{}\left\\{\vartheta(A_{1},\,A_{2}),\
\vartheta(A_{1}^{\prime},\,A_{2}^{\prime})}\right\\}}\right),$

where $\vartheta,A_{1},A_{1}^{\prime},A_{2},A_{2}^{\prime}$ are as defined in
the statement of the proposition. ∎