Skip to content
Preprint

Exact Privacy--Distortion Design of Support-Constrained Randomized Response

Oct 2026 · 0 citations · 11 references
Computer Science Mathematics

TL;DR

Under approximate local privacy restricted to input pairs at distance at most $H$, it is proved that stringent approximate privacy forces the support size to scale as $\Omega(H/\delta)$.

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 $\Omega(H/\delta)$. Deterministic evaluations illustrate the resulting tradeoff.

View source

Similar papers

#machine learning Preprint Oct 2026

Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy

AO-Pri-BAI is proposed, an adaptive algorithm that maintains private running estimates through Laplace-tree mechanisms and learns a sampling design through a min--max interaction between hard alternatives and arm allocations that satisfies pure $\epsilon$-differential privacy.

Ke-Qin Chen, Jie Bian, Yu-Lian Wu et al. · 0 citations
Preprint Sep 2026

Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

This work generalizes the implicit representation framework of Gupta et al. (SODA 2010) by allowing the encoder to run in fixed-parameter tractable time, and provides representation-dependent lower bounds that hold even for larger $\epsilon$.

Pritish Kamath, Ravi Kumar, Pasin Manurangsi · 1 citation
Preprint Oct 2026

Residual-Information Generalization Bounds Under Selective Privacy: Extended Version

This work derives complementary task-compression and individual-sample refinements, identifies a sharp obstruction showing why selective privacy alone need not give a vanishing certificate, and invert the bound to obtain the exact leakage allowance for a prescribed generalization tolerance.

A. Zamani, Parastoo Sadeghi, Mikael Skoglund · 0 citations
Review Oct 2026

Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits

Saturated Propose-test-release, a general mechanism that privately releases the output of a discrete selector with probability one once its stability certificate reaches a finite threshold, is introduced and a computable support-stability score is constructed.

Jian-Zhong Gu, T. Cai · 1 citation
Preprint Oct 2026

Diffusion Sensitivity Geometry and Strong Duality for Optimal Privacy-Utility Tradeoffs

A framework for the optimal privacy-utility tradeoff of ideal diffusion denoisers is developed, replacing conservative bounds with exact sensitivity characterizations and provably optimal noise calibration, and exact privacy guarantees for R\'enyi, approximate, and Gaussian differential privacy are obtained.

Tue Do, Daniel Alabi · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.