Private Learning Implies Online Learning: An Efficient Reduction
This work addresses a theoretical question in machine learning about the efficiency of connections between privacy and online learning, which is incremental as it builds on prior implications.
The paper resolves an open problem by showing that an efficient differentially private learner implies an efficient online learner, providing a black-box reduction in the context of pure differential privacy.
We study the relationship between the notions of differentially private learning and online learning in games. Several recent works have shown that differentially private learning implies online learning, but an open problem of Neel, Roth, and Wu \cite{NeelAaronRoth2018} asks whether this implication is {\it efficient}. Specifically, does an efficient differentially private learner imply an efficient online learner? In this paper we resolve this open question in the context of pure differential privacy. We derive an efficient black-box reduction from differentially private learning to online learning from expert advice.