Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy
For researchers in privacy and Markov chain theory, this work provides tighter theoretical bounds on contraction for discrete mechanisms, extending beyond LDP to any discrete kernel.
The paper derives achievable bounds on Dobrushin coefficients for Markov kernels with bounded pointwise maximal leakage (PML) when the minimum probability mass is bounded away from zero, recovering local differential privacy (LDP) as a special case. The results yield tighter contraction bounds for LDP mechanisms and extend to general f-divergences.
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.