Timezone: »

 
Poster
Minimax Optimal Estimation of Approximate Differential Privacy on Neighboring Databases
Xiyang Liu · Sewoong Oh

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #93
in Applications -- Privacy, Anonymity, and Security »

Differential privacy has become a widely accepted notion of privacy, leading to the introduction and deployment of numerous privatization mechanisms. However, ensuring the privacy guarantee is an error-prone process, both in designing mechanisms and in implementing those mechanisms. Both types of errors will be greatly reduced, if we have a data-driven approach to verify privacy guarantees, from a black-box access to a mechanism. We pose it as a property estimation problem, and study the fundamental trade-offs involved in the accuracy in estimated privacy guarantees and the number of samples required. We introduce a novel estimator that uses polynomial approximation of a carefully chosen degree to optimally trade-off bias and variance. With n samples, we show that this estimator achieves performance of a straightforward plug-in estimator with n*log(n) samples, a phenomenon referred to as effective sample size amplification. The minimax optimality of the proposed estimator is proved by comparing it to a matching fundamental lower bound.

Keywords: Information Theory · Learning Theory · Theory · Applications -> Privacy, Anonymity, and Security; Theory
[ Paper]  [ Poster] 

Author Information

Xiyang Liu (University of Washington)
Sewoong Oh (University of Washington)

More from the Same Authors