Profile Reconstruction from Private Sketches
Given a multiset of $n$ items from $\mathcal{D}$, the \emph{profile reconstruction} problem is to estimate, for $t = 0, 1, \dots, n$, the fraction $\vec{f}[t]$ of items in $\mathcal{D}$ that appear exactly $t$ times. We consider differentially private profile estimation in a distributed, space-const...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Artikel |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2406.01158 http://arxiv.org/abs/2406.01158 |
| Tags: |
Keine Tags, Fügen Sie das erste Tag hinzu!
|
| _version_ | 1879175746561245184 |
|---|---|
| author | Wu, Hao Pagh, Rasmus |
| author_browse | Pagh, Rasmus Wu, Hao |
| author_facet | Wu, Hao Pagh, Rasmus |
| author_sort | Wu, Hao |
| building | arXiv |
| collection | Acceso abierto |
| description | Given a multiset of $n$ items from $\mathcal{D}$, the \emph{profile reconstruction} problem is to estimate, for $t = 0, 1, \dots, n$, the fraction $\vec{f}[t]$ of items in $\mathcal{D}$ that appear exactly $t$ times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset that allows us to compute an approximation of $\vec{f} = (\vec{f}[0], \dots, \vec{f}[n])$. Using a histogram privatized using discrete Laplace noise, we show how to ``reverse'' the noise, using an approach of Dwork et al.~(ITCS '10). We show how to speed up their LP-based technique from polynomial time to $O(d + n \log n)$, where $d = |\mathcal{D}|$, and analyze the achievable error in the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. In all cases the dependency of the error on $d$ is $O( 1 / \sqrt{d})$ -- we give an information-theoretic lower bound showing that this dependence on $d$ is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee. |
| first_indexed | 2026-10-16T00:33:55Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2406.01158</identifier><datestamp>2024-06-04</datestamp>
<dc:title>Profile Reconstruction from Private Sketches</dc:title>
<dc:creator>Wu, Hao</dc:creator>
<dc:creator>Pagh, Rasmus</dc:creator>
<dc:subject>Cryptography and Security</dc:subject>
<dc:subject>Data Structures and Algorithms</dc:subject>
<dc:description>Given a multiset of $n$ items from $\mathcal{D}$, the \emph{profile reconstruction} problem is to estimate, for $t = 0, 1, \dots, n$, the fraction $\vec{f}[t]$ of items in $\mathcal{D}$ that appear exactly $t$ times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset that allows us to compute an approximation of $\vec{f} = (\vec{f}[0], \dots, \vec{f}[n])$. Using a histogram privatized using discrete Laplace noise, we show how to ``reverse'' the noise, using an approach of Dwork et al.~(ITCS '10). We show how to speed up their LP-based technique from polynomial time to $O(d + n \log n)$, where $d = |\mathcal{D}|$, and analyze the achievable error in the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. In all cases the dependency of the error on $d$ is $O( 1 / \sqrt{d})$ -- we give an information-theoretic lower bound showing that this dependence on $d$ is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee. </dc:description>
<dc:description>ICML 2024</dc:description>
<dc:date>2024-06-03</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2406.01158</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2406.01158</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2406.01158 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:33:55Z |
| publishDate | 2024 |
| publishDateRange | 2024 |
| publishDateSort | 2024 |
| record_format | oai_dc |
| spelling | arxiv-2406.011582024-06-04 Profile Reconstruction from Private Sketches Wu, Hao Pagh, Rasmus Cryptography and Security Data Structures and Algorithms Given a multiset of $n$ items from $\mathcal{D}$, the \emph{profile reconstruction} problem is to estimate, for $t = 0, 1, \dots, n$, the fraction $\vec{f}[t]$ of items in $\mathcal{D}$ that appear exactly $t$ times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset that allows us to compute an approximation of $\vec{f} = (\vec{f}[0], \dots, \vec{f}[n])$. Using a histogram privatized using discrete Laplace noise, we show how to ``reverse'' the noise, using an approach of Dwork et al.~(ITCS '10). We show how to speed up their LP-based technique from polynomial time to $O(d + n \log n)$, where $d = |\mathcal{D}|$, and analyze the achievable error in the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. In all cases the dependency of the error on $d$ is $O( 1 / \sqrt{d})$ -- we give an information-theoretic lower bound showing that this dependence on $d$ is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee. ICML 2024 2024-06-03 text https://arxiv.org/abs/2406.01158 http://arxiv.org/abs/2406.01158 |
| spellingShingle | Cryptography and Security Data Structures and Algorithms Wu, Hao Pagh, Rasmus Profile Reconstruction from Private Sketches |
| title | Profile Reconstruction from Private Sketches |
| title_full | Profile Reconstruction from Private Sketches |
| title_fullStr | Profile Reconstruction from Private Sketches |
| title_full_unstemmed | Profile Reconstruction from Private Sketches |
| title_short | Profile Reconstruction from Private Sketches |
| title_sort | profile reconstruction from private sketches |
| topic | Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.01158 http://arxiv.org/abs/2406.01158 |
| work_keys_str_mv | AT wuhao profilereconstructionfromprivatesketches AT paghrasmus profilereconstructionfromprivatesketches |