Improving the Variance of Differentially Private Randomized Experiments through Clustering

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.

Response to weaknesses:

Although 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:

• 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.
• 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,...)
• 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.

Response to Questions:

• 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.
• 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].
• 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.

[1]: “The Algorithmic Foundations of Differential Privacy”, Cynthia Dwork, Aaron Roth

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:

Q1.

In 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.

[1] “The Composition Theorem for Differential Privacy”, Peter Kairouz et al, 203.

Q2.

This 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). This is also reflected in the variance bound, Thm 3.4, where $(1-\lambda)^2$ appears in the denominator.

Q3.

Thank 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).

Q4.

Absolutely. 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.

We thank the reviewer for their careful and overall positive review. We address below their two questions:

Q1.

These 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$.

L. 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$.

L. 1171-1173 identifies the necessary and sufficient conditions for proving that the mechanism $M_2$ is (\epsilon, \delta)-DP.

We now detail the steps made on L. 1174-1177 in further detail, starting with substituting the event probabilities identified on L. 1170.

Step 1 (substituting event probabilities): $1 - \lambda + \lambda \tilde q(y) \leq e^{\tilde \epsilon} (\lambda \tilde q(y)) + \delta$

Step 2 (rearranging terms): 1 - \lambda + \lambda \tilde q(y) ( 1- e^{\tilde \epsilon)) \leq \delta

By the definition of $\delta := \max(0, 1 -\lambda + \lambda \gamma ( 1- e^{\tilde \epsilon}))$, this condition is equivalent to showing two inequalities:

(a) $1 - \lambda + \lambda \tilde q(y) ( 1- e^{\tilde \epsilon}) \leq 0$ and

(b) $1 - \lambda + \lambda \tilde q(y) ( 1- e^{\tilde \epsilon}) \leq 1 -\lambda + \lambda \gamma ( 1- e^{\tilde \epsilon})$

(b) always holds because $\tilde q(y) \geq \gamma$ and $1- e^{\tilde \epsilon} \leq 0$ since $\tilde \epsilon \geq 0$.

Therefore 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)$

Q2.

We 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.

We 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.

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.

Correlation between non-sensitive and private data:

It seems that your comment is about the measure of differential privacy and its limitations. We would like to highlight a few points:

• 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.
• 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”.
• 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.
• 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.

We would be happy to add a discussion around these points in the revision.

[1]: “The Algorithmic Foundations of Differential Privacy”, Cynthia Dwork, Aaron Roth

[2]: “Training Differentially private Ad prediction models with semi-sensitive features”, L. Chua et. al

[3] “Anonymous learning via look-alike clustering”, A. Javanmard et. al

Response to Questions:

• 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))]$.
• 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.