Skip to main content

Private Learning Implies Online Learning: An Efficient Reduction

Author(s): Gonen, Alon; Hazan, Elad; Moran, Shay

To refer to this page use:
Abstract: 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.
Publication Date: 2019
Citation: Gonen, Alon, Elad Hazan, and Shay Moran. "Private Learning Implies Online Learning: An Efficient Reduction." Advances in Neural Information Processing Systems 32 (2019).
ISSN: 1049-5258
Type of Material: Conference Article
Journal/Proceeding Title: Advances in Neural Information Processing Systems
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.