What Can We Learn Privately? II: Parity Functions Are Privately PAC Learnable from O(d log(1/β)/(εα)) ExamplesResearch Paper
Differential privacy (Dwork, McSherry, Nissim and Smith, 2006) requires a randomized algorithm's output distribution to change little when one individual's record is changed. PAC learning asks an algorithm to output, from i.i.d. labeled examples, a hypothesis whose error is small with high probability. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith (a…