Private Estimation When Data and Privacy Demands Are Correlated

We consider the problem of mean estimation of univariate data and frequency estimation of categorical data under heterogeneous privacy demands in the central-DP model. In this model, users provide the server with their datapoint (such as their salary in mean estimation or salary bracket in frequency estimation) and a privacy level. The server is then tasked with publishing an estimate of the sample mean or relative sample frequencies of the categories in the dataset, while respecting the individual privacy constraints. We consider the adversarial minimax setting where the dataset is the worst-case for the algorithm. This is in contrast to the statistical minimax setting where the dataset is sampled from a worst-case distribution. For this adversarial model, we formulate two distinct settings: the so-called correlated and weakly-correlated settings. These are explained below, and formally defined in Section 2. Both estimation problems are studied in both correlated and weakly-correlated settings, under both PAC error and mean-squared error.

Since we assume that we are given the heterogeneous privacy demands, simply considering the worst-case dataset leads to arbitrary correlations between user data values and their individual privacy requirements. Correlations may be reasonable for certain cases. For example, users sharing their salary may demand higher privacy if they are have an extremely high or low salary. Such correlations make it harder to estimate frequencies of categories in which users demand a lot more privacy. We emphasize that such correlations, although often accepted to be present in real-world, have never been modeled in the literature prior to this work that the authors are aware of.

It is equally well-motivated to consider the weakly-correlated setting where users do not have a strong correlation between their data and privacy demand. For example, for frequency estimation of users’ geographical-region, there may be no meaningful correlation between a user’s location and their privacy demand. We formulate this “weakly-correlated” setting by modeling the realization of the dataset as a uniformly random permutation of a worst-case dataset.

We propose algorithms for both PAC error and mean-squared error, for both correlated and weakly-correlated settings, for both mean and frequency estimation. Thus, in this work, we investigate eight different minimax rates. To obtain tight upper bounds on the minimax rates, we consider slightly different algorithms tailored to each combination of problem, setting, and error metric. However, we also present a fast heuristic algorithm that is agnostic to the underlying modeling assumptions and performs well in practice for all eight problems. Through experiments, we compare our algorithms to natural baseline algorithms and show superior performance of our algorithms. We also prove the minimax optimality of our algorithms for some combinations of problems and error metrics.

Organization: We define the problem in Section 2 and describe our algorithm in Section 3. Experiments are presented in Section 4, followed by theoretical analysis of the minimax rate in Section 5. Extended discussion can be found in Section 6, followed by concluding remarks on possible future directions of work.

The two most common models for DP are the central-DP model [22] and the local-DP model [32]; we focus on the central-DP model. The problem of frequency estimation under privacy constraints is well-studied under homogeneous DP [23, 29, 24, 44]. Mean estimation under privacy is also well-studied (see Biswas et al. [13] for references); although most work on mean estimation focuses on the statistical setting, one can use the ideas from empirical frequency estimation of Dwork et al. [23] and corresponding lower bounds from Vadhan [40] to obtain good error bounds for empirical mean estimation.

In terms of heterogeneity in privacy demands, a special case considered in the literature is the existence of a dataset requiring homogeneous privacy in conjunction with a public dataset [9, 10, 34, 5, 37, 30, 6, 42, 12]. Some early works on Heterogeneous DP (HDP) [4, 28] propose task-agnostic methods to deal with the heterogeneity in privacy. While the methods are versatile since they are task agnostic, one can not expect competitive performance from their methods for specific tasks like mean or frequency estimation. Further, neither of the methods can handle the case if there is a single user having no privacy demand (public data). Mean estimation under HDP is considered by Ferrando et al. [26] in the local-DP model, assuming the variance of the distribution is known. HDP mean estimation under the central-DP model has been studied in the statistical setting where users have i.i.d. data [25, 16, 18, 19]. Acharya et al. [2] study the problem of ridge regression under HDP and provide an algorithm similar to one of our baseline techniques we use in the experiments.¹¹1Their method can perform arbitrarily worse than the minimax optimal ridge regression algorithm; see the “Prop” algorithm in Section 4. HDP has also been considered in the context of mechanism design, auctions, and data valuation [25, 7, 31]. The problem of creating confidence intervals for the mean under sequential observations in local-DP was studied by Waudby-Smith et al. [45] for univariate random variables with heterogeneity in privacy demand. Canonne and Yucheng [15] present the problem of testing whether two datasets are from the same multinomial distribution under a different privacy constraint for each dataset.

Chaudhuri et al. [18] find the minimax optimal mean estimator for a given heterogeneous privacy demand when the user data is sampled i.i.d. from some unknown univariate distribution. The estimators employed in this work are similar in spirit to their work and our weakly-correlated setting exhibits a minimax rate closely related to their minimax rate. The exact relation between the two minimax rates, while intuitive, is non-trivial. The correlated setting we consider is significantly different from their set up and the results are proved using different techniques.

In the context of modeling correlations between privacy demand and data, Ghosh and Roth [27] show a negative result in the context of mechanism design. Ghosh and Roth [27] show that a dominant strategy incentive compatible mechanism for selling privacy at an auction, where privacy is provided to both user’s data and privacy sensitivity, is not possible in a meaningful way. However, we do not operate in the setting of an auction so the question of how to deal with correlations between data and privacy remains open. However, aside from Ghosh and Roth [27], the literature so far lacks any clear formulation of this problem, let alone a solution.

The probability simplex in $n$-dimensions is represented by ${\mathrm{\Delta }}_n$. The notation $a\wedge b$ is used to denote $\min \{a,b\}$. We use $\lceil \cdot \rceil$ to refer to the modified ceiling function $\lceil x\rceil =\min \{m\in \mathbb{Z}:m>x\}$. The notation $\mathrm{𝟏}$ denotes the vector, of appropriate length, with all entries being equal to $c$. In this work, the notation $M(\cdot )$, denoting a randomized algorithm $M$ mapping ${𝒳}^n$ to a probability distribution on $𝒴$, will interchangeably be used to refer to the output distribution or a sample from it. For vectors $𝒙$ and $𝒚$, $𝒙/𝒚$ shall represent element-wise division. The notations $\lesssim$ and $\simeq$ denote inequality and equality that hold up to a universal multiplicative constant.

Heterogeneous Differential Privacy (HDP) permits users to have different privacy requirements. The standard definition for HDP is presented in Definition 1 [4, 25].

In the DP framework, smaller $ϵ$ means higher privacy. The privacy levels $ϵ$ can range from zero to infinity.

Let $n$ be the number of users and let the heterogeneous privacy demand of the users be the vector $\mathit{ϵ}$. Without loss of generality, we assume it is arranged in a non-decreasing order, i.e., user $i$ has privacy requirement ${ϵ}_i$, and ${ϵ}_i\le {ϵ}_j$ for $i\le j$. We operate in the central-DP regime.

For normalized empirical frequency estimation with $k$ categories (or bins), we have $𝒳=[k]$ and $𝒴={[0,1]}^k$; the parameter $k$ is assumed to be known. For empirical mean estimation, without loss of generality, we consider $𝒳=[0,1]$ and $𝒴=[0,1]$. We study the problem in the adversarial minimax regime – for an algorithm, the worst case performance over all datasets is analyzed. We formulate two settings to capture possible correlations.

1. 1.

   Correlated setting: In this setting, for the privacy demand and $\mathit{ϵ}$-DP mechanism given, an adversary chooses a worst-case dataset $𝒙\in {𝒳}^n$. In other words, for user $i$ with privacy demand ${ϵ}_i$, adversary chooses the datapoint $x_i$ for $i\in [n]$.

2. 2.

   Weakly-correlated setting: In this setting, for the privacy demand and $\mathit{ϵ}$-DP mechanism given, an adversary chooses a worst-case dataset $𝒙\in {𝒳}^n$ that gets randomly permuted. That is, if $\sigma :[n]\to [n]$ denotes a uniformly random permutation over $[n]$ then user $i$ with privacy demand ${ϵ}_i$ is assigned the datapoint $x_{\sigma (i)}$. Henceforth, we let ${𝒙}_{\sigma }$ denote the permuted dataset.

Section 2.3 motivates these two settings. Let $\mu (𝒙)$ refer to the true empirical statistic of the dataset. In other words,

• $\mathrm{■}$

  For mean estimation, $\mu (𝒙)\in [0,1]$ and it is defined as $\mu (𝒙)=\frac{1}{n}{\sum }_{i=1}^n{x}_i$.

• $\mathrm{■}$

  For frequency estimation, $\mu (𝒙)\in {\mathrm{\Delta }}_k$ and the $j$-th component of $\mu (𝒙)$ is defined as $\mu {(𝒙)}_j=\frac{1}{n}{\sum }_{i=1}^n𝕀\{x_i=j\},j\in [k]$.

Note that these functions are permutation-invariant, i.e., $\mu (𝒙)=\mu ({𝒙}_{\sigma })$. Let ${ℳ}_{\mathit{ϵ}}$ refer to the set of all $\mathit{ϵ}$-DP mechanisms from ${𝒳}^n$ to $𝒴$. We define the minimax rates of frequency estimation in Definition 2.

Similarly, we define the minimax rates for mean estimation in Definition 3, deferred to Appendix A.

Since we consider the error bounds for a given privacy demand and an adversarial dataset, there could be an arbitrary correlation between the dataset and the privacy demand in the correlated setting. Considering arbitrary worst-case correlations avoids the need for obscure assumptions on joint distribution between privacy and data. This may or may not be desired, depending on the application. For example, if the categorical data consists of salary range of users, then the users in the highest and lowest salary range might demand a higher privacy leading to correlations between data and privacy demands.

A counterexample is if the categorical data consists of different types of cancers in patients; in this case such correlations need not exist in a meaningful way. Thus, to model such setting without meaningful correlations, we formulate the weakly correlated setting. Another possible way to break the correlation is to go to the statistical minimax setting where the samples are generated i.i.d. from some distribution, independent of the privacy demands, and the goal is to estimate the underlying multinomial distribution. The weakly correlated minimax rates and the statistical minimax rates are closely related (see Theorem 3). In other words, the random permutation of the worst-case dataset in the weakly correlated setting effectively breaks the correlations between the privacy demand and the dataset.

The above described statistical minimax rate is not related to the correlated adversarial minimax rate in a meaningful way. To see this, consider the case where all the users have no privacy constraint; the correlated adversarial minimax error is zero but the statistical minimax error is of the order $\frac{1}{\sqrt{n}}$ (PAC or square-root of MSE). Conversely, consider the case where $n/2$ users demand no privacy and rest of the users demand $ϵ\to 0$; the statistical rate is of the order $\frac{1}{\sqrt{n}}$ but the correlated adversarial minimax rate is of the order $1$.

We do not consider the worst case of $\mathit{ϵ}$ since the worst-case is trivial when every user demands full privacy ($ϵ\to 0$) and no meaningful estimation can be done. Other possible modeling choices, not presented in this work, include a different norm for errors, the statistical setting where the underlying dataset and privacy demand is jointly generated according to some distribution, and so on.

In the correlated regime, we present Theorem 1 on the minimax optimality of HPF-C$\mathbb{P}$ and HPM-C$\mathbb{P}$ in a certain regime of interest of the PAC minimax rate. The proof is presented in [17, Appendix I].

In particular, when the PAC minimax rate is at least $\frac{1}{2n}$ and at most $\frac{1}{4}$, then our upper bound is of the same order as the minimax rate, for both mean and frequency estimation. We emphasize that this really is the regime of interest for the problem being considered; without any privacy constraint, normalized mean and frequency count is naturally of the precision $\frac{1}{n}$. Theorem 6 also assumes that the PAC minimax rate is bounded away from the trivial upper bound of $\frac{1}{2}$. Thus, for the practically important regime of values of the PAC minimax rate, our proposed algorithms are order optimal.

In the weakly-correlated regime, to compare the PAC upper and lower bounds, we consider two regimes. This is primarily because of the lower bounds presented in Theorem 6 are difficult to analyze without further simplifications. Let $\mathrm{𝖵𝖺𝗋}(e^{-\mathit{ϵ}})$ denote the empirical variance of the vector $e^{-\mathit{ϵ}}$. Theorem 2 shows how the upper and lower bounds behave in the high privacy regime; the proof can be found in [17, Appendix I].

The high privacy assumption, i.e., ${\parallel \mathit{ϵ}\parallel }_{\mathrm{\infty }}\le 1$, is helpful for dealing with the implicit lower bounds presented in terms of expectation in Theorem 6. Such assumptions on the privacy level are frequent in the literature, even for homogeneous privacy [25, 21]. The downside to this regime is that it does not explain what occurs if there are some users desiring no privacy $(ϵ\to \mathrm{\infty })$, i.e., there is some public data. While HPF-W$\mathbb{P}$ and HPM-W$\mathbb{P}$ can handle such $\mathit{ϵ}$, the theorem can not. We remark that the assumptions made in Theorem 2 might be a shortcoming of the analysis and not the algorithm. For the homogeneous privacy demand $ϵ$, one can recover the minimax rate $1/nϵ$ from the theorem since the variance term is zero; see Dwork et al. [23] and Vadhan [40] for upper and lower bounds respectively.

Before presenting MSE minimax optimality result for the weakly-correlated setting in Theorem 3, we define another minimax rate closely related to the problem. For some set $S$, let $𝒫(S)$ denote the set of probability distributions on $S$; for a distribution $P$, let $\mu (P)$ denote its mean. Similar to the MSE-minimax rates, we define the minimax rate for mean estimation under $\mathit{ϵ}$-DP from i.i.d. data as

We take a moment to comment on ${ℰ}_{stat}(\mathit{ϵ})$. For $n$-users with no privacy demand, let $\mathbf{\infty }=(\mathrm{\infty },\mathrm{\dots },\mathrm{\infty })$, then note that ${ℰ}_{stat}(\mathbf{\infty })\simeq \frac{1}{n}$ as this is the standard minimax rate for mean estimation without privacy constraints [41]. Note that we have ${ℰ}_{wc}^f(k,\mathbf{\infty }),{ℰ}_{wc}^m(\mathbf{\infty })=0$. In Theorem 3, we show MSE-minimax optimality of the proposed algorithms for the weakly-correlated setting in the regime of privacy demands where $\mathit{ϵ}$ causes a non-trivial increase in the statistical rate ${ℰ}_{stat}$ to be greater than $\frac{1}{2n}$. In fact, in this regime, the MSE-minimax rates for empirical mean and frequency estimation are nearly the same as the MSE-minimax rate for statistical mean estimation.

The proof can be found in [17, Appendix J]. The $\log$-factor difference in the upper and lower bounds for ${ℰ}_{wc}^f(k,\mathit{ϵ})$ can probably be improved with a tighter lower bound.