Differentially Private Approximate Quantiles
In this work we study the problem of differentially private (DP) quantiles, in which given dataset $X$ and quantiles $q_1, ..., q_m \in [0,1]$, we want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call ApproximateQuantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Differentially Private Quantiles
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 resu…
Unbounded Differentially Private Quantile and Maximum Estimation
In this work we consider the problem of differentially private computation of quantiles for the data, especially the highest quantiles such as maximum, but with an unbounded range for the dataset. We show that this can b…
DPpack: An R Package for Differentially Private Statistical Analysis and Machine Learning
Differential privacy (DP) is the state-of-the-art framework for guaranteeing privacy for individuals when releasing aggregated statistics or building statistical/machine learning models from data. We develop the open-sou…
DescriptivePrivacy PreservingregressionPrivate PAC learning implies finite Littlestone dimension
We show that every approximately differentially private learning algorithm (possibly improper) for a class $H$ with Littlestone dimension~$d$ requires $\Omega\bigl(\log^*(d)\bigr)$ examples. As a corollary it follows tha…
Open-Ended Question AnsweringPAC learningDifferentially Private Conformal Prediction via Quantile Binary Search
Most Differentially Private (DP) approaches focus on limiting privacy leakage from learners based on the data that they are trained on, there are fewer approaches that consider leakage when procedures involve a calibrati…