Sparse Kernel Mechanisms for Locally Differentially Private Discrete Channels
Abstract
We study sparse locally private discrete mechanisms generated by a nonnegative kernel and an input-dependent admissible output support. The support set is intentionally small relative to the ambient alphabet and acts as a mechanism-design parameter. This formulation covers metric-ball supports, sparse exponential mechanisms, sparse staircase mechanisms, sparse randomized response, sparse additive kernels such as Skellam perturbations, and Poisson-binomial-inspired bounded-support channels. We give a general exact characterization of pure and approximate local differential privacy for this sparse-kernel class. Pure local differential privacy forces all supports to coincide, so genuinely input-dependent sparse supports are incompatible with pure privacy. In the approximate regime, the privacy defect decomposes exactly into support leakage and overlap excess loss. We instantiate the formula for several discrete mechanism families. For sparse staircase mechanisms, a shell-ratio condition eliminates overlap excess loss. For graph-metric supports, overlap of metric balls is necessary for nontrivial privacy. For sparse randomized response, the support-leakage term has a closed form in terms of support mismatch. For generic radius-truncated additive kernels and, in particular, sparse Skellam mechanisms, we obtain exact finite-support formulas in terms of the Skellam CDF and an exact Bessel-ratio overlap condition. Numerical evaluations illustrate how support radius and kernel shape separately affect support leakage and overlap excess loss.
Related
- Optimal quantum locally differentially private mechanisms in the high-privacy regime
- Differentially Private Average Treatment Effect Estimation by Propensity Score Blocking
- Differentially Private Synthetic Data via Generalized Moment Matching
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
BibTeX
@misc{zamani2026sparse,
title = {{Sparse Kernel Mechanisms for Locally Differentially Private Discrete Channels}},
author = {Amirreza Zamani and Parastoo Sadeghi and Mikael Skoglund},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07993},
eprint = {2610.07993},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07993},
}
RIS
TY - UNPB
TI - Sparse Kernel Mechanisms for Locally Differentially Private Discrete Channels
AU - Amirreza Zamani
AU - Parastoo Sadeghi
AU - Mikael Skoglund
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07993
UR - https://arxiv.org/abs/2610.07993
AB - We study sparse locally private discrete mechanisms generated by a nonnegative kernel and an input-dependent admissible output support. The support set is intentionally small relative to the ambient alphabet and acts as a mechanism-design parameter. This formulation covers metric-ball supports, sparse exponential mechanisms, sparse staircase mechanisms, sparse randomized response, sparse additive kernels such as Skellam perturbations, and Poisson-binomial-inspired bounded-support channels. We give a general exact characterization of pure and approximate local differential privacy for this sparse-kernel class. Pure local differential privacy forces all supports to coincide, so genuinely input-dependent sparse supports are incompatible with pure privacy. In the approximate regime, the privacy defect decomposes exactly into support leakage and overlap excess loss. We instantiate the formula for several discrete mechanism families. For sparse staircase mechanisms, a shell-ratio condition eliminates overlap excess loss. For graph-metric supports, overlap of metric balls is necessary for nontrivial privacy. For sparse randomized response, the support-leakage term has a closed form in terms of support mismatch. For generic radius-truncated additive kernels and, in particular, sparse Skellam mechanisms, we obtain exact finite-support formulas in terms of the Skellam CDF and an exact Bessel-ratio overlap condition. Numerical evaluations illustrate how support radius and kernel shape separately affect support leakage and overlap excess loss.
ER -