Timezone: »
Differentially Private Quantiles
Jennifer Gillenwater · Matthew Joseph · Alex Kulesza
Quantiles are often used for summarizing and understanding data. If that data is sensitive, it may be necessary to compute quantiles in a way that is differentially private, providing theoretical guarantees that the result does not reveal private information. However, in the common case where multiple quantiles are needed, existing differentially private algorithms scale poorly: they compute each quantile individually, splitting their privacy budget and thus decreasing accuracy. In this work we propose an instance of the exponential mechanism that simultaneously estimates $m$ quantiles from $n$ data points while guaranteeing differential privacy. The utility function is carefully structured to allow for an efficient implementation that returns estimates of all $m$ quantiles in time $O(mn\log(n) + m^2n)$. Experiments show that our method significantly outperforms the current state of the art on both real and synthetic data while remaining efficient enough to be practical.
Author Information
Jennifer Gillenwater (Google Research NYC)
Matthew Joseph (Google)
Alex Kulesza (Google)
More from the Same Authors
-
2021 : Learning with User-Level Privacy »
Daniel A Levy · Ziteng Sun · Kareem Amin · Satyen Kale · Alex Kulesza · Mehryar Mohri · Ananda Theertha Suresh -
2021 : Shuffle Private Stochastic Convex Optimization »
Albert Cheu · Matthew Joseph · Jieming Mao · Binghui Peng -
2023 Poster: Subset-Based Instance Optimality in Private Estimation »
Travis Dick · Alex Kulesza · Ziteng Sun · Ananda Suresh -
2022 Poster: A Joint Exponential Mechanism For Differentially Private Top-$k$ »
Jennifer Gillenwater · Matthew Joseph · andres munoz · Monica Ribero Diaz -
2022 Spotlight: A Joint Exponential Mechanism For Differentially Private Top-$k$ »
Jennifer Gillenwater · Matthew Joseph · andres munoz · Monica Ribero Diaz -
2021 Poster: Differentially Private Quantiles »
Jennifer Gillenwater · Matthew Joseph · Alex Kulesza -
2021 Spotlight: Differentially Private Quantiles »
Jennifer Gillenwater · Matthew Joseph · Alex Kulesza -
2020 : Scaling DPP MAP Inference »
Jennifer Gillenwater -
2019 Workshop: Negative Dependence: Theory and Applications in Machine Learning »
Mike Gartrell · Jennifer Gillenwater · Alex Kulesza · Zelda Mariet -
2019 Poster: Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy »
Kareem Amin · Alex Kulesza · andres munoz · Sergei Vassilvitskii -
2019 Oral: Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy »
Kareem Amin · Alex Kulesza · andres munoz · Sergei Vassilvitskii -
2019 Poster: A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes »
Jennifer Gillenwater · Alex Kulesza · Zelda Mariet · Sergei Vassilvitskii -
2019 Oral: A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes »
Jennifer Gillenwater · Alex Kulesza · Zelda Mariet · Sergei Vassilvitskii