Exact Privacy--Distortion Design of Support-Constrained Randomized Response
Abstract
Full-support local randomizers can incur unnecessary reporting distortion on ordered alphabets. We study randomized response whose output is restricted to a radius-t neighborhood of the private input. Input-dependent supports create privacy leakage at their boundaries, so ordinary likelihood-ratio calibration is no longer sufficient. Under approximate local privacy restricted to input pairs at distance at most H, we derive the exact hockey-stick defect of the mechanism. We then solve the joint design of the truthful probability, off-truth probability, and support radius. The fixed-radius optimum is available in closed form, while the global optimum requires only a one-dimensional integer search. We characterize both the privacy floor and its inverse, namely the smallest defect attainable under a reporting-distortion budget. We further prove that stringent approximate privacy forces the support size to scale as Ω(H/δ). Deterministic evaluations illustrate the resulting tradeoff.
Related
- A Self-Coupling Gaussian Extremal Inequality for Information-Constrained Optimal Transport with Applications to Rate-Distortion-Perception
- Privacy-Constrained Function Computation in Distributed Databases
- Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits
- An Intersection Cutting Plane Algorithm for Chance-Constrained Programs with Finite Support
- LASER: Latent Space Adjoint Matching for Support-Constrained Entropy-Regularized Offline RL
BibTeX
@misc{zamani2026exact,
title = {{Exact Privacy--Distortion Design of Support-Constrained Randomized Response}},
author = {Amirreza Zamani and Parastoo Sadeghi and Mikael Skoglund},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15972},
eprint = {2610.15972},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15972},
}
RIS
TY - UNPB
TI - Exact Privacy--Distortion Design of Support-Constrained Randomized Response
AU - Amirreza Zamani
AU - Parastoo Sadeghi
AU - Mikael Skoglund
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15972
UR - https://arxiv.org/abs/2610.15972
AB - Full-support local randomizers can incur unnecessary reporting distortion on ordered alphabets. We study randomized response whose output is restricted to a radius-t neighborhood of the private input. Input-dependent supports create privacy leakage at their boundaries, so ordinary likelihood-ratio calibration is no longer sufficient. Under approximate local privacy restricted to input pairs at distance at most H, we derive the exact hockey-stick defect of the mechanism. We then solve the joint design of the truthful probability, off-truth probability, and support radius. The fixed-radius optimum is available in closed form, while the global optimum requires only a one-dimensional integer search. We characterize both the privacy floor and its inverse, namely the smallest defect attainable under a reporting-distortion budget. We further prove that stringent approximate privacy forces the support size to scale as Ω(H/δ). Deterministic evaluations illustrate the resulting tradeoff.
ER -