Smooth Sensitivity Revisited: Towards Optimality
<|reference_start|>Smooth Sensitivity Revisited: Towards Optimality: Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a given query $q$ on the given input $D$ and releases $q(D)$ with noise added proportional to this smooth sensitivity. One question remains: what distribution should we pick the noise from?   In this paper, we give a new class of distributions suitable for the use with smooth sensitivity, which we name the PolyPlace distribution. This distribution improves upon the state-of-the-art Student's T distribution in terms of standard deviation by arbitrarily large factors, depending on a "smoothness parameter" $\gamma$, which one has to set in the smooth sensitivity framework. Moreover, our distribution is defined for a wider range of parameter $\gamma$, which can lead to significantly better performance.   Moreover, we prove that the PolyPlace distribution converges for $\gamma \rightarrow 0$ to the Laplace distribution and so does its variance. This means that the Laplace mechanism is a limit special case of the PolyPlace mechanism. This implies that out mechanism is in a certain sense optimal for $\gamma \to 0$.<|reference_end|>
@article{hladík2024smooth,
    title={Smooth Sensitivity Revisited: Towards Optimality},
    author={Richard Hlad'ik, Jakub Tv{e}tek},
    journal={arXiv preprint arXiv:2407.05067},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.05067},
    primaryClass={cs.CR}
}