Private PAC Learning May be Harder than Online Learning
<|reference_start|>Private PAC Learning May be Harder than Online Learning: We continue the study of the computational complexity of differentially private PAC learning and how it is situated within the foundations of machine learning. A recent line of work uncovered a qualitative equivalence between the private PAC model and Littlestone's mistake-bounded model of online learning, in particular, showing that any concept class of Littlestone dimension $d$ can be privately PAC learned using $\mathrm{poly}(d)$ samples. This raises the natural question of whether there might be a generic conversion from online learners to private PAC learners that also preserves computational efficiency.   We give a negative answer to this question under reasonable cryptographic assumptions (roughly, those from which it is possible to build indistinguishability obfuscation for all circuits). We exhibit a concept class that admits an online learner running in polynomial time with a polynomial mistake bound, but for which there is no computationally-efficient differentially private PAC learner. Our construction and analysis strengthens and generalizes that of Bun and Zhandry (TCC 2016-A), who established such a separation between private and non-private PAC learner.<|reference_end|>
@article{bun2024private,
    title={Private PAC Learning May be Harder than Online Learning},
    author={Mark Bun, Aloni Cohen, Rathin Desai},
    journal={arXiv preprint arXiv:2402.11119},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11119},
    primaryClass={cs.LG cs.CR cs.DS}
}