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 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.