Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

• URL: http://arxiv.org/abs/2601.09498v1
• Date: Wed, 14 Jan 2026 14:03:42 GMT
• Title: Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy
• Authors: Leonhard Grosse, Sara Saeidian, Tobias J. Oechtering, Mikael Skoglund,
• Abstract summary: We derive achievable bounds on contraction in terms of a kernels PML guarantees.<n>We extend the results to general $f$-divergences by an application of Binette's inequality.
• Score: 36.33156483258328
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Analysis of Shuffling Beyond Pure Local Differential Privacy [2.4264122405649045]
  Shuffling is a powerful way to amplify privacy of a local randomizer in private distributed data analysis.<n>We develop an analysis that applies to a broad class of local randomizers under mild regularity assumptions.<n>We use an FFT-based algorithm for computing the blanket divergence at finite $n$.
  arXiv  Detail & Related papers  (2026-01-27T03:35:03Z)
• Context-aware Privacy Bounds for Linear Queries [18.643148110719736]
  We revisit the privacy analysis of the Laplace mechanism through the lens of pointwise maximal leakage.<n>We demonstrate that the distribution-agnostic definition of the DP framework often mandates excessive noise.
  arXiv  Detail & Related papers  (2026-01-06T09:34:04Z)
• Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
  We study the problem of spectral graph clustering under edge differential privacy (DP)<n>Specifically, we develop three mechanisms: (i) graph perturbation via randomized edge flipping combined with adjacency matrix shuffling, which enforces edge privacy; (ii) private graph projection with additive Gaussian noise in a lower-dimensional space to reduce dimensionality and computational complexity; and (iii) a noisy power iteration method that distributes Gaussian noise across iterations to ensure edge DP while maintaining convergence.
  arXiv  Detail & Related papers  (2025-10-08T15:30:27Z)
• Risk Bounds for Mixture Density Estimation on Compact Domains via the $h$-Lifted Kullback--Leibler Divergence [2.8074364079901017]
  We introduce the $h$-lifted Kullback--Leibler (KL) divergence as a generalization of the standard KL divergence.<n>We develop a procedure for the computation of the corresponding maximum $h$-lifted likelihood estimators.
  arXiv  Detail & Related papers  (2024-04-19T02:31:34Z)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints. We derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$.
  arXiv  Detail & Related papers  (2024-01-17T09:23:25Z)
• Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions [49.726408540784334]
  Key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We show that our pessimistic estimate is the best possible among all pessimistic estimates.
  arXiv  Detail & Related papers  (2022-07-10T04:25:02Z)
• The Poisson binomial mechanism for secure and private federated learning [19.399122892615573]
  We introduce a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism.
  arXiv  Detail & Related papers  (2022-07-09T05:46:28Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• Local Differential Privacy Is Equivalent to Contraction of $E_\gamma$-Divergence [7.807294944710216]
  We show that LDP constraints can be equivalently cast in terms of the contraction coefficient of the $E_gamma$-divergence. We then use this equivalent formula to express LDP guarantees of privacy mechanisms in terms of contraction coefficients of arbitrary $f$-divergences.
  arXiv  Detail & Related papers  (2021-02-02T02:18:12Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.