A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917574960218112 |
|---|---|
| author | Singhal, Vikrant |
| author_facet | Singhal, Vikrant |
| contents | We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_06787 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions Singhal, Vikrant Data Structures and Algorithms Cryptography and Security Machine Learning We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times. |
| title | A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions |
| topic | Data Structures and Algorithms Cryptography and Security Machine Learning |
| url | https://arxiv.org/abs/2304.06787 |