A Computational Separation between Private Learning and Online Learning
Abstract
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).
BibTeX
@inproceedings{NEURIPS2020_ee715daa,
author = {Bun, Mark},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {20732--20743},
publisher = {Curran Associates, Inc.},
title = {A Computational Separation between Private Learning and Online Learning},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/ee715daa76f1b51d80343f45547be570-Paper.pdf},
volume = {33},
year = {2020}
}