Timezone: »
Spotlight
Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
Gavin Brown · Marco Gaboardi · Adam Smith · Jonathan Ullman · Lydia Zakynthinou
@
We present two sample-efficient differentially private mean estimators for $d$-dimensional (sub)Gaussian distributions with unknown covariance. Informally, given $n \gtrsim d/\alpha^2$ samples from such a distribution with mean $\mu$ and covariance $\Sigma$, our estimators output $\tilde\mu$ such that $\| \tilde\mu - \mu \|_{\Sigma} \leq \alpha$, where $\| \cdot \|_{\Sigma}$ is the \emph{Mahalanobis distance}. All previous estimators with the same guarantee either require strong a priori bounds on the covariance matrix or require $\Omega(d^{3/2})$ samples. Each of our estimators is based on a simple, general approach to designing differentially private mechanisms, but with novel technical steps to make the estimator private and sample-efficient. Our first estimator samples a point with approximately maximum Tukey depth using the exponential mechanism, but restricted to the set of points of large Tukey depth. Proving that this mechanism is private requires a novel analysis. Our second estimator perturbs the empirical mean of the data set with noise calibrated to the empirical covariance. Only the mean is released, however; the covariance is only used internally. Its sample complexity guarantees hold more generally for subgaussian distributions, albeit with a slightly worse dependence on the privacy parameter. For both estimators, careful preprocessing of the data is required to satisfy differential privacy.
Author Information
Gavin Brown (Boston University)
Marco Gaboardi (Boston University)
Adam Smith (Boston University)
Jonathan Ullman (Northeastern University)
Lydia Zakynthinou (Northeastern University)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Covariance-Aware Private Mean Estimation Without Private Covariance Estimation »
Thu. Dec 9th 04:30 -- 06:00 PM Room
More from the Same Authors
-
2021 Spotlight: Differentially Private Model Personalization »
Prateek Jain · John Rush · Adam Smith · Shuang Song · Abhradeep Guha Thakurta -
2023 Poster: Hypothesis Selection with Memory Constraints »
Maryam Aliakbarpour · Mark Bun · Adam Smith -
2023 Poster: Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation »
Palak Jain · Iden Kalemaj · Sofya Raskhodnikova · Satchit Sivakumar · Adam Smith -
2022 Poster: Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams »
Sergey Denisov · H. Brendan McMahan · John Rush · Adam Smith · Abhradeep Guha Thakurta -
2021 Poster: Differentially Private Model Personalization »
Prateek Jain · John Rush · Adam Smith · Shuang Song · Abhradeep Guha Thakurta -
2021 Poster: Differentially Private Sampling from Distributions »
Sofya Raskhodnikova · Satchit Sivakumar · Adam Smith · Marika Swanberg -
2021 Poster: Multiclass versus Binary Differentially Private PAC Learning »
Satchit Sivakumar · Mark Bun · Marco Gaboardi -
2020 Poster: CoinPress: Practical Private Mean and Covariance Estimation »
Sourav Biswas · Yihe Dong · Gautam Kamath · Jonathan Ullman -
2020 Poster: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2020 Poster: Auditing Differentially Private Machine Learning: How Private is Private SGD? »
Matthew Jagielski · Jonathan Ullman · Alina Oprea -
2020 Spotlight: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2019 Poster: Differentially Private Algorithms for Learning Mixtures of Separated Gaussians »
Gautam Kamath · Or Sheffet · Vikrant Singhal · Jonathan Ullman -
2019 Poster: Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy »
Jonathan Ullman · Adam Sealfon -
2018 : Invited talk 4: Models for private data analysis of distributed data »
Adam Smith -
2018 Poster: The Limits of Post-Selection Generalization »
Jonathan Ullman · Adam Smith · Kobbi Nissim · Uri Stemmer · Thomas Steinke -
2018 Poster: Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization »
Blake Woodworth · Jialei Wang · Adam Smith · Brendan McMahan · Nati Srebro -
2018 Spotlight: Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization »
Blake Woodworth · Jialei Wang · Adam Smith · Brendan McMahan · Nati Srebro -
2018 Poster: Improved Algorithms for Collaborative PAC Learning »
Huy Nguyen · Lydia Zakynthinou -
2018 Poster: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2018 Spotlight: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2016 Poster: Privacy Odometers and Filters: Pay-as-you-Go Composition »
Ryan Rogers · Salil Vadhan · Aaron Roth · Jonathan Ullman