Proceedings on Privacy Enhancing Technologies ; 2019 (1):26–46

Thee Chanyaswad*, Changchang Liu, and Prateek Mittal

RON-Gauss: Enhancing Utility in
Non-Interactive Private Data Release
Abstract: A key challenge facing the design of differential privacy in the non-interactive setting is tomaintain the utility of the released data. To overcome
this challenge, we utilize the Diaconis-Freedman-Meckes(DFM) effect, which states that most projections ofhigh-dimensional data are nearly Gaussian. Hence, we
propose the RON-Gauss model that leverages the novel
combination of dimensionality reduction via random orthonormal (RON) projection and the Gaussian generative model for synthesizing differentially-private data.
We analyze how RON-Gauss benefits from the DFM
effect, and present multiple algorithms for a range ofmachine learning applications, including both unsupervised and supervised learning. Furthermore, we rigorously prove that (a) our algorithms satisfy the strong
-differential privacy guarantee, and (b) RON projection can lower the level of perturbation required for differential privacy. Finally, we illustrate the effectivenessof RON-Gauss under three common machine learning
applications – clustering, classification, and regression– on three large real-world datasets. Our empirical results show that (a) RON-Gauss outperforms previous
approaches by up to an order of magnitude, and (b) loss
in utility compared to the non-private real data is small.
Thus, RON-Gauss can serve as a key enabler for realworld deployment of privacy-preserving data release.
Keywords: differential privacy, non-interactive private
data release, random orthonormal projection, Gaussian
generative model, Diaconis-Freedman-Meckes effect
DOI 10.2478/popets-2019-0003
Received 2018-05-31; revised 2018-09-15; accepted 2018-09-16.

*Corresponding Author: Thee Chanyaswad: Princeton University, E-mail: tc7@princeton.edu (Currently at
KBTG Machine Learning Team, Thailand, E-mail: theerachai.c@kbtg.tech)
Changchang Liu: Princeton University, E-mail:cl12@princeton.edu (Currently at IBM T. J. Watson ResearchCenter, E-mail: changchang.liu33@ibm.com)
Prateek Mittal: Princeton University, E-mail: pmittal@princeton.edu

1 Introduction
In an era of big data and machine learning, our digitalsociety is generating a considerable amount of personal
data at every moment. These data can be sensitive, andas a result, significant privacy concerns arise. Even withthe use of anonymization mechanisms, privacy leakage
can still occur, as exemplified by Narayanan et al. [91],Calandrino et al. [24], Barbaro and Zeller [8], Haeberlen
et al. [53], and Backes et al. [4]. These privacy leaks
have motivated the design of formal privacy analysis. To
this end, differential privacy (DP) has become the gold
standard for a rigorous privacy guarantee [15, 35–37,39]. Many mechanisms have been proposed to comply
with differential privacy [15, 26, 28, 36, 39, 41, 57, 76, 84,
93, 128], and various implementations of differentiallyprivate systems have been presented in the literature[1, 14, 44, 45, 51, 74, 79, 112, 117, 129].
There are two settings under differential privacy –interactive and non-interactive [35]. Among the two, thenon-interactive setting has traditionally been more challenging to implement due to the fact that the perturbation required is often too high for the published data
to be truly useful [11, 21, 40, 118]. However, this setting is still attractive, as there are incentives for thedata collectors to release the data in order to seek outside expertise, e.g. the Netflix prize [97], and OpenSNP[116]. Concurrently, there are incentives for researchers
to obtain the data in their entirety, as existing software
frameworks for data analytics could be directly used
[11, 80]. Particularly, in the current era when machinelearning has become the ubiquitous tool in data analysis, non-interactive data release would allow virtually
instant compatibility with existing learning algorithms.
For these reasons, we aim to design a non-interactive
differentially-private (DP) data release system.
In this work, we draw inspiration from the DiaconisFreedman-Meckes (DFM) effect [87], which shows that,
under suitable conditions, most projections of highdimensional data are nearly Gaussian. This effect suggests that, although finding an accurate model fora high-dimensional dataset is generally hard [18][122,chapter 7], its projection onto a low-dimensional space
may be modeled well by the Gaussian model. With

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Releaserespect to the application of non-interactive DP data
release, this is particularly important because, in DP,
simple statistics can generally be privately learned accurately [38, 42], while privately learning the databaseaccurately is generally much more difficult [21, 118, 124].
To apply the DFM effect to the non-interactive
DP data release, we combine two previously nonintersecting methods – dimensionality reduction (DR)[13, 66, 68, 78, 128, 137] and parametric generativemodel [11, 59, 81, 94, 98, 106, 134]. Although eachmethod has independently been explored for the application of non-interactive private data release, without
properly combining the two, the DFM effect has notbeen fully utilized. As we show in this work, combining
the two to utilize the DFM effect can lead to significant gain in the utility of the released data. Specifically,
we closely investigate the DFM theorem by Meckes [87]and propose the RON-Gauss model for non-interactive
private data release, which combines two techniques –
random orthonormal (RON) projection and the Gaussian generative model. The first component is the DR
technique used for two purposes: reducing the sensitivity(similar to previous works [13, 66, 68, 78, 128, 137]) andtriggering the DFM effect (which is a first, to the best of
our knowledge). The second component is the parametric model used to capture the Gaussian nature of the
projection and to allow an accurate DP data modeling.
We present three algorithms for RON-Gauss thatcan be applied to a wide range of machine learning applications, including both unsupervised and supervised
learning. The supervised learning application, in particular, provides an additional challenge on the conservation of the training label through the sanitization process. Unlike many previous works, RON-Gauss ensures
the integrity of the training label of the sanitized data.
We rigorously prove that all of our three algorithms preserve the strong -differential privacy guarantee. Moreover, to show the general applicability of our idea, we
extend the framework to employ the Gaussian Mixture
Model (GMM) [12, 90].
Finally, we evaluate our approach on three large
real-world datasets under three common machine learning applications under the non-interactive setting of
DP – clustering, classification, and regression. The noninteractive setting is attractive for these applications
since it allows multiple data-analytic algorithms to be
run on the released DP-data without requiring additional privacy budget like the interactive setting. We
demonstrate that our method can significantly improvethe utility performance by up to an order of magnitude
for a fixed privacy budget, when compared to four prior27

methods. More importantly, our method has small loss
in utility when compared to the performance of the nonprivate real data.
We summarize our contribution as follows.
– We exploit the DFM effect for utility enhancementof differential privacy in the non-interactive setting.
– We propose an approach consisting of random orthonormal projection and the Gaussian generativemodel (RON-Gauss) for non-interactive DP data release. We also extend this model to the Gaussian
Mixture Model (GMM).
– We present three algorithms to implement RONGauss that are suitable for both the unsupervisedand supervised machine learning tasks.
– We rigorously prove that our RON-Gauss algorithms satisfy the strong -differential privacy.
– We evaluate our method on three real-world
datasets on three machine learning applications under the non-interactive DP setting – clustering, classification, and regression. The experimental results
show that, when compared to previous methods,
our method can considerably enhance the utility
performance by up to an order of magnitude fora fixed privacy budget. Finally, compared to thenon-private baseline of using real data, RON-Gauss
incurs only a small loss in utility across all threemachine learning tasks.
Roadmap: We discuss prior works in Section 2, andpresent the background components of our approach,including details of the DFM effect, in Section 3. Then,
we present the proposed RON-Gauss model – along with
its theoretical analysis, algorithms for both supervisedand unsupervised learning, and the privacy proofs – in
Section 4. Finally, we present experimental results showing the strength of RON-Gauss in Section 5, and thediscussion in Section 6.

2 Prior Works
Our work focuses on non-interactive differentiallyprivate (DP) data release. Since our method involves
dimensionality reduction and a generative model, we
discuss the relevant works under these frameworks.

2.1 Generative Models for Differential
Privacy
The use of generative models for non-interactive DP
data release can be classified into two groups accord-

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Releaseing to Bowen and Liu [17]: non-parametric generativemodels, and parametric generative models.
2.1.1 Non-Parametric Generative Models
Primarily, these models utilize the differential privacy
guarantee of the Exponential mechanism [84], which
defines a distribution to synthesize the data based on
the input database and the pre-defined quality function. Various methods – both application-specific andapplication-independent – have been proposed [10, 16,
31, 52, 56, 57, 74, 77, 83, 84, 89, 98, 124, 127]. Our
approach contrasts these works in two ways. First, weconsider a parametric generative model, and, second,
we augment our model with dimensionality reduction to
trigger the DFM effect. We will compare our method tothis class of model by implementing the non-parametric
generative model based on Algorithm 1 in [16].

28

on two steps – kernel K-means clustering and generative
neural networks – to similarly provide (, δ)-differential
privacy. In contrast, our work aims at providing thestrictly stronger -differential privacy. Another previous
method is MODIPS by Liu [80], which applies statistical models based on the concept of sufficient statistics
to capture the distribution of the data, and then synthesizes the data from the differentially-private models.
This general idea is, in fact, closely related to the Gaussian generative model employed in this work. However,
the important distinction is that MODIPS is not accompanied by dimensionality reduction – a step which will
be shown to enhance the utility of released data via the
DFM effect. For comparison, we implement MODIPS in
our experiments and show the improvement achievable
by RON-Gauss.

2.2 Dimensionality Reduction and
Differential Privacy

2.1.2 Parametric Generative Models
Our method of using the Gaussian generative model, as
well as the Gaussian Mixture Model, falls into this category. We aim at building a system that can be applied
to various applications and data-types, i.e. applicationindependent. However, many previous works on noninteractive DP data release are application-specific orlimited by the data-types they are compatible with.
Thus, we discuss these two types separately.
2.1.2.1 Application-Specific
These models are designed for specific applications ordata-types. For example, the works by Sala et al. [106]and by Proserpio et al. [98] are for graph analysis, thesystem by Ororbia et al. [94] is for plaintext statistics, the analysis by Machanavajjhala et al. [81] is forcommuting pattern analysis, the Binomial-Beta modelby McClure and Reiter [82] and Bayesian-network by
Zhang et al. [134] are for binary data, and the LDA
model by Jiang et al. [66] is for binary classification.
In contrast, in this work, we aim at designing anapplication-independent generative model.
2.1.2.2 Application-Independent
These generative models are less common, possibly due
to the fact that releasing data for general analytics often requires a high level of perturbation that impacts
data utility. Bindschaedler et al. [11] design a systemfor plausible deniability, which can be extended to (, δ)differential privacy. Acs et al. [3] design a system based

Traditionally, data partition and aggregation [28, 31, 57,
58, 60, 61, 75, 93, 98–100, 130, 133, 136] have been applied to enhance data utility in differential privacy. In
contrast, our work utilizes the DFM effect for the utility
enhancement, of which an important component is dimensionality reduction (DR) using the RON projection.
We present previous works pertaining to the use of DR
in DP here. However, although previous works have explored the use of DR to directly provide DP or to reduce
the sensitivity of the query, our work, in contrast, uses
DR primarily to trigger the DFM effect for enhancing
data utility in the non-interactive setting.
2.2.1 Random Projection
For suitable query functions, random projection has
been shown to preserve differential privacy [13, 119,120]. Alternatively, random projection has also beenused to enhance the utility of differential privacy. Multiple types of random projections have been used with
the identity query for non-interactive DP data releasefor both purposes. For example, Blocki et al. [13], Kenthapadi et al. [68], Zhou et al. [137], and Xu et al.
[132] use a random matrix whose entries are i.i.d. Gaussian, whereas Li et al. [78] use i.i.d. Bernoulli entries.
However, there are three main contrasts to our work.
(1) While Blocki et al. [13] use random projection topreserve differential privacy, we use random projection
to enhance utility via the DFM effect. (2) Instead ofi.i.d. Gaussian or Bernoulli entries, we use random or-RON-Gauss: Enhancing Utility in Non-Interactive Private Data Releasethonormal (RON) projection to ensure the DFM effectas proved by Meckes [87]. (3) As opposed to our approach, none of the previous random-projection methods
couples DR with a generative model. We will experimentally compare our work with the method by Li et al. [78],and show that, by exploiting the Gaussian phenomenon
via the DFM effect, we achieve significant utility gain.

29

Remark 1. There is also the (, δ)-differential privacy((, δ)-DP) [30, 37], which is a relaxation of this definition. However, this work focuses primarily on thestronger -DP.
Our approach employs the Laplace mechanism, whichuses the notion of L1 -sensitivity. For a general query
function whose output can be a p × q matrix, the L1 sensitivity is defined as follows.

2.2.2 Other Dimensionality Reduction Methods
Other DR methods have also been used with the identity query to enhance data utility including PCA [66],wavelet transform [128], and lossy Fourier transform [2].
In contrast, our DR is coupled with a generative model,
rather than used with the identity query. We experimentally compare our work with the PCA method by
Jiang et al. [66] and show that our use of the generativemodel yields significant improvement.

3 Preliminaries
In this section, we discuss important background concepts related to our work.

3.1 Database Notation
We refer to the database as the dataset, which contains
n records (samples), each with m real-valued attributes(features) – although, our approach is also compatible
with categorical features since they can be converted toreal values with encoding techniques [126]. With thissetup, the dataset can be represented by the data matrix X ∈ Rm×n , whose column vectors xj are the samples, with xj (i) refers to the ith feature. Finally, randomvariables are denoted by a regular capital letter, e.g. Z,
which may refer to a random scalar, vector, or matrix.
The reference will be clear from the context.

3.2 Differential Privacy (DP)Differential privacy (DP) protects against the inferenceof the participation of a sample in the dataset as follows.
Definition 1 (-DP). A mechanism A on a query function f (·) preserves - differential privacy if for all neighboring pairs X, X0 ∈ Rm×n which differ in a single
record and for all possible measurable outputs S ⊆ R,
Pr[A(f (X)) ∈ S]
≤ exp().
Pr[A(f (X0 )) ∈ S]

Definition 2. The L1 -sensitivity of a query function
f : Rm×n → Rp×q for all neighboring datasets X, X0 ∈Rm×n which differ in a single sample isS(f ) = sup f (X) − f (X0 ) 1 .
X,X0

Remark 2. In DP, the notion of neighboring datasets
X, X0 can be considered in two related ways. The firstis the unbounded notion when one record is removed or
added. The second is the bounded notion when values of
one record vary. The main difference is that the latterassumes the size of the dataset n is publicly known,
while the former assumes it to be private. However, thetwo concepts are closely related and a mechanism thatsatisfies one can also satisfy the other with a small cost(cf. [16]). In the following analysis, we adopt the latternotion for clarity and mathematical simplicity.
The main tool for DP guarantee in this work is the
Laplace mechanism, which is recited as follows [39, 41].
Theorem 1. For a query function f : Rm×n → Rp×q
with the L1 -sensitivity S(f ), the following mechanism
preserves -differential privacy:
San(f (X)) = f (X) + Z,
where Z ∈ Rp×q with zj (i) drawn i.i.d. from the Laplace
distribution Lap(S(f )/).

3.3 Gaussian Generative Model
Gaussian generative model synthesizes the data fromthe Gaussian distribution N (µ, Σ), which is parameterized by the mean µ ∈ Rm , and the covarianceΣ ∈ Rm×m [90, 121]. Formally, the Gaussian generative model has the following density function:
1
1
f (x) = pexp(− (x − µ)T Σ−1 (x − µ)).
m2(2π) det(Σ)(1)
Hence, to obtain the Gaussian generative model for ourapplication, we only need to estimate its mean andcovariance. This reduces the difficult problem of dataRON-Gauss: Enhancing Utility in Non-Interactive Private Data Releasemodeling into the much simpler one of statistical estimation. This is particularly important in DP since it
has been shown that simple statistics of the databasecan be privately learned accurately [38, 42]. In addition,
this model is supported by the following rationales.
– It is supported by the Diaconis-Freedman-Meckes(DFM) effect [87], which may be viewed as an analog of the Central Limit Theorem (CLT) [54, 101]in the feature space. This effect will be discussed indetail in Section 3.4.
– It is simple to use and well-understood. Samplingfrom it is straightforward, since there exist multiple
available packages, e.g. [22, 49, 111].
– Various methods in data analysis have both directly
and indirectly utilized the Gaussian model, e.g. linear/quadratic discriminant analysis [46, 65], PCA[63][90, chapter 12], Gaussian Bayes net [90, chapter 10], Gaussian Markov random field [105], Restricted Boltzmann machine (RBM) network [105],
Radial Basis Function (RBF) network [19], factor
analysis [90, chapter 12], and SVM [96].
In spite of these advantages, we acknowledge that there
is possibly no single parametric model that can universally capture all possible datasets, and generalizing ourapproach to non-parametric generative models is an interesting future work.

3.4 Diaconis-Freedman-Meckes (DFM)
Intuitively, the Diaconis-Freedman-Meckes (DFM) effect – initially proved by Diaconis and Freedman in 1984[33] – states that "under suitable conditions, most projections are approximately Gaussian". Later, the precise
statement of the conditions and the appropriate projections has been proved by Meckes [86, 87], and thephenomenon has been substantiated both theoretically[55] and empirically [20, 92]. This work considers thetheorem by Meckes [87] as follows.
Theorem 2 (DFM effect [87, Corollary 4]). Let W ∈Rm×p be a random projection matrix with orthonormal
columns, X ∈ Rm be data drawn i.i.d. from an unknown
distribution X , which satisfies the regularity conditions
e = WT X ∈ Rp be the projectionin Table 1, and let X
of X via W, which has the distribution Xe. Then, forp  m, with high probability,dBL
Xe ≈ σN (0, I),

where N (0, I) is the standard multi-variate Gaussian
distribution with p dimensions, σ is the variance of30

Let the data X ∈ Rm be drawn from a distribution X ,which satisfies:hi
E kXk2 = σ 2 m,
sup E hv, Xi2 ≤ 1,v∈Sm−1hE

kXk2 σ −2 − m

i√≤ c m.

Table 1. The regularity conditions for the DFM effect. σ is thevariance defined in Theorem 2, c > 0 is a constant, and Sm−1 isthe topological sphere (cf. [125]).

dBL

the Gaussian distribution, and ≈ is the approximate
equality in distribution with respect to the conditionalbounded-Lipschitz distance.
Remark 3. The conditional bounded-Lipschitz distancedBL is a distance metric, which can be used to measure
the similarity between distributions. More detail on dBLdBL

can be found in [103]. Here, the notion ≈ is used toindicate that the distance between Xe and σN (0, I) is
bounded by a small value [87].
Theorem 2 suggests that, under the regularity conditions, most random orthonormal (RON) projections of
the data are close to Gaussian in distribution. Morespecifically, Meckes [87] suggests that the Gaussian phe2 log(m). For examnomenon generally occurs for p < log(log(m))
ple, if the original dimension of the dataset is m = 100,
the projected data would approach Gaussian with p ≤13. Intuitively, the regularity conditions assure that thedata are well-spread around the mean with a finite second moment. The convergence to the standard Gaussianalso implies that the mean of X is zero. However, thisis less critical since dBL is a distance metric [103], somean-shift can be shown to result in a Gaussian with ascaled mean-shift (cf. [86, 103]).

4 RON-Gauss: Exploiting the
DFM Effect for Non-Interactive
Differential Privacy
Based on the DFM effect discussed in Section 3.4, we
present our approach for the non-interactive DP data release: the RON-Gauss model. In the subsequent discussion, we first give an overview of the RON-Gauss model.
Then, we discuss the approach used in RON-Gauss withcorresponding theoretical analyses. Finally, we present
algorithms to implement RON-Gauss for both unsuper-RON-Gauss: Enhancing Utility in Non-Interactive Private Data Releasevised and supervised learning tasks, and prove that thedata generated from RON-Gauss preserve -DP.

4.1 Overview
RON-Gauss stands for Random OrthoNormal projection with GAUSSian generative model. As its name suggests, RON-Gauss has two components - dimensionality
reduction (DR) via random orthonormal (RON) projection, and parametric data modeling via the Gaussian
generative model. Each component plays an importantrole in RON-Gauss as follows.
The DR via random orthonormal (RON) projection
has two purposes. First, as previous works have shown[13, 66, 68, 78, 128, 137], DR can reduce sensitivity ofthe data. This is true for many DR techniques. However,in this work, we choose the RON projection due to thesecond purpose of DR in the RON-Gauss model, i.e. totrigger the DFM effect. This is verified by Theorem 2
as proved by Meckes [87].
The parametric modeling via the Gaussian generative model also has two purposes. First, it allows us to
fully exploit the DFM effect since, unlike most practical data-analytic settings, we know the distribution of
the data from the effect. Second, it allows us to reducethe difficult problem of non-interactive private data release into the more amenable one of DP statistical estimation. Particularly, it reduces the problem into thatof privately estimating the mean and covariance – aproblem which has seen success in DP literature (cf.
[15, 36, 38, 39, 41–43, 124]).
Combining these two components is crucial for getting high utility from the released data, as we will
demonstrate in our experiments, and we highlight themain differences between our approach and previous
works in non-interactive DP data release as follows.
– Although prior works have used DR for improving
utility of the released data (cf. Section 2.2), theseworks do not use the Gaussian generative model.
Hence, they do not fully exploit the DFM effect.
– Similarly, there have been prior works that use generative models for synthesizing private data (cf. Section 2.1). However, without DR, the sensitivity is
generally large for high-dimensional data, and, more
importantly, the DFM effect does not apply.
– Unlike the work by Blocki et al. [13], we do not use
random projection to provide DP. In RON-Gauss,
DP is provided after the projection via the Laplacemechanism on the Gaussian generative model.
– Unlike previous works that use i.i.d. Gaussian or
Bernoulli random projection [68, 78, 132, 137], we31

use RON projection, which has been proved to besuitable for the DFM effect (Theorem 2).
Finally, we acknowledge that although RON-Gauss isdesigned to be application-independent, it may not besuitable for every task. In this work, we focus on popularmachine learning tasks including clustering, regression,and classification. As discussed in Section 3.3, many machine learning algorithms implicitly or explicitly utilize
the Gaussian model, so RON-Gauss is generally suitable
for these applications.

4.2 Approach and Theoretical Analysis
The RON-Gauss model uses the following steps:
1. Pre-processing to satisfy the conditions for the DFM
effect (Theorem 2).
(a) Pre-normalization.
(b) Data centering.
(c) Data re-normalization.
2. RON projection.
3. Gaussian generative model estimation.
We provide the detail of each process as follows.
4.2.1 Data Pre-Processing
Given a dataset with n samples and m features, to utilize the DFM effect, we want to ensure that the datasatisfy the regularity conditions of Theorem 2. We showthat the following sample-wise normalization ensuresthe conditions are satisfied.
Lemma 1 (Sample-wise normalization). Let D ∈ Rm
be data drawn i.i.d. from a distribution D. Let X ∈ Rm
be derived from D by the sample-wise normalization1 :
X=

D
.
kDk

Then,

h
i
E kXk2 = 1,
sup E hv, Xi2 ≤ 1,v∈Sm−1hE

kXk2 σ −2 − mi= σ −2 − m .

Proof. The first and third equalities are obvious by observing that kXk = 1. The second inequality follows

1 Here, it is implicitly assumed that kDk is finite, which is typically the case when we are given a training dataset.

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Releasefrom the Cauchy–Schwarz
inequality[25, 109] as folhilows. E hv, Xi2 ≤ E kvk2 kXk2 = 1, since v is on thesurface of the unit sphere.
From this lemma, we can verify that the sample-wisenormalization satisfies the regularity conditions in The√
orem 2 simply by considering σ = 1/ m. Recall from
Theorem 2 that the choice of σ indicates what the variance of the projected data will be. In other words, a low
value of σ geometrically signifies a narrow bell curveof Gaussian. Hence, in our application, this is the normalization we employ. However, we observe that thisnormalization has an effect of placing all data samples onto the surface of the sphere, i.e. xi ∈ Sm−1 .
Hence, it is beneficial to center the data before performing this normalization to ensure that the data remain well-spread after the normalization. For this reason, data pre-processing for RON-Gauss consists ofthree steps – pre-normalization, data centering, anddata re-normalization. As we will discuss shortly, thepre-normalization is to aid with the sensitivity derivation of the sample mean used in the centering process,while the re-normalization is to ensure the regularity
conditions in Theorem 2 is satisfied before the projection. These three steps are discussed in detail as follows.
4.2.1.1 Pre-Normalization
We start with a given dataset X ∈ Rm×n with n samples
and m features, and perform the preliminary samplewise normalization as follows.
xi :=

xi
,
kxi k

for all xi ∈ X. This normalization ensures that kxi k = 1
for every sample, which will be important for the derivation of the L1 -sensitivity in the next step.
4.2.1.2 Data Centering
Data centering is performed before RON projection inorder to reduce the bias of the covariance estimation for
the Gaussian generative model and to ensure that thedata are well-spread. Data centering is achieved simply
by subtracting the DP-mean of the dataset. Given the
pre-normalized dataset, {xi ∈ Rm ; kxi k = 1}ni=1 , thePnsample mean is µ = n1 i=1 xi , and the L1 -sensitivityof the sample mean can be computed as follows.
Lemma 2. Given a sample-wise normalized dataset
X ∈ Rm×n , the L1 -sensitivity of the sample mean is√s(f ) = 2 m/n.

32

Proof. For neighboring datasets X, X0 ,s(f ) = sup f (X) − f (X0 ) 1
X,X0

√
1
m
xi − xi0 1 ≤ supxi − xi0 F
n
n
√
√
2 m
m
≤ sup
(kxi kF + xi0 F ) =
,
n
n

= sup

where the first inequality uses the norm relation [62,page 333].
With the L1 -sensitivity of the sample mean, we canthen derive DP-mean µDP via the Laplace mechanism (Theorem 1), and perform data centering by X̄ =X−µDP 1T , where 1 is the vector with all ones. We note
that, although the mean is DP-protected, the centereddata are not DP-protected, so they cannot be released.
RON-Gauss only uses the centered data to estimate thecovariance, which is then DP-protected. Hence, the centered data are never published. In addition, as will be
important to the DP analysis later, we note that thiscentering process ensures that any neighboring datasets
would be centered by the same mean. Hence, neighboring X̄ and X̄0 would still differ by only one record.
4.2.1.3 Data Re-Normalization
After adjusting the mean, the centered dataset X̄ would
likely not remain normalized. Hence, to ensure the regularity conditions in Theorem 2, we re-normalize the data
after the centering process using the same sample-wisenormalization scheme, i.e.
x̄i :=x̄i.
kx̄i kHence, we again have kx̄i k = 1 for every sample. In
addition, neighboring datasets still differ by only one
sample since the normalization factor only depends onthe corresponding sample, but not on any other sample.
4.2.1.4 Summary
Data_Preprocessing (Algorithm 1) summarizes
these steps for pre-processing the data, which include
pre-normalizing, centering, and re-normalizing. The DP
mean derivation uses the Laplace mechanism with thesensitivity in Lemma 2. If needed, the DP mean can also
be acquired from this algorithm.
4.2.2 RON Projection
As shown in Lemma 1, after the pre-processing steps,X̄ can be shown to be in a form that complies with theRON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

33

Algo. 1 Data_Preprocessing

Algo. 2 RON_Projection

Input: dataset X ∈ Rm×n and µ > 0.

Input: pre-processed dataset X̄ ∈ Rm×n , and dimension p < m.

1.
2.
3.
4.

Pre-normalize: xi := xi / kxi k for all xi ∈ X.
Pn
1x ) + Z, where zj (i)Derive the DP mean: µDP = ( ni=1 i√
is drawn i.i.d. from Lap(2 m/nµ ).
Center the data: X̄ = X − µDP 1T .
Re-normalize: x̄i = x̄i / kx̄i k for all x̄i ∈ X̄.

Output: X̄, µDP .

regularity conditions in Theorem 2. The next step isto project X̄ onto a low-dimensional space using therandom orthonormal (RON) projection matrix W ∈Rm×p : WT W = I. The RON projection matrix is derived independently of the dataset, so it does not leakprivacy, and no privacy budget is needed for its acquisition.
The projection is done via the linear transformation xei = WT x̄i ∈ Rp for each sample, or, equivalently,
e = WT X ∈ Rp×n . Since thein the matrix notation X
projection is done sample-wise, the neighboring datasets
would still differ by only one sample after the projection.
This property will be important to the DP analysis of
the RON projection later. In addition, the other important theoretical aspect of the RON projection step isthe bound on the projected data. This is provided by
the following lemma.
Lemma 3. Given a normalized data sample x̄ ∈ Rm
and a random orthonormal (RON) projection matrix,
W ∈ Rm×p : WT W = I, let x
e = WT x̄ be the projection
via W. Then, kx
ekF ≤ 1.
Proof. The proof is provided in Appendix A.
Lemma 3 indicates that the RON projection of the normalized data does not change their Frobenius norm.
This will be critical in the DP analysis of RON-Gauss
algorithms in the next step.
RON_Projection (Algorithm 2) summarizes thecurrent step that projects the pre-processed data onto alower dimension p via RON projection. The RON projection matrix can be derived efficiently via the QR factorization [50, 107], as shown in the algorithm. Specifically, the RON projection matrix is constructed bystacking side-by-side p column vectors of the unitarymatrix Q from the QR factorization. Then, the projece = WT X̄ ∈ Rp×n . Iftion is done via the linear operation X
needed, the RON projection matrix can also be acquired
from the output of the algorithm.
e are still
We further note that the projected data X
not DP-protected. This is one key difference between

1.
2.
3.
4.

Form a matrix A ∈ Rm×m whose elements are drawn i.i.d.
from the uniform distribution.
Factorize A via the QR factorization as A = QR, whereQ ∈ Rm×m : QT Q = I.
Construct a RON projection matrix W = [q1 , . . . , qp ] ∈Rm×p .
e = WT X̄ ∈ Rp×n .
Project the data: X

e ∈ Rp×n , W.
Output: X
our work and that of Blocki et al. [13], which uses rane
dom projection to directly provide DP. In our work, X
is never released, and we only use it to estimate the covariance of the Gaussian generative model in the next
step. The DP protection in our work is provided in thisnext step on the Gaussian generative model.
4.2.3 Gaussian Generative Model Estimation
This step constructs the Gaussian generative model,
which is where the DP protection in RON-Gauss is provided. We emphasize that RON-Gauss is an outputperturbation algorithm, and we employ the standard
DP threat model, i.e. the RON-Gauss algorithm is run
by a trusted entity and only the output of the algorithm
is available to the public. The DP-protected Gaussian
generative model is then used to synthesize DP dataset
for the non-interactive DP data release setting we consider. Synthesizing DP data from a parametric model, as
opposed to releasing the model itself, has two benefits.
First, existing machine learning software can readily be
used with the DP data as if they were the real data. Second, it presents an additional challenge for an attacker
aiming to perform inference attacks, since the attacker
would also need to estimate the model parameters fromthe released data, incurring further errors.
Before delving into the detail of this step, there is
an important distinction to be made about the dataanalytic problems we consider. Since machine learning
is currently the prominent tool in data analysis, we follow the convention in machine learning and consider twoclasses of problems – unsupervised learning and supervised learning. The main difference between the two isthat, in the latter, in addition to the feature data ine the teacher value or training label y ∈ Rn is also reX,quired to guide the data-analytic process. Hence, in thesubsequent analysis, we first consider the simpler classof unsupervised learning, and then, show a simple modification to include the teacher value for the supervised

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Releaselearning. Additionally, we conclude with an extension of
RON-Gauss to the Gaussian Mixture Model.
4.2.3.1 Unsupervised Learning
The unsupervised learning problems do not require thetraining label, so the Gaussian generative model only
e The main parameneeds to synthesize DP-protected X.
ter for the Gaussian generative model is the covariancee We use thematrix Σ, so we need to estimate Σ from X.
following formulation for the sample covariance:nΣ=

1 e eT
1X
XX =
x
ei x
eiT ∈ Rp×p .
n
n

(2)

i=1

We note that this estimate may be statistically biased
since the mean may not necessarily be zero after the
re-normalization. However, this formulation would yieldsignificantly lower sensitivity than its unbiased counterpart. This is due to the observation that only one
summand can change for neighboring datasets since, as
mentioned in the previous step, neighboring projected
f0 still differ by only one sample. Hence, we
e X
datasets X,
are willing to trade the bias for a much lower sensitivity.
In Appendix B, we specifically show that the saving insensitivity by our formulation is in the order of n, compared to the MLE of the covariance. Clearly, for large
datasets, this is significant and can be the difference
between usable and unusable models.
Next, we derive the sensitivity of the covariance estimate in Eq. (2) as follows.
Lemma 4. Given a dataset X ∈ Rm×n , lete be the pre-processed and RON-projected datasetX
via Data_Preprocessing and RON_Projection.
Then, the covariance Σ ∈ Rp×p in Eq. (2) has the L1 √sensitivity of 2 p/n.
Proof. For neighboring datasets X, X0 ,s(f ) = sup

1 e eT
1 f0 f0 T
X
XX − X
n
n

1

1 T
= sup
W [X − µDP 1T ][X − µDP 1T ]T W
n
−

1 T 0
W [X − µDP 1T ][X0 − µDP 1T ]T W ,
n
1

= sup

n
1 X T
W [xi − µDP ][xi − µDP ]T W
n
i=1

−

n
X
i=1

WT [xi0 − µDP ][xi0 − µDP ]T W,
1where the second equality is simply from the defe through Data_Preprocessing andinition of X

34

RON_Projection. Since all of the summands are thesame except for one in the neighboring datasets, we have1
WT [xi − µDP ][xi − µDP ]T W
n
− WT [xi0 − µDP ][xi0 − µDP ]T W 1 .

s(f ) = supThen, to simplify the notation and to apply Lemma 3,
we note that x
ei = WT [xi − µDP ] by definition. Hence,
T
1
x
ei x
eiT − xe0 i xe0 i
n
1
√
T
p
T
0
0
e
e
≤ sup
x
ei x
ei − x i x i
n
F
√
√
√
2 p
2 p
2 p
T
≤ sup
x
ei x
ei F ≤ supkx
ei k2F =,nnnwhere the first inequality uses the norm relation [62,page 333], and the last equality uses Lemma 3.

s(f ) = supLemma 4 provides an important insight into the RONGauss model. As discussed in the overview (Section 4.1),
the RON projection step of RON-Gauss serves two purposes – to initiate the DFM effect, and to reduce thesensitivity of the model. The latter purpose can clearlybe observed from Lemma 4. Specifically, Lemma 4 indicates that the L1 -sensitivity of the main parameter ofthe RON-Gauss model, i.e. the covariance, reduces as
the dimension p reduces. This is particularly attractive
when the original data are very high-dimensional as thenoise added by the Laplace mechanism could be greatly
reduced. For example, for the original data with 100
dimensions, the RON projection onto a 10-dimensional
subspace would reduce the sensitivity by about 3x.
With the L1 -sensitivity derived, the Laplace mechanism in Theorem 1 can be used to derive the DP covariance matrix: ΣDP . With ΣDP , RON-Gauss then generates the synthetic DP data from N (0, ΣDP ). If themean is needed, we can readily use WT µDP , which already satisfies DP due to the post-processing invarianceof DP [36]. This completes the RON-Gauss model for
unsupervised learning.
Algorithm 3 summarizes the RON-Gauss model for
unsupervised learning. First, the data are pre-processed
via Data_Preprocessing (Algorithm 1). The DP
mean derivation in Data-Preprocessing spends theprivacy budget µ . Second, the data are projected onto
a lower dimension p via RON_Projection. Third,
the algorithm derives the DP covariance using the
Laplace mechanism with the sensitivity derived in
Lemma 4. Finally, the algorithm synthesizes DP databy drawing samples from the Gaussian generative model
parametrized by the DP covariance. We conclude thediscussion on RON-Gauss for unsupervised learningwith the DP analysis of Algorithm 3.

35

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

Algo. 3 RON-Gauss for unsupervised learning
Input: dataset X ∈ Rm×n , dimension p < m, and µ , Σ > 0.
1.
2.
3.
4.

Obtain the pre-processed data X̄ ∈ Rm×n from
Data_Preprocessing with inputs X and µ .
e ∈ Rp×n from
Obtain the RON-projected data X
RON_Projection with inputs X̄ and p.
1 e eT
Derive the DP covariance: ΣDP = ( nXX ) + Z, where√zj (i) is drawn i.i.d. from Lap(2 p/nΣ ).
Synthesize DP data xiDP ∈ Rp by drawing samples fromN (0, ΣDP ).

DP }.
Output: {x1DP , . . . , xn
0

Theorem 3. Algorithm
differential privacy.

3

preserves(µ + Σ )-Proof. The proof follows the following induction. The
DP data xiDP are derived from only one source, i.e.
the Gaussian generative model of RON-Gauss. Basedon the post-processing invariance of DP, if the modelis DP-protected, then the released data are also similarly DP-protected. The Gaussian generative model isparametrized by ΣDP , which is DP-protected. Specifically, the ΣDP computation in step 3(a) spends Σ privacy budget with the Laplace mechanism, according to
Theorem 1. However, the centering process in step 1(c)also spends µ privacy budget on the Laplace mechanism
to derive µDP , which assists in the ΣDP derivation process. Due to the serial composition theorem [36], the two
privacy budgets add up. Hence, ΣDP preserves (µ +Σ )differential privacy, and, consequently, the Gaussian
generative model preserves (µ +Σ )-differential privacy,
so do the synthesized data.

words, we may not be able to extract the training label
from the projected data. Thus, to preserve the integrityof the training label, it should not be modified by the
RON projection process.
In RON-Gauss, the aforementioned challenge insupervised learning is navigated by augmenting theeXdata matrix with the training label as Xa =∈yT
R(p+1)×n . Then, the augmented covariance matrix canbe written in block form as,
"
#
 h
i 1 X
eX
eT
e
e
1 X
Xy
T
e
(3)
Σa =
X
y =
e T yT y .
n yTn yT X
This can then be used in a similar fashion to the covariance matrix in Eq. (2) for unsupervised learning.
We note that, again, this may not be an unbiased estimate of the augmented covariance matrix since themean may not necessarily be zero, but, similar to theunsupervised learning design, it has significantly lower
sensitivity than the unbiased counterpart. Therefore, we
are willing to trade the bias for achieving small sensitivity. Given the training label with bounded value2y ∈ [−a, a]n , the sensitivity of the augmented covariance matrix can be derived as follows.
Lemma 5. The L1 -sensitivityof√the augmented covari√
2 p+4a p+a2.
ance matrix in Eq. (3) isnProof. For neighboring datasets X, X0 , the sensitivity is
"
# "
#
T
f0 X
f0
f0 y0
eX
eT
e
1
X
Xy
X
X
S(Σa ) = sup,Te T yT y − y0T X
n yT Xf0
y0T y01

4.2.3.2 Supervised Learning
The unsupervised learning does not involve the guidancefrom the training label. However, in supervised learning,
the training label y is also required. Hence, the Gaussian
generative model needs to be modified to incorporate
the training label into the model in order to synthesize
e and y.
both DP-protected X
A simple method to incorporate the training label into the Gaussian generative model is to treat it
as another feature. However, when RON projection isapplied, it should only be applied to the feature data,
but not to the training label. This is because when the
projection is applied, each induced feature is a linear
combination of all original features. Therefore, if RON
projection is also applied to the training label, the integrity of the training label would be spoiled. In other1 e e T f0 f0 T
= sup ( X
X −X Xn+ yT y − y0T y0 1 ).

1

f0 y0
e −X
+ 2 Xy1

The proof then considers each summand separately. The
first summand is the sensitivity of Σ in Eq. (2), so it is√
2 p/n. The last summand can be written as,
supyT y − y0T y0 1
n

Pn
= sup
= sup

2
i=1 y(i) −Pnny(i)2 − y 0 (i)2 1n02
i=1 y (i) 1

=

a2
,
n

where the second equality is because only one element
in y and y0 differs.

2 As suggested by Liu [80], real-world data are often bounded,and the bounded-valued assumption is often made in DP analysis for multi-dimensional query (cf. [27, 39, 43, 137]).

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release36

Algo. 4 RON-Gauss for supervised learning

Algo. 5 RON-Gauss’ extension to GMM

Input: dataset with training labels X ∈ Rm×n , y ∈ [−a, a]n ,dimension p < m, and µ , Σ > 0.

Input: dataset X ∈ Rm×n , y ∈ {c1 , c2 , . . . , cL }n , dimension
p < m, and µ , Σ > 0.

1.
2.

3.
4.

5.

Obtain the pre-processed data X̄ ∈ Rm×n from
Data_Preprocessing with inputs X and µ .
e ∈ Rp×n from
Obtain the RON-projected data X
RON_Projection with inputs X̄ and p.
 eXForm the augmented data matrix Xa =∈ R(p+1)×n .
yT

1.

for c in {c1 , . . . , cL } do:2.

(a) Form Xc , whose nc column vectors are all samples inclass c.
(b) Obtain the pre-processed data X̄c ∈ Rm×nc and the
DP class-mean µDP
from Data_Preprocessing withc
inputs (Xc , µ ).
e c ∈ Rp×nc and the(c) Obtain the RON-projected data X
projection matrix W from RON_Projection with inputs X̄c and p.
e cX
e Tc ) +(d) Derive the DP class-covariance: ΣDP= ( n1 X
c√c
Z, where zj (i) is drawn i.i.d. from Lap(2 p/nc Σ ).
(e) Synthesize DP class-c data XDP
by drawing samplescDP ), and assign yDP = c for all
from N (WT µDP
,
Σ
c
c
c
samples in XDP
c .
DP
Let XDP = [XDP
c1 , . . . , XcL ].

3.

Let yDP = [yDP
, . . . , yDP
]T .
c1
cL

1
Xa XT
Derive the DP augmented covariance: ΣDP
= (n
a )+
a
√
√
(Σ)
Σ
Z
, where zj (i) is drawn i.i.d. from Lap((2 p + 4a p +a2 )/nΣ ).
xiDP
Synthesize DP augmented data
∈ Rp+1 by
y(i)DPdrawing samples from N (0, ΣDPa ).
DP } with training label yDP .
Output: {x1DP , . . . , xn
0

For the second summand, we haveT

T

Output: {XDP , yDP }.

f0 y0
e −X
2 Xy
sup

n

2
1

= sup

= sup
≤ sup

P

ei y(i) −ix

P e0 0i xi y (i)n0e2 xei y(i) − xi y 0 (i)1Theorem 4. Algorithm
differential privacy.

14preserves(µ + Σ )-n2(kxei y(i)k1 + xei0 y 0 (i)Proof. The proof mirrors that of Theorem 3 but uses
the sensitivity of the augmented covariance in Lemma
5 instead.

)
1

n
√

2 p(kxei y(i)kF + xei0 y 0 (i)

≤ sup
n
√
√
4a p
2 p(2a)
=
,
≤
n
n

)
F

where the second line is from the fact that the other n−1
terms are similar for neighboring datasets. By combing
the three summands, we have completed the proof.
As the L1 -sensitivity of Σa has been derived, we canuse the Laplace mechanism in Theorem 1 to acquire theDP augmented covariance matrix: ΣDP
a . Then, similar
to the unsupervised learning, RON-Gauss generates thesynthetic DP data – which include both the feature data
and the training label – from N (0, ΣDPa ). Notice thatthe only difference between the RON-Gauss model for
unsupervised learning and supervised learning is the useof ΣDP (Eq. (2)) and ΣDP(Eq. (3)), respectively.
a
Algorithm 4 presents the RON-Gauss model for supervised learning. The algorithm is similar to Algorithm
3. The only difference is the use of the augmented covariance matrix in step 4 with the sensitivity from Lemma 5
to incorporate the training label. As a result, Algorithm
4 can synthesize both the DP feature data xiDP and the
DP training label yDP . Finally, we present the privacy
guarantee of Algorithm 4 as follows.

4.2.3.3 Extension to Gaussian Mixture Model
Algorithm 4 for supervised learning uses the unimodal
Gaussian generative model. The labels synthesized fromthis algorithm are numerical. In many applications, e.g.
regression, this may already be effective. However, insome applications, e.g. classification, it is desirable tosynthesize the labels that are discrete or categorical. To
this end, we extend RON-Gauss to a multi-modal Gaussian generative model using the Gaussian Mixture Model(GMM) [12, 90]. Conceptually, each mode of GMM canbe used to capture the distribution of the data in eachclass. Thus, the entire dataset is modeled by the mixtureof these modes. In fact, many classifiers such as Linear
Discriminant Analysis (LDA) [46], Bayes Net [90], andmixture of Gaussians [90] also utilize this type of generative model, so this GMM extension has historically
been shown to be effective for classification.
In classification, the training label is categorical, i.e.
y ∈ {c1 , . . . , cL } for L-class classification. Algorithm 5presents an extension of RON-Gauss to GMM. The algorithm iterates through the data samples in each class. It
derives DP samples for each class in a similar procedure
to Algorithm 3 with one difference. For GMM, the dataRON-Gauss: Enhancing Utility in Non-Interactive Private Data Releasein each class are generated from the Gaussian generativemodel with the mean equal to the RON-projected DPclass-mean, i.e. WT µDP
c . This is to capture the multimodal nature of GMM. Since every DP sample drawn
from each iteration of step 1 belongs to the same class,the same training label is assigned for every synthesized
sample. Finally, after iterating through all classes, thealgorithm stacks the DP samples and training labels together before releasing the synthesized data.
We note that this algorithm assumes that each data
sample belongs to one class only, so each mode of Gaussian is derived from a disjoint set of data. This is
the common setting in supervised learning applications(cf. [12, 71, 90, 122]). In addition, to comply with thebounded DP notion we adopt throughout (cf. Remark2), the algorithm assumes that the number of samples ineach class nc is public information. Finally, we present
the DP analysis of Algorithm 5 as follows.
Theorem 5. Algorithm
differential privacy.

5preserves(µ + Σ )-Proof. Since the data partition is disjoint, and each class
has the same domain, the privacy budget used for eachclass does not add up from the parallel composition [38,85]. The proof then follows from that of Theorem 3.

5 Experiments
We demonstrate that RON-Gauss is effective across a
range of datasets and machine learning tasks via threeexperiments. For the datasets, we use a facial expression dataset [32], a sensor displacement dataset [6, 7],
and a social media dataset [67]. For the machine learning tasks, we use the clustering, classification, and regression applications. In non-interactive DP, the aim
is to release DP data such that the utility of the DPdata closely resembles that of the original data. Hence,to evaluate the quality of the non-interactive DP algorithms based on the utility measure commonly used forthe respective task (cf. Section 5.2). DP data with highquality, therefore, should provide the values of the utility measure close to that obtained from the non-private
data, and our experiments show that RON-Gauss canachieve this objective. We note that we choose taskcentric utility measures for our experiments since wewant to evaluate the approach based on how much insight can be gained from the synthesized data with respect to each task. However, in other settings, taskindependent evaluation metrics such as reconstruction

37

error or mutual information could also be appropriate.
We also compare our work to four previous approaches
that solely relied on either DR, or generative models.
Table 2 summarizes the experimental setups, and we
discuss them in detail as follows.

5.1 Datasets
5.1.1 Grammatical Facial Expression (GFE)
This dataset is based on facial expression analysis fromvideo images under Libras (a Brazilian sign language),and has 27,936 samples and 301 features [32]. There are
multiple clusters based on different grammatical expressions. The image features are designed to be informative of the facial expressions. However, the same features may be used to infer the individuals whose images
are included in the dataset. Hence, it is desirable to release a DP-protected dataset. We use this dataset forthe privacy-preserving clustering study on Algorithm 3.
5.1.2 Realistic Sensor Displacement (Realdisp)
This is a mobile-sensing dataset used for activity recognition [6, 7]. The features include readings of various
motion sensors, and the goal is to identify the activity being performed. However, the same features canpossibly be used to identify the individuals whose data
are in the dataset. Therefore, it is desirable to release a
DP-protected dataset. The dataset consists of 216,752
training samples, and 1,290 testing samples with 117
features. In our experiments, we use this dataset for theprivacy-preserving classification study with Algorithm
5. Specifically, we formulate it as a binary classification – identifying whether the subject is performing anaction that causes a location displacement or not, e.g.
walking, running, cycling, etc.
5.1.3 Buzz in Social Media (Twitter)
This dataset extracts 77 features from Twitter posts,
which are used to predict the popularity level of the
topic represented as a real value in [−1, 1] [67]. However,these features may also be used to infer the owner of
each tweet; thus it is desirable to instead release the DPprotected dataset. The dataset is divided into the training set of 573,820 samples, and the testing set of 4,715
samples. We use this dataset for privacy-preserving regression, and adopt Algorithm 4 for the experiments.

5.2 Setups
Since RON-Gauss algorithms require µ and Σ for themean and the covariance, respectively, given a fixed

38

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

Exp.

DatasetTraining Size

Feature Size

MetricML Alg.

DP Alg.

Clustering
Classification
Regression

GFE [32]
Realdisp [6, 7]
Twitter [67]27,936
216,752
573,820

301
117
77

S.C. (↑better)
Accuracy (↑better)
RMSE (↓better)

K-Means
SVM
KRR

Alg. 3Alg. 5
Alg. 4

Table 2. Summary of the experimental setups of the three experiments.

total privacy budget of , we allocate the budget as:µ = 0.3 and Σ = 0.7. The rationale is that the covariance is the more critical parameter in our algorithms,
and usually has higher complexity than the mean (Rp×pvs Rm ). For all experiments, we perform 100 trials andreport the average with the 95% confidence interval.
5.2.1 Clustering Setup
Clustering is unsupervised learning, so we apply Algorithm 3. We use K-means [71] as the clustering
method for its simplicity and efficiency, even for large
datasets, and use the Silhouette Coefficient (S.C.) [104]as the metric for evaluation. The number of clustersin K-means is set using the Silhouette analysis method[104, 110]. S.C. is defined as follows. For the sample xi
assigned to class y(i),– let a(i) be the average distance between xi and allother samples assigned to the same class y(i);– let b(i) be the average distance between xi and all
points assigned to the next nearest class.
b(i)−a(i), and S.C. is defined as:
Let sc(i) = max{b(i),a(i)}nS.C. =

1X
sc(i).
n[29, 95] as the classifier in all experiments. SVM is chosen since it has been shown to perform well on binaryclassification [23, 69, 108], and it has been proven –both empirically and theoretically – to generalize well[108, 122]. The evaluation metric is the traditional classification accuracy.
Since we consider the original training data as sensitive, we apply RON-Gauss to generate DP data thatare used to train machine learning models. However, wetest the machine learning models on the real test datain order to evaluate the ability of the DP training data
to capture the classification pattern of the real data.
5.2.3 Regression Setup
We use Algorithm 4 for regression, and use kernelridge regression (KRR) [71, 95] as the regressor due
to its large hypothesis class with proven theoretical error bound [108, 135]. The evaluation metric is the rootmean-square error (RMSE) [12, 71]. Finally, for comparison, we also provide a random-guess baseline of which
the prediction is drawn i.i.d. from a uniform distribution. Finally, we manage the train/test split in a similar
fashion to the above classification setup (Section 5.2.2).

i=1Intuitively, S.C. measures the average distance between
the sample and its class mean, normalized by the distance to the next nearest class mean. Its range is [−1, 1],
where higher value indicates better the performance.
We pick this metric for two reasons. First, as opposed to other metrics including ACC [131], ARI [64],or V-measure [102], S.C. does not require the knowledgeof the ground truth. This is vital both for our evaluationand for real-world applications, respectively because theground truth is not available for the synthetic data in
our evaluation, and it is often not available in practice,
too. Second, as suggested by Rousseeuw [104], S.C. depends primarily on the distribution of the data, but lesson the clustering algorithm used, so it is fitting for theevaluation of non-interactive private data release.

5.2.4 Comparison to Other Methods

5.2.2 Classification Setup

We compare RON-Gauss to these five methods for thefollowing reasons. The first comparison is to show thereal-world usability of RON-Gauss. The second and

For classification, we employ the GMM according to Algorithm 5, and use the support vector machine (SVM)

To provide context to the experimental results, we compare our approach to four previous works and a nonprivate baseline method as follows.
1. Real data: the non-private baseline approach, where
the result is obtained from the original data without
any modification.
2. Li et al. [78]: the method based on dimensionality
reduction via Bernoulli random projection on theidentity query.
3. Jiang et al. [66]: the method based on PCA on theidentity query.
4. Blum et al. [16]: exponential mechanism for noninteractive setting.
5. Liu [80]: parametric generative model without DR.

39

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

Method

Model

DR



S.C.

∆S.C.

Method

Model

DR



Accuracy (%)

Real data

−

−

−

.286

.00

Real data

-

-

-

89.61

Li et al. [78]

Identity

Bern.
Rand.

1.

.123±.000.16

Li et al. [78]

Identity

Bern.
Rand.

1.

65.04 ± 0.90

Jiang et al.
[66]

Identity

PCA

1.

.123±.000.16

Jiang et al. [66]

Identity

PCA

1.

54.51 ± 1.65

Blum et al. [16]1.

51.24 ± 1.83

Exp.
Mech.

−

1.

.026±.017

.26

Exp.
Mech.

-

Blum et al.
[16]

Liu [80]

GMM

-

1.

61.31 ± 0.65

Liu [80]

Gaussian−

1.

.092±.001.19

RON-Gauss

GMM

RON

1.

87.16 ± 0.27

RON-GaussGaussianRON

1.

.274±.015.01

Table 4. Classification results (Realdisp dataset).

Table 3. Clustering results (GFE dataset). ∆S.C. indicates theerror relative to the performance by real data.

5.3 Experimental Results

One consequence of the curse of dimensionality is theconcentration of the data mass near the surface of thehypercube encapsulating the data domain space. With
respect to our results, this leads to the observation that
despite using the unimodal Gaussian model the data
generated by RON-Gauss can form different clusters
around different parts of the hypercube surface. Thus,
if this unimodal distribution can represent the original
data well according to the DFM effect, it can provide
clustering performance close to that of the original data.

For methods with DR, the results reported are the best
results among varied dimensions.3

5.3.2 Privacy-Preserving Classification

third comparisons are to motivate the use of the Gaussian generative model over the identity query, and theremaining comparisons are to motivate DR via the RON
projection. For all previous methods, we use the parameters suggested by the respective authors, and we vary
the hyper-parameter before reporting the best result.

5.3.1 Privacy-Preserving Clustering
Table 3 summarizes the results for clustering, and thefollowing are main observations.
– Compared to the non-private baseline (real data),
RON-Gauss has almost identical performance with
only 0.01 additional error (4% error) while preserving strong privacy ( = 1.0).
– Compared to Li et al. [78] and Jiang et al. [66], who
use the identity query as opposed to the Gaussian
generative model, RON-Gauss has over 2x better
utility with the same privacy budget.
– Compared to Blum et al. [16] and Liu [80], who do
not use DR, RON-Gauss has over 10x and 3x better
utility with the same privacy budget.
For RON-Gauss, the optimal number of clusters basedon the Silhouette analysis is four. It is interesting tonote that RON-Gauss achieves good results despite using the unimodal Gaussian model. This can partially be
explained by the curse of dimensionality [9, 34, 48, 70].

3 As discussed by Chaudhuri et al. [26], in the real-world deployment, the parameter tuning process must be private as well.

Table 4 summarizes the classification results. The following are main observations.
– Compared to the non-private baseline (real data),
RON-Gauss has almost identical performance with2.45% additional error, while preserving strong privacy ( = 1.0).
– Compared to Li et al. [78] and Jiang et al. [66],
who use the identity query as opposed to GMM,
RON-Gauss has over 20% and 30% better utility,
respectively, with the same privacy budget.
– Compared to Blum et al. [16] and Liu [80], who
do not use DR, RON-Gauss has over 35% and 25%
better utility, respectively, with the same privacy.
5.3.3 Privacy-Preserving Regression
Table 5 summarizes the results for regression. The following are main observations.
– Compared to the non-private baseline (real data),
RON-Gauss actually performs statistically equallywell, while preserving strong privacy ( = 1.0).
– Compared to Li et al. [78] and Jiang et al. [66], who
use the identity query as opposed to the Gaussian
generative model, RON-Gauss has over 3x better
utility with the same privacy budget.

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

Method

Model

DR



RMSE (×10−2 )Real data

-

-

-

0.21

Li et al. [78]

Identity

Bern.
Rand.

1.

0.68 ± 0.01

Jiang et al. [66]

Identity

PCA

1.

0.68 ± 0.00

Blum et al. [16]

Exp.
Mech.

-

1.

0.62 ± 0.07

Liu [80]

Gaussian-1.

1.00 ± 0.12

RON-GaussGaussianRON

1.

0.21 ± 0.01

40

Fig. 1. Effects of dimension on the regression performance on
Twitter dataset.

Table 5. Regression results (Twitter dataset). RMSE is an error
metric, so lower values indicate better utility. (note: RMSE of
random guess is ∼ 57.20 × 10−2 ).

–Compared to Blum et al. [16] and Liu [80], who do
not use DR, RON-Gauss has over 3x and 5x better
utility with the same privacy budget.

5.3.4 Summary of Experimental Results
RON-Gauss outperforms all four other methods interms of utility across all three learning tasks. RONGauss also performs comparably well relative to the
maximum utility achieved by the non-private baselinein all tasks. The main results are concluded as follows.
– RON-Gauss provides performance close to that attainable from the non-private real data.
– Using the Gaussian generative model over the identity query has been shown to provide the utility gainof up to 2x, 30%, and 3x for clustering, classification, and regression, respectively.
– Using RON to reduce dimension of the data has
been shown to provide the utility gain of up to 10x,35%, and 5x, for clustering, classification, and regression, respectively.

6 Discussion
6.1 Effect of Dimension on the Utility
In Section 4, we discuss how RON projection can reduce
the level of noise required for DP. This effect can be observed experimentally as illustrated by Figure 1, whichshows the relationship between the dimension the data
are reduced to and the utility performance. Noticeably,
there is a gain in utility as the dimension is reduced.
Specifically, the peak performance is achieved at 4 dimensions in this case. This general trend is consistentacross different privacy budgets. Seeking the optimal

Fig. 2. Membership inference attack on RON-Gauss using Realdisp dataset. (Left) The attack accuracy against different valuesof . The dashed line shows the attack accuracy on the real datafor comparison. (Right) The tradeoff between the utility (classification accuracy) and the privacy leakage (the difference between
the membership inference accuracy and random guess at 50%).

dimension a priori is an interesting topic for future research on the RON-projection-based methods.

6.2 RON-Gauss Against MembershipInference Attack
Recent works have suggested using inference attacks tomeasure the susceptibility of the released data and identify the appropriate values of  for non-interactive differential privacy, e.g. [5, 114]. To evaluate RON-Gaussagainst inference attacks, we implement the membership inference attack proposed by Shokri et al. [114]using their published software [113]. This attack trains
shadow machine learning models and an attack model
to identify whether a given sample is in the dataset.
Since their attack is designed for a classification task,
we evaluate it on our classification experimental setup
using Realdisp data. For the attack, we use ten shadow
models and use neural network for the attack modelwith 0.01 learning rate trained on 50 epochs. These are
the default parameter values of the software used [113].
The results are shown in Figure 2. The test set ischosen such that a random guess on the membership
inference attack would yield an accuracy of 50%. FigureRON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

2 (Left) suggests that  values of 1.5 or less are appropriate for this setting since the performance of themembership inference attack is close to a random guess.
Figure 2 (Right) illustrates the utility-privacy tradeoff
based on this attack. The privacy leakage is defined as
the attack accuracy above the random guess level. In
other words, it measures how much the attack performs
better than a random guess. The utility is measured by
the classification accuracy similar to our classification
experiments in Section 5. The plot allows the practitioners to choose an  value that meets their utility-privacy
tradeoff. For example, if we require the privacy leakage to be less than 10%, the curve in Figure 2 (Right)
suggests that we can achieve almost 88% utility.
We note that the membership inference attack of
Shokri et al. [114] may not be the optimal inference attack against RON-Gauss, since it is a general attack
method not specifically tailored for our approach. We
leave the analysis of more advanced attacks that specifically utilize knowledge of the RON-Gauss mechanism
to future work, e.g. using hypothesis testing [5].

6.3 RON-Gauss as a Generative Model
Our work uses a parametric generative model to capture the essence of the unknown data distribution. Since
RON-Gauss involves DR as an important step, the
RON-Gauss model is inevitably lossy, i.e. there is information loss due to the use of the model itself. However, this loss is mitigated partly by the DFM effect,
which ensures that the data are close to Gaussian after
the RON projection. To illustrate the effectiveness of
this effect and of RON-Gauss as a parametric generative model, we test RON-Gauss purely for its quality asa generative model, i.e. without the DP component, on
the MNIST dataset [72, 73]. Since MNIST is typicallyused for classification, we use Algorithm 5 for RONGauss and set  → ∞ to leave out the effect of DP
noise. We project the data onto 392 dimensions – halfof the original dimensions of 784 – and synthesize thesamples, which are then reconstructed into the synthesized images. Examples of the synthesized images areshown in Figure 3. These images show good digit visibility, which indicates the potential of RON-Gauss as a
generative model.
However, admittedly, the visibility of the digits subsides gradually as we project the data onto lower dimensions. Particularly, we observe that, at dimensions lower
than 100, the digits are not very visible anymore. This
depicts that, despite its promise, RON-Gauss may not
yet be the universal model for every situation since there

41

Fig. 3. Synthesized MNIST images from the RON-Gauss model
without the DP component using half of the full dimensions.

remains the need to balance the information loss due to
DR. However, if sufficient information is retained, RONGauss has shown the potential to be a quality model byutilizing the DFM effect,as demonstrated by our experiments in Section 5.

6.4 The Design of µ and Σ for
RON-Gauss Algorithms
RON-Gauss Algorithms take as inputs two privacy parameters: µ and Σ . The algorithms are then shown topreserve (µ + Σ )-differential privacy. This means that,for a fixed total privacy budget of  = µ + Σ , we canchoose how much to allocate to µ and Σ in order tomaximize the utility of the synthesized data. In our experiments, we fix the ratio between the two based on theobservation about the sensitivity of the mean and thecovariance. However, the allocation can possibly be designed better by formulating it as an optimization problem that aims at maximizing the utility of the synthetic
data. Then, the optimal solution can be obtained using
grid search, random search, or Bayesian optimization[115]. We leave this as a possible future direction.

7 Conclusion
In this work, we combine two previously nonintersecting techniques – random orthonormal projection and Gaussian generative model – to provide
a solution to non-interactive private data release.
We propose the RON-Gauss model that exploits the
Diaconis-Freedman-Meckes effect, and present three algorithms for both unsupervised and supervised learning. We prove that our RON-Gauss model preserves differential privacy. Finally, our experiments on three
real-world datasets under clustering, classification, andregression applications show the strength of the method.
RON-Gauss provides significant performance improvement over previous approaches, and yields the utility
performance close to the non-private baseline, while preserving differential privacy with  = 1.

RON-Gauss: Enhancing Utility in Non-Interactive Private Data ReleaseAcknowledgement[11]

The authors would like to thank Sébastien Gambs forshepherding the paper, the anonymous reviewers fortheir valuable feedback, and Mert Al, Daniel Cullina,
and Alex Dytso for insightful discussions. This work is
supported in part by the National Science Foundation(NSF) under the grant CNS-1553437 and CCF-1617286,
an Army Research Office YIP Award, and faculty research awards from Google, Cisco, Intel, and IBM.

[12]
[13]

[14]

[15]

References
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan
McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.
Deep learning with differential privacy. In CCS, pages
308–318. ACM, 2016.
Gergely Acs, Claude Castelluccia, and Rui Chen. Differentially private histogram publishing through lossy compression. In ICDM, pages 1–10. IEEE, 2012.
Gergely Acs, Luca Melis, Claude Castelluccia, and Emiliano De Cristofaro. Differentially private mixture of generative neural networks. arXiv preprint arXiv:1709.04514,
2017.
Michael Backes, Pascal Berrang, Anne Hecksteden, Mathias Humbert, Andreas Keller, and Tim Meyer. Privacy inepigenetics: Temporal linkability of microrna expression
profiles. In Proceedings of the 25th USENIX Security Symposium, 2016.
Raghavendran Balu, Teddy Furon, and Sébastien Gambs.
Challenging differential privacy: the case of non-interactive
mechanisms. In European Symposium on Research in
Computer Security, pages 146–164. Springer, 2014.
Oresti Banos, Miguel Damas, Hector Pomares, Ignacio
Rojas, Mate Attila Toth, and Oliver Amft. A benchmark
dataset to evaluate sensor displacement in activity recognition. In UBICOMP, pages 1026–1035. ACM, 2012.
Oresti Banos, Claudia Villalonga, Rafael Garcia, Alejandro
Saez, Miguel Damas, Juan A. Holgado-Terriza, Sungyong
Lee, Hector Pomares, and Ignacio Rojas. Design, implementation and validation of a novel open framework foragile development of mobile health applications. Biomedical engineering online, 14(2):1, 2015.
Michael Barbaro and Tom Zeller Jr. A face is exposed foraol searcher no. 4417749. http://www.nytimes.com/2006/
08/09/technology/09aol.html, Aug 9, 2006 2006.
Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan,
and Uri Shaft. When is "nearest neighbor" meaningful? In
International conference on database theory, pages 217–
235. Springer, 1999.
Raffael Bild, Klaus A. Kuhn, and Fabian Prasser. Safepub:
A truthful data anonymization algorithm with strong privacy guarantees. Proceedings on Privacy Enhancing Technologies, 1:67–87, 2018.

[16]

[17]

[18]
[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

42

Vincent Bindschaedler, Reza Shokri, and Carl A. Gunter.
Plausible deniability for privacy-preserving data synthesis.
PVLDB, 10(5), 2017.
Christopher M. Bishop. Pattern recognition. Machine
Learning, 128, 2006.
Jeremiah Blocki, Avrim Blum, Anupam Datta, andOr Sheffet. The johnson-lindenstrauss transform itself
preserves differential privacy. In FOCS, pages 410–419.
IEEE, 2012.
Jeremiah Blocki, Anupam Datta, and Joseph Bonneau.
Differentially private password frequency lists. In NDSS,
2016.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi
Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART
symposium on Principles of database systems, pages 128–138. ACM, 2005.
Avrim Blum, Katrina Ligett, and Aaron Roth. A learningtheory approach to noninteractive database privacy. JACM,
60(2):12, 2013.
Claire McKay Bowen and Fang Liu. Differentially private
data synthesis methods. arXiv preprint arXiv:1602.01063,
2016.
George EP Box. Science and statistics. Journal of theAmerican Statistical Association, 71(356):791–799, 1976.
David S Broomhead and David Lowe. Radial basis functions, multi-variable functional interpolation and adaptive
networks. Technical report, Royal Signals and Radar Establishment Malvern (United Kingdom), 1988.
Andreas Buja, Dianne Cook, and Deborah F. Swayne. Interactive high-dimensional data visualization. Journal ofcomputational and graphical statistics, 5(1):78–99, 1996.
Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential
privacy. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 1–10. ACM, 2014.
John Burkardt. Normal_dataset: Generate multivariate normal random datasets. https://people.sc.fsu.edu/~jburkardt/cpp_src/normal_dataset/normal_dataset.html,
12/9/2009 2009.
Hyeran Byun and Seong-Whan Lee. Applications of support vector machines for pattern recognition: A survey. In
Pattern recognition with support vector machines, pages
213–236. Springer, 2002.
Joseph A. Calandrino, Ann Kilzer, Arvind Narayanan, Edward W. Felten, and Vitaly Shmatikov. "you might also
like:" privacy risks of collaborative filtering. In S&P, pages
231–246. IEEE, 2011.
Augustin-Louis Cauchy. Sur les formules qui resultent del’emploie du signe et sur> ou<, et sur les moyennes entre
plusieurs quantites. Cours d’Analyse, 1er Partie: Analyse
algebrique, pages 373–377, 1821.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D.
Sarwate. Differentially private empirical risk minimization.
JMLR, 12(Mar):1069–1109, 2011.
Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha.
Near-optimal differentially private principal components. In
NIPS, pages 989–997, 2012.
Graham Cormode, Cecilia Procopiuc, Divesh Srivastava,
Entong Shen, and Ting Yu. Differentially private spatial

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

[29]
[30]
[31]

[32]

[33]

[34]

[35]
[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

decompositions. In ICDE, pages 20–31. IEEE, 2012.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20(3):273–297, 1995.
Paul Cuff and Lanqing Yu. Differential privacy as a mutual
information constraint. In CCS, pages 43–54. ACM, 2016.
Wei-Yen Day and Ninghui Li. Differentially private publishing of high-dimensional data using sensitivity control. In
CCS, pages 451–462. ACM, 2015.
Fernando de Almeida Freitas, Sarajane Marques Peres,
Clodoaldo Aparecido de Moraes Lima, and Felipe Venancio
Barbosa. Grammatical facial expressions recognition withmachine learning. In FLAIRS Conference, 2014.
Persi Diaconis and David Freedman. Asymptotics of graphical projection pursuit. The annals of statistics, pages
793–815, 1984.
David L Donoho et al. High-dimensional data analysis:
The curses and blessings of dimensionality. AMS mathchallenges lecture, 1(2000):32, 2000.
Cynthia Dwork. Differential privacy, pages 1–12. Automata, languages and programming. Springer, 2006.
Cynthia Dwork. Differential privacy: A survey of results.
In International Conference on Theory and Applications ofModels of Computation, pages 1–19. Springer, 2008.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry,
Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy
via distributed noise generation. In Annual International
Conference on the Theory and Applications of Cryptographic Techniques, pages 486–503. Springer, 2006.
Cynthia Dwork and Jing Lei. Differential privacy and robust
statistics. In Proceedings of the forty-first annual ACM
symposium on Theory of computing, pages 371–380. ACM,
2009.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam
Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265–284.
Springer, 2006.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentiallyprivate data release: efficient algorithms and hardness results. In STOC, pages 381–390. ACM, 2009.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in
Theoretical Computer Science, 9(3-4):211–407, 2014.
Cynthia Dwork and Adam Smith. Differential privacy forstatistics: What we know and what we want to learn. Journal of Privacy and Confidentiality, 1(2):2, 2010.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and
Li Zhang. Analyze gauss: optimal bounds for privacypreserving principal component analysis. In STOC, pages
11–20. ACM, 2014.
Ulfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova.
Rappor: Randomized aggregatable privacy-preserving ordinal response. In CCS, pages 1054–1067. ACM, 2014.
Giulia Fanti, Vasyl Pihur, and Ulfar Erlingsson. Building
a rappor with the unknown: Privacy-preserving learning of
associations and data dictionaries. Proceedings on Privacy
Enhancing Technologies, 2016(3):41–61, 2016.
Ronald A. Fisher. The use of multiple measurements intaxonomic problems. Annals of eugenics, 7(2):179–188,
1936.

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]
[63]

43

Ronald Aylmer Fisher. Theory of statistical estimation. In
Mathematical Proceedings of the Cambridge PhilosophicalSociety, volume 22, pages 700–725. Cambridge University
Press, 1925.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani.
The elements of statistical learning, volume 1. Springer
series in statistics Springer, Berlin, 2001.
Alan Genz, Frank Bretz, Tetsuhisa Miwa, Xuefei Mi,
Friedrich Leisch, Fabian Scheip, Bjoern Bornkamp, Martin Maechler, and Torsten Hothorn. Package mvtnorm,
02/02/2016 2016.
Jorgen Pedersen Gram. Uber die entwicklung reeller
funktionen in reihen mittels der methode der kleinsten
quadrate. Journal fur reihe und angewandte Mathematik,
94:41–73, 1883.
Saikat Guha, Mudit Jain, and Venkata N. Padmanabhan.
Koi: A location-privacy platform for smartphone apps.
In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation, pages 14–14.
USENIX Association, 2012.
Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. Theory of
Cryptography, pages 339–356, 2012.
Andreas Haeberlen, Benjamin C. Pierce, and Arjun
Narayan. Differential privacy under fire. In USENIX Security Symposium, 2011.
Marjorie G. Hahn and Michael J. Klass. The multidimensional central limit theorem for arrays normed by affine
transformations. The Annals of Probability, pages 611–623,
1981.
Peter Hall and Ker-Chau Li. On almost linearity of low
dimensional projections from high dimensional data. The
annals of Statistics, pages 867–889, 1993.
Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and functional data. Journalof Machine Learning Research, 14(Feb):703–727, 2013.
Moritz Hardt, Katrina Ligett, and Frank McSherry. A
simple and practical algorithm for differentially private data
release. In NIPS, pages 2339–2347, 2012.
Moritz Hardt and Guy N. Rothblum. A multiplicative
weights mechanism for privacy-preserving data analysis.
In FOCS, pages 61–70. IEEE, 2010.
Moritz Hardt, Guy N. Rothblum, and Rocco A. Servedio.
Private data release via learning thresholds. In Proceedingsof the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 168–187. Society for Industrial andApplied Mathematics, 2012.
Michael Hay, Ashwin Machanavajjhala, Gerome Miklau,
Yan Chen, and Dan Zhang. Principled evaluation of differentially private algorithms using dpbench. In ICMD, pages
139–154. ACM, 2016.
Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan
Suciu. Boosting the accuracy of differentially private histograms through consistency. Proceedings of the VLDB
Endowment, 3(1-2):1021–1032, 2010.
Roger A. Horn and Charles R. Johnson. Matrix analysis.
Cambridge university press, 2012.
Harold Hotelling. Analysis of a complex of statistical variables into principal components. Journal of educational
psychology, 24(6):417, 1933.

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

[64]
[65]

[66]

[67]

[68]

[69]

[70]

[71]
[72]

[73]

[74]

[75]

[76]

[77]

[78]

[79]

Lawrence Hubert and Phipps Arabie. Comparing partitions.
Journal of classification, 2(1):193–218, 1985.
William James and Charles Stein. Estimation withquadratic loss. In Proceedings of the fourth Berkeley
symposium on mathematical statistics and probability,
volume 1, pages 361–379, 1961.
X. Jiang, Z. Ji, S. Wang, N. Mohammed, S. Cheng, and
L. Ohno-Machado. Differential-private data publishing
through component analysis. Transactions on data privacy,
6(1):19–34, Apr 2013.
Francois Kawala, Ahlame Douzal-Chouakria, Eric Gaussier,and Eustache Dimert. Predictions d’activite dans les reseaux sociaux en ligne. In 4ieme Conference sur les Modeles et l’Analyse des Reseaux: Approches Mathamatiques etInformatiques, page 16, 2013.
Krishnaram Kenthapadi, Aleksandra Korolova, Ilya
Mironov, and Nina Mishra. Privacy via the johnsonlindenstrauss transform. Journal of Privacy and Confidentiality, 5(1):2, 2013.
Ross D. King, Cao Feng, and Alistair Sutherland. Statlog:
comparison of classification algorithms on large real-world
problems. Applied Artificial Intelligence an International
Journal, 9(3):289–333, 1995.
Mario Köppen. The curse of dimensionality. In 5th Online
World Conference on Soft Computing in Industrial Applications (WSC5), volume 1, pages 4–8, 2000.
S. Y. Kung. Kernel Methods and Machine Learning. Cambridge University Press, Cambridge, UK, 2014.
Yann LeCun, Leon Bottou, Yoshua Bengio, and Patrick
Haffner. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–2324,
1998.
Yann Lecun, Corinna Cortes, and Christopher J.C Burges.
MNIST handwritten digit database. http://yann.lecun.
com/exdb/mnist/, 1998.
David Leoni. Non-interactive differential privacy: a survey. In Proceedings of the First International Workshop on
Open Data, pages 40–52. ACM, 2012.
Chao Li, Michael Hay, Gerome Miklau, and Yue Wang. A
data-and workload-aware algorithm for range queries under
differential privacy. Proceedings of the VLDB Endowment,
7(5):341–352, 2014.
Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor,
and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB
Journal, 24(6):757–781, 2015.
H. Li, L. Xiong, and X. Jiang. Differentially private
synthesization of multi-dimensional data using copulafunctions. Advances in database technology : proceedings.International Conference on Extending Database Technology, 2014:475–486, 2014.
Yang D. Li, Zhenjie Zhang, Marianne Winslett, and Yin
Yang. Compressive mechanism: Utilizing sparse representation in differential privacy. In WPES, pages 177–182. ACM,
2011.
Changchang Liu and Prateek Mittal. Linkmirage: Enabling
privacy-preserving analytics on social relationships. In
23nd Annual Network and Distributed System Security
Symposium, NDSS, pages 21–24, 2016.

[80]
[81]

[82]

[83]

[84]
[85]

[86]

[87]

[88]
[89]

[90]

[91]

[92]

[93]

[94]

[95]

[96]

44

Fang Liu. Model-based differential private data synthesis.
arXiv preprint arXiv:1606.08052, 2016.
Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. Privacy: Theory meetspractice on the map. In Data Engineering, 2008. ICDE
2008. IEEE 24th International Conference on, pages 277–
286. IEEE, 2008.
David McClure and Jerome P. Reiter. Differential privacy
and statistical disclosure risk measures: An investigation
with binary synthetic data. Trans.Data Privacy, 5(3):535–
552, 2012.
Frank McSherry and Ilya Mironov. Differentially private
recommender systems: building privacy into the netflix
prize contenders. In Proceedings of the 15th ACM SIGKDD
international conference on Knowledge discovery and data
mining, pages 627–636. ACM, 2009.
Frank McSherry and Kunal Talwar. Mechanism design via
differential privacy. In FOCS, pages 94–103. IEEE, 2007.
Frank D McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In
Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 19–30. ACM, 2009.
Elizabeth Meckes. Approximation of projections of random
vectors. Journal of Theoretical Probability, 25(2):333–352,
2012.
Elizabeth Meckes. Projections of probability distributions:
A measure-theoretic Dvoretzky theorem, pages 317–326.
Geometric Aspects of Functional Analysis. Springer, 2012.
Carl D. Meyer. Matrix analysis and applied linear algebra,
volume 2. Siam, 2000.
Noman Mohammed, Rui Chen, Benjamin Fung, andPhilip S. Yu. Differentially private data release for data
mining. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining,
pages 493–501. ACM, 2011.
Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. The MIT Press, One Rogers Street Cambridge
MA 02142-1209, 2012.
Arvind Narayanan, Hristo Paskov, Neil Zhenqiang Gong,
John Bethencourt, Emil Stefanov, Eui Chul Richard Shin,and Dawn Song. On the feasibility of internet-scale author
identification. In S&P, pages 300–314. IEEE, 2012.
David CL Ngo, Andrew BJ Teoh, and Alwyn Goh. Biometric hash: high-confidence face recognition. IEEE
transactions on circuits and systems for video technology,
16(6):771–775, 2006.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.
Smooth sensitivity and sampling in private data analysis. In
STOC, pages 75–84. ACM, 2007.
II Ororbia, G. Alexander, Fridolin Linder, and Joshua
Snoke. Privacy protection for natural language records:
Neural generative models for releasing synthetic twitter
data. arXiv preprint arXiv:1606.01151, 2016.
Fabian Pedregosa, Gael Varoquaux, Alexandre Gramfort,
Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, and Vincent
Dubourg. Scikit-learn: Machine learning in python. JMLR,
12(Oct):2825–2830, 2011.
Nicholas G. Polson and Steven L. Scott. Data augmentation for support vector machines. Bayesian Analysis,RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release

6(1):1–23, 2011.
Netflix Prize. http://www.netflixprize.com/.
Davide Proserpio, Sharon Goldberg, and Frank McSherry.
Calibrating data to sensitivity in private data analysis:
a platform for differentially-private analysis of weighted
datasets. PVLDB, 7(8):637–648, 2014.
[99] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Differentially private grids for geospatial data. In ICDE, pages
757–768. IEEE, 2013.
[100] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms. Proceedings of the VLDB Endowment,
6(14):1954–1965, 2013.
[101] Raul Rojas. Why the normal distribution. Freis Universitat
Berlin lecture notes, 2010.
[102] Andrew Rosenberg and Julia Hirschberg. V-measure: A
conditional entropy-based external cluster evaluation measure. In EMNLP-CoNLL, volume 7, pages 410–420, 2007.
[103] Gunter Rote. A new metric between polygons. In Werner
Kuich, editor, ICALP: International Colloquium on Automata, Languages, and Programming, pages 404–415.
Springer, Berlin, Heidelberg, July 1992.
[104] Peter J. Rousseeuw. Silhouettes: a graphical aid to theinterpretation and validation of cluster analysis. Journal ofComputational and Applied Mathematics, 20:53–65, 1987.
[105] Havard Rue and Leonhard Held. Gaussian Markov random
fields: theory and applications. CRC press, 2005.
[106] Alessandra Sala, Xiaohan Zhao, Christo Wilson, Haitao
Zheng, and Ben Y. Zhao. Sharing graphs using differentially private graph models. In Proceedings of the 2011
ACM SIGCOMM conference on Internet measurement conference, pages 81–98. ACM, 2011.
[107] Erhard Schmidt. Zur theorie der linearen und nichtlinearen
integralgleichungen. Mathematische Annalen, 63(4):433–
476, 1907.
[108] Bernhard Scholkopf and Alexander J. Smola. Learning withkernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[109] Hermann Amandus Schwarz. Uber ein die Flachen kleinsten Flacheninhalts betreffendes Problem der Variationsrechnung, pages 223–269. Gesammelte Mathematische
Abhandlungen. Springer, 1890.
[110] Scikit-learn. Selecting the number of clusters with silhouette analysis on kmeans clustering. http://scikitlearn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html#sphx-glr-auto-examples-clusterplot-kmeans-silhouette-analysis-py.
[111] SciPy.org. scipy.stats.multivariate_normal. https://docs.
scipy.org/doc/scipy-0.14.0/reference/generated/scipy.stats.
multivariate_normal.html, 5/11/2014 2014.
[112] Reza Shokri and Vitaly Shmatikov. Privacy-preserving deeplearning. In CCS, pages 1310–1321. ACM, 2015.
[113] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly
Shmatikov. https://github.com/csong27/membershipinference.
[114] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly
Shmatikov. Membership inference attacks against machinelearning models. In Security and Privacy (SP), 2017 IEEE
Symposium on, pages 3–18. IEEE, 2017.
[97]
[98]

45

[115] Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms.
In Advances in neural information processing systems,
pages 2951–2959, 2012.
[116] Open SNP. http://opensnp.org/.
[117] Florian Tramer, Zhicong Huang, Jean-Pierre Hubaux, andErman Ayday. Differential privacy with bounded priors:
reconciling utility and privacy in genome-wide association
studies. In CCS, pages 1286–1297. ACM, 2015.
[118] Jonathan Ullman and Salil Vadhan. Pcps and the hardnessof generating private synthetic data. In Theory of Cryptography Conference, pages 400–416. Springer, 2011.
[119] Jalaj Upadhyay. Circulant matrices and differential privacy.
analysis, 16:47, 2014.
[120] Jalaj Upadhyay. Randomness efficient fast-johnsonlindenstrauss transform with applications in differential privacy and compressed sensing. arXiv preprint
arXiv:1410.2470, 2014.
[121] Vladimir Vapnik. Estimation of dependences based on
empirical data. Springer Science & Business Media, 2006.
[122] Vladimir Vapnik. The nature of statistical learning theory.
Springer science & business media, 2013.
[123] Larry Wasserman. All of statistics: a concise course instatistical inference. Springer Science & Business Media,
2013.
[124] Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375–389, 2010.
[125] Eric W. Weisstein. Sphere. http://mathworld.wolfram.
com/Sphere.html.
[126] Wikipedia. Categorical variable. https://en.wikipedia.org/
wiki/Categorical_variable#cite_ref-yates_1-0, 2017.
[127] Oliver Williams and Frank McSherry. Probabilistic inference
and differential privacy. In NIPS, pages 2451–2459, 2010.
[128] Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. Differential privacy via wavelet transforms. IEEE Transactions
on Knowledge and Data Engineering, 23(8):1200–1214,
2011.
[129] Yonghui Xiao and Li Xiong. Protecting locations withdifferential privacy under temporal correlations. In CCS,
pages 1298–1309. ACM, 2015.
[130] Yonghui Xiao, Li Xiong, Liyue Fan, and Slawomir
Goryczka. Dpcube: differentially private histogram release through multidimensional partitioning. arXiv preprint
arXiv:1202.5358, 2012.
[131] Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised
deep embedding for clustering analysis. In ICML, pages
478–487, 2016.
[132] Chugui Xu, Ju Ren, Yaoxue Zhang, Zhan Qin, and Kui
Ren. Dppro: Differentially private high-dimensional data
release via random projection. IEEE Transactions on Information Forensics and Security, 2017.
[133] Jia Xu, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, Ge Yu,
and Marianne Winslett. Differentially private histogram
publication. The VLDB Journal, 22(6):797–822, 2013.
[134] Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. Privbayes: Private data
release via bayesian networks. In Proceedings of the 2014
ACM SIGMOD international conference on Management of
data, pages 1423–1434. ACM, 2014.

RON-Gauss: Enhancing Utility in Non-Interactive Private Data Release[135] Tong Zhang. Learning bounds for kernel regression using effective data dimensionality. Neural Computation,
17(9):2077–2098, 2005.
[136] Xiaojian Zhang, Rui Chen, Jianliang Xu, Xiaofeng Meng,and Yingtao Xie. Towards accurate histogram publication
under differential privacy. In SDM, pages 587–595. SIAM,
2014.
[137] Shuheng Zhou, Katrina Ligett, and Larry Wasserman. Differential privacy with compression. In ISIT, pages 2718–
2722. IEEE, 2009.

46

where µ is the sample mean specific to the instance ofthe dataset. Hence, the neighboring datasets may havedifferent means. Then, the sensitivity can be derived asfollows.
Lemma 6. The L1 -sensitivity of the MLE of the co√√variance matrix is (2 p + 2n p)/n.
Proof. For neighboring datasets X, X0 ,s(f ) = supn
1 X(xei − µ)(xei − µ)Tni=1

A Proof of Lemma 3
Proof. The proof uses the property of orthogonal projection in a vector space. First, notice that WT x F =WWT x F , which can be verified as follows.

p
WT x F = tr(xT WWT x)p= tr(xT WWT WWT x)= WWT x F ,where the second equality is from the fact that WT W =I. Then, notice that P = WWT is a projection matrix
with p orthonormal basis as the columns of W (cf. [88,Chapter 5]). Therefore, the idempotent property of P
can be used as,
WT x F = WWT x F = kPxkF= hPx, PxiF = hPx, xiF .
The last equality can be verified as follows. Let
Px ∈ P, and let x⊥ = x − Px ∈ P ⊥ ,then hPx, xiF = Px, Px + x⊥ F = hPx, PxiF +Px, x⊥ F = hPx, PxiF from the additivity of theinner product and the fact that Px, x⊥ F = 0 by
construction. Then, using the Cauchy-Schwarz inequality, kPxk2F = hPx, xi2F ≤ kPxkF kxkF , and, hence,
kPxkF = WWT x F = WT x F ≤ kxkF .

B L1 -Sensitivity of the MLE of
the Covariance
Consider the maximum likelihood estimate (MLE) [47]for the covariance matrix, which is an unbiased estimate(cf. [123]):n

1X
ΣM LE =
(xei − µ)(xei − µ)T ,
n
i=1

n
X
−
(xei0 − µ0 )(xei0 − µ0 )T
i=1

= sup

1
(
n

1
n
X

xei xei T − nµµT )

i=1

n
X
T
xei0 xei0 − nµ0 µ0T )
−(
i=1

1

T
1
= sup
(xei xei T − xei0 xei0 ) + n(µ0 µ0T − µµT )
n
1

≤ sup

1
( xei xei Tn1T+ xei0 xei0)
1

+ µ0 µ0T 1 + µµT 1
√
2 p
√
≤ sup
xei xei T+ 2 p µ0 µ0T
n
F
√
2 p
√
+ 2 p.
≤nF

The last inequality is due to the following observation:PP
kµkF = n1 k xei kF ≤ n1
kxei kF = 1.