Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

arXiv:2601.09498 · cs.IT, cs.CR, math.IT · Submitted 2026-01-14 · Read on arXiv

Listen

Transcript

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.

KTH Royal Institute of Technology · Inria Saclay

cs.IT, cs.CR, math.IT

Submitted: 2026-01-14

Updated: 2026-07-02

Comments: presented at ISIT 2026; full version including appendices

Journal ref: 2026 IEEE International Symposium on Information Theory (ISIT)

DOI: 10.1109/ISIT62367.2026.11653807

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

Importance score: 71/100

The gist: 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

Key concepts

Pointwise Maximal Leakage (PML): PML quantifies the worst-case leakage of an individual outcome by considering all distributions with a minimum probability mass greater than zero. It is a privacy measure that captures risks beyond simple averaging, allowing for smoother interpolation between uniform distribution privacy and LDP.
Dobrushin Coefficient ($\eta_{TV}$): This coefficient measures how much the total variation distance between two distributions shrinks after passing them through a specific Markov kernel. It quantifies the contraction or 'mixing' effect of the mechanism on the input data distribution.
$f$-Divergence Contraction Coefficient ($\eta_f(K)$): This coefficient measures how much a general $f$-divergence (a measure of distance between distributions) contracts when distributions are processed by a kernel. It is used to derive strong data processing inequalities for various divergence measures, extending the analysis beyond total variation.

Terminology

Differential Privacy — 15× in this paper · explained in 4 episodes
Elias — 14× in this paper · explained in 2 episodes
Nadia — 14× in this paper · explained in 2 episodes
Generalization — 7× in this paper · explained in 13 episodes
Local Differential Privacy (LDP) — 4× in this paper · explained in 3 episodes
International Symposium on Information Theory — 3× in this paper
Differentially Private — 2× in this paper · explained in 3 episodes
Information Leakage — 2× in this paper · explained in 2 episodes
Loss Function — 1× in this paper · explained in 2 episodes
Papers — 1× in this paper · explained in 3 episodes
Sample Complexity — 1× in this paper · explained in 20 episodes

Summary

The gist

How it works

The study focuses on quantifying privacy using pointwise maximal leakage (PML) instead of the more restrictive local differential privacy (LDP) when LDP guarantees are too strict for certain applications. PML is built on concrete threat-models and quantifies leakage of individual outcomes Y = y, capturing worst-case posterior risks that averaging might hide. The privacy quantification of PML depends both on the mechanism K and the distribution PX of the private random variable X.

The paper introduces a generalization of LDP based on pointwise maximal leakage, defining an (ε, c)-PML by restricting the supremum in Proposition 1 from P(X) to the set QX (c), where QX (c) is defined by minx PX(x) ≥ c. This definition allows for smooth interpolation between an ε-PML for only the uniform distribution and ε-LDP when c = 0.

Key Results and Bounds

The main statement of the work establishes bounds on the maximal Dobrushin coefficient given an (ε, c)-PML guarantee for any ε ≥ 0, c ∈ (0, 1/N]. This is expressed as ηTV(ε, c) ≤ min (e ε − 1 / e ε(1 − N c) + 1, 1).

The work further characterizes the contraction coefficients of private kernels when the privacy-guarantee is not strict by showing that if ε ≥ log(2/N c), then sup K∈M(ε,c) ηf (K) = 1 for any convex and twice-differentiable f. This implies that for total variation distance, if ε ≥ log(2/N c), then ηTV(ε, c) = 1.

When ε < log(2/N c), the contraction coefficient is bounded by Theorem 3: ηTV(ε, c) ≤ e(ε − 1 / e ε(1 − N c) + 1). This bound is achieved by considering mechanisms in M(ε, c) with a binary output alphabet Y = 2.

Extension to General f-Divergences

The paper extends these bounds to general f-divergences using Binette’s inequality, leading to data-processing inequalities for general f-divergences. The resulting bound on the divergence Df (K ◦ PXK ◦ QX) is given by Df (K ◦ PXK ◦ QX) ≤ ηTV(ε, c) fΓmin(ε, c) / (1 − Γmin(ε, c)) + fΓmax(ε, c) / Γmax(ε, c) - 1/δ.

Specific bounds are provided for relative entropy and Hellinger divergence in Corollary 1 and Corollary 2. These corollaries illustrate how the (ε, c)-PML mechanisms reduce the effective sample size by a factor proportional to the private Dobrushin coefficient Ξ(ε, c).

Application in Minimax Estimation

The bounds on the private Dobrushin coefficient are used to derive results on minimax estimation risk. For example, the minimax risk R⋆ ≥ 1/2 exp(- n Ξ(ε, c) log(1 − 4c)e ε + 1 / δ). This demonstrates that to achieve a specific risk level, the required sample size n is proportional to 1/Ξ(ε, c) δ.

The analysis concludes by showing how these bounds can be applied in a minimax estimation setting, where the private Dobrushin coefficient Ξ(ε, c) dictates the reduction in effective sample size. This shows that (ε, c)-PML mechanisms reduce the effective sample size by a factor proportional to the private Dobrushin coefficient Ξ(ε, c).

The paper presents achievable bounds on the Dobrushin coefficients of mechanisms satisfying PML for any data-generating distribution PX with minimum probability mass bounded away from zero by some constant c > 0, that is, for which minx PX(x) ≥ c. Further, we use the result to obtain strong data processing inequalities for general f-divergences. All omitted proofs can be found in the appendix.

The contraction coefficient of a kernel with respect to the total variation distance is expressed in computable form as ηTV(K) = sup x!=x' TV(KY X=xKY X=x'). The main statement of this work is the following. Let 0 < c ≤ 1/N and ε ≥ 0. If a Markov kernel K ∈ M(ε, c), that is, if K satisfies (ε, c)-PML, then ηTV(ε, c) ≤ min (e ε − 1 / e ε(1 − N c) + 1, 1). The remainder of this section is dedicated to the proof of this theorem.

Theorem 2 and Theorem 3 together show the statement in Theorem 1. We conclude this section with an example. The paper presents achievable bounds on the Dobrushin coefficients of mechanisms satisfying PML for any data-generating distribution PX with minimum probability mass bounded away from zero by some constant c > 0, that is, for which minx PX(x) ≥ c. Further, we use the result to obtain strong data processing inequalities for general f-divergences. All omitted proofs can be found in the appendix. The bound in Corollary 1 is shown in Figure 1 for two different kernels K1 and K2, we define them in the following example. Note that K1 also satisfies log(15)-LDP. Since K2 does not satisfy any finite LDP guarantee, such a comparison is not possible in this case. The bound in Corollary 2 is shown in Figure 1(b) for K2. Finally, the following example shows how the obtained bounds can be applied in a minimax estimation setting.

--- Page 5 ---

The contraction coefficient of a kernel with respect to some f-divergence Df quantifies “how much closer” two distributions will become in Df after being passed through the kernel. In order to further quantify the gap between the two sides of the DPI, consider the contraction coefficient of a kernel is defined as ηf (K) = sup PX!=QX Df (K ◦ PXK ◦ QX) Df(PXQX). It is known [10] that for any kernel K, ηχ2 (K) ≤ ηf (K) ≤ ηTV(K), where ηχ2 (K) denotes the case f(t) = (t − 1) squared.

The LDP guarantee of any Markov kernel K mapping from X to Y can be expressed as LDP(K) = sup y∈Y sup PX∈P(X) lK×PX (X → y) <ref:2601.

Improvements for AI systems

textbf Achievement of tighter minimax risk bounds for LDP mechanisms: The paper provides achievable bounds on contraction in terms of a kernel’s PML guarantees, allowing for tighter bounds for mechanisms satisfying LDP than those derived from standard LDP assumptions. This enables the application of these coefficients to find private minimax risk bounds by reduction to a hypothesis testing problem.
textbf Extension of privacy guarantees beyond strict LDP: The framework allows for quantifying privacy using (ε, c)-PML, which generalizes LDP by restricting the supremum in Proposition 1 from the entire probability simplex to a set where minx PX(x) ≥ c. This enables mechanism constructions that satisfy LDP and extends beyond the LDP regime to any discrete kernel.
textbf Robust privacy quantification for mechanisms with zero-probability assignments: The (ε, c)-PML definition allows it to quantify privacy leakage even when a mechanism has zero probability assignments, addressing the issue where LDP measure is infinite due to kernels containing zero elements. This enables reliable risk assessment for mechanisms like those in Example 1.
textbf Application of general f-divergence bounds: The work enables obtaining bounds on general f-divergences using the inequality derived from Binette’s generalization of reverse Pinsker’s inequality, yielding results like D(K ◦ PXK ◦ QX) ≤ Ξ(ε, c) log (1 − N c)e + 1 δ for relative entropy. This allows for privacy-preserving estimation across a wider class of statistical divergences.
textbf Improved sample complexity in minimax estimation: The derived bounds on the private Dobrushin coefficient, specifically ηTV(ε, c), allow researchers to show that (ε, c)-PML mechanisms reduce the effective sample size by a factor proportional to the private Dobrushin coefficient Ξ(ε, c). This leads to a requirement for sample size of n = omega 1/Ξ(ε, c) δ to achieve a target risk.

Abstract

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 zero by a constant c>0. This definition recovers local differential privacy (LDP) for c to 0. We derive achievable bounds on contraction in terms of a kernels PML guarantees, and provide mechanism constructions that achieve the presented bounds. Further, we extend the results to general f-divergences by an application of Binette's inequality. Our analysis yields tighter bounds for mechanisms satisfying LDP and extends beyond the LDP regime to any discrete kernel.