null
(Ed.)
A recent line of work has shown a qualitative equivalence between differentially
private PAC learning and online learning: A concept class is privately learnable
if and only if it is online learnable with a finite mistake bound. However, both
directions of this equivalence incur significant losses in both sample and computational efficiency. Studying a special case of this connection, Gonen, Hazan, and
Moran (NeurIPS 2019) showed that uniform or highly sample-efficient pure-private
learners can be time-efficiently compiled into online learners. We show that, assuming the existence of one-way functions, such an efficient conversion is impossible
even for general pure-private learners with polynomial sample complexity. This
resolves a question of Neel, Roth, and Wu (FOCS 2019).
more »
« less