Abstract
Modern society generates an incredible amount of data about individuals, and releasing summary statistics about this data in a manner that provably protects individual privacy would offer a valuable resource for researchers in many fields. We present the first algorithm for analysis of variance (ANOVA) that preserves differential privacy, allowing this important statistical test to be conducted (and the results released) on databases of sensitive information. In addition to our private algorithm for the F test statistic, we show a rigorous way to compute p-values that accounts for the added noise needed to preserve privacy. Finally, we present experimental results quantifying the statistical power of this differentially private version of the test, finding that a sample of several thousand observations is sufficient to detect variation between groups. The differentially private ANOVA algorithm is a promising approach for releasing a common test statistic that is valuable in fields in the sciences and social sciences.
I. INTRODUCTION
The goal of private data analysis is to gain useful information from databases of personal information while at the same time protecting the privacy of the individuals in the database. This has traditionally been done using ad hoc "anonymization" techniques, but in recent years these techniques have failed on numerous occasions (ex., [1] - [3] ). Differential privacy [4] has emerged as a rigorous framework for providing provably strong privacy while publicly disseminating useful information about a data set.
I. INTRODUCTION
Differential privacy is not a method for producing publishable output, but rather a sufficient condition that guarantees privacy is protected with the level of protection parameterized by a parameter . In order to satisfy differential privacy, the information being published (generally summary statistics) must in some way be randomized. In the simplest query algorithms, random noise is added to the correct (but not necessarily private) output. The result is often a good estimate of the true value. Some schemes are more complicated, adding noise in various ways during a computation. Differentially private algorithms have been created to allow for the release of simple summary statistics like means [4] and medians [5] , [6] , as well as more elaborate statistical output, including histograms [4] , linear regressions [5] , [7] , [8] , chi-squared tests [9] and a variety of machine learning techniques.
I. INTRODUCTION
In this paper, we present the first differentially private algorithm for conducting a one-way analysis of variance (ANOVA). This is a statistical test for settings with a categorical independent variable and a continuous dependent variable. It is a very widely used piece of statistical analysis and is used as the primary test of significance for many studies in biology, medicine, and the social sciences.
I. INTRODUCTION
A one-way ANOVA outputs a test statistic called an F statistic, which measures the ratio of the variation in means of categories to variation of individual observations. Our algorithm outputs an estimate of this value. However, F statistics are not of interest directly, but rather as a tool for measuring statistical significance of the result. One cannot simply look up our noisy estimate of F in an F -distribution table to find a p-value, because the noise makes extreme values more likely than they would otherwise be.
I. INTRODUCTION
Our second contribution is to give a rigorous method for computing p-values. This means that our algorithm produces final results that can be easily interpreted. (Most existing algorithms do not output these sorts of results. For example, algorithms for linear regression output only the best fit line, which is useful for making predictions but not sufficient for testing independence of two variables.)
I. INTRODUCTION
Finally, we run a series of experiments to measure the statistical power of our algorithm. That is, for a given privacy parameter and effect size, we show the required size of the database for the algorithm to indicate a statistically significant result. This provides a quantitative analysis of the utility-privacy tradeoff under our algorithm and provides a basis against which to compare future algorithms that might seek to improve upon this work. Our code is freely available at https://github.com/campbza/ Differentially-private-ANOVA.
II. BACKGROUND
Below we provide technical background on the two main topics of our paper, differential privacy and the ANOVA statistical test.
A. Differential Privacy
Imagine your data is part of a database about which some information is released. Intuitively, differential privacy guarantees that the published output would be similarly likely regardless of the specific values of your data. If the output is similarly likely regardless of your data's value, then someone seeing that output is unable to meaningfully infer anything about you. (This inability to learn from the output has been formalized and proven to be a consequence of differential privacy. See [10] for more details.) Differential privacy was introduced by Dwork et al. in 2006, and the core definition and theorems presented below were all present in that initial work. [4] Formally, we consider two databases D and D , each consisting of n rows. (A "row" consists of all information connected to a given record.) We say D and D are "neighboring" if they are the same except for one altered row. A function f on the database is said to be differentially private if the probability of any output of f is roughly the same for any neighboring inputs D and D .
A. Differential Privacy
Definition 1 (Differential Privacy). A (randomized) algorithm f with range R is -differentially private if for all S ⊆ R and for all neighboring databases D and D
A. Differential Privacy
We call the privacy parameter, which is chosen by the user. Differential privacy has many useful properties. Some, like those mentioned above, guarantee that it really is sufficient to guarantee privacy. Others allow for easier creation of private algorithms and easier use of those algorithms in practice. Two properties in particular will be useful to us here.
A. Differential Privacy
Theorem 1 (Composition). If f is 1-differentially private and g is 2-differentially private, then if h simply returns the outputs of both f and g (i.e., h(D) = (f (D), g(D))) then h is ( 1 + 2)-differentially private.
A. Differential Privacy
We will use this property to combine algorithms for intermediate calculations into an algorithm for ANOVA as a whole. It also means that our ANOVA algorithm can be combined with other differentially private algorithms to conduct larger, more complex statistical analyses.
A. Differential Privacy
The other useful property is resistance to post-processing:
A. Differential Privacy
This property is primarily a sanity check on the definition, since a good definition of privacy must have this property. In our case, it also means that our process for converting a noisy F statistic into a p-value maintains privacy.
A. Differential Privacy
We build our algorithm by using the standard Laplacian mechanism for individual components and then combining the result. This technique relies on knowing the sensitivity of certain computations. This sensitivity is defined as the maximum effect that can occur when a single row is changed.
Definition 2 (Sensitivity). The sensitivity of a (deterministic) function f on databases with real number outputs is the maximum over neighboring databases
We also define the Laplace distribution, for which this technique is named:
and has probability density function
We can now give the Laplacian mechanism, which gives a differentially private algorithm for any function with a known bound on sensitivity.
and has probability density function
Theorem 3 (Laplacian mechanism). Let f be a function with sensitivity at most s. Let L be a random variable drawn from Lap(s/ ). Then the function f (D) = f (D) + L is -differentially private.
B. ANOVA Testing
A one-way analysis of variance (ANOVA) evaluates whether the data is consistent with a null hypothesis under which all groups of the categorical variable share the same mean for some continuous response variable [11] . For example, it might test whether a choice of treatment (ex., surgery, medication, or none) had an effect on the mean life expectancy of patients with a particular disease. Deviation from the null hypothesis is measured with an F statistic. If the resulting F statistic is sufficiently unlikely to occur under the null hypothesis, the analyst can safely conclude that average response is not independent of group membership.
B. ANOVA Testing
A database D for an ANOVA test contains n rows, each containing a categorical variable that takes on one of k allowed values and a continuous variable. (We will throughout this paper assume that the continuous variable has been normalized and has allowed range [0, 1].) We let yij represent the j th row in category i. We let yi represent the mean of group i, and y represent the grand mean (i.e, the mean of all values). We let ni be the number of values in group i.
B. ANOVA Testing
An ANOVA test produces an F statistic. This can be calculated from two intermediate values. First is SSA, the sum of the squared error of all sample means compared to the grand mean weighted by the size of each group. This measures the variation between the means of each group.
B. ANOVA Testing
The second intermediate value is SSE, the sum squared error of all values compared to the grand mean. This measures the variation among the data points as a whole.
B. ANOVA Testing
The F statistic compares these two values. Intuitively, if all groups are distributed identically, then the random variation between groups should scale proportionately to the variation in individual values. If the groups have different means, SSA will grow faster than SSE. Therefore F is a ratio of SSA to SSE, with each adjusted to account for their respective degrees of freedom.
B. ANOVA Testing
When sample sizes are large, the distribution of the F statistic under the null hypothesis (given known values of k and n) is wellknown. Given a particular F statistic, one can compute the probability that a value that high or higher would have occurred by random chance if the null hypothesis was true. This is the p-value. A low p-value (often 0.05 or less) is seen as "significant" and is taken as reasonable evidence that the null hypothesis can be rejected.
III. OUR ALGORITHM
Our algorithm uses the Laplacian mechanism defined previously. In order to do so, we first prove sensitivity bounds on our queries. We assume all data has been normalized so that yij values fall in [0, 1] and that the number of possible groups k is fixed and public, but the number of samples from each group is not known. The most straightforward approach would be to bound the sensitivity of F , but this is very difficult. Instead we bound the sensitivity of SSA and SSE.
III. OUR ALGORITHM
Theorem 4. Recall that
III. OUR ALGORITHM
SSE has sensitivity bounded above by 7.
III. OUR ALGORITHM
Proof. We must analyze the effect of changing a single data point on SSE. There is a term in the sum for each data point, each with a value in [0, 1]. The term corresponding to the changed data point might change arbitrarily, so we bound this term's contribution to the change by 1.
III. OUR ALGORITHM
Next we look at the effect that change has on the other terms through its effect on yi and yj, where the data point's change moves it from group i to group j. (This is the worst case -changes that don't change the rows groups would have lesser effect.) Let ni and nj be the number of terms (i.e., data points) in each group excluding the data point being changed. We can bound the change's effect on yi by 1/ni. We are are therefore changing the value being squared in each term, yij − y i , by at most 1/ni. In general, if you change a 2 to (a + b) 2 , the change is 2ab + b 2 . Here we have a = yij − y i ≤ 1, so we can bound this by 2b + b 2 . Plugging in b = 1/ni gives us a per-term change of 2/ni + 1/n 2 i .
III. OUR ALGORITHM
We then have ni terms affected by this change, for a total effect of 2 + 1/ni < 3.
III. OUR ALGORITHM
Similarly, the effect on the terms in group j is bounded by 3. This gives us a change of at most 1 for term corresponding to the row being changed and a change of at most 3 for each of the two groups of other terms this row affects, for a total sensitivity of 7.
III. OUR ALGORITHM
The sensitivity of SSA is bounded above by 9 + 5/n.
III. OUR ALGORITHM
Proof. This proof follows the same logic as the previous one. Instead of thinking of k terms, each weighted by ni, think of the sum as n terms, with each group resulting in ni identical terms:
III. OUR ALGORITHM
Again, the term corresponding to our changed data point can change by 1. Other terms in group i see yi changed by 1/ni and y changed by 1/n. Again this is a change from a 2 to (a + b) 2 but this time b = 1/ni + 1/n. This gives us a per-term change of: 2(1/ni + 1/n) + (1/ni + 1/n) 2 =2/ni + 2/n + 1/n 2 i + 2/nni + 1/n 2
III. OUR ALGORITHM
We then sum this per-term change over ni terms to get a change of 2 + 2ni/n + 1/ni + 2/n + ni/n 2 ≤ 3 + 2ni/n + 2/n + ni/n 2
III. OUR ALGORITHM
There is an identical bound on the total change in the terms representing group j, the group the data is moving to. Then we consider the other terms. Say n * represents the number of terms not in either of these groups. Each of those terms sees y change by at most 1/n. With b = 1/n we get a total change of 2n * /n + n * /n 2 . We then add together those four separate bounds: the bound of 1 on the term's own change; the bound on the total change of terms in group i; the equivalent bound on change in group j; and the bound on the rest of the terms. Given that ni + nj + n * < n, this is bounded by 9 + 5/n.
III. OUR ALGORITHM
Using these sensitivity bounds it is straightforward to construct our algorithm. We compute estimates SSE and SSA of SSE and SSA using the Laplacian mechanism, then combine the results to estimate the F statistic. See Algorithm 1 for formal details.
III. OUR ALGORITHM
Output: F , SSA, SSE
III. OUR ALGORITHM
We now prove that this algorithm is -differentially private.
III. OUR ALGORITHM
Theorem 6. Algorithm 1 is -differentially private.
III. OUR ALGORITHM
Proof. By the sensitivity bounds of Theorems 4 and 5 and the known Laplacian mechanism (Theorem 3) we know that the computations of SSA and SSE are each /2-differentially private. By our composition theorem (Theorem 1), outputting both is -differentially private. Finally, since the computation of F does not require access to the database, Theorem 2 shows that it can be added to the output without loss of privacy.
III. OUR ALGORITHM
Note that while F is the value of most immediate interest, we can also output SSA and SSE without additional privacy loss. These values can sometimes give other useful information about the database "for free." For example, SSE/(n − k) is an estimate of the variance of the data, which might be of independent interest.
A. Computing p-values
Normally in an ANOVA test we get a value for F . We can then refer to the known F -distribution to find the p-value, the probability that the observed value, or more extreme, would have occurred by chance under the null hypothesis. The higher the F -ratio, the lower the p-value. However, our algorithm returns an approximation, F , of the real F value. One could simply compare this value to the F distribution and get an approximation of the true p-value, but one could also be more thorough and actually compute a distribution for F values under the null hypothesis and compare to that distribution. We do the latter.
A. Computing p-values
Under the null hypothesis, SSA is drawn from σ 2 χ 2 k−1 , the chisquared distribution with k − 1 degrees of freedom scaled by the variance σ 2 . SSE is similarly drawn from σ 2 χ 2 n−k . In the classic setting, the σ 2 factors cancel in the ratio, making the F distribution independent of the variance of the underlying data points. This is not true in our scenario. SSE is drawn from σ 2 χ 2 n−k + Lap(7/( /2)). The added Laplacian noise makes the resulting ratio dependent on σ 2 . Luckily, SSE/(n − k) is an estimate of σ 2 , and we can use this estimate to accurately compute a distribution for F .
A. Computing p-values
To simulate a null hypothesis F distribution we choose SSE and SSA from the above distributions, using SSE/(n − k) as our estimate of σ 2 . We repeat this a large number of times (100,000 in our experiments).
A. Computing p-values
When we see an output of Algorithm 1, we use the reported SSE value to compute the above distribution for F under the null hypothesis. Then we look at the percentage of that distribution falling above the particular value we saw for F and return that as our p-value. Note that this entire computation of p-value is done independently of the database, using only the output of Algorithm 1. Therefore it can be added to the algorithm as an additional output with no added privacy cost. Fig. 1 . The distribution of the F statistic (red) overlaid with distributions of the estimate F for two values of (green and gold). In all cases, n = 10, 000 and k = 10. The significant difference between these curves indicates that even though F is an estimate of F , ignoring the added noise in F produces unacceptably inaccurate conclusions.
A. Computing p-values
One of our key findings is that this added care in computing the p-value is absolutely necessary. Consider the distributions shown in Figure 1 . Here we have shown the standard F distribution when n = 10, 000 and k = 10, along with distributions of the estimate F when = 1 and when = 0.1. The dotted line shows the value of the F statistic that would normally indicate statistical significance with p = 0.05. However, at this point with = 1 the true p-value we calculate is 0.13. With = 0.1 the true p-value at that point is 0.41.
IV. RESULTS
We assessed the power of our differentially-private ANOVA test on synthetic data as we increased the database size n for different privacy parameters . We generated normally-distributed data from three equally-sized groups with the same standard deviation and three different means. That is, the n values were comprised of n/3 values drawn from N (0.35, 0.15), n/3 values drawn from N (0.5, 0.15), and n/3 values drawn from N (0.65, 0.15). Values were truncated to be within [0, 1]. We calculated estimates SSA, SSE, and F , and computed the p-value as described in Section III-A. We repeated this procedure (data generation, private ANOVA test, and p-value calculation) 1,000 times for (n, ) pairs and recorded the proportion of iterations that report a p-value less than 0.05.
IV. RESULTS
For our simulated datasets, we selected databases ranging from ten records to one million records, and privacy parameters ranging from = ∞ (non-private) to = 0.01. The choice of an "acceptable" value is a policy question: = .01 is extremely conservative and allows for safe composition with many other queries, while = 1 provides meaningful privacy protection but might be too high for the comfort of some.
IV. RESULTS
The power curves in Figure 2 quantify the number of records needed to consistently yield statistically significant results for (n, ) pairs. In the non-private case (when = ∞), databases with 100 records yield consistently significant F values over the 1,000 runs. As the value of decreases, more records are required to provide statistically significant results; with = 1 five to ten thousand data points are needed to frequently see significance, while nearly one million records are required when = 0.01.
IV. RESULTS
Whether these results are exciting or disappointing depends very much on one's reference point. On the one hand, databases with several thousand values are extremely common, meaning that we can now conduct ANOVA tests on a wide variety of real-world databases while protecting privacy, something that was not previously possible. On the other hand, the differentially private version is substantially less powerful than the traditional non-private version. We also verified that SSE/(n − k) is a sufficiently accurate estimate of σ 2 for the calculating p-values. We did this by running the experiment a second time using the ground truth variance (0.15 2 ) in the null distribution generation; this would be impossible in the real world (where the true σ 2 is not known), but it is guaranteed to give accurate p-values. The result (Figure 3) is extremely similar to our results using the estimated σ 2 , giving us confidence that this estimate is acceptable for real world use.
IV. RESULTS
Next, we evaluated the differentially-private F -ratios on data with a smaller effect size. We generated six groups of values with means [0.4, 0.45, 0.5, 0.5, 0.5, 0.6] and standard deviation 0.2, and again truncated values to be within [0, 1]. We computed the proportion of significant p-values as before. The increased number of groups and the closer group means shift the power curves to the right (Figure 4 ), but even in this setting, a database size on the order of 10,000 would yield frequently significant p-values for privacy parameter = 1.0.
V. CONCLUSION AND FUTURE WORK
We show that for practically-sized databases, one can execute differentially private ANOVA tests with reasonable privacy guarantees and convincing results. We also quantify exactly how much data is needed to pick up an effect of a given size. This is an important practical tool for data collection and analysis. Perhaps more importantly, it gives a clear measurement of the efficacy of our algorithm in real world terms, allowing for easy comparison between this work and future attempts to improve the power of differentially private ANOVA testing.
V. CONCLUSION AND FUTURE WORK
This project is only a small step into what is a very large area for exploration. There are other techniques for differentially private algorithms that might yield more powerful results. We made some attempts to use the propose-test-release framework of Dwork and Lei [5] or the smooth sensitivity framework of Nissim et al. [6] . These attempts gave us less effective algorithms than the one presented here, but it is certainly possible that further work could find a better algorithm.
V. CONCLUSION AND FUTURE WORK
We hope that presenting algorithms for differentially private equivalents of frequently used statistical tests will make it easier for practitioners in other fields to make use of differentially private analysis and allow the useful study of data that was otherwise inaccessible to researchers.

{'paper_id': '3391557', 'title': 'Differentially Private ANOVA Testing', 's2_url': 'https://api.semanticscholar.org/CorpusID:3391557', 'source': 'S2ORC'}