A Computational Separation between Private Learning and Online Learning
This resolves a key question in computational learning theory, providing a negative result that clarifies the computational separation between private and online learning, which is incremental as it builds on prior equivalence studies.
The paper tackles the problem of efficiently converting differentially private PAC learners into online learners, showing that such an efficient conversion is impossible for general pure-private learners with polynomial sample complexity, assuming one-way functions exist.
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).