Timezone: »
Spotlight
A Central Limit Theorem for Differentially Private Query Answering
Jinshuo Dong · Weijie Su · Linjun Zhang
@
Perhaps the single most important use case for differential privacy is to privately answer numerical queries, which is usually achieved by adding noise to the answer vector. The central question is, therefore, to understand which noise distribution optimizes the privacy-accuracy trade-off, especially when the dimension of the answer vector is high. Accordingly, an extensive literature has been dedicated to the question and the upper and lower bounds have been successfully matched up to constant factors (Bun et al.,2018; Steinke & Ullman, 2017). In this paper, we take a novel approach to address this important optimality question. We first demonstrate an intriguing central limit theorem phenomenon in the high-dimensional regime. More precisely, we prove that a mechanism is approximately Gaussian Differentially Private (Dong et al., 2021) if the added noise satisfies certain conditions. In particular, densities proportional to $\mathrm{e}^{-\|x\|_p^\alpha}$, where $\|x\|_p$ is the standard $\ell_p$-norm, satisfies the conditions. Taking this perspective, we make use of the Cramer--Rao inequality and show an "uncertainty principle"-style result: the product of privacy parameter and the $\ell_2$-loss of the mechanism is lower bounded by the dimension. Furthermore, the Gaussian mechanism achieves the constant-sharp optimal privacy-accuracy trade-off among all such noises. Our findings are corroborated by numerical experiments.
Author Information
Jinshuo Dong (University of Pennsylvania)
Weijie Su (Computer and Information Science and Wharton, University of Pennsylvania)
Linjun Zhang (Rutgers University)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: A Central Limit Theorem for Differentially Private Query Answering »
Thu. Dec 9th 04:30 -- 06:00 PM Room Virtual
More from the Same Authors
-
2022 Poster: The alignment property of SGD noise and how it helps select flat minima: A stability analysis »
Lei Wu · Mingze Wang · Weijie Su -
2022 Poster: C-Mixup: Improving Generalization in Regression »
Huaxiu Yao · Yiping Wang · Linjun Zhang · James Zou · Chelsea Finn -
2021 Poster: Adversarial Training Helps Transfer Learning via Better Representations »
Zhun Deng · Linjun Zhang · Kailas Vodrahalli · Kenji Kawaguchi · James Zou -
2021 Poster: You Are the Best Reviewer of Your Own Papers: An Owner-Assisted Scoring Mechanism »
Weijie Su -
2021 Poster: Imitating Deep Learning Dynamics via Locally Elastic Stochastic Differential Equations »
Jiayao Zhang · Hua Wang · Weijie Su -
2020 Poster: Label-Aware Neural Tangent Kernel: Toward Better Generalization and Local Elasticity »
Shuxiao Chen · Hangfeng He · Weijie Su -
2020 Poster: The Complete Lasso Tradeoff Diagram »
Hua Wang · Yachong Yang · Zhiqi Bu · Weijie Su -
2020 Spotlight: The Complete Lasso Tradeoff Diagram »
Hua Wang · Yachong Yang · Zhiqi Bu · Weijie Su -
2019 : Poster Session »
Clement Canonne · Kwang-Sung Jun · Seth Neel · Di Wang · Giuseppe Vietri · Liwei Song · Jonathan Lebensold · Huanyu Zhang · Lovedeep Gondara · Ang Li · FatemehSadat Mireshghallah · Jinshuo Dong · Anand D Sarwate · Antti Koskela · Joonas Jälkö · Matt Kusner · Dingfan Chen · Mi Jung Park · Ashwin Machanavajjhala · Jayashree Kalpathy-Cramer · · Vitaly Feldman · Andrew Tomkins · Hai Phan · Hossein Esfandiari · Mimansa Jaiswal · Mrinank Sharma · Jeff Druce · Casey Meehan · Zhengli Zhao · Hsiang Hsu · Davis Railsback · Abraham Flaxman · · Julius Adebayo · Aleksandra Korolova · Jiaming Xu · Naoise Holohan · Samyadeep Basu · Matthew Joseph · My Thai · Xiaoqian Yang · Ellen Vitercik · Michael Hutchinson · Chenghong Wang · Gregory Yauney · Yuchao Tao · Chao Jin · Si Kai Lee · Audra McMillan · Rauf Izmailov · Jiayi Guo · Siddharth Swaroop · Tribhuvanesh Orekondy · Hadi Esmaeilzadeh · Kevin Procopio · Alkis Polyzotis · Jafar Mohammadi · Nitin Agrawal -
2019 : Gaussian Differential Privacy »
Jinshuo Dong · Aaron Roth -
2019 Poster: Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing »
Zhiqi Bu · Jason Klusowski · Cynthia Rush · Weijie Su -
2019 Poster: Acceleration via Symplectic Discretization of High-Resolution Differential Equations »
Bin Shi · Simon Du · Weijie Su · Michael Jordan -
2017 : Strategic Classification from Revealed Preferences »
Jinshuo Dong