The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model
We provide a lowerbound on the sample complexity of distribution-free parity learning in the realizable case in the shuffle model of differential privacy. Namely, we show that the sample complexity of learning d-bit parity functions is Ω(2d/2). Our result extends a recent similar lowerbound o...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Labor Dynamics Institute
2022-11-01
|
| Series: | The Journal of Privacy and Confidentiality |
| Subjects: | |
| Online Access: | https://journalprivacyconfidentiality.org/index.php/jpc/article/view/805 |