A bounded-noise mechanism for differential privacy
We present an asymptotically optimal $(\epsilon,\delta)$ differentially private mechanism for answering multiple, adaptively asked, $\Delta$-sensitive queries, settling the conjecture of Steinke and Ullman [2020]. Our algorithm has a significant advantage that it adds independent bounded noise to each query, thus providing an absolute error bound. Additionally, we apply our algorithm in adaptive data analysis, obtaining an improved guarantee for answering multiple queries regarding some underlying distribution using a finite sample. Numerical computations show that the bounded-noise mechanism outperforms the Gaussian mechanism in many standard settings.
Code (1)
Similar Papers 제목 키워드 기반
Learning Numeric Optimal Differentially Private Truncated Additive Mechanisms
Differentially private (DP) mechanisms face the challenge of providing accurate results while protecting their inputs: the privacy-utility trade-off. A simple but powerful technique for DP adds noise to sensitivity-bound…
SensitivityGeneral Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation
We investigate unbiased high-dimensional mean estimators in differential privacy. We consider differentially private mechanisms whose expected output equals the mean of the input dataset, for every dataset drawn from a f…
Noiseless Privacy
In this paper, we define noiseless privacy, as a non-stochastic rival to differential privacy, requiring that the outputs of a mechanism (i.e., function composition of a privacy-preserving mapping and a query) can attain…
Privacy PreservingQuantizationTwo-sample testingGuaranteed Privacy-Preserving $\mathcal{H}_{\infty}$-Optimal Interval Observer Design for Bounded-Error LTI Systems
This paper furthers current research into the notion of guaranteed privacy, which provides a deterministic characterization of the privacy of output signals of a dynamical system or mechanism. Unlike stochastic different…
Privacy PreservingQ-ShiftDP: A Differentially Private Parameter-Shift Rule for Quantum Machine Learning
Quantum Machine Learning (QML) promises significant computational advantages, but preserving training data privacy remains challenging. Classical approaches like differentially private stochastic gradient descent (DP-SGD…
Quantum Machine Learning