Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release

arXiv:2502.02709 · cs.CR, cs.DB · Submitted 2025-02-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Enforcing Demographic Coherence".

Elias: Here's the gist of the paper. Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release introduces demographic coherence, a necessary condition inspired by privacy attacks that captures privacy violations arising from inferences about individuals that are incoherent with respect to the demographic patterns in the data.

Nadia: This framework provides a way to analyze data release algorithms and suggests experimental evaluation methodologies for assessing risks.

Elias: The study of privacy-preserving data releases has historically relied on two approaches: formal definitions of conditions sufficient for privacy preservation, like differential privacy, and attacks that demonstrate privacy breaches.

Nadia: Differential privacy's adversarial model may be too stringent when it significantly costs data utility.

Title and authors: Nadia: So we're talking about this paper called "Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release." It’s written by Mark Bun, Marco Carmosino, Palak Jain, Gabriel Kaptchuk, and Satchit Sivakumar. The title itself suggests they aren't just looking at abstract privacy math; they're focused on how data releases actually affect different groups of people.

Elias: Exactly. They’re trying to bridge the gap between formal privacy definitions like differential privacy and the real-world harms we see when data is released, especially when those inferences don't match the actual demographic patterns in the data. They are proposing a necessary condition for privacy that can be checked on any algorithm, not just one sufficient condition.

Priya: It sounds like they're trying to define what it means for a prediction to be coherent with the underlying population structure, which is something I think is crucial before we trust any release of data.

Nadia: Right. So they define demographic coherence as capturing privacy violations that come from inferences about individuals that just don't make sense with the demographic patterns in the dataset itself. It focuses on these confidence-rated predictors and what it means for them to be incoherent with respect to specific groups or lenses.

Elias: They give a formal definition of an incoherent predictor, saying it has alpha incoherence if for some collection C, lens rho, and distance metric dist, the prediction distance between two splits Xa and Xb is greater than alpha when measured over that collection. That’s a very precise way to formalize this kind of violation.

Priya: But what does that actually mean in practice? I need to know if this is just academic noise or if it leads to something we can measure with real data.

Nadia: Well, the paper shows that every differentially private release automatically satisfies demographic coherence, which is good because it means DP is a strong enough condition on its own. But they also found algorithms that are demographically coherent but not differentially private, which tells us there's a whole space of privacy mechanisms we haven't fully mapped yet.

Title and authors: Elias: That’s important because it means the necessary condition isn't just something DP satisfies; it’s a broader requirement that some other techniques might meet in ways DP doesn't. They also show that bounded max-information algorithms are coherence enforcing, which is a key connection they draw between privacy bounds and this demographic coherence concept.

Priya: So, if we look at the practical side, they instantiate this using the Wasserstein-one metric to measure how different the distributions are across those splits and lenses <ref:2502.02709#pg2>. That sounds like a concrete way to quantify that incoherence for real experiments.

Nadia: Precisely. They prove that any data curation algorithm with bounded max-information enforces this Wasserstein coherence under specific constraints on the size of the subpopulation C, which is a very specific constraint we can work with when designing systems.

Elias: That connection they make between differential privacy and max-information via Theorem six is really what grounds their entire framework. It shows that these two areas are deeply linked mathematically, allowing them to derive results about coherence enforcement from the properties of max-information bounds.

Priya: From my side, I'm wondering how this translates to actually designing a privacy filter. If we want our release to be coherent with respect to a certain demographic lens, what parameters—like epsilon—do we need to set?

Nadia: That’s the core application. They show that pure differential privacy algorithms enforce Wasserstein coherence under size constraint gamma, and approximate differential privacy algorithms do it under specific conditions, which are essentially parameter conversions for practitioners.

Elias: So they’re giving us a way to suggest epsilon values not just based on abstract guarantees, but based on the specific coherence constraints we want to enforce in our real data release scenarios. It moves the discussion from a black box guarantee to a target we can measure against.

Priya: That sounds like it gives curators some actual levers to pull when they're deciding how much noise or distortion they can afford for utility versus privacy. But what about where this framework stops working?

Nadia: The paper does flag that the analysis relies on Lemma one which bounds the probability that the Wasserstein distance between predictors on two splits exceeds alpha, and it notes that this bound depends on the size of the subpopulation C <ref:2502.02709#pg2>. That’s a limitation—the tighter our constraints are on C, like keeping it small, the better those bounds become.

Title and authors: Elias: And they also mentioned in Corollary two that for approximate differential privacy algorithms, the required parameters for achieving this coherence are indeed achievable under those specific conditions they laid out <ref:2502.02709#pg2>. It suggests a path forward for using approx-DP when aiming for a particular type of demographic coherence.

Priya: So, to wrap up the practical side, this framework lets us use Wasserstein distance to measure incoherence across different sub-populations and lenses, and it gives us concrete parameter conversions using pure or approximate differential privacy algorithms to meet those coherence targets.

Nadia: That’s the gist of it. This paper, "Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release," offers a necessary condition for data privacy that's inspired by real attacks, allowing us to analyze algorithms based on what they *must* guarantee rather than just what they *might* guarantee with differential privacy.

Elias: And it shows that this framework supports rigorous analysis, showing that all algorithms with bounded max-information are coherence enforcing, which is a strong statement about the relationship between these concepts. It gives us a solid foundation for how to think about privacy harms in terms of demographic patterns.

Priya: It’s interesting because it grounds the abstract concept of incoherence into something measurable through distance metrics and subpopulation analysis, giving us tangible ways to assess risks before we even deploy a system.

Nadia: Exactly. It provides the tools for curators to identify parameter regimes that lead to specific harms, and it demonstrates that this coherence measure is independent of accuracy, which is a really important distinction for how we design these systems.

Elias: So moving forward, they suggest using the Wasserstein-one metric specifically because it’s a natural way to instantiate this definition in practice, giving us a concrete mathematical tool to work with <ref:2502.02709#pg2>. It’s less abstract than just saying "it's coherent."

Priya: I think the most important thing here is that it helps us build intuition for setting real-world parameters because it connects the formal requirements directly to measurable distance metrics across different groups. That’s what makes this useful for building practical privacy mechanisms.

The paper's summary: Nadia: So, we’re talking about how they framed privacy not just as avoiding direct attacks, but as making sure the data release actually matches what you expect from your demographic patterns and groups in the data itself.

Elias: Exactly. They call this concept “demographic coherence,” which is essentially a necessary condition for privacy that comes from looking at how inferences about individuals might contradict the actual patterns in the dataset.

Priya: So, it’s not just about hiding names; it’s about ensuring that if you make a prediction based on private data, that prediction doesn't suddenly look weird or incoherent when you look at the data sorted by different demographic lenses.

Nadia: Right. They define an incoherent predictor formally, showing that if you have some confidence level and a certain distance between two ways of splitting the data, the prediction gap has to be larger than some alpha value for it to count as a violation.

Elias: But what they really nail is how this connects to things like differential privacy. they prove that any data release protected by differential privacy automatically satisfies this demographic coherence condition.

Priya: That’s a big deal because it means differential privacy isn't just a sufficient condition for one type of harm; it enforces this broader structural requirement about the data itself.

Nadia: But Elias pointed out they also found algorithms that are demographically coherent but aren't differential private, which shows there’s more flexibility in how we can achieve coherence than just sticking to differential privacy.

Elias: True. They showed that bounded max-information algorithms are coherence enforcing, and they even proved that approximate differential privacy can hit this coherence target under certain parameter settings.

Priya: When you think about applying this, it seems like they’re giving data curators a way to set specific targets for incoherence using metrics like the Wasserstein distance over different sub-populations and lenses.

Nadia: It gives them a tangible way to measure the risk—not just saying "this is private enough"—but actually measuring how incoherent their resulting predictions are with respect to those groups they care about.

Elias: So, it moves the goal from a black box guarantee to something where you can actually test if your release meets a specific coherence threshold using tools like Wasserstein-one distance.

Priya: That’s the practical part—it gives us a measurable metric for incoherence that relates directly to how different the probability distributions are between two ways of viewing the data.

Nadia: And they suggest that this framework is ergonomic, meaning it provides enough formal structure for rigorous analysis without getting so bogged down in overly abstract math that you can’t actually use it to make a decision about your release.

Elias: It’s about making sure you understand what the constraints mean for the system, not just memorizing the proof.

Priya: It really helps clarify that privacy isn't just an abstract number; it has to align with the actual structure of your data groups if you want to avoid specific kinds of demographic confusion harms.

Nadia: So they’re giving us a way to think about privacy in terms of what the data *shows* across different populations, which is a really useful shift when designing these systems.

Elias: And it sets up a good foundation for testing various release methods against these coherence constraints before you deploy anything.

Priya: Next time, we’ll look at how they specifically use that Wasserstein distance to set the real parameters for achieving this coherence.

The paper's improvements: Tom: So, we’re talking about how the authors suggest ways to make this framework more usable and better for actual work, moving beyond just defining what coherence looks like.

Nadia: They are focused on making it ergonomic so that data curators can actually use it without getting lost in the heavy math behind the necessary conditions.

Elias: Right. They want to provide sufficient formalism for rigorous analysis while keeping the actual privacy harms that matter front and center, you know? It’s not just a proof; it’s a tool for defending data releases.

Priya: I mean, they are suggesting experimental evaluation methodologies too, which is important because it shows how you could actually test if your release is coherent or not in a real-world deployment scenario.

Nadia: Exactly. They want to give people concrete ways to assess risk, instead of just having an abstract mathematical definition floating around in a paper.

Elias: They’re showing that this framework can be used to identify specific parameter regimes where certain harms are enabled, which is super useful for tuning the privacy settings.

Priya: That means if you want to avoid a certain type of demographic inference harm, you can use this framework to pinpoint exactly which constraints on your release parameters you need to satisfy.

Nadia: They also stress that this coherence measure is independent of accuracy, which is a key point for designing these systems; the goal isn't just high utility, it's controlled privacy against demographic incoherence.

Elias: That’s right. They want to emphasize that this coherence check applies regardless of how accurate the final prediction model turns out to be.

Priya: And they’re recommending using the Wasserstein-one metric specifically because it’s a natural way to instantiate these definitions in practice, which makes it more concrete than just relying on some generic distance measure.

Nadia: That metric is the practical tool you can use to measure that incoherence across different sub-populations and lenses, which is something we can actually set up for an experiment.

Elias: So they’re giving us a recipe: use this framework, test it with Wasserstein distance, and tune your differential privacy or approximate differential privacy parameters to hit your target coherence levels.

Priya: It gives data curators a path forward to move from abstract privacy goals to concrete deployment choices based on what the data actually shows across groups.

Nadia: And they’re really pushing the idea that this framework supports rigorous analytical arguments about algorithms, showing that all algorithms with bounded max-information are also coherence enforcing, which is a strong statement about their relationship.

Elias: It’s a big claim, but it grounds the entire concept in the properties of max-information bounds they established earlier.

Priya: So they’re showing that this isn't just some niche theoretical thing; it has implications for how we build systems that release data while respecting demographic realities.

Conclusion: Tom: So we’re wrapping up this look at "Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release." It boils down to using a necessary condition instead of just relying on differential privacy as the only safety net.

Nadia: Yeah, essentially, they established that demographic coherence is a required property for any private data release because it captures inferences that contradict the actual demographic patterns in your data.

Elias: It’s a necessary condition because it stems from how privacy attacks work; it’s not something you just hope to satisfy with one specific mechanism.

Priya: What I see is that this gives us a way to look at the data's structure itself—how the groups are distributed—and ensure our releases respect those distributions.

Nadia: Right. And they show that every differentially private release already satisfies this coherence, which means DP is a solid baseline for meeting these structural requirements.

Elias: But they also found algorithms that are coherent but not differential private, so we still have room to explore other privacy mechanisms beyond just the standard epsilon-based noise addition.

Priya: So for us as researchers looking at this, it means we can start building experimental setups that specifically measure this incoherence using things like the Wasserstein distance over different sub-populations.

Nadia: Exactly. We get a concrete way to assess risk by measuring how far off our predictions are when we look at those different demographic lenses.

Elias: I think the main thing here is that it provides a solid foundation for analyzing algorithms based on these necessary conditions, which is much stronger than just looking at sufficient conditions alone.

Priya: It shifts the focus from just hiding individual identities to making sure your released information makes sense when you look at how those individuals are grouped together in the data.

Nadia: So it's about building intuition for setting real-world parameters by connecting formal requirements directly to measurable distance metrics across different groups.

Elias: And it supports the idea that we can use approximate differential privacy algorithms to hit these coherence targets under specific conditions they laid out, which is a huge parameter conversion tool for practitioners.

Priya: It gives us a framework where we can identify exactly which parameter regimes enable specific types of demographic confusion harms before we even deploy anything.

Nadia: So the main point of this paper is that demographic coherence offers an ergonomic way to reason about privacy harms by providing necessary conditions that are measurable through things like Wasserstein-one distance.

Elias: It’s a strong analytical tool for algorithms, showing the link between bounded max-information and these coherence properties.

Priya: I think it’s really about making sure the data we release reflects the underlying reality of how those groups are structured, which is a fundamental step in building trust in released information.

Nadia: So that's our look at "Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release."

Elias: We’ll keep an eye on how this framework gets used to drive the next generation of privacy defenses.

cs.CR, cs.DB

Submitted: 2025-02-04

Updated: 2026-11-09

Comments: 56 pages. ITCS 2027 version

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release introduces demographic coherence…

Key concepts

Demographic Coherence
This is a necessary condition ensuring that predictions made from private data are consistent with the underlying demographic patterns in the dataset. It prevents privacy violations where inferences about individuals contradict known group statistics, focusing on the incoherence between individual predictions and population demographics.
$\alpha$-Incoherent Predictor
A predictor is considered $\alpha$-incoherent if its predictions regarding a specific sub-population $X_a$ differ significantly from those expected based on demographic patterns ($ ho$) and a confidence threshold ($C$). Formally, it means the prediction distance between two groups exceeds $\alpha$ for some relevant context.
Wasserstein Distance
This metric is used to quantify the 'distance' or difference between probability distributions of predictions across different data splits. By using Wasserstein-1 distance, researchers can measure how much a released algorithm deviates from demographic coherence, providing a concrete way to assess privacy risks.

Terminology

Summary

Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release introduces demographic coherence, a necessary condition inspired by privacy attacks that captures privacy violations arising from inferences about individuals that are incoherent with respect to the demographic patterns in the data. p. 0

Where the paper says it

We address the gap between these approaches by introducing demographic coherence, a condition inspired by privacy attacks that we argue is necessary for data privacy. This condition captures privacy violations arising from inferences about individuals that are incoherent with respect to the demographic patterns in the data.

This framework provides a way to analyze data release algorithms and suggests experimental evaluation methodologies for assessing risks. p. 0
Where the paper says it

Thus, we capture privacy threats that exist even when no attack is explicitly being carried out. Our framework not only provides a condition with respect to which data release algorithms can be analysed but suggests natural experimental evaluation methodologies that could be used to build practical intuition and make tangible assessment of risks.

Introduction and Motivation

The study of privacy-preserving data releases has historically relied on two approaches: formal definitions of conditions sufficient for privacy preservation, like differential privacy, and attacks that demonstrate privacy breaches. Differential privacy's adversarial model may be too stringent when it significantly costs data utility. Privacy attacks often lack a clear path towards designing protection mechanisms because they do not distill a set of agreed-upon properties that make the attack convincing. p. 2

Where the paper says it

Since then, there has been a robust literature describing increasingly sophisticated attacks which continue to motivate efforts towards privacy preserving data release [40, 10, 9, 12]. While these attacks have proved convincing enough to shift data protection practices in many fields, attack demonstrations do not provide a clear path towards designing data protection mechanisms themselves, even in the form of “prevent all attacks like this one”; the attack demonstrations do not take on the task of distilling a set of agreed upon properties that make the attack convincing.

The authors propose necessary conditions, which can formally define properties any private data release should guarantee without needing a single sufficient condition. p. 2
Where the paper says it

The deficiencies inherent in each of the existing approaches compels us to explore an intermediary design philosophy: necessary conditions. Within this approach, we can formally define (possibly many) properties that any private data release should guarantee without needing to provide a single, unifying, sufficient condition.

Defining Demographic Coherence

Demographic coherence is defined as a condition capturing privacy violations arising from inferences about individuals that are incoherent with respect to the demographic patterns in the data. This notion focuses on confidence-rated predictors, which can be distilled from almost any data-informed process. p. 0

Where the paper says it

This condition captures privacy violations arising from inferences about individuals that are incoherent with respect to the demographic patterns in the data. Our framework focuses on confidence rated predictors, which can in turn be distilled from almost any data-informed process.

The definition of a demographically incoherent predictor is that it has α-incoherent predictions with respect to Xa, Xb, ρ, and C if for some C ∈ C, d h(πρ (XaC)), h(πρ (XbC)) > α. p. 9
Where the paper says it

We call predictors that act in this way “demographically incoherent. ” There are two important (if unintuitive) subtleties that immediately emerge from this description of incoherent predictions: (1) Harmful predictors need not be accurate: Incoherent predictions focus on the behavior of the predictor independent of accuracy.

The formal definition of coherence enforcement involves checking the demographic coherence of an algorithm L with respect to a specific dataset X, a collection C, a lens ρ, and a distance metric dist(·, ·). p. 6
Where the paper says it

We say that A enforces (α, β)-demographic coherence, if for all algorithms L : Y → (X → [−1, 1]) that use the report produced by the curator to create a confidence-rated predictor h : X → [−1, 1], the following condition is satisfied. For all datasets X, Pr Xa,Xb $←−X,Ra←A(Xa),h←L(Ra) [dist(h(Xa), h(Xb)) ≥ α] ≤ β, where Xa, Xb represent a random split of the dataset X into halves, report Ra is produced by the data-curator using only Xa, and h is created by running algorithm L on the report, h(Xa) represents the empirical distribution of predictions made on Xa, and dist(·, ·) represents a metric distance between distributions.

Relationship to Existing Formalisms

The paper proves that every differentially private data release is also demographically coherent. Furthermore, it shows that there are demographically coherent algorithms which are not differentially private. p. 0

Where the paper says it

Our framework not only provides a condition with respect to which data release algorithms can be analysed but suggests natural experimental evaluation methodologies that could be used to build practical intuition and make tangible assessment of risks. Finally, we argue that demographic coherence is weaker than differential privacy: we prove that every differentially private data release is also demographically coherent, and that there are demographically coherent algorithms which are not differentially private.

The framework demonstrates that bounded max-information algorithms are coherence enforcing, and it proves that pure-DP and approx-DP algorithms enforce demographic coherence under specific parameter conversions. p. 7
Where the paper says it

We leverage the connection between differential privacy and max-information to show the exact parameter conversion under which differentially private algorithms enforce demographic coherence. Theorem 2 is an informal statement of Theorem 7, the result for pure-DP.

Enforcement via Differential Privacy

The authors establish Theorem 7, showing that pure-DP algorithms enforce Wasserstein coherence with respect to collection C, lens ρ, and size constraint γ. Similarly, Theorem 8 proves that approx-DP algorithms enforce Wasserstein coherence under specific conditions. p. 1

Where the paper says it

5 Instantiating Demographic Coherence with a Metric . 16 5 Algorithms that Enforce Wasserstein Demographic Coherence 17 5.

These results are derived by leveraging the connection between differential privacy and max-information, which is captured by Theorem 6 connecting bounded max-information to demographic coherence. p. 7
Where the paper says it

We leverage the connection between differential privacy and max-information to show the exact parameter conversion under which differentially private algorithms enforce demographic coherence. Theorem 2 is an informal statement of Theorem 7, the result for pure-DP.

Instantiating Coherence with Wasserstein Distance

The authors instantiate the definition of demographic coherence using the Wasserstein-1 metric. They show that an algorithm is (α, β)-Wasserstein-demographically-coherent if it satisfies a certain condition related to the distance between distributions on two splits Xa and Xb. p. 6

Where the paper says it

For all datasets X, Pr Xa,Xb $←−X,Ra←A(Xa),h←L(Ra) [dist(h(Xa), h(Xb)) ≥ α] ≤ β, where Xa, Xb represent a random split of the dataset X into halves, report Ra is produced by the data-curator using only Xa, and h is created by running algorithm L on the report, h(Xa) represents the empirical distribution of predictions made on Xa, and dist(·, ·) represents a metric distance between distributions. Here, β is the probability that h is not demographically coherent, and α represents how close the distributions of h(Xa) and h(Xb) are required to be.

The final theorem proves that any data curation algorithm with bounded max-information enforces Wasserstein coherence under specific constraints on the size of the subpopulation C. p. 6
Where the paper says it

In this context, we say that and algorithm A enforces Wasserstein-coherence. The following theorem is an informal statement of Theorem 6, which argues that any data-curation algorithm with bounded max-information [23] (a notion that mathematically captures the dependence of algorithms’ outputs to their inputs) also enforces Wasserstein coherence.

Comparison to Perfect Generalization

The paper compares demographic coherence to perfect generalization, noting that while they share conceptual similarities, the technical details differ in important ways. Coherence enforcement limits the set of algorithms against which indistinguishability applies, whereas perfect generalization concerns the behavior of the algorithm itself. p. 1

Where the paper says it

3 Differentially Private Algorithms Enforce Demographic Coherence . 26 6 Acknowledgments 27 A Comparison to Perfect Generalization 33 B Differential Privacy implies Bounded Max-Information: Sampling without Replacement B.

The paper concludes that demographic coherence is a relaxation of perfect generalization. p. 1
Where the paper says it

3 Differentially Private Algorithms Enforce Demographic Coherence . 26 6 Acknowledgments 27 A Comparison to Perfect Generalization 33 B Differential Privacy implies Bounded Max-Information: Sampling without Replacement B.

Technical Preliminaries and Bounds

The proof of Theorem 6 relies on Lemma 1, which bounds the probability that the Wasserstein distance between predictors on two splits exceeds α. This bound depends on the size of the subpopulation X ∩ C. p. 2

Where the paper says it

While early attempts, like k-anonymity, proved inadequate, differential privacy [24] has recently emerged as an accepted standard, seeing deployment in both industry [27, 5, 21, 53] and government [1]. These formal approaches are often seen as sufficient for ensuring data subject’s privacy, in that they are “one-size-fits-all,” i.

The analysis involves bounding conditional expectations using Azuma’s inequality, leading to a final bound on the probability that the prediction distance exceeds α. p. 6
Where the paper says it

For all datasets X, Pr Xa,Xb $←−X,Ra←A(Xa),h←L(Ra) [dist(h(Xa), h(Xb)) ≥ α] ≤ β, where Xa, Xb represent a random split of the dataset X into halves, report Ra is produced by the data-curator using only Xa, and h is created by running algorithm L on the report, h(Xa) represents the empirical distribution of predictions made on Xa, and dist(·, ·) represents a metric distance between distributions. Here, β is the probability that h is not demographically coherent, and α represents how close the distributions of h(Xa) and h(Xb) are required to be.

The proof of Theorem 8 uses Corollary 2 to show that the required parameters for approx-DP algorithms are achievable. p. 4
Where the paper says it

For example, we show that all algorithms with bounded max information are also coherence enforcing. – Demographic coherence enforcement is achievable.

The analysis of max-information bounds involves theorems connecting DP and bounded max-information, such as Theorem 3 and Theorem 4. p. 6
Where the paper says it

In this context, we say that and algorithm A enforces Wasserstein-coherence. The following theorem is an informal statement of Theorem 6, which argues that any data-curation algorithm with bounded max-information [23] (a notion that mathematically captures the dependence of algorithms’ outputs to their inputs) also enforces Wasserstein coherence.

The final result for approx-DP algorithms is given by Corollary 2. p. 3
Where the paper says it

In this work, we design a novel necessary privacy notion rooted in three key insights: (1) privacy harms are increasingly going to come in the form of inferences at the hands of predictive algorithms. 1 That is, we should be interested in the predictions that these algorithms make about people—and the decisions organizations may make based on these predictions—even when predictive algorithms are not intentionally designed with causing harm in mind; (2) we should consider the confidence with which an algorithm can make predictions, because simply increasing the confidence that an individual or a group has a certain attribute may be enough to result in harm; and (3) The harms associated with breaches of privacy are not experienced uniformly among members of a population.

The proof of Corollary 1 in Section 5. p. 4
Where the paper says it

We prove that demographic coherence enforcement is achievable, showing parameter conversions under which any pure differentially private (pure-DP) algorithm and any approximate differentially private (approx-DP) algorithm enforce demographic coherence. For an overview of these theorems, see Section 2.

3 shows that the probability of incoherence is bounded by µ/2. p. 6
Where the paper says it

For all datasets X, Pr Xa,Xb $←−X,Ra←A(Xa),h←L(Ra) [dist(h(Xa), h(Xb)) ≥ α] ≤ β, where Xa, Xb represent a random split of the dataset X into halves, report Ra is produced by the data-curator using only Xa, and h is created by running algorithm L on the report, h(Xa) represents the empirical distribution of predictions made on Xa, and dist(·, ·) represents a metric distance between distributions. Here, β is the probability that h is not demographically coherent, and α represents how close the distributions of h(Xa) and h(Xb) are required to be.

The final bound derived for approx-DP algorithms is given by Theorem 8. The proof of Theorem 6 concludes with the union bound over all subpopulations in the class. p. 6
Where the paper says it

The formal definition of coherence enforcement is more intricate than the one above. One key technical distinction is that the restriction on predictor h applies not only to the full sets Xa and Xb, but also across different subpopulations in those sets.

The final bound on the probability of incoherence is given by Equation (11). p. 6
Where the paper says it

For all datasets X, Pr Xa,Xb $←−X,Ra←A(Xa),h←L(Ra) [dist(h(Xa), h(Xb)) ≥ α] ≤ β, where Xa, Xb represent a random split of the dataset X into halves, report Ra is produced by the data-curator using only Xa, and h is created by running algorithm L on the report, h(Xa) represents the empirical distribution of predictions made on Xa, and dist(·, ·) represents a metric distance between distributions. Here, β is the probability that h is not demographically coherent, and α represents how close the distributions of h(Xa) and h(Xb) are required to be.

The proof of Theorem 8 uses the bound from Corollary 2 to show that the required parameters for approx-DP algorithms are achievable. p. 4
Where the paper says it

For example, we show that all algorithms with bounded max information are also coherence enforcing. – Demographic coherence enforcement is achievable.

Conclusion and Practical Implications

The framework is designed to be ergonomic, providing sufficient formalism for rigorous analysis while keeping concrete privacy harms salient. It suggests natural experimental evaluation methodologies that could be used to build practical intuition and make tangible assessments of risks. p. 0

Where the paper says it

Thus, we capture privacy threats that exist even when no attack is explicitly being carried out. Our framework not only provides a condition with respect to which data release algorithms can be analysed but suggests natural experimental evaluation methodologies that could be used to build practical intuition and make tangible assessment of risks.

The framework allows curators to identify parameter regimes that enable specific harms. p. 2
Where the paper says it

This makes it necessary to understand how small the parameters must be for the prevention of concrete privacy harms. Therefore, necessary conditions can provide a concrete methodology for justifying parameter choices by identifying parameter regimes that could enable specific 3

The work demonstrates that demographic coherence is weaker than differential privacy, as every differentially private release is also demographically coherent. p. 0
Where the paper says it

Our framework not only provides a condition with respect to which data release algorithms can be analysed but suggests natural experimental evaluation methodologies that could be used to build practical intuition and make tangible assessment of risks. Finally, we argue that demographic coherence is weaker than differential privacy: we prove that every differentially private data release is also demographically coherent, and that there are demographically coherent algorithms which are not differentially private.

The framework supports rigorous analytical arguments about algorithms, such as showing that all algorithms with bounded max-information are also coherence enforcing. p. 4
Where the paper says it

Finally, the formalism we build supports rigorous analytical arguments about algorithms. For example, we show that all algorithms with bounded max information are also coherence enforcing.

The work provides a vision of how demographic coherence can support the intuition building required to set real-world parameters. p. 3
Where the paper says it

Additionally, we provide a vision as to how demographic coherence can support the type of intuition building required to set real-world parameters. 1 Our Contributions In this work we make the following contributions: – Demographic Coherence.

The framework is intended to be useful in many different contexts, providing sufficient formalism for rigorous analysis and provable realization. p. 3
Where the paper says it

Our resulting notion, which we call demographic coherence, is intentionally designed to be ergonomic2 in many different contexts. For example, we provide sufficient formalism to enable rigorous analysis and provable realization, all while keeping the specific harms against which demographic coherence protects compellingly salient.

The authors emphasize that harm is not necessarily predicated on accuracy, and they design demographic coherence to be independent of accuracy. p. 5
Where the paper says it

, is the information extracted about the data subject true? We observe that harm is not necessarily predicated on accuracy, and we design demographic coherence to be intentionally 6

The framework is intended to be ergonomic in many different contexts. p. 3
Where the paper says it

, informal decision-making process made by humans that might not be explicitly codified as algorithms in the traditional sense. 2We use ergonomic in this context to mean ease of use by many different stakeholders.

The authors recommend the Wasserstein-1 metric for instantiating these definitions. p. 1
Where the paper says it

5 Instantiating Demographic Coherence with a Metric . 16 5 Algorithms that Enforce Wasserstein Demographic Coherence 17 5.

Acknowledgments and References

The authors thank Adam Smith for insightful comments and feedback that helped improve this work. The references cover a wide range of related works in differential privacy, attacks, generalization, and auditing techniques. p. 1

Where the paper says it

3 Differentially Private Algorithms Enforce Demographic Coherence . 26 6 Acknowledgments 27 A Comparison to Perfect Generalization 33 B Differential Privacy implies Bounded Max-Information: Sampling without Replacement B.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Demographic coherence enforcement allows data curators to ensure that predictors trained using private reports will be demographically coherent, capturing privacy violations arising from inferences incoherent with respect to demographic patterns in the data. This enables rigorous analysis of algorithms based on a necessary condition for privacy, rather than relying solely on sufficient conditions like differential privacy.

  2. The framework provides a natural translation to an experimental setup for comparing the effects of various algorithms for privacy preserving data release by measuring incoherence via Wasserstein distance over sub-populations and lenses. This facilitates building practical intuition and making tangible assessments of risks in real-world deployments.

  3. The system can be designed to enforce (alpha, beta)-Wasserstein coherence using pure differential privacy or approximate differential privacy algorithms, providing concrete parameter conversions for practitioners. This allows data curators to suggest specific epsilon values based on desired coherence constraints rather than relying on abstract notions of global privacy guarantees.

Abstract

The technical literature about data privacy largely consists of two complementary approaches: formal definitions of conditions sufficient for privacy preservation and attacks that demonstrate privacy breaches. Differential privacy is an accepted standard in the former sphere. However, differential privacy's powerful adversarial model and worst-case guarantees may make it too stringent in some situations, especially when achieving it comes at a significant cost to data utility. Meanwhile, privacy attacks aim to expose real and worrying privacy risks associated with existing data release processes but often face criticism for being unrealistic. Moreover, the literature on attacks generally does not identify what properties are necessary to defend against them. We address the gap between these approaches by introducing demographic coherence, a condition inspired by privacy attacks that we argue is necessary for data privacy. This condition captures privacy violations arising from inferences about individuals that are incoherent with respect to the demographic patterns in the data. Our framework focuses on confidence rated predictors, which can in turn be distilled from almost any data-informed process. Thus, we capture privacy threats that exist even when no attack is explicitly being carried out. Our framework not only provides a condition with respect to which data release algorithms can be analysed but suggests natural experimental evaluation methodologies that could be used to build practical intuition and make tangible assessment of risks. Finally, we argue that demographic coherence is weaker than differential privacy: we prove that every differentially private data release is also demographically coherent, and that there are demographically coherent algorithms which are not differentially private.

Sources

Related papers