PaperlayerView exact revision on arXiv

Source-linked AI summary

Differential Privacy: An Economic Method for Choosing Epsilon

Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, Aaron Roth

arXiv:1402.3329v1cs.DB

TL;DR

Choosing ε is difficult because it controls the tradeoff between privacy and accuracy, while prior work often provides little justification for selected values. The paper proposes an economic model balancing analyst accuracy with participant risks, applies it across statistical case studies, and finds that private studies can sometimes be cheaper or more accurate than non-private studies at the same cost.

  • Problem

    ε controls privacy strength and accuracy, yet studies have used values from 0.01 to 7 with little explanation or justification.

  • Method

    The paper models analyst accuracy and participants’ expected benefits and privacy risks to calculate acceptable ε and δ values for studies.

  • Results

    A differentially private study can sometimes be cheaper or more accurate than an equivalent non-private study at the same cost.

  • Takeaways & Limitations

    The model provides practical guidance for choosing ε and δ using quantities that can be estimated in real-world applications.

  • Takeaways & Limitations

    The model does not provide a fully rigorous way to estimate individuals’ base privacy costs, which depend on perceptions of privacy loss and uncertain events.

Abstract

from arXiv · show

Differential privacy is becoming a gold standard for privacy research; it offers a guaranteed bound on loss of privacy due to release of query results, even under worst-case assumptions. The theory of differential privacy is an active research area, and there are now differentially private algorithms for a wide range of interesting problems. However, the question of when differential privacy works in practice has received relatively little attention. In particular, there is still no rigorous method for choosing the key parameter $ε$, which controls the crucial tradeoff between the strength of the privacy guarantee and the accuracy of the published results. In this paper, we examine the role that these parameters play in concrete applications, identifying the key questions that must be addressed when choosing specific values. This choice requires balancing the interests of two different parties: the data analyst and the prospective participant, who must decide whether to allow their data to be included in the analysis. We propose a simple model that expresses this balance as formulas over a handful of parameters, and we use our model to choose $ε$ on a series of simple statistical studies. We also explore a surprising insight: in some circumstances, a differentially private study can be more accurate than a non-private study for the same cost, under our model. Finally, we discuss the simplifying assumptions in our model and outline a research agenda for possible refinements.

1 Introduction

The paper addresses the unresolved problem of choosing ε and δ in practical differential-privacy studies. It proposes an economic model balancing analyst accuracy against participant risks and applies it to case studies, including when private studies can outperform non-private ones at equal cost.

  • Motivation: Differential privacy limits how much an individual’s data can affect outputs without requiring assumptions about attackers’ knowledge or goals.For any result, the probability changes by at most a factor of e^ε.
  • The challenge of setting ε: ε governs privacy strength, query capacity, and achievable accuracy, but published studies often choose values from 0.01 to 7 without justification.The paper notes that selecting δ raises a similar concern for (ε,δ)-differential privacy.
  • Approach: The paper proposes a model that calculates acceptable ε and δ ranges from study parameters and balances analyst interests with prospective participants’ expected benefits and risks.Participants are modeled as rational contributors who participate when compensation outweighs expected privacy-related risks.
  • Case studies: The model is applied across one-query, many-query, constrained, and (ε,δ)-private studies involving smokers, educational data, movie ratings, and social networks.The case studies vary model inputs across four study scenarios.
  • Key result: A strongly private study can sometimes be cheaper or more accurate at fixed cost than an equivalent non-private study.Although privacy requires more participants to offset added noise, reduced participant risk can lower the compensation they demand.
  • Limitations: The model offers practical guidance but assumes participants fear specific bad events and can estimate expected costs, so some applications may need refinements.The paper identifies these assumptions as simplifications rather than universal features of participation decisions.

2 Background: Differential privacy

Differential privacy bounds the influence of one record on randomized outputs by comparing neighboring databases. The Laplace mechanism provides a canonical construction whose noise scale depends on function sensitivity and ε, while privacy also supports post-processing and composition.

  • Definition: Differential privacy compares randomized outputs on neighboring databases that differ in one record, bounding the effect of an individual’s data.The paper uses equal-size neighboring databases because database size is assumed public.
  • Definition: For every output set S, an ε-differentially private mechanism changes its probability by at most a multiplicative factor of e^ε between neighboring databases.The bound applies to arbitrary subsets of the mechanism’s output range, including singleton outputs.
  • Interpretation: The parameter ε controls how much output distributions can depend on whether an individual’s private data is included.The guarantee works in both directions: probabilities are bounded above and below across neighboring databases.
  • Laplace mechanism: The Laplace mechanism adds noise calibrated to a function’s sensitivity, using a Laplace distribution with scale c/ε for a c-sensitive real-valued function.Larger sensitivity or smaller ε produces a wider distribution and a higher probability of larger noise.
  • Laplace mechanism: For the proportion of smokers in N records, sensitivity is 1/N, so adding Lap(1/Nε) noise yields an ε-differentially private release.Changing one record alters the proportion by at most 1/N.
  • Properties: Differential privacy is preserved under arbitrary post-processing and degrades gracefully under composition, with k ε-private mechanisms yielding a kε-private mechanism.These properties support building complex private algorithms from simpler mechanisms.

3 Interpreting ε

Differential privacy interprets ε as a bound on how participation changes harmful-event probabilities and expected costs, while also trading privacy against accuracy. This interpretation motivates unpacking ε into more intuitive parameters for practical choice.

  • Privacy interpretation: For bad events that cannot directly observe participation, differential privacy limits the probability increase caused by participation to a factor of e^ε.The argument compares runs with real versus dummy data while holding other records fixed.
  • Privacy interpretation: Differential privacy does not prevent harm; it limits how much participation increases the risk of a harmful event relative to declining.A medical study, for example, cannot promise unchanged insurance premiums, only a bounded increase in their risk.
  • Privacy interpretation: The expected cost of participating in a study is within an e^ε factor of the expected cost of declining.Event costs are aggregated through an output cost function, so the guarantee can be expressed in terms of real-world consequences.
  • Modeling assumptions: The interpretation depends on which events belong to E and how costly they are; including unaffected events can make perceived risk unjustifiably large.The paper notes that deciding which events a mechanism may be responsible for is not purely technical.
  • Choosing ε: ε also controls the noise required for privacy, creating a direct tradeoff between participants’ expected costs and study accuracy.The paper describes ε as a knob balancing privacy and utility, while prior guidance often leaves its setting generic or weakly justified.
  • Choosing ε: The paper’s goal is to replace ε’s abstract compression of competing interests with a more ramified model using intuitive parameters.The competing interests include analyst accuracy requirements and participant compensation for risk.

4 A two-party model

The paper models privacy-parameter choice as a negotiation between an analyst seeking accurate results within a budget and individuals weighing compensation against privacy risks. Differential privacy bounds participation-related harm, while feasible choices of ε and N balance accuracy, privacy, budget, and compensation.

  • The two parties: The model treats ε selection as a two-party problem involving an analyst seeking useful, accurate results and an individual deciding whether to participate.The analyst requires target accuracy and has a study budget; the individual weighs expected compensation against participation-related risks.
  • The analyst’s view: The analyst evaluates accuracy against a benchmark, with error depending on ε and potentially on database size N.Benchmarks may be the non-private sample statistic or the population statistic; population inference also includes sampling error.
  • The analyst’s view: Larger N generally improves accuracy and can reduce privacy noise, but participant compensation creates a budget constraint on study size.The model assumes the analyst cannot tolerate error beyond target level α and is equally satisfied with results within that target.
  • The individual’s view: Participants are modeled as rational: they participate only when expected compensation outweighs their expected participation-related cost.The study is assumed to occur regardless of an individual’s decision, so the model addresses participation rather than whether the study should run.
  • The individual’s view: Differential privacy bounds how much participation can increase the probability of defined bad events, rather than preventing harmful events from occurring.For expected costs, the model derives C ≤ e^εE and therefore C − E ≤ (e^ε − 1)E.
  • Combining the two views: Feasible values of N and ε satisfy the study’s budget, target accuracy, and compensation requirements while exposing a privacy–accuracy tradeoff.Larger ε and smaller N favor study size and accuracy, whereas smaller ε and larger N provide stronger guarantees to individuals.
  • Combining the two views: The model abstracts away internal mechanism details and applies across offline, interactive, distributed, and centralized differentially private settings.Payments depend on the study through E and ε, with E capturing study-specific base costs and ε controlling the privacy guarantee.
  • Deriving the cost E: Estimating E remains a practical limitation because participants’ maximum expected costs may be difficult to calculate precisely.The paper considers reasoning about specific bad events and surveys as possible estimation approaches rather than selecting one universal E.

5 A simple study

The paper models a one-query differentially private mean-estimation study by balancing accuracy and participant-compensation constraints over ε and N. Case studies show that feasibility depends on the assumed privacy risks and costs participants face.

  • Study setup: The study recruits N subjects, estimates a population proportion, and releases the sample mean with Laplace noise of scale 1/(Nε).The sample mean has sensitivity 1/N, while ε controls the privacy–accuracy tradeoff.
  • Accuracy model: Accuracy is modeled as the probability that total error exceeds a target T, combining sampling error and Laplace noise.The analysis bounds the two error sources separately and combines them through a failure-probability bound.
  • Constraints: The budget constraint compensates each participant by (e^ε −1)E, while accuracy imposes AM(ε,N) ≤ α.Feasible choices satisfy both constraints simultaneously.
  • Constraints: Feasible values trade off privacy and study size: larger ε and smaller N improve accuracy and reduce study size, whereas smaller ε and larger N strengthen individual protection.Some parameter combinations may be infeasible, and sufficient closed-form conditions need not be necessary.
  • Case studies: For T = 0.05 and α = 0.05, one sufficient setting is ε = 0.0083 with N ≈20000, and with B = 3.0 × 10^4 the study is feasible when E ≤182.The threshold E feas ≈182 is obtained by solving the budget condition under the stated setting.
  • Case studies: The assumed scenarios produce different feasibility outcomes: social-network risk gives E = 1 and is feasible, while smoking-risk assumptions give E = 254.8 and no feasible solution.Movie-rating assumptions give E = 0.25 and are feasible; another disclosure scenario gives E = 12.5 and is feasible.

6 The true cost of privacy

The paper compares privacy-protected and non-private mean-estimation studies by modeling compensation for expected and worst-case privacy harms. Under a sufficient condition, private studies can cost less because differential privacy reduces participants’ risk even though it requires larger samples.

  • Cost model: The comparison assumes non-private participants may be compensated according to worst-case harm W, while private participants receive compensation based on expected baseline harm E.E includes harm expected even without participation, whereas W represents direct disclosure harm.
  • Cost model: Non-private studies directly release the sample mean, so their accuracy error comes only from sampling rather than added Laplace noise.The paper uses a lower bound on the required non-private sample size to compare budgets fairly.
  • Cost comparison: Theorem 9 gives a sufficient, but not necessary, condition under which private mean estimation is cheaper than non-private estimation exposing fraction φ of participants.Failure of the condition does not establish that the private study is more expensive.
  • Case studies: For the social-network scenario, substituting E = 1 and W = $100,000 into the condition shows that the private study is cheaper.The comparison uses the paper’s assumed exposure fraction and scenario costs.
  • Case studies: For movie ratings, the non-private study needs N′ ≥115 and costs approximately 575, whereas the equivalent private study with N = 20000 costs approximately 40.The private setting uses E = 0.25 and ε = 0.0083.
  • Case studies: At equal budgets, the private study can recruit more participants to improve accuracy, making it cheaper and more accurate in the movie-rating comparison.The paper attributes the cost advantage to lower participant compensation under bounded privacy risk despite the larger sample.

7 Extending the model

This section bounds ε in both directions and incorporates study-specific side conditions into feasibility analysis. Larger ε improves accuracy and reduces study size but weakens privacy, while smaller ε strengthens privacy at the cost of accuracy and participants.

  • 7.1 Upper bounds on ε: Large ε can satisfy formal differential privacy while providing an intuitively weak guarantee.With |X| = 10^6 and p* = 0.99, a mechanism can publish a targeted record with probability 0.99 while remaining ε-private for ε ≥ 14.
  • 7.2 Lower bounds on ε: Small ε can make outputs nearly independent of databases that differ in many rows, undermining accuracy.When ε ≤ 1/N, event probabilities across arbitrary databases differ by at most a factor of e, making the algorithm probably useless.
  • 7.3 Case Study: Educational statistics: The model allows study-specific limits such as fixed population size and maximum privacy harm per participant.The educational example uses N ≤ 1000 and bounds each student’s harm by (e^ε − 1)·12.5 ≤ 10.
  • 7.3 Case Study: Educational statistics: Adding population, privacy-harm, ε-bound, and accuracy constraints can make an otherwise feasible study infeasible.For the educational-data example, the original study without side constraints was feasible, but the added constraints were not jointly feasible for the Laplace mechanism.

8 What about δ?

The paper extends its economic model from ε-privacy to (ε,δ)-privacy, where δ permits a bounded probability of privacy failure. It models the resulting worst-case participant cost and applies the extension to a more accurate MWEM mechanism.

  • 8 What about δ?: (ε,δ)-differential privacy permits a δ probability of violating the pure privacy bound.An output that is impossible under ε-privacy may occur with probability up to δ under (ε,δ)-privacy.
  • 8 What about δ?: A reasonable guarantee requires δ to be much smaller than 1/N.For δ = 1/N, randomly outputting a database record is (0,δ)-private despite being intuitively non-private.
  • 8.1 Modeling δ: The analyst model treats accuracy as a function of ε, N, and δ, allowing the original feasibility framework to incorporate δ.The budget constraint becomes (e^ε −1)EN + δWN ≤ B.
  • 8.1 Modeling δ: The extended participant model bounds marginal expected cost by (e^ε − 1)E + δW.E is the base cost and W bounds the cost if private information is publicly revealed.
  • 8.2 Case study: The extension is evaluated by revisiting MWEM for many counting queries under (ε,δ)-privacy.The study retains the large-query setting while using the corresponding (ε,δ)-private accuracy guarantee.

9 Discussion

The discussion argues that the model’s added complexity reflects real-world decisions about participant costs, while identifying assumptions and refinements needed for greater realism.

  • 9 Discussion: The model’s multiple parameters represent real-world factors that individuals and analysts must consider when selecting ε.These include target accuracy, analyst accuracy, study budget, and participant base cost.
  • 9.2 Possible refinements: Estimating participants’ base cost lacks a totally rigorous method because it depends on how individuals perceive privacy risks.The authors identify this estimation problem as an area for refinement.
  • 9.2 Possible refinements: The model assumes homogeneous participants and a common relationship between ε and privacy harm.Possible refinements include heterogeneous base costs, empirical privacy attacks, and more realistic harm functions.
  • 9.2 Possible refinements: The comparison with non-private studies uses a crude model of participant compensation.The authors call for more research on how much individuals want to be paid for private data.

10 Related work

Prior work has discussed ε through adversarial beliefs, economic models, markets, and auctions, but the literature generally offers varied values with little convincing justification. This paper distinguishes its approach by modeling broader harms and participant costs.

  • 10 Related work: Applications have used ε values mostly between 0.01 and 10, with little or no convincing justification.The paper presents this variation as evidence that choosing ε remains insufficiently grounded.
  • 10 Related work: Lee and Clifton bound ε by modeling how much an adversary’s belief about database participation can change.Their model focuses on discovering participation, whereas this paper emphasizes harms beyond reidentification.
  • 10 Related work: The paper critiques participation discovery as an incomplete proxy because learning that someone participated may itself be relatively harmless.Differential privacy is intended to address harms beyond reidentification.
  • 10 Related work: Other work models rational agents’ costs, and this paper adopts a conservative approach that upper-bounds cost linearly in ε.The related models address how rational agents should evaluate their costs under differential privacy.
  • 10 Related work: Market and auction approaches treat ε as a priced commodity or set it at the largest value the analyst can afford.These approaches differ from the paper’s parameterized participant-and-analyst cost model.

11 Conclusion

The paper proposes an economic model for choosing ε and δ using quantities that can be estimated in practice. It applies the model in case studies and finds that, under its assumptions, a private study can sometimes cost less than a non-private study at the same accuracy.

  • The model enables principled selection of ε and δ from quantities that can be estimated in practice.
  • Two case studies apply the model to practical differential-privacy choices.
  • A private study can sometimes be cheaper than a non-private study with the same accuracy.

A Protected and unprotected events

Differential privacy protects events whose probabilities remain comparable when an individual participates or does not, but participation itself is excluded. The example distinguishes observable participation from mistaken beliefs about participation and emphasizes harms from incorrect inferences.

  • Protected and unprotected events: Events that reveal an individual’s participation are excluded from the protected event space.The event “John Doe contributes data to the study” directly changes with participation.
  • Protected and unprotected events: A useful noisy cancer count can let an adversary infer both the study population’s cancer status and John Doe’s status.The count must distinguish populations where everyone or no one has cancer.
  • Protected and unprotected events: If participation is observable, the adversary’s belief about John Doe’s cancer status differs depending on whether he participates.If participation is only believed and may be mistaken, the bad event can remain protected.
  • Protected and unprotected events: Differential privacy focuses on the consequences of privacy breaches rather than only whether an adversary correctly learns private data.Incorrect beliefs can still cause harms such as increased insurance premiums.

B The individual’s participation decision

The participation model assumes individuals can choose whether to contribute and evaluates compensation for their marginal increase in expected harm. The paper discusses a broader cost comparison but concludes that it does not require additional compensation once the study decision is made.

  • The individual’s participation decision: The model assumes individuals have a meaningful choice about whether to participate.This assumption may not hold when data has already been collected and individuals are difficult to contact.
  • The individual’s participation decision: A thought experiment estimates the compensation needed to incentivize participation when individuals genuinely have a choice.A small required compensation indicates that expected harm to a student is not very high under the model.
  • The individual’s participation decision: The model compensates participants for marginal harm from participating, while the cost relative to not running the study can be much higher.The study is assumed to run when participation decisions and compensation are evaluated.
  • The individual’s participation decision: The paper concludes that participants need not receive compensation beyond their marginal harm once the study has already been approved to run.The comparison uses the real database versus an empty database representing no study.
Loading 1402.3329v1…