# Noise-Aware Statistical Inference with Differentially Private Synthetic Data

###### Abstract

While generation of synthetic data under differential privacy (DP) has
received a lot of attention in the data privacy community, analysis of
synthetic data has received much less. Existing work has shown that simply
analysing DP synthetic data as if it were real does not produce valid
inferences of population-level quantities. For example, confidence intervals
become too narrow, which we demonstrate with a simple experiment. We tackle
this problem by combining synthetic data analysis techniques from the field of
multiple imputation (MI), and synthetic data generation using noise-aware (NA)
Bayesian modeling into a pipeline NA+MI that allows computing accurate
uncertainty estimates for population-level quantities from DP synthetic data.
To implement NA+MI for discrete data generation using the values of marginal
queries, we develop a novel noise-aware synthetic data generation algorithm
NAPSU-MQ using the principle of maximum entropy. Our experiments demonstrate
that the pipeline is able to produce accurate confidence intervals from DP
synthetic data. The intervals become wider with tighter privacy to accurately
capture the additional uncertainty stemming from DP noise.

[name=Theorem, numberwithin=section]theorem [name=Lemma, sibling=theorem]lemma
[name=Definition, sibling=theorem]definition [name=Corollary,
sibling=theorem]corollary [name=Assumption, sibling=theorem]assumption
[name=Conjecture, sibling=theorem]conjecture

Noise-Aware Statistical Inference with Differentially Private Synthetic Data

Ossi Räisä University of Helsinki<EMAIL_ADDRESS>Joonas Jälkö
University of Helsinki111Work done while at Aalto University.
<EMAIL_ADDRESS>
Samuel Kaski Aalto University, University of Manchester<EMAIL_ADDRESS>Antti Honkela University of Helsinki<EMAIL_ADDRESS>
##  1 INTRODUCTION

Availability of data for research is constrained by the dilemma between
privacy preservation and potential gains obtained from sharing. As a result,
many datasets are kept confidential to mitigate the possibility of privacy
violations, with access only granted to researchers after a lengthy approval
process, if at all, slowing down research.

One approach to solving the dilemma between free access and confidentiality is
releasing synthetic data, as proposed by [50]. The idea is that the _data
holder_ releases a synthetic dataset that is based on a real dataset. _Data
analysts_ can use the synthetic dataset instead of the real one for their
_downstream analysis_.

The synthetic dataset should maintain population-level statistical properties
of the original, which are of interest to the analysts. Privacy-protection of
the synthetic data can be guaranteed by employing differential privacy (DP)
[14], which offers provable protection, unlike non-DP synthetic data
generation methods.

The analysts of synthetic data should be able to draw valid conclusions on the
data generating process (DGP) of the real data using the synthetic data. An
important component of the conclusion in any scientific research is estimation
of uncertainty, usually in the form of a confidence interval or $p$-value.
However, as [55] point out, simply using synthetic data as if it were real
data only allows drawing conclusions about the synthetic data generating
process, not the real DGP.

Figure 1:  Toy data experiment results of logistic regression on 3 binary
variables, showing that PGM, PEP, RAP and PrivBayes are overconfident, even
with almost no privacy ($\epsilon=100$), PrivLCM is underconfident, while our
algorithm is well-calibrated. The first two panels from the left show the
fraction of the 95% confidence intervals that contain the true parameter value
in 100 repeats, with the target confidence level of 95% highlighted by a black
line. $\epsilon$ quantifies the strength of the privacy guarantee, ranging
from strong ($\epsilon=0.1$) to meaningless ($\epsilon=100$). The other
privacy parameter is fixed at $\delta=2.5\cdot 10^{-7}$. The third panel shows
the confidence intervals from synthetic data generated by our mechanism for
$\epsilon=0.5$, and the fourth panel shows the confidence intervals from PGM.
The third and fourth panels show that the overconfidence stems from intervals
that are too narrow, a result of failing to account for all uncertainty.

The issues of using synthetic data in place of real data are especially
apparent with DP, as DP requires adding noise to the synthetic data generation
process. We illustrate this with a simple toy data experiment. We generate
3-dimensional binary data, where one variable is generated from logistic
regression on the other two, serving as the original dataset. Then, we
generate synthetic data from the original data and compute confidence
intervals for the coefficients of the logistic regression from the synthetic
data. A more detailed description of the setup is given in Section 5.1. As
shown by Figure 1, the existing algorithms PGM [41], PEP [35], RAP [2] and
PrivBayes [59] do not provide valid confidence intervals, as they treat the
synthetic data as real data. Only our method NA+MI and PrivLCM [44] produce
valid confidence intervals. However, PrivLCM is too conservative, producing
much wider intervals, as shown by Figure 3(a), and does not scale to complex
datasets.

Our solution to overconfident uncertainty estimates builds on Rubin’s original
work on synthetic data generation [50]. He proposed generating multiple
synthetic datasets, running the analysis task on each of them, and combining
the results with simple combining rules called _Rubin’s rules_ [46, 47]. This
workflow is modeled after _multiple imputation_ [49], where it is used to deal
with missing data. Generating multiple synthetic datasets allows the combining
rules to account for the additional uncertainty that comes from the synthetic
data generation process, which includes DP noise when the synthetic data is
generated using a Bayesian model that accounts for the DP noise. We call the
combined pipeline of noise-aware (NA) private synthetic data generation and
analysis with multiple imputation (MI) the _NA+MI pipeline_. We give a more
detailed description in Section 2.

To implement the NA step, we develop an algorithm called _Noise-Aware Private
Synthetic data Using Marginal Queries_ (NAPSU-MQ), that generates synthetic
data from discrete tabular datasets using the noisy values of preselected
marginal queries. We describe NAPSU-MQ in Section 4. In Section 5 and
Supplemental Section G, we evaluate NAPSU-MQ on the UCI Adult and UCI US
Census (1990) datasets, showing that it can produce accurate confidence
intervals.

###  1.1 Related Work

There is a sizable literature on DP synthetic data generation. Most recent
work in the area either releases the values of a set of simple queries, such
as counting queries, under DP and uses them as the basis of synthetic data
[22, 10, 59, 41, 39, 40, 38, 4, 7, 53, 35, 2, 44], or trains some kind of
generative model, often a GAN, using the whole real dataset under DP [56, 58,
9, 36, 27]. There are also hybrid approaches that use sophisticated queries
that can capture all features of the dataset, and train a generative model
using those [21, 33]. Of the existing DP synthetic data generation algorithms,
NAPSU-MQ is closest to the PGM algorithm [41], which does maximum likelihood
estimation with the same data model as NAPSU-MQ instead of noise-aware
Bayesian inference. We describe this connection in more detail in Supplemental
Section D.

Rubin’s rules were originally developed for analyses on missing data, as part
of an approach called multiple imputation [49], which was later applied to
generate and analyse synthetic data [50] without DP. The variant of Rubin’s
rules that we use, and describe in Supplemental Section B, was developed
specifically for synthetic data generation [46, 47]. [45] have developed
simpler alternatives to Rubin’s rules under more restrictive assumptions, but
these assumptions rule out DP data synthesisers.

Rubin’s rules have not been widely used with DP synthetic data generation, and
we are only aware of four existing works studying the combination. [8] studied
Rubin’s rules with a very simple early synthetic data generation algorithm,
and concluded that Rubin’s rules are not appropriate for that algorithm. [61]
found that some simple one-dimensional methods developed by the multiple
imputation community are in fact DP, but not with practically useful privacy
bounds. [44] propose using Rubin’s rules with the noise-aware synthetic data
generation algorithm PrivLCM, but they only consider computing confidence
intervals of query values on the real dataset, not confidence intervals of
population parameters of arbitrary downstream analyses. [34] proposes
generating multiple synthetic datasets like we do, but their pipeline requires
splitting the privacy budget between each synthetic dataset, severely limiting
the number of datasets that can be generated with acceptable utility, and
their convergence theory assumes weak privacy111The theory applies
asymptotically when $\epsilon\to\infty$..

Noise-aware uncertainty estimates have been developed for specific DP
analyses. Examples include frequentist linear regression [16] and general
recipes for DP analyses without synthetic data [17, 11]. Bayesian examples
include posterior inference for simple exponential family models [5], linear
regression [6], generalised linear models [32], and approximate Bayesian
computation [20]. The AIM algorithm for synthetic data generation [40]
provides valid confidence intervals on the query values of the real dataset,
while NAPSU-MQ and the other methods mentioned provide confidence intervals on
population values.

Several works study techniques for mitigating the effect of DP noise. [55]
point out the importance of noise-aware synthetic data analysis with DP and
use publicly available data to augment the analysis and correct for the DP
noise in Bayesian inference. Other examples include bias reduction [19] and
averaging GANs [43].

While some of the existing works address uncertainty estimates for specific
analyses of synthetic data under DP, there is no existing method for proper
uncertainty estimation for general downstream analyses of population-level
quantities. We fill this gap with the NA+MI pipeline, which we implement for
discrete tabular data with NAPSU-MQ.

##  2 THE NA+MI PIPELINE

The early work on synthetic data generation with multiple imputation showed
that computing accurate uncertainty estimates with synthetic data requires
accounting for the additional uncertainty that comes from generating the
synthetic data [50, 46]. [50] proposed generating multiple synthetic datasets
$X^{Syn}_{i}$ from the posterior predictive distribution $p(X^{*}|X)$, where
$X^{*}$ is a prediction of a future dataset, and $X$ is the observed real
dataset. The downstream analysis is run on each $X^{Syn}_{i}$ as if
$X^{Syn}_{i}$ were the real dataset, and the results are combined using
specialised combining rules [46].

The generation of multiple datasets from $p(X^{*}|X)$ is necessary to give the
combining rules a way to estimate the variance of the synthetic data
generation process, which would not be possible if only a single dataset was
generated. For a parametric model,
$p(X^{*}|X)=\int_{\Theta}p(X^{*}|\theta)p(\theta|X)\mathrm{d}\theta$, where
$\theta\in\Theta$ is the parameter, $p(X^{*}|\theta)$ is the likelihood, and
$p(\theta|X)$ is the posterior of the parameter. $X^{Syn}_{i}$ is then
generated in two steps: first $\theta_{i}\sim p(\theta|X)$ is sampled, then
$X^{Syn}_{i}\sim p(X^{*}|\theta_{i})$.

The combining rules require including the posterior distribution $p(\theta|X)$
[46] for sampling $X^{Syn}_{i}$, so a non-Bayesian model that samples
$X^{Syn}_{i}\sim p(X^{*}|\hat{\theta})$ for some point-estimate $\hat{\theta}$
is not suitable for synthetic data generation with Rubin’s rules.

Requiring the synthetic data generation to be DP complicates the picture, as
only a noisy observation $\tilde{s}$ of $X$ can be made, which means that we
must use $p(\theta|\tilde{s})$ instead of $p(\theta|X)$. We call inference
algorithms for $p(\theta|\tilde{s})$ that account for the noise added for DP
_noise-aware_. The combination of noise-aware inference and multiple
imputation is the NA+MI pipeline, which we summarise in Figure 2. First, the
data holder runs inference on a noise-aware Bayesian model using the private
data, which we call the NA step. Different implementations of the NA step may
set different requirements on the form of $X$, the type of DP noise, and may
provide different privacy guarantees.

Data Holder (NA step)Data Analyst (MI step)ptData $X$Noise-awareGenerator . .
. SyntheticData $X^{Syn}_{1}$SyntheticData $X^{Syn}_{m}$ . . . AnalysisResult
$q_{1},v_{1}$AnalysisResult
$q_{m},v_{m}$CombinedResult$t_{\nu}(\bar{q},T^{*})$Privacy Barrier Figure 2:
NA+MI pipeline for noise-aware DP synthetic data generation and statistical
inference. The nodes shaded in blue are computed by the data holder, and the
nodes shaded in orange are computed by the data analyst. All nodes except Data
(with red border) can be released to the public. The synthetic datasets can be
generated by either party because the Generator is also released by the data
holder.

After the inference, the data holder generates multiple synthetic datasets.
The data holder can also release the posterior distribution in addition to the
synthetic datasets, so that the analyst can also generate synthetic datasets
if needed. Due to the post-processing immunity of DP (Theorem 3), releasing
multiple synthetic datasets, or the posterior distribution, does not
compromise privacy.

For each synthetic dataset, the analyst runs their analysis, and combines the
results using multiple imputation [46, 47, 48]. We call this the MI step. For
frequentist downstream analyses, we use Rubin’s rules, which require that each
analysis produces a point estimate $q_{i}$, and a variance estimate $v_{i}$
for the point estimate. The point estimates $q_{1},\dotsc,q_{m}$ and the
variance estimates $v_{1},\dotsc,v_{m}$ are fed to Rubin’s rules [46], which
give a $t$-distribution for the estimated quantity that the analyst can use to
compute confidence intervals or hypothesis tests. We describe Rubin’s rules in
more detail in Supplemental Section B.

##  3 BACKGROUND FOR NAPSU-MQ

In this section we describe the datasets and queries NAPSU-MQ uses, and
briefly describe key concepts from differential privacy, which we will use in
Section 4.

#### Data and Marginal Queries

NAPSU-MQ uses tabular datasets of $d$ discrete variables, where the domains of
the variables, and the number datapoints $n$ are known. We denote the set of
possible datapoints by $\mathcal{X}$, and the set of possible datasets by
$\mathcal{X}^{n}$. For a set of variables $I$ and $x\in\mathcal{X}$, $x^{(I)}$
denotes the selection of the variables in $I$ from $x$.

A marginal query of variables $I$ and value $v$ is a function
$a\colon\mathcal{X}\to\\{0,1\\}$ that takes a datapoint $x$ as input and
returns 1 if $x^{(I)}=v$ and 0 otherwise. For a dataset $X\in\mathcal{X}^{n}$,
we define $a(X)=\sum_{i=1}^{n}a(x_{i})$, where $x_{i}$ is the $i$:th datapoint
in $X$. When $I$ has $k$ variables, $a$ is called a $k$-way marginal query.

When evaluating multiple marginal queries $a_{1},\dotsc,a_{n_{q}}$, we
concatenate their values to a vector-valued function
$a\colon\mathcal{X}\to\\{0,1\\}^{n_{q}}$. We call the concatenation of
marginal queries for all possible values of variables $I$ the _full set of
marginals on $I$_ 222 Some existing works [41] use the term marginal query for
the full set of marginal queries. We chose this terminology because we deal
with individual marginal queries in Supplemental Section C. .

As a concrete example, take the 3-dimensional binary data used in Figure 1. A
single 2-way marginal query could, for example, look at the first two
variables of a datapoint, and check that both are 0. The full set of marginal
queries on the first two variables checks which of the 4 possible values the
first two variables of a datapoint have, and returns a 4-component vector with
a single 1 and 3 zeros, indicating the answer. As input to NAPSU-MQ, we could
use the concatenation of the 3 full sets of marginal queries for each pair of
variables333 Our experiments for the toy dataset use the full set of 3-way
marginals that includes all 3 variables. . Including these kinds of marginals
with more than one variable allows NAPSU-MQ to take the dependencies between
variables into account.

#### Differential Privacy

Differential privacy (DP) [14, 13] is a definition aiming to quantify the
privacy loss resulting from releasing the results of some algorithm. DP
algorithms are also called _mechanisms_.

A mechanism $\mathcal{M}$ is $(\epsilon,\delta)$-differentially private if for
all neighbouring datasets $X,X^{\prime}$ and all measurable output sets $S$

$P(\mathcal{M}(X)\in S)\leq e^{\epsilon}P(\mathcal{M}(X^{\prime})\in
S)+\delta.$ (1)

The neighbourhood relation in the definition is domain specific. We use the
_substitute_ neighbourhood relation for tabular datasets, where datasets are
neighbouring if they differ in at most one datapoint.

Together, $\epsilon$ and $\delta$ bound the tradeoff between false positive
and false negative rates for any hypothesis test [29]. Their choice is a
matter of policy [12]. $\delta\approx\frac{1}{n}$ permits mechanisms that
clearly violate privacy [15], so one should choose $\delta\ll\frac{1}{n}$.

The mechanism we use to release marginal query values under DP is the
_Gaussian mechanism_ [13, 3]. The Gaussian mechanism with noise variance
$\sigma_{DP}^{2}$ adds Gaussian noise to the value of a function
$f\colon\mathcal{X}^{n}\to\mathbb{R}^{k}$ for input data $X$:
$\mathcal{M}(X)=f(X)+\mathcal{N}(0,\sigma_{DP}^{2}I)$.

The privacy bounds of the Gaussian mechanism depend on the _sensitivity_ of
the function $f$, which is an upper bound on the change in the value of $f$
for neighbouring datasets. Larger sensitivities require a larger noise
variance. The $L_{2}$-sensitivity of a function $f$ is
$\Delta_{2}f=\sup_{X\sim X^{\prime}}||f(X)-f(X^{\prime})||_{2}$. $X\sim
X^{\prime}$ denotes that $X$ and $X^{\prime}$ are neighbouring.

The sensitivity of a concatenation of full sets of marginal queries has a
simple form: [] Let $a$ be the concatenation of $n_{s}$ full sets of marginal
queries. Then $\Delta_{2}a\leq\sqrt{2n_{s}}$.

###### Proof.

We defer the proof to Supplemental Section A. ∎

[[3]] The Gaussian mechanism for a function $f$ with $L_{2}$-sensitivity
$\Delta_{2}$ and noise variance $\sigma_{DP}^{2}$ is $(\epsilon,\delta)$-DP
with

$\delta\geq\Phi\left(\frac{\Delta_{2}}{2\sigma_{DP}}-\frac{\epsilon\sigma_{DP}}{\Delta_{2}}\right)-e^{\epsilon}\Phi\left(\frac{-\Delta_{2}}{2\sigma_{DP}}-\frac{\epsilon\sigma_{DP}}{\Delta_{2}}\right)$
(2)

where $\Phi$ is the cumulative distribution function of the standard Gaussian
distribution. If $\epsilon$, $\delta$ and $\Delta_{2}$ are given, which is
typical, $\sigma_{DP}^{2}$ can be solved from Theorem 3 using standard
numerical methods.

An important property of DP is post-processing immunity: post-processing the
result of a DP-algorithm does not weaken the privacy bounds. [[15]] Let
$\mathcal{M}$ be an $(\epsilon,\delta)$-DP mechanism, and let $f$ be any
algorithm. Then the composition $f\circ\mathcal{M}$ is $(\epsilon,\delta)$-DP.

Because of post-processing immunity, we can release marginal query values with
the Gaussian mechanism to obtain privacy bounds, and make arbitrary use of the
noisy query values without weakening the privacy bounds. This allows releasing
an arbitrary number of synthetic datasets without compromising on privacy.

##  4 NOISE-AWARE SYNTHETIC DATA GENERATION

In order to implement the NA step, the data holder needs to generate synthetic
data from the posterior of a noise-aware Bayesian model. [5] develop noise-
aware Bayesian inference under DP for simple exponential family models, with
noise added to sufficient statistics. However, their algorithm requires both
computing unnormalised densities for the model, and sampling from the model’s
conjugate prior. In our setting, neither of these is trivial.

We implement the NA step by generalising their algorithm to use arbitrary
marginal queries as the sufficient statistics, using the maximum entropy
distribution of the marginal queries as our exponential family model. We
develop a computationally feasible method to compute the unnormalised density
of this model, and sidestep the conjugate prior sampling by using standard
posterior sampling methods, which also allows us to use a non-conjugate prior.

We start by considering an arbitrary set of marginal queries $a$. We would
like to find an exponential family distribution that, in expectation, gives
the same answers to $a$ as the real data $X$. We do not want to assume
anything else about the distribution besides these expected query values, so
we use the principle of maximum entropy [28] to choose the distribution.

The distribution with maximal entropy that satisfies the constraint
$E_{X^{*}\sim P}(a(X^{*}))=a(X)$ is

$P(x)=\exp(\theta^{T}a(x)-\theta_{0}(\theta))$ (3)

for some parameters $\theta\in\mathbb{R}^{k}$ [54], where $k$ is the number of
queries. $\theta_{0}(\theta)$ is the normalising constant of the distribution,
so it is given by

$\theta_{0}(\theta)=\ln\left(\sum_{x\in\mathcal{X}}\exp(\theta^{T}a(x))\right).$
(4)

We denote this distribution by $\mathrm{MED}_{\theta}$, and use
$\mathrm{MED}_{\theta}^{n}$ to denote the distribution of $n$ i.i.d. samples
from $\mathrm{MED}_{\theta}$.

$\mathrm{MED}_{\theta}$ is clearly an exponential family distribution, with
sufficient statistic $a(x)$ and natural parameters $\theta$.
$\mathrm{MED}_{\theta}$ is also a Markov network [31], given in log-linear
form.

The Bayesian model we consider is derived from the generative process of the
noisy query values, which are observed. Assuming that the data generating
process is $\mathrm{MED}_{\theta}$, and knowing that the Gaussian mechanism
adds noise with variance $\sigma_{DP}^{2}$, we get the probabilistic model

$\displaystyle\theta$ $\displaystyle\sim\mathrm{Prior},\quad$ $\displaystyle
X$ $\displaystyle\sim\mathrm{MED}_{\theta}^{n},\quad$ (5) $\displaystyle s$
$\displaystyle=a(X),\quad$ $\displaystyle\tilde{s}$
$\displaystyle\sim\mathcal{N}(s,\sigma_{DP}^{2}I).$ (6)

In principle, we could now sample from the posterior $p(\theta\mid\tilde{s})$,
with $s$ marginalised out. In practice, the marginalisation is not feasible,
as $s$ is a discrete variable with a very large domain.

However, $s$ is a sum of the query values for individual datapoints, so
asymptotically $s$ has a normal distribution by the central limit theorem. We
can substitute the normal approximation for $s$ into the model, which allows
us to easily marginalise $s$ out, resulting in

$\displaystyle\theta$
$\displaystyle\sim\mathrm{Prior},\quad\tilde{s}\sim\mathcal{N}(n\mu(\theta),n\Sigma(\theta)+\sigma_{DP}^{2}I),$
(7)

where $\mu(\theta)$ and $\Sigma(\theta)$ denote the mean and covariance of
$a(x)$ for a single sample $x\sim\mathrm{MED}_{\theta}$.

To compute $\mu(\theta)$ and $\Sigma(\theta)$, we use both the exponential
family and Markov network structure of $\mathrm{MED}_{\theta}$. Due to the
exponential family structure,

$\displaystyle\mu(\theta)=\nabla\theta_{0}(\theta),\quad\quad\Sigma(\theta)=H_{\theta_{0}}(\theta),$
(8)

where $H_{\theta_{0}}$ is the Hessian of $\theta_{0}$. Computing $\theta_{0}$
naively requires summing over the exponentially large domain $\mathcal{X}$,
which is not tractable for complex domains. The Markov network structure gives
a solution: $\theta_{0}$ can be computed with the variable elimination
algorithm [31]. We can then autodifferentiate variable elimination to compute
$\mu(\theta)$ and $\Sigma(\theta)$. Alternatively, $\mu(\theta)$ can be
computed by belief propagation [31], and $\Sigma(\theta)$ can be
autodifferentiated from it.

For the prior, we choose another Gaussian distribution with mean 0 and
standard deviation 10, which is a simple and weak prior, but other priors
could be used.

To sample the posterior, we use existing posterior inference methods, namely
the Laplace approximation [18], which approximates the posterior with a
Gaussian distribution centered at the posterior mode, and the NUTS algorithm
[24], which is a _Markov chain Monte Carlo_ (MCMC) algorithm that samples the
posterior directly using the gradients of the posterior log-density.

The time complexities of computing $\mu(\theta)$ and $\Sigma(\theta)$ for
inference, as well as sampling $\mathrm{MED}_{\theta}$ after inference, depend
on the sparsity444In a sparse graph, the fraction of pairs of nodes with an
edge between them is small. of the Markov network graph that the selected set
of queries induces. Specifically, the time complexities are exponential in the
_tree width_ of the graph [31], which can be much lower than the
dimensionality for sparse graphs, making inference and sampling tractable for
sparse queries.

If we include all possible marginal queries from the selected variable sets,
the parametrisation of $\mathrm{MED}_{\theta}$ is not identifiable, as there
are linear dependencies among the queries [31]. Nonidentifiablity causes NUTS
sampling to be very slow, so we prune the queries to remove linear
dependencies while preserving the information in the queries using the
_canonical parametrisation_ for $\mathrm{MED}_{\theta}$ [31]. We give a
detailed description of the process in Supplemental Section C.

###  4.1 NAPSU-MQ Properties

We summarise NAPSU-MQ in Algorithm 1. The privacy bounds for NAPSU-MQ follow
from the material of Section 3: NAPSU-MQ (Algorithm 1) is
$(\epsilon,\delta)$-DP with regards to the real data $X$.

###### Proof.

The returned values of Algorithm 1 only depend on the real data $X$ through
$\tilde{s}$. Releasing $\tilde{s}$ is $(\epsilon,\delta)$-DP due to the
selection of $\sigma_{DP}^{2}$ with Theorem 3. Computing the returned values
from $\tilde{s}$ is post-processing, so by Theorem 3, NAPSU-MQ is
$(\epsilon,\delta)$-DP. ∎

In Supplemental Section B, we list the conditions under which Rubin’s rules
are unbiased [46]. As is typical with statistical methods, these assumptions
are asymptotic in nature. Our experiments in Section 5 show that NAPSU-MQ is
robust to these asymptotics and works with large enough samples.

The most important of the assumptions behind Rubin’s rules555 Assumptions B.1
and B.1 in Supplemental SectionB.  for synthetic data generation requires that
the synthetic data generation does not bias the downstream analysis. This
means that the marginal queries input to NAPSU-MQ must contain the relevant
information for the downstream analysis. For our experiments, we include a
fixed set of queries that gives enough information for the downstream task,
and select other queries automatically with an existing query selection
algorithm [39]. We leave further work on query selection for noise-aware
inference to future work.

Input: Real data $X$, marginal queries $a$, number of synthetic datasets $m$,
size of synthetic datasets $n_{Syn}$, privacy bounds $\epsilon,\delta$.

Output: Posterior distribution $p(\theta|\tilde{s})$, synthetic datasets
$X^{Syn}_{1},\dotsc,X^{Syn}_{m}$.

$a^{*}\leftarrow$ Canonical queries for $a$ (Section C);

$s\leftarrow a^{*}(X)$;

$\Delta_{2}\leftarrow$ Sensitivity of $s$ (Theorem 3);

$\sigma_{DP}^{2}\leftarrow$ Required noise variance for $(\epsilon,\delta)$-DP
with sensitivity $\Delta_{2}$ (Theorem 3);

Sample $\tilde{s}\sim\mathcal{N}(s,\sigma_{DP}^{2})$;

Run Bayesian inference algorithm to find $p(\theta|\tilde{s})$ (Section 4);

Sample $\theta_{i}\sim p(\theta|\tilde{s})$ and
$X^{Syn}_{i}\sim\mathrm{MED}_{\theta_{i}}^{n_{Syn}}$ for $1\leq i\leq m$;

return _$p(\theta|\tilde{s})$ , $X^{Syn}_{1},\dotsc,X^{Syn}_{m}$_

Algorithm 1 NAPSU-MQ

##  5 EXPERIMENTS

In this section, we give detailed descriptions on our two main experiments: a
simple toy data experiment, and our experiment with the UCI Adult dataset,
which demonstrate that NAPSU-MQ is able to compute accurate confidence
intervals. In Supplemental Section G, we describe an additional experiment
with the UCI US Census (1990) dataset, which confirms the results of the other
experiments. Our code is available under an open source license666 A library
implementation of NAPSU-MQ is available at https://github.com/DPBayes/twinify,
while code to replicate our experiments is at
https://github.com/DPBayes/NAPSU-MQ-experiments. .

(a)

(b)

Figure 3:  (a) Toy data confidence intervals widths. NA+MI produces slightly
wider intervals than PGM or PEP for $\epsilon>0.1$, which is necessary to
account for DP noise. PrivLCM produces much wider intervals. (b) Ablation
study on the toy data. “-NA” refers to removing noise-awareness, and “-MI”
refers to removing multiple imputation. Unless both are included, NAPSU-MQ is
overconfident like PGM except for $\epsilon\geq 1$ where noise-awareness is
not necessary. $\delta=2.5\cdot 10^{-7}$ in both (a) and (b).

###  5.1 Toy Data

To demonstrate the necessity of noise-awareness in synthetic data generation,
we measure the coverage of confidence intervals computed from DP synthetic
data on a generated toy dataset where the data generation process is known. We
test the existing algorithms PGM [41], PEP [35], RAP [2], PrivLCM [44],
PrivBayes [59] and our pipeline NA+MI, where data generation is implemented
with NAPSU-MQ. The authors of PrivLCM also propose using multiple imputation
[44], so we use Rubin’s rules [46] with the output of PrivLCM. We also ran
PGM, PEP, RAP and PrivBayes with Rubin’s rules, which did not produce useful
results, as these algorithms do not meet the assumptions of Rubin’s rules.

The original data consists of $n=2000$ datapoints of 3 binary variables. The
first two are sampled by independent coin flips. The third is sampled from
logistic regression on the other two variables with coefficients (1, 0).

For all algorithms except PrivLCM and PrivBayes, we use the full set of 3-way
marginal queries released with the Gaussian mechanism. PrivLCM doesn’t
implement these, and instead uses all full sets of 2-way marginals, and a
different mechanism, which is $(\epsilon,0)$-DP [44] instead of
$(\epsilon,\delta)$-DP like the other algorithms. PrivBayes requires
specifying a Bayesian network [59], which we set to match the data generating
process, and takes a single full set of 1-way marginals and a single full set
of 2-way marginals in addition to the full set of 3-way marginals the other
algorithms take. We use the Laplace approximation for NAPSU-MQ inference, as
it is much faster than NUTS and works well for this simple setting.

DP algorithms are typically evaluated under changing privacy bounds by fixing
$\delta\leq\frac{1}{n}$, and varying $\epsilon$, which is the setting used by
the authors of PGM [41], PEP [35] and RAP [2]. We follow this setting, fixing
$\delta=n^{-2}=2.5\cdot 10^{-7}$.

We generate $m=100$ synthetic datasets of size $n_{Syn}=n$ for all algorithms
except RAP, where the synthetic dataset size is a function of two
hyperparameters. We describe the hyperparameters in detail in Supplemental
Section E.

The downstream task is inferring the logistic regression coefficients from
synthetic data. We repeated all steps 100 times to measure the probability of
sampling a dataset giving a confidence interval that includes the true
parameter values.

Figure 1 shows the coverages, and Figure 3(a) shows the widths for the
resulting confidence intervals. All of the algorithms apart from ours and
PrivLCM are overconfident, even with very loose privacy bounds. Examining the
confidence intervals shows the reason: PGM is unbiased, but it produces too
narrow confidence intervals, while NAPSU-MQ produces wider confidence
intervals. On the other hand, for $\epsilon>0.25$, PrivLCM produces much wider
and too conservative confidence intervals.

#### Ablation Study

We also conducted an ablation study on the toy data to show that both multiple
imputation and noise-awareness are necessary for accurate confidence
intervals. The results are presented in Figure 3(b). Without both multiple
imputation and noise-awareness, NA+MI is overconfident like PGM, except for
$\epsilon\geq 1$, where noise-awareness is not required. We show the
confidence intervals produced by each method for $\epsilon=0.5$ in Figure S2
in the Supplement.

###  5.2 Adult Dataset

Our main experiment evaluates the performance of NAPSU-MQ on the UCI Adult
dataset [30]. We include 10 of the original 15 columns to remove redundant
columns and keep runtimes manageable, and discretise the continuous columns.
After dropping rows with missing values, there are $n=46\,043$ rows. The
discretised domain has $1\,792\,000$ distinct values. We give a detailed
description of the dataset, query selection and the downstream task in
Supplemental Section F.

Figure 4:  Top row: the fraction of downstream coefficients where the
synthetic confidence interval contains the real data coefficient, averaged
over 20 repeated runs on the Adult dataset using regularisation. NAPSU-MQ is
the only algorithm that is consistently around the diagonal, showing good
calibration. The error bands are bootstrap 95% confidence intervals of the
average over the 20 repeats. Bottom row: confidence intervals widths divided
by real data confidence interval widths. Each bar is a median over the
different coefficients and repeats, and the black lines are 95% bootstrapped
confidence intervals. The dashed line is at $y=1$, showing where synthetic
confidence intervals have the same width as original confidence intervals.
$\delta\approx 4.7\cdot 10^{-10}$ in all panels.

As our downstream task, we use logistic regression with income as the
dependent variable and a subset of the columns as the independent variables,
which allows us to include all the relevant marginals for synthetic data
generation. The synthetic dataset was still generated with all 10 columns.

We compare NAPSU-MQ against PGM [41], RAP [2] and PEP [35]. We used the
published implementations of their authors for all of them, with small
modifications to ensure compatibility with new library versions and our
experiments. The published implementation of PrivLCM only supports binary
data, and does not scale to datasets of this size, so it was not included in
this experiment. PrivBayes was also excluded, as it doesn’t support the set of
queries we use in this experiment. We also include a naive noise-aware
baseline that runs $m$ completely independent repeats of PGM, splitting the
privacy budget appropriately, and uses Rubin’s rules with the $m$ generated
synthetic datasets.

NAPSU-MQ and PGM-repeat sometimes generate synthetic datasets with no people
of some race with high income. Logistic regression will produce an extremely
wide confidence intervals for the corresponding coefficients. Rubin’s rules
average over estimates, so even a single bad estimate makes the combined
confidence interval extremely wide. This can be fixed in two ways: a simple
solution is removing estimates with extremely large variances before applying
Rubin’s rules. A more principled way is to add a very small regularisation
term to the logistic regression, which fixes the extremely wide confidence
intervals, but will require bootstrapping to get variance estimates, which
increases the computational cost of the downstream analysis. We used an
$l_{2}$-regularisation term of $10^{-5}$, and used 50 bootstrap samples.
Because of post-processing immunity, neither of these fixes affects the
privacy bounds.

As the input queries, we pick 2-way marginals that are relevant for the
downstream task, and select the rest of the queries with the MST algorithm
[39]. This selection was kept constant throughout the experiment. For the
privacy budget, we use $\delta=n^{-2}\approx 4.7\cdot 10^{-10}$ for all runs,
and vary $\epsilon$.

[47] discusses the choice of $n_{Syn}$ and $n$ for non-DP synthetic data
generation in detail. Based on his results, choosing $n_{Syn}=n$ is very safe,
and we use it for all algorithms except RAP, as in the toy data experiment
(Section 5.1). For NAPSU-MQ and PGM-repeat, we choose the number of generated
synthetic datasets with a preliminary experiment, presented in Figures S4 and
S3 in the Supplement. For NAPSU-MQ, the theory of [47], suggests that a larger
$m$ is better, but has diminishing returns. Our results in Figure S4 validate
this, as all values of $m$ produce similar results. We describe the other
hyperparameters in detail in Supplemental Section E.

The Laplace approximation for NAPSU-MQ does not work well for this setting
because many of the queries have small values, so we use NUTS [24] for
posterior inference. To speed up NUTS, we normalise the posterior before
running the inference using the mean and covariance of the Laplace
approximation

Results from 20 repeats of the experiment are shown in Figure 4. PGM, RAP and
PEP produce overconfident confidence intervals that do not meet the given
confidence levels. With the repeats, PGM becomes overly conservative, and
produces confidence intervals that are too wide. NAPSU-MQ is the only
algorithm that produces properly calibrated intervals, although repeated PGM
is able to produce narrower intervals than NAPSU-MQ with $\epsilon=0.1$. With
the more realistic $\epsilon=1$, the confidence intervals from NAPSU-MQ are
not much wider than non-DP intervals, while PGM-repeat produces much wider
intervals. Figure S8 shows that NAPSU-MQ reproduces 1- and 2-way marginals
nearly as accurately as PGM.

The results in Figure 4 were obtained using the small regularisation term.
Figure S5 shows the results with the trick of dropping large variances, which
are very close to Figure 4.

Noise-awareness, especially with the increased accuracy from NUTS, comes with
a steep computational cost, as PGM ran in 15s, while the Laplace approximation
took several minutes, and NUTS took up to ten hours. All of the algorithms
were run on 4 CPU cores of a cluster. The complete set of runtimes for all
algorithms and values of $\epsilon$ are shown in Table S1 of the Supplement.

##  6 DISCUSSION

While our general pipeline NA+MI is applicable to all kinds of datasets in
principle, the data generation algorithm NAPSU-MQ is currently only applicable
to discrete tabular data due to the reliance on perturbing query values, and
only supports sparse marginal queries perturbed with the Gaussian mechanism as
input due to the techniques we use to make the algorithm practical.

We aim to generalise NAPSU-MQ to more general query classes, such as linear
queries, in the future. Getting rid of the dependency on queries completely is
likely to be much more challenging, as it will require developing noise-aware
Bayesian inference without perturbing sufficient statistics. This may be
possible by adding noise-awareness to other types of DP Bayesian inference
methods, like DP variational inference [26] or DP MCMC [23, 57].

Only handling discrete data is not a major limitation, as the combination of
discretisation [60] and synthetic data generation with marginal-based
algorithms like PGM [41] have been shown to perform very well on tabular
synthetic data generation tasks [52].

The Gaussian mechanism adds noise uniformly to all queries, making small
queries relatively more noisy. This may reduce the accuracy of query-based
algorithms like NAPSU-MQ and the others we examined for groups with rare
combinations of data values, such as minorities.

Although we left query selection outside the scope of this paper, selecting
the right queries to support downstream analysis is important, as NA+MI cannot
guarantee confidence interval coverage if the selected queries do not contain
enough information for the downstream task. We plan to study whether existing
methods giving confidence bounds on query accuracy [40, 44] can be adapted to
give confidence intervals for arbitrary downstream analyses.

The runtime is a significant limitation in the current implementation of
NAPSU-MQ when using NUTS. As NAPSU-MQ is compatible with any non-DP posterior
sampling method, recent [25] and future advances in MCMC and other sampling
techniques are likely able to cut down on the runtime.

#### Conclusion

The analysis of DP synthetic data has not received much attention in existing
research. Our work patches a major hole in the current generation and analysis
methods by developing the NA+MI pipeline that allows computing accurate
confidence intervals and $p$-values from DP synthetic data. We develop the
NAPSU-MQ algorithm in order to implement NA+MI on nontrivial discrete
datasets. NA+MI only depends on noise-aware posterior inference, not NAPSU-MQ
specifically, and can thus be extended to other settings in the future. With
the noise-aware inference algorithm, NA+MI allows conducting valid statistical
analyses that include uncertainty estimates with DP synthetic data,
potentially unlocking existing privacy-sensitive datasets for widespread
analysis.

### Acknowledgments

This work was supported by the Academy of Finland (Flagship programme: Finnish
Center for Artificial Intelligence, FCAI; and grants 325572, 325573), the
Strategic Research Council at the Academy of Finland (Grant 336032), the UKRI
Turing AI World-Leading Researcher Fellowship, EP/W002973/1, as well as the
European Union (Project 101070617). Views and opinions expressed are however
those of the author(s) only and do not necessarily reflect those of the
European Union or the European Commission. Neither the European Union nor the
granting authority can be held responsible for them. The authors wish to thank
the Finnish Computing Competence Infrastructure (FCCI) for supporting this
project with computational and data storage resources.

## References

  * [1] Pieter Abbeel, Daphne Koller and Andrew Y. Ng  “Learning Factor Graphs in Polynomial Time and Sample Complexity”  In _Journal of Machine Learning Research_ 7, 2006, pp. 1743–1788
  * [2] Sergul Aydore, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth and Ankit A Siva  “Differentially Private Query Release Through Adaptive Projection”  In _Proceedings of the 38th International Conference on Machine Learning_ 139, Proceedings of Machine Learning Research  PMLR, 2021, pp. 457–467
  * [3] Borja Balle and Yu-Xiang Wang  “Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising”  In _Proceedings of the 35th International Conference on Machine Learning_ 80, Proceedings of Machine Learning Research  PMLR, 2018, pp. 394–403
  * [4] Garrett Bernstein, Ryan McKenna, Tao Sun, Daniel Sheldon, Michael Hay and Gerome Miklau  “Differentially Private Learning of Undirected Graphical Models Using Collective Graphical Models”  In _Proceedings of the 34th International Conference on Machine Learning_ 70, Proceedings of Machine Learning Research  PMLR, 2017, pp. 478–487
  * [5] Garrett Bernstein and Daniel Sheldon  “Differentially Private Bayesian Inference for Exponential Families”  In _Advances in Neural Information Processing Systems_ 31, 2018, pp. 2924–2934
  * [6] Garrett Bernstein and Daniel Sheldon  “Differentially Private Bayesian Linear Regression”  In _Advances in Neural Information Processing Systems_ 32, 2019, pp. 523–533
  * [7] Kuntai Cai, Xiaoyu Lei, Jianxin Wei and Xiaokui Xiao  “Data Synthesis via Differentially Private Markov Random Fields”  In _Proceedings of the VLDB Endowment_ 14.11 VLDB Endowment, 2021, pp. 2190–2202
  * [8] Anne-Sophie Charest  “How Can We Analyze Differentially-Private Synthetic Datasets?”  In _Journal of Privacy and Confidentiality_ 2.2, 2010  DOI: 10.29012/jpc.v2i2.589
  * [9] Dingfan Chen, Tribhuvanesh Orekondy and Mario Fritz  “GS-WGAN: A Gradient-Sanitized Approach for Learning Differentially Private Generators”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 12673–12684
  * [10] Rui Chen, Qian Xiao, Yu Zhang and Jianliang Xu  “Differentially Private High-Dimensional Data Publication via Sampling-Based Inference”  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ ACM, 2015, pp. 129–138  DOI: 10.1145/2783258.2783379
  * [11] Christian Covington, Xi He, James Honaker and Gautam Kamath  “Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacy”  arXiv, 2021  arXiv:2110.14465
  * [12] Cynthia Dwork  “Differential Privacy: A Survey of Results”  In _International Conference on Theory and Applications of Models of Computation_ Springer, 2008, pp. 1–19
  * [13] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov and Moni Naor  “Our Data, Ourselves: Privacy Via Distributed Noise Generation”  In _Advances in Cryptology - EUROCRYPT_ 4004, Lecture Notes in Computer Science  Springer, 2006, pp. 486–503  DOI: 10.1007/11761679_29
  * [14] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam D. Smith  “Calibrating Noise to Sensitivity in Private Data Analysis”  In _Third Theory of Cryptography Conference_ 3876, Lecture Notes in Computer Science  Springer, 2006, pp. 265–284  DOI: 10.1007/11681878_14
  * [15] Cynthia Dwork and Aaron Roth  “The Algorithmic Foundations of Differential Privacy”  In _Foundations and Trends in Theoretical Computer Science_ 9.3-4, 2014, pp. 211–407  DOI: 10.1561/0400000042
  * [16] Georgina Evans and Gary King  “Statistically Valid Inferences from Differentially Private Data Releases, with Application to the Facebook URLs Dataset”  In _Political Analysis_ , 2022, pp. 1–21  DOI: 10.1017/pan.2022.1
  * [17] Cecilia Ferrando, Shufan Wang and Daniel Sheldon  “Parametric Bootstrap for Differentially Private Confidence Intervals”  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ 151, Proceedings of Machine Learning Research  PMLR, 2022, pp. 1598–1618
  * [18] Andrew Gelman, John B Carlin, Hal S Stern, David B Dunson, Aki Vehtari and Donald B Rubin  “Bayesian Data Analysis”  In _Bayesian data analysis_ , Chapman & Hall/CRC Texts in Statistical Science Series  Boca Raton: CRC Press, 2014
  * [19] Sahra Ghalebikesabi, Harrison Wilde, Jack Jewson, Arnaud Doucet, Sebastian J. Vollmer and Chris Holmes  “Bias Mitigated Learning from Differentially Private Synthetic Data: A Cautionary Tale”  arXiv, 2021  arXiv:2108.10934
  * [20] Ruobin Gong  “Exact Inference with Approximate Computation for Differentially Private Data via Perturbations”  In _Journal of Privacy and Confidentiality_ 12.2, 2022  DOI: 10.29012/jpc.797
  * [21] Frederik Harder, Kamil Adamczewski and Mijung Park  “DP-MERF: Differentially Private Mean Embeddings with RandomFeatures for Practical Privacy-preserving Data Generation”  In _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ 130, Proceedings of Machine Learning Research  PMLR, 2021, pp. 1819–1827
  * [22] Moritz Hardt, Katrina Ligett and Frank McSherry  “A Simple and Practical Algorithm for Differentially Private Data Release”  In _Advances in Neural Information Processing Systems_ 25, 2012, pp. 2348–2356
  * [23] Mikko A. Heikkilä, Joonas Jälkö, Onur Dikmen and Antti Honkela  “Differentially Private Markov Chain Monte Carlo”  In _Advances in Neural Information Processing Systems_ 32, 2019, pp. 4115–4125
  * [24] Matthew D Hoffman and Andrew Gelman  “The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo.”  In _Journal of Machine Learning Research_ 15.1, 2014, pp. 1593–1623
  * [25] Matthew D. Hoffman, Alexey Radul and Pavel Sountsov  “An Adaptive-MCMC Scheme for Setting Trajectory Lengths in Hamiltonian Monte Carlo”  In _The 24th International Conference on Artificial Intelligence and Statistics_ 130, Proceedings of Machine Learning Research  PMLR, 2021, pp. 3907–3915
  * [26] Joonas Jälkö, Antti Honkela and Onur Dikmen  “Differentially Private Variational Inference for Non-conjugate Models”  In _Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence_ AUAI Press, 2017
  * [27] Joonas Jälkö, Eemil Lagerspetz, Jari Haukka, Sasu Tarkoma, Antti Honkela and Samuel Kaski  “Privacy-Preserving Data Sharing via Probabilistic Modeling”  In _Patterns_ 2.7, 2021, pp. 100271  DOI: 10.1016/j.patter.2021.100271
  * [28] E.. Jaynes  “Information Theory and Statistical Mechanics”  In _Physical Review_ 106.4, 1957, pp. 620–630  DOI: 10.1103/PhysRev.106.620
  * [29] Peter Kairouz, Sewoong Oh and Pramod Viswanath  “The Composition Theorem for Differential Privacy”  In _Proceedings of the 32nd International Conference on Machine Learning_ 37, Proceedings of Machine Learning Research  PMLR, 2015, pp. 1376–1385
  * [30] Ronny Kohavi and Barry Becker  “Adult”, UCI Machine Learning Repository, 1996
  * [31] Daphne Koller and Nir Friedman  “Probabilistic Graphical Models: Principles and Techniques”  MIT press, 2009
  * [32] Tejas Kulkarni, Joonas Jälkö, Antti Koskela, Samuel Kaski and Antti Honkela  “Differentially Private Bayesian Inference for Generalized Linear Models”  In _Proceedings of the 38th International Conference on Machine Learning_ 139, Proceedings of Machine Learning Research  PMLR, 2021, pp. 5838–5849
  * [33] Seng Pei Liew, Tsubasa Takahashi and Michihiko Ueno  “PEARL: Data Synthesis via Private Embeddings and Adversarial Reconstruction Learning”  In _International Conference on Learning Representations_ , 2022
  * [34] Fang Liu  “Model-Based Differentially Private Data Synthesis and Statistical Inference in Multiple Synthetic Datasets”  In _Trans. Data Priv._ 15.3, 2022, pp. 141–175
  * [35] Terrance Liu, Giuseppe Vietri and Steven Z. Wu  “Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 690–702
  * [36] Yunhui Long, Boxin Wang, Zhuolin Yang, Bhavya Kailkhura, Aston Zhang, Carl Gunter and Bo Li  “G-PATE: Scalable Differentially Private Data Generator via Private Aggregation of Teacher Discriminators”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 2965–2977
  * [37] Andrea Marshall, Douglas G Altman, Roger L Holder and Patrick Royston  “Combining Estimates of Interest in Prognostic Modelling Studies after Multiple Imputation: Current Practice and Guidelines”  In _BMC Medical Research Methodology_ 9.1, 2009, pp. 57  DOI: 10.1186/1471-2288-9-57
  * [38] Ryan McKenna, Gerome Miklau, Michael Hay and Ashwin Machanavajjhala  “Optimizing Error of High-Dimensional Statistical Queries under Differential Privacy”  In _Proceedings of the VLDB Endowment_ 11.10, 2018
  * [39] Ryan McKenna, Gerome Miklau and Daniel Sheldon  “Winning the NIST Contest: A Scalable and General Approach to Differentially Private Synthetic Data”  In _Journal of Privacy and Confidentiality_ 11.3, 2021  DOI: 10.29012/jpc.778
  * [40] Ryan McKenna, Brett Mullins, Daniel Sheldon and Gerome Miklau  “AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data”  In _Proceedings of the VLDB Endowment_ 15.11, 2022, pp. 2599–2612  DOI: 10.14778/3551793.3551817
  * [41] Ryan McKenna, Daniel Sheldon and Gerome Miklau  “Graphical-Model Based Estimation and Inference for Differential Privacy”  In _Proceedings of the 36th International Conference on Machine Learning_ 97, Proceedings of Machine Learning Research  PMLR, 2019, pp. 4435–4444
  * [42] Chris Meek, Bo Thiesson and David Heckerman  “US Census Data (1990)”, UCI Machine Learning Repository, 2001
  * [43] Marcel Neunhoeffer, Steven Wu and Cynthia Dwork  “Private Post-GAN Boosting”  In _International Conference on Learning Representations_ , 2021
  * [44] Michelle Nixon, Andres Barrientos, Jerome Reiter and Aleksandra Slavkovic  “A Latent Class Modeling Approach for Generating Synthetic Data and Making Posterior Inferences from Differentially Private Counts”  In _Journal of Privacy and Confidentiality_ 12.1, 2022  DOI: 10.29012/jpc.768
  * [45] Gillian M Raab, Beata Nowok and Chris Dibben  “Practical Data Synthesis for Large Samples”  In _Journal of Privacy and Confidentiality_ 7.3, 2018, pp. 67–97  DOI: 10.29012/jpc.v7i3.407
  * [46] Trivellore E Raghunathan, Jerome P Reiter and Donald B Rubin  “Multiple Imputation for Statistical Disclosure Limitation”  In _Journal of Official Statistics_ 19.1 Statistics Sweden (SCB), 2003, pp. 1
  * [47] Jerome P Reiter  “Satisfying Disclosure Restrictions with Synthetic Data Sets”  In _Journal of Official Statistics_ 18.4 Statistics Sweden (SCB), 2002, pp. 531
  * [48] Jerome P Reiter  “Significance Tests for Multi-Component Estimands from Multiply Imputed, Synthetic Microdata”  In _Journal of Statistical Planning and Inference_ 131.2 Elsevier, 2005, pp. 365–377
  * [49] Donald B. Rubin  “Multiple Imputation for Nonresponse in Surveys”  In _Multiple Imputation for Nonresponse in Surveys_ New York: John Wiley \& Sons, 1987
  * [50] Donald B. Rubin  “Discussion: Statistical Disclosure Limitation”  In _Journal of Official Statistics_ 9.2, 1993, pp. 461–468
  * [51] Yajuan Si and Jerome P Reiter  “A Comparison of Posterior Simulation and Inference by Combining Rules for Multiple Imputation”  In _Journal of Statistical Theory and Practice_ 5.2 Taylor & Francis, 2011, pp. 335–347
  * [52] Yuchao Tao, Ryan McKenna, Michael Hay, Ashwin Machanavajjhala and Gerome Miklau  “Benchmarking Differentially Private Synthetic Data Generation Algorithms”  arXiv, 2021  arXiv:2112.09238
  * [53] Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke and Zhiwei Steven Wu  “New Oracle-Efficient Algorithms for Private Synthetic Data Release”  In _Proceedings of the 37th International Conference on Machine Learning_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 9765–9774
  * [54] Martin J. Wainwright and Michael I. Jordan  “Graphical Models, Exponential Families, and Variational Inference”  In _Foundations and Trends in Machine Learning_ 1.1-2, 2008, pp. 1–305  DOI: 10.1561/2200000001
  * [55] Harrison Wilde, Jack Jewson, Sebastian J. Vollmer and Chris Holmes  “Foundations of Bayesian Learning from Synthetic Data”  In _The 24th International Conference on Artificial Intelligence and Statistics_ 130, Proceedings of Machine Learning Research  PMLR, 2021, pp. 541–549
  * [56] Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang and Jiayu Zhou  “Differentially Private Generative Adversarial Network”  arXiv, 2018  arXiv:1802.06739
  * [57] Sinan Yildirim and Beyza Ermis  “Exact MCMC with Differentially Private Moves - Revisiting the Penalty Algorithm in a Data Privacy Framework”  In _Statistics and Computing_ 29.5, 2019, pp. 947–963  DOI: 10.1007/s11222-018-9847-x
  * [58] Jinsung Yoon, James Jordon and Mihaela van der Schaar  “PATE-GAN: Generating Synthetic Data with Differential Privacy Guarantees”  In _International Conference on Learning Representations_ , 2019
  * [59] Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava and Xiaokui Xiao  “PrivBayes: Private Data Release via Bayesian Networks”  In _ACM Transactions on Database Systems_ 42.4, 2017, pp. 25:1–25:41  DOI: 10.1145/3134428
  * [60] Jun Zhang, Xiaokui Xiao and Xing Xie  “PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions”  In _Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference_ ACM, 2016, pp. 155–170  DOI: 10.1145/2882903.2882928
  * [61] Shijie Zheng  “The Differential Privacy of Bayesian Inference”, 2015
  * [62] Xiang Zhou and Jerome P. Reiter  “A Note on Bayesian Inference After Multiple Imputation”  In _The American Statistician_ 64.2, 2010, pp. 159–163  DOI: 10.1198/tast.2010.09109

##  Appendix A PROOF OF THEOREM 3

See 3

###### Proof.

Let $a_{1},\dotsc,a_{n_{s}}$ be the full sets of marginal queries that form
$a$. Because all of the queries of $a_{i}$ have the same set of variables, the
vector $a_{i}(x)$ has a single component of value 1, and the other components
are 0 for any $x\in\mathcal{X}$. Then, for any neighbouring
$X,X^{\prime}\in\mathcal{X}^{n}$, $||a_{i}(X)-a_{i}(X^{\prime})||_{2}^{2}\leq
2$. Then

$\displaystyle\Delta_{2}a$ $\displaystyle=\sup_{X\sim
X^{\prime}}||a(X)-a(X^{\prime})||_{2}=\sup_{X\sim
X^{\prime}}\sqrt{\sum_{i=1}^{n_{s}}||a_{i}(X)-a_{i}(X^{\prime})||_{2}^{2}}\leq\sup_{X\sim
X^{\prime}}\sqrt{\sum_{i=1}^{n_{s}}2}=\sqrt{2n_{s}}$ (9)

∎

##  Appendix B MULTIPLE IMPUTATION

In order to compute uncertainty estimates for downstream analyses from the
noise-aware posterior with NA+MI, we use Rubin’s rules for synthetic data [46,
47].

After the synthetic datasets $X^{Syn}_{i}$ for $1\leq i\leq m$ are released by
the data holder, the data analyst runs their downstream analysis on each
$X^{Syn}_{i}$. For each synthetic dataset, the analysis produces a point
estimate $q_{i}$ and a variance estimate $v_{i}$ for $q_{i}$.

The estimates $q_{1},\dotsc,q_{m}$ and $v_{1},\dotsc,v_{m}$ are combined as
follows [46]:

$\displaystyle\bar{q}=\frac{1}{m}\sum_{i=1}^{m}q_{i},\quad\bar{v}=\frac{1}{m}\sum_{i=1}^{m}v_{i},\quad
b=\frac{1}{m-1}\sum_{i=1}^{m}(q_{i}-\bar{q})^{2}.$ (10)

We use $\bar{q}$ as the combined point estimate, and set

$T=\left(1+\frac{1}{m}\right)b-\bar{v},\quad\quad
T^{*}=\begin{cases}T\quad\text{if }T\geq 0\\\
\frac{n_{Syn}}{n}\bar{v}\quad\text{otherwise}.\end{cases}$ (11)

$T$ is an estimate of the combined variance. $T$ can be negative, which is
corrected using $T^{*}$ instead [47].

We compute confidence intervals and hypothesis tests using the
$t$-distribution with mean $\bar{q}$, variance $T^{*}$, and degrees of freedom

$\nu=(m-1)(1-r^{-1})^{2},$ (12)

where $r=(1+\frac{1}{m})\frac{b}{\bar{v}}$ [47].

These combining rules apply when $q$ is a univariate estimate. [48] derives
appropriate combining rules for multivariate estimates, which can be applied
with NA+MI.

Rubin’s rules make many assumptions on the different distributions that are
involved [46, 51], such as the normality of the distribution of $q_{i}$ when
sampling data from the population. These assumptions may not hold for some
types of estimates, such as probabilities [37] or quantile estimates [62].
Further work [51] tries to reduce these assumptions, especially in the context
of missing data. Their results for synthetic data generation can be applied
with our method.

[51] propose to remove some of these assumptions by approximating the integral
that Rubin’s rules are derived from by sampling instead of using the
analytical approximations in (10) and (11). They find that their sampling-
based approximation can be effective, especially with a small number of
datasets, but is computationally more expensive.

###  B.1 Unbiasedness of Rubin’s Rules

Rubin’s rules make several assumptions on the downstream analysis method, and
several normal approximations when deriving the rules. [46] derive conditions
under which Rubin’s rules give an unbiased estimate.

Rubin’s rules aim to estimate a quantity $Q$ of the entire population $P$, of
which $X$ is a sample. Conceptually, the sampling of the synthetic datasets is
done in two stages: first, synthetic populations $P_{i}^{Syn}$ for $1\leq
i\leq m$ are sampled. Second, a synthetic dataset $X_{i}^{Syn}$ is sampled
i.i.d from $P_{i}^{Syn}$. This is equivalent to the sampling process for
$X_{i}^{Syn}$ described in Section 2, and makes stating the assumptions of
Rubin’s rules easier.

While the sampling process of synthetic data has to be i.i.d., this is not
required for the original data. This means that there are two versions of the
downstream analysis: the one for i.i.d. data, and the one for the complex
sampling method of the real data. The latter method is not used at any point,
so it is assumed to exist for the theory, but does not have to be practically
implementable.

We take advantage of this handling of complex sampling of real data by
including the computation of $s$ and adding noise to get $\tilde{s}$ in the
sampling scheme, so we are considering $\tilde{s}$ to be the original data
from the point of view of the theory. The fact that $\tilde{s}$ is a noisy
summary statistic instead of a dataset is not an issue, as the theory only
requires having a theoretical method to estimate $Q$ from $\tilde{s}$. If the
chosen marginal queries contain the relevant information for the downstream
task, so $s$ is a (approximate) sufficient statistic, this theoretical method
will exist.

Let $Q_{i}$ denote the quantity of interest $Q$ computed from the synthetic
population $P_{i}^{Syn}$ instead of $P$. Let $V_{i}$ denote the sampling
variance of $q_{i}$ from the synthetic population $P^{Syn}_{i}$. Note that
$q_{i}$ and it’s variance estimate $v_{i}$ are obtained using the downstream
analysis method for i.i.d. data. Let $\hat{Q}_{D}$ and $\hat{U}_{D}$ be the
point and variance estimates of $Q$ derived from $\tilde{s}$ when sampling the
population $P$, which are obtained using the theoretical inference method for
complex samples.

Now the assumptions of [46] are

For all $1\leq i\leq m$, $q_{i}$ is unbiased for $Q_{i}$ and asymptotically
normal with respect to sampling from the synthetic population $P_{i}^{Syn}$,
with sampling variance $V_{i}$.

For all $1\leq i\leq m$, $v_{i}$ is unbiased for $V_{i}$, and the sampling
variability in $v_{i}$ is negligible. That is $v_{i}\mid P_{i}^{Syn}\approx
V_{i}$. Additionally, the variation in $V_{i}$ across the synthetic
populations is negligible.

Assumptions B.1-B.1 ensure that the downstream analysis method used to
estimate $Q$ is accurate, for both point and variance estimates, when applied
to i.i.d. real data, regardless of the population.

$\hat{Q}_{D}\mid P\sim\mathcal{N}(Q,\hat{U}_{D})$

Assumption B.1 ensures that the analysis for complex sampling is accurate for
point and variance estimates when applied to the real population.

$Q_{i}\mid\tilde{s}\sim\mathcal{N}(\hat{Q}_{D},\hat{U}_{D})$

Assumption B.1 requires that the generation of synthetic datasets does not
bias the downstream analysis.

For query-based methods like NAPSU-MQ, Assumptions B.1 and B.1 may not hold
when the queries do not contain the relevant information for the downstream
task.

With Assumptions B.1-B.1, [46] show that $\bar{q}$ is an unbiased estimate of
$Q$, and $T$ is an asymptotically unbiased variance estimate.

[[46]] Assumptions B.1-B.1 imply that

  1. 1.

$E(\bar{q}\mid P)=Q$,

  2. 2.

$E(T\mid P)=\mathrm{Var}(\bar{q}\mid P)$,

  3. 3.

Asymptotically $\frac{\bar{q}-Q}{\sqrt{T}}\sim\mathcal{N}(0,1)$,

  4. 4.

For moderate $m$, $\frac{\bar{q}-Q}{\sqrt{T}}\sim t_{\nu}(0,1)$ [47].

##  Appendix C FINDING AND IDENTIFIABLE PARAMETRISATION

In this section, we describe the process we use to ensure the parametrisation
of the posterior in NAPSU-MQ is identifiable. We ensure identifiability by
dropping some of the selected queries, chosen using the the canonical
parametrisation of $\mathrm{MED}_{\theta}$ to ensure no information is lost.
First, we give some background on Markov networks, which is necessary to
understand the canonical parametrisation.

#### Markov Networks

A Markov network is a representation of a probability distribution that is
factored according to an undirected graph. Specifically, a Markov network
distribution $P$ is a product of _factors_. A factor is a function from a
subset of the variables to non-negative real numbers. The subset of variables
is called the _scope_ of the factor. The joint distribution is given by

$P(x)=\frac{1}{Z}\prod_{I\subset S}\phi_{I}(x_{I})$ (13)

where $S$ is the set of scopes for the factors. The undirected graph is formed
by representing each variable as a node, and adding edges such that the scope
of each factor is a clique in the graph.

#### Canonical Parametrisation

The canonical parametrisation is given in terms of _canonical factors_ [1].
The canonical factors depend on an arbitrary assignment of variables $x^{*}$.
We simply choose $x^{*}=(0,\dotsc,0)$. In the following, $x_{U}$ denotes the
selection of components in the set $U$ from the vector $x$, and $x_{-U}$
denotes the selection of all components except those in $U$.

A canonical factor $\phi^{*}_{D}$ with scope $D$ is defined as

$\phi^{*}_{D}(x)=\exp\left(\sum_{U\subseteq D}(-1)^{|D-U|}\ln
P(x_{U},x^{*}_{-U})\right)$

The sum is over all subsets of $D$, including $D$ itself and the empty set.
$|D-U|$ is the size of the set difference of $D$ and $U$.

[[1](Theorem 3)] Let $P$ be a Markov network with factor scopes $S$. Let
$S^{*}=\cup_{D\in S}\mathcal{P}(D)-\emptyset$. Then

$P(x)=P(x^{*})\prod_{D^{*}\in S^{*}}\phi^{*}_{D^{*}}(x_{D^{*}})$

There are more canonical factors than original factors, so it might seem that
there are more parameters in the canonical parametrisation than in the
original parametrisation. However, many values in the canonical factors turn
out to be ones. We can select the queries corresponding to non-one canonical
factor values to obtain a set of queries with the same information as the
original queries, but without linear dependencies [31]. We call this set of
queries the _canonical queries_.

Many of the canonical factor scopes are subsets of the original factor scopes,
so using the canonical queries as is would introduce new marginal query sets
and potentially increase the sensitivity of the queries. As all of the new
queries are sums of existing queries, we can replace each new query with the
old queries that sum to the new query, and use the same $\theta$ value for all
of the added queries to preserve identifiability. After the replacements, the
queries are a subset of the original non-canonical queries, so their
sensitivity is at most the original sensitivity. If one of the added queries
was already included, it does not need to be added again, because two
instances of a single query can be collapsed into a single instance with it’s
own parameter value. Because of this, we did not need to fix the $\theta$
values of any queries to the same value in the settings we studied.

##  Appendix D NAPSU-MQ VS. PGM

The PGM algorithm [41] generates synthetic data based on the same marginal
queries $a$ and noise addition as NAPSU-MQ. PGM also models the original data
using the $\mathrm{MED}_{\theta}$ distribution. Unlike NAPSU-MQ, PGM finds the
parameters $\theta$ by minimising the $l_{2}$-distance
$||\tilde{s}-n\mu(\theta)||_{2}$ between the observed noisy query values
$\tilde{s}$ and the expected query values
$n\mu(\theta)=nE_{x\sim\mathrm{MED}_{\theta}}(a(x))$ In the following, we’ll
replace the query values $s$ and $\tilde{s}$ that are summed over datapoints
with $u=\frac{s}{n}$ and $\tilde{u}=\frac{\tilde{s}}{n}$ that represent mean
query values over datapoints. Then the PGM objective is equivalent to
$||\tilde{u}-\mu(\theta)||_{2}$.

We can view the PGM minimisation problem as a maximum likelihood estimation in
the NAPSU-MQ probabilistic model

$\displaystyle X\sim\mathrm{MED}_{\theta}^{n},\quad
s=a(X),\quad\tilde{s}\sim\mathcal{N}(s,\sigma_{DP}^{2}I),$ (14)

where we replace normal approximation that NAPSU-MQ uses with a law of large
numbers approximation. Specifically, first replace $s$ with $u$ in (14):

$\displaystyle X\sim\mathrm{MED}_{\theta}^{n},\quad
u=\frac{a(X)}{n},\quad\tilde{u}\sim\mathcal{N}(u,\sigma_{DP}^{2}I/n^{2}).$
(15)

Because $u$ is a mean of sufficient statistics for individual datapoints, by
the law of large numbers, asymptotically $u\sim\delta_{\mu(\theta)}$. With
this approximation, the probabilistic model is

$\displaystyle
u\sim\delta_{\mu(\theta)},\quad\tilde{u}\sim\mathcal{N}(u,\sigma_{DP}^{2}I/n^{2}).$
(16)

$u$ can be marginalised from the likelihood of this model:

$\displaystyle p(\tilde{u}|\theta)$ $\displaystyle=\int
p(\tilde{u},u|\theta)\mathrm{d}u$ (17) $\displaystyle=\int
p(\tilde{u}|u)p(u|\theta)\mathrm{d}u$ (18)
$\displaystyle=\int\mathcal{N}(\tilde{u}|u,\sigma_{DP}^{2}I/n^{2})\delta_{\mu(\theta)}(u)\mathrm{d}u$
(19) $\displaystyle=\mathcal{N}(\tilde{u}|\mu(\theta),\sigma_{DP}^{2}I/n^{2})$
(20)

The marginalised log-likelihood is then

$\ln
p(\tilde{u}|\theta)=-\frac{n^{2}}{\sigma_{DP}^{2}}||\tilde{u}-\mu(\theta)||_{2}^{2}+\text{constant},$
(21)

so maximising the log-likelihood is equivalent to minimising the PGM
objective.

If we made a normal approximation instead of the law of large numbers
approximation in (15), we would get

$\displaystyle\tilde{u}\sim\mathcal{N}(\mu(\theta),\Sigma(\theta)/n+\sigma_{DP}^{2}I/n^{2}),$
(22)

so maximising the likelihood is still possible. Unlike PGM, this maximum
likelihood objective includes the covariance $\Sigma(\theta)$. We leave any
comparisons between maximising this objective and PGM to future work.

##  Appendix E HYPERPARAMETERS

#### NAPSU-MQ

The hyperparameters of NAPSU-MQ are the choice of prior, choice of inference
algorithm, and the parameters of that algorithm. For the toy data experiment,
we used the Laplace approximation for inference, which approximates the
posterior with a Gaussian centered at the maximum aposteriori estimate (MAP).
We find the MAP for the Laplace approximation with the LBFGS optimisation
algorithm, which we run until the loss improves by less than $10^{-5}$ in an
iteration, up to a maximum of 500 iterations. Sometimes LBFGS failed to
converge, which we detect by checking if the loss increased by over 1000 in
one iteration, and fix by restarting optimisation from a different starting
point. We also restarted if the maximum number of iterations was reached
without convergence. For the vast majority of runs, no restarts were needed,
and at most 3 were needed.

For the Adult experiment, we used NUTS [24]. We ran 4 chains of 800 warmup
samples and 2000 kept samples. We set the maximum tree depth of NUTS to 12. We
normalised the posterior using the mean and covariance from the Laplace
approximation. For the Laplace approximation, we used the same hyperparameters
as with the toy data set, except we set the maximum number of iterations to
6000.

For the prior, we used a Gaussian distribution with mean 0 and standard
deviation 10 for all components, without dependencies between components, for
both experiments.

#### PGM and Repeated PGM

PGM finds the $\mathrm{MED}_{\theta}$ parameters $\theta$ that minimise the
$L_{2}$-error between the expected query values and the noisy query values.
The PGM implementation offers several algorithms for this optimisation
problem, but we found that the default algorithm (mirror descent) and number
of iterations works well for both experiments.

#### RAP

RAP minimises the error on the selected queries of a continuous relaxation of
the discrete synthetic dataset. After the optimal relaxed synthetic dataset is
found, a discrete synthetic dataset is constructed by sampling. This gives two
hyperparameters that control the size of the synthetic data: the size of the
continuous dataset, and the number of samples for each datapoint in the
continuous relaxation. We set the size of the continuous dataset to 1000 for
both experiments, as recommended by the paper [2]. For the Adult data
experiment, we set the number of samples per datapoint to 46, so that the
total size of the synthetic dataset is close to the size of the original
dataset. For the toy data experiment, we set the number of samples per
datapoint to 50. The RAP paper [2] finds that much smaller values are
sufficient, but higher values should only increase accuracy.

In both cases, we weight the synthetic datapoints by $\frac{n}{n_{Syn}}$
before the downstream logistic regression to ensure that the logistic
regression does not over- or underestimate variances because of a different
sample size from the original data.

RAP also has two other hyperparameters that are relevant in our experiments:
the number of iterations and the learning rate for the query error
minimisation. After preliminary runs, we set the learning rate at 0.1 for both
experiments, and set the number of iterations to 5000 for the toy data
experiment, and 10000 for the Adult data experiment.

#### PEP

PEP has two hyperparameters: the number of iterations used to find a
distribution with maximum entropy that has approximately correct query values,
and the allowed bound on the difference of the query values. The PEP
implementation hardcodes the allowed difference to 0. We set the number of
iterations to 1000 after preliminary runs for both experiments.

#### PrivLCM

PrivLCM samples the posterior of a Bayesian latent class model, where the
number of classes in limited to make inference tractable. The model has
hyperparameters for the prior, and the number of latent classes. We leave the
prior hyperparameters to their defaults, and set the number of latent classes
to 10, which the PrivLCM authors used in a 5-dimensional binary data
experiment [44]. The remaining hyperparameter of PrivLCM is the number of
posterior samples that are obtained. To keep the runtime of PrivLCM
manageable, we set the number of samples to 500 after ensuring that the lower
number of samples did not degrade the accuracy of the estimated probabilities
for the joint distribution compared to using the default of 5000 samples.

#### PrivBayes

As we focus on synthetic data generation, we did not use the query selection
features of PrivBayes in the toy data experiment, and instead set the queries
according to the Bayesian network of the data generating process. Denoting the
three components of the data as $X=(X_{1},X_{2},X_{3})$, the queries are the
full set of 1-way marginals on $X_{1}$, the full set of 2-way marginals on
$(X_{1},X_{2})$, and the full set of 3-way marginals on all three variables.

##  Appendix F ADULT EXPERIMENT DETAILS AND EXTRA RESULTS

We include the columns Age, Workclass, Education, Marital Status, Race,
Gender, Capital gain, Capital loss, Hours per week and Income of the Adult
dataset, and discard the rest to remove redundant columns and keep computation
times manageable. We discretise Age and Hours per week to 5 buckets, and
discretise Capital gain and Capital loss to binary values indicating whether
their value is positive. The Income column is binary from the start, and
indicates whether a person has an income $>\$50\,000$.

In the downstream logistic regression, we use income as the dependent
variable, and Age, Race and Gender as independent variables. Age is
transformed back to a continuous value for the logistic regression by picking
the middle value of each discretisation bucket. We did not use all variables
for the downstream task, as a smaller set of variables allows including the
relevant marginals for synthetic data generation. The regularisation for the
logistic regression is $l_{2}$ with a very small multiplier of $10^{-5}$. When
the regularisation is used, variances are estimated with bootstrapping using
50 bootstrap samples.

All of the Adult experiment figures, except Figures S5 and S6 use the small
regularisation term. Figure S5 shows the results with the trick of removing
large variance estimates $(\geq 10^{3})$, and Figure S6 shows how many
estimates were removed.

For the input queries, we include the 2-way marginals with Hours per week and
each of the independent variables Age, Race and Gender and income, as well as
the 2-way marginal between Race and Gender. The rest of the queries were
selected with the MST algorithm [39]. For MST, we used $\epsilon=0.5$ and
$\delta=\frac{1}{n^{2}}\approx 4.7\cdot 10^{-10}$, but we do not include this
in our figures, as we focus on the synthetic data generation, not query
selection. The selected queries are shown in Figure S1. The selection is very
stable: in 100 repeats of query selection, these queries were selected 99
times.

We chose the number of generated synthetic datasets for NAPSU-MQ and the
number of repeats for repeated PGM by comparing the results of the Adult
experiment for different choices. The results are shown in Figure S4 for
NAPSU-MQ and Figure S3 for repeated PGM. We chose $m=100$ for NAPSU-MQ because
it produces the narrowest confidence intervals, and $m=5$ repeats for repeated
PGM because it had the best calibration overall.

Figure S1:  Markov network of selected queries for the Adult experiment. Each
edge in the graph represents a selected 2-way marginal.  Figure S2: Ablation
Study Confidence Intervals. Figure S3:  Comparison of different numbers of
repetitions for repeated PGM on the Adult dataset with regularisation. We
chose $m=5$ repeats to represent repeated PGM in the main experiment, although
the differences between the numbers of repeats are small.  Figure S4:
Comparison of different numbers of generated synthetic datasets for NAPSU-MQ
on the Adult dataset with regularisation. The differences are small, but
$m=100$ synthetic datasets produces the narrowest intervals, so we chose it
for the main experiment.  Figure S5:  Results from the Adult data experiment
with the trick of dropping large variances in the logistic regression instead
of adding a small regularisation term. The results are almost identical to
Figure 4, except for RAP, which suffers from the regularisation.

(a)

(b)

Figure S6:  The fraction of coefficients dropped before Rubin’s rules because of very high estimated variances from the downstream logistic regression in the Adult data experiment for NAPSU-MQ in (a) and PGM-repeat in (b).  Figure S7:  The tradeoff between the confidence level for DP confidence intervals and the width of the intervals on the Adult dataset with regularisation. The width ratio on the y-axis is with regards to the original 95% confidence interval, for all confidence levels, so the plot shows how much must the confidence level drop to obtain the same width from a DP confidence interval as a non-DP one. The horizontal line at $y=1$ shows this point. For $\epsilon=1$, the confidence level for NAPSU-MQ must be dropped to about 75%, and for PGM-repeat, it must be dropped to about 50%.  Figure S8:  Comparison of marginal query accuracy for Adult data. NAPSU-MQ is almost as accurate as PGM for all values of $\epsilon$, and is on par with PGM-repeat. The panels show the average total variation distance of all 1-way marginal distributions (left) or all 2-way marginal distributions (right) between the original discretised data and synthetic data, averaged over 20 repeats. For NAPSU-MQ and PGM-repeat-$m$, the synthetic marginal distributions were estimated by averaging over $m$ synthetic datasets, with $m=100$ for NAPSU-MQ.  Table S1:  Runtimes of each inference run for the Adult experiment. Does not include the time taken to generate synthetic data, or run any downstream analysis. The LA rows record the runtime for obtaining the Laplace approximation for NAPSU-MQ that is used in the NUTS inference, so the total runtime for a NAPSU-MQ run with NUTS is the sum of the LA and NUTS rows. Experiments were run on 4 CPU cores of a cluster.  |  | Mean | Standard Deviation
---|---|---|---
Algorithm | Epsilon |  |
LA | 0.1 | 2 min 53 s | 18.5 s
0.3 | 3 min 53 s | 29.4 s
0.5 | 3 min 38 s | 35.0 s
1.0 | 3 min 25 s | 25.5 s
NUTS | 0.1 | 9 h 59 min 6 s | 6506 s
0.3 | 7 h 33 min 28 s | 2701 s
0.5 | 4 h 57 min 40 s | 3185 s
1.0 | 3 h 51 min 34 s | 1274 s
PEP | 0.1 | 6 min 50 s | 25.4 s
0.3 | 7 min 18 s | 31.2 s
0.5 | 7 min 0 s | 33.1 s
1.0 | 7 min 7 s | 33.7 s
PGM | 0.1 | 15 s | 0.5 s
0.3 | 17 s | 1.5 s
0.5 | 15 s | 0.4 s
1.0 | 15 s | 0.6 s
PGM-repeat-10 | 0.1 | 2 min 35 s | 3.3 s
0.3 | 2 min 53 s | 13.0 s
0.5 | 2 min 37 s | 5.0 s
1.0 | 2 min 36 s | 4.4 s
PGM-repeat-20 | 0.1 | 5 min 15 s | 10.9 s
0.3 | 5 min 58 s | 28.4 s
0.5 | 5 min 10 s | 10.2 s
1.0 | 5 min 13 s | 12.6 s
PGM-repeat-5 | 0.1 | 1 min 17 s | 2.7 s
0.3 | 1 min 28 s | 6.7 s
0.5 | 1 min 18 s | 2.6 s
1.0 | 1 min 18 s | 1.9 s
RAP | 0.1 | 32 s | 2.4 s
0.3 | 34 s | 2.2 s
0.5 | 32 s | 2.1 s
1.0 | 31 s | 2.1 s

##  Appendix G US CENSUS DATA EXPERIMENT

We conducted an additional experiment on US Census data from the UCI
repository [42]. We limited the data to individuals who have served in the US
Military, and picked 9 columns777 The columns are dYrsserv, iSex, iVietnam,
iKorean, iMilitary, dPoverty, iMobillim, iEnglish and iMarital. , most
relating to military service. Even this subset of the data is large, with
$n=320\,754$. All columns are discrete, and have $10\,800$ possible values,
much fewer than the Adult experiment.

As the downstream task, we use logistic regression with dPoverty as the
dependent variable and iSex, iKorean, iVietnam and iMilitary as the
independent variables. dPoverty has three categories, so we combine the two
categories denoting people below the powerty line to make the dependent
variable binary for the logistic regression, but not synthetic data
generation.

As our queries we use 4 three-way marginals covering the independent and
dependent variables, and 3 two-way marginals that include the other variables
that are synthesised, but not included in the regression. As the published
implementation of RAP [2] does not support a mix of two- and three-way
marginals, we replace the two-way marginals with three-way marginals for RAP.
As in the Adult experiment, we set $\delta=n^{-2}\approx 9.7\cdot 10^{-12}$,
and vary $\epsilon$.

As in the adult experiment, we use $n_{Syn}=n$ for all algorithms except RAP.
For PGM-repeat and NAPSU-MQ, we choose $m$ with a preliminary experiment. For
NAPSU-MQ, we set $m=100$, although the differences between the choices are not
large. For PGM-repeat, we set $m=10$. We set the other hyperparameters for all
algorithms after testing runs to the same values used in the Adult experiment,
except we increased the number of optimisation iterations for PGM to 10 000
from the default of 1000, the number of iterations for PEP to 10 000 from
1000, and increased the number of kept samples in NUTS to 4000 for NAPSU-MQ.
We did not use the trick of dropping estimates with very high variances, or
using very small regularisation in the logistic regression with the US Census
data.

The results are shown in Figure S9. While PGM is calibrated with $\epsilon\geq
0.3$, it is severely overconfident with $\epsilon=0.1$. This is likely caused
by the large size of the dataset: at larger values of $\epsilon$, there is
little noise compared to the large sample size, while at $\epsilon=0.1$, the
noise has a clear effect.

NAPSU-MQ and PGM-repeat are able to produce calibrated results at
$\epsilon=0.1$. Of these, NAPSU-MQ produces clearly narrower confidence
intervals for all values of $\epsilon$.

Figure S10 shows the accuracies of the produced synthetic datasets on all
1-way and 2-way marginal queries for the algorithms. As with the Adult
dataset, shown in Figure S8, NAPSU-MQ is almost as accurate as PGM, and is
equally accurate as PGM-repeat. For $\epsilon\geq 0.5$, all of the
aforementioned algorithms are almost as accurate. RAP and PEP are nowhere
close to these algorithms in accuracy, having errors that are several times
larger than the other algorithms.

For some reason, PEP fails completely with this dataset. We are not sure what
causes this, as the algorithm should work in this setting as well as it did
with the Adult dataset, and the size of the dataset should not be an issue.

The runtimes for each algorithm are shown in Table S2. The difference between
PGM-repeat and NAPSU-MQ is much smaller than in the Adult data experiment, but
is still large.

Figure S9:  Results for the US Census experiment, showing that only NAPSU-MQ and PGM-repeat are calibrated for all values of $\epsilon$, and NAPSU-MQ produces significantly narrower confidence intervals than PGM-repeat. Like Figure 4, the top row shows the mean coverage over all coefficients and 20 runs for different confidence levels. The bottom row shows median confidence interval widths divided by real data confidence interval widths. $\delta\approx 9.7\cdot 10^{-12}$ in all panels. Figure S10:  Comparison of marginal query accuracy for US Census data. NAPSU-MQ is almost as accurate as PGM for all values of $\epsilon$, and is on par with PGM-repeat, as with the Adult data in Figure S8. The panels show the average total variation distance of all 1-way marginal distributions (left) or all 2-way marginal distributions (right) between the original discretised data and synthetic data, averaged over 20 repeats. For NAPSU-MQ and PGM-repeat-$m$, the synthetic marginal distributions were estimated by averaging over $m$ synthetic datasets, with $m=100$ for NAPSU-MQ. RAP and PEP have average total variation distances over 0.1 for both 1-way and 2-way marginals for all values of $\epsilon$.  Table S2:  Runtimes of each inference run for the US Census experiment. Does not include the time taken to generate synthetic data, or run any downstream analysis. The LA rows record the runtime for obtaining the Laplace approximation for NAPSU-MQ that is used in the NUTS inference, so the total runtime for a NAPSU-MQ run with NUTS is the sum of the LA and NUTS rows. Experiments were run on 4 CPU cores of a cluster.  |  | Mean | Standard Deviation
---|---|---|---
Algorithm | Epsilon |  |
LA | 0.1 | 2 min 2 s | 76.8 s
0.3 | 1 min 35 s | 23.8 s
0.5 | 1 min 51 s | 44.0 s
1.0 | 1 min 51 s | 44.8 s
NUTS | 0.1 | 3 h 32 min 25 s | 2836 s
0.3 | 1 h 57 min 45 s | 989 s
0.5 | 1 h 31 min 15 s | 951 s
1.0 | 1 h 8 min 6 s | 477 s
PEP | 0.1 | 17 s | 0.6 s
0.3 | 18 s | 1.0 s
0.5 | 17 s | 0.4 s
1.0 | 17 s | 0.5 s
PGM | 0.1 | 1 min 57 s | 2.8 s
0.3 | 1 min 58 s | 3.2 s
0.5 | 1 min 57 s | 4.2 s
1.0 | 1 min 57 s | 3.2 s
PGM-repeat-10 | 0.1 | 19 min 22 s | 28.0 s
0.3 | 19 min 18 s | 21.9 s
0.5 | 19 min 36 s | 33.9 s
1.0 | 19 min 25 s | 22.0 s
PGM-repeat-20 | 0.1 | 38 min 38 s | 50.2 s
0.3 | 38 min 59 s | 37.5 s
0.5 | 38 min 57 s | 40.5 s
1.0 | 38 min 39 s | 74.7 s
PGM-repeat-5 | 0.1 | 9 min 45 s | 17.6 s
0.3 | 9 min 38 s | 8.9 s
0.5 | 9 min 45 s | 12.8 s
1.0 | 9 min 43 s | 9.8 s
RAP | 0.1 | 28 s | 2.4 s
0.3 | 28 s | 2.0 s
0.5 | 27 s | 1.2 s
1.0 | 27 s | 3.5 s