Find in Library
Search millions of books, articles, and more
Indexed Open Access Databases
The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model
oleh: Kobbi Nissim, Chao Yan
Format: | Article |
---|---|
Diterbitkan: | Labor Dynamics Institute 2022-11-01 |
Deskripsi
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 on the sample complexity of private agnostic learning of parity functions in the shuffle model by Cheu and Ullman . We also sketch a simple shuffle model protocol demon- strating that our results are tight up to poly(d) factors.