Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

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

Nadia: Today's paper: "Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy".

Elias: The gist We investigate Dobrushin coefficients of discrete Markov kernels that have bounded pointwise maximal leakage (PML) with respect to all distributions with a minimum probability mass bounded away from…

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: So, we're looking at this paper called "Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy" and the authors are Leonhard Grosse, Sara Saeidian, Tobias J. Oechtering, and Mikael Skoglund. Elias you know what the main idea is?

Elias: Yeah, it's about looking at discrete Markov kernels—which are like random processes that take an input to an output—and quantifying their privacy using something called bounded pointwise maximal leakage or PML <ref:2601.09498#pg2>. The authors use this PML concept to define a privacy guarantee that goes beyond just the standard local differential privacy, which is what they call LDP <ref:2601.09498#pg3>.

Priya: What does that mean for us practically? Basically, they are trying to find a way to measure how much information leaks when you use these mechanisms even when the standard LDP constraints might be too strict for some applications. They're defining an (ε, c)-PML by restricting the privacy check based on a minimum probability mass bounded away from zero by some constant c greater than zero <ref:2601.09498#pg2>.

Nadia: Exactly, and they say that as that constant c goes to zero, this PML definition smoothly recovers the standard LDP we already know about <ref:2601.09498#pg1>. So it’s a way to interpolate between the two.

Elias: The paper claims they can derive achievable bounds on contraction in terms of these kernel PML guarantees, and they actually provide some mechanism constructions that hit those specific bounds <ref:2601.09498#pg2>.

Priya: And what are these bounds showing? They establish that the maximal Dobrushin coefficient has a certain limit based on the PML guarantee for any epsilon greater than or equal to zero and c less than or equal to one over N <ref:2601.09498#pg1>. It looks like they’re giving us some concrete limits on how much two distributions can move apart under these private mechanisms.

Nadia: And they get a specific formula for this contraction coefficient, which is ηTV(ε, c) less than or equal to min of e epsilon minus one over e epsilon times one over N c plus one and one <ref:2601.09498#pg1>. That’s the main statement they make about how good these mechanisms can be.

Elias: They then go a step further by characterizing the contraction coefficients of private kernels when the privacy guarantee isn't super strict, showing that if epsilon is greater than or equal to log of two over N c, then the supremum of K in M(ε, c) times ηf (K) for any convex and twice-differentiable f is one <ref:2601.09498#pg1>.

Priya: That part is interesting because it implies that for total variation distance, if epsilon is greater than or equal to log of two over N c, then ηTV(ε, c) equals one <ref:2601.09498#pg1>. So they're saying that under these conditions, the privacy guarantee itself dictates the worst-case contraction rate.

Paper summary: Nadia: And when epsilon is smaller than log of two over N c, the paper gives you a bound: ηTV(ε, c) is less than or equal to e raised to the power of epsilon minus one over e raised to the power of epsilon times one minus N c plus one <ref:2601.09498#pg1>. They even show this bound can be achieved by looking at mechanisms with a binary output alphabet, meaning two possible outcomes.

Elias: Moving beyond total variation distance, they extend these results to general f-divergences using something called Binette’s inequality <ref:2601.09498#pg2>. This leads to data processing inequalities for general f-divergences, giving a bound on the divergence Df of K o PX K o QX <ref:2601.09498#pg3>.

Priya: That general inequality is powerful because it gives us bounds for relative entropy and Hellinger divergence specifically in corollary one and corollary two <ref:2601.09498#pg3>. It illustrates how these (ε, c)-PML mechanisms can reduce the effective sample size by a factor related to that private Dobrushin coefficient Ξ(ε, c) <ref:2601.09498#pg3>.

Nadia: So for someone who just listens to the show, it means that if you use these PML mechanisms, you get tighter bounds on how much your data distribution changes after privacy processing than the standard LDP constraints might suggest <ref:2601.09498#pg3>.

Elias: And they apply these findings to minimax estimation risk as well, showing a risk R star greater than or equal to one over two times exp of minus n Xi(ε, c) log of one minus four c e raised to the power of epsilon plus one over delta <ref:2601.09498#pg3>. This shows that if you want a certain risk level, the required sample size n is proportional to one over Ξ(ε, c) times delta <ref:2601.09498#pg3>.

Priya: It’s clear that this work focuses on tightening the bounds for mechanisms satisfying LDP and extends beyond that to any discrete kernel <ref:2601.09498#pg1>. The authors flag their limitation, though, they state all omitted proofs are in the appendix <ref:2601.09498#pg2>, which is just standard for a paper like this.

Nadia: So to wrap up on the paper "Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy," it’s essentially providing tighter bounds on how much privacy mechanisms can contract distributions, even when you aren't strictly enforcing LDP <ref:2601.09498#pg1>.

Elias: The authors are using the concept of pointwise maximal leakage to generalize LDP and then showing how this new framework leads to stronger data processing inequalities for general f-divergences <ref:2601.09498#pg3>.

Priya: And the implication is that these bounds can be used in minimax estimation settings, telling us how sample size scales with the required risk level through a factor related to this private Dobrushin coefficient <ref:2601.09498#pg3>.

Nadia: So for listeners, this paper shows that we can get more precise quantification of privacy leakage by moving from just LDP to this PML framework <ref:2601.09498#pg1>.

Elias: And it suggests that understanding the contraction coefficient of a kernel in this private context is key to analyzing the risks introduced by these mechanisms <ref:2601.09498#pg3>.

Conclusion: Nadia: So we're wrapping up on this paper about Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy by Grosse, Saeidian, Oechtering, and Skoglund.

Elias: The main thing is they used pointwise maximal leakage or PML to define a privacy guarantee that goes beyond the standard local differential privacy we already know.

Priya: It's about finding a way to measure how much information leaks when you use these mechanisms even when the standard LDP constraints might be too strict for some applications.

Nadia: Right, so they’re looking at those worst-case posterior risks that averaging might hide, which is what PML captures.

Elias: They define this (epsilon, c)-PML by restricting the privacy check based on a minimum probability mass bounded away from zero by some constant c greater than zero.

Priya: That definition allows for a smooth interpolation between an epsilon-PML for only the uniform distribution and epsilon-LDP when c equals zero.

Nadia: And they derived actual bounds on contraction, which is basically how much the distributions can move apart under these privacy guarantees.

Elias: They showed that the maximal Dobrushin coefficient has a certain limit based on that PML guarantee for any epsilon greater than or equal to zero and c less than or equal to one over N.

Priya: The main result they state is that this contraction coefficient is bounded by the minimum of e to the power of epsilon minus one over e to the power of epsilon times one minus N c plus one and one.

Nadia: That’s a concrete limit on how much two distributions can change in terms of total variation distance under these private settings.

Elias: They also characterized when that contraction coefficient hits exactly one, which happens if epsilon is greater than or equal to the logarithm of two over N c.

Priya: So, if epsilon is big enough relative to c, the privacy guarantee itself dictates the worst-case contraction rate for your data.

Nadia: And they extended these results to general f-divergences using Binette’s inequality, which gives us stronger bounds on divergence measures.

Elias: That means we get data processing inequalities for general f-divergences, and those inequalities show how these PML mechanisms reduce the effective sample size by a factor related to that private Dobrushin coefficient.

Priya: Specifically for relative entropy and Hellinger divergence, it shows that the mechanism reduces the sample size by a factor proportional to that private Dobrushin coefficient.

Nadia: And they apply this to minimax estimation risk, showing how the required sample size scales with the desired risk level through a factor related to that coefficient.

Elias: So essentially, this paper shows we can get tighter bounds on how much privacy mechanisms can contract distributions, even when you aren't strictly enforcing LDP.

Priya: It's about using this PML framework to get more precise quantification of privacy leakage by moving beyond just LDP constraints.

Nadia: And it suggests that understanding the contraction coefficient of a kernel in this private context is key to analyzing the risks introduced by these mechanisms.