Enhancing Feature-Specific Data Protection via
Bayesian Coordinate Differential Privacy ^††thanks: The authors are listed in alphabetical order.

Our main contribution is addressing the challenge of feature-specific data protection from a Bayesian perspective. We present a novel Bayesian privacy framework, which we refer to as Bayesian Coordinate Differential Privacy (BCDP). BCDP complements LDP and allows a tailored privacy demand per feature. In essence, BCDP ensures that the odds of inferring a specific feature (also referred to as a coordinate) remain nearly unchanged before and after observing the outcome of the private mechanism. The framework’s parameters control the extent to which the odds remain unchanged, enabling varying levels of privacy per feature. As part of developing this new framework, we explore its formal relationship with other related DP notions and examine standard DP properties, such as post-processing and composition.

To demonstrate the efficacy of our framework, we study two fundamental problems in machine learning under a baseline level of LDP privacy, coupled with more stringent per-coordinate BCDP constraints. First, we address multivariate mean estimation. Our proposed algorithm satisfies BCDP constraints while outperforming a standard LDP algorithm, where the privacy level is determined by the most sensitive coordinate. Our experimental results confirm this advantage. Second, we present an algorithm for ordinary least squares regression under both LDP and BCDP constraints.

A key technical component of our algorithm for these two problems is a mechanism that builds on any off-the-shelf LDP mechanism and can be applied to various problems. Our algorithm involves making parallel queries to the LDP mechanism with a series of carefully selected privacy parameters where the $i$-th query omits the $i-1$ most sensitive coordinates. The outputs are then aggregated to produce the most accurate estimator for each coordinate.

We now give a high-level discussion of privacy in the Bayesian framework to motivate our approach. Formal definitions are in Section 2. Consider a set of users, each possessing a high-dimensional data point $\vecx$ with varying privacy protection needs across different features. For instance, $\vecx$ may contain genetic markers for diseases, and the $i$-th coordinate $x_{i}$ could reveal Alzheimer’s markers that the user wishes to keep strictly confidential. In a local privacy setting, users apply a locally private mechanism $M$ to obtain obfuscated data $M(\vecx)$, for public aggregation and analysis. Our focus is on understanding what can be inferred about $\vecx$, especially the sensitive feature $x_{i}$, from the obfuscated data.

Now, imagine an adversary placing a bet on a probabilistic event related to $\vecx$. Without extra information, their chances of guessing correctly are based on prior knowledge of the population. However, access to $M(\vecx)$ could prove advantageous for inference. Privacy in the Bayesian model is measured by how much $M(\vecx)$ improves the adversary’s chances. In other words, the privacy parameter limits how much their odds can shift.

The standard Bayesian interpretation of LDP ensures uniform privacy across all data features. In contrast, our framework BCDP enhances LDP by enabling feature-specific privacy controls. That is, BCDP restricts adversarial inference of events concerning individual coordinates. For example, BCDP ensures that the advantage an adversary gains from observing $M(\vecx)$ when betting on whether a person has the Alzheimer’s trait (i.e., $x_{i}=1$) is smaller than what would be achieved under a less stringent LDP constraint.

We remark that BCDP does not replace LDP, since it lacks global data protection. Also, correlation plays a crucial role in BCDP’s effectiveness: if a sensitive feature is highly correlated with less sensitive features, increasing protection for the sensitive feature imposes stricter protection for other features as well. As the correlation between features increases, BCDP’s guarantees converge to the uniform guarantees of LDP.

Statistical inference with LDP guarantees has been extensively studied. For comprehensive surveys see Xiong et al. (2020); Yang et al. (2023). Below, we discuss the results that are most relevant to our setup.

Several papers consider the uneven protection of privacy across features. For instance, Ghazi et al. (2022) and Acharya et al. (2020) focus on settings where the privacy parameters vary across different neighboring datasets. Other models arise from altering the concept of neighboring datasets (Kifer and Machanavajjhala, 2014; He et al., 2014), or they emphasize indistinguishability guarantees within a redefined metric space for the datasets or data points Chatzikokolakis et al. (2013); Alvim et al. (2018); Imola et al. (2022); Andrés et al. (2013). Another relevant notion for classification tasks is Label-DP which considers labels of training data as sensitive, but not the features themselves (Chaudhuri and Hsu, 2011; Beimel et al., 2013; Wang and Xu, 2019; Ghazi et al., 2021). A recent generalization of Label-DP, proposed by Mahloujifar et al. (2023), is Feature-DP, which allows specific features of the data to be disclosed by the algorithm while ensuring the privacy of the remaining information. A line of work, e.g., Kifer and Machanavajjhala (2011); Kenthapadi et al. (2013), studies attribute DP, which limits changes in the output distribution of the privacy mechanism when a single coordinate of the data is modified.

A common shortcoming in the aforementioned approaches is that the heterogeneous privacy protection across features, without accounting for their correlations, can lead to unaddressed privacy leakage—an issue our framework is specifically designed to mitigate. Another key distinction of our work is the integration of the BCDP framework with the LDP framework, enabling simultaneous protection at both the feature level and the global level.

A Bayesian approach to Central-DP is considered in Triastcyn and Faltings (2020) where the notation of neighboring dataset are taken over pairs that are drawn from the same distribution. This is similar in spirit to our framework but we operate in the Local-DP regime so we work with a prior instead. Xiao and Devadas (2023) consider a Bayesian approach to privacy where the goal is to prevent an observer from being able to nearly guess the input to a mechanism under a given notion of distance and error probability. Another Bayesian interpretation of DP is presented in Kasiviswanathan and Smith (2014) and show that DP ensures that the posterior distribution after observing the output of a DP algorithm is close to the prior in Total-Variation distance. None of these results explicitly focus on varying privacy features across coordinates.

Private mean estimation and private least-squares regression are well studied problems in literature in both central (Biswas et al., 2020; Karwa and Vadhan, 2017; Kifer et al., 2012; Vu and Slavkovic, 2009) and local (Asi et al., 2022; Feldman and Talwar, 2021; Zheng et al., 2017) DP regimes. We depart from these works as we consider a BCDP constraint in addition to an LDP constraint.

We present a formal treatment of our framework in Section 2. Some key properties of the framework are presented in Section 3. We consider the problem of mean estimation in Section 4 and ordinary least-squares regression in Section 5.

We first revisit the definition of Local Differential Privacy (LDP).

With the understanding that $M(\vecx)\sim\mu_{\vecx}(\cdot)$, Definition 1 can be rewritten in the more familiar form $\text{Pr}\{M(\vecx)\in R\}\leq e^{\varepsilon}\text{Pr}\{M(\vecx^{\prime})\in R\}\ \forall\vecx,\vecx^{\prime}\in\cX,R\in\cF_{\cY}$.

Next, we focus on a Bayesian interpretation of this setting. Suppose we have an underlying data distribution $\pi$. That is, we equip $(\cX,\cF_{\cX})$ with the probability measure $\pi$ which we call the prior. This induces a probability space $(\cX\times\cY,\cF_{\cX}\times\cF_{\cY},P)$ where the measure $P$ is characterized via

Note that the mechanism $M$ defining $\mu$ is precisely represented on this space by the random variable $M:(\vecx,y)\in\cX\times\cY\mapsto y$. By a slight abuse of notation, we continue to denote the (randomized) output of the mechanism by $M(\vecx)$. We first define the sets on $\cX$ which have positive probability under $\pi$

For $S\in\cF_{\cX}^{+}$ and $R\in\cF_{\cY}$, note that

We now introduce a Bayesian formulation of the LDP definition which involves both the mechanism $M$ and the prior $\pi$. This can be seen as the local version of the definitions proposed in earlier works, e.g., Kifer and Machanavajjhala (2014); Triastcyn and Faltings (2020).

We show in Proposition 1 that $\varepsilon$-LDP and $\varepsilon$-BDP can be viewed as equivalent, modulo some technicalities.

The reverse direction of the equivalence above relies on $\cY$ being a Polish space, which should capture all settings of practical interest. The proof can be found in Appendix A.1.

As discussed in Kifer and Machanavajjhala (2014), we can interpret the BDP definition in terms of odds ratios. The prior odds of two disjoint events $S$ and $S^{\prime}$ is given by $\pi(S)/\pi(S^{\prime})$. Now, for a set $R\in\mathcal{F}_{\mathcal{Y}}$ with positive measure, the posterior odds, after observing mechanism output $M(\vecx)\in R$, is equal to

One can easily verify that the BDP definition implies that the ratio of posterior and prior odds, also known as the odds ratio, is in the interval $[e^{-\varepsilon},e^{\varepsilon}]$. In other words, the BDP definition limits how much the output of the mechanism changes the odds, which in turn limits our ability to distinguish whether the data $\vecx$ was in $S$ or $S^{\prime}$.

We wish to measure the privacy loss of each coordinate incurred by a mechanism $M$. Initially, one might hypothesize that by altering the definition of LDP to reflect changes in specific coordinates, we could achieve privacy protection for certain features of the user’s data. More precisely, consider the following definition of Coordinate DP (CDP)¹¹1The acronym CDP is not to be confused with Concentrated DP, which is not considered in this work. where $\bm{c}$ represents a vector of the desired levels of privacy for each coordinate.

A special case of CDP, where all $c_{i}$’s are equal, is referred to as attribute DP in the literature Kifer and Machanavajjhala (2011); Kenthapadi et al. (2013); Ghazi et al. (2022). Additionally, CDP itself can be viewed as a special case of Partial DP, introduced in Ghazi et al. (2022).

The drawback of this definition is that it does not account for potential correlation among the data coordinates and, therefore, does not provide the type of guarantee we hope for regarding sensitive parts of the data. In other words, in $\bm{c}$-CDP, stating that the privacy level of coordinate $i$ is $c_{i}$ could be misleading. For instance, having $c_{i}=0$ does not necessarily ensure that no information is leaked about $x_{i}$, as the other (potentially less-well protected) coordinates $\vecx_{-i}$ may be correlated with it.

In order to capture the correlation among the data coordinates, we adopt a Bayesian interpretation of differential privacy. As seen in Proposition 1, BDP and LDP are closely related and this serves as the main motivation for our definition.

For $i\in[d]$, define

For $S_{i}\in\cF_{\cX_{i}}^{+}$, we have

where $\cX_{-i}=\bigtimes_{j\in[d],j\neq i}\cX_{j}$. Thus, similar to Definition 2, we have a natural version of privacy for each coordinate which we shall refer to as Bayesian Coordinate DP (BCDP).

Unlike the Coordinate-DP definition, this definition accounts for potential correlation between coordinates through incorporation of the prior $\pi$.

It is worth noting that, similar to the BDP definition, we can interpret the BCDP definition in terms of the odds ratio, with the difference that we consider the two events $\{x_{i}\in S_{i}\}$ and $\{x_{i}\in S_{i}’\}$. In other words, having a small $\delta_{i}$ guarantees that the mechanism’s output does not provide much useful information for discriminating between the possibilities that the underlying data has coordinate $x_{i}$ in $S_{i}$ or $S_{i}’$. This aligns with our goal of proposing a new formulation that characterizes how much information is revealed about each particular coordinate. We further discuss this interpretation in the next section.

Let there be $n$ users submitting their data to a central server via Local DP mechanisms. Let user $j$’s data be $\vecx^{(j)}\in[-1,1]^{d}$, where $\vecx^{(j)}$ is drawn from prior $\pi^{(j)}$ on $[-1,1]^{d}$; the server and users are not assumed to know the priors (which may be different for each individual user). Our goal is to estimate the empirical mean $\bar{\vecx}=\sum_{j=1}^{n}\frac{\vecx^{(j)}}{n}\in[-1,1]^{d}$ under $\varepsilon$-LDP and $\bm{\delta}$-BCDP. We consider $l_{2}$-norm as our error metric. Without loss of generality, we assume that $\bm{\delta}$ is in non-decreasing order. We make the following assumption regarding the priors.

Here $q$ can be interpreted as a measure of how much different coordinates are interdependent. For instance, in the case where coordinates are independent we have $q=0$, and in the case where they are fully equal, we have $q=1$. Note that we do not need (15) to hold for the last coordinate ($i=d$). While this slight relaxation does not play a role in this section, it will be useful when we move to the private optimization application.

It is also worth emphasizing that our analysis extends to cases where we have heterogeneous bounds across different coordinates (similar to $\eqref{eq:tv-bound}$) and different across users. However, we opt for a universal bound for the sake of simplifying the presentation of results. We assume that the upper bound $q$ is known to the designer of the local channels, which can be either the end user themselves or the central server.

Our proposed privacy mechanism $M_{\mathsf{mean}}$ (Mechanism 1) builds upon any LDP mechanism $M_{\mathsf{LDP}}$, capable of handling different dimensional inputs, that can be used for mean estimation as a black-box tool. While Algorithm 1 satisfies the privacy constraints for any black-box LDP mechanism $M_{\mathsf{LDP}}$, we shall focus on the mechanism presented by Duchi et al. (2013a) for proving error bounds. The mechanism of Duchi et al. (2013a), which is known to be minimax optimal for mean estimation, is outlined in Mechanism 2 for completeness. A figure explaining $M_{\mathsf{mean}}$ is presented in Figure 2.

Theorem 2 shows that our proposed mechanism satisfies the desired privacy constraints and provides a bound on the mean-squared error (MSE). The notation $a\wedge b$ refers to $\min\{a,b\}$. later in this section we present a refined result with a more interpretable MSE bound in Corollary 1.

The proof is presented in Appendix B.2. Here, we provide a proof sketch for the privacy guarantee. We first establish that $M_{\mathsf{mean}}$ is $\vecc$-CDP and $c_{d}$-LDP. The latter implies that $M_{\mathsf{mean}}$ also satisfies $c_{d}\bm{1}$-BCDP. Thus, if $\tilde{\delta}_{i}\geq c_{d}$, we have already shown that $M_{\mathsf{mean}}$ is $\delta_{i}$-BCDP with respect to the $i$-th coordinate. For the case where $c_{d}>\tilde{\delta}_{i}$, we use Proposition 4, which essentially implies that $M_{\mathsf{mean}}$ is $c_{i}+\log(1+qe^{c_{d}}-q)$-BCDP with respect to the $i$-th coordinate. Substituting the value of $c_{i}$ from the statement of Theorem 2 gives us the desired $\delta_{i}$-BCDP guarantee for coordinate $i$. Finally, the choice of $c_{d}$ in (16) ensures that the proposed $c_{i}$’s are all non-negative and valid.

We next make a few remarks regarding this result. First, note that while this bound applies to empirical mean estimation, when the data points $\{\vecx^{(j)}\}_{j=1}^{n}$ are independent and identically distributed, the result can also be used to derive an out-of-sample error bound for the statistical private mean estimation problem. In this case, an additional $\frac{d}{n}$ term would be added to the error bound. Secondly, note that in the special case where there is no coordinate-level privacy requirement (i.e., $\delta_{i}=\infty$), setting $\zeta=1$ implies $c_{1}=\ldots=c_{d}=\varepsilon$, which yields the error bound $\mathcal{O}({d^{2}}/(n\varepsilon^{2}))$. This matches the $\varepsilon$-LDP lower bound provided in Duchi et al. (2013a). Lastly, we would like to discuss the role of parameter $\zeta$. Note that when the correlation parameter $q$ is sufficiently high or the most sensitive privacy requirement $\delta_{1}$ is low enough such that $c_{d}$ is determined by the first term, $\log((e^{\zeta\tilde{\delta}_{1}}+q-1)/{q})$, in (16), one can verify that $c_{1}=(1-\zeta)\delta_{1}$. As $\zeta$ increases, $c_{1}$ decreases, leading to a worse estimate for the first coordinate. However, $c_{d}$ increases, indicating that, for the less-sensitive coordinates, we are increasing the privacy parameter, potentially resulting in lower estimation error for those coordinates. In other words, the parameter $\zeta$ allows us to control how we allocate the privacy budget of the most sensitive coordinate, $\delta_{1}$, between the estimation of the first coordinate and the privacy cost imposed by its correlation with other coordinates.

We next present a corollary that studies a special case where the coordinates are divided into more sensitive and less sensitive groups. In this case, users requests a general $\varepsilon$-LDP guarantee for all coordinates and a $\delta$-BCDP guarantee specifically for the more sensitive coordinates. Under this scenario, we further simplify the error bound which allows us to better highlight implications of Theorem 2.

Under the special structure of $\bm{\delta}$ and $\varepsilon$ in Corollary 1, the MSE can be thought of as sum of MSE of the more sensitive and the less sensitive coordinates. For low levels of correlation, the MSE of less private coordinates behave like the MSE of an $\varepsilon$-LDP mechanism on $d-k$ dimensional vector but the MSE of the more sensitive part depends on the dimension $d$ of the whole vector, not just the sensitive part, showing how the more sensitive part of the data affects the whole vector. As the correlation increases $q\to 1$, we have $c_{d}\to\delta/2$ and the MSE matches that of a $\min\bm{\delta}$-LDP mechanism. A supporting experiment is deferred to Appendix B.1.