arXiv:1609.03251v1 [cs.DS] 12 Sep 2016

Postprocessing for Iterative Differentially Private Algorithms

Jaewoo Lee
Penn State University, University Park, PA 16801

JLEE @ CSE . PSU . EDU

Daniel Kifer
Penn State University, University Park, PA 16801

DKIFER @ CSE . PSU . EDU

Abstract
Iterative algorithms for differential privacy run
for a fixed number of iterations, where each iteration learns some information from data and
produces an intermediate output. However, the
algorithm only releases the output of the last iteration, and from which the accuracy of algorithm is judged. In this paper, we propose a postprocessing algorithm that seeks to improve the
accuracy by incorporating the knowledge on the
data contained in intermediate outputs.

1. Introduction
When designing an iterative algorithm for differential privacy, fully utilizing the information privately learned from
data is crucial to the success. Suppose we have a simple
algorithm A that calls the function K(D, θt−1 ) T times in
a loop and returns θT as the final output, where D ∈ X N
is the input dataset and θt = K(D, θt−1 ) is an intermediate
output at the tth iteration. A large class of machine learning algorithms, including clustering, classification, and regression, can be written in this form, where K(D, θt ) minimizes some objective function and returns θt+1 . By the
composition theorem (Dwork & Roth, 2014), if the function K satisfies T -differential privacy, the algorithm A becomes -differentially private. At each iteration t, the algorithm extracts some information θt from the given dataset
D using the privacy budget of /T , but it only releases the final output θT (thus, the accuracy of the algorithm is largely
dependent on the magnitude of noise at the final iteration).
In this paper, we ask the following question: “Can we
improve the accuracy of the final output θT by incorporating the knowledge contained in the intermediate outputs θ1 , . . . , θT −1 ?” Recent studies have shown that postprocessing algorithms that make inferences on the original

TPDP 2016 ICML Workshop, New York, NY, USA

data from noisy outputs can significantly improve the accuracy of the results (Lee et al., 2015; Hay et al., 2010; Lin
& Kifer, 2013). The main source of improvements comes
from enforcing consistency constraints, a set of (hard) syntactic conditions that hold true for the original data. Inspired by these post-processing algorithms, we view the intermediate outputs θ1 , . . . , θT −1 as soft constraints on our
estimates (i.e., the original data). Note that the privacy
guarantee of A is not degraded by this post-processing. as
long as it doesn’t rely on the randomness of A.
Consider a differentially private algorithm A that generates a sequence of noisy statistics {θ̃1 , . . . , θ̃T } such that
θ̃t = K(D, θ̃t−1 ) + Y , where Y is a random variable representing the noise added for privacy. Our goal is to estimate
b from which θ̃1 , . . . , θ̃T are most likely to be
a dataset D
b a new estimator
generated. Once we have estimated D,
b without
θ̂ can be obtained by repeatedly running K on D
noise (contrast this to θ̃T produced with noise and using
b
fixed number of iterations). Informally, we try to find D
b θ̃t ) for t = 1, . . . , T . We note
such that K(D, θ̃t ) ≈ K(D,
b could be different from that of the origthat the size of D
inal dataset, N ; we only require intermediate outputs of K
on both datasets are similar. However, it is still challenging to efficiently explore the space of all possible datasets.
To this end, we propose to use MCMC method with carefully designed proposal distribution. The proposed algorithm builds a Markov chain over the space of all possible
datasets and makes use of noisy statistics to efficiently propose the next state. Given a dataset Dt , the proposed algorithm samples a new dataset D0 and determines whether
to accept or reject the dataset by considering the ratio of
P(θ̃1 . . . , θ̃T | D0 ) to P(θ̃1 , . . . , θ̃T | Dt ), i.e., MetroplisHastings step. While doing so, it keeps track of the best
scoring dataset.
In this paper, we instantiate this post-processing algorithm
in the context of K-means clustering. The contributions of
this paper are as follows:
• We propose a general framework for post-processing a
sequence of noisy private outputs, which improves the

Postprocessing for Iterative Differentially Private Algorithms

Algorithm 1 DP-KMEANS algorithm
Input: data D, # of clusters K, # of iterations T
(0)
(0)
Initialize c1 , · · · , cK
for t = 1 to T do
for j = 1 to
o
n K do
(t)
2
Bj = xi : j = arg min k kxi − ck k2

(t)
(t)
ñj ← |Bj | + Lap 2T

P


(t)
2T d
s̃j ←
xi ∈Bj xi + Lap

.
(t)
(t)
(t)
cj ← s̃j ñj

the Laplace noise to the average to ensure privacy.
PrivGene (Zhang et al., 2013) is a genetic algorithm based
framework for differentially private model fitting. Starting from a set of randomly chosen solutions, it iteratively
improves the quality of candidate solutions. To be specific, the algorithm starts with a candidate parameter set
Ω, initialized with random vectors. At each iteration, Ω is
enriched by adding offsprings (new candidate parameters),
generated using crossover and mutate operations on existing parameters. Then, the algorithm selects and maintains
a fixed number of parameters with best fitting scores using
exponential mechanism.

accuracy by incorporating intermediate results into the
process.
• We applied our framework to K-means clustering problem and introduce an efficient proposal distribution that
yields low rejection rate.
• Extensive empirical evaluations on both synthetic and
real datasets are provided to validate our proposed approach.

2. Related Works
We discuss differentially private algorithms that can be applied to the K-means problem. The first algorithm is DPKMEANS introduced in (Blum et al., 2005; McSherry,
2009). Each step of the algorithm is descripbed in Algorithm 1. The algorithm is almost identical to its non-private
counterpart, Lloyd’s algorithm, with two differences. First,
the algorithm takes a positive integer T as input and is only
run for T iterations. This is to split the given privacy budget
 into each iteration. Second, the centroid update is done by
using noisy sum and noisy count. The use of noisy statistics generated by the Laplace mechanism ensures that each
update is differentially private.
(t)

(t)

It is easy to see that the sensitivity of (n1 , . . . , nK ) is
1 as adding or removing one data point can change the
size of one cluster by 1. Assuming X is the unit L1 -ball
(t)
(t)
(i.e., kxi k1 ≤ 1), the sensitivity of (s1 , . . . , sK ) is also
1. Therefore, together with
 the argument of composition
theorem, adding Lap 2T
to sum and count ensures each

iteration satisfies /T -differential privacy.
GUPT (Mohan et al., 2012) is a general-purpose system that implements the “sample and aggregate” framework (Nissim et al., 2007). Let f be a function on a
database. In the context of this work, f is the K-means
clustering algorithm, which takes a database as input and
returns K centroids. Given a dataset D, GUPT first partitions D into ` disjoint blocks, say T1 , . . . , T` , and applies
f on each block Ti . The final output of GUPT is computed
by averaging the outputs f (Ti ) from each block and adding

Recently, Su et al. proposed EUGkM (Su et al., 2015), a
non-interactive grid based algorithm for K-means clustering. The main idea is to divide multi-dimensional space
into M rectangular grid cells. For each grid cell, it releases
a pair (ci , ni ) using the Laplace mechanism, where ci and
ni are the center and the noisy count of data points in the
cell, respectively. Note that noise is only added to the count
ni as releasing ci has no privacy implication. Given a set
of pairs S = {(ci , ni ) : i = 1, . . . , M }, EUGkM considers
there are ni data points at ci , and it applies (non-private) Kmeans algorithm on S. They also proposed hybrid method
which combines EUGkM with DP-KMEANS.

3. Postprocessing for K-means
In this section, we describe the proposed post-processing
framework in the context of K-means where the algorithm
releases a sequence of noisy cluster sums and sizes.
3.1. Inference on Centroids
(0)

(0)

Given the K initial centroids c1 , . . . , cK (chosen independent of D), let S = hθ̃1 , . . . , θ̃T i be the sequence
of (noisy) outputs generated by running Algorithm 1 for
(t)
(t)
(t)
(t)
T iterations, where θ̃t = (s̃1 , . . . , s̃K , ñ1 , . . . , ñK )
for t = 1, · · · , T . Notice that (noisy) cluster centroids
(t)
(t)
c1 , . . . , cK are completely determined by θ̃t . We abuse
notation and use θ̃t to denote both noisy statistics and K
centroids at iteration t. Let S(D, θ) and N (D, θ) be the
functions that return the sum and the number of data points
in each partition determined by the given centroids θ.
Our goal is to make an inference on the cluster centroids
c1 , . . . , cK based on the information S we learned privately from D. We do this by simulating datasets and
evaluating the likelihood of the observed noisy statistics
S under each dataset. Once a dataset that maximizes the
likelihood of S is found, new estimates for the cluster centroids can be derived by running a non-private K-means
algorithm (possibly with multiple random restarts) on the

Postprocessing for Iterative Differentially Private Algorithms

distribution that is far from π will have a high rejection rate
and result in slow convergence.

dataset. The log-likelihood is defined by:
(1)

(T )

(1)

(T )

ln P[S | D] = ln P[s̃1 , . . . , s̃K , ñ1 , . . . , ñK | D]
h
i
XT 
(t)
(t)
ln P s̃1 , . . . , s̃K S(D, θ̃t−1 )
=
t=1
h
i
(t)
(t)
+ ln P ñ1 , . . . , ñK N (D, θ̃t−1 )

It is shown that K-means algorithm can be thought as a special case of Gaussian Mixture Model (GMM), with means
equal to centroids and a common covariance set to δI for
(t)
(t)
(t)
(t)
small δ > 0. Given θt = (s̃1 , . . . , s̃K , ñ1 , . . . , ñK ), our
proposal distribution is defined to be a mixture of GausT X
K
X
(t)
(t)
∝
s̃k − Sk (D, θ̃t−1 ) + ñk − Nk (D, θ̃t−1 ) , sians:
K


X
1
1
(t)
t=1 k=1
q(x) =
ωk N x; ck , δI ,
(1)
k=1

where the subscript k in Sk (D, θ̃t−1 ) and Nk (D, θ̃t−1 ) represent the sum and number of data points in the k th cluster,
respectively.

where ωk = ñk

3.2. Imposing Consistency

Given the current dataset D(τ ) , a new dataset D0 is proposed by randomly choosing a data point xi from D and
replacing it with a new point x0 sampled from the proposal
distribution q. The sampling of x0 is done as follows:

The accuracy of noisy output S can be improved by imposing consistency constraints, using the algorithm proposed
(t)
(t)
in (Lee et al., 2015). Suppose ŝk and n̂k are new esti(t)
(t)
mates for s̃k and ñk , respectively. It is clear that they
should satisfy the following constraints:
XK
k=1
XK
k=1

(1)

XK

(1)

k=1
XK

ŝk =
n̂k =

k=1

(2)

ŝk = . . . =
(2)

XK

n̂k = . . . =

(T )
ŝ ,
k=1 k
XK
(T )
n̂ ,
k=1 k

and

(t)

n̂k ≥ 0 for all k = 1, . . . , K and t = 1, . . . , T .
For clear semantics and better readability, in the following
(t)
(t)
we continue to use the notation s̃k and ñk , but they represent the post-processed values.
3.3. Simulation via MCMC
The proposed algorithm makes use of approximate sampling method to find a dataset under which the likelihood
of S is maximized. Using MCMC, it samples datasets from
the approximate posterior distribution P(D | S) and evaluates the likelihood, while keeping track of the best solution.
The target distribution is
 X
XK
T
(t)
π(D) = exp −
 ks̃k − Sk (D, θ̃t−1 )k1
t=1
k=1 S

(t)
+ N kñk − Nk (D, θ̃t−1 )k1 ,
where S and N correspond to the privacy budgets for noisy
cluster sums and sizes.1
Proposal distribution The Metropolis-Hastings (MH)
algorithm requires choice of proposal distribution, and the
convergence of Markov chain to its stationary distribution
π is greatly dependent on that choice. The use of a proposal
1

For simplicity, we assume S = N .

(t)

.P

K
i=1

(t)

ñi

(t)

(t)

(t)

and ck = s̃k /ñk .

(i) choose an integer t randomly from {1, 2, . . . , T }.
(ii) sample z | t ∼ Cat (K, ω1 , . . . , ωK ).

I(z=k)
QK
(t)
(iii) sample x0 | z, t ∼ k=1 N ck , δI
.
In the above, Cat (K, ω1 , . . . , ωK ) represents the Categorical distribution having possible values in {1, . . . , K}, each
with probability mass ωk for k = 1, . . . , K. I(z = k) is an
indicator function whose value is 1 if z = k and 0 otherwise.
MH Algorithm Given D(τ ) , the proposed dataset D0 of
next state (τ + 1) is accepted with probability


π(S | D0 ) q(x | x0 )
,
1
.
A(D(τ ) , D0 ) = min
π(S | D(τ ) ) q(x0 | x)
Without loss of generality, suppose a data point x is removed from the ith cluster and a new data point x0 is added
to the j th cluster at time τ . Then we have
ln π(S | D0 ) − ln π(S | D(τ ) )
=−
+

T
X
(t)
(t)
ks̃i − Si (D0 , θ̃t−1 )k1 − ks̃i − Si (D(τ ) , θ̃t−1 )k1
t=1
(t)
ks̃j

(t)

− Sj (D0 , θ̃t−1 )k1 − ks̃j − Sj (D(τ ) , θ̃t−1 )k1

(t)

(t)

(t)

(t)

+ |ñi − Ni (D0 , θ̃t−1 )| − |ñi − Ni (D(τ ) , θ̃t−1 )|
+ |ñj − Nj (D0 , θ̃t−1 )| − |ñj − Nj (D(τ ) , θ̃t−1 )| .
We note that S(D0 , θ̃t−1 ) and N (D0 , θ̃t−1 ) can be calculated from S(D(τ ) , θ̃t−1 ) and N (D(τ ) , θ̃t−1 ), respectively.
The MH correction term is given by
(t)

(t)

q(x)
q(x | z, t)q(z = i)q(t)
ñ N (x; ci , δI)
=
= (ti0 )
.
0
0
0
0
0
0
(t0 )
q(x )
q(x | z , t )q(z = j)q(t )
ñj N (x0 ; cj , δI)

Postprocessing for Iterative Differentially Private Algorithms

of the final clusterings on all datasets, except on the Lifesci
dataset. On S1 and Tiger datasets, huge improvements in
WCSS were observed when  = 0.05.

Table 1. Datasets
DATASETS
S1
TIGER
G OWALLA
I MAGE
A DULT ( NUMERIC )
L IFESCI

SIZE

N

5,000
16,281
107,021
34,112
48,842
27,733

DIMENSION

2
2
2
3
6
10

d

K
15
2
5
3
5
3

The initial state D(0) is initialized with K centroids at the
(T )
(T )
last iteration. It consists of ñk data points at ck for
k = 1, . . . , K.

4. Experiments
In this section, the performance of the proposed postprocessing algorithm is evaluated over both synthetic and
real datasets. We note that our goal is not to develop a
better private algorithm for K-means; rather, we seek to
improve the accuracy of iterative differentially private algorithms in general by taking intermediate results into account. Given K partitions β1 , . . . , βK and their centroids
c1 , . . . , cK , the quality of clustering is measured by the
sum of squared distance between data points and their nearest centroids, within cluster sum of squares (WCSS); it is
the objective function of K-means problem.
W CSS =

K X
X

2

kx − ck k2

k=1 x∈βk

For the experiments, we used 6 external datasets. For
all datasets, the domain of each attribute is normalized to
[−1, 1] and then projected onto L1 -ball. The characteristics of datasets used in our experiments are summarized in
Table 1. For each dataset, we run DP-KMEANS (DPKM)
and the proposed method (MCMC) 10 times and report the
averaged WCSS. The performance of K-means algorithm
is largely dependent on the choice of initial centroids, it is
important to carefully select them. As in (Su et al., 2015),
K initial centroids are chosen independent of data such that
pairwise distance between centroids are greater than some
given constant.
Throughout the experiments, the number of iterations T for
DPKM is fixed to 5. For the proposed algorithm, the length
of Markov chain is fixed to 30,000 and the value of δ, the
variance of Gaussian component in the proposal distribution, is set to 0.001.
Figure 1 shows the performance of our post-processing algorithm for different values of . The value of  ranges from
0.05 to 1.0. The proposed algorithm improves the accuracy

Acknowledgement
This research was supported by NSF grant 1228669.

References
Blum, Avrim, Dwork, Cynthia, McSherry, Frank, and Nissim, Kobbi. Practical privacy: The sulq framework. In
PODS, 2005.
Dwork, Cynthia and Roth, Aaron. The algorithmic foundations of differential privacy. Foundations and Trends R
in Theoretical Computer Science, 9(3–4), 2014.
Hay, Michael, Rastogi, Vibhor, Miklau, Gerome, and Suciu, Dan. Boosting the accuracy of differentially private
histograms through consistency. Proc. VLDB Endow., 3
(1-2):1021–1032, September 2010. ISSN 2150-8097.
Lee, Jaewoo, Wang, Yue, and Kifer, Daniel. Maximum
likelihood postprocessing for differential privacy under
consistency constraints. In KDD, 2015.
Lin, Bing-Rong and Kifer, Daniel. Information preservation in statistical privacy and bayesian estimation of
unattributed histograms. In SIGMOD, 2013.
McSherry, Frank D. Privacy integrated queries: An extensible platform for privacy-preserving data analysis. In
SIGMOD, 2009.
Mohan, Prashanth, Thakurta, Abhradeep, Shi, Elaine,
Song, Dawn, and Culler, David. Gupt: Privacy preserving data analysis made easy. In SIGMOD, 2012.
Nissim, Kobbi, Raskhodnikova, Sofya, and Smith, Adam.
Smooth sensitivity and sampling in private data analysis.
In STOC, 2007.
Su, D., Cao, J., Li, N., Bertino, E., and Jin, H. Differentially Private k-Means Clustering. ArXiv e-prints, April
2015.
Zhang, Jun, Xiao, Xiaokui, Yang, Yin, Zhang, Zhenjie,
and Winslett, Marianne. Privgene: Differentially private model fitting using genetic algorithms. In SIGMOD,
2013.

Postprocessing for Iterative Differentially Private Algorithms

350

650

Non-private
DPKM
MCMC

300

250

260

Non-private
DPKM
MCMC

600

550

Non-private
DPKM
MCMC

255
250

150

500

WCSS

WCSS

WCSS

245
200

450

240
235
230

100

400

50

350

225

0
0.0

0.2

0.4

0.6

0.8

300
0.0

1.0

220

0.2

0.4



0.6

0.8

215
0.0

1.0

0.2

0.4



(a) S1

(b) Adult-num

1200

0.6

1.0

(c) Tiger

3000

800

2500

750

2000

700

Non-private
DPKM
MCMC

1100
1000

0.8



800

Non-private
DPKM
MCMC

700
600
500

WCSS

WCSS

WCSS

900

1500

Non-private
DPKM
MCMC

1000

400
300
0.0

0.2

0.4

0.6



(d) Image

0.8

1.0

500
0.0

0.2

0.4

0.6

0.8



(e) Gowalla
Figure 1. WCSS by varying 

650

600

1.0

550
0.0

0.2

0.4

0.6



(f) Lifesci

0.8

1.0

