Private PAC Learning May be Harder than Online Learning

Mark Bun, Aloni Cohen, Rathin Desai

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 wor…