Test without Trust: Optimal Locally Private Distribution Testing

Jayadev Acharya, Clement Canonne, Cody Freitag, Himanshu Tyagi
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2067-2076, 2019.

Abstract

We study the problem of distribution testing when the samples can only be accessed using a locally differentially private mechanism and focus on two representative testing questions of identity (goodness-of-fit) and independence testing for discrete distributions. First, we construct tests that use existing, general-purpose locally differentially private mechanisms such as the popular RAPPOR or the recently introduced Hadamard Response for collecting data and show that our proposed tests are sample optimal, when we insist on using these mechanisms. Next, we allow bespoke mechanisms designed specifically for testing and introduce the Randomized Aggregated Private Testing Optimal Response (RAPTOR) mechanism which is remarkably simple and requires only one bit of communication per sample. We show that our proposed mechanism yields sample-optimal tests, and in particular outperforms any test based on RAPPOR or Hadamard response. A distinguishing feature of our optimal mechanism is that, in contrast to existing mechanisms, it uses public randomness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-acharya19b, title = {Test without Trust: Optimal Locally Private Distribution Testing}, author = {Acharya, Jayadev and Canonne, Clement and Freitag, Cody and Tyagi, Himanshu}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2067--2076}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/acharya19b/acharya19b.pdf}, url = {https://proceedings.mlr.press/v89/acharya19b.html}, abstract = {We study the problem of distribution testing when the samples can only be accessed using a locally differentially private mechanism and focus on two representative testing questions of identity (goodness-of-fit) and independence testing for discrete distributions. First, we construct tests that use existing, general-purpose locally differentially private mechanisms such as the popular RAPPOR or the recently introduced Hadamard Response for collecting data and show that our proposed tests are sample optimal, when we insist on using these mechanisms. Next, we allow bespoke mechanisms designed specifically for testing and introduce the Randomized Aggregated Private Testing Optimal Response (RAPTOR) mechanism which is remarkably simple and requires only one bit of communication per sample. We show that our proposed mechanism yields sample-optimal tests, and in particular outperforms any test based on RAPPOR or Hadamard response. A distinguishing feature of our optimal mechanism is that, in contrast to existing mechanisms, it uses public randomness.} }
Endnote
%0 Conference Paper %T Test without Trust: Optimal Locally Private Distribution Testing %A Jayadev Acharya %A Clement Canonne %A Cody Freitag %A Himanshu Tyagi %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-acharya19b %I PMLR %P 2067--2076 %U https://proceedings.mlr.press/v89/acharya19b.html %V 89 %X We study the problem of distribution testing when the samples can only be accessed using a locally differentially private mechanism and focus on two representative testing questions of identity (goodness-of-fit) and independence testing for discrete distributions. First, we construct tests that use existing, general-purpose locally differentially private mechanisms such as the popular RAPPOR or the recently introduced Hadamard Response for collecting data and show that our proposed tests are sample optimal, when we insist on using these mechanisms. Next, we allow bespoke mechanisms designed specifically for testing and introduce the Randomized Aggregated Private Testing Optimal Response (RAPTOR) mechanism which is remarkably simple and requires only one bit of communication per sample. We show that our proposed mechanism yields sample-optimal tests, and in particular outperforms any test based on RAPPOR or Hadamard response. A distinguishing feature of our optimal mechanism is that, in contrast to existing mechanisms, it uses public randomness.
APA
Acharya, J., Canonne, C., Freitag, C. & Tyagi, H.. (2019). Test without Trust: Optimal Locally Private Distribution Testing. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2067-2076 Available from https://proceedings.mlr.press/v89/acharya19b.html.

Related Material