Sampling

The privacy loss parameter is one of the most important policy decisions that the data curator¹ must make about a deployment. But there are other parameters that affect privacy, some in the data collection stage, such as whether the data comes from a “secret sample,” where secrecy means that the set of data subjects chosen from the broader population is confidential knowledge. The sample size, population size, and sampling method can all affect the privacy-utility tradeoff. A secret, simple random sample, for example, can “amplify” the privacy guarantee, allowing one to gain more utility for the same privacy loss.

Other types of sampling methods may not provide additional privacy guarantees. Consider cluster sampling, where a population is divided into disjoint subgroups (called clusters), and then one of these clusters is randomly selected as the sample. Such an approach can be advantageous for performing market research and constructing geographical clusters to minimize travel time when conducting interviews.

For small cluster sizes, you can achieve privacy amplification via cluster sampling. However, as the cluster sizes grow, the amplification degrades, to the point that eventually there will be no additional privacy advantage. Further, if the clusters are sufficiently different from one another, then a private algorithm can infer which data points are in the sample, meaning that there is negligible advantage from privacy of the sample. ² This is still an active area of research at the time of publication. Privacy amplification by subsampling also appears in Chapter 7, where a mathematical justification for why this technique improves privacy in the case of a simple sample is discussed.

Metadata Parameters

There are decisions that affect utility as well as privacy, and these can be made by both the data curator and data analyst. One example of this is metadata parameters, such as inputting ranges for numerical variables and categories for categorical variables.

Why are data curators and analysts asked to input these metadata parameters? Datasets in the wild may have an infinite range or set of categories; this means the sensitivity of statistics computed on this data could be unbounded, which can pose a problem for maintaining the privacy guarantee. Therefore, many DP algorithms require the inputs to be bounded, or for the curator/analyst to set a bound to which the inputs can be clipped, in order to bound the privacy loss of the release.

However, these bounds and categories must be data-independent; they cannot be taken straight from the dataset, but rather should come from knowledge about the data domain and its collection. For example, the range for an “age” variable should not be the min and max of ages in the dataset, but rather $[0,110$] (for a dataset potentially containing any human) or $[0,18$] (for a dataset on children). Similarly, the categories for an “education” variable should not simply be those present in the dataset, but should come from a codebook of educational levels for this data domain.

Selecting these parameters independently of the dataset is critical for maintaining the desired privacy guarantee. However, these parameters also impact data utility. Ranges or categories that are too limited may introduce more bias into the statistic, but parameters that are too broad may introduce more variance into the statistic. Therefore, while the data curator is responsible for choosing these parameters, due to their high knowledge of the data domain, data analysts are typically also able to tune these parameters to achieve their bias-variance goals.

Allocating Privacy Loss Budget

Once the data curator has decided on privacy-loss parameters for the release, i.e. the global privacy-loss budget, the curator can then allocate this budget amongst different releases and analysts. For example, the curator may want to use 50% of the budget to do an initial DP release of basic summary statistics about the data set, such as histograms of key variables. The other 50% can then be allocated amongst analysts at different institutions, who can request additional statistics beyond the initial release.

Analysts, too, are responsible for allocating their portion of the privacy-loss budget amongst different statistics. There are different ways to do this: one can divide the privacy-loss portion equally across the statistics, spend more of the budget on statistics that provide richer information (such as sufficient statistics) or context (such as CDFs of variables), or allocate the budget in order to satisfy accuracy goals. For the latter option, some tools allow the analyst to “fix” the desired accuracy of some statistic, such as the size of the 95% confidence interval around a DP mean, and will automatically compute the correct allocation of privacy loss budget in order to achieve this goal.

There are three key challenges with allocating a privacy-loss budget. First, curators and analysts must contend with the inevitable tradeoff between privacy and accuracy; the more the budget is split across analysts and statistics, the lower the accuracy will be for each individual analysis.

Second, the allocation of the budget must be done prior to the release / computation of the DP statistics. This may make it hard to do exploratory data analysis, as it may be unknown a priori which statistics are more important and informative for the goals of the analysis. We will discuss this later in “Making these Decisions in the Context of Exploratory Data Analysis”.

Third, the privacy-loss budget is a finite resource - it must be shared across data users. This means that the allocation of the budget is a visible policy choice on the part of the data curator. This transparency makes it easier to solicit feedback around which data users may benefit from a larger share of the budget, but it may also make these decisions more contentious as stakeholders begin to view allocation as a zero-sum game. We will discuss this more in the conclusion of the chapter.

Practices that Aid Decision-Making

As we’ve discussed, there are many decisions that go into the DP data curation and analysis process. Making these decisions can feel overwhelming, especially because you will get only one (or limited) shots to analyze the data. Remember that any do-overs will result in additional privacy loss. In this section, we therefore discuss data practices that will help you make the best decisions possible. These practices start even before the process of data collection and extend throughout data analysis and distribution.

Making these Decisions in the Context of Exploratory Data Analysis

Although the section above has provided approaches for when you, as a data curator or analyst, have detailed information about the context, you may end up asking yourself, “how do I start with the analysis?” It is a challenge to perform exploratory data analysis (EDA) safely and release summary information early on, while still rationing your budget so that you have enough left for the remainder of the analysis. In many ways, these topics are the hardest part of a DP project.

There are two main challenges of selecting parameters in the context of exploratory data analysis. First, you may not know what statistics to release, and the choice of statistics itself may be disclosive. Second, you may have little information about metadata parameters, such as ranges or categories, for the statistics you would like to release.

Let us consider the first problem of choosing statistics in a privacy-preserving way. In many cases, the goal of working with the data will be to explore what is even interesting or relevant to release. Making these data-dependent decisions about which statistics to release in the first place can require a dedicated privacy-loss budget. The problem here is to permit “access to the raw data, while ensuring that the choice of statistics is not disclosive.” ¹¹ If this choice of statistics is differentially private, then you “can release these privately chosen statistics using privacy-preserving algorithms.”¹² One solution, proposed by Dwork and Ullman, is for an analyst to (forgetfully) performs EDA on independent slices of the data to come up with the statistics they would like to release. Here, “forgetfully” means they run the same EDA process on each slice, trying their best to forget what they learned in between. Then, they apply a DP mechanism such as Exponential mechanism over all the sets of statistics to choose which ones to release.

Second, let us consider how to choose metadata parameters when you have little context about what they might be. There are two approaches for doing so.

First, you can train on public data. For example, say you have a dataset that contains incomes of employees in an industry that you are unfamiliar with. You want to release the mean value of these incomes, but when using DP, this would require providing bounds on the range of the incomes. If you had no idea what these bounds might be, you could turn to publicly available data on historical incomes from this industry and use the inflation-adjusted estimates to supply as your bounds.

Second, there are algorithms that use privacy budget to estimate parameters. You should only use these algorithms if you feel that your own estimates may be way off base. These algorithms often use iterative approaches. For example, in the income example above, you could use a small portion of your privacy budget, say 1/10, to run a DP binary search algorithm to estimate the 5th and 95th quantiles of the distribution of incomes. Then, you can use these estimated quantiles as the input for your DP mean. A second approach is to create a DP histogram over an arbitrary large set of values. The recommendation is to choose the bins and set of values based on the data type — eg. floating point numbers. In this case, the bins are chosen with spacings that increase exponentially as they move away from 0. Noise is added to each count, and then the approximate maximum of the input values is chosen by selecting the most signficant bin whose count exceeds some threshold t, where t depends on your desired probability of not selecting a false positive. ¹³ However, we still recommend that you use your own estimates for the bounds instead of splitting the budget whenever possible.

Using these algorithms still requires some decisions on your end. For example, using the binary search algorithm requires choosing which quantiles to even estimate. For this, we recommend following rules-of-thumb, such as estimating the 5th and 95th quantile, or using logarithmically spaced bins for histograms.

Potential (Unexpected) Consequences of Transparent Parameter Selection

One of the benefits of DP is that it enables transparency around the method used for noise addition, including the many parameters we’ve discussed above that are used within the process. This is great compared to previous approaches of “security-through-obscurity,” where the method itself had to remain secret in order to guarantee protection. However, transparency often brings with it other challenges. Many deployments of DP have disregarded the additional work needed to support transparency, and have suffered the consequences of controversy and critique, so you as a data curator should be aware of the issues that may arise so you can prepare in advance of your deployment.

First, DP creates a zero-sum game between privacy and utility. When you explain DP to data users, you will have to make it clear that there is a strict privacy-utility tradeoff, as well as a finite privacy-loss budget. You should be aware that many data users may not have thought of privacy and utility this way before, so this may be a shocking revelation. Data users that may have worked together before will now be wary that allocating a larger share of the budget to one group diminishes the share of the budget available to other groups. Therefore, asking data users to come to consensus on how the privacy-loss budget should be distributed may be a contentious process. This is exactly what happened during the use of DP in the 2020 Decennial Census, where coalitions of data users fell apart because of the zero-sum game they were suddenly asked to participate in through the use of DP. ^{14 15}

This should not discourage you from being transparent about DP. Transparency and accountability are important benefits of using DP compared to prior approaches to disclosure avoidance. Nonetheless, you should be prepared to justify how all the decisions are made regarding the setting of the privacy-loss budget and the allocation of the budget amongst data users. Before advertising that data will be made available to data users using DP, you may consider setting a policy around how much budget will be used for internal research and/or trusted partners. Then, to allocate the rest of the budget, you might consider using a formal process where data users submit anonymous applications asking for a portion of the budget, and you use a third-party service to make these decisions as objectively as possible. On the other hand, if you would like collective engagement from data users on these decisions, you should set up modes of communication that mitigate the antagonistic aspects of this decision, such as building these agreements based on personal relationships and emphasizing shared goals.

Throughout this process, you will have to communicate to stakeholders about what the privacy-loss parameters actually mean for their contexts. This is no easy task. The challenges of explaining these parameters is well-documented ¹⁶; there are many ways in which stakeholders may misunderstand them. Data users who have more sophisticated statistical background may be better positioned than those without, which can make it hard for them to come to a consensus together. Across the board, stakeholders may not be used to reasoning about probabilistic risks.

Although research into communicating privacy-loss parameters is still nascent, emerging research ¹⁷ suggests that “odds-based explanation” methods can be effective in communicating about these parameters. This may look like the following text:

“If a data subject does respond to a true/false survey question, [x] out of 100 potential DP outputs will lead an analyst to believe that the data subject responded with [true].” “If a data subject does not respond to a true/false survey question, [y] out of 100 potential DP outputs will lead an analyst to believe that the data subject responded with [true].”

Other approaches include frequency visualization and sets of sample DP outputs. Visualizations, in particular, are underexplored in the DP literature and may be incredibly beneficial in communicating with data subjects and data users. Hands-on explainers (such as this notebook by OpenDP: https://docs.opendp.org/en/stable/user/programming-framework/a-framework-to-understand-dp.html#Distance-Between-Distributions---Divergence) can also be valuable for data scientists. Regardless of what approaches you use, you should remain sensitive to how challenging it is for stakeholders to evaluate these parameters and set expectations accordingly.

As a data curator, you will need to understand the relationship between your data’s privacy needs and the privacy-loss parameter values you choose. The choice of privacy-loss parameter values is key to protecting the privacy of subjects in the data set. As a data curator, this is also your responsibility, and may exist in tension with the desire to extract utility from the data for research or commercial purposes. Further, you will need to understand how to choose metadata parameters without regard for the values in the underlying data set. This decision also impacts the utility of the DP data analysis - for example, clamping values to an inappropriate range can lead to flawed statistics. By now, you should have a solid enough theoretical understanding of DP as a practice to be able to curate sensitive data in a way that results in useful DP statistics.

However, DP data curation doesn’t exist in a vacuum, instead, it is part of a network of researchers and institutions hoping to glean useful information from sensitive data. Since differential privacy leads to a trade-off between utility in privacy, this practice can lead to friction between competing interests. Beyond understanding the theory of DP, it is important that you, as a data curator, can also navigate the personal and professional implications of allocating a DP budget. In this chapter, you have learned several techniques for mitigating such friction - including effective communication of privacy budget allocation and the potential to use third party organizations to anonymously process DP budget requests. Remember that a significant part of the data curation process may rest on personal relationships, and allocating budget with a commitment to shared goals, as well as publishing contextual DP statistics as metadata can help to minimize contentiousness and make the DP data analysis process more productive for everyone.

In the next chapter, you will take your new knowledge of privacy-loss parameters, metadata parameter selection, and the organizational challenges of DP data curation, and learn how to secure your sensitive data against common privacy attacks. In particular, when choosing privacy loss parameters and allocating budget, you should have vulnerabilities in mind. Understanding these attacks will help you make responsible decisions as a data curator and serve a useful purpose as cautionary tales when communicating with data analysts.

Exercises

1. Consider a personal trainer app that tracks exercise and health habits. How could this app violate contextual integrity, when compared to a human trainer?

2. Take the following function and generate a dataset with unknown bounds

import random

def random_distribution():
    samples = []
    for i in range(200):
        sample = random.uniform(-1e9, 1e9)
        samples.append(sample)
    return samples

1. Suppose you have a maximum privacy loss budget of $ϵ=4$.

   1. How would you define and explain your choice of $\delta$?

   2. How do you divide your budget between data exploration and data analysis?

   3. If this data set is referring to markers in blood tests, how do you define your data bounds?

      1. Explain how your choice of sampling method can effect the privacy-utility tradeoff.