#  DP-PQD: Privately Detecting Per-Query Gaps In
Synthetic Data Generated By Black-Box Mechanisms

Shweta Patwa  Duke University<EMAIL_ADDRESS>,  Danyu Sun  Duke
University<EMAIL_ADDRESS>,  Amir Gilad  Hebrew University
<EMAIL_ADDRESS>,  Ashwin Machanavajjhala  Duke University
<EMAIL_ADDRESS>and  Sudeepa Roy  Duke University<EMAIL_ADDRESS>
###### Abstract.

Synthetic data generation methods, and in particular, private synthetic data
generation methods, are gaining popularity as a means to make copies of
sensitive databases that can be shared widely for research and data analysis.
Some of the fundamental operations in data analysis include analyzing
aggregated statistics, e.g., count, sum, or median, on a subset of data
satisfying some conditions. When synthetic data is generated, users may be
interested in knowing if their aggregated queries generating such statistics
can be reliably answered on the synthetic data, for instance, to decide if the
synthetic data is suitable for specific tasks. However, the standard data
generation systems do not provide “per-query” quality guarantees on the
synthetic data, and the users have no way of knowing how much the aggregated
statistics on the synthetic data can be trusted. To address this problem, we
present a novel framework named DP-PQD (differentially-private per-query
decider) to detect if the query answers on the private and synthetic datasets
are within a user-specified threshold of each other while guaranteeing
differential privacy. We give a suite of private algorithms for per-query
deciders for count, sum, and median queries, analyze their properties, and
evaluate them experimentally.

##  1\. Introduction

For more than a decade, we have witnessed an abundance of data containing
private and sensitive information and a growing interest in using this data
for decision making and data analytics. Formal policies like the GDPR (GDPR, 4
27) and CCPA (CCPA, 2023) require that the privacy of the individuals whose
data is being used be maintained. Differential privacy (DP) (Dwork, 2006) is
the gold standard in offering mathematically rigorous bounds on privacy
leakage while offering utility through multiple data releases, even in the
presence of side information. Intuitively, DP guarantees that the output has a
similar distribution whether an individual’s data is used. It has been widely
adopted by many organizations (Abowd, 2018; Dwork, 2019) and leading companies
(Erlingsson et al., 2014; Ding et al., 2017; Tang et al., 2017).

Private data can be queried directly using designated DP mechanisms. However,
the accuracy of the results depends heavily on the privacy budget, especially
when multiple queries need to be answered. Furthermore, the results may be
inconsistent with each other. A prominent alternative is using differentially-
private synthetic data generators (SDGs) to produce a synthetic copy of the
private data, which can be used repeatedly to answer multiple queries without
spending additional privacy budget. Previous works have employed techniques
from game theory (Hardt et al., 2012; Gaboardi et al., 2014; Vietri et al.,
2020), probabilistic graphical models (Zhang et al., 2017; McKenna et al.,
2019; Huang et al., 2019; McKenna et al., 2021a; Cai et al., 2021), and deep
learning (Rosenblatt et al., 2020; Ge et al., 2021). On the other hand, to
generate new instances of datasets resembling properties of the given dataset,
SDGs not satisfying DP have also become very popular alternatives in
applications where it is appropriate to do so. Examples include SDGs using
generative modeling (Patki et al., 2016) and deep learning techniques (Xu et
al., 2019; Park et al., 2018). Synthetic data offers advantages such as: ($1$)
consistency in answering a large number of statistical queries, ($2$)
preservation of desired correlations within data, and ($3$) concise
representation of the private data that circumvents expending more privacy
budget to answer queries.

While SDGs (DP or not) embody a promising approach for increasing the
usability of private data, there may exist discrepancies between query results
over the private and synthetic datasets. This work in particular focuses on
analyzing aggregated statistics, e.g., count, sum, or median, on a subset of
data satisfying some conditions, which form some of the most fundamental
operations in data analysis. When synthetic data produced by a SDG is used in
data analysis, users may be interested in knowing if their aggregated queries
generating such statistics can be reliably answered on said data. However, the
standard data generation systems do not provide “per-query” quality guarantees
on the synthetic data, and the users have no way of knowing how much the
aggregated statistics on the synthetic data can be trusted. We illustrate with
an example below.

###### Example 1.1.

Let the private database $D$ be a simplified version of the Adult database
(Dua and Graff, 2017) with attributes: age, education, capital-gain, marital-
status, occupation, relationship, and sex. Let $D_{s}$ denote the synthetic
copy of $D$ from PrivBayes (Zhang et al., 2017), which is a DP SDG. Also
consider the following query $q$, where (<a>, <b>) is one of
$(0,200),(200,400),(400,600),$ $(600,800)$ or $(800,1000)$:
SELECT COUNT(*) FROM $D_{s}$
WHERE capital-gain $\geq$ <a> AND capital-gain $<$ <b>.

Figure 1. Histogram for attribute $capital$-$gain$ in $D$ (in white, private
and not visible to the user) and $D_{s}$ (in navy blue, visible to the user)
for bins given by $(0,200),(200,400),(400,600),(600,800)$ and $(800,1000)$.

Figure 1 shows the output for the aforementioned values of <a> and <b>. Bars
with height $0$ are not shown here. Note that the corresponding counts from
$D$ are private and we include them here only for reference.

Suppose the user wants to know if the gap between $q(D)$ and $q(D_{s})$ is
less than $\tau=200$. How can the user find out if their distance bound for
query $q$ is met without access to either the private data or the SDG that was
used to produce the synthetic data? In Figure 1, we see that when (<a>, <b>)
$=(400,600)$, the (true) answer is ‘Yes’, whereas when (<a>, <b>) $=(0,200)$,
the (true) answer is ‘No’. In fact, the distance is $114.36$ times $200$.

In this paper, we aim to build a “Differentially-Private Per-Query Decider”,
which gives a ‘Yes’ (distance bound is satisfied) answer if $|q(D)-q(D_{s})|$
is smaller than a given distance bound $\tau>0$, and a ‘No’ (distance bound is
unmet) answer otherwise, while satisfying DP with a given privacy budget
$\epsilon>0$. However, there are several challenges that one needs to address.
First, we assume that we do not have access to the mechanism behind the SDG
producing $D_{s}$. All the per-query decider can see is the synthetic data
$D_{s}$ generated by the SDG. This SDG may be one of the SDGs satisfying DP
while outputting $D_{s}$ using a separate privacy budget (Hardt et al., 2012;
Gaboardi et al., 2014; Vietri et al., 2020; Zhang et al., 2017; McKenna et
al., 2019; Huang et al., 2019; McKenna et al., 2021a; Cai et al., 2021;
Rosenblatt et al., 2020; Ge et al., 2021), or a SDG that does not use DP
(Patki et al., 2016; Xu et al., 2019; Park et al., 2018). The per-query
decider should work with $D_{s}$ generated by any SDG. Second, not only can
the per-query decider not output the true ‘Yes’ or ‘No’ answers since $q(D)$
is private, but also it cannot give a deterministic answer because DP
mechanisms must be randomized algorithms. Third, the per-query decider should
have good accuracy – answering a random ‘Yes’/‘No’ answer is trivially private
but is not useful to the user. Finally, we aim to build a framework of per-
query decider that can handle different types of standard aggregates, namely
COUNT, MEDIAN, and SUM, which have different sensitivities on the input
(private) data and will need different techniques.

### Our Contributions

In this work, we propose a novel framework called Differentially-Private Per-
Query Decider (DP-PQD) to decide if the distance between $q(D)$ and $q(D_{s})$
is less than a user-provided distance bound of $\tau>0$ for a given query $q$
and privacy budget $\epsilon>0$. We investigate the problem for COUNT, SUM,
and MEDIAN queries under this framework (with optional predicates selecting a
subset of the data), which are three fundamental aggregate operators used in
data analysis. We make the following contributions.

#####  (1) The DP-PQD framework (Section 3):

We formally define the differentially-private per-query decider and introduce
the notion of effectiveness of an algorithm to capture the range of input
distance thresholds for which a per-query decider algorithm is expected to
perform well.

#####  (2) COUNT queries (Section 4):

For COUNT queries, we present and analyze two approaches, one based on the
Laplace Mechanism (LM) (Dwork et al., 2006b) that uses a DP noisy estimate of
$q(D)$ to compare with $q(D_{s})$, and the other is direct approach for
answering ‘Yes’ or ‘No’ based on the Exponential Mechanism (EM) (McSherry and
Talwar, 2007) using a carefully designed score function.

#####  (3) SUM queries (Section 5):

For SUM queries, we present and analyze three approaches. Two of them based on
the Laplace Mechanism (LM) (Dwork et al., 2006b) and the recent Race-to-the-
Top Mechanism (R2T) (Dong et al., 2022) use a DP noisy estimate of $q(D)$ to
compare with $q(D_{s})$. The third direct approach exploits the Sparse Vector
Technique (SVT) (Lyu et al., 2017) originally designed to detect when the
first of a sequence of queries exceeds a given threshold to implement a per-
query decider.

#####  (4) MEDIAN queries (Section 6):

For MEDIAN queries, we present and analyze two approaches: one uses a DP noisy
estimate of the median query using EM, and the other is a new histogram-based
DP mechanism that directly solves the problem using the LM.

##### (5) Experimental evaluation (Section 7):

We have implemented the DP-PQD framework with all the above algorithms to
evaluate our proposed solutions. We analyze the accuracy for  $22$ COUNT
queries (with a range of tuple selectivity),  $19$ SUM queries (with a range
of tuple selectivity and varying downward local sensitivities), and  $19$
MEDIAN queries (with different data distribution around the true median). One
of the interesting observations is that the error of a DP per-query decider is
not always monotonic in the privacy budget $\epsilon$, and we explain why this
happens.

##  2\. Preliminaries

In this section, we review some background concepts and present notations used
in the rest of the paper.

###  2.1. Data and Queries

We are given a private database instance $D$ that comprises a single relation
with attributes $A_{1},\ldots,A_{d}$. The domain of attribute $A_{i}$ is given
by $dom(A_{i})$, which is categorical or integral.

In this paper, we consider three aggregate operators: COUNT, SUM, and MEDIAN,
i.e., the corresponding aggregate queries in SQL with an optional WHERE clause
take the following form:

  * •

SELECT COUNT(*) FROM $D$ WHERE $\varphi$,

  * •

SELECT SUM($A_{i}$) FROM $D$ WHERE $\varphi$, and

  * •

SELECT MEDIAN($A_{i}$) FROM $D$ WHERE $\varphi$.

In these queries, first the predicate $\varphi$ (if the WHERE clause exists)
is applied over all tuples in $D$, and then the aggregate is computed on
tuples that satisfy $\varphi$. These queries output single real output value
and belong to the class of scalar queries.

###### Example 2.1.

Recall the private database $D$ and its synthetic copy $D_{s}$ from Example
1.1. Consider the following queries:

  * •

$q_{1}$: SELECT COUNT(*) FROM $D_{s}$ WHERE $age>30$ AND $education$ LIKE
’Masters’.

  * •

$q_{2}$: SELECT SUM($capital$-$gain$) FROM $D_{s}$ WHERE $education$ LIKE
’$12$th’.

  * •

$q_{3}$: SELECT MEDIAN($capital$-$gain$) FROM $D_{s}$.

Query $q_{1}$ asks for the number of people with age above $30$ and Master’s
degree, $q_{2}$ asks for the total capital-gain of people with $12$-th grade
education, and $q_{3}$ asks for the median of capital-gain over all people.

###  2.2. Differential Privacy

We use Differential Privacy (DP) (Dwork, 2006) as the measure of privacy. We
say that two databases $D$ and $D^{\prime}$ are neighbors if they differ by a
single tuple. This is denoted by $D\approx D^{\prime}$.

###### Definition 2.2 (Differential Privacy (Dwork and Roth, 2014)).

A randomized mechanism $\mathcal{M}$ is said to satisfy $\epsilon$-DP if
$~{}\forall S\subseteq Range(\mathcal{M})$ and $\forall D,D^{\prime}$ pair of
neighboring databases, i.e., $D\approx D^{\prime}$,

$Pr[\mathcal{M}(D)\in S]\leq e^{\epsilon}Pr[\mathcal{M}(D^{\prime})\in S]$

Smaller $\epsilon$ gives stronger privacy guarantee.

###### Definition 2.3 (Global Sensitivity).

For a scalar query $q$, its global sensitivity is given by $\Delta
q=\max\limits_{D\approx D^{\prime}}|q(D)-q(D^{\prime})|$.

###### Definition 2.4 (Downward Local Sensitivity).

For a scalar query $q$, its downward local sensitivity on database $D$ is
given by

$\displaystyle DS_{q,D}=\max\limits_{D^{\prime}\approx D,D^{\prime}\subseteq
D}|q(D)-q(D^{\prime})|$

###### Example 2.5.

Consider the private database $D$ and sum query $q_{2}$ from Example
2.1.Suppose $dom(capital$-$gain)$ is $\\{0,1,\ldots,$ $99999\\}$, so $\Delta
q_{2}=99999$ since the maximum change in the sum over all pairs of neighboring
databases is the maximum value in the domain. On the other hand, given a
database $D$, $DS_{q,D}$ equals the largest value in $capital$-$gain$ from
tuples in $D$ with $education$ equal to $12$-th.

Properties like composition (Dwork, 2006) and post-processing (Dwork et al.,
2006a) give a modular way to build complex DP mechanisms:

###### Proposition 2.6.

(Dwork, 2006; Dwork et al., 2006a) give the following:

  1. (1)

(Sequential composition) If $\mathcal{M}_{i}$ satisfies $\epsilon_{i}$-DP,
then the sequential application of $\mathcal{M}_{1}$,
$\mathcal{M}_{2},\cdots$, satisfies $\sum_{i}\epsilon_{i}$-DP.

  2. (2)

(Parallel composition) If each $\mathcal{M}_{i}$ accesses disjoint sets of
tuples, then they together satisfy $\max_{i}\epsilon_{i}$-DP.

  3. (3)

(Post-processing) Any function applied to the output of an $\epsilon$-DP
mechanism $\mathcal{M}$ also satisfies $\epsilon$-DP.

Laplace mechanism (LM). The Laplace mechanism (Dwork et al., 2006b) is a
common building block in DP mechanisms and is used to get a noisy estimate for
scalar queries with numeric answers. The noise injected is calibrated to the
global sensitivity of the query.

###### Definition 2.7 (Laplace Mechanism).

Given a database $D$, scalar query $q$ (with output in $\mathbb{R}$), and
privacy budget $\epsilon$, the Laplace mechanism $\mathcal{M}_{L}$ returns
$q(D)+\nu_{q}$, where $\nu_{q}\sim Lap(\Delta q/\epsilon)$.

Its accuracy is given by the following theorem (Dwork and Roth, 2014).

###### Theorem 2.8 (Accuracy of Laplace Mechanism (Dwork and Roth, 2014)).

Given a database $D$ and scalar query $q$ (with output in $\mathbb{R})$. Let
$y$ be the output from running the Laplace Mechanism $\mathcal{M}_{L}$ on $D$
and $q$ with privacy budget $\epsilon$. Then, $\forall\delta\in(0,1]$,

$\displaystyle Pr\left[|q(D)-y|\geq\frac{\Delta
q}{\epsilon}\ln{\frac{1}{\delta}}\right]\leq\delta$

###### Example 2.9.

Consider the private database $D$ and query $q_{1}$ from Example 2.1. $\Delta
q_{1}$ equals $1$ because the count can change by at most one on neighboring
databases. Say the output of $q_{1}$ on $D$ is $n_{1}$, a private quantity,
and we want a DP estimate, $\tilde{n}_{1}$, for it. $\mathcal{M}_{L}$ returns
$n_{1}$ plus noise sampled from $Lap(1/\epsilon)$. Also,
$Pr\left[|n_{1}-\tilde{n}_{1}|\geq\frac{1}{\epsilon}\ln{\frac{1}{\delta}}\right]\leq\delta$.

Exponential mechanism (EM). For categorical outputs, the Exponential mechanism
(McSherry and Talwar, 2007) is used with an appropriate score function that
gives the utility of each element in the output space with respect to the
given private database $D$. The likelihood of an element being returned as the
output depends on its score.

###### Definition 2.10 (Exponential Mechanism).

Given a database $D$, range of outputs $\mathcal{R}$, real-valued score
function $u(D,e)$ that gives the utility of $e\in\mathcal{R}$ with respect to
$D$, and privacy budget $\epsilon$, the Exponential mechanism
$\mathcal{M}_{E}$ returns $e\in\mathcal{R}$ with probability $c\cdot
e^{\frac{\epsilon u(D,e)}{2\Delta u}}$, where $c$ is a positive constant and
$\Delta u$ is the global sensitivity of $u$.

###### Example 2.11.

Recall the private database $D$ and query $q_{3}$ from Example 2.1. We find a
DP estimate for the median (Cormode et al., 2011) by applying
$\mathcal{M}_{E}$ with $u(D,e)=-|rank(e)-n/2|$, for $e\in
dom(capital$-$gain)$. $\Delta u$ is $1$, and therefore, $\mathcal{M}_{E}$
returns $e$ with probability $\propto e^{\epsilon u(D,e)/2}$.

###  2.3. Synthetic Data Generators

We treat the synthetic data generator (SDG) used to produce $D_{s}$ as a black
box. Our framework DP-PQD can be used in conjunction with any synthetic data
generator: a standard SDG (not satisfying DP) like (Patki et al., 2016; Xu et
al., 2019; Park et al., 2018) that typically takes $D$ and some optional
constraints as inputs, or an SDG satisfying DP (SDGDP) that takes $D$ and a
privacy budget as input. An SDGDP may or may not take a set of queries as
input. For example, PrivBayes (Zhang et al., 2017) does not take queries as
input but works such as (Hardt et al., 2012; Gaboardi et al., 2014; Vietri et
al., 2020; Huang et al., 2019; McKenna et al., 2021a, 2019, 2018) do. For an
SDGDP, we assume that it has a privacy budget separate from the privacy budget
$\epsilon$ for the per-query decider DP-PQD. DP-PQD takes as input the
synthetic data $D_{s}$ generated from any SDG, the private database $D$ and a
privacy budget $\epsilon$, does not need to run the SDG again, and does not
assume anything about how the SDG works.

##  3\. The DP-PQD Framework

In this section, we present the DP-PQD (Differentially-Private Per-Query
Decider) framework that intends to solve the following problem; the workflow
of DP-PQD is given in Figure 2.

###### Definition 3.1 (Differentially-Private Per-Query Decider).

Given a private database $D$, synthetic database $D_{s}$ for $D$ from a black-
box SDG, query $q$ (COUNT, SUM or MEDIAN), distance bound
$\tau>0\in\mathbb{R}$, and privacy budget $\epsilon>0$, return whether
$|q(D)-q(D_{s})|<\tau$ while satisfying $\epsilon$-DP. We call such a
mechanism a differentially-private per-query decider, or simply a per-query
decider, and denote it by $\mathcal{A}(D,D_{s},q,\tau,\epsilon)$, or
$\mathcal{A}(D)$ when $D_{s},q,\tau$, and $\epsilon$ are clear from context.

To simplify notation, we will write $o$ to denote the outcome of
$\mathcal{A}(D)$ when $\mathcal{A},D,D_{s},q,\tau,\epsilon$ are clear from
context. Here,

$\displaystyle o=1$ $\displaystyle\equiv$ “Distance bound satisfied”
$\displaystyle o=0$ $\displaystyle\equiv$ “Distance bound unmet”

Figure 2. Workflow of DP-PQD

In this paper, we investigate the following approaches for $\mathcal{A}(D)$:
($1$) spend $\epsilon$ to obtain a noisy DP estimate for $q(D)$, and compare
it with $q(D_{s})$ to check if the distance bound of $\tau$ is met (by
instantiating Algorithm 1 with a suitable DP mechanism
$\textnormal{{DPNoisy}}(\cdot)$), and ($2$) design specialized algorithms to
solve the problem without first estimating $q(D)$. A summary of our solutions
is given in Table 4.

For convenience, we denote the desired interval for $q(D)$ as
$\mathcal{I}:=(l,r)$ (known to the user), and the absolute difference in query
values of $q(D)$ and $q(D_{s})$ as $d_{q}$ (hidden from the user), i.e.,

(1) $\displaystyle\mathcal{I}$
$\displaystyle:=(l,r)=(q(D_{s})-\tau,q(D_{s})+\tau)$ (2) $\displaystyle d_{q}$
$\displaystyle:=|q(D)-q(D_{s})|$

Since $q(D_{s})$ is known to the user, but $q(D)$ is not, we envision the user
choosing $\tau$ as a percentage value of $q(D_{s})$ in practical applications.
Here, $\mathcal{I}=(l,r)=(q(D_{s})\cdot(1-\tau),q(D_{s})\cdot(1+\tau))$. The
$\tau$ value depends on how much error in $q(D_{s})$ can be tolerated by the
application using $q(D_{s})$. For example, $\tau$ larger than $10\%$ of
$q(D_{s})$ may introduce too much error in the downstream analysis. To present
our techniques in Sections 4, 5, and 6 for a given query, we use $\tau$ as a
constant, whereas in the experiments in Section 7 when we vary the queries, we
use and vary $\tau$ as a percentage of $q(D_{s})$ since the same value of
$\tau$ may not be meaningful to all queries.

$\mathcal{A}$ satisfies $\epsilon$-DP and like any randomized mechanism,
incurs error in deciding if the distance bound is met (i.e. if $d_{q}<\tau$).
We quantify error as the expectation of the event that $\mathcal{A}$ returns
the wrong outcome on $D$ defined as follows:

###### Definition 3.2 (Error).

Let $\mathcal{A}$ be a per-query decider for the given private database $D$,
synthetic database $D_{s}$, query $q$, distance bound $\tau$, and privacy
budget $\epsilon$. Then the error of $\mathcal{A}$ is given by:

$\displaystyle err_{\mathcal{A}}(q,D,D_{s},\tau,\epsilon)$
$\displaystyle=Pr[o=1\land d_{q}\geq\tau]+Pr[o=0\land d_{q}<\tau]$

where the probability is over the randomness in $\mathcal{A}$.

In Definition 3.2, the first term corresponds to the false positive rate and
the second term corresponds to the false negative rate. Intuitively, we expect
larger error when $d_{q}$ and $\tau$ are closer because the chance of the
random noise injected by $\mathcal{A}$ causing the wrong outcome becomes
higher.

###### Example 3.3.

Consider $D,D_{s},q$ from Example 1.1 where $(0,200)$ is used as the range.
Given that $\tau=200$. Here, $d_{q}$ (hidden from the user) equals $22,872$
and is greater than $\tau$, so the correct outcome of $\mathcal{A}$ is $o=0$.
Hence, a solution $\mathcal{A}$ makes a mistake if $o=1$ and the error equals
the probability that $\mathcal{A}$ returns $o=1$.

Next, we introduce a notion we call the effectiveness of a per-query decider
$\mathcal{A}$. The idea is to derive a lower bound for $\tau$ such that
$\mathcal{A}$ returns the correct outcome with probability at least $1-\delta$
(for $0<\delta<1$) in two cases: ($1$) $q(D)=q(D_{s})$, and ($2$) $q(D)\leq
q(D_{s})-2\tau$ or $q(D)\geq q(D_{s})+2\tau$. The first condition ensures that
$\mathcal{A}$ has high accuracy when the two query outputs match, and the
second condition ensures that $\mathcal{A}$ has high accuracy also for very
different query outputs. In the absence of the first case, an $\mathcal{A}$
that always returns $o=0$ meets the condition, and in the absence of the
second case, an $\mathcal{A}$ that always returns $o=1$ meets the condition,
but neither is a useful solution. We denote the lower bound by
$\tau_{min}^{\mathcal{A},\delta}$ and call it the effectiveness threshold of
$\mathcal{A}$ at $\delta$.

###### Definition 3.4 (Effectiveness).

Let $\mathcal{A}$ be a per-query decider for a given private database $D$, a
synthetic database $D_{s}$, a query $q$, a distance bound $\tau$, and a
privacy budget $\epsilon$. $\mathcal{A}$ is called effective at error
probability $0<\delta<1$ if the following two conditions hold:

  1. (1)

if $q(D)=q(D_{s}),Pr[o=1]\geq 1-\delta$, and

  2. (2)

if $q(D)\not\in(q(D_{s})-2\tau,q(D_{s})+2\tau),Pr[o=0]\geq 1-\delta$.

The smallest value of $\tau$ that achieves the above is called the
effectiveness threshold of $\mathcal{A}$ at $\delta$ and is denoted by
$\tau_{min}^{\mathcal{A},\delta}$.

We give an upper bound on the effectiveness thresholds of each solution for
COUNT and SUM queries (Section 4 and 5). We use effectiveness as proxy for
error for queries with high sensitivities, like SUM queries. For MEDIAN
queries, $q(D)$ shows up in the rank space in the analysis. This is an
interesting direction for future work. Table 1 summarizes the notations used
throughout the paper.

Notation | Description
---|---
$D,D_{s}$ | Private database and its synthetic copy
$q$ |  COUNT, SUM, or MEDIAN query
$\Delta q$ |  Global sensitivity of query $q$
$DS_{q,D}$ |  Downward local sensitivity of $q$ on $D$ (Sec. 5)
$\tau$ |  Given upper bound on $|q(D)-q(D_{s})|$
$\epsilon$ | Privacy budget
$\mathcal{I}=(l,r)$ | $(q(D_{s})-\tau,q(D_{s})+\tau)$
$\mathcal{A}(D,D_{s},q,\tau,\epsilon)$ |  $\epsilon$-DP per-query decider
$o\in\\{0,1\\}$ |  $\mathcal{A}$’s outcome on the given problem
$\tau_{min}^{\mathcal{A},\delta}$ |  Effectiveness threshold of $\mathcal{A}$ for $0<\delta\ll 1$
$GS_{q}$ |  Upper limit on $\Delta q$ for SUM query $q$ (Sec. 5)
Table 1. Table of Notations

##  4\. Solutions for COUNT query

We propose two approaches for COUNT query $q$: ($1$) $LM_{count}$ (that
instantiates Algorithm 1 with the Laplace Mechanism (LM)) in Section 4.1, and
($2$) $EM_{count}$ (that directly solves the problem using the Exponential
Mechanism (EM)) in Section 4.2, and analyze their errors. We also derive upper
bounds for their respective effectiveness thresholds.  We give an error
comparison in Section 4.2.

Input : $q$ \- count/sum/median query, $D$ \- private database, $D_{s}$ \-
synthetic database, $\tau$ \- distance bound, $\epsilon$ \- privacy budget,
DPNoisy \- any $\epsilon$-DP mechanism to get a noisy estimate for $q(D)$,
$\phi$ \- any additional parameter(s) that DPNoisy takes.

/* If DPNoisy = LM (Defn. 2.7), then $\phi=\emptyset$

If DPNoisy = EM (Defn. 2.10), then $\phi=\\{\mathcal{R},u\\}$

If DPNoisy = R2T (Sec. 5.2), then $\phi=\\{GS_{q},\beta\\}$ */

Output : $o=1$ if the desired distance bound from $q(D_{s})$ is satisfied for
$q(D)$, else $o=0$.

1

2 Function
_GenericDecider(_$q,D,D_{s},\tau,\epsilon,\textnormal{{DPNoisy}},\phi$_)_:

3 if  _$-\tau <\textnormal{{DPNoisy}}(D,q,\epsilon,\phi)-q(D_{s})<\tau$_ then

4 return $o=1$ (“Distance bound satisfied”);

5

6 return $o=0$ (“Distance bound unmet”);

7

Algorithm 1 Basic approach using DP estimate of $q(D)$

###  4.1. Laplace Mechanism-Based Approach

In our first algorithm, $LM_{count}$, we use the LM (Definition 2.7) to obtain
a DP estimate for $q(D)$ and check if the noisy answer is less than $\tau$
away from $q(D_{s})$. This is achieved by running GenericDecider (Algorithm 1)
with the LM that adds noise from $Lap(\frac{1}{\epsilon})$ as DPNoisy (since
$\Delta q$ = 1 for COUNT queries). Since we post-process a DP estimate
(Proposition 2.6), the following holds:

###### Observation 4.1.

$LM_{count}$ satisfies $\epsilon$-DP.

We denote the noise injected by the LM (Definition 2.7) as $\nu_{q}$ and
analyze $LM_{count}$’s error next. We will frequently use the following
properties of the Laplace distribution (with mean $0$) (Dwork and Roth, 2014).
For a Laplace random variable $\nu_{q}\sim Lap(\frac{1}{\epsilon})$ and for
$t\geq 0$,

(3) $\displaystyle Pr\left[\nu_{q}\geq t\cdot\frac{1}{\epsilon}\right]$
$\displaystyle=$ $\displaystyle\frac{1}{2}e^{-t}$ (4) $\displaystyle
Pr\left[\nu_{q}\leq-t\cdot\frac{1}{\epsilon}\right]$ $\displaystyle=$
$\displaystyle\frac{1}{2}e^{-t}$ (5) $\displaystyle Pr\left[|\nu_{q}|\geq
t\cdot\frac{1}{\epsilon}\right]$ $\displaystyle=$ $\displaystyle e^{-t}$

We next employ these equations to bound the error of $LM_{count}$. We give the
full proof of Proposition 4.2 in Appendix A.1.

###### Proposition 4.2.

Given a private database $D$, synthetic database $D_{s}$, COUNT query $q$,
distance bound $\tau$, and privacy budget $\epsilon$. Interval
$\mathcal{I}=(l,r)=(q(D_{s})-\tau,q(D_{s})+\tau)$ (1). $LM_{count}$ satisfies
the following:

  1. (1)

If $q(D)\leq l$ but $o=1$, then
$err(\cdot)\leq\frac{1}{2}e^{-(l-q(D))\epsilon}-\frac{1}{2}e^{-(r-q(D))\epsilon}$.

  2. (2)

If $q(D)\geq r$ but $o=1$, then
$err(\cdot)\leq\frac{1}{2}e^{-(q(D)-r)\epsilon}-\frac{1}{2}e^{-(q(D)-l)\epsilon}$.

  3. (3)

If $l<q(D)<r$ but $o=0$, then
$err(\cdot)=\frac{1}{2}e^{-(q(D)-l)\epsilon}+\frac{1}{2}e^{-(r-q(D))\epsilon}$.

We now give an upper bound for the effectiveness threshold.

###### Proposition 4.3.

Given a private database $D$, synthetic database $D_{s}$, COUNT query $q$,
privacy budget $\epsilon$, and error probability $0<\delta<1$, the
effectiveness threshold of the per-query decider $LM_{count}$ at $\delta$
(Definition 3.4) has the following upper bound:
$\tau_{min}^{LM_{count},\delta}\leq\frac{1}{\epsilon}\ln{\frac{1}{2\delta}}$.

We give the full proof of Proposition 4.3 in Appendix A.2.

###  4.2. A Direct Solution Using the EM

In our second algorithm, $EM_{count}$, instead of plugging in a DP estimate
for $q(D)$ to reach a decision about the distance bound, directly returns
whether $o=1$ (“Distance bound satisfied”) or not.

####  4.2.1. A straightforward EM-based per-query decider.

We begin by describing a straightforward approach we call $EM_{count}^{naive}$
that directly instantiates the EM (Definition 2.10) with the output range
$\mathcal{R}=\\{0,1\\}$ and the score function $u(D,D_{s},q,\tau,o)$ given by:

$\displaystyle\footnotesize\text{If
$q(D)\in\mathcal{I}$}\left\\{\begin{array}[]{lr}u(D,D_{s},q,\tau,o=0)=0\\\
u(D,D_{s},q,\tau,o=1)=1\end{array}\right.$ $\displaystyle\footnotesize\text{If
$q(D)\not\in\mathcal{I}$}\left\\{\begin{array}[]{lr}u(D,D_{s},q,\tau,o=0)=1\\\
u(D,D_{s},q,\tau,o=1)=0\end{array}\right.$

where $\mathcal{I}=(l,r)=(q(D_{s})-\tau,q(D_{s})+\tau)$ (from (1)).
Intuitively, $u(\cdot)$ gives a non-zero score only to the correct outcome.

We give the full proof of Proposition 4.4 in Appendix A.3.

###### Proposition 4.4.

The global sensitivity of $u$ is $\Delta u=1$.

The problem with $EM_{count}^{naive}$ is that it suffers from high error as
sensitivity $1$ is too high. For instance, when $q(D)\in\mathcal{I}$ but
$o=0$, $Pr[o=0]=c\cdot e^{\epsilon\times 0/2}$ and $Pr[o=1]=c\cdot
e^{\epsilon\times 1/2}$ (Definition 2.10), where $c$ is a positive constant.
Since there are only two outcomes

(6) $\displaystyle Pr[o=0]$ $\displaystyle=\frac{1}{1+e^{\epsilon/2}}$ (7)
$\displaystyle Pr[o=1]$
$\displaystyle=\frac{e^{\epsilon/2}}{1+e^{\epsilon/2}}$

When $q(D)\in\mathcal{I}$, $o=0$ is the wrong outcome and the error is given
by (6). Similarly for $q(D)\not\in\mathcal{I}$, error equals
$1/(1+e^{\epsilon/2})$.

In contrast, $LM_{count}$ shows that lower error may be achieved. For example,
when $q(D)=q(D_{s})$ but $o=0$ (case (3) in Proposition 4.2), $LM_{count}$’s
error, $e^{-\tau\epsilon}$, is smaller than $EM_{count}^{naive}$’s error for
values of $\epsilon$ and $\tau$ such as $0.1$ and $8$, respectively. We
improve upon $EM_{count}^{naive}$ by engineering a new score function with a
smaller global sensitivity.

####  4.2.2. An improved EM-based per-query decider.

To use the EM more reliably, we propose a new score function
$u^{\prime}(D,D_{s},q,\tau,o)$:

(10) $\displaystyle\footnotesize\text{If
$q(D)\not\in(l-\tau,r+\tau)$}\left\\{\begin{array}[]{lr}u^{\prime}(D,D_{s},q,\tau,o=0)=1\\\
u^{\prime}(D,D_{s},q,\tau,o=1)=0\end{array}\right.$ (13)
$\displaystyle\footnotesize\text{If
$q(D)\in(l-\tau,q(D_{s})]$}\left\\{\begin{array}[]{lr}u^{\prime}(D,D_{s},q,\tau,o=0)=1-\frac{q(D)-(l-\tau)}{2\tau}\\\
u^{\prime}(D,D_{s},q,\tau,o=1)=\frac{q(D)-(l-\tau)}{2\tau}\end{array}\right.$
(16) $\displaystyle\footnotesize\text{If
$q(D)\in(q(D_{s}),r+\tau)$}\left\\{\begin{array}[]{lr}u^{\prime}(D,D_{s},q,\tau,o=0)=\frac{q(D)-q(D_{s})}{2\tau}\\\
u^{\prime}(D,D_{s},q,\tau,o=1)=1-\frac{q(D)-q(D_{s})}{2\tau}\end{array}\right.$

We illustrate $u^{\prime}$ in Figure 3. Note that $u^{\prime}$ outputs a value
in the range $[0,1]$ by definition, and not just in the set $\\{0,1\\}$. It
allows for a more gradual transition between scores of $0$ and $1$.

$l$$r$$\tau$$\tau$$\tau$$\tau$$0$$1$ Figure 3. Score function $u^{\prime}$ for
output $o=0$ (in cyan) and $o=1$ (in pink). Recall that $r-l=2\cdot\tau$.

We give the full proof of Proposition 4.5 in Appendix A.4.

###### Proposition 4.5.

The global sensitivity of $u^{\prime}$ is $1/2\tau$.

We refer to the algorithm that directly instantiates the EM (Definition 2.10)
with $\mathcal{R}=\\{0,1\\}$ and score function $u^{\prime}$ as $EM_{count}$.
Since we post-process a DP estimate (Proposition 2.6), the following holds:

###### Observation 4.6.

$EM_{count}$ satisfies $\epsilon$-DP.

We now give an upper bound for the effectiveness threshold (proof in Appendix
A.5).

###### Proposition 4.7.

Given a private database $D$, synthetic database $D_{s}$, COUNT query $q$,
privacy budget $\epsilon$, and error probability $0<\delta<1$, the
effectiveness threshold of the per-query decider $EM_{count}$ at $\delta$
(Definition 3.4) has the following upper bound:
$\tau_{min}^{EM_{count},\delta}\leq\frac{1}{\epsilon}\ln{\frac{1-\delta}{\delta}}$.

Comparison of $LM_{count}$ and $EM_{count}$. Figure 4 depicts the error (along
the Y axis) for fixed $D_{s},q$, and $\epsilon$ but varying $q(D)$ values
(along the X axis) when $\tau=10$ (on the left) and $\tau=30$ (on the right).
We plot the error profile for $LM_{count}$ following Proposition 4.2. Note
that it gives upper bounds when $q(D)\leq l$ or $q(D)\geq r$. We plot the
error profile for $EM_{count}$ based on Definition 2.10 for the EM with score
function $u^{\prime}$ ((10) to (16)). For $\tau=10$ and $q(D)\in\mathcal{I}$,
$EM_{count}$’s error is smaller. At $q(D)=q(D_{s})$, $LM_{count}$’s error
$e^{-\epsilon\tau}$ is larger than $EM_{count}$’s error
$\frac{1}{1+e^{\epsilon\tau}}$ ($\epsilon\tau>0$).

Figure 4. Error from $LM_{count}$ (dashed) and $EM_{count}$ (solid) as $q(D)$
is varied along the X axis, where $D$ is the Adult dataset. The selection
predicate is $relationship$ LIKE ‘Unmarried’ AND $sex$ LIKE ‘Male’,
$q(D_{s})=749,\epsilon=0.1$ and $\tau=10,30$.  The vertical lines mark the
positions of $l,q(D_{s})$, and $r$, respectively.

##  5\. Solutions for SUM query

We now discuss our solutions for SUM query on attribute $A_{i}$: ($1$)
$LM_{sum}$ (that instantiates Algorithm 1 with the Laplace Mechanism (LM)) in
Section 5.1, ($2$) $R2T_{sum}$ (that instantiates Algorithm 1 with the Race-
to-the-Top (R2T) mechanism (Dong et al., 2022)) in Section 5.2, and ($3$)
$SVT_{sum}$ (that directly solves the problem using the Sparse Vector
Technique (SVT) (Lyu et al., 2017)) in Section 5.3. We derive upper bounds for
their effectiveness thresholds and then compare them.

Consider the SUM query $q:$ SELECT SUM($A_{i}$) FROM $D$ WHERE $\varphi$,
where $\varphi$ denotes the predicate in the WHERE clause and is empty. Its
global sensitivity $\Delta q$ equals $\max dom(A_{i})$ and is unbounded if the
domain is unbounded. As done in previous work (Amin et al., 2019; Thakkar et
al., 2019; Huang et al., 2021; Dong et al., 2022), we assume a bound of
$GS_{q}$ on $\Delta q$ and use it in the per-query deciders. Thus, we use
$GS_{q}$ as the global sensitivity in the analysis.

###  5.1. Laplace Mechanism-based Approach

Our algorithm $LM_{sum}$ works similarly to $LM_{count}$. The only difference
is that the scale of the Laplace distribution for noise $\nu_{q}$ is now
$GS_{q}/\epsilon$ instead of $1/\epsilon$. $LM_{sum}$ works by running
GenericDecider (Algorithm 1) with the LM (Definition 2.7) as DPNoisy. Since we
post-process a DP estimate (Proposition 2.6):

###### Observation 5.1.

$LM_{sum}$ satisfies $\epsilon$-DP.

$LM_{sum}$ suffers from the drawback that $GS_{q}$ is often large in practice,
resulting in high variance in $\nu_{q}$. For example, $A_{i}$ can represent
incomes, distances, etc. and may contain large numbers. This can cause
$LM_{sum}$ to make mistakes with higher probability. We derive an upper bound
for the effectiveness threshold below.

###### Proposition 5.2.

Given a private database $D$, synthetic database $D_{s}$, SUM query $q$ with
global sensitivity $GS_{q}$, privacy budget $\epsilon$, and error probability
$0<\delta<1$, the effectiveness threshold of the per-query decider $LM_{sum}$
at $\delta$ (Definition 3.4) has the following upper bound:
$\tau_{min}^{LM_{sum},\delta}\leq\frac{GS_{q}}{\epsilon}\ln{\frac{1}{2\delta}}$.

###### Proof Sketch.

The proof is the same as that of Proposition 4.3 (full proof given in Appendix
B.1). Since $\nu_{q}\sim Lap(GS_{q}/\epsilon)$, bounds (3)-(5) now use
$\frac{GS_{q}}{\epsilon}$ than $\frac{1}{\epsilon}$. ∎

We now give an example to illustrate how $\tau_{min}^{LM_{sum},\delta}$ is
computed. We will refer to this example again in Sections 5.2 and 5.3.

###### Example 5.3.

Let $D$ be the database derived from IPUMS-CPS (Flood et al., 2022) with
attributes $age,$ $sex,education$ and $income$-$total$, and $D_{s}$ be its
synthetic copy from an SDG. Consider the query $q$: SELECT
SUM($income$-$total$) FROM $D_{s}$ WHERE $age\leq 18$. Suppose
$GS_{q}=2M,DS_{q,D}=9K$ and $\epsilon=0.1$. For $\delta=0.05$, we get
$\tau_{min}^{LM_{sum},\delta}=\frac{GS_{q}}{\epsilon}\ln{\frac{1}{2\delta}}=4.605\times
10^{7}$.

Observe that $\tau_{min}^{LM_{sum},\delta}$ is proportional to $GS_{q}$, so it
is large in part due to $GS_{q}$ being large. If $GS_{q}$ was $2$, then
$\tau_{min}^{LM_{sum},0.05}=46.052$. Thus, $\tau_{min}^{LM_{sum},\delta}$
highly depends on $dom(A_{i})$ for sum, as expected.

###  5.2. R2T-based Approach

Our next algorithm, $R2T_{sum}$, uses a state-of-the-art DP mechanism for sum
queries called Race-to-the-Top (R2T) (Dong et al., 2022) to obtain a DP
estimate for $q(D)$. R2T constructs $\log(GS_{q})$ number of queries
(described below) with global sensitivities bounded by $2,4,8,\ldots,GS_{q}$.
Then it computes a noisy estimate for each query using the LM (Definition 2.7)
and returns the max of the largest noisy estimate and $0$ (for non-negative
integer-valued domain).

In $R2T_{sum}$, the $j$-th query (for $j=1$ to $\log(GS_{q})$) works by
running the original SUM query $q$ on a truncated database constructed by
removing tuples in $D$ with $A_{i}$ value greater than $t_{j}=2^{j}$. The
output is denoted by $q(D,t_{j})$. In Appendix B.2, we show that this choice
of truncation function for constructing queries satisfies the required
properties as stated in (Dong et al., 2022).

R2T (Dong et al., 2022) computes the noisy estimates for the constructed
queries as follows (for a given parameter $0<\beta<1$, which corresponds to
the confidence bound as equation (19) below will show):

(17)
$\displaystyle\tilde{q}(D,t_{j})=q(D,t_{j})+Lap\left(\frac{t_{j}}{\epsilon/\log(GS_{q})}\right)-\frac{t_{j}}{\epsilon/\log(GS_{q})}\ln{\frac{\log(GS_{q})}{\beta}}$

where $t_{j}=2^{j},j=1$ to $\log(GS_{q})$. The final estimate for $q(D)$ is:

(18) $\displaystyle\tilde{q}(D)=\max\\{\max_{j}\tilde{q}(D,t_{j}),q(D,0)\\}$

In our setting, the downward local sensitivity $DS_{q,D}$ (Definition 2.4) is
the largest $A_{i}$ value from tuples in $D$ that satisfy the WHERE condition
$\varphi$ in $q$, because removing the matching tuple gives the worst-case
change for $D\approx D^{\prime},D^{\prime}\subseteq D$. The following result
from (Dong et al., 2022) holds (discussed further in Appendix B.2)

(19) $\displaystyle Pr\left[q(D)\geq\tilde{q}(D)\geq
q(D)-4\log(GS_{q})\ln{\left(\frac{\log(GS_{q})}{\beta}\right)}\frac{DS_{q,D}}{\epsilon}\right]\geq
1-\beta$

In other words, the probability that the noisy estimate $\tilde{q}(D)$ for
$q(D)$ in $R2T_{sum}$ lies in the range
$[q(D)-4\log(GS_{q})\ln{\left(\frac{\log(GS_{q})}{\beta}\right)}\cdot$
$\frac{DS_{q,D}}{\epsilon},$ $q(D)]$ is at least $1-\beta$.

To summarize, $R2T_{sum}$ works by running GenericDecider (Algorithm 1) with
R2T (Dong et al., 2022) (and the aforementioned truncation function) as
DPNoisy, with parameters $GS_{q}$ and $0<\beta<1$ for confidence bound in
(19). Since we post-process a DP estimate (Proposition 2.6), the following
holds:

###### Observation 5.4.

$R2T_{sum}$ satisfies $\epsilon$-DP.

We give an upper bound on the effectiveness threshold of $R2T_{sum}$ using
(19) (proof in Appendix B.3).

###### Proposition 5.5.

Given a private database $D$, synthetic database $D_{s}$, SUM query $q$ with
global sensitivity $GS_{q}$and downward local sensitivity $DS_{q,D}$, privacy
budget $\epsilon$, and error probability $0<\delta<1$, the effectiveness
threshold of the per-query decider $R2T_{sum}$ at $\delta$ (Definition 3.4)
has the following upper bound: $\tau_{min}^{R2T_{sum},\delta}\leq
4\log(GS_{q})\ln{\left(\frac{\log(GS_{q})}{\delta}\right)}\frac{DS_{q,D}}{\epsilon}$.

We now illustrate how to compute $\tau_{min}^{R2T_{sum},\delta}$ for Example
5.3.

###### Example 5.6.

Recall the setting in Example 5.3. As a result,

$\displaystyle\tau_{min}^{R2T_{sum},\delta}=4\log(GS_{q})\ln{\left(\frac{\log(GS_{q})}{\delta}\right)}\frac{DS_{q,D}}{\epsilon}=4.549\times
10^{7}$

which is less than $\tau_{min}^{LM_{sum},\delta}=4.605\times 10^{7}$.

Observe that $\tau_{min}^{R2T_{sum},\delta}$ is proportional to
$\log{(GS_{q})}\log{\log{(GS_{q})}}\cdot$ $DS_{q,D}$, so it is large in part
due to $GS_{q}$ being large. In Example 5.6,
$\tau_{min}^{R2T_{sum},\delta}<\tau_{min}^{LM_{sum},\delta}$ due to the large
gap in $GS_{q}$ and $DS_{q,D}$. In our experiments (Section 7), we empirically
show how the errors for SUM queries vary in datasets with larger and smaller
$GS_{q}$ values.

###  5.3. SVT-based Approach

The Sparse Vector Technique (SVT) (Dwork and Roth, 2014; Lyu et al., 2017) is
a DP mechanism to report whether the output of a query $q$ on $D$ exceeds its
specified threshold. It compares noisy versions of $q(D)$ and the threshold,
and gives a yes ($\top$ = noisy query answer exceeded noisy threshold) or no
($\bot$ = noisy query answer did not exceed noisy threshold) answer. An
advantage of using SVT is that it consumes privacy budget only if output =
$\top$. The SVT algorithm is applied on a sequence of queries, each with its
own threshold, resulting in an output given by $\\{\top,\bot\\}^{l}$, where
$l$ is the number of queries answered. The balance on the privacy budget
degrades with the number of queries with output = $\top$ until the privacy
budget runs out (Lyu et al., 2017) and SVT stops.

We denote the per-query decider for SUM query $q$ that runs SVT on a sequence
of sum queries (described below) as $SVT_{sum}$ (Algorithm 2). Given privacy
budget $\epsilon$, $SVT_{sum}$ begins by sampling a noise term $\rho$
distributed as $Lap(\frac{1}{\epsilon/2})$ (line 2) and uses it to get the
noisy thresholds for all queries. The remaining $\epsilon/2$ privacy budget is
used towards the first $\top$ in the output, after which $SVT_{sum}$ stops. We
modify the queries from $R2T_{sum}$ (Section 5.2): $q_{j}(D)$
$=q(D,t_{j})/t_{j}$, for $t_{j}=2^{j},j=1$ to $\log(GS_{q})$. We divide by
$t_{j}$ so that $\forall j,\Delta q_{j}=1$ in the worst-case (i.e. the max
over the sensitivities of the input queries now does not exceed $1$), allowing
the noise scales to be proportional to $1$ than $GS_{q}$. The relevant
threshold values are $l$ and $r$, which must also be divided by $t_{j}$.
First, SVT is run on queries $q_{j}(D)$ with threshold $T_{j}=r/t_{j}$ (loop
in line 2), adding independent Laplace noise distributed as
$Lap(\frac{1}{\epsilon/2})$ to each $q_{j}(D)$. If any noisy $q_{j}(D)$ value
results in $\top$, then $o=0$ is returned (line 2). If not, only $\epsilon/2$
privacy budget has been consumed by $\rho$ and SVT is run on queries
$q_{j}(D)$ with threshold $T_{j}=(l+1)/t_{j}$ (loop in line 2), again adding
independent Laplace noise distributed as $Lap(\frac{1}{\epsilon/2})$ to each
$q_{j}(D)$. If any noisy $q_{j}(D)$ value results in $\top$, then $o=1$ is
returned (line 2). Otherwise, $o=0$ is returned at the end (line 2).

###### Definition 5.7.

In the context of SVT (Lyu et al., 2017), the sequence of queries used is
called monotonic if, in going from $D$ to a neighboring database $D^{\prime}$,
all query answers that are different change in the same direction, i.e., they
all increase or they all decrease.

Observe that $q_{j}(D)$s are monotonic because $\forall j,q(D,t_{j})\geq
q(D^{\prime},$ $t_{j})$ or $\forall j,q(D,t_{j})\leq q(D^{\prime},t_{j})$.
This helps save a factor of $2$ in the noise scale for $\nu_{j}$ (discussed
further in Appendix B.4). Unlike the previous per-query deciders that post-
process a DP estimate, here we need to show that $SVT_{sum}$ preserves DP.

Input : $q$ \- SUM query, $D$ \- private database, $D_{s}$ \- synthetic
database, $\tau$ \- distance bound, $\epsilon$ \- privacy budget

Output : $o=1$ if the desired distance bound from $q(D_{s})$ is satisfied for
$q(D)$, else $o=0$.

1

2 Function  _$SVT_{sum}$(_$q,D,D_{s},\tau,\epsilon$_)_:

3 $A_{i}\leftarrow$ aggregate attribute in $q$;

4 $l\leftarrow q(D_{s})-\tau,r\leftarrow q(D_{s})+\tau$;

5 $\rho\leftarrow Lap(\frac{1}{\epsilon/2})$;

6 for  _$j\in\\{1,2,3,\ldots,\lceil\log(GS_{q})\rceil\\}$_ do

7 $t_{j}\leftarrow 2^{j},q(D,t_{j})\leftarrow$ SELECT SUM($A_{i}$) FROM $D$
WHERE $\varphi$ AND $A_{i}\leq t_{j}$;

8 $q_{j}(D)\leftarrow q(D,t_{j})/t_{j},\nu_{j}\leftarrow
Lap(\frac{1}{\epsilon/2})$;

9 if  _$q_{j}(D)+\nu_{j}\geq r/t_{j}+\rho$_ then

10 return $o=0$ (“Distance bound unmet”);

11

12

13 for  _$j\in\\{1,2,3,\ldots,\lceil\log(GS_{q})\rceil\\}$_ do

14 $t_{j}\leftarrow 2^{j},q(D,t_{j})\leftarrow$ SELECT SUM($A_{i}$) FROM $D$
WHERE $\varphi$ AND $A_{i}\leq t_{j}$;

15 $q_{j}(D)\leftarrow q(D,t_{j})/t_{j},\nu_{j}\leftarrow
Lap(\frac{1}{\epsilon/2})$;

16 if  _$q_{j}(D)+\nu_{j}\geq(l+1)/t_{j}+\rho$_ then

17 return $o=1$ (“Distance bound satisfied”);

18

19

20 return $o=0$ (“Distance bound unmet”);

21

Algorithm 2 Per-query decider $SVT_{sum}$ for SUM

###### Theorem 5.8.

$SVT_{sum}$ is $\epsilon$-DP.

###### Proof Sketch.

Let $\top_{1}$ and $\top_{2}$ denote the ‘yes’ answers from SVT, i.e., when
the noisy query answer exceeds the noisy threshold in lines 2 and 2,
respectively. Let $\bot_{1}$ and $\bot_{2}$, respectively, denote when these
checks fail. Since the algorithm stops as soon as a $\top_{1}$ or $\top_{2}$
is returned in lines 2 or 2, the output string $a$ is either of the form
$\bot_{1},\ldots,\bot_{1},\top_{1}$ or
$\bot_{1},\ldots,\bot_{1},\bot_{2},\ldots,\bot_{2},\top_{2}$. For both forms,
we show in the full version that $Pr[SVT_{sum}(q,D,D_{s},\tau,\epsilon)=a]\leq
e^{\epsilon}Pr[SVT_{sum}(q,D^{\prime},D_{s},\tau,\epsilon)=a]$ for $D\approx
D^{\prime}$ holds adapting ideas from (Lyu et al., 2017). Intuitively,
$SVT_{sum}$ is equivalent to running SVT once, with the first half mapped to
$o=0$ and the remaining half mapped to $o=1$. A complete proof is given in
Appendix B.4. ∎

$SVT_{sum}$ incurs high error if $q(D)$ and $r$ (or $l$) are close because in
the later iterations where $t_{j}$ values are large, the check is easily
influenced by noise. Note that $\forall t_{k}\geq DS_{q,D},q(D,t_{k})=q(D)$,
where $DS_{q,D}$ is the downward local sensitivity (Definition 2.4). We
present an optimization in Algorithm 4 in Appendix B.5 aimed at improving the
accuracy of $SVT_{sum}$ by obtaining a private bound for $DS_{q,D}$ to be used
as the largest truncation threshold. In the rest of the paper, by $SVT_{sum}$
we will refer to the improved algorithm using the bound from Algorithm 4. We
analyze the error of $SVT_{sum}$ in Appendix B.6.

Comparison of $LM_{sum}$, $R2T_{sum}$ and $SVT_{sum}$. As demonstrated by
Examples 5.3 and 5.6, when the difference between $DS_{q,D}$ and $GS_{q}$ is
large, the effectiveness threshold for $R2T_{sum}$ is likely to be smaller
than that of $LM_{sum}$. We show that $SVT_{sum}$ can achieve smaller error
than $R2T_{sum}$ in the experiments (Section 7).

##  6\. Solutions for MEDIAN query

We present two solutions and analyze their errors for MEDIAN query $q$ on
attribute $A_{i}$: SELECT MEDIAN($A_{i}$) FROM $D$ WHERE $\varphi$. ($1$)
$EM_{med}$ (that instantiates Algorithm 1 with the Exponential Mechanism (EM))
in Section 6.1, and ($2$) $Hist_{med}$ (that directly solves the problem using
a noisy histogram) in Section 6.2. The true output of the median query $q(D)$
is the $\lceil\frac{n^{\prime}}{2}\rceil$-th element in the sorted list of
$A_{i}$ values among tuples that satisfy the WHERE clause, where $n^{\prime}$
is the (private) number of tuples in $D$ satisfying $\varphi$.

###  6.1. Exponential Mechanism-based approach

Let $rank_{\varphi}(D,e)$ be the output of the query: SELECT COUNT(*) FROM $D$
WHERE $\varphi$ AND $A_{i}<e$. Our approach $EM_{med}$ uses the algorithm from
(Cormode et al., 2011) that computes a noisy estimate for $q(D)$. $EM_{med}$
runs GenericDecider with the EM as DPNoisy, with additional parameters
$\mathcal{R}=dom(A_{i})$ and score function
$u(D,e)=-|rank_{\varphi}(D,e)-\frac{n^{\prime}}{2}|$, $\forall
e\in\mathcal{R}$. The sensitivity of the score function equals $1$ because
rank of any $e$ either stays the same or changes in the same direction as
$n^{\prime}$ between databases $D\approx D^{\prime}$. Since we post-process a
DP estimate (Proposition 2.6), the following observation holds:

###### Observation 6.1.

$EM_{med}$ satisfies $\epsilon$-DP.

We analyze the error of $EM_{med}$ in Appendix C.1.

###  6.2. Histogram-Based Algorithm

We next propose a histogram-based approach called $Hist_{med}$ (Algorithm 3),
which uses the intuition that if at least half the values in $A_{i}$ (from
tuples satisfying $\varphi$) either are less than or equal to $l$, or are
greater than or equal to $r$, then $q(D)\not\in\mathcal{I}$. These bounds
$l=q(D_{s})-\tau$ and $r=q(D_{s})+\tau$ are compared with a DP estimate, say
$m$, for $\lceil\frac{n^{\prime}}{2}\rceil$ obtained using the LM (line 3,
where $n^{\prime}$ is the number of tuples in $D$ satisfying $\varphi$). If
neither count exceeds $m$, then $o=1$ (line 3). Otherwise, $o=0$ (lines 3 and
3).

Input : $q$ \- MEDIAN query, $D$ \- private database, $D_{s}$ \- synthetic
database, $\tau$ \- distance bound, $\epsilon$ \- privacy budget for error
analysis

Output : Whether the distance bound is met for $q$

1

2 Function  _$Hist_{med}$(_$q,D,D_{s},\tau,\epsilon$_)_:

3 $n^{\prime}\leftarrow$ number of tuples in $D$ that satisfy $\varphi$ in
$q$;

4 $\nu_{q}\leftarrow Lap(\frac{1}{\epsilon/2}),\tilde{n}\leftarrow
n^{\prime}+\nu_{q}$;

5 $A_{i}\leftarrow$ attribute for median used in $q$;

6 $q_{1}(D)\leftarrow$ SELECT COUNT(*) FROM $D$ WHERE $\varphi$ AND $A_{i}\leq
q(D_{s})-\tau$;

7 $q_{2}(D)\leftarrow$ SELECT COUNT(*) FROM $D$ WHERE $\varphi$ AND $A_{i}\geq
q(D_{s})+\tau$;

8 $\nu_{q_{1}},\nu_{q_{2}}\leftarrow Lap(\frac{1}{\epsilon/2})$;

9 if  _$q_{1}(D)+\nu_{q_{1}}\geq\lceil\tilde{n}/2\rceil$_ then

10 return $o=0$ (“Distance bound unmet”);

11

12 else if  _$q_{2}(D)+\nu_{q_{2}}\geq\lceil\tilde{n}/2\rceil$_ then

13 return $o=0$ (“Distance bound unmet”);

14

15 else

16 return $o=1$ (“Distance bound satisfied”);

17

18

Algorithm 3 Per-query decider $Hist_{med}$ for MEDIAN

We next show that $Hist_{med}$ is $\epsilon$-DP.

###### Proposition 6.2.

$Hist_{med}$ satisfies $\epsilon$-DP.

###### Proof Sketch.

We spend $\epsilon/2$ to obtain an estimate for $n^{\prime}$, and the
remaining $\epsilon/2$ on $q_{1}(D)$ and $q_{2}(D)$ (lines 3-3) that use
disjoint sets of tuples ($\tau>0$). Hence $Hist_{med}$ satisfies $\epsilon$-DP
by sequential and parallel composition, and post-processing (Proposition 2.6).
∎

Comparison of $EM_{med}$ and $Hist_{med}$. Suppose $q$ is a query that
computes the median on attribute $age,q(D)=37,\epsilon=0.1,\tau=5$, and
$\mathcal{I}=(28,38)$ (as defined in (1)). $EM_{med}$ returns $e=38$ with
probability equal to $0.9995$. $38\not\in\mathcal{I}$ but
$q(D)\in\mathcal{I}$. $Hist_{med}$ can be the better choice (discussed further
in Appendix C.2).

Extending the framework to other aggregates. Our solutions can be used to
support some other aggregates, e.g., average can be expressed as the output of
a SUM query divided by the output of a COUNT query, each consuming some
$\epsilon$. The solutions for MEDIAN can be generalized to work for other
quantiles. For example, to compute the first quartile, we change the score
function in $EM_{med}$ to use $n^{\prime}/4$ instead of $n^{\prime}/2$, and
change $\lceil\tilde{n}/2\rceil$ to $\lceil\tilde{n}/4\rceil$ and $\lceil
3\tilde{n}/4\rceil$ in lines 3 and 3 (Algorithm 3), respectively. However,
supporting more complex aggregates needs careful analysis to establish bounds.

##  7\. Experiments

In this section, we analyze the accuracy and efficiency of our proposed per-
query deciders for COUNT, SUM and MEDIAN queries with the following questions:

  1. (1)

How is the accuracy of each proposed solution affected when $\tau$ and
$\epsilon$ are varied separately?

  2. (2)

For each proposed solution, what type of queries benefit most in terms of
accuracy?

  3. (3)

How does the performance of the specialized solutions compare with that of the
solutions bases on Algorithm 1?

We have implemented the per-query deciders in Python $3.8.8$ using Pandas
(pandas development team, 2020) and NumPy (Harris et al., 2020) libraries. All
experiments were run on Apple M$1$ CPU<EMAIL_ADDRESS>GHz with $16$ GB of RAM.

###  7.1. Experimental Setup

We describe the datasets, queries, error measures, and parameters.

Dataset.  We consider two datasets as the private database $D$.

(1) The first dataset is derived from the IPUMS-CPS survey data  (Flood et
al., 2022), an individual-level population database, for the years
$2011$-$2019$ with $1,340,703$ tuples and $10$ attributes: $relate$, $age$,
$sex$, $race$, $marst$, $citizen$, $workly$, $classwkr$, $educ$ and $inctot$.
The only numerical attributes are $age$ and $inctot$ with domains
$\\{0,1,\ldots,80,85\\}$ and $\\{0,1,\ldots,$ $999999999\\}$, respectively. We
only include tuples with $inctot$ value less than or equal to $500$K. The
domain sizes of the categorical attributes vary from $3$ to $36$.  (2) The
second dataset is derived from the NYC Yellow Taxi Trip data (TLC, 2022) for
January $2022$ with $2,177,719$ tuples and $10$ attributes: $vendorID$,
$passenger\\_count$, $trip\\_distance$, $rateCodeID$,
$store\\_and\\_fwd\\_flag$, $payment\\_type$, $fare\\_amount$, $tip\\_amount$,
$total\\_amount$ and $congestion\\_surcharge$ (with some pre-processing as
discussed in Appendix D). The domain sizes of the categorical attributes vary
from $2$ to $6$.

We generate a synthetic database $D_{s}$ for $D$ using PrivBayes (Zhang et
al., 2017), a Bayesian network based DP-SDG. Nodes and edges in the network
represent attributes in $D$ and conditional independence relations between
attributes in $D$. PrivBayes first learns a differentially private Bayesian
network $\hat{\mathcal{N}}$ and then uses it to derive a factored form of the
joint tuple probabilities based on the noisy conditional probabilities. Note
that $\hat{\mathcal{N}}$ can make incorrect conditional independence
assumptions between attributes in $D$.

Queries. We refer to the Summary File $1$ (SF-$1$) (SF1, 2012) released by the
U.S. Census Bureau to construct queries  for the IPUMS-CPS dataset. We analyze
$12$ COUNT, $9$ SUM (on $inctot$) and $9$ MEDIAN (on $age$) queries.  For the
second dataset, we analyze $10$ COUNT, $10$ SUM (on $total\\_amount$), and
$10$ MEDIAN (on $trip\\_distance$) queries. Due to space constraints, here we
present results on $4$ representative queries of each aggregate on the IPUMS-
CPS data, and $2$ SUM queries on the NYC Taxi Trip data with $DS_{q,D}$ much
smaller than $GS_{q}$ (Table 2), while the full list of queries and results
for the other queries on both datasets are shown in Appendix D.

Query | WHERE clause | $q(D),q(D_{s})$
---|---|---
|  |  $q_{1}$: $sex$ LIKE ‘Female’ AND $race$ LIKE ‘White-
---
American Indian-Asian’ AND $workly$ LIKE ‘Yes’
| $34$
---
$34$
|  |  $q_{3}$: $sex$ LIKE ‘Male’ AND $educ$ LIKE ‘Doctorate
---
degree’ AND $marst$ LIKE ‘Separated’
| $87$
---
$91$
|  |  $q_{5}$: $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘Grades $5$
---
or $6$’ AND $marst$ LIKE ‘Never married/single’
| $1560$
---
$1606$
1\. COUNT |  |  $q_{12}$: $race$ LIKE ‘White’ AND $marst$ LIKE ‘Married,
---
spouse present’ AND $citizen$ LIKE ‘Born in U.S’
| $471994$
---
$470483$
|  |  $q_{13}$: $sex$ LIKE ‘Female’ AND $race$ LIKE
---
‘White-Black’ AND $workly$ LIKE ‘No’
| $6915340$
---
$6942866$
|  |  $q_{16}$: $race$ LIKE ‘White’ AND $marst$ LIKE ‘Divorced’
---
AND $citizen$ LIKE ‘Not a citizen’
| $123543040$
---
$128497757$
|  |  $q_{20}$: $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘High
---
school diploma or equivalent’ AND $marst$
LIKE ‘Never married/single’
| $685635093$
---
$690711885$
2\. SUM on $inctot$ |  |  $q_{21}$: $race$ LIKE ‘White’ AND $marst$ LIKE ‘Married,
---
spouse present’ AND $citizen$ LIKE ‘Born in U.S’
| $23542765109$
---
$23434676868$
|  |  $q_{22}$: $workly$ LIKE ‘Yes’ AND $classwkr$ LIKE
---
‘Wage/salary, private’ AND $educ$ LIKE
‘Bachelor’s degree’
| $41$
---
$41$
|  |  $q_{23}$: $sex$ LIKE ‘Male’ AND $race$ LIKE ‘White-
---
Black’ AND $relate$ LIKE ‘Spouse’
| $40$
---
$40$
|  |  $q_{28}$: $race$ LIKE ‘Asian only’ AND $marst$ LIKE
---
‘Separated’ AND $citizen$ LIKE ‘Born in U.S’
| $39$
---
$39$
3\. MEDIAN on $age$ |  |  $q_{29}$: $sex$ LIKE ‘Male’ AND $race$ LIKE ‘White’
---
AND $classwkr$ LIKE ‘Wage/salary, private’
| $40$
---
$40$
|  |  $q_{45}$: $passenger\\_count<2$ AND $trip\\_distance=8$
---
AND $tip\\_amount\leq 2$
| $218047$
---
$213685$
4\. SUM on $total\\_$ $amount$ |  |  $q_{50}$: $trip\\_distance\leq 1$ AND $fare\\_amount\leq 6$
---
AND $congestion\\_surcharge=2$
| $5680776$
---
$5624898$
Table 2. Queries used in experiments. Blocks 1, 2, 3 are for the IPUMS-CPS
data, block 4 is for the NYC Taxi Trip data.

Error measure. We measure the error of per-query deciders as follows. We run
each of our per-query deciders 100 times to decide whether $q(D)$ lies in
$(q(D_{s})\cdot(1-\tau),q(D_{s})\cdot(1+\tau))$, where $\tau$ is a percentage
of the query answer on the synthetic data, $q(D_{s})$. We measure error as the
fraction of times the algorithm makes an error in determining whether $q(D)$
lies in $(q(D_{s})\cdot(1-\tau),q(D_{s})\cdot(1+\tau))$.

Parameter settings. We set $\beta=0.05$ in $R2T_{sum}$ (Section 5.2) and
$\theta=0.95$ in Algorithm $4$ (Section 5.3). Default $\epsilon=0.25$ and
$\tau=3.2\%$ of $q(D_{s})$. In our experiments, we vary
$\tau=0.2\%,0.8\%,3.2\%,$ $12.8\%,51.2\%$, and vary
$\epsilon=0.0625,0.125,0.25,0.5,1$.

###  7.2. Accuracy and Performance Analysis

####  7.2.1. Accuracy analysis

We present our analysis of the impact on accuracy as $\epsilon$ and $\tau$ are
varied individually. We also investigate which queries benefit the most for
each per-query decider. In the following discussion, we use
$\mathcal{I}=(q(D_{s})\cdot(1-\tau),q(D_{s})\cdot(1+\tau))$, where $\tau$ is a
percentage of $q(D_{s})$.

Figure 5.  IPUMS-CPS data: Error for COUNT queries from $LM_{count}$ (in blue)
and $EM_{count}$ (in orange) as $\tau$ varies.  The dotted line marks the
smallest $\tau$ value considered such that the query answer on the private
data belongs in the interval $\mathcal{I}$. Figure 6.  IPUMS-CPS data: Error
for COUNT queries from $LM_{count}$ (in blue) and $EM_{count}$ (in orange) as
$\epsilon$ varies.  Figure 7.  IPUMS-CPS data: Error for SUM queries from
$LM_{sum}$ (in blue), $R2T_{sum}$ (in purple) and $SVT_{sum}$ (in brown) as
$\tau$ varies.  The dotted line marks the smallest $\tau$ value considered
such that the query answer on the private data belongs in the interval
$\mathcal{I}$. Figure 8.  IPUMS-CPS data: Error for SUM queries from
$LM_{sum}$ (in blue), $R2T_{sum}$ (in purple) and $SVT_{sum}$ (in brown) as
$\epsilon$ varies.  Figure 9.  IPUMS-CPS data: Error for MEDIAN queries from
$EM_{med}$ (in orange) and $Hist_{med}$ (in green) as $\tau$ varies.  The
dotted line marks the smallest $\tau$ value considered such that the query
answer on the private data belongs in the interval $\mathcal{I}$. Figure 10.
IPUMS-CPS data: Error for MEDIAN queries from $EM_{med}$ (in orange) and
$Hist_{med}$ (in green) as $\epsilon$ varies. Figure 11.  NYC Taxi data: Error
for SUM queries from $LM_{sum}$ (in blue), $R2T_{sum}$ (in purple) and
$SVT_{sum}$ (in brown) as $\epsilon$ and $\tau$ vary separately. The dotted
line marks the smallest $\tau$ value considered such that the query answer on
the private data belongs in $\mathcal{I}$.

COUNT queries. We present our analysis for $4$ queries: $q_{1},q_{3},q_{5}$
and $q_{12}$ (Figures 5-6). Consider the setting where $\tau$ varies.
$q_{1}(D)$ equals $q_{1}(D_{s})$ and error from both $LM_{count}$ and
$EM_{count}$ decreases when $\tau$ increases, as expected. $EM_{count}$ gives
smaller error. For $\tau\leq 3.2\%,q_{3}(D)\not\in\mathcal{I}$. At
$\tau=3.2\%$, $q_{3}(D)$ is closest to one of $\mathcal{I}$’s endpoints, so we
see the error from $LM_{count}$ increase (before it goes to $0$) because there
is a higher probability of $q_{3}(D)$’s noisy estimate being in $\mathcal{I}$.
Similarly for $EM_{count}$ on $q_{3}$, where error starts decreasing for
$\tau>3.2\%$. $EM_{count}$’s error on $q_{3}$ for $\tau\leq 3.2\%$ ranges from
$0.39$ to $0.45$. For $\tau\leq 0.8\%,q_{5}(D)\not\in\mathcal{I}$. At
$\tau=3.2\%$, $q_{5}(D)\in\mathcal{I}$ and is closest to one of
$\mathcal{I}$’s endpoints, so $LM_{count}$’s error has the same trend as that
for $q_{3}$. In $EM_{count}$ for $q_{5}$ and $\tau=0.2\%$,
$c\cdot\exp(\epsilon u^{\prime}(\cdot)\tau)$ (Definition 2.10) for $o=0$ and
$o=1$ are closest, so $Pr[o=1]=0.27$ (after normalization). $EM_{count}$’s
error increases at $\tau=3.2\%$ (before it goes to $0$) because $q_{5}(D)$ is
close to an endpoint of $\mathcal{I}$. $LM_{count}$ and $EM_{count}$ give $0$
error for $q_{12}$ because the resulting $\tau$ values are such that $q(D)$
stays far from $\mathcal{I}$’s endpoints.

When $\epsilon$ is varied instead, the errors from both $LM_{count}$ and
$EM_{count}$ have a decreasing trend except for $q_{3}$ and $q_{12}$. As
$\epsilon$ increases,  the DP computations become less noisy. $LM_{count}$’s
error on $q_{3}$ increases initially because probability of $q_{3}(D)$’s noisy
estimate being in $\mathcal{I}$ increases despite the noise scale decreasing
(before error goes to $0$). Similarly for $EM_{count}$ on $q_{3}$.
$EM_{count}$’s error on $q_{12}$ increases for $\epsilon>0.5$ because
$c\cdot\exp(\epsilon u^{\prime}(\cdot)\tau)$ (Definition 2.10) for $o=0$ and
$o=1$ is greater than $c\cdot\exp(7527\cdot u^{\prime}(\cdot))$, represented
as infinity in Python. Either outcome is equally likely to be returned.

SUM queries. We present our analysis for $4$ queries: $q_{13},q_{16},q_{20}$
and $q_{21}$ (Figures 7-8). $DS_{q,D}$ values are: $127764,$
$278011,403353,500000$. Consider the setting where $\tau$ varies.
$q_{13}(D)\not\in\mathcal{I}$ (as defined in (1)) at $\tau=0.2\%$ and the
probability of $LM_{sum}$’s noisy estimate being outside $\mathcal{I}$ is
high, so the error is low. $LM_{sum}$’s error shoots up at $\tau=0.8\%$
because $q_{13}(D)$ is now in $\mathcal{I}$, but the probability that
$q_{13}(D)$’s noisy estimate is outside $\mathcal{I}$ is high. Error decreases
as $\tau$ increases further. Similarly for $q_{16}$ and $q_{20}$. $LM_{sum}$
incurs an error of $0$ for $q_{21}$ in all cases because $q_{21}(D)$ is large
and for the chosen $\tau$ values, it is far from $\mathcal{I}$’s endpoints in
comparison to the noise scale. $R2T_{sum}$ gives error close to $1$ whenever
$q_{13}(D)\in\mathcal{I}$ because the noise in its estimate for $q_{13}(D)$ is
large and this estimate falls outside $\mathcal{I}$. Similarly for $q_{16}$.
$R2T_{sum}$’s error on $q_{20}$ is high when $q_{20}(D)\in\mathcal{I}$ but
$\tau$ is small compared to the noise in $R2T_{sum}$’s estimate for
$q_{20}(D)$. As $\tau$ increases, the error decreases. $R2T_{sum}$’s error on
$q_{21}$ follows the same trend as that of $q_{20}$, except the error stays
low because $q_{21}(D_{s})$ is large and consequently $\tau$ values are large.
$SVT_{sum}$’s error on $q_{13}$ is low at $\tau=0.2\%$ because $q_{13}(D)<l$
and the chance of any noisy truncated sum query exceeding its noisy threshold
is low (lines 2 and 2 in Algorithm 2). For larger $\tau$,
$q_{13}(D)\in\mathcal{I}$ and moves away from $\mathcal{I}$’s endpoints, which
increases the chance of the threshold in line 2 not being exceeded and in line
2 being exceeded. Similarly for $q_{16}$, $q_{20}$ and $q_{21}$, where the
last two have large outputs on $D_{s}$ and so error decreases sooner.

When $\epsilon$ is varied, $LM_{sum}$’s error on the $4$ queries shows a
decreasing trend because the noise scale decreases as $\epsilon$ increases.
$q_{13}(D),q_{20}(D)$ and $q_{21}(D)$ are in the associated $\mathcal{I}$ at
(default) $\tau=3.2\%$. For the first two, increasing $\epsilon$ does not
change $R2T_{sum}$’s error  because the noise is
$O(\log{(GS_{q})}\log{\log{(GS_{q})}}\cdot DS_{q,D})$ (from (19)), keeping
$\tilde{q}(D)$ outside $\mathcal{I}$ with high probability. Since
$q_{21}(D_{s})$ is the largest, $R2T_{sum}$’s error decreases  because the
noise in $\tilde{q}(D)$ decreases as $\epsilon$ increases, while
$\mathcal{I}$’s width stays the same. For queries with answers on $D$ in
$\mathcal{I}$, $SVT_{sum}$’s error does not change much as $\epsilon$
increases.  $q_{13}(D)$ and $q_{20}(D)$ are close to the left-endpoints of the
respective intervals, and so $SVT_{sum}$’s error is high (line 2 in Algorithm
2). In contrast, $SVT_{sum}$’s error on $q_{16}$ decreases as $\epsilon$
increases because the noise scale decreases and $q_{16}(D)<l$.

Next, we analyze the impact of larger gaps in $DS_{q,D}$ and $GS_{q}$, for
small $GS_{q}$ of $377$ (Figure 11). When $\tau$ varies, $LM_{sum}$ and
$R2T_{sum}$ give highest error for $q_{45}$ at $\tau=3.2\%$ as
$q_{45}(D)\in\mathcal{I}$ (closer to $r$), but the noise in their estimates
for $q_{45}(D)$ is large while interval width is small, causing the estimates
to not be in $\mathcal{I}$. At $\tau=0.8\%$, $q_{50}(D)\not\in\mathcal{I}$
(closer to $r$). $LM_{sum}$ and $R2T_{sum}$ give low error as $\mathcal{I}$’s
width is large and their estimates for $q_{50}(D)$ are in $\mathcal{I}$ with
high probability. $SVT_{sum}$ gives low error for both queries, except for
$q_{50}$ at $\tau=0.8\%$ as the truncation threshold from Algorithm $4$ is
often smaller than $DS_{q,D}$, causing the check in line 2 to incorrectly
fail.

At default $\tau=3.2\%$, $q_{45}(D)$ and $q_{50}(D)$ are in their associated
intervals (closer to $r$). For $q_{45}$, the interval is small, so all $3$
solutions give error at least $0.35$ when $\epsilon$ is small, with
$R2T_{sum}$ giving the highest error due to large noise in its estimate. For
$q_{50}$, the interval width is larger, so all $3$ solutions give $0$ error.

MEDIAN queries. We present our analysis for $4$ queries:
$q_{22},q_{23},q_{28}$ and $q_{29}$ (Figures 9-10). Consider the setting where
$\tau$ varies. Let us first look at $EM_{med}$. For $q_{22}$ and $q_{29}$, the
support, i.e., tuples in $D$ that satisfy the predicates in the WHERE clause,
is large. As a result, the probability distribution used to sample the noisy
estimate for the median is more concentrated around the correct value. The
opposite is true for $q_{23}$ and $q_{28}$. We see error decrease as $\tau$
increases. $Hist_{med}$’s error has a decreasing trend in all cases because
the noisy bin counts are far from the query’s noisy estimate for majority,
i.e., $\lceil n^{\prime}/2\rceil$ (lines 3 and 3 in Algorithm 3).

When $\epsilon$ increases, the variance of the probability distribution used
to sample the noisy estimate in $EM_{med}$ decreases. $EM_{med}$’s error has a
decreasing trend except for $q_{29}$ because the scores are negatives numbers
with large magnitudes because the support is large (Definition 2.10). As
discussed above for $Hist_{med}$, the noisy bin counts are far from the
query’s noisy estimate for majority. As $\epsilon$ increases, the error
decreases because the noise scale decreases.

####  7.2.2. Performance analysis

We compare average runtimes of per-query deciders for COUNT, SUM and MEDIAN
queries in Table 3. The reported average is per query and per $1$ run (out of
the $100$ trials).

####  7.2.3. Discussion

We summarize our findings in this section. The experiments suggest the
following comparative trends between algorithms  (Table 4). In COUNT queries,
when $q(D)=q(D_{s})$, $EM_{count}$’s error is smaller than $LM_{count}$’s
error for different $\epsilon$ and $\tau$ values. When $q(D)\in\mathcal{I}$
and $q(D)\not\in\mathcal{I}$, $LM_{count}$ is superior. In SUM queries, when
$q(D)\in\mathcal{I}$ and $\tau$ varies, $LM_{sum}$ was the best choice
followed by $SVT_{sum}$. Note that $DS_{q,D}$ plays an important role here.
When $q(D)\not\in\mathcal{I}$, $R2T_{sum}$ and $SVT_{sum}$ were the better
choices. In MEDIAN queries, $Hist_{med}$ generally gives smaller error than
$EM_{med}$ no matter the relationship between $q(D)$ and $\mathcal{I}$.

There is not a clear pattern for when the error is high except for the
condition when $q(D)$ is close to one of the endpoints of the interval, or
when the downward local sensitivity is not far from the global sensitivity for
the given SUM query.

Typically, we expect error of DP algorithms to decrease with higher
$\epsilon$. But, we see the reverse in some experiments (see $LM_{count}$ for
$q_{3}$, $EM_{count}$ for $q_{12}$, $SVT_{sum}$ and $R2T_{sum}$ for queries
with answer on $D$ in the interval, and $EM_{med}$ for $q_{29}$). This is
because the error function for the per-query deciders is not monotonic in
$\epsilon$. This may suggest that there exist smarter ways to design
algorithms that only use a portion of the overall budget available to get
better accuracy.

$LM_{count}$ and $EM_{count}$ were not effective for queries at smaller
$\tau$, except when $q(D_{s})$ and $\tau$ are large, in which case we do not
know if either approach is effective. They were effective for the same
settings. Similarly for $LM_{sum}$. $R2T_{sum}$ and $SVT_{sum}$ were not
effective for queries with large answer on $D$ at small $\tau$.  In general
for all solutions, the accuracy can be improved with a larger privacy budget
$\epsilon$, or a larger distance bound $\tau$ between $q(D)$ and $q(D_{s})$,
which may not always be feasible.

##  8\. related work

We have used several existing DP mechanisms for count, sum, and median from
the literature (Dwork and Roth, 2014; Dong et al., 2022; Lyu et al., 2017;
Cormode et al., 2011) for DP-PQD. To the best of our knowledge, most existing
works on SDGs do not give per-query error bounds to the user.  AIM (McKenna et
al., 2022) is a novel differentially private SDG that generates $D_{s}$ while
minimizing average error over all the input marginal queries, and only gives
probabilistic upper-bounds on the error for marginal queries in the downward
closure of the input workload. It follows the select-measure-generate paradigm
(Li et al., 2010; McKenna et al., 2018, 2021b): ($1$) selects a set of
queries, ($2$) privately measures chosen queries, and ($3$) generates
synthetic data from the noisy measurements.  However, it differs from our
model wherein we are given $D_{s}$ from some black-box SDG and the goal is to
decide if the distance between the given (count, sum, or median) query $q$’s
output on $D$ and $D_{s}$ is less than the user-provided threshold $\tau$. We
do not make assumptions about the SDG and do not require that the given query
should be well approximated by the SDG (or $D_{s}$).

We also found that the parametric bootstrap approach (Ferrando et al., 2020)
does not work well because the underlying assumption about the difference
between bootstrap estimates and $q(D_{s})$ being representative of the
difference between $q(D_{s})$ and $q(D)$ does not hold when the SDG (e.g.
PrivBayes (Zhang et al., 2017)) uses techniques like post-processing.

| $LM_{count}$ | $EM_{count}$
---|---|---
$Time(s)$ | $0.312$ | $0.321$

| $LM_{sum}$ | $R2T_{sum}$ | $SVT_{sum}$
---|---|---|---
$Time(s)$ | $0.450$ | $4.022$ | $9.131$

| $EM_{med}$ | $Hist_{med}$
---|---|---
$Time(s)$ | $0.533$ | $1.043$

Table 3.  IPUMS-CPS data: Average runtimes. Query | Solution |  $\tau_{min}^{\mathcal{A},\delta}$ (upper bound) | Conclusions
---|---|---|---
|  | $LM_{count}$
---
(plug-in)
$\frac{1}{\epsilon}\ln{\frac{1}{2\delta}}$ |
COUNT |  | $EM_{count}$
---
(direct)
$\frac{1}{\epsilon}\ln{\frac{1-\delta}{\delta}}$ |  $LM_{count}$ is the better choice, for $\delta<\frac{1}{2}$ unless $q(D)=q(D_{s})$.
|  | $LM_{sum}$
---
(plug-in)
$\frac{GS_{q}}{\epsilon}\ln{\frac{1}{2\delta}}$ |
|  | $R2T_{sum}$
---
(plug-in)
| $4\log(GS_{q})\cdot$
---
$\ln{\left(\frac{\log(GS_{q})}{\delta}\right)}\frac{DS_{q,D}}{\epsilon}$
SUM |  | $SVT_{sum}$
---
(direct)
– |  If approx. $DS_{q,D}$ value is known to the user, and $DS_{q,D}$ is much smaller than $GS_{q}$, then choose $SVT_{sum}$ or $R2T_{sum}$. Otherwise, choose $LM_{sum}$ unless $\epsilon$ is small.
|  | $EM_{med}$
---
(plug-in)
– |
MEDIAN |  | $Hist_{med}$
---
(direct)
– |  $Hist_{med}$ empirically gives smaller error than $EM_{med}$.
Table 4.  Summary of proposed solutions and our recommendations based on
theoretical and empirical results. Those marked by (plug-in) are based on
Algorithm 1, whereas the rest solve the problem without plugging-in an
estimate for $q(D)$. Some theoretical upper bounds remain open problems.

##  9\. Conclusions and Future Work

We have presented the problem of measuring the per-query distance between the
output on private data and synthetic data, and detailed our error analysis for
COUNT, MEDIAN and SUM queries. Our proposed solutions fall in two classes:
($1$) use a DP algorithm to answer the query and check if the noisy answer is
close to the answer on the synthetic data, and ($2$) design specialized
algorithm. In addition to analyzing the error, we also introduce the notion of
effectiveness of a per-query decider and derive upper bounds on the
effectiveness thresholds of solutions for COUNT and SUM queries (except
$SVT_{sum}$). Deriving such bounds for MEDIAN query is future work. We find
that some mechanisms work better for smaller $\tau$.  Extending our work to
other useful queries involving other aggregate functions, joins, subqueries,
and group-by is future work. Designing baselines and benchmarks for the
problem in this work is future work, and may be of interest to the synthetic
data and data privacy communities.

###### Acknowledgements.

We thank the anonymous reviewers for their helpful comments. This work was
supported in part by NSF awards IIS-2147061, IIS-2008107, IIS-1703431, and
IIS-1552538.

## References

  * (1)
  * TLC (2022) 2022\.  New york city taxi and limousine commission (tlc) trip record data.  https://www.nyc.gov/site/tlc/about/tlc-trip-record-data.page.
  * Abowd (2018) John M. Abowd. 2018.  The U.S. Census Bureau Adopts Differential Privacy. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_ (London, United Kingdom) _(KDD ’18)_. Association for Computing Machinery, New York, NY, USA, 2867–2867.  https://doi.org/10.1145/3219819.3226070
  * Amin et al. (2019) Kareem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiskii. 2019.  Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy. In _Proceedings of the 36th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 263–271.  https://proceedings.mlr.press/v97/amin19a.html
  * Cai et al. (2021) Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. 2021.  Data Synthesis via Differentially Private Markov Random Field.  _Proc. VLDB Endow._ 14, 11 (2021), 2190–2202.  http://www.vldb.org/pvldb/vol14/p2190-cai.pdf
  * CCPA (2023) CCPA 2023.  California Consumer Privacy Act (CCPA).  https://oag.ca.gov/privacy/ccpa.
  * Chen et al. (2016) Yan Chen, Ashwin Machanavajjhala, Jerome P. Reiter, and Andrés F. Barrientos. 2016.  Differentially Private Regression Diagnostics. In _IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain_ , Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, and Xindong Wu (Eds.). IEEE Computer Society, 81–90.  https://doi.org/10.1109/ICDM.2016.0019
  * Cormode et al. (2011) Graham Cormode, Magda Procopiuc, Entong Shen, Divesh Srivastava, and Ting Yu. 2011.  Differentially Private Spatial Decompositions.  _CoRR_ abs/1103.5170 (2011).  arXiv:1103.5170 http://arxiv.org/abs/1103.5170
  * Ding et al. (2017) Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017.  Collecting Telemetry Data Privately. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ (Long Beach, California, USA) _(NIPS’17)_. Curran Associates Inc., Red Hook, NY, USA, 3574–3583.
  * Dong et al. (2022) Wei Dong, Juanru Fang, Ke Yi, Yuchao Tao, and Ashwin Machanavajjhala. 2022.  R2T: Instance-Optimal Truncation for Differentially Private Query Evaluation with Foreign Keys. In _Proceedings of the 2022 International Conference on Management of Data_ (Philadelphia, PA, USA) _(SIGMOD ’22)_. Association for Computing Machinery, New York, NY, USA, 759–772.  https://doi.org/10.1145/3514221.3517844
  * 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_ , Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (Eds.), Vol. 4052. 1–12.
  * Dwork (2019) Cynthia Dwork. 2019.  Differential Privacy and the US Census. In _Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ (Amsterdam, Netherlands) _(PODS ’19)_. Association for Computing Machinery, New York, NY, USA, 1.  https://doi.org/10.1145/3294052.3322188
  * 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 _Advances in Cryptology (EUROCRYPT 2006)_ (advances in cryptology (eurocrypt 2006) ed.) _(Lecture Notes in Computer Science)_ , Vol. 4004. Springer Verlag, 486–503.  https://www.microsoft.com/en-us/research/publication/our-data-ourselves-privacy-via-distributed-noise-generation/
  * 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 Third Conference on Theory of Cryptography_ (New York, NY) _(TCC’06)_. Springer-Verlag, Berlin, Heidelberg, 265–284.  https://doi.org/10.1007/11681878_14
  * 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.  https://doi.org/10.1561/0400000042
  * Erlingsson et al. (2014) Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014.  RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In _Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security_ (Scottsdale, Arizona, USA) _(CCS ’14)_. Association for Computing Machinery, New York, NY, USA, 1054–1067.  https://doi.org/10.1145/2660267.2660348
  * Ferrando et al. (2020) Cecilia Ferrando, Shufan Wang, and Daniel Sheldon. 2020.  General-Purpose Differentially-Private Confidence Intervals.  _CoRR_ abs/2006.07749 (2020).  arXiv:2006.07749 https://arxiv.org/abs/2006.07749
  * Flood et al. (2022) Sarah Flood, Miriam King, Renae Rodgers, Steven Ruggles, J. Robert Warren, and Michael Westberry. 2022.  Integrated Public Use Microdata Series, Current Population Survey: Version 10.0 [dataset].  Minneapolis, MN: IPUMS, 2022.  https://doi.org/10.18128/D030.V10.0
  * Gaboardi et al. (2014) Marco Gaboardi, Emilio Jesús Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. 2014.  Dual Query: Practical Private Query Release for High Dimensional Data. In _Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014_ _(JMLR Workshop and Conference Proceedings)_ , Vol. 32. JMLR.org, 1170–1178.  http://proceedings.mlr.press/v32/gaboardi14.html
  * GDPR (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).
  * Ge et al. (2021) Chang Ge, Shubhankar Mohapatra, Xi He, and Ihab F. Ilyas. 2021.  Kamino: Constraint-Aware Differentially Private Data Synthesis.  _Proc. VLDB Endow._ 14, 10 (2021), 1886–1899.  http://www.vldb.org/pvldb/vol14/p1886-ge.pdf
  * Hardt et al. (2012) Moritz Hardt, Katrina Ligett, and Frank Mcsherry. 2012.  A Simple and Practical Algorithm for Differentially Private Data Release. In _Advances in Neural Information Processing Systems_ , F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (Eds.), Vol. 25. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2012/file/208e43f0e45c4c78cafadb83d2888cb6-Paper.pdf
  * Harris et al. (2020) Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020.  Array programming with NumPy.  _Nature_ 585, 7825 (Sept. 2020), 357–362.  https://doi.org/10.1038/s41586-020-2649-2
  * Huang et al. (2021) Ziyue Huang, Yuting Liang, and Ke Yi. 2021.  Instance-optimal Mean Estimation Under Differential Privacy. In _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 25993–26004.  https://proceedings.neurips.cc/paper/2021/file/da54dd5a0398011cdfa50d559c2c0ef8-Paper.pdf
  * Huang et al. (2019) Zhiqi Huang, Ryan McKenna, George Bissias, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. 2019.  PSynDB: Accurate and Accessible Private Data Generation.  _Proc. VLDB Endow._ 12, 12 (2019), 1918–1921.  https://doi.org/10.14778/3352063.3352099
  * Li et al. (2010) Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. 2010.  Optimizing Linear Counting Queries under Differential Privacy. In _Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems_ (Indianapolis, Indiana, USA) _(PODS ’10)_. Association for Computing Machinery, New York, NY, USA, 123–134.  https://doi.org/10.1145/1807085.1807104
  * Lyu et al. (2017) Min Lyu, Dong Su, and Ninghui Li. 2017.  Understanding the Sparse Vector Technique for Differential Privacy.  _Proc. VLDB Endow._ 10, 6 (feb 2017), 637–648.  https://doi.org/10.14778/3055330.3055331
  * McKenna et al. (2018) Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. 2018.  Optimizing Error of High-Dimensional Statistical Queries under Differential Privacy.  _Proc. VLDB Endow._ 11, 10 (jun 2018), 1206–1219.  https://doi.org/10.14778/3231751.3231769
  * McKenna et al. (2021b) Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. 2021b.  HDMM: Optimizing error of high-dimensional statistical queries under differential privacy.  _CoRR_ abs/2106.12118 (2021).  arXiv:2106.12118 https://arxiv.org/abs/2106.12118
  * McKenna et al. (2021a) Ryan McKenna, Gerome Miklau, and Daniel Sheldon. 2021a.  Winning the NIST Contest: A scalable and general approach to differentially private synthetic data.  _CoRR_ abs/2108.04978 (2021).  arXiv:2108.04978 https://arxiv.org/abs/2108.04978
  * McKenna et al. (2022) Ryan McKenna, Brett Mullins, Daniel Sheldon, and Gerome Miklau. 2022.  AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data.  _CoRR_ abs/2201.12677 (2022).  arXiv:2201.12677 https://arxiv.org/abs/2201.12677
  * McKenna et al. (2019) Ryan McKenna, Daniel Sheldon, and Gerome Miklau. 2019.  Graphical-model based estimation and inference for differential privacy. In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ _(Proceedings of Machine Learning Research)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 4435–4444.  http://proceedings.mlr.press/v97/mckenna19a.html
  * McSherry and Talwar (2007) Frank McSherry and Kunal Talwar. 2007.  Mechanism Design via Differential Privacy. In _Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science_ _(FOCS ’07)_. IEEE Computer Society, USA, 94–103.  https://doi.org/10.1109/FOCS.2007.41
  * pandas development team (2020) The pandas development team. 2020.  _pandas-dev/pandas: Pandas_.  https://doi.org/10.5281/zenodo.3509134
  * Park et al. (2018) Noseong Park, Mahmoud Mohammadi, Kshitij Gorde, Sushil Jajodia, Hongkyu Park, and Youngmin Kim. 2018.  Data Synthesis Based on Generative Adversarial Networks.  _Proc. VLDB Endow._ 11, 10 (jun 2018), 1071–1083.  https://doi.org/10.14778/3231751.3231757
  * 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 2016, Montreal, QC, Canada, October 17-19, 2016_. IEEE, 399–410.  https://doi.org/10.1109/DSAA.2016.49
  * Rosenblatt et al. (2020) Lucas Rosenblatt, Xiaoyan Liu, Samira Pouyanfar, Eduardo de Leon, Anuj Desai, and Joshua Allen. 2020.  Differentially Private Synthetic Data: Applied Evaluations and Enhancements.  _CoRR_ abs/2011.05537 (2020).  arXiv:2011.05537 https://arxiv.org/abs/2011.05537
  * SF1 (2012) SF1 2012.  https://www2.census.gov/library/publications/cen2010/doc/sf1.pdf.
  * Tang et al. (2017) Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and XiaoFeng Wang. 2017.  Privacy Loss in Apple’s Implementation of Differential Privacy on MacOS 10.12.  _CoRR_ abs/1709.02753 (2017).  arXiv:1709.02753 http://arxiv.org/abs/1709.02753
  * Thakkar et al. (2019) Om Thakkar, Galen Andrew, and H. Brendan McMahan. 2019.  Differentially Private Learning with Adaptive Clipping.  _CoRR_ abs/1905.03871 (2019).  arXiv:1905.03871 http://arxiv.org/abs/1905.03871
  * Vietri et al. (2020) Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu. 2020.  New Oracle-Efficient Algorithms for Private Synthetic Data Release. In _Proceedings of the 37th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research)_ , Hal Daumé III and Aarti Singh (Eds.), Vol. 119. PMLR, 9765–9774.  https://proceedings.mlr.press/v119/vietri20b.html
  * Xu et al. (2019) Lei Xu, Maria Skoularidou, Alfredo Cuesta-Infante, and Kalyan Veeramachaneni. 2019.  _Modeling Tabular Data Using Conditional GAN_.  Curran Associates Inc., Red Hook, NY, USA.
  * Zhang et al. (2017) Jun Zhang, Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2017.  PrivBayes: Private Data Release via Bayesian Networks.  _ACM Trans. Database Syst._ 42, 4, Article 25 (Oct. 2017), 41 pages.  https://doi.org/10.1145/3134428

##  Appendix A Proofs from Section 4

###  A.1. Proof of Proposition 4.2

###### Proof.

For ($1$): When we get an error due to $q(D)\leq l$ and $o=1$, the if
condition (line 1) in GenericDecider (Algorithm 1) is satisfied, i.e.,
$l<q(D)+\nu_{q}<r$. Re-arranging the terms gives $0\leq
l-q(D)<\nu_{q}<r-q(D)$. Now, instantiating (3) with $t=(l-q(D))\epsilon$ and
then with $t=(r-q(D))\epsilon$ gives:

(20) $\displaystyle Pr[\nu_{q}>l-q(D)]$ $\displaystyle\leq Pr[\nu_{q}\geq
l-q(D)]=\frac{1}{2}e^{-(l-q(D))\epsilon}$ (21) $\displaystyle Pr[\nu_{q}\geq
r-q(D)]$ $\displaystyle=\frac{1}{2}e^{-(r-q(D))\epsilon}$

Where the first inequality in (20) stems from the property of DP that every
output has a positive probability. Subtracting (21) from (20),
$Pr[l-q(D)<\nu_{q}<r-q(D)]\leq\frac{1}{2}\left(e^{-(l-q(D))\epsilon}-e^{-(r-q(D))\epsilon}\right)$.

($2$): When we get an error due to $q(D)\geq r$ and $o=1$, the if condition
(line 1) in GenericDecider is satisfied, i.e., $l-q(D)<\nu_{q}<r-q(D)\leq 0$
(after re-arranging the terms). Now,

$\displaystyle Pr[\nu_{q}>l-q(D)]$ $\displaystyle=1-Pr[\nu_{q}\leq-(q(D)-l)]$
(22) $\displaystyle=1-\frac{1}{2}e^{-(q(D)-l)\epsilon}$

which follows from (4) with $t=(q(D)-l)\epsilon$.

$\displaystyle Pr[\nu_{q}\geq r-q(D)]$ $\displaystyle=1-Pr[\nu_{q}<r-q(D)]$
$\displaystyle\geq 1-Pr[\nu_{q}\leq r-q(D)]$ (23)
$\displaystyle=1-\frac{1}{2}e^{-(q(D)-r)\epsilon}$

which follows from (4) with $t=(q(D)-r)\epsilon$.

Note that $Pr[l-q(D)<\nu_{q}<r-q(D)]=Pr[\nu_{q}>l-q(D)]-Pr[\nu_{q}\geq
r-q(D)]$, and from (22) and (23), this expression is less than or equal to
$\frac{1}{2}\left(e^{-(q(D)-r)\epsilon}-e^{-(q(D)-l)\epsilon}\right)$.

($3$): When we get an error due to $l<q(D)<r$ and $o=0$, the else condition
(line 1) in GenericDecider is satisfied. Here, error is given by the
probability of the union of two disjoint events: (i) $\nu_{q}\leq l-q(D)$,
which is calculated by instantiating (4) with $t=(q(D)-l)\epsilon$, and (ii)
$\nu_{q}\geq r-q(D)$, which is calculated by instantiating (3) with
$t=(r-q(D))\epsilon$. Error equals
$\frac{1}{2}e^{-(q(D)-l)\epsilon}+\frac{1}{2}e^{-(r-q(D))\epsilon}$. ∎

###  A.2. Proof of Proposition 4.3

###### Proof.

We analyze the two cases in Definition 3.4.

  1. (1)

Let $q(D)=q(D_{s})$. $LM_{count}$ returns $o=1$ when the if condition (line 1)
in GenericDecider is satisfied. Therefore,

$\displaystyle Pr[o=1]$ $\displaystyle=Pr[|q(D)+\nu_{q}-q(D_{s})|<\tau]$
$\displaystyle=Pr[|\nu_{q}|<\tau]~{}~{}\quad\text{(since $q(D)=q(D_{s})$)}$
$\displaystyle=1-Pr[|\nu_{q}|\geq\tau]$
$\displaystyle=1-e^{-\tau\epsilon}~{}~{}\quad\text{(from (\ref{eq:lap-mod})
with $t=\tau\epsilon$)}$ (24) $\displaystyle\geq
1-\delta~{}~{}\quad\text{(when
$\tau\geq\frac{1}{\epsilon}\ln{\frac{1}{\delta}}>\frac{1}{\epsilon}\ln{\frac{1}{2\delta}}$)}$

  2. (2)

Let $q(D)\not\in(q(D_{s})-2\tau,q(D_{s})+2\tau)$. Without loss of generality,
suppose $q(D)\leq q(D_{s})-2\tau$, so

(25) $\displaystyle\tau\leq q(D_{s})-\tau-q(D)$

Recall that $LM_{count}$ returns $o=0$ when the else condition (line 1) in
GenericDecider is satisfied. Therefore,

$\displaystyle Pr[o=0]$ $\displaystyle=Pr[|q(D)+\nu_{q}-q(D_{s})|\geq\tau]$
$\displaystyle\geq Pr[q(D)+\nu_{q}-q(D_{s})\leq-\tau]$
$\displaystyle=Pr[\nu_{q}\leq q(D_{s})-\tau-q(D)]$
$\displaystyle=1-Pr[\nu_{q}>q(D_{s})-\tau-q(D)]$
$\displaystyle>1-Pr[\nu_{q}\geq q(D_{s})-\tau-q(D)]$
$\displaystyle=1-\frac{1}{2}e^{-(q(D_{s})-\tau-q(D))\epsilon}~{}~{}\quad\text{(from
(\ref{eq:lap-geq}) with}$ $t=(q(D_{s})-\tau-q(D))\epsilon$) $\displaystyle\geq
1-\frac{1}{2}e^{-\tau\epsilon}~{}~{}\quad\text{(from (\ref{eq:4pt3b_tau}))}$
(26) $\displaystyle\geq 1-\delta~{}~{}\quad\text{(when
$\tau\geq\frac{1}{\epsilon}\ln{\frac{1}{2\delta}}$)}$

From (24) and (26), the upper bound of $\tau_{min}^{LM_{count},\delta}$
follows. ∎

###  A.3. Proof of Proposition 4.4

###### Proof.

Note that since $u$ is binary, $\Delta u\leq 1$. We show that $\Delta u=1$.
The global sensitivity equals the worst case change in the output of $u$ on
neighboring databases $D\approx D^{\prime}$ for $o\in\mathcal{R}=\\{0,1\\}$.
Consider an interval $\mathcal{I}$ such that $q(D)=p\in\mathcal{I}$ and
$q(D^{\prime})=p+1\not\in\mathcal{I}$ (as $q$ is a count query and $\Delta
q=1$). $u(D,D_{s},q,\tau,o=1)=1$, whereas $u(D^{\prime},D_{s},q,\tau,o=1)=0$.
Instead if $o=0$, the scores differ by $1$ again. Similarly for
$q(D)\not\in\mathcal{I}$ and $q(D^{\prime})\in\mathcal{I}$. Thus, $\Delta
u=1$. ∎

###  A.4. Proof of Proposition 4.5

###### Proof.

The global sensitivity equals the worst case change in the output of
$u^{\prime}$ on neighboring databases $D\approx D^{\prime}$ for
$o\in\mathcal{R}=\\{0,1\\}$. Let $q(D)=p$ and $q(D^{\prime})=p+1$, for an
integer $p$ (as $\Delta q=1$ for count query $q$). We break down the analysis
for $o=1$ as follows:

  1. (1)

If $q(D)$ and $q(D^{\prime})$ both satisfy (10), then the scores from
$u^{\prime}$ are equal.

  2. (2)

If $q(D)$ and $q(D^{\prime})$ both satisfy (13), then the scores from
$u^{\prime}$ differ by $1/2\tau$ because:

$\displaystyle|\frac{q(D)-(l-\tau)}{2\tau}-\frac{q(D^{\prime})-(l-\tau)}{2\tau}|=|\frac{q(D)-q(D^{\prime})}{2\tau}|$

which equals $1/2\tau$ because $|q(D)-q(D^{\prime})|=|p-(p+1)|=1$.

  3. (3)

If $q(D)$ and $q(D^{\prime})$ both satisfy (16), then the scores from
$u^{\prime}$ differ by $1/2\tau$ because:

$\displaystyle|1-\frac{q(D)-q(D_{s})}{2\tau}-\left(1-\frac{q(D^{\prime})-q(D_{s})}{2\tau}\right)|=|\frac{q(D)-q(D^{\prime})}{2\tau}|$

which equals $1/2\tau$ because $|q(D)-q(D^{\prime})|=|p-(p+1)|=1$.

  4. (4)

If $q(D)$ satisfies (10) and $q(D^{\prime})$ satisfies (13), then $q(D)\leq
l-\tau$ because $q(D)$ and $q(D^{\prime})$ differ by $1$ (given), and so the
scores from $u^{\prime}$ differ by less than $1/2\tau$. Similarly for when:
($i$) $q(D)$ satisfies (13) and $q(D^{\prime})$ satisfies (16), and ($ii$)
$q(D)$ satisfies (16) and $q(D^{\prime})$ satisfies (10).

The other case, i.e., $o=0$, is proven similarly. Hence, the worst case change
is $1/2\tau$ and the global sensitivity of $u^{\prime}$ equals $1/2\tau$. ∎

###  A.5. Proof of Proposition 4.7

###### Proof.

We analyze the two cases in Definition 3.4. $c$ is a positive constant
(Definition 2.10). Proposition 4.5 gives $\Delta u^{\prime}=1/2\tau$.

  1. (1)

Let $q(D)=q(D_{s})$. Here, the score assigned by $u^{\prime}$ to $o=0$ is $0$
and to $o=1$ is $1$ (by (13)). From Definition 2.10, we get

$\displaystyle Pr[o=0]=c\cdot e^{\epsilon\times 0\times\tau}\text{ and
}Pr[o=1]=c\cdot e^{\epsilon\times 1\times\tau}$ (27) $\displaystyle\implies$
$\displaystyle Pr[o=1]=\frac{e^{\epsilon\tau}}{1+e^{\epsilon\tau}}\geq
1-\delta~{}~{}\quad\text{(when
$\tau\geq\frac{1}{\epsilon}\ln{\frac{1-\delta}{\delta}}$)}$

  2. (2)

Let $q(D)\not\in(q(D_{s})-2\tau,q(D_{s})+2\tau)$. Without loss of generality,
let $q(D)\leq q(D_{s})-2\tau=l-\tau$. Here, the score assigned by $u^{\prime}$
to $o=0$ is $1$ and to $o=1$ is $0$ (by (10)). From Definition 2.10, we get

$\displaystyle Pr[o=o]=c\cdot e^{\epsilon\times 1\times\tau}\text{ and
}Pr[o=1]=c\cdot e^{\epsilon\times 0\times\tau}$ (28) $\displaystyle\implies$
$\displaystyle Pr[o=0]=\frac{e^{\epsilon\tau}}{1+e^{\epsilon\tau}}\geq
1-\delta~{}~{}\quad\text{(when
$\tau\geq\frac{1}{\epsilon}\ln{\frac{1-\delta}{\delta}}$)}$

From (27) and (28), the upper bound of $\tau_{min}^{EM_{count},\delta}$
follows. ∎

##  Appendix B Proofs from Section 5

###  B.1. Proof of Proposition 5.2

###### Proof.

Since $\nu_{q}\sim Lap(GS_{q}/\epsilon)$, bounds (3)-(5) become

(29) $\displaystyle Pr\left[\nu_{q}\geq
t\cdot\frac{GS_{q}}{\epsilon}\right]=\frac{e^{-t}}{2}$ (30) $\displaystyle
Pr\left[\nu_{q}\leq-t\cdot\frac{GS_{q}}{\epsilon}\right]=\frac{e^{-t}}{2}$
(31) $\displaystyle Pr\left[|\nu_{q}|\geq
t\cdot\frac{GS_{q}}{\epsilon}\right]=e^{-t}$

We analyze the two cases in Definition 3.4.

  1. (1)

Let $q(D)=q(D_{s})$. $LM_{sum}$ returns $o=1$ when the if condition (line 1)
in GenericDecider is satisfied. Therefore,

$\displaystyle Pr[o=1]$ $\displaystyle=Pr[|q(D)+\nu_{q}-q(D_{s})|<\tau]$
$\displaystyle=Pr[|\nu_{q}|<\tau]~{}~{}\quad\text{(since $q(D)=q(D_{s})$)}$
$\displaystyle=1-Pr[|\nu_{q}|\geq\tau]$
$\displaystyle=1-e^{-\tau\epsilon/GS_{q}}~{}~{}\quad\text{(from (\ref{eq:lap-
sum-mod}) with $t=\tau\epsilon/GS_{q}$)}$ (32) $\displaystyle\geq
1-\delta~{}~{}\quad\text{(when
$\tau\geq\frac{GS_{q}}{\epsilon}\ln{\frac{1}{\delta}}>\frac{GS_{q}}{\epsilon}\ln{\frac{1}{2\delta}}$)}$

  2. (2)

Let $q(D)\not\in(q(D_{s})-2\tau,q(D_{s})+2\tau)$. Without loss of generality,
suppose $q(D)\leq q(D_{s})-2\tau$, so

(33) $\displaystyle\tau\leq q(D_{s})-\tau-q(D)$

Recall that $LM_{sum}$ returns $o=0$ when the else condition (line 1) in
GenericDecider is satisfied. Therefore,

$\displaystyle Pr[o=0]$ $\displaystyle=Pr[|q(D)+\nu_{q}-q(D_{s})|\geq\tau]$
$\displaystyle\geq Pr[q(D)+\nu_{q}-q(D_{s})\leq-\tau]$
$\displaystyle=Pr[\nu_{q}\leq q(D_{s})-\tau-q(D)]$
$\displaystyle=1-Pr[\nu_{q}>q(D_{s})-\tau-q(D)]$
$\displaystyle>1-Pr[\nu_{q}\geq q(D_{s})-\tau-q(D)]$
$\displaystyle=1-\frac{1}{2}e^{-(q(D_{s})-\tau-q(D))\cdot\frac{\epsilon}{GS_{q}}}~{}~{}\quad\text{(from
(\ref{eq:lap-sum-geq}) with}$
$t=(q(D_{s})-\tau-q(D))\cdot\frac{\epsilon}{GS_{q}}$) $\displaystyle\geq
1-\frac{1}{2}e^{-\tau\epsilon/GS_{q}}~{}~{}\quad\text{(from
(\ref{eq:5pt2b_tau}))}$ (34) $\displaystyle\geq 1-\delta~{}~{}\quad\text{(when
$\tau\geq\frac{GS_{q}}{\epsilon}\ln{\frac{1}{2\delta}}$)}$

From (32) and (34), the upper bound of $\tau_{min}^{LM_{sum},\delta}$ follows.
∎

###  B.2. R2T: Validity of Truncation Function and Known Confidence Bound

We are given a SUM query $q$ on (aggregate) attribute $A_{i}$. Recall from
Section 5.2 that we use a simple truncation function which removes tuples in
$D$ with $A_{i}$ value greater than $t_{j}=2^{j}$, for $j=1$ to
$\log(GS_{q})$. $q(D,t_{j})$ denotes the output of running $q$ on the
corresponding truncated database. (Dong et al., 2022) lays down three
properties that a valid truncation function must satisfy. We show next that
the simple truncation function meets the criteria.

###### Proposition B.1.

The simple truncation function satisfies the properties required by R2T (as
stated below) and is valid:

  1. (1)

For any $t_{j}$, the global sensitivity of $q(\cdot,t_{j})\leq t_{j}$.

  2. (2)

For any $t_{j}$, $q(D,t_{j})\leq q(D)$.

  3. (3)

For any $D$, $\exists$ non-negative integer $t^{*}(D)\leq GS_{q}$ such that
$\forall t_{j}\geq t^{*}(D),q(D,t_{j})=q(D)$.

###### Proof.

The simple truncation function is valid because:

  1. (1)

For any $t_{j}$, the worst-case change in the output of the truncated sum over
databases $D\approx D^{\prime}$ occurs when we add or remove a tuple with
$A_{i}=t_{j}$. Larger values get discarded.

  2. (2)

For any $t_{j}$, the result of applying $q$ on the truncated database cannot
exceed $q(D)$ because we remove at least $0$ tuples in the truncated database.

  3. (3)

$t^{*}(D)=GS_{q}$ satisfies the condition. $DS_{q,D}$ (Definition 2.4) is
another such value and is a private quantity.

∎

Theorem $5.1$ in (Dong et al., 2022) states that:

$\displaystyle Pr\left[q(D)\geq\tilde{q}(D)\geq
q(D)-4\log(GS_{q})\ln{\left(\frac{\log(GS_{q})}{\beta}\right)}\frac{t^{*}}{\epsilon}\right]\geq
1-\beta$

where $\tilde{q}(D)$ is R2T’s final estimate for $q(D)$, $t^{*}$ is as given
in Proposition B.1 and $0<\beta<1$. We apply this with $t^{*}=DS_{q,D}$ in
(19).

###  B.3. Proof of Proposition 5.5

###### Proof.

We analyze the two cases in Definition 3.4.

  1. (1)

Let $q(D)=q(D_{s})$. $R2T_{sum}$ returns $o=1$ when the if condition (line 1)
in GenericDecider is satisfied. Therefore,

$\displaystyle Pr[o=1]$ $\displaystyle=Pr[|\tilde{q}(D)-q(D_{s})|<\tau]$
$\displaystyle=Pr[|\tilde{q}(D)-q(D)|<\tau]~{}~{}\quad\text{(since
$q(D)=q(D_{s})$)}$ (35) $\displaystyle\geq 1-\delta$

from (19) for $\beta=\delta$ and $\tau\geq
4\log(GS_{q})\ln{\left(\frac{\log(GS_{q})}{\delta}\right)}\frac{DS_{q,D}}{\epsilon}$.

  2. (2)

Let $q(D)\not\in(q(D_{s})-2\tau,q(D_{s})+2\tau)$. Recall that $R2T_{sum}$
returns $o=0$ when the else condition (line 1) in GenericDecider is satisfied.
If $q(D)\leq q(D_{s})-2\tau=l-\tau$, then

$\displaystyle Pr[o=0]$ $\displaystyle=Pr[|\tilde{q}(D)-q(D_{s})|\geq\tau]$
$\displaystyle\geq Pr[-\tau\geq\tilde{q}(D)-q(D_{s})]$
$\displaystyle=Pr[\tilde{q}(D)\leq l]~{}~{}\quad\text{(since
$l=q(D_{s})-\tau$)}$ $\displaystyle\geq Pr[\tilde{q}(D)\leq
q(D)]~{}~{}\quad\text{(since $q(D)\leq l-\tau<l$)}$ (36) $\displaystyle\geq
1-\delta~{}~{}\quad\text{(from (\ref{eq:R2T_thm5-1}) with $\beta=\delta$)}$

Otherwise, if $q(D)\geq q(D_{s})+2\tau=r+\tau$, then

$\displaystyle Pr[o=0]$ $\displaystyle=Pr[|\tilde{q}(D)-q(D_{s})|\geq\tau]$
$\displaystyle\geq Pr[\tilde{q}(D)-q(D_{s})\geq\tau]$
$\displaystyle=Pr[\tilde{q}(D)\geq r]~{}~{}\quad\text{(since
$r=q(D_{s})+\tau$)}$ $\displaystyle\geq Pr[\tilde{q}(D)\geq
q(D)-\tau]~{}~{}\quad\text{(given $r\leq q(D)-\tau$)}$ (37) $\displaystyle\geq
1-\delta$

from (19) for $\beta=\delta$ and $\tau\geq
4\log(GS_{q})\ln{\left(\frac{\log(GS_{q})}{\delta}\right)}\frac{DS_{q,D}}{\epsilon}$.

From (35), (36) and (37), the upper bound of $\tau_{min}^{R2T_{sum},\delta}$
follows. ∎

###  B.4. SVT: Noise Scale in the Laplace Distribution for Monotonic Queries
and Proof of Theorem 5.8

For monotonic queries (Definition 5.7), Theorem $3$ (Lyu et al., 2017) shows
that a factor of $2$ can be saved in the scale of the Laplace distribution
used to sample independent noise for each noisy query answer. It analyzes
Algorithm $7$ (Lyu et al., 2017) that returns a DP estimate for each query
with a ‘yes’ answer (noisy query answer exceeded noisy threshold), which
consumes additional privacy budget as simply returning the already computed
noisy query answer violates $\epsilon$-DP. Algorithm $7$ (Lyu et al., 2017)
divides the given privacy budget into $\epsilon_{1}$ for the noisy thresholds,
$\epsilon_{2}$ for the noisy query answers, and $\epsilon_{3}$ for any DP
estimates to be returned. However, we note that this analysis does not
directly apply to our application of SVT in Algorithm 2 (or Algorithm 4)
because we do not return any DP estimates. We set
$\epsilon_{1}=\epsilon_{2}=\epsilon/2$. Below, we prove Theorem 5.8. We note
that this proof is adapted from the proof of Theorem 3 (Lyu et al., 2017), but
we repeat the steps here for the sake of completeness.

###### Proof.

Let $\top_{1}$ and $\top_{2}$ denote the ‘yes’ answers from SVT (Lyu et al.,
2017) in Algorithm 2, i.e., when the noisy query answer exceeds the noisy
threshold in lines 2 and 2, respectively. Let $\bot_{1}$ and $\bot_{2}$,
respectively, denote when these checks fail. Algorithm 2 stops as soon as
either: ($i$) check in line 2 passes, so the sequence of ‘yes’/‘no’ answers is
$\bot_{1},\ldots,\bot_{1},\top_{1}$, or ($ii$) check in line 2 passes, so the
sequence of ‘yes’/‘no’ answers is
$\bot_{1},\ldots,\bot_{1},\bot_{2},\ldots,\bot_{2},\top_{2}$. We denote this
sequence of ‘yes’/‘no’ answers by a string $a$, with length $|a|$.

Let $\mathbb{I}_{\top_{1}}=\\{i:a_{i}=\top_{1}\\}$, where $a_{i}$ is the
$i$-th character in $a$. Similarly
$\mathbb{I}_{\top_{2}},\mathbb{I}_{\bot_{1}}$, and $\mathbb{I}_{\bot_{2}}$ for
$\top_{2},\bot_{1}$, and $\bot_{2}$, respectively. Note that for ($i$),
$\mathbb{I}_{\bot_{1}}=\\{1,2,\ldots,|a|-1\\}$,
$\mathbb{I}_{\top_{1}}=\\{|a|\\}$, and
$\mathbb{I}_{\bot_{2}}=\mathbb{I}_{\top_{2}}=\emptyset$. Note that for ($ii$),
$\mathbb{I}_{\bot_{1}}\cup\mathbb{I}_{\bot_{2}}=\\{1,2,\ldots,|a|-1\\}$,
$\mathbb{I}_{\top_{1}}=\emptyset$, and $\mathbb{I}_{\top_{2}}=\\{|a|\\}$.

Motivated by (Lyu et al., 2017), let
$f_{j}^{(1)}(D,z)=Pr[q_{j}(D)+\nu_{j}<r/t_{j}+z]$ (not satisfying the
condition for line 2 in Algorithm 2) and
$g_{j}^{(1)}(D,z)=Pr[q_{j}(D)+\nu_{j}\geq r/t_{j}+z]$ (satisfying the
condition for line 2 in Algorithm 2), where the superscript represents the
$1$st for loop (line 2 in Algorithm 2) and $z$ represents the different values
$\rho$ can take (line 2 in Algorithm 2). Similarly, $f_{j}^{(2)}$ and
$g_{j}^{(2)}$ denote the two events, respectively, when threshold equals
$(l+1)/t_{j}$ instead of $r/t_{j}$ ($2$nd for loop in line 2 in Algorithm 2).

We denote by $\Delta$ the global sensitivity of the queries used:
$q_{j}(D)=q(D,t_{j})/t_{j}$, for $t_{j}=2^{j},j=1$ to $\log(GS_{q})$. Recall
from Section 5.2 that $q(D,t_{j})$ is a sum query on the truncated database
obtained by removing tuples in $D$ with $A_{i}$ value greater than $t_{j}$.
The global sensitivity of $q(\cdot,t_{j})$ (i.e., $q$ on any database
truncated with threshold $t_{j}$) is $t_{j}$ as larger values are discarded.
Hence, the worst case change in the output of $q_{j}(\cdot)$ on $D\approx
D^{\prime}$ is $1$ due to division by $t_{j}$.

When $a$ satisfies ($i$):  Given that $a=\bot_{1},\ldots,\bot_{1},\top_{1}$.
Here, $Pr[\text{sequence of `yes'/`no' answers in
}SVT_{sum}(q,D,D_{s},\tau,\epsilon)=a]$111Since $\rho\sim
Lap(\frac{1}{\epsilon/2})$ (line 2 in Algorithm 2) is drawn from a continuous
distribution with range $(-\infty,\infty)$, we use integration instead of sum.

$\displaystyle=$
$\displaystyle\int_{-\infty}^{\infty}Pr[((q_{1}(D)+\nu_{1}<r/t_{1}+\rho)\land...\land(q_{|a|-1}(D)+\nu_{|a|-1}<$
$\displaystyle r/t_{|a|-1}+\rho)\land(q_{|a|}(D)+\nu_{|a|}\geq
r/t_{|a|}+\rho))~{}|~{}\rho=z]Pr[\rho=z]dz$

(38)
$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z)\right)g_{|a|}^{(1)}(D,z)dz$

conditioning on $\rho$ taking value $z$, and then from the conditional
independence of the i.i.d. Laplace noise terms $\nu_{j}$ given $\rho=z$.

Now, we examine the two cases for monotonic queries, i.e., a sequence of
queries for which all answers that change in going from $D$ to a neighboring
database $D^{\prime}$ (i.e. $D\approx D^{\prime}$) either all increase or all
decrease (Definition 5.7):

  1. (1)

$\forall j,~{}q(D,t_{j})\geq q(D^{\prime},t_{j})$, where $D\approx
D^{\prime}$.

  2. (2)

$\forall j,~{}q(D,t_{j})\leq q(D^{\prime},t_{j})$, where $D\approx
D^{\prime}$.

Firstly, suppose $\forall j,~{}q(D,t_{j})\geq q(D^{\prime},t_{j})$, where
$D\approx D^{\prime}$. Thus,

(39) $\displaystyle\forall j,~{}q_{j}(D)\geq
q_{j}(D^{\prime})~{}~{}\quad\text{(dividing both sides by $t_{j}$)}$

Since the global sensitivity of $q_{j}$ is $\Delta=1$, we also have

(40) $\displaystyle\forall j,~{}q_{j}(D)\leq q_{j}(D^{\prime})+\Delta$

Using (39) we get,

$\displaystyle f_{j}^{(1)}(D,z)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}<r/t_{j}+z]$ (41) $\displaystyle\leq
Pr[q_{j}(D^{\prime})+\nu_{j}<r/t_{j}+z]=f_{j}^{(1)}(D^{\prime},z)$

Next, we prove a useful property of the Laplace distribution for $\nu_{j}\sim
Lap(\Delta/\epsilon_{2})$, namely: $\forall y,~{}Pr[\nu_{j}=y]\leq
e^{\epsilon_{2}}Pr[\nu_{j}=y+\Delta]$.

$\displaystyle|y+\Delta|$ $\displaystyle\leq|y|+\Delta~{}~{}\quad\text{(since
$\Delta=1$)}$ $\displaystyle\implies$ $\displaystyle
e^{|y+\Delta|\frac{\epsilon_{2}}{\Delta}}$ $\displaystyle\leq
e^{(|y|+\Delta)\frac{\epsilon_{2}}{\Delta}}$ $\displaystyle\implies$
$\displaystyle e^{|y+\Delta|\frac{\epsilon_{2}}{\Delta}}$ $\displaystyle\leq
e^{|y|\frac{\epsilon_{2}}{\Delta}}\cdot e^{\epsilon_{2}}$
$\displaystyle\implies$ $\displaystyle e^{-|y|/b}$ $\displaystyle\leq
e^{-|y+\Delta|/b}\cdot e^{\epsilon_{2}}~{}~{}\quad\text{(for
$b=\Delta/\epsilon_{2}$)}$ (42) $\displaystyle\implies$ $\displaystyle
Pr[\nu_{j}=y]$ $\displaystyle\leq
e^{\epsilon_{2}}Pr[\nu_{j}=y+\Delta]~{}~{}\quad\text{(since $\nu_{j}\sim
Lap(\Delta/\epsilon_{2})$)}$

Furthermore,

$\displaystyle g_{j}^{(1)}(D,z)$ $\displaystyle=Pr[q_{j}(D)+\nu_{j}\geq
r/t_{j}+z]$ $\displaystyle\leq Pr[q_{j}(D^{\prime})+\Delta+\nu_{j}\geq
r/t_{j}+z]~{}~{}\quad\text{(from (\ref{equn:case1-GS-1}))}$
$\displaystyle=Pr[q_{j}(D^{\prime})+\nu_{j}\geq r/t_{j}+z-\Delta]$
$\displaystyle\leq e^{\epsilon_{2}}Pr[q_{j}(D^{\prime})+\nu_{j}\geq
r/t_{j}+z]~{}~{}\quad\text{(from (\ref{equn:LapDistr-Property-nuj}))}$ (43)
$\displaystyle=e^{\epsilon_{2}}g_{j}^{(1)}(D^{\prime},z)$

So, $Pr[\text{sequence of `yes'/`no' answers in
}SVT_{sum}(q,D,D_{s},\tau,\epsilon)=a]$

$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z)\right)g_{|a|}^{(1)}(D,z)dz$
$\displaystyle\leq\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D^{\prime},z)\right)e^{\epsilon_{2}}g_{|a|}^{(1)}(D^{\prime},z)dz$
$\displaystyle=e^{\epsilon_{2}}Pr[\text{sequence of `yes'/`no' answers in }$
(44) $\displaystyle\hskip
34.1433ptSVT_{sum}(q,D^{\prime},D_{s},\tau,\epsilon)=a]$

Now, suppose $\forall j,q(D,t_{j})\leq q(D^{\prime},t_{j})$, where $D\approx
D^{\prime}$. Thus,

(45) $\displaystyle\forall j,~{}q_{j}(D)\leq
q_{j}(D^{\prime})~{}~{}\quad\text{(dividing both sides by $t_{j}$)}$

Since the global sensitivity of $q_{j}$ is $\Delta=1$, we also have

(46) $\displaystyle\forall j,~{}q_{j}(D)\geq q_{j}(D^{\prime})-\Delta$

Using (46) we get,

$\displaystyle f_{j}^{(1)}(D,z-\Delta)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}<r/t_{j}+z-\Delta]$ $\displaystyle\leq
Pr[q_{j}(D^{\prime})-\Delta+\nu_{j}<r/t_{j}+z-\Delta]$ (47)
$\displaystyle=f_{j}^{(1)}(D^{\prime},z)$

Furthermore,

$\displaystyle g_{j}^{(1)}(D,z-\Delta)$ $\displaystyle=Pr[q_{j}(D)+\nu_{j}\geq
r/t_{j}+z-\Delta]$ $\displaystyle\leq Pr[q_{j}(D^{\prime})+\nu_{j}\geq
r/t_{j}+z-\Delta]~{}~{}\quad\text{(from (\ref{equn:case2}))}$
$\displaystyle\leq e^{\epsilon_{2}}Pr[q_{j}(D^{\prime})+\nu_{j}\geq
r/t_{j}+z]~{}~{}\quad\text{(from (\ref{equn:LapDistr-Property-nuj}))}$ (48)
$\displaystyle=e^{\epsilon_{2}}g_{j}^{(1)}(D^{\prime},z)$

Since $\rho\sim Lap(\Delta/\epsilon_{1})$, by the property of the Laplace
distribution

(49) $\displaystyle\forall z,~{}Pr[\rho=z]\leq
e^{\epsilon_{1}}Pr[\rho=z+\Delta]$

So, $Pr[\text{sequence of `yes'/`no' answers in
}SVT_{sum}(q,D,D_{s},\tau,\epsilon)=a]$

$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z)\right)g_{|a|}^{(1)}(D,z)dz$
$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z-\Delta]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z-\Delta)\right)g_{|a|}^{(1)}(D,z-\Delta)dz$
(by change of integration variable from $z$ to $z-\Delta$)
$\displaystyle\leq\int_{-\infty}^{\infty}e^{\epsilon_{1}}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D^{\prime},z)\right)e^{\epsilon_{2}}g_{|a|}^{(1)}(D^{\prime},z)dz$
$\displaystyle=e^{\epsilon_{1}+\epsilon_{2}}Pr[\text{sequence of `yes'/`no'
answers in }$ (50) $\displaystyle\hskip
45.5244ptSVT_{sum}(q,D^{\prime},D_{s},\tau,\epsilon)=a]$

When $a$ satisfies (ii): Given that
$a=\bot_{1},\ldots,\bot_{1},\bot_{2},\ldots,\bot_{2},\top_{2}$.
$Pr[\text{sequence of `yes'/`no' answers in
}SVT_{sum}(q,D,D_{s},\tau,\epsilon)=a]$222Since $\rho\sim
Lap(\frac{1}{\epsilon/2})$ (line 2 in Algorithm 2) is drawn from a continuous
distribution with range $(-\infty,\infty)$, we use integration instead of sum.

(51)
$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z)\right)\left(\prod_{j\in\mathbb{I}_{\bot_{2}}}f_{j}^{(2)}(D,z)\right)g_{|a|}^{(2)}(D,z)dz$

conditioning on $\rho$ taking value $z$, and then from the conditional
independence of the i.i.d. Laplace noise terms $\nu_{j}$ given $\rho=z$.

Again, we examine the two cases for monotonic queries. Firstly, suppose
$\forall j,~{}q(D,t_{j})\geq q(D^{\prime},t_{j})$, where $D\approx
D^{\prime}$. Using (39) we get,

$\displaystyle f_{j}^{(1)}(D,z)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}<r/t_{j}+z]$ (52) $\displaystyle\leq
Pr[q_{j}(D^{\prime})+\nu_{j}<r/t_{j}+z]=f_{j}^{(1)}(D^{\prime},z)$
$\displaystyle f_{j}^{(2)}(D,z)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}<(l+1)/t_{j}+z]$ (53) $\displaystyle\leq
Pr[q_{j}(D^{\prime})+\nu_{j}<(l+1)/t_{j}+z]=f_{j}^{(2)}(D^{\prime},z)$
$\displaystyle g_{j}^{(2)}(D,z)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}\geq(l+1)/t_{j}+z]$ $\displaystyle\leq
Pr[q_{j}(D^{\prime})+\Delta+\nu_{j}\geq(l+1)/t_{j}+z]~{}~{}\quad\text{(from
(\ref{equn:case1-GS-1}))}$
$\displaystyle=Pr[q_{j}(D^{\prime})+\nu_{j}\geq(l+1)/t_{j}+z-\Delta]$
$\displaystyle\leq
e^{\epsilon_{2}}Pr[q_{j}(D^{\prime})+\nu_{j}\geq(l+1)/t_{j}+z]~{}~{}\quad\text{(from
(\ref{equn:LapDistr-Property-nuj}))}$ (54)
$\displaystyle=e^{\epsilon_{2}}g_{j}^{(2)}(D^{\prime},z)$

So, $Pr[\text{sequence of `yes'/`no' answers in
}SVT_{sum}(q,D,D_{s},\tau,\epsilon)=a]$

$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z)\right)\left(\prod_{j\in\mathbb{I}_{\bot_{2}}}f_{j}^{(2)}(D,z)\right)g_{|a|}^{(2)}(D,z)dz$
$\displaystyle\leq\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D^{\prime},z)\right)\left(\prod_{j\in\mathbb{I}_{\bot_{2}}}f_{j}^{(2)}(D^{\prime},z)\right)\cdot$
$\displaystyle\hskip 34.1433pte^{\epsilon_{2}}g_{|a|}^{(2)}(D^{\prime},z)dz$
$\displaystyle=e^{\epsilon_{2}}Pr[\text{sequence of `yes'/`no' answers in }$
(55) $\displaystyle\hskip
34.1433ptSVT_{sum}(q,D^{\prime},D_{s},\tau,\epsilon)=a]$

Now, suppose $\forall j,q(D,t_{j})\leq q(D^{\prime},t_{j})$, where $D\approx
D^{\prime}$. Using (46),

$\displaystyle f_{j}^{(1)}(D,z-\Delta)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}<r/t_{j}+z-\Delta]$ $\displaystyle\leq
Pr[q_{j}(D^{\prime})-\Delta+\nu_{j}<r/t_{j}+z-\Delta]$ (56)
$\displaystyle=f_{j}^{(1)}(D^{\prime},z)$ $\displaystyle
f_{j}^{(2)}(D,z-\Delta)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}<(l+1)/t_{j}+z-\Delta]$ $\displaystyle\leq
Pr[q_{j}(D^{\prime})-\Delta+\nu_{j}<(l+1)/t_{j}+z-\Delta]$ (57)
$\displaystyle=f_{j}^{(2)}(D^{\prime},z)$

Furthermore,

$\displaystyle g_{j}^{(2)}(D,z-\Delta)$
$\displaystyle=Pr[q_{j}(D)+\nu_{j}\geq(l+1)/t_{j}+z-\Delta]$
$\displaystyle\leq
Pr[q_{j}(D^{\prime})+\nu_{j}\geq(l+1)/t_{j}+z-\Delta]~{}~{}\text{(from
(\ref{equn:case2}))}$ $\displaystyle\leq
e^{\epsilon_{2}}Pr[q_{j}(D^{\prime})+\nu_{j}\geq(l+1)/t_{j}+z]~{}~{}\text{(from
(\ref{equn:LapDistr-Property-nuj}))}$ (58)
$\displaystyle=e^{\epsilon_{2}}g_{j}^{(2)}(D^{\prime},z)$

Recall from (49) that $\forall z,~{}Pr[\rho=z]\leq
e^{\epsilon_{1}}Pr[\rho=z+\Delta]$. So, $Pr[\text{sequence of `yes'/`no'
answers in }SVT_{sum}(q,D,D_{s},\tau,\epsilon)=a]$

$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z)\right)\left(\prod_{j\in\mathbb{I}_{\bot_{2}}}f_{j}^{(2)}(D,z)\right)g_{|a|}^{(2)}(D,z)dz$
$\displaystyle=\int_{-\infty}^{\infty}Pr[\rho=z-\Delta]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D,z-\Delta)\right)\left(\prod_{j\in\mathbb{I}_{\bot_{2}}}f_{j}^{(2)}(D,z-\Delta)\right)\cdot$
$\displaystyle g_{|a|}^{(2)}(D,z-\Delta)dz~{}~{}\text{(by change of
integration variable from $z$ to $z-\Delta$)}$
$\displaystyle\leq\int_{-\infty}^{\infty}e^{\epsilon_{1}}Pr[\rho=z]\left(\prod_{j\in\mathbb{I}_{\bot_{1}}}f_{j}^{(1)}(D^{\prime},z)\right)\left(\prod_{j\in\mathbb{I}_{\bot_{2}}}f_{j}^{(2)}(D^{\prime},z)\right)\cdot$
$\displaystyle\hskip 34.1433pte^{\epsilon_{2}}g_{|a|}^{(2)}(D^{\prime},z)dz$
$\displaystyle=e^{\epsilon_{1}+\epsilon_{2}}Pr[\text{sequence of `yes'/`no'
answers in }$ (59) $\displaystyle\hskip
45.5244ptSVT_{sum}(q,D^{\prime},D_{s},\tau,\epsilon)=a]$

∎

The sequence of ‘yes’/‘no’ answers for Algorithm 4 corresponds to
$a=\bot_{1},\ldots,\bot_{1},\top_{1}$ in the above proof. In Algorithm 4, SVT
is run with two-thirds of $\epsilon^{\prime}$, its input privacy budget, and
$\epsilon_{1}=\epsilon_{2}=\epsilon^{\prime}/3$. By sequential composition
(Proposition 2.6), Algorithm 4 is $\epsilon^{\prime}$-DP.

###  B.5. Improvement on $SVT_{sum}$ to lower error

Recall from (1) that $\mathcal{I}=(l,r)=(q(D_{s})-\tau,q(D_{s})+\tau)$.
$SVT_{sum}$ incurs high error if $q(D)$ and $r$ (or $l$) are close because in
the later iterations where $t_{j}$ values are large, the check is easily
influenced by noise. Note that $\forall t_{k}\geq DS_{q,D},q(D,t_{k})=q(D)$,
where $DS_{q,D}$ is the downward local sensitivity (Definition 2.4). Thus, in
Algorithm 4, we bound $t_{j}$ by a private bound for $DS_{q,D}$ (Chen et al.,
2016). In the loops in lines 2 and 2 in Algorithm 2, $t_{j}$ is bounded by
(the next largest power of $2$ from) $GS_{q}$. Instead, in the improved
$SVT_{sum}$, we use a private upper bound of $DS_{q,D}$ to reduce the noise in
Algorithm 4. This bound is still $GS_{q}$ in the worst case, but can take
lower values. To achieve this, we spend $\epsilon^{\prime}$ equal to a third
of $SVT_{sum}$’s privacy budget $\epsilon$ on Algorithm 4. The remaining
$2\epsilon/3$ of the privacy budget is used in Algorithm 2, hence each step in
$SVT_{sum}$ uses $\epsilon/3$ instead of $\epsilon/2$.

Since the number of tuples $n$ in $D$ satisfying $\varphi$ (the predicates in
the WHERE clause in $q$) is private, we spend $\epsilon^{\prime}/3$ of
Algorithm 4’s privacy budget $\epsilon^{\prime}$ to compute a DP estimate for
$n$ (line 4). SVT (loop in line 4) is run with the remaining privacy budget,
where $\epsilon^{\prime}/3$ is consumed by $\rho$ that is used to get noisy
thresholds for all queries and $\epsilon^{\prime}/3$ is used to add
independent Laplace noise to query answers. Query $q_{j}^{c}(D)$ computes the
number of tuples in $D$ that satisfy $\varphi$ and have $A_{i}$ value less
than or equal to $2^{j}$, for $j=1$ to $\lceil\log(GS_{q})\rceil$. Note that
$q_{j}^{c}(D)$s (line 4) are monotonic (Definition 5.7), which helps save a
factor of $2$ in the noise scale for $\nu_{j}^{c}$ (Lyu et al., 2017)
(discussed further in Appendix B.4). The return value becomes the largest $j$
used in lines 2 and 2 in Algorithm 2.

Input : $q$ \- SUM query, $D$ \- private database, $\epsilon^{\prime}$ \-
privacy budget (= $\epsilon/3$), $\theta$ \- fraction in $(0,1)$ (default
$0.95$)

Output : Private bound for $DS_{q,D}$

1

2 Function  _PrivateBoundDS(_$q,D,\epsilon^{\prime},\theta$_)_:

3 $n\leftarrow$ number of tuples in $D$ that satisfy $\varphi$ in $q$;

4 $\nu_{q}\leftarrow Lap(\frac{1}{\epsilon^{\prime}/3}),\tilde{n}\leftarrow
n+\nu_{q}$;

5 $A_{i}\leftarrow$ aggregate attribute in $q$;

6 $\rho\leftarrow Lap(\frac{1}{\epsilon^{\prime}/3})$;

7 for  _$j\in\\{1,2,3,\ldots,\lceil\log(GS_{q})\rceil\\}$_ do

8 $\nu_{j}^{c}\sim Lap(\frac{1}{\epsilon^{\prime}/3})$,
$q_{j}^{c}(D)\leftarrow$ SELECT COUNT(*) FROM $D$ WHERE $\varphi$ AND
$A_{i}\leq 2^{j}$;

9 if  _$q_{j}^{c}(D)+\nu_{j}^{c}\geq\theta*\tilde{n}+\rho$_ then

10 return $j$;

11

12

13 return $\lceil\log(GS_{q})\rceil$;

14

Algorithm 4 Private bound for $DS_{q,D}$

By sequential composition and post-processing (Proposition 2.6), the following
holds:

###### Observation B.2.

Algorithm 4 satisfies $\epsilon/3$-DP, and consequently the improved
$SVT_{sum}$ (with Algorithm 4) satisfies $\epsilon$-DP.

###  B.6. Empirical Error Analysis of $SVT_{sum}$

Our experiments suggest that $SVT_{sum}$’s error may not benefit from
increasing $\epsilon$ when $\tau$ is small and the query answer of the given
SUM query $q$ on $D$ is inside the interval $\mathcal{I}$ (as defined in (1)).
We find that as $\tau$ increases, error decreases more noticeably.

For several queries such as $q_{13}$ to $q_{18}$, $SVT_{sum}$’s error was in
between that of $LM_{sum}$’s error and $R2T_{sum}$’s error when $\tau$ was
varied. $SVT_{sum}$’s error was comparable to that of $R2T_{sum}$’s error for
$q_{19}$ with the third largest output on $D$ and $DS_{q,D}=276799$
(Definition 2.4). Queries $q_{20}$ and $q_{21}$ have output greater than
$685M$, and we saw that the error decreased quicker, i.e., for smaller $\tau$
values, but stayed comparable to or worse than $R2T_{sum}$’s error. The
$DS_{q,D}$ values for $q_{20}$ and $q_{21}$ are $403353$ and $500000$,
respectively, whereas the bound $GS_{q}$ on the global sensitivity is
$500000$. Observe that this gap is not large.

##  Appendix C Proofs from Section 6

###  C.1. Error Analysis of $EM_{med}$

###### Proposition C.1.

Given a private database $D$, synthetic database $D_{s}$, MEDIAN query $q$ on
aggregate attribute $A_{i}$, distance bound $\tau$, and privacy budget
$\epsilon$. Interval $\mathcal{I}=(l,r)=(q(D_{s})-\tau,q(D_{s})+\tau)$ (1).
$EM_{med}$ satisfies the following:

  1. (1)

If $q(D)\not\in\mathcal{I}$ but $o=1$, then $err(\cdot)$ equals

$\sum\limits_{e\in dom(A_{i})\cap\mathcal{I}}e^{\epsilon
u(D,e)/2}/\sum\limits_{e\in dom(A_{i})}e^{\epsilon u(D,e)/2}$

  2. (2)

If $q(D)\in\mathcal{I}$ but $o=0$, then $err(\cdot)$ equals

$\sum\limits_{e\in dom(A_{i})\setminus\mathcal{I}}e^{\epsilon
u(D,e)/2}/\sum\limits_{e\in dom(A_{i})}e^{\epsilon u(D,e)/2}$

###### Proof.

Recall from Definition 2.10 that the Exponential Mechanism (EM) picks an
element $e$ in the output space $\mathcal{R}$ with probability given by
$c\cdot e^{\frac{\epsilon u(D,e)}{2\Delta u}}$, where $u(D,e)$ is the utility
of $e\in\mathcal{R}$ on $D$ and $c$ is a positive constant. $EM_{med}$ runs
GenericDecider with the EM as DPNoisy, with additional parameters
$\mathcal{R}=dom(A_{i})$ and score function
$u(D,e)=-|rank_{\varphi}(D,e)-\frac{n^{\prime}}{2}|$, $\forall
e\in\mathcal{R}$ and $n^{\prime}$ equal to the number of tuples in $D$
satisfying $\varphi$ (WHERE clause) in the given MEDIAN query $q$. The
sensitivity of the score function equals $1$ because rank of any $e$ either
stays the same or changes in the same direction as $n^{\prime}$ on
$D^{\prime}\approx D$.

For ($1$): Given that $q(D)\not\in\mathcal{I}$ but $o=1$. Note that
GenericDecider returns $o=1$ when the condition in line 1 is met, i.e., when
the EM (i.e. $\textnormal{{DPNoisy}}(\cdot)$) uses $e\in
dom(A_{i})\cap\mathcal{I}$ as the noisy estimate so that $|e-q(D_{s})|<\tau$.
The error (i.e. probability of this happening) is given by

(60) $\displaystyle\sum\limits_{e\in dom(A_{i})\cap\mathcal{I}}c\cdot
e^{\epsilon u(D,e)/2}$

We know that

(61) $\displaystyle\sum\limits_{e\in dom(A_{i})}c\cdot e^{\epsilon
u(D,e)/2}=1$

Therefore, $err(\cdot)$ equals

(62) $\displaystyle\sum\limits_{e\in dom(A_{i})\cap\mathcal{I}}e^{\epsilon
u(D,e)/2}/\sum\limits_{e\in dom(A_{i})}e^{\epsilon u(D,e)/2}$

For ($2$): Given that $q(D)\in\mathcal{I}$ but $o=0$. Note that GenericDecider
returns $o=0$ when the condition in line 1 is unmet, i.e., when the EM (i.e.
$\textnormal{{DPNoisy}}(\cdot)$) uses $e\in dom(A_{i})\setminus\mathcal{I}$ as
the noisy estimate so that $|e-q(D_{s})|\geq\tau$. The error (i.e. probability
of this happening) is given by

(63) $\displaystyle\sum\limits_{e\in dom(A_{i})\setminus\mathcal{I}}c\cdot
e^{\epsilon u(D,e)/2}$

We know that

(64) $\displaystyle\sum\limits_{e\in dom(A_{i})}c\cdot e^{\epsilon
u(D,e)/2}=1$

Therefore, $err(\cdot)$ equals

(65) $\displaystyle\sum\limits_{e\in
dom(A_{i})\setminus\mathcal{I}}e^{\epsilon u(D,e)/2}/\sum\limits_{e\in
dom(A_{i})}e^{\epsilon u(D,e)/2}$

∎

###  C.2. Empirical Analyses and Comparison of Errors of $Hist_{med}$ &
$EM_{med}$

Empirical Error Analysis of $EM_{med}$. Let us revisit the empirical analysis
for $EM_{med}$ from Section 7. For $q_{22}$ and $q_{29}$, the support, i.e.,
tuples in $D$ that satisfy the predicates in the WHERE clause, is large. As a
result, the probability distribution used to sample the noisy estimate for the
median is more concentrated around the correct value. The opposite is true for
$q_{23}$ and $q_{28}$. We see error decrease as $\tau$ increases. When
$\epsilon$ increases, the variance of the probability distribution used to
sample the noisy estimate in $EM_{med}$ decreases. $EM_{med}$’s error has a
decreasing trend except for $q_{29}$ because the scores are negatives numbers
with large magnitudes due to the support being large (Definition 2.10).

Empirical Error Analysis of $Hist_{med}$. Recall that $n^{\prime}$ is the
number of tuples in $D$ that satisfy $\varphi$ (WHERE clause) in the given
MEDIAN query $q$. Our experiments suggest that when the gap between $q_{1}(D)$
and the majority, i.e., $\lceil\frac{n^{\prime}}{2}\rceil$, is large in
comparison to the noise scales (in the Laplace distributions) used to get the
respective noisy estimates, $Hist_{med}$ makes fewer mistakes in line 3 in
Algorithm 3. Similarly for the gap between $q_{2}(D)$ and
$\lceil\frac{n^{\prime}}{2}\rceil$ in line 3 in Algorithm 3. As $\epsilon$
increases, the noise scales decrease, reducing the chance of the noise terms
causing $Hist_{med}$ to make a mistake.

Empirical Error Comparison of $Hist_{med}$ & $EM_{med}$. In contrast to
$Hist_{med}$, the outcome from $EM_{med}$ is more dependent on the ranks (in
$D$) of domain values that are in the neighborhood of the true median $q(D)$.
For example, $Hist_{med}$’s error was smaller than that of $EM_{med}$ on
queries $q_{23}$ and $q_{28}$, even at small $\tau$ and $\epsilon$.

Query | WHERE clause | $q(D),q(D_{s})$
---|---|---
| $q_{1}$ |  |  $sex$ LIKE ‘Female’ AND $race$ LIKE ‘White-
---
American Indian-Asian’ AND $workly$ LIKE ‘Yes’
| $34$
---
$34$
| $q_{2}$ |  |  $race$ LIKE ‘White-Black’ AND $marst$ LIKE ‘Never married/
---
single’ AND $citizen$ LIKE ‘Naturalized citizen’
| $54$
---
$54$
| $q_{3}$ |  |  $sex$ LIKE ‘Male’ AND $educ$ LIKE ‘Doctorate
---
degree’ AND $marst$ LIKE ‘Separated’
| $87$
---
$91$
| $q_{4}$ |  |  $race$ LIKE ‘White-American Indian’ AND $marst$
---
LIKE ‘Widowed’ AND $citizen$ LIKE ‘Born in U.S’
| $624$
---
$624$
| $q_{5}$ |  |  $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘Grades $5$
---
or $6$’ AND $marst$ LIKE ‘Never married/single’
| $1560$
---
$1606$
| $q_{6}$ |  |  $sex$ LIKE ‘Female’ AND $race$ LIKE
---
‘White-Black’ AND $workly$ LIKE ‘Yes’
| $1893$
---
$1884$
| $q_{7}$ |  |  $sex$ LIKE ‘Female’ AND $race$ LIKE
---
‘Asian only’ AND $workly$ LIKE ‘No’
| $18693$
---
$18777$
| $q_{8}$ |  |  $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘Master’s degree’
---
AND $marst$ LIKE ‘Married, spouse present’
| $36756$
---
$36404$
| $q_{9}$ |  |  $race$ LIKE ‘Black’ AND $marst$ LIKE ‘Married, spouse
---
present’ AND $citizen$ LIKE ‘Born in U.S’
| $41691$
---
$42455$
| $q_{10}$ |  |  $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘Bachelor’s
---
degree’ AND $marst$ LIKE ‘Married, spouse present’
| $79723$
---
$79283$
| $q_{11}$ |  |  $sex$ LIKE ‘Female’ AND $race$ LIKE
---
‘White’ AND $workly$ LIKE ‘Yes’
| $320934$
---
$320001$
COUNT | $q_{12}$ |  |  $race$ LIKE ‘White’ AND $marst$ LIKE ‘Married,
---
spouse present’ AND $citizen$ LIKE ‘Born in U.S’
| $471994$
---
$470483$
| $q_{13}$ |  |  $sex$ LIKE ‘Female’ AND $race$ LIKE
---
‘White-Black’ AND $workly$ LIKE ‘No’
| $6915340$
---
$6942866$
| $q_{14}$ |  |  $race$ LIKE ‘Asian only’ AND $marst$ LIKE
---
‘Separated’ AND $citizen$ LIKE ‘Born in U.S’
| $7653748$
---
$7818555$
| $q_{15}$ |  |  $sex$ LIKE ‘Male’ AND $educ$ LIKE ‘Professional school
---
degree’ AND $marst$ LIKE ‘Married, spouse absent’
| $9891949$
---
$10129562$
| $q_{16}$ |  |  $race$ LIKE ‘White’ AND $marst$ LIKE ‘Divorced’
---
AND $citizen$ LIKE ‘Not a citizen’
| $123543040$
---
$128497757$
| $q_{17}$ |  |  $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘Master’s
---
degree’ AND $marst$ LIKE ‘Widowed’
| $138131505$
---
$139557517$
| $q_{18}$ |  |  $sex$ LIKE ‘Male’ AND $race$ LIKE
---
‘Asian only’ AND $workly$ LIKE ‘No’
| $143179279$
---
$149069654$
| $q_{19}$ |  |  $sex$ LIKE ‘Male’ AND $race$ LIKE
---
‘Black’ AND $workly$ LIKE ‘No’
| $327036909$
---
$336130017$
| $q_{20}$ |  |  $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘High school diploma
---
or equivalent’ AND $marst$ LIKE ‘Never married/single’
| $685635093$
---
$690711885$
SUM on $inctot$ | $q_{21}$ |  |  $race$ LIKE ‘White’ AND $marst$ LIKE ‘Married,
---
spouse present’ AND $citizen$ LIKE ‘Born in U.S’
| $23542765109$
---
$23434676868$
| $q_{22}$ |  |  $workly$ LIKE ‘Yes’ AND $classwkr$ LIKE ‘Wage/salary,
---
private’ AND $educ$ LIKE ‘Bachelor’s degree’
| $41$
---
$41$
| $q_{23}$ |  |  $sex$ LIKE ‘Male’ AND $race$ LIKE ‘White-
---
Black’ AND $relate$ LIKE ‘Spouse’
| $40$
---
$40$
| $q_{24}$ |  |  $sex$ LIKE ‘Male’ AND $race$ LIKE ‘Black’
---
AND $classwkr$ LIKE ‘Wage/salary, private’
| $40$
---
$40$
| $q_{25}$ |  |  $sex$ LIKE ‘Female’ AND $race$ LIKE
---
‘Black’ AND $workly$ LIKE ‘Yes’
| $41$
---
$41$
| $q_{26}$ |  |  $sex$ LIKE ‘Female’ AND $educ$ LIKE ‘Some college but
---