Differentially Private Approximate Quantiles
- URL: http://arxiv.org/abs/2110.05429v1
- Date: Mon, 11 Oct 2021 17:19:27 GMT
- Title: Differentially Private Approximate Quantiles
- Authors: Haim Kaplan, Shachar Schnapp, Uri Stemmer
- Abstract summary: In this work we study the problem of differentially private (DP) quantiles.
We want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP.
- Score: 27.950292359069216
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy [36.04370583654189]
We show how a clipping mechanism can achieve an instance-optimal error of $O(max_i x_i cdot loglog U /varepsilon)$.
We also extend our technique to the high-dimensional sum estimation problem and sparse vector aggregation.
arXiv Detail & Related papers (2024-03-15T09:04:00Z) - User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
We consider the example-scarce regime, where each user has only a few examples, and obtain the following results.
For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm.
We present a simple technique for adapting the exponential mechanism [McSherry, Talwar FOCS 2007] to the user-level setting.
arXiv Detail & Related papers (2023-09-21T21:51:55Z) - Data Structures for Density Estimation [66.36971978162461]
Given a sublinear (in $n$) number of samples from $p$, our main result is the first data structure that identifies $v_i$ in time sublinear in $k$.
We also give an improved version of the algorithm of Acharya et al. that reports $v_i$ in time linear in $k$.
arXiv Detail & Related papers (2023-06-20T06:13:56Z) - Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
We show that a simple invocation of $textttAboveThreshold$ can give more accurate and robust estimates on the highest quantiles.
We show that an improved analysis of $textttAboveThreshold$ can improve the privacy guarantees for the widely used Sparse Vector Technique.
arXiv Detail & Related papers (2023-05-02T03:23:07Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
We give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models.
In the pure DP setting, we give an efficient algorithm that estimates an unknown $d$-dimensional Gaussian distribution up to an arbitrary tiny total variation error.
For the special case of mean estimation, our algorithm achieves the optimal sample complexity of $widetilde O(d)$, improving on a $widetilde O(d1.5)$ bound from prior work.
arXiv Detail & Related papers (2022-12-15T18:27:39Z) - Differentially Private Quantiles [12.917299605014419]
We propose an instance of the exponential mechanism that simultaneously estimates $m$ quantiles from $n$ data points.
Our method significantly outperforms the current state of the art on both real and synthetic data.
arXiv Detail & Related papers (2021-02-16T16:02:59Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
We study the fundamental task of list-decodable mean estimation in high dimensions.
Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset.
A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
arXiv Detail & Related papers (2020-11-19T17:21:37Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
We show that a modified greedy algorithm can achieve an approximation factor of $0.305$.
We derive a data-dependent upper bound on the optimum.
It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
arXiv Detail & Related papers (2020-08-12T15:40:21Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized.
This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
arXiv Detail & Related papers (2020-04-16T19:16:38Z) - Differentially Quantized Gradient Methods [53.3186247068836]
We show that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $maxsigma_mathrmGD, rhon 2-R$.
No algorithm within a certain class can converge faster than $maxsigma_mathrmGD, 2-R$.
arXiv Detail & Related papers (2020-02-06T20:40:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.