APEx: Accuracy-Aware Differentially Private Data Exploration
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Ge, Chang
He, Xi
Ilyas, Ihab
Machanavajjhala, Ashwin
Organizations are increasingly interested in allowing external data scientists to explore their sensitive datasets. Due to the popularity of differential privacy, data owners want the data exploration to ensure provable privacy guarantees. However, current systems for answering queries with differential privacy place an inordinate burden on the data analysts to understand differential privacy, manage their privacy budget, and even implement new algorithms for noisy query answering. Moreover, current systems do not provide any guarantees to the data analyst on the quality they care about, namely accuracy of query answers. We present APEx, a novel system that allows data analysts to pose adaptively chosen sequences of queries along with required accuracy bounds. By translating queries and accuracy bounds into differentially private algorithms with the least privacy loss, APEx returns query answers to the data analyst that meet the accuracy bounds, and proves to the data owner that the entire data exploration process is differentially private. Our comprehensive experimental study on real datasets demonstrates that APEx can answer a variety of queries accurately with moderate to small privacy loss, and can support data exploration for entity resolution with high accuracy under reasonable privacy settings.
 I'm going to talk about APEX, accuracy-aware, differentially private data exploration. This work is a joint work with Professor Xi He from Waterloo when she was a student at Duke, with my advisor, Professor Ehab Elias, and with Professor Eswin from Duke University. Data exploration is an important prerequisite for many data-oriented tasks. Due to the magnitude and the diversity of the problem set and the data set, there is no turn-case solution to fit all. Most of the time, the data owner needs to hire a data analyst in the loop to tune a solution. For example, consider a medical database and the data analyst wants to predict the trend for particular disease. This process starts with exploring the data. Data exploration usually involves operations such as building histograms, top-key lists, summarization, profiling, and these insights can be used to tune complex motion learning and data analytics workflows, for example, to tune a deep neural network to predict the disease trend. However, when data contains sensitive information and is stored behind the firewall, due to privacy concerns, the data owner does not and cannot trust the analyst to freely explore the data. Because of the fundamental law of information recovery, the analyst can reconstruct the data set by asking too many queries. So in this setup, private data exploration becomes a problem. With recent advances in differential privacy, differential privacy provides a practical definition on guarantee the privacy of any individual records in its database. So it provides the opportunity for the data owner to set a privacy budget to bound the total information leakage. So in this way, the analyst submit queries and the privacy costs are epsilon, and the data owner tests whether the epsilon is smaller than the privacy budget and returns a noisy answer to the analyst. So using differential privacy, then the data owner can bound the total information leakage and the data owner becomes happy. But this solution requires a lot of burdens on the data analyst, for example. It requires the data analyst to understand differential privacy, understand the different mechanisms, know how to portion the privacy budget. So in other words, this requires the analyst to be the differential privacy expert. Even though she is, journal purpose DP systems does not provide an interpretable accuracy guarantee which the analyst cares about. So using this, the analyst is not that happy. So let's think a bit, what do the analysts and the owner really care about? The owner cares about to, wants to bound the total information leakage, while the data analyst cares about queries and the accuracy because of a privacy. Why not we let both of the parties express their concerns directly to a system and this system takes the privacy budget from the owner, takes the query, takes the accuracy tolerance from the analyst, compile them together and automatically provide accuracy guarantee for the data analyst and the privacy guarantee to the owner. The key idea of a SAS system is to translate accuracy tolerance to differential privacy mechanism. If we can have a SAS system, then exploring private data became practical and both parties, they can be happy. Apex is a SAS system. Apex takes the exploration query and the accuracy requirement from the analyst and the accuracy translator translates the input into differential privacy mechanism with a minimum privacy cost and run the mechanism on the private data and get the true cost and return the answer to the analyst. On the other side, it takes the privacy budget in differential privacy and the privacy analyzer ensures the overall data exploration satisfy differential privacy within that budget. Then you might want to ask why designing Apex is challenging? Well, for the accuracy analyzer, giving a query and accuracy requirement, the goal is to find a DP mechanism with the least privacy cost. In fact, this goal is intractable for complex queries. And some DP mechanism can have error which that is data dependent. And because of this, the best DP mechanism for query depends on the data. For the privacy analyzer, because of the data dependent mechanisms, the privacy loss of the individual queries can be data dependent too. So bounding the privacy loss of the overall interaction becomes non-trivial. So in our paper, we provide a formal proof using Apex that this exploration satisfy differential privacy. And in this talk, I'm going to focus the challenges related to the accuracy translator. Okay, so although the goal is intractable, as the first step, we identify three types of queries and define the accuracy requirement. All these can be modeled using this syntax, B and D on F, F is accuracy function, where W is the list of predicates. Depending on the query type, the analysts can also express having and all the byte clause. And the accuracy requirement is expressed as error alpha and the confidence of one minus beta. So alpha is the accuracy tolerance and beta minus the confidence level, which is a probability that an error can happen. These three types of queries are far from the complete set of operations in data exploration, but we believe they provide a rich semantics and can capture some of the most commonly used operations in data exploration, such as histogram, top key list, and the threshold testing. And meanwhile, those queries are well studied in the DP literature, and we can translate those queries using well-known differential privacy mechanism. So the first query is a workloading counting query, and it returns a set of noisy cons. If the analyst wants to select the population of all the US states, then she can express the query looking like this. So the accuracy requirement here means that the probability that the maximum noise added to the cons greater than alpha is smaller than beta. We can also define an ASPRA counting query, and it returns a set of predicates that satisfy the threshold. If the analyst wants to select the states which has population greater than one million, then she can express by having cons greater than one million. So the accuracy requirement can be defined like this. Suppose this scales the cons, and each of the points represent the population of a different state, and this is your threshold. Because of adding noise, some of the states are only labeled as a population smaller than C, and some of them are only labeled as a population greater than C. And here, this is your accuracy tolerance. The accuracy requirement states that beyond this minus plus alpha range, there is no error with high probability of one minus beta. Similarly, a top key queries can be defined. So when translating a query and an accuracy to differential private mechanism, different mechanisms can result at different privacy costs. So here are two examples from our benchmarking queries. And if you use Laplace mechanism, the difference can be 100x different. And if you consider the QW2, using Laplace mechanism, Laplace mechanism, the privacy cost is over 10x worth. Because some of the mechanism are data-independent mechanism, and translating queries, translating into data-independent mechanism is easy, because the privacy cost only depends on the query. Some mechanisms are data-dependent mechanism, whose privacy cost, whose true privacy cost actually depends on the data. So consider an example. Suppose the query is a single model attendance more than 100, and the accuracy specified is alpha 10, beta is 10 to the negative five. Using Laplace mechanism, the privacy cost epsilon is log 1 over 2 beta, outside over alpha is 1.08. And graphically speaking, this is your count, and this is the threshold 100. Suppose you know the true count, the true attendance of 1000 here, and this is your alpha, and this range, that's your noisy count. And you can see from this query, the noisy answer to this query is yes. Can we reduce the privacy cost without changing the answer? Well, in fact, we can relax alpha up to 900 without affecting the answer. If we set alpha as 900, then the privacy cost is reduced from 1.08 to 0.012, which is a big save. However, this approach will require you to know this true value, which is not possible upfront. Alternatively, we propose a multi-poking mechanism. And the idea is, the idea is you poke with increasing privacy budget. At the beginning, you set a small privacy budget and test whether the noisy count is surfacing a lot than the threshold. If no, then you increase the privacy budget and test again, until you find a large enough accuracy tolerance. So this is an example, this multi-poking mechanism is an example of data dependent mechanism. Bear this in mind, so the best mechanism for query depends on the data and the query. So Apex supports a set of mechanism for different queries. And we let Apex to choose, for giving a query an accuracy, we let Apex to choose the best one, and I will skip the detail for this. We did a lot of evaluations using benchmarking queries, and to summarize the key findings here, Apex can effectively translate the queries with accuracy requirement into DP mechanisms, and all queries can be answered with moderate to low privacy cost. As we empirically show that there is no universal best mechanism and Apex can automatically choose the optimal one. Another evaluation I would like to highlight is we can express a full data exploration workflow using Apex. So, antitrolution is a process to identify duplicated records that refers to the same entity in the real world. And we can express a antitrolution strategy using the queries supported by Apex. For example, in a potential antitrolution strategy, the data analyst wants to test the quality of similarity predicts. For example, how many duplicated record can this similarity predicts capture? And this question can be answered by WCQ, for example, using Apex. We did a lot of experiments by varying privacy budget, varying query accuracy, varying data size, and I just want to show you one of them. So, in this, the x-axis represents the privacy budget, and the y-axis represents this recall. When you give a small privacy budget, only few queries can be answered. So, the analyst does not have enough information to tune this workflow. Increasing the privacy budget allows more interactions for the data analyst, and therefore, the data analyst can get more insights from the data and better tune this strategy. Apex can allow antitrolution to reach good quality with reasonable privacy cost. For example, when you set the privacy budget as one, the recall is more than 95%. To summarize, we want to solve the challenge of between data owner and the data analyst when exploring private data set. And we designed Apex to let the data owner and the analyst express their concerns naturally so that both parties, they can focus on their own business in the most natural way. And Apex translates accuracy requirement into differential private mechanisms, and we empirically show that Apex can achieve high exploration quality with reasonable privacy cost. And that's all for my talk, and thanks you for your attention. I would like to take questions. Thank you.
 I'm going to talk about APEX, accuracy-aware,  differentially private data exploration.  This work is a joint work with Professor Xi He  from Waterloo when she was a student at Duke,  with my advisor, Professor Ehab Elias,  and with Professor Eswin from Duke University.  Data exploration is an important prerequisite  for many data-oriented tasks.  Due to the magnitude and the diversity  of the problem set and the data set,  there is no turn-case solution to fit all.  Most of the time, the data owner needs  to hire a data analyst in the loop to tune a solution.  For example, consider a medical database  and the data analyst wants to predict  the trend for particular disease.  This process starts with exploring the data.  Data exploration usually involves operations  such as building histograms, top-key lists,  summarization, profiling, and these insights  can be used to tune complex motion learning  and data analytics workflows, for example,  to tune a deep neural network to predict the disease trend.  However, when data contains sensitive information  and is stored behind the firewall,  due to privacy concerns, the data owner does not  and cannot trust the analyst to freely explore the data.  Because of the fundamental law of information recovery,  the analyst can reconstruct the data set  by asking too many queries.  So in this setup, private data exploration  becomes a problem.  With recent advances in differential privacy,  differential privacy provides a practical definition  on guarantee the privacy of any individual records  in its database.  So it provides the opportunity for the data owner  to set a privacy budget to bound  the total information leakage.  So in this way, the analyst submit queries  and the privacy costs are epsilon,  and the data owner tests whether the epsilon  is smaller than the privacy budget  and returns a noisy answer to the analyst.  So using differential privacy,  then the data owner can bound the total information leakage  and the data owner becomes happy.  But this solution requires a lot of burdens  on the data analyst, for example.  It requires the data analyst to understand  differential privacy, understand the different mechanisms,  know how to portion the privacy budget.  So in other words, this requires the analyst  to be the differential privacy expert.  Even though she is, journal purpose DP systems  does not provide an interpretable accuracy guarantee  which the analyst cares about.  So using this, the analyst is not that happy.  So let's think a bit, what do the analysts  and the owner really care about?  The owner cares about to,  wants to bound the total information leakage,  while the data analyst cares about queries  and the accuracy because of a privacy.  Why not we let both of the parties  express their concerns directly to a system  and this system takes the privacy budget from the owner,  takes the query, takes the accuracy tolerance  from the analyst, compile them together  and automatically provide accuracy guarantee  for the data analyst and the privacy guarantee to the owner.  The key idea of a SAS system is to translate accuracy  tolerance to differential privacy mechanism.  If we can have a SAS system, then exploring private data  became practical and both parties, they can be happy.  Apex is a SAS system.  Apex takes the exploration query  and the accuracy requirement from the analyst  and the accuracy translator translates the input  into differential privacy mechanism  with a minimum privacy cost  and run the mechanism on the private data  and get the true cost and return the answer to the analyst.  On the other side, it takes the privacy budget  in differential privacy and the privacy analyzer  ensures the overall data exploration  satisfy differential privacy within that budget.  Then you might want to ask why designing Apex is challenging?  Well, for the accuracy analyzer,  giving a query and accuracy requirement,  the goal is to find a DP mechanism  with the least privacy cost.  In fact, this goal is intractable for complex queries.  And some DP mechanism can have error  which that is data dependent.  And because of this, the best DP mechanism for query  depends on the data.  For the privacy analyzer,  because of the data dependent mechanisms,  the privacy loss of the individual queries  can be data dependent too.  So bounding the privacy loss of the overall interaction  becomes non-trivial.  So in our paper, we provide a formal proof  using Apex that this exploration  satisfy differential privacy.  And in this talk, I'm going to focus the challenges  related to the accuracy translator.  Okay, so although the goal is intractable,  as the first step, we identify three types of queries  and define the accuracy requirement.  All these can be modeled using this syntax,  B and D on F, F is accuracy function,  where W is the list of predicates.  Depending on the query type,  the analysts can also express having and all the byte clause.  And the accuracy requirement is expressed  as error alpha and the confidence of one minus beta.  So alpha is the accuracy tolerance  and beta minus the confidence level,  which is a probability that an error can happen.  These three types of queries are far from the complete set  of operations in data exploration,  but we believe they provide a rich semantics  and can capture some of the most commonly used  operations in data exploration,  such as histogram, top key list, and the threshold testing.  And meanwhile, those queries are well studied  in the DP literature, and we can translate those queries  using well-known differential privacy mechanism.  So the first query is a workloading counting query,  and it returns a set of noisy cons.  If the analyst wants to select the population  of all the US states, then she can express the query  looking like this.  So the accuracy requirement here means that the probability  that the maximum noise added to the cons greater than alpha  is smaller than beta.  We can also define an ASPRA counting query,  and it returns a set of predicates  that satisfy the threshold.  If the analyst wants to select the states  which has population greater than one million,  then she can express by having cons greater than one million.  So the accuracy requirement can be defined like this.  Suppose this scales the cons,  and each of the points represent the population  of a different state, and this is your threshold.  Because of adding noise, some of the states  are only labeled as a population smaller than C,  and some of them are only labeled  as a population greater than C.  And here, this is your accuracy tolerance.  The accuracy requirement states that beyond this minus  plus alpha range, there is no error  with high probability of one minus beta.  Similarly, a top key queries can be defined.  So when translating a query and an accuracy  to differential private mechanism,  different mechanisms can result  at different privacy costs.  So here are two examples from our benchmarking queries.  And if you use Laplace mechanism,  the difference can be 100x different.  And if you consider the QW2,  using Laplace mechanism,  Laplace mechanism, the privacy cost is over 10x worth.  Because some of the mechanism are data-independent mechanism,  and translating queries, translating into data-independent  mechanism is easy, because the privacy cost  only depends on the query.  Some mechanisms are data-dependent mechanism,  whose privacy cost, whose true privacy cost  actually depends on the data.  So consider an example.  Suppose the query is a single model attendance  more than 100, and the accuracy specified is alpha 10,  beta is 10 to the negative five.  Using Laplace mechanism, the privacy cost epsilon  is log 1 over 2 beta, outside over alpha is 1.08.  And graphically speaking, this is your count,  and this is the threshold 100.  Suppose you know the true count,  the true attendance of 1000 here,  and this is your alpha,  and this range, that's your noisy count.  And you can see from this query,  the noisy answer to this query is yes.  Can we reduce the privacy cost  without changing the answer?  Well, in fact, we can relax alpha up to 900  without affecting the answer.  If we set alpha as 900,  then the privacy cost is reduced from 1.08  to 0.012, which is a big save.  However, this approach will require you  to know this true value, which is not possible upfront.  Alternatively, we propose a multi-poking mechanism.  And the idea is, the idea is you poke  with increasing privacy budget.  At the beginning, you set a small privacy budget  and test whether the noisy count  is surfacing a lot than the threshold.  If no, then you increase the privacy budget  and test again, until you find a large enough  accuracy tolerance.  So this is an example, this multi-poking mechanism  is an example of data dependent mechanism.  Bear this in mind, so the best mechanism for query  depends on the data and the query.  So Apex supports a set of mechanism for different queries.  And we let Apex to choose, for giving a query an accuracy,  we let Apex to choose the best one,  and I will skip the detail for this.  We did a lot of evaluations using benchmarking queries,  and to summarize the key findings here,  Apex can effectively translate the queries  with accuracy requirement into DP mechanisms,  and all queries can be answered with moderate  to low privacy cost.  As we empirically show that there is no universal  best mechanism and Apex can automatically  choose the optimal one.  Another evaluation I would like to highlight  is we can express a full data exploration workflow  using Apex.  So, antitrolution is a process to identify  duplicated records that refers to the same entity  in the real world.  And we can express a antitrolution strategy  using the queries supported by Apex.  For example, in a potential antitrolution strategy,  the data analyst wants to test the quality  of similarity predicts.  For example, how many duplicated record  can this similarity predicts capture?  And this question can be answered by WCQ,  for example, using Apex.  We did a lot of experiments by varying privacy budget,  varying query accuracy, varying data size,  and I just want to show you one of them.  So, in this, the x-axis represents the privacy budget,  and the y-axis represents this recall.  When you give a small privacy budget,  only few queries can be answered.  So, the analyst does not have enough information  to tune this workflow.  Increasing the privacy budget allows more interactions  for the data analyst, and therefore,  the data analyst can get more insights from the data  and better tune this strategy.  Apex can allow antitrolution to reach good quality  with reasonable privacy cost.  For example, when you set the privacy budget as one,  the recall is more than 95%.  To summarize, we want to solve the challenge  of between data owner and the data analyst  when exploring private data set.  And we designed Apex to let the data owner  and the analyst express their concerns naturally  so that both parties, they can focus on their own business  in the most natural way.  And Apex translates accuracy requirement  into differential private mechanisms,  and we empirically show that Apex can achieve  high exploration quality with reasonable privacy cost.  And that's all for my talk,  and thanks you for your attention.  I would like to take questions.  Thank you.
Ge_He_Illya_Machanavajjhala_0_167.png Ge_He_Illya_Machanavajjhala_168_371.png Ge_He_Illya_Machanavajjhala_372_479.png Ge_He_Illya_Machanavajjhala_480_1823.png Ge_He_Illya_Machanavajjhala_1824_2255.png Ge_He_Illya_Machanavajjhala_2256_4751.png Ge_He_Illya_Machanavajjhala_4752_5927.png Ge_He_Illya_Machanavajjhala_5928_6839.png Ge_He_Illya_Machanavajjhala_6840_7211.png Ge_He_Illya_Machanavajjhala_7212_12971.png Ge_He_Illya_Machanavajjhala_12972_13331.png Ge_He_Illya_Machanavajjhala_13332_13883.png Ge_He_Illya_Machanavajjhala_13884_16283.png Ge_He_Illya_Machanavajjhala_16284_16343.png Ge_He_Illya_Machanavajjhala_16344_16847.png Ge_He_Illya_Machanavajjhala_16848_17603.png Ge_He_Illya_Machanavajjhala_17604_19019.png Ge_He_Illya_Machanavajjhala_19020_20279.png Ge_He_Illya_Machanavajjhala_20280_21467.png Ge_He_Illya_Machanavajjhala_21468_21597.png