Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908275408109568 |
|---|---|
| author | Aliakbarpour, Maryam Burudgunte, Arnav Cannone, Clément Rubinfeld, Ronitt |
| author_facet | Aliakbarpour, Maryam Burudgunte, Arnav Cannone, Clément Rubinfeld, Ronitt |
| contents | We extend the framework of augmented distribution testing (Aliakbarpour, Indyk, Rubinfeld, and Silwal, NeurIPS 2024) to the differentially private setting. This captures scenarios where a data analyst must perform hypothesis testing tasks on sensitive data, but is able to leverage prior knowledge (public, but possibly erroneous or untrusted) about the data distribution.
We design private algorithms in this augmented setting for three flagship distribution testing tasks, uniformity, identity, and closeness testing, whose sample complexity smoothly scales with the claimed quality of the auxiliary information. We complement our algorithms with information-theoretic lower bounds, showing that their sample complexity is optimal (up to logarithmic factors). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_14709 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Better Private Distribution Testing by Leveraging Unverified Auxiliary Data Aliakbarpour, Maryam Burudgunte, Arnav Cannone, Clément Rubinfeld, Ronitt Machine Learning Cryptography and Security Data Structures and Algorithms We extend the framework of augmented distribution testing (Aliakbarpour, Indyk, Rubinfeld, and Silwal, NeurIPS 2024) to the differentially private setting. This captures scenarios where a data analyst must perform hypothesis testing tasks on sensitive data, but is able to leverage prior knowledge (public, but possibly erroneous or untrusted) about the data distribution. We design private algorithms in this augmented setting for three flagship distribution testing tasks, uniformity, identity, and closeness testing, whose sample complexity smoothly scales with the claimed quality of the auxiliary information. We complement our algorithms with information-theoretic lower bounds, showing that their sample complexity is optimal (up to logarithmic factors). |
| title | Better Private Distribution Testing by Leveraging Unverified Auxiliary Data |
| topic | Machine Learning Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.14709 |