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

• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  We show that for a broad class of data structures their bounds cannot be significantly improved. This is a novel emphstatistical-computational trade-off for density estimation.
  arXiv  Detail & Related papers  (2024-10-30T15:03:33Z)
• Privately Counting Partially Ordered Data [50.98561191019676]
  We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d2)$.
  arXiv  Detail & Related papers  (2024-10-09T13:43:35Z)
• Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy [36.04370583654189]
  We show how the 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)
• 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.