# Differentially Private Data Generation with Missing Data

Shubhankar Mohapatra, Jianqiao Zong, Florian Kerschbaum, Xi He  University of
Waterloo shubhankar.mohapatra, jianqiao.zong, florian.kerschbaum,
<EMAIL_ADDRESS>
###### Abstract.

Despite several works that succeed in generating synthetic data with
differential privacy (DP) guarantees, they are inadequate for generating high-
quality synthetic data when the input data has missing values. In this work,
we formalize the problems of DP synthetic data with missing values and propose
three effective adaptive strategies that significantly improve the utility of
the synthetic data on four real-world datasets with different types and levels
of missing data and privacy requirements. We also identify the relationship
between privacy impact for the complete ground truth data and incomplete data
for these DP synthetic data generation algorithms. We model the missing
mechanisms as a sampling process to obtain tighter upper bounds for the
privacy guarantees to the ground truth data. Overall, this study contributes
to a better understanding of the challenges and opportunities for using
private synthetic data generation algorithms in the presence of missing data.

##  1\. Introduction

Our world as we see it today revolves around private data regarding our
medical, financial, and social information. It is sometimes imperative to
query such data for research and advancement of science (Kass et al., 2003;
Andreou et al., 2013). Many industries also use statistics from private data
to improve their products and user experience. However, reckless data sharing
for data-driven applications and research causes great privacy concerns
(Auxier et al., 2019; IBM, 2020) and penalties (GDP, 4 27). As a response,
differential privacy (DP) (Dwork, 2006) has emerged as a standard data privacy
guarantee which has now been adopted by government agencies (Abowd, 2018;
Hawes, 2020) and companies (Erlingsson et al., 2014; Greenberg, 2016; Johnson
et al., 2018). Informally, DP guarantees that the output distribution of an
algorithm is similar with or without a particular individual in the dataset. A
privacy budget is set to limit the total privacy loss and each query (e.g.,
releasing statistics (Abowd, 2018; Bureau, 1 30), building prediction models
(Papernot et al., 2018; Abadi et al., 2016), and answering SQL queries (Ge et
al., 2019; Johnson et al., 2018; Kotsogiannis et al., 2019; McSherry, 2009))
consumes part of the privacy budget, and once that budget is used up, no more
queries can be answered directly. An alternative way is to generate a
synthetic dataset using the privacy budget. The synthetic dataset, once
generated, can be made public, and the analyst can use it for any number of
downstream tasks (Chen et al., 2018; Chen et al., 2015; Jordon et al., 2019;
Zhang et al., 2014; Barak et al., 2007).

Despite a number of work (Zhang et al., 2014; Ge et al., 2021; Phan et al.,
2016; Jordon et al., 2019) that succeed in generating synthetic data with DP
guarantees, they only look at a simple scenario where the input data has no
missing values. Several prior studies (Little and Rubin, 2019; Getz et al.,
2023) have reported on the prevalence of missing data in various fields. For
instance, a study of 9 publicly available healthcare datasets commonly used in
machine learning research found that the proportion of missing values ranged
from 0.2% to 78.6% (Getz et al., 2023). The presence of missing data can be
attributed to multiple reasons, such as human errors (Agarwal and Singh, 2021)
and privacy regulations like GDPR (GDP, 4 27) which allow people the “right to
forget” where one may ask their data to be deleted completely (Politou et al.,
2018). Simply ignoring such missing data could result in a reduction of
statistical power and an increase in estimation bias (Nakagawa and Freckleton,
2008). In our work, we ask how missing data will affect the quality of the
synthetic data generated by mechanisms that offer DP guarantees. Our
preliminary study shows that existing DP mechanisms have 4%-18.5% decay in the
F1-score of downstream ML tasks on the synthetic dataset generated from a
dataset with 10% missing values as compared to that when generated from the
complete dataset. The decay varies depending on the types of missing
mechanisms and the types of data generation processes. Hence, there is a need
to understand this practical problem of DP synthetic data generation with
missing data.

In our work, we formally define the research problem of generating synthetic
data for sensitive data with missing values using DP. We consider a missing
mechanism that takes complete ground truth data and outputs data with missing
values. Under this setup, we can offer DP to either the incomplete data or the
ground truth data. For each privacy guarantee, we study how to handle missing
data in the synthetic data generation process. We explore several techniques,
including the vanilla approach that uses complete rows only, common imputation
techniques (e.g., statistical methods, hot and cold deck methods), and machine
learning methods. Unfortunately, these methods have their limitations, such as
discarding too many rows or incurring high privacy costs, leading to poor-
quality synthetic data. To overcome these limitations, we present three ways
to amend the existing algorithms for better utility. We call these amended
approaches adaptive recourse strategies.

In addition, we show the relationship between the privacy guarantee for these
DP mechanisms that they offer for the incomplete data and that for the ground
truth data. To do so, we model the missing mechanism as a sampling process and
obtain a tighter upper bound for the privacy loss to the ground truth data via
sampling amplification techniques (Balle et al., 2018; Steinke, 2022). Unlike
prior work for sampling amplification that considers a random subset, we make
use of the randomness due to missing values to amplify the privacy for ground
truth data. The major contributions of our work are as follows:

  * $\bullet$

We are the first to formalize and study the problems of DP synthetic data with
missing data. Our results show that existing algorithms have a decrease of
5-23% in utility with $\leq$ 5% missing values and a decrease of 10-190% with
$\leq$ 20% missing values.

  * $\bullet$

We develop three novel adaptive approaches, each tailored to an existing
category of DP mechanisms, that seamlessly combine missing data imputation
with the learning process. Our evaluation shows that they improve the utility
of the synthetic datasets by up to 15-72%. These simple yet effective
approaches sometimes even achieve the same utility as the synthetic data
generated from the no-missing ground truth data.

  * $\bullet$

We differentiate the privacy guarantees for both incomplete and ground truth
data. Our analysis develops sufficient conditions that when satisfied, the
algorithms for the incomplete data can be used to achieve privacy for the
ground truth data.

  * $\bullet$

We are the first to apply amplification due to missing mechanisms and tighten
the privacy bound for ground truth data. The amplified ground truth privacy is
0.1-0.65x the privacy achieved for the incomplete data with 10-50% missing
values.

##  2\. Preliminaries

We consider a database relation $R=\\{A_{1},\cdots,A_{k}\\}$ with $k$
attributes, and a database instance $D$ consisting of $n$ rows. We use $D_{i}$
to refer to the $i$th row of $D$, and $D_{ij}$ to refer to the $j$th attribute
of row $D_{i}$. We also use $S_{:i}$ to denote all elements from $1$ to $i$ in
a sequence $S$.

###  2.1. Missing Data

For missing data, we define a missingness indicator matrix
$M=[\ldots,m_{ij},\ldots]$ of size $n\times k$, where $i\in[1,n],j\in[1,k]$
and, shorthand $m_{i}$ to point to $i^{th}$ row of $M$. Each cell of $M$ has
one-to-one relation with $D$ such that, $m_{ij}=1$ if $D_{ij}$ is missing and
$m_{ij}=0$ otherwise.

Missing data is classified into different types using missing mechanisms. A
missing mechanism $M_{\phi}:\mathcal{D}\rightarrow\mathcal{D}$ takes as input
the ground truth dataset $\bar{D}$ and outputs an incomplete dataset $D$. It
is parameterized by $\Phi$, a set of probabilities, which refers to the set of
probabilities that control the unknown missing data process. Three missing
types can be defined using $\Phi$ and the conditional distribution of missing
indicator $m_{i}$ given the dataset $D_{i}$ (Little and Rubin, 2019; Rubin,
1976).

Missing completely at random (MCAR) assumes the probability of missingness is
completely independent of the data. Under MCAR, any two rows of the dataset,
regardless of their values, for the same attribute have the same probability
of having a missing value. Hence, the parameter set $\Phi$ consists of
$\\{\phi_{j}|j\in[1,k]$}, where $\phi_{j}$ is the probability of any row
having a missing value for the $j$th column. For $j\in[1,k]$ and $i\in[1,n]$,
$\Pr[m_{ij}|D]=\Pr[m_{ij}]=\phi_{j}$. Hence, the probability of a row having
no missing values is $\prod_{j=1}^{k}(1-\phi_{j})$.

Missing at random (MAR) captures the scenario when the probability of
missingness is independent of the missing values given the observed data. In
other words, under MAR how likely a value is to be missing can be estimated
based on the non-missing data. Consider examples, 1) Young people have missing
IQ (because they haven’t taken an IQ test yet), and MAR models the same
probability of missing IQ attribute for rows of the same age, regardless of
their IQ values; 2) Businessmen are less likely to share their income, and MAR
models the same probability for income values for rows that have an occupation
as ‘Business.’ MAR, therefore, is parameterized by a set of conditional
probabilities $\Phi$ where each $\phi\in|\Phi|$ maps relationships between
observed and missing values in the dataset. For $\phi_{x}\in\Phi$ that models
the $j$th column’s missingness, and for $i\in[1,n]$,
$\Pr[m_{ij}|D_{i(0)}]=\Pr[m_{ij}|D_{i(0)},D_{ij}]=\phi_{x}$, where $D_{i(0)}$
refers to the observed attributes for the $i$th row.

Missing not at random (MNAR) captures the scenario when given all the observed
information, the probability of missingness depends on the unobserved missing
values themselves. Consider examples, 1) Students with low scores are unlikely
to express their scores, and MNAR models the probability of the missing scores
depends on the actual value of the score attribute of the students. 2) People
who smoke don’t want to mention they smoke. Here MNAR models the probability
of missing smokers based on the attribute of smoking. With MNAR missingness,
$\Phi$ consists of a set of conditional probabilities that map the probability
of an attribute to be missing given its own value.

In practice, a dataset might have one or more types of missing data and
without prior domain knowledge, it is hard to determine the missing type. Some
prior work propose statistical tests to infer whether the missing type is
MCAR. These include the Little’s MCAR test (Little, 1988) and pattern mixture
models (Little, 1994). However, there exists no effective method for MAR and
MNAR missing types because it may depend on a combination of observed
variables, unobserved variables, and interactions between them (Van Buuren,
2018). Some binary indicator tests based on modeling techniques exist for MAR
but they are not definitive and are sensitive to the specific assumptions made
during analysis. For private datasets, these tests also need to be computed
privately by using a portion of the privacy budget.

###  2.2. Differential Privacy

Differential privacy (DP) (Dwork et al., 2006b; Dwork et al., 2006a) is used
as our measure of privacy.

###### Definition 2.1 (Differential Privacy (DP) (Dwork and Roth, 2014; Dwork
et al., 2006a)).

A randomized algorithm $M$ achieves ($\epsilon,\delta$)-DP if for all
$Z\subseteq$ Range($\mathcal{M}$) and for two neighboring databases
$D,D^{\prime}\in\mathcal{D}$ that differ in one row:

$\Pr[\mathcal{M}(D)\in Z]\leq e^{\epsilon}\Pr[\mathcal{M}(D^{\prime})\in
Z]+\delta.$

The privacy cost is measured by the parameters ($\epsilon,\delta$), often
referred to also as the privacy budget. The smaller the privacy parameters,
the stronger the offered privacy.

Gaussian mechanism (Dwork and Roth, 2014) and Laplace mechanism (Dwork et al.,
2006b) are two such widely used DP algorithms. Given a function
$f:\mathcal{D}\rightarrow\mathbb{R}^{d}$, the Gaussian mechanism adds noise
sampled from a Gaussian distribution $\mathcal{N}(0,S_{f}^{2}\sigma^{2})$ to
each component of the query output, where $\sigma$ is the noise scale and
$S_{f}$ is the $L_{2}$ sensitivity of function $f$, which is defined as
$S_{f}=\max_{D,D^{\prime}\text{differ in a row}}||f(D)-f(D^{\prime})||_{2}$.
For $\epsilon\in(0,1)$, if $\sigma\geq\sqrt{2\ln(1.25/\delta)}/\epsilon$, the
Gaussian mechanism satisfies $(\epsilon,\delta)$-DP. Laplace mechanism works
similarly but with the noise from the Laplace distribution and the $L_{1}$
sensitivity. Both these mechanisms have been applied to answer counting
queries (Li et al., 2015) and is widely used in estimating low dimensional
statistics about the dataset.

Complex DP algorithms can be built from these basic algorithms following two
important properties of DP: 1) Post-processing (Dwork et al., 2006a) states
that for any function $g$ defined over the output of the mechanism
$\mathcal{M}$, if $\mathcal{M}$ satisfies ($\epsilon,\delta$)-DP, so does
$g(\mathcal{M})$; 2) Composability (Dwork, 2006) states that if
$\mathcal{M}_{1}$, $\mathcal{M}_{2}$, $\cdots$, $\mathcal{M}_{k}$ satisfy
($\epsilon_{1},\delta_{1}$)-, ($\epsilon_{1},\delta_{1}$)-, $\cdots$,
($\epsilon_{k},\delta_{k}$)-DP, then sequentially applying these mechanisms
satisfies ($\sum_{i=1}^{k}\epsilon_{i},\sum_{i=1}^{k}\delta_{i}$)-DP.

Stability of transformations Datasets often require certain transformations as
a preprocessing step. Examples are SQL operators (e.g., Where, Select,
Groupby, scaling, and imputation). When the dataset is private, these
transformations should also be accounted for in the privacy analysis.

###### Theorem 2.2.

(McSherry, 2009) We say a transformation $T(\cdot)$, $c$-stable, if the
distance between $T(D)$ and $T(D^{\prime})$ is at most $c$ times the distance
between $D$ and $D^{\prime}$. The composite mechanism $\mathcal{M}\circ T$
then becomes $(c\cdot\epsilon,\delta)$-DP, for any mechanism $\mathcal{M}$
which is $(\epsilon,\delta)$-DP.

###  2.3. DP Synthetic Data Generation

A common DP study is to generate synthetic data given a fixed privacy budget.
The synthetic data, once generated, can be made public and all queries on this
dataset come for free due to the post-processing property of DP. There are
three main approaches for DP synthetic data generation (Tao et al., 2021):

Statistical approaches rely on estimating low-dimensional statistics about the
dataset such as marginals (Xiao et al., 2011; Qardaji et al., 2014). These
approaches can be made better by finding the correlation between attributes.
Techniques for improvement include probabilistic models (Koller and Friedman,
2009), Bayesian models (Zhang et al., 2014; Li et al., 2014; Ping et al.,
2017) and undirected graphs (Chen et al., 2015; McKenna et al., 2019).
Statistical approaches capture the underlying distribution of the correlated
independent attributes very well but fail to imbibe complex relationships
between multiple attributes.

Deep learning approaches have shown promise in generating synthetic data
(Shrivastava et al., 2017; Chawla, 2019; Gupta, 2019), especially autoencoders
and generative adversarial networks (GAN). Autoencoders map the dataset into a
well-behaved low-dimensional feature space, which can be sampled to create
synthetic data. GANs contain two neural network structures called the
generator and the discriminator. The generator generates fake examples and the
discriminator tries to distinguish between a real and fake example. Once they
have converged, the generator can be used to generate synthetic data. A common
technique to make these private is by using DPSGD (Williams and McSherry,
2010; Bassily et al., 2014; Song et al., 2013; Abadi et al., 2016). Multiple
deep learning approaches have been thus proposed privately for autoencoders
(Phan et al., 2016; Abay et al., 2018; Acs et al., 2018) and GANs (Frigerio et
al., 2019; Jordon et al., 2019; Torkzadehmahani et al., 2020; Xie et al.,
2018). They work well on image data but have trouble generating tabular data
due to poor encoding schemes for categorical data. Towards this end,
conditional GANs (Xu et al., 2019) and their private counterparts
(Torkzadehmahani et al., 2019) have been proposed in which the generators
sample based on the conditional probability of the categorical attribute’s
density.

Mixed approaches are inspired by both the above approaches and try to preserve
both low-dimensional statistics and high-level information. Some techniques
include leveraging the dimensionality reduction via random orthonormal (RON)
projection, the Gaussian generative model (Chanyaswad et al., 2019), combining
denial constraints and attribute-wise embedding models (Ge et al., 2021) and
Gretel.ai statistics (Noruzman et al., [n.d.]).

##  3\. Problem Statement

Consider a private dataset that lies behind a privacy firewall with $n$ rows
and $k$ attributes. A trusted curator wants to generate a synthetic version
for this dataset of the same size with an end-to-end ($\epsilon,\delta)$-DP
guarantee while achieving maximum utility (same statistics and correlations)
of the synthetic dataset as compared to the original one. In practice, the
data collected by the data curator can contain missing values. Prior work does
not consider an end-to-end solution for this scenario. Hence, in our work, we
consider the case when the private data has missing values. Depending on the
consideration of privacy, we formalize two versions of the problem. First, we
consider offering a DP guarantee to the incomplete dataset held by the data
curator. We formalize this problem as follows.

###### Problem 1.

[Privacy for Incomplete Data] Consider collecting data from a ground truth
data $\bar{D}$ of $n$ rows owned by $n$ individuals, a missing mechanism
$M_{\Phi}:\mathcal{D}\rightarrow\mathcal{D}$ is involved that takes in
$\bar{D}$ and outputs a dataset $D$ of $n$ rows but with missing values. A
trusted data curator uses this dataset $D$ as an input and aims to generate a
synthetic data $D^{*}$ of $n$ rows with a mechanism
$M:\mathcal{D}\rightarrow\mathcal{D}$ such that $D^{*}$ share similar
statistics and correlations as the ground truth data $\bar{D}$ and $M$ offers
$(\epsilon,\delta)$-DP to the input data $D$.

In Section 4, we delineate multiple options for the data curator to deal with
incomplete data, put forward challenges that come with them, and discuss which
option might be the best and when. The first option is a naïve adaptation of
prior work for DP data generation by simply discarding the rows with missing
values (Rubin, 1976). We refer to this approach as _complete row only_. This
approach can fail in many cases, as detailed in Section 4.1. For instance, if
all rows have some missing values, then there will be no input data for the
data generation methods. A second approach is to impute the missing parts with
inferred values from the observed data. We denote this approach as _imputation
first approach_. However, as our data is private, the imputation process needs
to be privatized as well and the additional incurred privacy cost must be
accounted for in the privacy budget. In section 4.1, we explore the privacy
costs of imputation and show how they can be expensive in practice. Rather
than having separate processes for imputation and synthetic data generation,
we can integrate these two processes into one. This line of thought motivates
us to a new approach, which we call _adaptive recourse approach_. In Section
4.2, we improve upon three categories of DP generation approaches and
demonstrate their effectiveness in generating synthetic data from incomplete
data. These strategies use no extra privacy budget and solely improve by
observing available data in the dataset.

The incomplete data $D$ can be modeled as a sample generated from a complete
ground truth dataset $\bar{D}$ via a missing mechanism $M_{\Phi}$. If the
privacy goal is to protect the ground truth dataset $\bar{D}$ with DP
guarantee, how will the problem and the solution be different? We formalize
the second problem as follows.

###### Problem 2.

[Privacy for Ground Truth Data] Consider the same setup as Problem 1. The
trusted data curator uses the incomplete dataset $D$ as input and aims to
generate a synthetic data $D^{*}$ of $n$ rows with a mechanism
$M:\mathcal{D}\rightarrow\mathcal{D}$ such that $D^{*}$ share similar
statistics and correlations as the ground truth data $\bar{D}$ and $M\circ
M_{\Phi}$ offers $(\bar{\epsilon},\bar{\delta})$-DP to the ground truth data
$\bar{D}$.

The above problem differs from our first problem only in the last line, where
we are trying to achieve DP not for the observed incomplete data but instead
for the ground truth data. The missing mechanism allows only partial
information to be available to the synthetic data generation process. At first
look, these two problems seem the same — guaranteeing privacy for the
incomplete data offers privacy to the ground truth data, but they are not
equivalent. In Section 5, we look closely into their relationship. We show
when privacy for the incomplete data can fail privacy for the ground truth
data, and when it cannot. We also present how the missing mechanism can be
used as a sampling mechanism to gain in terms of privacy and ultimately reach
more useful synthetic data. There are several theorems and lemmas in the
paper, the proofs for some of which are available in the longer version of the
paper (Mohapatra et al., 2023).

##  4\. Privacy for Incomplete Data

This section examines Problem 1 and explores methods for generating synthetic
data from an incomplete private dataset. The section starts by discussing two
vanilla methods that are found to be ineffective in the DP context and instead
recommends adaptive recourse methods that are novel solutions that address
both issues and produce better-quality synthetic data.

Figure 1. Random imputation from the domain of attributes performs worse that
complete row only approach.

###  4.1. Vanilla Approaches

Complete row only and imputation first are two traditional methods for
handling missing data. These methods either involve discarding rows with
missing values or filling up missing information with values inferred from the
observed data. and imputations.

Complete Row Only Approach. This approach is effective when the missingness is
completely at random (MCAR) since the distribution of each attribute remains
the same after removing missing rows. However, for other types of missingness,
such as missing at random (MAR) and missing not at random (MNAR), the complete
row only approach can lead to biased results. Hence, a standard synthetic data
generation algorithm that learns directly from the remaining complete rows
will result in a biased data distribution that is different from the ground
truth data.

Figure 2. Complete row only approach results in poor results for MAR and MNAR
missing mechanism.

Figure 2 illustrates the performance of four different DP synthetic data
generation algorithms using the complete row only approach for the Adult
dataset with various missing mechanisms. The results indicate that the
complete row only approach performs poorly for missing at random (MAR) and
missing not at random (MNAR) mechanisms, which introduce bias to the estimated
distribution of attributes. This bias can directly affect statistical
approaches such as PrivBayes which rely heavily on empirical estimation of
marginals. The 1-way distance between the generated synthetic dataset and the
original dataset confirms this observation.

Besides the potential bias issue for the complete row only approach, the
number of complete rows remaining can be very small. For synthetic data
generation methods involving large deep learning models such as GAN, feeding
the training process with a small number of complete rows will result in a
poor data generation model. This is because the learning process does not
converge or/and the noise added for achieving DP overshadows the signals of
the training samples. For example, the ground truth Adult dataset which has
32k rows reduces to $\approx 5$k complete rows with 20% MAR and $\approx 1$k
complete rows with 20% MCAR/MNAR missing mechanism respectively. Our results
show that the number of complete rows plays a vital role in the performance of
the synthetic data generation algorithms. We discuss this in detail in Section
6 where we study several prior work approaches and evaluate them on the
different missing data scenarios.

Imputation First Approach. Imputation is vastly used in practice where the
missing data are filled up with values inferred from the observed data. There
are multiple ways to impute missing values in the dataset, including:

  1. (1)

Statistical methods: Each attribute of the dataset is modeled separately using
statistical methods such as mean, median, and mode. The model is then used to
fill up the missing values of the attribute (Little and Rubin, 2019; Rubin,
1976). For example, in Figure 3, for the left tables, we use the median of the
observed values of column A, to fill up the missing value of the 4th row.

  2. (2)

Hot and cold deck methods: This imputation technique replaces every missing
value with another value from the same dataset (Hot deck) or from a proxy
dataset (Cold deck) (Andridge and Little, 2010; Nordholt, 1998). The missing
cells of the incomplete row are then filled up from the closest similar row.
Similarity metric like cosine distance or $\ell_{2}$ distance can be used.

  3. (3)

ML imputation: Machine learning (ML) based approaches are common for missing
data imputation (Jerez et al., 2010; Lakshminarayan et al., 1996). An ML model
is trained to predict the missing values of an attribute based on other non-
missing attributes in the dataset as training features.

In our setting, as the dataset is private, we need to perform these
imputations privately as well. A naive way to privately impute the dataset
without any privacy cost is by randomly choosing values from the domain of the
missing attribute. However, as we show in Figure 1, this naive imputation
technique (green bar) performs worse than the complete row only approach
(orange bar) even for the easiest to handle 10% MCAR missing data in the Adult
dataset. Therefore, we move forward to analyze other popular imputation
approaches that entail privacy costs. We skip analysis of the cold deck
imputation as finding another similar dataset is hard for a private dataset
without any prior information.

We can perform DP imputation in two ways. The first way is to split the
privacy budget and use the first split for imputation and the second split for
synthetic data generation. For example, the partial budget can be used to
privately train an ML model on the observed features for imputation (Abadi et
al., 2016; Bassily et al., 2014; Williams and McSherry, 2010; Song et al.,
2013). However, this approach is staggered due to tuning of the right budget
split and choice of imputation algorithm. Additionally, some imputation
techniques such as the hot deck imputation that are row specific (replicates
the missing value in a row based on some other observed value of a different
user) cannot be performed in the DP setting. Randomizing this row to achieve
DP introduces too many errors to the dataset.

The second way is to formulate imputation as a transformation of the dataset
and calculate the associated privacy cost as an end-to-end algorithm. We use
the notion of stability (Theorem 2.2) to calculate the privacy costs of these
transformations.

###### Lemma 4.1.

Consider a transformation $T_{A}(\cdot)$ for imputing attribute $A$, which
takes in the incomplete dataset $D$ as part of the input and outputs a dataset
$D^{\prime}$ with the complete values for attribute $A$. Then, the stability
of $T_{A}(\cdot)$ is $c=m_{A}+1$ where $m_{A}$ refers to the number of missing
values for the attribute $A$.

###### Proof.

As the neighboring databases $D$ and $D^{\prime}$ differ by a row,
$T_{A}(\cdot)$ uses two different values $x$ and $x^{\prime}$ to impute the
missing values in $D$ and $D^{\prime}$ respectively. As there are $m_{A(1)}$
rows in both $D$ and $D^{\prime}$ that have missing values for attribute $A$,
the resulted imputed databases, $T(D)$ and $T(D^{\prime})$ have $m_{A(1)}+1$
number of rows (include the row that $D$ and $D^{\prime}$ differ). ∎

Using the above Lemma we can see that applying a sequence of imputation
functions over the attributes of a dataset $(\cdots,T_{A_{i}},\cdots\\}$, the
difference in the resulted datasets can be very large when the input dataset
differs in a single row. Note that these results hold even if imputation
functions for two attributes are not the same.

###### Theorem 4.2.

The composite mechanism $\mathcal{M}\circ T$ on a dataset $D$ with $n$ rows is
$n\epsilon$-DP, where $\mathcal{M}$ is a $\epsilon$-DP mechanism, and $T$ is a
sequence of imputation functions performed to each attribute of $D$.

###### Proof.

Consider a worst-case scenario: $D$ and $D^{\prime}$ differ in a single row
that does not have any missing values, and the rest of the rows have only one
attribute with missing values, i.e., $\sum_{i}m_{A_{i}}=n-1$. As $T$ uses the
complete row to impute all the missing values, all rows will be affected and
the overall cost of $M\circ T$ will be $n\epsilon$-DP. ∎

###### Example 4.3.

In Figure 3, we illustrate two worst-case toy examples for a dataset with two
columns using mean and median imputations. The gray color indicates missing
values and dotted lines denote differing rows between the top and the bottom
datasets for each example. The missing values in both columns in the left and
right examples are filled up with mean and median functions respectively.
After applying imputations on the neighboring datasets $D$ and $D^{\prime}$,
the number of rows in column $B$ in both examples starts to differ by $4$ rows
and $5$ respectively including the imputed values and the differing row. In
such a scenario, one needs to pay $4\epsilon$ or $5\epsilon$ privacy cost to
ensure DP to the incomplete data.

Figure 3. Illustration of worst case statistical imputations.

###  4.2. Adaptive Recourse Approach

We have shown that the above two approaches suffer from ineffective use of the
data or privacy budget. The complete row only approach ends up discarding
several partial rows which could have been used in the learning process while
the imputation first approach ends up with a high privacy cost. These issues
motivate us to adapt the existing synthetic data generation methods to capture
both the information in the dataset and the privacy budget. We call such an
approach _adaptive recourse_. The idea is to utilize the privacy-preserving
learning part of the synthetic data generation process for both the imputation
and the sampling of the synthetic data. This is beneficial for two reasons.
First, the privacy budget is solely spent on the learning of a single model.
Second, the imputation process allows more complete training examples to be
generated for the iterative learning process, which further improves the
utility of the model. For this approach, we present three sub-approaches,
depending on the underlying data generation methods, including generative
adversarial networks (GAN), partial marginal observation, and column-wise data
generation. For each algorithm, we provide an algorithm instance to illustrate
their effectiveness in generating synthetic data from an incomplete dataset.

0: Incomplete dataset $D$, noise scale $\sigma$, epochs $E$, learning rates
$\eta_{D}$ and $\eta_{G}$, generator interval $T_{G}$, batch size $B$, missing
indicator matrix $M$

1: Initialize data generator $\theta^{D}_{G}$ and discriminator
$\theta^{D}_{D}$

2: Initialize mask generator $\theta^{M}_{G}$ and discriminator
$\theta^{M}_{D}$

3: for $i$ in [$1,\dots,E$] do

4: Subsample dataset $D$ into $\\{S_{k}\\}^{k=(|D|/B)}_{k=1}$ subsets

5: for $t$ in [$1,\dots,|D|/B$] do

6: Set real data $x_{data}=S_{t}$

7: Sample real mask $x_{mask}$ from missing indicator $M(S_{t})$

8: Fill missing values in $x_{data}$ with $0$

9: Generate fake data and mask $y_{data}=\theta^{D}_{G}(z)$ where
$z\sim\mathcal{N}(0,1)$ $y_{mask}=\theta^{M}_{G}(z)$ where
$z\sim\mathcal{N}(0,1)$

10: Update
$\theta^{D}_{D}=\theta^{D}_{D}-\eta_{D}\nabla_{\theta^{D}_{D}}[\frac{1}{B}(\theta^{D}_{D};x_{data})-\frac{1}{B}(\theta^{D}_{D};y_{data})]$
$\theta^{M}_{D}=\theta^{M}_{D}-\eta_{D}\nabla_{\theta^{M}_{D}}[\frac{1}{B}(\theta^{M}_{D};x_{mask})-\frac{1}{B}(\theta^{M}_{D};y_{mask})]$

11: if $t$ in interval of $T_{G}$ then

12: Generate fake data and mask $y_{data}=\theta^{D}_{G}(z)$ where
$z\sim\mathcal{N}(0,1)$ $y_{mask}=\theta^{M}_{G}(z)$ where
$z\sim\mathcal{N}(0,1)$

13: Compute data and mask gradient
$g_{d}=\nabla_{\theta^{D}_{G}}(\theta^{D}_{D};y_{data})$,
$g_{m}=\nabla_{\theta^{M}_{G}}(\theta^{M}_{D};y_{mask})$

14: Clip each gradient
$\bar{g_{i}}_{d}={g_{i}}_{d}/\max(1,\|{g_{i}}_{d}\|_{2})$
$\bar{g_{i}}_{m}={g_{i}}_{m}/\max(1,\|{g_{m}}\|_{2})$

15: Compute noisy gradients
$\tilde{g_{i}}_{d}=\bar{g_{i}}_{d}+2\sigma\mathcal{N}(0,1)$
$\tilde{g_{i}}_{m}=\bar{g_{i}}_{m}+2\sigma\mathcal{N}(0,1)$

16: Update generators
$\theta^{D}_{G}=\theta^{D}_{G}-\eta_{D}\frac{1}{B}\tilde{g_{i}}_{d}$
$\theta^{M}_{G}=\theta^{M}_{G}-\eta_{D}\frac{1}{B}\tilde{g_{i}}_{d}$

17: end if

18: end for

19: end for

20: Generate and return synthetic dataset from generator $\theta^{D}_{G}$

Algorithm 1 DP-MISGAN

GAN-based adaptive recourse. In non-private literature, numerous approaches
use the GAN framework to deal with missing data (Yoon et al., 2018; Li et al.,
2019; Luo et al., 2019; Xu et al., 2020). One such leading approach is called
MisGAN (Li et al., 2019). The core idea of this approach is to use two
generator-discriminator pairs — one for learning the data distribution and the
other for learning the missingness pattern. We develop a DP version of this
generation method called _DP-MisGAN_.

A straightforward way to build DPMisGAN is to privatize the non-private
optimizer of the discriminator (Williams and McSherry, 2010; Bassily et al.,
2014; Song et al., 2013; Abadi et al., 2016). However, this approach requires
adding noise twice, which can harm the algorithm’s utility and double the
privacy cost. Furthermore, we observe that we only need to publish the
generators, not the discriminators. Hence, we resort to the gradient
sanitization (GS) approach (Chen et al., 2020), which perturbs gradients
transferred from the discriminators to the generators in order to achieve DP.

We present our DPMisGAN in Algorithm 1. DP-MisGAN, like its non-private
counterpart, trains two discriminator-generator pairs. The whole training
procedure lasts for $E$ number of epochs and on each epoch, it samples $|D|/B$
subsets without replacement from the given dataset $D$, where each subset has
a size of $B$ assuming the data size is a multiple of $B$ (Line 4). For each
subset $S_{t}$, DP-MisGAN sets $x_{data}$ as the real data (Line 6) and sets
$x_{mask}$ as its corresponding real missing mask (Line 7). The missing mask
$x_{mask}$ can be computed from the missing indicator matrix $M$ and
corresponds to an array of the same length $x_{data}$ that consists of $1$
where the data is missing and $0$ otherwise. All missing values in real data
$x_{data}$ are filled up with $0$s (Line 8). DP-MisGAN then creates two fake
examples $y_{data}$ and $y_{mask}$ by sampling two vectors of random initial
noise from a Gaussian distribution $\mathcal{N}(0,1)$ and passing it through
the data and mask generators respectively (Line 9). The previously computed
variables $x_{data}$ and $x_{mask}$ are then used as input for both these GANs
and updated using gradient descent. Each iteration $t$ involves two phases. In
the first phase, the discriminators learn the true mask and data distributions
(Line 10). The second phase trains the two generators and is executed only in
the user-inputted generator intervals $T_{G}$ (Line 11). In each generator
interval, two fake samples $y_{data}$ and $y_{mask}$ are again generated
similarly from the two generators (Line 12). These fake samples are used to
compute gradients from the discriminators (Line 13) and carefully noised to
ensure privacy (Line 14 - 15). Finally after the training is completed for $E$
epochs, the discriminators are thrown away and the privately learnt data
generator is used to sample synthetic data. In our work, we calculate the
final $\epsilon$ value using a privacy accountant (Abadi et al., 2016;
Alghamdi et al., 2022; Gopi et al., 2021) for the specified number of noise
additions done during the generator update interval.

DPMisGAN benefits in two ways by applying gradient sanitization (GS) to
achieve DP. First, noise is added only to the gradients of the generators in
the second generator training phase (Line 14). Second, the tedious procedure
of hyperparameter tuning for the gradient clip $C$ is skipped. Gradient
clipping helps to bound the sensitivity of $\|g\|_{2}<C$ by replacing the
vector $g$ by $g/max(1,\|g\|_{2}/C)$ in DPSGD and can be vastly detrimental if
set wrong (Mohapatra et al., 2021). The training of MisGAN assumes an
underlying Wasserstein-Gan (WGAN) (Arjovsky et al., 2017) framework with an
additional gradient penalty term in the loss function of the discriminator
that enforces the $\ell_{2}$-norm of the discriminator gradients to be
naturally close to $1$. Hence, there is no need of hyperparameter tuning for
$C$ and can be set to $1$ for the whole training procedure. Each generator
update step in the DPMisGAN procedure is privatized using the _sampled
Gaussian mechanism_ (SGM) (Mironov et al., 2019). A tight bound for the
privacy loss of the training procedure can be calculated using Rényi-DP (RDP).

###### Definition 4.4 (Rényi-DP (Mironov, 2017)).

A randomized algorithm $M$ with domain $\mathcal{D}$ is
$(\alpha,\epsilon)$-RDP at order $\alpha>1$, for any pair of neighbouring
databases $D,D^{\prime}\in\mathcal{D}$ that differ in one tuple. Let $P_{D}$
and $P_{D^{\prime}}$ be the output probability density of $\mathcal{M}(D)$ and
$\mathcal{M}(D^{\prime})$ respectively. Then, it holds that:
$\frac{1}{\alpha-1}\log\operatorname*{\mathbb{E}}_{x\sim\mathcal{M}(D^{\prime})}\left(\frac{P_{D}(x)}{P_{D^{\prime}}(x)}\right)^{\alpha}\leq\epsilon$.

The post-processing and composability properties of DP also apply to RDP.
Specifically, if a sequence of adaptive mechanisms $\mathcal{M}_{1}$,
$\mathcal{M}_{2}$, $\cdots$, $\mathcal{M}_{k}$ satisfy
($\alpha,\epsilon_{1}$)-, ($\alpha,\epsilon_{2}$)-, $\cdots$,
($\alpha,\epsilon_{k}$)-RDP, then the composite privacy loss is
($\alpha,\sum_{i=1}^{k}\epsilon_{i}$)-RDP. The RDP privacy loss of the
_sampled Gaussian mechanism_ (SGM) (Mironov et al., 2019) is given using Lemma
4.5.

###### Lemma 4.5.

Given a database $D$ and query $f:\mathcal{D}\rightarrow\mathbb{R}^{d}$ with
sensitivity $S_{f}$, returning $f(\\{x\in D\mid\text{x is sampled with
probability r}\\})+\mathcal{N}(0,S_{f}^{2}\sigma^{2}\mathbb{I}^{d})$ results
in the following RDP cost for an integer moment $\alpha$.

$R_{\sigma,r}(\alpha)=\begin{cases}\frac{\alpha}{2(S_{f}\sigma)^{2}}&r=1\\\
\sum_{k=0}^{\alpha}\binom{\alpha}{k}(1-r)^{\alpha-k}r^{k}\exp(\frac{\alpha^{2}-\alpha}{2(S_{f}\sigma)^{2}})&0<r<1\end{cases}$

We can now calculate the total RDP cost of DP-MisGAN by composing the cost of
each SGM in the training procedure.

###### Theorem 4.6.

The total RDP cost of DP-MisGAN is

$R(\alpha)=2\lceil\frac{T}{T_{G}}\rceil\sum_{k=0}^{\alpha}\binom{\alpha}{k}(1-\frac{B}{|D|})^{\alpha-k}\frac{B}{|D|}^{k}\exp(\frac{\alpha^{2}-\alpha}{8\sigma^{2}})$

###### Proof.

Let the gradient clipping procedure of the discriminator in DP-MisGAN be
$f=g/\max(1,\|g\|_{2}/C)$. The sensitivity $S_{f}$ can be thus be derived by
the reversed triangle inequality.

$S_{f}=\max_{D,D^{\prime}}\|f(D)-f(D^{\prime})\|\leq 2C\leq 2$

The last inequality follows as we set $C=1$ in DP-MisGAN. Each SGM in DP-
MisGAN (Algorithm 1) has sampling probability of $\frac{B}{|D|}$ and thus the
RDP cost of each SGM can be derived using Lemma 4.5 as
$\sum_{k=0}^{\alpha}\binom{\alpha}{k}(1-\frac{B}{|D|})^{\alpha-k}\frac{B}{|D|}^{k}\exp(\frac{\alpha^{2}-\alpha}{8\sigma^{2}})$.
DP-MisGAN consists of two generators that are updated every generator interval
$T_{G}$ each. Therefore, using the composition property of RDP, we can compose
the costs for both the discriminators in DP-MisGAN as
$R(\alpha)=2\lceil\frac{T}{T_{G}}\rceil\sum_{k=0}^{\alpha}\binom{\alpha}{k}(1-\frac{B}{|D|})^{\alpha-k}\frac{B}{|D|}^{k}\exp(\frac{\alpha^{2}-\alpha}{8\sigma^{2}})$.
∎

By the tail bound property of RDP (Mironov, 2017), we can convert the RDP cost
of DP-MisGAN to $(\epsilon,\delta)$-DP, where $\epsilon$ is computed by

(1) $\epsilon(\delta)=\min_{\alpha}R(\alpha)+\frac{\log(1/\delta)}{\alpha-1},$

for a given $\delta$. In practice, given the parameters
$\epsilon,\delta,B,T,T_{G}$, the $\sigma$ is calculated using Theorem 4.6 and
the order $\alpha$ is usually searched within a range of user input values
(Waites, 2019).

We expect DP-MisGAN to perform better than the naive GAN approaches because it
learns from both the complete rows as well as the incomplete rows of the
dataset. Furthermore, as DP-MisGAN learns the missing data pattern of the
incomplete dataset, we anticipate that it will capture more information in
complex MAR and MNAR missing mechanisms.

0: Incomplete dataset $D$, Attributes $\mathcal{A}$, Privacy budget
$\epsilon_{1},\epsilon_{2}$

1: Initialize Bayesian network $B$ of degree $k$ and $V=\phi$

2: Sample $X_{1}$ from $\mathcal{A}$ and add $(X_{1},\phi)$ to $B$; add
$X_{1}$ to $V$

3: for $i=2\dots|\mathcal{A}|$ do

4: Initialize $\Omega=0$

5: For each $X\in\mathcal{A}\setminus V$ and each $\Psi\in{\binom{V}{k}}$; add
$(X,\Psi)$ to $\Omega$

6: Select a pair $(X_{i},\Psi_{i})$ from $\Omega$ with maximal mutual
information in complete rows for attributes $X_{i}$ in D using exponential
mechanism of budget $\epsilon_{1}/|\mathcal{A}|$

7: Add $(X_{i},\Psi_{i})$ to $B$; add $X_{i}$ to $V$

8: end for

9: Initialize synthetic dataset $D^{*}$

10: for $i=1\dots|\mathcal{A}|$ do

11: Compute distribution from non-missing values $\Pr[X_{i},\Psi_{i}]$ from
the complete rows of $X_{i}$ in $D$

12: Learn $\Pr^{*}[X_{i},\Psi_{i}]$ with Laplace mechanism at budget
$\epsilon_{2}$

13: Set negative values to $0$ and normalize

14: Sample from $\Pr^{*}[X_{i},\Psi_{i}]$ and add to $D^{*}$

15: end for

16: Return $D^{*}$

Algorithm 2 PrivBayes Enhanced (PrivBayesE)

Partial marginal observation-based adaptive recourse. This approach can be
applied to algorithms that use low dimensional marginal queries (Zhang et al.,
2014; McKenna et al., 2019). Instead of discarding all the partially missing
rows, only the rows with missing cells in the queried attributes are removed.
Such a strategy is most helpful when only a subset of attributes have missing
data. For example, with MAR missing mechanism, partial marginal observation
can be learned from all the non-missing columns.

We extend PrivBayes (Zhang et al., 2014) using this strategy and call it
PrivBayes enhanced or PrivBayesE in short (Algorithm 2). Similar to PrivBayes,
a Bayesian network is learned to know the correlated columns (Lines 1-8), and
each time a marginal query is asked, PrivBayesE learns from all non-missing
information of the attribute/(s) (Lines 9-15). The improvement as compared to
the complete row only approach is because the missing rows are discarded on a
smaller set of attributes rather than from the whole dataset. This is
especially beneficial for the missing completely at random (MCAR) where
looking at more data helps better estimate the true distribution of the
marginals and the missing at random (MAR) scenario where some marginals are
completely available and the distribution over such attributes can be
estimated as learning on complete data. The privacy analysis of PrivBayesE is
also similar to PrivBayes as the same marginals are computed in both
algorithms and no additional queries are asked to the dataset.

Column-wise data generation-based adaptive recourse. This approach can be
applied to any algorithm that uses column-wise intermediate models to learn
the data distribution. In such algorithms, a sequence of attributes is
decided, and starting with the second attribute in sequence, a model is
learned to predict the current attribute using previously learned ones. We
show that such an algorithmic architecture can impute values as the learning
proceeds. Each time a model is trained to predict the next attribute, the same
model can be used to impute missing values. No additional privacy costs are
involved in such an algorithm because only the existing models are used for
imputation. This strategy is most appropriate for learning missing data when
the missing data correlates with other attributes in the dataset (e.g., MAR).

0: Incomplete dataset $D$, Attributes $\mathcal{A}$, Constraints $\Psi$,
Privacy budget $\epsilon_{1},\epsilon_{2}$

1: Build sequence $S$ of attributes $\mathcal{A}$ using constraints $\Psi$

2: Initialize synthetic dataset $D^{*}$

3: Compute distribution of first attribute $H=\Pr[S_{1}]$ using all non-
missing values

4: Generate DP $H^{*}$ by adding Gaussian noise of budget $\epsilon_{1}$

5: Sample from $H^{*}$ to populate $D^{*}[S_{1}]$

6: for $i=2\dots|\mathcal{A}|$ do

7: Load training features $X=S_{:j}$, and target label $Y=S_{j}$

8: Train model $M=\theta(X,Y)$ privately with budget
$\frac{\epsilon_{2}}{|\mathcal{A}|-1}$

9: Impute missing values in dataset $D[S_{j}]$ using $M$

10: Predict synthetic values $\Omega=M(D^{*}[S_{:j}])$ and fill
$D^{*}[S_{j}]=\Omega$

11: end for

12: Return $D^{*}$

Algorithm 3 Kamino Impute (KaminoI)

We extend Kamino (Ge et al., 2021) using this strategy and call in Kamino
impute or KaminoI in short (Algorithm 3). A sequence of attributes within the
additional constraints $\Psi$ is decided to start the algorithm (Line 1). The
distribution of the first attribute in Kamino’s computed sequence is learnt
using all the non-missing cells (Line 3). This computed distribution is noised
(Line 4) and values are sampled to populate the synthetic dataset (Line 5).
The other attributes are learnt in sequence using a private intermediate model
(Lines 7-8) and missing values are simultaneously imputed (Line 9). The same
intermediate model is also used to fill up the synthetic dataset (Line 10).
The improvement as compared to the complete row only approach comes from the
fact that none of the missing values are discarded and instead used to learn
the intermediate models.

##  5\. Privacy for Groundtruth Data

In this section, we shift our focus to exploring the privacy implications for
the ground truth data, which we approach as a distinct problem that closely
relates to Problem 1. We find that privacy for ground truth can be attained by
ensuring that the probability of missing values in a row is independent of the
other rows in the dataset. Furthermore, we demonstrate that certain missing
mechanisms, such as MCAR, allow a tighter privacy analysis.

###  5.1. Relationship to Problem 1

We have proposed multiple synthetic data generation algorithms $M$ which train
on the incomplete dataset $D$ and achieve $(\epsilon,\delta)$-DP as solutions
to problem 1. However, this incomplete dataset $D$ results from a missing
mechanism $M_{\phi}$ on the ground truth dataset $\bar{D}$. In problem 2, we
study the same mechanisms $M$ which train on the $D$ but discuss their privacy
impact on $\bar{D}$. We do so by combining the missing mechanism $M_{\phi}$
and the synthetic data generation process $M$ as a composite mechanism $M\circ
M_{\phi}$.

It is important to note that just because $M$ is a DP mechanism for incomplete
data $D$, it does not necessarily mean that $M\circ M_{\phi}$ is DP for the
ground truth data $\bar{D}$.

###### Example 5.1.

In Figure 4, consider neighboring ground truth data $\bar{D}$ and
$\bar{D^{\prime}}$ differ in the last row’s income value (100k v.s. 80k).
Their income columns have an MNAR missing mechanism that hides the highest
income value and their corresponding incomplete data $D$ and $D^{\prime}$ then
differ more than one row. This means that an $\epsilon$-DP mechanism for
incomplete data cannot guarantee the same level of privacy for the ground
truth data.

The example above does not provide a strong privacy guarantee for the ground
truth data because the probability of a row having missing values depends on
the values of other rows. However, we can show that if $M_{\phi}$ enforces
independent probabilities for each row to have missing values, a strong
privacy guarantee applies to the ground truth data.

###### Theorem 5.2.

Let the missing mechanism $M_{\Phi}$ have independent randomness to hide the
values of each row and $D=M_{\phi}(\bar{D})$. If $M$ achieves
$(\epsilon,\delta)$-DP for $D$, then $M\circ M_{\Phi}$ satisfies
($\bar{\epsilon},\bar{\delta}$)-DP for $\bar{D}$, where
$\bar{\epsilon}\leq\epsilon,\bar{\delta}\leq\delta$.

###### Proof.

(sketch) As $M_{\Phi}$ has independent randomness to hide values of each row,
given the ground truth data $\bar{D}$ and a possible incomplete dataset $D$,
we have $\Pr[D|\bar{D}]=\prod_{l}\Pr[D_{l}|\bar{D}]$, where $D_{l}$ refers to
the value taken by the $l$th row. Consider neighboring groundtruth datasets
$\bar{D}$ and $\bar{D}^{\prime}$ differ in the $i$th row and any possible
output $O$ of $M\circ M_{\Phi}$. Let $\mathcal{D}$ be all possible incomplete
datasets that can be outputted by $M_{\Phi}$ from $\bar{D}$ or
$\bar{D}^{\prime}$. We partition $\mathcal{D}$ into
$\\{\cdots,\mathcal{D}_{j},\cdots\\}$ such that all datasets with the same row
values except the $i$th row are in the same group $\mathcal{D}_{j}$. Hence,
for all $D\in\mathcal{D}_{j}$, they have the same probability for
$\prod_{l\neq i}\Pr_{M_{\Phi}}[D_{l}|\bar{D}]$. Now we have

$\displaystyle\Pr[O|\bar{D}]$ $\displaystyle=$
$\displaystyle\sum_{\mathcal{D}_{j}}\sum_{D\in\mathcal{D}_{j}}\Pr_{M}[O|D]\Pr_{M_{\Phi}}[D|\bar{D}]$
$\displaystyle=$
$\displaystyle\sum_{\mathcal{D}_{j}}\sum_{D\in\mathcal{D}_{j}}(\Pr_{M}[O|D]\Pr_{M_{\Phi}}[D_{i}|\bar{D}]\cdot\prod_{l\neq
i}\Pr_{M_{\Phi}}[D_{l}|\bar{D}])$ $\displaystyle=$
$\displaystyle\sum_{\mathcal{D}_{j}}(\prod_{l\neq
i}\Pr_{M_{\Phi}}[D_{l}|\bar{D}]\cdot\sum_{D\in\mathcal{D}_{j}}\Pr_{M}[O|D]\Pr_{M_{\Phi}}[D_{i}|\bar{D}])$
$\displaystyle\leq$ $\displaystyle\sum_{\mathcal{D}_{j}}(\prod_{l\neq
i}\Pr_{M_{\Phi}}[D_{l}|\bar{D}^{\prime}]\cdot\sum_{D^{\prime}\in\mathcal{D}_{j}}(e^{\epsilon}\Pr_{M}[O|D^{\prime}]+\delta)\Pr_{M_{\Phi}}[D_{i}^{\prime}|\bar{D}^{\prime}])$
$\displaystyle=$ $\displaystyle
e^{\epsilon}\sum_{\mathcal{D}_{j}}\sum_{D^{\prime}\in\mathcal{D}_{j}}\Pr_{M}[O|D^{\prime}]\Pr_{M_{\Phi}}[D^{\prime}|\bar{D}]+\delta\sum_{\mathcal{D}_{j}}\sum_{D^{\prime}\in\mathcal{D}_{j}}\Pr_{M_{\Phi}}[D^{\prime}|\bar{D}^{\prime}]$
$\displaystyle=$ $\displaystyle
e^{\epsilon}\sum_{\mathcal{D}_{j}}\sum_{D^{\prime}\in\mathcal{D}_{j}}\Pr_{M}[O|D^{\prime}]\Pr_{M_{\Phi}}[D^{\prime}|\bar{D}]+\delta$

The inequality above is based on for any neighbors $D$ and $D^{\prime}$, we
have $\Pr_{M}[O|D]\leq e^{\epsilon}\Pr_{M}[O|D^{\prime}]+\delta$ and
$\sum_{D\in\mathcal{D}_{j}}\Pr_{M_{\Phi}}[D_{i}|\bar{D}]=\sum_{D^{\prime}\in\mathcal{D}_{j}}\Pr_{M_{\Phi}}[D^{\prime}_{i}|\bar{D}^{\prime}]=1$.
∎

Theorem 5.2 says that the privacy bound for the ground truth dataset is lesser
than equal to the bound of the incomplete dataset for a synthetic data
generation algorithm if each row in the ground truth dataset has an
independent probability of having missing values. Next we illustrate how to
obtain a tighter privacy bound for the missing completely at random (MCAR)
mechanism.

Figure 4. Example of private incomplete datasets generated from two
neighbouring ground truth datasets. Gray denotes missing cells and dotted
lines represent the differing row.

###  5.2. Privacy Amplification Due To MCAR

Missing completely at random (MCAR) enforces an independent probability of
having missing rows for each attribute in the dataset. We use these
probabilities to tighten the privacy bounds for ground truth data when the
missing mechanism is MCAR. The technique we developed is inspired by the
seminal work of privacy amplification due to sampling (Balle et al., 2018).
The premise of privacy amplification by subsampling is that we run a DP
algorithm on some random subset of the data (e.g., sampled Gaussian mechanism,
DP-SGD). The subset introduces additional uncertainty, which benefits privacy.
Privacy amplification due to subsampling has been shown to work for many
sampling methods (e.g., Poisson sampling, sampling with/without replacement)
and for neighboring datasets which may differ with replacement or
substitution. Privacy amplification by subsampling theorem 5.3 makes this
intuition precise.

###### Theorem 5.3 (Sampling Amplification Theorem (Balle et al., 2018;
Steinke, 2022)).

Consider an algorithm $M:\mathcal{D}\rightarrow\mathcal{D}$ that satisfies
$(\epsilon,\delta)$-DP and a sampling mechanism $S(D)$ that samples a random
subset $U$ from dataset $D$ of $n$ samples. If $p=max_{i\in[n]}\Pr_{U}[i\in
U]$, then the composite mechanism $M(S(D))$ offers
$(\epsilon^{\prime},\delta^{\prime})$-DP where
$\epsilon^{\prime}=\log(1+p(e^{\epsilon}-1))$, $\delta^{\prime}=p\delta$. For
small values of $\epsilon$, we have
$\epsilon^{\prime}=\log(1+p(e^{\epsilon}-1))\approx p\epsilon$.

In our missing data context, we note that for synthetic data generation
algorithms that train on incomplete data, many rows are naturally discarded
due to the presence of missing cells. We exploit this natural throwing out of
rows as a sampling mechanism and show that it can be used to amplify privacy.
Recall from Section 2.1 that MCAR enforces independent probability of having
missing cells in the dataset for each attribute $\phi_{1},\cdots,\phi_{k}$. We
use these probabilities to propose our amplification results in Proposition
5.4.

###### Proposition 5.4.

Consider an MCAR mechanism $M_{\Phi}:\mathcal{D}\rightarrow\mathcal{D}$ with
missing probabilities $\\{\phi_{1},\ldots,\phi_{k}\\}$ over attributes
$\\{A_{1},\ldots A_{k}\\}$ of the input ground truth data $\bar{D}$ and
outputs an incomplete dataset $D$. If an algorithm
$M:\mathcal{D}\rightarrow\mathcal{D}$ takes in rows in $D$ which have no
missing values on attributes
$\mathcal{A}_{M}\subseteq\\{A_{1},\ldots,A_{k}\\}$, then $M\circ M_{\Phi}$
offers $(p\epsilon,p\delta)$-DP to the ground truth data $\bar{D}$ where
$p_{\mathcal{A}_{M}}=\prod_{A_{i}\in\mathcal{A}_{M}}(1-\phi_{i})$. We call
$\mathcal{A}_{M}$ an amplification attribute set for $M$ and
$p_{\mathcal{A}_{M}}$ the amplification factor of $\mathcal{A}_{M}$.

###### Proof.

A row in MCAR has $\prod_{i=1}^{i=l}(1-\phi_{i})$ probability of having no
missing values and plugging in to Theorem 5.3. ∎

We note three important facts. First, if an algorithm $M$ takes in rows with
no missing values over an attribute set $\mathcal{A}_{M}$, then $M$ also takes
in rows with no missing values over an attribute set
$\mathcal{A}^{\prime}_{M}\subset\mathcal{A}_{M}$. In other words, if
$\mathcal{A}_{M}$ is an amplification attribute set for $M$, then any subset
of $\mathcal{A}_{M}$ is an amplification attribute set for $M$ with
amplification factor greater than that of $\mathcal{A}_{M}$. Second, when
$\mathcal{A}_{M}=\emptyset$, $p_{\mathcal{A}_{M}}=1$. Third and more
importantly, as the dataset is read only once, each attribute can only be used
once as an amplification factor. We can now use Proposition 5.4 and Theorem
5.3 in conjunction to show the privacy amplifications for the different
algorithms we have discussed so far in our paper.

Use case 1: Privacy amplification for complete row only approach. Here we show
how to apply Proposition 5.4 to all complete row only approaches (PrivBayes,
Kamino, and GAN-based approaches). As these approaches take as input all
attributes, the probability of seeing a row without missing values is
$\prod_{i=1}^{i=k}(1-\phi_{i})$. The following example illustrates how this
probability can be used to obtain a tighter privacy bound for the ground truth
data.

###### Example 5.5 (MCAR amplification for complete row only approach).

Consider the incomplete dataset from Figure 4. Let’s assume that the missing
data comes from an MCAR mechanism where the missing probabilities are
$\phi_{State}=\frac{1}{4},\phi_{Occupation}=0,\phi_{Gender}=\frac{1}{4},\phi_{Income}=\frac{1}{4}$
. Given $4$ DP sub-algorithms $M_{1},M_{2},M_{3},M_{4}$ that each offer DP
guarantee to the incomplete dataset $D$ at budget $\frac{\epsilon}{4}$.
$M_{1}$ computes the marginals of the complete rows over attribute ¡State¿,
$M_{2}$ over ¡Occupation¿, $M_{3}$ over ¡Gender¿ and $M_{4}$ over ¡Gender,
Income¿. As all sub-algorithms take as input only the complete rows, using
Proposition 5.4, the amplification is $\prod_{i}(1-\phi_{i})=0.421$ and using
Theorem 5.6 the final privacy is
$\bar{\epsilon}=4*0.421\frac{\epsilon}{4}=0.421\epsilon$.

Use case 2: Privacy amplification for partial marginal observation approach.
For partial marginal observation methods (e.g. PrivBayesE), calculating the
amplification privacy cost is more complex. These methods involve multiple
low-dimensional marginals with overlapping attributes. To determine the
overall amplification for such algorithms, it is necessary to calculate the
amplification for each marginal and carefully compose them. The complexity of
this calculation arises from the optimal selection of the amplification
attribute set for each marginal, which maximizes amplification while ensuring
that each attribute is used only once. First, we consider a simple case that
the amplification factors of all marginals are disjoint. In this scenario, we
can compose the total privacy cost using Theorem 5.6 and demonstrate using
Example 5.7.

###### Theorem 5.6.

Consider an MCAR mechanism $M_{\Phi}$, and a sequence of $j$ mechanisms
$M_{1},\ldots,M_{j}$ with DP guarantees of $\epsilon_{1},\ldots,\epsilon_{j}$
to $D$ and amplification attribute set
$\mathcal{A}_{M_{1}},\ldots,\mathcal{A}_{M_{j}}$ respectively. If their
amplification attribute sets do not overlap, then these mechanisms offers DP
to the ground truth data $\bar{D}$ at a cost of
$\bar{\epsilon}=\sum_{i=1}p_{\mathcal{A}_{M_{i}}\epsilon_{i}}$.

###### Proof.

As all mechanisms $M_{i}$ work on disjoint sets of attributes, their
amplification attribute sets $\mathcal{A}_{i}$ are also disjoint. Furthermore
as the missing probabilities are always $\leq 1$, we always use all attributes
in $\mathcal{A}_{i}$ amplify marginal $M_{i}$. We can then use Theorem 5.3 to
calculate the final amplified privacy cost
$\bar{\epsilon}=\sum_{i=1}p_{\mathcal{A}_{M_{i}}\epsilon_{i}}$. ∎

###### Example 5.7.

Continuing from Example 5.5, assume we have the same dataset but use a partial
observation algorithm. We consider only the sub-algorithms $M_{1},M_{2}$, and
$M_{4}$ for this example. The marginals for these sub-algorithms do not
overlap and allow us to consider all engaging attributes as their
amplification attribute set. Hence, by Theorem 5.6, $M_{1}$ is amplified using
$p_{M_{1}}=1-\phi_{state}=\frac{3}{4}$, $M_{2}$ is amplified using
$p_{M_{2}}=1-\phi_{occupation}=1$ and $M_{4}$ using
$p_{M_{4}}=(1-\phi_{gender})(1-\phi_{income})=\frac{9}{16}$. The amplified
privacy cost would thus be
$\frac{3}{4}\frac{\epsilon}{3}+\frac{\epsilon}{3}+\frac{9}{16}\frac{\epsilon}{3}=0.77\epsilon$.

The problem however gets more nuanced when two marginals have overlapping
attributes. We show this in Example 5.8 by first showing a naïve composition
and then an optimized one.

###### Example 5.8.

Consider all $4$ sub-algorithms in Example 5.5 and a partial observation
algorithm. The marginals for sub-algorithms $M_{3}$ and $M_{4}$ overlap in the
‘Gender’ attribute with amplification factors
$p_{M_{3}}=(1-\phi_{Gender})=\frac{3}{4}$ and
$p_{M_{4}}=(1-\phi_{Gender})(1-\phi_{Income})=\frac{9}{16}$ respectively. We
cannot apply Theorem 5.6 on $M_{3}$ and $M_{4}$’s entire attribute set as the
corresponding amplification attribute sets would then overlap on the ‘Gender’
attribute. A naïve solution would be to amplify the DP mechanism with the most
amplification and skip the others. In our example, we would amplify only
$M_{4}$ with amplification of $\frac{9}{16}$ and skip amplification for
$M_{3}$. The total amplified privacy cost would thus be
$\bar{\epsilon}=\frac{3}{4}\frac{\epsilon}{4}+\frac{\epsilon}{4}+\frac{\epsilon}{4}+\frac{9}{16}\frac{\epsilon}{4}=0.83\epsilon$.
However, a better bound can be calculated if overlapping mechanisms were
grouped together and amplified using the intersecting attribute. For instance,
both $M_{3}$ and $M_{4}$ can be amplified by an amplification factor of
$\frac{3}{4}$ using the amplification attribute set ‘Gender’, resulting in a
total privacy loss of
$\frac{3}{4}\frac{\epsilon}{4}+\frac{\epsilon}{4}+\frac{3}{4}(\frac{\epsilon}{4}+\frac{\epsilon}{4})=0.81\epsilon$
i.e. tighter than $0.83\epsilon$.

In a more general setting, solving this problem requires us to make groups of
the mechanisms with overlapping attributes and make sure that each group is
amplified using distinct amplification factors.

###### Problem 3.

Consider an MCAR mechanism $M_{\Phi}$ and a sequence of $j$ mechanisms
$M_{1},\ldots,M_{j}$ with DP guarantees of $\epsilon_{1},\ldots,\epsilon_{j}$
to $D$, where $M_{i}$ computes a marginal over attributes $\mathcal{A}_{i}$.
We would like to find amplification attribute sets
$\\{\mathcal{A}_{M_{1}}\subseteq\mathcal{A}_{1},\ldots,\mathcal{A}_{M_{j}}\subseteq\mathcal{A}_{k}\\}$
and their corresponding amplification factor $p_{1},\ldots,p_{j}$ for
$M_{1},...M_{j}$, that gives the smallest DP cost to the ground truth data
$\bar{D}$.

One way to solve the above problem is by creating valid partitions of
marginals and assigning each group in the partition an amplification attribute
set such that all groups have disjoint attribute sets and all marginals from
the same group are amplified using their own amplification attribute set.

###### Definition 5.9 (Valid partition).

Given DP mechanisms $M_{1},\ldots,M_{j}$ for computing marginals over
attribute sets $\mathcal{A}_{1},\ldots,\mathcal{A}_{j}$, a partition of these
mechanisms $P=\\{G_{1},\ldots G_{i}\\}$ is considered valid if it satisfies
these conditions: (1) All mechanisms in the same partition are amplified with
the same set of amplification attribute set and with the same amplification
factors; and (2) The amplification attribute sets of all partitions are
disjoint.

The privacy cost for a valid partition is $\bar{\epsilon}=\sum_{G_{l}\in
P}p_{\mathcal{A}_{G_{l}}}\sum_{M_{j}\in G_{l}}\epsilon_{j}$, where
$\mathcal{A}_{G_{l}}$ is the amplification attribute set for the mechanisms
grouped into $G_{l}$ and $p_{\mathcal{A}_{G_{l}}}$ is the corresponding
amplification factor.

A valid partition ensures that the amplification attribute set of each group
is disjoint and hence, all attributes in the dataset are only considered once
in the amplification analysis. To solve Problem 3, we simply need to choose
the partition which is both valid and also has the least privacy cost.
Therefore, all DP sub-mechanisms are amplified using the best disjoint
amplification attribute set. However, we note that enumerating all possible
valid partitions is intractable as there are exponentially many partitions
that we can possibly make from our DP sub-mechanisms111The total number of
partitions of a set is given by the Bell number.. If the cardinality of
$\mathcal{A}$ and the number of DP mechanisms $j$ are small, then one can
enumerate all possible solutions and choose the best one. However, for
datasets with a large number of attributes, we show an initial pruning method
to trim away bad solutions using Lemma 5.10.

###### Lemma 5.10.

A valid partition $P$ solution to Problem 3 should have a non-empty
amplification attribute set for all group $G\in P$.

###### Proof.

Suppose there are a sequence of DP sub-mechanisms $M_{1},\ldots,M_{j}$ with
privacy cost of $\epsilon_{1},\ldots,\epsilon_{j}$. A valid partition $P$ over
$M_{1},\ldots,M_{j}$ consists of a group $G$ that has an empty amplification
attribute set. Then the amplification factor of group $G$ will be $p_{G}=1$
and the overall privacy cost of this partition can be calculated using
Definition 5.9.

$\displaystyle\bar{\epsilon}_{P}$ $\displaystyle=$
$\displaystyle\sum_{G_{l}\in P}p_{\mathcal{A}_{G_{l}}}\sum_{M_{j}\in
G_{l}}\epsilon_{j}$ $\displaystyle=$
$\displaystyle\sum_{G_{l}\in\\{P-G\\}}p_{\mathcal{A}_{G_{l}}}\sum_{\mathcal{A}_{j}\in
G_{l}}\epsilon_{j}+\sum_{M_{j}\in G}\epsilon_{j}$ $\displaystyle=$
$\displaystyle L+X$

, where
$L=\sum_{G_{l}\in\\{P-G\\}}p_{\mathcal{A}_{G_{l}}}\sum_{\mathcal{A}_{j}\in
G_{l}}\epsilon_{j}$ and $X=\sum_{M_{j}\in G}\epsilon_{j}$. We can always
define another valid partition $P^{\prime}$ that has the groups as $P$ but
group $G$ has amplification attribute set $A$. Therefore, the privacy cost of
partition $P^{\prime}$ can be calculated as:

$\displaystyle\bar{\epsilon}_{P^{\prime}}$ $\displaystyle=$
$\displaystyle\sum_{G_{l}\in P^{\prime}}p_{\mathcal{A}_{G_{l}}}\sum_{M_{j}\in
G_{l}}\epsilon_{j}$ $\displaystyle=$
$\displaystyle\sum_{G_{l}\in\\{P^{\prime}-G\\}}p_{\mathcal{A}_{G_{l}}}\sum_{\mathcal{A}_{j}\in
G_{l}}\epsilon_{j}+p_{A}\sum_{M_{j}\in G}\epsilon_{j}$ $\displaystyle=$
$\displaystyle L^{\prime}+p_{A}X$

, where
$L^{\prime}=\sum_{G_{l}\in\\{P^{\prime}-G\\}}p_{\mathcal{A}_{G_{l}}}\sum_{\mathcal{A}_{j}\in
G_{l}}\epsilon_{j}$. Note that as amplification attribute set $A$ is used for
$G$ in $P^{\prime}$, the privacy cost of the other groups can at most be
increased by $p_{A}$. Assuming the worst case, $L^{\prime}=p_{A}L$ and that
the privacy cost of $P$ is always higher than that of $P^{\prime}$.

$\begin{split}L+X-L^{\prime}-p_{A}X\geq 0\\\ L+X-p_{A}L-p_{A}X\geq 0\\\
L(1-p_{A})+X(1-p_{A})\geq 0\\\ (L+X)(1-p_{A})\geq 0\end{split}$

The above inequality if always true as the first term is always positive ($L$
and $X$ are privacy costs) and the $p_{A}\leq 1$ as all missing percentages
are $\leq 1$. ∎

For large datasets where we are left with multiple partitions even after
pruning, we use a brute force search as described in Algorithm 4. In Line 1,
we enumerate all possible disjoint amplification attribute sets that we can
make from $\mathcal{A}$ and store in a variable $\mathcal{P}_{\mathcal{A}}$.
Then, we loop through each possible disjoint attribute set
$P_{\mathcal{A}}\in\mathcal{P}_{\mathcal{A}}$, and calculate the cost of each
amplification attribute set $\mathcal{A}_{l}\in P_{\mathcal{A}}$ in Line 2-3
using Proposition 5.4. We initialize the cost of the partition
$c_{P_{\mathcal{A}}}=0$ in Line 4. Then we loop through each pair of marginal
$S_{i}$ and its corresponding DP mechanism ($M_{i}$, $\epsilon_{i}$) and find
the candidate amplification attribute sets that are contained in the marginal
$S_{i}$ in Line 6. If no such candidate set is valid for $S_{i}$, then we can
prune the entire partition $P_{\mathcal{A}}$ using Lemma 5.10 and loop back to
Line 2. Otherwise, in Line 7-8, we find the candidate attribute set which has
the best amplification cost for $M_{i}$ and add its corresponding cost the
final cost $c_{P_{\mathcal{A}}}$. Finally, the partition with the minimum sum
cost is returned in Line 10. In Example 5.11 we show how Algorithm 4 can be
used to find the valid partition for our running example with the lowest
privacy cost.

###### Example 5.11.

Consider the same setup in Example 5.8. There are total of 4 attributes and
Algorithm 4 starts by enumerating all 15 possible disjoint amplification
attribute sets — {State — Occupation — Gender — Income}, {State Occupation —
Gender — Income}, … , {State Occupation Gender — Income}, … , {State
Occupation Gender Income}. We then iterate through each of these disjoint
sets. Let’s consider the disjoint sets
$\mathcal{A}_{1}:\\{State\\},\mathcal{A}_{2}:\\{Occupation\\},\mathcal{A}_{3}:\\{Gender\\},\mathcal{A}_{4}:\\{Income\\}$.
For each attribute set we calculate its corresponding amplification factor,
$c_{\mathcal{A}_{1}}:(1-\phi_{State})=3/4,c_{\mathcal{A}_{2}}:(1-\phi_{Occupation})=0,c_{\mathcal{A}_{3}}:(1-\phi_{Gender})=3/4,c_{\mathcal{A}_{4}}:(1-\phi_{Income})=3/4$.
We then iterate through all marginals and choose the best amplification
attribute for each marginal. Therefore, $M_{1}$ is amplified using
$\mathcal{A}_{1}$, $M_{2}$ using $\mathcal{A}_{2}$, $M_{3}$ and $M_{4}$ both
using $\mathcal{A}_{3}$. The final privacy cost therefore is
$\bar{\epsilon}=\frac{3}{4}\frac{\epsilon}{4}+\frac{\epsilon}{4}+\frac{3}{4}\frac{\epsilon}{4}+\frac{3}{4}\frac{\epsilon}{4}=0.81\epsilon$.
This partition also happens to be the best partition among the 15 partitions.

0: Marginals $\mathcal{S}=\\{S_{1},\ldots,S_{j}\\}$ over attributes
$\mathcal{A}$, DP mechanisms
$\mathcal{M}=\\{(M_{1},\epsilon_{1}),\ldots,(M_{j},\epsilon_{j})\\}$ for
$\mathcal{S}$, Missing probabilities $\Phi=\\{\Phi_{A}|A\in\mathcal{A}\\}$ for
MCAR

1: Find all possible partitions of $\mathcal{A}$ and store in
$\mathcal{P}_{\mathcal{A}}$

2: for each attribute partition $P_{\mathcal{A}}$ in
$\mathcal{P}_{\mathcal{A}}$ do

3: Calculate amplification factor
$c_{\mathcal{A}_{l}}=\prod_{A\in\mathcal{A}_{l}}(1-\phi_{A})$ for
$\mathcal{A}_{l}\in P_{\mathcal{A}}$

4: Initialize disjoint set cost $c_{P_{\mathcal{A}}}=0$

5: for each $S_{i}\in\mathcal{S}$ with its corresponding
($(M_{i},\epsilon_{i})$) do

6: Skip $P_{\mathcal{A}}$ if $\\{\mathcal{A}_{l}\subseteq
S_{i}|\mathcal{A}_{l}\in P_{\mathcal{A}}\\}=\emptyset$

7: Find the best amplification attribute set for
$M_{i}$:$\mathcal{A}_{l*}\leftarrow argmin_{\mathcal{A}_{l}\in
P_{\mathcal{A}}\wedge\mathcal{A}_{l}\subseteq S_{i}}c_{\mathcal{A}_{l}}$

8: Add the best amplified cost
$c_{P_{\mathcal{A}}}=c_{P_{\mathcal{A}}}+\epsilon_{i}\cdot
c_{\mathcal{A}_{l*}}$

9: end for

10: end for

11: Return the attribute partition $P_{\mathcal{A}}$ with minimum cost
$c_{P_{\mathcal{A}}}$

Algorithm 4 Optimal amplified privacy cost

Use case 3: Privacy amplification for column-wise imputation algorithms.
Column wise imputation algorithms (e.g., KaminoI) learn one attribute at a
time in predefined sequence $S$ over the attributes
$\\{A_{1},\ldots,A_{k}\\}$. The first attribute in the sequence $S_{1}$ is
learnt using its observed distribution and the rest $S_{2},\ldots,S_{k}$ are
learnt using intermediate models $M_{2},\ldots,M_{k}$ with privacy costs
$\epsilon_{2},\ldots,\epsilon_{k}$. At each $i^{th}$ iteration, the $S_{i}$
attribute is learnt using the intermediate model $M_{i}$ which takes the
previously learnt attributes $S_{:i}$ as feature input and learns the target
attribute $S_{i}$. After the training is complete, $M_{i}$ is used to sample
the synthetic dataset and also to impute the incomplete values of the target
attribute $D[S_{i}]$. Thus for the next model $M_{i+1}$, the previously learnt
attributes in sequence are either complete or imputed. In other words, the
total number of complete rows fed to an intermediate model $M_{i}$ solely
depends on the number of complete values in $D[S_{i}]$. Therefore, the
amplified privacy for ground truth data for $M_{i}$ is
$\bar{\epsilon_{i}}=p_{S_{i}}\epsilon_{i}$ where $p_{S_{i}}=1-\phi_{i}$ is the
amplification factor of attribute $S_{i}$. However, we note that for training
model $M_{i}$, every attribute $S_{:i-1}$ is considered for amplification
using the same probability as $S_{i}$. As each attribute can be used once, we
can only amplify a single model and calculate the privacy for ground truth
accordingly.

###### Theorem 5.12.

Consider an MCAR mechanism $M_{\Phi}$ and a sequence of attributes $S$ and $k$
mechanisms $M_{1},\ldots,M_{k}$ with privacy cost of
$\epsilon_{1},\ldots,\epsilon_{k}$ to $D$, where $M_{i}$ is an intermediate
model that trains $A_{i}$ as target and $A_{:i}$ as features. If model $M_{i}$
is used for imputation of attribute $A_{i}$, then the overall process offers
DP to the ground truth data $\bar{D}$ at a cost of
$\bar{\epsilon}=p_{S_{j}}\epsilon_{j}+\sum_{i=1,i\neq j}^{k}\epsilon_{i}$,
where $j=\max\limits_{i=1}^{k}(1-\phi_{i})$.

###### Proof.

As all cells of an attribute are imputed at previous iterations, the number of
complete rows fed to a model at the $i$th iteration depends on the missing
cells of the $S_{i}$ attribute. The amplification for the $i$th model can
therefore be calculated at $\epsilon_{i}p_{S_{i}}$, where
$p_{S_{i}}=1-\phi_{i}$ is the amplification factor of attribute $S_{i}$. To
calculate the overall privacy of the algorithm, we would like to compose the
amplified privacy of all sub models. However, the model $M_{i}$ trains on
every attribute $S_{:i-1}$ and each attribute uses the same probability as
$S_{i}$. Furthermore as each attribute can only be used once, we can only
amplify a single model. Hence, we choose to amplify the model with the maximum
amplification $M_{j}$ where $j=\max\limits_{i=1}^{k}(1-\phi_{i})$ and the
other models are left un-amplified. ∎

###### Example 5.13.

Consider the incomplete dataset from Figure 4. Lets assume we have a column
based imputation algorithm learns this dataset. Each attribute is learnt using
the equal privacy budget $\frac{\epsilon}{4}$. The attributes ‘State’,
‘Gender’ and ‘Income’ has an amplification factor $\frac{3}{4}$ whereas the
attribute ‘State’ has a factor of $1$. Therefore, the amplified privacy budget
is
$\bar{\epsilon}=\frac{3}{4}\frac{\epsilon}{4}+3\frac{\epsilon}{4}=0.9375\epsilon$.

Discussion on MAR and MNAR. MAR and MNAR mechanisms model probabilities on
missing data conditioned upon non-missing values from other columns (MAR) or
missing values from the same column in the dataset (MNAR). As discussed in
Section 2, unfortunately, there exists no foolproof method to verify if MAR
and MNAR missing types exist in the dataset because any such method may depend
on a combination of observed variables, unobserved variables, and interactions
between them. In this paragraph, we argue that due to the conditional nature
of these missing types, it is hard to attain privacy amplification with MAR or
MNAR missing mechanisms. In particular, due to the conditional dependence on
values in the dataset, each row may have a different probability of having
missing values. If these probabilities are given or can be learned privately,
we can take their maximum value or noisy upper bound for privacy
amplification. However, these missing probabilities are usually associated
with multiple patterns and complex relationships. For example, consider the
simple example in Figure 4 where rows with the highest income value (80k) are
missing. In this example, the probability of a row having a missing value
directly depends on the probability of a row having an income of 80k, which is
the highest income value. To calculate the missing probabilities associated
with this MNAR missing type, we not only need to find the highest value in the
column but also calculate its probability of occurrence. Without any
distribution assumption, such a calculation cannot be achieved with DP (Bun et
al., 2015). We leave these amplification extensions for MAR and MNAR for
future work.

##  6\. Evaluation

(a) 1-way ($\downarrow$)

(b) 2-way ($\downarrow$)

(c) F1-score ($\uparrow$)

Figure 5. The effect of missing data on DP synthetic data generation
algorithms.

(a) Adult 1-way ($\downarrow$)

(b) Bank 1-way ($\downarrow$)

(c) BR2000 1-way ($\downarrow$)

(d) National 1-way ($\downarrow$)

(e) Adult 2-way ($\downarrow$)

(f) Bank 2-way ($\downarrow$)

(g) BR2000 2-way ($\downarrow$)

(h) National 2-way ($\downarrow$)

(i) Adult F1-score ($\uparrow$)

(j) Bank F1-score ($\uparrow$)

(k) BR2000 F1-score ($\uparrow$)

(l) National F1-score ($\uparrow$)

Figure 6. Adaptive methods vs baselines with MCAR missingness at $\epsilon=1$.
Algorithms of the same category are colored with the same shade. The adaptive
methods result in better quality synthetic data. The red line denotes the best
no missing baseline.

We thoroughly experiment with DP synthetic data generation algorithms on
missing data. First, we demonstrate how existing DP methods are affected by
varying amount of missing data. Next, we evaluate the effectiveness of our
proposed adaptive recourse methods and analyze the impact of varying missing
data percentages, missing mechanisms, and privacy budgets for each method.
Finally, we show how missingness amplifies privacy for ground truth data.

###  6.1. Experimental Setup

Table 1. Dataset Characteristics Dataset | Cardinality | #Numerical Attr | #Categorical Attr
---|---|---|---
Adult | 32561 | 5 | 10
Bank | 45211 | 3 | 14
BR2000 | 38000 | 3 | 11
National | 15012 | 6 | 14

Datasets. We run our experiments on four tabular datasets: (i) Adult dataset
(Dua and Graff, 2017), which contains information about 32561 individuals from
the 1994 US Census (ii) Bank dataset (Moro et al., 2014), which has 45211 rows
about direct marketing campaigns of a Portuguese banking institution (iii)
BR2000 (Zhang et al., 2014), which consists of 38,000 census records collected
from Brazil in the year 2000, (iv) National dataset (Task et al., 2022) from
NIST Diverse Community Excerpts which contains information about 15012
individuals US census data. Each dataset has a combination of numerical and
categorical columns which are pre-processed according to the synthetic data
generation algorithm as discussed in their respective research paper –
numerical attributes are discretized into 10 uniform bins or scaled between 0
to 1 and the categorical attributes are encoded using one-hot or ordinal
encoding.

Baselines. We study four baselines that follow different approaches and have
been published in well-known conferences with their code readily available:
PrivBayes from statistical approaches, DPCTGAN, DPAutoGAN from deep learning
techniques, and Kamino which is a mixed approach. Their utility reply upon
multiple hyperparameters, and we try our best to tune these parameters by
running grid searches. We don’t account for the privacy cost for tuning but in
practice, these parameters need to be tuned privately as well (Mohapatra et
al., 2021; Papernot and Steinke, [n.d.]). We also notice that deep learning
methods need a larger privacy budget than other methods to get sensible
results. Therefore by default, we assign PrivBayes and Kamino $\epsilon=1$,
and the GAN approaches $\epsilon=3$. The adaptive methods for these baselines
have the same budget as their non-adaptive counterparts. Furthermore,
PrivBayes works on the notion of pure DP ($\delta=0$), and the others use
approx. DP. The $\delta$ value is roughly set to one magnitude lower than that
of $1/|D|$ to the nearest exponent of 10.

Missing data. We implement a pipeline that can generate different categories
of missing data at different missing percentages, using the approach from
Muzellec et al. (Muzellec et al., 2020). MCAR missing data is generated by
masking the original dataset using a realization of a Bernoulli variable with
a fixed parameter such that there is exactly the required number of missing
values. To generate MAR data, we first use 50% of the attributes in the
dataset as features for a logistic regression model. The other attributes then
have missing values according to random weights in the logistic model. A bias
term is fitted using line search to attain the desired proportion of missing
values. The MNAR approach works similarly to MAR, with the difference that the
50% non-missing attributes are masked by an MCAR mechanism. This imposes the
logistic model to depend potentially on missing values, hence enforcing MNAR
missingness. As 50% of the columns in the MAR mechanism has complete values,
it comparatively has more complete rows in comparison to MCAR and MNAR. We run
experiments on all kinds of missing types for every dataset and go up to 30%
missing values except the national dataset, where we stop at 20% due to the
lower number of rows in the original dataset.

Metrics. We use two utility metrics for evaluation. The first metric is
$k$-way marginal distance. We calculate all $k$-sized combinations of
attributes in the dataset (Zhang et al., 2014; Ge et al., 2021), and then
report the average variational distance between the true vs the synthetic
marginals. For each $k$-sized combination set of attributes in
$A\in\mathcal{A}$, we calculate the marginal,
$h:\mathcal{D}\rightarrow\mathbb{R}^{|\mathcal{D}(A)|}$ and report the average
variational distance between as
$\max_{a\in\mathcal{D}(A)}|h(D^{\prime})[a]-h(\bar{D})[a]|$ where $D^{\prime}$
and $\bar{D}$ are the synthetic data and ground true data respectively (Zhang
et al., 2014; Ge et al., 2021). In our evaluation, we set $k=1,2$. Smaller
values of this metric show more closeness between the true and synthetic data.
Our second metric is model training. We consider 9 classification models
(LogisticRegression, AdaBoost, GradientBoost, XGBoost, RandomForest,
BernoulliNB, DecisionTree, Bagging, and MLP) to classify each attribute in the
dataset (e.g., income is more than 50k or not, the loan should be given or not
to user) using all other attributes as features. Each target attribute is
processed to be a binary attribute, and we try to balance the two classes as
much as possible. The quality of the learning task is represented by the
average of all models across all attributes. The F1 score is reported for
learning quality. Each model is trained using 70% of the synthetic data, and
the F1 score is evaluated using 30% of the true data (Ge et al., 2021). Larger
values of this metric show better performance. For all our experiments, we run
3 times and report the mean with standard deviation.

(a) Adult 1-way ($\downarrow$)

(b) Bank 1-way ($\downarrow$)

(c) BR2000 1-way ($\downarrow$)

(d) National 1-way ($\downarrow$)

(e) Adult 2-way ($\downarrow$)

(f) Bank 2-way ($\downarrow$)

(g) BR2000 2-way ($\downarrow$)

(h) National 2-way ($\downarrow$)

(i) Adult F1-score ($\uparrow$)

(j) Bank F1-score ($\uparrow$)

(k) BR2000 F1-score ($\uparrow$)

(l) National F1-score ($\uparrow$)

Figure 7. Adaptive methods vs non-adaptive methods on different missing
mechanisms. The red line denotes the no missing baseline.

###  6.2. Experimental Findings

####  6.2.1. Benchmark Existing DP Methods on Missing Data

We demonstrate the impact of missing values on DP synthetic data generation
algorithms. Figure 5 shows the performance of the baselines on the Adult
dataset with varying levels of missing completely at random (MCAR) data
(x-axis). Our results indicate that missing data up to 5% minimally affects
the quality of the synthetic data with 1-way and 2-way metrics experiencing
5-19% impact, and F1-score experiencing 1-13% impact. However, as missing data
increases, the quality of synthetic data generated by all algorithms degrades
drastically. With 20% missing data, the 1-way metric is affected by 14-190%,
the 2-way by 18-147%, and the F1-score is impacted by 6-28%. With high amounts
of missing data ($\geq 10\%)$, PrivBayes and DPCTGAN exhibit the most decrease
in utility. However, Kamino and DPAutoGAN show a consistent level of
performance even with more missing data indicating a high degree of stability
in the output. The stability of these methods can be attributed to the fact
that these methods tend to extract more information from the available data.
Kamino learns the functional dependencies of the dataset and tries to preserve
them while generating the synthetic data and DPAutoGAN trains an autoencoder
as a preprocessing step to learn the low-dimensional statistics of the data.

####  6.2.2. Evaluate Adaptive Recourse Approach

We evaluate adaptive recourse approaches at various experimental
configuarations. Varying missing percentage. In this experiment, we compare
the different synthetic data generation algorithms to their improved adaptive
methods from Section 4.2. We repeat our experiment on four different datasets
with varying amount of MCAR data at two privacy levels ($\epsilon=1,3$).

(a) Adult 1-way ($\downarrow$)

(b) Bank 1-way ($\downarrow$)

(c) BR2000 1-way ($\downarrow$)

(d) National 1-way ($\downarrow$)

(e) Adult 2-way ($\downarrow$)

(f) Bank 2-way ($\downarrow$)

(g) BR2000 2-way ($\downarrow$)

(h) National 2-way ($\downarrow$)

(i) Adult F1-score ($\uparrow$)

(j) Bank F1-score ($\uparrow$)

(k) BR2000 F1-score ($\uparrow$)

(l) National F1-score ($\uparrow$)

Figure 8. Baselines vs Adaptive methods at $\epsilon=3$. The adaptive methods
perform better than their respective baselines.

We plot the algorithms in different shades of color depending on their type.
GAN-based approaches are colored in shades of blue, statistical methods
(PrivBayes and PrivBayesE) in yellow and mixed approaches (Kamino and KaminoI)
in pink. Algorithms of the same shade of color are compared (e.g, PrivBayesE
(Orange) is compared against PrivBayes (Yellow)). The red line denotes the
best corresponding utility metric achieved by any of the baselines on the no
missing ground truth data. We observe in general that adaptive methods
(DPMisGAN, PrivBayesE and KaminoI) result in better quality synthetic data
compared to their non-adaptive counterparts (DPAutoGAN, DPCTGAN, PrivBayes,
Kamino). Across all datasets, the 1-way scores are improved by up to 68%,
2-way by up to 66% and F1-scores of up to 24%. Furthermore, we observe that
the adaptive methods often achieve the same utility as the no missing baseline
with 10% missing data (e.g. 1-way and 2-way for KaminoI and PrivBayesE on the
Adult dataset at 10% missing data). We also observe that there is no algorithm
which performs the best overall. In the $\epsilon=1$ case, we note that
PrivBayesE beats the other mechanisms in most cases. However, in the
$\epsilon=3$ case, KaminoI significantly beats PrivBayesE for the Adult and
Bank datasets. We attribute this phenomenon to the fact that higher privacy
noise affects the learning of the intermediate models in Kamino. Each
intermediate model in Kamino receives $\epsilon/k$ (where $k$ is the number of
attributes) privacy budget that leaves little room to learn in the low privacy
regime.

Varying missing mechanisms. In Figure 7, we compare adaptive vs non-adaptive
methods with different missing mechanisms. We repeat our experiment for all
$4$ datasets and at 10% missing data for all missing mechanisms. The adaptive
methods (DPMisGAN, PrivBayesE, and KaminoI) beat their non-adaptive
counterparts across all missing mechanisms. The experiment conducted here is
similar to the one (shown in Figure 2) in Section 4.1, but there are slight
differences in the results. In this experiment, we kept the missing percentage
constant, while in Section 4.1, the number of rows was constant. As missing
values are added only to half of the attributes, missing at random (MAR) has
more complete rows (the number in brackets on the x-axis labels) as compared
to the other mechanisms. It is interesting to note that if we increase the
missing percentage for MAR and plot it with same rows (MAR-SR), the algorithms
start performing poorly. Hence, we make the conclusion that the number of
complete of rows makes a more vital impact compared to the missing mechanism
itself.

Table 2. Amplified privacy for ground truth data. Dataset | MCAR missing %
---|---
| 0.1 | 0.2 | 0.3 | 0.4 | 0.5
Adult | 0.88 | 0.77 | 0.65 | 0.47 | 0.44
BR2000 | 0.83 | 0.68 | 0.55 | 0.41 | 0.31

Varying privacy budget. We show the impact of the privacy budget in Figure 9
for adaptive methods with 10% MCAR missing data on Adult. We vary the privacy
budget $\epsilon\in[0.5,1,3,5,10,\infty]$ where $\epsilon=\infty$ refers to
the non-private run. First, we note that increasing the privacy budget
improves the utility of the synthetic dataset across all algorithms. Second,
we observe that PrivBayesE performs better at smaller epsilon values
($\epsilon=1$) but KaminoI has better performance with higher epsilon
($\epsilon\geq 3$). We attribute this phenomenon to the fact that KaminoI
trains multiple intermediate models and these models generally require higher
privacy budget.

(a) 1-way ($\downarrow$)

(b) 2-way ($\downarrow$)

(c) F1-score ($\uparrow$)

Figure 9. Varying privacy budget and comparing utilities of our approaches

####  6.2.3. Amplification Due To Missingness

In this experiment, we show the amplified privacy budget for ground truth
data. We experiment with PrivBayesE that runs on the incomplete dataset with
10 - 50% MCAR missing data. For each run, we allocate a privacy budget of
$\epsilon=1$ and observe the marginals calculated by PrivBayesE. We assume a
uniform privacy budget for each marginal calculated by PrivbayesE and run
Algorithm 4 to calculate the best valid partition of these marginals. In Table
2, we plot the amplified privacy cost $\bar{\epsilon}$ based on the best
partition found by the algorithm. We repeat the experiment for two datasets –
Adult and BR2000. Our results show that the amplified privacy cost decreases
almost linearly from 0.88x to 0.44x for Adult and 0.83x to 0.31x for the
BR2000 dataset.

##  7\. Related Work

Differentially private synthetic data generation has been studied vastly in
prior literature (Bowen and Liu, 2020; Fan, 2020; Zhu et al., 2017; of
Standards and Technology, 2018). Prior works generate synthetic data via
statistical approaches which estimate low-dimensional marginal distributions
(Qardaji et al., 2014; Xiao et al., 2011), deep learning approaches (Frigerio
et al., 2019; Jordon et al., 2019), or the combination of the two (Ge et al.,
2021). However, all of these algorithms focus on the no missing data setting.
Some prior work look into the differentially private missing data setting.
Patki et al. (Patki et al., 2016) propose the synthetic data vault framework
which identifies and repairs inconsistencies in the generated synthetic data
from incomplete data. Other works focus on privately imputing missing values.
Clifton et. al. (Clifton et al., 2022) introduce imputation for missing data
using differentially private k-nearest neighbours algorithm for use cases
involving SQL queries. Das et. al. (Das et al., 2022) analyze the privacy
bounds when adding privacy to the imputation stage and analysis stage
implemented from a non-private imputation algorithm using OLS regression.
Krishnan et. al.(Krishnan et al., 2016) propose PrivateClean a general
differentially private data cleaning framework to improve downstream sum, avg
and count queries. A couple of other works also deal with private data
cleaning (Huang et al., 2018) and private missing data imputation (Jagannathan
and Wright, 2008) using $k$-anonymity and cryptographic primitives such as
secure distributed computation respectively.

##  8\. Conclusion

In conclusion, our research paper presents a comprehensive study on
differentially private synthetic data generation algorithms for private
datasets with missing values. Our proposed adaptive recourse methods
outperform classical approaches and strike a balance between privacy and
utility. We also provide techniques for calculating privacy bounds and
demonstrate the effectiveness of our methods through extensive experiments on
real-world datasets. Our findings have important implications for privacy-
preserving data sharing and analysis, and can facilitate the development of
more effective methods for generating synthetic data in various practical
applications.

## References

  * (1)
  * GDP (4 27) 2016-04-27.  Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing Directive 95/46/EC (General Data Protection Regulation).  _OJ_ (2016-04-27).
  * Abadi et al. (2016) Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep Learning with Differential Privacy. In _CCS_. ACM, 308–318.
  * Abay et al. (2018) Nazmiye Ceren Abay, Yan Zhou, Murat Kantarcioglu, Bhavani Thuraisingham, and Latanya Sweeney. 2018\.  Privacy preserving synthetic data release using deep learning. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 510–526.
  * Abowd (2018) John M. Abowd. 2018\.  The U.S. Census Bureau Adopts Differential Privacy. In _KDD_. 2867.
  * Acs et al. (2018) Gergely Acs, Luca Melis, Claude Castelluccia, and Emiliano De Cristofaro. 2018.  Differentially private mixture of generative neural networks.  _IEEE Transactions on Knowledge and Data Engineering_ 31, 6 (2018), 1109–1121.
  * Agarwal and Singh (2021) Anish Agarwal and Rahul Singh. 2021.  Causal inference with corrupted data: Measurement error, missing values, discretization, and differential privacy.  _arXiv preprint arXiv:2107.02780_ (2021).
  * Alghamdi et al. (2022) Wael Alghamdi, Shahab Asoodeh, Flavio P Calmon, Juan Felipe Gomez, Oliver Kosut, Lalitha Sankar, and Fei Wei. 2022.  The Saddle-Point Accountant for Differential Privacy.  _arXiv preprint arXiv:2208.09595_ (2022).
  * Andreou et al. (2013) Elena Andreou, Eric Ghysels, and Andros Kourtellos. 2013\.  Should macroeconomic forecasters use daily financial data and how?  _Journal of Business & Economic Statistics_ 31, 2 (2013), 240–251.
  * Andridge and Little (2010) Rebecca R Andridge and Roderick JA Little. 2010.  A review of hot deck imputation for survey non-response.  _International statistical review_ 78, 1 (2010), 40–64.
  * Arjovsky et al. (2017) Martin Arjovsky, Soumith Chintala, and Léon Bottou. 2017\.  Wasserstein generative adversarial networks. In _International conference on machine learning_. PMLR, 214–223.
  * Auxier et al. (2019) Brooke Auxier, Lee Rainie, Monica Anderson, Andrew Perrin, Madhu Kumar, and Erica Turner. 2019\.  Americans and Privacy - Concerned Confused and Feeling Lack of Control Over Their Personal Information.  _Pew Research Center_ (2019).
  * Balle et al. (2018) Borja Balle, Gilles Barthe, and Marco Gaboardi. 2018\.  Privacy amplification by subsampling: Tight analyses via couplings and divergences.  _Advances in Neural Information Processing Systems_ 31 (2018).
  * Barak et al. (2007) Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. 2007\.  Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In _PODS_. 273–282.
  * Bassily et al. (2014) Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. 2014\.  Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In _FOCS_. 464–473.
  * Bowen and Liu (2020) Claire McKay Bowen and Fang Liu. 2020.  Comparative Study of Differentially Private Data Synthesis Methods.  _Statist. Sci._ 35, 2 (May 2020), 280–307.  https://doi.org/10.1214/19-sts742
  * Bun et al. (2015) Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. 2015\.  Differentially private release and learning of threshold functions. In _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_. IEEE, 634–649.
  * Bureau (1 30) U.S. Census Bureau. Accessed on 2020-11-30.  LEHD Origin-Destination Employment Statistics (2002-2017).  https://onthemap.ces.census.gov/
  * Chanyaswad et al. (2019) Thee Chanyaswad, Changchang Liu, and Prateek Mittal. 2019\.  Ron-gauss: Enhancing utility in non-interactive private data release.  _Proceedings on Privacy Enhancing Technologies_ 2019, 1 (2019), 26–46.
  * Chawla (2019) R. Chawla. 2019\.  Deepfakes : How a pervert shook the world.  _International Journal for Advance Research and Development_ 4 (2019), 4–8.
  * Chen et al. (2020) Dingfan Chen, Tribhuvanesh Orekondy, and Mario Fritz. 2020\.  Gs-wgan: A gradient-sanitized approach for learning differentially private generators.  _Advances in Neural Information Processing Systems_ 33 (2020), 12673–12684.
  * Chen et al. (2018) Qingrong Chen, Chong Xiang, Minhui Xue, Bo Li, Nikita Borisov, Dali Kaafar, and Haojin Zhu. 2018.  Differentially Private Data Generative Models.  _CoRR_ abs/1812.02274 (2018).
  * Chen et al. (2015) Rui Chen, Qian Xiao, Yu Zhang, and Jianliang Xu. 2015\.  Differentially Private High-Dimensional Data Publication via Sampling-Based Inference. In _SIGKDD_. 129–138.
  * Clifton et al. (2022) Chris Clifton, Eric J. Hanson, Keith Merrill, and Shawn Merrill. 2022.  Differentially Private _k_ -Nearest Neighbor Missing Data Imputation.  _ACM Trans. Priv. Secur._ 25, 3 (2022), 16:1–16:23.  https://doi.org/10.1145/3507952
  * Das et al. (2022) Soumojit Das, Jorg Dreschler, Keith Merrill, and Shawn Merrill. 2022.  Imputation under Differential Privacy.  _CoRR_ abs/2206.15063 (2022).  https://doi.org/10.48550/arXiv.2206.15063
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Dwork (2006) Cynthia Dwork. 2006\.  Differential Privacy. In _ICALP_ , Vol. 4052. Springer, 1–12.
  * Dwork et al. (2006a) Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006a.  Our Data, Ourselves: Privacy Via Distributed Noise Generation. In _EUROCRYPT_ , Vol. 4004. Springer, 486–503.
  * Dwork et al. (2006b) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006b.  Calibrating Noise to Sensitivity in Private Data Analysis. In _Proceedings of the 3rd Conference on Theory of Cryptography_ _(TCC ’06)_. 265–284.
  * Dwork and Roth (2014) Cynthia Dwork and Aaron Roth. 2014.  The Algorithmic Foundations of Differential Privacy.  _Foundations and Trends in Theoretical Computer Science_ 9, 3-4 (2014), 211–407.
  * Erlingsson et al. (2014) Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014\.  RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In _CCS_. ACM, 1054–1067.
  * Fan (2020) Liyue Fan. 2020\.  A Survey of Differentially Private Generative Adversarial Networks. In _The AAAI Workshop on Privacy-Preserving Artificial Intelligence_.
  * Frigerio et al. (2019) Lorenzo Frigerio, Anderson Santana de Oliveira, Laurent Gomez, and Patrick Duverger. 2019\.  Differentially Private Generative Adversarial Networks for Time Series, Continuous, and Discrete Open Data. In _SEC_. 151–164.
  * Ge et al. (2019) Chang Ge, Xi He, Ihab F. Ilyas, and Ashwin Machanavajjhala. 2019.  APEx: Accuracy-Aware Differentially Private Data Exploration. In _SIGMOD_. 177–194.
  * Ge et al. (2021) Chang Ge, Shubhankar Mohapatra, Xi He, and Ihab F Ilyas. 2021\.  Kamino: Constraint-aware differentially private data synthesis.  _Proceedings of the VLDB Endowment_ 14, 10 (2021), 1886–1899.
  * Getz et al. (2023) Kylie Getz, Rebecca A Hubbard, and Kristin A Linn. 2023\.  Performance of Multiple Imputation Using Modern Machine Learning Methods in Electronic Health Records Data.  _Epidemiology_ (2023), 10–1097.
  * Gopi et al. (2021) Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. 2021\.  Numerical composition of differential privacy.  _Advances in Neural Information Processing Systems_ 34 (2021), 11631–11642.
  * Greenberg (2016) Andy Greenberg. 2016\.  Apple’s ‘Differential Privacy’ Is About Collecting Your Data—But Not Your Data.  _Wired_ (2016).
  * Gupta (2019) Rahul Gupta. 2019\.  Data Augmentation for Low Resource Sentiment Analysis Using Generative Adversarial Networks. In _ICASSP_. IEEE, 7380–7384.
  * Hawes (2020) Michael B. Hawes. 2020\.  Implementing Differential Privacy: Seven Lessons From the 2020 United States Census.  _Harvard Data Science Review_ (30 4 2020).  https://doi.org/10.1162/99608f92.353c6f99 https://hdsr.mitpress.mit.edu/pub/dgg03vo6.
  * Huang et al. (2018) Yu Huang, Mostafa Milani, and Fei Chiang. 2018.  PACAS: Privacy-aware, data cleaning-as-a-service. In _2018 IEEE International Conference on Big Data (Big Data)_. IEEE, 1023–1030.
  * IBM (2020) IBM. 2020.  Cost of a Data Breach Report.  (2020).
  * Jagannathan and Wright (2008) Geetha Jagannathan and Rebecca N Wright. 2008.  Privacy-preserving imputation of missing data.  _Data & Knowledge Engineering_ 65, 1 (2008), 40–56.
  * Jerez et al. (2010) José M Jerez, Ignacio Molina, Pedro J García-Laencina, Emilio Alba, Nuria Ribelles, Miguel Martín, and Leonardo Franco. 2010.  Missing data imputation using statistical and machine learning methods in a real breast cancer problem.  _Artificial intelligence in medicine_ 50, 2 (2010), 105–115.
  * Johnson et al. (2018) Noah M. Johnson, Joseph P. Near, and Dawn Song. 2018.  Towards Practical Differential Privacy for SQL Queries.  _PVLDB_ 11, 5 (2018), 526–539.
  * Jordon et al. (2019) James Jordon, Jinsung Yoon, and Mihaela van der Schaar. 2019\.  PATE-GAN: Generating Synthetic Data with Differential Privacy Guarantees. In _ICLR_.
  * Kass et al. (2003) Nancy E Kass, Marvin R Natowicz, Sara Chandros Hull, Ruth R Faden, Laura Plantinga, Lawrence O Gostin, and Julia Slutsman. 2003\.  The use of medical records in research: what do patients want?  _The Journal of Law, Medicine & Ethics_ 31, 3 (2003), 429–433.
  * Koller and Friedman (2009) Daphne Koller and Nir Friedman. 2009.  _Probabilistic Graphical Models - Principles and Techniques_.  MIT Press.
  * Kotsogiannis et al. (2019) Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. 2019.  PrivateSQL: A Differentially Private SQL Query Engine.  _PVLDB_ 12, 11 (2019), 1371–1384.
  * Krishnan et al. (2016) Sanjay Krishnan, Jiannan Wang, Michael J Franklin, Ken Goldberg, and Tim Kraska. 2016.  Privateclean: Data cleaning and differential privacy. In _Proceedings of the 2016 International Conference on Management of Data_. 937–951.
  * Lakshminarayan et al. (1996) Kamakshi Lakshminarayan, Steven A Harp, Robert P Goldman, Tariq Samad, et al. 1996\.  Imputation of Missing Data Using Machine Learning Techniques.. In _KDD_ , Vol. 96.
  * Li et al. (2015) Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. 2015.  The matrix mechanism: optimizing linear counting queries under differential privacy.  _VLDB J._ 24, 6 (2015), 757–781.
  * Li et al. (2014) Haoran Li, Li Xiong, Lifan Zhang, and Xiaoqian Jiang. 2014\.  DPSynthesizer: Differentially Private Data Synthesizer for Privacy Preserving Data Sharing.  _Proc. VLDB Endow._ 7, 13 (2014), 1677–1680.
  * Li et al. (2019) Steven Cheng-Xian Li, Bo Jiang, and Benjamin Marlin. 2019\.  Misgan: Learning from incomplete data with generative adversarial networks.  _arXiv preprint arXiv:1902.09599_ (2019).
  * Little (1988) Roderick JA Little. 1988\.  A test of missing completely at random for multivariate data with missing values.  _Journal of the American statistical Association_ 83, 404 (1988), 1198–1202.
  * Little (1994) Roderick JA Little. 1994\.  A class of pattern-mixture models for normal incomplete data.  _Biometrika_ 81, 3 (1994), 471–483.
  * Little and Rubin (2019) Roderick JA Little and Donald B Rubin. 2019.  _Statistical analysis with missing data_. Vol. 793.  John Wiley & Sons.
  * Luo et al. (2019) Yonghong Luo, Ying Zhang, Xiangrui Cai, and Xiaojie Yuan. 2019\.  E2gan: End-to-end generative adversarial network for multivariate time series imputation. In _Proceedings of the 28th international joint conference on artificial intelligence_. AAAI Press, 3094–3100.
  * McKenna et al. (2019) Ryan McKenna, Daniel Sheldon, and Gerome Miklau. 2019\.  Graphical-model based estimation and inference for differential privacy. In _ICML_ , Vol. 97. 4435–4444.
  * McSherry (2009) Frank McSherry. 2009\.  Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In _SIGMOD_ , Ugur Çetintemel, Stanley B. Zdonik, Donald Kossmann, and Nesime Tatbul (Eds.). ACM, 19–30.
  * Mironov (2017) Ilya Mironov. 2017\.  Rényi differential privacy. In _2017 IEEE 30th Computer Security Foundations Symposium (CSF)_. IEEE, 263–275.
  * Mironov et al. (2019) Ilya Mironov, Kunal Talwar, and Li Zhang. 2019.  Rényi Differential Privacy of the Sampled Gaussian Mechanism.  _CoRR_ abs/1908.10530 (2019).  arXiv:1908.10530 http://arxiv.org/abs/1908.10530
  * Mohapatra et al. (2021) Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, and Om Thakkar. 2021\.  The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection.  _arXiv preprint arXiv:2111.04906_ (2021).
  * Mohapatra et al. (2023) Shubhankar Mohapatra, Jianqiao Zong, Florian Kerschbaum, and Xi He. 2023.  Differentially Private Data Generation with Missing Data.  https://github.com/mshubhankar/DP-DataGeneration-MissingData.
  * Moro et al. (2014) Sérgio Moro, Paulo Cortez, and Paulo Rita. 2014\.  A data-driven approach to predict the success of bank telemarketing.  _Decision Support Systems_ 62 (2014), 22–31.
  * Muzellec et al. (2020) Boris Muzellec, Julie Josse, Claire Boyer, and Marco Cuturi. 2020.  Missing data imputation using optimal transport. In _International Conference on Machine Learning_. PMLR, 7130–7140.
  * Nakagawa and Freckleton (2008) Shinichi Nakagawa and Robert P Freckleton. 2008.  Missing inaction: the dangers of ignoring missing data.  _Trends in ecology & evolution_ 23, 11 (2008), 592–596.
  * Nordholt (1998) Eric Schulte Nordholt. 1998\.  Imputation: methods, simulation experiments and practical examples.  _International Statistical Review_ 66, 2 (1998), 157–180.
  * Noruzman et al. ([n.d.]) AH Noruzman, NA Ghani, and NSA Zulkifli. [n.d.].  Gretel. ai: Open-Source Artificial Intelligence Tool To Generate New Synthetic Data.  ([n. d.]).
  * of Standards and Technology (2018) National Institute of Standards and Technology. 2018.  Differential Privacy Synthetic Data Challenge.  https://www.nist.gov/ctl/pscr/open-innovation-prize-challenges/past-prize-challenges/2018-differential-privacy-synthetic
  * Papernot et al. (2018) Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. 2018.  Scalable Private Learning with PATE. In _ICLR_.
  * Papernot and Steinke ([n.d.]) Nicolas Papernot and Thomas Steinke. [n.d.].  Hyperparameter Tuning with Renyi Differential Privacy. In _International Conference on Learning Representations_.
  * Patki et al. (2016) Neha Patki, Roy Wedge, and Kalyan Veeramachaneni. 2016\.  The Synthetic Data Vault. In _2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA)_. 399–410.  https://doi.org/10.1109/DSAA.2016.49
  * Phan et al. (2016) NhatHai Phan, Yue Wang, Xintao Wu, and Dejing Dou. 2016\.  Differential privacy preservation for deep auto-encoders: an application of human behavior prediction. In _Thirtieth AAAI Conference on Artificial Intelligence_.
  * Ping et al. (2017) Haoyue Ping, Julia Stoyanovich, and Bill Howe. 2017\.  DataSynthesizer: Privacy-Preserving Synthetic Datasets. In _SSDBM_. ACM, 42:1–42:5.
  * Politou et al. (2018) Eugenia Politou, Efthimios Alepis, and Constantinos Patsakis. 2018\.  Forgetting personal data and revoking consent under the GDPR: Challenges and proposed solutions.  _Journal of cybersecurity_ 4, 1 (2018), tyy001.
  * Qardaji et al. (2014) Wahbeh H. Qardaji, Weining Yang, and Ninghui Li. 2014.  PriView: practical differentially private release of marginal contingency tables. In _SIGMOD_. 1435–1446.
  * Rubin (1976) Donald B Rubin. 1976\.  Inference and missing data.  _Biometrika_ 63, 3 (1976), 581–592.
  * Shrivastava et al. (2017) Ashish Shrivastava, Tomas Pfister, Oncel Tuzel, Joshua Susskind, Wenda Wang, and Russell Webb. 2017\.  Learning from Simulated and Unsupervised Images through Adversarial Training. In _CVPR_. IEEE Computer Society, 2242–2251.
  * Song et al. (2013) Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. 2013\.  Stochastic gradient descent with differentially private updates. In _GlobalSIP_. 245–248.
  * Steinke (2022) Thomas Steinke. 2022\.  Composition of Differential Privacy & Privacy Amplification by Subsampling.  _arXiv preprint arXiv:2210.00597_ (2022).
  * Tao et al. (2021) Yuchao Tao, Ryan McKenna, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. 2021.  Benchmarking Differentially Private Synthetic Data Generation Algorithms.  _arXiv preprint arXiv:2112.09238_ (2021).
  * Task et al. (2022) Christine Task, Karan Bhagat, Streat Damon, and Gary Howarth. 2022.  NIST Diverse Community Excerpts Data.  https://doi.org/10.18434/MDS2-2895
  * Torkzadehmahani et al. (2019) Reihaneh Torkzadehmahani, Peter Kairouz, and Benedict Paten. 2019\.  Dp-cgan: Differentially private synthetic data and label generation. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_. 0–0.
  * Torkzadehmahani et al. (2020) Reihaneh Torkzadehmahani, Peter Kairouz, and Benedict Paten. 2020\.  DP-CGAN: Differentially Private Synthetic Data and Label Generation.  _CoRR_ abs/2001.09700 (2020).
  * Van Buuren (2018) Stef Van Buuren. 2018\.  _Flexible imputation of missing data_.  CRC press.
  * Waites (2019) Christopher Waites. 2019\.  PyVacy: Towards Practical Differential Privacy for Deep Learning.  _https://github.com/ChrisWaites/pyvacy_ (2019).
  * Williams and McSherry (2010) Oliver Williams and Frank McSherry. 2010.  Probabilistic Inference and Differential Privacy. In _NIPS_. 2451–2459.
  * Xiao et al. (2011) Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. 2011\.  Differential Privacy via Wavelet Transforms.  _IEEE Trans. Knowl. Data Eng._ 23, 8 (2011), 1200–1214.
  * Xie et al. (2018) Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. 2018.  Differentially Private Generative Adversarial Network.  _CoRR_ abs/1802.06739 (2018).
  * Xu et al. (2019) Lei Xu, Maria Skoularidou, Alfredo Cuesta-Infante, and Kalyan Veeramachaneni. 2019.  Modeling tabular data using conditional gan.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Xu et al. (2020) Yungang Xu, Zhigang Zhang, Lei You, Jiajia Liu, Zhiwei Fan, and Xiaobo Zhou. 2020\.  scIGANs: single-cell RNA-seq imputation using generative adversarial networks.  _Nucleic acids research_ 48, 15 (2020), e85–e85.
  * Yoon et al. (2018) Jinsung Yoon, James Jordon, and Mihaela Schaar. 2018\.  Gain: Missing data imputation using generative adversarial nets. In _International conference on machine learning_. PMLR, 5689–5698.
  * Zhang et al. (2014) Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2014\.  PrivBayes: private data release via bayesian networks. In _SIGMOD_. 1423–1434.
  * Zhu et al. (2017) Tianqing Zhu, Gang Li, Wanlei Zhou, and Philip S. Yu. 2017\.  Differentially Private Data Publishing and Analysis: A Survey.  _IEEE Trans. Knowl. Data Eng._ 29, 8 (2017), 1619–1638.