Bounds on the sample complexity for private learning and private data release
Bounds on the sample complexity for private learning and private data release
A. Beimel,H. Brenner,S. Kasiviswanathan,Kobbi Nissim
2010 · DOI: 10.1007/s10994-013-5404-1
Machine-mediated learning · 215 Citations
TLDR
This work examines several private learning tasks and shows strong separations between sample complexities of proper and improper private learners (such separation does not exist for non-private learners), and between sample complexities of efficient and inefficient proper private learners.