Robustness Implies Privacy in Statistical Estimation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913391425093632 |
|---|---|
| author | Hopkins, Samuel B. Kamath, Gautam Majid, Mahbod Narayanan, Shyam |
| author_facet | Hopkins, Samuel B. Kamath, Gautam Majid, Mahbod Narayanan, Shyam |
| contents | We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_05015 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Robustness Implies Privacy in Statistical Estimation Hopkins, Samuel B. Kamath, Gautam Majid, Mahbod Narayanan, Shyam Data Structures and Algorithms Cryptography and Security Information Theory Machine Learning We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples. |
| title | Robustness Implies Privacy in Statistical Estimation |
| topic | Data Structures and Algorithms Cryptography and Security Information Theory Machine Learning |
| url | https://arxiv.org/abs/2212.05015 |