Improving the Variance of Differentially Private Randomized Experiments through Clustering
Authors: Adel Javanmard
Vahab Mirrokni
Jean Pouget-Abadie
Venue: ICML 2025 poster (2025)
Keywords: causal inference
differential privacy
clustering
Primary area: general_machine_learning->causality
TL;DR: We investigate the variance penalty incurred when estimating causal effects from differentially private data and introduce a novel mechanism, Cluster-DP, that leverages cluster information to reduce this gap.

Abstract: Estimating causal effects from randomized experiments is only possible if participants are willing to disclose their potentially sensitive responses. Differential privacy, a widely used framework for ensuring an algorithm’s privacy guarantees, can encourage participants to share their responses without the risk of de-anonymization. However, many mechanisms achieve differential privacy by adding noise to the original dataset, which reduces the precision of causal effect estimation. This introduces a fundamental trade-off between privacy and variance when performing causal analyses on differentially private data.
In this work, we propose a new differentially private mechanism, \textsc{Cluster-DP}, which leverages a given cluster structure in the data to improve the privacy-variance trade-off. While our results apply to
any clustering, we demonstrate that selecting higher-quality clusters—according to a quality metric we introduce—can decrease the variance penalty without compromising privacy guarantees. Finally, we evaluate the theoretical and empirical performance of our \textsc{Cluster-DP} algorithm on both real and simulated data, comparing it to common baselines, including two special cases of our algorithm: its unclustered version and a uniform-prior version.

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Adel Javanmard 12
Vahab Mirrokni 2
Jean Pouget-Abadie
Abstract
regulations for protecting individuals' online data. Many participants and regulatory guidelines agree with sharing some degree of information, as long as there is plausible deniability, meaning no response can be tracked to any in- dividual. While this can be achieved by sharing only ag- gregated data, this is often not sufficient to entirely prevent the risk of de-anonymization (Sweeney, 2000; Narayanan & Shmatikov, 2008). Differential privacy is one possible data-sharing framework which diminishes this risk.
Estimating causal effects from randomized exper- iments is only possible if participants are willing to disclose their potentially sensitive responses. Differential privacy, a widely used framework for ensuring an algorithm's 's privacy guarantees, can encourage participants to share their responses without the risk of de- anonymization. However, many mechanisms achieve differential privacy by adding noise to the original dataset, which reduces the precision of causal effect estimation. This introduces a fundamental trade-off between pri- vacy and variance when performing causal anal- yses on differentially private data. this work, we propose a new differentially private mecha- nism, CLUSTEER-DP, which leverages given cluster structure in the data to improve the privacy- variance trade-off. While our results apply to any clustering, we demonstrate that selecting higher- quality clusters-according according to a quality metric we introduce- can decrease the variance penalty without compromising privacy guarantees. Fi- nally, we evaluate the theoretical and empirical performance of our CLUSTER- DP algorithm on both real and simulated data, comparing it to com- mon baselines, including two special cases of our algorithm: its unclustered version and a uniform- prior version.
Ensuring a differential privacy guarantee often comes at the cost of adding additional noise to the original dataset, which increases the variance of statistical estimators. This poses a challenge for many causal inference applications that aim obtain the most precise measurements possible of a causal effect. However, not all attributes are sensitive. If non-sensitive attributes can be used to cluster users, we may be able to improve this privacy-variance trade-off.
Motivating application. We are specifically motivated by the following real-world scenario: suppose we own an adver- tising platform, and an advertiser wants analyze the effect of their advertising on custom user segments (e.g., users who have already signed up for their service versus those who have not). This segmentation is proprietary information that the advertiser does not wish to share with the platform. Mcanwhile, the platform mandates that user responses (c.g.. whether user has seen or clicked on an advertisement) can only be shared with the advertiser in a differentially private manner. By obtaining privatized user-level data, the adver- tiser can analyze the effect along this proprictary dimension. Notably, the platform can share non non-private information, such as the user's country or, more granularly, their DMA (designated marketing area), and use this non-private cluster information to improve the privacy-variance trade-off of mechanism. Motivated by this application, we focus on the problem of releasing privatized user-level data rather than solely protecting the privacy of the final causal effect estimation. Leveraging the post- processing property of differential privacy (Dwork et al., 2014), this approach provides advertisers with flexibility to conduct further analysis on privatized data without compro- mising user privacy.
1. Introduction
Measuring causal effects from randomized experiments as- sumes that participants are willing to share potentially sen- sitive private responses to treatment. This assumption is constantly challenged by the rise of privacy concerns and
their differeentiall-
'Marshall School of Business, University of Southern Cali- fornia, Los Angeles. USA *Google Research, New York, USA. Correspondence to: Adel Javanmard <ajavanma Sajavanma@usc.edu>>. Jean Pouget- Abadic <jeanpa @ google.com>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Our paper introduces novel causal and differentially pri-

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
vate mechanism CLUSTER-DP that theoretically and empir- ically improves on the privacy-variane, trade-off of other baseline mechanisms by leveraging non-private cluster in- formation about the dataset. To do so, we analyze the privacy-variance trade-off for an intuitive set of causal and differentially private baselines. These baselines 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 third-party. In particular, we show that our mechanism, and its analysis, general- which samples re-
without clustering (cf. Equation (9)).
Among other works in this space, Guha & Reiter (2024) de- velops differentially private (DP) algorithms for estimating weighted average treatment effects with binary outcomes by first characterizing the global sensitivities of point and variance estimators. A subsample-and-agee -aggeggeee approach generates noisy versions of these estimators, followed by Bayesian procedure to produce interval estimates. In contrast, Lee et al. (2019) use DP empirical risk minimiza- tion to estimate propensity scores via a logistic regression model, adding mechanism. Both (Guha & Reiter, 2024; Lee et al., 2019) operate within the central DP framework, where a trusted curator collects raw data. Ohnishi & Awan (2023) take a local DP approach, where individuals privatize their data before sharing, and propose minimax optimal estimator for population average treatment effects (ATE) under fixed assignment probabilities, achieving optimal mean-squared error (MSE) rates. The proposed estimator is a special case of Algorithm 3 (with one cluster), a benchmark that we discuss in Section A.4 and in our numerical experiments in Section A.8.
izes baselines like UNIFORM-PRIOR-I sponses at random from the space of possible outcomes, and CLUSTER- DP, which is a special case when all units belong to the same cluster. As this last baseline indicates, our mechanism imposes no restrictions on the properties of the clusters, except that they each be of cardinality at least two. Our mechanism yields the largest improvements when the clusters exhibit specific measure of cluster quality.
noise using the Gaussian
Organization of the paper. In Section 2, we define and motivate the differential privacy setting and causal objective of our work, and discuss several intuitive mechanisms for privatizing a dataset while still allowing for unbiased and consistent estimation of the average treatment effect. In Sec- tion 3, we introduce our novel private- private-and-caute anducausall 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 diffferentially-rrvvaal counterparts. We conclude in Section 4 with numerical experiments on simulated and real graphs to validate our claims and compare the empirical performance of each algorithm.
Other works have explored the privacy-utility trade-off in various causal inference settings. Betlei et al. (2021) developed a differentially private method called ADUM for learning uplift models in randomized control trials. Their approach involves adding Laplace noise to aggre- gated responses within feature- bins. They examine the privacy-utilige trade-off through the mean-squared er- ror of the estimator, although they do not utilize clustering to reduce estimator variance. Niu et al. (2022) introduced a multi-stage learning meta-algorithm under privacy con- straints, employing DP-EBMs and sample-spliting to esti- mate conditional average treatment effects (CATE). Their work focuses on privacy-accurace trade-offs but does not provide private unit-level data or use clustering techniques to improve variance. These studies underscore ongoing ef- forts to balance privacy and utility in causal inference, each employing distinct approaches with their own limitations.
1.1. Related works
There is vast literature on differential privacy and causal inference. Here, we will discuss only the works closely related to ours to better position our research.
Causal inference under privacy constraints. Within the growing body of work recently at the intersection of privacy and causal inference, Kancharla & Kang (2021) explore the problem of estimating average treatment effects in ran- domized control trials where binary outcomes are privatized using a differentially private mechanism. Their mechanism randomly returns altered responses the true responses, with some predefined probabilities. In contrast, our work extends beyond binary outcomes to a general discrete out- come space and improves the privacy-variance variance tradeoff by leveraging a clustering structure of responses, which is quan- tified by cluster quality. Unlike their approach, which does not account for the empirical distribution of responses, our method offers broader applicability and variance reduction through clustering. In the absence of non-compliers, the procedure in (Kancharla& & Kang, 2021) can be viewed as a special case of this work when considering binary outcomes
Label-Differential privacy. The notion of differential pri- vacy measure (Dwork et al., 2006a;b) is widely used in practice and extensively covered in the literature. In this work, we focus primarily on label differential privacy, intro- duced by Chaudhuri & Hsu (201 1); ef our privacy setting and Remark 2.1. The literature on label differential privacy is mostly dedicated to classification and regression tasks with the goal of improving excess risk while offering pro- tection for labels (Beimel et al., 2013; Bassily et al., 2018; Wang & Xu, 2019).
Our approach draws inspiration from the work of Esfan- diari et al. (2022), adapting their technique to the context of causal effect estimation. While their method was devel-
2

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
oped for a different purpose, namely reducing excess risk of model trained on private labels, we have modified and extended it to address the specific challenges of privacy- preserving causal inference. To highlight our contributions, first note that the two works operate under different setrings and assumptions: Esfandiari et al. (2022) posits an underly- ing data-generating law p(ylæ) and cluster heterogeneity measure based on the distance of the "conditional" label distribution of a sample its cluster, averaged on the entire population. In our work, the features are only used to form the cluster, and nothing beyond that. This allows us to have the flexibility of making our proposal fully DP (using DP clustering per Remark 2.1) and in general better control the privacy leakage of features (if any) as it only used to make clusters. Additionally, and unlike (Esfandiari et al., 2022), we do not assume any underlying data generative model and the cluster homogeneity we define is simpler, as it is only based on the outcomes and clusters, without conditioning on the features. Our variance analysis contains completely new ideas with no resemblance to the analysis of (Esfandiari et al., 2022). Here, we need to analyze the variance of the ATE and its inflation due to the DP mechanism, which is done in multiple steps, considering the randomness with respect the treatments, and the DP mechanism separately. In addition, we provide a tighter analysis of the privacy guarantee than the proof methodology of (Esfandiari et al., 2022), and also extend it to an (e, 6)-type guarantee (See Theorem 3.1 and Definition 2.2).
potential outcome of unit i if it is controlled, and ys if it is treated, each sampled from finite response space y of cardinality K = |2 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 later in Section 4.
For our CLUSTER-DD algorithm, we will further assume that there is some known clustered structure of these units into C |C| non-overlapping clusters of size ne. and let G E C be the cluster membership of unit i. These clusters can 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, except that they must contain at least two units. In particular, our results hold for single large cluster. We show later in Section 3 that our results improve with specific measure of cluster quality.
Our causal estimand is the average treatment effect es- timand defined in the finite sample regime by T Σ (1)(1) - (0)) While we focus on the common finite sample setting, our results can be extended to their super- uuperpopulation equivalents, in which case, we denote by xy E R2d the covariate vector of each unit such that each (x,, (0), y (1), c,) is drawn from some joint distribution P.
1
n
Let z correspond to the treatment assignment of unit i, 2, = 1 if treated and 2; = 0 if controlled. Let n, be the total number of treated units and no to be the total number of controlled units across units. Treatment and control are assigned completely at random. When clustering of the data is available, the treatment assignment is sampled in completely randomized way over clusters: a fixed number of 71, (resp no,c) units is chosen uniformly at random to be treated (resp. controlled) within each cluster C, with ne = N1.c + Roo.c the total number of units in cluster c.
2. Causal Objective, Privacy Setting, and Common Baselines
We are motivated by a real-world scenario of a technol- ogy company 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. One reason for this might be that advertisers wish to run their own covariate-adie adjjsttmet methods, or they would like to in- vestigate proprietary sub-slices of users. On the other hand, this technology company seeks to protect the privacy of its users. Hence it must act as central unit which privatizes its datasets before passing them on to advertisers for them to perform their own causal inference analyses. We now intro- duce the formal causal objective and privacy setting, as well as a set of common baselines. To guide the reader through abundant notation, we include glossary at the beginning of the Appendix.
Privacy Setting. In the real-world advertising setting pre- sented above, it is assumed that a central unit privatizes the dataset before sharing it externally. Some of the mecha- nisms we explore also work without the presence of this central unit, setting known local differential privacy, but this is not a requirement.
In our setting, we have three key variables: outcomes, treat- ment assignments, cluster membership. An important ques- tion is which of these variables should be privatized. In our advertising setting, a unit's '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. In our exposition, primarily assume that the cluster structure is non-sensitive information (as is the case in our motivating application, where clusters can be formed based on user's 's country of designated market area). Nonetheless, as we discuss in the following remark, we can easily extend it to applications where cluster structure is
Causal Objective. We consider a fixed population of n units where we can assume the Stable Unit Treatment Value Assumption (Imbens& & Rubin, 2015). Let (1) be the
3

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
also deemed sensitive and should be privatized.
for the central unit to add noise 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 refer to this approach as the NOISY HISTOGRAI AASTOGRAM A ap- proach. We provide in Appendix A.4 a formal description of this approach, written in the broadest generality when a clustering is available, as well as a proof of its differential privacy guarantee along with its variance gap.
Remark 2.1. The privacy protection of cluster structure can be decoupled from that of outcomes. In particular, by virtue of the composition property of differential privacy (Dwork et al., 2014), we can allocate ê\ privacy budget for priva- tizing the clusters and E2 privacy budget for privatizing the outcomes. The end-to-end process will be E(= E1 + E2) is worth noting that there already exists a rich literature on Dl-clusterigg algorithms, see e.g., (Nissim el al., 2007; Feldman et al., 2009; 2017; Stemmer & Kaplan, 2018; Co- hen et al., 2021).
These aggregation- based approaches have two drawbacks in the real-world setting described in Sec- tion 2. First, in practice, advertisers expect user-level data, even if privatized. This is likely because they wish to ana- lyze their own segments of the user population or apply their own proprietary covariate -adiriatt-tdustmmentt methods. Second, the noise of these aggregated approaches is averaged over the number of clusters C' (if any) or over the number of possible outcomes K. User-level mechanisms on the other hand, add noise that is averaged over n, the number of users. This becomes yet another 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 >> K and > 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 through experiments in Appendix A.8.
Limitations.
Following Remark 2.1, we focus on privatizing the out- comes, assuming a given non-sensitive cluster structure. This approach aligns with the concept of label-differential privacy, introduced by Chaudhuri & Hsu (2011).
Definition 2.2. (Label Differential Privacy) Consider randomized mechanism M D - O that takes as in- put dataset D and outputs into O. Let e, ō E Rgzo- A mechanism M is called (e, 8)-label differentially private- or (E, ---bbel if for any two datasets (D, D') that dif- fer in the label (outcome) of a single example and any subset O S O we have TP (D) E O] S (D' E O] + 5, where is the privacy budget and 8 is the failure probability, If u = 0, then M is said to be e-label differentially private, or e-label DP.
The (e, didfferrreee privacy property states that it is un- likely that the observed output has a much higher or lower chance to be generated under a dataset D compared to a neighboring dataset D'. In our context, a unit's "label" refers to its observed outcome; we use the words outcome and label interchangeably.
The UNIFORM-PRIOR-I baseline. We also consider a differentially private causal mechanism that reports the true outcome with some probability, and otherwise reports an out- come sampled uniformly at random from the space of pos- sible outcomes. We refer to it as the UNIFORM-PRIOR-DD mechanism, formalized in Algorithm 1, because it does not leverage any information about the empirical distribution of outcomes beyond its support. The UNIFORM-RRIOR DP mechanism is a generalization of the mechanism proposed by (Kancharla & Kang, 2021) in the binary-outcome setting, when there are no non-compliers.
It is worth noting that the differential privacy focuses on the privacy loss to an individual by her contribution to a dataset. In the context of label-DP, one may wonder that the potential correlation between non-sensitive features and the labels may violate privacy of individuals. In such cases, it is the correlational pattern and the conclusions reached that affect the individual, not her presence or absence in the data set. We refer to (Dwork et al., 2014)CChapter 1) for an elaborate discussion.
Algorithm UNIFORM- DP mechanism
Two nggregation-barn based baselines. Perhaps 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 yi and add noise to the estimate before sharing it exter- nally. We provide in Appendix A.4 a formal description of this approach for the Horvitz-Thompson estimator, de- fined in Appendix A.2, which we refer to as the NOISY HORVITZ-TIOOMPSON mechanism, along with a proof of its differential privacy guarantee and its variance gap.
Input: Individual responses .i.....IM -Vn Output: Privatized responses 91.....9h Un for i E n.. do
v ~ (())
with probability À
II l the uniform distribution with probability 1 - A Return privatized responses (u...., J.
01
Ys
In the broadest generality when a clustering is available, the following stratified estimator is unbiased for the average
second and slightly more sophisticated approach would be
4

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
treatment effect:
For the sake of exposition, focus on the controlled units of a cluster C.
1
Di
7. 2,)
(1) Compute the empirical response distribution of the con- trolled units in the cluster po (yle).
111
140.c
As we discuss in Section 3, the UNIFORM-PRIOR-DE mech- anism is a special case of our proposed algorithm. We include its privacy guarantees and the variance gap of ix in Appendix A.5.
(2) Add noise drawn from a Laplace distribution with pa- rameter (a/no. to each response probability.
(3) Truncate the response probabilities be within the in- terval ly, 11, with Y S 1/K.
3. The CLUSTER-DP and CLUSTER-FREE-DP Mechanisms
(4) Renormalize the response probabilities to form dis- tribution, i.c. such that the resulting response probabilities remain in [y, 1], and add up to one.
We now introduce our differentially private mechanism, CLUSTER which not only provides user-level priva- tized outcomes, but also leverages information about the empirical distribution of outcomes within each cluster to im- prove its variance gap, When no good clustering is available, we consider its special case when all units can be considered part of the same cluster, the ST.USER--RREE-D mecha- nism.
(5) With probability X, each original response is replaced by random sample from this distribution constructed in the previous step.
3.1. Privacy guarantees
The following theorem and its corollary state the differential privacy guarantee of our CLUSTER-DD DP mechanism.
Algorithm 2 Our CLUSTER-DD mechanism
Theorem 3.1. Let ē > and := max(0, À x X )) The CLUSTER-DP mechanism described in Algo- rithm 2 is (e, 5)-label DP with min :/ 2 + 3 By setting log(1 + 1x2)), we have = O, and there- fore the CLUSTER-DP mechanism is also e-label DP, with 0
Parameters: threshold y E [o, 1/x]; noise scale o 2 0: re-sampling probability À E []
Input: Individual responses 1/1 V1..... Mh. treatment assign-
ments 21y.... Zn.
Output: Privatized responses V1 V1..... In
1 2 + log [ 1-1
for e E C do
=minn
for E {0, 11. E ) do 9. (vlc)) + max w ~ Laplace(o/naa.
where
We refer the reader to Appendix A.13 for a full proof of Theorem 3.1 and provide here some intuition for its stated privacy loss E. The first term min (1/a, 2/4) is the privacy budget used to privately estimate the empirical response distribution (-Ic) for each cluster. Fixing the transformed empirical distributions T. (-Ic), the log term is the privacy budget used to generate the privatized responses Js. By the composition theorem for differential privacy (Dwork et al. (2014), Theorem B. the total privacy loss is given by the sum of these two losses. As expected, when the resampling probability goes zero (A + 0), the privacy loss grows large (e + +oo). Similarly, as the Laplace noise and truncation parameter y grow large, the privacy guarantee improves (s + 0).
for E {0. 1) do
for y E ) do
if Σ, (vlc) > then
Sy < La (ylc) -7
else
Sy x- - (a(llc)
for MryEN y do
(v(c) + qalyle)
*E Su by (1- Ea(lle)))
for E [1....m] m} do
- vf ~ (z.())
with probability X
yi
with probability 1
Return privatized responses ........ ..
The CLUSTER- FREE mechanism. Because these privacy guarantees do not depend on the size, cardinality, or quality of the clusters, Theorem 3.1 also holds for the special case where there is no cluster structure to the data, in which case we repeat the same mechanism if all units belong to the same large cluster. We refer to this mechanism as the CLUSTER-FREE-DD mechanism, it has the same privacy guarantee as the CLUSTER- -D mechanism. We will show the benefit that clusters may have in Section 3.2.
Formalized in Algorithm 2, our proposed mechanism deals with each cluster individually and independently of other clusters, handling treated and controlled groups separately. It returns privatized potential outcome ÿ; for each unit, which is either the true outcome with some probability or sampled from a transformed empirical distribution re- sponses from units in the same cluster. The transformation inspired from a mechanism in (Esfandiari et al., 2022).
5

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
The distribu- tions da (y(y)c constructed in the CLUSTER-DP mechanism obey the following properties: L. (2(c) 2 for all y e V. and Σy (v(c) = 1. When setting the truncation pa- rameter 7 = 1/K, these distributions reduce to uniform dis- tributions over the space of all outcomes, in which case the cluster-DP mechanism amounts to the simpler UNIFORM- PRIOR-DP mechanism introduced briefly the end of Sec- tion 2, regardless of the value of the Laplace noise variance o², We obtain the privacy guarantees of this baseline, de- tailed in Section A.5, as a corollary of Theorem 3.1.
Similarity with UNIFORM-PRIOR-DE
treatment assignment, the privatized response Vs well the vector of probabilities y" Qayee An illustration is included in Figure 1.
Observeed data
Privatizing central unit
(Se, Ci)
(Ri, Ci)
(Br)
Privatized cutcome
3.2. Estimation and variance guarantees
Treated [x- 1)
Controlled [<=
We now consider estimating causal effects from the pri- vatized outcomes provided by our CLUSTER-DP mecha- nism. For each cluster E C and each value a E {0, 1} of treatment, we construct the response randomization matrix Q0,a RRKKK
Figure 1: Illustration of CLUSTER- DD mechanism with a central unit computing the (clustered) privatized outcomes for valid causal inference.
Qc,aly's u]
y) (1- + AQa(3'lc).
:1 :
=)
Since qu (-Ic) and the responses Yt are E-DP, by the post- processing property of differential privacy (Dwork al. (2014), Proposition 2.1), all the information passed to the third-party, as well as any estimation based on this informa- tion, is also e-DP.
Conditional its true outcome yi. treatment assignment 24, and cluster assignment c,, the privatized response i of unit i is distributed according to Qe,, (ū. v:l: Vy', P(ùs y'|G, zi; y/) = Q,,,, Iv/, yi]-
Remark 3.3. Note that the estimator iq depends on Q for E {0, 1]. From (2), Qe,a is a scalar of the identity matrix plus a rank one matrix. As shown in the proof of Proposition A.9 (ef. (27)), Q also a rank one perturba- tion of the (scaled) identity matrix. In Lemma A. we bound the maximum singular value of Q Using this lemma, the minimum singular value of FQ is at least (1 (1- ()/D>///// (IIAAK++1) +1). Therefore, Q is well-conditioned if X < 1, which will be the case by choosing a < & in our privacy bound in Theo- rem 3.1. This is also reflected in the variance bound, Theo- rem 3.5, where (1 X)² appears in the denominator.
We use the inverse of the response randomization matrix to debias the privatized responses. We use the notation y to represent in vector form the space of all possible potential outcomes, with similar ordering of rows and columns Qc,,2. With small abuse of notation, we write the index I: of the vector yJ Qu.l. as y Q [ii] and show that it is an unbiased estimate for yi over the randomness of Algo- rithm 2. As a result, by reweighting each privatized outcome by the inverse of its conditional probability of occurring Qc.., IM.. y4]. we construct an unbiased and consistent es- timator for the average treatment effect in the following Theorem, proof of which can be found in Appendix A.14.
Our goal for Algorithm 2 is to make the gap between the variance of our differentially -private estimator f and its non- differentially private counterpart NN as small as possible for given privacy guarantee. While all our results hold for any given clustering, they are greatly improved when clusters are homogeneous.
Theorem 3.2. Consider the following fq estimator;
( (
y" (17)
M1.
no.c
CEC
iEc
Conditionally on the randomness of the trealment assign- ment, to is equal in expectation over the randomness of the DP mechanism to the stratified cittrence-in-mman estima- tor below, henceforth &No-DE, which also implies that to is an unbiased and consistent estimator of
Definition 3.4 (Cluster homogeneity). For {0, 1}, de- fine a clustering' 's homogeneity as the average intra-cluster variance of outcomes Φa 2 0:
n 52 (Te(a))
Epp[to/2| = Σ The Σ
(1)
25
(0)
1 Zi
CEC
n²
Na,c
cEC
71..c
700c
where for vector ū E Rd, (2(T) = + E u)².
For third parties to compute this estimator themselves, the central unit must pass along the cluster assignment, the
The quantity da has a natural super-populatee interpreta- tion when taking its expectation of over the distribution P:
6

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
He E[Var(v(a)le)] Var(y(a)) - Var(Bly(a)]ec) > O. Holding Var(y(a)) constant, lower values of da implies that clusters are better separated. For &. = O, the outcome values of each clusters are contained within a singleton set. On the other hand, if &a is high, clusters contain a wide range of responses, up to the variation of outcomes of the population.
mechanisms reduces to the guarantee of the UNIFORM- PRIOR-DP mechanism in Theorem A.5 when setting the truncation parameter 7 = and oo. Because both CLUSTER- DD and CLUSTER FEERR-FREEDDD mechanisms use data-dependent priors, there may exist choices of (a, % A) which result in better privacy-variant trade-offs than the latter for certain outcome distributions. In the following section, we conduct empirical evaluations of the privacy- variance trade-off of the different mechanisms.
We now state our key theorem, which provides a bound on the variance of our estimator fo. with respect to the randomness of Algorithm 2 and the random assignment 2,
as a function of Var, [PNo-D]] and du.
4. Numerical Experiments
Theorem 3.5. The variance of to defined in Theorem 14 is bounded by
In this section, we perform several experiments to validate the claims we make the paper and to illustrate their useful- ness. Due to the strong limitations of the aggregation- based baselines in our real-world setting, we focus our attention three UNIFORM PRIOR DP, CLUSTER- FREE-DP, and CLUSTER- DD mechanisms, and relegate further experimen- tal investigations of these aggregation-base baselines to Appendix A.8.
0 S VaIDP, [To) Varz(fNo-Da
1 2)2
Σ Φa
ne A(na,))
n2 na,c
(E(0)))
(0
CEC
where @u is the measure of cluster homogeneity defined in Definition 3.4, and for any
We start by considering a Gaussian Mixture Model setting where for every unit in cluster c, a continuous quantity y is given by
2 ( 10000----10 A(z) =- 22 [ x
- -6-0/o]]
2/1y1B +...
31yy13 + (AVK + 1)2 + |1y - A(K- 1)m)
CiE 1.= /Bp. + V Bw,
(3)
(1-
where He and wA are drawn from the standard normal distri- bution. The coefficient / E [0, v] measures the dependence of the response on the cluster center. This specific param- eterization is chosen to fix the variance of the response, equal to v, as 3 varies. Since the proposed mechanism is for discrete outcome spaces, we quantize the response in the following way:
with K the number of possible outcomes and y {)}K the vector of all possible outcomes.
Theorem 3.1 and Theorem 3.5 together allow us to capture the privacy-variance trade-off of our proposed mechanism. Recall that the privacy guarantee of Theorem 3.1 is agnos- tie to the clustering. On the other hand, the variance gap in Theorem 3.5 depends first on the homogeneity of clus- ters, as defined in Definition 3.4, and a second term that is agnostic to the clustering. As a result, more homoge- neous teisters-thoss with low re-result in a smaller vari- ance gap with equal privacy guarantees, leading to a better privacy-variance trade-off than less homogeneous clusters.
K' o/
(1) = (0)+ and (0)))= =
- if < -
[w/A] otherwise
where A = 2 K' and [x] denotes the rounding of to the nearest integer. The treatment effect is additive term on the potential outcome under control. We fix
We can also provide some intuition for the second term A(z). By choosing 7 and to be arbitrarily small, we can make this second term arbitrarily small. As expected, the pri- vacy guarantees of Theorem 3.1 suffer in that regime. When setting À = O, our CLUSTER-DD DP mechanism always out- puts the true outcome, and we no longer produce privatized outcomes. In that case, we can set the truncation parameter y and the Laplace noise to be zero with no consequence to recover the trivial equality (fFDp,=(f) = Varz [NN..PP) from our bound above. Naturally, the more interesting set- ting from a privacy perspective is À E (0,1). 1).
= 1, such that the outcomes take values in the set ) { K',..,,,,, 14...,K,, O,.., K', K' +1}. We denote by K := 2(K'+ + 1) the size of outcome space.
Unless otherwise specified, and with no particular reason to fix parameters one way or another, we take K' 5. e = 5, and B 4.5. We consider C' = 3 clusters of sizes 500, 10 2 x 10a 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 x 10 5 x 103, and 1 units, and repeatedly draw uniformly at random uub-oopulations of three clusters from these original clusters.
As discussed previously, the privacy guarantee in Theo- rem 3.1 for the CLUSTER-DD and CLUSTER FREE-DP
7

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
For any given sub-population, we compute the variance Varpr: by empirically computing the variance (or his- togram) of fo empirically over 500 realizations of the ran- domness 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 CLUSTER- DP mechanism, we set the truncation parameter y = 0.02, the Laplace noise 10, and the resampling probability A = 0.8.
Experiment 2. (Role of clustering quality) In this ex- periment we show that, the clustering quality improves, the variance of the estimator for the CLUSTER-DP mech- anism decreases when compared to the variance of the estimator for the CLUSTER FREE-DP mechanism, with- out affecting their privacy guarantees, since these are ag- nostic to the clustering according to Theorem 3.1. Under our specified potential outcome model (3), the cluster ho- mogeneity da. as defined in Definition 3.4, is given by B = 61. hence our clusters become more homogeneous as 3 increases. From Theo- rem 3.5, the clustering structure reduces the variance of the estimator at more homogeneous clusters, i.e. lower values of do 61, and A. We verify this in Figure (1.c), which plots the ratio of the variances for two values of À {0.5, 0.8] as we vary B. As B grows, we observe a stronger reduction in the variance using the clustering structure of data. This effect is stronger at smaller values of X.
<o = ((Var(()(0)))c)
Experiment 1. (Privacy-variance trade-off) We com- pare the privacy-variangs trade-off of our suggested CLUSTER-DP mechanism with the CLUSTER-FREE--E mechanism, 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 (E, 6).
Experiment 3. (Simulation on YouTube data) Finally, we validate our results on subset of the YouTube social network to replicate two experiment results in a setting with natural clusters. We compare the variance of our suggested estimator for the CLUSTER- 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 1.
In Figure (1.a), we aim to fix the privacy loss to E = 0.2 and 8 10 for all three mechanisms. For the CLUSTER- DP and CLUSTER-FREE DP, we set the Laplace param- eter to = 10, and vary the truncation parameter y E /0.1/K1 1/K.. Following Theorem 3.1, we first choose e so that the corresponding privacy E, is equal to its target E =.2., and then choose the re-sampling probability A to obtain the failure probability 5 = 10-4, Likewise, for the ANIFORM-PRIOR-DD mechanism, we set the re-sampling probability À according to Theorem A.5, such that ε = 0.2 and 8 = 10-4. In summary, as the truncation parameter y varies, we compare the three mechanisms at the same pri- vacy loss. As we observe in Figure (1.a). for small values of y, the CLUSTER-DD achieves significantly lower variance compared to to the other mechanisms. When 7 = 1/K and = c0, the theory tells us that CLUSTER- DP reduces to UNIFORM-PRIOR- DP (stratified) and the CLUSTER FREE- DP reduces to UNIFORM PREMMMPPPOR----I DD (unstratified). How- ever, since we have set 10, we observe that the variance for the MELFORM-PRIORR D becomes lower than the other mechanisms for 7 1/k. The error-bars here correspond to 50 independent draws of the nub-population.
The YouTube social network dataset (Leskovec & 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:
y (0) x B wi, (e(1) - (0) +T,
with wy ~ N(O, capturing individual i's effect and the x! 3 term capturing the cluster-level effect. We follow a similar model as in (Zhou et al., 2020) and consider a four- dimensional feature vector 2;, with 2.1 being the number of nodes in cluster e; (the cluster of user i), 222 the number of edges in c; Tyy the number of edges in e; with other clusters, and wi the density of cluster G. Recall that for a cluster with n nodes and e edges, its density is defined as (3)
In Figure (1.b), we plot the variance of each estimator ver- sus its privacy loss E, we fix 5 10-4. Here, we op- timize the choice of Laplace parameter E {10, 20, )o} and the truncation parameter E (0.01/K, 0.1/K, 1/Kr. We observe that both CLUSTER- DP and CLUSTER FREE-DP DP estimators achieve a better trade-off than either version of the URIFORM-PRIOR- DP mechanism. Furthermore, the CL.STEER DP mechanism, which also leverages the cluster- ing structure, showcases an even better trade-off compared to the CLUSTER FREE FREE-DPPme mechanism.
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; to 0.1. In our experiments, we set B = 1,, and = 1. In the CLUSTER-DP mechanism, we set the truncation threshold to y = 0.1/K and the Laplace noise level to o = 5. In Figure (1.d), we plot the privacy-variance trade-off for the
8

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
unlerr (lattaiiraeeei
Batke DP man ahd
1.8
1.6
1.4
1.2
netrst witern ber Jater on
108
0.7
044
0.8
05
0.
0.2
0.4
08
08
03
13
(l.a)
(L.b)
(I.c)
(1.d)
Figure 2: Fuller figures can be found in Appendix A. (I.a) Variances each mechanism as we vary the truncation level Y E (0.1/K11/ 1/K] in Experiment 1. Privacy loss fixed at e = 0.2 and 5 = 10-1 (1.b) Privacy-variance trade-off of each mechanism under the setting of Experiment We fix the DP failure probability
10 and optimize the choice of {10, 20, (o) and y E {0.01/K /K, 0.1 / 1/x]. (1.c) Ratio of the variance of the estimators under the
and y in the sets CLUSTER-DP and CLUSTER FREE-DP mechanisms in Experiment 2. The benefit of CLUSTER-DP mechanism is stronger at larger 3 and smaller value of A. (I.d) Privacy-variance trade-off of the CLUSTER- DP and CLUSTER FREE-DP DP stratified estimators for the YouTube dataset in Experiment 3. The dotted line is the variance of the non-private stratified estimator.
CLUSTER-DD DD and the CLUSTER FREE-DP mechanisms, along with the variance of the non-private stratified estima- tor, finding once again that the CLUSTER-DP mechanism achieves a better trade-off by leveraging the natural cluster structure of the Youtube users.
reviewers for their feedback on improving this paper.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here
In Appendix. We include further experimental investiga- tions in Appendix A.6, A.8, and A.9, to verify, amongst others the unbiasedness and consistency of our estimators, as well as illustrate the limitations of aggregation-base based baselines against either of these three user-level mecha- nisms. We also include fuller versions of the subfigures in Figure 2.
References
Bassily, R., Thakurta, A. G., and Thakkar, O. D. Model- agnostic private learning. Advances in Neural Information Processing Systems, 2018
5. Conclusion
Beimel, A., Nissim, K., and Stemmer, U. Private learning and sanitization: Pure vs. approximate differential privacy. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 363-378. Springer. 2013.
Among differentially private algorithms that allow for valid causal inference, our approach leverages the presence of a non-private clustering structure to minimize the variance gap, as a function of cluster quality, while maintaining privacy guarantees constant. Our procedure generalizes cluster-free procedure, which we propose and compare to, as well more common uniform-prior baseline. We find that, theoretically and empirically on synthetic and semi- synthetic data, our approach outperforms these two methods. Furthermore, our setting, motivated by a real advertising scenario, precludes the use of aggregation-base methods, which we investigate as well.
Betlei, A., Gregoir, T., Rahier, T., Bissuel, A., Diemert, E., and Amini, M.-R. Differentially private individual treatment effect estimation from aggregated data. hal- 03339723, 2021.
Chaudhuri, K. and Hsu, D. Sample complexity bounds for differentially private learning. In Proceedings of the 24th Annual Conference on Learning Theory. pp. 155-186. JMLR Workshop and Conference Proceedings, 2011.
Acknowledgment
Cohen, E., Kaplan, H., Mansour, Y., Stemmer, U., and Tsfa- dia, E. Differentially prriip clustering of easy instances. In International Conference on Machine Learning, pp. 2059-2059. PMIR, 2021.
Adel Javanmard is supported in part by the NSF Award DMS-231 1024, the Sloan fellowship in Mathematics, an Adobe Faculty Research Award, an Amazon Faculty Re- search Award, and an iORB grant from USC Marshall School of Business. The authors are grateful to anonymous
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via dis-

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
tributed noise generation. In Advances in Cryptology- EUROCRYPT 2006: 24th Annual International Confer- ence the Theory and Applications of Cryptographic Techniques. St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pp. 486-503. Springer, 2006a.
Narayanan, and Shmatikov, V. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium Security and Privacy (sp 2008), pp. 111-125. IEEE, 2008,
Nissim, K., Raskhodnikova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Pro- ceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75-84, 2007.
Dwork, C., McSherry F., Nissim, K., and Smith, A. Cal- ibrating 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. pp. 265-284. Springer, 2006b.
Niu, F., Nori, H., Quistorff, B., Caruana, R., Ngwe, D., and Kannan, A. Differentially private estimation of heteroge- neous causal effects. In Conference on Causal Learning and Reasoning, pp. 618 (88-633.22 PMLR, 2022.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoreti- cal Computer Science, 9(3 4):211-407, 2014.
Ohnishi, and Awan, J. Locally private causal in- ference for randomized experiments. arXiv preprint arXiv:2301.01611 2023.
Esfandiari, H., Mirrokni, V., Syed, U., and Vassilvitskii, S. Label differential privacy via clustering. In International Conference on Artificial Intelligence and Statisties, pp- 7055-7075. PMLR, 2022.
Stemmer, U. and Kaplan, H. Differentially private k-means with constant multiplicative error. Advances in Neural Information Processing Systems, 31, 2018.
Feldman, D., Fiat, A., Kaplan, H., and Nissim, K. Private coresets. In Proceedings of the forty-first annual ACM symposium Theory of computing, pp. 361-370, 2009.
Sweeney, L. Simple demographies often identify people uniquely. Health (San Francisco), 67 (7100000): 1-34, 2000.
Feldman, D., Xiang, C., Zhu, R., and Rus, Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks. In Proceedings of the 16th ACM/IEEE International Conference Infor- mation Processing in Sensor Networks, pp. 3-15, 2017.
Wang. D. and Xu, J. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, pp. 6628 00--6667722 PMLR, 2019.
Wasserman, L. and Zhou, S. A statistical framework for differential privacy. Journal of the American Statistical Association, (15(489):375-389 2010.
Guha, S. and Reiter, J. P. Differentially private estimation of weighted average treatment effects for binary outcomes. arXiv preprini arXiv:2408.1 I 14766, 2024.
Zhou, Y., Liu, Y., Li, P., and Hu, F. Cluster-adaptive network a/b testing: From randomization to estimation. arXiv preprint arXiv:2008.0 08648, 2020.
Imbens, G. W. and Rubin, D. B. Causal inference in statis- tics, social, and biomedical sciences. Cambridge Univer- sity Press, 2015.
Kairouz, P., Oh, S., and Viswanath, P. The composition the- orem for differential privacy. In International conference on machine learning, pp. 1376-1385, PMLR, 2015.
Kancharla, M. and Kang, H. A robust, differentially private randomized experiment for evaluating online educational programs with sensitive student data. arXiv preprint arXiv:2112.02455, 2021.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What can we learn privately?
SIAM Journal on Computing, 40(3):793-822 2011.
Lee, S. K., Gresele, I.,, Park, M., and Muandet, K. Privacy- preserving causal inference via inverse probability weight- ing. arXiv preprint arXiv: /905. 12592, 2019.
Leskovec, J. and Krevl, A. SNAP Datasets: Stan- ford large network dataset collection. http://snay stanford. edu/ data, June 2014.
10

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
A. Appendix
A.I. Notation and common formulas
We recall here all the notations used in the paper and in the proofs:
total number of units.
ng (resp. n1)
total number of controlled (resp. treated) units.
treatment assignment of unit in {0,1), with i; 1 (resp. 0) indicating treatment (resp. control).
response space of cardinality potential outcome in of unit under treatment assignment 2. privatized outcome in Y of unit returned by the DP mechanism. vector notation of the entire response space (y) set of all clusters of cardinality C |C|
= | co.
Ve (z)
y:
cluster membership of unit i. number of units in cluster c, equal to { E [n] c = cf|- units belonging to cluster c with treatment assignment a, equal to {i: C == = C, 24 = aa. units belonging to cluster c, equal {i: c c). Oa,el for E {0,
O
Oe
na.cc
minimum of clipped empirical distribution, in [0, 1/K].
noise scale.
1- A Pa(Ulc)
true response sampling probability.
true distribution for treated (a 1) and controlled (a 0) units within cluster c, equal to (aY = y/c, = =c)
Pa(3)c)
empirical distribution for treated (a 1) and controlled (a 0) units within { C c, a. =
cluster equal to
Hi C; c, 2, a} measure of cluster quality, equal to Var (ar(E(Ya))eex)) response randomization matrix equal to (1 A)I((y' = y) + Aqd(v'lc).
da
Qcal's val uae
Σieo., Ey'ey Q D:ly'.
Ja
vector of outcomes observed by the central unit in cluster e with treatment assignment a, equal to (u) : E Oa,e), for E {0, 1}.
To(a)
all potential outcomes corresponding on units in cluster e and treatment assignment a, equal to (a) c = c). Note that (a) contains unobserved values.
indicator vector in gx with at the 8-th position and zero everywhere else.
A(x)
recurring expression in variance bounds, equal to 2K' { B²
(1-X)² + 2) +
3
(Av(+1)² (1-Xy² |1 A(K 1m)3 [ & -0/o 2/0

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
When the context is clear, sometimes adopt this lightened notation
P empirical probability of outcome for the controlled units in cluster c, equal No.e l6 O.e. : 3/1 = 2
p
empirical distribution outcomes of the controlled units in cluster c, arranged into a K K-dimensional vector, with coordinates pe, equal to jplley IR xxx1
Q
Qa,0
Qa.b b
Qc.ola,bj.
Q b].
Q
(Q-1)T.
q
distribution constructed in the DP mechanism (after adding noise to empiri- cal distribution Po,D, truncation and normalization), equal to [oo(vlc)lge> R
coordinate of vector q.
A.2. Variance of the Morvitz-Thomper estimator
The variance of the stratified Horvitz-Thomee Torvizz-Thompson estimator well-known. We recall it below:
NNO-DP := =>- nhe
ys
y: -1) zi)
11.
Ba.e
REC
iEc
Je = (w: c) E nm be the vector of outcomes of units in cluster and == Fc(1) - (0) be the vector of the
differences between each unit's potential outcome in treatment and in control. The variance of NN-DDP is given by
Var Varz(FNo-DP) [PN = Σ (T)(() + (7) (²(F))
n
n
R1.
10..c
CEC
where, for any vector u E Rd, (T) ア Euea(u
7) and ū = A Eued The formula for Var=//N can be
obtained from the formula above where all units belong to single cluster [C] = 1 and ne n.
A.3. Definition of Label Differential Privacy
We recall here formal definition of label differential privacy.
Definition A.1. (Label Differential Privacy) Consider a randomized mechanism dataset D and outputs into O. Let e, 8 E Rzo- A mechanism M is called (c, -abbel differentially private-or (c, -lllabel for any two datasets (D, D') that differ in the label (outcome) of a single example and any subset O C O we have DDM E O] S e (D') E O 8, where is the privacy budget and 8 the failure probability. If then M said to be e-label differentially private, e-label DP.
- O that takes as input a
Achieving label-differential privacy implies that the output of a mechanism does not change too much if single label in the input dataset is changed. The privacy loss controls the size of the possible change, and 8 is the failure probability in providing such a guarantee. In other words, (s, d)-iifferett 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 (e, ddddifferelt privacy property relaxes this constraint and states only that it is unlikely that the observed value (D) has much higher lower chance to be generated under dataset D compared to neighboring dataset D'. Differential privacy can also be viewed from statistical hypothesis testing framework, where an attacker aims to distinguish D from D' based on the output of the mechanism. This viewpoint has been put forward by (Wasserman & Zhou, 2010) and (Kairouz et al., 2015), who show that, by using the output of an (s, 8)-DP mechanism, the power of any test with significance level a E [0, is bounded by a + For small enough (s, 5), this bound is only slightly larger than a, and so any test which aims distinguishing D from D' is powerless.
A.4. Two aggregation- based baselines: description and guarantees.
The simplest approach to sharing a differentially private estimate of the average treatment effect for the central unit to compute some unbiased estimator based on the original responses yi and add noise the estimate before sharing
12

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
externally. We provide an example in Algorithm 3, written in the broadest generality when clustering is available. When no clustering is available,
simply assume that all units belong to the same cluster.
Algorithm 3 NOISY HORVITZ-THOMPSCN mechanism
Input: Individual responses y/1,-... Ua. (optional) cluster memberships c1...., Cn Output: Privatized estimate f
yi(1
24)
Return
we
we Laplace Ne).
(4)
11,ee
710ec
GEC
iEc
The variances of the noise parameters 7hc determine both the privacy guarantee e and additional estimator variance of the Noisy Horvitz-Thompee algorithm. To compute its privacy guarantee, we apply (Dwork et al. (2014), Theorem 3.6) and consider the sensitivity A. of the inner function c// - 1//nn../(1 - 21), defined as the maximum change its value when changing only one label in the data set. The variance of f can be expressed easily as a function of the variance of its non-differentialll--rie equivalent, the Horvitz-Thompson estimator without the Laplace noise:
No- ==
Σ
1c yi
y: zz)
(5)
n
11,
70.cc
GEC
iEc
Proposition A.2. The noisy Horvitz- Norvitz-Thompsonn estimator E-DP when setting de Aefe for every cluster, where A. min(nop Ro,cs R1,e]- maxyey y/- Furthermore, its variance with respect to the treatment assignment and the Laplace noise (DP) is given by
A E
VarDr,> Var (PN +
Σ eEC
where NNo-DP is the non-diffeenttialy--riin stratified Horvitz-Thompson estimator defined in Eq. 5, and [ax=<fNo-DP] is its variance with respect to the treatment assignment z.
Because these results hold for any clustering, they also hold when no clustering is available; in that case, consider all units to be part of the same cluster. We refer the reader to Appendix A.2 for the well-known closed-form expression of Varz(fNo-Dr)
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 written in the broadest generality when clustering is available.
Algorithm 4 NOISY HISTOGRAM mechanism
Input: Individual responses 1/,....,%. Va. (optional) cluster memberships C
Output: Privatized estimate i Compute the empirical distribution Pa (ylc) of treated (a = 1) and controlled (a = 0) units within cluster c.
nhe Σ
Return
:= CEC
x (pi (vlc) + Wi.ey po(ylc) wo.c.)) Wa.c.y ~ Lap.ace(nn.e..
(6)
BEY
Since the K bins corresponding to the K elements of y are disjoint, and the sensitivity of the value of each histogram bin n the central unit can share the histogram privately by adding independent draws from Lap 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 Korvitz-Thompoe counterpart.
13

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Proposition A.3. The noisy Histogram mechanism i is e-DP when setting 1la (#a for every cluster. Furthermore, its variance with respect to the treatment assignment z and the Laplace noise (DP) is given by
Varpp=
Varz [FN +
Σ NEY
Te
110,c
"1,e
CEC
where FNo-DP the non-diiferentially-rree private stratified Horvitz-Tommpan estimator defined in Eq. and Var, [FNoDD] its variance with respect to the treatment assignment
For the same privacy guarantee, the NOISY-HISTOGRAM mechanism, since ||y|| S ||y||2 and Rte, S min(no,,s ni,o) 2 max(no,. R1,e)
mechanism has smaller variance gap than the
No.c + ni,e. -2
proof of Propositions A.3 and A.2 can be found below in Appendix A.11.
A.5. The UNIFORM-PRIOK DP mechanism
Unlike the two prior mechanisms, the UNIFORM-PRIOR DP mechanism provides user-level outcomes. As formalized in Algorithm 1, it reports the true outcome with some probability, and otherwise reports an outcome sampled uniformly at random from the space of possible outcomes.
Our next result shows that the stratified estimator (I) is unbiased for the average treatment effect.
Proposition AA. The conditional expectation of the estimator fy, defined in Eq. (1), with respect the DP mechanism, equal the non-differentialy private Horvitz-T'oome Thhmmsso estimator: It is therefore unbiased for the average treatment effect over and the DP mechanism.
Enp[fx|z] = -No-DP and EDP,./AA]=7 =T
Having an unbiased estimator for causal inference an important but not entirely surprising result. fact, many differentially private mechanisms can recover true labels in expectation: (Kancharla Kang, 2021) also propose an unbiased differentially private estimator in the setting of binary potential outcomes ys {0, Instead, the main difficulty is to minimize the variance gap with non-differentially--riiae estimators. To state the variance of f under the UNIFORM-PRIOR-DD mechanism, we consider the following notation: y == 1/1l Evey y and y = 1/D0 EyEy y² over all possible outcomes. For a E {0, 1}. we also define Va == 1/1.. Eie (a) and va(a) = /n. Eie. vf(a) over the units of cluster c.
Theorem A.5. For any È > 0. the UNIFORM-PRIOR DP mechanism is (E, (),6)-labe DP when we set ó = max(0, 1 À + À )) In particular, it is e-label DP with e = log (1 (1- (LAAjK) Furthermore, the variance of estimator łx in (1) under the UNIFORM-PRIOR-DE mechanism and the treatment assignment is given by
n Σ
xy² X2y²
Varpe, Var= [NNo[[NNDD]]
Ro.c
T1.c
(1 A)2
OEC
n
(0)
(1)
2
(0)
(c(
(7)
n²
1 1-X
n0.cc
n1.c
A
7o.e
M1.
REC
As the sampling probability grows small - recover the non-private variance formula Varpp, + (ar_/fNo.DP) but the e-DP guarantee goes to infinity. Since the MMFFORM-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 (7) 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 fur by considering that all units belong to the same cluster:
U1
(1 - 2,)
(8)
X
n1
no
The following variance result is direct corollary of Theorem A.5.
14

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Corollary A.6. Under the UNIFORM-PRIOR-DE mechanism, the variance of the unstratifted estimator f"r defined in Eq. 8 given by
Xy² - y2
A
y
(1)
2Xy
y(0)
y(1)
TAu Var = Var,
No-DP)
Ti (1 X
1-
n0
T4
11g
+
n1
where Var, Io DD denotes the variance of its non-private equivalent & - DP Its differential privacy guarantees are the same those in Theorem A.5.
We refer the reader to Appendix A.2 for the well-known closed form formula of Varz (ar=(fNo-DPl The special case of the unstratified estimator f" in (8) for binary outcomes y = {0, }} was previously proposed by (Kancharla & Kang, 2021), I), in which case the variance of the estimator can be further simplified:
(1- 7o721 (1 A)2
Var [+ Var [ DPl +
(9)
The first two regregation-basee mechanisms in Section A.4 assumed that a trusted data curator (c.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-PRIE PRIEEM-PRROR--EE 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 local DP guarantee, defined by (Kasiviswanathan al., 201 which is stronger than a DP guarantee. That said, in motivating example, assuming the existence of trusted curator the technology company is more natural than putting the burden of privatizing responses each individual user.
A.6. Experiment 4. (Bias and Gaussianity)
We first verify that CLUSTER-DP estimator rip. given in Theorem 3.2, is unbiased and admits asymptotically Gaussian distribution by plotting the histogram and the qq-plot of f in Figures 3 and 4.
1.5
80
60
0.5
Quantiles of (f
0
40
-0.5
20
-1
-1.5
0
-4
-2
0
2
-1.5
-1
-0.5
0.5
1.5
Standard Normal Quantiles
Figure 3: histogram of
Figure 4: qq-plot of
A.7. Experiment 5. (Validation of theoretical bound)
In Theorem 3.5, we bounded the excess variance of the private estimator given in Theorem 3.2 compared the non- private estimator (5). The bound had two additive terms. The first one depends the cluster structure of data, namely the cluster homogeneity quantities do. Φ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- Var [ Var, [NNo-D]] empirically, by averaging over 500 different realizations 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 (, along with
mechanism. In Figure 5, we compute the gap
15

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
shaded region whose upper boundary corresponds to the upper bound given in Theorem 3.5 and its lower boundary corresponds to only the first term in that bound. We observe that the variance gap remains in the shaded which validates the theoretical upper bound given by Theorem 3.5, and shows that the derived bound is tight, up to the second term.
0.35
A 0.4
Var, (rx DPl
0.3
X 0.6
À 0.8
0.25
0.2
0.15
VarpPa [
0.1
0.05
0
1
2
3
4
5
Figure 5: The variance gap between the private estimator fq. given given in Theorem 3.2, and the non-private estimator -NO-DP in the setting of Experiment 5. The upper boundary of the shaded area corresponds to the upper bound derived in Theorem 3.5, and lower boundary corresponds to the the first term in that bound. As we see the gap remains between the two boundaries.
A.8. Experiment 6. (Comparisons with aggregation-based baselines)
2.5
Horvitz- Thompson+noise
noisy histogram
2
Cluster-DP
Conditional bias
1.5
0.5
0
0.5
1
1.5
2
E
Figure 6: Bias of the CLUSTER-DP. noisy Horvitz-Thooe Thompson and noisy histogram estimators under one shot communication between the central unit and the advertisers in the setting of Experiment 6.
We next compare the privacy-variance trade-off of the estimator based on the CLUSTER-DE mechanism with the other baselines discussed in Section 2 and Appendix A.4, namely the noisy Horvitz-Thonee Thommis- 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-sampe conditional bias than the other two baselines. To demonstrate this point, we fix the noise and randomization in each DP mechanisms for the super-populate populatioo and compute the bias of each estimator with respect to random draws from the super populatop and of the treatment assignments. Specifically we compute the expectation of the treatment effect estimator over 500 sub-pon sab-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 then computed as the difference between the expectation of the estimator and the true treatment effect. As we see in
16

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Figure 6, CLUSTER-DP estimator achieves lower conditional bias compared to the other two baselines, as vary the privacy loss e. The error bars obtained by considering 50 different realizations of the noise/randomizzation in the DP mechanisms.
A.9. Experiment 7. (Additional qq-plot for YouTube data experiment)
Figure 7 shows the qqplot of f with f being the CLUSTER-DP mechanism, using 500 realizations of the randomness in the outcomes and the DP mechanism, for the YouTube dataset described at the end of Section 4. As the plot demonstrates is an unbiased and Gaussian estimator.
Quantiles of Input Sample
0.5
-0.5
-1
-4
-2
0
2
4
Standard Normal Quantiles
Figure 7: qqplot of f T. with the CLUSTER-DP estimator using 500 realizations of randomness in the outcomes and the DP mechanism.
A.10. Fuller versions of Figures from Experiments 1-3
We include in Figure 8 on the next page fuller versions of the Figures from Experiments 1-3, included Section 4.
A.11. Proof of Proposition A.2 and A.3
We start by proving Proposition A.2. Recall the noisy Horvitz-Thompson estimator given by (4):
The n
y1(1
z4)
+ we we Laplace(ne)
11.
7a.cc
oEC
iEc
To show its privacy guarantee, we apply (Dwork al. (2014), Theorem 3.6). Consider the sensitivity A₂ of the inner function 1/ (1 z²). defined as the maximum change in its value when changing only label in the data private, keep them intact in computing the sensitivity. Therefore, changing only
set. Since the assignments label will change the inner function by at most A min min(Na,e: 11,c]-1 x max.ey ly]- By using (Dwork et al. (2014), Theorem 3.6), adding Laplace noise with parameter A./e will make each of the inner terms e e-DP and by the post- post-processing property (Dwork et al. (2014) 4), Proposition 2.1), is also eDP..
For the variance, recall the non-differentially--rieee Horvitz- Thommpsn estimator NN from (5), by which we can write
NO--DP
We-
GEC
17

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
2
2.5
uniiorrmppioo(uusttratiiie
1.8
uniform-priorteeeet uniioorm-pior((ttratiiedd)
2
cluster DP
cluster-free DP
1.6
Var (f)
1.5
Var(f)
1.4
uniform-prio((unstrafiiee] uniforr--rior((ttatiinne cluster DP cluster-free DP
1.2
0.8
0.2
0.4
0.6
0.8
0
0.5
1.5
2
K7
(a)
(b)
1.4
0.5
cluster
1
1.2
no-cluster DP
non-private stratified
0.9
Varfenar)
Vareaasee Paaae (eo)
0.8
Var(f)
0.8
0.6
0.7
0.4
0.6
0.2
0.5
0
2
3
4
1
1.5
2
2.5
3
3.5
3
(c)
(d)
Figure 8: (a) Variances of each mechanism vary the truncation level [0.1/K, in Experiment 1. The privacy
loss is fixed at 0.2 and 8 = 10-4, (b) Privacy-variance trade-off of each mechanism under the setting of Experiment
1. We fix the DP failure probability to 5 10-1, and optimize the choice of and y in the sets E {10, 20, oo) and E [0.01/K, 0.1/K, 1/x) ). (c) Ratio of the variance of the estimators under the CLUSTER-DP and CLUSTER FREE-DP mechanisms Experiment 2. The benefit of CLUSTER-DP mechanism stronger at larger 3 and smaller value of (d) Privacy-variance trade-ofi off of the CLUSTER- DP and CLUSTER FREE-DP stratified estimators for the YouTube dataset in Experiment The dotted line represents the variance of the non-private stratified estimator.
18

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Since we are drawn independently from each other and also independent from the assignments 2,, we have
Varpp, VarDP:x(FNoDDii
Σ
Var[we]
aEC
n
2
Warnp:=/fNo.Dp +
Σ
n
8
where the last step holds because we Laplace(ne) with Tlc Acfe.
We next proceed with proving Proposition A.3. Its privacy guarantee follows easily from the fact that (a(y)c has sensitivity i/na.e (histogram queries) and therefore adding independent draws from Laplace((na..e)) to the frequency of each value will make the histogram e-DP. To prove the claim on its variance, we note that the non-private Horvitz- Thooiiz-Thompson estimator can be written as
No- Σ
The Σ ypi(ule)
Σ Evvoculee)
GEC
DEY
DEY
Therefore, can write the noisy Histogram estimator (6)
The
((Pi(ylc) + W1.w Po(ylc) wo,c.,)
72
CEC
BEY
Noo DP
Σ Σ
The
y(wiey wo,cy).
eEC
yEY
Since Wa,cy are independent from each other and Wa,cy ~ Laplace(na.c). we get
Varpe,2 [+] (fNoo,,/fNO-De
No n2
v)
2 (Var(wi,e.)) Varlwo,ag))
GEC MEY
Var (NN +
Σ
v2
Σ CEC
The
2 (2m + 2%/
DEJ
VarDp=<(No-DDel
2
Σ y2
nre
2
62
11.c
2
n0.ec
VEY
CEC
This completes the proof of Proposition A.3.
A.12. Proof of Theorem A.5
DP mechanism is a special case of the CLUSTER- DP mechanism, we follow the proof of Theorem 3.5, 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 (26), which in the case that there no Laplace noise added, reads as
Because the UNIFORM-PRINE
Varpr(uo.c =oo.yy Poo.yTQQ-
T 100'ddaa((( ddaa(Qp))
Σ O0)
(10)
tEOD..
Note that we are using the lightened notation P to indicate the empirical distribution of outcomes of the controlled units in cluster c.
In the mechanism described by Algorithm 2, q is deta-dep and so correlated to p. In that case, we analyzed the first term via the decomposition diag(Qp) = diag(Qq) + diag @(p q)) and bounding q pll1. In the current case that q
the uniform distribution, this approach is not tight as || /ll would be large. However, since q (and therefore Q)
19

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering data-independent can directly analyze the first term as follows:
yJ Q (1 2)2
1
(1-
A
A
11
diag
(1-2)Ø+
A)p
1 (r
I
Kxl 111 111)
A
A
2A
yT (1 A)
diag(E)
diag(1)
18
11 y
K(1 X)2
K(1 2)
K² 2)2
Vū.c
Xy2
2Xy
2²8²
(1-X)
(1 - 1)2
(1 - X) y0.c
(1- A)2
Vo.e
Xy2 - x2
2X
yo.c
(11)
(1
A)
(1 A)2
(1 - X)
where we use the shorthand
v0( Vo.c no. tEDo.e
Σ y=(
yo.c
10.cc seOs.c
Using (1 in (10), we arrive
(1- + Ay 2212
yú,e
2A yo,c
Varpp(uu.dz,P)) P) = no.cc =no.c
n0,.y0,e
2
(1 X)2
(1 A)
1 X Vū.e + Xy² X28²
2xy
no.c
(1 A)2
(1 A) y0.c
Invoking (22), the above characterization yields the following:
Varp
n1
yo,c
Ví.e
2
yo&e
31.e
2
T0..c
111
(1 A)
110,c
11
CEC
n
1
1
xy²
X282
+
(12)
n
100.c
n1.c/
(1 - X)2
aEC
We next compute E, DF P)]. Since we are fixing na,e for each cluster, we have P(2; = a) a E {0, 13. We therefore have
Ra.e for i E O and
Eg ya.cl Ex
1
Σ 11 a))((a)
1 Σ vaaa) (.(a).
Na.c sEO.
The iEO.
Likewise we have Ex [v (a). Using this identities in (12), we obtain
E (a)r
n
A
y0
(1)
2
(0
Bo(l)
n
1
Bo.c
11,
(1 Aj
100cc
n1.6
CEC
n
X2y2
n?
11..c
n1..o
(1- 2)
cEC
We next recall (21):
Σ (S)(
S²(T(00)
S2((e)
Var,EEprflle P)]
nhe
n?
71,
No.c
ne
oEC
20

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
which is the variance of the typical estimator with no-differential-privaay and so was written as Var, (FrgDDNo-DP]- Finally, from the law of total variance, we have:
Var(f|no, n1, P) = Ez E Varpp no n1, P)] + Var= (f n1, P))
Ez Var 2, P)] + Var, EDP [F 2, P)]
Var=|fNo-DP]
+
Σ
1
Xy - 2222
100ec
11,00
LEC
X
(0)
y1)
2X
y0(0)
(c(l)
110ec
11.
(1 (1
110cc
11,
eEC
A.13. Proof of Theorem 3.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, 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 2.
We can think of M as composition of two mechanisms M1 and M2 with M(D) = M2(D, M2(D,M(()) where Mj (D) represents the mechanism that returns the noisy cluster label distribution q, and M2 q) represents the mechanism which uses q to re-sample the labels and use them to form the average treatment effect estimator f. By composition theorem for (s, 5)DD (see e.g. (Dwork al. (2014), Theorem B. if M1 is (e1, 6DP and M2 is (62, 62) then M (e1 + E2, 61 + dD..
After adding noise terms Wyee empirical distributions p c) and pi. (i.n(ylc). the dataset D is not accessed anymore. Furthermore, the empirical distributions have sensitivity 1/ng and the Laplace noise used in Mj is of scale a o/ng, /Te,, which imply that M1 is (1/a, O)-DP (see e.g. (Dwork et al. (2014), Theorem 3.6) for an argument).
For mechanism M2, note that it is a randomization per label mechanism (using perturbed distribution D. followed by post-processing (computing average treatment effect estimator). We next show that M2 is (E, 6)- Note that for all y e V, we have
P(u: y y y) A + Ag(v), P(ū: wlu + v) Aī(v)
Since P(ù: = y + y) is independent of y/ and P(; = yly/ + y) < Pū: = ylui = y), the only condition we need to verify is the following:
P(j+ uly. y) - e PT = ylı + v) 5
By substituting for the events probabilities, the above condition becomes
1 A + Ag(v) S Af +
By rearranging the terms, it can be rewritten as
1 - x))
Now recall that 8 = max 1 - A A1 - )) Hence, it is sufficient to show that
1 1 x (1 - ) < -1 -1-A+ - e²,
which by rearranging the terms reads as
0 A(7 - (1K7-7(w)i1 7(v)
which holds since E 0 and S q(y). To summarize, by applying composition theorem for (E, 8DDP, we obtain that M is (s', -abbel DP, with E' = 1/0 É
We next show that M is (s", -0)lbbel DP, with s" = 2/7 + a, which along with the previous result gives the claim of Theorem 3.1. Let Y1m be the random vector denoting the labels of the units. We need to show that for any two neighboring data sets D (yim: 21))) and D' (Nins z1mm) (where yıu and vi.. differ only in one entry) we have
((M E 0) s " ((M())))) E 60)+ +
(13)
21

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
for any set O )". Proof of this part requires more effort. Let WI:K be the random vector representing the noise values added to the set of possible labels in the data set. We then have
((M())))) 00)= Σ ((M())))) E O) yi:. Wi:K w1.K) P(WI:K w1:K),
WI:K
(14)
((
0) Σ (
Vi.n Wi:K w1.K) P(W1:K wi.k).
wirK
It suffices to show that for any value of Wi.K, we have
(( E O) = Fimi WEK = wiik)
(15)
S ((M(()))))) EO))Y -Vin Wi.K wi:k) + 6.
By multiplying both sides of the above equation with P(W1:K = wi:k), and summing over wi.K, and using that Ewix P(WI: = w1:K) = 1, we get the desired bound in (13).
Let q and 7' be empirical distributions the mechanism, as defined Algorithm 2. we continue by establishing a lemma on و| oo proven the next section.
Lemma A.7. For all y V (7(y) 7 (y) -
Define the shorthand R == M (y1:.) and R' == M (v(.n). In order to prove (15), it suffices to show that for all O1:.. E )"
we have
PRR = 01: Yum= = Vimi W1:K = wIKk) S E P(R'' = 01:n Vim = Viin WI.K = wi:k) + 6.
(16)
By the definition of the mechanism M we have
P(R = 01 Mm = Fimi WL.K w1.k) = P(R = 01m Min = Vl.n g(-))
n
= II
P(R: = o = yı: 7(-))
i=1
P(R' = O = Vin. WI.K = w1.k) = P(R = mmm Yinm = VL.. (()-)
n
I[ 1=1
P(R = = v.)
For case in presentation, we adopt the shorthand
A : = 0. = y, B
for 1...., Our next lemma bounds the event probability A, in terms of the event probability B, Proof of Lemma A.8 is deferred to Section A.13.
Lemma A.8. Let ē > O and define 5 = -1- x1=xx -64) <1. Without loss of generality suppose that the neighboring label sets yiu and vin differs in the first coordinate. We then have
2
A e
1+
Bi
+
(17)
m
2
A < B,
1+
for 2....,n.
(18)
mm
22

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
We now ready prove inequality (16). Using Lemma A.8, we write
= = 1m = Mi:n, Wi:K- w1:k) =
A
A min
1,
A
i=1
2=
2
min {
{1,
[1(1+
2 yn
n-1
e
1
B1 + 8
B
m
2
1+
B; +
I e 842/1
B,
e P(R 01ml 1mm /
Vini WIIK = wl.x) + 8.
where the second equality holds since A, S 1. for all i.
Proof of Lemma A.7
Recall the notation of Theorem 3.1. We consider two neighboring datasets D = (yim:: Z1m)) and D' = (Nim #1m)), where Vi: and Ví... differ only in one entry. Define the function Joy as follows:
71 x 7
fx) = max min
7 x
S 11
1, x>1
We consider (v) == (f(v) + wy) and ('(v) == (r( + wy), where ÿ and ý' respectively denote the empirical
distribution of 81:m and Vi.n and wy indicates the component of wi:k corresponding to label y. We wish to bound the difference between distributions q(y) and 7' (y)) defined in Algorithm 2, and recalled below:
Sy م
S
i(v) 4(v) +
d'(v) (v() +
A
En
Σy S
where A 111-,, (v) and A' 1, on A A/.
d' (3). To achieve this, we will need a bound on (g(x) q'(y)] and on a bound
Since f, is I-Lipschitz, we have for any E y
14(v) (1))) (57 wyy (1( + wwy) S -v()))"'v))) 5 _ n
where the last inequality holds because the datasets D and D' differ in only one label.
We now show that A A' S 1/n. Without loss of generality, we can assume that the neighboring label sets Vı.u and Vin differ in the first coordinate, with y1 f, 1/1 = E for e, l' E V. such that
p(() (L) + = p((') p' (c) 1 n n
It follows that
Σ ((v))= - Ed(r
(1((() + w2) + (+((())) + +we) 1-(5(()) + wt) f2(0'(e") wr)
1
-f-(8(( + we) + fr (8(()) 1 + we
= ('(() + + wt n
(e' + we)
n
1
1
f (((() +
w/
(1) wx)
n
n
23

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
where the second to last inequality holds since J- is non-decreasing function, and the last step follows from 1-Lippscitzzesss of J-- Likewise,
show A A' S 1/n in order obtain A A - 1/n.
With this, we next bound the difference between distributions ((v) and q' (y), defined above. Consider three different cases:
0, A 0. We have
Sw
S Ey Sy
(7(y) - ['(y)] - (a(y) - d'(3))+ +
A
Σy Cy
2
- (4(3) d'v6i + A - A S
The case of A < 0, >
0 can be handled similarly.
A, A' < 0. We have
A
((y) ((v) + (4(v) 7)
Ey (1(v') 7)
A
(v)) + (g(P) - 7) 1 A Ky
A
= (4(P) 7) + (4(3) 7)
Ky
1 1-Kg
= - (a(P) - 7) 1 - K
Therefore,
Ky
Ky
1- 1-K7
Id(v) - ((v) s (a(v) - 7)
+ +ld(v)) - qvv1l, 1 - A' KY
1 - A Ky 1 - A' Kg
(1 Kx) A
1 1- Kr
(g(x) - 7)
(1
A - Ky)(1 A' - Kx)
n1 N K
1 1 Ky
(g(v) - >) A 1
1- A' K
(1-A A - k-))
n
(a) 1 1- K
( ((v) - +1
nl - -'- - K
1- A Ky
(0) 2 1 1- 1-K K
2
<
n1 N K
(a) holds since A All < 1/n. (b) follows from the fact that, since q(v) 2 y for all y,
a(v) + (K 1)r S a(v) + Σ (00 = A
such that q(v) y 7 1-11-- A Ky.
A, A > 0. We have
A
((y) = 9(v) + (1 - q(v))
(1-(())
Σ Ey ((-(1)
a(00))
A
= =1 =1+(1- (1-9(t))
A + -
1-K
= =1 ((v))
A + K -1
24

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Therefore,
1 K
K
+g(0)) - - K - + K-
(1( - - S (1 ((1))
A K
A' +
K
JAV A
1
K -1 A' + K-1 K
$ (1 (w))
A + K -1
n
2 n
$ (1 ((1))
1) + - n K
n K
-1
Combining the above three cases together, we obtain our stated lemma.
Proof of Lemma A.8
We start by proving (17). Consider three different cases:
01 # y1, V/: In this case, have A = Aa((1)) , B1 = (01). Therefore, we can write
A1 $ (0)) + ^|la
7/1000
2X
S \o1( +
(1+
2
(1)(
n/y
2
Bi
1
117
1 + 2
S < Bi
+ 6,
my
where the second step follows from Lemma A.7, third step holds since y S (01), and the last step holds since é, So the claim (17) is proved in this case.
01 = y/ In this case, A = =1---- + Aā(01) ; = =1 We then have
A 1 X+ (o) - 7
< <1 X (01) x -- (o(o) n1
(19)
where we used Lemma A.7 along with the facts that (01) 2 7 and 0.
We next recall the definition := (1 - À + Ar(1 - e )) < 1. By a simple rearrangement of the terms and using that n' (o1) 2 y and غ > 0, we can verify the following,
1 1 X + (o. S é (o)) 55
(20)
Therefore, by combining equations (19) and (20), we get
2 A S e (1)) 8
2
d' (o)e) =c² =c=(1+ ny
Bi + +
my
which completes the proof of claim (17) in this case.
01 v In this case, A XQ((1), B1 = 1- - X + (01( The proof of claim (17) in this case follows readily from case 1, because A1 is the same as in there, while B3 is larger.
This concludes the proof of Claim 17. We next prove Claim 18. Note that for i - 2...., n., we have y; 1/-- Consider the following two cases:
o ys v/: In this case we have
A B, I- (o.)
1- Ao(o)
25

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering o # yi Since yi y/s we also have o, # V/. In this case, A1 Mioo)
B; X
By symmetry, we can assume 7(0x)= S (o:), without loss of generality, and therefore, the maximum value of the ratio 1 +
A1/ /B is achieved in the second case, for which we have A of (18).
110-v''l== 1 +
TTiss completes the proof my.
2
Bi ((a)
(((a))
A.14. Proof of Theorem 3.2
We would like to express the expectation [f n1). Recall that there are three sources of randomness:
the differential privacy mechanism DP: determines the Laplace noise w and the À probability of reporting the true outcome.
the randomized assignment z: determines which units get assigned to treatment and which units get assigned to control.
the super-population P: determines the potential outcomes as well as the cluster assignments.
For a given unit with (0), (1() c2) ~ P and 2 = a,
Epp
Σ
Q Quln W. .Tly' P,P Epp
ΣΣ T(ū = 1...e. z4 2, P
y'Ey
Y'EY yEY
EDP
I(ūe = y)Q [v',v] z, y'zi
y'Ey
vEy
(h)
Σ EEw
Σ DEV
Ex [U( = y)] 1// 2, P 2/
y'Ey
E
Σ DEY
Qa.z 1y, Vel 1= 13/ 1 2, P,P
8/ y'Ey
Ew [L(y b))1z,Ply's
E'
Σ VEY
1( v'1//24 =v(())
(a) holds since assignments is independent from (0). y/ (1), c; } (b) holds from the law of iterated expectation and the fact that there are two sources of randomness in the differential privacy mechanism: (A, w) with Qa,a independent of the Bernoulli >; (c) follows from the definition of Qe.a: Qa.a [y', yl = (1 A)I(y' = y) + Aqa (3 (3'(c) [c) and (d) follows from the fact that Qz,10. 'Q;; therefore, for any a, E [K].
1o. = In.b = I[a b).
Finally, (e) follows from the fact that w is independent from (0:(0), (i((), ci.. Similarly,
EDP
Σ Om.. 21) P.P v1( 21)
y'EY
As result, with no.e (resp. n1,c) the total number of controlled (resp. treated) units in cluster and n. n0,e + 11,60
Epp Epp[f|2, 2
Σ The
Σ (1)
24
Σ
(i) 1 Z
n
R1.
nuc
GEC
i=1
26

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
We recover the standard form of the difference-in--means estimator. From the law of iterated expectations, have
ED B2 (Dppf/=))11)) n1, Pl
A.15. Proof of Theorem 3.5
We would like to express the variance (f We begin by expressing the variance with respect to the first two, considering the third fixed. From the law of total variance, we have:
VarDp,= = E- [a no. n1. P)] + (arg/Ep no, n. P)]
Eg P (f22, Var, [EDp(f|z,P))
We bound the term Varpp(fiz,P) P) in separate proposition
Proposition A.9. For the average treatment effect estimator TQ given given in Theorem 3.2, we have
ΣΣ" (1-Xp= -1) S2 (Ta.c)
A(Ba.c)
parpp(f(z,
+
aaa
nhecc
[ cEC
where Va.. = (ui(a)) Oa,eh and
A(x) 2KB2
(AvK + 1)² (1- +2) +
3
A(K 1)7) (1 A)2 11yl 111111(K
1++
-f 2 re-a//o - (e-na/o-e-t - x
We now take its expectation with respect to We assume that, for each cluster there is fixed number of units (n1,e) assigned to treatment and a fixed number of units (no,e) assigned to control, regardless of the cluster assignment. We compute the expectation with Ez [N)))),
(Na.e 1) [Sa (Wa.c)]
E2
(n((a) - [(ui(a)iioo..
iE0a.c
27
Eg
Σ (a) naee
Σ Vi(a)
Nase SEOo.o
iEO...
(11 Thec iEO.
27
Σ P (2; = (a) - nE,
Σ I(2, = a)yi(a) II(es-aas(aa)
=
IE0
nacc (a)
1
P(4 a, a) yi (a)
The
Na.o iEO, JEO.
iEO.
Σ iEO.
Na,c Vc (a)
1
Σ
P (( a) (a)
P a, = a) (a)
no
Na.c ig0.
Na. jæiEO.
Ba,c (a)
1
Σ
(a(a)=
Ba, - 1)
na(ne - 1) (a)
Th
na.c jæiEo.
1E0
IEO,
27

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Adding and subtracting (a(
Ra.o-1 Eiso, (a), get:
(na,e - 1) (5
2
= Σ
nac u/ v/((a)
1 Σ
(a) + no.c Σ va((a)
na.c 1
Σ
vi(a)
The
The iEO.
ne (n 1) SEC,
ne( 1)
iEO,
1ED0
Na.cc
+ Ba.c
Σ
y (a) (na.e - 1) n
Σ Vi(a)
=
ao - 1)
Re
Ne
iED2
iED
Na. -
Σ va(aa) - -(na,e - 1)
Σ (i(a)
Tee 1E0.
1
The IED
(Na,c - 1)52(
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 3.2, we have:
Epr Ep
Σ The Σ (1(
24
(c(
1 Zz
101.c
eEC
As result, the second term is given by the usual formula for the variance of the stratified estimator:
2
(T)((1
S²(T((0)
(FeeF
Var, (Dr,
(21)
11.
710
Tee
EEC
where, for any vector of length n, (2) n Ei=1
(u: 1) and Din u. Recall that F. (v:
y:(0) (o))) = (1) (0). Since this is the variance of the typical estimator with no-differential- prrivattillppiivcc.... we write this term:
Var=[EDP(ff 22 (ar=DfNo-DP]
As result, we obtain
Varpr,=(flmo.e n1,e; P)
I Varz [No-DP]
Σ
(
(1 (1- A)2 -1)
1
5 (T)((a)
A(na,e
n
naee
nae
aE(0.1) CEC
(a1 \12 -1)
n S2 (a))
mee A(na,e)
Var /No
Σ
Σ
n² nhecc
n12 na,
aE aE(0,11 eEc
aE(0,1) eEC
which we can rewrite as:
Varpp=(F)nooes nic, P) S [No-DDN + (a-XP 1)² -1)
Σ
P + Σ
A A(Da.)
naecc
aE(0,1)
aE(0,1) CEC
where we have defined
n
S (Je(a))
δa =
2 0
n12
Na.c
OEC
Proof of Proposition A.9
We seek to compute Varpp(Fl2,7) P). We can rewrite f as
f Σ
Wa,c
na,
cEC
oE (0,1)
28

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
where Oa,- (i E [m] : = C, = a} and Me.c := Eieo... Eyey Qz,aaly (v', Mely'. Since () are i.i.d across units, and the DP mechanism is applied each clusters separately, such that the privatized outcomes yi independent across clusters, we have that W0.. and W1,0 are independent across clusters.
VarDr(f|z,
Σ Σ
n n oEC
Varpp(Haclz,P)
(22)
na.c
aE(u,1}
We proceed by calculating Varpr(uo.el3) P). The computation for (arpr(u P) is identical.
COMPUTING P))
We have
[,0 [ P] We begin by computing Epr (tor/u,./2z, PJ. Fixing cluster c, lighten the notation by using the shorthand Qe.n- Qu,b Qc,ola, b), Q Q la, 6). and Q (Q- Finally, recall that y (v)yey is the set of possible outcomes arranged into a vector with the same ordering as the columns of Q, and eg E Kx is the vector with I at the f-th position and zero everywhere else. Writing in matrix form, we have
Varpr(uo,dl z, P) = Epr
EErp P P|2
Σ Y
iE
Let y. y. z, be the vectors of variables Tt. yis Zús (w)y, respectively, We then have
Epp(ub,elz P| =
Σ
EDP
Q .00
Z
iEDo.c
Σ
EDP
Σ Q Ui) P
iE
KEY
EDP
QQ II1 = i.) z,P
iEDo.e
KEY
Following similar steps to the proof of Theorem 3.2, we have
EpP [ [[[ = Øi:) Pl
= Ew [ Ex [I(L 0:)) 20| 2, = EEw [T.
Q1.0 x.Pp
= Ies
follows
Ep Σ TTe Σ vi(().
(23)
iECo.e
tEDu.
We next calculate E[ Eiu3.o 1, Pl.
EDP [10,ll2, (0, P]
Σ
Edp y
Q (Q (. (
.i5
ijEEO..
Σ
Σ
-O]((' -ū;) 2,
i.jEO..c
LPEY
Σ B
Σ
--1 E [I(L T.)1((( = [5)1[o] P y
ijEEo.c
WeE
Σ iEDo
y Enp
(Q,H)
Qi. 2, 2,Pyy
REY
y E'E.
Σ
z,P
(24)
(fJEOo.c
29

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
For the first term, write
1 = 1 deag
(25)
KEY
tE
Let p ( E k be the empirical distributions of outcomes of the controlled units in cluster arranged into a K K-dimensional vector, such that Pe m Ki E Oo V/s = E In vector form,
p
Cz
no,c iEDo.e
Taking the expectation of both sides in (25) and summing over E Op,s we get
Σ
Ew
Qu.v.
2, P
= EE
diag
Q
Σ
Cy Q-
2, P
iEOo.c
1E0o.
Eww
Q
diag( (na,c
QP)QPPQQQ11 2, 2
[
1o--diin diag diag(Qii)Q 2
We next proceed with the second term on the right-hand side of (24). We have
Σ Q.2 Qu. Qu =
(Qen,) (Qey)) (ew
trEy
trey
Σ
Qell(Qe, )e (Qex))00)
trey
E Qee c. I Q²) 00,
tPe
=Q
I QQQ Cgg Cy
Taking the expectation of both sides of the above equation, we arrive at
Σ LeEY
2, y = En [yTe, Cvy 212, P]
y: (O),
where the second equality holds since + j Oo.c- Putting these pieces together, obtain
Enw EDPlu 2, = T ( "'diia(Q(0)) (QD)Q- 2
Σ
(1(0),,(0),
which along with (23) gives us
VarDP(uo.cl2: P)
Epplyu P EDDPLu..12,77
2
-no,cy Egp (Q-adiag(PP)))) P + Σ (0(0),;(0)
Σ
vx(0))
iFjEO... 0,0
iEDo.e
-o,cy To Q (diag(())Q-T)))
Eup
Σ
(0)
(26)
iEO..e
30

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
DECOMPOSING (a P)
We wish to bound Var(uo.e| P). We begin by decomposing into two distinct terms. Let = [oo(v/c))we> gxx1 be the distribution constructed in the DP mechanism after adding noise to the empirical distribution p, truncation, and normalization. We consider the following decomposition:
7 diag QD)Q-* diaa d=daa(QQ)Q QQ
+Q Q "
Plugging into (26),
(wo,p(u
y Enw diag((QQ)))) PI +y +y"Enn Ew "i - Q))Q-((= 1
Σ iEDO,
22(0).
no,e
term
temm
BOUNDING TERM I
By definition, we can write Q as Q = (1 X) + Aq1", with 1 E Rxxt indicating the all-one vector. Furthermore, 1 I'q q = 1 because q is probability distribution (Esfandiari et al. (2022), Theorem 6). Using the Sherman-Morison formula, we obtain
Q'' -' I -'=-----
- q1
1-x
(27)
Plugging for Q and Q-1, 11 we have the following chain of identities:
Qq = A) + Aº - q
diag (Qq) 1
X
diag( q)
1 9q
A
Xa 2A
l didga((uu (Q7)Q =
(1 X) 2 diag(q) +
(1 X)2 94
Using the last identity, we have
Ew Q diag(Q9) 1 Ply
X2 2X
(1 2)2 y Ew [diag(ğ)] y +
Ew [qq]] "y
(1 - x)2
27
X2 End
Em (7y 2 +
Σ vuu DEY
(1 2)2
(1 x)2
DEy
1
(
Em
Baly%(0) +
EEg (0)]² 2, p
(1 X)2
(1 - x)2
1
Exp
Egly? (0))
Ry Eq(v)(0))3) + Eglux (0)) 2,
(28)
(1 ))2
which can also be written as:
y EE [Q "digg T2, (1 2)
1
(o (vx P)²) + (v.)),v((0)2,, P)2
In the following lemma, we relate the expectation of outcomes with respect their expectation with respect p. Lemma A.10. If outcomes bounded by B,
Eq a (0) Pl < B² l| pll1 + na.c tEOv.e
Σ 20)
Eg. N (0))z 2| 2
Σ
31(
2BB Exo l| -ll1.
n0.e veOb.o
31

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering Using the above lemma, obtain:
y' T EE |.
1
B 11 - 1111 +
Σ
3i(0)
(1 - X)2
no,o iECo.
1
Σ
vi(0)
-2B EnD
1 1111
(1 2)2
100ec seCo.s
which can be simplified to
Ew [Q
(QQ)
z, P|
Σ vi(0) )
y:(0)²
- X\2
no,cc igCo,e
n0.cc iEDo..
2
1 Σ (0)
3
+ BB²
B
+ +2)Eu 11 -1ll1
n0ee iEDo.
(1 A1-
10.c
2 [c((0)
B²
(1-1)² A)2 + +2) Ew lll +2)Bu
pl11]
(29)
1o.c
(1 (1- Aj2
where (z)
ক- Eocgla a)² and 7 1 Eacga.
[
BOUNDING TERM II
We begin with the two inequalities
-dag((0
10- g < 111111121 - -
(30)
where [Q) maxi,j |Qiyl- For every & E qr 2 7 (Esfandiari et al. (2022), Theorem 6), and Eiey qt 1, which implies that vf V.g I 1 (K 1)y. Therefore, by definition of Q, we have
10/ S A+ A(1 (K 1)>) = A(K--AKK 117-
The following lemma bounds the maximum singular value of matrix Q.
Lemma A.11. The maximum singular value of label randomization matrix Q-! is at most AVK+1
1-X
Using Lemma A.11, get
(AVK + +12
yT diag(QQi
(1 -1= Ily1| A(K - 11) ğ
(31)
32

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
BOUNDING Var( c)
Combining (29) and (31) with the expression of Var(uo, 2), we get
VarDr(uo,cl2; P)
y En [Q- diag(Qq)Q y'
Ex [Q- - |z,
Σ v²(
Ro.
iEDo..
lern
term 11
(Jo,c) + no.e (00,c)² + B²
3
< (no.c - 1) (1 2)2
+2)E Ew
+ +2
- -llq-pllal
(1- 1)2
(AvK + 1)2
- (1-1)2 [1y1|311- -INKK11KKK--- A(K-1)7)el 11 -qll1) Σ (0)
iEDo.e
10..c
5² (3((0,.) + -oo,c(o.cc
Σ
(0) + no, A Eawl l1 p111
- 1)2
iEDs.c
1 (1--)=-11 -1) S (Jo,r) Ap 11 p(l1).
(no.e 1)
(32)
with
No.o = B² (1- (1- +2 + (AVK + 1)²
(
(1 - ^\2 11y1 - -
The final step is bounding the term EE, 1-111111111
Lemma A.12. Recall the notation q (rioyylc)l and p p= (po(vlc)). Then,
E q - p111 - 2K (++ a
(e-moollo -ooofo))) ]
nu.c
By using Lemma A.12 in (32), we obtain
Varpr(uo,dl;P)) (no.c -1) ( (1- 1) (² A(,0,))
(33)
with
y+ o (c-ra// -e-//))))/)) [
A(x) = 2b,
1
= 2K
B²
(1 - x)z +2) + (AVK + +12
(1- X)2 11y1 - A(K (1)-)))))
1 σ ( - - x
similar bound can be derived for Var(u c), which in conjunction with (22) gives the desired result.
Proof of Lemma A.10
We recall the statement of Lemma A.10 below for convenience.
Eg ~ 1y? (0)] P]
B l P1l1 no.c teCo..
Σ (0)
(34)
F.g. n (0)=,) P| N
Σ vn(0))
2B2R F. l| -pl11
(35)
Na.e veOb.e
33

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Proof. Since the outcomes bounded by B, have
E w (0) P] Eply = Ew
Σ yEy
y (gg - -Da) -Ba) z
I Ew
s (Āu - -.0) P
S B B Swlll - -011
PEY
Therefore,
B w (0)]],, P] < (0)1 P) + B² -2l11
We next note that This completes the proof of (34). Likewise we have
T(y = v) 8² P z
=0 E
Σ Σ
Σ
y:(0))
=
noccc
na.e iEOo.e
VED iEOo.e
g w l (0)) Eply)
Eg [0) - Ep (000
Eg [v)] + Eplu
2B Eg an [y:(0)] - 1p (0)]
s 2 l p11
Therefore, obtain:
B [22(0)]z P] [0)) 2B 1pl1-
We next note that
2
2 yc(0)
[1 v)
E0]
Σ
710cc
no.c keOo.e
VEViEoO.
This completes the proof of (35).
Proof of Lemma A.11
Lemma A.11.
The maximum singular value of label randomization matrix Q is most AVR+1 1-X
Proof. For any unit norm vector u we have
TT-
u
u
9ı
1-
Therefore, by triangle inequality
1+
1| TT-QQ
|1
|||||
1
1-X
where in the last step we used ||u||| and |
<
1.
34

---

Improving the Variance of Differentially Private Randomized Experiments through Clustering
Proof of Lemma A.12
Lemma A.12. Recall the notation q [ño(y|<)lvE> and p [0 (y/e)), where we dropped the subscript lighten the notation. Then,
E q p|l1] - 2K ( + a
(e-Mooelo - c )=
nu.c
We follow the proof of (Esfandiari et al. (2022), Lemma 5). By tighter derivation which carries in straightforward way, we obtain the following bound analogous to Equation (6) therein:
Eu mmxx(y, min(1, (,y. = 2KE mmxx(y, min(1, V)) Bw q p111] S Σ
DEy
where V |uy,a| Exp(no,e/o)) since Wyee Laplace(a/ (n/o)))) For random variable V Exp(a:), we have
J( yar av dv +
L" uae
fo ar aa de
E[max(7, min(1,
vae-aydu
ye avv - (v
)e-av - 10
)e
a
7
(e - - e-
which after substituting for u n gives the claim.
You can have much text here as you want. The main body must be at most 8 pages long, For the final version, one more page can be added. If you want, you can use an appendix like this one.
The onecolumn command above can be kept in place if you prefer a one-column appendix, or can be removed if you prefer two-column appendix. Apart from this possible change, the style (font size, spacing, margins, page numbering, etc.) should be kept the same the main body.
35


Reviews:
[{"review_id": "jeENZ9S3Ap", "reviewer": "Reviewer_giHc", "summary": "The paper proposes CLUSTER-DP, a differentially private mechanism aimed at improving the variance of causal effect estimation in randomized experiments by utilizing clustering structures within data. Traditional differential privacy (DP) approaches introduce noise to protect privacy, resulting in increased estimator variance. To improve this privacy-variance trade-off, the authors introduce clustering to guide noise addition, defining a new measure of \"cluster quality\" (cluster homogeneity) that quantifies intra-cluster variability of outcomes. They prove that leveraging high-quality clusters (more homogeneous groups) substantially reduces variance penalties compared to unclustered or uniform-prior baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to read our paper and for their thoughtful comments. We would be happy to include clarifications of the points below in a camera-ready version.\n\n*Correlation between non-sensitive and private data:* \n\nIt seems that your comment is about the measure of differential privacy and its limitations. We would like to highlight a few points:\n- There is a discussion about this in chapter 1 (The Promise of Differential Privacy) of [1] with an example about a medical study that teaches smoking may be correlated to cancer. Does this study compromise the smoker’s privacy? While the study reveals more information, under differential privacy this information is not deemed to be ‘leaked’. The rationale is that the impact on the smoker is the _same regardless of whether or not he was in the study_. It is the _conclusions reached_ in the study that affect the smoker, not his presence or absence in the data set. In other words, DP focuses on the privacy loss to an individual by her contribution to a dataset and therefore “by design” does not capture all of the privacy losses from correlations.\n- The notion of “inferential privacy” aims to consider privacy leakage due to correlation among individuals (it is identical to DP when individuals’ data are independent). So it is not addressing the case of correlation between sensitive and non-sensitive “features”, rather correlation between “individuals/samples”. \n- In our setting, the features $x_i$ are only used to form the clusters and then both the mechanism and analysis work with responses $y_i$ and cluster memberships $c_i$. Our analysis is under a finite sample setting, but extending it to its super-population equivalent assumes data $(y_i,c_i)$ are i.i.d, but conditional distribution $p(y|c)$ would be different (think of it as users are assigned to clusters independently according to some distribution and the marginal distribution of responses is a mixture distribution.) Notably, the responses $y_i$ are independent and so we don’t think inferential privacy would handle this, as it pertains to settings with correlation among samples.\n- The concern about the correlation between y (response) and c (cluster) is exactly the situation with label DP (where labels are deemed private while features are non-sensitive) and semi-sensitive features [2,3], which we discussed in the paper. Furthermore, in Remark 2.1, we argue that using the composition property of DP, we can extend our work to settings where both clusters and responses are sensitive. This “full DP” setting will also address the privacy leakage from correlations.   \n\nWe would be happy to add a discussion around these points in the revision.\n\n_[1]: “The Algorithmic Foundations of Differential Privacy”, Cynthia Dwork, Aaron Roth_\n\n_[2]: “Training Differentially private Ad prediction models with semi-sensitive features”, L. Chua et. al_\n\n_[3] “Anonymous learning via look-alike clustering”, A. Javanmard et. al_\n\n*Response to Questions:*\n\n- Please see our response above (third bullet point).  Considering the super-population regime, the correlation between clusters and responses is captured in the conditional distribution $p(y|c)$. We do not make any specific assumptions on it (which speaks to the generality of our framework) but it shows up in _Cluster homogeneity_ (Def 3.3). As discussed below the definition in population regime, $\\phi_a = E[Var(y(a|c))]$. \n- Note that $\\gamma$ is the truncation parameter (algorithm 1), so that $\\tilde{q}_a(y|c)\\ge \\gamma$. This is the distribution used for randomization, and so $\\frac{\\tilde{q}_a(y|c)}{\\tilde{q}_a(y’|c)} \\le \\frac{1}{\\gamma}$. This ratio is at the heart of DP analysis as it concerns the change of outcome distribution by replacing one user. As $K$ (# of possible outcomes) increases, it forces a bound on $\\gamma$, which makes this ratio to grow, leading to larger $\\epsilon$. A more high-level intuition is that when $K$ is small, an observed randomized response could be allocated to a larger fraction of users (fixing all other params) and so reidentification risk will be smaller.", "claims_and_evidence": "In the motivating application on online advertising, the authors claim that the non-sensitive cluster information can be shared and utilized to improve the mechanism's privacy-variance trade-off. However, this is only correct when the non-sensitive information has no correlation to the private data. Although the DP guarantee (values of \\epsilon, \\delta) might not change if correlation exists, the privacy is still comprised as the attack can infer the private information through the released clusters. This privacy risk has been quantified and analyzed by inferential privacy [1] and its follow-ups (e.g., [2-4]). The author should discuss this.\n\n[1] Ghosh, Arpita, and Robert Kleinberg. \"Inferential privacy guarantees for differentially private mechanisms.\" arXiv preprint arXiv:1603.01508 (2016).\n\n[2] Song, Shuang, Yizhen Wang, and Kamalika Chaudhuri. \"Pufferfish privacy mechanisms for correlated data.\" Proceedings of the 2017 ACM International Conference on Management of Data. 2017.\n\n[3] Zhang, Wanrong, Olga Ohrimenko, and Rachel Cummings. \"Attribute privacy: Framework and mechanisms.\" Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency. 2022.\n\n[4] Wang, Shuaiqi, et al. \"Inferentially-Private Private Information.\" arXiv preprint arXiv:2410.17095 (2024).", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proofs seem correct.", "experimental_designs_or_analyses": "Experiments make sense", "relation_to_broader_scientific_literature": "The paper is related to previous DP literatures", "essential_references_not_discussed": "See 'Claims And Evidence'", "other_strengths_and_weaknesses": "Strengths:\n- The paper is well-organized and easy to follow\n- Problem formulation and theoretical analysis are solid\n- Numerical experiments are conduct\n\nPlease see 'Claims And Evidence' for main weakness", "other_comments_or_suggestions": "NA", "questions_for_authors": "- Does the paper assume there is no correlation between the private and non-sensitive information? If not, how to model this correlation?\n- In Thm 3.1, $\\epsilon$ is related to $1/\\gamma$, where $\\gamma\\leq 1/K$. Can the authors provide intuitions on why $\\epsilon$ increases with $K$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "URR0JbZKFA", "reviewer": "Reviewer_LKUF", "summary": "This paper introduces Clustered-DP, a differentially private mechanism designed to improve the privacy-variance trade-off in randomized experiments. The proposed method improves the variance-precision trade-off compared to the traditional method, which introduces noise to the sensitive variables.\nThe paper provides theoretical privacy guarantees under label differential privacy and derives bounds on the variance of the causal effect estimator.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and overall positive review. We address below their two questions:\n\n_Q1._ \n\nThese derivations aim to establish the differential privacy guarantee of a mechanism $M_2$ which resamples labels at random with probability $\\lambda$ from the true distribution or a perturbed distribution $\\tilde q$. \n\nL. 1170 states the probabilities that the “privatized” outcome $\\tilde y$ is equal to a given potential outcome y. If y is the true potential outcome, then either it was sampled directly with probability (1-lambda) or it was sampled from $\\tilde q$ with probability $\\lambda$. Similarly, if $y$ is NOT the true potential outcome, then it must have been sampled from $\\tilde q$ with probability $\\lambda$.\n\nL. 1171-1173 identifies the necessary and sufficient conditions for proving that the mechanism $M_2$ is (\\epsilon, \\delta)-DP.\n\nWe now detail the steps made on L. 1174-1177  in further detail, starting with substituting the event probabilities identified on L. 1170.\n\nStep 1 (substituting event probabilities): $1 - \\lambda + \\lambda \\tilde q(y) \\leq e^{\\tilde \\epsilon} (\\lambda \\tilde q(y)) + \\delta$\n\nStep 2 (rearranging terms): $1 - \\lambda + \\lambda \\tilde q(y) ( 1- e^{\\tilde \\epsilon)) \\leq \\delta$\n\nBy the definition of $\\delta := \\max(0, 1 -\\lambda + \\lambda \\gamma ( 1- e^{\\tilde \\epsilon}))$, this condition is equivalent to showing two inequalities: \n\n(a) $1 - \\lambda + \\lambda \\tilde q(y) ( 1- e^{\\tilde \\epsilon}) \\leq 0$ and  \n\n(b) $1 - \\lambda + \\lambda \\tilde q(y) ( 1- e^{\\tilde \\epsilon}) \\leq 1 -\\lambda + \\lambda \\gamma ( 1- e^{\\tilde \\epsilon})$\n\n(b) always holds because $\\tilde q(y) \\geq \\gamma$ and $1- e^{\\tilde \\epsilon} \\leq 0$ since $\\tilde \\epsilon \\geq 0$. \n\nTherefore the initial condition on L. 1171 is equivalent to inequality (a), which can be rearranged to the form see on L. 1177: $0 \\leq \\lambda (\\gamma - \\tilde q(y)) ( 1 - \\tilde \\epsilon)$\n\n_Q2._ \n\nWe enforce the property that $\\tilde q_a(y|c)$ as an initial step of Algorithm 1. This is necessary to obtain the differential privacy guarantee in Theorem 3.1. The intuition is as follows: if for a given cluster $c$, treatment assignment $a$, and potential outcome $y$, we have  $\\tilde q_a(y|c) = 0$, then observing $y$ as a “privatized” output for that cluster and treatment assignment would mean that $y$ was equal to the original non-privatized outcome of individual $i$. This would be a violation of the differential privacy principle which aims to provide plausible deniability to individuals: seeing the output shouldn't allow you to be certain about any single individual's data.\n\nWe thank the reviewer for their patience with what is admittedly a notational-heavy subject. We would be happy to include these clarifications in a camera-ready version.", "claims_and_evidence": "One of the paper's key contributions is that the proposed Cluster-DP approach improves the privacy-variance trade-off. Theorems 3.1 and 3.4 provide the theoretical guarantee of privacy and variance, respectively. In section 4, both simulated and real-world data are used to demonstrate that CLUSTER-DP achieves lower variance compared to baseline methods while preserving privacy guarantees.", "methods_and_evaluation_criteria": "The CLUSTER-DP algorithm is well-designed to balance privacy and variance, leveraging non-sensitive cluster structures. The experiments show the comparisons to the baseline methods such as uniform-prior-dp.  The evaluation criteria show the privacy-variance trade-off, which is the main focus of the paper.", "theoretical_claims": "I checked the proof of Theorem 3.1 and didn't spot any errors or issues in the arguments. I didn't look at the results that are used in the references, and there are some derivations I didn't understand.", "experimental_designs_or_analyses": "The paper uses both synthetic and real-world datasets to evaluate performance and demonstrate the proposed method's generalizability. I checked experiments with numerical and real-world data. I think the results and analyses reflect the paper's key contribution.", "relation_to_broader_scientific_literature": "The paper is closely related to prior work on differential privacy and causal inference. It expands on existing methods by introducing clustering-based variance reduction.", "essential_references_not_discussed": "I'm not aware of essential references that have not been discussed.", "other_strengths_and_weaknesses": "- The paper is overall well-written, with clear motivation and rigorous derivations to the main results.\n\n- The proposed method is demonstrated with both synthetic and real-world datasets.\n\n- Although the choice of truncation parameter is discussed in the experiment section, it seems unclear how to choose the parameter in general.", "other_comments_or_suggestions": "(Please see the question below.)", "questions_for_authors": "- Could you give some more detail about the derivation from l.1169 to l.1177?\n\n- Could you provide some intuition about the property $\\tilde{q}_a(y|c) \\geq \\gamma$ ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uhfTKH8isI", "reviewer": "Reviewer_iSPq", "summary": "Authors give an algorithm they call Cluster-DP, which is a pure/approximate DP mechanism (label DP) for causal effect estimation. Its main insight is that you can reduce the variance of the estimates by leveraging known clustering structure in the data. At a high level, they add Laplace noise to the empirical response distributions within each cluster, do some clever truncation and renormalization, and get a data-dependent response distribution. They construct a response randomization matrix (again, novelty) and then use its inverse to debias the privatized outcomes, estimating average treatment effects. The main contributions are theoretical guarantees for the algorithm (label differential privacy guarantees and a detailed bound on the estimator’s variance gap relative to a non-private baseline). Their analysis carefully shows how improved cluster homogeneity leads to reduced variance, thereby achieving a better privacy-variance trade-off. They have some empirical evaluations on both synthetic and real data which show the usefulness of their approach in low-epsilon regimes, which is unsurprising following the bounds they give, but good validation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and positive review of our paper. We would be happy to clean up the notational remarks made by the reviewer, and clarify the points below in a camera-ready version. We now address their questions:\n\n_Q1._ \n\nIn our proof of Theorem 3.1, we use the composition theorem of differential privacy. In general, if mechanisms Mi are $(\\epsilon_i,\\delta_i)$- DP, then the composition satisfies $(\\sum_i \\epsilon_i, \\sum_i \\delta_i)$ DP. We use these results with $M_1$ the Laplace mechanism and $M_2$ the re-sampling process. If we do not allow any slack in the failure probability $\\delta$, then this cannot be tightened, i.e., one can find examples of mechanisms which violate $(\\epsilon, \\sum_i \\delta_i)$ DP if $\\epsilon< \\sum_i \\epsilon_i$; see [1]. But as shown in [1] if we allow for a larger value of $\\delta$, one can improve the privacy in terms of $\\epsilon$. This tightness is for general mechanisms. For the specific composition of Laplace mechanism and resampling, there may be some tighter bounds, but an analysis based on the composition property (as is our argument) cannot be tightened. Given that, we do not anticipate the bound to be excessively conservative, if conservative at all.\n\n[1] “The Composition Theorem for Differential Privacy”, Peter Kairouz et al, 203. \n\n\n_Q2._ \n\nThis is a good question. The matrix $Q_{c,a}$ is a scalar of the identity matrix plus a low rank matrix. As shown in the supplementary material (lines 1698-1704), its inverse is also a rank one perturbation of the (scaled) identity matrix. In Lemma A.11 we bound the maximum eigenvalue of $Q^{-1}$, which is the inverse of the minimum eigenvalue of $Q$. Using this lemma, the minimum eigenvalue of $Q^{-1}$ is at least $(1-\\lambda)/(\\lambda\\sqrt{K}+1)$. So the matrix is well-conditioned if $\\lambda$ (probability of resampling in the DP mechanism) is strictly less than 1, which is the case in our algorithm (by choosing $\\sigma< \\epsilon$ in privacy bound Thm 3.1). \nThis is also reflected in the variance bound, Thm 3.4, where $(1-\\lambda)^2$ appears in the denominator. \n \n_Q3._ \n\nThank you for raising this question. Our privacy guarantees are entirely robust to the chosen clusters! The statements of Theorem 3.1 and its corollaries do not depend on the cluster structure and properties; only the variance gap established in Theorem 3.4 depends on the cardinalities and homogeneity of clusters. In practice, clusters being more heterogeneous than assumed would show up as increased variance, which is measurable, but this would not endanger the integrity of the privacy claims. We do empirically evaluate the role of clustering quality in Experiment 2 and shown in Figure 1.c by varying beta which directly controls the cluster homogeneity (larger beta corresponding to more homogeneous clusters). As expected the performance of our results (in terms of variance gains over the Cluster-Free algorithm) improves at larger betas, and smaller lambdas (the resampling probability).\n\n_Q4._ \n\nAbsolutely. This is a great point, and definitely an exciting research direction for future work. As you noted, we propose binning as a solution, and implement it in the Numerical Experiments of Section 4, for both the fully synthetic and semi-synthetic data. We find the results satisfactory despite no particular tuning for the bin number and sizes. Using an adaptive grid is a natural approach to examine, which could yield further gains in the resulting privacy-variance tradeoff. Some immediate issues that practitioners should watch out for are 1) our guarantees depend on the number of bins K, hence one cannot choose an infinite number of bins, and 2) a data-adaptive choice of bin sizes requires access to the dataset which could leak information about the users’ data. This requires calibrating the noise level to ensure the privacy guarantee is maintained.", "claims_and_evidence": "Overall, I found that the authors made some novel and well-motivated claims, and managed to provide ample evidence (mainly theoretical) to support their Cluster-DP algorithm. The detailed derivations in the appendix were appreciated. They also have some empirical performance claims, which are less substantial but adequately validate their theory in my opinion.\n\nAs my review is mainly positive, I leave most of it as questions for the authors, to help clarify their work and its presentation.\n\nI'd like to highlight that I found the debiasing step via the inversion of the response randomization matrix $Q_{c,a}$ to be really interesting and non-trivial. However, its stability (especially when $\\lambda$ is close to 1) is not formally explored (as far as I could tell) and might be a source of unnecessary variance if the matrix is near-singular (is that right?). Could the authors discuss this a bit further? Extrapolating from the $\\lambda$ experiments seem to suggest this could be a problem, but maybe I'm over-interpreting these results.", "methods_and_evaluation_criteria": "The authors do not provide an extensive empirical evaluation, only a standard evaluation with a synthetic dataset and on (real) youtube data. This is adequate, as the main results of the paper are theoretical. However, more in depth empirical evaluation of Cluster DP would be great in future work.", "theoretical_claims": "I congratulate the authors on their careful formal statements and detailed proofs. I checked the proofs of Theorems A.5 (on the baseline uniform approach) and 3.1 (the Cluster DP mechanism). I did not find issues with either. Though I did not check it carefully, I skimmed the proof of Theorem 3.4 (for the main variance reduction claim), which is well broken up into propositions and lemmas.\n\nAs a general statement on the theory in this paper, though many of the tools used are standard, they are carefully and effectively combined in non-trivial ways, and the theory is broken up nicely to construct the desired bounds.", "experimental_designs_or_analyses": "I appreciated the conditional bias plots and variance gap plots, and the qq-plots. The youtube data seems reasonable for this problem. I'd be curious for the authors to comment on the empirical efficiency of their algorithm?\n\nI was unable to carefully check their experiments as the code wasn't provided.", "relation_to_broader_scientific_literature": "The manuscript appears well-situated within the literature. In particular, the authors claim a \"tighter analysis\" [Esfandiari et al. 2022] than previous work and substantiate the claim.", "essential_references_not_discussed": "Not aware of any.", "other_strengths_and_weaknesses": "Strengths:\nI congratulate the authors on this work, which I think is original and clearly presented. That said, it's not clear to me that it is particularly \"significant\" in that I'm not as aware of the desire for label-DP privacy guarantees in clustering for downstream causal effect estimation (a little niche). \n\nSo, in that sense, I would not consider this work to be award level, but I certainly believe it merits acceptance.\n\nWeaknesses:\nThe authors do a good job motivating the work in the intro for a specific application.\n\nHowever, the intuition for their approach could be better communicated. I found myself drawing some simple pictures to try to get a sense of why the Cluster-DP algorithm is a good idea for variance reduction; the authors should provide better intuition (through plots or a carefully constructed distributional example) to help the reader grasp the approach.", "other_comments_or_suggestions": "Nitpicks (mostly notational):\nMaybe I missed something, but the vector $y$ is used to denote the entire response space and in expressions like $\\mathbf{y}^\\top$. Can you distinguish between the vector of outcomes and the set $\\mathcal{Y}$ of possible outcomes in your notation?\n\nSome proofs switch between notations such as $\\mathbf{y}_{0,c}^2$ and \"\\overline{y^2_{0,c}}\"  $= 1 / n_{0,c} \\sum y_i^2 (0)$ or something, which made it hard for me to follow whether it was a sum or an average sometimes. Some of the $\\bar{y}$ and $\\overline{y_{0,c}}$ notational norms were more confusing than helpful.\n\nYou left some of the text from the template at the very bottom of the appendix, please delete in camera ready.", "questions_for_authors": "Q1. Theorem 3.1 presents a privacy bound that splits into a term derived from the Laplace mechanism and a term from the re-sampling process. Could you please discuss whether these bounds are tight in practice (I'm not sure your experiments really give us a sense, but maybe I'm missing something)? Are there settings or data regimes where you'd expect the analysis to be overly conservative?\n\nQ2. Your estimator relies on inverting the response randomization matrix $Q_{c,a}$. Under what conditions might this matrix become ill-conditioned, and how does that affect the variance of $\\hat{\\tau}_Q$? Is there a safeguard in your method for cases where the inversion is unstable? Maybe I'm misunderstanding something, I'd appreciate if the authors could help me here.\n\nQ3. My understanding of both the theory and the empirical results is that the variance reduction benefits rely on cluster homogeneity (authors parameterize this as $\\phi_a$). Can you elaborate on how robust your method is to mis-specified or sub-optimal clustering? E.g., if clusters are more heterogeneous than assumed? This is sort of touched on by considering \"Cluster-free DP,\" but I'm wondering if there's a smooth interpolation between that and the \"Cluster-DP\" version.\n\nQ4. This is a future work question: you gave a mechanism that, as far as I can tell, seems to work only for discrete outcome spaces (even though you expand it beyond binary). Is there hope for continuous outcomes? Can you discuss the foreseeable issues more carefully? You mention binning - the bin sizes could be parameterized, and done in such a way that adapts to the cluster structure. This seems natural, and may be worth discussing in future work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "M0nVbtego6", "reviewer": "Reviewer_WorV", "summary": "This paper proposes a differentially private algorithm for causal effect estimation, which leverages cluster structure in the data in order to reduce the variance (i.e., improve utility) while maintaining the same privacy guarantee.\n\n## update after rebuttal\n\nI’m bumping up my score, after reading the rebuttal and the other reviews. I think the novelty and theoretical results are strong selling points of the paper, though I do still feel that the label DP setting limits its scope. I think the paper would benefit from a more careful exposition of label DP (including its limitations and what it does and does not protect) and also in what scenarios is it reasonable to assume that attributes are non-sensitive.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their careful review of our paper. We hope to have addressed their questions, and would be happy to clarify these points in a camera-ready version.\n\n_Response to weaknesses:_\n\nAlthough we focus the presentation on a motivating application in the advertising space—which is already a very broad and important application, deriving most of the revenue of big tech companies—this framework can definitely be applied to other domains. We discuss a few here:\n- Healthcare: To analyze the causal effect of medical interventions, treatment strategies, and healthcare policies while preserving patient privacy. Here, the clustering can be done based on non-sensitive information, e.g. age, race, demographic information.\n- Finance: To study the causal impact of economic policies and investment strategies on financial outcomes, risk management, and market stability. Here, the clustering can be done based on the company industry classification information (eg. NAICS), size of the company, other public data (revenue, profit, stock price,...)\n- Social Sciences: To analyze the causal impact of social policies and societal factors on users behavior. Here, the clustering can be done demographic information as well as other publicly available data on users' social platforms.\n \n_Response to Questions:_\n\n- The variance of the full DP case will be larger than the partial DP (non-sensitive cluster and private response).  Since $\\epsilon_2 <\\epsilon$, in the full DP we need to add more noise in randomizing the responses. In addition, to preserve the privacy of clusters, we need to have some randomization there as well. This affects the variance because it  increases the cluster homogeneity quantities $\\phi_0,\\phi_1$, since these will now be defined w.r.t noisy clusters and will naturally  be larger than when they are defined w.r.t actual clusters. \n- No, it wouldn’t mix. In fact two important properties of differential privacy (which are widely used in practice and design) are composition and post-processing. The first states that combining two DP mechanisms will remain DP (but their privacy loss will be added); see sec 3.5 in [1]. The latter states that DP is immune to post-processing; see prop 2.1 in [1]. \n- The propose-test-release (PTR) mechanism aims to reduce the noise addition for privacy by working with local sensitivity instead of the global sensitivity. Such an approach can be seamlessly integrated into our mechanism, specifically in Algorithm 1 (line 228-229), when adding the Laplace noise: we can scale its noise using PTR and local sensitivity of empirical distribution of the cluster. However, we believe this would yield only minor benefits since the global sensitivity of empirical distribution is already 1/cluster-size; the PTR works most effective when the range of outputs is large.  \n\n[1]: “The Algorithmic Foundations of Differential Privacy”, Cynthia Dwork, Aaron Roth", "claims_and_evidence": "The claims made in the submission are supported by evidence.", "methods_and_evaluation_criteria": "The methods make sense for the problem at hand.", "theoretical_claims": "I didn't check the correctness of any of the proofs.", "experimental_designs_or_analyses": "I didn't check that carefully, but the experimental designs looked sound to me.", "relation_to_broader_scientific_literature": "The contributions of the paper are related to differentially private causal inference.", "essential_references_not_discussed": "All relevant related works are discussed in the paper, as far as I can tell.", "other_strengths_and_weaknesses": "Strengths --\n- Novel premise: I appreciated the idea of leveraging cluster structure in order to improve utility.\n- I thought the theoretical results were quite nice — presented cleanly, technically sound (to the best of my knowledge) and interpretable. For example, Theorem 3.4 is a nice result that provides insight into what type of clusters can best reduce the variance.\n- The paper is written nicely and communicates its ideas effectively. \n\nWeaknesses --\n- The proposed algorithm is very heavily inspired by one particular application (descibed in detail on the first page). It’s not totally clear to me how well this approach would generalize to other applications. In particular, any other use case for CLUSTER-DP would require access to non-sensitive user attributes which might not always be readily available. (The authors did address this point in Remark 2.1, but I’m not sure I’m wholly satisfied.)\n- The experimental results are mostly based on a numerical simulation; assuming I haven’t missed anything, the only non-simulated dataset is the Youtube dataset. To demonstrate the practicality of the algorithm, it would have been nice to see more experiments conducted on a broader array of realistic datasets.", "other_comments_or_suggestions": "I might have liked to see more justification on why label DP makes more sense as a privacy setting compared to standard DP.", "questions_for_authors": "- Going back to Remark 2.1, let’s say that the cluster structure is sensitive and privatizing the cluster requires $\\epsilon_1$ privacy budget. For the end-to-end process to have the same privacy guarantee $\\epsilon  = \\epsilon_1 + \\epsilon_2$ as the algorithm with non-sensitive cluster structure, we’d need reduce the $\\epsilon_2$ budget for privatizing the outcomes and thus re-introduce more variance. I am wondering if it would be possible to address this point? For example, are there allocations of $\\epsilon_1$ and $\\epsilon_2$ for which the end-to-end process would still have less variance than the non-sensitive cluster situation where the privacy budget can be fully devoted to privatizing the outcomes (i.e., $\\epsilon = \\epsilon_2$)?\n\n- Another question that I have about Remark 2.1 is that wouldn't the end-to-end process mix DP (for privatizing the clusters) and label DP (for privatizing the outcomes)? Would the resulting privacy guarantee thus be possible to easily interpret?\n\n- The paper’s approach is to set a privacy level, then for certain well-behaved cluster structures be able to achieve better utility. Rather than showing improved utility via bounding the variance of the estimator, I would be interested to know if the authors considered using something like Propose-Test-Release to reduce the noise scale (and maybe more directly improve the utility of the algorithm) for nicely-behaved clusters.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper examines differentially private causal estimation under the label-DP setting, where features are observed but labels are sensitive, and features can be used to cluster users. The authors introduce a novel estimation mechanism based on these clusters that can improve the privacy-utility tradeoff and analyze the mechanism theoretically and empirically, showing that better cluster quality translates to higher utility for the same privacy level.

After discussion, the reviewers were unanimous in favor of acceptance. They found the paper's problem setting and approach novel and the theoretical results rigorous and insightful, with supporting empirical evidence. The two main critiques were: (1) the problem setting, while significant, was perhaps narrow, and (2) concerns about the label-DP setting. For (1), no reviewer felt this was a major concern, and I believe the strengths of the paper outweigh this concern. For (2), the main concern came from Reviewer giHc in their comments about inferential privacy, and to a lesser extent from Reviewer WorV, who had questions about the label-DP setting. I found that these concerns were well addressed by the rebuttal, and both reviewers raised their scores. In particular, my own view is that the issue of inferential privacy is orthogonal to the choice of DP vs. label-DP and that label-DP is an existing notion that is correctly utilized in this paper. The authors can improve the paper by providing a longer discussion of label-DP and its assumptions and any potential limitations.
Decision: Accept (poster)