# Causal Inference with Differentially Private (Clustered) Outcomes

Adel Javanmard Data Sciences and Operations Department, University of Southern
CaliforniaGoogle Research Vahab Mirrokni 22footnotemark: 2 Jean Pouget-
Abadie22footnotemark: 2

###### Abstract

Estimating causal effects from randomized experiments is only feasible if
participants agree to reveal their potentially sensitive responses. Of the
many ways of ensuring privacy, label differential privacy is a widely used
measure of an algorithm’s privacy guarantee, which might encourage
participants to share responses without running the risk of de-anonymization.
Many differentially private mechanisms inject noise into the original data-set
to achieve this privacy guarantee, which increases the variance of most
statistical estimators and makes the precise measurement of causal effects
difficult: there exists a fundamental privacy-variance trade-off to performing
causal analyses from differentially private data. With the aim of achieving
lower variance for stronger privacy guarantees, we suggest a new differential
privacy mechanism, Cluster-DP, which leverages any given cluster structure of
the data while still allowing for the estimation of causal effects. We show
that, depending on an intuitive measure of cluster quality, we can improve the
variance loss while maintaining our privacy guarantees. We compare its
performance, theoretically and empirically, to that of its unclustered version
and a more extreme uniform-prior version which does not use any of the
original response distribution, both of which are special cases of the
Cluster-DP algorithm.

##  1 Introduction

Measurement and experimentation are essential tools to improve any user-facing
product. Technology companies routinely run randomized experiments (Imbens and
Rubin,, 2015), also known as A/B tests, to compare the performance of a new
product or iteration (the treatment) to some well-chosen baseline (the
control). Randomized experiments are also used to evaluate the impact of new
drugs, in the form of clinical trials, or to inform public policy. Measuring
causal effects from these randomized experiments assumes that participants are
willing to share their potentially sensitive or private response to treatment.
This assumption is constantly challenged by the rise of privacy concerns and
regulations for protecting individuals’ online data. Many participants and
regulatory guidelines agree with sharing some degree of information, as long
as there is so-called plausible deniability, meaning no response can be
tracked to any individual user, by sharing only aggregated data for example.
However, data aggregation is often not sufficient to entirely prevent the risk
of de-anonymization (Sweeney,, 2000; Narayanan and Shmatikov,, 2008).

Differential privacy is one possible framework which has emerged as a solid
contender under which user outcomes might be shared while diminishing the risk
of deanonymization. It formalizes the notion that two privatized datasets are
unlikely to differ in any measurable way if the true responses differ by a
single point. Ensuring such a privacy guarantee often comes at the risk of
adding additional noise into the original dataset, which increases the
variance of statistical estimators. This privacy-variance trade-off is crucial
for causal inference applications, since randomized experiments aim to obtain
the most precise measurements possible of a causal effect.

Our paper has two main objectives: (a) to mathematically analyze the privacy-
variance tradeoff for an intuitive set of algorithms that allow for the
estimation of causal effects from differentially private data; and (b) to
develop a novel mechanism Cluster-DP that enhances this privacy-variance
trade-off by leveraging non-sensitive cluster information about the dataset.

Many of the algorithms we consider assume the existence of a central unit that
observes all outcomes, and computes and shares a privatized dataset on which
causal inference analyses can be run by a third-party. Furthermore, our
suggested Cluster-DP mechanism assumes that outcomes exhibit some cluster
structure, such as geographic regions or broad demographic classes. Notably,
these clusters need not satisfy specific cardinality or quality constraints,
and can include singleton clusters, random clusters, or even a single cluster
containing all units. We do show however that our results improve when the
clusters exhibit a measure of cluster quality that we define.

In Section 2, we motivate and define the differential privacy setting and
causal objective of our work. In Section 3, we consider several intuitive
mechanisms for privatizing a dataset while allowing for unbiased and
consistent estimation of the average treatment effect. In particular, we
consider the Uniform-Prior-DP mechanism which samples responses with some
probability at random from the space of possible outcomes. In Section 4, we
introduce our novel private-and-causal Cluster-DP mechanism, and its special
case when all units belong to the same cluster, the Cluster-Free DP mechanism.
We evaluate their privacy guarantees and their variance gap to their non-
differentially-private counterparts. We conclude in Section 5 with numerical
experiments on simulated and real graphs to validate our claims and compare
the empirical performance of each algorithm.

###  1.1 Related works

There are different approaches to preserving the privacy of user data
regardless of any downstream analysis of it. A popular approach involves
anonymizing data by removing, aggregating, or randomizing identifying details
in some way before releasing the data to the public, in the hope of making
‘re-identification’ of users difficult. Several privacy measures have been
proposed under this approach, including $k$-anonymity (Sweeney,, 2002, 2000),
$\ell$-diversity (Machanavajjhala et al.,, 2007), and $t$-closeness (Li et
al.,, 2006). While providing a layer of privacy protection, there are well-
documented cases where de-identified data has been combined with other data
sources to uniquely re-identify large proportion of users (Narayanan and
Shmatikov,, 2008; Sweeney,, 2000).

In this work, we consider the differential privacy measure, which is a
property of a data processing algorithm, rather than of a data set (Dwork et
al., 2006a, ; Dwork et al., 2006b, ). Differential privacy is widely used and
extensively covered. In this work, we will focus primarily on label
differential privacy, introduced by Chaudhuri and Hsu, (2011). The literature
on label differential privacy is mostly dedicated to classification and
regression tasks with the goal of improving excess risk while offering
protection for labels (Beimel et al.,, 2013; Bassily et al.,, 2018; Wang and
Xu,, 2019). More recently, there have been several papers improving utility-
privacy tradeoffs of label DP algorithms (Esfandiari et al.,, 2022; Ghazi et
al.,, 2021, 2022). Our mechanism is inspired by a technique by (Esfandiari et
al.,, 2022), which we adapt to the estimation of causal effects. We further
provide privacy-variance tradeoffs and a tighter analysis of the privacy
guarantee than the proof methodology of (Esfandiari et al.,, 2022), which we
extend to an $({\varepsilon},\delta)$-type guarantee (See Theorem 4.1).

Panigrahi et al., (2022) study the problem of treatment effect estimation
after adjusting for potential confounders from different independent studies.
Using a Lasso estimator, a parsimonious model is selected in each study and an
unbiased estimator is constructed by aggregating simple summary statistics.
While sharing only the summary statistics provides some layer of protection,
this work does not provide any differential privacy guarantees.

Closer to our work, Kancharla and Kang, (2021) also study the problem of
average treatment effect estimation from a randomized control trial, where
outcomes have been privatized using a differentially private mechanism.
Specifically, they consider a binary outcome space and a mechanism, which for
any given true response $y_{i}$, either returns $\tilde{y_{i}}=0$ with
probability $r_{0}$, $\tilde{y_{i}}=1$ with probability $r_{1}$, or the true
outcome $\tilde{y}_{i}=y_{i}$ with probability $1-r_{0}-r_{1}$ for some choice
of probabilities $r_{0},r_{1}\in(0,1)$. Our setting and results differ
significantly in that (1) we go beyond binary responses and consider a general
discrete outcome space; (2) our mechanism leverages a clustering structure of
responses to improve the privacy-variance trade-off, and we quantify the
impact of cluster quality on the variance of the estimator. In fact, their
proposed procedure does not account for the empirical distribution of
responses, such that an extension of their algorithm to a general discrete
outcome space would be closer to the Uniform-Prior DP mechanism, which we
consider along with other baselines in Section 3. In the absence of non-
compliers, the procedure in (Kancharla and Kang,, 2021) can be viewed as a
special case of ours, for binary outcomes and assuming no-cluster structure
(see Equation 7 for further detail).

Betlei et al., (2021) focus on the randomized control trial set-up and propose
a differentially private method, called ADUM, to learn uplift models from data
aggregated along a given partition of the feature space. The privacy-utility
trade-off is studied by computing the mean-squared error of the estimator and
its dependence on the underlying partition size and privacy budget. The
analysis is for uni-dimensional feature spaces and makes the assumption that
every bin has the same number of treated and controlled units. The ADUM
mechanism adds Laplace noise to the count and the sum of responses from
treated and controlled groups within each bin, and uses the (noisy) aggregate
responses to estimate the conditional average treatment effect (CATE). While
the bins can be thought of as clusters based on the features, their work does
not use this clustering structure to reduce the variance of the estimator
resulting from the added noise to achieve differential privacy. The ADUM
mechanism is very similar to the noisy Horvitz-Thompson estimator baseline
discussed in Section 3, with the difference that ADUM adds noise to the count
and the sum of responses, while the noisy Horvitz-Thompson estimator baseline
adds noise directly to the average response of treated and controlled groups
in each cluster (cf. Equation (1)).

Niu et al., (2022) propose a meta-algorithm for multi-stage learning under
privacy constraints and apply that to CATE estimation. The methodology relies
on multiple sample-splittings where different parts of the sample are used to
estimate different components of the estimator. The approach uses DP-EBMs
(Nori et al.,, 2021) as the base learner, and conducts a privacy analysis
using the sample splitting structure of the algorithm and the parallel
composition property of differential privacy. They study the privacy-accuracy
trade-off empirically. This framework goes beyond randomized control trials
and allows for heterogeneous causal effects. However, they do not leverage the
cluster structure of the data to improve the variance-privacy tradeoff, nor do
they provide private ‘unit-level’ data to the experimenters; instead their
work aims to estimate the propensity model and the outcome model in a
differentially-private way.

##  2 Causal Objective and Privacy Setting

We are motivated by the real-world scenario of a technology company in the
business of selling advertising space to advertisers. Its clients, the
advertisers, wish to measure the effectiveness of their advertising campaigns
by running A/B tests, but do not want to rely on this technology company to
provide their causal estimates. Instead, they would like access to user-level
data, such as whether a user clicked on their ad, as well as any meaningful
covariates about that user, so that they can conduct these analyses
themselves. One reason for this might be that advertisers wish to run their
own covariate-adjustment methods, or they would like to investigate
proprietary sub-slices of users. On the other hand, this technology company
seeks to protect the privacy of its users, and does not wish to share
sensitive information about its users. Hence it must act as a central unit
which privatizes its datasets before passing them on to advertisers for them
to perform their own causal inference analyses on. We now introduce the formal
causal objective and privacy setting. To guide the reader through abundant
notation, we include a glossary at the beginning of the Appendix.

##### Causal Objective.

We consider a fixed population of $n$ users, henceforth units, where we can
assume the Stable Unit Treatment Value Assumption (Imbens and Rubin,, 2015).
Let $y_{i}(0)$ be the potential outcome of unit $i$ if it is controlled, and
$y_{i}(1)$ if it is treated. These potential outcomes are sampled from a
finite response space $\mathcal{Y}$ of cardinality $K=|\mathcal{Y}|$. While
finite response spaces are common in many advertising settings (e.g. number of
clicks or impressions), we suggest binning when outcomes are continuous, as
illustrated in Section 5.

For our Cluster-DP algorithm, we will further assume that there is some known
clustered structure of these units into $C=|\mathcal{C}|$ non-overlapping
clusters of size $n_{c}$, and let $c_{i}\in\mathcal{C}$ be the cluster
membership of unit $i$. These clusters may be geographic regions or broad
demographic groups the units belong to. We do not make any assumptions on the
number of clusters or their size. In particular, our results hold for a single
cluster or all singleton clusters. The strength of our results, however,
improve with a specific measure of cluster quality, introduced in Section 4.

While we focus on the common finite sample setting, we can easily extend our
results to their super-population equivalents. For this purpose, we will
sometimes denote by $x_{i}\in{\mathbb{R}}^{d}$ the covariate vector of each
unit $i$ such that each $(x_{i},y_{i}(0),y_{i}(1),c_{i})$ is drawn from some
joint distribution ${\mathcal{P}}$ . Our causal estimand is the average
treatment effect estimand defined in the finite sample regime by

$\tau=\frac{1}{n}\sum_{i=1}^{n}\left(y_{i}(1)-y_{i}(0)\right)\,.$

Let $z_{i}$ correspond to the treatment assignment of unit $i$, $z_{i}=1$ if
treated and $z_{i}=0$ if controlled. Let $n_{1}$ be the total number of
treated units and $n_{0}$ to be the total number of controlled units across
units. Treatment and control are assigned completely at random. When a
clustering of the data is available, the treatment assignment is sampled in a
completely randomized way over clusters: a fixed number of $n_{1,c}$ (resp
$n_{0,c}$) units is chosen uniformly at random to be treated (resp.
controlled) within each cluster $\mathcal{C}$, with $n_{c}=n_{1,c}+n_{0,c}$
the total number of units in cluster $c$.

##### Privacy Setting.

In the real-world advertising setting presented above, it is assumed that a
central unit privatizes the dataset before sharing it externally. Some of the
mechanisms we explore also work without the presence of this central unit, a
setting known as local differential privacy, but this is not a requirement for
our framework.

Furthermore, an important question is which variables (treatment assignment,
outcome, cluster assignment and/or covariates if available) are sensitive and
should be privatized. In our advertising setting, a unit’s treatment
assignment is assigned purely at random; it is therefore not sensitive, and
can be shared as-is. Outcomes are clearly sensitive and should be privatized.
Finally, of the mechanisms we present, only our proposed Cluster-DP mechanism
uses clusters—or covariates to form these clusters—to improve its privacy-
variance tradeoff. While not all covariates may be sensitive (e.g. broad
geographic regions), we can decouple the privacy protection of covariates from
that of outcomes. In particular, by virtue of the composition property of
differential privacy, we can allocate ${\varepsilon}_{1}$ privacy loss for the
first step (forming clusters from covariates) and ${\varepsilon}_{2}$ privacy
loss for the second step (computing the estimator). The end-to-end process
will be ${\varepsilon}(={\varepsilon}_{1}+{\varepsilon}_{2})$-DP. There
already exists a rich literature on DP-clustering algorithms, see e.g., Nissim
et al., (2007); Feldman et al., (2009, 2017); Stemmer and Kaplan, (2018);
Cohen et al., (2021). We focus therefore on the second step, namely estimating
average treatment effect from differentially private outcomes, assuming a
given cluster structure. This more restricted setting is known as label-
differential privacy, introduced by Chaudhuri and Hsu, (2011) and (re-)defined
formally below. In this context, a unit’s “label” refers to its observed
outcome; we use the words outcome and label interchangeably.

######  Definition 2.1.

(Label Differential Privacy) Consider a randomized mechanism
$M:D\to\mathcal{O}$ that takes as input a dataset $D$ and outputs into
$\mathcal{O}$. Let ${\varepsilon},\delta\in{\mathbb{R}}_{\geq 0}$. A mechanism
$M$ is called $({\varepsilon},\delta)$-_label differentially private_ —or
$({\varepsilon},\delta)$-label DP—if for any two datasets $(D,D^{\prime})$
that differ in the label (outcome) of a single example and any subset
$O\subseteq\mathcal{O}$ we have ${\mathbb{P}}[M(D)\in O]\leq
e^{\varepsilon}{\mathbb{P}}[M(D^{\prime})\in O]+\delta$ , where
${\varepsilon}$ is the privacy budget and $\delta$ is the failure probability.
If $\delta=0$, then $M$ is said to be ${\varepsilon}$-_label differentially
private_ , or ${\varepsilon}$-label DP.

Achieving label-differential privacy implies that the output of a mechanism
does not change too much if a single label in the input dataset is changed.
The _privacy loss_ ${\varepsilon}$ controls the size of the possible change,
and $\delta$ is the _failure probability_ in providing such a guarantee. In
other words, $({\varepsilon},0)$-differential privacy ensures that, for
_every_ run of the mechanism $M$, the observed output is (almost) equally
likely to be observed on every other neighboring dataset, simultaneously. The
$({\varepsilon},\delta)$-differential privacy property relaxes this constraint
and states only that it is unlikely that the observed value $M(D)$ has a much
higher or lower chance to be generated under a dataset $D$ compared to a
neighboring dataset $D^{\prime}$. Differential privacy can also be viewed from
a statistical hypothesis testing framework, where an attacker aims to
distinguish $D$ from $D^{\prime}$ based on the output of the mechanism. This
viewpoint has been put forward by Wasserman and Zhou, (2010) and Kairouz et
al., (2015), who show that, by using the output of an
$({\varepsilon},\delta)$-DP mechanism, the power of any test with significance
level $\alpha\in[0,1]$ is bounded by $e^{{\varepsilon}}\alpha+\delta$. For
small enough $({\varepsilon},\delta)$, this bound is only slightly larger than
$\alpha$, and so any test which aims to distinguishing $D$ from $D^{\prime}$
is powerless.

##  3 Aggregation-based baselines and the Uniform-Prior-DP mechanism

In this section, we introduce three differentially private algorithms that
still allow for the estimation of causal effects. These will serve as
important baselines to our proposed Cluster-DP algorithm, which will be
introduced later in Section 4.

###  3.1 Two aggregation-based baselines

The simplest approach to sharing a differentially private estimate of the
average treatment effect is for the central unit to compute some unbiased
estimator based on the original responses $y_{i}$ and add noise to the
estimate before sharing it externally. We provide an example in Algorithm 1,
written in the broadest generality when a clustering is available. When no
clustering is available, we can simply assume that all units belong to the
same cluster.

Input: Individual responses $y_{1},\dotsc,y_{n}$, (optional) cluster
memberships $c_{1},\dotsc,c_{n}$

Output: Privatized estimate $\hat{\tau}$ Return
$\displaystyle\hat{\tau}:=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\left\\{\sum_{i\in
c}\left(\frac{y_{i}z_{i}}{n_{1,c}}-\frac{y_{i}(1-z_{i})}{n_{0,c}}\right)+w_{c}\right\\}\,,\quad
w_{c}\sim\text{Laplace}(\eta_{c})\,.$ (1)

Algorithm 1 noisy Horvitz-Thompson mechanism

The variances of the noise parameters $\eta_{c}$ determine both the privacy
guarantee ${\varepsilon}$ and additional estimator variance of the Noisy
Horvitz-Thompson algorithm. To compute its privacy guarantee, we apply (Dwork
et al.,, 2014, Theorem 3.6) and consider the sensitivity $\Delta_{c}$ of the
inner function
$\nicefrac{{1}}{{n_{1,c}}}y_{i}z_{i}-\nicefrac{{1}}{{n_{0,c}}}y_{i}(1-z_{i})$,
defined as the maximum change in its value when changing only one label in the
data set. The variance of $\hat{\tau}$ can be expressed easily as a function
of the variance of its non-differentially-private equivalent, the Horvitz-
Thompson estimator without the Laplace noise:

$\displaystyle\hat{\tau}_{\textsc{No-
DP}}:=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\sum_{i\in
c}\left(\frac{y_{i}z_{i}}{n_{1,c}}-\frac{y_{i}(1-z_{i})}{n_{0,c}}\right)\,.$
(2)

######  Proposition 3.1.

The noisy Horvitz-Thompson estimator $\hat{\tau}$ is ${\varepsilon}$-DP when
setting $\eta_{c}=\nicefrac{{\Delta_{c}}}{{{\varepsilon}}}$ for every cluster,
where
$\Delta_{c}=\min\\{n_{0,c},n_{1,c}\\}^{-1}\times\max_{y\in\mathcal{Y}}|y|$.
Furthermore, its variance with respect to the treatment assignment ${\bm{z}}$
and the Laplace noise $(DP)$ is given by

${\rm Var}_{DP,{\bm{z}}}[\hat{\tau}]={\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+2\sum_{c\in\mathcal{C}}\left(\frac{n_{c}}{n}\frac{\Delta_{c}}{{\varepsilon}}\right)^{2}\,,$

where $\hat{\tau}_{\textsc{No-DP}}$ is the non-differentially-private
stratified Horvitz-Thompson estimator defined in Eq. 2, and ${\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-DP}}]$ is its variance with respect to
the treatment assignment ${\bm{z}}$.

Because these results hold for any clustering, they also hold when no
clustering is available; in that case, we consider all units to be part of the
same cluster. We refer the reader to the appendix for the well-known closed-
form expression of ${\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-DP}}]$.

A second and slightly more sophisticated approach would be for the central
unit to add noise to the frequency of responses in each cluster before sharing
the histogram externally, since the estimated treatment effect depends only on
the histogram of responses of treated and controlled units in each cluster. We
provide an example in Algorithm 2, written in the broadest generality when a
clustering is available.

Input: Individual responses $y_{1},\dotsc,y_{n}$, (optional) cluster
memberships $c_{1},\dotsc,c_{n}$

Output: Privatized estimate $\hat{\tau}$

Compute the empirical distribution $\hat{p}_{a}(y|c)$ of treated ($a=1$) and
controlled ($a=0$) units within cluster $c$.  Return
$\displaystyle\hat{\tau}:=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\sum_{y\in\mathcal{Y}}y\times(\hat{p}_{1}(y|c)+w_{1,c,y}-\hat{p}_{0}(y|c)-w_{0,c,y})\,,\quad
w_{a,c,y}\sim\text{Laplace}(\eta_{a,c})\,.$ (3)

Algorithm 2 noisy histogram mechanism

Since the $K$ bins corresponding to the $K$ elements of $\mathcal{Y}$ are
disjoint, and the sensitivity of the value of each histogram bin is
$n_{a,c}^{-1}$, the central unit can share the histogram privately by adding
independent draws from Laplace($(n_{a,c}{\varepsilon})^{-1}$) to the frequency
of each value. Furthermore, we can compute in closed form the variance gap of
the Noisy Histogram mechanism compared to its non-private Horvitz-Thompson
counterpart.

######  Proposition 3.2.

The noisy Histogram mechanism $\hat{\tau}$ is ${\varepsilon}$-DP when setting
$\eta_{a,c}=(n_{a,c}{\varepsilon})^{-1}$ for every cluster. Furthermore, its
variance with respect to the treatment assignment ${\bm{z}}$ and the Laplace
noise $(DP)$ is given by

${\rm Var}_{DP,{\bm{z}}}[\hat{\tau}]={\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\frac{2}{{\varepsilon}^{2}}\left(\sum_{y\in\mathcal{Y}}y^{2}\right)\sum_{c\in\mathcal{C}}\left(\frac{n_{c}}{n}\right)^{2}\left(\frac{1}{n_{0,c}^{2}}+\frac{1}{n_{1,c}^{2}}\right)\,,$

where $\hat{\tau}_{\textsc{No-DP}}$ is the non-differentially-private
stratified Horvitz-Thompson estimator defined in Eq. 2, and ${\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-DP}}]$ is its variance with respect to
the treatment assignment ${\bm{z}}$.

For the same privacy guarantee, the Noisy-Horvitz-Thompson mechanism has a
smaller variance gap than the Noisy-Histogram mechanism, since
$\|y\|_{\infty}\leq\|y\|_{2}$ and
$\min(n_{0,c},n_{1,c})^{-2}\leq\min(n_{0,c},n_{1,c})^{-2}+\max(n_{0,c},n_{1,c})^{-2}=n_{0,c}^{-2}+n_{1,c}^{-2}$.

##### Limitations

These aggregation-based approaches have two drawbacks in the real-world
setting of Section 2. First, advertisers expect user-level data even if
privatized. Perhaps this is because they wish to analyse their own slices of
the user population or perhaps they wish to apply their own proprietary
covariate-adjustment method to measure campaign effectiveness. Second, the
level of noise in Algorithm 1 is averaged over the number of clusters $C$; in
Algorithm 2, it is averaged over the number of possible outcomes $K$. The next
mechanisms that we introduce will privatize user-level responses, and the
noise level therein is averaged over $n$ samples, the number of users. This
becomes an important competitive advantage of user-level methods in the case
of one-shot communication between the central unit and the advertisers. In
particular, a user-level privatizing scheme achieves lower finite-sample
conditional bias than the prior two aggregation baselines when $n\gg K$ and
$n\gg C$, when we condition on the randomness of the DP mechanism and consider
the bias with respect to the randomization in the sub-population. We will
illustrate this point further in Experiment 5 of Section 5.

###  3.2 The Uniform-prior DP mechanism

Unlike the two prior mechanisms, the next mechanism we consider provides user-
level outcomes. Formalized in Algorithm 3, it reports the true outcome with
some probability, and otherwise reports an outcome sampled uniformly at random
from the space of possible outcomes. We refer to it as the uniform-prior-DP
mechanism because it does not leverage any information about the empirical
distribution of outcomes beyond its support.

Input: Individual responses $y_{1},\dotsc,y_{n}$

Output: Privatized responses $\tilde{y}_{1},\dotsc,\tilde{y}_{n}$

for  _$i\in\\{1,\dotsc n\\}$_ do

$\tilde{y}_{i}\leftarrow\begin{cases}{y}^{0}_{i}\sim\mathcal{U}(\mathcal{Y})&\text{\emph{with
probability }}\lambda\quad\text{// $\mathcal{U}$ is the uniform
distribution}\\\ y_{i}&\text{\emph{with probability }}1-\lambda\end{cases}$

_Return privatized responses_ $\\{\tilde{y}_{1},\dotsc,\tilde{y}_{n}\\}$.

Algorithm 3 uniform-prior-DP mechanism

The uniform-prior-DP mechanism is a generalization of the mechanism proposed
by Kancharla and Kang, (2021) in the binary-outcome setting, when there are no
non-compliers. In the broadest generality when a clustering is available, the
following stratified estimator is unbiased for the average treatment effect:

$\displaystyle\hat{\tau_{\lambda}}=\frac{1}{1-\lambda}\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\sum_{i\in
c}\left(\frac{\tilde{y}_{i}z_{i}}{n_{1,c}}-\frac{\tilde{y}_{i}(1-z_{i})}{n_{0,c}}\right)\,.$
(4)

######  Proposition 3.3.

The conditional expectation of the estimator $\hat{\tau}_{\lambda}$ defined in
Eq. (4), with respect to the DP mechanism, is equal to the non-differentially
private Horvitz-Thompson estimator. It is therefore unbiased for the average
treatment effect $\tau$ over ${\bm{z}}$ and the $DP$ mechanism.

${\mathbb{E}}_{DP}[\hat{\tau}_{\lambda}|{\bm{z}}]=\hat{\tau}_{\textsc{No-
DP}}\text{\quad and
\quad}{\mathbb{E}}_{DP,{\bm{z}}}[\hat{\tau}_{\lambda}]=\tau$

Having an unbiased estimator for causal inference is an important but not
entirely surprising result. In fact, many differentially private mechanisms
can recover true labels in expectation; Kancharla and Kang, (2021) also
propose an unbiased differentially private estimator in the setting of binary
potential outcomes $y_{i}\in\\{0,1\\}$. Instead, the main difficulty is to
minimize the variance gap with non-differentially-private estimators. To state
the variance of $\hat{\tau}$ under the uniform-prior-DP mechanism, we consider
the following notation:
$\bar{\mathsf{y}}:=\nicefrac{{1}}{{|\mathcal{Y}|}}\sum_{y\in\mathcal{Y}}y$ and
$\overline{\mathsf{y}^{2}}:=\nicefrac{{1}}{{|\mathcal{Y}|}}\sum_{y\in\mathcal{Y}}y^{2}$
over all possible outcomes. For $a\in\\{0,1\\}$, we also define
$\overline{y_{c}(a)}:=\nicefrac{{1}}{{n_{c}}}\sum_{i\in c}y_{i}(a)$ and
$\overline{y^{2}_{c}(a)}:=\nicefrac{{1}}{{n_{c}}}\sum_{i\in c}y_{i}^{2}(a)$
over the units of cluster $c$.

######  Theorem 3.4.

For any $\tilde{{\varepsilon}}>0$, the uniform-prior-DP mechanism is
$(\tilde{{\varepsilon}},\delta)$-label DP when we set
$\delta=\max(0,1-\lambda+\tfrac{\lambda}{K}(1-e^{\tilde{{\varepsilon}}}))\,.$
In particular, it is ${\varepsilon}$-label DP with
${\varepsilon}=\log\left(1+\frac{(1-\lambda)K}{\lambda}\right)$. Furthermore,
the variance of estimator $\hat{\tau}_{\lambda}$ in (4) under the uniform-
prior-DP mechanism and the treatment assignment ${\bm{z}}$ is given by

$\displaystyle{\rm Var}_{DP,{\bm{z}}}[\hat{\tau}_{\lambda}]$
$\displaystyle={\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left(\frac{1}{n_{0,c}}+\frac{1}{n_{1,c}}\right)\frac{\lambda\overline{\mathsf{y}^{2}}-\lambda^{2}\bar{\mathsf{y}}^{2}}{(1-\lambda)^{2}}$
$\displaystyle+\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left[\frac{\lambda}{1-\lambda}\left(\frac{\overline{y_{c}^{2}(0)}}{n_{0,c}}+\frac{\overline{y_{c}^{2}(1)}}{n_{1,c}}\right)-\frac{2\lambda\bar{\mathsf{y}}}{1-\lambda}\left(\frac{\overline{y_{c}(0)}}{n_{0,c}}+\frac{\overline{y_{c}(1)}}{n_{1,c}}\right)\right]\,,$
(5)

As the sampling probability grows small $\lambda\rightarrow 0$, we recover the
non-private variance formula ${\rm
Var}_{DP,{\bm{z}}}(\hat{\tau})\rightarrow{\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-DP}}]$, but the ${\varepsilon}$-DP
guarantee goes to infinity. Since the uniform-prior-DP mechanism itself does
not depend on the clusters, the privacy guarantee does not depend on the
clustering properties of the data, if any. The dependence on the clustering in
Equation (5) is only due to the definition of the stratified estimator. When a
good clustering is not available, the above estimator can be simplified to its
unstratified version $\hat{\tau}^{u}$ by considering that all units belong to
the same cluster:

$\displaystyle\hat{\tau}^{u}=\frac{1}{1-\lambda}\sum_{i=1}^{n}\left(\frac{\tilde{y}_{i}z_{i}}{n_{1}}-\frac{\tilde{y}_{i}(1-z_{i})}{n_{0}}\right)\,.$
(6)

The following variance result is a direct corollary of Theorem 3.4.

######  Corollary 3.5.

Under the uniform-prior-DP mechanism, the variance of the unstratified
estimator $\hat{\tau}^{u}$ defined in Eq. 6 is given by

${\rm Var}_{DP,{\bm{z}}}[\hat{\tau}^{u}]={\rm
Var}_{{\bm{z}}}[\hat{\tau}^{u}_{\textsc{No-
DP}}]+\frac{n}{n_{1}n_{0}}\frac{\lambda\overline{\mathsf{y}^{2}}-\lambda^{2}\bar{\mathsf{y}}^{2}}{(1-\lambda)^{2}}+\frac{\lambda}{1-\lambda}\left(\frac{\overline{y^{2}(0)}}{n_{0}}+\frac{\overline{y^{2}(1)}}{n_{1}}\right)-\frac{2\lambda\bar{\mathsf{y}}}{1-\lambda}\left(\frac{\overline{y(0)}}{n_{0}}+\frac{\overline{y(1)}}{n_{1}}\right)$

where ${\rm Var}_{{\bm{z}}}[\hat{\tau}^{u}_{\textsc{No-DP}}]$ denotes the
variance of its non-private equivalent $\hat{\tau}^{u}_{\textsc{No-DP}}$. Its
differential privacy guarantees are the same as those in Theorem 3.4.

We refer the reader to the appendix for the well-known closed form formula of
${\rm Var}_{{\bm{z}}}[\hat{\tau}^{u}_{\textsc{No-DP}}]$. The special case of
the unstratified estimator $\hat{\tau}^{u}$ in (6) for binary outcomes
$\mathcal{Y}=\\{0,1\\}$ was previously proposed by Kancharla and Kang, (2021),
in which case the variance of the estimator can be further simplified:

$\displaystyle{\rm Var}_{DP,{\bm{z}}}[\hat{\tau}^{u}]$ $\displaystyle={\rm
Var}_{{\bm{z}}}[\hat{\tau}^{u}_{\textsc{No-
DP}}]+\frac{n}{n_{0}n_{1}}\frac{\frac{\lambda}{2}(1-\frac{\lambda}{2})}{(1-\lambda)^{2}}\,.$
(7)

The first two aggregation-based mechanisms in Section 3.1 assumed that a
trusted data curator (e.g. a technology company, in the motivating example in
Section 2) has access to the true outcomes and computes a differentially
private estimate or empirical distribution of these responses. In contrast,
the Uniform-prior-DP mechanism can be implemented without such a curator: each
user can privatize their response before sharing it with the experimenter. In
other words, the Uniform-prior-DP mechanism provides a local DP guarantee,
defined by Kasiviswanathan et al., (2011), which is stronger than a DP
guarantee. That said, in our motivating example, assuming the existence of a
trusted curator—the technology company—is more natural than putting the burden
of privatizing responses on each individual user.

##  4 The Cluster-DP and Cluster-Free-DP mechanisms

We now introduce our main differentially private mechanism, Cluster-DP, which
not only provides user-level privatized outcomes, but also leverages
information about the empirical distribution of outcomes within each cluster
to improve its privacy-tradeoff. When no good clustering is available, we
consider its special case when all units can be considered part of the same
cluster, the Cluster-Free-DP mechanism.

Parameters: threshold $\gamma\in[0,\nicefrac{{1}}{{K}}]$; noise scale
$\sigma\geq 0$; re-sampling probability $\lambda\in[0,1]$

Input: Individual responses $y_{1},\dotsc,y_{n}$, treatment assignments
$z_{1},\dotsc,z_{n}$.

Output: Privatized responses $\tilde{y}_{1},\dotsc,\tilde{y}_{n}$

// _Compute noisy response distribution per cluster and treatment group_

for  _$c\in\mathcal{C}$_ do

for  _$a\in\\{0,1\\}$_ do

// _Add noise to each empirical probability distribution $\hat{p}_{a}(y|c)$
and truncate_

for  _$y\in\mathcal{Y}$_ do

$q_{a}(y|c)\leftarrow\max\\{\gamma,\min\\{1,\hat{p}_{a}(y|c)+w$}} , where
$w\sim\text{Laplace}(\sigma/n_{a,c})$

for  _$a\in\\{0,1\\}$_ do

// _Renormalize each distribution_

for  _$y\in\mathcal{Y}$_ do

if  _$\sum_{y}q_{a}(y|c) >1$_ then $\zeta_{y}\leftarrow q_{a}(y|c)-\gamma$;

else $\zeta_{y}\leftarrow 1-q_{a}(y|c)$

for  _$y\in\mathcal{Y}$_ do

$\tilde{q}_{a}(y|c)\leftarrow
q_{a}(y|c)+\frac{\zeta_{y}}{\sum_{y^{\prime}}\zeta_{y^{\prime}}}\left(1-\sum_{y}q_{a}(y|c)\right)$

// _Randomize responses_

for  _$i\in\\{1,\dotsc n\\}$_ do

$\tilde{y}_{i}\leftarrow\begin{cases}{y}^{0}_{i}\sim\tilde{q}_{z_{i}}(\cdot|c_{i})&\text{\emph{with
probability }}\lambda\\\ y_{i}&\text{\emph{with probability
}}1-\lambda\end{cases}$

_Return privatized responses_ $\\{\tilde{y}_{1},\dotsc,\tilde{y}_{n}\\}$.

Algorithm 4 Our suggested differential privacy mechanism: Cluster-DP

Formalized in Algorithm 4, our proposed mechanism deals with each cluster
individually and independently of other clusters, handling treated and
controlled groups separately. It returns a privatized potential outcome
$\tilde{y}_{i}$ for each unit, which is either the true outcome with some
probability or sampled from a transformed empirical distribution of responses
from units in the same cluster. The transformation is inspired from a
mechanism in Esfandiari et al., (2022). For the sake of exposition, we focus
on the controlled units of a cluster $c\in\mathcal{C}$.

  * (1)

Compute the empirical response distribution of the controlled units in the
cluster $\hat{p}_{0}(y|c)$.

  * (2)

Add noise drawn from a Laplace distribution with parameter $(\sigma/n_{0,c})$
to each response probability. Recall that $n_{0,c}$ is the number of
controlled units in cluster $c$.

  * (3)

Truncate the response probabilities to be within the interval $[\gamma,1]$,
with $\gamma\leq\nicefrac{{1}}{{K}}$ .

  * (4)

Renormalize the response probabilities to form a distribution. We follow a
specific renormalization so that the resulting response probabilities remain
in $[\gamma,1]$, and add up to one.

  * (5)

With probability $\lambda$, each original response is replaced by a random
sample from the distribution constructed in the previous step.

###  4.1 Privacy guarantees

The following theorem and its corollary state the differential privacy
guarantee of our proposed Cluster-DP mechanism.

######  Theorem 4.1.

Let $\tilde{{\varepsilon}}>0$ and
$\delta:=\max(0,1-\lambda+\lambda\gamma(1-e^{\tilde{{\varepsilon}}}))\,$. The
Cluster-DP mechanism described in Algorithm 4 is
$({\varepsilon},\delta)$-label DP with
${\varepsilon}=\min\left(\frac{1}{\sigma},\frac{2}{\gamma}\right)+\tilde{{\varepsilon}}\,.$
By setting $\tilde{{\varepsilon}}=\log(1+\tfrac{1-\lambda}{\lambda\gamma})$,
we have $\delta=0$, and therefore the Cluster-DP mechanism is also
${\varepsilon}$-label DP, with
${\varepsilon}=\min\left(\frac{1}{\sigma},\frac{2}{\gamma}\right)+\log\left(1+\frac{1-\lambda}{\lambda\gamma}\right)\,.$

We refer the reader to the Appendix for a full proof of Theorem 4.1 and
provide here some intuition for its stated privacy loss ${\varepsilon}$. The
first term
$\min\left(\nicefrac{{1}}{{\sigma}},\nicefrac{{2}}{{\gamma}}\right)$ is the
privacy budget used to privately estimate the empirical response distribution
$\tilde{q}_{a}(\cdot|c)$ for each cluster. Fixing the transformed empirical
distributions $\tilde{q}_{a}(\cdot|c)$, the $\log$ term is the privacy budget
used to generate the privatized responses $\tilde{y}_{i}$. By the composition
theorem for differential privacy (Dwork et al.,, 2014, Theorem B.1), the total
privacy loss is given by the sum of these two losses. As expected, when the
resampling probability goes to zero $(\lambda\rightarrow 0)$, the privacy loss
grows large $({\varepsilon}\rightarrow+\infty)$. Similarly, as the Laplace
noise $\sigma$ and truncation parameter $\gamma$ grow large, the privacy
guarantee improves $({\varepsilon}\rightarrow 0)$.

Because these privacy guarantees do not depend on the size, cardinality, or
quality of the clusters, Theorem 4.1 also holds for the special case where
there is no cluster structure to the data, in which case we can repeat the
same mechanism as if all units belong to the same large cluster. Known as the
Cluster-Free-DP mechanism, it has the same privacy guarantee as the Cluster-DP
mechanism. We will show the benefit that clusters may have in the following
section on the variance gap.

##### Similarity with uniform-prior-DP

The careful reader may have noticed similarities between the privacy
guarantees in Theorem 3.4 and Theorem 4.1. In fact, our cluster-DP mechanism
is a generalization of the uniform-prior-DP mechanism with the right choice of
parameters, and by extension also a generalization of the mechanism proposed
by Kancharla and Kang, (2021) with no non-compliers. To prove this, we observe
that the distributions $\tilde{q}_{a}(y|c)$ constructed in the cluster-DP
mechanism obey the following properties:
$\tilde{q}_{a}(y|c)\geq\gamma~{}\text{for all
}y\in\mathcal{Y}\,,\text{~{}and~{}}\sum_{y}\tilde{q}_{a}(y|c)=1\,.$ When
setting the truncation parameter $\gamma=\nicefrac{{1}}{{K}}$, these
distributions reduce to uniform distributions over the space of all outcomes,
in which case the cluster-DP mechanism amounts to the simpler uniform-prior-DP
mechanism, regardless of the value of the Laplace noise variance $\sigma^{2}$.

###  4.2 Estimation and variance guarantees

We now consider estimating causal effects from the privatized outcomes
provided by our suggested Cluster-DP mechanism. For each cluster
$c\in\mathcal{C}$ and each value $a\in\\{0,1\\}$ of treatment, we construct
the response randomization matrix $Q_{c,a}\in{\mathbb{R}}^{K\times K}$:

$Q_{c,a}[y^{\prime},y]:=(1-\lambda){\mathbb{I}}(y^{\prime}=y)+\lambda\tilde{q}_{a}(y^{\prime}|c)\,.$
(8)

Conditional on its true outcome $y_{i}$, treatment assignment $z_{i}$, and
cluster assignment $c_{i}$, the privatized response $\tilde{y}_{i}$ of unit
$i$ is distributed according to $Q_{c_{i},z_{i}}[\tilde{y}_{i},y_{i}]$; in
other words, $\forall
y^{\prime},\,P(\tilde{y}_{i}=y^{\prime}|c_{i},z_{i},y_{i})=Q_{c_{i},z_{i}}[y^{\prime},y_{i}].$

We use the inverse of the response randomization matrix to debias the
privatized responses. Recall the notation $\mathsf{y}$ to represent in vector
form the space of all possible potential outcomes, with similar ordering of
rows and columns as $Q_{c_{i},z_{i}}$. With a small abuse of notation, we
write the index $\tilde{y}_{i}$ of the vector $\mathsf{y}^{T}Q^{-1}_{c,z_{i}}$
as $\mathsf{y}^{T}Q^{-1}_{c,z_{i}}[\tilde{y}_{i}]\,$ and show that it is an
unbiased estimate for $y_{i}$ over the randomness of Algorithm 4. As a result,
by reweighting each privatized outcome by the inverse of its conditional
probability of occurring $Q_{c_{i},z_{i}}[\tilde{y}_{i},y_{i}]$, we propose
the following Horvitz-Thompson-like estimator for the average treatment
effect:

$\displaystyle\hat{\tau_{Q}}:=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\sum_{i\in
c}\left(\mathsf{y}^{T}Q^{-1}_{c,z_{i}}[\tilde{y_{i}}]\frac{z_{i}}{n_{1,c}}-\mathsf{y}^{T}Q^{-1}_{c,z_{i}}[\tilde{y_{i}}]\frac{1-z_{i}}{n_{0,c}}\right)\,.$
(9)

Figure 1: Illustration of Cluster-DP mechanism with a central unit computing
the (clustered) privatized outcomes for valid causal inference.

A proof of the following theorem can be found in the Appendix.

######  Theorem 4.2.

Conditionally on the randomness of the treatment assignment, $\hat{\tau}_{Q}$
is equal in expectation over the randomness of the DP mechanism to the
stratified difference-in-means estimator, such that $\hat{\tau_{Q}}$ is an
unbiased and consistent estimator of $\tau$.

${\mathbb{E}}_{DP}[\hat{\tau}_{Q}|{\bm{z}}]=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\left(\sum_{i=1}^{n}y_{i}(1)\frac{z_{i}}{n_{1,c}}-\sum_{i=1}^{n}y_{i}(0)\frac{1-z_{i}}{n_{0,c}}\right)=\hat{\tau}_{\textsc{No-
DP}}\text{\quad and \quad}{\mathbb{E}}_{DP,{\bm{z}}}[\hat{\tau}_{Q}]=\tau$

For the third parties to compute this estimator themselves, the central unit
must pass along the cluster assignment, the treatment assignment, the
privatized response $\tilde{y}_{i}$, as well as the vector of probabilities
$\mathsf{y}^{T}Q^{-1}_{c,z_{i}}$, as illustrated in Figure 1. Since
$\tilde{q}_{a}(\cdot|c)$ and the responses $\tilde{y_{i}}$ are
${\varepsilon}$-DP, by the post-processing property of differential privacy
(Dwork et al.,, 2014, Proposition 2.1), all the information passed to the
third-party, as well as any estimation based on this information, is also
${\varepsilon}$-DP.

Our goal for Algorithm 4 is to make the gap between the variance of our
differentially-private estimator $\hat{\tau}$ and its non-differentially
private counterpart $\hat{\tau}_{\textsc{No-DP}}$ as small as possible for a
given privacy guarantee. While all our results hold for any given clustering,
they are greatly improved when clusters are homogeneous, as defined below.

######  Definition 4.3 (Cluster homogeneity).

For $a\in\\{0,1\\}$, define a clustering’s homogeneity as the average intra-
cluster variance of outcomes $\phi_{a}\geq 0$, defined as

$\phi_{a}:=\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\frac{S^{2}(\vec{y}_{c}(a))}{n_{a,c}}\,,$

where for any vector $\vec{u}\in\mathbb{R}^{d}$ ,
$S^{2}(\vec{u}):=\frac{1}{d-1}\sum_{u\in\vec{u}}(u-\bar{u})^{2}$ and
$\bar{u}:=\frac{1}{d}\sum_{u\in\vec{u}}u$ .

The quantity $\phi_{a}$ has a natural super-population interpretation when
taking its expectation of over the distribution ${\mathcal{P}}$:
$\phi_{a}={\mathbb{E}}[{\rm Var}(y(a)|c)]={\rm Var}(y(a))-{\rm
Var}({\mathbb{E}}[y(a)|c])>0$. Holding ${\rm Var}(y(a))$ constant, lower
values of $\phi_{a}$ implies that clusters are better separated. For
$\phi_{a}=0$, the outcome values of each clusters are contained within a
singleton set. On the other hand, if $\phi_{a}$ is high, clusters contain a
wide range of responses, up to the variation of outcomes of the entire
population. The following theorem provides a bound on the variance of our
estimator $\hat{\tau}_{Q}$, with respect to the randomness of Algorithm 4 and
the random assignment ${\bm{z}}$, as a function of ${\rm
Var}_{\bm{z}}[\hat{\tau}_{\textsc{No-DP}}]$ and $\phi_{a}$.

######  Theorem 4.4.

The variance of the estimator $\hat{\tau}$ defined in (9) is bounded by

$\displaystyle 0\leq{\rm Var}_{DP,{\bm{z}}}$
$\displaystyle[\hat{\tau_{Q}}]-{\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]\leq\left(\frac{1}{(1-\lambda)^{2}}-1\right)\sum_{a\in\\{0,1\\}}\phi_{a}+\sum_{a\in\\{0,1\\}}\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\frac{A(n_{a,c})}{n_{a,c}},$

where $\phi_{a}$ is the measure of cluster homogeneity defined in Definition
4.3, and for any $x$,

$A(x):=2K\left[\frac{3\|\mathsf{y}\|_{\infty}^{2}+(\lambda\sqrt{K}+1)^{2}+\|\mathsf{y}\|_{2}^{2}(1-\lambda(K-1)\gamma)}{(1-\lambda)^{2}}+2\|\mathsf{y}\|_{\infty}^{2}\right]\left[\gamma+\frac{\sigma}{x}\Big{(}e^{-\gamma
x/{\sigma}}-e^{-x/{\sigma}}\Big{)}\right]\,,$

with $K$ the number of possible potential outcomes and
$\mathsf{y}\in\\{\mathcal{Y}\\}^{K}$ the vector of all possible outcomes.

Theorem 4.1 and Theorem 4.4 together allow us to capture the privacy-variance
trade-off of our proposed mechanism. Recall that the privacy guarantee of
Theorem 4.1 is agnostic to the clustering. On the other hand, the variance gap
in Theorem 4.4 depends first on the homogeneity of clusters, as defined in
Definition 4.3, and a second term that is agnostic to the clustering. As a
result, more homogeneous clusters—those with low $\phi_{a}$—result in a
smaller variance gap with equal privacy guarantees, leading to a better
privacy-variance trade-off than less homogeneous clusters, all else being
equal.

We now provide some intuition for the second term $A(x)$. By choosing $\gamma$
and $\sigma$ to be arbitrarily small, we can make this second term arbitrarily
small. As expected, the privacy guarantees of Theorem 4.1 suffer in that
regime. When setting $\lambda=0$, our Cluster-DP mechanism always outputs the
true outcome, and we no longer produce privatized outcomes. In that case, we
can set the truncation parameter $\gamma$ and the Laplace noise $\sigma$ to be
zero with no consequence to recover the trivial equality ${\rm
Var}_{DP,{\bm{z}}}(\hat{\tau})={\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]$ from our bound above. Naturally, the more interesting setting from a
privacy perspective is $\lambda\in(0,1)$.

As discussed previously, the privacy guarantee in Theorem 4.1 for the Cluster-
DP and Cluster free-DP mechanisms reduces to the guarantee of the uniform-
prior-DP mechanism in Theorem 3.4 when setting the truncation parameter
$\gamma=\nicefrac{{1}}{{K}}$ and $\sigma=\infty$. Yet, because both Cluster-DP
and Cluster-free-DP mechanisms use data-dependent priors, there may exist
choices of $(\sigma$, $\gamma$, $\lambda)$ which result in better privacy-
variance trade-offs than the latter for certain outcome distributions. Rather
than computing the variance gaps of each mechanism in closed-form, we
encourage practitioners to compute their performance empirically for different
values of each mechanism’s parameters, and to keep track of the resulting
privacy guarantee. In the following section, we conduct empirical evaluations
of the privacy-variance trade-off of the different mechanisms.

##  5 Numerical experiments

In this section, we perform a series of simulated experiments to validate the
theoretical claims we make in the paper and to illustrate their usefulness.
Except for Experiment 5, we focus our attention on the Uniform-prior DP,
Cluster-Free-DP, and Cluster-DP mechanisms, due to the strong limitations of
the aggregation-based baselines in our real-world setting compared to these
three user-level privatization schemes.

We start by considering a Gaussian Mixture Model setting where for every unit
$i$ in cluster $c$, a continuous quantity $y_{i}^{\prime}$ is given by

$\forall i\in c,\,y_{i}^{\prime}=\sqrt{\beta}\mu_{c}+\sqrt{v-\beta}w_{i}\,,$
(10)

where $\mu_{c}$ and $w_{i}$ are drawn from the standard normal distribution.
The coefficient $\beta\in[0,v]$ measures the dependence of the response on the
cluster center. This specific parameterization is chosen to fix the variance
of the response, equal to $v$, as $\beta$ varies. Since the proposed mechanism
is for discrete outcome spaces, we quantize the response in the following way:

$y_{i}(1)=y_{i}(0)+\tau\text{\quad and
\quad}y_{i}(0)=\begin{cases}K^{\prime}\text{~{}if~{}}y_{i}^{\prime}>2\sqrt{v}\\\
-K^{\prime}\text{~{}if~{}}y_{i}^{\prime}<-2\sqrt{v}\\\
[y/\Delta]\text{~{}otherwise}\end{cases}$

where $\Delta:=2\sqrt{v}/K^{\prime}$ and $[x]$ denotes the rounding of $x$ to
the nearest integer. The treatment effect is an additive $\tau$ term on the
potential outcome under control. We fix $\tau=1$, such that the outcomes take
values in the set
$\mathcal{Y}=\\{-K^{\prime},\dotsc,0,\dotsc,K^{\prime},K^{\prime}+1\\}$. We
denote by $K:=2(K^{\prime}+1)$ the size of outcome space.

Unless otherwise specified, and with no particular reason to fix parameters
one way or another, we take $K^{\prime}=5$, $v=5$, and $\beta=4.5$. We
consider $C=3$ clusters of sizes $500$, $10^{3}$, $2\times 10^{3}$ with an
equal number of controlled and treated units in each cluster. To display
confidence intervals around certain results, we consider a super-population of
three clusters of sizes $2.5\times 10^{3}$, $5\times 10^{3}$, and $10^{4}$
units, and repeatedly draw uniformly at random sub-populations of three
clusters from these original clusters.

For any given sub-population, we compute the variance ${\rm
Var}_{DP,{\bm{z}}}[\hat{\tau}_{Q}]$ by empirically computing the variance (or
histogram) of $\hat{\tau}_{Q}$ empirically over $500$ realizations of the
randomness in the corresponding DP mechanism (e.g. Laplace noise and response
randomization), as well as the treatment assignments, which are done by
choosing balanced set of treated and controlled units uniformly at random
within each cluster. Unless otherwise specified, for the Cluster-DP mechanism,
we set the truncation parameter $\gamma=0.02$, the Laplace noise $\sigma=10$,
and the resampling probability $\lambda=0.8$.

##### Experiment 1. (Bias and Gaussianity)

We first verify that our Cluster-DP estimator $\hat{\tau_{Q}}$, given by (9),
is unbiased and admits an asymptotically Gaussian distribution by plotting the
histogram and the qq-plot of $\hat{\tau}-\tau$ in Figures 2 and 3.

Figure 2: histogram of $\hat{\tau}-\tau$

Figure 3: qq-plot of $\hat{\tau}-\tau$

##### Experiment 2. (Privacy-variance trade-off)

We next compare the privacy-variance trade-off of our suggested Cluster-DP
mechanism with that of the Cluster-Free-DP mechanism, as well as the
stratified and unstratified versions of the Uniform-prior-DP mechanism. We
observe that the Cluster-DP can have significantly lower variance for its
estimator, compared to the other mechanisms, for the same privacy loss
(${\varepsilon},\delta$).

In Figure 4, we aim to fix the privacy loss to ${\varepsilon}=0.2$ and
$\delta=10^{-4}$ for all three mechanisms. For the Cluster-DP and Cluster-
Free-DP, we set the Laplace parameter to $\sigma=10$, and vary the truncation
parameter $\gamma\in[0.1/K,1/K]$. Following Theorem 4.1, we first choose
$\tilde{{\varepsilon}}$ so that the corresponding privacy ${\varepsilon}$, is
equal to its target ${\varepsilon}=0.2$, and then choose the re-sampling
probability $\lambda$ to obtain the failure probability $\delta=10^{-4}$.
Likewise, for the Uniform-prior-DP, we set the re-sampling probability
$\lambda$ according to Theorem 3.4, such that ${\varepsilon}=0.2$ and
$\delta=10^{-4}$. In summary, as the truncation parameter $\gamma$ varies, we
compare the three mechanisms at the same privacy loss. As we observe in Figure
4, for small values of $\gamma$, the Cluster-DP achieves significantly lower
variance compared to to the other mechanisms. When
$\gamma=\nicefrac{{1}}{{K}}$ and $\sigma=\infty$, the theory tells us that
Cluster-DP reduces to uniform-prior-DP (stratified) and the Cluster free-DP
reduces to uniform-prior-DP (unstratified). However, since we have set
$\sigma=10$, we observe that the variance for the uniform-prior-DP becomes
lower than the other mechanisms for $\gamma=\nicefrac{{1}}{{K}}$. The error-
bars here correspond to 50 independent draws of the sub-population.

In Figure 5, we plot the variance of the estimators versus the privacy loss
${\varepsilon}$, as we fix $\delta=10^{-4}$. Here, we optimize the choice of
Laplace parameter $\sigma\in\\{10,20,\infty\\}$ and the truncation parameter
$\gamma\in\\{\nicefrac{{0.01}}{{K}},\nicefrac{{0.1}}{{K}},\nicefrac{{1}}{{K}}\\}$.
We observe that both Cluster-DP and Cluster free-DP estimators, which use
data-dependent priors achieve a better trade-off than either version of the
Uniform-prior-DP mechanism. Furthermore, the Cluster-DP mechanism, which also
leverages the clustering structure, showcases an even better trade-off
compared to the Cluster free-DP mechanism.

Figure 4: Variances for the DP mechanisms, as we vary the truncation level
$\gamma\in[0.1/K,1/K]$, under the setting of Experiment 2. The privacy loss is
fixed at ${\varepsilon}=0.2$ and $\delta=10^{-4}$.

Figure 5: Privacy-variance trade-off for the four DP mechanisms under the
setting of Experiment 2. We fix the failure probability in DP guarantee to
$\delta=10^{-4}$, and optimize the choice of $\sigma$ and $\gamma$ in the sets
$\sigma\in\\{10,20,\infty\\}$ and
$\gamma\in\\{\nicefrac{{0.01}}{{K}},\nicefrac{{0.1}}{{K}},\nicefrac{{1}}{{K}}\\}$.

##### Experiment 3. (Role of clustering quality)

In this experiment we show that, as the clustering quality improves, the
variance of the estimator for the cluster-DP mechanism decreases when compared
to the variance of the estimator for the cluster free-DP mechanism, without
affecting their privacy guarantees, since these are agnostic to the clustering
according to Theorem 4.1. Under our specified potential outcome model (10),
the cluster homogeneity $\phi_{a}$, as defined in Definition 4.3, is given by
$\phi_{0}={\mathbb{E}}({\rm Var}(y_{i}(0)|c))\propto v-\beta=\phi_{1}$, hence
our clusters become more homogeneous as $\beta$ increases. From Theorem 4.4,
the clustering structure reduces the variance of the estimator at more
homogeneous clusters, i.e. lower values of $\phi_{0},\phi_{1}$, and $\lambda$.
We verify this in Figure 6, which plots the ratio of the variances for two
values of $\lambda\in\\{0.5,0.8\\}$ as we vary $\beta$ . As $\beta$ grows, we
observe a stronger reduction in the variance using the clustering structure of
data. This effect is stronger at smaller values of $\lambda$.

Figure 6: Ratio of the variance of the estimators under the cluster-DP and
cluster free-DP mechanisms in Experiment 3. The benefit of cluster-DP
mechanism is stronger at larger $\beta$ and smaller value of $\lambda$.

##### Experiment 4. (Validation of theoretical bound)

In Theorem 4.4, we bounded the excess variance of the private estimator (9)
compared to the non-private estimator (2). The bound had two additive terms.
The first one depends on the cluster structure of data, namely the cluster
homogeneity quantities $\phi_{0}$, $\phi_{1}$, and the second term did not
depend on the clusters, capturing instead an increase in the variance due to
the randomness of the Cluster-DP mechanism. In Figure 7, we compute the gap
${\rm Var}_{DP,{\bm{z}}}[\hat{\tau}]-{\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-DP}}]$ empirically, by averaging over
500 different realizations of the randomness in the DP mechanism and the
treatment assignments in the same setting as the previous experiment. We plot
this gap as we vary $\beta$, along with a shaded region whose upper boundary
corresponds to the upper bound given in Theorem 4.4 and its lower boundary
corresponds to only the first term in that bound. We observe that the variance
gap remains in the shaded area which validates the theoretical upper bound
given by Theorem 4.4, and shows that the derived bound is tight, up to the
second term.

Figure 7: The variance gap between the private estimator $\hat{\tau}_{Q}$,
given by (9), and the non-private estimator $\hat{\tau}_{\textsc{No-DP}}$ in
the setting of Experiment 4. The upper boundary of the shaded area corresponds
to the upper bound derived in Theorem 4.4, and it lower boundary corresponds
to the the first term in that bound. As we see the gap remains between the two
boundaries.

##### Experiment 5. (Comparisons with aggregation-based baselines)

Figure 8: Bias of the cluster-DP, noisy Horvitz-Thompson and noisy histogram
estimators under one shot communication between the central unit and the
advertisers in the setting of Experiment 5.

We next compare the privacy-variance trade-off of the estimator based on the
cluster-DP mechanism with the other baselines discussed in Section 3, namely
the noisy Horvitz-Thompson estimator and the noisy histogram estimator. The
goal of this experiment is to show that in the case of one-shot communication
between the central unit and the advertisers, the cluster-DP estimator
achieves lower finite-sample conditional bias than the other two baselines. To
demonstrate this point, we fix the noise and randomization in each DP
mechanisms for the super-population and compute the bias of each estimator
with respect to random draws from the super-population and of the treatment
assignments. Specifically we compute the expectation of the treatment effect
estimator over 500 sub-populations, each consisting of $500$, $1000$, $2000$
units from each cluster, uniformly at random with a balanced number of treated
and controlled units in each cluster. The bias is then computed as the
difference between the expectation of the estimator and the true treatment
effect. As we see in Figure 8, Cluster-DP estimator achieves a lower
conditional bias compared to the other two baselines, as we vary the privacy
loss ${\varepsilon}$. The error bars are obtained by considering 50 different
realizations of the noise/randomization in the DP mechanisms.

###  5.1 Simulation on the Youtube social network

Figure 9: qqplot of $\hat{\tau}-\tau$, with $\hat{\tau}$ the Cluster-DP
estimator using $500$ realizations of randomness in the outcomes and the DP
mechanism.

Figure 10: Privacy-variance trade-off of the Cluster-DP and Cluster free-DP
stratified estimators. The dotted line represents the variance of the non-
private stratified estimator.

We now use a subset of the Youtube social network to replicate two experiment
results in a setting with natural clusters. First, we demonstrate that the
proposed stratified estimator combined with the Cluster-DP mechanism is
unbiased and admits a Gaussian distribution, replicating the results of
Experiment 1. We then compare the variance of our suggested estimator for the
Cluster-DP mechanism with its variance when using the Cluster free-DP
mechanism to show the benefit of leveraging the clustering structure,
replicating the results of Experiment 2.

The Youtube social network dataset (Leskovec and Krevl,, 2014) contains the
friendship links of a set of users on Youtube, and the ground-truth clusters
correspond to groups created by users. We form a smaller dataset, by
considering only the 50 largest communities, which includes a total of
$22{,}179$ users with a minimum cluster size of 199. We generate the potential
outcomes for the users as follows:

$\displaystyle y_{i}(0)=x_{i}^{\sf T}\beta+w_{i}\,,\quad
y_{i}(1)=y_{i}(0)+\tau\,,$

with $w_{i}\sim{\sf N}(0,v^{2})$ capturing individual $i$’s effect and the
$x_{i}^{\sf T}\beta$ term capturing the cluster-level effect. We follow a
similar model as in (Zhou et al.,, 2020) and consider a four-dimensional
feature vector $x_{i}$, with $x_{i1}$ being the number of nodes in cluster
$c_{i}$ (the cluster of user $i$), $x_{i2}$ the number of edges in $c_{i}$,
$x_{i3}$ the number of edges in $c_{i}$ with other clusters, and $x_{i4}$ the
density of cluster $c_{i}$. Recall that for a cluster with $n$ nodes and $e$
edges, its density is defined as $e\times{n\choose 2}^{-1}$.

Since the proposed mechanism is for discrete outcome spaces, we quantize the
responses into $K=8$ levels. We standardize the features by making each of the
four features zero mean and unit norm across clusters, and setting the
standard deviation of the Gaussian noise $w_{i}$ to $v=0.1$. In our
experiments, we set $\beta=(1,1,1,1)^{\sf T}$ and $\tau=1$. In the Cluster-DP
mechanism, we set the truncation threshold to $\gamma=0.1/K$ and the Laplace
noise level to $\sigma=5$.

Figure 9 shows the qqplot of $\hat{\tau}-\tau$ with $\hat{\tau}$ being the
Cluster-DP mechanism, using $500$ realizations of the randomness in the
outcomes and the DP mechanism. As the plot demonstrates $\hat{\tau}$ is an
unbiased and Gaussian estimator. In Figure 10, we plot the privacy-variance
trade-off for the Cluster-DP and the Cluster free-DP mechanisms, along with
the variance of the non-private stratified estimator, finding once again that
the Cluster-DP mechanism achieves a better trade-off by leveraging the natural
cluster structure of the Youtube users.

## Acknowledgement

We would like to thank Nick Doudchenko, Ian Waudby-Smith, and many others for
helpful discussions on this work.

## References

  * Bassily et al., (2018) Bassily, R., Thakurta, A. G., and Thakkar, O. D. (2018).  Model-agnostic private learning.  Advances in Neural Information Processing Systems.
  * Beimel et al., (2013) Beimel, A., Nissim, K., and Stemmer, U. (2013).  Private learning and sanitization: Pure vs. approximate differential privacy.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 363–378. Springer.
  * Betlei et al., (2021) Betlei, A., Gregoir, T., Rahier, T., Bissuel, A., Diemert, E., and Amini, M.-R. (2021).  Differentially private individual treatment effect estimation from aggregated data.  hal-03339723.
  * Chaudhuri and Hsu, (2011) Chaudhuri, K. and Hsu, D. (2011).  Sample complexity bounds for differentially private learning.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 155–186. JMLR Workshop and Conference Proceedings.
  * Cohen et al., (2021) Cohen, E., Kaplan, H., Mansour, Y., Stemmer, U., and Tsfadia, E. (2021).  Differentially-private clustering of easy instances.  In International Conference on Machine Learning, pages 2049–2059. PMLR.
  * (6) Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. (2006a).  Our data, ourselves: Privacy via distributed noise generation.  In Advances in Cryptology-EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486–503. Springer.
  * (7) Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006b).  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer.
  * Dwork et al., (2014) Dwork, C., Roth, A., et al. (2014).  The algorithmic foundations of differential privacy.  Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407.
  * Esfandiari et al., (2022) Esfandiari, H., Mirrokni, V., Syed, U., and Vassilvitskii, S. (2022).  Label differential privacy via clustering.  In International Conference on Artificial Intelligence and Statistics, pages 7055–7075. PMLR.
  * Feldman et al., (2009) Feldman, D., Fiat, A., Kaplan, H., and Nissim, K. (2009).  Private coresets.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 361–370.
  * Feldman et al., (2017) Feldman, D., Xiang, C., Zhu, R., and Rus, D. (2017).  Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks.  In Proceedings of the 16th ACM/IEEE International Conference on Information Processing in Sensor Networks, pages 3–15.
  * Ghazi et al., (2021) Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., and Zhang, C. (2021).  Deep learning with label differential privacy.  Advances in neural information processing systems, 34:27131–27145.
  * Ghazi et al., (2022) Ghazi, B., Kamath, P., Kumar, R., Leeman, E., Manurangsi, P., Varadarajan, A., and Zhang, C. (2022).  Regression with label differential privacy.  arXiv preprint arXiv:2212.06074.
  * Imbens and Rubin, (2015) Imbens, G. W. and Rubin, D. B. (2015).  Causal inference in statistics, social, and biomedical sciences.  Cambridge University Press.
  * Kairouz et al., (2015) Kairouz, P., Oh, S., and Viswanath, P. (2015).  The composition theorem for differential privacy.  In International conference on machine learning, pages 1376–1385. PMLR.
  * Kancharla and Kang, (2021) Kancharla, M. and Kang, H. (2021).  A robust, differentially private randomized experiment for evaluating online educational programs with sensitive student data.  arXiv preprint arXiv:2112.02452.
  * Kasiviswanathan et al., (2011) Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., and Smith, A. (2011).  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826.
  * Leskovec and Krevl, (2014) Leskovec, J. and Krevl, A. (2014).  SNAP Datasets: Stanford large network dataset collection.  http://snap.stanford.edu/data.
  * Li et al., (2006) Li, N., Li, T., and Venkatasubramanian, S. (2006).  t-closeness: Privacy beyond k-anonymity and l-diversity.  In 2007 IEEE 23rd international conference on data engineering, pages 106–115. IEEE.
  * Machanavajjhala et al., (2007) Machanavajjhala, A., Kifer, D., Gehrke, J., and Venkitasubramaniam, M. (2007).  l-diversity: Privacy beyond k-anonymity.  ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1):3–es.
  * Narayanan and Shmatikov, (2008) Narayanan, A. and Shmatikov, V. (2008).  Robust de-anonymization of large sparse datasets.  In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages 111–125. IEEE.
  * Nissim et al., (2007) Nissim, K., Raskhodnikova, S., and Smith, A. (2007).  Smooth sensitivity and sampling in private data analysis.  In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75–84.
  * Niu et al., (2022) Niu, F., Nori, H., Quistorff, B., Caruana, R., Ngwe, D., and Kannan, A. (2022).  Differentially private estimation of heterogeneous causal effects.  In Conference on Causal Learning and Reasoning, pages 618–633. PMLR.
  * Nori et al., (2021) Nori, H., Caruana, R., Bu, Z., Shen, J. H., and Kulkarni, J. (2021).  Accuracy, interpretability, and differential privacy via explainable boosting.  In International Conference on Machine Learning, pages 8227–8237. PMLR.
  * Panigrahi et al., (2022) Panigrahi, S., Wang, J., and He, X. (2022).  Treatment effect estimation with efficient data aggregation.  arXiv preprint arXiv:2203.12726.
  * Stemmer and Kaplan, (2018) Stemmer, U. and Kaplan, H. (2018).  Differentially private k-means with constant multiplicative error.  Advances in Neural Information Processing Systems, 31.
  * Sweeney, (2000) Sweeney, L. (2000).  Simple demographics often identify people uniquely.  Health (San Francisco), 671(2000):1–34.
  * Sweeney, (2002) Sweeney, L. (2002).  k-anonymity: A model for protecting privacy.  International journal of uncertainty, fuzziness and knowledge-based systems, 10(05):557–570.
  * Wang and Xu, (2019) Wang, D. and Xu, J. (2019).  On sparse linear regression in the local differential privacy model.  In International Conference on Machine Learning, pages 6628–6637. PMLR.
  * Wasserman and Zhou, (2010) Wasserman, L. and Zhou, S. (2010).  A statistical framework for differential privacy.  Journal of the American Statistical Association, 105(489):375–389.
  * Zhou et al., (2020) Zhou, Y., Liu, Y., Li, P., and Hu, F. (2020).  Cluster-adaptive network a/b testing: From randomization to estimation.  arXiv preprint arXiv:2008.08648.

##  Appendix A Appendix

###  A.1 Notation and common formulas

We recall here all the notations used in the paper and in the proofs:

  * •

$n$: total number of units.

  * •

$n_{0}$ (resp $n_{1}$): total number of controlled (resp. treated) units.

  * •

$z_{i}\in\\{0,1\\}$: the treatment assignment of unit $i$. $z_{i}=1$ (resp.
$0$) implies unit $i$ is treated (resp. controlled).

  * •

$\mathcal{Y}$: response space of cardinality $K=|\mathcal{Y}|<\infty$.

  * •

$y_{i}(z)\in\mathcal{Y}$: the potential treatment outcome of unit $i$ under
treatment assignment value $z$.

  * •

$\tilde{y_{i}}\in\mathcal{Y}$: privatized outcome of unit $i$ returned by the
DP mechanism.

  * •

$\mathsf{y}=(y)_{y\in\mathcal{Y}}\;$: vector notation of the entire response
space.

  * •

$\mathcal{C}$: set of all clusters of cardinality $C=|\mathcal{C}|<\infty$.

  * •

$c_{i}$: cluster of unit $i$.

  * •

$n_{c}=|\\{i\in[n]:c_{i}=c\\}|$: number of units in cluster $c$.

  * •

$\mathcal{O}_{a,c}:=\left\\{i:\;c_{x_{i}}=c,z_{i}=a\right\\}\;$: units
belonging to cluster $c$ and treatment assignment $z_{i}=a$.

  * •

$\mathcal{O}_{c}:=\left\\{i:\;c_{i}=c\right\\}\;$: units belonging to cluster
$c$

  * •

$n_{a,c}=|\mathcal{O}_{a,c}|$ for $a\in\\{0,1\\}$.

  * •

$\gamma\in[0,1/K]$: minimum of clipped empirical distribution

  * •

$\sigma$: noise scale

  * •

$1-\lambda\in[0,1]$: true response sampling probability

  * •

$p_{a}(y|x)={\mathbb{P}}(Y(a)=y|X=x)$: true distribution for treated ($a=1$)
and controlled ($a=0$) units.

  * •

$p_{a}(y|c)={\mathbb{P}}(Y(a)=y|c_{X}=c)$: true distribution for treated
($a=1$) and controlled ($a=0$) units within cluster $c$.

  * •

$\hat{p}_{a}(y|c)=\dfrac{|\\{i:\;c_{x_{i}}=c,z_{i}=a,y_{i}=y\\}|}{|\\{i:\;c_{x_{i}}=c,z_{i}=a\\}|}$:
empirical distribution for treated ($a=1$) and controlled ($a=0$) units within
cluster $c$.

  * •

When the context is clear, we sometimes adopt this lightened notation:

    * –

$\hat{p}_{\ell}=\frac{1}{n_{0,c}}|\\{i\in\mathcal{O}_{0,c}:y_{i}=\ell\\}|$ :
empirical probability of outcome $\ell$ for the controlled units in cluster
$c$

    * –

$\hat{\bm{p}}=[\hat{p}_{l}]_{l\in\mathcal{Y}}\in{\mathbb{R}}^{K\times 1}$:
empirical distribution of outcomes of the controlled units in cluster $c$,
arranged into a $K$-dimensional vector, with coordinates $\hat{p}_{\ell}$.

  * •

$\phi_{a}={\rm Var}({\mathbb{E}}[Y(a)|c_{X}])$: clustering quality

  * •

$Q_{c,a}[y^{\prime},y]=(1-\lambda){\mathbb{I}}(y^{\prime}=y)+\lambda\tilde{q}_{a}(y^{\prime}|c)\;$:
response randomization matrix

  * •

When the context is clear, we sometimes adopt this lightened notation

    * –

$Q=Q_{c,0}$

    * –

$Q_{a,b}=Q_{c,0}[a,b]$,

    * –

$Q^{-1}_{a,b}=Q^{-1}_{c,0}[a,b]$,

    * –

$Q^{-{\sf T}}=(Q^{-1})^{\sf T}$.

    * –

$\tilde{\bm{q}}=[\tilde{q}_{0}(y|c)]_{y\in\mathcal{Y}}\in{\mathbb{R}}^{K\times
1}$ the distribution constructed in the DP mechanism (after adding noise to
empirical distribution $\hat{p}_{0,D}$, truncation and normalization)

    * –

$\tilde{q}_{l}$: coordinate $l$ of vector $\tilde{\bm{q}}$.

  * •

$u_{a,c}:=\sum_{i\in\mathcal{O}_{a,c}}\sum_{y^{\prime}\in\mathcal{Y}}Q_{c_{i},a}^{-1}[y^{\prime},\tilde{y}_{i}]y^{\prime}\,.$

  * •

$\vec{y}_{a,c}:=\\{y_{i}(a):i\in{\cal O}_{a,c}\\}$, for $a\in\\{0,1\\}$. Note
that $\vec{y}_{a,c}$ is observed by the experimenter.

  * •

$\vec{y}_{c}(a):=\\{y_{i}(a):c_{i}=c\\}$. Note that $\vec{y}_{c}(a)$ contains
unobserved values.

  * •

$e_{\ell}\in{\mathbb{R}}^{K\times 1}$ with $1$ at the $\ell$-th position and
zero everywhere else

  * •

$A(x)=2K\Big{\\{}B^{2}\Big{(}\frac{3}{(1-\lambda)^{2}}+2\Big{)}+\frac{(\lambda\sqrt{K}+1)^{2}}{(1-\lambda)^{2}}\|\mathcal{Y}\|^{2}(1-\lambda(K-1)\gamma)\Big{\\}}\Big{[}\gamma+\frac{\sigma}{x}\Big{(}e^{-\gamma
x/{\sigma}}-e^{-x/{\sigma}}\Big{)}\Big{]}\,$: recurring expression in variance
bounds.

We now state the well-known expression for the variance of the stratified
Horvitz-Thompson estimator, which we recall below:

$\displaystyle\hat{\tau}_{\textsc{No-
DP}}:=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\sum_{i\in
c}\left(\frac{y_{i}z_{i}}{n_{1,c}}-\frac{y_{i}(1-z_{i})}{n_{0,c}}\right)\,.$

Let $\vec{y}_{c}:=\\{y_{i}:c_{i}=c\\}\in\mathcal{Y}^{n_{c}}$ be the vector of
outcomes of units in cluster $c$, and
$\vec{\tau}_{c}:=\vec{y}_{c}(1)-\vec{y}_{c}(0)$ be the vector of the
differences between each unit’s potential outcome in treatment and in control.
The variance of $\hat{\tau}_{\textsc{No-DP}}$ is given by

${\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]=\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left(\frac{S^{2}(\vec{y}_{c}(1))}{n_{1,c}}+\frac{S^{2}(\vec{y}_{c}(0))}{n_{0,c}}-\frac{S^{2}(\vec{\tau}_{c})}{n_{c}}\right)\,,$

where, for any vector $u\in\mathbb{R}^{d}$ ,
$S^{2}(\vec{u}):=\frac{1}{d-1}\sum_{u\in\vec{u}}(u-\bar{u})^{2}$ and
$\bar{u}:=\frac{1}{d}\sum_{u\in\vec{u}}u$ . The formula for ${\rm
Var}_{\bm{z}}[\hat{\tau}^{u}_{\textsc{No-DP}}]$ can be obtained from the
formula above where all units belong to a single cluster $|\mathcal{C}|=1$ and
$n_{c}=n$.

###  A.2 Proof of Proposition 3.1 and 3.2

We start by proving Proposition 3.1. Recall the noisy Horvitz-Thompson
estimator $\hat{\tau}$ given by (1):

$\displaystyle\hat{\tau}:=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\left\\{\sum_{i\in
c}\left(\frac{y_{i}z_{i}}{n_{1,c}}-\frac{y_{i}(1-z_{i})}{n_{0,c}}\right)+w_{c}\right\\}\,,w_{c}\sim\text{Laplace}(\eta_{c})\,.$

To show its privacy guarantee, we apply (Dwork et al.,, 2014, Theorem 3.6).
Consider the sensitivity $\Delta_{c}$ of the inner function
$\nicefrac{{1}}{{n_{1,c}}}y_{i}z_{i}-\nicefrac{{1}}{{n_{0,c}}}y_{i}(1-z_{i})$,
defined as the maximum change in its value when changing only one label in the
data set. Since the assignments are not private, we keep them intact in
computing the sensitivity. Therefore, changing only on label will change the
inner function by at most
$\Delta_{c}=\min\\{n_{0,c},n_{1,c}\\}^{-1}\times\max_{y\in\mathcal{Y}}|y|$. By
using (Dwork et al.,, 2014, Theorem 3.6), adding Laplace noise with parameter
$\nicefrac{{\Delta_{c}}}{{{\varepsilon}}}$ will make each of the inner terms
${\varepsilon}$-DP and by the post-processing property (Dwork et al.,, 2014,
Proposition 2.1 ), $\hat{\tau}$ is also ${\varepsilon}$-DP.

For the variance, recall the non-differentially-private Horvitz-Thompson
estimator $\hat{\tau}_{\textsc{No-DP}}$ from (2), by which we can write

$\displaystyle\hat{\tau}=\hat{\tau}_{\textsc{No-
DP}}+\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}w_{c}\,.$

Since $w_{c}$ are drawn independently from each other and also independent
from the assignments $z_{i}$, we have

$\displaystyle{\rm Var}_{DP,{\bm{z}}}[\hat{\tau}]$ $\displaystyle={\rm
Var}_{DP,{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\sum_{c\in\mathcal{C}}\left(\frac{n_{c}}{n}\right)^{2}{\rm Var}[w_{c}]$
$\displaystyle={\rm Var}_{DP,{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+2\sum_{c\in\mathcal{C}}\left(\frac{n_{c}}{n}\frac{\Delta_{c}}{{\varepsilon}}\right)^{2}\,,$

where the last step holds because $w_{c}\sim\text{Laplace}(\eta_{c})$ with
$\eta_{c}=\nicefrac{{\Delta_{c}}}{{{\varepsilon}}}$.

We next proceed with proving Proposition 3.2. Its privacy guarantee follows
easily from the fact that $\hat{p}_{a}(y|c)$ has sensitivity
$\nicefrac{{1}}{{n_{a,c}}}$ (histogram queries) and therefore adding
independent draws from Laplace($(n_{a,c}{\varepsilon})^{-1}$) to the frequency
of each value will make the histogram ${\varepsilon}$-DP. To prove the claim
on its variance, we note that the non-private Horvitz-Thompson estimator can
be written as

$\displaystyle\hat{\tau}_{\textsc{No-
DP}}=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\left(\sum_{y\in\mathcal{Y}}y\hat{p}_{1}(y|c)-\sum_{y\in\mathcal{Y}}y\hat{p}_{0}(y|c)\right)\,.$

Therefore, we can write the noisy Histogram estimator (3) as

$\displaystyle\hat{\tau}$
$\displaystyle=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\sum_{y\in\mathcal{Y}}y(\hat{p}_{1}(y|c)+w_{1,c,y}-p_{0}(y|c)-w_{0,c,y})$
$\displaystyle=\hat{\tau}_{\textsc{No-
DP}}+\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\sum_{y\in\mathcal{Y}}y(w_{1,c,y}-w_{0,c,y})\,.$

Since $w_{a,c,y}$ are independent from each other and
$w_{a,c,y}\sim\text{Laplace}(\eta_{a,c})$, we get

$\displaystyle{\rm Var}_{DP,{\bm{z}}}[\hat{\tau}]$ $\displaystyle={\rm
Var}_{DP,{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\sum_{c\in\mathcal{C}}\sum_{y\in\mathcal{Y}}\left(\frac{n_{c}}{n}y\right)^{2}({\rm
Var}[w_{1,c,y}]+{\rm Var}[w_{0,c,y}])$ $\displaystyle={\rm
Var}_{DP,{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\left(\sum_{y\in\mathcal{Y}}y^{2}\right)\sum_{c\in\mathcal{C}}\left(\frac{n_{c}}{n}\right)^{2}(2\eta_{1,c}^{2}+2\eta_{0,c}^{2})$
$\displaystyle={\rm Var}_{DP,{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\frac{2}{{\varepsilon}^{2}}\left(\sum_{y\in\mathcal{Y}}y^{2}\right)\sum_{c\in\mathcal{C}}\left(\frac{n_{c}}{n}\right)^{2}\left(\frac{1}{n_{1,c}^{2}}+\frac{1}{n_{0,c}^{2}}\right)\,.$

This completes the proof of Proposition 3.2.

###  A.3 Proof of Theorem 3.4

Because the Uniform-Prior DP mechanism is a special case of the Cluster-DP
mechanism, we follow the proof of Theorem 4.4, which is detailed below and
which the reader might prefer reading first. In this special case, we can
obtain an exact form for the variance gap. Hence, we continue from (27), which
in the case that there is no Laplace noise added, reads as

$\displaystyle{\rm
Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})=n_{0,c}\mathsf{y}^{\sf T}Q^{-1}{\rm
diag}(Q\hat{\bm{p}})Q^{-{\sf
T}}\mathsf{y}-\sum_{i\in\mathcal{O}_{0,c}}y_{i}^{2}(0)\,.$ (11)

Note that we are using the lightened notation $\hat{\bm{p}}$ to indicate the
empirical distribution of outcomes of the controlled units in cluster $c$.

In the mechanism described by Algorithm 4, $\tilde{\bm{q}}$ is data-dependent
and so correlated to $\hat{\bm{p}}$. In that case, we analyzed the first term
via the decomposition ${\rm diag}(Q\hat{\bm{p}})={\rm
diag}(Q\tilde{\bm{q}})+{\rm diag}(Q(\hat{\bm{p}}-\tilde{\bm{q}}))$ and
bounding $\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}$. In the current case that
$\tilde{\bm{q}}$ is the uniform distribution, this approach is not tight as
$\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}$ would be large. However, since
$\tilde{\bm{q}}$ (and therefore $Q$) is data-independent we can directly
analyze the first term as follows:

$\displaystyle\mathsf{y}^{\sf T}Q^{-1}{\rm diag}(Q\hat{\bm{p}})Q^{-{\sf
T}}\mathsf{y}$ $\displaystyle=\frac{1}{(1-\lambda)^{2}}\mathsf{y}^{\sf
T}\left(I-\frac{\lambda}{K}\bm{1}\bm{1}^{\sf T}\right){\rm
diag}\left((1-\lambda)\hat{\bm{p}}+\frac{\lambda}{K}\bm{1}\right)\left(I-\frac{\lambda}{K}\bm{1}\bm{1}^{\sf
T}\right)\mathsf{y}$ $\displaystyle=\mathsf{y}^{\sf
T}\Big{\\{}\frac{1}{(1-\lambda)}{\rm
diag}(\hat{\bm{p}})+\frac{\lambda}{K(1-\lambda)^{2}}{\rm
diag}(\bm{1})-\frac{2\lambda}{K(1-\lambda)}\bm{1}\hat{\bm{p}}^{\sf
T}-\frac{\lambda^{2}}{K^{2}(1-\lambda)^{2}}\bm{1}\bm{1}^{\sf
T}\Big{\\}}\mathsf{y}$
$\displaystyle=\frac{\overline{\bm{y}_{0,c}^{2}}}{(1-\lambda)}+\frac{\lambda\overline{y^{2}}}{(1-\lambda)^{2}}-\frac{2\lambda\bar{y}}{(1-\lambda)}\overline{\bm{y}_{0,c}}-\frac{\lambda^{2}\bar{y}^{2}}{(1-\lambda)^{2}}$
$\displaystyle=\frac{\overline{\bm{y}_{0,c}^{2}}}{(1-\lambda)}+\frac{\lambda\overline{y^{2}}-\lambda^{2}\bar{y}^{2}}{(1-\lambda)^{2}}-\frac{2\lambda\bar{y}}{(1-\lambda)}\overline{\bm{y}_{0,c}}\,,$
(12)

where we use the shorthand

$\overline{\bm{y}_{0,c}^{2}}=\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}^{2}(0)\,,\quad\overline{\bm{y}_{0,c}}=\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)\,.$

Using (12) in (11), we arrive at

$\displaystyle{\rm Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})$
$\displaystyle=n_{0,c}\left[\frac{\overline{\bm{y}_{0,c}^{2}}}{(1-\lambda)}+\frac{\lambda\overline{y^{2}}-\lambda^{2}\bar{y}^{2}}{(1-\lambda)^{2}}-\frac{2\lambda\bar{y}}{(1-\lambda)}\overline{\bm{y}_{0,c}}\right]-n_{0,c}\overline{\vec{y}_{0,c}^{2}}$
$\displaystyle=n_{0,c}\left[\frac{\lambda}{1-\lambda}\overline{\bm{y}_{0,c}^{2}}+\frac{\lambda\overline{y^{2}}-\lambda^{2}\bar{y}^{2}}{(1-\lambda)^{2}}-\frac{2\lambda\bar{y}}{(1-\lambda)}\overline{\bm{y}_{0,c}}\right]\,.$

Invoking (23), the above characterization yields the following:

$\displaystyle{\rm Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})=$
$\displaystyle\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left[\frac{\lambda}{1-\lambda}\left(\frac{\overline{\bm{y}_{0,c}^{2}}}{n_{0,c}}+\frac{\overline{\bm{y}_{1,c}^{2}}}{n_{1,c}}\right)-\frac{2\lambda\bar{y}}{(1-\lambda)}\left(\frac{\overline{\bm{y}_{0,c}}}{n_{0,c}}+\frac{\overline{\bm{y}_{1,c}}}{n_{1,c}}\right)\right]$
$\displaystyle+\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left(\frac{1}{n_{0,c}}+\frac{1}{n_{1,c}}\right)\frac{\lambda\overline{y^{2}}-\lambda^{2}\bar{y}^{2}}{(1-\lambda)^{2}}\,.$
(13)

We next compute ${\mathbb{E}}_{{\bm{z}}}[{\rm
Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]$. Since we are fixing $n_{a,c}$
for each cluster, we have ${\mathbb{P}}(z_{i}=a)=\frac{n_{a,c}}{n_{c}}$ for
$i\in{\cal O}_{c}$ and $a\in\\{0,1\\}$. We therefore have

$\displaystyle{\mathbb{E}}_{{\bm{z}}}[\overline{\bm{y}_{a,c}}]={\mathbb{E}}_{{\bm{z}}}\left[\frac{1}{n_{a,c}}\sum_{i\in{\cal
O}_{c}}{\mathbb{I}}(z_{i}=a)y_{i}(a)\right]=\frac{1}{n_{c}}\sum_{i\in{\cal
O}_{c}}y_{i}(a)=\overline{\vec{y}_{c}(a)}\,.$

Likewise we have
${\mathbb{E}}_{{\bm{z}}}[\overline{\bm{y}^{2}_{a,c}}]=\overline{\vec{y}^{2}_{c}(a)}$.
Using this identities in (13), we obtain

$\displaystyle{\mathbb{E}}_{{\bm{z}}}[{\rm
Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]=$
$\displaystyle\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left[\frac{\lambda}{1-\lambda}\left(\frac{\overline{\bm{y}_{c}^{2}(0)}}{n_{0,c}}+\frac{\overline{\bm{y}_{c}^{2}(1)}}{n_{1,c}}\right)-\frac{2\lambda\bar{y}}{(1-\lambda)}\left(\frac{\overline{\bm{y}_{c}(0)}}{n_{0,c}}+\frac{\overline{\bm{y}_{c(1)}}}{n_{1,c}}\right)\right]$
$\displaystyle+\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left(\frac{1}{n_{0,c}}+\frac{1}{n_{1,c}}\right)\frac{\lambda\overline{y^{2}}-\lambda^{2}\bar{y}^{2}}{(1-\lambda)^{2}}\,.$

We next recall (22):

${\rm
Var}_{{\bm{z}}}[{\mathbb{E}}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]=\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left(\frac{S^{2}(\vec{y}_{c}(1))}{n_{1,c}}+\frac{S^{2}(\vec{y}_{c}(0))}{n_{0,c}}-\frac{S^{2}(\vec{\tau}_{c})}{n_{c}}\right)\,,$

which is the variance of the typical estimator with no-differential-privacy
and so was written as ${\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-DP}}]$.
Finally, from the law of total variance, we have:

$\displaystyle{\rm Var}(\hat{\tau}|n_{0},n_{1},{\mathcal{P}})$
$\displaystyle={\mathbb{E}}_{{\bm{z}}}[{\rm
Var}_{DP}(\hat{\tau}|{\bm{z}},n_{0},n_{1},{\mathcal{P}})]+{\rm
Var}_{{\bm{z}}}[{\mathbb{E}}_{DP}(\hat{\tau}|{\bm{z}},n_{0},n_{1},{\mathcal{P}})]$
$\displaystyle={\mathbb{E}}_{{\bm{z}}}[{\rm
Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]+{\rm
Var}_{{\bm{z}}}[{\mathbb{E}}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]$
$\displaystyle={\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left(\frac{1}{n_{0,c}}+\frac{1}{n_{1,c}}\right)\frac{\lambda\overline{y^{2}}-\lambda^{2}\bar{y}^{2}}{(1-\lambda)^{2}}$
$\displaystyle+\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left[\frac{\lambda}{1-\lambda}\left(\frac{\overline{\bm{y}_{c}^{2}(0)}}{n_{0,c}}+\frac{\overline{\bm{y}_{c}^{2}(1)}}{n_{1,c}}\right)-\frac{2\lambda\bar{y}}{(1-\lambda)}\left(\frac{\overline{\bm{y}_{c}(0)}}{n_{0,c}}+\frac{\overline{\bm{y}_{c}(1)}}{n_{1,c}}\right)\right]\,.$

###  A.4 Proof of Theorem 4.1

The Cluster-DP mechanism randomizes the labels using the empirical probability
of units with the same treatment status (treated or controlled) within the
same cluster, so we can focus on the controlled units within one cluster, and
drop the index $a,c$ from our notation, unless needed for clarification. With
slight abuse of notation, suppose that there are $n$ controlled units in the
cluster and denote by $M$ the mechanism described in Algorithm 4.

We can think of $M$ as composition of two mechanisms $M_{1}$ and $M_{2}$ with
$M(D)=M_{2}(D,M_{1}(D))$, where $M_{1}(D)$ represents the mechanism that
returns the noisy cluster label distribution $\tilde{q}$, and
$M_{2}(D,\tilde{q})$ represents the mechanism which uses $\tilde{q}$ to re-
sample the labels and use them to form the average treatment effect estimator
$\hat{\tau}$. By composition theorem for $({\varepsilon},\delta)$-DP (see e.g.
(Dwork et al.,, 2014, Theorem B.1)), if $M_{1}$ is
$({\varepsilon}_{1},\delta_{1})$-DP and $M_{2}$ is
$({\varepsilon}_{2},\delta_{2})$-DP, then $M$ is
$({\varepsilon}_{1}+{\varepsilon}_{2},\delta_{1}+\delta_{2})$-DP.

After adding noise terms $w_{y,c}$ to empirical distributions
$\hat{p}_{0,D}(y|c)$ and $\hat{p}_{1,D}(y|c)$, the dataset $D$ is not accessed
anymore. Furthermore, the empirical distributions have sensitivity $1/n_{c}$
and the Laplace noise used in $M_{1}$ is of scale $\sigma/n_{c}$, which imply
that $M_{1}$ is $(1/\sigma,0)$-DP (see e.g. (Dwork et al.,, 2014, Theorem 3.6)
for an argument).

For mechanism $M_{2}$, note that it is a randomization per label mechanism
(using perturbed distribution $\tilde{q}$), followed by post-processing
(computing average treatment effect estimator). We next show that $M_{2}$ is
$(\tilde{{\varepsilon}},\delta)$-DP. Note that for all $y\in\mathcal{Y}$, we
have

${\mathbb{P}}(\tilde{y}_{i}=y|y_{i}=y)=1-\lambda+\lambda\tilde{q}(y),\quad{\mathbb{P}}(\tilde{y}_{i}=y|y_{i}\neq
y)=\lambda\tilde{q}(y)\,.$

Since ${\mathbb{P}}(\tilde{y}_{i}=y|y_{i}\neq y)$ is independent of $y_{i}$
and ${\mathbb{P}}(\tilde{y}_{i}=y|y_{i}\neq
y)<{\mathbb{P}}(\tilde{y}_{i}=y|y_{i}=y)$, the only condition we need to
verify is the following:

${\mathbb{P}}(\tilde{y}_{i}=y|y_{i}=y)\leq
e^{\tilde{{\varepsilon}}}{\mathbb{P}}(\tilde{y}_{i}=y|y_{i}\neq y)+\delta\,.$

By substituting for the events probabilities and $\delta$, the above condition
becomes equivalent to

$0\leq\lambda(\gamma-\tilde{q}(y))(1-e^{\tilde{{\varepsilon}}})\,,$

which holds since $\tilde{{\varepsilon}}>0$ and $\gamma\leq\tilde{q}(y)$. To
summarize, by applying composition theorem for $({\varepsilon},\delta)$-DP, we
obtain that $M$ is $({\varepsilon}^{\prime},\delta)$-label DP, with
${\varepsilon}^{\prime}=1/\sigma+\tilde{{\varepsilon}}$.

We next show that $M$ is $({\varepsilon}^{\prime\prime},\delta)$-label DP,
with ${\varepsilon}^{\prime\prime}=2/\gamma+\sigma$, which along with the
previous result gives the claim of Theorem 4.1. Let $Y_{1:n}$ be the random
vector denoting the labels of the units. We need to show that for any two
neighboring data sets $D=(y_{1:n},x_{1:n})$ and
$D^{\prime}=(y^{\prime}_{1:n},x_{1:n})$ (where $y_{1:n}$ and
$y^{\prime}_{1:n}$ differ only in one entry) we have

$\displaystyle{{\mathbb{P}}(M(y_{1:n})\in O)}\leq
e^{{\varepsilon}^{\prime\prime}}{{\mathbb{P}}(M(y^{\prime}_{1:n})\in
O)}+\delta\,,$ (14)

for any set $O\in\mathcal{Y}^{n}$. Proof of this part requires more effort.
Let $W_{1:K}$ be the random vector representing the noise values added to the
set of possible labels in the data set. We then have

$\displaystyle\begin{split}{\mathbb{P}}(M(y_{1:n})\in
O)&=\sum_{w_{1:K}}{\mathbb{P}}(M(y_{1:n})\in
O)|Y_{1:n}=y_{1:n},W_{1:K}=w_{1:K})\;{\mathbb{P}}(W_{1:K}=w_{1:K})\,,\\\
{\mathbb{P}}(M(y^{\prime}_{1:n})\in
O)&=\sum_{w_{1:K}}{\mathbb{P}}(M(y^{\prime}_{1:n})\in
O)|Y_{1:n}=y^{\prime}_{1:n},W_{1:K}=w_{1:K})\;{\mathbb{P}}(W_{1:K}=w_{1:K})\,.\end{split}$
(15)

It suffices to show that for any value of $w_{1:K}$, we have

$\displaystyle{\mathbb{P}}(M(y_{1:n})\in
O)|Y_{1:n}=y_{1:n},W_{1:K}=w_{1:K})\leq
e^{{\varepsilon}^{\prime\prime}}{\mathbb{P}}(M(y^{\prime}_{1:n})\in
O)|Y_{1:n}=y^{\prime}_{1:n},W_{1:K}=w_{1:K})+\delta\,.$ (16)

By multiplying both sides of the above equation with
${\mathbb{P}}(W_{1:K}=w_{1:K})$, and summing over $w_{1:K}$, and using that
$\sum_{w_{1:K}}{\mathbb{P}}(W_{1:K}=w_{1:K})=1$, we get the desired bound in
(14).

Let $\tilde{q}$ and $\tilde{q}^{\prime}$ be the empirical distributions of the
DP mechanism, as defined in Algorithm 4. we continue by establishing a lemma
on $\|\tilde{q}-\tilde{q}^{\prime}\|_{\infty}$, proven in the next section.

######  Lemma A.1.

For all $y\in\mathcal{Y}$,
$|\tilde{q}(y)-\tilde{q}^{\prime}(y)|\leq\frac{2}{n}\,.$

Define the shorthand $R:=M(y_{1:n})$ and $R^{\prime}:=M(y^{\prime}_{1:n})$. In
order to prove (16), it suffices to show that for all
$o_{1:n}\in\mathcal{Y}^{n}$, we have

$\displaystyle{{\mathbb{P}}(R=o_{1:n}|Y_{1:n}=y_{1:n},W_{1:K}=w_{1:K})}\leq
e^{{\varepsilon}^{\prime\prime}}{{\mathbb{P}}(R^{\prime}=o_{1:n}|Y_{1:n}=y^{\prime}_{1:n},W_{1:K}=w_{1:K})}+\delta\,.$
(17)

By the definition of the mechanism $M$ we have

$\displaystyle{\mathbb{P}}(R=o_{1:n}|Y_{1:n}=y_{1:n},W_{1:K}=w_{1:K})$
$\displaystyle={\mathbb{P}}(R=o_{1:n}|Y_{1:n}=y_{1:n},\tilde{q}(\cdot))=\prod_{i=1}^{n}{\mathbb{P}}(R_{i}=o_{i}|Y_{i}=y_{i},\tilde{q}(\cdot))$
$\displaystyle{\mathbb{P}}(R^{\prime}=o_{1:n}|Y_{1:n}=y^{\prime}_{1:n},W_{1:K}=w_{1:K})$
$\displaystyle={\mathbb{P}}(R=o_{1:n}|Y_{1:n}=y^{\prime}_{1:n},\tilde{q}^{\prime}(\cdot))=\prod_{i=1}^{n}{\mathbb{P}}(R^{\prime}_{i}=o_{i}|Y^{\prime}_{i}=y^{\prime}_{i},\tilde{q}^{\prime}(\cdot))\
$

For ease in presentation, we adopt the shorthand

$A_{i}:={\mathbb{P}}(R_{i}=o_{i}|Y_{i}=y_{i},\tilde{q}(\cdot)),\quad
B_{i}:={\mathbb{P}}(R^{\prime}_{i}=o_{i}|Y^{\prime}_{i}=y^{\prime}_{i},\tilde{q}^{\prime}(\cdot))\,,$

for $i=1,\dotsc,n$. Our next lemma bounds the event probability $A_{i}$ in
terms of the event probability $B_{i}$. Proof of Lemma A.2 is deferred to
Section A.

######  Lemma A.2.

Let $\tilde{{\varepsilon}}>0$ and define
$\delta:=(1-\lambda+\lambda\gamma(1-e^{\tilde{{\varepsilon}}}))_{+}<1$.
Without loss of generality suppose that the neighboring label sets $y_{1:n}$
and $y^{\prime}_{1:n}$ differs in the first coordinate. We then have

$\displaystyle A_{1}$ $\displaystyle\leq
e^{\tilde{{\varepsilon}}}\left(1+\frac{2}{\gamma n}\right)B_{1}+\delta,$ (18)
$\displaystyle A_{i}$ $\displaystyle\leq B_{i}\left(1+\frac{2}{\gamma
n}\right),\quad\text{for }i=2,\dotsc,n.$ (19)

We are now ready to prove inequality (17). Using Lemma A.2, we write

$\displaystyle{\mathbb{P}}(R=o_{1:n}|Y_{1:n}=y_{1:n},W_{1:K}=w_{1:K})$
$\displaystyle=\prod_{i=1}^{n}A_{i}$
$\displaystyle=A_{1}\min\left\\{1,\prod_{i=2}^{n}A_{i}\right\\}$
$\displaystyle\leq\left[e^{\tilde{{\varepsilon}}}\left(1+\frac{2}{\gamma
n}\right)B_{1}+\delta\right]\min\left\\{1,\left(1+\frac{2}{\gamma
n}\right)^{n-1}\prod_{i=2}^{n}B_{i}\right\\}$ $\displaystyle\leq
e^{\tilde{{\varepsilon}}}\left(1+\frac{2}{\gamma
n}\right)^{n}\prod_{i=1}^{n}B_{i}+\delta$ $\displaystyle\leq
e^{\tilde{{\varepsilon}}+2/\gamma}\prod_{i=1}^{n}B_{i}+\delta$
$\displaystyle=e^{{\varepsilon}^{\prime\prime}}{\mathbb{P}}(R^{\prime}=o_{1:n}|Y_{1:n}=y^{\prime}_{1:n},W_{1:K}=w_{1:K})+\delta\,.$

where the second equality holds since $A_{i}\leq 1$, for all $i$.

### Proof of Lemma A.1

Recall the notation of Theorem 4.1. We consider two neighboring datasets
$D=(y_{1:n},x_{1:n})$ and $D^{\prime}=(y^{\prime}_{1:n},x_{1:n})$, where
$y_{1:n}$ and $y^{\prime}_{1:n}$ differ only in one entry. Define the function
$f_{\gamma}$ as follows:

$f_{\gamma}(x)=\max\\{\gamma,\min\\{1,x\\}\\}=\begin{cases}\gamma,\quad&x\leq\gamma\\\
x,&\gamma\leq x\leq 1\\\ 1,&x>1\end{cases}$

We consider $q(y):=f_{\gamma}(\hat{p}(y)+w_{y})$ and
$q^{\prime}(y):=f_{\gamma}(\hat{p}^{\prime}(y)+w_{y})$, where $\hat{p}$ and
$\hat{p}^{\prime}$ respectively denote the empirical distribution of $y_{1:n}$
and $y^{\prime}_{1:n}$ and $w_{y}$ indicates the component of $w_{1:K}$
corresponding to label $y$. We wish to bound the difference between
distributions $\tilde{q}(y)$ and $\tilde{q}^{\prime}(y)$, defined in Algorithm
4, and recalled below:

$\tilde{q}(y)=q(y)+\frac{\zeta_{y}}{\sum_{y^{\prime}}\zeta_{y^{\prime}}}\Delta\,,\quad\tilde{q}^{\prime}(y)=q^{\prime}(y)+\frac{\zeta^{\prime}_{y}}{\sum_{y^{\prime}}\zeta^{\prime}_{y^{\prime}}}\Delta^{\prime}\,,$

where $\Delta=1-\sum_{y}q(y)$ and $\Delta^{\prime}=1-\sum_{y}q^{\prime}(y)$.
To achieve this, we will need a bound on $|q(y)-q^{\prime}(y)|$ and on a bound
on $|\Delta-\Delta^{\prime}|$.

  * •

Since $f_{\gamma}$ is 1-Lipschitz, we have for any $y\in\mathcal{Y}$

$|q(y)-q^{\prime}(y)|=|f_{\gamma}(\hat{p}(y)+w_{y})-f_{\gamma}(\hat{p}^{\prime}(y)+w_{y})|\leq|\hat{p}(y)-\hat{p}^{\prime}(y)|\leq\frac{1}{n}\,,$

where the last inequality holds because the datasets $D$ and $D^{\prime}$
differ in only one label.

  * •

We now show that $|\Delta-\Delta^{\prime}|\leq 1/n$. Without loss of
generality, we can assume that the neighboring label sets $y_{1:n}$ and
$y^{\prime}_{1:n}$ differ in the first coordinate, with $y_{1}=\ell$,
$y^{\prime}_{1}=\ell^{\prime}$ for $\ell,\ell^{\prime}\in\mathcal{Y}$, such
that

$\hat{p}(\ell)=\hat{p}^{\prime}(\ell)+\frac{1}{n}\,,\quad\hat{p}(\ell^{\prime})=\hat{p}^{\prime}(\ell^{\prime})-\frac{1}{n}\,.$

It follows that

$\displaystyle\Delta^{\prime}-\Delta$
$\displaystyle=\sum_{y}q(y)-\sum_{y}q^{\prime}(y)$
$\displaystyle=f_{\gamma}(\hat{p}(\ell)+w_{\ell})+f_{\gamma}(\hat{p}(\ell^{\prime})+w_{\ell^{\prime}})-f_{\gamma}(\hat{p}^{\prime}(\ell)+w_{\ell})-f_{\gamma}(\hat{p}^{\prime}(\ell^{\prime})+w_{\ell^{\prime}})$
$\displaystyle=f_{\gamma}\left(\hat{p}^{\prime}(\ell)+\frac{1}{n}+w_{\ell}\right)-f_{\gamma}(\hat{p}^{\prime}(\ell)+w_{\ell})+f_{\gamma}\left(\hat{p}^{\prime}(\ell^{\prime})-\frac{1}{n}+w_{\ell^{\prime}}\right)-f_{\gamma}(\hat{p}^{\prime}(\ell^{\prime})+w_{\ell^{\prime}})$
$\displaystyle\leq
f_{\gamma}\left(\hat{p}^{\prime}(\ell)+\frac{1}{n}+w_{\ell}\right)-f_{\gamma}(\hat{p}^{\prime}(\ell)+w_{\ell})$
$\displaystyle\leq\frac{1}{n}\,,$

where the second to last inequality holds since $f_{\gamma}$ is a non-
decreasing function, and the last step follows from 1-Lipschitzness of
$f_{\gamma}$. Likewise, we can show $\Delta-\Delta^{\prime}\leq 1/n$ in order
to obtain $|\Delta-\Delta^{\prime}|\leq 1/n$.

With this, we next bound the difference between distributions $\tilde{q}(y)$
and $\tilde{q}^{\prime}(y)$, defined above. Consider three different cases:

  * •

$\Delta>0,\Delta^{\prime}<0$. We have

$\displaystyle|\tilde{q}(y)-\tilde{q}^{\prime}(y)|$
$\displaystyle\leq|q(y)-q^{\prime}(y)|+\Big{|}\frac{\zeta_{y}}{\sum_{y^{\prime}}\zeta_{y^{\prime}}}\Delta-\frac{\zeta^{\prime}_{y}}{\sum_{y^{\prime}}\zeta^{\prime}_{y^{\prime}}}\Delta^{\prime}\Big{|}$
$\displaystyle\leq|q(y)-q^{\prime}(y)|+|\Delta-\Delta^{\prime}|\leq\frac{2}{n}\,.$

The case of $\Delta<0$, $\Delta^{\prime}>0$ can be handled similarly.

  * •

$\Delta,\Delta^{\prime}<0$. We have

$\displaystyle\tilde{q}(y)$
$\displaystyle=q(y)+(q(y)-\gamma)\frac{\Delta}{\sum_{y^{\prime}}(q(y^{\prime})-\gamma)}$
$\displaystyle=q(y)+(q(y)-\gamma)\frac{\Delta}{1-\Delta-K\gamma}$
$\displaystyle=\gamma+(q(y)-\gamma)+(q(y)-\gamma)\frac{\Delta}{1-\Delta-K\gamma}$
$\displaystyle=\gamma+(q(y)-\gamma)\frac{1-K\gamma}{1-\Delta-K\gamma}\,.$

Therefore,

$\displaystyle|\tilde{q}(y)-\tilde{q}^{\prime}(y)|$
$\displaystyle\leq(q(y)-\gamma)\Big{|}\frac{1-K\gamma}{1-\Delta-K\gamma}-\frac{1-K\gamma}{1-\Delta^{\prime}-K\gamma}\Big{|}+|q^{\prime}(y)-q(y)|\frac{1-K\gamma}{1-\Delta^{\prime}-K\gamma}$
$\displaystyle=(q(y)-\gamma)\frac{(1-K\gamma)|\Delta-\Delta^{\prime}|}{(1-\Delta-K\gamma)(1-\Delta^{\prime}-K\gamma)}+\frac{1}{n}\frac{1-K\gamma}{1-\Delta^{\prime}-K\gamma}$
$\displaystyle=\frac{1-K\gamma}{1-\Delta^{\prime}-K\gamma}\left[\frac{(q(y)-\gamma)|\Delta-\Delta^{\prime}|}{(1-\Delta-K\gamma)}+\frac{1}{n}\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{n}\frac{1-K\gamma}{1-\Delta^{\prime}-K\gamma}\left(\frac{q(y)-\gamma}{1-\Delta-K\gamma}+1\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{2}{n}\frac{1-K\gamma}{1-\Delta^{\prime}-K\gamma}\leq\frac{2}{n}\,.$

$(a)$ holds since $|\Delta-\Delta^{\prime}|\leq 1/n$. $(b)$ follows from the
fact that, since $q(y)\geq\gamma$ for all $y$,

$q(y)+(K-1)\gamma\leq q(y)+\sum_{y^{\prime}\neq y}q(y^{\prime})=1-\Delta\,,$

such that $q(y)-\gamma\leq 1-\Delta-K\gamma$.

  * •

$\Delta,\Delta^{\prime}>0$. We have

$\displaystyle\tilde{q}(y)$
$\displaystyle=q(y)+(1-q(y))\frac{\Delta}{\sum_{y^{\prime}}(1-q(y^{\prime}))}$
$\displaystyle=1+(1-q(y))\left(\frac{\Delta}{\Delta+K-1}-1\right)$
$\displaystyle=1+(1-q(y))\frac{1-K}{\Delta+K-1}\,.$

Therefore,

$\displaystyle|\tilde{q}(y)-\tilde{q}^{\prime}(y)|$
$\displaystyle\leq(1-q(y))\Big{|}\frac{1-K}{\Delta+K-1}-\frac{1-K}{\Delta^{\prime}+K-1}\Big{|}+|q(y)-q^{\prime}(y)|\frac{K-1}{\Delta^{\prime}+K-1}$
$\displaystyle\leq(1-q(y))\left[\frac{|\Delta^{\prime}-\Delta|}{\Delta+K-1}+\frac{1}{n}\right]\frac{K-1}{\Delta^{\prime}+K-1}$
$\displaystyle\leq(1-q(y))\frac{1}{n(K-1)}+\frac{1}{n}\leq\frac{1}{n}\frac{K}{K-1}\leq\frac{2}{n}\,.$

Combining the above three cases together, we obtain our stated lemma.

### Proof of Lemma A.2

We start by proving (18). Consider three different cases:

  * •

$o_{1}\neq y_{1},y^{\prime}_{1}$: In this case, we have

$A_{1}=\lambda\tilde{q}(o_{1}),\quad B_{1}=\lambda\tilde{q}^{\prime}(o_{1}).$

Therefore, we can write

$\displaystyle A_{1}$
$\displaystyle\leq\lambda\tilde{q}^{\prime}(o_{1})+\lambda\|\tilde{q}-\tilde{q}^{\prime}\|_{\infty}$
$\displaystyle\leq\lambda\tilde{q}^{\prime}(o_{1})+\frac{2\lambda}{n}$
$\displaystyle\leq\lambda\tilde{q}^{\prime}(o_{1})\left(1+\frac{2}{n\gamma}\right)$
$\displaystyle=B_{1}\left(1+\frac{2}{n\gamma}\right)$ $\displaystyle\leq
e^{\tilde{{\varepsilon}}}B_{1}\left(1+\frac{2}{n\gamma}\right)+\delta,$

where the second step follows from Lemma A.1, third step holds since
$\gamma\leq\tilde{q}^{\prime}(o_{1})$, and the last step holds since
$\tilde{{\varepsilon}},\delta>0$. So the claim (18) is proved in this case.

  * •

$o_{1}=y_{1}$: In this case,

$A_{1}=1-\lambda+\lambda\tilde{q}(o_{1}),\quad
B_{1}=\lambda\tilde{q}^{\prime}(o_{1})\,.$

We then have

$\displaystyle A_{1}$ $\displaystyle\leq
1-\lambda+\lambda\tilde{q}^{\prime}(o_{1})+\lambda\|\tilde{q}-\tilde{q}^{\prime}\|_{\infty}$
$\displaystyle\leq
1-\lambda+\lambda\tilde{q}^{\prime}(o_{1})+\lambda\frac{2}{n\gamma}\tilde{q}^{\prime}(o_{1})e^{\tilde{{\varepsilon}}}\,,$
(20)

where we used Lemma A.1 along with the facts that
$\tilde{q}^{\prime}(o_{1})\geq\gamma$ and $\tilde{{\varepsilon}}>0$.

We next recall the definition
$\delta:=(1-\lambda+\lambda\gamma(1-e^{\tilde{{\varepsilon}}}))_{+}<1$. By a
simple rearrangement of the terms and using that
$\tilde{q}^{\prime}(o_{1})\geq\gamma$ and $\tilde{{\varepsilon}}>0$, we can
verify the following,

$\displaystyle 1-\lambda+\lambda\tilde{q}^{\prime}(o_{1})\leq
e^{\tilde{{\varepsilon}}}\lambda\tilde{q}^{\prime}(o_{1})+\delta\,.$ (21)

Therefore, by combining equations (20) and (21), we get

$\displaystyle A_{1}\leq
e^{\tilde{{\varepsilon}}}\lambda\tilde{q}^{\prime}(o_{1})+\delta+\lambda\frac{2}{n\gamma}\tilde{q}^{\prime}(o_{1})e^{\tilde{{\varepsilon}}}=e^{\tilde{{\varepsilon}}}=\left(1+\frac{2}{n\gamma}\right)B_{1}+\delta\,,$

which completes the proof of claim (18) in this case.

  * •

$o_{1}=y^{\prime}_{1}$: In this case,

$A_{1}=\lambda\tilde{q}(o_{1}),\quad
B_{1}=1-\lambda+\lambda\tilde{q}^{\prime}(o_{1})\,.$

The proof of claim (18) in this case follows readily from case 1, because
$A_{1}$ is the same as in there, while $B_{1}$ is larger.

This concludes the proof of Claim 18. We next prove Claim 19. Note that for
$i=2,\dotsc,n$, we have $y_{i}=y^{\prime}_{i}$. Consider the following two
cases:

  * •

$o_{i}=y_{i}=y^{\prime}_{i}$: In this case we have

$\frac{A_{i}}{B_{i}}=\frac{1-\lambda+\lambda\tilde{q}(o_{i})}{1-\lambda+\lambda\tilde{q}^{\prime}(o_{i})}\,.$

  * •

$o_{i}\neq y_{i}$: Since $y_{i}=y^{\prime}_{i}$, we also have $o_{i}\neq
y^{\prime}_{i}$. In this case,

$\frac{A_{i}}{B_{i}}=\frac{\lambda\tilde{q}(o_{i})}{\lambda\tilde{q}^{\prime}(o_{i})}.$

By symmetry, we can assume $\tilde{q}(o_{i})\leq\tilde{q}^{\prime}(o_{i})$,
without loss of generality, and therefore, the maximum value of the ratio
$A_{1}/B1$ is achieved in the second case, for which we have

$\frac{A_{i}}{B_{i}}=\frac{\tilde{q}(o_{i})}{\tilde{q}^{\prime}(o_{i})}\leq
1+\frac{\|\tilde{q}-\tilde{q}^{\prime}\|_{\infty}}{\tilde{q}^{\prime}(o_{i})}\leq
1+\frac{2}{n\gamma}\,.$

This completes the proof of (19).

###  A.5 Proof of Theorem 4.2

We would like to express the expectation
${\mathbb{E}}(\hat{\tau}|n_{0},n_{1})$. Recall that there are three sources of
randomness:

  * •

the differential privacy mechanism $DP$: determines the Laplace noise $\bm{w}$
and the $\lambda$ probability of reporting the true outcome.

  * •

the randomized assignment ${\bm{z}}$: determines which units get assigned to
treatment and which units get assigned to control.

  * •

the super-population ${\mathcal{P}}$: determines the potential outcomes as
well as the cluster assignments.

For a given unit $i$ with $(y_{i}(0),y_{i}(1),c_{i})\sim{\mathcal{P}}$ and
$z_{i}=a$,

$\displaystyle{\mathbb{E}}_{DP}\left[\sum_{y^{\prime}\in\mathcal{Y}}Q^{-1}_{c_{i},z_{i}}[y^{\prime},\tilde{y_{i}}]y^{\prime}z_{i}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle={\mathbb{E}}_{DP}\left[\sum_{y^{\prime}\in\mathcal{Y}}\sum_{y\in\mathcal{Y}}{\mathbb{I}}(\tilde{y}_{i}=y)Q^{-1}_{c_{i},z_{i}}[y^{\prime},y]y^{\prime}z_{i}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{y^{\prime}\in\mathcal{Y}}{\mathbb{E}}_{DP}\left[\sum_{y\in\mathcal{Y}}{\mathbb{I}}(\tilde{y}_{i}=y)Q^{-1}_{c_{i},z_{i}}[y^{\prime},y]\middle|{\bm{z}},{\mathcal{P}}\right]y^{\prime}z_{i}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{y^{\prime}\in\mathcal{Y}}{\mathbb{E}}_{\bm{w}}\left[\sum_{y\in\mathcal{Y}}{\mathbb{E}}_{\lambda}\left[{\mathbb{I}}(\tilde{y}_{i}=y)\right]Q^{-1}_{c_{i},z_{i}}[y^{\prime},y]\middle|{\bm{z}},{\mathcal{P}}\right]y^{\prime}z_{i}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\sum_{y^{\prime}\in\mathcal{Y}}{\mathbb{E}}_{\bm{w}}\left[\sum_{y\in\mathcal{Y}}Q_{c_{i},z_{i}}[y,y_{i}]Q^{-1}_{c_{i},z_{i}}[y^{\prime},y]\middle|{\bm{z}},{\mathcal{P}}\right]y^{\prime}z_{i}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\sum_{y^{\prime}\in\mathcal{Y}}{\mathbb{E}}_{\bm{w}}\left[{\mathbb{I}}(y_{i}=y^{\prime})\middle|{\bm{z}},{\mathcal{P}}\right]y^{\prime}z_{i}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}\sum_{y^{\prime}\in\mathcal{Y}}{\mathbb{I}}(y_{i}=y^{\prime})y^{\prime}z_{i}$
$\displaystyle=y_{i}(1)z_{i}\,.$

$(a)$ holds since assignments $z_{i}$ is independent from
$\\{y_{i}(0),y_{i}(1),c_{i}\\}$; $(b)$ holds from the law of iterated
expectation and the fact that there are two sources of randomness in the
differential privacy mechanism: $(\lambda,\bm{w})$ with $Q_{c,a}$ independent
of the Bernoulli $\lambda$; $(c)$ follows from the definition of $Q_{c,a}$:
$Q_{c,a}[y^{\prime},y]=(1-\lambda){\mathbb{I}}(y^{\prime}=y)+\lambda\tilde{q}_{a}(y^{\prime}|c)\,$;
and $(d)$ follows from the fact that $I=Q_{c_{i}}^{-1}Q_{c_{i}}$ therefore,
for any $a,b\in[K]$,

$\sum_{y}Q_{c_{i}}^{-1}[a,y]Q_{c_{i}}[y,b]=I_{a,b}={\mathbb{I}}(a=b)\,.$

Finally, $(e)$ follows from the fact that $\bm{w}$ is independent from
$\\{y_{i}(0),y_{i}(1),c_{i}\\}$. Similarly,

${\mathbb{E}}_{DP}\left[\sum_{y^{\prime}\in\mathcal{Y}}Q^{-1}_{c_{i},z_{i}}[y^{\prime},\tilde{y_{i}}]y^{\prime}(1-z_{i})\middle|{\bm{z}},{\mathcal{P}}\right]=y_{i}(0)(1-z_{i})$

As a result, with $n_{0,c}$ (resp. $n_{1,c}$) the total number of controlled
(resp. treated) units in cluster $c$ and $n_{c}:=n_{0,c}+n_{1,c}$,

${\mathbb{E}}_{DP}[\hat{\tau}|{\bm{z}},{\mathcal{P}}]=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\left(\sum_{i=1}^{n}y_{i}(1)\frac{z_{i}}{n_{1,c}}-\sum_{i=1}^{n}y_{i}(0)\frac{1-z_{i}}{n_{0,c}}\right)$

We recover the standard form of the difference-in-means estimator. From the
law of iterated expectations, we have

${\mathbb{E}}_{DP,{\bm{z}}}[\hat{\tau}]={\mathbb{E}}_{{\bm{z}}}\left[{\mathbb{E}}_{DP}[\hat{\tau}|{\bm{z}}]\middle|n_{0},n_{1},{\mathcal{P}}\right]=\tau\,.$

###  A.6 Proof of Theorem 4.4

We would like to express the variance ${\rm Var}_{DP,{\bm{z}}}(\hat{\tau})$.
We begin by expressing the variance with respect to the first two, considering
the third fixed. From the law of total variance, we have:

$\displaystyle{\rm Var}_{DP,{\bm{z}}}(\hat{\tau})$
$\displaystyle={\mathbb{E}}_{{\bm{z}}}[{\rm
Var}_{DP}(\hat{\tau}|{\bm{z}},n_{0},n_{1},{\mathcal{P}})]+{\rm
Var}_{{\bm{z}}}[{\mathbb{E}}_{DP}(\hat{\tau}|{\bm{z}},n_{0},n_{1},{\mathcal{P}})]$
$\displaystyle={\mathbb{E}}_{{\bm{z}}}[{\rm
Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]+{\rm
Var}_{{\bm{z}}}[{\mathbb{E}}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]$

We bound the term ${\rm Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})$ in a
separate proposition

######  Proposition A.3.

For the average treatment effect estimator $\hat{\tau}$ given by (9) we have

$\displaystyle{\rm Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})\leq$
$\displaystyle\sum_{a\in\\{0,1\\}}\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left[\left(\frac{1}{(1-\lambda)^{2}}-1\right)\frac{S^{2}(\vec{y}_{a,c})}{n_{a,c}}+\frac{A(n_{a,c})}{n_{a,c}}\right]\,,$

where $\vec{y}_{a,c}:=\\{y_{i}(a):i\in{\cal O}_{a,c}\\}$, and

$A(x)=2KB^{2}\left(\left(\frac{3}{(1-\lambda)^{2}}+2\right)+\frac{(\lambda\sqrt{K}+1)^{2}}{(1-\lambda)^{2}}\|\mathsf{y}\|^{2}(1-\lambda(K-1)\gamma)\right)\left[\gamma+\frac{\sigma}{x}\Big{(}e^{-\gamma
x/{\sigma}}-e^{-x/{\sigma}}\Big{)}\right]$

We now take its expectation with respect to ${\bm{z}}$. We assume that, for
each cluster c, there is a fixed number of units $(n_{1,c})$ assigned to
treatment and a fixed number of units $(n_{0,c})$ assigned to control,
regardless of the cluster assignment. We compute the expectation with
${\mathbb{E}}_{{\bm{z}}}\left[S^{2}(\vec{y}_{a,c})\right]$,

$\displaystyle(n_{a,c}-1){\mathbb{E}}_{{\bm{z}}}$
$\displaystyle\left[S^{2}(\vec{y}_{a,c})\right]$
$\displaystyle={\mathbb{E}}_{{\bm{z}}}\left[\sum_{i\in{\cal
O}_{a,c}}\left(y_{i}(a)-\overline{\\{y_{i}(a)\\}_{i\in{\cal
O}_{a,c}}}\right)^{2}\right]$
$\displaystyle={\mathbb{E}}_{{\bm{z}}}\left[\sum_{i\in{\cal
O}_{a,c}}y_{i}^{2}(a)-n_{a,c}\left(\frac{1}{n_{a,c}}\sum_{i\in{\cal
O}_{a,c}}y_{i}(a)\right)^{2}\right]$ $\displaystyle=\sum_{i\in{\cal
O}_{c}}{\mathbb{P}}\left(z_{i}=a\right)y_{i}^{2}(a)-n_{a,c}{\mathbb{E}}_{{\bm{z}}}\left[\left(\frac{1}{n_{a,c}}\sum_{i\in{\cal
O}_{c}}{\mathbb{I}}(z_{i}=a)y_{i}(a)\right)^{2}\right]$
$\displaystyle=\sum_{i\in{\cal
O}_{c}}\frac{n_{a,c}}{n_{c}}y_{i}^{2}(a)-\frac{1}{n_{a,c}}\sum_{i\in{\cal
O}_{c}}\sum_{j\in{\cal
O}_{c}}{\mathbb{P}}\left(z_{i}=a,z_{j}=a\right)y_{i}(a)y_{j}(a)$
$\displaystyle=\sum_{i\in{\cal
O}_{c}}\frac{n_{a,c}}{n_{c}}y_{i}^{2}(a)-\frac{1}{n_{a,c}}\sum_{i\in{\cal
O}_{c}}{\mathbb{P}}\left(z_{i}=a\right)y_{i}^{2}(a)-\frac{1}{n_{a,c}}\sum_{j\neq
i\in{\cal O}_{c}}{\mathbb{P}}\left(z_{i}=a,z_{j}=a\right)y_{i}(a)y_{j}(a)$
$\displaystyle=\sum_{i\in{\cal
O}_{c}}\frac{n_{a,c}}{n_{c}}y_{i}^{2}(a)-\frac{1}{n_{c}}\sum_{i\in{\cal
O}_{c}}y_{i}^{2}(a)-\frac{1}{n_{a,c}}\sum_{j\neq i\in{\cal
O}_{c}}\frac{n_{a,c}(n_{a,c}-1)}{n_{c}(n_{c}-1)}y_{i}(a)y_{j}(a)\,.$

Adding and subtracting $\frac{n_{a,c}-1}{n_{c}(n_{c}-1)}\sum_{i\in{\cal
O}_{c}}y_{i}^{2}(a)$, we get:

$\displaystyle(n_{a,c}-1)$
$\displaystyle{\mathbb{E}}_{{\bm{z}}}\left[S^{2}(\vec{y}_{a,c})\right]$
$\displaystyle=\sum_{i\in{\cal
O}_{c}}\frac{n_{a,c}}{n_{c}}y_{i}^{2}(a)-\frac{1}{n_{c}}\sum_{i\in{\cal
O}_{c}}y_{i}^{2}(a)+\frac{n_{a,c}-1}{n_{c}(n_{c}-1)}\sum_{i\in{\cal
O}_{c}}y_{i}^{2}(a)-\frac{n_{a,c}-1}{n_{c}(n_{c}-1)}\left(\sum_{i\in{\cal
O}_{c}}y_{i}(a)\right)^{2}$
$\displaystyle=\left(\frac{n_{a,c}}{n_{c}}-\frac{1}{n_{c}}+\frac{n_{a,c}-1}{n_{c}(n_{c}-1)}\right)\sum_{i\in{\cal
O}_{c}}y_{i}^{2}(a)-(n_{a,c}-1)\frac{n_{c}}{n_{c}-1}\left(\frac{1}{n_{c}}\sum_{i\in{\cal
O}_{c}}y_{i}(a)\right)^{2}$
$\displaystyle=\frac{n_{a,c}-1}{n_{c}-1}\sum_{i\in{\cal
O}_{c}}y_{i}^{2}(a)-(n_{a,c}-1)\frac{n_{c}}{n_{c}-1}\left(\frac{1}{n_{c}}\sum_{i\in{\cal
O}_{c}}y_{i}(a)\right)^{2}$ $\displaystyle=(n_{a,c}-1)S^{2}(\vec{y}_{c}(a)).$

For the second term, we again make the assumption that the number of treated
units is fixed at the cluster level. For the second term, from the proof of
Theorem 4.2, we have:

${\mathbb{E}}_{DP}[\hat{\tau}|{\bm{z}},{\mathcal{P}}]=\sum_{c\in\mathcal{C}}\frac{n_{c}}{n}\left(\sum_{i=1}^{n}y_{i}(1)\frac{z_{i}}{n_{1,c}}-\sum_{i=1}^{n}y_{i}(0)\frac{1-z_{i}}{n_{0,c}}\right)$

As a result, the second term is given by the usual formula for the variance of
the stratified estimator:

${\rm
Var}_{{\bm{z}}}[{\mathbb{E}}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]=\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left(\frac{S^{2}(\vec{y}_{c}(1))}{n_{1,c}}+\frac{S^{2}(\vec{y}_{c}(0))}{n_{0,c}}-\frac{S^{2}(\vec{\tau}_{c})}{n_{c}}\right)$
(22)

where, for any vector $\vec{u}$ of length $n$,
$S^{2}(u)=\frac{1}{n-1}\sum_{i=1}^{n}\left(u_{i}-\bar{u}\right)^{2}$ and
$\bar{u}=\frac{1}{n}\sum_{i=1}^{n}u_{i}$. Recall that
$\vec{\tau}_{c}=\\{y_{i}(1)-y_{i}(0)\\}_{i:c_{i}=c}=\vec{y}_{c}(1)-\vec{y}_{c}(0)$
. Since this is the variance of the typical estimator with no-differential-
privacy, we write this term:

${\rm
Var}_{{\bm{z}}}[{\mathbb{E}}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})]={\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-DP}}]$

As a result, we obtain

$\displaystyle{\rm Var}_{DP,{\bm{z}}}$
$\displaystyle(\hat{\tau}|n_{0,c},n_{1,c},{\mathcal{P}})$ $\displaystyle\leq$
$\displaystyle{\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\sum_{a\in\\{0,1\\}}\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\left[\left(\frac{1}{(1-\lambda)^{2}}-1\right)\frac{S^{2}(\vec{y}_{c}(a))}{n_{a,c}}+\frac{A(n_{a,c})}{n_{a,c}}\right]$
$\displaystyle\leq$ $\displaystyle{\rm Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\left(\frac{1}{(1-\lambda)^{2}}-1\right)\sum_{a\in\\{0,1\\}}\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\frac{S^{2}(\vec{y}_{c}(a))}{n_{a,c}}+\sum_{a\in\\{0,1\\}}\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\frac{A(n_{a,c})}{n_{a,c}}$

which we can rewrite as:

${\rm Var}_{DP,{\bm{z}}}(\hat{\tau}|n_{0,c},n_{1,c},{\mathcal{P}})\leq{\rm
Var}_{{\bm{z}}}[\hat{\tau}_{\textsc{No-
DP}}]+\left(\frac{1}{(1-\lambda)^{2}}-1\right)\sum_{a\in\\{0,1\\}}\phi_{a}+\sum_{a\in\\{0,1\\}}\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\frac{A(n_{a,c})}{n_{a,c}}$

where we have defined

$\phi_{a}:=\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\frac{S^{2}(\vec{y}_{c}(a))}{n_{a,c}}\geq
0$

### Proof of Proposition A.3

We seek to compute ${\rm Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})$. We can
rewrite $\hat{\tau}$ as

$\hat{\tau}=\sum_{c\in
C}\frac{n_{c}}{n}\sum_{a\in\\{0,1\\}}\frac{u_{a,c}}{n_{a,c}}\,,$

where $\mathcal{O}_{a,c}:=\left\\{i\in[n]:c_{i}=c,z_{i}=a\right\\}\,$ and
$u_{a,c}:=\sum_{i\in\mathcal{O}_{a,c}}\sum_{y^{\prime}\in\mathcal{Y}}Q_{c_{i},a}^{-1}[y^{\prime},\tilde{y}_{i}]y^{\prime}$.
Since $(y_{i}(0),y_{i}(1))$ are i.i.d across units, and the DP mechanism is
applied to each clusters separately, such that the privatized outcomes
$\tilde{y_{i}}$ are independent across clusters, we have that $u_{0,c}$ and
$u_{1,c}$ are independent across clusters.

${\rm
Var}_{DP}(\hat{\tau}|{\bm{z}},{\mathcal{P}})=\sum_{c\in\mathcal{C}}\frac{n_{c}^{2}}{n^{2}}\sum_{a\in\\{0,1\\}}\frac{1}{n_{a,c}^{2}}{\rm
Var}_{DP}(u_{a,c}|{\bm{z}},{\mathcal{P}})\,.$ (23)

We proceed by calculating ${\rm Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})$.
The computation for ${\rm Var}_{DP}(u_{1,c}|{\bm{z}},{\mathcal{P}})$ is
identical.

####  $\bullet$ Computing ${\rm Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})$

We have

${\rm
Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})={\mathbb{E}}_{DP}[u_{0,c}^{2}|{\bm{z}},{\mathcal{P}}]-{\mathbb{E}}_{DP}[u_{0,c}|{\bm{z}},{\mathcal{P}}]^{2}$

We begin by computing ${\mathbb{E}}_{DP}[u_{0,c}|{\bm{z}},{\mathcal{P}}]$.
Fixing cluster $c$, we lighten the notation by using the shorthand
$Q=Q_{c,0}$, $Q_{a,b}=Q_{c,0}[a,b]$, $Q^{-1}_{a,b}=Q^{-1}_{c,0}[a,b]$, and
$Q^{-{\sf T}}=(Q^{-1})^{\sf T}$. Finally, recall that
$\mathsf{y}=(y)_{y\in\mathcal{Y}}$ is the set of possible outcomes arranged
into a vector with the same ordering as the columns of $Q$, and
$e_{\ell}\in{\mathbb{R}}^{K\times 1}$ is the vector with $1$ at the $\ell$-th
position and zero everywhere else. Writing in matrix form, we have

$u_{0,c}=\sum_{i\in\mathcal{O}_{0,c}}\mathsf{y}^{\sf
T}Q^{-1}_{\cdot,\tilde{y}_{i}}\,.$

Let $\tilde{\bm{y}}$, $\bm{y}$, ${\bm{z}}$, $\bm{w}$ be the vectors of
variables $\tilde{y}_{i}$, $y_{i}$, $z_{i}$, $(w)_{y,c}$ respectively. We then
have

$\displaystyle{\mathbb{E}}_{DP}[u_{0,c}|{\bm{z}},{\mathcal{P}}]$
$\displaystyle=\sum_{i\in\mathcal{O}_{0,c}}{\mathbb{E}}_{DP}\left[\mathsf{y}^{\sf
T}Q^{-1}_{\cdot,\tilde{y}_{i}}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle=\sum_{i\in\mathcal{O}_{0,c}}{\mathbb{E}}_{DP}\left[\mathsf{y}^{\sf
T}\sum_{\ell\in\mathcal{Y}}Q^{-1}_{\cdot,\ell}{\mathbb{I}}(l=\tilde{y}_{i})\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle=\sum_{i\in\mathcal{O}_{0,c}}\mathsf{y}^{\sf
T}\sum_{\ell\in\mathcal{Y}}{\mathbb{E}}_{DP}\left[Q^{-1}_{\cdot,\ell}{\mathbb{I}}(l=\tilde{y}_{i})\middle|{\bm{z}},{\mathcal{P}}\right]$

Following similar steps to the proof of Theorem 4.2, we have

${\mathbb{E}}_{DP}\left[Q^{-1}_{\cdot,\ell}{\mathbb{I}}(l=\tilde{y}_{i})\middle|{\bm{z}},{\mathcal{P}}\right]={\mathbb{E}}_{\bm{w}}\left[Q^{-1}_{\cdot,\ell}{\mathbb{E}}_{\lambda}\left[{\mathbb{I}}(l=\tilde{y}_{i})\middle|\bm{w}\right]\middle|{\bm{z}},{\mathcal{P}}\right]={\mathbb{E}}_{\bm{w}}\left[Q^{-1}_{\cdot,\ell}Q_{l,y_{i}}\middle|{\bm{z}},{\mathcal{P}}\right]=Ie_{i}\,.$

It follows

${\mathbb{E}}_{DP}[u_{0,c}|{\bm{z}},{\mathcal{P}}]=\sum_{i\in\mathcal{O}_{0,c}}\mathsf{y}^{\sf
T}Ie_{i}=\sum_{i\in\mathcal{O}_{0,c}}y_{i}(0)\,.$ (24)

We next calculate ${\mathbb{E}}[u_{0,c}^{2}|{\bm{z}},{\mathcal{P}}]$.

$\displaystyle{\mathbb{E}}_{DP}\left[u_{0,c}^{2}|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle=\sum_{i,j\in\mathcal{O}_{0,c}}{\mathbb{E}}_{DP}\left[\mathsf{y}^{\sf
T}Q^{-1}_{\cdot,\tilde{y}_{j}}(Q^{-1}_{\cdot,\tilde{y}_{i}})^{\sf
T}\mathsf{y}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle=\sum_{i,j\in\mathcal{O}_{0,c}}\mathsf{y}^{\sf
T}{\mathbb{E}}_{DP}\left[\sum_{l,l^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,l^{\prime}}(Q^{-1}_{\cdot,l})^{\sf
T}{\mathbb{I}}(l=\tilde{y}_{i}){\mathbb{I}}(l^{\prime}=\tilde{y}_{j})\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
$\displaystyle=\sum_{i,j\in\mathcal{O}_{0,c}}\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[\sum_{l,l^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,l^{\prime}}(Q^{-1}_{\cdot,l})^{\sf
T}{\mathbb{E}}_{\lambda}\left[{\mathbb{I}}(l=\tilde{y}_{i}){\mathbb{I}}(l^{\prime}=\tilde{y}_{j})\middle|\bm{w}\right]\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
$\displaystyle=\sum_{i\in\mathcal{O}_{0,c}}\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[\sum_{\ell\in\mathcal{Y}}Q^{-1}_{\cdot,\ell}(Q^{-1}_{\cdot,\ell})^{\sf
T}Q_{\ell,y_{i}}\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
$\displaystyle\qquad+\sum_{i\neq j\in\mathcal{O}_{0,c}}\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[\sum_{\ell,\ell^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,\ell^{\prime}}(Q^{-1}_{\cdot,\ell})^{\sf
T}Q_{\ell,y_{i}}Q_{\ell^{\prime},y_{j}}\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
(25)

For the first term, we write

$\displaystyle\sum_{\ell\in\mathcal{Y}}Q^{-1}_{\cdot,\ell}(Q^{-1}_{\cdot,\ell})^{\sf
T}Q_{\ell,y_{i}}$
$\displaystyle=\sum_{\ell\in\mathcal{Y}}Q^{-1}_{\cdot,\ell}(Q^{-1}_{\cdot,\ell})^{\sf
T}(Qe_{y_{i}})_{\ell}=Q^{-1}{\rm diag}(Qe_{y_{i}})Q^{-{\sf T}}\,,$ (26)

Let $\hat{\bm{p}}=[\hat{p}_{0}(y|c)]_{y\in\mathcal{Y}}\in{\mathbb{R}}^{K\times
1}$ be the empirical distributions of outcomes of the controlled units in
cluster $c$, arranged into a $K$-dimensional vector, such that
$\hat{p}_{\ell}=\frac{1}{n_{0,c}}|\\{i\in\mathcal{O}_{0,c}:y_{i}=\ell\\}|$. In
vector form,

$\hat{\bm{p}}=\frac{1}{n_{0,c}}\sum_{i\in\mathcal{O}_{0,c}}e_{y_{i}}\,.$

Taking the expectation of both sides in (26) and summing over
$i\in\mathcal{O}_{0,c}$, we get

$\displaystyle\sum_{i\in\mathcal{O}_{0,c}}{\mathbb{E}}_{\bm{w}}\left[\sum_{\ell\in\mathcal{Y}}Q^{-1}_{\cdot,\ell}(Q^{-1}_{\cdot,\ell})^{\sf
T}Q_{\ell,y_{i}}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle={\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm
diag}\left(Q\sum_{i\in\mathcal{O}_{0,c}}e_{y_{i}}\right)Q^{-{\sf
T}}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle={\mathbb{E}}_{\bm{w}}\Big{[}Q^{-1}{\rm
diag}(n_{0,c}Q\hat{\bm{p}})Q^{-{\sf T}}\Big{|}{\bm{z}},{\mathcal{P}}\Big{]}$
$\displaystyle=n_{0,c}{\mathbb{E}}_{\bm{w}}\Big{[}Q^{-1}{\rm
diag}(Q\hat{\bm{p}})Q^{-{\sf T}}\Big{|}{\bm{z}},{\mathcal{P}}\Big{]}$

We next proceed with the second term on the right-hand side of (25). We have

$\displaystyle\sum_{\ell,\ell^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,\ell^{\prime}}Q^{-{\sf
T}}_{\cdot,\ell}Q_{\ell,y_{i}}Q_{\ell^{\prime},y_{j}}$
$\displaystyle=\sum_{\ell,\ell^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,\ell^{\prime}}Q^{-{\sf
T}}_{\cdot,\ell}(Qe_{y_{j}})_{\ell^{\prime}}(Qe_{y_{i}})_{\ell}$
$\displaystyle=\sum_{\ell,\ell^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,\ell^{\prime}}[(Qe_{y_{j}})_{\ell^{\prime}}(Qe_{y_{i}})_{\ell}]Q^{-{\sf
T}}_{\cdot,\ell}$
$\displaystyle=\sum_{\ell,\ell^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,\ell^{\prime}}(Qe_{y_{j}}e_{y_{i}}^{\sf
T}Q^{\sf T})_{\ell^{\prime},\ell}Q^{-{\sf T}}_{\cdot,\ell}$
$\displaystyle=Q^{-1}Qe_{y_{j}}e_{y_{i}}^{\sf T}Q^{\sf
T}Q^{-T}=e_{y_{j}}e_{y_{i}}^{\sf T}\,.$

Taking the expectation of both sides of the above equation, we arrive at

$\displaystyle\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[\sum_{\ell,\ell^{\prime}\in\mathcal{Y}}Q^{-1}_{\cdot,\ell^{\prime}}(Q^{-1}_{\cdot,\ell})^{\sf
T}Q_{\ell,y_{i}}Q_{\ell^{\prime},y_{j}}\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
$\displaystyle={\mathbb{E}}_{\bm{w}}\left[\mathsf{y}^{\sf
T}e_{y_{j}}e_{y_{i}}^{\sf T}\mathsf{y}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle=y_{i}(0)y_{j}(0)\,,$

where the second equality holds since $i\neq j\in\mathcal{O}_{0,c}$. Putting
these pieces together, we obtain

${\mathbb{E}}_{DP}[u_{0,c}^{2}|{\bm{z}},{\mathcal{P}}]=n_{0,c}\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\Big{[}Q^{-1}{\rm diag}(Q\hat{\bm{p}})Q^{-{\sf
T}}\Big{|}{\bm{z}},{\mathcal{P}}\Big{]}\mathsf{y}+\sum_{i\neq
j\in\mathcal{O}_{0,c}}y_{i}(0)y_{j}(0)\,,$

which along with (24) gives us

$\displaystyle{\rm Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})$
$\displaystyle={\mathbb{E}}_{DP}[u_{0,c}^{2}|{\bm{z}},{\mathcal{P}}]-{\mathbb{E}}_{DP}[u_{0,c}|{\bm{z}},{\mathcal{P}}]^{2}$
$\displaystyle=n_{0,c}\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm
diag}(Q\hat{\bm{p}})Q^{-{\sf
T}}\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}+\sum_{i\neq
j\in\mathcal{O}_{o,c}}y_{i}(0)y_{j}(0)-\left(\sum_{i\in\mathcal{O}_{0,c}}y_{i}(0)\right)^{2}$
$\displaystyle=n_{0,c}\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}\Big{[}Q^{-1}{\rm
diag}(Q\hat{\bm{p}})Q^{-{\sf
T}}\Big{|}{\bm{z}},{\mathcal{P}}\Big{]}\mathsf{y}-\sum_{i\in\mathcal{O}_{0,c}}y_{i}^{2}(0)\,.$
(27)

####  $\bullet$ Decomposing ${\rm Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})$

We wish to bound ${\rm Var}(u_{0,c}|{\bm{z}},{\mathcal{P}})$. We begin by
decomposing it into two distinct terms. Let
$\tilde{\bm{q}}=[\tilde{q}_{0}(y|c)]_{y\in\mathcal{Y}}\in{\mathbb{R}}^{K\times
1}$ be the distribution constructed in the DP mechanism after adding noise to
the empirical distribution $\hat{\bm{p}}$, truncation, and normalization. We
consider the following decomposition:

$\displaystyle Q^{-1}{\rm diag}(Q\hat{\bm{p}})Q^{-{\sf T}}=Q^{-1}{\rm
diag}(Q\tilde{\bm{q}})Q^{-{\sf T}}+Q^{-1}{\rm
diag}(Q(\hat{\bm{p}}-\tilde{\bm{q}}))Q^{-{\sf T}}\,.$

Plugging into (27),

$\displaystyle{\rm Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})=$ $\displaystyle
n_{0,c}\left(\underbrace{\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm diag}(Q\tilde{\bm{q}})Q^{-{\sf
T}}|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}}_{\text{term
I}}+\underbrace{\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm
diag}(Q(\hat{\bm{p}}-\tilde{\bm{q}}))Q^{-{\sf
T}}|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}}_{\text{term
II}}\right)-\sum_{i\in\mathcal{O}_{0,c}}y_{i}^{2}(0).$

####  $\bullet$ Bounding Term I

By definition, we can write $Q$ as
$Q=(1-\lambda)I+\lambda\tilde{\bm{q}}\bm{1}^{\sf T}\,$, with
$\bm{1}\in{\mathbb{R}}^{K\times 1}$ indicating the all-one vector.
Furthermore, $\bm{1}^{\sf T}\tilde{\bm{q}}=1$ because $\tilde{\bm{q}}$ is a
probability distribution (see (Esfandiari et al.,, 2022, Theorem 6)). Using
the Sherman–Morrison formula, we obtain

$Q^{-1}=\frac{1}{1-\lambda}I-\frac{\lambda}{1-\lambda}\tilde{\bm{q}}\bm{1}^{\sf
T}\,.$

Plugging for $Q$ and $Q^{-1}$, we have the following chain of identities:

$\displaystyle Q\tilde{\bm{q}}$
$\displaystyle=(1-\lambda)\tilde{\bm{q}}+\lambda\tilde{\bm{q}}=\tilde{\bm{q}}\,,$
$\displaystyle Q^{-1}{\rm diag}(Q\tilde{\bm{q}})$
$\displaystyle=\frac{1}{1-\lambda}{\rm
diag}(\tilde{\bm{q}})-\frac{\lambda}{1-\lambda}\tilde{\bm{q}}\tilde{\bm{q}}^{\sf
T}\,,$ $\displaystyle Q^{-1}{\rm diag}(Q\tilde{\bm{q}})Q^{-T}$
$\displaystyle=\frac{1}{(1-\lambda)^{2}}{\rm
diag}(\tilde{\bm{q}})+\frac{\lambda^{2}-2\lambda}{(1-\lambda)^{2}}\tilde{\bm{q}}\tilde{\bm{q}}^{\sf
T}\,.$

Using the last identity, we have

$\displaystyle\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm
diag}(Q\tilde{\bm{q}})Q^{-{\sf T}}|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
$\displaystyle=\frac{1}{(1-\lambda)^{2}}\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[{\rm diag}(\tilde{q})\right]\
\mathsf{y}+\frac{\lambda^{2}-2\lambda}{(1-\lambda)^{2}}\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[\tilde{\bm{q}}\tilde{\bm{q}}^{\sf
T}\right]\mathsf{y}$
$\displaystyle=\frac{1}{(1-\lambda)^{2}}\sum_{y\in\mathcal{Y}}{\mathbb{E}}_{\bm{w}}\left[\tilde{q}_{y}\right]y^{2}+\frac{\lambda^{2}-2\lambda}{(1-\lambda)^{2}}{\mathbb{E}}_{\bm{w}}\left[\left(\sum_{y\in\mathcal{Y}}y\tilde{q}_{y}\right)^{2}\right]$
$\displaystyle={\mathbb{E}}_{\bm{w}}\left[\frac{1}{(1-\lambda)^{2}}{\mathbb{E}}_{\tilde{\bm{q}}}[y_{i}^{2}(0)]+\left(1-\frac{1}{(1-\lambda)^{2}}\right){\mathbb{E}}_{\tilde{\bm{q}}}[y_{i}(0)]^{2}\middle|{\bm{z}},{\mathcal{P}}\right]$
$\displaystyle={\mathbb{E}}_{\bm{w}}\left[\frac{1}{(1-\lambda)^{2}}\Big{(}{\mathbb{E}}_{\tilde{\bm{q}}}[y_{i}^{2}(0)]-{\mathbb{E}}_{\tilde{\bm{q}}}[y_{i}(0)]^{2}\Big{)}+E_{\tilde{\bm{q}}}[y_{i}(0)]^{2}\middle|{\bm{z}},{\mathcal{P}}\right]\,.$
(28)

which can also be written as:

$\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm
diag}(Q\tilde{\bm{q}})Q^{-{\sf
T}}\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}=\frac{1}{(1-\lambda)^{2}}\Big{(}{\mathbb{E}}_{\tilde{\bm{q}},\bm{w}}[y_{i}^{2}(0)|{\bm{z}},{\mathcal{P}}]-{\mathbb{E}}_{\tilde{\bm{q}},\bm{w}}[y_{i}(0)|{\bm{z}},{\mathcal{P}}]^{2}\Big{)}+E_{\tilde{\bm{q}},\bm{w}}[y_{i}(0)|{\bm{z}},{\mathcal{P}}]^{2}$

In the following lemma, we relate the expectation of outcomes with respect to
$\tilde{\bm{q}}$ to their expectation with respect to $\hat{\bm{p}}$.

######  Lemma A.4.

If outcomes are bounded by $B$,

$\displaystyle{\mathbb{E}}_{\tilde{\bm{q}},\bm{w}}[y_{i}^{2}(0)]|{\bm{z}},{\mathcal{P}}]$
$\displaystyle\leq
B^{2}{\mathbb{E}}_{\bm{w}}\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}+\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)^{2}\,.$
$\displaystyle{\mathbb{E}}_{\tilde{\bm{q}},\bm{w}}[y_{i}(0)|{\bm{z}},{\mathcal{P}}]^{2}$
$\displaystyle\geq\left(\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)\right)^{2}-2B^{2}{\mathbb{E}}_{\bm{w}}\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}\,.$

Using the above lemma, we obtain:

$\displaystyle\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm
diag}(Q\tilde{\bm{q}})Q^{-{\sf
T}}\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
$\displaystyle\leq\frac{1}{(1-\lambda)^{2}}\Bigg{[}B^{2}{\mathbb{E}}_{\bm{w}}\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}+\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)^{2}\Bigg{]}$
$\displaystyle-\left(\frac{1}{(1-\lambda)^{2}}-1\right)\left\\{\left(\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)\right)^{2}-2B^{2}{\mathbb{E}}_{\bm{w}}\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}\right\\}\,,$

which can be simplified to

$\displaystyle\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}$
$\displaystyle\left[Q^{-1}{\rm diag}(Q\tilde{\bm{q}})Q^{-{\sf
T}}\middle|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}$
$\displaystyle\leq\frac{1}{(1-\lambda)^{2}}\left(\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)^{2}-\left(\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)\right)^{2}\right)$
$\displaystyle+\left(\frac{1}{n_{0,c}}\sum_{i\in{\cal
O}_{0,c}}y_{i}(0)\right)^{2}+B^{2}\Big{(}\frac{3}{(1-\lambda)^{2}}+2\Big{)}{\mathbb{E}}_{\bm{w}}\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}$
$\displaystyle\leq\frac{n_{0,c}-1}{n_{0,c}}\frac{S^{2}(\vec{y}_{0,c})}{(1-\lambda)^{2}}+\left(\overline{\vec{y}_{c}(0)}\right)^{2}+B^{2}\Big{(}\frac{3}{(1-\lambda)^{2}}+2\Big{)}{\mathbb{E}}_{\bm{w}}\left[\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}\right]\,,$
(29)

where $S^{2}(\vec{u})=\frac{1}{|\vec{u}-1|}\sum_{a\in\vec{u}}(a-\bar{a})^{2}$
and $\bar{\vec{u}}=\frac{1}{|\vec{u}|}\sum_{a\in\vec{u}}a$ .

####  $\bullet$ Bounding Term II

We begin with the two inequalities

$\displaystyle\mathsf{y}^{\sf T}Q^{-1}{\rm
diag}(Q(\hat{\bm{p}}-\tilde{\bm{q}}))Q^{-{\sf T}}\mathsf{y}$
$\displaystyle\leq\|Q^{-{\sf
T}}\mathsf{y}\|^{2}\|Q(\hat{\bm{p}}-\tilde{\bm{q}})\|_{\infty}$
$\displaystyle\leq\|Q^{-{\sf
T}}\mathsf{y}\|^{2}|Q|_{\infty}\|\hat{\bm{p}}-\tilde{\bm{q}}\|_{1}\,,$ (30)

where $|Q|_{\infty}=\max_{i,j}|Q_{ij}|$. For every $\ell\in\mathcal{Y}$
$\tilde{q}_{\ell}\geq\gamma$ (see (Esfandiari et al.,, 2022, Theorem 6)), and
$\sum_{\ell\in\mathcal{Y}}\tilde{q}_{l}=1$, which implies that
$\forall\ell\in\mathcal{Y},\tilde{q}_{l}\leq 1-(K-1)\gamma$. Therefore, by
definition of $Q$, we have

$|Q|_{\infty}\leq 1-\lambda+\lambda(1-(K-1)\gamma)=1-\lambda(K-1)\gamma\,.$

The following lemma bounds the maximum singular value of matrix $Q$.

######  Lemma A.5.

The maximum singular value of label randomization matrix $Q^{-1}$ is at most
$\frac{\lambda\sqrt{K}+1}{1-\lambda}$.

Using Lemma A.5, we get

$\displaystyle\mathsf{y}^{\sf T}Q^{-1}{\rm
diag}(Q(\hat{\bm{p}}-\tilde{\bm{q}}))Q^{-{\sf
T}}\mathsf{y}\leq\frac{(\lambda\sqrt{K}+1)^{2}}{(1-\lambda)^{2}}\|\mathsf{y}\|^{2}(1-\lambda(K-1)\gamma)\|\hat{\bm{p}}-\tilde{\bm{q}}\|_{1}\,.$
(31)

####  $\bullet$ Bounding ${\rm Var}(u_{0,c}|\bm{c})$

Combining (29) and (31) with the expression of ${\rm
Var}(u_{0,c}|\bm{c},{\bm{z}})$, we get

$\displaystyle{\rm Var}_{DP}(u_{0,c}|{\bm{z}},{\mathcal{P}})$
$\displaystyle=n_{0,c}\left(\underbrace{\mathsf{y}^{\sf
T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm diag}(Q\tilde{\bm{q}})Q^{-{\sf
T}}|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}}_{\text{term
I}}+\underbrace{\mathsf{y}^{\sf T}{\mathbb{E}}_{\bm{w}}\left[Q^{-1}{\rm
diag}(Q(\hat{\bm{p}}-\tilde{\bm{q}}))Q^{-{\sf
T}}|{\bm{z}},{\mathcal{P}}\right]\mathsf{y}}_{\text{term
II}}\right)-\sum_{i\in\mathcal{O}_{0,c}}y_{i}^{2}(0)$
$\displaystyle\leq(n_{0,c}-1)\frac{S^{2}(\vec{y}_{0,c})}{(1-\lambda)^{2}}+n_{0,c}\Big{(}(\overline{\vec{y}_{0,c}})^{2}+B^{2}\Big{(}\frac{3}{(1-\lambda)^{2}}+2\Big{)}{\mathbb{E}}_{\bm{w}}\left[\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}\right]+$
$\displaystyle\qquad\frac{(\lambda\sqrt{K}+1)^{2}}{(1-\lambda)^{2}}\|\mathsf{y}\|^{2}(1-\lambda(K-1)\gamma){\mathbb{E}}_{\bm{w}}\|\hat{\bm{p}}-\tilde{\bm{q}}\|_{1}\Big{)}-\sum_{i\in\mathcal{O}_{0,c}}y_{i}^{2}(0)$
$\displaystyle=\frac{n_{0,c}-1}{(1-\lambda)^{2}}S^{2}(\vec{y}_{0,c})+n_{0,c}(\overline{\vec{y}_{0,c}})^{2}-\sum_{i\in\mathcal{O}_{0,c}}y_{i}^{2}(0)+n_{0,c}A^{\prime}_{0,c}{\mathbb{E}}_{\bm{w}}[\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}]$
$\displaystyle=(n_{0,c}-1)\left(\frac{1}{(1-\lambda)^{2}}-1\right)S^{2}(\vec{y}_{0,c})+n_{0,c}A^{\prime}_{0,c}{\mathbb{E}}_{\bm{w}}[\|\tilde{\bm{q}}-\hat{\bm{p}}\|_{1}]\,,$
(32)

with