Differentially Private Quantiles with Smaller Error
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915671284121600 |
|---|---|
| author | Imola, Jacob Boninsegna, Fabrizio Keller, Hannah Aamand, Anders Chowdhury, Amrita Roy Pagh, Rasmus |
| author_facet | Imola, Jacob Boninsegna, Fabrizio Keller, Hannah Aamand, Anders Chowdhury, Amrita Roy Pagh, Rasmus |
| contents | In the approximate quantiles problem, the goal is to output $m$ quantile estimates, the ranks of which are as close as possible to $m$ given quantiles $0 \leq q_1 \leq\dots \leq q_m \leq 1$. We present a mechanism for approximate quantiles that satisfies $\varepsilon$-differential privacy for a dataset of $n$ real numbers where the ratio between the distance between the closest pair of points and the size of the domain is bounded by $ψ$. As long as the minimum gap between quantiles is sufficiently large, $|q_i-q_{i-1}|\geq Ω\left(\frac{m\log(m)\log(ψ)}{n\varepsilon}\right)$ for all $i$, the maximum rank error of our mechanism is $O\left(\frac{\log(ψ) + \log^2(m)}{\varepsilon}\right)$ with high probability. Previously, the best known algorithm under pure DP was due to Kaplan, Schnapp, and Stemmer~(ICML '22), who achieved a bound of $O\left(\frac{\log(ψ)\log^2(m) + \log^3(m)}{\varepsilon}\right)$. Our improvement stems from the use of continual counting techniques which allows the quantiles to be randomized in a correlated manner. We also present an $(\varepsilon,δ)$-differentially private mechanism that relaxes the gap assumption without affecting the error bound, improving on existing methods when $δ$ is sufficiently close to zero. We provide experimental evaluation which confirms that our mechanism performs favorably compared to prior work in practice, in particular when the number of quantiles $m$ is large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13662 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Quantiles with Smaller Error Imola, Jacob Boninsegna, Fabrizio Keller, Hannah Aamand, Anders Chowdhury, Amrita Roy Pagh, Rasmus Data Structures and Algorithms In the approximate quantiles problem, the goal is to output $m$ quantile estimates, the ranks of which are as close as possible to $m$ given quantiles $0 \leq q_1 \leq\dots \leq q_m \leq 1$. We present a mechanism for approximate quantiles that satisfies $\varepsilon$-differential privacy for a dataset of $n$ real numbers where the ratio between the distance between the closest pair of points and the size of the domain is bounded by $ψ$. As long as the minimum gap between quantiles is sufficiently large, $|q_i-q_{i-1}|\geq Ω\left(\frac{m\log(m)\log(ψ)}{n\varepsilon}\right)$ for all $i$, the maximum rank error of our mechanism is $O\left(\frac{\log(ψ) + \log^2(m)}{\varepsilon}\right)$ with high probability. Previously, the best known algorithm under pure DP was due to Kaplan, Schnapp, and Stemmer~(ICML '22), who achieved a bound of $O\left(\frac{\log(ψ)\log^2(m) + \log^3(m)}{\varepsilon}\right)$. Our improvement stems from the use of continual counting techniques which allows the quantiles to be randomized in a correlated manner. We also present an $(\varepsilon,δ)$-differentially private mechanism that relaxes the gap assumption without affecting the error bound, improving on existing methods when $δ$ is sufficiently close to zero. We provide experimental evaluation which confirms that our mechanism performs favorably compared to prior work in practice, in particular when the number of quantiles $m$ is large. |
| title | Differentially Private Quantiles with Smaller Error |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.13662 |