Poster
Private Learning Implies Online Learning: An Efficient Reduction
Alon Gonen · Elad Hazan · Shay Moran

Thu Dec 12th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #24
in Algorithms -- Online Learning »

We study the relationship between the notions of differentially private learning and online learning. 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.

Keywords: Theory · Algorithms -> Adaptive Data Analysis; Algorithms -> Classification; Algorithms -> Online Learning; Applications -> Privacy, Ano

Author Information

Alon Gonen (UCSD)
Elad Hazan (Princeton University)
Shay Moran (Google AI Princeton)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors