Private Learning Implies Online Learning: An Efficient Reduction

Alon Gonen; Elad Hazan; Shay Moran

NeurIPS 2019spotlight24 citations

Private Learning Implies Online Learning: An Efficient Reduction

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?

BibTeX

@inproceedings{NEURIPS2019_700fdb2b,
 author = {Gonen, Alon and Hazan, Elad and Moran, Shay},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Private Learning Implies Online Learning: An Efficient Reduction},
 url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/700fdb2ba62d4554dc268c65add4b16e-Paper.pdf},
 volume = {32},
 year = {2019}
}